re_parser/
lib.rs

1//! # re-parser
2//!
3//! A library for parsing regular expression patterns into an abstract syntax tree (AST).
4//!
5//! ## Supported syntax
6//!
7//! | Syntax | Description |
8//! |--------|-------------|
9//! | `a` | Literal character |
10//! | `.` | Any character (except newline) |
11//! | `^` `$` | Start / end of string anchors |
12//! | `\b` `\B` | Word / non-word boundary |
13//! | `\d` `\D` `\w` `\W` `\s` `\S` | Predefined character classes |
14//! | `[abc]` `[^abc]` `[a-z]` | Character classes |
15//! | `(...)` | Capturing group |
16//! | `(?P<name>...)` | Named capturing group |
17//! | `(?:...)` | Non-capturing group |
18//! | `(?=...)` `(?!...)` | Positive / negative lookahead |
19//! | `(?<=...)` `(?<!...)` | Positive / negative lookbehind |
20//! | `*` `+` `?` | Greedy quantifiers |
21//! | `*?` `+?` `??` | Lazy quantifiers |
22//! | `{n}` `{n,}` `{n,m}` | Counted quantifiers |
23//! | `a\|b` | Alternation |
24//! | `\n` `\t` `\r` | Common escape sequences |
25//!
26//! ## Example
27//!
28//! ```rust
29//! use re_parser::parse;
30//! use re_parser::ast::{Regex, QuantKind};
31//!
32//! let ast = parse(r"\d+").unwrap();
33//! // Regex::Quantifier(Box::new(Regex::EscapeClass(EscapeClass::Digit)), QuantKind::OneOrMore, true)
34//! println!("{ast:#?}");
35//! ```
36
37pub mod ast;
38pub mod error;
39mod parser;
40pub mod width;
41
42use crate::error::Result;
43use crate::parser::Parser;
44
45pub use width::Width;
46
47/// Parse a regex pattern string into an [`ast::Regex`] AST.
48///
49/// Returns [`error::ParseError`] on invalid syntax.
50pub fn parse(pattern: &str) -> Result<ast::Regex> {
51    Parser::new(pattern).parse()
52}
53
54/// Parse `pattern` and return the minimum and maximum number of characters it
55/// can match.
56///
57/// This is a convenience wrapper around [`parse`] + [`width::node_width`].
58///
59/// ```rust
60/// use re_parser::pattern_width;
61///
62/// let w = pattern_width(r"\d{4}-\d{2}-\d{2}").unwrap();
63/// assert_eq!(w.min, 10);
64/// assert_eq!(w.max, Some(10));
65/// assert!(w.is_fixed());
66/// ```
67pub fn pattern_width(pattern: &str) -> Result<Width> {
68    let ast = parse(pattern)?;
69    Ok(width::node_width(&ast))
70}
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75    use crate::ast::*;
76    use crate::error::ParseError;
77
78    // ---------------------------------------------------------------- literals
79
80    #[test]
81    fn test_single_literal() {
82        assert_eq!(parse("a"), Ok(Regex::Literal('a')));
83    }
84
85    #[test]
86    fn test_concat_literals() {
87        assert_eq!(
88            parse("ab"),
89            Ok(Regex::Concat(vec![Regex::Literal('a'), Regex::Literal('b')]))
90        );
91    }
92
93    #[test]
94    fn test_empty_pattern() {
95        assert_eq!(parse(""), Ok(Regex::Concat(vec![])));
96    }
97
98    // ---------------------------------------------------------------- any char
99
100    #[test]
101    fn test_any_char() {
102        assert_eq!(parse("."), Ok(Regex::AnyChar));
103    }
104
105    // --------------------------------------------------------------- anchors
106
107    #[test]
108    fn test_start_anchor() {
109        assert_eq!(parse("^"), Ok(Regex::Anchor(Anchor::Start)));
110    }
111
112    #[test]
113    fn test_end_anchor() {
114        assert_eq!(parse("$"), Ok(Regex::Anchor(Anchor::End)));
115    }
116
117    #[test]
118    fn test_word_boundary() {
119        assert_eq!(parse(r"\b"), Ok(Regex::Anchor(Anchor::WordBoundary)));
120    }
121
122    #[test]
123    fn test_non_word_boundary() {
124        assert_eq!(parse(r"\B"), Ok(Regex::Anchor(Anchor::NonWordBoundary)));
125    }
126
127    // --------------------------------------------------------- escape classes
128
129    #[test]
130    fn test_digit_class() {
131        assert_eq!(parse(r"\d"), Ok(Regex::EscapeClass(EscapeClass::Digit)));
132    }
133
134    #[test]
135    fn test_non_digit_class() {
136        assert_eq!(parse(r"\D"), Ok(Regex::EscapeClass(EscapeClass::NonDigit)));
137    }
138
139    #[test]
140    fn test_word_class() {
141        assert_eq!(parse(r"\w"), Ok(Regex::EscapeClass(EscapeClass::Word)));
142    }
143
144    #[test]
145    fn test_space_class() {
146        assert_eq!(parse(r"\s"), Ok(Regex::EscapeClass(EscapeClass::Space)));
147    }
148
149    #[test]
150    fn test_escaped_literal_dot() {
151        assert_eq!(parse(r"\."), Ok(Regex::Literal('.')));
152    }
153
154    #[test]
155    fn test_escaped_newline() {
156        assert_eq!(parse(r"\n"), Ok(Regex::Literal('\n')));
157    }
158
159    #[test]
160    fn test_invalid_escape() {
161        assert!(matches!(parse(r"\z"), Err(ParseError::InvalidEscape('z', _))));
162    }
163
164    // --------------------------------------------------------------- quantifiers
165
166    #[test]
167    fn test_star_greedy() {
168        assert_eq!(
169            parse("a*"),
170            Ok(Regex::Quantifier(
171                Box::new(Regex::Literal('a')),
172                QuantKind::ZeroOrMore,
173                true
174            ))
175        );
176    }
177
178    #[test]
179    fn test_plus_lazy() {
180        assert_eq!(
181            parse("a+?"),
182            Ok(Regex::Quantifier(
183                Box::new(Regex::Literal('a')),
184                QuantKind::OneOrMore,
185                false
186            ))
187        );
188    }
189
190    #[test]
191    fn test_question_mark() {
192        assert_eq!(
193            parse("a?"),
194            Ok(Regex::Quantifier(
195                Box::new(Regex::Literal('a')),
196                QuantKind::ZeroOrOne,
197                true
198            ))
199        );
200    }
201
202    #[test]
203    fn test_exact_quantifier() {
204        assert_eq!(
205            parse("a{3}"),
206            Ok(Regex::Quantifier(
207                Box::new(Regex::Literal('a')),
208                QuantKind::Exactly(3),
209                true
210            ))
211        );
212    }
213
214    #[test]
215    fn test_at_least_quantifier() {
216        assert_eq!(
217            parse("a{2,}"),
218            Ok(Regex::Quantifier(
219                Box::new(Regex::Literal('a')),
220                QuantKind::AtLeast(2),
221                true
222            ))
223        );
224    }
225
226    #[test]
227    fn test_between_quantifier() {
228        assert_eq!(
229            parse("a{1,5}"),
230            Ok(Regex::Quantifier(
231                Box::new(Regex::Literal('a')),
232                QuantKind::Between(1, 5),
233                true
234            ))
235        );
236    }
237
238    #[test]
239    fn test_between_min_gt_max_error() {
240        assert!(matches!(
241            parse("a{5,1}"),
242            Err(ParseError::InvalidQuantifier(_, _))
243        ));
244    }
245
246    // ---------------------------------------------------------- alternation
247
248    #[test]
249    fn test_alternation() {
250        assert_eq!(
251            parse("a|b"),
252            Ok(Regex::Alternation(vec![
253                Regex::Literal('a'),
254                Regex::Literal('b')
255            ]))
256        );
257    }
258
259    #[test]
260    fn test_multi_alternation() {
261        assert_eq!(
262            parse("a|b|c"),
263            Ok(Regex::Alternation(vec![
264                Regex::Literal('a'),
265                Regex::Literal('b'),
266                Regex::Literal('c'),
267            ]))
268        );
269    }
270
271    // --------------------------------------------------------------- groups
272
273    #[test]
274    fn test_capturing_group() {
275        assert_eq!(
276            parse("(a)"),
277            Ok(Regex::Group(
278                Box::new(Regex::Literal('a')),
279                GroupKind::Capturing
280            ))
281        );
282    }
283
284    #[test]
285    fn test_non_capturing_group() {
286        assert_eq!(
287            parse("(?:ab)"),
288            Ok(Regex::Group(
289                Box::new(Regex::Concat(vec![
290                    Regex::Literal('a'),
291                    Regex::Literal('b')
292                ])),
293                GroupKind::NonCapturing
294            ))
295        );
296    }
297
298    #[test]
299    fn test_named_group() {
300        assert_eq!(
301            parse("(?P<year>\\d+)"),
302            Ok(Regex::Group(
303                Box::new(Regex::Quantifier(
304                    Box::new(Regex::EscapeClass(EscapeClass::Digit)),
305                    QuantKind::OneOrMore,
306                    true
307                )),
308                GroupKind::Named("year".to_owned())
309            ))
310        );
311    }
312
313    #[test]
314    fn test_lookahead_pos() {
315        assert_eq!(
316            parse("a(?=b)"),
317            Ok(Regex::Concat(vec![
318                Regex::Literal('a'),
319                Regex::Group(Box::new(Regex::Literal('b')), GroupKind::LookaheadPos)
320            ]))
321        );
322    }
323
324    #[test]
325    fn test_lookahead_neg() {
326        assert_eq!(
327            parse("a(?!b)"),
328            Ok(Regex::Concat(vec![
329                Regex::Literal('a'),
330                Regex::Group(Box::new(Regex::Literal('b')), GroupKind::LookaheadNeg)
331            ]))
332        );
333    }
334
335    #[test]
336    fn test_lookbehind_pos() {
337        assert_eq!(
338            parse("(?<=a)b"),
339            Ok(Regex::Concat(vec![
340                Regex::Group(Box::new(Regex::Literal('a')), GroupKind::LookbehindPos),
341                Regex::Literal('b'),
342            ]))
343        );
344    }
345
346    #[test]
347    fn test_lookbehind_neg() {
348        assert_eq!(
349            parse("(?<!a)b"),
350            Ok(Regex::Concat(vec![
351                Regex::Group(Box::new(Regex::Literal('a')), GroupKind::LookbehindNeg),
352                Regex::Literal('b'),
353            ]))
354        );
355    }
356
357    #[test]
358    fn test_unmatched_open_paren() {
359        assert!(matches!(parse("(a"), Err(ParseError::UnmatchedOpenParen(_))));
360    }
361
362    #[test]
363    fn test_unmatched_close_paren() {
364        assert!(matches!(parse("a)"), Err(ParseError::UnmatchedCloseParen(_))));
365    }
366
367    // -------------------------------------------------------- character classes
368
369    #[test]
370    fn test_char_class_literals() {
371        assert_eq!(
372            parse("[abc]"),
373            Ok(Regex::CharClass(CharClass {
374                items: vec![
375                    CharClassItem::Literal('a'),
376                    CharClassItem::Literal('b'),
377                    CharClassItem::Literal('c'),
378                ],
379                negated: false,
380            }))
381        );
382    }
383
384    #[test]
385    fn test_char_class_negated() {
386        assert_eq!(
387            parse("[^abc]"),
388            Ok(Regex::CharClass(CharClass {
389                items: vec![
390                    CharClassItem::Literal('a'),
391                    CharClassItem::Literal('b'),
392                    CharClassItem::Literal('c'),
393                ],
394                negated: true,
395            }))
396        );
397    }
398
399    #[test]
400    fn test_char_class_range() {
401        assert_eq!(
402            parse("[a-z]"),
403            Ok(Regex::CharClass(CharClass {
404                items: vec![CharClassItem::Range('a', 'z')],
405                negated: false,
406            }))
407        );
408    }
409
410    #[test]
411    fn test_char_class_with_escape() {
412        assert_eq!(
413            parse(r"[\d]"),
414            Ok(Regex::CharClass(CharClass {
415                items: vec![CharClassItem::EscapeClass(EscapeClass::Digit)],
416                negated: false,
417            }))
418        );
419    }
420
421    #[test]
422    fn test_invalid_range() {
423        assert!(matches!(parse("[z-a]"), Err(ParseError::InvalidRange('z', 'a'))));
424    }
425
426    #[test]
427    fn test_unmatched_open_bracket() {
428        assert!(matches!(
429            parse("[abc"),
430            Err(ParseError::UnmatchedOpenBracket(_))
431        ));
432    }
433
434    // ----------------------------------------------------------- complex patterns
435
436    #[test]
437    fn test_email_like_pattern() {
438        // \w+@\w+\.\w+
439        let result = parse(r"\w+@\w+\.\w+");
440        assert!(result.is_ok());
441    }
442
443    #[test]
444    fn test_nested_groups() {
445        let result = parse("(a(b)c)");
446        assert!(result.is_ok());
447    }
448
449    #[test]
450    fn test_digit_plus() {
451        assert_eq!(
452            parse(r"\d+"),
453            Ok(Regex::Quantifier(
454                Box::new(Regex::EscapeClass(EscapeClass::Digit)),
455                QuantKind::OneOrMore,
456                true
457            ))
458        );
459    }
460
461    #[test]
462    fn test_complex_alternation_in_group() {
463        // (foo|bar)
464        let result = parse("(foo|bar)");
465        assert!(result.is_ok());
466        assert_eq!(
467            result.unwrap(),
468            Regex::Group(
469                Box::new(Regex::Alternation(vec![
470                    Regex::Concat(vec![
471                        Regex::Literal('f'),
472                        Regex::Literal('o'),
473                        Regex::Literal('o')
474                    ]),
475                    Regex::Concat(vec![
476                        Regex::Literal('b'),
477                        Regex::Literal('a'),
478                        Regex::Literal('r')
479                    ]),
480                ])),
481                GroupKind::Capturing,
482            )
483        );
484    }
485}
re_parser/lib.rs

re_parser/
lib.rs
