Theory LR_Sparse

(* Author: Basil Fürer *)

theory LR_Sparse
  imports LR_Fast "HOL-Library.IArray"
begin

section ‹Sparse closures for the set-anchored driver›

text ‹A closure of const‹dclosure› has one slot per production, but on
  a grammar of 286 items only about nine have a non-empty anchor set.  No
  driver operation observes the empty ones: const‹live› and
  const‹gfinal› look at non-empty items only, const‹red_set› unions
  anchor sets, const‹lgoto› maps an empty item to an empty one, and a
  round's image of an empty set is empty.  The sparse driver keeps only the
  non-empty items, computes a closure's rounds per nonterminal instead of per
  production, and refers to productions and symbols by numbers.

  The one observation that could depend on empty items is the order of the
  reduce candidates (const‹dcands›: const‹remdups› keeps the last
  occurrence).  It does not, because the closures the driver builds are
  ∗‹coherent›: items with the same production and dot have the same anchor
  set (‹coh›), so a production that has a non-empty complete item has only
  non-empty ones.  Coherence needs the start production to be no production of
  the grammar, which const‹fresh_name› provides.  Items known to have the same
  indentation set can share one representation cite‹‹Sect.~5.8› in "adams2013"›; coherence is
  such a fact, used here only to drop empty items.›

subsection ‹Productions as records›

text ‹The productions of the grammar and the start production, in one list;
  the start production gets the last position.›

definition eprods :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n × ('n, 't) rhs) list› where
  ‹eprods G Shn = iprods G @ [(Shn, [(Nt (istart G), Eq)])]›

fun symid :: ‹'n list ⇒ ('n, 't) sym ⇒ (nat, 't) sym› where
  ‹symid ns (Nt B) = Nt (ntidx ns B)›
| ‹symid ns (Tm a) = Tm a›

text ‹A production's record: its number (the first position of the production),
  the number of its left-hand side (the first position of a production with that
  left-hand side), its right-hand side over numbered nonterminals, and the
  production itself, for the tree and the reduce cells.›

