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

Issue:
validator not reporting an error for indefinite parsing
Hello. I hope this issue adds value to the other hang/timeout issues that are open already.

```rust
// not when no '!reserved |'
ident    = @{ !reserved | !(ASCII_DIGIT) ~ ('a'..'z' | 'A'..'Z' | "_" | '0'..'9')+ }
// not when reserved = {""}
reserved =  { " " }

// coalesced version from og. code
b_op = { "." }

expr_un = _{ term_un ~ (b_op ~ term_un)* }
term_un = _{ (ident) | "(" ~ expr_un ~ ")" }
// crashes!
expr_post = @{ (expr_un)* ~ b_op }

WHITESPACE = _{ (" " | NEWLINE)  }
```

The following input causes the hang:
```plaintext
if (
```

The debugger shows this:
```plaintext
--> 1:1
  |
1 | if (a) {
  | ^---
  |
  = parsing ident
```

Please note that the rule `ident`, by itself, doesn't cause a hang, and instead finishes normally:
```
- ident: ""
```

No other rule causes issues.


Discussion / hints:
The grammar you are describing has rules that do not consume anything:

- `ident    = @{ !reserved | ...` in case the input starts with something else than a space
- as a consequence `term_un` in case the input starts with something else than a space
- then `expr_un` in case the input  starts neither by a space nor by a `b_op` (".")

So when `expr_post` is applied to an input starting neither by a space nor by a dot,  the `*` consumes nothing indefinitely and gets stuck.

I'm new here but from what I understand, one of the steps in reading the grammar is validation (done if I'm not mistaken in meta/src/validator.rs).  The validation step should catch and report this kind of errors. There are two validation steps that seem to aim to catch this error, `pest_meta::validator::is_non_progressing` and `pest_meta::validator::is_non_failing`; but neither of them catches the error.

I would like fix this bug, but I don't know what those two step are really meant to do, if it is the right place to do it.
I'm not sure why those two steps are separate, what is the difference between "failing" and "not progressing" ?
> I'm not sure why those two steps are separate, what is the difference between "failing" and "not progressing" ?

@Tartasprint based on my understanding from reading the test cases and this older PR: https://github.com/pest-parser/pest/pull/259 , the difference is the following:

- non-progressing == it loops forever
- non-failing == it can terminate, but it is always succeeding / consuming tokens in one place, such as in choices, the non-failing branch always succeeds for possible inputs, while the other branches are "dead code" / redundant / never done because of that

Fix patch:
diff --git a/meta/src/validator.rs b/meta/src/validator.rs
index d9c2ed3c..a365530c 100644
--- a/meta/src/validator.rs
+++ b/meta/src/validator.rs
@@ -216,6 +216,12 @@ pub fn validate_undefined<'i>(
 pub fn validate_ast<'a, 'i: 'a>(rules: &'a Vec<ParserRule<'i>>) -> Vec<Error<Rule>> {
     let mut errors = vec![];
 
+    // WARNING: validate_{repetition,choice,whitespace_comment}
+    // use is_non_failing and is_non_progressing breaking assumptions:
+    // - for every `ParserExpr::RepMinMax(inner,min,max)`,
+    //   `min<=max` was not checked
+    // - left recursion was not checked
+    // - Every expression might not be checked
     errors.extend(validate_repetition(rules));
     errors.extend(validate_choices(rules));
     errors.extend(validate_whitespace_comment(rules));
@@ -229,15 +235,32 @@ pub fn validate_ast<'a, 'i: 'a>(rules: &'a Vec<ParserRule<'i>>) -> Vec<Error<Rul
     errors
 }
 
