Theory LR_Fast

(* Author: Basil Fürer *)

theory LR_Fast
  imports LR_Driver
begin

section ‹A faster closure for the set-anchored driver›

text ‹Profiling a parser generated for a large grammar puts nearly all of a step's time
  in const‹xclosure_auto›, the closure of the frame a step pushes.  Its
  rounds (const‹xround›) fold every slot of the round into the
  accumulator of the previous round, so each round unions the previous
  representation again and the const‹FinRep› lists grow with duplicates.
  text‹dclosure› runs the same rounds from a fresh accumulator and
  stops when a round adds nothing.  Its items equal those of
  const‹xclosure_auto› up to the sets their anchor representations
  denote (text‹xeq›), and every driver operation only looks at those
  sets, so a driver that caches text‹dclosure› (text‹drun_nh_c›)
  returns what const‹drun_nh› returns.›

subsection ‹Item lists equal up to anchor sets›

definition xrel :: ‹(nat set ⇒ nat set ⇒ bool) ⇒ ('n, 't) xitem list ⇒ ('n, 't) xitem list ⇒ bool› where
  ‹xrel P xs ys ⟷ list_all2 (λ(p, m, R) (p', m', R'). p = p' ∧ m = m' ∧ P (irep_set R) (irep_set R')) xs ys›

abbreviation xeq :: ‹('n, 't) xitem list ⇒ ('n, 't) xitem list ⇒ bool› where
  ‹xeq ≡ xrel (=)›

lemma xrel_refl: ‹(⋀S. P S S) ⟹ xrel P xs xs›
  unfolding xrel_def by (induction xs) auto

lemma xeq_refl [simp]: ‹xeq xs xs›
  by (rule xrel_refl) simp

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

lemma xrel_mono: ‹xrel P xs ys ⟹ (⋀S T. P S T ⟹ Q S T) ⟹ xrel Q xs ys›
  unfolding xrel_def by (erule list_all2_mono) (auto split: prod.split_asm)

lemma ximg_mono: ‹irep_set R ⊆ irep_set R' ⟹ ximg pr (p, m, R) ⊆ ximg pr (p, m, R')›
  by (cases p) auto

lemma xrel_ximg:
  ‹xrel (⊆) xs ys ⟹ ⋃ (ximg pr ` set xs) ⊆ ⋃ (ximg pr ` set ys)›
  unfolding xrel_def
