Theory Pattern_Tests

(* Author: Basil Fürer *)

theory Pattern_Tests
  imports TIGER_Lexer.TIGER_Pattern "Regular-Sets.Equivalence_Checking"
begin

section ‹Tests of the pattern sublanguage›

text ‹Every class and regex of a hand-written lexer spec, written as a pattern over the
  spec's names, elaborates to the spec's definition. Classes agree in normal form. Regexes agree as regexes over
  their normalized classes, read as letters, by the equivalence checker of
  ‹Regular-Sets› (two regexes with the same letter language have the same symbolic
  language). Associativity and units are not compared, as the hand-written spec nests
  concatenations differently.›

subsection ‹The hand-written classes and regexes›

abbreviation cp :: ‹string ⇒ nat list› where
  ‹cp s ≡ map of_char s›

definition ch :: ‹nat ⇒ nat cls› where
  ‹ch c = [(c, c)]›

definition chs :: ‹nat list ⇒ nat cls› where
  ‹chs cs = map (λc. (c, c)) cs›

definition ‹lower = [(0x61, 0x7A), (0x3B1, 0x3BA), (0x3BC, 0x3C9)]›
definition ‹upper = [(0x41, 0x5A), (0x391, 0x3A1), (0x3A3, 0x3A9)]›
definition ‹digit = [(0x30, 0x39)]›
definition ‹hexdigit = [(0x30, 0x39), (0x41, 0x46), (0x61, 0x66)]›
definition ‹bindigit = [(0x30, 0x31)]›

definition ‹idstart = lower @ upper›
definition ‹idchar = lower @ upper @ digit @ chs [0x5F, 0x27]›

definition ‹symchar = chs
  [0x21, 0x23, 0x24, 0x25, 0x26, 0x2A, 0x2B, 0x2D, 0x2F, 0x3A,
   0x3C, 0x3D, 0x3E, 0x3F, 0x40, 0x5C, 0x5E, 0x7C, 0x7E] @
  [(0x2190, 0x22FF)]›

definition ‹whitespace =
  [(0x0A, 0x0D), (0x20, 0x20), (0x85, 0x85), (0x200E, 0x200F), (0x2028, 0x2029)]›
definition ‹newline = [(0x0A, 0x0D), (0x85, 0x85), (0x2028, 0x2029)]›

definition ‹bidi = [(0x202A, 0x202E), (0x2066, 0x2069)]›

definition ‹line_char = cp_neg (newline @ bidi)›
definition ‹line_start = cp_neg (symchar @ newline @ bidi)›
definition ‹cmt_char = cp_neg (chs [0x7B, 0x2D] @ bidi)›
definition ‹str_char = cp_neg (chs [0x22, 0x5C, 0x24] @ newline @ bidi)›
definition ‹str_char_nobrace = cp_neg (chs [0x22, 0x5C, 0x24, 0x7B] @ newline @ bidi)›
definition ‹char_char = cp_neg (chs [0x27, 0x5C] @ newline @ bidi)›

definition many :: ‹'p ⇒ 'p rexp› where
  ‹many p = Times (Pred p) (Star (Pred p))›

definition opt :: ‹'p rexp ⇒ 'p rexp› where
  ‹opt r = Plus One r›

definition alts :: ‹'p rexp list ⇒ 'p rexp› where
  ‹alts rs = foldr Plus (butlast rs) (last rs)›

definition seq :: ‹'p rexp list ⇒ 'p rexp› where
  ‹seq rs = foldr Times (butlast rs) (last rs)›

definition word :: ‹nat list ⇒ nat cls rexp› where
  ‹word cs = seq (map (Pred ∘ ch) cs)›

text ‹Digit runs ‹D ("_"? D)*›, as in integer and float literals:›

definition run :: ‹nat cls ⇒ nat cls rexp› where
  ‹run d = Times (Pred d) (Star (Times (opt (Pred (ch 0x5F))) (Pred d)))›

definition ‹suffix_re = alts (map (word ∘ cp)
  [''i8'', ''i16'', ''i32'', ''i64'', ''u8'', ''u16'', ''u32'', ''u64''])›

definition ‹int_re = Times
  (alts [run digit,
         Times (word (cp ''0x'')) (run hexdigit),
         Times (word (cp ''0b'')) (run bindigit)])
  (opt suffix_re)›

definition ‹frac_re = Times (Pred (ch 0x2E)) (run digit)›
definition ‹exp_re = seq [Pred (chs [0x65, 0x45]), opt (Pred (ch 0x2D)), run digit]›
definition ‹float_re = Times (run digit) (Plus (Times frac_re (opt exp_re)) exp_re)›

text ‹An escape ‹\u{h…}› takes one to six hexadecimal digits denoting a Unicode scalar
  value cite‹‹Sect.~3.9, D76› in "unicode2025-standard"›: at most ‹10FFFF› and no surrogate ‹D800 .. DFFF›. By number of digits:›

definition ‹hex = Pred hexdigit›

