Too eager cycle without backtracking

[hanickadot]

(a|ab)+ won't match ab

Found a fix, it's in branch fix-for-cycles, created tests to trigger this error, but it's a big performance regression because compiler can't see thru and optimise deep recursion.

[Andersama]

This also happens for (a|ab){1,1} but does not for (a|ab), for ordinary cases where select isn't repeated there's not much need to keep track too much state, where the branch occurred and what the last branch taken was is sufficient. If we're in a repeating section you'll have to keep track of that state for every step (which means I guess you'll be allocating) in order to unwind and try a different path.

I guess the upside is since this doesn't work properly you're safe from some really awful backtracking. With how this implementation works you could call this a fuzzy match/search/starts_with...there are no false positives, but may be some false negatives.

The pattern / issue holds for all (a|ab){N,N}* manually writing it out will work properly, having it written with the repeat syntax breaks.

[Andersama]

Started thinking about this a bit more. Another way to consider this is that the current implementation is ok if sequence<<repeat<select<Options...>> Tail...> 's branches not only don't collide with Tail... but also don't collide with themselves. Unfortunately #94 / #166 Unrolling a selection wrapped by a repeat won't work here because they require a distinct branch. Which (a|ab)+ does not have.

It also gets worse, any select<> buried inside a repeat creates this issue sequence<<repeat<A...,select<Options...>,B...> Tail...>. Is equivalent to repeat<select<Options....>>,Tail...> given a bit of rewriting.