Theory LR_Diag

(* Author: Basil Fürer *)

theory LR_Diag
  imports LR_Plain LR_Sparse LR_Vec
begin

section ‹Diagnosing a rejected word›

text ‹When the parser rejects a word, the diagnostics rerun its steps and stop
  where the run fails. Nothing here is proved about errors: the parser's
  result decides acceptance, and the diagnostics only describe a rejection.›

subsection ‹The error›

text ‹A set of columns as a list of intervals, ascending: ‹(a, Some b)› is
  ‹{a..b}›, ‹(a, None)› is ‹{a..}›.›

type_synonym colset = ‹(nat × nat option) list›

text ‹The kind of a failure: the step function has no action
  (‹NoAction›), or the loop check finds a configuration that repeats between
  two shifts (‹ReduceCycle›). On a layout grammar the offending token may be
  accepted at another column: ‹Offside› when the accepted column nearest to
  it lies in an interval unbounded to the right (it must be indented further, a
  ‹>› or ‹≥› relation), ‹Misaligned› when that interval is bounded (it
  must be aligned, a ‹=› relation); each carries all accepted columns.›

datatype perr_kind = NoAction | ReduceCycle | Offside colset | Misaligned colset

text ‹A step of a repair sequence cite‹‹Sect.~4› in "diekmann2020-dont-panic"›: a terminal inserted at a
  column, a token deleted, a token kept.›

datatype 't rop = RIns 't nat | RDel 't | RKeep

