Theory LR_Loop

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

theory LR_Loop
  imports LR_Prod
begin

section ‹A cheaper loop check›

text ‹const‹xrun_hist› stops a run that revisits a stack between two shifts,
  by comparing the stack with all stacks since the last shift. The check only
  matters for the termination of the code: between shifts the input does not
  change, so a revisit means that the run loops (reduces of unit and empty
  productions do not shrink the stack cite‹‹Sect.~2.5› in "jourdan2012-validating-lr1"›), and its result is ‹None› as
  the run without a check (‹nrun›). Any check that fires only on a
  revisit gives the same result. ‹brun› keeps one stack of the
  current segment and compares only with it, saving the current stack after 1,
  2, 4, ‹…› steps (Brent's cycle detection
  cite‹"brent1980-monte-carlo-factorization"›), which finds every cycle.›

partial_function (option) nrun ::
  ‹('k list × 'w list ⇒ (('n, 't) dact × 'k list × 'w list) option) ⇒
    ('k list × 'w list ⇒ bool) ⇒ ('w ⇒ ('t, 'ch, 'm) token_scheme) ⇒
    'k list × 'w list × ('m, 'ch, 'n, 't) ast list ⇒ ('m, 'ch, 'n, 't) ast option›
  where
  ‹nrun ctl fin dec st = (case st of (stk, v, tstk) ⇒
     if fin (stk, v) then sresult tstk
     else Option.bind (ctl (stk, v)) (λ(act, stk', v').
       nrun ctl fin dec (stk', v', xtree dec act v tstk)))›

definition bupd :: ‹'k list option × nat × nat ⇒ 'k list ⇒ 'k list option × nat × nat› where
  ‹bupd d stk = (case d of (sv, c, p) ⇒ if c = p then (Some stk, 1, 2 * p) else (sv, c + 1, p))›

partial_function (option) brun ::
  ‹('k list × 'w list ⇒ (('n, 't) dact × 'k list × 'w list) option) ⇒
    ('k list × 'w list ⇒ bool) ⇒ ('w ⇒ ('t, 'ch, 'm) token_scheme) ⇒
    'k list option × nat × nat ⇒
    'k list × 'w list × ('m, 'ch, 'n, 't) ast list ⇒ ('m, 'ch, 'n, 't) ast option›
  where
  ‹brun ctl fin dec d st = (case st of (stk, v, tstk) ⇒
     if fin (stk, v) then sresult tstk
     else if fst d = Some stk then None
     else Option.bind (ctl (stk, v)) (λ(act, stk', v').
       brun ctl fin dec (if act = DShift then (None, 1, 1) else bupd d stk)
         (stk', v', xtree dec act v tstk)))›

lemmas brun_simps [code] = brun.simps

definition cstep :: ‹('k list × 'w list ⇒ (('n, 't) dact × 'k list × 'w list) option) ⇒
    ('k list × 'w list ⇒ bool) ⇒ 'k list × 'w list ⇒ 'k list × 'w list ⇒ bool› where
  ‹cstep ctl fin c c' ⟷ ¬ fin c ∧ (∃a. ctl c = Some (a, c'))›

context
  fixes ctl :: ‹'k list × 'w list ⇒ (('n, 't) dact × 'k list × 'w list) option›
    and fin :: ‹'k list × 'w list ⇒ bool›
    and dec :: ‹'w ⇒ ('t, 'ch, 'm) token_scheme›
  assumes keep: ‹⋀stk v a stk' v'. ctl (stk, v) = Some (a, stk', v') ⟹ a ≠ DShift ⟹ v' = v›
begin

abbreviation ctl_step where ‹ctl_step ≡ cstep ctl fin›

lemma nocycle:
  assumes h: ‹nrun ctl fin dec st = Some t›
  shows ‹ctl_step** (fst st, fst (snd st)) c' ⟹ ¬ ctl_step++ c' c'›