type_synonym ('n, 't) prec = ‹nat × nat × ((nat, 't) sym × irel) list × 'n × ('n, 't) rhs›

type_synonym ('n, 't) sitem = ‹('n, 't) prec × nat × indrep›

definition mkrec :: ‹('n × ('n, 't) rhs) list ⇒ 'n × ('n, 't) rhs ⇒ ('n, 't) prec› where
  ‹mkrec ps p = (ntidx ps p, ntidx (map fst ps) (fst p),
     map (λ(X, r). (symid (map fst ps) X, r)) (snd p), p)›

definition rpid :: ‹('n, 't) prec ⇒ nat› where ‹rpid r = fst r›
definition rlhs :: ‹('n, 't) prec ⇒ nat› where ‹rlhs r = fst (snd r)›
definition rrhs :: ‹('n, 't) prec ⇒ ((nat, 't) sym × irel) list› where ‹rrhs r = fst (snd (snd r))›
definition rprod :: ‹('n, 't) prec ⇒ 'n × ('n, 't) rhs› where ‹rprod r = snd (snd (snd r))›

lemma mkrec_sel [simp]:
  ‹rpid (mkrec ps p) = ntidx ps p›
  ‹rlhs (mkrec ps p) = ntidx (map fst ps) (fst p)›
  ‹rrhs (mkrec ps p) = map (λ(X, r). (symid (map fst ps) X, r)) (snd p)›
  ‹rprod (mkrec ps p) = p›
  by (simp_all add: mkrec_def rpid_def rlhs_def rrhs_def rprod_def)

fun sdec :: ‹('n, 't) sitem ⇒ ('n, 't) xitem› where
  ‹sdec (r, m, R) = (rprod r, m, R)›

text ‹Every record of a sparse item list is a table record.›

definition swf :: ‹('n × ('n, 't) rhs) list ⇒ ('n, 't) sitem list ⇒ bool› where
  ‹swf ps xs ⟷ (∀(r, m, R) ∈ set xs. r ∈ mkrec ps ` set ps)›

subsubsection ‹Numbering›

lemma ntidx_less: ‹ntidx xs x < length xs ⟷ x ∈ set xs›
  by (induction xs) auto

lemma ntidx_nth: ‹x ∈ set xs ⟹ xs ! ntidx xs x = x›
  by (induction xs) auto

lemma ntidx_notin: ‹x ∉ set xs ⟹ ntidx xs x = length xs›
  by (induction xs) auto

lemma ntidx_append_in: ‹x ∈ set xs ⟹ ntidx (xs @ ys) x = ntidx xs x›
  by (induction xs) auto

lemma ntidx_append_notin: ‹x ∉ set xs ⟹ ntidx (xs @ ys) x = length xs + ntidx ys x›
  by (induction xs) auto

lemma ntidx_nth_le: ‹k < length xs ⟹ ntidx xs (xs ! k) ≤ k›
proof (induction xs arbitrary: k)
  case (Cons a xs)
  then show ?case by (cases k) auto
qed simp

subsection ‹The tables›

text ‹Per grammar: the records by position, for each nonterminal number the
  positions of its productions, the number of productions, the goto table and the
  reduce cells over numbered symbols and productions, and the number of
  states.›

datatype ('n, 't) stab = STab
  (s_recs: ‹('n, 't) prec iarray›)
  (s_ntab: ‹nat list iarray›)
  (s_np: nat)
  (s_gt: ‹((nat, 't) sym × nat) list iarray›)
  (s_rt: ‹(nat × (nat × nat) × 't option × wrel) list iarray›)
  (s_ns: nat)
  (s_i0: nat)

definition lids :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat list› where
  ‹lids G Shn = map (λp. ntidx (map fst (eprods G Shn)) (fst p)) (iprods G)›

definition mk_stab :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒ ('n, 't) stab› where
  ‹mk_stab G Shn gt sts redtab = (let ps = eprods G Shn; ns = map fst ps;
       np = length (iprods G); ls = lids G Shn in
     STab (IArray (map (mkrec ps) ps))
       (IArray (map (λa. map fst (filter (λ(k, l). l = a) (zip [0..<np] ls))) [0..<np]))
       np
       (IArray (map (map (λ(X, j). (symid ns X, j))) gt))
       (IArray (map (map (λ(i', (pr, n), t, τ). (i', (ntidx ps pr, n), t, τ))) redtab))
       (length sts) (istart_ind G))›

definition ntl :: ‹('n, 't) stab ⇒ nat ⇒ nat list› where
  ‹ntl T a = (if a < IArray.length (s_ntab T) then s_ntab T !! a else [])›

subsection ‹Closure rounds per nonterminal›

text ‹An item's contribution to a round: the nonterminal after its dot, if the
  grammar has productions for it, with the image of its anchor set.›

definition sitem_nx :: ‹nat ⇒ ('n, 't) sitem ⇒ (nat × indrep) option› where
  ‹sitem_nx np = (λ(r, m, R). if m < length (rrhs r) then
     (case rrhs r ! m of (Nt b, q) ⇒ if b < np then Some (b, irep_img q R) else None | _ ⇒ None)
     else None)›

definition skn :: ‹('n, 't) stab ⇒ ('n, 't) sitem list ⇒ (nat × indrep) list› where
  ‹skn T K = filter (λ(_, I). I ≠ FinRep []) (List.map_filter (sitem_nx (s_np T)) K)›

definition sslot_nx :: ‹('n, 't) stab ⇒ nat ⇒ indrep ⇒ (nat × indrep) list› where
  ‹sslot_nx T a R = List.map_filter (λk. sitem_nx (s_np T) (s_recs T !! k, 0, R)) (ntl T a)›

text ‹The anchor sets of a round, per nonterminal number, as an association list
  with distinct keys and non-empty values.›

fun sins :: ‹nat × indrep ⇒ (nat × indrep) list ⇒ (nat × indrep) list› where
  ‹sins (b, I) [] = [(b, I)]›
| ‹sins (b, I) ((c, J) # N) = (if b = c then (c, irep_union I J) # N else (c, J) # sins (b, I) N)›

definition slk :: ‹(nat × indrep) list ⇒ nat ⇒ indrep› where
  ‹slk N a = (case map_of N a of Some R ⇒ R | None ⇒ FinRep [])›

definition sround :: ‹('n, 't) stab ⇒ (nat × indrep) list ⇒ (nat × indrep) list ⇒
    (nat × indrep) list› where
  ‹sround T kn N = fold sins (kn @ filter (λ(_, I). I ≠ FinRep [])
     (concat (map (λ(a, R). sslot_nx T a R) N))) []›

definition ssub :: ‹(nat × indrep) list ⇒ (nat × indrep) list ⇒ bool› where
  ‹ssub N' N ⟷ list_all (λ(a, R). irep_subset R (slk N a)) N'›

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

text ‹The closure: the kernel's non-empty items, then the non-empty slots in the
  order of the productions.›

definition sclosure :: ‹('n, 't) stab ⇒ ('n, 't) sitem list ⇒ ('n, 't) sitem list› where
  ‹sclosure T K = (let N = sfix T (skn T K) in
     filter (λ(_, _, R). irep_nonempty R) K @
     map (λk. (s_recs T !! k, 0, slk N (rlhs (s_recs T !! k))))
       (sort (concat (map (λ(a, _). ntl T a) N))))›

subsubsection ‹Grouping›

lemma sins_set:
  ‹irep_set (slk (sins (b, I) N) a) = irep_set (slk N a) ∪ (if a = b then irep_set I else {})›
proof (induction N)
  case (Cons x N)
  obtain c J where x: ‹x = (c, J)› by (cases x)
  show ?case
  proof (cases ‹b = c›)
    case True
    then show ?thesis by (cases ‹a = b›) (simp_all add: x slk_def Un_commute)
  next
    case False
    with Cons.IH show ?thesis by (cases ‹a = c›) (simp_all add: x slk_def)
  qed
qed (simp add: slk_def)

lemma sins_keys: ‹fst ` set (sins (b, I) N) = insert b (fst ` set N)›
  by (induction ‹(b, I)› N rule: sins.induct) auto

lemma sins_distinct: ‹distinct (map fst N) ⟹ distinct (map fst (sins (b, I) N))›
  by (induction ‹(b, I)› N rule: sins.induct) (auto simp: sins_keys)

lemma sins_nonempty:
  ‹irep_nonempty I ⟹ ∀(a, R) ∈ set N. irep_nonempty R ⟹
   ∀(a, R) ∈ set (sins (b, I) N). irep_nonempty R›
  by (induction ‹(b, I)› N rule: sins.induct) auto

definition kset :: ‹nat ⇒ (nat × indrep) list ⇒ nat set› where
  ‹kset a xs = ⋃ {irep_set I |I. (a, I) ∈ set xs}›

lemma kset_simps [simp]:
  ‹kset a [] = {}›
  ‹kset a ((b, I) # xs) = (if b = a then irep_set I else {}) ∪ kset a xs›
  by (auto simp: kset_def)

lemma kset_append [simp]: ‹kset a (xs @ ys) = kset a xs ∪ kset a ys›
  by (auto simp: kset_def)

lemma kset_concat: ‹kset a (concat xss) = ⋃ (kset a ` set xss)›
  by (auto simp: kset_def)

lemma kset_filter_ne: ‹kset a (filter (λ(_, I). I ≠ FinRep []) xs) = kset a xs›
proof (induction xs)
  case (Cons x xs)
  then show ?case by (cases x) simp
qed simp

lemma kset_concat_map: ‹kset a (concat (map (λ(b, R). f b R) N)) = (⋃(b, R) ∈ set N. kset a (f b R))›
  by (auto simp: kset_concat)

lemma fold_sins_set:
  ‹irep_set (slk (fold sins xs N) a) = irep_set (slk N a) ∪ kset a xs›proof (induction xs arbitrary: N)
  case (Cons x xs)
  then show ?case by (cases x) (auto simp: sins_set)
qed simp

lemma fold_sins_keys: ‹fst ` set (fold sins xs N) = fst ` set N ∪ fst ` set xs›
proof (induction xs arbitrary: N)
  case (Cons x xs)
  then show ?case by (cases x) (auto simp: sins_keys)
qed simp

lemma fold_sins_distinct: ‹distinct (map fst N) ⟹ distinct (map fst (fold sins xs N))›
  by (induction xs arbitrary: N) (auto simp: sins_distinct)

lemma fold_sins_nonempty:
  ‹∀(b, I) ∈ set xs. irep_nonempty I ⟹ ∀(a, R) ∈ set N. irep_nonempty R ⟹
   ∀(a, R) ∈ set (fold sins xs N). irep_nonempty R›
proof (induction xs arbitrary: N)
  case (Cons x xs)
  obtain b I where x: ‹x = (b, I)› by (cases x)
  have I: ‹irep_nonempty I› and xs: ‹∀(b, I) ∈ set xs. irep_nonempty I›
    using Cons.prems(1) x by (simp_all del: irep_nonempty_correct)
  have ‹∀(a, R) ∈ set (sins (b, I) N). irep_nonempty R›
    by (rule sins_nonempty[OF I Cons.prems(2)])
  from Cons.IH[OF xs this] show ?case by (simp add: x)
qed simp

lemma slk_in: ‹distinct (map fst N) ⟹ (a, R) ∈ set N ⟹ slk N a = R›
  by (simp add: slk_def)

lemma slk_Nil [simp]: ‹slk [] a = FinRep []›
  by (simp add: slk_def)

lemma slk_notin: ‹a ∉ fst ` set N ⟹ slk N a = FinRep []›
proof -
  assume ‹a ∉ fst ` set N›
  then have ‹map_of N a = None› by (simp add: map_of_eq_None_iff)
  then show ?thesis by (simp add: slk_def)
qed

subsubsection ‹What the tables hold›

lemma length_eprods [simp]: ‹length (eprods G Shn) = Suc (length (iprods G))›
  by (simp add: eprods_def)

lemma eprods_nth: ‹k < length (iprods G) ⟹ eprods G Shn ! k = iprods G ! k›
  by (simp add: eprods_def nth_append)

lemma lhs_id_less:
  ‹ntidx (map fst (eprods G Shn)) B < length (iprods G) ⟷ B ∈ fst ` set (iprods G)›
proof (cases ‹B ∈ fst ` set (iprods G)›)
  case True
  then have ‹B ∈ set (map fst (iprods G))› by simp
  then show ?thesis using True ntidx_less[of ‹map fst (iprods G)› B]
    by (simp add: eprods_def ntidx_append_in del: set_map)
next
  case False
  then have ‹B ∉ set (map fst (iprods G))› by simp
  then show ?thesis using False
    by (simp add: eprods_def ntidx_append_notin del: set_map)
qed

lemma length_lids [simp]: ‹length (lids G Shn) = length (iprods G)›
  by (simp add: lids_def)

lemma lids_nth:
  ‹k < length (iprods G) ⟹ lids G Shn ! k = ntidx (map fst (eprods G Shn)) (fst (iprods G ! k))›
  by (simp add: lids_def)

lemma lids_nth_le: ‹k < length (iprods G) ⟹ lids G Shn ! k ≤ k›
  using ntidx_nth_le[of k ‹map fst (eprods G Shn)›] by (simp add: lids_nth eprods_nth)

lemma set_lids:
  ‹b ∈ set (lids G Shn) ⟷ (∃B ∈ fst ` set (iprods G). b = ntidx (map fst (eprods G Shn)) B)›
  by (auto simp: lids_def)

lemma zip_upt_nth: ‹length ls = n ⟹ zip [0..<n] ls = map (λk. (k, ls ! k)) [0..<n]›
  by (rule nth_equalityI) simp_all

lemma mk_stab_sel [simp]:
  ‹s_np (mk_stab G Shn gt sts redtab) = length (iprods G)›
  ‹s_ns (mk_stab G Shn gt sts redtab) = length sts›
  ‹s_i0 (mk_stab G Shn gt sts redtab) = istart_ind G›
  ‹s_recs (mk_stab G Shn gt sts redtab) = IArray (map (mkrec (eprods G Shn)) (eprods G Shn))›
  ‹s_gt (mk_stab G Shn gt sts redtab) =
     IArray (map (map (λ(X, j). (symid (map fst (eprods G Shn)) X, j))) gt)›
  ‹s_rt (mk_stab G Shn gt sts redtab) =
     IArray (map (map (λ(i', (pr, n), t, τ). (i', (ntidx (eprods G Shn) pr, n), t, τ))) redtab)›
  by (simp_all add: mk_stab_def Let_def)

lemma ntl_mk_stab:
  ‹ntl (mk_stab G Shn gt sts redtab) a = filter (λk. lids G Shn ! k = a) [0..<length (iprods G)]›
proof (cases ‹a < length (iprods G)›)
  case True
  then show ?thesis
    by (simp add: ntl_def mk_stab_def Let_def zip_upt_nth filter_map o_def)
next
  case False
  have ‹filter (λk. lids G Shn ! k = a) [0..<length (iprods G)] = []›
    by (rule filter_False) (use False lids_nth_le[of _ G Shn] in fastforce)
  with False show ?thesis by (simp add: ntl_def mk_stab_def Let_def)
qed

lemma recs_mk_stab:
  ‹k < length (iprods G) ⟹
   s_recs (mk_stab G Shn gt sts redtab) !! k = mkrec (eprods G Shn) (iprods G ! k)›
  by (simp add: eprods_nth)

subsubsection ‹An item's contribution›

definition nx_set :: ‹nat ⇒ nat ⇒ ('n, 't) sitem ⇒ nat set› where
  ‹nx_set np a s = (case sitem_nx np s of Some (b, I) ⇒ if b = a then irep_set I else {} | None ⇒ {})›

lemma map_filter_nx_set:
  ‹kset a (List.map_filter (sitem_nx np) xs) = ⋃ (nx_set np a ` set xs)›
proof (induction xs)
  case (Cons x xs)
  then show ?case by (cases ‹sitem_nx np x›) (auto simp: nx_set_def)
qed simp

lemma ximg_nx_set:
  assumes p: ‹p ∈ set (eprods G Shn)› and A: ‹A ∈ fst ` set (iprods G)›
  shows ‹ximg (A, x) (sdec (mkrec (eprods G Shn) p, m, R)) =
    nx_set (length (iprods G)) (ntidx (map fst (eprods G Shn)) A) (mkrec (eprods G Shn) p, m, R)›
proof -
  let ?ns = ‹map fst (eprods G Shn)›
  have An: ‹A ∈ set ?ns› using A by (force simp: eprods_def)
  have Al: ‹ntidx ?ns A < length (iprods G)› using lhs_id_less[of G Shn A] A by simp
  show ?thesis
  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)
      have ‹ntidx ?ns B = ntidx ?ns A ⟷ B = A› by (rule ntidx_eq_iff[OF An])
      with True Xq Nt Al show ?thesis
        by (cases p) (auto simp: nx_set_def sitem_nx_def)
    qed (use True Xq in ‹cases p, auto simp: nx_set_def sitem_nx_def›)
  qed (cases p, auto simp: nx_set_def sitem_nx_def)
qed

lemma sitem_nx_key:
  assumes ‹p ∈ set (eprods G Shn)›
    and ‹sitem_nx (length (iprods G)) (mkrec (eprods G Shn) p, m, R) = Some (b, I)›
  shows ‹b ∈ set (lids G Shn)›
proof -
  let ?ns = ‹map fst (eprods G Shn)›
  from assms(2) obtain X q where Xq: ‹rrhs (mkrec (eprods G Shn) p) ! m = (symid ?ns X, q)›
      and s: ‹symid ?ns X = Nt b› and bl: ‹b < length (iprods G)›
    by (auto simp: sitem_nx_def split: if_splits sym.splits prod.splits)
  then obtain B where ‹X = Nt B› by (cases X) auto
  with s bl lhs_id_less[of G Shn B] show ?thesis by (force simp: set_lids)
qed

subsection ‹The rounds agree›

definition ine :: ‹'p × nat × indrep ⇒ bool› where
  ‹ine x ⟷ irep_nonempty (snd (snd x))›

lemma ine_simp [simp]: ‹ine (p, m, R) ⟷ irep_nonempty R›
  by (simp add: ine_def)

lemma irep_nonempty_iff: ‹irep_nonempty I ⟷ I ≠ FinRep []›
  by (cases I) auto

lemma ximg_cong: ‹irep_set R = irep_set R' ⟹ ximg pr (p, m, R) = ximg pr (p, m, R')›
  by (cases p) simp

lemma ximg_emptyR: ‹irep_set R = {} ⟹ ximg pr (p, m, R) = {}›
  by (cases p) simp

lemma ximg_filter_ine: ‹⋃ (ximg pr ` set (filter ine xs)) = ⋃ (ximg pr ` set xs)›
proof (induction xs)
  case (Cons x xs)
  obtain p m R where x: ‹x = (p, m, R)› by (cases x)
  show ?case
  proof (cases ‹ine x›)
    case False
    then have ‹ximg pr x = {}› by (simp add: x ximg_emptyR)
    with False Cons.IH show ?thesis by simp
  qed (use Cons.IH in simp)
qed simp

lemma map_sdec_filter: ‹map sdec (filter ine xs) = filter ine (map sdec xs)›
  by (induction xs) (auto simp: ine_def)

text ‹A sparse kernel stands for a kernel when its records are table records and
  their non-empty items agree.›

definition skrel :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) xitem list ⇒ ('n, 't) sitem list ⇒ bool› where
  ‹skrel G Shn K Ks ⟷ swf (eprods G Shn) Ks ∧ xeq (filter ine K) (filter ine (map sdec Ks))›

lemma swf_nx_set:
  assumes ‹swf (eprods G Shn) Ks› and ‹A ∈ fst ` set (iprods G)›
  shows ‹⋃ (nx_set (length (iprods G)) (ntidx (map fst (eprods G Shn)) A) ` set Ks) =
         ⋃ (ximg (A, x) ` set (map sdec Ks))›
proof -
  have ‹nx_set (length (iprods G)) (ntidx (map fst (eprods G Shn)) A) s = ximg (A, x) (sdec s)›
    if ‹s ∈ set Ks› for s
  proof -
    obtain r m R where s: ‹s = (r, m, R)› by (cases s)
    with that assms(1) obtain p where ‹p ∈ set (eprods G Shn)› ‹r = mkrec (eprods G Shn) p›
      unfolding swf_def by fast
    with s ximg_nx_set[OF _ assms(2)] show ?thesis by metis
  qed
  then show ?thesis by simp
qed

lemma skn_kset:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and r: ‹skrel G Shn K Ks›
    and A: ‹A ∈ fst ` set (iprods G)›
  shows ‹kset (ntidx (map fst (eprods G Shn)) A) (skn T Ks) = ⋃ (ximg (A, x) ` set K)›
proof -
  have ‹kset (ntidx (map fst (eprods G Shn)) A) (skn T Ks) = ⋃ (ximg (A, x) ` set (map sdec Ks))›
    using r A unfolding skrel_def skn_def T kset_filter_ne
    by (simp only: map_filter_nx_set mk_stab_sel swf_nx_set)
  also have ‹… = ⋃ (ximg (A, x) ` set (filter ine (map sdec Ks)))›
    by (rule ximg_filter_ine[symmetric])
  also have ‹… = ⋃ (ximg (A, x) ` set (filter ine K))›
    using r unfolding skrel_def by (metis xeq_ximg)
  also have ‹… = ⋃ (ximg (A, x) ` set K)›
    by (rule ximg_filter_ine)
  finally show ?thesis .
qed

lemma map_filter_map: ‹List.map_filter f (map g xs) = List.map_filter (f ∘ g) xs›
  by (induction xs) (auto split: option.split)

lemma sslot_kset:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and A: ‹A ∈ fst ` set (iprods G)›
  shows ‹kset (ntidx (map fst (eprods G Shn)) A) (sslot_nx T a R) =
    ⋃ ((λq. ximg (A, x) (iprods G ! q, 0, R)) ` {q. q < length (iprods G) ∧ lids G Shn ! q = a})›
proof -
  have eq: ‹nx_set (length (iprods G)) (ntidx (map fst (eprods G Shn)) A) (s_recs T !! q, 0, R) =
        ximg (A, x) (iprods G ! q, 0, R)› if ‹q < length (iprods G)› for q
  proof -
    have ‹iprods G ! q ∈ set (eprods G Shn)› using that by (simp add: eprods_def)
    from ximg_nx_set[OF this A, of x 0 R] that show ?thesis by (simp add: T recs_mk_stab eprods_nth)
  qed
  have m: ‹sslot_nx T a R = List.map_filter (sitem_nx (s_np T)) (map (λk. (s_recs T !! k, 0, R)) (ntl T a))›
    by (simp add: sslot_nx_def map_filter_map comp_def)
  have s: ‹set (ntl T a) = {q. q < length (iprods G) ∧ lids G Shn ! q = a}›
    by (auto simp: T ntl_mk_stab)
  have np: ‹s_np T = length (iprods G)› by (simp add: T)
  show ?thesis
    unfolding m np map_filter_nx_set set_map image_image s
    by (rule SUP_cong[OF refl]) (metis (no_types, lifting) eq mem_Collect_eq)
qed

lemma in_map_filter: ‹y ∈ set (List.map_filter f xs) ⟷ (∃x ∈ set xs. f x = Some y)›
  by (induction xs) (auto split: option.split)

definition sinv :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (nat × indrep) list ⇒ bool› where
  ‹sinv G Shn N ⟷ distinct (map fst N) ∧ fst ` set N ⊆ set (lids G Shn) ∧
     (∀(a, R) ∈ set N. irep_nonempty R)›

definition siter :: ‹('n, 't) stab ⇒ (nat × indrep) list ⇒ nat ⇒ (nat × indrep) list› where
  ‹siter T kn t = (sround T kn ^^ t) []›

lemma siter_simps [simp]:
  ‹siter T kn 0 = []›
  ‹siter T kn (Suc t) = sround T kn (siter T kn t)›
  by (simp_all add: siter_def)

lemma skrel_swf: ‹skrel G Shn K Ks ⟹ swf (eprods G Shn) Ks›
  by (simp add: skrel_def)

lemma skn_keys:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and w: ‹swf (eprods G Shn) Ks›
  shows ‹fst ` set (skn T Ks) ⊆ set (lids G Shn)›
proof
  fix b assume ‹b ∈ fst ` set (skn T Ks)›
  then obtain I s where s: ‹s ∈ set Ks› ‹sitem_nx (length (iprods G)) s = Some (b, I)›
    by (auto simp: skn_def T in_map_filter)
  obtain r m R where s': ‹s = (r, m, R)› by (cases s)
  with s(1) w obtain p where ‹p ∈ set (eprods G Shn)› ‹r = mkrec (eprods G Shn) p›
    unfolding swf_def by fast
  with s s' show ‹b ∈ set (lids G Shn)› by (metis sitem_nx_key)
qed

lemma sslot_keys:
  assumes T: ‹T = mk_stab G Shn gt sts redtab›
  shows ‹fst ` set (sslot_nx T a R) ⊆ set (lids G Shn)›
proof
  fix b assume b: ‹b ∈ fst ` set (sslot_nx T a R)›
  have np: ‹s_np T = length (iprods G)› by (simp add: T)
  from b obtain I where ‹(b, I) ∈ set (sslot_nx T a R)› by force
  then obtain k where k: ‹k ∈ set (ntl T a)›
      and ks: ‹sitem_nx (length (iprods G)) (s_recs T !! k, 0, R) = Some (b, I)›
    unfolding sslot_nx_def np in_map_filter by blast
  from k have kl: ‹k < length (iprods G)› by (simp add: T ntl_mk_stab)
  then have p: ‹iprods G ! k ∈ set (eprods G Shn)› by (simp add: eprods_def)
  from ks have ‹sitem_nx (length (iprods G)) (mkrec (eprods G Shn) (iprods G ! k), 0, R) = Some (b, I)›
    by (simp only: T recs_mk_stab[OF kl])
  with p show ‹b ∈ set (lids G Shn)› by (rule sitem_nx_key)
qed

lemma sround_inv:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and w: ‹swf (eprods G Shn) Ks›
  shows ‹sinv G Shn (sround T (skn T Ks) N)›
proof -
  let ?xs = ‹skn T Ks @ filter (λ(_, I). I ≠ FinRep []) (concat (map (λ(a, R). sslot_nx T a R) N))›
  have k: ‹fst ` set ?xs ⊆ set (lids G Shn)›
    using skn_keys[OF T w] sslot_keys[OF T] by fastforce
  have ne: ‹∀(b, I) ∈ set ?xs. irep_nonempty I›
    by (auto simp: skn_def irep_nonempty_iff simp del: irep_nonempty_correct)
  show ?thesis
    unfolding sinv_def sround_def
    using fold_sins_distinct[of ‹[]› ?xs] fold_sins_keys[of ?xs ‹[]›] fold_sins_nonempty[OF ne, of ‹[]›] k
    by auto
qed

lemma siter_inv:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and w: ‹swf (eprods G Shn) Ks›
  shows ‹sinv G Shn (siter T (skn T Ks) t)›
proof (cases t)
  case 0
  then show ?thesis by (simp add: sinv_def)
next
  case (Suc n)
  then show ?thesis using sround_inv[OF T w] by simp
qed

lemma sinv_slk: ‹sinv G Shn N ⟹ (b, R) ∈ set N ⟹ slk N b = R›
  by (simp add: sinv_def slk_in)

lemma set_slots:
  assumes ‹length cls = length (iprods G)›
  shows ‹set (map (λ(pr, R). (pr, 0::nat, R)) (zip (iprods G) cls)) =
    (λq. (iprods G ! q, 0, cls ! q)) ` {0..<length (iprods G)}›
proof -
  have ‹zip (iprods G) cls = map (λq. (iprods G ! q, cls ! q)) [0..<length (iprods G)]›
    using assms by (intro nth_equalityI) simp_all
  then show ?thesis by (simp add: image_image)
qed

text ‹The lockstep: after ‹t› rounds, the dense slot of a production and the
  sparse entry of its left-hand side hold the same anchor set.›

lemma lockstep:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and r: ‹skrel G Shn K Ks›
    and q: ‹q < length (iprods G)›
  shows ‹irep_set (diter G K t ! q) = irep_set (slk (siter T (skn T Ks) t) (lids G Shn ! q))›
  using q
proof (induction t arbitrary: q)
  case 0
  then show ?case by (simp add: slk_def)
next
  case (Suc t)
  let ?N = ‹siter T (skn T Ks) t›
  let ?n = ‹length (iprods G)›
  have inv: ‹sinv G Shn ?N› by (rule siter_inv[OF T skrel_swf[OF r]])
  obtain A rhs where pr: ‹iprods G ! q = (A, rhs)› by fastforce
  have A: ‹A ∈ fst ` set (iprods G)› using Suc.prems pr by (metis fst_conv image_eqI nth_mem)
  have a: ‹lids G Shn ! q = ntidx (map fst (eprods G Shn)) A› using lids_nth[OF Suc.prems] pr by simp
  have IH: ‹ximg (A, rhs) (iprods G ! q', 0, diter G K t ! q') =
      ximg (A, rhs) (iprods G ! q', 0, slk ?N (lids G Shn ! q'))› if ‹q' < ?n› for q'
    by (rule ximg_cong[OF Suc.IH[OF that]])
  have slots: ‹(⋃q' ∈ {0..<?n}. ximg (A, rhs) (iprods G ! q', 0, diter G K t ! q')) =
      (⋃(b, R) ∈ set ?N. ⋃q' ∈ {q'. q' < ?n ∧ lids G Shn ! q' = b}. ximg (A, rhs) (iprods G ! q', 0, R))›
  proof (intro equalityI subsetI)
    fix j assume ‹j ∈ (⋃q' ∈ {0..<?n}. ximg (A, rhs) (iprods G ! q', 0, diter G K t ! q'))›
    then obtain q' where q': ‹q' < ?n› and j0: ‹j ∈ ximg (A, rhs) (iprods G ! q', 0, diter G K t ! q')›
      by auto
    from j0 have j: ‹j ∈ ximg (A, rhs) (iprods G ! q', 0, slk ?N (lids G Shn ! q'))›
      by (simp only: IH[OF q'])
    show ‹j ∈ (⋃(b, R) ∈ set ?N. ⋃q' ∈ {q'. q' < ?n ∧ lids G Shn ! q' = b}. ximg (A, rhs) (iprods G ! q', 0, R))›
    proof (cases ‹lids G Shn ! q' ∈ fst ` set ?N›)
      case True
      then obtain R where R: ‹(lids G Shn ! q', R) ∈ set ?N› by force
      with j sinv_slk[OF inv R] q' show ?thesis by fastforce
    next
      case False
      with j show ?thesis by (simp add: slk_notin ximg_emptyR)
    qed
  next
    fix j assume ‹j ∈ (⋃(b, R) ∈ set ?N. ⋃q' ∈ {q'. q' < ?n ∧ lids G Shn ! q' = b}. ximg (A, rhs) (iprods G ! q', 0, R))›
    then obtain b R q' where R: ‹(b, R) ∈ set ?N› and q': ‹q' < ?n› ‹lids G Shn ! q' = b›
      and j: ‹j ∈ ximg (A, rhs) (iprods G ! q', 0, R)› by blast
    have ‹j ∈ ximg (A, rhs) (iprods G ! q', 0, diter G K t ! q')›
      using j sinv_slk[OF inv R] q'(2) IH[OF q'(1)] by simp
    with q'(1) show ‹j ∈ (⋃q' ∈ {0..<?n}. ximg (A, rhs) (iprods G ! q', 0, diter G K t ! q'))›
      by auto
  qed
  have dense: ‹irep_set (diter G K (Suc t) ! q) =
      ⋃ (ximg (A, rhs) ` set K) ∪ (⋃q' ∈ {0..<?n}. ximg (A, rhs) (iprods G ! q', 0, diter G K t ! q'))›
  proof -
    have ‹irep_set (diter G K (Suc t) ! q) = ⋃ (ximg (A, rhs) ` set (xslots G K (diter G K t)))›
      using Suc.prems pr by (simp add: dround_def fold_xcontrib_set)
    then show ?thesis
      by (simp only: xslots_def set_append set_slots[OF diter_length] image_Un Union_Un_distrib image_image)
  qed
  have sparse: ‹irep_set (slk (siter T (skn T Ks) (Suc t)) (lids G Shn ! q)) =
      ⋃ (ximg (A, rhs) ` set K) ∪
      (⋃(b, R) ∈ set ?N. ⋃q' ∈ {q'. q' < ?n ∧ lids G Shn ! q' = b}. ximg (A, rhs) (iprods G ! q', 0, R))›
  proof -
    have ‹irep_set (slk (siter T (skn T Ks) (Suc t)) (lids G Shn ! q)) =
        kset (lids G Shn ! q) (skn T Ks) ∪ (⋃(b, R) ∈ set ?N. kset (lids G Shn ! q) (sslot_nx T b R))›
      by (simp add: sround_def fold_sins_set kset_filter_ne kset_concat_map)
    also have ‹… = ⋃ (ximg (A, rhs) ` set K) ∪
        (⋃(b, R) ∈ set ?N. ⋃q' ∈ {q'. q' < ?n ∧ lids G Shn ! q' = b}. ximg (A, rhs) (iprods G ! q', 0, R))›
      unfolding a skn_kset[OF T r A, where x = rhs] sslot_kset[OF T A, where x = rhs] ..
    finally show ?thesis .
  qed
  show ?case by (simp only: dense sparse slots)
qed

text ‹So the sparse loop stops when the dense one does.›

lemma ssub_lockstep:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and r: ‹skrel G Shn K Ks›
  shows ‹ssub (siter T (skn T Ks) (Suc t)) (siter T (skn T Ks) t) ⟷
    list_all2 irep_subset (diter G K (Suc t)) (diter G K t)›
proof -
  let ?N = ‹siter T (skn T Ks) t›
  let ?N' = ‹siter T (skn T Ks) (Suc t)›
  let ?n = ‹length (iprods G)›
  have inv': ‹sinv G Shn ?N'› by (rule siter_inv[OF T skrel_swf[OF r]])
  have ‹ssub ?N' ?N ⟷ (∀q < ?n. irep_set (slk ?N' (lids G Shn ! q)) ⊆ irep_set (slk ?N (lids G Shn ! q)))›
  proof
    assume s: ‹ssub ?N' ?N›
    show ‹∀q < ?n. irep_set (slk ?N' (lids G Shn ! q)) ⊆ irep_set (slk ?N (lids G Shn ! q))›
    proof (intro allI impI)
      fix q assume ‹q < ?n›
      show ‹irep_set (slk ?N' (lids G Shn ! q)) ⊆ irep_set (slk ?N (lids G Shn ! q))›
      proof (cases ‹lids G Shn ! q ∈ fst ` set ?N'›)
        case True
        then obtain R where R: ‹(lids G Shn ! q, R) ∈ set ?N'› by force
        with s sinv_slk[OF inv' R] show ?thesis by (auto simp: ssub_def list_all_iff)
      next
        case False
        then show ?thesis by (simp add: slk_notin)
      qed
    qed
  next
    assume a: ‹∀q < ?n. irep_set (slk ?N' (lids G Shn ! q)) ⊆ irep_set (slk ?N (lids G Shn ! q))›
    have ‹irep_subset R (slk ?N b)› if b: ‹(b, R) ∈ set ?N'› for b R
    proof -
      from b inv' have ‹b ∈ set (lids G Shn)› by (force simp: sinv_def)
      then obtain q where q: ‹q < ?n› and bq: ‹b = lids G Shn ! q› by (auto simp: in_set_conv_nth)
      from a q have ‹irep_set (slk ?N' (lids G Shn ! q)) ⊆ irep_set (slk ?N (lids G Shn ! q))› by blast
      with bq sinv_slk[OF inv' b] show ?thesis by simp
    qed
    then show ‹ssub ?N' ?N› by (auto simp: ssub_def list_all_iff)
  qed
  also have ‹… ⟷ list_all2 irep_subset (diter G K (Suc t)) (diter G K t)›
    unfolding list_all2_conv_all_nth diter_length
    using lockstep[OF T r, where t = t] lockstep[OF T r, where t = ‹Suc t›] by auto
  finally show ?thesis .
qed

lemma sfix_siter:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and r: ‹skrel G Shn K Ks›
  shows ‹sfix T (skn T Ks) = siter T (skn T Ks) (xfuel G K)›
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_def)
qed

subsection ‹The closures agree›

lemma set_ntl:
  ‹T = mk_stab G Shn gt sts redtab ⟹ set (ntl T a) = {k. k < length (iprods G) ∧ lids G Shn ! k = a}›
  by (auto simp: ntl_mk_stab)

lemma distinct_ntl: ‹T = mk_stab G Shn gt sts redtab ⟹ distinct (ntl T a)›
  by (simp add: ntl_mk_stab)

lemma ntl_concat:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and d: ‹distinct (map fst N)›
  shows ‹sort (concat (map (λ(a, _). ntl T a) N)) =
    filter (λk. lids G Shn ! k ∈ fst ` set N) [0..<length (iprods G)]›
proof (rule sorted_distinct_set_unique)
  have ‹distinct (concat (map (λ(a, _). ntl T a) N))› using d
  proof (induction N)
    case (Cons x N)
    obtain a R where x: ‹x = (a, R)› by (cases x)
    from Cons.prems x have ‹a ∉ fst ` set N› by simp
    then have ‹set (ntl T a) ∩ set (concat (map (λ(a, _). ntl T a) N)) = {}›
      by (force simp: set_ntl[OF T])
    with Cons x show ?case by (simp add: distinct_ntl[OF T])
  qed simp
  then show ‹distinct (sort (concat (map (λ(a, _). ntl T a) N)))› by simp
  show ‹set (sort (concat (map (λ(a, _). ntl T a) N))) =
      set (filter (λk. lids G Shn ! k ∈ fst ` set N) [0..<length (iprods G)])›
    by (force simp: set_ntl[OF T])
qed (simp_all add: sorted_wrt_filter)

lemma list_all2_map_same:
  ‹(⋀x. x ∈ set xs ⟹ P (f x) (g x)) ⟹ list_all2 P (map f xs) (map g xs)›
  by (induction xs) auto

lemma recs_sel:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and k: ‹k < length (iprods G)›
  shows ‹rprod (s_recs T !! k) = iprods G ! k› ‹rlhs (s_recs T !! k) = lids G Shn ! k›
  by (simp_all only: T recs_mk_stab[OF k] mkrec_sel lids_nth[OF k])

text ‹A sparse closure stands for the non-empty items of the dense closure.›

lemma sclosure_rel:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and r: ‹skrel G Shn K Ks›
  shows ‹xeq (filter ine (dclosure G K)) (map sdec (sclosure T Ks))›
proof -
  let ?n = ‹length (iprods G)›
  let ?cls = ‹diter G K (xfuel G K)›
  let ?N = ‹sfix T (skn T Ks)›
  let ?ks = ‹filter (λk. lids G Shn ! k ∈ fst ` set ?N) [0..<?n]›
  have N: ‹?N = siter T (skn T Ks) (xfuel G K)› by (rule sfix_siter[OF T r])
  have inv: ‹sinv G Shn ?N› unfolding N by (rule siter_inv[OF T skrel_swf[OF r]])
  have lk: ‹irep_set (?cls ! q) = irep_set (slk ?N (lids G Shn ! q))› if ‹q < ?n› for q
    unfolding N by (rule lockstep[OF T r that])
  have ne: ‹irep_set (slk ?N b) ≠ {} ⟷ b ∈ fst ` set ?N› for b
  proof (cases ‹b ∈ fst ` set ?N›)
    case True
    then obtain R where R: ‹(b, R) ∈ set ?N› by force
    with inv have ‹irep_nonempty R› by (force simp: sinv_def simp del: irep_nonempty_correct)
    with True sinv_slk[OF inv R] show ?thesis by simp
  next
    case False
    then show ?thesis by (simp add: slk_notin)
  qed
  have zip: ‹zip (iprods G) ?cls = map (λq. (iprods G ! q, ?cls ! q)) [0..<?n]›
    by (intro nth_equalityI) simp_all
  have dense: ‹filter ine (dclosure G K) =
      filter ine K @ map (λq. (iprods G ! q, 0, ?cls ! q)) ?ks›
  proof -
    have fk: ‹filter (λq. irep_set (?cls ! q) ≠ {}) [0..<?n] = ?ks›
      by (rule filter_cong[OF refl]) (simp add: lk ne)
    show ?thesis by (simp add: dclosure_def xslots_def zip filter_map o_def fk)
  qed
  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: ‹xeq (filter ine K) (map sdec (filter ine Ks))›
    using r by (simp add: skrel_def map_sdec_filter)
  have slots: ‹xeq (map (λq. (iprods G ! q, 0, ?cls ! q)) ?ks)
      (map (λk. (iprods G ! k, 0, slk ?N (lids G Shn ! k))) ?ks)›
    unfolding xrel_def by (rule list_all2_map_same) (simp add: lk)
  show ?thesis
    unfolding dense sparse using kern slots by (simp add: xrel_def list_all2_appendI)
qed

lemma sclosure_swf:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and w: ‹swf (eprods G Shn) Ks›
  shows ‹swf (eprods G Shn) (sclosure T Ks)›
proof -
  have ‹s_recs T !! k ∈ mkrec (eprods G Shn) ` set (eprods G Shn)› if ‹k < length (iprods G)› for k
    using that by (auto simp: T intro!: imageI nth_mem)
  with w show ?thesis
    by (auto simp: swf_def sclosure_def Let_def set_ntl[OF T] simp del: IArray.sub_def)
qed

subsection ‹Coherence: the candidate order survives sparsity›

text ‹A list of items is coherent when items with the same production and dot
  have the same anchor set. The closures the driver builds are coherent, so a
  production with a non-empty complete item has only non-empty complete items,
  and the last occurrence that const‹remdups› keeps in const‹dcands› is
  a non-empty one.›

definition coh :: ‹('n, 't) xitem list ⇒ bool› where
  ‹coh xs ⟷ (∀p m R R'. (p, m, R) ∈ set xs ⟶ (p, m, R') ∈ set xs ⟶ irep_set R = irep_set R')›

definition kinv :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ bool› where
  ‹kinv G K ⟷ coh K ∧ (∀p R. (p, 0, R) ∈ set K ⟶ p ∉ set (iprods G))›

lemma xiter_slot_eq:
  assumes ‹q < length (iprods G)› ‹q' < length (iprods G)› ‹iprods G ! q = iprods G ! q'›
  shows ‹irep_set (xiter G xs s ! q) = irep_set (xiter G xs s ! q')›
  using assms by (cases s) (simp_all only: xiter_Suc_set, simp)

lemma coh_xclosure:
  assumes k: ‹kinv G K›
  shows ‹coh (xclosure_auto G K)›
proof -
  let ?cls = ‹xiter G K (xfuel G K)›
  have c: ‹coh K› and k0: ‹⋀p R. (p, 0, R) ∈ set K ⟹ p ∉ set (iprods G)›
    using k by (auto simp: kinv_def)
  have S: ‹set (xclosure_auto G K) = set K ∪ (λq. (iprods G ! q, 0, ?cls ! q)) ` {0..<length (iprods G)}›
    by (simp only: xclosure_auto_def xclosure_def xslots_def set_append set_slots[OF xiter_length])
  show ?thesis
    unfolding coh_def S
  proof (intro allI impI)
    fix p m R R'
    assume a: ‹(p, m, R) ∈ set K ∪ (λq. (iprods G ! q, 0, ?cls ! q)) ` {0..<length (iprods G)}›
      and b: ‹(p, m, R') ∈ set K ∪ (λq. (iprods G ! q, 0, ?cls ! q)) ` {0..<length (iprods G)}›
    show ‹irep_set R = irep_set R'›
    proof (cases ‹(p, m, R) ∈ set K›)
      case aK: True
      show ?thesis
      proof (cases ‹(p, m, R') ∈ set K›)
        case True
        with aK c show ?thesis unfolding coh_def by blast
      next
        case False
        with b obtain q where ‹q < length (iprods G)› ‹p = iprods G ! q› ‹m = 0› by auto
        with aK k0 have False by (metis nth_mem)
        then show ?thesis ..
      qed
    next
      case False
      with a obtain q where q: ‹q < length (iprods G)› ‹p = iprods G ! q› ‹m = 0› ‹R = ?cls ! q›
        by auto
      show ?thesis
      proof (cases ‹(p, m, R') ∈ set K›)
        case True
        with q k0 have False by (metis nth_mem)
        then show ?thesis ..
      next
        case False
        with b obtain q' where q': ‹q' < length (iprods G)› ‹p = iprods G ! q'› ‹R' = ?cls ! q'›
          by auto
        from q q' show ?thesis by (metis xiter_slot_eq)
      qed
    qed
  qed
qed
lemma coh_lgoto:
  assumes c: ‹coh xs›
  shows ‹coh (lgoto xs X RA)›
  unfolding coh_def
proof (intro allI impI)
  fix p m R R'
  assume a: ‹(p, m, R) ∈ set (lgoto xs X RA)› and b: ‹(p, m, R') ∈ set (lgoto xs X RA)›
  from lgoto_dot_pos[OF a] obtain k where m: ‹m = Suc k› by (metis gr0_conv_Suc)
  obtain R0 where R0: ‹(p, k, R0) ∈ set xs› ‹R = irep_inter R0 (irep_pre (snd (snd p ! k)) RA)›
    using a unfolding m by (rule lgoto_kernel_step)
  obtain R0' where R0': ‹(p, k, R0') ∈ set xs› ‹R' = irep_inter R0' (irep_pre (snd (snd p ! k)) RA)›
    using b unfolding m by (rule lgoto_kernel_step)
  from R0(1) R0'(1) c have ‹irep_set R0 = irep_set R0'› unfolding coh_def by blast
  with R0(2) R0'(2) show ‹irep_set R = irep_set R'› by simp
qed

lemma kinv_lgoto: ‹coh xs ⟹ kinv G (lgoto xs X RA)›
  unfolding kinv_def using coh_lgoto lgoto_dot_pos by blast

lemma kinv_xinit: ‹fresh_name G Shn ⟹ kinv G (xinit G Shn)›
  by (force simp: kinv_def coh_def xinit_def fresh_name_def)

lemma filter_remdups_map:
  assumes ‹⋀x. x ∈ set xs ⟹ P (f x) ⟹ Q x›
  shows ‹filter P (remdups (map f xs)) = filter P (remdups (map f (filter Q xs)))›
  using assms
proof (induction xs)
  case (Cons x xs)
  then have IH: ‹filter P (remdups (map f xs)) = filter P (remdups (map f (filter Q xs)))› by simp
  have eq: ‹f x ∈ f ` set xs ⟷ f x ∈ f ` set (filter Q xs)› if ‹P (f x)›
    using that Cons.prems by force
  show ?case
    using IH eq Cons.prems[of x] by (cases ‹P (f x)›) auto
qed simp

lemma red_set_filter_ine: ‹irep_set (red_set (filter ine CL) pr) = irep_set (red_set CL pr)›
  by (auto simp: red_set_correct ine_def)

lemma dcands_coh:
  assumes c: ‹coh CL›
  shows ‹dcands G i cells CL gc = dcands G i cells (filter ine CL) gc›
proof -
  let ?cmp = ‹λ(pr, m, R). m = length (snd pr)›
  have eq: ‹(λpr. irep_nonempty (red_set (filter ine CL) pr) ∧ dlic i cells w pr (red_set (filter ine CL) pr)) =
        (λpr. irep_nonempty (red_set CL pr) ∧ dlic i cells w pr (red_set CL pr))› for w
    by (rule ext) (simp only: irep_nonempty_correct red_set_filter_ine dlic_cong[OF red_set_filter_ine])
  have ff: ‹filter ?cmp (filter ine CL) = filter ine (filter ?cmp CL)›
    by (simp add: conj_commute)
  have comps: ‹filter (λpr. irep_nonempty (red_set CL pr) ∧ dlic i cells w pr (red_set CL pr))
        (remdups (map fst (filter ?cmp CL))) =
      filter (λpr. irep_nonempty (red_set CL pr) ∧ dlic i cells w pr (red_set CL pr))
        (remdups (map fst (filter ine (filter ?cmp CL))))› for w
  proof (rule filter_remdups_map)
    fix x assume x: ‹x ∈ set (filter ?cmp CL)›
      and P: ‹irep_nonempty (red_set CL (fst x)) ∧ dlic i cells w (fst x) (red_set CL (fst x))›
    obtain p m R where xp: ‹x = (p, m, R)› by (cases x)
    obtain R' where R': ‹(p, length (snd p), R') ∈ set CL› ‹irep_nonempty R'›
      using P[unfolded xp fst_conv] red_set_nonempty_iff by blast
    from x xp have ‹(p, length (snd p), R) ∈ set CL› by auto
    with R' c have ‹irep_set R = irep_set R'› unfolding coh_def by blast
    with R'(2) show ‹ine x› by (simp add: xp)
  qed
  show ?thesis unfolding dcands_def Let_def eq ff comps ..
qed

subsection ‹The driver's operations on sparse items›

text ‹Each operation decodes to its dense counterpart: symbols are compared as
  numbers, productions by their number.›

definition slgoto :: ‹('n, 't) sitem list ⇒ (nat, 't) sym ⇒ indrep ⇒ ('n, 't) sitem list› where
  ‹slgoto xs X RA =
     map (λ(r, m, R). (r, Suc m, irep_inter R (irep_pre (snd (rrhs r ! m)) RA)))
       (filter (λ(r, m, R). m < length (rrhs r) ∧ fst (rrhs r ! m) = X) xs)›

definition sred :: ‹('n, 't) sitem list ⇒ nat ⇒ nat ⇒ indrep› where
  ‹sred xs k n = foldr (λ(r, m, R) acc. if rpid r = k ∧ m = n then irep_union R acc else acc)
     xs (FinRep [])›

definition sdlic :: ‹nat ⇒ (nat × (nat × nat) × 't option × wrel) list ⇒ ('t × nat) list ⇒
    nat ⇒ nat ⇒ indrep ⇒ bool› where
  ‹sdlic i cells w k n RS ⟷ list_ex (λ(i', itm, t, τ).
       i' = i ∧ itm = (k, n) ∧
       (case w of [] ⇒ t = None | (a, c) # _ ⇒ t = Some a ∧ irep_ex_wsat τ c RS)) cells›

definition slive :: ‹('n, 't) sitem list ⇒ bool› where
  ‹slive xs = list_ex (λ(r, m, R). irep_nonempty R) xs›

definition sgfinal :: ‹('n, 't) stab ⇒ ('n, 't) sitem list list × ('t × nat) list ⇒ bool› where
  ‹sgfinal T gc ⟷ (case gc of (Ys, v) ⇒ v = [] ∧ Ys ≠ [] ∧
      list_ex (λ(r, m, R). rlhs r = s_np T ∧ m = Suc 0 ∧ irep_mem (s_i0 T) R) (hd Ys))›

definition sdnext :: ‹('n, 't) stab ⇒ nat ⇒ (nat, 't) sym ⇒ nat› where
  ‹sdnext T i X = (if i < IArray.length (s_gt T)
     then min (case map_of (s_gt T !! i) X of Some j ⇒ j | None ⇒ s_ns T) (s_ns T)
     else s_ns T)›

definition scells :: ‹('n × ('n, 't) rhs) list ⇒ ('n, 't) lacell list ⇒
    (nat × (nat × nat) × 't option × wrel) list› where
  ‹scells ps cells = map (λ(i', (pr, n), t, τ). (i', (ntidx ps pr, n), t, τ)) cells›

text ‹A symbol is told apart by its number when no other symbol has it: the
  terminals, and the nonterminals with productions.›

definition sgood :: ‹'n list ⇒ ('n, 't) sym ⇒ bool› where
  ‹sgood ns X ⟷ (∀Y. symid ns Y = symid ns X ⟶ Y = X)›

lemma sgood_Tm [simp]: ‹sgood ns (Tm a)›
  unfolding sgood_def by (auto elim: symid.elims)

lemma sgood_Nt: ‹B ∈ set ns ⟹ sgood ns (Nt B)›
  unfolding sgood_def by (auto elim!: symid.elims simp: eq_commute[of ‹ntidx ns B›] ntidx_eq_iff)

lemma swf_ConsD:
  assumes ‹swf ps ((r, m, R) # xs)›
  obtains p where ‹r = mkrec ps p› ‹p ∈ set ps› ‹swf ps xs›
  using assms unfolding swf_def by auto

lemma slgoto_dec:
  assumes w: ‹swf ps xs› and g: ‹sgood (map fst ps) X›
  shows ‹map sdec (slgoto xs (symid (map fst ps) X) RA) = lgoto (map sdec xs) X RA›
  using w
proof (induction xs)
  case (Cons x xs)
  obtain r m R where x: ‹x = (r, m, R)› by (cases x)
  from Cons.prems obtain p where r: ‹r = mkrec ps p› and w': ‹swf ps xs›
    unfolding x by (rule swf_ConsD)
  have IH: ‹map sdec (slgoto xs (symid (map fst ps) X) RA) = lgoto (map sdec xs) X RA›
    by (rule Cons.IH[OF w'])
  show ?case
  proof (cases ‹m < length (snd p)›)
    case True
    obtain Y I where yi: ‹snd p ! m = (Y, I)› by (cases ‹snd p ! m›)
    have ‹symid (map fst ps) Y = symid (map fst ps) X ⟷ Y = X›
      using g unfolding sgood_def by auto
    with True IH show ?thesis
      by (simp add: x r slgoto_def lgoto_def yi)
  next
    case False
    with IH show ?thesis by (simp add: x r slgoto_def lgoto_def)
  qed
qed (simp add: slgoto_def lgoto_def)

lemma slgoto_swf: ‹swf ps xs ⟹ swf ps (slgoto xs X RA)›
  unfolding swf_def slgoto_def by auto

lemma sred_dec:
  assumes w: ‹swf ps xs› and p: ‹pr ∈ set ps›
  shows ‹sred xs (ntidx ps pr) (length (snd pr)) = red_set (map sdec xs) pr›
  using w
proof (induction xs)
  case (Cons x xs)
  obtain r m R where x: ‹x = (r, m, R)› by (cases x)
  from Cons.prems obtain q where r: ‹r = mkrec ps q› and w': ‹swf ps xs›
    unfolding x by (rule swf_ConsD)
  have ‹ntidx ps q = ntidx ps pr ⟷ q = pr› by (rule ntidx_eq_iff[OF p])
  with Cons.IH[OF w'] show ?case by (simp add: x r sred_def red_set_def)
qed (simp add: sred_def red_set_def)

lemma sdlic_dec:
  assumes p: ‹pr ∈ set ps›
  shows ‹sdlic i (scells ps cells) w (ntidx ps pr) (length (snd pr)) RS = dlic i cells w pr RS›
proof -
  have e: ‹ntidx ps q = ntidx ps pr ⟷ q = pr› for q by (rule ntidx_eq_iff[OF p])
  show ?thesis
    by (induction cells) (auto simp: sdlic_def dlic_def scells_def e)
qed

lemma live_filter_ine: ‹live (filter ine xs) = live xs›
  by (induction xs) (auto simp: live_def ine_def)

lemma slive_dec: ‹slive xs = live (map sdec xs)›
  by (induction xs) (auto simp: slive_def live_def)

lemma skrel_live: ‹skrel G Shn K Ks ⟹ live K = slive Ks›
  unfolding skrel_def slive_dec by (metis live_filter_ine live_xeq)

lemma lhs_id_start:
  assumes fr: ‹fresh_name G Shn› and p: ‹p ∈ set (eprods G Shn)›
  shows ‹ntidx (map fst (eprods G Shn)) (fst p) = length (iprods G) ⟷ fst p = Shn›
proof (cases ‹fst p = Shn›)
  case True
  have ‹Shn ∉ set (map fst (iprods G))› using fr by (auto simp: fresh_name_def)
  with True show ?thesis by (simp add: eprods_def ntidx_append_notin)
next
  case False
  with p have ‹fst p ∈ fst ` set (iprods G)› by (force simp: eprods_def)
  with False lhs_id_less[of G Shn ‹fst p›] show ?thesis by simp
qed

lemma map_of_map_key:
  ‹(∀Y. f Y = f X ⟶ Y = X) ⟹ map_of (map (λ(k, v). (f k, v)) l) (f X) = map_of l X›
  by (induction l) auto

lemma sdnext_dec:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and g: ‹sgood (map fst (eprods G Shn)) X›
  shows ‹sdnext T i (symid (map fst (eprods G Shn)) X) = dnext gt sts i X›
proof -
  have m: ‹map_of (map (λ(k, v). (symid (map fst (eprods G Shn)) k, v)) l)
      (symid (map fst (eprods G Shn)) X) = map_of l X› for l :: ‹(_ × nat) list›
    by (rule map_of_map_key) (use g in ‹simp add: sgood_def›)
  show ?thesis by (simp add: T sdnext_def dnext_def la_next_def m split: option.split)
qed

subsection ‹Sparse closures against dense ones›

lemma xeq_trans: ‹xeq xs ys ⟹ xeq ys zs ⟹ xeq xs zs›
  unfolding xrel_def by (rule list_all2_trans[rotated], assumption, assumption) (auto split: prod.splits)

lemma xeq_filter_ine: ‹xeq xs ys ⟹ xeq (filter ine xs) (filter ine ys)›
  unfolding xrel_def by (induction rule: list_all2_induct) (auto split: prod.split_asm)

lemma lgoto_filter_ine: ‹filter ine (lgoto (filter ine xs) X RA) = filter ine (lgoto xs X RA)›
proof (induction xs)
  case (Cons x xs)
  obtain p m R where x: ‹x = (p, m, R)› by (cases x)
  with Cons.IH show ?case by (auto simp: lgoto_def)
qed (simp add: lgoto_def)

text ‹A cached dense closure and its sparse counterpart.›

definition screl :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) xitem list ⇒ ('n, 't) sitem list ⇒ bool› where
  ‹screl G Shn CL CLs ⟷ coh CL ∧ swf (eprods G Shn) CLs ∧ xeq (filter ine CL) (map sdec CLs)›

lemma screl_Nil [simp]: ‹screl G Shn [] []›
  by (simp add: screl_def coh_def swf_def xrel_def)

lemma screl_lgoto:
  assumes c: ‹screl G Shn CL CLs› and g: ‹sgood (map fst (eprods G Shn)) X›
    and RA: ‹irep_set RA = irep_set RB›
  shows ‹skrel G Shn (lgoto CL X RA) (slgoto CLs (symid (map fst (eprods G Shn)) X) RB)›
    and ‹kinv G (lgoto CL X RA)›
proof -
  have w: ‹swf (eprods G Shn) CLs› and x: ‹xeq (filter ine CL) (map sdec CLs)› and h: ‹coh CL›
    using c unfolding screl_def by simp_all
  have ‹xeq (filter ine (lgoto (filter ine CL) X RA)) (filter ine (lgoto (map sdec CLs) X RB))›
    by (rule xeq_filter_ine, rule lgoto_xeq[OF x RA])
  then show ‹skrel G Shn (lgoto CL X RA) (slgoto CLs (symid (map fst (eprods G Shn)) X) RB)›
    unfolding skrel_def lgoto_filter_ine slgoto_dec[OF w g] using slgoto_swf[OF w] by simp
  show ‹kinv G (lgoto CL X RA)› by (rule kinv_lgoto[OF h])
qed

lemma screl_closure:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and r: ‹skrel G Shn K Ks› and k: ‹kinv G K›
  shows ‹screl G Shn (xclosure_auto G K) (sclosure T Ks)›
  unfolding screl_def
  using coh_xclosure[OF k] sclosure_swf[OF T skrel_swf[OF r]]
    xeq_trans[OF xeq_filter_ine[OF xclosure_auto_dclosure[OF xeq_refl]] sclosure_rel[OF T r]]
  by simp

lemma screl_red:
  assumes c: ‹screl G Shn CL CLs› and p: ‹pr ∈ set (eprods G Shn)›
  shows ‹irep_set (sred CLs (ntidx (eprods G Shn) pr) (length (snd pr))) = irep_set (red_set CL pr)›
proof -
  have w: ‹swf (eprods G Shn) CLs› and x: ‹xeq (filter ine CL) (map sdec CLs)›
    using c unfolding screl_def by simp_all
  show ?thesis
    unfolding sred_dec[OF w p] using red_set_xeq[OF x, of pr] red_set_filter_ine[of CL pr] by simp
qed

lemma recs_ntidx:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and p: ‹p ∈ set (eprods G Shn)›
  shows ‹s_recs T !! ntidx (eprods G Shn) p = mkrec (eprods G Shn) p›
proof -
  have ‹ntidx (eprods G Shn) p < length (eprods G Shn)› using p by (simp only: ntidx_less)
  with p show ?thesis by (simp add: T ntidx_nth)
qed

subsection ‹The sparse driver›

datatype ('n, 't) sact = SShift | SReduce ‹('n, 't) prec›

fun sdec_act :: ‹('n, 't) sact ⇒ ('n, 't) dact› where
  ‹sdec_act SShift = DShift›
| ‹sdec_act (SReduce r) = DReduce (rprod r)›

type_synonym ('n, 't) sgconfig = ‹('n, 't) sitem list list × ('t × nat) list›

definition sdcands :: ‹('n, 't) stab ⇒ nat ⇒ (nat × (nat × nat) × 't option × wrel) list ⇒
    ('n, 't) sitem list ⇒ ('n, 't) sgconfig ⇒ ('n, 't) sact list› where
  ‹sdcands T i cells CL gc = (case gc of (Xs, w) ⇒
     if Xs = [] then [] else
     let comps = remdups (map (λ(r, m, R). rpid r) (filter (λ(r, m, R). m = length (rrhs r)) CL));
         reds = map (λk. SReduce (s_recs T !! k)) (filter (λk. let n = length (rrhs (s_recs T !! k));
                    RS = sred CL k n in irep_nonempty RS ∧ sdlic i cells w k n RS) comps)
     in (case w of [] ⇒ reds | _ ⇒ SShift # reds))›

lemma remdups_map_inj: ‹inj_on f (set xs) ⟹ remdups (map f xs) = map f (remdups xs)›
  by (induction xs) (auto simp: inj_on_def)

lemma sdcands_dec:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and w: ‹swf (eprods G Shn) CLs›
    and e: ‹Ks = [] ⟷ Xs = []›
  shows ‹map sdec_act (sdcands T i (scells (eprods G Shn) cells) CLs (Ks, v)) =
         dcands G i cells (map sdec CLs) (Xs, v)›
proof -
  let ?ps = ‹eprods G Shn›
  let ?C = ‹map fst (filter (λ(pr, m, R). m = length (snd pr)) (map sdec CLs))›
  have C: ‹set ?C ⊆ set ?ps› using w by (auto simp: swf_def)
  have ‹map (λ(r, m, R). rpid r) (filter (λ(r, m, R). m = length (rrhs r)) CLs) = map (ntidx ?ps) ?C›
    using w
  proof (induction CLs)
    case (Cons x xs)
    obtain r m R where x: ‹x = (r, m, R)› by (cases x)
    from Cons.prems obtain p where ‹r = mkrec ?ps p› ‹swf ?ps xs› unfolding x by (rule swf_ConsD)
    with Cons.IH show ?case by (simp add: x)
  qed simp
  moreover have inj: ‹inj_on (ntidx ?ps) (set ?C)›
  proof (rule inj_onI)
    fix x y assume ‹x ∈ set ?C› ‹y ∈ set ?C› ‹ntidx ?ps x = ntidx ?ps y›
    with C ntidx_eq_iff[of y ?ps x] show ‹x = y› by blast
  qed
  ultimately have comps: ‹remdups (map (λ(r, m, R). rpid r) (filter (λ(r, m, R). m = length (rrhs r)) CLs)) =
      map (ntidx ?ps) (remdups ?C)›
    by (simp only: remdups_map_inj[OF inj])
  have P: ‹(irep_nonempty (sred CLs (ntidx ?ps p) (length (snd p))) ∧
        sdlic i (scells ?ps cells) u (ntidx ?ps p) (length (snd p)) (sred CLs (ntidx ?ps p) (length (snd p)))) ⟷
      (irep_nonempty (red_set (map sdec CLs) p) ∧ dlic i cells u p (red_set (map sdec CLs) p))›
    if ‹p ∈ set ?ps› for p u
    using that by (simp add: sred_dec[OF w] sdlic_dec del: irep_nonempty_correct)
  have red: ‹set L ⊆ set ?ps ⟹
      map (sdec_act ∘ (λk. SReduce (s_recs T !! k))) (filter (λk.
          irep_nonempty (sred CLs k (length (rrhs (s_recs T !! k)))) ∧
          sdlic i (scells ?ps cells) u k (length (rrhs (s_recs T !! k)))
            (sred CLs k (length (rrhs (s_recs T !! k))))) (map (ntidx ?ps) L)) =
      map DReduce (filter (λpr. irep_nonempty (red_set (map sdec CLs) pr) ∧
          dlic i cells u pr (red_set (map sdec CLs) pr)) L)› for L u
    by (induction L) (simp_all add: P recs_ntidx[OF T] del: IArray.sub_def irep_nonempty_correct)
  have sub: ‹set (remdups ?C) ⊆ set ?ps› using C by simp
  show ?thesis
    unfolding sdcands_def dcands_def Let_def comps
    by (simp add: e red[OF sub] split: list.split del: IArray.sub_def irep_nonempty_correct)
qed

definition sgood_act :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) sact ⇒ bool› where
  ‹sgood_act G Shn a ⟷ (case a of SShift ⇒ True
     | SReduce r ⇒ r ∈ mkrec (eprods G Shn) ` set (eprods G Shn))›

lemma sdcands_good:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and w: ‹swf (eprods G Shn) CL›
  shows ‹∀act ∈ set (sdcands T i cells CL gc). sgood_act G Shn act›
proof -
  have r: ‹sgood_act G Shn (SReduce (s_recs T !! rpid r))›
    if ‹(r, m, R) ∈ set CL› for r m R
  proof -
    from w that obtain p where ‹p ∈ set (eprods G Shn)› ‹r = mkrec (eprods G Shn) p›
      unfolding swf_def by blast
    then show ?thesis using recs_ntidx[OF T] by (simp add: sgood_act_def del: IArray.sub_def)
  qed
  obtain Xs w where gc: ‹gc = (Xs, w)› by (cases gc)
  let ?f = ‹λk. SReduce (s_recs T !! k)› and ?g = ‹λ(r :: ('n, 't) prec, m :: nat, R :: indrep). rpid r›
  have sub: ‹set (map ?f (filter P (remdups (map ?g (filter Q CL))))) ⊆ ?f ` ?g ` set CL› for P Q
    unfolding set_map
    by (intro image_mono order_trans[OF filter_is_subset])
      (simp only: set_remdups set_map, intro image_mono filter_is_subset)
  have S: ‹set (sdcands T i cells CL gc) ⊆ insert SShift (?f ` ?g ` set CL)›
  proof (cases ‹Xs = []›)
    case False
    show ?thesis
    proof (cases w)
      case Nil
      show ?thesis unfolding sdcands_def Let_def gc prod.case if_not_P[OF False] Nil list.case
        by (rule subset_insertI2[OF sub])
    next
      case (Cons a w')
      show ?thesis unfolding sdcands_def Let_def gc prod.case if_not_P[OF False] Cons list.case list.set
        by (rule insert_mono[OF sub])
    qed
  qed (simp add: sdcands_def gc)
  show ?thesis
  proof
    fix act assume ‹act ∈ set (sdcands T i cells CL gc)›
    with S obtain x where ‹act = SShift ∨ (x ∈ set CL ∧ act = ?f (?g x))› by blast
    then show ‹sgood_act G Shn act›
    proof
      assume ‹act = SShift›
      then show ?thesis by (simp add: sgood_act_def)
    next
      assume a: ‹x ∈ set CL ∧ act = ?f (?g x)›
      obtain r m R where x: ‹x = (r, m, R)› by (cases x)
      from a r[of r m R] show ?thesis by (simp add: x del: IArray.sub_def)
    qed
  qed
qed

definition smstep :: ‹('n, 't) sitem list list ⇒ ('n, 't) sgconfig ⇒ ('n, 't) sact ⇒
    ('n, 't) sgconfig option› where
  ‹smstep cstk gc act = (case gc of (Xs, w) ⇒ (case act of
      SShift ⇒ (case w of [] ⇒ None | (a, c) # w' ⇒
        (if Xs = [] then None else Some (slgoto (hd cstk) (Tm a) (FinRep [c]) # Xs, w')))
    | SReduce r ⇒ (let n = length (rrhs r) in
        if drop n Xs = [] then None
        else let R = sred (hd cstk) (rpid r) n in
          if irep_nonempty R then Some (slgoto (cstk ! n) (Nt (rlhs r)) R # drop n Xs, w)
          else None)))›

definition sdlive :: ‹('n, 't) sgconfig ⇒ bool› where
  ‹sdlive gc = (case gc of (Xs, w) ⇒ Xs ≠ [] ∧ slive (hd Xs))›

fun sdpick :: ‹('n, 't) sitem list list ⇒ ('n, 't) sgconfig ⇒ ('n, 't) sact list ⇒
    (('n, 't) sact × ('n, 't) sgconfig) option› where
  ‹sdpick cstk gc [] = None›
| ‹sdpick cstk gc (act # acts) =
     (case smstep cstk gc act of
        Some gc' ⇒ (if sdlive gc' then Some (act, gc') else sdpick cstk gc acts)
      | None ⇒ sdpick cstk gc acts)›

text ‹A dense configuration and its sparse counterpart: related kernels, the
  dense ones coherent, the same input.›

definition sgrel :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) gconfig ⇒ ('n, 't) sgconfig ⇒ bool› where
  ‹sgrel G Shn gc gs ⟷ list_all2 (skrel G Shn) (fst gc) (fst gs) ∧
     (∀K ∈ set (fst gc). kinv G K) ∧ snd gc = snd gs›

lemma smstep_rel:
  assumes c: ‹list_all2 (screl G Shn) cstk cstks› and l: ‹length cstk = length (fst gc)›
    and g: ‹sgrel G Shn gc gs› and a: ‹sgood_act G Shn act›
  shows ‹rel_option (sgrel G Shn) (mstep_cached G cstk gc (sdec_act act)) (smstep cstks gs act)›
proof -
  obtain Xs w Ks where gc: ‹gc = (Xs, w)› ‹gs = (Ks, w)› and x: ‹list_all2 (skrel G Shn) Xs Ks›
    and kv: ‹∀K ∈ set Xs. kinv G K›
    using g unfolding sgrel_def by (cases gc; cases gs) auto
  have len: ‹length Ks = length Xs› using x by (simp add: list_all2_lengthD)
  have lc: ‹length cstks = length cstk› using c by (simp add: list_all2_lengthD)
  have nth: ‹screl G Shn (cstk ! k) (cstks ! k)› if ‹k < length Xs› for k
    using c that l gc by (simp add: list_all2_nthD)
  have h: ‹screl G Shn (hd cstk) (hd cstks)› if ‹Xs ≠ []›
  proof -
    have ‹cstk ≠ []› ‹cstks ≠ []› using that l lc gc by auto
    with nth[of 0] that show ?thesis by (simp add: hd_conv_nth)
  qed
  show ?thesis
  proof (cases act)
    case SShift
    show ?thesis
    proof (cases w)
      case Nil
      then show ?thesis by (simp add: SShift gc mstep_cached_code smstep_def)
    next
      case (Cons ac w')
      obtain a cc where ac: ‹ac = (a, cc)› by (cases ac)
      show ?thesis
      proof (cases ‹Xs = []›)
        case True
        then show ?thesis using len by (simp add: SShift gc Cons ac mstep_cached_code smstep_def)
      next
        case False
        have ks: ‹Ks ≠ []› using False len by auto
        from screl_lgoto[OF h[OF False] sgood_Tm[of _ a], where RA = ‹FinRep [cc]› and RB = ‹FinRep [cc]›]
        have ‹skrel G Shn (lgoto (hd cstk) (Tm a) (FinRep [cc])) (slgoto (hd cstks) (Tm a) (FinRep [cc]))›
          ‹kinv G (lgoto (hd cstk) (Tm a) (FinRep [cc]))›
          by simp_all
        with False ks x kv show ?thesis
          by (simp add: SShift gc Cons ac mstep_cached_code smstep_def sgrel_def)
      qed
    qed
  next
    case (SReduce r)
    from a obtain p where r: ‹r = mkrec (eprods G Shn) p› and p: ‹p ∈ set (eprods G Shn)›
      unfolding SReduce sgood_act_def by auto
    let ?n = ‹length (snd p)›
    have rn: ‹length (rrhs r) = ?n› and rp: ‹rprod r = p› by (simp_all add: r)
    show ?thesis
    proof (cases ‹drop ?n Xs = []›)
      case True
      then have ‹drop ?n Ks = []› using len by simp
      with True show ?thesis by (simp add: SReduce gc mstep_cached_code smstep_def rn rp Let_def)
    next
      case False
      then have n: ‹?n < length Xs› and ne: ‹Xs ≠ []› by auto
      have rs: ‹irep_set (sred (hd cstks) (rpid r) ?n) = irep_set (red_set (hd cstk) p)›
        unfolding r mkrec_sel by (rule screl_red[OF h[OF ne] p])
      have pn: ‹fst p ∈ set (map fst (eprods G Shn))› using p by force
      have sy: ‹symid (map fst (eprods G Shn)) (Nt (fst p)) = Nt (rlhs r)› by (simp add: r)
      from screl_lgoto[OF nth[OF n] sgood_Nt[OF pn], of ‹red_set (hd cstk) p› ‹sred (hd cstks) (rpid r) ?n›] rs sy
      have k: ‹skrel G Shn (lgoto (cstk ! ?n) (Nt (fst p)) (red_set (hd cstk) p))
          (slgoto (cstks ! ?n) (Nt (rlhs r)) (sred (hd cstks) (rpid r) ?n))›
        ‹kinv G (lgoto (cstk ! ?n) (Nt (fst p)) (red_set (hd cstk) p))›
        by simp_all
      have ‹list_all2 (skrel G Shn) (drop ?n Xs) (drop ?n Ks)› using x by (rule list_all2_dropI)
      moreover have ‹∀K ∈ set (drop ?n Xs). kinv G K› using kv by (meson in_set_dropD)
      moreover have ‹drop ?n Ks ≠ []› using False len by simp
      ultimately show ?thesis using False k rs
        by (simp add: SReduce gc mstep_cached_code smstep_def rn rp Let_def sgrel_def)
    qed
  qed
qed

lemma sgrel_dlive: ‹sgrel G Shn gc gs ⟹ dlive gc = sdlive gs›
proof -
  assume g: ‹sgrel G Shn gc gs›
  obtain Xs w Ks where gc: ‹gc = (Xs, w)› ‹gs = (Ks, w)› and x: ‹list_all2 (skrel G Shn) Xs Ks›
    using g unfolding sgrel_def by (cases gc; cases gs) auto
  show ?thesis
  proof (cases Xs)
    case Nil
    with x show ?thesis by (simp add: gc dlive_def sdlive_def)
  next
    case (Cons K Xs')
    with x obtain K' Ks' where ‹Ks = K' # Ks'› ‹skrel G Shn K K'› by (auto simp: list_all2_Cons1)
    with Cons show ?thesis by (simp add: gc dlive_def sdlive_def skrel_live)
  qed
qed

lemma sdpick_rel:
  assumes c: ‹list_all2 (screl G Shn) cstk cstks› and l: ‹length cstk = length (fst gc)›
    and g: ‹sgrel G Shn gc gs›
  shows ‹∀act ∈ set acts. sgood_act G Shn act ⟹
    rel_option (λ(a, g) (a', g'). a = sdec_act a' ∧ sgood_act G Shn a' ∧ sgrel G Shn g g')
      (dpick G cstk gc (map sdec_act acts)) (sdpick cstks gs acts)›
proof (induction acts)
  case (Cons act acts)
  from Cons.prems have ga: ‹sgood_act G Shn act› and as: ‹∀act ∈ set acts. sgood_act G Shn act›
    by simp_all
  note IH = Cons.IH[OF as]
  have m: ‹rel_option (sgrel G Shn) (mstep_cached G cstk gc (sdec_act act)) (smstep cstks gs act)›
    by (rule smstep_rel[OF c l g ga])
  show ?case
  proof (cases ‹mstep_cached G cstk gc (sdec_act act)›)
    case None
    with m have ‹smstep cstks gs act = None› by (cases ‹smstep cstks gs act›) simp_all
    with None IH show ?thesis by simp
  next
    case (Some g1)
    with m obtain g1' where s: ‹smstep cstks gs act = Some g1'› and r: ‹sgrel G Shn g1 g1'›
      by (cases ‹smstep cstks gs act›) simp_all
    with Some IH ga sgrel_dlive[OF r] show ?thesis by simp
  qed
qed simp

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

definition sdstep_act :: ‹('n, 't) stab ⇒ ('m, 'ch, 'n, 't) sdst ⇒
    (('n, 't) sact × ('m, 'ch, 'n, 't) sdst) option› where
  ‹sdstep_act T st = (case st of (gc, cstk, istk, v, tstk) ⇒
     let i = (case istk of [] ⇒ s_ns T | j # _ ⇒ j);
         cells = (if i < IArray.length (s_rt T) then s_rt T !! i else []);
         CL = (case cstk of [] ⇒ [] | c # _ ⇒ c)
     in (case sdpick cstk gc (sdcands T i cells CL gc) of
        None ⇒ None
      | Some (act, gc') ⇒ Some (act, case act of
          SShift ⇒ (gc',
              sclosure T (hd (fst gc')) # cstk,
              sdnext T i (Tm (tok (hd v))) # istk,
              tl v,
              Leaf (hd v) # tstk)
        | SReduce r ⇒ (gc',
              sclosure T (hd (fst gc')) # drop (length (rrhs r)) cstk,
              sdnext T (istk ! length (rrhs r)) (Nt (rlhs r)) # drop (length (rrhs r)) istk,
              v,
              Node (fst (rprod r)) (rev (take (length (rrhs r)) tstk))
                # drop (length (rrhs r)) tstk))))›

definition sdstep :: ‹('n, 't) stab ⇒ ('m, 'ch, 'n, 't) sdst ⇒ ('m, 'ch, 'n, 't) sdst option› where
  ‹sdstep T st = map_option snd (sdstep_act T st)›

partial_function (option) sdrun :: ‹('n, 't) stab ⇒ ('m, 'ch, 'n, 't) sdst ⇒ ('m, 'ch, 'n, 't) ast option›
  where
  ‹sdrun T st =
     (case st of (gc, cstk, istk, v, tstk) ⇒
        if sgfinal T gc then (case tstk of t # _ ⇒ Some t | [] ⇒ None)
        else Option.bind (sdstep T st) (sdrun T))›

lemmas sdrun_simps [code] = sdrun.simps

definition sinit :: ‹('n, 't) stab ⇒ ('n, 't) sitem list› where
  ‹sinit T = [(s_recs T !! s_np T, 0, FinRep [s_i0 T])]›

subsection ‹The sparse driver runs the dense one›

definition sst_rel :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) sdst ⇒ bool› where
  ‹sst_rel G Shn st sst ⟷ sgrel G Shn (fst st) (fst sst) ∧
     list_all2 (screl G Shn) (fst (snd st)) (fst (snd sst)) ∧
     length (fst (snd st)) = length (fst (fst st)) ∧ snd (snd st) = snd (snd sst)›

lemma scells_sel:
  assumes T: ‹T = mk_stab G Shn gt sts redtab›
  shows ‹(if i < IArray.length (s_rt T) then s_rt T !! i else []) =
         scells (eprods G Shn) (if i < length redtab then redtab ! i else [])›
  by (simp add: T scells_def)

lemma sdstep_act_rel:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and r: ‹sst_rel G Shn st sst›
  shows ‹rel_option (λ(a, s) (a', s'). a = sdec_act a' ∧ sst_rel G Shn s s')
           (dstep_act G gt sts redtab st) (sdstep_act T sst)›
proof -
  let ?ps = ‹eprods G Shn›
  obtain gc cstk istk v tstk gs cstks where
    st: ‹st = (gc, cstk, istk, v, tstk)› ‹sst = (gs, cstks, istk, v, tstk)› and
    g: ‹sgrel G Shn gc gs› and c: ‹list_all2 (screl G Shn) cstk cstks› and
    l: ‹length cstk = length (fst gc)›
    using r unfolding sst_rel_def by (cases st; cases sst) auto
  obtain Xs w Ks where gc: ‹gc = (Xs, w)› ‹gs = (Ks, w)› and x: ‹list_all2 (skrel G Shn) Xs Ks›
    using g unfolding sgrel_def by (cases gc; cases gs) auto
  have e: ‹Ks = [] ⟷ Xs = []› using x by auto
  define i where ‹i = (case istk of [] ⇒ length sts | j # _ ⇒ j)›
  define cells where ‹cells = (if i < length redtab then redtab ! i else [])›
  define CL where ‹CL = (case cstk of [] ⇒ [] | c # _ ⇒ c)›
  define CLs where ‹CLs = (case cstks of [] ⇒ [] | c # _ ⇒ c)›
  have cl: ‹screl G Shn CL CLs› using c unfolding CL_def CLs_def by (cases cstk; cases cstks) auto
  have ns: ‹s_ns T = length sts› by (simp add: T)
  have i': ‹(case istk of [] ⇒ s_ns T | j # _ ⇒ j) = i› unfolding ns i_def ..
  have i'': ‹(case istk of [] ⇒ length sts | j # _ ⇒ j) = i› unfolding i_def ..
  have cells': ‹(if i < IArray.length (s_rt T) then s_rt T !! i else []) = scells ?ps cells›
    unfolding cells_def by (rule scells_sel[OF T])
  define acts where ‹acts = sdcands T i (scells ?ps cells) CLs gs›
  have ‹dcands G i cells CL gc = dcands G i cells (filter ine CL) gc›
    using cl unfolding screl_def by (simp add: dcands_coh)
  also have ‹… = dcands G i cells (map sdec CLs) gc›
    using cl unfolding screl_def by (blast intro: dcands_xeq)
  also have ‹… = map sdec_act acts›
    unfolding acts_def gc using sdcands_dec[OF T _ e] cl unfolding screl_def by simp
  finally have da: ‹dcands G i cells CL gc = map sdec_act acts› .
  have u: ‹dcands G (case istk of [] ⇒ length sts | j # _ ⇒ j)
      (if (case istk of [] ⇒ length sts | j # _ ⇒ j) < length redtab
       then redtab ! (case istk of [] ⇒ length sts | j # _ ⇒ j) else [])
      (case cstk of [] ⇒ [] | c # _ ⇒ c) gc = map sdec_act acts›
    using da unfolding i_def cells_def CL_def .
  have us: ‹sdcands T (case istk of [] ⇒ s_ns T | j # _ ⇒ j)
      (if (case istk of [] ⇒ s_ns T | j # _ ⇒ j) < IArray.length (s_rt T)
       then s_rt T !! (case istk of [] ⇒ s_ns T | j # _ ⇒ j) else [])
      (case cstks of [] ⇒ [] | c # _ ⇒ c) gs = acts›
    unfolding acts_def CLs_def by (simp only: i' cells')
  have ga: ‹∀act ∈ set acts. sgood_act G Shn act›
    unfolding acts_def by (rule sdcands_good[OF T]) (use cl in ‹simp add: screl_def›)
  have pk: ‹rel_option (λ(a, g) (a', g'). a = sdec_act a' ∧ sgood_act G Shn a' ∧ sgrel G Shn g g')
      (dpick G cstk gc (map sdec_act acts)) (sdpick cstks gs acts)›
    by (rule sdpick_rel[OF c l g ga])
  show ?thesis
  proof (cases ‹dpick G cstk gc (map sdec_act acts)›)
    case None
    with pk have ‹sdpick cstks gs acts = None› by (cases ‹sdpick cstks gs acts›) auto
    with None show ?thesis
      unfolding st dstep_act_def sdstep_act_def Let_def prod.case u us by simp
  next
    case (Some p1)
    then obtain act g1 where p1: ‹dpick G cstk gc (map sdec_act acts) = Some (act, g1)›
      by (cases p1) auto
    with pk obtain act' g1' where p1': ‹sdpick cstks gs acts = Some (act', g1')›
      and aa: ‹act = sdec_act act'› and ga': ‹sgood_act G Shn act'› and g1: ‹sgrel G Shn g1 g1'›
      by (cases ‹sdpick cstks gs acts›) auto
    from dpick_sound[OF p1] have ms: ‹mstep_cached G cstk gc act = Some g1› and lv: ‹dlive g1›
      by simp_all
    obtain Ys w1 Ks1 where g1s: ‹g1 = (Ys, w1)› ‹g1' = (Ks1, w1)›
      and y: ‹list_all2 (skrel G Shn) Ys Ks1› and yk: ‹∀K ∈ set Ys. kinv G K›
      using g1 unfolding sgrel_def by (cases g1; cases g1') auto
    from lv obtain Y Ys' where Ys: ‹Ys = Y # Ys'› by (cases Ys) (auto simp: dlive_def g1s)
    with y obtain K1 Ks1' where Ks1: ‹Ks1 = K1 # Ks1'› and yk1: ‹skrel G Shn Y K1›
      by (auto simp: list_all2_Cons1)
    have hr: ‹screl G Shn (xclosure_auto G (hd (fst g1))) (sclosure T (hd (fst g1')))›
      using screl_closure[OF T yk1] yk by (simp add: g1s Ys Ks1)
    show ?thesis
    proof (cases act')
      case SShift
      then have act: ‹act = DShift› using aa by simp
      from ms[unfolded act gc] obtain a cc w' where ‹Xs ≠ []›
        and g1e: ‹g1 = (lgoto (hd cstk) (Tm a) (FinRep [cc]) # Xs, w')›
        by (rule mstep_shift_shape)
      then have len1: ‹length (fst g1) = Suc (length cstk)› using l gc by simp
      have nx: ‹sdnext T j (Tm b) = dnext gt sts j (Tm b)› for j b
        using sdnext_dec[OF T sgood_Tm[of _ b], where i = j] by simp
      show ?thesis
        unfolding st dstep_act_def sdstep_act_def Let_def prod.case u us
        using p1 p1' act SShift hr c len1 g1
        by (simp add: sst_rel_def nx i' i'')
    next
      case (SReduce r)
      from ga' obtain p where r: ‹r = mkrec ?ps p› and p: ‹p ∈ set ?ps›
        unfolding SReduce sgood_act_def by auto
      have rn: ‹length (rrhs r) = length (snd p)› and rp: ‹rprod r = p› by (simp_all add: r)
      have act: ‹act = DReduce p› using aa SReduce rp by simp
      from ms[unfolded act gc] obtain n: ‹length (snd p) < length Xs›
        and ‹irep_nonempty (red_set (hd cstk) p)›
        and g1e: ‹g1 = (lgoto (cstk ! length (snd p)) (Nt (fst p)) (red_set (hd cstk) p)
                # drop (length (snd p)) Xs, w)›
        by (rule mstep_reduce_shape)
      then have len1: ‹length (fst g1) = Suc (length (drop (length (snd p)) cstk))› using l gc by simp
      have pn: ‹fst p ∈ set (map fst ?ps)› using p by force
      have nx: ‹sdnext T j (Nt (rlhs r)) = dnext gt sts j (Nt (fst p))› for j
        using sdnext_dec[OF T sgood_Nt[OF pn], of j] by (simp add: r)
      have cd: ‹list_all2 (screl G Shn) (drop (length (snd p)) cstk) (drop (length (snd p)) cstks)›
        using c by (rule list_all2_dropI)
      show ?thesis
        unfolding st dstep_act_def sdstep_act_def Let_def prod.case u us
        using p1 p1' act SReduce hr cd len1 g1
        by (simp add: sst_rel_def nx rn rp i' i'')
    qed
  qed
qed

lemma sdstep_rel:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and r: ‹sst_rel G Shn st sst›
  shows ‹rel_option (sst_rel G Shn) (dstep G gt sts redtab st) (sdstep T sst)›
  using sdstep_act_rel[OF T r] unfolding dstep_eq_dstep_act sdstep_def
  by (cases ‹dstep_act G gt sts redtab st›; cases ‹sdstep_act T sst›) auto

lemma list_ex_filter_ine: ‹(⋀x. P x ⟹ ine x) ⟹ list_ex P (filter ine xs) = list_ex P xs›
  by (induction xs) auto

lemma sgfinal_rel:
  fixes G :: ‹('n, 't) is_cfg›
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and fr: ‹fresh_name G Shn› and g: ‹sgrel G Shn gc gs›
  shows ‹gfinal G Shn gc = sgfinal T gs›
proof -
  let ?ps = ‹eprods G Shn›
  let ?P = ‹λ(pr :: 'n × ('n, 't) rhs, m :: nat, R). fst pr = Shn ∧ m = Suc 0 ∧ irep_mem (istart_ind G) R›
  let ?Q = ‹λ(r :: ('n, 't) prec, m :: nat, R). rlhs r = s_np T ∧ m = Suc 0 ∧ irep_mem (s_i0 T) R›
  obtain Xs w Ks where gc: ‹gc = (Xs, w)› ‹gs = (Ks, w)› and x: ‹list_all2 (skrel G Shn) Xs Ks›
    using g unfolding sgrel_def by (cases gc; cases gs) auto
  show ?thesis
  proof (cases Xs)
    case Nil
    with x show ?thesis by (simp add: gc gfinal_def sgfinal_def)
  next
    case (Cons K Xs')
    with x obtain K1 Ks' where Ks: ‹Ks = K1 # Ks'› and k: ‹skrel G Shn K K1›
      by (auto simp: list_all2_Cons1)
    from k have w: ‹swf ?ps K1› and xk: ‹xeq (filter ine K) (filter ine (map sdec K1))›
      unfolding skrel_def by simp_all
    have Pi: ‹?P x ⟹ ine x› for x by (cases x) auto
    have ‹list_ex ?P K = list_ex ?P (filter ine K)› by (simp add: list_ex_filter_ine Pi)
    also have ‹… = list_ex ?P (filter ine (map sdec K1))›
      using xk unfolding xrel_def by (induction rule: list_all2_induct) (auto split: prod.split_asm)
    also have ‹… = list_ex ?P (map sdec K1)› by (simp add: list_ex_filter_ine Pi)
    also have ‹… = list_ex ?Q K1›
      using w
    proof (induction K1)
      case (Cons y ys)
      obtain r m R where y: ‹y = (r, m, R)› by (cases y)
      from Cons.prems obtain q where r: ‹r = mkrec ?ps q› and q: ‹q ∈ set ?ps› and w': ‹swf ?ps ys›
        unfolding y swf_def by auto
      have ‹rlhs r = s_np T ⟷ fst q = Shn› using lhs_id_start[OF fr q] by (simp add: T r)
      with Cons.IH[OF w'] show ?case by (simp add: y r T)
    qed simp
    finally show ?thesis by (simp add: gc Cons Ks gfinal_def sgfinal_def)
  qed
qed

lemma sst_rel_gfinal:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and fr: ‹fresh_name G Shn›
    and r: ‹sst_rel G Shn st sst›
  obtains gc cstk istk v tstk gs cstks where
    ‹st = (gc, cstk, istk, v, tstk)› ‹sst = (gs, cstks, istk, v, tstk)›
    ‹gfinal G Shn gc = sgfinal T gs›
  using r sgfinal_rel[OF T fr] unfolding sst_rel_def by (cases st; cases sst) auto

lemma drun_nh_imp_s:
  assumes run: ‹drun_nh G Shn gt sts redtab st = Some t›
  shows ‹T = mk_stab G Shn gt sts redtab ⟶ fresh_name G Shn ⟶
    (∀sst. sst_rel G Shn st sst ⟶ sdrun T sst = Some t)›
proof (rule drun_nh.raw_induct[OF _ run], goal_cases)
  case (1 f G Shn gt sts redtab st t)
  show ?case
  proof (intro impI allI)
    fix sst assume T: ‹T = mk_stab G Shn gt sts redtab› and fr: ‹fresh_name G Shn›
      and r: ‹sst_rel G Shn st sst›
    obtain gc cstk istk v tstk gs cstks where
      st: ‹st = (gc, cstk, istk, v, tstk)› ‹sst = (gs, cstks, istk, v, tstk)› and
      gf: ‹gfinal G Shn gc = sgfinal T gs›
      by (rule sst_rel_gfinal[OF T fr r])
    show ‹sdrun T sst = Some t›
    proof (cases ‹gfinal G Shn gc›)
      case True
      with "1"(2) gf show ?thesis unfolding st by (subst sdrun.simps) simp
    next
      case False
      with "1"(2) obtain st1 where sp: ‹dstep G gt sts redtab st = Some st1›
        and rec: ‹f G Shn gt sts redtab st1 = Some t›
        unfolding st by (auto simp: bind_eq_Some_conv)
      from sdstep_rel[OF T r] sp obtain sst1 where
        sp': ‹sdstep T sst = Some sst1› and r1: ‹sst_rel G Shn st1 sst1›
        by (cases ‹sdstep T sst›) auto
      from "1"(1)[OF rec] T fr r1 have ‹sdrun T sst1 = Some t› by blast
      with False gf sp' show ?thesis unfolding st by (subst sdrun.simps) simp
    qed
  qed
qed

lemma sdrun_imp_nh:
  assumes run: ‹sdrun T sst = Some t›
  shows ‹T = mk_stab G Shn gt sts redtab ⟶ fresh_name G Shn ⟶
    (∀st. sst_rel G Shn st sst ⟶ drun_nh G Shn gt sts redtab st = Some t)›
proof (rule sdrun.raw_induct[OF _ run], goal_cases)
  case (1 f T sst t)
  show ?case
  proof (intro impI allI)
    fix st assume T: ‹T = mk_stab G Shn gt sts redtab› and fr: ‹fresh_name G Shn›
      and r: ‹sst_rel G Shn st sst›
    obtain gc cstk istk v tstk gs cstks where
      st: ‹st = (gc, cstk, istk, v, tstk)› ‹sst = (gs, cstks, istk, v, tstk)› and
      gf: ‹gfinal G Shn gc = sgfinal T gs›
      by (rule sst_rel_gfinal[OF T fr r])
    show ‹drun_nh G Shn gt sts redtab st = Some t›
    proof (cases ‹sgfinal T gs›)
      case True
      with "1"(2) gf show ?thesis unfolding st by (subst drun_nh.simps) simp
    next
      case False
      with "1"(2) obtain sst1 where sp': ‹sdstep T sst = Some sst1›
        and rec: ‹f T sst1 = Some t›
        unfolding st by (auto simp: bind_eq_Some_conv)
      from sdstep_rel[OF T r] sp' obtain st1 where
        sp: ‹dstep G gt sts redtab st = Some st1› and r1: ‹sst_rel G Shn st1 sst1›
        by (cases ‹dstep G gt sts redtab st›) auto
      from "1"(1)[OF rec] T fr r1 have ‹drun_nh G Shn gt sts redtab st1 = Some t› by blast
      with False gf sp show ?thesis unfolding st by (subst drun_nh.simps) simp
    qed
  qed
qed

lemma drun_nh_eq_s:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and fr: ‹fresh_name G Shn›
    and r: ‹sst_rel G Shn st sst›
  shows ‹drun_nh G Shn gt sts redtab st = sdrun T sst›
proof (cases ‹drun_nh G Shn gt sts redtab st›)
  case None
  show ?thesis
  proof (rule ccontr)
    assume ‹drun_nh G Shn gt sts redtab st ≠ sdrun T sst›
    with None obtain t where ‹sdrun T sst = Some t› by (cases ‹sdrun T sst›) auto
    from sdrun_imp_nh[OF this, rule_format, OF T fr r] None show False by simp
  qed
next
  case (Some t)
  from drun_nh_imp_s[OF this, rule_format, OF T fr r] Some show ?thesis by simp
qed

lemma sinit_dec:
  assumes T: ‹T = mk_stab G Shn gt sts redtab› and fr: ‹fresh_name G Shn›
  shows ‹skrel G Shn (xinit G Shn) (sinit T)›
proof -
  let ?p = ‹(Shn, [(Nt (istart G), Eq)])›
  have ‹s_recs T !! s_np T = mkrec (eprods G Shn) ?p›
    by (simp add: T eprods_def nth_append)
  moreover have ‹?p ∈ set (eprods G Shn)› by (simp add: eprods_def)
  ultimately show ?thesis
    by (simp add: skrel_def sinit_def xinit_def swf_def T del: IArray.sub_def)
qed

text ‹The parser over the sparse driver: const‹dparse› as a run of
  const‹sdrun› over the table bundle, the initial kernel and its closure,
  each a constant the generated code computes once.›

lemma dparse_via_tables_s:
  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   ki:  ‹sinit stb = kin›
    and   kc:  ‹sclosure stb kin = kcl›
  shows ‹dparse G Shn w = sdrun stb (([kin], tcols w), [kcl], [i0], w, [])›
proof -
  have T: ‹stb = mk_stab G Shn gtab sts redtab› using tb by simp
  have k: ‹skrel G Shn (xinit G Shn) kin› using sinit_dec[OF T fr] ki by simp
  have kv: ‹kinv G (xinit G Shn)› by (rule kinv_xinit[OF fr])
  have ‹screl G Shn (xclosure_auto G (xinit G Shn)) kcl›
    using screl_closure[OF T k kv] kc by simp
  with k kv have ‹sst_rel G Shn (([xinit G Shn], tcols w), [xclosure_auto G (xinit G Shn)], [i0], w, [])
      (([kin], tcols w), [kcl], [i0], w, [])›
    by (simp add: sst_rel_def sgrel_def)
  then show ?thesis
    unfolding dparse_via_tables_nh[OF st gt rt refl refl i0] by (rule drun_nh_eq_s[OF T fr])
qed

end