Common — library colibrilib.pbdd — module PBDD_intf
1
module PBDD_intf

Abstract

2
use mach.int.Int63
3
use list.List
4
use list.Mem
5
use list.Distinct
6
use colibrilib.bdd.Key
7
use int.Int
8
use set.Set
9
use bool.Bool
10
use colibrilib.bdd.Node
11
use colibrilib.zarith.Zbit
12
use colibrilib.sbdd.SNode
13
use colibrilib.bdd.IArray63
14
15
type
t
16
type
indexes
= int
17
type
snodes
= Set.set snode
18
function
dom_indexes
(x:t) : indexes Valid (40ms) (colibri2)
19
axiom
dom_indexes_pos
: forall x:t. 0 <= dom_indexes x
20
function
dom_snodes
(x:t) : snodes
21
function
v
(x:t): indexes -> snodes -> bool
22
Valid (45ms) (colibri2)
23
axiom
support_v
: forall x id1 id2 sn.
24
(forall i. 0 <= i -> Zbit.bittest x.dom_indexes i -> (Zbit.bittest id1 i <-> Zbit.bittest id2 i)) ->
25
x.v id1 sn = x.v id2 sn
26
27
(* axiom false_after_numbits: forall x id sn. x.dom_numbits <= id -> x.v id sn = False *)
28
Valid (36ms) (colibri2)
29
val
dand
(x y: t) : t
30
ensures { result.dom_indexes = Zbit.lor x.dom_indexes y.dom_indexes }
31
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
32
ensures { result.v = (fun id sn -> andb (x.v id sn) (y.v id sn)) }
33
Valid (39ms) (colibri2)
34
val
dor
(x y: t) : t
35
ensures { result.dom_indexes = Zbit.lor x.dom_indexes y.dom_indexes }
36
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
37
ensures { result.v = (fun id sn -> orb (x.v id sn) (y.v id sn)) }
38
Valid (33ms) (colibri2)
39
val
dxor
(x y: t) : t
40
ensures { result.dom_indexes = Zbit.lor x.dom_indexes y.dom_indexes }
41
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
42
ensures { result.v = (fun id sn -> xorb (x.v id sn) (y.v id sn)) }
43
Valid (33ms) (colibri2)
44
val
tfalse
() : t
45
ensures { result.dom_indexes = 0 }
46
ensures { result.dom_snodes = Set.empty }
47
ensures { result.v = (fun _ _ -> False) }
48
Valid (29ms) (colibri2)
49
val
ttrue
() : t
50
ensures { result.dom_indexes = 0 }
51
ensures { result.dom_snodes = Set.empty }
52
ensures { result.v = (fun _ _ -> True) }
53
54
Valid (35ms) (colibri2)
55
val
dnot
(a: t) : t
56
ensures { result.dom_indexes = a.dom_indexes }
57
ensures { result.dom_snodes = a.dom_snodes }
58
ensures { result.v = (fun id sn -> notb (a.v id sn)) }
59
Valid (35ms) (colibri2)
60
val
is_equal
(x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)
61
ensures { result = (forall id sn. x.v id sn = y.v id sn) }
62
ensures { not result ->
63
0 <= wid /\ numbits wid <= numbits (Zbit.lor x.dom_indexes y.dom_indexes) /\
64
(Zbit.subset wid (Zbit.lor x.dom_indexes y.dom_indexes)) /\
65
(Set.subset wsn (Set.union x.dom_snodes y.dom_snodes)) /\
66
x.v wid wsn <> y.v wid wsn }
67
Valid (62ms) (colibri2)
68
val
is_inter_empty
(x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)
69
ensures { result = (forall id sn. not (x.v id sn /\ y.v id sn)) }
70
ensures { not result ->
71
(forall i. Zbit.bittest wid i -> Zbit.bittest (Zbit.lor x.dom_indexes y.dom_indexes) i) /\
72
(forall i. Set.mem i wsn -> Set.mem i (Set.union x.dom_snodes y.dom_snodes)) /\
73
x.v wid wsn /\ y.v wid wsn }
74
Valid (31ms) (colibri2)
75
val partial
bdd_of_index
(i: int63) : t
76
requires { 0 <= to_int i }
77
ensures { result.dom_indexes = Zbit.lsl 1 (to_int i) }
78
ensures { result.dom_snodes = Set.empty }
79
ensures { result.v = (fun id _ -> Zbit.bittest id (to_int i)) }
80
Valid (36ms) (colibri2)
81
val partial
bdd_of_snode
(v: snode) : t
82
ensures { result.dom_indexes = 0 }
83
ensures { result.dom_snodes = Set.singleton v }
84
ensures { result.v = (fun _ sn -> sn v) }
85
Valid (33ms) (colibri2)
86
val partial
bdd_not_snode
(v: snode) : t
87
ensures { result.dom_indexes = 0 }
88
ensures { result.dom_snodes = Set.singleton v }
89
ensures { result.v = (fun _ sn -> not (sn v)) }
90
Valid (84ms) (cvc4)
91
val partial
ite_index
(i: int63) (aa bb: t) : t
92
requires { 0 <= to_int i }
93
ensures { result.dom_indexes = Zbit.set (Zbit.lor aa.dom_indexes bb.dom_indexes) i }
94
ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }
95
ensures { result.v = (fun id sn -> if Zbit.bittest id i then aa.v id sn else bb.v id sn) }