text ‹The error, over the token type of the parser's input, so that a token
  record extended by the user (‹'m›) keeps its fields: the index of the
  offending token in the input, the token (‹None› at the end of the input),
  the state on top of the stack where the error is detected (after the
  reductions the offending token triggered: the state that hand-written messages
  are keyed on cite‹‹Sect.~5› in "pottier2016-lr1-reachability"›), the kind, the terminals that would have been
  accepted in place of the offending token, and whether the end of the input
  would have been. On a layout grammar also each expected terminal with the
  columns at which it would have been accepted, and for const‹Offside› or
  const‹Misaligned› the token the offending one must be indented from or
  aligned with; both are empty for a grammar without layout. Last, for the
  messages: the state after the last shift, before those reductions (the state
  whose kernel says what was being parsed), the stack where the error is
  detected, top first, each entry as its symbol and the spans of its tokens
  (the ‹$0, $1, …› of cite‹‹Sect.~5› in "pottier2016-lr1-reachability"›: what was recognised up to here), and the repair the
  recovery chose, empty if it chose none.›

record ('n, 't, 'ch, 'm) perr =
  pe_index :: nat
  pe_tok :: ‹('t, 'ch, 'm) token_scheme option›
  pe_state :: nat
  pe_kind :: perr_kind
  pe_expected :: ‹'t list›
  pe_expect_end :: bool
  pe_columns :: ‹('t × colset) list›
  pe_anchor :: ‹('t, 'ch, 'm) token_scheme option›
  pe_shift_state :: nat
  pe_stack :: ‹(('n, 't) sym × 'ch span list) list›
  pe_repair :: ‹'t rop list›

subsection ‹The engine›

text ‹The engine works on any configuration type ‹'c›, given the step
  ‹ctl›, the final test ‹fin›, the key of a configuration for the loop check
  (between shifts the input does not change, so the stack suffices), the
  remaining input and the token of an input element. It carries the AST stack
  as const‹brun› does, and the configuration right after the last shift. The
  loop check is const‹brun›'s (Brent's method
  cite‹"brent1980-monte-carlo-factorization"›, const‹bupd›). Termination is
  not proved, as for const‹brun›.›

datatype ('c, 'a) dstop =
    DDone ‹'c × 'a list›
  | DStuck perr_kind ‹'c × 'a list› ‹'c × 'a list›

partial_function (option) drun_diag ::
  ‹('c ⇒ (('n, 't) dact × 'c) option) ⇒ ('c ⇒ bool) ⇒ ('c ⇒ 'k list) ⇒
    ('c ⇒ 'w list) ⇒ ('w ⇒ ('t, 'ch, 'm) token_scheme) ⇒ 'k list option × nat × nat ⇒
    'c × ('m, 'ch, 'n, 't) ast list ⇒ 'c × ('m, 'ch, 'n, 't) ast list ⇒
    ('c, ('m, 'ch, 'n, 't) ast) dstop option›
  where
  ‹drun_diag ctl fin key inp dec d sh st = (case st of (c, tstk) ⇒
     if fin c then Some (DDone st)
     else if fst d = Some (key c) then Some (DStuck ReduceCycle st sh)
     else (case ctl c of
       None ⇒ Some (DStuck NoAction st sh)
     | Some (act, c') ⇒
         let st' = (c', xtree dec act (inp c) tstk)
         in if act = DShift then drun_diag ctl fin key inp dec (None, 1, 1) st' st'
            else drun_diag ctl fin key inp dec (bupd d (key c)) sh st'))›

lemmas drun_diag_simps [code] = drun_diag.simps

subsection ‹The expected terminals›

text ‹What would have been accepted at the error is computed on the actual
  stack, not read off a state: a trial starts from the configuration right
  after the last shift, before any reduction the offending token triggered, with
  a candidate as the lookahead, and runs the step until it shifts the candidate
  (expected), fails or repeats a configuration (not expected). For the end of
  the input the trial runs until the final test holds instead. Only reductions
  come before that shift, so a trial is short; its loop check starts afresh.
  This avoids both errors of a static reading cite‹‹Sect.~4› in "pottier2016-lr1-reachability"›: an
  LALR state merges lookaheads that are not valid on this stack, and the
  reductions on the offending token commit to one reading and lose
  futures that were valid before them.

  The set is what ∗‹this› parser accepts: where the tables keep a conflict,
  the step takes the first licensed candidate, and so does the trial.›

partial_function (option) dtrial ::
  ‹('c ⇒ (('n, 't) dact × 'c) option) ⇒ ('c ⇒ bool) ⇒ ('c ⇒ 'k list) ⇒
    'k list option × nat × nat ⇒ 'c ⇒ bool option›
  where
  ‹dtrial ctl fin key d c =
     (if fin c then Some True
      else if fst d = Some (key c) then Some False
      else (case ctl c of
        None ⇒ Some False
      | Some (act, c') ⇒
          if act = DShift then Some True else dtrial ctl fin key (bupd d (key c)) c'))›

lemmas dtrial_simps [code] = dtrial.simps

text ‹The candidates that pass their trial, and whether the end of the input
  does; ‹la› sets the lookahead of the saved configuration to a candidate
  (‹Some›) or to the end of the input (‹None›).›

definition dexpect :: ‹('c ⇒ (('n, 't) dact × 'c) option) ⇒ ('c ⇒ bool) ⇒ ('c ⇒ 'k list) ⇒
    ('x option ⇒ 'c) ⇒ 'x list ⇒ 'x list × bool› where
  ‹dexpect ctl fin key la xs =
     (filter (λx. dtrial ctl fin key (None, 1, 1) (la (Some x)) = Some True) xs,
      dtrial ctl fin key (None, 1, 1) (la None) = Some True)›

text ‹The stack of an error: each tree as its root symbol and the spans of its
  tokens, in input order.›

fun aspans :: ‹('m, 'ch, 'n, 't) ast ⇒ 'ch span list ⇒ 'ch span list›
  and aspanss :: ‹('m, 'ch, 'n, 't) ast list ⇒ 'ch span list ⇒ 'ch span list› where
  ‹aspans (Leaf x) acc = span x # acc›
| ‹aspans (Node n ts) acc = aspanss ts acc›
| ‹aspanss [] acc = acc›
| ‹aspanss (t # ts) acc = aspans t (aspanss ts acc)›

fun aroot :: ‹('m, 'ch, 'n, 't) ast ⇒ ('n, 't) sym› where
  ‹aroot (Leaf x) = Tm (tok x)›
| ‹aroot (Node n ts) = Nt n›

definition estack :: ‹('m, 'ch, 'n, 't) ast list ⇒ (('n, 't) sym × 'ch span list) list› where
  ‹estack tstk = map (λt. (aroot t, aspans t [])) tstk›

text ‹The error at a stop, given the state number and the remaining input of a
  configuration and the length of the word. The parser fails on the word, so the
  run does not reach a final configuration (‹DDone›) and terminates (‹None›
  only stands for a run without end); both are reported nonetheless, at the
  final configuration and as a cycle at the start.›

definition dperr :: ‹('c ⇒ nat) ⇒ ('c ⇒ 'w list) ⇒ ('w ⇒ ('t, 'ch, 'm) token_scheme) ⇒
    ('c ⇒ 't list × bool) ⇒ nat ⇒ ('c, ('m, 'ch, 'n, 't) ast) dstop option ⇒
    ('n, 't, 'ch, 'm) perr› where
  ‹dperr state inp dec ex n r = (case r of
       None ⇒ ⦇pe_index = 0, pe_tok = None, pe_state = 0, pe_kind = ReduceCycle,
         pe_expected = [], pe_expect_end = False, pe_columns = [], pe_anchor = None,
         pe_shift_state = 0, pe_stack = [], pe_repair = []⦈
     | Some s ⇒
         let (k, st, sh) = (case s of DDone st ⇒ (NoAction, st, st)
                                   | DStuck k st sh ⇒ (k, st, sh));
             c = fst st;
             (ts, e) = ex (fst sh)
         in ⦇pe_index = n - length (inp c),
            pe_tok = (case inp c of [] ⇒ None | x # _ ⇒ Some (dec x)),
            pe_state = state c, pe_kind = k, pe_expected = ts, pe_expect_end = e,
            pe_columns = [], pe_anchor = None, pe_shift_state = state (fst sh),
            pe_stack = estack (snd st), pe_repair = []⦈)›

text ‹The drivers report the symbols of the grammar the tables are built from. For a
  restricted grammar ‹orig› gives them the names of the grammar the user wrote.›

definition pe_names :: ‹('n ⇒ 'n) ⇒ ('n, 't, 'ch, 'm) perr ⇒ ('n, 't, 'ch, 'm) perr› where
  ‹pe_names orig e = e⦇pe_stack := map (λ(X, s).
     (case X of Nt n ⇒ Nt (orig n) | Tm t ⇒ Tm t, s)) (pe_stack e)⦈›

definition pe_diag_names :: ‹('n ⇒ 'n) ⇒ ('n, 't, 'ch, 'm) perr + 'x ⇒
    ('n, 't, 'ch, 'm) perr + 'x› where
  ‹pe_diag_names orig r = (case r of Inl e ⇒ Inl (pe_names orig e) | Inr x ⇒ Inr x)›

lemma pe_diag_names_Inr_iff: ‹pe_diag_names orig r = Inr x ⟷ r = Inr x›
  by (simp add: pe_diag_names_def split: sum.split)

definition pe_stop_names :: ‹('n ⇒ 'n) ⇒ (nat ⇒ 'w ⇒ (('n, 't, 'ch, 'm) perr × 'p) option) ⇒
    nat ⇒ 'w ⇒ (('n, 't, 'ch, 'm) perr × 'p) option› where
  ‹pe_stop_names orig stop b w = map_option (λ(e, pl). (pe_names orig e, pl)) (stop b w)›

subsection ‹The layout-free adapter›

text ‹The step of the simple driver on the plain action table
  (const‹pctl›, const‹pfinal›) over the input numbered by const‹tenc›, started as
  the parser's code equation starts const‹brun›. This is the only place that
  knows the tables.›

definition pstate :: ‹nat list × 'w list ⇒ nat› where
  ‹pstate c = (case fst c of [] ⇒ 0 | k # _ ⇒ k)›

definition pdiag_run :: ‹('n, 't) ptabs ⇒ nat ⇒ ('t ⇒ nat) ⇒ ('t, 'ch, 'm) token_scheme list ⇒
    (nat list × (('t, 'ch, 'm) token_scheme × nat) list, ('m, 'ch, 'n, 't) ast) dstop option› where
  ‹pdiag_run P i0 f w =
     (let st = (([i0], map (tenc f) w), [])
      in drun_diag (pctl P) (pfinal P) fst snd fst (None, 1, 1) st st)›

text ‹A trial needs a token of the lookahead's terminal, but stops at its
  shift and never reads it beyond its number; it gets an empty span, so the
  candidates can be terminals and the end of the input needs no token.›

definition ptrial :: ‹('t ⇒ nat) ⇒ nat list ⇒ 't option ⇒
    nat list × (('t, unit) token × nat) list› where
  ‹ptrial f kstk x = (kstk, case x of None ⇒ []
     | Some t ⇒ [tenc f ⦇tok = t, span = ⦇s_line = 0, s_col = 0, s_off = 0, s_len = 0, s_txt = []⦈⦈])›

definition pexpect :: ‹('n, 't) ptabs ⇒ ('t ⇒ nat) ⇒ 't list ⇒ nat list × 'w ⇒ 't list × bool› where
  ‹pexpect P f ts c = dexpect (pctl P) (pfinal P) fst (ptrial f (fst c)) ts›

text ‹The error of a rejected word, with the terminals ‹ts› as candidates.›

definition pdiagnose :: ‹('n, 't) ptabs ⇒ nat ⇒ ('t ⇒ nat) ⇒ 't list ⇒
    ('t, 'ch, 'm) token_scheme list ⇒ ('n, 't, 'ch, 'm) perr› where
  ‹pdiagnose P i0 f ts w = dperr pstate snd fst (pexpect P f ts) (length w) (pdiag_run P i0 f w)›

subsection ‹The set-anchored adapter›

text ‹The step of the set-anchored driver of the parser's code equation, on the
  control part of a driver state and the depth of its stack: const‹dstep_act›
  for the dense drivers (const‹drunwf›, const‹drun_nh_c›), the step of
  const‹sdrun› for the sparse one. Both keep a stack of closures whose items are
  a production, a dot and an anchor set, and differ only in how they represent
  the production, so the adapter is generic in it (‹'p›) and takes the step
  ‹stp› and the final test ‹fin›. The closures come from the cache stack, as
  in the parser, so a step computes only the closure of the frame it pushes; the
  AST stack is the engine's. The step keeps the depth, and the loop check
  compares it first, so two configurations of a chain of reductions are told
  apart without walking their stacks. A step is used at two token types, the
  parser's for the run and ‹unit› for the trials, so the functions below take
  one instance each.›

type_synonym 'p aitem = ‹'p × nat × indrep›

type_synonym ('p, 't) agconfig = ‹'p aitem list list × ('t × nat) list›

type_synonym ('m, 'ch, 'p, 'n, 't) ast_st =
  ‹('p, 't) agconfig × 'p aitem list list × nat list × ('m, 'ch, 't) tword ×
   ('m, 'ch, 'n, 't) ast list›

type_synonym ('m, 'ch, 'p, 'n, 't) astep =
  ‹('m, 'ch, 'p, 'n, 't) ast_st ⇒ (('n, 't) dact × ('m, 'ch, 'p, 'n, 't) ast_st) option›

type_synonym ('m, 'ch, 'p, 't) lcfg =
  ‹(('p, 't) agconfig × 'p aitem list list × nat list × ('m, 'ch, 't) tword) × nat›

definition lctl :: ‹('m, 'ch, 'p, 'n, 't) astep ⇒
    ('m, 'ch, 'p, 't) lcfg ⇒ (('n, 't) dact × ('m, 'ch, 'p, 't) lcfg) option› where
  ‹lctl stp c = (case c of ((gc, cstk, istk, v), n) ⇒
     map_option (λ(a, (gc', cstk', istk', v', _)). (a, (gc', cstk', istk', v'),
         case a of DShift ⇒ Suc n | DReduce pr ⇒ Suc (n - length (snd pr))))
       (stp (gc, cstk, istk, v, [])))›

definition lfin :: ‹(('p, 't) agconfig ⇒ bool) ⇒ ('m, 'ch, 'p, 't) lcfg ⇒ bool› where
  ‹lfin fin c = fin (fst (fst c))›

definition lkey :: ‹('m, 'ch, 'p, 't) lcfg ⇒
    (nat × 'p aitem list list × 'p aitem list list × nat list) list› where
  ‹lkey c = (case c of (((Xs, w), cstk, istk, v), n) ⇒ [(n, Xs, cstk, istk)])›

definition linp :: ‹('m, 'ch, 'p, 't) lcfg ⇒ ('m, 'ch, 't) tword› where
  ‹linp c = (case c of ((gc, cstk, istk, v), n) ⇒ v)›

definition lstate :: ‹('m, 'ch, 'p, 't) lcfg ⇒ nat› where
  ‹lstate c = (case c of ((gc, cstk, istk, v), n) ⇒ (case istk of [] ⇒ 0 | k # _ ⇒ k))›

text ‹The run, started as the code equation starts the driver.›

definition ldiag_run :: ‹('m, 'ch, 'p, 'n, 't) astep ⇒ (('p, 't) agconfig ⇒ bool) ⇒
    'p aitem list ⇒ 'p aitem list ⇒ nat ⇒ ('m, 'ch, 't) tword ⇒
    (('m, 'ch, 'p, 't) lcfg, ('m, 'ch, 'n, 't) ast) dstop option› where
  ‹ldiag_run stp fin xin xclos i0 w =
     (let c = ((([xin], tcols w), [xclos], [i0], w), 1)
      in drun_diag (lctl stp) (lfin fin) lkey linp id (None, 1, 1) (c, []) (c, []))›

text ‹A trial puts a candidate, a terminal at a column, as the only lookahead on
  the saved configuration, into the input of the machine and of the driver
  alike: the former is const‹tcols› of the latter, so the two agree. The token
  is fresh, as in the layout-free adapter, since the end of the input has no
  offending token to change; the step reads only its terminal and its column,
  and the trial stops at its shift.›

definition ltrial :: ‹('m, 'ch, 'p, 't) lcfg ⇒ ('t × nat) option ⇒ (unit, unit, 'p, 't) lcfg› where
  ‹ltrial c x = (case c of (((Xs, w), cstk, istk, v), n) ⇒
     let v' = (case x of None ⇒ []
       | Some (t, k) ⇒ [⦇tok = t, span = ⦇s_line = 0, s_col = k, s_off = 0, s_len = 0, s_txt = []⦈⦈])
     in (((Xs, tcols v'), cstk, istk, v'), n))›

definition ltry :: ‹(unit, unit, 'p, 'n, 't) astep ⇒ (('p, 't) agconfig ⇒ bool) ⇒
    ('m, 'ch, 'p, 't) lcfg ⇒ ('t × nat) option ⇒ bool› where
  ‹ltry stp fin c x = (dtrial (lctl stp) (lfin fin) lkey (None, 1, 1) (ltrial c x) = Some True)›

subsection ‹Columns›

text ‹Which columns to try. A step compares the column of the lookahead only
  with anchor sets: those of the frames when it licenses a reduce
  (const‹dlic›, const‹irep_ex_wsat›), and the set it intersects with the
  preimage of the singleton column when it shifts (const‹lgoto›,
  const‹irep_pre›). Each comparison is membership, a bound by the least or the
  greatest element, or by one more or less, so its outcome changes only next to
  the end of a run of consecutive columns in some set. The sets of a trial are
  those of the saved stack and its closures, and those its reductions derive from
  them. So we try ‹0› and the columns next to the ends of the runs of the sets
  on the saved stack and its closures, and take acceptance as constant between
  two of them. The derived sets are not scanned: that they add no ends is a claim
  checked on the tests against a scan of every column, not proved.›

definition run_ends :: ‹nat list ⇒ nat list› where
  ‹run_ends xs = filter (λx. x - 1 ∉ set xs ∨ Suc x ∉ set xs) xs›

fun irep_ends :: ‹indrep ⇒ nat list› where
  ‹irep_ends (FinRep xs) = run_ends xs›
| ‹irep_ends (UpRep xs n) = n # run_ends xs›

text ‹The columns next to the ends ‹es›, ascending and distinct: their cost
  follows the number of ends, not how large a column is.›

fun col_ins :: ‹nat ⇒ nat list ⇒ nat list› where
  ‹col_ins x [] = [x]›
| ‹col_ins x (y # ys) =
     (if x < y then x # y # ys else if x = y then y # ys else y # col_ins x ys)›

definition col_reps :: ‹nat list ⇒ nat list› where
  ‹col_reps es = fold col_ins (concat (map (λe. [e - 1, e, Suc e]) es)) [0]›

definition lreps :: ‹('m, 'ch, 'p, 't) lcfg ⇒ nat list› where
  ‹lreps c = (case c of (((Xs, w), cstk, istk, v), n) ⇒
     col_reps (concat (map (λ(pr, m, R). irep_ends R) (concat (Xs @ cstk)))))›

text ‹The accepted columns as intervals, from the outcomes at the tried columns,
  ascending: two accepted neighbours span the columns between them, and an
  accepted last one every column after it.›

fun cols_of :: ‹(nat × bool) list ⇒ colset› where
  ‹cols_of [] = []›
| ‹cols_of ((r, False) # rs) = cols_of rs›
| ‹cols_of ((r, True) # rs) = (case rs of
       [] ⇒ [(r, None)]
     | (_, True) # _ ⇒ (case cols_of rs of (_, h) # is ⇒ (r, h) # is | [] ⇒ [(r, None)])
     | (_, False) # _ ⇒ (r, Some r) # cols_of rs)›

definition col_in :: ‹nat ⇒ colset ⇒ bool› where
  ‹col_in k cs = list_ex (λ(a, b). a ≤ k ∧ (case b of None ⇒ True | Some b ⇒ k ≤ b)) cs›

text ‹The expected terminals, each with the columns at which it is accepted, and
  whether the end of the input is, from a trial at a terminal and column or at the
  end, the columns ‹rs› to try and the candidates ‹ts›.›

definition columns_at :: ‹(('t × nat) option ⇒ bool) ⇒ nat list ⇒ 't list ⇒
    ('t × colset) list × bool› where
  ‹columns_at try rs ts =
     (filter (λ(t, cs). cs ≠ [])
        (map (λt. (t, cols_of (map (λr. (r, try (Some (t, r)))) rs))) ts),
      try None)›

definition lcolumns :: ‹(unit, unit, 'p, 'n, 't) astep ⇒ (('p, 't) agconfig ⇒ bool) ⇒
    't list ⇒ ('m, 'ch, 'p, 't) lcfg ⇒ ('t × colset) list × bool› where
  ‹lcolumns stp fin ts c = columns_at (ltry stp fin c) (lreps c) ts›

subsection ‹The anchor›

text ‹The first token of a tree.›

fun afirst :: ‹('m, 'ch, 'n, 't) ast ⇒ ('t, 'ch, 'm) token_scheme option›
  and afirsts :: ‹('m, 'ch, 'n, 't) ast list ⇒ ('t, 'ch, 'm) token_scheme option› where
  ‹afirst (Leaf t) = Some t›
| ‹afirst (Node n ts) = afirsts ts›
| ‹afirsts [] = None›
| ‹afirsts (t # ts) = (case afirst t of None ⇒ afirsts ts | r ⇒ r)›

text ‹An offending token accepted at other columns is placed against the accepted
  column nearest to it. In an interval unbounded to the right that is its start
  ‹a›, and the token must be indented further than a construct at ‹a - 1› or as
  far as one at ‹a› (const‹Offside›); otherwise it must be aligned with one at
  that column (const‹Misaligned›). The construct is the innermost subtree on the
  AST stack after the last shift that starts at such a column, and the anchor is
  its first token. This matches columns, it does not trace which frame's anchor
  set excluded the token: the frames carry sets of columns, not the tokens that
  fixed them.›

definition lanchor :: ‹nat list ⇒ ('m, 'ch, 'n, 't) ast list ⇒ ('t, 'ch, 'm) token_scheme option› where
  ‹lanchor ks tstk = find (λt. s_col (span t) ∈ set ks) (List.map_filter afirst tstk)›

definition lmisplaced :: ‹nat ⇒ colset ⇒ ('m, 'ch, 'n, 't) ast list ⇒
    perr_kind × ('t, 'ch, 'm) token_scheme option› where
  ‹lmisplaced c cl tstk =
     (let near = (λ(a, b). (case b of None ⇒ (max a c, True) | Some b ⇒ (max a (min c b), False)));
          dist = (λk. if k ≤ c then c - k else k - c);
          cands = map near cl;
          (k, up) = fold (λy x. if dist (fst y) < dist (fst x) then y else x) (tl cands) (hd cands)
      in if up then (Offside cl, lanchor [k - 1, k] tstk) else (Misaligned cl, lanchor [k] tstk))›

subsection ‹The error›

text ‹The error at a stop, from its kind, the size ‹n› of the word, the input left,
  the state at the stop and after the last shift, the columns, and the AST stacks
  after the last shift and at the stop; a token with no action that is accepted at
  another column is const‹Offside› or const‹Misaligned›.›

definition mk_perr :: ‹perr_kind ⇒ nat ⇒ ('m, 'ch, 't) tword ⇒ nat ⇒ nat ⇒
    ('t × colset) list × bool ⇒ ('m, 'ch, 'n, 't) ast list ⇒ ('m, 'ch, 'n, 't) ast list ⇒
    ('n, 't, 'ch, 'm) perr› where
  ‹mk_perr k n v st sh ce tstk' tstk =
     (let (cols, e) = ce;
          tk = (case v of [] ⇒ None | x # _ ⇒ Some x);
          (k', anc) = (case (k, tk) of
              (NoAction, Some x) ⇒ (case map_of cols (tok x) of
                  Some cl ⇒ lmisplaced (s_col (span x)) cl tstk'
                | None ⇒ (k, None))
            | _ ⇒ (k, None))
      in ⦇pe_index = n - length v, pe_tok = tk, pe_state = st, pe_kind = k',
         pe_expected = map fst cols, pe_expect_end = e, pe_columns = cols, pe_anchor = anc,
         pe_shift_state = sh, pe_stack = estack tstk, pe_repair = []⦈)›

text ‹The error at a stop of the set-anchored drivers, with the terminals ‹ts› as
  candidates.›

definition ldperr :: ‹(unit, unit, 'p, 'n, 't) astep ⇒ (('p, 't) agconfig ⇒ bool) ⇒
    't list ⇒ nat ⇒ (('m, 'ch, 'p, 't) lcfg, ('m, 'ch, 'n, 't) ast) dstop option ⇒
    ('n, 't, 'ch, 'm) perr› where
  ‹ldperr stp fin ts n r = (case r of
       None ⇒ dperr lstate linp id (λ_. ([], False)) n r
     | Some s ⇒
         let (k, st, sh) = (case s of DDone st ⇒ (NoAction, st, st)
                                    | DStuck k st sh ⇒ (k, st, sh))
         in mk_perr k n (linp (fst st)) (lstate (fst st)) (lstate (fst sh))
              (lcolumns stp fin ts (fst sh)) (snd sh) (snd st))›

text ‹The error of a word the set-anchored parser rejects: for the dense drivers
  over the tables and the start frame of text‹dparse_via_tables›, for the
  sparse one over the bundle and the start frame of text‹dparse_via_tables_s›.›

definition ldiagnose :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒ ('n, 't) xitem list ⇒
    ('n, 't) xitem list ⇒ nat ⇒ 't list ⇒ ('m, 'ch, 't) tword ⇒ ('n, 't, 'ch, 'm) perr› where
  ‹ldiagnose G Shn gt sts redtab xin xclos i0 ts w =
     ldperr (dstep_act G gt sts redtab) (gfinal G Shn) ts (length w)
       (ldiag_run (dstep_act G gt sts redtab) (gfinal G Shn) xin xclos i0 w)›

definition sdstep_dact :: ‹('n, 't) stab ⇒ ('m, 'ch, 'n, 't) sdst ⇒
    (('n, 't) dact × ('m, 'ch, 'n, 't) sdst) option› where
  ‹sdstep_dact T st = map_option (λ(a, st'). (sdec_act a, st')) (sdstep_act T st)›

definition sdiagnose :: ‹('n, 't) stab ⇒ ('n, 't) sitem list ⇒ ('n, 't) sitem list ⇒
    nat ⇒ 't list ⇒ ('m, 'ch, 't) tword ⇒ ('n, 't, 'ch, 'm) perr› where
  ‹sdiagnose T kin kcl i0 ts w =
     ldperr (sdstep_dact T) (sgfinal T) ts (length w)
       (ldiag_run (sdstep_dact T) (sgfinal T) kin kcl i0 w)›

section ‹One pass›

text ‹The diagnoses above run a rejected word a second time. Here the run that
  decides acceptance keeps what the error needs, so every word is run once: an
  accepted word gives the parser's tree, a rejected one the error where the run
  stopped. The run takes the parser's step unchanged and adds only the
  configuration after the last shift, one argument more, so an accepted word costs
  what the parser costs. For the simple driver that run is const‹drun_diag›,
  whose loop check is const‹brun›'s. The set-anchored drivers without a history
  have no loop check, and their run, ‹arun›, has none either. Only the
  accepted words are proved: the one pass returns a tree exactly when the
  parser does, and the same tree (the ‹Inr_iff› facts below).›

subsection ‹The simple driver›

fun dstop_tree :: ‹('c, ('m, 'ch, 'n, 't) ast) dstop ⇒ ('m, 'ch, 'n, 't) ast option› where
  ‹dstop_tree (DDone st) = sresult (snd st)›
| ‹dstop_tree (DStuck k st sh) = None›

lemma brun_imp_drun_diag:
  assumes ‹brun ctl fin dec d st = Some t›
  shows ‹∀sh. Option.bind (drun_diag ctl fin fst snd dec d sh ((fst st, fst (snd st)), snd (snd st)))
           dstop_tree = Some t›
proof (rule brun.raw_induct[OF _ assms], goal_cases)
  case (1 f ctl fin dec d st t)
  obtain stk v tstk where st: ‹st = (stk, v, tstk)› by (cases st)
  show ?case
  proof (cases ‹fin (stk, v)›)
    case True
    with "1"(2) show ?thesis unfolding st by (simp add: drun_diag.simps)
  next
    case False
    with "1"(2) obtain act stk' v' where nc: ‹fst d ≠ Some stk›
        and c: ‹ctl (stk, v) = Some (act, stk', v')›
        and r: ‹f ctl fin dec (if act = DShift then (None, 1, 1) else bupd d stk)
                 (stk', v', xtree dec act v tstk) = Some t›
      unfolding st by (auto simp: bind_eq_Some_conv split: if_splits)
    from "1"(1)[OF r] have IH: ‹∀sh. Option.bind (drun_diag ctl fin fst snd dec
        (if act = DShift then (None, 1, 1) else bupd d stk) sh ((stk', v'), xtree dec act v tstk))
        dstop_tree = Some t›
      by simp
    show ?thesis
    proof
      fix sh
      show ‹Option.bind (drun_diag ctl fin fst snd dec d sh ((fst st, fst (snd st)), snd (snd st)))
          dstop_tree = Some t›
        using False nc c IH[THEN spec[where x = sh]]
          IH[THEN spec[where x = ‹((stk', v'), xtree dec act v tstk)›]] unfolding st
        by (subst drun_diag.simps) (cases ‹act = DShift›; simp add: Let_def)    qed
  qed
qed

lemma drun_diag_imp_brun:
  assumes ‹drun_diag ctl fin key inp dec d sh st = Some r›
  shows ‹key = fst ⟶ inp = snd ⟶ (∀t. dstop_tree r = Some t ⟶
           brun ctl fin dec d (fst (fst st), snd (fst st), snd st) = Some t)›
proof (rule drun_diag.raw_induct[OF _ assms], goal_cases)
  case (1 f ctl fin key inp dec d sh st r)
  obtain stk v tstk where st: ‹st = ((stk, v), tstk)› by (cases st) auto
  show ?case
  proof (intro impI allI)
    fix t
    assume k: ‹key = fst› and i: ‹inp = snd› and t: ‹dstop_tree r = Some t›
    show ‹brun ctl fin dec d (fst (fst st), snd (fst st), snd st) = Some t›
    proof (cases ‹fin (stk, v)›)
      case True
      with "1"(2) t show ?thesis unfolding st by (subst brun.simps) auto
    next
      case False
      show ?thesis
      proof (cases ‹fst d = Some stk›)
        case True
        with False "1"(2) t show ?thesis unfolding st k by auto
      next
        case nc: False
        show ?thesis
        proof (cases ‹ctl (stk, v)›)
          case None
          with False nc "1"(2) t show ?thesis unfolding st k by auto
        next
          case (Some p)
          then obtain act stk' v' where c: ‹ctl (stk, v) = Some (act, stk', v')›
            by (cases p) auto
          from False nc c "1"(2) obtain sh' where
              rec: ‹f ctl fin key inp dec (if act = DShift then (None, 1, 1) else bupd d stk) sh'
                     ((stk', v'), xtree dec act v tstk) = Some r›
            unfolding st k i by (cases ‹act = DShift›) (auto simp: Let_def)
          from "1"(1)[OF rec] k i t have
              ‹brun ctl fin dec (if act = DShift then (None, 1, 1) else bupd d stk)
                 (stk', v', xtree dec act v tstk) = Some t›
            by simp
          with False nc c show ?thesis unfolding st by (subst brun.simps) simp
        qed
      qed
    qed
  qed
qed

text ‹The parser's run and the diagnosing run, from any saved configuration.›

lemma brun_drun_diag:
  ‹brun ctl fin dec d (stk, v, tstk) =
     Option.bind (drun_diag ctl fin fst snd dec d sh ((stk, v), tstk)) dstop_tree›
proof (cases ‹brun ctl fin dec d (stk, v, tstk)›)
  case None
  show ?thesis
  proof (cases ‹drun_diag ctl fin fst snd dec d sh ((stk, v), tstk)›)
    case (Some r)
    show ?thesis
    proof (cases ‹dstop_tree r›)
      case (Some t)
      from drun_diag_imp_brun[OF ‹drun_diag _ _ _ _ _ _ _ _ = Some r›] Some None show ?thesis
        by simp
    qed (simp add: None ‹drun_diag _ _ _ _ _ _ _ _ = Some r›)
  qed (simp add: None)
next
  case (Some t)
  with brun_imp_drun_diag[OF Some, THEN spec[where x = sh]] show ?thesis by simp
qed

text ‹The one pass of the simple driver: the tree decoded by ‹dec›, or the error
  of const‹pdiagnose›, from the same run.›

definition pdiag :: ‹('n, 't) ptabs ⇒ nat ⇒ ('t ⇒ nat) ⇒ 't list ⇒
    (('m, 'ch, 'n, 't) ast ⇒ 'x option) ⇒ ('t, 'ch, 'm) token_scheme list ⇒
    ('n, 't, 'ch, 'm) perr + 'x› where
  ‹pdiag P i0 f ts dec w =
     (let r = pdiag_run P i0 f w
      in case Option.bind (Option.bind r dstop_tree) dec of
           Some x ⇒ Inr x
         | None ⇒ Inl (dperr pstate snd fst (pexpect P f ts) (length w) r))›

lemma pdiag_Inr_iff:
  ‹pdiag P i0 f ts dec w = Inr x ⟷
     Option.bind (brun (pctl P) (pfinal P) fst (None, 1, 1) ([i0], map (tenc f) w, [])) dec = Some x›
  unfolding pdiag_def pdiag_run_def Let_def brun_drun_diag[where sh = ‹(([i0], map (tenc f) w), [])›]
  by (simp add: Let_def split: option.split)

subsection ‹The set-anchored drivers›

text ‹The run stops at a final configuration (‹ADone›) or where the step has no
  action (‹AStuck›, with the configuration after the last shift).›

datatype 's astop = ADone 's | AStuck 's 's

partial_function (option) arun ::
  ‹('s ⇒ ('a × 's) option) ⇒ ('a ⇒ bool) ⇒ ('s ⇒ bool) ⇒ 's ⇒ 's ⇒ 's astop option›
  where
  ‹arun stp sft fin sh st =
     (if fin st then Some (ADone st)
      else (case stp st of
        None ⇒ Some (AStuck st sh)
      | Some (a, st') ⇒ arun stp sft fin (if sft a then st' else sh) st'))›

lemmas arun_simps [code] = arun.simps

fun is_dshift :: ‹('n, 't) dact ⇒ bool› where
  ‹is_dshift DShift = True›
| ‹is_dshift (DReduce pr) = False›

fun is_sshift :: ‹('n, 't) sact ⇒ bool› where
  ‹is_sshift SShift = True›
| ‹is_sshift (SReduce r) = False›

definition dst_tree :: ‹'g × 'c × 'i × 'v × ('m, 'ch, 'n, 't) ast list ⇒ ('m, 'ch, 'n, 't) ast option› where
  ‹dst_tree st = (case st of (gc, cstk, istk, v, tstk) ⇒ sresult tstk)›

fun astop_tree :: ‹('g × 'c × 'i × 'v × ('m, 'ch, 'n, 't) ast list) astop ⇒
    ('m, 'ch, 'n, 't) ast option› where
  ‹astop_tree (ADone st) = dst_tree st›
| ‹astop_tree (AStuck st sh) = None›

text ‹A driver that runs ‹stp› until ‹fin› holds, given by its unfolding ‹eq›,
  returns the tree of every final configuration the run reaches.›

lemma arun_imp:
  assumes r: ‹arun stp sft fin sh st = Some r›
    and eq: ‹⋀st. F st = (if fin st then dst_tree st else Option.bind (map_option snd (stp st)) F)›
  shows ‹∀t. astop_tree r = Some t ⟶ F st = Some t›
proof -
  have ‹stp' = stp ⟶ fin' = fin ⟶ (∀t. astop_tree r = Some t ⟶ F st = Some t)›
    if ‹arun stp' sft fin' sh st = Some r› for stp' fin'
  proof (rule arun.raw_induct[OF _ that], goal_cases)
    case (1 f stp' sft fin' sh st r)
    show ?case
    proof (intro impI allI)
      fix t
      assume s: ‹stp' = stp› and fi: ‹fin' = fin› and t: ‹astop_tree r = Some t›
      show ‹F st = Some t›
      proof (cases ‹fin st›)
        case True
        with "1"(2) t s fi show ?thesis by (subst eq) auto
      next
        case False
        show ?thesis
        proof (cases ‹stp st›)
          case None
          with False "1"(2) t s fi show ?thesis by auto
        next
          case (Some p)
          then obtain a st' where p: ‹stp st = Some (a, st')› by (cases p) auto
          with False "1"(2) s fi have rec: ‹f stp' sft fin' (if sft a then st' else sh) st' = Some r›
            by simp
          from "1"(1)[OF rec] s fi t have ‹F st' = Some t› by simp
          with False p show ?thesis by (subst eq) simp
        qed
      qed
    qed
  qed
  with r show ?thesis by simp
qed

lemma arun_fin: ‹fin st ⟹ arun stp sft fin sh st = Some (ADone st)›
  by (subst arun.simps) simp

lemma arun_step:
  ‹¬ fin st ⟹ stp st = Some (a, st') ⟹
     arun stp sft fin sh st = arun stp sft fin (if sft a then st' else sh) st'›
  by (subst arun.simps) simp

text ‹The two drivers, each as a run of const‹arun› from any saved
  configuration.›

lemma dstep_c_act_c: ‹dstep_c G gt sts redtab dt st = map_option snd (dstep_act_c G gt sts redtab dt st)›
  unfolding dstep_c_def dstep_act_c_def
  by (auto simp: Let_def split: prod.splits option.splits dact.splits)

lemma drun_nh_c_eq:
  ‹drun_nh_c G Shn gt sts redtab dt st =
     (if gfinal G Shn (fst st) then dst_tree st
      else Option.bind (map_option snd (dstep_act_c G gt sts redtab dt st)) (drun_nh_c G Shn gt sts redtab dt))›
  by (subst drun_nh_c.simps) (auto simp: dst_tree_def sresult_def dstep_c_act_c split: prod.splits list.splits)

lemma drun_nh_c_imp_arun:
  assumes ‹drun_nh_c G Shn gt sts redtab dt st = Some t›
  shows ‹∀sh. Option.bind (arun (dstep_act_c G gt sts redtab dt) is_dshift (λs. gfinal G Shn (fst s)) sh st)
           astop_tree = Some t›
proof (rule drun_nh_c.raw_induct[OF _ assms], goal_cases)
  case (1 f G Shn gt sts redtab dt st t)
  show ?case
  proof (cases ‹gfinal G Shn (fst st)›)
    case True
    with "1"(2) show ?thesis
      by (cases st) (auto simp: arun_fin dst_tree_def sresult_def split: list.splits)
  next
    case False
    with "1"(2) obtain a st' where s: ‹dstep_act_c G gt sts redtab dt st = Some (a, st')›
        and rec: ‹f G Shn gt sts redtab dt st' = Some t›
      by (cases st) (auto simp: bind_eq_Some_conv dstep_c_act_c)
    show ?thesis
    proof
      fix sh
      from "1"(1)[OF rec, THEN spec[where x = ‹if is_dshift a then st' else sh›]] False s
      show ‹Option.bind (arun (dstep_act_c G gt sts redtab dt) is_dshift (λs. gfinal G Shn (fst s)) sh st)
          astop_tree = Some t›
        by (simp add: arun_step)
    qed
  qed
qed

lemma drun_nh_c_arun:
  ‹drun_nh_c G Shn gt sts redtab dt st =
     Option.bind (arun (dstep_act_c G gt sts redtab dt) is_dshift (λs. gfinal G Shn (fst s)) sh st)
       astop_tree›
proof (cases ‹drun_nh_c G Shn gt sts redtab dt st›)
  case None
  show ?thesis
  proof (cases ‹arun (dstep_act_c G gt sts redtab dt) is_dshift (λs. gfinal G Shn (fst s)) sh st›)
    case (Some r)
    show ?thesis
    proof (cases ‹astop_tree r›)
      case (Some t)
      from arun_imp[OF ‹arun _ _ _ _ _ = Some r› drun_nh_c_eq] Some None show ?thesis by simp
    qed (simp add: None ‹arun _ _ _ _ _ = Some r›)
  qed (simp add: None)
next
  case (Some t)
  with drun_nh_c_imp_arun[OF Some, THEN spec[where x = sh]] show ?thesis by simp
qed

lemma sdrun_eq:
  ‹sdrun T st =
     (if sgfinal T (fst st) then dst_tree st
      else Option.bind (map_option snd (sdstep_act T st)) (sdrun T))›
  by (subst sdrun.simps) (auto simp: dst_tree_def sresult_def sdstep_def split: prod.splits list.splits)

lemma sdrun_imp_arun:
  assumes ‹sdrun T st = Some t›
  shows ‹∀sh. Option.bind (arun (sdstep_act T) is_sshift (λs. sgfinal T (fst s)) sh st) astop_tree = Some t›
proof (rule sdrun.raw_induct[OF _ assms], goal_cases)
  case (1 f T st t)
  show ?case
  proof (cases ‹sgfinal T (fst st)›)
    case True
    with "1"(2) show ?thesis
      by (cases st) (auto simp: arun_fin dst_tree_def sresult_def split: list.splits)
  next
    case False
    with "1"(2) obtain a st' where s: ‹sdstep_act T st = Some (a, st')› and rec: ‹f T st' = Some t›
      by (cases st) (auto simp: bind_eq_Some_conv sdstep_def)
    show ?thesis
    proof
      fix sh
      from "1"(1)[OF rec, THEN spec[where x = ‹if is_sshift a then st' else sh›]] False s
      show ‹Option.bind (arun (sdstep_act T) is_sshift (λs. sgfinal T (fst s)) sh st) astop_tree = Some t›
        by (simp add: arun_step)
    qed
  qed
qed

lemma sdrun_arun:
  ‹sdrun T st = Option.bind (arun (sdstep_act T) is_sshift (λs. sgfinal T (fst s)) sh st) astop_tree›
proof (cases ‹sdrun T st›)
  case None
  show ?thesis
  proof (cases ‹arun (sdstep_act T) is_sshift (λs. sgfinal T (fst s)) sh st›)
    case (Some r)
    show ?thesis
    proof (cases ‹astop_tree r›)
      case (Some t)
      from arun_imp[OF ‹arun _ _ _ _ _ = Some r› sdrun_eq] Some None show ?thesis by simp
    qed (simp add: None ‹arun _ _ _ _ _ = Some r›)
  qed (simp add: None)next
  case (Some t)
  with sdrun_imp_arun[OF Some, THEN spec[where x = sh]] show ?thesis by simp
qed

text ‹The error at a stop of const‹arun›, by const‹ldperr› on the
  configurations of const‹lctl›, whose depth is that of the state stack, and the
  one pass of a set-anchored driver: ‹stp› is its step at the token type of the
  trials, ‹r› its run.›

definition lcfg_of :: ‹('m, 'ch, 'p, 'n, 't) ast_st ⇒ ('m, 'ch, 'p, 't) lcfg × ('m, 'ch, 'n, 't) ast list› where
  ‹lcfg_of st = (case st of (gc, cstk, istk, v, tstk) ⇒ (((gc, cstk, istk, v), length istk), tstk))›

fun astop_dstop :: ‹('m, 'ch, 'p, 'n, 't) ast_st astop ⇒
    (('m, 'ch, 'p, 't) lcfg, ('m, 'ch, 'n, 't) ast) dstop› where
  ‹astop_dstop (ADone st) = DDone (lcfg_of st)›
| ‹astop_dstop (AStuck st sh) = DStuck NoAction (lcfg_of st) (lcfg_of sh)›

definition adiag :: ‹(unit, unit, 'p, 'n, 't) astep ⇒ (('p, 't) agconfig ⇒ bool) ⇒ 't list ⇒
    (('m, 'ch, 'n, 't) ast ⇒ 'x option) ⇒ nat ⇒ ('m, 'ch, 'p, 'n, 't) ast_st astop option ⇒
    ('n, 't, 'ch, 'm) perr + 'x› where
  ‹adiag stp fin ts dec n r =
     (case Option.bind (Option.bind r astop_tree) dec of
        Some x ⇒ Inr x
      | None ⇒ Inl (ldperr stp fin ts n (map_option astop_dstop r)))›

lemma adiag_Inr_iff: ‹adiag stp fin ts dec n r = Inr x ⟷ Option.bind (Option.bind r astop_tree) dec = Some x›
  unfolding adiag_def by (simp split: option.split)

text ‹The dense driver const‹drun_nh_c› over the tables and the start frame of
  text‹dparse_via_tables_nh_c›, its trials on the same step.›

definition ldiag_c :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒ (nat × nat option) list ⇒
    ('n, 't) xitem list ⇒ ('n, 't) xitem list ⇒ nat ⇒ 't list ⇒
    (('m, 'ch, 'n, 't) ast ⇒ 'x option) ⇒ ('m, 'ch, 't) tword ⇒ ('n, 't, 'ch, 'm) perr + 'x› where
  ‹ldiag_c G Shn gt sts redtab dt xin xclos i0 ts dec w =
     (let st = (([xin], tcols w), [xclos], [i0], w, [])
      in adiag (dstep_act_c G gt sts redtab dt) (gfinal G Shn) ts dec (length w)
           (arun (dstep_act_c G gt sts redtab dt) is_dshift (λs. gfinal G Shn (fst s)) st st))›

lemma ldiag_c_Inr_iff:
  ‹ldiag_c G Shn gt sts redtab dt xin xclos i0 ts dec w = Inr x ⟷
     Option.bind (drun_nh_c G Shn gt sts redtab dt (([xin], tcols w), [xclos], [i0], w, [])) dec = Some x›
  unfolding ldiag_c_def Let_def adiag_Inr_iff
    drun_nh_c_arun[where sh = ‹(([xin], tcols w), [xclos], [i0], w, [])›] ..

text ‹The sparse driver const‹sdrun› over the bundle and the start frame of
  text‹dparse_via_tables_s›.›

definition sdiag :: ‹('n, 't) stab ⇒ ('n, 't) sitem list ⇒ ('n, 't) sitem list ⇒ nat ⇒ 't list ⇒
    (('m, 'ch, 'n, 't) ast ⇒ 'x option) ⇒ ('m, 'ch, 't) tword ⇒ ('n, 't, 'ch, 'm) perr + 'x› where
  ‹sdiag T kin kcl i0 ts dec w =
     (let st = (([kin], tcols w), [kcl], [i0], w, [])
      in adiag (sdstep_dact T) (sgfinal T) ts dec (length w)
           (arun (sdstep_act T) is_sshift (λs. sgfinal T (fst s)) st st))›

lemma sdiag_Inr_iff:
  ‹sdiag T kin kcl i0 ts dec w = Inr x ⟷
     Option.bind (sdrun T (([kin], tcols w), [kcl], [i0], w, [])) dec = Some x›
  unfolding sdiag_def Let_def adiag_Inr_iff
    sdrun_arun[where sh = ‹(([kin], tcols w), [kcl], [i0], w, [])›] ..

subsection ‹The vector driver›

text ‹The parser's code equation runs const‹vrun_un›. Its one pass keeps the
  configuration after the last shift and tells apart the three ways to stop: at
  a final configuration, where nothing is live, and at a conflict between live
  reductions. Only the last restarts, as the parser does, on the sparse driver:
  a rejected word is reported from the frames where the run stopped. The run has
  no loop check, like const‹vrun_un›, which only runs on grammars without a
  nullable cycle.›

datatype ('m, 'ch, 'n, 't) vstop =
    VConflict
  | VDone ‹('m, 'ch, 'n, 't) vst_n›
  | VStuck ‹('m, 'ch, 'n, 't) vst_n› ‹('m, 'ch, 'n, 't) vst_n›

definition vstep_a :: ‹('n, 't) vtab ⇒ ('m, 'ch, 'n, 't) vst_n ⇒
    (('n, 't) vact × ('m, 'ch, 'n, 't) vst_n) option option› where
  ‹vstep_a V st = (case st of (fs, w, v, tstk) ⇒ (case fs of [] ⇒ Some None | (j, av) # _ ⇒
     (case vchoose_n V (fs, w) (vcands_n V j av w) of None ⇒ None | Some None ⇒ Some None
      | Some (Some (act, fs', w')) ⇒
          (case tstep (vdec act) (v, tstk) of (v', tstk') ⇒ Some (Some (act, fs', w', v', tstk'))))))›

partial_function (option) vdrun ::
  ‹('n, 't) vtab ⇒ ('m, 'ch, 'n, 't) vst_n ⇒ ('m, 'ch, 'n, 't) vst_n ⇒
    ('m, 'ch, 'n, 't) vstop option›
  where
  ‹vdrun V sh st =
     (if vfinal_n V st then Some (VDone st)
      else (case vstep_a V st of
        None ⇒ Some VConflict
      | Some None ⇒ Some (VStuck st sh)
      | Some (Some (a, st')) ⇒ vdrun V (case a of VShift ⇒ st' | VReduce _ _ _ ⇒ sh) st'))›

lemmas vdrun_simps [code] = vdrun.simps

fun vtree :: ‹('m, 'ch, 'n, 't) vst_n ⇒ ('m, 'ch, 'n, 't) ast option› where
  ‹vtree (fs, w, v, tstk) = (case tstk of t # _ ⇒ Some t | [] ⇒ None)›

fun vres :: ‹('m, 'ch, 'n, 't) vstop ⇒ ('m, 'ch, 'n, 't) ast option option› where
  ‹vres VConflict = None›
| ‹vres (VDone st) = Some (vtree st)›
| ‹vres (VStuck st sh) = Some None›

lemma vstep_un_a: ‹vstep_un V st = map_option (map_option snd) (vstep_a V st)›
  by (auto simp: vstep_un_def vstep_a_def split: prod.split list.split option.split)

lemma vrun_un_imp_vdrun:
  assumes ‹vrun_un V st = Some r›
  shows ‹∀sh. Option.bind (vdrun V sh st) vres = Some r›
proof (rule vrun_un.raw_induct[OF _ assms], goal_cases)
  case (1 f V st r)
  obtain fs w v tstk where st: ‹st = (fs, w, v, tstk)› by (cases st)
  note body = "1"(2)[unfolded st prod.case, folded st, unfolded vstep_un_a]
  show ?case
  proof
    fix sh
    show ‹Option.bind (vdrun V sh st) vres = Some r›
    proof (cases ‹vfinal_n V st›)
      case True
      with body show ?thesis by (subst vdrun.simps) (simp add: st)
    next
      case False
      show ?thesis
      proof (cases ‹vstep_a V st›)
        case None
        with False body show ?thesis by simp
      next
        case (Some y)
        show ?thesis
        proof (cases y)
          case None
          with ‹vstep_a V st = Some y› False body show ?thesis by (subst vdrun.simps) simp
        next
          case (Some p)
          obtain a st' where p: ‹p = (a, st')› by (cases p)
          with ‹vstep_a V st = Some y› Some False body have ‹f V st' = Some r› by simp
          from "1"(1)[OF this, THEN spec[where x = ‹case a of VShift ⇒ st' | VReduce _ _ _ ⇒ sh›]]
            ‹vstep_a V st = Some y› Some p False show ?thesis
            by (subst vdrun.simps) simp
        qed
      qed
    qed
  qed
qed

lemma vdrun_imp_vrun_un:
  assumes ‹vdrun V sh st = Some s›
  shows ‹∀r. vres s = Some r ⟶ vrun_un V st = Some r›
proof (rule vdrun.raw_induct[OF _ assms], goal_cases)
  case (1 f V sh st s)
  obtain fs w v tstk where st: ‹st = (fs, w, v, tstk)› by (cases st)
  show ?case
  proof (intro allI impI)
    fix r
    assume r: ‹vres s = Some r›
    show ‹vrun_un V st = Some r›
    proof (cases ‹vfinal_n V st›)
      case True
      with "1"(2) r show ?thesis by (subst vrun_un.simps) (auto simp: st)
    next
      case False
      show ?thesis
      proof (cases ‹vstep_a V st›)
        case None
        with False "1"(2) r show ?thesis by auto
      next
        case (Some y)
        show ?thesis
        proof (cases y)
          case None
          with ‹vstep_a V st = Some y› False "1"(2) r show ?thesis
            by (subst vrun_un.simps) (auto simp: st vstep_un_a)
        next
          case (Some p)
          obtain a st' where p: ‹p = (a, st')› by (cases p)
          with ‹vstep_a V st = Some y› Some False "1"(2)
          have ‹f V (case a of VShift ⇒ st' | VReduce _ _ _ ⇒ sh) st' = Some s› by simp
          from "1"(1)[OF this] r have ‹vrun_un V st' = Some r› by blast
          moreover from ‹vstep_a V st = Some y› Some p have ‹vstep_un V st = Some (Some st')›
            by (simp add: vstep_un_a)
          ultimately show ?thesis using False
            by (subst vrun_un.simps) (simp split: prod.split)
        qed
      qed
    qed
  qed
qed

lemma vrun_un_vdrun: ‹vrun_un V st = Option.bind (vdrun V sh st) vres›
proof (cases ‹vrun_un V st›)
  case None
  show ?thesis
  proof (cases ‹Option.bind (vdrun V sh st) vres›)
    case (Some r)
    then obtain s where ‹vdrun V sh st = Some s› ‹vres s = Some r›
      by (auto simp: bind_eq_Some_conv)
    with vdrun_imp_vrun_un None show ?thesis by fastforce
  qed (simp add: None)
next
  case (Some r)
  with vrun_un_imp_vdrun[OF Some, THEN spec[where x = sh]] show ?thesis by simp
qed

text ‹A trial on the frames after the last shift, as in const‹dtrial›; where two
  reductions are live it takes the first, so the expected terminals are read
  off the run at hand whichever conflict a candidate would meet. It needs
  neither tokens nor trees.›

type_synonym vcfg = ‹vframes × (nat × nat) list›

fun vpick_n :: ‹('n, 't) vtab ⇒ vcfg ⇒ ('n, 't) vact list ⇒ (('n, 't) vact × vcfg) option› where
  ‹vpick_n V c [] = None›
| ‹vpick_n V c (a # acts) = (case vmstep_n V c a of Some r ⇒ Some (a, r) | None ⇒ vpick_n V c acts)›

definition vfin_c :: ‹('n, 't) vtab ⇒ vcfg ⇒ bool› where
  ‹vfin_c V c = vfinal_n V
     (fst c, snd c, [] :: (unit, unit, 't) tword, [] :: (unit, unit, 'n, 't) ast list)›

partial_function (option) vtrial :: ‹('n, 't) vtab ⇒ vcfg ⇒ bool option› where
  ‹vtrial V c =
     (if vfin_c V c then Some True
      else (case c of (fs, w) ⇒ (case fs of [] ⇒ Some False | (j, av) # _ ⇒
        (case vpick_n V c (vcands_n V j av w) of
          None ⇒ Some False
        | Some (a, c') ⇒ (case a of VShift ⇒ Some True | VReduce _ _ _ ⇒ vtrial V c')))))›

lemmas vtrial_simps [code] = vtrial.simps

definition vtry :: ‹('n, 't) vtab ⇒ vcfg ⇒ ('t × nat) option ⇒ bool› where
  ‹vtry V c x = (vtrial V (fst c, case x of None ⇒ [] | Some (t, k) ⇒ [(vnum V t, k)]) = Some True)›

text ‹The columns to try are those of const‹lreps›, from the anchor sets of the
  frames.›

definition vcolumns :: ‹('n, 't) vtab ⇒ 't list ⇒ vcfg ⇒ ('t × colset) list × bool› where
  ‹vcolumns V ts c = columns_at (vtry V c)
     (col_reps (concat (map (λ(j, av). concat (map irep_ends av)) (fst c)))) ts›

definition vtop :: ‹vframes ⇒ nat› where
  ‹vtop fs = (case fs of [] ⇒ 0 | (j, _) # _ ⇒ j)›

text ‹The error at a stop, as const‹ldperr› gives it.›

definition vperr :: ‹('n, 't) vtab ⇒ 't list ⇒ nat ⇒ ('m, 'ch, 'n, 't) vst_n ⇒
    ('m, 'ch, 'n, 't) vst_n ⇒ ('n, 't, 'ch, 'm) perr› where
  ‹vperr V ts n st sh = (case (st, sh) of ((fs, _, v, tstk), (fs', w', _, tstk')) ⇒
     mk_perr NoAction n v (vtop fs) (vtop fs') (vcolumns V ts (fs', w')) tstk' tstk)›

text ‹The one pass over the parser's code equation
  text‹dparse_via_tables_vun›.›

definition vdiag :: ‹('n, 't) vtab ⇒ ('n, 't) stab ⇒ ('n, 't) sitem list ⇒ ('n, 't) sitem list ⇒
    nat ⇒ 't list ⇒ (('m, 'ch, 'n, 't) ast ⇒ 'x option) ⇒ ('m, 'ch, 't) tword ⇒
    ('n, 't, 'ch, 'm) perr + 'x› where
  ‹vdiag V T kin kcl i0 ts dec w =
     (let st = ([v_av0 V], vtcols V w, w, [])
      in (case vdrun V st st of
            Some (VDone s) ⇒ (case Option.bind (vtree s) dec of
                Some x ⇒ Inr x
              | None ⇒ Inl (vperr V ts (length w) s s))
          | Some (VStuck s sh) ⇒ Inl (vperr V ts (length w) s sh)
          | _ ⇒ sdiag T kin kcl i0 ts dec w))›

lemma vdiag_Inr_iff:
  ‹vdiag V T kin kcl i0 ts dec w = Inr x ⟷
     Option.bind (case vrun_un V ([v_av0 V], vtcols V w, w, []) of
         Some r ⇒ r | None ⇒ sdrun T (([kin], tcols w), [kcl], [i0], w, [])) dec = Some x›
  unfolding vdiag_def Let_def
    vrun_un_vdrun[where sh = ‹([v_av0 V], vtcols V w, w, [])›]
  by (auto simp: sdiag_Inr_iff split: option.split vstop.split)

text ‹The parser's code equation runs const‹vrun_k›, which is only known sound
  for const‹vrun_un›, with ‹f› numbering the tokens. So an accepted word goes
  through that equation itself, and a rejected one through const‹vdiag› for its
  error, a second pass.›

definition vkdiag :: ‹('n, 't) vtab ⇒ ('n, 't) vktab ⇒ ('n, 't) stab ⇒ ('n, 't) sitem list ⇒
    ('n, 't) sitem list ⇒ nat ⇒ ('t ⇒ nat) ⇒ 't list ⇒ (('m, 'ch, 'n, 't) ast ⇒ 'x option) ⇒
    ('m, 'ch, 't) tword ⇒ ('n, 't, 'ch, 'm) perr + 'x› where
  ‹vkdiag V K T kin kcl i0 f ts dec w =
     (case Option.bind (case vrun_k K [v_av0 V] (vtnum f w) w [] of
         Some r ⇒ r | None ⇒ sdrun T (([kin], tcols w), [kcl], [i0], w, [])) dec of
        Some x ⇒ Inr x
      | None ⇒ Inl (projl (vdiag V T kin kcl i0 ts (λ_. None :: unit option) w)))›

lemma vkdiag_Inr_iff:
  ‹vkdiag V K T kin kcl i0 f ts dec w = Inr x ⟷
     Option.bind (case vrun_k K [v_av0 V] (vtnum f w) w [] of
         Some r ⇒ r | None ⇒ sdrun T (([kin], tcols w), [kcl], [i0], w, [])) dec = Some x›
  unfolding vkdiag_def by (simp split: option.split)

text ‹The same with the tokens numbered by ‹f›, the numbering of the parser's code
  equation, where const‹vnum› searches the terminals of the tables for every token of
  the word and every trial. The backend proves prop‹vnum V = f› and rewrites the
  code equation of ‹p_diag› with ‹vkdiag_f›; nothing else is stated about them.›

definition vtry_f :: ‹('n, 't) vtab ⇒ ('t ⇒ nat) ⇒ vcfg ⇒ ('t × nat) option ⇒ bool› where
  ‹vtry_f V f c x = (vtrial V (fst c, case x of None ⇒ [] | Some (t, k) ⇒ [(f t, k)]) = Some True)›

definition vcolumns_f :: ‹('n, 't) vtab ⇒ ('t ⇒ nat) ⇒ 't list ⇒ vcfg ⇒ ('t × colset) list × bool› where
  ‹vcolumns_f V f ts c = columns_at (vtry_f V f c)
     (col_reps (concat (map (λ(j, av). concat (map irep_ends av)) (fst c)))) ts›

definition vperr_f :: ‹('n, 't) vtab ⇒ ('t ⇒ nat) ⇒ 't list ⇒ nat ⇒ ('m, 'ch, 'n, 't) vst_n ⇒
    ('m, 'ch, 'n, 't) vst_n ⇒ ('n, 't, 'ch, 'm) perr› where
  ‹vperr_f V f ts n st sh = (case (st, sh) of ((fs, _, v, tstk), (fs', w', _, tstk')) ⇒
     mk_perr NoAction n v (vtop fs) (vtop fs') (vcolumns_f V f ts (fs', w')) tstk' tstk)›

definition vdiag_f :: ‹('n, 't) vtab ⇒ ('t ⇒ nat) ⇒ ('n, 't) stab ⇒ ('n, 't) sitem list ⇒
    ('n, 't) sitem list ⇒ nat ⇒ 't list ⇒ (('m, 'ch, 'n, 't) ast ⇒ 'x option) ⇒ ('m, 'ch, 't) tword ⇒
    ('n, 't, 'ch, 'm) perr + 'x› where
  ‹vdiag_f V f T kin kcl i0 ts dec w =
     (let st = ([v_av0 V], vtnum f w, w, [])
      in (case vdrun V st st of
            Some (VDone s) ⇒ (case Option.bind (vtree s) dec of
                Some x ⇒ Inr x
              | None ⇒ Inl (vperr_f V f ts (length w) s s))
          | Some (VStuck s sh) ⇒ Inl (vperr_f V f ts (length w) s sh)
          | _ ⇒ sdiag T kin kcl i0 ts dec w))›

definition vkdiag_f :: ‹('n, 't) vtab ⇒ ('n, 't) vktab ⇒ ('n, 't) stab ⇒ ('n, 't) sitem list ⇒
    ('n, 't) sitem list ⇒ nat ⇒ ('t ⇒ nat) ⇒ 't list ⇒ (('m, 'ch, 'n, 't) ast ⇒ 'x option) ⇒
    ('m, 'ch, 't) tword ⇒ ('n, 't, 'ch, 'm) perr + 'x› where
  ‹vkdiag_f V K T kin kcl i0 f ts dec w =
     (case Option.bind (case vrun_k K [v_av0 V] (vtnum f w) w [] of
         Some r ⇒ r | None ⇒ sdrun T (([kin], tcols w), [kcl], [i0], w, [])) dec of
        Some x ⇒ Inr x
      | None ⇒ Inl (projl (vdiag_f V f T kin kcl i0 ts (λ_. None :: unit option) w)))›

lemma vtry_f_vnum: ‹vtry_f V (vnum V) = vtry V›
  by (intro ext) (simp add: vtry_f_def vtry_def)

lemma vcolumns_f_vnum: ‹vcolumns_f V (vnum V) = vcolumns V›
  by (intro ext) (simp add: vcolumns_f_def vcolumns_def vtry_f_vnum)

lemma vperr_f_vnum: ‹vperr_f V (vnum V) = vperr V›
  by (intro ext) (simp add: vperr_f_def vperr_def vcolumns_f_vnum)

lemma vdiag_f_vnum: ‹vdiag_f V (vnum V) = vdiag V›
  unfolding vdiag_f_def vdiag_def vperr_f_vnum vtcols_vtnum ..

lemma vkdiag_f_eq: ‹vnum V = f ⟹ vkdiag V K T kin kcl i0 f = vkdiag_f V K T kin kcl i0 f›
  by (hypsubst, unfold vkdiag_f_def vkdiag_def vdiag_f_vnum) (rule refl)

section ‹Messages›

text ‹An error as a message a person can act on, after cite‹‹Fig.~7› in "pottier2016-lr1-reachability"›:
  a position, a primary text and notes, as a record (‹pmsg›) that a client may
  render its own way, and a default rendering into one string. The text of the
  tokens is in the type ‹'ch› of the token record, so the caller supplies a
  function ‹'ch ⇒ string›; the parser command does so for typ‹char›. Line
  and column are printed as the lexer put them into the spans.›

subsection ‹What the parser was reading›

text ‹The terminals a nonterminal may start with: the terminals among the left
  corners reachable from it, where a left corner of a production is any symbol of
  its right-hand side with only nullable symbols before it. The search visits
  each symbol once; its fuel, the number of symbols of the grammar, only makes
  it a total function.›

definition lcorners :: ‹'n list ⇒ ('n, 't) rhs ⇒ ('n, 't) sym list› where
  ‹lcorners nul rhs = (let xs = map fst rhs in take (Suc (length (takeWhile (nsym nul) xs))) xs)›

fun lreach :: ‹('n, 't) is_cfg ⇒ 'n list ⇒ nat ⇒ ('n, 't) sym list ⇒ ('n, 't) sym list ⇒
    ('n, 't) sym list› where
  ‹lreach G nul 0 todo seen = seen›
| ‹lreach G nul (Suc f) [] seen = seen›
| ‹lreach G nul (Suc f) (x # todo) seen =
     (if x ∈ set seen then lreach G nul (Suc f) todo seen
      else lreach G nul f
        ((case x of Nt A ⇒ concat (map (λ(B, rhs). if B = A then lcorners nul rhs else []) (iprods G))
                  | Tm _ ⇒ []) @ todo) (x # seen))›

text ‹The patterns on the fuel and on ‹todo› together do not survive the
  preprocessing of ‹Code_Target_Numeral›, where ‹0› is no constructor, as for
  ‹rlevel› in 🗏‹LR_Recover.thy›.›

lemma lreach_code [code]:
  ‹lreach G nul f todo seen = (if f = 0 then seen else case todo of
     [] ⇒ seen
   | x # todo' ⇒
       if x ∈ set seen then lreach G nul f todo' seen
       else lreach G nul (f - 1)
         ((case x of Nt A ⇒ concat (map (λ(B, rhs). if B = A then lcorners nul rhs else []) (iprods G))
                   | Tm _ ⇒ []) @ todo') (x # seen))›
  by (cases f; cases todo) simp_all

definition nt_first :: ‹('n, 't) is_cfg ⇒ 'n list ⇒ 'n ⇒ 't list› where
  ‹nt_first G nul X =
     List.map_filter (λx. case x of Tm a ⇒ Some a | Nt _ ⇒ None)
       (lreach G nul (Suc (length (concat (map (λ(A, rhs). Nt A # map fst rhs) (iprods G)))))
          [Nt X] [])›

text ‹The nonterminals right after the dot in the kernel items of a state: what
  the parser was about to read there.›

definition kernel_nts :: ‹('n, 't) citem list list ⇒ nat ⇒ 'n list› where
  ‹kernel_nts sts k =
     (if k < length sts
      then remdups (List.map_filter (λ((A, rhs), m).
             if m < length rhs then (case fst (rhs ! m) of Nt X ⇒ Some X | Tm _ ⇒ None) else None)
             (sts ! k))
      else [])›

text ‹A heuristic, after cite‹‹Sect.~4› in "pottier2016-lr1-reachability"› (``an expression is expected''
  says more than the tokens that may start one): the expected terminals are
  summarised by a nonterminal ‹X› when the kernel of the state after the last
  shift has an item with the dot before ‹X› and every terminal that may start
  ‹X› is expected. The result: the nonterminals, and the expected terminals none
  of them covers.›

definition nt_summary :: ‹('n, 't) is_cfg ⇒ 'n list ⇒ 't list ⇒ 'n list × 't list› where
  ‹nt_summary G xs ex =
     (let nul = nullables G;
          fs = map (λX. (X, nt_first G nul X)) xs;
          cov = filter (λ(X, F). F ≠ [] ∧ set F ⊆ set ex) fs
      in (map fst cov, filter (λt. ¬ list_ex (λ(X, F). t ∈ set F) cov) ex))›

text ‹The summary of the kernel says nothing after a complete item, which is where the
  long lists are: inside a block, after an expression, anything that continues it is
  expected. There the classes come from what the grammar lets follow the symbol on top
  of the stack. That symbol may be the result of reductions the offending token
  triggered, and a reduced symbol ends with what it was reduced from, so the search takes
  unit productions both ways, from the symbol and from each left-hand side it ends. What
  may follow one of those symbols in a right-hand side is a candidate. This reads the
  grammar, not the stack below the top, so a candidate is only a name: it counts when all
  it may start with is expected, and when it covers at least two terminals still listed.
  The largest goes first.›

definition sreach :: ‹('x ⇒ 'x list) ⇒ nat ⇒ 'x list ⇒ 'x list› where
  ‹sreach nx n xs = rev (snd (fold (λ_ (todo, seen). case todo of
       [] ⇒ ([], seen)
     | x # t ⇒ if x ∈ set seen then (t, seen) else (t @ nx x, x # seen)) [0..<n] (xs, [])))›

definition rcorners :: ‹'n list ⇒ ('n, 't) rhs ⇒ ('n, 't) sym list› where
  ‹rcorners nul rhs = (let xs = rev (map fst rhs) in take (Suc (length (takeWhile (nsym nul) xs))) xs)›

definition follow_nts :: ‹('n, 't) is_cfg ⇒ 'n list ⇒ ('n, 't) sym ⇒ 'n list› where
  ‹follow_nts G nul y =
     (let ps = iprods G;
          n = Suc (length (concat (map (λ(A, rhs). Nt A # map fst rhs) ps)));
          ends = (λx. concat (map (λ(A, rhs). if x ∈ set (rcorners nul rhs) then [(Nt A, rhs)] else []) ps));
          up = (λx. map fst (filter (λ(A, rhs). list_all (λz. z = x ∨ nsym nul z) (map fst rhs)) (ends x)));
          down = (λx. case x of
              Tm _ ⇒ []
            | Nt B ⇒ concat (map (λ(A, rhs).
                if A = B then (case filter (λz. ¬ nsym nul z) (map fst rhs) of [z] ⇒ [z] | _ ⇒ [])
                else []) ps));
          ys = sreach (λx. up x @ down x) n (y # map fst (ends y));
          after = (λr. concat (map (λi. case drop i r of
              [] ⇒ []
            | (Z, _) # rest ⇒ if Z ∈ set ys then
                List.map_filter (λx. case x of Nt X ⇒ Some X | Tm _ ⇒ None) (lcorners nul rest)
              else []) [0..<length r]))
      in remdups (concat (map (λ(A, rhs). after rhs) ps)))›

definition class_summary :: ‹('n, 't) is_cfg ⇒ 'n list ⇒ 't list ⇒ 't list ⇒ 'n list × 't list› where
  ‹class_summary G xs ex rest0 =
     (let nul = nullables G;
          cs = filter (λ(X, F). set F ⊆ set ex) (map (λX. (X, remdups (nt_first G nul X))) xs)
      in fold (λ(X, F) (ns, rest).
           if 2 ≤ length (filter (λt. t ∈ set F) rest)
           then (ns @ [X], filter (λt. t ∉ set F) rest) else (ns, rest))
         (rev (sort_key (λ(X, F). length F) (rev cs))) ([], rest0))›

subsection ‹Unclosed brackets›

text ‹The brackets of a grammar: ‹(u, c)› when ‹c› ends a right-hand side with
  ‹u› before it, and every right-hand side has as many of the one as of the other. So
  ‹if› and ‹then› are no pair, as no production ends in ‹then›, and neither are a
  separator and a closer, as the closer occurs without the separator.›

definition brackets :: ‹('n, 't) is_cfg ⇒ ('t × 't) list› where
  ‹brackets G =
     (let rs = map (map fst ∘ snd) (iprods G);
          cnt = (λx r. length (filter (λy. y = x) r));
          tms = List.map_filter (λx. case x of Tm t ⇒ Some t | Nt _ ⇒ None)
      in remdups (concat (map (λr. if r = [] then [] else
           concat (map (λc. concat (map (λu.
               if u ≠ c ∧ list_all (λq. cnt (Tm u) q = cnt (Tm c) q) rs then [(u, c)] else [])
             (tms (butlast r)))) (tms [last r]))) rs)))›

text ‹The innermost bracket still open: the topmost opening bracket on the stack, a
  closed one being reduced away, with its token and its closer. The closer must be
  expected, or the bracket is not what is wrong here.›

definition open_bracket :: ‹('n, 't) is_cfg ⇒ ('n, 't, 'ch, 'm) perr ⇒ ('t × 'ch span × 't) option› where
  ‹open_bracket G e =
     (let bs = brackets G
      in case find (λ(X, ss). case X of Tm t ⇒ ss ≠ [] ∧ map_of bs t ≠ None | Nt _ ⇒ False) (pe_stack e) of
           Some (Tm t, s # _) ⇒ (case map_of bs t of
             Some c ⇒ if c ∈ set (pe_expected e) then Some (t, s, c) else None
           | None ⇒ None)
         | _ ⇒ None)›

text ‹Is that bracket the error? A repair settles it: it must start by inserting the
  closer. Without a repair there is the end of the input, where it is the error, and a
  token out of place on a later line at or left of the bracket's column, which has left
  the bracket's text. A token with no action inside the bracket says nothing by itself: a
  stray comma also leaves the closer expected.›

definition unclosed :: ‹('n, 't) is_cfg ⇒ ('n, 't, 'ch, 'm) perr ⇒ ('t × 'ch span) option› where
  ‹unclosed G e = (case open_bracket G e of
     None ⇒ None
   | Some (t, s, c) ⇒
       if (case filter (λr. r ≠ RKeep) (pe_repair e) of
             RIns d _ # _ ⇒ d = c
           | _ # _ ⇒ False
           | [] ⇒ (case pe_tok e of
               None ⇒ True
             | Some x ⇒ s_line s < s_line (span x) ∧ s_col (span x) ≤ s_col s ∧
                 (case pe_kind e of Offside _ ⇒ True | Misaligned _ ⇒ True | _ ⇒ False)))
       then Some (t, s) else None)›

subsection ‹Text›

fun nat_str :: ‹nat ⇒ string› where
  ‹nat_str n = (if n < 10 then [char_of (48 + n)] else nat_str (n div 10) @ [char_of (48 + n mod 10)])›

definition join_or :: ‹string list ⇒ string› where
  ‹join_or xs = (case rev xs of
       [] ⇒ []
     | [x] ⇒ x
     | x # ys ⇒ concat (map (λy. y @ '', '') (butlast (rev ys))) @ last (rev ys) @ '' or '' @ x)›

definition squote :: ‹string ⇒ string› where
  ‹squote s = CHR 0x27 # s @ [CHR 0x27]›

text ‹The article of a nonterminal's display name; none before a quoted terminal, which
  a generated list over a group starting with a terminal shows as.›

definition article :: ‹string ⇒ string› where
  ‹article s = (case s of c # _ ⇒ if c = CHR 0x27 then s
                                  else if c ∈ set ''aeiouAEIOU'' then ''an '' @ s else ''a '' @ s
                        | [] ⇒ s)›

text ‹The text of a run of tokens, with their spans: tokens on one line are
  separated as in the source, tokens on different lines by one space; a long
  text keeps its start and its end. Tokens without text (over typ‹unit›)
  give none.›

definition span_text :: ‹('ch ⇒ string) ⇒ 'ch span list ⇒ string› where
  ‹span_text chs ss = (case ss of
       [] ⇒ []
     | s # rest ⇒
         let txt = (λs. concat (map chs (s_txt s)));
             (r, _) = fold (λs (acc, p).
               (acc @ (if s_line s = s_line p then replicate (s_col s - (s_col p + s_len p)) (CHR '' '')
                       else '' '') @ txt s, s)) rest (txt s, s)
         in if list_all (λs. txt s = []) ss then []
            else if length r ≤ 60 then r else take 28 r @ '' ... '' @ drop (length r - 28) r)›

definition col_text :: ‹colset ⇒ string› where
  ‹col_text cs =
     (case cs of [(a, Some b)] ⇒ if a = b then ''column '' else ''columns ''
        | [(a, None)] ⇒ ''column '' | _ ⇒ ''columns '') @
     join_or (map (λ(a, b). case b of
         None ⇒ nat_str a @ '' or further''
       | Some b ⇒ if a = b then nat_str a else nat_str a @ ''..'' @ nat_str b) cs)›

subsection ‹The message›

text ‹A message: where (line, column, offset and length of the offending
  token; at the end of the input the position right after the last token, with
  length ‹0›), the primary text, and notes.›

record pmsg =
  pm_line :: nat
  pm_col :: nat
  pm_off :: nat
  pm_len :: nat
  pm_text :: string
  pm_notes :: ‹string list›

text ‹The key of a hand-written message cite‹"jeffery2003-lr-error-messages"› cite‹‹Sect.~5› in "pottier2016-lr1-reachability"›: the state where
  the error is detected, that state with the offending terminal (‹None› at the end of
  the input), or the state after the last shift, before the reductions the
  offending token triggered. The first is the default, as in Pottier: words that
  differ in their spurious reductions reach different keys, each its own sentence. Keys are
  state numbers of one build, but they are computed from the sentences at each
  elaboration, so a grammar edit that renumbers states is harmless; only the
  meaning of a message can go stale cite‹‹Sect.~6› in "pottier2016-lr1-reachability"›.›

datatype 't pkey = PState nat | PToken nat ‹'t option› | PShift nat

text ‹What a message needs beyond the error: the grammar, the states of the
  parser (for their kernels), the spelling of each terminal, the display name of
  a nonterminal, up to how many expected terminals are listed before they
  are summarised by nonterminals, and the hand-written messages.›

record ('n, 't) pinfo =
  pi_G :: ‹('n, 't) is_cfg›
  pi_states :: ‹('n, 't) citem list list›
  pi_spell :: ‹('t × string) list›
  pi_nt :: ‹'n ⇒ string›
  pi_k :: nat
  pi_msgs :: ‹('t pkey × string) list›

definition tspell :: ‹('n, 't) pinfo ⇒ 't ⇒ string› where
  ‹tspell I t = (case map_of (pi_spell I) t of Some s ⇒ s | None ⇒ ''?'')›

text ‹A token: its text, or the spelling of its terminal when it has none.›

definition tok_text :: ‹('n, 't) pinfo ⇒ ('ch ⇒ string) ⇒ ('t, 'ch, 'm) token_scheme ⇒ string› where
  ‹tok_text I chs x = (case concat (map chs (s_txt (span x))) of [] ⇒ tspell I (tok x) | s ⇒ s)›

definition sym_text :: ‹('n, 't) pinfo ⇒ ('n, 't) sym ⇒ string› where
  ‹sym_text I X = (case X of Nt A ⇒ pi_nt I A | Tm t ⇒ squote (tspell I t))›

text ‹The span of the last token read: the last token of the topmost entry of
  the stack that has one.›

definition last_span :: ‹(('n, 't) sym × 'ch span list) list ⇒ 'ch span option› where
  ‹last_span stk = (case filter (λ(X, ss). ss ≠ []) stk of [] ⇒ None | (X, ss) # _ ⇒ Some (last ss))›

text ‹The expected things: on a layout grammar, when there is an offending token,
  the terminals accepted at its column; then, when more than const‹pi_k›
  terminals are expected, the nonterminal summary, and the classes if the list is still
  too long; and the end of the input. Two entries that show alike (a nonterminal and a
  generated list of it) are listed once.›

definition expected_text :: ‹('n, 't) pinfo ⇒ ('n, 't, 'ch, 'm) perr ⇒ string list› where
  ‹expected_text I e =
     (let ex = (case (pe_tok e, pe_columns e) of
                  (Some x, _ # _) ⇒ map fst (filter (λ(t, cs). col_in (s_col (span x)) cs) (pe_columns e))
                | _ ⇒ pe_expected e);
          (ns, ts) = (if length ex ≤ pi_k I then ([], ex)
                      else nt_summary (pi_G I) (kernel_nts (pi_states I) (pe_shift_state e)) ex);
          (ms, us) = (if pi_k I < length ns + length ts
                      then (case pe_stack e of
                          [] ⇒ ([], ts)
                        | (Y, _) # _ ⇒ class_summary (pi_G I)
                            (follow_nts (pi_G I) (nullables (pi_G I)) Y) ex ts)
                      else ([], ts))
      in remdups (map (λX. article (pi_nt I X)) (ns @ ms) @ map (λt. squote (tspell I t)) us) @
         (if pe_expect_end e then [''end of input''] else []))›

text ‹What was recognised up to here: the topmost entry of the stack if it is a
  nonterminal, otherwise the text of the topmost three entries. A generated list over a
  group shown as its first terminal is taken by its text as well.›

definition upto_text :: ‹('n, 't) pinfo ⇒ ('ch ⇒ string) ⇒ ('n, 't, 'ch, 'm) perr ⇒ string list› where
  ‹upto_text I chs e =
     (let txt = (case span_text chs (concat (rev (map snd (take 3 (pe_stack e))))) of
                   [] ⇒ []
                 | s ⇒ [''up to here: '' @ squote s])
      in case pe_stack e of
       [] ⇒ []
     | (Nt A, ss) # _ ⇒
         if take 1 (pi_nt I A) = [CHR 0x27] then txt
         else if ss = [] then [] else
           [''up to here: '' @ article (pi_nt I A) @ '' was recognised'' @
            (case span_text chs ss of [] ⇒ [] | t ⇒ '': '' @ squote t)]
     | _ ⇒ txt)›

text ‹The template of the error, the most specific key first.›

definition phand :: ‹('n, 't) pinfo ⇒ ('n, 't, 'ch, 'm) perr ⇒ string option› where
  ‹phand I e =
     (let find = map_of (pi_msgs I)
      in case find (PToken (pe_state e) (map_option tok (pe_tok e))) of
           Some s ⇒ Some s
         | None ⇒ (case find (PState (pe_state e)) of
             Some s ⇒ Some s
           | None ⇒ find (PShift (pe_shift_state e))))›

text ‹The text of a stack entry, topmost first: of its tokens, or its symbol when
  it has none. Past the bottom of the stack it is empty.›

definition stack_text :: ‹('n, 't) pinfo ⇒ ('ch ⇒ string) ⇒ ('n, 't, 'ch, 'm) perr ⇒ nat ⇒ string› where
  ‹stack_text I chs e i = (case drop i (pe_stack e) of
       [] ⇒ []
     | (X, ss) # _ ⇒ (case span_text chs ss of [] ⇒ sym_text I X | t ⇒ t))›

text ‹The repair the recovery chose, for its note.›

fun rop_text :: ‹('n, 't) pinfo ⇒ 't rop ⇒ string list› where
  ‹rop_text I (RIns t k) = [''insert '' @ squote (tspell I t)]›
| ‹rop_text I (RDel t) = [''delete '' @ squote (tspell I t)]›
| ‹rop_text I RKeep = []›

definition repair_text :: ‹('n, 't) pinfo ⇒ ('n, 't, 'ch, 'm) perr ⇒ string list› where
  ‹repair_text I e = (case concat (map (rop_text I) (pe_repair e)) of
     [] ⇒ []
   | r # rs ⇒ [''repaired by: '' @ r @ concat (map (λs. '', '' @ s) rs)])›

text ‹A template with its holes ‹$0› to ‹$9› filled: a hole is one digit, and
  a ‹$› without a digit stands for itself.›

fun fill_holes :: ‹(nat ⇒ string) ⇒ string ⇒ string› where
  ‹fill_holes f (c # d # s) =
     (if c = CHR ''$'' ∧ 48 ≤ (of_char d :: nat) ∧ (of_char d :: nat) ≤ 57
      then f (of_char d - 48) @ fill_holes f s
      else c # fill_holes f (d # s))›
| ‹fill_holes f s = s›

definition perr_message :: ‹('n, 't) pinfo ⇒ ('ch ⇒ string) ⇒ ('n, 't, 'ch, 'm) perr ⇒ pmsg› where
  ‹perr_message I chs e =
     (let after = (case last_span (pe_stack e) of
                     None ⇒ []
                   | Some s ⇒ (case concat (map chs (s_txt s)) of [] ⇒ [] | t ⇒ '' (after '' @ squote t @ '')''));
          (l, c, off, n, what) = (case pe_tok e of
             Some x ⇒ (s_line (span x), s_col (span x), s_off (span x), s_len (span x), squote (tok_text I chs x))
           | None ⇒ (case last_span (pe_stack e) of
               None ⇒ (0, 0, 0, 0, ''end of input'')
             | Some s ⇒ (s_line s, s_col s + s_len s, s_off s + s_len s, 0, ''end of input'')));
          anchor = (λv. case pe_anchor e of
             None ⇒ []
           | Some a ⇒ '' ('' @ v @ '' '' @ squote (tok_text I chs a) @ '' at '' @
                        nat_str (s_line (span a)) @ '':'' @ nat_str (s_col (span a)) @ '')'');
          generic = (case pe_kind e of
             Misaligned cs ⇒ what @ '' at column '' @ nat_str c @ '' must be at '' @ col_text cs @
               anchor ''aligned with''
           | Offside cs ⇒ what @ '' at column '' @ nat_str c @ '' must be at '' @ col_text cs @
               anchor ''indented from''
           | ReduceCycle ⇒ ''the parser loops on a cycle of reductions at '' @ what @ after
           | NoAction ⇒ ''syntax error at '' @ what @ after);
          (text, demoted) = (case phand I e of
             Some t ⇒ (fill_holes (stack_text I chs e) t, [])
           | None ⇒ (case unclosed (pi_G I) e of
               None ⇒ (generic, [])
             | Some (t, s) ⇒
                 (squote (tspell I t) @ '' at '' @ nat_str (s_line s) @ '':'' @ nat_str (s_col s) @
                  '' is not closed'', [generic])));
          ex = expected_text I e
      in ⦇pm_line = l, pm_col = c, pm_off = off, pm_len = n, pm_text = text,
          pm_notes = demoted @ (if ex = [] then [] else [''expected: '' @ join_or ex]) @
            upto_text I chs e @ repair_text I e⦈)›

text ‹What the command reads from a sentence of an text‹errors› block: the
  state, the offending terminal, the state after the last shift, the index of the
  offending token and the depth of the stack; ‹None› if the word is accepted.›

fun diag_probe :: ‹('n, 't, 'ch, 'm) perr + 'x ⇒ (nat × 't option × nat × nat × nat) option› where
  ‹diag_probe (Inl e) = Some (pe_state e, map_option tok (pe_tok e), pe_shift_state e,
     pe_index e, length (pe_stack e))›
| ‹diag_probe (Inr _) = None›

definition pmsg_lines :: ‹pmsg ⇒ string list› where
  ‹pmsg_lines m = (nat_str (pm_line m) @ '':'' @ nat_str (pm_col m) @ '': '' @ pm_text m) #
     map (λs. ''  '' @ s) (pm_notes m)›

definition perr_render :: ‹('n, 't) pinfo ⇒ ('ch ⇒ string) ⇒ ('n, 't, 'ch, 'm) perr ⇒ string› where
  ‹perr_render I chs e = (case pmsg_lines (perr_message I chs e) of
     [] ⇒ [] | l # ls ⇒ l @ concat (map (λs. CHR 0x0A # s) ls))›

end