lezer-parser/lezer

Infinite loop in recovery

backmask opened this issue · 4 comments

backmask commented

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:

Steps to reproduce

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 commented

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 #14 to consider more robust approaches in the future.

backmask commented

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 (backmask/lezer-repro@913df5e) with the minimal change to the grammar to reproduce the issue.

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

marijnh commented

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 commented

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