Theory LR_Prod

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

theory LR_Prod
  imports LR_Tok
begin

section ‹Candidate tables›

text ‹The trie step filters the completed productions of a state by its
  lookahead cell at every step. Here the filtered lists are computed once, per
  state and lookahead, and the driver reads its reduce candidates off that
  table: the reduce function ‹Reduce› of an LR automaton
  cite‹‹Sect.~2.2› in "deremer1982-lalr-lookahead"›.›

subsection ‹Maps and entries of tries›

fun mapk_num :: ‹(num ⇒ 'a ⇒ 'b option) ⇒ 'a ntrie ⇒ 'b ntrie› where
  ‹mapk_num g NTip = NTip›
| ‹mapk_num g (NNode x l r) = NNode (Option.bind x (g num.One))
     (mapk_num (λk. g (num.Bit0 k)) l) (mapk_num (λk. g (num.Bit1 k)) r)›

lemma lookup_mapk_num: ‹lookup_num (mapk_num g t) k = Option.bind (lookup_num t k) (g k)›
proof (induction t arbitrary: g k)
  case (NNode x l r)
  then show ?case by (cases k) auto
qed simp

definition tab_mapk :: ‹(nat ⇒ 'a ⇒ 'b option) ⇒ 'a ntab ⇒ 'b ntab› where
  ‹tab_mapk f t = (case t of NTab z tr ⇒
     NTab (Option.bind z (f 0)) (mapk_num (λk. f (nat_of_num k)) tr))›

lemma tlookup_tab_mapk: ‹tlookup (tab_mapk f t) n = Option.bind (tlookup t n) (f n)›
proof (cases t)
  case (NTab z tr)
  show ?thesis
  proof (cases ‹n = 0›)
    case False
    then have n: ‹nat_of_num (num_of_nat n) = n› using num_of_nat_inverse by simp
    show ?thesis using False unfolding NTab tab_mapk_def tlookup_def
      by (simp add: lookup_mapk_num n)
  qed (simp add: NTab tab_mapk_def tlookup_def)
qed

fun entries_num :: ‹(num ⇒ nat) ⇒ 'a ntrie ⇒ (nat × 'a) list› where
  ‹entries_num f NTip = []›
| ‹entries_num f (NNode x l r) = (case x of None ⇒ [] | Some a ⇒ [(f num.One, a)]) @
     entries_num (λk. f (num.Bit0 k)) l @ entries_num (λk. f (num.Bit1 k)) r›

lemma entries_num_complete:
  ‹lookup_num t k = Some a ⟹ (f k, a) ∈ set (entries_num f t)›