ite_index for the indexes 0, 1, 2, in ghost code

    Valid (103ms) (colibri2)
98
val ghost
ite_index_g
(i: int63) (aa bb: t) : t
99
requires { 0 <= to_int i < 3 }
100
ensures { result.dom_indexes = Zbit.set (Zbit.lor aa.dom_indexes bb.dom_indexes) i }
101
ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }
102
ensures { result.v = (fun id sn -> if Zbit.bittest id i then aa.v id sn else bb.v id sn) }
103
Valid (35ms) (colibri2)
104
val partial
ite_snode
(v: snode) (aa bb: t) : t
105
ensures { result.dom_indexes = (Zbit.lor aa.dom_indexes bb.dom_indexes) }
106
ensures { result.dom_snodes = Set.add v (Set.union aa.dom_snodes bb.dom_snodes) }
107
ensures { result.v = (fun id sn -> if sn v then aa.v id sn else bb.v id sn) }
108
109
function
nb_nodes
(a:t) : int

The snodes of the BDD, included in the domain

113
function
support_snodes
(a:t) : snodes
114
Valid (33ms) (colibri2)
115
axiom
support_snodes_dom
: forall x. Set.subset (support_snodes x) x.dom_snodes

A snode of the support changes the value

    Valid (70ms) (colibri2)
118
axiom
support_snodes_dep
: forall x nd. Set.mem nd (support_snodes x) ->
119
exists id sn. x.v id (Set.add nd sn) <> x.v id (Set.remove nd sn)
120
Valid (49ms) (colibri2)
121
axiom
support_snodes_v
: forall x id sn1 sn2.
122
(forall nd. Set.mem nd (support_snodes x) -> sn1 nd = sn2 nd) ->
123
x.v id sn1 = x.v id sn2
124
Valid (36ms) (colibri2)
125
val
vars
(a:t) : list Key.t
126
ensures { forall n s ab. Mem.mem (Key.Var n s ab) result <-> Set.mem { n = n; s = s; scal = ab } (support_snodes a) }
127
ensures { Distinct.distinct result }
128
129
type
inspect
=
Bool
bool |
IteIndex
int63 t t |
IteSnode
snode t t

The bits of the substitution subst on the valuation id, sn

132
function
subst_bits
(subst: IArray63.t t) (id: indexes) (sn: snodes) : int -> bool =
133
fun i -> (subst i).v id sn

Substitution of shift_left_gen: the index i by subst i and the snode nd by shift_snode nd off

    Valid (42ms) (colibri2)
137
val partial
compose_shift
(subst: IArray63.t t) (off: int63) (x: t) : t
138
requires { numbits x.dom_indexes <= subst.IArray63.length }
139
ensures { forall nd. Set.mem nd (support_snodes x) -> nd.scal \/ in_bounds (to_int nd.s - to_int off) }
140
raises { Overflow -> exists nd. Set.mem nd (support_snodes x) /\ not nd.scal /\ not (in_bounds (to_int nd.s - to_int off)) }
141
ensures { (forall j. 0 <= j < subst.IArray63.length ->
142
numbits (subst j).dom_indexes <= subst.IArray63.length) ->
143
numbits result.dom_indexes <= subst.IArray63.length }
144
ensures { forall id sn. result.v id sn =
145
x.v (of_bits (subst_bits subst id sn) subst.IArray63.length)
146
(shifted sn (to_int off)) }
147
ensures { forall nd''. Set.mem nd'' (support_snodes result) ->
148
(exists j. 0 <= j < subst.IArray63.length /\ Set.mem nd'' (support_snodes (subst j))) \/
149
(exists nd. Set.mem nd (support_snodes x) /\ nd'' = shift_snode nd (to_int off)) }
150
Valid (30ms) (colibri2)
151
val partial
cofactors_snode
(nd: snode) (a: t) : (t, t)
152
returns { (p, n) ->
153
p.dom_indexes = a.dom_indexes /\
154
n.dom_indexes = a.dom_indexes /\
155
p.dom_snodes = Set.remove nd a.dom_snodes /\
156
n.dom_snodes = Set.remove nd a.dom_snodes /\
157
p.v = (fun id sn -> a.v id (Set.add nd sn)) /\
158
n.v = (fun id sn -> a.v id (Set.remove nd sn)) }

a at the position pos (a cofactor by the cube of the index pos on s bits: get_bit of bddbitv.ml)

    Valid (33ms) (colibri2)
