pest_meta/
validator.rs

1// pest. The Elegant Parser
2// Copyright (c) 2018 DragoÈ™ Tiselice
3//
4// Licensed under the Apache License, Version 2.0
5// <LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0> or the MIT
6// license <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
7// option. All files in the project carrying such notice may not be copied,
8// modified, or distributed except according to those terms.
9
10//! Helpers for validating pest grammars that could help with debugging
11//! and provide a more user-friendly error message.
12
13use std::{
14    collections::{HashMap, HashSet},
15    sync::LazyLock,
16};
17
18use pest::error::{Error, ErrorVariant, InputLocation};
19use pest::iterators::Pairs;
20use pest::unicode::unicode_property_names;
21use pest::Span;
22
23use crate::parser::{ParserExpr, ParserNode, ParserRule, Rule};
24
25static RUST_KEYWORDS: LazyLock<HashSet<&'static str>> = LazyLock::new(|| {
26    [
27        "abstract", "alignof", "as", "become", "box", "break", "const", "continue", "crate", "do",
28        "else", "enum", "extern", "false", "final", "fn", "for", "if", "impl", "in", "let", "loop",
29        "macro", "match", "mod", "move", "mut", "offsetof", "override", "priv", "proc", "pure",
30        "pub", "ref", "return", "Self", "self", "sizeof", "static", "struct", "super", "trait",
31        "true", "type", "typeof", "unsafe", "unsized", "use", "virtual", "where", "while", "yield",
32    ]
33    .iter()
34    .cloned()
35    .collect()
36});
37
38static PEST_KEYWORDS: LazyLock<HashSet<&'static str>> = LazyLock::new(|| {
39    [
40        "_", "ANY", "DROP", "EOI", "PEEK", "PEEK_ALL", "POP", "POP_ALL", "PUSH", "SOI",
41    ]
42    .iter()
43    .cloned()
44    .collect()
45});
46
47static BUILTINS: LazyLock<HashSet<&'static str>> = LazyLock::new(|| {
48    [
49        "ANY",
50        "DROP",
51        "EOI",
52        "PEEK",
53        "PEEK_ALL",
54        "POP",
55        "POP_ALL",
56        "SOI",
57        "ASCII_DIGIT",
58        "ASCII_NONZERO_DIGIT",
59        "ASCII_BIN_DIGIT",
60        "ASCII_OCT_DIGIT",
61        "ASCII_HEX_DIGIT",
62        "ASCII_ALPHA_LOWER",
63        "ASCII_ALPHA_UPPER",
64        "ASCII_ALPHA",
65        "ASCII_ALPHANUMERIC",
66        "ASCII",
67        "NEWLINE",
68    ]
69    .iter()
70    .cloned()
71    .chain(unicode_property_names())
72    .collect::<HashSet<&str>>()
73});
74
75/// It checks the parsed grammar for common mistakes:
76/// - using Pest keywords
77/// - duplicate rules
78/// - undefined rules
79///
80/// It returns a `Result` with a `Vec` of `Error`s if any of the above is found.
81/// If no errors are found, it returns the vector of names of used builtin rules.
82pub fn validate_pairs(pairs: Pairs<'_, Rule>) -> Result<Vec<&str>, Vec<Error<Rule>>> {
83    let definitions: Vec<_> = pairs
84        .clone()
85        .filter(|pair| pair.as_rule() == Rule::grammar_rule)
86        .map(|pair| pair.into_inner().next().unwrap())
87        .filter(|pair| pair.as_rule() != Rule::line_doc)
88        .map(|pair| pair.as_span())
89        .collect();
90
91    let called_rules: Vec<_> = pairs
92        .clone()
93        .filter(|pair| pair.as_rule() == Rule::grammar_rule)
94        .flat_map(|pair| {
95            pair.into_inner()
96                .flatten()
97                .skip(1)
98                .filter(|pair| pair.as_rule() == Rule::identifier)
99                .map(|pair| pair.as_span())
100        })
101        .collect();
102
103    let mut errors = vec![];
104
105    errors.extend(validate_pest_keywords(&definitions));
106    errors.extend(validate_already_defined(&definitions));
107    errors.extend(validate_undefined(&definitions, &called_rules));
108
109    if !errors.is_empty() {
110        return Err(errors);
111    }
112
113    let definitions: HashSet<_> = definitions.iter().map(|span| span.as_str()).collect();
114    let called_rules: HashSet<_> = called_rules.iter().map(|span| span.as_str()).collect();
115
116    let defaults = called_rules.difference(&definitions);
117
118    Ok(defaults.cloned().collect())
119}
120
121/// Validates that the given `definitions` do not contain any Rust keywords.
122#[allow(clippy::ptr_arg)]
123#[deprecated = "Rust keywords are no longer restricted from the pest grammar"]
124pub fn validate_rust_keywords(definitions: &Vec<Span<'_>>) -> Vec<Error<Rule>> {
125    let mut errors = vec![];
126
127    for definition in definitions {
128        let name = definition.as_str();
129
130        if RUST_KEYWORDS.contains(name) {
131            errors.push(Error::new_from_span(
132                ErrorVariant::CustomError {
133                    message: format!("{} is a rust keyword", name),
134                },
135                *definition,
136            ))
137        }
138    }
139
140    errors
141}
142
143/// Validates that the given `definitions` do not contain any Pest keywords.
144#[allow(clippy::ptr_arg)]
145pub fn validate_pest_keywords(definitions: &Vec<Span<'_>>) -> Vec<Error<Rule>> {
146    let mut errors = vec![];
147
148    for definition in definitions {
149        let name = definition.as_str();
150
151        if PEST_KEYWORDS.contains(name) {
152            errors.push(Error::new_from_span(
153                ErrorVariant::CustomError {
154                    message: format!("{} is a pest keyword", name),
155                },
156                *definition,
157            ))
158        }
159    }
160
161    errors
162}
163
164/// Validates that the given `definitions` do not contain any duplicate rules.
165#[allow(clippy::ptr_arg)]
166pub fn validate_already_defined(definitions: &Vec<Span<'_>>) -> Vec<Error<Rule>> {
167    let mut errors = vec![];
168    let mut defined = HashSet::new();
169
170    for definition in definitions {
171        let name = definition.as_str();
172
173        if defined.contains(&name) {
174            errors.push(Error::new_from_span(
175                ErrorVariant::CustomError {
176                    message: format!("rule {} already defined", name),
177                },
178                *definition,
179            ))
180        } else {
181            defined.insert(name);
182        }
183    }
184
185    errors
186}
187
188/// Validates that the given `definitions` do not contain any undefined rules.
189#[allow(clippy::ptr_arg)]
190pub fn validate_undefined<'i>(
191    definitions: &Vec<Span<'i>>,
192    called_rules: &Vec<Span<'i>>,
193) -> Vec<Error<Rule>> {
194    let mut errors = vec![];
195    let definitions: HashSet<_> = definitions.iter().map(|span| span.as_str()).collect();
196
197    for rule in called_rules {
198        let name = rule.as_str();
199
200        if !definitions.contains(name) && !BUILTINS.contains(name) {
201            errors.push(Error::new_from_span(
202                ErrorVariant::CustomError {
203                    message: format!("rule {} is undefined", name),
204                },
205                *rule,
206            ))
207        }
208    }
209
210    errors
211}
212
213/// Validates the abstract syntax tree for common mistakes:
214/// - infinite repetitions
215/// - choices that cannot be reached
216/// - left recursion
217#[allow(clippy::ptr_arg)]
218pub fn validate_ast<'a, 'i: 'a>(rules: &'a Vec<ParserRule<'i>>) -> Vec<Error<Rule>> {
219    let mut errors = vec![];
220
221    // WARNING: validate_{repetition,choice,whitespace_comment}
222    // use is_non_failing and is_non_progressing breaking assumptions:
223    // - for every `ParserExpr::RepMinMax(inner,min,max)`,
224    //   `min<=max` was not checked
225    // - left recursion was not checked
226    // - Every expression might not be checked
227    errors.extend(validate_repetition(rules));
228    errors.extend(validate_choices(rules));
229    errors.extend(validate_whitespace_comment(rules));
230    errors.extend(validate_left_recursion(rules));
231    #[cfg(feature = "grammar-extras")]
232    errors.extend(validate_tag_silent_rules(rules));
233
234    errors.sort_by_key(|error| match error.location {
235        InputLocation::Span(span) => span,
236        _ => unreachable!(),
237    });
238
239    errors
240}
241
242#[cfg(feature = "grammar-extras")]
243fn validate_tag_silent_rules<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>> {
244    use crate::ast::RuleType;
245
246    fn to_type_hash_map<'a, 'i: 'a>(
247        rules: &'a [ParserRule<'i>],
248    ) -> HashMap<String, (&'a ParserNode<'i>, RuleType)> {
249        rules
250            .iter()
251            .map(|r| (r.name.clone(), (&r.node, r.ty)))
252            .collect()
253    }
254    let mut result = vec![];
255
256    fn check_silent_builtin<'a, 'i: 'a>(
257        expr: &ParserExpr<'i>,
258        rules_ref: &HashMap<String, (&'a ParserNode<'i>, RuleType)>,
259        span: Span<'a>,
260    ) -> Option<Error<Rule>> {
261        match &expr {
262            ParserExpr::Ident(rule_name) => {
263                let rule = rules_ref.get(rule_name);
264                if matches!(rule, Some((_, RuleType::Silent))) {
265                    return Some(Error::<Rule>::new_from_span(
266                        ErrorVariant::CustomError {
267                            message: "tags on silent rules will not appear in the output"
268                                .to_owned(),
269                        },
270                        span,
271                    ));
272                } else if BUILTINS.contains(rule_name.as_str()) {
273                    return Some(Error::new_from_span(
274                        ErrorVariant::CustomError {
275                            message: "tags on built-in rules will not appear in the output"
276                                .to_owned(),
277                        },
278                        span,
279                    ));
280                }
281            }
282            ParserExpr::Rep(node)
283            | ParserExpr::RepMinMax(node, _, _)
284            | ParserExpr::RepMax(node, _)
285            | ParserExpr::RepMin(node, _)
286            | ParserExpr::RepOnce(node)
287            | ParserExpr::RepExact(node, _)
288            | ParserExpr::Opt(node)
289            | ParserExpr::Push(node)
290            | ParserExpr::PosPred(node)
291            | ParserExpr::NegPred(node) => {
292                return check_silent_builtin(&node.expr, rules_ref, span);
293            }
294            _ => {}
295        };
296        None
297    }
298
299    let rules_map = to_type_hash_map(rules);
300    for rule in rules {
301        let rules_ref = &rules_map;
302        let mut errors = rule.node.clone().filter_map_top_down(|node1| {
303            if let ParserExpr::NodeTag(node2, _) = node1.expr {
304                check_silent_builtin(&node2.expr, rules_ref, node1.span)
305            } else {
306                None
307            }
308        });
309        result.append(&mut errors);
310    }
311    result
312}
313
314/// Checks if `expr` is non-progressing, that is the expression does not
315/// consume any input or any stack. This includes expressions matching the empty input,
316/// `SOI` and ̀ `EOI`, predicates and repetitions.
317///
318/// # Example
319///
320/// ```pest
321/// not_progressing_1 = { "" }
322/// not_progressing_2 = { "a"? }
323/// not_progressing_3 = { !"a" }
324/// ```
325///
326/// # Assumptions
327/// - In `ParserExpr::RepMinMax(inner,min,max)`, `min<=max`
328/// - All rules identiers have a matching definition
329/// - There is no left-recursion (if only this one is broken returns false)
330/// - Every expression is being checked
331fn is_non_progressing<'i>(
332    expr: &ParserExpr<'i>,
333    rules: &HashMap<String, &ParserNode<'i>>,
334    trace: &mut Vec<String>,
335) -> bool {
336    match *expr {
337        ParserExpr::Str(ref string) | ParserExpr::Insens(ref string) => string.is_empty(),
338        ParserExpr::Ident(ref ident) => {
339            if ident == "SOI" || ident == "EOI" {
340                return true;
341            }
342
343            if !trace.contains(ident) {
344                if let Some(node) = rules.get(ident) {
345                    trace.push(ident.clone());
346                    let result = is_non_progressing(&node.expr, rules, trace);
347                    trace.pop().unwrap();
348
349                    return result;
350                }
351                // else
352                // the ident is
353                // - "POP","PEEK" => false
354                //      the slice being checked is not non_progressing since every
355                //      PUSH is being checked (assumption 4) and the expr
356                //      of a PUSH has to be non_progressing.
357                // - "POPALL", "PEEKALL" => false
358                //      same as "POP", "PEEK" unless the following:
359                //      BUG: if the stack is empty they are non_progressing
360                // - "DROP" => false doesn't consume the input but consumes the stack,
361                // - "ANY", "ASCII_*", UNICODE categories, "NEWLINE" => false
362                // - referring to another rule that is undefined (breaks assumption)
363            }
364            // else referring to another rule that was already seen.
365            //    this happens only if there is a left-recursion
366            //    that is only if an assumption is broken,
367            //    WARNING: we can choose to return false, but that might
368            //    cause bugs into the left_recursion check
369
370            false
371        }
372        ParserExpr::Seq(ref lhs, ref rhs) => {
373            is_non_progressing(&lhs.expr, rules, trace)
374                && is_non_progressing(&rhs.expr, rules, trace)
375        }
376        ParserExpr::Choice(ref lhs, ref rhs) => {
377            is_non_progressing(&lhs.expr, rules, trace)
378                || is_non_progressing(&rhs.expr, rules, trace)
379        }
380        // WARNING: the predicate indeed won't make progress on input but  it
381        // might progress on the stack
382        // ex: @{ PUSH(ANY) ~ (&(DROP))* ~ ANY }, input="AA"
383        //     Notice that this is ex not working as of now, the debugger seems
384        //     to run into an infinite loop on it
385        ParserExpr::PosPred(_) | ParserExpr::NegPred(_) => true,
386        ParserExpr::Rep(_) | ParserExpr::Opt(_) | ParserExpr::RepMax(_, _) => true,
387        // it either always fail (failing is progressing)
388        // or always match at least a character
389        ParserExpr::Range(_, _) => false,
390        ParserExpr::PeekSlice(_, _) => {
391            // the slice being checked is not non_progressing since every
392            // PUSH is being checked (assumption 4) and the expr
393            // of a PUSH has to be non_progressing.
394            // BUG: if the slice is of size 0, or the stack is not large
395            // enough it might be non-progressing
396            false
397        }
398
399        ParserExpr::RepExact(ref inner, min)
400        | ParserExpr::RepMin(ref inner, min)
401        | ParserExpr::RepMinMax(ref inner, min, _) => {
402            min == 0 || is_non_progressing(&inner.expr, rules, trace)
403        }
404        ParserExpr::Push(ref inner) => is_non_progressing(&inner.expr, rules, trace),
405        #[cfg(feature = "grammar-extras")]
406        ParserExpr::PushLiteral(_) => true,
407        ParserExpr::RepOnce(ref inner) => is_non_progressing(&inner.expr, rules, trace),
408        #[cfg(feature = "grammar-extras")]
409        ParserExpr::NodeTag(ref inner, _) => is_non_progressing(&inner.expr, rules, trace),
410    }
411}
412
413/// Checks if `expr` is non-failing, that is it matches any input.
414///
415/// # Example
416///
417/// ```pest
418/// non_failing_1 = { "" }
419/// ```
420///
421/// # Assumptions
422/// - In `ParserExpr::RepMinMax(inner,min,max)`, `min<=max`
423/// - In `ParserExpr::PeekSlice(max,Some(min))`, `max>=min`
424/// - All rules identiers have a matching definition
425/// - There is no left-recursion
426/// - All rules are being checked
427fn is_non_failing<'i>(
428    expr: &ParserExpr<'i>,
429    rules: &HashMap<String, &ParserNode<'i>>,
430    trace: &mut Vec<String>,
431) -> bool {
432    match *expr {
433        ParserExpr::Str(ref string) | ParserExpr::Insens(ref string) => string.is_empty(),
434        ParserExpr::Ident(ref ident) => {
435            if !trace.contains(ident) {
436                if let Some(node) = rules.get(ident) {
437                    trace.push(ident.clone());
438                    let result = is_non_failing(&node.expr, rules, trace);
439                    trace.pop().unwrap();
440
441                    result
442                } else {
443                    // else
444                    // the ident is
445                    // - "POP","PEEK" => false
446                    //      the slice being checked is not non_failing since every
447                    //      PUSH is being checked (assumption 4) and the expr
448                    //      of a PUSH has to be non_failing.
449                    // - "POP_ALL", "PEEK_ALL" => false
450                    //      same as "POP", "PEEK" unless the following:
451                    //      BUG: if the stack is empty they are non_failing
452                    // - "DROP" => false
453                    // - "ANY", "ASCII_*", UNICODE categories, "NEWLINE",
454                    //      "SOI", "EOI" => false
455                    // - referring to another rule that is undefined (breaks assumption)
456                    //      WARNING: might want to introduce a panic or report the error
457                    false
458                }
459            } else {
460                // referring to another rule R that was already seen
461                // WARNING: this might mean there is a circular non-failing path
462                //   it's not obvious wether this can happen without left-recursion
463                //   and thus breaking the assumption. Until there is answer to
464                //   this, to avoid changing behaviour we return:
465                false
466            }
467        }
468        ParserExpr::Opt(_) => true,
469        ParserExpr::Rep(_) => true,
470        ParserExpr::RepMax(_, _) => true,
471        ParserExpr::Seq(ref lhs, ref rhs) => {
472            is_non_failing(&lhs.expr, rules, trace) && is_non_failing(&rhs.expr, rules, trace)
473        }
474        ParserExpr::Choice(ref lhs, ref rhs) => {
475            is_non_failing(&lhs.expr, rules, trace) || is_non_failing(&rhs.expr, rules, trace)
476        }
477        // it either always fail
478        // or always match at least a character
479        ParserExpr::Range(_, _) => false,
480        ParserExpr::PeekSlice(_, _) => {
481            // the slice being checked is not non_failing since every
482            // PUSH is being checked (assumption 4) and the expr
483            // of a PUSH has to be non_failing.
484            // BUG: if the slice is of size 0, or the stack is not large
485            // enough it might be non-failing
486            false
487        }
488        ParserExpr::RepExact(ref inner, min)
489        | ParserExpr::RepMin(ref inner, min)
490        | ParserExpr::RepMinMax(ref inner, min, _) => {
491            min == 0 || is_non_failing(&inner.expr, rules, trace)
492        }
493        // BUG: the predicate may always fail, resulting in this expr non_failing
494        // ex of always failing predicates :
495        //     @{EOI ~ ANY | ANY ~ SOI | &("A") ~ &("B") | 'z'..'a'}
496        ParserExpr::NegPred(_) => false,
497        ParserExpr::RepOnce(ref inner) => is_non_failing(&inner.expr, rules, trace),
498        ParserExpr::Push(ref inner) | ParserExpr::PosPred(ref inner) => {
499            is_non_failing(&inner.expr, rules, trace)
500        }
501        #[cfg(feature = "grammar-extras")]
502        ParserExpr::PushLiteral(_) => true,
503        #[cfg(feature = "grammar-extras")]
504        ParserExpr::NodeTag(ref inner, _) => is_non_failing(&inner.expr, rules, trace),
505    }
506}
507
508fn validate_repetition<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>> {
509    let mut result = vec![];
510    let map = to_hash_map(rules);
511
512    for rule in rules {
513        let mut errors = rule.node
514            .clone()
515            .filter_map_top_down(|node| match node.expr {
516                ParserExpr::Rep(ref other)
517                | ParserExpr::RepOnce(ref other)
518                | ParserExpr::RepMin(ref other, _) => {
519                    if is_non_failing(&other.expr, &map, &mut vec![]) {
520                        Some(Error::new_from_span(
521                            ErrorVariant::CustomError {
522                                message:
523                                    "expression inside repetition cannot fail and will repeat \
524                                     infinitely"
525                                        .to_owned()
526                            },
527                            node.span
528                        ))
529                    } else if is_non_progressing(&other.expr, &map, &mut vec![]) {
530                        Some(Error::new_from_span(
531                            ErrorVariant::CustomError {
532                                message:
533                                    "expression inside repetition is non-progressing and will repeat \
534                                     infinitely"
535                                        .to_owned(),
536                            },
537                            node.span
538                        ))
539                    } else {
540                        None
541                    }
542                }
543                _ => None
544            });
545
546        result.append(&mut errors);
547    }
548
549    result
550}
551
552fn validate_choices<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>> {
553    let mut result = vec![];
554    let map = to_hash_map(rules);
555
556    for rule in rules {
557        let mut errors = rule
558            .node
559            .clone()
560            .filter_map_top_down(|node| match node.expr {
561                ParserExpr::Choice(ref lhs, _) => {
562                    let node = match lhs.expr {
563                        ParserExpr::Choice(_, ref rhs) => rhs,
564                        _ => lhs,
565                    };
566
567                    if is_non_failing(&node.expr, &map, &mut vec![]) {
568                        Some(Error::new_from_span(
569                            ErrorVariant::CustomError {
570                                message:
571                                    "expression cannot fail; following choices cannot be reached"
572                                        .to_owned(),
573                            },
574                            node.span,
575                        ))
576                    } else {
577                        None
578                    }
579                }
580                _ => None,
581            });
582
583        result.append(&mut errors);
584    }
585
586    result
587}
588
589fn validate_whitespace_comment<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>> {
590    let map = to_hash_map(rules);
591
592    rules
593        .iter()
594        .filter_map(|rule| {
595            if rule.name == "WHITESPACE" || rule.name == "COMMENT" {
596                if is_non_failing(&rule.node.expr, &map, &mut vec![]) {
597                    Some(Error::new_from_span(
598                        ErrorVariant::CustomError {
599                            message: format!(
600                                "{} cannot fail and will repeat infinitely",
601                                &rule.name
602                            ),
603                        },
604                        rule.node.span,
605                    ))
606                } else if is_non_progressing(&rule.node.expr, &map, &mut vec![]) {
607                    Some(Error::new_from_span(
608                        ErrorVariant::CustomError {
609                            message: format!(
610                                "{} is non-progressing and will repeat infinitely",
611                                &rule.name
612                            ),
613                        },
614                        rule.node.span,
615                    ))
616                } else {
617                    None
618                }
619            } else {
620                None
621            }
622        })
623        .collect()
624}
625
626fn validate_left_recursion<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>> {
627    left_recursion(to_hash_map(rules))
628}
629
630fn to_hash_map<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> HashMap<String, &'a ParserNode<'i>> {
631    rules.iter().map(|r| (r.name.clone(), &r.node)).collect()
632}
633
634fn left_recursion<'a, 'i: 'a>(rules: HashMap<String, &'a ParserNode<'i>>) -> Vec<Error<Rule>> {
635    fn check_expr<'a, 'i: 'a>(
636        node: &'a ParserNode<'i>,
637        rules: &'a HashMap<String, &ParserNode<'i>>,
638        trace: &mut Vec<String>,
639    ) -> Option<Error<Rule>> {
640        match node.expr.clone() {
641            ParserExpr::Ident(other) => {
642                if trace[0] == other {
643                    trace.push(other);
644                    let chain = trace
645                        .iter()
646                        .map(|ident| ident.as_ref())
647                        .collect::<Vec<_>>()
648                        .join(" -> ");
649
650                    return Some(Error::new_from_span(
651                        ErrorVariant::CustomError {
652                            message: format!(
653                                "rule {} is left-recursive ({}); pest::pratt_parser might be useful \
654                                 in this case",
655                                node.span.as_str(),
656                                chain
657                            )
658                        },
659                        node.span
660                    ));
661                }
662
663                if !trace.contains(&other) {
664                    if let Some(node) = rules.get(&other) {
665                        trace.push(other);
666                        let result = check_expr(node, rules, trace);
667                        trace.pop().unwrap();
668
669                        return result;
670                    }
671                }
672
673                None
674            }
675            ParserExpr::Seq(ref lhs, ref rhs) => {
676                if is_non_failing(&lhs.expr, rules, &mut vec![trace.last().unwrap().clone()])
677                    || is_non_progressing(
678                        &lhs.expr,
679                        rules,
680                        &mut vec![trace.last().unwrap().clone()],
681                    )
682                {
683                    check_expr(rhs, rules, trace)
684                } else {
685                    check_expr(lhs, rules, trace)
686                }
687            }
688            ParserExpr::Choice(ref lhs, ref rhs) => {
689                check_expr(lhs, rules, trace).or_else(|| check_expr(rhs, rules, trace))
690            }
691            ParserExpr::Rep(ref node) => check_expr(node, rules, trace),
692            ParserExpr::RepOnce(ref node) => check_expr(node, rules, trace),
693            ParserExpr::Opt(ref node) => check_expr(node, rules, trace),
694            ParserExpr::PosPred(ref node) => check_expr(node, rules, trace),
695            ParserExpr::NegPred(ref node) => check_expr(node, rules, trace),
696            ParserExpr::Push(ref node) => check_expr(node, rules, trace),
697            _ => None,
698        }
699    }
700
701    let mut errors = vec![];
702
703    for (name, node) in &rules {
704        let name = name.clone();
705
706        if let Some(error) = check_expr(node, &rules, &mut vec![name]) {
707            errors.push(error);
708        }
709    }
710
711    errors
712}
713
714#[cfg(test)]
715mod tests {
716    use super::super::parser::{consume_rules, PestParser};
717    use super::super::unwrap_or_report;
718    use super::*;
719    use pest::Parser;
720
721    #[test]
722    #[should_panic(expected = "grammar error
723
724 --> 1:1
725  |
7261 | ANY = { \"a\" }
727  | ^-^
728  |
729  = ANY is a pest keyword")]
730    fn pest_keyword() {
731        let input = "ANY = { \"a\" }";
732        unwrap_or_report(validate_pairs(
733            PestParser::parse(Rule::grammar_rules, input).unwrap(),
734        ));
735    }
736
737    #[test]
738    #[should_panic(expected = "grammar error
739
740 --> 1:13
741  |
7421 | a = { \"a\" } a = { \"a\" }
743  |             ^
744  |
745  = rule a already defined")]
746    fn already_defined() {
747        let input = "a = { \"a\" } a = { \"a\" }";
748        unwrap_or_report(validate_pairs(
749            PestParser::parse(Rule::grammar_rules, input).unwrap(),
750        ));
751    }
752
753    #[test]
754    #[should_panic(expected = "grammar error
755
756 --> 1:7
757  |
7581 | a = { b }
759  |       ^
760  |
761  = rule b is undefined")]
762    fn undefined() {
763        let input = "a = { b }";
764        unwrap_or_report(validate_pairs(
765            PestParser::parse(Rule::grammar_rules, input).unwrap(),
766        ));
767    }
768
769    #[test]
770    fn valid_recursion() {
771        let input = "a = { \"\" ~ \"a\"? ~ \"a\"* ~ (\"a\" | \"b\") ~ a }";
772        unwrap_or_report(consume_rules(
773            PestParser::parse(Rule::grammar_rules, input).unwrap(),
774        ));
775    }
776
777    #[test]
778    #[should_panic(expected = "grammar error
779
780 --> 1:16
781  |
7821 | WHITESPACE = { \"\" }
783  |                ^^
784  |
785  = WHITESPACE cannot fail and will repeat infinitely")]
786    fn non_failing_whitespace() {
787        let input = "WHITESPACE = { \"\" }";
788        unwrap_or_report(consume_rules(
789            PestParser::parse(Rule::grammar_rules, input).unwrap(),
790        ));
791    }
792
793    #[test]
794    #[should_panic(expected = "grammar error
795
796 --> 1:13
797  |
7981 | COMMENT = { SOI }
799  |             ^-^
800  |
801  = COMMENT is non-progressing and will repeat infinitely")]
802    fn non_progressing_comment() {
803        let input = "COMMENT = { SOI }";
804        unwrap_or_report(consume_rules(
805            PestParser::parse(Rule::grammar_rules, input).unwrap(),
806        ));
807    }
808
809    #[test]
810    fn non_progressing_empty_string() {
811        assert!(is_non_failing(
812            &ParserExpr::Insens("".into()),
813            &HashMap::new(),
814            &mut Vec::new()
815        ));
816        assert!(is_non_progressing(
817            &ParserExpr::Str("".into()),
818            &HashMap::new(),
819            &mut Vec::new()
820        ));
821    }
822
823    #[test]
824    fn progressing_non_empty_string() {
825        assert!(!is_non_progressing(
826            &ParserExpr::Insens("non empty".into()),
827            &HashMap::new(),
828            &mut Vec::new()
829        ));
830        assert!(!is_non_progressing(
831            &ParserExpr::Str("non empty".into()),
832            &HashMap::new(),
833            &mut Vec::new()
834        ));
835    }
836
837    #[test]
838    fn non_progressing_soi_eoi() {
839        assert!(is_non_progressing(
840            &ParserExpr::Ident("SOI".into()),
841            &HashMap::new(),
842            &mut Vec::new()
843        ));
844        assert!(is_non_progressing(
845            &ParserExpr::Ident("EOI".into()),
846            &HashMap::new(),
847            &mut Vec::new()
848        ));
849    }
850
851    #[test]
852    fn non_progressing_predicates() {
853        let progressing = ParserExpr::Str("A".into());
854
855        assert!(is_non_progressing(
856            &ParserExpr::PosPred(Box::new(ParserNode {
857                expr: progressing.clone(),
858                span: Span::new(" ", 0, 1).unwrap(),
859            })),
860            &HashMap::new(),
861            &mut Vec::new()
862        ));
863        assert!(is_non_progressing(
864            &ParserExpr::NegPred(Box::new(ParserNode {
865                expr: progressing,
866                span: Span::new(" ", 0, 1).unwrap(),
867            })),
868            &HashMap::new(),
869            &mut Vec::new()
870        ));
871    }
872
873    #[test]
874    fn non_progressing_0_length_repetitions() {
875        let input_progressing_node = Box::new(ParserNode {
876            expr: ParserExpr::Str("A".into()),
877            span: Span::new(" ", 0, 1).unwrap(),
878        });
879
880        assert!(!is_non_progressing(
881            &input_progressing_node.clone().expr,
882            &HashMap::new(),
883            &mut Vec::new()
884        ));
885
886        assert!(is_non_progressing(
887            &ParserExpr::Rep(input_progressing_node.clone()),
888            &HashMap::new(),
889            &mut Vec::new()
890        ));
891        assert!(is_non_progressing(
892            &ParserExpr::Opt(input_progressing_node.clone()),
893            &HashMap::new(),
894            &mut Vec::new()
895        ));
896        assert!(is_non_progressing(
897            &ParserExpr::RepExact(input_progressing_node.clone(), 0),
898            &HashMap::new(),
899            &mut Vec::new()
900        ));
901        assert!(is_non_progressing(
902            &ParserExpr::RepMin(input_progressing_node.clone(), 0),
903            &HashMap::new(),
904            &mut Vec::new()
905        ));
906        assert!(is_non_progressing(
907            &ParserExpr::RepMax(input_progressing_node.clone(), 0),
908            &HashMap::new(),
909            &mut Vec::new()
910        ));
911        assert!(is_non_progressing(
912            &ParserExpr::RepMax(input_progressing_node.clone(), 17),
913            &HashMap::new(),
914            &mut Vec::new()
915        ));
916
917        assert!(is_non_progressing(
918            &ParserExpr::RepMinMax(input_progressing_node.clone(), 0, 12),
919            &HashMap::new(),
920            &mut Vec::new()
921        ));
922    }
923
924    #[test]
925    fn non_progressing_nonzero_repetitions_with_non_progressing_expr() {
926        let a = "";
927        let non_progressing_node = Box::new(ParserNode {
928            expr: ParserExpr::Str(a.into()),
929            span: Span::new(a, 0, 0).unwrap(),
930        });
931        let exact = ParserExpr::RepExact(non_progressing_node.clone(), 7);
932        let min = ParserExpr::RepMin(non_progressing_node.clone(), 23);
933        let minmax = ParserExpr::RepMinMax(non_progressing_node.clone(), 12, 13);
934        let reponce = ParserExpr::RepOnce(non_progressing_node);
935
936        assert!(is_non_progressing(&exact, &HashMap::new(), &mut Vec::new()));
937        assert!(is_non_progressing(&min, &HashMap::new(), &mut Vec::new()));
938        assert!(is_non_progressing(
939            &minmax,
940            &HashMap::new(),
941            &mut Vec::new()
942        ));
943        assert!(is_non_progressing(
944            &reponce,
945            &HashMap::new(),
946            &mut Vec::new()
947        ));
948    }
949
950    #[test]
951    fn progressing_repetitions() {
952        let a = "A";
953        let input_progressing_node = Box::new(ParserNode {
954            expr: ParserExpr::Str(a.into()),
955            span: Span::new(a, 0, 1).unwrap(),
956        });
957        let exact = ParserExpr::RepExact(input_progressing_node.clone(), 1);
958        let min = ParserExpr::RepMin(input_progressing_node.clone(), 2);
959        let minmax = ParserExpr::RepMinMax(input_progressing_node.clone(), 4, 5);
960        let reponce = ParserExpr::RepOnce(input_progressing_node);
961
962        assert!(!is_non_progressing(
963            &exact,
964            &HashMap::new(),
965            &mut Vec::new()
966        ));
967        assert!(!is_non_progressing(&min, &HashMap::new(), &mut Vec::new()));
968        assert!(!is_non_progressing(
969            &minmax,
970            &HashMap::new(),
971            &mut Vec::new()
972        ));
973        assert!(!is_non_progressing(
974            &reponce,
975            &HashMap::new(),
976            &mut Vec::new()
977        ));
978    }
979
980    #[test]
981    fn non_progressing_push() {
982        let a = "";
983        let non_progressing_node = Box::new(ParserNode {
984            expr: ParserExpr::Str(a.into()),
985            span: Span::new(a, 0, 0).unwrap(),
986        });
987        let push = ParserExpr::Push(non_progressing_node.clone());
988
989        assert!(is_non_progressing(&push, &HashMap::new(), &mut Vec::new()));
990    }
991
992    #[test]
993    fn progressing_push() {
994        let a = "i'm make progress";
995        let progressing_node = Box::new(ParserNode {
996            expr: ParserExpr::Str(a.into()),
997            span: Span::new(a, 0, 1).unwrap(),
998        });
999        let push = ParserExpr::Push(progressing_node.clone());
1000
1001        assert!(!is_non_progressing(&push, &HashMap::new(), &mut Vec::new()));
1002    }
1003
1004    #[cfg(feature = "grammar-extras")]
1005    #[test]
1006    fn push_literal_is_non_progressing() {
1007        let a = "";
1008        let non_progressing_node = Box::new(ParserNode {
1009            expr: ParserExpr::PushLiteral("a".to_string()),
1010            span: Span::new(a, 0, 0).unwrap(),
1011        });
1012        let push = ParserExpr::Push(non_progressing_node.clone());
1013
1014        assert!(is_non_progressing(&push, &HashMap::new(), &mut Vec::new()));
1015    }
1016
1017    #[test]
1018    fn node_tag_forwards_is_non_progressing() {
1019        let progressing_node = Box::new(ParserNode {
1020            expr: ParserExpr::Str("i'm make progress".into()),
1021            span: Span::new(" ", 0, 1).unwrap(),
1022        });
1023        assert!(!is_non_progressing(
1024            &progressing_node.clone().expr,
1025            &HashMap::new(),
1026            &mut Vec::new()
1027        ));
1028        let non_progressing_node = Box::new(ParserNode {
1029            expr: ParserExpr::Str("".into()),
1030            span: Span::new(" ", 0, 1).unwrap(),
1031        });
1032        assert!(is_non_progressing(
1033            &non_progressing_node.clone().expr,
1034            &HashMap::new(),
1035            &mut Vec::new()
1036        ));
1037        #[cfg(feature = "grammar-extras")]
1038        {
1039            let progressing = ParserExpr::NodeTag(progressing_node.clone(), "TAG".into());
1040            let non_progressing = ParserExpr::NodeTag(non_progressing_node.clone(), "TAG".into());
1041
1042            assert!(!is_non_progressing(
1043                &progressing,
1044                &HashMap::new(),
1045                &mut Vec::new()
1046            ));
1047            assert!(is_non_progressing(
1048                &non_progressing,
1049                &HashMap::new(),
1050                &mut Vec::new()
1051            ));
1052        }
1053    }
1054
1055    #[test]
1056    fn progressing_range() {
1057        let progressing = ParserExpr::Range("A".into(), "Z".into());
1058        let failing_is_progressing = ParserExpr::Range("Z".into(), "A".into());
1059
1060        assert!(!is_non_progressing(
1061            &progressing,
1062            &HashMap::new(),
1063            &mut Vec::new()
1064        ));
1065        assert!(!is_non_progressing(
1066            &failing_is_progressing,
1067            &HashMap::new(),
1068            &mut Vec::new()
1069        ));
1070    }
1071
1072    #[test]
1073    fn progressing_choice() {
1074        let left_progressing_node = Box::new(ParserNode {
1075            expr: ParserExpr::Str("i'm make progress".into()),
1076            span: Span::new(" ", 0, 1).unwrap(),
1077        });
1078        assert!(!is_non_progressing(
1079            &left_progressing_node.clone().expr,
1080            &HashMap::new(),
1081            &mut Vec::new()
1082        ));
1083
1084        let right_progressing_node = Box::new(ParserNode {
1085            expr: ParserExpr::Ident("DROP".into()),
1086            span: Span::new("DROP", 0, 3).unwrap(),
1087        });
1088
1089        assert!(!is_non_progressing(
1090            &ParserExpr::Choice(left_progressing_node, right_progressing_node),
1091            &HashMap::new(),
1092            &mut Vec::new()
1093        ))
1094    }
1095
1096    #[test]
1097    fn non_progressing_choices() {
1098        let left_progressing_node = Box::new(ParserNode {
1099            expr: ParserExpr::Str("i'm make progress".into()),
1100            span: Span::new(" ", 0, 1).unwrap(),
1101        });
1102
1103        assert!(!is_non_progressing(
1104            &left_progressing_node.clone().expr,
1105            &HashMap::new(),
1106            &mut Vec::new()
1107        ));
1108
1109        let left_non_progressing_node = Box::new(ParserNode {
1110            expr: ParserExpr::Str("".into()),
1111            span: Span::new(" ", 0, 1).unwrap(),
1112        });
1113
1114        assert!(is_non_progressing(
1115            &left_non_progressing_node.clone().expr,
1116            &HashMap::new(),
1117            &mut Vec::new()
1118        ));
1119
1120        let right_progressing_node = Box::new(ParserNode {
1121            expr: ParserExpr::Ident("DROP".into()),
1122            span: Span::new("DROP", 0, 3).unwrap(),
1123        });
1124
1125        assert!(!is_non_progressing(
1126            &right_progressing_node.clone().expr,
1127            &HashMap::new(),
1128            &mut Vec::new()
1129        ));
1130
1131        let right_non_progressing_node = Box::new(ParserNode {
1132            expr: ParserExpr::Opt(Box::new(ParserNode {
1133                expr: ParserExpr::Str("   ".into()),
1134                span: Span::new(" ", 0, 1).unwrap(),
1135            })),
1136            span: Span::new(" ", 0, 1).unwrap(),
1137        });
1138
1139        assert!(is_non_progressing(
1140            &right_non_progressing_node.clone().expr,
1141            &HashMap::new(),
1142            &mut Vec::new()
1143        ));
1144
1145        assert!(is_non_progressing(
1146            &ParserExpr::Choice(left_non_progressing_node.clone(), right_progressing_node),
1147            &HashMap::new(),
1148            &mut Vec::new()
1149        ));
1150        assert!(is_non_progressing(
1151            &ParserExpr::Choice(left_progressing_node, right_non_progressing_node.clone()),
1152            &HashMap::new(),
1153            &mut Vec::new()
1154        ));
1155        assert!(is_non_progressing(
1156            &ParserExpr::Choice(left_non_progressing_node, right_non_progressing_node),
1157            &HashMap::new(),
1158            &mut Vec::new()
1159        ))
1160    }
1161
1162    #[test]
1163    fn non_progressing_seq() {
1164        let left_non_progressing_node = Box::new(ParserNode {
1165            expr: ParserExpr::Str("".into()),
1166            span: Span::new(" ", 0, 1).unwrap(),
1167        });
1168
1169        let right_non_progressing_node = Box::new(ParserNode {
1170            expr: ParserExpr::Opt(Box::new(ParserNode {
1171                expr: ParserExpr::Str("   ".into()),
1172                span: Span::new(" ", 0, 1).unwrap(),
1173            })),
1174            span: Span::new(" ", 0, 1).unwrap(),
1175        });
1176
1177        assert!(is_non_progressing(
1178            &ParserExpr::Seq(left_non_progressing_node, right_non_progressing_node),
1179            &HashMap::new(),
1180            &mut Vec::new()
1181        ))
1182    }
1183
1184    #[test]
1185    fn progressing_seqs() {
1186        let left_progressing_node = Box::new(ParserNode {
1187            expr: ParserExpr::Str("i'm make progress".into()),
1188            span: Span::new(" ", 0, 1).unwrap(),
1189        });
1190
1191        assert!(!is_non_progressing(
1192            &left_progressing_node.clone().expr,
1193            &HashMap::new(),
1194            &mut Vec::new()
1195        ));
1196
1197        let left_non_progressing_node = Box::new(ParserNode {
1198            expr: ParserExpr::Str("".into()),
1199            span: Span::new(" ", 0, 1).unwrap(),
1200        });
1201
1202        assert!(is_non_progressing(
1203            &left_non_progressing_node.clone().expr,
1204            &HashMap::new(),
1205            &mut Vec::new()
1206        ));
1207
1208        let right_progressing_node = Box::new(ParserNode {
1209            expr: ParserExpr::Ident("DROP".into()),
1210            span: Span::new("DROP", 0, 3).unwrap(),
1211        });
1212
1213        assert!(!is_non_progressing(
1214            &right_progressing_node.clone().expr,
1215            &HashMap::new(),
1216            &mut Vec::new()
1217        ));
1218
1219        let right_non_progressing_node = Box::new(ParserNode {
1220            expr: ParserExpr::Opt(Box::new(ParserNode {
1221                expr: ParserExpr::Str("   ".into()),
1222                span: Span::new(" ", 0, 1).unwrap(),
1223            })),
1224            span: Span::new(" ", 0, 1).unwrap(),
1225        });
1226
1227        assert!(is_non_progressing(
1228            &right_non_progressing_node.clone().expr,
1229            &HashMap::new(),
1230            &mut Vec::new()
1231        ));
1232
1233        assert!(!is_non_progressing(
1234            &ParserExpr::Seq(left_non_progressing_node, right_progressing_node.clone()),
1235            &HashMap::new(),
1236            &mut Vec::new()
1237        ));
1238        assert!(!is_non_progressing(
1239            &ParserExpr::Seq(left_progressing_node.clone(), right_non_progressing_node),
1240            &HashMap::new(),
1241            &mut Vec::new()
1242        ));
1243        assert!(!is_non_progressing(
1244            &ParserExpr::Seq(left_progressing_node, right_progressing_node),
1245            &HashMap::new(),
1246            &mut Vec::new()
1247        ))
1248    }
1249
1250    #[test]
1251    fn progressing_stack_operations() {
1252        assert!(!is_non_progressing(
1253            &ParserExpr::Ident("DROP".into()),
1254            &HashMap::new(),
1255            &mut Vec::new()
1256        ));
1257        assert!(!is_non_progressing(
1258            &ParserExpr::Ident("PEEK".into()),
1259            &HashMap::new(),
1260            &mut Vec::new()
1261        ));
1262        assert!(!is_non_progressing(
1263            &ParserExpr::Ident("POP".into()),
1264            &HashMap::new(),
1265            &mut Vec::new()
1266        ))
1267    }
1268
1269    #[test]
1270    fn non_failing_string() {
1271        let insens = ParserExpr::Insens("".into());
1272        let string = ParserExpr::Str("".into());
1273
1274        assert!(is_non_failing(&insens, &HashMap::new(), &mut Vec::new()));
1275
1276        assert!(is_non_failing(&string, &HashMap::new(), &mut Vec::new()))
1277    }
1278
1279    #[test]
1280    fn failing_string() {
1281        assert!(!is_non_failing(
1282            &ParserExpr::Insens("i may fail!".into()),
1283            &HashMap::new(),
1284            &mut Vec::new()
1285        ));
1286        assert!(!is_non_failing(
1287            &ParserExpr::Str("failure is not fatal".into()),
1288            &HashMap::new(),
1289            &mut Vec::new()
1290        ))
1291    }
1292
1293    #[test]
1294    fn failing_stack_operations() {
1295        assert!(!is_non_failing(
1296            &ParserExpr::Ident("DROP".into()),
1297            &HashMap::new(),
1298            &mut Vec::new()
1299        ));
1300        assert!(!is_non_failing(
1301            &ParserExpr::Ident("POP".into()),
1302            &HashMap::new(),
1303            &mut Vec::new()
1304        ));
1305        assert!(!is_non_failing(
1306            &ParserExpr::Ident("PEEK".into()),
1307            &HashMap::new(),
1308            &mut Vec::new()
1309        ))
1310    }
1311
1312    #[test]
1313    fn non_failing_zero_length_repetitions() {
1314        let failing = Box::new(ParserNode {
1315            expr: ParserExpr::Range("A".into(), "B".into()),
1316            span: Span::new(" ", 0, 1).unwrap(),
1317        });
1318        assert!(!is_non_failing(
1319            &failing.clone().expr,
1320            &HashMap::new(),
1321            &mut Vec::new()
1322        ));
1323        assert!(is_non_failing(
1324            &ParserExpr::Opt(failing.clone()),
1325            &HashMap::new(),
1326            &mut Vec::new()
1327        ));
1328        assert!(is_non_failing(
1329            &ParserExpr::Rep(failing.clone()),
1330            &HashMap::new(),
1331            &mut Vec::new()
1332        ));
1333        assert!(is_non_failing(
1334            &ParserExpr::RepExact(failing.clone(), 0),
1335            &HashMap::new(),
1336            &mut Vec::new()
1337        ));
1338        assert!(is_non_failing(
1339            &ParserExpr::RepMin(failing.clone(), 0),
1340            &HashMap::new(),
1341            &mut Vec::new()
1342        ));
1343        assert!(is_non_failing(
1344            &ParserExpr::RepMax(failing.clone(), 0),
1345            &HashMap::new(),
1346            &mut Vec::new()
1347        ));
1348        assert!(is_non_failing(
1349            &ParserExpr::RepMax(failing.clone(), 22),
1350            &HashMap::new(),
1351            &mut Vec::new()
1352        ));
1353        assert!(is_non_failing(
1354            &ParserExpr::RepMinMax(failing.clone(), 0, 73),
1355            &HashMap::new(),
1356            &mut Vec::new()
1357        ));
1358    }
1359
1360    #[test]
1361    fn non_failing_non_zero_repetitions_with_non_failing_expr() {
1362        let non_failing = Box::new(ParserNode {
1363            expr: ParserExpr::Opt(Box::new(ParserNode {
1364                expr: ParserExpr::Range("A".into(), "B".into()),
1365                span: Span::new(" ", 0, 1).unwrap(),
1366            })),
1367            span: Span::new(" ", 0, 1).unwrap(),
1368        });
1369        assert!(is_non_failing(
1370            &non_failing.clone().expr,
1371            &HashMap::new(),
1372            &mut Vec::new()
1373        ));
1374        assert!(is_non_failing(
1375            &ParserExpr::RepOnce(non_failing.clone()),
1376            &HashMap::new(),
1377            &mut Vec::new()
1378        ));
1379        assert!(is_non_failing(
1380            &ParserExpr::RepExact(non_failing.clone(), 1),
1381            &HashMap::new(),
1382            &mut Vec::new()
1383        ));
1384        assert!(is_non_failing(
1385            &ParserExpr::RepMin(non_failing.clone(), 6),
1386            &HashMap::new(),
1387            &mut Vec::new()
1388        ));
1389        assert!(is_non_failing(
1390            &ParserExpr::RepMinMax(non_failing.clone(), 32, 73),
1391            &HashMap::new(),
1392            &mut Vec::new()
1393        ));
1394    }
1395
1396    #[test]
1397    #[cfg(feature = "grammar-extras")]
1398    fn failing_non_zero_repetitions() {
1399        let failing = Box::new(ParserNode {
1400            expr: ParserExpr::NodeTag(
1401                Box::new(ParserNode {
1402                    expr: ParserExpr::Range("A".into(), "B".into()),
1403                    span: Span::new(" ", 0, 1).unwrap(),
1404                }),
1405                "Tag".into(),
1406            ),
1407            span: Span::new(" ", 0, 1).unwrap(),
1408        });
1409        assert!(!is_non_failing(
1410            &failing.clone().expr,
1411            &HashMap::new(),
1412            &mut Vec::new()
1413        ));
1414        assert!(!is_non_failing(
1415            &ParserExpr::RepOnce(failing.clone()),
1416            &HashMap::new(),
1417            &mut Vec::new()
1418        ));
1419        assert!(!is_non_failing(
1420            &ParserExpr::RepExact(failing.clone(), 3),
1421            &HashMap::new(),
1422            &mut Vec::new()
1423        ));
1424        assert!(!is_non_failing(
1425            &ParserExpr::RepMin(failing.clone(), 14),
1426            &HashMap::new(),
1427            &mut Vec::new()
1428        ));
1429        assert!(!is_non_failing(
1430            &ParserExpr::RepMinMax(failing.clone(), 47, 73),
1431            &HashMap::new(),
1432            &mut Vec::new()
1433        ));
1434    }
1435
1436    #[test]
1437    fn failing_choice() {
1438        let left_failing_node = Box::new(ParserNode {
1439            expr: ParserExpr::Str("i'm a failure".into()),
1440            span: Span::new(" ", 0, 1).unwrap(),
1441        });
1442        assert!(!is_non_failing(
1443            &left_failing_node.clone().expr,
1444            &HashMap::new(),
1445            &mut Vec::new()
1446        ));
1447
1448        let right_failing_node = Box::new(ParserNode {
1449            expr: ParserExpr::Ident("DROP".into()),
1450            span: Span::new("DROP", 0, 3).unwrap(),
1451        });
1452
1453        assert!(!is_non_failing(
1454            &ParserExpr::Choice(left_failing_node, right_failing_node),
1455            &HashMap::new(),
1456            &mut Vec::new()
1457        ))
1458    }
1459
1460    #[test]
1461    fn non_failing_choices() {
1462        let left_failing_node = Box::new(ParserNode {
1463            expr: ParserExpr::Str("i'm a failure".into()),
1464            span: Span::new(" ", 0, 1).unwrap(),
1465        });
1466
1467        assert!(!is_non_failing(
1468            &left_failing_node.clone().expr,
1469            &HashMap::new(),
1470            &mut Vec::new()
1471        ));
1472
1473        let left_non_failing_node = Box::new(ParserNode {
1474            expr: ParserExpr::Str("".into()),
1475            span: Span::new(" ", 0, 1).unwrap(),
1476        });
1477
1478        assert!(is_non_failing(
1479            &left_non_failing_node.clone().expr,
1480            &HashMap::new(),
1481            &mut Vec::new()
1482        ));
1483
1484        let right_failing_node = Box::new(ParserNode {
1485            expr: ParserExpr::Ident("DROP".into()),
1486            span: Span::new("DROP", 0, 3).unwrap(),
1487        });
1488
1489        assert!(!is_non_failing(
1490            &right_failing_node.clone().expr,
1491            &HashMap::new(),
1492            &mut Vec::new()
1493        ));
1494
1495        let right_non_failing_node = Box::new(ParserNode {
1496            expr: ParserExpr::Opt(Box::new(ParserNode {
1497                expr: ParserExpr::Str("   ".into()),
1498                span: Span::new(" ", 0, 1).unwrap(),
1499            })),
1500            span: Span::new(" ", 0, 1).unwrap(),
1501        });
1502
1503        assert!(is_non_failing(
1504            &right_non_failing_node.clone().expr,
1505            &HashMap::new(),
1506            &mut Vec::new()
1507        ));
1508
1509        assert!(is_non_failing(
1510            &ParserExpr::Choice(left_non_failing_node.clone(), right_failing_node),
1511            &HashMap::new(),
1512            &mut Vec::new()
1513        ));
1514        assert!(is_non_failing(
1515            &ParserExpr::Choice(left_failing_node, right_non_failing_node.clone()),
1516            &HashMap::new(),
1517            &mut Vec::new()
1518        ));
1519        assert!(is_non_failing(
1520            &ParserExpr::Choice(left_non_failing_node, right_non_failing_node),
1521            &HashMap::new(),
1522            &mut Vec::new()
1523        ))
1524    }
1525
1526    #[test]
1527    fn non_failing_seq() {
1528        let left_non_failing_node = Box::new(ParserNode {
1529            expr: ParserExpr::Str("".into()),
1530            span: Span::new(" ", 0, 1).unwrap(),
1531        });
1532
1533        let right_non_failing_node = Box::new(ParserNode {
1534            expr: ParserExpr::Opt(Box::new(ParserNode {
1535                expr: ParserExpr::Str("   ".into()),
1536                span: Span::new(" ", 0, 1).unwrap(),
1537            })),
1538            span: Span::new(" ", 0, 1).unwrap(),
1539        });
1540
1541        assert!(is_non_failing(
1542            &ParserExpr::Seq(left_non_failing_node, right_non_failing_node),
1543            &HashMap::new(),
1544            &mut Vec::new()
1545        ))
1546    }
1547
1548    #[test]
1549    fn failing_seqs() {
1550        let left_failing_node = Box::new(ParserNode {
1551            expr: ParserExpr::Str("i'm a failure".into()),
1552            span: Span::new(" ", 0, 1).unwrap(),
1553        });
1554
1555        assert!(!is_non_failing(
1556            &left_failing_node.clone().expr,
1557            &HashMap::new(),
1558            &mut Vec::new()
1559        ));
1560
1561        let left_non_failing_node = Box::new(ParserNode {
1562            expr: ParserExpr::Str("".into()),
1563            span: Span::new(" ", 0, 1).unwrap(),
1564        });
1565
1566        assert!(is_non_failing(
1567            &left_non_failing_node.clone().expr,
1568            &HashMap::new(),
1569            &mut Vec::new()
1570        ));
1571
1572        let right_failing_node = Box::new(ParserNode {
1573            expr: ParserExpr::Ident("DROP".into()),
1574            span: Span::new("DROP", 0, 3).unwrap(),
1575        });
1576
1577        assert!(!is_non_failing(
1578            &right_failing_node.clone().expr,
1579            &HashMap::new(),
1580            &mut Vec::new()
1581        ));
1582
1583        let right_non_failing_node = Box::new(ParserNode {
1584            expr: ParserExpr::Opt(Box::new(ParserNode {
1585                expr: ParserExpr::Str("   ".into()),
1586                span: Span::new(" ", 0, 1).unwrap(),
1587            })),
1588            span: Span::new(" ", 0, 1).unwrap(),
1589        });
1590
1591        assert!(is_non_failing(
1592            &right_non_failing_node.clone().expr,
1593            &HashMap::new(),
1594            &mut Vec::new()
1595        ));
1596
1597        assert!(!is_non_failing(
1598            &ParserExpr::Seq(left_non_failing_node, right_failing_node.clone()),
1599            &HashMap::new(),
1600            &mut Vec::new()
1601        ));
1602        assert!(!is_non_failing(
1603            &ParserExpr::Seq(left_failing_node.clone(), right_non_failing_node),
1604            &HashMap::new(),
1605            &mut Vec::new()
1606        ));
1607        assert!(!is_non_failing(
1608            &ParserExpr::Seq(left_failing_node, right_failing_node),
1609            &HashMap::new(),
1610            &mut Vec::new()
1611        ))
1612    }
1613
1614    #[test]
1615    fn failing_range() {
1616        let failing = ParserExpr::Range("A".into(), "Z".into());
1617        let always_failing = ParserExpr::Range("Z".into(), "A".into());
1618
1619        assert!(!is_non_failing(&failing, &HashMap::new(), &mut Vec::new()));
1620        assert!(!is_non_failing(
1621            &always_failing,
1622            &HashMap::new(),
1623            &mut Vec::new()
1624        ));
1625    }
1626
1627    #[test]
1628    fn _push_node_tag_pos_pred_forwarding_is_non_failing() {
1629        let failing_node = Box::new(ParserNode {
1630            expr: ParserExpr::Str("i'm a failure".into()),
1631            span: Span::new(" ", 0, 1).unwrap(),
1632        });
1633        assert!(!is_non_failing(
1634            &failing_node.clone().expr,
1635            &HashMap::new(),
1636            &mut Vec::new()
1637        ));
1638        let non_failing_node = Box::new(ParserNode {
1639            expr: ParserExpr::Str("".into()),
1640            span: Span::new(" ", 0, 1).unwrap(),
1641        });
1642        assert!(is_non_failing(
1643            &non_failing_node.clone().expr,
1644            &HashMap::new(),
1645            &mut Vec::new()
1646        ));
1647
1648        #[cfg(feature = "grammar-extras")]
1649        {
1650            assert!(!is_non_failing(
1651                &ParserExpr::NodeTag(failing_node.clone(), "TAG".into()),
1652                &HashMap::new(),
1653                &mut Vec::new()
1654            ));
1655            assert!(is_non_failing(
1656                &ParserExpr::NodeTag(non_failing_node.clone(), "TAG".into()),
1657                &HashMap::new(),
1658                &mut Vec::new()
1659            ));
1660        }
1661
1662        assert!(!is_non_failing(
1663            &ParserExpr::Push(failing_node.clone()),
1664            &HashMap::new(),
1665            &mut Vec::new()
1666        ));
1667        assert!(is_non_failing(
1668            &ParserExpr::Push(non_failing_node.clone()),
1669            &HashMap::new(),
1670            &mut Vec::new()
1671        ));
1672
1673        assert!(!is_non_failing(
1674            &ParserExpr::PosPred(failing_node.clone()),
1675            &HashMap::new(),
1676            &mut Vec::new()
1677        ));
1678        assert!(is_non_failing(
1679            &ParserExpr::PosPred(non_failing_node.clone()),
1680            &HashMap::new(),
1681            &mut Vec::new()
1682        ));
1683    }
1684
1685    #[cfg(feature = "grammar-extras")]
1686    #[test]
1687    fn push_literal_is_non_failing() {
1688        assert!(is_non_failing(
1689            &ParserExpr::PushLiteral("a".to_string()),
1690            &HashMap::new(),
1691            &mut Vec::new()
1692        ));
1693    }
1694
1695    #[test]
1696    #[should_panic(expected = "grammar error
1697
1698 --> 1:7
1699  |
17001 | a = { (\"\")* }
1701  |       ^---^
1702  |
1703  = expression inside repetition cannot fail and will repeat infinitely")]
1704    fn non_failing_repetition() {
1705        let input = "a = { (\"\")* }";
1706        unwrap_or_report(consume_rules(
1707            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1708        ));
1709    }
1710
1711    #[test]
1712    #[should_panic(expected = "grammar error
1713
1714 --> 1:18
1715  |
17161 | a = { \"\" } b = { a* }
1717  |                  ^^
1718  |
1719  = expression inside repetition cannot fail and will repeat infinitely")]
1720    fn indirect_non_failing_repetition() {
1721        let input = "a = { \"\" } b = { a* }";
1722        unwrap_or_report(consume_rules(
1723            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1724        ));
1725    }
1726
1727    #[test]
1728    #[should_panic(expected = "grammar error
1729
1730 --> 1:20
1731  |
17321 | a = { \"a\" ~ (\"b\" ~ (\"\")*) }
1733  |                    ^---^
1734  |
1735  = expression inside repetition cannot fail and will repeat infinitely")]
1736    fn deep_non_failing_repetition() {
1737        let input = "a = { \"a\" ~ (\"b\" ~ (\"\")*) }";
1738        unwrap_or_report(consume_rules(
1739            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1740        ));
1741    }
1742
1743    #[test]
1744    #[should_panic(expected = "grammar error
1745
1746 --> 1:7
1747  |
17481 | a = { (\"\" ~ &\"a\" ~ !\"a\" ~ (SOI | EOI))* }
1749  |       ^-------------------------------^
1750  |
1751  = expression inside repetition is non-progressing and will repeat infinitely")]
1752    fn non_progressing_repetition() {
1753        let input = "a = { (\"\" ~ &\"a\" ~ !\"a\" ~ (SOI | EOI))* }";
1754        unwrap_or_report(consume_rules(
1755            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1756        ));
1757    }
1758
1759    #[test]
1760    #[should_panic(expected = "grammar error
1761
1762 --> 1:20
1763  |
17641 | a = { !\"a\" } b = { a* }
1765  |                    ^^
1766  |
1767  = expression inside repetition is non-progressing and will repeat infinitely")]
1768    fn indirect_non_progressing_repetition() {
1769        let input = "a = { !\"a\" } b = { a* }";
1770        unwrap_or_report(consume_rules(
1771            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1772        ));
1773    }
1774
1775    #[test]
1776    #[should_panic(expected = "grammar error
1777
1778 --> 1:7
1779  |
17801 | a = { a }
1781  |       ^
1782  |
1783  = rule a is left-recursive (a -> a); pest::pratt_parser might be useful in this case")]
1784    fn simple_left_recursion() {
1785        let input = "a = { a }";
1786        unwrap_or_report(consume_rules(
1787            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1788        ));
1789    }
1790
1791    #[test]
1792    #[should_panic(expected = "grammar error
1793
1794 --> 1:7
1795  |
17961 | a = { b } b = { a }
1797  |       ^
1798  |
1799  = rule b is left-recursive (b -> a -> b); pest::pratt_parser might be useful in this case
1800
1801 --> 1:17
1802  |
18031 | a = { b } b = { a }
1804  |                 ^
1805  |
1806  = rule a is left-recursive (a -> b -> a); pest::pratt_parser might be useful in this case")]
1807    fn indirect_left_recursion() {
1808        let input = "a = { b } b = { a }";
1809        unwrap_or_report(consume_rules(
1810            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1811        ));
1812    }
1813
1814    #[test]
1815    #[should_panic(expected = "grammar error
1816
1817 --> 1:39
1818  |
18191 | a = { \"\" ~ \"a\"? ~ \"a\"* ~ (\"a\" | \"\") ~ a }
1820  |                                       ^
1821  |
1822  = rule a is left-recursive (a -> a); pest::pratt_parser might be useful in this case")]
1823    fn non_failing_left_recursion() {
1824        let input = "a = { \"\" ~ \"a\"? ~ \"a\"* ~ (\"a\" | \"\") ~ a }";
1825        unwrap_or_report(consume_rules(
1826            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1827        ));
1828    }
1829
1830    #[test]
1831    #[should_panic(expected = "grammar error
1832
1833 --> 1:13
1834  |
18351 | a = { \"a\" | a }
1836  |             ^
1837  |
1838  = rule a is left-recursive (a -> a); pest::pratt_parser might be useful in this case")]
1839    fn non_primary_choice_left_recursion() {
1840        let input = "a = { \"a\" | a }";
1841        unwrap_or_report(consume_rules(
1842            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1843        ));
1844    }
1845
1846    #[test]
1847    #[should_panic(expected = "grammar error
1848
1849 --> 1:14
1850  |
18511 | a = { !\"a\" ~ a }
1852  |              ^
1853  |
1854  = rule a is left-recursive (a -> a); pest::pratt_parser might be useful in this case")]
1855    fn non_progressing_left_recursion() {
1856        let input = "a = { !\"a\" ~ a }";
1857        unwrap_or_report(consume_rules(
1858            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1859        ));
1860    }
1861
1862    #[test]
1863    #[should_panic(expected = "grammar error
1864
1865 --> 1:7
1866  |
18671 | a = { \"a\"* | \"a\" | \"b\" }
1868  |       ^--^
1869  |
1870  = expression cannot fail; following choices cannot be reached")]
1871    fn lhs_non_failing_choice() {
1872        let input = "a = { \"a\"* | \"a\" | \"b\" }";
1873        unwrap_or_report(consume_rules(
1874            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1875        ));
1876    }
1877
1878    #[test]
1879    #[should_panic(expected = "grammar error
1880
1881 --> 1:13
1882  |
18831 | a = { \"a\" | \"a\"* | \"b\" }
1884  |             ^--^
1885  |
1886  = expression cannot fail; following choices cannot be reached")]
1887    fn lhs_non_failing_choice_middle() {
1888        let input = "a = { \"a\" | \"a\"* | \"b\" }";
1889        unwrap_or_report(consume_rules(
1890            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1891        ));
1892    }
1893
1894    #[test]
1895    #[should_panic(expected = "grammar error
1896
1897 --> 1:7
1898  |
18991 | a = { b | \"a\" } b = { \"b\"* | \"c\" }
1900  |       ^
1901  |
1902  = expression cannot fail; following choices cannot be reached
1903
1904 --> 1:23
1905  |
19061 | a = { b | \"a\" } b = { \"b\"* | \"c\" }
1907  |                       ^--^
1908  |
1909  = expression cannot fail; following choices cannot be reached")]
1910    fn lhs_non_failing_nested_choices() {
1911        let input = "a = { b | \"a\" } b = { \"b\"* | \"c\" }";
1912        unwrap_or_report(consume_rules(
1913            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1914        ));
1915    }
1916
1917    #[test]
1918    fn skip_can_be_defined() {
1919        let input = "skip = { \"\" }";
1920        unwrap_or_report(consume_rules(
1921            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1922        ));
1923    }
1924
1925    #[test]
1926    #[should_panic(expected = "grammar error
1927
1928 --> 1:7
1929  |
19301 | a = { #b = b } b = _{ ASCII_DIGIT+ }
1931  |       ^----^
1932  |
1933  = tags on silent rules will not appear in the output")]
1934    #[cfg(feature = "grammar-extras")]
1935    fn tag_on_silent_rule() {
1936        let input = "a = { #b = b } b = _{ ASCII_DIGIT+ }";
1937        unwrap_or_report(consume_rules(
1938            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1939        ));
1940    }
1941
1942    #[test]
1943    #[should_panic(expected = "grammar error
1944
1945 --> 1:7
1946  |
19471 | a = { #b = ASCII_DIGIT+ }
1948  |       ^---------------^
1949  |
1950  = tags on built-in rules will not appear in the output")]
1951    #[cfg(feature = "grammar-extras")]
1952    fn tag_on_builtin_rule() {
1953        let input = "a = { #b = ASCII_DIGIT+ }";
1954        unwrap_or_report(consume_rules(
1955            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1956        ));
1957    }
1958
1959    #[test]
1960    #[cfg(feature = "grammar-extras")]
1961    fn tag_on_normal_rule() {
1962        let input = "a = { #b = b } b = { ASCII_DIGIT+ }";
1963        unwrap_or_report(consume_rules(
1964            PestParser::parse(Rule::grammar_rules, input).unwrap(),
1965        ));
1966    }
1967}