[Performance improvement] Backtracking does a lot of unnecessary work

[matthew-dean]

So, I recognize that backtracking is warned against in the Chevrotain documentation, and the idea is to avoid it at all costs. But, despite my best efforts, Less and Sass have completely ambiguous rule starts and backtracking seems necessary.

While debugging my parser, I kept seeing calls to my custom error message provider during backtracking. I guess I had a naïve assumption that backtracking only inspected tokens and that was it. Like a sophisticated lookahead.

What I was surprised to find was that backtracking was doing an incredible amount of cloning of stacks and state, creating CSTs (that are never used?), and even going so far as to build error messages that are never thrown. Combined with the fact I was using chevrotain-allstar, which has poor performance when building error messages, I realized that backtracking + chevrotain-allstar wouldn't work at all.

My question is: why isn't backtracking only attempting to consume tokens, and then resetting the current index? Why does it need to build CSTs, clone errors, clone other stacks, build error messages, only to toss all that work away? It seems like backtracking would be a lot faster if all it did was just inspect the rule (the rule's tokens and subrules' tokens) to see if they match the current upcoming tokens. No?

I updated my fork of Chevrotain and have been attempting to get the backtracking rule invocation to skip certain steps that will just be thrown away anyway when backtracking finishes, but I keep running into an issue where state is saved somewhere during backtracking (looks like the lookAheadFuncsCache) and then is not retrievable if steps are skipped. I'll keep making attempts, but I thought I would post this as an issue in case you have thoughts about how to make this performant. Oop, I just needed to be running pnpm compile:watch in the root.

[matthew-dean]

I've made a PR #1983 which skips building error messages and returns earlier from a backtracking failure.