tests/regression.tc

   1 testcase "pathological O(n^2) behavior" {
   2   input "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
   3   output "x";
   4           s = x:: ManyA!
   5      ManyA =  ()
   6             | x:: A ManyA
   7           A = ()! ("a" & ManyAB)
   8     ManyAB = ()
   9             | "a" ManyAB
  10             | "b" ManyAB
  11
  12 }
  13
  14 testcase "another O(n^2) example, tickles different epsilon behaviors" {
  15   input "aaaa";
  16   output "x:{x:{x:{x}}}";
  17   s = x:: s A! | ()
  18   A = "a" & B
  19   B = () | B "a"
  20 }
  21
  22 testcase "unnamed" {
  23     input "aaaaa";
  24     s = A
  25     A = "a" s &~ "a" A
  26       | "a" A &~ "a" s
  27 }
  28
  29 testcase "unnamed" {
  30     input "ab c";
  31     output "1:{{a b} {c}}";
  32
  33     s     = ids
  34     ids   = "1":: id (" " ids &~ id ("":: ~[]*))
  35           | "2":: id (    ids &~ id ("":: ~[]*))
  36           | id
  37     id    = "":: [a-z]++
  38 }
  39
  40 testcase "unnamed" {
  41     input "ab c";
  42
  43     output "2:{{a} 1:{{b} {c}}}";
  44     output "1:{{a b} {c}}";
  45
  46     s     = ids
  47     ids   = "1":: id " " ids
  48           | "2":: id     ids
  49           | id
  50     id    = "":: [a-z]+
  51 }
  52
  53 testcase "unnamed" {
  54     input "aaabbbccc";
  55     output "ab";
  56
  57     s     = ab & dc
  58     ab    = ab:: a b
  59     dc    = dc:: d c
  60     a     = "a" a     | ()
  61     b     = "b" b "c" | ()
  62     c     = "c" c     | ()
  63     d     = "a" d "b" | ()
  64 }
  65
  66 testcase "unnamed" {
  67     input "aaabbbbccc";
  68
  69     s     = ab & dc
  70     ab    = ab:: a b
  71     dc    = dc:: d c
  72     a     = "a" a     | ()
  73     b     = "b" b "c" | ()
  74     c     = "c" c     | ()
  75     d     = "a" d "b" | ()
  76 }
  77
  78 testcase "unnamed" {
  79     input "aabb";
  80     output "xbx:{{a} abab:{a b} {b}}";
  81
  82     x     = ~[]
  83     s     = xbx:: ("":: x*) b ("":: x*)
  84     b     = abab:: [ab][ab]
  85          &~ ("aa"|"bb")
  86 }
  87
  88 testcase "unnamed" {
  89     input  "qxbambambam";
  90     output "bam:{a bam:{a bam:{a x}}}";
  91
  92     s   = "q" z
  93     z   = a z ^"bam"
  94         | ^"x"
  95     a   = a:: ()
  96 }
  97
  98 testcase "unnamed" {
  99     input  "baaaa";
 100     output "s2:{b0 a:{a:{epsilon}}}";
 101     output "b:{a:{a:{epsilon}} epsilon}";
 102     s   = s2:: b t
 103         | ^"b" t b
 104     t   = ^"a" t "a"
 105         | epsilon:: ()
 106     b   = b0:: "b"
 107         | epsilon:: ()
 108 }
 109
 110 testcase "qaq" {
 111     input  "qaq";
 112     output "q:{a:{s1}}";
 113
 114     s   = ^"q" x "q"
 115     x   = ^"a" a
 116         | epsilon:: ()
 117     a   = s1:: x
 118 }
 119
 120 testcase "unnamed" {
 121     input "baa";
 122     output "s1:{a2:{a2:{a0 b0} b0}}";
 123
 124     s   = s1:: "b" a
 125     a   = a2:: "a" a b
 126         | a0:: ()
 127     b   = b0:: ()
 128 }
 129
 130 testcase "epsilon forests" {
 131     input  "aaa";
 132
 133     output "s3:{s3:{epsilon a0 epsilon epsilon} epsilon epsilon epsilon}";
 134     output "s3:{s3:{epsilon epsilon epsilon epsilon} a0 epsilon epsilon}";
 135     output "s3:{s3:{epsilon epsilon a0 epsilon} epsilon epsilon epsilon}";
 136     output "s3:{s3:{epsilon epsilon epsilon a0} epsilon epsilon epsilon}";
 137     output "s3:{epsilon epsilon a0 a0}";
 138     output "s3:{s3:{s3:{epsilon epsilon epsilon epsilon} epsilon epsilon epsilon} epsilon epsilon epsilon}";
 139     output "s3:{s3:{epsilon epsilon epsilon epsilon} epsilon epsilon a0}";
 140     output "s3:{s3:{epsilon epsilon epsilon epsilon} epsilon a0 epsilon}";
 141     output "s3:{epsilon a0 epsilon a0}";
 142     output "s3:{epsilon a0 a0 epsilon}";
 143
 144     s   = s3:: "a" s a a a
 145         | epsilon:: ()
 146     a   = a0:: "a"
 147         | epsilon:: ()
 148 }
 149
 150 testcase "unnamed" {
 151     input "aa";
 152     output "poo:{poo:{poox poox} poox}";
 153     output "poo:{poox poo:{poox poox}}";
 154     s   = poo::  s s "a"
 155         | poox:: ()
 156 }
 157
 158 testcase "unnamed" {
 159     input "baa";
 160     output "s:{aa:{aa:{a b} b}}";
 161     s   = s:: "b" a
 162     a   = aa:: "a" a b
 163         | a:: ()
 164     b   = b:: ()
 165 }
 166
 167 testcase "unnamed" {
 168     input "aaab";
 169     output "sx:{b aa:{aa:{b b} b}}";
 170     s   = sx:: b d "a" "b"
 171         | sy:: "a" d "a" d
 172     d   = aa:: "a" a b
 173     a   = aa:: "a" b b
 174         | a::  ()
 175     b   = b::  ()
 176 }
 177
 178 testcase "a+(b*c)" {
 179     input "a+(b*c)";
 180     output "+:{{a} *:{{b} {c}}}";
 181
 182     s     = r
 183     r     = id
 184           | r ^"*" r
 185           | r ^"+" r
 186           | "(" r ")"
 187     id    = "":: [a-z]++
 188 }
 189
 190 testcase "a+b-d*c" {
 191     input "a+b-d*c";
 192     output "times:{plus:{stringify:{a} minus:{stringify:{b} stringify:{d}}} stringify:{c}}";
 193     output "plus:{stringify:{a} times:{minus:{stringify:{b} stringify:{d}} stringify:{c}}}";
 194     output "minus:{plus:{stringify:{a} stringify:{b}} times:{stringify:{d} stringify:{c}}}";
 195     output "plus:{stringify:{a} minus:{stringify:{b} times:{stringify:{d} stringify:{c}}}}";
 196     output "times:{minus:{plus:{stringify:{a} stringify:{b}} stringify:{d}} stringify:{c}}";
 197     w    = " "
 198     l    = id
 199     s    = assign:: l "=" q
 200          | q
 201     q    = id
 202          | assign:: l "=" q
 203          | minus:: q "-" q
 204          | plus:: q "+" q
 205          | times:: q "*" q
 206          | "(" q ")"
 207     id     = stringify:: idl++
 208     idl    = [a-d]
 209 }
 210
 211 testcase "priority" {
 212     input "a+b*c";
 213     output "plus:{stringify:{a} times:{stringify:{b} stringify:{c}}}";
 214     w    = " "
 215     l    = id
 216     s    = assign:: l "=" r
 217          | r
 218     r    = l
 219          | assign:: l "=" r
 220          | plus:: r "+" r
 221          > times:: r "*" r
 222          | "(" r ")"
 223          | times:: r r
 224     id     = stringify:: idl++
 225     idl    = [a-d]
 226 }
 227
 228 testcase "associativity" {
 229     input "a*b*c";
 230     output "times:{stringify:{a} times:{stringify:{b} stringify:{c}}}";
 231     w    = " "
 232     l    = id
 233     s    = assign:: l "=" r
 234          | r
 235     r    = l
 236          | assign:: l "=" r
 237          | plus:: r "+" r
 238          | times:: r "*" (r)
 239          | "(" r ")"
 240          | times:: r r
 241     id     = stringify:: idl++
 242     idl    = [a-d]
 243 }
 244
 245 testcase "unnamed" {
 246   input "aa bb";
 247   output "{q:{a a} q:{b b}}";
 248
 249   s    = "":: q */ ws
 250   ws   = " "*
 251   q    = q:: [a-z]++
 252 }
 253
 254 testcase "indentation" {
 255
 256     input "
 257
 258
 259
 260  while x>0
 261     while y>0
 262        foo()
 263           bar()
 264
 265
 266  while x>0
 267     while y>0
 268           foo()
 269         bar()
 270
 271
 272
 273 ";
 274   output "smt:{while:{>:{{x} {0}} while:{>:{{y} {0}} sbb:{{f o o} {b a r}}}} while:{>:{{x} {0}} sbb:{while:{>:{{y} {0}} {f o o}} {b a r}}}}";
 275
 276 indent    = ww
 277 outdent   = " "  outdent " "
 278           | " "  ("":: (~[])*)  "\n"
 279
 280 w          = " " | "\n" | "\r"
 281 ws         = "":: w*
 282 ww         = "":: sp*
 283 sp         = " "
 284 any        = "":: (~[])*
 285
 286 s          = smt:: ws! statement ws! statement ws!
 287
 288 block       =        "\n" indent!  blockBody
 289            &~        "\n" (" " outdent! " ") ~[\ ]! ("":: ~[]*)!
 290
 291 blockBody   =       statement
 292             > sbb:: statement ws blockBody
 293
 294 statement   = call
 295             | ^"while" expr block /ws
 296
 297 expr        = ident
 298             | call
 299             | expr ^">" expr   /ws
 300             | num
 301
 302 call        = expr "()"        /ws
 303
 304 num         = "":: [0-9]++
 305
 306 ident       = "":: [a-z]++ &~ keyword
 307 keyword     = "if" | "then" | "else" | "while"
 308
 309
 310
 311 }
 312
 313
 314 testcase "unnamed" {
 315     input "abc                         ";
 316
 317     s     = s2:: q " "*
 318     q     = a3:: [a-z] [a-z] [a-z]
 319          &~ ("":: ~[])! "b" ("":: ~[]*)!
 320 }
 321
 322 testcase "unnamed" {
 323     input "abc                         ";
 324     output "s:{a b c}";
 325
 326     s     = s:: [a-z] [a-z] [a-z] " "*
 327 }
 328
 329 testcase "a+2" {
 330
 331     input "a+2";
 332     output "Plus:{left:{Foo} right:{{2}}}";
 333
 334     s       = Expr
 335     Expr    = "":: [0-9]++
 336             | Plus:: (left::Expra) "+" (right::Expr)
 337     Expra   = Foo:: ("a" | "b")
 338
 339 }
 340
 341 testcase "unnamed" {
 342     input "aaaaa";
 343     output "top:{a q a}";
 344
 345     s = top:: z (q::"a"*) z
 346     z = a:: "a"
 347 }
 348
 349 testcase "dangling else" {
 350     input  "if (x) if (y) z else q";
 351     output "if:{ident:{x} else:{if:{ident:{y} then:{ident:{z}}} ident:{q}}}";
 352
 353     s      = Expr
 354     Expr   = if::     "if" "(" Expr ")" IfBody     /ws
 355            | ident::  [a-z]++
 356     IfBody = else::   Expr            "else"  Expr /ws
 357            | then::   Expr &~   (("":: (~[])*) "else" Expr! /ws)
 358     ws     = "":: [ ]**
 359 }
 360
 361
 362 testcase "unnamed" {
 363     input "12111211";
 364     output "ac:{{2 1 2 1}}";
 365
 366     s   = ab:: ab
 367         | ac:: ac
 368         | bc:: bc
 369     ab   = a & b
 370     ac   = a & c
 371     bc   = b & c
 372     a   = "":: ("1" x)*
 373     b   = "":: ("b":: x "2")*
 374     c   = "":: ("c":: x "2" x "1")*
 375     x   = [123]
 376 }
 377
 378 testcase "follow restrictions on empty string" {
 379   input "xxx";
 380   s = x:: "x" A "x" C "x"
 381   A = B
 382   B = "y"
 383     | () -> ~"x"
 384   C = D -> ~"x"
 385   D = ()
 386 }
 387
 388 testcase "unnamed" {
 389   input "axxxxxc";
 390   output "q:{a {x x x x x} c}";
 391   s  = q:: A ws (B|()) ws C
 392   ws = "":: [x]**
 393   A  = a:: "a"
 394   B  = b:: "b"
 395   C  = c:: "c"
 396 }
 397
 398 testcase "unnamed" {
 399   input "aaaaaaaaaaaaaaaaaaaa";
 400   output "";
 401   s = As & AAs
 402   As = () | As "a"
 403   AAs = () | AAs "aa"
 404 }
 405
 406 testcase "question mark" {
 407   input "aa aba abba";
 408   output "s:{Y Y Z}";
 409   s = s:: X " " X " " X
 410   X = Y > Z
 411   Y = Y:: "a" B? "a"
 412   Z = Z:: "a" "b"* "a"
 413   B = "b"
 414 }
 415
 416 testcase "operator: ... " {
 417   input "aaabbbaaa abababababa";
 418   output "s:{C:{a a a b b b a a a} B:{a b a b a b a b a b a}}";
 419   s:: = A " " A
 420   A   = B > C
 421   B:: = [ab]* &~ (... "bbb" ...)
 422   C:: = [ab]*
 423 }
 424
 425 testcase "operator: ~~" {
 426   input "aaabbbaaa abababababa";
 427   output "s:{C:{a a a b b b a a a} B:{a b a b a b a b a b a}}";
 428   s:: = A " " A
 429   A   = B > C
 430   B:: = ~~(... "bbb" ...)
 431   C:: = [ab]*
 432 }
 433
 434 testcase "lifts" {
 435     input "a+(b*c)";
 436     output "+:{a *:{id:{b} c}}";
 437
 438     s     = r
 439     r     = id
 440           | r ^"*" `r
 441           | `r ^"+" r
 442           | "(" r ")"
 443     id::  = [a-z]++
 444 }
 445
 446 testcase "epsilon as a positive conjunct" {
 447     input "abababab";
 448     s:: = X*
 449     X:: = "a" ("b"+ & ())
 450 }
 451
 452 testcase "epsilon as a negative conjunct" {
 453     input "aaaaa";
 454     s:: = X*
 455     X:: = "a" ("b"* &~ ())
 456 }