library colibrilib.dom_modrw — module RewriteThe table of the keys and the rewriting
module Rewrite130use real.RealInfix131use option.Option132use colibrilib.ring.Atom133use colibrilib.stda.StdA as A134use colibrilib.polynome.Lin135use colibrilib.polynome.ModRw136use colibrilib.env.Env137use colibrilib.spec.Opt138use colibrilib.spec.Defines139use Key140
The table of the keys (a backtrackable hash table of colibri2): the node r of the key k is the remainder of k
predicate tinv (m:Atom.t -> real) (k:(Lin.t, div)) (r:Atom.t) =144let p, v = k in m r = Real.mod_e (eval m p) (dv m v)145
r is the remainder of the key k in the model of d
predicate in_table (d:env) (k:(Lin.t, div)) (r:Atom.t) = live d -> tinv d.m k r148149val find (d:env) (k:(Lin.t, div)) : option Atom.t150ensures { when_some (in_table d k) result }151152val add (d:env) (k:(Lin.t, div)) (r:Atom.t) : unit153writes { d.state }154requires { in_table d k r }155
The remainders of the same key are merged
Valid (298ms) (colibri2)let merge_key (d:env) (r:Atom.t) (k:(Lin.t, div)) : unit158requires { in_table d k r }159= match find d k with160| Some r' -> if not (is_equal d r r') then merge d r r'161| None -> add d k r162end163
r is the remainder mod_e x den, when den is not zero
Valid (302ms) (colibri2 9) (split_vc) (depth 1)let partial rewrite (d:env) (r x den:Atom.t) : unit166requires { live d -> d.m den <> 0.0 -> defines2 d.m Real.mod_e r x den }167= match key d x den with168| None -> ()169| Some (p, v) ->170match is_cst p, v with171| Some c, Cst c' ->172(* `0 <= c < |m|` *)173let lemma l () : unit174ensures { Real.mod_e (A.real c) (A.real c') = A.real c }175= mod_facts (A.real c) (A.real c') 0 in176merge d r (cst_node d c)177| Some c, Abs y ->178if A.equal c (A.of_int 0) then begin179let lemma l () : unit180requires { live d }181ensures { Real.mod_e 0.0 (d.m y) = 0.0 }182= mod_facts 0.0 (d.m y) 0 in183merge d r (cst_node d c)184end else merge_key d r (p, v)185| _ -> merge_key d r (p, v)186end187end188
r is the remainder mod_e x den in the model md, when den is not zero
predicate remainder (md: model) (r x den: Atom.t) =192real_value md den <> 0.0 -> defines2 (real_value md) Real.mod_e r x den193
The remainder r = mod_e x den, registered in an environment of the model rm, live when rl: its callbacks run in the environments of the same model
Valid (38ms) (colibri2)type reg = { rr: Atom.t; rx: Atom.t; rden: Atom.t; ghost rm: model; ghost rl: bool }198invariant { rl -> remainder rm rr rx rden }199by { rr = any Atom.t; rx = any Atom.t; rden = any Atom.t; rm = any model; rl = false }200
The remainder r = mod_e x den, registered in d
Valid (53ms) (colibri2)let register (d:env) (r x den:Atom.t) : reg203requires { live d -> remainder d.model r x den }204ensures { result.rr = r /\ result.rx = x /\ result.rden = den }205ensures { result.rm = d.model /\ result.rl = live d }206= { rr = r; rx = x; rden = den; rm = pure { d.model }; rl = pure { live d } }207
The rewriting of a registered remainder, in an environment of its model, live only if the one of its registration was
Valid (53ms) (colibri2)let partial run (d:env) (g:reg) : unit211requires { d.model = g.rm /\ (live d -> g.rl) }212= rewrite d g.rr g.rx g.rden213end214