Theory LR_Simple

(* Author: Basil Fürer, Dmitriy Traytel *)

theory LR_Simple
  imports LR_Det "HOL-Library.IArray"
begin

section ‹A table-driven driver for grammars without layout annotations›

text ‹
  For a grammar whose relations are all const‹Any› (const‹ii›), the
  indentation sets of the set-anchored driver carry no information beyond
  whether they are empty: every set is empty or contains the start
  indentation. Such a grammar is an ordinary context-free grammar: Adams
  encodes one by giving every symbol the unconstrained relation (const‹Any›)
  cite‹‹Sect.~4› in "adams2013"›. The live items of a frame are then exactly those of the state of
  the precise automaton const‹pr0_states› the driver tracks, and the
  driver's choices are read off its index. This theory defines a driver over
  the index stack alone and proves that it computes the same result as
  const‹dparse›. It is the LR parser of DeRemer and Pennello
  cite‹‹Sect.~2.2› in "deremer1982-lalr-lookahead"›: a stack of automaton states and
  tables for the transition and reduce functions.
›

subsection ‹Anchor sets are empty or contain the start indentation›

definition anch_set :: ‹nat ⇒ indrep ⇒ bool› where
  ‹anch_set i0 R ⟷ irep_set R = {} ∨ i0 ∈ irep_set R›

definition anch_items :: ‹nat ⇒ ('n, 't) xitem list ⇒ bool› where
  ‹anch_items i0 xs ⟷ (∀(pr, m, R) ∈ set xs. anch_set i0 R)›

text ‹The relations in the productions of the items: const‹Any›, or
  const‹Eq› on a nonterminal (the start production).›

definition rel_ok :: ‹irel ⇒ ('n, 't) sym ⇒ bool› where
  ‹rel_ok r X ⟷ r = Any ∨ (r = Eq ∧ (∃B. X = Nt B))›

definition anns_ok :: ‹('n, 't) xitem list ⇒ bool› where
  ‹anns_ok xs ⟷ (∀(pr, m, R) ∈ set xs. ∀k < length (snd pr).
     rel_ok (snd (snd pr ! k)) (fst (snd pr ! k)))›

lemma rel_okD: ‹rel_ok r X ⟹ r = Any ∨ r = Eq›
  unfolding rel_ok_def by blast

lemma ii_rels:
  assumes ‹ii G› and ‹pr ∈ set (iprods G)› and ‹k < length (snd pr)›
  shows ‹snd (snd pr ! k) = Any›
  using assms unfolding ii_def by (cases pr) (auto simp: list_all_iff)

lemma anch_set_union:
  ‹anch_set i0 R1 ⟹ anch_set i0 R2 ⟹ anch_set i0 (irep_union R1 R2)›
  unfolding anch_set_def by auto

lemma anch_set_img:
  ‹anch_set i0 R ⟹ r = Any ∨ r = Eq ⟹ anch_set i0 (irep_img r R)›
  unfolding anch_set_def by auto

lemma anch_set_fold_xcontrib:
  assumes ‹anch_set i0 acc›
    and ‹⋀A rhs m R. ((A, rhs), m, R) ∈ set items ⟹
            anch_set i0 R ∧ (∀k < length rhs. snd (rhs ! k) = Any ∨ snd (rhs ! k) = Eq)›
  shows ‹anch_set i0 (fold (xcontrib pr) items acc)›
  using assms
proof (induction items arbitrary: acc)
  case (Cons it items)
  obtain A rhs m R where it: ‹it = ((A, rhs), m, R)› by (cases it) auto
  have ok: ‹anch_set i0 R› ‹∀k < length rhs. snd (rhs ! k) = Any ∨ snd (rhs ! k) = Eq›
    using Cons.prems(2)[of A rhs m R] it by auto
  have c: ‹anch_set i0 (xcontrib pr it acc)›
    using ok Cons.prems(1) unfolding it
    by (auto intro!: anch_set_union anch_set_img)
  have h: ‹anch_set i0 R ∧ (∀k < length rhs. snd (rhs ! k) = Any ∨ snd (rhs ! k) = Eq)›
    if ‹((A, rhs), m, R) ∈ set items› for A rhs m R
    using Cons.prems(2)[of A rhs m R] that by simp
  show ?case using Cons.IH[OF c h] by simp
qed simp

lemma xiter_anch:
  assumes ii: ‹ii G› and kern: ‹anch_items i0 xs› and anns: ‹anns_ok xs›
  shows ‹p < length (iprods G) ⟹ anch_set i0 (xiter G xs t ! p)›
proof (induction t arbitrary: p)
  case 0
  then show ?case by (simp add: anch_set_def)
next
  case (Suc t)
  have len: ‹length (xiter G xs t) = length (iprods G)› by simp
  show ?case
    unfolding xiter.simps xround_nth[OF len Suc.prems]
  proof (rule anch_set_fold_xcontrib)
    show ‹anch_set i0 (xiter G xs t ! p)› by (rule Suc.IH[OF Suc.prems])
  next
    fix A rhs m R assume mem: ‹((A, rhs), m, R) ∈ set (xslots G xs (xiter G xs t))›
    show ‹anch_set i0 R ∧ (∀k < length rhs. snd (rhs ! k) = Any ∨ snd (rhs ! k) = Eq)›
      using mem
    proof (rule xslots_memE)
      assume mem: ‹((A, rhs), m, R) ∈ set xs›
      have ‹anch_set i0 R› using kern mem unfolding anch_items_def by fastforce
      moreover have ‹∀k < length rhs. snd (rhs ! k) = Any ∨ snd (rhs ! k) = Eq›
        using anns mem rel_okD unfolding anns_ok_def by fastforce
      ultimately show ?thesis by blast
    next
      fix q assume q: ‹q < length (iprods G)› and ‹q < length (xiter G xs t)›
        and eq: ‹((A, rhs), m, R) = (iprods G ! q, 0, xiter G xs t ! q)›
      have pr: ‹(A, rhs) ∈ set (iprods G)› using q eq by (metis nth_mem prod.inject)
      have ‹R = xiter G xs t ! q› using eq by simp
      then have ‹anch_set i0 R› using Suc.IH[OF q] by simp
      moreover have ‹∀k < length rhs. snd (rhs ! k) = Any›
        using ii_rels[OF ii pr] by simp
      ultimately show ?thesis by simp
    qed
  qed
qed

lemma xclosure_auto_anch:
  assumes ii: ‹ii G› and kern: ‹anch_items i0 xs› and anns: ‹anns_ok xs›
  shows ‹anch_items i0 (xclosure_auto G xs)›
  unfolding anch_items_def
proof (intro ballI, clarify)
  fix pr m R assume mem: ‹(pr, m, R) ∈ set (xclosure_auto G xs)›
  then have ‹(pr, m, R) ∈ set (xslots G xs (xiter G xs (xfuel G xs)))›
    unfolding xclosure_auto_def xclosure_def .
  then show ‹anch_set i0 R›
  proof (rule xslots_memE)
    assume ‹(pr, m, R) ∈ set xs›
    then show ?thesis using kern unfolding anch_items_def by fastforce
  next
    fix q assume q: ‹q < length (iprods G)› and ‹q < length (xiter G xs (xfuel G xs))›
      and ‹(pr, m, R) = (iprods G ! q, 0, xiter G xs (xfuel G xs) ! q)›
    then show ?thesis using xiter_anch[OF ii kern anns q] by simp
  qed
qed

lemma xclosure_auto_anns_mem:
  assumes ii: ‹ii G› and anns: ‹anns_ok xs›
    and mem: ‹(pr, m, R) ∈ set (xclosure_auto G xs)› and k: ‹k < length (snd pr)›
  shows ‹rel_ok (snd (snd pr ! k)) (fst (snd pr ! k))›
proof -
  have mem': ‹(pr, m, R) ∈ set (xslots G xs (xiter G xs (xfuel G xs)))›
    using mem unfolding xclosure_auto_def xclosure_def .
  show ?thesis
    using mem'
  proof (rule xslots_memE)
    assume ‹(pr, m, R) ∈ set xs›
    then show ?thesis using anns k unfolding anns_ok_def by fastforce
  next
    fix q assume q: ‹q < length (iprods G)› and ‹q < length (xiter G xs (xfuel G xs))›
      and eq: ‹(pr, m, R) = (iprods G ! q, 0, xiter G xs (xfuel G xs) ! q)›
    have ‹pr ∈ set (iprods G)› using q eq by simp
    then show ?thesis using ii_rels[OF ii _ k] by (simp add: rel_ok_def)
  qed
qed

lemma xclosure_auto_anns:
  assumes ii: ‹ii G› and anns: ‹anns_ok xs›
  shows ‹anns_ok (xclosure_auto G xs)›
  unfolding anns_ok_def using xclosure_auto_anns_mem[OF ii anns] by fast

subsection ‹The live part of a closure is the reachable closure›

lemma irep_img_nonempty: ‹irep_set R ≠ {} ⟹ irep_set (irep_img r R) ≠ {}›
proof -
  assume ‹irep_set R ≠ {}›
  then obtain i where i: ‹i ∈ irep_set R› by blast
  have ‹∃j. irel_sat r j i› by (cases r) (auto intro: exI[of _ ‹Suc i›] exI[of _ i])
  then show ?thesis using i by auto
qed

lemma creach_funpow_live:
  assumes stable: ‹xstable G xs cls› and len: ‹length cls = length (iprods G)›
    and kern: ‹set s ⊆ lcore xs›
  shows ‹set ((creach_step G ^^ k) s) ⊆ lcore (xslots G xs cls)›
proof (induction k)
  case 0
  have ‹lcore xs ⊆ lcore (xslots G xs cls)›
    unfolding lcore_def using xslots_kernel by fast
  then show ?case using kern by simp