proof -
  have ‹ctl = ctl ⟶ fin = fin ⟶ (∀c'. ctl_step** (fst st, fst (snd st)) c' ⟶ ¬ ctl_step++ c' c')›
  proof (rule nrun.raw_induct[OF _ h, where P = ‹λctl' fin' dec' st t. ctl' = ctl ⟶ fin' = fin ⟶
      (∀c'. ctl_step** (fst st, fst (snd st)) c' ⟶ ¬ ctl_step++ c' c')›], goal_cases)
    case (1 f ctl' fin' dec' st t)
    obtain stk v ts where st: ‹st = (stk, v, ts)› by (cases st)
    show ?case
    proof (intro impI allI notI)
      fix c'
      assume c: ‹ctl' = ctl› and fi: ‹fin' = fin› and r: ‹ctl_step** (fst st, fst (snd st)) c'›
        and cyc: ‹ctl_step++ c' c'›
      have ‹ctl_step++ (stk, v) c'› using rtranclp_tranclp_tranclp[OF r cyc] unfolding st by simp
      then obtain c1 where s1: ‹ctl_step (stk, v) c1› and r1: ‹ctl_step** c1 c'›
        by (auto dest: tranclpD)
      from s1 obtain a where nf: ‹¬ fin (stk, v)› and sc: ‹ctl (stk, v) = Some (a, c1)›
        unfolding cstep_def by blast
      obtain stk1 v1 where c1: ‹c1 = (stk1, v1)› by (cases c1)
      from "1"(2) nf sc have rec: ‹f ctl' fin' dec' (stk1, v1, xtree dec' a v ts) = Some t›
        unfolding st c fi c1 by (auto simp: bind_eq_Some_conv)
      have ‹∀c'. ctl_step** (stk1, v1) c' ⟶ ¬ ctl_step++ c' c'› using "1"(1)[OF rec] c fi by simp
      then show False using r1 cyc unfolding c1 by blast
    qed
  qed
  then show ‹ctl_step** (fst st, fst (snd st)) c' ⟹ ¬ ctl_step++ c' c'› by blast
qed

lemma x_imp_n:
  assumes h: ‹xrun_hist ctl fin dec seen st = Some t›
  shows ‹nrun ctl fin dec st = Some t›
proof -
  have ‹ctl = ctl ⟶ fin = fin ⟶ dec = dec ⟶ nrun ctl fin dec st = Some t›
  proof (rule xrun_hist.raw_induct[OF _ h, where P = ‹λctl' fin' dec' seen st t. ctl' = ctl ⟶
      fin' = fin ⟶ dec' = dec ⟶ nrun ctl fin dec st = Some t›], goal_cases)
    case (1 f ctl' fin' dec' seen st t)
    obtain stk v ts where st: ‹st = (stk, v, ts)› by (cases st)
    show ?case
    proof (intro impI)
      assume c: ‹ctl' = ctl› and fi: ‹fin' = fin› and d: ‹dec' = dec›
      show ‹nrun ctl fin dec st = Some t›
      proof (cases ‹fin (stk, v)›)
        case True
        with "1"(2) show ?thesis unfolding st c fi by (subst nrun.simps) simp
      next
        case False
        from False "1"(2) obtain a stk' v' where
            sc: ‹ctl (stk, v) = Some (a, stk', v')›
          and rec: ‹f ctl' fin' dec' (if a = DShift then [] else stk # seen) (stk', v', xtree dec' a v ts) = Some t›
          unfolding st c fi by (auto simp: bind_eq_Some_conv split: if_splits)
        from "1"(1)[OF rec] c fi d have ‹nrun ctl fin dec (stk', v', xtree dec a v ts) = Some t› by simp
        then show ?thesis unfolding st using False sc by (subst nrun.simps) simp
      qed
    qed
  qed
  then show ?thesis by blast
qed

lemma n_imp_x:
  assumes h: ‹nrun ctl fin dec st = Some t›
  shows ‹(∀c'. ctl_step** (fst st, fst (snd st)) c' ⟶ ¬ ctl_step++ c' c') ⟹
    ∀s ∈ set seen. ctl_step++ (s, fst (snd st)) (fst st, fst (snd st)) ⟹
    xrun_hist ctl fin dec seen st = Some t›
