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. |
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" ] |
122 | pub fn validate_rust_keywords(definitions: &Vec<Span<'_>>) -> Vec<Error<Rule>> { |
123 | let mut errors: Vec> = vec![]; |
124 | |
125 | for definition: &Span<'_> in definitions { |
126 | let name: &str = definition.as_str(); |
127 | |
128 | if RUST_KEYWORDS.contains(name) { |
129 | errors.push(Error::new_from_span( |
130 | variant:ErrorVariant::CustomError { |
131 | message: format!(" {} is a rust keyword" , name), |
132 | }, |
133 | *definition, |
134 | )) |
135 | } |
136 | } |
137 | |
138 | errors |
139 | } |
140 | |
141 | /// Validates that the given `definitions` do not contain any Pest keywords. |
142 | #[allow (clippy::ptr_arg)] |
143 | pub fn validate_pest_keywords(definitions: &Vec<Span<'_>>) -> Vec<Error<Rule>> { |
144 | let mut errors: Vec> = vec![]; |
145 | |
146 | for definition: &Span<'_> in definitions { |
147 | let name: &str = definition.as_str(); |
148 | |
149 | if PEST_KEYWORDS.contains(name) { |
150 | errors.push(Error::new_from_span( |
151 | variant:ErrorVariant::CustomError { |
152 | message: format!(" {} is a pest keyword" , name), |
153 | }, |
154 | *definition, |
155 | )) |
156 | } |
157 | } |
158 | |
159 | errors |
160 | } |
161 | |
162 | /// Validates that the given `definitions` do not contain any duplicate rules. |
163 | #[allow (clippy::ptr_arg)] |
164 | pub fn validate_already_defined(definitions: &Vec<Span<'_>>) -> Vec<Error<Rule>> { |
165 | let mut errors: Vec> = vec![]; |
166 | let mut defined: HashSet<&str> = HashSet::new(); |
167 | |
168 | for definition: &Span<'_> in definitions { |
169 | let name: &str = definition.as_str(); |
170 | |
171 | if defined.contains(&name) { |
172 | errors.push(Error::new_from_span( |
173 | variant:ErrorVariant::CustomError { |
174 | message: format!("rule {} already defined" , name), |
175 | }, |
176 | *definition, |
177 | )) |
178 | } else { |
179 | defined.insert(name); |
180 | } |
181 | } |
182 | |
183 | errors |
184 | } |
185 | |
186 | /// Validates that the given `definitions` do not contain any undefined rules. |
187 | #[allow (clippy::ptr_arg)] |
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> = vec![]; |
193 | let definitions: HashSet<_> = definitions.iter().map(|span: &Span<'_>| span.as_str()).collect(); |
194 | |
195 | for rule: &Span<'_> in called_rules { |
196 | let name: &str = rule.as_str(); |
197 | |
198 | if !definitions.contains(name) && !BUILTINS.contains(name) { |
199 | errors.push(Error::new_from_span( |
200 | variant:ErrorVariant::CustomError { |
201 | message: format!("rule {} is undefined" , name), |
202 | }, |
203 | *rule, |
204 | )) |
205 | } |
206 | } |
207 | |
208 | errors |
209 | } |
210 | |
211 | /// Validates the abstract syntax tree for common mistakes: |
212 | /// - infinite repetitions |
213 | /// - choices that cannot be reached |
214 | /// - left recursion |
215 | #[allow (clippy::ptr_arg)] |
216 | pub fn validate_ast<'a, 'i: 'a>(rules: &'a Vec<ParserRule<'i>>) -> Vec<Error<Rule>> { |
217 | let mut errors: Vec> = vec![]; |
218 | |
219 | // WARNING: validate_{repetition,choice,whitespace_comment} |
220 | // use is_non_failing and is_non_progressing breaking assumptions: |
221 | // - for every `ParserExpr::RepMinMax(inner,min,max)`, |
222 | // `min<=max` was not checked |
223 | // - left recursion was not checked |
224 | // - Every expression might not be checked |
225 | errors.extend(iter:validate_repetition(rules)); |
226 | errors.extend(iter:validate_choices(rules)); |
227 | errors.extend(iter:validate_whitespace_comment(rules)); |
228 | errors.extend(iter:validate_left_recursion(rules)); |
229 | |
230 | errors.sort_by_key(|error: &Error| match error.location { |
231 | InputLocation::Span(span: (usize, usize)) => 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 |
255 | 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 |
349 | 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 | |
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 | |
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 | |
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 | |
546 | fn validate_left_recursion<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> Vec<Error<Rule>> { |
547 | left_recursion(rules:to_hash_map(rules)) |
548 | } |
549 | |
550 | fn to_hash_map<'a, 'i: 'a>(rules: &'a [ParserRule<'i>]) -> HashMap<String, &'a ParserNode<'i>> { |
551 | rules.iter().map(|r: &ParserRule<'_>| (r.name.clone(), &r.node)).collect() |
552 | } |
553 | |
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" )] |
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" )] |
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" )] |
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 ] |
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" )] |
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" )] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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" )] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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 ] |
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" )] |
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" )] |
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" )] |
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" )] |
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" )] |
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" )] |
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" )] |
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" )] |
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" )] |
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" )] |
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" )] |
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" )] |
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 ] |
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 | |