Skip to main content

regex_syntax/ast/
mod.rs

1/*!
2Defines an abstract syntax for regular expressions.
3*/
4
5use core::cmp::Ordering;
6
7use alloc::{boxed::Box, string::String, vec, vec::Vec};
8
9pub use crate::ast::visitor::{visit, Visitor};
10
11pub mod parse;
12pub mod print;
13mod visitor;
14
15/// An error that occurred while parsing a regular expression into an abstract
16/// syntax tree.
17///
18/// Note that not all ASTs represents a valid regular expression. For example,
19/// an AST is constructed without error for `\p{Quux}`, but `Quux` is not a
20/// valid Unicode property name. That particular error is reported when
21/// translating an AST to the high-level intermediate representation (`HIR`).
22#[derive(Clone, Debug, Eq, PartialEq)]
23#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
24pub struct Error {
25    /// The kind of error.
26    kind: ErrorKind,
27    /// The original pattern that the parser generated the error from. Every
28    /// span in an error is a valid range into this string.
29    pattern: String,
30    /// The span of this error.
31    span: Span,
32}
33
34impl Error {
35    /// Return the type of this error.
36    pub fn kind(&self) -> &ErrorKind {
37        &self.kind
38    }
39
40    /// The original pattern string in which this error occurred.
41    ///
42    /// Every span reported by this error is reported in terms of this string.
43    pub fn pattern(&self) -> &str {
44        &self.pattern
45    }
46
47    /// Return the span at which this error occurred.
48    pub fn span(&self) -> &Span {
49        &self.span
50    }
51
52    /// Return an auxiliary span. This span exists only for some errors that
53    /// benefit from being able to point to two locations in the original
54    /// regular expression. For example, "duplicate" errors will have the
55    /// main error position set to the duplicate occurrence while its
56    /// auxiliary span will be set to the initial occurrence.
57    pub fn auxiliary_span(&self) -> Option<&Span> {
58        use self::ErrorKind::*;
59        match self.kind {
60            FlagDuplicate { ref original } => Some(original),
61            FlagRepeatedNegation { ref original, .. } => Some(original),
62            GroupNameDuplicate { ref original, .. } => Some(original),
63            _ => None,
64        }
65    }
66}
67
68/// The type of an error that occurred while building an AST.
69///
70/// This error type is marked as `non_exhaustive`. This means that adding a
71/// new variant is not considered a breaking change.
72#[non_exhaustive]
73#[derive(Clone, Debug, Eq, PartialEq)]
74#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
75pub enum ErrorKind {
76    /// The capturing group limit was exceeded.
77    ///
78    /// Note that this represents a limit on the total number of capturing
79    /// groups in a regex and not necessarily the number of nested capturing
80    /// groups. That is, the nest limit can be low and it is still possible for
81    /// this error to occur.
82    CaptureLimitExceeded,
83    /// An invalid escape sequence was found in a character class set.
84    ClassEscapeInvalid,
85    /// An invalid character class range was found. An invalid range is any
86    /// range where the start is greater than the end.
87    ClassRangeInvalid,
88    /// An invalid range boundary was found in a character class. Range
89    /// boundaries must be a single literal codepoint, but this error indicates
90    /// that something else was found, such as a nested class.
91    ClassRangeLiteral,
92    /// An opening `[` was found with no corresponding closing `]`.
93    ClassUnclosed,
94    /// Note that this error variant is no longer used. Namely, a decimal
95    /// number can only appear as a repetition quantifier. When the number
96    /// in a repetition quantifier is empty, then it gets its own specialized
97    /// error, `RepetitionCountDecimalEmpty`.
98    DecimalEmpty,
99    /// An invalid decimal number was given where one was expected.
100    DecimalInvalid,
101    /// A bracketed hex literal was empty.
102    EscapeHexEmpty,
103    /// A bracketed hex literal did not correspond to a Unicode scalar value.
104    EscapeHexInvalid,
105    /// An invalid hexadecimal digit was found.
106    EscapeHexInvalidDigit,
107    /// EOF was found before an escape sequence was completed.
108    EscapeUnexpectedEof,
109    /// An unrecognized escape sequence.
110    EscapeUnrecognized,
111    /// A dangling negation was used when setting flags, e.g., `i-`.
112    FlagDanglingNegation,
113    /// A flag was used twice, e.g., `i-i`.
114    FlagDuplicate {
115        /// The position of the original flag. The error position
116        /// points to the duplicate flag.
117        original: Span,
118    },
119    /// The negation operator was used twice, e.g., `-i-s`.
120    FlagRepeatedNegation {
121        /// The position of the original negation operator. The error position
122        /// points to the duplicate negation operator.
123        original: Span,
124    },
125    /// Expected a flag but got EOF, e.g., `(?`.
126    FlagUnexpectedEof,
127    /// Unrecognized flag, e.g., `a`.
128    FlagUnrecognized,
129    /// A duplicate capture name was found.
130    GroupNameDuplicate {
131        /// The position of the initial occurrence of the capture name. The
132        /// error position itself points to the duplicate occurrence.
133        original: Span,
134    },
135    /// A capture group name is empty, e.g., `(?P<>abc)`.
136    GroupNameEmpty,
137    /// An invalid character was seen for a capture group name. This includes
138    /// errors where the first character is a digit (even though subsequent
139    /// characters are allowed to be digits).
140    GroupNameInvalid,
141    /// A closing `>` could not be found for a capture group name.
142    GroupNameUnexpectedEof,
143    /// An unclosed group, e.g., `(ab`.
144    ///
145    /// The span of this error corresponds to the unclosed parenthesis.
146    GroupUnclosed,
147    /// An unopened group, e.g., `ab)`.
148    GroupUnopened,
149    /// The nest limit was exceeded. The limit stored here is the limit
150    /// configured in the parser.
151    NestLimitExceeded(u32),
152    /// The range provided in a counted repetition operator is invalid. The
153    /// range is invalid if the start is greater than the end.
154    RepetitionCountInvalid,
155    /// An opening `{` was not followed by a valid decimal value.
156    /// For example, `x{}` or `x{]}` would fail.
157    RepetitionCountDecimalEmpty,
158    /// An opening `{` was found with no corresponding closing `}`.
159    RepetitionCountUnclosed,
160    /// A repetition operator was applied to a missing sub-expression. This
161    /// occurs, for example, in the regex consisting of just a `*` or even
162    /// `(?i)*`. It is, however, possible to create a repetition operating on
163    /// an empty sub-expression. For example, `()*` is still considered valid.
164    RepetitionMissing,
165    /// The special word boundary syntax, `\b{something}`, was used, but
166    /// either EOF without `}` was seen, or an invalid character in the
167    /// braces was seen.
168    SpecialWordBoundaryUnclosed,
169    /// The special word boundary syntax, `\b{something}`, was used, but
170    /// `something` was not recognized as a valid word boundary kind.
171    SpecialWordBoundaryUnrecognized,
172    /// The syntax `\b{` was observed, but afterwards the end of the pattern
173    /// was observed without being able to tell whether it was meant to be a
174    /// bounded repetition on the `\b` or the beginning of a special word
175    /// boundary assertion.
176    SpecialWordOrRepetitionUnexpectedEof,
177    /// The Unicode class is not valid. This typically occurs when a `\p` is
178    /// followed by something other than a `{`.
179    UnicodeClassInvalid,
180    /// When octal support is disabled, this error is produced when an octal
181    /// escape is used. The octal escape is assumed to be an invocation of
182    /// a backreference, which is the common case.
183    UnsupportedBackreference,
184    /// When syntax similar to PCRE's look-around is used, this error is
185    /// returned. Some example syntaxes that are rejected include, but are
186    /// not necessarily limited to, `(?=re)`, `(?!re)`, `(?<=re)` and
187    /// `(?<!re)`. Note that all of these syntaxes are otherwise invalid; this
188    /// error is used to improve the user experience.
189    UnsupportedLookAround,
190}
191
192#[cfg(feature = "std")]
193impl std::error::Error for Error {}
194
195impl core::fmt::Display for Error {
196    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
197        crate::error::Formatter::from(self).fmt(f)
198    }
199}
200
201impl core::fmt::Display for ErrorKind {
202    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
203        use self::ErrorKind::*;
204        match *self {
205            CaptureLimitExceeded => write!(
206                f,
207                "exceeded the maximum number of \
208                 capturing groups ({})",
209                u32::MAX
210            ),
211            ClassEscapeInvalid => {
212                write!(f, "invalid escape sequence found in character class")
213            }
214            ClassRangeInvalid => write!(
215                f,
216                "invalid character class range, \
217                 the start must be <= the end"
218            ),
219            ClassRangeLiteral => {
220                write!(f, "invalid range boundary, must be a literal")
221            }
222            ClassUnclosed => write!(f, "unclosed character class"),
223            DecimalEmpty => write!(f, "decimal literal empty"),
224            DecimalInvalid => write!(f, "decimal literal invalid"),
225            EscapeHexEmpty => write!(f, "hexadecimal literal empty"),
226            EscapeHexInvalid => {
227                write!(f, "hexadecimal literal is not a Unicode scalar value")
228            }
229            EscapeHexInvalidDigit => write!(f, "invalid hexadecimal digit"),
230            EscapeUnexpectedEof => write!(
231                f,
232                "incomplete escape sequence, \
233                 reached end of pattern prematurely"
234            ),
235            EscapeUnrecognized => write!(f, "unrecognized escape sequence"),
236            FlagDanglingNegation => {
237                write!(f, "dangling flag negation operator")
238            }
239            FlagDuplicate { .. } => write!(f, "duplicate flag"),
240            FlagRepeatedNegation { .. } => {
241                write!(f, "flag negation operator repeated")
242            }
243            FlagUnexpectedEof => {
244                write!(f, "expected flag but got end of regex")
245            }
246            FlagUnrecognized => write!(f, "unrecognized flag"),
247            GroupNameDuplicate { .. } => {
248                write!(f, "duplicate capture group name")
249            }
250            GroupNameEmpty => write!(f, "empty capture group name"),
251            GroupNameInvalid => write!(f, "invalid capture group character"),
252            GroupNameUnexpectedEof => write!(f, "unclosed capture group name"),
253            GroupUnclosed => write!(f, "unclosed group"),
254            GroupUnopened => write!(f, "unopened group"),
255            NestLimitExceeded(limit) => write!(
256                f,
257                "exceed the maximum number of \
258                 nested parentheses/brackets ({})",
259                limit
260            ),
261            RepetitionCountInvalid => write!(
262                f,
263                "invalid repetition count range, \
264                 the start must be <= the end"
265            ),
266            RepetitionCountDecimalEmpty => {
267                write!(f, "repetition quantifier expects a valid decimal")
268            }
269            RepetitionCountUnclosed => {
270                write!(f, "unclosed counted repetition")
271            }
272            RepetitionMissing => {
273                write!(f, "repetition operator missing expression")
274            }
275            SpecialWordBoundaryUnclosed => {
276                write!(
277                    f,
278                    "special word boundary assertion is either \
279                     unclosed or contains an invalid character",
280                )
281            }
282            SpecialWordBoundaryUnrecognized => {
283                write!(
284                    f,
285                    "unrecognized special word boundary assertion, \
286                     valid choices are: start, end, start-half \
287                     or end-half",
288                )
289            }
290            SpecialWordOrRepetitionUnexpectedEof => {
291                write!(
292                    f,
293                    "found either the beginning of a special word \
294                     boundary or a bounded repetition on a \\b with \
295                     an opening brace, but no closing brace",
296                )
297            }
298            UnicodeClassInvalid => {
299                write!(f, "invalid Unicode character class")
300            }
301            UnsupportedBackreference => {
302                write!(f, "backreferences are not supported")
303            }
304            UnsupportedLookAround => write!(
305                f,
306                "look-around, including look-ahead and look-behind, \
307                 is not supported"
308            ),
309        }
310    }
311}
312
313/// Span represents the position information of a single AST item.
314///
315/// All span positions are absolute byte offsets that can be used on the
316/// original regular expression that was parsed.
317#[derive(Clone, Copy, Eq, PartialEq)]
318#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
319pub struct Span {
320    /// The start byte offset.
321    pub start: Position,
322    /// The end byte offset.
323    pub end: Position,
324}
325
326impl core::fmt::Debug for Span {
327    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
328        write!(f, "Span({:?}, {:?})", self.start, self.end)
329    }
330}
331
332impl Ord for Span {
333    fn cmp(&self, other: &Span) -> Ordering {
334        (&self.start, &self.end).cmp(&(&other.start, &other.end))
335    }
336}
337
338impl PartialOrd for Span {
339    fn partial_cmp(&self, other: &Span) -> Option<Ordering> {
340        Some(self.cmp(other))
341    }
342}
343
344/// A single position in a regular expression.
345///
346/// A position encodes one half of a span, and include the byte offset, line
347/// number and column number.
348#[derive(Clone, Copy, Eq, PartialEq, Ord, PartialOrd)]
349#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
350pub struct Position {
351    /// The absolute offset of this position, starting at `0` from the
352    /// beginning of the regular expression pattern string.
353    pub offset: usize,
354    /// The line number, starting at `1`.
355    pub line: usize,
356    /// The approximate column number, starting at `1`.
357    pub column: usize,
358}
359
360impl core::fmt::Debug for Position {
361    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
362        write!(
363            f,
364            "Position(o: {:?}, l: {:?}, c: {:?})",
365            self.offset, self.line, self.column
366        )
367    }
368}
369
370impl Span {
371    /// Create a new span with the given positions.
372    pub fn new(start: Position, end: Position) -> Span {
373        Span { start, end }
374    }
375
376    /// Create a new span using the given position as the start and end.
377    pub fn splat(pos: Position) -> Span {
378        Span::new(pos, pos)
379    }
380
381    /// Create a new span by replacing the starting the position with the one
382    /// given.
383    pub fn with_start(self, pos: Position) -> Span {
384        Span { start: pos, ..self }
385    }
386
387    /// Create a new span by replacing the ending the position with the one
388    /// given.
389    pub fn with_end(self, pos: Position) -> Span {
390        Span { end: pos, ..self }
391    }
392
393    /// Returns true if and only if this span occurs on a single line.
394    pub fn is_one_line(&self) -> bool {
395        self.start.line == self.end.line
396    }
397
398    /// Returns true if and only if this span is empty. That is, it points to
399    /// a single position in the concrete syntax of a regular expression.
400    pub fn is_empty(&self) -> bool {
401        self.start.offset == self.end.offset
402    }
403}
404
405impl Position {
406    /// Create a new position with the given information.
407    ///
408    /// `offset` is the absolute offset of the position, starting at `0` from
409    /// the beginning of the regular expression pattern string.
410    ///
411    /// `line` is the line number, starting at `1`.
412    ///
413    /// `column` is the approximate column number, starting at `1`.
414    pub fn new(offset: usize, line: usize, column: usize) -> Position {
415        Position { offset, line, column }
416    }
417}
418
419/// An abstract syntax tree for a singular expression along with comments
420/// found.
421///
422/// Comments are not stored in the tree itself to avoid complexity. Each
423/// comment contains a span of precisely where it occurred in the original
424/// regular expression.
425#[derive(Clone, Debug, Eq, PartialEq)]
426#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
427pub struct WithComments {
428    /// The actual ast.
429    pub ast: Ast,
430    /// All comments found in the original regular expression.
431    pub comments: Vec<Comment>,
432}
433
434/// A comment from a regular expression with an associated span.
435///
436/// A regular expression can only contain comments when the `x` flag is
437/// enabled.
438#[derive(Clone, Debug, Eq, PartialEq)]
439#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
440pub struct Comment {
441    /// The span of this comment, including the beginning `#` and ending `\n`.
442    pub span: Span,
443    /// The comment text, starting with the first character following the `#`
444    /// and ending with the last character preceding the `\n`.
445    pub comment: String,
446}
447
448/// An abstract syntax tree for a single regular expression.
449///
450/// An `Ast`'s `fmt::Display` implementation uses constant stack space and heap
451/// space proportional to the size of the `Ast`.
452///
453/// This type defines its own destructor that uses constant stack space and
454/// heap space proportional to the size of the `Ast`.
455#[derive(Clone, Debug, Eq, PartialEq)]
456#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
457pub enum Ast {
458    /// An empty regex that matches everything.
459    Empty(Box<Span>),
460    /// A set of flags, e.g., `(?is)`.
461    Flags(Box<SetFlags>),
462    /// A single character literal, which includes escape sequences.
463    Literal(Box<Literal>),
464    /// The "any character" class.
465    Dot(Box<Span>),
466    /// A single zero-width assertion.
467    Assertion(Box<Assertion>),
468    /// A single Unicode character class, e.g., `\pL` or `\p{Greek}`.
469    ClassUnicode(Box<ClassUnicode>),
470    /// A single perl character class, e.g., `\d` or `\W`.
471    ClassPerl(Box<ClassPerl>),
472    /// A single bracketed character class set, which may contain zero or more
473    /// character ranges and/or zero or more nested classes. e.g.,
474    /// `[a-zA-Z\pL]`.
475    ClassBracketed(Box<ClassBracketed>),
476    /// A repetition operator applied to an arbitrary regular expression.
477    Repetition(Box<Repetition>),
478    /// A grouped regular expression.
479    Group(Box<Group>),
480    /// An alternation of regular expressions.
481    Alternation(Box<Alternation>),
482    /// A concatenation of regular expressions.
483    Concat(Box<Concat>),
484}
485
486impl Ast {
487    /// Create an "empty" AST item.
488    pub fn empty(span: Span) -> Ast {
489        Ast::Empty(Box::new(span))
490    }
491
492    /// Create a "flags" AST item.
493    pub fn flags(e: SetFlags) -> Ast {
494        Ast::Flags(Box::new(e))
495    }
496
497    /// Create a "literal" AST item.
498    pub fn literal(e: Literal) -> Ast {
499        Ast::Literal(Box::new(e))
500    }
501
502    /// Create a "dot" AST item.
503    pub fn dot(span: Span) -> Ast {
504        Ast::Dot(Box::new(span))
505    }
506
507    /// Create a "assertion" AST item.
508    pub fn assertion(e: Assertion) -> Ast {
509        Ast::Assertion(Box::new(e))
510    }
511
512    /// Create a "Unicode class" AST item.
513    pub fn class_unicode(e: ClassUnicode) -> Ast {
514        Ast::ClassUnicode(Box::new(e))
515    }
516
517    /// Create a "Perl class" AST item.
518    pub fn class_perl(e: ClassPerl) -> Ast {
519        Ast::ClassPerl(Box::new(e))
520    }
521
522    /// Create a "bracketed class" AST item.
523    pub fn class_bracketed(e: ClassBracketed) -> Ast {
524        Ast::ClassBracketed(Box::new(e))
525    }
526
527    /// Create a "repetition" AST item.
528    pub fn repetition(e: Repetition) -> Ast {
529        Ast::Repetition(Box::new(e))
530    }
531
532    /// Create a "group" AST item.
533    pub fn group(e: Group) -> Ast {
534        Ast::Group(Box::new(e))
535    }
536
537    /// Create a "alternation" AST item.
538    pub fn alternation(e: Alternation) -> Ast {
539        Ast::Alternation(Box::new(e))
540    }
541
542    /// Create a "concat" AST item.
543    pub fn concat(e: Concat) -> Ast {
544        Ast::Concat(Box::new(e))
545    }
546
547    /// Return the span of this abstract syntax tree.
548    pub fn span(&self) -> &Span {
549        match *self {
550            Ast::Empty(ref span) => span,
551            Ast::Flags(ref x) => &x.span,
552            Ast::Literal(ref x) => &x.span,
553            Ast::Dot(ref span) => span,
554            Ast::Assertion(ref x) => &x.span,
555            Ast::ClassUnicode(ref x) => &x.span,
556            Ast::ClassPerl(ref x) => &x.span,
557            Ast::ClassBracketed(ref x) => &x.span,
558            Ast::Repetition(ref x) => &x.span,
559            Ast::Group(ref x) => &x.span,
560            Ast::Alternation(ref x) => &x.span,
561            Ast::Concat(ref x) => &x.span,
562        }
563    }
564
565    /// Return true if and only if this Ast is empty.
566    pub fn is_empty(&self) -> bool {
567        match *self {
568            Ast::Empty(_) => true,
569            _ => false,
570        }
571    }
572
573    /// Returns true if and only if this AST has any (including possibly empty)
574    /// subexpressions.
575    fn has_subexprs(&self) -> bool {
576        match *self {
577            Ast::Empty(_)
578            | Ast::Flags(_)
579            | Ast::Literal(_)
580            | Ast::Dot(_)
581            | Ast::Assertion(_)
582            | Ast::ClassUnicode(_)
583            | Ast::ClassPerl(_) => false,
584            Ast::ClassBracketed(_)
585            | Ast::Repetition(_)
586            | Ast::Group(_)
587            | Ast::Alternation(_)
588            | Ast::Concat(_) => true,
589        }
590    }
591}
592
593/// Print a display representation of this Ast.
594///
595/// This does not preserve any of the original whitespace formatting that may
596/// have originally been present in the concrete syntax from which this Ast
597/// was generated.
598///
599/// This implementation uses constant stack space and heap space proportional
600/// to the size of the `Ast`.
601impl core::fmt::Display for Ast {
602    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
603        use crate::ast::print::Printer;
604        Printer::new().print(self, f)
605    }
606}
607
608/// An alternation of regular expressions.
609#[derive(Clone, Debug, Eq, PartialEq)]
610#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
611pub struct Alternation {
612    /// The span of this alternation.
613    pub span: Span,
614    /// The alternate regular expressions.
615    pub asts: Vec<Ast>,
616}
617
618impl Alternation {
619    /// Return this alternation as an AST.
620    ///
621    /// If this alternation contains zero ASTs, then `Ast::empty` is returned.
622    /// If this alternation contains exactly 1 AST, then the corresponding AST
623    /// is returned. Otherwise, `Ast::alternation` is returned.
624    pub fn into_ast(mut self) -> Ast {
625        match self.asts.len() {
626            0 => Ast::empty(self.span),
627            1 => self.asts.pop().unwrap(),
628            _ => Ast::alternation(self),
629        }
630    }
631}
632
633/// A concatenation of regular expressions.
634#[derive(Clone, Debug, Eq, PartialEq)]
635#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
636pub struct Concat {
637    /// The span of this concatenation.
638    pub span: Span,
639    /// The concatenation regular expressions.
640    pub asts: Vec<Ast>,
641}
642
643impl Concat {
644    /// Return this concatenation as an AST.
645    ///
646    /// If this alternation contains zero ASTs, then `Ast::empty` is returned.
647    /// If this alternation contains exactly 1 AST, then the corresponding AST
648    /// is returned. Otherwise, `Ast::concat` is returned.
649    pub fn into_ast(mut self) -> Ast {
650        match self.asts.len() {
651            0 => Ast::empty(self.span),
652            1 => self.asts.pop().unwrap(),
653            _ => Ast::concat(self),
654        }
655    }
656}
657
658/// A single literal expression.
659///
660/// A literal corresponds to a single Unicode scalar value. Literals may be
661/// represented in their literal form, e.g., `a` or in their escaped form,
662/// e.g., `\x61`.
663#[derive(Clone, Debug, Eq, PartialEq)]
664#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
665pub struct Literal {
666    /// The span of this literal.
667    pub span: Span,
668    /// The kind of this literal.
669    pub kind: LiteralKind,
670    /// The Unicode scalar value corresponding to this literal.
671    pub c: char,
672}
673
674impl Literal {
675    /// If this literal was written as a `\x` hex escape, then this returns
676    /// the corresponding byte value. Otherwise, this returns `None`.
677    pub fn byte(&self) -> Option<u8> {
678        match self.kind {
679            LiteralKind::HexFixed(HexLiteralKind::X) => {
680                u8::try_from(self.c).ok()
681            }
682            _ => None,
683        }
684    }
685}
686
687/// The kind of a single literal expression.
688#[derive(Clone, Debug, Eq, PartialEq)]
689#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
690pub enum LiteralKind {
691    /// The literal is written verbatim, e.g., `a` or `☃`.
692    Verbatim,
693    /// The literal is written as an escape because it is otherwise a special
694    /// regex meta character, e.g., `\*` or `\[`.
695    Meta,
696    /// The literal is written as an escape despite the fact that the escape is
697    /// unnecessary, e.g., `\%` or `\/`.
698    Superfluous,
699    /// The literal is written as an octal escape, e.g., `\141`.
700    Octal,
701    /// The literal is written as a hex code with a fixed number of digits
702    /// depending on the type of the escape, e.g., `\x61` or `\u0061` or
703    /// `\U00000061`.
704    HexFixed(HexLiteralKind),
705    /// The literal is written as a hex code with a bracketed number of
706    /// digits. The only restriction is that the bracketed hex code must refer
707    /// to a valid Unicode scalar value.
708    HexBrace(HexLiteralKind),
709    /// The literal is written as a specially recognized escape, e.g., `\f`
710    /// or `\n`.
711    Special(SpecialLiteralKind),
712}
713
714/// The type of a special literal.
715///
716/// A special literal is a special escape sequence recognized by the regex
717/// parser, e.g., `\f` or `\n`.
718#[derive(Clone, Debug, Eq, PartialEq)]
719#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
720pub enum SpecialLiteralKind {
721    /// Bell, spelled `\a` (`\x07`).
722    Bell,
723    /// Form feed, spelled `\f` (`\x0C`).
724    FormFeed,
725    /// Tab, spelled `\t` (`\x09`).
726    Tab,
727    /// Line feed, spelled `\n` (`\x0A`).
728    LineFeed,
729    /// Carriage return, spelled `\r` (`\x0D`).
730    CarriageReturn,
731    /// Vertical tab, spelled `\v` (`\x0B`).
732    VerticalTab,
733    /// Space, spelled `\ ` (`\x20`). Note that this can only appear when
734    /// parsing in verbose mode.
735    Space,
736}
737
738/// The type of a Unicode hex literal.
739///
740/// Note that all variants behave the same when used with brackets. They only
741/// differ when used without brackets in the number of hex digits that must
742/// follow.
743#[derive(Clone, Debug, Eq, PartialEq)]
744#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
745pub enum HexLiteralKind {
746    /// A `\x` prefix. When used without brackets, this form is limited to
747    /// two digits.
748    X,
749    /// A `\u` prefix. When used without brackets, this form is limited to
750    /// four digits.
751    UnicodeShort,
752    /// A `\U` prefix. When used without brackets, this form is limited to
753    /// eight digits.
754    UnicodeLong,
755}
756
757impl HexLiteralKind {
758    /// The number of digits that must be used with this literal form when
759    /// used without brackets. When used with brackets, there is no
760    /// restriction on the number of digits.
761    pub fn digits(&self) -> u32 {
762        match *self {
763            HexLiteralKind::X => 2,
764            HexLiteralKind::UnicodeShort => 4,
765            HexLiteralKind::UnicodeLong => 8,
766        }
767    }
768}
769
770/// A Perl character class.
771#[derive(Clone, Debug, Eq, PartialEq)]
772#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
773pub struct ClassPerl {
774    /// The span of this class.
775    pub span: Span,
776    /// The kind of Perl class.
777    pub kind: ClassPerlKind,
778    /// Whether the class is negated or not. e.g., `\d` is not negated but
779    /// `\D` is.
780    pub negated: bool,
781}
782
783/// The available Perl character classes.
784#[derive(Clone, Debug, Eq, PartialEq)]
785#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
786pub enum ClassPerlKind {
787    /// Decimal numbers.
788    Digit,
789    /// Whitespace.
790    Space,
791    /// Word characters.
792    Word,
793}
794
795/// An ASCII character class.
796#[derive(Clone, Debug, Eq, PartialEq)]
797#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
798pub struct ClassAscii {
799    /// The span of this class.
800    pub span: Span,
801    /// The kind of ASCII class.
802    pub kind: ClassAsciiKind,
803    /// Whether the class is negated or not. e.g., `[[:alpha:]]` is not negated
804    /// but `[[:^alpha:]]` is.
805    pub negated: bool,
806}
807
808/// The available ASCII character classes.
809#[derive(Clone, Debug, Eq, PartialEq)]
810#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
811pub enum ClassAsciiKind {
812    /// `[0-9A-Za-z]`
813    Alnum,
814    /// `[A-Za-z]`
815    Alpha,
816    /// `[\x00-\x7F]`
817    Ascii,
818    /// `[ \t]`
819    Blank,
820    /// `[\x00-\x1F\x7F]`
821    Cntrl,
822    /// `[0-9]`
823    Digit,
824    /// `[!-~]`
825    Graph,
826    /// `[a-z]`
827    Lower,
828    /// `[ -~]`
829    Print,
830    /// ``[!-/:-@\[-`{-~]``
831    Punct,
832    /// `[\t\n\v\f\r ]`
833    Space,
834    /// `[A-Z]`
835    Upper,
836    /// `[0-9A-Za-z_]`
837    Word,
838    /// `[0-9A-Fa-f]`
839    Xdigit,
840}
841
842impl ClassAsciiKind {
843    /// Return the corresponding ClassAsciiKind variant for the given name.
844    ///
845    /// The name given should correspond to the lowercase version of the
846    /// variant name. e.g., `cntrl` is the name for `ClassAsciiKind::Cntrl`.
847    ///
848    /// If no variant with the corresponding name exists, then `None` is
849    /// returned.
850    pub fn from_name(name: &str) -> Option<ClassAsciiKind> {
851        use self::ClassAsciiKind::*;
852        match name {
853            "alnum" => Some(Alnum),
854            "alpha" => Some(Alpha),
855            "ascii" => Some(Ascii),
856            "blank" => Some(Blank),
857            "cntrl" => Some(Cntrl),
858            "digit" => Some(Digit),
859            "graph" => Some(Graph),
860            "lower" => Some(Lower),
861            "print" => Some(Print),
862            "punct" => Some(Punct),
863            "space" => Some(Space),
864            "upper" => Some(Upper),
865            "word" => Some(Word),
866            "xdigit" => Some(Xdigit),
867            _ => None,
868        }
869    }
870}
871
872/// A Unicode character class.
873#[derive(Clone, Debug, Eq, PartialEq)]
874#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
875pub struct ClassUnicode {
876    /// The span of this class.
877    pub span: Span,
878    /// Whether this class is negated or not.
879    ///
880    /// Note: be careful when using this attribute. This specifically refers
881    /// to whether the class is written as `\p` or `\P`, where the latter
882    /// is `negated = true`. However, it also possible to write something like
883    /// `\P{scx!=Katakana}` which is actually equivalent to
884    /// `\p{scx=Katakana}` and is therefore not actually negated even though
885    /// `negated = true` here. To test whether this class is truly negated
886    /// or not, use the `is_negated` method.
887    pub negated: bool,
888    /// The kind of Unicode class.
889    pub kind: ClassUnicodeKind,
890}
891
892impl ClassUnicode {
893    /// Returns true if this class has been negated.
894    ///
895    /// Note that this takes the Unicode op into account, if it's present.
896    /// e.g., `is_negated` for `\P{scx!=Katakana}` will return `false`.
897    pub fn is_negated(&self) -> bool {
898        match self.kind {
899            ClassUnicodeKind::NamedValue {
900                op: ClassUnicodeOpKind::NotEqual,
901                ..
902            } => !self.negated,
903            _ => self.negated,
904        }
905    }
906}
907
908/// The available forms of Unicode character classes.
909#[derive(Clone, Debug, Eq, PartialEq)]
910pub enum ClassUnicodeKind {
911    /// A one letter abbreviated class, e.g., `\pN`.
912    OneLetter(char),
913    /// A binary property, general category or script. The string may be
914    /// empty.
915    Named(String),
916    /// A property name and an associated value.
917    NamedValue {
918        /// The type of Unicode op used to associate `name` with `value`.
919        op: ClassUnicodeOpKind,
920        /// The property name (which may be empty).
921        name: String,
922        /// The property value (which may be empty).
923        value: String,
924    },
925}
926
927#[cfg(feature = "arbitrary")]
928impl arbitrary::Arbitrary<'_> for ClassUnicodeKind {
929    fn arbitrary(
930        u: &mut arbitrary::Unstructured,
931    ) -> arbitrary::Result<ClassUnicodeKind> {
932        #[cfg(any(
933            feature = "unicode-age",
934            feature = "unicode-bool",
935            feature = "unicode-gencat",
936            feature = "unicode-perl",
937            feature = "unicode-script",
938            feature = "unicode-segment",
939        ))]
940        {
941            use alloc::string::ToString;
942
943            use super::unicode_tables::{
944                property_names::PROPERTY_NAMES,
945                property_values::PROPERTY_VALUES,
946            };
947
948            match u.choose_index(3)? {
949                0 => {
950                    let all = PROPERTY_VALUES
951                        .iter()
952                        .flat_map(|e| e.1.iter())
953                        .filter(|(name, _)| name.len() == 1)
954                        .count();
955                    let idx = u.choose_index(all)?;
956                    let value = PROPERTY_VALUES
957                        .iter()
958                        .flat_map(|e| e.1.iter())
959                        .take(idx + 1)
960                        .last()
961                        .unwrap()
962                        .0
963                        .chars()
964                        .next()
965                        .unwrap();
966                    Ok(ClassUnicodeKind::OneLetter(value))
967                }
968                1 => {
969                    let all = PROPERTY_VALUES
970                        .iter()
971                        .map(|e| e.1.len())
972                        .sum::<usize>()
973                        + PROPERTY_NAMES.len();
974                    let idx = u.choose_index(all)?;
975                    let name = PROPERTY_VALUES
976                        .iter()
977                        .flat_map(|e| e.1.iter())
978                        .chain(PROPERTY_NAMES)
979                        .map(|(_, e)| e)
980                        .take(idx + 1)
981                        .last()
982                        .unwrap();
983                    Ok(ClassUnicodeKind::Named(name.to_string()))
984                }
985                2 => {
986                    let all = PROPERTY_VALUES
987                        .iter()
988                        .map(|e| e.1.len())
989                        .sum::<usize>();
990                    let idx = u.choose_index(all)?;
991                    let (prop, value) = PROPERTY_VALUES
992                        .iter()
993                        .flat_map(|e| {
994                            e.1.iter().map(|(_, value)| (e.0, value))
995                        })
996                        .take(idx + 1)
997                        .last()
998                        .unwrap();
999                    Ok(ClassUnicodeKind::NamedValue {
1000                        op: u.arbitrary()?,
1001                        name: prop.to_string(),
1002                        value: value.to_string(),
1003                    })
1004                }
1005                _ => unreachable!("index chosen is impossible"),
1006            }
1007        }
1008        #[cfg(not(any(
1009            feature = "unicode-age",
1010            feature = "unicode-bool",
1011            feature = "unicode-gencat",
1012            feature = "unicode-perl",
1013            feature = "unicode-script",
1014            feature = "unicode-segment",
1015        )))]
1016        {
1017            match u.choose_index(3)? {
1018                0 => Ok(ClassUnicodeKind::OneLetter(u.arbitrary()?)),
1019                1 => Ok(ClassUnicodeKind::Named(u.arbitrary()?)),
1020                2 => Ok(ClassUnicodeKind::NamedValue {
1021                    op: u.arbitrary()?,
1022                    name: u.arbitrary()?,
1023                    value: u.arbitrary()?,
1024                }),
1025                _ => unreachable!("index chosen is impossible"),
1026            }
1027        }
1028    }
1029
1030    fn size_hint(depth: usize) -> (usize, Option<usize>) {
1031        #[cfg(any(
1032            feature = "unicode-age",
1033            feature = "unicode-bool",
1034            feature = "unicode-gencat",
1035            feature = "unicode-perl",
1036            feature = "unicode-script",
1037            feature = "unicode-segment",
1038        ))]
1039        {
1040            arbitrary::size_hint::and_all(&[
1041                usize::size_hint(depth),
1042                usize::size_hint(depth),
1043                arbitrary::size_hint::or(
1044                    (0, Some(0)),
1045                    ClassUnicodeOpKind::size_hint(depth),
1046                ),
1047            ])
1048        }
1049        #[cfg(not(any(
1050            feature = "unicode-age",
1051            feature = "unicode-bool",
1052            feature = "unicode-gencat",
1053            feature = "unicode-perl",
1054            feature = "unicode-script",
1055            feature = "unicode-segment",
1056        )))]
1057        {
1058            arbitrary::size_hint::and(
1059                usize::size_hint(depth),
1060                arbitrary::size_hint::or_all(&[
1061                    char::size_hint(depth),
1062                    String::size_hint(depth),
1063                    arbitrary::size_hint::and_all(&[
1064                        String::size_hint(depth),
1065                        String::size_hint(depth),
1066                        ClassUnicodeOpKind::size_hint(depth),
1067                    ]),
1068                ]),
1069            )
1070        }
1071    }
1072}
1073
1074/// The type of op used in a Unicode character class.
1075#[derive(Clone, Debug, Eq, PartialEq)]
1076#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1077pub enum ClassUnicodeOpKind {
1078    /// A property set to a specific value, e.g., `\p{scx=Katakana}`.
1079    Equal,
1080    /// A property set to a specific value using a colon, e.g.,
1081    /// `\p{scx:Katakana}`.
1082    Colon,
1083    /// A property that isn't a particular value, e.g., `\p{scx!=Katakana}`.
1084    NotEqual,
1085}
1086
1087impl ClassUnicodeOpKind {
1088    /// Whether the op is an equality op or not.
1089    pub fn is_equal(&self) -> bool {
1090        match *self {
1091            ClassUnicodeOpKind::Equal | ClassUnicodeOpKind::Colon => true,
1092            _ => false,
1093        }
1094    }
1095}
1096
1097/// A bracketed character class, e.g., `[a-z0-9]`.
1098#[derive(Clone, Debug, Eq, PartialEq)]
1099#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1100pub struct ClassBracketed {
1101    /// The span of this class.
1102    pub span: Span,
1103    /// Whether this class is negated or not. e.g., `[a]` is not negated but
1104    /// `[^a]` is.
1105    pub negated: bool,
1106    /// The type of this set. A set is either a normal union of things, e.g.,
1107    /// `[abc]` or a result of applying set operations, e.g., `[\pL--c]`.
1108    pub kind: ClassSet,
1109}
1110
1111/// A character class set.
1112///
1113/// This type corresponds to the internal structure of a bracketed character
1114/// class. That is, every bracketed character is one of two types: a union of
1115/// items (literals, ranges, other bracketed classes) or a tree of binary set
1116/// operations.
1117#[derive(Clone, Debug, Eq, PartialEq)]
1118#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1119pub enum ClassSet {
1120    /// An item, which can be a single literal, range, nested character class
1121    /// or a union of items.
1122    Item(ClassSetItem),
1123    /// A single binary operation (i.e., &&, -- or ~~).
1124    BinaryOp(ClassSetBinaryOp),
1125}
1126
1127impl ClassSet {
1128    /// Build a set from a union.
1129    pub fn union(ast: ClassSetUnion) -> ClassSet {
1130        ClassSet::Item(ClassSetItem::Union(ast))
1131    }
1132
1133    /// Return the span of this character class set.
1134    pub fn span(&self) -> &Span {
1135        match *self {
1136            ClassSet::Item(ref x) => x.span(),
1137            ClassSet::BinaryOp(ref x) => &x.span,
1138        }
1139    }
1140
1141    /// Return true if and only if this class set is empty.
1142    fn is_empty(&self) -> bool {
1143        match *self {
1144            ClassSet::Item(ClassSetItem::Empty(_)) => true,
1145            _ => false,
1146        }
1147    }
1148}
1149
1150/// A single component of a character class set.
1151#[derive(Clone, Debug, Eq, PartialEq)]
1152#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1153pub enum ClassSetItem {
1154    /// An empty item.
1155    ///
1156    /// Note that a bracketed character class cannot contain a single empty
1157    /// item. Empty items can appear when using one of the binary operators.
1158    /// For example, `[&&]` is the intersection of two empty classes.
1159    Empty(Span),
1160    /// A single literal.
1161    Literal(Literal),
1162    /// A range between two literals.
1163    Range(ClassSetRange),
1164    /// An ASCII character class, e.g., `[:alnum:]` or `[:punct:]`.
1165    Ascii(ClassAscii),
1166    /// A Unicode character class, e.g., `\pL` or `\p{Greek}`.
1167    Unicode(ClassUnicode),
1168    /// A perl character class, e.g., `\d` or `\W`.
1169    Perl(ClassPerl),
1170    /// A bracketed character class set, which may contain zero or more
1171    /// character ranges and/or zero or more nested classes. e.g.,
1172    /// `[a-zA-Z\pL]`.
1173    Bracketed(Box<ClassBracketed>),
1174    /// A union of items.
1175    Union(ClassSetUnion),
1176}
1177
1178impl ClassSetItem {
1179    /// Return the span of this character class set item.
1180    pub fn span(&self) -> &Span {
1181        match *self {
1182            ClassSetItem::Empty(ref span) => span,
1183            ClassSetItem::Literal(ref x) => &x.span,
1184            ClassSetItem::Range(ref x) => &x.span,
1185            ClassSetItem::Ascii(ref x) => &x.span,
1186            ClassSetItem::Perl(ref x) => &x.span,
1187            ClassSetItem::Unicode(ref x) => &x.span,
1188            ClassSetItem::Bracketed(ref x) => &x.span,
1189            ClassSetItem::Union(ref x) => &x.span,
1190        }
1191    }
1192}
1193
1194/// A single character class range in a set.
1195#[derive(Clone, Debug, Eq, PartialEq)]
1196#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1197pub struct ClassSetRange {
1198    /// The span of this range.
1199    pub span: Span,
1200    /// The start of this range.
1201    pub start: Literal,
1202    /// The end of this range.
1203    pub end: Literal,
1204}
1205
1206impl ClassSetRange {
1207    /// Returns true if and only if this character class range is valid.
1208    ///
1209    /// The only case where a range is invalid is if its start is greater than
1210    /// its end.
1211    pub fn is_valid(&self) -> bool {
1212        self.start.c <= self.end.c
1213    }
1214}
1215
1216/// A union of items inside a character class set.
1217#[derive(Clone, Debug, Eq, PartialEq)]
1218#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1219pub struct ClassSetUnion {
1220    /// The span of the items in this operation. e.g., the `a-z0-9` in
1221    /// `[^a-z0-9]`
1222    pub span: Span,
1223    /// The sequence of items that make up this union.
1224    pub items: Vec<ClassSetItem>,
1225}
1226
1227impl ClassSetUnion {
1228    /// Push a new item in this union.
1229    ///
1230    /// The ending position of this union's span is updated to the ending
1231    /// position of the span of the item given. If the union is empty, then
1232    /// the starting position of this union is set to the starting position
1233    /// of this item.
1234    ///
1235    /// In other words, if you only use this method to add items to a union
1236    /// and you set the spans on each item correctly, then you should never
1237    /// need to adjust the span of the union directly.
1238    pub fn push(&mut self, item: ClassSetItem) {
1239        if self.items.is_empty() {
1240            self.span.start = item.span().start;
1241        }
1242        self.span.end = item.span().end;
1243        self.items.push(item);
1244    }
1245
1246    /// Return this union as a character class set item.
1247    ///
1248    /// If this union contains zero items, then an empty union is
1249    /// returned. If this concatenation contains exactly 1 item, then the
1250    /// corresponding item is returned. Otherwise, ClassSetItem::Union is
1251    /// returned.
1252    pub fn into_item(mut self) -> ClassSetItem {
1253        match self.items.len() {
1254            0 => ClassSetItem::Empty(self.span),
1255            1 => self.items.pop().unwrap(),
1256            _ => ClassSetItem::Union(self),
1257        }
1258    }
1259}
1260
1261/// A Unicode character class set operation.
1262#[derive(Clone, Debug, Eq, PartialEq)]
1263#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1264pub struct ClassSetBinaryOp {
1265    /// The span of this operation. e.g., the `a-z--[h-p]` in `[a-z--h-p]`.
1266    pub span: Span,
1267    /// The type of this set operation.
1268    pub kind: ClassSetBinaryOpKind,
1269    /// The left hand side of the operation.
1270    pub lhs: Box<ClassSet>,
1271    /// The right hand side of the operation.
1272    pub rhs: Box<ClassSet>,
1273}
1274
1275/// The type of a Unicode character class set operation.
1276///
1277/// Note that this doesn't explicitly represent union since there is no
1278/// explicit union operator. Concatenation inside a character class corresponds
1279/// to the union operation.
1280#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1281#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1282pub enum ClassSetBinaryOpKind {
1283    /// The intersection of two sets, e.g., `\pN&&[a-z]`.
1284    Intersection,
1285    /// The difference of two sets, e.g., `\pN--[0-9]`.
1286    Difference,
1287    /// The symmetric difference of two sets. The symmetric difference is the
1288    /// set of elements belonging to one but not both sets.
1289    /// e.g., `[\pL~~[:ascii:]]`.
1290    SymmetricDifference,
1291}
1292
1293/// A single zero-width assertion.
1294#[derive(Clone, Debug, Eq, PartialEq)]
1295#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1296pub struct Assertion {
1297    /// The span of this assertion.
1298    pub span: Span,
1299    /// The assertion kind, e.g., `\b` or `^`.
1300    pub kind: AssertionKind,
1301}
1302
1303/// An assertion kind.
1304#[derive(Clone, Debug, Eq, PartialEq)]
1305#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1306pub enum AssertionKind {
1307    /// `^`
1308    StartLine,
1309    /// `$`
1310    EndLine,
1311    /// `\A`
1312    StartText,
1313    /// `\z`
1314    EndText,
1315    /// `\b`
1316    WordBoundary,
1317    /// `\B`
1318    NotWordBoundary,
1319    /// `\b{start}`
1320    WordBoundaryStart,
1321    /// `\b{end}`
1322    WordBoundaryEnd,
1323    /// `\<` (alias for `\b{start}`)
1324    WordBoundaryStartAngle,
1325    /// `\>` (alias for `\b{end}`)
1326    WordBoundaryEndAngle,
1327    /// `\b{start-half}`
1328    WordBoundaryStartHalf,
1329    /// `\b{end-half}`
1330    WordBoundaryEndHalf,
1331}
1332
1333/// A repetition operation applied to a regular expression.
1334#[derive(Clone, Debug, Eq, PartialEq)]
1335#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1336pub struct Repetition {
1337    /// The span of this operation.
1338    pub span: Span,
1339    /// The actual operation.
1340    pub op: RepetitionOp,
1341    /// Whether this operation was applied greedily or not.
1342    pub greedy: bool,
1343    /// The regular expression under repetition.
1344    pub ast: Box<Ast>,
1345}
1346
1347/// The repetition operator itself.
1348#[derive(Clone, Debug, Eq, PartialEq)]
1349#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1350pub struct RepetitionOp {
1351    /// The span of this operator. This includes things like `+`, `*?` and
1352    /// `{m,n}`.
1353    pub span: Span,
1354    /// The type of operation.
1355    pub kind: RepetitionKind,
1356}
1357
1358/// The kind of a repetition operator.
1359#[derive(Clone, Debug, Eq, PartialEq)]
1360#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1361pub enum RepetitionKind {
1362    /// `?`
1363    ZeroOrOne,
1364    /// `*`
1365    ZeroOrMore,
1366    /// `+`
1367    OneOrMore,
1368    /// `{m,n}`
1369    Range(RepetitionRange),
1370}
1371
1372/// A range repetition operator.
1373#[derive(Clone, Debug, Eq, PartialEq)]
1374#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1375pub enum RepetitionRange {
1376    /// `{m}`
1377    Exactly(u32),
1378    /// `{m,}`
1379    AtLeast(u32),
1380    /// `{m,n}`
1381    Bounded(u32, u32),
1382}
1383
1384impl RepetitionRange {
1385    /// Returns true if and only if this repetition range is valid.
1386    ///
1387    /// The only case where a repetition range is invalid is if it is bounded
1388    /// and its start is greater than its end.
1389    pub fn is_valid(&self) -> bool {
1390        match *self {
1391            RepetitionRange::Bounded(s, e) if s > e => false,
1392            _ => true,
1393        }
1394    }
1395}
1396
1397/// A grouped regular expression.
1398///
1399/// This includes both capturing and non-capturing groups. This does **not**
1400/// include flag-only groups like `(?is)`, but does contain any group that
1401/// contains a sub-expression, e.g., `(a)`, `(?P<name>a)`, `(?:a)` and
1402/// `(?is:a)`.
1403#[derive(Clone, Debug, Eq, PartialEq)]
1404#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1405pub struct Group {
1406    /// The span of this group.
1407    pub span: Span,
1408    /// The kind of this group.
1409    pub kind: GroupKind,
1410    /// The regular expression in this group.
1411    pub ast: Box<Ast>,
1412}
1413
1414impl Group {
1415    /// If this group is non-capturing, then this returns the (possibly empty)
1416    /// set of flags. Otherwise, `None` is returned.
1417    pub fn flags(&self) -> Option<&Flags> {
1418        match self.kind {
1419            GroupKind::NonCapturing(ref flags) => Some(flags),
1420            _ => None,
1421        }
1422    }
1423
1424    /// Returns true if and only if this group is capturing.
1425    pub fn is_capturing(&self) -> bool {
1426        match self.kind {
1427            GroupKind::CaptureIndex(_) | GroupKind::CaptureName { .. } => true,
1428            GroupKind::NonCapturing(_) => false,
1429        }
1430    }
1431
1432    /// Returns the capture index of this group, if this is a capturing group.
1433    ///
1434    /// This returns a capture index precisely when `is_capturing` is `true`.
1435    pub fn capture_index(&self) -> Option<u32> {
1436        match self.kind {
1437            GroupKind::CaptureIndex(i) => Some(i),
1438            GroupKind::CaptureName { ref name, .. } => Some(name.index),
1439            GroupKind::NonCapturing(_) => None,
1440        }
1441    }
1442}
1443
1444/// The kind of a group.
1445#[derive(Clone, Debug, Eq, PartialEq)]
1446#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1447pub enum GroupKind {
1448    /// `(a)`
1449    CaptureIndex(u32),
1450    /// `(?<name>a)` or `(?P<name>a)`
1451    CaptureName {
1452        /// True if the `?P<` syntax is used and false if the `?<` syntax is used.
1453        starts_with_p: bool,
1454        /// The capture name.
1455        name: CaptureName,
1456    },
1457    /// `(?:a)` and `(?i:a)`
1458    NonCapturing(Flags),
1459}
1460
1461/// A capture name.
1462///
1463/// This corresponds to the name itself between the angle brackets in, e.g.,
1464/// `(?P<foo>expr)`.
1465#[derive(Clone, Debug, Eq, PartialEq)]
1466pub struct CaptureName {
1467    /// The span of this capture name.
1468    pub span: Span,
1469    /// The capture name.
1470    pub name: String,
1471    /// The capture index.
1472    pub index: u32,
1473}
1474
1475#[cfg(feature = "arbitrary")]
1476impl arbitrary::Arbitrary<'_> for CaptureName {
1477    fn arbitrary(
1478        u: &mut arbitrary::Unstructured,
1479    ) -> arbitrary::Result<CaptureName> {
1480        let len = u.arbitrary_len::<char>()?;
1481        if len == 0 {
1482            return Err(arbitrary::Error::NotEnoughData);
1483        }
1484        let mut name: String = String::new();
1485        for _ in 0..len {
1486            let ch: char = u.arbitrary()?;
1487            let cp = u32::from(ch);
1488            let ascii_letter_offset = u8::try_from(cp % 26).unwrap();
1489            let ascii_letter = b'a' + ascii_letter_offset;
1490            name.push(char::from(ascii_letter));
1491        }
1492        Ok(CaptureName { span: u.arbitrary()?, name, index: u.arbitrary()? })
1493    }
1494
1495    fn size_hint(depth: usize) -> (usize, Option<usize>) {
1496        arbitrary::size_hint::and_all(&[
1497            Span::size_hint(depth),
1498            usize::size_hint(depth),
1499            u32::size_hint(depth),
1500        ])
1501    }
1502}
1503
1504/// A group of flags that is not applied to a particular regular expression.
1505#[derive(Clone, Debug, Eq, PartialEq)]
1506#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1507pub struct SetFlags {
1508    /// The span of these flags, including the grouping parentheses.
1509    pub span: Span,
1510    /// The actual sequence of flags.
1511    pub flags: Flags,
1512}
1513
1514/// A group of flags.
1515///
1516/// This corresponds only to the sequence of flags themselves, e.g., `is-u`.
1517#[derive(Clone, Debug, Eq, PartialEq)]
1518#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1519pub struct Flags {
1520    /// The span of this group of flags.
1521    pub span: Span,
1522    /// A sequence of flag items. Each item is either a flag or a negation
1523    /// operator.
1524    pub items: Vec<FlagsItem>,
1525}
1526
1527impl Flags {
1528    /// Add the given item to this sequence of flags.
1529    ///
1530    /// If the item was added successfully, then `None` is returned. If the
1531    /// given item is a duplicate, then `Some(i)` is returned, where
1532    /// `items[i].kind == item.kind`.
1533    pub fn add_item(&mut self, item: FlagsItem) -> Option<usize> {
1534        for (i, x) in self.items.iter().enumerate() {
1535            if x.kind == item.kind {
1536                return Some(i);
1537            }
1538        }
1539        self.items.push(item);
1540        None
1541    }
1542
1543    /// Returns the state of the given flag in this set.
1544    ///
1545    /// If the given flag is in the set but is negated, then `Some(false)` is
1546    /// returned.
1547    ///
1548    /// If the given flag is in the set and is not negated, then `Some(true)`
1549    /// is returned.
1550    ///
1551    /// Otherwise, `None` is returned.
1552    pub fn flag_state(&self, flag: Flag) -> Option<bool> {
1553        let mut negated = false;
1554        for x in &self.items {
1555            match x.kind {
1556                FlagsItemKind::Negation => {
1557                    negated = true;
1558                }
1559                FlagsItemKind::Flag(ref xflag) if xflag == &flag => {
1560                    return Some(!negated);
1561                }
1562                _ => {}
1563            }
1564        }
1565        None
1566    }
1567}
1568
1569/// A single item in a group of flags.
1570#[derive(Clone, Debug, Eq, PartialEq)]
1571#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1572pub struct FlagsItem {
1573    /// The span of this item.
1574    pub span: Span,
1575    /// The kind of this item.
1576    pub kind: FlagsItemKind,
1577}
1578
1579/// The kind of an item in a group of flags.
1580#[derive(Clone, Debug, Eq, PartialEq)]
1581#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1582pub enum FlagsItemKind {
1583    /// A negation operator applied to all subsequent flags in the enclosing
1584    /// group.
1585    Negation,
1586    /// A single flag in a group.
1587    Flag(Flag),
1588}
1589
1590impl FlagsItemKind {
1591    /// Returns true if and only if this item is a negation operator.
1592    pub fn is_negation(&self) -> bool {
1593        match *self {
1594            FlagsItemKind::Negation => true,
1595            _ => false,
1596        }
1597    }
1598}
1599
1600/// A single flag.
1601#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1602#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
1603pub enum Flag {
1604    /// `i`
1605    CaseInsensitive,
1606    /// `m`
1607    MultiLine,
1608    /// `s`
1609    DotMatchesNewLine,
1610    /// `U`
1611    SwapGreed,
1612    /// `u`
1613    Unicode,
1614    /// `R`
1615    CRLF,
1616    /// `x`
1617    IgnoreWhitespace,
1618}
1619
1620/// A custom `Drop` impl is used for `Ast` such that it uses constant stack
1621/// space but heap space proportional to the depth of the `Ast`.
1622impl Drop for Ast {
1623    fn drop(&mut self) {
1624        use core::mem;
1625
1626        match *self {
1627            Ast::Empty(_)
1628            | Ast::Flags(_)
1629            | Ast::Literal(_)
1630            | Ast::Dot(_)
1631            | Ast::Assertion(_)
1632            | Ast::ClassUnicode(_)
1633            | Ast::ClassPerl(_)
1634            // Bracketed classes are recursive, they get their own Drop impl.
1635            | Ast::ClassBracketed(_) => return,
1636            Ast::Repetition(ref x) if !x.ast.has_subexprs() => return,
1637            Ast::Group(ref x) if !x.ast.has_subexprs() => return,
1638            Ast::Alternation(ref x) if x.asts.is_empty() => return,
1639            Ast::Concat(ref x) if x.asts.is_empty() => return,
1640            _ => {}
1641        }
1642
1643        let empty_span = || Span::splat(Position::new(0, 0, 0));
1644        let empty_ast = || Ast::empty(empty_span());
1645        let mut stack = vec![mem::replace(self, empty_ast())];
1646        while let Some(mut ast) = stack.pop() {
1647            match ast {
1648                Ast::Empty(_)
1649                | Ast::Flags(_)
1650                | Ast::Literal(_)
1651                | Ast::Dot(_)
1652                | Ast::Assertion(_)
1653                | Ast::ClassUnicode(_)
1654                | Ast::ClassPerl(_)
1655                // Bracketed classes are recursive, so they get their own Drop
1656                // impl.
1657                | Ast::ClassBracketed(_) => {}
1658                Ast::Repetition(ref mut x) => {
1659                    stack.push(mem::replace(&mut x.ast, empty_ast()));
1660                }
1661                Ast::Group(ref mut x) => {
1662                    stack.push(mem::replace(&mut x.ast, empty_ast()));
1663                }
1664                Ast::Alternation(ref mut x) => {
1665                    stack.extend(x.asts.drain(..));
1666                }
1667                Ast::Concat(ref mut x) => {
1668                    stack.extend(x.asts.drain(..));
1669                }
1670            }
1671        }
1672    }
1673}
1674
1675/// A custom `Drop` impl is used for `ClassSet` such that it uses constant
1676/// stack space but heap space proportional to the depth of the `ClassSet`.
1677impl Drop for ClassSet {
1678    fn drop(&mut self) {
1679        use core::mem;
1680
1681        match *self {
1682            ClassSet::Item(ref item) => match *item {
1683                ClassSetItem::Empty(_)
1684                | ClassSetItem::Literal(_)
1685                | ClassSetItem::Range(_)
1686                | ClassSetItem::Ascii(_)
1687                | ClassSetItem::Unicode(_)
1688                | ClassSetItem::Perl(_) => return,
1689                ClassSetItem::Bracketed(ref x) => {
1690                    if x.kind.is_empty() {
1691                        return;
1692                    }
1693                }
1694                ClassSetItem::Union(ref x) => {
1695                    if x.items.is_empty() {
1696                        return;
1697                    }
1698                }
1699            },
1700            ClassSet::BinaryOp(ref op) => {
1701                if op.lhs.is_empty() && op.rhs.is_empty() {
1702                    return;
1703                }
1704            }
1705        }
1706
1707        let empty_span = || Span::splat(Position::new(0, 0, 0));
1708        let empty_set = || ClassSet::Item(ClassSetItem::Empty(empty_span()));
1709        let mut stack = vec![mem::replace(self, empty_set())];
1710        while let Some(mut set) = stack.pop() {
1711            match set {
1712                ClassSet::Item(ref mut item) => match *item {
1713                    ClassSetItem::Empty(_)
1714                    | ClassSetItem::Literal(_)
1715                    | ClassSetItem::Range(_)
1716                    | ClassSetItem::Ascii(_)
1717                    | ClassSetItem::Unicode(_)
1718                    | ClassSetItem::Perl(_) => {}
1719                    ClassSetItem::Bracketed(ref mut x) => {
1720                        stack.push(mem::replace(&mut x.kind, empty_set()));
1721                    }
1722                    ClassSetItem::Union(ref mut x) => {
1723                        stack.extend(x.items.drain(..).map(ClassSet::Item));
1724                    }
1725                },
1726                ClassSet::BinaryOp(ref mut op) => {
1727                    stack.push(mem::replace(&mut op.lhs, empty_set()));
1728                    stack.push(mem::replace(&mut op.rhs, empty_set()));
1729                }
1730            }
1731        }
1732    }
1733}
1734
1735#[cfg(test)]
1736mod tests {
1737    use super::*;
1738
1739    // We use a thread with an explicit stack size to test that our destructor
1740    // for Ast can handle arbitrarily sized expressions in constant stack
1741    // space. In case we run on a platform without threads (WASM?), we limit
1742    // this test to Windows/Unix.
1743    #[test]
1744    fn position_ord_is_consistent_with_eq() {
1745        let a = Position::new(0, 1, 1);
1746        let b = Position::new(0, 9, 9);
1747        assert_ne!(a, b);
1748        assert_ne!(a.cmp(&b), core::cmp::Ordering::Equal);
1749
1750        let mut set = alloc::collections::BTreeSet::new();
1751        set.insert(a);
1752        set.insert(b);
1753        assert_eq!(set.len(), 2);
1754    }
1755
1756    #[test]
1757    #[cfg(any(unix, windows))]
1758    fn no_stack_overflow_on_drop() {
1759        use std::thread;
1760
1761        let run = || {
1762            let span = || Span::splat(Position::new(0, 0, 0));
1763            let mut ast = Ast::empty(span());
1764            for i in 0..200 {
1765                ast = Ast::group(Group {
1766                    span: span(),
1767                    kind: GroupKind::CaptureIndex(i),
1768                    ast: Box::new(ast),
1769                });
1770            }
1771            assert!(!ast.is_empty());
1772        };
1773
1774        // We run our test on a thread with a small stack size so we can
1775        // force the issue more easily.
1776        //
1777        // NOTE(2023-03-21): It turns out that some platforms (like FreeBSD)
1778        // will just barf with very small stack sizes. So we bump this up a bit
1779        // to give more room to breath. When I did this, I confirmed that if
1780        // I remove the custom `Drop` impl for `Ast`, then this test does
1781        // indeed still fail with a stack overflow. (At the time of writing, I
1782        // had to bump it all the way up to 32K before the test would pass even
1783        // without the custom `Drop` impl. So 16K seems like a safe number
1784        // here.)
1785        //
1786        // See: https://github.com/rust-lang/regex/issues/967
1787        thread::Builder::new()
1788            .stack_size(16 << 10)
1789            .spawn(run)
1790            .unwrap()
1791            .join()
1792            .unwrap();
1793    }
1794
1795    // This tests that our `Ast` has a reasonable size. This isn't a hard rule
1796    // and it can be increased if given a good enough reason. But this test
1797    // exists because the size of `Ast` was at one point over 200 bytes on a
1798    // 64-bit target. Wow.
1799    #[test]
1800    fn ast_size() {
1801        let max = 2 * core::mem::size_of::<usize>();
1802        let size = core::mem::size_of::<Ast>();
1803        assert!(
1804            size <= max,
1805            "Ast size of {size} bytes is bigger than suggested max {max}",
1806        );
1807    }
1808}