Theory LR_Prec

(* Author: Basil Fürer *)

theory LR_Prec
  imports LR_Restrict
begin

section ‹Declarations›

datatype fkind = FDirect | FRight | FLeft
datatype passoc = ALeft | ARight | ANon | AOpen | AList

type_synonym ('n, 't) forbid = ‹('n, 't) alt × nat × fkind × ('n, 't) alt›

text ‹A level holds alternatives with a strictness flag, and ‹dlevels› is a list of
  chains of levels, loosest first: two levels are ordered only if they share a chain, so a
  partial order is several chains. ‹dforbids› are the restrictions a level table cannot
  express. A forbid ‹(p, k, FDirect, c)› keeps ‹c› from being child
  ‹k› of ‹p›; ‹FRight› and ‹FLeft› keep it off the whole right or left spine of that child.

  The levels are the priority chains and associativity groups of Afroozeh et al.
  cite‹‹Defs.~2, 4, Sect.~3.3› in "afroozeh2013-operator-precedence"›, and ‹ALeft›, ‹ARight›,
  ‹ANon› are the relations ‹L›, ‹R›, ‹N› of a priority declaration
  cite‹‹Def.~5.1› in "klint1994-disambiguation-filters"›.  ‹AOpen›, ‹AList› and the
  strictness flag have no counterpart there.  A forbid ‹(p, k, FDirect, c)› is the pattern
  ‹(E, p, k, c)› of cite‹‹Def.~5› in "afroozeh2013-operator-precedence"› and a one-level
  case of subtree exclusion cite‹‹Def.~5.20› in "klint1994-disambiguation-filters"›.›

record ('n, 't) prec_decl =
  dlevels :: ‹(passoc × (('n, 't) alt × bool) list) list list›
  dforbids :: ‹('n, 't) forbid list›

section ‹Spines›

fun sym_null :: ‹'n list ⇒ ('n, 't) sym ⇒ bool› where
  ‹sym_null ns (Nt x) = (x ∈ set ns)›
| ‹sym_null ns (Tm t) = False›

definition nstep :: ‹('n, 't) is_cfg ⇒ 'n list ⇒ 'n list› where
  ‹nstep G ns = remdups (map fst (filter (λp. list_all (λa. sym_null ns (fst a)) (snd p)) (iprods G)))›

fun nfix :: ‹('n, 't) is_cfg ⇒ nat ⇒ 'n list ⇒ 'n list› where
  ‹nfix G 0 ns = ns›
