Theory LR_Vec

(* Author: Basil Fürer *)

theory LR_Vec
  imports LR_Sparse
begin

section ‹A state-indexed driver with precomputed closures›

text ‹The set-anchored drivers of text‹LR_Driver› and text‹LR_Sparse› compute a
  closure after every step as a fixpoint over the kernel's anchor sets.  The
  closure's ∗‹shape› is a property of the LR(0) state alone: which productions
  get a slot, and from which kernel item each slot's anchors descend, through
  which chain of right-hand-side relations.  This follows Adams
  cite‹‹Sect.~5.8› in "adams2013"›: only the items before the closure keep
  indentation sets, and the closure items carry the relation that leads to
  them.  Only the anchor sets are
  input-dependent, and a chain of relations acts on an anchor set as one of three
  transfers: the identity (const‹Eq›), the up-set from the least anchor plus an
  offset (const‹Gt›, const‹Ge›), or the up-set from a constant
  (const‹Any›).  The driver of this theory tabulates, per state, its items,
  the transfer from each kernel item to each slot, the predecessor of each
  kernel item under each symbol, and its reduce cells, so that a step does no
  search: it indexes.

  The driver returns what const‹dparse› returns on every input, for a grammar
  whose automaton is deterministic (const‹mdet›).  Without determinism the two
  could pick different reduce candidates, since this driver's items are in table
  order rather than in the order the kernels happen to arrive in.›

subsection ‹Canonical anchor sets›

text ‹const‹irep_union› concatenates and const‹irep_pre› materialises intervals,
  so anchor sets of the running drivers carry duplicates.  The operations here
  keep a set sorted and duplicate-free, with the finite part of an
  const‹UpRep› below its bound; only the set an operation denotes enters the
  correctness argument.›

fun merge :: ‹nat list ⇒ nat list ⇒ nat list› where
  ‹merge [] ys = ys›
