library colibrilib.pbdd — module PBDDmodule PBDD : PBDD_intf248
Implemented
use ref.Ref249use mach.int.Int63250use list.List251use list.Mem252use list.Distinct253use colibrilib.bdd.Key254use int.Int255use int.MinMax256use set.Set257use bool.Bool258use colibrilib.sbdd.SBDD259use colibrilib.sbdd.SBDDShift260use colibrilib.bdd.IArray63261use seq.Seq262use mach.array.Array63263use colibrilib.sbdd.SNode264use colibrilib.zarith.Zbit265266function to_indexes (id:int) : SBDD.indexes = (fun (i:int63) -> Zbit.bittest id (to_int i))267Valid (107ms) (cvc4)268lemma to_indexes_lor: forall a b. to_indexes (Zbit.lor a b) = Set.union (to_indexes a) (to_indexes b)269Valid (92ms) (cvc4)270let lemma to_indexes_lsl_1 (i:int63) : unit271requires { 0 <= to_int i }272ensures { to_indexes (Zbit.lsl 1 (to_int i)) = Set.singleton i }273=274assert { forall j. 0 <= to_int j ->275Zbit.bittest (Zbit.asr 1 (0 - to_int i)) (to_int j)276= Zbit.bittest 1 (to_int j + (0 - to_int i)) }277Valid (698ms) (cvc4)278let lemma to_indexes_change (id:int) (i:int63) (v:bool) : unit279requires { 0 <= to_int i }280ensures { to_indexes (Zbit.change id (to_int i) v) = Map.set (to_indexes id) i v }281=282assert { forall j. 0 <= to_int j ->283Zbit.bittest (Zbit.change id (to_int i) v) (to_int j)284= (if j = i then v else to_indexes id j) };285assert { forall j. to_indexes (Zbit.change id (to_int i) v) j286= Map.set (to_indexes id) i v j }287288Valid (92ms) (colibri2 2) (cvc4) (cvc5) (split_vc) (depth 1)289let lemma numbits_bound_from_indexes (r wit:int) : ()290requires { 0 <= r }291requires { 0 <= wit }292requires { numbits wit <= Int63.max_int + 1 }293requires { forall i. Int63.max_int < i -> not (bittest r i) }294requires { Set.subset (to_indexes r) (to_indexes wit) }295ensures { numbits r <= numbits wit }296=297for i=0 to Int63.max_int do298invariant { forall j. 0 <= j < i -> Zbit.bittest r j -> Zbit.bittest wit j }299()300done301Valid (2.3s) (colibri2 15) (cvc5 5) (split_vc 4) (depth 4)302let rec ghost function from_indexes (s:SBDD.indexes) (wit:int) : int303requires { 0 <= wit }304requires { numbits wit <= Int63.max_int + 1 }305requires { Set.subset s (to_indexes wit) }306ensures { (to_indexes result) = s }307ensures { numbits result <= numbits wit }308ensures { 0 <= result }309=310let rec aux (k:int63) : int311requires { 0 <= k }312ensures { 0 <= result }313ensures { forall i. to_int k < i -> not (bittest result i) }314ensures { forall j:int63. j <= k ->315((to_indexes result) j <-> s j) }316ensures { forall j:int63. j <= k ->317(to_indexes result) j -> (to_indexes wit) j }318variant { k }319= if k = 0 then (if s 0 then 1 else 0)320else321let prev = aux (k - 1) in322change_nonneg prev (to_int k) (s k);323Zbit.change prev (to_int k) (s k)324in325let r = aux Int63.max_int in326numbits_bound_from_indexes r wit;327r328Valid (284ms) (colibri2 3) (cvc5) (split_vc) (depth 1)329let lemma to_indexes_subset (a:int) (b:int) : ()330requires { 0 <= a }331requires { Zbit.numbits a <= Int63.max_int + 1 }332requires { Set.subset (to_indexes a) (to_indexes b) }333ensures { Zbit.subset a b }334=335for i=0 to Int63.max_int do336invariant { forall j. 0 <= j < i -> Zbit.bittest a j -> Zbit.bittest b j }337()338done339Valid (60ms) (colibri2)340type t = {341b: SBDD.t;342ghost indexes : int;343} invariant { to_indexes indexes = b.SBDD.dom_indexes }344invariant { Zbit.numbits indexes <= Int63.max_int + 1 }345invariant { 0 <= indexes }346by { b = SBDD.tfalse (); indexes = 0 }347348type indexes = int349type snodes = Set.set snode350351function dom_indexes (x:t) : indexes = x.indexes352353function dom_snodes (x:t) : snodes = x.b.SBDD.dom_snodes354function v (x:t) : indexes -> snodes -> bool = (fun id sn -> x.b.SBDD.v (to_indexes id) sn)355Valid (111ms) (cvc4)356let lemma support_v (x:t) (id1 id2:indexes) (sn:snodes) : unit357requires { forall i. 0 <= i -> Zbit.bittest x.dom_indexes i -> (Zbit.bittest id1 i <-> Zbit.bittest id2 i) }358ensures { x.v id1 sn = x.v id2 sn }359=360SBDD.support_v x.b (to_indexes id1) (to_indexes id2) sn sn361Valid (200ms) (cvc4)362let dand (x y: t) : t363ensures { result.dom_indexes = Zbit.lor x.dom_indexes y.dom_indexes }364ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }365ensures { result.v = (fun id sn -> andb (x.v id sn) (y.v id sn)) } =366{ b = SBDD.dand x.b y.b; indexes = Zbit.lor x.indexes y.indexes }367Valid (202ms) (cvc4)368let dor (x y: t) : t369ensures { result.dom_indexes = Zbit.lor x.dom_indexes y.dom_indexes }370ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }371ensures { result.v = (fun id sn -> orb (x.v id sn) (y.v id sn)) } =372{ b = SBDD.dor x.b y.b; indexes = Zbit.lor x.indexes y.indexes }373Valid (796ms) (cvc4)374let dxor (x y: t) : t375ensures { result.dom_indexes = Zbit.lor x.dom_indexes y.dom_indexes }376ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }377ensures { result.v = (fun id sn -> xorb (x.v id sn) (y.v id sn)) } =378{ b = SBDD.dxor x.b y.b; indexes = Zbit.lor x.indexes y.indexes }379Valid (379ms) (colibri2 5) (cvc4) (split_vc) (depth 1)380let tfalse () : t381ensures { result.dom_indexes = 0 }382ensures { result.dom_snodes = Set.empty }383ensures { result.v = (fun _ _ -> False) } =384{ b = SBDD.tfalse (); indexes = 0 }385Valid (158ms) (colibri2 6) (split_vc) (depth 1)386let ttrue () : t387ensures { result.dom_indexes = 0 }388ensures { result.dom_snodes = Set.empty }389ensures { result.v = (fun _ _ -> True) } =390{ b = SBDD.ttrue (); indexes = 0 }391Valid (655ms) (cvc4)392let dnot (a: t) : t393ensures { result.dom_indexes = a.dom_indexes }394ensures { result.dom_snodes = a.dom_snodes }395ensures { result.v = (fun id sn -> notb (a.v id sn)) } =396{ b = SBDD.dnot a.b; indexes = a.indexes }397Valid (999ms) (cvc4)398let is_equal (x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)399ensures { result = (forall id sn. x.v id sn = y.v id sn) }400ensures { not result ->4010 <= wid /\ numbits wid <= numbits (Zbit.lor x.dom_indexes y.dom_indexes) /\402(Zbit.subset wid (Zbit.lor x.dom_indexes y.dom_indexes)) /\403(Set.subset wsn (Set.union x.dom_snodes y.dom_snodes)) /\404x.v wid wsn <> y.v wid wsn } =405let (r, ghost sid, ghost ssn) = SBDD.is_equal x.b y.b in406if r then (r,0,Set.empty) else407begin408lor_numbits x.dom_indexes y.dom_indexes;409assert { numbits (Zbit.lor x.dom_indexes y.dom_indexes)410= max (numbits x.dom_indexes) (numbits y.dom_indexes) };411let ghost id1 = from_indexes sid (Zbit.lor x.dom_indexes y.dom_indexes) in412let ghost sn1 = ssn in413to_indexes_subset id1 (Zbit.lor x.dom_indexes y.dom_indexes);414(r, id1, sn1)415end416Valid (105ms) (cvc4)417let is_inter_empty (x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)418ensures { result = (forall id sn. not (x.v id sn /\ y.v id sn)) }419ensures { not result ->4200 <= wid /\ numbits wid <= numbits (Zbit.lor x.dom_indexes y.dom_indexes) /\421(Zbit.subset wid (Zbit.lor x.dom_indexes y.dom_indexes)) /\422(Set.subset wsn (Set.union x.dom_snodes y.dom_snodes)) /\423x.v wid wsn /\ y.v wid wsn } =424let (r, ghost sid, ghost ssn) = SBDD.is_inter_empty x.b y.b in425if r then (r,0,Set.empty) else begin426lor_numbits x.dom_indexes y.dom_indexes;427assert { numbits (Zbit.lor x.dom_indexes y.dom_indexes)428= max (numbits x.dom_indexes) (numbits y.dom_indexes) };429let ghost id1 = from_indexes sid (Zbit.lor x.dom_indexes y.dom_indexes) in430let ghost sn1 = ssn in431to_indexes_subset id1 (Zbit.lor x.dom_indexes y.dom_indexes);432(r, id1, sn1)433end434Valid (108ms) (cvc4)435let partial bdd_of_index (i: int63) : t436requires { 0 <= to_int i }437ensures { result.dom_indexes = Zbit.lsl 1 (to_int i) }438ensures { result.dom_snodes = Set.empty }439ensures { result.v = (fun id _ -> Zbit.bittest id (to_int i)) } =440to_indexes_lsl_1 i;441{ b = SBDD.bdd_of_index i; indexes = Zbit.lsl 1 (to_int i) }442Valid (392ms) (colibri2 5) (cvc4) (split_vc) (depth 1)443let partial bdd_of_snode (v: snode) : t444ensures { result.dom_indexes = 0 }445ensures { result.dom_snodes = Set.singleton v }446ensures { result.v = (fun _ sn -> sn v) } =447{ b = SBDD.bdd_of_snode v; indexes = 0 }448Valid (412ms) (colibri2 5) (cvc4) (split_vc) (depth 1)449let partial bdd_not_snode (v: snode) : t450ensures { result.dom_indexes = 0 }451ensures { result.dom_snodes = Set.singleton v }452ensures { result.v = (fun _ sn -> not (sn v)) } =453{ b = SBDD.bdd_not_snode v; indexes = 0 }454Valid (1.6s) (colibri2 8) (cvc4 3) (split_vc) (depth 1)455let partial ite_index (i: int63) (aa bb: t) : t456requires { 0 <= to_int i }457ensures { result.dom_indexes = Zbit.set (Zbit.lor aa.dom_indexes bb.dom_indexes) i }458ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }459ensures { result.v = (fun id sn -> if Zbit.bittest id (to_int i) then aa.v id sn else bb.v id sn) } =460let ghost l = Zbit.lor aa.indexes bb.indexes in461lor_numbits aa.indexes bb.indexes;462numbits_set l (to_int i);463assert { forall j:int63. to_indexes (Zbit.set l (to_int i)) j464= Set.add i (Set.union aa.b.SBDD.dom_indexes bb.b.SBDD.dom_indexes) j };465{ b = SBDD.ite_index i aa.b bb.b; indexes = Zbit.set l (to_int i) }466Valid (1.4s) (colibri2 10) (cvc4 2) (split_vc) (depth 1)467let ghost ite_index_g (i: int63) (aa bb: t) : t468requires { 0 <= to_int i < 3 }469ensures { result.dom_indexes = Zbit.set (Zbit.lor aa.dom_indexes bb.dom_indexes) i }470ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }471ensures { result.v = (fun id sn -> if Zbit.bittest id (to_int i) then aa.v id sn else bb.v id sn) } =472let l = Zbit.lor aa.indexes bb.indexes in473lor_numbits aa.indexes bb.indexes;474numbits_set l (to_int i);475assert { forall j:int63. to_indexes (Zbit.set l (to_int i)) j476= Set.add i (Set.union aa.b.SBDD.dom_indexes bb.b.SBDD.dom_indexes) j };477{ b = SBDD.ite_index_g i aa.b bb.b; indexes = Zbit.set l (to_int i) }478Valid (1.2s) (cvc4)479let partial ite_snode (v: snode) (aa bb: t) : t480ensures { result.dom_indexes = (Zbit.lor aa.dom_indexes bb.dom_indexes) }481ensures { result.dom_snodes = Set.add v (Set.union aa.dom_snodes bb.dom_snodes) }482ensures { result.v = (fun id sn -> if sn v then aa.v id sn else bb.v id sn) } =483{ b = SBDD.ite_snode v aa.b bb.b; indexes = Zbit.lor aa.indexes bb.indexes }484485function nb_nodes (a:t) : int = SBDD.nb_nodes a.b486487function support_snodes (a:t) : snodes = SBDD.support_snodes a.b488Valid (33ms) (colibri2)489let lemma support_snodes_dom (x:t) : unit490ensures { Set.subset (support_snodes x) x.dom_snodes }491= SBDD.support_dom x.b492Valid (93ms) (cvc4)493let lemma support_snodes_dep (x:t) (nd: snode) : unit494requires { Set.mem nd (support_snodes x) }495ensures { exists id sn. x.v id (Set.add nd sn) <> x.v id (Set.remove nd sn) }496=497let ghost (sid, sn) = SBDD.support_snodes_dep x.b nd in498SBDD.support_dom x.b;499let ghost id = from_indexes (Set.inter sid x.b.SBDD.dom_indexes) x.indexes in500SBDD.support_exact x.b (to_indexes id) sid (Set.add nd sn) (Set.add nd sn);501SBDD.support_exact x.b (to_indexes id) sid (Set.remove nd sn) (Set.remove nd sn);502assert { x.v id (Set.add nd sn) <> x.v id (Set.remove nd sn) }503Valid (43ms) (colibri2)504let lemma support_snodes_v (x:t) (id:indexes) (sn1 sn2:snodes) : unit505requires { forall nd. Set.mem nd (support_snodes x) -> sn1 nd = sn2 nd }506ensures { x.v id sn1 = x.v id sn2 }507=508SBDD.support_exact x.b (to_indexes id) (to_indexes id) sn1 sn2509Valid (36ms) (colibri2)510let vars (a:t) : list Key.t511ensures { forall n s ab. Mem.mem (Key.Var n s ab) result <-> Set.mem { n = n; s = s; scal = ab } (support_snodes a) }512ensures { Distinct.distinct result }513= SBDD.vars a.b514Valid (46ms) (colibri2)515let lemma numbits_le_bits (x w: int) : unit516requires { 0 <= x /\ 0 <= w }517requires { forall i. 0 <= i -> bittest x i -> i < w }518ensures { numbits x <= w }519= if x > 0 then numbits_top_bit x520521function subst_bits (subst: IArray63.t t) (id: indexes) (sn: snodes) : int -> bool =522fun i -> (subst i).v id sn523Valid (3.3s) (colibri2 44) (cvc4 19) (split_vc 3) (depth 2)524let partial compose_shift (subst: IArray63.t t) (off: int63) (x: t) : t525requires { numbits x.dom_indexes <= subst.IArray63.length }526ensures { forall nd. Set.mem nd (support_snodes x) -> nd.scal \/ in_bounds (to_int nd.s - to_int off) }527raises { Overflow -> exists nd. Set.mem nd (support_snodes x) /\ not nd.scal /\ not (in_bounds (to_int nd.s - to_int off)) }528ensures { (forall j. 0 <= j < subst.IArray63.length ->529numbits (subst j).dom_indexes <= subst.IArray63.length) ->530numbits result.dom_indexes <= subst.IArray63.length }531ensures { forall id sn. result.v id sn =532x.v (of_bits (subst_bits subst id sn) subst.IArray63.length)533(shifted sn (to_int off)) }534ensures { forall nd''. Set.mem nd'' (support_snodes result) ->535(exists j. 0 <= j < subst.IArray63.length /\ Set.mem nd'' (support_snodes (subst j))) \/536(exists nd. Set.mem nd (support_snodes x) /\ nd'' = shift_snode nd (to_int off)) }537=538let n = subst.IArray63.length in539let a = Array63.make n (SBDD.tfalse ()) in540for j = 0 to n - 1 do541invariant { forall k. 0 <= k < j -> Seq.get a.Array63.elts k = (subst k).b }542a[j] <- (IArray63.get subst j).b543done;544let sa = IArray63.of_array a in545assert { forall k. 0 <= k < n -> sa k = (subst k).b };546let lemma supp (i: int63) : unit547requires { Set.mem i (SBDD.support_indexes x.b) }548ensures { 0 <= i < n }549=550assert { Set.mem i x.b.SBDD.dom_indexes };551assert { Zbit.bittest x.indexes (to_int i) };552if x.indexes > 0 && to_int i >= Zbit.numbits x.indexes then numbits_high_clear x.indexes (to_int i)553in554assert { forall i. Set.mem i (SBDD.support_indexes x.b) -> 0 <= i < n };555let r = SBDDShift.compose_shift sa off x.b in556let ghost wit = pure { of_bits (fun i -> bittest x.indexes i \/557exists k. 0 <= k < n /\ bittest (subst k).indexes i)558(Int63.max_int + 1) } in559numbits_le_bits wit pure { Int63.max_int + 1 };560let lemma sub (i: int63) : unit561requires { Set.mem i r.SBDD.dom_indexes }562ensures { to_indexes wit i }563=564if Set.mem i x.b.SBDD.dom_indexes then assert { bittest x.indexes i }565else assert { exists k. 0 <= k < n /\ bittest (subst k).indexes i }566in567let res = { b = r; indexes = from_indexes r.SBDD.dom_indexes wit } in568let lemma dom (_:unit) : unit569requires { forall j. 0 <= j < n -> numbits (subst j).dom_indexes <= n }570ensures { numbits res.dom_indexes <= n }571=572let ghost w = to_int n in573let lemma bit (i: int) : unit574requires { 0 <= i }575requires { bittest res.indexes i }576ensures { i < w }577=578if i >= w then begin579numbits_high_clear x.indexes i;580assert { forall k. 0 <= k < n -> not (bittest (subst k).indexes i) };581assert { not (bittest wit i) };582if pure { i > Int63.max_int } then begin583if res.indexes > 0 then numbits_high_clear res.indexes i584end else begin585let j = Int63.of_int i in586assert { to_indexes res.indexes j -> to_indexes wit j }587end588end589in590numbits_le_bits res.indexes w591in592let lemma value (id: indexes) (sn: snodes) : unit593ensures { res.v id sn =594x.v (of_bits (subst_bits subst id sn) n)595(shifted sn (to_int off)) }596=597SBDD.support_v x.b598pure { fun (i:int63) -> if 0 <= i < n then (sa i).SBDD.v (to_indexes id) sn else to_indexes id i }599pure { to_indexes (of_bits (subst_bits subst id sn) n) }600pure { shifted sn (to_int off) }601pure { shifted sn (to_int off) }602in603(* the snodes of the support of the result *)604let lemma img (nd'': snode) : unit605requires { Set.mem nd'' (support_snodes res) }606ensures { (exists j. 0 <= j < n /\ Set.mem nd'' (support_snodes (subst j))) \/607(exists nd. Set.mem nd (support_snodes x) /\ nd'' = shift_snode nd (to_int off)) }608=609support_snodes_dep res nd'';610let ghost (id, sn) = any (indexes, snodes)611ensures { let (id, sn) = result in res.v id (Set.add nd'' sn) <> res.v id (Set.remove nd'' sn) } in612let ghost sn1 = Set.add nd'' sn in613let ghost sn2 = Set.remove nd'' sn in614if pure { not (exists j. 0 <= j < n /\ Set.mem nd'' (support_snodes (subst j))) /\615not (exists nd. Set.mem nd (support_snodes x) /\ nd'' = shift_snode nd (to_int off)) } then begin616let lemma sj (j: int) : unit617requires { 0 <= j < n }618ensures { (subst j).v id sn1 = (subst j).v id sn2 }619= support_snodes_v pure { subst j } id sn1 sn2620in621let lemma same_id (_: unit) : unit622ensures { of_bits (subst_bits subst id sn1) n = of_bits (subst_bits subst id sn2) n }623= let lemma bt (i: int) : unit624requires { 0 <= i }625ensures { bittest (of_bits (subst_bits subst id sn1) n) i <-> bittest (of_bits (subst_bits subst id sn2) n) i }626= if i < to_int n then assert { (subst i).v id sn1 = (subst i).v id sn2 }627in628ext_bittest pure { of_bits (subst_bits subst id sn1) n } pure { of_bits (subst_bits subst id sn2) n }629in same_id ();630let lemma sx (nd: snode) : unit631requires { Set.mem nd (support_snodes x) }632ensures { sn1 (shift_snode nd (to_int off)) = sn2 (shift_snode nd (to_int off)) }633= assert { shift_snode nd (to_int off) <> nd'' }634in635let ghost g1 = pure { shifted sn1 (to_int off) } in636let ghost g2 = pure { shifted sn2 (to_int off) } in637let ghost ids = pure { of_bits (subst_bits subst id sn1) n } in638support_snodes_v x ids g1 g2;639value id sn1; value id sn2;640assert { res.v id sn1 = x.v ids g1 };641assert { res.v id sn2 = x.v (of_bits (subst_bits subst id sn2) n) g2 };642assert { ids = of_bits (subst_bits subst id sn2) n };643assert { res.v id sn1 = res.v id sn2 }644end645in646res647Valid (1.3s) (colibri2)648let partial cofactors_snode (nd: snode) (a: t) : (t, t)649returns { (p, n) ->650p.dom_indexes = a.dom_indexes /\651n.dom_indexes = a.dom_indexes /\652p.dom_snodes = Set.remove nd a.dom_snodes /\653n.dom_snodes = Set.remove nd a.dom_snodes /\654p.v = (fun id sn -> a.v id (Set.add nd sn)) /\655n.v = (fun id sn -> a.v id (Set.remove nd sn)) }656=657let (p, n) = SBDD.cofactors_snode nd a.b in658({ b = p; indexes = a.indexes }, { b = n; indexes = a.indexes })659
The cube of the snodes of l
Valid (1.1s) (colibri2)
662 let rec partial snodes_cube (l: list Key.t) : SBDD.t
663 variant { l }
664 ensures { SBDD.is_support result }
665 ensures { SBDD.support_indexes result = Set.empty }
666 ensures { forall nd. Set.mem nd (SBDD.support_snodes result) <-> Mem.mem (Key.Var nd.n nd.s nd.scal) l }
667 = match l with
668 | Nil -> SBDD.cube_true ()
669 | Cons (Key.Var n s a) l' -> SBDD.support_union (SBDD.cube_snode { n = n; s = s; scal = a }) (snodes_cube l')
670 | Cons (Key.Index _) l' -> snodes_cube l'
671 end
672
Valid (391ms) (cvc4)
673 let lemma no_snode (x: t) : unit
674 requires { forall id sn sn'. x.v id sn = x.v id sn' }
675 ensures { support_snodes x = Set.empty }
676 =
677 let lemma none (nd: snode) : unit
678 ensures { not (Set.mem nd (support_snodes x)) }
679 = if pure { Set.mem nd (support_snodes x) } then support_snodes_dep x nd
680 in
681 assert { (support_snodes x) = Set.empty }
682
Valid (667ms) (colibri2 15) (cvc4 6) (split_vc) (depth 1)
683 let partial exist_snodes (x: t) : t
684 ensures { result.dom_indexes = x.dom_indexes }
685 ensures { support_snodes result = Set.empty }
686 ensures { forall id sn. result.v id sn <-> exists sn'. x.v id sn' }
687 =
688 let c = snodes_cube (vars x) in
689 let r = SBDD.dexist c x.b in
690 let lemma memc (nd: snode) : unit
691 ensures { Set.mem nd (SBDD.support_snodes c) <-> Set.mem nd (SBDD.support_snodes x.b) }
692 = assert { nd = { n = nd.n; s = nd.s; scal = nd.scal } }
693 in
694 assert { forall nd. (SBDD.support_snodes c) nd = (SBDD.support_snodes x.b) nd };
695 assert { (SBDD.support_snodes c) = (SBDD.support_snodes x.b) };
696 assert { r.SBDD.dom_indexes = x.b.SBDD.dom_indexes };
697 let res = { b = r; indexes = x.indexes } in
698 let lemma value (id: indexes) (sn: snodes) : unit
699 ensures { res.v id sn <-> exists sn'. x.v id sn' }
700 =
701 let ghost sid = to_indexes id in
702 assert { res.v id sn <-> exists id' sn'. x.b.SBDD.v (SBDD.update_id sid (SBDD.support_indexes c) id')
703 (SBDD.update_sn sn (SBDD.support_snodes c) sn') };
704 assert { forall id'. SBDD.update_id sid (SBDD.support_indexes c) id' = sid };
705 let lemma upd (sn': snodes) : unit
706 ensures { x.b.SBDD.v sid (SBDD.update_sn sn (SBDD.support_snodes c) sn') = x.v id sn' }
707 = SBDD.support_exact x.b sid sid (SBDD.update_sn sn (SBDD.support_snodes x.b) sn') sn'
708 in
709 if pure { exists sn'. x.v id sn' } then begin
710 let ghost w = any snodes ensures { x.v id result } in
711 upd w;
712 assert { x.b.SBDD.v (SBDD.update_id sid (SBDD.support_indexes c) sid) (SBDD.update_sn sn (SBDD.support_snodes c) w) }
713 end
714 in
715 no_snode res;
716 res
717
Valid (548ms) (colibri2 31) (cvc4 4) (cvc5 4) (split_vc) (depth 1)
718 let partial get_pos (a: t) (pos s: int63) : t
719 requires { 0 <= s /\ numbits a.dom_indexes <= s }
720 requires { 0 <= pos /\ numbits pos <= s }
721 ensures { result.dom_indexes = 0 }
722 ensures { Set.subset result.dom_snodes a.dom_snodes }
723 ensures { forall id sn. result.v id sn <-> a.v pos sn }
724 =
725 let c = ref (SBDD.cube_true ()) in
726 SBDD.cube_empty_good !c;
727 for i = 0 to s - 1 do
728 invariant { SBDD.good_cube !c }
729 invariant { forall j: int63. Set.mem j (SBDD.support_indexes !c) <-> 0 <= j < i }
730 invariant { SBDD.support_snodes !c = Set.empty }
731 invariant { forall j: int63. Set.mem j (SBDD.get_cube_indexes !c) <-> (0 <= j < i /\ bittest pos j) }
732 invariant { SBDD.get_cube_snodes !c = Set.empty }
733 invariant { (!c).SBDD.dom_snodes = Set.empty }
734 let l = SBDD.cube_lit i (Zbit.test_bit (to_int pos) i) in
735 c := SBDD.cube_and !c l
736 done;
737 let ghost cs = SBDD.support_indexes !c in
738 let lemma dom (j: int63) : unit
739 ensures { Set.mem j a.b.SBDD.dom_indexes -> Set.mem j cs }
740 = if Set.mem j a.b.SBDD.dom_indexes && to_int j >= to_int s then
741 numbits_high_clear a.indexes (to_int j)
742 in
743 let r = SBDD.cofactor a.b !c in
744 assert { forall j. not (Set.mem j r.SBDD.dom_indexes) };
745 assert { r.SBDD.dom_indexes = Set.empty };
746 assert { forall j. not (Set.mem j (to_indexes 0)) };
747 assert { to_indexes 0 = Set.empty };
748 let res = { b = r; indexes = 0 } in
749 let lemma value (id: indexes) (sn: snodes) : unit
750 ensures { res.v id sn <-> a.v pos sn }
751 =
752 let ghost u = Set.union (Set.diff (to_indexes id) cs) (SBDD.get_cube_indexes !c) in
753 let ghost w = Set.union (Set.diff sn (SBDD.support_snodes !c)) (SBDD.get_cube_snodes !c) in
754 assert { forall x. Set.mem x w <-> sn x };
755 SBDD.support_dom a.b;
756 SBDD.support_exact a.b u (to_indexes (to_int pos)) w sn
757 in
758 res
759
Valid (578ms) (colibri2 35) (cvc4 5) (split_vc) (depth 1)
760 let partial exist_window (x: t) (s: int63) : t
761 requires { 0 <= s /\ numbits x.dom_indexes <= s }
762 ensures { result.dom_indexes = 0 }
763 ensures { Set.subset result.dom_snodes x.dom_snodes }
764 ensures { forall id sn. result.v id sn <-> exists p. 0 <= p /\ numbits p <= s /\ x.v p sn }
765 =
766 let c = ref (SBDD.cube_true ()) in
767 for i = 0 to s - 1 do
768 invariant { SBDD.is_support !c }
769 invariant { forall j: int63. Set.mem j (SBDD.support_indexes !c) <-> 0 <= j < i }
770 invariant { SBDD.support_snodes !c = Set.empty }
771 c := SBDD.support_union !c (SBDD.cube_index i)
772 done;
773 let ghost cs = SBDD.support_indexes !c in
774 let lemma dom (j: int63) : unit
775 ensures { Set.mem j x.b.SBDD.dom_indexes -> Set.mem j cs }
776 = if Set.mem j x.b.SBDD.dom_indexes && to_int j >= to_int s then
777 numbits_high_clear x.indexes (to_int j)
778 in
779 let r = SBDD.dexist !c x.b in
780 assert { forall j. not (Set.mem j r.SBDD.dom_indexes) };
781 assert { r.SBDD.dom_indexes = Set.empty };
782 assert { forall j. not (Set.mem j (to_indexes 0)) };
783 assert { to_indexes 0 = Set.empty };
784 let res = { b = r; indexes = 0 } in
785 let lemma value (id: indexes) (sn: snodes) : unit
786 ensures { res.v id sn <-> exists p. 0 <= p /\ numbits p <= s /\ x.v p sn }
787 =
788 let ghost sid = to_indexes id in
789 assert { forall sn'. SBDD.update_sn sn (SBDD.support_snodes !c) sn' = sn };
790 if pure { exists id' sn'. x.b.SBDD.v (SBDD.update_id sid cs id') (SBDD.update_sn sn (SBDD.support_snodes !c) sn') }
791 then begin
792 let ghost id' = any SBDD.indexes ensures { exists sn'. x.b.SBDD.v (SBDD.update_id sid cs result) (SBDD.update_sn sn (SBDD.support_snodes !c) sn') } in
793 let ghost u = SBDD.update_id sid cs id' in
794 mask_nonneg (to_int s);
795 mask_numbits (to_int s);
796 let ghost p = from_indexes (Set.inter u cs) (mask (to_int s)) in
797 SBDD.support_dom x.b;
798 SBDD.support_exact x.b (to_indexes p) u sn sn;
799 assert { x.v p sn }
800 end else begin
801 let lemma no (p: int) : unit
802 requires { 0 <= p /\ numbits p <= s }
803 ensures { not x.v p sn }
804 =
805 SBDD.support_dom x.b;
806 SBDD.support_exact x.b (SBDD.update_id sid cs (to_indexes p)) (to_indexes p) sn sn;
807 assert { forall sn'. not (x.b.SBDD.v (SBDD.update_id sid cs (to_indexes p))
808 (SBDD.update_sn sn (SBDD.support_snodes !c) sn')) };
809 assert { SBDD.update_sn sn (SBDD.support_snodes !c) sn = sn };
810 assert { not (x.b.SBDD.v (SBDD.update_id sid cs (to_indexes p)) sn) }
811 in ()
812 end
813 in
814 res
815
Valid (824ms) (colibri2 17) (cvc4 4) (split_vc) (depth 1)
816 let partial forall_snodes (x: t) : t
817 ensures { result.dom_indexes = x.dom_indexes }
818 ensures { support_snodes result = Set.empty }
819 ensures { forall id sn. result.v id sn <-> forall sn'. x.v id sn' }
820 =
821 let c = snodes_cube (vars x) in
822 let r = SBDD.dforall c x.b in
823 let lemma memc (nd: snode) : unit
824 ensures { Set.mem nd (SBDD.support_snodes c) <-> Set.mem nd (SBDD.support_snodes x.b) }
825 = assert { nd = { n = nd.n; s = nd.s; scal = nd.scal } }
826 in
827 assert { forall nd. (SBDD.support_snodes c) nd = (SBDD.support_snodes x.b) nd };
828 assert { (SBDD.support_snodes c) = (SBDD.support_snodes x.b) };
829 assert { r.SBDD.dom_indexes = x.b.SBDD.dom_indexes };
830 let res = { b = r; indexes = x.indexes } in
831 let lemma value (id: indexes) (sn: snodes) : unit
832 ensures { res.v id sn <-> forall sn'. x.v id sn' }
833 =
834 let ghost sid = to_indexes id in
835 assert { res.v id sn <-> forall id' sn'. x.b.SBDD.v (SBDD.update_id sid (SBDD.support_indexes c) id')
836 (SBDD.update_sn sn (SBDD.support_snodes c) sn') };
837 assert { forall id'. SBDD.update_id sid (SBDD.support_indexes c) id' = sid };
838 let lemma upd (sn': snodes) : unit
839 ensures { x.b.SBDD.v sid (SBDD.update_sn sn (SBDD.support_snodes c) sn') = x.v id sn' }
840 = SBDD.support_exact x.b sid sid (SBDD.update_sn sn (SBDD.support_snodes x.b) sn') sn'
841 in
842 if pure { not (forall sn'. x.v id sn') } then begin
843 let ghost w = any snodes ensures { not (x.v id result) } in
844 upd w;
845 assert { not (x.b.SBDD.v (SBDD.update_id sid (SBDD.support_indexes c) sid) (SBDD.update_sn sn (SBDD.support_snodes c) w)) }
846 end
847 in
848 no_snode res;
849 res
850
851 predicate mem_key (nd: snode) (l: list (snode, t)) =
852 match l with Nil -> false | Cons (nd', _) l' -> nd = nd' \/ mem_key nd l' end
853
854 predicate distinct_keys (l: list (snode, t)) =
855 match l with Nil -> true | Cons (nd, _) l' -> not (mem_key nd l') /\ distinct_keys l' end
856
857 function subst_sn (l: list (snode, t)) (id: indexes) (sn: snodes) : snodes =
858 match l with
859 | Nil -> sn
860 | Cons (nd, f) l' -> Map.set (subst_sn l' id sn) nd (f.v id sn)
861 end
862
Valid (156ms) (colibri2)
863 let rec conv (l: list (snode, t)) : list (snode, SBDD.t)
864 variant { l }
865 ensures { forall nd. SBDDShift.mem_key nd result <-> mem_key nd l }
866 ensures { distinct_keys l -> SBDDShift.distinct_keys result }
867 ensures { forall id sn. SBDDShift.subst_sn result (to_indexes id) sn = subst_sn l id sn }
868 ensures { forall nd g. Mem.mem (nd, g) result -> exists f. Mem.mem (nd, f) l /\ g = f.b }
869 = match l with
870 | Nil -> Nil
871 | Cons (nd, f) l' -> Cons (nd, f.b) (conv l')
872 end
873
Valid (527ms) (colibri2 13) (cvc4 4) (split_vc) (depth 1)
874 let partial compose_snodes (ghost w: int) (l: list (snode, t)) (x: t) : t
875 requires { distinct_keys l }
876 requires { 0 <= w <= Int63.max_int + 1 /\ numbits x.dom_indexes <= w }
877 requires { forall nd f. Mem.mem (nd, f) l -> numbits f.dom_indexes <= w }
878 ensures { numbits result.dom_indexes <= w }
879 ensures { forall id sn. result.v id sn = x.v id (subst_sn l id sn) }
880 =
881 let cl = conv l in
882 let r = SBDDShift.compose_snodes cl x.b in
883 let ghost wit = mask w in
884 mask_nonneg w;
885 mask_numbits w;
886 let lemma sub (i: int63) : unit
887 requires { Set.mem i r.SBDD.dom_indexes }
888 ensures { to_indexes wit i }
889 =
890 if Set.mem i x.b.SBDD.dom_indexes then begin
891 if to_int i >= w then numbits_high_clear x.indexes (to_int i)
892 end else begin
893 assert { exists nd g. Mem.mem (nd, g) cl /\ Set.mem i g.SBDD.dom_indexes };
894 assert { exists nd f. Mem.mem (nd, f) l /\ bittest f.indexes i };
895 if to_int i >= w then
896 assert { forall nd f. Mem.mem (nd, f) l -> not (bittest f.indexes i) by
897 numbits f.indexes <= w }
898 end
899 in
900 { b = r; indexes = from_indexes r.SBDD.dom_indexes wit }
901
902 type inspect = Bool bool | IteIndex int63 t t | IteSnode snode t t
The PBDD of a sub–BDD of a
Valid (50ms) (colibri2)
905 let sub (a:t) (th:SBDD.t) : t
906 requires { Set.subset th.SBDD.dom_indexes a.b.SBDD.dom_indexes }
907 ensures { result.b = th }
908 = { b = th; indexes = from_indexes th.SBDD.dom_indexes a.indexes }
909
Valid (638ms) (colibri2 49) (cvc4 3) (split_vc 8) (depth 3)
910 let inspect (a:t) : inspect
911 ensures { match result with
912 | Bool b -> a.v = (fun _ _ -> b) /\ support_snodes a = Set.empty
913 | IteIndex i th el ->
914 Set.subset (support_snodes th) (support_snodes a) /\
915 Set.subset (support_snodes el) (support_snodes a) /\
916 0 <= to_int i /\ Zbit.bittest a.dom_indexes i /\
917 Zbit.subset th.dom_indexes (Zbit.unset a.dom_indexes i) /\
918 Zbit.subset el.dom_indexes (Zbit.unset a.dom_indexes i) /\
919 Set.subset th.dom_snodes a.dom_snodes /\
920 Set.subset el.dom_snodes a.dom_snodes /\
921 0 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\
922 a.v = (fun id sn -> if Zbit.bittest id i then th.v id sn else el.v id sn)
923 | IteSnode nd th el ->
924 Set.mem nd (support_snodes a) /\
925 Set.subset (support_snodes th) (Set.remove nd (support_snodes a)) /\
926 Set.subset (support_snodes el) (Set.remove nd (support_snodes a)) /\
927 Set.mem nd a.dom_snodes /\
928 Zbit.subset th.dom_indexes a.dom_indexes /\
929 Zbit.subset el.dom_indexes a.dom_indexes /\
930 Set.subset th.dom_snodes (Set.remove nd a.dom_snodes) /\
931 Set.subset el.dom_snodes (Set.remove nd a.dom_snodes) /\
932 0 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\
933 a.v = (fun id sn -> if sn nd then th.v id sn else el.v id sn)
934 end }
935 =
936 match SBDD.inspect a.b with
937 | SBDD.Bool b -> Bool b
938 | SBDD.IteIndex i th el ->
939 let th' = sub a th in
940 let el' = sub a el in
941 let ghost u = Zbit.unset a.indexes (to_int i) in
942 unset_nonneg a.indexes (to_int i);
943 let lemma unset_bits (j: int) : unit
944 ensures { bittest u j <-> (j <> to_int i /\ bittest a.indexes j) }
945 = if 0 <= j then begin
946 def_asr 1 (- to_int i) j;
947 assert { bittest (lsl 1 i) j <-> j = to_int i }
948 end
949 in
950 assert { forall j: int63. Set.mem j (to_indexes u) <-> (j <> i /\ Set.mem j (to_indexes a.indexes)) };
951 to_indexes_subset th'.indexes u;
952 to_indexes_subset el'.indexes u;
953 IteIndex i th' el'
954 | SBDD.IteSnode nd th el -> IteSnode nd (sub a th) (sub a el)
955 end
956
Valid (370ms) (colibri2 12) (cvc4) (cvc5) (split_vc) (depth 1)
957 let partial compose_index (i: int63) (f a: t) : t
958 requires { 0 <= to_int i }
959 ensures { result.dom_indexes = (Zbit.lor f.dom_indexes (Zbit.unset a.dom_indexes (to_int i))) }
960 ensures { result.dom_snodes = Set.union f.dom_snodes a.dom_snodes }
961 ensures { result.v = (fun id sn -> a.v (Zbit.change id (to_int i) (f.v id sn)) sn) } =
962 let ghost u = Zbit.unset a.indexes (to_int i) in
963 let lemma unset_bits (j: int) : unit
964 ensures { bittest u j <-> (j <> to_int i /\ bittest a.indexes j) }
965 = if 0 <= j then begin
966 def_asr 1 (- to_int i) j;
967 assert { bittest (lsl 1 i) j <-> j = to_int i }
968 end
969 in
970 assert { forall j: int63. Set.mem j (to_indexes u) <-> (j <> i /\ Set.mem j (to_indexes a.indexes)) };
971 assert { forall j: int63. to_indexes u j = Set.remove i (to_indexes a.indexes) j };
972 assert { to_indexes u = Set.remove i (to_indexes a.indexes) };
973 assert { to_indexes (Zbit.lor f.indexes u) = Set.union (to_indexes f.indexes) (to_indexes u) };
974 let res = { b = SBDD.compose_index i f.b a.b; indexes = Zbit.lor f.indexes (Zbit.unset a.indexes (to_int i)) } in
975 assert { forall id sn. res.v id sn
976 = (a.v (Zbit.change id (to_int i) (f.v id sn)) sn) };
977 res
978
979end