Theory LR_Det

(* Author: Basil Fürer *)

theory LR_Det
  imports LR_Driver
begin

section ‹The static sufficient condition for const‹mdet››

text ‹This theory proves ‹rlalr_conflicts G Shn = [] ⟹ mdet G Shn›
  (text‹rlalr_sufficient›, at the end): an executable check on the
  driver's tables implies the determinism premise of its completeness.
  After Barthwal cite‹‹Def.~5.3.7, Thm.~5.4.4› in "barthwal2010-thesis-cfl-hol4"› (‹okSlr›: conflict
  freedom is demanded on viable-prefix-reachable states only), DeRemer and
  Pennello cite‹‹Sect.~3› in "deremer1982-lalr-lookahead"› (per-item lookahead) and Jourdan, Pottier and
  Leroy cite‹‹Sect.~3.4, Thm.~4› in "jourdan2012-validating-lr1"› (a validator on the automaton; the validators imply
  unambiguity).

  In order: saturation of the anchored reachable closure; the precise
  (viable-prefix) automaton text‹pr0_states› and its worklist; the
  rigid-point conflict analysis text‹rlalr_conflicts›; tracking every
  reachable configuration by the driver's index stack; the pooled width
  invariant; the canonical tracked stack text‹strack› and its descent;
  the soundness of the rigid-point walk, from which
  text‹rlalr_sufficient› follows.›


section ‹Saturation of the anchored reachable closure›

text ‹The report and the check read the fuelled const‹wreach›, which is
  total; this section shows it is saturated.  The general argument:
  const‹wreach_step› only emits dot-0 items, so regardless of the kernel the
  chain grows by at most one item per production per typ‹wrel›, which is
  const‹wreach›'s fuel.  text‹funpow_saturates› bounds the chain by
  term‹card U› for a universe term‹U› containing the start, too coarse
  here; the variant below bounds it by the increment.›


subsection ‹const‹wreach_step› is extensional, monotone, and dot-0 bounded›

text ‹const‹wreach_step› inlines its contribution function; name it for the
  set-level reasoning below.›

definition wcontrib :: ‹('n, 't) is_cfg ⇒ ('n, 't) witem ⇒ ('n, 't) witem list› where
  ‹wcontrib G = (λ(pr, m, ρ).
      if m < length (snd pr)
      then (case fst (snd pr ! m) of
             Nt B ⇒ map (λbr. (br, 0, wcomp (winv (w_of (snd (snd pr ! m)))) ρ))
                     (filter (λbr. fst br = B) (iprods G))
           | Tm _ ⇒ [])
      else [])›

lemma wreach_step_alt:
  ‹wreach_step G ws = remdups (ws @ concat (map (wcontrib G) ws))›
  unfolding wreach_step_def wcontrib_def by simp

lemma wreach_step_set:
  ‹set (wreach_step G xs) = set xs ∪ (⋃x ∈ set xs. set (wcontrib G x))›
  unfolding wreach_step_alt by auto

lemma wreach_step_ext:
  ‹set xs = set ys ⟹ set (wreach_step G xs) = set (wreach_step G ys)›
  by (simp add: wreach_step_set)

lemma wreach_step_mono: ‹set xs ⊆ set (wreach_step G xs)›
  by (simp add: wreach_step_set)

text ‹Every item const‹wreach_step› emits sits at dot 0 on a production of
  the grammar; this bounds the growth independently of the kernel.›

definition wdot0 :: ‹('n, 't) is_cfg ⇒ ('n, 't) witem list› where
  ‹wdot0 G = concat (map (λpr. map (λρ. (pr, 0, ρ))
      [WEq, WGe, WGt, WLe, WLt, WAny]) (iprods G))›

lemma wdot0_mem: ‹pr ∈ set (iprods G) ⟹ (pr, 0, ρ) ∈ set (wdot0 G)›
  unfolding wdot0_def by (cases ρ) force+

