Skip to main content

regex_syntax/ast/
parse.rs

1/*!
2This module provides a regular expression parser.
3*/
4
5use core::{
6    borrow::Borrow,
7    cell::{Cell, RefCell},
8    mem,
9};
10
11use alloc::{
12    boxed::Box,
13    string::{String, ToString},
14    vec,
15    vec::Vec,
16};
17
18use crate::{
19    ast::{self, Ast, Position, Span},
20    either::Either,
21    is_escapeable_character, is_meta_character,
22};
23
24type Result<T> = core::result::Result<T, ast::Error>;
25
26/// A primitive is an expression with no sub-expressions. This includes
27/// literals, assertions and non-set character classes. This representation
28/// is used as intermediate state in the parser.
29///
30/// This does not include ASCII character classes, since they can only appear
31/// within a set character class.
32#[derive(Clone, Debug, Eq, PartialEq)]
33enum Primitive {
34    Literal(ast::Literal),
35    Assertion(ast::Assertion),
36    Dot(Span),
37    Perl(ast::ClassPerl),
38    Unicode(ast::ClassUnicode),
39}
40
41impl Primitive {
42    /// Return the span of this primitive.
43    fn span(&self) -> &Span {
44        match *self {
45            Primitive::Literal(ref x) => &x.span,
46            Primitive::Assertion(ref x) => &x.span,
47            Primitive::Dot(ref span) => span,
48            Primitive::Perl(ref x) => &x.span,
49            Primitive::Unicode(ref x) => &x.span,
50        }
51    }
52
53    /// Convert this primitive into a proper AST.
54    fn into_ast(self) -> Ast {
55        match self {
56            Primitive::Literal(lit) => Ast::literal(lit),
57            Primitive::Assertion(assert) => Ast::assertion(assert),
58            Primitive::Dot(span) => Ast::dot(span),
59            Primitive::Perl(cls) => Ast::class_perl(cls),
60            Primitive::Unicode(cls) => Ast::class_unicode(cls),
61        }
62    }
63
64    /// Convert this primitive into an item in a character class.
65    ///
66    /// If this primitive is not a legal item (i.e., an assertion or a dot),
67    /// then return an error.
68    fn into_class_set_item<P: Borrow<Parser>>(
69        self,
70        p: &ParserI<'_, P>,
71    ) -> Result<ast::ClassSetItem> {
72        use self::Primitive::*;
73        use crate::ast::ClassSetItem;
74
75        match self {
76            Literal(lit) => Ok(ClassSetItem::Literal(lit)),
77            Perl(cls) => Ok(ClassSetItem::Perl(cls)),
78            Unicode(cls) => Ok(ClassSetItem::Unicode(cls)),
79            x => Err(p.error(*x.span(), ast::ErrorKind::ClassEscapeInvalid)),
80        }
81    }
82
83    /// Convert this primitive into a literal in a character class. In
84    /// particular, literals are the only valid items that can appear in
85    /// ranges.
86    ///
87    /// If this primitive is not a legal item (i.e., a class, assertion or a
88    /// dot), then return an error.
89    fn into_class_literal<P: Borrow<Parser>>(
90        self,
91        p: &ParserI<'_, P>,
92    ) -> Result<ast::Literal> {
93        use self::Primitive::*;
94
95        match self {
96            Literal(lit) => Ok(lit),
97            x => Err(p.error(*x.span(), ast::ErrorKind::ClassRangeLiteral)),
98        }
99    }
100}
101
102/// Returns true if the given character is a hexadecimal digit.
103fn is_hex(c: char) -> bool {
104    ('0' <= c && c <= '9') || ('a' <= c && c <= 'f') || ('A' <= c && c <= 'F')
105}
106
107/// Returns true if the given character is a valid in a capture group name.
108///
109/// If `first` is true, then `c` is treated as the first character in the
110/// group name (which must be alphabetic or underscore).
111fn is_capture_char(c: char, first: bool) -> bool {
112    if first {
113        c == '_' || c.is_alphabetic()
114    } else {
115        c == '_' || c == '.' || c == '[' || c == ']' || c.is_alphanumeric()
116    }
117}
118
119/// A builder for a regular expression parser.
120///
121/// This builder permits modifying configuration options for the parser.
122#[derive(Clone, Debug)]
123pub struct ParserBuilder {
124    ignore_whitespace: bool,
125    nest_limit: u32,
126    octal: bool,
127    empty_min_range: bool,
128}
129
130impl Default for ParserBuilder {
131    fn default() -> ParserBuilder {
132        ParserBuilder::new()
133    }
134}
135
136impl ParserBuilder {
137    /// Create a new parser builder with a default configuration.
138    pub fn new() -> ParserBuilder {
139        ParserBuilder {
140            ignore_whitespace: false,
141            nest_limit: 250,
142            octal: false,
143            empty_min_range: false,
144        }
145    }
146
147    /// Build a parser from this configuration with the given pattern.
148    pub fn build(&self) -> Parser {
149        Parser {
150            pos: Cell::new(Position { offset: 0, line: 1, column: 1 }),
151            capture_index: Cell::new(0),
152            nest_limit: self.nest_limit,
153            octal: self.octal,
154            empty_min_range: self.empty_min_range,
155            initial_ignore_whitespace: self.ignore_whitespace,
156            ignore_whitespace: Cell::new(self.ignore_whitespace),
157            comments: RefCell::new(vec![]),
158            stack_group: RefCell::new(vec![]),
159            stack_class: RefCell::new(vec![]),
160            capture_names: RefCell::new(vec![]),
161            scratch: RefCell::new(String::new()),
162        }
163    }
164
165    /// Set the nesting limit for this parser.
166    ///
167    /// The nesting limit controls how deep the abstract syntax tree is allowed
168    /// to be. If the AST exceeds the given limit (e.g., with too many nested
169    /// groups), then an error is returned by the parser.
170    ///
171    /// The purpose of this limit is to act as a heuristic to prevent stack
172    /// overflow for consumers that do structural induction on an `Ast` using
173    /// explicit recursion. While this crate never does this (instead using
174    /// constant stack space and moving the call stack to the heap), other
175    /// crates may.
176    ///
177    /// This limit is not checked until the entire AST is parsed. Therefore,
178    /// if callers want to put a limit on the amount of heap space used, then
179    /// they should impose a limit on the length, in bytes, of the concrete
180    /// pattern string. In particular, this is viable since this parser
181    /// implementation will limit itself to heap space proportional to the
182    /// length of the pattern string.
183    ///
184    /// Note that a nest limit of `0` will return a nest limit error for most
185    /// patterns but not all. For example, a nest limit of `0` permits `a` but
186    /// not `ab`, since `ab` requires a concatenation, which results in a nest
187    /// depth of `1`. In general, a nest limit is not something that manifests
188    /// in an obvious way in the concrete syntax, therefore, it should not be
189    /// used in a granular way.
190    pub fn nest_limit(&mut self, limit: u32) -> &mut ParserBuilder {
191        self.nest_limit = limit;
192        self
193    }
194
195    /// Whether to support octal syntax or not.
196    ///
197    /// Octal syntax is a little-known way of uttering Unicode codepoints in
198    /// a regular expression. For example, `a`, `\x61`, `\u0061` and
199    /// `\141` are all equivalent regular expressions, where the last example
200    /// shows octal syntax.
201    ///
202    /// While supporting octal syntax isn't in and of itself a problem, it does
203    /// make good error messages harder. That is, in PCRE based regex engines,
204    /// syntax like `\0` invokes a backreference, which is explicitly
205    /// unsupported in Rust's regex engine. However, many users expect it to
206    /// be supported. Therefore, when octal support is disabled, the error
207    /// message will explicitly mention that backreferences aren't supported.
208    ///
209    /// Octal syntax is disabled by default.
210    pub fn octal(&mut self, yes: bool) -> &mut ParserBuilder {
211        self.octal = yes;
212        self
213    }
214
215    /// Enable verbose mode in the regular expression.
216    ///
217    /// When enabled, verbose mode permits insignificant whitespace in many
218    /// places in the regular expression, as well as comments. Comments are
219    /// started using `#` and continue until the end of the line.
220    ///
221    /// By default, this is disabled. It may be selectively enabled in the
222    /// regular expression by using the `x` flag regardless of this setting.
223    pub fn ignore_whitespace(&mut self, yes: bool) -> &mut ParserBuilder {
224        self.ignore_whitespace = yes;
225        self
226    }
227
228    /// Allow using `{,n}` as an equivalent to `{0,n}`.
229    ///
230    /// When enabled, the parser accepts `{,n}` as valid syntax for `{0,n}`.
231    /// Most regular expression engines don't support the `{,n}` syntax, but
232    /// some others do it, namely Python's `re` library.
233    ///
234    /// This is disabled by default.
235    pub fn empty_min_range(&mut self, yes: bool) -> &mut ParserBuilder {
236        self.empty_min_range = yes;
237        self
238    }
239}
240
241/// A regular expression parser.
242///
243/// This parses a string representation of a regular expression into an
244/// abstract syntax tree. The size of the tree is proportional to the length
245/// of the regular expression pattern.
246///
247/// A `Parser` can be configured in more detail via a [`ParserBuilder`].
248#[derive(Clone, Debug)]
249pub struct Parser {
250    /// The current position of the parser.
251    pos: Cell<Position>,
252    /// The current capture index.
253    capture_index: Cell<u32>,
254    /// The maximum number of open parens/brackets allowed. If the parser
255    /// exceeds this number, then an error is returned.
256    nest_limit: u32,
257    /// Whether to support octal syntax or not. When `false`, the parser will
258    /// return an error helpfully pointing out that backreferences are not
259    /// supported.
260    octal: bool,
261    /// The initial setting for `ignore_whitespace` as provided by
262    /// `ParserBuilder`. It is used when resetting the parser's state.
263    initial_ignore_whitespace: bool,
264    /// Whether the parser supports `{,n}` repetitions as an equivalent to
265    /// `{0,n}.`
266    empty_min_range: bool,
267    /// Whether whitespace should be ignored. When enabled, comments are
268    /// also permitted.
269    ignore_whitespace: Cell<bool>,
270    /// A list of comments, in order of appearance.
271    comments: RefCell<Vec<ast::Comment>>,
272    /// A stack of grouped sub-expressions, including alternations.
273    stack_group: RefCell<Vec<GroupState>>,
274    /// A stack of nested character classes. This is only non-empty when
275    /// parsing a class.
276    stack_class: RefCell<Vec<ClassState>>,
277    /// A sorted sequence of capture names. This is used to detect duplicate
278    /// capture names and report an error if one is detected.
279    capture_names: RefCell<Vec<ast::CaptureName>>,
280    /// A scratch buffer used in various places. Mostly this is used to
281    /// accumulate relevant characters from parts of a pattern.
282    scratch: RefCell<String>,
283}
284
285/// ParserI is the internal parser implementation.
286///
287/// We use this separate type so that we can carry the provided pattern string
288/// along with us. In particular, a `Parser` internal state is not tied to any
289/// one pattern, but `ParserI` is.
290///
291/// This type also lets us use `ParserI<&Parser>` in production code while
292/// retaining the convenience of `ParserI<Parser>` for tests, which sometimes
293/// work against the internal interface of the parser.
294#[derive(Clone, Debug)]
295struct ParserI<'s, P> {
296    /// The parser state/configuration.
297    parser: P,
298    /// The full regular expression provided by the user.
299    pattern: &'s str,
300}
301
302/// GroupState represents a single stack frame while parsing nested groups
303/// and alternations. Each frame records the state up to an opening parenthesis
304/// or a alternating bracket `|`.
305#[derive(Clone, Debug)]
306enum GroupState {
307    /// This state is pushed whenever an opening group is found.
308    Group {
309        /// The concatenation immediately preceding the opening group.
310        concat: ast::Concat,
311        /// The group that has been opened. Its sub-AST is always empty.
312        group: ast::Group,
313        /// Whether this group has the `x` flag enabled or not.
314        ignore_whitespace: bool,
315    },
316    /// This state is pushed whenever a new alternation branch is found. If
317    /// an alternation branch is found and this state is at the top of the
318    /// stack, then this state should be modified to include the new
319    /// alternation.
320    Alternation(ast::Alternation),
321}
322
323/// ClassState represents a single stack frame while parsing character classes.
324/// Each frame records the state up to an intersection, difference, symmetric
325/// difference or nested class.
326///
327/// Note that a parser's character class stack is only non-empty when parsing
328/// a character class. In all other cases, it is empty.
329#[derive(Clone, Debug)]
330enum ClassState {
331    /// This state is pushed whenever an opening bracket is found.
332    Open {
333        /// The union of class items immediately preceding this class.
334        union: ast::ClassSetUnion,
335        /// The class that has been opened. Typically this just corresponds
336        /// to the `[`, but it can also include `[^` since `^` indicates
337        /// negation of the class.
338        set: ast::ClassBracketed,
339    },
340    /// This state is pushed when a operator is seen. When popped, the stored
341    /// set becomes the left hand side of the operator.
342    Op {
343        /// The type of the operation, i.e., &&, -- or ~~.
344        kind: ast::ClassSetBinaryOpKind,
345        /// The left-hand side of the operator.
346        lhs: ast::ClassSet,
347    },
348}
349
350impl Parser {
351    /// Create a new parser with a default configuration.
352    ///
353    /// The parser can be run with either the `parse` or `parse_with_comments`
354    /// methods. The parse methods return an abstract syntax tree.
355    ///
356    /// To set configuration options on the parser, use [`ParserBuilder`].
357    pub fn new() -> Parser {
358        ParserBuilder::new().build()
359    }
360
361    /// Parse the regular expression into an abstract syntax tree.
362    pub fn parse(&mut self, pattern: &str) -> Result<Ast> {
363        ParserI::new(self, pattern).parse()
364    }
365
366    /// Parse the regular expression and return an abstract syntax tree with
367    /// all of the comments found in the pattern.
368    pub fn parse_with_comments(
369        &mut self,
370        pattern: &str,
371    ) -> Result<ast::WithComments> {
372        ParserI::new(self, pattern).parse_with_comments()
373    }
374
375    /// Reset the internal state of a parser.
376    ///
377    /// This is called at the beginning of every parse. This prevents the
378    /// parser from running with inconsistent state (say, if a previous
379    /// invocation returned an error and the parser is reused).
380    fn reset(&self) {
381        // These settings should be in line with the construction
382        // in `ParserBuilder::build`.
383        self.pos.set(Position { offset: 0, line: 1, column: 1 });
384        self.capture_index.set(0);
385        self.ignore_whitespace.set(self.initial_ignore_whitespace);
386        self.comments.borrow_mut().clear();
387        self.stack_group.borrow_mut().clear();
388        self.stack_class.borrow_mut().clear();
389        self.capture_names.borrow_mut().clear();
390        self.scratch.borrow_mut().clear();
391    }
392}
393
394impl<'s, P: Borrow<Parser>> ParserI<'s, P> {
395    /// Build an internal parser from a parser configuration and a pattern.
396    fn new(parser: P, pattern: &'s str) -> ParserI<'s, P> {
397        ParserI { parser, pattern }
398    }
399
400    /// Return a reference to the parser state.
401    fn parser(&self) -> &Parser {
402        self.parser.borrow()
403    }
404
405    /// Return a reference to the pattern being parsed.
406    fn pattern(&self) -> &str {
407        self.pattern
408    }
409
410    /// Create a new error with the given span and error type.
411    fn error(&self, span: Span, kind: ast::ErrorKind) -> ast::Error {
412        ast::Error { kind, pattern: self.pattern().to_string(), span }
413    }
414
415    /// Return the current offset of the parser.
416    ///
417    /// The offset starts at `0` from the beginning of the regular expression
418    /// pattern string.
419    fn offset(&self) -> usize {
420        self.parser().pos.get().offset
421    }
422
423    /// Return the current line number of the parser.
424    ///
425    /// The line number starts at `1`.
426    fn line(&self) -> usize {
427        self.parser().pos.get().line
428    }
429
430    /// Return the current column of the parser.
431    ///
432    /// The column number starts at `1` and is reset whenever a `\n` is seen.
433    fn column(&self) -> usize {
434        self.parser().pos.get().column
435    }
436
437    /// Return the next capturing index. Each subsequent call increments the
438    /// internal index.
439    ///
440    /// The span given should correspond to the location of the opening
441    /// parenthesis.
442    ///
443    /// If the capture limit is exceeded, then an error is returned.
444    fn next_capture_index(&self, span: Span) -> Result<u32> {
445        let current = self.parser().capture_index.get();
446        let i = current.checked_add(1).ok_or_else(|| {
447            self.error(span, ast::ErrorKind::CaptureLimitExceeded)
448        })?;
449        self.parser().capture_index.set(i);
450        Ok(i)
451    }
452
453    /// Adds the given capture name to this parser. If this capture name has
454    /// already been used, then an error is returned.
455    fn add_capture_name(&self, cap: &ast::CaptureName) -> Result<()> {
456        let mut names = self.parser().capture_names.borrow_mut();
457        match names
458            .binary_search_by_key(&cap.name.as_str(), |c| c.name.as_str())
459        {
460            Err(i) => {
461                names.insert(i, cap.clone());
462                Ok(())
463            }
464            Ok(i) => Err(self.error(
465                cap.span,
466                ast::ErrorKind::GroupNameDuplicate { original: names[i].span },
467            )),
468        }
469    }
470
471    /// Return whether the parser should ignore whitespace or not.
472    fn ignore_whitespace(&self) -> bool {
473        self.parser().ignore_whitespace.get()
474    }
475
476    /// Return the character at the current position of the parser.
477    ///
478    /// This panics if the current position does not point to a valid char.
479    fn char(&self) -> char {
480        self.char_at(self.offset())
481    }
482
483    /// Return the character at the given position.
484    ///
485    /// This panics if the given position does not point to a valid char.
486    fn char_at(&self, i: usize) -> char {
487        self.pattern()[i..]
488            .chars()
489            .next()
490            .unwrap_or_else(|| panic!("expected char at offset {i}"))
491    }
492
493    /// Bump the parser to the next Unicode scalar value.
494    ///
495    /// If the end of the input has been reached, then `false` is returned.
496    fn bump(&self) -> bool {
497        if self.is_eof() {
498            return false;
499        }
500        let Position { mut offset, mut line, mut column } = self.pos();
501        if self.char() == '\n' {
502            line = line.checked_add(1).unwrap();
503            column = 1;
504        } else {
505            column = column.checked_add(1).unwrap();
506        }
507        offset += self.char().len_utf8();
508        self.parser().pos.set(Position { offset, line, column });
509        self.pattern()[self.offset()..].chars().next().is_some()
510    }
511
512    /// If the substring starting at the current position of the parser has
513    /// the given prefix, then bump the parser to the character immediately
514    /// following the prefix and return true. Otherwise, don't bump the parser
515    /// and return false.
516    fn bump_if(&self, prefix: &str) -> bool {
517        if self.pattern()[self.offset()..].starts_with(prefix) {
518            for _ in 0..prefix.chars().count() {
519                self.bump();
520            }
521            true
522        } else {
523            false
524        }
525    }
526
527    /// Returns true if and only if the parser is positioned at a look-around
528    /// prefix. The conditions under which this returns true must always
529    /// correspond to a regular expression that would otherwise be consider
530    /// invalid.
531    ///
532    /// This should only be called immediately after parsing the opening of
533    /// a group or a set of flags.
534    fn is_lookaround_prefix(&self) -> bool {
535        self.bump_if("?=")
536            || self.bump_if("?!")
537            || self.bump_if("?<=")
538            || self.bump_if("?<!")
539    }
540
541    /// Bump the parser, and if the `x` flag is enabled, bump through any
542    /// subsequent spaces. Return true if and only if the parser is not at
543    /// EOF.
544    fn bump_and_bump_space(&self) -> bool {
545        if !self.bump() {
546            return false;
547        }
548        self.bump_space();
549        !self.is_eof()
550    }
551
552    /// If the `x` flag is enabled (i.e., whitespace insensitivity with
553    /// comments), then this will advance the parser through all whitespace
554    /// and comments to the next non-whitespace non-comment byte.
555    ///
556    /// If the `x` flag is disabled, then this is a no-op.
557    ///
558    /// This should be used selectively throughout the parser where
559    /// arbitrary whitespace is permitted when the `x` flag is enabled. For
560    /// example, `{   5  , 6}` is equivalent to `{5,6}`.
561    fn bump_space(&self) {
562        if !self.ignore_whitespace() {
563            return;
564        }
565        while !self.is_eof() {
566            if self.char().is_whitespace() {
567                self.bump();
568            } else if self.char() == '#' {
569                let start = self.pos();
570                let mut comment_text = String::new();
571                self.bump();
572                while !self.is_eof() {
573                    let c = self.char();
574                    self.bump();
575                    if c == '\n' {
576                        break;
577                    }
578                    comment_text.push(c);
579                }
580                let comment = ast::Comment {
581                    span: Span::new(start, self.pos()),
582                    comment: comment_text,
583                };
584                self.parser().comments.borrow_mut().push(comment);
585            } else {
586                break;
587            }
588        }
589    }
590
591    /// Peek at the next character in the input without advancing the parser.
592    ///
593    /// If the input has been exhausted, then this returns `None`.
594    fn peek(&self) -> Option<char> {
595        if self.is_eof() {
596            return None;
597        }
598        self.pattern()[self.offset() + self.char().len_utf8()..].chars().next()
599    }
600
601    /// Like peek, but will ignore spaces when the parser is in whitespace
602    /// insensitive mode.
603    fn peek_space(&self) -> Option<char> {
604        if !self.ignore_whitespace() {
605            return self.peek();
606        }
607        if self.is_eof() {
608            return None;
609        }
610        let mut start = self.offset() + self.char().len_utf8();
611        let mut in_comment = false;
612        for (i, c) in self.pattern()[start..].char_indices() {
613            if c.is_whitespace() {
614                continue;
615            } else if !in_comment && c == '#' {
616                in_comment = true;
617            } else if in_comment && c == '\n' {
618                in_comment = false;
619            } else {
620                start += i;
621                break;
622            }
623        }
624        self.pattern()[start..].chars().next()
625    }
626
627    /// Returns true if the next call to `bump` would return false.
628    fn is_eof(&self) -> bool {
629        self.offset() == self.pattern().len()
630    }
631
632    /// Return the current position of the parser, which includes the offset,
633    /// line and column.
634    fn pos(&self) -> Position {
635        self.parser().pos.get()
636    }
637
638    /// Create a span at the current position of the parser. Both the start
639    /// and end of the span are set.
640    fn span(&self) -> Span {
641        Span::splat(self.pos())
642    }
643
644    /// Create a span that covers the current character.
645    fn span_char(&self) -> Span {
646        let mut next = Position {
647            offset: self.offset().checked_add(self.char().len_utf8()).unwrap(),
648            line: self.line(),
649            column: self.column().checked_add(1).unwrap(),
650        };
651        if self.char() == '\n' {
652            next.line += 1;
653            next.column = 1;
654        }
655        Span::new(self.pos(), next)
656    }
657
658    /// Parse and push a single alternation on to the parser's internal stack.
659    /// If the top of the stack already has an alternation, then add to that
660    /// instead of pushing a new one.
661    ///
662    /// The concatenation given corresponds to a single alternation branch.
663    /// The concatenation returned starts the next branch and is empty.
664    ///
665    /// This assumes the parser is currently positioned at `|` and will advance
666    /// the parser to the character following `|`.
667    #[inline(never)]
668    fn push_alternate(&self, mut concat: ast::Concat) -> Result<ast::Concat> {
669        assert_eq!(self.char(), '|');
670        concat.span.end = self.pos();
671        self.push_or_add_alternation(concat);
672        self.bump();
673        Ok(ast::Concat { span: self.span(), asts: vec![] })
674    }
675
676    /// Pushes or adds the given branch of an alternation to the parser's
677    /// internal stack of state.
678    fn push_or_add_alternation(&self, concat: ast::Concat) {
679        use self::GroupState::*;
680
681        let mut stack = self.parser().stack_group.borrow_mut();
682        if let Some(&mut Alternation(ref mut alts)) = stack.last_mut() {
683            alts.asts.push(concat.into_ast());
684            return;
685        }
686        stack.push(Alternation(ast::Alternation {
687            span: Span::new(concat.span.start, self.pos()),
688            asts: vec![concat.into_ast()],
689        }));
690    }
691
692    /// Parse and push a group AST (and its parent concatenation) on to the
693    /// parser's internal stack. Return a fresh concatenation corresponding
694    /// to the group's sub-AST.
695    ///
696    /// If a set of flags was found (with no group), then the concatenation
697    /// is returned with that set of flags added.
698    ///
699    /// This assumes that the parser is currently positioned on the opening
700    /// parenthesis. It advances the parser to the character at the start
701    /// of the sub-expression (or adjoining expression).
702    ///
703    /// If there was a problem parsing the start of the group, then an error
704    /// is returned.
705    #[inline(never)]
706    fn push_group(&self, mut concat: ast::Concat) -> Result<ast::Concat> {
707        assert_eq!(self.char(), '(');
708        match self.parse_group()? {
709            Either::Left(set) => {
710                let ignore = set.flags.flag_state(ast::Flag::IgnoreWhitespace);
711                if let Some(v) = ignore {
712                    self.parser().ignore_whitespace.set(v);
713                }
714
715                concat.asts.push(Ast::flags(set));
716                Ok(concat)
717            }
718            Either::Right(group) => {
719                let old_ignore_whitespace = self.ignore_whitespace();
720                let new_ignore_whitespace = group
721                    .flags()
722                    .and_then(|f| f.flag_state(ast::Flag::IgnoreWhitespace))
723                    .unwrap_or(old_ignore_whitespace);
724                self.parser().stack_group.borrow_mut().push(
725                    GroupState::Group {
726                        concat,
727                        group,
728                        ignore_whitespace: old_ignore_whitespace,
729                    },
730                );
731                self.parser().ignore_whitespace.set(new_ignore_whitespace);
732                Ok(ast::Concat { span: self.span(), asts: vec![] })
733            }
734        }
735    }
736
737    /// Pop a group AST from the parser's internal stack and set the group's
738    /// AST to the given concatenation. Return the concatenation containing
739    /// the group.
740    ///
741    /// This assumes that the parser is currently positioned on the closing
742    /// parenthesis and advances the parser to the character following the `)`.
743    ///
744    /// If no such group could be popped, then an unopened group error is
745    /// returned.
746    #[inline(never)]
747    fn pop_group(&self, mut group_concat: ast::Concat) -> Result<ast::Concat> {
748        use self::GroupState::*;
749
750        assert_eq!(self.char(), ')');
751        let mut stack = self.parser().stack_group.borrow_mut();
752        let (mut prior_concat, mut group, ignore_whitespace, alt) = match stack
753            .pop()
754        {
755            Some(Group { concat, group, ignore_whitespace }) => {
756                (concat, group, ignore_whitespace, None)
757            }
758            Some(Alternation(alt)) => match stack.pop() {
759                Some(Group { concat, group, ignore_whitespace }) => {
760                    (concat, group, ignore_whitespace, Some(alt))
761                }
762                None | Some(Alternation(_)) => {
763                    return Err(self.error(
764                        self.span_char(),
765                        ast::ErrorKind::GroupUnopened,
766                    ));
767                }
768            },
769            None => {
770                return Err(self
771                    .error(self.span_char(), ast::ErrorKind::GroupUnopened));
772            }
773        };
774        self.parser().ignore_whitespace.set(ignore_whitespace);
775        group_concat.span.end = self.pos();
776        self.bump();
777        group.span.end = self.pos();
778        match alt {
779            Some(mut alt) => {
780                alt.span.end = group_concat.span.end;
781                alt.asts.push(group_concat.into_ast());
782                group.ast = Box::new(alt.into_ast());
783            }
784            None => {
785                group.ast = Box::new(group_concat.into_ast());
786            }
787        }
788        prior_concat.asts.push(Ast::group(group));
789        Ok(prior_concat)
790    }
791
792    /// Pop the last state from the parser's internal stack, if it exists, and
793    /// add the given concatenation to it. There either must be no state or a
794    /// single alternation item on the stack. Any other scenario produces an
795    /// error.
796    ///
797    /// This assumes that the parser has advanced to the end.
798    #[inline(never)]
799    fn pop_group_end(&self, mut concat: ast::Concat) -> Result<Ast> {
800        concat.span.end = self.pos();
801        let mut stack = self.parser().stack_group.borrow_mut();
802        let ast = match stack.pop() {
803            None => Ok(concat.into_ast()),
804            Some(GroupState::Alternation(mut alt)) => {
805                alt.span.end = self.pos();
806                alt.asts.push(concat.into_ast());
807                Ok(Ast::alternation(alt))
808            }
809            Some(GroupState::Group { group, .. }) => {
810                return Err(
811                    self.error(group.span, ast::ErrorKind::GroupUnclosed)
812                );
813            }
814        };
815        // If we try to pop again, there should be nothing.
816        match stack.pop() {
817            None => ast,
818            Some(GroupState::Alternation(_)) => {
819                // This unreachable is unfortunate. This case can't happen
820                // because the only way we can be here is if there were two
821                // `GroupState::Alternation`s adjacent in the parser's stack,
822                // which we guarantee to never happen because we never push a
823                // `GroupState::Alternation` if one is already at the top of
824                // the stack.
825                unreachable!()
826            }
827            Some(GroupState::Group { group, .. }) => {
828                Err(self.error(group.span, ast::ErrorKind::GroupUnclosed))
829            }
830        }
831    }
832
833    /// Parse the opening of a character class and push the current class
834    /// parsing context onto the parser's stack. This assumes that the parser
835    /// is positioned at an opening `[`. The given union should correspond to
836    /// the union of set items built up before seeing the `[`.
837    ///
838    /// If there was a problem parsing the opening of the class, then an error
839    /// is returned. Otherwise, a new union of set items for the class is
840    /// returned (which may be populated with either a `]` or a `-`).
841    #[inline(never)]
842    fn push_class_open(
843        &self,
844        parent_union: ast::ClassSetUnion,
845    ) -> Result<ast::ClassSetUnion> {
846        assert_eq!(self.char(), '[');
847
848        let (nested_set, nested_union) = self.parse_set_class_open()?;
849        self.parser()
850            .stack_class
851            .borrow_mut()
852            .push(ClassState::Open { union: parent_union, set: nested_set });
853        Ok(nested_union)
854    }
855
856    /// Parse the end of a character class set and pop the character class
857    /// parser stack. The union given corresponds to the last union built
858    /// before seeing the closing `]`. The union returned corresponds to the
859    /// parent character class set with the nested class added to it.
860    ///
861    /// This assumes that the parser is positioned at a `]` and will advance
862    /// the parser to the byte immediately following the `]`.
863    ///
864    /// If the stack is empty after popping, then this returns the final
865    /// "top-level" character class AST (where a "top-level" character class
866    /// is one that is not nested inside any other character class).
867    ///
868    /// If there is no corresponding opening bracket on the parser's stack,
869    /// then an error is returned.
870    #[inline(never)]
871    fn pop_class(
872        &self,
873        nested_union: ast::ClassSetUnion,
874    ) -> Result<Either<ast::ClassSetUnion, ast::ClassBracketed>> {
875        assert_eq!(self.char(), ']');
876
877        let item = ast::ClassSet::Item(nested_union.into_item());
878        let prevset = self.pop_class_op(item);
879        let mut stack = self.parser().stack_class.borrow_mut();
880        match stack.pop() {
881            None => {
882                // We can never observe an empty stack:
883                //
884                // 1) We are guaranteed to start with a non-empty stack since
885                //    the character class parser is only initiated when it sees
886                //    a `[`.
887                // 2) If we ever observe an empty stack while popping after
888                //    seeing a `]`, then we signal the character class parser
889                //    to terminate.
890                panic!("unexpected empty character class stack")
891            }
892            Some(ClassState::Op { .. }) => {
893                // This panic is unfortunate, but this case is impossible
894                // since we already popped the Op state if one exists above.
895                // Namely, every push to the class parser stack is guarded by
896                // whether an existing Op is already on the top of the stack.
897                // If it is, the existing Op is modified. That is, the stack
898                // can never have consecutive Op states.
899                panic!("unexpected ClassState::Op")
900            }
901            Some(ClassState::Open { mut union, mut set }) => {
902                self.bump();
903                set.span.end = self.pos();
904                set.kind = prevset;
905                if stack.is_empty() {
906                    Ok(Either::Right(set))
907                } else {
908                    union.push(ast::ClassSetItem::Bracketed(Box::new(set)));
909                    Ok(Either::Left(union))
910                }
911            }
912        }
913    }
914
915    /// Return an "unclosed class" error whose span points to the most
916    /// recently opened class.
917    ///
918    /// This should only be called while parsing a character class.
919    #[inline(never)]
920    fn unclosed_class_error(&self) -> ast::Error {
921        for state in self.parser().stack_class.borrow().iter().rev() {
922            if let ClassState::Open { ref set, .. } = *state {
923                return self.error(set.span, ast::ErrorKind::ClassUnclosed);
924            }
925        }
926        // We are guaranteed to have a non-empty stack with at least
927        // one open bracket, so we should never get here.
928        panic!("no open character class found")
929    }
930
931    /// Push the current set of class items on to the class parser's stack as
932    /// the left hand side of the given operator.
933    ///
934    /// A fresh set union is returned, which should be used to build the right
935    /// hand side of this operator.
936    #[inline(never)]
937    fn push_class_op(
938        &self,
939        next_kind: ast::ClassSetBinaryOpKind,
940        next_union: ast::ClassSetUnion,
941    ) -> ast::ClassSetUnion {
942        let item = ast::ClassSet::Item(next_union.into_item());
943        let new_lhs = self.pop_class_op(item);
944        self.parser()
945            .stack_class
946            .borrow_mut()
947            .push(ClassState::Op { kind: next_kind, lhs: new_lhs });
948        ast::ClassSetUnion { span: self.span(), items: vec![] }
949    }
950
951    /// Pop a character class set from the character class parser stack. If the
952    /// top of the stack is just an item (not an operation), then return the
953    /// given set unchanged. If the top of the stack is an operation, then the
954    /// given set will be used as the rhs of the operation on the top of the
955    /// stack. In that case, the binary operation is returned as a set.
956    #[inline(never)]
957    fn pop_class_op(&self, rhs: ast::ClassSet) -> ast::ClassSet {
958        let mut stack = self.parser().stack_class.borrow_mut();
959        let (kind, lhs) = match stack.pop() {
960            Some(ClassState::Op { kind, lhs }) => (kind, lhs),
961            Some(state @ ClassState::Open { .. }) => {
962                stack.push(state);
963                return rhs;
964            }
965            None => unreachable!(),
966        };
967        let span = Span::new(lhs.span().start, rhs.span().end);
968        ast::ClassSet::BinaryOp(ast::ClassSetBinaryOp {
969            span,
970            kind,
971            lhs: Box::new(lhs),
972            rhs: Box::new(rhs),
973        })
974    }
975}
976
977impl<'s, P: Borrow<Parser>> ParserI<'s, P> {
978    /// Parse the regular expression into an abstract syntax tree.
979    fn parse(&self) -> Result<Ast> {
980        self.parse_with_comments().map(|astc| astc.ast)
981    }
982
983    /// Parse the regular expression and return an abstract syntax tree with
984    /// all of the comments found in the pattern.
985    fn parse_with_comments(&self) -> Result<ast::WithComments> {
986        // Reset before reading parser state so a Parser can be reused.
987        self.parser().reset();
988        let mut concat = ast::Concat { span: self.span(), asts: vec![] };
989        loop {
990            self.bump_space();
991            if self.is_eof() {
992                break;
993            }
994            match self.char() {
995                '(' => concat = self.push_group(concat)?,
996                ')' => concat = self.pop_group(concat)?,
997                '|' => concat = self.push_alternate(concat)?,
998                '[' => {
999                    let class = self.parse_set_class()?;
1000                    concat.asts.push(Ast::class_bracketed(class));
1001                }
1002                '?' => {
1003                    concat = self.parse_uncounted_repetition(
1004                        concat,
1005                        ast::RepetitionKind::ZeroOrOne,
1006                    )?;
1007                }
1008                '*' => {
1009                    concat = self.parse_uncounted_repetition(
1010                        concat,
1011                        ast::RepetitionKind::ZeroOrMore,
1012                    )?;
1013                }
1014                '+' => {
1015                    concat = self.parse_uncounted_repetition(
1016                        concat,
1017                        ast::RepetitionKind::OneOrMore,
1018                    )?;
1019                }
1020                '{' => {
1021                    concat = self.parse_counted_repetition(concat)?;
1022                }
1023                _ => concat.asts.push(self.parse_primitive()?.into_ast()),
1024            }
1025        }
1026        let ast = self.pop_group_end(concat)?;
1027        NestLimiter::new(self).check(&ast)?;
1028        Ok(ast::WithComments {
1029            ast,
1030            comments: mem::replace(
1031                &mut *self.parser().comments.borrow_mut(),
1032                vec![],
1033            ),
1034        })
1035    }
1036
1037    /// Parses an uncounted repetition operation. An uncounted repetition
1038    /// operator includes ?, * and +, but does not include the {m,n} syntax.
1039    /// The given `kind` should correspond to the operator observed by the
1040    /// caller.
1041    ///
1042    /// This assumes that the parser is currently positioned at the repetition
1043    /// operator and advances the parser to the first character after the
1044    /// operator. (Note that the operator may include a single additional `?`,
1045    /// which makes the operator ungreedy.)
1046    ///
1047    /// The caller should include the concatenation that is being built. The
1048    /// concatenation returned includes the repetition operator applied to the
1049    /// last expression in the given concatenation.
1050    #[inline(never)]
1051    fn parse_uncounted_repetition(
1052        &self,
1053        mut concat: ast::Concat,
1054        kind: ast::RepetitionKind,
1055    ) -> Result<ast::Concat> {
1056        assert!(
1057            self.char() == '?' || self.char() == '*' || self.char() == '+'
1058        );
1059        let op_start = self.pos();
1060        let ast = match concat.asts.pop() {
1061            Some(ast) => ast,
1062            None => {
1063                return Err(
1064                    self.error(self.span(), ast::ErrorKind::RepetitionMissing)
1065                )
1066            }
1067        };
1068        match ast {
1069            Ast::Empty(_) | Ast::Flags(_) => {
1070                return Err(
1071                    self.error(self.span(), ast::ErrorKind::RepetitionMissing)
1072                )
1073            }
1074            _ => {}
1075        }
1076        let mut greedy = true;
1077        if self.bump() && self.char() == '?' {
1078            greedy = false;
1079            self.bump();
1080        }
1081        concat.asts.push(Ast::repetition(ast::Repetition {
1082            span: ast.span().with_end(self.pos()),
1083            op: ast::RepetitionOp {
1084                span: Span::new(op_start, self.pos()),
1085                kind,
1086            },
1087            greedy,
1088            ast: Box::new(ast),
1089        }));
1090        Ok(concat)
1091    }
1092
1093    /// Parses a counted repetition operation. A counted repetition operator
1094    /// corresponds to the {m,n} syntax, and does not include the ?, * or +
1095    /// operators.
1096    ///
1097    /// This assumes that the parser is currently positioned at the opening `{`
1098    /// and advances the parser to the first character after the operator.
1099    /// (Note that the operator may include a single additional `?`, which
1100    /// makes the operator ungreedy.)
1101    ///
1102    /// The caller should include the concatenation that is being built. The
1103    /// concatenation returned includes the repetition operator applied to the
1104    /// last expression in the given concatenation.
1105    #[inline(never)]
1106    fn parse_counted_repetition(
1107        &self,
1108        mut concat: ast::Concat,
1109    ) -> Result<ast::Concat> {
1110        assert!(self.char() == '{');
1111        let start = self.pos();
1112        let ast = match concat.asts.pop() {
1113            Some(ast) => ast,
1114            None => {
1115                return Err(
1116                    self.error(self.span(), ast::ErrorKind::RepetitionMissing)
1117                )
1118            }
1119        };
1120        match ast {
1121            Ast::Empty(_) | Ast::Flags(_) => {
1122                return Err(
1123                    self.error(self.span(), ast::ErrorKind::RepetitionMissing)
1124                )
1125            }
1126            _ => {}
1127        }
1128        if !self.bump_and_bump_space() {
1129            return Err(self.error(
1130                Span::new(start, self.pos()),
1131                ast::ErrorKind::RepetitionCountUnclosed,
1132            ));
1133        }
1134        let count_start = specialize_err(
1135            self.parse_decimal(),
1136            ast::ErrorKind::DecimalEmpty,
1137            ast::ErrorKind::RepetitionCountDecimalEmpty,
1138        );
1139        if self.is_eof() {
1140            return Err(self.error(
1141                Span::new(start, self.pos()),
1142                ast::ErrorKind::RepetitionCountUnclosed,
1143            ));
1144        }
1145        let range = if self.char() == ',' {
1146            if !self.bump_and_bump_space() {
1147                return Err(self.error(
1148                    Span::new(start, self.pos()),
1149                    ast::ErrorKind::RepetitionCountUnclosed,
1150                ));
1151            }
1152            if self.char() != '}' {
1153                let count_start = match count_start {
1154                    Ok(c) => c,
1155                    Err(err)
1156                        if err.kind
1157                            == ast::ErrorKind::RepetitionCountDecimalEmpty =>
1158                    {
1159                        if self.parser().empty_min_range {
1160                            0
1161                        } else {
1162                            return Err(err);
1163                        }
1164                    }
1165                    err => err?,
1166                };
1167                let count_end = specialize_err(
1168                    self.parse_decimal(),
1169                    ast::ErrorKind::DecimalEmpty,
1170                    ast::ErrorKind::RepetitionCountDecimalEmpty,
1171                )?;
1172                ast::RepetitionRange::Bounded(count_start, count_end)
1173            } else {
1174                ast::RepetitionRange::AtLeast(count_start?)
1175            }
1176        } else {
1177            ast::RepetitionRange::Exactly(count_start?)
1178        };
1179
1180        if self.is_eof() || self.char() != '}' {
1181            return Err(self.error(
1182                Span::new(start, self.pos()),
1183                ast::ErrorKind::RepetitionCountUnclosed,
1184            ));
1185        }
1186
1187        let mut greedy = true;
1188        if self.bump_and_bump_space() && self.char() == '?' {
1189            greedy = false;
1190            self.bump();
1191        }
1192
1193        let op_span = Span::new(start, self.pos());
1194        if !range.is_valid() {
1195            return Err(
1196                self.error(op_span, ast::ErrorKind::RepetitionCountInvalid)
1197            );
1198        }
1199        concat.asts.push(Ast::repetition(ast::Repetition {
1200            span: ast.span().with_end(self.pos()),
1201            op: ast::RepetitionOp {
1202                span: op_span,
1203                kind: ast::RepetitionKind::Range(range),
1204            },
1205            greedy,
1206            ast: Box::new(ast),
1207        }));
1208        Ok(concat)
1209    }
1210
1211    /// Parse a group (which contains a sub-expression) or a set of flags.
1212    ///
1213    /// If a group was found, then it is returned with an empty AST. If a set
1214    /// of flags is found, then that set is returned.
1215    ///
1216    /// The parser should be positioned at the opening parenthesis.
1217    ///
1218    /// This advances the parser to the character before the start of the
1219    /// sub-expression (in the case of a group) or to the closing parenthesis
1220    /// immediately following the set of flags.
1221    ///
1222    /// # Errors
1223    ///
1224    /// If flags are given and incorrectly specified, then a corresponding
1225    /// error is returned.
1226    ///
1227    /// If a capture name is given and it is incorrectly specified, then a
1228    /// corresponding error is returned.
1229    #[inline(never)]
1230    fn parse_group(&self) -> Result<Either<ast::SetFlags, ast::Group>> {
1231        assert_eq!(self.char(), '(');
1232        let open_span = self.span_char();
1233        self.bump();
1234        self.bump_space();
1235        if self.is_lookaround_prefix() {
1236            return Err(self.error(
1237                Span::new(open_span.start, self.span().end),
1238                ast::ErrorKind::UnsupportedLookAround,
1239            ));
1240        }
1241        let inner_span = self.span();
1242        let mut starts_with_p = true;
1243        if self.bump_if("?P<") || {
1244            starts_with_p = false;
1245            self.bump_if("?<")
1246        } {
1247            let capture_index = self.next_capture_index(open_span)?;
1248            let name = self.parse_capture_name(capture_index)?;
1249            Ok(Either::Right(ast::Group {
1250                span: open_span,
1251                kind: ast::GroupKind::CaptureName { starts_with_p, name },
1252                ast: Box::new(Ast::empty(self.span())),
1253            }))
1254        } else if self.bump_if("?") {
1255            if self.is_eof() {
1256                return Err(
1257                    self.error(open_span, ast::ErrorKind::GroupUnclosed)
1258                );
1259            }
1260            let flags = self.parse_flags()?;
1261            let char_end = self.char();
1262            self.bump();
1263            if char_end == ')' {
1264                // We don't allow empty flags, e.g., `(?)`. We instead
1265                // interpret it as a repetition operator missing its argument.
1266                if flags.items.is_empty() {
1267                    return Err(self.error(
1268                        inner_span,
1269                        ast::ErrorKind::RepetitionMissing,
1270                    ));
1271                }
1272                Ok(Either::Left(ast::SetFlags {
1273                    span: Span { end: self.pos(), ..open_span },
1274                    flags,
1275                }))
1276            } else {
1277                assert_eq!(char_end, ':');
1278                Ok(Either::Right(ast::Group {
1279                    span: open_span,
1280                    kind: ast::GroupKind::NonCapturing(flags),
1281                    ast: Box::new(Ast::empty(self.span())),
1282                }))
1283            }
1284        } else {
1285            let capture_index = self.next_capture_index(open_span)?;
1286            Ok(Either::Right(ast::Group {
1287                span: open_span,
1288                kind: ast::GroupKind::CaptureIndex(capture_index),
1289                ast: Box::new(Ast::empty(self.span())),
1290            }))
1291        }
1292    }
1293
1294    /// Parses a capture group name. Assumes that the parser is positioned at
1295    /// the first character in the name following the opening `<` (and may
1296    /// possibly be EOF). This advances the parser to the first character
1297    /// following the closing `>`.
1298    ///
1299    /// The caller must provide the capture index of the group for this name.
1300    #[inline(never)]
1301    fn parse_capture_name(
1302        &self,
1303        capture_index: u32,
1304    ) -> Result<ast::CaptureName> {
1305        if self.is_eof() {
1306            return Err(self
1307                .error(self.span(), ast::ErrorKind::GroupNameUnexpectedEof));
1308        }
1309        let start = self.pos();
1310        loop {
1311            if self.char() == '>' {
1312                break;
1313            }
1314            if !is_capture_char(self.char(), self.pos() == start) {
1315                return Err(self.error(
1316                    self.span_char(),
1317                    ast::ErrorKind::GroupNameInvalid,
1318                ));
1319            }
1320            if !self.bump() {
1321                break;
1322            }
1323        }
1324        let end = self.pos();
1325        if self.is_eof() {
1326            return Err(self
1327                .error(self.span(), ast::ErrorKind::GroupNameUnexpectedEof));
1328        }
1329        assert_eq!(self.char(), '>');
1330        self.bump();
1331        let name = &self.pattern()[start.offset..end.offset];
1332        if name.is_empty() {
1333            return Err(self.error(
1334                Span::new(start, start),
1335                ast::ErrorKind::GroupNameEmpty,
1336            ));
1337        }
1338        let capname = ast::CaptureName {
1339            span: Span::new(start, end),
1340            name: name.to_string(),
1341            index: capture_index,
1342        };
1343        self.add_capture_name(&capname)?;
1344        Ok(capname)
1345    }
1346
1347    /// Parse a sequence of flags starting at the current character.
1348    ///
1349    /// This advances the parser to the character immediately following the
1350    /// flags, which is guaranteed to be either `:` or `)`.
1351    ///
1352    /// # Errors
1353    ///
1354    /// If any flags are duplicated, then an error is returned.
1355    ///
1356    /// If the negation operator is used more than once, then an error is
1357    /// returned.
1358    ///
1359    /// If no flags could be found or if the negation operation is not followed
1360    /// by any flags, then an error is returned.
1361    #[inline(never)]
1362    fn parse_flags(&self) -> Result<ast::Flags> {
1363        let mut flags = ast::Flags { span: self.span(), items: vec![] };
1364        let mut last_was_negation = None;
1365        while self.char() != ':' && self.char() != ')' {
1366            if self.char() == '-' {
1367                last_was_negation = Some(self.span_char());
1368                let item = ast::FlagsItem {
1369                    span: self.span_char(),
1370                    kind: ast::FlagsItemKind::Negation,
1371                };
1372                if let Some(i) = flags.add_item(item) {
1373                    return Err(self.error(
1374                        self.span_char(),
1375                        ast::ErrorKind::FlagRepeatedNegation {
1376                            original: flags.items[i].span,
1377                        },
1378                    ));
1379                }
1380            } else {
1381                last_was_negation = None;
1382                let item = ast::FlagsItem {
1383                    span: self.span_char(),
1384                    kind: ast::FlagsItemKind::Flag(self.parse_flag()?),
1385                };
1386                if let Some(i) = flags.add_item(item) {
1387                    return Err(self.error(
1388                        self.span_char(),
1389                        ast::ErrorKind::FlagDuplicate {
1390                            original: flags.items[i].span,
1391                        },
1392                    ));
1393                }
1394            }
1395            if !self.bump() {
1396                return Err(
1397                    self.error(self.span(), ast::ErrorKind::FlagUnexpectedEof)
1398                );
1399            }
1400        }
1401        if let Some(span) = last_was_negation {
1402            return Err(self.error(span, ast::ErrorKind::FlagDanglingNegation));
1403        }
1404        flags.span.end = self.pos();
1405        Ok(flags)
1406    }
1407
1408    /// Parse the current character as a flag. Do not advance the parser.
1409    ///
1410    /// # Errors
1411    ///
1412    /// If the flag is not recognized, then an error is returned.
1413    #[inline(never)]
1414    fn parse_flag(&self) -> Result<ast::Flag> {
1415        match self.char() {
1416            'i' => Ok(ast::Flag::CaseInsensitive),
1417            'm' => Ok(ast::Flag::MultiLine),
1418            's' => Ok(ast::Flag::DotMatchesNewLine),
1419            'U' => Ok(ast::Flag::SwapGreed),
1420            'u' => Ok(ast::Flag::Unicode),
1421            'R' => Ok(ast::Flag::CRLF),
1422            'x' => Ok(ast::Flag::IgnoreWhitespace),
1423            _ => {
1424                Err(self
1425                    .error(self.span_char(), ast::ErrorKind::FlagUnrecognized))
1426            }
1427        }
1428    }
1429
1430    /// Parse a primitive AST. e.g., A literal, non-set character class or
1431    /// assertion.
1432    ///
1433    /// This assumes that the parser expects a primitive at the current
1434    /// location. i.e., All other non-primitive cases have been handled.
1435    /// For example, if the parser's position is at `|`, then `|` will be
1436    /// treated as a literal (e.g., inside a character class).
1437    ///
1438    /// This advances the parser to the first character immediately following
1439    /// the primitive.
1440    fn parse_primitive(&self) -> Result<Primitive> {
1441        match self.char() {
1442            '\\' => self.parse_escape(),
1443            '.' => {
1444                let ast = Primitive::Dot(self.span_char());
1445                self.bump();
1446                Ok(ast)
1447            }
1448            '^' => {
1449                let ast = Primitive::Assertion(ast::Assertion {
1450                    span: self.span_char(),
1451                    kind: ast::AssertionKind::StartLine,
1452                });
1453                self.bump();
1454                Ok(ast)
1455            }
1456            '$' => {
1457                let ast = Primitive::Assertion(ast::Assertion {
1458                    span: self.span_char(),
1459                    kind: ast::AssertionKind::EndLine,
1460                });
1461                self.bump();
1462                Ok(ast)
1463            }
1464            c => {
1465                let ast = Primitive::Literal(ast::Literal {
1466                    span: self.span_char(),
1467                    kind: ast::LiteralKind::Verbatim,
1468                    c,
1469                });
1470                self.bump();
1471                Ok(ast)
1472            }
1473        }
1474    }
1475
1476    /// Parse an escape sequence as a primitive AST.
1477    ///
1478    /// This assumes the parser is positioned at the start of the escape
1479    /// sequence, i.e., `\`. It advances the parser to the first position
1480    /// immediately following the escape sequence.
1481    #[inline(never)]
1482    fn parse_escape(&self) -> Result<Primitive> {
1483        assert_eq!(self.char(), '\\');
1484        let start = self.pos();
1485        if !self.bump() {
1486            return Err(self.error(
1487                Span::new(start, self.pos()),
1488                ast::ErrorKind::EscapeUnexpectedEof,
1489            ));
1490        }
1491        let c = self.char();
1492        // Put some of the more complicated routines into helpers.
1493        match c {
1494            '0'..='7' => {
1495                if !self.parser().octal {
1496                    return Err(self.error(
1497                        Span::new(start, self.span_char().end),
1498                        ast::ErrorKind::UnsupportedBackreference,
1499                    ));
1500                }
1501                let mut lit = self.parse_octal();
1502                lit.span.start = start;
1503                return Ok(Primitive::Literal(lit));
1504            }
1505            '8'..='9' if !self.parser().octal => {
1506                return Err(self.error(
1507                    Span::new(start, self.span_char().end),
1508                    ast::ErrorKind::UnsupportedBackreference,
1509                ));
1510            }
1511            'x' | 'u' | 'U' => {
1512                let mut lit = self.parse_hex()?;
1513                lit.span.start = start;
1514                return Ok(Primitive::Literal(lit));
1515            }
1516            'p' | 'P' => {
1517                let mut cls = self.parse_unicode_class()?;
1518                cls.span.start = start;
1519                return Ok(Primitive::Unicode(cls));
1520            }
1521            'd' | 's' | 'w' | 'D' | 'S' | 'W' => {
1522                let mut cls = self.parse_perl_class();
1523                cls.span.start = start;
1524                return Ok(Primitive::Perl(cls));
1525            }
1526            _ => {}
1527        }
1528
1529        // Handle all of the one letter sequences inline.
1530        self.bump();
1531        let span = Span::new(start, self.pos());
1532        if is_meta_character(c) {
1533            return Ok(Primitive::Literal(ast::Literal {
1534                span,
1535                kind: ast::LiteralKind::Meta,
1536                c,
1537            }));
1538        }
1539        if is_escapeable_character(c) {
1540            return Ok(Primitive::Literal(ast::Literal {
1541                span,
1542                kind: ast::LiteralKind::Superfluous,
1543                c,
1544            }));
1545        }
1546        let special = |kind, c| {
1547            Ok(Primitive::Literal(ast::Literal {
1548                span,
1549                kind: ast::LiteralKind::Special(kind),
1550                c,
1551            }))
1552        };
1553        match c {
1554            'a' => special(ast::SpecialLiteralKind::Bell, '\x07'),
1555            'f' => special(ast::SpecialLiteralKind::FormFeed, '\x0C'),
1556            't' => special(ast::SpecialLiteralKind::Tab, '\t'),
1557            'n' => special(ast::SpecialLiteralKind::LineFeed, '\n'),
1558            'r' => special(ast::SpecialLiteralKind::CarriageReturn, '\r'),
1559            'v' => special(ast::SpecialLiteralKind::VerticalTab, '\x0B'),
1560            'A' => Ok(Primitive::Assertion(ast::Assertion {
1561                span,
1562                kind: ast::AssertionKind::StartText,
1563            })),
1564            'z' => Ok(Primitive::Assertion(ast::Assertion {
1565                span,
1566                kind: ast::AssertionKind::EndText,
1567            })),
1568            'b' => {
1569                let mut wb = ast::Assertion {
1570                    span,
1571                    kind: ast::AssertionKind::WordBoundary,
1572                };
1573                // After a \b, we "try" to parse things like \b{start} for
1574                // special word boundary assertions.
1575                if !self.is_eof() && self.char() == '{' {
1576                    if let Some(kind) =
1577                        self.maybe_parse_special_word_boundary(start)?
1578                    {
1579                        wb.kind = kind;
1580                        wb.span.end = self.pos();
1581                    }
1582                }
1583                Ok(Primitive::Assertion(wb))
1584            }
1585            'B' => Ok(Primitive::Assertion(ast::Assertion {
1586                span,
1587                kind: ast::AssertionKind::NotWordBoundary,
1588            })),
1589            '<' => Ok(Primitive::Assertion(ast::Assertion {
1590                span,
1591                kind: ast::AssertionKind::WordBoundaryStartAngle,
1592            })),
1593            '>' => Ok(Primitive::Assertion(ast::Assertion {
1594                span,
1595                kind: ast::AssertionKind::WordBoundaryEndAngle,
1596            })),
1597            _ => Err(self.error(span, ast::ErrorKind::EscapeUnrecognized)),
1598        }
1599    }
1600
1601    /// Attempt to parse a specialty word boundary. That is, `\b{start}`,
1602    /// `\b{end}`, `\b{start-half}` or `\b{end-half}`.
1603    ///
1604    /// This is similar to `maybe_parse_ascii_class` in that, in most cases,
1605    /// if it fails it will just return `None` with no error. This is done
1606    /// because `\b{5}` is a valid expression and we want to let that be parsed
1607    /// by the existing counted repetition parsing code. (I thought about just
1608    /// invoking the counted repetition code from here, but it seemed a little
1609    /// ham-fisted.)
1610    ///
1611    /// Unlike `maybe_parse_ascii_class` though, this can return an error.
1612    /// Namely, if we definitely know it isn't a counted repetition, then we
1613    /// return an error specific to the specialty word boundaries.
1614    ///
1615    /// This assumes the parser is positioned at a `{` immediately following
1616    /// a `\b`. When `None` is returned, the parser is returned to the position
1617    /// at which it started: pointing at a `{`.
1618    ///
1619    /// The position given should correspond to the start of the `\b`.
1620    fn maybe_parse_special_word_boundary(
1621        &self,
1622        wb_start: Position,
1623    ) -> Result<Option<ast::AssertionKind>> {
1624        assert_eq!(self.char(), '{');
1625
1626        let is_valid_char = |c| match c {
1627            'A'..='Z' | 'a'..='z' | '-' => true,
1628            _ => false,
1629        };
1630        let start = self.pos();
1631        if !self.bump_and_bump_space() {
1632            return Err(self.error(
1633                Span::new(wb_start, self.pos()),
1634                ast::ErrorKind::SpecialWordOrRepetitionUnexpectedEof,
1635            ));
1636        }
1637        let start_contents = self.pos();
1638        // This is one of the critical bits: if the first non-whitespace
1639        // character isn't in [-A-Za-z] (i.e., this can't be a special word
1640        // boundary), then we bail and let the counted repetition parser deal
1641        // with this.
1642        if !is_valid_char(self.char()) {
1643            self.parser().pos.set(start);
1644            return Ok(None);
1645        }
1646
1647        // Now collect up our chars until we see a '}'.
1648        let mut scratch = self.parser().scratch.borrow_mut();
1649        scratch.clear();
1650        while !self.is_eof() && is_valid_char(self.char()) {
1651            scratch.push(self.char());
1652            self.bump_and_bump_space();
1653        }
1654        if self.is_eof() || self.char() != '}' {
1655            return Err(self.error(
1656                Span::new(start, self.pos()),
1657                ast::ErrorKind::SpecialWordBoundaryUnclosed,
1658            ));
1659        }
1660        let end = self.pos();
1661        self.bump();
1662        let kind = match scratch.as_str() {
1663            "start" => ast::AssertionKind::WordBoundaryStart,
1664            "end" => ast::AssertionKind::WordBoundaryEnd,
1665            "start-half" => ast::AssertionKind::WordBoundaryStartHalf,
1666            "end-half" => ast::AssertionKind::WordBoundaryEndHalf,
1667            _ => {
1668                return Err(self.error(
1669                    Span::new(start_contents, end),
1670                    ast::ErrorKind::SpecialWordBoundaryUnrecognized,
1671                ))
1672            }
1673        };
1674        Ok(Some(kind))
1675    }
1676
1677    /// Parse an octal representation of a Unicode codepoint up to 3 digits
1678    /// long. This expects the parser to be positioned at the first octal
1679    /// digit and advances the parser to the first character immediately
1680    /// following the octal number. This also assumes that parsing octal
1681    /// escapes is enabled.
1682    ///
1683    /// Assuming the preconditions are met, this routine can never fail.
1684    #[inline(never)]
1685    fn parse_octal(&self) -> ast::Literal {
1686        assert!(self.parser().octal);
1687        assert!('0' <= self.char() && self.char() <= '7');
1688        let start = self.pos();
1689        // Parse up to two more digits.
1690        while self.bump()
1691            && '0' <= self.char()
1692            && self.char() <= '7'
1693            && self.pos().offset - start.offset <= 2
1694        {}
1695        let end = self.pos();
1696        let octal = &self.pattern()[start.offset..end.offset];
1697        // Parsing the octal should never fail since the above guarantees a
1698        // valid number.
1699        let codepoint =
1700            u32::from_str_radix(octal, 8).expect("valid octal number");
1701        // The max value for 3 digit octal is 0777 = 511 and [0, 511] has no
1702        // invalid Unicode scalar values.
1703        let c = char::from_u32(codepoint).expect("Unicode scalar value");
1704        ast::Literal {
1705            span: Span::new(start, end),
1706            kind: ast::LiteralKind::Octal,
1707            c,
1708        }
1709    }
1710
1711    /// Parse a hex representation of a Unicode codepoint. This handles both
1712    /// hex notations, i.e., `\xFF` and `\x{FFFF}`. This expects the parser to
1713    /// be positioned at the `x`, `u` or `U` prefix. The parser is advanced to
1714    /// the first character immediately following the hexadecimal literal.
1715    #[inline(never)]
1716    fn parse_hex(&self) -> Result<ast::Literal> {
1717        assert!(
1718            self.char() == 'x' || self.char() == 'u' || self.char() == 'U'
1719        );
1720
1721        let hex_kind = match self.char() {
1722            'x' => ast::HexLiteralKind::X,
1723            'u' => ast::HexLiteralKind::UnicodeShort,
1724            _ => ast::HexLiteralKind::UnicodeLong,
1725        };
1726        if !self.bump_and_bump_space() {
1727            return Err(
1728                self.error(self.span(), ast::ErrorKind::EscapeUnexpectedEof)
1729            );
1730        }
1731        if self.char() == '{' {
1732            self.parse_hex_brace(hex_kind)
1733        } else {
1734            self.parse_hex_digits(hex_kind)
1735        }
1736    }
1737
1738    /// Parse an N-digit hex representation of a Unicode codepoint. This
1739    /// expects the parser to be positioned at the first digit and will advance
1740    /// the parser to the first character immediately following the escape
1741    /// sequence.
1742    ///
1743    /// The number of digits given must be 2 (for `\xNN`), 4 (for `\uNNNN`)
1744    /// or 8 (for `\UNNNNNNNN`).
1745    #[inline(never)]
1746    fn parse_hex_digits(
1747        &self,
1748        kind: ast::HexLiteralKind,
1749    ) -> Result<ast::Literal> {
1750        let mut scratch = self.parser().scratch.borrow_mut();
1751        scratch.clear();
1752
1753        let start = self.pos();
1754        for i in 0..kind.digits() {
1755            if i > 0 && !self.bump_and_bump_space() {
1756                return Err(self
1757                    .error(self.span(), ast::ErrorKind::EscapeUnexpectedEof));
1758            }
1759            if !is_hex(self.char()) {
1760                return Err(self.error(
1761                    self.span_char(),
1762                    ast::ErrorKind::EscapeHexInvalidDigit,
1763                ));
1764            }
1765            scratch.push(self.char());
1766        }
1767        // The final bump just moves the parser past the literal, which may
1768        // be EOF.
1769        self.bump_and_bump_space();
1770        let end = self.pos();
1771        let hex = scratch.as_str();
1772        match u32::from_str_radix(hex, 16).ok().and_then(char::from_u32) {
1773            None => Err(self.error(
1774                Span::new(start, end),
1775                ast::ErrorKind::EscapeHexInvalid,
1776            )),
1777            Some(c) => Ok(ast::Literal {
1778                span: Span::new(start, end),
1779                kind: ast::LiteralKind::HexFixed(kind),
1780                c,
1781            }),
1782        }
1783    }
1784
1785    /// Parse a hex representation of any Unicode scalar value. This expects
1786    /// the parser to be positioned at the opening brace `{` and will advance
1787    /// the parser to the first character following the closing brace `}`.
1788    #[inline(never)]
1789    fn parse_hex_brace(
1790        &self,
1791        kind: ast::HexLiteralKind,
1792    ) -> Result<ast::Literal> {
1793        let mut scratch = self.parser().scratch.borrow_mut();
1794        scratch.clear();
1795
1796        let brace_pos = self.pos();
1797        let start = self.span_char().end;
1798        while self.bump_and_bump_space() && self.char() != '}' {
1799            if !is_hex(self.char()) {
1800                return Err(self.error(
1801                    self.span_char(),
1802                    ast::ErrorKind::EscapeHexInvalidDigit,
1803                ));
1804            }
1805            scratch.push(self.char());
1806        }
1807        if self.is_eof() {
1808            return Err(self.error(
1809                Span::new(brace_pos, self.pos()),
1810                ast::ErrorKind::EscapeUnexpectedEof,
1811            ));
1812        }
1813        let end = self.pos();
1814        let hex = scratch.as_str();
1815        assert_eq!(self.char(), '}');
1816        self.bump_and_bump_space();
1817
1818        if hex.is_empty() {
1819            return Err(self.error(
1820                Span::new(brace_pos, self.pos()),
1821                ast::ErrorKind::EscapeHexEmpty,
1822            ));
1823        }
1824        match u32::from_str_radix(hex, 16).ok().and_then(char::from_u32) {
1825            None => Err(self.error(
1826                Span::new(start, end),
1827                ast::ErrorKind::EscapeHexInvalid,
1828            )),
1829            Some(c) => Ok(ast::Literal {
1830                span: Span::new(start, self.pos()),
1831                kind: ast::LiteralKind::HexBrace(kind),
1832                c,
1833            }),
1834        }
1835    }
1836
1837    /// Parse a decimal number into a u32 while trimming leading and trailing
1838    /// whitespace.
1839    ///
1840    /// This expects the parser to be positioned at the first position where
1841    /// a decimal digit could occur. This will advance the parser to the byte
1842    /// immediately following the last contiguous decimal digit.
1843    ///
1844    /// If no decimal digit could be found or if there was a problem parsing
1845    /// the complete set of digits into a u32, then an error is returned.
1846    fn parse_decimal(&self) -> Result<u32> {
1847        let mut scratch = self.parser().scratch.borrow_mut();
1848        scratch.clear();
1849
1850        while !self.is_eof() && self.char().is_whitespace() {
1851            self.bump();
1852        }
1853        let start = self.pos();
1854        while !self.is_eof() && '0' <= self.char() && self.char() <= '9' {
1855            scratch.push(self.char());
1856            self.bump_and_bump_space();
1857        }
1858        let span = Span::new(start, self.pos());
1859        while !self.is_eof() && self.char().is_whitespace() {
1860            self.bump_and_bump_space();
1861        }
1862        let digits = scratch.as_str();
1863        if digits.is_empty() {
1864            return Err(self.error(span, ast::ErrorKind::DecimalEmpty));
1865        }
1866        match u32::from_str_radix(digits, 10).ok() {
1867            Some(n) => Ok(n),
1868            None => Err(self.error(span, ast::ErrorKind::DecimalInvalid)),
1869        }
1870    }
1871
1872    /// Parse a standard character class consisting primarily of characters or
1873    /// character ranges, but can also contain nested character classes of
1874    /// any type (sans `.`).
1875    ///
1876    /// This assumes the parser is positioned at the opening `[`. If parsing
1877    /// is successful, then the parser is advanced to the position immediately
1878    /// following the closing `]`.
1879    #[inline(never)]
1880    fn parse_set_class(&self) -> Result<ast::ClassBracketed> {
1881        assert_eq!(self.char(), '[');
1882
1883        let mut union =
1884            ast::ClassSetUnion { span: self.span(), items: vec![] };
1885        loop {
1886            self.bump_space();
1887            if self.is_eof() {
1888                return Err(self.unclosed_class_error());
1889            }
1890            match self.char() {
1891                '[' => {
1892                    // If we've already parsed the opening bracket, then
1893                    // attempt to treat this as the beginning of an ASCII
1894                    // class. If ASCII class parsing fails, then the parser
1895                    // backs up to `[`.
1896                    if !self.parser().stack_class.borrow().is_empty() {
1897                        if let Some(cls) = self.maybe_parse_ascii_class() {
1898                            union.push(ast::ClassSetItem::Ascii(cls));
1899                            continue;
1900                        }
1901                    }
1902                    union = self.push_class_open(union)?;
1903                }
1904                ']' => match self.pop_class(union)? {
1905                    Either::Left(nested_union) => {
1906                        union = nested_union;
1907                    }
1908                    Either::Right(class) => return Ok(class),
1909                },
1910                '&' if self.peek() == Some('&') => {
1911                    assert!(self.bump_if("&&"));
1912                    union = self.push_class_op(
1913                        ast::ClassSetBinaryOpKind::Intersection,
1914                        union,
1915                    );
1916                }
1917                '-' if self.peek() == Some('-') => {
1918                    assert!(self.bump_if("--"));
1919                    union = self.push_class_op(
1920                        ast::ClassSetBinaryOpKind::Difference,
1921                        union,
1922                    );
1923                }
1924                '~' if self.peek() == Some('~') => {
1925                    assert!(self.bump_if("~~"));
1926                    union = self.push_class_op(
1927                        ast::ClassSetBinaryOpKind::SymmetricDifference,
1928                        union,
1929                    );
1930                }
1931                _ => {
1932                    union.push(self.parse_set_class_range()?);
1933                }
1934            }
1935        }
1936    }
1937
1938    /// Parse a single primitive item in a character class set. The item to
1939    /// be parsed can either be one of a simple literal character, a range
1940    /// between two simple literal characters or a "primitive" character
1941    /// class like \w or \p{Greek}.
1942    ///
1943    /// If an invalid escape is found, or if a character class is found where
1944    /// a simple literal is expected (e.g., in a range), then an error is
1945    /// returned.
1946    #[inline(never)]
1947    fn parse_set_class_range(&self) -> Result<ast::ClassSetItem> {
1948        let prim1 = self.parse_set_class_item()?;
1949        self.bump_space();
1950        if self.is_eof() {
1951            return Err(self.unclosed_class_error());
1952        }
1953        // If the next char isn't a `-`, then we don't have a range.
1954        // There are two exceptions. If the char after a `-` is a `]`, then
1955        // `-` is interpreted as a literal `-`. Alternatively, if the char
1956        // after a `-` is a `-`, then `--` corresponds to a "difference"
1957        // operation.
1958        if self.char() != '-'
1959            || self.peek_space() == Some(']')
1960            || self.peek_space() == Some('-')
1961        {
1962            return prim1.into_class_set_item(self);
1963        }
1964        // OK, now we're parsing a range, so bump past the `-` and parse the
1965        // second half of the range.
1966        if !self.bump_and_bump_space() {
1967            return Err(self.unclosed_class_error());
1968        }
1969        let prim2 = self.parse_set_class_item()?;
1970        let range = ast::ClassSetRange {
1971            span: Span::new(prim1.span().start, prim2.span().end),
1972            start: prim1.into_class_literal(self)?,
1973            end: prim2.into_class_literal(self)?,
1974        };
1975        if !range.is_valid() {
1976            return Err(
1977                self.error(range.span, ast::ErrorKind::ClassRangeInvalid)
1978            );
1979        }
1980        Ok(ast::ClassSetItem::Range(range))
1981    }
1982
1983    /// Parse a single item in a character class as a primitive, where the
1984    /// primitive either consists of a verbatim literal or a single escape
1985    /// sequence.
1986    ///
1987    /// This assumes the parser is positioned at the beginning of a primitive,
1988    /// and advances the parser to the first position after the primitive if
1989    /// successful.
1990    ///
1991    /// Note that it is the caller's responsibility to report an error if an
1992    /// illegal primitive was parsed.
1993    #[inline(never)]
1994    fn parse_set_class_item(&self) -> Result<Primitive> {
1995        if self.char() == '\\' {
1996            self.parse_escape()
1997        } else {
1998            let x = Primitive::Literal(ast::Literal {
1999                span: self.span_char(),
2000                kind: ast::LiteralKind::Verbatim,
2001                c: self.char(),
2002            });
2003            self.bump();
2004            Ok(x)
2005        }
2006    }
2007
2008    /// Parses the opening of a character class set. This includes the opening
2009    /// bracket along with `^` if present to indicate negation. This also
2010    /// starts parsing the opening set of unioned items if applicable, since
2011    /// there are special rules applied to certain characters in the opening
2012    /// of a character class. For example, `[^]]` is the class of all
2013    /// characters not equal to `]`. (`]` would need to be escaped in any other
2014    /// position.) Similarly for `-`.
2015    ///
2016    /// In all cases, the op inside the returned `ast::ClassBracketed` is an
2017    /// empty union. This empty union should be replaced with the actual item
2018    /// when it is popped from the parser's stack.
2019    ///
2020    /// This assumes the parser is positioned at the opening `[` and advances
2021    /// the parser to the first non-special byte of the character class.
2022    ///
2023    /// An error is returned if EOF is found.
2024    #[inline(never)]
2025    fn parse_set_class_open(
2026        &self,
2027    ) -> Result<(ast::ClassBracketed, ast::ClassSetUnion)> {
2028        assert_eq!(self.char(), '[');
2029        let start = self.pos();
2030        if !self.bump_and_bump_space() {
2031            return Err(self.error(
2032                Span::new(start, self.pos()),
2033                ast::ErrorKind::ClassUnclosed,
2034            ));
2035        }
2036
2037        let negated = if self.char() != '^' {
2038            false
2039        } else {
2040            if !self.bump_and_bump_space() {
2041                return Err(self.error(
2042                    Span::new(start, self.pos()),
2043                    ast::ErrorKind::ClassUnclosed,
2044                ));
2045            }
2046            true
2047        };
2048        // Accept any number of `-` as literal `-`.
2049        let mut union =
2050            ast::ClassSetUnion { span: self.span(), items: vec![] };
2051        while self.char() == '-' {
2052            union.push(ast::ClassSetItem::Literal(ast::Literal {
2053                span: self.span_char(),
2054                kind: ast::LiteralKind::Verbatim,
2055                c: '-',
2056            }));
2057            if !self.bump_and_bump_space() {
2058                return Err(self.error(
2059                    Span::new(start, start),
2060                    ast::ErrorKind::ClassUnclosed,
2061                ));
2062            }
2063        }
2064        // If `]` is the *first* char in a set, then interpret it as a literal
2065        // `]`. That is, an empty class is impossible to write.
2066        if union.items.is_empty() && self.char() == ']' {
2067            union.push(ast::ClassSetItem::Literal(ast::Literal {
2068                span: self.span_char(),
2069                kind: ast::LiteralKind::Verbatim,
2070                c: ']',
2071            }));
2072            if !self.bump_and_bump_space() {
2073                return Err(self.error(
2074                    Span::new(start, self.pos()),
2075                    ast::ErrorKind::ClassUnclosed,
2076                ));
2077            }
2078        }
2079        let set = ast::ClassBracketed {
2080            span: Span::new(start, self.pos()),
2081            negated,
2082            kind: ast::ClassSet::union(ast::ClassSetUnion {
2083                span: Span::new(union.span.start, union.span.start),
2084                items: vec![],
2085            }),
2086        };
2087        Ok((set, union))
2088    }
2089
2090    /// Attempt to parse an ASCII character class, e.g., `[:alnum:]`.
2091    ///
2092    /// This assumes the parser is positioned at the opening `[`.
2093    ///
2094    /// If no valid ASCII character class could be found, then this does not
2095    /// advance the parser and `None` is returned. Otherwise, the parser is
2096    /// advanced to the first byte following the closing `]` and the
2097    /// corresponding ASCII class is returned.
2098    #[inline(never)]
2099    fn maybe_parse_ascii_class(&self) -> Option<ast::ClassAscii> {
2100        // ASCII character classes are interesting from a parsing perspective
2101        // because parsing cannot fail with any interesting error. For example,
2102        // in order to use an ASCII character class, it must be enclosed in
2103        // double brackets, e.g., `[[:alnum:]]`. Alternatively, you might think
2104        // of it as "ASCII character classes have the syntax `[:NAME:]` which
2105        // can only appear within character brackets." This means that things
2106        // like `[[:lower:]A]` are legal constructs.
2107        //
2108        // However, if one types an incorrect ASCII character class, e.g.,
2109        // `[[:loower:]]`, then we treat that as a normal nested character
2110        // class containing the characters `:elorw`. One might argue that we
2111        // should return an error instead since the repeated colons give away
2112        // the intent to write an ASCII class. But what if the user typed
2113        // `[[:lower]]` instead? How can we tell that was intended to be an
2114        // ASCII class and not just a normal nested class?
2115        //
2116        // Reasonable people can probably disagree over this, but for better
2117        // or worse, we implement semantics that never fails at the expense
2118        // of better failure modes.
2119        assert_eq!(self.char(), '[');
2120        // If parsing fails, then we back up the parser to this starting point.
2121        let start = self.pos();
2122        let mut negated = false;
2123        if !self.bump() || self.char() != ':' {
2124            self.parser().pos.set(start);
2125            return None;
2126        }
2127        if !self.bump() {
2128            self.parser().pos.set(start);
2129            return None;
2130        }
2131        if self.char() == '^' {
2132            negated = true;
2133            if !self.bump() {
2134                self.parser().pos.set(start);
2135                return None;
2136            }
2137        }
2138        let name_start = self.offset();
2139        while self.char() != ':' && self.bump() {}
2140        if self.is_eof() {
2141            self.parser().pos.set(start);
2142            return None;
2143        }
2144        let name = &self.pattern()[name_start..self.offset()];
2145        if !self.bump_if(":]") {
2146            self.parser().pos.set(start);
2147            return None;
2148        }
2149        let kind = match ast::ClassAsciiKind::from_name(name) {
2150            Some(kind) => kind,
2151            None => {
2152                self.parser().pos.set(start);
2153                return None;
2154            }
2155        };
2156        Some(ast::ClassAscii {
2157            span: Span::new(start, self.pos()),
2158            kind,
2159            negated,
2160        })
2161    }
2162
2163    /// Parse a Unicode class in either the single character notation, `\pN`
2164    /// or the multi-character bracketed notation, `\p{Greek}`. This assumes
2165    /// the parser is positioned at the `p` (or `P` for negation) and will
2166    /// advance the parser to the character immediately following the class.
2167    ///
2168    /// Note that this does not check whether the class name is valid or not.
2169    #[inline(never)]
2170    fn parse_unicode_class(&self) -> Result<ast::ClassUnicode> {
2171        assert!(self.char() == 'p' || self.char() == 'P');
2172
2173        let mut scratch = self.parser().scratch.borrow_mut();
2174        scratch.clear();
2175
2176        let negated = self.char() == 'P';
2177        if !self.bump_and_bump_space() {
2178            return Err(
2179                self.error(self.span(), ast::ErrorKind::EscapeUnexpectedEof)
2180            );
2181        }
2182        let (start, kind) = if self.char() == '{' {
2183            let start = self.span_char().end;
2184            while self.bump_and_bump_space() && self.char() != '}' {
2185                scratch.push(self.char());
2186            }
2187            if self.is_eof() {
2188                return Err(self
2189                    .error(self.span(), ast::ErrorKind::EscapeUnexpectedEof));
2190            }
2191            assert_eq!(self.char(), '}');
2192            self.bump();
2193
2194            let name = scratch.as_str();
2195            if let Some(i) = name.find("!=") {
2196                (
2197                    start,
2198                    ast::ClassUnicodeKind::NamedValue {
2199                        op: ast::ClassUnicodeOpKind::NotEqual,
2200                        name: name[..i].to_string(),
2201                        value: name[i + 2..].to_string(),
2202                    },
2203                )
2204            } else if let Some(i) = name.find(':') {
2205                (
2206                    start,
2207                    ast::ClassUnicodeKind::NamedValue {
2208                        op: ast::ClassUnicodeOpKind::Colon,
2209                        name: name[..i].to_string(),
2210                        value: name[i + 1..].to_string(),
2211                    },
2212                )
2213            } else if let Some(i) = name.find('=') {
2214                (
2215                    start,
2216                    ast::ClassUnicodeKind::NamedValue {
2217                        op: ast::ClassUnicodeOpKind::Equal,
2218                        name: name[..i].to_string(),
2219                        value: name[i + 1..].to_string(),
2220                    },
2221                )
2222            } else {
2223                (start, ast::ClassUnicodeKind::Named(name.to_string()))
2224            }
2225        } else {
2226            let start = self.pos();
2227            let c = self.char();
2228            if c == '\\' {
2229                return Err(self.error(
2230                    self.span_char(),
2231                    ast::ErrorKind::UnicodeClassInvalid,
2232                ));
2233            }
2234            self.bump_and_bump_space();
2235            let kind = ast::ClassUnicodeKind::OneLetter(c);
2236            (start, kind)
2237        };
2238        Ok(ast::ClassUnicode {
2239            span: Span::new(start, self.pos()),
2240            negated,
2241            kind,
2242        })
2243    }
2244
2245    /// Parse a Perl character class, e.g., `\d` or `\W`. This assumes the
2246    /// parser is currently at a valid character class name and will be
2247    /// advanced to the character immediately following the class.
2248    #[inline(never)]
2249    fn parse_perl_class(&self) -> ast::ClassPerl {
2250        let c = self.char();
2251        let span = self.span_char();
2252        self.bump();
2253        let (negated, kind) = match c {
2254            'd' => (false, ast::ClassPerlKind::Digit),
2255            'D' => (true, ast::ClassPerlKind::Digit),
2256            's' => (false, ast::ClassPerlKind::Space),
2257            'S' => (true, ast::ClassPerlKind::Space),
2258            'w' => (false, ast::ClassPerlKind::Word),
2259            'W' => (true, ast::ClassPerlKind::Word),
2260            c => panic!("expected valid Perl class but got '{c}'"),
2261        };
2262        ast::ClassPerl { span, kind, negated }
2263    }
2264}
2265
2266/// A type that traverses a fully parsed Ast and checks whether its depth
2267/// exceeds the specified nesting limit. If it does, then an error is returned.
2268#[derive(Debug)]
2269struct NestLimiter<'p, 's, P> {
2270    /// The parser that is checking the nest limit.
2271    p: &'p ParserI<'s, P>,
2272    /// The current depth while walking an Ast.
2273    depth: u32,
2274}
2275
2276impl<'p, 's, P: Borrow<Parser>> NestLimiter<'p, 's, P> {
2277    fn new(p: &'p ParserI<'s, P>) -> NestLimiter<'p, 's, P> {
2278        NestLimiter { p, depth: 0 }
2279    }
2280
2281    #[inline(never)]
2282    fn check(self, ast: &Ast) -> Result<()> {
2283        ast::visit(ast, self)
2284    }
2285
2286    fn increment_depth(&mut self, span: &Span) -> Result<()> {
2287        let new = self.depth.checked_add(1).ok_or_else(|| {
2288            self.p.error(
2289                span.clone(),
2290                ast::ErrorKind::NestLimitExceeded(u32::MAX),
2291            )
2292        })?;
2293        let limit = self.p.parser().nest_limit;
2294        if new > limit {
2295            return Err(self.p.error(
2296                span.clone(),
2297                ast::ErrorKind::NestLimitExceeded(limit),
2298            ));
2299        }
2300        self.depth = new;
2301        Ok(())
2302    }
2303
2304    fn decrement_depth(&mut self) {
2305        // Assuming the correctness of the visitor, this should never drop
2306        // below 0.
2307        self.depth = self.depth.checked_sub(1).unwrap();
2308    }
2309}
2310
2311impl<'p, 's, P: Borrow<Parser>> ast::Visitor for NestLimiter<'p, 's, P> {
2312    type Output = ();
2313    type Err = ast::Error;
2314
2315    fn finish(self) -> Result<()> {
2316        Ok(())
2317    }
2318
2319    fn visit_pre(&mut self, ast: &Ast) -> Result<()> {
2320        let span = match *ast {
2321            Ast::Empty(_)
2322            | Ast::Flags(_)
2323            | Ast::Literal(_)
2324            | Ast::Dot(_)
2325            | Ast::Assertion(_)
2326            | Ast::ClassUnicode(_)
2327            | Ast::ClassPerl(_) => {
2328                // These are all base cases, so we don't increment depth.
2329                return Ok(());
2330            }
2331            Ast::ClassBracketed(ref x) => &x.span,
2332            Ast::Repetition(ref x) => &x.span,
2333            Ast::Group(ref x) => &x.span,
2334            Ast::Alternation(ref x) => &x.span,
2335            Ast::Concat(ref x) => &x.span,
2336        };
2337        self.increment_depth(span)
2338    }
2339
2340    fn visit_post(&mut self, ast: &Ast) -> Result<()> {
2341        match *ast {
2342            Ast::Empty(_)
2343            | Ast::Flags(_)
2344            | Ast::Literal(_)
2345            | Ast::Dot(_)
2346            | Ast::Assertion(_)
2347            | Ast::ClassUnicode(_)
2348            | Ast::ClassPerl(_) => {
2349                // These are all base cases, so we don't decrement depth.
2350                Ok(())
2351            }
2352            Ast::ClassBracketed(_)
2353            | Ast::Repetition(_)
2354            | Ast::Group(_)
2355            | Ast::Alternation(_)
2356            | Ast::Concat(_) => {
2357                self.decrement_depth();
2358                Ok(())
2359            }
2360        }
2361    }
2362
2363    fn visit_class_set_item_pre(
2364        &mut self,
2365        ast: &ast::ClassSetItem,
2366    ) -> Result<()> {
2367        let span = match *ast {
2368            ast::ClassSetItem::Empty(_)
2369            | ast::ClassSetItem::Literal(_)
2370            | ast::ClassSetItem::Range(_)
2371            | ast::ClassSetItem::Ascii(_)
2372            | ast::ClassSetItem::Unicode(_)
2373            | ast::ClassSetItem::Perl(_) => {
2374                // These are all base cases, so we don't increment depth.
2375                return Ok(());
2376            }
2377            ast::ClassSetItem::Bracketed(ref x) => &x.span,
2378            ast::ClassSetItem::Union(ref x) => &x.span,
2379        };
2380        self.increment_depth(span)
2381    }
2382
2383    fn visit_class_set_item_post(
2384        &mut self,
2385        ast: &ast::ClassSetItem,
2386    ) -> Result<()> {
2387        match *ast {
2388            ast::ClassSetItem::Empty(_)
2389            | ast::ClassSetItem::Literal(_)
2390            | ast::ClassSetItem::Range(_)
2391            | ast::ClassSetItem::Ascii(_)
2392            | ast::ClassSetItem::Unicode(_)
2393            | ast::ClassSetItem::Perl(_) => {
2394                // These are all base cases, so we don't decrement depth.
2395                Ok(())
2396            }
2397            ast::ClassSetItem::Bracketed(_) | ast::ClassSetItem::Union(_) => {
2398                self.decrement_depth();
2399                Ok(())
2400            }
2401        }
2402    }
2403
2404    fn visit_class_set_binary_op_pre(
2405        &mut self,
2406        ast: &ast::ClassSetBinaryOp,
2407    ) -> Result<()> {
2408        self.increment_depth(&ast.span)
2409    }
2410
2411    fn visit_class_set_binary_op_post(
2412        &mut self,
2413        _ast: &ast::ClassSetBinaryOp,
2414    ) -> Result<()> {
2415        self.decrement_depth();
2416        Ok(())
2417    }
2418}
2419
2420/// When the result is an error, transforms the ast::ErrorKind from the source
2421/// Result into another one. This function is used to return clearer error
2422/// messages when possible.
2423fn specialize_err<T>(
2424    result: Result<T>,
2425    from: ast::ErrorKind,
2426    to: ast::ErrorKind,
2427) -> Result<T> {
2428    if let Err(e) = result {
2429        if e.kind == from {
2430            Err(ast::Error { kind: to, pattern: e.pattern, span: e.span })
2431        } else {
2432            Err(e)
2433        }
2434    } else {
2435        result
2436    }
2437}
2438
2439#[cfg(test)]
2440mod tests {
2441    use core::ops::Range;
2442
2443    use alloc::format;
2444
2445    use super::*;
2446
2447    // Our own assert_eq, which has slightly better formatting (but honestly
2448    // still kind of crappy).
2449    macro_rules! assert_eq {
2450        ($left:expr, $right:expr) => {{
2451            match (&$left, &$right) {
2452                (left_val, right_val) => {
2453                    if !(*left_val == *right_val) {
2454                        panic!(
2455                            "assertion failed: `(left == right)`\n\n\
2456                             left:  `{:?}`\nright: `{:?}`\n\n",
2457                            left_val, right_val
2458                        )
2459                    }
2460                }
2461            }
2462        }};
2463    }
2464
2465    // We create these errors to compare with real ast::Errors in the tests.
2466    // We define equality between TestError and ast::Error to disregard the
2467    // pattern string in ast::Error, which is annoying to provide in tests.
2468    #[derive(Clone, Debug)]
2469    struct TestError {
2470        span: Span,
2471        kind: ast::ErrorKind,
2472    }
2473
2474    impl PartialEq<ast::Error> for TestError {
2475        fn eq(&self, other: &ast::Error) -> bool {
2476            self.span == other.span && self.kind == other.kind
2477        }
2478    }
2479
2480    impl PartialEq<TestError> for ast::Error {
2481        fn eq(&self, other: &TestError) -> bool {
2482            self.span == other.span && self.kind == other.kind
2483        }
2484    }
2485
2486    fn s(str: &str) -> String {
2487        str.to_string()
2488    }
2489
2490    fn parser(pattern: &str) -> ParserI<'_, Parser> {
2491        ParserI::new(Parser::new(), pattern)
2492    }
2493
2494    fn parser_octal(pattern: &str) -> ParserI<'_, Parser> {
2495        let parser = ParserBuilder::new().octal(true).build();
2496        ParserI::new(parser, pattern)
2497    }
2498
2499    fn parser_empty_min_range(pattern: &str) -> ParserI<'_, Parser> {
2500        let parser = ParserBuilder::new().empty_min_range(true).build();
2501        ParserI::new(parser, pattern)
2502    }
2503
2504    fn parser_nest_limit(
2505        pattern: &str,
2506        nest_limit: u32,
2507    ) -> ParserI<'_, Parser> {
2508        let p = ParserBuilder::new().nest_limit(nest_limit).build();
2509        ParserI::new(p, pattern)
2510    }
2511
2512    fn parser_ignore_whitespace(pattern: &str) -> ParserI<'_, Parser> {
2513        let p = ParserBuilder::new().ignore_whitespace(true).build();
2514        ParserI::new(p, pattern)
2515    }
2516
2517    /// Short alias for creating a new span.
2518    fn nspan(start: Position, end: Position) -> Span {
2519        Span::new(start, end)
2520    }
2521
2522    /// Short alias for creating a new position.
2523    fn npos(offset: usize, line: usize, column: usize) -> Position {
2524        Position::new(offset, line, column)
2525    }
2526
2527    /// Create a new span from the given offset range. This assumes a single
2528    /// line and sets the columns based on the offsets. i.e., This only works
2529    /// out of the box for ASCII, which is fine for most tests.
2530    fn span(range: Range<usize>) -> Span {
2531        let start = Position::new(range.start, 1, range.start + 1);
2532        let end = Position::new(range.end, 1, range.end + 1);
2533        Span::new(start, end)
2534    }
2535
2536    /// Create a new span for the corresponding byte range in the given string.
2537    fn span_range(subject: &str, range: Range<usize>) -> Span {
2538        let start = Position {
2539            offset: range.start,
2540            line: 1 + subject[..range.start].matches('\n').count(),
2541            column: 1 + subject[..range.start]
2542                .chars()
2543                .rev()
2544                .position(|c| c == '\n')
2545                .unwrap_or(subject[..range.start].chars().count()),
2546        };
2547        let end = Position {
2548            offset: range.end,
2549            line: 1 + subject[..range.end].matches('\n').count(),
2550            column: 1 + subject[..range.end]
2551                .chars()
2552                .rev()
2553                .position(|c| c == '\n')
2554                .unwrap_or(subject[..range.end].chars().count()),
2555        };
2556        Span::new(start, end)
2557    }
2558
2559    /// Create a verbatim literal starting at the given position.
2560    fn lit(c: char, start: usize) -> Ast {
2561        lit_with(c, span(start..start + c.len_utf8()))
2562    }
2563
2564    /// Create a meta literal starting at the given position.
2565    fn meta_lit(c: char, span: Span) -> Ast {
2566        Ast::literal(ast::Literal { span, kind: ast::LiteralKind::Meta, c })
2567    }
2568
2569    /// Create a verbatim literal with the given span.
2570    fn lit_with(c: char, span: Span) -> Ast {
2571        Ast::literal(ast::Literal {
2572            span,
2573            kind: ast::LiteralKind::Verbatim,
2574            c,
2575        })
2576    }
2577
2578    /// Create a concatenation with the given range.
2579    fn concat(range: Range<usize>, asts: Vec<Ast>) -> Ast {
2580        concat_with(span(range), asts)
2581    }
2582
2583    /// Create a concatenation with the given span.
2584    fn concat_with(span: Span, asts: Vec<Ast>) -> Ast {
2585        Ast::concat(ast::Concat { span, asts })
2586    }
2587
2588    /// Create an alternation with the given span.
2589    fn alt(range: Range<usize>, asts: Vec<Ast>) -> Ast {
2590        Ast::alternation(ast::Alternation { span: span(range), asts })
2591    }
2592
2593    /// Create a capturing group with the given span.
2594    fn group(range: Range<usize>, index: u32, ast: Ast) -> Ast {
2595        Ast::group(ast::Group {
2596            span: span(range),
2597            kind: ast::GroupKind::CaptureIndex(index),
2598            ast: Box::new(ast),
2599        })
2600    }
2601
2602    /// Create an ast::SetFlags.
2603    ///
2604    /// The given pattern should be the full pattern string. The range given
2605    /// should correspond to the byte offsets where the flag set occurs.
2606    ///
2607    /// If negated is true, then the set is interpreted as beginning with a
2608    /// negation.
2609    fn flag_set(
2610        pat: &str,
2611        range: Range<usize>,
2612        flag: ast::Flag,
2613        negated: bool,
2614    ) -> Ast {
2615        let mut items = vec![ast::FlagsItem {
2616            span: span_range(pat, (range.end - 2)..(range.end - 1)),
2617            kind: ast::FlagsItemKind::Flag(flag),
2618        }];
2619        if negated {
2620            items.insert(
2621                0,
2622                ast::FlagsItem {
2623                    span: span_range(pat, (range.start + 2)..(range.end - 2)),
2624                    kind: ast::FlagsItemKind::Negation,
2625                },
2626            );
2627        }
2628        Ast::flags(ast::SetFlags {
2629            span: span_range(pat, range.clone()),
2630            flags: ast::Flags {
2631                span: span_range(pat, (range.start + 2)..(range.end - 1)),
2632                items,
2633            },
2634        })
2635    }
2636
2637    #[test]
2638    fn parser_can_be_reused() {
2639        let mut p = Parser::new();
2640        assert!(p.parse("a").is_ok());
2641        assert!(p.parse("a").is_ok());
2642        assert!(p.parse("b+").is_ok());
2643
2644        // Capture indices must restart at 1 on each parse.
2645        let first = p.parse("(a)").unwrap();
2646        let second = p.parse("(a)").unwrap();
2647        assert_eq!(first, second);
2648
2649        // Named groups from a previous parse must not count as duplicates.
2650        assert!(p.parse("(?P<foo>a)").is_ok());
2651        assert!(p.parse("(?P<foo>a)").is_ok());
2652        assert!(p.parse("(?<bar>a)").is_ok());
2653    }
2654
2655    #[test]
2656    fn parse_nest_limit() {
2657        // A nest limit of 0 still allows some types of regexes.
2658        assert_eq!(
2659            parser_nest_limit("", 0).parse(),
2660            Ok(Ast::empty(span(0..0)))
2661        );
2662        assert_eq!(parser_nest_limit("a", 0).parse(), Ok(lit('a', 0)));
2663
2664        // Test repetition operations, which require one level of nesting.
2665        assert_eq!(
2666            parser_nest_limit("a+", 0).parse().unwrap_err(),
2667            TestError {
2668                span: span(0..2),
2669                kind: ast::ErrorKind::NestLimitExceeded(0),
2670            }
2671        );
2672        assert_eq!(
2673            parser_nest_limit("a+", 1).parse(),
2674            Ok(Ast::repetition(ast::Repetition {
2675                span: span(0..2),
2676                op: ast::RepetitionOp {
2677                    span: span(1..2),
2678                    kind: ast::RepetitionKind::OneOrMore,
2679                },
2680                greedy: true,
2681                ast: Box::new(lit('a', 0)),
2682            }))
2683        );
2684        assert_eq!(
2685            parser_nest_limit("(a)+", 1).parse().unwrap_err(),
2686            TestError {
2687                span: span(0..3),
2688                kind: ast::ErrorKind::NestLimitExceeded(1),
2689            }
2690        );
2691        assert_eq!(
2692            parser_nest_limit("a+*", 1).parse().unwrap_err(),
2693            TestError {
2694                span: span(0..2),
2695                kind: ast::ErrorKind::NestLimitExceeded(1),
2696            }
2697        );
2698        assert_eq!(
2699            parser_nest_limit("a+*", 2).parse(),
2700            Ok(Ast::repetition(ast::Repetition {
2701                span: span(0..3),
2702                op: ast::RepetitionOp {
2703                    span: span(2..3),
2704                    kind: ast::RepetitionKind::ZeroOrMore,
2705                },
2706                greedy: true,
2707                ast: Box::new(Ast::repetition(ast::Repetition {
2708                    span: span(0..2),
2709                    op: ast::RepetitionOp {
2710                        span: span(1..2),
2711                        kind: ast::RepetitionKind::OneOrMore,
2712                    },
2713                    greedy: true,
2714                    ast: Box::new(lit('a', 0)),
2715                })),
2716            }))
2717        );
2718
2719        // Test concatenations. A concatenation requires one level of nesting.
2720        assert_eq!(
2721            parser_nest_limit("ab", 0).parse().unwrap_err(),
2722            TestError {
2723                span: span(0..2),
2724                kind: ast::ErrorKind::NestLimitExceeded(0),
2725            }
2726        );
2727        assert_eq!(
2728            parser_nest_limit("ab", 1).parse(),
2729            Ok(concat(0..2, vec![lit('a', 0), lit('b', 1)]))
2730        );
2731        assert_eq!(
2732            parser_nest_limit("abc", 1).parse(),
2733            Ok(concat(0..3, vec![lit('a', 0), lit('b', 1), lit('c', 2)]))
2734        );
2735
2736        // Test alternations. An alternation requires one level of nesting.
2737        assert_eq!(
2738            parser_nest_limit("a|b", 0).parse().unwrap_err(),
2739            TestError {
2740                span: span(0..3),
2741                kind: ast::ErrorKind::NestLimitExceeded(0),
2742            }
2743        );
2744        assert_eq!(
2745            parser_nest_limit("a|b", 1).parse(),
2746            Ok(alt(0..3, vec![lit('a', 0), lit('b', 2)]))
2747        );
2748        assert_eq!(
2749            parser_nest_limit("a|b|c", 1).parse(),
2750            Ok(alt(0..5, vec![lit('a', 0), lit('b', 2), lit('c', 4)]))
2751        );
2752
2753        // Test character classes. Classes form their own mini-recursive
2754        // syntax!
2755        assert_eq!(
2756            parser_nest_limit("[a]", 0).parse().unwrap_err(),
2757            TestError {
2758                span: span(0..3),
2759                kind: ast::ErrorKind::NestLimitExceeded(0),
2760            }
2761        );
2762        assert_eq!(
2763            parser_nest_limit("[a]", 1).parse(),
2764            Ok(Ast::class_bracketed(ast::ClassBracketed {
2765                span: span(0..3),
2766                negated: false,
2767                kind: ast::ClassSet::Item(ast::ClassSetItem::Literal(
2768                    ast::Literal {
2769                        span: span(1..2),
2770                        kind: ast::LiteralKind::Verbatim,
2771                        c: 'a',
2772                    }
2773                )),
2774            }))
2775        );
2776        assert_eq!(
2777            parser_nest_limit("[ab]", 1).parse().unwrap_err(),
2778            TestError {
2779                span: span(1..3),
2780                kind: ast::ErrorKind::NestLimitExceeded(1),
2781            }
2782        );
2783        assert_eq!(
2784            parser_nest_limit("[ab[cd]]", 2).parse().unwrap_err(),
2785            TestError {
2786                span: span(3..7),
2787                kind: ast::ErrorKind::NestLimitExceeded(2),
2788            }
2789        );
2790        assert_eq!(
2791            parser_nest_limit("[ab[cd]]", 3).parse().unwrap_err(),
2792            TestError {
2793                span: span(4..6),
2794                kind: ast::ErrorKind::NestLimitExceeded(3),
2795            }
2796        );
2797        assert_eq!(
2798            parser_nest_limit("[a--b]", 1).parse().unwrap_err(),
2799            TestError {
2800                span: span(1..5),
2801                kind: ast::ErrorKind::NestLimitExceeded(1),
2802            }
2803        );
2804        assert_eq!(
2805            parser_nest_limit("[a--bc]", 2).parse().unwrap_err(),
2806            TestError {
2807                span: span(4..6),
2808                kind: ast::ErrorKind::NestLimitExceeded(2),
2809            }
2810        );
2811    }
2812
2813    #[test]
2814    fn parse_comments() {
2815        let pat = "(?x)
2816# This is comment 1.
2817foo # This is comment 2.
2818  # This is comment 3.
2819bar
2820# This is comment 4.";
2821        let astc = parser(pat).parse_with_comments().unwrap();
2822        assert_eq!(
2823            astc.ast,
2824            concat_with(
2825                span_range(pat, 0..pat.len()),
2826                vec![
2827                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
2828                    lit_with('f', span_range(pat, 26..27)),
2829                    lit_with('o', span_range(pat, 27..28)),
2830                    lit_with('o', span_range(pat, 28..29)),
2831                    lit_with('b', span_range(pat, 74..75)),
2832                    lit_with('a', span_range(pat, 75..76)),
2833                    lit_with('r', span_range(pat, 76..77)),
2834                ]
2835            )
2836        );
2837        assert_eq!(
2838            astc.comments,
2839            vec![
2840                ast::Comment {
2841                    span: span_range(pat, 5..26),
2842                    comment: s(" This is comment 1."),
2843                },
2844                ast::Comment {
2845                    span: span_range(pat, 30..51),
2846                    comment: s(" This is comment 2."),
2847                },
2848                ast::Comment {
2849                    span: span_range(pat, 53..74),
2850                    comment: s(" This is comment 3."),
2851                },
2852                ast::Comment {
2853                    span: span_range(pat, 78..98),
2854                    comment: s(" This is comment 4."),
2855                },
2856            ]
2857        );
2858    }
2859
2860    #[test]
2861    fn parse_holistic() {
2862        assert_eq!(parser("]").parse(), Ok(lit(']', 0)));
2863        assert_eq!(
2864            parser(r"\\\.\+\*\?\(\)\|\[\]\{\}\^\$\#\&\-\~").parse(),
2865            Ok(concat(
2866                0..36,
2867                vec![
2868                    meta_lit('\\', span(0..2)),
2869                    meta_lit('.', span(2..4)),
2870                    meta_lit('+', span(4..6)),
2871                    meta_lit('*', span(6..8)),
2872                    meta_lit('?', span(8..10)),
2873                    meta_lit('(', span(10..12)),
2874                    meta_lit(')', span(12..14)),
2875                    meta_lit('|', span(14..16)),
2876                    meta_lit('[', span(16..18)),
2877                    meta_lit(']', span(18..20)),
2878                    meta_lit('{', span(20..22)),
2879                    meta_lit('}', span(22..24)),
2880                    meta_lit('^', span(24..26)),
2881                    meta_lit('$', span(26..28)),
2882                    meta_lit('#', span(28..30)),
2883                    meta_lit('&', span(30..32)),
2884                    meta_lit('-', span(32..34)),
2885                    meta_lit('~', span(34..36)),
2886                ]
2887            ))
2888        );
2889    }
2890
2891    #[test]
2892    fn parse_ignore_whitespace() {
2893        // Test that basic whitespace insensitivity works.
2894        let pat = "(?x)a b";
2895        assert_eq!(
2896            parser(pat).parse(),
2897            Ok(concat_with(
2898                nspan(npos(0, 1, 1), npos(7, 1, 8)),
2899                vec![
2900                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
2901                    lit_with('a', nspan(npos(4, 1, 5), npos(5, 1, 6))),
2902                    lit_with('b', nspan(npos(6, 1, 7), npos(7, 1, 8))),
2903                ]
2904            ))
2905        );
2906
2907        // Test that we can toggle whitespace insensitivity.
2908        let pat = "(?x)a b(?-x)a b";
2909        assert_eq!(
2910            parser(pat).parse(),
2911            Ok(concat_with(
2912                nspan(npos(0, 1, 1), npos(15, 1, 16)),
2913                vec![
2914                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
2915                    lit_with('a', nspan(npos(4, 1, 5), npos(5, 1, 6))),
2916                    lit_with('b', nspan(npos(6, 1, 7), npos(7, 1, 8))),
2917                    flag_set(pat, 7..12, ast::Flag::IgnoreWhitespace, true),
2918                    lit_with('a', nspan(npos(12, 1, 13), npos(13, 1, 14))),
2919                    lit_with(' ', nspan(npos(13, 1, 14), npos(14, 1, 15))),
2920                    lit_with('b', nspan(npos(14, 1, 15), npos(15, 1, 16))),
2921                ]
2922            ))
2923        );
2924
2925        // Test that nesting whitespace insensitive flags works.
2926        let pat = "a (?x:a )a ";
2927        assert_eq!(
2928            parser(pat).parse(),
2929            Ok(concat_with(
2930                span_range(pat, 0..11),
2931                vec![
2932                    lit_with('a', span_range(pat, 0..1)),
2933                    lit_with(' ', span_range(pat, 1..2)),
2934                    Ast::group(ast::Group {
2935                        span: span_range(pat, 2..9),
2936                        kind: ast::GroupKind::NonCapturing(ast::Flags {
2937                            span: span_range(pat, 4..5),
2938                            items: vec![ast::FlagsItem {
2939                                span: span_range(pat, 4..5),
2940                                kind: ast::FlagsItemKind::Flag(
2941                                    ast::Flag::IgnoreWhitespace
2942                                ),
2943                            },],
2944                        }),
2945                        ast: Box::new(lit_with('a', span_range(pat, 6..7))),
2946                    }),
2947                    lit_with('a', span_range(pat, 9..10)),
2948                    lit_with(' ', span_range(pat, 10..11)),
2949                ]
2950            ))
2951        );
2952
2953        // Test that whitespace after an opening paren is insignificant.
2954        let pat = "(?x)( ?P<foo> a )";
2955        assert_eq!(
2956            parser(pat).parse(),
2957            Ok(concat_with(
2958                span_range(pat, 0..pat.len()),
2959                vec![
2960                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
2961                    Ast::group(ast::Group {
2962                        span: span_range(pat, 4..pat.len()),
2963                        kind: ast::GroupKind::CaptureName {
2964                            starts_with_p: true,
2965                            name: ast::CaptureName {
2966                                span: span_range(pat, 9..12),
2967                                name: s("foo"),
2968                                index: 1,
2969                            }
2970                        },
2971                        ast: Box::new(lit_with('a', span_range(pat, 14..15))),
2972                    }),
2973                ]
2974            ))
2975        );
2976        let pat = "(?x)(  a )";
2977        assert_eq!(
2978            parser(pat).parse(),
2979            Ok(concat_with(
2980                span_range(pat, 0..pat.len()),
2981                vec![
2982                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
2983                    Ast::group(ast::Group {
2984                        span: span_range(pat, 4..pat.len()),
2985                        kind: ast::GroupKind::CaptureIndex(1),
2986                        ast: Box::new(lit_with('a', span_range(pat, 7..8))),
2987                    }),
2988                ]
2989            ))
2990        );
2991        let pat = "(?x)(  ?:  a )";
2992        assert_eq!(
2993            parser(pat).parse(),
2994            Ok(concat_with(
2995                span_range(pat, 0..pat.len()),
2996                vec![
2997                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
2998                    Ast::group(ast::Group {
2999                        span: span_range(pat, 4..pat.len()),
3000                        kind: ast::GroupKind::NonCapturing(ast::Flags {
3001                            span: span_range(pat, 8..8),
3002                            items: vec![],
3003                        }),
3004                        ast: Box::new(lit_with('a', span_range(pat, 11..12))),
3005                    }),
3006                ]
3007            ))
3008        );
3009        let pat = r"(?x)\x { 53 }";
3010        assert_eq!(
3011            parser(pat).parse(),
3012            Ok(concat_with(
3013                span_range(pat, 0..pat.len()),
3014                vec![
3015                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
3016                    Ast::literal(ast::Literal {
3017                        span: span(4..13),
3018                        kind: ast::LiteralKind::HexBrace(
3019                            ast::HexLiteralKind::X
3020                        ),
3021                        c: 'S',
3022                    }),
3023                ]
3024            ))
3025        );
3026
3027        // Test that whitespace after an escape is OK.
3028        let pat = r"(?x)\ ";
3029        assert_eq!(
3030            parser(pat).parse(),
3031            Ok(concat_with(
3032                span_range(pat, 0..pat.len()),
3033                vec![
3034                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
3035                    Ast::literal(ast::Literal {
3036                        span: span_range(pat, 4..6),
3037                        kind: ast::LiteralKind::Superfluous,
3038                        c: ' ',
3039                    }),
3040                ]
3041            ))
3042        );
3043    }
3044
3045    #[test]
3046    fn parse_newlines() {
3047        let pat = ".\n.";
3048        assert_eq!(
3049            parser(pat).parse(),
3050            Ok(concat_with(
3051                span_range(pat, 0..3),
3052                vec![
3053                    Ast::dot(span_range(pat, 0..1)),
3054                    lit_with('\n', span_range(pat, 1..2)),
3055                    Ast::dot(span_range(pat, 2..3)),
3056                ]
3057            ))
3058        );
3059
3060        let pat = "foobar\nbaz\nquux\n";
3061        assert_eq!(
3062            parser(pat).parse(),
3063            Ok(concat_with(
3064                span_range(pat, 0..pat.len()),
3065                vec![
3066                    lit_with('f', nspan(npos(0, 1, 1), npos(1, 1, 2))),
3067                    lit_with('o', nspan(npos(1, 1, 2), npos(2, 1, 3))),
3068                    lit_with('o', nspan(npos(2, 1, 3), npos(3, 1, 4))),
3069                    lit_with('b', nspan(npos(3, 1, 4), npos(4, 1, 5))),
3070                    lit_with('a', nspan(npos(4, 1, 5), npos(5, 1, 6))),
3071                    lit_with('r', nspan(npos(5, 1, 6), npos(6, 1, 7))),
3072                    lit_with('\n', nspan(npos(6, 1, 7), npos(7, 2, 1))),
3073                    lit_with('b', nspan(npos(7, 2, 1), npos(8, 2, 2))),
3074                    lit_with('a', nspan(npos(8, 2, 2), npos(9, 2, 3))),
3075                    lit_with('z', nspan(npos(9, 2, 3), npos(10, 2, 4))),
3076                    lit_with('\n', nspan(npos(10, 2, 4), npos(11, 3, 1))),
3077                    lit_with('q', nspan(npos(11, 3, 1), npos(12, 3, 2))),
3078                    lit_with('u', nspan(npos(12, 3, 2), npos(13, 3, 3))),
3079                    lit_with('u', nspan(npos(13, 3, 3), npos(14, 3, 4))),
3080                    lit_with('x', nspan(npos(14, 3, 4), npos(15, 3, 5))),
3081                    lit_with('\n', nspan(npos(15, 3, 5), npos(16, 4, 1))),
3082                ]
3083            ))
3084        );
3085    }
3086
3087    #[test]
3088    fn parse_uncounted_repetition() {
3089        assert_eq!(
3090            parser(r"a*").parse(),
3091            Ok(Ast::repetition(ast::Repetition {
3092                span: span(0..2),
3093                op: ast::RepetitionOp {
3094                    span: span(1..2),
3095                    kind: ast::RepetitionKind::ZeroOrMore,
3096                },
3097                greedy: true,
3098                ast: Box::new(lit('a', 0)),
3099            }))
3100        );
3101        assert_eq!(
3102            parser(r"a+").parse(),
3103            Ok(Ast::repetition(ast::Repetition {
3104                span: span(0..2),
3105                op: ast::RepetitionOp {
3106                    span: span(1..2),
3107                    kind: ast::RepetitionKind::OneOrMore,
3108                },
3109                greedy: true,
3110                ast: Box::new(lit('a', 0)),
3111            }))
3112        );
3113
3114        assert_eq!(
3115            parser(r"a?").parse(),
3116            Ok(Ast::repetition(ast::Repetition {
3117                span: span(0..2),
3118                op: ast::RepetitionOp {
3119                    span: span(1..2),
3120                    kind: ast::RepetitionKind::ZeroOrOne,
3121                },
3122                greedy: true,
3123                ast: Box::new(lit('a', 0)),
3124            }))
3125        );
3126        assert_eq!(
3127            parser(r"a??").parse(),
3128            Ok(Ast::repetition(ast::Repetition {
3129                span: span(0..3),
3130                op: ast::RepetitionOp {
3131                    span: span(1..3),
3132                    kind: ast::RepetitionKind::ZeroOrOne,
3133                },
3134                greedy: false,
3135                ast: Box::new(lit('a', 0)),
3136            }))
3137        );
3138        assert_eq!(
3139            parser(r"a?").parse(),
3140            Ok(Ast::repetition(ast::Repetition {
3141                span: span(0..2),
3142                op: ast::RepetitionOp {
3143                    span: span(1..2),
3144                    kind: ast::RepetitionKind::ZeroOrOne,
3145                },
3146                greedy: true,
3147                ast: Box::new(lit('a', 0)),
3148            }))
3149        );
3150        assert_eq!(
3151            parser(r"a?b").parse(),
3152            Ok(concat(
3153                0..3,
3154                vec![
3155                    Ast::repetition(ast::Repetition {
3156                        span: span(0..2),
3157                        op: ast::RepetitionOp {
3158                            span: span(1..2),
3159                            kind: ast::RepetitionKind::ZeroOrOne,
3160                        },
3161                        greedy: true,
3162                        ast: Box::new(lit('a', 0)),
3163                    }),
3164                    lit('b', 2),
3165                ]
3166            ))
3167        );
3168        assert_eq!(
3169            parser(r"a??b").parse(),
3170            Ok(concat(
3171                0..4,
3172                vec![
3173                    Ast::repetition(ast::Repetition {
3174                        span: span(0..3),
3175                        op: ast::RepetitionOp {
3176                            span: span(1..3),
3177                            kind: ast::RepetitionKind::ZeroOrOne,
3178                        },
3179                        greedy: false,
3180                        ast: Box::new(lit('a', 0)),
3181                    }),
3182                    lit('b', 3),
3183                ]
3184            ))
3185        );
3186        assert_eq!(
3187            parser(r"ab?").parse(),
3188            Ok(concat(
3189                0..3,
3190                vec![
3191                    lit('a', 0),
3192                    Ast::repetition(ast::Repetition {
3193                        span: span(1..3),
3194                        op: ast::RepetitionOp {
3195                            span: span(2..3),
3196                            kind: ast::RepetitionKind::ZeroOrOne,
3197                        },
3198                        greedy: true,
3199                        ast: Box::new(lit('b', 1)),
3200                    }),
3201                ]
3202            ))
3203        );
3204        assert_eq!(
3205            parser(r"(ab)?").parse(),
3206            Ok(Ast::repetition(ast::Repetition {
3207                span: span(0..5),
3208                op: ast::RepetitionOp {
3209                    span: span(4..5),
3210                    kind: ast::RepetitionKind::ZeroOrOne,
3211                },
3212                greedy: true,
3213                ast: Box::new(group(
3214                    0..4,
3215                    1,
3216                    concat(1..3, vec![lit('a', 1), lit('b', 2),])
3217                )),
3218            }))
3219        );
3220        assert_eq!(
3221            parser(r"|a?").parse(),
3222            Ok(alt(
3223                0..3,
3224                vec![
3225                    Ast::empty(span(0..0)),
3226                    Ast::repetition(ast::Repetition {
3227                        span: span(1..3),
3228                        op: ast::RepetitionOp {
3229                            span: span(2..3),
3230                            kind: ast::RepetitionKind::ZeroOrOne,
3231                        },
3232                        greedy: true,
3233                        ast: Box::new(lit('a', 1)),
3234                    }),
3235                ]
3236            ))
3237        );
3238
3239        assert_eq!(
3240            parser(r"*").parse().unwrap_err(),
3241            TestError {
3242                span: span(0..0),
3243                kind: ast::ErrorKind::RepetitionMissing,
3244            }
3245        );
3246        assert_eq!(
3247            parser(r"(?i)*").parse().unwrap_err(),
3248            TestError {
3249                span: span(4..4),
3250                kind: ast::ErrorKind::RepetitionMissing,
3251            }
3252        );
3253        assert_eq!(
3254            parser(r"(*)").parse().unwrap_err(),
3255            TestError {
3256                span: span(1..1),
3257                kind: ast::ErrorKind::RepetitionMissing,
3258            }
3259        );
3260        assert_eq!(
3261            parser(r"(?:?)").parse().unwrap_err(),
3262            TestError {
3263                span: span(3..3),
3264                kind: ast::ErrorKind::RepetitionMissing,
3265            }
3266        );
3267        assert_eq!(
3268            parser(r"+").parse().unwrap_err(),
3269            TestError {
3270                span: span(0..0),
3271                kind: ast::ErrorKind::RepetitionMissing,
3272            }
3273        );
3274        assert_eq!(
3275            parser(r"?").parse().unwrap_err(),
3276            TestError {
3277                span: span(0..0),
3278                kind: ast::ErrorKind::RepetitionMissing,
3279            }
3280        );
3281        assert_eq!(
3282            parser(r"(?)").parse().unwrap_err(),
3283            TestError {
3284                span: span(1..1),
3285                kind: ast::ErrorKind::RepetitionMissing,
3286            }
3287        );
3288        assert_eq!(
3289            parser(r"|*").parse().unwrap_err(),
3290            TestError {
3291                span: span(1..1),
3292                kind: ast::ErrorKind::RepetitionMissing,
3293            }
3294        );
3295        assert_eq!(
3296            parser(r"|+").parse().unwrap_err(),
3297            TestError {
3298                span: span(1..1),
3299                kind: ast::ErrorKind::RepetitionMissing,
3300            }
3301        );
3302        assert_eq!(
3303            parser(r"|?").parse().unwrap_err(),
3304            TestError {
3305                span: span(1..1),
3306                kind: ast::ErrorKind::RepetitionMissing,
3307            }
3308        );
3309    }
3310
3311    #[test]
3312    fn parse_counted_repetition() {
3313        assert_eq!(
3314            parser(r"a{5}").parse(),
3315            Ok(Ast::repetition(ast::Repetition {
3316                span: span(0..4),
3317                op: ast::RepetitionOp {
3318                    span: span(1..4),
3319                    kind: ast::RepetitionKind::Range(
3320                        ast::RepetitionRange::Exactly(5)
3321                    ),
3322                },
3323                greedy: true,
3324                ast: Box::new(lit('a', 0)),
3325            }))
3326        );
3327        assert_eq!(
3328            parser(r"a{5,}").parse(),
3329            Ok(Ast::repetition(ast::Repetition {
3330                span: span(0..5),
3331                op: ast::RepetitionOp {
3332                    span: span(1..5),
3333                    kind: ast::RepetitionKind::Range(
3334                        ast::RepetitionRange::AtLeast(5)
3335                    ),
3336                },
3337                greedy: true,
3338                ast: Box::new(lit('a', 0)),
3339            }))
3340        );
3341        assert_eq!(
3342            parser(r"a{5,9}").parse(),
3343            Ok(Ast::repetition(ast::Repetition {
3344                span: span(0..6),
3345                op: ast::RepetitionOp {
3346                    span: span(1..6),
3347                    kind: ast::RepetitionKind::Range(
3348                        ast::RepetitionRange::Bounded(5, 9)
3349                    ),
3350                },
3351                greedy: true,
3352                ast: Box::new(lit('a', 0)),
3353            }))
3354        );
3355        assert_eq!(
3356            parser(r"a{5}?").parse(),
3357            Ok(Ast::repetition(ast::Repetition {
3358                span: span(0..5),
3359                op: ast::RepetitionOp {
3360                    span: span(1..5),
3361                    kind: ast::RepetitionKind::Range(
3362                        ast::RepetitionRange::Exactly(5)
3363                    ),
3364                },
3365                greedy: false,
3366                ast: Box::new(lit('a', 0)),
3367            }))
3368        );
3369        assert_eq!(
3370            parser(r"ab{5}").parse(),
3371            Ok(concat(
3372                0..5,
3373                vec![
3374                    lit('a', 0),
3375                    Ast::repetition(ast::Repetition {
3376                        span: span(1..5),
3377                        op: ast::RepetitionOp {
3378                            span: span(2..5),
3379                            kind: ast::RepetitionKind::Range(
3380                                ast::RepetitionRange::Exactly(5)
3381                            ),
3382                        },
3383                        greedy: true,
3384                        ast: Box::new(lit('b', 1)),
3385                    }),
3386                ]
3387            ))
3388        );
3389        assert_eq!(
3390            parser(r"ab{5}c").parse(),
3391            Ok(concat(
3392                0..6,
3393                vec![
3394                    lit('a', 0),
3395                    Ast::repetition(ast::Repetition {
3396                        span: span(1..5),
3397                        op: ast::RepetitionOp {
3398                            span: span(2..5),
3399                            kind: ast::RepetitionKind::Range(
3400                                ast::RepetitionRange::Exactly(5)
3401                            ),
3402                        },
3403                        greedy: true,
3404                        ast: Box::new(lit('b', 1)),
3405                    }),
3406                    lit('c', 5),
3407                ]
3408            ))
3409        );
3410
3411        assert_eq!(
3412            parser(r"a{ 5 }").parse(),
3413            Ok(Ast::repetition(ast::Repetition {
3414                span: span(0..6),
3415                op: ast::RepetitionOp {
3416                    span: span(1..6),
3417                    kind: ast::RepetitionKind::Range(
3418                        ast::RepetitionRange::Exactly(5)
3419                    ),
3420                },
3421                greedy: true,
3422                ast: Box::new(lit('a', 0)),
3423            }))
3424        );
3425        assert_eq!(
3426            parser(r"a{ 5 , 9 }").parse(),
3427            Ok(Ast::repetition(ast::Repetition {
3428                span: span(0..10),
3429                op: ast::RepetitionOp {
3430                    span: span(1..10),
3431                    kind: ast::RepetitionKind::Range(
3432                        ast::RepetitionRange::Bounded(5, 9)
3433                    ),
3434                },
3435                greedy: true,
3436                ast: Box::new(lit('a', 0)),
3437            }))
3438        );
3439        assert_eq!(
3440            parser_empty_min_range(r"a{,9}").parse(),
3441            Ok(Ast::repetition(ast::Repetition {
3442                span: span(0..5),
3443                op: ast::RepetitionOp {
3444                    span: span(1..5),
3445                    kind: ast::RepetitionKind::Range(
3446                        ast::RepetitionRange::Bounded(0, 9)
3447                    ),
3448                },
3449                greedy: true,
3450                ast: Box::new(lit('a', 0)),
3451            }))
3452        );
3453        assert_eq!(
3454            parser_ignore_whitespace(r"a{5,9} ?").parse(),
3455            Ok(Ast::repetition(ast::Repetition {
3456                span: span(0..8),
3457                op: ast::RepetitionOp {
3458                    span: span(1..8),
3459                    kind: ast::RepetitionKind::Range(
3460                        ast::RepetitionRange::Bounded(5, 9)
3461                    ),
3462                },
3463                greedy: false,
3464                ast: Box::new(lit('a', 0)),
3465            }))
3466        );
3467        assert_eq!(
3468            parser(r"\b{5,9}").parse(),
3469            Ok(Ast::repetition(ast::Repetition {
3470                span: span(0..7),
3471                op: ast::RepetitionOp {
3472                    span: span(2..7),
3473                    kind: ast::RepetitionKind::Range(
3474                        ast::RepetitionRange::Bounded(5, 9)
3475                    ),
3476                },
3477                greedy: true,
3478                ast: Box::new(Ast::assertion(ast::Assertion {
3479                    span: span(0..2),
3480                    kind: ast::AssertionKind::WordBoundary,
3481                })),
3482            }))
3483        );
3484
3485        assert_eq!(
3486            parser(r"(?i){0}").parse().unwrap_err(),
3487            TestError {
3488                span: span(4..4),
3489                kind: ast::ErrorKind::RepetitionMissing,
3490            }
3491        );
3492        assert_eq!(
3493            parser(r"(?m){1,1}").parse().unwrap_err(),
3494            TestError {
3495                span: span(4..4),
3496                kind: ast::ErrorKind::RepetitionMissing,
3497            }
3498        );
3499        assert_eq!(
3500            parser(r"a{]}").parse().unwrap_err(),
3501            TestError {
3502                span: span(2..2),
3503                kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
3504            }
3505        );
3506        assert_eq!(
3507            parser(r"a{1,]}").parse().unwrap_err(),
3508            TestError {
3509                span: span(4..4),
3510                kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
3511            }
3512        );
3513        assert_eq!(
3514            parser(r"a{").parse().unwrap_err(),
3515            TestError {
3516                span: span(1..2),
3517                kind: ast::ErrorKind::RepetitionCountUnclosed,
3518            }
3519        );
3520        assert_eq!(
3521            parser(r"a{}").parse().unwrap_err(),
3522            TestError {
3523                span: span(2..2),
3524                kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
3525            }
3526        );
3527        assert_eq!(
3528            parser(r"a{a").parse().unwrap_err(),
3529            TestError {
3530                span: span(2..2),
3531                kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
3532            }
3533        );
3534        assert_eq!(
3535            parser(r"a{9999999999}").parse().unwrap_err(),
3536            TestError {
3537                span: span(2..12),
3538                kind: ast::ErrorKind::DecimalInvalid,
3539            }
3540        );
3541        assert_eq!(
3542            parser(r"a{9").parse().unwrap_err(),
3543            TestError {
3544                span: span(1..3),
3545                kind: ast::ErrorKind::RepetitionCountUnclosed,
3546            }
3547        );
3548        assert_eq!(
3549            parser(r"a{9,a").parse().unwrap_err(),
3550            TestError {
3551                span: span(4..4),
3552                kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
3553            }
3554        );
3555        assert_eq!(
3556            parser(r"a{9,9999999999}").parse().unwrap_err(),
3557            TestError {
3558                span: span(4..14),
3559                kind: ast::ErrorKind::DecimalInvalid,
3560            }
3561        );
3562        assert_eq!(
3563            parser(r"a{9,").parse().unwrap_err(),
3564            TestError {
3565                span: span(1..4),
3566                kind: ast::ErrorKind::RepetitionCountUnclosed,
3567            }
3568        );
3569        assert_eq!(
3570            parser(r"a{9,11").parse().unwrap_err(),
3571            TestError {
3572                span: span(1..6),
3573                kind: ast::ErrorKind::RepetitionCountUnclosed,
3574            }
3575        );
3576        assert_eq!(
3577            parser(r"a{2,1}").parse().unwrap_err(),
3578            TestError {
3579                span: span(1..6),
3580                kind: ast::ErrorKind::RepetitionCountInvalid,
3581            }
3582        );
3583        assert_eq!(
3584            parser(r"{5}").parse().unwrap_err(),
3585            TestError {
3586                span: span(0..0),
3587                kind: ast::ErrorKind::RepetitionMissing,
3588            }
3589        );
3590        assert_eq!(
3591            parser(r"|{5}").parse().unwrap_err(),
3592            TestError {
3593                span: span(1..1),
3594                kind: ast::ErrorKind::RepetitionMissing,
3595            }
3596        );
3597    }
3598
3599    #[test]
3600    fn parse_alternate() {
3601        assert_eq!(
3602            parser(r"a|b").parse(),
3603            Ok(Ast::alternation(ast::Alternation {
3604                span: span(0..3),
3605                asts: vec![lit('a', 0), lit('b', 2)],
3606            }))
3607        );
3608        assert_eq!(
3609            parser(r"(a|b)").parse(),
3610            Ok(group(
3611                0..5,
3612                1,
3613                Ast::alternation(ast::Alternation {
3614                    span: span(1..4),
3615                    asts: vec![lit('a', 1), lit('b', 3)],
3616                })
3617            ))
3618        );
3619
3620        assert_eq!(
3621            parser(r"a|b|c").parse(),
3622            Ok(Ast::alternation(ast::Alternation {
3623                span: span(0..5),
3624                asts: vec![lit('a', 0), lit('b', 2), lit('c', 4)],
3625            }))
3626        );
3627        assert_eq!(
3628            parser(r"ax|by|cz").parse(),
3629            Ok(Ast::alternation(ast::Alternation {
3630                span: span(0..8),
3631                asts: vec![
3632                    concat(0..2, vec![lit('a', 0), lit('x', 1)]),
3633                    concat(3..5, vec![lit('b', 3), lit('y', 4)]),
3634                    concat(6..8, vec![lit('c', 6), lit('z', 7)]),
3635                ],
3636            }))
3637        );
3638        assert_eq!(
3639            parser(r"(ax|by|cz)").parse(),
3640            Ok(group(
3641                0..10,
3642                1,
3643                Ast::alternation(ast::Alternation {
3644                    span: span(1..9),
3645                    asts: vec![
3646                        concat(1..3, vec![lit('a', 1), lit('x', 2)]),
3647                        concat(4..6, vec![lit('b', 4), lit('y', 5)]),
3648                        concat(7..9, vec![lit('c', 7), lit('z', 8)]),
3649                    ],
3650                })
3651            ))
3652        );
3653        assert_eq!(
3654            parser(r"(ax|(by|(cz)))").parse(),
3655            Ok(group(
3656                0..14,
3657                1,
3658                alt(
3659                    1..13,
3660                    vec![
3661                        concat(1..3, vec![lit('a', 1), lit('x', 2)]),
3662                        group(
3663                            4..13,
3664                            2,
3665                            alt(
3666                                5..12,
3667                                vec![
3668                                    concat(
3669                                        5..7,
3670                                        vec![lit('b', 5), lit('y', 6)]
3671                                    ),
3672                                    group(
3673                                        8..12,
3674                                        3,
3675                                        concat(
3676                                            9..11,
3677                                            vec![lit('c', 9), lit('z', 10),]
3678                                        )
3679                                    ),
3680                                ]
3681                            )
3682                        ),
3683                    ]
3684                )
3685            ))
3686        );
3687
3688        assert_eq!(
3689            parser(r"|").parse(),
3690            Ok(alt(
3691                0..1,
3692                vec![Ast::empty(span(0..0)), Ast::empty(span(1..1)),]
3693            ))
3694        );
3695        assert_eq!(
3696            parser(r"||").parse(),
3697            Ok(alt(
3698                0..2,
3699                vec![
3700                    Ast::empty(span(0..0)),
3701                    Ast::empty(span(1..1)),
3702                    Ast::empty(span(2..2)),
3703                ]
3704            ))
3705        );
3706        assert_eq!(
3707            parser(r"a|").parse(),
3708            Ok(alt(0..2, vec![lit('a', 0), Ast::empty(span(2..2)),]))
3709        );
3710        assert_eq!(
3711            parser(r"|a").parse(),
3712            Ok(alt(0..2, vec![Ast::empty(span(0..0)), lit('a', 1),]))
3713        );
3714
3715        assert_eq!(
3716            parser(r"(|)").parse(),
3717            Ok(group(
3718                0..3,
3719                1,
3720                alt(
3721                    1..2,
3722                    vec![Ast::empty(span(1..1)), Ast::empty(span(2..2)),]
3723                )
3724            ))
3725        );
3726        assert_eq!(
3727            parser(r"(a|)").parse(),
3728            Ok(group(
3729                0..4,
3730                1,
3731                alt(1..3, vec![lit('a', 1), Ast::empty(span(3..3)),])
3732            ))
3733        );
3734        assert_eq!(
3735            parser(r"(|a)").parse(),
3736            Ok(group(
3737                0..4,
3738                1,
3739                alt(1..3, vec![Ast::empty(span(1..1)), lit('a', 2),])
3740            ))
3741        );
3742
3743        assert_eq!(
3744            parser(r"a|b)").parse().unwrap_err(),
3745            TestError {
3746                span: span(3..4),
3747                kind: ast::ErrorKind::GroupUnopened,
3748            }
3749        );
3750        assert_eq!(
3751            parser(r"(a|b").parse().unwrap_err(),
3752            TestError {
3753                span: span(0..1),
3754                kind: ast::ErrorKind::GroupUnclosed,
3755            }
3756        );
3757    }
3758
3759    #[test]
3760    fn parse_unsupported_lookaround() {
3761        assert_eq!(
3762            parser(r"(?=a)").parse().unwrap_err(),
3763            TestError {
3764                span: span(0..3),
3765                kind: ast::ErrorKind::UnsupportedLookAround,
3766            }
3767        );
3768        assert_eq!(
3769            parser(r"(?!a)").parse().unwrap_err(),
3770            TestError {
3771                span: span(0..3),
3772                kind: ast::ErrorKind::UnsupportedLookAround,
3773            }
3774        );
3775        assert_eq!(
3776            parser(r"(?<=a)").parse().unwrap_err(),
3777            TestError {
3778                span: span(0..4),
3779                kind: ast::ErrorKind::UnsupportedLookAround,
3780            }
3781        );
3782        assert_eq!(
3783            parser(r"(?<!a)").parse().unwrap_err(),
3784            TestError {
3785                span: span(0..4),
3786                kind: ast::ErrorKind::UnsupportedLookAround,
3787            }
3788        );
3789    }
3790
3791    #[test]
3792    fn parse_group() {
3793        assert_eq!(
3794            parser("(?i)").parse(),
3795            Ok(Ast::flags(ast::SetFlags {
3796                span: span(0..4),
3797                flags: ast::Flags {
3798                    span: span(2..3),
3799                    items: vec![ast::FlagsItem {
3800                        span: span(2..3),
3801                        kind: ast::FlagsItemKind::Flag(
3802                            ast::Flag::CaseInsensitive
3803                        ),
3804                    }],
3805                },
3806            }))
3807        );
3808        assert_eq!(
3809            parser("(?iU)").parse(),
3810            Ok(Ast::flags(ast::SetFlags {
3811                span: span(0..5),
3812                flags: ast::Flags {
3813                    span: span(2..4),
3814                    items: vec![
3815                        ast::FlagsItem {
3816                            span: span(2..3),
3817                            kind: ast::FlagsItemKind::Flag(
3818                                ast::Flag::CaseInsensitive
3819                            ),
3820                        },
3821                        ast::FlagsItem {
3822                            span: span(3..4),
3823                            kind: ast::FlagsItemKind::Flag(
3824                                ast::Flag::SwapGreed
3825                            ),
3826                        },
3827                    ],
3828                },
3829            }))
3830        );
3831        assert_eq!(
3832            parser("(?i-U)").parse(),
3833            Ok(Ast::flags(ast::SetFlags {
3834                span: span(0..6),
3835                flags: ast::Flags {
3836                    span: span(2..5),
3837                    items: vec![
3838                        ast::FlagsItem {
3839                            span: span(2..3),
3840                            kind: ast::FlagsItemKind::Flag(
3841                                ast::Flag::CaseInsensitive
3842                            ),
3843                        },
3844                        ast::FlagsItem {
3845                            span: span(3..4),
3846                            kind: ast::FlagsItemKind::Negation,
3847                        },
3848                        ast::FlagsItem {
3849                            span: span(4..5),
3850                            kind: ast::FlagsItemKind::Flag(
3851                                ast::Flag::SwapGreed
3852                            ),
3853                        },
3854                    ],
3855                },
3856            }))
3857        );
3858
3859        assert_eq!(
3860            parser("()").parse(),
3861            Ok(Ast::group(ast::Group {
3862                span: span(0..2),
3863                kind: ast::GroupKind::CaptureIndex(1),
3864                ast: Box::new(Ast::empty(span(1..1))),
3865            }))
3866        );
3867        assert_eq!(
3868            parser("(a)").parse(),
3869            Ok(Ast::group(ast::Group {
3870                span: span(0..3),
3871                kind: ast::GroupKind::CaptureIndex(1),
3872                ast: Box::new(lit('a', 1)),
3873            }))
3874        );
3875        assert_eq!(
3876            parser("(())").parse(),
3877            Ok(Ast::group(ast::Group {
3878                span: span(0..4),
3879                kind: ast::GroupKind::CaptureIndex(1),
3880                ast: Box::new(Ast::group(ast::Group {
3881                    span: span(1..3),
3882                    kind: ast::GroupKind::CaptureIndex(2),
3883                    ast: Box::new(Ast::empty(span(2..2))),
3884                })),
3885            }))
3886        );
3887
3888        assert_eq!(
3889            parser("(?:a)").parse(),
3890            Ok(Ast::group(ast::Group {
3891                span: span(0..5),
3892                kind: ast::GroupKind::NonCapturing(ast::Flags {
3893                    span: span(2..2),
3894                    items: vec![],
3895                }),
3896                ast: Box::new(lit('a', 3)),
3897            }))
3898        );
3899
3900        assert_eq!(
3901            parser("(?i:a)").parse(),
3902            Ok(Ast::group(ast::Group {
3903                span: span(0..6),
3904                kind: ast::GroupKind::NonCapturing(ast::Flags {
3905                    span: span(2..3),
3906                    items: vec![ast::FlagsItem {
3907                        span: span(2..3),
3908                        kind: ast::FlagsItemKind::Flag(
3909                            ast::Flag::CaseInsensitive
3910                        ),
3911                    },],
3912                }),
3913                ast: Box::new(lit('a', 4)),
3914            }))
3915        );
3916        assert_eq!(
3917            parser("(?i-U:a)").parse(),
3918            Ok(Ast::group(ast::Group {
3919                span: span(0..8),
3920                kind: ast::GroupKind::NonCapturing(ast::Flags {
3921                    span: span(2..5),
3922                    items: vec![
3923                        ast::FlagsItem {
3924                            span: span(2..3),
3925                            kind: ast::FlagsItemKind::Flag(
3926                                ast::Flag::CaseInsensitive
3927                            ),
3928                        },
3929                        ast::FlagsItem {
3930                            span: span(3..4),
3931                            kind: ast::FlagsItemKind::Negation,
3932                        },
3933                        ast::FlagsItem {
3934                            span: span(4..5),
3935                            kind: ast::FlagsItemKind::Flag(
3936                                ast::Flag::SwapGreed
3937                            ),
3938                        },
3939                    ],
3940                }),
3941                ast: Box::new(lit('a', 6)),
3942            }))
3943        );
3944
3945        assert_eq!(
3946            parser("(").parse().unwrap_err(),
3947            TestError {
3948                span: span(0..1),
3949                kind: ast::ErrorKind::GroupUnclosed,
3950            }
3951        );
3952        assert_eq!(
3953            parser("(?").parse().unwrap_err(),
3954            TestError {
3955                span: span(0..1),
3956                kind: ast::ErrorKind::GroupUnclosed,
3957            }
3958        );
3959        assert_eq!(
3960            parser("(?P").parse().unwrap_err(),
3961            TestError {
3962                span: span(2..3),
3963                kind: ast::ErrorKind::FlagUnrecognized,
3964            }
3965        );
3966        assert_eq!(
3967            parser("(?P<").parse().unwrap_err(),
3968            TestError {
3969                span: span(4..4),
3970                kind: ast::ErrorKind::GroupNameUnexpectedEof,
3971            }
3972        );
3973        assert_eq!(
3974            parser("(a").parse().unwrap_err(),
3975            TestError {
3976                span: span(0..1),
3977                kind: ast::ErrorKind::GroupUnclosed,
3978            }
3979        );
3980        assert_eq!(
3981            parser("(()").parse().unwrap_err(),
3982            TestError {
3983                span: span(0..1),
3984                kind: ast::ErrorKind::GroupUnclosed,
3985            }
3986        );
3987        assert_eq!(
3988            parser(")").parse().unwrap_err(),
3989            TestError {
3990                span: span(0..1),
3991                kind: ast::ErrorKind::GroupUnopened,
3992            }
3993        );
3994        assert_eq!(
3995            parser("a)").parse().unwrap_err(),
3996            TestError {
3997                span: span(1..2),
3998                kind: ast::ErrorKind::GroupUnopened,
3999            }
4000        );
4001    }
4002
4003    #[test]
4004    fn parse_capture_name() {
4005        assert_eq!(
4006            parser("(?<a>z)").parse(),
4007            Ok(Ast::group(ast::Group {
4008                span: span(0..7),
4009                kind: ast::GroupKind::CaptureName {
4010                    starts_with_p: false,
4011                    name: ast::CaptureName {
4012                        span: span(3..4),
4013                        name: s("a"),
4014                        index: 1,
4015                    }
4016                },
4017                ast: Box::new(lit('z', 5)),
4018            }))
4019        );
4020        assert_eq!(
4021            parser("(?P<a>z)").parse(),
4022            Ok(Ast::group(ast::Group {
4023                span: span(0..8),
4024                kind: ast::GroupKind::CaptureName {
4025                    starts_with_p: true,
4026                    name: ast::CaptureName {
4027                        span: span(4..5),
4028                        name: s("a"),
4029                        index: 1,
4030                    }
4031                },
4032                ast: Box::new(lit('z', 6)),
4033            }))
4034        );
4035        assert_eq!(
4036            parser("(?P<abc>z)").parse(),
4037            Ok(Ast::group(ast::Group {
4038                span: span(0..10),
4039                kind: ast::GroupKind::CaptureName {
4040                    starts_with_p: true,
4041                    name: ast::CaptureName {
4042                        span: span(4..7),
4043                        name: s("abc"),
4044                        index: 1,
4045                    }
4046                },
4047                ast: Box::new(lit('z', 8)),
4048            }))
4049        );
4050
4051        assert_eq!(
4052            parser("(?P<a_1>z)").parse(),
4053            Ok(Ast::group(ast::Group {
4054                span: span(0..10),
4055                kind: ast::GroupKind::CaptureName {
4056                    starts_with_p: true,
4057                    name: ast::CaptureName {
4058                        span: span(4..7),
4059                        name: s("a_1"),
4060                        index: 1,
4061                    }
4062                },
4063                ast: Box::new(lit('z', 8)),
4064            }))
4065        );
4066
4067        assert_eq!(
4068            parser("(?P<a.1>z)").parse(),
4069            Ok(Ast::group(ast::Group {
4070                span: span(0..10),
4071                kind: ast::GroupKind::CaptureName {
4072                    starts_with_p: true,
4073                    name: ast::CaptureName {
4074                        span: span(4..7),
4075                        name: s("a.1"),
4076                        index: 1,
4077                    }
4078                },
4079                ast: Box::new(lit('z', 8)),
4080            }))
4081        );
4082
4083        assert_eq!(
4084            parser("(?P<a[1]>z)").parse(),
4085            Ok(Ast::group(ast::Group {
4086                span: span(0..11),
4087                kind: ast::GroupKind::CaptureName {
4088                    starts_with_p: true,
4089                    name: ast::CaptureName {
4090                        span: span(4..8),
4091                        name: s("a[1]"),
4092                        index: 1,
4093                    }
4094                },
4095                ast: Box::new(lit('z', 9)),
4096            }))
4097        );
4098
4099        assert_eq!(
4100            parser("(?P<a¾>)").parse(),
4101            Ok(Ast::group(ast::Group {
4102                span: Span::new(
4103                    Position::new(0, 1, 1),
4104                    Position::new(9, 1, 9),
4105                ),
4106                kind: ast::GroupKind::CaptureName {
4107                    starts_with_p: true,
4108                    name: ast::CaptureName {
4109                        span: Span::new(
4110                            Position::new(4, 1, 5),
4111                            Position::new(7, 1, 7),
4112                        ),
4113                        name: s("a¾"),
4114                        index: 1,
4115                    }
4116                },
4117                ast: Box::new(Ast::empty(Span::new(
4118                    Position::new(8, 1, 8),
4119                    Position::new(8, 1, 8),
4120                ))),
4121            }))
4122        );
4123        assert_eq!(
4124            parser("(?P<名字>)").parse(),
4125            Ok(Ast::group(ast::Group {
4126                span: Span::new(
4127                    Position::new(0, 1, 1),
4128                    Position::new(12, 1, 9),
4129                ),
4130                kind: ast::GroupKind::CaptureName {
4131                    starts_with_p: true,
4132                    name: ast::CaptureName {
4133                        span: Span::new(
4134                            Position::new(4, 1, 5),
4135                            Position::new(10, 1, 7),
4136                        ),
4137                        name: s("名字"),
4138                        index: 1,
4139                    }
4140                },
4141                ast: Box::new(Ast::empty(Span::new(
4142                    Position::new(11, 1, 8),
4143                    Position::new(11, 1, 8),
4144                ))),
4145            }))
4146        );
4147
4148        assert_eq!(
4149            parser("(?P<").parse().unwrap_err(),
4150            TestError {
4151                span: span(4..4),
4152                kind: ast::ErrorKind::GroupNameUnexpectedEof,
4153            }
4154        );
4155        assert_eq!(
4156            parser("(?P<>z)").parse().unwrap_err(),
4157            TestError {
4158                span: span(4..4),
4159                kind: ast::ErrorKind::GroupNameEmpty,
4160            }
4161        );
4162        assert_eq!(
4163            parser("(?P<a").parse().unwrap_err(),
4164            TestError {
4165                span: span(5..5),
4166                kind: ast::ErrorKind::GroupNameUnexpectedEof,
4167            }
4168        );
4169        assert_eq!(
4170            parser("(?P<ab").parse().unwrap_err(),
4171            TestError {
4172                span: span(6..6),
4173                kind: ast::ErrorKind::GroupNameUnexpectedEof,
4174            }
4175        );
4176        assert_eq!(
4177            parser("(?P<0a").parse().unwrap_err(),
4178            TestError {
4179                span: span(4..5),
4180                kind: ast::ErrorKind::GroupNameInvalid,
4181            }
4182        );
4183        assert_eq!(
4184            parser("(?P<~").parse().unwrap_err(),
4185            TestError {
4186                span: span(4..5),
4187                kind: ast::ErrorKind::GroupNameInvalid,
4188            }
4189        );
4190        assert_eq!(
4191            parser("(?P<abc~").parse().unwrap_err(),
4192            TestError {
4193                span: span(7..8),
4194                kind: ast::ErrorKind::GroupNameInvalid,
4195            }
4196        );
4197        assert_eq!(
4198            parser("(?P<a>y)(?P<a>z)").parse().unwrap_err(),
4199            TestError {
4200                span: span(12..13),
4201                kind: ast::ErrorKind::GroupNameDuplicate {
4202                    original: span(4..5),
4203                },
4204            }
4205        );
4206        assert_eq!(
4207            parser("(?P<5>)").parse().unwrap_err(),
4208            TestError {
4209                span: span(4..5),
4210                kind: ast::ErrorKind::GroupNameInvalid,
4211            }
4212        );
4213        assert_eq!(
4214            parser("(?P<5a>)").parse().unwrap_err(),
4215            TestError {
4216                span: span(4..5),
4217                kind: ast::ErrorKind::GroupNameInvalid,
4218            }
4219        );
4220        assert_eq!(
4221            parser("(?P<¾>)").parse().unwrap_err(),
4222            TestError {
4223                span: Span::new(
4224                    Position::new(4, 1, 5),
4225                    Position::new(6, 1, 6),
4226                ),
4227                kind: ast::ErrorKind::GroupNameInvalid,
4228            }
4229        );
4230        assert_eq!(
4231            parser("(?P<¾a>)").parse().unwrap_err(),
4232            TestError {
4233                span: Span::new(
4234                    Position::new(4, 1, 5),
4235                    Position::new(6, 1, 6),
4236                ),
4237                kind: ast::ErrorKind::GroupNameInvalid,
4238            }
4239        );
4240        assert_eq!(
4241            parser("(?P<☃>)").parse().unwrap_err(),
4242            TestError {
4243                span: Span::new(
4244                    Position::new(4, 1, 5),
4245                    Position::new(7, 1, 6),
4246                ),
4247                kind: ast::ErrorKind::GroupNameInvalid,
4248            }
4249        );
4250        assert_eq!(
4251            parser("(?P<a☃>)").parse().unwrap_err(),
4252            TestError {
4253                span: Span::new(
4254                    Position::new(5, 1, 6),
4255                    Position::new(8, 1, 7),
4256                ),
4257                kind: ast::ErrorKind::GroupNameInvalid,
4258            }
4259        );
4260    }
4261
4262    #[test]
4263    fn parse_flags() {
4264        assert_eq!(
4265            parser("i:").parse_flags(),
4266            Ok(ast::Flags {
4267                span: span(0..1),
4268                items: vec![ast::FlagsItem {
4269                    span: span(0..1),
4270                    kind: ast::FlagsItemKind::Flag(ast::Flag::CaseInsensitive),
4271                }],
4272            })
4273        );
4274        assert_eq!(
4275            parser("i)").parse_flags(),
4276            Ok(ast::Flags {
4277                span: span(0..1),
4278                items: vec![ast::FlagsItem {
4279                    span: span(0..1),
4280                    kind: ast::FlagsItemKind::Flag(ast::Flag::CaseInsensitive),
4281                }],
4282            })
4283        );
4284
4285        assert_eq!(
4286            parser("isU:").parse_flags(),
4287            Ok(ast::Flags {
4288                span: span(0..3),
4289                items: vec![
4290                    ast::FlagsItem {
4291                        span: span(0..1),
4292                        kind: ast::FlagsItemKind::Flag(
4293                            ast::Flag::CaseInsensitive
4294                        ),
4295                    },
4296                    ast::FlagsItem {
4297                        span: span(1..2),
4298                        kind: ast::FlagsItemKind::Flag(
4299                            ast::Flag::DotMatchesNewLine
4300                        ),
4301                    },
4302                    ast::FlagsItem {
4303                        span: span(2..3),
4304                        kind: ast::FlagsItemKind::Flag(ast::Flag::SwapGreed),
4305                    },
4306                ],
4307            })
4308        );
4309
4310        assert_eq!(
4311            parser("-isU:").parse_flags(),
4312            Ok(ast::Flags {
4313                span: span(0..4),
4314                items: vec![
4315                    ast::FlagsItem {
4316                        span: span(0..1),
4317                        kind: ast::FlagsItemKind::Negation,
4318                    },
4319                    ast::FlagsItem {
4320                        span: span(1..2),
4321                        kind: ast::FlagsItemKind::Flag(
4322                            ast::Flag::CaseInsensitive
4323                        ),
4324                    },
4325                    ast::FlagsItem {
4326                        span: span(2..3),
4327                        kind: ast::FlagsItemKind::Flag(
4328                            ast::Flag::DotMatchesNewLine
4329                        ),
4330                    },
4331                    ast::FlagsItem {
4332                        span: span(3..4),
4333                        kind: ast::FlagsItemKind::Flag(ast::Flag::SwapGreed),
4334                    },
4335                ],
4336            })
4337        );
4338        assert_eq!(
4339            parser("i-sU:").parse_flags(),
4340            Ok(ast::Flags {
4341                span: span(0..4),
4342                items: vec![
4343                    ast::FlagsItem {
4344                        span: span(0..1),
4345                        kind: ast::FlagsItemKind::Flag(
4346                            ast::Flag::CaseInsensitive
4347                        ),
4348                    },
4349                    ast::FlagsItem {
4350                        span: span(1..2),
4351                        kind: ast::FlagsItemKind::Negation,
4352                    },
4353                    ast::FlagsItem {
4354                        span: span(2..3),
4355                        kind: ast::FlagsItemKind::Flag(
4356                            ast::Flag::DotMatchesNewLine
4357                        ),
4358                    },
4359                    ast::FlagsItem {
4360                        span: span(3..4),
4361                        kind: ast::FlagsItemKind::Flag(ast::Flag::SwapGreed),
4362                    },
4363                ],
4364            })
4365        );
4366        assert_eq!(
4367            parser("i-sR:").parse_flags(),
4368            Ok(ast::Flags {
4369                span: span(0..4),
4370                items: vec![
4371                    ast::FlagsItem {
4372                        span: span(0..1),
4373                        kind: ast::FlagsItemKind::Flag(
4374                            ast::Flag::CaseInsensitive
4375                        ),
4376                    },
4377                    ast::FlagsItem {
4378                        span: span(1..2),
4379                        kind: ast::FlagsItemKind::Negation,
4380                    },
4381                    ast::FlagsItem {
4382                        span: span(2..3),
4383                        kind: ast::FlagsItemKind::Flag(
4384                            ast::Flag::DotMatchesNewLine
4385                        ),
4386                    },
4387                    ast::FlagsItem {
4388                        span: span(3..4),
4389                        kind: ast::FlagsItemKind::Flag(ast::Flag::CRLF),
4390                    },
4391                ],
4392            })
4393        );
4394
4395        assert_eq!(
4396            parser("isU").parse_flags().unwrap_err(),
4397            TestError {
4398                span: span(3..3),
4399                kind: ast::ErrorKind::FlagUnexpectedEof,
4400            }
4401        );
4402        assert_eq!(
4403            parser("isUa:").parse_flags().unwrap_err(),
4404            TestError {
4405                span: span(3..4),
4406                kind: ast::ErrorKind::FlagUnrecognized,
4407            }
4408        );
4409        assert_eq!(
4410            parser("isUi:").parse_flags().unwrap_err(),
4411            TestError {
4412                span: span(3..4),
4413                kind: ast::ErrorKind::FlagDuplicate { original: span(0..1) },
4414            }
4415        );
4416        assert_eq!(
4417            parser("i-sU-i:").parse_flags().unwrap_err(),
4418            TestError {
4419                span: span(4..5),
4420                kind: ast::ErrorKind::FlagRepeatedNegation {
4421                    original: span(1..2),
4422                },
4423            }
4424        );
4425        assert_eq!(
4426            parser("-)").parse_flags().unwrap_err(),
4427            TestError {
4428                span: span(0..1),
4429                kind: ast::ErrorKind::FlagDanglingNegation,
4430            }
4431        );
4432        assert_eq!(
4433            parser("i-)").parse_flags().unwrap_err(),
4434            TestError {
4435                span: span(1..2),
4436                kind: ast::ErrorKind::FlagDanglingNegation,
4437            }
4438        );
4439        assert_eq!(
4440            parser("iU-)").parse_flags().unwrap_err(),
4441            TestError {
4442                span: span(2..3),
4443                kind: ast::ErrorKind::FlagDanglingNegation,
4444            }
4445        );
4446    }
4447
4448    #[test]
4449    fn parse_flag() {
4450        assert_eq!(parser("i").parse_flag(), Ok(ast::Flag::CaseInsensitive));
4451        assert_eq!(parser("m").parse_flag(), Ok(ast::Flag::MultiLine));
4452        assert_eq!(parser("s").parse_flag(), Ok(ast::Flag::DotMatchesNewLine));
4453        assert_eq!(parser("U").parse_flag(), Ok(ast::Flag::SwapGreed));
4454        assert_eq!(parser("u").parse_flag(), Ok(ast::Flag::Unicode));
4455        assert_eq!(parser("R").parse_flag(), Ok(ast::Flag::CRLF));
4456        assert_eq!(parser("x").parse_flag(), Ok(ast::Flag::IgnoreWhitespace));
4457
4458        assert_eq!(
4459            parser("a").parse_flag().unwrap_err(),
4460            TestError {
4461                span: span(0..1),
4462                kind: ast::ErrorKind::FlagUnrecognized,
4463            }
4464        );
4465        assert_eq!(
4466            parser("☃").parse_flag().unwrap_err(),
4467            TestError {
4468                span: span_range("☃", 0..3),
4469                kind: ast::ErrorKind::FlagUnrecognized,
4470            }
4471        );
4472    }
4473
4474    #[test]
4475    fn parse_primitive_non_escape() {
4476        assert_eq!(
4477            parser(r".").parse_primitive(),
4478            Ok(Primitive::Dot(span(0..1)))
4479        );
4480        assert_eq!(
4481            parser(r"^").parse_primitive(),
4482            Ok(Primitive::Assertion(ast::Assertion {
4483                span: span(0..1),
4484                kind: ast::AssertionKind::StartLine,
4485            }))
4486        );
4487        assert_eq!(
4488            parser(r"$").parse_primitive(),
4489            Ok(Primitive::Assertion(ast::Assertion {
4490                span: span(0..1),
4491                kind: ast::AssertionKind::EndLine,
4492            }))
4493        );
4494
4495        assert_eq!(
4496            parser(r"a").parse_primitive(),
4497            Ok(Primitive::Literal(ast::Literal {
4498                span: span(0..1),
4499                kind: ast::LiteralKind::Verbatim,
4500                c: 'a',
4501            }))
4502        );
4503        assert_eq!(
4504            parser(r"|").parse_primitive(),
4505            Ok(Primitive::Literal(ast::Literal {
4506                span: span(0..1),
4507                kind: ast::LiteralKind::Verbatim,
4508                c: '|',
4509            }))
4510        );
4511        assert_eq!(
4512            parser(r"☃").parse_primitive(),
4513            Ok(Primitive::Literal(ast::Literal {
4514                span: span_range("☃", 0..3),
4515                kind: ast::LiteralKind::Verbatim,
4516                c: '☃',
4517            }))
4518        );
4519    }
4520
4521    #[test]
4522    fn parse_escape() {
4523        assert_eq!(
4524            parser(r"\|").parse_primitive(),
4525            Ok(Primitive::Literal(ast::Literal {
4526                span: span(0..2),
4527                kind: ast::LiteralKind::Meta,
4528                c: '|',
4529            }))
4530        );
4531        let specials = &[
4532            (r"\a", '\x07', ast::SpecialLiteralKind::Bell),
4533            (r"\f", '\x0C', ast::SpecialLiteralKind::FormFeed),
4534            (r"\t", '\t', ast::SpecialLiteralKind::Tab),
4535            (r"\n", '\n', ast::SpecialLiteralKind::LineFeed),
4536            (r"\r", '\r', ast::SpecialLiteralKind::CarriageReturn),
4537            (r"\v", '\x0B', ast::SpecialLiteralKind::VerticalTab),
4538        ];
4539        for &(pat, c, ref kind) in specials {
4540            assert_eq!(
4541                parser(pat).parse_primitive(),
4542                Ok(Primitive::Literal(ast::Literal {
4543                    span: span(0..2),
4544                    kind: ast::LiteralKind::Special(kind.clone()),
4545                    c,
4546                }))
4547            );
4548        }
4549        assert_eq!(
4550            parser(r"\A").parse_primitive(),
4551            Ok(Primitive::Assertion(ast::Assertion {
4552                span: span(0..2),
4553                kind: ast::AssertionKind::StartText,
4554            }))
4555        );
4556        assert_eq!(
4557            parser(r"\z").parse_primitive(),
4558            Ok(Primitive::Assertion(ast::Assertion {
4559                span: span(0..2),
4560                kind: ast::AssertionKind::EndText,
4561            }))
4562        );
4563        assert_eq!(
4564            parser(r"\b").parse_primitive(),
4565            Ok(Primitive::Assertion(ast::Assertion {
4566                span: span(0..2),
4567                kind: ast::AssertionKind::WordBoundary,
4568            }))
4569        );
4570        assert_eq!(
4571            parser(r"\b{start}").parse_primitive(),
4572            Ok(Primitive::Assertion(ast::Assertion {
4573                span: span(0..9),
4574                kind: ast::AssertionKind::WordBoundaryStart,
4575            }))
4576        );
4577        assert_eq!(
4578            parser(r"\b{end}").parse_primitive(),
4579            Ok(Primitive::Assertion(ast::Assertion {
4580                span: span(0..7),
4581                kind: ast::AssertionKind::WordBoundaryEnd,
4582            }))
4583        );
4584        assert_eq!(
4585            parser(r"\b{start-half}").parse_primitive(),
4586            Ok(Primitive::Assertion(ast::Assertion {
4587                span: span(0..14),
4588                kind: ast::AssertionKind::WordBoundaryStartHalf,
4589            }))
4590        );
4591        assert_eq!(
4592            parser(r"\b{end-half}").parse_primitive(),
4593            Ok(Primitive::Assertion(ast::Assertion {
4594                span: span(0..12),
4595                kind: ast::AssertionKind::WordBoundaryEndHalf,
4596            }))
4597        );
4598        assert_eq!(
4599            parser(r"\<").parse_primitive(),
4600            Ok(Primitive::Assertion(ast::Assertion {
4601                span: span(0..2),
4602                kind: ast::AssertionKind::WordBoundaryStartAngle,
4603            }))
4604        );
4605        assert_eq!(
4606            parser(r"\>").parse_primitive(),
4607            Ok(Primitive::Assertion(ast::Assertion {
4608                span: span(0..2),
4609                kind: ast::AssertionKind::WordBoundaryEndAngle,
4610            }))
4611        );
4612        assert_eq!(
4613            parser(r"\B").parse_primitive(),
4614            Ok(Primitive::Assertion(ast::Assertion {
4615                span: span(0..2),
4616                kind: ast::AssertionKind::NotWordBoundary,
4617            }))
4618        );
4619
4620        // We also support superfluous escapes in most cases now too.
4621        for c in ['!', '@', '%', '"', '\'', '/', ' '] {
4622            let pat = format!(r"\{c}");
4623            assert_eq!(
4624                parser(&pat).parse_primitive(),
4625                Ok(Primitive::Literal(ast::Literal {
4626                    span: span(0..2),
4627                    kind: ast::LiteralKind::Superfluous,
4628                    c,
4629                }))
4630            );
4631        }
4632
4633        // Some superfluous escapes, namely [0-9A-Za-z], are still banned. This
4634        // gives flexibility for future evolution.
4635        assert_eq!(
4636            parser(r"\e").parse_escape().unwrap_err(),
4637            TestError {
4638                span: span(0..2),
4639                kind: ast::ErrorKind::EscapeUnrecognized,
4640            }
4641        );
4642        assert_eq!(
4643            parser(r"\y").parse_escape().unwrap_err(),
4644            TestError {
4645                span: span(0..2),
4646                kind: ast::ErrorKind::EscapeUnrecognized,
4647            }
4648        );
4649
4650        // Starting a special word boundary without any non-whitespace chars
4651        // after the brace makes it ambiguous whether the user meant to write
4652        // a counted repetition (probably not?) or an actual special word
4653        // boundary assertion.
4654        assert_eq!(
4655            parser(r"\b{").parse_escape().unwrap_err(),
4656            TestError {
4657                span: span(0..3),
4658                kind: ast::ErrorKind::SpecialWordOrRepetitionUnexpectedEof,
4659            }
4660        );
4661        assert_eq!(
4662            parser_ignore_whitespace(r"\b{ ").parse_escape().unwrap_err(),
4663            TestError {
4664                span: span(0..4),
4665                kind: ast::ErrorKind::SpecialWordOrRepetitionUnexpectedEof,
4666            }
4667        );
4668        // When 'x' is not enabled, the space is seen as a non-[-A-Za-z] char,
4669        // and thus causes the parser to treat it as a counted repetition.
4670        assert_eq!(
4671            parser(r"\b{ ").parse().unwrap_err(),
4672            TestError {
4673                span: span(2..4),
4674                kind: ast::ErrorKind::RepetitionCountUnclosed,
4675            }
4676        );
4677        // In this case, we got some valid chars that makes it look like the
4678        // user is writing one of the special word boundary assertions, but
4679        // we forget to close the brace.
4680        assert_eq!(
4681            parser(r"\b{foo").parse_escape().unwrap_err(),
4682            TestError {
4683                span: span(2..6),
4684                kind: ast::ErrorKind::SpecialWordBoundaryUnclosed,
4685            }
4686        );
4687        // We get the same error as above, except it is provoked by seeing a
4688        // char that we know is invalid before seeing a closing brace.
4689        assert_eq!(
4690            parser(r"\b{foo!}").parse_escape().unwrap_err(),
4691            TestError {
4692                span: span(2..6),
4693                kind: ast::ErrorKind::SpecialWordBoundaryUnclosed,
4694            }
4695        );
4696        // And this one occurs when, syntactically, everything looks okay, but
4697        // we don't use a valid spelling of a word boundary assertion.
4698        assert_eq!(
4699            parser(r"\b{foo}").parse_escape().unwrap_err(),
4700            TestError {
4701                span: span(3..6),
4702                kind: ast::ErrorKind::SpecialWordBoundaryUnrecognized,
4703            }
4704        );
4705
4706        // An unfinished escape is illegal.
4707        assert_eq!(
4708            parser(r"\").parse_escape().unwrap_err(),
4709            TestError {
4710                span: span(0..1),
4711                kind: ast::ErrorKind::EscapeUnexpectedEof,
4712            }
4713        );
4714    }
4715
4716    #[test]
4717    fn parse_unsupported_backreference() {
4718        assert_eq!(
4719            parser(r"\0").parse_escape().unwrap_err(),
4720            TestError {
4721                span: span(0..2),
4722                kind: ast::ErrorKind::UnsupportedBackreference,
4723            }
4724        );
4725        assert_eq!(
4726            parser(r"\9").parse_escape().unwrap_err(),
4727            TestError {
4728                span: span(0..2),
4729                kind: ast::ErrorKind::UnsupportedBackreference,
4730            }
4731        );
4732    }
4733
4734    #[test]
4735    fn parse_octal() {
4736        for i in 0..511 {
4737            let pat = format!(r"\{i:o}");
4738            assert_eq!(
4739                parser_octal(&pat).parse_escape(),
4740                Ok(Primitive::Literal(ast::Literal {
4741                    span: span(0..pat.len()),
4742                    kind: ast::LiteralKind::Octal,
4743                    c: char::from_u32(i).unwrap(),
4744                }))
4745            );
4746        }
4747        assert_eq!(
4748            parser_octal(r"\778").parse_escape(),
4749            Ok(Primitive::Literal(ast::Literal {
4750                span: span(0..3),
4751                kind: ast::LiteralKind::Octal,
4752                c: '?',
4753            }))
4754        );
4755        assert_eq!(
4756            parser_octal(r"\7777").parse_escape(),
4757            Ok(Primitive::Literal(ast::Literal {
4758                span: span(0..4),
4759                kind: ast::LiteralKind::Octal,
4760                c: '\u{01FF}',
4761            }))
4762        );
4763        assert_eq!(
4764            parser_octal(r"\778").parse(),
4765            Ok(Ast::concat(ast::Concat {
4766                span: span(0..4),
4767                asts: vec![
4768                    Ast::literal(ast::Literal {
4769                        span: span(0..3),
4770                        kind: ast::LiteralKind::Octal,
4771                        c: '?',
4772                    }),
4773                    Ast::literal(ast::Literal {
4774                        span: span(3..4),
4775                        kind: ast::LiteralKind::Verbatim,
4776                        c: '8',
4777                    }),
4778                ],
4779            }))
4780        );
4781        assert_eq!(
4782            parser_octal(r"\7777").parse(),
4783            Ok(Ast::concat(ast::Concat {
4784                span: span(0..5),
4785                asts: vec![
4786                    Ast::literal(ast::Literal {
4787                        span: span(0..4),
4788                        kind: ast::LiteralKind::Octal,
4789                        c: '\u{01FF}',
4790                    }),
4791                    Ast::literal(ast::Literal {
4792                        span: span(4..5),
4793                        kind: ast::LiteralKind::Verbatim,
4794                        c: '7',
4795                    }),
4796                ],
4797            }))
4798        );
4799
4800        assert_eq!(
4801            parser_octal(r"\8").parse_escape().unwrap_err(),
4802            TestError {
4803                span: span(0..2),
4804                kind: ast::ErrorKind::EscapeUnrecognized,
4805            }
4806        );
4807    }
4808
4809    #[test]
4810    fn parse_hex_two() {
4811        for i in 0..256 {
4812            let pat = format!(r"\x{i:02x}");
4813            assert_eq!(
4814                parser(&pat).parse_escape(),
4815                Ok(Primitive::Literal(ast::Literal {
4816                    span: span(0..pat.len()),
4817                    kind: ast::LiteralKind::HexFixed(ast::HexLiteralKind::X),
4818                    c: char::from_u32(i).unwrap(),
4819                }))
4820            );
4821        }
4822
4823        assert_eq!(
4824            parser(r"\xF").parse_escape().unwrap_err(),
4825            TestError {
4826                span: span(3..3),
4827                kind: ast::ErrorKind::EscapeUnexpectedEof,
4828            }
4829        );
4830        assert_eq!(
4831            parser(r"\xG").parse_escape().unwrap_err(),
4832            TestError {
4833                span: span(2..3),
4834                kind: ast::ErrorKind::EscapeHexInvalidDigit,
4835            }
4836        );
4837        assert_eq!(
4838            parser(r"\xFG").parse_escape().unwrap_err(),
4839            TestError {
4840                span: span(3..4),
4841                kind: ast::ErrorKind::EscapeHexInvalidDigit,
4842            }
4843        );
4844    }
4845
4846    #[test]
4847    fn parse_hex_four() {
4848        for i in 0..65536 {
4849            let c = match char::from_u32(i) {
4850                None => continue,
4851                Some(c) => c,
4852            };
4853            let pat = format!(r"\u{i:04x}");
4854            assert_eq!(
4855                parser(&pat).parse_escape(),
4856                Ok(Primitive::Literal(ast::Literal {
4857                    span: span(0..pat.len()),
4858                    kind: ast::LiteralKind::HexFixed(
4859                        ast::HexLiteralKind::UnicodeShort
4860                    ),
4861                    c,
4862                }))
4863            );
4864        }
4865
4866        assert_eq!(
4867            parser(r"\uF").parse_escape().unwrap_err(),
4868            TestError {
4869                span: span(3..3),
4870                kind: ast::ErrorKind::EscapeUnexpectedEof,
4871            }
4872        );
4873        assert_eq!(
4874            parser(r"\uG").parse_escape().unwrap_err(),
4875            TestError {
4876                span: span(2..3),
4877                kind: ast::ErrorKind::EscapeHexInvalidDigit,
4878            }
4879        );
4880        assert_eq!(
4881            parser(r"\uFG").parse_escape().unwrap_err(),
4882            TestError {
4883                span: span(3..4),
4884                kind: ast::ErrorKind::EscapeHexInvalidDigit,
4885            }
4886        );
4887        assert_eq!(
4888            parser(r"\uFFG").parse_escape().unwrap_err(),
4889            TestError {
4890                span: span(4..5),
4891                kind: ast::ErrorKind::EscapeHexInvalidDigit,
4892            }
4893        );
4894        assert_eq!(
4895            parser(r"\uFFFG").parse_escape().unwrap_err(),
4896            TestError {
4897                span: span(5..6),
4898                kind: ast::ErrorKind::EscapeHexInvalidDigit,
4899            }
4900        );
4901        assert_eq!(
4902            parser(r"\uD800").parse_escape().unwrap_err(),
4903            TestError {
4904                span: span(2..6),
4905                kind: ast::ErrorKind::EscapeHexInvalid,
4906            }
4907        );
4908    }
4909
4910    #[test]
4911    fn parse_hex_eight() {
4912        for i in 0..65536 {
4913            let c = match char::from_u32(i) {
4914                None => continue,
4915                Some(c) => c,
4916            };
4917            let pat = format!(r"\U{i:08x}");
4918            assert_eq!(
4919                parser(&pat).parse_escape(),
4920                Ok(Primitive::Literal(ast::Literal {
4921                    span: span(0..pat.len()),
4922                    kind: ast::LiteralKind::HexFixed(
4923                        ast::HexLiteralKind::UnicodeLong
4924                    ),
4925                    c,
4926                }))
4927            );
4928        }
4929
4930        assert_eq!(
4931            parser(r"\UF").parse_escape().unwrap_err(),
4932            TestError {
4933                span: span(3..3),
4934                kind: ast::ErrorKind::EscapeUnexpectedEof,
4935            }
4936        );
4937        assert_eq!(
4938            parser(r"\UG").parse_escape().unwrap_err(),
4939            TestError {
4940                span: span(2..3),
4941                kind: ast::ErrorKind::EscapeHexInvalidDigit,
4942            }
4943        );
4944        assert_eq!(
4945            parser(r"\UFG").parse_escape().unwrap_err(),
4946            TestError {
4947                span: span(3..4),
4948                kind: ast::ErrorKind::EscapeHexInvalidDigit,
4949            }
4950        );
4951        assert_eq!(
4952            parser(r"\UFFG").parse_escape().unwrap_err(),
4953            TestError {
4954                span: span(4..5),
4955                kind: ast::ErrorKind::EscapeHexInvalidDigit,
4956            }
4957        );
4958        assert_eq!(
4959            parser(r"\UFFFG").parse_escape().unwrap_err(),
4960            TestError {
4961                span: span(5..6),
4962                kind: ast::ErrorKind::EscapeHexInvalidDigit,
4963            }
4964        );
4965        assert_eq!(
4966            parser(r"\UFFFFG").parse_escape().unwrap_err(),
4967            TestError {
4968                span: span(6..7),
4969                kind: ast::ErrorKind::EscapeHexInvalidDigit,
4970            }
4971        );
4972        assert_eq!(
4973            parser(r"\UFFFFFG").parse_escape().unwrap_err(),
4974            TestError {
4975                span: span(7..8),
4976                kind: ast::ErrorKind::EscapeHexInvalidDigit,
4977            }
4978        );
4979        assert_eq!(
4980            parser(r"\UFFFFFFG").parse_escape().unwrap_err(),
4981            TestError {
4982                span: span(8..9),
4983                kind: ast::ErrorKind::EscapeHexInvalidDigit,
4984            }
4985        );
4986        assert_eq!(
4987            parser(r"\UFFFFFFFG").parse_escape().unwrap_err(),
4988            TestError {
4989                span: span(9..10),
4990                kind: ast::ErrorKind::EscapeHexInvalidDigit,
4991            }
4992        );
4993    }
4994
4995    #[test]
4996    fn parse_hex_brace() {
4997        assert_eq!(
4998            parser(r"\u{26c4}").parse_escape(),
4999            Ok(Primitive::Literal(ast::Literal {
5000                span: span(0..8),
5001                kind: ast::LiteralKind::HexBrace(
5002                    ast::HexLiteralKind::UnicodeShort
5003                ),
5004                c: '⛄',
5005            }))
5006        );
5007        assert_eq!(
5008            parser(r"\U{26c4}").parse_escape(),
5009            Ok(Primitive::Literal(ast::Literal {
5010                span: span(0..8),
5011                kind: ast::LiteralKind::HexBrace(
5012                    ast::HexLiteralKind::UnicodeLong
5013                ),
5014                c: '⛄',
5015            }))
5016        );
5017        assert_eq!(
5018            parser(r"\x{26c4}").parse_escape(),
5019            Ok(Primitive::Literal(ast::Literal {
5020                span: span(0..8),
5021                kind: ast::LiteralKind::HexBrace(ast::HexLiteralKind::X),
5022                c: '⛄',
5023            }))
5024        );
5025        assert_eq!(
5026            parser(r"\x{26C4}").parse_escape(),
5027            Ok(Primitive::Literal(ast::Literal {
5028                span: span(0..8),
5029                kind: ast::LiteralKind::HexBrace(ast::HexLiteralKind::X),
5030                c: '⛄',
5031            }))
5032        );
5033        assert_eq!(
5034            parser(r"\x{10fFfF}").parse_escape(),
5035            Ok(Primitive::Literal(ast::Literal {
5036                span: span(0..10),
5037                kind: ast::LiteralKind::HexBrace(ast::HexLiteralKind::X),
5038                c: '\u{10FFFF}',
5039            }))
5040        );
5041
5042        assert_eq!(
5043            parser(r"\x").parse_escape().unwrap_err(),
5044            TestError {
5045                span: span(2..2),
5046                kind: ast::ErrorKind::EscapeUnexpectedEof,
5047            }
5048        );
5049        assert_eq!(
5050            parser(r"\x{").parse_escape().unwrap_err(),
5051            TestError {
5052                span: span(2..3),
5053                kind: ast::ErrorKind::EscapeUnexpectedEof,
5054            }
5055        );
5056        assert_eq!(
5057            parser(r"\x{FF").parse_escape().unwrap_err(),
5058            TestError {
5059                span: span(2..5),
5060                kind: ast::ErrorKind::EscapeUnexpectedEof,
5061            }
5062        );
5063        assert_eq!(
5064            parser(r"\x{}").parse_escape().unwrap_err(),
5065            TestError {
5066                span: span(2..4),
5067                kind: ast::ErrorKind::EscapeHexEmpty,
5068            }
5069        );
5070        assert_eq!(
5071            parser(r"\x{FGF}").parse_escape().unwrap_err(),
5072            TestError {
5073                span: span(4..5),
5074                kind: ast::ErrorKind::EscapeHexInvalidDigit,
5075            }
5076        );
5077        assert_eq!(
5078            parser(r"\x{FFFFFF}").parse_escape().unwrap_err(),
5079            TestError {
5080                span: span(3..9),
5081                kind: ast::ErrorKind::EscapeHexInvalid,
5082            }
5083        );
5084        assert_eq!(
5085            parser(r"\x{D800}").parse_escape().unwrap_err(),
5086            TestError {
5087                span: span(3..7),
5088                kind: ast::ErrorKind::EscapeHexInvalid,
5089            }
5090        );
5091        assert_eq!(
5092            parser(r"\x{FFFFFFFFF}").parse_escape().unwrap_err(),
5093            TestError {
5094                span: span(3..12),
5095                kind: ast::ErrorKind::EscapeHexInvalid,
5096            }
5097        );
5098    }
5099
5100    #[test]
5101    fn parse_decimal() {
5102        assert_eq!(parser("123").parse_decimal(), Ok(123));
5103        assert_eq!(parser("0").parse_decimal(), Ok(0));
5104        assert_eq!(parser("01").parse_decimal(), Ok(1));
5105
5106        assert_eq!(
5107            parser("-1").parse_decimal().unwrap_err(),
5108            TestError { span: span(0..0), kind: ast::ErrorKind::DecimalEmpty }
5109        );
5110        assert_eq!(
5111            parser("").parse_decimal().unwrap_err(),
5112            TestError { span: span(0..0), kind: ast::ErrorKind::DecimalEmpty }
5113        );
5114        assert_eq!(
5115            parser("9999999999").parse_decimal().unwrap_err(),
5116            TestError {
5117                span: span(0..10),
5118                kind: ast::ErrorKind::DecimalInvalid,
5119            }
5120        );
5121    }
5122
5123    #[test]
5124    fn parse_set_class() {
5125        fn union(span: Span, items: Vec<ast::ClassSetItem>) -> ast::ClassSet {
5126            ast::ClassSet::union(ast::ClassSetUnion { span, items })
5127        }
5128
5129        fn intersection(
5130            span: Span,
5131            lhs: ast::ClassSet,
5132            rhs: ast::ClassSet,
5133        ) -> ast::ClassSet {
5134            ast::ClassSet::BinaryOp(ast::ClassSetBinaryOp {
5135                span,
5136                kind: ast::ClassSetBinaryOpKind::Intersection,
5137                lhs: Box::new(lhs),
5138                rhs: Box::new(rhs),
5139            })
5140        }
5141
5142        fn difference(
5143            span: Span,
5144            lhs: ast::ClassSet,
5145            rhs: ast::ClassSet,
5146        ) -> ast::ClassSet {
5147            ast::ClassSet::BinaryOp(ast::ClassSetBinaryOp {
5148                span,
5149                kind: ast::ClassSetBinaryOpKind::Difference,
5150                lhs: Box::new(lhs),
5151                rhs: Box::new(rhs),
5152            })
5153        }
5154
5155        fn symdifference(
5156            span: Span,
5157            lhs: ast::ClassSet,
5158            rhs: ast::ClassSet,
5159        ) -> ast::ClassSet {
5160            ast::ClassSet::BinaryOp(ast::ClassSetBinaryOp {
5161                span,
5162                kind: ast::ClassSetBinaryOpKind::SymmetricDifference,
5163                lhs: Box::new(lhs),
5164                rhs: Box::new(rhs),
5165            })
5166        }
5167
5168        fn itemset(item: ast::ClassSetItem) -> ast::ClassSet {
5169            ast::ClassSet::Item(item)
5170        }
5171
5172        fn item_ascii(cls: ast::ClassAscii) -> ast::ClassSetItem {
5173            ast::ClassSetItem::Ascii(cls)
5174        }
5175
5176        fn item_unicode(cls: ast::ClassUnicode) -> ast::ClassSetItem {
5177            ast::ClassSetItem::Unicode(cls)
5178        }
5179
5180        fn item_perl(cls: ast::ClassPerl) -> ast::ClassSetItem {
5181            ast::ClassSetItem::Perl(cls)
5182        }
5183
5184        fn item_bracket(cls: ast::ClassBracketed) -> ast::ClassSetItem {
5185            ast::ClassSetItem::Bracketed(Box::new(cls))
5186        }
5187
5188        fn lit(span: Span, c: char) -> ast::ClassSetItem {
5189            ast::ClassSetItem::Literal(ast::Literal {
5190                span,
5191                kind: ast::LiteralKind::Verbatim,
5192                c,
5193            })
5194        }
5195
5196        fn empty(span: Span) -> ast::ClassSetItem {
5197            ast::ClassSetItem::Empty(span)
5198        }
5199
5200        fn range(span: Span, start: char, end: char) -> ast::ClassSetItem {
5201            let pos1 = Position {
5202                offset: span.start.offset + start.len_utf8(),
5203                column: span.start.column + 1,
5204                ..span.start
5205            };
5206            let pos2 = Position {
5207                offset: span.end.offset - end.len_utf8(),
5208                column: span.end.column - 1,
5209                ..span.end
5210            };
5211            ast::ClassSetItem::Range(ast::ClassSetRange {
5212                span,
5213                start: ast::Literal {
5214                    span: Span { end: pos1, ..span },
5215                    kind: ast::LiteralKind::Verbatim,
5216                    c: start,
5217                },
5218                end: ast::Literal {
5219                    span: Span { start: pos2, ..span },
5220                    kind: ast::LiteralKind::Verbatim,
5221                    c: end,
5222                },
5223            })
5224        }
5225
5226        fn alnum(span: Span, negated: bool) -> ast::ClassAscii {
5227            ast::ClassAscii { span, kind: ast::ClassAsciiKind::Alnum, negated }
5228        }
5229
5230        fn lower(span: Span, negated: bool) -> ast::ClassAscii {
5231            ast::ClassAscii { span, kind: ast::ClassAsciiKind::Lower, negated }
5232        }
5233
5234        assert_eq!(
5235            parser("[[:alnum:]]").parse(),
5236            Ok(Ast::class_bracketed(ast::ClassBracketed {
5237                span: span(0..11),
5238                negated: false,
5239                kind: itemset(item_ascii(alnum(span(1..10), false))),
5240            }))
5241        );
5242        assert_eq!(
5243            parser("[[[:alnum:]]]").parse(),
5244            Ok(Ast::class_bracketed(ast::ClassBracketed {
5245                span: span(0..13),
5246                negated: false,
5247                kind: itemset(item_bracket(ast::ClassBracketed {
5248                    span: span(1..12),
5249                    negated: false,
5250                    kind: itemset(item_ascii(alnum(span(2..11), false))),
5251                })),
5252            }))
5253        );
5254        assert_eq!(
5255            parser("[[:alnum:]&&[:lower:]]").parse(),
5256            Ok(Ast::class_bracketed(ast::ClassBracketed {
5257                span: span(0..22),
5258                negated: false,
5259                kind: intersection(
5260                    span(1..21),
5261                    itemset(item_ascii(alnum(span(1..10), false))),
5262                    itemset(item_ascii(lower(span(12..21), false))),
5263                ),
5264            }))
5265        );
5266        assert_eq!(
5267            parser("[[:alnum:]--[:lower:]]").parse(),
5268            Ok(Ast::class_bracketed(ast::ClassBracketed {
5269                span: span(0..22),
5270                negated: false,
5271                kind: difference(
5272                    span(1..21),
5273                    itemset(item_ascii(alnum(span(1..10), false))),
5274                    itemset(item_ascii(lower(span(12..21), false))),
5275                ),
5276            }))
5277        );
5278        assert_eq!(
5279            parser("[[:alnum:]~~[:lower:]]").parse(),
5280            Ok(Ast::class_bracketed(ast::ClassBracketed {
5281                span: span(0..22),
5282                negated: false,
5283                kind: symdifference(
5284                    span(1..21),
5285                    itemset(item_ascii(alnum(span(1..10), false))),
5286                    itemset(item_ascii(lower(span(12..21), false))),
5287                ),
5288            }))
5289        );
5290
5291        assert_eq!(
5292            parser("[a]").parse(),
5293            Ok(Ast::class_bracketed(ast::ClassBracketed {
5294                span: span(0..3),
5295                negated: false,
5296                kind: itemset(lit(span(1..2), 'a')),
5297            }))
5298        );
5299        assert_eq!(
5300            parser(r"[a\]]").parse(),
5301            Ok(Ast::class_bracketed(ast::ClassBracketed {
5302                span: span(0..5),
5303                negated: false,
5304                kind: union(
5305                    span(1..4),
5306                    vec![
5307                        lit(span(1..2), 'a'),
5308                        ast::ClassSetItem::Literal(ast::Literal {
5309                            span: span(2..4),
5310                            kind: ast::LiteralKind::Meta,
5311                            c: ']',
5312                        }),
5313                    ]
5314                ),
5315            }))
5316        );
5317        assert_eq!(
5318            parser(r"[a\-z]").parse(),
5319            Ok(Ast::class_bracketed(ast::ClassBracketed {
5320                span: span(0..6),
5321                negated: false,
5322                kind: union(
5323                    span(1..5),
5324                    vec![
5325                        lit(span(1..2), 'a'),
5326                        ast::ClassSetItem::Literal(ast::Literal {
5327                            span: span(2..4),
5328                            kind: ast::LiteralKind::Meta,
5329                            c: '-',
5330                        }),
5331                        lit(span(4..5), 'z'),
5332                    ]
5333                ),
5334            }))
5335        );
5336        assert_eq!(
5337            parser("[ab]").parse(),
5338            Ok(Ast::class_bracketed(ast::ClassBracketed {
5339                span: span(0..4),
5340                negated: false,
5341                kind: union(
5342                    span(1..3),
5343                    vec![lit(span(1..2), 'a'), lit(span(2..3), 'b'),]
5344                ),
5345            }))
5346        );
5347        assert_eq!(
5348            parser("[a-]").parse(),
5349            Ok(Ast::class_bracketed(ast::ClassBracketed {
5350                span: span(0..4),
5351                negated: false,
5352                kind: union(
5353                    span(1..3),
5354                    vec![lit(span(1..2), 'a'), lit(span(2..3), '-'),]
5355                ),
5356            }))
5357        );
5358        assert_eq!(
5359            parser("[-a]").parse(),
5360            Ok(Ast::class_bracketed(ast::ClassBracketed {
5361                span: span(0..4),
5362                negated: false,
5363                kind: union(
5364                    span(1..3),
5365                    vec![lit(span(1..2), '-'), lit(span(2..3), 'a'),]
5366                ),
5367            }))
5368        );
5369        assert_eq!(
5370            parser(r"[\pL]").parse(),
5371            Ok(Ast::class_bracketed(ast::ClassBracketed {
5372                span: span(0..5),
5373                negated: false,
5374                kind: itemset(item_unicode(ast::ClassUnicode {
5375                    span: span(1..4),
5376                    negated: false,
5377                    kind: ast::ClassUnicodeKind::OneLetter('L'),
5378                })),
5379            }))
5380        );
5381        assert_eq!(
5382            parser(r"[\w]").parse(),
5383            Ok(Ast::class_bracketed(ast::ClassBracketed {
5384                span: span(0..4),
5385                negated: false,
5386                kind: itemset(item_perl(ast::ClassPerl {
5387                    span: span(1..3),
5388                    kind: ast::ClassPerlKind::Word,
5389                    negated: false,
5390                })),
5391            }))
5392        );
5393        assert_eq!(
5394            parser(r"[a\wz]").parse(),
5395            Ok(Ast::class_bracketed(ast::ClassBracketed {
5396                span: span(0..6),
5397                negated: false,
5398                kind: union(
5399                    span(1..5),
5400                    vec![
5401                        lit(span(1..2), 'a'),
5402                        item_perl(ast::ClassPerl {
5403                            span: span(2..4),
5404                            kind: ast::ClassPerlKind::Word,
5405                            negated: false,
5406                        }),
5407                        lit(span(4..5), 'z'),
5408                    ]
5409                ),
5410            }))
5411        );
5412
5413        assert_eq!(
5414            parser("[a-z]").parse(),
5415            Ok(Ast::class_bracketed(ast::ClassBracketed {
5416                span: span(0..5),
5417                negated: false,
5418                kind: itemset(range(span(1..4), 'a', 'z')),
5419            }))
5420        );
5421        assert_eq!(
5422            parser("[a-cx-z]").parse(),
5423            Ok(Ast::class_bracketed(ast::ClassBracketed {
5424                span: span(0..8),
5425                negated: false,
5426                kind: union(
5427                    span(1..7),
5428                    vec![
5429                        range(span(1..4), 'a', 'c'),
5430                        range(span(4..7), 'x', 'z'),
5431                    ]
5432                ),
5433            }))
5434        );
5435        assert_eq!(
5436            parser(r"[\w&&a-cx-z]").parse(),
5437            Ok(Ast::class_bracketed(ast::ClassBracketed {
5438                span: span(0..12),
5439                negated: false,
5440                kind: intersection(
5441                    span(1..11),
5442                    itemset(item_perl(ast::ClassPerl {
5443                        span: span(1..3),
5444                        kind: ast::ClassPerlKind::Word,
5445                        negated: false,
5446                    })),
5447                    union(
5448                        span(5..11),
5449                        vec![
5450                            range(span(5..8), 'a', 'c'),
5451                            range(span(8..11), 'x', 'z'),
5452                        ]
5453                    ),
5454                ),
5455            }))
5456        );
5457        assert_eq!(
5458            parser(r"[a-cx-z&&\w]").parse(),
5459            Ok(Ast::class_bracketed(ast::ClassBracketed {
5460                span: span(0..12),
5461                negated: false,
5462                kind: intersection(
5463                    span(1..11),
5464                    union(
5465                        span(1..7),
5466                        vec![
5467                            range(span(1..4), 'a', 'c'),
5468                            range(span(4..7), 'x', 'z'),
5469                        ]
5470                    ),
5471                    itemset(item_perl(ast::ClassPerl {
5472                        span: span(9..11),
5473                        kind: ast::ClassPerlKind::Word,
5474                        negated: false,
5475                    })),
5476                ),
5477            }))
5478        );
5479        assert_eq!(
5480            parser(r"[a--b--c]").parse(),
5481            Ok(Ast::class_bracketed(ast::ClassBracketed {
5482                span: span(0..9),
5483                negated: false,
5484                kind: difference(
5485                    span(1..8),
5486                    difference(
5487                        span(1..5),
5488                        itemset(lit(span(1..2), 'a')),
5489                        itemset(lit(span(4..5), 'b')),
5490                    ),
5491                    itemset(lit(span(7..8), 'c')),
5492                ),
5493            }))
5494        );
5495        assert_eq!(
5496            parser(r"[a~~b~~c]").parse(),
5497            Ok(Ast::class_bracketed(ast::ClassBracketed {
5498                span: span(0..9),
5499                negated: false,
5500                kind: symdifference(
5501                    span(1..8),
5502                    symdifference(
5503                        span(1..5),
5504                        itemset(lit(span(1..2), 'a')),
5505                        itemset(lit(span(4..5), 'b')),
5506                    ),
5507                    itemset(lit(span(7..8), 'c')),
5508                ),
5509            }))
5510        );
5511        assert_eq!(
5512            parser(r"[\^&&^]").parse(),
5513            Ok(Ast::class_bracketed(ast::ClassBracketed {
5514                span: span(0..7),
5515                negated: false,
5516                kind: intersection(
5517                    span(1..6),
5518                    itemset(ast::ClassSetItem::Literal(ast::Literal {
5519                        span: span(1..3),
5520                        kind: ast::LiteralKind::Meta,
5521                        c: '^',
5522                    })),
5523                    itemset(lit(span(5..6), '^')),
5524                ),
5525            }))
5526        );
5527        assert_eq!(
5528            parser(r"[\&&&&]").parse(),
5529            Ok(Ast::class_bracketed(ast::ClassBracketed {
5530                span: span(0..7),
5531                negated: false,
5532                kind: intersection(
5533                    span(1..6),
5534                    itemset(ast::ClassSetItem::Literal(ast::Literal {
5535                        span: span(1..3),
5536                        kind: ast::LiteralKind::Meta,
5537                        c: '&',
5538                    })),
5539                    itemset(lit(span(5..6), '&')),
5540                ),
5541            }))
5542        );
5543        assert_eq!(
5544            parser(r"[&&&&]").parse(),
5545            Ok(Ast::class_bracketed(ast::ClassBracketed {
5546                span: span(0..6),
5547                negated: false,
5548                kind: intersection(
5549                    span(1..5),
5550                    intersection(
5551                        span(1..3),
5552                        itemset(empty(span(1..1))),
5553                        itemset(empty(span(3..3))),
5554                    ),
5555                    itemset(empty(span(5..5))),
5556                ),
5557            }))
5558        );
5559
5560        let pat = "[☃-⛄]";
5561        assert_eq!(
5562            parser(pat).parse(),
5563            Ok(Ast::class_bracketed(ast::ClassBracketed {
5564                span: span_range(pat, 0..9),
5565                negated: false,
5566                kind: itemset(ast::ClassSetItem::Range(ast::ClassSetRange {
5567                    span: span_range(pat, 1..8),
5568                    start: ast::Literal {
5569                        span: span_range(pat, 1..4),
5570                        kind: ast::LiteralKind::Verbatim,
5571                        c: '☃',
5572                    },
5573                    end: ast::Literal {
5574                        span: span_range(pat, 5..8),
5575                        kind: ast::LiteralKind::Verbatim,
5576                        c: '⛄',
5577                    },
5578                })),
5579            }))
5580        );
5581
5582        assert_eq!(
5583            parser(r"[]]").parse(),
5584            Ok(Ast::class_bracketed(ast::ClassBracketed {
5585                span: span(0..3),
5586                negated: false,
5587                kind: itemset(lit(span(1..2), ']')),
5588            }))
5589        );
5590        assert_eq!(
5591            parser(r"[]\[]").parse(),
5592            Ok(Ast::class_bracketed(ast::ClassBracketed {
5593                span: span(0..5),
5594                negated: false,
5595                kind: union(
5596                    span(1..4),
5597                    vec![
5598                        lit(span(1..2), ']'),
5599                        ast::ClassSetItem::Literal(ast::Literal {
5600                            span: span(2..4),
5601                            kind: ast::LiteralKind::Meta,
5602                            c: '[',
5603                        }),
5604                    ]
5605                ),
5606            }))
5607        );
5608        assert_eq!(
5609            parser(r"[\[]]").parse(),
5610            Ok(concat(
5611                0..5,
5612                vec![
5613                    Ast::class_bracketed(ast::ClassBracketed {
5614                        span: span(0..4),
5615                        negated: false,
5616                        kind: itemset(ast::ClassSetItem::Literal(
5617                            ast::Literal {
5618                                span: span(1..3),
5619                                kind: ast::LiteralKind::Meta,
5620                                c: '[',
5621                            }
5622                        )),
5623                    }),
5624                    Ast::literal(ast::Literal {
5625                        span: span(4..5),
5626                        kind: ast::LiteralKind::Verbatim,
5627                        c: ']',
5628                    }),
5629                ]
5630            ))
5631        );
5632
5633        assert_eq!(
5634            parser("[").parse().unwrap_err(),
5635            TestError {
5636                span: span(0..1),
5637                kind: ast::ErrorKind::ClassUnclosed,
5638            }
5639        );
5640        assert_eq!(
5641            parser("[[").parse().unwrap_err(),
5642            TestError {
5643                span: span(1..2),
5644                kind: ast::ErrorKind::ClassUnclosed,
5645            }
5646        );
5647        assert_eq!(
5648            parser("[[-]").parse().unwrap_err(),
5649            TestError {
5650                span: span(0..1),
5651                kind: ast::ErrorKind::ClassUnclosed,
5652            }
5653        );
5654        assert_eq!(
5655            parser("[[[:alnum:]").parse().unwrap_err(),
5656            TestError {
5657                span: span(1..2),
5658                kind: ast::ErrorKind::ClassUnclosed,
5659            }
5660        );
5661        assert_eq!(
5662            parser(r"[\b]").parse().unwrap_err(),
5663            TestError {
5664                span: span(1..3),
5665                kind: ast::ErrorKind::ClassEscapeInvalid,
5666            }
5667        );
5668        assert_eq!(
5669            parser(r"[\w-a]").parse().unwrap_err(),
5670            TestError {
5671                span: span(1..3),
5672                kind: ast::ErrorKind::ClassRangeLiteral,
5673            }
5674        );
5675        assert_eq!(
5676            parser(r"[a-\w]").parse().unwrap_err(),
5677            TestError {
5678                span: span(3..5),
5679                kind: ast::ErrorKind::ClassRangeLiteral,
5680            }
5681        );
5682        assert_eq!(
5683            parser(r"[z-a]").parse().unwrap_err(),
5684            TestError {
5685                span: span(1..4),
5686                kind: ast::ErrorKind::ClassRangeInvalid,
5687            }
5688        );
5689
5690        assert_eq!(
5691            parser_ignore_whitespace("[a ").parse().unwrap_err(),
5692            TestError {
5693                span: span(0..1),
5694                kind: ast::ErrorKind::ClassUnclosed,
5695            }
5696        );
5697        assert_eq!(
5698            parser_ignore_whitespace("[a- ").parse().unwrap_err(),
5699            TestError {
5700                span: span(0..1),
5701                kind: ast::ErrorKind::ClassUnclosed,
5702            }
5703        );
5704    }
5705
5706    #[test]
5707    fn parse_set_class_open() {
5708        assert_eq!(parser("[a]").parse_set_class_open(), {
5709            let set = ast::ClassBracketed {
5710                span: span(0..1),
5711                negated: false,
5712                kind: ast::ClassSet::union(ast::ClassSetUnion {
5713                    span: span(1..1),
5714                    items: vec![],
5715                }),
5716            };
5717            let union = ast::ClassSetUnion { span: span(1..1), items: vec![] };
5718            Ok((set, union))
5719        });
5720        assert_eq!(
5721            parser_ignore_whitespace("[   a]").parse_set_class_open(),
5722            {
5723                let set = ast::ClassBracketed {
5724                    span: span(0..4),
5725                    negated: false,
5726                    kind: ast::ClassSet::union(ast::ClassSetUnion {
5727                        span: span(4..4),
5728                        items: vec![],
5729                    }),
5730                };
5731                let union =
5732                    ast::ClassSetUnion { span: span(4..4), items: vec![] };
5733                Ok((set, union))
5734            }
5735        );
5736        assert_eq!(parser("[^a]").parse_set_class_open(), {
5737            let set = ast::ClassBracketed {
5738                span: span(0..2),
5739                negated: true,
5740                kind: ast::ClassSet::union(ast::ClassSetUnion {
5741                    span: span(2..2),
5742                    items: vec![],
5743                }),
5744            };
5745            let union = ast::ClassSetUnion { span: span(2..2), items: vec![] };
5746            Ok((set, union))
5747        });
5748        assert_eq!(
5749            parser_ignore_whitespace("[ ^ a]").parse_set_class_open(),
5750            {
5751                let set = ast::ClassBracketed {
5752                    span: span(0..4),
5753                    negated: true,
5754                    kind: ast::ClassSet::union(ast::ClassSetUnion {
5755                        span: span(4..4),
5756                        items: vec![],
5757                    }),
5758                };
5759                let union =
5760                    ast::ClassSetUnion { span: span(4..4), items: vec![] };
5761                Ok((set, union))
5762            }
5763        );
5764        assert_eq!(parser("[-a]").parse_set_class_open(), {
5765            let set = ast::ClassBracketed {
5766                span: span(0..2),
5767                negated: false,
5768                kind: ast::ClassSet::union(ast::ClassSetUnion {
5769                    span: span(1..1),
5770                    items: vec![],
5771                }),
5772            };
5773            let union = ast::ClassSetUnion {
5774                span: span(1..2),
5775                items: vec![ast::ClassSetItem::Literal(ast::Literal {
5776                    span: span(1..2),
5777                    kind: ast::LiteralKind::Verbatim,
5778                    c: '-',
5779                })],
5780            };
5781            Ok((set, union))
5782        });
5783        assert_eq!(
5784            parser_ignore_whitespace("[ - a]").parse_set_class_open(),
5785            {
5786                let set = ast::ClassBracketed {
5787                    span: span(0..4),
5788                    negated: false,
5789                    kind: ast::ClassSet::union(ast::ClassSetUnion {
5790                        span: span(2..2),
5791                        items: vec![],
5792                    }),
5793                };
5794                let union = ast::ClassSetUnion {
5795                    span: span(2..3),
5796                    items: vec![ast::ClassSetItem::Literal(ast::Literal {
5797                        span: span(2..3),
5798                        kind: ast::LiteralKind::Verbatim,
5799                        c: '-',
5800                    })],
5801                };
5802                Ok((set, union))
5803            }
5804        );
5805        assert_eq!(parser("[^-a]").parse_set_class_open(), {
5806            let set = ast::ClassBracketed {
5807                span: span(0..3),
5808                negated: true,
5809                kind: ast::ClassSet::union(ast::ClassSetUnion {
5810                    span: span(2..2),
5811                    items: vec![],
5812                }),
5813            };
5814            let union = ast::ClassSetUnion {
5815                span: span(2..3),
5816                items: vec![ast::ClassSetItem::Literal(ast::Literal {
5817                    span: span(2..3),
5818                    kind: ast::LiteralKind::Verbatim,
5819                    c: '-',
5820                })],
5821            };
5822            Ok((set, union))
5823        });
5824        assert_eq!(parser("[--a]").parse_set_class_open(), {
5825            let set = ast::ClassBracketed {
5826                span: span(0..3),
5827                negated: false,
5828                kind: ast::ClassSet::union(ast::ClassSetUnion {
5829                    span: span(1..1),
5830                    items: vec![],
5831                }),
5832            };
5833            let union = ast::ClassSetUnion {
5834                span: span(1..3),
5835                items: vec![
5836                    ast::ClassSetItem::Literal(ast::Literal {
5837                        span: span(1..2),
5838                        kind: ast::LiteralKind::Verbatim,
5839                        c: '-',
5840                    }),
5841                    ast::ClassSetItem::Literal(ast::Literal {
5842                        span: span(2..3),
5843                        kind: ast::LiteralKind::Verbatim,
5844                        c: '-',
5845                    }),
5846                ],
5847            };
5848            Ok((set, union))
5849        });
5850        assert_eq!(parser("[]a]").parse_set_class_open(), {
5851            let set = ast::ClassBracketed {
5852                span: span(0..2),
5853                negated: false,
5854                kind: ast::ClassSet::union(ast::ClassSetUnion {
5855                    span: span(1..1),
5856                    items: vec![],
5857                }),
5858            };
5859            let union = ast::ClassSetUnion {
5860                span: span(1..2),
5861                items: vec![ast::ClassSetItem::Literal(ast::Literal {
5862                    span: span(1..2),
5863                    kind: ast::LiteralKind::Verbatim,
5864                    c: ']',
5865                })],
5866            };
5867            Ok((set, union))
5868        });
5869        assert_eq!(
5870            parser_ignore_whitespace("[ ] a]").parse_set_class_open(),
5871            {
5872                let set = ast::ClassBracketed {
5873                    span: span(0..4),
5874                    negated: false,
5875                    kind: ast::ClassSet::union(ast::ClassSetUnion {
5876                        span: span(2..2),
5877                        items: vec![],
5878                    }),
5879                };
5880                let union = ast::ClassSetUnion {
5881                    span: span(2..3),
5882                    items: vec![ast::ClassSetItem::Literal(ast::Literal {
5883                        span: span(2..3),
5884                        kind: ast::LiteralKind::Verbatim,
5885                        c: ']',
5886                    })],
5887                };
5888                Ok((set, union))
5889            }
5890        );
5891        assert_eq!(parser("[^]a]").parse_set_class_open(), {
5892            let set = ast::ClassBracketed {
5893                span: span(0..3),
5894                negated: true,
5895                kind: ast::ClassSet::union(ast::ClassSetUnion {
5896                    span: span(2..2),
5897                    items: vec![],
5898                }),
5899            };
5900            let union = ast::ClassSetUnion {
5901                span: span(2..3),
5902                items: vec![ast::ClassSetItem::Literal(ast::Literal {
5903                    span: span(2..3),
5904                    kind: ast::LiteralKind::Verbatim,
5905                    c: ']',
5906                })],
5907            };
5908            Ok((set, union))
5909        });
5910        assert_eq!(parser("[-]a]").parse_set_class_open(), {
5911            let set = ast::ClassBracketed {
5912                span: span(0..2),
5913                negated: false,
5914                kind: ast::ClassSet::union(ast::ClassSetUnion {
5915                    span: span(1..1),
5916                    items: vec![],
5917                }),
5918            };
5919            let union = ast::ClassSetUnion {
5920                span: span(1..2),
5921                items: vec![ast::ClassSetItem::Literal(ast::Literal {
5922                    span: span(1..2),
5923                    kind: ast::LiteralKind::Verbatim,
5924                    c: '-',
5925                })],
5926            };
5927            Ok((set, union))
5928        });
5929
5930        assert_eq!(
5931            parser("[").parse_set_class_open().unwrap_err(),
5932            TestError {
5933                span: span(0..1),
5934                kind: ast::ErrorKind::ClassUnclosed,
5935            }
5936        );
5937        assert_eq!(
5938            parser_ignore_whitespace("[    ")
5939                .parse_set_class_open()
5940                .unwrap_err(),
5941            TestError {
5942                span: span(0..5),
5943                kind: ast::ErrorKind::ClassUnclosed,
5944            }
5945        );
5946        assert_eq!(
5947            parser("[^").parse_set_class_open().unwrap_err(),
5948            TestError {
5949                span: span(0..2),
5950                kind: ast::ErrorKind::ClassUnclosed,
5951            }
5952        );
5953        assert_eq!(
5954            parser("[]").parse_set_class_open().unwrap_err(),
5955            TestError {
5956                span: span(0..2),
5957                kind: ast::ErrorKind::ClassUnclosed,
5958            }
5959        );
5960        assert_eq!(
5961            parser("[-").parse_set_class_open().unwrap_err(),
5962            TestError {
5963                span: span(0..0),
5964                kind: ast::ErrorKind::ClassUnclosed,
5965            }
5966        );
5967        assert_eq!(
5968            parser("[--").parse_set_class_open().unwrap_err(),
5969            TestError {
5970                span: span(0..0),
5971                kind: ast::ErrorKind::ClassUnclosed,
5972            }
5973        );
5974
5975        // See: https://github.com/rust-lang/regex/issues/792
5976        assert_eq!(
5977            parser("(?x)[-#]").parse_with_comments().unwrap_err(),
5978            TestError {
5979                span: span(4..4),
5980                kind: ast::ErrorKind::ClassUnclosed,
5981            }
5982        );
5983    }
5984
5985    #[test]
5986    fn maybe_parse_ascii_class() {
5987        assert_eq!(
5988            parser(r"[:alnum:]").maybe_parse_ascii_class(),
5989            Some(ast::ClassAscii {
5990                span: span(0..9),
5991                kind: ast::ClassAsciiKind::Alnum,
5992                negated: false,
5993            })
5994        );
5995        assert_eq!(
5996            parser(r"[:alnum:]A").maybe_parse_ascii_class(),
5997            Some(ast::ClassAscii {
5998                span: span(0..9),
5999                kind: ast::ClassAsciiKind::Alnum,
6000                negated: false,
6001            })
6002        );
6003        assert_eq!(
6004            parser(r"[:^alnum:]").maybe_parse_ascii_class(),
6005            Some(ast::ClassAscii {
6006                span: span(0..10),
6007                kind: ast::ClassAsciiKind::Alnum,
6008                negated: true,
6009            })
6010        );
6011
6012        let p = parser(r"[:");
6013        assert_eq!(p.maybe_parse_ascii_class(), None);
6014        assert_eq!(p.offset(), 0);
6015
6016        let p = parser(r"[:^");
6017        assert_eq!(p.maybe_parse_ascii_class(), None);
6018        assert_eq!(p.offset(), 0);
6019
6020        let p = parser(r"[^:alnum:]");
6021        assert_eq!(p.maybe_parse_ascii_class(), None);
6022        assert_eq!(p.offset(), 0);
6023
6024        let p = parser(r"[:alnnum:]");
6025        assert_eq!(p.maybe_parse_ascii_class(), None);
6026        assert_eq!(p.offset(), 0);
6027
6028        let p = parser(r"[:alnum]");
6029        assert_eq!(p.maybe_parse_ascii_class(), None);
6030        assert_eq!(p.offset(), 0);
6031
6032        let p = parser(r"[:alnum:");
6033        assert_eq!(p.maybe_parse_ascii_class(), None);
6034        assert_eq!(p.offset(), 0);
6035    }
6036
6037    #[test]
6038    fn parse_unicode_class() {
6039        assert_eq!(
6040            parser(r"\pN").parse_escape(),
6041            Ok(Primitive::Unicode(ast::ClassUnicode {
6042                span: span(0..3),
6043                negated: false,
6044                kind: ast::ClassUnicodeKind::OneLetter('N'),
6045            }))
6046        );
6047        assert_eq!(
6048            parser(r"\PN").parse_escape(),
6049            Ok(Primitive::Unicode(ast::ClassUnicode {
6050                span: span(0..3),
6051                negated: true,
6052                kind: ast::ClassUnicodeKind::OneLetter('N'),
6053            }))
6054        );
6055        assert_eq!(
6056            parser(r"\p{N}").parse_escape(),
6057            Ok(Primitive::Unicode(ast::ClassUnicode {
6058                span: span(0..5),
6059                negated: false,
6060                kind: ast::ClassUnicodeKind::Named(s("N")),
6061            }))
6062        );
6063        assert_eq!(
6064            parser(r"\P{N}").parse_escape(),
6065            Ok(Primitive::Unicode(ast::ClassUnicode {
6066                span: span(0..5),
6067                negated: true,
6068                kind: ast::ClassUnicodeKind::Named(s("N")),
6069            }))
6070        );
6071        assert_eq!(
6072            parser(r"\p{Greek}").parse_escape(),
6073            Ok(Primitive::Unicode(ast::ClassUnicode {
6074                span: span(0..9),
6075                negated: false,
6076                kind: ast::ClassUnicodeKind::Named(s("Greek")),
6077            }))
6078        );
6079
6080        assert_eq!(
6081            parser(r"\p{scx:Katakana}").parse_escape(),
6082            Ok(Primitive::Unicode(ast::ClassUnicode {
6083                span: span(0..16),
6084                negated: false,
6085                kind: ast::ClassUnicodeKind::NamedValue {
6086                    op: ast::ClassUnicodeOpKind::Colon,
6087                    name: s("scx"),
6088                    value: s("Katakana"),
6089                },
6090            }))
6091        );
6092        assert_eq!(
6093            parser(r"\p{scx=Katakana}").parse_escape(),
6094            Ok(Primitive::Unicode(ast::ClassUnicode {
6095                span: span(0..16),
6096                negated: false,
6097                kind: ast::ClassUnicodeKind::NamedValue {
6098                    op: ast::ClassUnicodeOpKind::Equal,
6099                    name: s("scx"),
6100                    value: s("Katakana"),
6101                },
6102            }))
6103        );
6104        assert_eq!(
6105            parser(r"\p{scx!=Katakana}").parse_escape(),
6106            Ok(Primitive::Unicode(ast::ClassUnicode {
6107                span: span(0..17),
6108                negated: false,
6109                kind: ast::ClassUnicodeKind::NamedValue {
6110                    op: ast::ClassUnicodeOpKind::NotEqual,
6111                    name: s("scx"),
6112                    value: s("Katakana"),
6113                },
6114            }))
6115        );
6116
6117        assert_eq!(
6118            parser(r"\p{:}").parse_escape(),
6119            Ok(Primitive::Unicode(ast::ClassUnicode {
6120                span: span(0..5),
6121                negated: false,
6122                kind: ast::ClassUnicodeKind::NamedValue {
6123                    op: ast::ClassUnicodeOpKind::Colon,
6124                    name: s(""),
6125                    value: s(""),
6126                },
6127            }))
6128        );
6129        assert_eq!(
6130            parser(r"\p{=}").parse_escape(),
6131            Ok(Primitive::Unicode(ast::ClassUnicode {
6132                span: span(0..5),
6133                negated: false,
6134                kind: ast::ClassUnicodeKind::NamedValue {
6135                    op: ast::ClassUnicodeOpKind::Equal,
6136                    name: s(""),
6137                    value: s(""),
6138                },
6139            }))
6140        );
6141        assert_eq!(
6142            parser(r"\p{!=}").parse_escape(),
6143            Ok(Primitive::Unicode(ast::ClassUnicode {
6144                span: span(0..6),
6145                negated: false,
6146                kind: ast::ClassUnicodeKind::NamedValue {
6147                    op: ast::ClassUnicodeOpKind::NotEqual,
6148                    name: s(""),
6149                    value: s(""),
6150                },
6151            }))
6152        );
6153
6154        assert_eq!(
6155            parser(r"\p").parse_escape().unwrap_err(),
6156            TestError {
6157                span: span(2..2),
6158                kind: ast::ErrorKind::EscapeUnexpectedEof,
6159            }
6160        );
6161        assert_eq!(
6162            parser(r"\p{").parse_escape().unwrap_err(),
6163            TestError {
6164                span: span(3..3),
6165                kind: ast::ErrorKind::EscapeUnexpectedEof,
6166            }
6167        );
6168        assert_eq!(
6169            parser(r"\p{N").parse_escape().unwrap_err(),
6170            TestError {
6171                span: span(4..4),
6172                kind: ast::ErrorKind::EscapeUnexpectedEof,
6173            }
6174        );
6175        assert_eq!(
6176            parser(r"\p{Greek").parse_escape().unwrap_err(),
6177            TestError {
6178                span: span(8..8),
6179                kind: ast::ErrorKind::EscapeUnexpectedEof,
6180            }
6181        );
6182
6183        assert_eq!(
6184            parser(r"\pNz").parse(),
6185            Ok(Ast::concat(ast::Concat {
6186                span: span(0..4),
6187                asts: vec![
6188                    Ast::class_unicode(ast::ClassUnicode {
6189                        span: span(0..3),
6190                        negated: false,
6191                        kind: ast::ClassUnicodeKind::OneLetter('N'),
6192                    }),
6193                    Ast::literal(ast::Literal {
6194                        span: span(3..4),
6195                        kind: ast::LiteralKind::Verbatim,
6196                        c: 'z',
6197                    }),
6198                ],
6199            }))
6200        );
6201        assert_eq!(
6202            parser(r"\p{Greek}z").parse(),
6203            Ok(Ast::concat(ast::Concat {
6204                span: span(0..10),
6205                asts: vec![
6206                    Ast::class_unicode(ast::ClassUnicode {
6207                        span: span(0..9),
6208                        negated: false,
6209                        kind: ast::ClassUnicodeKind::Named(s("Greek")),
6210                    }),
6211                    Ast::literal(ast::Literal {
6212                        span: span(9..10),
6213                        kind: ast::LiteralKind::Verbatim,
6214                        c: 'z',
6215                    }),
6216                ],
6217            }))
6218        );
6219        assert_eq!(
6220            parser(r"\p\{").parse().unwrap_err(),
6221            TestError {
6222                span: span(2..3),
6223                kind: ast::ErrorKind::UnicodeClassInvalid,
6224            }
6225        );
6226        assert_eq!(
6227            parser(r"\P\{").parse().unwrap_err(),
6228            TestError {
6229                span: span(2..3),
6230                kind: ast::ErrorKind::UnicodeClassInvalid,
6231            }
6232        );
6233    }
6234
6235    #[test]
6236    fn parse_perl_class() {
6237        assert_eq!(
6238            parser(r"\d").parse_escape(),
6239            Ok(Primitive::Perl(ast::ClassPerl {
6240                span: span(0..2),
6241                kind: ast::ClassPerlKind::Digit,
6242                negated: false,
6243            }))
6244        );
6245        assert_eq!(
6246            parser(r"\D").parse_escape(),
6247            Ok(Primitive::Perl(ast::ClassPerl {
6248                span: span(0..2),
6249                kind: ast::ClassPerlKind::Digit,
6250                negated: true,
6251            }))
6252        );
6253        assert_eq!(
6254            parser(r"\s").parse_escape(),
6255            Ok(Primitive::Perl(ast::ClassPerl {
6256                span: span(0..2),
6257                kind: ast::ClassPerlKind::Space,
6258                negated: false,
6259            }))
6260        );
6261        assert_eq!(
6262            parser(r"\S").parse_escape(),
6263            Ok(Primitive::Perl(ast::ClassPerl {
6264                span: span(0..2),
6265                kind: ast::ClassPerlKind::Space,
6266                negated: true,
6267            }))
6268        );
6269        assert_eq!(
6270            parser(r"\w").parse_escape(),
6271            Ok(Primitive::Perl(ast::ClassPerl {
6272                span: span(0..2),
6273                kind: ast::ClassPerlKind::Word,
6274                negated: false,
6275            }))
6276        );
6277        assert_eq!(
6278            parser(r"\W").parse_escape(),
6279            Ok(Primitive::Perl(ast::ClassPerl {
6280                span: span(0..2),
6281                kind: ast::ClassPerlKind::Word,
6282                negated: true,
6283            }))
6284        );
6285
6286        assert_eq!(
6287            parser(r"\d").parse(),
6288            Ok(Ast::class_perl(ast::ClassPerl {
6289                span: span(0..2),
6290                kind: ast::ClassPerlKind::Digit,
6291                negated: false,
6292            }))
6293        );
6294        assert_eq!(
6295            parser(r"\dz").parse(),
6296            Ok(Ast::concat(ast::Concat {
6297                span: span(0..3),
6298                asts: vec![
6299                    Ast::class_perl(ast::ClassPerl {
6300                        span: span(0..2),
6301                        kind: ast::ClassPerlKind::Digit,
6302                        negated: false,
6303                    }),
6304                    Ast::literal(ast::Literal {
6305                        span: span(2..3),
6306                        kind: ast::LiteralKind::Verbatim,
6307                        c: 'z',
6308                    }),
6309                ],
6310            }))
6311        );
6312    }
6313
6314    // This tests a bug fix where the nest limit checker wasn't decrementing
6315    // its depth during post-traversal, which causes long regexes to trip
6316    // the default limit too aggressively.
6317    #[test]
6318    fn regression_454_nest_too_big() {
6319        let pattern = r#"
6320        2(?:
6321          [45]\d{3}|
6322          7(?:
6323            1[0-267]|
6324            2[0-289]|
6325            3[0-29]|
6326            4[01]|
6327            5[1-3]|
6328            6[013]|
6329            7[0178]|
6330            91
6331          )|
6332          8(?:
6333            0[125]|
6334            [139][1-6]|
6335            2[0157-9]|
6336            41|
6337            6[1-35]|
6338            7[1-5]|
6339            8[1-8]|
6340            90
6341          )|
6342          9(?:
6343            0[0-2]|
6344            1[0-4]|
6345            2[568]|
6346            3[3-6]|
6347            5[5-7]|
6348            6[0167]|
6349            7[15]|
6350            8[0146-9]
6351          )
6352        )\d{4}
6353        "#;
6354        assert!(parser_nest_limit(pattern, 50).parse().is_ok());
6355    }
6356
6357    // This tests that we treat a trailing `-` in a character class as a
6358    // literal `-` even when whitespace mode is enabled and there is whitespace
6359    // after the trailing `-`.
6360    #[test]
6361    fn regression_455_trailing_dash_ignore_whitespace() {
6362        assert!(parser("(?x)[ / - ]").parse().is_ok());
6363        assert!(parser("(?x)[ a - ]").parse().is_ok());
6364        assert!(parser(
6365            "(?x)[
6366            a
6367            - ]
6368        "
6369        )
6370        .parse()
6371        .is_ok());
6372        assert!(parser(
6373            "(?x)[
6374            a # wat
6375            - ]
6376        "
6377        )
6378        .parse()
6379        .is_ok());
6380
6381        assert!(parser("(?x)[ / -").parse().is_err());
6382        assert!(parser("(?x)[ / - ").parse().is_err());
6383        assert!(parser(
6384            "(?x)[
6385            / -
6386        "
6387        )
6388        .parse()
6389        .is_err());
6390        assert!(parser(
6391            "(?x)[
6392            / - # wat
6393        "
6394        )
6395        .parse()
6396        .is_err());
6397    }
6398}