Theory Recover_Tests

(* Author: Basil Fürer *)

theory Recover_Tests
  imports TIGER_Grammar_Tests.Diag_Tests TIGER_Grammar_Tests.Parser_Check
begin

section ‹Recovery from rejected words›

text ‹Tokens with their offsets, as a lexer gives them: the span of an error token
  is computed from them.›

definition tr :: ‹nat ⇒ nat ⇒ 'tok ⇒ ('tok, unit) token› where
  ‹tr l c x = ⦇tok = x, span = span.make l c (100 * l + c) 1 []⦈›

fun toks :: ‹nat ⇒ 'tok list ⇒ ('tok, unit) token list› where
  ‹toks i [] = []›
| ‹toks i (x # xs) = tr 0 i x # toks (Suc (Suc i)) xs›

definition rtoks :: ‹('n, 't, unit, unit) perr list × ('t, unit) token list ⇒
    nat list × ('t × nat × nat) list› where
  ‹rtoks r = (map pe_index (fst r), map (λx. (tok x, s_col (span x), s_len (span x))) (snd r))›

subsection ‹Layout-free: the simple driver›

datatype r_tok = RX | RNum | RPlus | RSemi | RLP | RRP | REq | RErr

datatype r_exp = ENum | EAdd r_exp r_exp | EBad
datatype r_stmt = SLet r_exp | SBad

grammar (relation) rc =
  tokens ‹r_tok›
  productions
    P :: ‹r_stmt list› = St RSemi P ⇒ ‹λs _ p. s # p› | St ⇒ ‹λs. [s]›
  and
    St :: ‹r_stmt› = RX REq E ⇒ ‹λ_ _ e. SLet e› | RErr ⇒ ‹λ_. SBad›
  and
    E :: ‹r_exp› = E RPlus T ⇒ ‹λa _ b. EAdd a b› | T
  and
    T :: ‹r_exp› = RNum ⇒ ‹λ_. ENum› | RLP E RRP ⇒ ‹λ_ e _. e› | RErr ⇒ ‹λ_. EBad›

parser (no_diagnostics) rc_plain for rc

parser (diagnostics) rc_parse for rc recover RErr

ML ‹same_code context "rc_plain" "rc_parse" ["_coverage", "_diag", "_info", "_probe", "_recover", "_render", "_repair", "_terminals"]›

ML ‹val _ = @{thms rc_parse_recover.clean rc_parse_recover.no_error}›

text ‹A good word goes through untouched.›

parser_check ‹rc_parse_recover (toks 0 [RX, REq, RNum]) = ([], Some [SLet ENum])›

text ‹The offending token is replaced where an expression may stand, and the
  error token is not offered as expected.›

parser_check ‹(case rc_parse_recover (toks 0 [RX, REq, RNum, RPlus, RRP, RSemi, RX, REq, RNum]) of
    ([e], Some x) ⇒ pe_index e = 4 ∧ pe_expected e = [RNum, RLP] ∧
      x = [SLet (EAdd ENum EBad), SLet ENum]
  | _ ⇒ False)›

text ‹Nothing skipped: the error token is inserted, with an empty span.›

parser_check ‹rtoks (rc_parse_repair (toks 0 [RX, REq, RSemi, RX, REq, RNum])) =
    ([2], [(RX, 0, 1), (REq, 2, 1), (RErr, 4, 0), (RSemi, 4, 1), (RX, 6, 1), (REq, 8, 1), (RNum, 10, 1)])›

text ‹At the end of the input.›

parser_check ‹rtoks (rc_parse_repair (toks 0 [RX, REq, RNum, RPlus])) =
    ([4], [(RX, 0, 1), (REq, 2, 1), (RNum, 4, 1), (RPlus, 6, 1), (RErr, 7, 0)])›

text ‹The stack is popped to where the error token can be shifted, and the tokens
  up to the continuation are skipped: the span runs from the first to the last.›

parser_check ‹rtoks (rc_parse_repair (toks 0 [RX, REq, RNum, RNum, RNum, RSemi, RX, REq, RNum])) =
    ([3], [(RX, 0, 1), (REq, 2, 1), (RErr, 4, 5), (RSemi, 10, 1), (RX, 12, 1), (REq, 14, 1), (RNum, 16, 1)])›

text ‹A statement that does not start right, with no expression on the stack.›

parser_check ‹rc_parse_recover (toks 0 [RRP, RSemi, RX, REq, RNum]) ≠ ([], None) ∧
    snd (rc_parse_recover (toks 0 [RRP, RSemi, RX, REq, RNum])) = Some [SBad, SLet ENum]›

text ‹Several errors in one word, each index one of the original word.›

parser_check ‹(case rc_parse_recover (toks 0 [RX, REq, RRP, RSemi, RX, REq, RNum, RSemi, RX, RSemi,
      RX, REq, RPlus, RSemi, RX, REq, RNum]) of (es, x) ⇒ (map pe_index es, x)) =
    ([2, 9, 12], Some [SLet EBad, SLet ENum, SBad, SLet (EAdd EBad EBad), SLet ENum])›

text ‹A second error right after a recovery is taken for a consequence of it: it is
  recovered from, not reported.›

parser_check ‹(case rc_parse_recover (toks 0 [RX, REq, RRP, RRP, RPlus, RRP, RSemi, RX, REq, RNum]) of
    (es, x) ⇒ (map pe_index es, x)) = ([2], Some [SLet (EAdd EBad EBad), SLet ENum])›

text ‹The empty word has no token to make an error token from.›

parser_check ‹(case rc_parse_recover [] of ([e], None) ⇒ pe_index e = 0 | _ ⇒ False)›

text ‹A word with no place for the error token: ‹None›, with the report.›

datatype np_tok = NA | NB | NErr

grammar (relation) np =
  tokens ‹np_tok›
  productions S :: ‹nat› = NA X ⇒ ‹λ_ x. x›
    and X :: ‹nat› = NB ⇒ ‹λ_. 1› | NErr ⇒ ‹λ_. 0›

parser (diagnostics) np_parse for np recover NErr

parser_check ‹(case np_parse_recover (toks 0 [NB]) of ([e], None) ⇒ pe_index e = 0 | _ ⇒ False)›

parser_check ‹snd (np_parse_recover (toks 0 [NA, NA])) = Some 0›

text ‹An entry: the facts are about the grammar of the entry.›

parser (diagnostics) rc_exp for rc (E) recover RErr

ML ‹val _ = @{thms rc_exp_recover.no_error}›

parser_check ‹snd (rc_exp_recover (toks 0 [RNum, RPlus, RRP])) = Some (EAdd ENum EBad)›

text ‹A name that is not a terminal of the grammar is ignored (expected warning).›

parser (diagnostics) np_none for np recover RX

subsection ‹A conflict›

text ‹The error token is an ordinary terminal: the normal check reports a conflict
  it takes part in (expected warnings), and the vector driver restarts on the sparse
  one, which is the sparse adapter here.›

datatype cf_tok = CA | CB | CErr

grammar (relation) cf =
  tokens ‹cf_tok›
  productions S :: ‹nat› = X CB ⇒ ‹λx _. x› | Y CB ⇒ ‹λy _. y›
    and X :: ‹nat› = CA ⇒ ‹λ_. 0› | CErr ⇒ ‹λ_. 1›
    and Y :: ‹nat› = CErr ⇒ ‹λ_. 2›

parser (diagnostics) cf_parse for cf recover CErr

parser_check ‹(case cf_parse_recover (toks 0 [CB, CB]) of (es, x) ⇒ (map pe_index es, x)) =
    ([0], Some 1)›

subsection ‹The set-anchored driver›

text ‹A cycle keeps the parser on the dense tables with the history (expected warning).›

datatype dc_tok = DA | DB | DC | DErr

grammar (relation) dc =
  tokens ‹dc_tok›
  productions S :: ‹nat› = X DB ⇒ ‹λx _. x› | DC D ⇒ ‹λ_ d. d›
    and X :: ‹nat› = DA ⇒ ‹λ_. 0› | DErr ⇒ ‹λ_. 1›
    and D :: ‹nat› = D ⇒ ‹λd. d› | DB ⇒ ‹λ_. 2›

parser (diagnostics) dc_parse for dc recover DErr

parser_check ‹dc_parse_recover (toks 0 [DA, DB]) = ([], Some 0)›

parser_check ‹(case dc_parse_recover (toks 0 [DB, DB]) of (es, x) ⇒ (map pe_index es, x)) =
    ([0], Some 1)›

subsection ‹Layout: the vector driver›

datatype l_tok = LWhile | LColon | LId | LErr

datatype l_stm = LS | LBad

grammar (relation) ly =
  tokens ‹l_tok›
  terminals "while" = ‹LWhile› and ":" = ‹LColon›
  productions
      WhileStmt :: ‹l_stm list› = "while"⇧> Test⇧= ":"⇧> Suite⇧= ⇒ ‹λ_ s. s›
    and
      Test = LId⇧≥ ⇒ ‹λ_. ()›
    and
      Suite :: ‹l_stm list› = Block⇧>
    and
      Block :: ‹l_stm list›
        = St⇧=        ⇒ ‹λs. [s]›
        | Block⇧= St⇧= ⇒ ‹λb s. b @ [s]›
    and
      St :: ‹l_stm› = LId⇧= ⇒ ‹λ_. LS› | LErr⇧= ⇒ ‹λ_. LBad›

parser (no_diagnostics) ly_plain for ly

parser (diagnostics) ly_parse for ly recover LErr

ML ‹same_code context "ly_plain" "ly_parse" ["_coverage", "_diag", "_info", "_probe", "_recover", "_render", "_repair", "_terminals"]›

definition lw where ‹lw xs = map (λ(l, c, x). tr l c x) xs›

parser_check ‹ly_parse_recover (lw [(0, 1, LWhile), (0, 7, LId), (0, 8, LColon), (1, 3, LId), (2, 3, LId)]) =
    ([], Some [LS, LS])›

text ‹A misaligned statement: the error token gets the column that fits, and the
  word stays good from there on.›

parser_check ‹(case ly_parse_recover (lw [(0, 1, LWhile), (0, 7, LId), (0, 8, LColon), (1, 3, LId), (2, 4, LId), (3, 3, LId)])
    of (es, x) ⇒ (map (λe. (pe_index e, pe_kind e)) es, x)) =
    ([(4, Misaligned [(3, Some 3)])], Some [LS, LBad, LS])›

parser_check ‹rtoks (ly_parse_repair (lw [(0, 1, LWhile), (0, 7, LId), (0, 8, LColon), (1, 3, LId), (2, 4, LId), (3, 3, LId)])) =
    ([4], [(LWhile, 1, 1), (LId, 7, 1), (LColon, 8, 1), (LId, 3, 1), (LErr, 3, 1), (LId, 3, 1)])›

text ‹An offside suite: its token is replaced at a column the state accepts.›

parser_check ‹(case ly_parse_recover (lw [(0, 1, LWhile), (0, 7, LId), (0, 8, LColon), (1, 0, LId)])
    of (es, x) ⇒ (map (λe. (pe_index e, pe_kind e)) es, x)) =
    ([(3, Offside [(1, None)])], Some [LBad])›

parser_check ‹rtoks (ly_parse_repair (lw [(0, 1, LWhile), (0, 7, LId), (0, 8, LColon), (1, 0, LId)])) =
    ([3], [(LWhile, 1, 1), (LId, 7, 1), (LColon, 8, 1), (LErr, 1, 1)])›

text ‹Two errors, far apart.›

parser_check ‹(case ly_parse_recover (lw [(0, 1, LWhile), (0, 7, LId), (0, 8, LColon), (1, 3, LId), (2, 4, LId),
   (3, 3, LId), (4, 3, LId), (5, 3, LId), (6, 3, LId), (7, 5, LId), (8, 3, LId)])
  of (es, x) ⇒ (map (λe. (pe_index e, pe_kind e)) es, x)) =
    ([(4, Misaligned [(3, Some 3)]), (9, Misaligned [(3, Some 3)])],
     Some [LS, LBad, LS, LS, LS, LS, LBad, LS])›

subsection ‹Reports and target languages›

text ‹The report of a stop is the one of ‹p_diag›, on the original word.›

parser_check ‹(case rc_parse_diag (toks 0 [RX, RNum]) of
    Inl e ⇒ fst (rc_parse_recover (toks 0 [RX, RNum])) = [e] | Inr _ ⇒ False)›

export_code rc_parse_recover ly_parse_recover cf_parse_recover dc_parse_recover
  checking SML Scala

export_code rc_parse_recover ly_parse_recover cf_parse_recover dc_parse_recover in Haskell

export_code rc_parse_recover ly_parse_recover cf_parse_recover dc_parse_recover in OCaml

end