pest_meta/
validator.rs

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

pest_meta/
validator.rs
