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> = vec![];
124
125 for definition: &Span<'_> in definitions {
126 let name: &str = definition.as_str();
127
128 if RUST_KEYWORDS.contains(name) {
129 errors.push(Error::new_from_span(
130 variant: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> = vec![];
145
146 for definition: &Span<'_> in definitions {
147 let name: &str = definition.as_str();
148
149 if PEST_KEYWORDS.contains(name) {
150 errors.push(Error::new_from_span(
151 variant: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> = vec![];
166 let mut defined: HashSet<&str> = HashSet::new();
167
168 for definition: &Span<'_> in definitions {
169 let name: &str = definition.as_str();
170
171 if defined.contains(&name) {
172 errors.push(Error::new_from_span(
173 variant: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> = vec![];
193 let definitions: HashSet<_> = definitions.iter().map(|span: &Span<'_>| span.as_str()).collect();
194
195 for rule: &Span<'_> in called_rules {
196 let name: &str = rule.as_str();
197
198 if !definitions.contains(name) && !BUILTINS.contains(name) {
199 errors.push(Error::new_from_span(
200 variant: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> = 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(iter:validate_repetition(rules));
226 errors.extend(iter:validate_choices(rules));
227 errors.extend(iter:validate_whitespace_comment(rules));
228 errors.extend(iter:validate_left_recursion(rules));
229 #[cfg(feature = "grammar-extras")]
230 errors.extend(validate_tag_silent_rules(rules));
231
232 errors.sort_by_key(|error: &Error| match error.location {
233 InputLocation::Span(span: (usize, usize)) => 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 ParserExpr::RepOnce(ref inner) => is_non_progressing(&inner.expr, rules, trace),
404 #[cfg(feature = "grammar-extras")]
405 ParserExpr::NodeTag(ref inner, _) => is_non_progressing(&inner.expr, rules, trace),
406 }
407}
408
409/// Checks if `expr` is non-failing, that is it matches any input.
410///
411/// # Example
412///
413/// ```pest
414/// non_failing_1 = { "" }
415/// ```
416///
417/// # Assumptions
418/// - In `ParserExpr::RepMinMax(inner,min,max)`, `min<=max`
419/// - In `ParserExpr::PeekSlice(max,Some(min))`, `max>=min`
420/// - All rules identiers have a matching definition
421/// - There is no left-recursion
422/// - All rules are being checked
423fn is_non_failing<'i>(
424 expr: &ParserExpr<'i>,
425 rules: &HashMap<String, &ParserNode<'i>>,
426 trace: &mut Vec<String>,
427) -> bool {
428 match *expr {
429 ParserExpr::Str(ref string) | ParserExpr::Insens(ref string) => string.is_empty(),
430 ParserExpr::Ident(ref ident) => {
431 if !trace.contains(ident) {
432 if let Some(node) = rules.get(ident) {
433 trace.push(ident.clone());
434 let result = is_non_failing(&node.expr, rules, trace);
435 trace.pop().unwrap();
436
437 result
438 } else {
439 // else
440 // the ident is
441 // - "POP","PEEK" => false
442 // the slice being checked is not non_failing since every
443 // PUSH is being checked (assumption 4) and the expr
444 // of a PUSH has to be non_failing.
445 // - "POP_ALL", "PEEK_ALL" => false
446 // same as "POP", "PEEK" unless the following:
447 // BUG: if the stack is empty they are non_failing
448 // - "DROP" => false
449 // - "ANY", "ASCII_*", UNICODE categories, "NEWLINE",
450 // "SOI", "EOI" => false
451 // - referring to another rule that is undefined (breaks assumption)
452 // WARNING: might want to introduce a panic or report the error
453 false
454 }
455 } else {
456 // referring to another rule R that was already seen
457 // WARNING: this might mean there is a circular non-failing path
458 // it's not obvious wether this can happen without left-recursion
459 // and thus breaking the assumption. Until there is answer to
460 // this, to avoid changing behaviour we return:
461 false
462 }
463 }
464 ParserExpr::Opt(_) => true,
465 ParserExpr::Rep(_) => true,
466 ParserExpr::RepMax(_, _) => true,
467 ParserExpr::Seq(ref lhs, ref rhs) => {
468 is_non_failing(&lhs.expr, rules, trace) && is_non_failing(&rhs.expr, rules, trace)
469 }
470 ParserExpr::Choice(ref lhs, ref rhs) => {
471 is_non_failing(&lhs.expr, rules, trace) || is_non_failing(&rhs.expr, rules, trace)
472 }
473 // it either always fail
474 // or always match at least a character
475 ParserExpr::Range(_, _) => false,
476 ParserExpr::PeekSlice(_, _) => {
477 // the slice being checked is not non_failing since every
478 // PUSH is being checked (assumption 4) and the expr
479 // of a PUSH has to be non_failing.
480 // BUG: if the slice is of size 0, or the stack is not large
481 // enough it might be non-failing
482 false
483 }
484 ParserExpr::RepExact(ref inner, min)
485 | ParserExpr::RepMin(ref inner, min)
486 | ParserExpr::RepMinMax(ref inner, min, _) => {
487 min == 0 || is_non_failing(&inner.expr, rules, trace)
488 }
489 // BUG: the predicate may always fail, resulting in this expr non_failing
490 // ex of always failing predicates :
491 // @{EOI ~ ANY | ANY ~ SOI | &("A") ~ &("B") | 'z'..'a'}
492 ParserExpr::NegPred(_) => false,
493 ParserExpr::RepOnce(ref inner) => is_non_failing(&inner.expr, rules, trace),
494 ParserExpr::Push(ref inner) | ParserExpr::PosPred(ref inner) => {
495 is_non_failing(&inner.expr, rules, trace)
496 }
497 #[cfg(feature = "grammar-extras")]
498 ParserExpr::NodeTag(ref inner, _) => is_non_failing(&inner.expr, rules, trace),
499 }
500}
501
502fn validate_repetition<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>> {
503 let mut result = vec![];
504 let map = to_hash_map(rules);
505
506 for rule in rules {
507 let mut errors = rule.node
508 .clone()
509 .filter_map_top_down(|node| match node.expr {
510 ParserExpr::Rep(ref other)
511 | ParserExpr::RepOnce(ref other)
512 | ParserExpr::RepMin(ref other, _) => {
513 if is_non_failing(&other.expr, &map, &mut vec![]) {
514 Some(Error::new_from_span(
515 ErrorVariant::CustomError {
516 message:
517 "expression inside repetition cannot fail and will repeat \
518 infinitely"
519 .to_owned()
520 },
521 node.span
522 ))
523 } else if is_non_progressing(&other.expr, &map, &mut vec![]) {
524 Some(Error::new_from_span(
525 ErrorVariant::CustomError {
526 message:
527 "expression inside repetition is non-progressing and will repeat \
528 infinitely"
529 .to_owned(),
530 },
531 node.span
532 ))
533 } else {
534 None
535 }
536 }
537 _ => None
538 });
539
540 result.append(&mut errors);
541 }
542
543 result
544}
545
546fn validate_choices<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>> {
547 let mut result = vec![];
548 let map = to_hash_map(rules);
549
550 for rule in rules {
551 let mut errors = rule
552 .node
553 .clone()
554 .filter_map_top_down(|node| match node.expr {
555 ParserExpr::Choice(ref lhs, _) => {
556 let node = match lhs.expr {
557 ParserExpr::Choice(_, ref rhs) => rhs,
558 _ => lhs,
559 };
560
561 if is_non_failing(&node.expr, &map, &mut vec![]) {
562 Some(Error::new_from_span(
563 ErrorVariant::CustomError {
564 message:
565 "expression cannot fail; following choices cannot be reached"
566 .to_owned(),
567 },
568 node.span,
569 ))
570 } else {
571 None
572 }
573 }
574 _ => None,
575 });
576
577 result.append(&mut errors);
578 }
579
580 result
581}
582
583fn validate_whitespace_comment<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>> {
584 let map = to_hash_map(rules);
585
586 rules
587 .iter()
588 .filter_map(|rule| {
589 if rule.name == "WHITESPACE" || rule.name == "COMMENT" {
590 if is_non_failing(&rule.node.expr, &map, &mut vec![]) {
591 Some(Error::new_from_span(
592 ErrorVariant::CustomError {
593 message: format!(
594 "{} cannot fail and will repeat infinitely",
595 &rule.name
596 ),
597 },
598 rule.node.span,
599 ))
600 } else if is_non_progressing(&rule.node.expr, &map, &mut vec![]) {
601 Some(Error::new_from_span(
602 ErrorVariant::CustomError {
603 message: format!(
604 "{} is non-progressing and will repeat infinitely",
605 &rule.name
606 ),
607 },
608 rule.node.span,
609 ))
610 } else {
611 None
612 }
613 } else {
614 None
615 }
616 })
617 .collect()
618}
619
620fn validate_left_recursion<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>> {
621 left_recursion(rules:to_hash_map(rules))
622}
623
624fn to_hash_map<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> HashMap<String, &'a ParserNode<'i>> {
625 rules.iter().map(|r: &ParserRule<'_>| (r.name.clone(), &r.node)).collect()
626}
627
628fn left_recursion<'a, 'i: 'a>(rules: HashMap<String, &'a ParserNode<'i>>) -> Vec<Error<Rule>> {
629 fn check_expr<'a, 'i: 'a>(
630 node: &'a ParserNode<'i>,
631 rules: &'a HashMap<String, &ParserNode<'i>>,
632 trace: &mut Vec<String>,
633 ) -> Option<Error<Rule>> {
634 match node.expr.clone() {
635 ParserExpr::Ident(other) => {
636 if trace[0] == other {
637 trace.push(other);
638 let chain = trace
639 .iter()
640 .map(|ident| ident.as_ref())
641 .collect::<Vec<_>>()
642 .join(" -> ");
643
644 return Some(Error::new_from_span(
645 ErrorVariant::CustomError {
646 message: format!(
647 "rule {} is left-recursive ({}); pest::pratt_parser might be useful \
648 in this case",
649 node.span.as_str(),
650 chain
651 )
652 },
653 node.span
654 ));
655 }
656
657 if !trace.contains(&other) {
658 if let Some(node) = rules.get(&other) {
659 trace.push(other);
660 let result = check_expr(node, rules, trace);
661 trace.pop().unwrap();
662
663 return result;
664 }
665 }
666
667 None
668 }
669 ParserExpr::Seq(ref lhs, ref rhs) => {
670 if is_non_failing(&lhs.expr, rules, &mut vec![trace.last().unwrap().clone()])
671 || is_non_progressing(
672 &lhs.expr,
673 rules,
674 &mut vec![trace.last().unwrap().clone()],
675 )
676 {
677 check_expr(rhs, rules, trace)
678 } else {
679 check_expr(lhs, rules, trace)
680 }
681 }
682 ParserExpr::Choice(ref lhs, ref rhs) => {
683 check_expr(lhs, rules, trace).or_else(|| check_expr(rhs, rules, trace))
684 }
685 ParserExpr::Rep(ref node) => check_expr(node, rules, trace),
686 ParserExpr::RepOnce(ref node) => check_expr(node, rules, trace),
687 ParserExpr::Opt(ref node) => check_expr(node, rules, trace),
688 ParserExpr::PosPred(ref node) => check_expr(node, rules, trace),
689 ParserExpr::NegPred(ref node) => check_expr(node, rules, trace),
690 ParserExpr::Push(ref node) => check_expr(node, rules, trace),
691 _ => None,
692 }
693 }
694
695 let mut errors = vec![];
696
697 for (name, node) in &rules {
698 let name = name.clone();
699
700 if let Some(error) = check_expr(node, &rules, &mut vec![name]) {
701 errors.push(error);
702 }
703 }
704
705 errors
706}
707
708#[cfg(test)]
709mod tests {
710 use super::super::parser::{consume_rules, PestParser};
711 use super::super::unwrap_or_report;
712 use super::*;
713 use pest::Parser;
714
715 #[test]
716 #[should_panic(expected = "grammar error
717
718 --> 1:1
719 |
7201 | ANY = { \"a\" }
721 | ^-^
722 |
723 = ANY is a pest keyword")]
724 fn pest_keyword() {
725 let input = "ANY = { \"a\" }";
726 unwrap_or_report(validate_pairs(
727 PestParser::parse(Rule::grammar_rules, input).unwrap(),
728 ));
729 }
730
731 #[test]
732 #[should_panic(expected = "grammar error
733
734 --> 1:13
735 |
7361 | a = { \"a\" } a = { \"a\" }
737 | ^
738 |
739 = rule a already defined")]
740 fn already_defined() {
741 let input = "a = { \"a\" } a = { \"a\" }";
742 unwrap_or_report(validate_pairs(
743 PestParser::parse(Rule::grammar_rules, input).unwrap(),
744 ));
745 }
746
747 #[test]
748 #[should_panic(expected = "grammar error
749
750 --> 1:7
751 |
7521 | a = { b }
753 | ^
754 |
755 = rule b is undefined")]
756 fn undefined() {
757 let input = "a = { b }";
758 unwrap_or_report(validate_pairs(
759 PestParser::parse(Rule::grammar_rules, input).unwrap(),
760 ));
761 }
762
763 #[test]
764 fn valid_recursion() {
765 let input = "a = { \"\" ~ \"a\"? ~ \"a\"* ~ (\"a\" | \"b\") ~ a }";
766 unwrap_or_report(consume_rules(
767 PestParser::parse(Rule::grammar_rules, input).unwrap(),
768 ));
769 }
770
771 #[test]
772 #[should_panic(expected = "grammar error
773
774 --> 1:16
775 |
7761 | WHITESPACE = { \"\" }
777 | ^^
778 |
779 = WHITESPACE cannot fail and will repeat infinitely")]
780 fn non_failing_whitespace() {
781 let input = "WHITESPACE = { \"\" }";
782 unwrap_or_report(consume_rules(
783 PestParser::parse(Rule::grammar_rules, input).unwrap(),
784 ));
785 }
786
787 #[test]
788 #[should_panic(expected = "grammar error
789
790 --> 1:13
791 |
7921 | COMMENT = { SOI }
793 | ^-^
794 |
795 = COMMENT is non-progressing and will repeat infinitely")]
796 fn non_progressing_comment() {
797 let input = "COMMENT = { SOI }";
798 unwrap_or_report(consume_rules(
799 PestParser::parse(Rule::grammar_rules, input).unwrap(),
800 ));
801 }
802
803 #[test]
804 fn non_progressing_empty_string() {
805 assert!(is_non_failing(
806 &ParserExpr::Insens("".into()),
807 &HashMap::new(),
808 &mut Vec::new()
809 ));
810 assert!(is_non_progressing(
811 &ParserExpr::Str("".into()),
812 &HashMap::new(),
813 &mut Vec::new()
814 ));
815 }
816
817 #[test]
818 fn progressing_non_empty_string() {
819 assert!(!is_non_progressing(
820 &ParserExpr::Insens("non empty".into()),
821 &HashMap::new(),
822 &mut Vec::new()
823 ));
824 assert!(!is_non_progressing(
825 &ParserExpr::Str("non empty".into()),
826 &HashMap::new(),
827 &mut Vec::new()
828 ));
829 }
830
831 #[test]
832 fn non_progressing_soi_eoi() {
833 assert!(is_non_progressing(
834 &ParserExpr::Ident("SOI".into()),
835 &HashMap::new(),
836 &mut Vec::new()
837 ));
838 assert!(is_non_progressing(
839 &ParserExpr::Ident("EOI".into()),
840 &HashMap::new(),
841 &mut Vec::new()
842 ));
843 }
844
845 #[test]
846 fn non_progressing_predicates() {
847 let progressing = ParserExpr::Str("A".into());
848
849 assert!(is_non_progressing(
850 &ParserExpr::PosPred(Box::new(ParserNode {
851 expr: progressing.clone(),
852 span: Span::new(" ", 0, 1).unwrap(),
853 })),
854 &HashMap::new(),
855 &mut Vec::new()
856 ));
857 assert!(is_non_progressing(
858 &ParserExpr::NegPred(Box::new(ParserNode {
859 expr: progressing,
860 span: Span::new(" ", 0, 1).unwrap(),
861 })),
862 &HashMap::new(),
863 &mut Vec::new()
864 ));
865 }
866
867 #[test]
868 fn non_progressing_0_length_repetitions() {
869 let input_progressing_node = Box::new(ParserNode {
870 expr: ParserExpr::Str("A".into()),
871 span: Span::new(" ", 0, 1).unwrap(),
872 });
873
874 assert!(!is_non_progressing(
875 &input_progressing_node.clone().expr,
876 &HashMap::new(),
877 &mut Vec::new()
878 ));
879
880 assert!(is_non_progressing(
881 &ParserExpr::Rep(input_progressing_node.clone()),
882 &HashMap::new(),
883 &mut Vec::new()
884 ));
885 assert!(is_non_progressing(
886 &ParserExpr::Opt(input_progressing_node.clone()),
887 &HashMap::new(),
888 &mut Vec::new()
889 ));
890 assert!(is_non_progressing(
891 &ParserExpr::RepExact(input_progressing_node.clone(), 0),
892 &HashMap::new(),
893 &mut Vec::new()
894 ));
895 assert!(is_non_progressing(
896 &ParserExpr::RepMin(input_progressing_node.clone(), 0),
897 &HashMap::new(),
898 &mut Vec::new()
899 ));
900 assert!(is_non_progressing(
901 &ParserExpr::RepMax(input_progressing_node.clone(), 0),
902 &HashMap::new(),
903 &mut Vec::new()
904 ));
905 assert!(is_non_progressing(
906 &ParserExpr::RepMax(input_progressing_node.clone(), 17),
907 &HashMap::new(),
908 &mut Vec::new()
909 ));
910
911 assert!(is_non_progressing(
912 &ParserExpr::RepMinMax(input_progressing_node.clone(), 0, 12),
913 &HashMap::new(),
914 &mut Vec::new()
915 ));
916 }
917
918 #[test]
919 fn non_progressing_nonzero_repetitions_with_non_progressing_expr() {
920 let a = "";
921 let non_progressing_node = Box::new(ParserNode {
922 expr: ParserExpr::Str(a.into()),
923 span: Span::new(a, 0, 0).unwrap(),
924 });
925 let exact = ParserExpr::RepExact(non_progressing_node.clone(), 7);
926 let min = ParserExpr::RepMin(non_progressing_node.clone(), 23);
927 let minmax = ParserExpr::RepMinMax(non_progressing_node.clone(), 12, 13);
928 let reponce = ParserExpr::RepOnce(non_progressing_node);
929
930 assert!(is_non_progressing(&exact, &HashMap::new(), &mut Vec::new()));
931 assert!(is_non_progressing(&min, &HashMap::new(), &mut Vec::new()));
932 assert!(is_non_progressing(
933 &minmax,
934 &HashMap::new(),
935 &mut Vec::new()
936 ));
937 assert!(is_non_progressing(
938 &reponce,
939 &HashMap::new(),
940 &mut Vec::new()
941 ));
942 }
943
944 #[test]
945 fn progressing_repetitions() {
946 let a = "A";
947 let input_progressing_node = Box::new(ParserNode {
948 expr: ParserExpr::Str(a.into()),
949 span: Span::new(a, 0, 1).unwrap(),
950 });
951 let exact = ParserExpr::RepExact(input_progressing_node.clone(), 1);
952 let min = ParserExpr::RepMin(input_progressing_node.clone(), 2);
953 let minmax = ParserExpr::RepMinMax(input_progressing_node.clone(), 4, 5);
954 let reponce = ParserExpr::RepOnce(input_progressing_node);
955
956 assert!(!is_non_progressing(
957 &exact,
958 &HashMap::new(),
959 &mut Vec::new()
960 ));
961 assert!(!is_non_progressing(&min, &HashMap::new(), &mut Vec::new()));
962 assert!(!is_non_progressing(
963 &minmax,
964 &HashMap::new(),
965 &mut Vec::new()
966 ));
967 assert!(!is_non_progressing(
968 &reponce,
969 &HashMap::new(),
970 &mut Vec::new()
971 ));
972 }
973
974 #[test]
975 fn non_progressing_push() {
976 let a = "";
977 let non_progressing_node = Box::new(ParserNode {
978 expr: ParserExpr::Str(a.into()),
979 span: Span::new(a, 0, 0).unwrap(),
980 });
981 let push = ParserExpr::Push(non_progressing_node.clone());
982
983 assert!(is_non_progressing(&push, &HashMap::new(), &mut Vec::new()));
984 }
985
986 #[test]
987 fn progressing_push() {
988 let a = "i'm make progress";
989 let progressing_node = Box::new(ParserNode {
990 expr: ParserExpr::Str(a.into()),
991 span: Span::new(a, 0, 1).unwrap(),
992 });
993 let push = ParserExpr::Push(progressing_node.clone());
994
995 assert!(!is_non_progressing(&push, &HashMap::new(), &mut Vec::new()));
996 }
997
998 #[test]
999 fn node_tag_forwards_is_non_progressing() {
1000 let progressing_node = Box::new(ParserNode {
1001 expr: ParserExpr::Str("i'm make progress".into()),
1002 span: Span::new(" ", 0, 1).unwrap(),
1003 });
1004 assert!(!is_non_progressing(
1005 &progressing_node.clone().expr,
1006 &HashMap::new(),
1007 &mut Vec::new()
1008 ));
1009 let non_progressing_node = Box::new(ParserNode {
1010 expr: ParserExpr::Str("".into()),
1011 span: Span::new(" ", 0, 1).unwrap(),
1012 });
1013 assert!(is_non_progressing(
1014 &non_progressing_node.clone().expr,
1015 &HashMap::new(),
1016 &mut Vec::new()
1017 ));
1018 #[cfg(feature = "grammar-extras")]
1019 {
1020 let progressing = ParserExpr::NodeTag(progressing_node.clone(), "TAG".into());
1021 let non_progressing = ParserExpr::NodeTag(non_progressing_node.clone(), "TAG".into());
1022
1023 assert!(!is_non_progressing(
1024 &progressing,
1025 &HashMap::new(),
1026 &mut Vec::new()
1027 ));
1028 assert!(is_non_progressing(
1029 &non_progressing,
1030 &HashMap::new(),
1031 &mut Vec::new()
1032 ));
1033 }
1034 }
1035
1036 #[test]
1037 fn progressing_range() {
1038 let progressing = ParserExpr::Range("A".into(), "Z".into());
1039 let failing_is_progressing = ParserExpr::Range("Z".into(), "A".into());
1040
1041 assert!(!is_non_progressing(
1042 &progressing,
1043 &HashMap::new(),
1044 &mut Vec::new()
1045 ));
1046 assert!(!is_non_progressing(
1047 &failing_is_progressing,
1048 &HashMap::new(),
1049 &mut Vec::new()
1050 ));
1051 }
1052
1053 #[test]
1054 fn progressing_choice() {
1055 let left_progressing_node = Box::new(ParserNode {
1056 expr: ParserExpr::Str("i'm make progress".into()),
1057 span: Span::new(" ", 0, 1).unwrap(),
1058 });
1059 assert!(!is_non_progressing(
1060 &left_progressing_node.clone().expr,
1061 &HashMap::new(),
1062 &mut Vec::new()
1063 ));
1064
1065 let right_progressing_node = Box::new(ParserNode {
1066 expr: ParserExpr::Ident("DROP".into()),
1067 span: Span::new("DROP", 0, 3).unwrap(),
1068 });
1069
1070 assert!(!is_non_progressing(
1071 &ParserExpr::Choice(left_progressing_node, right_progressing_node),
1072 &HashMap::new(),
1073 &mut Vec::new()
1074 ))
1075 }
1076
1077 #[test]
1078 fn non_progressing_choices() {
1079 let left_progressing_node = Box::new(ParserNode {
1080 expr: ParserExpr::Str("i'm make progress".into()),
1081 span: Span::new(" ", 0, 1).unwrap(),
1082 });
1083
1084 assert!(!is_non_progressing(
1085 &left_progressing_node.clone().expr,
1086 &HashMap::new(),
1087 &mut Vec::new()
1088 ));
1089
1090 let left_non_progressing_node = Box::new(ParserNode {
1091 expr: ParserExpr::Str("".into()),
1092 span: Span::new(" ", 0, 1).unwrap(),
1093 });
1094
1095 assert!(is_non_progressing(
1096 &left_non_progressing_node.clone().expr,
1097 &HashMap::new(),
1098 &mut Vec::new()
1099 ));
1100
1101 let right_progressing_node = Box::new(ParserNode {
1102 expr: ParserExpr::Ident("DROP".into()),
1103 span: Span::new("DROP", 0, 3).unwrap(),
1104 });
1105
1106 assert!(!is_non_progressing(
1107 &right_progressing_node.clone().expr,
1108 &HashMap::new(),
1109 &mut Vec::new()
1110 ));
1111
1112 let right_non_progressing_node = Box::new(ParserNode {
1113 expr: ParserExpr::Opt(Box::new(ParserNode {
1114 expr: ParserExpr::Str(" ".into()),
1115 span: Span::new(" ", 0, 1).unwrap(),
1116 })),
1117 span: Span::new(" ", 0, 1).unwrap(),
1118 });
1119
1120 assert!(is_non_progressing(
1121 &right_non_progressing_node.clone().expr,
1122 &HashMap::new(),
1123 &mut Vec::new()
1124 ));
1125
1126 assert!(is_non_progressing(
1127 &ParserExpr::Choice(left_non_progressing_node.clone(), right_progressing_node),
1128 &HashMap::new(),
1129 &mut Vec::new()
1130 ));
1131 assert!(is_non_progressing(
1132 &ParserExpr::Choice(left_progressing_node, right_non_progressing_node.clone()),
1133 &HashMap::new(),
1134 &mut Vec::new()
1135 ));
1136 assert!(is_non_progressing(
1137 &ParserExpr::Choice(left_non_progressing_node, right_non_progressing_node),
1138 &HashMap::new(),
1139 &mut Vec::new()
1140 ))
1141 }
1142
1143 #[test]
1144 fn non_progressing_seq() {
1145 let left_non_progressing_node = Box::new(ParserNode {
1146 expr: ParserExpr::Str("".into()),
1147 span: Span::new(" ", 0, 1).unwrap(),
1148 });
1149
1150 let right_non_progressing_node = Box::new(ParserNode {
1151 expr: ParserExpr::Opt(Box::new(ParserNode {
1152 expr: ParserExpr::Str(" ".into()),
1153 span: Span::new(" ", 0, 1).unwrap(),
1154 })),
1155 span: Span::new(" ", 0, 1).unwrap(),
1156 });
1157
1158 assert!(is_non_progressing(
1159 &ParserExpr::Seq(left_non_progressing_node, right_non_progressing_node),
1160 &HashMap::new(),
1161 &mut Vec::new()
1162 ))
1163 }
1164
1165 #[test]
1166 fn progressing_seqs() {
1167 let left_progressing_node = Box::new(ParserNode {
1168 expr: ParserExpr::Str("i'm make progress".into()),
1169 span: Span::new(" ", 0, 1).unwrap(),
1170 });
1171
1172 assert!(!is_non_progressing(
1173 &left_progressing_node.clone().expr,
1174 &HashMap::new(),
1175 &mut Vec::new()
1176 ));
1177
1178 let left_non_progressing_node = Box::new(ParserNode {
1179 expr: ParserExpr::Str("".into()),
1180 span: Span::new(" ", 0, 1).unwrap(),
1181 });
1182
1183 assert!(is_non_progressing(
1184 &left_non_progressing_node.clone().expr,
1185 &HashMap::new(),
1186 &mut Vec::new()
1187 ));
1188
1189 let right_progressing_node = Box::new(ParserNode {
1190 expr: ParserExpr::Ident("DROP".into()),
1191 span: Span::new("DROP", 0, 3).unwrap(),
1192 });
1193
1194 assert!(!is_non_progressing(
1195 &right_progressing_node.clone().expr,
1196 &HashMap::new(),
1197 &mut Vec::new()
1198 ));
1199
1200 let right_non_progressing_node = Box::new(ParserNode {
1201 expr: ParserExpr::Opt(Box::new(ParserNode {
1202 expr: ParserExpr::Str(" ".into()),
1203 span: Span::new(" ", 0, 1).unwrap(),
1204 })),
1205 span: Span::new(" ", 0, 1).unwrap(),
1206 });
1207
1208 assert!(is_non_progressing(
1209 &right_non_progressing_node.clone().expr,
1210 &HashMap::new(),
1211 &mut Vec::new()
1212 ));
1213
1214 assert!(!is_non_progressing(
1215 &ParserExpr::Seq(left_non_progressing_node, right_progressing_node.clone()),
1216 &HashMap::new(),
1217 &mut Vec::new()
1218 ));
1219 assert!(!is_non_progressing(
1220 &ParserExpr::Seq(left_progressing_node.clone(), right_non_progressing_node),
1221 &HashMap::new(),
1222 &mut Vec::new()
1223 ));
1224 assert!(!is_non_progressing(
1225 &ParserExpr::Seq(left_progressing_node, right_progressing_node),
1226 &HashMap::new(),
1227 &mut Vec::new()
1228 ))
1229 }
1230
1231 #[test]
1232 fn progressing_stack_operations() {
1233 assert!(!is_non_progressing(
1234 &ParserExpr::Ident("DROP".into()),
1235 &HashMap::new(),
1236 &mut Vec::new()
1237 ));
1238 assert!(!is_non_progressing(
1239 &ParserExpr::Ident("PEEK".into()),
1240 &HashMap::new(),
1241 &mut Vec::new()
1242 ));
1243 assert!(!is_non_progressing(
1244 &ParserExpr::Ident("POP".into()),
1245 &HashMap::new(),
1246 &mut Vec::new()
1247 ))
1248 }
1249
1250 #[test]
1251 fn non_failing_string() {
1252 let insens = ParserExpr::Insens("".into());
1253 let string = ParserExpr::Str("".into());
1254
1255 assert!(is_non_failing(&insens, &HashMap::new(), &mut Vec::new()));
1256
1257 assert!(is_non_failing(&string, &HashMap::new(), &mut Vec::new()))
1258 }
1259
1260 #[test]
1261 fn failing_string() {
1262 assert!(!is_non_failing(
1263 &ParserExpr::Insens("i may fail!".into()),
1264 &HashMap::new(),
1265 &mut Vec::new()
1266 ));
1267 assert!(!is_non_failing(
1268 &ParserExpr::Str("failure is not fatal".into()),
1269 &HashMap::new(),
1270 &mut Vec::new()
1271 ))
1272 }
1273
1274 #[test]
1275 fn failing_stack_operations() {
1276 assert!(!is_non_failing(
1277 &ParserExpr::Ident("DROP".into()),
1278 &HashMap::new(),
1279 &mut Vec::new()
1280 ));
1281 assert!(!is_non_failing(
1282 &ParserExpr::Ident("POP".into()),
1283 &HashMap::new(),
1284 &mut Vec::new()
1285 ));
1286 assert!(!is_non_failing(
1287 &ParserExpr::Ident("PEEK".into()),
1288 &HashMap::new(),
1289 &mut Vec::new()
1290 ))
1291 }
1292
1293 #[test]
1294 fn non_failing_zero_length_repetitions() {
1295 let failing = Box::new(ParserNode {
1296 expr: ParserExpr::Range("A".into(), "B".into()),
1297 span: Span::new(" ", 0, 1).unwrap(),
1298 });
1299 assert!(!is_non_failing(
1300 &failing.clone().expr,
1301 &HashMap::new(),
1302 &mut Vec::new()
1303 ));
1304 assert!(is_non_failing(
1305 &ParserExpr::Opt(failing.clone()),
1306 &HashMap::new(),
1307 &mut Vec::new()
1308 ));
1309 assert!(is_non_failing(
1310 &ParserExpr::Rep(failing.clone()),
1311 &HashMap::new(),
1312 &mut Vec::new()
1313 ));
1314 assert!(is_non_failing(
1315 &ParserExpr::RepExact(failing.clone(), 0),
1316 &HashMap::new(),
1317 &mut Vec::new()
1318 ));
1319 assert!(is_non_failing(
1320 &ParserExpr::RepMin(failing.clone(), 0),
1321 &HashMap::new(),
1322 &mut Vec::new()
1323 ));
1324 assert!(is_non_failing(
1325 &ParserExpr::RepMax(failing.clone(), 0),
1326 &HashMap::new(),
1327 &mut Vec::new()
1328 ));
1329 assert!(is_non_failing(
1330 &ParserExpr::RepMax(failing.clone(), 22),
1331 &HashMap::new(),
1332 &mut Vec::new()
1333 ));
1334 assert!(is_non_failing(
1335 &ParserExpr::RepMinMax(failing.clone(), 0, 73),
1336 &HashMap::new(),
1337 &mut Vec::new()
1338 ));
1339 }
1340
1341 #[test]
1342 fn non_failing_non_zero_repetitions_with_non_failing_expr() {
1343 let non_failing = Box::new(ParserNode {
1344 expr: ParserExpr::Opt(Box::new(ParserNode {
1345 expr: ParserExpr::Range("A".into(), "B".into()),
1346 span: Span::new(" ", 0, 1).unwrap(),
1347 })),
1348 span: Span::new(" ", 0, 1).unwrap(),
1349 });
1350 assert!(is_non_failing(
1351 &non_failing.clone().expr,
1352 &HashMap::new(),
1353 &mut Vec::new()
1354 ));
1355 assert!(is_non_failing(
1356 &ParserExpr::RepOnce(non_failing.clone()),
1357 &HashMap::new(),
1358 &mut Vec::new()
1359 ));
1360 assert!(is_non_failing(
1361 &ParserExpr::RepExact(non_failing.clone(), 1),
1362 &HashMap::new(),
1363 &mut Vec::new()
1364 ));
1365 assert!(is_non_failing(
1366 &ParserExpr::RepMin(non_failing.clone(), 6),
1367 &HashMap::new(),
1368 &mut Vec::new()
1369 ));
1370 assert!(is_non_failing(
1371 &ParserExpr::RepMinMax(non_failing.clone(), 32, 73),
1372 &HashMap::new(),
1373 &mut Vec::new()
1374 ));
1375 }
1376
1377 #[test]
1378 #[cfg(feature = "grammar-extras")]
1379 fn failing_non_zero_repetitions() {
1380 let failing = Box::new(ParserNode {
1381 expr: ParserExpr::NodeTag(
1382 Box::new(ParserNode {
1383 expr: ParserExpr::Range("A".into(), "B".into()),
1384 span: Span::new(" ", 0, 1).unwrap(),
1385 }),
1386 "Tag".into(),
1387 ),
1388 span: Span::new(" ", 0, 1).unwrap(),
1389 });
1390 assert!(!is_non_failing(
1391 &failing.clone().expr,
1392 &HashMap::new(),
1393 &mut Vec::new()
1394 ));
1395 assert!(!is_non_failing(
1396 &ParserExpr::RepOnce(failing.clone()),
1397 &HashMap::new(),
1398 &mut Vec::new()
1399 ));
1400 assert!(!is_non_failing(
1401 &ParserExpr::RepExact(failing.clone(), 3),
1402 &HashMap::new(),
1403 &mut Vec::new()
1404 ));
1405 assert!(!is_non_failing(
1406 &ParserExpr::RepMin(failing.clone(), 14),
1407 &HashMap::new(),
1408 &mut Vec::new()
1409 ));
1410 assert!(!is_non_failing(
1411 &ParserExpr::RepMinMax(failing.clone(), 47, 73),
1412 &HashMap::new(),
1413 &mut Vec::new()
1414 ));
1415 }
1416
1417 #[test]
1418 fn failing_choice() {
1419 let left_failing_node = Box::new(ParserNode {
1420 expr: ParserExpr::Str("i'm a failure".into()),
1421 span: Span::new(" ", 0, 1).unwrap(),
1422 });
1423 assert!(!is_non_failing(
1424 &left_failing_node.clone().expr,
1425 &HashMap::new(),
1426 &mut Vec::new()
1427 ));
1428
1429 let right_failing_node = Box::new(ParserNode {
1430 expr: ParserExpr::Ident("DROP".into()),
1431 span: Span::new("DROP", 0, 3).unwrap(),
1432 });
1433
1434 assert!(!is_non_failing(
1435 &ParserExpr::Choice(left_failing_node, right_failing_node),
1436 &HashMap::new(),
1437 &mut Vec::new()
1438 ))
1439 }
1440
1441 #[test]
1442 fn non_failing_choices() {
1443 let left_failing_node = Box::new(ParserNode {
1444 expr: ParserExpr::Str("i'm a failure".into()),
1445 span: Span::new(" ", 0, 1).unwrap(),
1446 });
1447
1448 assert!(!is_non_failing(
1449 &left_failing_node.clone().expr,
1450 &HashMap::new(),
1451 &mut Vec::new()
1452 ));
1453
1454 let left_non_failing_node = Box::new(ParserNode {
1455 expr: ParserExpr::Str("".into()),
1456 span: Span::new(" ", 0, 1).unwrap(),
1457 });
1458
1459 assert!(is_non_failing(
1460 &left_non_failing_node.clone().expr,
1461 &HashMap::new(),
1462 &mut Vec::new()
1463 ));
1464
1465 let right_failing_node = Box::new(ParserNode {
1466 expr: ParserExpr::Ident("DROP".into()),
1467 span: Span::new("DROP", 0, 3).unwrap(),
1468 });
1469
1470 assert!(!is_non_failing(
1471 &right_failing_node.clone().expr,
1472 &HashMap::new(),
1473 &mut Vec::new()
1474 ));
1475
1476 let right_non_failing_node = Box::new(ParserNode {
1477 expr: ParserExpr::Opt(Box::new(ParserNode {
1478 expr: ParserExpr::Str(" ".into()),
1479 span: Span::new(" ", 0, 1).unwrap(),
1480 })),
1481 span: Span::new(" ", 0, 1).unwrap(),
1482 });
1483
1484 assert!(is_non_failing(
1485 &right_non_failing_node.clone().expr,
1486 &HashMap::new(),
1487 &mut Vec::new()
1488 ));
1489
1490 assert!(is_non_failing(
1491 &ParserExpr::Choice(left_non_failing_node.clone(), right_failing_node),
1492 &HashMap::new(),
1493 &mut Vec::new()
1494 ));
1495 assert!(is_non_failing(
1496 &ParserExpr::Choice(left_failing_node, right_non_failing_node.clone()),
1497 &HashMap::new(),
1498 &mut Vec::new()
1499 ));
1500 assert!(is_non_failing(
1501 &ParserExpr::Choice(left_non_failing_node, right_non_failing_node),
1502 &HashMap::new(),
1503 &mut Vec::new()
1504 ))
1505 }
1506
1507 #[test]
1508 fn non_failing_seq() {
1509 let left_non_failing_node = Box::new(ParserNode {
1510 expr: ParserExpr::Str("".into()),
1511 span: Span::new(" ", 0, 1).unwrap(),
1512 });
1513
1514 let right_non_failing_node = Box::new(ParserNode {
1515 expr: ParserExpr::Opt(Box::new(ParserNode {
1516 expr: ParserExpr::Str(" ".into()),
1517 span: Span::new(" ", 0, 1).unwrap(),
1518 })),
1519 span: Span::new(" ", 0, 1).unwrap(),
1520 });
1521
1522 assert!(is_non_failing(
1523 &ParserExpr::Seq(left_non_failing_node, right_non_failing_node),
1524 &HashMap::new(),
1525 &mut Vec::new()
1526 ))
1527 }
1528
1529 #[test]
1530 fn failing_seqs() {
1531 let left_failing_node = Box::new(ParserNode {
1532 expr: ParserExpr::Str("i'm a failure".into()),
1533 span: Span::new(" ", 0, 1).unwrap(),
1534 });
1535
1536 assert!(!is_non_failing(
1537 &left_failing_node.clone().expr,
1538 &HashMap::new(),
1539 &mut Vec::new()
1540 ));
1541
1542 let left_non_failing_node = Box::new(ParserNode {
1543 expr: ParserExpr::Str("".into()),
1544 span: Span::new(" ", 0, 1).unwrap(),
1545 });
1546
1547 assert!(is_non_failing(
1548 &left_non_failing_node.clone().expr,
1549 &HashMap::new(),
1550 &mut Vec::new()
1551 ));
1552
1553 let right_failing_node = Box::new(ParserNode {
1554 expr: ParserExpr::Ident("DROP".into()),
1555 span: Span::new("DROP", 0, 3).unwrap(),
1556 });
1557
1558 assert!(!is_non_failing(
1559 &right_failing_node.clone().expr,
1560 &HashMap::new(),
1561 &mut Vec::new()
1562 ));
1563
1564 let right_non_failing_node = Box::new(ParserNode {
1565 expr: ParserExpr::Opt(Box::new(ParserNode {
1566 expr: ParserExpr::Str(" ".into()),
1567 span: Span::new(" ", 0, 1).unwrap(),
1568 })),
1569 span: Span::new(" ", 0, 1).unwrap(),
1570 });
1571
1572 assert!(is_non_failing(
1573 &right_non_failing_node.clone().expr,
1574 &HashMap::new(),
1575 &mut Vec::new()
1576 ));
1577
1578 assert!(!is_non_failing(
1579 &ParserExpr::Seq(left_non_failing_node, right_failing_node.clone()),
1580 &HashMap::new(),
1581 &mut Vec::new()
1582 ));
1583 assert!(!is_non_failing(
1584 &ParserExpr::Seq(left_failing_node.clone(), right_non_failing_node),
1585 &HashMap::new(),
1586 &mut Vec::new()
1587 ));
1588 assert!(!is_non_failing(
1589 &ParserExpr::Seq(left_failing_node, right_failing_node),
1590 &HashMap::new(),
1591 &mut Vec::new()
1592 ))
1593 }
1594
1595 #[test]
1596 fn failing_range() {
1597 let failing = ParserExpr::Range("A".into(), "Z".into());
1598 let always_failing = ParserExpr::Range("Z".into(), "A".into());
1599
1600 assert!(!is_non_failing(&failing, &HashMap::new(), &mut Vec::new()));
1601 assert!(!is_non_failing(
1602 &always_failing,
1603 &HashMap::new(),
1604 &mut Vec::new()
1605 ));
1606 }
1607
1608 #[test]
1609 fn _push_node_tag_pos_pred_forwarding_is_non_failing() {
1610 let failing_node = Box::new(ParserNode {
1611 expr: ParserExpr::Str("i'm a failure".into()),
1612 span: Span::new(" ", 0, 1).unwrap(),
1613 });
1614 assert!(!is_non_failing(
1615 &failing_node.clone().expr,
1616 &HashMap::new(),
1617 &mut Vec::new()
1618 ));
1619 let non_failing_node = Box::new(ParserNode {
1620 expr: ParserExpr::Str("".into()),
1621 span: Span::new(" ", 0, 1).unwrap(),
1622 });
1623 assert!(is_non_failing(
1624 &non_failing_node.clone().expr,
1625 &HashMap::new(),
1626 &mut Vec::new()
1627 ));
1628
1629 #[cfg(feature = "grammar-extras")]
1630 {
1631 assert!(!is_non_failing(
1632 &ParserExpr::NodeTag(failing_node.clone(), "TAG".into()),
1633 &HashMap::new(),
1634 &mut Vec::new()
1635 ));
1636 assert!(is_non_failing(
1637 &ParserExpr::NodeTag(non_failing_node.clone(), "TAG".into()),
1638 &HashMap::new(),
1639 &mut Vec::new()
1640 ));
1641 }
1642
1643 assert!(!is_non_failing(
1644 &ParserExpr::Push(failing_node.clone()),
1645 &HashMap::new(),
1646 &mut Vec::new()
1647 ));
1648 assert!(is_non_failing(
1649 &ParserExpr::Push(non_failing_node.clone()),
1650 &HashMap::new(),
1651 &mut Vec::new()
1652 ));
1653
1654 assert!(!is_non_failing(
1655 &ParserExpr::PosPred(failing_node.clone()),
1656 &HashMap::new(),
1657 &mut Vec::new()
1658 ));
1659 assert!(is_non_failing(
1660 &ParserExpr::PosPred(non_failing_node.clone()),
1661 &HashMap::new(),
1662 &mut Vec::new()
1663 ));
1664 }
1665
1666 #[test]
1667 #[should_panic(expected = "grammar error
1668
1669 --> 1:7
1670 |
16711 | a = { (\"\")* }
1672 | ^---^
1673 |
1674 = expression inside repetition cannot fail and will repeat infinitely")]
1675 fn non_failing_repetition() {
1676 let input = "a = { (\"\")* }";
1677 unwrap_or_report(consume_rules(
1678 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1679 ));
1680 }
1681
1682 #[test]
1683 #[should_panic(expected = "grammar error
1684
1685 --> 1:18
1686 |
16871 | a = { \"\" } b = { a* }
1688 | ^^
1689 |
1690 = expression inside repetition cannot fail and will repeat infinitely")]
1691 fn indirect_non_failing_repetition() {
1692 let input = "a = { \"\" } b = { a* }";
1693 unwrap_or_report(consume_rules(
1694 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1695 ));
1696 }
1697
1698 #[test]
1699 #[should_panic(expected = "grammar error
1700
1701 --> 1:20
1702 |
17031 | a = { \"a\" ~ (\"b\" ~ (\"\")*) }
1704 | ^---^
1705 |
1706 = expression inside repetition cannot fail and will repeat infinitely")]
1707 fn deep_non_failing_repetition() {
1708 let input = "a = { \"a\" ~ (\"b\" ~ (\"\")*) }";
1709 unwrap_or_report(consume_rules(
1710 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1711 ));
1712 }
1713
1714 #[test]
1715 #[should_panic(expected = "grammar error
1716
1717 --> 1:7
1718 |
17191 | a = { (\"\" ~ &\"a\" ~ !\"a\" ~ (SOI | EOI))* }
1720 | ^-------------------------------^
1721 |
1722 = expression inside repetition is non-progressing and will repeat infinitely")]
1723 fn non_progressing_repetition() {
1724 let input = "a = { (\"\" ~ &\"a\" ~ !\"a\" ~ (SOI | EOI))* }";
1725 unwrap_or_report(consume_rules(
1726 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1727 ));
1728 }
1729
1730 #[test]
1731 #[should_panic(expected = "grammar error
1732
1733 --> 1:20
1734 |
17351 | a = { !\"a\" } b = { a* }
1736 | ^^
1737 |
1738 = expression inside repetition is non-progressing and will repeat infinitely")]
1739 fn indirect_non_progressing_repetition() {
1740 let input = "a = { !\"a\" } b = { a* }";
1741 unwrap_or_report(consume_rules(
1742 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1743 ));
1744 }
1745
1746 #[test]
1747 #[should_panic(expected = "grammar error
1748
1749 --> 1:7
1750 |
17511 | a = { a }
1752 | ^
1753 |
1754 = rule a is left-recursive (a -> a); pest::pratt_parser might be useful in this case")]
1755 fn simple_left_recursion() {
1756 let input = "a = { a }";
1757 unwrap_or_report(consume_rules(
1758 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1759 ));
1760 }
1761
1762 #[test]
1763 #[should_panic(expected = "grammar error
1764
1765 --> 1:7
1766 |
17671 | a = { b } b = { a }
1768 | ^
1769 |
1770 = rule b is left-recursive (b -> a -> b); pest::pratt_parser might be useful in this case
1771
1772 --> 1:17
1773 |
17741 | a = { b } b = { a }
1775 | ^
1776 |
1777 = rule a is left-recursive (a -> b -> a); pest::pratt_parser might be useful in this case")]
1778 fn indirect_left_recursion() {
1779 let input = "a = { b } b = { a }";
1780 unwrap_or_report(consume_rules(
1781 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1782 ));
1783 }
1784
1785 #[test]
1786 #[should_panic(expected = "grammar error
1787
1788 --> 1:39
1789 |
17901 | a = { \"\" ~ \"a\"? ~ \"a\"* ~ (\"a\" | \"\") ~ a }
1791 | ^
1792 |
1793 = rule a is left-recursive (a -> a); pest::pratt_parser might be useful in this case")]
1794 fn non_failing_left_recursion() {
1795 let input = "a = { \"\" ~ \"a\"? ~ \"a\"* ~ (\"a\" | \"\") ~ a }";
1796 unwrap_or_report(consume_rules(
1797 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1798 ));
1799 }
1800
1801 #[test]
1802 #[should_panic(expected = "grammar error
1803
1804 --> 1:13
1805 |
18061 | a = { \"a\" | a }
1807 | ^
1808 |
1809 = rule a is left-recursive (a -> a); pest::pratt_parser might be useful in this case")]
1810 fn non_primary_choice_left_recursion() {
1811 let input = "a = { \"a\" | a }";
1812 unwrap_or_report(consume_rules(
1813 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1814 ));
1815 }
1816
1817 #[test]
1818 #[should_panic(expected = "grammar error
1819
1820 --> 1:14
1821 |
18221 | a = { !\"a\" ~ a }
1823 | ^
1824 |
1825 = rule a is left-recursive (a -> a); pest::pratt_parser might be useful in this case")]
1826 fn non_progressing_left_recursion() {
1827 let input = "a = { !\"a\" ~ a }";
1828 unwrap_or_report(consume_rules(
1829 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1830 ));
1831 }
1832
1833 #[test]
1834 #[should_panic(expected = "grammar error
1835
1836 --> 1:7
1837 |
18381 | a = { \"a\"* | \"a\" | \"b\" }
1839 | ^--^
1840 |
1841 = expression cannot fail; following choices cannot be reached")]
1842 fn lhs_non_failing_choice() {
1843 let input = "a = { \"a\"* | \"a\" | \"b\" }";
1844 unwrap_or_report(consume_rules(
1845 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1846 ));
1847 }
1848
1849 #[test]
1850 #[should_panic(expected = "grammar error
1851
1852 --> 1:13
1853 |
18541 | a = { \"a\" | \"a\"* | \"b\" }
1855 | ^--^
1856 |
1857 = expression cannot fail; following choices cannot be reached")]
1858 fn lhs_non_failing_choice_middle() {
1859 let input = "a = { \"a\" | \"a\"* | \"b\" }";
1860 unwrap_or_report(consume_rules(
1861 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1862 ));
1863 }
1864
1865 #[test]
1866 #[should_panic(expected = "grammar error
1867
1868 --> 1:7
1869 |
18701 | a = { b | \"a\" } b = { \"b\"* | \"c\" }
1871 | ^
1872 |
1873 = expression cannot fail; following choices cannot be reached
1874
1875 --> 1:23
1876 |
18771 | a = { b | \"a\" } b = { \"b\"* | \"c\" }
1878 | ^--^
1879 |
1880 = expression cannot fail; following choices cannot be reached")]
1881 fn lhs_non_failing_nested_choices() {
1882 let input = "a = { b | \"a\" } b = { \"b\"* | \"c\" }";
1883 unwrap_or_report(consume_rules(
1884 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1885 ));
1886 }
1887
1888 #[test]
1889 fn skip_can_be_defined() {
1890 let input = "skip = { \"\" }";
1891 unwrap_or_report(consume_rules(
1892 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1893 ));
1894 }
1895
1896 #[test]
1897 #[should_panic(expected = "grammar error
1898
1899 --> 1:7
1900 |
19011 | a = { #b = b } b = _{ ASCII_DIGIT+ }
1902 | ^----^
1903 |
1904 = tags on silent rules will not appear in the output")]
1905 #[cfg(feature = "grammar-extras")]
1906 fn tag_on_silent_rule() {
1907 let input = "a = { #b = b } b = _{ ASCII_DIGIT+ }";
1908 unwrap_or_report(consume_rules(
1909 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1910 ));
1911 }
1912
1913 #[test]
1914 #[should_panic(expected = "grammar error
1915
1916 --> 1:7
1917 |
19181 | a = { #b = ASCII_DIGIT+ }
1919 | ^---------------^
1920 |
1921 = tags on built-in rules will not appear in the output")]
1922 #[cfg(feature = "grammar-extras")]
1923 fn tag_on_builtin_rule() {
1924 let input = "a = { #b = ASCII_DIGIT+ }";
1925 unwrap_or_report(consume_rules(
1926 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1927 ));
1928 }
1929
1930 #[test]
1931 #[cfg(feature = "grammar-extras")]
1932 fn tag_on_normal_rule() {
1933 let input = "a = { #b = b } b = { ASCII_DIGIT+ }";
1934 unwrap_or_report(consume_rules(
1935 PestParser::parse(Rule::grammar_rules, input).unwrap(),
1936 ));
1937 }
1938}
1939