Fil-C on Nix

Filnix wiki

the formal campaign

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

DecisionWhy
the pass's position is a relation (walks, at_pos), not a program counterchecked_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 nothingits check_ahead's fact does not hold; what it may still do is the check_ahead corollary's
spares is no hypothesis of the theoremsevery 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 freeSoundness.v covers it by Runtime.v's free_checked
From Stdlib Require Import String ZArith List Bool Lia Relations
From Nanofil Require Import Term Maps Syntax Cfg Values Memory Runtime Ops Semantics Machine Validate Coverage Evidence Walk Steps Invariant
Import ListNotations
Open Scope Z_scope

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.

49Definition hull_casege : genv md : module c : config l : name i : inst rest : listinst : Prop ≔
let f ≔ fr_fnc_framec in
∃b k live fa q, find_blockl fn_blocksf = Someb ∧ i :: rest = skipnk b_instsb ∧ facts_holdge c_memc fr_envc_framec live ∧ live_domf l k live ∧ fact_ofq live = Somefa ∧ hull_coveredi q f_pfa f_lofa f_alfa live s_oncefn_srcmd f = true

The proofs over the runs of Machine R, for any runtime R.

58Module Persistence R : Runtime
60Module I ≔ Invariant R
Import I
Import RM

Each step keeps the invariant

Allocating the named local x at a base above 0 keeps every local above 0 (locals_pos).

68Lemma locals_pos_put
∀ fr x base fr′
0 < base
fr_localsfr′ = putx Somebase fr_localsfr
Explore proof 3 tactics

Initial goal

⊢
∀fr : frame x : name base : Z, locals_posfr → 0 < base → ∀fr′ : frame, fr_localsfr′ = putx Somebase fr_localsfr → locals_posfr′

intros fr x base Hpos Hb fr′ Hl y b H

fr :
x :
base :
Z
Hpos :
Hb :
0 < base
fr′ :
Hl :
fr_localsfr′ = putx Somebase fr_localsfr
y :
b :
Z
H :
lookupy fr_localsfr′ = SomeSomeb
⊢
0 < b

rewrite Hl , lookup_put in H

fr :
x :
base :
Z
Hpos :
Hb :
0 < base
fr′ :
Hl :
fr_localsfr′ = putx Somebase fr_localsfr
y :
b :
Z
H :
→
SomeSomebase
=
SomeSomeb
⊢
0 < b

destruct name_eqby x ; injection H as ← ; exact Hb | exact Hpos_ _ H

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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

A call is not ahead-transparent, so a doomed frame never makes one.

78Lemma ahead_call
∀ r callee args
ahead_transparentCallr callee args = false
Explore proof 1 tactics

Initial goal

⊢
∀r : call_result callee : value args : listarg, ahead_transparentCallr callee args = false

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
reflexivity

Nor is a raw call.

82Lemma ahead_raw_call
∀ r callee args
ahead_transparentRawCallr callee args = false
Explore proof 1 tactics

Initial goal

⊢
∀r : call_result callee : value args : listarg, ahead_transparentRawCallr callee args = false

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
reflexivity

A step at a variadic function's snapshot keeps inv: it enters the entry block.

87Lemma next_inv_snapshot
∀ ge md c c′ s xs l
ge_modulege = md
stepge c = Nextc′
invge md c, s
invge md c′, s
Explore proof 10 tactics

Initial goal

⊢
∀ge : genv md : module c c′ : config s : R.state xs : listword l : name, ge_modulege = md → checked_modulemd → ready_statec, s → fr_atc_framec = Snapshotxs l → stepge c = Nextc′ → invge md c, s → invge md c′, s

intros ge md c c′ s xs l Hge Hmd Hr Ha Hs Hin & Hpos & Hpt Hcall

ge :
md :
c, c′ :
s :
R.state
xs :
listword
l :
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
Hin :
InIFuncfr_fnc_framefstc, s md
Hpos :
Hpt :
fr_doomedc_framefstc, s ≠ None ∨ point_okge md c_memfstc, s c_framefstc, s
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersfstc, s
⊢
invge md c′, s

unfold inv

ge :
md :
c, c′ :
s :
R.state
xs :
listword
l :
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
Hin :
InIFuncfr_fnc_framefstc, s md
Hpos :
Hpt :
fr_doomedc_framefstc, s ≠ None ∨ point_okge md c_memfstc, s c_framefstc, s
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersfstc, s
⊢
frame_okge md c_memfstc′, s c_framefstc′, s ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersfstc′, s

simpl in *

ge :
md :
c, c′ :
s :
R.state
xs :
listword
l :
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

destruct step_snapshot_ _ _ _ _ Ha Hs as Hc & Hf & Hl & Hd & Ha′

ge :
md :
c, c′ :
s :
R.state
xs :
listword
l :
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hc :
Ha′ :
fr_atc_framec′ = Enterl None
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

rewrite Hc

ge :
md :
c, c′ :
s :
R.state
xs :
listword
l :
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hc :
Ha′ :
fr_atc_framec′ = Enterl None
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc

split ; | exact Hcall

ge :
md :
c, c′ :
s :
R.state
xs :
listword
l :
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hc :
Ha′ :
fr_atc_framec′ = Enterl None
⊢
frame_okge md c_memc′ c_framec′

split ; rewrite Hf ; exact Hin |

ge :
md :
c, c′ :
s :
R.state
xs :
listword
l :
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hc :
Ha′ :
fr_atc_framec′ = Enterl None
⊢
locals_posc_framec′ ∧ fr_doomedc_framec′ ≠ None ∨ point_okge md c_memc′ c_framec′

split ; intros x b Hx ; rewrite Hl in Hx ; exact Hpos_ _ Hx |

ge :
md :
c, c′ :
s :
R.state
xs :
listword
l :
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hc :
Ha′ :
fr_atc_framec′ = Enterl None
⊢
fr_doomedc_framec′ ≠ None ∨ point_okge md c_memc′ c_framec′

destruct Hpt as Hd0 | Hp ; left ; rewrite Hd ; exact Hd0 | right

ge :
md :
c, c′ :
s :
R.state
xs :
listword
l :
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hc :
Ha′ :
fr_atc_framec′ = Enterl None
⊢
point_okge md c_memc′ c_framec′

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
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′

Entering a block keeps inv (enter_point_ok).

100Lemma next_inv_enter
∀ ge md c c′ s l from
ge_modulege = md
stepge c = Nextc′
invge md c, s
invge md c′, s
Explore proof 10 tactics

Initial goal

⊢
∀ge : genv md : module c c′ : config s : R.state l : name from : optionname, ge_modulege = md → checked_modulemd → ready_statec, s → fr_atc_framec = Enterl from → stepge c = Nextc′ → invge md c, s → invge md c′, s

intros ge md c c′ s l from Hge Hmd Hr Ha Hs Hin & Hpos & Hpt Hcall

ge :
md :
c, c′ :
s :
R.state
l :
from :
optionname
Hge :
ge_modulege = md
Hr :
Ha :
Hs :
stepge c = Nextc′
Hin :
InIFuncfr_fnc_framefstc, s md
Hpos :
Hpt :
fr_doomedc_framefstc, s ≠ None ∨ point_okge md c_memfstc, s c_framefstc, s
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersfstc, s
⊢
invge md c′, s

unfold inv

ge :
md :
c, c′ :
s :
R.state
l :
from :
optionname
Hge :
ge_modulege = md
Hr :
Ha :
Hs :
stepge c = Nextc′
Hin :
InIFuncfr_fnc_framefstc, s md
Hpos :
Hpt :
fr_doomedc_framefstc, s ≠ None ∨ point_okge md c_memfstc, s c_framefstc, s
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersfstc, s
⊢
frame_okge md c_memfstc′, s c_framefstc′, s ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersfstc′, s

simpl in *

ge :
md :
c, c′ :
s :
R.state
l :
from :
optionname
Hge :
ge_modulege = md
Hr :
Ha :
Hs :
stepge c = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

pose proof enter_point_ok_ _ _ _ _ _ Hmd Hin Ha Hs as Hep

ge :
md :
c, c′ :
s :
R.state
l :
from :
optionname
Hge :
ge_modulege = md
Hr :
Ha :
Hs :
stepge c = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hep :
point_okge md c_memc c_framec → point_okge md c_memc′ c_framec′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

destruct step_enter_ _ _ _ _ Ha Hs as b & e & _ & _ & →

ge :
md :
s :
R.state
l :
from :
optionname
Hge :
ge_modulege = md
Hr :
Ha :
e :
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc

simpl in *

ge :
md :
s :
R.state
l :
from :
optionname
Hge :
ge_modulege = md
Hr :
Ha :
e :
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
⊢
frame_okge md c_memc fr_fn ≔ fr_fnc_framec; fr_env ≔ e; fr_locals ≔ fr_localsc_framec; fr_doomed ≔ fr_doomedc_framec; fr_at ≔ Execl b_instsb b_jumpb ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc

split ; | exact Hcall

ge :
md :
s :
R.state
l :
from :
optionname
Hge :
ge_modulege = md
Hr :
Ha :
e :
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc

split ; exact Hin |

ge :
md :
s :
R.state
l :
from :
optionname
Hge :
ge_modulege = md
Hr :
Ha :
e :
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc

