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 use std::collections::{HashMap, HashSet};
11 
12 use pest::error::{Error, ErrorVariant, InputLocation};
13 use pest::iterators::Pairs;
14 use pest::Span;
15 
16 use parser::{ParserExpr, ParserNode, ParserRule, Rule};
17 use UNICODE_PROPERTY_NAMES;
18 
19 #[allow(clippy::needless_pass_by_value)]
validate_pairs<'i>(pairs: Pairs<'i, Rule>) -> Result<Vec<&'i str>, Vec<Error<Rule>>>20 pub fn validate_pairs<'i>(pairs: Pairs<'i, Rule>) -> Result<Vec<&'i str>, Vec<Error<Rule>>> {
21     let mut rust_keywords = HashSet::new();
22     rust_keywords.insert("abstract");
23     rust_keywords.insert("alignof");
24     rust_keywords.insert("as");
25     rust_keywords.insert("become");
26     rust_keywords.insert("box");
27     rust_keywords.insert("break");
28     rust_keywords.insert("const");
29     rust_keywords.insert("continue");
30     rust_keywords.insert("crate");
31     rust_keywords.insert("do");
32     rust_keywords.insert("else");
33     rust_keywords.insert("enum");
34     rust_keywords.insert("extern");
35     rust_keywords.insert("false");
36     rust_keywords.insert("final");
37     rust_keywords.insert("fn");
38     rust_keywords.insert("for");
39     rust_keywords.insert("if");
40     rust_keywords.insert("impl");
41     rust_keywords.insert("in");
42     rust_keywords.insert("let");
43     rust_keywords.insert("loop");
44     rust_keywords.insert("macro");
45     rust_keywords.insert("match");
46     rust_keywords.insert("mod");
47     rust_keywords.insert("move");
48     rust_keywords.insert("mut");
49     rust_keywords.insert("offsetof");
50     rust_keywords.insert("override");
51     rust_keywords.insert("priv");
52     rust_keywords.insert("proc");
53     rust_keywords.insert("pure");
54     rust_keywords.insert("pub");
55     rust_keywords.insert("ref");
56     rust_keywords.insert("return");
57     rust_keywords.insert("Self");
58     rust_keywords.insert("self");
59     rust_keywords.insert("sizeof");
60     rust_keywords.insert("static");
61     rust_keywords.insert("struct");
62     rust_keywords.insert("super");
63     rust_keywords.insert("trait");
64     rust_keywords.insert("true");
65     rust_keywords.insert("type");
66     rust_keywords.insert("typeof");
67     rust_keywords.insert("unsafe");
68     rust_keywords.insert("unsized");
69     rust_keywords.insert("use");
70     rust_keywords.insert("virtual");
71     rust_keywords.insert("where");
72     rust_keywords.insert("while");
73     rust_keywords.insert("yield");
74 
75     let mut pest_keywords = HashSet::new();
76     pest_keywords.insert("_");
77     pest_keywords.insert("ANY");
78     pest_keywords.insert("DROP");
79     pest_keywords.insert("EOI");
80     pest_keywords.insert("PEEK");
81     pest_keywords.insert("PEEK_ALL");
82     pest_keywords.insert("POP");
83     pest_keywords.insert("POP_ALL");
84     pest_keywords.insert("PUSH");
85     pest_keywords.insert("SOI");
86 
87     let mut builtins = HashSet::new();
88     builtins.insert("ANY");
89     builtins.insert("DROP");
90     builtins.insert("EOI");
91     builtins.insert("PEEK");
92     builtins.insert("PEEK_ALL");
93     builtins.insert("POP");
94     builtins.insert("POP_ALL");
95     builtins.insert("SOI");
96     builtins.insert("ASCII_DIGIT");
97     builtins.insert("ASCII_NONZERO_DIGIT");
98     builtins.insert("ASCII_BIN_DIGIT");
99     builtins.insert("ASCII_OCT_DIGIT");
100     builtins.insert("ASCII_HEX_DIGIT");
101     builtins.insert("ASCII_ALPHA_LOWER");
102     builtins.insert("ASCII_ALPHA_UPPER");
103     builtins.insert("ASCII_ALPHA");
104     builtins.insert("ASCII_ALPHANUMERIC");
105     builtins.insert("ASCII");
106     builtins.insert("NEWLINE");
107     builtins.extend(UNICODE_PROPERTY_NAMES);
108 
109     let definitions: Vec<_> = pairs
110         .clone()
111         .filter(|pair| pair.as_rule() == Rule::grammar_rule)
112         .map(|pair| pair.into_inner().next().unwrap().as_span())
113         .collect();
114     let called_rules: Vec<_> = pairs
115         .clone()
116         .filter(|pair| pair.as_rule() == Rule::grammar_rule)
117         .flat_map(|pair| {
118             pair.into_inner()
119                 .flatten()
120                 .skip(1)
121                 .filter(|pair| pair.as_rule() == Rule::identifier)
122                 .map(|pair| pair.as_span())
123         })
124         .collect();
125 
126     let mut errors = vec![];
127 
128     errors.extend(validate_rust_keywords(&definitions, &rust_keywords));
129     errors.extend(validate_pest_keywords(&definitions, &pest_keywords));
130     errors.extend(validate_already_defined(&definitions));
131     errors.extend(validate_undefined(&definitions, &called_rules, &builtins));
132 
133     if !errors.is_empty() {
134         return Err(errors);
135     }
136 
137     let definitions: HashSet<_> = definitions.iter().map(|span| span.as_str()).collect();
138     let called_rules: HashSet<_> = called_rules.iter().map(|span| span.as_str()).collect();
139 
140     let defaults = called_rules.difference(&definitions);
141 
142     Ok(defaults.cloned().collect())
143 }
144 
145 #[allow(clippy::implicit_hasher, clippy::ptr_arg)]
validate_rust_keywords<'i>( definitions: &Vec<Span<'i>>, rust_keywords: &HashSet<&str>, ) -> Vec<Error<Rule>>146 pub fn validate_rust_keywords<'i>(
147     definitions: &Vec<Span<'i>>,
148     rust_keywords: &HashSet<&str>,
149 ) -> Vec<Error<Rule>> {
150     let mut errors = vec![];
151 
152     for definition in definitions {
153         let name = definition.as_str();
154 
155         if rust_keywords.contains(name) {
156             errors.push(Error::new_from_span(
157                 ErrorVariant::CustomError {
158                     message: format!("{} is a rust keyword", name),
159                 },
160                 definition.clone(),
161             ))
162         }
163     }
164 
165     errors
166 }
167 
168 #[allow(clippy::implicit_hasher, clippy::ptr_arg)]
validate_pest_keywords<'i>( definitions: &Vec<Span<'i>>, pest_keywords: &HashSet<&str>, ) -> Vec<Error<Rule>>169 pub fn validate_pest_keywords<'i>(
170     definitions: &Vec<Span<'i>>,
171     pest_keywords: &HashSet<&str>,
172 ) -> Vec<Error<Rule>> {
173     let mut errors = vec![];
174 
175     for definition in definitions {
176         let name = definition.as_str();
177 
178         if pest_keywords.contains(name) {
179             errors.push(Error::new_from_span(
180                 ErrorVariant::CustomError {
181                     message: format!("{} is a pest keyword", name),
182                 },
183                 definition.clone(),
184             ))
185         }
186     }
187 
188     errors
189 }
190 
191 #[allow(clippy::ptr_arg)]
validate_already_defined<'i>(definitions: &Vec<Span<'i>>) -> Vec<Error<Rule>>192 pub fn validate_already_defined<'i>(definitions: &Vec<Span<'i>>) -> Vec<Error<Rule>> {
193     let mut errors = vec![];
194     let mut defined = HashSet::new();
195 
196     for definition in definitions {
197         let name = definition.as_str();
198 
199         if defined.contains(&name) {
200             errors.push(Error::new_from_span(
201                 ErrorVariant::CustomError {
202                     message: format!("rule {} already defined", name),
203                 },
204                 definition.clone(),
205             ))
206         } else {
207             defined.insert(name);
208         }
209     }
210 
211     errors
212 }
213 
214 #[allow(clippy::implicit_hasher, clippy::ptr_arg)]
validate_undefined<'i>( definitions: &Vec<Span<'i>>, called_rules: &Vec<Span<'i>>, builtins: &HashSet<&str>, ) -> Vec<Error<Rule>>215 pub fn validate_undefined<'i>(
216     definitions: &Vec<Span<'i>>,
217     called_rules: &Vec<Span<'i>>,
218     builtins: &HashSet<&str>,
219 ) -> Vec<Error<Rule>> {
220     let mut errors = vec![];
221     let definitions: HashSet<_> = definitions.iter().map(|span| span.as_str()).collect();
222 
223     for rule in called_rules {
224         let name = rule.as_str();
225 
226         if !definitions.contains(name) && !builtins.contains(name) {
227             errors.push(Error::new_from_span(
228                 ErrorVariant::CustomError {
229                     message: format!("rule {} is undefined", name),
230                 },
231                 rule.clone(),
232             ))
233         }
234     }
235 
236     errors
237 }
238 
239 #[allow(clippy::ptr_arg)]
validate_ast<'a, 'i: 'a>(rules: &'a Vec<ParserRule<'i>>) -> Vec<Error<Rule>>240 pub fn validate_ast<'a, 'i: 'a>(rules: &'a Vec<ParserRule<'i>>) -> Vec<Error<Rule>> {
241     let mut errors = vec![];
242 
243     errors.extend(validate_repetition(rules));
244     errors.extend(validate_choices(rules));
245     errors.extend(validate_whitespace_comment(rules));
246     errors.extend(validate_left_recursion(rules));
247 
248     errors.sort_by_key(|error| match error.location {
249         InputLocation::Span(span) => span,
250         _ => unreachable!(),
251     });
252 
253     errors
254 }
255 
is_non_progressing<'i>( expr: &ParserExpr<'i>, rules: &HashMap<String, &ParserNode<'i>>, trace: &mut Vec<String>, ) -> bool256 fn is_non_progressing<'i>(
257     expr: &ParserExpr<'i>,
258     rules: &HashMap<String, &ParserNode<'i>>,
259     trace: &mut Vec<String>,
260 ) -> bool {
261     match *expr {
262         ParserExpr::Str(ref string) => string == "",
263         ParserExpr::Ident(ref ident) => {
264             if ident == "soi" || ident == "eoi" {
265                 return true;
266             }
267 
268             if !trace.contains(ident) {
269                 if let Some(node) = rules.get(ident) {
270                     trace.push(ident.clone());
271                     let result = is_non_progressing(&node.expr, rules, trace);
272                     trace.pop().unwrap();
273 
274                     return result;
275                 }
276             }
277 
278             false
279         }
280         ParserExpr::PosPred(_) => true,
281         ParserExpr::NegPred(_) => true,
282         ParserExpr::Seq(ref lhs, ref rhs) => {
283             is_non_progressing(&lhs.expr, rules, trace)
284                 && is_non_progressing(&rhs.expr, rules, trace)
285         }
286         ParserExpr::Choice(ref lhs, ref rhs) => {
287             is_non_progressing(&lhs.expr, rules, trace)
288                 || is_non_progressing(&rhs.expr, rules, trace)
289         }
290         _ => false,
291     }
292 }
293 
is_non_failing<'i>( expr: &ParserExpr<'i>, rules: &HashMap<String, &ParserNode<'i>>, trace: &mut Vec<String>, ) -> bool294 fn is_non_failing<'i>(
295     expr: &ParserExpr<'i>,
296     rules: &HashMap<String, &ParserNode<'i>>,
297     trace: &mut Vec<String>,
298 ) -> bool {
299     match *expr {
300         ParserExpr::Str(ref string) => string == "",
301         ParserExpr::Ident(ref ident) => {
302             if !trace.contains(ident) {
303                 if let Some(node) = rules.get(ident) {
304                     trace.push(ident.clone());
305                     let result = is_non_failing(&node.expr, rules, trace);
306                     trace.pop().unwrap();
307 
308                     return result;
309                 }
310             }
311 
312             false
313         }
314         ParserExpr::Opt(_) => true,
315         ParserExpr::Rep(_) => true,
316         ParserExpr::Seq(ref lhs, ref rhs) => {
317             is_non_failing(&lhs.expr, rules, trace) && is_non_failing(&rhs.expr, rules, trace)
318         }
319         ParserExpr::Choice(ref lhs, ref rhs) => {
320             is_non_failing(&lhs.expr, rules, trace) || is_non_failing(&rhs.expr, rules, trace)
321         }
322         _ => false,
323     }
324 }
325 
validate_repetition<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>>326 fn validate_repetition<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>> {
327     let mut result = vec![];
328     let map = to_hash_map(rules);
329 
330     for rule in rules {
331         let mut errors = rule.node
332             .clone()
333             .filter_map_top_down(|node| match node.expr {
334                 ParserExpr::Rep(ref other)
335                 | ParserExpr::RepOnce(ref other)
336                 | ParserExpr::RepMin(ref other, _) => {
337                     if is_non_failing(&other.expr, &map, &mut vec![]) {
338                         Some(Error::new_from_span(
339                             ErrorVariant::CustomError {
340                                 message:
341                                     "expression inside repetition cannot fail and will repeat \
342                                      infinitely"
343                                         .to_owned()
344                             },
345                             node.span.clone()
346                         ))
347                     } else if is_non_progressing(&other.expr, &map, &mut vec![]) {
348                         Some(Error::new_from_span(
349                             ErrorVariant::CustomError {
350                                 message:
351                                     "expression inside repetition is non-progressing and will repeat \
352                                      infinitely"
353                                         .to_owned(),
354                             },
355                             node.span.clone()
356                         ))
357                     } else {
358                         None
359                     }
360                 }
361                 _ => None
362             });
363 
364         result.append(&mut errors);
365     }
366 
367     result
368 }
369 
validate_choices<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>>370 fn validate_choices<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>> {
371     let mut result = vec![];
372     let map = to_hash_map(rules);
373 
374     for rule in rules {
375         let mut errors = rule
376             .node
377             .clone()
378             .filter_map_top_down(|node| match node.expr {
379                 ParserExpr::Choice(ref lhs, _) => {
380                     let node = match lhs.expr {
381                         ParserExpr::Choice(_, ref rhs) => rhs,
382                         _ => lhs,
383                     };
384 
385                     if is_non_failing(&node.expr, &map, &mut vec![]) {
386                         Some(Error::new_from_span(
387                             ErrorVariant::CustomError {
388                                 message:
389                                     "expression cannot fail; following choices cannot be reached"
390                                         .to_owned(),
391                             },
392                             node.span.clone(),
393                         ))
394                     } else {
395                         None
396                     }
397                 }
398                 _ => None,
399             });
400 
401         result.append(&mut errors);
402     }
403 
404     result
405 }
406 
validate_whitespace_comment<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>>407 fn validate_whitespace_comment<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>> {
408     let map = to_hash_map(rules);
409 
410     rules
411         .iter()
412         .filter_map(|rule| {
413             if rule.name == "WHITESPACE" || rule.name == "COMMENT" {
414                 if is_non_failing(&rule.node.expr, &map, &mut vec![]) {
415                     Some(Error::new_from_span(
416                         ErrorVariant::CustomError {
417                             message: format!(
418                                 "{} cannot fail and will repeat infinitely",
419                                 &rule.name
420                             ),
421                         },
422                         rule.node.span.clone(),
423                     ))
424                 } else if is_non_progressing(&rule.node.expr, &map, &mut vec![]) {
425                     Some(Error::new_from_span(
426                         ErrorVariant::CustomError {
427                             message: format!(
428                                 "{} is non-progressing and will repeat infinitely",
429                                 &rule.name
430                             ),
431                         },
432                         rule.node.span.clone(),
433                     ))
434                 } else {
435                     None
436                 }
437             } else {
438                 None
439             }
440         })
441         .collect()
442 }
443 
validate_left_recursion<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>>444 fn validate_left_recursion<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>> {
445     left_recursion(to_hash_map(rules))
446 }
447 
to_hash_map<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> HashMap<String, &'a ParserNode<'i>>448 fn to_hash_map<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> HashMap<String, &'a ParserNode<'i>> {
449     rules.iter().map(|r| (r.name.clone(), &r.node)).collect()
450 }
451 
452 #[allow(clippy::needless_pass_by_value)]
left_recursion<'a, 'i: 'a>(rules: HashMap<String, &'a ParserNode<'i>>) -> Vec<Error<Rule>>453 fn left_recursion<'a, 'i: 'a>(rules: HashMap<String, &'a ParserNode<'i>>) -> Vec<Error<Rule>> {
454     fn check_expr<'a, 'i: 'a>(
455         node: &'a ParserNode<'i>,
456         rules: &'a HashMap<String, &ParserNode<'i>>,
457         trace: &mut Vec<String>,
458     ) -> Option<Error<Rule>> {
459         match node.expr.clone() {
460             ParserExpr::Ident(other) => {
461                 if trace[0] == other {
462                     trace.push(other);
463                     let chain = trace
464                         .iter()
465                         .map(|ident| ident.as_ref())
466                         .collect::<Vec<_>>()
467                         .join(" -> ");
468 
469                     return Some(Error::new_from_span(
470                         ErrorVariant::CustomError {
471                             message: format!(
472                                 "rule {} is left-recursive ({}); pest::prec_climber might be useful \
473                                  in this case",
474                                 node.span.as_str(),
475                                 chain
476                             )
477                         },
478                         node.span.clone()
479                     ));
480                 }
481 
482                 if !trace.contains(&other) {
483                     if let Some(node) = rules.get(&other) {
484                         trace.push(other);
485                         let result = check_expr(node, rules, trace);
486                         trace.pop().unwrap();
487 
488                         return result;
489                     }
490                 }
491 
492                 None
493             }
494             ParserExpr::Seq(ref lhs, ref rhs) => {
495                 if is_non_failing(&lhs.expr, rules, &mut vec![trace.last().unwrap().clone()]) {
496                     check_expr(rhs, rules, trace)
497                 } else {
498                     check_expr(lhs, rules, trace)
499                 }
500             }
501             ParserExpr::Choice(ref lhs, ref rhs) => {
502                 check_expr(&lhs, rules, trace).or_else(|| check_expr(&rhs, rules, trace))
503             }
504             ParserExpr::Rep(ref node) => check_expr(&node, rules, trace),
505             ParserExpr::RepOnce(ref node) => check_expr(&node, rules, trace),
506             ParserExpr::Opt(ref node) => check_expr(&node, rules, trace),
507             ParserExpr::PosPred(ref node) => check_expr(&node, rules, trace),
508             ParserExpr::NegPred(ref node) => check_expr(&node, rules, trace),
509             ParserExpr::Push(ref node) => check_expr(&node, rules, trace),
510             _ => None,
511         }
512     }
513 
514     let mut errors = vec![];
515 
516     for (ref name, ref node) in &rules {
517         let name = (*name).clone();
518 
519         if let Some(error) = check_expr(node, &rules, &mut vec![name]) {
520             errors.push(error);
521         }
522     }
523 
524     errors
525 }
526 
527 #[cfg(test)]
528 mod tests {
529     use super::super::parser::{consume_rules, PestParser};
530     use super::super::unwrap_or_report;
531     use super::*;
532     use pest::Parser;
533 
534     #[test]
535     #[should_panic(expected = "grammar error
536 
537  --> 1:1
538   |
539 1 | let = { \"a\" }
540   | ^-^
541   |
542   = let is a rust keyword")]
rust_keyword()543     fn rust_keyword() {
544         let input = "let = { \"a\" }";
545         unwrap_or_report(validate_pairs(
546             PestParser::parse(Rule::grammar_rules, input).unwrap(),
547         ));
548     }
549 
550     #[test]
551     #[should_panic(expected = "grammar error
552 
553  --> 1:1
554   |
555 1 | ANY = { \"a\" }
556   | ^-^
557   |
558   = ANY is a pest keyword")]
pest_keyword()559     fn pest_keyword() {
560         let input = "ANY = { \"a\" }";
561         unwrap_or_report(validate_pairs(
562             PestParser::parse(Rule::grammar_rules, input).unwrap(),
563         ));
564     }
565 
566     #[test]
567     #[should_panic(expected = "grammar error
568 
569  --> 1:13
570   |
571 1 | a = { \"a\" } a = { \"a\" }
572   |             ^
573   |
574   = rule a already defined")]
already_defined()575     fn already_defined() {
576         let input = "a = { \"a\" } a = { \"a\" }";
577         unwrap_or_report(validate_pairs(
578             PestParser::parse(Rule::grammar_rules, input).unwrap(),
579         ));
580     }
581 
582     #[test]
583     #[should_panic(expected = "grammar error
584 
585  --> 1:7
586   |
587 1 | a = { b }
588   |       ^
589   |
590   = rule b is undefined")]
undefined()591     fn undefined() {
592         let input = "a = { b }";
593         unwrap_or_report(validate_pairs(
594             PestParser::parse(Rule::grammar_rules, input).unwrap(),
595         ));
596     }
597 
598     #[test]
valid_recursion()599     fn valid_recursion() {
600         let input = "a = { \"\" ~ \"a\"? ~ \"a\"* ~ (\"a\" | \"b\") ~ a }";
601         unwrap_or_report(consume_rules(
602             PestParser::parse(Rule::grammar_rules, input).unwrap(),
603         ));
604     }
605 
606     #[test]
607     #[should_panic(expected = "grammar error
608 
609  --> 1:16
610   |
611 1 | WHITESPACE = { \"\" }
612   |                ^^
613   |
614   = WHITESPACE cannot fail and will repeat infinitely")]
non_failing_whitespace()615     fn non_failing_whitespace() {
616         let input = "WHITESPACE = { \"\" }";
617         unwrap_or_report(consume_rules(
618             PestParser::parse(Rule::grammar_rules, input).unwrap(),
619         ));
620     }
621 
622     #[test]
623     #[should_panic(expected = "grammar error
624 
625  --> 1:13
626   |
627 1 | COMMENT = { soi }
628   |             ^-^
629   |
630   = COMMENT is non-progressing and will repeat infinitely")]
non_progressing_comment()631     fn non_progressing_comment() {
632         let input = "COMMENT = { soi }";
633         unwrap_or_report(consume_rules(
634             PestParser::parse(Rule::grammar_rules, input).unwrap(),
635         ));
636     }
637 
638     #[test]
639     #[should_panic(expected = "grammar error
640 
641  --> 1:7
642   |
643 1 | a = { (\"\")* }
644   |       ^---^
645   |
646   = expression inside repetition cannot fail and will repeat infinitely")]
non_failing_repetition()647     fn non_failing_repetition() {
648         let input = "a = { (\"\")* }";
649         unwrap_or_report(consume_rules(
650             PestParser::parse(Rule::grammar_rules, input).unwrap(),
651         ));
652     }
653 
654     #[test]
655     #[should_panic(expected = "grammar error
656 
657  --> 1:18
658   |
659 1 | a = { \"\" } b = { a* }
660   |                  ^^
661   |
662   = expression inside repetition cannot fail and will repeat infinitely")]
indirect_non_failing_repetition()663     fn indirect_non_failing_repetition() {
664         let input = "a = { \"\" } b = { a* }";
665         unwrap_or_report(consume_rules(
666             PestParser::parse(Rule::grammar_rules, input).unwrap(),
667         ));
668     }
669 
670     #[test]
671     #[should_panic(expected = "grammar error
672 
673  --> 1:20
674   |
675 1 | a = { \"a\" ~ (\"b\" ~ (\"\")*) }
676   |                    ^---^
677   |
678   = expression inside repetition cannot fail and will repeat infinitely")]
deep_non_failing_repetition()679     fn deep_non_failing_repetition() {
680         let input = "a = { \"a\" ~ (\"b\" ~ (\"\")*) }";
681         unwrap_or_report(consume_rules(
682             PestParser::parse(Rule::grammar_rules, input).unwrap(),
683         ));
684     }
685 
686     #[test]
687     #[should_panic(expected = "grammar error
688 
689  --> 1:7
690   |
691 1 | a = { (\"\" ~ &\"a\" ~ !\"a\" ~ (soi | eoi))* }
692   |       ^-------------------------------^
693   |
694   = expression inside repetition is non-progressing and will repeat infinitely")]
non_progressing_repetition()695     fn non_progressing_repetition() {
696         let input = "a = { (\"\" ~ &\"a\" ~ !\"a\" ~ (soi | eoi))* }";
697         unwrap_or_report(consume_rules(
698             PestParser::parse(Rule::grammar_rules, input).unwrap(),
699         ));
700     }
701 
702     #[test]
703     #[should_panic(expected = "grammar error
704 
705  --> 1:20
706   |
707 1 | a = { !\"a\" } b = { a* }
708   |                    ^^
709   |
710   = expression inside repetition is non-progressing and will repeat infinitely")]
indirect_non_progressing_repetition()711     fn indirect_non_progressing_repetition() {
712         let input = "a = { !\"a\" } b = { a* }";
713         unwrap_or_report(consume_rules(
714             PestParser::parse(Rule::grammar_rules, input).unwrap(),
715         ));
716     }
717 
718     #[test]
719     #[should_panic(expected = "grammar error
720 
721  --> 1:7
722   |
723 1 | a = { a }
724   |       ^
725   |
726   = rule a is left-recursive (a -> a); pest::prec_climber might be useful in this case")]
simple_left_recursion()727     fn simple_left_recursion() {
728         let input = "a = { a }";
729         unwrap_or_report(consume_rules(
730             PestParser::parse(Rule::grammar_rules, input).unwrap(),
731         ));
732     }
733 
734     #[test]
735     #[should_panic(expected = "grammar error
736 
737  --> 1:7
738   |
739 1 | a = { b } b = { a }
740   |       ^
741   |
742   = rule b is left-recursive (b -> a -> b); pest::prec_climber might be useful in this case
743 
744  --> 1:17
745   |
746 1 | a = { b } b = { a }
747   |                 ^
748   |
749   = rule a is left-recursive (a -> b -> a); pest::prec_climber might be useful in this case")]
indirect_left_recursion()750     fn indirect_left_recursion() {
751         let input = "a = { b } b = { a }";
752         unwrap_or_report(consume_rules(
753             PestParser::parse(Rule::grammar_rules, input).unwrap(),
754         ));
755     }
756 
757     #[test]
758     #[should_panic(expected = "grammar error
759 
760  --> 1:39
761   |
762 1 | a = { \"\" ~ \"a\"? ~ \"a\"* ~ (\"a\" | \"\") ~ a }
763   |                                       ^
764   |
765   = rule a is left-recursive (a -> a); pest::prec_climber might be useful in this case")]
non_failing_left_recursion()766     fn non_failing_left_recursion() {
767         let input = "a = { \"\" ~ \"a\"? ~ \"a\"* ~ (\"a\" | \"\") ~ a }";
768         unwrap_or_report(consume_rules(
769             PestParser::parse(Rule::grammar_rules, input).unwrap(),
770         ));
771     }
772 
773     #[test]
774     #[should_panic(expected = "grammar error
775 
776  --> 1:13
777   |
778 1 | a = { \"a\" | a }
779   |             ^
780   |
781   = rule a is left-recursive (a -> a); pest::prec_climber might be useful in this case")]
non_primary_choice_left_recursion()782     fn non_primary_choice_left_recursion() {
783         let input = "a = { \"a\" | a }";
784         unwrap_or_report(consume_rules(
785             PestParser::parse(Rule::grammar_rules, input).unwrap(),
786         ));
787     }
788 
789     #[test]
790     #[should_panic(expected = "grammar error
791 
792  --> 1:7
793   |
794 1 | a = { \"a\"* | \"a\" | \"b\" }
795   |       ^--^
796   |
797   = expression cannot fail; following choices cannot be reached")]
lhs_non_failing_choice()798     fn lhs_non_failing_choice() {
799         let input = "a = { \"a\"* | \"a\" | \"b\" }";
800         unwrap_or_report(consume_rules(
801             PestParser::parse(Rule::grammar_rules, input).unwrap(),
802         ));
803     }
804 
805     #[test]
806     #[should_panic(expected = "grammar error
807 
808  --> 1:13
809   |
810 1 | a = { \"a\" | \"a\"* | \"b\" }
811   |             ^--^
812   |
813   = expression cannot fail; following choices cannot be reached")]
lhs_non_failing_choice_middle()814     fn lhs_non_failing_choice_middle() {
815         let input = "a = { \"a\" | \"a\"* | \"b\" }";
816         unwrap_or_report(consume_rules(
817             PestParser::parse(Rule::grammar_rules, input).unwrap(),
818         ));
819     }
820 
821     #[test]
822     #[should_panic(expected = "grammar error
823 
824  --> 1:7
825   |
826 1 | a = { b | \"a\" } b = { \"b\"* | \"c\" }
827   |       ^
828   |
829   = expression cannot fail; following choices cannot be reached
830 
831  --> 1:23
832   |
833 1 | a = { b | \"a\" } b = { \"b\"* | \"c\" }
834   |                       ^--^
835   |
836   = expression cannot fail; following choices cannot be reached")]
lhs_non_failing_nested_choices()837     fn lhs_non_failing_nested_choices() {
838         let input = "a = { b | \"a\" } b = { \"b\"* | \"c\" }";
839         unwrap_or_report(consume_rules(
840             PestParser::parse(Rule::grammar_rules, input).unwrap(),
841         ));
842     }
843 
844     #[test]
skip_can_be_defined()845     fn skip_can_be_defined() {
846         let input = "skip = { \"\" }";
847         unwrap_or_report(consume_rules(
848             PestParser::parse(Rule::grammar_rules, input).unwrap(),
849         ));
850     }
851 }
852