proof -
  have ‹ctl = ctl ⟶ fin = fin ⟶ dec = dec ⟶ (∀c'. ctl_step** (fst st, fst (snd st)) c' ⟶ ¬ ctl_step++ c' c') ⟶
      (∀seen. (∀s ∈ set seen. ctl_step++ (s, fst (snd st)) (fst st, fst (snd st))) ⟶
        xrun_hist ctl fin dec seen st = Some t)›
  proof (rule nrun.raw_induct[OF _ h, where P = ‹λctl' fin' dec' st t. ctl' = ctl ⟶ fin' = fin ⟶
      dec' = dec ⟶ (∀c'. ctl_step** (fst st, fst (snd st)) c' ⟶ ¬ ctl_step++ c' c') ⟶
      (∀seen. (∀s ∈ set seen. ctl_step++ (s, fst (snd st)) (fst st, fst (snd st))) ⟶
        xrun_hist ctl fin dec seen st = Some t)›], goal_cases)
    case (1 f ctl' fin' dec' st t)
    obtain stk v ts where st: ‹st = (stk, v, ts)› by (cases st)
    show ?case
    proof (intro impI allI)
      fix seen
      assume c: ‹ctl' = ctl› and fi: ‹fin' = fin› and d: ‹dec' = dec›
        and nc: ‹∀c'. ctl_step** (fst st, fst (snd st)) c' ⟶ ¬ ctl_step++ c' c'›
        and inv: ‹∀s ∈ set seen. ctl_step++ (s, fst (snd st)) (fst st, fst (snd st))›
      show ‹xrun_hist ctl fin dec seen st = Some t›
      proof (cases ‹fin (stk, v)›)
        case True
        with "1"(2) show ?thesis unfolding st c fi by (subst xrun_hist.simps) simp
      next
        case False
        have ns: ‹stk ∉ set seen›
        proof
          assume ‹stk ∈ set seen›
          with inv have ‹ctl_step++ (stk, v) (stk, v)› unfolding st by auto
          with nc show False unfolding st by auto
        qed
        from False "1"(2) obtain a stk' v' where
            sc: ‹ctl (stk, v) = Some (a, stk', v')›
          and rec: ‹f ctl' fin' dec' (stk', v', xtree dec' a v ts) = Some t›
          unfolding st c fi by (auto simp: bind_eq_Some_conv)
        have s1: ‹ctl_step (stk, v) (stk', v')› using False sc unfolding cstep_def by blast
        have nc': ‹∀c'. ctl_step** (stk', v') c' ⟶ ¬ ctl_step++ c' c'›
          using nc s1 unfolding st by (auto intro: converse_rtranclp_into_rtranclp)
        have inv': ‹∀s ∈ set (if a = DShift then [] else stk # seen). ctl_step++ (s, v') (stk', v')›
        proof (cases ‹a = DShift›)
          case False
          then have v': ‹v' = v› using keep[OF sc] by blast
          show ?thesis using False inv s1 unfolding st v' by (auto intro: tranclp.trancl_into_trancl)
        qed simp
        from "1"(1)[OF rec] c fi d nc' inv'
        have ‹xrun_hist ctl fin dec (if a = DShift then [] else stk # seen) (stk', v', xtree dec a v ts) = Some t›
          by simp
        then show ?thesis unfolding st using False ns sc by (subst xrun_hist.simps) simp
      qed
    qed
  qed
  then show ‹(∀c'. ctl_step** (fst st, fst (snd st)) c' ⟶ ¬ ctl_step++ c' c') ⟹
    ∀s ∈ set seen. ctl_step++ (s, fst (snd st)) (fst st, fst (snd st)) ⟹
    xrun_hist ctl fin dec seen st = Some t› by blast
qed

lemma b_imp_n:
  assumes h: ‹brun ctl fin dec d st = Some t›
  shows ‹nrun ctl fin dec st = Some t›
proof -
  have ‹ctl = ctl ⟶ fin = fin ⟶ dec = dec ⟶ nrun ctl fin dec st = Some t›
  proof (rule brun.raw_induct[OF _ h, where P = ‹λctl' fin' dec' d st t. ctl' = ctl ⟶
      fin' = fin ⟶ dec' = dec ⟶ nrun ctl fin dec st = Some t›], goal_cases)
    case (1 f ctl' fin' dec' d st t)
    obtain stk v ts where st: ‹st = (stk, v, ts)› by (cases st)
    show ?case
    proof (intro impI)
      assume c: ‹ctl' = ctl› and fi: ‹fin' = fin› and dd: ‹dec' = dec›
      show ‹nrun ctl fin dec st = Some t›
      proof (cases ‹fin (stk, v)›)
        case True
        with "1"(2) show ?thesis unfolding st c fi by (subst nrun.simps) simp
      next
        case False
        from False "1"(2) obtain a stk' v' where
            sc: ‹ctl (stk, v) = Some (a, stk', v')›
          and rec: ‹f ctl' fin' dec' (if a = DShift then (None, 1, 1) else bupd d stk)
              (stk', v', xtree dec' a v ts) = Some t›
          unfolding st c fi by (auto simp: bind_eq_Some_conv split: if_splits)
        from "1"(1)[OF rec] c fi dd have ‹nrun ctl fin dec (stk', v', xtree dec a v ts) = Some t› by simp
        then show ?thesis unfolding st using False sc by (subst nrun.simps) simp
      qed
    qed
  qed
  then show ?thesis by blast
qed

lemma fst_bupd: ‹fst (bupd d stk) = Some stk ∨ fst (bupd d stk) = fst d›
  by (cases d) (auto simp: bupd_def)

lemma n_imp_b:
  assumes h: ‹nrun ctl fin dec st = Some t›
  shows ‹(∀c'. ctl_step** (fst st, fst (snd st)) c' ⟶ ¬ ctl_step++ c' c') ⟹
    (∀s. fst d = Some s ⟶ ctl_step++ (s, fst (snd st)) (fst st, fst (snd st))) ⟹
    brun ctl fin dec d st = Some t›
proof -
  have ‹ctl = ctl ⟶ fin = fin ⟶ dec = dec ⟶ (∀c'. ctl_step** (fst st, fst (snd st)) c' ⟶ ¬ ctl_step++ c' c') ⟶
      (∀d. (∀s. fst d = Some s ⟶ ctl_step++ (s, fst (snd st)) (fst st, fst (snd st))) ⟶
        brun ctl fin dec d st = Some t)›
  proof (rule nrun.raw_induct[OF _ h, where P = ‹λctl' fin' dec' st t. ctl' = ctl ⟶ fin' = fin ⟶
      dec' = dec ⟶ (∀c'. ctl_step** (fst st, fst (snd st)) c' ⟶ ¬ ctl_step++ c' c') ⟶
      (∀d. (∀s. fst d = Some s ⟶ ctl_step++ (s, fst (snd st)) (fst st, fst (snd st))) ⟶
        brun ctl fin dec d st = Some t)›], goal_cases)
    case (1 f ctl' fin' dec' st t)
    obtain stk v ts where st: ‹st = (stk, v, ts)› by (cases st)
    show ?case
    proof (intro impI allI)
      fix d :: ‹'k list option × nat × nat›
      assume c: ‹ctl' = ctl› and fi: ‹fin' = fin› and dd: ‹dec' = dec›
        and nc: ‹∀c'. ctl_step** (fst st, fst (snd st)) c' ⟶ ¬ ctl_step++ c' c'›
        and inv: ‹∀s. fst d = Some s ⟶ ctl_step++ (s, fst (snd st)) (fst st, fst (snd st))›
      show ‹brun ctl fin dec d st = Some t›
      proof (cases ‹fin (stk, v)›)
        case True
        with "1"(2) show ?thesis unfolding st c fi by (subst brun.simps) simp
      next
        case False
        have ns: ‹fst d ≠ Some stk›
        proof
          assume ‹fst d = Some stk›
          with inv have ‹ctl_step++ (stk, v) (stk, v)› unfolding st by auto
          with nc show False unfolding st by auto
        qed
        from False "1"(2) obtain a stk' v' where
            sc: ‹ctl (stk, v) = Some (a, stk', v')›
          and rec: ‹f ctl' fin' dec' (stk', v', xtree dec' a v ts) = Some t›
          unfolding st c fi by (auto simp: bind_eq_Some_conv)
        have s1: ‹ctl_step (stk, v) (stk', v')› using False sc unfolding cstep_def by blast
        have nc': ‹∀c'. ctl_step** (stk', v') c' ⟶ ¬ ctl_step++ c' c'›
          using nc s1 unfolding st by (auto intro: converse_rtranclp_into_rtranclp)
        have inv': ‹∀s. fst (if a = DShift then (None, 1, 1) else bupd d stk) = Some s ⟶
            ctl_step++ (s, v') (stk', v')›
        proof (cases ‹a = DShift›)
          case False
          then have v': ‹v' = v› using keep[OF sc] by blast
          show ?thesis using False inv s1 fst_bupd[of d stk] unfolding st v'
            by (auto intro: tranclp.trancl_into_trancl)
        qed simp
        have ih: ‹∀d. (∀s. fst d = Some s ⟶ ctl_step++ (s, v') (stk', v')) ⟶
            brun ctl fin dec d (stk', v', xtree dec a v ts) = Some t›
          using "1"(1)[OF rec] c fi dd nc' unfolding fst_conv snd_conv by blast
        have ‹brun ctl fin dec (if a = DShift then (None, 1, 1) else bupd d stk) (stk', v', xtree dec a v ts) = Some t›
          using spec[OF ih, of ‹if a = DShift then (None, 1, 1) else bupd d stk›] inv' by blast
        then show ?thesis unfolding st using False ns sc by (subst brun.simps) simp
      qed
    qed
  qed
  then show ‹(∀c'. ctl_step** (fst st, fst (snd st)) c' ⟶ ¬ ctl_step++ c' c') ⟹
    (∀s. fst d = Some s ⟶ ctl_step++ (s, fst (snd st)) (fst st, fst (snd st))) ⟹
    brun ctl fin dec d st = Some t› by blast
qed

theorem xrun_hist_brun:
  ‹xrun_hist ctl fin dec [] st = brun ctl fin dec (None, 1, 1) st›
proof (cases ‹nrun ctl fin dec st›)
  case None
  have x: ‹xrun_hist ctl fin dec [] st = None›
    using x_imp_n None by (cases ‹xrun_hist ctl fin dec [] st›) auto
  have b: ‹brun ctl fin dec (None, 1, 1) st = None›
    using b_imp_n None by (cases ‹brun ctl fin dec (None, 1, 1) st›) auto
  show ?thesis using x b by simp
next
  case (Some t)
  have nc: ‹∀c'. ctl_step** (fst st, fst (snd st)) c' ⟶ ¬ ctl_step++ c' c'› using nocycle[OF Some] by blast
  show ?thesis using n_imp_x[OF Some nc] n_imp_b[OF Some nc] by simp
qed

end

lemma kctl_keep:
  ‹kctl K (stk, v) = Some (a, stk', v') ⟹ a ≠ DShift ⟹ v' = v›
  by (auto simp: kctl_def Let_def split: list.splits option.splits prod.splits dact.splits)

lemma dparse_via_prod_loop:
  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 = brun (kctl K) (kfinal K) fst (None, 1, 1) ([i0], map (kenc K) w, [])›
  unfolding dparse_via_prod_tables[OF static st gt rt pcs pfs i0 lt jt kt]
  by (rule xrun_hist_brun) (rule kctl_keep)

end