split ; exact Hpos |

ge :
md :
s :
R.state
l :
from :
optionname
Hge :
ge_modulege = md
Hr :
Ha :
e :
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc

destruct Hpt as Hd0 | Hp ; left ; exact Hd0 | right ; exact HepHp

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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

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).

114Lemma next_inv_jump
∀ ge md c c′ s l j
ge_modulege = md
fr_atc_framec = Execl [ ] j
stepge c = Nextc′
invge md c, s
invge md c′, s
Explore proof 32 tactics

Initial goal

⊢
∀ge : genv md : module c c′ : config s : R.state l : name j : jump, ge_modulege = md → checked_modulemd → ready_statec, s → fr_atc_framec = Execl [ ] j → stepge c = Nextc′ → invge md c, s → invge md c′, s

intros ge md c c′ s l j Hge Hmd Hr Ha Hs Hin & Hpos & Hpt Hcall

ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
stepge c = Nextc′
Hin :
InIFuncfr_fnc_framefstc, s md
Hpos :
Hpt :
fr_doomedc_framefstc, s ≠ None ∨ point_okge md c_memfstc, s c_framefstc, s
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersfstc, s
⊢
invge md c′, s

unfold inv

ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
stepge c = Nextc′
Hin :
InIFuncfr_fnc_framefstc, s md
Hpos :
Hpt :
fr_doomedc_framefstc, s ≠ None ∨ point_okge md c_memfstc, s c_framefstc, s
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersfstc, s
⊢
frame_okge md c_memfstc′, s c_framefstc′, s ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersfstc′, s

simpl in *

ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
stepge c = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

unfold step in Hs

ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
match fr_atc_framec with
Snapshot_ :: _ as xs l
⇒
negbforallbsnapshot_word xs
→
Stuck"snapshot"
else
Freshheap_req16 8 × Z.of_natDatatypes.lengthxs λbase : Z ⇒ c_frame ≔ fr_fn ≔ fr_fnc_framec; fr_env ≔ putva_snapshot WPtrptr_addr ≔ base; ptr_cap ≔ Robase fr_envc_framec; fr_locals ≔ fr_localsc_framec; fr_doomed ≔ fr_doomedc_framec; fr_at ≔ Enterl None; c_callers ≔ c_callersc; c_mem ≔ snapshot_valuesxs base allocatedc_memc heap_req16 8 × Z.of_natDatatypes.lengthxs base; c_fuel ≔ c_fuelc
Enterl from
⇒
else
or_stuck"block"
Execl [ ] j
⇒
jump_stepge c l j
Execl i :: rest j
⇒
match let* why ≔ fr_doomedc_framec in if ahead_transparenti then None else Somewhy with
Somewhy
⇒
None
⇒
or_stuck"instruction"
let* out0 ≔ inst_stepge c_framec c_memc i in
let* od ≔ doomed_resultge c_framec c_memc i out0 in
Someinst_nextc l rest j fstod sndod
=
Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

rewrite Ha in Hs

ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

destruct jump_step_next_ _ _ _ _ Hs as t & Ht & → | Hd & o & Hret

2 open

focused goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

+simpl

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
⊢
frame_okge md c_memc with_pointc_framec Enteredge_labelt Somel ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

split ; | exact Hcall

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

split ; exact Hin |

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

split ; exact Hpos |

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

destruct Hpt as Hd0 | Hp ; left ; exact Hd0 | right

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

destruct point_ok_exec_inv_ _ _ _ _ _ _ Hp Ha as E & b & out & k & HE & Hb & Ho & Hj & _ & Hat

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hat :
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

unfold point_ok

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hat :
⊢
∃ E0 : listname × listfact  ,
∧
Enterl0 Somep
⇒
∃bp : block t0 : target, find_blockp fn_blocksfr_fnwith_pointc_framec Enteredge_labelt Somel = Somebp ∧ Int0 jump_targetsb_jumpbp ∧ edge_labelt0 = l0 ∧ is_pollt0 = true ∨ ∃out0 : listfact, lookupp E0 = Someout0 ∧ facts_holdge c_memc fr_envwith_pointc_framec Enteredge_labelt Somel out0
Execl0 is j0
⇒
∃b0 : block out0 : listfact k0 : nat, find_blockl0 fn_blocksfr_fnwith_pointc_framec Enteredge_labelt Somel = Someb0 ∧ lookupl0 E0 = Someout0 ∧ j0 = b_jumpb0 ∧ is = skipnk0 b_instsb0 ∧ at_posge fn_srcmd fr_fnwith_pointc_framec Enteredge_labelt Somel c_memc with_pointc_framec Enteredge_labelt Somel is j0 out0 fr_fnwith_pointc_framec Enteredge_labelt Somel l0 k0
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

cbv zeta

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hat :
⊢
∃ E0 : listname × listfact  ,
∧
Enterl0 Somep
⇒
∃bp : block t0 : target, find_blockp fn_blocksfr_fnwith_pointc_framec Enteredge_labelt Somel = Somebp ∧ Int0 jump_targetsb_jumpbp ∧ edge_labelt0 = l0 ∧ is_pollt0 = true ∨ ∃out0 : listfact, lookupp E0 = Someout0 ∧ facts_holdge c_memc fr_envwith_pointc_framec Enteredge_labelt Somel out0
Execl0 is j0
⇒
∃b0 : block out0 : listfact k0 : nat, find_blockl0 fn_blocksfr_fnwith_pointc_framec Enteredge_labelt Somel = Someb0 ∧ lookupl0 E0 = Someout0 ∧ j0 = b_jumpb0 ∧ is = skipnk0 b_instsb0 ∧ at_posge fn_srcmd fr_fnwith_pointc_framec Enteredge_labelt Somel c_memc with_pointc_framec Enteredge_labelt Somel is j0 out0 fr_fnwith_pointc_framec Enteredge_labelt Somel l0 k0
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

simpl

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hat :
⊢
∃E0 : listname × listfact, pass_exitsfn_srcmd fr_fnc_framec fr_fnc_framec = SomeE0 ∧ ∃bp : block t0 : target, find_blockl fn_blocksfr_fnc_framec = Somebp ∧ Int0 jump_targetsb_jumpbp ∧ edge_labelt0 = edge_labelt ∧ is_pollt0 = true ∨ ∃out0 : listfact, lookupl E0 = Someout0 ∧ facts_holdge c_memc fr_envc_framec out0
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

exists E

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hat :
⊢
pass_exitsfn_srcmd fr_fnc_framec fr_fnc_framec = SomeE ∧ ∃bp : block t0 : target, find_blockl fn_blocksfr_fnc_framec = Somebp ∧ Int0 jump_targetsb_jumpbp ∧ edge_labelt0 = edge_labelt ∧ is_pollt0 = true ∨ ∃out0 : listfact, lookupl E = Someout0 ∧ facts_holdge c_memc fr_envc_framec out0
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

split ; exact HE |

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hat :
⊢
∃bp : block t0 : target, find_blockl fn_blocksfr_fnc_framec = Somebp ∧ Int0 jump_targetsb_jumpbp ∧ edge_labelt0 = edge_labelt ∧ is_pollt0 = true ∨ ∃out0 : listfact, lookupl E = Someout0 ∧ facts_holdge c_memc fr_envc_framec out0
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

exists b, t

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hat :
⊢
find_blockl fn_blocksfr_fnc_framec = Someb ∧ Int jump_targetsb_jumpb ∧ edge_labelt = edge_labelt ∧ is_pollt = true ∨ ∃out0 : listfact, lookupl E = Someout0 ∧ facts_holdge c_memc fr_envc_framec out0
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

split ; exact Hb |

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hat :
⊢
Int jump_targetsb_jumpb ∧ edge_labelt = edge_labelt ∧ is_pollt = true ∨ ∃out0 : listfact, lookupl E = Someout0 ∧ facts_holdge c_memc fr_envc_framec out0
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

split ; rewrite <- Hj ; exact taken_target_in_ _ _ _ Ht |

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hat :
⊢
edge_labelt = edge_labelt ∧ is_pollt = true ∨ ∃out0 : listfact, lookupl E = Someout0 ∧ facts_holdge c_memc fr_envc_framec out0
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

split ; reflexivity |

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hat :
⊢
is_pollt = true ∨ ∃out0 : listfact, lookupl E = Someout0 ∧ facts_holdge c_memc fr_envc_framec out0
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

destruct is_pollt eqn: Ep ; left ; reflexivity | right

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hat :
Ep :
is_pollt = false
⊢
∃out0 : listfact, lookupl E = Someout0 ∧ facts_holdge c_memc fr_envc_framec out0
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

exists out

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hat :
Ep :
is_pollt = false
⊢
lookupl E = Someout ∧ facts_holdge c_memc fr_envc_framec out
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

split ; exact Ho |

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hat :
Ep :
is_pollt = false
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

destruct Hat as live & Hw & _ & Hjc | access & rest′ & live′ & E′ & _ ; | discriminate E'

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec [ ] live out
Hjc :
Ep :
is_pollt = false
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

rewrite walks_nil_ _ _ Hw

2 open

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Ht :
taken_targetge c_framec j = Somet
E :
listname × listfact
out :
listfact
k :
nat
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec [ ] live out
Hjc :
Ep :
is_pollt = false
deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

