Prevent stack overflows during parsing caused by recursive implementation by using trampolines

[jvdb]

Because Metal is implemented with as little mutable state as possible, many functionality is implemented using recursion. Since the JVM does not currently implement tail call elimination, this regularly leads to stack overflows.

The goal is to prevent these stack overflows by letting the recursive functions use trampolines. This is a mechanism that encodes the next recursive step into a method (typically using a lambda expression) that can be popped off the stack and executed. As a result, this allows a recursive style of programming without the stack overflow issue.

Recursion is used extensively in Metal. The first step (and goal of this issue) is to reimplement all recursive code using trampolines that can get executed during parsing. So this includes:

Tokens:

• Rep
• RepN
• Seq
• Cho
• While
• Sub, which delegates to ByOffset.hasRootAtOffset()
• Tie
• TokenRef (tree processing, see below)

ValueExpressions:

• NameRef, which delegates to ByName.getAllValues() and Wrapping.wrap()
• TokenRef, which delegates to ByToken.getAllValues() and Wrapping.wrap()
• First
• Nth, which uses Reversal.reverse()
• Reverse, which delegates to Reversal.reverse()
• Fold
• Expand, which delegates to ImmutableList.add(ImmutableList)
• BinaryValueExpression
• UnaryValueExpression
• Expand
• Elvis

Expressions:

• ComparisonExpression

Data structures:

• ImmutableList<T> (createFromArray() method and add(ImmutableList) method, latter does tree processing, see below)
• DataExpressionSource (getValueAtIndex() method)
• Callbacks (handleCallbacks() method, note: it's void)

The remaining recursive code should also use trampolines (or be moved). This is addressed in #166.

Also to consider is recursion in four methods that are used a lot and a not prone to recursing extensively: ParseGraph's add(ParseValue), add(ParseReference), addBranch() and closeBranch(). This is discussed in #173.

One issue to consider is whether the Trampoline.next() method should throw an IOException. This is required by all Token implementations (except TokenRef) because Token.parse() throws it. It is unnecessary for the others. Possible solutions appear to be either wrapping the IOException (ugly) or creating two trampoline interfaces (duplication). Currently the latter is used: there are now Trampoline and SafeTrampoline, where the former's next() and computeResult() methods may throw an IOException.

Some methods are difficult to implement using only tail call recursion because they process a tree and handle both head and tail cases recursively, of which then only one is in the tail call. Converting these to trampolines as is can still result in stack overflows in some cases, so they need to be rewritten to tail call recursion. Below is a list of these cases as encountered during conversion:

• ByOffset.getLowestOffsetValue()
• ByName.getAllValues()
• ByToken.getAllValues()
• ImmutableList.add(ImmutableList)
• TokenRef.lookup()
• ParseGraph.current()
• ByToken.getAllRoots()