use core::cell::{Cell, RefCell};

use alloc::{

    boxed::Box,

    string::{String, ToString},

    vec,

    vec::Vec,

};

use crate::{

    error::Error,

    hir::{self, Config, Flags, Hir, HirKind},

};

// These are all of the errors that can occur while parsing a regex. Unlike

// regex-syntax, our errors are not particularly great. They are just enough

// to get a general sense of what went wrong. But in exchange, the error

// reporting mechanism is *much* simpler than what's in regex-syntax.

//

// By convention, we use each of these messages in exactly one place. That

// way, every branch that leads to an error has a unique message. This in turn

// means that given a message, one can precisely identify which part of the

// parser reported it.

//

// Finally, we give names to each message so that we can reference them in

// tests.

const ERR_TOO_MUCH_NESTING: &str = "pattern has too much nesting";

const ERR_TOO_MANY_CAPTURES: &str = "too many capture groups";

const ERR_DUPLICATE_CAPTURE_NAME: &str = "duplicate capture group name";

const ERR_UNCLOSED_GROUP: &str = "found open group without closing ')'";

const ERR_UNCLOSED_GROUP_QUESTION: &str =

    "expected closing ')', but got end of pattern";

const ERR_UNOPENED_GROUP: &str = "found closing ')' without matching '('";

const ERR_LOOK_UNSUPPORTED: &str = "look-around is not supported";

const ERR_EMPTY_FLAGS: &str = "empty flag directive '(?)' is not allowed";

const ERR_MISSING_GROUP_NAME: &str =

    "expected capture group name, but got end of pattern";

const ERR_INVALID_GROUP_NAME: &str = "invalid group name";

const ERR_UNCLOSED_GROUP_NAME: &str =

    "expected end of capture group name, but got end of pattern";

const ERR_EMPTY_GROUP_NAME: &str = "empty capture group names are not allowed";

const ERR_FLAG_UNRECOGNIZED: &str = "unrecognized inline flag";

const ERR_FLAG_REPEATED_NEGATION: &str =

    "inline flag negation cannot be repeated";

const ERR_FLAG_DUPLICATE: &str = "duplicate inline flag is not allowed";

const ERR_FLAG_UNEXPECTED_EOF: &str =

    "expected ':' or ')' to end inline flags, but got end of pattern";

const ERR_FLAG_DANGLING_NEGATION: &str =

    "inline flags cannot end with negation directive";

const ERR_DECIMAL_NO_DIGITS: &str =

    "expected decimal number, but found no digits";

const ERR_DECIMAL_INVALID: &str = "got invalid decimal number";

const ERR_HEX_BRACE_INVALID_DIGIT: &str =

    "expected hexadecimal number in braces, but got non-hex digit";

const ERR_HEX_BRACE_UNEXPECTED_EOF: &str =

    "expected hexadecimal number, but saw end of pattern before closing brace";

const ERR_HEX_BRACE_EMPTY: &str =

    "expected hexadecimal number in braces, but got no digits";

const ERR_HEX_BRACE_INVALID: &str = "got invalid hexadecimal number in braces";

const ERR_HEX_FIXED_UNEXPECTED_EOF: &str =

    "expected fixed length hexadecimal number, but saw end of pattern first";

const ERR_HEX_FIXED_INVALID_DIGIT: &str =

    "expected fixed length hexadecimal number, but got non-hex digit";

const ERR_HEX_FIXED_INVALID: &str =

    "got invalid fixed length hexadecimal number";

const ERR_HEX_UNEXPECTED_EOF: &str =

    "expected hexadecimal number, but saw end of pattern first";

const ERR_ESCAPE_UNEXPECTED_EOF: &str =

    "saw start of escape sequence, but saw end of pattern before it finished";

const ERR_BACKREF_UNSUPPORTED: &str = "backreferences are not supported";

const ERR_UNICODE_CLASS_UNSUPPORTED: &str =

    "Unicode character classes are not supported";

const ERR_ESCAPE_UNRECOGNIZED: &str = "unrecognized escape sequence";

const ERR_POSIX_CLASS_UNRECOGNIZED: &str =

    "unrecognized POSIX character class";

const ERR_UNCOUNTED_REP_SUB_MISSING: &str =

    "uncounted repetition operator must be applied to a sub-expression";

const ERR_COUNTED_REP_SUB_MISSING: &str =

    "counted repetition operator must be applied to a sub-expression";

