Theory Span_Tests

(* Author: Basil Fürer *)

theory Span_Tests
  imports TIGER_Grammar.LR_Prec_Parse Parser_Check
begin

section ‹The span of a yield: ‹@span››

text ‹‹@span› in an alternative passes the action the span of the alternative's yield,
  in the place where it is written among the value symbols. It is not a grammar symbol:
  the grammar constant does not see it.›

datatype s_tok = SNum | SPlus | SStar | SLP | SRP | SU

datatype ex = Num nat | Add nat nat ex ex | Mul nat nat ex ex | Par nat ‹char list› ex | Unit nat

type_synonym stoken = ‹(s_tok, char) token›

text ‹A token at line 1, column and offset ‹i›, of the text ‹s›; consecutive tokens
  are one character apart, so the yield of a node has gaps.›

fun stoks :: ‹nat ⇒ (s_tok × string) list ⇒ stoken list› where
  ‹stoks i [] = []›
| ‹stoks i ((t, s) # xs) =
    ⦇tok = t, span = span.make 1 i i (length s) s⦈ # stoks (i + length s + 1) xs›

grammar spx =
  tokens ‹stoken›
  terminals "+" = ‹SPlus› and "(" = ‹SLP› and ")" = ‹SRP› and "()" = ‹SU›
  productions
    E :: ‹ex› = E "+" T @span ⇒ ‹λa b sp. Add (s_off sp) (s_len sp) a b› | T
  and
    T :: ‹ex› = SNum ⇒ ‹λx. Num (s_off (span x))›
      | "(" @span E ")" ⇒ ‹λsp e. Par (s_col sp) (s_txt sp) e›
      | "()" @span ⇒ ‹λsp. Unit (s_len sp)›

text ‹The grammar constant has no trace of ‹@span›.›

lemma ‹spx =
  is_cfg.make
   [(''E'', [(Nt ''E'', Any), (Tm SPlus, Any), (Nt ''T'', Any)]),
    (''E'', [(Nt ''T'', Any)]),
    (''T'', [(Tm SNum, Any)]),
    (''T'', [(Tm SLP, Any), (Nt ''E'', Any), (Tm SRP, Any)]),
    (''T'', [(Tm SU, Any)])]
   ''E'' 0›
  by (simp only: spx_def)

parser spx_parse for spx

text ‹‹1 + (2 + ())› at offsets 0, 2, 4, 6, 8, 10, 13: the whole word spans 14
  characters, the inner sum 6 (from ‹2› to the end of ‹()›).›

definition w1 :: ‹stoken list› where
  ‹w1 = stoks 0 [(SNum, ''1''), (SPlus, ''+''), (SLP, ''(''), (SNum, ''2''), (SPlus, ''+''),
    (SU, ''()''), (SRP, '')'')]›

parser_check ‹spx_parse w1 =
  Some (Add 0 14 (Num 0) (Par 4 ''(2+())'' (Add 6 6 (Num 6) (Unit 2))))›

subsection ‹With the relation: the bridge›

text ‹The relation's intro takes const‹word_span› of the production's word, the
  decoder const‹yield_span› of the node's children; the parser's theorems relate the
  two.›

grammar (relation) spr =
  tokens ‹stoken›
  terminals "+" = ‹SPlus› and "(" = ‹SLP› and ")" = ‹SRP› and "()" = ‹SU›
  productions
    E :: ‹ex› = E "+" T @span ⇒ ‹λa b sp. Add (s_off sp) (s_len sp) a b› | T
  and
    T :: ‹ex› = SNum ⇒ ‹λx. Num (s_off (span x))›
      | "(" @span E ")" ⇒ ‹λsp e. Par (s_col sp) (s_txt sp) e›
      | "()" @span ⇒ ‹λsp. Unit (s_len sp)›

ML ‹val _ = @{thms spr.intros}›

parser spr_parse for spr

parser_check ‹spr_parse w1 =
  Some (Add 0 14 (Num 0) (Par 4 ''(2+())'' (Add 6 6 (Num 6) (Unit 2))))›

lemma ‹spr_parse w = Some x ⟹ spr_E w x›
  by (fact spr_parse.sound)

lemma ‹spr_E w x ⟹ spr_parse w = Some x›
  by (fact spr_parse.complete)

subsection ‹Under layout, in a template, nested›

text ‹An indentation-sensitive relation (the intros carry the column premises) and a
  template alternative with ‹@span›; ‹S›'s value is the length of each nested yield.›

grammar (relation) spl =
  tokens ‹stoken›
  terminals "(" = ‹SLP› and ")" = ‹SRP›
  productions
    Wrap(X) :: ‹nat list› = "(" X⇧> ")" @span ⇒ ‹λxs sp. s_len sp # xs›
  and
    S :: ‹nat list› = SNum⇧= ⇒ ‹λ_. []› | Wrap(S)

parser spl_parse for spl

parser_check ‹spl_parse (stoks 0 [(SLP, ''(''), (SLP, ''(''), (SNum, ''42''), (SRP, '')''), (SRP, '')'')]) =
  Some [10, 6]›

lemma ‹spl_parse w = Some x ⟹ spl_S 0 w x›
  by (fact spl_parse.sound)

subsection ‹With precedence declarations›

text ‹The parser is built from the restricted grammar; the decoders, and with them
  ‹@span›, are those of the grammar as written.›

grammar spp =
  tokens ‹stoken›
  terminals "+" = ‹SPlus› and "*" = ‹SStar›
  precedence left "*" > left "+"
  productions
    E :: ‹ex›
      = E "+" E @span ⇒ ‹λa b sp. Add (s_off sp) (s_len sp) a b›
      | E "*" @span E ⇒ ‹λa sp b. Mul (s_off sp) (s_len sp) a b›
      | SNum ⇒ ‹λx. Num (s_off (span x))›

parser spp_parse for spp

text ‹‹1 + 2 * 3› at offsets 0, 2, 4, 6, 8.›

parser_check ‹spp_parse (stoks 0 [(SNum, ''1''), (SPlus, ''+''), (SNum, ''2''), (SStar, ''*''), (SNum, ''3'')]) =
  Some (Add 0 9 (Num 0) (Mul 4 5 (Num 4) (Num 8)))›

subsection ‹Errors›

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

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

ML ‹
  val _ = rejected "whose yield can be empty, ‹S = @span›"
    "grammar bad = tokens s_tok productions S :: nat = @span ⇒ ‹λsp. s_len sp›";
  val _ = rejected "whose yield can be empty, ‹S = O @span›"
    "grammar bad = tokens s_tok productions S :: nat = O @span ⇒ ‹λ_ sp. s_len sp› \
    \and O :: unit = ⇒ ‹()› | SNum ⇒ ‹λ_. ()›";
  val _ = rejected "has @span twice"
    "grammar bad = tokens s_tok productions S :: nat = SNum @span @span ⇒ ‹λ_ sp _. s_len sp›";
  val _ = rejected "takes no annotation"
    "grammar bad = tokens s_tok productions S :: nat = SNum @span= ⇒ ‹λ_ sp. s_len sp›";
  val _ = rejected "@span inside an operator's group"
    "grammar bad = tokens s_tok productions S :: ‹nat list› = (SNum @span)+ ⇒ ‹λxs. map fst xs›";
  val _ = rejected "@span is not a template argument"
    "grammar bad = tokens s_tok productions P(X) :: nat = SNum X ⇒ ‹λ_ _. 0› and S :: nat = P(@span)";
  val _ = rejected "(here SNum, @span)"
    "grammar bad = tokens s_tok productions S :: nat = SNum @span ⇒ ‹λsp. s_len sp›";
›

end