Fil-C on Nix

Filnix wiki

the formal campaign

rocq/theories/Ahead.v

Campaign 3's scheduled checks: what the validator's backward pass for check_ahead computes, point by point (formal.md, Campaign 3; rocq.md, Facts ahead; schedule.md). It is the first step toward the doomed frame of Doomed.v.

ahead_justified/3 walks a function's blocks once, from the last, and each block's instructions from its jump. At each point it keeps needs: a single-definition base N with an offset H, meaning that every path from the point reaches, through ahead-transparent instructions only and before any poll edge, edge back or end, a raw access through N whose bytes reach N + H. A check_ahead is accepted where its access is followed by a need that covers the bytes it checks early. This file states those needs as functions of the point, so that a frame can carry them forward, and proves that the pass's one sweep computes them.

Decisions

DecisionWhy
the facts are read from the final tablean edge reads its target's entry facts only for a later block, which the sweep has finished; no later step puts that label again, labels being unique
ahead_justified is split into ahead_fold, ahead_block, ahead_edge and ahead_acceptsas ir.pl's ahead_block/6 and ahead_edge/5 are; the proofs read each part on its own
From Stdlib Require Import String ZArith List Bool Lia
From Nanofil Require Import Term Maps Syntax Cfg Values Memory Validate Walk Dominance Evidence
Import ListNotations
Open Scope Z_scope

Facts at a point

The needs at the jump of a block b: the meet over its edges (ahead_meet/2, the bases every edge needs, each at its least offset). An edge reads its target's entry facts from the table ins if the target comes later in the block order ord, and needs nothing if it is a poll edge or goes back (ahead_edge/5).

39Definition exit_inord : listname ins : listname × facts b : block : facts ≔

The final table of a function's entry facts: for each block's label, the needs before its first instruction, as ahead_fold leaves them.

45Definition ahead_entriesf : func : listname × facts ≔

The needs at the jump of a block b of a function f, read from the final table ahead_entries.

49Definition block_exitf : func b : block : facts ≔

The needs before a list of instructions is of a function f, when the facts after the last one are out: ahead_step/5 applied from the last instruction back to the first.

55Definition facts_fromf : func is : listinst out : facts : facts ≔

One block

One backward step, ahead_step with its arguments in the order fold_left takes.

62Definition step_backonce : listname × def ptrs : listname × value fs : facts i : inst : facts ≔
ahead_steponce ptrs i fs

A block's walk (ahead_insts/8) over its instructions, given in reverse as ris and starting from the facts after them, leaves the facts before its first instruction: the step_back fold.

68Lemma ahead_insts_after
∀ once ptrs ris after next js
fstahead_instsonce ptrs ris after next js = fold_leftstep_backonce ptrs ris after
Explore proof 5 tactics

Initial goal

⊢
∀once : listname × def ptrs : listname × value ris : listinst after next : facts js : listname, fstahead_instsonce ptrs ris after next js = fold_leftstep_backonce ptrs ris after

intros once ptrs ris

once :
listname × def
ptrs :
listname × value
ris :
listinst
⊢
∀after next : facts js : listname, fstahead_instsonce ptrs ris after next js = fold_leftstep_backonce ptrs ris after

induction ris as | i ris IH ; intros after next js ; reflexivity |

once :
listname × def
ptrs :
listname × value
i :
ris :
listinst
IH :
∀after next : facts js : listname, fstahead_instsonce ptrs ris after next js = fold_leftstep_backonce ptrs ris after
after, next :
js :
listname
⊢
fstahead_instsonce ptrs i :: ris after next js = fold_leftstep_backonce ptrs i :: ris after

simpl

once :
listname × def
ptrs :
listname × value
i :
ris :
listinst
IH :
∀after next : facts js : listname, fstahead_instsonce ptrs ris after next js = fold_leftstep_backonce ptrs ris after
after, next :
js :
listname
⊢
fst
ahead_instsonce ptrs ris ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
=
fold_leftstep_backonce ptrs ris step_backonce ptrs after i

rewrite IH

once :
listname × def
ptrs :
listname × value
i :
ris :
listinst
IH :
∀after next : facts js : listname, fstahead_instsonce ptrs ris after next js = fold_leftstep_backonce ptrs ris after
after, next :
js :
listname
⊢
fold_leftstep_backonce ptrs ris ahead_steponce ptrs i after = fold_leftstep_backonce ptrs ris step_backonce ptrs after i

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros once ptrs ris
induction ris as | i ris IH ; intros after next js ; reflexivity |
simpl
rewrite IH
reflexivity

With no facts after it, no instruction is accepted: a check_ahead needs a need to cover its early bytes.

77Lemma ahead_accepts_nil
∀ once i
ahead_acceptsonce [ ] i = None
Explore proof 12 tactics

Initial goal

⊢
∀once : listname × def i : inst, ahead_acceptsonce [ ] i = None

intros once i

once :
listname × def
i :
⊢
ahead_acceptsonce [ ] i = None

destruct i as q k o args | | | | | | | | ; try reflexivity

once :
listname × def
q :
o :
args :
listvalue
⊢
ahead_acceptsonce [ ] Letq k o args = None

destruct k ; try reflexivity

once :
listname × def
q :
o :
args :
listvalue
⊢
ahead_acceptsonce [ ] Letq A o args = None

destruct o ; try reflexivity

once :
listname × def
q :
lo, hi :
Z
align, ahi :
Z
args :
listvalue
⊢
ahead_acceptsonce [ ] Letq A CheckAheadlo hi r align ahi args = None

destruct args as | p | a args ; try reflexivity

once :
listname × def
q :
lo, hi :
Z
align, ahi :
Z
⊢
ahead_acceptsonce [ ] Letq A CheckAheadlo hi r align ahi p = None

cbn beta iota delta [ ahead_accepts ]

once :
listname × def
q :
lo, hi :
Z
align, ahi :
Z
⊢
once_hasonce q
&&
existsb
λ e : value × Z × Z  ⇒
match exact_baseonce e with
Somen, k
⇒
&&
match lookupn [ ] with
Someh
⇒
k + hi ≤? h
None
⇒
false
None
⇒
false
→
Someq
else
None
=
None

generalize guard_chainonce p as es

once :
listname × def
q :
lo, hi :
Z
align, ahi :
Z
⊢
∀ es : listvalue × Z × Z  ,
once_hasonce q
&&
existsb
λ e : value × Z × Z  ⇒
match exact_baseonce e with
Somen, k
⇒
&&
match lookupn [ ] with
Someh
⇒
k + hi ≤? h
None
⇒
false
None
⇒
false
es
→
Someq
else
None
=
None

intros es

