Theory Lexer_Table_Tests

(* Author: Basil Fürer *)

theory Lexer_Table_Tests
  imports Lexer_Command_Tests TIGER_Lexer.Lexer_Check
begin

section ‹Tests of the generated lexers›

text ‹The lexers that @{command lexer} builds for the specs of ‹Lexer_Command_Tests›,
  checked with @{command lexer_check} where no theorem is needed.›

subsection ‹Identifiers and operators›

text ‹‹αβ →⇒›, a newline and ‹A›. The final stack is the start stack:›

lexer_check ‹cp_lex [0x3B1, 0x3B2, 0x20, 0x2192, 0x21D2, 0x0A, 0x41] =
  (Lexed []
    [⦇tok = LIDENT, span = ⦇s_line = 0, s_col = 0, s_off = 0, s_len = 2, s_txt = [0x3B1, 0x3B2]⦈,
      trivia = [0x20]⦈,
     ⦇tok = OP, span = ⦇s_line = 0, s_col = 3, s_off = 3, s_len = 2, s_txt = [0x2192, 0x21D2]⦈,
      trivia = [0x0A]⦈,
     ⦇tok = UIDENT, span = ⦇s_line = 1, s_col = 0, s_off = 6, s_len = 1, s_txt = [0x41]⦈,
      trivia = []⦈],
   [], [()])›

subsection ‹Nested comments›

text ‹‹a(*(**)*)1›: the nested comment is the trailing trivia of ‹a›:›

lexer_check ‹cmt_lex [0x61, 0x28, 0x2A, 0x28, 0x2A, 0x2A, 0x29, 0x2A, 0x29, 0x31] =
  (Lexed []
    [⦇tok = Word, span = ⦇s_line = 0, s_col = 0, s_off = 0, s_len = 1, s_txt = [0x61]⦈,
      trivia = [0x28, 0x2A, 0x28, 0x2A, 0x2A, 0x29, 0x2A, 0x29]⦈,
     ⦇tok = Num, span = ⦇s_line = 0, s_col = 9, s_off = 9, s_len = 1, s_txt = [0x31]⦈,
      trivia = []⦈],
   [], [Code])›

text ‹An unterminated comment consumes the input but ends in ‹Comment›, which is not
  final, so the scan fails:›

lexer_check ‹cmt_lex [0x61, 0x28, 0x2A, 0x62] =
  (Lexed []
    [⦇tok = Word, span = ⦇s_line = 0, s_col = 0, s_off = 0, s_len = 1, s_txt = [0x61]⦈,
      trivia = [0x28, 0x2A, 0x62]⦈],
   [], [Comment, Code])›

lexer_check ‹cmt_lex.ok [0x61, 0x62]› ‹¬ cmt_lex.ok [0x61, 0x28, 0x2A, 0x62]›
  ‹¬ cmt_lex.ok [0x61, 0x2B]›

text ‹The correctness theorem on a concrete input: the result of the lexer is a
  derivation of const‹symbolic.lexes› from the start mode:›

lemma cmt_lex_ab:
  ‹cmt_lex [0x61, 0x62] =
    (Lexed [] [⦇tok = Word, span = ⦇s_line = 0, s_col = 0, s_off = 0, s_len = 2,
      s_txt = [0x61, 0x62]⦈, trivia = []⦈], [], [Code])›
  by eval

lemma
  ‹symbolic.lexes in_cls cmt.spec cmt.is_newline [cmt.start] ⦇line = 0, col = 0, off = 0⦈
    [0x61, 0x62]
    (Lexed [] [⦇tok = Word, span = ⦇s_line = 0, s_col = 0, s_off = 0, s_len = 2,
      s_txt = [0x61, 0x62]⦈, trivia = []⦈]) [] [Code]›
  by (rule cmt_lex.correct[THEN iffD1]) (simp_all add: cmt_lex_ab)

subsection ‹Bytes›

text ‹The same spec on bytes. Its classes stay below ‹0x100›, apart from the
  complement in the comment rule, which reaches the end of the codepoints:›

