Common — library colibrilib.fp_conv — module RelDb

The relation database, on its storage

The implementations of Env.getrel and Env.updrel, with the same specifications, on the trusted entries, store and notify of the domain Dom_rel (the intervals stored on a class, each true in the model): the extraction (fp_conv.drv) maps the two val of Env to them.

680
module RelDb
681
use int.Int
682
use list.List
683
use list.Mem as LM
684
use colibrilib.ring.Atom
685
use colibrilib.fbin.Fp
686
use colibrilib.zinterval.Zi as Zi
687
use option.Option
688
use Env

The entries (k, i) stored on the class of x (Egraph.get_dom of Dom_rel.dom): i is an interval of zi k - zi x

692
val
entries
(d: envp 'm) (x: Atom.t) : list (Atom.t, Zi.t)
693
ensures { forall k i. LM.mem (k, i) result -> live d -> relh i (d.mf x) (d.mf k) }

Store the entry (y, i) on the class of x (Dom_rel.upd_dom, the meet with the entry of the representative of y)

697
val
store
(d: env) (x y: Atom.t) (i: Zi.t) : unit
698
requires { live d -> relh i (d.mf x) (d.mf y) }
699
writes { d.state }
700
ensures { d.ri = old d.ri /\ d.dy = old d.dy }

The relation of the classes of x and y changed (Dom_rel.on_change: the waits of Conv.wait_rel and Conv.wait_mono)

705
val
notify
(d: env) (x y: Atom.t) : unit
706
writes { d.state }
707
ensures { d.ri = old d.ri /\ d.dy = old d.dy }

The meet of acc and the entries of l whose key is in the class of y

  Valid (1.1s) (cvc4)
711
let rec
meet_entries
(d: envp 'm) (ghost x: Atom.t) (y: Atom.t)
712
(l: list (Atom.t, Zi.t)) (acc: Zi.t) : Zi.t
713
requires { forall k i. LM.mem (k, i) l -> live d -> relh i (d.mf x) (d.mf k) }
714
requires { live d -> relh acc (d.mf x) (d.mf y) }
715
ensures { live d -> relh result (d.mf x) (d.mf y) }
716
variant { l }
717
= match l with
718
| Nil -> acc
719
| Cons (k, i) t ->
720
{proof…}
721
assert { LM.mem (k, i) l /\ forall z. LM.mem z t -> LM.mem z l };
722
{qed}
723
if is_equal d k y then begin
724
let n = Zi.inter acc i in
725
{proof…}
726
if pure { live d } then Zi.mem_inter (zi (d.mf y) - zi (d.mf x)) acc i;
727
{qed}
728
meet_entries d x y t n
729
end else meet_entries d x y t acc
730
end
731
Valid (40ms) (colibri2)
732
let
getrel
(d: envp 'm) (fm: format) (x y: Atom.t) : Zi.t
733
ensures { live d -> relh result (d.mf x) (d.mf y) }
734
= meet_entries d x y (entries d x) Zi.top
735
Valid (90ms) (colibri2)
736
let
updrel
(d: env) (fm: format) (x y: Atom.t) (i: Zi.t) : option Zi.t
737
requires { live d -> relh i (d.mf x) (d.mf y) }
738
ensures { d.ri = old d.ri /\ d.dy = old d.dy }
739
ensures { match result with Some n -> live d -> relh n (d.mf x) (d.mf y) | None -> true end }
740
= let cur = getrel d fm x y in
741
let n = Zi.inter cur i in
742
if not (Zi.equal n cur) then begin
743
{proof…}
744
if pure { live d } then begin
745
Zi.mem_inter (zi (d.mf y) - zi (d.mf x)) cur i;
746
Zi.mem_rev (zi (d.mf y) - zi (d.mf x)) n;
747
assert { zi (d.mf x) - zi (d.mf y) = - (zi (d.mf y) - zi (d.mf x)) }
748
end;
749
{qed}
750
store d x y n;
751
store d y x (Zi.rev n);
752
notify d x y;
753
Some n
754
end else None
755
end