| ‹nfix G (Suc f) ns = (let ns' = nstep G ns in if ns' = ns then ns else nfix G f ns')›

definition nulls :: ‹('n, 't) is_cfg ⇒ 'n list› where
  ‹nulls G = nfix G (Suc (length (iprods G))) []›

fun is_nt :: ‹('n, 't) sym ⇒ bool› where
  ‹is_nt (Nt x) = True›
| ‹is_nt (Tm t) = False›

text ‹A top-down automaton cannot see whether a subtree is empty, so a position is on the
  spine when everything beyond it is nullable in the grammar. Stopping at closed productions
  is the special case of a terminal beyond the position.  Spine forbids are needed because
  one-level patterns cannot exclude a looser operator that sits arbitrarily deep on a spine
  cite‹‹Sect.~2.2, Fig.~2› in "afroozeh2013-operator-precedence"›.›

definition rpos :: ‹'n list ⇒ ('n, 't) rhs ⇒ nat ⇒ bool› where
  ‹rpos ns r k ⟷ k < length r ∧ is_nt (fst (r ! k)) ∧
     list_all (λa. sym_null ns (fst a)) (drop (Suc k) r)›

definition lpos :: ‹'n list ⇒ ('n, 't) rhs ⇒ nat ⇒ bool› where
  ‹lpos ns r k ⟷ k < length r ∧ is_nt (fst (r ! k)) ∧
     list_all (λa. sym_null ns (fst a)) (take k r)›

definition fb :: ‹('n, 't) forbid list ⇒ fkind ⇒ ('n, 't) alt ⇒ nat ⇒ ('n, 't) alt list› where
  ‹fb F kd p k = map (λf. snd (snd (snd f)))
     (filter (λf. fst f = p ∧ fst (snd f) = k ∧ fst (snd (snd f)) = kd) F)›

section ‹The tree predicate›

text ‹‹pk› accepts a tree when no node matches a forbid, carrying the forbids
  inherited along spines downwards.  This is the filter generated by an exclusion
  predicate checked on every subtree cite‹‹Defs.~4.9, 4.11› in "klint1994-disambiguation-filters"›.›

inductive pk ::
  ‹('n, 't) is_cfg ⇒ 'n list ⇒ ('n, 't) forbid list ⇒ ('n, 't) alt set ⇒ ('n, 't) alt set ⇒
   ('n, 't) alt set ⇒ ('m, 'ch, 'n, 't) ptree ⇒ bool›
  for G ns F where
  pk_leaf: ‹pk G ns F D R L (PLeaf t)›
| pk_node: ‹(n, r) ∈ set (iprods G) ⟹ (n, r) ∉ D ⟹ (n, r) ∉ R ⟹ (n, r) ∉ L ⟹
    length ts = length r ⟹
    (⋀k. k < length r ⟹ fst (proot (ts ! k)) = fst (r ! k) ∧
      irel_sat (snd (r ! k)) (snd (proot (ts ! k))) i ∧
      pk G ns F (set (fb F FDirect (n, r) k))
        (set (fb F FRight (n, r) k) ∪ (if rpos ns r k then R else {}))
        (set (fb F FLeft (n, r) k) ∪ (if lpos ns r k then L else {})) (ts ! k)) ⟹
    pk G ns F D R L (PNode n i ts)›

section ‹The automaton›

type_synonym ('n, 't) pstate = ‹'n × ('n, 't) alt list × ('n, 't) alt list × ('n, 't) alt list›

definition canon :: ‹('n, 't) is_cfg ⇒ ('n ⇒ ('n, 't) alt list) ⇒ ('n ⇒ ('n, 't) alt list) ⇒ 'n ⇒
    ('n, 't) alt list ⇒ ('n, 't) alt list ⇒ ('n, 't) alt list ⇒ ('n, 't) pstate› where
  ‹canon G rt lt N D R L =
    (let R' = filter (λp. p ∈ set R) (rt N);
         L' = filter (λp. p ∈ set L) (lt N)
     in (N, filter (λp. fst p = N ∧ (p ∈ set D ∨ p ∈ set R' ∨ p ∈ set L')) (iprods G), R', L'))›

definition pok :: ‹('n, 't) pstate ⇒ ('n, 't) alt ⇒ bool› where
  ‹pok q p ⟷ p ∉ set (fst (snd q))›

definition pstep :: ‹('n, 't) is_cfg ⇒ 'n list ⇒ ('n, 't) forbid list ⇒
    ('n ⇒ ('n, 't) alt list) ⇒ ('n ⇒ ('n, 't) alt list) ⇒
    ('n, 't) pstate ⇒ ('n, 't) alt ⇒ nat ⇒ ('n, 't) pstate› where
  ‹pstep G ns F rt lt q p k =
    canon G rt lt (case fst (snd p ! k) of Nt x ⇒ x | Tm _ ⇒ fst q) (fb F FDirect p k)
      (fb F FRight p k @ (if rpos ns (snd p) k then fst (snd (snd q)) else []))
      (fb F FLeft p k @ (if lpos ns (snd p) k then snd (snd (snd q)) else []))›

definition paut :: ‹('n, 't) is_cfg ⇒ 'n list ⇒ ('n, 't) forbid list ⇒
    ('n ⇒ ('n, 't) alt list) ⇒ ('n ⇒ ('n, 't) alt list) ⇒
    ('n, 't, ('n, 't) pstate) prec_aut› where
  ‹paut G ns F rt lt = ⦇ok = pok, step = pstep G ns F rt lt⦈›

locale spined =
  fixes G :: ‹('n, 't) is_cfg› and ns :: ‹'n list› and F :: ‹('n, 't) forbid list›
    and rt lt :: ‹'n ⇒ ('n, 't) alt list›
  assumes rt_self: ‹p ∈ set (iprods G) ⟹ p ∈ set (rt (fst p))›
    and lt_self: ‹p ∈ set (iprods G) ⟹ p ∈ set (lt (fst p))›
    and rt_step: ‹(n, r) ∈ set (iprods G) ⟹ rpos ns r k ⟹ fst (r ! k) = Nt x ⟹
        set (rt x) ⊆ set (rt n)›
    and lt_step: ‹(n, r) ∈ set (iprods G) ⟹ lpos ns r k ⟹ fst (r ! k) = Nt x ⟹
        set (lt x) ⊆ set (lt n)›
begin

abbreviation ‹A ≡ paut G ns F rt lt›

lemma canon_cong:
  assumes ‹⋀p. p ∈ set (rt N) ⟹ p ∈ set R1 ⟷ p ∈ set R2›
    and ‹⋀p. p ∈ set (lt N) ⟹ p ∈ set L1 ⟷ p ∈ set L2›
  shows ‹canon G rt lt N D R1 L1 = canon G rt lt N D R2 L2›
proof -
  have ‹filter (λp. p ∈ set R1) (rt N) = filter (λp. p ∈ set R2) (rt N)›
    ‹filter (λp. p ∈ set L1) (lt N) = filter (λp. p ∈ set L2) (lt N)›
    using assms by (auto intro: filter_cong)
  then show ?thesis by (simp add: canon_def Let_def)
qed

lemma step_canon:
  assumes p: ‹(N, r) ∈ set (iprods G)› and x: ‹fst (r ! k) = Nt x›
  shows ‹step A (canon G rt lt N D R L) (N, r) k = canon G rt lt x (fb F FDirect (N, r) k)
      (fb F FRight (N, r) k @ (if rpos ns r k then R else []))
      (fb F FLeft (N, r) k @ (if lpos ns r k then L else []))›
proof -
  have *: ‹canon G rt lt x (fb F FDirect (N, r) k)
      (fb F FRight (N, r) k @ (if rpos ns r k then filter (λp. p ∈ set R) (rt N) else []))
      (fb F FLeft (N, r) k @ (if lpos ns r k then filter (λp. p ∈ set L) (lt N) else [])) =
    canon G rt lt x (fb F FDirect (N, r) k)
      (fb F FRight (N, r) k @ (if rpos ns r k then R else []))
      (fb F FLeft (N, r) k @ (if lpos ns r k then L else []))›
  proof (rule canon_cong)
    show ‹p ∈ set (fb F FRight (N, r) k @ (if rpos ns r k then filter (λp. p ∈ set R) (rt N) else [])) ⟷
        p ∈ set (fb F FRight (N, r) k @ (if rpos ns r k then R else []))› if ‹p ∈ set (rt x)› for p
      using that rt_step[OF p _ x] by auto
    show ‹p ∈ set (fb F FLeft (N, r) k @ (if lpos ns r k then filter (λp. p ∈ set L) (lt N) else [])) ⟷
        p ∈ set (fb F FLeft (N, r) k @ (if lpos ns r k then L else []))› if ‹p ∈ set (lt x)› for p
      using that lt_step[OF p _ x] by auto
  qed
  show ?thesis using x by (simp add: paut_def pstep_def canon_def[of G rt lt N D R L] Let_def * [symmetric])
qed

lemma ok_canon:
  assumes p: ‹(N, r) ∈ set (iprods G)›
  shows ‹ok A (canon G rt lt N D R L) (N, r) ⟷
    (N, r) ∉ set D ∧ (N, r) ∉ set R ∧ (N, r) ∉ set L›
  using p rt_self[OF p] lt_self[OF p] by (auto simp: paut_def pok_def canon_def Let_def)

lemma canon_of_run:
  ‹prec_run G A q t ⟹ q = canon G rt lt N D R L ⟹ (⋀n i ts. t = PNode n i ts ⟹ n = N) ⟹
   pk G ns F (set D) (set R) (set L) t›
proof (induction arbitrary: N D R L rule: prec_run.induct)
  case (prec_leaf q t)
  show ?case by (rule pk_leaf)
next
  case (prec_node n r q ts i)
  have n: ‹n = N› using prec_node.prems(2) by simp
  note p = prec_node.hyps(1)[unfolded n]
  have o: ‹(N, r) ∉ set D› ‹(N, r) ∉ set R› ‹(N, r) ∉ set L›
    using prec_node.hyps(2) ok_canon[OF p] by (simp_all add: n prec_node.prems(1))
  show ?case unfolding n
  proof (rule pk_node[OF p o prec_node.hyps(3)])
    fix k assume k: ‹k < length r›
    note h = prec_node.IH[OF k]
    have ‹pk G ns F (set (fb F FDirect (N, r) k))
        (set (fb F FRight (N, r) k) ∪ (if rpos ns r k then set R else {}))
        (set (fb F FLeft (N, r) k) ∪ (if lpos ns r k then set L else {})) (ts ! k)›
    proof (cases ‹ts ! k›)
      case (PLeaf t)
      then show ?thesis by (simp add: pk_leaf)
    next
      case (PNode m j us)
      then have x: ‹fst (r ! k) = Nt m› using h by simp
      have ‹pk G ns F (set (fb F FDirect (N, r) k))
          (set (fb F FRight (N, r) k @ (if rpos ns r k then R else [])))
          (set (fb F FLeft (N, r) k @ (if lpos ns r k then L else []))) (ts ! k)›
      proof (rule h[THEN conjunct2, THEN conjunct2, THEN conjunct2, rule_format])
        show ‹step A q (n, r) k = canon G rt lt m (fb F FDirect (N, r) k)
            (fb F FRight (N, r) k @ (if rpos ns r k then R else []))
            (fb F FLeft (N, r) k @ (if lpos ns r k then L else []))›
          unfolding n prec_node.prems(1) by (rule step_canon[OF p x])
      qed (simp add: PNode)
      then show ?thesis by (auto elim!: back_subst[where P = ‹λS. pk G ns F _ S _ _›]
            back_subst[where P = ‹λS. pk G ns F _ _ S _›])
    qed
    with h show ‹fst (proot (ts ! k)) = fst (r ! k) ∧ irel_sat (snd (r ! k)) (snd (proot (ts ! k))) i ∧
        pk G ns F (set (fb F FDirect (N, r) k))
        (set (fb F FRight (N, r) k) ∪ (if rpos ns r k then set R else {}))
        (set (fb F FLeft (N, r) k) ∪ (if lpos ns r k then set L else {})) (ts ! k)› by blast
  qed
qed

lemma run_of_pk:
  ‹pk G ns F SD SR SL t ⟹ SD = set D ⟹ SR = set R ⟹ SL = set L ⟹
   (⋀n i ts. t = PNode n i ts ⟹ n = N) ⟹ prec_run G A (canon G rt lt N D R L) t›
proof (induction arbitrary: N D R L rule: pk.induct)
  case (pk_leaf D R L t)
  show ?case by (rule prec_leaf)
next
  case (pk_node n r SD SR SL ts i)
  have n: ‹n = N› using pk_node.prems(4) by simp
  note p = pk_node.hyps(1)[unfolded n]
  have o: ‹ok A (canon G rt lt N D R L) (N, r)›
    using pk_node.hyps(2-4) ok_canon[OF p] by (simp add: n pk_node.prems)
  show ?case unfolding n
  proof (rule prec_node[OF p o pk_node.hyps(5)])
    fix k assume k: ‹k < length r›
    note h = pk_node.IH[OF k, unfolded n]
    have ‹prec_run G A (step A (canon G rt lt N D R L) (N, r) k) (ts ! k)›
    proof (cases ‹ts ! k›)
      case (PLeaf t)
      then show ?thesis by (simp add: prec_leaf)
    next
      case (PNode m j us)
      then have x: ‹fst (r ! k) = Nt m› using h by simp
      have ‹prec_run G A (canon G rt lt m (fb F FDirect (N, r) k)
          (fb F FRight (N, r) k @ (if rpos ns r k then R else []))
          (fb F FLeft (N, r) k @ (if lpos ns r k then L else []))) (ts ! k)›
        by (rule h[THEN conjunct2, THEN conjunct2, THEN conjunct2, rule_format])
          (auto simp: PNode pk_node.prems)
      with step_canon[OF p x] show ?thesis by simp
    qed
    with h show ‹fst (proot (ts ! k)) = fst (r ! k) ∧ irel_sat (snd (r ! k)) (snd (proot (ts ! k))) i ∧
        prec_run G A (step A (canon G rt lt N D R L) (N, r) k) (ts ! k)› by blast
  qed
qed

theorem run_iff_pk:
  assumes ‹⋀n i ts. t = PNode n i ts ⟹ n = N›
  shows ‹prec_run G A (canon G rt lt N D R L) t ⟷ pk G ns F (set D) (set R) (set L) t›
proof
  assume a: ‹prec_run G A (canon G rt lt N D R L) t›
  show ‹pk G ns F (set D) (set R) (set L) t› by (rule canon_of_run[OF a refl]) (rule assms)
next
  assume a: ‹pk G ns F (set D) (set R) (set L) t›
  show ‹prec_run G A (canon G rt lt N D R L) t› by (rule run_of_pk[OF a refl refl refl]) (rule assms)
qed

end

section ‹Spine tables›

definition snext :: ‹('n, 't) is_cfg ⇒ (('n, 't) rhs ⇒ nat ⇒ bool) ⇒ 'n ⇒ 'n list› where
  ‹snext G pos N = concat (map (λp. if fst p = N then concat (map (λk.
       if pos (snd p) k then (case fst (snd p ! k) of Nt x ⇒ [x] | Tm _ ⇒ []) else [])
     [0..<length (snd p)]) else []) (iprods G))›

definition spn :: ‹('n, 't) is_cfg ⇒ (('n, 't) rhs ⇒ nat ⇒ bool) ⇒ 'n ⇒ ('n, 't) alt list› where
  ‹spn G pos N = filter (λp. fst p ∈ set (reach (snext G pos) N)) (iprods G)›

definition stab :: ‹('n, 't) is_cfg ⇒ (('n, 't) rhs ⇒ nat ⇒ bool) ⇒ ('n × ('n, 't) alt list) list› where
  ‹stab G pos = map (λN. (N, spn G pos N)) (remdups (map fst (iprods G)))›

definition lk :: ‹('a × 'b list) list ⇒ 'a ⇒ 'b list› where
  ‹lk tb N = (case map_of tb N of Some x ⇒ x | None ⇒ [])›

definition syms :: ‹('n, 't) is_cfg ⇒ 'n set› where
  ‹syms G = {x. ∃p ∈ set (iprods G). ∃a ∈ set (snd p). fst a = Nt x}›

lemma finite_syms: ‹finite (syms G)›
proof -
  have ‹syms G ⊆ (⋃p ∈ set (iprods G). ⋃a ∈ set (snd p). case fst a of Nt x ⇒ {x} | Tm _ ⇒ {})›
    by (force simp: syms_def)
  moreover have ‹finite (⋃p ∈ set (iprods G). ⋃a ∈ set (snd p). case fst a of Nt x ⇒ {x} | Tm _ ⇒ {})›
    by (auto split: sym.split)
  ultimately show ?thesis by (rule finite_subset)
qed

lemma in_syms: ‹p ∈ set (iprods G) ⟹ k < length (snd p) ⟹ fst (snd p ! k) = Nt x ⟹ x ∈ syms G›
  unfolding syms_def using nth_mem by fastforce

lemma snext_syms: ‹set (snext G pos N) ⊆ syms G›
  by (force simp: snext_def in_syms split: sym.splits if_splits)

lemma snext_fin: ‹finite ((steps (snext G pos))* `` {N})›
  by (rule reach_within(2)[of ‹insert N (syms G)›]) (auto simp: finite_syms dest: snext_syms[of G pos, THEN subsetD])

lemma snext_step:
  assumes ‹(n, r) ∈ set (iprods G)› ‹pos r k› ‹k < length r› ‹fst (r ! k) = Nt x›
  shows ‹x ∈ set (snext G pos n)›
proof -
  have ‹x ∈ set (concat (map (λk. if pos r k then (case fst (r ! k) of Nt x ⇒ [x] | Tm _ ⇒ []) else [])
      [0..<length r]))›
    using assms(2-4) by (auto intro!: bexI[of _ k])
  with assms(1) show ?thesis by (auto simp: snext_def intro!: bexI[of _ ‹(n, r)›])
qed

lemma reach_mono:
  assumes fin: ‹finite ((steps f)* `` {n})› ‹finite ((steps f)* `` {x})›
    and x: ‹x ∈ set (reach f n)›
  shows ‹set (reach f x) ⊆ set (reach f n)›
proof
  fix y assume ‹y ∈ set (reach f x)›
  with reach_spec(3)[OF fin(2)] have ‹(x, y) ∈ (steps f)*› by blast
  then show ‹y ∈ set (reach f n)›
  proof (induction rule: rtrancl_induct)
    case base
    from x show ?case .
  next
    case (step y z)
    with reach_spec(2)[OF fin(1)] show ?case by (auto simp: steps_def)
  qed
qed

lemma spn_self: ‹p ∈ set (iprods G) ⟹ p ∈ set (spn G pos (fst p))›
  using reach_spec(1)[OF snext_fin] by (auto simp: spn_def)

lemma spn_step:
  assumes ‹(n, r) ∈ set (iprods G)› ‹pos r k› ‹k < length r› ‹fst (r ! k) = Nt x›
  shows ‹set (spn G pos x) ⊆ set (spn G pos n)›
proof -
  have ‹x ∈ set (reach (snext G pos) n)›
    using reach_spec(2)[OF snext_fin reach_spec(1)[OF snext_fin] snext_step[where pos = pos, OF assms]] .
  from reach_mono[OF snext_fin snext_fin this] show ?thesis by (auto simp: spn_def)
qed

lemma lk_map: ‹lk (map (λN. (N, f N)) xs) N = (if N ∈ set xs then f N else [])›
  by (induction xs) (auto simp: lk_def)

lemma lk_stab: ‹lk (stab G pos) N = (if N ∈ set (map fst (iprods G)) then spn G pos N else [])›
  unfolding stab_def lk_map by simp

lemma lk_shape: ‹∃g. lk (stab G pos) N = filter g (iprods G)›
  unfolding lk_stab spn_def by (cases ‹N ∈ set (map fst (iprods G))›)
    (auto intro: exI[of _ ‹λ_. False›])

lemma lk_self: ‹p ∈ set (iprods G) ⟹ p ∈ set (lk (stab G pos) (fst p))›
proof -
  assume p: ‹p ∈ set (iprods G)›
  then have ‹fst p ∈ set (map fst (iprods G))› by simp
  with spn_self[OF p] show ?thesis unfolding lk_stab by simp
qed

lemma lk_step:
  assumes ‹(n, r) ∈ set (iprods G)› ‹pos r k› ‹k < length r› ‹fst (r ! k) = Nt x›
  shows ‹set (lk (stab G pos) x) ⊆ set (lk (stab G pos) n)›
proof -
  have ‹n ∈ set (map fst (iprods G))› using assms(1) by force
  then show ?thesis unfolding lk_stab using spn_step[where pos = pos, OF assms] by auto
qed

section ‹Levels to forbids›

text ‹‹level_forbids› turns levels into forbids on the first and last child of
  each alternative, after the pattern tables of
  cite‹‹Tables~1--2› in "afroozeh2013-operator-precedence"› and the precedence and
  associativity automata of cite‹‹Sects.~3.1.1--3.1.2› in "adams2017-tree-automata"›.
  It departs from both: a looser alternative that is open on the right is forbidden on the
  whole right spine of the first child, not only as that child.›

definition pick0 :: ‹('n, 't) rhs ⇒ nat ⇒ bool› where ‹pick0 r k ⟷ k = 0›
definition pickl :: ‹('n, 't) rhs ⇒ nat ⇒ bool› where ‹pickl r k ⟷ Suc k = length r›

definition opens :: ‹('n, 't) is_cfg ⇒ (('n, 't) rhs ⇒ nat ⇒ bool) ⇒ ('n, 't) sym ⇒ 'n ⇒ bool› where
  ‹opens G pos X T = (case X of Nt x ⇒ T ∈ set (reach (snext G pos) x) | Tm _ ⇒ False)›

definition lopen :: ‹('n, 't) is_cfg ⇒ ('n, 't) alt ⇒ 'n ⇒ bool› where
  ‹lopen G c T ⟷ snd c ≠ [] ∧ opens G pick0 (fst (hd (snd c))) T›

definition ropen :: ‹('n, 't) is_cfg ⇒ ('n, 't) alt ⇒ 'n ⇒ bool› where
  ‹ropen G c T ⟷ snd c ≠ [] ∧ opens G pickl (fst (last (snd c))) T›

type_synonym ('n, 't) ltab = ‹(('n, 't) alt × nat × passoc × bool) list›

definition lvl_tab :: ‹(passoc × (('n, 't) alt × bool) list) list ⇒ ('n, 't) ltab› where
  ‹lvl_tab lvs = concat (map (λ(i, a, cs). map (λ(c, s). (c, i, a, s)) cs) (List.indexed_from 0 lvs))›

definition lside :: ‹('n, 't) is_cfg ⇒ ('n, 't) ltab ⇒ ('n, 't) alt ⇒ nat ⇒ passoc ⇒ 'n ⇒ ('n, 't) forbid list› where
  ‹lside G tb p lp ap X = (if ap = AOpen then [] else concat (map (λc.
     case map_of tb c of None ⇒ []
     | Some (lc, ac, _) ⇒
        if ap = AList ∧ ac = AList ∧ fst p = X then [] else
        if lc < lp ∨ (lc = lp ∧ ap ≠ ALeft) then
          (if lopen G c X then [(p, 0, FDirect, c)] else []) @
          (if ropen G c X then [(p, 0, FRight, c)] else [])
        else []) (filter (λc. fst c = X) (iprods G))))›

definition rside :: ‹('n, 't) is_cfg ⇒ ('n, 't) ltab ⇒ ('n, 't) alt ⇒ nat ⇒ passoc ⇒ 'n ⇒ ('n, 't) forbid list› where
  ‹rside G tb p lp ap X = concat (map (λc.
     case map_of tb c of None ⇒ []
     | Some (lc, ac, sc) ⇒
        if ap = AList ∧ ac = AList ∧ fst p = X then [] else
        if (lc < lp ∨ (lc = lp ∧ ap ≠ ARight)) ∧ (lopen G c X ∨ sc)
        then [(p, length (snd p) - 1, FDirect, c)] else []) (filter (λc. fst c = X) (iprods G)))›

definition level_forbids :: ‹('n, 't) is_cfg ⇒ (passoc × (('n, 't) alt × bool) list) list ⇒ ('n, 't) forbid list› where
  ‹level_forbids G lvs = (let tb = lvl_tab lvs in concat (map (λ(p, lp, ap, _).
     if length (snd p) ≤ 1 then [] else
       (case fst (hd (snd p)) of Nt X ⇒ lside G tb p lp ap X | Tm _ ⇒ []) @
       (case fst (last (snd p)) of Nt X ⇒ rside G tb p lp ap X | Tm _ ⇒ [])) tb))›

definition forbids :: ‹('n, 't) is_cfg ⇒ ('n, 't) prec_decl ⇒ ('n, 't) forbid list› where
  ‹forbids G d = dforbids d @ concat (map (level_forbids G) (dlevels d))›

section ‹Top level›

definition prec_ok :: ‹('n, 't) is_cfg ⇒ ('n, 't) prec_decl ⇒ ('m, 'ch, 'n, 't) ptree ⇒ bool› where
  ‹prec_ok G d t ⟷ pk G (nulls G) (forbids G d) {} {} {} t›

definition compile :: ‹('n, 't) is_cfg ⇒ ('n, 't) prec_decl ⇒ ('n, 't, ('n, 't) pstate) prec_aut› where
  ‹compile G d = (let ns = nulls G; rb = stab G (rpos ns); lb = stab G (lpos ns)
     in paut G ns (forbids G d) (lk rb) (lk lb))›

definition pq0 :: ‹('n, 't) is_cfg ⇒ ('n, 't) pstate› where
  ‹pq0 G = (let ns = nulls G; rb = stab G (rpos ns); lb = stab G (lpos ns)
     in canon G (lk rb) (lk lb) (istart G) [] [] [])›

definition restrict :: ‹(string, 't) is_cfg ⇒ (string, 't) prec_decl ⇒ (string, 't) is_cfg› where
  ‹restrict G d = (let ns = nulls G; rb = stab G (rpos ns); lb = stab G (lpos ns)
     in restrict_gen G (paut G ns (forbids G d) (lk rb) (lk lb)) fst
          (canon G (lk rb) (lk lb) (istart G) [] [] []))›

lemma restrict_alt: ‹restrict G d = restrict_gen G (compile G d) fst (pq0 G)›
  by (simp add: restrict_def compile_def pq0_def Let_def)

interpretation prec_sp: spined G ns F ‹lk (stab G (rpos ns))› ‹lk (stab G (lpos ns))› for G ns F
proof
  show ‹p ∈ set (lk (stab G (rpos ns)) (fst p))› if ‹p ∈ set (iprods G)› for p
    using lk_self[OF that] .
  show ‹p ∈ set (lk (stab G (lpos ns)) (fst p))› if ‹p ∈ set (iprods G)› for p
    using lk_self[OF that] .
  show ‹set (lk (stab G (rpos ns)) x) ⊆ set (lk (stab G (rpos ns)) n)›
    if ‹(n, r) ∈ set (iprods G)› ‹rpos ns r k› ‹fst (r ! k) = Nt x› for n r k x
    by (rule lk_step[where pos = ‹rpos ns›, OF that(1,2) _ that(3)]) (use that(2) in ‹simp add: rpos_def›)
  show ‹set (lk (stab G (lpos ns)) x) ⊆ set (lk (stab G (lpos ns)) n)›
    if ‹(n, r) ∈ set (iprods G)› ‹lpos ns r k› ‹fst (r ! k) = Nt x› for n r k x
    by (rule lk_step[where pos = ‹lpos ns›, OF that(1,2) _ that(3)]) (use that(2) in ‹simp add: lpos_def›)
qed

theorem accepts_iff_prec_ok:
  assumes ‹⋀n i ts. t = PNode n i ts ⟹ n = istart G›
  shows ‹prec_run G (compile G d) (pq0 G) t ⟷ prec_ok G d t›
  using prec_sp.run_iff_pk[where ns = ‹nulls G› and F = ‹forbids G d› and D = ‹[]› and R = ‹[]›
      and L = ‹[]›, OF assms]
  by (simp add: compile_def pq0_def prec_ok_def Let_def)

section ‹Finitely many states›

definition subs :: ‹'a list ⇒ 'a list set› where
  ‹subs P = (λS. filter (λp. p ∈ S) P) ` Pow (set P)›

lemma finite_subs: ‹finite (subs P)›
  by (simp add: subs_def)

lemma filter_subs: ‹filter g P ∈ subs P›
proof -
  have ‹filter g P = filter (λp. p ∈ {p ∈ set P. g p}) P› by (rule filter_cong) auto
  then show ?thesis unfolding subs_def by blast
qed

definition pspace :: ‹('n, 't) is_cfg ⇒ ('n, 't) pstate set› where
  ‹pspace G = insert (istart G) (syms G) × subs (iprods G) × subs (iprods G) × subs (iprods G)›

lemma finite_pspace: ‹finite (pspace G)›
  by (simp add: pspace_def finite_syms finite_subs)

lemma canon_space:
  assumes ‹N ∈ insert (istart G) (syms G)›
  shows ‹canon G (lk (stab G p1)) (lk (stab G p2)) N D R L ∈ pspace G›
proof -
  obtain g1 g2 where g: ‹lk (stab G p1) N = filter g1 (iprods G)› ‹lk (stab G p2) N = filter g2 (iprods G)›
    using lk_shape by metis
  show ?thesis using assms
    by (simp add: canon_def Let_def pspace_def g filter_subs)
qed

lemma mem_concat_map: ‹y ∈ set (concat (map f xs)) ⟹ ∃x∈set xs. y ∈ set (f x)›
  by auto

lemma rsucc_mem:
  assumes ‹z ∈ set (rsucc G A nt q)›
  obtains l k x where ‹l < length (iprods G)› ‹k < length (snd (iprods G ! l))›
    ‹fst (snd (iprods G ! l) ! k) = Nt x› ‹z = step A q (iprods G ! l) k›
proof -
  obtain l where l: ‹l ∈ set (ralts G A nt q)› and
    z: ‹z ∈ set (concat (map (λk. case fst (snd (iprods G ! l) ! k) of
        Nt _ ⇒ [step A q (iprods G ! l) k] | Tm _ ⇒ []) [0..<length (snd (iprods G ! l))]))›
    using mem_concat_map[OF assms[unfolded rsucc_def]] by blast
  obtain k where k0: ‹k ∈ set [0..<length (snd (iprods G ! l))]› and
    y: ‹z ∈ set (case fst (snd (iprods G ! l) ! k) of
        Nt _ ⇒ [step A q (iprods G ! l) k] | Tm _ ⇒ [])›
    using mem_concat_map[OF z] by blast
  have k: ‹k < length (snd (iprods G ! l))› using k0 by simp
  show ?thesis
  proof (cases ‹fst (snd (iprods G ! l) ! k)›)
    case (Nt x)
    with l k y that[of l k x] show ?thesis by (simp add: set_ralts)
  next
    case (Tm t)
    with y show ?thesis by simp
  qed
qed

lemma rsucc_space:
  ‹set (rsucc G (paut G ns F (lk (stab G p1)) (lk (stab G p2))) fst q) ⊆ pspace G›
proof
  fix z assume ‹z ∈ set (rsucc G (paut G ns F (lk (stab G p1)) (lk (stab G p2))) fst q)›
  then obtain l k x where l: ‹l < length (iprods G)› ‹k < length (snd (iprods G ! l))›
    ‹fst (snd (iprods G ! l) ! k) = Nt x›
    ‹z = step (paut G ns F (lk (stab G p1)) (lk (stab G p2))) q (iprods G ! l) k›
    by (rule rsucc_mem)
  have ‹x ∈ insert (istart G) (syms G)› using in_syms[OF nth_mem[OF l(1)] l(2,3)] by simp
  from canon_space[OF this] l show ‹z ∈ pspace G›
    by (simp add: paut_def pstep_def)
qed

theorem restrict_correct:
  assumes ‹no_self_unit G›
  shows ‹∃Q (cls :: _ ⇒ string). restrict_ok G (compile G d) (pq0 G) Q cls (restrict G d) orig_name›
  unfolding restrict_alt
proof (rule restrict_gen_correct[OF _ _ assms])
  have q: ‹pq0 G ∈ pspace G› unfolding pq0_def Let_def by (rule canon_space) simp
  show ‹finite ((steps (rsucc G (compile G d) fst))* `` {pq0 G})›
    by (rule reach_within(2)[OF finite_pspace q])
      (simp add: compile_def Let_def rsucc_space)
  show ‹fst (pq0 G) = istart G› by (simp add: pq0_def canon_def Let_def)
qed (simp add: compile_def paut_def pstep_def canon_def Let_def)

end