Import 'regex-syntax' package vesion 0.6.17
* Add OWNERS
Bug: 152884384
Test: make
Change-Id: I760a69ffc851039ceaff58980deece308a426aed
diff --git a/src/ast/mod.rs b/src/ast/mod.rs
new file mode 100644
index 0000000..7179f2d
--- /dev/null
+++ b/src/ast/mod.rs
@@ -0,0 +1,1502 @@
+/*!
+Defines an abstract syntax for regular expressions.
+*/
+
+use std::cmp::Ordering;
+use std::error;
+use std::fmt;
+
+pub use ast::visitor::{visit, Visitor};
+
+pub mod parse;
+pub mod print;
+mod visitor;
+
+/// An error that occurred while parsing a regular expression into an abstract
+/// syntax tree.
+///
+/// Note that note all ASTs represents a valid regular expression. For example,
+/// an AST is constructed without error for `\p{Quux}`, but `Quux` is not a
+/// valid Unicode property name. That particular error is reported when
+/// translating an AST to the high-level intermediate representation (`HIR`).
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Error {
+ /// The kind of error.
+ kind: ErrorKind,
+ /// The original pattern that the parser generated the error from. Every
+ /// span in an error is a valid range into this string.
+ pattern: String,
+ /// The span of this error.
+ span: Span,
+}
+
+impl Error {
+ /// Return the type of this error.
+ pub fn kind(&self) -> &ErrorKind {
+ &self.kind
+ }
+
+ /// The original pattern string in which this error occurred.
+ ///
+ /// Every span reported by this error is reported in terms of this string.
+ pub fn pattern(&self) -> &str {
+ &self.pattern
+ }
+
+ /// Return the span at which this error occurred.
+ pub fn span(&self) -> &Span {
+ &self.span
+ }
+
+ /// Return an auxiliary span. This span exists only for some errors that
+ /// benefit from being able to point to two locations in the original
+ /// regular expression. For example, "duplicate" errors will have the
+ /// main error position set to the duplicate occurrence while its
+ /// auxiliary span will be set to the initial occurrence.
+ pub fn auxiliary_span(&self) -> Option<&Span> {
+ use self::ErrorKind::*;
+ match self.kind {
+ FlagDuplicate { ref original } => Some(original),
+ FlagRepeatedNegation { ref original, .. } => Some(original),
+ GroupNameDuplicate { ref original, .. } => Some(original),
+ _ => None,
+ }
+ }
+}
+
+/// The type of an error that occurred while building an AST.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum ErrorKind {
+ /// The capturing group limit was exceeded.
+ ///
+ /// Note that this represents a limit on the total number of capturing
+ /// groups in a regex and not necessarily the number of nested capturing
+ /// groups. That is, the nest limit can be low and it is still possible for
+ /// this error to occur.
+ CaptureLimitExceeded,
+ /// An invalid escape sequence was found in a character class set.
+ ClassEscapeInvalid,
+ /// An invalid character class range was found. An invalid range is any
+ /// range where the start is greater than the end.
+ ClassRangeInvalid,
+ /// An invalid range boundary was found in a character class. Range
+ /// boundaries must be a single literal codepoint, but this error indicates
+ /// that something else was found, such as a nested class.
+ ClassRangeLiteral,
+ /// An opening `[` was found with no corresponding closing `]`.
+ ClassUnclosed,
+ /// Note that this error variant is no longer used. Namely, a decimal
+ /// number can only appear as a repetition quantifier. When the number
+ /// in a repetition quantifier is empty, then it gets its own specialized
+ /// error, `RepetitionCountDecimalEmpty`.
+ DecimalEmpty,
+ /// An invalid decimal number was given where one was expected.
+ DecimalInvalid,
+ /// A bracketed hex literal was empty.
+ EscapeHexEmpty,
+ /// A bracketed hex literal did not correspond to a Unicode scalar value.
+ EscapeHexInvalid,
+ /// An invalid hexadecimal digit was found.
+ EscapeHexInvalidDigit,
+ /// EOF was found before an escape sequence was completed.
+ EscapeUnexpectedEof,
+ /// An unrecognized escape sequence.
+ EscapeUnrecognized,
+ /// A dangling negation was used when setting flags, e.g., `i-`.
+ FlagDanglingNegation,
+ /// A flag was used twice, e.g., `i-i`.
+ FlagDuplicate {
+ /// The position of the original flag. The error position
+ /// points to the duplicate flag.
+ original: Span,
+ },
+ /// The negation operator was used twice, e.g., `-i-s`.
+ FlagRepeatedNegation {
+ /// The position of the original negation operator. The error position
+ /// points to the duplicate negation operator.
+ original: Span,
+ },
+ /// Expected a flag but got EOF, e.g., `(?`.
+ FlagUnexpectedEof,
+ /// Unrecognized flag, e.g., `a`.
+ FlagUnrecognized,
+ /// A duplicate capture name was found.
+ GroupNameDuplicate {
+ /// The position of the initial occurrence of the capture name. The
+ /// error position itself points to the duplicate occurrence.
+ original: Span,
+ },
+ /// A capture group name is empty, e.g., `(?P<>abc)`.
+ GroupNameEmpty,
+ /// An invalid character was seen for a capture group name. This includes
+ /// errors where the first character is a digit (even though subsequent
+ /// characters are allowed to be digits).
+ GroupNameInvalid,
+ /// A closing `>` could not be found for a capture group name.
+ GroupNameUnexpectedEof,
+ /// An unclosed group, e.g., `(ab`.
+ ///
+ /// The span of this error corresponds to the unclosed parenthesis.
+ GroupUnclosed,
+ /// An unopened group, e.g., `ab)`.
+ GroupUnopened,
+ /// The nest limit was exceeded. The limit stored here is the limit
+ /// configured in the parser.
+ NestLimitExceeded(u32),
+ /// The range provided in a counted repetition operator is invalid. The
+ /// range is invalid if the start is greater than the end.
+ RepetitionCountInvalid,
+ /// An opening `{` was not followed by a valid decimal value.
+ /// For example, `x{}` or `x{]}` would fail.
+ RepetitionCountDecimalEmpty,
+ /// An opening `{` was found with no corresponding closing `}`.
+ RepetitionCountUnclosed,
+ /// A repetition operator was applied to a missing sub-expression. This
+ /// occurs, for example, in the regex consisting of just a `*` or even
+ /// `(?i)*`. It is, however, possible to create a repetition operating on
+ /// an empty sub-expression. For example, `()*` is still considered valid.
+ RepetitionMissing,
+ /// The Unicode class is not valid. This typically occurs when a `\p` is
+ /// followed by something other than a `{`.
+ UnicodeClassInvalid,
+ /// When octal support is disabled, this error is produced when an octal
+ /// escape is used. The octal escape is assumed to be an invocation of
+ /// a backreference, which is the common case.
+ UnsupportedBackreference,
+ /// When syntax similar to PCRE's look-around is used, this error is
+ /// returned. Some example syntaxes that are rejected include, but are
+ /// not necessarily limited to, `(?=re)`, `(?!re)`, `(?<=re)` and
+ /// `(?<!re)`. Note that all of these syntaxes are otherwise invalid; this
+ /// error is used to improve the user experience.
+ UnsupportedLookAround,
+ /// Hints that destructuring should not be exhaustive.
+ ///
+ /// This enum may grow additional variants, so this makes sure clients
+ /// don't count on exhaustive matching. (Otherwise, adding a new variant
+ /// could break existing code.)
+ #[doc(hidden)]
+ __Nonexhaustive,
+}
+
+impl error::Error for Error {
+ // TODO: Remove this method entirely on the next breaking semver release.
+ #[allow(deprecated)]
+ fn description(&self) -> &str {
+ use self::ErrorKind::*;
+ match self.kind {
+ CaptureLimitExceeded => "capture group limit exceeded",
+ ClassEscapeInvalid => "invalid escape sequence in character class",
+ ClassRangeInvalid => "invalid character class range",
+ ClassRangeLiteral => "invalid range boundary, must be a literal",
+ ClassUnclosed => "unclosed character class",
+ DecimalEmpty => "empty decimal literal",
+ DecimalInvalid => "invalid decimal literal",
+ EscapeHexEmpty => "empty hexadecimal literal",
+ EscapeHexInvalid => "invalid hexadecimal literal",
+ EscapeHexInvalidDigit => "invalid hexadecimal digit",
+ EscapeUnexpectedEof => "unexpected eof (escape sequence)",
+ EscapeUnrecognized => "unrecognized escape sequence",
+ FlagDanglingNegation => "dangling flag negation operator",
+ FlagDuplicate { .. } => "duplicate flag",
+ FlagRepeatedNegation { .. } => "repeated negation",
+ FlagUnexpectedEof => "unexpected eof (flag)",
+ FlagUnrecognized => "unrecognized flag",
+ GroupNameDuplicate { .. } => "duplicate capture group name",
+ GroupNameEmpty => "empty capture group name",
+ GroupNameInvalid => "invalid capture group name",
+ GroupNameUnexpectedEof => "unclosed capture group name",
+ GroupUnclosed => "unclosed group",
+ GroupUnopened => "unopened group",
+ NestLimitExceeded(_) => "nest limit exceeded",
+ RepetitionCountInvalid => "invalid repetition count range",
+ RepetitionCountUnclosed => "unclosed counted repetition",
+ RepetitionMissing => "repetition operator missing expression",
+ UnicodeClassInvalid => "invalid Unicode character class",
+ UnsupportedBackreference => "backreferences are not supported",
+ UnsupportedLookAround => "look-around is not supported",
+ _ => unreachable!(),
+ }
+ }
+}
+
+impl fmt::Display for Error {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ ::error::Formatter::from(self).fmt(f)
+ }
+}
+
+impl fmt::Display for ErrorKind {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ use self::ErrorKind::*;
+ match *self {
+ CaptureLimitExceeded => write!(
+ f,
+ "exceeded the maximum number of \
+ capturing groups ({})",
+ ::std::u32::MAX
+ ),
+ ClassEscapeInvalid => {
+ write!(f, "invalid escape sequence found in character class")
+ }
+ ClassRangeInvalid => write!(
+ f,
+ "invalid character class range, \
+ the start must be <= the end"
+ ),
+ ClassRangeLiteral => {
+ write!(f, "invalid range boundary, must be a literal")
+ }
+ ClassUnclosed => write!(f, "unclosed character class"),
+ DecimalEmpty => write!(f, "decimal literal empty"),
+ DecimalInvalid => write!(f, "decimal literal invalid"),
+ EscapeHexEmpty => write!(f, "hexadecimal literal empty"),
+ EscapeHexInvalid => {
+ write!(f, "hexadecimal literal is not a Unicode scalar value")
+ }
+ EscapeHexInvalidDigit => write!(f, "invalid hexadecimal digit"),
+ EscapeUnexpectedEof => write!(
+ f,
+ "incomplete escape sequence, \
+ reached end of pattern prematurely"
+ ),
+ EscapeUnrecognized => write!(f, "unrecognized escape sequence"),
+ FlagDanglingNegation => {
+ write!(f, "dangling flag negation operator")
+ }
+ FlagDuplicate { .. } => write!(f, "duplicate flag"),
+ FlagRepeatedNegation { .. } => {
+ write!(f, "flag negation operator repeated")
+ }
+ FlagUnexpectedEof => {
+ write!(f, "expected flag but got end of regex")
+ }
+ FlagUnrecognized => write!(f, "unrecognized flag"),
+ GroupNameDuplicate { .. } => {
+ write!(f, "duplicate capture group name")
+ }
+ GroupNameEmpty => write!(f, "empty capture group name"),
+ GroupNameInvalid => write!(f, "invalid capture group character"),
+ GroupNameUnexpectedEof => write!(f, "unclosed capture group name"),
+ GroupUnclosed => write!(f, "unclosed group"),
+ GroupUnopened => write!(f, "unopened group"),
+ NestLimitExceeded(limit) => write!(
+ f,
+ "exceed the maximum number of \
+ nested parentheses/brackets ({})",
+ limit
+ ),
+ RepetitionCountInvalid => write!(
+ f,
+ "invalid repetition count range, \
+ the start must be <= the end"
+ ),
+ RepetitionCountDecimalEmpty => {
+ write!(f, "repetition quantifier expects a valid decimal")
+ }
+ RepetitionCountUnclosed => {
+ write!(f, "unclosed counted repetition")
+ }
+ RepetitionMissing => {
+ write!(f, "repetition operator missing expression")
+ }
+ UnicodeClassInvalid => {
+ write!(f, "invalid Unicode character class")
+ }
+ UnsupportedBackreference => {
+ write!(f, "backreferences are not supported")
+ }
+ UnsupportedLookAround => write!(
+ f,
+ "look-around, including look-ahead and look-behind, \
+ is not supported"
+ ),
+ _ => unreachable!(),
+ }
+ }
+}
+
+/// Span represents the position information of a single AST item.
+///
+/// All span positions are absolute byte offsets that can be used on the
+/// original regular expression that was parsed.
+#[derive(Clone, Copy, Eq, PartialEq)]
+pub struct Span {
+ /// The start byte offset.
+ pub start: Position,
+ /// The end byte offset.
+ pub end: Position,
+}
+
+impl fmt::Debug for Span {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ write!(f, "Span({:?}, {:?})", self.start, self.end)
+ }
+}
+
+impl Ord for Span {
+ fn cmp(&self, other: &Span) -> Ordering {
+ (&self.start, &self.end).cmp(&(&other.start, &other.end))
+ }
+}
+
+impl PartialOrd for Span {
+ fn partial_cmp(&self, other: &Span) -> Option<Ordering> {
+ Some(self.cmp(other))
+ }
+}
+
+/// A single position in a regular expression.
+///
+/// A position encodes one half of a span, and include the byte offset, line
+/// number and column number.
+#[derive(Clone, Copy, Eq, PartialEq)]
+pub struct Position {
+ /// The absolute offset of this position, starting at `0` from the
+ /// beginning of the regular expression pattern string.
+ pub offset: usize,
+ /// The line number, starting at `1`.
+ pub line: usize,
+ /// The approximate column number, starting at `1`.
+ pub column: usize,
+}
+
+impl fmt::Debug for Position {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ write!(
+ f,
+ "Position(o: {:?}, l: {:?}, c: {:?})",
+ self.offset, self.line, self.column
+ )
+ }
+}
+
+impl Ord for Position {
+ fn cmp(&self, other: &Position) -> Ordering {
+ self.offset.cmp(&other.offset)
+ }
+}
+
+impl PartialOrd for Position {
+ fn partial_cmp(&self, other: &Position) -> Option<Ordering> {
+ Some(self.cmp(other))
+ }
+}
+
+impl Span {
+ /// Create a new span with the given positions.
+ pub fn new(start: Position, end: Position) -> Span {
+ Span { start: start, end: end }
+ }
+
+ /// Create a new span using the given position as the start and end.
+ pub fn splat(pos: Position) -> Span {
+ Span::new(pos, pos)
+ }
+
+ /// Create a new span by replacing the starting the position with the one
+ /// given.
+ pub fn with_start(self, pos: Position) -> Span {
+ Span { start: pos, ..self }
+ }
+
+ /// Create a new span by replacing the ending the position with the one
+ /// given.
+ pub fn with_end(self, pos: Position) -> Span {
+ Span { end: pos, ..self }
+ }
+
+ /// Returns true if and only if this span occurs on a single line.
+ pub fn is_one_line(&self) -> bool {
+ self.start.line == self.end.line
+ }
+
+ /// Returns true if and only if this span is empty. That is, it points to
+ /// a single position in the concrete syntax of a regular expression.
+ pub fn is_empty(&self) -> bool {
+ self.start.offset == self.end.offset
+ }
+}
+
+impl Position {
+ /// Create a new position with the given information.
+ ///
+ /// `offset` is the absolute offset of the position, starting at `0` from
+ /// the beginning of the regular expression pattern string.
+ ///
+ /// `line` is the line number, starting at `1`.
+ ///
+ /// `column` is the approximate column number, starting at `1`.
+ pub fn new(offset: usize, line: usize, column: usize) -> Position {
+ Position { offset: offset, line: line, column: column }
+ }
+}
+
+/// An abstract syntax tree for a singular expression along with comments
+/// found.
+///
+/// Comments are not stored in the tree itself to avoid complexity. Each
+/// comment contains a span of precisely where it occurred in the original
+/// regular expression.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct WithComments {
+ /// The actual ast.
+ pub ast: Ast,
+ /// All comments found in the original regular expression.
+ pub comments: Vec<Comment>,
+}
+
+/// A comment from a regular expression with an associated span.
+///
+/// A regular expression can only contain comments when the `x` flag is
+/// enabled.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Comment {
+ /// The span of this comment, including the beginning `#` and ending `\n`.
+ pub span: Span,
+ /// The comment text, starting with the first character following the `#`
+ /// and ending with the last character preceding the `\n`.
+ pub comment: String,
+}
+
+/// An abstract syntax tree for a single regular expression.
+///
+/// An `Ast`'s `fmt::Display` implementation uses constant stack space and heap
+/// space proportional to the size of the `Ast`.
+///
+/// This type defines its own destructor that uses constant stack space and
+/// heap space proportional to the size of the `Ast`.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum Ast {
+ /// An empty regex that matches everything.
+ Empty(Span),
+ /// A set of flags, e.g., `(?is)`.
+ Flags(SetFlags),
+ /// A single character literal, which includes escape sequences.
+ Literal(Literal),
+ /// The "any character" class.
+ Dot(Span),
+ /// A single zero-width assertion.
+ Assertion(Assertion),
+ /// A single character class. This includes all forms of character classes
+ /// except for `.`. e.g., `\d`, `\pN`, `[a-z]` and `[[:alpha:]]`.
+ Class(Class),
+ /// A repetition operator applied to an arbitrary regular expression.
+ Repetition(Repetition),
+ /// A grouped regular expression.
+ Group(Group),
+ /// An alternation of regular expressions.
+ Alternation(Alternation),
+ /// A concatenation of regular expressions.
+ Concat(Concat),
+}
+
+impl Ast {
+ /// Return the span of this abstract syntax tree.
+ pub fn span(&self) -> &Span {
+ match *self {
+ Ast::Empty(ref span) => span,
+ Ast::Flags(ref x) => &x.span,
+ Ast::Literal(ref x) => &x.span,
+ Ast::Dot(ref span) => span,
+ Ast::Assertion(ref x) => &x.span,
+ Ast::Class(ref x) => x.span(),
+ Ast::Repetition(ref x) => &x.span,
+ Ast::Group(ref x) => &x.span,
+ Ast::Alternation(ref x) => &x.span,
+ Ast::Concat(ref x) => &x.span,
+ }
+ }
+
+ /// Return true if and only if this Ast is empty.
+ pub fn is_empty(&self) -> bool {
+ match *self {
+ Ast::Empty(_) => true,
+ _ => false,
+ }
+ }
+
+ /// Returns true if and only if this AST has any (including possibly empty)
+ /// subexpressions.
+ fn has_subexprs(&self) -> bool {
+ match *self {
+ Ast::Empty(_)
+ | Ast::Flags(_)
+ | Ast::Literal(_)
+ | Ast::Dot(_)
+ | Ast::Assertion(_) => false,
+ Ast::Class(_)
+ | Ast::Repetition(_)
+ | Ast::Group(_)
+ | Ast::Alternation(_)
+ | Ast::Concat(_) => true,
+ }
+ }
+}
+
+/// Print a display representation of this Ast.
+///
+/// This does not preserve any of the original whitespace formatting that may
+/// have originally been present in the concrete syntax from which this Ast
+/// was generated.
+///
+/// This implementation uses constant stack space and heap space proportional
+/// to the size of the `Ast`.
+impl fmt::Display for Ast {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ use ast::print::Printer;
+ Printer::new().print(self, f)
+ }
+}
+
+/// An alternation of regular expressions.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Alternation {
+ /// The span of this alternation.
+ pub span: Span,
+ /// The alternate regular expressions.
+ pub asts: Vec<Ast>,
+}
+
+impl Alternation {
+ /// Return this alternation as an AST.
+ ///
+ /// If this alternation contains zero ASTs, then Ast::Empty is
+ /// returned. If this alternation contains exactly 1 AST, then the
+ /// corresponding AST is returned. Otherwise, Ast::Alternation is returned.
+ pub fn into_ast(mut self) -> Ast {
+ match self.asts.len() {
+ 0 => Ast::Empty(self.span),
+ 1 => self.asts.pop().unwrap(),
+ _ => Ast::Alternation(self),
+ }
+ }
+}
+
+/// A concatenation of regular expressions.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Concat {
+ /// The span of this concatenation.
+ pub span: Span,
+ /// The concatenation regular expressions.
+ pub asts: Vec<Ast>,
+}
+
+impl Concat {
+ /// Return this concatenation as an AST.
+ ///
+ /// If this concatenation contains zero ASTs, then Ast::Empty is
+ /// returned. If this concatenation contains exactly 1 AST, then the
+ /// corresponding AST is returned. Otherwise, Ast::Concat is returned.
+ pub fn into_ast(mut self) -> Ast {
+ match self.asts.len() {
+ 0 => Ast::Empty(self.span),
+ 1 => self.asts.pop().unwrap(),
+ _ => Ast::Concat(self),
+ }
+ }
+}
+
+/// A single literal expression.
+///
+/// A literal corresponds to a single Unicode scalar value. Literals may be
+/// represented in their literal form, e.g., `a` or in their escaped form,
+/// e.g., `\x61`.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Literal {
+ /// The span of this literal.
+ pub span: Span,
+ /// The kind of this literal.
+ pub kind: LiteralKind,
+ /// The Unicode scalar value corresponding to this literal.
+ pub c: char,
+}
+
+impl Literal {
+ /// If this literal was written as a `\x` hex escape, then this returns
+ /// the corresponding byte value. Otherwise, this returns `None`.
+ pub fn byte(&self) -> Option<u8> {
+ let short_hex = LiteralKind::HexFixed(HexLiteralKind::X);
+ if self.c as u32 <= 255 && self.kind == short_hex {
+ Some(self.c as u8)
+ } else {
+ None
+ }
+ }
+}
+
+/// The kind of a single literal expression.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum LiteralKind {
+ /// The literal is written verbatim, e.g., `a` or `☃`.
+ Verbatim,
+ /// The literal is written as an escape because it is punctuation, e.g.,
+ /// `\*` or `\[`.
+ Punctuation,
+ /// The literal is written as an octal escape, e.g., `\141`.
+ Octal,
+ /// The literal is written as a hex code with a fixed number of digits
+ /// depending on the type of the escape, e.g., `\x61` or or `\u0061` or
+ /// `\U00000061`.
+ HexFixed(HexLiteralKind),
+ /// The literal is written as a hex code with a bracketed number of
+ /// digits. The only restriction is that the bracketed hex code must refer
+ /// to a valid Unicode scalar value.
+ HexBrace(HexLiteralKind),
+ /// The literal is written as a specially recognized escape, e.g., `\f`
+ /// or `\n`.
+ Special(SpecialLiteralKind),
+}
+
+/// The type of a special literal.
+///
+/// A special literal is a special escape sequence recognized by the regex
+/// parser, e.g., `\f` or `\n`.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum SpecialLiteralKind {
+ /// Bell, spelled `\a` (`\x07`).
+ Bell,
+ /// Form feed, spelled `\f` (`\x0C`).
+ FormFeed,
+ /// Tab, spelled `\t` (`\x09`).
+ Tab,
+ /// Line feed, spelled `\n` (`\x0A`).
+ LineFeed,
+ /// Carriage return, spelled `\r` (`\x0D`).
+ CarriageReturn,
+ /// Vertical tab, spelled `\v` (`\x0B`).
+ VerticalTab,
+ /// Space, spelled `\ ` (`\x20`). Note that this can only appear when
+ /// parsing in verbose mode.
+ Space,
+}
+
+/// The type of a Unicode hex literal.
+///
+/// Note that all variants behave the same when used with brackets. They only
+/// differ when used without brackets in the number of hex digits that must
+/// follow.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum HexLiteralKind {
+ /// A `\x` prefix. When used without brackets, this form is limited to
+ /// two digits.
+ X,
+ /// A `\u` prefix. When used without brackets, this form is limited to
+ /// four digits.
+ UnicodeShort,
+ /// A `\U` prefix. When used without brackets, this form is limited to
+ /// eight digits.
+ UnicodeLong,
+}
+
+impl HexLiteralKind {
+ /// The number of digits that must be used with this literal form when
+ /// used without brackets. When used with brackets, there is no
+ /// restriction on the number of digits.
+ pub fn digits(&self) -> u32 {
+ match *self {
+ HexLiteralKind::X => 2,
+ HexLiteralKind::UnicodeShort => 4,
+ HexLiteralKind::UnicodeLong => 8,
+ }
+ }
+}
+
+/// A single character class expression.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum Class {
+ /// A Unicode character class, e.g., `\pL` or `\p{Greek}`.
+ Unicode(ClassUnicode),
+ /// A perl character class, e.g., `\d` or `\W`.
+ Perl(ClassPerl),
+ /// A bracketed character class set, which may contain zero or more
+ /// character ranges and/or zero or more nested classes. e.g.,
+ /// `[a-zA-Z\pL]`.
+ Bracketed(ClassBracketed),
+}
+
+impl Class {
+ /// Return the span of this character class.
+ pub fn span(&self) -> &Span {
+ match *self {
+ Class::Perl(ref x) => &x.span,
+ Class::Unicode(ref x) => &x.span,
+ Class::Bracketed(ref x) => &x.span,
+ }
+ }
+}
+
+/// A Perl character class.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct ClassPerl {
+ /// The span of this class.
+ pub span: Span,
+ /// The kind of Perl class.
+ pub kind: ClassPerlKind,
+ /// Whether the class is negated or not. e.g., `\d` is not negated but
+ /// `\D` is.
+ pub negated: bool,
+}
+
+/// The available Perl character classes.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum ClassPerlKind {
+ /// Decimal numbers.
+ Digit,
+ /// Whitespace.
+ Space,
+ /// Word characters.
+ Word,
+}
+
+/// An ASCII character class.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct ClassAscii {
+ /// The span of this class.
+ pub span: Span,
+ /// The kind of ASCII class.
+ pub kind: ClassAsciiKind,
+ /// Whether the class is negated or not. e.g., `[[:alpha:]]` is not negated
+ /// but `[[:^alpha:]]` is.
+ pub negated: bool,
+}
+
+/// The available ASCII character classes.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum ClassAsciiKind {
+ /// `[0-9A-Za-z]`
+ Alnum,
+ /// `[A-Za-z]`
+ Alpha,
+ /// `[\x00-\x7F]`
+ Ascii,
+ /// `[ \t]`
+ Blank,
+ /// `[\x00-\x1F\x7F]`
+ Cntrl,
+ /// `[0-9]`
+ Digit,
+ /// `[!-~]`
+ Graph,
+ /// `[a-z]`
+ Lower,
+ /// `[ -~]`
+ Print,
+ /// `[!-/:-@\[-`{-~]`
+ Punct,
+ /// `[\t\n\v\f\r ]`
+ Space,
+ /// `[A-Z]`
+ Upper,
+ /// `[0-9A-Za-z_]`
+ Word,
+ /// `[0-9A-Fa-f]`
+ Xdigit,
+}
+
+impl ClassAsciiKind {
+ /// Return the corresponding ClassAsciiKind variant for the given name.
+ ///
+ /// The name given should correspond to the lowercase version of the
+ /// variant name. e.g., `cntrl` is the name for `ClassAsciiKind::Cntrl`.
+ ///
+ /// If no variant with the corresponding name exists, then `None` is
+ /// returned.
+ pub fn from_name(name: &str) -> Option<ClassAsciiKind> {
+ use self::ClassAsciiKind::*;
+ match name {
+ "alnum" => Some(Alnum),
+ "alpha" => Some(Alpha),
+ "ascii" => Some(Ascii),
+ "blank" => Some(Blank),
+ "cntrl" => Some(Cntrl),
+ "digit" => Some(Digit),
+ "graph" => Some(Graph),
+ "lower" => Some(Lower),
+ "print" => Some(Print),
+ "punct" => Some(Punct),
+ "space" => Some(Space),
+ "upper" => Some(Upper),
+ "word" => Some(Word),
+ "xdigit" => Some(Xdigit),
+ _ => None,
+ }
+ }
+}
+
+/// A Unicode character class.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct ClassUnicode {
+ /// The span of this class.
+ pub span: Span,
+ /// Whether this class is negated or not.
+ ///
+ /// Note: be careful when using this attribute. This specifically refers
+ /// to whether the class is written as `\p` or `\P`, where the latter
+ /// is `negated = true`. However, it also possible to write something like
+ /// `\P{scx!=Katakana}` which is actually equivalent to
+ /// `\p{scx=Katakana}` and is therefore not actually negated even though
+ /// `negated = true` here. To test whether this class is truly negated
+ /// or not, use the `is_negated` method.
+ pub negated: bool,
+ /// The kind of Unicode class.
+ pub kind: ClassUnicodeKind,
+}
+
+impl ClassUnicode {
+ /// Returns true if this class has been negated.
+ ///
+ /// Note that this takes the Unicode op into account, if it's present.
+ /// e.g., `is_negated` for `\P{scx!=Katakana}` will return `false`.
+ pub fn is_negated(&self) -> bool {
+ match self.kind {
+ ClassUnicodeKind::NamedValue {
+ op: ClassUnicodeOpKind::NotEqual,
+ ..
+ } => !self.negated,
+ _ => self.negated,
+ }
+ }
+}
+
+/// The available forms of Unicode character classes.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum ClassUnicodeKind {
+ /// A one letter abbreviated class, e.g., `\pN`.
+ OneLetter(char),
+ /// A binary property, general category or script. The string may be
+ /// empty.
+ Named(String),
+ /// A property name and an associated value.
+ NamedValue {
+ /// The type of Unicode op used to associate `name` with `value`.
+ op: ClassUnicodeOpKind,
+ /// The property name (which may be empty).
+ name: String,
+ /// The property value (which may be empty).
+ value: String,
+ },
+}
+
+/// The type of op used in a Unicode character class.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum ClassUnicodeOpKind {
+ /// A property set to a specific value, e.g., `\p{scx=Katakana}`.
+ Equal,
+ /// A property set to a specific value using a colon, e.g.,
+ /// `\p{scx:Katakana}`.
+ Colon,
+ /// A property that isn't a particular value, e.g., `\p{scx!=Katakana}`.
+ NotEqual,
+}
+
+impl ClassUnicodeOpKind {
+ /// Whether the op is an equality op or not.
+ pub fn is_equal(&self) -> bool {
+ match *self {
+ ClassUnicodeOpKind::Equal | ClassUnicodeOpKind::Colon => true,
+ _ => false,
+ }
+ }
+}
+
+/// A bracketed character class, e.g., `[a-z0-9]`.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct ClassBracketed {
+ /// The span of this class.
+ pub span: Span,
+ /// Whether this class is negated or not. e.g., `[a]` is not negated but
+ /// `[^a]` is.
+ pub negated: bool,
+ /// The type of this set. A set is either a normal union of things, e.g.,
+ /// `[abc]` or a result of applying set operations, e.g., `[\pL--c]`.
+ pub kind: ClassSet,
+}
+
+/// A character class set.
+///
+/// This type corresponds to the internal structure of a bracketed character
+/// class. That is, every bracketed character is one of two types: a union of
+/// items (literals, ranges, other bracketed classes) or a tree of binary set
+/// operations.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum ClassSet {
+ /// An item, which can be a single literal, range, nested character class
+ /// or a union of items.
+ Item(ClassSetItem),
+ /// A single binary operation (i.e., &&, -- or ~~).
+ BinaryOp(ClassSetBinaryOp),
+}
+
+impl ClassSet {
+ /// Build a set from a union.
+ pub fn union(ast: ClassSetUnion) -> ClassSet {
+ ClassSet::Item(ClassSetItem::Union(ast))
+ }
+
+ /// Return the span of this character class set.
+ pub fn span(&self) -> &Span {
+ match *self {
+ ClassSet::Item(ref x) => x.span(),
+ ClassSet::BinaryOp(ref x) => &x.span,
+ }
+ }
+
+ /// Return true if and only if this class set is empty.
+ fn is_empty(&self) -> bool {
+ match *self {
+ ClassSet::Item(ClassSetItem::Empty(_)) => true,
+ _ => false,
+ }
+ }
+}
+
+/// A single component of a character class set.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum ClassSetItem {
+ /// An empty item.
+ ///
+ /// Note that a bracketed character class cannot contain a single empty
+ /// item. Empty items can appear when using one of the binary operators.
+ /// For example, `[&&]` is the intersection of two empty classes.
+ Empty(Span),
+ /// A single literal.
+ Literal(Literal),
+ /// A range between two literals.
+ Range(ClassSetRange),
+ /// An ASCII character class, e.g., `[:alnum:]` or `[:punct:]`.
+ Ascii(ClassAscii),
+ /// A Unicode character class, e.g., `\pL` or `\p{Greek}`.
+ Unicode(ClassUnicode),
+ /// A perl character class, e.g., `\d` or `\W`.
+ Perl(ClassPerl),
+ /// A bracketed character class set, which may contain zero or more
+ /// character ranges and/or zero or more nested classes. e.g.,
+ /// `[a-zA-Z\pL]`.
+ Bracketed(Box<ClassBracketed>),
+ /// A union of items.
+ Union(ClassSetUnion),
+}
+
+impl ClassSetItem {
+ /// Return the span of this character class set item.
+ pub fn span(&self) -> &Span {
+ match *self {
+ ClassSetItem::Empty(ref span) => span,
+ ClassSetItem::Literal(ref x) => &x.span,
+ ClassSetItem::Range(ref x) => &x.span,
+ ClassSetItem::Ascii(ref x) => &x.span,
+ ClassSetItem::Perl(ref x) => &x.span,
+ ClassSetItem::Unicode(ref x) => &x.span,
+ ClassSetItem::Bracketed(ref x) => &x.span,
+ ClassSetItem::Union(ref x) => &x.span,
+ }
+ }
+}
+
+/// A single character class range in a set.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct ClassSetRange {
+ /// The span of this range.
+ pub span: Span,
+ /// The start of this range.
+ pub start: Literal,
+ /// The end of this range.
+ pub end: Literal,
+}
+
+impl ClassSetRange {
+ /// Returns true if and only if this character class range is valid.
+ ///
+ /// The only case where a range is invalid is if its start is greater than
+ /// its end.
+ pub fn is_valid(&self) -> bool {
+ self.start.c <= self.end.c
+ }
+}
+
+/// A union of items inside a character class set.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct ClassSetUnion {
+ /// The span of the items in this operation. e.g., the `a-z0-9` in
+ /// `[^a-z0-9]`
+ pub span: Span,
+ /// The sequence of items that make up this union.
+ pub items: Vec<ClassSetItem>,
+}
+
+impl ClassSetUnion {
+ /// Push a new item in this union.
+ ///
+ /// The ending position of this union's span is updated to the ending
+ /// position of the span of the item given. If the union is empty, then
+ /// the starting position of this union is set to the starting position
+ /// of this item.
+ ///
+ /// In other words, if you only use this method to add items to a union
+ /// and you set the spans on each item correctly, then you should never
+ /// need to adjust the span of the union directly.
+ pub fn push(&mut self, item: ClassSetItem) {
+ if self.items.is_empty() {
+ self.span.start = item.span().start;
+ }
+ self.span.end = item.span().end;
+ self.items.push(item);
+ }
+
+ /// Return this union as a character class set item.
+ ///
+ /// If this union contains zero items, then an empty union is
+ /// returned. If this concatenation contains exactly 1 item, then the
+ /// corresponding item is returned. Otherwise, ClassSetItem::Union is
+ /// returned.
+ pub fn into_item(mut self) -> ClassSetItem {
+ match self.items.len() {
+ 0 => ClassSetItem::Empty(self.span),
+ 1 => self.items.pop().unwrap(),
+ _ => ClassSetItem::Union(self),
+ }
+ }
+}
+
+/// A Unicode character class set operation.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct ClassSetBinaryOp {
+ /// The span of this operation. e.g., the `a-z--[h-p]` in `[a-z--h-p]`.
+ pub span: Span,
+ /// The type of this set operation.
+ pub kind: ClassSetBinaryOpKind,
+ /// The left hand side of the operation.
+ pub lhs: Box<ClassSet>,
+ /// The right hand side of the operation.
+ pub rhs: Box<ClassSet>,
+}
+
+/// The type of a Unicode character class set operation.
+///
+/// Note that this doesn't explicitly represent union since there is no
+/// explicit union operator. Concatenation inside a character class corresponds
+/// to the union operation.
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub enum ClassSetBinaryOpKind {
+ /// The intersection of two sets, e.g., `\pN&&[a-z]`.
+ Intersection,
+ /// The difference of two sets, e.g., `\pN--[0-9]`.
+ Difference,
+ /// The symmetric difference of two sets. The symmetric difference is the
+ /// set of elements belonging to one but not both sets.
+ /// e.g., `[\pL~~[:ascii:]]`.
+ SymmetricDifference,
+}
+
+/// A single zero-width assertion.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Assertion {
+ /// The span of this assertion.
+ pub span: Span,
+ /// The assertion kind, e.g., `\b` or `^`.
+ pub kind: AssertionKind,
+}
+
+/// An assertion kind.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum AssertionKind {
+ /// `^`
+ StartLine,
+ /// `$`
+ EndLine,
+ /// `\A`
+ StartText,
+ /// `\z`
+ EndText,
+ /// `\b`
+ WordBoundary,
+ /// `\B`
+ NotWordBoundary,
+}
+
+/// A repetition operation applied to a regular expression.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Repetition {
+ /// The span of this operation.
+ pub span: Span,
+ /// The actual operation.
+ pub op: RepetitionOp,
+ /// Whether this operation was applied greedily or not.
+ pub greedy: bool,
+ /// The regular expression under repetition.
+ pub ast: Box<Ast>,
+}
+
+/// The repetition operator itself.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct RepetitionOp {
+ /// The span of this operator. This includes things like `+`, `*?` and
+ /// `{m,n}`.
+ pub span: Span,
+ /// The type of operation.
+ pub kind: RepetitionKind,
+}
+
+/// The kind of a repetition operator.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum RepetitionKind {
+ /// `?`
+ ZeroOrOne,
+ /// `*`
+ ZeroOrMore,
+ /// `+`
+ OneOrMore,
+ /// `{m,n}`
+ Range(RepetitionRange),
+}
+
+/// A range repetition operator.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum RepetitionRange {
+ /// `{m}`
+ Exactly(u32),
+ /// `{m,}`
+ AtLeast(u32),
+ /// `{m,n}`
+ Bounded(u32, u32),
+}
+
+impl RepetitionRange {
+ /// Returns true if and only if this repetition range is valid.
+ ///
+ /// The only case where a repetition range is invalid is if it is bounded
+ /// and its start is greater than its end.
+ pub fn is_valid(&self) -> bool {
+ match *self {
+ RepetitionRange::Bounded(s, e) if s > e => false,
+ _ => true,
+ }
+ }
+}
+
+/// A grouped regular expression.
+///
+/// This includes both capturing and non-capturing groups. This does **not**
+/// include flag-only groups like `(?is)`, but does contain any group that
+/// contains a sub-expression, e.g., `(a)`, `(?P<name>a)`, `(?:a)` and
+/// `(?is:a)`.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Group {
+ /// The span of this group.
+ pub span: Span,
+ /// The kind of this group.
+ pub kind: GroupKind,
+ /// The regular expression in this group.
+ pub ast: Box<Ast>,
+}
+
+impl Group {
+ /// If this group is non-capturing, then this returns the (possibly empty)
+ /// set of flags. Otherwise, `None` is returned.
+ pub fn flags(&self) -> Option<&Flags> {
+ match self.kind {
+ GroupKind::NonCapturing(ref flags) => Some(flags),
+ _ => None,
+ }
+ }
+
+ /// Returns true if and only if this group is capturing.
+ pub fn is_capturing(&self) -> bool {
+ match self.kind {
+ GroupKind::CaptureIndex(_) | GroupKind::CaptureName(_) => true,
+ GroupKind::NonCapturing(_) => false,
+ }
+ }
+
+ /// Returns the capture index of this group, if this is a capturing group.
+ ///
+ /// This returns a capture index precisely when `is_capturing` is `true`.
+ pub fn capture_index(&self) -> Option<u32> {
+ match self.kind {
+ GroupKind::CaptureIndex(i) => Some(i),
+ GroupKind::CaptureName(ref x) => Some(x.index),
+ GroupKind::NonCapturing(_) => None,
+ }
+ }
+}
+
+/// The kind of a group.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum GroupKind {
+ /// `(a)`
+ CaptureIndex(u32),
+ /// `(?P<name>a)`
+ CaptureName(CaptureName),
+ /// `(?:a)` and `(?i:a)`
+ NonCapturing(Flags),
+}
+
+/// A capture name.
+///
+/// This corresponds to the name itself between the angle brackets in, e.g.,
+/// `(?P<foo>expr)`.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct CaptureName {
+ /// The span of this capture name.
+ pub span: Span,
+ /// The capture name.
+ pub name: String,
+ /// The capture index.
+ pub index: u32,
+}
+
+/// A group of flags that is not applied to a particular regular expression.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct SetFlags {
+ /// The span of these flags, including the grouping parentheses.
+ pub span: Span,
+ /// The actual sequence of flags.
+ pub flags: Flags,
+}
+
+/// A group of flags.
+///
+/// This corresponds only to the sequence of flags themselves, e.g., `is-u`.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Flags {
+ /// The span of this group of flags.
+ pub span: Span,
+ /// A sequence of flag items. Each item is either a flag or a negation
+ /// operator.
+ pub items: Vec<FlagsItem>,
+}
+
+impl Flags {
+ /// Add the given item to this sequence of flags.
+ ///
+ /// If the item was added successfully, then `None` is returned. If the
+ /// given item is a duplicate, then `Some(i)` is returned, where
+ /// `items[i].kind == item.kind`.
+ pub fn add_item(&mut self, item: FlagsItem) -> Option<usize> {
+ for (i, x) in self.items.iter().enumerate() {
+ if x.kind == item.kind {
+ return Some(i);
+ }
+ }
+ self.items.push(item);
+ None
+ }
+
+ /// Returns the state of the given flag in this set.
+ ///
+ /// If the given flag is in the set but is negated, then `Some(false)` is
+ /// returned.
+ ///
+ /// If the given flag is in the set and is not negated, then `Some(true)`
+ /// is returned.
+ ///
+ /// Otherwise, `None` is returned.
+ pub fn flag_state(&self, flag: Flag) -> Option<bool> {
+ let mut negated = false;
+ for x in &self.items {
+ match x.kind {
+ FlagsItemKind::Negation => {
+ negated = true;
+ }
+ FlagsItemKind::Flag(ref xflag) if xflag == &flag => {
+ return Some(!negated);
+ }
+ _ => {}
+ }
+ }
+ None
+ }
+}
+
+/// A single item in a group of flags.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct FlagsItem {
+ /// The span of this item.
+ pub span: Span,
+ /// The kind of this item.
+ pub kind: FlagsItemKind,
+}
+
+/// The kind of an item in a group of flags.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum FlagsItemKind {
+ /// A negation operator applied to all subsequent flags in the enclosing
+ /// group.
+ Negation,
+ /// A single flag in a group.
+ Flag(Flag),
+}
+
+impl FlagsItemKind {
+ /// Returns true if and only if this item is a negation operator.
+ pub fn is_negation(&self) -> bool {
+ match *self {
+ FlagsItemKind::Negation => true,
+ _ => false,
+ }
+ }
+}
+
+/// A single flag.
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub enum Flag {
+ /// `i`
+ CaseInsensitive,
+ /// `m`
+ MultiLine,
+ /// `s`
+ DotMatchesNewLine,
+ /// `U`
+ SwapGreed,
+ /// `u`
+ Unicode,
+ /// `x`
+ IgnoreWhitespace,
+}
+
+/// A custom `Drop` impl is used for `Ast` such that it uses constant stack
+/// space but heap space proportional to the depth of the `Ast`.
+impl Drop for Ast {
+ fn drop(&mut self) {
+ use std::mem;
+
+ match *self {
+ Ast::Empty(_)
+ | Ast::Flags(_)
+ | Ast::Literal(_)
+ | Ast::Dot(_)
+ | Ast::Assertion(_)
+ // Classes are recursive, so they get their own Drop impl.
+ | Ast::Class(_) => return,
+ Ast::Repetition(ref x) if !x.ast.has_subexprs() => return,
+ Ast::Group(ref x) if !x.ast.has_subexprs() => return,
+ Ast::Alternation(ref x) if x.asts.is_empty() => return,
+ Ast::Concat(ref x) if x.asts.is_empty() => return,
+ _ => {}
+ }
+
+ let empty_span = || Span::splat(Position::new(0, 0, 0));
+ let empty_ast = || Ast::Empty(empty_span());
+ let mut stack = vec![mem::replace(self, empty_ast())];
+ while let Some(mut ast) = stack.pop() {
+ match ast {
+ Ast::Empty(_)
+ | Ast::Flags(_)
+ | Ast::Literal(_)
+ | Ast::Dot(_)
+ | Ast::Assertion(_)
+ // Classes are recursive, so they get their own Drop impl.
+ | Ast::Class(_) => {}
+ Ast::Repetition(ref mut x) => {
+ stack.push(mem::replace(&mut x.ast, empty_ast()));
+ }
+ Ast::Group(ref mut x) => {
+ stack.push(mem::replace(&mut x.ast, empty_ast()));
+ }
+ Ast::Alternation(ref mut x) => {
+ stack.extend(x.asts.drain(..));
+ }
+ Ast::Concat(ref mut x) => {
+ stack.extend(x.asts.drain(..));
+ }
+ }
+ }
+ }
+}
+
+/// A custom `Drop` impl is used for `ClassSet` such that it uses constant
+/// stack space but heap space proportional to the depth of the `ClassSet`.
+impl Drop for ClassSet {
+ fn drop(&mut self) {
+ use std::mem;
+
+ match *self {
+ ClassSet::Item(ref item) => match *item {
+ ClassSetItem::Empty(_)
+ | ClassSetItem::Literal(_)
+ | ClassSetItem::Range(_)
+ | ClassSetItem::Ascii(_)
+ | ClassSetItem::Unicode(_)
+ | ClassSetItem::Perl(_) => return,
+ ClassSetItem::Bracketed(ref x) => {
+ if x.kind.is_empty() {
+ return;
+ }
+ }
+ ClassSetItem::Union(ref x) => {
+ if x.items.is_empty() {
+ return;
+ }
+ }
+ },
+ ClassSet::BinaryOp(ref op) => {
+ if op.lhs.is_empty() && op.rhs.is_empty() {
+ return;
+ }
+ }
+ }
+
+ let empty_span = || Span::splat(Position::new(0, 0, 0));
+ let empty_set = || ClassSet::Item(ClassSetItem::Empty(empty_span()));
+ let mut stack = vec![mem::replace(self, empty_set())];
+ while let Some(mut set) = stack.pop() {
+ match set {
+ ClassSet::Item(ref mut item) => match *item {
+ ClassSetItem::Empty(_)
+ | ClassSetItem::Literal(_)
+ | ClassSetItem::Range(_)
+ | ClassSetItem::Ascii(_)
+ | ClassSetItem::Unicode(_)
+ | ClassSetItem::Perl(_) => {}
+ ClassSetItem::Bracketed(ref mut x) => {
+ stack.push(mem::replace(&mut x.kind, empty_set()));
+ }
+ ClassSetItem::Union(ref mut x) => {
+ stack.extend(x.items.drain(..).map(ClassSet::Item));
+ }
+ },
+ ClassSet::BinaryOp(ref mut op) => {
+ stack.push(mem::replace(&mut op.lhs, empty_set()));
+ stack.push(mem::replace(&mut op.rhs, empty_set()));
+ }
+ }
+ }
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+
+ // We use a thread with an explicit stack size to test that our destructor
+ // for Ast can handle arbitrarily sized expressions in constant stack
+ // space. In case we run on a platform without threads (WASM?), we limit
+ // this test to Windows/Unix.
+ #[test]
+ #[cfg(any(unix, windows))]
+ fn no_stack_overflow_on_drop() {
+ use std::thread;
+
+ let run = || {
+ let span = || Span::splat(Position::new(0, 0, 0));
+ let mut ast = Ast::Empty(span());
+ for i in 0..200 {
+ ast = Ast::Group(Group {
+ span: span(),
+ kind: GroupKind::CaptureIndex(i),
+ ast: Box::new(ast),
+ });
+ }
+ assert!(!ast.is_empty());
+ };
+
+ // We run our test on a thread with a small stack size so we can
+ // force the issue more easily.
+ thread::Builder::new()
+ .stack_size(1 << 10)
+ .spawn(run)
+ .unwrap()
+ .join()
+ .unwrap();
+ }
+}
diff --git a/src/ast/parse.rs b/src/ast/parse.rs
new file mode 100644
index 0000000..f5b4548
--- /dev/null
+++ b/src/ast/parse.rs
@@ -0,0 +1,5901 @@
+/*!
+This module provides a regular expression parser.
+*/
+
+use std::borrow::Borrow;
+use std::cell::{Cell, RefCell};
+use std::mem;
+use std::result;
+
+use ast::{self, Ast, Position, Span};
+use either::Either;
+
+use is_meta_character;
+
+type Result<T> = result::Result<T, ast::Error>;
+
+/// A primitive is an expression with no sub-expressions. This includes
+/// literals, assertions and non-set character classes. This representation
+/// is used as intermediate state in the parser.
+///
+/// This does not include ASCII character classes, since they can only appear
+/// within a set character class.
+#[derive(Clone, Debug, Eq, PartialEq)]
+enum Primitive {
+ Literal(ast::Literal),
+ Assertion(ast::Assertion),
+ Dot(Span),
+ Perl(ast::ClassPerl),
+ Unicode(ast::ClassUnicode),
+}
+
+impl Primitive {
+ /// Return the span of this primitive.
+ fn span(&self) -> &Span {
+ match *self {
+ Primitive::Literal(ref x) => &x.span,
+ Primitive::Assertion(ref x) => &x.span,
+ Primitive::Dot(ref span) => span,
+ Primitive::Perl(ref x) => &x.span,
+ Primitive::Unicode(ref x) => &x.span,
+ }
+ }
+
+ /// Convert this primitive into a proper AST.
+ fn into_ast(self) -> Ast {
+ match self {
+ Primitive::Literal(lit) => Ast::Literal(lit),
+ Primitive::Assertion(assert) => Ast::Assertion(assert),
+ Primitive::Dot(span) => Ast::Dot(span),
+ Primitive::Perl(cls) => Ast::Class(ast::Class::Perl(cls)),
+ Primitive::Unicode(cls) => Ast::Class(ast::Class::Unicode(cls)),
+ }
+ }
+
+ /// Convert this primitive into an item in a character class.
+ ///
+ /// If this primitive is not a legal item (i.e., an assertion or a dot),
+ /// then return an error.
+ fn into_class_set_item<P: Borrow<Parser>>(
+ self,
+ p: &ParserI<P>,
+ ) -> Result<ast::ClassSetItem> {
+ use self::Primitive::*;
+ use ast::ClassSetItem;
+
+ match self {
+ Literal(lit) => Ok(ClassSetItem::Literal(lit)),
+ Perl(cls) => Ok(ClassSetItem::Perl(cls)),
+ Unicode(cls) => Ok(ClassSetItem::Unicode(cls)),
+ x => Err(p.error(*x.span(), ast::ErrorKind::ClassEscapeInvalid)),
+ }
+ }
+
+ /// Convert this primitive into a literal in a character class. In
+ /// particular, literals are the only valid items that can appear in
+ /// ranges.
+ ///
+ /// If this primitive is not a legal item (i.e., a class, assertion or a
+ /// dot), then return an error.
+ fn into_class_literal<P: Borrow<Parser>>(
+ self,
+ p: &ParserI<P>,
+ ) -> Result<ast::Literal> {
+ use self::Primitive::*;
+
+ match self {
+ Literal(lit) => Ok(lit),
+ x => Err(p.error(*x.span(), ast::ErrorKind::ClassRangeLiteral)),
+ }
+ }
+}
+
+/// Returns true if the given character is a hexadecimal digit.
+fn is_hex(c: char) -> bool {
+ ('0' <= c && c <= '9') || ('a' <= c && c <= 'f') || ('A' <= c && c <= 'F')
+}
+
+/// Returns true if the given character is a valid in a capture group name.
+///
+/// If `first` is true, then `c` is treated as the first character in the
+/// group name (which is not allowed to be a digit).
+fn is_capture_char(c: char, first: bool) -> bool {
+ c == '_'
+ || (!first && c >= '0' && c <= '9')
+ || (c >= 'a' && c <= 'z')
+ || (c >= 'A' && c <= 'Z')
+}
+
+/// A builder for a regular expression parser.
+///
+/// This builder permits modifying configuration options for the parser.
+#[derive(Clone, Debug)]
+pub struct ParserBuilder {
+ ignore_whitespace: bool,
+ nest_limit: u32,
+ octal: bool,
+}
+
+impl Default for ParserBuilder {
+ fn default() -> ParserBuilder {
+ ParserBuilder::new()
+ }
+}
+
+impl ParserBuilder {
+ /// Create a new parser builder with a default configuration.
+ pub fn new() -> ParserBuilder {
+ ParserBuilder {
+ ignore_whitespace: false,
+ nest_limit: 250,
+ octal: false,
+ }
+ }
+
+ /// Build a parser from this configuration with the given pattern.
+ pub fn build(&self) -> Parser {
+ Parser {
+ pos: Cell::new(Position { offset: 0, line: 1, column: 1 }),
+ capture_index: Cell::new(0),
+ nest_limit: self.nest_limit,
+ octal: self.octal,
+ initial_ignore_whitespace: self.ignore_whitespace,
+ ignore_whitespace: Cell::new(self.ignore_whitespace),
+ comments: RefCell::new(vec![]),
+ stack_group: RefCell::new(vec![]),
+ stack_class: RefCell::new(vec![]),
+ capture_names: RefCell::new(vec![]),
+ scratch: RefCell::new(String::new()),
+ }
+ }
+
+ /// Set the nesting limit for this parser.
+ ///
+ /// The nesting limit controls how deep the abstract syntax tree is allowed
+ /// to be. If the AST exceeds the given limit (e.g., with too many nested
+ /// groups), then an error is returned by the parser.
+ ///
+ /// The purpose of this limit is to act as a heuristic to prevent stack
+ /// overflow for consumers that do structural induction on an `Ast` using
+ /// explicit recursion. While this crate never does this (instead using
+ /// constant stack space and moving the call stack to the heap), other
+ /// crates may.
+ ///
+ /// This limit is not checked until the entire Ast is parsed. Therefore,
+ /// if callers want to put a limit on the amount of heap space used, then
+ /// they should impose a limit on the length, in bytes, of the concrete
+ /// pattern string. In particular, this is viable since this parser
+ /// implementation will limit itself to heap space proportional to the
+ /// lenth of the pattern string.
+ ///
+ /// Note that a nest limit of `0` will return a nest limit error for most
+ /// patterns but not all. For example, a nest limit of `0` permits `a` but
+ /// not `ab`, since `ab` requires a concatenation, which results in a nest
+ /// depth of `1`. In general, a nest limit is not something that manifests
+ /// in an obvious way in the concrete syntax, therefore, it should not be
+ /// used in a granular way.
+ pub fn nest_limit(&mut self, limit: u32) -> &mut ParserBuilder {
+ self.nest_limit = limit;
+ self
+ }
+
+ /// Whether to support octal syntax or not.
+ ///
+ /// Octal syntax is a little-known way of uttering Unicode codepoints in
+ /// a regular expression. For example, `a`, `\x61`, `\u0061` and
+ /// `\141` are all equivalent regular expressions, where the last example
+ /// shows octal syntax.
+ ///
+ /// While supporting octal syntax isn't in and of itself a problem, it does
+ /// make good error messages harder. That is, in PCRE based regex engines,
+ /// syntax like `\0` invokes a backreference, which is explicitly
+ /// unsupported in Rust's regex engine. However, many users expect it to
+ /// be supported. Therefore, when octal support is disabled, the error
+ /// message will explicitly mention that backreferences aren't supported.
+ ///
+ /// Octal syntax is disabled by default.
+ pub fn octal(&mut self, yes: bool) -> &mut ParserBuilder {
+ self.octal = yes;
+ self
+ }
+
+ /// Enable verbose mode in the regular expression.
+ ///
+ /// When enabled, verbose mode permits insigificant whitespace in many
+ /// places in the regular expression, as well as comments. Comments are
+ /// started using `#` and continue until the end of the line.
+ ///
+ /// By default, this is disabled. It may be selectively enabled in the
+ /// regular expression by using the `x` flag regardless of this setting.
+ pub fn ignore_whitespace(&mut self, yes: bool) -> &mut ParserBuilder {
+ self.ignore_whitespace = yes;
+ self
+ }
+}
+
+/// A regular expression parser.
+///
+/// This parses a string representation of a regular expression into an
+/// abstract syntax tree. The size of the tree is proportional to the length
+/// of the regular expression pattern.
+///
+/// A `Parser` can be configured in more detail via a
+/// [`ParserBuilder`](struct.ParserBuilder.html).
+#[derive(Clone, Debug)]
+pub struct Parser {
+ /// The current position of the parser.
+ pos: Cell<Position>,
+ /// The current capture index.
+ capture_index: Cell<u32>,
+ /// The maximum number of open parens/brackets allowed. If the parser
+ /// exceeds this number, then an error is returned.
+ nest_limit: u32,
+ /// Whether to support octal syntax or not. When `false`, the parser will
+ /// return an error helpfully pointing out that backreferences are not
+ /// supported.
+ octal: bool,
+ /// The initial setting for `ignore_whitespace` as provided by
+ /// Th`ParserBuilder`. is is used when reseting the parser's state.
+ initial_ignore_whitespace: bool,
+ /// Whether whitespace should be ignored. When enabled, comments are
+ /// also permitted.
+ ignore_whitespace: Cell<bool>,
+ /// A list of comments, in order of appearance.
+ comments: RefCell<Vec<ast::Comment>>,
+ /// A stack of grouped sub-expressions, including alternations.
+ stack_group: RefCell<Vec<GroupState>>,
+ /// A stack of nested character classes. This is only non-empty when
+ /// parsing a class.
+ stack_class: RefCell<Vec<ClassState>>,
+ /// A sorted sequence of capture names. This is used to detect duplicate
+ /// capture names and report an error if one is detected.
+ capture_names: RefCell<Vec<ast::CaptureName>>,
+ /// A scratch buffer used in various places. Mostly this is used to
+ /// accumulate relevant characters from parts of a pattern.
+ scratch: RefCell<String>,
+}
+
+/// ParserI is the internal parser implementation.
+///
+/// We use this separate type so that we can carry the provided pattern string
+/// along with us. In particular, a `Parser` internal state is not tied to any
+/// one pattern, but `ParserI` is.
+///
+/// This type also lets us use `ParserI<&Parser>` in production code while
+/// retaining the convenience of `ParserI<Parser>` for tests, which sometimes
+/// work against the internal interface of the parser.
+#[derive(Clone, Debug)]
+struct ParserI<'s, P> {
+ /// The parser state/configuration.
+ parser: P,
+ /// The full regular expression provided by the user.
+ pattern: &'s str,
+}
+
+/// GroupState represents a single stack frame while parsing nested groups
+/// and alternations. Each frame records the state up to an opening parenthesis
+/// or a alternating bracket `|`.
+#[derive(Clone, Debug)]
+enum GroupState {
+ /// This state is pushed whenever an opening group is found.
+ Group {
+ /// The concatenation immediately preceding the opening group.
+ concat: ast::Concat,
+ /// The group that has been opened. Its sub-AST is always empty.
+ group: ast::Group,
+ /// Whether this group has the `x` flag enabled or not.
+ ignore_whitespace: bool,
+ },
+ /// This state is pushed whenever a new alternation branch is found. If
+ /// an alternation branch is found and this state is at the top of the
+ /// stack, then this state should be modified to include the new
+ /// alternation.
+ Alternation(ast::Alternation),
+}
+
+/// ClassState represents a single stack frame while parsing character classes.
+/// Each frame records the state up to an intersection, difference, symmetric
+/// difference or nested class.
+///
+/// Note that a parser's character class stack is only non-empty when parsing
+/// a character class. In all other cases, it is empty.
+#[derive(Clone, Debug)]
+enum ClassState {
+ /// This state is pushed whenever an opening bracket is found.
+ Open {
+ /// The union of class items immediately preceding this class.
+ union: ast::ClassSetUnion,
+ /// The class that has been opened. Typically this just corresponds
+ /// to the `[`, but it can also include `[^` since `^` indicates
+ /// negation of the class.
+ set: ast::ClassBracketed,
+ },
+ /// This state is pushed when a operator is seen. When popped, the stored
+ /// set becomes the left hand side of the operator.
+ Op {
+ /// The type of the operation, i.e., &&, -- or ~~.
+ kind: ast::ClassSetBinaryOpKind,
+ /// The left-hand side of the operator.
+ lhs: ast::ClassSet,
+ },
+}
+
+impl Parser {
+ /// Create a new parser with a default configuration.
+ ///
+ /// The parser can be run with either the `parse` or `parse_with_comments`
+ /// methods. The parse methods return an abstract syntax tree.
+ ///
+ /// To set configuration options on the parser, use
+ /// [`ParserBuilder`](struct.ParserBuilder.html).
+ pub fn new() -> Parser {
+ ParserBuilder::new().build()
+ }
+
+ /// Parse the regular expression into an abstract syntax tree.
+ pub fn parse(&mut self, pattern: &str) -> Result<Ast> {
+ ParserI::new(self, pattern).parse()
+ }
+
+ /// Parse the regular expression and return an abstract syntax tree with
+ /// all of the comments found in the pattern.
+ pub fn parse_with_comments(
+ &mut self,
+ pattern: &str,
+ ) -> Result<ast::WithComments> {
+ ParserI::new(self, pattern).parse_with_comments()
+ }
+
+ /// Reset the internal state of a parser.
+ ///
+ /// This is called at the beginning of every parse. This prevents the
+ /// parser from running with inconsistent state (say, if a previous
+ /// invocation returned an error and the parser is reused).
+ fn reset(&self) {
+ // These settings should be in line with the construction
+ // in `ParserBuilder::build`.
+ self.pos.set(Position { offset: 0, line: 1, column: 1 });
+ self.ignore_whitespace.set(self.initial_ignore_whitespace);
+ self.comments.borrow_mut().clear();
+ self.stack_group.borrow_mut().clear();
+ self.stack_class.borrow_mut().clear();
+ }
+}
+
+impl<'s, P: Borrow<Parser>> ParserI<'s, P> {
+ /// Build an internal parser from a parser configuration and a pattern.
+ fn new(parser: P, pattern: &'s str) -> ParserI<'s, P> {
+ ParserI { parser: parser, pattern: pattern }
+ }
+
+ /// Return a reference to the parser state.
+ fn parser(&self) -> &Parser {
+ self.parser.borrow()
+ }
+
+ /// Return a reference to the pattern being parsed.
+ fn pattern(&self) -> &str {
+ self.pattern.borrow()
+ }
+
+ /// Create a new error with the given span and error type.
+ fn error(&self, span: Span, kind: ast::ErrorKind) -> ast::Error {
+ ast::Error {
+ kind: kind,
+ pattern: self.pattern().to_string(),
+ span: span,
+ }
+ }
+
+ /// Return the current offset of the parser.
+ ///
+ /// The offset starts at `0` from the beginning of the regular expression
+ /// pattern string.
+ fn offset(&self) -> usize {
+ self.parser().pos.get().offset
+ }
+
+ /// Return the current line number of the parser.
+ ///
+ /// The line number starts at `1`.
+ fn line(&self) -> usize {
+ self.parser().pos.get().line
+ }
+
+ /// Return the current column of the parser.
+ ///
+ /// The column number starts at `1` and is reset whenever a `\n` is seen.
+ fn column(&self) -> usize {
+ self.parser().pos.get().column
+ }
+
+ /// Return the next capturing index. Each subsequent call increments the
+ /// internal index.
+ ///
+ /// The span given should correspond to the location of the opening
+ /// parenthesis.
+ ///
+ /// If the capture limit is exceeded, then an error is returned.
+ fn next_capture_index(&self, span: Span) -> Result<u32> {
+ let current = self.parser().capture_index.get();
+ let i = current.checked_add(1).ok_or_else(|| {
+ self.error(span, ast::ErrorKind::CaptureLimitExceeded)
+ })?;
+ self.parser().capture_index.set(i);
+ Ok(i)
+ }
+
+ /// Adds the given capture name to this parser. If this capture name has
+ /// already been used, then an error is returned.
+ fn add_capture_name(&self, cap: &ast::CaptureName) -> Result<()> {
+ let mut names = self.parser().capture_names.borrow_mut();
+ match names
+ .binary_search_by_key(&cap.name.as_str(), |c| c.name.as_str())
+ {
+ Err(i) => {
+ names.insert(i, cap.clone());
+ Ok(())
+ }
+ Ok(i) => Err(self.error(
+ cap.span,
+ ast::ErrorKind::GroupNameDuplicate { original: names[i].span },
+ )),
+ }
+ }
+
+ /// Return whether the parser should ignore whitespace or not.
+ fn ignore_whitespace(&self) -> bool {
+ self.parser().ignore_whitespace.get()
+ }
+
+ /// Return the character at the current position of the parser.
+ ///
+ /// This panics if the current position does not point to a valid char.
+ fn char(&self) -> char {
+ self.char_at(self.offset())
+ }
+
+ /// Return the character at the given position.
+ ///
+ /// This panics if the given position does not point to a valid char.
+ fn char_at(&self, i: usize) -> char {
+ self.pattern()[i..]
+ .chars()
+ .next()
+ .unwrap_or_else(|| panic!("expected char at offset {}", i))
+ }
+
+ /// Bump the parser to the next Unicode scalar value.
+ ///
+ /// If the end of the input has been reached, then `false` is returned.
+ fn bump(&self) -> bool {
+ if self.is_eof() {
+ return false;
+ }
+ let Position { mut offset, mut line, mut column } = self.pos();
+ if self.char() == '\n' {
+ line = line.checked_add(1).unwrap();
+ column = 1;
+ } else {
+ column = column.checked_add(1).unwrap();
+ }
+ offset += self.char().len_utf8();
+ self.parser().pos.set(Position {
+ offset: offset,
+ line: line,
+ column: column,
+ });
+ self.pattern()[self.offset()..].chars().next().is_some()
+ }
+
+ /// If the substring starting at the current position of the parser has
+ /// the given prefix, then bump the parser to the character immediately
+ /// following the prefix and return true. Otherwise, don't bump the parser
+ /// and return false.
+ fn bump_if(&self, prefix: &str) -> bool {
+ if self.pattern()[self.offset()..].starts_with(prefix) {
+ for _ in 0..prefix.chars().count() {
+ self.bump();
+ }
+ true
+ } else {
+ false
+ }
+ }
+
+ /// Returns true if and only if the parser is positioned at a look-around
+ /// prefix. The conditions under which this returns true must always
+ /// correspond to a regular expression that would otherwise be consider
+ /// invalid.
+ ///
+ /// This should only be called immediately after parsing the opening of
+ /// a group or a set of flags.
+ fn is_lookaround_prefix(&self) -> bool {
+ self.bump_if("?=")
+ || self.bump_if("?!")
+ || self.bump_if("?<=")
+ || self.bump_if("?<!")
+ }
+
+ /// Bump the parser, and if the `x` flag is enabled, bump through any
+ /// subsequent spaces. Return true if and only if the parser is not at
+ /// EOF.
+ fn bump_and_bump_space(&self) -> bool {
+ if !self.bump() {
+ return false;
+ }
+ self.bump_space();
+ !self.is_eof()
+ }
+
+ /// If the `x` flag is enabled (i.e., whitespace insensitivity with
+ /// comments), then this will advance the parser through all whitespace
+ /// and comments to the next non-whitespace non-comment byte.
+ ///
+ /// If the `x` flag is disabled, then this is a no-op.
+ ///
+ /// This should be used selectively throughout the parser where
+ /// arbitrary whitespace is permitted when the `x` flag is enabled. For
+ /// example, `{ 5 , 6}` is equivalent to `{5,6}`.
+ fn bump_space(&self) {
+ if !self.ignore_whitespace() {
+ return;
+ }
+ while !self.is_eof() {
+ if self.char().is_whitespace() {
+ self.bump();
+ } else if self.char() == '#' {
+ let start = self.pos();
+ let mut comment_text = String::new();
+ self.bump();
+ while !self.is_eof() {
+ let c = self.char();
+ self.bump();
+ if c == '\n' {
+ break;
+ }
+ comment_text.push(c);
+ }
+ let comment = ast::Comment {
+ span: Span::new(start, self.pos()),
+ comment: comment_text,
+ };
+ self.parser().comments.borrow_mut().push(comment);
+ } else {
+ break;
+ }
+ }
+ }
+
+ /// Peek at the next character in the input without advancing the parser.
+ ///
+ /// If the input has been exhausted, then this returns `None`.
+ fn peek(&self) -> Option<char> {
+ if self.is_eof() {
+ return None;
+ }
+ self.pattern()[self.offset() + self.char().len_utf8()..].chars().next()
+ }
+
+ /// Like peek, but will ignore spaces when the parser is in whitespace
+ /// insensitive mode.
+ fn peek_space(&self) -> Option<char> {
+ if !self.ignore_whitespace() {
+ return self.peek();
+ }
+ if self.is_eof() {
+ return None;
+ }
+ let mut start = self.offset() + self.char().len_utf8();
+ let mut in_comment = false;
+ for (i, c) in self.pattern()[start..].char_indices() {
+ if c.is_whitespace() {
+ continue;
+ } else if !in_comment && c == '#' {
+ in_comment = true;
+ } else if in_comment && c == '\n' {
+ in_comment = false;
+ } else {
+ start += i;
+ break;
+ }
+ }
+ self.pattern()[start..].chars().next()
+ }
+
+ /// Returns true if the next call to `bump` would return false.
+ fn is_eof(&self) -> bool {
+ self.offset() == self.pattern().len()
+ }
+
+ /// Return the current position of the parser, which includes the offset,
+ /// line and column.
+ fn pos(&self) -> Position {
+ self.parser().pos.get()
+ }
+
+ /// Create a span at the current position of the parser. Both the start
+ /// and end of the span are set.
+ fn span(&self) -> Span {
+ Span::splat(self.pos())
+ }
+
+ /// Create a span that covers the current character.
+ fn span_char(&self) -> Span {
+ let mut next = Position {
+ offset: self.offset().checked_add(self.char().len_utf8()).unwrap(),
+ line: self.line(),
+ column: self.column().checked_add(1).unwrap(),
+ };
+ if self.char() == '\n' {
+ next.line += 1;
+ next.column = 1;
+ }
+ Span::new(self.pos(), next)
+ }
+
+ /// Parse and push a single alternation on to the parser's internal stack.
+ /// If the top of the stack already has an alternation, then add to that
+ /// instead of pushing a new one.
+ ///
+ /// The concatenation given corresponds to a single alternation branch.
+ /// The concatenation returned starts the next branch and is empty.
+ ///
+ /// This assumes the parser is currently positioned at `|` and will advance
+ /// the parser to the character following `|`.
+ #[inline(never)]
+ fn push_alternate(&self, mut concat: ast::Concat) -> Result<ast::Concat> {
+ assert_eq!(self.char(), '|');
+ concat.span.end = self.pos();
+ self.push_or_add_alternation(concat);
+ self.bump();
+ Ok(ast::Concat { span: self.span(), asts: vec![] })
+ }
+
+ /// Pushes or adds the given branch of an alternation to the parser's
+ /// internal stack of state.
+ fn push_or_add_alternation(&self, concat: ast::Concat) {
+ use self::GroupState::*;
+
+ let mut stack = self.parser().stack_group.borrow_mut();
+ if let Some(&mut Alternation(ref mut alts)) = stack.last_mut() {
+ alts.asts.push(concat.into_ast());
+ return;
+ }
+ stack.push(Alternation(ast::Alternation {
+ span: Span::new(concat.span.start, self.pos()),
+ asts: vec![concat.into_ast()],
+ }));
+ }
+
+ /// Parse and push a group AST (and its parent concatenation) on to the
+ /// parser's internal stack. Return a fresh concatenation corresponding
+ /// to the group's sub-AST.
+ ///
+ /// If a set of flags was found (with no group), then the concatenation
+ /// is returned with that set of flags added.
+ ///
+ /// This assumes that the parser is currently positioned on the opening
+ /// parenthesis. It advances the parser to the character at the start
+ /// of the sub-expression (or adjoining expression).
+ ///
+ /// If there was a problem parsing the start of the group, then an error
+ /// is returned.
+ #[inline(never)]
+ fn push_group(&self, mut concat: ast::Concat) -> Result<ast::Concat> {
+ assert_eq!(self.char(), '(');
+ match self.parse_group()? {
+ Either::Left(set) => {
+ let ignore = set.flags.flag_state(ast::Flag::IgnoreWhitespace);
+ if let Some(v) = ignore {
+ self.parser().ignore_whitespace.set(v);
+ }
+
+ concat.asts.push(Ast::Flags(set));
+ Ok(concat)
+ }
+ Either::Right(group) => {
+ let old_ignore_whitespace = self.ignore_whitespace();
+ let new_ignore_whitespace = group
+ .flags()
+ .and_then(|f| f.flag_state(ast::Flag::IgnoreWhitespace))
+ .unwrap_or(old_ignore_whitespace);
+ self.parser().stack_group.borrow_mut().push(
+ GroupState::Group {
+ concat: concat,
+ group: group,
+ ignore_whitespace: old_ignore_whitespace,
+ },
+ );
+ self.parser().ignore_whitespace.set(new_ignore_whitespace);
+ Ok(ast::Concat { span: self.span(), asts: vec![] })
+ }
+ }
+ }
+
+ /// Pop a group AST from the parser's internal stack and set the group's
+ /// AST to the given concatenation. Return the concatenation containing
+ /// the group.
+ ///
+ /// This assumes that the parser is currently positioned on the closing
+ /// parenthesis and advances the parser to the character following the `)`.
+ ///
+ /// If no such group could be popped, then an unopened group error is
+ /// returned.
+ #[inline(never)]
+ fn pop_group(&self, mut group_concat: ast::Concat) -> Result<ast::Concat> {
+ use self::GroupState::*;
+
+ assert_eq!(self.char(), ')');
+ let mut stack = self.parser().stack_group.borrow_mut();
+ let (mut prior_concat, mut group, ignore_whitespace, alt) = match stack
+ .pop()
+ {
+ Some(Group { concat, group, ignore_whitespace }) => {
+ (concat, group, ignore_whitespace, None)
+ }
+ Some(Alternation(alt)) => match stack.pop() {
+ Some(Group { concat, group, ignore_whitespace }) => {
+ (concat, group, ignore_whitespace, Some(alt))
+ }
+ None | Some(Alternation(_)) => {
+ return Err(self.error(
+ self.span_char(),
+ ast::ErrorKind::GroupUnopened,
+ ));
+ }
+ },
+ None => {
+ return Err(self
+ .error(self.span_char(), ast::ErrorKind::GroupUnopened));
+ }
+ };
+ self.parser().ignore_whitespace.set(ignore_whitespace);
+ group_concat.span.end = self.pos();
+ self.bump();
+ group.span.end = self.pos();
+ match alt {
+ Some(mut alt) => {
+ alt.span.end = group_concat.span.end;
+ alt.asts.push(group_concat.into_ast());
+ group.ast = Box::new(alt.into_ast());
+ }
+ None => {
+ group.ast = Box::new(group_concat.into_ast());
+ }
+ }
+ prior_concat.asts.push(Ast::Group(group));
+ Ok(prior_concat)
+ }
+
+ /// Pop the last state from the parser's internal stack, if it exists, and
+ /// add the given concatenation to it. There either must be no state or a
+ /// single alternation item on the stack. Any other scenario produces an
+ /// error.
+ ///
+ /// This assumes that the parser has advanced to the end.
+ #[inline(never)]
+ fn pop_group_end(&self, mut concat: ast::Concat) -> Result<Ast> {
+ concat.span.end = self.pos();
+ let mut stack = self.parser().stack_group.borrow_mut();
+ let ast = match stack.pop() {
+ None => Ok(concat.into_ast()),
+ Some(GroupState::Alternation(mut alt)) => {
+ alt.span.end = self.pos();
+ alt.asts.push(concat.into_ast());
+ Ok(Ast::Alternation(alt))
+ }
+ Some(GroupState::Group { group, .. }) => {
+ return Err(
+ self.error(group.span, ast::ErrorKind::GroupUnclosed)
+ );
+ }
+ };
+ // If we try to pop again, there should be nothing.
+ match stack.pop() {
+ None => ast,
+ Some(GroupState::Alternation(_)) => {
+ // This unreachable is unfortunate. This case can't happen
+ // because the only way we can be here is if there were two
+ // `GroupState::Alternation`s adjacent in the parser's stack,
+ // which we guarantee to never happen because we never push a
+ // `GroupState::Alternation` if one is already at the top of
+ // the stack.
+ unreachable!()
+ }
+ Some(GroupState::Group { group, .. }) => {
+ Err(self.error(group.span, ast::ErrorKind::GroupUnclosed))
+ }
+ }
+ }
+
+ /// Parse the opening of a character class and push the current class
+ /// parsing context onto the parser's stack. This assumes that the parser
+ /// is positioned at an opening `[`. The given union should correspond to
+ /// the union of set items built up before seeing the `[`.
+ ///
+ /// If there was a problem parsing the opening of the class, then an error
+ /// is returned. Otherwise, a new union of set items for the class is
+ /// returned (which may be populated with either a `]` or a `-`).
+ #[inline(never)]
+ fn push_class_open(
+ &self,
+ parent_union: ast::ClassSetUnion,
+ ) -> Result<ast::ClassSetUnion> {
+ assert_eq!(self.char(), '[');
+
+ let (nested_set, nested_union) = self.parse_set_class_open()?;
+ self.parser()
+ .stack_class
+ .borrow_mut()
+ .push(ClassState::Open { union: parent_union, set: nested_set });
+ Ok(nested_union)
+ }
+
+ /// Parse the end of a character class set and pop the character class
+ /// parser stack. The union given corresponds to the last union built
+ /// before seeing the closing `]`. The union returned corresponds to the
+ /// parent character class set with the nested class added to it.
+ ///
+ /// This assumes that the parser is positioned at a `]` and will advance
+ /// the parser to the byte immediately following the `]`.
+ ///
+ /// If the stack is empty after popping, then this returns the final
+ /// "top-level" character class AST (where a "top-level" character class
+ /// is one that is not nested inside any other character class).
+ ///
+ /// If there is no corresponding opening bracket on the parser's stack,
+ /// then an error is returned.
+ #[inline(never)]
+ fn pop_class(
+ &self,
+ nested_union: ast::ClassSetUnion,
+ ) -> Result<Either<ast::ClassSetUnion, ast::Class>> {
+ assert_eq!(self.char(), ']');
+
+ let item = ast::ClassSet::Item(nested_union.into_item());
+ let prevset = self.pop_class_op(item);
+ let mut stack = self.parser().stack_class.borrow_mut();
+ match stack.pop() {
+ None => {
+ // We can never observe an empty stack:
+ //
+ // 1) We are guaranteed to start with a non-empty stack since
+ // the character class parser is only initiated when it sees
+ // a `[`.
+ // 2) If we ever observe an empty stack while popping after
+ // seeing a `]`, then we signal the character class parser
+ // to terminate.
+ panic!("unexpected empty character class stack")
+ }
+ Some(ClassState::Op { .. }) => {
+ // This panic is unfortunate, but this case is impossible
+ // since we already popped the Op state if one exists above.
+ // Namely, every push to the class parser stack is guarded by
+ // whether an existing Op is already on the top of the stack.
+ // If it is, the existing Op is modified. That is, the stack
+ // can never have consecutive Op states.
+ panic!("unexpected ClassState::Op")
+ }
+ Some(ClassState::Open { mut union, mut set }) => {
+ self.bump();
+ set.span.end = self.pos();
+ set.kind = prevset;
+ if stack.is_empty() {
+ Ok(Either::Right(ast::Class::Bracketed(set)))
+ } else {
+ union.push(ast::ClassSetItem::Bracketed(Box::new(set)));
+ Ok(Either::Left(union))
+ }
+ }
+ }
+ }
+
+ /// Return an "unclosed class" error whose span points to the most
+ /// recently opened class.
+ ///
+ /// This should only be called while parsing a character class.
+ #[inline(never)]
+ fn unclosed_class_error(&self) -> ast::Error {
+ for state in self.parser().stack_class.borrow().iter().rev() {
+ match *state {
+ ClassState::Open { ref set, .. } => {
+ return self
+ .error(set.span, ast::ErrorKind::ClassUnclosed);
+ }
+ _ => {}
+ }
+ }
+ // We are guaranteed to have a non-empty stack with at least
+ // one open bracket, so we should never get here.
+ panic!("no open character class found")
+ }
+
+ /// Push the current set of class items on to the class parser's stack as
+ /// the left hand side of the given operator.
+ ///
+ /// A fresh set union is returned, which should be used to build the right
+ /// hand side of this operator.
+ #[inline(never)]
+ fn push_class_op(
+ &self,
+ next_kind: ast::ClassSetBinaryOpKind,
+ next_union: ast::ClassSetUnion,
+ ) -> ast::ClassSetUnion {
+ let item = ast::ClassSet::Item(next_union.into_item());
+ let new_lhs = self.pop_class_op(item);
+ self.parser()
+ .stack_class
+ .borrow_mut()
+ .push(ClassState::Op { kind: next_kind, lhs: new_lhs });
+ ast::ClassSetUnion { span: self.span(), items: vec![] }
+ }
+
+ /// Pop a character class set from the character class parser stack. If the
+ /// top of the stack is just an item (not an operation), then return the
+ /// given set unchanged. If the top of the stack is an operation, then the
+ /// given set will be used as the rhs of the operation on the top of the
+ /// stack. In that case, the binary operation is returned as a set.
+ #[inline(never)]
+ fn pop_class_op(&self, rhs: ast::ClassSet) -> ast::ClassSet {
+ let mut stack = self.parser().stack_class.borrow_mut();
+ let (kind, lhs) = match stack.pop() {
+ Some(ClassState::Op { kind, lhs }) => (kind, lhs),
+ Some(state @ ClassState::Open { .. }) => {
+ stack.push(state);
+ return rhs;
+ }
+ None => unreachable!(),
+ };
+ let span = Span::new(lhs.span().start, rhs.span().end);
+ ast::ClassSet::BinaryOp(ast::ClassSetBinaryOp {
+ span: span,
+ kind: kind,
+ lhs: Box::new(lhs),
+ rhs: Box::new(rhs),
+ })
+ }
+}
+
+impl<'s, P: Borrow<Parser>> ParserI<'s, P> {
+ /// Parse the regular expression into an abstract syntax tree.
+ fn parse(&self) -> Result<Ast> {
+ self.parse_with_comments().map(|astc| astc.ast)
+ }
+
+ /// Parse the regular expression and return an abstract syntax tree with
+ /// all of the comments found in the pattern.
+ fn parse_with_comments(&self) -> Result<ast::WithComments> {
+ assert_eq!(self.offset(), 0, "parser can only be used once");
+ self.parser().reset();
+ let mut concat = ast::Concat { span: self.span(), asts: vec![] };
+ loop {
+ self.bump_space();
+ if self.is_eof() {
+ break;
+ }
+ match self.char() {
+ '(' => concat = self.push_group(concat)?,
+ ')' => concat = self.pop_group(concat)?,
+ '|' => concat = self.push_alternate(concat)?,
+ '[' => {
+ let class = self.parse_set_class()?;
+ concat.asts.push(Ast::Class(class));
+ }
+ '?' => {
+ concat = self.parse_uncounted_repetition(
+ concat,
+ ast::RepetitionKind::ZeroOrOne,
+ )?;
+ }
+ '*' => {
+ concat = self.parse_uncounted_repetition(
+ concat,
+ ast::RepetitionKind::ZeroOrMore,
+ )?;
+ }
+ '+' => {
+ concat = self.parse_uncounted_repetition(
+ concat,
+ ast::RepetitionKind::OneOrMore,
+ )?;
+ }
+ '{' => {
+ concat = self.parse_counted_repetition(concat)?;
+ }
+ _ => concat.asts.push(self.parse_primitive()?.into_ast()),
+ }
+ }
+ let ast = self.pop_group_end(concat)?;
+ NestLimiter::new(self).check(&ast)?;
+ Ok(ast::WithComments {
+ ast: ast,
+ comments: mem::replace(
+ &mut *self.parser().comments.borrow_mut(),
+ vec![],
+ ),
+ })
+ }
+
+ /// Parses an uncounted repetition operation. An uncounted repetition
+ /// operator includes ?, * and +, but does not include the {m,n} syntax.
+ /// The given `kind` should correspond to the operator observed by the
+ /// caller.
+ ///
+ /// This assumes that the paser is currently positioned at the repetition
+ /// operator and advances the parser to the first character after the
+ /// operator. (Note that the operator may include a single additional `?`,
+ /// which makes the operator ungreedy.)
+ ///
+ /// The caller should include the concatenation that is being built. The
+ /// concatenation returned includes the repetition operator applied to the
+ /// last expression in the given concatenation.
+ #[inline(never)]
+ fn parse_uncounted_repetition(
+ &self,
+ mut concat: ast::Concat,
+ kind: ast::RepetitionKind,
+ ) -> Result<ast::Concat> {
+ assert!(
+ self.char() == '?' || self.char() == '*' || self.char() == '+'
+ );
+ let op_start = self.pos();
+ let ast = match concat.asts.pop() {
+ Some(ast) => ast,
+ None => {
+ return Err(
+ self.error(self.span(), ast::ErrorKind::RepetitionMissing)
+ )
+ }
+ };
+ match ast {
+ Ast::Empty(_) | Ast::Flags(_) => {
+ return Err(
+ self.error(self.span(), ast::ErrorKind::RepetitionMissing)
+ )
+ }
+ _ => {}
+ }
+ let mut greedy = true;
+ if self.bump() && self.char() == '?' {
+ greedy = false;
+ self.bump();
+ }
+ concat.asts.push(Ast::Repetition(ast::Repetition {
+ span: ast.span().with_end(self.pos()),
+ op: ast::RepetitionOp {
+ span: Span::new(op_start, self.pos()),
+ kind: kind,
+ },
+ greedy: greedy,
+ ast: Box::new(ast),
+ }));
+ Ok(concat)
+ }
+
+ /// Parses a counted repetition operation. A counted repetition operator
+ /// corresponds to the {m,n} syntax, and does not include the ?, * or +
+ /// operators.
+ ///
+ /// This assumes that the paser is currently positioned at the opening `{`
+ /// and advances the parser to the first character after the operator.
+ /// (Note that the operator may include a single additional `?`, which
+ /// makes the operator ungreedy.)
+ ///
+ /// The caller should include the concatenation that is being built. The
+ /// concatenation returned includes the repetition operator applied to the
+ /// last expression in the given concatenation.
+ #[inline(never)]
+ fn parse_counted_repetition(
+ &self,
+ mut concat: ast::Concat,
+ ) -> Result<ast::Concat> {
+ assert!(self.char() == '{');
+ let start = self.pos();
+ let ast = match concat.asts.pop() {
+ Some(ast) => ast,
+ None => {
+ return Err(
+ self.error(self.span(), ast::ErrorKind::RepetitionMissing)
+ )
+ }
+ };
+ match ast {
+ Ast::Empty(_) | Ast::Flags(_) => {
+ return Err(
+ self.error(self.span(), ast::ErrorKind::RepetitionMissing)
+ )
+ }
+ _ => {}
+ }
+ if !self.bump_and_bump_space() {
+ return Err(self.error(
+ Span::new(start, self.pos()),
+ ast::ErrorKind::RepetitionCountUnclosed,
+ ));
+ }
+ let count_start = specialize_err(
+ self.parse_decimal(),
+ ast::ErrorKind::DecimalEmpty,
+ ast::ErrorKind::RepetitionCountDecimalEmpty,
+ )?;
+ let mut range = ast::RepetitionRange::Exactly(count_start);
+ if self.is_eof() {
+ return Err(self.error(
+ Span::new(start, self.pos()),
+ ast::ErrorKind::RepetitionCountUnclosed,
+ ));
+ }
+ if self.char() == ',' {
+ if !self.bump_and_bump_space() {
+ return Err(self.error(
+ Span::new(start, self.pos()),
+ ast::ErrorKind::RepetitionCountUnclosed,
+ ));
+ }
+ if self.char() != '}' {
+ let count_end = specialize_err(
+ self.parse_decimal(),
+ ast::ErrorKind::DecimalEmpty,
+ ast::ErrorKind::RepetitionCountDecimalEmpty,
+ )?;
+ range = ast::RepetitionRange::Bounded(count_start, count_end);
+ } else {
+ range = ast::RepetitionRange::AtLeast(count_start);
+ }
+ }
+ if self.is_eof() || self.char() != '}' {
+ return Err(self.error(
+ Span::new(start, self.pos()),
+ ast::ErrorKind::RepetitionCountUnclosed,
+ ));
+ }
+
+ let mut greedy = true;
+ if self.bump_and_bump_space() && self.char() == '?' {
+ greedy = false;
+ self.bump();
+ }
+
+ let op_span = Span::new(start, self.pos());
+ if !range.is_valid() {
+ return Err(
+ self.error(op_span, ast::ErrorKind::RepetitionCountInvalid)
+ );
+ }
+ concat.asts.push(Ast::Repetition(ast::Repetition {
+ span: ast.span().with_end(self.pos()),
+ op: ast::RepetitionOp {
+ span: op_span,
+ kind: ast::RepetitionKind::Range(range),
+ },
+ greedy: greedy,
+ ast: Box::new(ast),
+ }));
+ Ok(concat)
+ }
+
+ /// Parse a group (which contains a sub-expression) or a set of flags.
+ ///
+ /// If a group was found, then it is returned with an empty AST. If a set
+ /// of flags is found, then that set is returned.
+ ///
+ /// The parser should be positioned at the opening parenthesis.
+ ///
+ /// This advances the parser to the character before the start of the
+ /// sub-expression (in the case of a group) or to the closing parenthesis
+ /// immediately following the set of flags.
+ ///
+ /// # Errors
+ ///
+ /// If flags are given and incorrectly specified, then a corresponding
+ /// error is returned.
+ ///
+ /// If a capture name is given and it is incorrectly specified, then a
+ /// corresponding error is returned.
+ #[inline(never)]
+ fn parse_group(&self) -> Result<Either<ast::SetFlags, ast::Group>> {
+ assert_eq!(self.char(), '(');
+ let open_span = self.span_char();
+ self.bump();
+ self.bump_space();
+ if self.is_lookaround_prefix() {
+ return Err(self.error(
+ Span::new(open_span.start, self.span().end),
+ ast::ErrorKind::UnsupportedLookAround,
+ ));
+ }
+ let inner_span = self.span();
+ if self.bump_if("?P<") {
+ let capture_index = self.next_capture_index(open_span)?;
+ let cap = self.parse_capture_name(capture_index)?;
+ Ok(Either::Right(ast::Group {
+ span: open_span,
+ kind: ast::GroupKind::CaptureName(cap),
+ ast: Box::new(Ast::Empty(self.span())),
+ }))
+ } else if self.bump_if("?") {
+ if self.is_eof() {
+ return Err(
+ self.error(open_span, ast::ErrorKind::GroupUnclosed)
+ );
+ }
+ let flags = self.parse_flags()?;
+ let char_end = self.char();
+ self.bump();
+ if char_end == ')' {
+ // We don't allow empty flags, e.g., `(?)`. We instead
+ // interpret it as a repetition operator missing its argument.
+ if flags.items.is_empty() {
+ return Err(self.error(
+ inner_span,
+ ast::ErrorKind::RepetitionMissing,
+ ));
+ }
+ Ok(Either::Left(ast::SetFlags {
+ span: Span { end: self.pos(), ..open_span },
+ flags: flags,
+ }))
+ } else {
+ assert_eq!(char_end, ':');
+ Ok(Either::Right(ast::Group {
+ span: open_span,
+ kind: ast::GroupKind::NonCapturing(flags),
+ ast: Box::new(Ast::Empty(self.span())),
+ }))
+ }
+ } else {
+ let capture_index = self.next_capture_index(open_span)?;
+ Ok(Either::Right(ast::Group {
+ span: open_span,
+ kind: ast::GroupKind::CaptureIndex(capture_index),
+ ast: Box::new(Ast::Empty(self.span())),
+ }))
+ }
+ }
+
+ /// Parses a capture group name. Assumes that the parser is positioned at
+ /// the first character in the name following the opening `<` (and may
+ /// possibly be EOF). This advances the parser to the first character
+ /// following the closing `>`.
+ ///
+ /// The caller must provide the capture index of the group for this name.
+ #[inline(never)]
+ fn parse_capture_name(
+ &self,
+ capture_index: u32,
+ ) -> Result<ast::CaptureName> {
+ if self.is_eof() {
+ return Err(self
+ .error(self.span(), ast::ErrorKind::GroupNameUnexpectedEof));
+ }
+ let start = self.pos();
+ loop {
+ if self.char() == '>' {
+ break;
+ }
+ if !is_capture_char(self.char(), self.pos() == start) {
+ return Err(self.error(
+ self.span_char(),
+ ast::ErrorKind::GroupNameInvalid,
+ ));
+ }
+ if !self.bump() {
+ break;
+ }
+ }
+ let end = self.pos();
+ if self.is_eof() {
+ return Err(self
+ .error(self.span(), ast::ErrorKind::GroupNameUnexpectedEof));
+ }
+ assert_eq!(self.char(), '>');
+ self.bump();
+ let name = &self.pattern()[start.offset..end.offset];
+ if name.is_empty() {
+ return Err(self.error(
+ Span::new(start, start),
+ ast::ErrorKind::GroupNameEmpty,
+ ));
+ }
+ let capname = ast::CaptureName {
+ span: Span::new(start, end),
+ name: name.to_string(),
+ index: capture_index,
+ };
+ self.add_capture_name(&capname)?;
+ Ok(capname)
+ }
+
+ /// Parse a sequence of flags starting at the current character.
+ ///
+ /// This advances the parser to the character immediately following the
+ /// flags, which is guaranteed to be either `:` or `)`.
+ ///
+ /// # Errors
+ ///
+ /// If any flags are duplicated, then an error is returned.
+ ///
+ /// If the negation operator is used more than once, then an error is
+ /// returned.
+ ///
+ /// If no flags could be found or if the negation operation is not followed
+ /// by any flags, then an error is returned.
+ #[inline(never)]
+ fn parse_flags(&self) -> Result<ast::Flags> {
+ let mut flags = ast::Flags { span: self.span(), items: vec![] };
+ let mut last_was_negation = None;
+ while self.char() != ':' && self.char() != ')' {
+ if self.char() == '-' {
+ last_was_negation = Some(self.span_char());
+ let item = ast::FlagsItem {
+ span: self.span_char(),
+ kind: ast::FlagsItemKind::Negation,
+ };
+ if let Some(i) = flags.add_item(item) {
+ return Err(self.error(
+ self.span_char(),
+ ast::ErrorKind::FlagRepeatedNegation {
+ original: flags.items[i].span,
+ },
+ ));
+ }
+ } else {
+ last_was_negation = None;
+ let item = ast::FlagsItem {
+ span: self.span_char(),
+ kind: ast::FlagsItemKind::Flag(self.parse_flag()?),
+ };
+ if let Some(i) = flags.add_item(item) {
+ return Err(self.error(
+ self.span_char(),
+ ast::ErrorKind::FlagDuplicate {
+ original: flags.items[i].span,
+ },
+ ));
+ }
+ }
+ if !self.bump() {
+ return Err(
+ self.error(self.span(), ast::ErrorKind::FlagUnexpectedEof)
+ );
+ }
+ }
+ if let Some(span) = last_was_negation {
+ return Err(self.error(span, ast::ErrorKind::FlagDanglingNegation));
+ }
+ flags.span.end = self.pos();
+ Ok(flags)
+ }
+
+ /// Parse the current character as a flag. Do not advance the parser.
+ ///
+ /// # Errors
+ ///
+ /// If the flag is not recognized, then an error is returned.
+ #[inline(never)]
+ fn parse_flag(&self) -> Result<ast::Flag> {
+ match self.char() {
+ 'i' => Ok(ast::Flag::CaseInsensitive),
+ 'm' => Ok(ast::Flag::MultiLine),
+ 's' => Ok(ast::Flag::DotMatchesNewLine),
+ 'U' => Ok(ast::Flag::SwapGreed),
+ 'u' => Ok(ast::Flag::Unicode),
+ 'x' => Ok(ast::Flag::IgnoreWhitespace),
+ _ => {
+ Err(self
+ .error(self.span_char(), ast::ErrorKind::FlagUnrecognized))
+ }
+ }
+ }
+
+ /// Parse a primitive AST. e.g., A literal, non-set character class or
+ /// assertion.
+ ///
+ /// This assumes that the parser expects a primitive at the current
+ /// location. i.e., All other non-primitive cases have been handled.
+ /// For example, if the parser's position is at `|`, then `|` will be
+ /// treated as a literal (e.g., inside a character class).
+ ///
+ /// This advances the parser to the first character immediately following
+ /// the primitive.
+ fn parse_primitive(&self) -> Result<Primitive> {
+ match self.char() {
+ '\\' => self.parse_escape(),
+ '.' => {
+ let ast = Primitive::Dot(self.span_char());
+ self.bump();
+ Ok(ast)
+ }
+ '^' => {
+ let ast = Primitive::Assertion(ast::Assertion {
+ span: self.span_char(),
+ kind: ast::AssertionKind::StartLine,
+ });
+ self.bump();
+ Ok(ast)
+ }
+ '$' => {
+ let ast = Primitive::Assertion(ast::Assertion {
+ span: self.span_char(),
+ kind: ast::AssertionKind::EndLine,
+ });
+ self.bump();
+ Ok(ast)
+ }
+ c => {
+ let ast = Primitive::Literal(ast::Literal {
+ span: self.span_char(),
+ kind: ast::LiteralKind::Verbatim,
+ c: c,
+ });
+ self.bump();
+ Ok(ast)
+ }
+ }
+ }
+
+ /// Parse an escape sequence as a primitive AST.
+ ///
+ /// This assumes the parser is positioned at the start of the escape
+ /// sequence, i.e., `\`. It advances the parser to the first position
+ /// immediately following the escape sequence.
+ #[inline(never)]
+ fn parse_escape(&self) -> Result<Primitive> {
+ assert_eq!(self.char(), '\\');
+ let start = self.pos();
+ if !self.bump() {
+ return Err(self.error(
+ Span::new(start, self.pos()),
+ ast::ErrorKind::EscapeUnexpectedEof,
+ ));
+ }
+ let c = self.char();
+ // Put some of the more complicated routines into helpers.
+ match c {
+ '0'..='7' => {
+ if !self.parser().octal {
+ return Err(self.error(
+ Span::new(start, self.span_char().end),
+ ast::ErrorKind::UnsupportedBackreference,
+ ));
+ }
+ let mut lit = self.parse_octal();
+ lit.span.start = start;
+ return Ok(Primitive::Literal(lit));
+ }
+ '8'..='9' if !self.parser().octal => {
+ return Err(self.error(
+ Span::new(start, self.span_char().end),
+ ast::ErrorKind::UnsupportedBackreference,
+ ));
+ }
+ 'x' | 'u' | 'U' => {
+ let mut lit = self.parse_hex()?;
+ lit.span.start = start;
+ return Ok(Primitive::Literal(lit));
+ }
+ 'p' | 'P' => {
+ let mut cls = self.parse_unicode_class()?;
+ cls.span.start = start;
+ return Ok(Primitive::Unicode(cls));
+ }
+ 'd' | 's' | 'w' | 'D' | 'S' | 'W' => {
+ let mut cls = self.parse_perl_class();
+ cls.span.start = start;
+ return Ok(Primitive::Perl(cls));
+ }
+ _ => {}
+ }
+
+ // Handle all of the one letter sequences inline.
+ self.bump();
+ let span = Span::new(start, self.pos());
+ if is_meta_character(c) {
+ return Ok(Primitive::Literal(ast::Literal {
+ span: span,
+ kind: ast::LiteralKind::Punctuation,
+ c: c,
+ }));
+ }
+ let special = |kind, c| {
+ Ok(Primitive::Literal(ast::Literal {
+ span: span,
+ kind: ast::LiteralKind::Special(kind),
+ c: c,
+ }))
+ };
+ match c {
+ 'a' => special(ast::SpecialLiteralKind::Bell, '\x07'),
+ 'f' => special(ast::SpecialLiteralKind::FormFeed, '\x0C'),
+ 't' => special(ast::SpecialLiteralKind::Tab, '\t'),
+ 'n' => special(ast::SpecialLiteralKind::LineFeed, '\n'),
+ 'r' => special(ast::SpecialLiteralKind::CarriageReturn, '\r'),
+ 'v' => special(ast::SpecialLiteralKind::VerticalTab, '\x0B'),
+ ' ' if self.ignore_whitespace() => {
+ special(ast::SpecialLiteralKind::Space, ' ')
+ }
+ 'A' => Ok(Primitive::Assertion(ast::Assertion {
+ span: span,
+ kind: ast::AssertionKind::StartText,
+ })),
+ 'z' => Ok(Primitive::Assertion(ast::Assertion {
+ span: span,
+ kind: ast::AssertionKind::EndText,
+ })),
+ 'b' => Ok(Primitive::Assertion(ast::Assertion {
+ span: span,
+ kind: ast::AssertionKind::WordBoundary,
+ })),
+ 'B' => Ok(Primitive::Assertion(ast::Assertion {
+ span: span,
+ kind: ast::AssertionKind::NotWordBoundary,
+ })),
+ _ => Err(self.error(span, ast::ErrorKind::EscapeUnrecognized)),
+ }
+ }
+
+ /// Parse an octal representation of a Unicode codepoint up to 3 digits
+ /// long. This expects the parser to be positioned at the first octal
+ /// digit and advances the parser to the first character immediately
+ /// following the octal number. This also assumes that parsing octal
+ /// escapes is enabled.
+ ///
+ /// Assuming the preconditions are met, this routine can never fail.
+ #[inline(never)]
+ fn parse_octal(&self) -> ast::Literal {
+ use std::char;
+ use std::u32;
+
+ assert!(self.parser().octal);
+ assert!('0' <= self.char() && self.char() <= '7');
+ let start = self.pos();
+ // Parse up to two more digits.
+ while self.bump()
+ && '0' <= self.char()
+ && self.char() <= '7'
+ && self.pos().offset - start.offset <= 2
+ {}
+ let end = self.pos();
+ let octal = &self.pattern()[start.offset..end.offset];
+ // Parsing the octal should never fail since the above guarantees a
+ // valid number.
+ let codepoint =
+ u32::from_str_radix(octal, 8).expect("valid octal number");
+ // The max value for 3 digit octal is 0777 = 511 and [0, 511] has no
+ // invalid Unicode scalar values.
+ let c = char::from_u32(codepoint).expect("Unicode scalar value");
+ ast::Literal {
+ span: Span::new(start, end),
+ kind: ast::LiteralKind::Octal,
+ c: c,
+ }
+ }
+
+ /// Parse a hex representation of a Unicode codepoint. This handles both
+ /// hex notations, i.e., `\xFF` and `\x{FFFF}`. This expects the parser to
+ /// be positioned at the `x`, `u` or `U` prefix. The parser is advanced to
+ /// the first character immediately following the hexadecimal literal.
+ #[inline(never)]
+ fn parse_hex(&self) -> Result<ast::Literal> {
+ assert!(
+ self.char() == 'x' || self.char() == 'u' || self.char() == 'U'
+ );
+
+ let hex_kind = match self.char() {
+ 'x' => ast::HexLiteralKind::X,
+ 'u' => ast::HexLiteralKind::UnicodeShort,
+ _ => ast::HexLiteralKind::UnicodeLong,
+ };
+ if !self.bump_and_bump_space() {
+ return Err(
+ self.error(self.span(), ast::ErrorKind::EscapeUnexpectedEof)
+ );
+ }
+ if self.char() == '{' {
+ self.parse_hex_brace(hex_kind)
+ } else {
+ self.parse_hex_digits(hex_kind)
+ }
+ }
+
+ /// Parse an N-digit hex representation of a Unicode codepoint. This
+ /// expects the parser to be positioned at the first digit and will advance
+ /// the parser to the first character immediately following the escape
+ /// sequence.
+ ///
+ /// The number of digits given must be 2 (for `\xNN`), 4 (for `\uNNNN`)
+ /// or 8 (for `\UNNNNNNNN`).
+ #[inline(never)]
+ fn parse_hex_digits(
+ &self,
+ kind: ast::HexLiteralKind,
+ ) -> Result<ast::Literal> {
+ use std::char;
+ use std::u32;
+
+ let mut scratch = self.parser().scratch.borrow_mut();
+ scratch.clear();
+
+ let start = self.pos();
+ for i in 0..kind.digits() {
+ if i > 0 && !self.bump_and_bump_space() {
+ return Err(self
+ .error(self.span(), ast::ErrorKind::EscapeUnexpectedEof));
+ }
+ if !is_hex(self.char()) {
+ return Err(self.error(
+ self.span_char(),
+ ast::ErrorKind::EscapeHexInvalidDigit,
+ ));
+ }
+ scratch.push(self.char());
+ }
+ // The final bump just moves the parser past the literal, which may
+ // be EOF.
+ self.bump_and_bump_space();
+ let end = self.pos();
+ let hex = scratch.as_str();
+ match u32::from_str_radix(hex, 16).ok().and_then(char::from_u32) {
+ None => Err(self.error(
+ Span::new(start, end),
+ ast::ErrorKind::EscapeHexInvalid,
+ )),
+ Some(c) => Ok(ast::Literal {
+ span: Span::new(start, end),
+ kind: ast::LiteralKind::HexFixed(kind),
+ c: c,
+ }),
+ }
+ }
+
+ /// Parse a hex representation of any Unicode scalar value. This expects
+ /// the parser to be positioned at the opening brace `{` and will advance
+ /// the parser to the first character following the closing brace `}`.
+ #[inline(never)]
+ fn parse_hex_brace(
+ &self,
+ kind: ast::HexLiteralKind,
+ ) -> Result<ast::Literal> {
+ use std::char;
+ use std::u32;
+
+ let mut scratch = self.parser().scratch.borrow_mut();
+ scratch.clear();
+
+ let brace_pos = self.pos();
+ let start = self.span_char().end;
+ while self.bump_and_bump_space() && self.char() != '}' {
+ if !is_hex(self.char()) {
+ return Err(self.error(
+ self.span_char(),
+ ast::ErrorKind::EscapeHexInvalidDigit,
+ ));
+ }
+ scratch.push(self.char());
+ }
+ if self.is_eof() {
+ return Err(self.error(
+ Span::new(brace_pos, self.pos()),
+ ast::ErrorKind::EscapeUnexpectedEof,
+ ));
+ }
+ let end = self.pos();
+ let hex = scratch.as_str();
+ assert_eq!(self.char(), '}');
+ self.bump_and_bump_space();
+
+ if hex.is_empty() {
+ return Err(self.error(
+ Span::new(brace_pos, self.pos()),
+ ast::ErrorKind::EscapeHexEmpty,
+ ));
+ }
+ match u32::from_str_radix(hex, 16).ok().and_then(char::from_u32) {
+ None => Err(self.error(
+ Span::new(start, end),
+ ast::ErrorKind::EscapeHexInvalid,
+ )),
+ Some(c) => Ok(ast::Literal {
+ span: Span::new(start, self.pos()),
+ kind: ast::LiteralKind::HexBrace(kind),
+ c: c,
+ }),
+ }
+ }
+
+ /// Parse a decimal number into a u32 while trimming leading and trailing
+ /// whitespace.
+ ///
+ /// This expects the parser to be positioned at the first position where
+ /// a decimal digit could occur. This will advance the parser to the byte
+ /// immediately following the last contiguous decimal digit.
+ ///
+ /// If no decimal digit could be found or if there was a problem parsing
+ /// the complete set of digits into a u32, then an error is returned.
+ fn parse_decimal(&self) -> Result<u32> {
+ let mut scratch = self.parser().scratch.borrow_mut();
+ scratch.clear();
+
+ while !self.is_eof() && self.char().is_whitespace() {
+ self.bump();
+ }
+ let start = self.pos();
+ while !self.is_eof() && '0' <= self.char() && self.char() <= '9' {
+ scratch.push(self.char());
+ self.bump_and_bump_space();
+ }
+ let span = Span::new(start, self.pos());
+ while !self.is_eof() && self.char().is_whitespace() {
+ self.bump_and_bump_space();
+ }
+ let digits = scratch.as_str();
+ if digits.is_empty() {
+ return Err(self.error(span, ast::ErrorKind::DecimalEmpty));
+ }
+ match u32::from_str_radix(digits, 10).ok() {
+ Some(n) => Ok(n),
+ None => Err(self.error(span, ast::ErrorKind::DecimalInvalid)),
+ }
+ }
+
+ /// Parse a standard character class consisting primarily of characters or
+ /// character ranges, but can also contain nested character classes of
+ /// any type (sans `.`).
+ ///
+ /// This assumes the parser is positioned at the opening `[`. If parsing
+ /// is successful, then the parser is advanced to the position immediately
+ /// following the closing `]`.
+ #[inline(never)]
+ fn parse_set_class(&self) -> Result<ast::Class> {
+ assert_eq!(self.char(), '[');
+
+ let mut union =
+ ast::ClassSetUnion { span: self.span(), items: vec![] };
+ loop {
+ self.bump_space();
+ if self.is_eof() {
+ return Err(self.unclosed_class_error());
+ }
+ match self.char() {
+ '[' => {
+ // If we've already parsed the opening bracket, then
+ // attempt to treat this as the beginning of an ASCII
+ // class. If ASCII class parsing fails, then the parser
+ // backs up to `[`.
+ if !self.parser().stack_class.borrow().is_empty() {
+ if let Some(cls) = self.maybe_parse_ascii_class() {
+ union.push(ast::ClassSetItem::Ascii(cls));
+ continue;
+ }
+ }
+ union = self.push_class_open(union)?;
+ }
+ ']' => match self.pop_class(union)? {
+ Either::Left(nested_union) => {
+ union = nested_union;
+ }
+ Either::Right(class) => return Ok(class),
+ },
+ '&' if self.peek() == Some('&') => {
+ assert!(self.bump_if("&&"));
+ union = self.push_class_op(
+ ast::ClassSetBinaryOpKind::Intersection,
+ union,
+ );
+ }
+ '-' if self.peek() == Some('-') => {
+ assert!(self.bump_if("--"));
+ union = self.push_class_op(
+ ast::ClassSetBinaryOpKind::Difference,
+ union,
+ );
+ }
+ '~' if self.peek() == Some('~') => {
+ assert!(self.bump_if("~~"));
+ union = self.push_class_op(
+ ast::ClassSetBinaryOpKind::SymmetricDifference,
+ union,
+ );
+ }
+ _ => {
+ union.push(self.parse_set_class_range()?);
+ }
+ }
+ }
+ }
+
+ /// Parse a single primitive item in a character class set. The item to
+ /// be parsed can either be one of a simple literal character, a range
+ /// between two simple literal characters or a "primitive" character
+ /// class like \w or \p{Greek}.
+ ///
+ /// If an invalid escape is found, or if a character class is found where
+ /// a simple literal is expected (e.g., in a range), then an error is
+ /// returned.
+ #[inline(never)]
+ fn parse_set_class_range(&self) -> Result<ast::ClassSetItem> {
+ let prim1 = self.parse_set_class_item()?;
+ self.bump_space();
+ if self.is_eof() {
+ return Err(self.unclosed_class_error());
+ }
+ // If the next char isn't a `-`, then we don't have a range.
+ // There are two exceptions. If the char after a `-` is a `]`, then
+ // `-` is interpreted as a literal `-`. Alternatively, if the char
+ // after a `-` is a `-`, then `--` corresponds to a "difference"
+ // operation.
+ if self.char() != '-'
+ || self.peek_space() == Some(']')
+ || self.peek_space() == Some('-')
+ {
+ return prim1.into_class_set_item(self);
+ }
+ // OK, now we're parsing a range, so bump past the `-` and parse the
+ // second half of the range.
+ if !self.bump_and_bump_space() {
+ return Err(self.unclosed_class_error());
+ }
+ let prim2 = self.parse_set_class_item()?;
+ let range = ast::ClassSetRange {
+ span: Span::new(prim1.span().start, prim2.span().end),
+ start: prim1.into_class_literal(self)?,
+ end: prim2.into_class_literal(self)?,
+ };
+ if !range.is_valid() {
+ return Err(
+ self.error(range.span, ast::ErrorKind::ClassRangeInvalid)
+ );
+ }
+ Ok(ast::ClassSetItem::Range(range))
+ }
+
+ /// Parse a single item in a character class as a primitive, where the
+ /// primitive either consists of a verbatim literal or a single escape
+ /// sequence.
+ ///
+ /// This assumes the parser is positioned at the beginning of a primitive,
+ /// and advances the parser to the first position after the primitive if
+ /// successful.
+ ///
+ /// Note that it is the caller's responsibility to report an error if an
+ /// illegal primitive was parsed.
+ #[inline(never)]
+ fn parse_set_class_item(&self) -> Result<Primitive> {
+ if self.char() == '\\' {
+ self.parse_escape()
+ } else {
+ let x = Primitive::Literal(ast::Literal {
+ span: self.span_char(),
+ kind: ast::LiteralKind::Verbatim,
+ c: self.char(),
+ });
+ self.bump();
+ Ok(x)
+ }
+ }
+
+ /// Parses the opening of a character class set. This includes the opening
+ /// bracket along with `^` if present to indicate negation. This also
+ /// starts parsing the opening set of unioned items if applicable, since
+ /// there are special rules applied to certain characters in the opening
+ /// of a character class. For example, `[^]]` is the class of all
+ /// characters not equal to `]`. (`]` would need to be escaped in any other
+ /// position.) Similarly for `-`.
+ ///
+ /// In all cases, the op inside the returned `ast::ClassBracketed` is an
+ /// empty union. This empty union should be replaced with the actual item
+ /// when it is popped from the parser's stack.
+ ///
+ /// This assumes the parser is positioned at the opening `[` and advances
+ /// the parser to the first non-special byte of the character class.
+ ///
+ /// An error is returned if EOF is found.
+ #[inline(never)]
+ fn parse_set_class_open(
+ &self,
+ ) -> Result<(ast::ClassBracketed, ast::ClassSetUnion)> {
+ assert_eq!(self.char(), '[');
+ let start = self.pos();
+ if !self.bump_and_bump_space() {
+ return Err(self.error(
+ Span::new(start, self.pos()),
+ ast::ErrorKind::ClassUnclosed,
+ ));
+ }
+
+ let negated = if self.char() != '^' {
+ false
+ } else {
+ if !self.bump_and_bump_space() {
+ return Err(self.error(
+ Span::new(start, self.pos()),
+ ast::ErrorKind::ClassUnclosed,
+ ));
+ }
+ true
+ };
+ // Accept any number of `-` as literal `-`.
+ let mut union =
+ ast::ClassSetUnion { span: self.span(), items: vec![] };
+ while self.char() == '-' {
+ union.push(ast::ClassSetItem::Literal(ast::Literal {
+ span: self.span_char(),
+ kind: ast::LiteralKind::Verbatim,
+ c: '-',
+ }));
+ if !self.bump_and_bump_space() {
+ return Err(self.error(
+ Span::new(start, self.pos()),
+ ast::ErrorKind::ClassUnclosed,
+ ));
+ }
+ }
+ // If `]` is the *first* char in a set, then interpret it as a literal
+ // `]`. That is, an empty class is impossible to write.
+ if union.items.is_empty() && self.char() == ']' {
+ union.push(ast::ClassSetItem::Literal(ast::Literal {
+ span: self.span_char(),
+ kind: ast::LiteralKind::Verbatim,
+ c: ']',
+ }));
+ if !self.bump_and_bump_space() {
+ return Err(self.error(
+ Span::new(start, self.pos()),
+ ast::ErrorKind::ClassUnclosed,
+ ));
+ }
+ }
+ let set = ast::ClassBracketed {
+ span: Span::new(start, self.pos()),
+ negated: negated,
+ kind: ast::ClassSet::union(ast::ClassSetUnion {
+ span: Span::new(union.span.start, union.span.start),
+ items: vec![],
+ }),
+ };
+ Ok((set, union))
+ }
+
+ /// Attempt to parse an ASCII character class, e.g., `[:alnum:]`.
+ ///
+ /// This assumes the parser is positioned at the opening `[`.
+ ///
+ /// If no valid ASCII character class could be found, then this does not
+ /// advance the parser and `None` is returned. Otherwise, the parser is
+ /// advanced to the first byte following the closing `]` and the
+ /// corresponding ASCII class is returned.
+ #[inline(never)]
+ fn maybe_parse_ascii_class(&self) -> Option<ast::ClassAscii> {
+ // ASCII character classes are interesting from a parsing perspective
+ // because parsing cannot fail with any interesting error. For example,
+ // in order to use an ASCII character class, it must be enclosed in
+ // double brackets, e.g., `[[:alnum:]]`. Alternatively, you might think
+ // of it as "ASCII character characters have the syntax `[:NAME:]`
+ // which can only appear within character brackets." This means that
+ // things like `[[:lower:]A]` are legal constructs.
+ //
+ // However, if one types an incorrect ASCII character class, e.g.,
+ // `[[:loower:]]`, then we treat that as a normal nested character
+ // class containing the characters `:elorw`. One might argue that we
+ // should return an error instead since the repeated colons give away
+ // the intent to write an ASCII class. But what if the user typed
+ // `[[:lower]]` instead? How can we tell that was intended to be an
+ // ASCII class and not just a normal nested class?
+ //
+ // Reasonable people can probably disagree over this, but for better
+ // or worse, we implement semantics that never fails at the expense
+ // of better failure modes.
+ assert_eq!(self.char(), '[');
+ // If parsing fails, then we back up the parser to this starting point.
+ let start = self.pos();
+ let mut negated = false;
+ if !self.bump() || self.char() != ':' {
+ self.parser().pos.set(start);
+ return None;
+ }
+ if !self.bump() {
+ self.parser().pos.set(start);
+ return None;
+ }
+ if self.char() == '^' {
+ negated = true;
+ if !self.bump() {
+ self.parser().pos.set(start);
+ return None;
+ }
+ }
+ let name_start = self.offset();
+ while self.char() != ':' && self.bump() {}
+ if self.is_eof() {
+ self.parser().pos.set(start);
+ return None;
+ }
+ let name = &self.pattern()[name_start..self.offset()];
+ if !self.bump_if(":]") {
+ self.parser().pos.set(start);
+ return None;
+ }
+ let kind = match ast::ClassAsciiKind::from_name(name) {
+ Some(kind) => kind,
+ None => {
+ self.parser().pos.set(start);
+ return None;
+ }
+ };
+ Some(ast::ClassAscii {
+ span: Span::new(start, self.pos()),
+ kind: kind,
+ negated: negated,
+ })
+ }
+
+ /// Parse a Unicode class in either the single character notation, `\pN`
+ /// or the multi-character bracketed notation, `\p{Greek}`. This assumes
+ /// the parser is positioned at the `p` (or `P` for negation) and will
+ /// advance the parser to the character immediately following the class.
+ ///
+ /// Note that this does not check whether the class name is valid or not.
+ #[inline(never)]
+ fn parse_unicode_class(&self) -> Result<ast::ClassUnicode> {
+ assert!(self.char() == 'p' || self.char() == 'P');
+
+ let mut scratch = self.parser().scratch.borrow_mut();
+ scratch.clear();
+
+ let negated = self.char() == 'P';
+ if !self.bump_and_bump_space() {
+ return Err(
+ self.error(self.span(), ast::ErrorKind::EscapeUnexpectedEof)
+ );
+ }
+ let (start, kind) = if self.char() == '{' {
+ let start = self.span_char().end;
+ while self.bump_and_bump_space() && self.char() != '}' {
+ scratch.push(self.char());
+ }
+ if self.is_eof() {
+ return Err(self
+ .error(self.span(), ast::ErrorKind::EscapeUnexpectedEof));
+ }
+ assert_eq!(self.char(), '}');
+ self.bump();
+
+ let name = scratch.as_str();
+ if let Some(i) = name.find("!=") {
+ (
+ start,
+ ast::ClassUnicodeKind::NamedValue {
+ op: ast::ClassUnicodeOpKind::NotEqual,
+ name: name[..i].to_string(),
+ value: name[i + 2..].to_string(),
+ },
+ )
+ } else if let Some(i) = name.find(':') {
+ (
+ start,
+ ast::ClassUnicodeKind::NamedValue {
+ op: ast::ClassUnicodeOpKind::Colon,
+ name: name[..i].to_string(),
+ value: name[i + 1..].to_string(),
+ },
+ )
+ } else if let Some(i) = name.find('=') {
+ (
+ start,
+ ast::ClassUnicodeKind::NamedValue {
+ op: ast::ClassUnicodeOpKind::Equal,
+ name: name[..i].to_string(),
+ value: name[i + 1..].to_string(),
+ },
+ )
+ } else {
+ (start, ast::ClassUnicodeKind::Named(name.to_string()))
+ }
+ } else {
+ let start = self.pos();
+ let c = self.char();
+ if c == '\\' {
+ return Err(self.error(
+ self.span_char(),
+ ast::ErrorKind::UnicodeClassInvalid,
+ ));
+ }
+ self.bump_and_bump_space();
+ let kind = ast::ClassUnicodeKind::OneLetter(c);
+ (start, kind)
+ };
+ Ok(ast::ClassUnicode {
+ span: Span::new(start, self.pos()),
+ negated: negated,
+ kind: kind,
+ })
+ }
+
+ /// Parse a Perl character class, e.g., `\d` or `\W`. This assumes the
+ /// parser is currently at a valid character class name and will be
+ /// advanced to the character immediately following the class.
+ #[inline(never)]
+ fn parse_perl_class(&self) -> ast::ClassPerl {
+ let c = self.char();
+ let span = self.span_char();
+ self.bump();
+ let (negated, kind) = match c {
+ 'd' => (false, ast::ClassPerlKind::Digit),
+ 'D' => (true, ast::ClassPerlKind::Digit),
+ 's' => (false, ast::ClassPerlKind::Space),
+ 'S' => (true, ast::ClassPerlKind::Space),
+ 'w' => (false, ast::ClassPerlKind::Word),
+ 'W' => (true, ast::ClassPerlKind::Word),
+ c => panic!("expected valid Perl class but got '{}'", c),
+ };
+ ast::ClassPerl { span: span, kind: kind, negated: negated }
+ }
+}
+
+/// A type that traverses a fully parsed Ast and checks whether its depth
+/// exceeds the specified nesting limit. If it does, then an error is returned.
+#[derive(Debug)]
+struct NestLimiter<'p, 's: 'p, P: 'p + 's> {
+ /// The parser that is checking the nest limit.
+ p: &'p ParserI<'s, P>,
+ /// The current depth while walking an Ast.
+ depth: u32,
+}
+
+impl<'p, 's, P: Borrow<Parser>> NestLimiter<'p, 's, P> {
+ fn new(p: &'p ParserI<'s, P>) -> NestLimiter<'p, 's, P> {
+ NestLimiter { p: p, depth: 0 }
+ }
+
+ #[inline(never)]
+ fn check(self, ast: &Ast) -> Result<()> {
+ ast::visit(ast, self)
+ }
+
+ fn increment_depth(&mut self, span: &Span) -> Result<()> {
+ let new = self.depth.checked_add(1).ok_or_else(|| {
+ self.p.error(
+ span.clone(),
+ ast::ErrorKind::NestLimitExceeded(::std::u32::MAX),
+ )
+ })?;
+ let limit = self.p.parser().nest_limit;
+ if new > limit {
+ return Err(self.p.error(
+ span.clone(),
+ ast::ErrorKind::NestLimitExceeded(limit),
+ ));
+ }
+ self.depth = new;
+ Ok(())
+ }
+
+ fn decrement_depth(&mut self) {
+ // Assuming the correctness of the visitor, this should never drop
+ // below 0.
+ self.depth = self.depth.checked_sub(1).unwrap();
+ }
+}
+
+impl<'p, 's, P: Borrow<Parser>> ast::Visitor for NestLimiter<'p, 's, P> {
+ type Output = ();
+ type Err = ast::Error;
+
+ fn finish(self) -> Result<()> {
+ Ok(())
+ }
+
+ fn visit_pre(&mut self, ast: &Ast) -> Result<()> {
+ let span = match *ast {
+ Ast::Empty(_)
+ | Ast::Flags(_)
+ | Ast::Literal(_)
+ | Ast::Dot(_)
+ | Ast::Assertion(_)
+ | Ast::Class(ast::Class::Unicode(_))
+ | Ast::Class(ast::Class::Perl(_)) => {
+ // These are all base cases, so we don't increment depth.
+ return Ok(());
+ }
+ Ast::Class(ast::Class::Bracketed(ref x)) => &x.span,
+ Ast::Repetition(ref x) => &x.span,
+ Ast::Group(ref x) => &x.span,
+ Ast::Alternation(ref x) => &x.span,
+ Ast::Concat(ref x) => &x.span,
+ };
+ self.increment_depth(span)
+ }
+
+ fn visit_post(&mut self, ast: &Ast) -> Result<()> {
+ match *ast {
+ Ast::Empty(_)
+ | Ast::Flags(_)
+ | Ast::Literal(_)
+ | Ast::Dot(_)
+ | Ast::Assertion(_)
+ | Ast::Class(ast::Class::Unicode(_))
+ | Ast::Class(ast::Class::Perl(_)) => {
+ // These are all base cases, so we don't decrement depth.
+ Ok(())
+ }
+ Ast::Class(ast::Class::Bracketed(_))
+ | Ast::Repetition(_)
+ | Ast::Group(_)
+ | Ast::Alternation(_)
+ | Ast::Concat(_) => {
+ self.decrement_depth();
+ Ok(())
+ }
+ }
+ }
+
+ fn visit_class_set_item_pre(
+ &mut self,
+ ast: &ast::ClassSetItem,
+ ) -> Result<()> {
+ let span = match *ast {
+ ast::ClassSetItem::Empty(_)
+ | ast::ClassSetItem::Literal(_)
+ | ast::ClassSetItem::Range(_)
+ | ast::ClassSetItem::Ascii(_)
+ | ast::ClassSetItem::Unicode(_)
+ | ast::ClassSetItem::Perl(_) => {
+ // These are all base cases, so we don't increment depth.
+ return Ok(());
+ }
+ ast::ClassSetItem::Bracketed(ref x) => &x.span,
+ ast::ClassSetItem::Union(ref x) => &x.span,
+ };
+ self.increment_depth(span)
+ }
+
+ fn visit_class_set_item_post(
+ &mut self,
+ ast: &ast::ClassSetItem,
+ ) -> Result<()> {
+ match *ast {
+ ast::ClassSetItem::Empty(_)
+ | ast::ClassSetItem::Literal(_)
+ | ast::ClassSetItem::Range(_)
+ | ast::ClassSetItem::Ascii(_)
+ | ast::ClassSetItem::Unicode(_)
+ | ast::ClassSetItem::Perl(_) => {
+ // These are all base cases, so we don't decrement depth.
+ Ok(())
+ }
+ ast::ClassSetItem::Bracketed(_) | ast::ClassSetItem::Union(_) => {
+ self.decrement_depth();
+ Ok(())
+ }
+ }
+ }
+
+ fn visit_class_set_binary_op_pre(
+ &mut self,
+ ast: &ast::ClassSetBinaryOp,
+ ) -> Result<()> {
+ self.increment_depth(&ast.span)
+ }
+
+ fn visit_class_set_binary_op_post(
+ &mut self,
+ _ast: &ast::ClassSetBinaryOp,
+ ) -> Result<()> {
+ self.decrement_depth();
+ Ok(())
+ }
+}
+
+/// When the result is an error, transforms the ast::ErrorKind from the source
+/// Result into another one. This function is used to return clearer error
+/// messages when possible.
+fn specialize_err<T>(
+ result: Result<T>,
+ from: ast::ErrorKind,
+ to: ast::ErrorKind,
+) -> Result<T> {
+ if let Err(e) = result {
+ if e.kind == from {
+ Err(ast::Error { kind: to, pattern: e.pattern, span: e.span })
+ } else {
+ Err(e)
+ }
+ } else {
+ result
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use std::ops::Range;
+
+ use super::{Parser, ParserBuilder, ParserI, Primitive};
+ use ast::{self, Ast, Position, Span};
+
+ // Our own assert_eq, which has slightly better formatting (but honestly
+ // still kind of crappy).
+ macro_rules! assert_eq {
+ ($left:expr, $right:expr) => {{
+ match (&$left, &$right) {
+ (left_val, right_val) => {
+ if !(*left_val == *right_val) {
+ panic!(
+ "assertion failed: `(left == right)`\n\n\
+ left: `{:?}`\nright: `{:?}`\n\n",
+ left_val, right_val
+ )
+ }
+ }
+ }
+ }};
+ }
+
+ // We create these errors to compare with real ast::Errors in the tests.
+ // We define equality between TestError and ast::Error to disregard the
+ // pattern string in ast::Error, which is annoying to provide in tests.
+ #[derive(Clone, Debug)]
+ struct TestError {
+ span: Span,
+ kind: ast::ErrorKind,
+ }
+
+ impl PartialEq<ast::Error> for TestError {
+ fn eq(&self, other: &ast::Error) -> bool {
+ self.span == other.span && self.kind == other.kind
+ }
+ }
+
+ impl PartialEq<TestError> for ast::Error {
+ fn eq(&self, other: &TestError) -> bool {
+ self.span == other.span && self.kind == other.kind
+ }
+ }
+
+ fn s(str: &str) -> String {
+ str.to_string()
+ }
+
+ fn parser(pattern: &str) -> ParserI<Parser> {
+ ParserI::new(Parser::new(), pattern)
+ }
+
+ fn parser_octal(pattern: &str) -> ParserI<Parser> {
+ let parser = ParserBuilder::new().octal(true).build();
+ ParserI::new(parser, pattern)
+ }
+
+ fn parser_nest_limit(pattern: &str, nest_limit: u32) -> ParserI<Parser> {
+ let p = ParserBuilder::new().nest_limit(nest_limit).build();
+ ParserI::new(p, pattern)
+ }
+
+ fn parser_ignore_whitespace(pattern: &str) -> ParserI<Parser> {
+ let p = ParserBuilder::new().ignore_whitespace(true).build();
+ ParserI::new(p, pattern)
+ }
+
+ /// Short alias for creating a new span.
+ fn nspan(start: Position, end: Position) -> Span {
+ Span::new(start, end)
+ }
+
+ /// Short alias for creating a new position.
+ fn npos(offset: usize, line: usize, column: usize) -> Position {
+ Position::new(offset, line, column)
+ }
+
+ /// Create a new span from the given offset range. This assumes a single
+ /// line and sets the columns based on the offsets. i.e., This only works
+ /// out of the box for ASCII, which is fine for most tests.
+ fn span(range: Range<usize>) -> Span {
+ let start = Position::new(range.start, 1, range.start + 1);
+ let end = Position::new(range.end, 1, range.end + 1);
+ Span::new(start, end)
+ }
+
+ /// Create a new span for the corresponding byte range in the given string.
+ fn span_range(subject: &str, range: Range<usize>) -> Span {
+ let start = Position {
+ offset: range.start,
+ line: 1 + subject[..range.start].matches('\n').count(),
+ column: 1 + subject[..range.start]
+ .chars()
+ .rev()
+ .position(|c| c == '\n')
+ .unwrap_or(subject[..range.start].chars().count()),
+ };
+ let end = Position {
+ offset: range.end,
+ line: 1 + subject[..range.end].matches('\n').count(),
+ column: 1 + subject[..range.end]
+ .chars()
+ .rev()
+ .position(|c| c == '\n')
+ .unwrap_or(subject[..range.end].chars().count()),
+ };
+ Span::new(start, end)
+ }
+
+ /// Create a verbatim literal starting at the given position.
+ fn lit(c: char, start: usize) -> Ast {
+ lit_with(c, span(start..start + c.len_utf8()))
+ }
+
+ /// Create a punctuation literal starting at the given position.
+ fn punct_lit(c: char, span: Span) -> Ast {
+ Ast::Literal(ast::Literal {
+ span: span,
+ kind: ast::LiteralKind::Punctuation,
+ c: c,
+ })
+ }
+
+ /// Create a verbatim literal with the given span.
+ fn lit_with(c: char, span: Span) -> Ast {
+ Ast::Literal(ast::Literal {
+ span: span,
+ kind: ast::LiteralKind::Verbatim,
+ c: c,
+ })
+ }
+
+ /// Create a concatenation with the given range.
+ fn concat(range: Range<usize>, asts: Vec<Ast>) -> Ast {
+ concat_with(span(range), asts)
+ }
+
+ /// Create a concatenation with the given span.
+ fn concat_with(span: Span, asts: Vec<Ast>) -> Ast {
+ Ast::Concat(ast::Concat { span: span, asts: asts })
+ }
+
+ /// Create an alternation with the given span.
+ fn alt(range: Range<usize>, asts: Vec<Ast>) -> Ast {
+ Ast::Alternation(ast::Alternation { span: span(range), asts: asts })
+ }
+
+ /// Create a capturing group with the given span.
+ fn group(range: Range<usize>, index: u32, ast: Ast) -> Ast {
+ Ast::Group(ast::Group {
+ span: span(range),
+ kind: ast::GroupKind::CaptureIndex(index),
+ ast: Box::new(ast),
+ })
+ }
+
+ /// Create an ast::SetFlags.
+ ///
+ /// The given pattern should be the full pattern string. The range given
+ /// should correspond to the byte offsets where the flag set occurs.
+ ///
+ /// If negated is true, then the set is interpreted as beginning with a
+ /// negation.
+ fn flag_set(
+ pat: &str,
+ range: Range<usize>,
+ flag: ast::Flag,
+ negated: bool,
+ ) -> Ast {
+ let mut items = vec![ast::FlagsItem {
+ span: span_range(pat, (range.end - 2)..(range.end - 1)),
+ kind: ast::FlagsItemKind::Flag(flag),
+ }];
+ if negated {
+ items.insert(
+ 0,
+ ast::FlagsItem {
+ span: span_range(pat, (range.start + 2)..(range.end - 2)),
+ kind: ast::FlagsItemKind::Negation,
+ },
+ );
+ }
+ Ast::Flags(ast::SetFlags {
+ span: span_range(pat, range.clone()),
+ flags: ast::Flags {
+ span: span_range(pat, (range.start + 2)..(range.end - 1)),
+ items: items,
+ },
+ })
+ }
+
+ #[test]
+ fn parse_nest_limit() {
+ // A nest limit of 0 still allows some types of regexes.
+ assert_eq!(
+ parser_nest_limit("", 0).parse(),
+ Ok(Ast::Empty(span(0..0)))
+ );
+ assert_eq!(parser_nest_limit("a", 0).parse(), Ok(lit('a', 0)));
+
+ // Test repetition operations, which require one level of nesting.
+ assert_eq!(
+ parser_nest_limit("a+", 0).parse().unwrap_err(),
+ TestError {
+ span: span(0..2),
+ kind: ast::ErrorKind::NestLimitExceeded(0),
+ }
+ );
+ assert_eq!(
+ parser_nest_limit("a+", 1).parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..2),
+ op: ast::RepetitionOp {
+ span: span(1..2),
+ kind: ast::RepetitionKind::OneOrMore,
+ },
+ greedy: true,
+ ast: Box::new(lit('a', 0)),
+ }))
+ );
+ assert_eq!(
+ parser_nest_limit("(a)+", 1).parse().unwrap_err(),
+ TestError {
+ span: span(0..3),
+ kind: ast::ErrorKind::NestLimitExceeded(1),
+ }
+ );
+ assert_eq!(
+ parser_nest_limit("a+*", 1).parse().unwrap_err(),
+ TestError {
+ span: span(0..2),
+ kind: ast::ErrorKind::NestLimitExceeded(1),
+ }
+ );
+ assert_eq!(
+ parser_nest_limit("a+*", 2).parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..3),
+ op: ast::RepetitionOp {
+ span: span(2..3),
+ kind: ast::RepetitionKind::ZeroOrMore,
+ },
+ greedy: true,
+ ast: Box::new(Ast::Repetition(ast::Repetition {
+ span: span(0..2),
+ op: ast::RepetitionOp {
+ span: span(1..2),
+ kind: ast::RepetitionKind::OneOrMore,
+ },
+ greedy: true,
+ ast: Box::new(lit('a', 0)),
+ })),
+ }))
+ );
+
+ // Test concatenations. A concatenation requires one level of nesting.
+ assert_eq!(
+ parser_nest_limit("ab", 0).parse().unwrap_err(),
+ TestError {
+ span: span(0..2),
+ kind: ast::ErrorKind::NestLimitExceeded(0),
+ }
+ );
+ assert_eq!(
+ parser_nest_limit("ab", 1).parse(),
+ Ok(concat(0..2, vec![lit('a', 0), lit('b', 1)]))
+ );
+ assert_eq!(
+ parser_nest_limit("abc", 1).parse(),
+ Ok(concat(0..3, vec![lit('a', 0), lit('b', 1), lit('c', 2)]))
+ );
+
+ // Test alternations. An alternation requires one level of nesting.
+ assert_eq!(
+ parser_nest_limit("a|b", 0).parse().unwrap_err(),
+ TestError {
+ span: span(0..3),
+ kind: ast::ErrorKind::NestLimitExceeded(0),
+ }
+ );
+ assert_eq!(
+ parser_nest_limit("a|b", 1).parse(),
+ Ok(alt(0..3, vec![lit('a', 0), lit('b', 2)]))
+ );
+ assert_eq!(
+ parser_nest_limit("a|b|c", 1).parse(),
+ Ok(alt(0..5, vec![lit('a', 0), lit('b', 2), lit('c', 4)]))
+ );
+
+ // Test character classes. Classes form their own mini-recursive
+ // syntax!
+ assert_eq!(
+ parser_nest_limit("[a]", 0).parse().unwrap_err(),
+ TestError {
+ span: span(0..3),
+ kind: ast::ErrorKind::NestLimitExceeded(0),
+ }
+ );
+ assert_eq!(
+ parser_nest_limit("[a]", 1).parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..3),
+ negated: false,
+ kind: ast::ClassSet::Item(ast::ClassSetItem::Literal(
+ ast::Literal {
+ span: span(1..2),
+ kind: ast::LiteralKind::Verbatim,
+ c: 'a',
+ }
+ )),
+ })))
+ );
+ assert_eq!(
+ parser_nest_limit("[ab]", 1).parse().unwrap_err(),
+ TestError {
+ span: span(1..3),
+ kind: ast::ErrorKind::NestLimitExceeded(1),
+ }
+ );
+ assert_eq!(
+ parser_nest_limit("[ab[cd]]", 2).parse().unwrap_err(),
+ TestError {
+ span: span(3..7),
+ kind: ast::ErrorKind::NestLimitExceeded(2),
+ }
+ );
+ assert_eq!(
+ parser_nest_limit("[ab[cd]]", 3).parse().unwrap_err(),
+ TestError {
+ span: span(4..6),
+ kind: ast::ErrorKind::NestLimitExceeded(3),
+ }
+ );
+ assert_eq!(
+ parser_nest_limit("[a--b]", 1).parse().unwrap_err(),
+ TestError {
+ span: span(1..5),
+ kind: ast::ErrorKind::NestLimitExceeded(1),
+ }
+ );
+ assert_eq!(
+ parser_nest_limit("[a--bc]", 2).parse().unwrap_err(),
+ TestError {
+ span: span(4..6),
+ kind: ast::ErrorKind::NestLimitExceeded(2),
+ }
+ );
+ }
+
+ #[test]
+ fn parse_comments() {
+ let pat = "(?x)
+# This is comment 1.
+foo # This is comment 2.
+ # This is comment 3.
+bar
+# This is comment 4.";
+ let astc = parser(pat).parse_with_comments().unwrap();
+ assert_eq!(
+ astc.ast,
+ concat_with(
+ span_range(pat, 0..pat.len()),
+ vec![
+ flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
+ lit_with('f', span_range(pat, 26..27)),
+ lit_with('o', span_range(pat, 27..28)),
+ lit_with('o', span_range(pat, 28..29)),
+ lit_with('b', span_range(pat, 74..75)),
+ lit_with('a', span_range(pat, 75..76)),
+ lit_with('r', span_range(pat, 76..77)),
+ ]
+ )
+ );
+ assert_eq!(
+ astc.comments,
+ vec![
+ ast::Comment {
+ span: span_range(pat, 5..26),
+ comment: s(" This is comment 1."),
+ },
+ ast::Comment {
+ span: span_range(pat, 30..51),
+ comment: s(" This is comment 2."),
+ },
+ ast::Comment {
+ span: span_range(pat, 53..74),
+ comment: s(" This is comment 3."),
+ },
+ ast::Comment {
+ span: span_range(pat, 78..98),
+ comment: s(" This is comment 4."),
+ },
+ ]
+ );
+ }
+
+ #[test]
+ fn parse_holistic() {
+ assert_eq!(parser("]").parse(), Ok(lit(']', 0)));
+ assert_eq!(
+ parser(r"\\\.\+\*\?\(\)\|\[\]\{\}\^\$\#\&\-\~").parse(),
+ Ok(concat(
+ 0..36,
+ vec![
+ punct_lit('\\', span(0..2)),
+ punct_lit('.', span(2..4)),
+ punct_lit('+', span(4..6)),
+ punct_lit('*', span(6..8)),
+ punct_lit('?', span(8..10)),
+ punct_lit('(', span(10..12)),
+ punct_lit(')', span(12..14)),
+ punct_lit('|', span(14..16)),
+ punct_lit('[', span(16..18)),
+ punct_lit(']', span(18..20)),
+ punct_lit('{', span(20..22)),
+ punct_lit('}', span(22..24)),
+ punct_lit('^', span(24..26)),
+ punct_lit('$', span(26..28)),
+ punct_lit('#', span(28..30)),
+ punct_lit('&', span(30..32)),
+ punct_lit('-', span(32..34)),
+ punct_lit('~', span(34..36)),
+ ]
+ ))
+ );
+ }
+
+ #[test]
+ fn parse_ignore_whitespace() {
+ // Test that basic whitespace insensitivity works.
+ let pat = "(?x)a b";
+ assert_eq!(
+ parser(pat).parse(),
+ Ok(concat_with(
+ nspan(npos(0, 1, 1), npos(7, 1, 8)),
+ vec![
+ flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
+ lit_with('a', nspan(npos(4, 1, 5), npos(5, 1, 6))),
+ lit_with('b', nspan(npos(6, 1, 7), npos(7, 1, 8))),
+ ]
+ ))
+ );
+
+ // Test that we can toggle whitespace insensitivity.
+ let pat = "(?x)a b(?-x)a b";
+ assert_eq!(
+ parser(pat).parse(),
+ Ok(concat_with(
+ nspan(npos(0, 1, 1), npos(15, 1, 16)),
+ vec![
+ flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
+ lit_with('a', nspan(npos(4, 1, 5), npos(5, 1, 6))),
+ lit_with('b', nspan(npos(6, 1, 7), npos(7, 1, 8))),
+ flag_set(pat, 7..12, ast::Flag::IgnoreWhitespace, true),
+ lit_with('a', nspan(npos(12, 1, 13), npos(13, 1, 14))),
+ lit_with(' ', nspan(npos(13, 1, 14), npos(14, 1, 15))),
+ lit_with('b', nspan(npos(14, 1, 15), npos(15, 1, 16))),
+ ]
+ ))
+ );
+
+ // Test that nesting whitespace insensitive flags works.
+ let pat = "a (?x:a )a ";
+ assert_eq!(
+ parser(pat).parse(),
+ Ok(concat_with(
+ span_range(pat, 0..11),
+ vec![
+ lit_with('a', span_range(pat, 0..1)),
+ lit_with(' ', span_range(pat, 1..2)),
+ Ast::Group(ast::Group {
+ span: span_range(pat, 2..9),
+ kind: ast::GroupKind::NonCapturing(ast::Flags {
+ span: span_range(pat, 4..5),
+ items: vec![ast::FlagsItem {
+ span: span_range(pat, 4..5),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::IgnoreWhitespace
+ ),
+ },],
+ }),
+ ast: Box::new(lit_with('a', span_range(pat, 6..7))),
+ }),
+ lit_with('a', span_range(pat, 9..10)),
+ lit_with(' ', span_range(pat, 10..11)),
+ ]
+ ))
+ );
+
+ // Test that whitespace after an opening paren is insignificant.
+ let pat = "(?x)( ?P<foo> a )";
+ assert_eq!(
+ parser(pat).parse(),
+ Ok(concat_with(
+ span_range(pat, 0..pat.len()),
+ vec![
+ flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
+ Ast::Group(ast::Group {
+ span: span_range(pat, 4..pat.len()),
+ kind: ast::GroupKind::CaptureName(ast::CaptureName {
+ span: span_range(pat, 9..12),
+ name: s("foo"),
+ index: 1,
+ }),
+ ast: Box::new(lit_with('a', span_range(pat, 14..15))),
+ }),
+ ]
+ ))
+ );
+ let pat = "(?x)( a )";
+ assert_eq!(
+ parser(pat).parse(),
+ Ok(concat_with(
+ span_range(pat, 0..pat.len()),
+ vec![
+ flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
+ Ast::Group(ast::Group {
+ span: span_range(pat, 4..pat.len()),
+ kind: ast::GroupKind::CaptureIndex(1),
+ ast: Box::new(lit_with('a', span_range(pat, 7..8))),
+ }),
+ ]
+ ))
+ );
+ let pat = "(?x)( ?: a )";
+ assert_eq!(
+ parser(pat).parse(),
+ Ok(concat_with(
+ span_range(pat, 0..pat.len()),
+ vec![
+ flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
+ Ast::Group(ast::Group {
+ span: span_range(pat, 4..pat.len()),
+ kind: ast::GroupKind::NonCapturing(ast::Flags {
+ span: span_range(pat, 8..8),
+ items: vec![],
+ }),
+ ast: Box::new(lit_with('a', span_range(pat, 11..12))),
+ }),
+ ]
+ ))
+ );
+ let pat = r"(?x)\x { 53 }";
+ assert_eq!(
+ parser(pat).parse(),
+ Ok(concat_with(
+ span_range(pat, 0..pat.len()),
+ vec![
+ flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
+ Ast::Literal(ast::Literal {
+ span: span(4..13),
+ kind: ast::LiteralKind::HexBrace(
+ ast::HexLiteralKind::X
+ ),
+ c: 'S',
+ }),
+ ]
+ ))
+ );
+
+ // Test that whitespace after an escape is OK.
+ let pat = r"(?x)\ ";
+ assert_eq!(
+ parser(pat).parse(),
+ Ok(concat_with(
+ span_range(pat, 0..pat.len()),
+ vec![
+ flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
+ Ast::Literal(ast::Literal {
+ span: span_range(pat, 4..6),
+ kind: ast::LiteralKind::Special(
+ ast::SpecialLiteralKind::Space
+ ),
+ c: ' ',
+ }),
+ ]
+ ))
+ );
+ // ... but only when `x` mode is enabled.
+ let pat = r"\ ";
+ assert_eq!(
+ parser(pat).parse().unwrap_err(),
+ TestError {
+ span: span_range(pat, 0..2),
+ kind: ast::ErrorKind::EscapeUnrecognized,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_newlines() {
+ let pat = ".\n.";
+ assert_eq!(
+ parser(pat).parse(),
+ Ok(concat_with(
+ span_range(pat, 0..3),
+ vec![
+ Ast::Dot(span_range(pat, 0..1)),
+ lit_with('\n', span_range(pat, 1..2)),
+ Ast::Dot(span_range(pat, 2..3)),
+ ]
+ ))
+ );
+
+ let pat = "foobar\nbaz\nquux\n";
+ assert_eq!(
+ parser(pat).parse(),
+ Ok(concat_with(
+ span_range(pat, 0..pat.len()),
+ vec![
+ lit_with('f', nspan(npos(0, 1, 1), npos(1, 1, 2))),
+ lit_with('o', nspan(npos(1, 1, 2), npos(2, 1, 3))),
+ lit_with('o', nspan(npos(2, 1, 3), npos(3, 1, 4))),
+ lit_with('b', nspan(npos(3, 1, 4), npos(4, 1, 5))),
+ lit_with('a', nspan(npos(4, 1, 5), npos(5, 1, 6))),
+ lit_with('r', nspan(npos(5, 1, 6), npos(6, 1, 7))),
+ lit_with('\n', nspan(npos(6, 1, 7), npos(7, 2, 1))),
+ lit_with('b', nspan(npos(7, 2, 1), npos(8, 2, 2))),
+ lit_with('a', nspan(npos(8, 2, 2), npos(9, 2, 3))),
+ lit_with('z', nspan(npos(9, 2, 3), npos(10, 2, 4))),
+ lit_with('\n', nspan(npos(10, 2, 4), npos(11, 3, 1))),
+ lit_with('q', nspan(npos(11, 3, 1), npos(12, 3, 2))),
+ lit_with('u', nspan(npos(12, 3, 2), npos(13, 3, 3))),
+ lit_with('u', nspan(npos(13, 3, 3), npos(14, 3, 4))),
+ lit_with('x', nspan(npos(14, 3, 4), npos(15, 3, 5))),
+ lit_with('\n', nspan(npos(15, 3, 5), npos(16, 4, 1))),
+ ]
+ ))
+ );
+ }
+
+ #[test]
+ fn parse_uncounted_repetition() {
+ assert_eq!(
+ parser(r"a*").parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..2),
+ op: ast::RepetitionOp {
+ span: span(1..2),
+ kind: ast::RepetitionKind::ZeroOrMore,
+ },
+ greedy: true,
+ ast: Box::new(lit('a', 0)),
+ }))
+ );
+ assert_eq!(
+ parser(r"a+").parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..2),
+ op: ast::RepetitionOp {
+ span: span(1..2),
+ kind: ast::RepetitionKind::OneOrMore,
+ },
+ greedy: true,
+ ast: Box::new(lit('a', 0)),
+ }))
+ );
+
+ assert_eq!(
+ parser(r"a?").parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..2),
+ op: ast::RepetitionOp {
+ span: span(1..2),
+ kind: ast::RepetitionKind::ZeroOrOne,
+ },
+ greedy: true,
+ ast: Box::new(lit('a', 0)),
+ }))
+ );
+ assert_eq!(
+ parser(r"a??").parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..3),
+ op: ast::RepetitionOp {
+ span: span(1..3),
+ kind: ast::RepetitionKind::ZeroOrOne,
+ },
+ greedy: false,
+ ast: Box::new(lit('a', 0)),
+ }))
+ );
+ assert_eq!(
+ parser(r"a?").parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..2),
+ op: ast::RepetitionOp {
+ span: span(1..2),
+ kind: ast::RepetitionKind::ZeroOrOne,
+ },
+ greedy: true,
+ ast: Box::new(lit('a', 0)),
+ }))
+ );
+ assert_eq!(
+ parser(r"a?b").parse(),
+ Ok(concat(
+ 0..3,
+ vec![
+ Ast::Repetition(ast::Repetition {
+ span: span(0..2),
+ op: ast::RepetitionOp {
+ span: span(1..2),
+ kind: ast::RepetitionKind::ZeroOrOne,
+ },
+ greedy: true,
+ ast: Box::new(lit('a', 0)),
+ }),
+ lit('b', 2),
+ ]
+ ))
+ );
+ assert_eq!(
+ parser(r"a??b").parse(),
+ Ok(concat(
+ 0..4,
+ vec![
+ Ast::Repetition(ast::Repetition {
+ span: span(0..3),
+ op: ast::RepetitionOp {
+ span: span(1..3),
+ kind: ast::RepetitionKind::ZeroOrOne,
+ },
+ greedy: false,
+ ast: Box::new(lit('a', 0)),
+ }),
+ lit('b', 3),
+ ]
+ ))
+ );
+ assert_eq!(
+ parser(r"ab?").parse(),
+ Ok(concat(
+ 0..3,
+ vec![
+ lit('a', 0),
+ Ast::Repetition(ast::Repetition {
+ span: span(1..3),
+ op: ast::RepetitionOp {
+ span: span(2..3),
+ kind: ast::RepetitionKind::ZeroOrOne,
+ },
+ greedy: true,
+ ast: Box::new(lit('b', 1)),
+ }),
+ ]
+ ))
+ );
+ assert_eq!(
+ parser(r"(ab)?").parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..5),
+ op: ast::RepetitionOp {
+ span: span(4..5),
+ kind: ast::RepetitionKind::ZeroOrOne,
+ },
+ greedy: true,
+ ast: Box::new(group(
+ 0..4,
+ 1,
+ concat(1..3, vec![lit('a', 1), lit('b', 2),])
+ )),
+ }))
+ );
+ assert_eq!(
+ parser(r"|a?").parse(),
+ Ok(alt(
+ 0..3,
+ vec![
+ Ast::Empty(span(0..0)),
+ Ast::Repetition(ast::Repetition {
+ span: span(1..3),
+ op: ast::RepetitionOp {
+ span: span(2..3),
+ kind: ast::RepetitionKind::ZeroOrOne,
+ },
+ greedy: true,
+ ast: Box::new(lit('a', 1)),
+ }),
+ ]
+ ))
+ );
+
+ assert_eq!(
+ parser(r"*").parse().unwrap_err(),
+ TestError {
+ span: span(0..0),
+ kind: ast::ErrorKind::RepetitionMissing,
+ }
+ );
+ assert_eq!(
+ parser(r"(?i)*").parse().unwrap_err(),
+ TestError {
+ span: span(4..4),
+ kind: ast::ErrorKind::RepetitionMissing,
+ }
+ );
+ assert_eq!(
+ parser(r"(*)").parse().unwrap_err(),
+ TestError {
+ span: span(1..1),
+ kind: ast::ErrorKind::RepetitionMissing,
+ }
+ );
+ assert_eq!(
+ parser(r"(?:?)").parse().unwrap_err(),
+ TestError {
+ span: span(3..3),
+ kind: ast::ErrorKind::RepetitionMissing,
+ }
+ );
+ assert_eq!(
+ parser(r"+").parse().unwrap_err(),
+ TestError {
+ span: span(0..0),
+ kind: ast::ErrorKind::RepetitionMissing,
+ }
+ );
+ assert_eq!(
+ parser(r"?").parse().unwrap_err(),
+ TestError {
+ span: span(0..0),
+ kind: ast::ErrorKind::RepetitionMissing,
+ }
+ );
+ assert_eq!(
+ parser(r"(?)").parse().unwrap_err(),
+ TestError {
+ span: span(1..1),
+ kind: ast::ErrorKind::RepetitionMissing,
+ }
+ );
+ assert_eq!(
+ parser(r"|*").parse().unwrap_err(),
+ TestError {
+ span: span(1..1),
+ kind: ast::ErrorKind::RepetitionMissing,
+ }
+ );
+ assert_eq!(
+ parser(r"|+").parse().unwrap_err(),
+ TestError {
+ span: span(1..1),
+ kind: ast::ErrorKind::RepetitionMissing,
+ }
+ );
+ assert_eq!(
+ parser(r"|?").parse().unwrap_err(),
+ TestError {
+ span: span(1..1),
+ kind: ast::ErrorKind::RepetitionMissing,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_counted_repetition() {
+ assert_eq!(
+ parser(r"a{5}").parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..4),
+ op: ast::RepetitionOp {
+ span: span(1..4),
+ kind: ast::RepetitionKind::Range(
+ ast::RepetitionRange::Exactly(5)
+ ),
+ },
+ greedy: true,
+ ast: Box::new(lit('a', 0)),
+ }))
+ );
+ assert_eq!(
+ parser(r"a{5,}").parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..5),
+ op: ast::RepetitionOp {
+ span: span(1..5),
+ kind: ast::RepetitionKind::Range(
+ ast::RepetitionRange::AtLeast(5)
+ ),
+ },
+ greedy: true,
+ ast: Box::new(lit('a', 0)),
+ }))
+ );
+ assert_eq!(
+ parser(r"a{5,9}").parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..6),
+ op: ast::RepetitionOp {
+ span: span(1..6),
+ kind: ast::RepetitionKind::Range(
+ ast::RepetitionRange::Bounded(5, 9)
+ ),
+ },
+ greedy: true,
+ ast: Box::new(lit('a', 0)),
+ }))
+ );
+ assert_eq!(
+ parser(r"a{5}?").parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..5),
+ op: ast::RepetitionOp {
+ span: span(1..5),
+ kind: ast::RepetitionKind::Range(
+ ast::RepetitionRange::Exactly(5)
+ ),
+ },
+ greedy: false,
+ ast: Box::new(lit('a', 0)),
+ }))
+ );
+ assert_eq!(
+ parser(r"ab{5}").parse(),
+ Ok(concat(
+ 0..5,
+ vec![
+ lit('a', 0),
+ Ast::Repetition(ast::Repetition {
+ span: span(1..5),
+ op: ast::RepetitionOp {
+ span: span(2..5),
+ kind: ast::RepetitionKind::Range(
+ ast::RepetitionRange::Exactly(5)
+ ),
+ },
+ greedy: true,
+ ast: Box::new(lit('b', 1)),
+ }),
+ ]
+ ))
+ );
+ assert_eq!(
+ parser(r"ab{5}c").parse(),
+ Ok(concat(
+ 0..6,
+ vec![
+ lit('a', 0),
+ Ast::Repetition(ast::Repetition {
+ span: span(1..5),
+ op: ast::RepetitionOp {
+ span: span(2..5),
+ kind: ast::RepetitionKind::Range(
+ ast::RepetitionRange::Exactly(5)
+ ),
+ },
+ greedy: true,
+ ast: Box::new(lit('b', 1)),
+ }),
+ lit('c', 5),
+ ]
+ ))
+ );
+
+ assert_eq!(
+ parser(r"a{ 5 }").parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..6),
+ op: ast::RepetitionOp {
+ span: span(1..6),
+ kind: ast::RepetitionKind::Range(
+ ast::RepetitionRange::Exactly(5)
+ ),
+ },
+ greedy: true,
+ ast: Box::new(lit('a', 0)),
+ }))
+ );
+ assert_eq!(
+ parser(r"a{ 5 , 9 }").parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..10),
+ op: ast::RepetitionOp {
+ span: span(1..10),
+ kind: ast::RepetitionKind::Range(
+ ast::RepetitionRange::Bounded(5, 9)
+ ),
+ },
+ greedy: true,
+ ast: Box::new(lit('a', 0)),
+ }))
+ );
+ assert_eq!(
+ parser_ignore_whitespace(r"a{5,9} ?").parse(),
+ Ok(Ast::Repetition(ast::Repetition {
+ span: span(0..8),
+ op: ast::RepetitionOp {
+ span: span(1..8),
+ kind: ast::RepetitionKind::Range(
+ ast::RepetitionRange::Bounded(5, 9)
+ ),
+ },
+ greedy: false,
+ ast: Box::new(lit('a', 0)),
+ }))
+ );
+
+ assert_eq!(
+ parser(r"(?i){0}").parse().unwrap_err(),
+ TestError {
+ span: span(4..4),
+ kind: ast::ErrorKind::RepetitionMissing,
+ }
+ );
+ assert_eq!(
+ parser(r"(?m){1,1}").parse().unwrap_err(),
+ TestError {
+ span: span(4..4),
+ kind: ast::ErrorKind::RepetitionMissing,
+ }
+ );
+ assert_eq!(
+ parser(r"a{]}").parse().unwrap_err(),
+ TestError {
+ span: span(2..2),
+ kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
+ }
+ );
+ assert_eq!(
+ parser(r"a{1,]}").parse().unwrap_err(),
+ TestError {
+ span: span(4..4),
+ kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
+ }
+ );
+ assert_eq!(
+ parser(r"a{").parse().unwrap_err(),
+ TestError {
+ span: span(1..2),
+ kind: ast::ErrorKind::RepetitionCountUnclosed,
+ }
+ );
+ assert_eq!(
+ parser(r"a{}").parse().unwrap_err(),
+ TestError {
+ span: span(2..2),
+ kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
+ }
+ );
+ assert_eq!(
+ parser(r"a{a").parse().unwrap_err(),
+ TestError {
+ span: span(2..2),
+ kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
+ }
+ );
+ assert_eq!(
+ parser(r"a{9999999999}").parse().unwrap_err(),
+ TestError {
+ span: span(2..12),
+ kind: ast::ErrorKind::DecimalInvalid,
+ }
+ );
+ assert_eq!(
+ parser(r"a{9").parse().unwrap_err(),
+ TestError {
+ span: span(1..3),
+ kind: ast::ErrorKind::RepetitionCountUnclosed,
+ }
+ );
+ assert_eq!(
+ parser(r"a{9,a").parse().unwrap_err(),
+ TestError {
+ span: span(4..4),
+ kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
+ }
+ );
+ assert_eq!(
+ parser(r"a{9,9999999999}").parse().unwrap_err(),
+ TestError {
+ span: span(4..14),
+ kind: ast::ErrorKind::DecimalInvalid,
+ }
+ );
+ assert_eq!(
+ parser(r"a{9,").parse().unwrap_err(),
+ TestError {
+ span: span(1..4),
+ kind: ast::ErrorKind::RepetitionCountUnclosed,
+ }
+ );
+ assert_eq!(
+ parser(r"a{9,11").parse().unwrap_err(),
+ TestError {
+ span: span(1..6),
+ kind: ast::ErrorKind::RepetitionCountUnclosed,
+ }
+ );
+ assert_eq!(
+ parser(r"a{2,1}").parse().unwrap_err(),
+ TestError {
+ span: span(1..6),
+ kind: ast::ErrorKind::RepetitionCountInvalid,
+ }
+ );
+ assert_eq!(
+ parser(r"{5}").parse().unwrap_err(),
+ TestError {
+ span: span(0..0),
+ kind: ast::ErrorKind::RepetitionMissing,
+ }
+ );
+ assert_eq!(
+ parser(r"|{5}").parse().unwrap_err(),
+ TestError {
+ span: span(1..1),
+ kind: ast::ErrorKind::RepetitionMissing,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_alternate() {
+ assert_eq!(
+ parser(r"a|b").parse(),
+ Ok(Ast::Alternation(ast::Alternation {
+ span: span(0..3),
+ asts: vec![lit('a', 0), lit('b', 2)],
+ }))
+ );
+ assert_eq!(
+ parser(r"(a|b)").parse(),
+ Ok(group(
+ 0..5,
+ 1,
+ Ast::Alternation(ast::Alternation {
+ span: span(1..4),
+ asts: vec![lit('a', 1), lit('b', 3)],
+ })
+ ))
+ );
+
+ assert_eq!(
+ parser(r"a|b|c").parse(),
+ Ok(Ast::Alternation(ast::Alternation {
+ span: span(0..5),
+ asts: vec![lit('a', 0), lit('b', 2), lit('c', 4)],
+ }))
+ );
+ assert_eq!(
+ parser(r"ax|by|cz").parse(),
+ Ok(Ast::Alternation(ast::Alternation {
+ span: span(0..8),
+ asts: vec![
+ concat(0..2, vec![lit('a', 0), lit('x', 1)]),
+ concat(3..5, vec![lit('b', 3), lit('y', 4)]),
+ concat(6..8, vec![lit('c', 6), lit('z', 7)]),
+ ],
+ }))
+ );
+ assert_eq!(
+ parser(r"(ax|by|cz)").parse(),
+ Ok(group(
+ 0..10,
+ 1,
+ Ast::Alternation(ast::Alternation {
+ span: span(1..9),
+ asts: vec![
+ concat(1..3, vec![lit('a', 1), lit('x', 2)]),
+ concat(4..6, vec![lit('b', 4), lit('y', 5)]),
+ concat(7..9, vec![lit('c', 7), lit('z', 8)]),
+ ],
+ })
+ ))
+ );
+ assert_eq!(
+ parser(r"(ax|(by|(cz)))").parse(),
+ Ok(group(
+ 0..14,
+ 1,
+ alt(
+ 1..13,
+ vec![
+ concat(1..3, vec![lit('a', 1), lit('x', 2)]),
+ group(
+ 4..13,
+ 2,
+ alt(
+ 5..12,
+ vec![
+ concat(
+ 5..7,
+ vec![lit('b', 5), lit('y', 6)]
+ ),
+ group(
+ 8..12,
+ 3,
+ concat(
+ 9..11,
+ vec![lit('c', 9), lit('z', 10),]
+ )
+ ),
+ ]
+ )
+ ),
+ ]
+ )
+ ))
+ );
+
+ assert_eq!(
+ parser(r"|").parse(),
+ Ok(alt(
+ 0..1,
+ vec![Ast::Empty(span(0..0)), Ast::Empty(span(1..1)),]
+ ))
+ );
+ assert_eq!(
+ parser(r"||").parse(),
+ Ok(alt(
+ 0..2,
+ vec![
+ Ast::Empty(span(0..0)),
+ Ast::Empty(span(1..1)),
+ Ast::Empty(span(2..2)),
+ ]
+ ))
+ );
+ assert_eq!(
+ parser(r"a|").parse(),
+ Ok(alt(0..2, vec![lit('a', 0), Ast::Empty(span(2..2)),]))
+ );
+ assert_eq!(
+ parser(r"|a").parse(),
+ Ok(alt(0..2, vec![Ast::Empty(span(0..0)), lit('a', 1),]))
+ );
+
+ assert_eq!(
+ parser(r"(|)").parse(),
+ Ok(group(
+ 0..3,
+ 1,
+ alt(
+ 1..2,
+ vec![Ast::Empty(span(1..1)), Ast::Empty(span(2..2)),]
+ )
+ ))
+ );
+ assert_eq!(
+ parser(r"(a|)").parse(),
+ Ok(group(
+ 0..4,
+ 1,
+ alt(1..3, vec![lit('a', 1), Ast::Empty(span(3..3)),])
+ ))
+ );
+ assert_eq!(
+ parser(r"(|a)").parse(),
+ Ok(group(
+ 0..4,
+ 1,
+ alt(1..3, vec![Ast::Empty(span(1..1)), lit('a', 2),])
+ ))
+ );
+
+ assert_eq!(
+ parser(r"a|b)").parse().unwrap_err(),
+ TestError {
+ span: span(3..4),
+ kind: ast::ErrorKind::GroupUnopened,
+ }
+ );
+ assert_eq!(
+ parser(r"(a|b").parse().unwrap_err(),
+ TestError {
+ span: span(0..1),
+ kind: ast::ErrorKind::GroupUnclosed,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_unsupported_lookaround() {
+ assert_eq!(
+ parser(r"(?=a)").parse().unwrap_err(),
+ TestError {
+ span: span(0..3),
+ kind: ast::ErrorKind::UnsupportedLookAround,
+ }
+ );
+ assert_eq!(
+ parser(r"(?!a)").parse().unwrap_err(),
+ TestError {
+ span: span(0..3),
+ kind: ast::ErrorKind::UnsupportedLookAround,
+ }
+ );
+ assert_eq!(
+ parser(r"(?<=a)").parse().unwrap_err(),
+ TestError {
+ span: span(0..4),
+ kind: ast::ErrorKind::UnsupportedLookAround,
+ }
+ );
+ assert_eq!(
+ parser(r"(?<!a)").parse().unwrap_err(),
+ TestError {
+ span: span(0..4),
+ kind: ast::ErrorKind::UnsupportedLookAround,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_group() {
+ assert_eq!(
+ parser("(?i)").parse(),
+ Ok(Ast::Flags(ast::SetFlags {
+ span: span(0..4),
+ flags: ast::Flags {
+ span: span(2..3),
+ items: vec![ast::FlagsItem {
+ span: span(2..3),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::CaseInsensitive
+ ),
+ }],
+ },
+ }))
+ );
+ assert_eq!(
+ parser("(?iU)").parse(),
+ Ok(Ast::Flags(ast::SetFlags {
+ span: span(0..5),
+ flags: ast::Flags {
+ span: span(2..4),
+ items: vec![
+ ast::FlagsItem {
+ span: span(2..3),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::CaseInsensitive
+ ),
+ },
+ ast::FlagsItem {
+ span: span(3..4),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::SwapGreed
+ ),
+ },
+ ],
+ },
+ }))
+ );
+ assert_eq!(
+ parser("(?i-U)").parse(),
+ Ok(Ast::Flags(ast::SetFlags {
+ span: span(0..6),
+ flags: ast::Flags {
+ span: span(2..5),
+ items: vec![
+ ast::FlagsItem {
+ span: span(2..3),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::CaseInsensitive
+ ),
+ },
+ ast::FlagsItem {
+ span: span(3..4),
+ kind: ast::FlagsItemKind::Negation,
+ },
+ ast::FlagsItem {
+ span: span(4..5),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::SwapGreed
+ ),
+ },
+ ],
+ },
+ }))
+ );
+
+ assert_eq!(
+ parser("()").parse(),
+ Ok(Ast::Group(ast::Group {
+ span: span(0..2),
+ kind: ast::GroupKind::CaptureIndex(1),
+ ast: Box::new(Ast::Empty(span(1..1))),
+ }))
+ );
+ assert_eq!(
+ parser("(a)").parse(),
+ Ok(Ast::Group(ast::Group {
+ span: span(0..3),
+ kind: ast::GroupKind::CaptureIndex(1),
+ ast: Box::new(lit('a', 1)),
+ }))
+ );
+ assert_eq!(
+ parser("(())").parse(),
+ Ok(Ast::Group(ast::Group {
+ span: span(0..4),
+ kind: ast::GroupKind::CaptureIndex(1),
+ ast: Box::new(Ast::Group(ast::Group {
+ span: span(1..3),
+ kind: ast::GroupKind::CaptureIndex(2),
+ ast: Box::new(Ast::Empty(span(2..2))),
+ })),
+ }))
+ );
+
+ assert_eq!(
+ parser("(?:a)").parse(),
+ Ok(Ast::Group(ast::Group {
+ span: span(0..5),
+ kind: ast::GroupKind::NonCapturing(ast::Flags {
+ span: span(2..2),
+ items: vec![],
+ }),
+ ast: Box::new(lit('a', 3)),
+ }))
+ );
+
+ assert_eq!(
+ parser("(?i:a)").parse(),
+ Ok(Ast::Group(ast::Group {
+ span: span(0..6),
+ kind: ast::GroupKind::NonCapturing(ast::Flags {
+ span: span(2..3),
+ items: vec![ast::FlagsItem {
+ span: span(2..3),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::CaseInsensitive
+ ),
+ },],
+ }),
+ ast: Box::new(lit('a', 4)),
+ }))
+ );
+ assert_eq!(
+ parser("(?i-U:a)").parse(),
+ Ok(Ast::Group(ast::Group {
+ span: span(0..8),
+ kind: ast::GroupKind::NonCapturing(ast::Flags {
+ span: span(2..5),
+ items: vec![
+ ast::FlagsItem {
+ span: span(2..3),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::CaseInsensitive
+ ),
+ },
+ ast::FlagsItem {
+ span: span(3..4),
+ kind: ast::FlagsItemKind::Negation,
+ },
+ ast::FlagsItem {
+ span: span(4..5),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::SwapGreed
+ ),
+ },
+ ],
+ }),
+ ast: Box::new(lit('a', 6)),
+ }))
+ );
+
+ assert_eq!(
+ parser("(").parse().unwrap_err(),
+ TestError {
+ span: span(0..1),
+ kind: ast::ErrorKind::GroupUnclosed,
+ }
+ );
+ assert_eq!(
+ parser("(?").parse().unwrap_err(),
+ TestError {
+ span: span(0..1),
+ kind: ast::ErrorKind::GroupUnclosed,
+ }
+ );
+ assert_eq!(
+ parser("(?P").parse().unwrap_err(),
+ TestError {
+ span: span(2..3),
+ kind: ast::ErrorKind::FlagUnrecognized,
+ }
+ );
+ assert_eq!(
+ parser("(?P<").parse().unwrap_err(),
+ TestError {
+ span: span(4..4),
+ kind: ast::ErrorKind::GroupNameUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser("(a").parse().unwrap_err(),
+ TestError {
+ span: span(0..1),
+ kind: ast::ErrorKind::GroupUnclosed,
+ }
+ );
+ assert_eq!(
+ parser("(()").parse().unwrap_err(),
+ TestError {
+ span: span(0..1),
+ kind: ast::ErrorKind::GroupUnclosed,
+ }
+ );
+ assert_eq!(
+ parser(")").parse().unwrap_err(),
+ TestError {
+ span: span(0..1),
+ kind: ast::ErrorKind::GroupUnopened,
+ }
+ );
+ assert_eq!(
+ parser("a)").parse().unwrap_err(),
+ TestError {
+ span: span(1..2),
+ kind: ast::ErrorKind::GroupUnopened,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_capture_name() {
+ assert_eq!(
+ parser("(?P<a>z)").parse(),
+ Ok(Ast::Group(ast::Group {
+ span: span(0..8),
+ kind: ast::GroupKind::CaptureName(ast::CaptureName {
+ span: span(4..5),
+ name: s("a"),
+ index: 1,
+ }),
+ ast: Box::new(lit('z', 6)),
+ }))
+ );
+ assert_eq!(
+ parser("(?P<abc>z)").parse(),
+ Ok(Ast::Group(ast::Group {
+ span: span(0..10),
+ kind: ast::GroupKind::CaptureName(ast::CaptureName {
+ span: span(4..7),
+ name: s("abc"),
+ index: 1,
+ }),
+ ast: Box::new(lit('z', 8)),
+ }))
+ );
+
+ assert_eq!(
+ parser("(?P<").parse().unwrap_err(),
+ TestError {
+ span: span(4..4),
+ kind: ast::ErrorKind::GroupNameUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser("(?P<>z)").parse().unwrap_err(),
+ TestError {
+ span: span(4..4),
+ kind: ast::ErrorKind::GroupNameEmpty,
+ }
+ );
+ assert_eq!(
+ parser("(?P<a").parse().unwrap_err(),
+ TestError {
+ span: span(5..5),
+ kind: ast::ErrorKind::GroupNameUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser("(?P<ab").parse().unwrap_err(),
+ TestError {
+ span: span(6..6),
+ kind: ast::ErrorKind::GroupNameUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser("(?P<0a").parse().unwrap_err(),
+ TestError {
+ span: span(4..5),
+ kind: ast::ErrorKind::GroupNameInvalid,
+ }
+ );
+ assert_eq!(
+ parser("(?P<~").parse().unwrap_err(),
+ TestError {
+ span: span(4..5),
+ kind: ast::ErrorKind::GroupNameInvalid,
+ }
+ );
+ assert_eq!(
+ parser("(?P<abc~").parse().unwrap_err(),
+ TestError {
+ span: span(7..8),
+ kind: ast::ErrorKind::GroupNameInvalid,
+ }
+ );
+ assert_eq!(
+ parser("(?P<a>y)(?P<a>z)").parse().unwrap_err(),
+ TestError {
+ span: span(12..13),
+ kind: ast::ErrorKind::GroupNameDuplicate {
+ original: span(4..5),
+ },
+ }
+ );
+ }
+
+ #[test]
+ fn parse_flags() {
+ assert_eq!(
+ parser("i:").parse_flags(),
+ Ok(ast::Flags {
+ span: span(0..1),
+ items: vec![ast::FlagsItem {
+ span: span(0..1),
+ kind: ast::FlagsItemKind::Flag(ast::Flag::CaseInsensitive),
+ }],
+ })
+ );
+ assert_eq!(
+ parser("i)").parse_flags(),
+ Ok(ast::Flags {
+ span: span(0..1),
+ items: vec![ast::FlagsItem {
+ span: span(0..1),
+ kind: ast::FlagsItemKind::Flag(ast::Flag::CaseInsensitive),
+ }],
+ })
+ );
+
+ assert_eq!(
+ parser("isU:").parse_flags(),
+ Ok(ast::Flags {
+ span: span(0..3),
+ items: vec![
+ ast::FlagsItem {
+ span: span(0..1),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::CaseInsensitive
+ ),
+ },
+ ast::FlagsItem {
+ span: span(1..2),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::DotMatchesNewLine
+ ),
+ },
+ ast::FlagsItem {
+ span: span(2..3),
+ kind: ast::FlagsItemKind::Flag(ast::Flag::SwapGreed),
+ },
+ ],
+ })
+ );
+
+ assert_eq!(
+ parser("-isU:").parse_flags(),
+ Ok(ast::Flags {
+ span: span(0..4),
+ items: vec![
+ ast::FlagsItem {
+ span: span(0..1),
+ kind: ast::FlagsItemKind::Negation,
+ },
+ ast::FlagsItem {
+ span: span(1..2),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::CaseInsensitive
+ ),
+ },
+ ast::FlagsItem {
+ span: span(2..3),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::DotMatchesNewLine
+ ),
+ },
+ ast::FlagsItem {
+ span: span(3..4),
+ kind: ast::FlagsItemKind::Flag(ast::Flag::SwapGreed),
+ },
+ ],
+ })
+ );
+ assert_eq!(
+ parser("i-sU:").parse_flags(),
+ Ok(ast::Flags {
+ span: span(0..4),
+ items: vec![
+ ast::FlagsItem {
+ span: span(0..1),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::CaseInsensitive
+ ),
+ },
+ ast::FlagsItem {
+ span: span(1..2),
+ kind: ast::FlagsItemKind::Negation,
+ },
+ ast::FlagsItem {
+ span: span(2..3),
+ kind: ast::FlagsItemKind::Flag(
+ ast::Flag::DotMatchesNewLine
+ ),
+ },
+ ast::FlagsItem {
+ span: span(3..4),
+ kind: ast::FlagsItemKind::Flag(ast::Flag::SwapGreed),
+ },
+ ],
+ })
+ );
+
+ assert_eq!(
+ parser("isU").parse_flags().unwrap_err(),
+ TestError {
+ span: span(3..3),
+ kind: ast::ErrorKind::FlagUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser("isUa:").parse_flags().unwrap_err(),
+ TestError {
+ span: span(3..4),
+ kind: ast::ErrorKind::FlagUnrecognized,
+ }
+ );
+ assert_eq!(
+ parser("isUi:").parse_flags().unwrap_err(),
+ TestError {
+ span: span(3..4),
+ kind: ast::ErrorKind::FlagDuplicate { original: span(0..1) },
+ }
+ );
+ assert_eq!(
+ parser("i-sU-i:").parse_flags().unwrap_err(),
+ TestError {
+ span: span(4..5),
+ kind: ast::ErrorKind::FlagRepeatedNegation {
+ original: span(1..2),
+ },
+ }
+ );
+ assert_eq!(
+ parser("-)").parse_flags().unwrap_err(),
+ TestError {
+ span: span(0..1),
+ kind: ast::ErrorKind::FlagDanglingNegation,
+ }
+ );
+ assert_eq!(
+ parser("i-)").parse_flags().unwrap_err(),
+ TestError {
+ span: span(1..2),
+ kind: ast::ErrorKind::FlagDanglingNegation,
+ }
+ );
+ assert_eq!(
+ parser("iU-)").parse_flags().unwrap_err(),
+ TestError {
+ span: span(2..3),
+ kind: ast::ErrorKind::FlagDanglingNegation,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_flag() {
+ assert_eq!(parser("i").parse_flag(), Ok(ast::Flag::CaseInsensitive));
+ assert_eq!(parser("m").parse_flag(), Ok(ast::Flag::MultiLine));
+ assert_eq!(parser("s").parse_flag(), Ok(ast::Flag::DotMatchesNewLine));
+ assert_eq!(parser("U").parse_flag(), Ok(ast::Flag::SwapGreed));
+ assert_eq!(parser("u").parse_flag(), Ok(ast::Flag::Unicode));
+ assert_eq!(parser("x").parse_flag(), Ok(ast::Flag::IgnoreWhitespace));
+
+ assert_eq!(
+ parser("a").parse_flag().unwrap_err(),
+ TestError {
+ span: span(0..1),
+ kind: ast::ErrorKind::FlagUnrecognized,
+ }
+ );
+ assert_eq!(
+ parser("☃").parse_flag().unwrap_err(),
+ TestError {
+ span: span_range("☃", 0..3),
+ kind: ast::ErrorKind::FlagUnrecognized,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_primitive_non_escape() {
+ assert_eq!(
+ parser(r".").parse_primitive(),
+ Ok(Primitive::Dot(span(0..1)))
+ );
+ assert_eq!(
+ parser(r"^").parse_primitive(),
+ Ok(Primitive::Assertion(ast::Assertion {
+ span: span(0..1),
+ kind: ast::AssertionKind::StartLine,
+ }))
+ );
+ assert_eq!(
+ parser(r"$").parse_primitive(),
+ Ok(Primitive::Assertion(ast::Assertion {
+ span: span(0..1),
+ kind: ast::AssertionKind::EndLine,
+ }))
+ );
+
+ assert_eq!(
+ parser(r"a").parse_primitive(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..1),
+ kind: ast::LiteralKind::Verbatim,
+ c: 'a',
+ }))
+ );
+ assert_eq!(
+ parser(r"|").parse_primitive(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..1),
+ kind: ast::LiteralKind::Verbatim,
+ c: '|',
+ }))
+ );
+ assert_eq!(
+ parser(r"☃").parse_primitive(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span_range("☃", 0..3),
+ kind: ast::LiteralKind::Verbatim,
+ c: '☃',
+ }))
+ );
+ }
+
+ #[test]
+ fn parse_escape() {
+ assert_eq!(
+ parser(r"\|").parse_primitive(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..2),
+ kind: ast::LiteralKind::Punctuation,
+ c: '|',
+ }))
+ );
+ let specials = &[
+ (r"\a", '\x07', ast::SpecialLiteralKind::Bell),
+ (r"\f", '\x0C', ast::SpecialLiteralKind::FormFeed),
+ (r"\t", '\t', ast::SpecialLiteralKind::Tab),
+ (r"\n", '\n', ast::SpecialLiteralKind::LineFeed),
+ (r"\r", '\r', ast::SpecialLiteralKind::CarriageReturn),
+ (r"\v", '\x0B', ast::SpecialLiteralKind::VerticalTab),
+ ];
+ for &(pat, c, ref kind) in specials {
+ assert_eq!(
+ parser(pat).parse_primitive(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..2),
+ kind: ast::LiteralKind::Special(kind.clone()),
+ c: c,
+ }))
+ );
+ }
+ assert_eq!(
+ parser(r"\A").parse_primitive(),
+ Ok(Primitive::Assertion(ast::Assertion {
+ span: span(0..2),
+ kind: ast::AssertionKind::StartText,
+ }))
+ );
+ assert_eq!(
+ parser(r"\z").parse_primitive(),
+ Ok(Primitive::Assertion(ast::Assertion {
+ span: span(0..2),
+ kind: ast::AssertionKind::EndText,
+ }))
+ );
+ assert_eq!(
+ parser(r"\b").parse_primitive(),
+ Ok(Primitive::Assertion(ast::Assertion {
+ span: span(0..2),
+ kind: ast::AssertionKind::WordBoundary,
+ }))
+ );
+ assert_eq!(
+ parser(r"\B").parse_primitive(),
+ Ok(Primitive::Assertion(ast::Assertion {
+ span: span(0..2),
+ kind: ast::AssertionKind::NotWordBoundary,
+ }))
+ );
+
+ assert_eq!(
+ parser(r"\").parse_escape().unwrap_err(),
+ TestError {
+ span: span(0..1),
+ kind: ast::ErrorKind::EscapeUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser(r"\y").parse_escape().unwrap_err(),
+ TestError {
+ span: span(0..2),
+ kind: ast::ErrorKind::EscapeUnrecognized,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_unsupported_backreference() {
+ assert_eq!(
+ parser(r"\0").parse_escape().unwrap_err(),
+ TestError {
+ span: span(0..2),
+ kind: ast::ErrorKind::UnsupportedBackreference,
+ }
+ );
+ assert_eq!(
+ parser(r"\9").parse_escape().unwrap_err(),
+ TestError {
+ span: span(0..2),
+ kind: ast::ErrorKind::UnsupportedBackreference,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_octal() {
+ for i in 0..511 {
+ let pat = format!(r"\{:o}", i);
+ assert_eq!(
+ parser_octal(&pat).parse_escape(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..pat.len()),
+ kind: ast::LiteralKind::Octal,
+ c: ::std::char::from_u32(i).unwrap(),
+ }))
+ );
+ }
+ assert_eq!(
+ parser_octal(r"\778").parse_escape(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..3),
+ kind: ast::LiteralKind::Octal,
+ c: '?',
+ }))
+ );
+ assert_eq!(
+ parser_octal(r"\7777").parse_escape(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..4),
+ kind: ast::LiteralKind::Octal,
+ c: '\u{01FF}',
+ }))
+ );
+ assert_eq!(
+ parser_octal(r"\778").parse(),
+ Ok(Ast::Concat(ast::Concat {
+ span: span(0..4),
+ asts: vec![
+ Ast::Literal(ast::Literal {
+ span: span(0..3),
+ kind: ast::LiteralKind::Octal,
+ c: '?',
+ }),
+ Ast::Literal(ast::Literal {
+ span: span(3..4),
+ kind: ast::LiteralKind::Verbatim,
+ c: '8',
+ }),
+ ],
+ }))
+ );
+ assert_eq!(
+ parser_octal(r"\7777").parse(),
+ Ok(Ast::Concat(ast::Concat {
+ span: span(0..5),
+ asts: vec![
+ Ast::Literal(ast::Literal {
+ span: span(0..4),
+ kind: ast::LiteralKind::Octal,
+ c: '\u{01FF}',
+ }),
+ Ast::Literal(ast::Literal {
+ span: span(4..5),
+ kind: ast::LiteralKind::Verbatim,
+ c: '7',
+ }),
+ ],
+ }))
+ );
+
+ assert_eq!(
+ parser_octal(r"\8").parse_escape().unwrap_err(),
+ TestError {
+ span: span(0..2),
+ kind: ast::ErrorKind::EscapeUnrecognized,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_hex_two() {
+ for i in 0..256 {
+ let pat = format!(r"\x{:02x}", i);
+ assert_eq!(
+ parser(&pat).parse_escape(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..pat.len()),
+ kind: ast::LiteralKind::HexFixed(ast::HexLiteralKind::X),
+ c: ::std::char::from_u32(i).unwrap(),
+ }))
+ );
+ }
+
+ assert_eq!(
+ parser(r"\xF").parse_escape().unwrap_err(),
+ TestError {
+ span: span(3..3),
+ kind: ast::ErrorKind::EscapeUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser(r"\xG").parse_escape().unwrap_err(),
+ TestError {
+ span: span(2..3),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ assert_eq!(
+ parser(r"\xFG").parse_escape().unwrap_err(),
+ TestError {
+ span: span(3..4),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_hex_four() {
+ for i in 0..65536 {
+ let c = match ::std::char::from_u32(i) {
+ None => continue,
+ Some(c) => c,
+ };
+ let pat = format!(r"\u{:04x}", i);
+ assert_eq!(
+ parser(&pat).parse_escape(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..pat.len()),
+ kind: ast::LiteralKind::HexFixed(
+ ast::HexLiteralKind::UnicodeShort
+ ),
+ c: c,
+ }))
+ );
+ }
+
+ assert_eq!(
+ parser(r"\uF").parse_escape().unwrap_err(),
+ TestError {
+ span: span(3..3),
+ kind: ast::ErrorKind::EscapeUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser(r"\uG").parse_escape().unwrap_err(),
+ TestError {
+ span: span(2..3),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ assert_eq!(
+ parser(r"\uFG").parse_escape().unwrap_err(),
+ TestError {
+ span: span(3..4),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ assert_eq!(
+ parser(r"\uFFG").parse_escape().unwrap_err(),
+ TestError {
+ span: span(4..5),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ assert_eq!(
+ parser(r"\uFFFG").parse_escape().unwrap_err(),
+ TestError {
+ span: span(5..6),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ assert_eq!(
+ parser(r"\uD800").parse_escape().unwrap_err(),
+ TestError {
+ span: span(2..6),
+ kind: ast::ErrorKind::EscapeHexInvalid,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_hex_eight() {
+ for i in 0..65536 {
+ let c = match ::std::char::from_u32(i) {
+ None => continue,
+ Some(c) => c,
+ };
+ let pat = format!(r"\U{:08x}", i);
+ assert_eq!(
+ parser(&pat).parse_escape(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..pat.len()),
+ kind: ast::LiteralKind::HexFixed(
+ ast::HexLiteralKind::UnicodeLong
+ ),
+ c: c,
+ }))
+ );
+ }
+
+ assert_eq!(
+ parser(r"\UF").parse_escape().unwrap_err(),
+ TestError {
+ span: span(3..3),
+ kind: ast::ErrorKind::EscapeUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser(r"\UG").parse_escape().unwrap_err(),
+ TestError {
+ span: span(2..3),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ assert_eq!(
+ parser(r"\UFG").parse_escape().unwrap_err(),
+ TestError {
+ span: span(3..4),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ assert_eq!(
+ parser(r"\UFFG").parse_escape().unwrap_err(),
+ TestError {
+ span: span(4..5),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ assert_eq!(
+ parser(r"\UFFFG").parse_escape().unwrap_err(),
+ TestError {
+ span: span(5..6),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ assert_eq!(
+ parser(r"\UFFFFG").parse_escape().unwrap_err(),
+ TestError {
+ span: span(6..7),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ assert_eq!(
+ parser(r"\UFFFFFG").parse_escape().unwrap_err(),
+ TestError {
+ span: span(7..8),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ assert_eq!(
+ parser(r"\UFFFFFFG").parse_escape().unwrap_err(),
+ TestError {
+ span: span(8..9),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ assert_eq!(
+ parser(r"\UFFFFFFFG").parse_escape().unwrap_err(),
+ TestError {
+ span: span(9..10),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_hex_brace() {
+ assert_eq!(
+ parser(r"\u{26c4}").parse_escape(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..8),
+ kind: ast::LiteralKind::HexBrace(
+ ast::HexLiteralKind::UnicodeShort
+ ),
+ c: '⛄',
+ }))
+ );
+ assert_eq!(
+ parser(r"\U{26c4}").parse_escape(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..8),
+ kind: ast::LiteralKind::HexBrace(
+ ast::HexLiteralKind::UnicodeLong
+ ),
+ c: '⛄',
+ }))
+ );
+ assert_eq!(
+ parser(r"\x{26c4}").parse_escape(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..8),
+ kind: ast::LiteralKind::HexBrace(ast::HexLiteralKind::X),
+ c: '⛄',
+ }))
+ );
+ assert_eq!(
+ parser(r"\x{26C4}").parse_escape(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..8),
+ kind: ast::LiteralKind::HexBrace(ast::HexLiteralKind::X),
+ c: '⛄',
+ }))
+ );
+ assert_eq!(
+ parser(r"\x{10fFfF}").parse_escape(),
+ Ok(Primitive::Literal(ast::Literal {
+ span: span(0..10),
+ kind: ast::LiteralKind::HexBrace(ast::HexLiteralKind::X),
+ c: '\u{10FFFF}',
+ }))
+ );
+
+ assert_eq!(
+ parser(r"\x").parse_escape().unwrap_err(),
+ TestError {
+ span: span(2..2),
+ kind: ast::ErrorKind::EscapeUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser(r"\x{").parse_escape().unwrap_err(),
+ TestError {
+ span: span(2..3),
+ kind: ast::ErrorKind::EscapeUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser(r"\x{FF").parse_escape().unwrap_err(),
+ TestError {
+ span: span(2..5),
+ kind: ast::ErrorKind::EscapeUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser(r"\x{}").parse_escape().unwrap_err(),
+ TestError {
+ span: span(2..4),
+ kind: ast::ErrorKind::EscapeHexEmpty,
+ }
+ );
+ assert_eq!(
+ parser(r"\x{FGF}").parse_escape().unwrap_err(),
+ TestError {
+ span: span(4..5),
+ kind: ast::ErrorKind::EscapeHexInvalidDigit,
+ }
+ );
+ assert_eq!(
+ parser(r"\x{FFFFFF}").parse_escape().unwrap_err(),
+ TestError {
+ span: span(3..9),
+ kind: ast::ErrorKind::EscapeHexInvalid,
+ }
+ );
+ assert_eq!(
+ parser(r"\x{D800}").parse_escape().unwrap_err(),
+ TestError {
+ span: span(3..7),
+ kind: ast::ErrorKind::EscapeHexInvalid,
+ }
+ );
+ assert_eq!(
+ parser(r"\x{FFFFFFFFF}").parse_escape().unwrap_err(),
+ TestError {
+ span: span(3..12),
+ kind: ast::ErrorKind::EscapeHexInvalid,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_decimal() {
+ assert_eq!(parser("123").parse_decimal(), Ok(123));
+ assert_eq!(parser("0").parse_decimal(), Ok(0));
+ assert_eq!(parser("01").parse_decimal(), Ok(1));
+
+ assert_eq!(
+ parser("-1").parse_decimal().unwrap_err(),
+ TestError { span: span(0..0), kind: ast::ErrorKind::DecimalEmpty }
+ );
+ assert_eq!(
+ parser("").parse_decimal().unwrap_err(),
+ TestError { span: span(0..0), kind: ast::ErrorKind::DecimalEmpty }
+ );
+ assert_eq!(
+ parser("9999999999").parse_decimal().unwrap_err(),
+ TestError {
+ span: span(0..10),
+ kind: ast::ErrorKind::DecimalInvalid,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_set_class() {
+ fn union(span: Span, items: Vec<ast::ClassSetItem>) -> ast::ClassSet {
+ ast::ClassSet::union(ast::ClassSetUnion {
+ span: span,
+ items: items,
+ })
+ }
+
+ fn intersection(
+ span: Span,
+ lhs: ast::ClassSet,
+ rhs: ast::ClassSet,
+ ) -> ast::ClassSet {
+ ast::ClassSet::BinaryOp(ast::ClassSetBinaryOp {
+ span: span,
+ kind: ast::ClassSetBinaryOpKind::Intersection,
+ lhs: Box::new(lhs),
+ rhs: Box::new(rhs),
+ })
+ }
+
+ fn difference(
+ span: Span,
+ lhs: ast::ClassSet,
+ rhs: ast::ClassSet,
+ ) -> ast::ClassSet {
+ ast::ClassSet::BinaryOp(ast::ClassSetBinaryOp {
+ span: span,
+ kind: ast::ClassSetBinaryOpKind::Difference,
+ lhs: Box::new(lhs),
+ rhs: Box::new(rhs),
+ })
+ }
+
+ fn symdifference(
+ span: Span,
+ lhs: ast::ClassSet,
+ rhs: ast::ClassSet,
+ ) -> ast::ClassSet {
+ ast::ClassSet::BinaryOp(ast::ClassSetBinaryOp {
+ span: span,
+ kind: ast::ClassSetBinaryOpKind::SymmetricDifference,
+ lhs: Box::new(lhs),
+ rhs: Box::new(rhs),
+ })
+ }
+
+ fn itemset(item: ast::ClassSetItem) -> ast::ClassSet {
+ ast::ClassSet::Item(item)
+ }
+
+ fn item_ascii(cls: ast::ClassAscii) -> ast::ClassSetItem {
+ ast::ClassSetItem::Ascii(cls)
+ }
+
+ fn item_unicode(cls: ast::ClassUnicode) -> ast::ClassSetItem {
+ ast::ClassSetItem::Unicode(cls)
+ }
+
+ fn item_perl(cls: ast::ClassPerl) -> ast::ClassSetItem {
+ ast::ClassSetItem::Perl(cls)
+ }
+
+ fn item_bracket(cls: ast::ClassBracketed) -> ast::ClassSetItem {
+ ast::ClassSetItem::Bracketed(Box::new(cls))
+ }
+
+ fn lit(span: Span, c: char) -> ast::ClassSetItem {
+ ast::ClassSetItem::Literal(ast::Literal {
+ span: span,
+ kind: ast::LiteralKind::Verbatim,
+ c: c,
+ })
+ }
+
+ fn empty(span: Span) -> ast::ClassSetItem {
+ ast::ClassSetItem::Empty(span)
+ }
+
+ fn range(span: Span, start: char, end: char) -> ast::ClassSetItem {
+ let pos1 = Position {
+ offset: span.start.offset + start.len_utf8(),
+ column: span.start.column + 1,
+ ..span.start
+ };
+ let pos2 = Position {
+ offset: span.end.offset - end.len_utf8(),
+ column: span.end.column - 1,
+ ..span.end
+ };
+ ast::ClassSetItem::Range(ast::ClassSetRange {
+ span: span,
+ start: ast::Literal {
+ span: Span { end: pos1, ..span },
+ kind: ast::LiteralKind::Verbatim,
+ c: start,
+ },
+ end: ast::Literal {
+ span: Span { start: pos2, ..span },
+ kind: ast::LiteralKind::Verbatim,
+ c: end,
+ },
+ })
+ }
+
+ fn alnum(span: Span, negated: bool) -> ast::ClassAscii {
+ ast::ClassAscii {
+ span: span,
+ kind: ast::ClassAsciiKind::Alnum,
+ negated: negated,
+ }
+ }
+
+ fn lower(span: Span, negated: bool) -> ast::ClassAscii {
+ ast::ClassAscii {
+ span: span,
+ kind: ast::ClassAsciiKind::Lower,
+ negated: negated,
+ }
+ }
+
+ assert_eq!(
+ parser("[[:alnum:]]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..11),
+ negated: false,
+ kind: itemset(item_ascii(alnum(span(1..10), false))),
+ })))
+ );
+ assert_eq!(
+ parser("[[[:alnum:]]]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..13),
+ negated: false,
+ kind: itemset(item_bracket(ast::ClassBracketed {
+ span: span(1..12),
+ negated: false,
+ kind: itemset(item_ascii(alnum(span(2..11), false))),
+ })),
+ })))
+ );
+ assert_eq!(
+ parser("[[:alnum:]&&[:lower:]]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..22),
+ negated: false,
+ kind: intersection(
+ span(1..21),
+ itemset(item_ascii(alnum(span(1..10), false))),
+ itemset(item_ascii(lower(span(12..21), false))),
+ ),
+ })))
+ );
+ assert_eq!(
+ parser("[[:alnum:]--[:lower:]]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..22),
+ negated: false,
+ kind: difference(
+ span(1..21),
+ itemset(item_ascii(alnum(span(1..10), false))),
+ itemset(item_ascii(lower(span(12..21), false))),
+ ),
+ })))
+ );
+ assert_eq!(
+ parser("[[:alnum:]~~[:lower:]]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..22),
+ negated: false,
+ kind: symdifference(
+ span(1..21),
+ itemset(item_ascii(alnum(span(1..10), false))),
+ itemset(item_ascii(lower(span(12..21), false))),
+ ),
+ })))
+ );
+
+ assert_eq!(
+ parser("[a]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..3),
+ negated: false,
+ kind: itemset(lit(span(1..2), 'a')),
+ })))
+ );
+ assert_eq!(
+ parser(r"[a\]]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..5),
+ negated: false,
+ kind: union(
+ span(1..4),
+ vec![
+ lit(span(1..2), 'a'),
+ ast::ClassSetItem::Literal(ast::Literal {
+ span: span(2..4),
+ kind: ast::LiteralKind::Punctuation,
+ c: ']',
+ }),
+ ]
+ ),
+ })))
+ );
+ assert_eq!(
+ parser(r"[a\-z]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..6),
+ negated: false,
+ kind: union(
+ span(1..5),
+ vec![
+ lit(span(1..2), 'a'),
+ ast::ClassSetItem::Literal(ast::Literal {
+ span: span(2..4),
+ kind: ast::LiteralKind::Punctuation,
+ c: '-',
+ }),
+ lit(span(4..5), 'z'),
+ ]
+ ),
+ })))
+ );
+ assert_eq!(
+ parser("[ab]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..4),
+ negated: false,
+ kind: union(
+ span(1..3),
+ vec![lit(span(1..2), 'a'), lit(span(2..3), 'b'),]
+ ),
+ })))
+ );
+ assert_eq!(
+ parser("[a-]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..4),
+ negated: false,
+ kind: union(
+ span(1..3),
+ vec![lit(span(1..2), 'a'), lit(span(2..3), '-'),]
+ ),
+ })))
+ );
+ assert_eq!(
+ parser("[-a]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..4),
+ negated: false,
+ kind: union(
+ span(1..3),
+ vec![lit(span(1..2), '-'), lit(span(2..3), 'a'),]
+ ),
+ })))
+ );
+ assert_eq!(
+ parser(r"[\pL]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..5),
+ negated: false,
+ kind: itemset(item_unicode(ast::ClassUnicode {
+ span: span(1..4),
+ negated: false,
+ kind: ast::ClassUnicodeKind::OneLetter('L'),
+ })),
+ })))
+ );
+ assert_eq!(
+ parser(r"[\w]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..4),
+ negated: false,
+ kind: itemset(item_perl(ast::ClassPerl {
+ span: span(1..3),
+ kind: ast::ClassPerlKind::Word,
+ negated: false,
+ })),
+ })))
+ );
+ assert_eq!(
+ parser(r"[a\wz]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..6),
+ negated: false,
+ kind: union(
+ span(1..5),
+ vec![
+ lit(span(1..2), 'a'),
+ item_perl(ast::ClassPerl {
+ span: span(2..4),
+ kind: ast::ClassPerlKind::Word,
+ negated: false,
+ }),
+ lit(span(4..5), 'z'),
+ ]
+ ),
+ })))
+ );
+
+ assert_eq!(
+ parser("[a-z]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..5),
+ negated: false,
+ kind: itemset(range(span(1..4), 'a', 'z')),
+ })))
+ );
+ assert_eq!(
+ parser("[a-cx-z]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..8),
+ negated: false,
+ kind: union(
+ span(1..7),
+ vec![
+ range(span(1..4), 'a', 'c'),
+ range(span(4..7), 'x', 'z'),
+ ]
+ ),
+ })))
+ );
+ assert_eq!(
+ parser(r"[\w&&a-cx-z]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..12),
+ negated: false,
+ kind: intersection(
+ span(1..11),
+ itemset(item_perl(ast::ClassPerl {
+ span: span(1..3),
+ kind: ast::ClassPerlKind::Word,
+ negated: false,
+ })),
+ union(
+ span(5..11),
+ vec![
+ range(span(5..8), 'a', 'c'),
+ range(span(8..11), 'x', 'z'),
+ ]
+ ),
+ ),
+ })))
+ );
+ assert_eq!(
+ parser(r"[a-cx-z&&\w]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..12),
+ negated: false,
+ kind: intersection(
+ span(1..11),
+ union(
+ span(1..7),
+ vec![
+ range(span(1..4), 'a', 'c'),
+ range(span(4..7), 'x', 'z'),
+ ]
+ ),
+ itemset(item_perl(ast::ClassPerl {
+ span: span(9..11),
+ kind: ast::ClassPerlKind::Word,
+ negated: false,
+ })),
+ ),
+ })))
+ );
+ assert_eq!(
+ parser(r"[a--b--c]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..9),
+ negated: false,
+ kind: difference(
+ span(1..8),
+ difference(
+ span(1..5),
+ itemset(lit(span(1..2), 'a')),
+ itemset(lit(span(4..5), 'b')),
+ ),
+ itemset(lit(span(7..8), 'c')),
+ ),
+ })))
+ );
+ assert_eq!(
+ parser(r"[a~~b~~c]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..9),
+ negated: false,
+ kind: symdifference(
+ span(1..8),
+ symdifference(
+ span(1..5),
+ itemset(lit(span(1..2), 'a')),
+ itemset(lit(span(4..5), 'b')),
+ ),
+ itemset(lit(span(7..8), 'c')),
+ ),
+ })))
+ );
+ assert_eq!(
+ parser(r"[\^&&^]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..7),
+ negated: false,
+ kind: intersection(
+ span(1..6),
+ itemset(ast::ClassSetItem::Literal(ast::Literal {
+ span: span(1..3),
+ kind: ast::LiteralKind::Punctuation,
+ c: '^',
+ })),
+ itemset(lit(span(5..6), '^')),
+ ),
+ })))
+ );
+ assert_eq!(
+ parser(r"[\&&&&]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..7),
+ negated: false,
+ kind: intersection(
+ span(1..6),
+ itemset(ast::ClassSetItem::Literal(ast::Literal {
+ span: span(1..3),
+ kind: ast::LiteralKind::Punctuation,
+ c: '&',
+ })),
+ itemset(lit(span(5..6), '&')),
+ ),
+ })))
+ );
+ assert_eq!(
+ parser(r"[&&&&]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..6),
+ negated: false,
+ kind: intersection(
+ span(1..5),
+ intersection(
+ span(1..3),
+ itemset(empty(span(1..1))),
+ itemset(empty(span(3..3))),
+ ),
+ itemset(empty(span(5..5))),
+ ),
+ })))
+ );
+
+ let pat = "[☃-⛄]";
+ assert_eq!(
+ parser(pat).parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span_range(pat, 0..9),
+ negated: false,
+ kind: itemset(ast::ClassSetItem::Range(ast::ClassSetRange {
+ span: span_range(pat, 1..8),
+ start: ast::Literal {
+ span: span_range(pat, 1..4),
+ kind: ast::LiteralKind::Verbatim,
+ c: '☃',
+ },
+ end: ast::Literal {
+ span: span_range(pat, 5..8),
+ kind: ast::LiteralKind::Verbatim,
+ c: '⛄',
+ },
+ })),
+ })))
+ );
+
+ assert_eq!(
+ parser(r"[]]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..3),
+ negated: false,
+ kind: itemset(lit(span(1..2), ']')),
+ })))
+ );
+ assert_eq!(
+ parser(r"[]\[]").parse(),
+ Ok(Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..5),
+ negated: false,
+ kind: union(
+ span(1..4),
+ vec![
+ lit(span(1..2), ']'),
+ ast::ClassSetItem::Literal(ast::Literal {
+ span: span(2..4),
+ kind: ast::LiteralKind::Punctuation,
+ c: '[',
+ }),
+ ]
+ ),
+ })))
+ );
+ assert_eq!(
+ parser(r"[\[]]").parse(),
+ Ok(concat(
+ 0..5,
+ vec![
+ Ast::Class(ast::Class::Bracketed(ast::ClassBracketed {
+ span: span(0..4),
+ negated: false,
+ kind: itemset(ast::ClassSetItem::Literal(
+ ast::Literal {
+ span: span(1..3),
+ kind: ast::LiteralKind::Punctuation,
+ c: '[',
+ }
+ )),
+ })),
+ Ast::Literal(ast::Literal {
+ span: span(4..5),
+ kind: ast::LiteralKind::Verbatim,
+ c: ']',
+ }),
+ ]
+ ))
+ );
+
+ assert_eq!(
+ parser("[").parse().unwrap_err(),
+ TestError {
+ span: span(0..1),
+ kind: ast::ErrorKind::ClassUnclosed,
+ }
+ );
+ assert_eq!(
+ parser("[[").parse().unwrap_err(),
+ TestError {
+ span: span(1..2),
+ kind: ast::ErrorKind::ClassUnclosed,
+ }
+ );
+ assert_eq!(
+ parser("[[-]").parse().unwrap_err(),
+ TestError {
+ span: span(0..1),
+ kind: ast::ErrorKind::ClassUnclosed,
+ }
+ );
+ assert_eq!(
+ parser("[[[:alnum:]").parse().unwrap_err(),
+ TestError {
+ span: span(1..2),
+ kind: ast::ErrorKind::ClassUnclosed,
+ }
+ );
+ assert_eq!(
+ parser(r"[\b]").parse().unwrap_err(),
+ TestError {
+ span: span(1..3),
+ kind: ast::ErrorKind::ClassEscapeInvalid,
+ }
+ );
+ assert_eq!(
+ parser(r"[\w-a]").parse().unwrap_err(),
+ TestError {
+ span: span(1..3),
+ kind: ast::ErrorKind::ClassRangeLiteral,
+ }
+ );
+ assert_eq!(
+ parser(r"[a-\w]").parse().unwrap_err(),
+ TestError {
+ span: span(3..5),
+ kind: ast::ErrorKind::ClassRangeLiteral,
+ }
+ );
+ assert_eq!(
+ parser(r"[z-a]").parse().unwrap_err(),
+ TestError {
+ span: span(1..4),
+ kind: ast::ErrorKind::ClassRangeInvalid,
+ }
+ );
+
+ assert_eq!(
+ parser_ignore_whitespace("[a ").parse().unwrap_err(),
+ TestError {
+ span: span(0..1),
+ kind: ast::ErrorKind::ClassUnclosed,
+ }
+ );
+ assert_eq!(
+ parser_ignore_whitespace("[a- ").parse().unwrap_err(),
+ TestError {
+ span: span(0..1),
+ kind: ast::ErrorKind::ClassUnclosed,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_set_class_open() {
+ assert_eq!(parser("[a]").parse_set_class_open(), {
+ let set = ast::ClassBracketed {
+ span: span(0..1),
+ negated: false,
+ kind: ast::ClassSet::union(ast::ClassSetUnion {
+ span: span(1..1),
+ items: vec![],
+ }),
+ };
+ let union = ast::ClassSetUnion { span: span(1..1), items: vec![] };
+ Ok((set, union))
+ });
+ assert_eq!(
+ parser_ignore_whitespace("[ a]").parse_set_class_open(),
+ {
+ let set = ast::ClassBracketed {
+ span: span(0..4),
+ negated: false,
+ kind: ast::ClassSet::union(ast::ClassSetUnion {
+ span: span(4..4),
+ items: vec![],
+ }),
+ };
+ let union =
+ ast::ClassSetUnion { span: span(4..4), items: vec![] };
+ Ok((set, union))
+ }
+ );
+ assert_eq!(parser("[^a]").parse_set_class_open(), {
+ let set = ast::ClassBracketed {
+ span: span(0..2),
+ negated: true,
+ kind: ast::ClassSet::union(ast::ClassSetUnion {
+ span: span(2..2),
+ items: vec![],
+ }),
+ };
+ let union = ast::ClassSetUnion { span: span(2..2), items: vec![] };
+ Ok((set, union))
+ });
+ assert_eq!(
+ parser_ignore_whitespace("[ ^ a]").parse_set_class_open(),
+ {
+ let set = ast::ClassBracketed {
+ span: span(0..4),
+ negated: true,
+ kind: ast::ClassSet::union(ast::ClassSetUnion {
+ span: span(4..4),
+ items: vec![],
+ }),
+ };
+ let union =
+ ast::ClassSetUnion { span: span(4..4), items: vec![] };
+ Ok((set, union))
+ }
+ );
+ assert_eq!(parser("[-a]").parse_set_class_open(), {
+ let set = ast::ClassBracketed {
+ span: span(0..2),
+ negated: false,
+ kind: ast::ClassSet::union(ast::ClassSetUnion {
+ span: span(1..1),
+ items: vec![],
+ }),
+ };
+ let union = ast::ClassSetUnion {
+ span: span(1..2),
+ items: vec![ast::ClassSetItem::Literal(ast::Literal {
+ span: span(1..2),
+ kind: ast::LiteralKind::Verbatim,
+ c: '-',
+ })],
+ };
+ Ok((set, union))
+ });
+ assert_eq!(
+ parser_ignore_whitespace("[ - a]").parse_set_class_open(),
+ {
+ let set = ast::ClassBracketed {
+ span: span(0..4),
+ negated: false,
+ kind: ast::ClassSet::union(ast::ClassSetUnion {
+ span: span(2..2),
+ items: vec![],
+ }),
+ };
+ let union = ast::ClassSetUnion {
+ span: span(2..3),
+ items: vec![ast::ClassSetItem::Literal(ast::Literal {
+ span: span(2..3),
+ kind: ast::LiteralKind::Verbatim,
+ c: '-',
+ })],
+ };
+ Ok((set, union))
+ }
+ );
+ assert_eq!(parser("[^-a]").parse_set_class_open(), {
+ let set = ast::ClassBracketed {
+ span: span(0..3),
+ negated: true,
+ kind: ast::ClassSet::union(ast::ClassSetUnion {
+ span: span(2..2),
+ items: vec![],
+ }),
+ };
+ let union = ast::ClassSetUnion {
+ span: span(2..3),
+ items: vec![ast::ClassSetItem::Literal(ast::Literal {
+ span: span(2..3),
+ kind: ast::LiteralKind::Verbatim,
+ c: '-',
+ })],
+ };
+ Ok((set, union))
+ });
+ assert_eq!(parser("[--a]").parse_set_class_open(), {
+ let set = ast::ClassBracketed {
+ span: span(0..3),
+ negated: false,
+ kind: ast::ClassSet::union(ast::ClassSetUnion {
+ span: span(1..1),
+ items: vec![],
+ }),
+ };
+ let union = ast::ClassSetUnion {
+ span: span(1..3),
+ items: vec![
+ ast::ClassSetItem::Literal(ast::Literal {
+ span: span(1..2),
+ kind: ast::LiteralKind::Verbatim,
+ c: '-',
+ }),
+ ast::ClassSetItem::Literal(ast::Literal {
+ span: span(2..3),
+ kind: ast::LiteralKind::Verbatim,
+ c: '-',
+ }),
+ ],
+ };
+ Ok((set, union))
+ });
+ assert_eq!(parser("[]a]").parse_set_class_open(), {
+ let set = ast::ClassBracketed {
+ span: span(0..2),
+ negated: false,
+ kind: ast::ClassSet::union(ast::ClassSetUnion {
+ span: span(1..1),
+ items: vec![],
+ }),
+ };
+ let union = ast::ClassSetUnion {
+ span: span(1..2),
+ items: vec![ast::ClassSetItem::Literal(ast::Literal {
+ span: span(1..2),
+ kind: ast::LiteralKind::Verbatim,
+ c: ']',
+ })],
+ };
+ Ok((set, union))
+ });
+ assert_eq!(
+ parser_ignore_whitespace("[ ] a]").parse_set_class_open(),
+ {
+ let set = ast::ClassBracketed {
+ span: span(0..4),
+ negated: false,
+ kind: ast::ClassSet::union(ast::ClassSetUnion {
+ span: span(2..2),
+ items: vec![],
+ }),
+ };
+ let union = ast::ClassSetUnion {
+ span: span(2..3),
+ items: vec![ast::ClassSetItem::Literal(ast::Literal {
+ span: span(2..3),
+ kind: ast::LiteralKind::Verbatim,
+ c: ']',
+ })],
+ };
+ Ok((set, union))
+ }
+ );
+ assert_eq!(parser("[^]a]").parse_set_class_open(), {
+ let set = ast::ClassBracketed {
+ span: span(0..3),
+ negated: true,
+ kind: ast::ClassSet::union(ast::ClassSetUnion {
+ span: span(2..2),
+ items: vec![],
+ }),
+ };
+ let union = ast::ClassSetUnion {
+ span: span(2..3),
+ items: vec![ast::ClassSetItem::Literal(ast::Literal {
+ span: span(2..3),
+ kind: ast::LiteralKind::Verbatim,
+ c: ']',
+ })],
+ };
+ Ok((set, union))
+ });
+ assert_eq!(parser("[-]a]").parse_set_class_open(), {
+ let set = ast::ClassBracketed {
+ span: span(0..2),
+ negated: false,
+ kind: ast::ClassSet::union(ast::ClassSetUnion {
+ span: span(1..1),
+ items: vec![],
+ }),
+ };
+ let union = ast::ClassSetUnion {
+ span: span(1..2),
+ items: vec![ast::ClassSetItem::Literal(ast::Literal {
+ span: span(1..2),
+ kind: ast::LiteralKind::Verbatim,
+ c: '-',
+ })],
+ };
+ Ok((set, union))
+ });
+
+ assert_eq!(
+ parser("[").parse_set_class_open().unwrap_err(),
+ TestError {
+ span: span(0..1),
+ kind: ast::ErrorKind::ClassUnclosed,
+ }
+ );
+ assert_eq!(
+ parser_ignore_whitespace("[ ")
+ .parse_set_class_open()
+ .unwrap_err(),
+ TestError {
+ span: span(0..5),
+ kind: ast::ErrorKind::ClassUnclosed,
+ }
+ );
+ assert_eq!(
+ parser("[^").parse_set_class_open().unwrap_err(),
+ TestError {
+ span: span(0..2),
+ kind: ast::ErrorKind::ClassUnclosed,
+ }
+ );
+ assert_eq!(
+ parser("[]").parse_set_class_open().unwrap_err(),
+ TestError {
+ span: span(0..2),
+ kind: ast::ErrorKind::ClassUnclosed,
+ }
+ );
+ assert_eq!(
+ parser("[-").parse_set_class_open().unwrap_err(),
+ TestError {
+ span: span(0..2),
+ kind: ast::ErrorKind::ClassUnclosed,
+ }
+ );
+ assert_eq!(
+ parser("[--").parse_set_class_open().unwrap_err(),
+ TestError {
+ span: span(0..3),
+ kind: ast::ErrorKind::ClassUnclosed,
+ }
+ );
+ }
+
+ #[test]
+ fn maybe_parse_ascii_class() {
+ assert_eq!(
+ parser(r"[:alnum:]").maybe_parse_ascii_class(),
+ Some(ast::ClassAscii {
+ span: span(0..9),
+ kind: ast::ClassAsciiKind::Alnum,
+ negated: false,
+ })
+ );
+ assert_eq!(
+ parser(r"[:alnum:]A").maybe_parse_ascii_class(),
+ Some(ast::ClassAscii {
+ span: span(0..9),
+ kind: ast::ClassAsciiKind::Alnum,
+ negated: false,
+ })
+ );
+ assert_eq!(
+ parser(r"[:^alnum:]").maybe_parse_ascii_class(),
+ Some(ast::ClassAscii {
+ span: span(0..10),
+ kind: ast::ClassAsciiKind::Alnum,
+ negated: true,
+ })
+ );
+
+ let p = parser(r"[:");
+ assert_eq!(p.maybe_parse_ascii_class(), None);
+ assert_eq!(p.offset(), 0);
+
+ let p = parser(r"[:^");
+ assert_eq!(p.maybe_parse_ascii_class(), None);
+ assert_eq!(p.offset(), 0);
+
+ let p = parser(r"[^:alnum:]");
+ assert_eq!(p.maybe_parse_ascii_class(), None);
+ assert_eq!(p.offset(), 0);
+
+ let p = parser(r"[:alnnum:]");
+ assert_eq!(p.maybe_parse_ascii_class(), None);
+ assert_eq!(p.offset(), 0);
+
+ let p = parser(r"[:alnum]");
+ assert_eq!(p.maybe_parse_ascii_class(), None);
+ assert_eq!(p.offset(), 0);
+
+ let p = parser(r"[:alnum:");
+ assert_eq!(p.maybe_parse_ascii_class(), None);
+ assert_eq!(p.offset(), 0);
+ }
+
+ #[test]
+ fn parse_unicode_class() {
+ assert_eq!(
+ parser(r"\pN").parse_escape(),
+ Ok(Primitive::Unicode(ast::ClassUnicode {
+ span: span(0..3),
+ negated: false,
+ kind: ast::ClassUnicodeKind::OneLetter('N'),
+ }))
+ );
+ assert_eq!(
+ parser(r"\PN").parse_escape(),
+ Ok(Primitive::Unicode(ast::ClassUnicode {
+ span: span(0..3),
+ negated: true,
+ kind: ast::ClassUnicodeKind::OneLetter('N'),
+ }))
+ );
+ assert_eq!(
+ parser(r"\p{N}").parse_escape(),
+ Ok(Primitive::Unicode(ast::ClassUnicode {
+ span: span(0..5),
+ negated: false,
+ kind: ast::ClassUnicodeKind::Named(s("N")),
+ }))
+ );
+ assert_eq!(
+ parser(r"\P{N}").parse_escape(),
+ Ok(Primitive::Unicode(ast::ClassUnicode {
+ span: span(0..5),
+ negated: true,
+ kind: ast::ClassUnicodeKind::Named(s("N")),
+ }))
+ );
+ assert_eq!(
+ parser(r"\p{Greek}").parse_escape(),
+ Ok(Primitive::Unicode(ast::ClassUnicode {
+ span: span(0..9),
+ negated: false,
+ kind: ast::ClassUnicodeKind::Named(s("Greek")),
+ }))
+ );
+
+ assert_eq!(
+ parser(r"\p{scx:Katakana}").parse_escape(),
+ Ok(Primitive::Unicode(ast::ClassUnicode {
+ span: span(0..16),
+ negated: false,
+ kind: ast::ClassUnicodeKind::NamedValue {
+ op: ast::ClassUnicodeOpKind::Colon,
+ name: s("scx"),
+ value: s("Katakana"),
+ },
+ }))
+ );
+ assert_eq!(
+ parser(r"\p{scx=Katakana}").parse_escape(),
+ Ok(Primitive::Unicode(ast::ClassUnicode {
+ span: span(0..16),
+ negated: false,
+ kind: ast::ClassUnicodeKind::NamedValue {
+ op: ast::ClassUnicodeOpKind::Equal,
+ name: s("scx"),
+ value: s("Katakana"),
+ },
+ }))
+ );
+ assert_eq!(
+ parser(r"\p{scx!=Katakana}").parse_escape(),
+ Ok(Primitive::Unicode(ast::ClassUnicode {
+ span: span(0..17),
+ negated: false,
+ kind: ast::ClassUnicodeKind::NamedValue {
+ op: ast::ClassUnicodeOpKind::NotEqual,
+ name: s("scx"),
+ value: s("Katakana"),
+ },
+ }))
+ );
+
+ assert_eq!(
+ parser(r"\p{:}").parse_escape(),
+ Ok(Primitive::Unicode(ast::ClassUnicode {
+ span: span(0..5),
+ negated: false,
+ kind: ast::ClassUnicodeKind::NamedValue {
+ op: ast::ClassUnicodeOpKind::Colon,
+ name: s(""),
+ value: s(""),
+ },
+ }))
+ );
+ assert_eq!(
+ parser(r"\p{=}").parse_escape(),
+ Ok(Primitive::Unicode(ast::ClassUnicode {
+ span: span(0..5),
+ negated: false,
+ kind: ast::ClassUnicodeKind::NamedValue {
+ op: ast::ClassUnicodeOpKind::Equal,
+ name: s(""),
+ value: s(""),
+ },
+ }))
+ );
+ assert_eq!(
+ parser(r"\p{!=}").parse_escape(),
+ Ok(Primitive::Unicode(ast::ClassUnicode {
+ span: span(0..6),
+ negated: false,
+ kind: ast::ClassUnicodeKind::NamedValue {
+ op: ast::ClassUnicodeOpKind::NotEqual,
+ name: s(""),
+ value: s(""),
+ },
+ }))
+ );
+
+ assert_eq!(
+ parser(r"\p").parse_escape().unwrap_err(),
+ TestError {
+ span: span(2..2),
+ kind: ast::ErrorKind::EscapeUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser(r"\p{").parse_escape().unwrap_err(),
+ TestError {
+ span: span(3..3),
+ kind: ast::ErrorKind::EscapeUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser(r"\p{N").parse_escape().unwrap_err(),
+ TestError {
+ span: span(4..4),
+ kind: ast::ErrorKind::EscapeUnexpectedEof,
+ }
+ );
+ assert_eq!(
+ parser(r"\p{Greek").parse_escape().unwrap_err(),
+ TestError {
+ span: span(8..8),
+ kind: ast::ErrorKind::EscapeUnexpectedEof,
+ }
+ );
+
+ assert_eq!(
+ parser(r"\pNz").parse(),
+ Ok(Ast::Concat(ast::Concat {
+ span: span(0..4),
+ asts: vec![
+ Ast::Class(ast::Class::Unicode(ast::ClassUnicode {
+ span: span(0..3),
+ negated: false,
+ kind: ast::ClassUnicodeKind::OneLetter('N'),
+ })),
+ Ast::Literal(ast::Literal {
+ span: span(3..4),
+ kind: ast::LiteralKind::Verbatim,
+ c: 'z',
+ }),
+ ],
+ }))
+ );
+ assert_eq!(
+ parser(r"\p{Greek}z").parse(),
+ Ok(Ast::Concat(ast::Concat {
+ span: span(0..10),
+ asts: vec![
+ Ast::Class(ast::Class::Unicode(ast::ClassUnicode {
+ span: span(0..9),
+ negated: false,
+ kind: ast::ClassUnicodeKind::Named(s("Greek")),
+ })),
+ Ast::Literal(ast::Literal {
+ span: span(9..10),
+ kind: ast::LiteralKind::Verbatim,
+ c: 'z',
+ }),
+ ],
+ }))
+ );
+ assert_eq!(
+ parser(r"\p\{").parse().unwrap_err(),
+ TestError {
+ span: span(2..3),
+ kind: ast::ErrorKind::UnicodeClassInvalid,
+ }
+ );
+ assert_eq!(
+ parser(r"\P\{").parse().unwrap_err(),
+ TestError {
+ span: span(2..3),
+ kind: ast::ErrorKind::UnicodeClassInvalid,
+ }
+ );
+ }
+
+ #[test]
+ fn parse_perl_class() {
+ assert_eq!(
+ parser(r"\d").parse_escape(),
+ Ok(Primitive::Perl(ast::ClassPerl {
+ span: span(0..2),
+ kind: ast::ClassPerlKind::Digit,
+ negated: false,
+ }))
+ );
+ assert_eq!(
+ parser(r"\D").parse_escape(),
+ Ok(Primitive::Perl(ast::ClassPerl {
+ span: span(0..2),
+ kind: ast::ClassPerlKind::Digit,
+ negated: true,
+ }))
+ );
+ assert_eq!(
+ parser(r"\s").parse_escape(),
+ Ok(Primitive::Perl(ast::ClassPerl {
+ span: span(0..2),
+ kind: ast::ClassPerlKind::Space,
+ negated: false,
+ }))
+ );
+ assert_eq!(
+ parser(r"\S").parse_escape(),
+ Ok(Primitive::Perl(ast::ClassPerl {
+ span: span(0..2),
+ kind: ast::ClassPerlKind::Space,
+ negated: true,
+ }))
+ );
+ assert_eq!(
+ parser(r"\w").parse_escape(),
+ Ok(Primitive::Perl(ast::ClassPerl {
+ span: span(0..2),
+ kind: ast::ClassPerlKind::Word,
+ negated: false,
+ }))
+ );
+ assert_eq!(
+ parser(r"\W").parse_escape(),
+ Ok(Primitive::Perl(ast::ClassPerl {
+ span: span(0..2),
+ kind: ast::ClassPerlKind::Word,
+ negated: true,
+ }))
+ );
+
+ assert_eq!(
+ parser(r"\d").parse(),
+ Ok(Ast::Class(ast::Class::Perl(ast::ClassPerl {
+ span: span(0..2),
+ kind: ast::ClassPerlKind::Digit,
+ negated: false,
+ })))
+ );
+ assert_eq!(
+ parser(r"\dz").parse(),
+ Ok(Ast::Concat(ast::Concat {
+ span: span(0..3),
+ asts: vec![
+ Ast::Class(ast::Class::Perl(ast::ClassPerl {
+ span: span(0..2),
+ kind: ast::ClassPerlKind::Digit,
+ negated: false,
+ })),
+ Ast::Literal(ast::Literal {
+ span: span(2..3),
+ kind: ast::LiteralKind::Verbatim,
+ c: 'z',
+ }),
+ ],
+ }))
+ );
+ }
+
+ // This tests a bug fix where the nest limit checker wasn't decrementing
+ // its depth during post-traversal, which causes long regexes to trip
+ // the default limit too aggressively.
+ #[test]
+ fn regression_454_nest_too_big() {
+ let pattern = r#"
+ 2(?:
+ [45]\d{3}|
+ 7(?:
+ 1[0-267]|
+ 2[0-289]|
+ 3[0-29]|
+ 4[01]|
+ 5[1-3]|
+ 6[013]|
+ 7[0178]|
+ 91
+ )|
+ 8(?:
+ 0[125]|
+ [139][1-6]|
+ 2[0157-9]|
+ 41|
+ 6[1-35]|
+ 7[1-5]|
+ 8[1-8]|
+ 90
+ )|
+ 9(?:
+ 0[0-2]|
+ 1[0-4]|
+ 2[568]|
+ 3[3-6]|
+ 5[5-7]|
+ 6[0167]|
+ 7[15]|
+ 8[0146-9]
+ )
+ )\d{4}
+ "#;
+ assert!(parser_nest_limit(pattern, 50).parse().is_ok());
+ }
+
+ // This tests that we treat a trailing `-` in a character class as a
+ // literal `-` even when whitespace mode is enabled and there is whitespace
+ // after the trailing `-`.
+ #[test]
+ fn regression_455_trailing_dash_ignore_whitespace() {
+ assert!(parser("(?x)[ / - ]").parse().is_ok());
+ assert!(parser("(?x)[ a - ]").parse().is_ok());
+ assert!(parser(
+ "(?x)[
+ a
+ - ]
+ "
+ )
+ .parse()
+ .is_ok());
+ assert!(parser(
+ "(?x)[
+ a # wat
+ - ]
+ "
+ )
+ .parse()
+ .is_ok());
+
+ assert!(parser("(?x)[ / -").parse().is_err());
+ assert!(parser("(?x)[ / - ").parse().is_err());
+ assert!(parser(
+ "(?x)[
+ / -
+ "
+ )
+ .parse()
+ .is_err());
+ assert!(parser(
+ "(?x)[
+ / - # wat
+ "
+ )
+ .parse()
+ .is_err());
+ }
+}
diff --git a/src/ast/print.rs b/src/ast/print.rs
new file mode 100644
index 0000000..1b9bc41
--- /dev/null
+++ b/src/ast/print.rs
@@ -0,0 +1,569 @@
+/*!
+This module provides a regular expression printer for `Ast`.
+*/
+
+use std::fmt;
+
+use ast::visitor::{self, Visitor};
+use ast::{self, Ast};
+
+/// A builder for constructing a printer.
+///
+/// Note that since a printer doesn't have any configuration knobs, this type
+/// remains unexported.
+#[derive(Clone, Debug)]
+struct PrinterBuilder {
+ _priv: (),
+}
+
+impl Default for PrinterBuilder {
+ fn default() -> PrinterBuilder {
+ PrinterBuilder::new()
+ }
+}
+
+impl PrinterBuilder {
+ fn new() -> PrinterBuilder {
+ PrinterBuilder { _priv: () }
+ }
+
+ fn build(&self) -> Printer {
+ Printer { _priv: () }
+ }
+}
+
+/// A printer for a regular expression abstract syntax tree.
+///
+/// A printer converts an abstract syntax tree (AST) to a regular expression
+/// pattern string. This particular printer uses constant stack space and heap
+/// space proportional to the size of the AST.
+///
+/// This printer will not necessarily preserve the original formatting of the
+/// regular expression pattern string. For example, all whitespace and comments
+/// are ignored.
+#[derive(Debug)]
+pub struct Printer {
+ _priv: (),
+}
+
+impl Printer {
+ /// Create a new printer.
+ pub fn new() -> Printer {
+ PrinterBuilder::new().build()
+ }
+
+ /// Print the given `Ast` to the given writer. The writer must implement
+ /// `fmt::Write`. Typical implementations of `fmt::Write` that can be used
+ /// here are a `fmt::Formatter` (which is available in `fmt::Display`
+ /// implementations) or a `&mut String`.
+ pub fn print<W: fmt::Write>(&mut self, ast: &Ast, wtr: W) -> fmt::Result {
+ visitor::visit(ast, Writer { printer: self, wtr: wtr })
+ }
+}
+
+#[derive(Debug)]
+struct Writer<'p, W> {
+ printer: &'p mut Printer,
+ wtr: W,
+}
+
+impl<'p, W: fmt::Write> Visitor for Writer<'p, W> {
+ type Output = ();
+ type Err = fmt::Error;
+
+ fn finish(self) -> fmt::Result {
+ Ok(())
+ }
+
+ fn visit_pre(&mut self, ast: &Ast) -> fmt::Result {
+ match *ast {
+ Ast::Group(ref x) => self.fmt_group_pre(x),
+ Ast::Class(ast::Class::Bracketed(ref x)) => {
+ self.fmt_class_bracketed_pre(x)
+ }
+ _ => Ok(()),
+ }
+ }
+
+ fn visit_post(&mut self, ast: &Ast) -> fmt::Result {
+ use ast::Class;
+
+ match *ast {
+ Ast::Empty(_) => Ok(()),
+ Ast::Flags(ref x) => self.fmt_set_flags(x),
+ Ast::Literal(ref x) => self.fmt_literal(x),
+ Ast::Dot(_) => self.wtr.write_str("."),
+ Ast::Assertion(ref x) => self.fmt_assertion(x),
+ Ast::Class(Class::Perl(ref x)) => self.fmt_class_perl(x),
+ Ast::Class(Class::Unicode(ref x)) => self.fmt_class_unicode(x),
+ Ast::Class(Class::Bracketed(ref x)) => {
+ self.fmt_class_bracketed_post(x)
+ }
+ Ast::Repetition(ref x) => self.fmt_repetition(x),
+ Ast::Group(ref x) => self.fmt_group_post(x),
+ Ast::Alternation(_) => Ok(()),
+ Ast::Concat(_) => Ok(()),
+ }
+ }
+
+ fn visit_alternation_in(&mut self) -> fmt::Result {
+ self.wtr.write_str("|")
+ }
+
+ fn visit_class_set_item_pre(
+ &mut self,
+ ast: &ast::ClassSetItem,
+ ) -> Result<(), Self::Err> {
+ match *ast {
+ ast::ClassSetItem::Bracketed(ref x) => {
+ self.fmt_class_bracketed_pre(x)
+ }
+ _ => Ok(()),
+ }
+ }
+
+ fn visit_class_set_item_post(
+ &mut self,
+ ast: &ast::ClassSetItem,
+ ) -> Result<(), Self::Err> {
+ use ast::ClassSetItem::*;
+
+ match *ast {
+ Empty(_) => Ok(()),
+ Literal(ref x) => self.fmt_literal(x),
+ Range(ref x) => {
+ self.fmt_literal(&x.start)?;
+ self.wtr.write_str("-")?;
+ self.fmt_literal(&x.end)?;
+ Ok(())
+ }
+ Ascii(ref x) => self.fmt_class_ascii(x),
+ Unicode(ref x) => self.fmt_class_unicode(x),
+ Perl(ref x) => self.fmt_class_perl(x),
+ Bracketed(ref x) => self.fmt_class_bracketed_post(x),
+ Union(_) => Ok(()),
+ }
+ }
+
+ fn visit_class_set_binary_op_in(
+ &mut self,
+ ast: &ast::ClassSetBinaryOp,
+ ) -> Result<(), Self::Err> {
+ self.fmt_class_set_binary_op_kind(&ast.kind)
+ }
+}
+
+impl<'p, W: fmt::Write> Writer<'p, W> {
+ fn fmt_group_pre(&mut self, ast: &ast::Group) -> fmt::Result {
+ use ast::GroupKind::*;
+ match ast.kind {
+ CaptureIndex(_) => self.wtr.write_str("("),
+ CaptureName(ref x) => {
+ self.wtr.write_str("(?P<")?;
+ self.wtr.write_str(&x.name)?;
+ self.wtr.write_str(">")?;
+ Ok(())
+ }
+ NonCapturing(ref flags) => {
+ self.wtr.write_str("(?")?;
+ self.fmt_flags(flags)?;
+ self.wtr.write_str(":")?;
+ Ok(())
+ }
+ }
+ }
+
+ fn fmt_group_post(&mut self, _ast: &ast::Group) -> fmt::Result {
+ self.wtr.write_str(")")
+ }
+
+ fn fmt_repetition(&mut self, ast: &ast::Repetition) -> fmt::Result {
+ use ast::RepetitionKind::*;
+ match ast.op.kind {
+ ZeroOrOne if ast.greedy => self.wtr.write_str("?"),
+ ZeroOrOne => self.wtr.write_str("??"),
+ ZeroOrMore if ast.greedy => self.wtr.write_str("*"),
+ ZeroOrMore => self.wtr.write_str("*?"),
+ OneOrMore if ast.greedy => self.wtr.write_str("+"),
+ OneOrMore => self.wtr.write_str("+?"),
+ Range(ref x) => {
+ self.fmt_repetition_range(x)?;
+ if !ast.greedy {
+ self.wtr.write_str("?")?;
+ }
+ Ok(())
+ }
+ }
+ }
+
+ fn fmt_repetition_range(
+ &mut self,
+ ast: &ast::RepetitionRange,
+ ) -> fmt::Result {
+ use ast::RepetitionRange::*;
+ match *ast {
+ Exactly(x) => write!(self.wtr, "{{{}}}", x),
+ AtLeast(x) => write!(self.wtr, "{{{},}}", x),
+ Bounded(x, y) => write!(self.wtr, "{{{},{}}}", x, y),
+ }
+ }
+
+ fn fmt_literal(&mut self, ast: &ast::Literal) -> fmt::Result {
+ use ast::LiteralKind::*;
+
+ match ast.kind {
+ Verbatim => self.wtr.write_char(ast.c),
+ Punctuation => write!(self.wtr, r"\{}", ast.c),
+ Octal => write!(self.wtr, r"\{:o}", ast.c as u32),
+ HexFixed(ast::HexLiteralKind::X) => {
+ write!(self.wtr, r"\x{:02X}", ast.c as u32)
+ }
+ HexFixed(ast::HexLiteralKind::UnicodeShort) => {
+ write!(self.wtr, r"\u{:04X}", ast.c as u32)
+ }
+ HexFixed(ast::HexLiteralKind::UnicodeLong) => {
+ write!(self.wtr, r"\U{:08X}", ast.c as u32)
+ }
+ HexBrace(ast::HexLiteralKind::X) => {
+ write!(self.wtr, r"\x{{{:X}}}", ast.c as u32)
+ }
+ HexBrace(ast::HexLiteralKind::UnicodeShort) => {
+ write!(self.wtr, r"\u{{{:X}}}", ast.c as u32)
+ }
+ HexBrace(ast::HexLiteralKind::UnicodeLong) => {
+ write!(self.wtr, r"\U{{{:X}}}", ast.c as u32)
+ }
+ Special(ast::SpecialLiteralKind::Bell) => {
+ self.wtr.write_str(r"\a")
+ }
+ Special(ast::SpecialLiteralKind::FormFeed) => {
+ self.wtr.write_str(r"\f")
+ }
+ Special(ast::SpecialLiteralKind::Tab) => self.wtr.write_str(r"\t"),
+ Special(ast::SpecialLiteralKind::LineFeed) => {
+ self.wtr.write_str(r"\n")
+ }
+ Special(ast::SpecialLiteralKind::CarriageReturn) => {
+ self.wtr.write_str(r"\r")
+ }
+ Special(ast::SpecialLiteralKind::VerticalTab) => {
+ self.wtr.write_str(r"\v")
+ }
+ Special(ast::SpecialLiteralKind::Space) => {
+ self.wtr.write_str(r"\ ")
+ }
+ }
+ }
+
+ fn fmt_assertion(&mut self, ast: &ast::Assertion) -> fmt::Result {
+ use ast::AssertionKind::*;
+ match ast.kind {
+ StartLine => self.wtr.write_str("^"),
+ EndLine => self.wtr.write_str("$"),
+ StartText => self.wtr.write_str(r"\A"),
+ EndText => self.wtr.write_str(r"\z"),
+ WordBoundary => self.wtr.write_str(r"\b"),
+ NotWordBoundary => self.wtr.write_str(r"\B"),
+ }
+ }
+
+ fn fmt_set_flags(&mut self, ast: &ast::SetFlags) -> fmt::Result {
+ self.wtr.write_str("(?")?;
+ self.fmt_flags(&ast.flags)?;
+ self.wtr.write_str(")")?;
+ Ok(())
+ }
+
+ fn fmt_flags(&mut self, ast: &ast::Flags) -> fmt::Result {
+ use ast::{Flag, FlagsItemKind};
+
+ for item in &ast.items {
+ match item.kind {
+ FlagsItemKind::Negation => self.wtr.write_str("-"),
+ FlagsItemKind::Flag(ref flag) => match *flag {
+ Flag::CaseInsensitive => self.wtr.write_str("i"),
+ Flag::MultiLine => self.wtr.write_str("m"),
+ Flag::DotMatchesNewLine => self.wtr.write_str("s"),
+ Flag::SwapGreed => self.wtr.write_str("U"),
+ Flag::Unicode => self.wtr.write_str("u"),
+ Flag::IgnoreWhitespace => self.wtr.write_str("x"),
+ },
+ }?;
+ }
+ Ok(())
+ }
+
+ fn fmt_class_bracketed_pre(
+ &mut self,
+ ast: &ast::ClassBracketed,
+ ) -> fmt::Result {
+ if ast.negated {
+ self.wtr.write_str("[^")
+ } else {
+ self.wtr.write_str("[")
+ }
+ }
+
+ fn fmt_class_bracketed_post(
+ &mut self,
+ _ast: &ast::ClassBracketed,
+ ) -> fmt::Result {
+ self.wtr.write_str("]")
+ }
+
+ fn fmt_class_set_binary_op_kind(
+ &mut self,
+ ast: &ast::ClassSetBinaryOpKind,
+ ) -> fmt::Result {
+ use ast::ClassSetBinaryOpKind::*;
+ match *ast {
+ Intersection => self.wtr.write_str("&&"),
+ Difference => self.wtr.write_str("--"),
+ SymmetricDifference => self.wtr.write_str("~~"),
+ }
+ }
+
+ fn fmt_class_perl(&mut self, ast: &ast::ClassPerl) -> fmt::Result {
+ use ast::ClassPerlKind::*;
+ match ast.kind {
+ Digit if ast.negated => self.wtr.write_str(r"\D"),
+ Digit => self.wtr.write_str(r"\d"),
+ Space if ast.negated => self.wtr.write_str(r"\S"),
+ Space => self.wtr.write_str(r"\s"),
+ Word if ast.negated => self.wtr.write_str(r"\W"),
+ Word => self.wtr.write_str(r"\w"),
+ }
+ }
+
+ fn fmt_class_ascii(&mut self, ast: &ast::ClassAscii) -> fmt::Result {
+ use ast::ClassAsciiKind::*;
+ match ast.kind {
+ Alnum if ast.negated => self.wtr.write_str("[:^alnum:]"),
+ Alnum => self.wtr.write_str("[:alnum:]"),
+ Alpha if ast.negated => self.wtr.write_str("[:^alpha:]"),
+ Alpha => self.wtr.write_str("[:alpha:]"),
+ Ascii if ast.negated => self.wtr.write_str("[:^ascii:]"),
+ Ascii => self.wtr.write_str("[:ascii:]"),
+ Blank if ast.negated => self.wtr.write_str("[:^blank:]"),
+ Blank => self.wtr.write_str("[:blank:]"),
+ Cntrl if ast.negated => self.wtr.write_str("[:^cntrl:]"),
+ Cntrl => self.wtr.write_str("[:cntrl:]"),
+ Digit if ast.negated => self.wtr.write_str("[:^digit:]"),
+ Digit => self.wtr.write_str("[:digit:]"),
+ Graph if ast.negated => self.wtr.write_str("[:^graph:]"),
+ Graph => self.wtr.write_str("[:graph:]"),
+ Lower if ast.negated => self.wtr.write_str("[:^lower:]"),
+ Lower => self.wtr.write_str("[:lower:]"),
+ Print if ast.negated => self.wtr.write_str("[:^print:]"),
+ Print => self.wtr.write_str("[:print:]"),
+ Punct if ast.negated => self.wtr.write_str("[:^punct:]"),
+ Punct => self.wtr.write_str("[:punct:]"),
+ Space if ast.negated => self.wtr.write_str("[:^space:]"),
+ Space => self.wtr.write_str("[:space:]"),
+ Upper if ast.negated => self.wtr.write_str("[:^upper:]"),
+ Upper => self.wtr.write_str("[:upper:]"),
+ Word if ast.negated => self.wtr.write_str("[:^word:]"),
+ Word => self.wtr.write_str("[:word:]"),
+ Xdigit if ast.negated => self.wtr.write_str("[:^xdigit:]"),
+ Xdigit => self.wtr.write_str("[:xdigit:]"),
+ }
+ }
+
+ fn fmt_class_unicode(&mut self, ast: &ast::ClassUnicode) -> fmt::Result {
+ use ast::ClassUnicodeKind::*;
+ use ast::ClassUnicodeOpKind::*;
+
+ if ast.negated {
+ self.wtr.write_str(r"\P")?;
+ } else {
+ self.wtr.write_str(r"\p")?;
+ }
+ match ast.kind {
+ OneLetter(c) => self.wtr.write_char(c),
+ Named(ref x) => write!(self.wtr, "{{{}}}", x),
+ NamedValue { op: Equal, ref name, ref value } => {
+ write!(self.wtr, "{{{}={}}}", name, value)
+ }
+ NamedValue { op: Colon, ref name, ref value } => {
+ write!(self.wtr, "{{{}:{}}}", name, value)
+ }
+ NamedValue { op: NotEqual, ref name, ref value } => {
+ write!(self.wtr, "{{{}!={}}}", name, value)
+ }
+ }
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use super::Printer;
+ use ast::parse::ParserBuilder;
+
+ fn roundtrip(given: &str) {
+ roundtrip_with(|b| b, given);
+ }
+
+ fn roundtrip_with<F>(mut f: F, given: &str)
+ where
+ F: FnMut(&mut ParserBuilder) -> &mut ParserBuilder,
+ {
+ let mut builder = ParserBuilder::new();
+ f(&mut builder);
+ let ast = builder.build().parse(given).unwrap();
+
+ let mut printer = Printer::new();
+ let mut dst = String::new();
+ printer.print(&ast, &mut dst).unwrap();
+ assert_eq!(given, dst);
+ }
+
+ #[test]
+ fn print_literal() {
+ roundtrip("a");
+ roundtrip(r"\[");
+ roundtrip_with(|b| b.octal(true), r"\141");
+ roundtrip(r"\x61");
+ roundtrip(r"\x7F");
+ roundtrip(r"\u0061");
+ roundtrip(r"\U00000061");
+ roundtrip(r"\x{61}");
+ roundtrip(r"\x{7F}");
+ roundtrip(r"\u{61}");
+ roundtrip(r"\U{61}");
+
+ roundtrip(r"\a");
+ roundtrip(r"\f");
+ roundtrip(r"\t");
+ roundtrip(r"\n");
+ roundtrip(r"\r");
+ roundtrip(r"\v");
+ roundtrip(r"(?x)\ ");
+ }
+
+ #[test]
+ fn print_dot() {
+ roundtrip(".");
+ }
+
+ #[test]
+ fn print_concat() {
+ roundtrip("ab");
+ roundtrip("abcde");
+ roundtrip("a(bcd)ef");
+ }
+
+ #[test]
+ fn print_alternation() {
+ roundtrip("a|b");
+ roundtrip("a|b|c|d|e");
+ roundtrip("|a|b|c|d|e");
+ roundtrip("|a|b|c|d|e|");
+ roundtrip("a(b|c|d)|e|f");
+ }
+
+ #[test]
+ fn print_assertion() {
+ roundtrip(r"^");
+ roundtrip(r"$");
+ roundtrip(r"\A");
+ roundtrip(r"\z");
+ roundtrip(r"\b");
+ roundtrip(r"\B");
+ }
+
+ #[test]
+ fn print_repetition() {
+ roundtrip("a?");
+ roundtrip("a??");
+ roundtrip("a*");
+ roundtrip("a*?");
+ roundtrip("a+");
+ roundtrip("a+?");
+ roundtrip("a{5}");
+ roundtrip("a{5}?");
+ roundtrip("a{5,}");
+ roundtrip("a{5,}?");
+ roundtrip("a{5,10}");
+ roundtrip("a{5,10}?");
+ }
+
+ #[test]
+ fn print_flags() {
+ roundtrip("(?i)");
+ roundtrip("(?-i)");
+ roundtrip("(?s-i)");
+ roundtrip("(?-si)");
+ roundtrip("(?siUmux)");
+ }
+
+ #[test]
+ fn print_group() {
+ roundtrip("(?i:a)");
+ roundtrip("(?P<foo>a)");
+ roundtrip("(a)");
+ }
+
+ #[test]
+ fn print_class() {
+ roundtrip(r"[abc]");
+ roundtrip(r"[a-z]");
+ roundtrip(r"[^a-z]");
+ roundtrip(r"[a-z0-9]");
+ roundtrip(r"[-a-z0-9]");
+ roundtrip(r"[-a-z0-9]");
+ roundtrip(r"[a-z0-9---]");
+ roundtrip(r"[a-z&&m-n]");
+ roundtrip(r"[[a-z&&m-n]]");
+ roundtrip(r"[a-z--m-n]");
+ roundtrip(r"[a-z~~m-n]");
+ roundtrip(r"[a-z[0-9]]");
+ roundtrip(r"[a-z[^0-9]]");
+
+ roundtrip(r"\d");
+ roundtrip(r"\D");
+ roundtrip(r"\s");
+ roundtrip(r"\S");
+ roundtrip(r"\w");
+ roundtrip(r"\W");
+
+ roundtrip(r"[[:alnum:]]");
+ roundtrip(r"[[:^alnum:]]");
+ roundtrip(r"[[:alpha:]]");
+ roundtrip(r"[[:^alpha:]]");
+ roundtrip(r"[[:ascii:]]");
+ roundtrip(r"[[:^ascii:]]");
+ roundtrip(r"[[:blank:]]");
+ roundtrip(r"[[:^blank:]]");
+ roundtrip(r"[[:cntrl:]]");
+ roundtrip(r"[[:^cntrl:]]");
+ roundtrip(r"[[:digit:]]");
+ roundtrip(r"[[:^digit:]]");
+ roundtrip(r"[[:graph:]]");
+ roundtrip(r"[[:^graph:]]");
+ roundtrip(r"[[:lower:]]");
+ roundtrip(r"[[:^lower:]]");
+ roundtrip(r"[[:print:]]");
+ roundtrip(r"[[:^print:]]");
+ roundtrip(r"[[:punct:]]");
+ roundtrip(r"[[:^punct:]]");
+ roundtrip(r"[[:space:]]");
+ roundtrip(r"[[:^space:]]");
+ roundtrip(r"[[:upper:]]");
+ roundtrip(r"[[:^upper:]]");
+ roundtrip(r"[[:word:]]");
+ roundtrip(r"[[:^word:]]");
+ roundtrip(r"[[:xdigit:]]");
+ roundtrip(r"[[:^xdigit:]]");
+
+ roundtrip(r"\pL");
+ roundtrip(r"\PL");
+ roundtrip(r"\p{L}");
+ roundtrip(r"\P{L}");
+ roundtrip(r"\p{X=Y}");
+ roundtrip(r"\P{X=Y}");
+ roundtrip(r"\p{X:Y}");
+ roundtrip(r"\P{X:Y}");
+ roundtrip(r"\p{X!=Y}");
+ roundtrip(r"\P{X!=Y}");
+ }
+}
diff --git a/src/ast/visitor.rs b/src/ast/visitor.rs
new file mode 100644
index 0000000..3eaa4b0
--- /dev/null
+++ b/src/ast/visitor.rs
@@ -0,0 +1,519 @@
+use std::fmt;
+
+use ast::{self, Ast};
+
+/// A trait for visiting an abstract syntax tree (AST) in depth first order.
+///
+/// The principle aim of this trait is to enable callers to perform case
+/// analysis on an abstract syntax tree without necessarily using recursion.
+/// In particular, this permits callers to do case analysis with constant stack
+/// usage, which can be important since the size of an abstract syntax tree
+/// may be proportional to end user input.
+///
+/// Typical usage of this trait involves providing an implementation and then
+/// running it using the [`visit`](fn.visit.html) function.
+///
+/// Note that the abstract syntax tree for a regular expression is quite
+/// complex. Unless you specifically need it, you might be able to use the
+/// much simpler
+/// [high-level intermediate representation](../hir/struct.Hir.html)
+/// and its
+/// [corresponding `Visitor` trait](../hir/trait.Visitor.html)
+/// instead.
+pub trait Visitor {
+ /// The result of visiting an AST.
+ type Output;
+ /// An error that visiting an AST might return.
+ type Err;
+
+ /// All implementors of `Visitor` must provide a `finish` method, which
+ /// yields the result of visiting the AST or an error.
+ fn finish(self) -> Result<Self::Output, Self::Err>;
+
+ /// This method is called before beginning traversal of the AST.
+ fn start(&mut self) {}
+
+ /// This method is called on an `Ast` before descending into child `Ast`
+ /// nodes.
+ fn visit_pre(&mut self, _ast: &Ast) -> Result<(), Self::Err> {
+ Ok(())
+ }
+
+ /// This method is called on an `Ast` after descending all of its child
+ /// `Ast` nodes.
+ fn visit_post(&mut self, _ast: &Ast) -> Result<(), Self::Err> {
+ Ok(())
+ }
+
+ /// This method is called between child nodes of an
+ /// [`Alternation`](struct.Alternation.html).
+ fn visit_alternation_in(&mut self) -> Result<(), Self::Err> {
+ Ok(())
+ }
+
+ /// This method is called on every
+ /// [`ClassSetItem`](enum.ClassSetItem.html)
+ /// before descending into child nodes.
+ fn visit_class_set_item_pre(
+ &mut self,
+ _ast: &ast::ClassSetItem,
+ ) -> Result<(), Self::Err> {
+ Ok(())
+ }
+
+ /// This method is called on every
+ /// [`ClassSetItem`](enum.ClassSetItem.html)
+ /// after descending into child nodes.
+ fn visit_class_set_item_post(
+ &mut self,
+ _ast: &ast::ClassSetItem,
+ ) -> Result<(), Self::Err> {
+ Ok(())
+ }
+
+ /// This method is called on every
+ /// [`ClassSetBinaryOp`](struct.ClassSetBinaryOp.html)
+ /// before descending into child nodes.
+ fn visit_class_set_binary_op_pre(
+ &mut self,
+ _ast: &ast::ClassSetBinaryOp,
+ ) -> Result<(), Self::Err> {
+ Ok(())
+ }
+
+ /// This method is called on every
+ /// [`ClassSetBinaryOp`](struct.ClassSetBinaryOp.html)
+ /// after descending into child nodes.
+ fn visit_class_set_binary_op_post(
+ &mut self,
+ _ast: &ast::ClassSetBinaryOp,
+ ) -> Result<(), Self::Err> {
+ Ok(())
+ }
+
+ /// This method is called between the left hand and right hand child nodes
+ /// of a [`ClassSetBinaryOp`](struct.ClassSetBinaryOp.html).
+ fn visit_class_set_binary_op_in(
+ &mut self,
+ _ast: &ast::ClassSetBinaryOp,
+ ) -> Result<(), Self::Err> {
+ Ok(())
+ }
+}
+
+/// Executes an implementation of `Visitor` in constant stack space.
+///
+/// This function will visit every node in the given `Ast` while calling the
+/// appropriate methods provided by the
+/// [`Visitor`](trait.Visitor.html) trait.
+///
+/// The primary use case for this method is when one wants to perform case
+/// analysis over an `Ast` without using a stack size proportional to the depth
+/// of the `Ast`. Namely, this method will instead use constant stack size, but
+/// will use heap space proportional to the size of the `Ast`. This may be
+/// desirable in cases where the size of `Ast` is proportional to end user
+/// input.
+///
+/// If the visitor returns an error at any point, then visiting is stopped and
+/// the error is returned.
+pub fn visit<V: Visitor>(ast: &Ast, visitor: V) -> Result<V::Output, V::Err> {
+ HeapVisitor::new().visit(ast, visitor)
+}
+
+/// HeapVisitor visits every item in an `Ast` recursively using constant stack
+/// size and a heap size proportional to the size of the `Ast`.
+struct HeapVisitor<'a> {
+ /// A stack of `Ast` nodes. This is roughly analogous to the call stack
+ /// used in a typical recursive visitor.
+ stack: Vec<(&'a Ast, Frame<'a>)>,
+ /// Similar to the `Ast` stack above, but is used only for character
+ /// classes. In particular, character classes embed their own mini
+ /// recursive syntax.
+ stack_class: Vec<(ClassInduct<'a>, ClassFrame<'a>)>,
+}
+
+/// Represents a single stack frame while performing structural induction over
+/// an `Ast`.
+enum Frame<'a> {
+ /// A stack frame allocated just before descending into a repetition
+ /// operator's child node.
+ Repetition(&'a ast::Repetition),
+ /// A stack frame allocated just before descending into a group's child
+ /// node.
+ Group(&'a ast::Group),
+ /// The stack frame used while visiting every child node of a concatenation
+ /// of expressions.
+ Concat {
+ /// The child node we are currently visiting.
+ head: &'a Ast,
+ /// The remaining child nodes to visit (which may be empty).
+ tail: &'a [Ast],
+ },
+ /// The stack frame used while visiting every child node of an alternation
+ /// of expressions.
+ Alternation {
+ /// The child node we are currently visiting.
+ head: &'a Ast,
+ /// The remaining child nodes to visit (which may be empty).
+ tail: &'a [Ast],
+ },
+}
+
+/// Represents a single stack frame while performing structural induction over
+/// a character class.
+enum ClassFrame<'a> {
+ /// The stack frame used while visiting every child node of a union of
+ /// character class items.
+ Union {
+ /// The child node we are currently visiting.
+ head: &'a ast::ClassSetItem,
+ /// The remaining child nodes to visit (which may be empty).
+ tail: &'a [ast::ClassSetItem],
+ },
+ /// The stack frame used while a binary class operation.
+ Binary { op: &'a ast::ClassSetBinaryOp },
+ /// A stack frame allocated just before descending into a binary operator's
+ /// left hand child node.
+ BinaryLHS {
+ op: &'a ast::ClassSetBinaryOp,
+ lhs: &'a ast::ClassSet,
+ rhs: &'a ast::ClassSet,
+ },
+ /// A stack frame allocated just before descending into a binary operator's
+ /// right hand child node.
+ BinaryRHS { op: &'a ast::ClassSetBinaryOp, rhs: &'a ast::ClassSet },
+}
+
+/// A representation of the inductive step when performing structural induction
+/// over a character class.
+///
+/// Note that there is no analogous explicit type for the inductive step for
+/// `Ast` nodes because the inductive step is just an `Ast`. For character
+/// classes, the inductive step can produce one of two possible child nodes:
+/// an item or a binary operation. (An item cannot be a binary operation
+/// because that would imply binary operations can be unioned in the concrete
+/// syntax, which is not possible.)
+enum ClassInduct<'a> {
+ Item(&'a ast::ClassSetItem),
+ BinaryOp(&'a ast::ClassSetBinaryOp),
+}
+
+impl<'a> HeapVisitor<'a> {
+ fn new() -> HeapVisitor<'a> {
+ HeapVisitor { stack: vec![], stack_class: vec![] }
+ }
+
+ fn visit<V: Visitor>(
+ &mut self,
+ mut ast: &'a Ast,
+ mut visitor: V,
+ ) -> Result<V::Output, V::Err> {
+ self.stack.clear();
+ self.stack_class.clear();
+
+ visitor.start();
+ loop {
+ visitor.visit_pre(ast)?;
+ if let Some(x) = self.induct(ast, &mut visitor)? {
+ let child = x.child();
+ self.stack.push((ast, x));
+ ast = child;
+ continue;
+ }
+ // No induction means we have a base case, so we can post visit
+ // it now.
+ visitor.visit_post(ast)?;
+
+ // At this point, we now try to pop our call stack until it is
+ // either empty or we hit another inductive case.
+ loop {
+ let (post_ast, frame) = match self.stack.pop() {
+ None => return visitor.finish(),
+ Some((post_ast, frame)) => (post_ast, frame),
+ };
+ // If this is a concat/alternate, then we might have additional
+ // inductive steps to process.
+ if let Some(x) = self.pop(frame) {
+ if let Frame::Alternation { .. } = x {
+ visitor.visit_alternation_in()?;
+ }
+ ast = x.child();
+ self.stack.push((post_ast, x));
+ break;
+ }
+ // Otherwise, we've finished visiting all the child nodes for
+ // this AST, so we can post visit it now.
+ visitor.visit_post(post_ast)?;
+ }
+ }
+ }
+
+ /// Build a stack frame for the given AST if one is needed (which occurs if
+ /// and only if there are child nodes in the AST). Otherwise, return None.
+ ///
+ /// If this visits a class, then the underlying visitor implementation may
+ /// return an error which will be passed on here.
+ fn induct<V: Visitor>(
+ &mut self,
+ ast: &'a Ast,
+ visitor: &mut V,
+ ) -> Result<Option<Frame<'a>>, V::Err> {
+ Ok(match *ast {
+ Ast::Class(ast::Class::Bracketed(ref x)) => {
+ self.visit_class(x, visitor)?;
+ None
+ }
+ Ast::Repetition(ref x) => Some(Frame::Repetition(x)),
+ Ast::Group(ref x) => Some(Frame::Group(x)),
+ Ast::Concat(ref x) if x.asts.is_empty() => None,
+ Ast::Concat(ref x) => {
+ Some(Frame::Concat { head: &x.asts[0], tail: &x.asts[1..] })
+ }
+ Ast::Alternation(ref x) if x.asts.is_empty() => None,
+ Ast::Alternation(ref x) => Some(Frame::Alternation {
+ head: &x.asts[0],
+ tail: &x.asts[1..],
+ }),
+ _ => None,
+ })
+ }
+
+ /// Pops the given frame. If the frame has an additional inductive step,
+ /// then return it, otherwise return `None`.
+ fn pop(&self, induct: Frame<'a>) -> Option<Frame<'a>> {
+ match induct {
+ Frame::Repetition(_) => None,
+ Frame::Group(_) => None,
+ Frame::Concat { tail, .. } => {
+ if tail.is_empty() {
+ None
+ } else {
+ Some(Frame::Concat { head: &tail[0], tail: &tail[1..] })
+ }
+ }
+ Frame::Alternation { tail, .. } => {
+ if tail.is_empty() {
+ None
+ } else {
+ Some(Frame::Alternation {
+ head: &tail[0],
+ tail: &tail[1..],
+ })
+ }
+ }
+ }
+ }
+
+ fn visit_class<V: Visitor>(
+ &mut self,
+ ast: &'a ast::ClassBracketed,
+ visitor: &mut V,
+ ) -> Result<(), V::Err> {
+ let mut ast = ClassInduct::from_bracketed(ast);
+ loop {
+ self.visit_class_pre(&ast, visitor)?;
+ if let Some(x) = self.induct_class(&ast) {
+ let child = x.child();
+ self.stack_class.push((ast, x));
+ ast = child;
+ continue;
+ }
+ self.visit_class_post(&ast, visitor)?;
+
+ // At this point, we now try to pop our call stack until it is
+ // either empty or we hit another inductive case.
+ loop {
+ let (post_ast, frame) = match self.stack_class.pop() {
+ None => return Ok(()),
+ Some((post_ast, frame)) => (post_ast, frame),
+ };
+ // If this is a union or a binary op, then we might have
+ // additional inductive steps to process.
+ if let Some(x) = self.pop_class(frame) {
+ if let ClassFrame::BinaryRHS { ref op, .. } = x {
+ visitor.visit_class_set_binary_op_in(op)?;
+ }
+ ast = x.child();
+ self.stack_class.push((post_ast, x));
+ break;
+ }
+ // Otherwise, we've finished visiting all the child nodes for
+ // this class node, so we can post visit it now.
+ self.visit_class_post(&post_ast, visitor)?;
+ }
+ }
+ }
+
+ /// Call the appropriate `Visitor` methods given an inductive step.
+ fn visit_class_pre<V: Visitor>(
+ &self,
+ ast: &ClassInduct<'a>,
+ visitor: &mut V,
+ ) -> Result<(), V::Err> {
+ match *ast {
+ ClassInduct::Item(item) => {
+ visitor.visit_class_set_item_pre(item)?;
+ }
+ ClassInduct::BinaryOp(op) => {
+ visitor.visit_class_set_binary_op_pre(op)?;
+ }
+ }
+ Ok(())
+ }
+
+ /// Call the appropriate `Visitor` methods given an inductive step.
+ fn visit_class_post<V: Visitor>(
+ &self,
+ ast: &ClassInduct<'a>,
+ visitor: &mut V,
+ ) -> Result<(), V::Err> {
+ match *ast {
+ ClassInduct::Item(item) => {
+ visitor.visit_class_set_item_post(item)?;
+ }
+ ClassInduct::BinaryOp(op) => {
+ visitor.visit_class_set_binary_op_post(op)?;
+ }
+ }
+ Ok(())
+ }
+
+ /// Build a stack frame for the given class node if one is needed (which
+ /// occurs if and only if there are child nodes). Otherwise, return None.
+ fn induct_class(&self, ast: &ClassInduct<'a>) -> Option<ClassFrame<'a>> {
+ match *ast {
+ ClassInduct::Item(&ast::ClassSetItem::Bracketed(ref x)) => {
+ match x.kind {
+ ast::ClassSet::Item(ref item) => {
+ Some(ClassFrame::Union { head: item, tail: &[] })
+ }
+ ast::ClassSet::BinaryOp(ref op) => {
+ Some(ClassFrame::Binary { op: op })
+ }
+ }
+ }
+ ClassInduct::Item(&ast::ClassSetItem::Union(ref x)) => {
+ if x.items.is_empty() {
+ None
+ } else {
+ Some(ClassFrame::Union {
+ head: &x.items[0],
+ tail: &x.items[1..],
+ })
+ }
+ }
+ ClassInduct::BinaryOp(op) => Some(ClassFrame::BinaryLHS {
+ op: op,
+ lhs: &op.lhs,
+ rhs: &op.rhs,
+ }),
+ _ => None,
+ }
+ }
+
+ /// Pops the given frame. If the frame has an additional inductive step,
+ /// then return it, otherwise return `None`.
+ fn pop_class(&self, induct: ClassFrame<'a>) -> Option<ClassFrame<'a>> {
+ match induct {
+ ClassFrame::Union { tail, .. } => {
+ if tail.is_empty() {
+ None
+ } else {
+ Some(ClassFrame::Union {
+ head: &tail[0],
+ tail: &tail[1..],
+ })
+ }
+ }
+ ClassFrame::Binary { .. } => None,
+ ClassFrame::BinaryLHS { op, rhs, .. } => {
+ Some(ClassFrame::BinaryRHS { op: op, rhs: rhs })
+ }
+ ClassFrame::BinaryRHS { .. } => None,
+ }
+ }
+}
+
+impl<'a> Frame<'a> {
+ /// Perform the next inductive step on this frame and return the next
+ /// child AST node to visit.
+ fn child(&self) -> &'a Ast {
+ match *self {
+ Frame::Repetition(rep) => &rep.ast,
+ Frame::Group(group) => &group.ast,
+ Frame::Concat { head, .. } => head,
+ Frame::Alternation { head, .. } => head,
+ }
+ }
+}
+
+impl<'a> ClassFrame<'a> {
+ /// Perform the next inductive step on this frame and return the next
+ /// child class node to visit.
+ fn child(&self) -> ClassInduct<'a> {
+ match *self {
+ ClassFrame::Union { head, .. } => ClassInduct::Item(head),
+ ClassFrame::Binary { op, .. } => ClassInduct::BinaryOp(op),
+ ClassFrame::BinaryLHS { ref lhs, .. } => {
+ ClassInduct::from_set(lhs)
+ }
+ ClassFrame::BinaryRHS { ref rhs, .. } => {
+ ClassInduct::from_set(rhs)
+ }
+ }
+ }
+}
+
+impl<'a> ClassInduct<'a> {
+ fn from_bracketed(ast: &'a ast::ClassBracketed) -> ClassInduct<'a> {
+ ClassInduct::from_set(&ast.kind)
+ }
+
+ fn from_set(ast: &'a ast::ClassSet) -> ClassInduct<'a> {
+ match *ast {
+ ast::ClassSet::Item(ref item) => ClassInduct::Item(item),
+ ast::ClassSet::BinaryOp(ref op) => ClassInduct::BinaryOp(op),
+ }
+ }
+}
+
+impl<'a> fmt::Debug for ClassFrame<'a> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ let x = match *self {
+ ClassFrame::Union { .. } => "Union",
+ ClassFrame::Binary { .. } => "Binary",
+ ClassFrame::BinaryLHS { .. } => "BinaryLHS",
+ ClassFrame::BinaryRHS { .. } => "BinaryRHS",
+ };
+ write!(f, "{}", x)
+ }
+}
+
+impl<'a> fmt::Debug for ClassInduct<'a> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ let x = match *self {
+ ClassInduct::Item(it) => match *it {
+ ast::ClassSetItem::Empty(_) => "Item(Empty)",
+ ast::ClassSetItem::Literal(_) => "Item(Literal)",
+ ast::ClassSetItem::Range(_) => "Item(Range)",
+ ast::ClassSetItem::Ascii(_) => "Item(Ascii)",
+ ast::ClassSetItem::Perl(_) => "Item(Perl)",
+ ast::ClassSetItem::Unicode(_) => "Item(Unicode)",
+ ast::ClassSetItem::Bracketed(_) => "Item(Bracketed)",
+ ast::ClassSetItem::Union(_) => "Item(Union)",
+ },
+ ClassInduct::BinaryOp(it) => match it.kind {
+ ast::ClassSetBinaryOpKind::Intersection => {
+ "BinaryOp(Intersection)"
+ }
+ ast::ClassSetBinaryOpKind::Difference => {
+ "BinaryOp(Difference)"
+ }
+ ast::ClassSetBinaryOpKind::SymmetricDifference => {
+ "BinaryOp(SymmetricDifference)"
+ }
+ },
+ };
+ write!(f, "{}", x)
+ }
+}