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}