Theory LR_Trie

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

theory LR_Trie
  imports LR_Int
begin

section ‹Tables as binary tries›

text ‹A table from naturals to values as a binary trie: the path to a key is
  the sequence of bits of its binary numeral, least significant first. With
  binary naturals (▩‹Code_Binary_Nat›) a lookup follows the constructors of
  the numeral and involves no arithmetic, and a trie is static data.

  The datatype is the binary trie of Verbatim++
  cite‹‹Sects.~5.1--5.2› in "egolf2022-verbatim-plus-plus"›, where a memo is keyed by the
  length of a suffix as a binary number and a lookup reads the key bit by bit, comparing no
  keys.  Okasaki and Gill cite‹"okasaki1998-integer-maps"› treat integer maps as binary
  tries (Patricia trees); the trie here is a plain one, with one node per bit of the key.›

datatype 'a ntrie = NTip | NNode ‹'a option› ‹'a ntrie› ‹'a ntrie›

fun lookup_num :: ‹'a ntrie ⇒ num ⇒ 'a option› where
  ‹lookup_num NTip _ = None›
| ‹lookup_num (NNode x l r) num.One = x›
| ‹lookup_num (NNode x l r) (num.Bit0 k) = lookup_num l k›
| ‹lookup_num (NNode x l r) (num.Bit1 k) = lookup_num r k›

datatype 'a ntab = NTab ‹'a option› ‹'a ntrie›

definition tlookup :: ‹'a ntab ⇒ nat ⇒ 'a option› where
  ‹tlookup t n = (case t of NTab z tr ⇒ if n = 0 then z else lookup_num tr (num_of_nat n))›

text ‹Code equations for binary naturals, to be declared where
  ▩‹Code_Binary_Nat› is imported.›

lemma tlookup_binary:
  ‹tlookup t 0 = (case t of NTab z tr ⇒ z)›
  ‹tlookup t (nat_of_num k) = (case t of NTab z tr ⇒ lookup_num tr k)›
  unfolding tlookup_def by (simp_all split: ntab.splits add: nat_of_num_numeral)

text ‹The trie of the keys ‹a * k + b›, ‹k ≥ 1›, up to the bound ‹B›.›