+/// Checks if `expr` is non-progressing, that is the expression does not
+/// consume any input or any stack. This includes expressions matching the empty input,
+/// `SOI` and ̀ `EOI`, predicates and repetitions.
+///
+/// # Example
+///
+/// ```pest
+/// not_progressing_1 = { "" }
+/// not_progressing_2 = { "a"? }
+/// not_progressing_3 = { !"a" }
+/// ```
+///
+/// # Assumptions
+/// - In `ParserExpr::RepMinMax(inner,min,max)`, `min<=max`
+/// - All rules identiers have a matching definition
+/// - There is no left-recursion (if only this one is broken returns false)
+/// - Every expression is being checked
 fn is_non_progressing<'i>(
     expr: &ParserExpr<'i>,
     rules: &HashMap<String, &ParserNode<'i>>,
     trace: &mut Vec<String>,
 ) -> bool {
     match *expr {
-        ParserExpr::Str(ref string) => string.is_empty(),
+        ParserExpr::Str(ref string) | ParserExpr::Insens(ref string) => string.is_empty(),
         ParserExpr::Ident(ref ident) => {
-            if ident == "soi" || ident == "eoi" {
+            if ident == "SOI" || ident == "EOI" {
                 return true;
             }
 
@@ -249,12 +272,27 @@ fn is_non_progressing<'i>(
 
                     return result;
                 }
+                // else
+                // the ident is
+                // - "POP","PEEK" => false
+                //      the slice being checked is not non_progressing since every
+                //      PUSH is being checked (assumption 4) and the expr
+                //      of a PUSH has to be non_progressing.
+                // - "POPALL", "PEEKALL" => false
+                //      same as "POP", "PEEK" unless the following:
+                //      BUG: if the stack is empty they are non_progressing
+                // - "DROP" => false doesn't consume the input but consumes the stack,
+                // - "ANY", "ASCII_*", UNICODE categories, "NEWLINE" => false
+                // - referring to another rule that is undefined (breaks assumption)
             }
+            // else referring to another rule that was already seen.
+            //    this happens only if there is a left-recursion
+            //    that is only if an assumption is broken,
+            //    WARNING: we can choose to return false, but that might
+            //    cause bugs into the left_recursion check
 
             false
         }
-        ParserExpr::PosPred(_) => true,
-        ParserExpr::NegPred(_) => true,
         ParserExpr::Seq(ref lhs, ref rhs) => {
             is_non_progressing(&lhs.expr, rules, trace)
                 && is_non_progressing(&rhs.expr, rules, trace)
@@ -263,17 +301,58 @@ fn is_non_progressing<'i>(
             is_non_progressing(&lhs.expr, rules, trace)
                 || is_non_progressing(&rhs.expr, rules, trace)
         }
-        _ => false,
+        // WARNING: the predicate indeed won't make progress on input but  it
+        // might progress on the stack
+        // ex: @{ PUSH(ANY) ~ (&(DROP))* ~ ANY }, input="AA"
+        //     Notice that this is ex not working as of now, the debugger seems
+        //     to run into an infinite loop on it
+        ParserExpr::PosPred(_) | ParserExpr::NegPred(_) => true,
+        ParserExpr::Rep(_) | ParserExpr::Opt(_) | ParserExpr::RepMax(_, _) => true,
+        // it either always fail (failing is progressing)
+        // or always match at least a character
+        ParserExpr::Range(_, _) => false,
+        ParserExpr::PeekSlice(_, _) => {
+            // the slice being checked is not non_progressing since every
+            // PUSH is being checked (assumption 4) and the expr
+            // of a PUSH has to be non_progressing.
+            // BUG: if the slice is of size 0, or the stack is not large
+            // enough it might be non-progressing
+            false
+        }
+
+        ParserExpr::RepExact(ref inner, min)
+        | ParserExpr::RepMin(ref inner, min)
+        | ParserExpr::RepMinMax(ref inner, min, _) => {
+            min == 0 || is_non_progressing(&inner.expr, rules, trace)
+        }
+        ParserExpr::Push(ref inner) => is_non_progressing(&inner.expr, rules, trace),
+        ParserExpr::RepOnce(ref inner) | ParserExpr::NodeTag(ref inner, _) => {
+            is_non_progressing(&inner.expr, rules, trace)
+        }
     }
 }
 