const ERR_COUNTED_REP_UNCLOSED: &str =

    "found unclosed counted repetition operator";

const ERR_COUNTED_REP_MIN_UNCLOSED: &str =

    "found incomplete and unclosed counted repetition operator";

const ERR_COUNTED_REP_COMMA_UNCLOSED: &str =

    "found counted repetition operator with a comma that is unclosed";

const ERR_COUNTED_REP_MIN_MAX_UNCLOSED: &str =

    "found counted repetition with min and max that is unclosed";

const ERR_COUNTED_REP_INVALID: &str =

    "expected closing brace for counted repetition, but got something else";

const ERR_COUNTED_REP_INVALID_RANGE: &str =

    "found counted repetition with a min bigger than its max";

const ERR_CLASS_UNCLOSED_AFTER_ITEM: &str =

    "non-empty character class has no closing bracket";

const ERR_CLASS_INVALID_RANGE_ITEM: &str =

    "character class ranges must start and end with a single character";

const ERR_CLASS_INVALID_ITEM: &str =

    "invalid escape sequence in character class";

const ERR_CLASS_UNCLOSED_AFTER_DASH: &str =

    "non-empty character class has no closing bracket after dash";

const ERR_CLASS_UNCLOSED_AFTER_NEGATION: &str =

    "negated character class has no closing bracket";

const ERR_CLASS_UNCLOSED_AFTER_CLOSING: &str =

    "character class begins with literal ']' but has no closing bracket";

const ERR_CLASS_INVALID_RANGE: &str = "invalid range in character class";

const ERR_CLASS_UNCLOSED: &str = "found unclosed character class";

const ERR_CLASS_NEST_UNSUPPORTED: &str =

    "nested character classes are not supported";

const ERR_CLASS_INTERSECTION_UNSUPPORTED: &str =

    "character class intersection is not supported";

const ERR_CLASS_DIFFERENCE_UNSUPPORTED: &str =

    "character class difference is not supported";

const ERR_CLASS_SYMDIFFERENCE_UNSUPPORTED: &str =

    "character class symmetric difference is not supported";

const ERR_SPECIAL_WORD_BOUNDARY_UNCLOSED: &str =

    "special word boundary assertion is unclosed or has an invalid character";

const ERR_SPECIAL_WORD_BOUNDARY_UNRECOGNIZED: &str =

    "special word boundary assertion is unrecognized";

const ERR_SPECIAL_WORD_OR_REP_UNEXPECTED_EOF: &str =

    "found start of special word boundary or repetition without an end";

/// 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`].

#[derive(Clone, Debug)]

pub(super) struct Parser<'a> {

    /// The configuration of the parser as given by the caller.

    config: Config,

    /// The pattern we're parsing as given by the caller.

    pattern: &'a str,

    /// The call depth of the parser. This is incremented for each

    /// sub-expression parsed. Its peak value is the maximum nesting of the

    /// pattern.

    depth: Cell<u32>,

    /// The current position of the parser.

    pos: Cell<usize>,

    /// The current codepoint of the parser. The codepoint corresponds to the

    /// codepoint encoded in `pattern` beginning at `pos`.

    ///

    /// This is `None` if and only if `pos == pattern.len()`.

    char: Cell<Option<char>>,

    /// The current capture index.

    capture_index: Cell<u32>,

    /// The flags that are currently set.

    flags: RefCell<Flags>,

    /// 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<String>>,

}

/// The constructor and a variety of helper routines.

impl<'a> Parser<'a> {

    /// Build a parser from this configuration with the given pattern.