162
val partial
get_pos
(a: t) (pos s: int63) : t
163
requires { 0 <= s /\ numbits a.dom_indexes <= s }
164
requires { 0 <= pos /\ numbits pos <= s }
165
ensures { result.dom_indexes = 0 }
166
ensures { Set.subset result.dom_snodes a.dom_snodes }
167
ensures { forall id sn. result.v id sn <-> a.v pos sn }

Existential (resp. universal) quantification over all the snodes (Cudd.Bdd.exist (resp. forall) with the cube of the snodes of the support, as in to_knownbits)

    Valid (39ms) (colibri2)
172
val partial
exist_snodes
(x: t) : t
173
ensures { result.dom_indexes = x.dom_indexes }
174
ensures { support_snodes result = Set.empty }
175
ensures { forall id sn. result.v id sn <-> exists sn'. x.v id sn' }

Existential quantification over the positions of the window s (Cudd.Bdd.exist with the cube of the indexes 0..s-1)

    Valid (38ms) (colibri2)
179
val partial
exist_window
(x: t) (s: int63) : t
180
requires { 0 <= s /\ numbits x.dom_indexes <= s }
181
ensures { result.dom_indexes = 0 }
182
ensures { Set.subset result.dom_snodes x.dom_snodes }
183
ensures { forall id sn. result.v id sn <-> exists p. 0 <= p /\ numbits p <= s /\ x.v p sn }
184
Valid (38ms) (colibri2)
185
val partial
forall_snodes
(x: t) : t
186
ensures { result.dom_indexes = x.dom_indexes }
187
ensures { support_snodes result = Set.empty }
188
ensures { forall id sn. result.v id sn <-> forall sn'. x.v id sn' }

Substitution of snodes by BDDs

191
predicate
mem_key
(nd: snode) (l: list (snode, t)) =
192
match l with Nil -> false | Cons (nd', _) l' -> nd = nd' \/ mem_key nd l' end
193
194
predicate
distinct_keys
(l: list (snode, t)) =
195
match l with Nil -> true | Cons (nd, _) l' -> not (mem_key nd l') /\ distinct_keys l' end
196
197
function
subst_sn
(l: list (snode, t)) (id: indexes) (sn: snodes) : snodes =
198
match l with
199
| Nil -> sn
200
| Cons (nd, f) l' -> Map.set (subst_sn l' id sn) nd (f.v id sn)
201
end

The simultaneous substitution of the snodes of l (one Var.subst); w bounds the indexes

    Valid (34ms) (colibri2)
205
val partial
compose_snodes
(ghost w: int) (l: list (snode, t)) (x: t) : t
206
requires { distinct_keys l }
207
requires { 0 <= w <= Int63.max_int + 1 /\ numbits x.dom_indexes <= w }
208
requires { forall nd f. Mem.mem (nd, f) l -> numbits f.dom_indexes <= w }
209
ensures { numbits result.dom_indexes <= w }
210
ensures { forall id sn. result.v id sn = x.v id (subst_sn l id sn) }

Top node of the BDD

    Valid (33ms) (colibri2)
213
val
inspect
(a:t) : inspect
214
ensures { match result with
215
| Bool b -> a.v = (fun _ _ -> b) /\ support_snodes a = Set.empty
216
| IteIndex i th el ->
217
Set.subset (support_snodes th) (support_snodes a) /\
218
Set.subset (support_snodes el) (support_snodes a) /\
219
0 <= to_int i /\ Zbit.bittest a.dom_indexes i /\
220
Zbit.subset th.dom_indexes (Zbit.unset a.dom_indexes i) /\
221
Zbit.subset el.dom_indexes (Zbit.unset a.dom_indexes i) /\
222
Set.subset th.dom_snodes a.dom_snodes /\
223
Set.subset el.dom_snodes a.dom_snodes /\
224
0 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\
225
a.v = (fun id sn -> if Zbit.bittest id i then th.v id sn else el.v id sn)
226
| IteSnode nd th el ->
227
Set.mem nd (support_snodes a) /\
228
Set.subset (support_snodes th) (Set.remove nd (support_snodes a)) /\
229
Set.subset (support_snodes el) (Set.remove nd (support_snodes a)) /\
230
Set.mem nd a.dom_snodes /\
231
Zbit.subset th.dom_indexes a.dom_indexes /\
232
Zbit.subset el.dom_indexes a.dom_indexes /\
233
Set.subset th.dom_snodes (Set.remove nd a.dom_snodes) /\
234
Set.subset el.dom_snodes (Set.remove nd a.dom_snodes) /\
235
0 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\
236
a.v = (fun id sn -> if sn nd then th.v id sn else el.v id sn)
237
end }
238
Valid (87ms) (cvc4)
239
val partial
compose_index
(i: int63) (f a: t) : t
240
requires { 0 <= to_int i }
241
ensures { result.dom_indexes = (Zbit.lor f.dom_indexes (Zbit.unset a.dom_indexes i)) }
242
ensures { result.dom_snodes = Set.union f.dom_snodes a.dom_snodes }
243
ensures { result.v = (fun id sn -> a.v (Zbit.change id i (f.v id sn)) sn) }
244
245
246
end