library colibrilib.sbdd — module SBDD_intfmodule SBDD_intf587
Abstract
use mach.int.Int63588use int.Int589use list.List590use list.Mem591use list.Distinct592use set.Set593use bool.Bool594use colibrilib.bdd.Node595use SNode596use colibrilib.bdd.Key597598type t599type index = int63600type indexes = Set.set index601type snodes = Set.set snode602function dom_indexes (x:t) : indexes603function dom_snodes (x:t) : snodes604function v (x:t): indexes -> snodes -> bool605predicate is_cube (cb:t)606predicate is_support (cb:t)607608function update_id (id: indexes) (s: indexes) (id': indexes) : indexes =609(fun i -> if s i then id' i else id i)610function update_sn (sn: snodes) (s: snodes) (sn': snodes) : snodes =611(fun i -> if s i then sn' i else sn i)612function get_cube_indexes (cb: t) : indexes613function get_cube_snodes (cb: t) : snodes614Valid (74ms) (colibri2)615axiom support_v: forall x id1 id2 sn1 sn2.616(forall i. Set.mem i x.dom_indexes -> id1 i = id2 i) ->617(forall s. Set.mem s x.dom_snodes -> sn1 s = sn2 s) ->618x.v id1 sn1 = x.v id2 sn2619Valid (79ms) (colibri2)620val dand (x y: t) : t621ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }622ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }623ensures { result.v = (fun id sn -> andb (x.v id sn) (y.v id sn)) }624Valid (78ms) (colibri2)625val dor (x y: t) : t626ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }627ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }628ensures { result.v = (fun id sn -> orb (x.v id sn) (y.v id sn)) }629Valid (79ms) (colibri2)630val dxor (x y: t) : t631ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }632ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }633ensures { result.v = (fun id sn -> xorb (x.v id sn) (y.v id sn)) }634Valid (85ms) (colibri2)635val tfalse () : t636ensures { result.dom_indexes = Set.empty }637ensures { result.dom_snodes = Set.empty }638ensures { result.v = (fun _ _ -> false) }639Valid (77ms) (colibri2)640val ttrue () : t641ensures { result.dom_indexes = Set.empty }642ensures { result.dom_snodes = Set.empty }643ensures { result.v = (fun _ _ -> true) }644Valid (82ms) (colibri2)645val dnot (a: t) : t646ensures { result.dom_indexes = a.dom_indexes }647ensures { result.dom_snodes = a.dom_snodes }648ensures { result.v = (fun id sn -> notb (a.v id sn)) }649Valid (79ms) (colibri2)650val is_equal (x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)651ensures { result = (forall id sn. x.v id sn = y.v id sn) }652ensures { not result ->653((Set.subset wid (Set.union x.dom_indexes y.dom_indexes)) /\654(Set.subset wsn (Set.union x.dom_snodes y.dom_snodes)) /\655x.v wid wsn <> y.v wid wsn) }656Valid (82ms) (colibri2)657val is_inter_empty (x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)658ensures { result = (forall id sn. not (x.v id sn /\ y.v id sn)) }659ensures { not result ->660(Set.subset wid (Set.union x.dom_indexes y.dom_indexes)) /\661(Set.subset wsn (Set.union x.dom_snodes y.dom_snodes)) /\662x.v wid wsn /\ y.v wid wsn }663Valid (52ms) (colibri2)664val partial bdd_of_index (i: index) : t665ensures { result.dom_indexes = Set.singleton i }666ensures { result.dom_snodes = Set.empty }667ensures { result.v = (fun id _ -> id i) }668Valid (69ms) (colibri2)669val partial bdd_of_snode (v: snode) : t670ensures { result.dom_indexes = Set.empty }671ensures { result.dom_snodes = Set.singleton v }672ensures { result.v = (fun _ sn -> sn v) }673Valid (60ms) (colibri2)674val partial bdd_not_index (i: index) : t675ensures { result.dom_indexes = Set.singleton i }676ensures { result.dom_snodes = Set.empty }677ensures { result.v = (fun id _ -> not (id i)) }678Valid (58ms) (colibri2)679val partial bdd_not_snode (v: snode) : t680ensures { result.dom_indexes = Set.empty }681ensures { result.dom_snodes = Set.singleton v }682ensures { result.v = (fun _ sn -> not (sn v)) }683Valid (76ms) (colibri2)684val partial ite_index (i: index) (aa bb: t) : t685ensures { result.dom_indexes = Set.add i (Set.union aa.dom_indexes bb.dom_indexes) }686ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }687ensures { result.v = (fun id sn -> if id i then aa.v id sn else bb.v id sn) }688
ite_index for the indexes 0, 1, 2, in ghost code
Valid (27ms) (colibri2)
691 val ghost ite_index_g (i: index) (aa bb: t) : t
692 requires { 0 <= i < 3 }
693 ensures { result.dom_indexes = Set.add i (Set.union aa.dom_indexes bb.dom_indexes) }
694 ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }
695 ensures { result.v = (fun id sn -> if id i then aa.v id sn else bb.v id sn) }
696
Valid (73ms) (colibri2)
697 val partial ite_snode (v: snode) (aa bb: t) : t
698 ensures { result.dom_indexes = Set.union aa.dom_indexes bb.dom_indexes }
699 ensures { result.dom_snodes = Set.add v (Set.union aa.dom_snodes bb.dom_snodes) }
700 ensures { result.v = (fun id sn -> if sn v then aa.v id sn else bb.v id sn) }
701
Valid (62ms) (colibri2)
702 val partial cofactors_index (i: index) (a: t) : (t, t)
703 returns { (p, n) ->
704 p.dom_indexes = Set.remove i a.dom_indexes /\
705 n.dom_indexes = Set.remove i a.dom_indexes /\
706 p.dom_snodes = a.dom_snodes /\
707 n.dom_snodes = a.dom_snodes /\
708 p.v = (fun id sn -> a.v (Set.add i id) sn) /\
709 n.v = (fun id sn -> a.v (Set.remove i id) sn) }
710
Valid (71ms) (colibri2)
711 val partial cofactors_snode (v: snode) (a: t) : (t, t)
712 returns { (p, n) ->
713 p.dom_indexes = a.dom_indexes /\
714 n.dom_indexes = a.dom_indexes /\
715 p.dom_snodes = Set.remove v a.dom_snodes /\
716 n.dom_snodes = Set.remove v a.dom_snodes /\
717 p.v = (fun id sn -> a.v id (Set.add v sn)) /\
718 n.v = (fun id sn -> a.v id (Set.remove v sn)) }
719
720 function nb_nodes (a:t) : int
The variables of the BDD, included in the domain
function support_indexes (a:t) : indexes724function support_snodes (a:t) : snodes725Valid (78ms) (colibri2)726axiom support_dom: forall x.727Set.subset (support_indexes x) x.dom_indexes /\ Set.subset (support_snodes x) x.dom_snodes728Valid (89ms) (colibri2)729axiom support_exact: forall x id1 id2 sn1 sn2.730(forall i. Set.mem i (support_indexes x) -> id1 i = id2 i) ->731(forall s. Set.mem s (support_snodes x) -> sn1 s = sn2 s) ->732x.v id1 sn1 = x.v id2 sn2733
A snode of the support changes the value
Valid (88ms) (colibri2)
736 axiom support_snodes_dep: forall x nd. Set.mem nd (support_snodes x) ->
737 exists id sn. x.v id (Set.add nd sn) <> x.v id (Set.remove nd sn)
Cubes of positive literals, for dexist/dforall
Valid (77ms) (colibri2)
740 val cube_true () : t
741 ensures { result.dom_indexes = Set.empty /\ result.dom_snodes = Set.empty }
742 ensures { support_indexes result = Set.empty /\ support_snodes result = Set.empty }
743 ensures { is_support result }
744
Valid (79ms) (colibri2)
745 val partial cube_snode (nd: snode) : t
746 ensures { result.dom_indexes = Set.empty /\ result.dom_snodes = Set.singleton nd }
747 ensures { support_indexes result = Set.empty /\ support_snodes result = Set.singleton nd }
748 ensures { is_support result }
749
Valid (72ms) (colibri2)
750 val partial cube_index (i: index) : t
751 ensures { result.dom_indexes = Set.singleton i /\ result.dom_snodes = Set.empty }
752 ensures { support_indexes result = Set.singleton i /\ support_snodes result = Set.empty }
753 ensures { is_support result }
A cube whose positive literals are in its support
predicate good_cube (cb: t) =756is_cube cb /\ Set.subset (get_cube_indexes cb) (support_indexes cb) /\757Set.subset (get_cube_snodes cb) (support_snodes cb)758Valid (80ms) (colibri2)759axiom cube_empty_good: forall x. is_support x -> support_indexes x = Set.empty ->760support_snodes x = Set.empty ->761good_cube x /\ get_cube_indexes x = Set.empty /\ get_cube_snodes x = Set.empty762
The literal i (if b) or not i
Valid (78ms) (colibri2)
765 val partial cube_lit (i: index) (b: bool) : t
766 ensures { result.dom_indexes = Set.singleton i /\ result.dom_snodes = Set.empty }
767 ensures { support_indexes result = Set.singleton i /\ support_snodes result = Set.empty }
768 ensures { good_cube result }
769 ensures { get_cube_indexes result = (if b then Set.singleton i else Set.empty) }
770 ensures { get_cube_snodes result = Set.empty }
The conjunction of two cubes on disjoint variables
Valid (104ms) (colibri2)
773 val cube_and (x y: t) : t
774 requires { good_cube x /\ good_cube y }
775 requires { Set.inter (support_indexes x) (support_indexes y) = Set.empty }
776 requires { Set.inter (support_snodes x) (support_snodes y) = Set.empty }
777 ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }
778 ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
779 ensures { good_cube result }
780 ensures { support_indexes result = Set.union (support_indexes x) (support_indexes y) }
781 ensures { support_snodes result = Set.union (support_snodes x) (support_snodes y) }
782 ensures { get_cube_indexes result = Set.union (get_cube_indexes x) (get_cube_indexes y) }
783 ensures { get_cube_snodes result = Set.union (get_cube_snodes x) (get_cube_snodes y) }
Cudd.Bdd.support_union
Valid (60ms) (colibri2)
786 val support_union (x y: t) : t
787 requires { is_support x /\ is_support y }
788 ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }
789 ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
790 ensures { support_indexes result = Set.union (support_indexes x) (support_indexes y) }
791 ensures { support_snodes result = Set.union (support_snodes x) (support_snodes y) }
792 ensures { is_support result }
793
Valid (66ms) (colibri2)
794 val vars (a:t) : list Key.t
795 ensures { forall i. Mem.mem (Key.Index i) result <-> Set.mem i (support_indexes a) }
796 ensures { forall n s ab. Mem.mem (Key.Var n s ab) result <-> Set.mem { n = n; s = s; scal = ab } (support_snodes a) }
797 ensures { Distinct.distinct result }
798
799 type inspect = Bool bool | IteIndex index t t | IteSnode snode t t
Top node of the BDD
Valid (71ms) (colibri2)
802 val inspect (a:t) : inspect
803 ensures { match result with
804 | Bool b -> a.v = (fun _ _ -> b) /\
805 support_indexes a = Set.empty /\ support_snodes a = Set.empty
806 | IteIndex i th el ->
807 Set.mem i (support_indexes a) /\
808 Set.subset (support_indexes th) (Set.remove i (support_indexes a)) /\
809 Set.subset (support_indexes el) (Set.remove i (support_indexes a)) /\
810 Set.subset (support_snodes th) (support_snodes a) /\
811 Set.subset (support_snodes el) (support_snodes a) /\
812 Set.mem i a.dom_indexes /\
813 Set.subset th.dom_indexes (Set.remove i a.dom_indexes) /\
814 Set.subset el.dom_indexes (Set.remove i a.dom_indexes) /\
815 Set.subset th.dom_snodes a.dom_snodes /\
816 Set.subset el.dom_snodes a.dom_snodes /\
817 0 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\
818 a.v = (fun id sn -> if Set.mem i id then th.v id sn else el.v id sn)
819 | IteSnode nd th el ->
820 Set.mem nd (support_snodes a) /\
821 Set.subset (support_indexes th) (support_indexes a) /\
822 Set.subset (support_indexes el) (support_indexes a) /\
823 Set.subset (support_snodes th) (Set.remove nd (support_snodes a)) /\
824 Set.subset (support_snodes el) (Set.remove nd (support_snodes a)) /\
825 Set.mem nd a.dom_snodes /\
826 Set.subset th.dom_indexes a.dom_indexes /\
827 Set.subset el.dom_indexes a.dom_indexes /\
828 Set.subset th.dom_snodes (Set.remove nd a.dom_snodes) /\
829 Set.subset el.dom_snodes (Set.remove nd a.dom_snodes) /\
830 0 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\
831 a.v = (fun id sn -> if Set.mem nd sn then th.v id sn else el.v id sn)
832 end }
833
Valid (63ms) (colibri2)
834 val dexist (s x: t) : t
835 requires { is_support s }
836 ensures { result.dom_indexes = Set.diff x.dom_indexes (support_indexes s) }
837 ensures { result.dom_snodes = Set.diff x.dom_snodes (support_snodes s) }
838 ensures { result.v = (fun id sn ->
839 exists id' sn'. x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn')) }
840
Valid (63ms) (colibri2)
841 val dforall (s x: t) : t
842 requires { is_support s }
843 ensures { result.dom_indexes = Set.diff x.dom_indexes (support_indexes s) }
844 ensures { result.dom_snodes = Set.diff x.dom_snodes (support_snodes s) }
845 ensures { result.v = (fun id sn ->
846 forall id' sn'. x.v (update_id id (support_indexes s) id') (update_sn sn (support_snodes s) sn')) }
847
Valid (80ms) (colibri2)
848 val partial compose_index (i: index) (f a: t) : t
849 ensures { result.dom_indexes = Set.union f.dom_indexes (Set.remove i a.dom_indexes) }
850 ensures { result.dom_snodes = Set.union f.dom_snodes a.dom_snodes }
851 ensures { result.v = (fun id sn -> a.v (Map.set id i (f.v id sn)) sn) }
852
Valid (70ms) (colibri2)
853 val partial compose_snode (v: snode) (f a: t) : t
854 ensures { result.dom_indexes = Set.union f.dom_indexes a.dom_indexes }
855 ensures { result.dom_snodes = Set.union f.dom_snodes (Set.remove v a.dom_snodes) }
856 ensures { result.v = (fun id sn -> a.v id (Map.set sn v (f.v id sn))) }
857
Valid (64ms) (colibri2)
858 val cofactor (a cb: t) : t
859 requires { is_cube cb }
860 ensures { result.dom_indexes = Set.diff a.dom_indexes (support_indexes cb) }
861 ensures { result.dom_snodes = Set.diff a.dom_snodes (support_snodes cb) }
862 ensures { result.v = (fun id sn ->
863 a.v (Set.union (Set.diff id (support_indexes cb)) (get_cube_indexes cb))
864 (Set.union (Set.diff sn (support_snodes cb)) (get_cube_snodes cb))) }
865
866 scope Vector
867 type vector = abstract mutable { }
868
869 function removed_indexes (v:vector) : indexes
870 function removed_snodes (v:vector) : snodes
871 function added_indexes (v:vector) : indexes
872 function added_snodes (v:vector) : snodes
873 function subst (v:vector) : (indexes -> snodes -> bool) -> (indexes -> snodes -> bool)
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 =876fun id sn -> a (Map.set id i b) sn877function upd_snode (a: indexes -> snodes -> bool) (sn0: snode) (b: bool) : indexes -> snodes -> bool =878fun id sn -> a id (Map.set sn sn0 b)879Valid (75ms) (colibri2)880val create () : vector881ensures { result.removed_indexes = Set.empty }882ensures { result.removed_snodes = Set.empty }883ensures { result.added_indexes = Set.empty }884ensures { result.added_snodes = Set.empty }885ensures { result.subst = (fun a -> a) }886Valid (74ms) (colibri2)887val partial add_index (v: vector) (i: index) (f: t) : vector888requires { not (Set.mem i v.removed_indexes) }889ensures { result.removed_indexes = Set.add i v.removed_indexes }890ensures { result.removed_snodes = v.removed_snodes }891ensures { result.added_indexes = Set.union v.added_indexes f.dom_indexes }892ensures { result.added_snodes = Set.union v.added_snodes f.dom_snodes }893ensures { result.subst = (fun a id sn -> v.subst (upd_index a i (f.v id sn)) id sn) }894Valid (78ms) (colibri2)895val partial add_snode (v: vector) (sn0: snode) (f: t) : vector896requires { not (Set.mem sn0 v.removed_snodes) }897ensures { result.removed_indexes = v.removed_indexes }898ensures { result.removed_snodes = Set.add sn0 v.removed_snodes }899ensures { result.added_indexes = Set.union v.added_indexes f.dom_indexes }900ensures { result.added_snodes = Set.union v.added_snodes f.dom_snodes }901ensures { result.subst = (fun a id sn -> v.subst (upd_snode a sn0 (f.v id sn)) id sn) }902Valid (60ms) (colibri2)903val compose (v: vector) (a: t) : t904ensures { result.dom_indexes = Set.union v.added_indexes (Set.diff a.dom_indexes v.removed_indexes) }905ensures { result.dom_snodes = Set.union v.added_snodes (Set.diff a.dom_snodes v.removed_snodes) }906ensures { result.v = v.subst a.v }907end908909end910