exact Hjct Ht Ep

deferred goal
ge :
md :
c, c′ :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
Hs :
jump_stepge c l j = Nextc′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc′
⊢
frame_okge md c_memc′ c_framec′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc′

+destruct return_step_next_ _ _ Hret as caller & pd & callers & e & m′ & Hc & →

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
caller :
callers :
listframe × pending
e :
m′ :
Memory.mem
Hs :
jump_stepge c l j = Nextc_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Hd :
Hret :
return_stepc o = Nextc_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc
Hc :
c_callersc = caller, pd :: callers
⊢
frame_okge md c_memc_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc c_framec_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc

rewrite Hc in Hcall

ge :
md :
s :
R.state
l :
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl [ ] j
caller :
callers :
listframe × pending
e :
m′ :
Memory.mem
Hs :
jump_stepge c l j = Nextc_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp caller, pd :: callers
Hd :
Hret :
return_stepc o = Nextc_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc
Hc :
c_callersc = caller, pd :: callers
⊢
frame_okge md c_memc_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc c_framec_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc

inversion Hcall as | fp fps Hpk Hrest ; subst

ge :
s :
R.state
l :
j :
Hr :
Ha :
fr_atc_framec = Execl [ ] j
caller :
callers :
listframe × pending
e :
m′ :
Memory.mem
Hs :
jump_stepge c l j = Nextc_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc
Hpt :
Hcall :
Forallλfp : frame × pending ⇒ parkedge_modulege fstfp caller, pd :: callers
Hd :
Hret :
return_stepc o = Nextc_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc
Hc :
c_callersc = caller, pd :: callers
Hrest :
Forallλfp : frame × pending ⇒ parkedge_modulege fstfp callers
Hpk :
parkedge_modulege fstcaller, pd
⊢
frame_okge ge_modulege c_memc_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc c_framec_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc ∧ Forallλfp : frame × pending ⇒ parkedge_modulege fstfp c_callersc_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc

simpl

ge :
s :
R.state
l :
j :
Hr :
Ha :
fr_atc_framec = Execl [ ] j
caller :
callers :
listframe × pending
e :
m′ :
Memory.mem
Hs :
jump_stepge c l j = Nextc_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc
Hpt :
Hcall :
Forallλfp : frame × pending ⇒ parkedge_modulege fstfp caller, pd :: callers
Hd :
Hret :
return_stepc o = Nextc_frame ≔ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller; c_callers ≔ callers; c_mem ≔ m′; c_fuel ≔ c_fuelc
Hc :
c_callersc = caller, pd :: callers
Hrest :
Forallλfp : frame × pending ⇒ parkedge_modulege fstfp callers
Hpk :
parkedge_modulege fstcaller, pd
⊢
frame_okge ge_modulege m′ fr_fn ≔ fr_fncaller; fr_env ≔ e; fr_locals ≔ fr_localscaller; fr_doomed ≔ fr_doomedcaller; fr_at ≔ fr_atcaller ∧ Forallλfp : frame × pending ⇒ parkedge_modulege fstfp callers

split ; exact parked_resume_ _ _ _ _ Hpk | exact Hrest

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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
+simpl
split ; | exact Hcall
split ; exact Hin |
split ; exact Hpos |
destruct Hpt as Hd0 | Hp ; left ; exact Hd0 | right
destruct point_ok_exec_inv_ _ _ _ _ _ _ Hp Ha as E & b & out & k & HE & Hb & Ho & Hj & _ & Hat
unfold point_ok
cbv zeta
simpl
exists E
split ; exact HE |
exists b, t
split ; exact Hb |
split ; rewrite <- Hj ; exact taken_target_in_ _ _ _ Ht |
split ; reflexivity |
destruct is_pollt eqn: Ep ; left ; reflexivity | right
exists out
split ; exact Ho |
destruct Hat as live & Hw & _ & Hjc | access & rest′ & live′ & E′ & _ ; | discriminate E'
rewrite walks_nil_ _ _ Hw
exact Hjct Ht Ep
+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

An instruction i that continues keeps inv: the pass's next position holds (at_pos_continue), unless the step doomed the frame.

138Lemma next_inv_continue
∀ ge md c s l i rest j out0 od e1 l1 m1
fr_atc_framec = Execl i :: rest j
inst_stepge c_framec c_memc i = Someout0
doomed_resultge c_framec c_memc i out0 = Someod
fstod = IContinuee1 l1 m1
invge md c, s
invge md mkConfigmkFramefr_fnc_framec e1 l1 sndod Execl rest j c_callersc m1 c_fuelc, s
Proof 28 steps Qed
intros ge md c s l i rest j out0 od e1 l1 m1 Hmd Hr Ha Hi Hdr Ho Hin & Hpos & Hpt Hcall
unfold inv
simpl in *
assert Hfit : objects_fitm_regionsc_memc by exact R.address_space_ _ Hr
split ; | exact Hcall
split ; exact Hin |
destruct fr_doomedc_framec as w | eqn: Ew
∗assert Hnd : fr_doomedc_framec ≠ None by rewrite Ew ; discriminate
destruct doomed_result_doomed_ _ _ _ _ _ Hnd Hdr as Hsd & Ho′ | e′ & Ho′ | o′ & Ho′ ; rewrite Ho in Ho' ; try discriminate Ho'
--subst out0
pose proof inst_step_locals_ _ _ _ _ _ _ Hi as Hl1
subst l1
split ; exact Hpos | left ; exact Hsd
--injection Ho' as _ → _
split ; exact Hpos | left ; exact Hsd
∗destruct Hpt as Hd0 | Hp ; congruence |
destruct doomed_result_fresh_ _ _ _ _ _ Ew Hdr as → | e′ & w & → ; simpl in Ho |- *
--subst out0
pose proof inst_step_locals_ _ _ _ _ _ _ Hi as Hl1
subst l1
split ; exact Hpos |
right
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 & _
eapply point_ok_exec ; simpl ; exact HE | reflexivity | exact Hb | exact Hout | exact Hj | symmetry ; exact Hrest |
eapply at_pos_continue ; exact Hmd | exact Hin | exact Hb | exact Hk | exact Hfit | exact Hpos | exact Hat | exact Hi | reflexivity
--injection Ho as _ ← _
split ; exact Hpos | left ; discriminate

A call keeps inv: the callee starts at its entry, and the caller waits with no fact (parked).

