Parser run-time error with nested application of right-nullable production rules

[jurgenvinju]

Describe the bug

import IO;

layout WS = [\ \t\r\n]* !>> [\ \t\r\n];

start syntax Stmt
    = "if" "(" Expr ")" Stmt () !>> "else"
    | "if" "(" Expr ")" Stmt "else" Stmt
    | "{" "}"
    ;

syntax Expr = "x";

public str example =    "if (x) 
                        '   if (x)
                        '       if (x) 
                        '           {}";

void main() {
    print([start[Stmt]] example);
}

This gives a parse error, so when the else branch is not there it does not parse. If you add the else branch to the example, then a parse tree is produced.

• This bug must have been introduced recently, because the Rascal grammar has the same feature and that still works.
• This also indicates that the bug is in the parser generator and not in the parser run-time, since the new parser and the Rascal parser share the same run-time environment
• We added code for case insensitive literatal follow and precede restrictions and requirements in September 2020. That code is very near to the currently failing example.

[jurgenvinju]

@tvdstorm thanks for reporting.

[jurgenvinju]

• if we remove the follow restriction, then the bug is not triggered

[jurgenvinju]

• if we remove the follow restriction, but keep the () symbol, we get the same parse error.

[jurgenvinju]

• if we add the follow restriction, and remove the () symbol, we get a perfect parse tree

And so the bug is related to the empty symbol and how it is processed.

[jurgenvinju]

• replacing () with "" has no effect

[jurgenvinju]

simplified test module: needs two if's nested to trigger the bug, no less. more is same.

import IO;

layout WS = [\ \t\r\n]* ;

import ParseTree;

start syntax Stmt
    = "if" "(" Expr ")" Stmt ""
    | "{" "}"
    ;

syntax Expr = "x";

public str example =    "if (x) 
                        '   if (x)
                        '       {}";

