Adding upstream version 110.0.1.upstream/110.0.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

4 files changed, 8517 insertions, 0 deletions

diff --git a/third_party/rust/regex-syntax/src/ast/mod.rs b/third_party/rust/regex-syntax/src/ast/mod.rs
new file mode 100644
index 0000000000..387ea3a698
--- /dev/null
+++ b/third_party/rust/regex-syntax/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 crate::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 not 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 {
+        crate::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, 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, line, 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 crate::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/third_party/rust/regex-syntax/src/ast/parse.rs b/third_party/rust/regex-syntax/src/ast/parse.rs
new file mode 100644
index 0000000000..6e9c9aca06
--- /dev/null
+++ b/third_party/rust/regex-syntax/src/ast/parse.rs
@@ -0,0 +1,5930 @@
+/*!
+This module provides a regular expression parser.
+*/
+
+use std::borrow::Borrow;
+use std::cell::{Cell, RefCell};
+use std::mem;
+use std::result;
+
+use crate::ast::{self, Ast, Position, Span};
+use crate::either::Either;
+
+use crate::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 crate::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 must be alphabetic or underscore).
+fn is_capture_char(c: char, first: bool) -> bool {
+    c == '_'
+        || (!first
+            && (('0' <= c && c <= '9') || c == '.' || c == '[' || c == ']'))
+        || ('A' <= c && c <= 'Z')
+        || ('a' <= c && 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
+    /// length 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 insignificant 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
+    /// `ParserBuilder`. It is used when resetting 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, 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, pattern: self.pattern().to_string(), 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, line, 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,
+                        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() {
+            if let ClassState::Open { ref set, .. } = *state {
+                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,
+            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,
+            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 parser 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,
+            },
+            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 parser 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,
+            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,
+                }))
+            } 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,
+                });
+                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,
+                kind: ast::LiteralKind::Punctuation,
+                c,
+            }));
+        }
+        let special = |kind, c| {
+            Ok(Primitive::Literal(ast::Literal {
+                span,
+                kind: ast::LiteralKind::Special(kind),
+                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,
+                kind: ast::AssertionKind::StartText,
+            })),
+            'z' => Ok(Primitive::Assertion(ast::Assertion {
+                span,
+                kind: ast::AssertionKind::EndText,
+            })),
+            'b' => Ok(Primitive::Assertion(ast::Assertion {
+                span,
+                kind: ast::AssertionKind::WordBoundary,
+            })),
+            'B' => Ok(Primitive::Assertion(ast::Assertion {
+                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,
+        }
+    }
+
+    /// 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,
+            }),
+        }
+    }
+
+    /// 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,
+            }),
+        }
+    }
+
+    /// 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, start),
+                    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,
+            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,
+            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,
+            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, kind, 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> {
+    /// 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, 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 crate::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,
+            kind: ast::LiteralKind::Punctuation,
+            c,
+        })
+    }
+
+    /// Create a verbatim literal with the given span.
+    fn lit_with(c: char, span: Span) -> Ast {
+        Ast::Literal(ast::Literal {
+            span,
+            kind: ast::LiteralKind::Verbatim,
+            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, 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 })
+    }
+
+    /// 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,
+            },
+        })
+    }
+
+    #[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<a_1>z)").parse(),
+            Ok(Ast::Group(ast::Group {
+                span: span(0..10),
+                kind: ast::GroupKind::CaptureName(ast::CaptureName {
+                    span: span(4..7),
+                    name: s("a_1"),
+                    index: 1,
+                }),
+                ast: Box::new(lit('z', 8)),
+            }))
+        );
+
+        assert_eq!(
+            parser("(?P<a.1>z)").parse(),
+            Ok(Ast::Group(ast::Group {
+                span: span(0..10),
+                kind: ast::GroupKind::CaptureName(ast::CaptureName {
+                    span: span(4..7),
+                    name: s("a.1"),
+                    index: 1,
+                }),
+                ast: Box::new(lit('z', 8)),
+            }))
+        );
+
+        assert_eq!(
+            parser("(?P<a[1]>z)").parse(),
+            Ok(Ast::Group(ast::Group {
+                span: span(0..11),
+                kind: ast::GroupKind::CaptureName(ast::CaptureName {
+                    span: span(4..8),
+                    name: s("a[1]"),
+                    index: 1,
+                }),
+                ast: Box::new(lit('z', 9)),
+            }))
+        );
+
+        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,
+                }))
+            );
+        }
+        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,
+                }))
+            );
+        }
+
+        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,
+                }))
+            );
+        }
+
+        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, items })
+        }
+
+        fn intersection(
+            span: Span,
+            lhs: ast::ClassSet,
+            rhs: ast::ClassSet,
+        ) -> ast::ClassSet {
+            ast::ClassSet::BinaryOp(ast::ClassSetBinaryOp {
+                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,
+                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,
+                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,
+                kind: ast::LiteralKind::Verbatim,
+                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,
+                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, kind: ast::ClassAsciiKind::Alnum, negated }
+        }
+
+        fn lower(span: Span, negated: bool) -> ast::ClassAscii {
+            ast::ClassAscii { span, kind: ast::ClassAsciiKind::Lower, 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..0),
+                kind: ast::ErrorKind::ClassUnclosed,
+            }
+        );
+        assert_eq!(
+            parser("[--").parse_set_class_open().unwrap_err(),
+            TestError {
+                span: span(0..0),
+                kind: ast::ErrorKind::ClassUnclosed,
+            }
+        );
+
+        // See: https://github.com/rust-lang/regex/issues/792
+        assert_eq!(
+            parser("(?x)[-#]").parse_with_comments().unwrap_err(),
+            TestError {
+                span: span(4..4),
+                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/third_party/rust/regex-syntax/src/ast/print.rs b/third_party/rust/regex-syntax/src/ast/print.rs
new file mode 100644
index 0000000000..045de2eaf2
--- /dev/null
+++ b/third_party/rust/regex-syntax/src/ast/print.rs
@@ -0,0 +1,568 @@
+/*!
+This module provides a regular expression printer for `Ast`.
+*/
+
+use std::fmt;
+
+use crate::ast::visitor::{self, Visitor};
+use crate::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 { wtr })
+    }
+}
+
+#[derive(Debug)]
+struct Writer<W> {
+    wtr: W,
+}
+
+impl<W: fmt::Write> Visitor for Writer<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 crate::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 crate::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<W: fmt::Write> Writer<W> {
+    fn fmt_group_pre(&mut self, ast: &ast::Group) -> fmt::Result {
+        use crate::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 crate::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 crate::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 crate::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 crate::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 crate::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 crate::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 crate::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 crate::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 crate::ast::ClassUnicodeKind::*;
+        use crate::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 crate::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/third_party/rust/regex-syntax/src/ast/visitor.rs b/third_party/rust/regex-syntax/src/ast/visitor.rs
new file mode 100644
index 0000000000..78ee487cff
--- /dev/null
+++ b/third_party/rust/regex-syntax/src/ast/visitor.rs
@@ -0,0 +1,517 @@
+use std::fmt;
+
+use crate::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 })
+                    }
+                }
+            }
+            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, 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, 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)
+    }
+}