Theory TIGER_Tables

(* Author: Basil Fürer *)

theory TIGER_Tables
  imports TIGER_Driver TIGER_Intervals "HOL-Library.Char_ord" "HOL-Library.IArray"
begin

section ‹Tables by evaluation›

text ‹The generator runs once, at definition time. Its output becomes nullary constants
  whose code equations ‹eval› produces, and the run-time lexer only indexes them
  cite‹‹Sect.~17› in "paxson2026-flex-manual"›. The transition and acceptance
  tables are immutable arrays (typ‹'a iarray›). On the interval instance a character
  finds its minterm by binary search in the intervals of all minterms, sorted by their
  lower ends.

  The correctness of a table is that of its generator, instantiated: the runner on
  arrays is const‹eba.run_dfa› and the classifier is a
  const‹eba.minterm_classifier›, for every spec. No proof looks at a table value.

  The byte instance of the interval algebra is interpreted here, after the generator
  (an interpretation carries only the locale constants defined before it).›

subsection ‹The runner on arrays›

text ‹The scan of const‹scan› with array lookups:›

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

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

text ‹The two scans agree as long as no transition leaves the table:›

lemma scan_ia_eq_scan:
  assumes ‹⋀q c. q < length T ⟹ T ! q ! cls c < length T› ‹q < length T›
  shows ‹scan_ia (IArray (map IArray T)) (IArray A) cls d q n s b = scan T A cls d q n s b›
  using assms(2) by (induct s arbitrary: q n b) (simp_all add: Let_def assms(1))

context eba
begin

lemma run_tables_ia_eq_run_dfa:
  assumes ‹minterm_classifier rs cls›
  shows ‹run_tables_ia (IArray (map IArray (dfa_trans (mode_dfa rs))))
    (IArray (dfa_accept (mode_dfa rs))) cls (dead_state rs) s = run_dfa rs cls s›
proof -
  let ?T = ‹dfa_trans (mode_dfa rs)›
  let ?A = ‹dfa_accept (mode_dfa rs)›
  have len: ‹length ?T = length (dfa_states (mode_dfa rs))›
    by (simp add: mode_dfa_def length_dfa_trans)
  have ‹0 < length (dfa_states (mode_dfa rs))›
    using dfa_run_correct[of rs ‹[]›] by (simp add: dfa_run_def)
  then have ‹scan_ia (IArray (map IArray ?T)) (IArray ?A) cls (dead_state rs) 0 0 s None =
    scan ?T ?A cls (dead_state rs) 0 0 s None›
    by (intro scan_ia_eq_scan) (use trans_step[OF assms] len in auto)
  then show ?thesis
    by (simp add: run_tables_ia_def run_dfa_def run_tables_def)
qed

end

subsection ‹Binary search›

text ‹In an array sorted by first components, the search finds the last entry between
  ‹l› and ‹h› whose first component is at most ‹c›:›

function bsearch :: ‹('a::linorder × 'b) iarray ⇒ 'a ⇒ nat ⇒ nat ⇒ nat› where
  ‹bsearch t c l h =
    (if Suc l < h then
       if fst (t !! ((l + h) div 2)) ≤ c then bsearch t c ((l + h) div 2) h
       else bsearch t c l ((l + h) div 2)
     else l)›
  by pat_completeness auto

termination
  by (relation ‹measure (λ(t, c, l, h). h - l)›) auto

declare bsearch.simps[simp del]

lemma bsearch:
  assumes ‹sorted (map fst (IArray.list_of t))› ‹l < h› ‹h ≤ IArray.length t›
    and ‹fst (t !! l) ≤ c›
  shows ‹l ≤ bsearch t c l h ∧ bsearch t c l h < h ∧ fst (t !! bsearch t c l h) ≤ c ∧
    (∀j. bsearch t c l h < j ⟶ j < h ⟶ c < fst (t !! j))›
  using assms(2-)
proof (induction ‹h - l› arbitrary: l h rule: less_induct)
  case less
  let ?m = ‹(l + h) div 2›
  show ?case
  proof (cases ‹Suc l < h›)
    case False
    then have ‹bsearch t c l h = l›
      by (simp add: bsearch.simps)
    with less.prems False show ?thesis
      by auto
  next
    case True
    then have m: ‹l < ?m› ‹?m < h›
      by presburger+
    then have d: ‹h - ?m < h - l› ‹?m - l < h - l›
      by linarith+
    show ?thesis
    proof (cases ‹fst (t !! ?m) ≤ c›)
      case True
      with less.hyps[of h ?m] less.prems m d have ‹?m ≤ bsearch t c ?m h ∧
        bsearch t c ?m h < h ∧ fst (t !! bsearch t c ?m h) ≤ c ∧
        (∀j. bsearch t c ?m h < j ⟶ j < h ⟶ c < fst (t !! j))›
        by simp
      moreover from True ‹Suc l < h› have ‹bsearch t c l h = bsearch t c ?m h›
        by (subst bsearch.simps) simp
      ultimately show ?thesis
        using m by auto
    next
      case False
      have ‹c < fst (t !! j)› if ‹?m ≤ j› ‹j < h› for j
        using False sorted_nth_mono[OF assms(1) that(1)] that(2) less.prems by fastforce
      moreover from False ‹Suc l < h› have ‹bsearch t c l h = bsearch t c l ?m›
        by (subst bsearch.simps) simp
      ultimately show ?thesis
        using less.hyps[of ?m l] less.prems m d by (simp, meson not_le)
    qed
  qed
qed

subsection ‹The minterm table of the interval instance›

text ‹The minterm table lists every interval of every minterm with the number of its
  minterm, sorted by lower ends. A character looks up the last interval starting at or
  below it:›

definition class_table :: ‹('s × 'ch::linorder cls) list ⇒ ('ch × 'ch × nat) list› where
  ‹class_table M = sort_key fst
    (concat (map (λk. map (λ(l, h). (l, h, k)) (snd (M ! k))) [0 ..< length M]))›

definition class_of :: ‹('ch::linorder × 'ch × nat) iarray ⇒ 'ch ⇒ nat› where
  ‹class_of t c = snd (snd (t !! bsearch t c 0 (IArray.length t)))›

lemma mem_class_table:
  ‹x ∈ set (class_table M) ⟷
    (∃k l h. k < length M ∧ x = (l, h, k) ∧ (l, h) ∈ set (snd (M ! k)))›
  by (force simp: class_table_def)

text ‹A list of well-formed, pairwise disjoint classes is a partition of the characters
  it covers. The lookup in its table finds the class of each character it covers:›

context discrete_order
begin

text ‹Two different intervals of a separated class share no character:›

lemma separated_disjoint:
  assumes ‹separated p› ‹x ∈ set p› ‹y ∈ set p› ‹x ≠ y›
    and ‹fst x ≤ c› ‹c ≤ snd x› ‹fst y ≤ c› ‹c ≤ snd y›
  shows False
proof -
  have sep: ‹snd (p ! i) < top ∧ succ (snd (p ! i)) < fst (p ! j)›
    if ‹i < j› ‹j < length p› for i j
    using assms(1) that by (simp add: separated_def sorted_wrt_iff_nth_less)
  have *: ‹False› if ‹u ∈ set p› ‹w ∈ set p› ‹u ≠ w› ‹c ≤ snd u› ‹fst w ≤ c›
    ‹index_of p u < index_of p w› for u w
  proof -
    from that have ‹snd u < top› ‹succ (snd u) < fst w›
      using sep[of ‹index_of p u› ‹index_of p w›] index_of_less[of w p] nth_index_of[of u p]
        nth_index_of[of w p]
      by simp_all
    with less_succ[of ‹snd u›] that(4,5) show False
      by (meson le_less_trans less_le_not_le order.strict_trans)
  qed
  have ‹index_of p x ≠ index_of p y›
    using assms(2-4) by (metis nth_index_of)
  then have ‹index_of p x < index_of p y ∨ index_of p y < index_of p x›
    by (rule neq_iff[THEN iffD1])
  with *[of x y] *[of y x] assms(2-8) show False
    by blast
qed

text ‹The intervals of different entries of the table of a partition share no
  character, and each entry is nonempty:›

lemma class_table_disjoint:
  assumes wf: ‹⋀k. k < length M ⟹ wf_cls (snd (M ! k))›
    and disj: ‹⋀i j c. ⟦ i < length M; j < length M; in_cls (snd (M ! i)) c;
      in_cls (snd (M ! j)) c ⟧ ⟹ i = j›
    and ‹x ∈ set (class_table M)› ‹y ∈ set (class_table M)›
    and ‹fst x ≤ c› ‹c ≤ fst (snd x)› ‹fst y ≤ c› ‹c ≤ fst (snd y)›
  shows ‹x = y›
proof -
  from assms(3) obtain k l h where x: ‹k < length M› ‹x = (l, h, k)› ‹(l, h) ∈ set (snd (M ! k))›
    by (auto simp: mem_class_table)
  from assms(4) obtain k' l' h' where
    y: ‹k' < length M› ‹y = (l', h', k')› ‹(l', h') ∈ set (snd (M ! k'))›
    by (auto simp: mem_class_table)
  from x y assms(5-8) have ‹in_cls (snd (M ! k)) c› ‹in_cls (snd (M ! k')) c›
    by (auto simp: in_cls_iff intro: bexI[rotated])
  with disj x(1) y(1) have ‹k' = k›
    by blast
  from wf[OF x(1)] have ‹separated (snd (M ! k))›
    by (simp add: wf_cls_def)
  with separated_disjoint[of ‹snd (M ! k)› ‹(l, h)› ‹(l', h')› c] x y ‹k' = k› assms(5-8)
  show ‹x = y›
    by fastforce
qed

lemma class_table_nonempty:
  assumes wf: ‹⋀k. k < length M ⟹ wf_cls (snd (M ! k))›
    and ‹x ∈ set (class_table M)›
  shows ‹fst x ≤ fst (snd x)›
proof -
  from assms(2) obtain k l h where
    ‹k < length M› ‹x = (l, h, k)› ‹(l, h) ∈ set (snd (M ! k))›
    by (auto simp: mem_class_table)
  with wf[of k] show ?thesis
    by (auto simp: wf_cls_def in_range_iff)
qed

lemma class_of_partition:
  assumes wf: ‹⋀k. k < length M ⟹ wf_cls (snd (M ! k))›
    and disj: ‹⋀i j c. ⟦ i < length M; j < length M; in_cls (snd (M ! i)) c;
      in_cls (snd (M ! j)) c ⟧ ⟹ i = j›
    and k: ‹k < length M› ‹in_cls (snd (M ! k)) c›
  shows ‹class_of (IArray (class_table M)) c < length M ∧
    in_cls (snd (M ! class_of (IArray (class_table M)) c)) c›
proof -
  let ?xs = ‹class_table M›
  let ?i = ‹bsearch (IArray ?xs) c 0 (length ?xs)›
  have sorted: ‹sorted (map fst ?xs)›
    by (simp add: class_table_def)
  from k obtain l h where ‹(l, h) ∈ set (snd (M ! k))› ‹l ≤ c› ‹c ≤ h›
    by (auto simp: in_cls_iff)
  with k(1) obtain j where j: ‹j < length ?xs› ‹?xs ! j = (l, h, k)›
    by (metis in_set_conv_nth mem_class_table)
  moreover from j(1) have len: ‹0 < length ?xs›
    by linarith
  moreover have ‹fst (?xs ! 0) ≤ c›
    using sorted_nth_mono[OF sorted, of 0 j] j ‹l ≤ c› len by simp
  ultimately
  have i: ‹?i < length ?xs› ‹fst (?xs ! ?i) ≤ c›
    ‹∀j'. ?i < j' ⟶ j' < length ?xs ⟶ c < fst (?xs ! j')›
    using bsearch[of ‹IArray ?xs› 0 ‹length ?xs› c] sorted by auto
  with j ‹l ≤ c› have ‹j ≤ ?i›
    by (metis fst_conv not_le)
  with sorted_nth_mono[OF sorted this] i(1) j have ‹l ≤ fst (?xs ! ?i)›
    by simp
  moreover have ‹fst (?xs ! ?i) ≤ fst (snd (?xs ! ?i))›
    using class_table_nonempty[OF wf] i(1) by simp
  ultimately have ‹?xs ! ?i = ?xs ! j›
    using class_table_disjoint[OF wf disj, where x = ‹?xs ! ?i› and y = ‹?xs ! j›
      and c = ‹fst (?xs ! ?i)›] i(1,2) j nth_mem[OF j(1)] order.trans[OF i(2) ‹c ≤ h›]
    by simp
  with j k show ?thesis
    by (simp add: class_of_def)
qed

end

context bounded_discrete_order
begin

lemma wf_minterms: ‹(S, μ) ∈ set (minterms P) ⟹ wf_cls μ›
  by (induct P arbitrary: S μ) (auto simp: wf_top wf_conj)

text ‹The lookup in the minterm table of a mode is a classifier into its minterms:›

lemma minterm_classifier_class_of:
  ‹minterm_classifier rs (class_of (IArray (class_table (mode_minterms rs))))›
  unfolding minterm_classifier_def
proof
  fix c
  let ?M = ‹mode_minterms rs›
  have wf: ‹wf_cls (snd (?M ! k))› if ‹k < length ?M› for k
    using wf_minterms nth_mem[OF that] by (metis mode_minterms_def prod.collapse)
  obtain S μ where ‹(S, μ) ∈ set ?M› ‹in_cls μ c›
    using minterms_cover[of ‹mode_atoms rs› c] by (auto simp: mode_minterms_def)
  then obtain k where ‹k < length ?M› ‹in_cls (snd (?M ! k)) c›
    by (metis in_set_conv_nth snd_conv)
  from class_of_partition[OF wf _ this] minterms_disjoint
  show ‹class_of (IArray (class_table ?M)) c < length ?M ∧
    in_cls (snd (?M ! class_of (IArray (class_table ?M)) c)) c›
    by (metis mode_minterms_def)
qed

end

subsection ‹The byte instance›

text ‹Bytes are the first instance. The interpretation follows the generator, so it
  carries the generator's constants (‹char_mode_dfa›) and theorems.›

lemma of_char_le_255: ‹of_char c ≤ (255::nat)›
  using nat_of_char_less_256[of c] by linarith

lemma of_char_minus_mod: ‹(of_char c - Suc 0) mod 256 = (of_char c - Suc 0 :: nat)›
  by (simp add: less_imp_diff_less)

definition char_succ :: ‹char ⇒ char› where
  ‹char_succ c = char_of (Suc (of_char c))›

definition char_pred :: ‹char ⇒ char› where
  ‹char_pred c = char_of (of_char c - 1 :: nat)›

text ‹Bytes are a bounded discrete order:›

global_interpretation char_cls:
  bounded_discrete_order ‹char_of (0::nat)› ‹char_of (255::nat)› char_succ char_pred
  defines char_clip = char_cls.clip
    and char_merge = char_cls.merge
    and char_norm = char_cls.cls_norm
    and char_compl_from = char_cls.compl_from
    and char_top = char_cls.cls_top
    and char_disj = char_cls.cls_disj
    and char_neg = char_cls.cls_neg
    and char_conj = char_cls.cls_conj
    and char_minterms = char_cls.minterms
    and char_mode_minterms = char_cls.mode_minterms
    and char_mode_dfa = char_cls.mode_dfa
    and char_dead_state = char_cls.dead_state
  by unfold_locales
    (auto simp: less_eq_char_def less_char_def char_succ_def char_pred_def of_char_le_255
      of_char_minus_mod)

text ‹The ‹defines› clause does not fold const‹char_minterms› into the
  equations of ‹char_cls.minterms›, so we fold it by hand:›

lemmas char_minterms_code[code] =
  char_cls.minterms.simps[unfolded char_top_def char_conj_def char_neg_def,
    folded char_minterms_def char_top_def char_conj_def char_neg_def]

text ‹The ‹defines› clause does not fold the generator's equations either:›

lemmas char_mode_minterms_code[code] =
  char_cls.mode_minterms_def[unfolded char_top_def char_conj_def char_neg_def,
    folded char_mode_minterms_def char_minterms_def char_top_def char_conj_def char_neg_def]

lemmas char_mode_dfa_code[code] =
  char_cls.mode_dfa_def[unfolded char_top_def char_conj_def char_neg_def,
    folded char_mode_dfa_def char_mode_minterms_def char_top_def char_conj_def char_neg_def]

lemmas char_dead_state_code[code] =
  char_cls.dead_state_def[unfolded char_top_def char_conj_def char_neg_def,
    folded char_dead_state_def char_mode_dfa_def char_top_def char_conj_def char_neg_def]

text ‹In the theorems of the interpretation the constants appear unfolded:›

lemma char_mode_minterms_eq: ‹char_mode_minterms = char_cls.mode_minterms›
  by (simp add: char_mode_minterms_def char_top_def char_conj_def char_neg_def)

lemma char_mode_dfa_eq: ‹char_mode_dfa = char_cls.mode_dfa›
  by (simp add: char_mode_dfa_def char_top_def char_conj_def char_neg_def)

lemma char_dead_state_eq: ‹char_dead_state = char_cls.dead_state›
  by (simp add: char_dead_state_def char_top_def char_conj_def char_neg_def)

text ‹The tables of a mode on bytes are the minterm table, the transitions, the
  acceptance and the dead state. One constant holds all four, so one evaluation
  produces them:›

type_synonym char_tables = ‹(char × char × nat) iarray × nat iarray iarray × nat option iarray × nat›

definition char_tables :: ‹('k, char cls, char, 'm) rule list ⇒ char_tables› where
  ‹char_tables rs = (IArray (class_table (char_mode_minterms rs)),
    IArray (map IArray (dfa_trans (char_mode_dfa rs))), IArray (dfa_accept (char_mode_dfa rs)),
    char_dead_state rs)›

fun run_char :: ‹char_tables ⇒ char list ⇒ (nat × char list × char list) option› where
  ‹run_char (C, T, A, d) = run_tables_ia T A (class_of C) d›

text ‹The runner on the tables of a mode is const‹char_cls.run_dfa›:›

lemma run_char_tables:
  ‹run_char (char_tables rs) =
    char_cls.run_dfa rs (class_of (IArray (class_table (char_cls.mode_minterms rs))))›
  by (simp add: fun_eq_iff char_tables_def char_mode_minterms_eq char_mode_dfa_eq
      char_dead_state_eq char_cls.run_tables_ia_eq_run_dfa char_cls.minterm_classifier_class_of)

text ‹The lexer on bytes takes the tables of all modes as one array and an index ‹ix›
  into it for each mode, so modes with the same rules share their tables and the driver
  never compares modes. A mode whose index is outside the array has no rules:›

definition char_lexer ::
  ‹char_tables iarray ⇒ ('m ⇒ nat) ⇒ ('k, char cls, char, 'm) lexer_spec ⇒
    (char ⇒ bool) ⇒ 'm list ⇒ pos ⇒ char list ⇒ ('k, char) lexed × char list × 'm list›
where
  ‹char_lexer TT ix =
    drive (λm. if ix m < IArray.length TT then run_char (TT !! ix m) else (λ_. None))›

text ‹The runner of const‹char_lexer› runs the modes of ‹sp› if the index of each
  mode holds its tables or is outside the array for a mode without rules:›

lemma mode_runner_char_lexer:
  assumes ‹⋀m. if ix m < IArray.length TT then TT !! ix m = char_tables (sp m) else sp m = []›
  shows ‹char_cls.mode_runner sp
    (λm. if ix m < IArray.length TT then run_char (TT !! ix m) else (λ_. None))›
  unfolding char_cls.mode_runner_def
proof (intro allI)
  fix m s i p rest
  show ‹(if ix m < IArray.length TT then run_char (TT !! ix m) else (λ_. None)) s =
      Some (i, p, rest) ⟷ char_cls.first_token (sp m) i p s ∧ s = p @ rest›
    using assms[of m]
    by (auto simp: run_char_tables char_cls.run_dfa_Some_iff char_cls.minterm_classifier_class_of
        char_cls.first_token.simps split: if_splits)
qed

text ‹If the index of each mode holds its tables, the lexer on bytes is
  const‹char_cls.lexes›:›

theorem char_lexer_iff_lexes:
  assumes ‹∀m. ix m < IArray.length TT ∧ TT !! ix m = char_tables (sp m)›
  shows ‹char_lexer TT ix sp is_newline st q s = (l, r, stf) ⟷
    char_cls.lexes sp is_newline st q s l r stf›
  unfolding char_lexer_def
  by (rule char_cls.drive_iff_lexes[OF mode_runner_char_lexer]) (use assms in auto)

text ‹The tables of a spec on the modes ‹0, …, n - 1› (const‹list_spec›), with the
  identity as index:›

definition char_lexer_tables :: ‹('k, char cls, char, nat) rule list list ⇒ char_tables iarray›
where
  ‹char_lexer_tables sps = IArray (map char_tables sps)›

theorem char_lexer_list_iff_lexes:
  ‹char_lexer (char_lexer_tables sps) id (list_spec sps) is_newline st q s = (l, r, stf) ⟷
    char_cls.lexes (list_spec sps) is_newline st q s l r stf›
  unfolding char_lexer_def
  by (rule char_cls.drive_iff_lexes[OF mode_runner_char_lexer])
    (simp add: char_lexer_tables_def list_spec_def)

subsection ‹Code equations by evaluation›

text ‹‹eval_eq ctxt t› evaluates the closed term ‹t› to a value ‹v› and proves ‹t = v›
  by ‹eval›. ‹eval_table b t› notes this equation as ‹b› for a nullary constant ‹t›.
  Declared ‹[code]›, the equation replaces the definition in generated code:›

ML ‹
fun eval_eq ctxt t =
  let
    val v = Value_Command.value ctxt t
    val eqn = HOLogic.mk_Trueprop (HOLogic.mk_eq (t, v))
  in
    Goal.prove ctxt [] [] eqn (fn {context = ctxt, ...} =>
      CONVERSION (Code_Runtime.dynamic_holds_conv ctxt) 1 THEN resolve_tac ctxt [TrueI] 1)
  end

fun eval_table (b, t) lthy = snd (Local_Theory.note ((b, []), [eval_eq lthy t]) lthy)
›

end