primrec mk_trie :: ‹(nat ⇒ 'a option) ⇒ nat ⇒ nat ⇒ nat ⇒ nat ⇒ 'a ntrie› where
  ‹mk_trie f B 0 a b = NTip›
| ‹mk_trie f B (Suc fu) a b = (if B < a + b then NTip
     else NNode (f (a + b)) (mk_trie f B fu (2 * a) b) (mk_trie f B fu (2 * a) (a + b)))›

fun nbits :: ‹num ⇒ nat› where
  ‹nbits num.One = 1›
| ‹nbits (num.Bit0 k) = Suc (nbits k)›
| ‹nbits (num.Bit1 k) = Suc (nbits k)›

lemma nat_of_num_pos: ‹0 < nat_of_num k›
  by (induction k) auto

lemma nbits_le: ‹nbits k ≤ nat_of_num k›
proof (induction k)
  case (Bit0 k) then show ?case using nat_of_num_pos[of k] by simp
next
  case (Bit1 k) then show ?case using nat_of_num_pos[of k] by simp
qed simp

lemma lookup_mk_trie:
  assumes ‹0 < a› and ‹a * nat_of_num k + b ≤ B ⟶ nbits k ≤ fu›
  shows ‹lookup_num (mk_trie f B fu a b) k =
    (if a * nat_of_num k + b ≤ B then f (a * nat_of_num k + b) else None)›
  using assms
proof (induction k arbitrary: fu a b)
  case One
  then show ?case by (cases fu) auto
next
  case (Bit0 k)
  have eq: ‹a * nat_of_num (num.Bit0 k) + b = 2 * a * nat_of_num k + b› by simp
  have le: ‹a + b ≤ 2 * a * nat_of_num k + b› using nat_of_num_pos[of k] Bit0.prems(1) by simp
  show ?case
  proof (cases fu)
    case 0 then show ?thesis using Bit0.prems by simp
  next
    case (Suc fu')
    show ?thesis
    proof (cases ‹B < a + b›)
      case True
      then have ‹¬ a * nat_of_num (num.Bit0 k) + b ≤ B› using le eq by linarith
      then show ?thesis using Suc True by simp
    next
      case False
      have ih: ‹lookup_num (mk_trie f B fu' (2 * a) b) k =
          (if 2 * a * nat_of_num k + b ≤ B then f (2 * a * nat_of_num k + b) else None)›
        by (rule Bit0.IH) (use Bit0.prems Suc in ‹unfold eq, auto›)
      then show ?thesis unfolding eq using Suc False by simp
    qed
  qed
next
  case (Bit1 k)
  have eq: ‹a * nat_of_num (num.Bit1 k) + b = 2 * a * nat_of_num k + (a + b)› by simp
  show ?case
  proof (cases fu)
    case 0 then show ?thesis using Bit1.prems by simp
  next
    case (Suc fu')
    show ?thesis
    proof (cases ‹B < a + b›)
      case True
      then have ‹¬ a * nat_of_num (num.Bit1 k) + b ≤ B› using eq by linarith
      then show ?thesis using Suc True by simp
    next
      case False
      have ih: ‹lookup_num (mk_trie f B fu' (2 * a) (a + b)) k =
          (if 2 * a * nat_of_num k + (a + b) ≤ B then f (2 * a * nat_of_num k + (a + b)) else None)›
        by (rule Bit1.IH) (use Bit1.prems Suc in ‹unfold eq, auto›)
      then show ?thesis unfolding eq using Suc False by simp
    qed
  qed
qed

definition tab_of_fun :: ‹(nat ⇒ 'a option) ⇒ nat ⇒ 'a ntab› where
  ‹tab_of_fun f B = NTab (f 0) (mk_trie f B (Suc B) 1 0)›

lemma tlookup_tab_of_fun: ‹tlookup (tab_of_fun f B) n = (if n ≤ B then f n else None)›
proof (cases ‹n = 0›)
  case True
  then show ?thesis unfolding tab_of_fun_def tlookup_def by simp
next
  case False
  then have n: ‹n = nat_of_num (num_of_nat n)›
    using num_of_nat_inverse by simp
  have ‹lookup_num (mk_trie f B (Suc B) 1 0) (num_of_nat n) =
      (if 1 * nat_of_num (num_of_nat n) + 0 ≤ B then f (1 * nat_of_num (num_of_nat n) + 0) else None)›
    by (rule lookup_mk_trie) (use nbits_le[of ‹num_of_nat n›] in auto)
  then show ?thesis unfolding tab_of_fun_def tlookup_def using False n[symmetric] by simp
qed

definition tab_of_list :: ‹'a list ⇒ 'a ntab› where
  ‹tab_of_list xs = tab_of_fun (λn. if n < length xs then Some (xs ! n) else None) (length xs)›

lemma tlookup_tab_of_list: ‹tlookup (tab_of_list xs) n = (if n < length xs then Some (xs ! n) else None)›
  unfolding tab_of_list_def tlookup_tab_of_fun by auto

definition tab_of_assoc :: ‹(nat × 'a) list ⇒ 'a ntab› where
  ‹tab_of_assoc kvs = tab_of_fun (map_of kvs) (fold max (map fst kvs) 0)›

lemma fold_max_acc: ‹(m :: nat) ≤ fold max xs m›
  by (induction xs arbitrary: m) (auto intro: le_trans[OF max.cobounded2])

lemma fold_max_ge: ‹(x :: nat) ∈ set xs ⟹ x ≤ fold max xs m›
  by (induction xs arbitrary: m) (auto intro: le_trans[OF max.cobounded1 fold_max_acc])

lemma tlookup_tab_of_assoc: ‹tlookup (tab_of_assoc kvs) k = map_of kvs k›
proof -
  have ‹map_of kvs k = None› if ‹¬ k ≤ fold max (map fst kvs) 0›
  proof (rule ccontr)
    assume ‹map_of kvs k ≠ None›
    then have ‹k ∈ set (map fst kvs)› by (auto dest: map_of_SomeD intro: rev_image_eqI)
    then show False using that fold_max_ge by blast
  qed
  then show ?thesis unfolding tab_of_assoc_def tlookup_tab_of_fun by auto
qed

definition tab_opt :: ‹(nat × 'a) list ⇒ ('a ⇒ 'b option) ⇒ 'b ntab› where
  ‹tab_opt kvs g = tab_of_fun (λk. Option.bind (map_of kvs k) g) (fold max (map fst kvs) 0)›

lemma tlookup_tab_opt: ‹tlookup (tab_opt kvs g) k = Option.bind (map_of kvs k) g›
proof -
  have ‹map_of kvs k = None› if ‹¬ k ≤ fold max (map fst kvs) 0›
  proof (rule ccontr)
    assume ‹map_of kvs k ≠ None›
    then have ‹k ∈ set (map fst kvs)› by (auto dest: map_of_SomeD intro: rev_image_eqI)
    then show False using that fold_max_ge by blast
  qed
  then show ?thesis unfolding tab_opt_def tlookup_tab_of_fun by auto
qed

text ‹Structural drop, without arithmetic on the length.›

fun drop_as :: ‹'a list ⇒ 'b list ⇒ 'b list› where
  ‹drop_as [] ys = ys›
| ‹drop_as (_ # xs) [] = []›
| ‹drop_as (_ # xs) (_ # ys) = drop_as xs ys›

lemma drop_as_eq: ‹drop_as xs ys = drop (length xs) ys›
  by (induction xs ys rule: drop_as.induct) auto

subsection ‹Trie tables and the trie step›

datatype ('n, 't) jtabs = JTabs
  (jt_lal: ‹('t × nat) list›) (jt_miss: nat)
  (jt_gT: ‹nat ntab ntab›) (jt_gN: ‹nat ntab ntab›)
  (jt_lic: ‹unit ntab ntab ntab›) (jt_pc: ‹nat list ntab›)
  (jt_prs: ‹(('n × ('n, 't) rhs) × nat) ntab›) (jt_pf: ‹bool ntab›)

text ‹The lookahead as a number: ‹0› for the end of the input, ‹Suc i› for the
  ‹i›-th token of the tables, ‹jt_miss› for any other token.›

definition jla :: ‹('n, 't) jtabs ⇒ ('m, 'ch, 't) tword ⇒ nat› where
  ‹jla J v = (case v of [] ⇒ 0 | x # _ ⇒
     (case map_of (jt_lal J) (tok x) of Some l ⇒ l | None ⇒ jt_miss J))›

definition jget :: ‹'a ntab ntab ⇒ nat ⇒ nat ⇒ 'a option› where
  ‹jget tab i k = (case tlookup tab i of None ⇒ None | Some r ⇒ tlookup r k)›

definition jlicd :: ‹unit ntab option ⇒ nat ⇒ bool› where
  ‹jlicd lics j = (case lics of None ⇒ False | Some t ⇒ tlookup t j ≠ None)›

definition jtarget :: ‹('n, 't) jtabs ⇒ nat list ⇒ nat ⇒ iact ⇒ nat option› where
  ‹jtarget J stk l act = (case act of
      IShift ⇒ jget (jt_gT J) (hd stk) l
    | IReduce j ⇒ (case tlookup (jt_prs J) j of None ⇒ None | Some (pr, A) ⇒
        (case drop_as (snd pr) stk of [] ⇒ None | i' # _ ⇒ jget (jt_gN J) i' A)))›

definition jctl :: ‹('n, 't) jtabs ⇒ ('m, 'ch, 't) sctl_t ⇒
    (('n, 't) dact × ('m, 'ch, 't) sctl_t) option› where
  ‹jctl J c = (case c of (stk, v) ⇒
     (case stk of [] ⇒ None | i # _ ⇒
       let l = jla J v;
           lics = jget (jt_lic J) i l;
           comps = (case tlookup (jt_pc J) i of None ⇒ [] | Some cs ⇒ cs);
           cands = (case v of [] ⇒ [] | _ ⇒ [IShift]) @ map IReduce (filter (jlicd lics) comps)
       in (case spick (jtarget J stk l) cands of
            None ⇒ None
          | Some (IShift, q) ⇒ Some (DShift, q # stk, tl v)
          | Some (IReduce j, q) ⇒ (case tlookup (jt_prs J) j of None ⇒ None | Some (pr, A) ⇒
              Some (DReduce pr, q # drop_as (snd pr) stk, v)))))›

definition jfinal :: ‹('n, 't) jtabs ⇒ ('m, 'ch, 't) sctl_t ⇒ bool› where
  ‹jfinal J c ⟷ (case c of (stk, v) ⇒ v = [] ∧
     (case stk of [] ⇒ False | i # _ ⇒ tlookup (jt_pf J) i = Some True))›

subsection ‹The trie tables of the list tables›

fun jtabs_of :: ‹('n, 't) ltabs ⇒ ('n, 't) jtabs› where
  ‹jtabs_of (LTabs ns gT gN cs pc prs pl ph pf) = (let
     toks = remdups (concat (map (map fst) gT) @ concat (map (List.map_filter snd) cs));
     lal = map (λa. (a, Suc (la_tindex toks a))) toks;
     miss = Suc (length toks);
     li = (λa. case map_of lal a of Some l ⇒ l | None ⇒ miss);
     lt = (λt. case t of None ⇒ 0 | Some a ⇒ li a)
   in JTabs lal miss
     (tab_of_list (map (λrow. tab_opt (map (λ(a, j). (li a, j)) row)
        (λj. if min j ns < ns then Some (min j ns) else None)) gT))
     (tab_of_list (map (λrow. tab_opt row
        (λj. if min j ns < ns then Some (min j ns) else None)) gN))
     (tab_of_list (map (λcells. tab_of_fun (λl. let js = map fst (filter (λ(j, t). lt t = l) cells) in
        if js = [] then None else Some (tab_of_assoc (map (λj. (j, ())) js))) miss) cs))
     (tab_of_list pc)
     (tab_of_list (zip prs ph))
     (tab_of_list pf))›

subsection ‹Correctness of the trie step›

text ‹The trie tables need the facts that const‹mk_ltabs› guarantees about the
  productions offered as reduces.›

fun lwf2 :: ‹('n, 't) ltabs ⇒ bool› where
  ‹lwf2 (LTabs ns gT gN cs pc prs pl ph pf) ⟷ (∀row ∈ set pc. ∀j ∈ set row.
     j < length prs ∧ j < length ph ∧ j < length pl ∧ pl ! j = length (snd (prs ! j)))›

lemma lwf2_mk_ltabs: ‹lwf2 (mk_ltabs gt sts redtab pc pf)›
proof -
  have ‹la_tindex (remdups (concat pc)) pr < length (remdups (concat pc))›
    if ‹row ∈ set pc› ‹pr ∈ set row› for row pr
    using la_tindex_nth[of pr ‹remdups (concat pc)›] that by auto
  then show ?thesis unfolding mk_ltabs_def Let_def by auto
qed

text ‹Token numbers.›

lemma map_of_lal:
  ‹map_of (map (λa. (a, f a)) xs) b = (if b ∈ set xs then Some (f b) else None)›
  by (induction xs) auto

lemma li_inj:
  assumes ‹a ∈ set toks›
  shows ‹(case map_of (map (λa. (a, Suc (la_tindex toks a))) toks) a of Some l ⇒ l | None ⇒ Suc (length toks)) =
      (case map_of (map (λa. (a, Suc (la_tindex toks a))) toks) b of Some l ⇒ l | None ⇒ Suc (length toks))
    ⟷ a = b›
  using assms la_tindex_nth[of a toks] la_tindex_inj[of a toks b] by (auto simp: map_of_lal)

lemma map_of_li_row:
  assumes li_eq: ‹⋀a b. a ∈ set toks ⟹ li a = li b ⟷ a = b›
    and keys: ‹set (map fst row) ⊆ set toks›
  shows ‹map_of (map (λ(a, j). (li a, j)) row) (li b) = map_of row b›
  using keys
proof (induction row)
  case (Cons x row)
  obtain a j where x: ‹x = (a, j)› by (cases x)
  have a: ‹a ∈ set toks› using Cons.prems x by simp
  show ?case using Cons li_eq[OF a, of b] unfolding x by auto
qed simp

lemma map_of_li_row_0:
  fixes li :: ‹'a ⇒ nat›
  assumes ‹⋀a. 0 < li a›
  shows ‹map_of (map (λ(a, j). (li a, j)) row) 0 = None›
proof (induction row)
  case (Cons x row)
  obtain a j where x: ‹x = (a, j)› by (cases x)
  show ?case using Cons assms[of a] unfolding x by auto
qed simp

theorem jctl_eq:
  assumes wf: ‹lwf2 L›
  shows ‹jctl (jtabs_of L) (stk, v) = isctl (itabs_of L) (stk, v)›
proof -
  obtain ns gT gN cs pc prs pl ph pf where L: ‹L = LTabs ns gT gN cs pc prs pl ph pf›
    by (cases L)
  define toks where ‹toks = remdups (concat (map (map fst) gT) @
     concat (map (List.map_filter snd) cs))›
  define li where ‹li = (λa. case map_of (map (λa. (a, Suc (la_tindex toks a))) toks) a of
     Some l ⇒ l | None ⇒ Suc (length toks))›
  define lt where ‹lt = (λt. case t of None ⇒ 0 | Some a ⇒ li a)›
  define J where ‹J = jtabs_of L›
  define T where ‹T = itabs_of L›
  have Jf: ‹jt_lal J = map (λa. (a, Suc (la_tindex toks a))) toks› ‹jt_miss J = Suc (length toks)›
    ‹jt_gT J = tab_of_list (map (λrow. tab_opt (map (λ(a, j). (li a, j)) row)
        (λj. if min j ns < ns then Some (min j ns) else None)) gT)›
    ‹jt_gN J = tab_of_list (map (λrow. tab_opt row
        (λj. if min j ns < ns then Some (min j ns) else None)) gN)›
    ‹jt_lic J = tab_of_list (map (λcells. tab_of_fun
        (λl. let js = map fst (filter (λ(j, t). lt t = l) cells) in
          if js = [] then None else Some (tab_of_assoc (map (λj. (j, ())) js)))
        (Suc (length toks))) cs)›
    ‹jt_pc J = tab_of_list pc› ‹jt_prs J = tab_of_list (zip prs ph)› ‹jt_pf J = tab_of_list pf›
    unfolding J_def L toks_def li_def lt_def by (simp_all add: Let_def)
  have li_val: ‹li a = (if a ∈ set toks then Suc (la_tindex toks a) else Suc (length toks))› for a
    unfolding li_def by (simp add: map_of_lal)
  have li_pos: ‹0 < li a› for a using li_val[of a] by simp
  have li_le: ‹li a ≤ Suc (length toks)› for a
    using li_val[of a] la_tindex_nth[of a toks] by (auto split: if_splits)
  have li_eq: ‹a ∈ set toks ⟹ li a = li b ⟷ a = b› for a b
    unfolding li_def by (rule li_inj)
  have jla: ‹jla J v = (case v of [] ⇒ 0 | x # _ ⇒ li (tok x))›
    unfolding jla_def Jf li_def by (simp split: list.splits)
  have gT_keys: ‹set (map fst row) ⊆ set toks› if ‹row ∈ set gT› for row
    using that unfolding toks_def by auto
  have cs_toks: ‹a ∈ set toks› if ‹row ∈ set cs› ‹(j, Some a) ∈ set row› for row j a
    using that unfolding toks_def by (force simp: List.map_filter_def)
  have matchv: ‹lt t = jla J v ⟷ (case v of [] ⇒ t = None | x # _ ⇒ t = Some (tok x))›
    if ‹t = None ∨ (∃a. t = Some a ∧ a ∈ set toks)› for t
    using that li_pos li_eq unfolding lt_def jla by (auto split: list.splits option.splits)
  show ?thesis
  proof (cases stk)
    case Nil
    then show ?thesis unfolding J_def[symmetric] T_def[symmetric] jctl_def isctl_def by simp
  next
    case (Cons i rest)
    define cells where ‹cells = (if i < length cs then cs ! i else [])›
    define comps where ‹comps = (if i < length pc then pc ! i else [])›
    define I where ‹I = icands comps cells v›
    have jc: ‹j < length prs ∧ j < length ph ∧ j < length pl ∧ pl ! j = length (snd (prs ! j))›
      if ‹j ∈ set comps› for j
      using that wf unfolding L comps_def by (auto split: if_splits)
    have jI: ‹j ∈ set comps› if ‹IReduce j ∈ set I› for j
      using that unfolding I_def icands_def Let_def by (cases v) auto
    have sI: ‹v ≠ []› if ‹IShift ∈ set I›
      using that unfolding I_def icands_def Let_def by (cases v) auto
    have lic: ‹jlicd (jget (jt_lic J) i (jla J v)) j = ilic cells v j› for j
    proof (cases ‹i < length cs›)
      case False
      then show ?thesis unfolding jlicd_def jget_def Jf cells_def ilic_def
        by (simp add: tlookup_tab_of_list)
    next
      case True
      define row where ‹row = cs ! i›
      have row_in: ‹row ∈ set cs› using True unfolding row_def by simp
      have la_le: ‹jla J v ≤ Suc (length toks)› using li_le unfolding jla by (simp split: list.splits)
      define js where ‹js = map fst (filter (λ(j, t). lt t = jla J v) row)›
      have g: ‹jget (jt_lic J) i (jla J v) =
          (if js = [] then None else Some (tab_of_assoc (map (λj. (j, ())) js)))›
        unfolding jget_def Jf using True la_le
        by (simp add: tlookup_tab_of_list tlookup_tab_of_fun row_def[symmetric] js_def Let_def)
      have mem: ‹jlicd (jget (jt_lic J) i (jla J v)) j ⟷ j ∈ set js›
        unfolding g jlicd_def by (auto simp: tlookup_tab_of_assoc map_of_lal)
      have tv: ‹t = None ∨ (∃a. t = Some a ∧ a ∈ set toks)› if ‹(j', t) ∈ set row› for j' t
        using that cs_toks[OF row_in] by (cases t) auto
      have e1: ‹j ∈ set js ⟷ (∃t. (j, t) ∈ set row ∧ lt t = jla J v)›
        unfolding js_def by force
      have e2: ‹ilic cells v j ⟷
          (∃t. (j, t) ∈ set row ∧ (case v of [] ⇒ t = None | x # _ ⇒ t = Some (tok x)))›
        unfolding ilic_def list_ex_iff cells_def row_def using True by force
      show ?thesis unfolding mem e1 e2 using matchv tv by blast
    qed
    have cj: ‹(case tlookup (jt_pc J) i of None ⇒ [] | Some cs ⇒ cs) = comps›
      unfolding Jf comps_def by (simp add: tlookup_tab_of_list)
    have cand: ‹(case v of [] ⇒ [] | _ ⇒ [IShift]) @
        map IReduce (filter (jlicd (jget (jt_lic J) i (jla J v))) comps) = I›
    proof -
      have ‹filter (jlicd (jget (jt_lic J) i (jla J v))) comps = filter (ilic cells v) comps›
        by (rule filter_cong) (simp_all add: lic)
      then show ?thesis unfolding I_def icands_def Let_def by (cases v) simp_all
    qed
    have hd_i: ‹hd stk = i› using Cons by simp
    have pg: ‹jget (jt_gT J) i' (li a) = (let q = inext (it_gtT T) (it_ns T) i' a in
        if q < it_ns T then Some q else None)› for i' a
    proof (cases ‹i' < length gT›)
      case True
      have k: ‹set (map fst (gT ! i')) ⊆ set toks› using gT_keys True by simp
      show ?thesis unfolding jget_def Jf T_def L using True
        by (simp add: tlookup_tab_of_list tlookup_tab_opt map_of_li_row[OF li_eq k] inext_def Let_def
            split: option.splits)
    next
      case False
      then show ?thesis unfolding jget_def Jf T_def L by (simp add: tlookup_tab_of_list inext_def)
    qed
    have pg0: ‹jget (jt_gT J) i' 0 = None› for i'
      unfolding jget_def Jf
      by (simp add: tlookup_tab_of_list tlookup_tab_opt map_of_li_row_0[OF li_pos] split: option.splits)
    have pn: ‹jget (jt_gN J) i' A = (let q = inext (it_gtN T) (it_ns T) i' A in
        if q < it_ns T then Some q else None)› for i' A
      unfolding jget_def Jf T_def L
      by (simp add: tlookup_tab_of_list tlookup_tab_opt inext_def Let_def split: option.splits)
    have pj: ‹tlookup (jt_prs J) j = Some (prs ! j, ph ! j)›
      ‹it_prs T !! j = prs ! j› ‹it_plhs T !! j = ph ! j›
      ‹drop_as (snd (prs ! j)) stk = drop (it_plen T !! j) stk› if ‹j ∈ set comps› for j
      using jc[OF that] unfolding Jf T_def L by (simp_all add: tlookup_tab_of_list drop_as_eq)
    have tg: ‹jtarget J stk (jla J v) a = itarget T stk v a› if ‹a ∈ set I› for a
    proof (cases a)
      case IShift
      show ?thesis
      proof (cases v)
        case Nil
        then show ?thesis unfolding IShift jtarget_def itarget_def jla by (simp add: pg0)
      next
        case (Cons x v')
        then show ?thesis unfolding IShift jtarget_def itarget_def jla by (simp add: pg)
      qed
    next
      case (IReduce j)
      have j: ‹j ∈ set comps› using jI that IReduce by blast
      show ?thesis unfolding IReduce jtarget_def itarget_def iact.case
        unfolding pj(1,3)[OF j] pj(4)[OF j, symmetric] option.case prod.case
        by (simp add: pn split: list.splits)
    qed
    have sp: ‹spick (jtarget J stk (jla J v)) I = spick (itarget T stk v) I›
      by (rule spick_cong) (rule tg)
    have ci: ‹(if i < IArray.length (it_cells T) then it_cells T !! i else []) = cells›
      unfolding T_def L cells_def by simp
    have pi: ‹(if i < IArray.length (it_pc T) then it_pc T !! i else []) = comps›
      unfolding T_def L comps_def by simp
    have JE: ‹jctl J (stk, v) = (case spick (jtarget J stk (jla J v)) I of
          None ⇒ None
        | Some (IShift, q) ⇒ Some (DShift, q # stk, tl v)
        | Some (IReduce j, q) ⇒ (case tlookup (jt_prs J) j of None ⇒ None | Some (pr, A) ⇒
            Some (DReduce pr, q # drop_as (snd pr) stk, v)))›
      unfolding jctl_def prod.case using Cons by (simp only: list.case prod.case Let_def cj cand)
    have IE: ‹isctl T (stk, v) = (case spick (itarget T stk v) I of
          None ⇒ None
        | Some (IShift, q) ⇒ Some (DShift, q # stk, tl v)
        | Some (IReduce j, q) ⇒
            Some (DReduce (it_prs T !! j), q # drop (it_plen T !! j) stk, v))›
      unfolding isctl_def prod.case using Cons
      by (simp only: list.case prod.case Let_def ci pi I_def)
    have ‹jctl J (stk, v) = isctl T (stk, v)›
    proof (cases ‹spick (itarget T stk v) I›)
      case None
      then show ?thesis unfolding JE IE sp by simp
    next
      case (Some r)
      obtain a q where r: ‹r = (a, q)› by (cases r)
      from spick_SomeD[OF Some[unfolded r]] have aI: ‹a ∈ set I› by blast
      show ?thesis
      proof (cases a)
        case IShift
        then show ?thesis unfolding JE IE sp Some r by simp
      next
        case (IReduce j)
        have j: ‹j ∈ set comps› using jI aI IReduce by blast
        show ?thesis unfolding JE IE sp Some r IReduce option.case prod.case iact.case
          unfolding pj(1,2)[OF j] pj(4)[OF j, symmetric] option.case prod.case ..
      qed
    qed
    then show ?thesis unfolding J_def T_def .
  qed
qed

theorem jfinal_eq: ‹jfinal (jtabs_of L) c = isfinal (itabs_of L) c›
  by (cases L; cases c) (auto simp: jfinal_def isfinal_def Let_def tlookup_tab_of_list split: list.splits)


subsection ‹Table inlining›

lemma dparse_via_trie_tables:
  assumes static: ‹sstatic G Shn›
    and st: ‹pr0_states G Shn = sts› and gt: ‹pgtab G sts = gtab›
    and rt: ‹red_buckets G Shn (length sts) = redtab›
    and pcs: ‹pcomps G sts = pc› and pfs: ‹pfins Shn sts = pf›
    and i0: ‹st_find sts (lr0_start G Shn) = i0›
    and lt: ‹mk_ltabs gtab sts redtab pc pf = L›
    and jt: ‹jtabs_of L = J›
  shows ‹dparse G Shn w = srun_hist (jctl J) (jfinal J) [] ([i0], w, [])›
proof -
  have wf: ‹lwf2 L› using lwf2_mk_ltabs lt by blast
  have c: ‹jctl (jtabs_of L) = isctl (itabs_of L)›
    by (rule ext) (simp only: split_paired_all jctl_eq[OF wf])
  have f: ‹jfinal (jtabs_of L) = isfinal (itabs_of L)› by (rule ext) (rule jfinal_eq)
  show ?thesis
    unfolding dparse_via_index_tables[OF static st gt rt pcs pfs i0 lt refl] jt[symmetric] c f ..
qed

text ‹Tree building without arithmetic on the length of the right-hand side.›

fun take_as :: ‹'a list ⇒ 'b list ⇒ 'b list› where
  ‹take_as [] _ = []›
| ‹take_as (_ # xs) [] = []›
| ‹take_as (_ # xs) (y # ys) = y # take_as xs ys›

lemma take_as_eq: ‹take_as xs ys = take (length xs) ys›
  by (induction xs ys rule: take_as.induct) auto

lemma stree_code [code]:
  ‹stree act v tstk = (case act of
      DShift ⇒ Leaf (hd v) # tstk
    | DReduce pr ⇒ Node (fst pr) (rev (take_as (snd pr) tstk)) # drop_as (snd pr) tstk)›
  by (simp add: stree_def take_as_eq drop_as_eq split: dact.split)

end