Theory Diag_Tests

(* Author: Basil Fürer *)

theory Diag_Tests
  imports TIGER_Grammar.LR_Parser Parser_Check
begin

section ‹Diagnostics of rejected words›

definition tu :: ‹nat ⇒ 'tok ⇒ char list ⇒ ('tok, unit) token› where
  ‹tu i x u = ⦇tok = x, span = span.make 0 i 0 (length u) []⦈›

subsection ‹The simple driver: ‹lay››

text ‹The grammar ‹lay› of ‹Regression_Tests›, with two parsers: ‹lay_plain›
  without the option and ‹lay_parse› with it. The option adds ‹lay_parse_diag›,
  which runs a word once and returns the tree or the error, ‹lay_parse_terminals›,
  ‹lay_parse_info› and ‹lay_parse_render› for the messages (section ∗‹Messages›)
  and the fact ‹lay_parse_diag.Inr_iff›, and leaves the code equations of the
  parser and its tables as they are (checked below).›

datatype lay_tok = LX | LNum | LPlus | LSemi | LLP | LRP

grammar (relation) lay =
  tokens ‹lay_tok›
  productions
    S :: ‹nat list› = E LSemi S ⇒ ‹λe _ s. e # s› | E ⇒ ‹λe. [e]›
  and
    E :: ‹nat› = E LPlus T ⇒ ‹λa _ b. a + b› | T
  and
    T :: ‹nat› = N | LLP E LRP ⇒ ‹λ_ e _. e›
  and
    N :: ‹nat› = LX ⇒ ‹λ_. 1› | LNum ⇒ ‹λ_. 2›

parser (no_diagnostics) lay_plain for lay

parser (diagnostics) lay_parse for lay

