Debian Codegraph @

examples/python/bounded model checking/bubble_sort.py

raw
1 # File name: bubble_sort.py
2 #
3 # BUBBLESORT - Copyright (c) June, 2020 - Matteo Nicoli
4
5 from z3 import Solver, Int, Array, IntSort, And, Not, If, Select, Store, sat
6
7 def init(i,j) :
8 return And(i == 0, j == 0)
9
10 def invert(A0, A1, tmp, i0, i1) :
11 return If(Select(A0, i0) > Select(A0, i0 + 1), \
12 And(tmp == Select(A0, i0), \
13 A1 == Store(A0, i0, Select(A0, i0 + 1)), \
14 A1 == Store(A0, i0 + 1, tmp)), \
15 A1 == A0)
16
17 def bsort_step(A0, A1, tmp, i0, j0, i1, j1, dim) :
18 return If( j0 < dim - 1, \
19 And( \
20 If( i0 < dim - 1, \
21 And(invert(A0, A1, tmp, i0, i1),i1 == i0 + 1), \
22 i1 == i0 + 1), \
23 j1 == j0 + 1), \
24 And(j1 == j0 + 1, A1 == A0))
25
26 def mk_tran_condition(A, i, j, tmp, dim) :
27 condition = []
28 for _ in range(dim) :
29 condition.append(bsort_step(A[0],A[1],tmp[0],i[0],j[0],i[1],j[1],dim))
30 A = A[1:]
31 i = i[1:]
32 j = j[1:]
33 tmp = tmp[1:]
34 return condition
35
36 def check(variables, Ar, dim) :
37 for e in range(dim) :
38 yield variables[e] == Select(Ar,e)
39
40 def mk_post_condition(values) :
41 condition = [v1 <= v2 for v1,v2 in zip(values,values[1:])]
42 return And(*condition)
43
44
45 def main() :
46 dim = int(input("size of the array: "))
47
48 i = [Int(f"i_{x}") for x in range(dim + 1)]
49 j = [Int(f"j_{x}") for x in range(dim + 1)]
50 A = [Array(f"A_{x}",IntSort(),IntSort()) for x in range(dim + 1)]
51 tmp = [Int(f"tmp_{x}") for x in range(dim)]
52
53 s = Solver()
54
55 init_condition = init(i[0],j[0])
56 s.add(init_condition)
57
58 tran_condition = mk_tran_condition(A, i, j, tmp, dim)
59 s.add(And(*tran_condition))
60
61 values = [Int(f"n_{x}") for x in range(dim)]
62 init_check_condition = check(values,A[-1],dim)
63 s.add(And(*init_check_condition))
64
65 post_condition = mk_post_condition(values)
66
67 print("Bubble sort")
68 print("---------------------")
69
70 s.push()
71 s.add(Not(post_condition))
72
73 print("Testing the validity of the algorithm; `valid expected`:")
74
75 if s.check() == sat :
76 print(f"counterexample:\n{s.model()}")
77 else :
78 print("valid")
79
80 print("---------------------")
81
82 s.pop()
83
84 s.add(post_condition)
85 print("Getting a model...")
86 print("Model:")
87
88 if s.check() == sat :
89 print(s.model())
90
91
92 if __name__ == "__main__" :
93 main()