library colibrilib.sbdd — module SBDDmodule SBDD : SBDD_intf912
Implemented
use mach.int.Int63913use int.Int914use list.List915use list.Mem916use list.Distinct917use set.Set918use bool.Bool919use colibrilib.bdd.CVar920use colibrilib.bdd.CCube921use colibrilib.bdd.Var922use colibrilib.bdd.Key923use VBDD924use colibrilib.bdd.Node925use SNode926927type t = VBDD.t928type index = int63929type indexes = Set.set index930931function to_indexes (x:VBDD.Cube.b) : indexes = (fun i -> x (Index i))932933type snodes = Set.set snode934935function to_snodes (x:VBDD.Cube.b) : snodes = (fun i -> x (Var i.n i.s i.scal))936937function to_cube (x:indexes) (y:snodes) : VBDD.Cube.b = (fun i -> match i with938| Index i -> x i939| Var nv sv av -> y {n=nv;s=sv;scal=av}940end )941942function dom_indexes (x:t) : indexes = to_indexes x.VBDD.dom943function dom_snodes (x:t) : snodes = to_snodes x.VBDD.dom944function v (x:t): indexes -> snodes -> bool = (fun id sn -> x.VBDD.v (to_cube id sn))945Valid (75ms) (colibri2)946lemma mem_to_cube_index: forall id sn i. Set.mem (Index i) (to_cube id sn) <-> Set.mem i id Valid (69ms) (colibri2)947lemma mem_to_cube_snode: forall id sn nd. Set.mem (Var nd.n nd.s nd.scal) (to_cube id sn) <-> Set.mem nd sn948949lemma to_cube_to_indexes: Valid (89ms) (colibri2)950forall c. to_cube (to_indexes c) (to_snodes c) = c951952lemma to_indexes_to_cube: Valid (77ms) (colibri2)953forall id sn. to_indexes (to_cube id sn) = id954lemma to_snodes_to_cube: Valid (85ms) (colibri2)955forall id sn. to_snodes (to_cube id sn) = sn956Valid (290ms) (colibri2)957let lemma support_v (x:t) (id1 id2:indexes) (sn1 sn2:snodes) : unit958requires { forall i. Set.mem i x.dom_indexes -> id1 i = id2 i }959requires { forall s. Set.mem s x.dom_snodes -> sn1 s = sn2 s }960ensures { x.v id1 sn1 = x.v id2 sn2 }961=962VBDD.support_v x (to_cube id1 sn1) (to_cube id2 sn2)963Valid (113ms) (colibri2)964let lemma subset_indexes_of_subset (c d: VBDD.Cube.b) : unit965requires { Set.subset c d }966ensures { Set.subset (to_indexes c) (to_indexes d) }967=968assert { forall i. Set.mem (Index i) c -> Set.mem (Index i) d }969Valid (77ms) (colibri2) (cvc4) (split_vc) (depth 1)970let lemma subset_snodes_of_subset (c d: VBDD.Cube.b) : unit971requires { Set.subset c d }972ensures { Set.subset (to_snodes c) (to_snodes d) }973=974assert { forall v. c (Var v.n v.s v.scal) -> d (Var v.n v.s v.scal) }975Valid (4.3s) (colibri2 3) (cvc4 3) (split_vc 2) (depth 2)976let dand (x y: t) : t977ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }978ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }979ensures { result.v = (fun id sn -> andb (x.v id sn) (y.v id sn)) } =980let r = VBDD.dand x y in981assert { forall i. Set.mem i (dom_indexes r) <-> Set.mem i (Set.union x.dom_indexes y.dom_indexes) };982assert { forall nd. Set.mem nd (dom_snodes r) <-> Set.mem nd (Set.union x.dom_snodes y.dom_snodes) };983assert { forall id sn. v r id sn = andb (v x id sn) (v y id sn) };984r985Valid (951ms) (colibri2 3) (cvc4 3) (split_vc) (depth 1)986let dor (x y: t) : t987ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }988ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }989ensures { result.v = (fun id sn -> orb (x.v id sn) (y.v id sn)) } =990let r = VBDD.dor x y in991assert { forall i. Set.mem i (dom_indexes r) <-> Set.mem i (Set.union x.dom_indexes y.dom_indexes) };992assert { forall nd. Set.mem nd (dom_snodes r) <-> Set.mem nd (Set.union x.dom_snodes y.dom_snodes) };993assert { forall id sn. v r id sn = orb (v x id sn) (v y id sn) };994r995Valid (473ms) (cvc4)996let dxor (x y: t) : t997ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }998ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }999ensures { result.v = (fun id sn -> xorb (x.v id sn) (y.v id sn)) } =1000VBDD.dxor x y1001Valid (70ms) (cvc4)1002let tfalse () : t1003ensures { result.dom_indexes = Set.empty }1004ensures { result.dom_snodes = Set.empty }1005ensures { result.v = (fun _ _ -> false) } =1006VBDD.tfalse ()1007Valid (346ms) (cvc4)1008let ttrue () : t1009ensures { result.dom_indexes = Set.empty }1010ensures { result.dom_snodes = Set.empty }1011ensures { result.v = (fun _ _ -> true) } =1012VBDD.ttrue ()1013Valid (145ms) (cvc4)1014let dnot (a: t) : t1015ensures { result.dom_indexes = a.dom_indexes }1016ensures { result.dom_snodes = a.dom_snodes }1017ensures { result.v = (fun id sn -> notb (a.v id sn)) } =1018VBDD.dnot a1019Valid (1.2s) (colibri2)1020let is_equal (x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)1021ensures { result = (forall id sn. x.v id sn = y.v id sn) }1022ensures { not result ->1023((Set.subset wid (Set.union x.dom_indexes y.dom_indexes)) /\1024(Set.subset wsn (Set.union x.dom_snodes y.dom_snodes)) /\1025x.v wid wsn <> y.v wid wsn) } =1026let (r, ghost c) = VBDD.is_equal x y in1027if r then (r, Set.empty, Set.empty) else1028begin1029subset_indexes_of_subset c (Set.union x.VBDD.dom y.VBDD.dom);1030subset_snodes_of_subset c (Set.union x.VBDD.dom y.VBDD.dom);1031let ghost id = to_indexes c in1032let ghost sn = to_snodes c in1033(r, id, sn)1034end1035Valid (1.2s) (colibri2)1036let is_inter_empty (x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)1037ensures { result = (forall id sn. not (x.v id sn /\ y.v id sn)) }1038ensures { not result ->1039(Set.subset wid (Set.union x.dom_indexes y.dom_indexes)) /\1040(Set.subset wsn (Set.union x.dom_snodes y.dom_snodes)) /\1041(x.v wid wsn /\ y.v wid wsn) } =1042let (r, ghost c) = VBDD.is_inter_empty x y in1043if r then (r, Set.empty, Set.empty) else1044begin1045subset_indexes_of_subset c (Set.union x.VBDD.dom y.VBDD.dom);1046subset_snodes_of_subset c (Set.union x.VBDD.dom y.VBDD.dom);1047let ghost id = to_indexes c in1048let ghost sn = to_snodes c in1049(r, id, sn)1050end1051Valid (483ms) (colibri2)1052let partial bdd_of_index (i: index) : t1053ensures { result.dom_indexes = Set.singleton i }1054ensures { result.dom_snodes = Set.empty }1055ensures { result.v = (fun id _ -> id i) } =1056VBDD.bdd_of_var (Index i)1057Valid (573ms) (colibri2)1058let partial bdd_of_snode (v: snode) : t1059ensures { result.dom_indexes = Set.empty }1060ensures { result.dom_snodes = Set.singleton v }1061ensures { result.v = (fun _ sn -> sn v) } =1062VBDD.bdd_of_var (Var v.n v.s v.scal)10631064lemma to_cube_singleton_index: Valid (437ms) (colibri2)1065forall id: indexes, sn: snodes, i: index.1066to_cube id sn = Set.singleton (Index i) <->1067id = Set.singleton i /\ sn = Set.empty10681069lemma to_cube_singleton_snode: Valid (507ms) (colibri2)1070forall id: indexes, sn: snodes, v: snode.1071to_cube id sn = Set.singleton (Var v.n v.s v.scal) <->1072id = Set.empty /\ sn = Set.singleton v1073Valid (831ms) (cvc4)1074let partial bdd_not_index (i: index) : t1075ensures { result.dom_indexes = Set.singleton i }1076ensures { result.dom_snodes = Set.empty }1077ensures { result.v = (fun id _ -> not (id i)) } =1078VBDD.bdd_not (Index i)1079Valid (776ms) (cvc4)1080let partial bdd_not_snode (v: snode) : t1081ensures { result.dom_indexes = Set.empty }1082ensures { result.dom_snodes = Set.singleton v }1083ensures { result.v = (fun _ sn -> not (sn v)) } =1084VBDD.bdd_not (Var v.n v.s v.scal)10851086lemma to_indexes_add_index: Valid (54ms) (cvc4)1087forall x: VBDD.Cube.b, i: index.1088to_indexes (Set.add (Index i) x) = Set.add i (to_indexes x)1089lemma to_snodes_add_index: Valid (76ms) (colibri2)1090forall x: VBDD.Cube.b, i: index.1091to_snodes (Set.add (Index i) x) = to_snodes x1092lemma to_indexes_add_snode: Valid (74ms) (colibri2)1093forall x: VBDD.Cube.b, v: snode.1094to_indexes (Set.add (Var v.n v.s v.scal) x) = to_indexes x1095lemma to_snodes_add_snode: Valid (318ms) (cvc4)1096forall x: VBDD.Cube.b, v: snode.1097to_snodes (Set.add (Var v.n v.s v.scal) x) = Set.add v (to_snodes x)10981099lemma to_indexes_union: Valid (276ms) (cvc4)1100forall x y: VBDD.Cube.b.1101to_indexes (Set.union x y) = Set.union (to_indexes x) (to_indexes y)1102lemma to_snodes_union: Valid (190ms) (cvc4)1103forall x y: VBDD.Cube.b.1104to_snodes (Set.union x y) = Set.union (to_snodes x) (to_snodes y)1105Valid (399ms) (cvc4)1106let partial ite_index (i: index) (aa bb: t) : t1107ensures { result.dom_indexes = Set.add i (Set.union aa.dom_indexes bb.dom_indexes) }1108ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }1109ensures { result.v = (fun id sn -> if id i then aa.v id sn else bb.v id sn) } =1110let r = VBDD.ite (Index i) aa bb in1111let lemma pt (id: indexes) (sn: snodes) : unit1112ensures { r.v id sn = if id i then aa.v id sn else bb.v id sn }1113=1114assert { r.v id sn = r.VBDD.v (to_cube id sn) };1115mem_to_cube_index id sn i1116in1117r1118Valid (109ms) (colibri2)1119let ghost ite_index_g (i: index) (aa bb: t) : t1120requires { 0 <= i < 3 }1121ensures { result.dom_indexes = Set.add i (Set.union aa.dom_indexes bb.dom_indexes) }1122ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }1123ensures { result.v = (fun id sn -> if id i then aa.v id sn else bb.v id sn) } =1124let r = VBDD.ite_g (Index i) aa bb in1125let lemma pt (id: indexes) (sn: snodes) : unit1126ensures { r.v id sn = if id i then aa.v id sn else bb.v id sn }1127=1128assert { r.v id sn = r.VBDD.v (to_cube id sn) };1129mem_to_cube_index id sn i1130in1131r1132Valid (409ms) (cvc4)1133let partial ite_snode (v: snode) (aa bb: t) : t1134ensures { result.dom_indexes = Set.union aa.dom_indexes bb.dom_indexes }1135ensures { result.dom_snodes = Set.add v (Set.union aa.dom_snodes bb.dom_snodes) }1136ensures { result.v = (fun id sn -> if sn v then aa.v id sn else bb.v id sn) } =1137let r = VBDD.ite (Var v.n v.s v.scal) aa bb in1138let lemma pt (id: indexes) (sn: snodes) : unit1139ensures { r.v id sn = if sn v then aa.v id sn else bb.v id sn }1140=1141assert { r.v id sn = r.VBDD.v (to_cube id sn) };1142mem_to_cube_snode id sn v1143in1144r11451146lemma to_indexes_remove_index: Valid (62ms) (cvc4)1147forall x: VBDD.Cube.b, i: index.1148to_indexes (Set.remove (Index i) x) = Set.remove i (to_indexes x)1149lemma to_snodes_remove_index: Valid (79ms) (colibri2)1150forall x: VBDD.Cube.b, i: index.1151to_snodes (Set.remove (Index i) x) = to_snodes x1152lemma to_indexes_remove_snode: Valid (78ms) (colibri2)1153forall x: VBDD.Cube.b, v: snode.1154to_indexes (Set.remove (Var v.n v.s v.scal) x) = to_indexes x1155lemma to_snodes_remove_snode: Valid (364ms) (cvc4)1156forall x: VBDD.Cube.b, v: snode.1157to_snodes (Set.remove (Var v.n v.s v.scal) x) = Set.remove v (to_snodes x)11581159lemma to_cube_add_index: Valid (90ms) (colibri2)1160forall id: indexes, sn: snodes, i: index.1161to_cube (Set.add i id) sn = Set.add (Index i) (to_cube id sn)1162lemma to_cube_remove_index: Valid (84ms) (colibri2)1163forall id: indexes, sn: snodes, i: index.1164to_cube (Set.remove i id) sn = Set.remove (Index i) (to_cube id sn)1165lemma to_cube_add_snode: Valid (88ms) (colibri2)1166forall id: indexes, sn: snodes, v: snode.1167to_cube id (Set.add v sn) = Set.add (Var v.n v.s v.scal) (to_cube id sn)1168lemma to_cube_remove_snode: Valid (91ms) (colibri2)1169forall id: indexes, sn: snodes, v: snode.1170to_cube id (Set.remove v sn) = Set.remove (Var v.n v.s v.scal) (to_cube id sn)1171Valid (1.1s) (colibri2)1172let partial cofactors_index (i: index) (a: t) : (t, t)1173returns { (p, n) ->1174p.dom_indexes = Set.remove i a.dom_indexes /\1175n.dom_indexes = Set.remove i a.dom_indexes /\1176p.dom_snodes = a.dom_snodes /\1177n.dom_snodes = a.dom_snodes /\1178p.v = (fun id sn -> a.v (Set.add i id) sn) /\1179n.v = (fun id sn -> a.v (Set.remove i id) sn) } =1180let (p, n) = VBDD.cofactors (Index i) a in1181(p, n)1182Valid (224ms) (colibri2 6) (split_vc 2) (depth 2)1183let partial cofactors_snode (v: snode) (a: t) : (t, t)1184returns { (p, n) ->1185p.dom_indexes = a.dom_indexes /\1186n.dom_indexes = a.dom_indexes /\1187p.dom_snodes = Set.remove v a.dom_snodes /\1188n.dom_snodes = Set.remove v a.dom_snodes /\1189p.v = (fun id sn -> a.v id (Set.add v sn)) /\1190n.v = (fun id sn -> a.v id (Set.remove v sn)) } =1191let (p, n) = VBDD.cofactors (Var v.n v.s v.scal) a in1192(p, n)11931194function nb_nodes (a:t) : int = VBDD.nb_nodes a11951196function support_indexes (a:t) : indexes = to_indexes (VBDD.support a)1197function support_snodes (a:t) : snodes = to_snodes (VBDD.support a)1198Valid (91ms) (colibri2)1199lemma support_dom: forall x.1200Set.subset (support_indexes x) x.dom_indexes /\ Set.subset (support_snodes x) x.dom_snodes1201Valid (695ms) (colibri2) (cvc4) (split_vc) (depth 1)1202let lemma support_exact (x:t) (id1 id2:indexes) (sn1 sn2:snodes) : unit1203requires { forall i. Set.mem i (support_indexes x) -> id1 i = id2 i }1204requires { forall s. Set.mem s (support_snodes x) -> sn1 s = sn2 s }1205ensures { x.v id1 sn1 = x.v id2 sn2 }1206=1207VBDD.support_exact x (to_cube id1 sn1) (to_cube id2 sn2)1208Valid (98ms) (colibri2 5) (split_vc) (depth 1)1209let lemma support_snodes_dep (x:t) (nd: snode) : unit1210requires { Set.mem nd (support_snodes x) }1211ensures { exists id sn. x.v id (Set.add nd sn) <> x.v id (Set.remove nd sn) }1212=1213VBDD.support_dep x (Var nd.n nd.s nd.scal);1214let ghost c = any VBDD.Cube.b1215ensures { 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) } in1216assert { to_cube (to_indexes c) (to_snodes c) = c };1217assert { x.v (to_indexes c) (Set.add nd (to_snodes c)) <> x.v (to_indexes c) (Set.remove nd (to_snodes c)) }12181219predicate is_support (cb:t) = BDD.is_support cb.b1220Valid (139ms) (colibri2)1221let cube_true () : t1222ensures { result.dom_indexes = Set.empty /\ result.dom_snodes = Set.empty }1223ensures { support_indexes result = Set.empty /\ support_snodes result = Set.empty }1224ensures { is_support result }1225= VBDD.ttrue ()1226Valid (160ms) (colibri2)1227let partial cube_snode (nd: snode) : t1228ensures { result.dom_indexes = Set.empty /\ result.dom_snodes = Set.singleton nd }1229ensures { support_indexes result = Set.empty /\ support_snodes result = Set.singleton nd }1230ensures { is_support result }1231= VBDD.bdd_of_var (Var nd.n nd.s nd.scal)1232Valid (132ms) (colibri2)1233let partial cube_index (i: index) : t1234ensures { result.dom_indexes = Set.singleton i /\ result.dom_snodes = Set.empty }1235ensures { support_indexes result = Set.singleton i /\ support_snodes result = Set.empty }1236ensures { is_support result }1237= VBDD.bdd_of_var (Index i)1238Valid (95ms) (colibri2)1239let support_union (x y: t) : t1240requires { is_support x /\ is_support y }1241ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }1242ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }1243ensures { support_indexes result = Set.union (support_indexes x) (support_indexes y) }1244ensures { support_snodes result = Set.union (support_snodes x) (support_snodes y) }1245ensures { is_support result }1246= VBDD.support_union x y12471248Valid (108ms) (colibri2)1249let vars (a:t) : list Key.t1250ensures { forall i. Mem.mem (Key.Index i) result <-> Set.mem i (support_indexes a) }1251ensures { forall n s ab. Mem.mem (Key.Var n s ab) result <-> Set.mem { n = n; s = s; scal = ab } (support_snodes a) }1252ensures { Distinct.distinct result }1253= VBDD.vars a12541255type inspect = Bool bool | IteIndex index t t | IteSnode snode t t1256Valid (400ms) (colibri2 40) (cvc4) (split_vc 5) (depth 3)1257let inspect (a:t) : inspect1258ensures { match result with1259| Bool b -> a.v = (fun _ _ -> b) /\1260support_indexes a = Set.empty /\ support_snodes a = Set.empty1261| IteIndex i th el ->1262Set.mem i (support_indexes a) /\1263Set.subset (support_indexes th) (Set.remove i (support_indexes a)) /\1264Set.subset (support_indexes el) (Set.remove i (support_indexes a)) /\1265Set.subset (support_snodes th) (support_snodes a) /\1266Set.subset (support_snodes el) (support_snodes a) /\1267Set.mem i a.dom_indexes /\1268Set.subset th.dom_indexes (Set.remove i a.dom_indexes) /\1269Set.subset el.dom_indexes (Set.remove i a.dom_indexes) /\1270Set.subset th.dom_snodes a.dom_snodes /\1271Set.subset el.dom_snodes a.dom_snodes /\12720 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\1273a.v = (fun id sn -> if Set.mem i id then th.v id sn else el.v id sn)1274| IteSnode nd th el ->1275Set.mem nd (support_snodes a) /\1276Set.subset (support_indexes th) (support_indexes a) /\1277Set.subset (support_indexes el) (support_indexes a) /\1278Set.subset (support_snodes th) (Set.remove nd (support_snodes a)) /\1279Set.subset (support_snodes el) (Set.remove nd (support_snodes a)) /\1280Set.mem nd a.dom_snodes /\1281Set.subset th.dom_indexes a.dom_indexes /\1282Set.subset el.dom_indexes a.dom_indexes /\1283Set.subset th.dom_snodes (Set.remove nd a.dom_snodes) /\1284Set.subset el.dom_snodes (Set.remove nd a.dom_snodes) /\12850 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\1286a.v = (fun id sn -> if Set.mem nd sn then th.v id sn else el.v id sn)1287end }1288=1289match VBDD.inspect a with1290| VBDD.Bool b -> Bool b1291| VBDD.Ite (Index i) th el ->1292assert { forall id sn. Set.mem (Index i) (to_cube id sn) <-> Set.mem i id };1293IteIndex i th el1294| VBDD.Ite (Var n s a) th el ->1295let nd = { n = n; s = s; scal = a } in1296assert { forall id sn. Set.mem (Var n s a) (to_cube id sn) <-> Set.mem nd sn };1297IteSnode nd th el1298end12991300lemma to_indexes_diff: Valid (1.9s) (cvc4)1301forall x y: VBDD.Cube.b.1302to_indexes (Set.diff x y) = Set.diff (to_indexes x) (to_indexes y)1303lemma to_snodes_diff: Valid (1.5s) (cvc4)1304forall x y: VBDD.Cube.b.1305to_snodes (Set.diff x y) = Set.diff (to_snodes x) (to_snodes y)13061307function update_id (id: indexes) (s: indexes) (id': indexes) : indexes =1308(fun i -> if s i then id' i else id i)1309function update_sn (sn: snodes) (s: snodes) (sn': snodes) : snodes =1310(fun i -> if s i then sn' i else sn i)13111312lemma to_cube_update: Valid (125ms) (colibri2)1313forall id sn s_id s_sn id' sn'.1314VBDD.update (to_cube id sn) (to_cube s_id s_sn) (to_cube id' sn')1315= to_cube (update_id id s_id id') (update_sn sn s_sn sn')13161317lemma update_roundtrip: Valid (97ms) (colibri2)1318forall x: t, s: t, id: indexes, sn: snodes, c': VBDD.Cube.b.1319x.v (update_id id (support_indexes s) (to_indexes c')) (update_sn sn (support_snodes s) (to_snodes c'))1320= x.VBDD.v (VBDD.update (to_cube id sn) (VBDD.support s) c')1321Valid (469ms) (colibri2 5) (cvc4 2) (split_vc) (depth 1)1322let dexist (s x: t) : t1323requires { is_support s }1324ensures { result.dom_indexes = Set.diff x.dom_indexes (support_indexes s) }1325ensures { result.dom_snodes = Set.diff x.dom_snodes (support_snodes s) }1326ensures { result.v = (fun id sn ->1327exists id' sn'. x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn')) } =1328let r = VBDD.dexist s x in1329assert { forall id sn id' sn'.1330x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn')1331= x.VBDD.v (VBDD.update (to_cube id sn) (VBDD.support s) (to_cube id' sn')) };1332assert { forall id sn.1333(exists id' sn'. x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn'))1334= (exists c'. x.VBDD.v (VBDD.update (to_cube id sn) (VBDD.support s) c')) };1335assert { forall id sn. r.v id sn =1336(exists id' sn'. x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn')) };1337r1338Valid (172ms) (colibri2 6) (cvc4) (split_vc) (depth 1)1339let dforall (s x: t) : t1340requires { is_support s }1341ensures { result.dom_indexes = Set.diff x.dom_indexes (support_indexes s) }1342ensures { result.dom_snodes = Set.diff x.dom_snodes (support_snodes s) }1343ensures { result.v = (fun id sn ->1344forall id' sn'. x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn')) } =1345let r = VBDD.dforall s x in1346assert { forall id sn id' sn'.1347x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn')1348= x.VBDD.v (VBDD.update (to_cube id sn) (VBDD.support s) (to_cube id' sn')) };1349assert { forall id sn.1350(forall id' sn'. x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn'))1351= (forall c'. x.VBDD.v (VBDD.update (to_cube id sn) (VBDD.support s) c')) };1352assert { forall id sn.1353r.v id sn = (forall id' sn'. x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn')) };1354r13551356lemma to_cube_map_set_index: Valid (100ms) (colibri2)1357forall id: indexes, sn: snodes, i: index, b: bool.1358to_cube (Map.set id i b) sn = Map.set (to_cube id sn) (Index i) b1359lemma to_cube_map_set_snode: Valid (97ms) (colibri2)1360forall id: indexes, sn: snodes, v: snode, b: bool.1361to_cube id (Map.set sn v b) = Map.set (to_cube id sn) (Var v.n v.s v.scal) b1362Valid (407ms) (colibri2 4) (cvc4) (split_vc) (depth 1)1363let partial compose_index (i: index) (f a: t) : t1364ensures { result.dom_indexes = Set.union f.dom_indexes (Set.remove i a.dom_indexes) }1365ensures { result.dom_snodes = Set.union f.dom_snodes a.dom_snodes }1366ensures { result.v = (fun id sn -> a.v (Map.set id i (f.v id sn)) sn) } =1367let r = VBDD.compose (Index i) f a in1368assert { forall id sn.1369to_cube (Map.set id i (f.v id sn)) sn = Map.set (to_cube id sn) (Index i) (f.v id sn) };1370assert { forall id sn. r.v id sn = a.v (Map.set id i (f.v id sn)) sn };1371r1372Valid (388ms) (colibri2 4) (cvc4) (split_vc) (depth 1)1373let partial compose_snode (v: snode) (f a: t) : t1374ensures { result.dom_indexes = Set.union f.dom_indexes a.dom_indexes }1375ensures { result.dom_snodes = Set.union f.dom_snodes (Set.remove v a.dom_snodes) }1376ensures { result.v = (fun id sn -> a.v id (Map.set sn v (f.v id sn))) } =1377let r = VBDD.compose (Var v.n v.s v.scal) f a in1378assert { forall id sn.1379to_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) };1380assert { forall id sn. r.v id sn = a.v id (Map.set sn v (f.v id sn)) };1381r13821383function get_cube_indexes (cb: t) : indexes = to_indexes (VBDD.get_cube cb)1384function get_cube_snodes (cb: t) : snodes = to_snodes (VBDD.get_cube cb)13851386lemma to_cube_union: Valid (290ms) (cvc4)1387forall a1: indexes, b1: indexes, a2: snodes, b2: snodes.1388to_cube (Set.union a1 b1) (Set.union a2 b2) = Set.union (to_cube a1 a2) (to_cube b1 b2)1389lemma to_cube_diff: Valid (331ms) (cvc4)1390forall a1: indexes, b1: indexes, a2: snodes, b2: snodes.1391to_cube (Set.diff a1 b1) (Set.diff a2 b2) = Set.diff (to_cube a1 a2) (to_cube b1 b2)1392lemma to_cube_get_cube: Valid (58ms) (colibri2)1393forall cb: t. to_cube (get_cube_indexes cb) (get_cube_snodes cb) = VBDD.get_cube cb1394
A cube on the variables of the keys
predicate is_cube (cb:t) = BDD.is_cube cb.b /\1397forall y. Set.mem y (BDD.get_cube cb.b) -> Set.mem (key_of_var y) keys13981399predicate good_cube (cb: t) =1400is_cube cb /\ Set.subset (get_cube_indexes cb) (support_indexes cb) /\1401Set.subset (get_cube_snodes cb) (support_snodes cb)1402Valid (59ms) (colibri2)1403lemma to_indexes_empty: to_indexes (Set.empty: VBDD.Cube.b) = Set.empty Valid (70ms) (colibri2)1404lemma to_snodes_empty: to_snodes (Set.empty: VBDD.Cube.b) = Set.empty1405Valid (72ms) (cvc4)1406let lemma cube_empty_good (x: t) : unit1407requires { is_support x /\ support_indexes x = Set.empty /\ support_snodes x = Set.empty }1408ensures { good_cube x /\ get_cube_indexes x = Set.empty /\ get_cube_snodes x = Set.empty }1409=1410assert { VBDD.get_cube x = VBDD.support x };1411assert { get_cube_indexes x = support_indexes x /\ get_cube_snodes x = support_snodes x }1412Valid (388ms) (colibri2 11) (cvc4) (split_vc) (depth 1)1413let partial cube_lit (i: index) (b: bool) : t1414ensures { result.dom_indexes = Set.singleton i /\ result.dom_snodes = Set.empty }1415ensures { support_indexes result = Set.singleton i /\ support_snodes result = Set.empty }1416ensures { good_cube result }1417ensures { get_cube_indexes result = (if b then Set.singleton i else Set.empty) }1418ensures { get_cube_snodes result = Set.empty }1419=1420let r = if b then VBDD.bdd_of_var (Index i) else VBDD.bdd_not (Index i) in1421assert { VBDD.get_cube r = if b then Set.singleton (Index i) else Set.empty };1422r1423Valid (1.9s) (colibri2 25) (cvc4 2) (split_vc 3) (depth 2)1424let cube_and (x y: t) : t1425requires { good_cube x /\ good_cube y }1426requires { Set.inter (support_indexes x) (support_indexes y) = Set.empty }1427requires { Set.inter (support_snodes x) (support_snodes y) = Set.empty }1428ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }1429ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }1430ensures { good_cube result }1431ensures { support_indexes result = Set.union (support_indexes x) (support_indexes y) }1432ensures { support_snodes result = Set.union (support_snodes x) (support_snodes y) }1433ensures { get_cube_indexes result = Set.union (get_cube_indexes x) (get_cube_indexes y) }1434ensures { get_cube_snodes result = Set.union (get_cube_snodes x) (get_cube_snodes y) }1435=1436assert { forall k. Set.mem k (VBDD.support x) -> Set.mem k (VBDD.support y) ->1437match k with1438| Index i -> Set.mem i (support_indexes x) /\ Set.mem i (support_indexes y)1439| 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)1440end };1441assert { forall k. Set.mem k (VBDD.support x) -> Set.mem k (VBDD.support y) -> false1442by match k with1443| Index i -> Set.mem i (Set.inter (support_indexes x) (support_indexes y))1444| Var n s a -> Set.mem { n = n; s = s; scal = a } (Set.inter (support_snodes x) (support_snodes y))1445end };1446VBDD.of_to_dom x; VBDD.of_to_dom y;1447assert { forall v. Set.mem v (BDD.support x.VBDD.b) -> Set.mem (key_of_var v) (VBDD.support x)1448by Set.mem v x.VBDD.b.BDD.dom /\ Set.mem (key_of_var v) keys /\ var_of_key (key_of_var v) = v };1449assert { forall v. Set.mem v (BDD.support y.VBDD.b) -> Set.mem (key_of_var v) (VBDD.support y)1450by Set.mem v y.VBDD.b.BDD.dom /\ Set.mem (key_of_var v) keys /\ var_of_key (key_of_var v) = v };1451assert { forall v. Set.mem v (BDD.support x.VBDD.b) -> Set.mem v (BDD.support y.VBDD.b) -> false1452by Set.mem (key_of_var v) (VBDD.support x) /\ Set.mem (key_of_var v) (VBDD.support y) };1453assert { Set.inter (BDD.support x.VBDD.b) (BDD.support y.VBDD.b) = Set.empty };1454assert { forall v. Set.mem v (BDD.get_cube x.VBDD.b) -> Set.mem (key_of_var v) (VBDD.get_cube x) };1455assert { forall v. Set.mem v (BDD.get_cube y.VBDD.b) -> Set.mem (key_of_var v) (VBDD.get_cube y) };1456assert { Set.subset (BDD.get_cube x.VBDD.b) (BDD.support x.VBDD.b) };1457assert { Set.subset (BDD.get_cube y.VBDD.b) (BDD.support y.VBDD.b) };1458let r = VBDD.dand x y in1459assert { support_indexes r = Set.union (support_indexes x) (support_indexes y) };1460assert { support_snodes r = Set.union (support_snodes x) (support_snodes y) };1461assert { get_cube_indexes r = Set.union (get_cube_indexes x) (get_cube_indexes y) };1462assert { get_cube_snodes r = Set.union (get_cube_snodes x) (get_cube_snodes y) };1463assert { is_cube r };1464r1465Valid (161ms) (colibri2 5) (cvc4) (split_vc) (depth 1)1466let cofactor (a cb: t) : t1467requires { is_cube cb }1468ensures { result.dom_indexes = Set.diff a.dom_indexes (support_indexes cb) }1469ensures { result.dom_snodes = Set.diff a.dom_snodes (support_snodes cb) }1470ensures { result.v = (fun id sn ->1471a.v (Set.union (Set.diff id (support_indexes cb)) (get_cube_indexes cb))1472(Set.union (Set.diff sn (support_snodes cb)) (get_cube_snodes cb))) } =1473let r = VBDD.cofactor a cb in1474assert { forall id sn.1475Set.union (Set.diff (to_cube id sn) (VBDD.support cb)) (VBDD.get_cube cb)1476= to_cube (Set.union (Set.diff id (support_indexes cb)) (get_cube_indexes cb))1477(Set.union (Set.diff sn (support_snodes cb)) (get_cube_snodes cb)) };1478assert { forall id sn. r.v id sn =1479a.v (Set.union (Set.diff id (support_indexes cb)) (get_cube_indexes cb))1480(Set.union (Set.diff sn (support_snodes cb)) (get_cube_snodes cb)) };1481r14821483scope Vector1484type vector = VBDD.Vector.vector14851486function removed_indexes (v:vector) : indexes = to_indexes (VBDD.Vector.removed v)1487function removed_snodes (v:vector) : snodes = to_snodes (VBDD.Vector.removed v)1488function added_indexes (v:vector) : indexes = to_indexes (VBDD.Vector.added v)1489function added_snodes (v:vector) : snodes = to_snodes (VBDD.Vector.added v)1490
A predicate on indexes and snodes as a predicate on cubes
function lift (a: indexes -> snodes -> bool) : VBDD.Value.b =1493fun c -> a (to_indexes c) (to_snodes c)14941495function subst (v:vector) : (indexes -> snodes -> bool) -> (indexes -> snodes -> bool) =1496fun a id sn -> (VBDD.Vector.subst v) (lift a) (to_cube id sn)1497
a with the index i (resp. the snode sn0) set to b
function upd_index (a: indexes -> snodes -> bool) (i: index) (b: bool) : indexes -> snodes -> bool =1500fun id sn -> a (Map.set id i b) sn1501function upd_snode (a: indexes -> snodes -> bool) (sn0: snode) (b: bool) : indexes -> snodes -> bool =1502fun id sn -> a id (Map.set sn sn0 b)1503Valid (217ms) (colibri2)1504let create () : vector1505ensures { result.removed_indexes = Set.empty }1506ensures { result.removed_snodes = Set.empty }1507ensures { result.added_indexes = Set.empty }1508ensures { result.added_snodes = Set.empty }1509ensures { result.subst = (fun a -> a) } =1510VBDD.Vector.create ()1511Valid (92ms) (colibri2 11) (cvc4) (split_vc) (depth 1)1512let partial add_index (v: vector) (i: index) (f: t) : vector1513requires { not (Set.mem i v.removed_indexes) }1514ensures { result.removed_indexes = Set.add i v.removed_indexes }1515ensures { result.removed_snodes = v.removed_snodes }1516ensures { result.added_indexes = Set.union v.added_indexes f.dom_indexes }1517ensures { result.added_snodes = Set.union v.added_snodes f.dom_snodes }1518ensures { result.subst = (fun a id sn -> v.subst (upd_index a i (f.v id sn)) id sn) } =1519let r = VBDD.Vector.add v (Index i) f in1520let lemma subst_add (a: indexes -> snodes -> bool) (id: indexes) (sn: snodes) : unit1521ensures { subst r a id sn = subst v (upd_index a i (f.v id sn)) id sn }1522=1523let ghost b = pure { f.v id sn } in1524let lemma pt (c: Cube.b) : unit1525ensures { VBDD.Vector.upd (lift a) (Index i) b c = lift (upd_index a i b) c }1526= assert { to_indexes (Map.set c (Index i) b) = Map.set (to_indexes c) i b };1527assert { to_snodes (Map.set c (Index i) b) = to_snodes c }1528in1529assert { VBDD.Vector.upd (lift a) (Index i) b = lift (upd_index a i b) };1530assert { f.v id sn = f.VBDD.v (to_cube id sn) }1531in1532r1533Valid (101ms) (colibri2 11) (cvc4) (split_vc) (depth 1)1534let partial add_snode (v: vector) (sn0: snode) (f: t) : vector1535requires { not (Set.mem sn0 v.removed_snodes) }1536ensures { result.removed_indexes = v.removed_indexes }1537ensures { result.removed_snodes = Set.add sn0 v.removed_snodes }1538ensures { result.added_indexes = Set.union v.added_indexes f.dom_indexes }1539ensures { result.added_snodes = Set.union v.added_snodes f.dom_snodes }1540ensures { result.subst = (fun a id sn -> v.subst (upd_snode a sn0 (f.v id sn)) id sn) } =1541let r = VBDD.Vector.add v (Var sn0.n sn0.s sn0.scal) f in1542let lemma subst_add (a: indexes -> snodes -> bool) (id: indexes) (sn: snodes) : unit1543ensures { subst r a id sn = subst v (upd_snode a sn0 (f.v id sn)) id sn }1544=1545let ghost b = pure { f.v id sn } in1546let lemma pt (c: Cube.b) : unit1547ensures { VBDD.Vector.upd (lift a) (Var sn0.n sn0.s sn0.scal) b c = lift (upd_snode a sn0 b) c }1548= assert { to_indexes (Map.set c (Var sn0.n sn0.s sn0.scal) b) = to_indexes c };1549assert { to_snodes (Map.set c (Var sn0.n sn0.s sn0.scal) b) = Map.set (to_snodes c) sn0 b }1550in1551assert { VBDD.Vector.upd (lift a) (Var sn0.n sn0.s sn0.scal) b = lift (upd_snode a sn0 b) };1552assert { f.v id sn = f.VBDD.v (to_cube id sn) }1553in1554r1555Valid (118ms) (cvc4)1556let compose (v: vector) (a: t) : t1557ensures { result.dom_indexes = Set.union v.added_indexes (Set.diff a.dom_indexes v.removed_indexes) }1558ensures { result.dom_snodes = Set.union v.added_snodes (Set.diff a.dom_snodes v.removed_snodes) }1559ensures { result.v = v.subst a.v } =1560let r = VBDD.Vector.compose v a in1561let lemma lift_v (c: VBDD.Cube.b) : unit1562ensures { lift a.v c = a.VBDD.v c }1563= assert { to_cube (to_indexes c) (to_snodes c) = c } in1564assert { lift a.v = a.VBDD.v };1565let lemma comp_subst (id: indexes) (sn: snodes) : unit1566ensures { (subst v (a.v)) id sn = r.v id sn }1567= assert { (subst v (a.v)) id sn = (VBDD.Vector.subst v) a.VBDD.v (to_cube id sn) } in1568r1569end15701571end1572