lemma length_wdot0: ‹length (wdot0 G) = length (iprods G) * 6›
proof -
  have ‹length (concat (map (λpr. [(pr, 0, WEq), (pr, 0, WGe), (pr, 0, WGt),
        (pr, 0, WLe), (pr, 0, WLt), (pr, 0, WAny)]) ps)) = length ps * 6›
    for ps :: ‹('n × ('n, 't) rhs) list›
    by (induction ps) auto
  then show ?thesis unfolding wdot0_def by simp
qed

lemma wcontrib_simp:
  ‹wcontrib G (pr, m, ρ) =
      (if m < length (snd pr)
       then (case fst (snd pr ! m) of
              Nt B ⇒ map (λbr. (br, 0, wcomp (winv (w_of (snd (snd pr ! m)))) ρ))
                      (filter (λbr. fst br = B) (iprods G))
            | Tm _ ⇒ [])
       else [])›
  unfolding wcontrib_def by simp

lemma wcontrib_dot0:
  assumes ‹y ∈ set (wcontrib G x)›
  shows ‹y ∈ set (wdot0 G)›
proof -
  obtain pr m ρ where x: ‹x = (pr, m, ρ)› by (cases x) auto
  show ?thesis
  proof (cases ‹m < length (snd pr)›)
    case False
    then show ?thesis using assms unfolding x wcontrib_simp by simp
  next
    case True
    show ?thesis
    proof (cases ‹fst (snd pr ! m)›)
      case (Tm a)
      then show ?thesis using assms True unfolding x wcontrib_simp by simp
    next
      case (Nt B)
      have ‹y ∈ set (map (λbr. (br, 0, wcomp (winv (w_of (snd (snd pr ! m)))) ρ))
                     (filter (λbr. fst br = B) (iprods G)))›
        using assms True Nt unfolding x wcontrib_simp by simp
      then obtain br where br: ‹br ∈ set (iprods G)›
        and yeq: ‹y = (br, 0, wcomp (winv (w_of (snd (snd pr ! m)))) ρ)› by auto
      show ?thesis unfolding yeq by (rule wdot0_mem[OF br])
    qed
  qed
qed
lemma wreach_step_delta: ‹set (wreach_step G xs) ⊆ set xs ∪ set (wdot0 G)›
  by (auto simp: wreach_step_set dest: wcontrib_dot0)

subsection ‹Hence the fuelled const‹wreach› is saturated›

theorem wreach_stable: ‹set (wreach_step G (wreach G s)) = set (wreach G s)›
  unfolding wreach_def
proof (rule funpow_saturates_delta[where D = ‹set (wdot0 G)›])
  show ‹⋀xs ys. set xs = set ys ⟹ set (wreach_step G xs) = set (wreach_step G ys)›
    by (rule wreach_step_ext)
  show ‹⋀xs. set xs ⊆ set (wreach_step G xs)› by (rule wreach_step_mono)
  show ‹⋀xs. set (wreach_step G xs) ⊆ set xs ∪ set (wdot0 G)›
    by (rule wreach_step_delta)
  show ‹finite (set (wdot0 G))› by simp
  show ‹card (set (wdot0 G)) ≤ Suc (length (iprods G) * 6)›
    using card_length[of ‹wdot0 G›] length_wdot0[of G] by simp
qed

lemma funpow_wreach_mono: ‹set xs ⊆ set ((wreach_step G ^^ k) xs)›
proof (induction k)
  case (Suc k)
  have ‹set ((wreach_step G ^^ k) xs) ⊆ set ((wreach_step G ^^ Suc k) xs)›
    using wreach_step_mono by simp
  with Suc show ?case by simp
qed simp

lemma wreach_kernel: ‹set (wkernel s) ⊆ set (wreach G s)›
  unfolding wreach_def by (rule funpow_wreach_mono)

text ‹const‹wreach› is saturated, so it contains everything one
  const‹wreach_step› would add.›

lemma wreach_emit:
  assumes mem: ‹(pr', m', ρ') ∈ set (wreach G s)›
    and m_lt: ‹m' < length (snd pr')›
    and nxt: ‹fst (snd pr' ! m') = Nt (fst br)›
    and br: ‹br ∈ set (iprods G)›
  shows ‹(br, 0, wcomp (winv (w_of (snd (snd pr' ! m')))) ρ') ∈ set (wreach G s)›
proof -
  have ‹(br, 0, wcomp (winv (w_of (snd (snd pr' ! m')))) ρ')
        ∈ set (wcontrib G (pr', m', ρ'))›
    unfolding wcontrib_simp using m_lt nxt br by simp
  then have ‹(br, 0, wcomp (winv (w_of (snd (snd pr' ! m')))) ρ')
        ∈ set (wreach_step G (wreach G s))›
    using mem by (auto simp: wreach_step_set)
  then show ?thesis unfolding wreach_stable .
qed

section ‹The item-relative conflict analysis: diagnosis›

text ‹Why the entry-relative walk below cannot separate the remaining
  states, on the state after ‹"type" LId TVars› of an ML-style signature
  grammar (state 7 of const‹pr0_states›).  Its kernel holds
  ‹Spec = "type"= LId> TVars> ⋅›, the same production continued by
  ‹"=" Ty›, and ‹TVars = TVars≥ ⋅ LId≥›.  The entry anchor is the anchor
  of the ‹TVars› subtree just read, and const‹wreach› relates it to each
  item's own indentation: ‹WGt› for the two ‹Spec› items (‹TVars>›), ‹WGe›
  for the ‹TVars› item (‹TVars≥›).  The shift cell on ‹LId› composes the
  inverse of that ‹WGe› with the element relation ‹LId≥›:
  ‹wcomp WLe WGe = WAny›.  The token is at or right of the inner ‹TVars›'
  indentation, which is at or left of the anchor; nothing relates the token
  to the anchor.  The reduce seeds on ‹LId› are the cells ‹WEq› (the next
  spec of the same block) and ‹WLt› (the next spec of an enclosing block,
  through ‹"module" UId ":" Sig>›), each composed with ‹winv WGt›: ‹WLt›.
  So the pair at the state is ‹(WLt, WAny)›, and no entry further back
  recovers a class from ‹WAny›.  The ‹WAny› is the item's: the shift side
  is a relation to the ‹TVars› item's indentation, the reduce side a
  relation to the ‹Spec› item's, and the entry anchor is ‹≥›-related to
  the one and ‹>›-related to the other, so the anchor is the wrong
  quantity to express either against.

  Expressed against the ‹Spec› item's own indentation both sides are
  exact.  The reduce side already is: a cell relates the lookahead's column
  to the completed item's left-hand-side indentation (‹WEq›, ‹WLt›).  The
  shift side is translated through the items that predicted it.  The
  ‹TVars› item at dot 1 was predicted one entry back, in the state after
  ‹"type" LId› (state 8), whose kernel is the two ‹Spec› items at dot 2; the
  predictors of ‹TVars› in that state's closure are those two items (through
  ‹TVars>›: the ‹TVars› indentation is strictly right of the ‹Spec›'s) and
  the ‹TVars› item itself (left recursion through ‹TVars≥›, which only
  repeats).  The shift side becomes ‹wcomp WGt WGe = WGt› against the
  ‹Spec› item's indentation, the reduce side is ‹WEq› or ‹WLt› against the
  same item's indentation, popped along the same entry, and the two are
  const‹wdisjoint›.

  The comparison is sound because the reference is one column.  ‹Spec› is
  anchored (‹anchored_nts› below: ‹"type"=›), so in the real frame every
  ‹Spec› item at a dot ‹≥ 1› has the singleton pool ‹{column of "type"}›,
  and two such items at the same dot in the same frame read that ‹"type"›
  at the same entry; both sides' relations hold at that column, a disjoint
  pair is impossible.  At a nonterminal whose pool is not a singleton the
  two sides may be satisfied at different pool elements and disjointness
  proves nothing: that is the two-action layout of an unanchored
  nonterminal (a constructor list, an arrow-type tail), which anchoring that
  nonterminal removes.  The other sound reference is the start item at the
  start state, whose pool is ‹{istart_ind}›.

  The walk that follows from this (the next section): a triple is a state
  with two cursors, each an item of the state's closure and a class relating
  the lookahead's column to the item's left-hand-side indentation.  A cursor
  at dot 0 is replaced by its predictors in the same state, the class
  composed with the predicted position's relation; two cursors at kernel
  items pop one entry along the same edge of the precise automaton (the
  entry symbol is the symbol before both dots), the classes unchanged, and
  where that entry is rigid both are first read against its column and a
  disjoint pair is refuted.  The ‹Spec› pair above is refuted one pop later,
  at the state entered over ‹"type"›.  At the start state both cursors predict
  up to the start item and are compared there.  No entry anchor, no
  ‹rho_classes›, no ‹tm_classes›.›

section ‹The item-relative conflict analysis›

text ‹Comparing the two sides of a candidate pair against a single shared
  state anchor is unsound for const‹mdet›: a reduce-built frame pools
  entry anchors, and the two sides can be live via different ones.  The
  comparison is sound only where both sides are read against one column: the
  column of a shifted token, the anchor of an anchored nonterminal, or
  ‹istart_ind› at the start state.  So the analysis keeps each side on its
  item.  A cursor is a typ‹('n, 't) witem› read item-relatively: in
  ‹(pr, m, σ)› the class ‹σ› relates the lookahead's column to the
  indentation of the instance of ‹pr›'s left-hand side the item stands for.
  A reduce seed is the completed item with its cell's relation, a shift seed
  the item whose dotted terminal is the lookahead, with that terminal's
  relation.  The walk goes back through the entries of the precise automaton
  as far as the start state: a cursor at dot 0 moves to the items that
  predicted it (the predicting position's relation composes, the state stays);
  two cursors at kernel items move together to every predecessor along the
  state's entry, unchanged.  const‹wdisjoint› runs where the entry is
  rigid, both cursors read against the entry's column through the relation
  of the symbol before their dots: a disjoint pair refutes the path, a pair
  that is not disjoint walks on, since the entry that separates the two
  sides may lie further back.  A pair that reaches the start item undisjoint
  is a conflict.  The walk is a worklist over triples (state, cursor,
  cursor) in a finite space; exhausted fuel reports a conflict, and so does a
  triple with both classes ‹WAny›: nothing composes out of ‹WAny›, so
  every descendant of such a triple is one, none is disjoint, and the walk
  would only reach the start item undisjoint; returning at once saves the
  walk.›

text ‹The analysis runs over the precise automaton (const‹pr0_states›
  with the const‹pgtab› gotos and the const‹la_fix› cells): these
  are the driver's own tables, so a cell that licenses a runtime reduce is one
  of the cells inspected here.›

definition pin_edges :: ‹(('n, 't) sym × nat) list list ⇒ nat ⇒
    (nat × ('n, 't) sym) list› where
  ‹pin_edges gt s = concat (map (λp.
       map (λ(X, s'). (p, X)) (filter (λ(X, s'). s' = s) (gt ! p)))
     [0..<length gt])›

text ‹All static reads below use const‹wreach›, the form the saturation
  lemmas of this theory speak about; the classes it carries are not used.›

text ‹A nonterminal ‹A› is ‹anchored› when every ‹A›-production starts with
  an ‹Eq›-related element that is a terminal or itself an anchored
  nonterminal: any tree of ‹A› then admits exactly one anchor, the column of
  its leftmost token (cf. the ‹anchored›/‹lead_refl› analysis of
  ‹Indentation_Sensitive› section 4).  A reduce-goto over an anchored
  nonterminal therefore carries a ‹rigid› entry anchor, a token column
  shared by both sides of a pair, and the const‹wdisjoint› comparison
  is sound there, as at a shift entry.  Computed as a decreasing fixpoint
  from the full nonterminal list.›

definition anchored_nts :: ‹('n, 't) is_cfg ⇒ 'n list› where
  ‹anchored_nts G = (let nts = remdups (map fst (iprods G));
       ok = (λS (B, rhs). rhs ≠ [] ∧ snd (hd rhs) = Eq ∧
               (case fst (hd rhs) of Tm _ ⇒ True | Nt B' ⇒ B' ∈ set S));
       step = (λS. filter (λA. list_all (λp. fst p ≠ A ∨ ok S p) (iprods G)) S)
   in (step ^^ length nts) nts)›

definition irigid :: ‹'n list ⇒ ('n, 't) sym ⇒ bool› where
  ‹irigid anc X ⟷ (case X of Tm _ ⇒ True | Nt B ⇒ B ∈ set anc)›

text ‹The walk reads the states' closures from ‹wrs›, the list of their
  const‹wreach› lists, computed once for all states.  The cursors that
  predicted an ‹A›-item at dot 0 in state ‹s›: the items of ‹s› with
  ‹Nt A› at the dot, the class composed with that position's relation (the
  predicted indentation relates by it to the predictor's).›

definition ipreds :: ‹('n, 't) witem list list ⇒ nat ⇒ 'n ⇒ wrel ⇒
    ('n, 't) witem list› where
  ‹ipreds wrs s A σ = remdups (List.map_filter (λ(pr, m, _).
      if m < length (snd pr) ∧ fst (snd pr ! m) = Nt A
      then Some (pr, m, wcomp (w_of (snd (snd pr ! m))) σ) else None)
      (wrs ! s))›

text ‹Whether a closure holds an item, in any class.›

definition ihas :: ‹('n, 't) witem list ⇒ 'n × ('n, 't) rhs ⇒ nat ⇒ bool› where
  ‹ihas ws pr m ⟷ list_ex (λ(pr', m', _). pr' = pr ∧ m' = m) ws›

text ‹A kernel cursor read against the column of the state's entry, through
  the relation of the symbol before its dot (the kernel item's pool was
  filtered by that relation against the entry pool).›

definition itrans :: ‹('n, 't) witem ⇒ wrel› where
  ‹itrans = (λ(pr, m, σ). wcomp (winv (w_of (snd (snd pr ! (m - 1))))) σ)›

text ‹The walk's terminal triples: both classes ‹WAny›; two cursors on the
  start item that are not disjoint against ‹istart_ind›; a triple no frame
  can hold (one cursor on the start item, the other at a kernel item; two
  kernel items with different symbols before the dot), reported rather than
  carrying a proof that it is dead, which the precise automaton never
  produces.  Two cursors on the start item that are disjoint have no
  successor.›

fun ifires :: ‹'n ⇒ 'n list ⇒ nat × ('n, 't) witem × ('n, 't) witem ⇒ bool› where
  ‹ifires Shn anc (s, (pr1, m1, σ1), (pr2, m2, σ2)) ⟷
     σ1 = WAny ∧ σ2 = WAny ∨
     (if m1 = 0 ∧ fst pr1 = Shn ∧ m2 = 0 ∧ fst pr2 = Shn then ¬ wdisjoint σ1 σ2
      else if m1 = 0 ∧ fst pr1 ≠ Shn ∨ m2 = 0 ∧ fst pr2 ≠ Shn then False
      else m1 = 0 ∨ m2 = 0 ∨ fst (snd pr1 ! (m1 - 1)) ≠ fst (snd pr2 ! (m2 - 1)))›

text ‹The successors of a triple: the left cursor at dot 0 predicted first,
  then the right; two kernel cursors with the same symbol before the dot pop
  together along every entry of the state whose source state holds both
  popped items, unless the entry is rigid and they are disjoint against its
  column.›

fun isuccs :: ‹'n ⇒ ('n, 't) witem list list ⇒ (('n, 't) sym × nat) list list ⇒
    'n list ⇒ nat × ('n, 't) witem × ('n, 't) witem ⇒
    (nat × ('n, 't) witem × ('n, 't) witem) list›
  where
  ‹isuccs Shn wrs gt anc (s, (pr1, m1, σ1), (pr2, m2, σ2)) =
     (if m1 = 0 ∧ fst pr1 = Shn ∧ m2 = 0 ∧ fst pr2 = Shn then []
      else if m1 = 0 ∧ fst pr1 ≠ Shn
      then map (λc. (s, c, (pr2, m2, σ2))) (ipreds wrs s (fst pr1) σ1)
      else if m2 = 0 ∧ fst pr2 ≠ Shn
      then map (λc. (s, (pr1, m1, σ1), c)) (ipreds wrs s (fst pr2) σ2)
      else if m1 = 0 ∨ m2 = 0 then []
      else (let X = fst (snd pr1 ! (m1 - 1)) in
        if X ≠ fst (snd pr2 ! (m2 - 1)) ∨
           irigid anc X ∧ wdisjoint (itrans (pr1, m1, σ1)) (itrans (pr2, m2, σ2))
        then []
        else List.map_filter (λ(p, X'). if X' = X ∧
               ihas (wrs ! p) pr1 (m1 - 1) ∧ ihas (wrs ! p) pr2 (m2 - 1)
               then Some (p, (pr1, m1 - 1, σ1), (pr2, m2 - 1, σ2)) else None)
             (pin_edges gt s)))›

text ‹The walk: a worklist with a seen set, each triple popped at most once.›

primrec ifire :: ‹'n ⇒ ('n, 't) witem list list ⇒ (('n, 't) sym × nat) list list ⇒
    'n list ⇒ nat ⇒ (nat × ('n, 't) witem × ('n, 't) witem) list ⇒
    (nat × ('n, 't) witem × ('n, 't) witem) list ⇒ bool› where
  ‹ifire Shn wrs gt anc 0 seen work = True›
| ‹ifire Shn wrs gt anc (Suc n) seen work =
     (case work of
        [] ⇒ False
      | t # wk ⇒
          if ifires Shn anc t then True
          else ifire Shn wrs gt anc n (t # seen)
            (filter (λt'. t' ∉ set (t # seen) ∧ t' ∉ set wk)
               (remdups (isuccs Shn wrs gt anc t)) @ wk))›

lemma ifire_Nil [simp]: ‹ifire Shn wrs gt anc (Suc n) seen [] = False›
  by simp

lemma ifire_Cons [simp]:
  ‹ifire Shn wrs gt anc (Suc n) seen (t # wk) =
     (if ifires Shn anc t then True
      else ifire Shn wrs gt anc n (t # seen)
        (filter (λt'. t' ∉ set (t # seen) ∧ t' ∉ set wk)
           (remdups (isuccs Shn wrs gt anc t)) @ wk))›
  by simp

text ‹Fuel for the triples the walk can visit: both cursors of a triple at
  state ‹s› are items of ‹s›'s closure (the seeds and the predictions are
  drawn from it, a pop is kept only if its target holds both items), each in
  one of six classes, and the worklist pops a triple at most once.  Naturals
  are unary in the generated code, so the bound is the sum over the states of
  the squared item counts, not a square of the grammar's size.›

definition ifuel :: ‹('n, 't) witem list list ⇒ nat› where
  ‹ifuel wrs = Suc (36 * sum_list (map (λws.
     let n = length (remdups (map (λ(pr, m, _). (pr, m)) ws)) in n * n) wrs))›

text ‹Reduce seeds at a state: one per cell of a production completed in the
  precise closure, the cursor's class the cell's own relation; the lookahead
  stays with it.  A completed production the precise context excludes seeds
  nothing; the runtime's anchor filtering excludes it dynamically.›

definition ireds_at :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list ⇒ nat ⇒ ('t option × ('n, 't) witem) list› where
  ‹ireds_at G Shn sp L i =
     (let ws = wreach G (sp ! i)
      in List.map_filter (λ(i', (pr, m), t, τ).
           if i' = i ∧ m = length (snd pr) ∧ fst pr ≠ Shn ∧
              list_ex (λ(pr', m', ρ). pr' = pr ∧ m' = m) ws
           then Some (t, (pr, m, τ)) else None) L)›

text ‹Shift seeds: the items with a terminal at the dot, the class that
  terminal's relation.›

definition ishifts :: ‹('n, 't) witem list ⇒ ('t × ('n, 't) witem) list› where
  ‹ishifts ws = remdups (List.map_filter (λ(pr, m, ρ).
      if m < length (snd pr)
      then (case fst (snd pr ! m) of
             Tm a ⇒ Some (a, (pr, m, w_of (snd (snd pr ! m)))) | Nt _ ⇒ None)
      else None) ws)›

definition rr_none_at :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list ⇒ nat ⇒ bool› where
  ‹rr_none_at G Shn sp L i =
     (let reds = ireds_at G Shn sp L i
      in list_ex (λ(t, c). t = None ∧
           list_ex (λ(t', c'). fst c' ≠ fst c ∧ t' = None) reds) reds)›

definition ipairs_at :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list ⇒ nat ⇒ (('n, 't) witem × ('n, 't) witem) list› where
  ‹ipairs_at G Shn sp L i =
     (let reds = ireds_at G Shn sp L i;
          shifts = ishifts (wreach G (sp ! i));
          srs = concat (map (λ(t, c). case t of
              Some a ⇒ map (λ(a', c'). (c, c')) (filter (λ(a', c'). a' = a) shifts)
            | None ⇒ []) reds);
          rrs = concat (map (λ(t, c). List.map_filter (λ(t', c').
                 if fst c' ≠ fst c ∧ t' = t ∧ t ≠ None then Some (c, c') else None) reds)
                 reds)
      in remdups (srs @ rrs))›

definition rlalr_conflict_at :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list ⇒ nat ⇒ bool› where
  ‹rlalr_conflict_at G Shn sp L i ⟷
     rr_none_at G Shn sp L i ∨
     list_ex (λ(c1, c2). ifire Shn (map (wreach G) sp) (pgtab G sp) (anchored_nts G)
         (ifuel (map (wreach G) sp)) [] [(i, c1, c2)])
       (ipairs_at G Shn sp L i)›

definition rlalr_conflicts :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat list› where
  ‹rlalr_conflicts G Shn = (let sp = pr0_states G Shn; L = la_fix G Shn in
     filter (rlalr_conflict_at G Shn sp L) [0..<length sp])›

section ‹From a determinism violation to concrete witnesses›

text ‹Eliminations for the sufficiency proof: the negation of
  const‹mdet› yields concrete witnesses, the cell that licensed each
  reduce candidate and the closure item and anchor that keep each successor
  alive.›

lemma liveE:
  assumes ‹live xs›
  obtains pr m R j where ‹(pr, m, R) ∈ set xs› and ‹j ∈ irep_set R›
  using assms that unfolding live_def
  by (fastforce simp: list_ex_iff)

lemma dliveE:
  assumes ‹dlive (Xs, w)›
  obtains pr m R j where ‹Xs ≠ []› and ‹(pr, m, R) ∈ set (hd Xs)›
    and ‹j ∈ irep_set R›
  using assms that unfolding dlive_def by (auto elim: liveE)

lemma dlicE:
  assumes ‹dlic i cells ((a, c) # w') pr RS›
  obtains τ where ‹(i, (pr, length (snd pr)), Some a, τ) ∈ set cells›
    and ‹irep_ex_wsat τ c RS›
  using assms that unfolding dlic_def by (fastforce simp: list_ex_iff)

lemma dlic_NilE:
  assumes ‹dlic i cells [] pr RS›
  obtains τ where ‹(i, (pr, length (snd pr)), None, τ) ∈ set cells›
  using assms that unfolding dlic_def by (fastforce simp: list_ex_iff)

text ‹A live shift successor yields a closure item with the shifted terminal
  at its dot and an anchor compatible with the token's column.›

lemma shift_live_srcE:
  assumes step: ‹mstep_cached G cstk (Xs, w) DShift = Some gc'›
    and live: ‹dlive gc'›
  obtains a c w' pr m R j where
    ‹w = (a, c) # w'›
    and ‹(pr, m, R) ∈ set (hd cstk)›
    and ‹m < length (snd pr)›
    and ‹fst (snd pr ! m) = Tm a›
    and ‹j ∈ irep_set R›
    and ‹irel_sat (snd (snd pr ! m)) c j›
proof -
  from step obtain a c w' where
    w: ‹w = (a, c) # w'› and Xs_ne: ‹Xs ≠ []›
    and gc': ‹gc' = (lgoto (hd cstk) (Tm a) (FinRep [c]) # Xs, w')›
    by (rule mstep_shift_shape)
  from live obtain pr m' R' j where
    itm: ‹(pr, m', R') ∈ set (lgoto (hd cstk) (Tm a) (FinRep [c]))›
    and jR': ‹j ∈ irep_set R'›
    unfolding gc' by (auto elim: dliveE)
  obtain m where m': ‹m' = Suc m› using lgoto_dot_pos[OF itm] by (cases m') auto
  from lgoto_kernel_step[OF itm[unfolded m']] obtain R where
    src: ‹(pr, m, R) ∈ set (hd cstk)› and m_lt: ‹m < length (snd pr)›
    and sym: ‹fst (snd pr ! m) = Tm a›
    and R': ‹R' = irep_inter R (irep_pre (snd (snd pr ! m)) (FinRep [c]))› .
  have jR: ‹j ∈ irep_set R› and jrel: ‹irel_sat (snd (snd pr ! m)) c j›
    using jR' unfolding R' by auto
  from that[OF w src m_lt sym jR jrel] show thesis .
qed

section ‹Tracking a reachable configuration›

text ‹The dynamic half of the sufficiency argument: every configuration the
  indexed machine reaches is tracked, frame by frame, by the driver's own
  index stack under const‹didx_ok›.  A frame owes its obligations only
  where it has a ‹live› (anchored) item: a dead frame never contributes a
  candidate, and by ‹xclosure_auto_live_creach› over the empty kernel a
  dead kernel has a dead closure.  Where the pushed frame is live the table's
  goto is the canonical successor index, so the index stack also records the
  goto history the descent below walks.›

lemma dnext_st_find:
  assumes tab: ‹tables_ok G Shn sts gt L›
    and ok: ‹didx_ok G sts Xs istk›
    and d_lt: ‹d < length Xs›
    and live: ‹lcore (lgoto (xclosure_auto G (Xs ! d)) X RA) ≠ {}›
  shows ‹dnext gt sts (istk ! d) X = st_find sts (cgoto (creach G (sts ! (istk ! d))) X)›
proof -
  from live obtain pr0 n0 R0' j0 where
    g0: ‹(pr0, n0, R0') ∈ set (lgoto (xclosure_auto G (Xs ! d)) X RA)›
    and j0: ‹j0 ∈ irep_set R0'›
    unfolding lcore_def by auto
  obtain m0 where n0: ‹n0 = Suc m0› using lgoto_dot_pos[OF g0] by (cases n0) auto
  from lgoto_kernel_step[OF g0[unfolded n0]] obtain R0 where
    src0: ‹(pr0, m0, R0) ∈ set (xclosure_auto G (Xs ! d))›
    and m0_lt: ‹m0 < length (snd pr0)› and X0: ‹fst (snd pr0 ! m0) = X›
    and R0': ‹R0' = irep_inter R0 (irep_pre (snd (snd pr0 ! m0)) RA)› .
  have j0R0: ‹j0 ∈ irep_set R0› using j0 unfolding R0' by auto
  have f_live: ‹lcore (Xs ! d) ≠ {}› by (rule closure_live_kernel[OF src0 j0R0])
  from didx_okD[OF ok d_lt f_live] have p_lt: ‹istk ! d < length sts›
    and cover: ‹lcore (Xs ! d) ⊆ set (sts ! (istk ! d))› by auto
  have kern: ‹⋀pr m R. (pr, m, R) ∈ set (Xs ! d) ⟹ irep_nonempty R ⟹
      (pr, m) ∈ set (sts ! (istk ! d))›
    using cover by (fastforce simp: lcore_def)
  have src0_cr: ‹(pr0, m0) ∈ set (creach G (sts ! (istk ! d)))›
    by (rule xclosure_auto_live_creach[OF kern src0 j0R0])
  have lookup0: ‹map_of (gt ! (istk ! d)) (fst (snd pr0 ! m0)) =
      Some (st_find sts (cgoto (creach G (sts ! (istk ! d))) (fst (snd pr0 ! m0))))›
    using tab p_lt src0_cr m0_lt unfolding tables_ok_def by blast
  have lookup: ‹map_of (gt ! (istk ! d)) X =
      Some (st_find sts (cgoto (creach G (sts ! (istk ! d))) X))›
    using lookup0 unfolding X0 .
  have gt_len: ‹length gt = length sts› using tab unfolding tables_ok_def by blast
  show ?thesis
    unfolding dnext_def la_next_def lookup option.case
    using p_lt gt_len by (simp add: min_def st_find_le)
qed

text ‹A cell of the driver's reduce bucket ‹i› is a completed cell of
  const‹la_fix› at index ‹i›.›

lemma red_buckets_memD:
  assumes ‹i < n› and ‹c ∈ set (red_buckets G Shn n ! i)›
  shows ‹c ∈ set (la_fix G Shn) ∧ fst c = i ∧
         (case c of (i', itm, t, τ) ⇒ snd itm = length (snd (fst itm)))›
  using assms unfolding red_buckets_def cell_buckets_def by (auto simp: Let_def)

section ‹Accept/reduce conflicts›

text ‹The case const‹rlalr_conflicts› ignores: the start production
  completed next to an end-of-input reduce cell of another production, the
  driver accepting where the relation of the grammar has a second value.›

definition acc_conflicts :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat list› where
  ‹acc_conflicts G Shn = (let sts = pr0_states G Shn in
     filter (λi. (start_prod G Shn, Suc 0) ∈ set (sts ! i) ∧
        list_ex (λ(i', (pr, m), t, τ). i' = i ∧ m = length (snd pr) ∧
                  t = None ∧ pr ≠ start_prod G Shn) (la_fix G Shn))
       [0..<length sts])›

text ‹Reducing by the start production is dead: nothing in the initial
  closure expects term‹Nt Shn›.›

lemma lgoto_xinit_Shn:
  assumes fn: ‹fresh_name G Shn›
  shows ‹lgoto (xclosure_auto G (xinit G Shn)) (Nt Shn) RA = []›
proof -
  have ‹¬ (m < length (snd pr) ∧ fst (snd pr ! m) = Nt Shn)›
    if item: ‹(pr, m, R) ∈ set (xclosure_auto G (xinit G Shn))› for pr m R
  proof
    assume ‹m < length (snd pr) ∧ fst (snd pr ! m) = Nt Shn›
    then have m: ‹m < length (snd pr)› and X: ‹fst (snd pr ! m) = Nt Shn› by auto
    from dshape_prods[OF dshape_init, of 0 pr m R] item
    have ‹pr ∈ set (iprods G) ∨ pr = start_prod G Shn› by simp
    then show False
    proof
      assume prG: ‹pr ∈ set (iprods G)›
      have ‹snd pr ! m ∈ set (snd pr)› using m by simp
      with fn prG X show False
        unfolding fresh_name_def by (cases pr; cases ‹snd pr ! m›) fastforce
    next
      assume ‹pr = start_prod G Shn›
      with m X fn show False unfolding start_prod_def fresh_name_def by simp
    qed
  qed
  then show ?thesis unfolding lgoto_def by (auto simp: filter_empty_conv)
qed

lemma final_shape:
  assumes fn: ‹fresh_name G Shn›
    and inv: ‹dinv G Shn w ((Xs, u), cstk, istk, v, tstk)›
    and fin: ‹gfinal G Shn (Xs, u)›
  shows ‹∃X. Xs = [X, xinit G Shn]›
proof -
  have fin': ‹gfinal G Shn (fst ((Xs, u), cstk, istk, v, tstk))› using fin by simp
  from dinv_final[OF fn inv fin'] obtain t where tstk: ‹tstk = [t]› by auto
  from inv obtain RAs where lenR: ‹length RAs = length tstk›
    and sh: ‹dshape G Shn Xs (zip (map asym tstk) RAs)›
    unfolding dinv_def by auto
  have ‹length Xs = 2› ‹Xs ! 1 = xinit G Shn›
    using sh lenR tstk unfolding dshape_def by auto
  then show ?thesis
    by (cases Xs) (auto simp: length_Suc_conv)
qed

text ‹With an empty accept/reduce report, no live reduce is offered at an
  accepting configuration.›

lemma no_reduce_at_final:
  assumes fn: ‹fresh_name G Shn› and chk: ‹acc_conflicts G Shn = []›
    and inv: ‹dinv G Shn w ((Xs, u), cstk, istk, v, tstk)›
    and ok: ‹didx_ok G (pr0_states G Shn) Xs istk›
    and fin: ‹gfinal G Shn (Xs, u)›
    and cand: ‹DReduce pr ∈ set (dcands G (hd istk)
                 (red_buckets G Shn (length (pr0_states G Shn)) ! hd istk)
                 (xclosure_auto G (hd Xs)) (Xs, u))›
    and step: ‹mstep G (Xs, u) (DReduce pr) = Some gc'› and live: ‹dlive gc'›
  shows False
proof -
  let ?sts = ‹pr0_states G Shn› and ?i = ‹hd istk›
  from final_shape[OF fn inv fin] obtain X where Xs: ‹Xs = [X, xinit G Shn]› by blast
  have u: ‹u = []› using fin unfolding gfinal_def by simp
  have istk_ne: ‹istk ≠ []› using didx_ok_len[OF ok] Xs by auto
  from fin obtain pr0 R where item: ‹(pr0, Suc 0, R) ∈ set X› and Shn: ‹fst pr0 = Shn›
    and mem: ‹irep_mem (istart_ind G) R›
    unfolding gfinal_def Xs by (auto simp: list_ex_iff)
  have lv: ‹(pr0, Suc 0) ∈ lcore X› using lcoreI[OF item, of ‹istart_ind G›] mem by simp
  have i_lt: ‹?i < length ?sts› and cover: ‹lcore X ⊆ set (?sts ! ?i)›
    using didx_okD[OF ok, of 0] lv Xs istk_ne by (auto simp: hd_conv_nth)
  from inv obtain RAs where sh: ‹dshape G Shn Xs (zip (map asym tstk) RAs)›
    unfolding dinv_def by auto
  have item': ‹(pr0, Suc 0, R) ∈ set (xclosure_auto G (Xs ! 0))›
    using item xclosure_auto_kernel_sub Xs by fastforce
  have pr0: ‹pr0 = start_prod G Shn›
    using dshape_prods[OF sh _ item'] Shn fn unfolding fresh_name_def by force
  have acc: ‹(start_prod G Shn, Suc 0) ∈ set (?sts ! ?i)›
    using lv pr0 cover by blast
  from dcands_reduceD[OF cand]
  have ‹dlic ?i (red_buckets G Shn (length ?sts) ! ?i) u pr (red_set (xclosure_auto G (hd Xs)) pr)›
    by simp
  then obtain τ where
      cell: ‹(?i, (pr, length (snd pr)), None, τ) ∈ set (red_buckets G Shn (length ?sts) ! ?i)›
    unfolding dlic_def u by (auto simp: list_ex_iff)
  then have cellL: ‹(?i, (pr, length (snd pr)), None, τ) ∈ set (la_fix G Shn)›
    by (rule red_buckets_memD[OF i_lt, THEN conjunct1])
  have ne: ‹pr ≠ start_prod G Shn›
  proof
    assume pr: ‹pr = start_prod G Shn›
    have ‹gc' = (lgoto (xclosure_auto G (xinit G Shn)) (Nt Shn)
                   (red_set (xclosure_auto G X) pr) # [xinit G Shn], u)›
      using step unfolding mstep_def mstep_cached_def Xs pr start_prod_def
      by (auto simp: Let_def split: if_splits)
    then have ‹gc' = ([] # [xinit G Shn], u)› by (simp add: lgoto_xinit_Shn[OF fn])
    with live show False unfolding dlive_def live_def by simp
  qed
  have ‹?i ∈ set (acc_conflicts G Shn)›
    unfolding acc_conflicts_def Let_def using i_lt acc cellL ne
    by (auto simp: list_ex_iff intro!: bexI[where x = ‹(?i, (pr, length (snd pr)), None, τ)›])
  with chk show False by simp
qed

section ‹Soundness of the item-relative walk: the worklist›

text ‹A ‹False› result of const‹ifire› can only arise from an exhausted
  worklist (fuel exhaustion returns ‹True›), so it certifies that no triple
  the successor relation const‹isuccs› reaches from the seed fires.  The
  worklist invariant: no seen triple fires, and every successor of a seen
  triple is seen or still to do.›

lemma map_filterI:
  ‹x ∈ set xs ⟹ f x = Some y ⟹ y ∈ set (List.map_filter f xs)›
  unfolding List.map_filter_def by force

lemma concat_map_memI:
  ‹x ∈ set xs ⟹ y ∈ set (g x) ⟹ y ∈ set (concat (map g xs))›
  by auto

text ‹The worklist's closure: when the walk returns ‹False›, the triples
  it saw form a set closed under const‹isuccs› none of which fires.›

lemma ifire_False_closed:
  assumes res: ‹ifire Shn wrs gt anc n seen work = False›
    and inv: ‹∀t ∈ set seen. ¬ ifires Shn anc t ∧
        set (isuccs Shn wrs gt anc t) ⊆ set seen ∪ set work›
  shows ‹∃S. set seen ∪ set work ⊆ S ∧
    (∀t ∈ S. ¬ ifires Shn anc t ∧ set (isuccs Shn wrs gt anc t) ⊆ S)›
  using res inv
proof (induction n arbitrary: seen work)
  case 0
  then show ?case by simp
next
  case (Suc n)
  show ?case
  proof (cases work)
    case Nil
    with Suc.prems show ?thesis by (intro exI[of _ ‹set seen›]) auto
  next
    case (Cons t wk)
    have nf: ‹¬ ifires Shn anc t› using Suc.prems Cons by (auto split: if_splits)
    have rec: ‹ifire Shn wrs gt anc n (t # seen)
      (filter (λt'. t' ∉ set (t # seen) ∧ t' ∉ set wk)
         (remdups (isuccs Shn wrs gt anc t)) @ wk) = False›
      using Suc.prems Cons nf by simp
    have inv': ‹∀u ∈ set (t # seen). ¬ ifires Shn anc u ∧
        set (isuccs Shn wrs gt anc u) ⊆ set (t # seen) ∪
          set (filter (λt'. t' ∉ set (t # seen) ∧ t' ∉ set wk)
            (remdups (isuccs Shn wrs gt anc t)) @ wk)›
      using Suc.prems Cons nf by auto
    from Suc.IH[OF rec inv'] Cons show ?thesis by auto
  qed
qed

lemma ifire_False_sound:
  assumes res: ‹ifire Shn wrs gt anc n seen work = False›
    and inv: ‹∀t ∈ set seen. ¬ ifires Shn anc t ∧
        set (isuccs Shn wrs gt anc t) ⊆ set seen ∪ set work›
    and t0: ‹t0 ∈ set seen ∪ set work›
    and desc: ‹(λt t'. t' ∈ set (isuccs Shn wrs gt anc t))** t0 t'›
  shows ‹¬ ifires Shn anc t'›
proof -
  obtain S where sub: ‹set seen ∪ set work ⊆ S›
    and cl: ‹∀t ∈ S. ¬ ifires Shn anc t ∧ set (isuccs Shn wrs gt anc t) ⊆ S›
    using ifire_False_closed[OF res inv] by blast
  have ‹t' ∈ S›
    using desc t0 sub cl by (induction rule: rtranclp_induct) auto
  with cl show ?thesis by blast
qed

theorem ifire_sound:
  assumes res: ‹ifire Shn wrs gt anc n [] [t0] = False›
    and desc: ‹(λt t'. t' ∈ set (isuccs Shn wrs gt anc t))** t0 t'›
  shows ‹¬ ifires Shn anc t'›
  using ifire_False_sound[OF res _ _ desc] by auto


section ‹Stack shape along reachability, and anchor persistence›

lemma dshapeD:
  assumes ‹dshape G Shn Xs α›
  shows ‹length Xs = length α + 1› and ‹Xs ! length α = xinit G Shn›
    and ‹⋀k. k < length α ⟹
      Xs ! k = lgoto (xclosure_auto G (Xs ! Suc k)) (fst (α ! k)) (snd (α ! k))›
  using assms unfolding dshape_def by auto

text ‹Every reachable stack is const‹dshape›-shaped (part of the
  tracking invariant of text‹imreach_strack› below): each frame is the
  const‹lgoto› of the closure of the frame below, along a recorded goto
  history.  Anchors of a kernel item persist from its prediction: descending
  the dots, the item's anchor set only shrinks from the dot-0 slot in the
  closure of the frame where it was predicted.›

lemma wkernel_memI:
  ‹(pr, m) ∈ set s ⟹
   (pr, m, if m = 0 then WAny else w_of (snd (snd pr ! (m - 1)))) ∈ set (wkernel s)›
  unfolding wkernel_def by force

lemma xclosure_auto_kernelD:
  assumes ‹(pr, m, R) ∈ set (xclosure_auto G s)› and ‹1 ≤ m›
  shows ‹(pr, m, R) ∈ set s›
proof -
  have ‹(pr, m, R) ∈ set (xslots G s (xiter G s (xfuel G s)))›
    using assms(1) unfolding xclosure_auto_def xclosure_def .
  then show ?thesis
  proof (rule xslots_memE)
    assume ‹(pr, m, R) ∈ set s› then show ?thesis .
  next
    fix q assume ‹q < length (iprods G)›
      and ‹q < length (xiter G s (xfuel G s))›
      and ‹(pr, m, R) = (iprods G ! q, 0, xiter G s (xfuel G s) ! q)›
    then show ?thesis using assms(2) by auto
  qed
qed

text ‹A kernel item at dot ‹m ≥ 1› in frame ‹k› descends to the dot-0 slot of
  the closure of frame ‹k + m›, its anchor set only shrinking.›

lemma dshape_persist:
  assumes sh: ‹dshape G Shn Xs α›
  shows ‹(pr, m, R) ∈ set (Xs ! k) ⟹ k < length Xs ⟹ 1 ≤ m ⟹
     ∃R0. k + m < length Xs ∧ (pr, 0, R0) ∈ set (xclosure_auto G (Xs ! (k + m))) ∧
           irep_set R ⊆ irep_set R0›
proof (induction m arbitrary: k R)
  case 0
  then show ?case by simp
next
  case (Suc m)
  note lenX = dshapeD(1)[OF sh] and bot = dshapeD(2)[OF sh] and shp = dshapeD(3)[OF sh]
  have k_lt_a: ‹k < length α›
  proof (rule ccontr)
    assume ‹¬ k < length α›
    then have ‹k = length α› using Suc.prems(2) lenX by simp
    then have ‹(pr, Suc m, R) ∈ set (xinit G Shn)› using Suc.prems(1) bot by simp
    then show False unfolding xinit_def by auto
  qed
  have frame: ‹Xs ! k = lgoto (xclosure_auto G (Xs ! Suc k)) (fst (α ! k)) (snd (α ! k))›
    by (rule shp[OF k_lt_a])
  from lgoto_kernel_step[OF Suc.prems(1)[unfolded frame]] obtain R' where
    src: ‹(pr, m, R') ∈ set (xclosure_auto G (Xs ! Suc k))›
    and Req: ‹R = irep_inter R' (irep_pre (snd (snd pr ! m)) (snd (α ! k)))› .
  have sub: ‹irep_set R ⊆ irep_set R'› unfolding Req by auto
  show ?case
  proof (cases m)
    case 0
    have ‹Suc k < length Xs› using k_lt_a lenX by simp
    then show ?thesis using src sub 0 by auto
  next
    case (Suc m')
    have m_pos: ‹1 ≤ m› using Suc by simp
    have src': ‹(pr, m, R') ∈ set (xslots G (Xs ! Suc k)
        (xiter G (Xs ! Suc k) (xfuel G (Xs ! Suc k))))›
      using src unfolding xclosure_auto_def xclosure_def .
    have kern: ‹(pr, m, R') ∈ set (Xs ! Suc k)›
      using src'
    proof (rule xslots_memE)
      assume ‹(pr, m, R') ∈ set (Xs ! Suc k)›
      then show ?thesis .
    next
      fix q assume ‹q < length (iprods G)›
        and ‹q < length (xiter G (Xs ! Suc k) (xfuel G (Xs ! Suc k)))›
        and ‹(pr, m, R') = (iprods G ! q, 0, xiter G (Xs ! Suc k) (xfuel G (Xs ! Suc k)) ! q)›
      then show ?thesis using Suc by auto
    qed
    have Sk_lt: ‹Suc k < length Xs› using k_lt_a lenX by simp
    from Suc.IH[OF kern Sk_lt m_pos] obtain R0 where
      ‹Suc k + m < length Xs›
      and s0: ‹(pr, 0, R0) ∈ set (xclosure_auto G (Xs ! (Suc k + m)))›
      and sub2: ‹irep_set R' ⊆ irep_set R0› by blast
    then show ?thesis using sub by fastforce
  qed
qed

section ‹The pooled width invariant›

text ‹The per-item form of the width invariant: each anchored closure item
  relates to ‹some› element of the frame's entry pool ‹P› by a ‹wreach›
  class; different items may pick different pool elements, as the pooled
  machine's frames demand.  This is the observation of
  cite‹‹Sect.~5.8› in "adams2013"› that the items of one item set can carry different
  indentation sets, so one set shared by all of them is not enough.
  First the closure preservation, by
  text‹xiter_slot_induct›: every step reuses its source's pool element.›

lemma xiter_pool:
  assumes kern: ‹⋀pr m R j. (pr, m, R) ∈ set xs ⟹ j ∈ irep_set R ⟹
      ∃ρ l. (pr, m, ρ) ∈ set (wreach G s) ∧ l ∈ P ∧ wsat ρ l j›
  shows ‹p < length (iprods G) ⟹ j ∈ irep_set (xiter G xs t ! p) ⟹
     ∃ρ l. (iprods G ! p, 0, ρ) ∈ set (wreach G s) ∧ l ∈ P ∧ wsat ρ l j›
proof (rule xiter_slot_induct[where Q = ‹λpr m j. ∃ρ l. (pr, m, ρ) ∈ set (wreach G s) ∧ l ∈ P ∧ wsat ρ l j›,
    OF kern])
  fix pr m i j p
  assume ‹∃ρ l. (pr, m, ρ) ∈ set (wreach G s) ∧ l ∈ P ∧ wsat ρ l i› and m: ‹m < length (snd pr)›
    ‹fst (snd pr ! m) = Nt (fst (iprods G ! p))› ‹p < length (iprods G)›
    and rel: ‹irel_sat (snd (snd pr ! m)) j i›
  then obtain ρ l where ‹(pr, m, ρ) ∈ set (wreach G s)› ‹l ∈ P› ‹wsat ρ l i› by blast
  with wreach_emit[OF _ m(1,2)] m(3) wsat_reanchor[OF _ ‹wsat ρ l i›] rel
  show ‹∃ρ l. (iprods G ! p, 0, ρ) ∈ set (wreach G s) ∧ l ∈ P ∧ wsat ρ l j› by fastforce
qed

text ‹The kernel hypothesis, per frame kind: an ‹lgoto›-built frame pools the
  goto label's anchors, the bottom frame is pinned at ‹istart_ind›.›

lemma wanch_pool_lgoto:
  assumes cover: ‹⋀pr m R j. (pr, m, R) ∈ set (lgoto CL X RA) ⟹ j ∈ irep_set R ⟹
      (pr, m) ∈ set s›
    and mem: ‹(pr, m, R) ∈ set (lgoto CL X RA)› and jR: ‹j ∈ irep_set R›
  shows ‹∃ρ l. (pr, m, ρ) ∈ set (wreach G s) ∧ l ∈ irep_set RA ∧ wsat ρ l j›
proof -
  obtain m0 where m: ‹m = Suc m0› using lgoto_dot_pos[OF mem] by (cases m) auto
  from lgoto_kernel_step[OF mem[unfolded m]] obtain Rs where
    m0_lt: ‹m0 < length (snd pr)›
    and Req: ‹R = irep_inter Rs (irep_pre (snd (snd pr ! m0)) RA)› .
  from jR obtain l where lRA: ‹l ∈ irep_set RA›
    and rel: ‹irel_sat (snd (snd pr ! m0)) l j›
    unfolding Req by auto
  have kmem: ‹(pr, m) ∈ set s› by (rule cover[OF mem jR])
  have ‹(pr, m, w_of (snd (snd pr ! (m - 1)))) ∈ set (wkernel s)›
    using wkernel_memI[OF kmem] unfolding m by simp
  then have wmem: ‹(pr, m, w_of (snd (snd pr ! m0))) ∈ set (wreach G s)›
    using wreach_kernel unfolding m by auto
  have ‹wsat (w_of (snd (snd pr ! m0))) l j› by (rule w_of_sound[OF rel])
  then show ?thesis using wmem lRA by blast
qed

lemma wanch_pool_xinit:
  assumes mem: ‹(pr, m, R) ∈ set (xinit G Shn)› and jR: ‹j ∈ irep_set R›
    and cover: ‹(pr, m) ∈ set s›
  shows ‹∃ρ. (pr, m, ρ) ∈ set (wreach G s) ∧ wsat ρ (istart_ind G) j›
proof -
  have m0: ‹m = 0› using mem unfolding xinit_def by auto
  have ‹(pr, m, WAny) ∈ set (wkernel s)›
    using wkernel_memI[OF cover] unfolding m0 by simp
  then have ‹(pr, m, WAny) ∈ set (wreach G s)› using wreach_kernel by auto
  then show ?thesis by auto
qed

section ‹The anchored-nonterminal fixpoint›

text ‹const‹anchored_nts› iterates a filter; each round either fixes the
  list or strictly shortens it, so ‹length nts› rounds reach the greatest
  fixpoint.  The destructor: an anchored nonterminal's productions all start
  with an ‹Eq›-related terminal or anchored nonterminal.›

lemma funpow_filter_fix:
  fixes stp :: ‹'a list ⇒ 'a list›
  assumes step: ‹⋀S. stp S = S ∨ length (stp S) < length S›
  shows ‹stp ((stp ^^ n) S0) = (stp ^^ n) S0 ∨ length ((stp ^^ n) S0) ≤ length S0 - n›
proof (induction n)
  case 0
  then show ?case using step by auto
next
  case (Suc n)
  show ?case
  proof (cases ‹stp ((stp ^^ n) S0) = (stp ^^ n) S0›)
    case True
    then have ‹(stp ^^ Suc n) S0 = (stp ^^ n) S0› by simp
    then show ?thesis using True by simp
  next
    case False
    with Suc.IH have len_n: ‹length ((stp ^^ n) S0) ≤ length S0 - n› by blast
    from step[of ‹(stp ^^ n) S0›] False
    have ‹length (stp ((stp ^^ n) S0)) < length ((stp ^^ n) S0)› by blast
    then have ‹length ((stp ^^ Suc n) S0) ≤ length S0 - Suc n›
      using len_n by simp
    then show ?thesis by blast
  qed
qed

lemma funpow_filter_stable:
  fixes stp :: ‹'a list ⇒ 'a list›
  assumes step: ‹⋀S. stp S = S ∨ length (stp S) < length S›
    and nil: ‹stp [] = []›
  shows ‹stp ((stp ^^ length S0) S0) = (stp ^^ length S0) S0›
proof -
  from funpow_filter_fix[OF step, of ‹length S0› S0]
  consider ‹stp ((stp ^^ length S0) S0) = (stp ^^ length S0) S0›
    | ‹length ((stp ^^ length S0) S0) = 0› by fastforce
  then show ?thesis
  proof cases
    case 1
    then show ?thesis .
  next
    case 2
    then have ‹(stp ^^ length S0) S0 = []› by simp
    then show ?thesis using nil by simp
  qed
qed

lemma anchored_ntsD:
  fixes G :: ‹('n, 't) is_cfg›
  assumes A: ‹A ∈ set (anchored_nts G)› and pr: ‹(A, rhs) ∈ set (iprods G)›
  shows ‹rhs ≠ [] ∧ snd (hd rhs) = Eq ∧
         (case fst (hd rhs) of Tm _ ⇒ True | Nt B ⇒ B ∈ set (anchored_nts G))›
proof -
  define ok where ‹ok = (λS (B :: 'n, rhs :: ('n, 't) rhs). rhs ≠ [] ∧ snd (hd rhs) = Eq ∧
      (case fst (hd rhs) of Tm _ ⇒ True | Nt B' ⇒ B' ∈ set S))›
  define stp where ‹stp = (λS. filter (λA. list_all (λp. fst p ≠ A ∨ ok S p) (iprods G)) S)›
  have step: ‹stp S = S ∨ length (stp S) < length S› for S
  proof (cases ‹∀A ∈ set S. list_all (λp. fst p ≠ A ∨ ok S p) (iprods G)›)
    case True
    then have ‹stp S = S› unfolding stp_def by (simp add: filter_id_conv)
    then show ?thesis ..
  next
    case False
    then obtain A' where ‹A' ∈ set S›
      and ‹¬ list_all (λp. fst p ≠ A' ∨ ok S p) (iprods G)› by blast
    then have ‹length (stp S) < length S›
      unfolding stp_def by (intro length_filter_less) auto
    then show ?thesis ..
  qed
  have nil: ‹stp [] = []› unfolding stp_def by simp
  have unf: ‹anchored_nts G = (stp ^^ length (remdups (map fst (iprods G))))
      (remdups (map fst (iprods G)))›
    unfolding anchored_nts_def stp_def ok_def Let_def by simp
  have stable: ‹stp (anchored_nts G) = anchored_nts G›
    unfolding unf by (rule funpow_filter_stable[OF step nil])
  have ‹A ∈ set (stp (anchored_nts G))› using A stable by simp
  then have ‹list_all (λp. fst p ≠ A ∨ ok (anchored_nts G) p) (iprods G)›
    unfolding stp_def by simp
  then have ‹ok (anchored_nts G) (A, rhs)›
    using pr by (fastforce simp: list_all_iff)
  then show ?thesis unfolding ok_def by simp
qed

section ‹Anchored pools are singletons›

lemma anchored_nts_sub: ‹set (anchored_nts G) ⊆ fst ` set (iprods G)›
proof -
  have gen: ‹set ((stp ^^ k) S0) ⊆ set S0›
    if sub: ‹⋀S. set (stp S) ⊆ set S› for stp :: ‹'x list ⇒ 'x list› and k S0
  proof (induction k)
    case 0 then show ?case by simp
  next
    case (Suc k)
    have ‹set ((stp ^^ Suc k) S0) ⊆ set ((stp ^^ k) S0)› using sub by simp
    then show ?case using Suc.IH by blast
  qed
  show ?thesis
    unfolding anchored_nts_def Let_def
    by (rule subset_trans[OF gen]) auto
qed

lemma dshape_persist1:
  assumes sh: ‹dshape G Shn Xs α›
  shows ‹(pr, m, R) ∈ set (Xs ! k) ⟹ k < length Xs ⟹ 1 ≤ m ⟹
     ∃R1. k + m - 1 < length α ∧ (pr, 1, R1) ∈ set (Xs ! (k + m - 1)) ∧
           irep_set R ⊆ irep_set R1›
proof (induction m arbitrary: k R)
  case 0
  then show ?case by simp
next
  case (Suc m)
  note lenX = dshapeD(1)[OF sh] and bot = dshapeD(2)[OF sh] and shp = dshapeD(3)[OF sh]
  have k_lt_a: ‹k < length α›
  proof (rule ccontr)
    assume ‹¬ k < length α›
    then have ‹k = length α› using Suc.prems(2) lenX by simp
    then have ‹(pr, Suc m, R) ∈ set (xinit G Shn)› using Suc.prems(1) bot by simp
    then show False unfolding xinit_def by auto
  qed
  show ?case
  proof (cases m)
    case 0
    then show ?thesis using Suc.prems(1) k_lt_a by auto
  next
    case (Suc m')
    have frame: ‹Xs ! k = lgoto (xclosure_auto G (Xs ! Suc k)) (fst (α ! k)) (snd (α ! k))›
      by (rule shp[OF k_lt_a])
    from lgoto_kernel_step[OF Suc.prems(1)[unfolded frame]] obtain R' where
      src: ‹(pr, m, R') ∈ set (xclosure_auto G (Xs ! Suc k))›
      and Req: ‹R = irep_inter R' (irep_pre (snd (snd pr ! m)) (snd (α ! k)))› .
    have sub: ‹irep_set R ⊆ irep_set R'› unfolding Req by auto
    have src'': ‹(pr, m, R') ∈ set (xslots G (Xs ! Suc k)
        (xiter G (Xs ! Suc k) (xfuel G (Xs ! Suc k))))›
      using src unfolding xclosure_auto_def xclosure_def .
    have kern: ‹(pr, m, R') ∈ set (Xs ! Suc k)›
      using src''
    proof (rule xslots_memE)
      assume ‹(pr, m, R') ∈ set (Xs ! Suc k)›
      then show ?thesis .
    next
      fix q assume ‹q < length (iprods G)›
        and ‹q < length (xiter G (Xs ! Suc k) (xfuel G (Xs ! Suc k)))›
        and ‹(pr, m, R') = (iprods G ! q, 0, xiter G (Xs ! Suc k) (xfuel G (Xs ! Suc k)) ! q)›
      then show ?thesis using Suc by auto
    qed
    have Sk_lt: ‹Suc k < length Xs› using k_lt_a lenX by simp
    have m_pos: ‹1 ≤ m› using Suc by simp
    from Suc.IH[OF kern Sk_lt m_pos] obtain R1 where
      lt1: ‹Suc k + m - 1 < length α›
      and s1: ‹(pr, 1, R1) ∈ set (Xs ! (Suc k + m - 1))›
      and sub1: ‹irep_set R' ⊆ irep_set R1› by blast
    have idx: ‹Suc k + m - 1 = k + Suc m - 1› using m_pos by simp
    show ?thesis using lt1 s1 sub sub1 unfolding idx by blast
  qed
qed

lemma irep_pre_Eq: ‹irep_set (irep_pre Eq L) = irep_set L›
  by auto

text ‹The label of a reduce over an anchored nonterminal is bounded by a
  single column: every completed instance descends to its dot-1 form, whose
  ‹Eq› first-symbol filter bounds it by the pool of the frame where the
  first symbol was crossed: a shift column, or an anchored pool one level
  down.›

lemma red_set_anchored_singleton:
  assumes sh: ‹dshape G Shn Xs α› and ne: ‹Xs ≠ []›
    and tmS: ‹∀k < length α. ∀a. fst (α ! k) = Tm a ⟶ (∃c. snd (α ! k) = FinRep [c])›
    and sng: ‹∀k < length α. ∀B. fst (α ! k) = Nt B ⟶ B ∈ set (anchored_nts G) ⟶
                (∃c. irep_set (snd (α ! k)) ⊆ {c})›
    and fresh: ‹fresh_name G Shn›
    and anch: ‹fst pr ∈ set (anchored_nts G)›
  shows ‹∃c. irep_set (red_set (xclosure_auto G (hd Xs)) pr) ⊆ {c}›
proof (cases ‹∃R. (pr, length (snd pr), R) ∈ set (xclosure_auto G (hd Xs)) ∧
    irep_set R ≠ {}›)
  case False
  have ‹irep_set (red_set (xclosure_auto G (hd Xs)) pr) ⊆ {0}›
    using False by (fastforce simp: red_set_correct)
  then show ?thesis by blast
next
  case True
  then obtain Rw where inst_w: ‹(pr, length (snd pr), Rw) ∈ set (xclosure_auto G (hd Xs))›
    by blast
  note lenX = dshapeD(1)[OF sh]
  have hd0: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
  have prG: ‹pr ∈ set (iprods G)›
  proof -
    have ‹pr ∈ set (iprods G) ∨ pr = start_prod G Shn›
      using dshape_prods[OF sh _ inst_w[unfolded hd0]] by simp
    moreover have ‹pr ≠ start_prod G Shn›
    proof
      assume ‹pr = start_prod G Shn›
      then have ‹fst pr = Shn› unfolding start_prod_def by simp
      then have ‹Shn ∈ set (anchored_nts G)› using anch by simp
      then have ‹Shn ∈ fst ` set (iprods G)›
        by (rule subsetD[OF anchored_nts_sub])
      then show False using fresh unfolding fresh_name_def by auto
    qed
    ultimately show ?thesis by blast
  qed
  obtain A rhs where preq: ‹pr = (A, rhs)› by (cases pr)
  from anchored_ntsD[OF anch[unfolded preq fst_conv] prG[unfolded preq]]
  have rhs_ne: ‹rhs ≠ []› and hdEq: ‹snd (hd rhs) = Eq›
    and hdok: ‹case fst (hd rhs) of Tm _ ⇒ True | Nt B ⇒ B ∈ set (anchored_nts G)›
    by auto
  define d where ‹d = length (snd pr)›
  have d_pos: ‹1 ≤ d› unfolding d_def preq using rhs_ne by (cases rhs) auto
  have one: ‹d - 1 < length α ∧ fst (α ! (d - 1)) = fst (snd pr ! 0) ∧
      irep_set R ⊆ irep_set (irep_pre (snd (snd pr ! 0)) (snd (α ! (d - 1))))›
    if inst: ‹(pr, length (snd pr), R) ∈ set (xclosure_auto G (hd Xs))› for R
  proof -
    have inst': ‹(pr, length (snd pr), R) ∈ set (xslots G (hd Xs)
        (xiter G (hd Xs) (xfuel G (hd Xs))))›
      using inst unfolding xclosure_auto_def xclosure_def .
    have kern: ‹(pr, length (snd pr), R) ∈ set (hd Xs)›
      using inst'
    proof (rule xslots_memE)
      assume ‹(pr, length (snd pr), R) ∈ set (hd Xs)›
      then show ?thesis .
    next
      fix q assume ‹q < length (iprods G)›
        and ‹q < length (xiter G (hd Xs) (xfuel G (hd Xs)))›
        and eq: ‹(pr, length (snd pr), R) =
           (iprods G ! q, 0, xiter G (hd Xs) (xfuel G (hd Xs)) ! q)›
      have ‹length (snd pr) = 0› using eq by auto
      then show ?thesis using d_pos unfolding d_def by simp
    qed
    have k0_lt: ‹(0 :: nat) < length Xs› using ne by (cases Xs) auto
    have dm: ‹1 ≤ length (snd pr)› using d_pos unfolding d_def by simp
    from dshape_persist1[OF sh kern[unfolded hd0] k0_lt dm]
    obtain R1 where lt1: ‹0 + length (snd pr) - 1 < length α›
      and s1: ‹(pr, 1, R1) ∈ set (Xs ! (0 + length (snd pr) - 1))›
      and sub1: ‹irep_set R ⊆ irep_set R1› by blast
    have idx: ‹0 + length (snd pr) - 1 = d - 1› unfolding d_def by simp
    have lt': ‹d - 1 < length α› using lt1 unfolding idx .
    have frame: ‹Xs ! (d - 1) =
        lgoto (xclosure_auto G (Xs ! Suc (d - 1))) (fst (α ! (d - 1))) (snd (α ! (d - 1)))›
      using sh lt' unfolding dshape_def by auto
    have s1': ‹(pr, Suc 0, R1) ∈ set (lgoto (xclosure_auto G (Xs ! Suc (d - 1)))
        (fst (α ! (d - 1))) (snd (α ! (d - 1))))›
      using s1 unfolding idx frame by simp
    from lgoto_kernel_step[OF s1'] obtain R0 where
      src0: ‹(pr, 0, R0) ∈ set (xclosure_auto G (Xs ! Suc (d - 1)))›
      and m0: ‹0 < length (snd pr)›
      and X0: ‹fst (snd pr ! 0) = fst (α ! (d - 1))›
      and R1eq: ‹R1 = irep_inter R0 (irep_pre (snd (snd pr ! 0)) (snd (α ! (d - 1))))› .
    have sub2: ‹irep_set R1 ⊆ irep_set (irep_pre (snd (snd pr ! 0)) (snd (α ! (d - 1))))›
      unfolding R1eq by auto
    have ‹irep_set R ⊆ irep_set (irep_pre (snd (snd pr ! 0)) (snd (α ! (d - 1))))›
      using sub1 sub2 by (rule subset_trans)
    then show ?thesis using lt' X0 by simp
  qed
  from one[OF inst_w] have k1: ‹d - 1 < length α›
    and Xa: ‹fst (α ! (d - 1)) = fst (snd pr ! 0)› by auto
  have first_rel: ‹snd (snd pr ! 0) = Eq›
    using hdEq rhs_ne unfolding preq by (simp add: hd_conv_nth)
  have bound: ‹∃c. irep_set (irep_pre (snd (snd pr ! 0)) (snd (α ! (d - 1)))) ⊆ {c}›
  proof (cases ‹fst (snd pr ! 0)›)
    case (Tm b)
    from tmS k1 Xa Tm obtain c where ‹snd (α ! (d - 1)) = FinRep [c]› by auto
    then show ?thesis unfolding first_rel irep_pre_Eq by auto
  next
    case (Nt B)
    have hd0': ‹fst (hd rhs) = fst (snd pr ! 0)›
      using rhs_ne unfolding preq by (simp add: hd_conv_nth)
    have Banch: ‹B ∈ set (anchored_nts G)›
      using hdok unfolding hd0' Nt by simp
    have ‹∃c. irep_set (snd (α ! (d - 1))) ⊆ {c}›
      using sng[rule_format, of ‹d - 1› B] k1 Xa Nt Banch by simp
    then obtain c where ‹irep_set (snd (α ! (d - 1))) ⊆ {c}› by blast
    then show ?thesis unfolding first_rel irep_pre_Eq by auto
  qed
  have bound': ‹∃c. ∀R. (pr, length (snd pr), R) ∈ set (xclosure_auto G (hd Xs)) ⟶
      irep_set R ⊆ {c}›
    using bound one by blast
  then obtain c where c: ‹⋀R. (pr, length (snd pr), R) ∈ set (xclosure_auto G (hd Xs)) ⟹
      irep_set R ⊆ {c}› by blast
  have ‹irep_set (red_set (xclosure_auto G (hd Xs)) pr) ⊆ {c}›
    using c by (fastforce simp: red_set_correct)
  then show ?thesis by blast
qed

section ‹The canonical tracked stack›

text ‹The descent needs more than const‹didx_ok›: the goto history
  (const‹dshape›), singleton pools on shift entries, the canonical bottom
  index, and the ‹adjacency› tying each tracked index to the canonical goto
  target of the index below along the recorded symbol.  The bottom index and the
  adjacency say what Barthwal's ‹validItem_inv›
  cite‹‹Def.~5.4.3› in "barthwal2010-thesis-cfl-hol4"› says: the state of every
  sub-stack is the one reached from the start state by reading its symbols.  The safety
  invariant of Jourdan et al. cite‹‹Sect.~3.2› in "jourdan2012-validating-lr1"›
  describes only a statically known suffix of the stack; here every index is
  tracked.  The reachability
  induction constructs exactly these witnesses.›

definition strack :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) xitem list list ⇒
    (('n, 't) sym × indrep) list ⇒ nat list ⇒ bool› where
  ‹strack G Shn Xs α pstk ⟷
     dshape G Shn Xs α ∧
     didx_ok G (pr0_states G Shn) Xs pstk ∧
     last pstk = p0start G Shn ∧
     (∀k < length α. ∀a. fst (α ! k) = Tm a ⟶ (∃c. snd (α ! k) = FinRep [c])) ∧
     (∀k < length α. ∀B. fst (α ! k) = Nt B ⟶ B ∈ set (anchored_nts G) ⟶
        (∃c. irep_set (snd (α ! k)) ⊆ {c})) ∧
     (∀k < length α. ∀B. fst (α ! k) = Nt B ⟶
        (∀l ∈ irep_set (snd (α ! k)). ∃pr R0. fst pr = B ∧
           (pr, 0, R0) ∈ set (xclosure_auto G (Xs ! Suc k)) ∧ l ∈ irep_set R0)) ∧
     (∀k < length α. pstk ! k =
        st_find (pr0_states G Shn)
          (cgoto (creach G (pr0_states G Shn ! (pstk ! Suc k))) (fst (α ! k))))›

lemma strackD:
  assumes ‹strack G Shn Xs α pstk›
  shows ‹dshape G Shn Xs α› and ‹didx_ok G (pr0_states G Shn) Xs pstk›
    and ‹last pstk = p0start G Shn›
    and ‹∀k < length α. ∀a. fst (α ! k) = Tm a ⟶ (∃c. snd (α ! k) = FinRep [c])›
    and ‹∀k < length α. ∀B. fst (α ! k) = Nt B ⟶ B ∈ set (anchored_nts G) ⟶
        (∃c. irep_set (snd (α ! k)) ⊆ {c})›
    and ‹∀k < length α. ∀B. fst (α ! k) = Nt B ⟶
        (∀l ∈ irep_set (snd (α ! k)). ∃pr R0. fst pr = B ∧
           (pr, 0, R0) ∈ set (xclosure_auto G (Xs ! Suc k)) ∧ l ∈ irep_set R0)›
    and ‹∀k < length α. pstk ! k =
        st_find (pr0_states G Shn)
          (cgoto (creach G (pr0_states G Shn ! (pstk ! Suc k))) (fst (α ! k)))›
  using assms unfolding strack_def by blast+

lemma strackI:
  assumes ‹dshape G Shn Xs α› and ‹didx_ok G (pr0_states G Shn) Xs pstk›
    and ‹last pstk = p0start G Shn›
    and ‹∀k < length α. ∀a. fst (α ! k) = Tm a ⟶ (∃c. snd (α ! k) = FinRep [c])›
    and ‹∀k < length α. ∀B. fst (α ! k) = Nt B ⟶ B ∈ set (anchored_nts G) ⟶
        (∃c. irep_set (snd (α ! k)) ⊆ {c})›
    and ‹∀k < length α. ∀B. fst (α ! k) = Nt B ⟶
        (∀l ∈ irep_set (snd (α ! k)). ∃pr R0. fst pr = B ∧
           (pr, 0, R0) ∈ set (xclosure_auto G (Xs ! Suc k)) ∧ l ∈ irep_set R0)›
    and ‹∀k < length α. pstk ! k =
        st_find (pr0_states G Shn)
          (cgoto (creach G (pr0_states G Shn ! (pstk ! Suc k))) (fst (α ! k)))›
  shows ‹strack G Shn Xs α pstk›
  using assms unfolding strack_def by blast

lemma strack_tl:
  assumes tr: ‹strack G Shn Xs ((X0, RA) # α') pstk›
  shows ‹strack G Shn (tl Xs) α' (tl pstk)›
proof -
  note sh = strackD(1)[OF tr] and mt = strackD(2)[OF tr] and lastp = strackD(3)[OF tr]
    and tmS = strackD(4)[OF tr] and sng = strackD(5)[OF tr] and slot = strackD(6)[OF tr]
    and adj = strackD(7)[OF tr]
  note lenX = dshapeD(1)[OF sh] and bot = dshapeD(2)[OF sh] and shp = dshapeD(3)[OF sh]
  have Xs_ne: ‹Xs ≠ []› using lenX by auto
  obtain x0 Xr where Xs_eq: ‹Xs = x0 # Xr› using Xs_ne by (cases Xs) auto
  have nthX: ‹⋀k. tl Xs ! k = Xs ! Suc k› unfolding Xs_eq by simp
  have len_tl: ‹length (tl Xs) = length α' + 1› using lenX by simp
  have lenp: ‹length pstk = length Xs› by (rule didx_ok_len[OF mt])
  obtain p0 Pr where pstk_eq: ‹pstk = p0 # Pr›
    using lenp Xs_ne by (cases pstk) auto
  have nthP: ‹⋀k. tl pstk ! k = pstk ! Suc k› unfolding pstk_eq by simp
  have Pr_ne: ‹Pr ≠ []› using lenp lenX pstk_eq by auto
  have sh': ‹dshape G Shn (tl Xs) α'›
    unfolding dshape_def
  proof (intro conjI)
    show ‹length (tl Xs) = length α' + 1› by (rule len_tl)
    show ‹tl Xs ! length α' = xinit G Shn› using bot by (simp add: nthX)
    show ‹∀k < length α'. tl Xs ! k =
        lgoto (xclosure_auto G (tl Xs ! Suc k)) (fst (α' ! k)) (snd (α' ! k))›
    proof (intro allI impI)
      fix k assume k: ‹k < length α'›
      have ‹Suc k < length ((X0, RA) # α')› using k by simp
      from shp[OF this] show ‹tl Xs ! k =
          lgoto (xclosure_auto G (tl Xs ! Suc k)) (fst (α' ! k)) (snd (α' ! k))›
        by (simp add: nthX)
    qed
  qed
  have mt': ‹didx_ok G (pr0_states G Shn) (tl Xs) (tl pstk)›
    unfolding didx_ok_def
  proof (intro conjI)
    show ‹length (tl pstk) = length (tl Xs)› using lenp by (simp add: Xs_eq pstk_eq)
    show ‹∀k < length (tl Xs). lcore (tl Xs ! k) ≠ {} ⟶
        tl pstk ! k < length (pr0_states G Shn) ∧
        lcore (tl Xs ! k) ⊆ set (pr0_states G Shn ! (tl pstk ! k))›
    proof (intro allI impI)
      fix k assume k: ‹k < length (tl Xs)› and lv: ‹lcore (tl Xs ! k) ≠ {}›
      have sk: ‹Suc k < length Xs› using k unfolding Xs_eq by simp
      show ‹tl pstk ! k < length (pr0_states G Shn) ∧
          lcore (tl Xs ! k) ⊆ set (pr0_states G Shn ! (tl pstk ! k))›
        using didx_okD[OF mt sk] lv by (simp add: nthX nthP)
    qed
  qed
  have last': ‹last (tl pstk) = p0start G Shn›
    using lastp Pr_ne unfolding pstk_eq by simp
  have tmS': ‹∀k < length α'. ∀a. fst (α' ! k) = Tm a ⟶
      (∃c. snd (α' ! k) = FinRep [c])›
  proof (intro allI impI)
    fix k a assume k: ‹k < length α'› and t: ‹fst (α' ! k) = Tm a›
    show ‹∃c. snd (α' ! k) = FinRep [c]›
      using tmS[rule_format, of ‹Suc k› a] k t by simp
  qed
  have sng': ‹∀k < length α'. ∀B. fst (α' ! k) = Nt B ⟶
      B ∈ set (anchored_nts G) ⟶ (∃c. irep_set (snd (α' ! k)) ⊆ {c})›
  proof (intro allI impI)
    fix k B assume k: ‹k < length α'› and t: ‹fst (α' ! k) = Nt B›
      and an: ‹B ∈ set (anchored_nts G)›
    show ‹∃c. irep_set (snd (α' ! k)) ⊆ {c}›
      using sng[rule_format, of ‹Suc k› B] k t an by simp
  qed
  have slot': ‹∀k < length α'. ∀B. fst (α' ! k) = Nt B ⟶
      (∀l ∈ irep_set (snd (α' ! k)). ∃pr R0. fst pr = B ∧
         (pr, 0, R0) ∈ set (xclosure_auto G (tl Xs ! Suc k)) ∧ l ∈ irep_set R0)›
  proof (intro allI impI)
    fix k B assume k: ‹k < length α'› and t: ‹fst (α' ! k) = Nt B›
    have ‹∀l ∈ irep_set (snd (α' ! k)). ∃pr R0. fst pr = B ∧
        (pr, 0, R0) ∈ set (xclosure_auto G (Xs ! Suc (Suc k))) ∧ l ∈ irep_set R0›
      using slot[rule_format, of ‹Suc k› B] k t by simp
    then show ‹∀l ∈ irep_set (snd (α' ! k)). ∃pr R0. fst pr = B ∧
        (pr, 0, R0) ∈ set (xclosure_auto G (tl Xs ! Suc k)) ∧ l ∈ irep_set R0›
      by (simp add: nthX)
  qed
  have adj': ‹∀k < length α'. tl pstk ! k =
      st_find (pr0_states G Shn)
        (cgoto (creach G (pr0_states G Shn ! (tl pstk ! Suc k))) (fst (α' ! k)))›
  proof (intro allI impI)
    fix k assume k: ‹k < length α'›
    have ‹Suc k < length ((X0, RA) # α')› using k by simp
    from adj[rule_format, OF this]
    show ‹tl pstk ! k = st_find (pr0_states G Shn)
        (cgoto (creach G (pr0_states G Shn ! (tl pstk ! Suc k))) (fst (α' ! k)))›
      by (simp add: nthP)
  qed
  show ?thesis
    by (rule strackI[OF sh' mt' last' tmS' sng' slot' adj'])
qed

lemma strack_drop:
  ‹strack G Shn Xs α pstk ⟹ d ≤ length α ⟹
   strack G Shn (drop d Xs) (drop d α) (drop d pstk)›
proof (induction d arbitrary: Xs α pstk)
  case 0
  then show ?case by simp
next
  case (Suc d)
  obtain X RA α' where α: ‹α = (X, RA) # α'›
    using Suc.prems(2) by (cases α) auto
  have tl: ‹strack G Shn (tl Xs) α' (tl pstk)›
    by (rule strack_tl[OF Suc.prems(1)[unfolded α]])
  have d_le: ‹d ≤ length α'› using Suc.prems(2) unfolding α by simp
  from Suc.IH[OF tl d_le] show ?case unfolding α by (simp add: drop_Suc)
qed

text ‹Pushing a frame on a tracked stack: the new frame's index is the
  canonical goto of the index below along the pushed symbol, the extended
  index stack is checked by const‹didx_ok›, and the three per-label
  conditions are checked for the pushed label only.›

lemma strack_push:
  assumes tr: ‹strack G Shn Xs α pstk›
    and NF: ‹NF = lgoto (xclosure_auto G (hd Xs)) X RA›
    and p': ‹p' = st_find (pr0_states G Shn)
        (cgoto (creach G (pr0_states G Shn ! (pstk ! 0))) X)›
    and mt': ‹didx_ok G (pr0_states G Shn) (NF # Xs) (p' # pstk)›
    and tm: ‹⋀a. X = Tm a ⟹ ∃c. RA = FinRep [c]›
    and sng: ‹⋀B. X = Nt B ⟹ B ∈ set (anchored_nts G) ⟹ ∃c. irep_set RA ⊆ {c}›
    and slot: ‹⋀B l. X = Nt B ⟹ l ∈ irep_set RA ⟹ ∃pr R0. fst pr = B ∧
        (pr, 0, R0) ∈ set (xclosure_auto G (hd Xs)) ∧ l ∈ irep_set R0›
  shows ‹strack G Shn (NF # Xs) ((X, RA) # α) (p' # pstk)›
proof -
  note sh = strackD(1)[OF tr] and mt = strackD(2)[OF tr] and lastp = strackD(3)[OF tr]
    and tmS = strackD(4)[OF tr] and sngI = strackD(5)[OF tr] and slotI = strackD(6)[OF tr]
    and adj = strackD(7)[OF tr]
  have ne: ‹Xs ≠ []› using dshapeD(1)[OF sh] by auto
  have pstk_ne: ‹pstk ≠ []› using didx_ok_len[OF mt] ne by auto
  have hd0: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
  have sh': ‹dshape G Shn (NF # Xs) ((X, RA) # α)›
    unfolding NF by (rule dshape_push[OF sh ne])
  have last': ‹last (p' # pstk) = p0start G Shn› using lastp pstk_ne by simp
  have tmS': ‹∀k < length ((X, RA) # α). ∀b. fst (((X, RA) # α) ! k) = Tm b ⟶
      (∃c'. snd (((X, RA) # α) ! k) = FinRep [c'])›
    using tmS tm by (auto simp: less_Suc_eq_0_disj nth_Cons')
  have sng': ‹∀k < length ((X, RA) # α). ∀B. fst (((X, RA) # α) ! k) = Nt B ⟶
      B ∈ set (anchored_nts G) ⟶ (∃c'. irep_set (snd (((X, RA) # α) ! k)) ⊆ {c'})›
    using sngI sng by (auto simp: less_Suc_eq_0_disj nth_Cons')
  have slot': ‹∀k < length ((X, RA) # α). ∀B. fst (((X, RA) # α) ! k) = Nt B ⟶
      (∀l ∈ irep_set (snd (((X, RA) # α) ! k)). ∃pr R0. fst pr = B ∧
         (pr, 0, R0) ∈ set (xclosure_auto G ((NF # Xs) ! Suc k)) ∧ l ∈ irep_set R0)›
    using slotI slot hd0 by (auto simp: less_Suc_eq_0_disj nth_Cons')
  have adj': ‹∀k < length ((X, RA) # α). (p' # pstk) ! k =
      st_find (pr0_states G Shn)
        (cgoto (creach G (pr0_states G Shn ! ((p' # pstk) ! Suc k)))
          (fst (((X, RA) # α) ! k)))›
  proof (intro allI impI)
    fix k assume ‹k < length ((X, RA) # α)›
    then show ‹(p' # pstk) ! k =
        st_find (pr0_states G Shn)
          (cgoto (creach G (pr0_states G Shn ! ((p' # pstk) ! Suc k)))
            (fst (((X, RA) # α) ! k)))›
      using adj p' by (cases k) auto
  qed
  show ?thesis by (rule strackI[OF sh' mt' last' tmS' sng' slot' adj'])
qed

text ‹Every configuration the indexed machine reaches carries a tracked
  stack whose indices are the driver's own: a shift pushes the token's
  singleton label, a reduce drops the handle and pushes the nonterminal with
  its pooled anchors.  The pushed index is the table's goto, which resolves
  to the canonical successor because the pushed frame is live
  (text‹dnext_st_find›); the singleton and slot conditions come from
  text‹red_set_anchored_singleton› and text‹dshape_persist›.›

theorem imreach_strack:
  assumes ‹imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn) ic›
    and fresh: ‹fresh_name G Shn›
  shows ‹∃α. strack G Shn (fst (fst ic)) α (snd ic)›
  using assms(1)
proof (induction rule: imreach.induct)
  case (imreach_init w)
  have mt: ‹didx_ok G (pr0_states G Shn) [xinit G Shn]
      [st_find (pr0_states G Shn) (lr0_start G Shn)]›
    by (rule didx_ok_init[OF tables_ok_concrete])
  have ‹strack G Shn [xinit G Shn] [] [st_find (pr0_states G Shn) (lr0_start G Shn)]›
    unfolding strack_def using dshape_init mt by (simp add: p0start_def)
  then show ?case by auto
next
  case (imreach_step ic act ic')
  let ?sts = ‹pr0_states G Shn› and ?gt = ‹pgtab G (pr0_states G Shn)›
  note tab = tables_ok_concrete[of G Shn]
  obtain gc istk where ic: ‹ic = (gc, istk)› by (cases ic)
  obtain Xs w where gc: ‹gc = (Xs, w)› by (cases gc)
  obtain gc' istk' where ic': ‹ic' = (gc', istk')› by (cases ic')
  obtain α where tr: ‹strack G Shn Xs α istk›
    using imreach_step.IH unfolding ic gc by auto
  note sh = strackD(1)[OF tr] and mt = strackD(2)[OF tr]
    and tmS = strackD(4)[OF tr] and sngI = strackD(5)[OF tr]
  note lenXa = dshapeD(1)[OF sh]
  have len: ‹length istk = length Xs› by (rule didx_ok_len[OF mt])
  have lv': ‹dlive gc'› using imreach_step.hyps(3) unfolding ic' by simp
  show ?case
  proof (cases act)
    case DShift
    have step0: ‹imstep G ?gt ?sts ((Xs, w), istk) DShift = Some (gc', istk')›
      using imreach_step.hyps(2) unfolding ic gc ic' DShift .
    then have mstep: ‹mstep G (Xs, w) DShift = Some gc'›
      and istk': ‹istk' = dnext ?gt ?sts (hd istk) (Tm (fst (hd w))) # istk›
      unfolding imstep_def by (auto split: option.splits)
    have step: ‹mstep_cached G (map (xclosure_auto G) Xs) (Xs, w) DShift = Some gc'›
      using mstep unfolding mstep_def by simp
    from mstep_shift_shape[OF step] obtain a c w' where
      w: ‹w = (a, c) # w'› and ne: ‹Xs ≠ []›
      and gc': ‹gc' = (lgoto (hd (map (xclosure_auto G) Xs)) (Tm a) (FinRep [c]) # Xs, w')› .
    define NF where ‹NF = lgoto (xclosure_auto G (hd Xs)) (Tm a) (FinRep [c])›
    define p' where ‹p' = dnext ?gt ?sts (hd istk) (Tm a)›
    have gc'2: ‹fst gc' = NF # Xs›
      unfolding gc' NF_def using ne by (simp add: hd_map)
    have istk'2: ‹istk' = p' # istk› unfolding istk' p'_def w by simp
    have z_lt: ‹0 < length Xs› using ne by simp
    have hd0: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
    have istk_ne: ‹istk ≠ []› using len ne by auto
    have hdi: ‹hd istk = istk ! 0› using istk_ne by (simp add: hd_conv_nth)
    have liveNF: ‹lcore NF ≠ {}›
      using lv' ne unfolding gc' NF_def dlive_lcore by (simp add: hd_map)
    have p'eq: ‹p' = st_find ?sts (cgoto (creach G (?sts ! (istk ! 0))) (Tm a))›
      unfolding p'_def hdi
      by (rule dnext_st_find[OF tab mt z_lt liveNF[unfolded NF_def hd0]])
    have mt': ‹didx_ok G ?sts (NF # Xs) (p' # istk)›
      using didx_ok_push[OF tab mt z_lt, where X = ‹Tm a› and RA = ‹FinRep [c]›]
      unfolding NF_def p'_def hd0 hdi by simp
    have ‹strack G Shn (NF # Xs) ((Tm a, FinRep [c]) # α) (p' # istk)›
      by (rule strack_push[OF tr NF_def p'eq mt']) simp_all
    then show ?thesis unfolding ic' fst_conv snd_conv gc'2 istk'2 by blast
  next
    case (DReduce pr)
    define d where ‹d = length (snd pr)›
    have step0: ‹imstep G ?gt ?sts ((Xs, w), istk) (DReduce pr) = Some (gc', istk')›
      using imreach_step.hyps(2) unfolding ic gc ic' DReduce .
    then have mstep: ‹mstep G (Xs, w) (DReduce pr) = Some gc'›
      and istk': ‹istk' = dnext ?gt ?sts (istk ! d) (Nt (fst pr)) # drop d istk›
      unfolding imstep_def d_def by (auto split: option.splits)
    have step: ‹mstep_cached G (map (xclosure_auto G) Xs) (Xs, w) (DReduce pr) = Some gc'›
      using mstep unfolding mstep_def by simp
    have d_lt: ‹d < length Xs›
      unfolding d_def by (rule mstep_reduce_shape[OF step]) blast
    have gc'0: ‹gc' = (lgoto (map (xclosure_auto G) Xs ! d) (Nt (fst pr))
                  (red_set (hd (map (xclosure_auto G) Xs)) pr) # drop d Xs, w)›
      unfolding d_def by (rule mstep_reduce_shape[OF step]) blast
    have ne: ‹Xs ≠ []› using d_lt by auto
    have hdd: ‹hd (drop d Xs) = Xs ! d› using d_lt by (simp add: hd_drop_conv_nth)
    define RA where ‹RA = red_set (xclosure_auto G (hd Xs)) pr›
    define NF where ‹NF = lgoto (xclosure_auto G (hd (drop d Xs))) (Nt (fst pr)) RA›
    define p' where ‹p' = dnext ?gt ?sts (istk ! d) (Nt (fst pr))›
    have gc'2: ‹fst gc' = NF # drop d Xs›
      unfolding gc'0 NF_def RA_def hdd using d_lt ne by (simp add: hd_map)
    have istk'2: ‹istk' = p' # drop d istk› unfolding istk' p'_def ..
    have d_le_a: ‹d ≤ length α› using d_lt lenXa by simp
    have trd: ‹strack G Shn (drop d Xs) (drop d α) (drop d istk)›
      by (rule strack_drop[OF tr d_le_a])
    have pd: ‹drop d istk ! 0 = istk ! d› using len d_lt by simp
    have liveNF: ‹lcore NF ≠ {}›
      using lv' d_lt ne unfolding gc'0 NF_def RA_def hdd dlive_lcore by (simp add: hd_map)
    have p'eq: ‹p' = st_find ?sts (cgoto (creach G (?sts ! (drop d istk ! 0))) (Nt (fst pr)))›
      unfolding p'_def pd
      by (rule dnext_st_find[OF tab mt d_lt liveNF[unfolded NF_def hdd]])
    have mt': ‹didx_ok G ?sts (NF # drop d Xs) (p' # drop d istk)›
      unfolding NF_def p'_def hdd by (rule didx_ok_push[OF tab mt d_lt])
    have sng0: ‹fst pr ∈ set (anchored_nts G) ⟹ ∃c. irep_set RA ⊆ {c}›
      unfolding RA_def
      by (rule red_set_anchored_singleton[OF sh ne tmS sngI fresh])
    have slot0: ‹⋀l. l ∈ irep_set RA ⟹ ∃pra R0. fst pra = fst pr ∧
        (pra, 0, R0) ∈ set (xclosure_auto G (Xs ! d)) ∧ l ∈ irep_set R0›
    proof -
      fix l assume l: ‹l ∈ irep_set RA›
      then obtain R where R: ‹(pr, d, R) ∈ set (xclosure_auto G (hd Xs))›
        and lR: ‹l ∈ irep_set R›
        unfolding RA_def red_set_correct d_def[symmetric] by blast
      have hd0: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
      show ‹∃pra R0. fst pra = fst pr ∧
          (pra, 0, R0) ∈ set (xclosure_auto G (Xs ! d)) ∧ l ∈ irep_set R0›
      proof (cases d)
        case 0
        have ‹(pr, 0, R) ∈ set (xclosure_auto G (Xs ! d))›
          using R hd0 unfolding 0 by simp
        then show ?thesis using lR by blast
      next
        case (Suc d')
        have kern: ‹(pr, d, R) ∈ set (Xs ! 0)›
          by (rule xclosure_auto_kernelD[OF R[unfolded hd0]]) (simp add: Suc)
        have z_lt: ‹0 < length Xs› using ne by simp
        have one_le: ‹1 ≤ d› using Suc by simp
        from dshape_persist[OF sh kern z_lt one_le] obtain R0 where
          m0: ‹(pr, 0, R0) ∈ set (xclosure_auto G (Xs ! (0 + d)))›
          and sb: ‹irep_set R ⊆ irep_set R0› by blast
        have ‹(pr, 0, R0) ∈ set (xclosure_auto G (Xs ! d))› using m0 by simp
        then show ?thesis using sb lR by blast
      qed
    qed
    have ‹strack G Shn (NF # drop d Xs) ((Nt (fst pr), RA) # drop d α) (p' # drop d istk)›
    proof (rule strack_push[OF trd NF_def p'eq mt'])
      show ‹⋀a. Nt (fst pr) = Tm a ⟹ ∃c. RA = FinRep [c]› by simp
      show ‹⋀B. Nt (fst pr) = Nt B ⟹ B ∈ set (anchored_nts G) ⟹ ∃c. irep_set RA ⊆ {c}›
        using sng0 by simp
      show ‹⋀B l. Nt (fst pr) = Nt B ⟹ l ∈ irep_set RA ⟹ ∃pra R0. fst pra = B ∧
          (pra, 0, R0) ∈ set (xclosure_auto G (hd (drop d Xs))) ∧ l ∈ irep_set R0›
        using slot0 unfolding hdd by simp
    qed
    then show ?thesis unfolding ic' fst_conv snd_conv gc'2 istk'2 by blast
  qed
qed

section ‹The descent to the start state›

text ‹The entry pool of the top frame of a tracked stack: the goto label's
  anchors, or ‹istart_ind› at the bottom frame.›

definition epool :: ‹('n, 't) is_cfg ⇒ (('n, 't) sym × indrep) list ⇒ nat set› where
  ‹epool G α = (case α of [] ⇒ {istart_ind G} | (X, RA) # _ ⇒ irep_set RA)›

lemma pin_edgesI:
  ‹p < length gt ⟹ (X, s) ∈ set (gt ! p) ⟹ (p, X) ∈ set (pin_edges gt s)›
  unfolding pin_edges_def by fastforce

text ‹A cursor realised in a frame: its item is in the frame's closure with an
  indentation the class holds at, for the lookahead column ‹c›.›

definition icur :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ nat ⇒ ('n, 't) witem ⇒ bool›
  where
  ‹icur G X c = (λ(pr, m, σ). ∃R j. (pr, m, R) ∈ set (xclosure_auto G X) ∧
      j ∈ irep_set R ∧ wsat σ c j)›

text ‹A cursor realised in a frame at round ‹t› of its closure: the item is
  among the frame's slots after ‹t› rounds, with an indentation the class holds
  at for the lookahead column ‹c›.  const‹icur› is the fuelled round.  The
  descent counts rounds down within a frame (a dot-0 item's indentation comes from
  a predicting item of an earlier round) and frames down across a pop.›

definition icur_at :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ nat ⇒ nat ⇒
    ('n, 't) witem ⇒ bool› where
  ‹icur_at G X t c = (λ(pr, m, σ). ∃R j. (pr, m, R) ∈ set (xslots G X (xiter G X t)) ∧
      j ∈ irep_set R ∧ wsat σ c j)›

lemma icur_at_fuel: ‹icur G X c cur ⟷ icur_at G X (xfuel G X) c cur›
  unfolding icur_def icur_at_def xclosure_auto_def xclosure_def by (cases cur) simp

text ‹Where a slot's indentation comes from: an element of a dot-0 pool at round
  ‹t› is the image of an element of a predicting item's pool at an earlier round.›

lemma xiter_pred:
  assumes p: ‹p < length (iprods G)› and j: ‹j ∈ irep_set (xiter G xs t ! p)›
  shows ‹∃t' pr' m' R' j'. t' < t ∧ (pr', m', R') ∈ set (xslots G xs (xiter G xs t')) ∧
      m' < length (snd pr') ∧ fst (snd pr' ! m') = Nt (fst (iprods G ! p)) ∧
      j' ∈ irep_set R' ∧ irel_sat (snd (snd pr' ! m')) j j'›
proof -
  have ‹p < length (iprods G) ⟹ j ∈ irep_set (xiter G xs t ! p) ⟹
      ∃t' pr' m' R' j'. t' < t ∧ (pr', m', R') ∈ set (xslots G xs (xiter G xs t')) ∧
      m' < length (snd pr') ∧ fst (snd pr' ! m') = Nt (fst (iprods G ! p)) ∧
      j' ∈ irep_set R' ∧ irel_sat (snd (snd pr' ! m')) j j'›
  proof (induction t arbitrary: p j)
    case 0
    then show ?case by simp
  next
    case (Suc t)
    have eq: ‹xiter G xs (Suc t) ! p =
        fold (xcontrib (iprods G ! p)) (xslots G xs (xiter G xs t)) (xiter G xs t ! p)›
      using xround_nth[OF xiter_length Suc.prems(1)] by simp
    have ‹j ∈ irep_set (xiter G xs t ! p) ∪
        ⋃ (ximg (iprods G ! p) ` set (xslots G xs (xiter G xs t)))›
      using Suc.prems(2) unfolding eq fold_xcontrib_set .
    then show ?case
    proof
      assume ‹j ∈ irep_set (xiter G xs t ! p)›
      from Suc.IH[OF Suc.prems(1) this] show ?thesis by (meson less_SucI)
    next
      assume ‹j ∈ ⋃ (ximg (iprods G ! p) ` set (xslots G xs (xiter G xs t)))›
      then show ?thesis by (fastforce split: if_splits)
    qed
  qed
  from this[OF p j] show ?thesis .
qed

text ‹The pooled width invariant, at any round of const‹xclosure_auto›.›

lemma xslots_pool:
  assumes kern: ‹⋀pr m R j. (pr, m, R) ∈ set xs ⟹ j ∈ irep_set R ⟹
      ∃ρ l. (pr, m, ρ) ∈ set (wreach G s) ∧ l ∈ P ∧ wsat ρ l j›
    and mem: ‹(pr, m, R) ∈ set (xslots G xs (xiter G xs t))›
    and jR: ‹j ∈ irep_set R›
  shows ‹∃ρ l. (pr, m, ρ) ∈ set (wreach G s) ∧ l ∈ P ∧ wsat ρ l j›
  using mem
proof (rule xslots_memE)
  assume mem2: ‹(pr, m, R) ∈ set xs›
  from kern[OF mem2 jR] show ?thesis .
next
  fix q assume q: ‹q < length (iprods G)›
    and ‹q < length (xiter G xs t)›
    and eq: ‹(pr, m, R) = (iprods G ! q, 0, xiter G xs t ! q)›
  have ‹j ∈ irep_set (xiter G xs t ! q)› using jR eq by simp
  from xiter_pool[OF kern q this] show ?thesis using eq by simp
qed

text ‹The frame-0 pooled width invariant, packaged: every item of the top frame's
  slots at any round carries a ‹wreach› class at the tracked precise state,
  anchored at some element of the top entry pool.›

lemma strack_pool_at:
  assumes tr: ‹strack G Shn Xs α pstk› and live: ‹lcore (hd Xs) ≠ {}›
    and mem: ‹(pr, m, R) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t))›
    and jR: ‹j ∈ irep_set R›
  shows ‹∃ρ l. (pr, m, ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0))) ∧
        l ∈ epool G α ∧ wsat ρ l j›
proof -
  note sh = strackD(1)[OF tr] and mt = strackD(2)[OF tr]
  note lenX = dshapeD(1)[OF sh] and bot = dshapeD(2)[OF sh] and shp = dshapeD(3)[OF sh]
  have Xs_ne: ‹Xs ≠ []› using lenX by auto
  have hd0: ‹hd Xs = Xs ! 0› using Xs_ne by (simp add: hd_conv_nth)
  have z_lt: ‹0 < length Xs› using Xs_ne by auto
  have live0: ‹lcore (Xs ! 0) ≠ {}› using live hd0 by simp
  have cover0: ‹lcore (Xs ! 0) ⊆ set (pr0_states G Shn ! (pstk ! 0))›
    using didx_okD[OF mt z_lt live0] by blast
  have kern0: ‹⋀pr' m' R' j'. (pr', m', R') ∈ set (Xs ! 0) ⟹
      j' ∈ irep_set R' ⟹
      ∃ρ l. (pr', m', ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0))) ∧
            l ∈ epool G α ∧ wsat ρ l j'›
  proof -
    fix pr' m' R' j' assume a: ‹(pr', m', R') ∈ set (Xs ! 0)›
      and b: ‹j' ∈ irep_set R'›
    have cov: ‹(pr', m') ∈ set (pr0_states G Shn ! (pstk ! 0))›
      by (rule lcore_subD[OF cover0 a b])
    show ‹∃ρ l. (pr', m', ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0))) ∧
        l ∈ epool G α ∧ wsat ρ l j'›
    proof (cases α)
      case Nil
      have x0: ‹Xs ! 0 = xinit G Shn› using bot unfolding Nil by simp
      from wanch_pool_xinit[OF a[unfolded x0] b cov] obtain ρ where
        ‹(pr', m', ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0)))›
        and ‹wsat ρ (istart_ind G) j'› by blast
      then show ?thesis unfolding epool_def Nil by auto
    next
      case (Cons e α')
      obtain X0 RA where e: ‹e = (X0, RA)› by (cases e)
      have z_la: ‹0 < length α› unfolding Cons by simp
      have f0: ‹Xs ! 0 = lgoto (xclosure_auto G (Xs ! Suc 0)) X0 RA›
        using shp[OF z_la] unfolding Cons e by simp
      have covL: ‹⋀pra ma Ra ja. (pra, ma, Ra)
          ∈ set (lgoto (xclosure_auto G (Xs ! Suc 0)) X0 RA) ⟹
          ja ∈ irep_set Ra ⟹
          (pra, ma) ∈ set (pr0_states G Shn ! (pstk ! 0))›
      proof -
        fix pra ma Ra ja
        assume aa: ‹(pra, ma, Ra)
            ∈ set (lgoto (xclosure_auto G (Xs ! Suc 0)) X0 RA)›
          and bb: ‹ja ∈ irep_set Ra›
        have ‹(pra, ma, Ra) ∈ set (Xs ! 0)› using aa f0 by simp
        then show ‹(pra, ma) ∈ set (pr0_states G Shn ! (pstk ! 0))›
          using bb by (rule lcore_subD[OF cover0])
      qed
      have ex: ‹∃ρ l. (pr', m', ρ)
            ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0))) ∧
          l ∈ irep_set RA ∧ wsat ρ l j'›
        by (rule wanch_pool_lgoto[OF _ a[unfolded f0] b]) (rule covL)
      then show ?thesis unfolding epool_def Cons e by auto
    qed
  qed
  show ?thesis
    by (rule xslots_pool[OF _ mem[unfolded hd0] jR]) (rule kern0)
qed

lemma strack_pool:
  assumes tr: ‹strack G Shn Xs α pstk› and live: ‹lcore (hd Xs) ≠ {}›
    and mem: ‹(pr, m, R) ∈ set (xclosure_auto G (hd Xs))›
    and jR: ‹j ∈ irep_set R›
  shows ‹∃ρ l. (pr, m, ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0))) ∧
        l ∈ epool G α ∧ wsat ρ l j›
  using mem unfolding xclosure_auto_def xclosure_def
  by (rule strack_pool_at[OF tr live _ jR])

text ‹A dot-0 item of the fresh start name is the start item of the bottom frame,
  whose pool is ‹{istart_ind}›: no production has the start name on its left (so it
  is no slot), and every kernel item above the bottom frame has its dot past 0.›

lemma strack_start_item:
  assumes tr: ‹strack G Shn Xs α pstk› and fresh: ‹fresh_name G Shn›
    and mem: ‹(pr, 0, R) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t))›
    and shn: ‹fst pr = Shn›
  shows ‹α = [] ∧ irep_set R = {istart_ind G}›
proof -
  note sh = strackD(1)[OF tr]
  note lenX = dshapeD(1)[OF sh] and bot = dshapeD(2)[OF sh] and shp = dshapeD(3)[OF sh]
  have Xs_ne: ‹Xs ≠ []› using lenX by auto
  have hd0: ‹hd Xs = Xs ! 0› using Xs_ne by (simp add: hd_conv_nth)
  have kern: ‹(pr, 0, R) ∈ set (hd Xs)›
  proof (rule xslots_memE[OF mem])
    assume ‹(pr, 0, R) ∈ set (hd Xs)›
    then show ?thesis .
  next
    fix p assume ‹(pr, 0, R) = (iprods G ! p, 0, xiter G (hd Xs) t ! p)›
      and ‹p < length (iprods G)›
    then have ‹pr ∈ set (iprods G)› by auto
    then have ‹Shn ∈ fst ` set (iprods G)› using shn by force
    then show ?thesis using fresh unfolding fresh_name_def by blast
  qed
  show ?thesis
  proof (cases α)
    case Nil
    have x0: ‹Xs ! 0 = xinit G Shn› using bot unfolding Nil by simp
    then show ?thesis using kern hd0 unfolding Nil xinit_def by auto
  next
    case (Cons e α')
    obtain X0 RA where e: ‹e = (X0, RA)› by (cases e)
    have z_la: ‹0 < length α› unfolding Cons by simp
    have f0: ‹Xs ! 0 = lgoto (xclosure_auto G (Xs ! Suc 0)) X0 RA›
      using shp[OF z_la] unfolding Cons e by simp
    have ‹(pr, 0, R) ∈ set (lgoto (xclosure_auto G (Xs ! Suc 0)) X0 RA)›
      using kern hd0 f0 by simp
    from lgoto_dot_pos[OF this] show ?thesis by simp
  qed
qed

text ‹A kernel item of the top frame is the goto image of an item of the frame
  below: the symbol before its dot is the entry's, its pool is the lower item's
  filtered by the dot's relation against the entry pool.›

lemma strack_pop:
  assumes tr: ‹strack G Shn Xs α pstk›
    and mem: ‹(pr, Suc m, R) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t))›
    and jR: ‹j ∈ irep_set R›
  obtains X0 RA α' R' l where ‹α = (X0, RA) # α'› and ‹m < length (snd pr)›
    and ‹fst (snd pr ! m) = X0› and ‹(pr, m, R') ∈ set (xclosure_auto G (Xs ! 1))›
    and ‹j ∈ irep_set R'› and ‹l ∈ irep_set RA› and ‹irel_sat (snd (snd pr ! m)) l j›
proof -
  have sh: ‹dshape G Shn Xs α› using strackD(1)[OF tr] .
  have len: ‹length Xs = length α + 1› by (rule dshapeD(1)[OF sh])
  have last: ‹Xs ! length α = xinit G Shn› by (rule dshapeD(2)[OF sh])
  have hd: ‹hd Xs = Xs ! 0› using len by (cases Xs) auto
  have mem0: ‹(pr, Suc m, R) ∈ set (Xs ! 0)›
    using mem unfolding hd by (auto dest: xslots_memE)
  obtain X0 RA α' where α: ‹α = (X0, RA) # α'›
  proof (cases α)
    case Nil
    then have ‹Xs ! 0 = xinit G Shn› using last by simp
    with mem0 show thesis unfolding xinit_def by simp
  next
    case (Cons a α')
    then show thesis using that by (cases a) auto
  qed
  have ‹0 < length α› unfolding α by simp
  from dshapeD(3)[OF sh this] have X0eq:
    ‹Xs ! 0 = lgoto (xclosure_auto G (Xs ! Suc 0)) (fst (α ! 0)) (snd (α ! 0))› .
  from mem0 have ‹(pr, Suc m, R) ∈ set (lgoto (xclosure_auto G (Xs ! 1)) X0 RA)›
    unfolding X0eq α by simp
  from lgoto_kernel_step[OF this] obtain Rs where
    m_lt: ‹m < length (snd pr)› and fstm: ‹fst (snd pr ! m) = X0›
    and Rs: ‹(pr, m, Rs) ∈ set (xclosure_auto G (Xs ! 1))›
    and Req: ‹R = irep_inter Rs (irep_pre (snd (snd pr ! m)) RA)› .
  from jR obtain l where ‹j ∈ irep_set Rs› and ‹l ∈ irep_set RA›
    and ‹irel_sat (snd (snd pr ! m)) l j› unfolding Req by auto
  then show thesis by (rule that[OF α m_lt fstm Rs, of l])
qed

text ‹The tracked indices of the two top frames are adjacent along the entry
  symbol, so the edge is in const‹pin_edges›: the lower item is in the lower
  state's LR(0) closure, hence the goto entry is in its row of the table.›

lemma strack_edge:
  assumes tr: ‹strack G Shn Xs ((X0, RA) # α') pstk›
    and mem: ‹(pr, m, R) ∈ set (xclosure_auto G (Xs ! 1))› and jR: ‹j ∈ irep_set R›
    and m: ‹m < length (snd pr)› and X: ‹fst (snd pr ! m) = X0›
  shows ‹pstk ! 1 < length (pr0_states G Shn) ∧
      (pstk ! 1, X0) ∈ set (pin_edges (pgtab G (pr0_states G Shn)) (pstk ! 0))›
proof -
  have live1: ‹lcore (Xs ! 1) ≠ {}› using closure_live_kernel[OF mem jR] .
  have len: ‹length Xs = length ((X0, RA) # α') + 1›
    using dshapeD(1)[OF strackD(1)[OF tr]] .
  then have lt: ‹1 < length Xs› by simp
  have ok: ‹didx_ok G (pr0_states G Shn) Xs pstk› using strackD(2)[OF tr] .
  from didx_okD[OF ok lt live1]
  have lt1: ‹pstk ! 1 < length (pr0_states G Shn)›
    and cover1: ‹lcore (Xs ! 1) ⊆ set (pr0_states G Shn ! (pstk ! 1))› by blast+
  have kern: ‹⋀pr m R. (pr, m, R) ∈ set (Xs ! 1) ⟹ irep_nonempty R ⟹
      (pr, m) ∈ set (pr0_states G Shn ! (pstk ! 1))›
    using lcore_subD_ne[OF cover1] .
  have creach: ‹(pr, m) ∈ set (creach G (pr0_states G Shn ! (pstk ! 1)))›
    using xclosure_auto_live_creach[OF kern mem jR] .
  have tab: ‹(X0, st_find (pr0_states G Shn)
        (cgoto (creach G (pr0_states G Shn ! (pstk ! 1))) X0))
      ∈ set (pgtab G (pr0_states G Shn) ! (pstk ! 1))›
    using pgtab_mem[OF lt1 creach m] X by simp
  have p0: ‹pstk ! 0 = st_find (pr0_states G Shn)
      (cgoto (creach G (pr0_states G Shn ! (pstk ! 1))) X0)›
    using strackD(7)[OF tr, rule_format, of 0] by simp
  show ?thesis
    using lt1 tab p0 pin_edgesI[of ‹pstk ! 1› ‹pgtab G (pr0_states G Shn)›] by simp
qed

text ‹A rigid entry's pool is a singleton: a token's column, or an anchored
  nonterminal's.›

lemma strack_rigid:
  assumes tr: ‹strack G Shn Xs ((X0, RA) # α') pstk›
    and rig: ‹irigid (anchored_nts G) X0›
  shows ‹∃col. irep_set RA ⊆ {col}›
proof (cases X0)
  case (Tm a)
  from strackD(4)[OF tr] Tm obtain c where ‹RA = FinRep [c]› by fastforce
  then show ?thesis by simp
next
  case (Nt B)
  from rig Nt have ‹B ∈ set (anchored_nts G)› by (simp add: irigid_def)
  with strackD(5)[OF tr] Nt show ?thesis by fastforce
qed

text ‹The prediction step: a realised dot-0 cursor of a production has a realised
  predecessor among const‹ipreds›, at an earlier round of the same frame.›

lemma strack_predict:
  assumes tr: ‹strack G Shn Xs α pstk› and live: ‹lcore (hd Xs) ≠ {}›
    and cur: ‹icur_at G (hd Xs) t c (pr, 0, σ)› and shn: ‹fst pr ≠ Shn›
  shows ‹∃t' cur'. t' < t ∧ icur_at G (hd Xs) t' c cur' ∧
      cur' ∈ set (ipreds (map (wreach G) (pr0_states G Shn)) (pstk ! 0) (fst pr) σ)›
proof -
  note sh = strackD(1)[OF tr] and mt = strackD(2)[OF tr]
  note lenX = dshapeD(1)[OF sh] and bot = dshapeD(2)[OF sh] and shp = dshapeD(3)[OF sh]
  have Xs_ne: ‹Xs ≠ []› using lenX by auto
  have hd0: ‹hd Xs = Xs ! 0› using Xs_ne by (simp add: hd_conv_nth)
  have z_lt: ‹0 < length Xs› using Xs_ne by auto
  have live0: ‹lcore (Xs ! 0) ≠ {}› using live hd0 by simp
  obtain R j where mem: ‹(pr, 0, R) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t))›
    and jR: ‹j ∈ irep_set R› and wj: ‹wsat σ c j›
    using cur unfolding icur_at_def by auto
  have nokern: ‹(pr, 0, R) ∉ set (hd Xs)›
  proof
    assume kern: ‹(pr, 0, R) ∈ set (hd Xs)›
    show False
    proof (cases α)
      case Nil
      have x0: ‹Xs ! 0 = xinit G Shn› using bot unfolding Nil by simp
      then show ?thesis using kern hd0 shn unfolding Nil xinit_def by auto
    next
      case (Cons e α')
      obtain X0 RA where e: ‹e = (X0, RA)› by (cases e)
      have z_la: ‹0 < length α› unfolding Cons by simp
      have f0: ‹Xs ! 0 = lgoto (xclosure_auto G (Xs ! Suc 0)) X0 RA›
        using shp[OF z_la] unfolding Cons e by simp
      have ‹(pr, 0, R) ∈ set (lgoto (xclosure_auto G (Xs ! Suc 0)) X0 RA)›
        using kern hd0 f0 by simp
      from lgoto_dot_pos[OF this] show False by simp
    qed
  qed
  obtain p where p: ‹p < length (iprods G)› and pr: ‹pr = iprods G ! p›
      and R: ‹R = xiter G (hd Xs) t ! p›
    using mem nokern by (auto elim!: xslots_memE)
  obtain t' pr' m' R' j' where tt: ‹t' < t›
    and mem': ‹(pr', m', R') ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t'))›
    and m': ‹m' < length (snd pr')› and nt: ‹fst (snd pr' ! m') = Nt (fst pr)›
    and j'R: ‹j' ∈ irep_set R'› and rel: ‹irel_sat (snd (snd pr' ! m')) j j'›
    using xiter_pred[OF p jR[unfolded R]] unfolding pr by blast
  obtain ρ where rho: ‹(pr', m', ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0)))›
    using strack_pool_at[OF tr live mem' j'R] by blast
  have idx: ‹pstk ! 0 < length (pr0_states G Shn)›
    using didx_okD[OF mt z_lt live0] by blast
  have rho': ‹(pr', m', ρ) ∈ set (map (wreach G) (pr0_states G Shn) ! (pstk ! 0))›
    using rho idx by simp
  define cur' where ‹cur' = (pr', m', wcomp (w_of (snd (snd pr' ! m'))) σ)›
  have ‹cur' ∈ set (ipreds (map (wreach G) (pr0_states G Shn)) (pstk ! 0) (fst pr) σ)›
    unfolding ipreds_def cur'_def set_remdups
    by (rule map_filterI[OF rho']) (simp add: m' nt)
  moreover have ‹icur_at G (hd Xs) t' c cur'›
    unfolding icur_at_def cur'_def
    using mem' j'R wcomp_sound[OF wj w_of_sound[OF rel]] by auto
  ultimately show ?thesis using tt by blast
qed

text ‹The pop step: two realised kernel cursors have the entry symbol before
  their dots, are not disjoint at a rigid entry, and pop to realised cursors of the
  frame below along an edge of const‹pin_edges›, both items in the lower
  state's closure.›

lemma strack_pop_step:
  assumes tr: ‹strack G Shn Xs α pstk› and live: ‹lcore (hd Xs) ≠ {}›
    and c1: ‹icur_at G (hd Xs) t1 c (pr1, Suc m1, σ1)›
    and c2: ‹icur_at G (hd Xs) t2 c (pr2, Suc m2, σ2)›
  shows ‹∃X0 RA α'. α = (X0, RA) # α' ∧
      fst (snd pr1 ! m1) = X0 ∧ fst (snd pr2 ! m2) = X0 ∧
      (irigid (anchored_nts G) X0 ⟶
         ¬ wdisjoint (itrans (pr1, Suc m1, σ1)) (itrans (pr2, Suc m2, σ2))) ∧
      strack G Shn (tl Xs) α' (tl pstk) ∧ lcore (hd (tl Xs)) ≠ {} ∧
      icur G (hd (tl Xs)) c (pr1, m1, σ1) ∧ icur G (hd (tl Xs)) c (pr2, m2, σ2) ∧
      (pstk ! 1, X0) ∈ set (pin_edges (pgtab G (pr0_states G Shn)) (pstk ! 0)) ∧
      ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr1 m1 ∧
      ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr2 m2›
proof -
  from c1 obtain R1 j1 where
      mem1: ‹(pr1, Suc m1, R1) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t1))›
    and j1: ‹j1 ∈ irep_set R1› and w1: ‹wsat σ1 c j1›
    by (auto simp: icur_at_def)
  from c2 obtain R2 j2 where
      mem2: ‹(pr2, Suc m2, R2) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t2))›
    and j2: ‹j2 ∈ irep_set R2› and w2: ‹wsat σ2 c j2›
    by (auto simp: icur_at_def)
  obtain X0 RA α' R1' l1 where α1: ‹α = (X0, RA) # α'›
    and lt1: ‹m1 < length (snd pr1)› and X1: ‹fst (snd pr1 ! m1) = X0›
    and mem1': ‹(pr1, m1, R1') ∈ set (xclosure_auto G (Xs ! 1))›
    and j1': ‹j1 ∈ irep_set R1'› and l1: ‹l1 ∈ irep_set RA›
    and rel1: ‹irel_sat (snd (snd pr1 ! m1)) l1 j1›
    by (rule strack_pop[OF tr mem1 j1])
  obtain X0' RA' α'' R2' l2 where α2: ‹α = (X0', RA') # α''›
    and lt2: ‹m2 < length (snd pr2)› and X2: ‹fst (snd pr2 ! m2) = X0'›
    and mem2': ‹(pr2, m2, R2') ∈ set (xclosure_auto G (Xs ! 1))›
    and j2': ‹j2 ∈ irep_set R2'› and l2: ‹l2 ∈ irep_set RA'›
    and rel2: ‹irel_sat (snd (snd pr2 ! m2)) l2 j2›
    by (rule strack_pop[OF tr mem2 j2])
  from α1 α2 have eq: ‹X0' = X0› ‹RA' = RA› by simp_all
  have tr1: ‹strack G Shn Xs ((X0, RA) # α') pstk› using tr unfolding α1 .
  have tr': ‹strack G Shn (tl Xs) α' (tl pstk)› using strack_tl[OF tr1] .
  have len: ‹length Xs = length α + 1› using dshapeD(1)[OF strackD(1)[OF tr]] .
  have lenp: ‹length pstk = length Xs› using didx_ok_len[OF strackD(2)[OF tr]] .
  have hdtl: ‹hd (tl Xs) = Xs ! 1› using len α1 by (cases Xs; cases ‹tl Xs›) auto
  have tlp: ‹tl pstk ! 0 = pstk ! 1› using lenp len α1 by (cases pstk) auto
  have rig: ‹irigid (anchored_nts G) X0 ⟹
      ¬ wdisjoint (itrans (pr1, Suc m1, σ1)) (itrans (pr2, Suc m2, σ2))›
  proof -
    assume rg: ‹irigid (anchored_nts G) X0›
    from strack_rigid[OF tr1 rg] obtain col where sub: ‹irep_set RA ⊆ {col}› ..
    with l1 l2 eq have lc: ‹l1 = col› ‹l2 = col› by auto
    have s1: ‹wsat (itrans (pr1, Suc m1, σ1)) c l1›
      using wcomp_sound[OF w1 winv_sound[OF w_of_sound[OF rel1]]] by (simp add: itrans_def)
    have s2: ‹wsat (itrans (pr2, Suc m2, σ2)) c l2›
      using wcomp_sound[OF w2 winv_sound[OF w_of_sound[OF rel2]]] by (simp add: itrans_def)
    show ‹¬ wdisjoint (itrans (pr1, Suc m1, σ1)) (itrans (pr2, Suc m2, σ2))›
      by (rule wdisjoint_sound[where l = col, OF s1[unfolded lc(1)] s2[unfolded lc(2)]])
  qed
  have live': ‹lcore (hd (tl Xs)) ≠ {}›
    unfolding hdtl by (rule closure_live_kernel[OF mem1' j1'])
  have ic1: ‹icur G (hd (tl Xs)) c (pr1, m1, σ1)›
    using mem1' j1' w1 unfolding hdtl icur_def by auto
  have ic2: ‹icur G (hd (tl Xs)) c (pr2, m2, σ2)›
    using mem2' j2' w2 unfolding hdtl icur_def by auto
  have edge1: ‹pstk ! 1 < length (pr0_states G Shn) ∧
      (pstk ! 1, X0) ∈ set (pin_edges (pgtab G (pr0_states G Shn)) (pstk ! 0))›
    using strack_edge[OF tr1 mem1' j1' lt1 X1] .
  have pool: ‹⋀pr m R j. (pr, m, R) ∈ set (xclosure_auto G (Xs ! 1)) ⟹
      j ∈ irep_set R ⟹ ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr m›
  proof -
    fix pr m R j
    assume mm: ‹(pr, m, R) ∈ set (xclosure_auto G (Xs ! 1))› and jj: ‹j ∈ irep_set R›
    from strack_pool[OF tr' live' mm[folded hdtl] jj] obtain ρ where
      ‹(pr, m, ρ) ∈ set (wreach G (pr0_states G Shn ! (tl pstk ! 0)))› by blast
    then have ‹(pr, m, ρ) ∈ set (map (wreach G) (pr0_states G Shn) ! (pstk ! 1))›
      using edge1 tlp by simp
    then show ‹ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr m›
      unfolding ihas_def list_ex_iff by auto
  qed
  have h1: ‹ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr1 m1›
    by (rule pool[OF mem1' j1'])
  have h2: ‹ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr2 m2›
    by (rule pool[OF mem2' j2'])
  show ?thesis
    using α1 X1 X2 eq rig tr' live' ic1 ic2 edge1 h1 h2 by auto
qed

text ‹One step of the descent: a realised triple fires, or has a realised
  successor with fewer frames, or as many frames and fewer rounds.›

lemma strack_step:
  assumes tr: ‹strack G Shn Xs α pstk› and fresh: ‹fresh_name G Shn›
    and live: ‹lcore (hd Xs) ≠ {}›
    and c1: ‹icur_at G (hd Xs) t1 c cur1› and c2: ‹icur_at G (hd Xs) t2 c cur2›
  shows ‹ifires Shn (anchored_nts G) (pstk ! 0, cur1, cur2) ∨
    (∃Xs' α' pstk' t1' t2' cur1' cur2'.
       (pstk' ! 0, cur1', cur2') ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
          (pgtab G (pr0_states G Shn)) (anchored_nts G) (pstk ! 0, cur1, cur2)) ∧
       strack G Shn Xs' α' pstk' ∧ lcore (hd Xs') ≠ {} ∧
       icur_at G (hd Xs') t1' c cur1' ∧ icur_at G (hd Xs') t2' c cur2' ∧
       (length Xs' < length Xs ∨ length Xs' = length Xs ∧ t1' + t2' < t1 + t2))›
proof -
  obtain pr1 m1 σ1 where cur1: ‹cur1 = (pr1, m1, σ1)› by (cases cur1) auto
  obtain pr2 m2 σ2 where cur2: ‹cur2 = (pr2, m2, σ2)› by (cases cur2) auto
  have len: ‹length Xs = length α + 1› using dshapeD(1)[OF strackD(1)[OF tr]] .
  have plen: ‹length pstk = length Xs› using didx_ok_len[OF strackD(2)[OF tr]] .
  have c1': ‹icur_at G (hd Xs) t1 c (pr1, m1, σ1)› using c1 cur1 by simp
  have c2': ‹icur_at G (hd Xs) t2 c (pr2, m2, σ2)› using c2 cur2 by simp
  consider (A) ‹m1 = 0› ‹fst pr1 ≠ Shn›
    | (B) ‹¬ (m1 = 0 ∧ fst pr1 ≠ Shn)› ‹m2 = 0› ‹fst pr2 ≠ Shn›
    | (C) ‹m1 = 0› ‹fst pr1 = Shn› ‹m2 = 0› ‹fst pr2 = Shn›
    | (D1) ‹m1 = 0› ‹fst pr1 = Shn› ‹m2 ≠ 0›
    | (D2) ‹m2 = 0› ‹fst pr2 = Shn› ‹m1 ≠ 0›
    | (E) ‹m1 ≠ 0› ‹m2 ≠ 0›
    by auto
  then show ?thesis
  proof cases
    case A
    have c1z: ‹icur_at G (hd Xs) t1 c (pr1, 0, σ1)› using c1' A(1) by simp
    obtain t' cur' where lt: ‹t' < t1› and ic: ‹icur_at G (hd Xs) t' c cur'›
      and mem: ‹cur' ∈ set (ipreds (map (wreach G) (pr0_states G Shn)) (pstk ! 0)
        (fst pr1) σ1)›
      using strack_predict[OF tr live c1z A(2)] by blast
    have succ: ‹(pstk ! 0, cur', cur2) ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
      (pgtab G (pr0_states G Shn)) (anchored_nts G) (pstk ! 0, cur1, cur2))›
      using mem A by (simp add: cur1 cur2)
    show ?thesis using succ tr live ic c2 lt
      by (intro disjI2 exI[of _ Xs] exI[of _ α] exI[of _ pstk] exI[of _ t'] exI[of _ t2]
          exI[of _ cur'] exI[of _ cur2] conjI) auto
  next
    case B
    have c2z: ‹icur_at G (hd Xs) t2 c (pr2, 0, σ2)› using c2' B(2) by simp
    obtain t' cur' where lt: ‹t' < t2› and ic: ‹icur_at G (hd Xs) t' c cur'›
      and mem: ‹cur' ∈ set (ipreds (map (wreach G) (pr0_states G Shn)) (pstk ! 0)
        (fst pr2) σ2)›
      using strack_predict[OF tr live c2z B(3)] by blast
    have succ: ‹(pstk ! 0, cur1, cur') ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
      (pgtab G (pr0_states G Shn)) (anchored_nts G) (pstk ! 0, cur1, cur2))›
      using mem B by (simp add: cur1 cur2 B(1))
    show ?thesis using succ tr live ic c1 lt
      by (intro disjI2 exI[of _ Xs] exI[of _ α] exI[of _ pstk] exI[of _ t1] exI[of _ t']
          exI[of _ cur1] exI[of _ cur'] conjI) auto
  next
    case C
    have c1z: ‹icur_at G (hd Xs) t1 c (pr1, 0, σ1)› using c1' C(1) by simp
    have c2z: ‹icur_at G (hd Xs) t2 c (pr2, 0, σ2)› using c2' C(3) by simp
    obtain R1 j1 where s1: ‹(pr1, 0, R1) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t1))›
      and j1: ‹j1 ∈ irep_set R1› and w1: ‹wsat σ1 c j1›
      using c1z unfolding icur_at_def by auto
    obtain R2 j2 where s2: ‹(pr2, 0, R2) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t2))›
      and j2: ‹j2 ∈ irep_set R2› and w2: ‹wsat σ2 c j2›
      using c2z unfolding icur_at_def by auto
    have r1: ‹irep_set R1 = {istart_ind G}›
      using strack_start_item[OF tr fresh s1 C(2)] by simp
    have r2: ‹irep_set R2 = {istart_ind G}›
      using strack_start_item[OF tr fresh s2 C(4)] by simp
    have ‹j1 = j2› using j1 j2 r1 r2 by simp
    then have nd: ‹¬ wdisjoint σ1 σ2› using wdisjoint_sound w1 w2 by blast
    show ?thesis using nd by (simp add: cur1 cur2 C)
  next
    case D1
    show ?thesis using D1 by (simp add: cur1 cur2)
  next
    case D2
    show ?thesis using D2 by (simp add: cur1 cur2)
  next
    case E
    obtain m1' where m1: ‹m1 = Suc m1'› using E(1) by (cases m1) auto
    obtain m2' where m2: ‹m2 = Suc m2'› using E(2) by (cases m2) auto
    have c1s: ‹icur_at G (hd Xs) t1 c (pr1, Suc m1', σ1)› using c1' m1 by simp
    have c2s: ‹icur_at G (hd Xs) t2 c (pr2, Suc m2', σ2)› using c2' m2 by simp
    obtain X0 RA α' where al: ‹α = (X0, RA) # α'›
      and x1: ‹fst (snd pr1 ! m1') = X0› and x2: ‹fst (snd pr2 ! m2') = X0›
      and rig: ‹irigid (anchored_nts G) X0 ⟶
        ¬ wdisjoint (itrans (pr1, Suc m1', σ1)) (itrans (pr2, Suc m2', σ2))›
      and tr': ‹strack G Shn (tl Xs) α' (tl pstk)› and live': ‹lcore (hd (tl Xs)) ≠ {}›
      and ic1: ‹icur G (hd (tl Xs)) c (pr1, m1', σ1)›
      and ic2: ‹icur G (hd (tl Xs)) c (pr2, m2', σ2)›
      and edge: ‹(pstk ! 1, X0) ∈ set (pin_edges (pgtab G (pr0_states G Shn)) (pstk ! 0))›
      and h1: ‹ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr1 m1'›
      and h2: ‹ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr2 m2'›
      using strack_pop_step[OF tr live c1s c2s] by blast
    have hlen: ‹length Xs = length α' + 2› using len al by simp
    have nth1: ‹tl pstk ! 0 = pstk ! 1› using plen hlen by (simp add: nth_tl)
    have mf: ‹(pstk ! 1, (pr1, m1', σ1), (pr2, m2', σ2)) ∈ set (List.map_filter
      (λ(p, X'). if X' = X0 ∧ ihas (map (wreach G) (pr0_states G Shn) ! p) pr1 m1'
          ∧ ihas (map (wreach G) (pr0_states G Shn) ! p) pr2 m2'
        then Some (p, (pr1, m1', σ1), (pr2, m2', σ2)) else None)
      (pin_edges (pgtab G (pr0_states G Shn)) (pstk ! 0)))›
      by (rule map_filterI[OF edge])
        (simp add: h1[unfolded One_nat_def] h2[unfolded One_nat_def])
    have succ: ‹(pstk ! 1, (pr1, m1', σ1), (pr2, m2', σ2)) ∈ set (isuccs Shn
      (map (wreach G) (pr0_states G Shn)) (pgtab G (pr0_states G Shn)) (anchored_nts G)
      (pstk ! 0, cur1, cur2))›
      using rig mf by (simp add: cur1 cur2 m1 m2 x1 x2 cong: if_cong)
    have ict1: ‹icur_at G (hd (tl Xs)) (xfuel G (hd (tl Xs))) c (pr1, m1', σ1)›
      using ic1 icur_at_fuel by blast
    have ict2: ‹icur_at G (hd (tl Xs)) (xfuel G (hd (tl Xs))) c (pr2, m2', σ2)›
      using ic2 icur_at_fuel by blast
    have shorter: ‹length (tl Xs) < length Xs› using hlen by simp
    show ?thesis
      using succ[folded nth1] tr' live' ict1 ict2 shorter by blast
  qed
qed

text ‹The descent, by induction on the frames and then on the rounds: from a
  tracked stack whose top frame realises both cursors of a triple, the walk's
  successor relation reaches a triple that fires.›

lemma strack_fires_at:
  ‹∀Xs α pstk t1 t2 cur1 cur2. length Xs = n ⟶ t1 + t2 = k ⟶
     strack G Shn Xs α pstk ⟶ fresh_name G Shn ⟶ lcore (hd Xs) ≠ {} ⟶
     icur_at G (hd Xs) t1 c cur1 ⟶ icur_at G (hd Xs) t2 c cur2 ⟶
     (∃t'. (λt t'. t' ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
          (pgtab G (pr0_states G Shn)) (anchored_nts G) t))** (pstk ! 0, cur1, cur2) t' ∧
        ifires Shn (anchored_nts G) t')›
proof (induction n arbitrary: k rule: less_induct)
  case (less n)
  note IHn = less.IH
  show ?case
  proof (induction k rule: less_induct)
    case (less k)
    note IHk = less.IH
    let ?R = ‹λt t'. t' ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
          (pgtab G (pr0_states G Shn)) (anchored_nts G) t)›
    show ?case
    proof (intro allI impI)
      fix Xs α pstk t1 t2 cur1 cur2
      assume len: ‹length Xs = n› and sum: ‹t1 + t2 = k›
        and tr: ‹strack G Shn Xs α pstk›
        and fresh: ‹fresh_name G Shn› and live: ‹lcore (hd Xs) ≠ {}›
        and c1: ‹icur_at G (hd Xs) t1 c cur1› and c2: ‹icur_at G (hd Xs) t2 c cur2›
      from strack_step[OF tr fresh live c1 c2]
      show ‹∃t'. ?R** (pstk ! 0, cur1, cur2) t' ∧ ifires Shn (anchored_nts G) t'›
      proof
        assume ‹ifires Shn (anchored_nts G) (pstk ! 0, cur1, cur2)›
        then show ?thesis by blast
      next
        assume ‹∃Xs' α' pstk' t1' t2' cur1' cur2'.
          (pstk' ! 0, cur1', cur2') ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
            (pgtab G (pr0_states G Shn)) (anchored_nts G) (pstk ! 0, cur1, cur2)) ∧
          strack G Shn Xs' α' pstk' ∧ lcore (hd Xs') ≠ {} ∧
          icur_at G (hd Xs') t1' c cur1' ∧ icur_at G (hd Xs') t2' c cur2' ∧
          (length Xs' < length Xs ∨ length Xs' = length Xs ∧ t1' + t2' < t1 + t2)›
        then obtain Xs' α' pstk' t1' t2' cur1' cur2'
          where succ: ‹(pstk' ! 0, cur1', cur2') ∈ set (isuccs Shn
              (map (wreach G) (pr0_states G Shn)) (pgtab G (pr0_states G Shn))
              (anchored_nts G) (pstk ! 0, cur1, cur2))›
            and tr': ‹strack G Shn Xs' α' pstk'› and live': ‹lcore (hd Xs') ≠ {}›
            and c1': ‹icur_at G (hd Xs') t1' c cur1'›
            and c2': ‹icur_at G (hd Xs') t2' c cur2'›
            and dec: ‹length Xs' < length Xs ∨
              length Xs' = length Xs ∧ t1' + t2' < t1 + t2›
          by blast
        from dec have ‹∃t'. ?R** (pstk' ! 0, cur1', cur2') t' ∧
            ifires Shn (anchored_nts G) t'›
        proof
          assume lt: ‹length Xs' < length Xs›
          from IHn[of ‹length Xs'› ‹t1' + t2'›] lt len
          show ?thesis using tr' fresh live' c1' c2' by blast
        next
          assume ‹length Xs' = length Xs ∧ t1' + t2' < t1 + t2›
          with IHk[of ‹t1' + t2'›] len sum
          show ?thesis using tr' fresh live' c1' c2' by blast
        qed
        then show ?thesis using succ by (meson converse_rtranclp_into_rtranclp)
      qed
    qed
  qed
qed

theorem strack_fires:
  assumes tr: ‹strack G Shn Xs α pstk›
    and fresh: ‹fresh_name G Shn›
    and live: ‹lcore (hd Xs) ≠ {}›
    and c1: ‹icur G (hd Xs) c cur1› and c2: ‹icur G (hd Xs) c cur2›
  shows ‹∃t'. (λt t'. t' ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
        (pgtab G (pr0_states G Shn)) (anchored_nts G) t))** (pstk ! 0, cur1, cur2) t' ∧
      ifires Shn (anchored_nts G) t'›
  using strack_fires_at[rule_format, OF refl refl tr fresh live] c1 c2
  unfolding icur_at_fuel by blast


section ‹Sufficiency of the item-relative check›

text ‹The final assembly: ‹rlalr_conflicts G Shn = []› plus
  const‹fresh_name› implies const‹mdet›.  A determinism violation
  yields two live candidates at a tracked, live top frame; each candidate's
  runtime license transports to a static seed at the tracked state
  (const‹ireds_at› / const‹ishifts›) that the frame realises
  (const‹icur›), the pair of cursors is in const‹ipairs_at›, the
  empty report makes the walk return ‹False›, and ‹strack_fires› +
  ‹ifire_sound› close the contradiction.  ‹None›/‹None› pairs are
  refuted by const‹rr_none_at› directly; a reduce of the fresh start
  name cannot have a live successor.›

text ‹Membership constructors for the static seeds.›

lemma ireds_at_memI:
  assumes cell: ‹(i, (pr, length (snd pr)), t, τ) ∈ set L›
    and shn: ‹fst pr ≠ Shn›
    and wmem: ‹(pr, length (snd pr), ρ) ∈ set (wreach G (sp ! i))›
  shows ‹(t, (pr, length (snd pr), τ)) ∈ set (ireds_at G Shn sp L i)›
  unfolding ireds_at_def Let_def
  by (rule map_filterI[OF cell]) (use shn wmem in ‹auto simp: list_ex_iff›)

lemma ishifts_memI:
  assumes ‹(pr, m, ρ) ∈ set ws› and ‹m < length (snd pr)›
    and ‹fst (snd pr ! m) = Tm a›
  shows ‹(a, (pr, m, w_of (snd (snd pr ! m)))) ∈ set (ishifts ws)›
  unfolding ishifts_def set_remdups
  by (rule map_filterI[OF assms(1)]) (use assms(2,3) in simp)

lemma ipairs_at_srI:
  assumes red: ‹(Some a, c) ∈ set (ireds_at G Shn sp L i)›
    and sh: ‹(a, c') ∈ set (ishifts (wreach G (sp ! i)))›
  shows ‹(c, c') ∈ set (ipairs_at G Shn sp L i)›
proof -
  have ‹(c, c') ∈ set (concat (map (λ(t, c). case t of
        Some a ⇒ map (λ(a', c'). (c, c'))
            (filter (λ(a', c'). a' = a) (ishifts (wreach G (sp ! i))))
      | None ⇒ []) (ireds_at G Shn sp L i)))›
    by (rule concat_map_memI[OF red]) (use sh in force)
  then show ?thesis unfolding ipairs_at_def Let_def by simp
qed

lemma ipairs_at_rrI:
  assumes r1: ‹(Some a, (pr1, m1, τ1)) ∈ set (ireds_at G Shn sp L i)›
    and r2: ‹(Some a, (pr2, m2, τ2)) ∈ set (ireds_at G Shn sp L i)›
    and ne: ‹pr2 ≠ pr1›
  shows ‹((pr1, m1, τ1), (pr2, m2, τ2)) ∈ set (ipairs_at G Shn sp L i)›
proof -
  have inner: ‹((pr1, m1, τ1), (pr2, m2, τ2)) ∈ set (List.map_filter (λ(t', c').
      if fst c' ≠ fst (pr1, m1, τ1) ∧ t' = Some a ∧ Some a ≠ None
      then Some ((pr1, m1, τ1), c') else None)
      (ireds_at G Shn sp L i))›
    by (rule map_filterI[OF r2]) (use ne in simp)
  have ‹((pr1, m1, τ1), (pr2, m2, τ2)) ∈ set (concat (map (λ(t, c).
        List.map_filter (λ(t', c').
          if fst c' ≠ fst c ∧ t' = t ∧ t ≠ None then Some (c, c') else None)
          (ireds_at G Shn sp L i)) (ireds_at G Shn sp L i)))›
    by (rule concat_map_memI[OF r1]) (use inner in simp)
  then show ?thesis unfolding ipairs_at_def Let_def by simp
qed

lemma rr_none_atI:
  assumes r1: ‹(None, (pr1, m1, τ1)) ∈ set (ireds_at G Shn sp L i)›
    and r2: ‹(None, (pr2, m2, τ2)) ∈ set (ireds_at G Shn sp L i)›
    and ne: ‹pr2 ≠ pr1›
  shows ‹rr_none_at G Shn sp L i›
proof -
  have inner: ‹list_ex (λ(t', c'). fst c' ≠ fst (pr1, m1, τ1) ∧ t' = None)
      (ireds_at G Shn sp L i)›
    unfolding list_ex_iff by (rule bexI[OF _ r2]) (use ne in simp)
  have outer: ‹list_ex (λ(t, c). t = None ∧
      list_ex (λ(t', c'). fst c' ≠ fst c ∧ t' = None)
        (ireds_at G Shn sp L i)) (ireds_at G Shn sp L i)›
    unfolding list_ex_iff
    by (rule bexI[OF _ r1]) (use inner in ‹fastforce simp: list_ex_iff›)
  show ?thesis unfolding rr_none_at_def Let_def using outer by simp
qed

lemma dcands_shift_or_reduce:
  assumes ‹a ∈ set (dcands G i cells CL (Xs, w))›
  shows ‹a = DShift ∧ w ≠ [] ∨ (∃pr. a = DReduce pr ∧
      irep_nonempty (red_set CL pr) ∧ dlic i cells w pr (red_set CL pr))›
  using assms unfolding dcands_def
  by (auto simp: Let_def split: if_splits list.splits)

text ‹A reduce of the fresh start name has no live successor: the goto
  frame's kernel items would need ‹Nt Shn› at a dot of the exposed frame's
  closure, but ‹Shn› occurs in no grammar symbol.›

lemma shn_reduce_dead:
  assumes tr: ‹strack G Shn Xs α pstk›
    and fresh: ‹fresh_name G Shn›
    and step: ‹mstep G (Xs, w) (DReduce pr) = Some gc'›
    and shn: ‹fst pr = Shn›
    and lv: ‹dlive gc'›
  shows False
proof -
  note mt = strackD(2)[OF tr]
  have step': ‹mstep_cached G (map (xclosure_auto G) Xs) (Xs, w) (DReduce pr) = Some gc'›
    using step unfolding mstep_def by simp
  define d where ‹d = length (snd pr)›
  have d_lt: ‹d < length Xs›
    unfolding d_def by (rule mstep_reduce_shape[OF step']) blast
  have gc': ‹gc' = (lgoto (map (xclosure_auto G) Xs ! d) (Nt (fst pr))
        (red_set (hd (map (xclosure_auto G) Xs)) pr) # drop d Xs, w)›
    unfolding d_def by (rule mstep_reduce_shape[OF step']) blast
  have lvt: ‹dlive (lgoto (xclosure_auto G (Xs ! d)) (Nt Shn)
      (red_set (hd (map (xclosure_auto G) Xs)) pr) # drop d Xs, w)›
    using lv unfolding gc' shn using d_lt by simp
  from lvt obtain pr1 m1 R1 j1 where
    itm0: ‹(pr1, m1, R1) ∈ set (hd (lgoto (xclosure_auto G (Xs ! d)) (Nt Shn)
        (red_set (hd (map (xclosure_auto G) Xs)) pr) # drop d Xs))›
    and jR1: ‹j1 ∈ irep_set R1›
    by (blast elim: dliveE)
  have itm: ‹(pr1, m1, R1) ∈ set (lgoto (xclosure_auto G (Xs ! d)) (Nt Shn)
      (red_set (hd (map (xclosure_auto G) Xs)) pr))›
    using itm0 by simp
  obtain m0 where m1: ‹m1 = Suc m0›
    using lgoto_dot_pos[OF itm] by (cases m1) auto
  from lgoto_kernel_step[OF itm[unfolded m1]] obtain Rs where
    src: ‹(pr1, m0, Rs) ∈ set (xclosure_auto G (Xs ! d))›
    and m0lt: ‹m0 < length (snd pr1)›
    and dsym: ‹fst (snd pr1 ! m0) = Nt Shn›
    and Req: ‹R1 = irep_inter Rs (irep_pre (snd (snd pr1 ! m0))
        (red_set (hd (map (xclosure_auto G) Xs)) pr))› .
  have jRs: ‹j1 ∈ irep_set Rs› using jR1 unfolding Req by simp
  have lived: ‹lcore (Xs ! d) ≠ {}› by (rule closure_live_kernel[OF src jRs])
  have pd_lt: ‹pstk ! d < length (pr0_states G Shn)›
    and coverd: ‹lcore (Xs ! d) ⊆ set (pr0_states G Shn ! (pstk ! d))›
    using didx_okD[OF mt d_lt lived] by blast+
  have kernD: ‹⋀pr' m' R'. (pr', m', R') ∈ set (Xs ! d) ⟹
      irep_nonempty R' ⟹ (pr', m') ∈ set (pr0_states G Shn ! (pstk ! d))›
    by (blast intro: lcore_subD_ne[OF coverd])
  have srcC: ‹(pr1, m0) ∈ set (creach G (pr0_states G Shn ! (pstk ! d)))›
    by (rule xclosure_auto_live_creach[OF kernD src jRs])
  have crU: ‹set (creach G (pr0_states G Shn ! (pstk ! d))) ⊆ cuniv G Shn›
    by (rule creach_univ[OF pr0_states_univ[OF nth_mem[OF pd_lt]]])
  have ‹fst (snd pr1 ! m0) ∈ set (gram_syms G)›
    by (rule dot_sym_gram[OF crU srcC m0lt])
  then have inG: ‹Nt Shn ∈ set (gram_syms G)› unfolding dsym .
  have ‹Nt Shn ∉ set (gram_syms G)›
  proof
    assume mem: ‹Nt Shn ∈ set (gram_syms G)›
    show False
    proof (cases ‹Nt Shn = Nt (istart G)›)
      case True
      then show False using fresh unfolding fresh_name_def by simp
    next
      case False
      have inL: ‹Nt Shn ∈ set (concat (map (λ(A, y). map fst y) (iprods G)))›
        using mem False unfolding gram_syms_def by (auto split: if_splits)
      from inL obtain A rhs where pmem: ‹(A, rhs) ∈ set (iprods G)›
        and inrhs: ‹Nt Shn ∈ set (map fst rhs)› by fastforce
      from inrhs obtain e where emem: ‹e ∈ set rhs›
        and efst: ‹fst e = Nt Shn› by auto
      obtain X r where eeq: ‹e = (X, r)› by (cases e)
      have ball2: ‹∀(X', r') ∈ set rhs. X' ≠ Nt Shn›
        using fresh pmem unfolding fresh_name_def by fastforce
      have ‹X ≠ Nt Shn› using ball2 emem unfolding eeq by fastforce
      then show False using efst eeq by simp
    qed
  qed
  then show False using inG by simp
qed

text ‹Each runtime license transports to a static seed at the tracked
  state: the driver's reduce cell is a cell of const‹la_fix› at the
  top frame's index, the item it licenses is in the top frame's closure with
  an indentation the cell's relation holds at (const‹icur›), and
  text‹strack_pool› places the item in the state's const‹wreach›.›

lemma reduce_seed_Some:
  assumes tr: ‹strack G Shn Xs α pstk›
    and live: ‹lcore (hd Xs) ≠ {}›
    and ne: ‹Xs ≠ []›
    and lic: ‹dlic (pstk ! 0) (red_buckets G Shn (length (pr0_states G Shn)) ! (pstk ! 0))
        ((a, c) # w') pr (red_set (xclosure_auto G (hd Xs)) pr)›
    and shn: ‹fst pr ≠ Shn›
  shows ‹∃τ. (Some a, (pr, length (snd pr), τ)) ∈ set (ireds_at G Shn (pr0_states G Shn)
          (la_fix G Shn) (pstk ! 0)) ∧
        icur G (hd Xs) c (pr, length (snd pr), τ)›
proof -
  note mt = strackD(2)[OF tr]
  have z_lt: ‹0 < length Xs› using ne by auto
  have hd0: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
  have i_lt: ‹pstk ! 0 < length (pr0_states G Shn)›
    using didx_okD[OF mt z_lt] live unfolding hd0 by blast
  from dlicE[OF lic] obtain τ where
    cellb: ‹(pstk ! 0, (pr, length (snd pr)), Some a, τ)
        ∈ set (red_buckets G Shn (length (pr0_states G Shn)) ! (pstk ! 0))›
    and sat: ‹irep_ex_wsat τ c (red_set (xclosure_auto G (hd Xs)) pr)› .
  have cell: ‹(pstk ! 0, (pr, length (snd pr)), Some a, τ) ∈ set (la_fix G Shn)›
    using red_buckets_memD[OF i_lt cellb] by blast
  from sat obtain jr where
    jr: ‹jr ∈ irep_set (red_set (xclosure_auto G (hd Xs)) pr)›
    and wt: ‹wsat τ c jr›
    unfolding irep_ex_wsat_correct by blast
  from jr obtain Rr where
    mem: ‹(pr, length (snd pr), Rr) ∈ set (xclosure_auto G (hd Xs))›
    and jrR: ‹jr ∈ irep_set Rr›
    unfolding red_set_correct by blast
  from strack_pool[OF tr live mem jrR] obtain ρ where
    wr: ‹(pr, length (snd pr), ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0)))›
    by blast
  have ‹icur G (hd Xs) c (pr, length (snd pr), τ)›
    unfolding icur_def using mem jrR wt by auto
  then show ?thesis using ireds_at_memI[OF cell shn wr] by blast
qed

lemma reduce_seed_None:
  assumes tr: ‹strack G Shn Xs α pstk›
    and live: ‹lcore (hd Xs) ≠ {}›
    and ne: ‹Xs ≠ []›
    and lic: ‹dlic (pstk ! 0) (red_buckets G Shn (length (pr0_states G Shn)) ! (pstk ! 0))
        [] pr (red_set (xclosure_auto G (hd Xs)) pr)›
    and nonvac: ‹irep_nonempty (red_set (xclosure_auto G (hd Xs)) pr)›
    and shn: ‹fst pr ≠ Shn›
  shows ‹∃τ. (None, (pr, length (snd pr), τ)) ∈ set (ireds_at G Shn (pr0_states G Shn)
          (la_fix G Shn) (pstk ! 0))›
proof -
  note mt = strackD(2)[OF tr]
  have z_lt: ‹0 < length Xs› using ne by auto
  have hd0: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
  have i_lt: ‹pstk ! 0 < length (pr0_states G Shn)›
    using didx_okD[OF mt z_lt] live unfolding hd0 by blast
  from dlic_NilE[OF lic] obtain τ where
    cellb: ‹(pstk ! 0, (pr, length (snd pr)), None, τ)
        ∈ set (red_buckets G Shn (length (pr0_states G Shn)) ! (pstk ! 0))› .
  have cell: ‹(pstk ! 0, (pr, length (snd pr)), None, τ) ∈ set (la_fix G Shn)›
    using red_buckets_memD[OF i_lt cellb] by blast
  obtain jr where jr: ‹jr ∈ irep_set (red_set (xclosure_auto G (hd Xs)) pr)›
    using nonvac unfolding irep_nonempty_correct by blast
  from jr obtain Rr where
    mem: ‹(pr, length (snd pr), Rr) ∈ set (xclosure_auto G (hd Xs))›
    and jrR: ‹jr ∈ irep_set Rr›
    unfolding red_set_correct by blast
  from strack_pool[OF tr live mem jrR] obtain ρ where
    wr: ‹(pr, length (snd pr), ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0)))›
    by blast
  show ?thesis using ireds_at_memI[OF cell shn wr] by blast
qed

lemma shift_seed:
  assumes tr: ‹strack G Shn Xs α pstk›
    and ne: ‹Xs ≠ []›
    and step: ‹mstep G (Xs, w) DShift = Some gc'›
    and lv: ‹dlive gc'›
  shows ‹∃a c w' cs. w = (a, c) # w' ∧
      (a, cs) ∈ set (ishifts (wreach G (pr0_states G Shn ! (pstk ! 0)))) ∧
      icur G (hd Xs) c cs›
proof -
  have step': ‹mstep_cached G (map (xclosure_auto G) Xs) (Xs, w) DShift = Some gc'›
    using step unfolding mstep_def by simp
  from shift_live_srcE[OF step' lv] obtain a c w' pr m R j where
    w: ‹w = (a, c) # w'›
    and src0: ‹(pr, m, R) ∈ set (hd (map (xclosure_auto G) Xs))›
    and m_lt: ‹m < length (snd pr)›
    and sym: ‹fst (snd pr ! m) = Tm a›
    and jR: ‹j ∈ irep_set R›
    and rel: ‹irel_sat (snd (snd pr ! m)) c j› .
  have src: ‹(pr, m, R) ∈ set (xclosure_auto G (hd Xs))›
    using src0 ne by (simp add: hd_map)
  have live0: ‹lcore (hd Xs) ≠ {}› by (rule closure_live_kernel[OF src jR])
  from strack_pool[OF tr live0 src jR] obtain ρ where
    wr: ‹(pr, m, ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0)))› by blast
  have memS: ‹(a, (pr, m, w_of (snd (snd pr ! m)))) ∈
      set (ishifts (wreach G (pr0_states G Shn ! (pstk ! 0))))›
    by (rule ishifts_memI[OF wr m_lt sym])
  have ‹icur G (hd Xs) c (pr, m, w_of (snd (snd pr ! m)))›
    unfolding icur_def using src jR w_of_sound[OF rel] by auto
  then show ?thesis using w memS by blast
qed

text ‹The sufficiency theorem: an empty report makes the pooled machine
  deterministic.  Cf.\ Barthwal cite‹‹Thm.~5.4.4› in "barthwal2010-thesis-cfl-hol4"› (conflict freedom on
  reachable states suffices) and Jourdan et al. cite‹‹Sect.~3.3› in "jourdan2012-validating-lr1"› (the
  completeness validator); the item-relative walk replaces their single-anchor comparison,
  which the test grammar ‹xag› refutes for the pooled machine.  The index
  the driver consulted is the top of the tracked stack, so the check at that
  one index covers both candidates.›


theorem rlalr_sufficient:
  assumes chk: ‹rlalr_conflicts G Shn = []› and fresh: ‹fresh_name G Shn›
  shows ‹mdet G Shn›
  unfolding mdet_def
proof (intro allI impI)
  fix gc istk i redtab CL a1 a2 gc1 gc2
  assume reach: ‹imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn) (gc, istk)›
    and idef: ‹i = hd istk›
    and rdef: ‹redtab = red_buckets G Shn (length (pr0_states G Shn)) ! i›
    and cldef: ‹CL = xclosure_auto G (hd (fst gc))›
    and c1: ‹a1 ∈ set (dcands G i redtab CL gc)›
    and c2: ‹a2 ∈ set (dcands G i redtab CL gc)›
    and ne12: ‹a1 ≠ a2›
    and s1: ‹mstep G gc a1 = Some gc1› and s2: ‹mstep G gc a2 = Some gc2›
    and lv1: ‹dlive gc1› and lv2: ‹dlive gc2›
  obtain Xs w where gc: ‹gc = (Xs, w)› by (cases gc)
  have ne: ‹Xs ≠ []› and live0: ‹lcore (hd Xs) ≠ {}›
    using imreach_dlive[OF reach] unfolding gc dlive_def by (simp_all add: live_lcore)
  have clX: ‹CL = xclosure_auto G (hd Xs)› using cldef unfolding gc by simp
  from imreach_strack[OF reach fresh] obtain α where
    tr: ‹strack G Shn Xs α istk› unfolding gc by auto
  note mt = strackD(2)[OF tr]
  have z_lt: ‹0 < length Xs› using ne by auto
  have hd0: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
  have istk_ne: ‹istk ≠ []› using didx_ok_len[OF mt] ne by auto
  have hdi: ‹hd istk = istk ! 0› using istk_ne by (simp add: hd_conv_nth)
  have i_lt: ‹istk ! 0 < length (pr0_states G Shn)›
    using didx_okD[OF mt z_lt] live0 unfolding hd0 by blast
  have cs1: ‹a1 = DShift ∧ w ≠ [] ∨ (∃pr. a1 = DReduce pr ∧
      irep_nonempty (red_set CL pr) ∧ dlic i redtab w pr (red_set CL pr))›
    using dcands_shift_or_reduce c1 unfolding gc by blast
  have cs2: ‹a2 = DShift ∧ w ≠ [] ∨ (∃pr. a2 = DReduce pr ∧
      irep_nonempty (red_set CL pr) ∧ dlic i redtab w pr (red_set CL pr))›
    using dcands_shift_or_reduce c2 unfolding gc by blast
  have nc: ‹¬ rlalr_conflict_at G Shn (pr0_states G Shn) (la_fix G Shn) (istk ! 0)›
  proof
    assume ‹rlalr_conflict_at G Shn (pr0_states G Shn) (la_fix G Shn) (istk ! 0)›
    then have ‹istk ! 0 ∈ set (rlalr_conflicts G Shn)›
      unfolding rlalr_conflicts_def Let_def using i_lt by simp
    then show False using chk by simp
  qed
  have no_none: ‹¬ rr_none_at G Shn (pr0_states G Shn) (la_fix G Shn) (istk ! 0)›
    using nc unfolding rlalr_conflict_at_def by (auto simp: list_ex_iff)
  have walkF: ‹⋀c1 c2. (c1, c2) ∈ set (ipairs_at G Shn (pr0_states G Shn)
        (la_fix G Shn) (istk ! 0)) ⟹
      ifire Shn (map (wreach G) (pr0_states G Shn)) (pgtab G (pr0_states G Shn))
        (anchored_nts G) (ifuel (map (wreach G) (pr0_states G Shn)))
        [] [(istk ! 0, c1, c2)] = False›
    using nc unfolding rlalr_conflict_at_def
    by (auto simp: list_ex_iff simp del: ifire.simps ifire_Cons)
  have kill: False if ‹(c1, c2) ∈ set (ipairs_at G Shn (pr0_states G Shn) (la_fix G Shn) (istk ! 0))›
      ‹icur G (hd Xs) c c1› ‹icur G (hd Xs) c c2› for c c1 c2
  proof -
    from strack_fires[OF tr fresh live0 that(2,3)] obtain t' where
      ‹(λt t'. t' ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
          (pgtab G (pr0_states G Shn)) (anchored_nts G) t))** (istk ! 0, c1, c2) t'›
      and ‹ifires Shn (anchored_nts G) t'› by blast
    with ifire_sound[OF walkF[OF that(1)]] show False by simp
  qed
  have sr_case: False if ss: ‹mstep G gc DShift = Some gcs› ‹dlive gcs›
      and sr: ‹mstep G gc (DReduce pr) = Some gcr› ‹dlive gcr›
      and lic: ‹dlic i redtab w pr (red_set CL pr)› for gcs gcr pr
  proof -
    from shift_seed[OF tr ne ss(1)[unfolded gc] ss(2)] obtain a c w' cs where
      w: ‹w = (a, c) # w'›
      and shm: ‹(a, cs) ∈ set (ishifts (wreach G (pr0_states G Shn ! (istk ! 0))))›
      and ics: ‹icur G (hd Xs) c cs› by blast
    have ‹fst pr ≠ Shn› using shn_reduce_dead[OF tr fresh sr(1)[unfolded gc] _ sr(2)] by blast
    moreover have ‹dlic (istk ! 0) (red_buckets G Shn (length (pr0_states G Shn)) ! (istk ! 0))
        ((a, c) # w') pr (red_set (xclosure_auto G (hd Xs)) pr)›
      using lic unfolding idef rdef clX w hdi by simp
    ultimately obtain τ where
        rdm: ‹(Some a, (pr, length (snd pr), τ)) ∈ set (ireds_at G Shn (pr0_states G Shn)
            (la_fix G Shn) (istk ! 0))›
        and icr: ‹icur G (hd Xs) c (pr, length (snd pr), τ)›
      using reduce_seed_Some[OF tr live0 ne] by blast
    show False by (rule kill[OF ipairs_at_srI[OF rdm shm] icr ics])
  qed
  consider
      (SS) ‹a1 = DShift› and ‹a2 = DShift›
    | (SR) pr2 where ‹a1 = DShift› ‹a2 = DReduce pr2›
        ‹irep_nonempty (red_set CL pr2)› ‹dlic i redtab w pr2 (red_set CL pr2)›
    | (RS) pr1 where ‹a2 = DShift› ‹a1 = DReduce pr1›
        ‹irep_nonempty (red_set CL pr1)› ‹dlic i redtab w pr1 (red_set CL pr1)›
    | (RR) pr1 pr2 where ‹a1 = DReduce pr1› ‹a2 = DReduce pr2›
        ‹irep_nonempty (red_set CL pr1)› ‹dlic i redtab w pr1 (red_set CL pr1)›
        ‹irep_nonempty (red_set CL pr2)› ‹dlic i redtab w pr2 (red_set CL pr2)›
    using cs1 cs2 by blast
  then show False
  proof cases
    case SS
    then show False using ne12 by simp
  next
    case (SR pr2)
    show False by (rule sr_case[OF s1[unfolded SR(1)] lv1 s2[unfolded SR(2)] lv2 SR(4)])
  next
    case (RS pr1)
    show False by (rule sr_case[OF s2[unfolded RS(1)] lv2 s1[unfolded RS(2)] lv1 RS(4)])
  next
    case (RR pr1 pr2)
    let ?R = ‹ireds_at G Shn (pr0_states G Shn) (la_fix G Shn) (istk ! 0)›
    have prne: ‹pr2 ≠ pr1› using ne12 unfolding RR(1) RR(2) by auto
    have shn1: ‹fst pr1 ≠ Shn› using shn_reduce_dead[OF tr fresh s1[unfolded gc RR(1)] _ lv1] by blast
    have shn2: ‹fst pr2 ≠ Shn› using shn_reduce_dead[OF tr fresh s2[unfolded gc RR(2)] _ lv2] by blast
    have lic1: ‹dlic (istk ! 0) (red_buckets G Shn (length (pr0_states G Shn)) ! (istk ! 0))
        w pr1 (red_set (xclosure_auto G (hd Xs)) pr1)›
      and lic2: ‹dlic (istk ! 0) (red_buckets G Shn (length (pr0_states G Shn)) ! (istk ! 0))
        w pr2 (red_set (xclosure_auto G (hd Xs)) pr2)›
      using RR(4,6) unfolding idef rdef clX hdi by simp_all
    show False
    proof (cases w)
      case Nil
      from reduce_seed_None[OF tr live0 ne lic1[unfolded Nil] RR(3)[unfolded clX] shn1]
        reduce_seed_None[OF tr live0 ne lic2[unfolded Nil] RR(5)[unfolded clX] shn2]
      obtain τ1 τ2 where ‹(None, (pr1, length (snd pr1), τ1)) ∈ set ?R›
        ‹(None, (pr2, length (snd pr2), τ2)) ∈ set ?R› by blast
      then have ‹rr_none_at G Shn (pr0_states G Shn) (la_fix G Shn) (istk ! 0)›
        using prne by (rule rr_none_atI)
      with no_none show False by simp
    next
      case (Cons ac w')
      then obtain a c where w: ‹w = (a, c) # w'› by (cases ac) simp
      from reduce_seed_Some[OF tr live0 ne lic1[unfolded w] shn1] obtain τ1 where
        m1: ‹(Some a, (pr1, length (snd pr1), τ1)) ∈ set ?R›
        and ic1: ‹icur G (hd Xs) c (pr1, length (snd pr1), τ1)› by blast
      from reduce_seed_Some[OF tr live0 ne lic2[unfolded w] shn2] obtain τ2 where
        m2: ‹(Some a, (pr2, length (snd pr2), τ2)) ∈ set ?R›
        and ic2: ‹icur G (hd Xs) c (pr2, length (snd pr2), τ2)› by blast
      show False by (rule kill[OF ipairs_at_rrI[OF m1 m2 prne] ic1 ic2])
    qed
  qed
qed

section ‹Executable packaging: the automaton computed once›

text ‹The checks above are written for reading: each one names the
  automaton, the goto tables and the saturated cell table it needs, and the
  evaluator recomputes every one of them at every occurrence. At the size of
  a real grammar that dominates the cost of the text‹parser›
  command, so this section restates them against precomputed arguments, in
  the manner of const‹la_fix_gen›, and proves the restatements
  equal to the originals. Nothing changes meaning: the ‹_gen›
  forms are definitions and every bridge below is a theorem.

  const‹rlalr_conflict_at› is the worst offender - it names
  const‹pgtab›, const‹anchored_nts›, the states' const‹wreach›
  lists and const‹ifuel› under the const‹list_ex›, so they are
  rebuilt once per candidate pair of every state.  The restatement reads the
  state's closure from the shared list, so it agrees with the original on the
  states of the automaton only, which is all const‹rlalr_conflicts›
  asks about.›

definition ireds_gen :: ‹'n ⇒ ('n, 't) witem list ⇒ ('n, 't) lacell list ⇒ nat ⇒
    ('t option × ('n, 't) witem) list› where
  ‹ireds_gen Shn ws L i =
     List.map_filter (λ(i', (pr, m), t, τ).
       if i' = i ∧ m = length (snd pr) ∧ fst pr ≠ Shn ∧
          list_ex (λ(pr', m', ρ). pr' = pr ∧ m' = m) ws
       then Some (t, (pr, m, τ)) else None) L›

lemma ireds_at_gen:
  ‹ireds_at G Shn sp L i = ireds_gen Shn (wreach G (sp ! i)) L i›
  by (simp add: ireds_at_def ireds_gen_def Let_def)

definition rr_none_gen :: ‹('t option × ('n, 't) witem) list ⇒ bool› where
  ‹rr_none_gen reds =
     list_ex (λ(t, c). t = None ∧
       list_ex (λ(t', c'). fst c' ≠ fst c ∧ t' = None) reds) reds›

lemma rr_none_at_gen:
  ‹rr_none_at G Shn sp L i = rr_none_gen (ireds_at G Shn sp L i)›
  by (simp add: rr_none_at_def rr_none_gen_def Let_def)

definition ipairs_gen :: ‹('n, 't) witem list ⇒ ('t option × ('n, 't) witem) list ⇒
    (('n, 't) witem × ('n, 't) witem) list› where
  ‹ipairs_gen ws reds =
     (let shifts = ishifts ws;
          srs = concat (map (λ(t, c). case t of
              Some a ⇒ map (λ(a', c'). (c, c')) (filter (λ(a', c'). a' = a) shifts)
            | None ⇒ []) reds);
          rrs = concat (map (λ(t, c). List.map_filter (λ(t', c').
                 if fst c' ≠ fst c ∧ t' = t ∧ t ≠ None then Some (c, c') else None) reds)
                 reds)
      in remdups (srs @ rrs))›

lemma ipairs_at_gen:
  ‹ipairs_at G Shn sp L i = ipairs_gen (wreach G (sp ! i)) (ireds_at G Shn sp L i)›
  by (simp add: ipairs_at_def ipairs_gen_def Let_def)

definition rlalr_conflict_at_gen :: ‹'n ⇒ ('n, 't) witem list list ⇒
    (('n, 't) sym × nat) list list ⇒ 'n list ⇒ nat ⇒ ('n, 't) lacell list ⇒
    nat ⇒ bool› where
  ‹rlalr_conflict_at_gen Shn wrs gp ants fuel L i ⟷
     (let ws = wrs ! i; reds = ireds_gen Shn ws L i
      in rr_none_gen reds ∨
         list_ex (λ(c1, c2). ifire Shn wrs gp ants fuel [] [(i, c1, c2)])
           (ipairs_gen ws reds))›

lemma rlalr_conflict_at_pointwise:
  assumes ‹i < length sp›
  shows ‹rlalr_conflict_at G Shn sp L i =
     rlalr_conflict_at_gen Shn (map (wreach G) sp) (pgtab G sp) (anchored_nts G)
       (ifuel (map (wreach G) sp)) L i›
  using assms by (simp add: rlalr_conflict_at_def rlalr_conflict_at_gen_def Let_def
        ireds_at_gen rr_none_at_gen ipairs_at_gen)

lemma rlalr_conflicts_code [code]:
  ‹rlalr_conflicts G Shn =
     (let sp = pr0_states G Shn; gp = pgtab G sp; L = la_fix_gen G Shn gp sp;
          wrs = map (wreach G) sp
      in filter (rlalr_conflict_at_gen Shn wrs gp (anchored_nts G) (ifuel wrs) L)
           [0..<length sp])›
  unfolding rlalr_conflicts_def la_fix_def Let_def
  by (rule filter_cong[OF refl]) (simp add: rlalr_conflict_at_pointwise)

lemma acc_conflicts_code [code]:
  ‹acc_conflicts G Shn =
     (let sts = pr0_states G Shn; L = la_fix_gen G Shn (pgtab G sts) sts;
          p0 = start_prod G Shn
      in filter (λi. (p0, Suc 0) ∈ set (sts ! i) ∧
           list_ex (λ(i', (pr, m), t, τ). i' = i ∧ m = length (snd pr) ∧
                     t = None ∧ pr ≠ p0) L)
          [0..<length sts])›
  by (simp add: acc_conflicts_def la_fix_def Let_def)

text ‹The bundle the text‹parser› command evaluates: the six
  tables its parse body is specialised to, followed by the two conflict
  reports it discharges text‹mdet› and the accept/reduce premise
  with. Sharing across the eight components is the point - the automaton,
  its goto table and the saturated cell table are each built once for all
  of them.›

definition lr_tables :: ‹('n, 't) is_cfg ⇒ 'n ⇒
    ('n, 't) citem list list × (('n, 't) sym × nat) list list ×
    ('n, 't) lacell list list × ('n, 't) xitem list × ('n, 't) xitem list ×
    nat × nat list × nat list› where
  ‹lr_tables G Shn =
     (let sp = pr0_states G Shn; gp = pgtab G sp; L = la_fix_gen G Shn gp sp;
          ants = anchored_nts G; wrs = map (wreach G) sp; fuel = ifuel wrs;
          s0 = start_prod G Shn; xi = xinit G Shn
      in (sp, gp, cell_buckets L (length sp), xi, xclosure_auto G xi,
          st_find sp (lr0_start G Shn),
          filter (rlalr_conflict_at_gen Shn wrs gp ants fuel L) [0..<length sp],
          filter (λi. (s0, Suc 0) ∈ set (sp ! i) ∧
                    list_ex (λ(i', (pr, m), t, τ). i' = i ∧ m = length (snd pr) ∧
                              t = None ∧ pr ≠ s0) L)
            [0..<length sp]))›

theorem lr_tables_eq:
  ‹lr_tables G Shn =
     (pr0_states G Shn,
      pgtab G (pr0_states G Shn),
      red_buckets G Shn (length (pr0_states G Shn)),
      xinit G Shn,
      xclosure_auto G (xinit G Shn),
      st_find (pr0_states G Shn) (lr0_start G Shn),
      rlalr_conflicts G Shn,
      acc_conflicts G Shn)›
  by (simp add: lr_tables_def red_buckets_def la_fix_def rlalr_conflicts_code
        acc_conflicts_code Let_def)

end