Repository: pest-parser/pest (language: rust)

Issue:
Bug: Non-matching rule changes parsing result
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:

```diff
--- 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:

```rst
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:

```js
[
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) ]),
        ]),
    ]),
]),
]
```


Discussion / hints:
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.
Also, really nice minimal example! 👍 
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.
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.
OK! If you’re on it, that’s great.

Unrelatedly: Do you have comment to the PEEK[..] PR? I wrote some things [here](https://github.com/pest-parser/pest/pull/334#discussion_r232497932) but never got an answer
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!
OK, great! Sorry for being pushy :sweat_smile: 
No worries! Really excited to see rST grammar ready. Your project seems to be the most comprehensive use of pest grammars until now!
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`](https://github.com/pest-parser/pest/blob/addfff2345f84b35e4ec7924354fc3feda47b589/generator/src/generator.rs#L460), 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:

```pest
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.
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.

Fix patch:
diff --git a/meta/src/optimizer/restorer.rs b/meta/src/optimizer/restorer.rs
index f606b79f..2faf8f8b 100644
--- a/meta/src/optimizer/restorer.rs
+++ b/meta/src/optimizer/restorer.rs
@@ -66,6 +66,7 @@ fn child_modifies_state(
 ) -> bool {
     expr.iter_top_down().any(|expr| match expr {
         OptimizedExpr::Push(_) => true,
+        OptimizedExpr::Ident(ref name) if name == "DROP" => true,
         OptimizedExpr::Ident(ref name) if name == "POP" => true,
         OptimizedExpr::Ident(ref name) => {
             match cache.get(name).cloned() {
diff --git a/pest/src/stack.rs b/pest/src/stack.rs
index e4010be0..36cde86d 100644
--- a/pest/src/stack.rs
+++ b/pest/src/stack.rs
@@ -59,11 +59,7 @@ impl<T: Clone> Stack<T> {
 
     /// Takes a snapshot of the current `Stack`.
     pub fn snapshot(&mut self) {
-        let ops_index = self.ops.len();
-
-        if ops_index > self.most_recent_snap() {
-            self.snapshots.push(ops_index);
-        }
+        self.snapshots.push(self.ops.len());
     }
 
     /// Rewinds the `Stack` to the most recent `snapshot()`. If no `snapshot()` has been taken, this
@@ -95,10 +91,6 @@ impl<T: Clone> Stack<T> {
             }
         }
     }
-
-    fn most_recent_snap(&self) -> usize {
-        *self.snapshots.last().unwrap_or(&0)
-    }
 }
 
 #[derive(Debug)]
@@ -124,6 +116,20 @@ mod test {
         assert!(stack.is_empty());
     }
 
+    #[test]
+    fn snapshot_twice() {
+        let mut stack = Stack::new();
+
+        stack.push(0);
+
+        stack.snapshot();
+        stack.snapshot();
+        stack.restore();
+        stack.restore();
+
+        assert_eq!(stack.iter().collect::<Vec<&i32>>(), vec![&0]);
+    }
+
     #[test]
     fn iter() {
         let mut stack = Stack::new();


Test patch:
diff --git a/derive/tests/grammar.pest b/derive/tests/grammar.pest
index 404f33fd..5155b373 100644
--- a/derive/tests/grammar.pest
+++ b/derive/tests/grammar.pest
@@ -41,7 +41,9 @@ peek_all = { PUSH(range) ~ PUSH(range) ~ PEEK_ALL }
 pop_ = { PUSH(range) ~ PUSH(range) ~ POP ~ POP }
 pop_all = { PUSH(range) ~ PUSH(range) ~ POP_ALL }
 pop_fail = { PUSH(range) ~ !POP ~ range ~ POP }
-checkpoint_restore = ${ PUSH("") ~ (PUSH("a") ~ "b" ~ POP | POP ~ "a") ~ EOI }
+checkpoint_restore = ${
+		PUSH("") ~ (PUSH("a") ~ "b" ~ POP | DROP ~ "b" | POP ~ "a") ~ EOI
+}
 ascii_digits = { ASCII_DIGIT+ }
 ascii_nonzero_digits = { ASCII_NONZERO_DIGIT+ }
 ascii_bin_digits = { ASCII_BIN_DIGIT+ }