Theory Param_Tests

(* Author: Basil Fürer *)

theory Param_Tests
  imports TIGER_Grammar.LR_Prec_Parse Parser_Check
begin

section ‹Templates and operators›

text ‹Templates ‹P(X, …)› and the operators ‹* + ?› desugar to ordinary nonterminals
  before elaboration (🗏‹../grammar_expand.ML›): nothing new in HOL. The tests
  compare each against the grammar written by hand.›

fun toks :: ‹nat ⇒ 'tok list ⇒ ('tok, unit) token list› where
  ‹toks i [] = []›
| ‹toks i (x # xs) = ⦇tok = x, span = span.make 0 i i 1 []⦈ # toks (Suc (Suc i)) xs›

datatype p_tok = PId | PSemi | PComma | PLB | PRB | PKw

ML ‹
  (* terminals by token value, so that two grammars compare *)
  fun prods_of thy g =
    let
      val gr = the (Grammar_Common.get_grammar_global thy (Sign.full_bname thy g));
      fun sym (Grammar_Common.RN n) = "N " ^ n
        | sym (Grammar_Common.RC i) = "C " ^ Syntax.string_of_term_global thy (Vector.sub (#terminals gr, i))
        | sym (Grammar_Common.RT i) = "T " ^ Syntax.string_of_term_global thy (Vector.sub (#terminals gr, i));
    in map (fn {lhs, rhs, ...} => (lhs, map (fn (s, a) => (sym s, a)) rhs)) (#prods gr) end;
  fun nts_of thy g =
    Grammar_Common.nonterms_list
      (the (Grammar_Common.get_grammar_global thy (Sign.full_bname thy g)))
    |> map (fn (n, {binding, carrier, ...}) => (n, Binding.name_of binding, carrier));
  fun insensitive thy g =
    Grammar_Defs.is_indent_insensitive
      (the (Grammar_Common.get_grammar_global thy (Sign.full_bname thy g)));
›


subsection ‹Operators›

grammar (relation) pstar =
  tokens ‹p_tok›
  terminals ";" = ‹PSemi›
  productions
    S :: ‹nat list› = (PId ";")* ⇒ ‹map (λ_. 1)›

grammar (relation) pstar_hand =
  tokens ‹p_tok›
  terminals ";" = ‹PSemi›
  productions
    S :: ‹nat list› = L ⇒ ‹map (λ_. 1)›
  and
    L :: ‹(p_tok, unit) token list› = ⇒ ‹[]› | L PId ";" ⇒ ‹λxs x1. xs @ [x1]›

lemma ‹pstar =
  is_cfg.make
   [(''S'', [(Nt ''(PId ;)*'', Any)]),
    (''(PId ;)*'', []),
    (''(PId ;)*'', [(Nt ''(PId ;)*'', Any), (Tm PId, Any), (Tm PSemi, Any)])]
   ''S'' 0›
  by (simp only: pstar_def)

ML ‹
  assert ((nts_of theory "pstar" |> map #2) = ["S", "S_1"]);
  assert (insensitive theory "pstar");
›

parser pstar_parse for pstar

parser_check ‹pstar_parse (toks 0 [PId, PSemi, PId, PSemi]) = Some [1, 1]›
parser_check ‹pstar_parse [] = Some []›
parser_check ‹pstar_parse (toks 0 [PId]) = None›

text ‹‹+› and ‹?› over one nonterminal; ‹";"?› binds nothing.›

grammar (relation) popt =
  tokens ‹p_tok›
  terminals ";" = ‹PSemi› and "," = ‹PComma›
  productions
    S :: ‹(nat list × nat option)› = I+ ";"? J? ⇒ ‹Pair›
  and
    I :: ‹nat› = PId ⇒ ‹λ_. 1› | PId "," ⇒ ‹λ_. 2›
  and
    J :: ‹nat› = PKw ⇒ ‹λ_. 3›

ML ‹
  assert ((nts_of theory "popt" |> map #2) = ["S", "I", "J", "I_list1", "S_1", "J_opt"]);
›

ML ‹val _ = @{thms popt_def}›

parser popt_parse for popt

parser_check ‹popt_parse (toks 0 [PId, PId, PComma, PSemi, PKw]) = Some ([1, 2], Some 3)›
parser_check ‹popt_parse (toks 0 [PId, PSemi]) = Some ([1], None)›
parser_check ‹popt_parse (toks 0 [PId, PKw]) = Some ([1], Some 3)›

text ‹A group with two value symbols has the pair as its element.›

grammar ppair =
  tokens ‹p_tok›
  terminals ";" = ‹PSemi›
  productions
    S :: ‹(nat × nat) list› = (I ";" I)+
  and
    I :: ‹nat› = PId ⇒ ‹λ_. 1› | PKw ⇒ ‹λ_. 2›

parser ppair_parse for ppair

parser_check ‹ppair_parse (toks 0 [PId, PSemi, PKw, PKw, PSemi, PId]) = Some [(1, 2), (2, 1)]›


subsection ‹Templates›

text ‹A block in braces or aligned, once as a template and once by hand
  (‹File›/‹Decls›/‹DItems›).›

grammar (relation) pblk =
  tokens ‹p_tok›
  terminals ";" = ‹PSemi› and "{" = ‹PLB› and "}" = ‹PRB›
  productions
    Block(X) :: ‹'x list›
      = (X⇧=)+⇧=
      | "{"⇧= "}"⇧> ⇒ ‹[]›
      | "{"⇧= Sep1(X, ";") "}"⇧>
      | "{"⇧= Sep1(X, ";") ";" "}"⇧>
  and
    File :: ‹nat list› = Block(Decl)
  and
    Decl :: ‹nat› = PId⇧= ⇒ ‹λ_. 1› | PKw⇧= Block(Decl)⇧> ⇒ ‹λ_ ds. sum_list ds›

grammar (relation) pblk_hand =
  tokens ‹p_tok›
  terminals ";" = ‹PSemi› and "{" = ‹PLB› and "}" = ‹PRB›
  productions
    File :: ‹nat list› = Blk
  and
    Decl :: ‹nat› = PId⇧= ⇒ ‹λ_. 1› | PKw⇧= Blk⇧> ⇒ ‹λ_ ds. sum_list ds›
  and
    Blk :: ‹nat list›
      = Decls⇧=
      | "{"⇧= "}"⇧> ⇒ ‹[]›
      | "{"⇧= DItems "}"⇧>
      | "{"⇧= DItems ";" "}"⇧>
  and
    Decls :: ‹nat list› = Decl⇧= ⇒ ‹λx1. [x1]› | Decls⇧= Decl⇧= ⇒ ‹λxs x1. xs @ [x1]›
  and
    DItems :: ‹nat list› = Decl ⇒ ‹λx. [x]› | DItems ";" Decl ⇒ ‹λxs x. xs @ [x]›

ML ‹val _ = @{thms pblk_def}›

ML ‹
  assert ((nts_of theory "pblk" |> map #1) =
    ["File", "Decl", "Block(Decl)", "Decl+", "Sep1(Decl, ;)"]);
  assert ((nts_of theory "pblk" |> map #2) =
    ["File", "Decl", "Block_Decl", "Decl_list1", "Sep1_Decl_x3B"]);
  (* the same productions as by hand, under a renaming *)
  val ren =
    AList.lookup (op =)
      [("File", "File"), ("Decl", "Decl"), ("Block(Decl)", "Blk"), ("Decl+", "Decls"),
       ("Sep1(Decl, ;)", "DItems")];
  fun rn (s, a) =
    if String.isPrefix "N " s then ("N " ^ the (ren (unprefix "N " s)), a) else (s, a);
  val ps = prods_of theory "pblk" |> map (fn (l, r) => (the (ren l), map rn r));
  val hs = prods_of theory "pblk_hand";
  assert (eq_set (op =) (ps, hs));
›

parser pblk_parse for pblk
parser pblk_hand_parse for pblk_hand

definition ‹w_brace = toks 0 [PLB, PId, PSemi, PKw, PLB, PId, PRB, PSemi, PRB]›

parser_check ‹pblk_parse w_brace = Some [1, 1]›
parser_check ‹pblk_hand_parse w_brace = Some [1, 1]›

text ‹Aligned: two declarations in column 0.›

definition w_aligned :: ‹(p_tok, unit) token list› where ‹w_aligned =
  [⦇tok = PId, span = span.make 0 0 0 1 []⦈, ⦇tok = PId, span = span.make 1 0 0 1 []⦈]›

parser_check ‹pblk_parse w_aligned = Some [1, 1]›
parser_check ‹pblk_hand_parse w_aligned = Some [1, 1]›

text ‹The relation of an instance is the hand-written one.›

ML ‹val _ = const_name‹pblk_Block_Decl››
ML ‹val _ = @{thms pblk.intros}›


subsection ‹The prelude›

grammar plist =
  tokens ‹p_tok›
  terminals "," = ‹PComma› and ";" = ‹PSemi› and "{" = ‹PLB› and "}" = ‹PRB›
  productions
    S :: ‹nat list list› = "{" Sep(Sep1(I, ","), ";") "}"
  and
    I :: ‹nat› = PId ⇒ ‹λ_. 1› | PKw ⇒ ‹λ_. 2›

ML ‹
  assert ((nts_of theory "plist" |> map #1) =
    ["S", "I", "Sep1(I, ,)", "Sep(Sep1(I, ,), ;)", "Sep1(Sep1(I, ,), ;)"]);
›


subsection ‹Layout›

text ‹‹(Stmt=)+› is the aligned block written by hand: the recursive occurrence copies
  the annotation of the group's first symbol.›

grammar (relation) psuite =
  tokens ‹p_tok›
  terminals ":" = ‹PSemi›
  productions
    Prog :: ‹nat› = (Stmt⇧=)+ ⇒ ‹sum_list›
  and
    Stmt :: ‹nat› = PId⇧= ⇒ ‹λ_. 1› | PKw⇧= ":"⇧> (Stmt⇧=)+⇧> ⇒ ‹λ_ ns. sum_list ns + 1›

grammar (relation) psuite_hand =
  tokens ‹p_tok›
  terminals ":" = ‹PSemi›
  productions
    Prog :: ‹nat› = Blk ⇒ ‹sum_list›
  and
    Stmt :: ‹nat› = PId⇧= ⇒ ‹λ_. 1› | PKw⇧= ":"⇧> Blk⇧> ⇒ ‹λ_ ns. sum_list ns + 1›
  and
    Blk :: ‹nat list› = Stmt⇧= ⇒ ‹λx1. [x1]› | Blk⇧= Stmt⇧= ⇒ ‹λxs x1. xs @ [x1]›

ML ‹
  val ren = AList.lookup (op =) [("Prog", "Prog"), ("Stmt", "Stmt"), ("Stmt+", "Blk")];
  fun rn (s, a) =
    if String.isPrefix "N " s then ("N " ^ the (ren (unprefix "N " s)), a) else (s, a);
  assert (eq_set (op =)
    (prods_of theory "psuite" |> map (fn (l, r) => (the (ren l), map rn r)),
     prods_of theory "psuite_hand"));
  assert (not (insensitive theory "psuite"));
  assert (insensitive theory "ppair");
›

parser psuite_parse for psuite
parser psuite_hand_parse for psuite_hand

definition w_suite :: ‹(p_tok, unit) token list› where ‹w_suite =
  [⦇tok = PKw, span = span.make 0 0 0 1 []⦈, ⦇tok = PSemi, span = span.make 0 1 1 1 []⦈,
   ⦇tok = PId, span = span.make 1 2 2 1 []⦈, ⦇tok = PId, span = span.make 2 2 2 1 []⦈,
   ⦇tok = PId, span = span.make 3 0 0 1 []⦈]›

parser_check ‹psuite_parse w_suite = Some 4›
parser_check ‹psuite_hand_parse w_suite = Some 4›

text ‹The parser's soundness for a grammar with instances, stated over the relation of
  the generated nonterminal's parent.›

lemma ‹psuite_parse w = Some n ⟹ psuite_Prog 0 w n›
  using psuite_parse.sound by blast


subsection ‹Messages›

parser (diagnostics) pstar_diag for pstar

parser_check ‹(case pstar_diag_diag (toks 0 [PId, PId]) of
    Inl e ⇒ pmsg_lines (perr_message pstar_diag_info (λ_. []) e) | Inr _ ⇒ []) =
  [''0:2: syntax error at '' @ squote ''PId'',
   ''  expected: '' @ squote '';'']›

text ‹A generated list or option shows as its element in messages, a group as its first
  symbol (a terminal quoted, without article); an element and a list of it are listed once.
  After ‹MKw› the kernel has the dot before ‹Item+›, ‹Item› and ‹(, Item)+›.›

datatype m_tok = MA | MB | MC | MD | ME | MF | MKw | MSemi | MComma

grammar pmsg =
  tokens ‹m_tok›
  terminals ";" = ‹MSemi› and "," = ‹MComma›
  productions
    S :: ‹nat›
      = MKw Item+ ";" ⇒ ‹λ_ xs. length xs›
      | MKw Item "," ⇒ ‹λ_ _. 0›
      | MKw ("," Item)+ ";" ⇒ ‹λ_ xs. length xs›
  and
    Item :: ‹nat›
      = MA ⇒ ‹λ_. 1› | MB ⇒ ‹λ_. 1› | MC ⇒ ‹λ_. 1›
      | MD ⇒ ‹λ_. 1› | ME ⇒ ‹λ_. 1› | MF ⇒ ‹λ_. 1›

parser (diagnostics) pmsg_diag for pmsg

parser_check ‹(case pmsg_diag_diag (toks 0 [MKw, MSemi]) of
    Inl e ⇒ pmsg_lines (perr_message pmsg_diag_info (λ_. []) e) | Inr _ ⇒ []) =
  [''0:2: syntax error at '' @ squote '';'',
   ''  expected: an Item or '' @ squote '','']›
  and ‹(case pmsg_diag_diag (toks 0 [MKw, MA, MB, MComma]) of
    Inl e ⇒ pmsg_lines (perr_message pmsg_diag_info (λ_. []) e) | Inr _ ⇒ []) =
  [''0:6: syntax error at '' @ squote '','',
   ''  expected: an Item or '' @ squote '';'',
   ''  up to here: an Item was recognised'']›
  and ‹(case pmsg_diag_diag (toks 0 [MKw, MComma, MA, MComma, MA, MA]) of
    Inl e ⇒ pmsg_lines (perr_message pmsg_diag_info (λ_. []) e) | Inr _ ⇒ []) =
  [''0:10: syntax error at '' @ squote ''MA'',
   ''  expected: '' @ squote '';'' @ '' or '' @ squote '','',
   ''  up to here: an Item was recognised'']›

text ‹Under composition: a copied nonterminal in a list template of the prelude.›

grammar pmsg_sep =
  tokens ‹m_tok›
  terminals ";" = ‹MSemi› and "," = ‹MComma›
  productions
    T :: ‹nat› = MKw Sep1(pmsg.Item, ",") ";"? ⇒ ‹λ_ xs. length xs›

ML ‹
  assert ((nts_of theory "pmsg_sep" |> map #1) = ["T", "Sep1(pmsg.Item, ,)", ";?", unchecked_name‹pmsg.Item›]);
›

parser (diagnostics) pmsg_sep_diag for pmsg_sep

parser_check ‹(case pmsg_sep_diag_diag (toks 0 [MKw, MSemi]) of
    Inl e ⇒ pmsg_lines (perr_message pmsg_sep_diag_info (λ_. []) e) | Inr _ ⇒ []) =
  [''0:2: syntax error at '' @ squote '';'', ''  expected: an Item'']›

subsection ‹Composition›

text ‹A reference to a grammar with instances copies them; a template of another grammar
  brings that grammar's nonterminals and spellings.›

grammar (relation) pcomp =
  tokens ‹p_tok›
  productions
    Top :: ‹nat list list› = pblk.File+

ML ‹
  assert ((nts_of theory "pcomp" |> map #1) =
    ["Top", "pblk.File+", unchecked_name‹pblk.File›, "pblk.Block(Decl)", "pblk.Decl+", unchecked_name‹pblk.Decl›,
     "pblk.Sep1(Decl, ;)"]);
  assert ((nts_of theory "pcomp" |> map #2) =
    ["Top", "pblk_File_list1", "pblk_File", "pblk_Block_Decl", "pblk_Decl_list1", "pblk_Decl",
     "pblk_Sep1_Decl_x3B"]);
›

ML ‹val _ = @{thms pcomp.pblk_File_iff}›

grammar ptmpl =
  tokens ‹p_tok›
  productions
    Top :: ‹nat list› = PKw pblk.Block(Item) ⇒ ‹λ_ xs. xs›
  and
    Item :: ‹nat› = PComma ⇒ ‹λ_. 7› | pblk.Decl⇧=

ML ‹
  assert ((nts_of theory "ptmpl" |> map #1) =
    ["Top", "Item", "Block(Item)", "Item+", "Sep1(Item, ;)", unchecked_name‹pblk.Decl›, "pblk.Block(Decl)",
     "pblk.Decl+", "pblk.Sep1(Decl, ;)"]);
›

parser ptmpl_parse for ptmpl

parser_check ‹ptmpl_parse (toks 0 [PKw, PLB, PComma, PSemi, PKw, PLB, PRB, PRB]) = Some [7, 0]›


subsection ‹Errors›

ML ‹
fun command_error src =
  let val thy = theory in
    (fold Toplevel.command_exception (Outer_Syntax.parse_text thy (K {skip_theory = false, theory = thy}) Position.none src)
       (Toplevel.make_state (SOME (Context.Theory thy))); NONE)
    handle Runtime.EXCURSION_FAIL (exn, _) => SOME (Runtime.exn_message exn)
  end;

fun rejected frag src =
  (case command_error src of
    NONE => error ("accepted: " ^ src)
  | SOME msg =>
      if String.isSubstring frag msg then () else error ("unexpected: " ^ msg));
›

ML ‹
  val _ = assert (is_none (command_error
    "grammar ok = tokens p_tok productions S :: ‹nat list› = List(I) and I :: nat = PId ⇒ ‹λ_. 1›"));
  val _ = rejected "Undefined template \"Lst\""
    "grammar bad = tokens p_tok productions S :: ‹nat list› = Lst(I) and I :: nat = PId ⇒ ‹λ_. 1›";
  val _ = rejected "has 2 parameter(s), applied to 1"
    "grammar bad = tokens p_tok productions S :: ‹nat list› = Sep(I) and I :: nat = PId ⇒ ‹λ_. 1›";
  val _ = rejected "An annotation of a group"
    "grammar bad = tokens p_tok productions S :: nat = (PId PId)= ⇒ ‹λ_ _. 1›";
  val _ = rejected "is not a template"
    "grammar bad = tokens p_tok productions P(X) :: nat = X(PId) | PId ⇒ ‹λ_. 1› and S :: nat = P(PId)";
  val _ = rejected "does not terminate"
    "grammar bad = tokens p_tok productions P(X) :: nat = P(List(X)) | PId ⇒ ‹λ_. 1› and S :: nat = P(PId)";
  val _ = rejected "parameter \"X\" twice"
    "grammar bad = tokens p_tok productions P(X, X) :: nat = PId ⇒ ‹λ_. 1› and S :: nat = P(PId, PId)";
  val _ = rejected "Carrier inference"
    "grammar bad = tokens p_tok productions S :: ‹nat list› = PId* ⇒ ‹λxs. xs›";
  val _ = rejected "templates only; an option"
    "grammar (relation) bad = productions P(X) = X";
›

end