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
| Decision | Why |
|---|---|
| the facts are read from the final table | an 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_accepts | as ir.pl's ahead_block/6 and ahead_edge/5 are; the proofs read each part on its own |
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).
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.
The needs at the jump of a block b of a function f, read from the final table ahead_entries.
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.
One block
One backward step, ahead_step with its arguments in the order fold_left takes.
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.
Explore proof 5 tactics
Initial goal
intros once ptrs ris
induction ris as | i ris IH ; intros after next js ; reflexivity |
simpl
rewrite IH
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
With no facts after it, no instruction is accepted: a check_ahead needs a need to cover its early bytes.
Explore proof 12 tactics
Initial goal
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 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
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
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.
Explore proof 14 tactics
Initial goal
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
3 openfocused goal
focused goal
–destruct ahead_acceptsonce next i as q′ | eqn: Ea ; | left ; exact Hj
3 opendeferred goal
deferred goal
destruct Hj as ← | Hj ; right ; left ; eauto | left ; exact Hj
2 opendeferred goal
deferred goal
–right
2 opendeferred goal
right
2 opendeferred goal
exists [ ], i, i′, post
2 opendeferred goal
auto
deferred goal
–right
right
exists i :: pre, i1, i′, post
auto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
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.
Explore proof 29 tactics
Initial goal
intros once ptrs is out js q H
destruct ahead_insts_js_ _ _ _ _ _ _ H as Hj | i & post & _ & Ha | pre & i1 & i & post & E & Ha
3 openfocused goal
focused goal
–left
3 opendeferred goal
deferred goal
exact Hj
2 opendeferred goal
deferred goal
–rewrite ahead_accepts_nil in Ha
2 opendeferred goal
discriminate Ha
deferred goal
–right
assert Eis : is = revpost ++ i :: i1 :: revpre
2 openfocused goal
{rewrite <- rev_involutiveis , E
2 opendeferred goal
rewrite rev_app_distr
2 opendeferred goal
simpl
2 opendeferred goal
rewrite <- ! app_assoc
2 opendeferred goal
reflexivity
deferred goal
exists lengthpost, i
rewrite Eis
split ; | split
3 openfocused goal
focused goal
+rewrite nth_error_app2 by rewrite length_rev ; lia
3 opendeferred goal
deferred goal
rewrite length_rev , Nat.sub_diag
3 opendeferred goal
deferred goal
reflexivity
2 opendeferred goal
deferred goal
+rewrite length_app , length_rev
2 opendeferred goal
simpl
2 opendeferred goal
lia
deferred goal
+replace skipnSSlengthpost revpost ++ i :: i1 :: revpre with revpre
2 openfocused goal
∗rewrite fold_left_rev_right
2 opendeferred goal
exact Ha
deferred goal
∗rewrite skipn_app , length_rev
replace SSlengthpost − lengthpost%nat with 2%nat by lia
rewrite skipn_all2 by rewrite length_rev ; lia
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The sweep over the blocks
Searching from position n + 1 gives the index from n, plus one.
Explore proof 4 tactics
Initial goal
intros l ls
induction ls as | l′ ls IH ; intros n ; reflexivity |
simpl
destruct name_eqbl l′ ; reflexivity | apply IH
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
In a list without duplicates, a name's index is its position.
Explore proof 16 tactics
Initial goal
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 |- *
2 open–injection Hj as ←
2 openrewrite name_eqb_refl
2 openreflexivity
–assert E : name_eqbl l0 = false
2 open{apply name_eqb_false
2 openintros →
2 openpose proof mem_false_ _ Hn _ nth_error_In_ _ Hj as E
2 openrewrite name_eqb_refl in E
2 opendiscriminate E
rewrite E , index_of_S , IH_ _ Hnd Hj
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The sweep over a fixed list of blocks bs with unique labels, given the single definitions once and the proofs' pointers ptrs.
The state after the sweep has walked the blocks S, from the last.
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.
Explore proof 10 tactics
Initial goal
intros ins js b
unfold ahead_block
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
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
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.
Explore proof 17 tactics
Initial goal
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
2 open–apply Nat.ltb_lt in Elt
2 openrewrite lookup_put_other ; reflexivity |
2 openapply name_eqb_false
2 openintros →
2 openrewrite Hj in Et
2 openinjection Et as ←
2 openlia
–destruct lookupl putlb e ins , lookupl ins ; reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
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.
Proof 58 steps Qed
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.
Explore proof 3 tactics
Initial goal
intros f b Hnd Hin
destruct ahead_fold_suffixsingle_definitionsf proof_pointersf single_definitionsf _ Hnd 0 as He _
exact Heb Hin
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
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.
Explore proof 3 tactics
Initial goal
intros f q Hnd Hq
destruct ahead_fold_suffixsingle_definitionsf proof_pointersf single_definitionsf _ Hnd 0 as _ Hj
exact Hjq Hq
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.