Theory Reach_Tests

(* Author: Basil Fürer *)

theory Reach_Tests
  imports TIGER_Grammar.LR_Parser Parser_Check
begin

section ‹Coverage of the error states›

text ‹Sentences of the driver against 🗏‹../lr_reach.ML›: every word over the
  terminals up to a length, cut at the first error, gives the same pairs of a state and
  a terminal and the same shortest lengths as the engine.›

declare [[parser_errors_budget = 120]]

ML ‹
fun coverage_of ctxt name =
  let
    val cov = the (LR_Backend.get_coverage ctxt name);
    val ((view, driver), _) = LR_Backend.evaluate_coverage ctxt (#coverage cov) [];
  in (cov, view, driver) end;

fun brute ctxt name len =
  let
    val (cov, view, driver) = coverage_of ctxt name;
    val hide = #hide cov;
    val (v, _, _) = LR_Backend.dest_view view;
    val nt = #nterms v;
    val r = LR_Reach.run {hide = hide, seconds = 30.0} v;
    fun key (s, z) = s * (nt + 1) + z;
    fun enc w = maps (fn t => [t, 0]) (rev w);
    val toks = filter (fn t => SOME t <> hide) (0 upto nt - 1);
    val seen = Unsynchronized.ref Inttab.empty;
    fun note k d = seen := Inttab.map_default (k, d) (fn e => Int.min (e, d)) (!seen);
    fun step w =
      (case driver (enc w) of
        [] => true
      | st :: tk :: _ :: idx :: _ => (note (key (st, tk)) idx; tk = nt)
      | _ => raise Fail "driver");
    fun layer n fr =
      if n > len orelse null fr then ()
      else
        let val alive = filter step fr
        in layer (n + 1) (if n = len then [] else maps (fn w => map (fn t => t :: w) toks) alive) end;
    val _ = layer 0 [[]];
    val eng = Inttab.make (map (fn {state, look, dist, ...} => (key (state, look), dist)) (#errors r));
    val seen = Inttab.dest (!seen);
    val missing = filter_out (Inttab.defined eng o fst) seen;
    val wrong = filter (fn (k, d) => Inttab.lookup eng k <> SOME d andalso Inttab.defined eng k) seen;
    val extra =
      filter (fn {state, look, dist, ...} =>
        (if look = nt then dist <= len else dist < len) andalso
        not (AList.defined (op =) seen (key (state, look)))) (#errors r);
    val _ = assert (#complete r andalso null missing andalso null wrong andalso null extra);
  in (length (#errors r), #facts r) end;
›

datatype t = X | Num | Plus | Semi | LP | RP

grammar g =
  tokens ‹t›
  productions
    S :: ‹nat› = E Semi S ⇒ ‹λe _ s. e› | E
  and
    E :: ‹nat› = E Plus T ⇒ ‹λa _ b. a› | T
  and
    T :: ‹nat› = X ⇒ ‹λ_. 1› | Num ⇒ ‹λ_. 2› | LP E RP ⇒ ‹λ_ e _. e›

parser (diagnostics) p for g
  errors
    LP RP ⇒ ‹m›

ML ‹assert (brute context const_name‹p› 8 = (28, 254))›

parser_error_states p
parser_error_states (token) p

text ‹The skeleton of an ‹errors› block for the open states, one shortest sentence each.›

ML ‹
fun skeleton_of ctxt name by_token =
  let
    val (cov, view, driver) = coverage_of ctxt name;
    val hits = LR_Backend.error_hits ctxt cov (view, driver);
  in LR_Diagnostics.skeleton (#spelled cov) by_token (filter_out (LR_Diagnostics.covered (#keys cov)) hits) end;
›

ML ‹
  assert (skeleton_of context const_name‹p› false = cat_lines
    ["errors",
     "    \"X\" \"X\" ⇒ ‹TODO state 3›",
     "  | \"Num\" \"X\" ⇒ ‹TODO state 4›",
     "  | \"LP\" \"Num\" \"RP\" \"X\" ⇒ ‹TODO state 5›",
     "  | \"LP\" \"Num\" ⇒ ‹TODO state 6›",
     "  | \"Num\" \"Semi\" ⇒ ‹TODO state 9›",
     "  | \"Num\" \"Plus\" ⇒ ‹TODO state 11›",
     "  | \"Num\" \"RP\" ⇒ ‹TODO state 12›",
     "  | ‹[]› ⇒ ‹TODO state 13›"])›

datatype t2 = Ta | Tb | Tc | Td | Te | Tf | Tg

grammar g2 =
  tokens ‹t2›
  productions
    S :: ‹nat› = Ta A Tc ⇒ ‹λ_ _ _. 0› | Tb A Td ⇒ ‹λ_ _ _. 0› | L Te ⇒ ‹λ_ _. 0›
  and
    A :: ‹nat› = Tg ⇒ ‹λ_. 0›
  and
    L :: ‹nat› = ⇒ ‹0› | L I ⇒ ‹λ_ _. 0›
  and
    I :: ‹nat› = Tf O Ta ⇒ ‹λ_ _ _. 0›
  and
    O :: ‹nat› = ⇒ ‹0› | Tb ⇒ ‹λ_. 0›

parser (diagnostics) p2 for g2

ML ‹assert (brute context const_name‹p2› 9 = (66, 47))›

text ‹The error token: states only it reaches are no error states.›

datatype t3 = X3 | Plus3 | Semi3 | Err3

grammar g3 =
  tokens ‹t3›
  productions
    S :: ‹nat› = E Semi3 S ⇒ ‹λe _ s. e› | E | Err3 Semi3 S ⇒ ‹λ_ _ s. s›
  and
    E :: ‹nat› = E Plus3 X3 ⇒ ‹λa _ _. a› | X3 ⇒ ‹λ_. 1›

parser (diagnostics) p3 for g3 recover Err3

ML ‹assert (brute context const_name‹p3› 9 = (11, 53))›

parser_error_states p3

text ‹The skeleton of ‹p› pasted: every error state has a message now.›

parser (diagnostics) p_full for g
  errors
    LP RP ⇒ ‹m›
  | "X" "X" ⇒ ‹an operand is followed by another operand›
  | "Num" "X" ⇒ ‹a number is followed by an operand›
  | "LP" "Num" "RP" "X" ⇒ ‹a parenthesis is followed by an operand›
  | "LP" "Num" ⇒ ‹a parenthesis is not closed›
  | "Num" "Semi" ⇒ ‹a statement is missing after ';'›
  | "Num" "Plus" ⇒ ‹an operand is missing after '+'›
  | "Num" "RP" ⇒ ‹a ')' without '('›
  | ‹[]› ⇒ ‹the input is empty›

ML ‹assert (length (#keys (the (LR_Backend.get_coverage context const_name‹p_full›))) = 9)›

text ‹The same with a key for each pair, and a key that does not count.›

parser (diagnostics) p_key for g
  errors
    LP RP (token) ⇒ ‹m›
  | LP RP (shift) ⇒ ‹n›

ML ‹
  let val c = the (LR_Backend.get_coverage context const_name‹p_key›)
  in assert (length (#keys c) = 1 andalso #shifts c = 1) end›

section ‹A grammar with columns›

datatype tok = While | Colon | Id

grammar py =
  tokens ‹tok›
  terminals "while" = ‹While› and ":" = ‹Colon›
  productions
      Prog :: ‹nat› = Block
    and
      Block :: ‹nat›
        = Stmt⇧=
        | Block⇧= Stmt⇧=  ⇒ ‹(+)›
    and
      Stmt :: ‹nat›
        = Id⇧=                      ⇒ ‹λ_. 1›
        | "while"⇧= Id⇧> ":"⇧> Block⇧>  ⇒ ‹λ_ n. n + 1›

parser (diagnostics) py_p for py
  errors
    "while"@1 Id@7 ":"@8 Id@3 Id@4 ⇒ ‹Statements of a suite line up.›

parser_error_states py_p

text ‹The driver on every word up to a length in every order of its columns meets
  no error outside the list.›

ML ‹
fun brute_columns ctxt name len =
  let
    val (cov, view, driver) = coverage_of ctxt name;
    val hits = LR_Backend.error_hits ctxt cov (view, driver);
    val listed = map (fn {state, look, ...} => (state, look)) hits;
    val nt = length (#spelled cov);
    val seen = Unsynchronized.ref [];
    fun choices [] = [0, 8]
      | choices cs =
          let
            val s = sort_distinct int_ord cs;
            fun mids (a :: (r as b :: _)) = (a + b) div 2 :: mids r
              | mids _ = [];
          in s @ mids s @ [List.last s + 64] @ (if hd s > 1 then [hd s div 2] else []) end;
    fun go w =
      List.app (fn t => List.app (fn c =>
        let val w' = w @ [(t, c)]
        in
          (case driver (maps (fn (a, b) => [a, b]) w') of
            [] => if length w' < len then go w' else ()
          | st :: tk :: _ =>
              (seen := insert (op =) (st, tk) (!seen);
               if tk = nt andalso length w' < len then go w' else ())
          | _ => raise Fail "driver")
        end) (choices (map snd w))) (0 upto nt - 1);
    val _ = go [];
  in (length listed, length (!seen), subtract (op =) listed (!seen)) end;
›

ML ‹assert (#3 (brute_columns context const_name‹py_p› 6) = [])›

section ‹‹on_error_reduce››

text ‹The error after a statement of a suite: without the option in the state of the
  token, with it in the state after the reductions.›

definition col :: ‹nat ⇒ 't ⇒ ('t, unit) token› where
  ‹col c t = ⦇tok = t, span = span.make 0 c c 1 []⦈›

parser (diagnostics) py_o for py
  on_error_reduce Stmt Block
  errors
    "while"@1 Id@7 ":"@8 Id@3 ":"@9 ⇒ ‹after a suite›

ML ‹val _ = @{thms py_o_diag.Inr_iff}›

definition py_w where ‹py_w = [col 1 While, col 7 Id, col 8 Colon, col 3 Id, col 9 Colon]›

parser_check ‹(case (py_o_diag_base py_w, py_o_diag py_w) of
    (Inl a, Inl b) ⇒ pe_state a ≠ pe_state b ∧ pe_index a = pe_index b
  | _ ⇒ False)›

parser_check ‹py_o [col 1 While, col 7 Id, col 8 Colon, col 3 Id] = py_p [col 1 While, col 7 Id, col 8 Colon, col 3 Id]›

text ‹With recovery the report is the one of ‹p_diag›, the repair the plain one.›

datatype tr = RId | RColon | RErr

grammar pr =
  tokens ‹tr›
  productions
      Block :: ‹nat›
        = Stmt⇧=
        | Block⇧= Stmt⇧=  ⇒ ‹(+)›
    and
      Stmt :: ‹nat›
        = RId⇧= ⇒ ‹λ_. 1›
        | RId⇧= RColon⇧> Block⇧> ⇒ ‹λ_ _ n. n›
        | RErr⇧= ⇒ ‹λ_. 0›

parser (diagnostics) pr_o for pr recover RErr on_error_reduce Stmt

definition pr_w where ‹pr_w = [col 0 RId, col 2 RColon, col 4 RId, col 6 RColon, col 8 RColon]›

parser_check ‹(case (fst (pr_o_repair pr_w), pr_o_diag pr_w) of
    (a # _, Inl b) ⇒ pe_state a = pe_state b | _ ⇒ False)›

text ‹The sparse and the dense drivers.›

datatype cf_tok = CA | CB | CErr

grammar 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_p for cf recover CErr
  errors CB ⇒ ‹m›

parser_error_states cf_p

datatype dc_tok = DA | DB | DC

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

parser (diagnostics) dc_o for dc on_error_reduce X
  errors DA DA ⇒ ‹m›

parser_check ‹(case dc_o_diag [col 0 DA, col 2 DA] of Inl e ⇒ pe_index e = 1 | _ ⇒ False)›

text ‹The simple driver ignores it, with a warning.›

parser (diagnostics) p_o for g on_error_reduce T
  errors LP RP ⇒ ‹m›

section ‹Tokens with further fields›

record tt = ‹(t, unit) token› +
  mark :: nat

grammar gt =
  tokens ‹tt›
  productions
    S :: ‹nat› = X Plus X ⇒ ‹λa _ b. mark a›

parser (diagnostics) p_t for gt
  token_info ‹λ_. tt.fields 7›
  errors X X ⇒ ‹m›

parser_error_states p_t

text ‹Without it the sentences are not run, and the pairs are still listed.›

parser (diagnostics) p_u for gt
  errors ‹[⦇tok = X, span = span.make 0 0 0 1 [], mark = 0⦈, ⦇tok = X, span = span.make 0 2 2 1 [], mark = 0⦈]› ⇒ ‹m›

end