Infinite loop in recovery

[backmask]

Hello,

Lezer will sometimes stall during its recovery phase at https://github.com/lezer-parser/lr/blob/main/src/stack.ts#L119 (while (this.stack.length > base) this.stack.pop()) because base was previously resolved to a negative value.

Setup

The following repo should contain everything needed to reproduce the issue: https://github.com/backmask/lezer-repro

The grammar itself is a bit complex (https://github.com/backmask/lezer-repro/blob/master/src/lezer.grammar), I tried to simplify it as much as possible but it appears that having a quite ambiguous grammar is necessary to reproduce the issue. The input itself was shrunk to 0:(,0.

The repo contains two patches:

• https://github.com/backmask/lezer-repro/blob/master/patches/%40lezer%2Bgenerator%2B0.15.1.patch to apply the latest fix on @lezer/generator
• https://github.com/backmask/lezer-repro/blob/master/patches/%40lezer%2Blr%2B0.15.2.patch to avoid entering into the infinite loop

Steps to reproduce

• Checkout https://github.com/backmask/lezer-repro
• Run

  npm i
  npm run generate
  npm run test

The output should be

1) Lezer bug repro
       should not resolve a negative base:
     Error: Negative base, the code will stall
      at Stack.reduce (file:///C:/Dev/lezer-repro/node_modules/@lezer/lr/dist/index.js:126:19)
      at Stack.forceReduce (file:///C:/Dev/lezer-repro/node_modules/@lezer/lr/dist/index.js:308:14)
      at Parse.runRecovery (file:///C:/Dev/lezer-repro/node_modules/@lezer/lr/dist/index.js:1221:35)

[marijnh]

Thanks for setting up a reproduction! That was very helpful. This uncovered a fundamental unsoundness in the way forced stack reductions are implemented. Attached patch adds a check to avoid the issue (the problem was introduced a few reductions before the one that actually crashed). I've opened https://github.com/lezer-parser/lezer/issues/14 to consider more robust approaches in the future.

[backmask]

Woah thanks for the quick fix @marijnh ! It appears that there are some cases where we can still get a negative base. I updated the reproduction repo (https://github.com/backmask/lezer-repro/commit/913df5ea442f8297da5693c0d77eb6e751eb2032) with the minimal change to the grammar to reproduce the issue.

Let me know if I should create a new issue :)

[marijnh]

My bad, I mixed up the meaning of a boolean argument and only solved the case where the forced reduction directly goes past the base of the stack. Attached patch (0.15.4) should make it properly check for validity on every forced reduction.

[backmask]

I confirm that 0.15.4 does fix my issue, thanks a lot!