once :
listname × def
q :
lo, hi :
Z
align, ahi :
Z
es :
listvalue × Z × Z
⊢
once_hasonce q
&&
existsb
λ e : value × Z × Z  ⇒
match exact_baseonce e with
Somen, k
⇒
&&
match lookupn [ ] with
Someh
⇒
k + hi ≤? h
None
⇒
false
None
⇒
false
es
→
Someq
else
None
=
None

cbn [ lookup ]

once :
listname × def
q :
lo, hi :
Z
align, ahi :
Z
es :
listvalue × Z × Z
⊢
once_hasonce q
&&
existsb
λ e : value × Z × Z  ⇒
match exact_baseonce e with
Some_, k
⇒
near_offsetk && near_offsetk + lo && false
None
⇒
false
es
→
Someq
else
None
=
None

match goal with|- context [existsb?g es]⇒replace existsbg es with false by induction es as | e es IH ; reflexivity | ; simpl ; rewrite <- IH ; destruct exact_baseonce e as n kk | ; rewrite andb_false_r | ; reflexivityend

once :
listname × def
q :
lo, hi :
Z
align, ahi :
Z
es :
listvalue × Z × Z
⊢
once_hasonce q && false
→
Someq
else
None
=
None

rewrite andb_false_r

once :
listname × def
q :
lo, hi :
Z
align, ahi :
Z
es :
listvalue × Z × Z
⊢
None = None

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros once i
destruct i as q k o args | | | | | | | | ; try reflexivity
destruct k ; try reflexivity
destruct o ; try reflexivity
destruct args as | p | a args ; try reflexivity
cbn beta iota delta [ ahead_accepts ]
generalize guard_chainonce p as es
intros es
cbn [ lookup ]
match goal with|- context [existsb?g es]⇒replace existsbg es with false by induction es as | e es IH ; reflexivity | ; simpl ; rewrite <- IH ; destruct exact_baseonce e as n kk | ; rewrite andb_false_r | ; reflexivityend
rewrite andb_false_r
reflexivity

Where does a proof q come from, if a block's walk over the reversed instructions ris accepts it? Either it was in the list js accepted before the walk; or it is the first of ris, accepted with next, the facts the walk was given for after its access; or it is an instruction i followed by another (its access), accepted with the facts the walk had after that access.

97Lemma ahead_insts_js
∀ once ptrs ris after next js q
Inq sndahead_instsonce ptrs ris after next js
Inq js ∨ ∃i post, ris = i :: post ∧ ahead_acceptsonce next i = Someq ∨ ∃pre i1 i post, ris = pre ++ i1 :: i :: post ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i = Someq
Explore proof 14 tactics

Initial goal

⊢
∀once : listname × def ptrs : listname × value ris : listinst after next : facts js : listname q : name, Inq sndahead_instsonce ptrs ris after next js → Inq js ∨ ∃i : inst post : listinst, ris = i :: post ∧ ahead_acceptsonce next i = Someq ∨ ∃pre : listinst i1 i : inst post : listinst, ris = pre ++ i1 :: i :: post ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i = Someq

intros once ptrs ris

once :
listname × def
ptrs :
listname × value
ris :
listinst
⊢
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs ris after next js → Inq js ∨ ∃i : inst post : listinst, ris = i :: post ∧ ahead_acceptsonce next i = Someq ∨ ∃pre : listinst i1 i : inst post : listinst, ris = pre ++ i1 :: i :: post ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i = Someq

induction ris as | i ris IH ; intros after next js q H ; left ; exact H |

once :
listname × def
ptrs :
listname × value
i :
ris :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs ris after next js → Inq js ∨ ∃i : inst post : listinst, ris = i :: post ∧ ahead_acceptsonce next i = Someq ∨ ∃pre : listinst i1 i : inst post : listinst, ris = pre ++ i1 :: i :: post ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i = Someq
after, next :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs i :: ris after next js
⊢
Inq js ∨ ∃i0 : inst post : listinst, i :: ris = i0 :: post ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre : listinst i1 i0 : inst post : listinst, i :: ris = pre ++ i1 :: i0 :: post ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i0 = Someq

simpl in H

once :
listname × def
ptrs :
listname × value
i :
ris :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs ris after next js → Inq js ∨ ∃i : inst post : listinst, ris = i :: post ∧ ahead_acceptsonce next i = Someq ∨ ∃pre : listinst i1 i : inst post : listinst, ris = pre ++ i1 :: i :: post ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs ris ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
⊢
Inq js ∨ ∃i0 : inst post : listinst, i :: ris = i0 :: post ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre : listinst i1 i0 : inst post : listinst, i :: ris = pre ++ i1 :: i0 :: post ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i0 = Someq

destruct IH_ _ _ _ H as Hj | i′ & post & → & Ha | pre & i1 & i′ & post & → & Ha

3 open

once :
listname × def
ptrs :
listname × value
i :
ris :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs ris after next js → Inq js ∨ ∃i : inst post : listinst, ris = i :: post ∧ ahead_acceptsonce next i = Someq ∨ ∃pre : listinst i1 i : inst post : listinst, ris = pre ++ i1 :: i :: post ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs ris ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Hj :
Inq
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
⊢
Inq js ∨ ∃i0 : inst post : listinst, i :: ris = i0 :: post ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre : listinst i1 i0 : inst post : listinst, i :: ris = pre ++ i1 :: i0 :: post ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i0 = Someq
focused goal
once :
listname × def
ptrs :
listname × value
i, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre : listinst i1 i : inst post0 : listinst, i′ :: post = pre ++ i1 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce after i′ = Someq
⊢
Inq js ∨ ∃i0 : inst post0 : listinst, i :: i′ :: post = i0 :: post0 ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre : listinst i1 i0 : inst post0 : listinst, i :: i′ :: post = pre ++ i1 :: i0 :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i0 = Someq
focused goal
once :
listname × def
ptrs :
listname × value
i :
pre :
listinst
i1, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs pre ++ i1 :: i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, pre ++ i1 :: i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre0 : listinst i2 i : inst post0 : listinst, pre ++ i1 :: i′ :: post = pre0 ++ i2 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs pre ++ i1 :: i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre ahead_steponce ptrs i after i′ = Someq
⊢
Inq js ∨ ∃i0 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = i0 :: post0 ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre0 : listinst i0 i2 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = pre0 ++ i0 :: i2 :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i2 = Someq

–destruct ahead_acceptsonce next i as q′ | eqn: Ea ; | left ; exact Hj

3 open

