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