rocq/theories/Invariant.v
Campaign 3's run-level evidence invariant, stated (docs/rocq.md, The evidence invariant over runs): what holds at each point of a frame of Machine R (Machine.v), and the lemmas each kind of step needs. Persistence.v proves that every step keeps it.
The invariant (inv) says that the running frame, unless a check_ahead doomed it, is at a point where the facts the evidence pass computed for that point hold (point_ok), and that every waiting caller has no fact (parked). It also says that each live fact's pointer has a single definition whose site dominates the point (live_dom), so that the reuse forms may read that pointer's definition.
The live facts' pointers dominate
A fact names the pointer its check was of. The reuse forms read that pointer's single definition, so they need it to dominate the point where the fact is live (live_dom). This is a property of the pass alone, block by block: a check's pointer is an operand the check uses (definitions_dominate/3), and a fact that reaches a block's entry over every incoming edge has a pointer dominating each reachable predecessor's end, so the entry too (dom_meet).
A function f of a checked_module md is valid in the ways the proofs use: it has a first block, its dominator intervals (block_intervals) are its fn_doms, its block labels are distinct, and its definitions dominate their uses (definitions_dominate/3).
Explore proof 15 tactics
Initial goal
unfold checked_module , valid
intros md f Hv _ Hin
destruct existsb_ md ; discriminate Hv |
injection Hv as Hv
unfold valid_items in Hv
apply andb_true_iff in Hv as _ Hv
rewrite forallb_forall in Hv
specialize Hv_ Hin
simpl in Hv
unfold valid_func , fn_doms in *
destruct fn_blocksf as | b0 bs eqn: Eb ; discriminate Hv |
destruct block_intervalsb0 :: bs as doms | eqn: Ed ; | discriminate Hv
repeat match goal withHb : _ && _ = true |- _⇒apply andb_true_iff in Hb as ? ?end
exists b0, bs
auto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Where the labels of the blocks bs are distinct, the block find_block finds for l is the only block of bs labelled l.
Explore proof 14 tactics
Initial goal
induction bs as | b0 bs IH ; simpl ; intros l b b′ Hnd Hf Hin Hl ; discriminate Hf |
apply andb_true_iff in Hnd as Hn Hnd
destruct name_eqbb_labelb0 l eqn: E
2 openfocused goal
–injection Hf as ←
2 opendeferred goal
apply name_eqb_true in E
2 opendeferred goal
destruct Hin as → | Hin ; reflexivity |
2 opendeferred goal
exfalso
2 opendeferred goal
apply negb_true_iff in Hn
2 opendeferred goal
pose proof mem_false_ _ Hn b_labelb′ in_map_ _ _ Hin as Hne
2 opendeferred goal
rewrite E , Hl in Hne
2 opendeferred goal
apply name_eqb_false in Hne
2 opendeferred goal
exact Hneeq_refl
deferred goal
–destruct Hin as → | Hin ; rewrite Hl in E ; apply name_eqb_false in E ; contradiction |
exact IH_ _ _ Hnd Hf Hin Hl
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Where dropping k elements of l leaves x before rest, x is l's element at k, dropping k + 1 leaves rest, and k is below l's length.
Explore proof 8 tactics
Initial goal
intros A k
induction k as | k IH ; intros l x rest H ; destruct l as | y l ; simpl in * ; try discriminate H
2 openfocused goal
–injection H as → →
2 opendeferred goal
split ; reflexivity |
2 opendeferred goal
split ; reflexivity | lia
deferred goal
–destruct IH_ _ _ H as H1 & H2 & H3
split ; exact H1 |
split ; exact H2 | lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A temporary among the values vs is among their temporaries (value_temps).
Explore proof 5 tactics
Initial goal
intros vs a H
unfold value_temps
apply in_flat_map
exists Tmpa
split ; exact H | left ; reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The single definition of each live fact's pointer (its P, where P is a temporary y with one definition) is at a site that dominates index k of block l of f (dominating).
The same, where block l is reachable: what the reuse forms need of the live facts at index k of l.
A site that dominates index k of block l dominates every later index k' of l.
Explore proof 2 tactics
Initial goal
intros doms l k k′ | d j Hk H ; simpl in * ; reflexivity |
destruct name_eqbd l ; apply Z.ltb_lt in H ; apply Z.ltb_lt ; lia | exact H
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
So live facts that dominate index k of a block dominate every later index of it.
Explore proof 7 tactics
Initial goal
intros f l k k′ live Hk H Hr fa y Hfa Hy Ho
destruct HHr fa y Hfa Hy Ho as s & D & H1 & H2 & H3
exists s, D
split ; exact H1 |
split ; exact H2 |
eapply site_dominates_mono ; | exact H3
lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The empty list of facts dominates every point.
Explore proof 1 tactics
kill d keeps only facts it was given.
Explore proof 4 tactics
Initial goal
unfold kill
intros d fs fa H
apply filter_In in H
exact proj1H
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
evidence_after keeps only facts it was given.
Explore proof 4 tactics
Initial goal
unfold evidence_after
intros i fs fa H
destruct evidence_preservingi ; | destruct H
destruct inst_def_firsti ; exact kill_incl_ _ _ H | exact H
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The fact a check-like instruction i adds (check_fact) is of a pointer y that i uses.
Explore proof 3 tactics
Initial goal
intros i fa y H Hy
destruct i as q k o args | | | | | | | ; try discriminate H
destruct k , o ; try discriminate H ; destruct args as | a1 | a2 | a3 | a4 args ; simpl in H ; try discriminate H ; injection H as ← ; simpl in Hy ; subst ; apply value_temps_in ; simpl ; auto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
One step of the pass (checked_inst_rest) takes one instruction, or a check and its access, and keeps only facts it had or the check's own.
Explore proof 31 tactics
Initial goal
intros s i rest live rest′ live′ Hc
destruct check_facti as fa0 | eqn: Hf
2 openfocused goal
–destruct access_fact_some_ _ Hf as fb Hg
2 opendeferred goal
destruct checked_inst_rest_check_ _ _ _ _ _ _ _ Hf Hg Hc as access & → & _ & →
2 opendeferred goal
split ; right ; eauto |
2 opendeferred goal
intros fa Hfa
2 opendeferred goal
apply evidence_after_incl in Hfa as ← | Hfa ; right ; reflexivity |
2 opendeferred goal
left
2 opendeferred goal
exact evidence_after_incl_ _ _ Hfa
deferred goal
–destruct is_check_locali eqn: Hcl
2 openfocused goal
+destruct i as q k o args | | | | | | | ; try discriminate Hcl
2 opendeferred goal
destruct k ; try discriminate Hcl ; destruct o ; try discriminate Hcl ; destruct args ; try discriminate Hcl
2 opendeferred goal
destruct checked_inst_rest_local_cov_ _ _ _ _ _ _ _ _ _ _ Hc as access & → & _ & →
2 opendeferred goal
split ; right ; eauto |
2 opendeferred goal
intros fa Hfa
2 opendeferred goal
left
2 opendeferred goal
exact kill_incl_ _ _ evidence_after_incl_ _ _ Hfa
deferred goal
+destruct is_check_functioni eqn: Hcf
2 openfocused goal
∗destruct i as q k o args | | | | | | | ; try discriminate Hcf
2 opendeferred goal
destruct k ; try discriminate Hcf ; destruct o ; try discriminate Hcf
2 opendeferred goal
destruct checked_inst_rest_function_rest_ _ _ _ _ _ _ Hc as → & r & cargs & →
2 opendeferred goal
split ; right ; eauto | intros fa
deferred goal
∗assert Hs′ : pass_speciali = false
2 openfocused goal
{destruct pass_speciali eqn: Hp ; | reflexivity
2 opendeferred goal
destruct pass_special_cases_ Hp Hf as E | E ; congruence
deferred goal
rewrite checked_inst_rest_generic_ _ _ _ Hs′ in Hc
destruct generic_rest_shape_ _ _ _ _ _ Hc as → & Hlive & _
split ; left ; reflexivity |
intros fa Hfa
left
destruct Hlive as → | d & g & _ & → ; exact evidence_after_incl_ _ _ Hfa | exact kill_incl_ _ _ Hfa
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
In a block b of a function f of a checked module md, where the facts before the pass's step at index k dominate k, the facts after it dominate index k + 1: a check's own fact is of an operand it uses, whose single definition dominates it (use_dominated).
Explore proof 12 tactics
Initial goal
intros md f b k i rest live rest′ live′ Hmd Hin Hb Hk Hc H Hr fa y Hfa Hy Ho
destruct proj2pass_live_after_ _ _ _ _ _ Hc fa Hfa as Hl | Hf
2 openfocused goal
–exact live_dom_mono_ _ _ _ _ le_S_ _ le_nk H Hr fa y Hl Hy Ho
deferred goal
–destruct func_facts_ _ Hmd Hin as _ & _ & _ & _ & _ & Hdd
unfold once_has in Ho
destruct lookupy single_definitionsf as D | eqn: Ey ; | discriminate Ho
destruct use_dominated_ _ _ _ _ _ _ Hdd Hb Hr Hk check_fact_uses_ _ _ Hf Hy Ey as s & Hs & Hsd
exists s, D
split ; exact Ey |
split ; exact Hs |
eapply site_dominates_mono ; | exact Hsd
lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The pass's facts at a block's end (checked_insts walking the block from index k) dominate the end, where those it started with dominated k.
Explore proof 10 tactics
Initial goal
intros md f b n
induction n as | n IH ; intros k is live out Hmd Hin Hb Hs Hk H Hc ; destruct is as | i rest ; cbn [ checked_insts ] in Hc ; injection Hc as ← ; exact live_dom_mono_ _ _ _ _ Hk H | ; discriminate Hc |
destruct checked_inst_rest_ i rest live as rest′ live′ | eqn: Ec ; | discriminate Hc
simpl in Hc
destruct skipn_cons_ _ _ _ _ eq_symHs as Hki & Hrest & Hlen
pose proof pass_step_dom_ _ _ _ _ _ _ _ _ Hmd Hin Hb Hki Ec H as H1
destruct proj1pass_live_after_ _ _ _ _ _ Ec as → | a & →
2 openfocused goal
–exact IH_ _ _ _ Hmd Hin Hb eq_symHrest Hlen H1 Hc
deferred goal
–destruct skipn_cons_ _ _ _ _ Hrest as _ & Hrest′ & Hlen′
exact IH_ _ _ _ Hmd Hin Hb eq_symHrest′ Hlen′ live_dom_mono_ _ _ _ _ le_S_ _ le_n_ H1 Hc
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Each block's exit facts, in the map ex from labels to the facts at their end, dominate its end.
Each successor label of a jump j is the label of one of its targets (jump_targets).
Explore proof 5 tactics
Initial goal
intros t | v t1 t2 | v | vs | | s H ; simpl in H ; try contradiction
2 openfocused goal
–destruct H as ← |
2 opendeferred goal
exists t
2 opendeferred goal
split ; left | ; reflexivity
deferred goal
–destruct H as ← | ← | ; exists t1 | exists t2 ; simpl ; auto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Where every block's exit facts dominate its end, the pass's entry facts of a block b (entry_live) dominate its entry: a fact that reaches b over every incoming edge has a pointer whose definition dominates each reachable predecessor's end, so b's entry too (dom_meet). The entry block has no incoming edge and no fact.
Proof 45 steps Qed
Every block's exit facts, as the pass computes them for f (pass_exits), dominate its end.
Proof 34 steps Qed
The invariant, frame by frame
The edge a jump j takes (taken_target) is one of its targets.
Explore proof 9 tactics
Initial goal
unfold taken_target
intros ge fr j t H
destruct j ; try discriminate H
2 open–injection H as ←
2 openleft
2 openreflexivity
–destruct value_x_ _ _ _ as n | | | ; try discriminate H
injection H as ←
destruct n =? 0 ; simpl ; auto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Explore proof 3 tactics
Initial goal
unfold edge_step
intros c from t c′ H
destruct t , fr_doomedc_framec ; try discriminate H ; injection H as ← ; auto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
A jump at the end of block l takes an edge, the one taken_target names, or returns from a frame that is not doomed.
Proof 33 steps Qed
What holds where
at_pos says where the pass is in a block and what holds there: between two of the pass's steps, the live facts the next instruction relies on (and, at the block's end, the facts the next unpolled edge carries); or between a check and the access the pass took with it, the fact that covers the access (pair_claim). A check_function's raw call needs no fact but its function check.
At a block's end, before its jump j: if the edge j takes does not poll, the facts live hold. A poll edge carries no fact, since the runtime may act there.
Between a check and the access the pass took with it: the fact fb that covers the access (covered_access) holds, with the facts pre the pass kept with it, and live' is what evidence_after keeps of pre across the access; or, after a check_function, the access is a raw call through q whose pointer p passed its function check (function_check_res), and the pass keeps no fact.
Where the pass is in the instructions is of block l of f, and what holds there, with out the pass's exit facts of the block. Either it is between two of its steps, with facts live that the pass walks to out (walks), that dominate index k (live_dom), and that hold if the next instruction relies on them (relies) or, at the block's end, as the jump carries them (jump_claim); or it is between a check and the access it took with it (pair_claim).
What holds at the point of the frame fr in memory m, for its function f of the module md: at a snapshot, or at the entry entered from no block, the point is f's entry; at a block's entry from the block p, the edge is one of p's and, unless it polls, p's exit facts hold; within a block, at_pos, with the exit facts E the pass computes (pass_exits).
Every named local the frame has allocated lies above address 0: a check_local's fact needs its address not to wrap.
The running frame fr: it runs a function of the module md, its locals lie above 0 (locals_pos), and it is point_ok unless a check_ahead doomed it.
A waiting caller fr: it runs a function of md, its locals lie above 0, it is not doomed, and it waits just after its call, inside a block whose rest the pass walks from no fact at all: a call ends every fact.
The runtime's action at a safepoint changes no region where it comes just before an instruction i that the pass relies on facts across (relies). Every runtime satisfies it (spares_any): no region changes at a safepoint. It was kept a hypothesis while the safepoint stood for signal handlers too, since natively a pointer store whose aux must be allocated exits to the runtime, where a handler the program installed may free the checked object (docs/rocq.md, The evidence invariant over runs).
Every runtime spares every module's facts: the collector changes no region at a safepoint (R.collector_live).
Explore proof 2 tactics
Source script
The empty list of facts holds.
Explore proof 1 tactics
Initial goal
intros ge m e fa
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Where the facts after a step hold, whatever comes next may rely on them.
Explore proof 6 tactics
Initial goal
intros ge s m fr is j live out f l k Hw Hd Hl
left
exists live
split ; exact Hw |
split ; exact Hd |
destruct is ; intros t _ _ ; exact Hl | intros _ ; exact Hl
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Explore proof 14 tactics
Initial goal
intros ge md m fr e Hin & Hpos & Hd & E & l & rest & j & b & out & k & HE & Ha & Hb & Hout & Hj & Hk & Hw
split ; exact Hin |
split ; exact Hpos |
right
exists E
split ; exact HE |
simpl
rewrite Ha
exists b, out, k
split ; exact Hb |
split ; exact Hout |
split ; exact Hj |
split ; exact Hk |
eapply at_pos_between ; exact Hw | apply live_dom_nil | apply facts_hold_nil
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A callee g of a checked module, its frame fr made by call_frame from the arguments xs, starts at its entry, frame_ok.
Explore proof 15 tactics
Initial goal
intros ge md m g xs fr Hmd Hin H
unfold call_frame in H
destruct lengthxs <? lengthfn_paramsg%nat ; discriminate H |
destruct module_func_ _ Hmd Hin as _ & _ & E & HE
destruct fn_blocksg as | b bs eqn: Eb ; discriminate H |
injection H as ←
split ; exact Hin |
split ; intros x base Hx ; exfalso ; exact lookup_unallocated_ _ _ Hx |
right
exists E
split ; exact HE |
unfold entry_label
simpl
rewrite Eb
destruct variadic_funcg ; reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
An instruction i the pass took, that continues, leaves the pass's next position true: the facts after it, or the fact that covers the access the pass took with it (pair_claim). The facts before i need to hold only if the pass relies on them (relies).
Proof 67 steps Qed
The access the pass took with its check, if it continues, leaves the facts the pass has after it.
Explore proof 6 tactics
Initial goal
intros ge m fr access live′ e1 l1 m1 fb & pre & _ & → & Hh | → & _ Hs ; | apply facts_hold_nil
eapply evidence_after_holds ; | exact Hs
intros fa Hin
apply Hh
right
exact Hin
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Where the instruction i at the pass's position, index k of block b, continues with environment e1 and memory m1, the next position, at index k + 1, holds of any frame fr1 with environment e1.
Explore proof 18 tactics
Initial goal
intros ge md m fr i rest j out e1 l1 m1 fr1 f l b k Hmd Hin Hb Hk Hfit Hpos Hat Hs He
destruct find_block_in_ _ _ Hb as Hbin ←
destruct skipn_cons_ _ _ _ _ eq_symHk as Hki & _ & _
destruct Hat as live & Hw & Hd & Hl | access & rest′ & live′ & E & Hw & Hd & Hp
2 openfocused goal
–destruct walks_cons_ _ _ _ _ Hw as rest′ & live′ & Hc & Hw′
2 opendeferred goal
pose proof pass_step_dom_ _ _ _ _ _ _ _ _ Hmd Hin Hbin Hki Hc Hd as Hd′
2 opendeferred goal
destruct pass_step_ _ _ _ _ _ _ _ _ _ _ _ _ Hfit Hpos Hl Hc Hs He as → & Hh | access & → & Hp
3 openfocused goal
deferred goal
+eapply at_pos_between ; exact Hw′ | exact Hd′ | rewrite He ; exact Hh
2 opendeferred goal
deferred goal
+right
2 opendeferred goal
exists access, rest′, live′
2 opendeferred goal
split ; reflexivity |
2 opendeferred goal
split ; exact Hw′ |
2 opendeferred goal
split ; exact live_dom_mono_ _ _ _ _ le_S_ _ le_n_ Hd′ |
2 opendeferred goal
exact Hp
deferred goal
–injection E as ← ←
eapply at_pos_between ; exact Hw | exact Hd |
rewrite He
eapply pair_continue ; eauto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
After an instruction the pass relies on nothing for, and that is not a check_function, the pass goes on with no facts.
Explore proof 10 tactics
Initial goal
intros ge s m fr i rest j out f l k Hat Hr Hcf
destruct Hat as live & Hw & _ | access & rest′ & live′ & E & Hw & _ & Hp
2 openfocused goal
–destruct walks_cons_ _ _ _ _ Hw as rest′ & live′ & Hc & Hw′
2 opendeferred goal
destruct relies_false_rest_ _ _ _ _ _ Hr Hcf Hc as → →
2 opendeferred goal
exact Hw′
deferred goal
–injection E as ← ←
destruct Hp as fb & pre & _ & → & _ | → & _ ; | exact Hw
unfold evidence_after in Hw
rewrite relies_preserving_ _ Hr in Hw
exact Hw
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Reading and making point_ok
Explore proof 7 tactics
Initial goal
intros ge md m fr l is j E b out k HE Ha Hb Ho Hj Hk Hat
unfold point_ok
cbv zeta
exists E
split ; exact HE |
rewrite Ha
eauto 8
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Explore proof 7 tactics
Initial goal
intros ge md m fr l is j H Ha
unfold point_ok in H
cbv zeta in H
destruct H as E & HE & H
rewrite Ha in H
destruct H as b & out & k & ?
eauto 10
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A running frame that is not doomed, at a call, can wait after it with no fact, whatever the call does: it is parked there.
Explore proof 12 tactics
Initial goal
intros ge md m fr l r callee args rest j Hin & Hpos & Hpt Hd Ha
destruct Hpt as Hd0 | Hp ; congruence |
destruct point_ok_exec_inv_ _ _ _ _ _ _ Hp Ha as E & b & out & k & HE & Hb & Hout & Hj & Hk & Hat
destruct skipn_cons_ _ _ _ _ eq_symHk as _ & Hrest & _
split ; exact Hin |
split ; exact Hpos |
split ; reflexivity |
exists E, l, rest, j, b, out, Sk
simpl
repeat split ; assumption || reflexivity |
split ; symmetry ; exact Hrest |
eapply walks_after ; exact Hat | reflexivity | reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Explore proof 8 tactics
Initial goal
intros ge md m m′ fr fr′ xs l H Ha Hf Ha′
unfold point_ok in *
cbv zeta in *
rewrite Hf , Ha′
destruct H as E & HE & H
exists E
split ; exact HE |
destruct Ha as Ha | Ha ; rewrite Ha in H ; exact H
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Nothing is found in an empty map.