    pub(super) fn new(config: Config, pattern: &'a str) -> Parser<'a> {

        Parser {

            config,

            pattern,

            depth: Cell::new(0),

            pos: Cell::new(0),

            char: Cell::new(pattern.chars().next()),

            capture_index: Cell::new(0),

            flags: RefCell::new(config.flags),

            capture_names: RefCell::new(vec![]),

        }

    }

    /// Returns the full pattern string that we're parsing.

    fn pattern(&self) -> &str {

        self.pattern

    }

    /// Return the current byte offset of the parser.

    ///

    /// The offset starts at `0` from the beginning of the regular expression

    /// pattern string.

    fn pos(&self) -> usize {

        self.pos.get()

    }

    /// Increments the call depth of the parser.

    ///

    /// If the call depth would exceed the configured nest limit, then this

    /// returns an error.

    ///

    /// This returns the old depth.

    fn increment_depth(&self) -> Result<u32, Error> {

        let old = self.depth.get();

        if old > self.config.nest_limit {

            return Err(Error::new(ERR_TOO_MUCH_NESTING));

        }

        // OK because our depth starts at 0, and we return an error if it

        // ever reaches the limit. So the call depth can never exceed u32::MAX.

        let new = old.checked_add(1).unwrap();

        self.depth.set(new);

        Ok(old)

    }

    /// Decrements the call depth of the parser.

    ///

    /// This panics if the current depth is 0.

    fn decrement_depth(&self) {

        let old = self.depth.get();

        // If this fails then the caller has a bug in how they're incrementing

        // and decrementing the depth of the parser's call stack.

        let new = old.checked_sub(1).unwrap();

        self.depth.set(new);

    }

    /// Return the codepoint at the current position of the parser.

    ///

    /// This panics if the parser is positioned at the end of the pattern.

    fn char(&self) -> char {

        self.char.get().expect("codepoint, but parser is done")

    }

    /// Returns true if the next call to `bump` would return false.

    fn is_done(&self) -> bool {

        self.pos() == self.pattern.len()

    }

    /// Returns the flags that are current set for this regex.

    fn flags(&self) -> Flags {

        *self.flags.borrow()

    }

    /// 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_done() {

            return false;

        }

        self.pos.set(self.pos() + self.char().len_utf8());

        self.char.set(self.pattern()[self.pos()..].chars().next());

        self.char.get().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.pos()..].starts_with(prefix) {

            for _ in 0..prefix.chars().count() {

                self.bump();

            }

            true

        } else {

            false

        }

    }

    /// 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 done.

    fn bump_and_bump_space(&self) -> bool {

        if !self.bump() {

            return false;

        }

        self.bump_space();

        !self.is_done()

    }

    /// 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.flags().ignore_whitespace {

            return;

        }

        while !self.is_done() {

            if self.char().is_whitespace() {

                self.bump();

            } else if self.char() == '#' {

                self.bump();

                while !self.is_done() {

                    let c = self.char();

                    self.bump();

                    if c == '\n' {

                        break;

                    }

                }

            } 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_done() {

            return None;

        }

        self.pattern()[self.pos() + self.char().len_utf8()..].chars().next()

    }

    /// Peeks at the next character in the pattern from the current offset, and

    /// will ignore spaces when the parser is in whitespace insensitive mode.

    fn peek_space(&self) -> Option<char> {

        if !self.flags().ignore_whitespace {

            return self.peek();

        }

        if self.is_done() {

            return None;

        }

        let mut start = self.pos() + self.char().len_utf8();

        let mut in_comment = false;

        for (i, ch) in self.pattern()[start..].char_indices() {

            if ch.is_whitespace() {

                continue;

            } else if !in_comment && ch == '#' {

                in_comment = true;

            } else if in_comment && ch == '\n' {

                in_comment = false;

            } else {

                start += i;

                break;

            }

        }

        self.pattern()[start..].chars().next()

    }

    /// Return the next capturing index. Each subsequent call increments the

    /// internal index. Since the way capture indices are computed is a public

    /// API guarantee, use of this routine depends on the parser being depth

    /// first and left-to-right.

    ///

    /// If the capture limit is exceeded, then an error is returned.

    fn next_capture_index(&self) -> Result<u32, Error> {

        let current = self.capture_index.get();

        let next = current

            .checked_add(1)

            .ok_or_else(|| Error::new(ERR_TOO_MANY_CAPTURES))?;

        self.capture_index.set(next);

        Ok(next)

    }

    /// 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, name: &str) -> Result<(), Error> {

        let mut names = self.capture_names.borrow_mut();

        match names.binary_search_by(|n| name.cmp(n)) {

            Ok(_) => Err(Error::new(ERR_DUPLICATE_CAPTURE_NAME)),

            Err(i) => {

                names.insert(i, name.to_string());

                Ok(())

            }

        }

    }

    /// 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("?<!")

    }

}

/// The actual parser. We try to break out each kind of regex syntax into its

/// own routine.

impl<'a> Parser<'a> {