once :
listname × def
ptrs :
listname × value
i :
ris :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs ris after next js → Inq js ∨ ∃i : inst post : listinst, ris = i :: post ∧ ahead_acceptsonce next i = Someq ∨ ∃pre : listinst i1 i : inst post : listinst, ris = pre ++ i1 :: i :: post ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i = Someq
after, next :
js :
listname
q, q′ :
Ea :
ahead_acceptsonce next i = Someq′
H :
Inq sndahead_instsonce ptrs ris ahead_steponce ptrs i after after q′ :: js
Hj :
Inq q′ :: js
⊢
Inq js ∨ ∃i0 : inst post : listinst, i :: ris = i0 :: post ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre : listinst i1 i0 : inst post : listinst, i :: ris = pre ++ i1 :: i0 :: post ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i0 = Someq
deferred goal
once :
listname × def
ptrs :
listname × value
i, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre : listinst i1 i : inst post0 : listinst, i′ :: post = pre ++ i1 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce after i′ = Someq
⊢
Inq js ∨ ∃i0 : inst post0 : listinst, i :: i′ :: post = i0 :: post0 ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre : listinst i1 i0 : inst post0 : listinst, i :: i′ :: post = pre ++ i1 :: i0 :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i0 = Someq
deferred goal
once :
listname × def
ptrs :
listname × value
i :
pre :
listinst
i1, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs pre ++ i1 :: i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, pre ++ i1 :: i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre0 : listinst i2 i : inst post0 : listinst, pre ++ i1 :: i′ :: post = pre0 ++ i2 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs pre ++ i1 :: i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre ahead_steponce ptrs i after i′ = Someq
⊢
Inq js ∨ ∃i0 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = i0 :: post0 ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre0 : listinst i0 i2 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = pre0 ++ i0 :: i2 :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i2 = Someq

destruct Hj as ← | Hj ; right ; left ; eauto | left ; exact Hj

2 open

deferred goal
once :
listname × def
ptrs :
listname × value
i, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre : listinst i1 i : inst post0 : listinst, i′ :: post = pre ++ i1 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce after i′ = Someq
⊢
Inq js ∨ ∃i0 : inst post0 : listinst, i :: i′ :: post = i0 :: post0 ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre : listinst i1 i0 : inst post0 : listinst, i :: i′ :: post = pre ++ i1 :: i0 :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i0 = Someq
deferred goal
once :
listname × def
ptrs :
listname × value
i :
pre :
listinst
i1, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs pre ++ i1 :: i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, pre ++ i1 :: i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre0 : listinst i2 i : inst post0 : listinst, pre ++ i1 :: i′ :: post = pre0 ++ i2 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs pre ++ i1 :: i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre ahead_steponce ptrs i after i′ = Someq
⊢
Inq js ∨ ∃i0 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = i0 :: post0 ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre0 : listinst i0 i2 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = pre0 ++ i0 :: i2 :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i2 = Someq

–right

2 open

once :
listname × def
ptrs :
listname × value
i, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre : listinst i1 i : inst post0 : listinst, i′ :: post = pre ++ i1 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce after i′ = Someq
⊢
∃i0 : inst post0 : listinst, i :: i′ :: post = i0 :: post0 ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre : listinst i1 i0 : inst post0 : listinst, i :: i′ :: post = pre ++ i1 :: i0 :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i0 = Someq
deferred goal
once :
listname × def
ptrs :
listname × value
i :
pre :
listinst
i1, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs pre ++ i1 :: i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, pre ++ i1 :: i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre0 : listinst i2 i : inst post0 : listinst, pre ++ i1 :: i′ :: post = pre0 ++ i2 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs pre ++ i1 :: i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre ahead_steponce ptrs i after i′ = Someq
⊢
Inq js ∨ ∃i0 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = i0 :: post0 ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre0 : listinst i0 i2 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = pre0 ++ i0 :: i2 :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i2 = Someq

right

2 open

once :
listname × def
ptrs :
listname × value
i, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre : listinst i1 i : inst post0 : listinst, i′ :: post = pre ++ i1 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce after i′ = Someq
⊢
∃pre : listinst i1 i0 : inst post0 : listinst, i :: i′ :: post = pre ++ i1 :: i0 :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i0 = Someq
deferred goal
once :
listname × def
ptrs :
listname × value
i :
pre :
listinst
i1, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs pre ++ i1 :: i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, pre ++ i1 :: i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre0 : listinst i2 i : inst post0 : listinst, pre ++ i1 :: i′ :: post = pre0 ++ i2 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs pre ++ i1 :: i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre ahead_steponce ptrs i after i′ = Someq
⊢
Inq js ∨ ∃i0 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = i0 :: post0 ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre0 : listinst i0 i2 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = pre0 ++ i0 :: i2 :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i2 = Someq

exists [ ], i, i′, post

2 open

once :
listname × def
ptrs :
listname × value
i, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre : listinst i1 i : inst post0 : listinst, i′ :: post = pre ++ i1 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce after i′ = Someq
⊢
i :: i′ :: post = [ ] ++ i :: i′ :: post ∧ ahead_acceptsonce fold_leftstep_backonce ptrs [ ] after i′ = Someq
deferred goal
once :
listname × def
ptrs :
listname × value
i :
pre :
listinst
i1, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs pre ++ i1 :: i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, pre ++ i1 :: i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre0 : listinst i2 i : inst post0 : listinst, pre ++ i1 :: i′ :: post = pre0 ++ i2 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs pre ++ i1 :: i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre ahead_steponce ptrs i after i′ = Someq
⊢
Inq js ∨ ∃i0 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = i0 :: post0 ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre0 : listinst i0 i2 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = pre0 ++ i0 :: i2 :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i2 = Someq

auto

deferred goal
once :
listname × def
ptrs :
listname × value
i :
pre :
listinst
i1, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs pre ++ i1 :: i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, pre ++ i1 :: i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre0 : listinst i2 i : inst post0 : listinst, pre ++ i1 :: i′ :: post = pre0 ++ i2 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs pre ++ i1 :: i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre ahead_steponce ptrs i after i′ = Someq
⊢
Inq js ∨ ∃i0 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = i0 :: post0 ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre0 : listinst i0 i2 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = pre0 ++ i0 :: i2 :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i2 = Someq

–right

once :
listname × def
ptrs :
listname × value
i :
pre :
listinst
i1, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs pre ++ i1 :: i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, pre ++ i1 :: i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre0 : listinst i2 i : inst post0 : listinst, pre ++ i1 :: i′ :: post = pre0 ++ i2 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs pre ++ i1 :: i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre ahead_steponce ptrs i after i′ = Someq
⊢
∃i0 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = i0 :: post0 ∧ ahead_acceptsonce next i0 = Someq ∨ ∃pre0 : listinst i0 i2 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = pre0 ++ i0 :: i2 :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i2 = Someq

right

once :
listname × def
ptrs :
listname × value
i :
pre :
listinst
i1, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs pre ++ i1 :: i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, pre ++ i1 :: i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre0 : listinst i2 i : inst post0 : listinst, pre ++ i1 :: i′ :: post = pre0 ++ i2 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs pre ++ i1 :: i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre ahead_steponce ptrs i after i′ = Someq
⊢
∃pre0 : listinst i0 i2 : inst post0 : listinst, i :: pre ++ i1 :: i′ :: post = pre0 ++ i0 :: i2 :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i2 = Someq

