Theory LR_Int

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

theory LR_Int
  imports LR_Simple
begin

section ‹The simple driver on integer indices›

text ‹With binary naturals, converting a state index to an integer for every
  array access costs about half of a step. The tables are stored with natural
  numbers, which keeps them static data, and converted once into tables with
  integer indices; the driver then runs on a stack of integer indices.›

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

lemmas zrun_hist_simps [code] = zrun_hist.simps

text ‹const‹zrun_hist› on encoded stacks computes const‹srun_hist›, if the
  steps and final tests agree under an injective encoding of stack entries.›

locale run_transfer =
  fixes enc :: ‹nat ⇒ 'k›
    and ctl1 :: ‹('m, 'ch, 't) sctl_t ⇒ (('n, 't) dact × ('m, 'ch, 't) sctl_t) option›
    and fin1 :: ‹('m, 'ch, 't) sctl_t ⇒ bool›
    and ctl2 :: ‹'k list × ('m, 'ch, 't) tword ⇒ (('n, 't) dact × 'k list × ('m, 'ch, 't) tword) option›
    and fin2 :: ‹'k list × ('m, 'ch, 't) tword ⇒ bool›
  assumes inj: ‹inj enc›
    and ctl: ‹⋀stk v. ctl2 (map enc stk, v) =
      map_option (λ(a, stk', v'). (a, map enc stk', v')) (ctl1 (stk, v))›
    and fin: ‹⋀stk v. fin2 (map enc stk, v) = fin1 (stk, v)›
begin

