Theory TIGER_Driver

(* Author: Basil Fürer *)

theory TIGER_Driver
  imports TIGER_Lexer
begin

section ‹The driver›

text ‹The driver lexes a whole input. It steps the runner of the mode on top of the
  stack, applies the action of the winning rule and stops when no step applies: the
  stack is empty, no rule matches, or the action returns the empty stack. It returns
  the lexed source, the residue and the stack it stops in
  cite‹‹Sect.~10› in "paxson2026-flex-manual"›
  cite‹‹Fig.~4, Tokens› in "egolf2021-verbatim-verified-lexer"›. Trivia go into the
  header or the trailing trivia of the token before them, spans come from
  const‹span_at› and const‹advance_list›.

  The driver is generic in the runner ‹R›, which maps a mode and an input to the winning
  rule, the lexeme and the rest. It takes the rest as term‹drop (length p) s›, which
  makes the termination argument independent of ‹R›, and it stops on an empty lexeme,
  which a correct runner never returns.›

fun drive ::
  ‹('m ⇒ 'ch list ⇒ (nat × 'ch list × 'ch list) option) ⇒ ('k, 'p, 'ch, 'm) lexer_spec ⇒
    ('ch ⇒ bool) ⇒ 'm list ⇒ pos ⇒ 'ch list ⇒ ('k, 'ch) lexed × 'ch list × 'm list›
where
  ‹drive R sp is_newline [] q s = (Lexed [] [], s, [])›
| ‹drive R sp is_newline (m # st) q [] = (Lexed [] [], [], m # st)›
| ‹drive R sp is_newline (m # st) q (c # v) =
    (case R m (c # v) of
      None ⇒ (Lexed [] [], c # v, m # st)
    | Some (i, p, _) ⇒
        (case act (sp m ! i) p (m # st) of
          (k, st') ⇒
            if p = [] ∨ st' = [] then (Lexed [] [], c # v, m # st)
            else
              (case drive R sp is_newline st' (advance_list is_newline p q)
                  (drop (length p) (c # v)) of
                (Lexed h ts, r, stf) ⇒
                  (case k of
                    None ⇒ (Lexed (p @ h) ts, r, stf)
                  | Some k ⇒
                      (Lexed [] (⦇tok = k, span = span_at q p, trivia = h⦈ # ts), r, stf)))))›

text ‹A spec whose modes are the numbers below the length of a list, with no rules in
  the other modes. Tables for such a spec are an array indexed by the mode, so the
  driver never compares modes:›

definition list_spec :: ‹'a list list ⇒ nat ⇒ 'a list› where
  ‹list_spec sps m = (if m < length sps then sps ! m else [])›

context symbolic
begin

subsection ‹The invariant›

text ‹‹R› runs the modes of ‹sp› if it returns exactly the winning rule and lexeme of
  const‹first_token› in each mode:›

definition mode_runner ::
  ‹('k, 'p, 'ch, 'm) lexer_spec ⇒ ('m ⇒ 'ch list ⇒ (nat × 'ch list × 'ch list) option) ⇒
    bool›
where
  ‹mode_runner sp R ⟷
    (∀m s i p rest. R m s = Some (i, p, rest) ⟷ first_token (sp m) i p s ∧ s = p @ rest)›

lemma step_iff_mode_runner:
  assumes ‹mode_runner sp R›
  shows ‹step sp (m # st) s (k, p, st', s') ⟷
    (∃i. R m s = Some (i, p, s') ∧ act (sp m ! i) p (m # st) = (k, st') ∧ st' ≠ [])›
  using assms by (auto simp: mode_runner_def step.simps)

lemma lexes_drive:
  assumes ‹mode_runner sp R›
  shows ‹case drive R sp is_newline st q s of
    (l, r, stf) ⇒ lexes sp is_newline st q s l r stf›
  using assms
proof (induction R sp is_newline st q s rule: drive.induct)
  case (1 R sp is_newline q s)
  then show ?case
    by (auto intro: lexes_stop elim: step.cases)
next
  case (2 R sp is_newline m st q)
  have ‹¬ step sp (m # st) [] x› for x
    by (auto elim!: step.cases first_token.cases match_rule.cases)
  then show ?case
    by (auto intro: lexes_stop)
next
  case (3 R sp is_newline m st q c v)
  note runner = step_iff_mode_runner[OF ‹mode_runner sp R›]
  show ?case
  proof (cases ‹R m (c # v)›)
    case None
    then have ‹¬ step sp (m # st) (c # v) x› for x
      using runner by (cases x) auto
    with None show ?thesis
      by (auto intro: lexes_stop)
  next
    case (Some x)
    then obtain i p rest where R: ‹R m (c # v) = Some (i, p, rest)›
      by (cases x) auto
    with ‹mode_runner sp R› have ‹first_token (sp m) i p (c # v)› ‹c # v = p @ rest›
      by (auto simp: mode_runner_def)
    then have ‹p ≠ []› and rest: ‹drop (length p) (c # v) = rest›
      by (auto dest!: first_token_match elim: match_rule.cases)
    obtain k st' where act: ‹act (sp m ! i) p (m # st) = (k, st')›
      by (cases ‹act (sp m ! i) p (m # st)›)
    show ?thesis
    proof (cases ‹st' = []›)
      case True
      then have ‹¬ step sp (m # st) (c # v) y› for y
        using runner R act by (cases y) auto
      with R act True show ?thesis
        by (auto intro: lexes_stop)
    next
      case False
      with R act have step: ‹step sp (m # st) (c # v) (k, p, st', rest)›
        using runner by auto
      let ?d = ‹drive R sp is_newline st' (advance_list is_newline p q) rest›
      from "3.IH"[OF R refl refl act[symmetric]] False ‹p ≠ []› ‹mode_runner sp R› rest
      have IH: ‹case ?d of (l, r, stf) ⇒
        lexes sp is_newline st' (advance_list is_newline p q) rest l r stf›
        by simp
      obtain h ts r stf where d: ‹?d = (Lexed h ts, r, stf)›
        by (metis lexed.exhaust prod.exhaust)
      from IH d step R act False ‹p ≠ []› rest show ?thesis
        by (cases k) (auto intro: lexes_token lexes_trivia)
    qed
  qed
qed

text ‹The driver returns a run of the spec (‹lexes_drive›), and by determinism of the spec
  that run is the only one. This is how Verbatim gets Completeness from Soundness and
  Uniqueness cite‹‹Sects.~V-A--V-C› in "egolf2021-verbatim-verified-lexer"›. Verbatim
  assumes unambiguous rules (each label has one regex); this driver needs only a correct
  runner.›

theorem drive_iff_lexes:
  assumes ‹mode_runner sp R›
  shows ‹drive R sp is_newline st q s = (l, r, stf) ⟷ lexes sp is_newline st q s l r stf›
proof
  assume ‹drive R sp is_newline st q s = (l, r, stf)›
  with lexes_drive[OF assms, of is_newline st q s] show ‹lexes sp is_newline st q s l r stf›
    by simp
next
  assume ‹lexes sp is_newline st q s l r stf›
  with lexes_drive[OF assms, of is_newline st q s]
  show ‹drive R sp is_newline st q s = (l, r, stf)›
    by (auto split: prod.splits dest: lexes_deterministic)
qed

end

context eba
begin

text ‹The driver over the DFA runner of each mode, with a classifier for each mode:›

definition run_lexer ::
  ‹('k, 'p, 'ch, 'm) lexer_spec ⇒ ('m ⇒ 'ch ⇒ nat) ⇒ ('ch ⇒ bool) ⇒ 'm list ⇒ pos ⇒
    'ch list ⇒ ('k, 'ch) lexed × 'ch list × 'm list›
where
  ‹run_lexer sp cls = drive (λm. run_dfa (sp m) (cls m)) sp›

lemma mode_runner_run_dfa:
  assumes ‹⋀m. minterm_classifier (sp m) (cls m)›
  shows ‹mode_runner sp (λm. run_dfa (sp m) (cls m))›
  using run_dfa_Some_iff[OF assms] by (simp add: mode_runner_def)

section ‹Surface theorems›

text ‹With a classifier into the minterms of each mode, the driver returns exactly the
  lexed source, the residue and the final stack of const‹lexes›:›

theorem run_lexer_iff_lexes:
  assumes ‹⋀m. minterm_classifier (sp m) (cls m)›
  shows ‹run_lexer sp cls is_newline st q s = (l, r, stf) ⟷
    lexes sp is_newline st q s l r stf›
  unfolding run_lexer_def by (rule drive_iff_lexes[OF mode_runner_run_dfa[OF assms]])

end

end