proof (induction t arbitrary: f k)
  case (NNode x l r)
  show ?case
  proof (cases k)
    case (Bit0 k')
    then show ?thesis using NNode.prems NNode.IH(1)[of k' ‹λk. f (num.Bit0 k)›] by simp
  next
    case (Bit1 k')
    then show ?thesis using NNode.prems NNode.IH(2)[of k' ‹λk. f (num.Bit1 k)›] by simp
  qed (use NNode.prems in simp)
qed simp

definition tentries :: ‹'a ntab ⇒ (nat × 'a) list› where
  ‹tentries t = (case t of NTab z tr ⇒
     (case z of None ⇒ [] | Some a ⇒ [(0, a)]) @ entries_num nat_of_num tr)›

lemma tentries_complete: ‹tlookup t n = Some a ⟹ (n, a) ∈ set (tentries t)›
proof (cases t)
  case (NTab z tr)
  assume h: ‹tlookup t n = Some a›
  show ?thesis
  proof (cases ‹n = 0›)
    case False
    then have n: ‹nat_of_num (num_of_nat n) = n› using num_of_nat_inverse by simp
    from h False have ‹lookup_num tr (num_of_nat n) = Some a› unfolding NTab tlookup_def by simp
    from entries_num_complete[OF this, of nat_of_num] show ?thesis
      unfolding NTab tentries_def n by simp
  qed (use h in ‹simp add: NTab tentries_def tlookup_def›)
qed

definition trow :: ‹'a ntab ntab ⇒ nat ⇒ 'a ntab› where
  ‹trow t i = (case tlookup t i of None ⇒ NTab None NTip | Some r ⇒ r)›

lemma jget_trow: ‹jget t i k = tlookup (trow t i) k›
  unfolding jget_def trow_def tlookup_def by (simp split: option.splits)

subsection ‹The candidate tables and their step›

datatype ('n, 't) ktabs = KTabs
  (kt_lal: ‹('t × nat) list›) (kt_miss: nat)
  (kt_T: ‹nat ntab ntab›) (kt_N: ‹nat ntab ntab›) (kt_C: ‹nat list ntab ntab›)
  (kt_prs: ‹(('n × ('n, 't) rhs) × nat) ntab›) (kt_pf: ‹bool ntab›)

definition jcomps :: ‹('n, 't) jtabs ⇒ nat ⇒ nat list› where
  ‹jcomps J i = (case tlookup (jt_pc J) i of None ⇒ [] | Some cs ⇒ cs)›

definition ktabs_of :: ‹('n, 't) jtabs ⇒ ('n, 't) ktabs› where
  ‹ktabs_of J = KTabs (jt_lal J) (jt_miss J) (jt_gT J) (jt_gN J)
     (tab_mapk (λi lics. Some (tab_mapk
        (λl t. Some (filter (λj. tlookup t j ≠ None) (jcomps J i))) lics)) (jt_lic J))
     (jt_prs J) (jt_pf J)›

text ‹The input token with its number, as const‹jenc›.›

definition kenc :: ‹('n, 't) ktabs ⇒ ('t, 'ch, 'm) token_scheme ⇒
    ('t, 'ch, 'm) token_scheme × nat› where
  ‹kenc K x = (x, case map_of (kt_lal K) (tok x) of Some l ⇒ l | None ⇒ kt_miss K)›

lemma kenc_ktabs_of: ‹kenc (ktabs_of J) = jenc J›
  by (simp add: fun_eq_iff kenc_def jenc_def jla_def ktabs_of_def split: option.split)

definition kcands :: ‹('n, 't) ktabs ⇒ nat ⇒ nat ⇒ nat list› where
  ‹kcands K k l = (case jget (kt_C K) k l of None ⇒ [] | Some cs ⇒ cs)›

definition ktarget :: ‹('n, 't) ktabs ⇒ nat list ⇒ nat ⇒ iact ⇒
    (('n, 't) dact × nat list) option› where
  ‹ktarget K kstk l act = (case act of
      IShift ⇒ (case kstk of [] ⇒ None
        | k # _ ⇒ map_option (λk'. (DShift, k' # kstk)) (jget (kt_T K) k l))
    | IReduce j ⇒ (case tlookup (kt_prs K) j of None ⇒ None | Some (pr, A) ⇒
        (case drop_as (snd pr) kstk of [] ⇒ None | k'' # rest ⇒
           map_option (λk'. (DReduce pr, k' # k'' # rest)) (jget (kt_N K) k'' A))))›

definition kctl :: ‹('n, 't) ktabs ⇒ nat list × (('t, 'ch, 'm) token_scheme × nat) list ⇒
    (('n, 't) dact × nat list × (('t, 'ch, 'm) token_scheme × nat) list) option› where
  ‹kctl K c = (case c of (kstk, v) ⇒
     (case kstk of [] ⇒ None | k # _ ⇒
       let l = (case v of [] ⇒ 0 | (_, l) # _ ⇒ l);
           cands = (case v of [] ⇒ [] | _ ⇒ [IShift]) @ map IReduce (kcands K k l)
       in (case spick (ktarget K kstk l) cands of
            None ⇒ None
          | Some (_, a, stk') ⇒ Some (a, stk', (case a of DShift ⇒ tl v | DReduce _ ⇒ v)))))›

definition kfinal :: ‹('n, 't) ktabs ⇒ nat list × (('t, 'ch, 'm) token_scheme × nat) list ⇒
    bool› where
  ‹kfinal K c ⟷ (case c of (kstk, v) ⇒ v = [] ∧
     (case kstk of [] ⇒ False | k # _ ⇒ tlookup (kt_pf K) k = Some True))›

subsection ‹Correctness of the step on candidate tables›

lemma spick_map:
  assumes ‹⋀a. a ∈ set xs ⟹ g a = map_option (h a) (f a)›
  shows ‹spick g xs = map_option (λ(a, b). (a, h a b)) (spick f xs)›
  using assms by (induction xs) (auto split: option.splits)

lemma jlicd_simps: ‹jlicd None = (λ_. False)› ‹jlicd (Some t) = (λj. tlookup t j ≠ None)›
  by (simp_all add: fun_eq_iff jlicd_def)

lemma kt_rows:
  ‹kt_T (ktabs_of J) = jt_gT J› ‹kt_N (ktabs_of J) = jt_gN J›
  ‹kt_prs (ktabs_of J) = jt_prs J› ‹kt_pf (ktabs_of J) = jt_pf J›
  by (simp_all add: ktabs_of_def)

lemma kcands_row:
  ‹kcands (ktabs_of J) i l = filter (jlicd (jget (jt_lic J) i l)) (jcomps J i)›
proof -
  have row: ‹jget (kt_C (ktabs_of J)) i l =
      Option.bind (jget (jt_lic J) i l) (λt. Some (filter (λj. tlookup t j ≠ None) (jcomps J i)))›
    by (simp add: ktabs_of_def jget_def tlookup_tab_mapk split: option.splits)
  show ?thesis by (cases ‹jget (jt_lic J) i l›) (simp_all add: kcands_def row jlicd_simps)
qed

lemma kfinal_eq: ‹kfinal (ktabs_of J) (stk, v) = jfinal2 J (stk, v)›
  by (cases stk) (auto simp: kfinal_def jfinal2_def kt_rows)

lemma ktarget_eq:
  assumes s: ‹stk = i # rest›
  shows ‹ktarget (ktabs_of J) stk l act = map_option (λq. case act of
      IShift ⇒ (DShift, q # stk)
    | IReduce j ⇒ (case tlookup (jt_prs J) j of None ⇒ (DShift, []) | Some (pr, A) ⇒
        (DReduce pr, q # drop_as (snd pr) stk)))
    (jtarget J stk l act)›
proof (cases act)
  case IShift
  show ?thesis unfolding IShift s by (simp add: ktarget_def jtarget_def kt_rows)
next
  case (IReduce j)
  show ?thesis
  proof (cases ‹tlookup (jt_prs J) j›)
    case (Some prA)
    obtain pr A where prA: ‹prA = (pr, A)› by (cases prA)
    show ?thesis
    proof (cases ‹drop_as (snd pr) stk›)
      case (Cons i' rest')
      show ?thesis using Some Cons unfolding IReduce prA
        by (simp add: ktarget_def jtarget_def kt_rows option.map_comp o_def)
    qed (use Some prA IReduce in ‹simp add: ktarget_def jtarget_def kt_rows›)
  qed (use IReduce in ‹simp add: ktarget_def jtarget_def kt_rows›)
qed

theorem kctl_eq: ‹kctl (ktabs_of J) (stk, v) = jctl2 J (stk, v)›
proof (cases stk)
  case (Cons i rest)
  define l where ‹l = (case v of [] ⇒ 0 | (_, l) # _ ⇒ l)›
  define cands where ‹cands = (case v of [] ⇒ [] | _ ⇒ [IShift]) @
    map IReduce (filter (jlicd (jget (jt_lic J) i l)) (jcomps J i))›
  define h where ‹h = (λact q. case act of
      IShift ⇒ (DShift, q # stk)
    | IReduce j ⇒ (case tlookup (jt_prs J) j of None ⇒ (DShift, []) | Some (pr, A) ⇒
        (DReduce pr, q # drop_as (snd pr) stk)))›
  have sp: ‹spick (ktarget (ktabs_of J) stk l) cands =
      map_option (λ(a, b). (a, h a b)) (spick (jtarget J stk l) cands)›
    by (rule spick_map) (use ktarget_eq[OF Cons] in ‹simp add: h_def›)
  have k: ‹kctl (ktabs_of J) (stk, v) =
      (case spick (ktarget (ktabs_of J) stk l) cands of None ⇒ None
        | Some (_, a, stk') ⇒ Some (a, stk', (case a of DShift ⇒ tl v | DReduce _ ⇒ v)))›
    unfolding kctl_def Cons l_def cands_def by (simp add: Let_def kcands_row)
  have j: ‹jctl2 J (stk, v) = (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)))›
    unfolding jctl2_def Cons l_def cands_def jcomps_def by (simp add: Let_def)
  show ?thesis
  proof (cases ‹spick (jtarget J stk l) cands›)
    case (Some aq)
    obtain act q where aq: ‹aq = (act, q)› by (cases aq)
    have tq: ‹jtarget J stk l act = Some q› using spick_SomeD[OF Some[unfolded aq]] by simp
    show ?thesis
    proof (cases act)
      case (IReduce j)
      from tq obtain pr A where prA: ‹tlookup (jt_prs J) j = Some (pr, A)›
        unfolding IReduce jtarget_def by (auto split: option.splits list.splits)
      show ?thesis unfolding k j sp Some aq IReduce using prA by (simp add: h_def)
    qed (simp add: k j sp Some aq h_def)
  qed (simp add: k j sp)
qed (simp add: kctl_def jctl2_def)

lemma kctl_eq_fun: ‹kctl (ktabs_of J) = jctl2 J›
  by (rule ext) (simp only: split_paired_all kctl_eq)

lemma kfinal_eq_fun: ‹kfinal (ktabs_of J) = jfinal2 J›
  by (rule ext) (simp only: split_paired_all kfinal_eq)

theorem xrun_kctl:
  ‹xrun_hist (kctl (ktabs_of J)) (kfinal (ktabs_of J)) fst seen (stk, v, tstk) =
    xrun_hist (jctl2 J) (jfinal2 J) fst seen (stk, v, tstk)›
  unfolding kctl_eq_fun kfinal_eq_fun ..

subsection ‹The code equation›

lemma dparse_via_prod_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›
    and kt: ‹ktabs_of J = K›
  shows ‹dparse G Shn w = xrun_hist (kctl K) (kfinal K) fst [] ([i0], map (kenc K) w, [])›
  unfolding dparse_via_trie_tok_tables[OF static st gt rt pcs pfs i0 lt jt]
    xrun_kctl[symmetric] kt[symmetric] kenc_ktabs_of ..

end