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