    pub(super) fn parse(&self) -> Result<Hir, Error> {

        let hir = self.parse_inner()?;

        // While we also check nesting during parsing, that only checks the

        // number of recursive parse calls. It does not necessarily cover

        // all possible recursive nesting of the Hir itself. For example,

        // repetition operators don't require recursive parse calls. So one

        // can stack them arbitrarily without overflowing the stack in the

        // *parser*. But then if one recurses over the resulting Hir, a stack

        // overflow is possible. So here we check the Hir nesting level

        // thoroughly to ensure it isn't nested too deeply.

        //

        // Note that we do still need the nesting limit check in the parser as

        // well, since that will avoid overflowing the stack during parse time

        // before the complete Hir value is constructed.

        check_hir_nesting(&hir, self.config.nest_limit)?;

        Ok(hir)

    }

    fn parse_inner(&self) -> Result<Hir, Error> {

        let depth = self.increment_depth()?;

        let mut alternates = vec![];

        let mut concat = vec![];

        loop {

            self.bump_space();

            if self.is_done() {

                break;

            }

            match self.char() {

                '(' => {

                    // Save the old flags and reset them only when we close

                    // the group.

                    let oldflags = *self.flags.borrow();

                    if let Some(sub) = self.parse_group()? {

                        concat.push(sub);

                        // We only reset them here because if 'parse_group'

                        // returns None, then that means it handled a flag

                        // directive, e.g., '(?ism)'. And the whole point is

                        // that those flags remain active until either disabled

                        // or the end of the pattern or current group.

                        *self.flags.borrow_mut() = oldflags;

                    }

                    if self.char.get() != Some(')') {

                        return Err(Error::new(ERR_UNCLOSED_GROUP));

                    }

                    self.bump();

                }

                ')' => {

                    if depth == 0 {

                        return Err(Error::new(ERR_UNOPENED_GROUP));

                    }

                    break;

                }

                '|' => {

                    alternates.push(Hir::concat(core::mem::take(&mut concat)));

                    self.bump();

                }

                '[' => concat.push(self.parse_class()?),

                '?' | '*' | '+' => {

                    concat = self.parse_uncounted_repetition(concat)?;

                }

                '{' => {

                    concat = self.parse_counted_repetition(concat)?;

                }

                _ => concat.push(self.parse_primitive()?),

            }

        }

        self.decrement_depth();

        alternates.push(Hir::concat(concat));

        // N.B. This strips off the "alternation" if there's only one branch.

        Ok(Hir::alternation(alternates))

    }

    /// Parses a "primitive" pattern. A primitive is any expression that does

    /// not contain any sub-expressions.

    ///

    /// This assumes the parser is pointing at the beginning of the primitive.

    fn parse_primitive(&self) -> Result<Hir, Error> {

        let ch = self.char();

        self.bump();

        match ch {

            '\\' => self.parse_escape(),

            '.' => Ok(self.hir_dot()),

            '^' => Ok(self.hir_anchor_start()),

            '$' => Ok(self.hir_anchor_end()),

            ch => Ok(self.hir_char(ch)),

        }

    }

    /// Parse an escape sequence. This always results in a "primitive" HIR,

    /// that is, an HIR with no sub-expressions.

    ///

    /// This assumes the parser is positioned at the start of the sequence,

    /// immediately *after* the `\`. It advances the parser to the first

    /// position immediately following the escape sequence.

    fn parse_escape(&self) -> Result<Hir, Error> {

        if self.is_done() {

            return Err(Error::new(ERR_ESCAPE_UNEXPECTED_EOF));

        }

        let ch = self.char();

        // Put some of the more complicated routines into helpers.

        match ch {

            '0'..='9' => return Err(Error::new(ERR_BACKREF_UNSUPPORTED)),

            'p' | 'P' => {

                return Err(Error::new(ERR_UNICODE_CLASS_UNSUPPORTED))

            }

            'x' | 'u' | 'U' => return self.parse_hex(),

            'd' | 's' | 'w' | 'D' | 'S' | 'W' => {

                return Ok(self.parse_perl_class());

            }

            _ => {}

        }

        // Handle all of the one letter sequences inline.

        self.bump();

        if hir::is_meta_character(ch) || hir::is_escapable_character(ch) {

            return Ok(self.hir_char(ch));

        }

        let special = |ch| Ok(self.hir_char(ch));

        match ch {

            'a' => special('\x07'),

            'f' => special('\x0C'),

            't' => special('\t'),

            'n' => special('\n'),

            'r' => special('\r'),

            'v' => special('\x0B'),

            'A' => Ok(Hir::look(hir::Look::Start)),

            'z' => Ok(Hir::look(hir::Look::End)),

            'b' => {

                let mut hir = Hir::look(hir::Look::Word);

                if !self.is_done() && self.char() == '{' {

                    if let Some(special) =

                        self.maybe_parse_special_word_boundary()?

                    {

                        hir = special;

                    }

                }

                Ok(hir)

            }

            'B' => Ok(Hir::look(hir::Look::WordNegate)),

            '<' => Ok(Hir::look(hir::Look::WordStart)),

            '>' => Ok(Hir::look(hir::Look::WordEnd)),

            _ => Err(Error::new(ERR_ESCAPE_UNRECOGNIZED)),

        }

    }

