rocq/theories/Persistence.v
Campaign 3's evidence invariant over whole runs (docs/formal.md, Campaign 3, Proof persistence; docs/rocq.md, The evidence invariant over runs).
Evidence.v proves ir.pl's evidence pass sound one instruction and one edge at a time. This file carries that along every run of Machine.v's machine: in each state a run of a checked module reaches, the facts the pass computed for the running frame's position hold (inv, stated in Invariant.v), so a raw access the pass accepted by a live fact, or took with its own check, gives no unchecked (run_access_not_unchecked). Walk.v reads the pass back block by block and position by position, and Steps.v says what each kind of step does to the frame.
At a safepoint before an instruction the pass relies on facts across, the runtime changes no region: every runtime spares the pass's facts (Invariant.v's spares_any, from Runtime.v's collector_live), so the theorems take no hypothesis about safepoints. Until 2026-11-09 spares was one, because a pointer store whose aux must be allocated exits to the runtime (filc_exit_with_allocation_root in filc_runtime.c), where a deferred signal handler may free the checked object, and the store lands in the freed object's retained memory, safe natively by retention but unchecked in the model. A handler is the program's code, and installing one ends a run in the model, so that case is now a constraint on verifying handlers: one must not free an object whose check is in flight.
Decisions
| Decision | Why |
|---|---|
the pass's position is a relation (walks, at_pos), not a program counter | checked_inst_rest/7 takes a check and its access in one step, so the pass's positions are a subset of the instructions |
| a doomed frame claims nothing | its check_ahead's fact does not hold; what it may still do is the check_ahead corollary's |
spares is no hypothesis of the theorems | every runtime meets it (spares_any) since the safepoint became the collector's alone (2026-11-09). Before, it was false natively at a pointer store's aux exit, where a handler's free may show (docs/rocq.md, The evidence invariant over runs) |
| no unchecked outcome is claimed for a free | Soundness.v covers it by Runtime.v's free_checked |
Every step keeps the invariant
The pass accepted the raw access i, the next instruction of block l in the configuration c, by hull_covered/7, with live facts that hold and whose pointers' single definitions dominate i (live_dom). Chain.v proves such an access checked.
Each step keeps the invariant
Allocating the named local x at a base above 0 keeps every local above 0 (locals_pos).
Explore proof 3 tactics
Initial goal
intros fr x base Hpos Hb fr′ Hl y b H
rewrite Hl , lookup_put in H
destruct name_eqby x ; injection H as ← ; exact Hb | exact Hpos_ _ H
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A call is not ahead-transparent, so a doomed frame never makes one.
Explore proof 1 tactics
Initial goal
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Nor is a raw call.
Explore proof 1 tactics
Initial goal
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Explore proof 10 tactics
Initial goal
intros ge md c c′ s xs l Hge Hmd Hr Ha Hs Hin & Hpos & Hpt Hcall
unfold inv
simpl in *
destruct step_snapshot_ _ _ _ _ Ha Hs as Hc & Hf & Hl & Hd & Ha′
rewrite Hc
split ; | exact Hcall
split ; rewrite Hf ; exact Hin |
split ; intros x b Hx ; rewrite Hl in Hx ; exact Hpos_ _ Hx |
destruct Hpt as Hd0 | Hp ; left ; rewrite Hd ; exact Hd0 | right
eapply point_ok_entry ; exact Hp | left ; exact Ha | exact Hf | exact Ha′
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Entering a block keeps inv (enter_point_ok).
Explore proof 10 tactics
Initial goal
intros ge md c c′ s l from Hge Hmd Hr Ha Hs Hin & Hpos & Hpt Hcall
unfold inv
simpl in *
pose proof enter_point_ok_ _ _ _ _ _ Hmd Hin Ha Hs as Hep
destruct step_enter_ _ _ _ _ Ha Hs as b & e & _ & _ & →
simpl in *
split ; | exact Hcall
split ; exact Hin |
split ; exact Hpos |
destruct Hpt as Hd0 | Hp ; left ; exact Hd0 | right ; exact HepHp
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A jump keeps inv: it takes an edge, whose facts hold unless it polls, or returns to a waiting caller, which resumes with no fact (parked_resume).
Explore proof 32 tactics
Initial goal
intros ge md c c′ s l j Hge Hmd Hr Ha Hs Hin & Hpos & Hpt Hcall
unfold inv
simpl in *
unfold step in Hs
rewrite Ha in Hs
destruct jump_step_next_ _ _ _ _ Hs as t & Ht & → | Hd & o & Hret
2 openfocused goal
+simpl
2 opendeferred goal
split ; | exact Hcall
2 opendeferred goal
split ; exact Hin |
2 opendeferred goal
split ; exact Hpos |
2 opendeferred goal
destruct Hpt as Hd0 | Hp ; left ; exact Hd0 | right
2 opendeferred goal
destruct point_ok_exec_inv_ _ _ _ _ _ _ Hp Ha as E & b & out & k & HE & Hb & Ho & Hj & _ & Hat
2 opendeferred goal
unfold point_ok
2 opendeferred goal
cbv zeta
2 opendeferred goal
simpl
2 opendeferred goal
exists E
2 opendeferred goal
split ; exact HE |
2 opendeferred goal
exists b, t
2 opendeferred goal
split ; exact Hb |
2 opendeferred goal
split ; rewrite <- Hj ; exact taken_target_in_ _ _ _ Ht |
2 opendeferred goal
split ; reflexivity |
2 opendeferred goal
destruct is_pollt eqn: Ep ; left ; reflexivity | right
2 opendeferred goal
exists out
2 opendeferred goal
split ; exact Ho |
2 opendeferred goal
destruct Hat as live & Hw & _ & Hjc | access & rest′ & live′ & E′ & _ ; | discriminate E'
2 opendeferred goal
rewrite walks_nil_ _ _ Hw
2 opendeferred goal
exact Hjct Ht Ep
deferred goal
+destruct return_step_next_ _ _ Hret as caller & pd & callers & e & m′ & Hc & →
rewrite Hc in Hcall
inversion Hcall as | fp fps Hpk Hrest ; subst
simpl
split ; exact parked_resume_ _ _ _ _ Hpk | exact Hrest
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
An instruction i that continues keeps inv: the pass's next position holds (at_pos_continue), unless the step doomed the frame.
Proof 28 steps Qed
Proof 28 steps Qed
An instruction that continues or calls keeps inv.
Explore proof 5 tactics
Initial goal
intros ge md c c′ s l i rest j Hge Hmd Hr Ha Hs H
destruct step_exec_cons_ _ _ _ _ _ _ Ha Hs ltac:discriminate ltac:discriminate as Hdoom & out0 & od & Hi & Hdr & Hn
destruct inst_next_next_ _ _ _ _ _ _ Hn as e1 & l1 & m1 & Ho & → | g & xs & pd & callee & Ho & Hcf & →
2 openfocused goal
–eapply next_inv_continue ; eassumption
deferred goal
–eapply next_inv_call ; eassumption
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Explore proof 6 tactics
Initial goal
intros ge md c c′ s Hge Hmd Hr Hs H
destruct fr_atc_framec as xs l | l from | l | i rest j eqn: Ha
4 openfocused goal
focused goal
–exact next_inv_snapshot_ _ _ _ _ _ _ Hge Hmd Hr Ha Hs H
3 opendeferred goal
deferred goal
–exact next_inv_enter_ _ _ _ _ _ _ Hge Hmd Hr Ha Hs H
2 opendeferred goal
–exact next_inv_jump_ _ _ _ _ _ _ Hge Hmd Hr Ha Hs H
–exact next_inv_inst_ _ _ _ _ _ _ _ _ Hge Hmd Hr Ha Hs H
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The pass relies on no fact across an allocation, of a heap object or of a named local, and an allocation is not a check_function.
Explore proof 1 tactics
Initial goal
intros s i d & c & al & args & → | x & size & → ; destruct c | ; split ; reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
An instruction that allocates, a heap object or a named local at a base above 0, keeps inv; the pass keeps no fact across it.
Proof 39 steps Qed
Explore proof 20 tactics
Initial goal
intros ge md c q k s base s′ Hr Hs He Hal Hin & Hpos & Hpt Hcall
unfold inv in *
simpl in *
destruct step_fresh_kept_ _ _ _ Hs as Halign _
destruct R.fresh_allocation_ _ _ _ _ Hr Halign He Hal as Hb0 & _ _
destruct fr_atc_framec as xs l | l from | l | i rest j eqn: Ha
4 openfocused goal
focused goal
focused goal
–destruct step_snapshot_fresh_ _ _ _ _ _ Ha Hs base as Hc & Hf & Hl & Hd & Ha′
4 opendeferred goal
deferred goal
deferred goal
rewrite Hc
4 opendeferred goal
deferred goal
deferred goal
split ; | exact Hcall
4 opendeferred goal
deferred goal
deferred goal
split ; rewrite Hf ; exact Hin |
4 opendeferred goal
deferred goal
deferred goal
split ; intros x b Hx ; rewrite Hl in Hx ; exact Hpos_ _ Hx |
4 opendeferred goal
deferred goal
deferred goal
destruct Hpt as Hd0 | Hp ; left ; rewrite Hd ; exact Hd0 | right
4 opendeferred goal
deferred goal
deferred goal
eapply point_ok_entry ; exact Hp | left ; exact Ha | exact Hf | exact Ha′
3 opendeferred goal
deferred goal
deferred goal
–exfalso
3 opendeferred goal
deferred goal
exact step_enter_fresh_ _ _ _ _ _ Ha Hs
2 opendeferred goal
deferred goal
–exfalso
2 opendeferred goal
unfold step in Hs
2 opendeferred goal
rewrite Ha in Hs
2 opendeferred goal
exact jump_step_not_fresh_ _ _ _ _ _ Hs
deferred goal
–exact alloc_inv_inst_ _ _ _ _ _ base s′ _ _ _ _ Hr Ha Hs Hb0 conjconjHin conjHpos Hpt Hcall
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A covered access is a raw access, which the pass relies on facts for.
Explore proof 5 tactics
Initial goal
unfold covered_access , relies
intros s i q lo hi r al H
destruct raw_accessi ; | discriminate H
rewrite ! orb_true_r
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The runtime's action at a safepoint keeps inv: no fact is live across a poll edge, and before an instruction the pass relies on facts for, the regions are unchanged (spares_any).
Proof 43 steps Qed
Explore proof 5 tactics
Initial goal
intros ge md st st′ Hge Hmd Hr Hs H
destruct Hs as c c′ s E | c q k s base s′ E He Hal | c s s′ m′ Hd Hact
3 openfocused goal
focused goal
–eapply next_inv ; eauto
2 opendeferred goal
deferred goal
–eapply alloc_inv ; eauto
deferred goal
–eapply safepoint_inv ; eauto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
From a ready start where it holds, inv holds in every state a run reaches.
Explore proof 4 tactics
Initial goal
intros ge md st st′ Hge Hmd Hfree H
induction H as st st′ Hs | st | st1 st2 st3 H12 IH1 H23 IH2 ; intros Hr Hi ; auto
2 openfocused goal
–eapply mstep_inv ; eauto
deferred goal
–apply IH2 ; exact mreachable_ready_ _ _ Hfree H12 Hr | exact IH1Hr Hi
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
inv holds where a run starts: at the entry of a checked module's function, with no caller.
Explore proof 3 tactics
Initial goal
intros ge md f xs fr m fuel s Hmd Hin Hc
split ; | constructor
exact call_frame_ok_ _ _ _ _ _ Hmd Hin Hc
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
No unchecked access
In a ready state where inv holds, a frame that is not doomed runs no raw access, and no raw call, to an unchecked outcome, unless the pass accepted the access by hull_covered/7, with facts that hold and dominate (hull_case). Chain.v's Hull closes that case with Single.v's invariant.
Explore proof 23 tactics
Initial goal
intros ge md c s l i rest j why _ & Hpos & Hpt _ Hr Hd Ha Hi
simpl in *
assert Hfit : objects_fitm_regionsc_memc by exact R.address_space_ _ Hr
destruct Hpt as Hd0 | Hp ; congruence |
destruct point_ok_exec_inv_ _ _ _ _ _ _ Hp Ha as E & b & out & k & _ & Hb & _ & _ & Hk & Hat
destruct Hat as live & Hw & Hdom & Hl | access & rest′ & live′ & E′ & _ & _ & Hpc
2 openfocused goal
–destruct walks_cons_ _ _ _ _ Hw as rest′ & live′ & Hc & _
2 opendeferred goal
destruct raw_accessi as q x off need | eqn: Hra
3 openfocused goal
deferred goal
+assert Hrel : reliesfn_srcmd fr_fnc_framec i = true by unfold relies ; rewrite Hra , ! orb_true_r ; reflexivity
3 opendeferred goal
deferred goal
destruct generic_access_not_unchecked_ _ _ _ _ _ _ _ _ q x off need why Hfit HlHrel raw_access_not_special_ _ Hra Hc Hra as Hn | fa & Hfa & Hh ; left ; exact Hn | right ; exists b, k, live, fa, q
3 opendeferred goal
deferred goal
repeat split ; eassumption |
3 opendeferred goal
deferred goal
split ; exact HlHrel |
3 opendeferred goal
deferred goal
repeat split ; eassumption |
3 opendeferred goal
deferred goal
exact Hh
2 opendeferred goal
deferred goal
+destruct Hi as Hi | r & cl & args & → ; congruence |
2 opendeferred goal
rewrite raw_call_alone in Hc
2 opendeferred goal
discriminate Hc
deferred goal
–injection E′ as ← _
left
destruct Hpc as fb & pre & Hcov & _ & Hh | _ & r & q & args & p & → & Hq & Hc
2 openfocused goal
+destruct Hhfb or_introleq_refl as p & Eq & _ & Hpass
2 opendeferred goal
exact covered_access_not_unchecked_ _ _ _ _ _ _ _ _ _ _ Hfit Hcov Eq Hpass
deferred goal
+exact raw_call_checked_ _ _ _ _ _ _ _ Hq Hc
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The same of every state of a run of a checked module's function that starts ready, where the genv's free is R's.
Explore proof 5 tactics
Initial goal
intros ge md f xs fr m fuel s0 c s l i rest j why Hmd Hge Hfree Hin Hcf H0 Hreach
eapply access_not_unchecked
3 openfocused goal
shelved goal
–eapply mreachable_inv ; eauto
2 opendeferred goal
exact start_inv_ _ _ _ _ _ _ s0 Hmd Hin Hcf
deferred goal
–exact mreachable_ready_ _ _ Hfree Hreach H0
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The interpreter's runtime
The same for the interpreter's runtime.
Under the interpreter's runtime, in every state of a run of a checked module's function that starts ready, a frame that is not doomed runs no raw access or raw call to unchecked, unless the pass accepted it by hull_covered/7 (Chain.v's interp_access_checked closes that case).
Explore proof 2 tactics
Initial goal
intros md globals f xs fr m fuel s0 c s l i rest j why ge Hmd Hin Hcf H0 Hreach Hd Ha Hi
exact InterpPersistence.run_access_not_uncheckedge md f xs fr m fuel s0 c s l i rest j why Hmd eq_refl eq_refl Hin Hcf H0 Hreach Hd Ha Hi
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.