lexer (char) cmt_bytes :: ‹ctok› (* ~6 s *)
  modes Code Comment
  exclusive Comment
  where letter = ‹[a-z]›
  rules
    ‹letter+› ⇒ Word
  | ‹[0-9]+› ⇒ Num
  | ‹[ \n]+› ⇒ skip
  | "(*" ⇒ skip, push Comment
  | <Comment> (
      "(*" ⇒ skip, push Comment
    | "*)" ⇒ skip, pop
    | ‹[^*(]+ | [*(]› ⇒ skip
  )

lexer_check ‹cmt_bytes_lex ''ab (* (* c *) *) 12'' =
  (Lexed []
    [⦇tok = Word, span = ⦇s_line = 0, s_col = 0, s_off = 0, s_len = 2, s_txt = ''ab''⦈,
      trivia = '' (* (* c *) *) ''⦈,
     ⦇tok = Num, span = ⦇s_line = 0, s_col = 17, s_off = 17, s_len = 2, s_txt = ''12''⦈,
      trivia = []⦈],
   [], [cmt_bytes_mode.Code])›

subsection ‹The hook›

text ‹‹a--b›: subtraction after the operand, negation after the operator:›

lexer_check ‹map tok (toks (fst (ops_lex [0x61, 0x2D, 0x2D, 0x62]))) = [Id, Minus, Neg, Id]›

subsection ‹Shared tables›

text ‹Modes with the same active rules share their tables: ‹A› and ‹B› have the
  untagged rules, the exclusive ‹C› has its own:›

lexer sh :: ‹ctok›
  modes A B C
  exclusive C
  rules
    ‹[a-z]+› ⇒ Word
  | "{" ⇒ skip, push C
  | <C> ("}" ⇒ skip, pop | ‹[0-9]+› ⇒ Num)

lemma ‹sh_lex.index A = 0› ‹sh_lex.index B = 0› ‹sh_lex.index C = 1›
  ‹IArray.length sh_lex.tables = 2›
  by (simp_all add: sh_lex.index_def sh_lex.tables_def)

lexer_check ‹map tok (toks (fst (sh_lex [0x61, 0x7B, 0x31, 0x7D, 0x62]))) = [Word, Num, Word]›

subsection ‹Unreachable rules›

text ‹The second rule matches only ‹a›, which the first matches with higher priority.
  The command warns that the second rule cannot be matched in mode ‹()›:›

lexer dup :: ‹ctok›
  rules "a" ⇒ Word | "a" ⇒ Num

ML_command ‹
  let
    val th = Proof_Context.get_thm context unchecked_name‹dup_lex.tables_0_code›;
    val lit = snd (HOLogic.dest_eq (HOLogic.dest_Trueprop (Thm.prop_of th)));
  in assert (Lexer_Tables.accepted lit = [0]) end
›

text ‹With ‹(no_check)›, the command does not warn:›

lexer (no_check) dup' :: ‹ctok›
  rules "a" ⇒ Word | "a" ⇒ Num

subsection ‹The lexing diagnostic›

text ‹@{command lex} prints the tokens of a text with their trivia, the residue and the
  final stack:›

lex cmt_lex ‹ab (* c *) 12›

lex cmt_bytes_lex ‹ab (* c›

ML_command ‹
  let
    val out = Lexer_Check.lex context term‹cmt_lex› ‹a (* *) 1+›
      |> Pretty.string_of |> Protocol_Message.clean_output;
  in
    assert (String.isSubstring "Word  0:0     \"a\"  trivia \" (* *) \"" out);
    assert (String.isSubstring "residue \"+\"" out);
    assert (String.isSubstring "(the top is final)" out)
  end
›

subsection ‹A failing check›

text ‹A false check shows the left-hand side:›

ML_command ‹
  (case Exn.capture (Lexer_Check.verify context)
      term‹map tok (toks (fst (sh_lex [0x61]))) = []› of
    Exn.Res _ => error "No error"
  | Exn.Exn exn =>
      assert (String.isSubstring "the left-hand side is [Word]"
        (Protocol_Message.clean_output (Runtime.exn_message exn))))
›

subsection ‹Errors›

text ‹The byte instance rejects a class that reaches above ‹0xFF›, at the definition of
  a named class or at the lexer for a class written in a rule:›

ML_command ‹
  lexer_fails context
    "(char) greek :: ‹ctok› where alpha = ‹[α-ω]› rules ‹alpha+› ⇒ Word"
    "the class \"alpha\" = [0x3B1-0x3C9] reaches above";
  lexer_fails context "(char) lambda :: ‹ctok› rules \"λ\" ⇒ Word"
    "= [0x3BB] reaches above 0xFF";
  lexer_fails context "(utf8) e :: ‹ctok› rules \"x\" ⇒ Word"
    "unknown option \"utf8\""
›

text ‹With ‹(sketch)›, the command defines the spec only:›

lexer (sketch) sk :: ‹ctok›
  rules ‹[a-z]+› ⇒ Word

ML_command ‹
  assert (can (Proof_Context.get_thms context) unchecked_name‹sk.spec.simps›);
  assert (not (can (Proof_Context.read_const {proper = true, strict = true} context) "sk_lex"))
›

end