    /// Attempt to parse a specialty word boundary. That is, `\b{start}`,

    /// `\b{end}`, `\b{start-half}` or `\b{end-half}`.

    ///

    /// This is similar to `maybe_parse_ascii_class` in that, in most cases,

    /// if it fails it will just return `None` with no error. This is done

    /// because `\b{5}` is a valid expression and we want to let that be parsed

    /// by the existing counted repetition parsing code. (I thought about just

    /// invoking the counted repetition code from here, but it seemed a little

    /// ham-fisted.)

    ///

    /// Unlike `maybe_parse_ascii_class` though, this can return an error.

    /// Namely, if we definitely know it isn't a counted repetition, then we

    /// return an error specific to the specialty word boundaries.

    ///

    /// This assumes the parser is positioned at a `{` immediately following

    /// a `\b`. When `None` is returned, the parser is returned to the position

    /// at which it started: pointing at a `{`.

    ///

    /// The position given should correspond to the start of the `\b`.

    fn maybe_parse_special_word_boundary(&self) -> Result<Option<Hir>, Error> {

        assert_eq!(self.char(), '{');

        let is_valid_char = |c| match c {

            'A'..='Z' | 'a'..='z' | '-' => true,

            _ => false,

        };

        let start = self.pos();

        if !self.bump_and_bump_space() {

            return Err(Error::new(ERR_SPECIAL_WORD_OR_REP_UNEXPECTED_EOF));

        }

        // This is one of the critical bits: if the first non-whitespace

        // character isn't in [-A-Za-z] (i.e., this can't be a special word

        // boundary), then we bail and let the counted repetition parser deal

        // with this.

        if !is_valid_char(self.char()) {

            self.pos.set(start);

            self.char.set(Some('{'));

            return Ok(None);

        }

        // Now collect up our chars until we see a '}'.

        let mut scratch = String::new();

        while !self.is_done() && is_valid_char(self.char()) {

            scratch.push(self.char());

            self.bump_and_bump_space();

        }

        if self.is_done() || self.char() != '}' {

            return Err(Error::new(ERR_SPECIAL_WORD_BOUNDARY_UNCLOSED));

        }

        self.bump();

        let kind = match scratch.as_str() {

            "start" => hir::Look::WordStart,

            "end" => hir::Look::WordEnd,

            "start-half" => hir::Look::WordStartHalf,

            "end-half" => hir::Look::WordEndHalf,

            _ => {

                return Err(Error::new(ERR_SPECIAL_WORD_BOUNDARY_UNRECOGNIZED))

            }

        };

        Ok(Some(Hir::look(kind)))

    }

    /// 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.

    fn parse_hex(&self) -> Result<Hir, Error> {

        let digit_len = match self.char() {

            'x' => 2,

            'u' => 4,

            'U' => 8,

            unk => unreachable!(

                "invalid start of fixed length hexadecimal number {unk}"

            ),

        };

        if !self.bump_and_bump_space() {

            return Err(Error::new(ERR_HEX_UNEXPECTED_EOF));

        }

        if self.char() == '{' {

            self.parse_hex_brace()

        } else {

            self.parse_hex_digits(digit_len)

        }

    }

    /// 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`).

    fn parse_hex_digits(&self, digit_len: usize) -> Result<Hir, Error> {

        let mut scratch = String::new();

        for i in 0..digit_len {

            if i > 0 && !self.bump_and_bump_space() {

                return Err(Error::new(ERR_HEX_FIXED_UNEXPECTED_EOF));

            }

            if !is_hex(self.char()) {

                return Err(Error::new(ERR_HEX_FIXED_INVALID_DIGIT));

            }

            scratch.push(self.char());

        }

        // The final bump just moves the parser past the literal, which may

        // be EOF.

        self.bump_and_bump_space();

        match u32::from_str_radix(&scratch, 16).ok().and_then(char::from_u32) {

            None => Err(Error::new(ERR_HEX_FIXED_INVALID)),

            Some(ch) => Ok(self.hir_char(ch)),

        }

    }