exists i :: pre, i1, i′, post

once :
listname × def
ptrs :
listname × value
i :
pre :
listinst
i1, i′ :
post :
listinst
IH :
∀after next : facts js : listname q : name, Inq sndahead_instsonce ptrs pre ++ i1 :: i′ :: post after next js → Inq js ∨ ∃i : inst post0 : listinst, pre ++ i1 :: i′ :: post = i :: post0 ∧ ahead_acceptsonce next i = Someq ∨ ∃pre0 : listinst i2 i : inst post0 : listinst, pre ++ i1 :: i′ :: post = pre0 ++ i2 :: i :: post0 ∧ ahead_acceptsonce fold_leftstep_backonce ptrs pre0 after i = Someq
after, next :
js :
listname
q :
H :
Inq
snd
ahead_instsonce ptrs pre ++ i1 :: i′ :: post ahead_steponce ptrs i after after
match ahead_acceptsonce next i with
Someq
⇒
q :: js
None
⇒
js
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre ahead_steponce ptrs i after i′ = Someq
⊢
i :: pre ++ i1 :: i′ :: post = i :: pre ++ i1 :: i′ :: post ∧ ahead_acceptsonce fold_leftstep_backonce ptrs i :: pre after i′ = Someq

auto

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros once ptrs ris
induction ris as | i ris IH ; intros after next js q H ; left ; exact H |
simpl in H
destruct IH_ _ _ _ H as Hj | i′ & post & → & Ha | pre & i1 & i′ & post & → & Ha
–destruct ahead_acceptsonce next i as q′ | eqn: Ea ; | left ; exact Hj
destruct Hj as ← | Hj ; right ; left ; eauto | left ; exact Hj
–right
right
exists [ ], i, i′, post
auto
–right
right
exists i :: pre, i1, i′, post
auto

A proof q that a block's walk over its instructions is accepts, starting from the facts out at its jump, was accepted before the block, or is the instruction at some index k, not the last, accepted (ahead_accepts) with the facts before the instructions from k + 2 on, the ones after its access at k + 1.

116Lemma block_accepts
∀ once ptrs is out js q
Inq sndahead_instsonce ptrs revis out [ ] js
Inq js ∨ ∃k i, nth_erroris k = Somei ∧ Sk < lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i = Someq
Explore proof 29 tactics

Initial goal

⊢
∀once : listname × def ptrs : listname × value is : listinst out : facts js : listname q : name, Inq sndahead_instsonce ptrs revis out [ ] js → Inq js ∨ ∃k : nat i : inst, nth_erroris k = Somei ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i = Someq

intros once ptrs is out js q H

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
⊢
Inq js ∨ ∃k : nat i : inst, nth_erroris k = Somei ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i = Someq

destruct ahead_insts_js_ _ _ _ _ _ _ H as Hj | i & post & _ & Ha | pre & i1 & i & post & E & Ha

3 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
Hj :
Inq js
⊢
Inq js ∨ ∃k : nat i : inst, nth_erroris k = Somei ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i = Someq
focused goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
i :
post :
listinst
Ha :
ahead_acceptsonce [ ] i = Someq
⊢
Inq js ∨ ∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq
focused goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
⊢
Inq js ∨ ∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq

–left

3 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
Hj :
Inq js
⊢
Inq js
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
i :
post :
listinst
Ha :
ahead_acceptsonce [ ] i = Someq
⊢
Inq js ∨ ∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
⊢
Inq js ∨ ∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq

exact Hj

2 open

deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
i :
post :
listinst
Ha :
ahead_acceptsonce [ ] i = Someq
⊢
Inq js ∨ ∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
⊢
Inq js ∨ ∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq

–rewrite ahead_accepts_nil in Ha

2 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
i :
post :
listinst
Ha :
None = Someq
⊢
Inq js ∨ ∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
⊢
Inq js ∨ ∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq

discriminate Ha

deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
⊢
Inq js ∨ ∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq

–right

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
⊢
∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq

assert Eis : is = revpost ++ i :: i1 :: revpre

2 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
⊢
is = revpost ++ i :: i1 :: revpre
focused goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq

