Common — library colibrilib.sbdd — module SBDD_intf
587
module SBDD_intf

Abstract

588
use mach.int.Int63
589
use int.Int
590
use list.List
591
use list.Mem
592
use list.Distinct
593
use set.Set
594
use bool.Bool
595
use colibrilib.bdd.Node
596
use SNode
597
use colibrilib.bdd.Key
598
599
type
t
600
type
index
= int63
601
type
indexes
= Set.set index
602
type
snodes
= Set.set snode
603
function
dom_indexes
(x:t) : indexes
604
function
dom_snodes
(x:t) : snodes
605
function
v
(x:t): indexes -> snodes -> bool
606
predicate
is_cube
(cb:t)
607
predicate
is_support
(cb:t)
608
609
function
update_id
(id: indexes) (s: indexes) (id': indexes) : indexes =
610
(fun i -> if s i then id' i else id i)
611
function
update_sn
(sn: snodes) (s: snodes) (sn': snodes) : snodes =
612
(fun i -> if s i then sn' i else sn i)
613
function
get_cube_indexes
(cb: t) : indexes
614
function
get_cube_snodes
(cb: t) : snodes
615
Valid (74ms) (colibri2)
616
axiom
support_v
: forall x id1 id2 sn1 sn2.
617
(forall i. Set.mem i x.dom_indexes -> id1 i = id2 i) ->
618
(forall s. Set.mem s x.dom_snodes -> sn1 s = sn2 s) ->
619
x.v id1 sn1 = x.v id2 sn2
620
Valid (79ms) (colibri2)
621
val
dand
(x y: t) : t
622
ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }
623
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
624
ensures { result.v = (fun id sn -> andb (x.v id sn) (y.v id sn)) }
625
Valid (78ms) (colibri2)
626
val
dor
(x y: t) : t
627
ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }
628
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
629
ensures { result.v = (fun id sn -> orb (x.v id sn) (y.v id sn)) }
630
Valid (79ms) (colibri2)
631
val
dxor
(x y: t) : t
632
ensures { result.dom_indexes = Set.union x.dom_indexes y.dom_indexes }
633
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
634
ensures { result.v = (fun id sn -> xorb (x.v id sn) (y.v id sn)) }
635
Valid (85ms) (colibri2)
636
val
tfalse
() : t
637
ensures { result.dom_indexes = Set.empty }
638
ensures { result.dom_snodes = Set.empty }
639
ensures { result.v = (fun _ _ -> false) }
640
Valid (77ms) (colibri2)
641
val
ttrue
() : t
642
ensures { result.dom_indexes = Set.empty }
643
ensures { result.dom_snodes = Set.empty }
644
ensures { result.v = (fun _ _ -> true) }
645
Valid (82ms) (colibri2)
646
val
dnot
(a: t) : t
647
ensures { result.dom_indexes = a.dom_indexes }
648
ensures { result.dom_snodes = a.dom_snodes }
649
ensures { result.v = (fun id sn -> notb (a.v id sn)) }
650
Valid (79ms) (colibri2)
651
val
is_equal
(x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)
652
ensures { result = (forall id sn. x.v id sn = y.v id sn) }
653
ensures { not result ->
654
((Set.subset wid (Set.union x.dom_indexes y.dom_indexes)) /\
655
(Set.subset wsn (Set.union x.dom_snodes y.dom_snodes)) /\
656
x.v wid wsn <> y.v wid wsn) }
657
Valid (82ms) (colibri2)
658
val
is_inter_empty
(x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)
659
ensures { result = (forall id sn. not (x.v id sn /\ y.v id sn)) }
660
ensures { not result ->
661
(Set.subset wid (Set.union x.dom_indexes y.dom_indexes)) /\
662
(Set.subset wsn (Set.union x.dom_snodes y.dom_snodes)) /\
663
x.v wid wsn /\ y.v wid wsn }
664
Valid (52ms) (colibri2)
665
val partial
bdd_of_index
(i: index) : t
666
ensures { result.dom_indexes = Set.singleton i }
667
ensures { result.dom_snodes = Set.empty }
668
ensures { result.v = (fun id _ -> id i) }
669
Valid (69ms) (colibri2)
670
val partial
bdd_of_snode
(v: snode) : t
671
ensures { result.dom_indexes = Set.empty }
672
ensures { result.dom_snodes = Set.singleton v }
673
ensures { result.v = (fun _ sn -> sn v) }
674
Valid (60ms) (colibri2)
675
val partial
bdd_not_index
(i: index) : t
676
ensures { result.dom_indexes = Set.singleton i }
677
ensures { result.dom_snodes = Set.empty }
678
ensures { result.v = (fun id _ -> not (id i)) }
679
Valid (58ms) (colibri2)
680
val partial
bdd_not_snode
(v: snode) : t
681
ensures { result.dom_indexes = Set.empty }
682
ensures { result.dom_snodes = Set.singleton v }
683
ensures { result.v = (fun _ sn -> not (sn v)) }
684
Valid (76ms) (colibri2)
685
val partial
ite_index
(i: index) (aa bb: t) : t
686
ensures { result.dom_indexes = Set.add i (Set.union aa.dom_indexes bb.dom_indexes) }
687
ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }
688
ensures { result.v = (fun id sn -> if id i then aa.v id sn else bb.v id sn) }

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

724
function
support_indexes
(a:t) : indexes
725
function
support_snodes
(a:t) : snodes
726
Valid (78ms) (colibri2)
727
axiom
support_dom
: forall x.
728
Set.subset (support_indexes x) x.dom_indexes /\ Set.subset (support_snodes x) x.dom_snodes
729
Valid (89ms) (colibri2)
730
axiom
support_exact
: forall x id1 id2 sn1 sn2.
731
(forall i. Set.mem i (support_indexes x) -> id1 i = id2 i) ->
732
(forall s. Set.mem s (support_snodes x) -> sn1 s = sn2 s) ->
733
x.v id1 sn1 = x.v id2 sn2

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

756
predicate
good_cube
(cb: t) =
757
is_cube cb /\ Set.subset (get_cube_indexes cb) (support_indexes cb) /\
758
Set.subset (get_cube_snodes cb) (support_snodes cb)
759
Valid (80ms) (colibri2)
760
axiom
cube_empty_good
: forall x. is_support x -> support_indexes x = Set.empty ->
761
support_snodes x = Set.empty ->
762
good_cube x /\ get_cube_indexes x = Set.empty /\ get_cube_snodes x = Set.empty

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

876
function
upd_index
(a: indexes -> snodes -> bool) (i: index) (b: bool) : indexes -> snodes -> bool =
877
fun id sn -> a (Map.set id i b) sn
878
function
upd_snode
(a: indexes -> snodes -> bool) (sn0: snode) (b: bool) : indexes -> snodes -> bool =
879
fun id sn -> a id (Map.set sn sn0 b)
880
Valid (75ms) (colibri2)
881
val
create
() : vector
882
ensures { result.removed_indexes = Set.empty }
883
ensures { result.removed_snodes = Set.empty }
884
ensures { result.added_indexes = Set.empty }
885
ensures { result.added_snodes = Set.empty }
886
ensures { result.subst = (fun a -> a) }
887
Valid (74ms) (colibri2)
888
val partial
add_index
(v: vector) (i: index) (f: t) : vector
889
requires { not (Set.mem i v.removed_indexes) }
890
ensures { result.removed_indexes = Set.add i v.removed_indexes }
891
ensures { result.removed_snodes = v.removed_snodes }
892
ensures { result.added_indexes = Set.union v.added_indexes f.dom_indexes }
893
ensures { result.added_snodes = Set.union v.added_snodes f.dom_snodes }
894
ensures { result.subst = (fun a id sn -> v.subst (upd_index a i (f.v id sn)) id sn) }
895
Valid (78ms) (colibri2)
896
val partial
add_snode
(v: vector) (sn0: snode) (f: t) : vector
897
requires { not (Set.mem sn0 v.removed_snodes) }
898
ensures { result.removed_indexes = v.removed_indexes }
899
ensures { result.removed_snodes = Set.add sn0 v.removed_snodes }
900
ensures { result.added_indexes = Set.union v.added_indexes f.dom_indexes }
901
ensures { result.added_snodes = Set.union v.added_snodes f.dom_snodes }
902
ensures { result.subst = (fun a id sn -> v.subst (upd_snode a sn0 (f.v id sn)) id sn) }
903
Valid (60ms) (colibri2)
904
val
compose
(v: vector) (a: t) : t
905
ensures { result.dom_indexes = Set.union v.added_indexes (Set.diff a.dom_indexes v.removed_indexes) }
906
ensures { result.dom_snodes = Set.union v.added_snodes (Set.diff a.dom_snodes v.removed_snodes) }
907
ensures { result.v = v.subst a.v }
908
end
909
910
end