    /// 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 `}`.

    fn parse_hex_brace(&self) -> Result<Hir, Error> {

        let mut scratch = String::new();

        while self.bump_and_bump_space() && self.char() != '}' {

            if !is_hex(self.char()) {

                return Err(Error::new(ERR_HEX_BRACE_INVALID_DIGIT));

            }

            scratch.push(self.char());

        }

        if self.is_done() {

            return Err(Error::new(ERR_HEX_BRACE_UNEXPECTED_EOF));

        }

        assert_eq!(self.char(), '}');

        self.bump_and_bump_space();

        if scratch.is_empty() {

            return Err(Error::new(ERR_HEX_BRACE_EMPTY));

        }

        match u32::from_str_radix(&scratch, 16).ok().and_then(char::from_u32) {

            None => Err(Error::new(ERR_HEX_BRACE_INVALID)),

            Some(ch) => Ok(self.hir_char(ch)),

        }

    }

    /// 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, Error> {

        let mut scratch = String::new();

        while !self.is_done() && self.char().is_whitespace() {

            self.bump();

        }

        while !self.is_done() && '0' <= self.char() && self.char() <= '9' {

            scratch.push(self.char());

            self.bump_and_bump_space();

        }

        while !self.is_done() && self.char().is_whitespace() {

            self.bump_and_bump_space();

        }

        let digits = scratch.as_str();

        if digits.is_empty() {

            return Err(Error::new(ERR_DECIMAL_NO_DIGITS));

        }

