Theory TIGER_Codepoints

(* Author: Basil Fürer *)

theory TIGER_Codepoints
  imports TIGER_Tables "HOL-Library.Code_Target_Nat"
begin

section ‹The codepoint instance›

text ‹Codepoints are natural numbers, and the range is
  ‹0 .. 0x10FFFF›. Surrogates are in the range: excluding them is the business of the
  decoder. As typ‹nat› is unbounded, character classes are no Boolean algebra on it
  (the negation of a class holds of no number above the range). We read a class at the
  number clamped to the range instead, so a number above the range lexes as
  ‹U+10FFFF›, and prove that on an input in range this reading is the plain one
  (const‹in_cls›).

  Generated code represents typ‹nat› by target integers (‹Code_Target_Nat›):
  in the default unary representation ‹0x10FFFF› alone has a million constructors.

  The lexer ‹cp_lexer› takes the tables of the modes as one array and a
  mode index into it, so modes with the same rules share their tables. Its surface
  theorems hold for every index under which each mode finds its tables. A spec on
  codepoints is read on bytes by ‹char_spec›, which keeps the part of each
  class below ‹0x100›.›

subsection ‹Classes read in the range›

locale range_order = discrete_order bot top succ pred
  for bot top :: ‹'ch::linorder› and succ pred
begin

definition clamp :: ‹'ch ⇒ 'ch› where
  ‹clamp c = (if c < bot then bot else if top < c then top else c)›

definition in_clamped :: ‹'ch cls ⇒ 'ch ⇒ bool› where
  ‹in_clamped p c ⟷ in_cls p (clamp c)›

definition sat_clamped :: ‹'ch cls ⇒ bool› where
  ‹sat_clamped p ⟷ sat_cls (clip p)›

lemma clamp_in_range: ‹bot ≤ clamp c ∧ clamp c ≤ top›
  using bot_le_top by (auto simp: clamp_def)

lemma clamp_id: ‹⟦ bot ≤ c; c ≤ top ⟧ ⟹ clamp c = c›
  by (auto simp: clamp_def)

lemma in_clamped_iff: ‹⟦ bot ≤ c; c ≤ top ⟧ ⟹ in_clamped p c ⟷ in_cls p c›
  by (simp add: in_clamped_def clamp_id)

text ‹Read in the range, classes form an effective Boolean algebra:›

sublocale eba in_clamped cls_top cls_bot cls_conj cls_disj cls_neg sat_clamped
proof unfold_locales
  fix p
  show ‹sat_clamped p ⟷ (∃c. in_clamped p c)›
    using clamp_in_range clamp_id
    by (auto simp: sat_clamped_def in_clamped_def sat_cls_iff in_cls_clip) metis
qed (simp_all add: in_clamped_def clamp_in_range in_cls_top in_cls_bot in_cls_conj in_cls_disj
    in_cls_neg)

end

subsection ‹Semantics that agree on the input›

text ‹The judgments read the denotation only at the characters of the input. Two
  denotations that agree there give the same lexing:›

lemma star_cong:
  assumes ‹⋀w. set w ⊆ A ⟹ w ∈ L ⟷ w ∈ L'› ‹w ∈ star L› ‹set w ⊆ A›
  shows ‹w ∈ star L'›
  using assms(2,3) by induct (auto simp: assms(1))

lemma conc_cong:
  assumes ‹⋀w. set w ⊆ A ⟹ w ∈ L1 ⟷ w ∈ L1'› ‹⋀w. set w ⊆ A ⟹ w ∈ L2 ⟷ w ∈ L2'›
    and ‹set w ⊆ A›
  shows ‹w ∈ L1 @@ L2 ⟷ w ∈ L1' @@ L2'›
proof
  assume ‹w ∈ L1 @@ L2›
  then obtain u v where ‹w = u @ v› ‹u ∈ L1› ‹v ∈ L2›
    by blast
  with assms show ‹w ∈ L1' @@ L2'›
    by auto
next
  assume ‹w ∈ L1' @@ L2'›
  then obtain u v where ‹w = u @ v› ‹u ∈ L1'› ‹v ∈ L2'›
    by blast
  with assms show ‹w ∈ L1 @@ L2›
    by auto
