Theory TIGER_Lexer

(* Author: Basil Fürer *)

theory TIGER_Lexer
  imports TIGER_Gen
begin

section ‹The runner›

text ‹The runner steps the DFA of a mode over the input, remembers the last accepting
  position and its rule, stops at the dead state or at the end of input, and backs up to
  that position cite‹‹Sect.~17› in "paxson2026-flex-manual"›
  cite‹‹Sect.~2, Fig.~1(a)› in "reps1998-maximal-munch-linear"›. Its surface theorem is
  equality with const‹symbolic.first_token›, the step of the specification. The proof
  follows the shape of ‹auto_split_lemma› in session‹Functional-Automata›
  (‹AutoMaxChop›), Nipkow's scanner ‹auto_split›
  cite‹‹Sect.~5.2› in "nipkow1998-verified-lexical-analysis"›: an invariant on the
  part already read, carried along the scan. Nipkow's scanner has one automaton and no rule
  priorities; here the last accept also records the winning rule.

  The driver over const‹symbolic.lexes› is in theory ‹TIGER_Driver›. Reps'
  bounded-lookahead linearity cite‹‹Sect.~3› in "reps1998-maximal-munch-linear"›
  comes later, and Reps' memoization of failed state-position pairs is deferred.
  Verbatim++ verifies a Reps-style memo of maximal-prefix results across tokens, keyed by
  the length of the suffix, and analyses the result as ‹O(n log n)›
  cite‹‹Sects.~4--5› in "egolf2022-verbatim-plus-plus"›.›

subsection ‹The scan on tables›

text ‹The scan reads tables only: the transition table ‹T›, indexed by state and
  minterm number, the acceptance table ‹A›, the classifier ‹cls› from characters to
  minterm numbers (a table lookup at run time) and the index ‹d› of the dead state. It
  keeps the current state ‹q›, the number ‹n› of characters read and the last accept
  as a rule and a length. The initial state is ‹0› and the empty prefix never counts as
  an accept:›

