library colibrilib.fp_conv — module RelDbThe 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.
module RelDb680use int.Int681use list.List682use list.Mem as LM683use colibrilib.ring.Atom684use colibrilib.fbin.Fp685use colibrilib.zinterval.Zi as Zi686use option.Option687use Env688
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
val entries (d: envp 'm) (x: Atom.t) : list (Atom.t, Zi.t)692ensures { forall k i. LM.mem (k, i) result -> live d -> relh i (d.mf x) (d.mf k) }693
Store the entry (y, i) on the class of x (Dom_rel.upd_dom, the meet with the entry of the representative of y)
val store (d: env) (x y: Atom.t) (i: Zi.t) : unit697requires { live d -> relh i (d.mf x) (d.mf y) }698writes { d.state }699ensures { d.ri = old d.ri /\ d.dy = old d.dy }700
The relation of the classes of x and y changed (Dom_rel.on_change: the waits of Conv.wait_rel and Conv.wait_mono)
val notify (d: env) (x y: Atom.t) : unit705writes { d.state }706ensures { d.ri = old d.ri /\ d.dy = old d.dy }707
The meet of acc and the entries of l whose key is in the class of y
Valid (1.1s) (cvc4)let rec meet_entries (d: envp 'm) (ghost x: Atom.t) (y: Atom.t)711(l: list (Atom.t, Zi.t)) (acc: Zi.t) : Zi.t712requires { forall k i. LM.mem (k, i) l -> live d -> relh i (d.mf x) (d.mf k) }713requires { live d -> relh acc (d.mf x) (d.mf y) }714ensures { live d -> relh result (d.mf x) (d.mf y) }715variant { l }716= match l with717| Nil -> acc718| Cons (k, i) t ->719{proof…}720assert { LM.mem (k, i) l /\ forall z. LM.mem z t -> LM.mem z l };721{qed}722if is_equal d k y then begin723let n = Zi.inter acc i in724{proof…}725if pure { live d } then Zi.mem_inter (zi (d.mf y) - zi (d.mf x)) acc i;726{qed}727meet_entries d x y t n728end else meet_entries d x y t acc729end730Valid (40ms) (colibri2)731let getrel (d: envp 'm) (fm: format) (x y: Atom.t) : Zi.t732ensures { live d -> relh result (d.mf x) (d.mf y) }733= meet_entries d x y (entries d x) Zi.top734Valid (90ms) (colibri2)735let updrel (d: env) (fm: format) (x y: Atom.t) (i: Zi.t) : option Zi.t736requires { live d -> relh i (d.mf x) (d.mf y) }737ensures { d.ri = old d.ri /\ d.dy = old d.dy }738ensures { match result with Some n -> live d -> relh n (d.mf x) (d.mf y) | None -> true end }739= let cur = getrel d fm x y in740let n = Zi.inter cur i in741if not (Zi.equal n cur) then begin742{proof…}743if pure { live d } then begin744Zi.mem_inter (zi (d.mf y) - zi (d.mf x)) cur i;745Zi.mem_rev (zi (d.mf y) - zi (d.mf x)) n;746assert { zi (d.mf x) - zi (d.mf y) = - (zi (d.mf y) - zi (d.mf x)) }747end;748{qed}749store d x y n;750store d y x (Zi.rev n);751notify d x y;752Some n753end else None754end755