qed

lemma lang_cong:
  assumes ‹⋀p c. c ∈ A ⟹ sem p c = sem' p c› ‹set w ⊆ A›
  shows ‹w ∈ symbolic.lang sem r ⟷ w ∈ symbolic.lang sem' r›
  using assms(2)
proof (induction r arbitrary: w)
  case (Atom p)
  then show ?case
    by (auto simp: assms(1) symbolic.lang.simps)
next
  case (Times r1 r2)
  then show ?case
    using conc_cong[of A ‹symbolic.lang sem r1› ‹symbolic.lang sem' r1›
      ‹symbolic.lang sem r2› ‹symbolic.lang sem' r2› w]
    by (simp add: symbolic.lang.simps)
next
  case (Star r)
  then show ?case
    using star_cong[of A ‹symbolic.lang sem r› ‹symbolic.lang sem' r› w]
      star_cong[of A ‹symbolic.lang sem' r› ‹symbolic.lang sem r› w]
    by (auto simp: symbolic.lang.simps)
qed (auto simp: symbolic.lang.simps)

text ‹In the rest of this subsection ‹sem› and ‹sem'› agree on ‹A›:›

context
  fixes A and sem sem' :: ‹'p ⇒ 'ch ⇒ bool›
  assumes agree: ‹⋀p c. c ∈ A ⟹ sem p c = sem' p c›
begin

lemma match_rule_cong:
  ‹set w ⊆ A ⟹ symbolic.match_rule sem ρ w ⟷ symbolic.match_rule sem' ρ w›
  using lang_cong[where A = A and sem = sem and sem' = sem', OF agree]
  by (simp add: symbolic.match_rule.simps)

lemma max_pref_cong:
  assumes ‹set s ⊆ A›
  shows ‹symbolic.max_pref sem (rs :: ('k, 'p, 'ch, 'm) rule list) p s ⟷
    symbolic.max_pref sem' rs p s›
proof -
  have mr: ‹symbolic.match_rule sem ρ' p' ⟷ symbolic.match_rule sem' ρ' p'›
    if ‹s = p' @ u'› for ρ' :: ‹('k, 'p, 'ch, 'm) rule› and p' u'
    using match_rule_cong[of p'] that assms by simp
  show ?thesis
    unfolding symbolic.max_pref.simps by (metis mr)
qed

lemma first_token_cong:
  assumes ‹set s ⊆ A›
  shows ‹symbolic.first_token sem (rs :: ('k, 'p, 'ch, 'm) rule list) i p s ⟷
    symbolic.first_token sem' rs i p s›
proof -
  have ‹set p ⊆ A› if ‹∃u. s = p @ u›
    using that assms by auto
  then have ‹(∃u. s = p @ u) ⟹
      symbolic.match_rule sem ρ p ⟷ symbolic.match_rule sem' ρ p›
    for ρ :: ‹('k, 'p, 'ch, 'm) rule›
    using match_rule_cong by blast
  then show ?thesis
    using max_pref_cong[OF assms] symbolic.max_prefD[of sem rs p s]
      symbolic.max_prefD[of sem' rs p s]
    unfolding symbolic.first_token.simps by metis
qed

lemma step_cong:
  assumes ‹set s ⊆ A›
  shows ‹symbolic.step sem sp st s x ⟷ symbolic.step sem' sp st s x›
  by (simp add: symbolic.step.simps first_token_cong[OF assms])

lemma lexes_cong_imp:
  assumes ‹symbolic.lexes sem sp is_newline st q s l r stf› ‹set s ⊆ A›
  shows ‹symbolic.lexes sem' sp is_newline st q s l r stf›
  using assms
proof (induction rule: symbolic.lexes.induct[of sem, consumes 1, case_names stop token trivia])
  case (stop st s q)
  then have ‹¬ symbolic.step sem' sp st s x› for x
    using step_cong[of s sp st x] by blast
  then show ?case
    by (rule symbolic.lexes_stop)
next
  case (token st s k p st' s' q h ts r stf)
  from token.hyps(1) token.prems have ‹set s' ⊆ A›
    by (auto simp: symbolic.step.simps)
  from token.hyps(1) have ‹symbolic.step sem' sp st s (Some k, p, st', s')›
    by (simp add: step_cong[OF token.prems])
  from this token.IH[OF ‹set s' ⊆ A›] show ?case
    by (rule symbolic.lexes_token)
next
  case (trivia st s p st' s' q h ts r stf)
  from trivia.hyps(1) trivia.prems have ‹set s' ⊆ A›
    by (auto simp: symbolic.step.simps)
  from trivia.hyps(1) have ‹symbolic.step sem' sp st s (None, p, st', s')›
    by (simp add: step_cong[OF trivia.prems])
  from this trivia.IH[OF ‹set s' ⊆ A›] show ?case
    by (rule symbolic.lexes_trivia)
qed

end

lemma lexes_cong:
  assumes ‹⋀p c. c ∈ A ⟹ sem p c = sem' p c› ‹set s ⊆ A›
  shows ‹symbolic.lexes sem sp is_newline st q s l r stf ⟷
    symbolic.lexes sem' sp is_newline st q s l r stf›
  using lexes_cong_imp[of A sem sem'] lexes_cong_imp[of A sem' sem] assms by (metis (no_types))

context range_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 of the clamped character in the minterm table of a mode is a
  classifier into its minterms. Above the range it is the class of ‹top›:›

lemma minterm_classifier_class_of_clamp:
  ‹minterm_classifier rs (λc. class_of (IArray (class_table (mode_minterms rs))) (clamp c))›
  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)
  have disj: ‹i = j›
    if ‹i < length ?M› ‹j < length ?M› ‹in_cls (snd (?M ! i)) d› ‹in_cls (snd (?M ! j)) d›
    for i j d
  proof -
    from that(1,3) wf[of i] have ‹bot ≤ d› ‹d ≤ top›
      by (auto simp: wf_cls_def in_range_iff in_cls_iff)
    with that minterms_disjoint show ?thesis
      by (metis in_clamped_iff mode_minterms_def)
  qed
  obtain S μ where ‹(S, μ) ∈ set ?M› ‹in_clamped μ 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)) (clamp c)›
    by (metis in_set_conv_nth snd_conv in_clamped_def)
  from class_of_partition[OF wf disj this]
  show ‹class_of (IArray (class_table ?M)) (clamp c) < length ?M ∧
    in_clamped (snd (?M ! class_of (IArray (class_table ?M)) (clamp c))) c›
    by (simp add: in_clamped_def)
qed

end

subsection ‹The interpretation›

global_interpretation cp_cls: range_order ‹0::nat› ‹0x10FFFF› Suc ‹λc. c - 1›
  defines cp_clamp = cp_cls.clamp
    and cp_clip = cp_cls.clip
    and cp_sat = cp_cls.sat_clamped
    and cp_merge = cp_cls.merge
    and cp_norm = cp_cls.cls_norm
    and cp_compl_from = cp_cls.compl_from
    and cp_top = cp_cls.cls_top
    and cp_disj = cp_cls.cls_disj
    and cp_neg = cp_cls.cls_neg
    and cp_conj = cp_cls.cls_conj
    and cp_minterms = cp_cls.minterms
    and cp_mode_minterms = cp_cls.mode_minterms
    and cp_mode_dfa = cp_cls.mode_dfa
    and cp_dead_state = cp_cls.dead_state
  by unfold_locales auto

text ‹As for bytes, we fold the defined constants into the generator's equations by
  hand:›

lemmas cp_sat_code[code] =
  cp_cls.sat_clamped_def[folded cp_clip_def cp_sat_def]

lemmas cp_minterms_code[code] =
  cp_cls.minterms.simps[unfolded cp_top_def cp_conj_def cp_neg_def cp_sat_def,
    folded cp_minterms_def cp_top_def cp_conj_def cp_neg_def cp_sat_def]

lemmas cp_mode_minterms_code[code] =
  cp_cls.mode_minterms_def[unfolded cp_top_def cp_conj_def cp_neg_def cp_sat_def,
    folded cp_mode_minterms_def cp_minterms_def cp_top_def cp_conj_def cp_neg_def cp_sat_def]

lemmas cp_mode_dfa_code[code] =
  cp_cls.mode_dfa_def[unfolded cp_top_def cp_conj_def cp_neg_def cp_sat_def,
    folded cp_mode_dfa_def cp_mode_minterms_def cp_top_def cp_conj_def cp_neg_def cp_sat_def]

lemmas cp_dead_state_code[code] =
  cp_cls.dead_state_def[unfolded cp_top_def cp_conj_def cp_neg_def cp_sat_def,
    folded cp_dead_state_def cp_mode_dfa_def cp_top_def cp_conj_def cp_neg_def cp_sat_def]

lemma cp_mode_minterms_eq: ‹cp_mode_minterms = cp_cls.mode_minterms›
  by (simp add: cp_mode_minterms_def cp_top_def cp_conj_def cp_neg_def cp_sat_def)

lemma cp_mode_dfa_eq: ‹cp_mode_dfa = cp_cls.mode_dfa›
  by (simp add: cp_mode_dfa_def cp_top_def cp_conj_def cp_neg_def cp_sat_def)

lemma cp_dead_state_eq: ‹cp_dead_state = cp_cls.dead_state›
  by (simp add: cp_dead_state_def cp_top_def cp_conj_def cp_neg_def cp_sat_def)

text ‹Above the range, the classifier reads a number as ‹U+10FFFF›:›

lemma cp_clamp_eq: ‹cp_clamp c = min c 0x10FFFF›
  by (simp add: cp_cls.clamp_def)

subsection ‹Tables and the lexer›

text ‹The tables of a mode on codepoints, as for bytes:›

type_synonym cp_tables = ‹(nat × nat × nat) iarray × nat iarray iarray × nat option iarray × nat›

definition cp_tables :: ‹('k, nat cls, nat, 'm) rule list ⇒ cp_tables› where
  ‹cp_tables rs = (IArray (class_table (cp_mode_minterms rs)),
    IArray (map IArray (dfa_trans (cp_mode_dfa rs))), IArray (dfa_accept (cp_mode_dfa rs)),
    cp_dead_state rs)›

text ‹The sizes of the tables of a mode, on codepoints or bytes: the intervals of the class
  table, the minterms (the columns of the transitions) and the states:›

definition table_size :: ‹'c iarray × 'n iarray iarray × 'a × 'd ⇒ nat × nat × nat› where
  ‹table_size t = (case t of (C, T, A, d) ⇒
     (IArray.length C, IArray.length (T !! 0), IArray.length T))›

fun run_cp :: ‹cp_tables ⇒ nat list ⇒ (nat × nat list × nat list) option› where
  ‹run_cp (C, T, A, d) = run_tables_ia T A (λc. class_of C (cp_clamp c)) d›

lemma run_cp_tables:
  ‹run_cp (cp_tables rs) =
    cp_cls.run_dfa rs (λc. class_of (IArray (class_table (cp_cls.mode_minterms rs))) (cp_clamp c))›
  by (simp add: fun_eq_iff cp_tables_def cp_mode_minterms_eq cp_mode_dfa_eq cp_dead_state_eq
      cp_cls.run_tables_ia_eq_run_dfa cp_cls.minterm_classifier_class_of_clamp)

text ‹The lexer on codepoints 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 cp_lexer ::
  ‹cp_tables iarray ⇒ ('m ⇒ nat) ⇒ ('k, nat cls, nat, 'm) lexer_spec ⇒ (nat ⇒ bool) ⇒
    'm list ⇒ pos ⇒ nat list ⇒ ('k, nat) lexed × nat list × 'm list›
where
  ‹cp_lexer TT ix =
    drive (λm. if ix m < IArray.length TT then run_cp (TT !! ix m) else (λ_. None))›

text ‹The runner of const‹cp_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_cp_lexer:
  assumes ‹⋀m. if ix m < IArray.length TT then TT !! ix m = cp_tables (sp m) else sp m = []›
  shows ‹cp_cls.mode_runner sp
    (λm. if ix m < IArray.length TT then run_cp (TT !! ix m) else (λ_. None))›
  unfolding cp_cls.mode_runner_def
proof (intro allI)
  fix m s i p rest
  show ‹(if ix m < IArray.length TT then run_cp (TT !! ix m) else (λ_. None)) s =
      Some (i, p, rest) ⟷ cp_cls.first_token (sp m) i p s ∧ s = p @ rest›
    using assms[of m]
    by (auto simp: run_cp_tables cp_cls.run_dfa_Some_iff cp_cls.minterm_classifier_class_of_clamp
        cp_cls.first_token.simps split: if_splits)
qed

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

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

lemma cp_lexer_tables_index:
  ‹if id m < IArray.length (cp_lexer_tables sps) then cp_lexer_tables sps !! id m =
    cp_tables (list_spec sps m) else list_spec sps m = []›
  by (simp add: cp_lexer_tables_def list_spec_def)

theorem cp_lexer_list_iff_lexes:
  ‹cp_lexer (cp_lexer_tables sps) id (list_spec sps) is_newline st q s = (l, r, stf) ⟷
    cp_cls.lexes (list_spec sps) is_newline st q s l r stf›
  unfolding cp_lexer_def
  by (rule cp_cls.drive_iff_lexes[OF mode_runner_cp_lexer[OF cp_lexer_tables_index]])

theorem cp_lexer_list_iff_lexes_in_range:
  assumes ‹∀c ∈ set s. c ≤ 0x10FFFF›
  shows ‹cp_lexer (cp_lexer_tables sps) id (list_spec sps) is_newline st q s = (l, r, stf) ⟷
    symbolic.lexes in_cls (list_spec sps) is_newline st q s l r stf›
  unfolding cp_lexer_list_iff_lexes
  by (rule lexes_cong[where A = ‹{.. 0x10FFFF}›]) (use assms in ‹auto simp: cp_cls.in_clamped_iff›)

subsection ‹A spec on codepoints read on bytes›

text ‹A class of codepoints read on bytes is its part below ‹0x100›. A rule reads its
  lexeme as the codepoints of the bytes:›

definition byte_cls :: ‹nat cls ⇒ char cls› where
  ‹byte_cls ps = [(char_of a, char_of (min b 255)). (a, b) ← ps, a ≤ 255]›

definition char_rule :: ‹('k, nat cls, nat, 'm) rule ⇒ ('k, char cls, char, 'm) rule› where
  ‹char_rule ρ = ⦇match = map_rexp byte_cls (match ρ), act = λu. act ρ (map of_char u)⦈›

definition char_spec :: ‹('k, nat cls, nat, 'm) lexer_spec ⇒ ('k, char cls, char, 'm) lexer_spec›
where
  ‹char_spec sp m = map char_rule (sp m)›

section ‹Surface theorems›

text ‹If the index of each mode holds its tables, the lexer on codepoints is the driver
  of the spec with classes read in the range:›

theorem cp_lexer_iff_lexes:
  assumes ‹∀m. ix m < IArray.length TT ∧ TT !! ix m = cp_tables (sp m)›
  shows ‹cp_lexer TT ix sp is_newline st q s = (l, r, stf) ⟷
    cp_cls.lexes sp is_newline st q s l r stf›
  unfolding cp_lexer_def
  by (rule cp_cls.drive_iff_lexes[OF mode_runner_cp_lexer]) (use assms in auto)

text ‹On an input in range, it is the driver of the spec with the plain reading
  const‹in_cls› of classes:›

theorem cp_lexer_iff_lexes_in_range:
  assumes ‹∀m. ix m < IArray.length TT ∧ TT !! ix m = cp_tables (sp m)›
    and ‹∀c ∈ set s. c ≤ 0x10FFFF›
  shows ‹cp_lexer TT ix sp is_newline st q s = (l, r, stf) ⟷
    symbolic.lexes in_cls sp is_newline st q s l r stf›
  unfolding cp_lexer_iff_lexes[OF assms(1)]
  by (rule lexes_cong[where A = ‹{.. 0x10FFFF}›])
    (use assms(2) in ‹auto simp: cp_cls.in_clamped_iff›)

end