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

Issue:
Breaking change between 2.1 and 2.4/2.5
**Describe the bug**

During this discussion [Implicit expression ·  #761](https://github.com/pest-parser/pest/discussions/761) I have discovered that there is a difference of behavior for the following syntax between pest 2.1 and pest 2.4/2.5, for now I don't know if it's the expected behavior or not. I open an issue to know how to decide this.

**To Reproduce**
For the following grammar:
```bash
program = _{ SOI ~ implicit ~ EOI  }
implicit= ${ or ~ (WHITESPACE+ ~ or )* }

or  = !{ and ~ (or_op ~ and)+ | and }
and = { comp ~ (and_op ~ comp)+ | comp }
comp = { array ~ eq_op ~ array | array }

array = ${ term }

term = _{ ASCII_ALPHANUMERIC+ }
or_op = { "||" }
and_op = { "&&" }
eq_op = { "=" }
WHITESPACE = _{ " " | "\t" | NEWLINE }
```


The input `a a` return this error for pest 2.4/2.5 :x: :
```bash
 --> 1:3
  |
1 | a a
  |   ^---
  |
  = expected EOI, or_op, and_op, or eq_op
```

Success for 2.1 :heavy_check_mark: 


**Expected behavior**

Run without error and return two `array`.



Discussion / hints:
It may be a side-effect of some optimization work that has been done since 2.1, e.g. https://github.com/pest-parser/pest/pull/473 ?
@vincent-herlemont I managed to reproduce it. I tried `git bisect` to find the commit where it stopped parsing and it turned out to be this one b720edcd0385d8e4965b4da06f92efd01edb33e9 from that optimization PR #473.
If my understanding is correct, that optimization will try to rewrite rules of the form `a ~ b | a` to `a ~ b?` which seems reasonable on its own, but I guess it may be problematic in some contexts due to the greedy backtracking nature of parsing here.

@SkiFire13 @dragostis @CAD97 do you have any suggestions on how to proceed here -- should that optimization be reverted, or should it stay as it is and @vincent-herlemont could rewrite that grammar in some way (I guess one dummy workaround is to introduce extra rules, so that the optimization fails to be applied), or can you see an easy way to restrict that optimization?
Transforming `a ~ b | a` to `a ~ b?` is incorrect when implicit whitespace is on, yeah. Generally the consistency/predicability of whitespace behavior is really not great.

With the implied whitespace made explicit, it's transforming

```rust
@{ a ~ WHITESPACE* ~ b | a }
// to
@{ a ~ WHITESPACE* ~ b? }
// which is incorrect, it should be
@{ a ~ (WHITESPACE* ~ b)? }
```

Probably the "correct" fix is to "desugar" all of the implicit whitespace rules before applying any optimization transformations.

Fix patch:
diff --git a/debugger/Cargo.toml b/debugger/Cargo.toml
index c79c48f6..a557d13d 100644
--- a/debugger/Cargo.toml
+++ b/debugger/Cargo.toml
@@ -1,7 +1,7 @@
 [package]
 name = "pest_debugger"
 description = "pest grammar debugger"
-version = "2.5.2"
+version = "2.5.3"
 edition = "2021"
 authors = ["Dragoș Tiselice <dragostiselice@gmail.com>", "Tomas Tauber <me@tomtau.be>"]
 homepage = "https://pest.rs/"
@@ -14,9 +14,9 @@ readme = "_README.md"
 rust-version = "1.56"
 
 [dependencies]
-pest = { path = "../pest", version = "2.5.2" }
-pest_meta = { path = "../meta", version = "2.5.2" }
-pest_vm = { path = "../vm", version = "2.5.2" }
+pest = { path = "../pest", version = "2.5.3" }
+pest_meta = { path = "../meta", version = "2.5.3" }
+pest_vm = { path = "../vm", version = "2.5.3" }
 rustyline = "10"
 thiserror = "1"
 
diff --git a/derive/Cargo.toml b/derive/Cargo.toml
index d700c566..efc3f266 100644
--- a/derive/Cargo.toml
+++ b/derive/Cargo.toml
@@ -1,7 +1,7 @@
 [package]
 name = "pest_derive"
 description = "pest's derive macro"
-version = "2.5.2"
+version = "2.5.3"
 edition = "2021"
 authors = ["Dragoș Tiselice <dragostiselice@gmail.com>"]
 homepage = "https://pest.rs/"
@@ -23,5 +23,5 @@ std = ["pest/std", "pest_generator/std"]
 
 [dependencies]
 # for tests, included transitively anyway
-pest = { path = "../pest", version = "2.5.2", default-features = false }
-pest_generator = { path = "../generator", version = "2.5.2", default-features = false }
+pest = { path = "../pest", version = "2.5.3", default-features = false }
+pest_generator = { path = "../generator", version = "2.5.3", default-features = false }
diff --git a/generator/Cargo.toml b/generator/Cargo.toml
index 1a6cb322..a9645fc5 100644
--- a/generator/Cargo.toml
+++ b/generator/Cargo.toml
@@ -1,7 +1,7 @@
 [package]
 name = "pest_generator"
 description = "pest code generator"
-version = "2.5.2"
+version = "2.5.3"
 edition = "2021"
 authors = ["Dragoș Tiselice <dragostiselice@gmail.com>"]
 homepage = "https://pest.rs/"
@@ -18,8 +18,8 @@ default = ["std"]
 std = ["pest/std"]
 
 [dependencies]
-pest = { path = "../pest", version = "2.5.2", default-features = false }
-pest_meta = { path = "../meta", version = "2.5.2" }
+pest = { path = "../pest", version = "2.5.3", default-features = false }
+pest_meta = { path = "../meta", version = "2.5.3" }
 proc-macro2 = "1.0"
 quote = "1.0"
 syn = "1.0"
diff --git a/grammars/Cargo.toml b/grammars/Cargo.toml
index 44fda66b..55ea025d 100644
--- a/grammars/Cargo.toml
+++ b/grammars/Cargo.toml
@@ -1,7 +1,7 @@
 [package]
 name = "pest_grammars"
 description = "pest popular grammar implementations"
-version = "2.5.2"
+version = "2.5.3"
 edition = "2021"
 authors = ["Dragoș Tiselice <dragostiselice@gmail.com>"]
 homepage = "https://pest.rs/"
@@ -14,8 +14,8 @@ readme = "_README.md"
 rust-version = "1.56"
 
 [dependencies]
-pest = { path = "../pest", version = "2.5.2" }
-pest_derive = { path = "../derive", version = "2.5.2" }
+pest = { path = "../pest", version = "2.5.3" }
+pest_derive = { path = "../derive", version = "2.5.3" }
 
 [dev-dependencies]
 criterion = "0.3"
diff --git a/meta/Cargo.toml b/meta/Cargo.toml
index ae15b85e..7a83d3b7 100644
--- a/meta/Cargo.toml
+++ b/meta/Cargo.toml
@@ -1,7 +1,7 @@
 [package]
 name = "pest_meta"
 description = "pest meta language parser and validator"
-version = "2.5.2"
+version = "2.5.3"
 edition = "2021"
 authors = ["Dragoș Tiselice <dragostiselice@gmail.com>"]
 homepage = "https://pest.rs/"
@@ -16,7 +16,7 @@ include = ["Cargo.toml", "src/**/*", "src/grammar.rs", "_README.md", "LICENSE-*"
 rust-version = "1.56"
 
 [dependencies]
-pest = { path = "../pest", version = "2.5.2" }
+pest = { path = "../pest", version = "2.5.3" }
 once_cell = "1.8.0"
 
 [build-dependencies]
diff --git a/meta/src/optimizer/factorizer.rs b/meta/src/optimizer/factorizer.rs
index 5481870b..cff018b6 100644
--- a/meta/src/optimizer/factorizer.rs
+++ b/meta/src/optimizer/factorizer.rs
@@ -26,7 +26,11 @@ pub fn factor(rule: Rule) -> Rule {
                         }
                     }
                     // Converts `(rule ~ rest) | rule` to `rule ~ rest?`, avoiding trying to match `rule` twice.
-                    (Expr::Seq(l1, l2), r) => {
+                    // This is only done for atomic rules, because other rule types have implicit whitespaces.
+                    // FIXME: "desugar" implicit whitespace rules before applying any optimizations
+                    (Expr::Seq(l1, l2), r)
+                        if matches!(ty, RuleType::Atomic | RuleType::CompoundAtomic) =>
+                    {
                         if *l1 == r {
                             Expr::Seq(l1, Box::new(Expr::Opt(l2)))
                         } else {
diff --git a/meta/src/optimizer/mod.rs b/meta/src/optimizer/mod.rs
index 2038753b..b1fa05ff 100644
--- a/meta/src/optimizer/mod.rs
+++ b/meta/src/optimizer/mod.rs
@@ -543,7 +543,7 @@ mod tests {
             use crate::ast::Expr::*;
             vec![Rule {
                 name: "rule".to_owned(),
-                ty: RuleType::Silent,
+                ty: RuleType::Atomic,
                 expr: box_tree!(Choice(
                     Seq(Ident(String::from("a")), Ident(String::from("b"))),
                     Ident(String::from("a"))
@@ -554,7 +554,7 @@ mod tests {
             use crate::optimizer::OptimizedExpr::*;
             vec![OptimizedRule {
                 name: "rule".to_owned(),
-                ty: RuleType::Silent,
+                ty: RuleType::Atomic,
                 expr: box_tree!(Seq(Ident(String::from("a")), Opt(Ident(String::from("b"))))),
             }]
         };
diff --git a/pest/Cargo.toml b/pest/Cargo.toml
index 2dd3837e..a9ddbefe 100644
--- a/pest/Cargo.toml
+++ b/pest/Cargo.toml
@@ -1,7 +1,7 @@
 [package]
 name = "pest"
 description = "The Elegant Parser"
-version = "2.5.2"
+version = "2.5.3"
 edition = "2021"
 authors = ["Dragoș Tiselice <dragostiselice@gmail.com>"]
 homepage = "https://pest.rs/"
diff --git a/vm/Cargo.toml b/vm/Cargo.toml
index 5061c81d..ecaab960 100644
--- a/vm/Cargo.toml
+++ b/vm/Cargo.toml
@@ -1,7 +1,7 @@
 [package]
 name = "pest_vm"
 description = "pest grammar virtual machine"
-version = "2.5.2"
+version = "2.5.3"
 edition = "2021"
 authors = ["Dragoș Tiselice <dragostiselice@gmail.com>"]
 homepage = "https://pest.rs/"
@@ -14,5 +14,5 @@ readme = "_README.md"
 rust-version = "1.56"
 
 [dependencies]
-pest = { path = "../pest", version = "2.5.2" }
-pest_meta = { path = "../meta", version = "2.5.2" }
+pest = { path = "../pest", version = "2.5.3" }
+pest_meta = { path = "../meta", version = "2.5.3" }


Test patch:
diff --git a/derive/tests/implicit.pest b/derive/tests/implicit.pest
new file mode 100644
index 00000000..18ebf7ea
--- /dev/null
+++ b/derive/tests/implicit.pest
@@ -0,0 +1,14 @@
+program = _{ SOI ~ implicit ~ EOI  }
+implicit= ${ or ~ (WHITESPACE+ ~ or )* }
+
+or  = !{ and ~ (or_op ~ and)+ | and }
+and = { comp ~ (and_op ~ comp)+ | comp }
+comp = { array ~ eq_op ~ array | array }
+
+array = ${ term }
+
+term = _{ ASCII_ALPHANUMERIC+ }
+or_op = { "||" }
+and_op = { "&&" }
+eq_op = { "=" }
+WHITESPACE = _{ " " | "\t" | NEWLINE }
\ No newline at end of file
diff --git a/derive/tests/implicit.rs b/derive/tests/implicit.rs
new file mode 100644
index 00000000..8ad5a7e6
--- /dev/null
+++ b/derive/tests/implicit.rs
@@ -0,0 +1,25 @@
+// Licensed under the Apache License, Version 2.0
+// <LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0> or the MIT
+// license <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. All files in the project carrying such notice may not be copied,
+// modified, or distributed except according to those terms.
+
+#![cfg_attr(not(feature = "std"), no_std)]
+extern crate alloc;
+extern crate pest;
+extern crate pest_derive;
+
+use pest::Parser;
+use pest_derive::Parser;
+
+#[derive(Parser)]
+#[grammar = "../tests/implicit.pest"]
+struct TestImplicitParser;
+
+#[test]
+fn test_implicit_whitespace() {
+    // this failed to parse due to a bug in the optimizer
+    // see: https://github.com/pest-parser/pest/issues/762#issuecomment-1375374868
+    let successful_parse = TestImplicitParser::parse(Rule::program, "a a");
+    assert!(successful_parse.is_ok());
+}