Common — library colibrilib.dom_modrw — module Rewrite

The table of the keys and the rewriting

130
module Rewrite
131
use real.RealInfix
132
use option.Option
133
use colibrilib.ring.Atom
134
use colibrilib.stda.StdA as A
135
use colibrilib.polynome.Lin
136
use colibrilib.polynome.ModRw
137
use colibrilib.env.Env
138
use colibrilib.spec.Opt
139
use colibrilib.spec.Defines
140
use Key

The table of the keys (a backtrackable hash table of colibri2): the node r of the key k is the remainder of k

144
predicate
tinv
(m:Atom.t -> real) (k:(Lin.t, div)) (r:Atom.t) =
145
let p, v = k in m r = Real.mod_e (eval m p) (dv m v)

r is the remainder of the key k in the model of d

148
predicate
in_table
(d:env) (k:(Lin.t, div)) (r:Atom.t) = live d -> tinv d.m k r
149
150
val
find
(d:env) (k:(Lin.t, div)) : option Atom.t
151
ensures { when_some (in_table d k) result }
152
153
val
add
(d:env) (k:(Lin.t, div)) (r:Atom.t) : unit
154
writes { d.state }
155
requires { in_table d k r }

The remainders of the same key are merged

  Valid (298ms) (colibri2)
158
let
merge_key
(d:env) (r:Atom.t) (k:(Lin.t, div)) : unit
159
requires { in_table d k r }
160
= match find d k with
161
| Some r' -> if not (is_equal d r r') then merge d r r'
162
| None -> add d k r
163
end

r is the remainder mod_e x den, when den is not zero

  Valid (302ms) (colibri2 9) (split_vc) (depth 1)
166
let partial
rewrite
(d:env) (r x den:Atom.t) : unit
167
requires { live d -> d.m den <> 0.0 -> defines2 d.m Real.mod_e r x den }
168
= match key d x den with
169
| None -> ()
170
| Some (p, v) ->
171
match is_cst p, v with
172
| Some c, Cst c' ->
173
(* `0 <= c < |m|` *)
174
let lemma l () : unit
175
ensures { Real.mod_e (A.real c) (A.real c') = A.real c }
176
= mod_facts (A.real c) (A.real c') 0 in
177
merge d r (cst_node d c)
178
| Some c, Abs y ->
179
if A.equal c (A.of_int 0) then begin
180
let lemma l () : unit
181
requires { live d }
182
ensures { Real.mod_e 0.0 (d.m y) = 0.0 }
183
= mod_facts 0.0 (d.m y) 0 in
184
merge d r (cst_node d c)
185
end else merge_key d r (p, v)
186
| _ -> merge_key d r (p, v)
187
end
188
end

r is the remainder mod_e x den in the model md, when den is not zero

192
predicate
remainder
(md: model) (r x den: Atom.t) =
193
real_value md den <> 0.0 -> defines2 (real_value md) Real.mod_e r x den

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)
198
type
reg
= {
rr
: Atom.t;
rx
: Atom.t;
rden
: Atom.t; ghost
rm
: model; ghost
rl
: bool }
199
invariant { rl -> remainder rm rr rx rden }
200
by { rr = any Atom.t; rx = any Atom.t; rden = any Atom.t; rm = any model; rl = false }

The remainder r = mod_e x den, registered in d

  Valid (53ms) (colibri2)
203
let
register
(d:env) (r x den:Atom.t) : reg
204
requires { live d -> remainder d.model r x den }
205
ensures { result.rr = r /\ result.rx = x /\ result.rden = den }
206
ensures { result.rm = d.model /\ result.rl = live d }
207
= { rr = r; rx = x; rden = den; rm = pure { d.model }; rl = pure { live d } }

The rewriting of a registered remainder, in an environment of its model, live only if the one of its registration was

  Valid (53ms) (colibri2)
211
let partial
run
(d:env) (g:reg) : unit
212
requires { d.model = g.rm /\ (live d -> g.rl) }
213
= rewrite d g.rr g.rx g.rden
214
end