        match u32::from_str_radix(digits, 10).ok() {

            Some(n) => Ok(n),

            None => Err(Error::new(ERR_DECIMAL_INVALID)),

        }

    }

    /// Parses an uncounted repetition operator. An uncounted repetition

    /// operator includes `?`, `*` and `+`, but does not include the `{m,n}`

    /// syntax. The current character should be one of `?`, `*` or `+`. Any

    /// other character will result in a panic.

    ///

    /// 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.

    ///

    /// If the concatenation is empty, then this returns an error.

    fn parse_uncounted_repetition(

        &self,

        mut concat: Vec<Hir>,

    ) -> Result<Vec<Hir>, Error> {

        let sub = match concat.pop() {

            Some(hir) => Box::new(hir),

            None => {

                return Err(Error::new(ERR_UNCOUNTED_REP_SUB_MISSING));

            }

        };

        let (min, max) = match self.char() {

            '?' => (0, Some(1)),

            '*' => (0, None),

            '+' => (1, None),

            unk => unreachable!("unrecognized repetition operator '{unk}'"),

        };

        let mut greedy = true;

        if self.bump() && self.char() == '?' {

            greedy = false;

            self.bump();

        }

        if self.flags().swap_greed {

            greedy = !greedy;

        }

        concat.push(Hir::repetition(hir::Repetition {

            min,

            max,

            greedy,

            sub,

        }));

        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 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.

    ///

    /// If the concatenation is empty, then this returns an error.

    fn parse_counted_repetition(

        &self,

        mut concat: Vec<Hir>,

    ) -> Result<Vec<Hir>, Error> {

        assert_eq!(self.char(), '{', "expected opening brace");

        let sub = match concat.pop() {

            Some(hir) => Box::new(hir),

            None => {

                return Err(Error::new(ERR_COUNTED_REP_SUB_MISSING));

            }

        };

        if !self.bump_and_bump_space() {

            return Err(Error::new(ERR_COUNTED_REP_UNCLOSED));

        }

        let min = self.parse_decimal()?;

        let mut max = Some(min);

        if self.is_done() {

            return Err(Error::new(ERR_COUNTED_REP_MIN_UNCLOSED));

        }

        if self.char() == ',' {

            if !self.bump_and_bump_space() {

                return Err(Error::new(ERR_COUNTED_REP_COMMA_UNCLOSED));

            }

            if self.char() != '}' {

                max = Some(self.parse_decimal()?);

            } else {

                max = None;

            }

            if self.is_done() {

                return Err(Error::new(ERR_COUNTED_REP_MIN_MAX_UNCLOSED));

            }

        }

        if self.char() != '}' {

            return Err(Error::new(ERR_COUNTED_REP_INVALID));

        }

        let mut greedy = true;

        if self.bump_and_bump_space() && self.char() == '?' {

            greedy = false;

            self.bump();

        }

        if self.flags().swap_greed {

            greedy = !greedy;

        }

        if max.map_or(false, |max| min > max) {

            return Err(Error::new(ERR_COUNTED_REP_INVALID_RANGE));

        }

        concat.push(Hir::repetition(hir::Repetition {

            min,

            max,

            greedy,

            sub,

        }));

        Ok(concat)

    }

    /// Parses the part of a pattern that starts with a `(`. This is usually

    /// a group sub-expression, but might just be a directive that enables

    /// (or disables) certain flags.

    ///

    /// This assumes the parser is pointing at the opening `(`.

    fn parse_group(&self) -> Result<Option<Hir>, Error> {

        assert_eq!(self.char(), '(');

        self.bump_and_bump_space();

        if self.is_lookaround_prefix() {

            return Err(Error::new(ERR_LOOK_UNSUPPORTED));

        }

        if self.bump_if("?P<") || self.bump_if("?<") {

            let index = self.next_capture_index()?;

            let name = Some(Box::from(self.parse_capture_name()?));

            let sub = Box::new(self.parse_inner()?);

            let cap = hir::Capture { index, name, sub };

            Ok(Some(Hir::capture(cap)))

        } else if self.bump_if("?") {

            if self.is_done() {

                return Err(Error::new(ERR_UNCLOSED_GROUP_QUESTION));

            }

            let start = self.pos();

            // The flags get reset in the top-level 'parse' routine.

            *self.flags.borrow_mut() = self.parse_flags()?;

            let consumed = self.pos() - start;

            if self.char() == ')' {

                // We don't allow empty flags, e.g., `(?)`.

                if consumed == 0 {

                    return Err(Error::new(ERR_EMPTY_FLAGS));

                }

                Ok(None)

            } else {

                assert_eq!(':', self.char());

                self.bump();

                self.parse_inner().map(Some)

            }

        } else {

            let index = self.next_capture_index()?;

            let sub = Box::new(self.parse_inner()?);

            let cap = hir::Capture { index, name: None, sub };

            Ok(Some(Hir::capture(cap)))

        }

    }

    /// 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 `>`.

    fn parse_capture_name(&self) -> Result<&str, Error> {

        if self.is_done() {

            return Err(Error::new(ERR_MISSING_GROUP_NAME));

        }

        let start = self.pos();

        loop {

            if self.char() == '>' {

                break;

            }

            if !is_capture_char(self.char(), self.pos() == start) {

                return Err(Error::new(ERR_INVALID_GROUP_NAME));

            }

            if !self.bump() {

                break;

            }

        }

        let end = self.pos();

        if self.is_done() {

            return Err(Error::new(ERR_UNCLOSED_GROUP_NAME));

        }

        assert_eq!(self.char(), '>');

        self.bump();

        let name = &self.pattern()[start..end];

        if name.is_empty() {

            return Err(Error::new(ERR_EMPTY_GROUP_NAME));

        }

        self.add_capture_name(name)?;

        Ok(name)

    }

    /// 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.

    fn parse_flags(&self) -> Result<Flags, Error> {

        let mut flags = *self.flags.borrow();

        let mut negate = false;

        // Keeps track of whether the previous flag item was a '-'. We use this

        // to detect whether there is a dangling '-', which is invalid.

        let mut last_was_negation = false;

        // A set to keep track of the flags we've seen. Since all flags are

        // ASCII, we only need 128 bytes.

        let mut seen = [false; 128];

        while self.char() != ':' && self.char() != ')' {

            if self.char() == '-' {

                last_was_negation = true;

                if negate {

                    return Err(Error::new(ERR_FLAG_REPEATED_NEGATION));

                }

                negate = true;

            } else {

                last_was_negation = false;

                self.parse_flag(&mut flags, negate)?;

                // OK because every valid flag is ASCII, and we're only here if

                // the flag is valid.

                let flag_byte = u8::try_from(self.char()).unwrap();

                if seen[usize::from(flag_byte)] {

                    return Err(Error::new(ERR_FLAG_DUPLICATE));

                }

                seen[usize::from(flag_byte)] = true;

            }

            if !self.bump() {

                return Err(Error::new(ERR_FLAG_UNEXPECTED_EOF));

            }

        }

        if last_was_negation {

            return Err(Error::new(ERR_FLAG_DANGLING_NEGATION));

        }

        Ok(flags)

    }

    /// Parse the current character as a flag. Do not advance the parser.

    ///

    /// This sets the appropriate boolean value in place on the set of flags

    /// given. The boolean is inverted when `negate` is true.

    ///

    /// # Errors

    ///

    /// If the flag is not recognized, then an error is returned.

    fn parse_flag(

        &self,

        flags: &mut Flags,

        negate: bool,

    ) -> Result<(), Error> {

        let enabled = !negate;

        match self.char() {

            'i' => flags.case_insensitive = enabled,

            'm' => flags.multi_line = enabled,

            's' => flags.dot_matches_new_line = enabled,

            'U' => flags.swap_greed = enabled,

            'R' => flags.crlf = enabled,

            'x' => flags.ignore_whitespace = enabled,

            // We make a special exception for this flag where we let it

            // through as a recognized flag, but treat it as a no-op. This in

            // practice retains some compatibility with the regex crate. It is

            // a little suspect to do this, but for example, '(?-u:\b).+' in

            // the regex crate is equivalent to '\b.+' in regex-lite.

            'u' => {}

            _ => return Err(Error::new(ERR_FLAG_UNRECOGNIZED)),

        }

        Ok(())

    }

    /// Parse a standard character class consisting primarily of characters or

    /// character ranges.

    ///

    /// 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 `]`.

    fn parse_class(&self) -> Result<Hir, Error> {

        assert_eq!(self.char(), '[');

        let mut union = vec![];

        if !self.bump_and_bump_space() {

            return Err(Error::new(ERR_CLASS_UNCLOSED));

        }

        // Determine whether the class is negated or not.

        let negate = if self.char() != '^' {

            false

        } else {

            if !self.bump_and_bump_space() {

                return Err(Error::new(ERR_CLASS_UNCLOSED_AFTER_NEGATION));

            }

            true

        };

        // Accept any number of `-` as literal `-`.

        while self.char() == '-' {

            union.push(hir::ClassRange { start: '-', end: '-' });

            if !self.bump_and_bump_space() {

                return Err(Error::new(ERR_CLASS_UNCLOSED_AFTER_DASH));

            }

        }

        // 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.is_empty() && self.char() == ']' {

            union.push(hir::ClassRange { start: ']', end: ']' });

            if !self.bump_and_bump_space() {

                return Err(Error::new(ERR_CLASS_UNCLOSED_AFTER_CLOSING));

            }

        }

        loop {

            self.bump_space();

            if self.is_done() {

                return Err(Error::new(ERR_CLASS_UNCLOSED));

            }

            match self.char() {

                '[' => {

                    // Attempt to treat this as the beginning of a POSIX class.

                    // If POSIX class parsing fails, then the parser backs up

                    // to `[`.

                    if let Some(class) = self.maybe_parse_posix_class() {

                        union.extend_from_slice(&class.ranges);

                        continue;

                    }

                    // ... otherwise we don't support nested classes.

                    return Err(Error::new(ERR_CLASS_NEST_UNSUPPORTED));

                }

                ']' => {

                    self.bump();

                    let mut class = hir::Class::new(union);

                    // Note that we must apply case folding before negation!

                    // Consider `(?i)[^x]`. If we applied negation first, then

                    // the result would be the character class that matched any

                    // Unicode scalar value.

                    if self.flags().case_insensitive {

                        class.ascii_case_fold();

                    }

                    if negate {

                        class.negate();

                    }

                    return Ok(Hir::class(class));

                }

                '&' if self.peek() == Some('&') => {

                    return Err(Error::new(

                        ERR_CLASS_INTERSECTION_UNSUPPORTED,

                    ));

                }

                '-' if self.peek() == Some('-') => {

                    return Err(Error::new(ERR_CLASS_DIFFERENCE_UNSUPPORTED));

                }

                '~' if self.peek() == Some('~') => {

                    return Err(Error::new(

                        ERR_CLASS_SYMDIFFERENCE_UNSUPPORTED,

                    ));

                }

                _ => self.parse_class_range(&mut union)?,

            }

        }

    }