{rewrite <- rev_involutiveis , E

2 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
⊢
revpre ++ i1 :: i :: post = revpost ++ i :: i1 :: revpre
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq

rewrite rev_app_distr

2 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
⊢
revi1 :: i :: post ++ revpre = revpost ++ i :: i1 :: revpre
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq

simpl

2 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
⊢
revpost ++ i ++ i1 ++ revpre = revpost ++ i :: i1 :: revpre
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq

rewrite <- ! app_assoc

2 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
⊢
revpost ++ i ++ i1 ++ revpre = revpost ++ i :: i1 :: revpre
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq

reflexivity

deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
∃k : nat i0 : inst, nth_erroris k = Somei0 ∧ Sk < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSk is i0 = Someq

exists lengthpost, i

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
nth_erroris Datatypes.lengthpost = Somei ∧ SDatatypes.lengthpost < Datatypes.lengthis%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSDatatypes.lengthpost is i = Someq

rewrite Eis

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
nth_errorrevpost ++ i :: i1 :: revpre Datatypes.lengthpost = Somei ∧ SDatatypes.lengthpost < Datatypes.lengthrevpost ++ i :: i1 :: revpre%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSDatatypes.lengthpost revpost ++ i :: i1 :: revpre i = Someq

split ; | split

3 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
nth_errorrevpost ++ i :: i1 :: revpre Datatypes.lengthpost = Somei
focused goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
SDatatypes.lengthpost < Datatypes.lengthrevpost ++ i :: i1 :: revpre%nat
focused goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSDatatypes.lengthpost revpost ++ i :: i1 :: revpre i = Someq

+rewrite nth_error_app2 by rewrite length_rev ; lia

3 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
nth_errori :: i1 :: revpre Datatypes.lengthpost − Datatypes.lengthrevpost = Somei
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
SDatatypes.lengthpost < Datatypes.lengthrevpost ++ i :: i1 :: revpre%nat
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSDatatypes.lengthpost revpost ++ i :: i1 :: revpre i = Someq

rewrite length_rev , Nat.sub_diag

3 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
nth_errori :: i1 :: revpre 0 = Somei
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
SDatatypes.lengthpost < Datatypes.lengthrevpost ++ i :: i1 :: revpre%nat
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSDatatypes.lengthpost revpost ++ i :: i1 :: revpre i = Someq

reflexivity

2 open

deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
SDatatypes.lengthpost < Datatypes.lengthrevpost ++ i :: i1 :: revpre%nat
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSDatatypes.lengthpost revpost ++ i :: i1 :: revpre i = Someq

+rewrite length_app , length_rev

2 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
SDatatypes.lengthpost < Datatypes.lengthpost + Datatypes.lengthi :: i1 :: revpre%nat
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSDatatypes.lengthpost revpost ++ i :: i1 :: revpre i = Someq

simpl

2 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
SDatatypes.lengthpost < Datatypes.lengthpost + SSDatatypes.lengthrevpre%nat
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSDatatypes.lengthpost revpost ++ i :: i1 :: revpre i = Someq

lia

deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
ahead_acceptsonce fold_rightahead_steponce ptrs out skipnSSDatatypes.lengthpost revpost ++ i :: i1 :: revpre i = Someq

+replace skipnSSlengthpost revpost ++ i :: i1 :: revpre with revpre

2 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
ahead_acceptsonce fold_rightahead_steponce ptrs out revpre i = Someq
focused goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
revpre = skipnSSDatatypes.lengthpost revpost ++ i :: i1 :: revpre

∗rewrite fold_left_rev_right

2 open

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
ahead_acceptsonce fold_leftλx : facts y : inst ⇒ ahead_steponce ptrs y x pre out i = Someq
deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
revpre = skipnSSDatatypes.lengthpost revpost ++ i :: i1 :: revpre

exact Ha

deferred goal
once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
revpre = skipnSSDatatypes.lengthpost revpost ++ i :: i1 :: revpre

∗rewrite skipn_app , length_rev

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
revpre = skipnSSDatatypes.lengthpost revpost ++ skipnSSDatatypes.lengthpost − Datatypes.lengthpost i :: i1 :: revpre

replace SSlengthpost − lengthpost%nat with 2%nat by lia

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
revpre = skipnSSDatatypes.lengthpost revpost ++ skipn2 i :: i1 :: revpre

rewrite skipn_all2 by rewrite length_rev ; lia

once :
listname × def
ptrs :
listname × value
is :
listinst
out :
js :
listname
q :
H :
Inq sndahead_instsonce ptrs revis out [ ] js
pre :
listinst
i1, i :
post :
listinst
E :
revis = pre ++ i1 :: i :: post
Ha :
ahead_acceptsonce fold_leftstep_backonce ptrs pre out i = Someq
Eis :
is = revpost ++ i :: i1 :: revpre
⊢
revpre = [ ] ++ skipn2 i :: i1 :: revpre

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros once ptrs is out js q H
destruct ahead_insts_js_ _ _ _ _ _ _ H as Hj | i & post & _ & Ha | pre & i1 & i & post & E & Ha
–left
exact Hj
–rewrite ahead_accepts_nil in Ha
discriminate Ha
–right
assert Eis : is = revpost ++ i :: i1 :: revpre
{rewrite <- rev_involutiveis , E
rewrite rev_app_distr
simpl
rewrite <- ! app_assoc
reflexivity
exists lengthpost, i
rewrite Eis
split ; | split
+rewrite nth_error_app2 by rewrite length_rev ; lia
rewrite length_rev , Nat.sub_diag
reflexivity
+rewrite length_app , length_rev
simpl
lia
+replace skipnSSlengthpost revpost ++ i :: i1 :: revpre with revpre
∗rewrite fold_left_rev_right
exact Ha
∗rewrite skipn_app , length_rev
replace SSlengthpost − lengthpost%nat with 2%nat by lia
rewrite skipn_all2 by rewrite length_rev ; lia
reflexivity

The sweep over the blocks

Searching from position n + 1 gives the index from n, plus one.

139Lemma index_of_S
∀ l ls n
index_ofl ls Sn = option_mapS index_ofl ls n
Explore proof 4 tactics

Initial goal

⊢
∀l : name ls : listname n : nat, index_ofl ls Sn = option_mapS index_ofl ls n

intros l ls

l :
ls :
listname
⊢
∀n : nat, index_ofl ls Sn = option_mapS index_ofl ls n

induction ls as | l′ ls IH ; intros n ; reflexivity |

l, l′ :
ls :
listname
IH :
∀n : nat, index_ofl ls Sn = option_mapS index_ofl ls n
n :
nat
⊢
index_ofl l′ :: ls Sn = option_mapS index_ofl l′ :: ls n

simpl

l, l′ :
ls :
listname
IH :
∀n : nat, index_ofl ls Sn = option_mapS index_ofl ls n
n :
nat
⊢
name_eqbl l′
→
SomeSn
else
index_ofl ls SSn
=
option_mapS
name_eqbl l′
→
Somen
else
index_ofl ls Sn

destruct name_eqbl l′ ; reflexivity | apply IH

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros l ls
induction ls as | l′ ls IH ; intros n ; reflexivity |
simpl
destruct name_eqbl l′ ; reflexivity | apply IH

In a list without duplicates, a name's index is its position.

146Lemma index_of_nth
∀ ls j l
no_dupsls = true
nth_errorls j = Somel
index_ofl ls 0 = Somej
Explore proof 16 tactics

Initial goal

⊢
∀ls : listname j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej

induction ls as | l0 ls IH ; intros j l Hnd Hj ; destruct j ; discriminate Hj |

l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hnd :
no_dupsl0 :: ls = true
Hj :
nth_errorl0 :: ls j = Somel
⊢
index_ofl l0 :: ls 0 = Somej

simpl in Hnd

l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hnd :
negbmeml0 ls && no_dupsls = true
Hj :
nth_errorl0 :: ls j = Somel
⊢
index_ofl l0 :: ls 0 = Somej

apply andb_true_iff in Hnd as Hn Hnd

l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
negbmeml0 ls = true
Hnd :
no_dupsls = true
Hj :
nth_errorl0 :: ls j = Somel
⊢
index_ofl l0 :: ls 0 = Somej

apply negb_true_iff in Hn

l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorl0 :: ls j = Somel
⊢
index_ofl l0 :: ls 0 = Somej

destruct j as | j ; simpl in Hj |- *

2 open

l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
Somel0 = Somel
⊢
→
Some0%nat
else
index_ofl ls 1
=
Some0%nat
focused goal
l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel
⊢
→
Some0%nat
else
index_ofl ls 1
=
SomeSj

–injection Hj as ←

2 open

l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
⊢
→
Some0%nat
else
index_ofl0 ls 1
=
Some0%nat
deferred goal
l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel
⊢
→
Some0%nat
else
index_ofl ls 1
=
SomeSj

rewrite name_eqb_refl

2 open

l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
⊢
Some0%nat = Some0%nat
deferred goal
l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel
⊢
→
Some0%nat
else
index_ofl ls 1
=
SomeSj

reflexivity

deferred goal
l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel
⊢
→
Some0%nat
else
index_ofl ls 1
=
SomeSj

–assert E : name_eqbl l0 = false

2 open

l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel
⊢
name_eqbl l0 = false
focused goal
l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel
E :
name_eqbl l0 = false
⊢
→
Some0%nat
else
index_ofl ls 1
=
SomeSj

{apply name_eqb_false

2 open

l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel
⊢
l ≠ l0
deferred goal
l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel
E :
name_eqbl l0 = false
⊢
→
Some0%nat
else
index_ofl ls 1
=
SomeSj

intros →

2 open

l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel0
⊢
False
deferred goal
l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel
E :
name_eqbl l0 = false
⊢
→
Some0%nat
else
index_ofl ls 1
=
SomeSj

pose proof mem_false_ _ Hn _ nth_error_In_ _ Hj as E

2 open

l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel0
E :
name_eqbl0 l0 = false
⊢
False
deferred goal
l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel
E :
name_eqbl l0 = false
⊢
→
Some0%nat
else
index_ofl ls 1
=
SomeSj

rewrite name_eqb_refl in E

2 open

l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel0
E :
true = false
⊢
False
deferred goal
l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel
E :
name_eqbl l0 = false
⊢
→
Some0%nat
else
index_ofl ls 1
=
SomeSj

discriminate E

deferred goal
l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel
E :
name_eqbl l0 = false
⊢
→
Some0%nat
else
index_ofl ls 1
=
SomeSj

rewrite E , index_of_S , IH_ _ Hnd Hj

l0 :
ls :
listname
IH :
∀j : nat l : name, no_dupsls = true → nth_errorls j = Somel → index_ofl ls 0 = Somej
j :
nat
l :
Hn :
meml0 ls = false
Hnd :
no_dupsls = true
Hj :
nth_errorls j = Somel
E :
name_eqbl l0 = false
⊢
option_mapS Somej = SomeSj

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
induction ls as | l0 ls IH ; intros j l Hnd Hj ; destruct j ; discriminate Hj |
simpl in Hnd
apply andb_true_iff in Hnd as Hn Hnd
apply negb_true_iff in Hn
destruct j as | j ; simpl in Hj |- *
–injection Hj as ←
reflexivity
–assert E : name_eqbl l0 = false
intros →
pose proof mem_false_ _ Hn _ nth_error_In_ _ Hj as E
rewrite name_eqb_refl in E
discriminate E
rewrite E , index_of_S , IH_ _ Hnd Hj
reflexivity

The sweep over a fixed list of blocks bs with unique labels, given the single definitions once and the proofs' pointers ptrs.

161Section Sweep
163Variables once : listname × def
163Variables ptrs : listname × value
163Variables bs : listblock
164Hypothesis Hnd
no_dupsmapb_label bs = true
166Let ord ≔

The state after the sweep has walked the blocks S, from the last.

169Definition sweepS : listblock : listname × facts × listname ≔
fold_leftahead_blockord once ptrs revS [ ], [ ]

One block of the sweep (ahead_block/6), unfolded: it puts the block's entry facts in the table, with its phis' names ended, and adds what its walk accepts to the list of proofs.

175Lemma ahead_block_eq
Explore proof 10 tactics

Initial goal

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
⊢
∀ins : listname × facts js : listname b : block, ahead_blockord once ptrs ins, js b = putb_labelb phis_end_needsb_phisb fold_rightahead_steponce ptrs exit_inord ins b b_instsb ins, sndahead_instsonce ptrs revb_instsb exit_inord ins b [ ] js

intros ins js b

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
ins :
listname × facts
js :
listname
⊢
ahead_blockord once ptrs ins, js b = putb_labelb phis_end_needsb_phisb fold_rightahead_steponce ptrs exit_inord ins b b_instsb ins, sndahead_instsonce ptrs revb_instsb exit_inord ins b [ ] js

unfold ahead_block

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
ins :
listname × facts
js :
listname
⊢
let 'entry0, js′ ≔ ahead_instsonce ptrs revb_instsb ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb [ ] js in
putb_labelb phis_end_needsb_phisb entry0 ins, js′
=
putb_labelb phis_end_needsb_phisb fold_rightahead_steponce ptrs exit_inord ins b b_instsb ins, sndahead_instsonce ptrs revb_instsb exit_inord ins b [ ] js

pose proof ahead_insts_afteronce ptrs revb_instsb exit_inord ins b [ ] js as E

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
ins :
listname × facts
js :
listname
E :
fstahead_instsonce ptrs revb_instsb exit_inord ins b [ ] js = fold_leftstep_backonce ptrs revb_instsb exit_inord ins b
⊢
let 'entry0, js′ ≔ ahead_instsonce ptrs revb_instsb ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb [ ] js in
putb_labelb phis_end_needsb_phisb entry0 ins, js′
=
putb_labelb phis_end_needsb_phisb fold_rightahead_steponce ptrs exit_inord ins b b_instsb ins, sndahead_instsonce ptrs revb_instsb exit_inord ins b [ ] js

unfold exit_in in E |- *

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
ins :
listname × facts
js :
listname
E :
⊢
let 'entry0, js′ ≔ ahead_instsonce ptrs revb_instsb ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb [ ] js in
putb_labelb phis_end_needsb_phisb entry0 ins, js′
=

destruct ahead_insts_ _ _ _ _ _ as entry0 js′ eqn: Ea

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
ins :
listname × facts
js :
listname
entry0 :
js′ :
listname
Ea :
ahead_instsonce ptrs revb_instsb ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb [ ] js = entry0, js′
E :
fstentry0, js′ = fold_leftstep_backonce ptrs revb_instsb ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb
⊢
putb_labelb phis_end_needsb_phisb entry0 ins, js′ = putb_labelb phis_end_needsb_phisb fold_rightahead_steponce ptrs ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb b_instsb ins, sndentry0, js′

simpl in E |- *

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
ins :
listname × facts
js :
listname
entry0 :
js′ :
listname
Ea :
ahead_instsonce ptrs revb_instsb ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb [ ] js = entry0, js′
E :
entry0 = fold_leftstep_backonce ptrs revb_instsb ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb

rewrite E

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
ins :
listname × facts
js :
listname
entry0 :
js′ :
listname
Ea :
ahead_instsonce ptrs revb_instsb ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb [ ] js = entry0, js′
E :
entry0 = fold_leftstep_backonce ptrs revb_instsb ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb

unfold step_back

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
ins :
listname × facts
js :
listname
entry0 :
js′ :
listname
Ea :
ahead_instsonce ptrs revb_instsb ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb [ ] js = entry0, js′
E :
entry0 = fold_leftstep_backonce ptrs revb_instsb ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb
⊢
putb_labelb phis_end_needsb_phisb fold_leftλfs : facts i : inst ⇒ ahead_steponce ptrs i fs revb_instsb ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb ins, js′ = putb_labelb phis_end_needsb_phisb fold_rightahead_steponce ptrs ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb b_instsb ins, js′

rewrite <- fold_left_rev_right , rev_involutive

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
ins :
listname × facts
js :
listname
entry0 :
js′ :
listname
Ea :
ahead_instsonce ptrs revb_instsb ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb [ ] js = entry0, js′
E :
entry0 = fold_leftstep_backonce ptrs revb_instsb ahead_meetmapahead_edgeord index_ofb_labelb ord 0 ins jump_targetsb_jumpb

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ins js b
pose proof ahead_insts_afteronce ptrs revb_instsb exit_inord ins b [ ] js as E
unfold exit_in in E |- *
destruct ahead_insts_ _ _ _ _ _ as entry0 js′ eqn: Ea
simpl in E |- *
rewrite E
unfold step_back
rewrite <- fold_left_rev_right , rev_involutive
reflexivity

A table entry for a label put earlier in the block order does not change the facts at a later block's jump: its edges read only the labels after it.

190Lemma exit_put
∀ lb jb e ins b p
index_oflb ord 0 = Somejb
index_ofb_labelb ord 0 = Somep
jb ≤ p%nat
exit_inord putlb e ins b = exit_inord ins b
Explore proof 17 tactics

Initial goal

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
⊢
∀lb : name jb : nat e : facts ins : listname × facts b : block p : nat, index_oflb ord 0 = Somejb → index_ofb_labelb ord 0 = Somep → jb ≤ p%nat → exit_inord putlb e ins b = exit_inord ins b

intros lb jb e ins b p Hj Hp Hle

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
⊢
exit_inord putlb e ins b = exit_inord ins b

unfold exit_in

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat

rewrite Hp

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat

f_equal

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
⊢
mapahead_edgeord Somep putlb e ins jump_targetsb_jumpb = mapahead_edgeord Somep ins jump_targetsb_jumpb

apply map_ext

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
⊢
∀a : target, ahead_edgeord Somep putlb e ins a = ahead_edgeord Somep ins a

intros l | l ; | reflexivity

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
⊢
ahead_edgeord Somep putlb e ins Tol = ahead_edgeord Somep ins Tol

cbn beta iota delta [ ahead_edge ]

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
⊢
match index_ofl ord 0 with
Sometp
⇒
match lookupl putlb e ins with
Somefs
⇒
p <? tp%nat
→
fs
else
[ ]
None
⇒
[ ]
None
⇒
[ ]
=
match index_ofl ord 0 with
Sometp
⇒
match lookupl ins with
Somefs
⇒
p <? tp%nat
→
fs
else
[ ]
None
⇒
[ ]
None
⇒
[ ]

destruct index_ofl ord 0 as tp | eqn: Et ; | reflexivity

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
tp :
nat
Et :
index_ofl ord 0 = Sometp
⊢
match lookupl putlb e ins with
Somefs
⇒
p <? tp%nat
→
fs
else
[ ]
None
⇒
[ ]
=
match lookupl ins with
Somefs
⇒
p <? tp%nat
→
fs
else
[ ]
None
⇒
[ ]

destruct p <? tp%nat eqn: Elt

2 open

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
tp :
nat
Et :
index_ofl ord 0 = Sometp
Elt :
p <? tp%nat = true
⊢
match lookupl putlb e ins with
Somefs
⇒
fs
None
⇒
[ ]
=
match lookupl ins with
Somefs
⇒
fs
None
⇒
[ ]
focused goal
once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
tp :
nat
Et :
index_ofl ord 0 = Sometp
Elt :
p <? tp%nat = false
⊢
match lookupl putlb e ins with
Some_ | _
⇒
[ ]
=
match lookupl ins with
Some_ | _
⇒
[ ]

–apply Nat.ltb_lt in Elt

2 open

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
tp :
nat
Et :
index_ofl ord 0 = Sometp
Elt :
p < tp%nat
⊢
match lookupl putlb e ins with
Somefs
⇒
fs
None
⇒
[ ]
=
match lookupl ins with
Somefs
⇒
fs
None
⇒
[ ]
deferred goal
once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
tp :
nat
Et :
index_ofl ord 0 = Sometp
Elt :
p <? tp%nat = false
⊢
match lookupl putlb e ins with
Some_ | _
⇒
[ ]
=
match lookupl ins with
Some_ | _
⇒
[ ]

rewrite lookup_put_other ; reflexivity |

2 open

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
tp :
nat
Et :
index_ofl ord 0 = Sometp
Elt :
p < tp%nat
⊢
name_eqbl lb = false
deferred goal
once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
tp :
nat
Et :
index_ofl ord 0 = Sometp
Elt :
p <? tp%nat = false
⊢
match lookupl putlb e ins with
Some_ | _
⇒
[ ]
=
match lookupl ins with
Some_ | _
⇒
[ ]

apply name_eqb_false

2 open

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
tp :
nat
Et :
index_ofl ord 0 = Sometp
Elt :
p < tp%nat
⊢
l ≠ lb
deferred goal
once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
tp :
nat
Et :
index_ofl ord 0 = Sometp
Elt :
p <? tp%nat = false
⊢
match lookupl putlb e ins with
Some_ | _
⇒
[ ]
=
match lookupl ins with
Some_ | _
⇒
[ ]

intros →

2 open

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
tp :
nat
Et :
index_oflb ord 0 = Sometp
Elt :
p < tp%nat
⊢
False
deferred goal
once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
tp :
nat
Et :
index_ofl ord 0 = Sometp
Elt :
p <? tp%nat = false
⊢
match lookupl putlb e ins with
Some_ | _
⇒
[ ]
=
match lookupl ins with
Some_ | _
⇒
[ ]

rewrite Hj in Et

2 open

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
tp :
nat
Et :
Somejb = Sometp
Elt :
p < tp%nat
⊢
False
deferred goal
once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
tp :
nat
Et :
index_ofl ord 0 = Sometp
Elt :
p <? tp%nat = false
⊢
match lookupl putlb e ins with
Some_ | _
⇒
[ ]
=
match lookupl ins with
Some_ | _
⇒
[ ]

injection Et as ←

2 open

once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
Elt :
p < jb%nat
⊢
False
deferred goal
once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
tp :
nat
Et :
index_ofl ord 0 = Sometp
Elt :
p <? tp%nat = false
⊢
match lookupl putlb e ins with
Some_ | _
⇒
[ ]
=
match lookupl ins with
Some_ | _
⇒
[ ]

lia

deferred goal
once :
listname × def
ptrs :
listname × value
bs :
listblock
Hnd :
no_dupsmapb_label bs = true
ord :=
mapb_label bs : listname
lb :
jb :
nat
ins :
listname × facts
p :
nat
Hj :
index_oflb ord 0 = Somejb
Hp :
index_ofb_labelb ord 0 = Somep
Hle :
jb ≤ p%nat
l :
tp :
nat
Et :
index_ofl ord 0 = Sometp
Elt :
p <? tp%nat = false
⊢
match lookupl putlb e ins with
Some_ | _
⇒
[ ]
=
match lookupl ins with
Some_ | _
⇒
[ ]

–destruct lookupl putlb e ins , lookupl ins ; reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros lb jb e ins b p Hj Hp Hle
unfold exit_in
rewrite Hp
f_equal
apply map_ext
intros l | l ; | reflexivity
cbn beta iota delta [ ahead_edge ]
destruct index_ofl ord 0 as tp | eqn: Et ; | reflexivity
destruct p <? tp%nat eqn: Elt
–apply Nat.ltb_lt in Elt
rewrite lookup_put_other ; reflexivity |
intros →
rewrite Hj in Et
injection Et as ←
lia
–destruct lookupl putlb e ins , lookupl ins ; reflexivity

After the sweep has walked the blocks from the j-th to the last, each of them has its entry facts in the table, and each accepted proof was accepted in one of them as block_accepts says, both read from the table as it stands. The induction behind ahead_entry and ahead_accepted.

207Lemma ahead_fold_suffix
∀ j
∀b, Inb skipnj bs → lookupb_labelb fstsweepskipnj bs = Somephis_end_needsb_phisb fold_rightahead_steponce ptrs exit_inord fstsweepskipnj bs b b_instsb ∧ ∀q, Inq sndsweepskipnj bs → ∃b k i, Inb skipnj bs ∧ nth_errorb_instsb k = Somei ∧ Sk < lengthb_instsb%nat ∧ ahead_acceptsonce fold_rightahead_steponce ptrs exit_inord fstsweepskipnj bs b skipnSSk b_instsb i = Someq
Proof 58 steps Qed
intros j
remember skipnj bs as S eqn: ES
revert j ES
induction S as | b S IH ; intros j ES
–split ; intros b |
intros q Hq
destruct Hq
–assert Hb : nth_errorbs j = Someb by rewrite <- Nat.add_0_rj , <- nth_error_skipn , <- ES ; reflexivity
assert ES′ : S = skipnDatatypes.Sj bs
{rewrite <- skipn_skipn1 j
rewrite <- ES
reflexivity
destruct IH_ ES' as IHe IHj
assert Hpos : index_ofb_labelb ord 0 = Somej by apply index_of_nth ; exact Hnd | unfold ord ; rewrite nth_error_map , Hb ; reflexivity
assert Hlater : ∀b′, Inb′ S → ∃p, index_ofb_labelb′ ord 0 = Somep ∧ j < p%nat
{intros b′ Hin
rewrite ES' in Hin
destruct In_nth_error_ _ Hin as t Ht
rewrite nth_error_skipn in Ht
exists Datatypes.Sj + t%nat
split ; | lia
apply index_of_nth ; exact Hnd | unfold ord ; rewrite nth_error_map , Ht ; reflexivity
unfold sweep
simpl rev
rewrite fold_left_app
fold sweepS
simpl fold_left
destruct sweepS as ins js eqn: Esw
simpl fst
simpl snd
set e := phis_end_needs_ _
assert Hx : ∀b′, Inb′ b :: S → exit_inord putb_labelb e ins b′ = exit_inord ins b′
{intros b′ ← | Hin ; exact exit_put_ _ _ _ _ _ Hpos Hpos le_n_ |
destruct Hlater_ Hin as p & Hp & Hlt
exact exit_put_ _ _ _ _ _ Hpos Hp ltac:lia
split
+intros b′ Hin
rewrite Hx_ Hin
destruct Hin as ← | Hin
∗rewrite lookup_put_same
reflexivity
∗destruct Hlater_ Hin as p & Hp & Hlt
rewrite lookup_put_other ; exact IHe_ Hin |
intros E
rewrite E , Hpos in Hp
injection Hp as →
lia
+intros q Hq
destruct block_accepts_ _ _ _ _ _ Hq as Hj | k & i & Hk & Hlen & Ha
∗destruct IHj_ Hj as b′ & k & i & Hin & Hk & Hlen & Ha
exists b', k, i
rewrite Hx_ or_introrHin
split ; right ; exact Hin | auto
∗exists b, k, i
rewrite Hx_ or_introleq_refl
split ; left ; reflexivity | auto

In a function f whose block labels are unique, each block b's entry facts in the final table are what its instructions make of its exit facts (facts_from of block_exit), with the names its phis define ended. So the table the pass leaves is a fixed point that can be read at any point.

255Theorem ahead_entry
Explore proof 3 tactics
Source script
intros f b Hnd Hin
exact Heb Hin

In a function f whose block labels are unique, a proof q that ahead_justified/3 accepts is the instruction at some index k of a block b, not the last, accepted (ahead_accepts, a single-definition check_ahead whose early bytes a need covers) with the facts before the instructions after its access, read from the final table. Doomed.v starts its doomed frame from this.

271Theorem ahead_accepted
∀ f q
∃b k i, Inb fn_blocksf ∧ nth_errorb_instsb k = Somei ∧ Sk < lengthb_instsb%nat ∧ ahead_acceptssingle_definitionsf facts_fromf skipnSSk b_instsb block_exitf b i = Someq
Explore proof 3 tactics

Initial goal

⊢
∀f : func q : name, no_dupsmapb_label fn_blocksf = true → Inq ahead_justifiedf single_definitionsf → ∃b : block k : nat i : inst, Inb fn_blocksf ∧ nth_errorb_instsb k = Somei ∧ Sk < Datatypes.lengthb_instsb%nat ∧ ahead_acceptssingle_definitionsf facts_fromf skipnSSk b_instsb block_exitf b i = Someq

intros f q Hnd Hq

⊢
∃b : block k : nat i : inst, Inb fn_blocksf ∧ nth_errorb_instsb k = Somei ∧ Sk < Datatypes.lengthb_instsb%nat ∧ ahead_acceptssingle_definitionsf facts_fromf skipnSSk b_instsb block_exitf b i = Someq

destruct ahead_fold_suffixsingle_definitionsf proof_pointersf single_definitionsf _ Hnd 0 as _ Hj

f :
q :
Hnd :
Hj :
∀q : name, Inq sndsweepsingle_definitionsf proof_pointersf single_definitionsf fn_blocksf skipn0 fn_blocksf → ∃b : block k : nat i : inst, Inb skipn0 fn_blocksf ∧ nth_errorb_instsb k = Somei ∧ Sk < Datatypes.lengthb_instsb%nat ∧ ahead_acceptssingle_definitionsf fold_rightahead_stepsingle_definitionsf proof_pointersf single_definitionsf exit_inmapb_label fn_blocksf fstsweepsingle_definitionsf proof_pointersf single_definitionsf fn_blocksf skipn0 fn_blocksf b skipnSSk b_instsb i = Someq
⊢
∃b : block k : nat i : inst, Inb fn_blocksf ∧ nth_errorb_instsb k = Somei ∧ Sk < Datatypes.lengthb_instsb%nat ∧ ahead_acceptssingle_definitionsf facts_fromf skipnSSk b_instsb block_exitf b i = Someq

exact Hjq Hq

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros f q Hnd Hq
exact Hjq Hq