ML ‹
  (* the constants of the parser ‹diag›, defined with the option, are those of ‹plain›,
     defined without it, renamed, plus ‹extra›, and their code equations are the same *)
  fun same_code ctxt plain diag extra =
    let
      val thy = Proof_Context.theory_of ctxt;
      val base = Context.theory_base_name thy ^ ".";
      fun consts_of p =
        #constants (Consts.dest (Sign.consts_of thy))
        |> map #1
        |> filter (fn c => c = base ^ p orelse String.isPrefix (base ^ p ^ "_") c)
        |> sort_strings;
      fun eqns c =
        map (XML.content_of o YXML.parse_body o Pretty.unformatted_string_of)
          (Code.pretty_cert thy (Code.get_cert ctxt [] c));
      val from = map String.str (String.explode plain);
      fun go [] = []
        | go (cs as c :: rest) =
            if is_prefix (op =) from cs then diag :: go (drop (length from) cs)
            else c :: go rest;
      val rename = implode o go o map String.str o String.explode;
      val ps = consts_of plain;
      val ds = consts_of diag;
      val renamed = map rename ps;
      val extra' = subtract (op =) renamed ds;
    in
      (extra' = map (fn s => base ^ diag ^ s) extra
        orelse error ("diagnostics: unexpected constants " ^ commas_quote extra'));
      ps ~~ renamed |> List.app (fn (c, c') =>
        if map rename (eqns c) = eqns c' then ()
        else error ("diagnostics: the code equations of " ^ c' ^ " differ from " ^ c))
    end
›

ML ‹same_code context "lay_plain" "lay_parse" ["_coverage", "_diag", "_info", "_probe", "_render", "_terminals"]›

lemma ‹lay_parse_diag w = Inr x ⟷ lay_S w x›
  using lay_parse_diag.Inr_iff lay_parse.sound lay_parse.complete by blast

text ‹An accepted word: ‹Inr› with the parser's value.›

parser_check ‹lay_parse_diag [tu 1 LX ''x'', tu 2 LPlus ''+'', tu 3 LLP ''('', tu 4 LNum ''2'',
    tu 5 LRP '')'', tu 6 LSemi '';'', tu 7 LX ''x''] = Inr [3, 1]›

text ‹A wrong token in the middle: the second ‹+›, index 2 counting from 0,
  reported with its span; an operand was expected.›

parser_check ‹(case lay_parse_diag [tu 1 LX ''x'', tu 2 LPlus ''+'', tu 3 LPlus ''+'', tu 4 LX ''x''] of
    Inl e ⇒ pe_index e = 2 ∧ pe_tok e = Some (tu 3 LPlus ''+'') ∧
      map_option (s_col ∘ span) (pe_tok e) = Some 3 ∧ pe_kind e = NoAction ∧
      pe_expected e = [LLP, LX, LNum] ∧ ¬ pe_expect_end e
  | Inr _ ⇒ False)›

text ‹A closing parenthesis without an opening one: an operator, a separator or
  the end of the input was expected.›

parser_check ‹(case lay_parse_diag [tu 1 LX ''x'', tu 2 LRP '')''] of
    Inl e ⇒ pe_index e = 1 ∧ pe_expected e = [LSemi, LPlus] ∧ pe_expect_end e
  | Inr _ ⇒ False)›

text ‹A premature end of input and the empty input.›

parser_check ‹(case lay_parse_diag [tu 1 LX ''x'', tu 2 LPlus ''+''] of
    Inl e ⇒ pe_index e = 2 ∧ pe_tok e = None ∧ pe_kind e = NoAction ∧
      pe_expected e = [LLP, LX, LNum] ∧ ¬ pe_expect_end e
  | Inr _ ⇒ False)›

parser_check ‹(case lay_parse_diag [] of
    Inl e ⇒ pe_index e = 0 ∧ pe_tok e = None ∧ pe_kind e = NoAction ∧
      pe_expected e = [LLP, LX, LNum] ∧ ¬ pe_expect_end e
  | Inr _ ⇒ False)›

text ‹The candidates are the grammar's terminals in the order they occur in the
  productions, with their spellings; ‹lay› declares none, so a terminal is spelled
  by its name. The expected set keeps this order.›

lemma ‹lay_parse_terminals = [(LSemi, ''LSemi''), (LPlus, ''LPlus''), (LLP, ''LLP''), (LRP, ''LRP''),
    (LX, ''LX''), (LNum, ''LNum'')]›
  by (simp add: lay_parse_terminals_def)

subsection ‹The expected set against a brute-force oracle›

text ‹A design claim, checked on small grammars: a terminal ‹t› is in the expected
  set of a rejected word iff the consumed prefix extended by ‹t› and some short
  completion ‹u› is accepted; the end of the input is expected iff the prefix
  itself is accepted. The completions ‹u› range over the words up to length
  ‹k› over a few closing terminals ‹cs›, enough to complete every viable prefix
  of the grammars below within the bound. The set depends only on the
  configuration after the prefix, so each distinct report is checked once.›

fun words :: ‹'a list ⇒ nat ⇒ 'a list list› where
  ‹words xs 0 = [[]]›
| ‹words xs (Suc n) = [] # concat (map (λx. map ((#) x) (words xs n)) xs)›

definition brute_expect :: ‹(('t, unit) token list ⇒ 'a option) ⇒ 't list ⇒ 't list ⇒ nat ⇒
    't list ⇒ 't list × bool› where
  ‹brute_expect p ts cs k pre =
     (filter (λt. ∃u ∈ set (words cs k). p (map (λx. tu 0 x []) (pre @ t # u)) ≠ None) ts,
      p (map (λx. tu 0 x []) pre) ≠ None)›

text ‹The reports of the rejected words up to length ‹n› that disagree with the
  oracle, as (prefix, (expected set, end), (oracle's set, end)).›

definition brute_mismatches :: ‹(('t, unit) token list ⇒ 'a option) ⇒
    (('t, unit) token list ⇒ (string, 't, unit, unit) perr + 'a) ⇒ 't list ⇒ 't list ⇒ nat ⇒ nat ⇒
    ('t list × ('t list × bool) × 't list × bool) list› where
  ‹brute_mismatches p d ts cs n k =
     filter (λ(pre, (r, e), (b, e')). set r ≠ set b ∨ e ≠ e')
       (map (λ(pre, r). (pre, r, brute_expect p ts cs k pre))
         (remdups (List.map_filter (λw. case d (map (λx. tu 0 x []) w) of
              Inl e ⇒ Some (take (pe_index e) w, pe_expected e, pe_expect_end e)
            | Inr _ ⇒ None) (words ts n))))›

ML ‹
  fun check_oracle ctxt name t =
    let val r = Value_Command.value ctxt t in
      (case try HOLogic.dest_list r of
        SOME [] => writeln (name ^ ": the expected sets agree with the oracle")
      | _ => error (name ^ ": expected sets disagree with the oracle:\n" ^ Syntax.string_of_term ctxt r))
    end
›

ML ‹
  check_oracle context "lay"
    term‹brute_mismatches lay_parse lay_parse_diag [LX, LNum, LPlus, LSemi, LLP, LRP] [LX, LRP] 4 6›
›
subsection ‹One pass against the rerun›

text ‹‹lay_parse_diag› runs a word once. On every word up to length ‹4› it agrees
  with the parser followed, on a rejection, by a second run of the diagnosis.›

parser_check ‹list_all (λw. let w' = map (λx. tu 0 x []) w in
    lay_parse_diag w' = (case lay_parse w' of Some x ⇒ Inr x
      | None ⇒ Inl (pdiagnose lay_parse_ptabs lay_parse_i0 (pnum lay_parse_ptabs)
                    (map fst lay_parse_terminals) w')))
    (words [LX, LNum, LPlus, LSemi, LLP, LRP] 4)›

subsection ‹A unit self-loop›

text ‹A grammar with ‹A ⇒+ A› is ambiguous, so its determinism check fails and the
  parser runs the set-anchored driver, with the history that stops on a repeated
  configuration (expected warning). The diagnostics run the same step, and their loop
  check fires as the parser's does.›

datatype abc_tok = PA | PB | PC

grammar (relation) uloop =
  tokens ‹abc_tok›
  productions S :: ‹nat› = C ⇒ ‹λc. c›
    and B :: ‹nat› = B ⇒ ‹λn. n› | PB ⇒ ‹λ_. 0›
    and C :: ‹nat› = B ⇒ ‹λb. b›

parser (diagnostics) uloop_parse for uloop

parser_check ‹(case uloop_parse_diag [tu 1 PB ''x''] of
    Inl e ⇒ pe_kind e = ReduceCycle ∧ pe_index e = 1 ∧ pe_tok e = None
  | Inr _ ⇒ False)›

parser_check ‹(case uloop_parse_diag [tu 1 PB ''x'', tu 2 PB ''y''] of
    Inl e ⇒ pe_kind e = NoAction ∧ pe_index e = 1 ∧ pe_tok e = Some (tu 2 PB ''y'')
  | Inr _ ⇒ False)›

text ‹Without layout annotations every column is accepted, and the token is
  not misplaced.›

parser_check ‹(case uloop_parse_diag [tu 1 PC ''x''] of
    Inl e ⇒ pe_kind e = NoAction ∧ pe_expected e = [PB] ∧ pe_columns e = [(PB, [(0, None)])]
  | Inr _ ⇒ False)›

text ‹The engine on the plain tables of ‹uloop›, built as the command builds
  them for the simple driver. They keep both reduces of the conflict, and the
  step takes the first, ‹B = B›, which rebuilds the stack it popped: on ‹PB›
  the loop check fires at the end of the input and the error is
  const‹ReduceCycle›, not const‹NoAction›. On ‹PB PB› the second ‹PB› has no
  action.›

definition ul_states where ‹ul_states = pr0_states uloop ''!''›

definition ul_ptabs where
  ‹ul_ptabs = ptabs_of (ktabs_of (jtabs_of (mk_ltabs (pgtab uloop ul_states) ul_states
     (red_buckets uloop ''!'' (size ul_states)) (pcomps uloop ul_states) (pfins ''!'' ul_states))))›

definition ul_i0 where ‹ul_i0 = st_find ul_states (lr0_start uloop ''!'')›

parser_check ‹(let e = pdiagnose ul_ptabs ul_i0 (pnum ul_ptabs) [PA, PB, PC] [tu 1 PB ''x''] in
    pe_kind e = ReduceCycle ∧ pe_index e = 1 ∧ pe_tok e = None)›

parser_check ‹(let e = pdiagnose ul_ptabs ul_i0 (pnum ul_ptabs) [PA, PB, PC] [tu 1 PB ''x'', tu 2 PB ''y''] in
    pe_kind e = NoAction ∧ pe_index e = 1 ∧ pe_tok e = Some (tu 2 PB ''y''))›

text ‹The trials run into the same cycle: after ‹PB› the reduce ‹B = PB› is
  followed by ‹B = B› forever, whatever the lookahead, and the loop check, which
  each trial starts afresh, ends every trial. Nothing is expected, not even the
  end of the input, although ‹[PB]› is in the language: the set is what this
  parser accepts, and on ‹uloop›'s conflicting tables it accepts nothing.›

parser_check ‹(let e = pdiagnose ul_ptabs ul_i0 (pnum ul_ptabs) [PA, PB, PC] [tu 1 PB ''x''] in
    pe_expected e = [] ∧ ¬ pe_expect_end e)›

subsection ‹Merged lookaheads and spurious reductions›

text ‹The example of cite‹‹Sect.~4› in "pottier2016-lr1-reachability"›: brackets and parentheses around
  lists. The LALR state after ‹INT› merges the contexts inside ‹(› and ‹[›, so
  it reduces on ‹)› after ‹[ INT› and fails only two reductions later, in the
  state after ‹[ list›. A static reading of the first state would expect ‹)›,
  one of the second only ‹]›. The trials expect an operator, ‹,› and ‹]›,
  and the error keeps the state where it was detected.›

datatype br_tok = BInt | BPlus | BComma | BLP | BRP | BLB | BRB

grammar (relation) br =
  tokens ‹br_tok›
  terminals "+" = BPlus and "," = BComma and "(" = BLP and ")" = BRP and "[" = BLB and "]" = BRB
  productions
    E :: ‹nat› = E "+" A ⇒ ‹λa b. a + b› | A
  and
    A :: ‹nat› = "(" L ")" ⇒ ‹λl. l› | "[" L "]" ⇒ ‹λl. l› | BInt ⇒ ‹λ_. 1›
  and
    L :: ‹nat› = E | E "," L ⇒ ‹λe l. e + l›

parser (diagnostics) br_parse for br

parser_check ‹(case br_parse_diag [tu 1 BLB ''['', tu 2 BInt ''1'', tu 3 BRP '')''] of
    Inl e ⇒ pe_index e = 2 ∧ pe_tok e = Some (tu 3 BRP '')'') ∧
      set (pe_expected e) = {BPlus, BComma, BRB} ∧ ¬ pe_expect_end e
  | Inr _ ⇒ False)›

text ‹The state where the error is detected is not the one after the last shift:
  the trials start from the latter.›

parser_check ‹(case br_parse_diag [tu 1 BLB ''['', tu 2 BInt ''1'', tu 3 BRP '')''] of
    Inl e ⇒ pe_state e ≠ pstate (fst (case pdiag_run br_parse_ptabs br_parse_i0 br_parse_tnum
      [tu 1 BLB ''['', tu 2 BInt ''1'', tu 3 BRP '')''] of Some (DStuck _ _ sh) ⇒ sh))
  | Inr _ ⇒ False)›

ML ‹
  check_oracle context "br"
    term‹brute_mismatches br_parse br_parse_diag [BInt, BPlus, BComma, BLP, BRP, BLB, BRB]
      [BInt, BRP, BRB] 4 6›
›

subsection ‹An extended token record›

text ‹The error carries the token at the user's record type, extra fields
  included.›

datatype py_tok = PWhile | PColon | PId
datatype trivia = Whitespace | Comment

record py_token = ‹(py_tok, nat) token› +
  trailing :: ‹(trivia × nat span) list›

datatype out = Foo ‹(trivia × nat span) list› | Bar

grammar (relation) t_ext =
  tokens ‹py_token›
  terminals "while" = PWhile and ":" = ‹PColon›
  productions
    X = Y | "while" ⇒ ‹Bar›
  and
    Y = ":" PId ⇒ ‹Foo ∘ trailing›

parser (diagnostics) t_ext_parse for t_ext

text ‹Declared spellings are kept; ‹PId› has none.›

lemma ‹map snd t_ext_parse_terminals = [''while'', '':'', ''PId'']›
  by (simp add: t_ext_parse_terminals_def)

parser_check ‹(case t_ext_parse_diag
      [⦇tok = PColon, span = ⦇s_line = 0, s_col = 0, s_off = 0, s_len = 1, s_txt = []⦈, trailing = []⦈,
       ⦇tok = PColon, span = ⦇s_line = 0, s_col = 2, s_off = 2, s_len = 1, s_txt = []⦈,
        trailing = [(Comment, ⦇s_line = 0, s_col = 4, s_off = 4, s_len = 3, s_txt = []⦈)]⦈] of
    Inl e ⇒ pe_index e = 1 ∧ pe_expected e = [PId] ∧
      map_option trailing (pe_tok e) = Some [(Comment, ⦇s_line = 0, s_col = 4, s_off = 4, s_len = 3, s_txt = []⦈)]
  | Inr _ ⇒ False)›

subsection ‹The set-anchored driver: layout›

text ‹The layout grammars of ‹Regression_Tests›, with the option. Their parsers run
  the set-anchored driver. The rejected words there are rejected for a column: the
  report gives the columns at which the token would be accepted and the token it
  must be aligned with or indented from.›

datatype do_tok = DDo | DId

grammar (relation) do =
  tokens ‹do_tok›
  terminals "do" = ‹DDo›
  productions
      Expr :: ‹unit›
        = DId⇧>          ⇒ ‹λ_. ()›
        | "do"⇧> BStmts⇧> ⇒ ‹λ_. ()›
    and
      BStmts :: ‹unit›
        = BExpr⇧=         ⇒ ‹λ_. ()›
        | BStmts⇧= BExpr⇧= ⇒ ‹λ_ _. ()›
    and
      BExpr :: ‹unit›
        = DId⇧=          ⇒ ‹λ_. ()›
        | "do"⇧= BStmts⇧> ⇒ ‹λ_. ()›

parser (diagnostics) do_parse2 for do

text ‹‹y› continues the inner block at column 7 or the outer one at column 4; at
  column 2 it is nearest to the outer one, opened by the inner ‹do›.›

parser_check ‹(case do_parse2_diag [tu 1 DDo ''do'', tu 4 DDo ''do'', tu 7 DId ''x'', tu 2 DId ''y''] of
    Inl e ⇒ pe_index e = 3 ∧ pe_tok e = Some (tu 2 DId ''y'') ∧
      pe_kind e = Misaligned [(4, Some 4), (7, Some 7)] ∧ pe_anchor e = Some (tu 4 DDo ''do'') ∧
      pe_columns e = [(DId, [(4, Some 4), (7, Some 7)]), (DDo, [(4, Some 4), (7, Some 7)])] ∧
      pe_expect_end e
  | Inr _ ⇒ False)›

text ‹At column 9 it is nearest to the inner block, which starts with ‹x›.›

parser_check ‹(case do_parse2_diag [tu 1 DDo ''do'', tu 4 DDo ''do'', tu 7 DId ''x'', tu 9 DId ''y''] of
    Inl e ⇒ pe_kind e = Misaligned [(4, Some 4), (7, Some 7)] ∧ pe_anchor e = Some (tu 7 DId ''x'')
  | Inr _ ⇒ False)›

text ‹At the end of the input there is no token to misplace: the error is
  const‹NoAction›, and the block may start at any column right of ‹4›.›

parser_check ‹(case do_parse2_diag [tu 1 DDo ''do'', tu 4 DDo ''do''] of
    Inl e ⇒ pe_kind e = NoAction ∧ pe_tok e = None ∧ pe_anchor e = None ∧
      pe_columns e = [(DId, [(5, None)]), (DDo, [(5, None)])] ∧ ¬ pe_expect_end e
  | Inr _ ⇒ False)›

datatype hc_tok = HCase | HOf | HLC | HRC | HSemi | HId

grammar (relation) hask_case =
  tokens ‹hc_tok›
  terminals
    "case" = ‹HCase› and "of" = ‹HOf›   and
    "{"    = ‹HLC›   and "}"  = ‹HRC›   and ";" = ‹HSemi›
  productions
      Case = "case"⇧> Exp⇧= "of"⇧> AltBlock⇧= ⇒ ‹λ_ _. ()›
    and
      Exp = HId⇧≥ ⇒ ‹λ_. ()›
    and
      AltBlock :: ‹unit›
        = "{"⇧> Alts "}" ⇒ ‹λ_. ()›
        | AltLayout⇧>      ⇒ ‹λ_. ()›
    and
      AltLayout :: ‹unit›
        = Alts⇧=            ⇒ ‹λ_. ()›
        | AltLayout⇧= Alts⇧= ⇒ ‹λ_ _. ()›
    and
      Alts :: ‹unit›
        = HId⇧=            ⇒ ‹λ_. ()›
        | Alts⇧= ";"⇧≥ HId⇧= ⇒ ‹λ_ _. ()›

parser (diagnostics) hask_case_parse2 for hask_case

parser_check ‹(case hask_case_parse2_diag [tu 1 HCase ''case'', tu 6 HId ''x'', tu 8 HOf ''of'',
      tu 3 HId ''A'', tu 4 HId ''B''] of
    Inl e ⇒ pe_index e = 4 ∧ pe_kind e = Misaligned [(3, Some 3)] ∧
      pe_anchor e = Some (tu 3 HId ''A'') ∧
      pe_columns e = [(HId, [(3, Some 3)]), (HSemi, [(3, None)])]
  | Inr _ ⇒ False)›

grammar (relation) py_suite =
  tokens ‹py_tok›
  terminals "while" = ‹PWhile› and ":" = ‹PColon›
  productions
      WhileStmt = "while"⇧> Test⇧= ":"⇧> Suite⇧= ⇒ ‹λ_ _. ()›
    and
      Test = PId⇧≥ ⇒ ‹λ_. ()›
    and
      Suite = Block⇧> ⇒ ‹λ_. ()›
    and
      Block :: ‹unit›
        = BStatement⇧=        ⇒ ‹λ_. ()›
        | Block⇧= BStatement⇧= ⇒ ‹λ_ _. ()›
    and
      BStatement = PId⇧= ⇒ ‹λ_. ()›

parser (no_diagnostics) py_plain for py_suite

parser (diagnostics) py_parse2 for py_suite

text ‹The option leaves the code equations of the set-anchored parser and its
  tables as they are.›

ML ‹same_code context "py_plain" "py_parse2" ["_coverage", "_diag", "_info", "_probe", "_render", "_terminals"]›

text ‹The one pass of the vector driver agrees with the parser and a second run of
  the diagnosis on the sparse driver on every word up to length ‹4› over tokens at
  a few columns.›

parser_check ‹list_all (λw. let w' = map (λ(x, i). tu i x []) w in
    py_parse2_diag w' = (case py_parse2 w' of Some x ⇒ Inr x
      | None ⇒ Inl (sdiagnose py_parse2_stab py_parse2_sinit py_parse2_sclos py_parse2_i0
                    (map fst py_parse2_terminals) w')))
    (words [(PWhile, 1), (PId, 3), (PId, 1), (PColon, 2), (PId, 0)] 4)›

parser_check ‹(case py_parse2_diag [tu 1 PWhile ''while'', tu 7 PId ''x'', tu 8 PColon '':'',
      tu 3 PId ''y'', tu 4 PId ''z''] of
    Inl e ⇒ pe_index e = 4 ∧ pe_kind e = Misaligned [(3, Some 3)] ∧
      pe_anchor e = Some (tu 3 PId ''y'') ∧ pe_expected e = [PId] ∧ pe_expect_end e
  | Inr _ ⇒ False)›

text ‹The suite must be indented: right of column ‹0›, where the statement may
  start, so at least as far as ‹while›.›

parser_check ‹(case py_parse2_diag [tu 1 PWhile ''while'', tu 7 PId ''x'', tu 8 PColon '':'',
      tu 0 PId ''y''] of
    Inl e ⇒ pe_kind e = Offside [(1, None)] ∧ pe_anchor e = Some (tu 1 PWhile ''while'')
  | Inr _ ⇒ False)›

datatype iswim_tok = IWhere | IPlus | IMinus | IEq | ILP | IRP | IId

grammar (relation) iswim =
  tokens ‹iswim_tok›
  terminals
    "where" = ‹IWhere› and "+" = ‹IPlus› and "-" = ‹IMinus› and
    "="     = ‹IEq›    and "(" = ‹ILP›   and ")" = ‹IRP›
  productions
      Expr :: ‹unit›
        = Expr⇧= "where"⇧≥ IId⇧≥ "="⇧≥ WExpr⇧≥  ⇒ ‹λ_ _ _. ()›
        | Expr⇧= "+"⇧≥ Expr⇧=                 ⇒ ‹λ_ _. ()›
        | "-"⇧≥ Expr⇧=                       ⇒ ‹λ_. ()›
        | "("⇧≥ Expr ")"⇧≥                  ⇒ ‹λ_. ()›
        | IId⇧≥                             ⇒ ‹λ_. ()›
    and
      WExpr :: ‹unit›
        = WExpr⇧= "where"⇧≥ IId⇧≥ "="⇧≥ WExpr⇧≥  ⇒ ‹λ_ _ _. ()›
        | WExpr⇧= "+"⇧≥ Expr⇧=                 ⇒ ‹λ_ _. ()›
        | "-"⇧= Expr⇧=                        ⇒ ‹λ_. ()›
        | "("⇧= Expr ")"⇧≥                   ⇒ ‹λ_. ()›
        | IId⇧=                              ⇒ ‹λ_. ()›

parser (diagnostics) iswim_parse2 for iswim

text ‹‹iswim› keeps conflicts, and its start symbol takes every column, so most
  of its errors are not about columns. Inside a ‹where› clause, ‹"-"= Expr=›
  anchors the operand at the ‹-›, and ‹IId≥› puts it at or right of that.›

parser_check ‹(case iswim_parse2_diag [tu 1 IId ''x'', tu 3 IWhere ''where'', tu 9 IId ''y'', tu 11 IEq ''='',
      tu 2 IMinus ''-'', tu 0 IId ''z''] of
    Inl e ⇒ pe_index e = 5 ∧ pe_kind e = Offside [(2, None)] ∧
      pe_anchor e = Some (tu 2 IMinus ''-'') ∧ set (pe_expected e) = {IId, IMinus, ILP}
  | Inr _ ⇒ False)›

subsection ‹The representative columns against a scan of every column›

text ‹The claim behind const‹lreps›: the trials at the representative columns
  decide every column. For each rejected word ‹pre @ u›, ‹u› up to length ‹n›
  over the terminals ‹ts› at the columns ‹cs›, every terminal is tried at every
  column below ‹K› and compared with the reported columns. The result counts the
  rejected words and those with an const‹Offside› or const‹Misaligned› report,
  and lists the disagreements.›

definition col_check :: ‹(unit, unit, 'p, 'n, 't) astep ⇒ (('p, 't) agconfig ⇒ bool) ⇒
    'p aitem list ⇒ 'p aitem list ⇒ nat ⇒ 't list ⇒ ('t × nat) list ⇒ nat list ⇒
    nat ⇒ nat ⇒ nat × nat × (('t × nat) list × ('t × nat) list) list› where
  ‹col_check stp fin xin xclos i0 ts pre cs n K =
     (let ws = map (λu. pre @ u) (words [(t, k). t ← ts, k ← cs] n);
          rs = List.map_filter (λw. let tw = map (λ(t, k). tu k t []) w in
                 (case ldiag_run stp fin xin xclos i0 tw of
                   Some (DStuck kd st sh) ⇒
                     Some (w, ldperr stp fin ts (length tw) (Some (DStuck kd st sh)), fst sh)
                 | _ ⇒ None)) ws;
          lay = filter (λ(w, e, c). case pe_kind e of Offside _ ⇒ True | Misaligned _ ⇒ True
                                                   | _ ⇒ False) rs;
          bad = List.map_filter (λ(w, e, c).
                  let m = [(t, k). t ← ts, k ← [0..<K],
                           col_in k (case map_of (pe_columns e) t of None ⇒ [] | Some cs ⇒ cs) ≠
                           ltry stp fin c (Some (t, k))]
                  in if m = [] then None else Some (w, m)) rs
      in (length rs, length lay, bad))›

ML ‹
  fun check_cols ctxt name t =
    let val r = Value_Command.value ctxt t in
      (case HOLogic.strip_tuple r of
        [n, l, bad] =>
          (case try HOLogic.dest_list bad of
            SOME [] => writeln (name ^ ": the columns agree with the scan on " ^
              Syntax.string_of_term ctxt n ^ " rejected words, " ^
              Syntax.string_of_term ctxt l ^ " of them reported Offside or Misaligned")
          | _ => error (name ^ ": columns disagree with the scan:\n" ^ Syntax.string_of_term ctxt bad))
      | _ => error "check_cols")
    end
›

ML ‹
  check_cols context "do"
    term‹col_check (sdstep_dact do_parse2_stab) (sgfinal do_parse2_stab)
      do_parse2_sinit do_parse2_sclos do_parse2_i0
      [DDo, DId] [] [0, 1, 2, 4, 6] 4 12›
›

ML ‹
  check_cols context "do, nested"
    term‹col_check (sdstep_dact do_parse2_stab) (sgfinal do_parse2_stab)
      do_parse2_sinit do_parse2_sclos do_parse2_i0
      [DDo, DId] [(DDo, 1), (DDo, 4)] [1, 3, 4, 5, 7, 9] 3 14›
›

ML ‹
  check_cols context "hask_case"
    term‹col_check (sdstep_dact hask_case_parse2_stab) (sgfinal hask_case_parse2_stab)
      hask_case_parse2_sinit hask_case_parse2_sclos hask_case_parse2_i0
      [HCase, HOf, HLC, HRC, HSemi, HId]
      [(HCase, 1), (HId, 6), (HOf, 8)] [2, 3, 4, 9] 3 14›
›

ML ‹
  check_cols context "py_suite"
    term‹col_check (sdstep_dact py_parse2_stab) (sgfinal py_parse2_stab)
      py_parse2_sinit py_parse2_sclos py_parse2_i0
      [PWhile, PColon, PId]
      [(PWhile, 1), (PId, 7), (PColon, 8)] [0, 2, 3, 4, 6] 3 14›
›

ML ‹
  check_cols context "iswim"
    term‹col_check (sdstep_dact iswim_parse2_stab) (sgfinal iswim_parse2_stab)
      iswim_parse2_sinit iswim_parse2_sclos iswim_parse2_i0
      [IWhere, IPlus, IMinus, IEq, ILP, IRP, IId]
      [] [0, 2, 4] 3 10›
›

ML ‹
  check_cols context "iswim, where"
    term‹col_check (sdstep_dact iswim_parse2_stab) (sgfinal iswim_parse2_stab)
      iswim_parse2_sinit iswim_parse2_sclos iswim_parse2_i0
      [IWhere, IPlus, IMinus, IEq, ILP, IRP, IId]
      [(IId, 1), (IWhere, 3), (IId, 9), (IEq, 11)] [0, 2, 9, 11, 12] 2 16›
›

text ‹The same with a conflict in the tables, where a run may restart on the sparse
  driver.›

parser_check ‹list_all (λw. let w' = map (λ(x, i). tu i x []) w in
    iswim_parse2_diag w' = (case iswim_parse2 w' of Some x ⇒ Inr x
      | None ⇒ Inl (sdiagnose iswim_parse2_stab iswim_parse2_sinit iswim_parse2_sclos
                    iswim_parse2_i0 (map fst iswim_parse2_terminals) w')))
    (words [(IId, 0), (IId, 2), (IWhere, 2), (IEq, 3), (IPlus, 4), (ILP, 1), (IRP, 1)] 4)›

text ‹Those conflicts are between a shift and a reduction, which the vector driver
  resolves by itself. It stops only on two live reductions (expected warning), and
  there the one pass restarts on the sparse driver.›

grammar (relation) rr =
  tokens ‹abc_tok›
  productions S :: ‹nat› = A PC ⇒ ‹λa _. a› | B PC ⇒ ‹λb _. b›
    and A :: ‹nat› = PA ⇒ ‹λ_. 0›
    and B :: ‹nat› = PA ⇒ ‹λ_. 1›

parser (diagnostics) rr_parse for rr

parser_check ‹(let w = [tu 1 PA [], tu 2 PC []]; st = ([v_av0 rr_parse_vtab], vtcols rr_parse_vtab w, w, [])
    in vdrun rr_parse_vtab st st = Some VConflict)›

parser_check ‹list_all (λw. let w' = map (λ(x, i). tu i x []) w in
    rr_parse_diag w' = (case rr_parse w' of Some x ⇒ Inr x
      | None ⇒ Inl (sdiagnose rr_parse_stab rr_parse_sinit rr_parse_sclos
                    rr_parse_i0 (map fst rr_parse_terminals) w')))
    (words [(PA, 1), (PB, 2), (PC, 2)] 4)›

parser_check ‹(case rr_parse_diag [tu 1 PA [], tu 2 PC [], tu 3 PC []] of
    Inl e ⇒ pe_index e = 2 ∧ pe_expected e = [] ∧ pe_expect_end e
  | Inr _ ⇒ False)›

section ‹Messages›

text ‹‹p_info› collects what the messages need: the grammar, the LR(0)
  kernels, the spellings of the terminals and the nonterminals' names. For tokens
  over typ‹char› or typ‹unit›, ‹p_render› is
  const‹perr_render› with it. The grammars below take tokens over
  typ‹char›, so a payload token is shown by its text. The messages are checked
  line by line: const‹pmsg_lines› of const‹perr_message›, which
  const‹perr_render› joins with newlines.›

definition tc :: ‹nat ⇒ nat ⇒ 'tok ⇒ string ⇒ ('tok, char) token› where
  ‹tc l c x s = ⦇tok = x, span = span.make l c c (length s) s⦈›

datatype m_tok = MX | MNum | MPlus | MSemi | MLP | MRP

grammar (relation) m_lay =
  tokens ‹(m_tok, char) token›
  terminals "+" = MPlus and ";" = MSemi and "(" = MLP and ")" = MRP
  productions
    S :: ‹nat list› = E ";" S ⇒ ‹λe s. e # s› | E ⇒ ‹λe. [e]›
  and
    E :: ‹nat› = E "+" T ⇒ ‹λa b. a + b› | T
  and
    T :: ‹nat› = N | "(" E ")" ⇒ ‹λe. e›
  and
    N :: ‹nat› = MX ⇒ ‹λ_. 1› | MNum ⇒ ‹λ_. 2›

parser (diagnostics) m_lay_parse for m_lay

parser_check ‹(case m_lay_parse_diag [tc 0 0 MX ''x'', tc 0 2 MPlus ''+'', tc 0 4 MPlus ''+''] of
    Inl e ⇒ pmsg_lines (perr_message m_lay_parse_info (λc. [c]) e) | Inr _ ⇒ []) =
  [''0:4: syntax error at '+' (after '+')'',
   ''  expected: '(', 'MX' or '' @ squote ''MNum'',
   ''  up to here: '' @ squote ''x +'']›

text ‹Past const‹pi_k› expected terminals (5 in ‹p_info›) the summary takes
  over: with 1, the three here are FIRST(‹T›), and ‹T› follows the dot in the
  kernel of the last shift.›

parser_check ‹(case m_lay_parse_diag [tc 0 0 MX ''x'', tc 0 2 MPlus ''+'', tc 0 4 MPlus ''+''] of
    Inl e ⇒ pmsg_lines (perr_message (m_lay_parse_info⦇pi_k := 1⦈) (λc. [c]) e) | Inr _ ⇒ []) =
  [''0:4: syntax error at '+' (after '+')'',
   ''  expected: a T'',
   ''  up to here: '' @ squote ''x +'']›

text ‹At the end of the input the position is right after the last token, and
  the stack holds a whole ‹E›. The ‹(› is still open and its closer is expected, so
  the bracket is the primary text, and the generic text becomes a note.›

parser_check ‹(case m_lay_parse_diag [tc 0 0 MLP ''('', tc 0 1 MX ''x'', tc 0 3 MPlus ''+'', tc 1 0 MNum ''12''] of
    Inl e ⇒ pmsg_lines (perr_message m_lay_parse_info (λc. [c]) e) | Inr _ ⇒ []) =
  [''1:2: '' @ squote ''('' @ '' at 0:0 is not closed'',
   ''  syntax error at end of input (after '' @ squote ''12'' @ '')'',
   ''  expected: '' @ squote ''+'' @ '' or '' @ squote '')'',
   ''  up to here: an E was recognised: '' @ squote ''x + 12'']›

parser_check ‹(case m_lay_parse_diag [] of
    Inl e ⇒ pmsg_lines (perr_message m_lay_parse_info (λc. [c]) e) | Inr _ ⇒ []) =
  [''0:0: syntax error at end of input'',
   ''  expected: '(', 'MX' or '' @ squote ''MNum'']›

subsubsection ‹Unclosed brackets and classes›

text ‹The brackets come from the productions: ‹+› and ‹;› pair with nothing.›

parser_check ‹brackets (pi_G m_lay_parse_info) = [(MLP, MRP)]›

text ‹The closer not expected: the bracket is not the error, an operand is missing.›

parser_check ‹hd (case m_lay_parse_diag [tc 0 0 MLP ''('', tc 0 1 MX ''x'', tc 0 3 MPlus ''+''] of
    Inl e ⇒ pmsg_lines (perr_message m_lay_parse_info (λc. [c]) e) | Inr _ ⇒ []) =
  ''0:4: syntax error at end of input (after '' @ squote ''+'' @ '')''›

text ‹A token with no action inside a bracket leaves the closer expected, and says
  nothing by itself; a repair decides.›

definition m_stray :: ‹m_tok rop list ⇒ string› where
  ‹m_stray r = (case m_lay_parse_diag [tc 0 0 MLP ''('', tc 0 1 MX ''x'', tc 0 3 MNum ''1''] of
     Inl e ⇒ hd (pmsg_lines (perr_message m_lay_parse_info (λc. [c]) (e⦇pe_repair := r⦈)))
   | Inr _ ⇒ [])›

parser_check ‹m_stray [] = ''0:3: syntax error at '' @ squote ''1'' @ '' (after '' @ squote ''x'' @ '')''›
parser_check ‹m_stray [RDel MNum] = m_stray []›
parser_check ‹m_stray [RKeep, RIns MRP 0] = ''0:3: '' @ squote ''('' @ '' at 0:0 is not closed''›

text ‹On a layout grammar a missing closer shows at the next offside token, on a later
  line and left of the bracket. Further right it stays a question of columns.›

grammar (relation) m_off =
  tokens ‹(m_tok, char) token›
  terminals "(" = MLP and ")" = MRP
  productions
    Ds :: ‹nat› = D⇧= ⇒ ‹λd. d› | Ds⇧= D⇧= ⇒ ‹λa b. a + b›
  and
    D :: ‹nat› = MNum⇧= "("⇧> As⇧> ")"⇧> ⇒ ‹λ_ a. a›
  and
    As :: ‹nat› = MX⇧= ⇒ ‹λ_. 1› | As⇧= MX⇧> ⇒ ‹λa _. a›

parser m_off_parse for m_off

definition m_off_first :: ‹(m_tok, char) token list ⇒ string› where
  ‹m_off_first w = (case m_off_parse_diag w of
     Inl e ⇒ hd (pmsg_lines (perr_message m_off_parse_info (λc. [c]) e)) | Inr _ ⇒ [])›

parser_check ‹m_off_first [tc 0 0 MNum ''f'', tc 0 3 MLP ''('', tc 0 4 MX ''x'', tc 1 0 MX ''y''] =
  ''1:0: '' @ squote ''('' @ '' at 0:3 is not closed''›

parser_check ‹take 7 (m_off_first [tc 0 0 MNum ''f'', tc 0 3 MLP ''('', tc 0 4 MX ''x'', tc 1 4 MX ''y'']) =
  ''1:4: 'y''›

text ‹Classes: after a complete ‹At› nothing follows a dot in the kernel, yet the
  grammar lets another ‹At› follow, and it stands for all three of its terminals. The
  separator keeps its name.›

grammar m_app =
  tokens ‹(m_tok, char) token›
  terminals ";" = MSemi and "(" = MLP and ")" = MRP
  productions
    S :: ‹nat› = Sp ";" ⇒ ‹λs. s›
  and
    Sp :: ‹nat› = At | Sp At ⇒ ‹λa b. a + b›
  and
    At :: ‹nat› = MX ⇒ ‹λ_. 1› | MNum ⇒ ‹λ_. 2› | "(" Sp ")" ⇒ ‹λs. s›

parser m_app_parse for m_app

parser_check ‹(case m_app_parse_diag [tc 0 0 MX ''x'', tc 0 2 MPlus ''+''] of
    Inl e ⇒ (pmsg_lines (perr_message (m_app_parse_info⦇pi_k := 2⦈) (λc. [c]) e)) ! 1 | Inr _ ⇒ []) =
  ''  expected: an At or '' @ squote '';''›

text ‹Within the limit the terminals stay as they are.›

parser_check ‹(case m_app_parse_diag [tc 0 0 MX ''x'', tc 0 2 MPlus ''+''] of
    Inl e ⇒ length (expected_text m_app_parse_info e) | Inr _ ⇒ 0) = 4›

datatype md_tok = MDo | MId

grammar (relation) m_do =
  tokens ‹(md_tok, char) token›
  terminals "do" = ‹MDo›
  productions
      Expr :: ‹unit›
        = MId⇧>          ⇒ ‹λ_. ()›
        | "do"⇧> BStmts⇧> ⇒ ‹λ_. ()›
    and
      BStmts :: ‹unit›
        = BExpr⇧=         ⇒ ‹λ_. ()›
        | BStmts⇧= BExpr⇧= ⇒ ‹λ_ _. ()›
    and
      BExpr :: ‹unit›
        = MId⇧=          ⇒ ‹λ_. ()›
        | "do"⇧= BStmts⇧> ⇒ ‹λ_. ()›

parser (diagnostics) m_do_parse for m_do

text ‹A misplaced token is reported with the columns that would accept it and the
  token it must be aligned with.›

parser_check ‹(case m_do_parse_diag [tc 0 1 MDo ''do'', tc 0 4 MDo ''do'', tc 0 7 MId ''x'', tc 1 2 MId ''y''] of
    Inl e ⇒ pmsg_lines (perr_message m_do_parse_info (λc. [c]) e) | Inr _ ⇒ []) =
  [''1:2: 'y' at column 2 must be at columns 4 or 7 (aligned with 'do' at 0:4)'',
   ''  expected: end of input'',
   ''  up to here: a BStmts was recognised: '' @ squote ''do x'']›

text ‹For a word over typ‹unit› tokens there is no text: a token is shown by
  the spelling of its terminal, and what was recognised by its nonterminal only.›

parser_check ‹(case do_parse2_diag [tu 1 DDo ''do'', tu 4 DDo ''do'', tu 7 DId ''x'', tu 2 DId ''y''] of
    Inl e ⇒ do_parse2_render e | Inr _ ⇒ []) =
  ''0:2: 'DId' at column 2 must be at columns 4 or 7 (aligned with 'do' at 0:4)'' @ [CHR 0x0A] @
  ''  expected: end of input'' @ [CHR 0x0A] @
  ''  up to here: a BStmts was recognised''›

subsection ‹Hand-written messages›

text ‹An ⬚‹errors› block attaches messages to error states by example
  cite‹"jeffery2003-lr-error-messages"› cite‹‹Sect.~5› in "pottier2016-lr1-reachability"›. One evaluation of ‹_probe› gives each sentence its
  state; the result is the data ‹_messages›, with no theorem. The block below has
  three good sentences, one with a key on the pair of state and terminal, and
  expected warnings: a word that is accepted, a second sentence for one key, a
  hole below the stack, and a name that is no terminal. All of them leave the
  parser defined.›

datatype me_tok = EInt | EPlus | EComma | ELP | ERP | ELB | ERB

grammar (relation) m_br =
  tokens ‹(me_tok, char) token›
  terminals "+" = EPlus and "," = EComma and "(" = ELP and ")" = ERP and "[" = ELB and "]" = ERB
  productions
    E :: ‹nat› = E "+" A ⇒ ‹λa b. a + b› | A
  and
    A :: ‹nat› = "(" L ")" ⇒ ‹λl. l› | "[" L "]" ⇒ ‹λl. l› | EInt ⇒ ‹λ_. 1›
  and
    L :: ‹nat› = E | E "," L ⇒ ‹λe l. e + l›

parser (diagnostics) m_br_parse for m_br
  errors
    "(" "]" ⇒ ‹An expression must follow $0.›
  | "(" EInt ")" ")" ⇒ ‹One closing parenthesis too many.›
  | "(" EInt "]" ⇒ ‹Unclosed '(': after $0, ')' is expected.›
  | "(" EInt "+" "]" (token) ⇒ ‹']' cannot follow $0 here.›
  | EInt ⇒ ‹never reached: the word is accepted›
  | "(" "+" ⇒ ‹never used: the key of the first sentence›
  | "[" EInt "]" "+" "]" ⇒ ‹Missing an operand after $0, $7.›
  | nonsense ⇒ ‹never used: no such terminal›

definition m_br_lines :: ‹(me_tok, char) token list ⇒ string list› where
  ‹m_br_lines w = (case m_br_parse_diag w of
     Inl e ⇒ pmsg_lines (perr_message m_br_parse_info (λc. [c]) e) | Inr _ ⇒ [])›

text ‹The hand-written text replaces the primary line, with ‹$0› the text of the
  topmost stack entry, here the whole ‹L›; the position and the notes stay.›

parser_check ‹m_br_lines [tc 0 0 ELP ''('', tc 0 1 EInt ''12'', tc 0 3 EPlus ''+'', tc 0 4 EInt ''3'', tc 0 6 ERB '']''] =
  [''0:6: Unclosed '' @ squote ''('' @ '': after 12+3, '' @ squote '')'' @ '' is expected.'',
   ''  expected: '' @ squote ''+'' @ '', '' @ squote '')'' @ '' or '' @ squote '','',
   ''  up to here: a L was recognised: '' @ squote ''12+3'']›

text ‹The key is the state, so another word reaching it gets the message; the state
  is that of an open bracket, reached here from ‹[›.›

parser_check ‹hd (m_br_lines [tc 0 0 ELP ''('', tc 0 1 ELP ''('', tc 0 2 ERB '']'']) =
  ''0:2: An expression must follow (.''›

text ‹A key on the pair goes before one on the state alone: the sentence with
  ‹$7› has the same state as the one with ‹(token)›, and answers for the other
  terminals. The hole below the stack is empty at run time.›

parser_check
  ‹hd (m_br_lines [tc 0 0 ELP ''('', tc 0 1 EInt ''1'', tc 0 2 EPlus ''+'', tc 0 3 ERB '']'']) =
     ''0:3: '' @ squote '']'' @ '' cannot follow + here.''›

parser_check
  ‹hd (m_br_lines [tc 0 0 ELP ''('', tc 0 1 EInt ''1'', tc 0 2 EPlus ''+'', tc 0 3 ERP '')'']) =
     ''0:3: Missing an operand after +, .''›

text ‹A state without a message keeps the default text.›

parser_check ‹hd (m_br_lines [tc 0 0 ELB ''['', tc 0 1 EInt ''1'', tc 0 2 ERP '')'']) =
  ''0:2: syntax error at '' @ squote '')'' @ '' (after '' @ squote ''1'' @ '')''›

text ‹A ‹$› without a digit is itself.›

parser_check ‹fill_holes (λi. if i = 1 then ''x'' else []) ''$1 costs $y$2.'' = ''x costs $y.''›

text ‹The added constants are ‹_messages› and ‹_probe›, and the code equations stay those of the
  parser without a block.›

parser (no_diagnostics) m_br_plain for m_br

ML ‹same_code context "m_br_plain" "m_br_parse"
  ["_coverage", "_diag", "_info", "_messages", "_probe", "_render", "_terminals"]›

text ‹A layout grammar, on the vector driver: ‹@› gives a token's column, and
  the other tokens follow one past the token before. Keys are the same; the
  message replaces the primary line about the column as well. With ‹(shift)› the
  key is the state after the last shift, before the reductions the offending token
  triggered.›

parser (diagnostics) m_do_msg for m_do
  errors
    "do"@1 "do"@4 MId@7 MId@2 ⇒ ‹This statement is not aligned with $0.›
  | "do"@1 ⇒ ‹A block is expected after 'do'.›
  | MId@1 MId@1 (shift) ⇒ ‹A single expression only, not $0.›

parser_check ‹(case m_do_msg_diag [tc 0 1 MDo ''do'', tc 0 4 MDo ''do'', tc 0 7 MId ''x'', tc 1 2 MId ''y''] of
    Inl e ⇒ pmsg_lines (perr_message m_do_msg_info (λc. [c]) e) | Inr _ ⇒ []) =
  [''1:2: This statement is not aligned with do x.'',
   ''  expected: end of input'',
   ''  up to here: a BStmts was recognised: '' @ squote ''do x'']›

parser_check ‹(case m_do_msg_diag [tc 0 3 MDo ''do''] of
    Inl e ⇒ hd (pmsg_lines (perr_message m_do_msg_info (λc. [c]) e)) | Inr _ ⇒ []) =
  ''0:5: A block is expected after '' @ squote ''do'' @ ''.''›

text ‹Over typ‹unit› tokens a stack entry has no text and ‹$0› is its symbol.›

parser (diagnostics) py_msg for py_suite
  errors
    "while"@1 PId@7 ":"@8 PId@3 PId@4 ⇒ ‹Statements of a suite line up, after $0.›

parser_check ‹(case py_msg_diag [tu 1 PWhile ''while'', tu 7 PId ''x'', tu 8 PColon '':'',
      tu 3 PId ''y'', tu 4 PId ''z''] of
    Inl e ⇒ hd (pmsg_lines (perr_message py_msg_info (λ_. []) e)) | Inr _ ⇒ []) =
  ''0:4: Statements of a suite line up, after '' @ squote ''PId'' @ ''.''›

text ‹Tokens with further fields cannot be built from their terminals: such a
  sentence is a warning, and a word given as a term works.›

parser (diagnostics) t_ext_msg for t_ext
  errors
    ":" ":" ⇒ ‹never used: the tokens have the field trailing›
  | ‹[⦇tok = PColon, span = span.make 0 0 0 1 [], trailing = []⦈,
      ⦇tok = PColon, span = span.make 0 2 2 1 [], trailing = []⦈]› ⇒ ‹An identifier follows ':'.›

parser_check ‹(case t_ext_msg_diag
      [⦇tok = PColon, span = span.make 0 0 0 1 [], trailing = []⦈,
       ⦇tok = PColon, span = span.make 0 2 2 1 [], trailing = []⦈] of
    Inl e ⇒ hd (pmsg_lines (perr_message t_ext_msg_info (λ_. []) e)) | Inr _ ⇒ []) =
  ''0:2: An identifier follows '' @ squote '':'' @ ''.''›

subsection ‹An ‹errors› block cannot fail the parser›

text ‹A sentence with a free variable or without code is dropped with a warning
  (expected), and the others stay.›

axiomatization m_no_code :: ‹(me_tok, char) token list›

parser (diagnostics) m_brx_parse for m_br
  errors
    "(" "]" ⇒ ‹Kept.›
  | ‹[tc 0 0 ELP ''('', y]› ⇒ ‹never used: a free variable›
  | ‹m_no_code› ⇒ ‹never used: no code›

parser_check ‹(case m_brx_parse_diag [tc 0 0 ELP ''('', tc 0 2 ERB '']''] of
    Inl e ⇒ hd (pmsg_lines (perr_message m_brx_parse_info (λc. [c]) e)) | Inr _ ⇒ []) =
  ''0:2: Kept.''›

subsection ‹The words of the block are not keywords›

lemma errors: ‹True› by (fact TrueI)

subsection ‹Columns›

text ‹Linear in the ends, however large the columns.›

parser_check ‹col_reps [1000000, 2, 2] = [0, 1, 2, 3, 999999, 1000000, 1000001]›

subsection ‹The state-indexed driver›

text ‹Constructors without arguments are numbered by a case distinction.›

parser_check ‹map rr_parse_tnum [PA, PB, PC] = map (vnum rr_parse_vtab) [PA, PB, PC]›

text ‹Under text‹parser_literal_tables› its tables are literals (expected warning,
  as for ‹rr_parse›), and nothing else changes.›

declare [[parser_literal_tables]]
parser (diagnostics) rr_lit_parse for rr
declare [[parser_literal_tables = false]]

parser_check ‹list_all (λw. let w' = map (λ(x, i). tu i x []) w in
    rr_lit_parse_diag w' = rr_parse_diag w')
    (words [(PA, 1), (PB, 2), (PC, 2)] 4)›

subsection ‹Exported code›

text ‹The parsers with their messages compile in every target.›

export_code lay_parse_diag lay_parse_render do_parse2_diag do_parse2_render
  m_br_parse_diag m_br_parse_render checking SML Scala

export_code lay_parse_diag lay_parse_render do_parse2_diag do_parse2_render in Haskell

export_code lay_parse_diag lay_parse_render do_parse2_diag do_parse2_render in OCaml

end