ValueStack not properly reset during application of "reduction rules"

[sirthias]

When a rule transforms the value stack (rather than simply pushing values onto it) then these transformations are not always rolled back (as one would expect) when an optional or repetition rules fails further up in the rule structure.

The tests added with the referenced commit below demonstrate the problem.

Due to the mutable nature of the value stack (which is mutable in order to avoid an allocation with every push) fixing this problem is not entirely trivial. Switching to an immutable stack implementation would provide an easy, immediate solution but come with a quite severe performance penalty.

One way could be to switch to a hybrid mutable/immutable value stack implementation, which mutates in place for the large majority of cases and only allocates when optional, zeroOrMore or oneOrMore is applied to rules that actually consume values (i.e. whose I type parameter is not HNil).

Another solution would be to completely disallow reduction rules for optional, zeroOrMore or oneOrMore combinators, which would be an unfortunate restriction, since they can be quite handy in many cases.

[ljleb]

@sirthias Could we allocate one single temporary value on top of the ValueStack per reduction rule run, which would be used to store temporary results generated by reduction rules?

For a given a reduction rule R: if R matches, then the real value on top of the ValueStack is overwritten by the value from the temporary slot (that was generated by R); if R fails, the temporary value on top of the ValueStack is simply discarded and the rule following R is handled. It might not be required for that temporary var to be pushed on top of the ValueStack.