lemma mem_map_enc: ‹map enc stk ∈ map enc ` set seen ⟷ stk ∈ set seen›
  using inj_mapI[OF inj] by (auto simp: inj_image_mem_iff)

lemma s_imp_z:
  assumes h: ‹srun_hist ctl1 fin1 seen st = Some t›
  shows ‹zrun_hist ctl2 fin2 (map (map enc) seen) (map enc (fst st), snd st) = Some t›
proof -
  have ‹ctl1 = ctl1 ⟶ fin1 = fin1 ⟶
      zrun_hist ctl2 fin2 (map (map enc) seen) (map enc (fst st), snd st) = Some t›
  proof (rule srun_hist.raw_induct[OF _ h, where P = ‹λctl fin seen st t. ctl = ctl1 ⟶ fin = fin1 ⟶
      zrun_hist ctl2 fin2 (map (map enc) seen) (map enc (fst st), snd st) = Some t›], goal_cases)
    case (1 f ctl fin seen st t)
    obtain stk v tstk where st: ‹st = (stk, v, tstk)› by (cases st)
    show ?case
    proof (intro impI)
      assume c: ‹ctl = ctl1› and fi: ‹fin = fin1›
      show ‹zrun_hist ctl2 fin2 (map (map enc) seen) (map enc (fst st), snd st) = Some t›
      proof (cases ‹fin1 (stk, v)›)
        case True
        with "1"(2) show ?thesis unfolding st c fi by (subst zrun_hist.simps) (simp add: fin)
      next
        case False
        from False "1"(2) have nk: ‹stk ∉ set seen› unfolding st c fi by (auto split: if_splits)
        from False "1"(2) obtain a stk' v' where
            sc: ‹ctl1 (stk, v) = Some (a, stk', v')›
          and rec: ‹f ctl fin (if a = DShift then [] else stk # seen) (stk', v', stree a v tstk) = Some t›
          unfolding st c fi by (auto simp: bind_eq_Some_conv split: if_splits)
        from "1"(1)[OF rec] c fi
        have ‹zrun_hist ctl2 fin2 (map (map enc) (if a = DShift then [] else stk # seen))
            (map enc stk', v', stree a v tstk) = Some t› by simp
        then show ?thesis unfolding st using False nk sc
          by (subst zrun_hist.simps) (cases ‹a = DShift›; simp add: fin ctl mem_map_enc)
      qed
    qed
  qed
  then show ?thesis by blast
qed

lemma z_imp_s:
  assumes h: ‹zrun_hist ctl2 fin2 seen2 st2 = Some t›
  shows ‹seen2 = map (map enc) seen ⟹ st2 = (map enc stk, v, tstk) ⟹
    srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t›
proof -
  have ‹ctl2 = ctl2 ⟶ fin2 = fin2 ⟶ (∀seen stk v tstk. seen2 = map (map enc) seen ⟶
      st2 = (map enc stk, v, tstk) ⟶ srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t)›
  proof (rule zrun_hist.raw_induct[OF _ h, where P = ‹λctl fin seen2 st2 t. ctl = ctl2 ⟶ fin = fin2 ⟶
      (∀seen stk v tstk. seen2 = map (map enc) seen ⟶
        st2 = (map enc stk, v, tstk) ⟶ srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t)›], goal_cases)
    case (1 f ctl fin seen2 st2 t)
    show ?case
    proof (intro impI allI)
      fix seen stk v tstk
      assume c: ‹ctl = ctl2› and fi: ‹fin = fin2› and se: ‹seen2 = map (map enc) seen›
        and st: ‹st2 = (map enc stk, v, tstk)›
      show ‹srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t›
      proof (cases ‹fin1 (stk, v)›)
        case True
        with "1"(2) show ?thesis unfolding st c fi by (subst srun_hist.simps) (simp add: fin)
      next
        case False
        from False "1"(2) have nk: ‹stk ∉ set seen›
          unfolding st c fi se by (auto simp: fin mem_map_enc split: if_splits)
        from False "1"(2) obtain a stk2 v' where
            sc: ‹ctl2 (map enc stk, v) = Some (a, stk2, v')›
          and rec: ‹f ctl fin (if a = DShift then [] else map enc stk # seen2) (stk2, v', stree a v tstk) = Some t›
          unfolding st c fi by (auto simp: bind_eq_Some_conv fin split: if_splits)
        from sc obtain stk' where sc1: ‹ctl1 (stk, v) = Some (a, stk', v')› and stk2: ‹stk2 = map enc stk'›
          unfolding ctl by (auto split: prod.splits)
        have ‹srun_hist ctl1 fin1 (if a = DShift then [] else stk # seen) (stk', v', stree a v tstk) = Some t›
          using "1"(1)[OF rec] c fi se stk2 by simp
        then show ?thesis using False nk sc1 by (subst srun_hist.simps) simp
      qed
    qed
  qed
  then show ‹seen2 = map (map enc) seen ⟹ st2 = (map enc stk, v, tstk) ⟹
    srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t› by blast
qed

theorem zrun_hist_eq:
  ‹zrun_hist ctl2 fin2 (map (map enc) seen) (map enc stk, v, tstk) = srun_hist ctl1 fin1 seen (stk, v, tstk)›
proof (cases ‹srun_hist ctl1 fin1 seen (stk, v, tstk)›)
  case None
  show ?thesis
  proof (cases ‹zrun_hist ctl2 fin2 (map (map enc) seen) (map enc stk, v, tstk)›)
    case (Some t)
    from z_imp_s[OF Some refl refl] None show ?thesis by simp
  qed (simp add: None)
next
  case (Some t)
  from s_imp_z[OF Some] Some show ?thesis by simp
qed

end

subsection ‹Integer tables and the integer step›

datatype ('n, 't) ztabs = ZTabs
  (zt_ns: integer)
  (zt_gtT: ‹('t × integer) list iarray›) (zt_gtN: ‹(integer × integer) list iarray›)
  (zt_cells: ‹(integer × 't option) list iarray›) (zt_pc: ‹integer list iarray›)
  (zt_prs: ‹('n × ('n, 't) rhs) iarray›) (zt_plen: ‹nat iarray›) (zt_plhs: ‹integer iarray›)
  (zt_pf: ‹bool iarray›)

abbreviation zi :: ‹nat ⇒ integer› where ‹zi ≡ integer_of_nat›

fun ztabs_of :: ‹('n, 't) ltabs ⇒ ('n, 't) ztabs› where
  ‹ztabs_of (LTabs ns gT gN cs pc prs pl ph pf) =
     ZTabs (zi ns)
       (IArray (map (map (λ(a, j). (a, zi j))) gT)) (IArray (map (map (λ(k, j). (zi k, zi j))) gN))
       (IArray (map (map (λ(j, t). (zi j, t))) cs)) (IArray (map (map zi) pc))
       (IArray prs) (IArray pl) (IArray (map zi ph)) (IArray pf)›

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

datatype zact = ZShift | ZReduce integer

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

definition zcands :: ‹integer list ⇒ (integer × 't option) list ⇒ ('m, 'ch, 't) tword ⇒ zact list› where
  ‹zcands comps cells v = (let reds = map ZReduce (filter (zlic cells v) comps)
     in (case v of [] ⇒ reds | _ ⇒ ZShift # reds))›

definition ztarget :: ‹('n, 't) ztabs ⇒ integer list ⇒ ('m, 'ch, 't) tword ⇒ zact ⇒
    integer option› where
  ‹ztarget T stk v act = (case act of
      ZShift ⇒ (case v of [] ⇒ None | x # _ ⇒
        let q = zinext (zt_gtT T) (zt_ns T) (hd stk) (tok x) in
        if q < zt_ns T then Some q else None)
    | ZReduce j ⇒ (case drop (IArray.sub' (zt_plen T, j)) stk of [] ⇒ None | i' # _ ⇒
        let q = zinext (zt_gtN T) (zt_ns T) i' (IArray.sub' (zt_plhs T, j)) in
        if q < zt_ns T then Some q else None))›

definition zctl :: ‹('n, 't) ztabs ⇒ integer list × ('m, 'ch, 't) tword ⇒
    (('n, 't) dact × integer list × ('m, 'ch, 't) tword) option› where
  ‹zctl T c = (case c of (stk, v) ⇒
     (case stk of [] ⇒ None | i # _ ⇒
       let cells = (if i < IArray.length' (zt_cells T) then IArray.sub' (zt_cells T, i) else []);
           comps = (if i < IArray.length' (zt_pc T) then IArray.sub' (zt_pc T, i) else [])
       in (case spick (ztarget T stk v) (zcands comps cells v) of
            None ⇒ None
          | Some (ZShift, q) ⇒ Some (DShift, q # stk, tl v)
          | Some (ZReduce j, q) ⇒
              Some (DReduce (IArray.sub' (zt_prs T, j)),
                q # drop (IArray.sub' (zt_plen T, j)) stk, v))))›

definition zfinal :: ‹('n, 't) ztabs ⇒ integer list × ('m, 'ch, 't) tword ⇒ bool› where
  ‹zfinal T c ⟷ (case c of (stk, v) ⇒ v = [] ∧
     (case stk of [] ⇒ False | i # _ ⇒ i < IArray.length' (zt_pf T) ∧ IArray.sub' (zt_pf T, i)))›

subsection ‹Correctness of the integer step›

lemma zi_inj: ‹inj zi›
  by (metis injI nat_of_integer_integer_of_nat)

lemma zi_eq [simp]: ‹zi a = zi b ⟷ a = b›
  using zi_inj by (simp add: inj_eq)

lemma zi_less [simp]: ‹zi a < zi b ⟷ a < b›
  by (simp add: integer_of_nat_eq_of_nat)

lemma zi_min: ‹min (zi a) (zi b) = zi (min a b)›
  by (simp add: min_def integer_of_nat_eq_of_nat)

lemma sub'_IArray [simp]: ‹IArray.sub' (IArray xs, zi i) = xs ! i›
  by simp

lemma length'_IArray [simp]: ‹IArray.length' (IArray xs) = zi (length xs)›
  by simp

lemma map_of_map_snd: ‹map_of (map (λ(a, j). (a, f j)) row) a = map_option f (map_of row a)›
  by (induction row) auto

lemma map_of_map_zi:
  ‹map_of (map (λ(k, j). (zi k, zi j)) row) (zi k) = map_option zi (map_of row k)›
  by (induction row) auto

lemma zinext_inext:
  assumes ‹⋀row. row ∈ set tab ⟹ map_of (f row) k' = map_option zi (map_of row k)›
  shows ‹zinext (IArray (map f tab)) (zi n) (zi i) k' = zi (inext (IArray tab) n i k)›
  using assms[of ‹tab ! i›]
  by (auto simp: zinext_def inext_def zi_min split: option.splits)

primrec zact_of :: ‹iact ⇒ zact› where
  ‹zact_of IShift = ZShift›
| ‹zact_of (IReduce j) = ZReduce (zi j)›

lemma zlic_ilic: ‹zlic (map (λ(j, t). (zi j, t)) cells) v (zi j) = ilic cells v j›
  unfolding zlic_def ilic_def by (induction cells) auto

lemma zcands_icands:
  ‹zcands (map zi comps) (map (λ(j, t). (zi j, t)) cells) v = map zact_of (icands comps cells v)›
proof -
  have ‹filter (zlic (map (λ(j, t). (zi j, t)) cells) v) (map zi comps) =
      map zi (filter (ilic cells v) comps)›
    by (simp add: filter_map comp_def zlic_ilic)
  then show ?thesis unfolding zcands_def icands_def Let_def
    by (cases v) (simp_all add: comp_def)
qed

lemma spick_map_option:
  ‹spick (λx. map_option h (f x)) xs = map_option (λ(a, b). (a, h b)) (spick f xs)›
  by (induction xs) (auto split: option.splits)

text ‹Every production number offered as a reduce indexes the table of
  left-hand sides.›

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

lemma ztarget_itarget:
  assumes L: ‹L = LTabs ns gT gN cs pc prs pl ph pf›
    and ne: ‹stk ≠ []› and j: ‹⋀j. a = IReduce j ⟹ j < length ph›
  shows ‹ztarget (ztabs_of L) (map zi stk) v (zact_of a) =
    map_option zi (itarget (itabs_of L) stk v a)›
proof (cases a)
  case IShift
  have hd: ‹hd (map zi stk) = zi (hd stk)› using ne by (cases stk) auto
  have n: ‹zinext (IArray (map (map (λ(a, j). (a, zi j))) gT)) (zi ns) (zi i) k =
      zi (inext (IArray gT) ns i k)› for i k
    by (rule zinext_inext) (rule map_of_map_snd)
  show ?thesis unfolding IShift L ztarget_def itarget_def
    by (cases v) (simp_all add: hd n Let_def)
next
  case (IReduce j')
  have jl: ‹j' < length ph› using j IReduce by blast
  have n: ‹zinext (IArray (map (map (λ(k, j). (zi k, zi j))) gN)) (zi ns) (zi i) (zi k) =
      zi (inext (IArray gN) ns i k)› for i k
    by (rule zinext_inext) (rule map_of_map_zi)
  show ?thesis
  proof (cases ‹drop (pl ! j') stk›)
    case Nil
    then show ?thesis unfolding IReduce L ztarget_def itarget_def by (simp add: drop_map)
  next
    case (Cons i' rest)
    show ?thesis unfolding IReduce L ztarget_def itarget_def
      using jl Cons by (simp add: drop_map n Let_def)
  qed
qed

theorem zctl_eq:
  assumes wf: ‹lwf L›
  shows ‹zctl (ztabs_of L) (map zi stk, v) =
    map_option (λ(a, stk', v'). (a, map zi 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)
  show ?thesis
  proof (cases stk)
    case Nil
    then show ?thesis unfolding zctl_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 ph› if ‹j ∈ set comps› for j
      using that wf unfolding L comps_def by (auto split: if_splits)
    have jI: ‹j < length ph› if ‹IReduce j ∈ set I› for j
      using that jc unfolding I_def icands_def Let_def by (cases v) auto
    have tg: ‹ztarget (ztabs_of L) (map zi stk) v (zact_of a) =
        map_option zi (itarget (itabs_of L) stk v a)› if ‹a ∈ set I› for a
      by (rule ztarget_itarget[OF L]) (use Cons jI that in auto)
    have sp: ‹spick (ztarget (ztabs_of L) (map zi stk) v) (map zact_of I) =
        map_option (λ(a, b). (zact_of a, zi b)) (spick (itarget (itabs_of L) stk v) I)›
    proof -
      have 1: ‹spick (ztarget (ztabs_of L) (map zi stk) v) (map zact_of I) =
          map_option (λ(a, b). (zact_of a, b))
            (spick (λx. ztarget (ztabs_of L) (map zi stk) v (zact_of x)) I)›
        by (simp add: spick_map comp_def)
      have 2: ‹spick (λx. ztarget (ztabs_of L) (map zi stk) v (zact_of x)) I =
          spick (λx. map_option zi (itarget (itabs_of L) stk v x)) I›
        by (rule spick_cong) (rule tg)
      show ?thesis unfolding 1 2 spick_map_option
        by (cases ‹spick (itarget (itabs_of L) stk v) I›) auto
    qed
    have cz: ‹(if zi i < IArray.length' (zt_cells (ztabs_of L))
        then IArray.sub' (zt_cells (ztabs_of L), zi i) else []) = map (λ(j, t). (zi j, t)) cells›
      by (simp add: L cells_def)
    have pz: ‹(if zi i < IArray.length' (zt_pc (ztabs_of L))
        then IArray.sub' (zt_pc (ztabs_of L), zi i) else []) = map zi comps›
      by (simp add: L comps_def)
    have ci: ‹(if i < IArray.length (it_cells (itabs_of L))
        then it_cells (itabs_of L) !! i else []) = cells›
      by (simp add: L cells_def)
    have pi: ‹(if i < IArray.length (it_pc (itabs_of L))
        then it_pc (itabs_of L) !! i else []) = comps›
      by (simp add: L comps_def)
    have zc: ‹zcands (map zi comps) (map (λ(j, t). (zi j, t)) cells) v = map zact_of I›
      unfolding I_def by (rule zcands_icands)
    show ?thesis
    proof (cases ‹spick (itarget (itabs_of L) stk v) I›)
      case None
      show ?thesis unfolding zctl_def isctl_def Cons
        using None sp cz pz ci pi zc I_def Cons by (simp add: Let_def)
    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
      have sp': ‹spick (ztarget (ztabs_of L) (zi i # map zi rest) v) (map zact_of I) =
          map_option (λ(a, b). (zact_of a, zi b)) (spick (itarget (itabs_of L) (i # rest) v) I)›
        using sp unfolding Cons by simp
      have fl: ‹IArray.sub' (zt_plen (ztabs_of L), zi j) = it_plen (itabs_of L) !! j›
        ‹IArray.sub' (zt_prs (ztabs_of L), zi j) = it_prs (itabs_of L) !! j› for j
        unfolding L by simp_all
      show ?thesis
      proof (cases a)
        case IShift
        have Some': ‹spick (itarget (itabs_of L) (i # rest) v) I = Some (IShift, q)›
          using Some r IShift unfolding Cons by simp
        show ?thesis unfolding zctl_def isctl_def Cons
          by (simp only: list.map prod.case list.case Let_def cz pz ci pi zc I_def[symmetric] sp'
              Some' option.map option.case zact_of.simps zact.case iact.case)
      next
        case (IReduce j)
        have Some': ‹spick (itarget (itabs_of L) (i # rest) v) I = Some (IReduce j, q)›
          using Some r IReduce unfolding Cons by simp
        have dm: ‹map zi (drop (it_plen (itabs_of L) !! j) (i # rest)) =
            drop (it_plen (itabs_of L) !! j) (zi i # map zi rest)›
          using drop_map[of ‹it_plen (itabs_of L) !! j› zi ‹i # rest›] by simp
        show ?thesis unfolding zctl_def isctl_def Cons
          by (simp only: list.map prod.case list.case Let_def cz pz ci pi zc I_def[symmetric] sp'
              Some' option.map option.case zact_of.simps zact.case iact.case fl dm[symmetric])
      qed
    qed
  qed
qed

lemma zfinal_eq: ‹zfinal (ztabs_of L) (map zi stk, v) = isfinal (itabs_of L) (stk, v)›
  by (cases L; cases stk) (auto simp: zfinal_def isfinal_def)

lemma lwf_mk_ltabs: ‹lwf (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

theorem zrun_eq:
  assumes ‹lwf L›
  shows ‹zrun_hist (zctl (ztabs_of L)) (zfinal (ztabs_of L)) [] ([zi i0], w, []) =
     srun_hist (isctl (itabs_of L)) (isfinal (itabs_of L)) [] ([i0], w, [])›
proof -
  interpret run_transfer zi ‹isctl (itabs_of L)› ‹isfinal (itabs_of L)›
    ‹zctl (ztabs_of L)› ‹zfinal (ztabs_of L)›
    by (rule run_transfer.intro) (rule zi_inj, rule zctl_eq[OF assms], rule zfinal_eq)
  show ?thesis using zrun_hist_eq[of ‹[]› ‹[i0]›] by simp
qed

subsection ‹Table inlining›

lemma dparse_via_int_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 zt: ‹ztabs_of L = Z›
  shows ‹dparse G Shn w = zrun_hist (zctl Z) (zfinal Z) [] ([zi i0], w, [])›
proof -
  have ‹lwf L› using lwf_mk_ltabs lt by blast
  then show ?thesis
    unfolding dparse_via_index_tables[OF static st gt rt pcs pfs i0 lt refl] zt[symmetric]
    by (rule zrun_eq[symmetric])
qed

end