168Lemma next_inv_call
∀ ge md c s l i rest j out0 od g xs pd callee
ge_modulege = md
fr_atc_framec = Execl i :: rest j
fr_doomedc_framec = None ∨ ahead_transparenti = true
inst_stepge c_framec c_memc i = Someout0
doomed_resultge c_framec c_memc i out0 = Someod
fstod = ICallg xs pd
call_frameg xs = Somecallee
invge md c, s
Proof 28 steps Qed
intros ge md c s l i rest j out0 od g xs pd callee Hge Hmd Ha Hdoom Hi Hdr Ho Hcf Hin & Hpos & Hpt Hcall
unfold inv
simpl in *
assert Hd : fr_doomedc_framec = None ∧ out0 = ICallg xs pd ∧ sndod = None
{destruct fr_doomedc_framec as w | eqn: Ew
–assert Hnd : fr_doomedc_framec ≠ None by rewrite Ew ; discriminate
destruct doomed_result_doomed_ _ _ _ _ _ Hnd Hdr as _ & Ho′ | e′ & Ho′ | o′ & Ho′ ; rewrite Ho in Ho' ; try discriminate Ho'
subst out0
destruct inst_step_call_shape_ _ _ _ _ _ _ Hi as _ & r & cl & args & → | r & cl & args & → ; destruct Hdoom as Hdoom | Hdoom ; simpl in Hdoom ; discriminate Hdoom
–destruct doomed_result_fresh_ _ _ _ _ _ Ew Hdr as → | e′ & w & → ; simpl in Ho ; | discriminate Ho
auto
destruct Hd as Hd & → & Hsd
destruct inst_step_call_shape_ _ _ _ _ _ _ Hi as Hg & Hcl
rewrite Hge in Hg
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 & _
simpl
split ; exact call_frame_ok_ _ _ _ _ _ Hmd Hg Hcf |
constructor ; | exact Hcall
split ; exact Hin |
split ; exact Hpos |
split ; exact Hsd |
exists E, l, rest, j, b, out, Sk
simpl
repeat split ; assumption || reflexivity |
split ; symmetry ; exact Hrest |
eapply walks_after ; exact Hat | | ; destruct Hcl as r & cl & args & → | r & cl & args & → ; reflexivity

An instruction that continues or calls keeps inv.

203Lemma next_inv_inst
∀ ge md c c′ s l i rest j
ge_modulege = md
fr_atc_framec = Execl i :: rest j
stepge c = Nextc′
invge md c, s
invge md c′, s
Explore proof 5 tactics

Initial goal

⊢
∀ge : genv md : module c c′ : config s : R.state l : name i : inst rest : listinst j : jump, ge_modulege = md → checked_modulemd → ready_statec, s → fr_atc_framec = Execl i :: rest j → stepge c = Nextc′ → invge md c, s → invge md c′, s

intros ge md c c′ s l i rest j Hge Hmd Hr Ha Hs H

ge :
md :
c, c′ :
s :
R.state
l :
i :
rest :
listinst
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl i :: rest j
Hs :
stepge c = Nextc′
H :
invge md c, s
⊢
invge md c′, s

destruct step_exec_cons_ _ _ _ _ _ _ Ha Hs ltac:discriminate ltac:discriminate as Hdoom & out0 & od & Hi & Hdr & Hn

ge :
md :
c, c′ :
s :
R.state
l :
i :
rest :
listinst
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl i :: rest j
Hs :
stepge c = Nextc′
H :
invge md c, s
Hdoom :
fr_doomedc_framec = None ∨ ahead_transparenti = true
out0 :
od :
inst_out × optionreason
Hi :
inst_stepge c_framec c_memc i = Someout0
Hdr :
doomed_resultge c_framec c_memc i out0 = Someod
Hn :
inst_nextc l rest j fstod sndod = Nextc′
⊢
invge md c′, s

destruct inst_next_next_ _ _ _ _ _ _ Hn as e1 & l1 & m1 & Ho & → | g & xs & pd & callee & Ho & Hcf & →

2 open

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl i :: rest j
od :
inst_out × optionreason
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
Hs :
stepge c = Nextc_frame ≔ fr_fn ≔ fr_fnc_framec; fr_env ≔ e1; fr_locals ≔ l1; fr_doomed ≔ sndod; fr_at ≔ Execl rest j; c_callers ≔ c_callersc; c_mem ≔ m1; c_fuel ≔ c_fuelc
H :
invge md c, s
Hdoom :
fr_doomedc_framec = None ∨ ahead_transparenti = true
out0 :
Hi :
inst_stepge c_framec c_memc i = Someout0
Hdr :
doomed_resultge c_framec c_memc i out0 = Someod
Hn :
inst_nextc l rest j fstod sndod = Nextc_frame ≔ fr_fn ≔ fr_fnc_framec; fr_env ≔ e1; fr_locals ≔ l1; fr_doomed ≔ sndod; fr_at ≔ Execl rest j; c_callers ≔ c_callersc; c_mem ≔ m1; c_fuel ≔ c_fuelc
Ho :
fstod = IContinuee1 l1 m1
⊢
invge md c_frame ≔ fr_fn ≔ fr_fnc_framec; fr_env ≔ e1; fr_locals ≔ l1; fr_doomed ≔ sndod; fr_at ≔ Execl rest j; c_callers ≔ c_callersc; c_mem ≔ m1; c_fuel ≔ c_fuelc, s
focused goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl i :: rest j
od :
inst_out × optionreason
callee :
Hs :
stepge c = Nextc_frame ≔ callee; c_callers ≔ fr_fn ≔ fr_fnc_framec; fr_env ≔ fr_envc_framec; fr_locals ≔ fr_localsc_framec; fr_doomed ≔ sndod; fr_at ≔ Execl rest j, pd :: c_callersc; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
H :
invge md c, s
Hdoom :
fr_doomedc_framec = None ∨ ahead_transparenti = true
out0 :
Hi :
inst_stepge c_framec c_memc i = Someout0
Hdr :
doomed_resultge c_framec c_memc i out0 = Someod
Hn :
inst_nextc l rest j fstod sndod = Nextc_frame ≔ callee; c_callers ≔ fr_fn ≔ fr_fnc_framec; fr_env ≔ fr_envc_framec; fr_locals ≔ fr_localsc_framec; fr_doomed ≔ sndod; fr_at ≔ Execl rest j, pd :: c_callersc; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
g :
xs :
listword
Ho :
fstod = ICallg xs pd
Hcf :
call_frameg xs = Somecallee
⊢
invge md c_frame ≔ callee; c_callers ≔ fr_fn ≔ fr_fnc_framec; fr_env ≔ fr_envc_framec; fr_locals ≔ fr_localsc_framec; fr_doomed ≔ sndod; fr_at ≔ Execl rest j, pd :: c_callersc; c_mem ≔ c_memc; c_fuel ≔ c_fuelc, s

–eapply next_inv_continue ; eassumption

deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
Hge :
ge_modulege = md
Hr :
Ha :
fr_atc_framec = Execl i :: rest j
od :
inst_out × optionreason
callee :
Hs :
stepge c = Nextc_frame ≔ callee; c_callers ≔ fr_fn ≔ fr_fnc_framec; fr_env ≔ fr_envc_framec; fr_locals ≔ fr_localsc_framec; fr_doomed ≔ sndod; fr_at ≔ Execl rest j, pd :: c_callersc; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
H :
invge md c, s
Hdoom :
fr_doomedc_framec = None ∨ ahead_transparenti = true
out0 :
Hi :
inst_stepge c_framec c_memc i = Someout0
Hdr :
doomed_resultge c_framec c_memc i out0 = Someod
Hn :
inst_nextc l rest j fstod sndod = Nextc_frame ≔ callee; c_callers ≔ fr_fn ≔ fr_fnc_framec; fr_env ≔ fr_envc_framec; fr_locals ≔ fr_localsc_framec; fr_doomed ≔ sndod; fr_at ≔ Execl rest j, pd :: c_callersc; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
g :
xs :
listword
Ho :
fstod = ICallg xs pd
Hcf :
call_frameg xs = Somecallee
⊢
invge md c_frame ≔ callee; c_callers ≔ fr_fn ≔ fr_fnc_framec; fr_env ≔ fr_envc_framec; fr_locals ≔ fr_localsc_framec; fr_doomed ≔ sndod; fr_at ≔ Execl rest j, pd :: c_callersc; c_mem ≔ c_memc; c_fuel ≔ c_fuelc, s

–eapply next_inv_call ; eassumption

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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 & →
–eapply next_inv_continue ; eassumption
–eapply next_inv_call ; eassumption

A step that allocates nothing (Next) keeps inv, whatever the frame's point.

217Lemma next_inv
∀ ge md c c′ s
ge_modulege = md
stepge c = Nextc′
invge md c, s
invge md c′, s
Explore proof 6 tactics

Initial goal

⊢
∀ge : genv md : module c c′ : config s : R.state, ge_modulege = md → checked_modulemd → ready_statec, s → stepge c = Nextc′ → invge md c, s → invge md c′, s

intros ge md c c′ s Hge Hmd Hr Hs H

ge :
md :
c, c′ :
s :
R.state
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
H :
invge md c, s
⊢
invge md c′, s

destruct fr_atc_framec as xs l | l from | l | i rest j eqn: Ha

4 open

ge :
md :
c, c′ :
s :
R.state
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
H :
invge md c, s
xs :
listword
l :
⊢
invge md c′, s
focused goal
ge :
md :
c, c′ :
s :
R.state
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
H :
invge md c, s
l :
from :
optionname
Ha :
⊢
invge md c′, s
focused goal
ge :
md :
c, c′ :
s :
R.state
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
H :
invge md c, s
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
invge md c′, s
focused goal
ge :
md :
c, c′ :
s :
R.state
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
H :
invge md c, s
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
invge md c′, s

–exact next_inv_snapshot_ _ _ _ _ _ _ Hge Hmd Hr Ha Hs H

3 open

deferred goal
ge :
md :
c, c′ :
s :
R.state
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
H :
invge md c, s
l :
from :
optionname
Ha :
⊢
invge md c′, s
deferred goal
ge :
md :
c, c′ :
s :
R.state
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
H :
invge md c, s
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
invge md c′, s
deferred goal
ge :
md :
c, c′ :
s :
R.state
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
H :
invge md c, s
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
invge md c′, s

–exact next_inv_enter_ _ _ _ _ _ _ Hge Hmd Hr Ha Hs H

2 open

deferred goal
ge :
md :
c, c′ :
s :
R.state
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
H :
invge md c, s
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
invge md c′, s
deferred goal
ge :
md :
c, c′ :
s :
R.state
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
H :
invge md c, s
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
invge md c′, s

–exact next_inv_jump_ _ _ _ _ _ _ Hge Hmd Hr Ha Hs H

deferred goal
ge :
md :
c, c′ :
s :
R.state
Hge :
ge_modulege = md
Hr :
Hs :
stepge c = Nextc′
H :
invge md c, s
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
invge md c′, s

–exact next_inv_inst_ _ _ _ _ _ _ _ _ Hge Hmd Hr Ha Hs H

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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
–exact next_inv_snapshot_ _ _ _ _ _ _ Hge Hmd Hr Ha Hs H
–exact next_inv_enter_ _ _ _ _ _ _ Hge Hmd Hr Ha Hs H
–exact next_inv_jump_ _ _ _ _ _ _ Hge Hmd Hr Ha Hs H
–exact next_inv_inst_ _ _ _ _ _ _ _ _ Hge Hmd Hr Ha Hs H

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.

231Lemma relies_alloc_any
∀ s i
∃d c al args, i = Letd c Allocal args ∨ ∃x size, i = LocalAllocx size
reliess i = false ∧ is_check_functioni = false
Explore proof 1 tactics

Initial goal

⊢
∀s : src i : inst, ∃d : name c : class al : Z args : listvalue, i = Letd c Allocal args ∨ ∃x : name size : Z, i = LocalAllocx size → reliess i = false ∧ is_check_functioni = false

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
intros s i d & c & al & args & → | x & size & → ; destruct c | ; split ; reflexivity

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.

240Lemma alloc_inv_inst
∀ ge md c q k s base s′ l i rest j
fr_atc_framec = Execl i :: rest j
stepge c = Freshq k
0 < base
invge md c, s
invge md kbase, s′
Proof 39 steps Qed
intros ge md c q k s base s′ l i rest j Hr Ha Hs Hb0 Hin & Hpos & Hpt Hcall
unfold inv in *
simpl in *
destruct step_exec_cons_ _ _ _ _ _ _ Ha Hs ltac:discriminate ltac:discriminate as Hdoom & out0 & od & Hi & Hdr & Hn
destruct inst_next_fresh_ _ _ _ _ _ _ _ Hn as k0 & Ho & Hk
assert Hout : fstod = out0 ∧ fr_doomedc_framec = None → sndod = None
{destruct fr_doomedc_framec as w | eqn: Ew
–assert Hnd : fr_doomedc_framec ≠ None by rewrite Ew ; discriminate
destruct doomed_result_doomed_ _ _ _ _ _ Hnd Hdr as _ & Ho′ | e′ & Ho′ | o′ & Ho′ ; rewrite Ho in Ho' ; try discriminate Ho'
split ; congruence | discriminate
–destruct doomed_result_fresh_ _ _ _ _ _ Ew Hdr as → | e′ & w & → ; simpl in Ho |- * ; auto | discriminate Ho
destruct Hout as Hout Hsd
rewrite Ho in Hout
subst out0
pose proof inst_step_fresh_shape_ _ _ _ _ _ Hi as Hshape
rewrite Hk
destruct k0base as e locals m′ eqn: Ek
simpl
assert Hlocals : locals = fr_localsc_framec ∨ ∃x size, i = LocalAllocx size ∧ locals = putx Somebase fr_localsc_framec
{destruct Hshape as d & cl & al & args & → & Hl | x & size & → & Hl ; specialize Hlbase ; rewrite Ek in Hl ; simpl in Hl ; eauto
split ; | exact Hcall
split ; exact Hin |
split
{destruct Hlocals as → | x & size & _ & → ; exact Hpos |
eapply locals_pos_put ; exact Hpos | exact Hb0 | reflexivity
destruct fr_doomedc_framec as w | eqn: Ew
+left
destruct sndod eqn: Esd ; discriminate |
assert Hnd : fr_doomedc_framec ≠ None by rewrite Ew ; discriminate
exfalso
exact proj1doomed_result_doomed_ _ _ _ _ _ Hnd Hdr Esd
+rewrite Hsdeq_refl
right
destruct Hpt as Hd0 | Hp ; congruence |
destruct point_ok_exec_inv_ _ _ _ _ _ _ Hp Ha as E & b & out & kp & HE & Hb & Hout & Hj & Hkp & Hat
destruct skipn_cons_ _ _ _ _ eq_symHkp as _ & Hrest & _
destruct relies_alloc_anyfn_srcmd fr_fnc_framec i ltac:destruct Hshape as d & cl & al & args & → & _ | x & size & → & _ ; eauto 6 as Hrel Hcf
eapply point_ok_exec ; simpl ; exact HE | reflexivity | exact Hb | exact Hout | exact Hj | symmetry ; exact Hrest |
eapply at_pos_between ; exact walks_after_ _ _ _ _ _ _ _ _ _ _ Hat Hrel Hcf | apply live_dom_nil | apply facts_hold_nil

An allocation, at the base R's alloc gives with the new runtime state s', keeps inv: R's fresh base lies above 0.

282Lemma alloc_inv
∀ ge md c q k s base s′
stepge c = Freshq k
0 ≤ req_extentq
R.allocs q = Somebase, s′
invge md c, s
invge md kbase, s′
Explore proof 20 tactics

Initial goal

⊢
∀ge : genv md : module c : config q : alloc_req k : Z → config s : R.state base : Z s′ : R.state, ready_statec, s → stepge c = Freshq k → 0 ≤ req_extentq → R.allocs q = Somebase, s′ → invge md c, s → invge md kbase, s′

intros ge md c q k s base s′ Hr Hs He Hal Hin & Hpos & Hpt Hcall

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hin :
InIFuncfr_fnc_framefstc, s md
Hpos :
Hpt :
fr_doomedc_framefstc, s ≠ None ∨ point_okge md c_memfstc, s c_framefstc, s
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersfstc, s
⊢
invge md kbase, s′

unfold inv in *

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hin :
InIFuncfr_fnc_framefstc, s md
Hpos :
Hpt :
fr_doomedc_framefstc, s ≠ None ∨ point_okge md c_memfstc, s c_framefstc, s
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersfstc, s
⊢
frame_okge md c_memfstkbase, s′ c_framefstkbase, s′ ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersfstkbase, s′

simpl in *

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

destruct step_fresh_kept_ _ _ _ Hs as Halign _

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

destruct R.fresh_allocation_ _ _ _ _ Hr Halign He Hal as Hb0 & _ _

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

destruct fr_atc_framec as xs l | l from | l | i rest j eqn: Ha

4 open

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
xs :
listword
l :
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
focused goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
from :
optionname
Ha :
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
focused goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
focused goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

–destruct step_snapshot_fresh_ _ _ _ _ _ Ha Hs base as Hc & Hf & Hl & Hd & Ha′

4 open

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
xs :
listword
l :
Hc :
Ha′ :
fr_atc_framekbase = Enterl None
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
from :
optionname
Ha :
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

rewrite Hc

4 open

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
xs :
listword
l :
Hc :
Ha′ :
fr_atc_framekbase = Enterl None
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
from :
optionname
Ha :
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

split ; | exact Hcall

4 open

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
xs :
listword
l :
Hc :
Ha′ :
fr_atc_framekbase = Enterl None
⊢
frame_okge md c_memkbase c_framekbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
from :
optionname
Ha :
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

split ; rewrite Hf ; exact Hin |

4 open

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
xs :
listword
l :
Hc :
Ha′ :
fr_atc_framekbase = Enterl None
⊢
locals_posc_framekbase ∧ fr_doomedc_framekbase ≠ None ∨ point_okge md c_memkbase c_framekbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
from :
optionname
Ha :
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

split ; intros x b Hx ; rewrite Hl in Hx ; exact Hpos_ _ Hx |

4 open

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
xs :
listword
l :
Hc :
Ha′ :
fr_atc_framekbase = Enterl None
⊢
fr_doomedc_framekbase ≠ None ∨ point_okge md c_memkbase c_framekbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
from :
optionname
Ha :
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

destruct Hpt as Hd0 | Hp ; left ; rewrite Hd ; exact Hd0 | right

4 open

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
xs :
listword
l :
Hc :
Ha′ :
fr_atc_framekbase = Enterl None
⊢
point_okge md c_memkbase c_framekbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
from :
optionname
Ha :
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

eapply point_ok_entry ; exact Hp | left ; exact Ha | exact Hf | exact Ha′

3 open

deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
from :
optionname
Ha :
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

–exfalso

3 open

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
from :
optionname
Ha :
⊢
False
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

exact step_enter_fresh_ _ _ _ _ _ Ha Hs

2 open

deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

–exfalso

2 open

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
False
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

unfold step in Hs

2 open

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
match fr_atc_framec with
Snapshot_ :: _ as xs l
⇒
negbforallbsnapshot_word xs
→
Stuck"snapshot"
else
Freshheap_req16 8 × Z.of_natDatatypes.lengthxs λbase : Z ⇒ c_frame ≔ fr_fn ≔ fr_fnc_framec; fr_env ≔ putva_snapshot WPtrptr_addr ≔ base; ptr_cap ≔ Robase fr_envc_framec; fr_locals ≔ fr_localsc_framec; fr_doomed ≔ fr_doomedc_framec; fr_at ≔ Enterl None; c_callers ≔ c_callersc; c_mem ≔ snapshot_valuesxs base allocatedc_memc heap_req16 8 × Z.of_natDatatypes.lengthxs base; c_fuel ≔ c_fuelc
Enterl from
⇒
else
or_stuck"block"
Execl [ ] j
⇒
jump_stepge c l j
Execl i :: rest j
⇒
match let* why ≔ fr_doomedc_framec in if ahead_transparenti then None else Somewhy with
Somewhy
⇒
None
⇒
or_stuck"instruction"
let* out0 ≔ inst_stepge c_framec c_memc i in
let* od ≔ doomed_resultge c_framec c_memc i out0 in
Someinst_nextc l rest j fstod sndod
=
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
j :
Ha :
fr_atc_framec = Execl [ ] j
⊢
False
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

rewrite Ha in Hs

2 open

ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
l :
j :
Hs :
jump_stepge c l j = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
Ha :
fr_atc_framec = Execl [ ] j
⊢
False
deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

exact jump_step_not_fresh_ _ _ _ _ _ Hs

deferred goal
ge :
md :
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
Hr :
Hs :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hcall :
Forallλfp : frame × pending ⇒ parkedmd fstfp c_callersc
Halign :
0 < req_alignq
Hb0 :
0 < base
l :
i :
rest :
listinst
j :
Ha :
fr_atc_framec = Execl i :: rest j
⊢
frame_okge md c_memkbase c_framekbase ∧ Forallλfp : frame × pending ⇒ parkedmd fstfp c_callerskbase

–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
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
–destruct step_snapshot_fresh_ _ _ _ _ _ Ha Hs base 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′
–exfalso
exact step_enter_fresh_ _ _ _ _ _ Ha Hs
–exfalso
unfold step in Hs
rewrite Ha in Hs
exact jump_step_not_fresh_ _ _ _ _ _ Hs
–exact alloc_inv_inst_ _ _ _ _ _ base s′ _ _ _ _ Hr Ha Hs Hb0 conjconjHin conjHpos Hpt Hcall

A covered access is a raw access, which the pass relies on facts for.

302Lemma covered_relies
∀ s i q lo hi r al
covered_accessi q lo hi r al = true
reliess i = true
Explore proof 5 tactics

Initial goal

⊢
∀s : src i : inst q : name lo hi : Z r : rights al : Z, covered_accessi q lo hi r al = true → reliess i = true

unfold covered_access , relies

⊢
∀ s : src i : inst q : name lo hi : Z r : rights al : Z  ,
match raw_accessi with
Someq′, x, off, need
⇒
let size, aa ≔ access_size_alignx in
name_eqbq′ q && lo ≤? off && off + size ≤? hi && al mod aa =? 0 && off − lo mod aa =? 0 && rights_allowr need
None
⇒
false
=
true
→
||
match raw_accessi with
Some_
⇒
true
None
⇒
false
=
true

intros s i q lo hi r al H

s :
i :
q :
lo, hi :
Z
al :
Z
H :
match raw_accessi with
Someq′, x, off, need
⇒
let size, aa ≔ access_size_alignx in
name_eqbq′ q && lo ≤? off && off + size ≤? hi && al mod aa =? 0 && off − lo mod aa =? 0 && rights_allowr need
None
⇒
false
=
true
⊢
||
match raw_accessi with
Some_
⇒
true
None
⇒
false
=
true

destruct raw_accessi ; | discriminate H

s :
i :
q :
lo, hi :
Z
al :
Z
p :
name × access_type × Z × rights
H :
let p0, need ≔ p in
let p1, off ≔ p0 in
let q′, x ≔ p1 in
let size, aa ≔ access_size_alignx in
name_eqbq′ q && lo ≤? off && off + size ≤? hi && al mod aa =? 0 && off − lo mod aa =? 0 && rights_allowr need
=
true
⊢
evidence_preservingi || is_check_locali || repeated_getters i || true = true

rewrite ! orb_true_r

s :
i :
q :
lo, hi :
Z
al :
Z
p :
name × access_type × Z × rights
H :
let p0, need ≔ p in
let p1, off ≔ p0 in
let q′, x ≔ p1 in
let size, aa ≔ access_size_alignx in
name_eqbq′ q && lo ≤? off && off + size ≤? hi && al mod aa =? 0 && off − lo mod aa =? 0 && rights_allowr need
=
true
⊢
true = true

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros s i q lo hi r al H
destruct raw_accessi ; | discriminate H
rewrite ! orb_true_r
reflexivity

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).

311Lemma safepoint_inv
∀ ge md c s s′ m′
safepoint_duege c = true
R.safepoints c_memc s′ m′
invge md c, s
invge md with_memc m′, s′
Proof 43 steps Qed
intros ge md c s s′ m′ Hdue Hact Hin & Hpos & Hpt Hcall
unfold inv in *
simpl in *
split ; | exact Hcall
split ; exact Hin |
split ; exact Hpos |
destruct Hpt as Hd0 | Hp ; left ; exact Hd0 | right
pose proof Hdue as Hdue0
unfold safepoint_due in Hdue
destruct fr_atc_framec as xs l | l from | l is j eqn: Ha ; try discriminate Hdue
destruct point_ok_exec_inv_ _ _ _ _ _ _ Hp Ha as E & b & out & k & HE & Hb & Hout & Hj & Hk & Hat
eapply point_ok_exec ; exact HE | exact Ha | exact Hb | exact Hout | exact Hj | exact Hk |
destruct is as | i rest
–destruct Hat as live & Hw & Hd & Hjc | access & rest′ & live′ & E′ & _ ; | discriminate E'
left
exists live
split ; exact Hw |
split ; exact Hd |
intros t Ht Hpoll
exfalso
unfold with_mem in Ht
simpl in Ht
rewrite Ht in Hdue
destruct t ; simpl in Hdue , Hpoll ; discriminate Hdue | discriminate Hpoll
–assert Hreg : reliesfn_srcmd fr_fnc_framec i = true → m_regionsm' = m_regionsc_memc by intros Hr ; exact spares_anyge md c s s' m' Hdue0 Hact l i rest j Ha Hr
destruct Hat as live & Hw & Hd & Hl | access & rest′ & live′ & E′ & Hw & Hd & Hpc
+left
exists live
split ; exact Hw |
split ; exact Hd |
intros Hr
eapply facts_hold_same ; exact HregHr | exact HlHr
+injection E' as ← ←
right
exists i, rest, live'
split ; reflexivity |
split ; exact Hw |
split ; exact Hd |
destruct Hpc as fb & pre & Hcov & → & Hh | Hfn ; left | right ; exact Hfn
exists fb, pre
split ; exact Hcov |
split ; reflexivity |
eapply facts_hold_same ; exact Hregcovered_relies_ _ _ _ _ _ _ Hcov | exact Hh

Every machine step from a ready state keeps inv.

339Theorem mstep_inv
∀ ge md st st′
ge_modulege = md
mstepge st st′
invge md st
invge md st′
Explore proof 5 tactics

Initial goal

⊢
∀ge : genv md : module st st′ : mstate, ge_modulege = md → checked_modulemd → ready_statest → mstepge st st′ → invge md st → invge md st′

intros ge md st st′ Hge Hmd Hr Hs H

ge :
md :
st, st′ :
Hge :
ge_modulege = md
Hs :
mstepge st st′
H :
invge md st
⊢
invge md st′

destruct Hs as c c′ s E | c q k s base s′ E He Hal | c s s′ m′ Hd Hact

3 open

ge :
md :
Hge :
ge_modulege = md
s :
R.state
Hr :
c′ :
E :
stepge c = Nextc′
H :
invge md c, s
⊢
invge md c′, s
focused goal
ge :
md :
Hge :
ge_modulege = md
s :
R.state
Hr :
k :
Z → config
base :
Z
s′ :
R.state
E :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
H :
invge md c, s
⊢
invge md kbase, s′
focused goal
ge :
md :
Hge :
ge_modulege = md
s :
R.state
Hr :
s′ :
R.state
m′ :
Memory.mem
Hd :
safepoint_duege c = true
Hact :
R.safepoints c_memc s′ m′
H :
invge md c, s
⊢
invge md with_memc m′, s′

–eapply next_inv ; eauto

2 open

deferred goal
ge :
md :
Hge :
ge_modulege = md
s :
R.state
Hr :
k :
Z → config
base :
Z
s′ :
R.state
E :
stepge c = Freshq k
He :
0 ≤ req_extentq
Hal :
R.allocs q = Somebase, s′
H :
invge md c, s
⊢
invge md kbase, s′
deferred goal
ge :
md :
Hge :
ge_modulege = md
s :
R.state
Hr :
s′ :
R.state
m′ :
Memory.mem
Hd :
safepoint_duege c = true
Hact :
R.safepoints c_memc s′ m′
H :
invge md c, s
⊢
invge md with_memc m′, s′

–eapply alloc_inv ; eauto

deferred goal
ge :
md :
Hge :
ge_modulege = md
s :
R.state
Hr :
s′ :
R.state
m′ :
Memory.mem
Hd :
safepoint_duege c = true
Hact :
R.safepoints c_memc s′ m′
H :
invge md c, s
⊢
invge md with_memc m′, s′

–eapply safepoint_inv ; eauto

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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
–eapply next_inv ; eauto
–eapply alloc_inv ; eauto
–eapply safepoint_inv ; eauto

From a ready start where it holds, inv holds in every state a run reaches.

352Theorem mreachable_inv
∀ ge md st st′
ge_modulege = md
ge_freege = R.free
mreachablege st st′
invge md st
invge md st′
Explore proof 4 tactics

Initial goal

⊢
∀ge : genv md : module st st′ : mstate, ge_modulege = md → checked_modulemd → ge_freege = R.free → mreachablege st st′ → ready_statest → invge md st → invge md st′

intros ge md st st′ Hge Hmd Hfree H

ge :
md :
st, st′ :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
H :
mreachablege st st′
⊢
ready_statest → invge md st → invge md st′

induction H as st st′ Hs | st | st1 st2 st3 H12 IH1 H23 IH2 ; intros Hr Hi ; auto

2 open

ge :
md :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
st, st′ :
Hs :
mstepge st st′
Hi :
invge md st
⊢
invge md st′
focused goal
ge :
md :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
st1, st2, st3 :
H12 :
clos_refl_transmstate mstepge st1 st2
H23 :
clos_refl_transmstate mstepge st2 st3
IH1 :
ready_statest1 → invge md st1 → invge md st2
IH2 :
ready_statest2 → invge md st2 → invge md st3
Hi :
invge md st1
⊢
invge md st3

–eapply mstep_inv ; eauto

deferred goal
ge :
md :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
st1, st2, st3 :
H12 :
clos_refl_transmstate mstepge st1 st2
H23 :
clos_refl_transmstate mstepge st2 st3
IH1 :
ready_statest1 → invge md st1 → invge md st2
IH2 :
ready_statest2 → invge md st2 → invge md st3
Hi :
invge md st1
⊢
invge md st3

–apply IH2 ; exact mreachable_ready_ _ _ Hfree H12 Hr | exact IH1Hr Hi

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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
–eapply mstep_inv ; eauto
–apply IH2 ; exact mreachable_ready_ _ _ Hfree H12 Hr | exact IH1Hr Hi

inv holds where a run starts: at the entry of a checked module's function, with no caller.

364Lemma start_inv
∀ ge md f xs fr m fuel s
InIFuncf md
call_framef xs = Somefr
invge md mkConfigfr [ ] m fuel, s
Explore proof 3 tactics

Initial goal

⊢
∀ge : genv md : module f : func xs : listword fr : frame m : Memory.mem fuel : Z s : R.state, checked_modulemd → InIFuncf md → call_framef xs = Somefr → invge md c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s

intros ge md f xs fr m fuel s Hmd Hin Hc

ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s :
R.state
Hin :
InIFuncf md
Hc :
call_framef xs = Somefr
⊢
invge md c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s

split ; | constructor

ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s :
R.state
Hin :
InIFuncf md
Hc :
call_framef xs = Somefr
⊢
frame_okge md c_memfstc_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s c_framefstc_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s

exact call_frame_ok_ _ _ _ _ _ Hmd Hin Hc

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge md f xs fr m fuel s Hmd Hin Hc
split ; | constructor
exact call_frame_ok_ _ _ _ _ _ Hmd Hin Hc

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.

379Theorem access_not_unchecked
∀ ge md c s l i rest j why
invge md c, s
fr_atc_framec = Execl i :: rest j
raw_accessi ≠ None ∨ ∃r cl args, i = RawCallr cl args
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest
Explore proof 23 tactics

Initial goal

⊢
∀ge : genv md : module c : config s : R.state l : name i : inst rest : listinst j : jump why : reason, invge md c, s → ready_statec, s → fr_doomedc_framec = None → fr_atc_framec = Execl i :: rest j → raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args → inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

intros ge md c s l i rest j why _ & Hpos & Hpt _ Hr Hd Ha Hi

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hpos :
Hpt :
fr_doomedc_framefstc, s ≠ None ∨ point_okge md c_memfstc, s c_framefstc, s
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

simpl in *

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

assert Hfit : objects_fitm_regionsc_memc by exact R.address_space_ _ Hr

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hpt :
fr_doomedc_framec ≠ None ∨ point_okge md c_memc c_framec
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

destruct Hpt as Hd0 | Hp ; congruence |

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

destruct point_ok_exec_inv_ _ _ _ _ _ _ Hp Ha as E & b & out & k & _ & Hb & _ & _ & Hk & Hat

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnc_framec c_memc c_framec i :: rest j out fr_fnc_framec l k
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

destruct Hat as live & Hw & Hdom & Hl | access & rest′ & live′ & E′ & _ & _ & Hpc

2 open

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest
focused goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
access :
rest′ :
listinst
live′ :
listfact
E′ :
i :: rest = access :: rest′
Hpc :
pair_claimge c_memc c_framec access live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

–destruct walks_cons_ _ _ _ _ Hw as rest′ & live′ & Hc & _

2 open

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec i rest live = Somerest′, live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
access :
rest′ :
listinst
live′ :
listfact
E′ :
i :: rest = access :: rest′
Hpc :
pair_claimge c_memc c_framec access live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

destruct raw_accessi as q x off need | eqn: Hra

3 open

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
q :
off :
Z
need :
Hra :
raw_accessi = Someq, x, off, need
Hi :
Someq, x, off, need ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec i rest live = Somerest′, live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest
focused goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hra :
raw_accessi = None
Hi :
None ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec i rest live = Somerest′, live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
access :
rest′ :
listinst
live′ :
listfact
E′ :
i :: rest = access :: rest′
Hpc :
pair_claimge c_memc c_framec access live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

+assert Hrel : reliesfn_srcmd fr_fnc_framec i = true by unfold relies ; rewrite Hra , ! orb_true_r ; reflexivity

3 open

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
q :
off :
Z
need :
Hra :
raw_accessi = Someq, x, off, need
Hi :
Someq, x, off, need ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec i rest live = Somerest′, live′
Hrel :
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hra :
raw_accessi = None
Hi :
None ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec i rest live = Somerest′, live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
access :
rest′ :
listinst
live′ :
listfact
E′ :
i :: rest = access :: rest′
Hpc :
pair_claimge c_memc c_framec access live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

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 open

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
q :
off :
Z
need :
Hra :
raw_accessi = Someq, x, off, need
Hi :
Someq, x, off, need ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec i rest live = Somerest′, live′
Hrel :
fa :
Hfa :
fact_ofq live = Somefa
Hh :
⊢
find_blockl fn_blocksfr_fnc_framec = Someb ∧ i :: rest = skipnk b_instsb ∧ facts_holdge c_memc fr_envc_framec live ∧ live_domfr_fnc_framec l k live ∧ fact_ofq live = Somefa ∧ hull_coveredi q f_pfa f_lofa f_alfa live s_oncefn_srcmd fr_fnc_framec = true
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hra :
raw_accessi = None
Hi :
None ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec i rest live = Somerest′, live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
access :
rest′ :
listinst
live′ :
listfact
E′ :
i :: rest = access :: rest′
Hpc :
pair_claimge c_memc c_framec access live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

repeat split ; eassumption |

3 open

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
q :
off :
Z
need :
Hra :
raw_accessi = Someq, x, off, need
Hi :
Someq, x, off, need ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec i rest live = Somerest′, live′
Hrel :
fa :
Hfa :
fact_ofq live = Somefa
Hh :
⊢
facts_holdge c_memc fr_envc_framec live ∧ live_domfr_fnc_framec l k live ∧ fact_ofq live = Somefa ∧ hull_coveredi q f_pfa f_lofa f_alfa live s_oncefn_srcmd fr_fnc_framec = true
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hra :
raw_accessi = None
Hi :
None ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec i rest live = Somerest′, live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
access :
rest′ :
listinst
live′ :
listfact
E′ :
i :: rest = access :: rest′
Hpc :
pair_claimge c_memc c_framec access live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

split ; exact HlHrel |

3 open

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
q :
off :
Z
need :
Hra :
raw_accessi = Someq, x, off, need
Hi :
Someq, x, off, need ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec i rest live = Somerest′, live′
Hrel :
fa :
Hfa :
fact_ofq live = Somefa
Hh :
⊢
live_domfr_fnc_framec l k live ∧ fact_ofq live = Somefa ∧ hull_coveredi q f_pfa f_lofa f_alfa live s_oncefn_srcmd fr_fnc_framec = true
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hra :
raw_accessi = None
Hi :
None ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec i rest live = Somerest′, live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
access :
rest′ :
listinst
live′ :
listfact
E′ :
i :: rest = access :: rest′
Hpc :
pair_claimge c_memc c_framec access live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

repeat split ; eassumption |

3 open

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
q :
off :
Z
need :
Hra :
raw_accessi = Someq, x, off, need
Hi :
Someq, x, off, need ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec i rest live = Somerest′, live′
Hrel :
fa :
Hfa :
fact_ofq live = Somefa
Hh :
⊢
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hra :
raw_accessi = None
Hi :
None ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec i rest live = Somerest′, live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
access :
rest′ :
listinst
live′ :
listfact
E′ :
i :: rest = access :: rest′
Hpc :
pair_claimge c_memc c_framec access live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

exact Hh

2 open

deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hra :
raw_accessi = None
Hi :
None ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec i :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec i rest live = Somerest′, live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
access :
rest′ :
listinst
live′ :
listfact
E′ :
i :: rest = access :: rest′
Hpc :
pair_claimge c_memc c_framec access live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

+destruct Hi as Hi | r & cl & args & → ; congruence |

2 open

ge :
md :
s :
R.state
l :
rest :
listinst
j :
why :
Hr :
Hd :
cl :
args :
listarg
Hra :
raw_accessRawCallr cl args = None
Ha :
fr_atc_framec = Execl RawCallr cl args :: rest j
E :
listname × listfact
out :
listfact
k :
nat
Hk :
RawCallr cl args :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec RawCallr cl args :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd fr_fnc_framec RawCallr cl args rest live = Somerest′, live′
⊢
inst_stepge c_framec c_memc RawCallr cl args ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l RawCallr cl args rest
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
access :
rest′ :
listinst
live′ :
listfact
E′ :
i :: rest = access :: rest′
Hpc :
pair_claimge c_memc c_framec access live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

rewrite raw_call_alone in Hc

2 open

ge :
md :
s :
R.state
l :
rest :
listinst
j :
why :
Hr :
Hd :
cl :
args :
listarg
Hra :
raw_accessRawCallr cl args = None
Ha :
fr_atc_framec = Execl RawCallr cl args :: rest j
E :
listname × listfact
out :
listfact
k :
nat
Hk :
RawCallr cl args :: rest = skipnk b_instsb
live :
listfact
Hw :
walksfn_srcmd fr_fnc_framec RawCallr cl args :: rest live out
Hdom :
Hl :
rest′ :
listinst
live′ :
listfact
Hc :
None = Somerest′, live′
⊢
inst_stepge c_framec c_memc RawCallr cl args ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l RawCallr cl args rest
deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
access :
rest′ :
listinst
live′ :
listfact
E′ :
i :: rest = access :: rest′
Hpc :
pair_claimge c_memc c_framec access live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

discriminate Hc

deferred goal
ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
access :
rest′ :
listinst
live′ :
listfact
E′ :
i :: rest = access :: rest′
Hpc :
pair_claimge c_memc c_framec access live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

–injection E′ as ← _

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
rest′ :
listinst
live′ :
listfact
Hpc :
pair_claimge c_memc c_framec i live′
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

left

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
rest′ :
listinst
live′ :
listfact
Hpc :
pair_claimge c_memc c_framec i live′
⊢

destruct Hpc as fb & pre & Hcov & _ & Hh | _ & r & q & args & p & → & Hq & Hc

2 open

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
rest′ :
listinst
live′ :
listfact
fb :
pre :
listfact
Hcov :
covered_accessi f_qfb f_lofb f_hifb f_rfb f_alfb = true
Hh :
⊢
focused goal
ge :
md :
s :
R.state
l :
rest :
listinst
j :
why :
Hr :
Hd :
q :
args :
listarg
Hi :
raw_accessRawCallr Tmpq args ≠ None ∨ ∃r0 : call_result cl : value args0 : listarg, RawCallr Tmpq args = RawCallr0 cl args0
Ha :
fr_atc_framec = Execl RawCallr Tmpq args :: rest j
E :
listname × listfact
out :
listfact
k :
nat
Hk :
RawCallr Tmpq args :: rest = skipnk b_instsb
rest′ :
listinst
live′ :
listfact
p :
Hq :
Hc :
⊢

+destruct Hhfb or_introleq_refl as p & Eq & _ & Hpass

2 open

ge :
md :
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hr :
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
E :
listname × listfact
out :
listfact
k :
nat
Hk :
i :: rest = skipnk b_instsb
rest′ :
listinst
live′ :
listfact
fb :
pre :
listfact
Hcov :
covered_accessi f_qfb f_lofb f_hifb f_rfb f_alfb = true
Hh :
p :
Hpass :
⊢
deferred goal
ge :
md :
s :
R.state
l :
rest :
listinst
j :
why :
Hr :
Hd :
q :
args :
listarg
Hi :
raw_accessRawCallr Tmpq args ≠ None ∨ ∃r0 : call_result cl : value args0 : listarg, RawCallr Tmpq args = RawCallr0 cl args0
Ha :
fr_atc_framec = Execl RawCallr Tmpq args :: rest j
E :
listname × listfact
out :
listfact
k :
nat
Hk :
RawCallr Tmpq args :: rest = skipnk b_instsb
rest′ :
listinst
live′ :
listfact
p :
Hq :
Hc :
⊢

exact covered_access_not_unchecked_ _ _ _ _ _ _ _ _ _ _ Hfit Hcov Eq Hpass

deferred goal
ge :
md :
s :
R.state
l :
rest :
listinst
j :
why :
Hr :
Hd :
q :
args :
listarg
Hi :
raw_accessRawCallr Tmpq args ≠ None ∨ ∃r0 : call_result cl : value args0 : listarg, RawCallr Tmpq args = RawCallr0 cl args0
Ha :
fr_atc_framec = Execl RawCallr Tmpq args :: rest j
E :
listname × listfact
out :
listfact
k :
nat
Hk :
RawCallr Tmpq args :: rest = skipnk b_instsb
rest′ :
listinst
live′ :
listfact
p :
Hq :
Hc :
⊢

+exact raw_call_checked_ _ _ _ _ _ _ _ Hq Hc

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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
–destruct walks_cons_ _ _ _ _ Hw as rest′ & live′ & Hc & _
destruct raw_accessi as q x off need | eqn: Hra
+assert Hrel : reliesfn_srcmd fr_fnc_framec i = true by unfold relies ; rewrite Hra , ! orb_true_r ; reflexivity
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
repeat split ; eassumption |
split ; exact HlHrel |
repeat split ; eassumption |
exact Hh
+destruct Hi as Hi | r & cl & args & → ; congruence |
rewrite raw_call_alone in Hc
discriminate Hc
–injection E′ as ← _
left
destruct Hpc as fb & pre & Hcov & _ & Hh | _ & r & q & args & p & → & Hq & Hc
+destruct Hhfb or_introleq_refl as p & Eq & _ & Hpass
exact covered_access_not_unchecked_ _ _ _ _ _ _ _ _ _ _ Hfit Hcov Eq Hpass
+exact raw_call_checked_ _ _ _ _ _ _ _ Hq Hc

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.

410Theorem run_access_not_unchecked
∀ ge md f xs fr m fuel s0 c s l i rest j why
ge_modulege = md
ge_freege = R.free
InIFuncf md
call_framef xs = Somefr
R.readys0 m
mreachablege mkConfigfr [ ] m fuel, s0 c, s
fr_atc_framec = Execl i :: rest j
raw_accessi ≠ None ∨ ∃r cl args, i = RawCallr cl args
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest
Explore proof 5 tactics

Initial goal

⊢
∀ge : genv md : module f : func xs : listword fr : frame m : Memory.mem fuel : Z s0 : R.state c : config s : R.state l : name i : inst rest : listinst j : jump why : reason, checked_modulemd → ge_modulege = md → ge_freege = R.free → InIFuncf md → call_framef xs = Somefr → R.readys0 m → mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s → fr_doomedc_framec = None → fr_atc_framec = Execl i :: rest j → raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args → inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

intros ge md f xs fr m fuel s0 c s l i rest j why Hmd Hge Hfree Hin Hcf H0 Hreach

ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s0 :
R.state
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
H0 :
R.readys0 m
Hreach :
mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s
⊢
fr_doomedc_framec = None → fr_atc_framec = Execl i :: rest j → raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args → inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

eapply access_not_unchecked

3 open

ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s0 :
R.state
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
H0 :
R.readys0 m
Hreach :
mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s
⊢
invge md c, ?s
focused goal
ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s0 :
R.state
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
H0 :
R.readys0 m
Hreach :
mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s
⊢
shelved goal
ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s0 :
R.state
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
H0 :
R.readys0 m
Hreach :
mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s
⊢
R.state

–eapply mreachable_inv ; eauto

2 open

ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s0 :
R.state
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
H0 :
R.readys0 m
Hreach :
mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s
⊢
invge md c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0
deferred goal
ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s0 :
R.state
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
H0 :
R.readys0 m
Hreach :
mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s

exact start_inv_ _ _ _ _ _ _ s0 Hmd Hin Hcf

deferred goal
ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s0 :
R.state
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
H0 :
R.readys0 m
Hreach :
mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s

–exact mreachable_ready_ _ _ Hfree Hreach H0

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge md f xs fr m fuel s0 c s l i rest j why Hmd Hge Hfree Hin Hcf H0 Hreach
–eapply mreachable_inv ; eauto
exact start_inv_ _ _ _ _ _ _ s0 Hmd Hin Hcf
–exact mreachable_ready_ _ _ Hfree Hreach H0

The interpreter's runtime

The same for the interpreter's runtime.

430Module InterpPersistence ≔ Persistence InterpRuntime
Import InterpPersistence.I

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).

438Corollary interp_access_not_unchecked
∀ md globals f xs fr m fuel s0 c s l i rest j why
let ge ≔ mkGenvmd globals InterpRuntime.free in
checked_modulemd → InIFuncf md → call_framef xs = Somefr → InterpRuntime.readys0 m → RM.mreachablege mkConfigfr [ ] m fuel, s0 c, s → fr_doomedc_framec = None → fr_atc_framec = Execl i :: rest j → raw_accessi ≠ None ∨ ∃r cl args, i = RawCallr cl args → inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest
Explore proof 2 tactics

Initial goal

⊢
∀ md : module globals : listname × ptr f : func xs : listword fr : frame m : Memory.mem fuel : Z s0 : InterpRuntime.state c : config s : InterpRuntime.state l : name i : inst rest : listinst j : jump why : reason  ,
let ge ≔ ge_module ≔ md; ge_globals ≔ globals; ge_free ≔ InterpRuntime.free in
checked_modulemd → InIFuncf md → call_framef xs = Somefr → InterpRuntime.readys0 m → RM.mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s → fr_doomedc_framec = None → fr_atc_framec = Execl i :: rest j → raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args → inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

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

md :
globals :
listname × ptr
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
l :
i :
rest :
listinst
j :
why :
ge :=
ge_module ≔ md; ge_globals ≔ globals; ge_free ≔ InterpRuntime.free : genv
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
Hreach :
RM.mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hi :
raw_accessi ≠ None ∨ ∃r : call_result cl : value args : listarg, i = RawCallr cl args
⊢
inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy ∨ hull_casege md c l i rest

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.

Source script
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