next
  case (Suc k)
  let ?cs = ‹(creach_step G ^^ k) s›
  show ?case
  proof
    fix c assume ‹c ∈ set ((creach_step G ^^ Suc k) s)›
    then have ‹c ∈ set (creach_step G ?cs)› by simp
    then consider ‹c ∈ set ?cs›
      | pr pr' m' where ‹c = (pr, 0)› ‹pr ∈ set (iprods G)› ‹(pr', m') ∈ set ?cs›
          ‹m' < length (snd pr')› ‹fst (snd pr' ! m') = Nt (fst pr)›
      unfolding creach_step_set by blast
    then show ‹c ∈ lcore (xslots G xs cls)›
    proof cases
      case 1 then show ?thesis using Suc.IH by blast
    next
      case (2 pr pr' m')
      from 2(3) Suc.IH have ‹(pr', m') ∈ lcore (xslots G xs cls)› by blast
      then obtain R' where mem': ‹(pr', m', R') ∈ set (xslots G xs cls)›
        and ne: ‹irep_nonempty R'› unfolding lcore_def by blast
      from 2(2) obtain q where q: ‹q < length (iprods G)› and pq: ‹iprods G ! q = pr›
        by (metis in_set_conv_nth)
      obtain A rhs where pr': ‹pr' = (A, rhs)› by (cases pr')
      have img: ‹ximg pr (pr', m', R') ≠ {}›
        using 2(4,5) ne irep_img_nonempty[of R' ‹snd (rhs ! m')›]
        unfolding pr' by auto
      have ‹ximg (iprods G ! q) (pr', m', R') ⊆ irep_set (xround G xs cls ! q)›
        unfolding xround_nth[OF len q] fold_xcontrib_set using mem' by blast
      also have ‹… ⊆ irep_set (cls ! q)› by (rule xstableD[OF stable len q])
      finally have ‹irep_nonempty (cls ! q)› using img pq by auto
      moreover have ‹(iprods G ! q, 0, cls ! q) ∈ set (xslots G xs cls)›
        using xslots_slot[OF q] len q by simp
      ultimately show ?thesis unfolding 2(1) lcore_def pq[symmetric] by blast
    qed
  qed
qed

theorem lcore_xclosure_auto:
  assumes kern: ‹lcore xs = set s›
  shows ‹lcore (xclosure_auto G xs) = set (creach G s)›
proof
  show ‹lcore (xclosure_auto G xs) ⊆ set (creach G s)›
  proof
    fix c assume ‹c ∈ lcore (xclosure_auto G xs)›
    then obtain pr m R where c: ‹c = (pr, m)› and mem: ‹(pr, m, R) ∈ set (xclosure_auto G xs)›
      and ne: ‹irep_nonempty R› unfolding lcore_def by blast
    from ne obtain j where ‹j ∈ irep_set R› by auto
    have k: ‹⋀pr m R. (pr, m, R) ∈ set xs ⟹ irep_nonempty R ⟹ (pr, m) ∈ set s›
      using kern unfolding lcore_def by blast
    from xclosure_auto_live_creach[OF k mem ‹j ∈ _›] show ‹c ∈ set (creach G s)› using c by simp
  qed
next
  show ‹set (creach G s) ⊆ lcore (xclosure_auto G xs)›
    unfolding creach_def xclosure_auto_def xclosure_def
    by (rule creach_funpow_live[OF xfuel_stable]) (use kern in simp_all)
qed


subsection ‹The set-valued goto on live cores›

text ‹Through a position with relation const‹Any› an item keeps its set; through
  const‹Eq› (only the start production has it) it is intersected with the
  goto's set, which contains the start indentation.›

definition goto_ok :: ‹nat ⇒ ('n, 't) xitem list ⇒ ('n, 't) sym ⇒ indrep ⇒ bool› where
  ‹goto_ok i0 CL X RA ⟷ irep_nonempty RA ∧
     (∀(pr, m, R) ∈ set CL. m < length (snd pr) ⟶ fst (snd pr ! m) = X ⟶
        snd (snd pr ! m) = Any ∨ (snd (snd pr ! m) = Eq ∧ i0 ∈ irep_set RA))›

lemma goto_set:
  assumes ok: ‹goto_ok i0 CL X RA› and anch: ‹anch_set i0 R›
    and mem: ‹(pr, m, R) ∈ set CL› and m: ‹m < length (snd pr)› and X: ‹fst (snd pr ! m) = X›
  shows ‹irep_set (irep_inter R (irep_pre (snd (snd pr ! m)) RA)) = {} ⟷ irep_set R = {}›
    and ‹anch_set i0 (irep_inter R (irep_pre (snd (snd pr ! m)) RA))›
proof -
  have ne: ‹irep_set RA ≠ {}› using ok unfolding goto_ok_def by simp
  have r: ‹snd (snd pr ! m) = Any ∨ (snd (snd pr ! m) = Eq ∧ i0 ∈ irep_set RA)›
    using ok mem m X unfolding goto_ok_def by fastforce
  have pa: ‹irep_set (irep_pre Any RA) = UNIV› using ne by auto
  have pe: ‹irep_set (irep_pre Eq RA) = irep_set RA› by simp
  from r consider ‹snd (snd pr ! m) = Any› | ‹snd (snd pr ! m) = Eq› ‹i0 ∈ irep_set RA› by blast
  then have ‹(irep_set (irep_inter R (irep_pre (snd (snd pr ! m)) RA)) = {} ⟷ irep_set R = {}) ∧
      anch_set i0 (irep_inter R (irep_pre (snd (snd pr ! m)) RA))›
  proof cases
    case 1 then show ?thesis using pa anch by (simp add: anch_set_def)
  next
    case 2 then show ?thesis using pe anch unfolding anch_set_def by auto
  qed
  then show ‹irep_set (irep_inter R (irep_pre (snd (snd pr ! m)) RA)) = {} ⟷ irep_set R = {}›
    and ‹anch_set i0 (irep_inter R (irep_pre (snd (snd pr ! m)) RA))› by blast+
qed

lemma set_cgoto:
  ‹set (cgoto cs X) = {(pr, Suc m) | pr m. (pr, m) ∈ set cs ∧ m < length (snd pr) ∧ fst (snd pr ! m) = X}›
  unfolding cgoto_def by force

theorem lcore_lgoto:
  assumes ok: ‹goto_ok i0 CL X RA› and anch: ‹anch_items i0 CL› and cs: ‹lcore CL = set cs›
  shows ‹lcore (lgoto CL X RA) = set (cgoto cs X)›
proof -
  have a: ‹anch_set i0 R› if ‹(pr, m, R) ∈ set CL› for pr m R
    using anch that unfolding anch_items_def by fastforce
  have ‹lcore (lgoto CL X RA) =
      {(pr, Suc m) | pr m. (pr, m) ∈ lcore CL ∧ m < length (snd pr) ∧ fst (snd pr ! m) = X}›
  proof (intro equalityI subsetI)
    fix c assume ‹c ∈ lcore (lgoto CL X RA)›
    then obtain pr m' R' where c: ‹c = (pr, m')› and mem: ‹(pr, m', R') ∈ set (lgoto CL X RA)›
      and ne: ‹irep_nonempty R'› unfolding lcore_def by blast
    from mem obtain m R where m': ‹m' = Suc m› and memCL: ‹(pr, m, R) ∈ set CL›
      and m: ‹m < length (snd pr)› and X: ‹fst (snd pr ! m) = X›
      and R': ‹R' = irep_inter R (irep_pre (snd (snd pr ! m)) RA)›
      unfolding lgoto_def by auto
    have ‹irep_nonempty R› using goto_set(1)[OF ok a[OF memCL] memCL m X] ne R' by auto
    then have ‹(pr, m) ∈ lcore CL› using memCL unfolding lcore_def by blast
    then show ‹c ∈ {(pr, Suc m) | pr m. (pr, m) ∈ lcore CL ∧ m < length (snd pr) ∧ fst (snd pr ! m) = X}›
      using c m' m X by blast
  next
    fix c assume ‹c ∈ {(pr, Suc m) | pr m. (pr, m) ∈ lcore CL ∧ m < length (snd pr) ∧ fst (snd pr ! m) = X}›
    then obtain pr m where c: ‹c = (pr, Suc m)› and l: ‹(pr, m) ∈ lcore CL›
      and m: ‹m < length (snd pr)› and X: ‹fst (snd pr ! m) = X› by blast
    from l obtain R where memCL: ‹(pr, m, R) ∈ set CL› and ne: ‹irep_nonempty R›
      unfolding lcore_def by blast
    have mem: ‹(pr, Suc m, irep_inter R (irep_pre (snd (snd pr ! m)) RA)) ∈ set (lgoto CL X RA)›
      by (rule lgoto_memI[OF memCL m X])
    have ‹irep_nonempty (irep_inter R (irep_pre (snd (snd pr ! m)) RA))›
      using goto_set(1)[OF ok a[OF memCL] memCL m X] ne by auto
    then show ‹c ∈ lcore (lgoto CL X RA)› using mem c unfolding lcore_def by blast
  qed
  also have ‹… = set (cgoto cs X)› unfolding set_cgoto cs by blast
  finally show ?thesis .
qed

lemma lgoto_anch:
  assumes ok: ‹goto_ok i0 CL X RA› and anch: ‹anch_items i0 CL›
  shows ‹anch_items i0 (lgoto CL X RA)›
  unfolding anch_items_def
proof (intro ballI, clarify)
  fix pr m' R' assume mem: ‹(pr, m', R') ∈ set (lgoto CL X RA)›
  from mem obtain m R where memCL: ‹(pr, m, R) ∈ set CL›
    and m: ‹m < length (snd pr)› and X: ‹fst (snd pr ! m) = X›
    and R': ‹R' = irep_inter R (irep_pre (snd (snd pr ! m)) RA)›
    unfolding lgoto_def by auto
  have ‹anch_set i0 R› using anch memCL unfolding anch_items_def by fastforce
  from goto_set(2)[OF ok this memCL m X] show ‹anch_set i0 R'› using R' by simp
qed

lemma lgoto_anns: ‹anns_ok CL ⟹ anns_ok (lgoto CL X RA)›
  unfolding anns_ok_def lgoto_def by fastforce

text ‹The two gotos of the driver meet const‹goto_ok›: a terminal has
  relation const‹Any› everywhere, and the set of a reduce contains the start
  indentation when it is not empty.›

lemma goto_ok_Tm:
  ‹anns_ok CL ⟹ irep_nonempty RA ⟹ goto_ok i0 CL (Tm a) RA›
  unfolding goto_ok_def anns_ok_def rel_ok_def by fastforce

lemma goto_ok_Nt:
  ‹anns_ok CL ⟹ irep_nonempty RA ⟹ i0 ∈ irep_set RA ⟹ goto_ok i0 CL (Nt A) RA›
  unfolding goto_ok_def anns_ok_def rel_ok_def by fastforce

lemma red_set_anch:
  assumes ‹anch_items i0 CL› and ‹irep_nonempty (red_set CL pr)›
  shows ‹i0 ∈ irep_set (red_set CL pr)›
proof -
  from assms(2) obtain R where mem: ‹(pr, length (snd pr), R) ∈ set CL› and ne: ‹irep_nonempty R›
    unfolding red_set_nonempty_iff by blast
  have ‹anch_set i0 R› using assms(1) mem unfolding anch_items_def by fastforce
  then have ‹i0 ∈ irep_set R› using ne unfolding anch_set_def by auto
  then show ?thesis unfolding red_set_correct using mem by blast
qed

text ‹The successor in the precise automaton, with the sentinel
  term‹length psts› for a dead successor.›

theorem pnext_resolve:
  assumes psts: ‹psts = pr0_states G Shn› and p: ‹p < length psts›
  shows ‹dnext (pgtab G psts) psts p X < length psts ⟷ cgoto (creach G (psts ! p)) X ≠ []›
    and ‹dnext (pgtab G psts) psts p X < length psts ⟹
           set (psts ! dnext (pgtab G psts) psts p X) = set (cgoto (creach G (psts ! p)) X)›
proof -
  let ?s = ‹psts ! p› and ?pgt = ‹pgtab G psts›
  have len: ‹length ?pgt = length psts› unfolding pgtab_def by simp
  have dn: ‹dnext ?pgt psts p X = la_next ?pgt psts p X› unfolding dnext_def using p len by simp
  have s_in: ‹?s ∈ set psts› using p by simp
  have univ: ‹set ?s ⊆ cuniv G Shn›
    by (rule pr0_states_univ) (use s_in psts in simp)
  have ‹(dnext ?pgt psts p X < length psts ⟷ cgoto (creach G ?s) X ≠ []) ∧
      (dnext ?pgt psts p X < length psts ⟶
         set (psts ! dnext ?pgt psts p X) = set (cgoto (creach G ?s) X))›
  proof (cases ‹∃pr m. (pr, m) ∈ set (creach G ?s) ∧ m < length (snd pr) ∧ fst (snd pr ! m) = X›)
    case True
    then obtain pr m where mem: ‹(pr, m) ∈ set (creach G ?s)› and m: ‹m < length (snd pr)›
      and X: ‹fst (snd pr ! m) = X› by blast
    have ‹(pr, m) ∈ cuniv G Shn› using creach_univ[OF univ] mem by blast
    from cuniv_next_gram_syms[OF this m] have X_sym: ‹X ∈ set (gram_syms G)› using X by simp
    obtain t where t: ‹t ∈ set psts› and te: ‹set t = set (cgoto (creach G ?s) X)›
      using pr0_states_closed[OF s_in[unfolded psts] X_sym] unfolding psts by blast
    from st_find_found[OF t te] have
        sf_lt: ‹st_find psts (cgoto (creach G ?s) X) < length psts›
      and sf_set: ‹set (psts ! st_find psts (cgoto (creach G ?s) X)) = set (cgoto (creach G ?s) X)›
      by auto
    have look: ‹map_of (?pgt ! p) X = Some (st_find psts (cgoto (creach G ?s) X))›
      using pgtab_lookup[OF p mem m] X by simp
    have eq: ‹dnext ?pgt psts p X = st_find psts (cgoto (creach G ?s) X)›
      unfolding dn la_next_def look using sf_lt by simp
    have ‹cgoto (creach G ?s) X ≠ []›
      using cgoto_memI[OF mem m X] by auto
    then show ?thesis using eq sf_lt sf_set by simp
  next
    case False
    have none: ‹map_of (?pgt ! p) X = None›
      by (rule pgtab_none[OF p]) (use False in blast)
    have eq: ‹dnext ?pgt psts p X = length psts› unfolding dn la_next_def none by simp
    have f: ‹filter (λ(pr, m). m < length (snd pr) ∧ fst (snd pr ! m) = X) (creach G ?s) = []›
      unfolding filter_empty_conv using False by fast
    have ‹cgoto (creach G ?s) X = []› unfolding cgoto_def f by simp
    then show ?thesis using eq by simp
  qed
  then show ‹dnext ?pgt psts p X < length psts ⟷ cgoto (creach G ?s) X ≠ []›
    and ‹dnext ?pgt psts p X < length psts ⟹
           set (psts ! dnext ?pgt psts p X) = set (cgoto (creach G ?s) X)› by blast+
qed


subsection ‹The simple driver›

text ‹Per state: the productions it completes, and whether it completes the
  start production.›

definition pcomps :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list list ⇒ ('n × ('n, 't) rhs) list list› where
  ‹pcomps G sts =
     map (λs. remdups (map fst (filter (λ(pr, m). m = length (snd pr)) (creach G s)))) sts›

definition pfins :: ‹'n ⇒ ('n, 't) citem list list ⇒ bool list› where
  ‹pfins Shn sts = map (λs. list_ex (λ(pr, m). fst pr = Shn ∧ m = Suc 0) s) sts›

text ‹A reduce cell licenses the reduce by naming the next token (or the end of
  the input); the width relation is not consulted.›

definition slic :: ‹nat ⇒ ('n, 't) lacell list ⇒ ('m, 'ch, 't) tword ⇒ 'n × ('n, 't) rhs ⇒ bool› where
  ‹slic i cells v pr ⟷ list_ex (λ(i', itm, t, τ).
       i' = i ∧ itm = (pr, length (snd pr)) ∧
       (case v of [] ⇒ t = None | x # _ ⇒ t = Some (tok x))) cells›

definition scands :: ‹('n × ('n, 't) rhs) list ⇒ nat ⇒ ('n, 't) lacell list ⇒
    ('m, 'ch, 't) tword ⇒ ('n, 't) dact list› where
  ‹scands comps i cells v = (let reds = map DReduce (filter (slic i cells v) comps)
     in (case v of [] ⇒ reds | _ ⇒ DShift # reds))›

text ‹The successor of an action, if it is live.›

definition starget :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    nat list ⇒ ('m, 'ch, 't) tword ⇒ ('n, 't) dact ⇒ nat option› where
  ‹starget gt sts stk v act = (case act of
      DShift ⇒ (case v of [] ⇒ None | x # _ ⇒
        let q = dnext gt sts (hd stk) (Tm (tok x)) in
        if q < length sts then Some q else None)
    | DReduce pr ⇒ (if length (snd pr) < length stk then
        let q = dnext gt sts (stk ! length (snd pr)) (Nt (fst pr)) in
        if q < length sts then Some q else None
      else None))›

fun spick :: ‹('a ⇒ 'b option) ⇒ 'a list ⇒ ('a × 'b) option› where
  ‹spick f [] = None›
| ‹spick f (a # as) = (case f a of Some b ⇒ Some (a, b) | None ⇒ spick f as)›

type_synonym ('m, 'ch, 't) sctl_t = ‹nat list × ('m, 'ch, 't) tword›

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

text ‹The step on the control part (the index stack and the input).›

definition sctl :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list list ⇒ ('n × ('n, 't) rhs) list list ⇒ ('m, 'ch, 't) sctl_t ⇒
    (('n, 't) dact × ('m, 'ch, 't) sctl_t) option› where
  ‹sctl gt sts redtab pc c = (case c of (stk, v) ⇒
     (case stk of [] ⇒ None | i # _ ⇒
       let cells = (if i < length redtab then redtab ! i else []);
           comps = (if i < length pc then pc ! i else [])
       in (case spick (starget gt sts stk v) (scands comps i cells v) of
            None ⇒ None
          | Some (act, q) ⇒ Some (act, case act of
              DShift ⇒ (q # stk, tl v)
            | DReduce pr ⇒ (q # drop (length (snd pr)) stk, v)))))›

definition stree :: ‹('n, 't) dact ⇒ ('m, 'ch, 't) tword ⇒ ('m, 'ch, 'n, 't) ast list ⇒
    ('m, 'ch, 'n, 't) ast list› where
  ‹stree act v tstk = (case act of
      DShift ⇒ Leaf (hd v) # tstk
    | DReduce pr ⇒ Node (fst pr) (rev (take (length (snd pr)) tstk)) # drop (length (snd pr)) tstk)›

definition sstep :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list list ⇒ ('n × ('n, 't) rhs) list list ⇒ ('m, 'ch, 'n, 't) sst ⇒
    ('m, 'ch, 'n, 't) sst option› where
  ‹sstep gt sts redtab pc st = (case st of (stk, v, tstk) ⇒
     map_option (λ(act, stk', v'). (stk', v', stree act v tstk)) (sctl gt sts redtab pc (stk, v)))›

definition sfinal :: ‹bool list ⇒ ('m, 'ch, 't) sctl_t ⇒ bool› where
  ‹sfinal pf c ⟷ (case c of (stk, v) ⇒ v = [] ∧ stk ≠ [] ∧ hd stk < length pf ∧ pf ! hd stk)›

definition sresult :: ‹('m, 'ch, 'n, 't) ast list ⇒ ('m, 'ch, 'n, 't) ast option› where
  ‹sresult tstk = (case tstk of t # _ ⇒ Some t | [] ⇒ None)›

fun srun :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list list ⇒ ('n × ('n, 't) rhs) list list ⇒ bool list ⇒ nat ⇒
    ('m, 'ch, 'n, 't) sst ⇒ ('m, 'ch, 'n, 't) ast option› where
  ‹srun gt sts redtab pc pf 0 st = (case st of (stk, v, tstk) ⇒
     if sfinal pf (stk, v) then sresult tstk else None)›
| ‹srun gt sts redtab pc pf (Suc n) st = (case st of (stk, v, tstk) ⇒
     if sfinal pf (stk, v) then sresult tstk
     else (case sstep gt sts redtab pc st of
             None ⇒ None
           | Some st' ⇒ srun gt sts redtab pc pf n st'))›

partial_function (option) srunwf ::
  ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list list ⇒ ('n × ('n, 't) rhs) list list ⇒ bool list ⇒
    ('m, 'ch, 'n, 't) sst ⇒ ('m, 'ch, 'n, 't) ast option›
  where
  ‹srunwf gt sts redtab pc pf st = (case st of (stk, v, tstk) ⇒
     if sfinal pf (stk, v) then sresult tstk
     else Option.bind (sstep gt sts redtab pc st) (srunwf gt sts redtab pc pf))›

text ‹The run with a history of the stacks since the last shift, over any
  step on the control part (const‹sctl›, or the indexed step below) and
  final test.›

partial_function (option) srun_hist ::
  ‹(('m, 'ch, 't) sctl_t ⇒ (('n, 't) dact × ('m, 'ch, 't) sctl_t) option) ⇒
    (('m, 'ch, 't) sctl_t ⇒ bool) ⇒ nat list list ⇒
    ('m, 'ch, 'n, 't) sst ⇒ ('m, 'ch, 'n, 't) ast option›
  where
  ‹srun_hist ctl fin seen st = (case st of (stk, v, tstk) ⇒
     if fin (stk, v) then sresult tstk
     else if stk ∈ set seen then None
     else Option.bind (ctl (stk, v)) (λ(act, stk', v').
       srun_hist ctl fin (if act = DShift then [] else stk # seen)
         (stk', v', stree act v tstk)))›

lemmas srun_hist_simps [code] = srun_hist.simps

definition sinit :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒ ('m, 'ch, 't) tword ⇒
    ('m, 'ch, 'n, 't) sst› where
  ‹sinit G Shn sts w = ([st_find sts (lr0_start G Shn)], w, [])›

definition sparse :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('m, 'ch, 't) tword ⇒ ('m, 'ch, 'n, 't) ast option› where
  ‹sparse G Shn w = (let sts = pr0_states G Shn; gt = pgtab G sts;
       redtab = red_buckets G Shn (length sts)
     in srunwf gt sts redtab (pcomps G sts) (pfins Shn sts) (sinit G Shn sts w))›


subsection ‹The simulation relation›

text ‹The static conditions: no layout annotations, operational determinism,
  and reduce cells naming a token carry no width constraint.›

definition wany_ok :: ‹('n, 't) lacell list list ⇒ bool› where
  ‹wany_ok redtab ⟷ list_all (list_all (λ(i, itm, t, τ). t = None ∨ τ = WAny)) redtab›

definition sstatic :: ‹('n, 't) is_cfg ⇒ 'n ⇒ bool› where
  ‹sstatic G Shn ⟷ ii G ∧ mdet G Shn ∧
     wany_ok (red_buckets G Shn (length (pr0_states G Shn)))›

lemma sstaticI:
  ‹ii G ⟹ rlalr_conflicts G Shn = [] ⟹ fresh_name G Shn ⟹
     wany_ok (red_buckets G Shn (length (pr0_states G Shn))) ⟹ sstatic G Shn›
  unfolding sstatic_def using rlalr_sufficient[of G Shn] by (intro conjI) simp_all

lemma wany_okD:
  ‹wany_ok redtab ⟹ i < length redtab ⟹ (i', itm, t, τ) ∈ set (redtab ! i) ⟹
     t ≠ None ⟹ τ = WAny›
  unfolding wany_ok_def list_all_iff by (fastforce dest: nth_mem)

definition sctrl :: ‹('m, 'ch, 'n, 't) sst ⇒ ('m, 'ch, 't) sctl_t› where
  ‹sctrl ss = (case ss of (stk, v, tstk) ⇒ (stk, v))›

definition ssim :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
    ('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) sst ⇒ bool› where
  ‹ssim G Shn sts st ss ⟷ (case st of ((Xs, w), cstk, istk, v, tstk) ⇒
     case ss of (stk, v', tstk') ⇒
       v' = v ∧ tstk' = tstk ∧ w = tcols v ∧ Xs ≠ [] ∧ stk = istk ∧
       cstk_ok G Xs cstk ∧ didx_ok G (pr0_states G Shn) Xs istk ∧
       (∀k < length Xs. istk ! k < length sts ∧ set (sts ! (istk ! k)) = lcore (Xs ! k)) ∧
       (∀X ∈ set Xs. anch_items (istart_ind G) X ∧ anns_ok X) ∧
       imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn) ((Xs, w), istk))›

lemma ssim_init:
  assumes sts: ‹sts = pr0_states G Shn›
  shows ‹ssim G Shn sts (dinit G Shn sts w) (sinit G Shn sts w)›
proof -
  obtain t where t: ‹t ∈ set sts› and te: ‹set t = set (ccore (xinit G Shn))›
    using pr0_states_start[of G Shn] sts by blast
  from st_find_found[OF t te[unfolded ccore_xinit]]
  have lt: ‹st_find sts (lr0_start G Shn) < length sts›
    and eq: ‹set (sts ! st_find sts (lr0_start G Shn)) = set (lr0_start G Shn)› by auto
  have anch: ‹anch_items (istart_ind G) (xinit G Shn)›
    unfolding anch_items_def anch_set_def xinit_def by simp
  have anns: ‹anns_ok (xinit G Shn)›
    unfolding anns_ok_def rel_ok_def xinit_def by simp
  show ?thesis
    unfolding ssim_def dinit_def sinit_def
    using lt eq anch anns
    by (simp add: cstk_ok_def lcore_xinit didx_ok_init[OF tables_ok_concrete] imreach_init sts)
qed

lemma ssim_len:
  ‹ssim G Shn sts ((Xs, w), cstk, istk, v, tstk) (stk, v', tstk') ⟹ length stk = length Xs›
  unfolding ssim_def using didx_ok_len by fastforce

lemma ssim_final:
  assumes sim: ‹ssim G Shn sts ((Xs, w), cstk, istk, v, tstk) (stk, v', tstk')›
  shows ‹gfinal G Shn (Xs, w) ⟷ sfinal (pfins Shn sts) (stk, v')›
proof -
  from sim have v: ‹v' = v› ‹w = tcols v› and ne: ‹Xs ≠ []› and si: ‹stk = istk›
    and p: ‹istk ! 0 < length sts› ‹set (sts ! (istk ! 0)) = lcore (Xs ! 0)›
    and anch: ‹anch_items (istart_ind G) (hd Xs)›
    unfolding ssim_def by auto
  have len: ‹length stk = length Xs› using ssim_len[OF sim] .
  then have stk_ne: ‹stk ≠ []› using ne by auto
  then have hd: ‹hd stk = stk ! 0› by (simp add: hd_conv_nth)
  have hdX: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
  have i0: ‹⋀pr m R. (pr, m, R) ∈ set (hd Xs) ⟹ irep_mem (istart_ind G) R ⟷ irep_nonempty R›
    using anch unfolding anch_items_def anch_set_def by fastforce
  have ‹list_ex (λ(pr, m, R). fst pr = Shn ∧ m = Suc 0 ∧ irep_mem (istart_ind G) R) (hd Xs) ⟷
        (∃(pr, m) ∈ lcore (hd Xs). fst pr = Shn ∧ m = Suc 0)›
    unfolding list_ex_iff lcore_def using i0 by fastforce
  also have ‹… ⟷ pfins Shn sts ! hd stk›
    unfolding pfins_def using p hd hdX si by (auto simp: list_ex_iff)
  moreover have ‹w = [] ⟷ v' = []› using v by (simp add: tcols_def)
  ultimately show ?thesis
    unfolding gfinal_def sfinal_def using ne stk_ne p hd si by (auto simp: pfins_def)
qed

lemma pcomps_mem:
  ‹p < length sts ⟹
     pr ∈ set (pcomps G sts ! p) ⟷ (pr, length (snd pr)) ∈ set (creach G (sts ! p))›
  unfolding pcomps_def by force

lemma slic_dlic:
  assumes c: ‹⋀i' itm t τ. (i', itm, t, τ) ∈ set cells ⟹ t ≠ None ⟹ τ = WAny›
    and ne: ‹irep_nonempty RS›
  shows ‹dlic i cells (tcols v) pr RS ⟷ slic i cells v pr›
proof -
  show ?thesis
  proof (cases v)
    case Nil
    then show ?thesis unfolding dlic_def slic_def by simp
  next
    case (Cons x v')
    have ‹⋀i' itm t τ. (i', itm, t, τ) ∈ set cells ⟹ t = Some (tok x) ⟹
        irep_ex_wsat τ (s_col (span x)) RS›
      using c ne by fastforce
    then show ?thesis unfolding dlic_def slic_def Cons list_ex_iff by fastforce
  qed
qed


subsection ‹Candidates and picks›

lemma cstk_ok_map: ‹cstk_ok G Xs cstk ⟷ cstk = map (xclosure_auto G) Xs›
  unfolding cstk_ok_def by (induction Xs arbitrary: cstk) (auto simp: list_all2_Cons1)

lemma dpick_NoneD:
  ‹dpick G cstk gc acts = None ⟹ a ∈ set acts ⟹ mstep_cached G cstk gc a = Some gc' ⟹
     ¬ dlive gc'›
  by (induction acts) (auto split: option.splits if_splits)

lemma spick_SomeD: ‹spick f xs = Some (a, b) ⟹ a ∈ set xs ∧ f a = Some b›
  by (induction xs) (auto split: option.splits)

lemma spick_None_iff: ‹spick f xs = None ⟷ (∀a ∈ set xs. f a = None)›
  by (induction xs) (auto split: option.splits)

lemma dcands_mem:
  assumes ‹Xs ≠ []›
  shows ‹act ∈ set (dcands G i cells CL (Xs, w)) ⟷ (case act of
      DShift ⇒ w ≠ []
    | DReduce pr ⇒ irep_nonempty (red_set CL pr) ∧ dlic i cells w pr (red_set CL pr))›
proof -
  have comp: ‹pr ∈ set (remdups (map fst (filter (λ(pr, m, R). m = length (snd pr)) CL)))›
    if ‹irep_nonempty (red_set CL pr)› for pr
  proof -
    from that obtain R where ‹(pr, length (snd pr), R) ∈ set CL›
      unfolding red_set_nonempty_iff by blast
    then show ?thesis by force
  qed
  show ?thesis
    using assms comp unfolding dcands_def
    by (cases act; cases w) (auto simp: Let_def)
qed

lemma scands_mem:
  ‹act ∈ set (scands comps i cells v) ⟷ (case act of
      DShift ⇒ v ≠ []
    | DReduce pr ⇒ pr ∈ set comps ∧ slic i cells v pr)›
  unfolding scands_def by (cases act; cases v) auto


subsection ‹One step›

context
  fixes G :: ‹('n, 't) is_cfg› and Shn :: 'n
    and sts :: ‹('n, 't) citem list list› and gt :: ‹(('n, 't) sym × nat) list list›
    and redtab :: ‹('n, 't) lacell list list› and pc :: ‹('n × ('n, 't) rhs) list list›
  assumes static: ‹sstatic G Shn›
    and sts: ‹sts = pr0_states G Shn› and gt: ‹gt = pgtab G sts›
    and redtab: ‹redtab = red_buckets G Shn (length sts)›
    and pc: ‹pc = pcomps G sts›
begin

lemma tabs: ‹tables_ok G Shn sts gt (la_fix G Shn)›
  using tables_ok_concrete[of G Shn] unfolding sts gt .

lemma ii: ‹ii G› and det: ‹mdet G Shn›
  and wany: ‹wany_ok (red_buckets G Shn (length sts))›
  using static unfolding sstatic_def sts by blast+

context
  fixes Xs :: ‹('n, 't) xitem list list› and w cstk istk
    and v :: ‹('m, 'ch, 't) tword› and tstk :: ‹('m, 'ch, 'n, 't) ast list› and stk i
  assumes sim: ‹ssim G Shn sts ((Xs, w), cstk, istk, v, tstk) (stk, v, tstk)›
    and hd_stk: ‹hd stk = i›
begin

lemma c_ne: ‹Xs ≠ []› and c_w: ‹w = tcols v› and c_stk: ‹stk = istk›
  and c_cstk: ‹cstk = map (xclosure_auto G) Xs›
  and c_didx: ‹didx_ok G sts Xs istk›
  and c_reach: ‹imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn) ((Xs, w), istk)›
  using sim unfolding ssim_def sts cstk_ok_map by auto

lemma c_prec: ‹k < length Xs ⟹ istk ! k < length sts ∧ set (sts ! (istk ! k)) = lcore (Xs ! k)›
  using sim unfolding ssim_def by auto

lemma c_frames: ‹X ∈ set Xs ⟹ anch_items (istart_ind G) X ∧ anns_ok X›
  using sim unfolding ssim_def by auto

lemma c_ilen: ‹length istk = length Xs›
  using didx_ok_len[OF c_didx] .

lemma c_len: ‹length stk = length Xs›
  using c_stk c_ilen by simp

lemma c_hd0: ‹stk ! 0 = i› and c_hdX: ‹hd Xs = Xs ! 0›
  using c_len c_ne hd_stk by (cases stk; cases Xs; simp)+

lemma c_istk_case: ‹(case istk of [] ⇒ length sts | j # _ ⇒ j) = i›
  using c_stk c_len c_ne hd_stk by (cases stk) auto

lemma c_cstk_case: ‹(case cstk of [] ⇒ [] | c # _ ⇒ c) = xclosure_auto G (hd Xs)›
  using c_cstk c_ne by (cases Xs) auto

lemma c_istk0: ‹istk ! 0 = i›
  using c_stk c_hd0 by simp

lemma c_i_lt: ‹i < length sts›
  using c_prec[of 0] c_ne c_istk0 by simp

lemma c_cells: ‹(if i < length redtab then redtab ! i else []) = red_buckets G Shn (length sts) ! i›
  using c_i_lt unfolding redtab by simp

lemma c_comps: ‹(if i < length pc then pc ! i else []) = pcomps G sts ! i›
  using c_i_lt unfolding pc pcomps_def by simp

lemma c_frame_cl:
  assumes ‹k < length Xs›
  shows ‹lcore (xclosure_auto G (Xs ! k)) = set (creach G (sts ! (istk ! k)))›
    and ‹anch_items (istart_ind G) (xclosure_auto G (Xs ! k))›
    and ‹anns_ok (xclosure_auto G (Xs ! k))›
proof -
  have f: ‹anch_items (istart_ind G) (Xs ! k) ∧ anns_ok (Xs ! k)›
    using c_frames assms by simp
  show ‹lcore (xclosure_auto G (Xs ! k)) = set (creach G (sts ! (istk ! k)))›
    by (rule lcore_xclosure_auto) (use c_prec[OF assms] in simp)
  show ‹anch_items (istart_ind G) (xclosure_auto G (Xs ! k))›
    using xclosure_auto_anch[OF ii] f by blast
  show ‹anns_ok (xclosure_auto G (Xs ! k))›
    using xclosure_auto_anns[OF ii] f by blast
qed

lemma c_CL:
  ‹lcore (xclosure_auto G (hd Xs)) = set (creach G (sts ! i))›
  ‹anch_items (istart_ind G) (xclosure_auto G (hd Xs))›
  ‹anns_ok (xclosure_auto G (hd Xs))›
  using c_frame_cl[of 0] c_ne c_istk0 c_hdX by simp_all

lemma c_red_comps:
  ‹irep_nonempty (red_set (xclosure_auto G (hd Xs)) pr) ⟷ pr ∈ set (pcomps G sts ! i)›
  unfolding pcomps_mem[OF c_i_lt] c_CL(1)[symmetric] red_set_nonempty_iff lcore_def by blast

lemma c_shift:
  assumes v: ‹v = x # v'›
  shows ‹mstep G (Xs, w) DShift =
      Some (lgoto (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)]) # Xs, tcols v')›
    and ‹lcore (lgoto (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)])) =
      set (cgoto (creach G (sts ! i)) (Tm (tok x)))›
proof -
  show ‹mstep G (Xs, w) DShift =
      Some (lgoto (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)]) # Xs, tcols v')›
    unfolding mstep_def mstep_cached_def using c_ne by (simp add: c_w v hd_map)
  show ‹lcore (lgoto (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)])) =
      set (cgoto (creach G (sts ! i)) (Tm (tok x)))›
    by (rule lcore_lgoto[OF goto_ok_Tm[OF c_CL(3)] c_CL(2) c_CL(1)]) simp
qed

lemma c_reduce:
  assumes n: ‹length (snd pr) < length Xs›
    and RS: ‹irep_nonempty (red_set (xclosure_auto G (hd Xs)) pr)›
  shows ‹mstep G (Xs, w) (DReduce pr) =
      Some (lgoto (xclosure_auto G (Xs ! length (snd pr))) (Nt (fst pr))
              (red_set (xclosure_auto G (hd Xs)) pr) # drop (length (snd pr)) Xs, w)›
    and ‹lcore (lgoto (xclosure_auto G (Xs ! length (snd pr))) (Nt (fst pr))
              (red_set (xclosure_auto G (hd Xs)) pr)) =
      set (cgoto (creach G (sts ! (istk ! length (snd pr)))) (Nt (fst pr)))›
proof -
  show ‹mstep G (Xs, w) (DReduce pr) =
      Some (lgoto (xclosure_auto G (Xs ! length (snd pr))) (Nt (fst pr))
              (red_set (xclosure_auto G (hd Xs)) pr) # drop (length (snd pr)) Xs, w)›
    unfolding mstep_def mstep_cached_def using c_ne n RS by (simp add: Let_def hd_map)
  have ok: ‹goto_ok (istart_ind G) (xclosure_auto G (Xs ! length (snd pr))) (Nt (fst pr))
      (red_set (xclosure_auto G (hd Xs)) pr)›
    by (rule goto_ok_Nt[OF c_frame_cl(3)[OF n] RS red_set_anch[OF c_CL(2) RS]])
  show ‹lcore (lgoto (xclosure_auto G (Xs ! length (snd pr))) (Nt (fst pr))
              (red_set (xclosure_auto G (hd Xs)) pr)) =
      set (cgoto (creach G (sts ! (istk ! length (snd pr)))) (Nt (fst pr)))›
    by (rule lcore_lgoto[OF ok c_frame_cl(2)[OF n] c_frame_cl(1)[OF n]])
qed

lemma c_act_iff:
  ‹(act ∈ set (dcands G i (red_buckets G Shn (length sts) ! i) (xclosure_auto G (hd Xs)) (Xs, w)) ∧
     (∃gc'. mstep G (Xs, w) act = Some gc' ∧ dlive gc')) ⟷
   (act ∈ set (scands (pcomps G sts ! i) i (red_buckets G Shn (length sts) ! i) v) ∧
     starget gt sts stk v act ≠ None)›
proof (cases act)
  case DShift
  show ?thesis
  proof (cases v)
    case Nil
    then show ?thesis unfolding DShift dcands_mem[OF c_ne] scands_mem using c_w by simp
  next
    case (Cons x v')
    have pr: ‹dnext gt sts i (Tm (tok x)) < length sts ⟷
        cgoto (creach G (sts ! i)) (Tm (tok x)) ≠ []›
      using pnext_resolve(1)[OF sts c_i_lt] unfolding gt .
    show ?thesis unfolding DShift dcands_mem[OF c_ne] scands_mem c_shift(1)[OF Cons]
      using pr c_shift(2)[OF Cons] c_w Cons hd_stk by (simp add: dlive_lcore starget_def Let_def)
  qed
next
  case (DReduce pr)
  show ?thesis
  proof (cases ‹irep_nonempty (red_set (xclosure_auto G (hd Xs)) pr)›)
    case False
    then show ?thesis unfolding DReduce dcands_mem[OF c_ne] scands_mem c_red_comps by simp
  next
    case RS: True
    have lic: ‹dlic i (red_buckets G Shn (length sts) ! i) w pr (red_set (xclosure_auto G (hd Xs)) pr)
        ⟷ slic i (red_buckets G Shn (length sts) ! i) v pr›
      unfolding c_w
      by (rule slic_dlic[OF wany_okD[OF wany] RS]) (use c_i_lt in simp_all)
    show ?thesis
    proof (cases ‹length (snd pr) < length Xs›)
      case False
      then have ‹mstep G (Xs, w) (DReduce pr) = None›
        unfolding mstep_def mstep_cached_def by simp
      moreover have ‹starget gt sts stk v (DReduce pr) = None›
        using False c_len unfolding starget_def by simp
      ultimately show ?thesis unfolding DReduce by simp
    next
      case n: True
      have q_lt: ‹istk ! length (snd pr) < length sts› using c_prec[OF n] by simp
      have pr': ‹dnext gt sts (istk ! length (snd pr)) (Nt (fst pr)) < length sts ⟷
          cgoto (creach G (sts ! (istk ! length (snd pr)))) (Nt (fst pr)) ≠ []›
        using pnext_resolve(1)[OF sts q_lt] unfolding gt .
      show ?thesis unfolding DReduce dcands_mem[OF c_ne] scands_mem c_reduce(1)[OF n RS]
        using RS lic pr' c_reduce(2)[OF n RS] n c_len c_stk c_red_comps
        by (simp add: dlive_lcore starget_def Let_def)
    qed
  qed
qed

lemma lcore_Nil_ne: ‹lcore xs ≠ {} ⟹ xs ≠ []›
  unfolding lcore_def by auto

lemma c_shift_post:
  assumes v: ‹v = x # v'› and q: ‹q = dnext gt sts i (Tm (tok x))› and q_lt: ‹q < length sts›
  shows ‹ssim G Shn sts
     ((lgoto (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)]) # Xs, tcols v'),
      xclosure_auto G (lgoto (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)])) # cstk,
      dnext gt sts i (Tm (tok x)) # istk, v', ts)
     (q # stk, v', ts)›
proof -
  let ?F = ‹lgoto (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)])›
  let ?q = ‹dnext gt sts i (Tm (tok x))›
  have ne: ‹cgoto (creach G (sts ! i)) (Tm (tok x)) ≠ []›
    using pnext_resolve(1)[OF sts c_i_lt, of ‹Tm (tok x)›] q q_lt unfolding gt by simp
  have Fl: ‹lcore ?F = set (sts ! q)›
    using c_shift(2)[OF v] pnext_resolve(2)[OF sts c_i_lt, of ‹Tm (tok x)›] q q_lt
    unfolding gt by simp
  have Fne: ‹?F ≠ []› using c_shift(2)[OF v] ne by (intro lcore_Nil_ne) simp
  have ok: ‹goto_ok (istart_ind G) (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)])›
    by (rule goto_ok_Tm[OF c_CL(3)]) simp
  have Fa: ‹anch_items (istart_ind G) ?F› using lgoto_anch[OF ok c_CL(2)] .
  have Fn: ‹anns_ok ?F› using lgoto_anns[OF c_CL(3)] .
  have didx: ‹didx_ok G sts (?F # Xs) (?q # istk)›
    using didx_ok_push[OF tabs c_didx, of 0 ‹Tm (tok x)› ‹FinRep [s_col (span x)]›]
      c_ne c_hdX c_istk0 by simp
  have hdi: ‹hd istk = i› using c_stk hd_stk by simp
  have reach: ‹imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn)
      ((?F # Xs, tcols v'), ?q # istk)›
  proof (rule imreach_step[OF c_reach, of DShift])
    show ‹imstep G (pgtab G (pr0_states G Shn)) (pr0_states G Shn) ((Xs, w), istk) DShift =
        Some ((?F # Xs, tcols v'), ?q # istk)›
      unfolding imstep_def prod.case c_shift(1)[OF v] option.case dact.case hdi gt sts
      by (simp add: c_w v tcols_def)
    show ‹dlive (fst ((?F # Xs, tcols v'), ?q # istk))›
      unfolding fst_conv dlive_lcore c_shift(2)[OF v] using ne by simp
  qed
  have prec: ‹∀k < length (?F # Xs). (?q # istk) ! k < length sts ∧
      set (sts ! ((?q # istk) ! k)) = lcore ((?F # Xs) ! k)›
  proof (intro allI impI)
    fix k assume k: ‹k < length (?F # Xs)›
    show ‹(?q # istk) ! k < length sts ∧ set (sts ! ((?q # istk) ! k)) = lcore ((?F # Xs) ! k)›
    proof (cases k)
      case 0 then show ?thesis using q_lt Fl q by simp
    next
      case (Suc k') then show ?thesis using c_prec[of k'] k by simp
    qed
  qed
  have fr: ‹∀X ∈ set (?F # Xs). anch_items (istart_ind G) X ∧ anns_ok X›
    unfolding list.set(2) ball_simps(7) using Fa Fn c_frames by blast
  have cs: ‹cstk_ok G (?F # Xs) (xclosure_auto G ?F # cstk)›
    using c_cstk by (simp add: cstk_ok_map)
  have ist: ‹q # stk = ?q # istk›
    using c_stk q by simp
  have sts': ‹didx_ok G (pr0_states G Shn) (?F # Xs) (?q # istk)›
    using didx unfolding sts .
  show ?thesis unfolding ssim_def prod.case
    by (intro conjI refl list.distinct(2) ist cs sts' prec fr reach)
qed

lemma c_reduce_post:
  assumes n: ‹length (snd pr) < length Xs›
    and RS: ‹irep_nonempty (red_set (xclosure_auto G (hd Xs)) pr)›
    and q: ‹q = dnext gt sts (istk ! length (snd pr)) (Nt (fst pr))› and q_lt: ‹q < length sts›
  shows ‹ssim G Shn sts
     ((lgoto (xclosure_auto G (Xs ! length (snd pr))) (Nt (fst pr))
         (red_set (xclosure_auto G (hd Xs)) pr) # drop (length (snd pr)) Xs, w),
      xclosure_auto G (lgoto (xclosure_auto G (Xs ! length (snd pr))) (Nt (fst pr))
         (red_set (xclosure_auto G (hd Xs)) pr)) # drop (length (snd pr)) cstk,
      dnext gt sts (istk ! length (snd pr)) (Nt (fst pr)) # drop (length (snd pr)) istk, v, ts)
     (q # drop (length (snd pr)) stk, v, ts)›
proof -
  let ?n = ‹length (snd pr)›
  let ?F = ‹lgoto (xclosure_auto G (Xs ! ?n)) (Nt (fst pr)) (red_set (xclosure_auto G (hd Xs)) pr)›
  let ?q = ‹dnext gt sts (istk ! ?n) (Nt (fst pr))›
  have sn: ‹istk ! ?n < length sts› using c_prec[OF n] by simp
  have ne: ‹cgoto (creach G (sts ! (istk ! ?n))) (Nt (fst pr)) ≠ []›
    using pnext_resolve(1)[OF sts sn, of ‹Nt (fst pr)›] q q_lt unfolding gt by simp
  have Fl: ‹lcore ?F = set (sts ! q)›
    using c_reduce(2)[OF n RS] pnext_resolve(2)[OF sts sn, of ‹Nt (fst pr)›] q q_lt
    unfolding gt by simp
  have Fne: ‹?F ≠ []› using c_reduce(2)[OF n RS] ne by (intro lcore_Nil_ne) simp
  have ok: ‹goto_ok (istart_ind G) (xclosure_auto G (Xs ! ?n)) (Nt (fst pr))
      (red_set (xclosure_auto G (hd Xs)) pr)›
    by (rule goto_ok_Nt[OF c_frame_cl(3)[OF n] RS red_set_anch[OF c_CL(2) RS]])
  have Fa: ‹anch_items (istart_ind G) ?F› using lgoto_anch[OF ok c_frame_cl(2)[OF n]] .
  have Fn: ‹anns_ok ?F› using lgoto_anns[OF c_frame_cl(3)[OF n]] .
  have didx: ‹didx_ok G sts (?F # drop ?n Xs) (?q # drop ?n istk)›
    using didx_ok_push[OF tabs c_didx n] .
  have reach: ‹imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn)
      ((?F # drop ?n Xs, w), ?q # drop ?n istk)›
  proof (rule imreach_step[OF c_reach, of ‹DReduce pr›])
    show ‹imstep G (pgtab G (pr0_states G Shn)) (pr0_states G Shn) ((Xs, w), istk) (DReduce pr) =
        Some ((?F # drop ?n Xs, w), ?q # drop ?n istk)›
      unfolding imstep_def prod.case c_reduce(1)[OF n RS] option.case dact.case gt sts ..
    show ‹dlive (fst ((?F # drop ?n Xs, w), ?q # drop ?n istk))›
      unfolding fst_conv dlive_lcore c_reduce(2)[OF n RS] using ne by simp
  qed
  have prec: ‹∀k < length (?F # drop ?n Xs). (?q # drop ?n istk) ! k < length sts ∧
      set (sts ! ((?q # drop ?n istk) ! k)) = lcore ((?F # drop ?n Xs) ! k)›
  proof (intro allI impI)
    fix k assume k: ‹k < length (?F # drop ?n Xs)›
    show ‹(?q # drop ?n istk) ! k < length sts ∧
      set (sts ! ((?q # drop ?n istk) ! k)) = lcore ((?F # drop ?n Xs) ! k)›
    proof (cases k)
      case 0 then show ?thesis using q_lt Fl q by simp
    next
      case (Suc k')
      have kk: ‹?n + k' < length Xs› using k Suc n by simp
      have e1: ‹drop ?n istk ! k' = istk ! (?n + k')›
        by (rule nth_drop) (use n c_ilen in ‹metis less_imp_le›)
      have e2: ‹drop ?n Xs ! k' = Xs ! (?n + k')›
        by (rule nth_drop) (rule less_imp_le[OF n])
      show ?thesis unfolding Suc nth_Cons_Suc e1 e2 by (rule c_prec[OF kk])
    qed
  qed
  have fr: ‹∀X ∈ set (drop ?n Xs). anch_items (istart_ind G) X ∧ anns_ok X›
  proof
    fix X assume ‹X ∈ set (drop ?n Xs)›
    then have ‹X ∈ set Xs› by (rule in_set_dropD)
    then show ‹anch_items (istart_ind G) X ∧ anns_ok X› by (rule c_frames)
  qed
  have fr': ‹∀X ∈ set (?F # drop ?n Xs). anch_items (istart_ind G) X ∧ anns_ok X›
    unfolding list.set(2) ball_simps(7) using Fa Fn fr by blast
  have cs: ‹cstk_ok G (?F # drop ?n Xs) (xclosure_auto G ?F # drop ?n cstk)›
    using c_cstk by (simp add: cstk_ok_map drop_map)
  have ist': ‹q # drop ?n stk = ?q # drop ?n istk›
    using c_stk q by simp
  have sts': ‹didx_ok G (pr0_states G Shn) (?F # drop ?n Xs) (?q # drop ?n istk)›
    using didx unfolding sts .
  show ?thesis unfolding ssim_def prod.case
    by (intro conjI refl list.distinct(2) ist' cs sts' prec fr' reach c_w)
qed

end

lemma ssim_step:
  assumes sim: ‹ssim G Shn sts st ss› and nf: ‹¬ gfinal G Shn (fst st)›
  shows ‹rel_option (ssim G Shn sts) (dstep G gt sts redtab st) (sstep gt sts redtab pc ss)›
proof -
  obtain Xs w cstk istk v tstk where st: ‹st = ((Xs, w), cstk, istk, v, tstk)›
    by (cases st) auto
  obtain stk v' tstk' where ss: ‹ss = (stk, v', tstk')› by (cases ss) auto
  have v': ‹v' = v› and t': ‹tstk' = tstk› using sim unfolding st ss ssim_def by auto
  have sim': ‹ssim G Shn sts ((Xs, w), cstk, istk, v, tstk) (stk, v, tstk)›
    using sim unfolding st ss v' t' .
  obtain i where hd: ‹hd stk = i› by blast
  have ne: ‹Xs ≠ []› using c_ne[OF sim' hd] .
  have stk_ne: ‹stk ≠ []› using c_len[OF sim' hd] ne by auto
  then obtain rest where stk_eq: ‹stk = i # rest› using hd by (cases stk) auto
  let ?cells = ‹red_buckets G Shn (length sts) ! i›
  let ?CL = ‹xclosure_auto G (hd Xs)›
  let ?D = ‹dcands G i ?cells ?CL (Xs, w)›
  let ?S = ‹scands (pcomps G sts ! i) i ?cells v›
  let ?f = ‹starget gt sts stk v›
  have dstep_eq: ‹dstep G gt sts redtab st = (case dpick G cstk (Xs, w) ?D of
        None ⇒ None
      | Some (act, gc') ⇒ Some (case act of
          DShift ⇒ (gc', xclosure_auto G (hd (fst gc')) # cstk,
              dnext gt sts i (Tm (tok (hd v))) # istk, tl v, Leaf (hd v) # tstk)
        | DReduce pr ⇒ (gc', xclosure_auto G (hd (fst gc')) # drop (length (snd pr)) cstk,
              dnext gt sts (istk ! length (snd pr)) (Nt (fst pr)) # drop (length (snd pr)) istk, v,
              Node (fst pr) (rev (take (length (snd pr)) tstk)) # drop (length (snd pr)) tstk)))›
    unfolding st dstep_def Let_def prod.case c_istk_case[OF sim' hd] c_cstk_case[OF sim' hd]
      c_cells[OF sim' hd] ..
  have sctl_eq: ‹sctl gt sts redtab pc (stk, v) = (case spick ?f ?S of
        None ⇒ None
      | Some (act, q) ⇒ Some (act, case act of
          DShift ⇒ (q # stk, tl v)
        | DReduce pr ⇒ (q # drop (length (snd pr)) stk, v)))›
    using c_cells[OF sim' hd] c_comps[OF sim' hd]
    by (simp only: sctl_def stk_eq list.case prod.case Let_def)
  have iff: ‹⋀a. (a ∈ set ?D ∧ (∃gc'. mstep G (Xs, w) a = Some gc' ∧ dlive gc')) ⟷
      (a ∈ set ?S ∧ ?f a ≠ None)›
    by (rule c_act_iff[OF sim' hd])
  have mc: ‹⋀a. mstep_cached G cstk (Xs, w) a = mstep G (Xs, w) a›
    by (simp add: mstep_def c_cstk[OF sim' hd])
  have hdi: ‹i = hd istk› using c_stk[OF sim' hd] hd by simp
  have didx': ‹didx_ok G (pr0_states G Shn) Xs istk› using c_didx[OF sim' hd] unfolding sts .
  have uniq: ‹a1 = a2›
    if ‹a1 ∈ set ?D› ‹a2 ∈ set ?D› ‹mstep G (Xs, w) a1 = Some gc1› ‹mstep G (Xs, w) a2 = Some gc2›
      ‹dlive gc1› ‹dlive gc2› for a1 a2 gc1 gc2
  proof (rule ccontr)
    assume ‹a1 ≠ a2›
    from det[unfolded mdet_def, rule_format, of ‹(Xs, w)› istk i ‹?cells› ?CL a1 a2 gc1 gc2]
    show False using c_reach[OF sim' hd] ne didx' hdi that ‹a1 ≠ a2› unfolding sts by simp
  qed
  show ?thesis
  proof (cases ‹dpick G cstk (Xs, w) ?D›)
    case None
    have ‹∀a ∈ set ?S. ?f a = None›
    proof (intro ballI)
      fix a assume a: ‹a ∈ set ?S›
      show ‹?f a = None›
      proof (rule ccontr)
        assume ‹?f a ≠ None›
        with a iff obtain gc' where ‹a ∈ set ?D› ‹mstep G (Xs, w) a = Some gc'› ‹dlive gc'› by blast
        with dpick_NoneD[OF None] mc show False by metis
      qed
    qed
    then have ‹spick ?f ?S = None› by (simp add: spick_None_iff)
    then show ?thesis unfolding dstep_eq ss sstep_def v' t' prod.case sctl_eq None by simp
  next
    case (Some r)
    obtain a gc' where r: ‹r = (a, gc')› by (cases r)
    from dpick_sound[OF Some[unfolded r]] mc have aD: ‹a ∈ set ?D›
      and ms: ‹mstep G (Xs, w) a = Some gc'› and lv: ‹dlive gc'› by auto
    from iff[of a] aD ms lv obtain q where fq: ‹?f a = Some q› by auto
    have aS: ‹a ∈ set ?S› using iff[of a] aD ms lv by blast
    obtain a' q' where sp: ‹spick ?f ?S = Some (a', q')›
      using spick_None_iff[of ?f ?S] aS fq by (cases ‹spick ?f ?S›) auto
    from spick_SomeD[OF sp] have a'S: ‹a' ∈ set ?S› and fq': ‹?f a' = Some q'› by auto
    from iff[of a'] a'S fq' obtain gc'' where ‹a' ∈ set ?D› ‹mstep G (Xs, w) a' = Some gc''›
      ‹dlive gc''› by auto
    from uniq[OF aD this(1) ms this(2) lv this(3)] have aa: ‹a' = a› by simp
    with fq fq' have qq: ‹q' = q› by simp
    have sp': ‹spick ?f ?S = Some (a, q)› using sp aa qq by simp
    show ?thesis
    proof (cases a)
      case DShift
      from fq obtain x v'' where v: ‹v = x # v''› by (cases v) (auto simp: DShift starget_def)
      have q: ‹q = dnext gt sts i (Tm (tok x))› and q_lt: ‹q < length sts›
        using fq unfolding DShift starget_def v hd by (auto simp: Let_def split: if_splits)
      have gc': ‹gc' = (lgoto ?CL (Tm (tok x)) (FinRep [s_col (span x)]) # Xs, tcols v'')›
        using ms c_shift(1)[OF sim' hd v] unfolding DShift by simp
      show ?thesis
        unfolding dstep_eq ss sstep_def v' t' prod.case sctl_eq sp' Some r DShift
        using c_shift_post[OF sim' hd v q q_lt, of ‹Leaf x # tstk›] gc' v
        by (simp add: stree_def)
    next
      case (DReduce pr)
      let ?n = ‹length (snd pr)›
      have RS: ‹irep_nonempty (red_set ?CL pr)› using aD unfolding DReduce dcands_mem[OF ne] by simp
      have n: ‹?n < length Xs› and q: ‹q = dnext gt sts (stk ! ?n) (Nt (fst pr))›
        and q_lt: ‹q < length sts›
        using fq c_len[OF sim' hd] unfolding DReduce starget_def by (auto simp: Let_def split: if_splits)
      have gc': ‹gc' = (lgoto (xclosure_auto G (Xs ! ?n)) (Nt (fst pr)) (red_set ?CL pr)
          # drop ?n Xs, w)›
        using ms c_reduce(1)[OF sim' hd n RS] unfolding DReduce by simp
      show ?thesis
        unfolding dstep_eq ss sstep_def v' t' prod.case sctl_eq sp' Some r DReduce
        using c_reduce_post[OF sim' hd n RS q[unfolded c_stk[OF sim' hd]] q_lt,
            of ‹Node (fst pr) (rev (take ?n tstk)) # drop ?n tstk›] gc'
        by (simp add: stree_def)
    qed
  qed
qed

lemma ssim_final':
  assumes ‹ssim G Shn sts st ss›
  shows ‹gfinal G Shn (fst st) ⟷ sfinal (pfins Shn sts) (sctrl ss)›
proof -
  obtain Xs w cstk istk v tstk where st: ‹st = ((Xs, w), cstk, istk, v, tstk)› by (cases st) auto
  obtain stk v' tstk' where ss: ‹ss = (stk, v', tstk')› by (cases ss) auto
  show ?thesis using ssim_final[OF assms[unfolded st ss]] unfolding st ss sctrl_def by simp
qed

lemma ssim_tstk:
  ‹ssim G Shn sts ((gc, cstk, istk, v, tstk)) (stk, v', tstk') ⟹ tstk' = tstk›
  unfolding ssim_def by (cases gc) auto

lemma ssim_drun:
  ‹ssim G Shn sts st ss ⟹
     drun G Shn gt sts redtab n st = srun gt sts redtab pc (pfins Shn sts) n ss›
proof (induction n arbitrary: st ss)
  case 0
  obtain gc cstk istk v tstk where st: ‹st = (gc, cstk, istk, v, tstk)› by (cases st) auto
  obtain stk v' tstk' where ss: ‹ss = (stk, v', tstk')› by (cases ss) auto
  have f: ‹gfinal G Shn gc ⟷ sfinal (pfins Shn sts) (stk, v')›
    using ssim_final'[OF "0"] unfolding st ss sctrl_def by simp
  have t: ‹tstk' = tstk› using ssim_tstk "0" unfolding st ss by blast
  show ?case using f t unfolding st ss by (auto simp: sresult_def split: list.splits)
next
  case (Suc n)
  obtain gc cstk istk v tstk where st: ‹st = (gc, cstk, istk, v, tstk)› by (cases st) auto
  obtain stk v' tstk' where ss: ‹ss = (stk, v', tstk')› by (cases ss) auto
  have f: ‹gfinal G Shn gc ⟷ sfinal (pfins Shn sts) (stk, v')›
    using ssim_final'[OF Suc.prems] unfolding st ss sctrl_def by simp
  show ?case
  proof (cases ‹gfinal G Shn gc›)
    case True
    have t: ‹tstk' = tstk› using ssim_tstk Suc.prems unfolding st ss by blast
    then show ?thesis using f True unfolding st ss by (auto simp: sresult_def split: list.splits)
  next
    case False
    have r: ‹rel_option (ssim G Shn sts) (dstep G gt sts redtab st) (sstep gt sts redtab pc ss)›
      by (rule ssim_step[OF Suc.prems]) (use False st in simp)
    show ?thesis
    proof (cases ‹dstep G gt sts redtab st›)
      case None
      with r have ‹sstep gt sts redtab pc ss = None› by (cases ‹sstep gt sts redtab pc ss›) auto
      then show ?thesis using None False f unfolding st ss by simp
    next
      case (Some st')
      with r obtain ss' where ss': ‹sstep gt sts redtab pc ss = Some ss'›
        and sim': ‹ssim G Shn sts st' ss'› by (cases ‹sstep gt sts redtab pc ss›) auto
      show ?thesis using Some ss' False f Suc.IH[OF sim'] unfolding st ss
        by (simp del: srun.simps) (simp add: ss'[unfolded ss])
    qed
  qed
qed

end

subsection ‹Runs›

lemma srun_imp_srunwf:
  ‹srun gt sts redtab pc pf n st = Some t ⟹ srunwf gt sts redtab pc pf st = Some t›
  by (induction n arbitrary: st) (auto simp: srunwf.simps split: prod.splits option.splits if_splits)

lemma srunwf_imp_srun_ex:
  assumes ‹srunwf gt sts redtab pc pf st = Some t›
  shows ‹∃n. srun gt sts redtab pc pf n st = Some t›
proof (rule srunwf.raw_induct[OF _ assms], goal_cases)
  case (1 f gt sts redtab pc pf st t)
  obtain stk v tstk where st: ‹st = (stk, v, tstk)› by (cases st)
  show ?case
  proof (cases ‹sfinal pf (stk, v)›)
    case True
    with "1"(2)[unfolded st] have ‹srun gt sts redtab pc pf 0 st = Some t›
      unfolding st by simp
    then show ?thesis by blast
  next
    case False
    with "1"(2)[unfolded st] obtain st1 where
        sp: ‹sstep gt sts redtab pc (stk, v, tstk) = Some st1›
      and rec: ‹f gt sts redtab pc pf st1 = Some t›
      by (auto simp: bind_eq_Some_conv)
    from "1"(1)[OF rec] obtain n where ‹srun gt sts redtab pc pf n st1 = Some t› ..
    with False sp have ‹srun gt sts redtab pc pf (Suc n) st = Some t›
      unfolding st by simp
    then show ?thesis by blast
  qed
qed

lemma drunwf_srunwf:
  assumes ‹⋀n. drun G Shn gt sts redtab n st = srun gt' sts' redtab' pc pf n ss›
  shows ‹drunwf G Shn gt sts redtab st = srunwf gt' sts' redtab' pc pf ss›
proof (cases ‹drunwf G Shn gt sts redtab st›)
  case None
  show ?thesis
  proof (cases ‹srunwf gt' sts' redtab' pc pf ss›)
    case (Some t)
    from srunwf_imp_srun_ex[OF Some] obtain n where ‹srun gt' sts' redtab' pc pf n ss = Some t› ..
    with assms[of n] have ‹drun G Shn gt sts redtab n st = Some t› by simp
    from drun_imp_drunwf[OF this] None show ?thesis by (metis option.distinct(1))
  qed (simp only: None)
next
  case (Some t)
  from drunwf_imp_drun_ex[OF Some] obtain n where ‹drun G Shn gt sts redtab n st = Some t› ..
  with assms[of n] have ‹srun gt' sts' redtab' pc pf n ss = Some t› by simp
  from srun_imp_srunwf[OF this] Some show ?thesis by (simp only:)
qed

theorem dparse_eq_sparse:
  assumes ‹sstatic G Shn›
  shows ‹dparse G Shn w = sparse G Shn w›
  unfolding dparse_def sparse_def Let_def
  by (rule drunwf_srunwf, rule ssim_drun[OF assms refl refl refl refl])
     (rule ssim_init[OF refl])

subsection ‹Repeated stacks: the code equation of const‹srunwf››

text ‹As for const‹drunwf›: a run that revisits a control state never
  ends, and const‹srun_hist› stops it. The control state is the stack and
  the input, and reduces keep the input, so the stacks seen since the last
  shift are recorded. Reduces of unit and empty productions do not shrink
  the stack, so a run can revisit one cite‹‹Sect.~2.5› in "jourdan2012-validating-lr1"›; Jourdan et al.
  bound the run by fuel instead.›

definition snext :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list list ⇒ ('n × ('n, 't) rhs) list list ⇒ bool list ⇒
    ('m, 'ch, 't) sctl_t ⇒ ('m, 'ch, 't) sctl_t ⇒ bool› where
  ‹snext gt sts redtab pc pf c d ⟷
     ¬ sfinal pf c ∧ (∃a. sctl gt sts redtab pc c = Some (a, d))›

lemma sctl_reduce_v:
  ‹sctl gt sts redtab pc (stk, v) = Some (DReduce pr, stk', v') ⟹ v' = v›
  unfolding sctl_def by (auto simp: Let_def split: list.splits option.splits prod.splits)

lemma srun_on_cycle_None:
  assumes ‹(snext gt sts redtab pc pf)++ c (sctrl st)›
    ‹(snext gt sts redtab pc pf)++ (sctrl st) c›
  shows ‹srun gt sts redtab pc pf n st = None›
  using assms
proof (induction n arbitrary: st)
  case (0 st)
  from converse_tranclpE[OF "0.prems"(2)] obtain e where ‹snext gt sts redtab pc pf (sctrl st) e›
    by blast
  then show ?case unfolding snext_def sctrl_def by (cases st) auto
next
  case (Suc n st)
  obtain stk v tstk where st: ‹st = (stk, v, tstk)› by (cases st)
  from converse_tranclpE[OF Suc.prems(2)] obtain e where
    e: ‹snext gt sts redtab pc pf (sctrl st) e› by blast
  then obtain a where nf: ‹¬ sfinal pf (stk, v)›
    and sc: ‹sctl gt sts redtab pc (stk, v) = Some (a, e)›
    unfolding snext_def st sctrl_def by auto
  obtain stk' v' where e': ‹e = (stk', v')› by (cases e)
  let ?st' = ‹(stk', v', stree a v tstk)›
  have step: ‹sstep gt sts redtab pc st = Some ?st'›
    unfolding sstep_def st using sc e' by simp
  have ce: ‹(snext gt sts redtab pc pf)++ c (sctrl ?st')›
    using tranclp.trancl_into_trancl[OF Suc.prems(1) e] e' by (simp add: sctrl_def)
  have ec: ‹(snext gt sts redtab pc pf)++ (sctrl ?st') c›
  proof (rule converse_tranclpE[OF Suc.prems(2)])
    assume ‹snext gt sts redtab pc pf (sctrl st) c›
    with e have ‹e = c› unfolding snext_def by auto
    then show ?thesis using Suc.prems e' by (auto simp: sctrl_def intro: tranclp_trans)
  next
    fix e'' assume ‹snext gt sts redtab pc pf (sctrl st) e''›
      ‹(snext gt sts redtab pc pf)++ e'' c›
    with e have ‹e'' = e› unfolding snext_def by auto
    then show ?thesis using ‹(snext gt sts redtab pc pf)++ e'' c› e'
      by (simp add: sctrl_def)
  qed
  have ‹srun gt sts redtab pc pf (Suc n) st = srun gt sts redtab pc pf n ?st'›
    using nf step unfolding st by simp
  also have ‹… = None› by (rule Suc.IH[OF ce ec])
  finally show ?case .
qed

lemma srunwf_on_cycle_None:
  assumes ‹(snext gt sts redtab pc pf)++ c (sctrl st)›
    ‹(snext gt sts redtab pc pf)++ (sctrl st) c›
  shows ‹srunwf gt sts redtab pc pf st = None›
  using srunwf_imp_srun_ex[of gt sts redtab pc pf st] srun_on_cycle_None[OF assms]
  by (cases ‹srunwf gt sts redtab pc pf st›) auto

definition shist_ok :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list list ⇒ ('n × ('n, 't) rhs) list list ⇒ bool list ⇒ nat list list ⇒
    ('m, 'ch, 'n, 't) sst ⇒ bool› where
  ‹shist_ok gt sts redtab pc pf seen st ⟷
     (∀k ∈ set seen. (snext gt sts redtab pc pf)++ (k, fst (snd st)) (sctrl st))›

lemma shist_ok_Nil [simp]: ‹shist_ok gt sts redtab pc pf [] st›
  unfolding shist_ok_def by simp

lemma srun_hist_imp_srunwf:
  assumes h: ‹srun_hist ctl fin seen st = Some t›
    and c: ‹ctl = sctl gt sts redtab pc› and f: ‹fin = sfinal pf›
  shows ‹srunwf gt sts redtab pc pf st = Some t›
proof -
  have ‹ctl = sctl gt sts redtab pc ⟶ fin = sfinal pf ⟶
      srunwf gt sts redtab pc pf st = Some t›
  proof (rule srun_hist.raw_induct[OF _ h], goal_cases)
    case (1 f ctl fin seen st t)
    obtain stk v tstk where st: ‹st = (stk, v, tstk)› by (cases st)
    show ?case
    proof (intro impI)
      assume c: ‹ctl = sctl gt sts redtab pc› and fi: ‹fin = sfinal pf›
      show ‹srunwf gt sts redtab pc pf st = Some t›
      proof (cases ‹sfinal pf (stk, v)›)
        case True
        with "1"(2) show ?thesis unfolding st c fi by (simp add: srunwf.simps)
      next
        case False
        from False "1"(2) obtain a stk' v' where
            sc: ‹sctl gt sts redtab pc (stk, v) = Some (a, stk', v')›
          and rec: ‹f ctl fin (if a = DShift then [] else stk # seen)
              (stk', v', stree a v tstk) = Some t›
          unfolding st c fi by (auto simp: bind_eq_Some_conv split: if_splits)
        from "1"(1)[OF rec] c fi
        have ‹srunwf gt sts redtab pc pf (stk', v', stree a v tstk) = Some t› by blast
        with False sc show ?thesis unfolding st by (subst srunwf.simps) (simp add: sstep_def)
      qed
    qed
  qed
  with c f show ?thesis by blast
qed

lemma srun_imp_srun_hist:
  assumes ‹srun gt sts redtab pc pf n st = Some t›
    and ‹shist_ok gt sts redtab pc pf seen st›
  shows ‹srun_hist (sctl gt sts redtab pc) (sfinal pf) seen st = Some t›
  using assms
proof (induction n arbitrary: st seen)
  case (0 st seen)
  obtain stk v tstk where st: ‹st = (stk, v, tstk)› by (cases st)
  show ?case using "0.prems"(1) unfolding st
    by (subst srun_hist.simps) (auto split: if_splits)
next
  case (Suc n st seen)
  obtain stk v tstk where st: ‹st = (stk, v, tstk)› by (cases st)
  show ?case
  proof (cases ‹sfinal pf (stk, v)›)
    case True
    with Suc.prems(1) show ?thesis unfolding st by (subst srun_hist.simps) simp
  next
    case False
    with Suc.prems(1) obtain st1 where sp: ‹sstep gt sts redtab pc st = Some st1›
      and rec: ‹srun gt sts redtab pc pf n st1 = Some t›
      unfolding st by (auto split: option.splits)
    from sp obtain a stk' v' where sc: ‹sctl gt sts redtab pc (stk, v) = Some (a, stk', v')›
      and st1: ‹st1 = (stk', v', stree a v tstk)›
      unfolding st sstep_def by (auto split: prod.splits)
    have r: ‹snext gt sts redtab pc pf (stk, v) (stk', v')›
      unfolding snext_def using False sc by blast
    have nk: ‹stk ∉ set seen›
    proof
      assume ‹stk ∈ set seen›
      with Suc.prems(2) have c: ‹(snext gt sts redtab pc pf)++ (stk, v) (sctrl st)›
        unfolding shist_ok_def st by simp
      then have ‹(snext gt sts redtab pc pf)++ (sctrl st) (sctrl st)›
        unfolding st sctrl_def by simp
      from srunwf_on_cycle_None[OF this this] srun_imp_srunwf[OF Suc.prems(1)] show False by simp
    qed
    have ok: ‹shist_ok gt sts redtab pc pf (if a = DShift then [] else stk # seen) st1›
    proof (cases ‹a = DShift›)
      case True then show ?thesis by simp
    next
      case nsh: False
      then obtain pr where a: ‹a = DReduce pr› by (cases a) auto
      have vv: ‹v' = v› using sctl_reduce_v sc[unfolded a] .
      show ?thesis unfolding shist_ok_def st1 sctrl_def
      proof (intro ballI)
        fix k assume ‹k ∈ set (if a = DShift then [] else stk # seen)›
        with nsh have ‹k = stk ∨ k ∈ set seen› by simp
        then show ‹(snext gt sts redtab pc pf)++ (k, fst (snd (stk', v', stree a v tstk)))
            (case (stk', v', stree a v tstk) of (stk, v, tstk) ⇒ (stk, v))›
        proof
          assume ‹k = stk›
          then show ?thesis using r vv by simp
        next
          assume ‹k ∈ set seen›
          with Suc.prems(2) have ‹(snext gt sts redtab pc pf)++ (k, v) (stk, v)›
            unfolding shist_ok_def st sctrl_def by simp
          then show ?thesis using r vv by (simp add: tranclp.trancl_into_trancl)
        qed
      qed
    qed
    from Suc.IH[OF rec ok] have ih: ‹srun_hist (sctl gt sts redtab pc) (sfinal pf)
        (if a = DShift then [] else stk # seen) st1 = Some t› .
    show ?thesis using False nk sc ih unfolding st st1 by (subst srun_hist.simps) simp
  qed
qed

theorem srunwf_code [code]:
  ‹srunwf gt sts redtab pc pf st =
     srun_hist (sctl gt sts redtab pc) (sfinal pf) [] st›
proof (cases ‹srun_hist (sctl gt sts redtab pc) (sfinal pf) [] st›)
  case None
  show ?thesis
  proof (cases ‹srunwf gt sts redtab pc pf st›)
    case (Some t)
    from srunwf_imp_srun_ex[OF Some] obtain n where ‹srun gt sts redtab pc pf n st = Some t› ..
    from srun_imp_srun_hist[OF this shist_ok_Nil] None show ?thesis by simp
  qed (simp only: None)
next
  case (Some t)
  from srun_hist_imp_srunwf[OF Some refl refl] Some show ?thesis by simp
qed

subsection ‹Table inlining›

text ‹The counterpart of text‹dparse_via_tables›: under the static
  conditions the parser runs the simple driver on precomputed tables.›

lemma dparse_via_simple_tables:
  assumes static: ‹sstatic G Shn›
    and st: ‹pr0_states G Shn = sts› and gt: ‹pgtab G sts = gtab›
    and rt: ‹red_buckets G Shn (length sts) = redtab›
    and pcs: ‹pcomps G sts = pc› and pfs: ‹pfins Shn sts = pf›
    and i0: ‹st_find sts (lr0_start G Shn) = i0›
  shows ‹dparse G Shn w = srunwf gtab sts redtab pc pf ([i0], w, [])›
  unfolding dparse_eq_sparse[OF static] sparse_def sinit_def Let_def
  by (simp add: st gt rt pcs pfs i0)

section ‹Indexed tables›

text ‹The step const‹sctl› looks up goto rows by symbol, compares productions
  in the reduce cells, and indexes lists. The indexed step below does the same
  lookups on tables computed from those of const‹sctl› at definition time:
  productions and nonterminals are numbered, goto rows are keyed by the
  terminal or by the number of the nonterminal (the usual split into an action
  and a goto table cite‹‹Sect.~2.4› in "jourdan2012-validating-lr1"›), the length of the state list
  is stored, and the tables are immutable arrays. It computes the same function
  (text‹isctl_eq›).›

lemma la_tindex_nth: ‹x ∈ set xs ⟹ la_tindex xs x < length xs ∧ xs ! la_tindex xs x = x›
  by (induction xs) auto

lemma la_tindex_inj:
  ‹x ∈ set xs ⟹ y ∈ set xs ⟹ la_tindex xs x = la_tindex xs y ⟷ x = y›
  by (metis la_tindex_nth)

definition tm_row :: ‹(('n, 't) sym × nat) list ⇒ ('t × nat) list› where
  ‹tm_row row = concat (map (λ(X, j). case X of Tm a ⇒ [(a, j)] | Nt _ ⇒ []) row)›

definition nt_row :: ‹'n list ⇒ (('n, 't) sym × nat) list ⇒ (nat × nat) list› where
  ‹nt_row nms row = concat (map (λ(X, j). case X of
      Nt B ⇒ if B ∈ set nms then [(la_tindex nms B, j)] else [] | Tm _ ⇒ []) row)›

lemma map_of_tm_row: ‹map_of (tm_row row) a = map_of row (Tm a)›
  unfolding tm_row_def by (induction row) (auto split: sym.splits)

lemma map_of_nt_row:
  ‹A ∈ set nms ⟹ map_of (nt_row nms row) (la_tindex nms A) = map_of row (Nt A)›
  unfolding nt_row_def by (induction row) (auto split: sym.splits simp: la_tindex_inj)

text ‹The reduce cells of a coarse state, by production number.›

definition cell_row :: ‹('n × ('n, 't) rhs) list ⇒ nat ⇒ ('n, 't) lacell list ⇒
    (nat × 't option) list› where
  ‹cell_row prs i cells = concat (map (λ(i', itm, t, τ).
     if i' = i ∧ snd itm = length (snd (fst itm)) ∧ fst itm ∈ set prs
     then [(la_tindex prs (fst itm), t)] else []) cells)›

text ‹The tables as lists, which evaluation computes, and as arrays.›

datatype ('n, 't) ltabs = LTabs nat ‹('t × nat) list list› ‹(nat × nat) list list›
  ‹(nat × 't option) list list› ‹nat list list› ‹('n × ('n, 't) rhs) list› ‹nat list› ‹nat list›
  ‹bool list›

datatype ('n, 't) itabs = ITabs
  (it_ns: nat)
  (it_gtT: ‹('t × nat) list iarray›) (it_gtN: ‹(nat × nat) list iarray›)
  (it_cells: ‹(nat × 't option) list iarray›) (it_pc: ‹nat list iarray›)
  (it_prs: ‹('n × ('n, 't) rhs) iarray›) (it_plen: ‹nat iarray›) (it_plhs: ‹nat iarray›)
  (it_pf: ‹bool iarray›)

fun itabs_of :: ‹('n, 't) ltabs ⇒ ('n, 't) itabs› where
  ‹itabs_of (LTabs ns gT gN cs pc prs pl ph pf) =
     ITabs ns (IArray gT) (IArray gN) (IArray cs) (IArray pc) (IArray prs) (IArray pl) (IArray ph)
       (IArray pf)›

definition mk_ltabs :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list list ⇒ ('n × ('n, 't) rhs) list list ⇒ bool list ⇒ ('n, 't) ltabs› where
  ‹mk_ltabs gt sts redtab pc pf = (let prs = remdups (concat pc); nms = remdups (map fst prs) in
     LTabs (length sts) (map tm_row gt) (map (nt_row nms) gt)
       (map (λi. cell_row prs i (redtab ! i)) [0..<length redtab])
       (map (map (la_tindex prs)) pc) prs
       (map (λpr. length (snd pr)) prs) (map (λpr. la_tindex nms (fst pr)) prs) pf)›

subsection ‹The indexed step›

definition inext :: ‹('k × nat) list iarray ⇒ nat ⇒ nat ⇒ 'k ⇒ nat› where
  ‹inext tab n i k = (if i < IArray.length tab
     then (case map_of (tab !! i) k of Some j ⇒ min j n | None ⇒ n) else n)›

datatype iact = IShift | IReduce nat

definition ilic :: ‹(nat × 't option) list ⇒ ('m, 'ch, 't) tword ⇒ nat ⇒ bool› where
  ‹ilic cells v j ⟷ list_ex (λ(j', t). j' = j ∧
     (case v of [] ⇒ t = None | x # _ ⇒ t = Some (tok x))) cells›

definition icands :: ‹nat list ⇒ (nat × 't option) list ⇒ ('m, 'ch, 't) tword ⇒ iact list› where
  ‹icands comps cells v = (let reds = map IReduce (filter (ilic cells v) comps)
     in (case v of [] ⇒ reds | _ ⇒ IShift # reds))›

definition itarget :: ‹('n, 't) itabs ⇒ nat list ⇒ ('m, 'ch, 't) tword ⇒ iact ⇒ nat option› where
  ‹itarget T stk v act = (case act of
      IShift ⇒ (case v of [] ⇒ None | x # _ ⇒
        let q = inext (it_gtT T) (it_ns T) (hd stk) (tok x) in
        if q < it_ns T then Some q else None)
    | IReduce j ⇒ (case drop (it_plen T !! j) stk of [] ⇒ None | i' # _ ⇒
        let q = inext (it_gtN T) (it_ns T) i' (it_plhs T !! j) in
        if q < it_ns T then Some q else None))›

definition isctl :: ‹('n, 't) itabs ⇒ ('m, 'ch, 't) sctl_t ⇒
    (('n, 't) dact × ('m, 'ch, 't) sctl_t) option› where
  ‹isctl T c = (case c of (stk, v) ⇒
     (case stk of [] ⇒ None | i # _ ⇒
       let cells = (if i < IArray.length (it_cells T) then it_cells T !! i else []);
           comps = (if i < IArray.length (it_pc T) then it_pc T !! i else [])
       in (case spick (itarget T stk v) (icands comps cells v) of
            None ⇒ None
          | Some (IShift, q) ⇒ Some (DShift, q # stk, tl v)
          | Some (IReduce j, q) ⇒
              Some (DReduce (it_prs T !! j), q # drop (it_plen T !! j) stk, v))))›

definition isfinal :: ‹('n, 't) itabs ⇒ ('m, 'ch, 't) sctl_t ⇒ bool› where
  ‹isfinal T c ⟷ (case c of (stk, v) ⇒ v = [] ∧
     (case stk of [] ⇒ False | i # _ ⇒ i < IArray.length (it_pf T) ∧ it_pf T !! i))›

subsection ‹Correctness›

lemma iarray_simps [simp]:
  ‹IArray.length (IArray xs) = length xs› ‹IArray xs !! i = xs ! i›
  by simp_all

lemma inext_dnext:
  assumes ‹⋀row. row ∈ set gt ⟹ map_of (f row) k = map_of row X›
  shows ‹inext (IArray (map f gt)) (length sts) i k = dnext gt sts i X›
  using assms[of ‹gt ! i›]
  by (auto simp: inext_def dnext_def la_next_def split: option.splits)

lemma ilic_cell_row:
  assumes ‹pr ∈ set prs›
  shows ‹ilic (cell_row prs i cells) v (la_tindex prs pr) ⟷ slic i cells v pr›
  unfolding ilic_def slic_def cell_row_def list_ex_iff using assms
  by (fastforce simp: la_tindex_inj split: if_splits)

lemma spick_map:
  ‹spick f (map g xs) = map_option (λ(a, b). (g a, b)) (spick (f ∘ g) xs)›
  by (induction xs) (auto split: option.splits)

lemma spick_cong:
  ‹(⋀x. x ∈ set xs ⟹ f x = g x) ⟹ spick f xs = spick g xs›
  by (induction xs) (auto split: option.splits)

lemma case_drop:
  ‹(case drop n xs of [] ⇒ a | y # _ ⇒ f y) = (if n < length xs then f (xs ! n) else a)›
proof (cases ‹n < length xs›)
  case True
  then have ‹drop n xs = xs ! n # drop (Suc n) xs› by (rule Cons_nth_drop_Suc[symmetric])
  then show ?thesis using True by simp
qed simp

lemma isfinal_eq: ‹isfinal (itabs_of (mk_ltabs gt sts redtab pc pf)) = sfinal pf›
  by (rule ext) (auto simp: isfinal_def sfinal_def mk_ltabs_def Let_def split: prod.split list.split)

lemma isctl_eq_at:
  ‹isctl (itabs_of (mk_ltabs gt sts redtab pc pf)) (stk, v) = sctl gt sts redtab pc (stk, v)›
proof -
  define c where ‹c = (stk, v)›
  define prs where ‹prs = remdups (concat pc)›
  define nms where ‹nms = remdups (map fst prs)›
  define T where ‹T = itabs_of (mk_ltabs gt sts redtab pc pf)›
  have T: ‹it_ns T = length sts›
    ‹it_gtT T = IArray (map tm_row gt)› ‹it_gtN T = IArray (map (nt_row nms) gt)›
    ‹it_cells T = IArray (map (λi. cell_row prs i (redtab ! i)) [0..<length redtab])›
    ‹it_pc T = IArray (map (map (la_tindex prs)) pc)› ‹it_prs T = IArray prs›
    ‹it_plen T = IArray (map (λpr. length (snd pr)) prs)›
    ‹it_plhs T = IArray (map (λpr. la_tindex nms (fst pr)) prs)›
    unfolding T_def mk_ltabs_def Let_def prs_def nms_def by simp_all
  have gt_tm: ‹⋀i a. inext (IArray (map tm_row gt)) (length sts) i a = dnext gt sts i (Tm a)›
    by (rule inext_dnext) (rule map_of_tm_row)
  have gt_nt: ‹⋀i A. A ∈ set nms ⟹
      inext (IArray (map (nt_row nms) gt)) (length sts) i (la_tindex nms A) = dnext gt sts i (Nt A)›
    by (rule inext_dnext) (rule map_of_nt_row)
  note c = c_def
  have ‹isctl T c = sctl gt sts redtab pc c›
  proof (cases stk)
    case Nil
    then show ?thesis unfolding c isctl_def sctl_def by simp
  next
    case (Cons i rest)
    let ?cells = ‹if i < length redtab then redtab ! i else []›
    define comps where ‹comps = (if i < length pc then pc ! i else [])›
    let ?cellsI = ‹if i < length redtab then cell_row prs i (redtab ! i) else []›
    define compsI where ‹compsI = map (la_tindex prs) comps›
    let ?I = ‹icands compsI ?cellsI v›
    have cellsI: ‹(if i < IArray.length (it_cells T) then it_cells T !! i else []) = ?cellsI›
      by (simp add: T)
    have compsI: ‹(if i < IArray.length (it_pc T) then it_pc T !! i else []) = compsI›
      by (simp add: T compsI_def comps_def)
    have comps_prs: ‹pr ∈ set prs› if ‹pr ∈ set comps› for pr
      using that unfolding prs_def comps_def by (auto split: if_splits)
    have comps_map: ‹map (λj. prs ! j) compsI = comps›
      unfolding compsI_def map_map comp_def
    proof (rule map_idI)
      fix x assume ‹x ∈ set comps›
      from la_tindex_nth[OF comps_prs[OF this]] show ‹prs ! la_tindex prs x = x› by blast
    qed
    have jI: ‹j < length prs ∧ prs ! j ∈ set comps› if ‹j ∈ set compsI› for j
    proof -
      from that obtain pr where pr: ‹pr ∈ set comps› and j: ‹j = la_tindex prs pr›
        unfolding compsI_def set_map by blast
      from la_tindex_nth[OF comps_prs[OF pr]] pr show ?thesis unfolding j by simp
    qed
    have lic: ‹ilic ?cellsI v j ⟷ slic i ?cells v (prs ! j)› if ‹j ∈ set compsI› for j
    proof -
      from that obtain pr where pr: ‹pr ∈ set comps› and j: ‹j = la_tindex prs pr›
        unfolding compsI_def set_map by blast
      have prs_j: ‹prs ! j = pr› using la_tindex_nth[OF comps_prs[OF pr]] unfolding j by blast
      show ?thesis
      proof (cases ‹i < length redtab›)
        case True
        then show ?thesis using ilic_cell_row[OF comps_prs[OF pr]] j prs_j by simp
      next
        case False
        then show ?thesis unfolding ilic_def slic_def by simp
      qed
    qed
    define to where ‹to = (λa. case a of IShift ⇒ DShift | IReduce j ⇒ DReduce (prs ! j))›
    have cands: ‹scands comps i ?cells v = map to ?I›
    proof -
      have ‹filter (slic i ?cells v) comps = map (λj. prs ! j) (filter (ilic ?cellsI v) compsI)›
        unfolding comps_map[symmetric] filter_map comp_def
        by (rule arg_cong[where f = ‹map _›], rule filter_cong) (simp_all add: lic comps_map)
      then show ?thesis unfolding scands_def icands_def Let_def to_def
        by (cases v) simp_all
    qed
    have tgt: ‹starget gt sts stk v (to a) = itarget T stk v a› if ‹a ∈ set ?I› for a
    proof (cases a)
      case IShift
      then show ?thesis unfolding to_def starget_def itarget_def
        by (cases v) (simp_all add: gt_tm T)
    next
      case (IReduce j)
      then have j: ‹j ∈ set compsI› using that unfolding icands_def Let_def
        by (cases v) auto
      from jI[OF j] have j_lt: ‹j < length prs› by blast
      have A: ‹fst (prs ! j) ∈ set nms› unfolding nms_def using j_lt by simp
      show ?thesis unfolding IReduce to_def starget_def itarget_def
        using j_lt gt_nt[OF A] by (simp add: T case_drop)
    qed
    have sp: ‹spick (starget gt sts stk v) (scands comps i ?cells v) =
        map_option (λ(a, b). (to a, b)) (spick (itarget T stk v) ?I)›
      unfolding cands spick_map by (simp add: comp_def spick_cong[OF tgt])
    have S: ‹sctl gt sts redtab pc c =
        (case spick (starget gt sts stk v) (scands comps i ?cells v) of
          None ⇒ None
        | Some (act, q) ⇒ Some (act, case act of
            DShift ⇒ (q # stk, tl v)
          | DReduce pr ⇒ (q # drop (length (snd pr)) stk, v)))›
      unfolding c sctl_def Cons comps_def by (simp only: prod.case list.case Let_def)
    have Iq: ‹isctl T c =
        (case spick (itarget T stk v) ?I of
          None ⇒ None
        | Some (IShift, q) ⇒ Some (DShift, q # stk, tl v)
        | Some (IReduce j, q) ⇒
            Some (DReduce (it_prs T !! j), q # drop (it_plen T !! j) stk, v))›
      unfolding c isctl_def Cons prod.case list.case Let_def cellsI compsI ..
    show ?thesis
    proof (cases ‹spick (itarget T stk v) ?I›)
      case None
      then show ?thesis unfolding Iq S sp by simp
    next
      case (Some r)
      obtain a q where r: ‹r = (a, q)› by (cases r)
      from spick_SomeD[OF Some[unfolded r]] have aI: ‹a ∈ set ?I› by blast
      show ?thesis
      proof (cases a)
        case IShift
        then show ?thesis unfolding Iq S sp Some r by (simp add: to_def)
      next
        case (IReduce j)
        then have j: ‹j ∈ set compsI› using aI unfolding icands_def Let_def
          by (cases v) auto
        from jI[OF j] have j_lt: ‹j < length prs› by blast
        show ?thesis unfolding Iq S sp Some r IReduce using j_lt by (simp add: to_def T)
      qed
    qed
  qed
  then show ?thesis unfolding c_def T_def .
qed

theorem isctl_eq:
  ‹isctl (itabs_of (mk_ltabs gt sts redtab pc pf)) = sctl gt sts redtab pc›
  by (rule ext) (simp only: split_paired_all isctl_eq_at)

subsection ‹Table inlining›

text ‹The code equation of a parser under the static conditions: the indexed
  step over tables computed at definition time.›

lemma dparse_via_index_tables:
  assumes static: ‹sstatic G Shn›
    and st: ‹pr0_states G Shn = sts› and gt: ‹pgtab G sts = gtab›
    and rt: ‹red_buckets G Shn (length sts) = redtab›
    and pcs: ‹pcomps G sts = pc› and pfs: ‹pfins Shn sts = pf›
    and i0: ‹st_find sts (lr0_start G Shn) = i0›
    and lt: ‹mk_ltabs gtab sts redtab pc pf = L›
    and it: ‹itabs_of L = T›
  shows ‹dparse G Shn w = srun_hist (isctl T) (isfinal T) [] ([i0], w, [])›
  unfolding dparse_via_simple_tables[OF static st gt rt pcs pfs i0] srunwf_code
    isctl_eq[of gtab sts redtab pc pf, symmetric] isfinal_eq[of gtab sts redtab pc pf, symmetric]
    lt it ..

text ‹Immutable arrays in OCaml, as theory‹HOL-Library.IArray› provides them for
  SML and Haskell.›

code_printing
  type_constructor iarray ⇀ (OCaml) "_ array"
| constant IArray ⇀ (OCaml) "Array.of'_list"
| constant IArray.tabulate ⇀ (OCaml) "(fun (n, f) -> Array.init (Z.to'_int n) (fun i -> f (Z.of'_int i)))"
| constant IArray.sub' ⇀ (OCaml) "(fun (a, i) -> Array.get a (Z.to'_int i))"
| constant IArray.length' ⇀ (OCaml) "(fun a -> Z.of'_int (Array.length a))"

code_reserved (OCaml) Array

text ‹Bounds checks compare as typ‹integer›: the code equation of
  const‹IArray.length› converts the length back to typ‹nat›, which
  with binary naturals (▩‹Code_Binary_Nat›) costs more
  than the rest of a step.›

lemma iarray_length_less_code [code_unfold]:
  ‹(i < IArray.length as) = (integer_of_nat i < IArray.length' as)›
  by (simp add: integer_of_nat_eq_of_nat)

end