definition ‹hex_cp4 = Plus
  (seq [Pred (cp_neg ([(0, 0x2F), (0x3A, 0x40), (0x47, 0x60)] @ chs [0x44, 0x64])), hex, hex, hex])
  (seq [Pred (chs [0x44, 0x64]), Pred [(0x30, 0x37)], hex, hex])›

definition ‹hex_cp5 = Plus
  (seq [Pred [(0x31, 0x39), (0x41, 0x46), (0x61, 0x66)], hex, hex, hex, hex])
  (Times (Pred (ch 0x30)) hex_cp4)›

definition ‹hex_cp6 = Plus
  (Times (Pred (ch 0x30)) hex_cp5)
  (seq [Pred (ch 0x31), Pred (ch 0x30), hex, hex, hex, hex])›

definition ‹escape_re = Times (Pred (ch 0x5C)) (Plus
  (Pred (chs [0x30, 0x74, 0x6E, 0x72, 0x22, 0x27, 0x5C, 0x24]))
  (seq [word (cp ''u{''), alts [hex, seq [hex, hex], seq [hex, hex, hex], hex_cp4, hex_cp5,
    hex_cp6], Pred (ch 0x7D)]))›

text ‹The text of a string: characters, escapes, and runs of ‹$› before a character
  other than ‹{› or before an escape. A string without holes is text between quotes. A
  string with holes is a start ‹"…${›, middles ‹}…${› and an end ‹}…"›, with the tokens
  of the holes between them. A run of ‹$› may stand before ‹${› and the closing quote:›

definition ‹dollars = many (ch 0x24)›

definition ‹str_text = Star (alts [Pred str_char, escape_re,
  Times dollars (alts [Pred str_char_nobrace, escape_re])])›

definition ‹str_open = Times str_text (Times (Star (Pred (ch 0x24))) (word (cp ''${'')))›
definition ‹str_close = Times str_text (Times (opt dollars) (Pred (ch 0x22)))›

definition ‹str_re = Times (Pred (ch 0x22)) str_close›
definition ‹str_start_re = Times (Pred (ch 0x22)) str_open›
definition ‹str_mid_re = Times (Pred (ch 0x7D)) str_open›
definition ‹str_end_re = Times (Pred (ch 0x7D)) str_close›

definition ‹char_re = seq [Pred (ch 0x27), Plus (Pred char_char) escape_re, Pred (ch 0x27)]›

text ‹A line comment is a run of at least two dashes that no symbol character extends,
  then the rest of the line:›

definition ‹line_comment_re = seq [word (cp ''--''), Star (Pred (ch 0x2D)),
  opt (Times (Pred line_start) (Star (Pred line_char)))]›

subsection ‹Comparison›

fun atom_list :: ‹'a rexp ⇒ 'a list› where
  ‹atom_list (Atom a) = [a]›
| ‹atom_list (Plus r s) = atom_list r @ atom_list s›
| ‹atom_list (Times r s) = atom_list r @ atom_list s›
| ‹atom_list (Star r) = atom_list r›
| ‹atom_list _ = []›

definition same_lang :: ‹nat cls rexp ⇒ nat cls rexp ⇒ bool› where
  ‹same_lang r s =
    (let r' = map_rexp cp_norm r; s' = map_rexp cp_norm s;
         as = remdups (atom_list r' @ atom_list s');
         ix = (λa. the (map_of (zip as [0..<length as]) a))
     in check_eqv (map_rexp ix r') (map_rexp ix s'))›

subsection ‹Classes›

lemma ‹cp_norm PAT‹[a-zα-κμ-ω]› = cp_norm lower› by eval
lemma ‹cp_norm PAT‹[A-ZΑ-ΡΣ-Ω]› = cp_norm upper› by eval
lemma ‹cp_norm PAT‹[0-9]› = cp_norm digit› by eval
lemma ‹cp_norm PAT‹[0-9a-fA-F]› = cp_norm hexdigit› by eval
lemma ‹cp_norm PAT‹[01]› = cp_norm bindigit› by eval
lemma ‹PAT‹[a-b A]› = [(0x20, 0x20), (0x41, 0x41), (0x61, 0x62)]› by eval
lemma ‹cp_norm PAT‹lower | upper› = cp_norm idstart› by eval
lemma ‹cp_norm PAT‹lower | upper | digit | [_']› = cp_norm idchar› by eval

lemma ‹cp_norm PAT‹[!#$%&*+\-/:<=>?@\\^|~\u{2190}-\u{22FF}]› =
  cp_norm symchar›
  by eval

lemma ‹cp_norm PAT‹[\n-\r \u{85}\u{200E}-\u{200F}\u{2028}-\u{2029}]› = cp_norm whitespace›
  by eval

lemma ‹cp_norm PAT‹[\n-\r\u{85}\u{2028}-\u{2029}]› = cp_norm newline› by eval
lemma ‹cp_norm PAT‹[\u{202A}-\u{202E}\u{2066}-\u{2069}]› = cp_norm bidi› by eval
lemma ‹cp_norm PAT‹_ # (newline | bidi)› = cp_norm line_char› by eval
lemma ‹cp_norm PAT‹line_char # symchar› = cp_norm line_start› by eval
lemma ‹cp_norm PAT‹_ # ([{\-] | bidi)› = cp_norm cmt_char› by eval
lemma ‹cp_norm PAT‹_ # (["\\$] | newline | bidi)› = cp_norm str_char› by eval
lemma ‹cp_norm PAT‹str_char # [{]› = cp_norm str_char_nobrace› by eval
lemma ‹cp_norm PAT‹_ # (['\\] | newline | bidi)› = cp_norm char_char› by eval

subsection ‹Regexes›

lemma ‹same_lang PAT‹digit ("_"? digit)*› (run digit)› by eval
lemma ‹same_lang PAT‹"i8" | "i16" | "i32" | "i64" | "u8" | "u16" | "u32" | "u64"› suffix_re›
  by eval

lemma ‹same_lang PAT‹(run(digit) | "0x" run(hexdigit) | "0b" run(bindigit)) suffix_re?› int_re›
  by eval

lemma ‹same_lang PAT‹"." run(digit)› frac_re› by eval
lemma ‹same_lang PAT‹[eE] "-"? run(digit)› exp_re› by eval
lemma ‹same_lang PAT‹run(digit) (frac_re exp_re? | exp_re)› float_re› by eval
lemma ‹same_lang (Pred PAT‹[0-9a-fA-F]›) hex› by eval
text ‹The first class of the hand-written const‹hex_cp4› is the complement of the
  non-digits below ‹g› and of ‹d›, ‹D›, so it also holds every codepoint from ‹g›
  on (‹\u{z123}› is an escape). The pattern of the design differs from it, and agrees
  with it once those codepoints are added:›

lemma ‹¬ same_lang PAT‹[0-9a-ce-fA-CE-F] hex hex hex | [dD] [0-7] hex hex› hex_cp4›
  by eval

lemma ‹same_lang
  PAT‹[0-9a-ce-fA-CE-F\u{67}-\u{10FFFF}] hex hex hex | [dD] [0-7] hex hex› hex_cp4›
  by eval

lemma ‹same_lang PAT‹[1-9a-fA-F] hex hex hex hex | "0" hex_cp4› hex_cp5› by eval
lemma ‹same_lang PAT‹"0" hex_cp5 | "10" hex hex hex hex› hex_cp6› by eval

lemma ‹same_lang
  PAT‹"\\" ([0tnr"'\\$] | "u{" (hex | hex hex | hex hex hex | hex_cp4 | hex_cp5 | hex_cp6) "}")›
  escape_re›
  by eval

lemma ‹same_lang PAT‹"$"+› dollars› by eval
lemma ‹same_lang PAT‹(str_char | escape_re | "$"+ (str_char # [{] | escape_re))*› str_text›
  by eval

lemma ‹same_lang PAT‹str_text "$"* "${"› str_open› by eval
lemma ‹same_lang PAT‹str_text "$"* "\""› str_close› by eval
lemma ‹same_lang PAT‹"\"" str_close› str_re› by eval
lemma ‹same_lang PAT‹"\"" str_open› str_start_re› by eval
lemma ‹same_lang PAT‹"}" str_open› str_mid_re› by eval
lemma ‹same_lang PAT‹"}" str_close› str_end_re› by eval
lemma ‹same_lang PAT‹"'" (char_char | escape_re) "'"› char_re› by eval
lemma ‹same_lang PAT‹"--" "-"* (line_start line_char*)?› line_comment_re› by eval

text ‹The equivalence checker tells regexes apart:›

lemma ‹¬ same_lang PAT‹"--" "-"+› line_comment_re› by eval

subsection ‹Templates and errors›

text ‹The diagnostic command elaborates in the environment of its ‹where› block. A
  parameter used as a class is a class:›

pattern ‹run(digit) | sep([a], [b])›
  where digit = ‹[0-9]› | run(d) = ‹d ("_"? d)*› | sep(c, d) = ‹(c # d) d›

ML ‹
fun expect_error msg src =
  (case Exn.capture (Pattern.read context (Pattern.const_env context)) (Input.string src) of
    Exn.Res _ => error ("No error for " ^ quote src)
  | Exn.Exn (ERROR m) =>
      if String.isSubstring msg m then () else error ("Wrong error for " ^ quote src ^ ": " ^ m)
  | Exn.Exn e => Exn.reraise e);

expect_error "Undefined constant: \"nowhere\"" "[a] nowhere";
expect_error "left side of # is not a class" "\"ab\" # [a]";
expect_error "right side of # is not a class" "_ # [a]*";
expect_error "empty range" "[z-a]";
expect_error "codepoint above U+10FFFF" "\"\\u{110000}\"";
expect_error "unknown escape" "\"\\q\"";
expect_error "unterminated class" "[a-z";
expect_error "escaped blank in a class" "[a\\ b]";
expect_error "newline in a class" "[a\nb]";
expect_error "takes 1 argument" "run";
expect_error "is neither a class nor a regex" "cp";
expect_error "expected \")\"" "(lower";
›

end