// nested direct left recursion test
ometa NestedDirectLR {
  top  = a:va       -> ['<top>', va],
  a    = a:va 'a'   -> ['<a.1>', va, 'a']
       | c:vc 'a'   -> ['<a.2>', vc, 'a'],
  c    = c:vc 'c'   -> ['<c.1>', vc, 'c']
       | 'c'        -> ['<c.2>', 'c']
}

//test::
NestedDirectLR.matchAll('ccaa', 'top')
 [<top>, [<a.1>, [<a.2>, [<c.1>, [<c.2>, c], c], a], a]]





// silly grammar to test backtracking and priorities
ometa Silly {
  top  = a:va b:vb    -> ['<top>', va, vb],
  a    = 'a'          -> ['<a>', 'a'],
  b    = 'b'          -> ['<b.1>', 'b']
       | 'b' 'b'      -> ['<b.2>', "bb"]
}

// good, obvious
Silly.matchAll('ab', 'top')
 [<top>, [<a>, a], [<b.1>, b]]

Silly.matchAll('abb', 'top')
 [<top>, [<a>, a], [<b.1>, b]]



// silly grammar to test backtracking and priorities
ometa Silly2 {
  top  = a:va b:vb    -> ['<top>', va, vb],
  a    = 'a'          -> ['<a>', 'a'],
  b    = 'b' 'b'      -> ['<b.1>', "bb"]
       | 'b'          -> ['<b.2>', 'b']
}

// good, obvious
Silly2.matchAll('ab', 'top')
 [<top>, [<a>, a], [<b.2>, b]]

Silly2.matchAll('abb', 'top')
 [<top>, [<a>, a], [<b.1>, bb]]



// test backtracking and left recursion: backtracking at the end of recursion
ometa BacktrackLR1 {
  top  = a:va b:vb    -> ['<top>', va, vb],
  a    = a:v1 'a' 'a' -> ['<a.1>', v1, "aa"]
       | a:v2 'a'     -> ['<a.2>', v2, 'a']
       | 'a' 'a'      -> ['<a.3>', "aa"],
  b    = 'a' 'b'      -> ['<b>', "ab"]
}

//BAD: match fails because applications of rule a consume all of 'a's in input string
BacktrackLR1.matchAll('aaab', 'top')
<FAIL>






// test backtracking and left recursion
ometa BacktrackLR2 {
  top  = a:va b:vb    -> ['<top>', va, vb],
  a    = a:v1 'a' 'a' -> ['<a.1>', v1, "aa"]
       | a:v2 'a'     -> ['<a.2>', v2, 'a']
       | 'a' 'c'      -> ['<a.3>', "ac"],
  b    = 'a' 'b'      -> ['<b>', "ab"]
}

//BAD: Again, this fails.  I suppose it's because rule <a.2> matches somehow?
BacktrackLR2.matchAll('acab', 'top')
<FAIL>






////  OLD:: based on assumption that OMeta backtracks to consume entire string ////

// quick grammar to play around with direct left recursion
ometa DirectLR {
  top  = a:va b:vb    -> ['<top>', va, vb],
  a    = a:v1 'a'     -> ['<a.1>', v1]
       | a:v2 'a' 'b' -> ['<a.2>', v2]
       | 'a'          -> ['<a.3>', 'a'],
  b    = 'b'          -> ['<b>', 'b']
}

//BAD: this "match" does not cover the end of the string.  Also, it should use 
// the second choice '<a.2>' for the second node
DirectLR.matchAll('aabb', 'top')
 [<top>, [<a.1>, [<a.3>, a]], [<b>, b]]





// variation on last grammar to illustrate shortcomings in left recursion handling
ometa DirectLR2 {
  top  = a:va b:vb  -> ['<top>', va, vb],
  a    = a:v1 'a'   -> ['<a.1>', v1]
       | 'ab'       -> ['<a.2>', 'ab']
       | 'a'        -> ['<a.3>', 'a'],
  b    = 'b'        -> ['<b>', 'b']
}

//BAD: again, the string is only partially matched
DirectLR2.matchAll('aabb', 'top')
 [<top>, [<a.1>, [<a.3>, a]], [<b>, b]]

//BAD: am I doing something wrong so the last character is being ignored?
DirectLR2.matchAll('abb', 'top')
 [<top>, [<a.3>, a], [<b>, b]]






//NOTE: I just found http://vpri.org/pipermail/ometa/2008-June/000006.html which 
// disclaims support of indirect left recursion in OMeta.  So the failures below 
// are moot.

// quick grammar to play around with indirect left recursion
ometa MultiChoiceLR {
  top      = ad:v       -> ['<top>', v],
  a        = ab:vab     -> ['<a>', vab]
           | ac:vac     -> ['<a>', vac]
           | ad:vad     -> ['<a>', vad],
  ab       = a:va 'b'   -> ['<ab>', va, 'b']
           | 'b'        -> ['<ab>', 'b'],
  ac       = a:v1 'c'   -> ['<ac>', v1, 'c']
           | a:v2 'cb'  -> ['<ac>', v2, 'bc']
           | 'c'        -> ['<ac>', 'c'],
  ad       = a:va 'd'   -> ['<ad>', va, 'd']
}

//BAD: this match fails -- it needs to backtrack and reevaluate rule <a> without the 
// cached result for <ab> (which is not in the parse stack for the seed trace).  Also
// note that I think the result should be 
//   [<top>, [<ad>, [<a>, [<ab>, [<a>, [<ac>, c]], b]], d]]
// i.e. it should use the higher-precedence rule for <ab> instead of a single 
// application of <ac> which would give
//   [<top>, [<ad>, [<a>, [<ac>, cb]], d]]
MultiChoiceLR.matchAll('cbd', 'top')


//BAD: this match fails, though I think it should be
//   [<top>, [<ad>, [<a>, [<ac>, [<a>, [<ac>, cb]], c]], d]]
MultiChoiceLR.matchAll('cbcd', 'top')


//GOOD: this one looks good
MultiChoiceLR.matchAll('bd', 'top')
 [<top>, [<ad>, [<a>, [<ab>, b]], d]]

//BAD: this one should have a few extra applications of rule <ad>, right?
MultiChoiceLR.matchAll('bddd', 'top')
 [<top>, [<ad>, [<a>, [<ab>, b]], d]]

//BAD: still missing an application of rule <ad>
MultiChoiceLR.matchAll('cdd', 'top')
 [<top>, [<ad>, [<a>, [<ac>, c]], d]]

//BAD: match fails, likely same problem as the first example
MultiChoiceLR.matchAll('cbbcbbd', 'top')