void main() {
    print(parse(#start[Stmt], example, |example:///|, allowAmbiguity=true));
}

[jurgenvinju]

• there are subtle differences between "" and () nevertheless. don't understand yet
• no follow restrictions in layout present either, still parse errors.
• hypothesis: something goes wrong with layout intermix?

[tvdstorm]

One subtlety that comes to mind: there are two consecutive empties in the example with the parse error.

[tvdstorm]

There's also a difference in behavior depending on trailing white space or not:

module NestedIfs

import ParseTree;
import IO;

layout Layout = [\ \t\n]* !>> [\ \t\n];

start syntax Stmt
    = "if" "(" "x" ")" Stmt "else" Stmt
    | "if" "(" "x" ")" Stmt () !>> "else"
    | "{" "}"
    ;

str bug1 = "if (x) if (x) if (x) {}";

str bug2 = "if (x) if (x) if (x) {} ";

void triggerBug() {
    void doit(str src) {
        try {
            println("Parsing: `<src>`");
            parse(#Stmt, src);
        }
        catch value e: {
            println(e);
        }

    }

    println("### BUG1 (no trailing whitespace)");
    doit(bug1); // parse error
    doit(bug1[7..]); // parse error
    doit(bug1[14..]); // ok

    println("\n### BUG2 (trailing whitespace)");
    doit(bug2); // parse error
    doit(bug2[7..]); // ok
    doit(bug2[14..]); // ok

}

[PaulKlint]

It would be very helpful to convert these examples to tests that we can include in our test suite.

[tvdstorm]

See: 322750d86007f108c6021aff7790d5e099b0a6b9

[jurgenvinju]

Mmm yes but that is probably caused by not using the start nonterminal..

-- Jurgen Vinju http://jurgen.vinju.org CWI SWAT TU Eindhoven Swat.engineering BV

[tvdstorm]

No, it isn't: the follow restriction on layout eats layout until the ().

[jurgenvinju]

Mmm.. It should also eat the layout beyond the ()

On Fri, 3 Dec 2021 at 17:44, Tijs van der Storm @.***> wrote:

No, it isn't: the follow restriction on layout eats layout until the ().

— You are receiving this because you were assigned. Reply to this email directly, view it on GitHub https://github.com/usethesource/rascal/issues/1542#issuecomment-985668127, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAPF5F4XGMVTBQWNQTLTAZ3UPDXYFANCNFSM5JHDHSZA . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

-- Jurgen Vinju http://jurgen.vinju.org CWI SWAT TU Eindhoven Swat.engineering BV

[tvdstorm]

but there isn't, because of the follow restriction on layout.

[jurgenvinju]

The bug has nothing to do with follow restrictions. Or in other words: there are more relevant test cases. The DanglingElse example is complex and definitely needs to be added to the test set. However, that example is too big to debug.

Here is a version that triggers the bug without follow restrictions:

module Tijs

import IO;

layout WS = [\ \t\r\n]* ;

import ParseTree;

start syntax Stmt
    = "if" "(" Expr ")" Stmt ()
    | "if" "(" Expr ")" Stmt "else" Stmt
    | "{" "}"
    ;

syntax Expr = "x";

public str example =    "if (x) 
                        '   if (x)
                        '       {}";

void main() {
    print(parse(#start[Stmt], example, |example:///|, allowAmbiguity=true));
}

• Simply removing the () resolves the bug, and no more parse errors seem present.
• if we close the rule with a "fi" before the () the bug also dissappears
• so we have an hypothesis that something goes wrong with "right nullable" rules, namely rules that end with a nullable non-terminal.

It is baffling we discover this bug now, since the Rascal grammar itself has such a rule:

ifThen: Label label "if" "(" {Expression ","}+ conditions ")" Statement!variableDeclaration!functionDeclaration thenStatement () !>> "else"  

[jurgenvinju]

@arnoldlankamp two bugs in one day. still digging on this bug; but it's nice to remember all the good things you wrote :-) If you have a hunch, I'd appreciate it.

[jurgenvinju]

If we add a bogus constraint to the previous non-terminal before the (), then the bug dissappears!

module Tijs

import IO;

layout WS = [\ \t\r\n]* ;

import ParseTree;

start syntax Stmt
    = "if" "(" Expr ")" Stmt!bla ()
    | "if" "(" Expr ")" Stmt "else" Stmt
    | "{" "}"
    | bla: "bla"
    ;

syntax Expr = "x";

public str example =    "if (x) 
                        '   if (x)
                        '       {}";

void main() {
    print(parse(#start[Stmt], example, |example:///|, allowAmbiguity=true));
}

@tvdstorm here's a workaround for the bug for you, for short term success.

[jurgenvinju]

This also explains why the Rascal grammar was not bothered by this bug, and this makes it possible that this particular bug has always been there.

[jurgenvinju]

It is also a possible hint for resolving the issue, since the code path that is triggered by having constraints on the non-terminal before the right-nullable one does not have the bug.

[jurgenvinju]

it does not matter which filter is put on the Stmt symbol before the () (follow restriction, exclude, reserve, any condition is enough to "fix" the issue.

[arnoldlankamp]

This issue looks similar to #1543 . Maybe the proposed fix for that one will also resolve this one. If it doesn't let me know and I'll have another look.

[jurgenvinju]

thanks @arnoldlankamp ; I'll try that tomorrow.

[arnoldlankamp]

This issue likely has something to do with the prefix sharing optimization, in combination with right nullables. If you add the same restriction to the Stmt in both the rule with and without the else clause, you likely get the parse error back.

I'd expect using this piece of grammar produces the same parse error as the original example:

start syntax Stmt
    = "if" "(" Expr ")" Stmt!bla ()
    | "if" "(" Expr ")" Stmt!bla "else" Stmt
    | "{" "}"
    | bla: "bla"
    ;

[jurgenvinju]

Yes; you are correct. If the prefix is the same again, the parse error comes back.

[jurgenvinju]

I have my eyes on this line:

https://github.com/usethesource/rascal/blob/bb72c03cc9b4004c42879c973e7b7f31e3b23f1f/src/org/rascalmpl/parser/gtd/stack/AbstractStackNode.java#L683

With consecutive nullables such as layout empty layout, would this not abort too early?

[jurgenvinju]

@tvdstorm shall we put the failing DanglingElse test to @ignore while we try to fix this? Because now the other developments on the main branch are invisible until we fix the current bug.

[arnoldlankamp]

With consecutive nullables such as layout empty layout, would this not abort too early?

This line is there to keep track of what we've already processed, to prevent duplicate results.

It's a bit hard to explain without a whiteboard unfortunately. This whole hidden-right-recursion thing is a bit tricky 😅 .

[jurgenvinju]

This was my thinking:

• it seems we identify propagatedIndexes by the input position only.
• and, the input position does not shift if we process a nullable;
• but we do label that position as propagated
• and we have the next nullable still to propagate, but we won't do that because the input position is already stored in propagatedIndexes

Definitely tricky stuff, but should we not mark the processed position by a input position + rule position key here?

[arnoldlankamp]

Definitely tricky stuff, but should we not mark the processed position by a input position + rule position key here?

The instance of the AbstractStackNode represents the rule position.

But I guess we may be dealing with the same issue as #1543 .

If we look at (line 666 of all places): https://github.com/usethesource/rascal/blob/bb72c03cc9b4004c42879c973e7b7f31e3b23f1f/src/org/rascalmpl/parser/gtd/stack/AbstractStackNode.java#L666 . We see the same fromIndex optimization. If we replace that one by for(int i = edgesMapToAdd.size() - 1; i >= 0; --i){ as well, it may resolve the issue.

[jurgenvinju]

Thanks @arnoldlankamp; I'll look into that. Meanwhile I've been producing test cases to trigger all these issues, with some unexpected results so it may take a while to close this issue even if you've solved it. hold on...

[jurgenvinju]

Ok; the fix on line 666 does not break the parser runtime, but it also does not fix the current bug...

• leave this fix and continue, assuming we may have a stacked problem and we've now popped the first issue of the stack?
• or unfix this because it may make the parser a bit slower and we don't know if it is related to the issue at all?
• or there is third alternative unknown to me...

[jurgenvinju]

More tomorrow. I have a X-mas tree to set up now and cook some food for the children :-)

[jurgenvinju]

The problem with the test cases was that I accidentally reverted line 666 instead of 587 to trigger the other bug :-) since the code looked so similar I was misreading it for the wrong location. So that mystery is solved now. I can trigger these bugs in a reproducible manner.

[arnoldlankamp]

The test cases would be very interesting too look at.

Also, I'm wondering what happens if we introduce a level of indirection by adding another start symbol 🤔 . E.g.: start syntax Root = Stmt.

[arnoldlankamp]

It may be tripping up over the empty at the end, in combination with the empty layout before it; for which the AbstractStackNode instances are both shared between the first and second match of in the "if" "(" Expr ")" Stmt "" construction, since the empty and empty layout have the same start and end location in both occurrences. Their prefix has a different start location however and should be propagated all the way to the end. Maybe it's not doing so for some reason 🤔 ?

I think we can also reduce the test case to: S := "x" S "" "" | "y", with xxy as input and still trigger the error. The smaller the test, the easier it is to debug 😉 .

[arnoldlankamp]

Just to clarify visually:

if L (x) L 
  if L (x) L
    {}
  L ""  <-- (1) Same input location
L ""    <-- (2) as these two

What should happen is the following:

• L and "" (1) are matched first (prefix starts at second if)
• L (2) shares its location with L (1) but has a different prefix start location (first if), so it should be added as prefix and be propagated to "" (2)
• "" (2) shares its location with "" (1), but since it receives a prefix with a different start location (first if), it should reduce it (since it's the last item in the production) and complete the parse.

[jurgenvinju]

Ok @arnoldlankamp here's a simplified example which still exhibits the bug. I'll turn this into a test case today:

lexical Stmt
    = "i" Stmt () ()                 // if rule
    | "i" Stmt () "e" Stmt      // else rule
    | "!"                                  // bang
    ;
public str example = "ii!";

• removed layout from the example, but to trigger the bug I need to introduce an additional nullable in the if rule, and in the else rule to simulate the effect that layout used to have (the original layout rule was nullable))
• shortened the "if" and "else" keywords: no effect
• removed nesting in the example input "i!": this produces a parse tree instead of an error, so reverted that
• removed the else rule entirely: this produces a parse tree instead of an error, so reverted that
• added a terminator after the "() ()"; this produces a parse tree instead of an error, so reverted that
• changed the Stmt symbol in the if rule (added a constraint): this produces a parse tree instead of an error, so reverted that. This confirms the same bug is still represented by the current parse error.

So to trigger this particular bug:

• consecutive nullables are essential
• nesting is essential in the input
• shared prefixes are essential
• right-nullability is essential

[jurgenvinju]

See test/org/rascalmpl/test/parser/DoubleRightNullableWithPrefixSharing.java. It has a main method which triggers the bug

[arnoldlankamp]

Interestingly, the prefixes don't seem to be shared between the if and if else alternatives. The generated stack nodes have different ids. These two (43 and 49): https://github.com/usethesource/rascal/blob/9d1a82bd87a256d5b56c834b17cb7c1bbfa94fe3/test/org/rascalmpl/test/parser/DoubleRightNullableWithPrefixSharing.java#L78 https://github.com/usethesource/rascal/blob/9d1a82bd87a256d5b56c834b17cb7c1bbfa94fe3/test/org/rascalmpl/test/parser/DoubleRightNullableWithPrefixSharing.java#L87

[arnoldlankamp]

When I have some time I'll make a checkout of the project and step through it with a debugger to see what's happening.

[jurgenvinju]

Ok. mmmm.. maybe one of the alternatives is reducing too early? before it can be propagated?

The id's were generated from the grammar positions. So every symbol position in every rule gets a unique id. Maybe prefix sharing is done on different grounds than just the id.

[arnoldlankamp]

It's either not being reduced or expanded or recognized. We just need to figure out which and why 🤔 .

Shared prefixes need to be calculated in the generator in order to be picked up by the parser. The parser just looks at the id's of the stack nodes (id + start pos = unique stack node instance).

This is an example of a test that applies prefix sharing: https://github.com/usethesource/rascal/blob/9d1a82bd87a256d5b56c834b17cb7c1bbfa94fe3/test/org/rascalmpl/test/parser/AmbiguousRecursivePrefixShared.java#L54-L55

Prefix sharing is an optimization, so the parser should function correctly if you don't use them (although using them in this specific case might make the bug disappear as a side effect).

[jurgenvinju]

That is a lot of opportunity for speed that we are not using at all! That's worth it's own issue report for the parser generator.

The current issue has many similarities with an original bug in Tomita's GLR. Farshi and Rekers both fixed this by an extra search stage to find the missing reductions for hidden right nulled rules. Scott and Johnstone solved it more elegantly by reducing all right nulled rules "early" so that an additional search is not needed with their RNGLR version. Rob and I made an Scannerless and disambiguating version too. Maybe we can use this fix here too once we confirm the behavior of missing reductions?

[arnoldlankamp]

Yes, it does looks similar to the original GLR issue and the bug is most likely related to the right nullables, however the parser should be able to handle those without issue and in many examples I've tested in the past it actually does (I should have added those to the test suite back then 🤦‍♂️). The question we are left with is: why doesn't it work in this specific case 🤔 ?

The right nullable fix in this parser's algorithm is rather trivial; just propagate the missing prefixes forward and reduce if you add a prefix for a 'new' start position to the last node of the alternative. Unfortunately in the current implementation of the parser things have become a bit complicated in places due to all the optimizations. Which is probably wherein to problem lies.

The parser's algorithm itself is also fairly straightforward if you disregard all the complexity the optimizations add. It's probably easiest to imagine it as an Earley parser with a the above described RN fix, sort of.

Hopefully I'll have some time to look at it on Sunday. I'll let you know once I've found the source of the issue.

[jurgenvinju]

Thanks Arnold. The algorithm is unclear to me indeed, so your help is appreciated!

[arnoldlankamp]

That is a lot of opportunity for speed that we are not using at all! That's worth it's own issue report for the parser generator.

Ah, it seems I added a preprocessor to handle the sharing just before I left, so the generator doesn't need to calculate this.

This thing: https://github.com/usethesource/rascal/blob/master/src/org/rascalmpl/parser/gtd/preprocessing/ExpectBuilder.java .

It may even be the source of this bug 🤔 .

[arnoldlankamp]

It indeed seems to be related to prefix sharing. If I disable this functionality the DoubleRightNullableWithPrefixSharing test completes successfully.

[jurgenvinju]

Similar to removing the "else" rule indeed. The sharing is onder of the crucial factors to triggering the bug

[arnoldlankamp]

Changing this line to false resolves this issue for now: https://github.com/usethesource/rascal/blob/be4edf25e697c5ccc4f5d7ee35b5552665042897/src/org/rascalmpl/parser/gtd/preprocessing/ExpectBuilder.java#L67 .

I'll dig a little deeper to find out where it goes wrong.