library colibrilib.sbdd — module SBDDShiftmodule SBDDShift1574
Implemented
use mach.int.Int631575use int.Int1576use list.List1577use list.Mem1578use list.Distinct1579use set.Set1580use colibrilib.bdd.Node1581use SNode1582use colibrilib.bdd.Key1583use colibrilib.bdd.IArray631584use SBDD1585
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
function mix_id (subst: IArray63.t t) (l: list Key.t) (id: indexes) (sn: snodes) (id': indexes) : indexes =1590fun i -> if Mem.mem (Index i) l then (subst i).v id sn else id' i1591function mix_sn (off: int) (l: list Key.t) (sn sn': snodes) : snodes =1592fun nd -> if Mem.mem (Var nd.n nd.s nd.scal) l then sn (shift_snode nd off) else sn' nd Valid (295ms) (cvc4)1593let lemma mix_index (subst: IArray63.t t) (off: int) (i: index) (l: list Key.t)1594(id: indexes) (sn: snodes) : unit1595requires { not (Mem.mem (Index i) l) }1596ensures { 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 }1597ensures { mix_sn off l sn sn = mix_sn off (Cons (Index i) l) sn sn }1598= ()1599Valid (330ms) (cvc4)1600let lemma mix_snode (subst: IArray63.t t) (off: int) (nd: snode) (l: list Key.t)1601(id: indexes) (sn: snodes) : unit1602requires { not (Mem.mem (Var nd.n nd.s nd.scal) l) }1603ensures { mix_id subst l id sn id = mix_id subst (Cons (Var nd.n nd.s nd.scal) l) id sn id }1604ensures { 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 }1605= ()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)
predicate mem_key (nd: snode) (l: list (snode, t)) =1686match l with Nil -> false | Cons (nd', _) l' -> nd = nd' \/ mem_key nd l' end16871688predicate distinct_keys (l: list (snode, t)) =1689match l with Nil -> true | Cons (nd, _) l' -> not (mem_key nd l') /\ distinct_keys l' end1690
The valuation of the snodes after the (simultaneous) substitution l
function subst_sn (l: list (snode, t)) (id: indexes) (sn: snodes) : snodes =1693match l with1694| Nil -> sn1695| Cons (nd, f) l' -> Map.set (subst_sn l' id sn) nd (f.v id sn)1696end1697Valid (527ms) (colibri2 11) (cvc4) (split_vc) (depth 1)1698let rec partial add_snodes (l: list (snode, t)) : Vector.vector1699requires { distinct_keys l }1700variant { l }1701ensures { result.Vector.removed_indexes = Set.empty }1702ensures { forall nd. Set.mem nd result.Vector.removed_snodes <-> mem_key nd l }1703ensures { forall i. Set.mem i result.Vector.added_indexes ->1704exists nd f. Mem.mem (nd, f) l /\ Set.mem i f.dom_indexes }1705ensures { forall a id sn. Vector.subst result a id sn = a id (subst_sn l id sn) }1706= match l with1707| Nil ->1708let lemma nil (a: indexes -> snodes -> bool) (id: indexes) (sn: snodes) : unit1709ensures { a id sn = a id (subst_sn Nil id sn) }1710= ()1711in1712Vector.create ()1713| Cons (nd, f) l' ->1714let vec = add_snodes l' in1715Vector.add_snode vec nd f1716end1717Valid (139ms) (colibri2)1718let partial compose_snodes (l: list (snode, t)) (x: t) : t1719requires { distinct_keys l }1720ensures { forall i. Set.mem i result.dom_indexes ->1721Set.mem i x.dom_indexes \/ exists nd f. Mem.mem (nd, f) l /\ Set.mem i f.dom_indexes }1722ensures { forall id sn. result.v id sn = x.v id (subst_sn l id sn) }1723= Vector.compose (add_snodes l) x1724end1725