Bug: Non-matching rule changes parsing result

[flying-sheep]

I created a test repo: https://github.com/flying-sheep/pest-bug

It contains two almost identical grammars and a test for each that checks if the parse tree matches my expectations. One of them doesn’t, while it really should. Check out the two grammars: They only differ in that one I use title = {a|b}; block = {title|…} and in the other I use block = {a|b|…}. The two grammars should function exactly equal!

It may be a problem with stack checkpoints but I’m not sure… pest grammars aren’t very debuggable.

If none of you can find out what’s wrong: How can I debug this?

---

This is the difference between the grammars:

--- src/title-one-rule.pest     2018-11-14 23:20:03.477000000 +0100
+++ src/title-two-rules.pest    2018-11-14 23:20:12.106000000 +0100
@@ -2,7 +2,7 @@
 blocks   = _{ block ~ (blank_line+ ~ block)* }
 block    = _{ PEEK[..] ~ hanging_block }
 hanging_block = _{
-    title |
+    (title_both | title_underline) |
     bullet_list |
     paragraph
 }

This is the document I parse:

paragraph

-  item 1
-  item 2
   more text
   more text 2
   more text 3
   - nested item 1
   - nested item 2
   - nested item 3

this is the parse tree I expect:

[
paragraph(0, 10, [ line(0, 10) ]),
bullet_list(11, 131, [
    bullet_item(11, 21, [ line(14, 21) ]),
    bullet_item(21, 131, [
        line(24, 31),
        paragraph(34, 74, [
            line(34, 44),
            line(47, 59),
            line(62, 74),
        ]),
        bullet_list(77, 131, [
            bullet_item(77, 93, [ line(79, 93) ]),
            bullet_item(96, 112, [ line(98, 112) ]),
            bullet_item(115, 131, [ line(117, 131) ]),
        ]),
    ]),
]),
]

[dragostis]

Looking into this right now. There is a debugger PR #277, but it would need to be rebased in order to work with your branch of pest.

[dragostis]

Also, really nice minimal example! 👍

[dragostis]

The difference is the content of the stack. In title_two_rules every time you peek, the stack contains:

stack: ["   "]
stack: ["   "]
stack: ["   "]
stack: ["   "]
stack: ["   "]
stack: ["   "]
stack: ["   "]
stack: ["   "]
stack: ["   "]
stack: ["   "]
stack: ["   "]
stack: ["   "]

while in title_one_rule:

stack: ["   "]
stack: ["  "]
stack: ["  "]
stack: ["  "]
stack: ["  "]
stack: ["  "]
stack: ["  "]
stack: ["  "]

Haven't yet figured out why this happens, though. On it.

[dragostis]

I have one non-related bug: restoration doesn't take DROP into consideration, only POP. Fix is super easy.

The issue here seems to be cause by the stack being restored to an earlier state than it should be.

[flying-sheep]

OK! If you’re on it, that’s great.

Unrelatedly: Do you have comment to the PEEK[..] PR? I wrote some things here but never got an answer

[dragostis]

I read your comments but was a bit caught up the last few days. I'll get right to that once we figure out what the issue here is!

[flying-sheep]

OK, great! Sorry for being pushy 😅

[dragostis]

No worries! Really excited to see rST grammar ready. Your project seems to be the most comprehensive use of pest grammars until now!

[dragostis]

This bug is pretty hard to figure out. When you wrap it up in an extra title rule, the title call gets wrapped up in a RestoreOnErr, but so does title_both and it seems like the outer one is malfunctioning. The inner one calls Stack::rewind_to with index 5 which is correct, but the outer one calls it with index 3 which is not. In the other example this does not happen because the outer restore does not exist. The issue here is that I can't figure out why the index is 3 instead of one. I tried to reproduce this in a smaller example, but was unable to.

Update: It seems like actually bullet_list's restore is causing the issue. I've also managed to get a minimally reproducible case:

top = { PUSH("hi") ~ (a | POP) }

a = { b | "boo" }
b = { PUSH("a") ~ POP }

Redefining a = { b } makes it work for the input "hihi", while this doesn't work in its current form. This also seems to break the playground because it's running POP on an empty stack.

[dragostis]

Found the bug. Damn, this was quite hard to debug, but the issue is pretty clear. Will write a PR once I know for sure that the fix is correct.

[flying-sheep]

Great news, thank you very much! Maybe you should also mention what made debugging hard while the memory is fresh.

It might help to improve the debugging story down the line.

[dragostis]

The issue was simply the complexity of the grammar and the fact that Rust debugging is very immature. I it was really hard to read bracktraces provided by rust-lldb. I think we should take a stab at rewriting stack-related code before 3.0 and make sure its fine-tuned for good performance, but this will have to wait until I write my thoughts on the IR optimizer.