+/// Checks if `expr` is non-failing, that is it matches any input.
+///
+/// # Example
+///
+/// ```pest
+/// non_failing_1 = { "" }
+/// ```
+///
+/// # Assumptions
+/// - In `ParserExpr::RepMinMax(inner,min,max)`, `min<=max`
+/// - In `ParserExpr::PeekSlice(max,Some(min))`, `max>=min`
+/// - All rules identiers have a matching definition
+/// - There is no left-recursion
+/// - All rules are being checked
 fn is_non_failing<'i>(
     expr: &ParserExpr<'i>,
     rules: &HashMap<String, &ParserNode<'i>>,
     trace: &mut Vec<String>,
 ) -> bool {
     match *expr {
-        ParserExpr::Str(ref string) => string.is_empty(),
+        ParserExpr::Str(ref string) | ParserExpr::Insens(ref string) => string.is_empty(),
         ParserExpr::Ident(ref ident) => {
             if !trace.contains(ident) {
                 if let Some(node) = rules.get(ident) {
@@ -281,21 +360,66 @@ fn is_non_failing<'i>(
                     let result = is_non_failing(&node.expr, rules, trace);
                     trace.pop().unwrap();
 
-                    return result;
+                    result
+                } else {
+                    // else
+                    // the ident is
+                    // - "POP","PEEK" => false
+                    //      the slice being checked is not non_failing since every
+                    //      PUSH is being checked (assumption 4) and the expr
+                    //      of a PUSH has to be non_failing.
+                    // - "POP_ALL", "PEEK_ALL" => false
+                    //      same as "POP", "PEEK" unless the following:
+                    //      BUG: if the stack is empty they are non_failing
+                    // - "DROP" => false
+                    // - "ANY", "ASCII_*", UNICODE categories, "NEWLINE",
+                    //      "SOI", "EOI" => false
+                    // - referring to another rule that is undefined (breaks assumption)
+                    //      WARNING: might want to introduce a panic or report the error
+                    false
                 }
+            } else {
+                // referring to another rule R that was already seen
+                // WARNING: this might mean there is a circular non-failing path
+                //   it's not obvious wether this can happen without left-recursion
+                //   and thus breaking the assumption. Until there is answer to
+                //   this, to avoid changing behaviour we return:
+                false
             }
-
-            false
         }
         ParserExpr::Opt(_) => true,
         ParserExpr::Rep(_) => true,
+        ParserExpr::RepMax(_, _) => true,
         ParserExpr::Seq(ref lhs, ref rhs) => {
             is_non_failing(&lhs.expr, rules, trace) && is_non_failing(&rhs.expr, rules, trace)
         }
         ParserExpr::Choice(ref lhs, ref rhs) => {
             is_non_failing(&lhs.expr, rules, trace) || is_non_failing(&rhs.expr, rules, trace)
         }
-        _ => false,
+        // it either always fail
+        // or always match at least a character
+        ParserExpr::Range(_, _) => false,
+        ParserExpr::PeekSlice(_, _) => {
+            // the slice being checked is not non_failing since every
+            // PUSH is being checked (assumption 4) and the expr
+            // of a PUSH has to be non_failing.
+            // BUG: if the slice is of size 0, or the stack is not large
+            // enough it might be non-failing
+            false
+        }
+        ParserExpr::RepExact(ref inner, min)
+        | ParserExpr::RepMin(ref inner, min)
+        | ParserExpr::RepMinMax(ref inner, min, _) => {
+            min == 0 || is_non_failing(&inner.expr, rules, trace)
+        }
+        // BUG: the predicate may always fail, resulting in this expr non_failing
+        // ex of always failing predicates :
+        //     @{EOI ~ ANY | ANY ~ SOI | &("A") ~ &("B") | 'z'..'a'}
+        ParserExpr::NegPred(_) => false,
+        ParserExpr::RepOnce(ref inner) => is_non_failing(&inner.expr, rules, trace),
+        ParserExpr::Push(ref inner)
+        | ParserExpr::NodeTag(ref inner, _)
+        | ParserExpr::PosPred(ref inner) => is_non_failing(&inner.expr, rules, trace),
     }
 }
 
