Common — library colibrilib.sbdd — module SBDD
912
module SBDD : SBDD_intf

Implemented

913
use mach.int.Int63
914
use int.Int
915
use list.List
916
use list.Mem
917
use list.Distinct
918
use set.Set
919
use bool.Bool
920
use colibrilib.bdd.CVar
921
use colibrilib.bdd.CCube
922
use colibrilib.bdd.Var
923
use colibrilib.bdd.Key
924
use VBDD
925
use colibrilib.bdd.Node
926
use SNode
927
928
type
t
= VBDD.t
929
type
index
= int63
930
type
indexes
= Set.set index
931
932
function
to_indexes
(x:VBDD.Cube.b) : indexes = (fun i -> x (Index i))
933
934
type
snodes
= Set.set snode
935
936
function
to_snodes
(x:VBDD.Cube.b) : snodes = (fun i -> x (Var i.n i.s i.scal))
937
938
function
to_cube
(x:indexes) (y:snodes) : VBDD.Cube.b = (fun i -> match i with
939
| Index i -> x i
940
| Var nv sv av -> y {n=nv;s=sv;scal=av}
941
end )
942
943
function
dom_indexes
(x:t) : indexes = to_indexes x.VBDD.dom
944
function
dom_snodes
(x:t) : snodes = to_snodes x.VBDD.dom
945
function
v
(x:t): indexes -> snodes -> bool = (fun id sn -> x.VBDD.v (to_cube id sn))
946
Valid (75ms) (colibri2)
947
lemma
mem_to_cube_index
: forall id sn i. Set.mem (Index i) (to_cube id sn) <-> Set.mem i id Valid (69ms) (colibri2)
948
lemma
mem_to_cube_snode
: forall id sn nd. Set.mem (Var nd.n nd.s nd.scal) (to_cube id sn) <-> Set.mem nd sn
949
950
lemma
to_cube_to_indexes
: Valid (89ms) (colibri2)
951
forall c. to_cube (to_indexes c) (to_snodes c) = c
952
953
lemma
to_indexes_to_cube
: Valid (77ms) (colibri2)
954
forall id sn. to_indexes (to_cube id sn) = id
955
lemma
to_snodes_to_cube
: Valid (85ms) (colibri2)
956
forall id sn. to_snodes (to_cube id sn) = sn
957
Valid (290ms) (colibri2)
958
let lemma
support_v
(x:t) (id1 id2:indexes) (sn1 sn2:snodes) : unit
959
requires { forall i. Set.mem i x.dom_indexes -> id1 i = id2 i }
960
requires { forall s. Set.mem s x.dom_snodes -> sn1 s = sn2 s }
961
ensures { x.v id1 sn1 = x.v id2 sn2 }
962
=
963
VBDD.support_v x (to_cube id1 sn1) (to_cube id2 sn2)
964
Valid (113ms) (colibri2)
965
let lemma
subset_indexes_of_subset
(c d: VBDD.Cube.b) : unit
966
requires { Set.subset c d }
967
ensures { Set.subset (to_indexes c) (to_indexes d) }
968
=
969
assert { forall i. Set.mem (Index i) c -> Set.mem (Index i) d }
970
Valid (77ms) (colibri2) (cvc4) (split_vc) (depth 1)
971
let lemma
subset_snodes_of_subset
(c d: VBDD.Cube.b) : unit
972
requires { Set.subset c d }
973
ensures { Set.subset (to_snodes c) (to_snodes d) }
974
=
975
assert { forall v. c (Var v.n v.s v.scal) -> d (Var v.n v.s v.scal) }
976
Valid (4.3s) (colibri2 3) (cvc4 3) (split_vc 2) (depth 2)
977
let
dand
(x y: t) : t
978
ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }
979
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
980
ensures { result.v = (fun id sn -> andb (x.v id sn) (y.v id sn)) } =
981
let r = VBDD.dand x y in
982
assert { forall i. Set.mem i (dom_indexes r) <-> Set.mem i (Set.union x.dom_indexes y.dom_indexes) };
983
assert { forall nd. Set.mem nd (dom_snodes r) <-> Set.mem nd (Set.union x.dom_snodes y.dom_snodes) };
984
assert { forall id sn. v r id sn = andb (v x id sn) (v y id sn) };
985
r
986
Valid (951ms) (colibri2 3) (cvc4 3) (split_vc) (depth 1)
987
let
dor
(x y: t) : t
988
ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }
989
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
990
ensures { result.v = (fun id sn -> orb (x.v id sn) (y.v id sn)) } =
991
let r = VBDD.dor x y in
992
assert { forall i. Set.mem i (dom_indexes r) <-> Set.mem i (Set.union x.dom_indexes y.dom_indexes) };
993
assert { forall nd. Set.mem nd (dom_snodes r) <-> Set.mem nd (Set.union x.dom_snodes y.dom_snodes) };
994
assert { forall id sn. v r id sn = orb (v x id sn) (v y id sn) };
995
r
996
Valid (473ms) (cvc4)
997
let
dxor
(x y: t) : t
998
ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }
999
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
1000
ensures { result.v = (fun id sn -> xorb (x.v id sn) (y.v id sn)) } =
1001
VBDD.dxor x y
1002
Valid (70ms) (cvc4)
1003
let
tfalse
() : t
1004
ensures { result.dom_indexes = Set.empty }
1005
ensures { result.dom_snodes = Set.empty }
1006
ensures { result.v = (fun _ _ -> false) } =
1007
VBDD.tfalse ()
1008
Valid (346ms) (cvc4)
1009
let
ttrue
() : t
1010
ensures { result.dom_indexes = Set.empty }
1011
ensures { result.dom_snodes = Set.empty }
1012
ensures { result.v = (fun _ _ -> true) } =
1013
VBDD.ttrue ()
1014
Valid (145ms) (cvc4)
1015
let
dnot
(a: t) : t
1016
ensures { result.dom_indexes = a.dom_indexes }
1017
ensures { result.dom_snodes = a.dom_snodes }
1018
ensures { result.v = (fun id sn -> notb (a.v id sn)) } =
1019
VBDD.dnot a
1020
Valid (1.2s) (colibri2)
1021
let
is_equal
(x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)
1022
ensures { result = (forall id sn. x.v id sn = y.v id sn) }
1023
ensures { not result ->
1024
((Set.subset wid (Set.union x.dom_indexes y.dom_indexes)) /\
1025
(Set.subset wsn (Set.union x.dom_snodes y.dom_snodes)) /\
1026
x.v wid wsn <> y.v wid wsn) } =
1027
let (r, ghost c) = VBDD.is_equal x y in
1028
if r then (r, Set.empty, Set.empty) else
1029
begin
1030
subset_indexes_of_subset c (Set.union x.VBDD.dom y.VBDD.dom);
1031
subset_snodes_of_subset c (Set.union x.VBDD.dom y.VBDD.dom);
1032
let ghost id = to_indexes c in
1033
let ghost sn = to_snodes c in
1034
(r, id, sn)
1035
end
1036
Valid (1.2s) (colibri2)
1037
let
is_inter_empty
(x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)
1038
ensures { result = (forall id sn. not (x.v id sn /\ y.v id sn)) }
1039
ensures { not result ->
1040
(Set.subset wid (Set.union x.dom_indexes y.dom_indexes)) /\
1041
(Set.subset wsn (Set.union x.dom_snodes y.dom_snodes)) /\
1042
(x.v wid wsn /\ y.v wid wsn) } =
1043
let (r, ghost c) = VBDD.is_inter_empty x y in
1044
if r then (r, Set.empty, Set.empty) else
1045
begin
1046
subset_indexes_of_subset c (Set.union x.VBDD.dom y.VBDD.dom);
1047
subset_snodes_of_subset c (Set.union x.VBDD.dom y.VBDD.dom);
1048
let ghost id = to_indexes c in
1049
let ghost sn = to_snodes c in
1050
(r, id, sn)
1051
end
1052
Valid (483ms) (colibri2)
1053
let partial
bdd_of_index
(i: index) : t
1054
ensures { result.dom_indexes = Set.singleton i }
1055
ensures { result.dom_snodes = Set.empty }
1056
ensures { result.v = (fun id _ -> id i) } =
1057
VBDD.bdd_of_var (Index i)
1058
Valid (573ms) (colibri2)
1059
let partial
bdd_of_snode
(v: snode) : t
1060
ensures { result.dom_indexes = Set.empty }
1061
ensures { result.dom_snodes = Set.singleton v }
1062
ensures { result.v = (fun _ sn -> sn v) } =
1063
VBDD.bdd_of_var (Var v.n v.s v.scal)
1064
1065
lemma
to_cube_singleton_index
: Valid (437ms) (colibri2)
1066
forall id: indexes, sn: snodes, i: index.
1067
to_cube id sn = Set.singleton (Index i) <->
1068
id = Set.singleton i /\ sn = Set.empty
1069
1070
lemma
to_cube_singleton_snode
: Valid (507ms) (colibri2)
1071
forall id: indexes, sn: snodes, v: snode.
1072
to_cube id sn = Set.singleton (Var v.n v.s v.scal) <->
1073
id = Set.empty /\ sn = Set.singleton v
1074
Valid (831ms) (cvc4)
1075
let partial
bdd_not_index
(i: index) : t
1076
ensures { result.dom_indexes = Set.singleton i }
1077
ensures { result.dom_snodes = Set.empty }
1078
ensures { result.v = (fun id _ -> not (id i)) } =
1079
VBDD.bdd_not (Index i)
1080
Valid (776ms) (cvc4)
1081
let partial
bdd_not_snode
(v: snode) : t
1082
ensures { result.dom_indexes = Set.empty }
1083
ensures { result.dom_snodes = Set.singleton v }
1084
ensures { result.v = (fun _ sn -> not (sn v)) } =
1085
VBDD.bdd_not (Var v.n v.s v.scal)
1086
1087
lemma
to_indexes_add_index
: Valid (54ms) (cvc4)
1088
forall x: VBDD.Cube.b, i: index.
1089
to_indexes (Set.add (Index i) x) = Set.add i (to_indexes x)
1090
lemma
to_snodes_add_index
: Valid (76ms) (colibri2)
1091
forall x: VBDD.Cube.b, i: index.
1092
to_snodes (Set.add (Index i) x) = to_snodes x
1093
lemma
to_indexes_add_snode
: Valid (74ms) (colibri2)
1094
forall x: VBDD.Cube.b, v: snode.
1095
to_indexes (Set.add (Var v.n v.s v.scal) x) = to_indexes x
1096
lemma
to_snodes_add_snode
: Valid (318ms) (cvc4)
1097
forall x: VBDD.Cube.b, v: snode.
1098
to_snodes (Set.add (Var v.n v.s v.scal) x) = Set.add v (to_snodes x)
1099
1100
lemma
to_indexes_union
: Valid (276ms) (cvc4)
1101
forall x y: VBDD.Cube.b.
1102
to_indexes (Set.union x y) = Set.union (to_indexes x) (to_indexes y)
1103
lemma
to_snodes_union
: Valid (190ms) (cvc4)
1104
forall x y: VBDD.Cube.b.
1105
to_snodes (Set.union x y) = Set.union (to_snodes x) (to_snodes y)
1106
Valid (399ms) (cvc4)
1107
let partial
ite_index
(i: index) (aa bb: t) : t
1108
ensures { result.dom_indexes = Set.add i (Set.union aa.dom_indexes bb.dom_indexes) }
1109
ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }
1110
ensures { result.v = (fun id sn -> if id i then aa.v id sn else bb.v id sn) } =
1111
let r = VBDD.ite (Index i) aa bb in
1112
let lemma pt (id: indexes) (sn: snodes) : unit
1113
ensures { r.v id sn = if id i then aa.v id sn else bb.v id sn }
1114
=
1115
assert { r.v id sn = r.VBDD.v (to_cube id sn) };
1116
mem_to_cube_index id sn i
1117
in
1118
r
1119
Valid (109ms) (colibri2)
1120
let ghost
ite_index_g
(i: index) (aa bb: t) : t
1121
requires { 0 <= i < 3 }
1122
ensures { result.dom_indexes = Set.add i (Set.union aa.dom_indexes bb.dom_indexes) }
1123
ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }
1124
ensures { result.v = (fun id sn -> if id i then aa.v id sn else bb.v id sn) } =
1125
let r = VBDD.ite_g (Index i) aa bb in
1126
let lemma pt (id: indexes) (sn: snodes) : unit
1127
ensures { r.v id sn = if id i then aa.v id sn else bb.v id sn }
1128
=
1129
assert { r.v id sn = r.VBDD.v (to_cube id sn) };
1130
mem_to_cube_index id sn i
1131
in
1132
r
1133
Valid (409ms) (cvc4)
1134
let partial
ite_snode
(v: snode) (aa bb: t) : t
1135
ensures { result.dom_indexes = Set.union aa.dom_indexes bb.dom_indexes }
1136
ensures { result.dom_snodes = Set.add v (Set.union aa.dom_snodes bb.dom_snodes) }
1137
ensures { result.v = (fun id sn -> if sn v then aa.v id sn else bb.v id sn) } =
1138
let r = VBDD.ite (Var v.n v.s v.scal) aa bb in
1139
let lemma pt (id: indexes) (sn: snodes) : unit
1140
ensures { r.v id sn = if sn v then aa.v id sn else bb.v id sn }
1141
=
1142
assert { r.v id sn = r.VBDD.v (to_cube id sn) };
1143
mem_to_cube_snode id sn v
1144
in
1145
r
1146
1147
lemma
to_indexes_remove_index
: Valid (62ms) (cvc4)
1148
forall x: VBDD.Cube.b, i: index.
1149
to_indexes (Set.remove (Index i) x) = Set.remove i (to_indexes x)
1150
lemma
to_snodes_remove_index
: Valid (79ms) (colibri2)
1151
forall x: VBDD.Cube.b, i: index.
1152
to_snodes (Set.remove (Index i) x) = to_snodes x
1153
lemma
to_indexes_remove_snode
: Valid (78ms) (colibri2)
1154
forall x: VBDD.Cube.b, v: snode.
1155
to_indexes (Set.remove (Var v.n v.s v.scal) x) = to_indexes x
1156
lemma
to_snodes_remove_snode
: Valid (364ms) (cvc4)
1157
forall x: VBDD.Cube.b, v: snode.
1158
to_snodes (Set.remove (Var v.n v.s v.scal) x) = Set.remove v (to_snodes x)
1159
1160
lemma
to_cube_add_index
: Valid (90ms) (colibri2)
1161
forall id: indexes, sn: snodes, i: index.
1162
to_cube (Set.add i id) sn = Set.add (Index i) (to_cube id sn)
1163
lemma
to_cube_remove_index
: Valid (84ms) (colibri2)
1164
forall id: indexes, sn: snodes, i: index.
1165
to_cube (Set.remove i id) sn = Set.remove (Index i) (to_cube id sn)
1166
lemma
to_cube_add_snode
: Valid (88ms) (colibri2)
1167
forall id: indexes, sn: snodes, v: snode.
1168
to_cube id (Set.add v sn) = Set.add (Var v.n v.s v.scal) (to_cube id sn)
1169
lemma
to_cube_remove_snode
: Valid (91ms) (colibri2)
1170
forall id: indexes, sn: snodes, v: snode.
1171
to_cube id (Set.remove v sn) = Set.remove (Var v.n v.s v.scal) (to_cube id sn)
1172
Valid (1.1s) (colibri2)
1173
let partial
cofactors_index
(i: index) (a: t) : (t, t)
1174
returns { (p, n) ->
1175
p.dom_indexes = Set.remove i a.dom_indexes /\
1176
n.dom_indexes = Set.remove i a.dom_indexes /\
1177
p.dom_snodes = a.dom_snodes /\
1178
n.dom_snodes = a.dom_snodes /\
1179
p.v = (fun id sn -> a.v (Set.add i id) sn) /\
1180
n.v = (fun id sn -> a.v (Set.remove i id) sn) } =
1181
let (p, n) = VBDD.cofactors (Index i) a in
1182
(p, n)
1183
Valid (224ms) (colibri2 6) (split_vc 2) (depth 2)
1184
let partial
cofactors_snode
(v: snode) (a: t) : (t, t)
1185
returns { (p, n) ->
1186
p.dom_indexes = a.dom_indexes /\
1187
n.dom_indexes = a.dom_indexes /\
1188
p.dom_snodes = Set.remove v a.dom_snodes /\
1189
n.dom_snodes = Set.remove v a.dom_snodes /\
1190
p.v = (fun id sn -> a.v id (Set.add v sn)) /\
1191
n.v = (fun id sn -> a.v id (Set.remove v sn)) } =
1192
let (p, n) = VBDD.cofactors (Var v.n v.s v.scal) a in
1193
(p, n)
1194
1195
function
nb_nodes
(a:t) : int = VBDD.nb_nodes a
1196
1197
function
support_indexes
(a:t) : indexes = to_indexes (VBDD.support a)
1198
function
support_snodes
(a:t) : snodes = to_snodes (VBDD.support a)
1199
Valid (91ms) (colibri2)
1200
lemma
support_dom
: forall x.
1201
Set.subset (support_indexes x) x.dom_indexes /\ Set.subset (support_snodes x) x.dom_snodes
1202
Valid (695ms) (colibri2) (cvc4) (split_vc) (depth 1)
1203
let lemma
support_exact
(x:t) (id1 id2:indexes) (sn1 sn2:snodes) : unit
1204
requires { forall i. Set.mem i (support_indexes x) -> id1 i = id2 i }
1205
requires { forall s. Set.mem s (support_snodes x) -> sn1 s = sn2 s }
1206
ensures { x.v id1 sn1 = x.v id2 sn2 }
1207
=
1208
VBDD.support_exact x (to_cube id1 sn1) (to_cube id2 sn2)
1209
Valid (98ms) (colibri2 5) (split_vc) (depth 1)
1210
let lemma
support_snodes_dep
(x:t) (nd: snode) : unit
1211
requires { Set.mem nd (support_snodes x) }
1212
ensures { exists id sn. x.v id (Set.add nd sn) <> x.v id (Set.remove nd sn) }
1213
=
1214
VBDD.support_dep x (Var nd.n nd.s nd.scal);
1215
let ghost c = any VBDD.Cube.b
1216
ensures { x.VBDD.v (Set.add (Var nd.n nd.s nd.scal) result) <> x.VBDD.v (Set.remove (Var nd.n nd.s nd.scal) result) } in
1217
assert { to_cube (to_indexes c) (to_snodes c) = c };
1218
assert { x.v (to_indexes c) (Set.add nd (to_snodes c)) <> x.v (to_indexes c) (Set.remove nd (to_snodes c)) }
1219
1220
predicate
is_support
(cb:t) = BDD.is_support cb.b
1221
Valid (139ms) (colibri2)
1222
let
cube_true
() : t
1223
ensures { result.dom_indexes = Set.empty /\ result.dom_snodes = Set.empty }
1224
ensures { support_indexes result = Set.empty /\ support_snodes result = Set.empty }
1225
ensures { is_support result }
1226
= VBDD.ttrue ()
1227
Valid (160ms) (colibri2)
1228
let partial
cube_snode
(nd: snode) : t
1229
ensures { result.dom_indexes = Set.empty /\ result.dom_snodes = Set.singleton nd }
1230
ensures { support_indexes result = Set.empty /\ support_snodes result = Set.singleton nd }
1231
ensures { is_support result }
1232
= VBDD.bdd_of_var (Var nd.n nd.s nd.scal)
1233
Valid (132ms) (colibri2)
1234
let partial
cube_index
(i: index) : t
1235
ensures { result.dom_indexes = Set.singleton i /\ result.dom_snodes = Set.empty }
1236
ensures { support_indexes result = Set.singleton i /\ support_snodes result = Set.empty }
1237
ensures { is_support result }
1238
= VBDD.bdd_of_var (Index i)
1239
Valid (95ms) (colibri2)
1240
let
support_union
(x y: t) : t
1241
requires { is_support x /\ is_support y }
1242
ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }
1243
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
1244
ensures { support_indexes result = Set.union (support_indexes x) (support_indexes y) }
1245
ensures { support_snodes result = Set.union (support_snodes x) (support_snodes y) }
1246
ensures { is_support result }
1247
= VBDD.support_union x y
1248
1249
Valid (108ms) (colibri2)
1250
let
vars
(a:t) : list Key.t
1251
ensures { forall i. Mem.mem (Key.Index i) result <-> Set.mem i (support_indexes a) }
1252
ensures { forall n s ab. Mem.mem (Key.Var n s ab) result <-> Set.mem { n = n; s = s; scal = ab } (support_snodes a) }
1253
ensures { Distinct.distinct result }
1254
= VBDD.vars a
1255
1256
type
inspect
=
Bool
bool |
IteIndex
index t t |
IteSnode
snode t t
1257
Valid (400ms) (colibri2 40) (cvc4) (split_vc 5) (depth 3)
1258
let
inspect
(a:t) : inspect
1259
ensures { match result with
1260
| Bool b -> a.v = (fun _ _ -> b) /\
1261
support_indexes a = Set.empty /\ support_snodes a = Set.empty
1262
| IteIndex i th el ->
1263
Set.mem i (support_indexes a) /\
1264
Set.subset (support_indexes th) (Set.remove i (support_indexes a)) /\
1265
Set.subset (support_indexes el) (Set.remove i (support_indexes a)) /\
1266
Set.subset (support_snodes th) (support_snodes a) /\
1267
Set.subset (support_snodes el) (support_snodes a) /\
1268
Set.mem i a.dom_indexes /\
1269
Set.subset th.dom_indexes (Set.remove i a.dom_indexes) /\
1270
Set.subset el.dom_indexes (Set.remove i a.dom_indexes) /\
1271
Set.subset th.dom_snodes a.dom_snodes /\
1272
Set.subset el.dom_snodes a.dom_snodes /\
1273
0 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\
1274
a.v = (fun id sn -> if Set.mem i id then th.v id sn else el.v id sn)
1275
| IteSnode nd th el ->
1276
Set.mem nd (support_snodes a) /\
1277
Set.subset (support_indexes th) (support_indexes a) /\
1278
Set.subset (support_indexes el) (support_indexes a) /\
1279
Set.subset (support_snodes th) (Set.remove nd (support_snodes a)) /\
1280
Set.subset (support_snodes el) (Set.remove nd (support_snodes a)) /\
1281
Set.mem nd a.dom_snodes /\
1282
Set.subset th.dom_indexes a.dom_indexes /\
1283
Set.subset el.dom_indexes a.dom_indexes /\
1284
Set.subset th.dom_snodes (Set.remove nd a.dom_snodes) /\
1285
Set.subset el.dom_snodes (Set.remove nd a.dom_snodes) /\
1286
0 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\
1287
a.v = (fun id sn -> if Set.mem nd sn then th.v id sn else el.v id sn)
1288
end }
1289
=
1290
match VBDD.inspect a with
1291
| VBDD.Bool b -> Bool b
1292
| VBDD.Ite (Index i) th el ->
1293
assert { forall id sn. Set.mem (Index i) (to_cube id sn) <-> Set.mem i id };
1294
IteIndex i th el
1295
| VBDD.Ite (Var n s a) th el ->
1296
let nd = { n = n; s = s; scal = a } in
1297
assert { forall id sn. Set.mem (Var n s a) (to_cube id sn) <-> Set.mem nd sn };
1298
IteSnode nd th el
1299
end
1300
1301
lemma
to_indexes_diff
: Valid (1.9s) (cvc4)
1302
forall x y: VBDD.Cube.b.
1303
to_indexes (Set.diff x y) = Set.diff (to_indexes x) (to_indexes y)
1304
lemma
to_snodes_diff
: Valid (1.5s) (cvc4)
1305
forall x y: VBDD.Cube.b.
1306
to_snodes (Set.diff x y) = Set.diff (to_snodes x) (to_snodes y)
1307
1308
function
update_id
(id: indexes) (s: indexes) (id': indexes) : indexes =
1309
(fun i -> if s i then id' i else id i)
1310
function
update_sn
(sn: snodes) (s: snodes) (sn': snodes) : snodes =
1311
(fun i -> if s i then sn' i else sn i)
1312
1313
lemma
to_cube_update
: Valid (125ms) (colibri2)
1314
forall id sn s_id s_sn id' sn'.
1315
VBDD.update (to_cube id sn) (to_cube s_id s_sn) (to_cube id' sn')
1316
= to_cube (update_id id s_id id') (update_sn sn s_sn sn')
1317
1318
lemma
update_roundtrip
: Valid (97ms) (colibri2)
1319
forall x: t, s: t, id: indexes, sn: snodes, c': VBDD.Cube.b.
1320
x.v (update_id id (support_indexes s) (to_indexes c')) (update_sn sn (support_snodes s) (to_snodes c'))
1321
= x.VBDD.v (VBDD.update (to_cube id sn) (VBDD.support s) c')
1322
Valid (469ms) (colibri2 5) (cvc4 2) (split_vc) (depth 1)
1323
let
dexist
(s x: t) : t
1324
requires { is_support s }
1325
ensures { result.dom_indexes = Set.diff x.dom_indexes (support_indexes s) }
1326
ensures { result.dom_snodes = Set.diff x.dom_snodes (support_snodes s) }
1327
ensures { result.v = (fun id sn ->
1328
exists id' sn'. x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn')) } =
1329
let r = VBDD.dexist s x in
1330
assert { forall id sn id' sn'.
1331
x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn')
1332
= x.VBDD.v (VBDD.update (to_cube id sn) (VBDD.support s) (to_cube id' sn')) };
1333
assert { forall id sn.
1334
(exists id' sn'. x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn'))
1335
= (exists c'. x.VBDD.v (VBDD.update (to_cube id sn) (VBDD.support s) c')) };
1336
assert { forall id sn. r.v id sn =
1337
(exists id' sn'. x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn')) };
1338
r
1339
Valid (172ms) (colibri2 6) (cvc4) (split_vc) (depth 1)
1340
let
dforall
(s x: t) : t
1341
requires { is_support s }
1342
ensures { result.dom_indexes = Set.diff x.dom_indexes (support_indexes s) }
1343
ensures { result.dom_snodes = Set.diff x.dom_snodes (support_snodes s) }
1344
ensures { result.v = (fun id sn ->
1345
forall id' sn'. x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn')) } =
1346
let r = VBDD.dforall s x in
1347
assert { forall id sn id' sn'.
1348
x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn')
1349
= x.VBDD.v (VBDD.update (to_cube id sn) (VBDD.support s) (to_cube id' sn')) };
1350
assert { forall id sn.
1351
(forall id' sn'. x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn'))
1352
= (forall c'. x.VBDD.v (VBDD.update (to_cube id sn) (VBDD.support s) c')) };
1353
assert { forall id sn.
1354
r.v id sn = (forall id' sn'. x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn')) };
1355
r
1356
1357
lemma
to_cube_map_set_index
: Valid (100ms) (colibri2)
1358
forall id: indexes, sn: snodes, i: index, b: bool.
1359
to_cube (Map.set id i b) sn = Map.set (to_cube id sn) (Index i) b
1360
lemma
to_cube_map_set_snode
: Valid (97ms) (colibri2)
1361
forall id: indexes, sn: snodes, v: snode, b: bool.
1362
to_cube id (Map.set sn v b) = Map.set (to_cube id sn) (Var v.n v.s v.scal) b
1363
Valid (407ms) (colibri2 4) (cvc4) (split_vc) (depth 1)
1364
let partial
compose_index
(i: index) (f a: t) : t
1365
ensures { result.dom_indexes = Set.union f.dom_indexes (Set.remove i a.dom_indexes) }
1366
ensures { result.dom_snodes = Set.union f.dom_snodes a.dom_snodes }
1367
ensures { result.v = (fun id sn -> a.v (Map.set id i (f.v id sn)) sn) } =
1368
let r = VBDD.compose (Index i) f a in
1369
assert { forall id sn.
1370
to_cube (Map.set id i (f.v id sn)) sn = Map.set (to_cube id sn) (Index i) (f.v id sn) };
1371
assert { forall id sn. r.v id sn = a.v (Map.set id i (f.v id sn)) sn };
1372
r
1373
Valid (388ms) (colibri2 4) (cvc4) (split_vc) (depth 1)
1374
let partial
compose_snode
(v: snode) (f a: t) : t
1375
ensures { result.dom_indexes = Set.union f.dom_indexes a.dom_indexes }
1376
ensures { result.dom_snodes = Set.union f.dom_snodes (Set.remove v a.dom_snodes) }
1377
ensures { result.v = (fun id sn -> a.v id (Map.set sn v (f.v id sn))) } =
1378
let r = VBDD.compose (Var v.n v.s v.scal) f a in
1379
assert { forall id sn.
1380
to_cube id (Map.set sn v (f.v id sn)) = Map.set (to_cube id sn) (Var v.n v.s v.scal) (f.v id sn) };
1381
assert { forall id sn. r.v id sn = a.v id (Map.set sn v (f.v id sn)) };
1382
r
1383
1384
function
get_cube_indexes
(cb: t) : indexes = to_indexes (VBDD.get_cube cb)
1385
function
get_cube_snodes
(cb: t) : snodes = to_snodes (VBDD.get_cube cb)
1386
1387
lemma
to_cube_union
: Valid (290ms) (cvc4)
1388
forall a1: indexes, b1: indexes, a2: snodes, b2: snodes.
1389
to_cube (Set.union a1 b1) (Set.union a2 b2) = Set.union (to_cube a1 a2) (to_cube b1 b2)
1390
lemma
to_cube_diff
: Valid (331ms) (cvc4)
1391
forall a1: indexes, b1: indexes, a2: snodes, b2: snodes.
1392
to_cube (Set.diff a1 b1) (Set.diff a2 b2) = Set.diff (to_cube a1 a2) (to_cube b1 b2)
1393
lemma
to_cube_get_cube
: Valid (58ms) (colibri2)
1394
forall cb: t. to_cube (get_cube_indexes cb) (get_cube_snodes cb) = VBDD.get_cube cb

A cube on the variables of the keys

1397
predicate
is_cube
(cb:t) = BDD.is_cube cb.b /\
1398
forall y. Set.mem y (BDD.get_cube cb.b) -> Set.mem (key_of_var y) keys
1399
1400
predicate
good_cube
(cb: t) =
1401
is_cube cb /\ Set.subset (get_cube_indexes cb) (support_indexes cb) /\
1402
Set.subset (get_cube_snodes cb) (support_snodes cb)
1403
Valid (59ms) (colibri2)
1404
lemma
to_indexes_empty
: to_indexes (Set.empty: VBDD.Cube.b) = Set.empty Valid (70ms) (colibri2)
1405
lemma
to_snodes_empty
: to_snodes (Set.empty: VBDD.Cube.b) = Set.empty
1406
Valid (72ms) (cvc4)
1407
let lemma
cube_empty_good
(x: t) : unit
1408
requires { is_support x /\ support_indexes x = Set.empty /\ support_snodes x = Set.empty }
1409
ensures { good_cube x /\ get_cube_indexes x = Set.empty /\ get_cube_snodes x = Set.empty }
1410
=
1411
assert { VBDD.get_cube x = VBDD.support x };
1412
assert { get_cube_indexes x = support_indexes x /\ get_cube_snodes x = support_snodes x }
1413
Valid (388ms) (colibri2 11) (cvc4) (split_vc) (depth 1)
1414
let partial
cube_lit
(i: index) (b: bool) : t
1415
ensures { result.dom_indexes = Set.singleton i /\ result.dom_snodes = Set.empty }
1416
ensures { support_indexes result = Set.singleton i /\ support_snodes result = Set.empty }
1417
ensures { good_cube result }
1418
ensures { get_cube_indexes result = (if b then Set.singleton i else Set.empty) }
1419
ensures { get_cube_snodes result = Set.empty }
1420
=
1421
let r = if b then VBDD.bdd_of_var (Index i) else VBDD.bdd_not (Index i) in
1422
assert { VBDD.get_cube r = if b then Set.singleton (Index i) else Set.empty };
1423
r
1424
Valid (1.9s) (colibri2 25) (cvc4 2) (split_vc 3) (depth 2)
1425
let
cube_and
(x y: t) : t
1426
requires { good_cube x /\ good_cube y }
1427
requires { Set.inter (support_indexes x) (support_indexes y) = Set.empty }
1428
requires { Set.inter (support_snodes x) (support_snodes y) = Set.empty }
1429
ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }
1430
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
1431
ensures { good_cube result }
1432
ensures { support_indexes result = Set.union (support_indexes x) (support_indexes y) }
1433
ensures { support_snodes result = Set.union (support_snodes x) (support_snodes y) }
1434
ensures { get_cube_indexes result = Set.union (get_cube_indexes x) (get_cube_indexes y) }
1435
ensures { get_cube_snodes result = Set.union (get_cube_snodes x) (get_cube_snodes y) }
1436
=
1437
assert { forall k. Set.mem k (VBDD.support x) -> Set.mem k (VBDD.support y) ->
1438
match k with
1439
| Index i -> Set.mem i (support_indexes x) /\ Set.mem i (support_indexes y)
1440
| Var n s a -> Set.mem { n = n; s = s; scal = a } (support_snodes x) /\ Set.mem { n = n; s = s; scal = a } (support_snodes y)
1441
end };
1442
assert { forall k. Set.mem k (VBDD.support x) -> Set.mem k (VBDD.support y) -> false
1443
by match k with
1444
| Index i -> Set.mem i (Set.inter (support_indexes x) (support_indexes y))
1445
| Var n s a -> Set.mem { n = n; s = s; scal = a } (Set.inter (support_snodes x) (support_snodes y))
1446
end };
1447
VBDD.of_to_dom x; VBDD.of_to_dom y;
1448
assert { forall v. Set.mem v (BDD.support x.VBDD.b) -> Set.mem (key_of_var v) (VBDD.support x)
1449
by Set.mem v x.VBDD.b.BDD.dom /\ Set.mem (key_of_var v) keys /\ var_of_key (key_of_var v) = v };
1450
assert { forall v. Set.mem v (BDD.support y.VBDD.b) -> Set.mem (key_of_var v) (VBDD.support y)
1451
by Set.mem v y.VBDD.b.BDD.dom /\ Set.mem (key_of_var v) keys /\ var_of_key (key_of_var v) = v };
1452
assert { forall v. Set.mem v (BDD.support x.VBDD.b) -> Set.mem v (BDD.support y.VBDD.b) -> false
1453
by Set.mem (key_of_var v) (VBDD.support x) /\ Set.mem (key_of_var v) (VBDD.support y) };
1454
assert { Set.inter (BDD.support x.VBDD.b) (BDD.support y.VBDD.b) = Set.empty };
1455
assert { forall v. Set.mem v (BDD.get_cube x.VBDD.b) -> Set.mem (key_of_var v) (VBDD.get_cube x) };
1456
assert { forall v. Set.mem v (BDD.get_cube y.VBDD.b) -> Set.mem (key_of_var v) (VBDD.get_cube y) };
1457
assert { Set.subset (BDD.get_cube x.VBDD.b) (BDD.support x.VBDD.b) };
1458
assert { Set.subset (BDD.get_cube y.VBDD.b) (BDD.support y.VBDD.b) };
1459
let r = VBDD.dand x y in
1460
assert { support_indexes r = Set.union (support_indexes x) (support_indexes y) };
1461
assert { support_snodes r = Set.union (support_snodes x) (support_snodes y) };
1462
assert { get_cube_indexes r = Set.union (get_cube_indexes x) (get_cube_indexes y) };
1463
assert { get_cube_snodes r = Set.union (get_cube_snodes x) (get_cube_snodes y) };
1464
assert { is_cube r };
1465
r
1466
Valid (161ms) (colibri2 5) (cvc4) (split_vc) (depth 1)
1467
let
cofactor
(a cb: t) : t
1468
requires { is_cube cb }
1469
ensures { result.dom_indexes = Set.diff a.dom_indexes (support_indexes cb) }
1470
ensures { result.dom_snodes = Set.diff a.dom_snodes (support_snodes cb) }
1471
ensures { result.v = (fun id sn ->
1472
a.v (Set.union (Set.diff id (support_indexes cb)) (get_cube_indexes cb))
1473
(Set.union (Set.diff sn (support_snodes cb)) (get_cube_snodes cb))) } =
1474
let r = VBDD.cofactor a cb in
1475
assert { forall id sn.
1476
Set.union (Set.diff (to_cube id sn) (VBDD.support cb)) (VBDD.get_cube cb)
1477
= to_cube (Set.union (Set.diff id (support_indexes cb)) (get_cube_indexes cb))
1478
(Set.union (Set.diff sn (support_snodes cb)) (get_cube_snodes cb)) };
1479
assert { forall id sn. r.v id sn =
1480
a.v (Set.union (Set.diff id (support_indexes cb)) (get_cube_indexes cb))
1481
(Set.union (Set.diff sn (support_snodes cb)) (get_cube_snodes cb)) };
1482
r
1483
1484
scope Vector
1485
type
vector
= VBDD.Vector.vector
1486
1487
function
removed_indexes
(v:vector) : indexes = to_indexes (VBDD.Vector.removed v)
1488
function
removed_snodes
(v:vector) : snodes = to_snodes (VBDD.Vector.removed v)
1489
function
added_indexes
(v:vector) : indexes = to_indexes (VBDD.Vector.added v)
1490
function
added_snodes
(v:vector) : snodes = to_snodes (VBDD.Vector.added v)

A predicate on indexes and snodes as a predicate on cubes

1493
function
lift
(a: indexes -> snodes -> bool) : VBDD.Value.b =
1494
fun c -> a (to_indexes c) (to_snodes c)
1495
1496
function
subst
(v:vector) : (indexes -> snodes -> bool) -> (indexes -> snodes -> bool) =
1497
fun a id sn -> (VBDD.Vector.subst v) (lift a) (to_cube id sn)

a with the index i (resp. the snode sn0) set to b

1500
function
upd_index
(a: indexes -> snodes -> bool) (i: index) (b: bool) : indexes -> snodes -> bool =
1501
fun id sn -> a (Map.set id i b) sn
1502
function
upd_snode
(a: indexes -> snodes -> bool) (sn0: snode) (b: bool) : indexes -> snodes -> bool =
1503
fun id sn -> a id (Map.set sn sn0 b)
1504
Valid (217ms) (colibri2)
1505
let
create
() : vector
1506
ensures { result.removed_indexes = Set.empty }
1507
ensures { result.removed_snodes = Set.empty }
1508
ensures { result.added_indexes = Set.empty }
1509
ensures { result.added_snodes = Set.empty }
1510
ensures { result.subst = (fun a -> a) } =
1511
VBDD.Vector.create ()
1512
Valid (92ms) (colibri2 11) (cvc4) (split_vc) (depth 1)
1513
let partial
add_index
(v: vector) (i: index) (f: t) : vector
1514
requires { not (Set.mem i v.removed_indexes) }
1515
ensures { result.removed_indexes = Set.add i v.removed_indexes }
1516
ensures { result.removed_snodes = v.removed_snodes }
1517
ensures { result.added_indexes = Set.union v.added_indexes f.dom_indexes }
1518
ensures { result.added_snodes = Set.union v.added_snodes f.dom_snodes }
1519
ensures { result.subst = (fun a id sn -> v.subst (upd_index a i (f.v id sn)) id sn) } =
1520
let r = VBDD.Vector.add v (Index i) f in
1521
let lemma subst_add (a: indexes -> snodes -> bool) (id: indexes) (sn: snodes) : unit
1522
ensures { subst r a id sn = subst v (upd_index a i (f.v id sn)) id sn }
1523
=
1524
let ghost b = pure { f.v id sn } in
1525
let lemma pt (c: Cube.b) : unit
1526
ensures { VBDD.Vector.upd (lift a) (Index i) b c = lift (upd_index a i b) c }
1527
= assert { to_indexes (Map.set c (Index i) b) = Map.set (to_indexes c) i b };
1528
assert { to_snodes (Map.set c (Index i) b) = to_snodes c }
1529
in
1530
assert { VBDD.Vector.upd (lift a) (Index i) b = lift (upd_index a i b) };
1531
assert { f.v id sn = f.VBDD.v (to_cube id sn) }
1532
in
1533
r
1534
Valid (101ms) (colibri2 11) (cvc4) (split_vc) (depth 1)
1535
let partial
add_snode
(v: vector) (sn0: snode) (f: t) : vector
1536
requires { not (Set.mem sn0 v.removed_snodes) }
1537
ensures { result.removed_indexes = v.removed_indexes }
1538
ensures { result.removed_snodes = Set.add sn0 v.removed_snodes }
1539
ensures { result.added_indexes = Set.union v.added_indexes f.dom_indexes }
1540
ensures { result.added_snodes = Set.union v.added_snodes f.dom_snodes }
1541
ensures { result.subst = (fun a id sn -> v.subst (upd_snode a sn0 (f.v id sn)) id sn) } =
1542
let r = VBDD.Vector.add v (Var sn0.n sn0.s sn0.scal) f in
1543
let lemma subst_add (a: indexes -> snodes -> bool) (id: indexes) (sn: snodes) : unit
1544
ensures { subst r a id sn = subst v (upd_snode a sn0 (f.v id sn)) id sn }
1545
=
1546
let ghost b = pure { f.v id sn } in
1547
let lemma pt (c: Cube.b) : unit
1548
ensures { VBDD.Vector.upd (lift a) (Var sn0.n sn0.s sn0.scal) b c = lift (upd_snode a sn0 b) c }
1549
= assert { to_indexes (Map.set c (Var sn0.n sn0.s sn0.scal) b) = to_indexes c };
1550
assert { to_snodes (Map.set c (Var sn0.n sn0.s sn0.scal) b) = Map.set (to_snodes c) sn0 b }
1551
in
1552
assert { VBDD.Vector.upd (lift a) (Var sn0.n sn0.s sn0.scal) b = lift (upd_snode a sn0 b) };
1553
assert { f.v id sn = f.VBDD.v (to_cube id sn) }
1554
in
1555
r
1556
Valid (118ms) (cvc4)
1557
let
compose
(v: vector) (a: t) : t
1558
ensures { result.dom_indexes = Set.union v.added_indexes (Set.diff a.dom_indexes v.removed_indexes) }
1559
ensures { result.dom_snodes = Set.union v.added_snodes (Set.diff a.dom_snodes v.removed_snodes) }
1560
ensures { result.v = v.subst a.v } =
1561
let r = VBDD.Vector.compose v a in
1562
let lemma lift_v (c: VBDD.Cube.b) : unit
1563
ensures { lift a.v c = a.VBDD.v c }
1564
= assert { to_cube (to_indexes c) (to_snodes c) = c } in
1565
assert { lift a.v = a.VBDD.v };
1566
let lemma comp_subst (id: indexes) (sn: snodes) : unit
1567
ensures { (subst v (a.v)) id sn = r.v id sn }
1568
= assert { (subst v (a.v)) id sn = (VBDD.Vector.subst v) a.VBDD.v (to_cube id sn) } in
1569
r
1570
end
1571
1572
end