fun scan ::
  ‹nat list list ⇒ nat option list ⇒ ('ch ⇒ nat) ⇒ nat ⇒ nat ⇒ nat ⇒ 'ch list ⇒
    (nat × nat) option ⇒ (nat × nat) option›
where
  ‹scan T A cls d q n [] b = b›
| ‹scan T A cls d q n (c # v) b =
    (let q' = T ! q ! cls c in
     if q' = d then b
     else scan T A cls d q' (Suc n) v (case A ! q' of None ⇒ b | Some i ⇒ Some (i, Suc n)))›

text ‹The runner backs up to the last accept and splits the input there:›

definition run_tables ::
  ‹nat list list ⇒ nat option list ⇒ ('ch ⇒ nat) ⇒ nat ⇒ 'ch list ⇒
    (nat × 'ch list × 'ch list) option›
where
  ‹run_tables T A cls d s =
    map_option (λ(i, n). (i, take n s, drop n s)) (scan T A cls d 0 0 s None)›

text ‹An index below the length of the list finds its element:›

lemma nth_index_of_if_less: ‹index_of Q y < length Q ⟹ Q ! index_of Q y = y›
  by (induct Q) auto

subsection ‹The invariant›

context symbolic
begin

text ‹After reading ‹u›, the remembered accept ‹b› is the longest nonempty prefix of ‹u›
  that some rule matches, with the least rule matching it. This is const‹first_token›
  on ‹u›. With no accept, no rule matches a prefix of ‹u›:›

definition last_accept :: ‹('k, 'p, 'ch, 'm) rule list ⇒ 'ch list ⇒ (nat × nat) option ⇒ bool›
where
  ‹last_accept rs u b = (case b of
     None ⇒ ∀p t ρ. u = p @ t ⟶ ρ ∈ set rs ⟶ ¬ match_rule ρ p
   | Some (i, n) ⇒ n ≤ length u ∧ first_token rs i (take n u) u)›

lemma last_accept_Nil: ‹last_accept rs [] None›
  by (simp add: last_accept_def match_rule.simps)

text ‹A longest match stays longest when the input grows by words that no rule matches:›

lemma max_pref_append:
  assumes ‹max_pref rs p u›
    and ‹⋀w t ρ. v = w @ t ⟹ w ≠ [] ⟹ ρ ∈ set rs ⟹ ¬ match_rule ρ (u @ w)›
  shows ‹max_pref rs p (u @ v)›
proof -
  from assms(1) obtain r ρ where ‹u = p @ r› ‹ρ ∈ set rs› ‹match_rule ρ p›
    by (blast dest: max_prefD)
  show ?thesis
  proof (rule max_prefI[of ‹u @ v› p ‹r @ v› ρ rs])
    show ‹u @ v = p @ r @ v›
      using ‹u = p @ r› by simp
  next
    fix p' u' ρ'
    assume ‹u @ v = p' @ u'› ‹length p < length p'› ‹ρ' ∈ set rs›
    from ‹u @ v = p' @ u'› obtain us where ‹u = p' @ us ∧ us @ v = u' ∨ u @ us = p' ∧ v = us @ u'›
      unfolding append_eq_append_conv2 by blast
    then show ‹¬ match_rule ρ' p'›
    proof
      assume ‹u = p' @ us ∧ us @ v = u'›
      then show ?thesis
        using max_pref_longest[OF assms(1), of p' us ρ'] ‹length p < length p'› ‹ρ' ∈ set rs›
        by blast
    next
      assume ‹u @ us = p' ∧ v = us @ u'›
      then show ?thesis
        using max_pref_longest[OF assms(1), of p' ‹[]› ρ'] ‹length p < length p'›
          ‹ρ' ∈ set rs› assms(2)[of us u' ρ']
        by (cases ‹us = []›) auto
    qed
  qed fact+
qed

lemma first_token_append:
  assumes ‹first_token rs i p u›
    and ‹⋀w t ρ. v = w @ t ⟹ w ≠ [] ⟹ ρ ∈ set rs ⟹ ¬ match_rule ρ (u @ w)›
  shows ‹first_token rs i p (u @ v)›
proof -
  from assms(1) have ‹max_pref rs p u› ‹i < length rs› ‹match_rule (rs ! i) p›
    ‹∀j < i. ¬ match_rule (rs ! j) p›
    by (auto elim: first_token.cases)
  moreover from ‹max_pref rs p u› assms(2) have ‹max_pref rs p (u @ v)›
    by (rule max_pref_append)
  ultimately show ?thesis
    by (blast intro: first_tokenI)
qed

lemma last_accept_append:
  assumes ‹last_accept rs u b›
    and ‹⋀w t ρ. v = w @ t ⟹ w ≠ [] ⟹ ρ ∈ set rs ⟹ ¬ match_rule ρ (u @ w)›
  shows ‹last_accept rs (u @ v) b›
proof (cases b)
  case None
  moreover have ‹¬ match_rule ρ p› if ‹u @ v = p @ t› ‹ρ ∈ set rs› for p t ρ
  proof -
    from ‹u @ v = p @ t› obtain us where ‹u = p @ us ∧ us @ v = t ∨ u @ us = p ∧ v = us @ t›
      unfolding append_eq_append_conv2 by blast
    then show ?thesis
    proof
      assume ‹u = p @ us ∧ us @ v = t›
      with assms(1) None ‹ρ ∈ set rs› show ?thesis
        by (auto simp: last_accept_def)
    next
      assume ‹u @ us = p ∧ v = us @ t›
      with assms None ‹ρ ∈ set rs› show ?thesis
        by (cases ‹us = []›) (auto simp: last_accept_def)
    qed
  qed
  ultimately show ?thesis by (simp add: last_accept_def)
next
  case (Some a)
  then obtain i n where ‹b = Some (i, n)›
    by (cases a) auto
  with assms(1) have ‹n ≤ length u› ‹first_token rs i (take n u) u›
    by (simp_all add: last_accept_def)
  with ‹b = Some (i, n)› show ?thesis
    using first_token_append[OF ‹first_token rs i (take n u) u› assms(2)]
    by (simp add: last_accept_def)
qed

text ‹On a nonempty word, the acceptance of the state reached says which rules match it:›

lemma no_match_iff_acc_None:
  ‹w ≠ [] ⟹
    (∀ρ ∈ set rs. ¬ match_rule ρ w) ⟷ acc (foldl delta_char (init_state rs) w) = None›
  by (auto simp: acc_foldl_delta_char_None_iff match_rule.simps in_set_conv_nth) (metis nth_mem)

lemma first_token_self_if_acc:
  assumes ‹w ≠ []› ‹acc (foldl delta_char (init_state rs) w) = Some i›
  shows ‹first_token rs i w w›
proof -
  from assms have ‹i < length rs› ‹match_rule (rs ! i) w› ‹∀j < i. ¬ match_rule (rs ! j) w›
    using acc_foldl_delta_char_match_rule[OF assms(1), of rs i] by blast+
  moreover have ‹max_pref rs w w›
    by (rule max_prefI[of w w ‹[]› ‹rs ! i› rs]) (use calculation in auto)
  ultimately show ?thesis
    by (blast intro: first_tokenI)
qed

end

subsection ‹The scan keeps the invariant›

context eba
begin

text ‹A classifier sends every character to a minterm of the mode that holds for it.
  const‹minterm_index› is one. The run-time lexer uses a table:›

definition minterm_classifier :: ‹('k, 'p, 'ch, 'm) rule list ⇒ ('ch ⇒ nat) ⇒ bool› where
  ‹minterm_classifier rs cls ⟷
    (∀c. cls c < length (mode_minterms rs) ∧ sem (snd (mode_minterms rs ! cls c)) c)›

lemma minterm_classifier_minterm_index: ‹minterm_classifier rs (minterm_index rs)›
  by (simp add: minterm_classifier_def minterm_index)

text ‹The dead state is the index of the empty state. If the empty state is not
  explored, the index is out of range and never reached:›

definition dead_state :: ‹('k, 'p, 'ch, 'm) rule list ⇒ nat› where
  ‹dead_state rs = index_of (dfa_states (mode_dfa rs)) {}›

definition run_dfa ::
  ‹('k, 'p, 'ch, 'm) rule list ⇒ ('ch ⇒ nat) ⇒ 'ch list ⇒
    (nat × 'ch list × 'ch list) option›
where
  ‹run_dfa rs cls =
    run_tables (dfa_trans (mode_dfa rs)) (dfa_accept (mode_dfa rs)) cls (dead_state rs)›

text ‹A transition through the classifier is the step by the character
  (@{thm [source] delta_eq_delta_char}):›

lemma trans_step:
  assumes ‹minterm_classifier rs cls› ‹q < length (dfa_states (mode_dfa rs))›
  shows ‹dfa_trans (mode_dfa rs) ! q ! cls c < length (dfa_states (mode_dfa rs)) ∧
    dfa_states (mode_dfa rs) ! (dfa_trans (mode_dfa rs) ! q ! cls c) =
      delta_char (dfa_states (mode_dfa rs) ! q) c›
proof -
  let ?M = ‹mode_minterms rs›
  let ?Q = ‹dfa_states (mode_dfa rs)›
  let ?k = ‹cls c›
  let ?q' = ‹dfa_trans (mode_dfa rs) ! q ! ?k›

  from assms(1) have k: ‹?k < length ?M› ‹sem (snd (?M ! ?k)) c›
    unfolding minterm_classifier_def by blast+
  have q': ‹?q' < length ?Q ∧ ?Q ! ?q' = delta (?Q ! q) (fst (?M ! ?k))›
    using dfa_trans_correct[of q ‹map fst ?M› rs ?k] assms(2) k(1)
    by (simp add: mode_dfa_def)
  have ‹?Q ! q ⊆ tagged_closure rs›
    using dfa_states_subset[OF nth_mem[OF assms(2)[unfolded mode_dfa_def]]]
    by (simp add: mode_dfa_def)
  moreover have ‹(fst (?M ! ?k), snd (?M ! ?k)) ∈ set ?M›
    using k(1) by simp
  ultimately have ‹delta (?Q ! q) (fst (?M ! ?k)) = delta_char (?Q ! q) c›
    using k(2) by (rule delta_eq_delta_char)
  with q' show ?thesis
    by simp
qed

text ‹The invariant holds after every character the scan reads. At the dead state no
  extension of the input read so far is matched, so stopping there keeps it too:›

lemma scan_last_accept:
  assumes ‹minterm_classifier rs cls›
    and ‹q < length (dfa_states (mode_dfa rs))›
    and ‹dfa_states (mode_dfa rs) ! q = foldl delta_char (init_state rs) u›
    and ‹last_accept rs u b›
  shows ‹last_accept rs (u @ v)
    (scan (dfa_trans (mode_dfa rs)) (dfa_accept (mode_dfa rs)) cls (dead_state rs)
      q (length u) v b)›
  using assms(2-)
proof (induct v arbitrary: q u b)
  case (Cons c v)
  let ?Q = ‹dfa_states (mode_dfa rs)›
  let ?q' = ‹dfa_trans (mode_dfa rs) ! q ! cls c›
  let ?X = ‹foldl delta_char (init_state rs) (u @ [c])›
  from trans_step[OF assms(1) Cons.prems(1), of c] Cons.prems(2)
  have q': ‹?q' < length ?Q› ‹?Q ! ?q' = ?X›
    by simp_all
  show ?case
  proof (cases ‹?q' = dead_state rs›)
    case True
    with q' have ‹?X = {}›
      by (metis dead_state_def nth_index_of_if_less)
    have ‹¬ match_rule ρ (u @ w)› if ‹c # v = w @ t› ‹w ≠ []› ‹ρ ∈ set rs› for w t ρ
    proof -
      from that(1,2) obtain w' where ‹w = c # w'›
        by (cases w) auto
      with ‹?X = {}› have ‹acc (foldl delta_char (init_state rs) (u @ w)) = None›
        by (simp add: acc_def)
      with ‹w ≠ []› ‹ρ ∈ set rs› show ?thesis
        using no_match_iff_acc_None[of ‹u @ w› rs] by simp
    qed
    then have ‹last_accept rs (u @ c # v) b›
      by (rule last_accept_append[OF Cons.prems(3)])
    with True show ?thesis
      by simp
  next
    case False
    let ?b' = ‹case dfa_accept (mode_dfa rs) ! ?q' of None ⇒ b | Some i ⇒ Some (i, Suc (length u))›
    have ‹dfa_accept (mode_dfa rs) ! ?q' = acc ?X›
      using q' by (simp add: dfa_accept_eq mode_dfa_def)
    have ‹last_accept rs (u @ [c]) ?b'›
    proof (cases ‹acc ?X›)
      case None
      then have ‹¬ match_rule ρ (u @ [c])› if ‹ρ ∈ set rs› for ρ
        using no_match_iff_acc_None[of ‹u @ [c]› rs] that by simp
      then have ‹last_accept rs (u @ [c]) b›
        by (intro last_accept_append[OF Cons.prems(3)]) (auto simp: Cons_eq_append_conv)
      with None ‹dfa_accept (mode_dfa rs) ! ?q' = acc ?X› show ?thesis
        by simp
    next
      case (Some i)
      then have ‹first_token rs i (u @ [c]) (u @ [c])›
        by (intro first_token_self_if_acc) simp_all
      with Some ‹dfa_accept (mode_dfa rs) ! ?q' = acc ?X› show ?thesis
        by (simp add: last_accept_def)
    qed
    from Cons.hyps[OF q'(1) q'(2) this] False show ?thesis
      by (simp add: Let_def)
  qed
qed simp

lemma last_accept_scan:
  assumes ‹minterm_classifier rs cls›
  shows ‹last_accept rs s
    (scan (dfa_trans (mode_dfa rs)) (dfa_accept (mode_dfa rs)) cls (dead_state rs) 0 0 s None)›
proof -
  have ‹0 < length (dfa_states (mode_dfa rs))›
    ‹dfa_states (mode_dfa rs) ! 0 = foldl delta_char (init_state rs) []›
    using dfa_run_correct[of rs ‹[]›] by (simp_all add: dfa_run_def)
  from scan_last_accept[OF assms this last_accept_Nil, of s] show ?thesis
    by simp
qed

lemma run_dfa_sound:
  assumes ‹minterm_classifier rs cls› ‹run_dfa rs cls s = Some (i, p, rest)›
  shows ‹first_token rs i p s ∧ s = p @ rest›
proof -
  from assms(2) obtain n where
    ‹scan (dfa_trans (mode_dfa rs)) (dfa_accept (mode_dfa rs)) cls (dead_state rs) 0 0 s None =
      Some (i, n)› ‹p = take n s› ‹rest = drop n s›
    by (auto simp: run_dfa_def run_tables_def)
  with last_accept_scan[OF assms(1), of s] show ?thesis
    by (simp add: last_accept_def)
qed

lemma run_dfa_None_no_first_token:
  assumes ‹minterm_classifier rs cls› ‹run_dfa rs cls s = None›
  shows ‹¬ first_token rs i p s›
proof
  assume ‹first_token rs i p s›
  then obtain u ρ where ‹s = p @ u› ‹ρ ∈ set rs› ‹match_rule ρ p›
    by (blast dest: first_token_max_pref max_prefD)
  moreover from assms have
    ‹last_accept rs s None›
    using last_accept_scan[OF assms(1), of s] by (simp add: run_dfa_def run_tables_def)
  ultimately show False
    by (auto simp: last_accept_def)
qed

section ‹Surface theorems›

text ‹With any classifier into the minterms of the mode, the runner returns exactly the
  winning rule and lexeme of const‹first_token›, and fails exactly when no rule
  matches a nonempty prefix. For one step, this is Verbatim's soundness and completeness
  cite‹‹Sects.~V-A, V-C› in "egolf2021-verbatim-verified-lexer"›, which Verbatim
  proves for derivatives, not for a DFA:›

theorem run_dfa_Some_iff:
  assumes ‹minterm_classifier rs cls›
  shows ‹run_dfa rs cls s = Some (i, p, rest) ⟷ first_token rs i p s ∧ s = p @ rest›
proof
  assume ‹run_dfa rs cls s = Some (i, p, rest)›
  with assms show ‹first_token rs i p s ∧ s = p @ rest›
    by (rule run_dfa_sound)
next
  assume ‹first_token rs i p s ∧ s = p @ rest›
  then have ‹first_token rs i p s› ‹s = p @ rest›
    by blast+
  show ‹run_dfa rs cls s = Some (i, p, rest)›
  proof (cases ‹run_dfa rs cls s›)
    case None
    with assms ‹first_token rs i p s› show ?thesis
      by (blast dest: run_dfa_None_no_first_token)
  next
    case (Some x)
    then obtain i' p' rest' where ‹run_dfa rs cls s = Some (i', p', rest')›
      by (cases x) auto
    moreover from run_dfa_sound[OF assms this] have ‹first_token rs i' p' s› ‹s = p' @ rest'›
      by blast+
    moreover from first_token_deterministic[OF ‹first_token rs i' p' s› ‹first_token rs i p s›]
    have ‹i' = i› ‹p' = p›
      by simp_all
    ultimately show ?thesis
      using ‹s = p @ rest› by simp
  qed
qed

theorem run_dfa_None_iff:
  assumes ‹minterm_classifier rs cls›
  shows ‹run_dfa rs cls s = None ⟷ (∄i p. first_token rs i p s)›
proof
  assume ‹run_dfa rs cls s = None›
  with assms show ‹∄i p. first_token rs i p s›
    by (blast dest: run_dfa_None_no_first_token)
next
  assume ‹∄i p. first_token rs i p s›
  then show ‹run_dfa rs cls s = None›
    using run_dfa_Some_iff[OF assms] by (cases ‹run_dfa rs cls s›) auto
qed

end

end