proof (induction rule: list_all2_induct)
  case (Cons x xs y ys)
  obtain p m R p' m' R' where ‹x = (p, m, R)› ‹y = (p', m', R')› by (metis prod.collapse)
  with Cons.hyps(1) ximg_mono[of R R' pr p m] have ‹ximg pr x ⊆ ximg pr y› by simp
  with Cons.IH show ?case by auto
qed simp

lemma xeq_ximg: ‹xeq xs ys ⟹ ⋃ (ximg pr ` set xs) = ⋃ (ximg pr ` set ys)›
  by (intro equalityI xrel_ximg) (auto elim: xrel_mono dest: xeq_sym)

lemma xslots_xrel:
  assumes ‹xrel P xs ys› and ‹list_all2 (λa b. P (irep_set a) (irep_set b)) cls cls'›
  shows ‹xrel P (xslots G xs cls) (xslots G ys cls')›
proof -
  have ‹list_all2 (λ(p, m, R) (p', m', R'). p = p' ∧ m = m' ∧ P (irep_set R) (irep_set R'))
      (map2 (λpr R. (pr, 0, R)) (iprods G) cls) (map2 (λpr R. (pr, 0, R)) (iprods G) cls')›
    using assms(2) by (auto simp: list_all2_conv_all_nth)
  with assms(1) show ?thesis unfolding xrel_def xslots_def by (rule list_all2_appendI)
qed

subsection ‹Rounds from a fresh accumulator›

definition dround :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ indrep list ⇒ indrep list› where
  ‹dround G xs cls = map (λpr. fold (xcontrib pr) (xslots G xs cls) (FinRep [])) (iprods G)›

fun diter :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ nat ⇒ indrep list› where
  ‹diter G xs 0 = map (λ_. FinRep []) (iprods G)›
| ‹diter G xs (Suc s) = dround G xs (diter G xs s)›

lemma diter_length [simp]: ‹length (diter G xs s) = length (iprods G)›
  by (cases s) (simp_all add: dround_def)

lemma xiter_mono:
  ‹p < length (iprods G) ⟹ irep_set (xiter G xs s ! p) ⊆ irep_set (xiter G xs (Suc s) ! p)›
  by (simp only: xiter.simps(2) xround_nth[OF xiter_length] fold_xcontrib_set) blast

lemma xiter_Suc_set:
  ‹p < length (iprods G) ⟹
   irep_set (xiter G xs (Suc s) ! p) = ⋃ (ximg (iprods G ! p) ` set (xslots G xs (xiter G xs s)))›
proof (induction s arbitrary: p)
  case 0
  then show ?case by (simp only: xiter.simps(2) xround_nth[OF xiter_length] fold_xcontrib_set) simp
next
  case (Suc s)
  have ‹list_all2 (λa b. irep_set a ⊆ irep_set b) (xiter G xs s) (xiter G xs (Suc s))›
    using xiter_mono[of _ G xs s] by (simp only: list_all2_conv_all_nth xiter_length) blast
  then have ‹xrel (⊆) (xslots G xs (xiter G xs s)) (xslots G xs (xiter G xs (Suc s)))›
    by (rule xslots_xrel[OF xrel_refl, rotated]) simp  from xrel_ximg[OF this, of ‹iprods G ! p›] Suc.IH[OF Suc.prems] show ?case
    by (simp only: xiter.simps(2)[of G xs ‹Suc s›] xround_nth[OF xiter_length Suc.prems] fold_xcontrib_set) blast
qed

lemma xiter_diter:
  assumes ‹xeq f f'›
  shows ‹list_all2 (λa b. irep_set a = irep_set b) (xiter G f s) (diter G f' s)›
proof (induction s)
  case 0
  then show ?case by (simp add: list_all2_conv_all_nth)
next
  case (Suc s)
  have eq: ‹⋃ (ximg pr ` set (xslots G f (xiter G f s))) = ⋃ (ximg pr ` set (xslots G f' (diter G f' s)))› for pr
    by (rule xeq_ximg[OF xslots_xrel[OF assms Suc.IH]])
  show ?case
    unfolding list_all2_conv_all_nth
  proof (intro conjI allI impI)
    fix p assume ‹p < length (xiter G f (Suc s))›
    then have p: ‹p < length (iprods G)› by (simp only: xiter_length)
    show ‹irep_set (xiter G f (Suc s) ! p) = irep_set (diter G f' (Suc s) ! p)›
      using p by (simp only: xiter_Suc_set[OF p] eq diter.simps dround_def nth_map fold_xcontrib_set) simp
  qed (simp only: xiter_length diter_length)qed

definition dclosure :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ ('n, 't) xitem list› where
  ‹dclosure G xs = xslots G xs (diter G xs (xfuel G xs))›

lemma xstable_diter:
  assumes ‹xeq f f'›
  shows ‹xstable G f (xiter G f t) ⟷ list_all2 irep_subset (diter G f' (Suc t)) (diter G f' t)›
proof -
  have a: ‹list_all2 (λa b. irep_set a = irep_set b) (xiter G f t) (diter G f' t)›
    and b: ‹list_all2 (λa b. irep_set a = irep_set b) (xiter G f (Suc t)) (diter G f' (Suc t))›
    by (rule xiter_diter[OF assms])+
  have ‹xstable G f (xiter G f t) ⟷ list_all2 irep_subset (xiter G f (Suc t)) (xiter G f t)›
    by (simp only: xstable_def xiter.simps(2))
  also have ‹… ⟷ list_all2 irep_subset (diter G f' (Suc t)) (diter G f' t)›
    using a b by (simp only: list_all2_conv_all_nth irep_subset_correct xiter_length diter_length) auto
  finally show ?thesis .
qed

lemma xfuel_xeq: ‹xeq f f' ⟹ xfuel G f = xfuel G f'›
  unfolding xfuel_def using xstable_diter[of f f'] xstable_diter[of f' f'] by simp

lemma xclosure_auto_dclosure: ‹xeq f f' ⟹ xeq (xclosure_auto G f) (dclosure G f')›
  unfolding xclosure_auto_def xclosure_def dclosure_def
  by (simp only: xfuel_xeq[of f f']) (rule xslots_xrel[OF _ xiter_diter])

text ‹Executably, the rounds are iterated once, as for const‹xclosure_auto›.›

lemma dclosure_code [code]:
  ‹dclosure G xs = xslots G xs (fst (the (while_option
     (λ(cls, nxt). ¬ list_all2 irep_subset nxt cls) (λ(cls, nxt). (nxt, dround G xs nxt))
     (diter G xs 0, dround G xs (diter G xs 0)))))›
proof -
  obtain k where ‹xstable G xs (xiter G xs k)›
    using xcls_stable_ex by blast
  then have ‹while_option (λt. ¬ xstable G xs (xiter G xs t)) Suc 0 = Some (xfuel G xs)›
    unfolding xfuel_def by (rule nat_search_Some)
  moreover have
    ‹map_option (λt. (diter G xs t, diter G xs (Suc t)))
       (while_option (λt. ¬ xstable G xs (xiter G xs t)) Suc 0) =
     while_option (λ(cls, nxt). ¬ list_all2 irep_subset nxt cls) (λ(cls, nxt). (nxt, dround G xs nxt))
       (diter G xs 0, diter G xs (Suc 0))›
    by (rule while_option_commute
        [where f = ‹λt. (diter G xs t, diter G xs (Suc t))› and s = 0])
      (simp_all add: xstable_diter[OF xeq_refl])
  ultimately have
    ‹Some (diter G xs (xfuel G xs), diter G xs (Suc (xfuel G xs))) =
     while_option (λ(cls, nxt). ¬ list_all2 irep_subset nxt cls) (λ(cls, nxt). (nxt, dround G xs nxt))
       (diter G xs 0, dround G xs (diter G xs 0))›
    by simp
  from this[symmetric] show ?thesis
    by (simp add: dclosure_def)
qed

text ‹For the code, a round builds the slot list once and keeps of it only the
  items before a nonterminal, with their images; each production then folds
  over the images for its left-hand side.›

definition dnx :: ‹('n, 't) xitem list ⇒ ('n × indrep) list› where
  ‹dnx sl = List.map_filter (λ((A, rhs), m, R).
     if m < length rhs then (case rhs ! m of (Nt B, r) ⇒ Some (B, irep_img r R) | _ ⇒ None)
     else None) sl›

lemma fold_xcontrib_dnx:
  ‹fold (xcontrib pr) sl acc =
   fold (λ(B, I) acc. if B = fst pr then irep_union I acc else acc) (dnx sl) acc›
  by (induction sl arbitrary: acc)
     (auto simp: dnx_def split: sym.splits prod.splits)

lemma dround_code [code]:
  ‹dround G xs cls = (let nx = dnx (xslots G xs cls) in
     map (λpr. fold (λ(B, I) acc. if B = fst pr then irep_union I acc else acc) nx (FinRep []))
       (iprods G))›
  unfolding dround_def Let_def by (simp add: fold_xcontrib_dnx)

subsection ‹Nonterminals as numbers›

text ‹The left-hand sides of a round are compared as numbers: a nonterminal is
  numbered by its first position among the left-hand sides of the productions,
  the per-production numbers are a table (text‹dtab›) that the
  text‹parser› command evaluates once, and the numbers of the kernel's
  successors are computed once per closure (text‹dkn›).›

fun ntidx :: ‹'n list ⇒ 'n ⇒ nat› where
  ‹ntidx [] B = 0›
| ‹ntidx (A # As) B = (if A = B then 0 else Suc (ntidx As B))›

lemma ntidx_eq_iff: ‹A ∈ set As ⟹ ntidx As B = ntidx As A ⟷ B = A›
  by (induction As) auto

definition dtab_of :: ‹'n list ⇒ 'n × ('n, 't) rhs ⇒ nat × nat option› where
  ‹dtab_of ns = (λ(A, rhs). (ntidx ns A,
     case rhs of (Nt B, _) # _ ⇒ Some (ntidx ns B) | _ ⇒ None))›

definition dtab :: ‹('n, 't) is_cfg ⇒ (nat × nat option) list› where
  ‹dtab G = map (dtab_of (map fst (iprods G))) (iprods G)›

definition dkn :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ (nat × indrep) list› where
  ‹dkn G xs = map (λ(B, I). (ntidx (map fst (iprods G)) B, I)) (dnx xs)›

definition dround_t :: ‹('n, 't) is_cfg ⇒ (nat × nat option) list ⇒ (nat × indrep) list ⇒
    indrep list ⇒ indrep list› where
  ‹dround_t G dt kn cls = (let
     nx = filter (λ(_, I). I ≠ FinRep []) (kn @ List.map_filter (λ(((l, f), (A, rhs)), R).
            case f of None ⇒ None
            | Some b ⇒ (case rhs of (_, r) # _ ⇒ Some (b, irep_img r R) | [] ⇒ None))
          (zip (zip dt (iprods G)) cls))
   in map (λ(l, f). fold (λ(b, I) acc. if b = l then irep_union I acc else acc) nx (FinRep [])) dt)›

lemma dnx_append: ‹dnx (xs @ ys) = dnx xs @ dnx ys›
  unfolding dnx_def by (induction xs) (simp_all split: option.split)

lemma dnx_slots:
  ‹map (λ(B, I). (ntidx ns B, I)) (dnx (map2 (λpr R. (pr, 0, R)) ps cls)) =
   List.map_filter (λ(((l, f), (A, rhs)), R). case f of None ⇒ None
       | Some b ⇒ (case rhs of (_, r) # _ ⇒ Some (b, irep_img r R) | [] ⇒ None))
     (zip (zip (map (dtab_of ns) ps) ps) cls)›
proof (induction ps arbitrary: cls)
  case (Cons pr ps)
  then show ?case
    by (cases cls) (auto simp: dnx_def dtab_of_def split: list.splits sym.splits prod.splits)
qed (simp add: dnx_def)

lemma fold_ntidx:
  assumes ‹A ∈ set ns›
  shows ‹fold (λ(b, I) acc. if b = ntidx ns A then irep_union I acc else acc)
           (map (λ(B, I). (ntidx ns B, I)) nx) acc =
         fold (λ(B, I) acc. if B = A then irep_union I acc else acc) nx acc›
  by (induction nx arbitrary: acc) (auto simp: ntidx_eq_iff[OF assms])

text ‹Images that are empty as representations are dropped: a union with them
  changes nothing, not even the representation.›

lemma fold_union_filter:
  ‹fold (λ(b, I) acc. if b = l then irep_union I acc else acc) (filter (λ(_, I). I ≠ FinRep []) nx) acc =
   fold (λ(b, I) acc. if b = l then irep_union I acc else acc) nx acc›
proof (induction nx arbitrary: acc)
  case (Cons x nx)
  have ‹irep_union (FinRep []) acc = acc› for acc by (cases acc) simp_all
  with Cons show ?case by (cases x) auto
qed simp

lemma dround_t_dround: ‹dround_t G (dtab G) (dkn G xs) cls = dround G xs cls›
proof -
  let ?ns = ‹map fst (iprods G)›
  let ?h = ‹λ(B, I). (ntidx ?ns B, I)›
  have nx: ‹dkn G xs @ List.map_filter (λ(((l, f), (A, rhs)), R). case f of None ⇒ None
            | Some b ⇒ (case rhs of (_, r) # _ ⇒ Some (b, irep_img r R) | [] ⇒ None))
          (zip (zip (dtab G) (iprods G)) cls) = map ?h (dnx (xslots G xs cls))›
    unfolding dkn_def dtab_def xslots_def dnx_append map_append dnx_slots ..
  have fe: ‹fold (λ(b, I) acc. if b = fst (dtab_of ?ns pr) then irep_union I acc else acc)
          (map ?h (dnx (xslots G xs cls))) (FinRep []) =
        fold (λ(B, I) acc. if B = fst pr then irep_union I acc else acc)
          (dnx (xslots G xs cls)) (FinRep [])› if ‹pr ∈ set (iprods G)› for pr
  proof -
    have ‹fst pr ∈ set ?ns› using that by simp
    moreover have ‹fst (dtab_of ?ns pr) = ntidx ?ns (fst pr)› by (simp add: dtab_of_def split: prod.split)
    ultimately show ?thesis by (simp only: fold_ntidx)
  qed
  show ?thesis
    unfolding dround_t_def dround_code Let_def nx unfolding dtab_def map_map
    by (intro map_cong refl) (simp only: comp_apply case_prod_beta fold_union_filter fe)
qed

definition dclosure_t :: ‹('n, 't) is_cfg ⇒ (nat × nat option) list ⇒
    ('n, 't) xitem list ⇒ ('n, 't) xitem list› where
  ‹dclosure_t G dt xs = (let kn = dkn G xs in xslots G xs (fst (the (while_option
     (λ(cls, nxt). ¬ list_all2 irep_subset nxt cls) (λ(cls, nxt). (nxt, dround_t G dt kn nxt))
     (map (λ_. FinRep []) dt, dround_t G dt kn (map (λ_. FinRep []) dt))))))›

lemma dclosure_t_eq: ‹dclosure_t G (dtab G) xs = dclosure G xs›
proof -
  have ‹map (λ_. FinRep []) (dtab G) = diter G xs 0› by (simp add: dtab_def)
  then show ?thesis
    unfolding dclosure_t_def dclosure_code Let_def dround_t_dround by simp
qed

subsection ‹The driver operations respect set-equality›

lemma list_all2_nth_refl:
  ‹list_all2 R xs ys ⟹ (⋀x. R x x) ⟹ R (xs ! k) (ys ! k)›
proof (induction arbitrary: k rule: list_all2_induct)
  case Nil then show ?case by simp
next
  case (Cons x xs y ys) then show ?case by (cases k) simp_all
qed

lemma list_all2_hd_refl: ‹list_all2 R xs ys ⟹ (⋀x. R x x) ⟹ R (hd xs) (hd ys)›
  using list_all2_nth_refl[of R xs ys 0] by (cases xs; cases ys) simp_all

lemma lgoto_xeq:
  ‹xeq xs ys ⟹ irep_set RA = irep_set RB ⟹ xeq (lgoto xs X RA) (lgoto ys X RB)›
  unfolding xrel_def lgoto_def
  by (induction rule: list_all2_induct) (auto split: prod.split_asm)

lemma red_set_xeq: ‹xeq xs ys ⟹ irep_set (red_set xs pr) = irep_set (red_set ys pr)›
  unfolding xrel_def red_set_def
  by (induction rule: list_all2_induct) (auto split: prod.split_asm)

lemma comps_xeq:
  ‹xeq xs ys ⟹ map fst (filter (λ(pr, m, R). m = length (snd pr)) xs) =
                map fst (filter (λ(pr, m, R). m = length (snd pr)) ys)›
  unfolding xrel_def by (induction rule: list_all2_induct) (auto split: prod.split_asm)

lemma dlic_cong: ‹irep_set RS = irep_set RS' ⟹ dlic i cells w pr RS = dlic i cells w pr RS'›
  unfolding dlic_def by (simp split: list.splits)
lemma dcands_xeq:
  assumes a: ‹xeq CL CL'›
  shows ‹dcands G i cells CL gc = dcands G i cells CL' gc›
proof -
  have eq: ‹(λpr. irep_nonempty (red_set CL pr) ∧ dlic i cells w pr (red_set CL pr)) =
        (λpr. irep_nonempty (red_set CL' pr) ∧ dlic i cells w pr (red_set CL' pr))› for w
    by (rule ext) (metis red_set_xeq[OF a] dlic_cong irep_nonempty_correct)
  show ?thesis unfolding dcands_def Let_def comps_xeq[OF a] eq ..
qed

lemma live_xeq: ‹xeq xs ys ⟹ live xs = live ys›
  unfolding xrel_def live_def
  by (induction rule: list_all2_induct) (auto split: prod.split_asm)

lemma gfinal_xeq:
  ‹list_all2 xeq Ys Ys' ⟹ gfinal G Shn (Ys, v) = gfinal G Shn (Ys', v)›
proof -
  assume a: ‹list_all2 xeq Ys Ys'›
  have ‹xeq (hd Ys) (hd Ys')› by (rule list_all2_hd_refl[OF a]) simp
  then have ‹list_ex (λ(pr, m, R). fst pr = Shn ∧ m = Suc 0 ∧ irep_mem (istart_ind G) R) (hd Ys) =
             list_ex (λ(pr, m, R). fst pr = Shn ∧ m = Suc 0 ∧ irep_mem (istart_ind G) R) (hd Ys')›
    unfolding xrel_def by (induction rule: list_all2_induct) (auto split: prod.split_asm)
  moreover have ‹Ys = [] ⟷ Ys' = []› using a by (auto dest: list_all2_lengthD)
  ultimately show ?thesis unfolding gfinal_def by simp
qed

definition gxeq :: ‹('n, 't) gconfig ⇒ ('n, 't) gconfig ⇒ bool› where
  ‹gxeq gc gc' ⟷ list_all2 xeq (fst gc) (fst gc') ∧ snd gc = snd gc'›

lemma mstep_cached_xeq:
  assumes c: ‹list_all2 xeq cstk cstk'› and g: ‹gxeq gc gc'›
  shows ‹rel_option gxeq (mstep_cached G cstk gc act) (mstep_cached G cstk' gc' act)›
proof -
  obtain Xs w Xs' where gc: ‹gc = (Xs, w)› ‹gc' = (Xs', w)› and x: ‹list_all2 xeq Xs Xs'›
    using g unfolding gxeq_def by (cases gc; cases gc') auto
  have len: ‹length Xs = length Xs'› using x by (rule list_all2_lengthD)
  have hd: ‹xeq (hd cstk) (hd cstk')› by (rule list_all2_hd_refl[OF c]) simp
  have nth: ‹xeq (cstk ! k) (cstk' ! k)› for k by (rule list_all2_nth_refl[OF c]) simp
  have dr: ‹list_all2 xeq (drop k Xs) (drop k Xs')› for k using x by (rule list_all2_dropI)
  show ?thesis
  proof (cases act)
    case DShift
    then show ?thesis
      using lgoto_xeq[OF hd] x len unfolding gc by (auto simp: mstep_cached_def gxeq_def split: list.splits)
  next
    case (DReduce pr)
    have rs: ‹irep_set (red_set (hd cstk) pr) = irep_set (red_set (hd cstk') pr)›
      by (rule red_set_xeq[OF hd])
    then show ?thesis
      using DReduce lgoto_xeq[OF nth rs] dr len unfolding gc
      by (auto simp: mstep_cached_def gxeq_def Let_def)
  qed
qed

lemma dlive_xeq: ‹gxeq gc gc' ⟹ dlive gc = dlive gc'›
proof -
  assume g: ‹gxeq gc gc'›
  then have x: ‹list_all2 xeq (fst gc) (fst gc')› unfolding gxeq_def by simp
  have ‹xeq (hd (fst gc)) (hd (fst gc'))› by (rule list_all2_hd_refl[OF x]) simp
  moreover have ‹fst gc = [] ⟷ fst gc' = []› using x by (auto dest: list_all2_lengthD)
  ultimately show ?thesis unfolding dlive_def by (auto split: prod.splits dest: live_xeq)
qed

lemma dpick_xeq:
  assumes c: ‹list_all2 xeq cstk cstk'› and g: ‹gxeq gc gc'›
  shows ‹rel_option (λ(a, g) (a', g'). a = a' ∧ gxeq g g') (dpick G cstk gc acts) (dpick G cstk' gc' acts)›
proof (induction acts)
  case (Cons act acts)
  show ?case
  proof (cases ‹mstep_cached G cstk gc act›)
    case None
    with mstep_cached_xeq[OF c g, of G act] have ‹mstep_cached G cstk' gc' act = None›
      by (cases ‹mstep_cached G cstk' gc' act›) simp_all
    with None Cons.IH show ?thesis by simp
  next
    case (Some g1)
    with mstep_cached_xeq[OF c g, of G act] obtain g1' where
      ‹mstep_cached G cstk' gc' act = Some g1'› and r: ‹gxeq g1 g1'›
      by (cases ‹mstep_cached G cstk' gc' act›) simp_all
    with Some Cons.IH dlive_xeq[OF r] show ?thesis by simp
  qed
qed simp

subsection ‹The driver over text‹dclosure››

lemma dcands_gxeq: ‹gxeq gc gc' ⟹ dcands G i cells CL gc = dcands G i cells CL gc'›
  unfolding gxeq_def dcands_def by (cases gc; cases gc') (auto dest: list_all2_lengthD)

definition dstep_c :: ‹('n, 't) is_cfg ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒ (nat × nat option) list ⇒
    ('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) dst option› where
  ‹dstep_c G gt sts redtab dt st = (case st of (gc, cstk, istk, v, tstk) ⇒
     let i = (case istk of [] ⇒ length sts | j # _ ⇒ j);
         cells = (if i < length redtab then redtab ! i else []);
         CL = (case cstk of [] ⇒ [] | c # _ ⇒ c)
     in (case dpick G cstk gc (dcands G i cells CL gc) of
        None ⇒ None
      | Some (act, gc') ⇒ Some (case act of
          DShift ⇒ (gc',
              dclosure_t G dt (hd (fst gc')) # cstk,
              dnext gt sts i (Tm (tok (hd v))) # istk,
              tl v,
              Leaf (hd v) # tstk)
        | DReduce pr ⇒ (gc',
              dclosure_t G dt (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))))›

definition dst_rel :: ‹('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) dst ⇒ bool› where
  ‹dst_rel st st' ⟷ gxeq (fst st) (fst st') ∧
     list_all2 xeq (fst (snd st)) (fst (snd st')) ∧ snd (snd st) = snd (snd st')›

lemma dstep_xeq:
  assumes r: ‹dst_rel st st'›
  shows ‹rel_option dst_rel (dstep G gt sts redtab st) (dstep_c G gt sts redtab (dtab G) st')›
proof -
  obtain gc cstk istk v tstk gc' cstk' where
    st: ‹st = (gc, cstk, istk, v, tstk)› ‹st' = (gc', cstk', istk, v, tstk)› and
    g: ‹gxeq gc gc'› and c: ‹list_all2 xeq cstk cstk'›
    using r unfolding dst_rel_def by (cases st; cases st') auto
  have cl: ‹xeq (case cstk of [] ⇒ [] | c # _ ⇒ c) (case cstk' of [] ⇒ [] | c # _ ⇒ c)›
    using c by (cases cstk; cases cstk') 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 acts where ‹acts = dcands G i cells (case cstk of [] ⇒ [] | c # _ ⇒ c) gc›
  have acts': ‹dcands G i cells (case cstk' of [] ⇒ [] | c # _ ⇒ c) gc' = acts›
    unfolding acts_def dcands_xeq[OF cl] dcands_gxeq[OF g] ..
  have p: ‹rel_option (λ(a, g) (a', g'). a = a' ∧ gxeq g g') (dpick G cstk gc acts) (dpick G cstk' gc' acts)›
    by (rule dpick_xeq[OF c g])
  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 = acts›
    ‹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' = acts›
    using acts' unfolding acts_def cells_def i_def by simp_all
  show ?thesis
  proof (cases ‹dpick G cstk gc acts›)
    case None
    with p have ‹dpick G cstk' gc' acts = None› by (cases ‹dpick G cstk' gc' acts›) auto
    with None show ?thesis
      unfolding st dstep_def dstep_c_def Let_def prod.case u by simp
  next
    case (Some p1)
    then obtain act g1 where p1: ‹dpick G cstk gc acts = Some (act, g1)› by (cases p1) auto
    with p obtain g1' where p1': ‹dpick G cstk' gc' acts = Some (act, g1')› and g1: ‹gxeq g1 g1'›
      by (cases ‹dpick G cstk' gc' acts›) auto
    have x1: ‹list_all2 xeq (fst g1) (fst g1')› using g1 unfolding gxeq_def by simp
    have h: ‹xeq (xclosure_auto G (hd (fst g1))) (dclosure_t G (dtab G) (hd (fst g1')))›
      unfolding dclosure_t_eq by (rule xclosure_auto_dclosure, rule list_all2_hd_refl[OF x1]) simp
    have ‹list_all2 xeq (drop k cstk) (drop k cstk')› for k using c by (rule list_all2_dropI)
    with h g1 c show ?thesis
      unfolding st dstep_def dstep_c_def Let_def prod.case u
      by (simp add: p1 p1' dst_rel_def split: dact.splits)
  qed
qed

lemma gfinal_gxeq: ‹gxeq gc gc' ⟹ gfinal G Shn gc = gfinal G Shn gc'›
  unfolding gxeq_def by (cases gc; cases gc') (auto dest: gfinal_xeq)

partial_function (option) drun_nh_c ::
  ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒ (nat × nat option) list ⇒
    ('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) ast option›
  where
  ‹drun_nh_c G Shn gt sts redtab dt st =
     (case st of (gc, cstk, istk, v, tstk) ⇒
        if gfinal G Shn gc then (case tstk of t # _ ⇒ Some t | [] ⇒ None)
        else Option.bind (dstep_c G gt sts redtab dt st) (drun_nh_c G Shn gt sts redtab dt))›

lemmas drun_nh_c_simps [code] = drun_nh_c.simps

lemma drun_nh_imp_c:
  assumes ‹drun_nh G Shn gt sts redtab st = Some t›
  shows ‹∀st'. dst_rel st st' ⟶ drun_nh_c G Shn gt sts redtab (dtab G) st' = Some t›
proof (rule drun_nh.raw_induct[OF _ assms], goal_cases)
  case (1 f G Shn gt sts redtab st t)
  show ?case
  proof (intro allI impI)
    fix st' assume r: ‹dst_rel st st'›
    obtain gc cstk istk v tstk gc' cstk' where
      st: ‹st = (gc, cstk, istk, v, tstk)› ‹st' = (gc', cstk', istk, v, tstk)› and g: ‹gxeq gc gc'›
      using r unfolding dst_rel_def by (cases st; cases st') auto
    show ‹drun_nh_c G Shn gt sts redtab (dtab G) st' = Some t›
    proof (cases ‹gfinal G Shn gc›)
      case True
      with "1"(2) gfinal_gxeq[OF g] show ?thesis
        unfolding st by (subst drun_nh_c.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 dstep_xeq[OF r, of G gt sts redtab] sp obtain st1' where
        sp': ‹dstep_c G gt sts redtab (dtab G) st' = Some st1'› and r1: ‹dst_rel st1 st1'›
        by (cases ‹dstep_c G gt sts redtab (dtab G) st'›) auto
      from "1"(1)[OF rec] r1 have ‹drun_nh_c G Shn gt sts redtab (dtab G) st1' = Some t› by blast
      with False gfinal_gxeq[OF g] sp' show ?thesis
        unfolding st by (subst drun_nh_c.simps) simp
    qed
  qed
qed

lemma drun_nh_c_imp:
  assumes ‹drun_nh_c G Shn gt sts redtab dt st' = Some t›
  shows ‹dt = dtab G ⟶ (∀st. dst_rel st st' ⟶ drun_nh G Shn gt sts redtab st = Some t)›
proof (rule drun_nh_c.raw_induct[OF _ assms], goal_cases)
  case (1 f G Shn gt sts redtab dt st' t)
  show ?case
  proof (intro allI impI)
    fix st assume d: ‹dt = dtab G› and r: ‹dst_rel st st'›
    note prem = "1"(2)[unfolded d]
    obtain gc cstk istk v tstk gc' cstk' where
      st: ‹st = (gc, cstk, istk, v, tstk)› ‹st' = (gc', cstk', istk, v, tstk)› and g: ‹gxeq gc gc'›
      using r unfolding dst_rel_def by (cases st; cases st') auto
    show ‹drun_nh G Shn gt sts redtab st = Some t›
    proof (cases ‹gfinal G Shn gc›)
      case True
      with prem gfinal_gxeq[OF g] show ?thesis
        unfolding st by (subst drun_nh.simps) simp
    next
      case False
      with prem gfinal_gxeq[OF g] obtain st1' where sp': ‹dstep_c G gt sts redtab (dtab G) st' = Some st1'›
        and rec: ‹f G Shn gt sts redtab (dtab G) st1' = Some t›
        unfolding st by (auto simp: bind_eq_Some_conv)
      from dstep_xeq[OF r, of G gt sts redtab] sp' obtain st1 where
        sp: ‹dstep G gt sts redtab st = Some st1› and r1: ‹dst_rel st1 st1'›
        by (cases ‹dstep G gt sts redtab st›) auto
      from "1"(1)[OF rec] r1 have ‹drun_nh G Shn gt sts redtab st1 = Some t› by blast
      with False sp show ?thesis
        unfolding st by (subst drun_nh.simps) simp
    qed
  qed
qed

lemma drun_nh_eq_c:
  ‹dst_rel st st' ⟹ drun_nh G Shn gt sts redtab st = drun_nh_c G Shn gt sts redtab (dtab G) st'›
  using drun_nh_imp_c[of G Shn gt sts redtab st] drun_nh_c_imp[of G Shn gt sts redtab ‹dtab G› st']
  by (metis not_Some_eq)

lemma dparse_via_tables_nh_c:
  assumes st:  ‹pr0_states G Shn = sts›
    and   gt:  ‹pgtab G sts = gtab›
    and   rt:  ‹red_buckets G Shn (length sts) = redtab›
    and   xi:  ‹xinit G Shn = xin›
    and   xc:  ‹dclosure G xin = xclos›
    and   i0:  ‹st_find sts (lr0_start G Shn) = i0›
    and   dt:  ‹dtab G = dtb›
  shows ‹dparse G Shn w =
     drun_nh_c G Shn gtab sts redtab dtb (([xin], tcols w), [xclos], [i0], w, [])›
proof -
  have ‹dst_rel (([xin], tcols w), [xclosure_auto G xin], [i0], w, [])
                (([xin], tcols w), [xclos], [i0], w, [])›
    using xclosure_auto_dclosure[OF xeq_refl, of G xin] unfolding xc dst_rel_def gxeq_def by simp
  then show ?thesis
    unfolding dparse_via_tables_nh[OF st gt rt xi refl i0] dt[symmetric] by (rule drun_nh_eq_c)
qed

text ‹const‹dstep_act› over text‹dclosure›, for drivers that need the
  action (the error diagnostics).›

definition dstep_act_c :: ‹('n, 't) is_cfg ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒ (nat × nat option) list ⇒
    ('m, 'ch, 'n, 't) dst ⇒ (('n, 't) dact × ('m, 'ch, 'n, 't) dst) option› where
  ‹dstep_act_c G gt sts redtab dt st = (case st of (gc, cstk, istk, v, tstk) ⇒
     let i = (case istk of [] ⇒ length sts | j # _ ⇒ j);
         cells = (if i < length redtab then redtab ! i else []);
         CL = (case cstk of [] ⇒ [] | c # _ ⇒ c)
     in (case dpick G cstk gc (dcands G i cells CL gc) of
        None ⇒ None
      | Some (act, gc') ⇒ Some (act, case act of
          DShift ⇒ (gc',
              dclosure_t G dt (hd (fst gc')) # cstk,
              dnext gt sts i (Tm (tok (hd v))) # istk,
              tl v,
              Leaf (hd v) # tstk)
        | DReduce pr ⇒ (gc',
              dclosure_t G dt (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))))›

end