| ‹merge xs [] = xs›
| ‹merge (x # xs) (y # ys) =
    (if x < y then x # merge xs (y # ys)
     else if y < x then y # merge (x # xs) ys else x # merge xs ys)›

lemma set_merge [simp]: ‹set (merge xs ys) = set xs ∪ set ys›
  by (induction xs ys rule: merge.induct) auto

fun cunion :: ‹indrep ⇒ indrep ⇒ indrep› where
  ‹cunion (FinRep xs) (FinRep ys) = FinRep (merge xs ys)›
| ‹cunion (FinRep xs) (UpRep ys n) = UpRep (filter (λi. i < n) (merge xs ys)) n›
| ‹cunion (UpRep xs n) (FinRep ys) = UpRep (filter (λi. i < n) (merge xs ys)) n›
| ‹cunion (UpRep xs n) (UpRep ys m) = UpRep (filter (λi. i < min n m) (merge xs ys)) (min n m)›

lemma cunion_set [simp]: ‹irep_set (cunion R S) = irep_set R ∪ irep_set S›
  by (cases R; cases S) auto

text ‹The set with the up-set from ‹t› added.›

fun cup :: ‹nat ⇒ indrep ⇒ indrep› where
  ‹cup t (FinRep xs) = UpRep (filter (λi. i < t) xs) t›
| ‹cup t (UpRep xs n) = UpRep (filter (λi. i < min t n) xs) (min t n)›

lemma cup_set [simp]: ‹irep_set (cup t R) = irep_set R ∪ {m. t ≤ m}›
  by (cases R) auto

fun cinter :: ‹indrep ⇒ indrep ⇒ indrep› where
  ‹cinter (FinRep xs) S = FinRep (filter (λi. irep_mem i S) xs)›
| ‹cinter (UpRep xs n) (FinRep ys) = FinRep (filter (λi. irep_mem i (UpRep xs n)) ys)›
| ‹cinter (UpRep xs n) (UpRep ys m) =
     UpRep (filter (λi. i < max n m)
       (merge (filter (λi. irep_mem i (UpRep ys m)) xs) (filter (λi. irep_mem i (UpRep xs n)) ys)))
       (max n m)›

lemma cinter_set [simp]: ‹irep_set (cinter R S) = irep_set R ∩ irep_set S›
  by (cases R; cases S) auto

text ‹The elements below a bound, as a finite set.›

fun cbelow :: ‹nat ⇒ indrep ⇒ indrep› where
  ‹cbelow b (FinRep xs) = FinRep (filter (λi. i < b) xs)›
| ‹cbelow b (UpRep xs n) = FinRep (filter (λi. i < b) xs @ [n..<b])›

lemma cbelow_set [simp]: ‹irep_set (cbelow b R) = irep_set R ∩ {i. i < b}›
  by (cases R) auto

lemma fold_max_lt_iff: ‹i < fold max ys a ⟷ i < a ∨ (∃y ∈ set ys. i < y)› for ys :: ‹nat list›
  using Max.set_eq_fold[of a ys, symmetric] by (simp add: Max_gr_iff)

lemma fold_max_le_iff: ‹i ≤ fold max ys a ⟷ i ≤ a ∨ (∃y ∈ set ys. i ≤ y)› for ys :: ‹nat list›
  using Max.set_eq_fold[of a ys, symmetric] by (simp add: Max_ge_iff)

lemma up_unbounded: ‹∃j ∈ A ∪ Collect ((≤) n). x < j› ‹∃j ∈ A ∪ Collect ((≤) n). x ≤ j›
  for n x :: nat
  by (rule bexI[of _ ‹max (Suc x) n›]; simp)+

text ‹The parent anchors in ‹R› compatible with a child anchor in ‹RA›:
  term‹irep_inter R (irep_pre q RA)› without materialising the preimage.›

definition cpre :: ‹irel ⇒ indrep ⇒ indrep ⇒ indrep› where
  ‹cpre q RA R = (case q of
     Eq ⇒ cinter R RA
   | Gt ⇒ (case RA of FinRep ys ⇒ (if ys = [] then FinRep [] else cbelow (fold max ys 0) R)
            | UpRep _ _ ⇒ R)
   | Ge ⇒ (case RA of FinRep ys ⇒ (if ys = [] then FinRep [] else cbelow (Suc (fold max ys 0)) R)
            | UpRep _ _ ⇒ R)
   | Any ⇒ (if irep_nonempty RA then R else FinRep []))›

lemma cpre_set [simp]: ‹irep_set (cpre q RA R) = irep_set R ∩ irep_set (irep_pre q RA)›
proof (cases q)
  case Gt
  then show ?thesis
    by (cases RA) (auto simp: cpre_def fold_max_lt_iff up_unbounded simp del: irep_pre.simps)
next
  case Ge
  then show ?thesis
    by (cases RA) (auto simp: cpre_def fold_max_le_iff less_Suc_eq_le up_unbounded ex_in_conv simp del: irep_pre.simps)
qed (auto simp: cpre_def)

subsection ‹Anchor-set transfers›

text ‹A transfer is a join of up to three parts: the identity, the up-set from
  the least anchor shifted by ‹d›, and the up-set from a constant ‹d› (present only
  when the set is non-empty).  The relations of the grammar are transfers, and
  transfers are closed under join and composition.  They stand in for the
  closure of the indentation relations under composition and union
  cite‹‹Lemmas~2 and~3› in "adams2013"›, where a union holds each form at most once.
  Unlike the relations there, a transfer acts on anchor sets.›

type_synonym eff = ‹bool × nat option × nat option›

definition sh :: ‹nat ⇒ nat set ⇒ nat set› where ‹sh d S = {m. ∃j ∈ S. j + d ≤ m}›
definition cn :: ‹nat ⇒ nat set ⇒ nat set› where ‹cn d S = {m. S ≠ {} ∧ d ≤ m}›

definition osh :: ‹nat option ⇒ nat set ⇒ nat set› where
  ‹osh s S = (case s of None ⇒ {} | Some d ⇒ sh d S)›
definition ocn :: ‹nat option ⇒ nat set ⇒ nat set› where
  ‹ocn c S = (case c of None ⇒ {} | Some d ⇒ cn d S)›

fun eff_set :: ‹eff ⇒ nat set ⇒ nat set› where
  ‹eff_set (i, s, c) S = (if i then S else {}) ∪ osh s S ∪ ocn c S›

abbreviation ebot :: eff where ‹ebot ≡ (False, None, None)›
abbreviation eid :: eff where ‹eid ≡ (True, None, None)›

fun of_rel :: ‹irel ⇒ eff› where
  ‹of_rel Eq = (True, None, None)›
| ‹of_rel Gt = (False, Some 1, None)›
| ‹of_rel Ge = (False, Some 0, None)›
| ‹of_rel Any = (False, None, Some 0)›

lemma eff_set_of_rel: ‹eff_set (of_rel q) S = {j. ∃i ∈ S. irel_sat q j i}›
  by (cases q) (auto simp: osh_def ocn_def sh_def cn_def Suc_le_eq)

lemma eff_set_img: ‹eff_set (of_rel q) (irep_set R) = irep_set (irep_img q R)›
  by (simp add: eff_set_of_rel)

lemma osh_simps [simp]: ‹osh None S = {}› ‹osh (Some d) S = sh d S›
  and ocn_simps [simp]: ‹ocn None S = {}› ‹ocn (Some d) S = cn d S›
  by (simp_all add: osh_def ocn_def)

lemma sh_empty [simp]: ‹sh d {} = {}› and cn_empty [simp]: ‹cn d {} = {}›
  by (simp_all add: sh_def cn_def)

lemma osh_empty [simp]: ‹osh s {} = {}› and ocn_empty [simp]: ‹ocn c {} = {}›
  by (simp_all add: osh_def ocn_def split: option.splits)

lemma eff_set_empty [simp]: ‹eff_set e {} = {}›
  by (cases e) simp

lemma eff_set_bot [simp]: ‹eff_set ebot S = {}›
  by (simp add: osh_def ocn_def)

lemma eff_set_id [simp]: ‹eff_set eid S = S›
  by (simp add: osh_def ocn_def)

lemma sh_UN: ‹sh d (⋃ 𝒜) = ⋃ (sh d ` 𝒜)› and cn_UN: ‹cn d (⋃ 𝒜) = ⋃ (cn d ` 𝒜)›
  unfolding sh_def cn_def by auto

lemma osh_UN: ‹osh s (⋃ 𝒜) = ⋃ (osh s ` 𝒜)› and ocn_UN: ‹ocn c (⋃ 𝒜) = ⋃ (ocn c ` 𝒜)›
  unfolding osh_def ocn_def by (auto simp: sh_UN cn_UN split: option.splits)

lemma eff_set_UN: ‹eff_set e (⋃ 𝒜) = ⋃ (eff_set e ` 𝒜)›
  by (cases e) (auto simp: osh_UN ocn_UN)

lemma eff_set_Un: ‹eff_set e (A ∪ B) = eff_set e A ∪ eff_set e B›
  using eff_set_UN[of e ‹{A, B}›] by simp

lemma eff_set_mono: ‹A ⊆ B ⟹ eff_set e A ⊆ eff_set e B›
  by (metis eff_set_Un subset_Un_eq)

text ‹Join: the parts of both.  The joins of the shifts and of the constants are
  their minima, since a smaller offset gives a larger up-set.›

definition omin :: ‹nat option ⇒ nat option ⇒ nat option› where
  ‹omin a b = (case a of None ⇒ b | Some x ⇒ (case b of None ⇒ Some x | Some y ⇒ Some (min x y)))›

lemma sh_min: ‹sh (min x y) S = sh x S ∪ sh y S› and cn_min: ‹cn (min x y) S = cn x S ∪ cn y S›
  unfolding sh_def cn_def min_def
  by (auto 0 3 intro: le_trans add_left_mono) (meson add_le_cancel_left le_trans nat_le_linear)

lemma omin_simps [simp]:
  ‹omin None b = b› ‹omin a None = a› ‹omin (Some x) (Some y) = Some (min x y)›
  by (simp_all add: omin_def split: option.split)

lemma osh_omin: ‹osh (omin a b) S = osh a S ∪ osh b S›
  and ocn_omin: ‹ocn (omin a b) S = ocn a S ∪ ocn b S›
  unfolding osh_def ocn_def omin_def by (auto simp: sh_min cn_min split: option.splits)

fun ejoin :: ‹eff ⇒ eff ⇒ eff› where
  ‹ejoin (i1, s1, c1) (i2, s2, c2) = (i1 ∨ i2, omin s1 s2, omin c1 c2)›

lemma eff_set_join: ‹eff_set (ejoin e f) S = eff_set e S ∪ eff_set f S›
  by (cases e; cases f) (auto simp: osh_omin ocn_omin)

lemma eff_set_fold_ejoin: ‹eff_set (fold ejoin xs a) S = eff_set a S ∪ (⋃x ∈ set xs. eff_set x S)›
  by (induction xs arbitrary: a) (auto simp: eff_set_join)

text ‹Composition, ‹e2› after ‹e1›: a shift after a shift adds the offsets, a
  constant after anything stays, a shift after a constant is a constant.›

lemma sh_sh: ‹sh d2 (sh d1 S) = sh (d1 + d2) S›
  unfolding sh_def by (auto 0 3 intro: le_trans[OF add_right_mono] simp: add.assoc[symmetric])

lemma cn_sh: ‹cn d2 (sh d1 S) = cn d2 S›
  unfolding sh_def cn_def by auto

lemma sh_cn: ‹sh d2 (cn d1 S) = cn (d1 + d2) S›
  unfolding sh_def cn_def by auto

lemma cn_cn: ‹cn d2 (cn d1 S) = cn d2 S›
  unfolding cn_def by auto

lemma sh_absorb: ‹d ≤ d' ⟹ sh d' S ⊆ sh d S› and cn_absorb: ‹d ≤ d' ⟹ cn d' S ⊆ cn d S›
  unfolding sh_def cn_def by (auto intro: le_trans[OF add_left_mono])

text ‹What a transfer ‹e› does after a shift, and after a constant, by ‹d›.›

fun aft_sh :: ‹nat ⇒ eff ⇒ eff› where
  ‹aft_sh d (i, s, c) = (False, omin (if i then Some d else None) (map_option ((+) d) s), c)›

fun aft_cn :: ‹nat ⇒ eff ⇒ eff› where
  ‹aft_cn d (i, s, c) =
     (False, None, omin (if i then Some d else None) (omin (map_option ((+) d) s) c))›

lemma eff_set_after_sh: ‹eff_set e (sh d S) = eff_set (aft_sh d e) S›
proof (cases e)
  case (fields i s c)
  then show ?thesis
    using sh_absorb[of d ‹d + _› S]
    by (cases i; cases s; cases c) (auto simp: sh_sh cn_sh sh_min)
qed

lemma eff_set_after_cn: ‹eff_set e (cn d S) = eff_set (aft_cn d e) S›
proof (cases e)
  case (fields i s c)
  then show ?thesis
    using cn_absorb[of d ‹d + _› S]
    by (cases i; cases s; cases c) (auto simp: sh_cn cn_cn cn_min)
qed

fun ecomp :: ‹eff ⇒ eff ⇒ eff› where
  ‹ecomp e2 (i1, s1, c1) =
     ejoin (if i1 then e2 else ebot)
      (ejoin (case s1 of None ⇒ ebot | Some d ⇒ aft_sh d e2)
             (case c1 of None ⇒ ebot | Some d ⇒ aft_cn d e2))›

lemma eff_set_comp: ‹eff_set (ecomp e2 e1) S = eff_set e2 (eff_set e1 S)›
proof (cases e1)
  case (fields i s c)
  have ‹eff_set e2 (osh s S) = eff_set (case s of None ⇒ ebot | Some d ⇒ aft_sh d e2) S›
    by (cases s) (simp_all add: eff_set_after_sh)
  moreover have ‹eff_set e2 (ocn c S) = eff_set (case c of None ⇒ ebot | Some d ⇒ aft_cn d e2) S›
    by (cases c) (simp_all add: eff_set_after_cn)
  moreover have ‹eff_set e2 (if i then S else {}) = eff_set (if i then e2 else ebot) S›
    by simp
  ultimately show ?thesis
    by (simp only: fields ecomp.simps eff_set.simps[of i s c] eff_set_Un eff_set_join Un_assoc)
qed

subsection ‹The transfer order and its well-foundedness›

text ‹A transfer below another denotes a subset for every argument.  Every
  ascending chain is finite: the identity is added at most once, and each offset,
  once present, only decreases.›

fun ole :: ‹nat option ⇒ nat option ⇒ bool› where
  ‹ole None _ = True›
| ‹ole (Some d) None = False›
| ‹ole (Some d) (Some d') = (d' ≤ d)›

fun ele :: ‹eff ⇒ eff ⇒ bool› where
  ‹ele (i1, s1, c1) (i2, s2, c2) = ((i1 ⟶ i2) ∧ ole s1 s2 ∧ ole c1 c2)›

lemma ole_refl [simp]: ‹ole a a›
  by (cases a) simp_all

lemma ole_trans: ‹ole a b ⟹ ole b c ⟹ ole a c›
  by (cases a; cases b; cases c) simp_all

lemma ole_omin1: ‹ole a (omin a b)› and ole_omin2: ‹ole b (omin a b)›
  by (cases a; cases b; simp add: omin_def)+

lemma ele_refl [simp]: ‹ele e e›
  by (cases e) simp

lemma ele_trans: ‹ele e f ⟹ ele f g ⟹ ele e g›
  by (cases e; cases f; cases g) (auto intro: ole_trans)

lemma ele_join2: ‹ele f (ejoin e f)›
  by (cases e; cases f; simp add: ole_omin2)

lemma ele_fold_ejoin: ‹ele a (fold ejoin xs a)›
proof -
  have ‹ele b a ⟹ ele b (fold ejoin xs a)› for b
  proof (induction xs arbitrary: a)
    case (Cons x xs)
    from Cons.prems have ‹ele b (ejoin x a)› by (rule ele_trans) (rule ele_join2)
    then have ‹ele b (fold ejoin xs (ejoin x a))› by (rule Cons.IH)
    then show ?case by simp
  qed simp
  then show ?thesis by simp
qed

fun omeas :: ‹nat option ⇒ nat × nat› where
  ‹omeas None = (1, 0)›
| ‹omeas (Some d) = (0, d)›

lemma ole_omeas:
  ‹ole a b ⟹ a ≠ b ⟹ (omeas b, omeas a) ∈ less_than <*lex*> less_than›
  by (cases a; cases b) auto

text ‹An increase raises the identity flag, or keeps it and decreases the shift,
  or keeps both and decreases the constant.›

lemma wf_eff_inc: ‹wf {(f, e). ele e f ∧ e ≠ f}›
proof -
  have wo: ‹wf {(b, a). ole a b ∧ a ≠ b}›
    by (rule wf_subset[OF wf_inv_image[OF wf_lex_prod[OF wf_less_than wf_less_than]], of _ omeas])
      (auto dest: ole_omeas)
  have wb: ‹wf {(True, False)}›
    by (rule wf_subset[OF wf_inv_image[OF wf_less_than], of _ ‹λb. if b then 0 else 1›]) auto
  have ‹{(f, e). ele e f ∧ e ≠ f} ⊆
      {(True, False)} <*lex*> ({(b, a). ole a b ∧ a ≠ b} <*lex*> {(b, a). ole a b ∧ a ≠ b})›
    by clarsimp (metis (full_types))
  then show ?thesis by (rule wf_subset[rotated]) (intro wf_lex_prod wb wo)
qed

lemma list_all2_ne_lex:
  assumes ‹list_all2 ele xs ys› and ‹xs ≠ ys›
  shows ‹(ys, xs) ∈ lex {(f, e). ele e f ∧ e ≠ f}›
  using assms
proof (induction rule: list_all2_induct)
  case (Cons x xs y ys)
  show ?case
  proof (cases ‹x = y›)
    case True
    with Cons have ‹(ys, xs) ∈ lex {(f, e). ele e f ∧ e ≠ f}› by simp
    then show ?thesis unfolding True lex_conv
      by clarsimp (metis Cons_eq_appendI)
  next
    case False
    then have ‹ele x y ∧ x ≠ y› using Cons.hyps(1) by blast
    moreover have ‹y # ys = [] @ y # ys› ‹x # xs = [] @ x # xs› by simp_all
    moreover have ‹length (y # ys) = length (x # xs)›
      using list_all2_lengthD[OF Cons.hyps(2)] by simp
    ultimately show ?thesis unfolding lex_conv by (simp only: mem_Collect_eq case_prod_conv) blast
  qed
qed simp

lemma wf_eff_list_inc: ‹wf {(ys, xs). list_all2 ele xs ys ∧ xs ≠ ys}›
  by (rule wf_subset[OF wf_lex[OF wf_eff_inc]]) (auto simp: list_all2_ne_lex)

declare eff_set.simps [simp del]

subsection ‹The closure graph›

text ‹A closure round sends the anchor set of a nonterminal ‹c› through the
  first symbol of each production of ‹c›: an edge to ‹a›, labelled with the
  relation of that symbol.  The table invariant ‹ntl_ok› says that only
  nonterminals with a number have productions.›

definition tedge :: ‹('n, 't) stab ⇒ nat ⇒ nat ⇒ irel ⇒ bool› where
  ‹tedge T c a q ⟷ c < s_np T ∧ a < s_np T ∧
     (∃k ∈ set (ntl T c). ∃rest. rrhs (s_recs T !! k) = (Nt a, q) # rest)›

definition ntl_ok :: ‹('n, 't) stab ⇒ bool› where
  ‹ntl_ok T ⟷ (∀c. s_np T ≤ c ⟶ ntl T c = [])›

lemma ntl_ok_mk_stab: ‹ntl_ok (mk_stab G Shn gt sts redtab)›
  unfolding ntl_ok_def ntl_mk_stab
  by (auto intro!: filter_False) (metis le_trans lids_nth_le not_le)

lemma nx_set_slot:
  ‹nx_set np a (r, 0, R) =
     ⋃{irep_set (irep_img q R) |q. a < np ∧ (∃rest. rrhs r = (Nt a, q) # rest)}›
  by (auto simp: nx_set_def sitem_nx_def neq_Nil_conv split: list.splits sym.splits prod.splits)

lemma sslot_kset_tedge:
  assumes ‹ntl_ok T›
  shows ‹kset a (sslot_nx T c R) = ⋃{eff_set (of_rel q) (irep_set R) |q. tedge T c a q}›
proof (cases ‹c < s_np T›)
  case True
  have ‹kset a (sslot_nx T c R) = ⋃ (nx_set (s_np T) a ` (λk. (s_recs T !! k, 0, R)) ` set (ntl T c))›
    unfolding sslot_nx_def
    using map_filter_nx_set[of a ‹s_np T› ‹map (λk. (s_recs T !! k, 0, R)) (ntl T c)›]
    by (simp add: map_filter_map o_def)
  also have ‹… = ⋃{eff_set (of_rel q) (irep_set R) |q. tedge T c a q}›
    using True by (auto simp: nx_set_slot tedge_def eff_set_img)
  finally show ?thesis .
next
  case False
  with assms show ?thesis by (simp add: ntl_ok_def sslot_nx_def tedge_def List.map_filter_def)
qed


text ‹A round on anchor-set assignments: the kernel's sets, and every edge's
  image of the set at its source.›

definition sem_round :: ‹('n, 't) stab ⇒ (nat × indrep) list ⇒ (nat ⇒ nat set) ⇒ nat ⇒ nat set› where
  ‹sem_round T kn ν a = kset a kn ∪ ⋃{eff_set (of_rel q) (ν c) |c q. tedge T c a q}›

lemma sem_round_mono: ‹(⋀c. ν c ⊆ μ c) ⟹ sem_round T kn ν a ⊆ sem_round T kn μ a›
proof -
  assume le: ‹⋀c. ν c ⊆ μ c›
  have ‹eff_set (of_rel q) (ν c) ⊆ eff_set (of_rel q) (μ c)› for q c by (rule eff_set_mono[OF le])
  then show ?thesis unfolding sem_round_def by fast
qed

lemma UN_keys_slk:
  assumes d: ‹distinct (map fst N)› and f: ‹⋀c. f c {} = {}›
  shows ‹(⋃(c, R) ∈ set N. f c (irep_set R)) = (⋃c. f c (irep_set (slk N c)))›
proof (intro equalityI subsetI)
  fix x assume ‹x ∈ (⋃(c, R) ∈ set N. f c (irep_set R))›
  then obtain c R where ‹(c, R) ∈ set N› ‹x ∈ f c (irep_set R)› by blast
  with d have ‹x ∈ f c (irep_set (slk N c))› by (simp add: slk_in)
  then show ‹x ∈ (⋃c. f c (irep_set (slk N c)))› by blast
next
  fix x assume ‹x ∈ (⋃c. f c (irep_set (slk N c)))›
  then obtain c where x: ‹x ∈ f c (irep_set (slk N c))› by blast
  show ‹x ∈ (⋃(c, R) ∈ set N. f c (irep_set R))›
  proof (cases ‹c ∈ fst ` set N›)
    case True
    then obtain R where ‹(c, R) ∈ set N› by force
    with d x show ?thesis by (auto simp: slk_in)
  next
    case False
    with x f show ?thesis by (simp add: slk_notin)
  qed
qed

lemma sround_distinct: ‹distinct (map fst (sround T kn N))›
  unfolding sround_def by (rule fold_sins_distinct) simp

lemma siter_distinct: ‹distinct (map fst (siter T kn t))›
  by (cases t) (simp_all add: sround_distinct)

lemma sround_sem:
  assumes ok: ‹ntl_ok T› and d: ‹distinct (map fst N)›
  shows ‹irep_set (slk (sround T kn N) a) = sem_round T kn (λc. irep_set (slk N c)) a›
proof -
  let ?f = ‹λc S. ⋃{eff_set (of_rel q) S |q. tedge T c a q}›
  have ‹irep_set (slk (sround T kn N) a) = kset a kn ∪ (⋃(c, R) ∈ set N. kset a (sslot_nx T c R))›
    by (simp add: sround_def fold_sins_set kset_filter_ne kset_concat_map)
  also have ‹(⋃(c, R) ∈ set N. kset a (sslot_nx T c R)) = (⋃(c, R) ∈ set N. ?f c (irep_set R))›
    by (simp add: sslot_kset_tedge[OF ok])
  also have ‹… = (⋃c. ?f c (irep_set (slk N c)))›
    by (rule UN_keys_slk[OF d]) auto
  finally show ?thesis by (auto simp: sem_round_def)
qed

subsection ‹Paths and their transfers›

text ‹The transfer of a path in the closure graph, from a kernel nonterminal
  ‹b›: the composition of the relations on its edges.›

inductive treach :: ‹('n, 't) stab ⇒ nat ⇒ nat ⇒ eff ⇒ bool› for T b where
  treach_refl: ‹treach T b b eid›
| treach_edge: ‹treach T b c e ⟹ tedge T c a q ⟹ treach T b a (ecomp (of_rel q) e)›

definition tpaths :: ‹('n, 't) stab ⇒ (nat × indrep) list ⇒ nat ⇒ nat set› where
  ‹tpaths T kn a = ⋃{eff_set e (irep_set R) |b R e. (b, R) ∈ set kn ∧ treach T b a e}›

lemma kset_le_tpaths: ‹kset a kn ⊆ tpaths T kn a›
proof
  fix x assume ‹x ∈ kset a kn›
  then obtain R where R: ‹(a, R) ∈ set kn› and x: ‹x ∈ irep_set R› by (auto simp: kset_def)
  have ‹eff_set eid (irep_set R) ∈ {eff_set e (irep_set R') |b R' e. (b, R') ∈ set kn ∧ treach T b a e}›
    using R treach_refl[of T a] by blast
  with x show ‹x ∈ tpaths T kn a› unfolding tpaths_def eff_set_id by blast
qed

lemma sem_round_tpaths: ‹sem_round T kn (tpaths T kn) a ⊆ tpaths T kn a›
proof -
  have ‹eff_set (of_rel q) (tpaths T kn c) ⊆ tpaths T kn a› if ‹tedge T c a q› for c q
  proof
    fix x assume ‹x ∈ eff_set (of_rel q) (tpaths T kn c)›
    then obtain b R e where ‹(b, R) ∈ set kn› ‹treach T b c e›
        ‹x ∈ eff_set (of_rel q) (eff_set e (irep_set R))›
      unfolding tpaths_def by (auto simp: eff_set_UN)
    with that show ‹x ∈ tpaths T kn a›
      unfolding tpaths_def by (blast intro: treach_edge eff_set_comp[THEN equalityD2, THEN subsetD])
  qed
  then show ?thesis unfolding sem_round_def using kset_le_tpaths by blast
qed

lemma siter_le_tpaths:
  assumes ‹ntl_ok T›
  shows ‹irep_set (slk (siter T kn t) a) ⊆ tpaths T kn a›
proof (induction t arbitrary: a)
  case (Suc t)
  have ‹irep_set (slk (siter T kn (Suc t)) a) = sem_round T kn (λc. irep_set (slk (siter T kn t) c)) a›
    by (simp add: sround_sem[OF assms siter_distinct])
  also have ‹… ⊆ sem_round T kn (tpaths T kn) a›
    by (rule sem_round_mono) (rule Suc.IH)
  also have ‹… ⊆ tpaths T kn a› by (rule sem_round_tpaths)
  finally show ?case .
qed simp

text ‹Conversely, a set assignment that a round does not enlarge contains every
  path's image.›

lemma tpaths_le_post:
  assumes post: ‹⋀a. sem_round T kn ν a ⊆ ν a›
  shows ‹tpaths T kn a ⊆ ν a›
proof -
  have ‹eff_set e (irep_set R) ⊆ ν a› if ‹treach T b a e› ‹(b, R) ∈ set kn› for b a e R
    using that(1)
  proof induction
    case treach_refl
    have ‹irep_set R ⊆ kset b kn› using that(2) by (auto simp: kset_def)
    also have ‹… ⊆ ν b› using post[of b] by (simp add: sem_round_def)
    finally show ?case by simp
  next
    case (treach_edge c e a q)
    have ‹eff_set (ecomp (of_rel q) e) (irep_set R) = eff_set (of_rel q) (eff_set e (irep_set R))›
      by (rule eff_set_comp)
    also have ‹… ⊆ eff_set (of_rel q) (ν c)› by (rule eff_set_mono[OF treach_edge.IH])
    also have ‹… ⊆ ν a› using post[of a] treach_edge.hyps(2) unfolding sem_round_def by blast
    finally show ?case .
  qed
  then show ?thesis unfolding tpaths_def by blast
qed

text ‹So the fixpoint the sparse closure computes is the union of the path
  images, whenever its loop stops.›

definition sfix_loop :: ‹('n, 't) stab ⇒ (nat × indrep) list ⇒
    ((nat × indrep) list × (nat × indrep) list) option› where
  ‹sfix_loop T kn = while_option (λ(N, N'). ¬ ssub N' N)
     (λ(N, N'). (N', sround T kn N')) ([], sround T kn [])›

lemma ssub_le:
  assumes ‹ssub N' N› shows ‹irep_set (slk N' a) ⊆ irep_set (slk N a)›
proof (cases ‹map_of N' a›)
  case (Some R)
  then have ‹(a, R) ∈ set N'› by (rule map_of_SomeD)
  with assms Some show ?thesis by (auto simp: ssub_def list_all_iff slk_def)
qed (simp add: slk_def)

lemma sfix_tpaths:
  assumes ok: ‹ntl_ok T› and stop: ‹sfix_loop T kn ≠ None›
  shows ‹irep_set (slk (sfix T kn) a) = tpaths T kn a›
proof -
  obtain N N' where loop: ‹sfix_loop T kn = Some (N, N')› using stop by auto
  let ?P = ‹λp. ∃t. fst p = siter T kn t ∧ snd p = siter T kn (Suc t)›
  have ‹?P (N, N')›
  proof (rule while_option_rule[OF _ loop[unfolded sfix_loop_def]])
    fix p assume ‹?P p›
    then obtain t where ‹fst p = siter T kn t› ‹snd p = siter T kn (Suc t)› by blast
    then show ‹?P ((λ(N, N'). (N', sround T kn N')) p)›
      by (intro exI[of _ ‹Suc t›]) (simp add: case_prod_beta)
  qed (intro exI[of _ 0]; simp)
  then obtain t where N: ‹N = siter T kn t› and N': ‹N' = siter T kn (Suc t)› by auto
  have sub: ‹ssub N' N› using while_option_stop[OF loop[unfolded sfix_loop_def]] by simp
  have fx: ‹sfix T kn = N› using loop by (simp add: sfix_def sfix_loop_def)
  have post: ‹sem_round T kn (λc. irep_set (slk N c)) b ⊆ irep_set (slk N b)› for b
    using ssub_le[OF sub, of b] by (simp add: N N' sround_sem[OF ok siter_distinct])
  show ?thesis
    unfolding fx using siter_le_tpaths[OF ok, of kn t a] tpaths_le_post[OF post, of a]
    by (auto simp: N)
qed


subsection ‹The saturated transfer table›

text ‹For each source nonterminal ‹b›, a row with the join of the transfers of
  all paths from ‹b› to each nonterminal: the least fixpoint of the edges,
  reached by iteration, since the transfer order has no infinite ascending
  chains.  The equations have the shape of Eq.~(4.1) of DeRemer and Pennello,
  cf.~cite‹‹Sect.~4.1› in "deremer1982-lalr-lookahead"›, with transfers in place of
  sets and a composition along each edge.  They are solved by plain iteration,
  not by the traversal ‹Digraph› given there.›

definition hd_nt :: ‹('n, 't) prec ⇒ (nat × irel) option› where
  ‹hd_nt r = (case rrhs r of (Nt a, q) # _ ⇒ Some (a, q) | _ ⇒ None)›

lemma hd_nt_eq: ‹hd_nt r = Some (a, q) ⟷ (∃rest. rrhs r = (Nt a, q) # rest)›
  by (auto simp: hd_nt_def split: list.split sym.split prod.split)

definition tin :: ‹('n, 't) stab ⇒ nat ⇒ (nat × irel) list› where
  ‹tin T a = concat (map (λc. List.map_filter (λk. case hd_nt (s_recs T !! k) of
       Some (a', q) ⇒ if a' = a then Some (c, q) else None | None ⇒ None) (ntl T c))
     [0..<s_np T])›

lemma set_tin: ‹a < s_np T ⟹ set (tin T a) = {(c, q). tedge T c a q}›
proof -
  have c: ‹(case h of Some (a', q') ⇒ if a' = a then Some (x, q') else None | None ⇒ None) = Some (y, q)
      ⟷ h = Some (a, q) ∧ y = x› for h :: ‹(nat × irel) option› and x y :: nat and q
    by (cases h) (auto split: if_splits)
  assume ‹a < s_np T›
  then show ?thesis
    by (auto simp: tin_def tedge_def in_map_filter c hd_nt_eq[symmetric] simp del: IArray.sub_def)
qed

definition tr_step :: ‹('n, 't) stab ⇒ eff list ⇒ eff list› where
  ‹tr_step T row = map (λa. fold ejoin (map (λ(c, q). ecomp (of_rel q) (row ! c)) (tin T a)) (row ! a))
     [0..<s_np T]›

definition tinit :: ‹nat ⇒ nat ⇒ eff list› where
  ‹tinit n b = map (λa. if a = b then eid else ebot) [0..<n]›

definition trow_loop :: ‹('n, 't) stab ⇒ nat ⇒ eff list option› where
  ‹trow_loop T b = while_option (λrow. tr_step T row ≠ row) (tr_step T) (tinit (s_np T) b)›

definition trow :: ‹('n, 't) stab ⇒ nat ⇒ eff list› where
  ‹trow T b = the (trow_loop T b)›

lemma length_tr_step [simp]: ‹length (tr_step T row) = s_np T›
  by (simp add: tr_step_def)

lemma tr_step_nth: ‹a < s_np T ⟹
    tr_step T row ! a = fold ejoin (map (λ(c, q). ecomp (of_rel q) (row ! c)) (tin T a)) (row ! a)›
  by (simp add: tr_step_def)

lemma tr_step_inc: ‹length row = s_np T ⟹ list_all2 ele row (tr_step T row)›
  by (simp add: list_all2_conv_all_nth tr_step_nth ele_fold_ejoin)

lemma trow_loop_Some: ‹trow_loop T b ≠ None›
proof -
  let ?P = ‹λrow. length row = s_np T›
  have ‹{(t, s). (?P s ∧ tr_step T s ≠ s) ∧ t = tr_step T s} ⊆ {(ys, xs). list_all2 ele xs ys ∧ xs ≠ ys}›
    using tr_step_inc by fastforce
  then have ‹wf {(t, s). (?P s ∧ tr_step T s ≠ s) ∧ t = tr_step T s}›
    by (rule wf_subset[OF wf_eff_list_inc])
  then have ‹∃r. trow_loop T b = Some r›
    unfolding trow_loop_def by (rule wf_while_option_Some) (simp_all add: tinit_def)
  then show ?thesis by auto
qed

text ‹The semantic invariant of the iteration: every entry is below the paths,
  and the source's entry contains the identity.›

definition tpath_set :: ‹('n, 't) stab ⇒ nat ⇒ nat ⇒ nat set ⇒ nat set› where
  ‹tpath_set T b a S = ⋃{eff_set e S |e. treach T b a e}›

lemma tpath_set_edge:
  assumes ‹tedge T c a q›
  shows ‹eff_set (of_rel q) (tpath_set T b c S) ⊆ tpath_set T b a S›
proof
  fix x assume ‹x ∈ eff_set (of_rel q) (tpath_set T b c S)›
  then obtain e where e: ‹treach T b c e› and x: ‹x ∈ eff_set (of_rel q) (eff_set e S)›
    unfolding tpath_set_def eff_set_UN by blast
  have ‹eff_set (ecomp (of_rel q) e) S ∈ {eff_set e S |e. treach T b a e}›
    using treach_edge[OF e assms] by blast
  with x show ‹x ∈ tpath_set T b a S› unfolding tpath_set_def eff_set_comp by blast
qed

definition trow_inv :: ‹('n, 't) stab ⇒ nat ⇒ eff list ⇒ bool› where
  ‹trow_inv T b row ⟷ length row = s_np T ∧
     (∀a < s_np T. ∀S. eff_set (row ! a) S ⊆ tpath_set T b a S) ∧
     (∀S. b < s_np T ⟶ S ⊆ eff_set (row ! b) S)›

lemma trow_inv_init: ‹trow_inv T b (tinit (s_np T) b)›
proof -
  have ‹S ⊆ tpath_set T b b S› for S
  proof -
    have ‹eff_set eid S ∈ {eff_set e S |e. treach T b b e}› using treach_refl[of T b] by blast
    then show ?thesis unfolding tpath_set_def eff_set_id by blast
  qed
  then show ?thesis by (simp add: trow_inv_def tinit_def)
qed

lemma tr_step_set:
  assumes ‹a < s_np T›
  shows ‹eff_set (tr_step T row ! a) S =
    eff_set (row ! a) S ∪ ⋃{eff_set (of_rel q) (eff_set (row ! c) S) |c q. tedge T c a q}›
proof -
  have ‹eff_set (tr_step T row ! a) S =
      eff_set (row ! a) S ∪ (⋃(c, q) ∈ set (tin T a). eff_set (of_rel q) (eff_set (row ! c) S))›
    using assms by (simp add: tr_step_nth eff_set_fold_ejoin case_prod_beta eff_set_comp)
  also have ‹(⋃(c, q) ∈ set (tin T a). eff_set (of_rel q) (eff_set (row ! c) S)) =
      ⋃{eff_set (of_rel q) (eff_set (row ! c) S) |c q. tedge T c a q}›
    using assms by (auto simp: set_tin)
  finally show ?thesis .
qed

lemma trow_inv_step:
  assumes inv: ‹trow_inv T b row›
  shows ‹trow_inv T b (tr_step T row)›
  unfolding trow_inv_def
proof (intro conjI allI impI)
  show ‹length (tr_step T row) = s_np T› by simp
next
  fix a S assume a: ‹a < s_np T›
  have ‹eff_set (of_rel q) (eff_set (row ! c) S) ⊆ tpath_set T b a S› if e: ‹tedge T c a q› for c q
  proof -
    have ‹c < s_np T› using e by (simp add: tedge_def)
    with inv have ‹eff_set (row ! c) S ⊆ tpath_set T b c S› by (simp add: trow_inv_def)
    then have ‹eff_set (of_rel q) (eff_set (row ! c) S) ⊆ eff_set (of_rel q) (tpath_set T b c S)›
      by (rule eff_set_mono)
    also have ‹… ⊆ tpath_set T b a S› by (rule tpath_set_edge[OF e])
    finally show ?thesis .
  qed
  moreover have ‹eff_set (row ! a) S ⊆ tpath_set T b a S› using inv a by (simp add: trow_inv_def)
  ultimately show ‹eff_set (tr_step T row ! a) S ⊆ tpath_set T b a S›
    unfolding tr_step_set[OF a] by blast
next
  fix S assume b: ‹b < s_np T›
  with inv have ‹S ⊆ eff_set (row ! b) S› by (simp add: trow_inv_def)
  then show ‹S ⊆ eff_set (tr_step T row ! b) S› unfolding tr_step_set[OF b] by blast
qed

lemma trow_some: obtains r where ‹trow_loop T b = Some r› ‹trow T b = r›
  using trow_loop_Some[of T b] by (auto simp: trow_def)

lemma trow_inv_trow: ‹trow_inv T b (trow T b)›
proof -
  obtain r where r: ‹trow_loop T b = Some r› and t: ‹trow T b = r› by (rule trow_some)
  have ‹trow_inv T b r›
    using while_option_rule[where P = ‹trow_inv T b›, OF trow_inv_step r[unfolded trow_loop_def]
        trow_inv_init] .
  with t show ?thesis by simp
qed

lemma tr_step_trow: ‹tr_step T (trow T b) = trow T b›
proof -
  obtain r where r: ‹trow_loop T b = Some r› and t: ‹trow T b = r› by (rule trow_some)
  from while_option_stop[OF r[unfolded trow_loop_def]] t show ?thesis by simp
qed

lemma trow_sem:
  assumes b: ‹b < s_np T› and a: ‹a < s_np T›
  shows ‹eff_set (trow T b ! a) S = tpath_set T b a S›
proof
  show ‹eff_set (trow T b ! a) S ⊆ tpath_set T b a S›
    using trow_inv_trow[of T b] a by (simp add: trow_inv_def)
  have ‹eff_set e S ⊆ eff_set (trow T b ! a') S› if ‹treach T b a' e› for a' e
    using that
  proof induction
    case treach_refl
    then show ?case using trow_inv_trow[of T b] b by (simp add: trow_inv_def)
  next
    case (treach_edge c e a q)
    have a': ‹a < s_np T› using treach_edge.hyps(2) by (simp add: tedge_def)
    have ‹eff_set (ecomp (of_rel q) e) S = eff_set (of_rel q) (eff_set e S)› by (rule eff_set_comp)
    also have ‹… ⊆ eff_set (of_rel q) (eff_set (trow T b ! c) S)›
      by (rule eff_set_mono[OF treach_edge.IH])
    also have ‹… ⊆ eff_set (tr_step T (trow T b) ! a) S›
      using treach_edge.hyps(2) unfolding tr_step_set[OF a'] by blast
    finally show ?case by (simp only: tr_step_trow)
  qed
  then show ‹tpath_set T b a S ⊆ eff_set (trow T b ! a) S› unfolding tpath_set_def by blast
qed

text ‹The closure's anchor set of a numbered nonterminal, from the kernel
  without a fixpoint.›

lemma sfix_trow:
  assumes ok: ‹ntl_ok T› and stop: ‹sfix_loop T kn ≠ None›
    and kn: ‹⋀b R. (b, R) ∈ set kn ⟹ b < s_np T› and a: ‹a < s_np T›
  shows ‹irep_set (slk (sfix T kn) a) = (⋃(b, R) ∈ set kn. eff_set (trow T b ! a) (irep_set R))›
proof -
  have ‹irep_set (slk (sfix T kn) a) = tpaths T kn a› by (rule sfix_tpaths[OF ok stop])
  also have ‹… = (⋃(b, R) ∈ set kn. tpath_set T b a (irep_set R))›
    unfolding tpaths_def tpath_set_def by blast
  also have ‹… = (⋃(b, R) ∈ set kn. eff_set (trow T b ! a) (irep_set R))›
    by (rule SUP_cong[OF refl]) (auto simp: trow_sem[OF kn a])
  finally show ?thesis .
qed



subsection ‹Applying a transfer›

text ‹The least anchor of a non-empty set, and a transfer applied to a set.›

fun imin :: ‹indrep ⇒ nat› where
  ‹imin (FinRep []) = 0›
| ‹imin (FinRep (x # xs)) = fold min xs x›
| ‹imin (UpRep xs n) = fold min xs n›

lemma fold_min_le_iff: ‹fold min ys a ≤ i ⟷ a ≤ i ∨ (∃y ∈ set ys. y ≤ i)› for ys :: ‹nat list›
  using Min.set_eq_fold[of a ys, symmetric] by (simp add: Min_le_iff)

lemma imin_le_iff: ‹irep_set R ≠ {} ⟹ imin R ≤ i ⟷ (∃j ∈ irep_set R. j ≤ i)›
proof (cases R)
  case (FinRep xs)
  assume ‹irep_set R ≠ {}›
  with FinRep show ?thesis by (cases xs) (auto simp: fold_min_le_iff)
next
  case (UpRep xs n)
  then show ?thesis by (auto simp: fold_min_le_iff intro: le_trans)
qed

lemma sh_imin:
  assumes ne: ‹irep_set R ≠ {}›
  shows ‹sh d (irep_set R) = {m. imin R + d ≤ m}›
proof -
  have l: ‹imin R ≤ j› if ‹j ∈ irep_set R› for j
    using imin_le_iff[OF ne, of j] that by blast
  obtain j0 where j0: ‹j0 ∈ irep_set R› ‹j0 ≤ imin R›
    using imin_le_iff[OF ne, of ‹imin R›] by blast
  with l have ‹j0 = imin R› by (simp add: le_antisym)
  with j0 l show ?thesis
    by (auto simp: sh_def intro: le_trans[OF add_right_mono])
qed

definition eapp :: ‹eff ⇒ indrep ⇒ indrep› where
  ‹eapp e R = (if irep_nonempty R then (case e of (i, s, c) ⇒
     let R1 = (if i then R else FinRep []);
         R2 = (case s of None ⇒ R1 | Some d ⇒ cup (imin R + d) R1)
     in (case c of None ⇒ R2 | Some d ⇒ cup d R2))
   else FinRep [])›

lemma eapp_set [simp]: ‹irep_set (eapp e R) = eff_set e (irep_set R)›
proof (cases ‹irep_set R = {}›)
  case False
  obtain i s c where e: ‹e = (i, s, c)› by (cases e)
  show ?thesis
    using False sh_imin[OF False]
    by (cases s; cases c) (auto simp: eapp_def e eff_set.simps cn_def)
qed (simp add: eapp_def)



subsection ‹The tables›

text ‹The items of state ‹j›: its LR(0) closure, in the order const‹creach›
  lists them.  A frame of the driver is a state with one anchor set per item.
  An item is a ∗‹slot› when the closure adds it: dot ‹0› of a grammar
  production.  The others, the ∗‹kernel positions›, get their anchors from the
  predecessor frame; a slot gets its anchors from the kernel positions, through
  the transfer of the closure graph (const‹trow›).›

definition vits :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list list ⇒ nat ⇒ ('n, 't) citem list› where
  ‹vits G sts j = (if j < length sts then creach G (sts ! j) else [])›

definition is_slot :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem ⇒ bool› where
  ‹is_slot G it ⟷ snd it = 0 ∧ fst it ∈ set (iprods G)›

definition getR :: ‹indrep list ⇒ nat ⇒ indrep› where
  ‹getR av k = (if k < length av then av ! k else FinRep [])›

definition iget :: ‹'a iarray ⇒ nat ⇒ 'a ⇒ 'a› where
  ‹iget xs k d = (if k < IArray.length xs then xs !! k else d)›

definition nnum :: ‹('n, 't) is_cfg ⇒ 'n ⇒ 'n ⇒ nat› where
  ‹nnum G Shn B = ntidx (map fst (eprods G Shn)) B›

text ‹The nonterminal after an item's dot, if the grammar has productions for it,
  with the relation it carries.›

definition vnext_nt :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem ⇒ ('n × irel) option› where
  ‹vnext_nt G it = (case it of (p, m) ⇒ if m < length (snd p) then
     (case snd p ! m of (Nt B, q) ⇒ if B ∈ fst ` set (iprods G) then Some (B, q) else None
      | _ ⇒ None) else None)›

text ‹The contributions to a slot: per kernel position whose item expects a
  nonterminal, the transfer from that position's anchors to the slot's.›

definition vcontrib :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) stab ⇒ ('n, 't) citem list ⇒
    ('n, 't) citem ⇒ (nat × eff) list› where
  ‹vcontrib G Shn T its it = (if is_slot G it then
     List.map_filter (λkk. if is_slot G (its ! kk) then None else
       (case vnext_nt G (its ! kk) of None ⇒ None
        | Some (B, q) ⇒ Some (kk, ecomp (trow T (nnum G Shn B) ! nnum G Shn (fst (fst it))) (of_rel q))))
       [0..<length its]
   else [])›

text ‹The kernel of a successor under ‹X›: per item of the successor state, the
  position of its predecessor in the state left and the relation of the symbol
  crossed.›

definition vkmap :: ‹('n, 't) citem list ⇒ ('n, 't) sym ⇒ ('n, 't) citem list ⇒
    (nat × irel) option list› where
  ‹vkmap its X its' = map (λ(p, m). if 0 < m ∧ m ≤ length (snd p) ∧ fst (snd p ! (m - 1)) = X
     then Some (ntidx its (p, m - 1), snd (snd p ! (m - 1))) else None) its'›

definition ventry :: ‹('n, 't) is_cfg ⇒ (('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    nat ⇒ ('n, 't) sym ⇒ (nat × (nat × irel) option list) option› where
  ‹ventry G gt sts j X = (let j' = dnext gt sts j X in
     if j' < length sts then Some (j', vkmap (vits G sts j) X (vits G sts j')) else None)›

text ‹The completed items of a state, each at its first position, with the
  number of the nonterminal it reduces to; the reduce cells per token and at the
  end of the input, by position.›

definition vcomps :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list ⇒ (nat × nat × ('n × ('n, 't) rhs)) list› where
  ‹vcomps G Shn its = List.map_filter (λs. case its ! s of (pr, m) ⇒
     if m = length (snd pr) ∧ ntidx its (pr, m) = s then Some (s, nnum G Shn (fst pr), pr) else None)
     [0..<length its]›

definition vcells :: ‹('n, 't) citem list ⇒ nat ⇒ ('n, 't) lacell list ⇒ 't option ⇒ (nat × wrel) list› where
  ‹vcells its j cells t = List.map_filter (λ(i', (pr, n), t', τ).
     if i' = j ∧ n = length (snd pr) ∧ t' = t then Some (ntidx its (pr, n), τ) else None) cells›

text ‹The tokens the tables number: the grammar's terminals and those of the
  reduce cells.›

definition vtoks :: ‹('n, 't) is_cfg ⇒ ('n, 't) lacell list list ⇒ 't list› where
  ‹vtoks G redtab = remdups ([a. Tm a ← gram_syms G] @
     List.map_filter (λ(i', itm, t, τ). t) (concat redtab))›

datatype ('n, 't) vtab = VTab
  (v_lal: ‹('t × nat) list›)
  (v_miss: nat)
  (v_sh: ‹(nat × (nat × irel) option list) option iarray iarray›)
  (v_go: ‹(nat × (nat × irel) option list) option iarray iarray›)
  (v_ct: ‹(nat × eff) list list iarray›)
  (v_cp: ‹(nat × nat × ('n × ('n, 't) rhs)) list iarray›)
  (v_cl: ‹(nat × wrel) list iarray iarray›)
  (v_ce: ‹nat list iarray›)
  (v_fin: ‹nat iarray›)
  (v_av0: ‹nat × indrep list›)
  (v_ind0: nat)

definition vnum :: ‹('n, 't) vtab ⇒ 't ⇒ nat› where
  ‹vnum V a = (case map_of (v_lal V) a of Some l ⇒ l | None ⇒ v_miss V)›

subsection ‹The driver›

text ‹A successor frame: the kernel anchors through the predecessor map, then
  the slots from the kernel; no frame when the kernel is dead.›

definition vkav :: ‹(nat × irel) option list ⇒ indrep list ⇒ indrep ⇒ indrep list› where
  ‹vkav km av RA = map (λx. case x of None ⇒ FinRep [] | Some (ps, q) ⇒ cpre q RA (getR av ps)) km›

definition vfill :: ‹(nat × eff) list list ⇒ indrep list ⇒ indrep list› where
  ‹vfill cts kav = map (λ(R, cs). fold (λ(kk, e) acc. cunion acc (eapp e (getR kav kk))) cs R)
     (zip kav cts)›

definition vgo :: ‹('n, 't) vtab ⇒ nat × (nat × irel) option list ⇒ indrep list ⇒ indrep ⇒
    (nat × indrep list) option› where
  ‹vgo V e av RA = (case e of (j', km) ⇒ let kav = vkav km av RA in
     if list_ex irep_nonempty kav then Some (j', vfill (iget (v_ct V) j' []) kav) else None)›

datatype ('n, 't) vact = VShift | VReduce nat nat ‹'n × ('n, 't) rhs›

fun vdec :: ‹('n, 't) vact ⇒ ('n, 't) dact› where
  ‹vdec VShift = DShift›
| ‹vdec (VReduce s b pr) = DReduce pr›

type_synonym vframes = ‹(nat × indrep list) list›

definition vmstep :: ‹('n, 't) vtab ⇒ vframes × ('t × nat) list ⇒ ('n, 't) vact ⇒
    (vframes × ('t × nat) list) option› where
  ‹vmstep V fw act = (case fw of (fs, w) ⇒ (case fs of [] ⇒ None | (j, av) # _ ⇒
     (case act of
        VShift ⇒ (case w of [] ⇒ None | (a, c) # w' ⇒
          (case iget (iget (v_sh V) j (IArray [])) (vnum V a) None of None ⇒ None
           | Some e ⇒ map_option (λf. (f # fs, w')) (vgo V e av (FinRep [c]))))
      | VReduce s b pr ⇒ (let n = length (snd pr) in
          if n < length fs then (case fs ! n of (j0, av0) ⇒
            (case iget (iget (v_go V) j0 (IArray [])) b None of None ⇒ None
             | Some e ⇒ map_option (λf. (f # drop n fs, w)) (vgo V e av0 (getR av s))))
          else None))))›

definition vlic :: ‹('n, 't) vtab ⇒ nat ⇒ ('t × nat) list ⇒ nat ⇒ indrep ⇒ bool› where
  ‹vlic V j w s RS = (case w of [] ⇒ s ∈ set (iget (v_ce V) j [])
     | (a, c) # _ ⇒ list_ex (λ(s', τ). s' = s ∧ irep_ex_wsat τ c RS)
         (iget (iget (v_cl V) j (IArray [])) (vnum V a) []))›

definition vcands :: ‹('n, 't) vtab ⇒ nat ⇒ indrep list ⇒ ('t × nat) list ⇒ ('n, 't) vact list› where
  ‹vcands V j av w = (let reds = map (λ(s, b, pr). VReduce s b pr)
       (filter (λ(s, b, pr). let RS = getR av s in irep_nonempty RS ∧ vlic V j w s RS) (iget (v_cp V) j []))
     in (case w of [] ⇒ reds | _ ⇒ VShift # reds))›

fun vpick :: ‹('n, 't) vtab ⇒ vframes × ('t × nat) list ⇒ ('n, 't) vact list ⇒
    (('n, 't) vact × vframes × ('t × nat) list) option› where
  ‹vpick V fw [] = None›
| ‹vpick V fw (act # acts) = (case vmstep V fw act of Some r ⇒ Some (act, r) | None ⇒ vpick V fw acts)›

type_synonym ('m, 'ch, 'n, 't) vst =
  ‹vframes × ('t × nat) list × ('m, 'ch, 't) tword × ('m, 'ch, 'n, 't) ast list›

definition vfinal :: ‹('n, 't) vtab ⇒ ('m, 'ch, 'n, 't) vst ⇒ bool› where
  ‹vfinal V st = (case st of (fs, w, v, tstk) ⇒ w = [] ∧ (case fs of [] ⇒ False
     | (j, av) # _ ⇒ irep_mem (v_ind0 V) (getR av (iget (v_fin V) j 0))))›

text ‹The tables of a grammar.›

definition vinit_frame :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) stab ⇒ ('n, 't) citem list list ⇒ nat × indrep list› where
  ‹vinit_frame G Shn T sts = (let i0 = st_find sts (lr0_start G Shn); its = vits G sts i0 in
     (i0, vfill (map (vcontrib G Shn T its) its)
       (map (λit. if it = (start_prod G Shn, 0) then FinRep [istart_ind G] else FinRep []) its)))›

definition mk_vtab :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) stab ⇒ ('n, 't) citem list list ⇒
    (('n, 't) sym × nat) list list ⇒ ('n, 't) lacell list list ⇒ ('n, 't) vtab› where
  ‹mk_vtab G Shn T sts gt redtab = (let toks = vtoks G redtab; ns = [0..<length sts];
       ps = eprods G Shn in
     VTab (zip toks [0..<length toks]) (length toks)
       (IArray (map (λj. IArray (map (λa. ventry G gt sts j (Tm a)) toks)) ns))
       (IArray (map (λj. IArray (map (λb. ventry G gt sts j (Nt (fst (ps ! b)))) [0..<length ps])) ns))
       (IArray (map (λj. map (vcontrib G Shn T (vits G sts j)) (vits G sts j)) ns))
       (IArray (map (λj. vcomps G Shn (vits G sts j)) ns))
       (IArray (map (λj. IArray (map (λa. vcells (vits G sts j) j (redtab ! j) (Some a)) toks)) ns))
       (IArray (map (λj. map fst (vcells (vits G sts j) j (redtab ! j) None)) ns))
       (IArray (map (λj. ntidx (vits G sts j) (start_prod G Shn, 1)) ns))
       (vinit_frame G Shn T sts)
       (istart_ind G))›



section ‹The vector driver runs the dense one›

subsection ‹Anchor sets by item›

text ‹The anchors an item list gives a core item, over all its copies; only
  this enters the relation between a frame of the dense driver and a vector of
  anchor sets.›

definition aset :: ‹('n, 't) xitem list ⇒ ('n, 't) citem ⇒ nat set› where
  ‹aset xs it = ⋃ {irep_set R |R. (fst it, snd it, R) ∈ set xs}›

lemma aset_Nil [simp]: ‹aset [] it = {}›
  by (simp add: aset_def)

lemma aset_Cons [simp]:
  ‹aset ((p, m, R) # xs) it = (if (p, m) = it then irep_set R else {}) ∪ aset xs it›
  by (cases it) (auto simp: aset_def)

lemma aset_append [simp]: ‹aset (xs @ ys) it = aset xs it ∪ aset ys it›
  by (auto simp: aset_def)

lemma aset_filter_ine [simp]: ‹aset (filter ine xs) it = aset xs it›
  by (auto simp: aset_def ine_def)

lemma aset_xeq: ‹xeq xs ys ⟹ aset xs it = aset ys it›
  unfolding xrel_def by (induction rule: list_all2_induct) (auto split: prod.splits)

lemma aset_red: ‹irep_set (red_set CL pr) = aset CL (pr, length (snd pr))›
  by (simp add: red_set_correct aset_def)

lemma aset_ne_lcore: ‹aset xs it ≠ {} ⟷ it ∈ lcore xs›
  by (cases it) (auto simp: aset_def lcore_def)

lemma aset_notin: ‹it ∉ lcore xs ⟹ aset xs it = {}›
  using aset_ne_lcore by blast

lemma live_aset: ‹live xs ⟷ (∃it. aset xs it ≠ {})›
  by (auto simp: live_lcore aset_ne_lcore)

lemma aset_lgoto:
  ‹aset (lgoto xs X RA) (p, m) = (if 0 < m ∧ m ≤ length (snd p) ∧ fst (snd p ! (m - 1)) = X
     then aset xs (p, m - 1) ∩ irep_set (irep_pre (snd (snd p ! (m - 1))) RA) else {})›
proof (induction xs)
  case (Cons x xs)
  obtain p' m' R where x: ‹x = (p', m', R)› by (cases x)
  show ?case
    using Cons.IH by (cases m) (auto simp: x lgoto_def)
qed (simp add: lgoto_def)



subsection ‹The closure by item›

text ‹The closure's anchor set at an item: the kernel's, and at a slot the
  transfers from every kernel item expecting a nonterminal.  The route is the
  sparse closure (const‹sclosure›), whose fixpoint is the union of the paths
  (@{thm [source] sfix_trow}).›

definition venc :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) xitem list ⇒ ('n, 't) sitem list› where
  ‹venc G Shn X = map (λ(p, m, R). (mkrec (eprods G Shn) p, m, R)) (filter ine X)›

lemma map_sdec_venc: ‹map sdec (venc G Shn X) = filter ine X›
  by (induction X) (auto simp: venc_def)

lemma skrel_venc:
  assumes ‹⋀p m R. (p, m, R) ∈ set X ⟹ irep_nonempty R ⟹ p ∈ set (eprods G Shn)›
  shows ‹skrel G Shn X (venc G Shn X)›
proof -
  have ‹swf (eprods G Shn) (venc G Shn X)› unfolding swf_def
  proof
    fix x assume ‹x ∈ set (venc G Shn X)›
    then obtain p m R where ‹(p, m, R) ∈ set X› ‹irep_nonempty R› ‹x = (mkrec (eprods G Shn) p, m, R)›
      by (auto simp: venc_def)
    with assms show ‹case x of (r, m, R) ⇒ r ∈ mkrec (eprods G Shn) ` set (eprods G Shn)› by auto
  qed
  then show ?thesis by (simp add: skrel_def map_sdec_venc)
qed

lemma sfix_loop_some:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and r: ‹skrel G Shn K Ks›
  shows ‹sfix_loop T (skn T Ks) ≠ None›
proof -
  let ?kn = ‹skn T Ks›
  obtain k where ‹xstable G K (xiter G K k)›
    using xcls_stable_ex by blast
  then have ‹while_option (λt. ¬ xstable G K (xiter G K t)) Suc 0 = Some (xfuel G K)›
    unfolding xfuel_def by (rule nat_search_Some)
  moreover have
    ‹map_option (λt. (siter T ?kn t, siter T ?kn (Suc t)))
       (while_option (λt. ¬ xstable G K (xiter G K t)) Suc 0) =
     while_option (λ(N, N'). ¬ ssub N' N) (λ(N, N'). (N', sround T ?kn N'))
       (siter T ?kn 0, siter T ?kn (Suc 0))›
    by (rule while_option_commute[where f = ‹λt. (siter T ?kn t, siter T ?kn (Suc t))› and s = 0])
      (simp_all only: xstable_diter[OF xeq_refl] ssub_lockstep[OF T r, simplified siter_simps] siter_simps case_prod_conv)
  ultimately have
    ‹while_option (λ(N, N'). ¬ ssub N' N) (λ(N, N'). (N', sround T ?kn N')) ([], sround T ?kn []) =
     Some (siter T ?kn (xfuel G K), siter T ?kn (Suc (xfuel G K)))›
    by simp
  then show ?thesis by (simp add: sfix_loop_def)
qed

lemma skn_key_less:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and w: ‹swf (eprods G Shn) Ks›
    and b: ‹(b, R) ∈ set (skn T Ks)›
  shows ‹b < s_np T›
proof -
  from b skn_keys[OF T w] have ‹b ∈ set (lids G Shn)› by force
  then obtain k where ‹k < length (iprods G)› ‹lids G Shn ! k = b› by (auto simp: in_set_conv_nth)
  with lids_nth_le[of k G Shn] show ?thesis by (simp add: T)
qed

lemma sitem_nx_vnext:
  ‹sitem_nx (length (iprods G)) (mkrec (eprods G Shn) p, m, R) =
     map_option (λ(B, q). (nnum G Shn B, irep_img q R)) (vnext_nt G (p, m))›
proof (cases ‹m < length (snd p)›)
  case True
  obtain X q where Xq: ‹snd p ! m = (X, q)› by (cases ‹snd p ! m›)
  show ?thesis
  proof (cases X)
    case (Nt B)
    with True Xq lhs_id_less[of G Shn B] show ?thesis
      by (cases p) (simp add: sitem_nx_def vnext_nt_def nnum_def)
  qed (use True Xq in ‹cases p, simp add: sitem_nx_def vnext_nt_def›)
qed (cases p, simp add: sitem_nx_def vnext_nt_def)

text ‹The transfers into a nonterminal, summed over the kernel's items.›

definition vin :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) stab ⇒ ('n, 't) xitem list ⇒ nat ⇒ nat set› where
  ‹vin G Shn T X a = ⋃{eff_set (ecomp (trow T (nnum G Shn B) ! a) (of_rel q)) (aset X it) |it B q.
     vnext_nt G it = Some (B, q)}›

lemma skn_paths:
  assumes T: ‹T = mk_stab G Shn gt sts redtab›
  shows ‹(⋃(b, R) ∈ set (skn T (venc G Shn X)). eff_set (trow T b ! a) (irep_set R)) = vin G Shn T X a›
proof (rule set_eqI)
  fix x
  have im: ‹aset X it = ⋃ (irep_set ` {R. (fst it, snd it, R) ∈ set X})› for it
    unfolding aset_def by blast
  have sub: ‹(fst it, snd it, R) ∈ set X ⟹ irep_set R ⊆ aset X it› for R it
    unfolding im by blast
  have D: ‹x ∈ eff_set e (aset X it) ⟹ ∃R. (fst it, snd it, R) ∈ set X ∧ x ∈ eff_set e (irep_set R)› for e it
    unfolding im eff_set_UN by blast
  let ?E = ‹λB q. ecomp (trow T (nnum G Shn B) ! a) (of_rel q)›
  have mv: ‹x ∈ vin G Shn T X a ⟷ (∃p m R B q. (p, m, R) ∈ set X ∧ vnext_nt G (p, m) = Some (B, q) ∧
      x ∈ eff_set (?E B q) (irep_set R))› (is ‹_ ⟷ ?r›)
  proof
    assume ‹x ∈ vin G Shn T X a›
    then obtain it B q where i: ‹vnext_nt G it = Some (B, q)› ‹x ∈ eff_set (?E B q) (aset X it)›
      unfolding vin_def by blast
    from D[OF i(2)] obtain R where ‹(fst it, snd it, R) ∈ set X› ‹x ∈ eff_set (?E B q) (irep_set R)›
      by blast
    with i(1) show ?r by (metis prod.collapse)
  next
    assume ?r
    then obtain p m R B q where r: ‹(p, m, R) ∈ set X› ‹vnext_nt G (p, m) = Some (B, q)›
      ‹x ∈ eff_set (?E B q) (irep_set R)› by blast
    have ‹irep_set R ⊆ aset X (p, m)› using sub[of ‹(p, m)› R] r(1) by simp
    from eff_set_mono[OF this, of ‹?E B q›] r(3) have ‹x ∈ eff_set (?E B q) (aset X (p, m))›
      by blast
    with r(2) show ‹x ∈ vin G Shn T X a› unfolding vin_def by blast
  qed
  have nx: ‹sitem_nx (s_np T) (mkrec (eprods G Shn) p, m, R) =
      map_option (λ(B, q). (nnum G Shn B, irep_img q R)) (vnext_nt G (p, m))› for p m R
    using sitem_nx_vnext by (simp add: T)
  have ev: ‹eff_set (?E B q) (irep_set R) = eff_set (trow T (nnum G Shn B) ! a) (irep_set (irep_img q R))›
    for B q R by (simp only: eff_set_comp eff_set_img)
  have sk: ‹(b, R) ∈ set (skn T (venc G Shn X)) ⟷
      R ≠ FinRep [] ∧ (∃s ∈ set (venc G Shn X). sitem_nx (s_np T) s = Some (b, R))› for b R
    by (auto simp: skn_def in_map_filter)
  have vc: ‹s ∈ set (venc G Shn X) ⟷
      (∃p m R. (p, m, R) ∈ set X ∧ irep_nonempty R ∧ s = (mkrec (eprods G Shn) p, m, R))› for s
    by (force simp: venc_def)
  show ‹x ∈ (⋃(b, R) ∈ set (skn T (venc G Shn X)). eff_set (trow T b ! a) (irep_set R)) ⟷ x ∈ vin G Shn T X a›
  proof
    assume ‹x ∈ (⋃(b, R) ∈ set (skn T (venc G Shn X)). eff_set (trow T b ! a) (irep_set R))›
    then obtain b R where bR: ‹(b, R) ∈ set (skn T (venc G Shn X))› ‹x ∈ eff_set (trow T b ! a) (irep_set R)›
      by blast
    then obtain s where s: ‹s ∈ set (venc G Shn X)› ‹sitem_nx (s_np T) s = Some (b, R)›
      unfolding sk by blast
    then obtain p m R' where ‹(p, m, R') ∈ set X› ‹s = (mkrec (eprods G Shn) p, m, R')›
      unfolding vc by blast
    with s(2) have pm: ‹(p, m, R') ∈ set X›
        ‹sitem_nx (s_np T) (mkrec (eprods G Shn) p, m, R') = Some (b, R)›
      by simp_all
    then obtain B q where v: ‹vnext_nt G (p, m) = Some (B, q)›
        and br: ‹b = nnum G Shn B› ‹R = irep_img q R'›
      unfolding nx by auto
    from bR(2) have ‹x ∈ eff_set (?E B q) (irep_set R')› unfolding ev br .
    with pm(1) v show ‹x ∈ vin G Shn T X a› unfolding mv by blast
  next
    assume ‹x ∈ vin G Shn T X a›
    then obtain p m R B q where r: ‹(p, m, R) ∈ set X› ‹vnext_nt G (p, m) = Some (B, q)›
        ‹x ∈ eff_set (?E B q) (irep_set R)›
      unfolding mv by blast
    then have ne: ‹irep_nonempty R› by (metis empty_iff eff_set_empty irep_nonempty_correct)
    from r(3) have x: ‹x ∈ eff_set (trow T (nnum G Shn B) ! a) (irep_set (irep_img q R))› by (simp only: ev)
    then have ‹irep_set (irep_img q R) ≠ {}› by (metis empty_iff eff_set_empty)
    then have i: ‹irep_img q R ≠ FinRep []› by (metis irep_nonempty_iff irep_nonempty_correct)
    have s: ‹(mkrec (eprods G Shn) p, m, R) ∈ set (venc G Shn X)› unfolding vc using r(1) ne by blast
    have ‹(nnum G Shn B, irep_img q R) ∈ set (skn T (venc G Shn X))›
      unfolding sk by (intro conjI i bexI[OF _ s]) (simp add: nx r(2))
    with x show ‹x ∈ (⋃(b, R) ∈ set (skn T (venc G Shn X)). eff_set (trow T b ! a) (irep_set R))›
      by blast
  qed
qed

lemma slk_sfix_vin:
  assumes T: ‹T = mk_stab G Shn gt sts redtab›
    and w: ‹⋀p m R. (p, m, R) ∈ set X ⟹ irep_nonempty R ⟹ p ∈ set (eprods G Shn)›
    and A: ‹A ∈ fst ` set (iprods G)›
  shows ‹irep_set (slk (sfix T (skn T (venc G Shn X))) (nnum G Shn A)) = vin G Shn T X (nnum G Shn A)›
proof -
  have r: ‹skrel G Shn X (venc G Shn X)› by (rule skrel_venc[OF w])
  have ok: ‹ntl_ok T› by (simp add: T ntl_ok_mk_stab)
  have a: ‹nnum G Shn A < s_np T› using A lhs_id_less[of G Shn A] by (simp add: T nnum_def)
  have ‹irep_set (slk (sfix T (skn T (venc G Shn X))) (nnum G Shn A)) =
      (⋃(b, R) ∈ set (skn T (venc G Shn X)). eff_set (trow T b ! nnum G Shn A) (irep_set R))›
    by (rule sfix_trow[OF ok sfix_loop_some[OF T r] skn_key_less[OF T skrel_swf[OF r]] a])
  then show ?thesis by (simp add: skn_paths[OF T])
qed

lemma cl_aset:
  assumes T: ‹T = mk_stab G Shn gt sts redtab›
    and w: ‹⋀p m R. (p, m, R) ∈ set X ⟹ irep_nonempty R ⟹ p ∈ set (eprods G Shn)›
  shows ‹aset (xclosure_auto G X) it =
    aset X it ∪ (if is_slot G it then vin G Shn T X (nnum G Shn (fst (fst it))) else {})›
proof -
  let ?n = ‹length (iprods G)›
  let ?Ks = ‹venc G Shn X›
  let ?N = ‹sfix T (skn T ?Ks)›
  let ?ks = ‹filter (λk. lids G Shn ! k ∈ fst ` set ?N) [0..<?n]›
  have r: ‹skrel G Shn X ?Ks› by (rule skrel_venc[OF w])
  have inv: ‹sinv G Shn ?N›
    unfolding sfix_siter[OF T r] by (rule siter_inv[OF T skrel_swf[OF r]])
  have fne: ‹filter (λ(_, _, R). irep_nonempty R) ?Ks = filter ine ?Ks›
    by (rule filter_cong) (auto simp: ine_def simp del: irep_nonempty_correct)
  have sparse: ‹map sdec (sclosure T ?Ks) =
      map sdec (filter ine ?Ks) @ map (λk. (iprods G ! k, 0, slk ?N (lids G Shn ! k))) ?ks›
    using inv unfolding sclosure_def Let_def fne sinv_def
    by (simp add: ntl_concat[OF T] recs_sel[OF T] del: IArray.sub_def cong: map_cong)
  have kern: ‹aset (map sdec (filter ine ?Ks)) it = aset X it›
    by (simp add: map_sdec_filter map_sdec_venc)
  have slots: ‹aset (map (λk. (iprods G ! k, 0, slk ?N (lids G Shn ! k))) ?ks) it =
      (if is_slot G it then irep_set (slk ?N (nnum G Shn (fst (fst it)))) else {})›
    proof (cases ‹is_slot G it›)
    case True
    let ?b = ‹nnum G Shn (fst (fst it))›
    let ?S = ‹{irep_set R |R. (fst it, snd it, R) ∈ set (map (λk. (iprods G ! k, 0, slk ?N (lids G Shn ! k))) ?ks)}›
    have l: ‹lids G Shn ! k = ?b› if ‹k < ?n› ‹iprods G ! k = fst it› for k
      using that by (simp add: lids_nth nnum_def)
    from True obtain k where k: ‹k < ?n› ‹iprods G ! k = fst it› ‹snd it = 0›
      by (auto simp: is_slot_def in_set_conv_nth)
    have sub: ‹?S ⊆ {irep_set (slk ?N ?b)}› using l by auto
    show ?thesis
    proof (cases ‹?b ∈ fst ` set ?N›)
      case True
      have ‹(fst it, snd it, slk ?N ?b) ∈ set (map (λk. (iprods G ! k, 0, slk ?N (lids G Shn ! k))) ?ks)›
        using k True l[OF k(1,2)] by (force intro!: image_eqI[of _ _ k])
      then have ‹?S = {irep_set (slk ?N ?b)}› using sub by blast
      with ‹is_slot G it› show ?thesis by (simp add: aset_def)
    next
      case False
      then have ‹irep_set (slk ?N ?b) = {}› by (simp add: slk_notin)
      with sub ‹is_slot G it› show ?thesis unfolding aset_def by auto
    qed
  next
    case False
    then show ?thesis by (auto simp: aset_def is_slot_def)
  qed
  have ‹aset (xclosure_auto G X) it = aset (filter ine (dclosure G X)) it›
    by (simp add: aset_xeq[OF xclosure_auto_dclosure[OF xeq_refl]])
  also have ‹… = aset (map sdec (sclosure T ?Ks)) it› by (rule aset_xeq[OF sclosure_rel[OF T r]])
  also have ‹… = aset X it ∪ (if is_slot G it then irep_set (slk ?N (nnum G Shn (fst (fst it)))) else {})›
    unfolding sparse aset_append kern slots ..
  also have ‹… = aset X it ∪ (if is_slot G it then vin G Shn T X (nnum G Shn (fst (fst it))) else {})›
    using slk_sfix_vin[OF T w] by (auto simp: is_slot_def)
  finally show ?thesis .
qed



subsection ‹Filling a frame›

text ‹A kernel vector stands for a kernel ‹X› at the items of a state when it
  holds the kernel's anchor set at every position but the slots, which it leaves
  empty.›

definition vkrel :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list ⇒ ('n, 't) xitem list ⇒ indrep list ⇒ bool› where
  ‹vkrel G its X kav ⟷ length kav = length its ∧
     (∀s < length its. irep_set (kav ! s) = (if is_slot G (its ! s) then {} else aset X (its ! s)))›

lemma fold_cunion_set:
  ‹irep_set (fold (λ(kk, e) acc. cunion acc (eapp e (getR kav kk))) cs R) =
     irep_set R ∪ (⋃(kk, e) ∈ set cs. eff_set e (irep_set (getR kav kk)))›
  by (induction cs arbitrary: R) auto

lemma length_vfill [simp]: ‹length (vfill cts kav) = min (length kav) (length cts)›
  by (simp add: vfill_def)

lemma vfill_nth:
  ‹s < length kav ⟹ s < length cts ⟹
   vfill cts kav ! s = fold (λ(kk, e) acc. cunion acc (eapp e (getR kav kk))) (cts ! s) (kav ! s)›
  by (simp add: vfill_def)

lemma vcontrib_set:
  ‹(kk, e) ∈ set (vcontrib G Shn T its it) ⟷ is_slot G it ∧ kk < length its ∧ ¬ is_slot G (its ! kk) ∧
     (∃B q. vnext_nt G (its ! kk) = Some (B, q) ∧
        e = ecomp (trow T (nnum G Shn B) ! nnum G Shn (fst (fst it))) (of_rel q))›
proof -
  let ?f = ‹λkk. if is_slot G (its ! kk) then None else
       (case vnext_nt G (its ! kk) of None ⇒ None
        | Some (B, q) ⇒ Some (kk, ecomp (trow T (nnum G Shn B) ! nnum G Shn (fst (fst it))) (of_rel q)))›
  have f: ‹?f x = Some (kk, e) ⟷ x = kk ∧ ¬ is_slot G (its ! kk) ∧
      (∃B q. vnext_nt G (its ! kk) = Some (B, q) ∧
        e = ecomp (trow T (nnum G Shn B) ! nnum G Shn (fst (fst it))) (of_rel q))› for x
    by (auto split: option.splits)
  show ?thesis
  proof (cases ‹is_slot G it›)
    case True
    then show ?thesis unfolding vcontrib_def by (simp only: True if_True in_map_filter f) auto
  qed (simp add: vcontrib_def)
qed

lemma vfill_cl:
  assumes T: ‹T = mk_stab G Shn gt sts redtab›
    and w: ‹⋀p m R. (p, m, R) ∈ set X ⟹ irep_nonempty R ⟹ p ∈ set (eprods G Shn)›
    and k: ‹vkrel G its X kav›
    and cov: ‹⋀it. aset X it ≠ {} ⟹ it ∈ set its›
    and ns: ‹⋀it. is_slot G it ⟹ aset X it = {}›
    and s: ‹s < length its›
  shows ‹irep_set (vfill (map (vcontrib G Shn T its) its) kav ! s) = aset (xclosure_auto G X) (its ! s)›
proof -
  let ?it = ‹its ! s›
  let ?C = ‹⋃(kk, e) ∈ set (vcontrib G Shn T its ?it). eff_set e (irep_set (getR kav kk))›
  have cl: ‹aset (xclosure_auto G X) it =
      aset X it ∪ (if is_slot G it then vin G Shn T X (nnum G Shn (fst (fst it))) else {})› for it
    by (rule cl_aset[OF T]) (rule w)
  have lk: ‹length kav = length its› using k by (simp add: vkrel_def)
  have v: ‹irep_set (vfill (map (vcontrib G Shn T its) its) kav ! s) = irep_set (kav ! s) ∪ ?C›
    using s lk by (simp add: vfill_nth fold_cunion_set)
  show ?thesis
  proof (cases ‹is_slot G ?it›)
    case False
    then have ‹vcontrib G Shn T its ?it = []› by (simp add: vcontrib_def)
    with False k s show ?thesis unfolding v cl by (simp add: vkrel_def)
  next
    case True
    let ?a = ‹nnum G Shn (fst (fst ?it))›
    have C: ‹?C = vin G Shn T X ?a›
    proof (rule set_eqI, rule iffI)
      fix x assume ‹x ∈ ?C›
      then obtain kk e where c: ‹(kk, e) ∈ set (vcontrib G Shn T its ?it)›
          and x: ‹x ∈ eff_set e (irep_set (getR kav kk))›
        by blast
      from c obtain B q where kk: ‹kk < length its› ‹¬ is_slot G (its ! kk)›
          and B: ‹vnext_nt G (its ! kk) = Some (B, q)›
          and e: ‹e = ecomp (trow T (nnum G Shn B) ! ?a) (of_rel q)›
        unfolding vcontrib_set by blast
      have ‹irep_set (getR kav kk) = aset X (its ! kk)›
        using k kk lk by (simp add: vkrel_def getR_def)
      with x e have ‹x ∈ eff_set (ecomp (trow T (nnum G Shn B) ! ?a) (of_rel q)) (aset X (its ! kk))›
        by simp
      with B show ‹x ∈ vin G Shn T X ?a› unfolding vin_def by blast
    next
      fix x assume ‹x ∈ vin G Shn T X ?a›
      then obtain it' B q where B: ‹vnext_nt G it' = Some (B, q)›
          and x: ‹x ∈ eff_set (ecomp (trow T (nnum G Shn B) ! ?a) (of_rel q)) (aset X it')›
        unfolding vin_def by blast
      then have ‹aset X it' ≠ {}› by (metis empty_iff eff_set_empty)
      then have it': ‹it' ∈ set its› ‹¬ is_slot G it'› using cov ns by blast+
      then obtain kk where kk: ‹kk < length its› ‹its ! kk = it'› by (auto simp: in_set_conv_nth)
      have ‹irep_set (getR kav kk) = aset X it'›
        using k kk lk it'(2) by (simp add: vkrel_def getR_def)
      moreover have ‹(kk, ecomp (trow T (nnum G Shn B) ! ?a) (of_rel q)) ∈ set (vcontrib G Shn T its ?it)›
        unfolding vcontrib_set using True kk it'(2) B by blast
      ultimately show ‹x ∈ ?C› using x by (intro UN_I) auto
    qed
    have ‹irep_set (kav ! s) = {}› using True k s by (simp add: vkrel_def)
    with True show ?thesis unfolding v C cl by (simp add: ns)
  qed
qed



subsection ‹The successor's kernel›

text ‹A frame stands for a closure ‹CL› when it holds the closure's anchor set at
  every item of its state.›

definition vfr :: ‹('n, 't) xitem list ⇒ ('n, 't) citem list ⇒ indrep list ⇒ bool› where
  ‹vfr CL its av ⟷ length av = length its ∧ (∀s < length its. irep_set (av ! s) = aset CL (its ! s))›

lemma vfr_getR:
  assumes fr: ‹vfr CL its av› and cov: ‹lcore CL ⊆ set its›
  shows ‹irep_set (getR av (ntidx its it)) = aset CL it›
proof (cases ‹it ∈ set its›)
  case True
  then have ‹ntidx its it < length its› ‹its ! ntidx its it = it› by (simp_all add: ntidx_less ntidx_nth)
  with fr show ?thesis by (simp add: vfr_def getR_def)
next
  case False
  with cov have ‹aset CL it = {}› by (intro aset_notin) blast
  with False fr show ?thesis by (simp add: vfr_def getR_def ntidx_notin)
qed

lemma length_vkav [simp]: ‹length (vkav km av RA) = length km›
  by (simp add: vkav_def)

lemma length_vkmap [simp]: ‹length (vkmap its X its') = length its'›
  by (simp add: vkmap_def)

lemma vkav_krel:
  assumes fr: ‹vfr CL its av› and cov: ‹lcore CL ⊆ set its›
  shows ‹vkrel G its' (lgoto CL X RA) (vkav (vkmap its X its') av RA)›
  unfolding vkrel_def
proof (intro conjI allI impI)
  fix s assume s: ‹s < length its'›
  obtain p m where pm: ‹its' ! s = (p, m)› by (cases ‹its' ! s›)
  have ‹irep_set (vkav (vkmap its X its') av RA ! s) =
      (if 0 < m ∧ m ≤ length (snd p) ∧ fst (snd p ! (m - 1)) = X
       then aset CL (p, m - 1) ∩ irep_set (irep_pre (snd (snd p ! (m - 1))) RA) else {})›
    using s pm vfr_getR[OF fr cov] by (simp add: vkav_def vkmap_def)
  then show ‹irep_set (vkav (vkmap its X its') av RA ! s) =
      (if is_slot G (its' ! s) then {} else aset (lgoto CL X RA) (its' ! s))›
    by (simp add: pm aset_lgoto is_slot_def)
qed simp


subsection ‹Frames of a reachable configuration›

text ‹Every frame of a reachable configuration is live: a step pushes a live
  frame and keeps a suffix of the old stack.  So every frame has a state, its
  closure stays inside that state's items, and its anchored items come from the
  productions the sparse tables number.›

lemma imreach_frames_live:
  ‹imreach G Shn gt sts ic ⟹ X ∈ set (fst (fst ic)) ⟹ live X›
proof (induction arbitrary: X rule: imreach.induct)
  case (imreach_init w)
  then show ?case by (simp add: xinit_def live_def)
next
  case (imreach_step ic act ic')
  obtain Xs w istk where ic: ‹ic = ((Xs, w), istk)› by (metis prod.exhaust)
  obtain Xs' w' istk' where ic': ‹ic' = ((Xs', w'), istk')› by (metis prod.exhaust)
  have ms: ‹mstep_cached G (map (xclosure_auto G) Xs) (Xs, w) act = Some (Xs', w')›
    using imstep_mstep[OF imreach_step.hyps(2)] by (simp add: ic ic' mstep_def)
  have hd: ‹live (hd Xs')› and ne: ‹Xs' ≠ []›
    using imreach_step.hyps(3) by (simp_all add: ic' dlive_def)
  have tl: ‹set (tl Xs') ⊆ set Xs›
  proof (cases act)
    case DShift
    show ?thesis by (rule mstep_shift_shape[OF ms[unfolded DShift]]) auto
  next
    case (DReduce pr)
    show ?thesis by (rule mstep_reduce_shape[OF ms[unfolded DReduce]]) (auto dest: in_set_dropD)
  qed
  from ne obtain Y Ys where Xs': ‹Xs' = Y # Ys› by (cases Xs') auto
  from imreach_step.prems hd tl imreach_step.IH show ?case by (auto simp: ic ic' Xs')
qed

lemma didx_ok_drop: ‹didx_ok G sts Xs istk ⟹ didx_ok G sts (drop k Xs) (drop k istk)›
  by (auto simp: didx_ok_def)

lemma frame_cov:
  assumes ok: ‹didx_ok G sts Xs istk› and k: ‹k < length Xs› and lv: ‹live (Xs ! k)›
  shows ‹istk ! k < length sts› and ‹lcore (xclosure_auto G (Xs ! k)) ⊆ set (vits G sts (istk ! k))›
proof -
  have ok': ‹didx_ok G sts (drop k Xs) (drop k istk)› by (rule didx_ok_drop[OF ok])
  have ne: ‹drop k Xs ≠ []› using k by simp
  have li: ‹length istk = length Xs› by (rule didx_ok_len[OF ok])
  have hX: ‹hd (drop k Xs) = Xs ! k› and hi: ‹hd (drop k istk) = istk ! k›
    using k li by (simp_all add: hd_drop_conv_nth)
  from lv obtain pr m R where ‹(pr, m, R) ∈ set (Xs ! k)› and ‹irep_nonempty R›
    unfolding live_def list_ex_iff by fastforce
  moreover from this obtain j where ‹j ∈ irep_set R› by auto
  ultimately have ‹(pr, m, R) ∈ set (xclosure_auto G (hd (drop k Xs)))› and ‹j ∈ irep_set R›
    using hX xclosure_auto_kernel_sub[of ‹Xs ! k› G] by auto
  from didx_ok_creach(1)[OF ok' ne this] show lt: ‹istk ! k < length sts› by (simp add: hi)
  show ‹lcore (xclosure_auto G (Xs ! k)) ⊆ set (vits G sts (istk ! k))›
  proof
    fix it assume ‹it ∈ lcore (xclosure_auto G (Xs ! k))›
    then obtain pr m R where it: ‹it = (pr, m)› and mem: ‹(pr, m, R) ∈ set (xclosure_auto G (Xs ! k))›
      and ‹irep_nonempty R› unfolding lcore_def by blast
    then obtain j where ‹j ∈ irep_set R› by auto
    from didx_ok_creach(2)[OF ok' ne, of pr m R j] mem this hX hi lt
    show ‹it ∈ set (vits G sts (istk ! k))› by (simp add: it vits_def)
  qed
qed

lemma frame_eprods:
  assumes tab: ‹tables_ok G Shn sts gt L› and ok: ‹didx_ok G sts Xs istk› and k: ‹k < length Xs›
    and mem: ‹(p, m, R) ∈ set (Xs ! k)› and R: ‹irep_nonempty R›
  shows ‹p ∈ set (eprods G Shn)›
proof -
  have ‹(p, m) ∈ lcore (Xs ! k)› using mem R unfolding lcore_def by blast
  with didx_okD[OF ok k] have ‹(p, m) ∈ set (sts ! (istk ! k))› and ‹istk ! k < length sts› by auto
  moreover from tab have ‹∀s ∈ set sts. set s ⊆ cuniv G Shn› by (simp add: tables_ok_def)
  ultimately have ‹(p, m) ∈ cuniv G Shn› by (meson nth_mem subsetD)
  then show ?thesis by (auto simp: cuniv_def eprods_def start_prod_def)
qed

lemma closure_eprods:
  assumes tab: ‹tables_ok G Shn sts gt L› and j: ‹j < length sts›
    and mem: ‹it ∈ set (vits G sts j)›
  shows ‹fst it ∈ set (eprods G Shn)›
proof -
  from tab j have ‹set (sts ! j) ⊆ cuniv G Shn› by (simp add: tables_ok_def)
  then have ‹set (vits G sts j) ⊆ cuniv G Shn› using j by (simp add: vits_def creach_univ)
  with mem show ?thesis by (cases it) (auto simp: cuniv_def eprods_def start_prod_def)
qed

text ‹The vector frames stand for the dense ones: same states, and each vector
  holds its frame's closure.›

definition vrel :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list list ⇒ ('n, 't) xitem list list ⇒
    nat list ⇒ vframes ⇒ bool› where
  ‹vrel G sts Xs istk fs ⟷ map fst fs = istk ∧ length Xs = length fs ∧
     (∀k < length fs. vfr (xclosure_auto G (Xs ! k)) (vits G sts (istk ! k)) (snd (fs ! k)))›

lemma vrel_push:
  ‹vrel G sts Xs istk fs ⟹ vfr (xclosure_auto G X) (vits G sts j) av ⟹
     vrel G sts (X # Xs) (j # istk) ((j, av) # fs)›
  by (auto simp: vrel_def nth_Cons split: nat.split)

lemma vrel_drop: ‹vrel G sts Xs istk fs ⟹ vrel G sts (drop n Xs) (drop n istk) (drop n fs)›
  by (auto simp: vrel_def drop_map)

lemma vrel_nth:
  assumes ‹vrel G sts Xs istk fs› and ‹k < length fs›
  shows ‹fst (fs ! k) = istk ! k› and ‹vfr (xclosure_auto G (Xs ! k)) (vits G sts (istk ! k)) (snd (fs ! k))›
  using assms by (auto simp: vrel_def)


subsection ‹Looking up the tables›

lemma map_of_zip_upt:
  ‹map_of (zip xs [k..<k + length xs]) a = (if a ∈ set xs then Some (k + ntidx xs a) else None)›
proof (induction xs arbitrary: k)
  case (Cons x xs)
  from Cons.IH[of ‹Suc k›] show ?case by (auto simp del: upt_Suc simp add: upt_conv_Cons)
qed simp

lemma iget_IArray [simp]: ‹iget (IArray xs) k d = (if k < length xs then xs ! k else d)›
  by (simp add: iget_def)

lemma vnum_mk: ‹V = mk_vtab G Shn T sts gt redtab ⟹ vnum V a = ntidx (vtoks G redtab) a›
  using map_of_zip_upt[of ‹vtoks G redtab› 0 a]
  by (auto simp: vnum_def mk_vtab_def Let_def ntidx_notin)

lemma v_sh_mk:
  assumes V: ‹V = mk_vtab G Shn T sts gt redtab› and j: ‹j < length sts›
  shows ‹iget (iget (v_sh V) j (IArray [])) (vnum V a) None =
    (if a ∈ set (vtoks G redtab) then ventry G gt sts j (Tm a) else None)›
  using j by (simp add: vnum_mk[OF V]) (simp add: V mk_vtab_def Let_def ntidx_less ntidx_nth)

lemma v_go_mk:
  assumes V: ‹V = mk_vtab G Shn T sts gt redtab› and j: ‹j < length sts› and b: ‹b < length (eprods G Shn)›
  shows ‹iget (iget (v_go V) j (IArray [])) b None = ventry G gt sts j (Nt (fst (eprods G Shn ! b)))›
  using j b by (simp add: V mk_vtab_def Let_def del: upt_Suc)

lemma v_ct_mk:
  assumes V: ‹V = mk_vtab G Shn T sts gt redtab› and j: ‹j < length sts›
  shows ‹iget (v_ct V) j [] = map (vcontrib G Shn T (vits G sts j)) (vits G sts j)›
  using j by (simp add: V mk_vtab_def Let_def)

lemma v_cp_mk:
  assumes V: ‹V = mk_vtab G Shn T sts gt redtab› and j: ‹j < length sts›
  shows ‹iget (v_cp V) j [] = vcomps G Shn (vits G sts j)›
  using j by (simp add: V mk_vtab_def Let_def)

lemma v_cl_mk:
  assumes V: ‹V = mk_vtab G Shn T sts gt redtab› and j: ‹j < length sts›
  shows ‹iget (iget (v_cl V) j (IArray [])) (vnum V a) [] =
    (if a ∈ set (vtoks G redtab) then vcells (vits G sts j) j (redtab ! j) (Some a) else [])›
  using j by (simp add: vnum_mk[OF V]) (simp add: V mk_vtab_def Let_def ntidx_less ntidx_nth)

lemma v_ce_mk:
  assumes V: ‹V = mk_vtab G Shn T sts gt redtab› and j: ‹j < length sts›
  shows ‹iget (v_ce V) j [] = map fst (vcells (vits G sts j) j (redtab ! j) None)›
  using j by (simp add: V mk_vtab_def Let_def)

lemma v_fin_mk:
  assumes V: ‹V = mk_vtab G Shn T sts gt redtab› and j: ‹j < length sts›
  shows ‹iget (v_fin V) j 0 = ntidx (vits G sts j) (start_prod G Shn, 1)›
  using j by (simp add: V mk_vtab_def Let_def)

lemma v_ind0_mk: ‹V = mk_vtab G Shn T sts gt redtab ⟹ v_ind0 V = istart_ind G›
  by (simp add: mk_vtab_def Let_def)

lemma v_av0_mk: ‹V = mk_vtab G Shn T sts gt redtab ⟹ v_av0 V = vinit_frame G Shn T sts›
  by (simp add: mk_vtab_def Let_def)

lemma vcomps_set:
  ‹(s, b, pr) ∈ set (vcomps G Shn its) ⟷
     (pr, length (snd pr)) ∈ set its ∧ s = ntidx its (pr, length (snd pr)) ∧ b = nnum G Shn (fst pr)›
  (is ‹?L ⟷ ?R›)
proof
  assume ?L
  then obtain x where x: ‹x < length its› and e: ‹(case its ! x of (pr', m) ⇒
      if m = length (snd pr') ∧ ntidx its (pr', m) = x then Some (x, nnum G Shn (fst pr'), pr')
      else None) = Some (s, b, pr)›
    unfolding vcomps_def in_map_filter by auto
  obtain pr' m where i: ‹its ! x = (pr', m)› by (cases ‹its ! x›)
  from e i have ‹pr' = pr› ‹m = length (snd pr)› ‹s = x› ‹b = nnum G Shn (fst pr)› ‹ntidx its (pr, m) = x›
    by (auto split: if_splits)
  with x i show ?R by (metis nth_mem)
next
  assume r: ?R
  then have ‹s < length its› ‹its ! s = (pr, length (snd pr))› by (simp_all add: ntidx_less ntidx_nth)
  with r show ?L unfolding vcomps_def in_map_filter by force
qed

lemma vcells_set:
  ‹(s', τ) ∈ set (vcells its j cells t) ⟷
     (∃pr. (j, (pr, length (snd pr)), t, τ) ∈ set cells ∧ s' = ntidx its (pr, length (snd pr)))›
  unfolding vcells_def in_map_filter
  apply (rule iffI)
   apply (erule bexE)
  subgoal for x by (cases x) (auto split: if_splits, blast)
  by (force split: if_splits)


subsection ‹A successor frame›

text ‹The anchors of a successor kernel depend on the anchor set crossed only
  through its elements, so the vector driver may cross a different
  representation of the same set.›

lemma aset_lgoto_cong:
  ‹irep_set RA' = irep_set RA ⟹ aset (lgoto CL X RA') it = aset (lgoto CL X RA) it›
  by (cases it) (simp add: aset_lgoto)

lemma vkrel_cong: ‹vkrel G its X kav ⟹ (⋀it. aset X' it = aset X it) ⟹ vkrel G its X' kav›
  by (simp add: vkrel_def)

lemma aset_lgoto_slot: ‹is_slot G it ⟹ aset (lgoto CL X RA) it = {}›
  by (cases it) (simp add: aset_lgoto is_slot_def)

lemma vgo_succ:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and V: ‹V = mk_vtab G Shn T sts gt redtab›
    and fr: ‹vfr CL (vits G sts j) av› and cov: ‹lcore CL ⊆ set (vits G sts j)›
    and RA: ‹irep_set RA' = irep_set RA›
    and j': ‹j' < length sts› and k': ‹lcore (lgoto CL Y RA) ⊆ set (sts ! j')›
    and w: ‹⋀p m R. (p, m, R) ∈ set (lgoto CL Y RA) ⟹ irep_nonempty R ⟹ p ∈ set (eprods G Shn)›
  obtains av' where
    ‹vgo V (j', vkmap (vits G sts j) Y (vits G sts j')) av RA' =
       (if live (lgoto CL Y RA) then Some (j', av') else None)›
    and ‹vfr (xclosure_auto G (lgoto CL Y RA)) (vits G sts j') av'›
proof -
  let ?its = ‹vits G sts j'› and ?X = ‹lgoto CL Y RA›
  let ?kav = ‹vkav (vkmap (vits G sts j) Y ?its) av RA'›
  let ?av = ‹vfill (map (vcontrib G Shn T ?its) ?its) ?kav›
  have k: ‹vkrel G ?its ?X ?kav›
    by (rule vkrel_cong[OF vkav_krel[OF fr cov]]) (rule aset_lgoto_cong[OF RA, symmetric])
  have its: ‹?its = creach G (sts ! j')› using j' by (simp add: vits_def)
  have cov': ‹it ∈ set ?its› if ‹aset ?X it ≠ {}› for it
    using that k' creach_superset[of ‹sts ! j'› G] its by (auto simp: aset_ne_lcore)
  have ns: ‹aset ?X it = {}› if ‹is_slot G it› for it using that by (rule aset_lgoto_slot)
  have kl: ‹length ?kav = length ?its› by simp
  have kn: ‹irep_set (?kav ! s) = (if is_slot G (?its ! s) then {} else aset ?X (?its ! s))›
    if ‹s < length ?its› for s
    using k that unfolding vkrel_def by blast
  have lx: ‹list_ex irep_nonempty ?kav ⟷ live ?X›
  proof
    assume ‹list_ex irep_nonempty ?kav›
    then obtain s where s: ‹s < length ?its› and ne: ‹irep_nonempty (?kav ! s)›
      using kl by (metis in_set_conv_nth list_ex_iff)
    with kn[OF s] have ‹aset ?X (?its ! s) ≠ {}› by (auto split: if_splits)
    then show ‹live ?X› using live_aset by blast
  next
    assume ‹live ?X›
    then obtain it where ne: ‹aset ?X it ≠ {}› by (auto simp: live_aset)
    then have m: ‹it ∈ set ?its› by (rule cov')
    let ?s = ‹ntidx ?its it›
    have s: ‹?s < length ?its› and si: ‹?its ! ?s = it› using m by (simp_all add: ntidx_less ntidx_nth)
    have ‹¬ is_slot G it› using ne ns by blast
    with kn[OF s] si ne have ‹irep_set (?kav ! ?s) ≠ {}› by simp
    with s kl show ‹list_ex irep_nonempty ?kav›
      by (metis nth_mem list_ex_iff irep_nonempty_correct)
  qed
  have ‹vfr (xclosure_auto G ?X) ?its ?av›
    unfolding vfr_def
  proof (intro conjI allI impI)
    show ‹length ?av = length ?its› by simp
    fix s assume s: ‹s < length ?its›
    show ‹irep_set (?av ! s) = aset (xclosure_auto G ?X) (?its ! s)›
      by (rule vfill_cl[OF T w k cov' ns]) (assumption | rule s)+
  qed
  moreover have ‹vgo V (j', vkmap (vits G sts j) Y ?its) av RA' =
      (if live ?X then Some (j', ?av) else None)›
    using lx by (simp add: vgo_def v_ct_mk[OF V j'])
  ultimately show ?thesis using that by blast
qed


subsection ‹Crossing a symbol›

lemma vits_cuniv:
  assumes tab: ‹tables_ok G Shn sts gt L› and j: ‹j < length sts›
  shows ‹set (vits G sts j) ⊆ cuniv G Shn›
proof -
  from tab j have ‹set (sts ! j) ⊆ cuniv G Shn› by (simp add: tables_ok_def)
  then show ?thesis using j by (simp add: vits_def creach_univ)
qed

lemma live_lgoto_gram_sym:
  assumes tab: ‹tables_ok G Shn sts gt L› and j: ‹j < length sts›
    and cov: ‹lcore CL ⊆ set (vits G sts j)› and lv: ‹live (lgoto CL Y RA)›
  shows ‹Y ∈ set (gram_syms G)›
proof -
  from lv obtain p m where ne: ‹aset (lgoto CL Y RA) (p, m) ≠ {}› by (auto simp: live_aset)
  then have m: ‹0 < m› ‹m ≤ length (snd p)› and Y: ‹fst (snd p ! (m - 1)) = Y›
    and ‹aset CL (p, m - 1) ≠ {}› by (auto simp: aset_lgoto split: if_splits)
  then have ‹(p, m - 1) ∈ cuniv G Shn›
    using cov vits_cuniv[OF tab j] by (auto simp: aset_ne_lcore)
  from cuniv_next_gram_syms[OF this] m Y show ?thesis by simp
qed

lemma tm_vtoks: ‹Tm a ∈ set (gram_syms G) ⟹ a ∈ set (vtoks G redtab)›
  by (force simp: vtoks_def)

text ‹The successor of frame ‹d› under ‹Y›: the vector driver finds an entry
  and a live kernel exactly when the dense successor is live, and then its
  frame holds the dense successor's closure.›

lemma vgo_ventry:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and V: ‹V = mk_vtab G Shn T sts gt redtab›
    and tab: ‹tables_ok G Shn sts gt L›
    and ok: ‹didx_ok G sts Xs istk› and d: ‹d < length Xs› and lvd: ‹live (Xs ! d)›
    and fr: ‹vfr (xclosure_auto G (Xs ! d)) (vits G sts (istk ! d)) av›
    and RA: ‹irep_set RA' = irep_set RA›
  obtains av' where
    ‹(case ventry G gt sts (istk ! d) Y of None ⇒ None | Some e ⇒ vgo V e av RA') =
       (if live (lgoto (xclosure_auto G (Xs ! d)) Y RA)
        then Some (dnext gt sts (istk ! d) Y, av') else None)›
    and ‹vfr (xclosure_auto G (lgoto (xclosure_auto G (Xs ! d)) Y RA))
           (vits G sts (dnext gt sts (istk ! d) Y)) av'›
proof -
  let ?j = ‹istk ! d› and ?CL = ‹xclosure_auto G (Xs ! d)›
  let ?X = ‹lgoto ?CL Y RA› and ?j' = ‹dnext gt sts (istk ! d) Y›
  have j: ‹?j < length sts› and cov: ‹lcore ?CL ⊆ set (vits G sts ?j)›
    by (rule frame_cov[OF ok d lvd])+
  have okp: ‹didx_ok G sts (?X # drop d Xs) (?j' # drop d istk)›
    by (rule didx_ok_push[OF tab ok d])
  have w: ‹p ∈ set (eprods G Shn)› if ‹(p, m, R) ∈ set ?X› and ‹irep_nonempty R› for p m R
    using frame_eprods[OF tab okp, of 0 p m R] that by simp
  show ?thesis
  proof (cases ‹live ?X›)
    case True
    then have ‹lcore ?X ≠ {}› by (simp add: live_lcore)
    with didx_okD[OF okp, of 0] have j': ‹?j' < length sts› and k': ‹lcore ?X ⊆ set (sts ! ?j')›
      by simp_all
    obtain av' where g: ‹vgo V (?j', vkmap (vits G sts ?j) Y (vits G sts ?j')) av RA' =
        (if live ?X then Some (?j', av') else None)›
      and f: ‹vfr (xclosure_auto G ?X) (vits G sts ?j') av'›
      by (rule vgo_succ[OF T V fr cov RA j' k']) (rule w, assumption+)
    show ?thesis by (rule that[of av']) (use g f j' in ‹simp_all add: ventry_def Let_def›)
  next
    case False
    show ?thesis
    proof (cases ‹?j' < length sts›)
      case j': True
      have k': ‹lcore ?X ⊆ set (sts ! ?j')› using False by (simp add: live_lcore)
      obtain av' where g: ‹vgo V (?j', vkmap (vits G sts ?j) Y (vits G sts ?j')) av RA' =
          (if live ?X then Some (?j', av') else None)›
        and f: ‹vfr (xclosure_auto G ?X) (vits G sts ?j') av'›
        by (rule vgo_succ[OF T V fr cov RA j' k']) (rule w, assumption+)
      show ?thesis by (rule that[of av']) (use g f False j' in ‹simp_all add: ventry_def Let_def›)
    next
      case j': False
      show ?thesis by (rule that[of ‹[]›]) (use False j' in ‹simp_all add: ventry_def Let_def vits_def vfr_def›)
    qed
  qed
qed


subsection ‹One action›

lemma vrel_head:
  assumes tab: ‹tables_ok G Shn sts gt L› and ir: ‹imreach G Shn gt sts ((Xs, w), istk)›
    and r: ‹vrel G sts Xs istk fs›
  obtains j av fs0 where ‹fs = (j, av) # fs0› and ‹hd istk = j› and ‹Xs ≠ []› and ‹live (hd Xs)›
    and ‹j < length sts› and ‹lcore (xclosure_auto G (hd Xs)) ⊆ set (vits G sts j)›
    and ‹vfr (xclosure_auto G (hd Xs)) (vits G sts j) av› and ‹didx_ok G sts Xs istk›
proof -
  have ok: ‹didx_ok G sts Xs istk› using imreach_didx_ok[OF tab ir] by simp
  have ne: ‹Xs ≠ []› and lv: ‹live (hd Xs)› using imreach_dlive[OF ir] by (simp_all add: dlive_def)
  have lf: ‹length fs = length Xs› and li: ‹length istk = length Xs›
    using r didx_ok_len[OF ok] by (simp_all add: vrel_def)
  obtain j av fs0 where fs: ‹fs = (j, av) # fs0› using ne lf by (cases fs) auto
  have ni: ‹istk ≠ []› using ne li by auto
  have hX: ‹hd Xs = Xs ! 0› and hi: ‹hd istk = istk ! 0› using ne ni by (simp_all add: hd_conv_nth)
  have j: ‹hd istk = j› using vrel_nth(1)[OF r, of 0] by (simp add: fs hi)
  have lv0: ‹live (Xs ! 0)› using lv hX by simp
  have d0: ‹0 < length Xs› using ne by simp
  show ?thesis
  proof (rule that[OF fs j ne lv])
    show ‹j < length sts› and ‹lcore (xclosure_auto G (hd Xs)) ⊆ set (vits G sts j)›
      using frame_cov[OF ok d0 lv0] hX hi j by simp_all
    show ‹vfr (xclosure_auto G (hd Xs)) (vits G sts j) av›
      using vrel_nth(2)[OF r, of 0] hX hi j by (simp add: fs)
  qed (rule ok)
qed

lemma vmstep_shift:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and V: ‹V = mk_vtab G Shn T sts gt redtab›
    and tab: ‹tables_ok G Shn sts gt L› and ir: ‹imreach G Shn gt sts ((Xs, w), istk)›
    and r: ‹vrel G sts Xs istk fs›
  shows ‹case vmstep V (fs, w) VShift of
      None ⇒ (∀ic'. imstep G gt sts ((Xs, w), istk) DShift = Some ic' ⟶ ¬ dlive (fst ic'))
    | Some (fs', w') ⇒ ∃Xs' istk'. imstep G gt sts ((Xs, w), istk) DShift = Some ((Xs', w'), istk') ∧
        dlive (Xs', w') ∧ vrel G sts Xs' istk' fs'›
proof -
  obtain j av fs0 where fs: ‹fs = (j, av) # fs0› and hj: ‹hd istk = j› and ne: ‹Xs ≠ []›
    and lv: ‹live (hd Xs)› and j: ‹j < length sts›
    and cov: ‹lcore (xclosure_auto G (hd Xs)) ⊆ set (vits G sts j)›
    and fr: ‹vfr (xclosure_auto G (hd Xs)) (vits G sts j) av› and ok: ‹didx_ok G sts Xs istk›
    by (rule vrel_head[OF tab ir r])
  show ?thesis
  proof (cases w)
    case Nil
    then show ?thesis by (simp add: fs vmstep_def imstep_def mstep_def mstep_cached_def)
  next
    case (Cons ac w')
    obtain a c where w: ‹w = (a, c) # w'› using Cons by (cases ac) auto
    let ?CL = ‹xclosure_auto G (hd Xs)›
    let ?X = ‹lgoto ?CL (Tm a) (FinRep [c])› and ?j' = ‹dnext gt sts j (Tm a)›
    have im: ‹imstep G gt sts ((Xs, w), istk) DShift = Some ((?X # Xs, w'), ?j' # istk)›
      using ne hj by (simp add: imstep_def mstep_def mstep_cached_def w hd_map)
    have li: ‹length istk = length Xs› by (rule didx_ok_len[OF ok])
    have ni: ‹istk ≠ []› using ne li by auto
    have hX: ‹Xs ! 0 = hd Xs› and hi: ‹istk ! 0 = hd istk› using ne ni by (simp_all add: hd_conv_nth)
    have d0: ‹0 < length Xs› and lv0: ‹live (Xs ! 0)› using ne lv hX by simp_all
    have fr0: ‹vfr (xclosure_auto G (Xs ! 0)) (vits G sts (istk ! 0)) av› using fr hX hi hj by simp
    obtain av' where g: ‹(case ventry G gt sts j (Tm a) of None ⇒ None
          | Some e ⇒ vgo V e av (FinRep [c])) = (if live ?X then Some (?j', av') else None)›
      and f: ‹vfr (xclosure_auto G ?X) (vits G sts ?j') av'›
      by (rule vgo_ventry[OF T V tab ok d0 lv0 fr0 refl, where Y = ‹Tm a›, unfolded hX hi hj])
    have a: ‹a ∈ set (vtoks G redtab)› if ‹live ?X›
      using live_lgoto_gram_sym[OF tab j cov that] by (rule tm_vtoks)
    have vm: ‹vmstep V (fs, w) VShift =
        map_option (λf. (f # fs, w')) (if live ?X then Some (?j', av') else None)›
    proof (cases ‹a ∈ set (vtoks G redtab)›)
      case True
      then show ?thesis using g
        by (cases ‹ventry G gt sts j (Tm a)›) (simp_all add: vmstep_def fs w v_sh_mk[OF V j])
    next
      case False
      then show ?thesis using a by (auto simp: vmstep_def fs w v_sh_mk[OF V j])
    qed
    show ?thesis
    proof (cases ‹live ?X›)
      case True
      have ‹vrel G sts (?X # Xs) (?j' # istk) ((?j', av') # fs)› by (rule vrel_push[OF r f])
      with True im show ?thesis by (simp add: vm dlive_def)
    next
      case False
      with im show ?thesis by (simp add: vm dlive_def)
    qed
  qed
qed

lemma vmstep_reduce:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and V: ‹V = mk_vtab G Shn T sts gt redtab›
    and tab: ‹tables_ok G Shn sts gt L› and ir: ‹imreach G Shn gt sts ((Xs, w), istk)›
    and r: ‹vrel G sts Xs istk fs›
    and c: ‹(s, b, pr) ∈ set (vcomps G Shn (vits G sts (hd istk)))›
    and ne: ‹irep_nonempty (getR (snd (hd fs)) s)›
  shows ‹case vmstep V (fs, w) (VReduce s b pr) of
      None ⇒ (∀ic'. imstep G gt sts ((Xs, w), istk) (DReduce pr) = Some ic' ⟶ ¬ dlive (fst ic'))
    | Some (fs', w') ⇒ ∃Xs' istk'. imstep G gt sts ((Xs, w), istk) (DReduce pr) = Some ((Xs', w'), istk') ∧
        dlive (Xs', w') ∧ vrel G sts Xs' istk' fs'›
proof -
  obtain j av fs0 where fs: ‹fs = (j, av) # fs0› and hj: ‹hd istk = j› and nX: ‹Xs ≠ []›
    and lv: ‹live (hd Xs)› and j: ‹j < length sts›
    and cov: ‹lcore (xclosure_auto G (hd Xs)) ⊆ set (vits G sts j)›
    and fr: ‹vfr (xclosure_auto G (hd Xs)) (vits G sts j) av› and ok: ‹didx_ok G sts Xs istk›
    by (rule vrel_head[OF tab ir r])
  let ?n = ‹length (snd pr)› and ?CL = ‹xclosure_auto G (hd Xs)›
  from c have m: ‹(pr, ?n) ∈ set (vits G sts j)› and s: ‹s = ntidx (vits G sts j) (pr, ?n)›
    and b: ‹b = nnum G Shn (fst pr)› by (simp_all add: vcomps_set hj)
  have RS: ‹irep_set (getR av s) = irep_set (red_set ?CL pr)›
    using vfr_getR[OF fr cov] by (simp add: s aset_red)
  have RSne: ‹irep_nonempty (red_set ?CL pr)› using ne RS by (simp add: fs)
  have fp: ‹fst pr ∈ set (map fst (eprods G Shn))› using closure_eprods[OF tab j m] by simp
  have bl: ‹b < length (eprods G Shn)› using fp ntidx_less[of ‹map fst (eprods G Shn)›]
    by (simp add: b nnum_def)
  have bf: ‹fst (eprods G Shn ! b) = fst pr›
    using ntidx_nth[OF fp] bl by (simp add: b nnum_def)
  have lf: ‹length fs = length Xs› using r by (simp add: vrel_def)
  show ?thesis
  proof (cases ‹?n < length Xs›)
    case False
    then show ?thesis using lf by (simp add: fs vmstep_def imstep_def mstep_def mstep_cached_def)
  next
    case n: True
    let ?j0 = ‹istk ! ?n› and ?CL0 = ‹xclosure_auto G (Xs ! ?n)›
    let ?X = ‹lgoto ?CL0 (Nt (fst pr)) (red_set ?CL pr)› and ?j' = ‹dnext gt sts ?j0 (Nt (fst pr))›
    have im: ‹imstep G gt sts ((Xs, w), istk) (DReduce pr) = Some ((?X # drop ?n Xs, w), ?j' # drop ?n istk)›
      using n nX RSne by (simp add: imstep_def mstep_def mstep_cached_def hd_map)
    have lv0: ‹live (Xs ! ?n)› using imreach_frames_live[OF ir] n by simp
    obtain av0 where fsn: ‹fs ! ?n = (?j0, av0)› and fr0: ‹vfr ?CL0 (vits G sts ?j0) av0›
      using vrel_nth[OF r] n lf by (metis prod.collapse)
    have j0: ‹?j0 < length sts› by (rule frame_cov(1)[OF ok n lv0])
    obtain av' where g: ‹(case ventry G gt sts ?j0 (Nt (fst pr)) of None ⇒ None
          | Some e ⇒ vgo V e av0 (getR av s)) = (if live ?X then Some (?j', av') else None)›
      and f: ‹vfr (xclosure_auto G ?X) (vits G sts ?j') av'›
      by (rule vgo_ventry[OF T V tab ok n lv0 fr0 RS])
    have vm: ‹vmstep V (fs, w) (VReduce s b pr) =
        map_option (λf. (f # drop ?n fs, w)) (if live ?X then Some (?j', av') else None)›
      using g n lf fsn fs
      by (cases ‹ventry G gt sts ?j0 (Nt (fst pr))›) (simp_all add: vmstep_def v_go_mk[OF V j0 bl] bf)
    show ?thesis
    proof (cases ‹live ?X›)
      case True
      have ‹vrel G sts (?X # drop ?n Xs) (?j' # drop ?n istk) ((?j', av') # drop ?n fs)›
        by (rule vrel_push[OF vrel_drop[OF r] f])
      with True im show ?thesis by (simp add: vm dlive_def)
    next
      case False
      with im show ?thesis by (simp add: vm dlive_def)
    qed
  qed
qed


subsection ‹The candidates›

lemma vlic_dlic:
  assumes V: ‹V = mk_vtab G Shn T sts gt redtab› and j: ‹j < length sts› and jr: ‹j < length redtab›
    and m: ‹(pr, length (snd pr)) ∈ set (vits G sts j)›
    and s: ‹s = ntidx (vits G sts j) (pr, length (snd pr))›
    and RS: ‹irep_set RS' = irep_set RS›
  shows ‹vlic V j w s RS' ⟷ dlic j (redtab ! j) w pr RS›
proof -
  let ?its = ‹vits G sts j› and ?n = ‹length (snd pr)› and ?cells = ‹redtab ! j›
  have nt: ‹s = ntidx ?its (pr', length (snd pr')) ⟷ pr' = pr› for pr'
    using ntidx_eq_iff[OF m, of ‹(pr', length (snd pr'))›] s by auto
  have vc: ‹(s, τ) ∈ set (vcells ?its j ?cells t) ⟷ (j, (pr, ?n), t, τ) ∈ set ?cells› for t τ
    unfolding vcells_set by (simp add: nt del: split_paired_Ex)
  show ?thesis
  proof (cases w)
    case Nil
    have ‹vlic V j w s RS' ⟷ (∃τ. (s, τ) ∈ set (vcells ?its j ?cells None))›
      by (force simp: vlic_def Nil v_ce_mk[OF V j])
    also have ‹… ⟷ dlic j ?cells w pr RS›
      by (auto simp: vc dlic_def Nil list_ex_iff)
    finally show ?thesis .
  next
    case (Cons ac w')
    obtain a c where w: ‹w = (a, c) # w'› using Cons by (cases ac) auto
    have tok: ‹a ∈ set (vtoks G redtab)› if ‹(j, (pr, ?n), Some a, τ) ∈ set ?cells› for τ
    proof -
      have ‹(j, (pr, ?n), Some a, τ) ∈ set (concat redtab)› using that jr by auto
      then show ?thesis by (force simp: vtoks_def in_map_filter)
    qed
    have ‹vlic V j w s RS' ⟷ (∃τ. (j, (pr, ?n), Some a, τ) ∈ set ?cells ∧ irep_ex_wsat τ c RS')›
      using tok by (auto simp: vlic_def w v_cl_mk[OF V j] list_ex_iff vc)
    also have ‹… ⟷ dlic j ?cells w pr RS›
      using RS by (auto simp: dlic_def w list_ex_iff)
    finally show ?thesis .
  qed
qed

lemma vcands_dcands:
  assumes V: ‹V = mk_vtab G Shn T sts gt redtab› and j: ‹j < length sts› and jr: ‹j < length redtab›
    and fr: ‹vfr CL (vits G sts j) av› and cov: ‹lcore CL ⊆ set (vits G sts j)› and ne: ‹Xs ≠ []›
  shows ‹vdec ` set (vcands V j av w) = set (dcands G j (redtab ! j) CL (Xs, w))›
proof (intro equalityI subsetI)
  fix a assume ‹a ∈ vdec ` set (vcands V j av w)›
  then obtain act where act: ‹act ∈ set (vcands V j av w)› and a: ‹a = vdec act› by blast
  show ‹a ∈ set (dcands G j (redtab ! j) CL (Xs, w))›
  proof (cases act)
    case VShift
    then have ‹w ≠ []› using act by (auto simp: vcands_def split: list.splits)
    with ne show ?thesis using dcands_shift[of ‹(Xs, w)›] by (simp add: a VShift)
  next
    case (VReduce s b pr)
    from act have c: ‹(s, b, pr) ∈ set (vcomps G Shn (vits G sts j))›
      and nz: ‹irep_nonempty (getR av s)› and lc: ‹vlic V j w s (getR av s)›
      by (auto simp: vcands_def VReduce v_cp_mk[OF V j] Let_def split: list.splits)
    from c have m: ‹(pr, length (snd pr)) ∈ set (vits G sts j)›
      and s: ‹s = ntidx (vits G sts j) (pr, length (snd pr))› by (simp_all add: vcomps_set)
    have RS: ‹irep_set (getR av s) = irep_set (red_set CL pr)›
      using vfr_getR[OF fr cov] by (simp add: s aset_red)
    have dl: ‹dlic j (redtab ! j) w pr (red_set CL pr)› using lc vlic_dlic[OF V j jr m s RS] by simp
    have rn: ‹irep_nonempty (red_set CL pr)› using nz RS by simp
    then obtain R where ‹(pr, length (snd pr), R) ∈ set CL› by (meson red_set_nonempty_iff)
    from dcands_reduceI[of ‹(Xs, w)›, OF _ this rn] ne dl show ?thesis by (simp add: a VReduce)
  qed
next
  fix a assume a: ‹a ∈ set (dcands G j (redtab ! j) CL (Xs, w))›
  show ‹a ∈ vdec ` set (vcands V j av w)›
  proof (cases a)
    case DShift
    then have ‹w ≠ []› using a ne by (cases w) (auto simp: dcands_def Let_def)
    then have ‹VShift ∈ set (vcands V j av w)› by (auto simp: vcands_def Let_def split: list.splits)
    then show ?thesis by (force simp: DShift)
  next
    case (DReduce pr)
    let ?n = ‹length (snd pr)›
    from dcands_reduceD[OF a[unfolded DReduce]] have rn: ‹irep_nonempty (red_set CL pr)›
      and dl: ‹dlic j (redtab ! j) w pr (red_set CL pr)› by simp_all
    have m: ‹(pr, ?n) ∈ set (vits G sts j)›
      using rn cov aset_red[of CL pr] by (auto simp: aset_ne_lcore)
    let ?s = ‹ntidx (vits G sts j) (pr, ?n)›
    have RS: ‹irep_set (getR av ?s) = irep_set (red_set CL pr)›
      using vfr_getR[OF fr cov] by (simp add: aset_red)
    have c: ‹(?s, nnum G Shn (fst pr), pr) ∈ set (vcomps G Shn (vits G sts j))›
      by (simp add: vcomps_set m)
    have lc: ‹vlic V j w ?s (getR av ?s)› using dl vlic_dlic[OF V j jr m refl RS] by simp
    have ‹VReduce ?s (nnum G Shn (fst pr)) pr ∈ set (vcands V j av w)›
      using c rn RS lc by (force simp: vcands_def v_cp_mk[OF V j] Let_def split: list.splits)
    then show ?thesis by (force simp: DReduce)
  qed
qed


subsection ‹One step›

text ‹A vector state stands for a reachable dense one with the same input,
  tree stack and frames.›

definition vst_rel :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒ (('n, 't) sym × nat) list list ⇒
    ('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) vst ⇒ bool› where
  ‹vst_rel G Shn sts gt st vs ⟷ (case st of ((Xs, w), cstk, istk, v, tstk) ⇒
     vs = (fst vs, w, v, tstk) ∧ vrel G sts Xs istk (fst vs) ∧
     imreach G Shn gt sts ((Xs, w), istk) ∧ dfollow_ok G sts st)›

subsection ‹Acceptance›

lemma vfinal_gfinal:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and V: ‹V = mk_vtab G Shn T sts gt redtab›
    and tab: ‹tables_ok G Shn sts gt L› and fn: ‹fresh_name G Shn›
    and ir: ‹imreach G Shn gt sts ((Xs, w), istk)› and r: ‹vrel G sts Xs istk fs›
  shows ‹vfinal V (fs, w, v, tstk) ⟷ gfinal G Shn (Xs, w)›
proof -
  obtain j av fs0 where fs: ‹fs = (j, av) # fs0› and ne: ‹Xs ≠ []› and j: ‹j < length sts›
    and cov: ‹lcore (xclosure_auto G (hd Xs)) ⊆ set (vits G sts j)›
    and fr: ‹vfr (xclosure_auto G (hd Xs)) (vits G sts j) av› and ok: ‹didx_ok G sts Xs istk›
    by (rule vrel_head[OF tab ir r])
  have w: ‹p ∈ set (eprods G Shn)› if ‹(p, m, R) ∈ set (hd Xs)› ‹irep_nonempty R› for p m R
    using frame_eprods[OF tab ok, of 0] that ne by (simp add: hd_conv_nth)
  have ns: ‹¬ is_slot G (start_prod G Shn, Suc 0)› by (simp add: is_slot_def)
  have A: ‹irep_set (getR av (iget (v_fin V) j 0)) = aset (hd Xs) (start_prod G Shn, Suc 0)›
    using vfr_getR[OF fr cov, of ‹(start_prod G Shn, Suc 0)›] cl_aset[OF T w, where it = ‹(start_prod G Shn, Suc 0)›] ns
    by (simp add: v_fin_mk[OF V j])
  have E: ‹list_ex (λ(pr, m, R). fst pr = Shn ∧ m = Suc 0 ∧ irep_mem (istart_ind G) R) (hd Xs) ⟷
      istart_ind G ∈ aset (hd Xs) (start_prod G Shn, Suc 0)›
  proof
    assume ‹list_ex (λ(pr, m, R). fst pr = Shn ∧ m = Suc 0 ∧ irep_mem (istart_ind G) R) (hd Xs)›
    then obtain pr R where m: ‹(pr, Suc 0, R) ∈ set (hd Xs)› and l: ‹fst pr = Shn›
      and i: ‹istart_ind G ∈ irep_set R›
      unfolding list_ex_iff by force
    have ‹pr ∈ set (eprods G Shn)› using w[OF m] i by auto
    then have ‹pr = start_prod G Shn› using l fn
      by (force simp: eprods_def start_prod_def fresh_name_def)
    then show ‹istart_ind G ∈ aset (hd Xs) (start_prod G Shn, Suc 0)› using m i by (auto simp: aset_def)
  next
    assume ‹istart_ind G ∈ aset (hd Xs) (start_prod G Shn, Suc 0)›
    then obtain R where ‹(start_prod G Shn, Suc 0, R) ∈ set (hd Xs)› and ‹istart_ind G ∈ irep_set R›
      by (auto simp: aset_def)
    then show ‹list_ex (λ(pr, m, R). fst pr = Shn ∧ m = Suc 0 ∧ irep_mem (istart_ind G) R) (hd Xs)›
      unfolding list_ex_iff by (force simp: start_prod_def)
  qed
  show ?thesis using A E ne by (simp add: vfinal_def gfinal_def fs v_ind0_mk[OF V])
qed

subsection ‹The initial frame›

lemma vinit_vrel:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and tab: ‹tables_ok G Shn sts gt L›
    and fn: ‹fresh_name G Shn›
  shows ‹vrel G sts [xinit G Shn] [st_find sts (lr0_start G Shn)] [vinit_frame G Shn T sts]›
proof -
  let ?i = ‹st_find sts (lr0_start G Shn)› and ?X = ‹xinit G Shn›
  let ?its = ‹vits G sts ?i›
  let ?kav = ‹map (λit. if it = (start_prod G Shn, 0) then FinRep [istart_ind G] else FinRep []) ?its›
  obtain t where t: ‹t ∈ set sts› ‹set t = set (lr0_start G Shn)›
    using tab unfolding tables_ok_def by blast
  from st_find_found[OF t] have i: ‹?i < length sts› and si: ‹set (sts ! ?i) = {(start_prod G Shn, 0)}›
    by (simp_all add: lr0_start_def)
  have its: ‹(start_prod G Shn, 0) ∈ set ?its›
    using i si creach_superset[of ‹sts ! ?i› G] by (auto simp: vits_def)
  have ‹start_prod G Shn ∉ set (iprods G)› using fn by (force simp: fresh_name_def start_prod_def)
  then have nsl: ‹¬ is_slot G (start_prod G Shn, 0)› by (simp add: is_slot_def)
  have ax: ‹aset ?X it = (if it = (start_prod G Shn, 0) then {istart_ind G} else {})› for it
    by (cases it) (auto simp: xinit_def start_prod_def)
  have k: ‹vkrel G ?its ?X ?kav› using nsl by (auto simp: vkrel_def ax)
  have w: ‹p ∈ set (eprods G Shn)› if ‹(p, m, R) ∈ set ?X› ‹irep_nonempty R› for p m R
    using that by (simp add: xinit_def eprods_def)
  have cov: ‹it ∈ set ?its› if ‹aset ?X it ≠ {}› for it using that its by (simp add: ax split: if_splits)
  have ns: ‹aset ?X it = {}› if ‹is_slot G it› for it using that nsl by (auto simp: ax)
  have ‹irep_set (vfill (map (vcontrib G Shn T ?its) ?its) ?kav ! s) = aset (xclosure_auto G ?X) (?its ! s)›
    if ‹s < length ?its› for s
    using T w k cov ns that by (rule vfill_cl)
  then have ‹vfr (xclosure_auto G ?X) ?its (vfill (map (vcontrib G Shn T ?its) ?its) ?kav)›
    by (simp add: vfr_def)
  then show ?thesis by (simp add: vrel_def vinit_frame_def Let_def)
qed

section ‹Runtime determinism›

text ‹The vector driver orders its reductions by table position, the dense one by
  closure order.  Without const‹mdet› the two agree on a step when a shift is
  live (both try it first) or when exactly one action is live; the vector driver
  checks this at run time and reports a conflict otherwise.›

subsection ‹The checked driver›

text ‹The first live action, provided it is a shift or no later action is live;
  ‹None› on a conflict between live reductions, ‹Some None› when nothing is live.›

fun vchoose :: ‹('n, 't) vtab ⇒ vframes × ('t × nat) list ⇒ ('n, 't) vact list ⇒
    (('n, 't) vact × vframes × ('t × nat) list) option option› where
  ‹vchoose V fw [] = Some None›
| ‹vchoose V fw (a # acts) = (case vmstep V fw a of
     None ⇒ vchoose V fw acts
   | Some r ⇒ if a = VShift ∨ ¬ list_ex (λb. vmstep V fw b ≠ None) acts then Some (Some (a, r))
              else None)›

definition vstep_u :: ‹('n, 't) vtab ⇒ ('m, 'ch, 'n, 't) vst ⇒ ('m, 'ch, 'n, 't) vst option option› where
  ‹vstep_u V st = (case st of (fs, w, v, tstk) ⇒ (case fs of [] ⇒ Some None | (j, av) # _ ⇒
     (case vchoose V (fs, w) (vcands V j av w) of None ⇒ None | Some None ⇒ Some None
      | Some (Some (act, fs', w')) ⇒
          (case tstep (vdec act) (v, tstk) of (v', tstk') ⇒ Some (Some (fs', w', v', tstk'))))))›

text ‹‹None›: a conflict was met (or the run diverges); ‹Some r›: the dense result.›

partial_function (option) vrun_u ::
  ‹('n, 't) vtab ⇒ ('m, 'ch, 'n, 't) vst ⇒ ('m, 'ch, 'n, 't) ast option option›
  where
  ‹vrun_u V st = (case st of (fs, w, v, tstk) ⇒
     if vfinal V st then Some (case tstk of t # _ ⇒ Some t | [] ⇒ None)
     else (case vstep_u V st of None ⇒ None | Some None ⇒ Some None
       | Some (Some st') ⇒ vrun_u V st'))›

lemmas vrun_u_simps [code] = vrun_u.simps

lemma vchoose_SomeD:
  ‹vchoose V fw acts = Some (Some (a, r)) ⟹ a ∈ set acts ∧ vmstep V fw a = Some r ∧
     (a = VShift ∨ (∀b ∈ set acts. b ≠ a ⟶ vmstep V fw b = None))›
  by (induction V fw acts rule: vchoose.induct)
     (auto split: option.splits if_splits simp: list_ex_iff
       simp del: split_paired_All split_paired_Ex)

lemma vchoose_NoneD: ‹vchoose V fw acts = Some None ⟹ b ∈ set acts ⟹ vmstep V fw b = None›
  by (induction V fw acts rule: vchoose.induct) (auto split: option.splits if_splits)

lemma dpick_unique:
  assumes ‹a ∈ set D› and ‹mstep_cached G cstk gc a = Some g› and ‹dlive g›
    and ‹⋀d g'. d ∈ set D ⟹ d ≠ a ⟹ mstep_cached G cstk gc d = Some g' ⟹ ¬ dlive g'›
  shows ‹dpick G cstk gc D = Some (a, g)›
  using assms
proof (induction D)
  case (Cons d D)
  then show ?case by (cases ‹d = a›) (auto split: option.splits simp del: split_paired_All)
qed simp

lemma dpick_none:
  assumes ‹⋀d g'. d ∈ set D ⟹ mstep_cached G cstk gc d = Some g' ⟹ ¬ dlive g'›
  shows ‹dpick G cstk gc D = None›
  using assms by (induction D) (auto split: option.splits)

lemma vstep_u_dstep:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and V: ‹V = mk_vtab G Shn T sts gt redtab›
    and stc: ‹sts = pr0_states G Shn› and gtc: ‹gt = pgtab G sts›
    and rt: ‹redtab = red_buckets G Shn (length sts)›
    and rel: ‹vst_rel G Shn sts gt st vs›
  shows ‹vstep_u V vs = Some None ⟹ dstep G gt sts redtab st = None›
    and ‹vstep_u V vs = Some (Some vs') ⟹
      ∃st'. dstep G gt sts redtab st = Some st' ∧ vst_rel G Shn sts gt st' vs'›
proof -
  let ?L = ‹la_fix G Shn›
  have tab: ‹tables_ok G Shn sts gt ?L› using tables_ok_concrete[of G Shn] stc gtc by simp
  obtain Xs w cstk istk v tstk where st: ‹st = ((Xs, w), cstk, istk, v, tstk)›
    by (metis prod.exhaust)
  obtain fs where vs: ‹vs = (fs, w, v, tstk)› and r: ‹vrel G sts Xs istk fs›
    and ir: ‹imreach G Shn gt sts ((Xs, w), istk)› and inv: ‹dfollow_ok G sts st›
    using rel by (cases vs) (auto simp: vst_rel_def st)
  obtain j av fs0 where fs: ‹fs = (j, av) # fs0› and hj: ‹hd istk = j› and ne: ‹Xs ≠ []›
    and j: ‹j < length sts›
    and cov: ‹lcore (xclosure_auto G (hd Xs)) ⊆ set (vits G sts j)›
    and fr: ‹vfr (xclosure_auto G (hd Xs)) (vits G sts j) av› and ok: ‹didx_ok G sts Xs istk›
    by (rule vrel_head[OF tab ir r])
  have cs: ‹cstk = map (xclosure_auto G) Xs› using inv by (simp add: st dfollow_ok_def)
  have jr: ‹j < length redtab› using j by (simp add: rt)
  obtain istk0 where ist: ‹istk = j # istk0›
    using hj ok ne by (cases istk) (auto simp: didx_ok_def)
  obtain X0 Xs0 where Xs: ‹Xs = X0 # Xs0› using ne by (cases Xs) auto
  let ?CL = ‹xclosure_auto G (hd Xs)›
  let ?A = ‹vcands V j av w› and ?D = ‹dcands G j (redtab ! j) ?CL (Xs, w)›
  have AD: ‹vdec ` set ?A = set ?D› by (rule vcands_dcands[OF V j jr fr cov ne])
  have dsE: ‹dstep G gt sts redtab st = None ⟷ dpick G cstk (Xs, w) ?D = None›
    by (simp add: dstep_def st ist cs Xs jr split: option.splits dact.splits)
  have mc: ‹mstep_cached G cstk (Xs, w) a = mstep G (Xs, w) a› for a by (simp add: mstep_def cs)
  have vm: ‹case vmstep V (fs, w) act of
      None ⇒ (∀ic'. imstep G gt sts ((Xs, w), istk) (vdec act) = Some ic' ⟶ ¬ dlive (fst ic'))
    | Some (fs', w') ⇒ ∃Xs' istk'. imstep G gt sts ((Xs, w), istk) (vdec act) = Some ((Xs', w'), istk') ∧
        dlive (Xs', w') ∧ vrel G sts Xs' istk' fs'› if act: ‹act ∈ set ?A› for act
  proof (cases act)
    case VShift
    show ?thesis using vmstep_shift[OF T V tab ir r] unfolding VShift vdec.simps .
  next
    case (VReduce s b pr)
    from act have c: ‹(s, b, pr) ∈ set (vcomps G Shn (vits G sts (hd istk)))›
      and nz: ‹irep_nonempty (getR (snd (hd fs)) s)›
      by (auto simp: vcands_def VReduce v_cp_mk[OF V j] Let_def hj fs split: list.splits)
    show ?thesis using vmstep_reduce[OF T V tab ir r c nz] unfolding VReduce vdec.simps .
  qed
  text ‹A vector action without a step: its dense counterpart has no live step.›
  have dead: ‹¬ dlive g'› if ‹act ∈ set ?A› ‹vmstep V (fs, w) act = None›
    ‹mstep_cached G cstk (Xs, w) (vdec act) = Some g'› for act g'
  proof -
    from vm[OF that(1)] that(2)
    have ‹∀ic'. imstep G gt sts ((Xs, w), istk) (vdec act) = Some ic' ⟶ ¬ dlive (fst ic')› by simp
    with that(3) show ?thesis by (simp add: imstep_def mc)
  qed
  show ‹dstep G gt sts redtab st = None› if vn: ‹vstep_u V vs = Some None›
  proof -
    have ch: ‹vchoose V (fs, w) ?A = Some None›
      using vn by (simp add: vstep_u_def vs fs split: option.splits prod.splits)
    have ‹dpick G cstk (Xs, w) ?D = None›
    proof (rule dpick_none)
      fix d g' assume d: ‹d ∈ set ?D› and m: ‹mstep_cached G cstk (Xs, w) d = Some g'›
      from d AD obtain b where b: ‹b ∈ set ?A› and db: ‹d = vdec b› by blast
      show ‹¬ dlive g'› using dead[OF b vchoose_NoneD[OF ch b]] m db by simp
    qed
    with dsE show ?thesis by simp
  qed
  show ‹∃st'. dstep G gt sts redtab st = Some st' ∧ vst_rel G Shn sts gt st' vs'›
    if vy: ‹vstep_u V vs = Some (Some vs')›
  proof -
    obtain act fs' w' where ch: ‹vchoose V (fs, w) ?A = Some (Some (act, fs', w'))›
      and vs': ‹vs' = (case tstep (vdec act) (v, tstk) of (v', tstk') ⇒ (fs', w', v', tstk'))›
      using vy by (auto simp: vstep_u_def vs fs split: option.splits prod.splits)
    from vchoose_SomeD[OF ch] have act: ‹act ∈ set ?A› and vms: ‹vmstep V (fs, w) act = Some (fs', w')›
      and alt: ‹act = VShift ∨ (∀b ∈ set ?A. b ≠ act ⟶ vmstep V (fs, w) b = None)› by simp_all
    from vm[OF act] vms obtain Xs' istk' where
      im: ‹imstep G gt sts ((Xs, w), istk) (vdec act) = Some ((Xs', w'), istk')›
      and lv: ‹dlive (Xs', w')› and r': ‹vrel G sts Xs' istk' fs'› by auto
    have ms: ‹mstep_cached G cstk (Xs, w) (vdec act) = Some (Xs', w')›
      using im by (simp add: imstep_def mc split: option.splits)
    have pick: ‹dpick G cstk (Xs, w) ?D = Some (vdec act, (Xs', w'))›
      using alt
    proof
      assume sh: ‹act = VShift›
      with act have ‹w ≠ []› by (auto simp: vcands_def Let_def split: list.splits)
      then obtain rest where ‹?D = DShift # rest› using ne by (cases w) (auto simp: dcands_def Let_def)
      with ms lv sh show ?thesis by simp
    next
      assume un: ‹∀b ∈ set ?A. b ≠ act ⟶ vmstep V (fs, w) b = None›
      show ?thesis
      proof (rule dpick_unique[OF _ ms lv])
        show ‹vdec act ∈ set ?D› using act AD by blast
        fix d g' assume d: ‹d ∈ set ?D› ‹d ≠ vdec act› and m: ‹mstep_cached G cstk (Xs, w) d = Some g'›
        from d(1) AD obtain b where b: ‹b ∈ set ?A› and db: ‹d = vdec b› by blast
        with d(2) have ‹b ≠ act› by blast
        with un b have ‹vmstep V (fs, w) b = None› by blast
        from dead[OF b this] m db show ‹¬ dlive g'› by simp
      qed
    qed
    have lic: ‹∀pr. vdec act = DReduce pr ⟶ lic_at G ?L sts ((Xs, w), istk) pr›
    proof (intro allI impI)
      fix pr assume ‹vdec act = DReduce pr›
      with act AD have ‹DReduce pr ∈ set ?D› by force
      from dcands_reduceD[OF this] have ‹dlic j (redtab ! j) w pr (red_set ?CL pr)› by simp
      then have ‹dlic_L j ?L w pr (red_set ?CL pr)›
        using dlic_buckets[of j ‹length sts› ?L] j by (simp add: rt red_buckets_def)
      then show ‹lic_at G ?L sts ((Xs, w), istk) pr› using j by (simp add: lic_at_def hj)
    qed
    from dstep_of_dpick[OF tab stc gtc refl rt ir inv[unfolded st] im lv lic, unfolded fst_conv]
      pick hj
    obtain v' tstk' where tp: ‹(v', tstk') = tstep (vdec act) (v, tstk)›
      and ds: ‹dstep G gt sts redtab ((Xs, w), cstk, istk, v, tstk)
          = Some ((Xs', w'), map (xclosure_auto G) Xs', istk', v', tstk')›
      and inv': ‹dfollow_ok G sts ((Xs', w'), map (xclosure_auto G) Xs', istk', v', tstk')›
      by blast
    have ir': ‹imreach G Shn gt sts ((Xs', w'), istk')› using imreach_step[OF ir im] lv by simp
    have ‹vs' = (fs', w', v', tstk')› using vs' tp[symmetric] by simp
    moreover have ‹vst_rel G Shn sts gt ((Xs', w'), map (xclosure_auto G) Xs', istk', v', tstk')
        (fs', w', v', tstk')› using r' ir' inv' by (simp add: vst_rel_def)
    ultimately show ?thesis using ds by (simp add: st)
  qed
qed


subsection ‹The checked run›

definition vctx_u :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list list ⇒ ('n, 't) vtab ⇒ bool› where
  ‹vctx_u G Shn gt sts redtab V ⟷ V = mk_vtab G Shn (mk_stab G Shn gt sts redtab) sts gt redtab ∧
     sts = pr0_states G Shn ∧ gt = pgtab G sts ∧ redtab = red_buckets G Shn (length sts) ∧
     fresh_name G Shn›

lemma vctx_u_final:
  assumes c: ‹vctx_u G Shn gt sts redtab V› and r: ‹vst_rel G Shn sts gt st vs›
  obtains gc cstk istk v tstk fs where ‹st = (gc, cstk, istk, v, tstk)› ‹vs = (fs, snd gc, v, tstk)›
    ‹vfinal V vs ⟷ gfinal G Shn gc›
proof -
  obtain Xs w cstk istk v tstk where st: ‹st = ((Xs, w), cstk, istk, v, tstk)›
    by (metis prod.exhaust)
  obtain fs where vs: ‹vs = (fs, w, v, tstk)› and rr: ‹vrel G sts Xs istk fs›
    and ir: ‹imreach G Shn gt sts ((Xs, w), istk)›
    using r by (cases vs) (auto simp: vst_rel_def st)
  have tab: ‹tables_ok G Shn sts gt (la_fix G Shn)›
    using c tables_ok_concrete[of G Shn] by (simp add: vctx_u_def)
  have V: ‹V = mk_vtab G Shn (mk_stab G Shn gt sts redtab) sts gt redtab›
    and fn: ‹fresh_name G Shn› using c by (simp_all add: vctx_u_def)
  have ‹vfinal V vs ⟷ gfinal G Shn (Xs, w)›
    unfolding vs by (rule vfinal_gfinal[OF refl V tab fn ir rr])
  then show thesis using that[of ‹(Xs, w)› cstk istk v tstk fs] st vs by simp
qed

lemma vrun_u_sound:
  assumes run: ‹vrun_u V vs = Some r›
  shows ‹∀G Shn gt sts redtab st. vctx_u G Shn gt sts redtab V ⟶ vst_rel G Shn sts gt st vs ⟶
    drun_nh G Shn gt sts redtab st = r›
proof (rule vrun_u.raw_induct[OF _ run], goal_cases)
  case (1 f V vs r)
  show ?case
  proof (intro impI allI)
    fix G Shn gt sts redtab st
    assume c: ‹vctx_u G Shn gt sts redtab V› and rl: ‹vst_rel G Shn sts gt st vs›
    obtain gc cstk istk v tstk fs where st: ‹st = (gc, cstk, istk, v, tstk)›
      and vs: ‹vs = (fs, snd gc, v, tstk)› and gf: ‹vfinal V vs ⟷ gfinal G Shn gc›
      by (rule vctx_u_final[OF c rl])
    have V: ‹V = mk_vtab G Shn (mk_stab G Shn gt sts redtab) sts gt redtab›
      and stc: ‹sts = pr0_states G Shn› and gtc: ‹gt = pgtab G sts›
      and rt: ‹redtab = red_buckets G Shn (length sts)› using c by (simp_all add: vctx_u_def)
    note su = vstep_u_dstep[OF refl V stc gtc rt rl]
    show ‹drun_nh G Shn gt sts redtab st = r›
    proof (cases ‹vfinal V vs›)
      case True
      with "1"(2) gf show ?thesis unfolding st vs by (subst drun_nh.simps) simp
    next
      case False
      show ?thesis
      proof (cases ‹vstep_u V vs›)
        case None
        with False "1"(2) show ?thesis unfolding vs by (simp add: vs[symmetric])
      next
        case (Some x)
        show ?thesis
        proof (cases x)
          case None
          with Some False "1"(2) have r: ‹r = None› unfolding vs by (simp add: vs[symmetric])
          from su(1) Some None have ‹dstep G gt sts redtab st = None› by simp
          with False gf r show ?thesis unfolding st by (subst drun_nh.simps) simp
        next
          case (Some vs1)
          with ‹vstep_u V vs = Some x› False "1"(2) have rec: ‹f V vs1 = Some r›
            unfolding vs by (simp add: vs[symmetric])
          from su(2) ‹vstep_u V vs = Some x› Some obtain st1 where
            sp: ‹dstep G gt sts redtab st = Some st1› and r1: ‹vst_rel G Shn sts gt st1 vs1›
            by blast
          from "1"(1)[OF rec] c r1 have ‹drun_nh G Shn gt sts redtab st1 = r› by blast
          with False gf sp show ?thesis unfolding st by (subst drun_nh.simps) simp
        qed
      qed
    qed
  qed
qed

theorem vrun_u_dparse:
  assumes fn: ‹fresh_name G Shn›
    and sts: ‹sts = pr0_states G Shn› and gt: ‹gt = pgtab G sts›
    and rt: ‹redtab = red_buckets G Shn (length sts)›
    and V: ‹V = mk_vtab G Shn (mk_stab G Shn gt sts redtab) sts gt redtab›
    and run: ‹vrun_u V ([v_av0 V], tcols w, w, []) = Some r›
  shows ‹dparse G Shn w = r›
proof -
  have c: ‹vctx_u G Shn gt sts redtab V› using assms by (simp add: vctx_u_def)
  have tab: ‹tables_ok G Shn sts gt (la_fix G Shn)› using tables_ok_concrete[of G Shn] sts gt by simp
  have ‹vst_rel G Shn sts gt (dinit G Shn sts w) ([v_av0 V], tcols w, w, [])›
    using vinit_vrel[OF refl tab fn] imreach_init[of G Shn gt sts ‹tcols w›]
      dfollow_ok_dinit[of G Shn w]
    by (simp add: vst_rel_def dinit_def v_av0_mk[OF V] sts)
  with vrun_u_sound[OF run] c have ‹drun_nh G Shn gt sts redtab (dinit G Shn sts w) = r› by blast
  moreover have ‹dparse G Shn w = drun_nh G Shn gt sts redtab (dinit G Shn sts w)›
    using dparse_via_tables_nh[OF sts[symmetric] gt[symmetric] rt[symmetric] refl refl refl]
    by (simp add: dinit_def)
  ultimately show ?thesis by simp
qed

text ‹The parser for the code generator: the checked vector run, and the sparse
  driver should it meet a conflict.›

lemma dparse_via_tables_vu:
  assumes st: ‹pr0_states G Shn = sts›
    and gt: ‹pgtab G sts = gtab›
    and rt: ‹red_buckets G Shn (length sts) = redtab›
    and i0: ‹st_find sts (lr0_start G Shn) = i0›
    and fr: ‹fresh_name G Shn›
    and tb: ‹mk_stab G Shn gtab sts redtab = stb›
    and vt: ‹mk_vtab G Shn stb sts gtab redtab = vtb›
    and ki: ‹sinit stb = kin›
    and kc: ‹sclosure stb kin = kcl›
  shows ‹dparse G Shn w = (case vrun_u vtb ([v_av0 vtb], tcols w, w, []) of
      Some r ⇒ r | None ⇒ sdrun stb (([kin], tcols w), [kcl], [i0], w, []))›
proof (cases ‹vrun_u vtb ([v_av0 vtb], tcols w, w, [])›)
  case None
  then show ?thesis using dparse_via_tables_s[OF st gt rt i0 fr tb ki kc] by simp
next
  case (Some r)
  have ‹dparse G Shn w = r›
    by (rule vrun_u_dparse[OF fr st[symmetric] gt[symmetric] rt[symmetric] _ Some])
       (simp add: tb vt)
  with Some show ?thesis by simp
qed

section ‹Faster code›

text ‹Code equations, and a copy of the checked driver, that the generated parser
  runs instead of the definitions above.  Each is proved equal to what it replaces
  (the copy: sound for it), so the simulation argument is untouched.›

subsection ‹Anchor-set operations›

text ‹The generated code rebuilds a list that an equation matches as ‹x # xs› and
  passes on whole; the equations here pass the list itself instead.›

text ‹A frame read by one walk down the list, without its length.›

lemma getR_code [code]:
  ‹getR [] k = FinRep []›
  ‹getR (R # av) k = (if k = 0 then R else getR av (k - 1))›
  by (simp add: getR_def) (cases k, simp_all add: getR_def)

lemma merge_code [code]:
  ‹merge xs ys = (case xs of [] ⇒ ys | x # xs' ⇒ (case ys of [] ⇒ xs | y # ys' ⇒
     if x < y then x # merge xs' ys else if y < x then y # merge xs ys' else x # merge xs' ys'))›
  by (cases xs; cases ys) simp_all

text ‹Two sorted finite sets intersected by a merge.  The operations keep their
  sets sorted, but no lemma says so: the check at runtime keeps the equation
  unconditional.›

fun slt :: ‹nat list ⇒ bool› where
  ‹slt (x # y # ys) ⟷ x < y ∧ slt (y # ys)›
| ‹slt _ ⟷ True›

lemma slt_sorted: ‹slt xs ⟷ sorted_wrt (<) xs›
  by (induction xs rule: slt.induct) (auto intro: less_trans)

fun inter_s :: ‹nat list ⇒ nat list ⇒ nat list› where
  ‹inter_s [] ys = []›
| ‹inter_s xs [] = []›
| ‹inter_s (x # xs) (y # ys) =
    (if x < y then inter_s xs (y # ys) else if y < x then inter_s (x # xs) ys
     else x # inter_s xs ys)›

lemma slt_code [code]:
  ‹slt xs = (case xs of [] ⇒ True | x # xs' ⇒ (case xs' of [] ⇒ True | y # _ ⇒ x < y ∧ slt xs'))›
  by (cases xs rule: slt.cases) simp_all

lemma inter_s_code [code]:
  ‹inter_s xs ys = (case xs of [] ⇒ [] | x # xs' ⇒ (case ys of [] ⇒ [] | y # ys' ⇒
     if x < y then inter_s xs' ys else if y < x then inter_s xs ys' else x # inter_s xs' ys'))›
  by (cases xs; cases ys) simp_all

lemma inter_s_filter:
  ‹sorted_wrt (<) xs ⟹ sorted_wrt (<) ys ⟹ inter_s xs ys = filter (λi. i ∈ set ys) xs›
proof (induction xs ys rule: inter_s.induct)
  case (3 x xs y ys)
  then show ?case
    by (auto intro!: filter_cong)
qed simp_all

text ‹A union with an empty finite set, and an intersection with a singleton, give
  back an argument: no list is built.  The general cases are the equations above,
  under another name.›

definition cunion_m :: ‹indrep ⇒ indrep ⇒ indrep› where
  ‹cunion_m = cunion›

lemma cunion_m_code [code]:
  ‹cunion_m (FinRep xs) (FinRep ys) = FinRep (merge xs ys)›
  ‹cunion_m (FinRep xs) (UpRep ys n) = UpRep (filter (λi. i < n) (merge xs ys)) n›
  ‹cunion_m (UpRep xs n) (FinRep ys) = UpRep (filter (λi. i < n) (merge xs ys)) n›
  ‹cunion_m (UpRep xs n) (UpRep ys m) = UpRep (filter (λi. i < min n m) (merge xs ys)) (min n m)›
  by (simp_all add: cunion_m_def)

lemma cunion_code [code]:
  ‹cunion R S = (case R of
     FinRep xs ⇒ (case xs of [] ⇒ (case S of FinRep _ ⇒ S | UpRep _ _ ⇒ cunion_m R S)
       | _ # _ ⇒ (case S of FinRep ys ⇒ (case ys of [] ⇒ R | _ # _ ⇒ cunion_m R S)
                  | UpRep _ _ ⇒ cunion_m R S))
   | UpRep _ _ ⇒ cunion_m R S)›
  by (auto simp: cunion_m_def split: indrep.split list.split)

definition cinter_m :: ‹indrep ⇒ indrep ⇒ indrep› where
  ‹cinter_m = cinter›

lemma cinter_m_code [code]:
  ‹cinter_m (FinRep xs) (FinRep ys) =
     FinRep (if slt xs ∧ slt ys then inter_s xs ys else filter (λi. irep_mem i (FinRep ys)) xs)›
  ‹cinter_m (FinRep xs) (UpRep ys m) = FinRep (filter (λi. irep_mem i (UpRep ys m)) xs)›
  ‹cinter_m (UpRep xs n) (FinRep ys) = FinRep (filter (λi. irep_mem i (UpRep xs n)) ys)›
  ‹cinter_m (UpRep xs n) (UpRep ys m) =
     UpRep (filter (λi. i < max n m)
       (merge (filter (λi. irep_mem i (UpRep ys m)) xs) (filter (λi. irep_mem i (UpRep xs n)) ys)))
       (max n m)›
  by (simp_all add: cinter_m_def slt_sorted inter_s_filter del: irep_mem_correct)

lemma filter_eq_replicate: ‹filter (λi. i = y) xs = replicate (count_list xs y) y›
  by (induction xs) auto

text ‹A finite set may repeat an element, so the singleton on the right comes back
  only when it occurs once.›

lemma cinter_code [code]:
  ‹cinter R S = (case R of
     FinRep xs ⇒ (case xs of
         [] ⇒ FinRep []
       | x # xs' ⇒ (case xs' of
           [] ⇒ (if irep_mem x S then R else FinRep [])
         | _ # _ ⇒ (case S of
             FinRep ys ⇒ (case ys of
                 [] ⇒ cinter_m R S
               | y # ys' ⇒ (case ys' of
                   [] ⇒ (let k = count_list xs y in if k = 1 then S else FinRep (replicate k y))
                 | _ # _ ⇒ cinter_m R S))
           | UpRep _ _ ⇒ cinter_m R S)))
   | UpRep _ _ ⇒ (case S of
       FinRep ys ⇒ (case ys of
           [] ⇒ cinter_m R S
         | y # ys' ⇒ (case ys' of [] ⇒ (if irep_mem y R then S else FinRep []) | _ # _ ⇒ cinter_m R S))
     | UpRep _ _ ⇒ cinter_m R S))›
  by (auto simp: cinter_m_def filter_eq_replicate Let_def split: indrep.split list.split)

text ‹A frame filled in one pass, without the pairs of const‹zip›; a dead kernel
  item adds nothing to a finite set.›

fun vfill_row :: ‹indrep list ⇒ (nat × eff) list ⇒ indrep ⇒ indrep› where
  ‹vfill_row kav [] acc = acc›
| ‹vfill_row kav ((kk, e) # cs) acc = vfill_row kav cs (let R = getR kav kk in
     if irep_nonempty R then cunion acc (eapp e R)
     else (case acc of FinRep _ ⇒ acc | UpRep _ _ ⇒ cunion acc (FinRep [])))›

fun vfill_go :: ‹indrep list ⇒ indrep list ⇒ (nat × eff) list list ⇒ indrep list› where
  ‹vfill_go kav (R # Rs) (cs # css) = vfill_row kav cs R # vfill_go kav Rs css›
| ‹vfill_go kav _ _ = []›

lemma merge_Nil2 [simp]: ‹merge xs [] = xs›
  by (cases xs) simp_all

lemma eapp_dead: ‹¬ irep_nonempty R ⟹ eapp e R = FinRep []›
  by (simp add: eapp_def)

lemma vfill_row_fold:
  ‹vfill_row kav cs R = fold (λ(kk, e) acc. cunion acc (eapp e (getR kav kk))) cs R›
  by (induction kav cs R rule: vfill_row.induct) (simp add: Let_def eapp_dead split: indrep.split)+

lemma vfill_code [code]: ‹vfill cts kav = vfill_go kav kav cts›
proof -
  have ‹vfill_go kav Rs cts =
      map (λ(R, cs). fold (λ(kk, e) acc. cunion acc (eapp e (getR kav kk))) cs R) (zip Rs cts)› for Rs
    by (induction kav Rs cts rule: vfill_go.induct) (simp_all add: vfill_row_fold)
  then show ?thesis by (simp add: vfill_def)
qed

text ‹The plain successor const‹vgo› pads its kernel to every item of the target, so
  each contribution read from it by const‹getR› walks down a list as long as the state:
  quadratic in its items per transition. The diagnostics and the recovery run it; the code
  reads the padded kernel from an array instead.›

fun vfill_row_a :: ‹indrep iarray ⇒ (nat × eff) list ⇒ indrep ⇒ indrep› where
  ‹vfill_row_a A [] acc = acc›
| ‹vfill_row_a A ((kk, e) # cs) acc = vfill_row_a A cs (let R = iget A kk (FinRep []) in
     if irep_nonempty R then cunion acc (eapp e R)
     else (case acc of FinRep _ ⇒ acc | UpRep _ _ ⇒ cunion acc (FinRep [])))›

fun vfill_go_a :: ‹indrep iarray ⇒ indrep list ⇒ (nat × eff) list list ⇒ indrep list› where
  ‹vfill_go_a A (R # Rs) (cs # css) = vfill_row_a A cs R # vfill_go_a A Rs css›
| ‹vfill_go_a A _ _ = []›

lemma vfill_row_a: ‹vfill_row_a (IArray kav) cs R = vfill_row kav cs R›
proof (induction cs arbitrary: R)
  case (Cons c cs)
  then show ?case by (cases c) (simp add: iget_def getR_def)
qed simp

lemma vfill_go_code [code]: ‹vfill_go kav Rs css = vfill_go_a (IArray kav) Rs css›
  by (induction kav Rs css rule: vfill_go.induct) (simp_all add: vfill_row_a)

subsection ‹Numbered lookahead›

text ‹The checked driver with the lookahead numbered once, before the run, where
  const‹vrun_u› searches the token list at every shift and every licence.  A
  reduction finds its target frame by one const‹drop›, without the length of the
  stack.›

definition vnw :: ‹('n, 't) vtab ⇒ ('t × nat) list ⇒ (nat × nat) list› where
  ‹vnw V w = map (λ(a, c). (vnum V a, c)) w›

definition vmstep_n :: ‹('n, 't) vtab ⇒ vframes × (nat × nat) list ⇒ ('n, 't) vact ⇒
    (vframes × (nat × nat) list) option› where
  ‹vmstep_n V fw act = (case fw of (fs, w) ⇒ (case fs of [] ⇒ None | (j, av) # _ ⇒
     (case act of
        VShift ⇒ (case w of [] ⇒ None | (a, c) # w' ⇒
          (case iget (iget (v_sh V) j (IArray [])) a None of None ⇒ None
           | Some e ⇒ map_option (λf. (f # fs, w')) (vgo V e av (FinRep [c]))))
      | VReduce s b pr ⇒ (let fs' = drop (length (snd pr)) fs in (case fs' of [] ⇒ None
          | (j0, av0) # _ ⇒
            (case iget (iget (v_go V) j0 (IArray [])) b None of None ⇒ None
             | Some e ⇒ map_option (λf. (f # fs', w)) (vgo V e av0 (getR av s))))))))›

definition vlic_n :: ‹('n, 't) vtab ⇒ nat ⇒ (nat × nat) list ⇒ nat ⇒ indrep ⇒ bool› where
  ‹vlic_n V j w s RS = (case w of [] ⇒ s ∈ set (iget (v_ce V) j [])
     | (a, c) # _ ⇒ list_ex (λ(s', τ). s' = s ∧ irep_ex_wsat τ c RS)
         (iget (iget (v_cl V) j (IArray [])) a []))›

definition vcands_n :: ‹('n, 't) vtab ⇒ nat ⇒ indrep list ⇒ (nat × nat) list ⇒ ('n, 't) vact list› where
  ‹vcands_n V j av w = (let reds = map (λ(s, b, pr). VReduce s b pr)
       (filter (λ(s, b, pr). let RS = getR av s in irep_nonempty RS ∧ vlic_n V j w s RS)
         (iget (v_cp V) j []))
     in (case w of [] ⇒ reds | _ ⇒ VShift # reds))›

fun vchoose_n :: ‹('n, 't) vtab ⇒ vframes × (nat × nat) list ⇒ ('n, 't) vact list ⇒
    (('n, 't) vact × vframes × (nat × nat) list) option option› where
  ‹vchoose_n V fw [] = Some None›
| ‹vchoose_n V fw (a # acts) = (case vmstep_n V fw a of
     None ⇒ vchoose_n V fw acts
   | Some r ⇒ if a = VShift ∨ ¬ list_ex (λb. vmstep_n V fw b ≠ None) acts then Some (Some (a, r))
              else None)›

type_synonym ('m, 'ch, 'n, 't) vst_n =
  ‹vframes × (nat × nat) list × ('m, 'ch, 't) tword × ('m, 'ch, 'n, 't) ast list›

definition vstep_un :: ‹('n, 't) vtab ⇒ ('m, 'ch, 'n, 't) vst_n ⇒ ('m, 'ch, 'n, 't) vst_n option option› where
  ‹vstep_un V st = (case st of (fs, w, v, tstk) ⇒ (case fs of [] ⇒ Some None | (j, av) # _ ⇒
     (case vchoose_n V (fs, w) (vcands_n V j av w) of None ⇒ None | Some None ⇒ Some None
      | Some (Some (act, fs', w')) ⇒
          (case tstep (vdec act) (v, tstk) of (v', tstk') ⇒ Some (Some (fs', w', v', tstk'))))))›

definition vfinal_n :: ‹('n, 't) vtab ⇒ ('m, 'ch, 'n, 't) vst_n ⇒ bool› where
  ‹vfinal_n V st = (case st of (fs, w, v, tstk) ⇒ w = [] ∧ (case fs of [] ⇒ False
     | (j, av) # _ ⇒ irep_mem (v_ind0 V) (getR av (iget (v_fin V) j 0))))›

partial_function (option) vrun_un ::
  ‹('n, 't) vtab ⇒ ('m, 'ch, 'n, 't) vst_n ⇒ ('m, 'ch, 'n, 't) ast option option›
  where
  ‹vrun_un V st = (case st of (fs, w, v, tstk) ⇒
     if vfinal_n V st then Some (case tstk of t # _ ⇒ Some t | [] ⇒ None)
     else (case vstep_un V st of None ⇒ None | Some None ⇒ Some None
       | Some (Some st') ⇒ vrun_un V st'))›

lemmas vrun_un_simps [code] = vrun_un.simps

lemma vnw_simps [simp]: ‹vnw V [] = []› ‹vnw V ((a, c) # w) = (vnum V a, c) # vnw V w›
  by (simp_all add: vnw_def)

lemma vmstep_n_vnw:
  ‹vmstep_n V (fs, vnw V w) act = map_option (λ(fs', w'). (fs', vnw V w')) (vmstep V (fs, w) act)›
proof (cases act)
  case VShift
  then show ?thesis
    by (cases w) (auto simp: vmstep_n_def vmstep_def option.map_comp comp_def
        split: list.split option.split)
next
  case (VReduce s b pr)
  then show ?thesis
  proof (cases ‹length (snd pr) < length fs›)
    case True
    obtain j av fs1 where fs: ‹fs = (j, av) # fs1› using True by (cases fs) auto
    obtain j0 av0 where nth: ‹fs ! length (snd pr) = (j0, av0)› by (cases ‹fs ! length (snd pr)›)
    have dr: ‹drop (length (snd pr)) fs = (j0, av0) # drop (Suc (length (snd pr))) fs›
      using True nth by (metis Cons_nth_drop_Suc)
    show ?thesis using True nth dr unfolding VReduce fs
      by (auto simp: vmstep_n_def vmstep_def Let_def option.map_comp comp_def split: option.split)
  next
    case False
    then show ?thesis using VReduce
      by (auto simp: vmstep_n_def vmstep_def Let_def split: list.split)
  qed
qed

lemma vlic_n_vnw: ‹vlic_n V j (vnw V w) s RS = vlic V j w s RS›
  by (cases w) (auto simp: vlic_n_def vlic_def)

lemma vcands_n_vnw: ‹vcands_n V j av (vnw V w) = vcands V j av w›
  unfolding vcands_n_def vcands_def vlic_n_vnw by (cases w) auto

lemma vchoose_n_vnw:
  ‹vchoose_n V (fs, vnw V w) acts =
     map_option (map_option (λ(a, fs', w'). (a, fs', vnw V w'))) (vchoose V (fs, w) acts)›
proof (induction acts)
  case (Cons a acts)
  have ex: ‹list_ex (λb. vmstep_n V (fs, vnw V w) b ≠ None) acts ⟷
      list_ex (λb. vmstep V (fs, w) b ≠ None) acts›
    by (simp add: vmstep_n_vnw)
  show ?case using Cons.IH by (auto simp: vmstep_n_vnw ex split: option.split)
qed simp

lemma vstep_un_vnw:
  ‹vstep_un V (fs, vnw V w, v, tstk) =
     map_option (map_option (λ(fs', w', vt). (fs', vnw V w', vt))) (vstep_u V (fs, w, v, tstk))›
  by (auto simp: vstep_un_def vstep_u_def vchoose_n_vnw vcands_n_vnw
      split: list.split option.split prod.split)

lemma vfinal_n_vnw: ‹vfinal_n V (fs, vnw V w, v, tstk) = vfinal V (fs, w, v, tstk)›
  by (simp add: vfinal_n_def vfinal_def vnw_def)

lemma vrun_un_sound:
  assumes run: ‹vrun_un V vs = Some r›
  shows ‹∀fs w v tstk. vs = (fs, vnw V w, v, tstk) ⟶ vrun_u V (fs, w, v, tstk) = Some r›
proof (rule vrun_un.raw_induct[OF _ run], goal_cases)
  case (1 f V vs r)
  show ?case
  proof (intro allI impI)
    fix fs w v tstk
    assume vs: ‹vs = (fs, vnw V w, v, tstk)›
    note body = "1"(2)[unfolded vs, simplified vfinal_n_vnw vstep_un_vnw]
    show ‹vrun_u V (fs, w, v, tstk) = Some r›
    proof (cases ‹vfinal V (fs, w, v, tstk)›)
      case True
      with body show ?thesis by (subst vrun_u.simps) simp
    next
      case False
      show ?thesis
      proof (cases ‹vstep_u V (fs, w, v, tstk)›)
        case None
        with False body show ?thesis by simp
      next
        case (Some x)
        show ?thesis
        proof (cases x)
          case None
          with Some False body show ?thesis by (subst vrun_u.simps) simp
        next
          case (Some st1)
          obtain fs1 w1 v1 t1 where st1: ‹st1 = (fs1, w1, v1, t1)› by (cases st1)
          from ‹vstep_u V (fs, w, v, tstk) = Some x› Some st1 False body
          have ‹f V (fs1, vnw V w1, v1, t1) = Some r› by simp
          with "1"(1) have ‹vrun_u V st1 = Some r› unfolding st1 by blast
          with False ‹vstep_u V (fs, w, v, tstk) = Some x› Some show ?thesis
            by (subst vrun_u.simps) simp
        qed
      qed
    qed
  qed
qed

definition vtcols :: ‹('n, 't) vtab ⇒ ('m, 'ch, 't) tword ⇒ (nat × nat) list› where
  ‹vtcols V w = map (λt. (vnum V (tok t), s_col (span t))) w›

lemma vtcols_vnw: ‹vtcols V w = vnw V (tcols w)›
  by (simp add: vtcols_def vnw_def tcols_def)

text ‹The parser for the code generator: const‹vrun_un› on the numbered word, and
  the sparse driver should it meet a conflict.›

lemma dparse_via_tables_vun:
  assumes st: ‹pr0_states G Shn = sts›
    and gt: ‹pgtab G sts = gtab›
    and rt: ‹red_buckets G Shn (length sts) = redtab›
    and i0: ‹st_find sts (lr0_start G Shn) = i0›
    and fr: ‹fresh_name G Shn›
    and tb: ‹mk_stab G Shn gtab sts redtab = stb›
    and vt: ‹mk_vtab G Shn stb sts gtab redtab = vtb›
    and ki: ‹sinit stb = kin›
    and kc: ‹sclosure stb kin = kcl›
  shows ‹dparse G Shn w = (case vrun_un vtb ([v_av0 vtb], vtcols vtb w, w, []) of
      Some r ⇒ r | None ⇒ sdrun stb (([kin], tcols w), [kcl], [i0], w, []))›
proof (cases ‹vrun_un vtb ([v_av0 vtb], vtcols vtb w, w, [])›)
  case None
  then show ?thesis using dparse_via_tables_s[OF st gt rt i0 fr tb ki kc] by simp
next
  case (Some r)
  have ‹vrun_u vtb ([v_av0 vtb], tcols w, w, []) = Some r›
    using vrun_un_sound[OF Some] by (simp add: vtcols_vnw)
  then have ‹dparse G Shn w = r›
    using dparse_via_tables_vu[OF st gt rt i0 fr tb vt ki kc, of w] by simp
  with Some show ?thesis by simp
qed

subsection ‹Kernel-only frames›

text ‹An entry of the successor tables names the kernel items of the target
  state, and const‹vkav› pads them with an empty set for every other item.  The
  entries here keep the kernel items alone, with a plan of the target's items:
  whether each is a kernel item, and its contributions, each from the rank of
  its kernel item.  The tables come from const‹mk_vtab›'s by a map.›

type_synonym kentry = ‹nat × (nat × irel) list × (bool × (nat × eff) list) list›

datatype ('n, 't) vktab = VKTab
  (k_v: ‹('n, 't) vtab›)
  (k_sh: ‹kentry option iarray iarray›)
  (k_go: ‹kentry option iarray iarray›)

text ‹The kernel items, and the rank of a kernel item among them; for any other
  item a rank past them all, where a frame reads the empty set.›

fun ksome :: ‹'a option list ⇒ 'a list› where
  ‹ksome [] = []›
| ‹ksome (None # xs) = ksome xs›
| ‹ksome (Some x # xs) = x # ksome xs›

fun kidx :: ‹'a option list ⇒ nat ⇒ nat option› where
  ‹kidx [] k = None›
| ‹kidx (x # xs) k = (case k of
     0 ⇒ (case x of None ⇒ None | Some _ ⇒ Some 0)
   | Suc k' ⇒ (case x of None ⇒ kidx xs k' | Some _ ⇒ map_option Suc (kidx xs k')))›

definition krank :: ‹'a option list ⇒ nat ⇒ nat› where
  ‹krank km kk = (case kidx km kk of None ⇒ length km | Some r ⇒ r)›

definition kconv :: ‹('n, 't) vtab ⇒ nat × (nat × irel) option list ⇒ kentry› where
  ‹kconv V e = (case e of (j', km) ⇒ (j', ksome km,
     map (λ(x, cs). (x ≠ None, map (λ(kk, e). (krank km kk, e)) cs)) (zip km (iget (v_ct V) j' []))))›

definition kmap :: ‹('n, 't) vtab ⇒ (nat × (nat × irel) option list) option iarray iarray ⇒
    kentry option iarray iarray› where
  ‹kmap V T = IArray (map (λr. IArray (map (map_option (kconv V)) (IArray.list_of r))) (IArray.list_of T))›

definition mk_vktab :: ‹('n, 't) vtab ⇒ ('n, 't) vktab› where
  ‹mk_vktab V = VKTab V (kmap V (v_sh V)) (kmap V (v_go V))›

lemma iget_kmap:
  ‹iget (iget (kmap V T) j (IArray [])) a None = map_option (kconv V) (iget (iget T j (IArray [])) a None)›
  by (cases T) (auto simp: kmap_def iget_def)

fun vfill_p :: ‹indrep list ⇒ (bool × (nat × eff) list) list ⇒ indrep list ⇒ indrep list› where
  ‹vfill_p kav [] Rs = []›
| ‹vfill_p kav ((b, cs) # pl) Rs = (if b
     then (case Rs of [] ⇒ vfill_row kav cs (FinRep []) # vfill_p kav pl []
           | R # Rs' ⇒ vfill_row kav cs R # vfill_p kav pl Rs')
     else vfill_row kav cs (FinRep []) # vfill_p kav pl Rs)›

definition vgo_k :: ‹kentry ⇒ indrep list ⇒ indrep ⇒ (nat × indrep list) option› where
  ‹vgo_k e av RA = (case e of (j', ks, pl) ⇒ let kav = map (λ(ps, q). cpre q RA (getR av ps)) ks in
     if list_ex irep_nonempty kav then Some (j', vfill_p kav pl kav) else None)›

lemma vfill_p_zip:
  ‹vfill_p K (map (λ(x, cs). (x ≠ None, g cs)) (zip km cts)) (map f (ksome km)) =
     map (λ(x, cs). vfill_row K (g cs) (case_option (FinRep []) f x)) (zip km cts)›
proof (induction km arbitrary: cts)
  case (Cons x km)
  then show ?case by (cases cts; cases x) auto
qed simp

lemma length_ksome: ‹length (ksome xs) ≤ length xs›
  by (induction xs rule: ksome.induct) auto

lemma krank_getR:
  ‹getR (map (case_option (FinRep []) f) km) kk = getR (map f (ksome km)) (krank km kk)›
proof (induction km arbitrary: kk)
  case Nil
  then show ?case by (simp add: getR_def krank_def)
next
  case (Cons x km)
  have l: ‹length (ksome km) ≤ length km› by (rule length_ksome)
  show ?case
  proof (cases kk)
    case 0
    with l show ?thesis by (cases x) (auto simp: getR_def krank_def)
  next
    case (Suc k)
    have ih: ‹getR (map (case_option (FinRep []) f) km) k = getR (map f (ksome km)) (krank km k)›
      by (rule Cons.IH)
    show ?thesis
      using ih l by (cases x; cases ‹kidx km k›) (auto simp: Suc krank_def getR_def)
  qed
qed

lemma vfill_row_cong:
  ‹(⋀kk. getR K kk = getR K' (r kk)) ⟹ vfill_row K cs acc = vfill_row K' (map (λ(kk, e). (r kk, e)) cs) acc›
  by (induction K cs acc rule: vfill_row.induct) (simp_all add: Let_def)

lemma vgo_k_kconv: ‹vgo_k (kconv V e) av RA = vgo V e av RA›
proof (cases e)
  case (Pair j' km)
  let ?f = ‹λ(ps, q). cpre q RA (getR av ps)›
  have kav: ‹vkav km av RA = map (case_option (FinRep []) ?f) km›
    by (simp add: vkav_def)
  have live: ‹list_ex irep_nonempty (map ?f (ksome km)) =
      list_ex irep_nonempty (map (case_option (FinRep []) ?f) km)›
    by (induction km rule: ksome.induct) auto
  have row: ‹fold (λ(kk, e) acc. cunion acc (eapp e (getR (map (case_option (FinRep []) ?f) km) kk))) cs R =
      vfill_row (map ?f (ksome km)) (map (λ(kk, e). (krank km kk, e)) cs) R› for cs R
    unfolding vfill_row_fold[symmetric] by (rule vfill_row_cong[OF krank_getR])
  have fill: ‹vfill cts (map (case_option (FinRep []) ?f) km) =
      vfill_p (map ?f (ksome km))
        (map (λ(x, cs). (x ≠ None, map (λ(kk, e). (krank km kk, e)) cs)) (zip km cts))
        (map ?f (ksome km))› for cts
    unfolding vfill_p_zip vfill_def zip_map1 map_map
    by (rule map_cong) (auto simp: row)
  show ?thesis
    unfolding Pair vgo_k_def vgo_def kconv_def kav Let_def prod.case live fill ..
qed
subsection ‹The fused run›

text ‹const‹vrun_un› with a step taken in place: the shift when it is live, else
  the reduce candidates scanned in table order, without the list of candidates,
  the choice and the next state built between them.›

datatype ('n, 't) vsres = VSConf | VSRej | VSRed ‹'n × ('n, 't) rhs› vframes

definition vlive_k :: ‹('n, 't) vktab ⇒ nat ⇒ indrep list ⇒ (nat × nat) list ⇒ nat ⇒ bool› where
  ‹vlive_k K j av w s = (let RS = getR av s in irep_nonempty RS ∧ vlic_n (k_v K) j w s RS)›

definition vred_k :: ‹('n, 't) vktab ⇒ vframes ⇒ indrep list ⇒ nat ⇒ nat ⇒ 'n × ('n, 't) rhs ⇒
    vframes option› where
  ‹vred_k K fs av s b pr = (let fs' = drop (length (snd pr)) fs in (case fs' of [] ⇒ None
     | (j0, av0) # _ ⇒ (case iget (iget (k_go K) j0 (IArray [])) b None of None ⇒ None
        | Some e ⇒ map_option (λf. f # fs') (vgo_k e av0 (getR av s)))))›

fun vscan_k :: ‹('n, 't) vktab ⇒ vframes ⇒ (nat × nat) list ⇒ nat ⇒ indrep list ⇒
    (nat × nat × ('n × ('n, 't) rhs)) list ⇒ ('n, 't) vsres› where
  ‹vscan_k K fs w j av [] = VSRej›
| ‹vscan_k K fs w j av ((s, b, pr) # cs) = (if vlive_k K j av w s
     then (case vred_k K fs av s b pr of None ⇒ vscan_k K fs w j av cs
       | Some fs' ⇒ if list_ex (λ(s, b, pr). vlive_k K j av w s ∧ vred_k K fs av s b pr ≠ None) cs
                    then VSConf else VSRed pr fs')
     else vscan_k K fs w j av cs)›

definition vshift_k :: ‹('n, 't) vktab ⇒ nat ⇒ indrep list ⇒ (nat × nat) list ⇒ (nat × indrep list) option› where
  ‹vshift_k K j av w = (case w of [] ⇒ None | (a, c) # _ ⇒
     (case iget (iget (k_sh K) j (IArray [])) a None of None ⇒ None | Some e ⇒ vgo_k e av (FinRep [c])))›

partial_function (option) vrun_k ::
  ‹('n, 't) vktab ⇒ vframes ⇒ (nat × nat) list ⇒ ('m, 'ch, 't) tword ⇒ ('m, 'ch, 'n, 't) ast list ⇒
    ('m, 'ch, 'n, 't) ast option option›
  where
  ‹vrun_k K fs w v tstk = (if w = [] ∧ (case fs of [] ⇒ False
       | (j, av) # _ ⇒ irep_mem (v_ind0 (k_v K)) (getR av (iget (v_fin (k_v K)) j 0)))
     then Some (case tstk of t # _ ⇒ Some t | [] ⇒ None)
     else (case fs of [] ⇒ Some None | (j, av) # _ ⇒
       (case vshift_k K j av w of
          Some f ⇒ vrun_k K (f # fs) (tl w) (tl v) (Leaf (hd v) # tstk)
        | None ⇒ (case vscan_k K fs w j av (iget (v_cp (k_v K)) j []) of
            VSConf ⇒ None
          | VSRej ⇒ Some None
          | VSRed pr fs' ⇒ vrun_k K fs' w v
              (Node (fst pr) (rev (take (length (snd pr)) tstk)) # drop (length (snd pr)) tstk)))))›

lemmas vrun_k_simps [code] = vrun_k.simps

lemma k_v_mk [simp]: ‹k_v (mk_vktab V) = V›
  by (simp add: mk_vktab_def)

lemma vshift_k_vmstep:
  ‹vshift_k (mk_vktab V) j av w = Some f ⟹ vmstep_n V ((j, av) # fs, w) VShift = Some (f # (j, av) # fs, tl w)›
  ‹vshift_k (mk_vktab V) j av w = None ⟹ vmstep_n V ((j, av) # fs, w) VShift = None›
  by (auto simp: vshift_k_def vmstep_n_def mk_vktab_def iget_kmap vgo_k_kconv split: list.splits option.splits)
    (metis surj_pair)

lemma vred_k_vmstep:
  ‹vmstep_n V ((j, av) # fs, w) (VReduce s b pr) =
     map_option (λfs'. (fs', w)) (vred_k (mk_vktab V) ((j, av) # fs) av s b pr)›
  by (auto simp: vred_k_def vmstep_n_def mk_vktab_def iget_kmap vgo_k_kconv Let_def option.map_comp comp_def
      split: list.splits option.splits)

lemma vscan_k_vchoose:
  fixes V :: ‹('n, 't) vtab› and j :: nat and av :: ‹indrep list› and w :: ‹(nat × nat) list›
  defines ‹ok ≡ λ(s :: nat, b :: nat, pr :: 'n × ('n, 't) rhs). let RS = getR av s in irep_nonempty RS ∧ vlic_n V j w s RS›
  shows ‹vscan_k (mk_vktab V) ((j, av) # fs) w j av cs = VSRej ⟹
      vchoose_n V ((j, av) # fs, w) (map (λ(s, b, pr). VReduce s b pr) (filter ok cs)) = Some None›
    and ‹vscan_k (mk_vktab V) ((j, av) # fs) w j av cs = VSRed pr fs' ⟹ ∃s b.
      vchoose_n V ((j, av) # fs, w) (map (λ(s, b, pr). VReduce s b pr) (filter ok cs)) =
        Some (Some (VReduce s b pr, fs', w))›
proof (induction cs)
  case (Cons c cs)
  obtain s b p where c: ‹c = (s, b, p)› by (cases c)
  have lv: ‹vlive_k (mk_vktab V) j av w s ⟷ ok (s, b, p)›
    by (simp add: ok_def vlive_k_def)
  have ex: ‹list_ex (λb. vmstep_n V ((j, av) # fs, w) b ≠ None) (map (λ(s, b, pr). VReduce s b pr) (filter ok cs)) ⟷
      list_ex (λ(s, b, pr). vlive_k (mk_vktab V) j av w s ∧ vred_k (mk_vktab V) ((j, av) # fs) av s b pr ≠ None) cs›
    by (induction cs) (auto simp: vred_k_vmstep ok_def vlive_k_def)
  { case 1
    then show ?case using Cons.IH(1) lv ex
      by (auto simp: c vred_k_vmstep split: if_splits option.splits) }
  { case 2
    then show ?case using Cons.IH(2) lv ex
      by (auto simp: c vred_k_vmstep split: if_splits option.splits) }
qed simp_all

lemma vstep_un_k:
  fixes V :: ‹('n, 't) vtab›
  shows ‹vshift_k (mk_vktab V) j av w = Some f ⟹
      vstep_un V ((j, av) # fs, w, v, tstk) = Some (Some (f # (j, av) # fs, tl w, tl v, Leaf (hd v) # tstk))›
    and ‹vshift_k (mk_vktab V) j av w = None ⟹
      vscan_k (mk_vktab V) ((j, av) # fs) w j av (iget (v_cp V) j []) = VSRej ⟹
      vstep_un V ((j, av) # fs, w, v, tstk) = Some None›
    and ‹vshift_k (mk_vktab V) j av w = None ⟹
      vscan_k (mk_vktab V) ((j, av) # fs) w j av (iget (v_cp V) j []) = VSRed pr fs' ⟹
      vstep_un V ((j, av) # fs, w, v, tstk) =
        Some (Some (fs', w, v, Node (fst pr) (rev (take (length (snd pr)) tstk)) # drop (length (snd pr)) tstk))›
proof -
  let ?reds = ‹map (λ(s, b, pr). VReduce s b pr) (filter (λ(s :: nat, b :: nat, pr :: 'n × ('n, 't) rhs).
      let RS = getR av s in irep_nonempty RS ∧ vlic_n V j w s RS) (iget (v_cp V) j []))›
  have none: ‹vchoose_n V ((j, av) # fs, w) (vcands_n V j av w) = vchoose_n V ((j, av) # fs, w) ?reds›
    if ‹vshift_k (mk_vktab V) j av w = None›
    using vshift_k_vmstep(2)[OF that, of fs] by (cases w) (simp_all add: vcands_n_def)
  { assume sh: ‹vshift_k (mk_vktab V) j av w = Some f›
    then have ‹w ≠ []› by (auto simp: vshift_k_def)
    then show ‹vstep_un V ((j, av) # fs, w, v, tstk) = Some (Some (f # (j, av) # fs, tl w, tl v, Leaf (hd v) # tstk))›
      using vshift_k_vmstep(1)[OF sh, of fs] by (cases w) (auto simp: vstep_un_def vcands_n_def) }
  { assume sh: ‹vshift_k (mk_vktab V) j av w = None›
      and sc: ‹vscan_k (mk_vktab V) ((j, av) # fs) w j av (iget (v_cp V) j []) = VSRej›
    show ‹vstep_un V ((j, av) # fs, w, v, tstk) = Some None›
      using vscan_k_vchoose(1)[OF sc] none[OF sh] by (simp add: vstep_un_def) }
  { assume sh: ‹vshift_k (mk_vktab V) j av w = None›
      and sc: ‹vscan_k (mk_vktab V) ((j, av) # fs) w j av (iget (v_cp V) j []) = VSRed pr fs'›
    show ‹vstep_un V ((j, av) # fs, w, v, tstk) =
        Some (Some (fs', w, v, Node (fst pr) (rev (take (length (snd pr)) tstk)) # drop (length (snd pr)) tstk))›
      using vscan_k_vchoose(2)[OF sc] none[OF sh] by (auto simp: vstep_un_def) }
qed

lemma vrun_k_sound:
  assumes run: ‹vrun_k K fs w v tstk = Some r›
  shows ‹K = mk_vktab V ⟶ vrun_un V (fs, w, v, tstk) = Some r›
proof (rule vrun_k.raw_induct[where P = ‹λK fs w v tstk r. K = mk_vktab V ⟶ vrun_un V (fs, w, v, tstk) = Some r›,
    OF _ run], goal_cases)
  case (1 f K fs w v tstk r)
  show ?case
  proof
    assume K: ‹K = mk_vktab V›
    note body = "1"(2)[unfolded K k_v_mk]
    have fin: ‹vfinal_n V (fs, w, v, tstk) ⟷ w = [] ∧ (case fs of [] ⇒ False
        | (j, av) # _ ⇒ irep_mem (v_ind0 V) (getR av (iget (v_fin V) j 0)))›
      by (simp add: vfinal_n_def)
    show ‹vrun_un V (fs, w, v, tstk) = Some r›
    proof (cases ‹vfinal_n V (fs, w, v, tstk)›)
      case True
      with body fin show ?thesis by (subst vrun_un.simps) simp
    next
      case nf: False
      show ?thesis
      proof (cases fs)
        case Nil
        with nf body fin show ?thesis by (subst vrun_un.simps) (simp add: vstep_un_def)
      next
        case (Cons fr fs1)
        obtain j av where fr: ‹fr = (j, av)› by (cases fr)
        note body = body[unfolded Cons fr]
        note nf' = nf[unfolded Cons fr]
        have nfin: ‹¬ (w = [] ∧ irep_mem (v_ind0 V) (getR av (iget (v_fin V) j 0)))›
          using nf' fin[unfolded Cons fr] by simp
        show ?thesis
        proof (cases ‹vshift_k (mk_vktab V) j av w›)
          case (Some f')
          from nfin Some body have ‹f K (f' # (j, av) # fs1) (tl w) (tl v) (Leaf (hd v) # tstk) = Some r›
            by (cases w) (simp_all add: K)
          with "1"(1) K have ‹vrun_un V (f' # (j, av) # fs1, tl w, tl v, Leaf (hd v) # tstk) = Some r›
            by blast
          with nf' show ?thesis
            unfolding Cons fr by (subst vrun_un.simps) (simp add: vstep_un_k(1)[OF Some, of fs1 v tstk])
        next
          case sh: None
          show ?thesis
          proof (cases ‹vscan_k (mk_vktab V) ((j, av) # fs1) w j av (iget (v_cp V) j [])›)
            case VSConf
            from nfin sh VSConf body show ?thesis by (cases w) (simp_all add: K)
          next
            case VSRej
            from nfin sh VSRej body have ‹r = None› by (cases w) (simp_all add: K)
            with nf' show ?thesis
              unfolding Cons fr by (subst vrun_un.simps) (simp add: vstep_un_k(2)[OF sh VSRej, of v tstk])
          next
            case (VSRed pr fs')
            from nfin sh VSRed body have ‹f K fs' w v
                (Node (fst pr) (rev (take (length (snd pr)) tstk)) # drop (length (snd pr)) tstk) = Some r›
              by (cases w) (simp_all add: K)
            with "1"(1) K have ‹vrun_un V (fs', w, v,
                Node (fst pr) (rev (take (length (snd pr)) tstk)) # drop (length (snd pr)) tstk) = Some r›
              by blast
            with nf' show ?thesis
              unfolding Cons fr by (subst vrun_un.simps) (simp add: vstep_un_k(3)[OF sh VSRed, of v tstk])
          qed
        qed
      qed
    qed
  qed
qed

text ‹The parser for the code generator: const‹vrun_k› over the kernel-only tables,
  and the sparse driver should it meet a conflict.›

lemma dparse_via_tables_vk:
  assumes st: ‹pr0_states G Shn = sts›
    and gt: ‹pgtab G sts = gtab›
    and rt: ‹red_buckets G Shn (length sts) = redtab›
    and i0: ‹st_find sts (lr0_start G Shn) = i0›
    and fr: ‹fresh_name G Shn›
    and tb: ‹mk_stab G Shn gtab sts redtab = stb›
    and vt: ‹mk_vtab G Shn stb sts gtab redtab = vtb›
    and kt: ‹mk_vktab vtb = vktb›
    and ki: ‹sinit stb = kin›
    and kc: ‹sclosure stb kin = kcl›
  shows ‹dparse G Shn w = (case vrun_k vktb [v_av0 vtb] (vtcols vtb w) w [] of
      Some r ⇒ r | None ⇒ sdrun stb (([kin], tcols w), [kcl], [i0], w, []))›
proof (cases ‹vrun_k vktb [v_av0 vtb] (vtcols vtb w) w []›)
  case None
  then show ?thesis using dparse_via_tables_s[OF st gt rt i0 fr tb ki kc] by simp
next
  case (Some r)
  have ‹vrun_un vtb ([v_av0 vtb], vtcols vtb w, w, []) = Some r›
    using vrun_k_sound[OF Some] kt by simp
  then show ?thesis
    using dparse_via_tables_vun[OF st gt rt i0 fr tb vt ki kc, of w] Some by simp
qed

text ‹The numbers of some tokens, from the tokens of the tables alone: no table has
  to be built to know them. The backend evaluates them with its checks, so that a
  token type of constructors without arguments is numbered by a case distinction
  rather than a search through const‹v_lal›.›

definition vnums :: ‹('n, 't) is_cfg ⇒ 'n ⇒ 't list ⇒ nat list› where
  ‹vnums G Shn ctrs =
     map (ntidx (vtoks G (red_buckets G Shn (length (pr0_states G Shn))))) ctrs›

lemma vnums_map:
  assumes st: ‹pr0_states G Shn = sts›
    and rt: ‹red_buckets G Shn (length sts) = redtab›
    and vt: ‹mk_vtab G Shn stb sts gtab redtab = vtb›
    and ns: ‹vnums G Shn ctrs = ns›
  shows ‹map (vnum vtb) ctrs = ns›
proof -
  have ‹vnum vtb = ntidx (vtoks G redtab)›
    by (rule ext) (rule vnum_mk[OF vt[symmetric]])
  then show ?thesis unfolding ns[symmetric] vnums_def st rt by simp
qed

definition vtnum :: ‹('t ⇒ nat) ⇒ ('m, 'ch, 't) tword ⇒ (nat × nat) list› where
  ‹vtnum f w = map (λt. (f (tok t), s_col (span t))) w›

lemma vtcols_vtnum: ‹vtcols V w = vtnum (vnum V) w›
  by (simp add: vtcols_def vtnum_def)

lemma dparse_via_tables_vkn:
  assumes st: ‹pr0_states G Shn = sts›
    and gt: ‹pgtab G sts = gtab›
    and rt: ‹red_buckets G Shn (length sts) = redtab›
    and i0: ‹st_find sts (lr0_start G Shn) = i0›
    and fr: ‹fresh_name G Shn›
    and tb: ‹mk_stab G Shn gtab sts redtab = stb›
    and vt: ‹mk_vtab G Shn stb sts gtab redtab = vtb›
    and kt: ‹mk_vktab vtb = vktb›
    and ki: ‹sinit stb = kin›
    and kc: ‹sclosure stb kin = kcl›
    and tn: ‹vnum vtb = f›
  shows ‹dparse G Shn w = (case vrun_k vktb [v_av0 vtb] (vtnum f w) w [] of
      Some r ⇒ r | None ⇒ sdrun stb (([kin], tcols w), [kcl], [i0], w, []))›
  unfolding tn[symmetric] vtcols_vtnum[symmetric]
  by (rule dparse_via_tables_vk[OF st gt rt i0 fr tb vt kt ki kc])

section ‹Building the tables once›

text ‹const‹mk_vtab› states each entry on its own, which the proofs want and the
  code generator should not follow: const‹vits› runs a closure per state, token and
  nonterminal, and const‹trow› a fixpoint per contribution.  Its code equation
  computes the closures and the transfer rows once, and the edges of the transfer
  graph once for all rows.›

definition tr_step_c :: ‹('n, 't) stab ⇒ (nat × irel) list iarray ⇒ eff list ⇒ eff list› where
  ‹tr_step_c T ti row = map (λa. fold ejoin (map (λ(c, q). ecomp (of_rel q) (row ! c)) (ti !! a)) (row ! a))
     [0..<s_np T]›

lemma tr_step_c: ‹tr_step_c T (IArray (map (tin T) [0..<s_np T])) = tr_step T›
  by (auto simp: fun_eq_iff tr_step_c_def tr_step_def)

definition trows :: ‹('n, 't) stab ⇒ eff list iarray› where
  ‹trows T = (let ti = IArray (map (tin T) [0..<s_np T]) in
     IArray (map (λb. the (while_option (λrow. tr_step_c T ti row ≠ row) (tr_step_c T ti)
       (tinit (s_np T) b))) [0..<s_np T]))›

definition vrow :: ‹eff list iarray ⇒ ('n, 't) stab ⇒ nat ⇒ eff list› where
  ‹vrow R T b = (if b < IArray.length R then R !! b else trow T b)›

lemma vrow_trows: ‹vrow (trows T) T b = trow T b›
  by (simp add: vrow_def trows_def tr_step_c trow_def trow_loop_def)

definition vcontrib_c :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) stab ⇒ eff list iarray ⇒
    ('n, 't) citem list ⇒ ('n, 't) citem ⇒ (nat × eff) list› where
  ‹vcontrib_c G Shn T R its it = (if is_slot G it then
     List.map_filter (λkk. if is_slot G (its ! kk) then None else
       (case vnext_nt G (its ! kk) of None ⇒ None
        | Some (B, q) ⇒ Some (kk, ecomp (vrow R T (nnum G Shn B) ! nnum G Shn (fst (fst it))) (of_rel q))))
       [0..<length its]
   else [])›

lemma vcontrib_c: ‹vcontrib_c G Shn T (trows T) = vcontrib G Shn T›
  unfolding vcontrib_c_def[abs_def] vcontrib_def[abs_def] vrow_trows ..

definition vits_tab :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list list ⇒ ('n, 't) citem list iarray› where
  ‹vits_tab G sts = IArray (map (vits G sts) [0..<length sts])›

lemma vits_tab: ‹iget (vits_tab G sts) j [] = vits G sts j›
  by (simp add: iget_def vits_tab_def vits_def)

definition ventry_c :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) citem list iarray ⇒ nat ⇒ ('n, 't) sym ⇒ (nat × (nat × irel) option list) option› where
  ‹ventry_c gt sts A j X = (let j' = dnext gt sts j X in
     if j' < length sts then Some (j', vkmap (iget A j []) X (iget A j' [])) else None)›

lemma ventry_c: ‹ventry_c gt sts (vits_tab G sts) = ventry G gt sts›
  by (simp add: fun_eq_iff ventry_c_def ventry_def vits_tab Let_def)

definition vinit_frame_c :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) stab ⇒ eff list iarray ⇒
    ('n, 't) citem list list ⇒ ('n, 't) citem list iarray ⇒ nat × indrep list› where
  ‹vinit_frame_c G Shn T R sts A = (let i0 = st_find sts (lr0_start G Shn); its = iget A i0 [] in
     (i0, vfill (map (vcontrib_c G Shn T R its) its)
       (map (λit. if it = (start_prod G Shn, 0) then FinRep [istart_ind G] else FinRep []) its)))›

lemma vinit_frame_c: ‹vinit_frame_c G Shn T (trows T) sts (vits_tab G sts) = vinit_frame G Shn T sts›
  by (simp add: vinit_frame_c_def vinit_frame_def vits_tab vcontrib_c Let_def)

lemma mk_vtab_code [code]:
  ‹mk_vtab G Shn T sts gt redtab = (let toks = vtoks G redtab; ns = [0..<length sts];
       ps = eprods G Shn; A = vits_tab G sts; R = trows T in
     VTab (zip toks [0..<length toks]) (length toks)
       (IArray (map (λj. IArray (map (λa. ventry_c gt sts A j (Tm a)) toks)) ns))
       (IArray (map (λj. IArray (map (λb. ventry_c gt sts A j (Nt (fst (ps ! b)))) [0..<length ps])) ns))
       (IArray (map (λj. let its = iget A j [] in map (vcontrib_c G Shn T R its) its) ns))
       (IArray (map (λj. vcomps G Shn (iget A j [])) ns))
       (IArray (map (λj. let its = iget A j [] in
          IArray (map (λa. vcells its j (redtab ! j) (Some a)) toks)) ns))
       (IArray (map (λj. map fst (vcells (iget A j []) j (redtab ! j) None)) ns))
       (IArray (map (λj. ntidx (iget A j []) (start_prod G Shn, 1)) ns))
       (vinit_frame_c G Shn T R sts A)
       (istart_ind G))›
  by (simp add: mk_vtab_def Let_def ventry_c vcontrib_c vits_tab vinit_frame_c)

text ‹The two names are too short to keep from later theories' variables.›

hide_const (open) sh cn

end