Common — library colibrilib.sbdd — module SBDDShift
1574
module SBDDShift

Implemented

1575
use mach.int.Int63
1576
use int.Int
1577
use list.List
1578
use list.Mem
1579
use list.Distinct
1580
use set.Set
1581
use colibrilib.bdd.Node
1582
use SNode
1583
use colibrilib.bdd.Key
1584
use colibrilib.bdd.IArray63
1585
use SBDD

The substitution of the keys of l: the index i by subst i and the snode nd by shift_snode nd off, evaluated on id, sn

1590
function
mix_id
(subst: IArray63.t t) (l: list Key.t) (id: indexes) (sn: snodes) (id': indexes) : indexes =
1591
fun i -> if Mem.mem (Index i) l then (subst i).v id sn else id' i
1592
function
mix_sn
(off: int) (l: list Key.t) (sn sn': snodes) : snodes =
1593
fun nd -> if Mem.mem (Var nd.n nd.s nd.scal) l then sn (shift_snode nd off) else sn' nd Valid (295ms) (cvc4)
1594
let lemma
mix_index
(subst: IArray63.t t) (off: int) (i: index) (l: list Key.t)
1595
(id: indexes) (sn: snodes) : unit
1596
requires { not (Mem.mem (Index i) l) }
1597
ensures { Map.set (mix_id subst l id sn id) i ((subst i).v id sn) = mix_id subst (Cons (Index i) l) id sn id }
1598
ensures { mix_sn off l sn sn = mix_sn off (Cons (Index i) l) sn sn }
1599
= ()
1600
Valid (330ms) (cvc4)
1601
let lemma
mix_snode
(subst: IArray63.t t) (off: int) (nd: snode) (l: list Key.t)
1602
(id: indexes) (sn: snodes) : unit
1603
requires { not (Mem.mem (Var nd.n nd.s nd.scal) l) }
1604
ensures { mix_id subst l id sn id = mix_id subst (Cons (Var nd.n nd.s nd.scal) l) id sn id }
1605
ensures { Map.set (mix_sn off l sn sn) nd (sn (shift_snode nd off)) = mix_sn off (Cons (Var nd.n nd.s nd.scal) l) sn sn }
1606
= ()

The substitution of the keys of l. Differs from bddbitv.ml: built from the end of the list (the vector type is mutable, so a result must be fresh); same cost.

    Valid (506ms) (colibri2 35) (cvc5 2) (split_vc) (depth 1)
1611
let rec partial
add_vars
(subst: IArray63.t t) (off: int63) (l: list Key.t) : Vector.vector
1612
requires { Distinct.distinct l }
1613
requires { forall i. Mem.mem (Index i) l -> 0 <= i < subst.length }
1614
variant { l }
1615
ensures { forall n s a. Mem.mem (Var n s a) l -> a \/ in_bounds (to_int s - to_int off) }
1616
ensures { forall i. Set.mem i result.Vector.removed_indexes <-> Mem.mem (Index i) l }
1617
ensures { forall nd. Set.mem nd result.Vector.removed_snodes <-> Mem.mem (Var nd.n nd.s nd.scal) l }
1618
ensures { forall i. Set.mem i result.Vector.added_indexes ->
1619
exists j. Mem.mem (Index j) l /\ Set.mem i (subst j).dom_indexes }
1620
ensures { forall nd. Set.mem nd result.Vector.added_snodes ->
1621
(exists j. Mem.mem (Index j) l /\ Set.mem nd (subst j).dom_snodes) \/
1622
(exists nd'. Mem.mem (Var nd'.n nd'.s nd'.scal) l /\ nd = shift_snode nd' off) }
1623
ensures { forall a id sn. Vector.subst result a id sn = a (mix_id subst l id sn id) (mix_sn off l sn sn) }
1624
raises { Overflow -> exists n s. Mem.mem (Var n s False) l /\ not (in_bounds (to_int s - to_int off)) }
1625
= match l with
1626
| Nil ->
1627
let lemma nil (id: indexes) (sn: snodes) : unit
1628
ensures { mix_id subst Nil id sn id = id /\ mix_sn off Nil sn sn = sn }
1629
=
1630
assert { forall i. mix_id subst Nil id sn id i = id i };
1631
assert { forall nd. mix_sn off Nil sn sn nd = sn nd }
1632
in
1633
Vector.create ()
1634
| Cons (Index i) l' ->
1635
let vec = add_vars subst off l' in
1636
let r = Vector.add_index vec i (IArray63.get subst i) in
1637
let lemma step (a: indexes -> snodes -> bool) (id: indexes) (sn: snodes) : unit
1638
ensures { Vector.subst r a id sn = a (mix_id subst l id sn id) (mix_sn off l sn sn) }
1639
= mix_index subst (to_int off) i l' id sn
1640
in
1641
r
1642
| Cons (Var n s a) l' ->
1643
let vec = add_vars subst off l' in
1644
let nd = { n = n; s = s; scal = a } in
1645
let nd' = shift_snode_checked nd off in
1646
let r = Vector.add_snode vec nd (bdd_of_snode nd') in
1647
let lemma step (a: indexes -> snodes -> bool) (id: indexes) (sn: snodes) : unit
1648
ensures { Vector.subst r a id sn = a (mix_id subst l id sn id) (mix_sn off l sn sn) }
1649
= mix_snode subst (to_int off) nd l' id sn
1650
in
1651
r
1652
end

Substitution of shift_left_gen: the index i by subst i and the snode nd by shift_snode nd off

    Valid (630ms) (colibri2 10) (cvc4) (split_vc) (depth 1)
1656
let partial
compose_shift
(subst: IArray63.t t) (off: int63) (x: t) : t
1657
requires { forall i. Set.mem i (support_indexes x) -> 0 <= i < subst.length }
1658
ensures { forall nd. Set.mem nd (support_snodes x) -> nd.scal \/ in_bounds (to_int nd.s - to_int off) }
1659
ensures { forall i. Set.mem i result.dom_indexes ->
1660
Set.mem i x.dom_indexes \/
1661
exists j. 0 <= j < subst.length /\ Set.mem i (subst j).dom_indexes }
1662
ensures { forall nd. Set.mem nd result.dom_snodes ->
1663
Set.mem nd x.dom_snodes \/
1664
(exists j. 0 <= j < subst.length /\ Set.mem nd (subst j).dom_snodes) \/
1665
(exists nd'. Set.mem nd' (support_snodes x) /\ nd = shift_snode nd' off) }
1666
ensures { forall id sn. result.v id sn =
1667
x.v (fun (i:int63) -> if 0 <= i < subst.length then (subst i).v id sn else id i)
1668
(fun nd -> sn (shift_snode nd off)) }
1669
raises { Overflow -> exists nd. Set.mem nd (support_snodes x) /\ not nd.scal /\ not (in_bounds (to_int nd.s - to_int off)) }
1670
=
1671
let l = vars x in
1672
let r = Vector.compose (add_vars subst off l) x in
1673
let lemma pt (id: indexes) (sn: snodes) : unit
1674
ensures { r.v id sn =
1675
x.v (fun (i:int63) -> if 0 <= i < subst.length then (subst i).v id sn else id i)
1676
(fun nd -> sn (shift_snode nd off)) }
1677
=
1678
assert { r.v id sn = x.v (mix_id subst l id sn id) (mix_sn off l sn sn) };
1679
support_exact x pure { mix_id subst l id sn id }
1680
pure { fun (i:int63) -> if 0 <= i < subst.length then (subst i).v id sn else id i }
1681
pure { mix_sn off l sn sn } pure { fun nd -> sn (shift_snode nd off) }
1682
in
1683
r

Substitution of snodes by BDDs (Var.subst restricted to snodes)

1686
predicate
mem_key
(nd: snode) (l: list (snode, t)) =
1687
match l with Nil -> false | Cons (nd', _) l' -> nd = nd' \/ mem_key nd l' end
1688
1689
predicate
distinct_keys
(l: list (snode, t)) =
1690
match l with Nil -> true | Cons (nd, _) l' -> not (mem_key nd l') /\ distinct_keys l' end

The valuation of the snodes after the (simultaneous) substitution l

1693
function
subst_sn
(l: list (snode, t)) (id: indexes) (sn: snodes) : snodes =
1694
match l with
1695
| Nil -> sn
1696
| Cons (nd, f) l' -> Map.set (subst_sn l' id sn) nd (f.v id sn)
1697
end
1698
Valid (527ms) (colibri2 11) (cvc4) (split_vc) (depth 1)
1699
let rec partial
add_snodes
(l: list (snode, t)) : Vector.vector
1700
requires { distinct_keys l }
1701
variant { l }
1702
ensures { result.Vector.removed_indexes = Set.empty }
1703
ensures { forall nd. Set.mem nd result.Vector.removed_snodes <-> mem_key nd l }
1704
ensures { forall i. Set.mem i result.Vector.added_indexes ->
1705
exists nd f. Mem.mem (nd, f) l /\ Set.mem i f.dom_indexes }
1706
ensures { forall a id sn. Vector.subst result a id sn = a id (subst_sn l id sn) }
1707
= match l with
1708
| Nil ->
1709
let lemma nil (a: indexes -> snodes -> bool) (id: indexes) (sn: snodes) : unit
1710
ensures { a id sn = a id (subst_sn Nil id sn) }
1711
= ()
1712
in
1713
Vector.create ()
1714
| Cons (nd, f) l' ->
1715
let vec = add_snodes l' in
1716
Vector.add_snode vec nd f
1717
end
1718
Valid (139ms) (colibri2)
1719
let partial
compose_snodes
(l: list (snode, t)) (x: t) : t
1720
requires { distinct_keys l }
1721
ensures { forall i. Set.mem i result.dom_indexes ->
1722
Set.mem i x.dom_indexes \/ exists nd f. Mem.mem (nd, f) l /\ Set.mem i f.dom_indexes }
1723
ensures { forall id sn. result.v id sn = x.v id (subst_sn l id sn) }
1724
= Vector.compose (add_snodes l) x
1725
end