@@ -583,17 +707,873 @@ mod tests {
 
  --> 1:13
   |
-1 | COMMENT = { soi }
+1 | COMMENT = { SOI }
   |             ^-^
   |
   = COMMENT is non-progressing and will repeat infinitely")]
     fn non_progressing_comment() {
-        let input = "COMMENT = { soi }";
+        let input = "COMMENT = { SOI }";
         unwrap_or_report(consume_rules(
             PestParser::parse(Rule::grammar_rules, input).unwrap(),
         ));
     }
 
+    #[test]
+    fn non_progressing_empty_string() {
+        assert!(is_non_failing(
+            &ParserExpr::Insens("".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_progressing(
+            &ParserExpr::Str("".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+    }
+
+    #[test]
+    fn progressing_non_empty_string() {
+        assert!(!is_non_progressing(
+            &ParserExpr::Insens("non empty".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_progressing(
+            &ParserExpr::Str("non empty".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+    }
+
+    #[test]
+    fn non_progressing_soi_eoi() {
+        assert!(is_non_progressing(
+            &ParserExpr::Ident("SOI".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_progressing(
+            &ParserExpr::Ident("EOI".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+    }
+
+    #[test]
+    fn non_progressing_predicates() {
+        let progressing = ParserExpr::Str("A".into());
+
+        assert!(is_non_progressing(
+            &ParserExpr::PosPred(Box::new(ParserNode {
+                expr: progressing.clone(),
+                span: Span::new(" ", 0, 1).unwrap(),
+            })),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_progressing(
+            &ParserExpr::NegPred(Box::new(ParserNode {
+                expr: progressing,
+                span: Span::new(" ", 0, 1).unwrap(),
+            })),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+    }
+
+    #[test]
+    fn non_progressing_0_length_repetitions() {
+        let input_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("A".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(!is_non_progressing(
+            &input_progressing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        assert!(is_non_progressing(
+            &ParserExpr::Rep(input_progressing_node.clone()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_progressing(
+            &ParserExpr::Opt(input_progressing_node.clone()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_progressing(
+            &ParserExpr::RepExact(input_progressing_node.clone(), 0),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_progressing(
+            &ParserExpr::RepMin(input_progressing_node.clone(), 0),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_progressing(
+            &ParserExpr::RepMax(input_progressing_node.clone(), 0),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_progressing(
+            &ParserExpr::RepMax(input_progressing_node.clone(), 17),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        assert!(is_non_progressing(
+            &ParserExpr::RepMinMax(input_progressing_node.clone(), 0, 12),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+    }
+
+    #[test]
+    fn non_progressing_nonzero_repetitions_with_non_progressing_expr() {
+        let a = "";
+        let non_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str(a.into()),
+            span: Span::new(a, 0, 0).unwrap(),
+        });
+        let exact = ParserExpr::RepExact(non_progressing_node.clone(), 7);
+        let min = ParserExpr::RepMin(non_progressing_node.clone(), 23);
+        let minmax = ParserExpr::RepMinMax(non_progressing_node.clone(), 12, 13);
+        let reponce = ParserExpr::RepOnce(non_progressing_node);
+
+        assert!(is_non_progressing(&exact, &HashMap::new(), &mut Vec::new()));
+        assert!(is_non_progressing(&min, &HashMap::new(), &mut Vec::new()));
+        assert!(is_non_progressing(
+            &minmax,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_progressing(
+            &reponce,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+    }
+
+    #[test]
+    fn progressing_repetitions() {
+        let a = "A";
+        let input_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str(a.into()),
+            span: Span::new(a, 0, 1).unwrap(),
+        });
+        let exact = ParserExpr::RepExact(input_progressing_node.clone(), 1);
+        let min = ParserExpr::RepMin(input_progressing_node.clone(), 2);
+        let minmax = ParserExpr::RepMinMax(input_progressing_node.clone(), 4, 5);
+        let reponce = ParserExpr::RepOnce(input_progressing_node);
+
+        assert!(!is_non_progressing(
+            &exact,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_progressing(&min, &HashMap::new(), &mut Vec::new()));
+        assert!(!is_non_progressing(
+            &minmax,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_progressing(
+            &reponce,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+    }
+
+    #[test]
+    fn non_progressing_push() {
+        let a = "";
+        let non_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str(a.into()),
+            span: Span::new(a, 0, 0).unwrap(),
+        });
+        let push = ParserExpr::Push(non_progressing_node.clone());
+
+        assert!(is_non_progressing(&push, &HashMap::new(), &mut Vec::new()));
+    }
+
+    #[test]
+    fn progressing_push() {
+        let a = "i'm make progress";
+        let progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str(a.into()),
+            span: Span::new(a, 0, 1).unwrap(),
+        });
+        let push = ParserExpr::Push(progressing_node.clone());
+
+        assert!(!is_non_progressing(&push, &HashMap::new(), &mut Vec::new()));
+    }
+
+    #[test]
+    fn node_tag_forwards_is_non_progressing() {
+        let progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("i'm make progress".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+        assert!(!is_non_progressing(
+            &progressing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        let non_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+        assert!(is_non_progressing(
+            &non_progressing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        let progressing = ParserExpr::NodeTag(progressing_node.clone(), "TAG".into());
+        let non_progressing = ParserExpr::NodeTag(non_progressing_node.clone(), "TAG".into());
+
+        assert!(!is_non_progressing(
+            &progressing,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_progressing(
+            &non_progressing,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+    }
+
+    #[test]
+    fn progressing_range() {
+        let progressing = ParserExpr::Range("A".into(), "Z".into());
+        let failing_is_progressing = ParserExpr::Range("Z".into(), "A".into());
+
+        assert!(!is_non_progressing(
+            &progressing,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_progressing(
+            &failing_is_progressing,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+    }
+
+    #[test]
+    fn progressing_choice() {
+        let left_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("i'm make progress".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+        assert!(!is_non_progressing(
+            &left_progressing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        let right_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Ident("DROP".into()),
+            span: Span::new("DROP", 0, 3).unwrap(),
+        });
+
+        assert!(!is_non_progressing(
+            &ParserExpr::Choice(left_progressing_node, right_progressing_node),
+            &HashMap::new(),
+            &mut Vec::new()
+        ))
+    }
+
+    #[test]
+    fn non_progressing_choices() {
+        let left_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("i'm make progress".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(!is_non_progressing(
+            &left_progressing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        let left_non_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(is_non_progressing(
+            &left_non_progressing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        let right_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Ident("DROP".into()),
+            span: Span::new("DROP", 0, 3).unwrap(),
+        });
+
+        assert!(!is_non_progressing(
+            &right_progressing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        let right_non_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Opt(Box::new(ParserNode {
+                expr: ParserExpr::Str("   ".into()),
+                span: Span::new(" ", 0, 1).unwrap(),
+            })),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(is_non_progressing(
+            &right_non_progressing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        assert!(is_non_progressing(
+            &ParserExpr::Choice(left_non_progressing_node.clone(), right_progressing_node),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_progressing(
+            &ParserExpr::Choice(left_progressing_node, right_non_progressing_node.clone()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_progressing(
+            &ParserExpr::Choice(left_non_progressing_node, right_non_progressing_node),
+            &HashMap::new(),
+            &mut Vec::new()
+        ))
+    }
+
+    #[test]
+    fn non_progressing_seq() {
+        let left_non_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        let right_non_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Opt(Box::new(ParserNode {
+                expr: ParserExpr::Str("   ".into()),
+                span: Span::new(" ", 0, 1).unwrap(),
+            })),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(is_non_progressing(
+            &ParserExpr::Seq(left_non_progressing_node, right_non_progressing_node),
+            &HashMap::new(),
+            &mut Vec::new()
+        ))
+    }
+
+    #[test]
+    fn progressing_seqs() {
+        let left_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("i'm make progress".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(!is_non_progressing(
+            &left_progressing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        let left_non_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(is_non_progressing(
+            &left_non_progressing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        let right_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Ident("DROP".into()),
+            span: Span::new("DROP", 0, 3).unwrap(),
+        });
+
+        assert!(!is_non_progressing(
+            &right_progressing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        let right_non_progressing_node = Box::new(ParserNode {
+            expr: ParserExpr::Opt(Box::new(ParserNode {
+                expr: ParserExpr::Str("   ".into()),
+                span: Span::new(" ", 0, 1).unwrap(),
+            })),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(is_non_progressing(
+            &right_non_progressing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        assert!(!is_non_progressing(
+            &ParserExpr::Seq(left_non_progressing_node, right_progressing_node.clone()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_progressing(
+            &ParserExpr::Seq(left_progressing_node.clone(), right_non_progressing_node),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_progressing(
+            &ParserExpr::Seq(left_progressing_node, right_progressing_node),
+            &HashMap::new(),
+            &mut Vec::new()
+        ))
+    }
+
+    #[test]
+    fn progressing_stack_operations() {
+        assert!(!is_non_progressing(
+            &ParserExpr::Ident("DROP".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_progressing(
+            &ParserExpr::Ident("PEEK".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_progressing(
+            &ParserExpr::Ident("POP".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ))
+    }
+
+    #[test]
+    fn non_failing_string() {
+        let insens = ParserExpr::Insens("".into());
+        let string = ParserExpr::Str("".into());
+
+        assert!(is_non_failing(&insens, &HashMap::new(), &mut Vec::new()));
+
+        assert!(is_non_failing(&string, &HashMap::new(), &mut Vec::new()))
+    }
+
+    #[test]
+    fn failing_string() {
+        assert!(!is_non_failing(
+            &ParserExpr::Insens("i may fail!".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_failing(
+            &ParserExpr::Str("failure is not fatal".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ))
+    }
+
+    #[test]
+    fn failing_stack_operations() {
+        assert!(!is_non_failing(
+            &ParserExpr::Ident("DROP".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_failing(
+            &ParserExpr::Ident("POP".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_failing(
+            &ParserExpr::Ident("PEEK".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ))
+    }
+
+    #[test]
+    fn non_failing_zero_length_repetitions() {
+        let failing = Box::new(ParserNode {
+            expr: ParserExpr::Range("A".into(), "B".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+        assert!(!is_non_failing(
+            &failing.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::Opt(failing.clone()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::Rep(failing.clone()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::RepExact(failing.clone(), 0),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::RepMin(failing.clone(), 0),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::RepMax(failing.clone(), 0),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::RepMax(failing.clone(), 22),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::RepMinMax(failing.clone(), 0, 73),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+    }
+
+    #[test]
+    fn non_failing_non_zero_repetitions_with_non_failing_expr() {
+        let non_failing = Box::new(ParserNode {
+            expr: ParserExpr::Opt(Box::new(ParserNode {
+                expr: ParserExpr::Range("A".into(), "B".into()),
+                span: Span::new(" ", 0, 1).unwrap(),
+            })),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+        assert!(is_non_failing(
+            &non_failing.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::RepOnce(non_failing.clone()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::RepExact(non_failing.clone(), 1),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::RepMin(non_failing.clone(), 6),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::RepMinMax(non_failing.clone(), 32, 73),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+    }
+
+    #[test]
+    fn failing_non_zero_repetitions() {
+        let failing = Box::new(ParserNode {
+            expr: ParserExpr::NodeTag(
+                Box::new(ParserNode {
+                    expr: ParserExpr::Range("A".into(), "B".into()),
+                    span: Span::new(" ", 0, 1).unwrap(),
+                }),
+                "Tag".into(),
+            ),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+        assert!(!is_non_failing(
+            &failing.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_failing(
+            &ParserExpr::RepOnce(failing.clone()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_failing(
+            &ParserExpr::RepExact(failing.clone(), 3),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_failing(
+            &ParserExpr::RepMin(failing.clone(), 14),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_failing(
+            &ParserExpr::RepMinMax(failing.clone(), 47, 73),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+    }
+
+    #[test]
+    fn failing_choice() {
+        let left_failing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("i'm a failure".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+        assert!(!is_non_failing(
+            &left_failing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        let right_failing_node = Box::new(ParserNode {
+            expr: ParserExpr::Ident("DROP".into()),
+            span: Span::new("DROP", 0, 3).unwrap(),
+        });
+
+        assert!(!is_non_failing(
+            &ParserExpr::Choice(left_failing_node, right_failing_node),
+            &HashMap::new(),
+            &mut Vec::new()
+        ))
+    }
+
+    #[test]
+    fn non_failing_choices() {
+        let left_failing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("i'm a failure".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(!is_non_failing(
+            &left_failing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        let left_non_failing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(is_non_failing(
+            &left_non_failing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        let right_failing_node = Box::new(ParserNode {
+            expr: ParserExpr::Ident("DROP".into()),
+            span: Span::new("DROP", 0, 3).unwrap(),
+        });
+
+        assert!(!is_non_failing(
+            &right_failing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        let right_non_failing_node = Box::new(ParserNode {
+            expr: ParserExpr::Opt(Box::new(ParserNode {
+                expr: ParserExpr::Str("   ".into()),
+                span: Span::new(" ", 0, 1).unwrap(),
+            })),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(is_non_failing(
+            &right_non_failing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        assert!(is_non_failing(
+            &ParserExpr::Choice(left_non_failing_node.clone(), right_failing_node),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::Choice(left_failing_node, right_non_failing_node.clone()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::Choice(left_non_failing_node, right_non_failing_node),
+            &HashMap::new(),
+            &mut Vec::new()
+        ))
+    }
+
+    #[test]
+    fn non_failing_seq() {
+        let left_non_failing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        let right_non_failing_node = Box::new(ParserNode {
+            expr: ParserExpr::Opt(Box::new(ParserNode {
+                expr: ParserExpr::Str("   ".into()),
+                span: Span::new(" ", 0, 1).unwrap(),
+            })),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(is_non_failing(
+            &ParserExpr::Seq(left_non_failing_node, right_non_failing_node),
+            &HashMap::new(),
+            &mut Vec::new()
+        ))
+    }
+
+    #[test]
+    fn failing_seqs() {
+        let left_failing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("i'm a failure".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(!is_non_failing(
+            &left_failing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        let left_non_failing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(is_non_failing(
+            &left_non_failing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        let right_failing_node = Box::new(ParserNode {
+            expr: ParserExpr::Ident("DROP".into()),
+            span: Span::new("DROP", 0, 3).unwrap(),
+        });
+
+        assert!(!is_non_failing(
+            &right_failing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        let right_non_failing_node = Box::new(ParserNode {
+            expr: ParserExpr::Opt(Box::new(ParserNode {
+                expr: ParserExpr::Str("   ".into()),
+                span: Span::new(" ", 0, 1).unwrap(),
+            })),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+
+        assert!(is_non_failing(
+            &right_non_failing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        assert!(!is_non_failing(
+            &ParserExpr::Seq(left_non_failing_node, right_failing_node.clone()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_failing(
+            &ParserExpr::Seq(left_failing_node.clone(), right_non_failing_node),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(!is_non_failing(
+            &ParserExpr::Seq(left_failing_node, right_failing_node),
+            &HashMap::new(),
+            &mut Vec::new()
+        ))
+    }
+
+    #[test]
+    fn failing_range() {
+        let failing = ParserExpr::Range("A".into(), "Z".into());
+        let always_failing = ParserExpr::Range("Z".into(), "A".into());
+
+        assert!(!is_non_failing(&failing, &HashMap::new(), &mut Vec::new()));
+        assert!(!is_non_failing(
+            &always_failing,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+    }
+
+    #[test]
+    fn _push_node_tag_pos_pred_forwarding_is_non_failing() {
+        let failing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("i'm a failure".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+        assert!(!is_non_failing(
+            &failing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        let non_failing_node = Box::new(ParserNode {
+            expr: ParserExpr::Str("".into()),
+            span: Span::new(" ", 0, 1).unwrap(),
+        });
+        assert!(is_non_failing(
+            &non_failing_node.clone().expr,
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        assert!(!is_non_failing(
+            &ParserExpr::NodeTag(failing_node.clone(), "TAG".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::NodeTag(non_failing_node.clone(), "TAG".into()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        assert!(!is_non_failing(
+            &ParserExpr::Push(failing_node.clone()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::Push(non_failing_node.clone()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+
+        assert!(!is_non_failing(
+            &ParserExpr::PosPred(failing_node.clone()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+        assert!(is_non_failing(
+            &ParserExpr::PosPred(non_failing_node.clone()),
+            &HashMap::new(),
+            &mut Vec::new()
+        ));
+    }
+
     #[test]
     #[should_panic(expected = "grammar error
 
@@ -647,12 +1627,12 @@ mod tests {
 
  --> 1:7
   |
-1 | a = { (\"\" ~ &\"a\" ~ !\"a\" ~ (soi | eoi))* }
+1 | a = { (\"\" ~ &\"a\" ~ !\"a\" ~ (SOI | EOI))* }
   |       ^-------------------------------^
   |
   = expression inside repetition is non-progressing and will repeat infinitely")]
     fn non_progressing_repetition() {
-        let input = "a = { (\"\" ~ &\"a\" ~ !\"a\" ~ (soi | eoi))* }";
+        let input = "a = { (\"\" ~ &\"a\" ~ !\"a\" ~ (SOI | EOI))* }";
         unwrap_or_report(consume_rules(
             PestParser::parse(Rule::grammar_rules, input).unwrap(),
         ));


Test patch: