syntaxmate 0.2.1

use std::collections::BTreeMap;
use std::fmt;
use std::ops::Deref;
use std::sync::{Arc, OnceLock};

use super::analysis::RegexAnalysis;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct RegexFlags {
    pub case_insensitive: bool,
    pub multi_line: bool,
    pub dot_matches_new_line: bool,
    pub ignore_whitespace: bool,
}

#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct RegexFeatures {
    pub lookahead: bool,
    pub lookbehind: bool,
    pub backreference: bool,
    pub subroutine: bool,
    pub anchor_a: bool,
    pub anchor_g: bool,
    pub line_anchor: bool,
    pub named_group: bool,
    pub possessive_or_atomic: bool,
    pub inline_flags: bool,
    pub unicode_or_posix_class: bool,
    pub conditional: bool,
    pub unsupported_escape: bool,
}

impl RegexFeatures {
    pub fn requires_fallback(&self) -> bool {
        self.lookahead
            || self.lookbehind
            || self.backreference
            || self.subroutine
            || self.anchor_g
            || self.named_group
            || self.possessive_or_atomic
            || self.conditional
            || self.unsupported_escape
    }

    pub fn reasons(&self) -> Vec<&'static str> {
        let mut reasons = Vec::new();
        if self.lookahead {
            reasons.push("lookahead");
        }
        if self.lookbehind {
            reasons.push("lookbehind");
        }
        if self.backreference {
            reasons.push("backreference");
        }
        if self.subroutine {
            reasons.push("subroutine");
        }
        if self.anchor_g {
            reasons.push("\\G");
        }
        if self.named_group {
            reasons.push("named-group");
        }
        if self.possessive_or_atomic {
            reasons.push("possessive-or-atomic");
        }
        if self.conditional {
            reasons.push("conditional");
        }
        if self.unsupported_escape {
            reasons.push("unsupported-escape");
        }
        reasons
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AnchorKind {
    LineStart,
    LineEnd,
    TextStart,
    TextEnd,
    TextEndOrFinalNewline,
    Continuation,
    WordBoundary,
    NotWordBoundary,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum LookKind {
    Ahead,
    NotAhead,
    Behind,
    NotBehind,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PerlClassKind {
    Digit,
    NotDigit,
    Space,
    NotSpace,
    Word,
    NotWord,
    HorizontalSpace,
    NotHorizontalSpace,
    VerticalSpace,
    NotVerticalSpace,
    NotNewline,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ClassAtom {
    Char(char),
    Range(char, char),
    Perl(PerlClassKind),
    Posix { name: String, negated: bool },
    Unicode { name: String, negated: bool },
    Nested(Box<CharClass>),
}

#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct CharClass {
    pub negated: bool,
    /// Written in brackets. Oniguruma folds case for bracketed classes as a
    /// whole but leaves escapes such as `\p{Lu}` and `\w` unfolded.
    pub bracketed: bool,
    /// Additional union terms intersected with `atoms` by Oniguruma's `&&`
    /// operator. Each inner vector is a union, so `[ab&&bc&&cd]` is stored as
    /// `ab AND bc AND cd`.
    pub intersections: Vec<Vec<ClassAtom>>,
    pub atoms: Vec<ClassAtom>,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Backref {
    Number(u32),
    Name(String),
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum AstPathStep {
    Branch(usize),
    Child,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SubroutineCall {
    pub target: Backref,
    pub(crate) target_path: Option<Vec<AstPathStep>>,
}

/// Text of a literal node. Unescaped literal runs borrow a span of the
/// shared pattern source instead of owning a copy: keyword inventories parse
/// to thousands of literals, and one allocation per literal dominated both
/// parsing and teardown.
#[derive(Clone)]
pub struct LiteralText(LiteralRepr);

#[derive(Clone)]
enum LiteralRepr {
    Source {
        source: Arc<str>,
        start: u32,
        end: u32,
    },
    Owned(String),
}

impl LiteralText {
    fn from_source(source: &Arc<str>, start: usize, end: usize) -> Self {
        match (u32::try_from(start), u32::try_from(end)) {
            (Ok(start), Ok(end)) => Self(LiteralRepr::Source {
                source: Arc::clone(source),
                start,
                end,
            }),
            _ => Self(LiteralRepr::Owned(source[start..end].to_owned())),
        }
    }

    pub fn as_str(&self) -> &str {
        match &self.0 {
            LiteralRepr::Source { source, start, end } => &source[*start as usize..*end as usize],
            LiteralRepr::Owned(text) => text,
        }
    }

    /// Appends `other`, extending a source span in place when `other`
    /// continues it.
    fn push_literal(&mut self, other: &Self) {
        if let (
            LiteralRepr::Source { source, end, .. },
            LiteralRepr::Source {
                source: next_source,
                start: next_start,
                end: next_end,
            },
        ) = (&mut self.0, &other.0)
            && Arc::ptr_eq(source, next_source)
            && *end == *next_start
        {
            *end = *next_end;
            return;
        }
        let mut text = std::mem::take(self).into_string();
        text.push_str(other);
        self.0 = LiteralRepr::Owned(text);
    }

    fn into_string(self) -> String {
        match self.0 {
            LiteralRepr::Owned(text) => text,
            repr => Self(repr).as_str().to_owned(),
        }
    }
}

impl Default for LiteralText {
    fn default() -> Self {
        Self(LiteralRepr::Owned(String::new()))
    }
}

impl Deref for LiteralText {
    type Target = str;

    fn deref(&self) -> &str {
        self.as_str()
    }
}

impl AsRef<str> for LiteralText {
    fn as_ref(&self) -> &str {
        self.as_str()
    }
}

impl From<String> for LiteralText {
    fn from(text: String) -> Self {
        Self(LiteralRepr::Owned(text))
    }
}

impl From<&str> for LiteralText {
    fn from(text: &str) -> Self {
        Self(LiteralRepr::Owned(text.to_owned()))
    }
}

impl PartialEq for LiteralText {
    fn eq(&self, other: &Self) -> bool {
        self.as_str() == other.as_str()
    }
}

impl Eq for LiteralText {}

impl PartialEq<str> for LiteralText {
    fn eq(&self, other: &str) -> bool {
        self.as_str() == other
    }
}

impl PartialEq<&str> for LiteralText {
    fn eq(&self, other: &&str) -> bool {
        self.as_str() == *other
    }
}

impl fmt::Debug for LiteralText {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(self.as_str(), f)
    }
}

impl fmt::Display for LiteralText {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(self.as_str())
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Ast {
    Empty,
    Literal(LiteralText),
    Dot,
    Grapheme,
    Class(CharClass),
    Anchor(AnchorKind),
    Concat(Vec<Ast>),
    Alternation(Vec<Ast>),
    Repeat {
        node: Box<Ast>,
        min: usize,
        max: Option<usize>,
        greedy: bool,
        possessive: bool,
        atomic: bool,
    },
    Group {
        index: Option<u32>,
        name: Option<String>,
        child: Box<Ast>,
    },
    Look {
        kind: LookKind,
        child: Box<Ast>,
    },
    Backref(Backref),
    Conditional {
        condition: Backref,
        matched: Box<Ast>,
        unmatched: Box<Ast>,
    },
    Subroutine(Box<SubroutineCall>),
    Flags {
        flags: RegexFlags,
        child: Box<Ast>,
    },
    Unsupported(String),
}

fn collect_group_paths(
    ast: &Ast,
    path: &mut Vec<AstPathStep>,
    paths: &mut BTreeMap<u32, Vec<AstPathStep>>,
) {
    if let Ast::Group {
        index: Some(index), ..
    } = ast
    {
        paths.insert(*index, path.clone());
    }
    match ast {
        Ast::Concat(nodes) | Ast::Alternation(nodes) => {
            for (index, node) in nodes.iter().enumerate() {
                path.push(AstPathStep::Branch(index));
                collect_group_paths(node, path, paths);
                path.pop();
            }
        }
        Ast::Conditional {
            matched, unmatched, ..
        } => {
            path.push(AstPathStep::Branch(0));
            collect_group_paths(matched, path, paths);
            path.pop();
            path.push(AstPathStep::Branch(1));
            collect_group_paths(unmatched, path, paths);
            path.pop();
        }
        Ast::Repeat { node, .. }
        | Ast::Group { child: node, .. }
        | Ast::Look { child: node, .. }
        | Ast::Flags { child: node, .. } => {
            path.push(AstPathStep::Child);
            collect_group_paths(node, path, paths);
            path.pop();
        }
        Ast::Empty
        | Ast::Literal(_)
        | Ast::Dot
        | Ast::Grapheme
        | Ast::Class(_)
        | Ast::Anchor(_)
        | Ast::Backref(_)
        | Ast::Subroutine(_)
        | Ast::Unsupported(_) => {}
    }
}

fn resolve_subroutine_paths(
    ast: &mut Ast,
    named_captures: &BTreeMap<String, u32>,
    paths: &BTreeMap<u32, Vec<AstPathStep>>,
) {
    if let Ast::Subroutine(call) = ast {
        let target = match &call.target {
            Backref::Number(index) => Some(*index),
            Backref::Name(name) => named_captures.get(name).copied(),
        };
        call.target_path = target.and_then(|index| paths.get(&index).cloned());
    }
    match ast {
        Ast::Concat(nodes) | Ast::Alternation(nodes) => {
            for node in nodes {
                resolve_subroutine_paths(node, named_captures, paths);
            }
        }
        Ast::Conditional {
            matched, unmatched, ..
        } => {
            resolve_subroutine_paths(matched, named_captures, paths);
            resolve_subroutine_paths(unmatched, named_captures, paths);
        }
        Ast::Repeat { node, .. }
        | Ast::Group { child: node, .. }
        | Ast::Look { child: node, .. }
        | Ast::Flags { child: node, .. } => {
            resolve_subroutine_paths(node, named_captures, paths);
        }
        _ => {}
    }
}

#[derive(Debug, Clone)]
pub struct ParsedRegex {
    pub source: String,
    pub ast: Ast,
    pub features: RegexFeatures,
    pub flags: RegexFlags,
    pub capture_count: u32,
    /// Last group of each name.
    pub named_captures: BTreeMap<String, u32>,
    /// Every group of each name used by more than one group, ascending.
    pub duplicate_names: BTreeMap<String, Vec<u32>>,
    pub diagnostics: Vec<String>,
    pub(crate) first_diagnostic_position: Option<usize>,
    analysis: OnceLock<RegexAnalysis>,
}

impl PartialEq for ParsedRegex {
    fn eq(&self, other: &Self) -> bool {
        self.source == other.source
            && self.ast == other.ast
            && self.features == other.features
            && self.flags == other.flags
            && self.capture_count == other.capture_count
            && self.named_captures == other.named_captures
            && self.duplicate_names == other.duplicate_names
            && self.diagnostics == other.diagnostics
    }
}

impl Eq for ParsedRegex {}

impl ParsedRegex {
    pub(crate) fn initialize_analysis(&self) -> &RegexAnalysis {
        self.analysis.get_or_init(|| RegexAnalysis::new(self))
    }

    pub(crate) fn analysis(&self) -> &RegexAnalysis {
        self.initialize_analysis()
    }

    pub(crate) fn prefilter(&self) -> &super::prefilter::Prefilter {
        self.analysis().prefilter(self)
    }

    pub fn route_reason(&self) -> &'static str {
        if self.features.requires_fallback() {
            "fallback"
        } else {
            "dfa"
        }
    }
}

pub fn parse(pattern: &str) -> ParsedRegex {
    Parser::new(pattern).parse()
}

pub fn classify_features(pattern: &str) -> RegexFeatures {
    parse(pattern).features
}

fn is_quantifier_start(ch: char) -> bool {
    matches!(ch, '*' | '+' | '?' | '{')
}

/// Escaped ASCII punctuation and whitespace always denote the scalar itself:
/// every special escape in `parse_escape` is a letter or digit.
fn is_punctuation_escape(ch: char) -> bool {
    ch.is_ascii() && !ch.is_ascii_alphanumeric()
}

fn is_regex_syntax(ch: char) -> bool {
    matches!(
        ch,
        '(' | '[' | '.' | '^' | '$' | '\\' | ')' | '|' | '*' | '+' | '?' | '{'
    )
}

/// ASCII bytes that stand for themselves outside a class: everything except
/// regex syntax and, under the extended `x` option, whitespace and `#`.
/// Quantifier starts are syntax, so a run of these bytes never contains a
/// quantifier. Indexed by `extended` then byte.
static PLAIN_LITERAL_BYTE: [[bool; 256]; 2] = {
    let mut table = [[false; 256]; 2];
    let mut byte = 0;
    while byte < 128 {
        let plain = !matches!(
            byte as u8,
            b'(' | b'[' | b'.' | b'^' | b'$' | b'\\' | b')' | b'|' | b'*' | b'+' | b'?' | b'{'
        );
        // Oniguruma's extended-mode separators exclude vertical tab and all
        // non-ASCII whitespace. This is distinct from the \s character class.
        let extended_syntax = matches!(byte as u8, b'\t' | b'\n' | b'\r' | b'\x0c' | b' ' | b'#');
        table[0][byte] = plain;
        table[1][byte] = plain && !extended_syntax;
        byte += 1;
    }
    table
};

/// End of the run of plain literal bytes starting at `pos`.
#[inline]
fn plain_literal_end(bytes: &[u8], mut pos: usize, extended: bool) -> usize {
    let table = &PLAIN_LITERAL_BYTE[usize::from(extended)];
    while let Some(&byte) = bytes.get(pos) {
        if !table[usize::from(byte)] {
            break;
        }
        pos += 1;
    }
    pos
}

struct Parser<'a> {
    source: &'a str,
    bytes: &'a [u8],
    /// Byte offset into `source`; always on a scalar boundary.
    pos: usize,
    /// Scratch stack shared by every sequence and branch list under
    /// construction. Nested constructs complete before their parent resumes,
    /// so each list occupies the top of the stack and leaves as one
    /// exactly-sized vector instead of growing its own allocation.
    nodes: Vec<Ast>,
    /// Shared copy of `source` that unescaped literals borrow spans of;
    /// created on the first such literal.
    shared_source: Option<Arc<str>>,
    /// The same scratch discipline for character-class unions.
    class_atoms: Vec<ClassAtom>,
    next_capture: u32,
    named_captures: BTreeMap<String, u32>,
    duplicate_names: BTreeMap<String, Vec<u32>>,
    features: RegexFeatures,
    flags: RegexFlags,
    diagnostics: Vec<String>,
    first_diagnostic_position: Option<usize>,
    depth: usize,
}

/// Bounds recursive-descent nesting so hostile grammar patterns cannot
/// overflow the stack. One regex nesting level spans several Rust call frames,
/// and parsed ASTs are also walked recursively, so this must be conservative
/// for callers using small worker-thread stacks. Bundled grammars stay below
/// 32 levels; exceeding this limit degrades the over-deep construct to a
/// never-matching node instead of aborting the process.
const MAX_PARSE_DEPTH: usize = 128;

impl<'a> Parser<'a> {
    fn new(source: &'a str) -> Self {
        Self {
            source,
            bytes: source.as_bytes(),
            pos: 0,
            nodes: Vec::new(),
            shared_source: None,
            class_atoms: Vec::new(),
            next_capture: 1,
            named_captures: BTreeMap::new(),
            duplicate_names: BTreeMap::new(),
            features: RegexFeatures::default(),
            flags: RegexFlags::default(),
            diagnostics: Vec::new(),
            first_diagnostic_position: None,
            depth: 0,
        }
    }

    fn parse(mut self) -> ParsedRegex {
        let mut ast = self.parse_alternation(None);
        if self.pos < self.bytes.len() {
            let at = self.char_index(self.pos);
            self.diagnostic(at, format!("trailing input at char {at}"));
        }
        if self.features.subroutine {
            let mut paths = BTreeMap::new();
            collect_group_paths(&ast, &mut Vec::new(), &mut paths);
            resolve_subroutine_paths(&mut ast, &self.named_captures, &paths);
        }
        ParsedRegex {
            source: self.source.to_owned(),
            ast,
            features: self.features,
            // Option changes are represented at the AST node where they are
            // active.  The VM therefore always starts with Oniguruma's
            // defaults; using the final parser state here incorrectly applies
            // a trailing `(?i)`/`(?-i)` choice to the entire expression.
            flags: RegexFlags::default(),
            capture_count: self.next_capture.saturating_sub(1),
            named_captures: self.named_captures,
            duplicate_names: self.duplicate_names,
            diagnostics: self.diagnostics,
            first_diagnostic_position: self.first_diagnostic_position,
            analysis: OnceLock::new(),
        }
    }

    /// Literal text of the unescaped source span `start..end`.
    fn source_literal(&mut self, start: usize, end: usize) -> LiteralText {
        let source = self
            .shared_source
            .get_or_insert_with(|| Arc::from(self.source));
        LiteralText::from_source(source, start, end)
    }

    fn parse_alternation(&mut self, terminator: Option<char>) -> Ast {
        let first = self.parse_concat(terminator);
        if self.peek() != Some('|') {
            // Most groups have one branch; only an option change inside it
            // needs the branch-list normalization.
            return if has_flag_change_marker(&first) {
                normalize_flag_changes(vec![first])
            } else {
                first
            };
        }
        let base = self.nodes.len();
        self.nodes.push(first);
        while self.peek() == Some('|') {
            self.bump();
            // Keyword inventories are thousands of plain words; build each
            // directly in the branch list.
            let branch = match self.parse_plain_literal_branch(terminator) {
                Some(literal) => literal,
                None => self.parse_concat(terminator),
            };
            self.nodes.push(branch);
        }
        let branches = self.nodes.drain(base..).collect();
        normalize_flag_changes(branches)
    }

    fn parse_concat(&mut self, terminator: Option<char>) -> Ast {
        if let Some(literal) = self.parse_plain_literal_branch(terminator) {
            return literal;
        }
        let base = self.nodes.len();
        while let Some(ch) = self.peek() {
            if Some(ch) == terminator || ch == '|' {
                break;
            }
            if self.flags.ignore_whitespace && matches!(ch, '\t' | '\n' | '\r' | '\x0c' | ' ') {
                self.bump();
                continue;
            }
            if self.flags.ignore_whitespace && ch == '#' {
                while self.peek().is_some_and(|next| next != '\n') {
                    self.bump();
                }
                continue;
            }
            let node = self.parse_repeat();
            push_concat_node(&mut self.nodes, base, node);
        }
        match self.nodes.len() - base {
            0 => Ast::Empty,
            1 => self.nodes.pop().expect("one node"),
            _ => Ast::Concat(self.nodes.drain(base..).collect()),
        }
    }

    /// Keyword inventories spell most sequences as bare ASCII words ending at
    /// a branch or group boundary. Such a sequence parses to the single
    /// literal (under the active option snapshot) that the general path
    /// would build scalar run by scalar run, so take it in one scan.
    #[inline(always)]
    fn parse_plain_literal_branch(&mut self, terminator: Option<char>) -> Option<Ast> {
        let start = self.pos;
        let end = plain_literal_end(self.bytes, start, self.flags.ignore_whitespace);
        if end == start {
            return None;
        }
        let ends_sequence = match self.bytes.get(end) {
            None => true,
            Some(b'|') => true,
            Some(b')') => terminator == Some(')'),
            Some(_) => false,
        };
        if !ends_sequence {
            return None;
        }
        self.pos = end;
        let literal = Ast::Literal(self.source_literal(start, end));
        Some(if self.flags == RegexFlags::default() {
            literal
        } else {
            Ast::Flags {
                flags: self.flags,
                child: Box::new(literal),
            }
        })
    }

    fn parse_repeat(&mut self) -> Ast {
        let active_flags = self.flags;
        let atom_is_group = self.peek() == Some('(');
        let mut node = self.parse_atom();
        // Bare option groups such as `(?i)` affect the remainder of the
        // enclosing subexpression. Snapshot those options on consuming atoms.
        // Groups and lookarounds snapshot their children while parsing, so an
        // outer wrapper here would overwrite an inner `(?-i)` transition.
        if !atom_is_group
            && active_flags != RegexFlags::default()
            && matches!(
                node,
                Ast::Literal(_)
                    | Ast::Dot
                    | Ast::Grapheme
                    | Ast::Class(_)
                    | Ast::Anchor(_)
                    | Ast::Backref(_)
                    | Ast::Subroutine(_)
            )
        {
            node = Ast::Flags {
                flags: active_flags,
                child: Box::new(node),
            };
        }
        while let Some(ch) = self.peek() {
            let braced = ch == '{';
            let quantifier = match ch {
                '*' => {
                    self.bump();
                    Some((0, None, false))
                }
                '+' => {
                    self.bump();
                    Some((1, None, false))
                }
                '?' => {
                    self.bump();
                    Some((0, Some(1), false))
                }
                '{' => self.parse_braced_quantifier(),
                _ => None,
            };
            let Some((min, max, is_braced_exact)) = quantifier else {
                break;
            };
            // Oniguruma keeps the historical Ruby interpretation of `{n}?`:
            // the exact repetition is optional (zero or exactly n copies),
            // rather than a lazily evaluated exact repetition. TextMate
            // grammars rely on this, notably LaTeX hyperlink argument rules.
            if is_braced_exact && self.peek() == Some('?') {
                self.bump();
                let exact = Ast::Repeat {
                    node: Box::new(node),
                    min,
                    max,
                    greedy: true,
                    possessive: false,
                    atomic: false,
                };
                node = Ast::Repeat {
                    node: Box::new(exact),
                    min: 0,
                    max: Some(1),
                    greedy: true,
                    possessive: false,
                    atomic: false,
                };
                continue;
            }
            let mut greedy = true;
            let mut possessive = false;
            if self.peek() == Some('?') {
                self.bump();
                greedy = false;
            } else if self.peek() == Some('+') && !braced {
                // After an interval, Oniguruma reads `+` as another
                // quantifier: `a{1,2}+` is `(?:a{1,2})+`, not possessive.
                self.bump();
                possessive = true;
                self.features.possessive_or_atomic = true;
            }
            node = Ast::Repeat {
                node: Box::new(node),
                min,
                max,
                greedy,
                possessive,
                atomic: false,
            };
        }
        node
    }

    fn parse_atom(&mut self) -> Ast {
        let Some(ch) = self.bump() else {
            return Ast::Empty;
        };
        match ch {
            '(' => self.parse_group(),
            '[' => self.parse_class(),
            '.' => Ast::Dot,
            '^' => {
                self.features.line_anchor = true;
                Ast::Anchor(AnchorKind::LineStart)
            }
            '$' => {
                self.features.line_anchor = true;
                Ast::Anchor(AnchorKind::LineEnd)
            }
            '\\' if self.peek().is_some_and(is_punctuation_escape) => {
                self.pos += 1;
                self.parse_literal_run(self.pos - 2)
            }
            '\\' => self.parse_escape(false),
            ')' => {
                let at = self.char_index(self.pos - 1);
                self.diagnostic(at, format!("unmatched ')' at char {at}"));
                Ast::Unsupported("unmatched ')'".to_owned())
            }
            _ => self.parse_literal_run(self.pos - ch.len_utf8()),
        }
    }

    /// Continues a literal run whose first scalar (or punctuation escape)
    /// starts at `start` and has been consumed. Punctuation escapes such as
    /// `\.` are literal scalars too; absorbing them here yields the same
    /// coalesced literal `push_concat_node` would build from one-scalar
    /// pieces. A scalar or escape followed by a quantifier ends the run so
    /// the quantifier binds to it alone. The run is measured first so the
    /// string is allocated once; keyword inventories parse thousands of runs.
    fn parse_literal_run(&mut self, start: usize) -> Ast {
        let mut escaped = start < self.pos && self.bytes[start] == b'\\';
        let extended = self.flags.ignore_whitespace;
        while let Some(&byte) = self.bytes.get(self.pos) {
            if PLAIN_LITERAL_BYTE[usize::from(extended)][usize::from(byte)] {
                // A plain byte is followed by a quantifier only where the run
                // of plain bytes stops; that final scalar then binds alone.
                self.pos = plain_literal_end(self.bytes, self.pos, extended);
                if self
                    .bytes
                    .get(self.pos)
                    .is_some_and(|following| is_quantifier_start(char::from(*following)))
                {
                    self.pos -= 1;
                    break;
                }
                continue;
            }
            if byte == b'\\' {
                // Punctuation escapes and quantifiers are ASCII, so byte
                // lookahead cannot split a multi-byte scalar.
                let absorbs = self
                    .bytes
                    .get(self.pos + 1)
                    .is_some_and(|escaped| is_punctuation_escape(char::from(*escaped)))
                    && !self
                        .bytes
                        .get(self.pos + 2)
                        .is_some_and(|following| is_quantifier_start(char::from(*following)));
                if !absorbs {
                    break;
                }
                escaped = true;
                self.pos += 2;
                continue;
            }
            // Every other ASCII byte is regex syntax, or whitespace and `#`
            // in extended mode (see `PLAIN_LITERAL_BYTE`).
            if byte.is_ascii() {
                break;
            }
            let next = self.peek().expect("scalar boundary");
            let width = next.len_utf8();
            if self
                .bytes
                .get(self.pos + width)
                .is_some_and(|following| is_quantifier_start(char::from(*following)))
            {
                break;
            }
            self.pos += width;
        }
        let run = &self.source[start..self.pos];
        if !escaped {
            return Ast::Literal(self.source_literal(start, self.pos));
        }
        let mut literal = String::with_capacity(run.len());
        let mut scalars = run.chars();
        while let Some(scalar) = scalars.next() {
            if scalar == '\\' {
                literal.push(scalars.next().expect("absorbed escapes are complete"));
            } else {
                literal.push(scalar);
            }
        }
        Ast::Literal(literal.into())
    }

    fn parse_group(&mut self) -> Ast {
        if self.depth >= MAX_PARSE_DEPTH {
            self.skip_balanced('(', ')');
            self.diagnostic(
                self.char_index(self.pos),
                "maximum group nesting depth exceeded".to_string(),
            );
            return Ast::Unsupported("nesting too deep".to_string());
        }
        self.depth += 1;
        let parsed = self.parse_group_inner();
        self.depth -= 1;
        parsed
    }

    /// Consumes input up to and including the delimiter matching the opener
    /// that was already consumed, tracking nesting and escapes. Used only on
    /// the over-deep degradation path; bracket imprecision inside classes is
    /// acceptable there.
    fn skip_balanced(&mut self, opener: char, closer: char) {
        let mut balance = 1usize;
        while balance > 0 {
            let Some(ch) = self.bump() else {
                break;
            };
            match ch {
                '\\' => {
                    self.bump();
                }
                ch if ch == opener => balance += 1,
                ch if ch == closer => balance -= 1,
                _ => {}
            }
        }
    }

    fn parse_group_inner(&mut self) -> Ast {
        if self.peek() != Some('?') {
            let index = self.alloc_capture(None);
            let outer = self.flags;
            let child = self.parse_alternation(Some(')'));
            self.flags = outer;
            self.expect(')');
            return Ast::Group {
                index: Some(index),
                name: None,
                child: Box::new(child),
            };
        }
        self.bump();
        match self.peek() {
            Some(':') => {
                self.bump();
                let outer = self.flags;
                let child = self.parse_alternation(Some(')'));
                self.flags = outer;
                self.expect(')');
                child
            }
            Some('=') => {
                self.bump();
                self.features.lookahead = true;
                let outer = self.flags;
                let child = self.parse_alternation(Some(')'));
                self.flags = outer;
                self.expect(')');
                Ast::Look {
                    kind: LookKind::Ahead,
                    child: Box::new(child),
                }
            }
            Some('!') => {
                self.bump();
                self.features.lookahead = true;
                let outer = self.flags;
                let child = self.parse_alternation(Some(')'));
                self.flags = outer;
                self.expect(')');
                Ast::Look {
                    kind: LookKind::NotAhead,
                    child: Box::new(child),
                }
            }
            Some('<') => {
                self.bump();
                match self.peek() {
                    Some('=') => {
                        self.bump();
                        self.features.lookbehind = true;
                        let outer = self.flags;
                        let child = self.parse_alternation(Some(')'));
                        self.flags = outer;
                        self.expect(')');
                        Ast::Look {
                            kind: LookKind::Behind,
                            child: Box::new(child),
                        }
                    }
                    Some('!') => {
                        self.bump();
                        self.features.lookbehind = true;
                        let outer = self.flags;
                        let child = self.parse_alternation(Some(')'));
                        self.flags = outer;
                        self.expect(')');
                        Ast::Look {
                            kind: LookKind::NotBehind,
                            child: Box::new(child),
                        }
                    }
                    _ => {
                        let name = self.take_until(b'>').to_owned();
                        self.expect('>');
                        self.features.named_group = true;
                        let index = self.alloc_capture(Some(name.clone()));
                        let outer = self.flags;
                        let child = self.parse_alternation(Some(')'));
                        self.flags = outer;
                        self.expect(')');
                        Ast::Group {
                            index: Some(index),
                            name: Some(name),
                            child: Box::new(child),
                        }
                    }
                }
            }
            Some('P') if self.peek_second() == Some('<') => {
                self.bump();
                self.bump();
                let name = self.take_until(b'>').to_owned();
                self.expect('>');
                self.features.named_group = true;
                let index = self.alloc_capture(Some(name.clone()));
                let outer = self.flags;
                let child = self.parse_alternation(Some(')'));
                self.flags = outer;
                self.expect(')');
                Ast::Group {
                    index: Some(index),
                    name: Some(name),
                    child: Box::new(child),
                }
            }
            Some('>') => {
                self.bump();
                self.features.possessive_or_atomic = true;
                let outer = self.flags;
                let child = self.parse_alternation(Some(')'));
                self.flags = outer;
                self.expect(')');
                Ast::Repeat {
                    node: Box::new(child),
                    min: 1,
                    max: Some(1),
                    greedy: true,
                    possessive: true,
                    atomic: true,
                }
            }
            Some('#') => {
                self.bump();
                self.take_until(b')');
                self.expect(')');
                Ast::Empty
            }
            Some('(') => {
                self.features.conditional = true;
                let outer = self.flags;
                let conditional = self.parse_conditional();
                self.flags = outer;
                conditional
            }
            Some(ch) if is_flag_char(ch) || ch == '-' => self.parse_flag_group(),
            _ => {
                self.features.unsupported_escape = true;
                let rest = self.take_until(b')');
                self.expect(')');
                Ast::Unsupported(format!("unsupported group (?{rest})"))
            }
        }
    }

    fn parse_conditional(&mut self) -> Ast {
        self.bump(); // condition's opening `(`
        let raw = self.take_until(b')');
        self.expect(')');
        let condition = if let Ok(index) = raw.parse::<u32>() {
            Some(Backref::Number(index))
        } else if let Some(name) = raw.strip_prefix('<').and_then(|raw| raw.strip_suffix('>')) {
            Some(Backref::Name(name.to_owned()))
        } else {
            raw.strip_prefix('\'')
                .and_then(|raw| raw.strip_suffix('\''))
                .map(|name| Backref::Name(name.to_owned()))
        };

        let matched = self.parse_concat(Some(')'));
        let unmatched = if self.peek() == Some('|') {
            self.bump();
            self.parse_alternation(Some(')'))
        } else {
            Ast::Empty
        };
        self.expect(')');
        condition.map_or_else(
            || {
                self.diagnostic(
                    self.char_index(self.pos),
                    format!("unsupported conditional test ({raw})"),
                );
                Ast::Unsupported("conditional-test".to_owned())
            },
            |condition| Ast::Conditional {
                condition,
                matched: Box::new(matched),
                unmatched: Box::new(unmatched),
            },
        )
    }

    fn parse_flag_group(&mut self) -> Ast {
        let mut local = self.flags;
        let mut negating = false;
        while let Some(ch) = self.peek() {
            match ch {
                'i' | 'm' | 's' | 'x' => {
                    self.features.inline_flags = true;
                    self.bump();
                    apply_flag(&mut local, ch, !negating);
                }
                '-' => {
                    self.features.inline_flags = true;
                    self.bump();
                    negating = true;
                }
                ':' => {
                    self.bump();
                    let outer = self.flags;
                    self.flags = local;
                    let child = self.parse_alternation(Some(')'));
                    self.flags = outer;
                    self.expect(')');
                    // Keep an explicit snapshot even when `local` is the
                    // default. An enclosing bare option change may otherwise
                    // wrap this child and erase a scoped `(?-i:...)` reset.
                    return Ast::Flags {
                        flags: local,
                        child: Box::new(child),
                    };
                }
                ')' => {
                    self.bump();
                    self.flags = local;
                    return flag_change_marker(local);
                }
                _ => break,
            }
        }
        self.features.unsupported_escape = true;
        Ast::Unsupported("malformed inline flags".to_owned())
    }

    fn parse_class(&mut self) -> Ast {
        Ast::Class(self.parse_class_body())
    }

    fn parse_class_body(&mut self) -> CharClass {
        if self.depth >= MAX_PARSE_DEPTH {
            self.skip_balanced('[', ']');
            self.diagnostic(
                self.char_index(self.pos),
                "maximum class nesting depth exceeded".to_string(),
            );
            return CharClass::default();
        }
        self.depth += 1;
        let parsed = self.parse_class_body_inner();
        self.depth -= 1;
        parsed
    }

    fn parse_class_body_inner(&mut self) -> CharClass {
        let mut class = CharClass {
            bracketed: true,
            ..CharClass::default()
        };
        if self.peek() == Some('^') {
            self.bump();
            class.negated = true;
        }
        // The union being read accumulates on the scratch atom stack from
        // `base`; nested classes use and release the stack above it. The
        // first union becomes `atoms`, each one after `&&` an intersection.
        let base = self.class_atoms.len();
        let mut first_union = true;
        // Oniguruma treats `]` as a literal when it is the first class atom,
        // e.g. `[]),;}]`. Several VS Code TypeScript rules rely on this form.
        if self.peek() == Some(']') {
            self.bump();
            self.class_atoms.push(ClassAtom::Char(']'));
        }
        while let Some(ch) = self.peek() {
            if ch == ']' {
                self.bump();
                break;
            }
            if ch == '&' && self.peek_second() == Some('&') {
                self.bump();
                self.bump();
                self.finish_class_union(&mut class, base, &mut first_union);
                continue;
            }
            let atom = self.read_class_atom();
            if let ClassAtom::Char(start) = atom {
                if self.peek() == Some('-') && self.peek_second().is_some_and(|next| next != ']') {
                    self.bump();
                    let end_atom = self.read_class_atom();
                    if let ClassAtom::Char(end) = end_atom {
                        self.class_atoms.push(ClassAtom::Range(start, end));
                    } else {
                        self.class_atoms.push(ClassAtom::Char(start));
                        self.class_atoms.push(ClassAtom::Char('-'));
                        self.class_atoms.push(end_atom);
                    }
                    continue;
                }
                self.class_atoms.push(ClassAtom::Char(start));
            } else {
                self.class_atoms.push(atom);
            }
        }
        self.finish_class_union(&mut class, base, &mut first_union);
        class
    }

    fn finish_class_union(&mut self, class: &mut CharClass, base: usize, first_union: &mut bool) {
        let union = self.class_atoms.drain(base..).collect();
        if std::mem::take(first_union) {
            class.atoms = union;
        } else {
            class.intersections.push(union);
        }
    }

    fn read_class_atom(&mut self) -> ClassAtom {
        let Some(ch) = self.peek() else {
            return ClassAtom::Char('\0');
        };
        if ch == '[' && self.peek_second() == Some(':') {
            self.bump();
            self.bump();
            let mut negated = false;
            if self.peek() == Some('^') {
                self.bump();
                negated = true;
            }
            let start = self.pos;
            let mut end = self.bytes.len();
            while let Some(next) = self.peek() {
                if next == ':' && self.peek_second() == Some(']') {
                    end = self.pos;
                    self.bump();
                    self.bump();
                    break;
                }
                self.bump();
            }
            self.features.unicode_or_posix_class = true;
            return ClassAtom::Posix {
                name: self.source[start..end].to_owned(),
                negated,
            };
        }
        if ch == '[' {
            self.bump();
            return ClassAtom::Nested(Box::new(self.parse_class_body()));
        }
        if ch == '\\' {
            self.bump();
            return self.class_escape();
        }
        self.bump();
        ClassAtom::Char(ch)
    }

    fn class_escape(&mut self) -> ClassAtom {
        let Some(ch) = self.bump() else {
            return ClassAtom::Char('\\');
        };
        match ch {
            'd' => ClassAtom::Perl(PerlClassKind::Digit),
            'D' => ClassAtom::Perl(PerlClassKind::NotDigit),
            's' => ClassAtom::Perl(PerlClassKind::Space),
            'S' => ClassAtom::Perl(PerlClassKind::NotSpace),
            'w' => ClassAtom::Perl(PerlClassKind::Word),
            'W' => ClassAtom::Perl(PerlClassKind::NotWord),
            'h' => ClassAtom::Perl(PerlClassKind::HorizontalSpace),
            'H' => ClassAtom::Perl(PerlClassKind::NotHorizontalSpace),
            'v' => ClassAtom::Perl(PerlClassKind::VerticalSpace),
            'V' => ClassAtom::Perl(PerlClassKind::NotVerticalSpace),
            'N' => ClassAtom::Perl(PerlClassKind::NotNewline),
            'p' | 'P' if self.peek() == Some('{') => {
                self.bump();
                let name = self.take_until(b'}').to_owned();
                self.expect('}');
                self.features.unicode_or_posix_class = true;
                ClassAtom::Unicode {
                    name,
                    negated: ch == 'P',
                }
            }
            'x' => {
                let digits = if self.peek() == Some('{') {
                    self.bump();
                    let digits = self.take_until(b'}');
                    self.expect('}');
                    digits
                } else {
                    self.take_hex_digits(2)
                };
                let chars = digits
                    .split_ascii_whitespace()
                    .map(hex_char)
                    .collect::<Option<Vec<_>>>();
                match chars.as_deref() {
                    Some([ch]) => ClassAtom::Char(*ch),
                    Some(chars) if !chars.is_empty() => ClassAtom::Nested(Box::new(CharClass {
                        bracketed: true,
                        negated: false,
                        intersections: Vec::new(),
                        atoms: chars.iter().copied().map(ClassAtom::Char).collect(),
                    })),
                    _ => ClassAtom::Char('x'),
                }
            }
            'u' => {
                let digits = self.take_hex_digits(4);
                ClassAtom::Char(hex_char(digits).unwrap_or('u'))
            }
            _ => ClassAtom::Char(unescape_char(ch)),
        }
    }

    fn parse_escape(&mut self, in_class: bool) -> Ast {
        let Some(ch) = self.bump() else {
            return Ast::Literal("\\".into());
        };
        match ch {
            'A' => {
                self.features.anchor_a = true;
                Ast::Anchor(AnchorKind::TextStart)
            }
            'G' => {
                self.features.anchor_g = true;
                Ast::Anchor(AnchorKind::Continuation)
            }
            'z' => Ast::Anchor(AnchorKind::TextEnd),
            'Z' => Ast::Anchor(AnchorKind::TextEndOrFinalNewline),
            'b' if !in_class => Ast::Anchor(AnchorKind::WordBoundary),
            'B' if !in_class => Ast::Anchor(AnchorKind::NotWordBoundary),
            'd' => Ast::Class(CharClass {
                bracketed: false,
                negated: false,
                intersections: Vec::new(),
                atoms: vec![ClassAtom::Perl(PerlClassKind::Digit)],
            }),
            'D' => Ast::Class(CharClass {
                bracketed: false,
                negated: false,
                intersections: Vec::new(),
                atoms: vec![ClassAtom::Perl(PerlClassKind::NotDigit)],
            }),
            's' => Ast::Class(CharClass {
                bracketed: false,
                negated: false,
                intersections: Vec::new(),
                atoms: vec![ClassAtom::Perl(PerlClassKind::Space)],
            }),
            'S' => Ast::Class(CharClass {
                bracketed: false,
                negated: false,
                intersections: Vec::new(),
                atoms: vec![ClassAtom::Perl(PerlClassKind::NotSpace)],
            }),
            'w' => Ast::Class(CharClass {
                bracketed: false,
                negated: false,
                intersections: Vec::new(),
                atoms: vec![ClassAtom::Perl(PerlClassKind::Word)],
            }),
            'W' => Ast::Class(CharClass {
                bracketed: false,
                negated: false,
                intersections: Vec::new(),
                atoms: vec![ClassAtom::Perl(PerlClassKind::NotWord)],
            }),
            'h' => Ast::Class(CharClass {
                bracketed: false,
                negated: false,
                intersections: Vec::new(),
                atoms: vec![ClassAtom::Perl(PerlClassKind::HorizontalSpace)],
            }),
            'H' => Ast::Class(CharClass {
                bracketed: false,
                negated: false,
                intersections: Vec::new(),
                atoms: vec![ClassAtom::Perl(PerlClassKind::NotHorizontalSpace)],
            }),
            'v' => Ast::Class(CharClass {
                bracketed: false,
                negated: false,
                intersections: Vec::new(),
                atoms: vec![ClassAtom::Perl(PerlClassKind::VerticalSpace)],
            }),
            'V' => Ast::Class(CharClass {
                bracketed: false,
                negated: false,
                intersections: Vec::new(),
                atoms: vec![ClassAtom::Perl(PerlClassKind::NotVerticalSpace)],
            }),
            'N' => Ast::Class(CharClass {
                bracketed: false,
                negated: false,
                intersections: Vec::new(),
                atoms: vec![ClassAtom::Perl(PerlClassKind::NotNewline)],
            }),
            'X' => Ast::Grapheme,
            'p' | 'P' if self.peek() == Some('{') => {
                self.bump();
                let name = self.take_until(b'}').to_owned();
                self.expect('}');
                self.features.unicode_or_posix_class = true;
                Ast::Class(CharClass {
                    bracketed: false,
                    negated: false,
                    intersections: Vec::new(),
                    atoms: vec![ClassAtom::Unicode {
                        name,
                        negated: ch == 'P',
                    }],
                })
            }
            'k' if self.peek() == Some('<') => {
                self.bump();
                let name = self.take_until(b'>').to_owned();
                self.expect('>');
                self.features.backreference = true;
                Ast::Backref(Backref::Name(name))
            }
            'g' if self.peek() == Some('<') => {
                self.bump();
                let name = self.take_until(b'>').to_owned();
                self.expect('>');
                self.features.subroutine = true;
                if let Ok(index) = name.parse::<u32>() {
                    Ast::Subroutine(Box::new(SubroutineCall {
                        target: Backref::Number(index),
                        target_path: None,
                    }))
                } else {
                    Ast::Subroutine(Box::new(SubroutineCall {
                        target: Backref::Name(name),
                        target_path: None,
                    }))
                }
            }
            '1'..='9' => {
                let mut number = ch.to_digit(10).unwrap_or(0);
                while let Some(next @ '0'..='9') = self.peek() {
                    let digit = next.to_digit(10).unwrap_or(0);
                    // Hostile `\1` + long digit runs must not overflow; stop
                    // absorbing digits once the backref index no longer fits.
                    let Some(next_number) = number
                        .checked_mul(10)
                        .and_then(|value| value.checked_add(digit))
                    else {
                        break;
                    };
                    self.bump();
                    number = next_number;
                }
                self.features.backreference = true;
                Ast::Backref(Backref::Number(number))
            }
            'x' if self.peek() == Some('{') => {
                self.bump();
                let digits = self.take_until(b'}');
                self.expect('}');
                Ast::Literal(hex_char(digits).unwrap_or('\u{FFFD}').to_string().into())
            }
            'x' => {
                let digits = self.take_hex_digits(2);
                Ast::Literal(hex_char(digits).unwrap_or('x').to_string().into())
            }
            'u' => {
                let digits = self.take_hex_digits(4);
                Ast::Literal(hex_char(digits).unwrap_or('u').to_string().into())
            }
            'R' => Ast::Alternation(vec![
                Ast::Literal("\r\n".into()),
                Ast::Class(CharClass {
                    bracketed: false,
                    negated: false,
                    intersections: Vec::new(),
                    atoms: vec![
                        ClassAtom::Char('\n'),
                        ClassAtom::Char('\r'),
                        ClassAtom::Char('\u{000B}'),
                        ClassAtom::Char('\u{000C}'),
                        ClassAtom::Char('\u{0085}'),
                        ClassAtom::Char('\u{2028}'),
                        ClassAtom::Char('\u{2029}'),
                    ],
                }),
            ]),
            _ => Ast::Literal(unescape_char(ch).to_string().into()),
        }
    }

    fn parse_braced_quantifier(&mut self) -> Option<(usize, Option<usize>, bool)> {
        let saved = self.pos;
        self.bump(); // {
        let min_digits = self.take_digits();
        if min_digits.is_empty() {
            if self.peek() != Some(',') {
                self.pos = saved;
                return None;
            }
            self.bump();
            let max_digits = self.take_digits();
            let Some(max) = max_digits.parse::<usize>().ok() else {
                self.pos = saved;
                return None;
            };
            if self.peek() != Some('}') {
                self.pos = saved;
                return None;
            }
            self.bump();
            return Some((0, Some(max), false));
        }
        let min = min_digits.parse::<usize>().ok()?;
        let is_braced_exact = self.peek() != Some(',');
        let max = if !is_braced_exact {
            self.bump();
            let max_digits = self.take_digits();
            if max_digits.is_empty() {
                None
            } else {
                Some(max_digits.parse::<usize>().ok()?)
            }
        } else {
            Some(min)
        };
        if self.peek() != Some('}') {
            self.pos = saved;
            return None;
        }
        self.bump();
        Some((min, max, is_braced_exact))
    }

    fn alloc_capture(&mut self, name: Option<String>) -> u32 {
        let index = self.next_capture;
        self.next_capture += 1;
        if let Some(name) = name {
            if let Some(last) = self.named_captures.get_mut(&name) {
                let previous = std::mem::replace(last, index);
                self.duplicate_names
                    .entry(name)
                    .or_insert_with(|| vec![previous])
                    .push(index);
            } else {
                self.named_captures.insert(name, index);
            }
        }
        index
    }

    fn take_digits(&mut self) -> &'a str {
        let start = self.pos;
        while self.bytes.get(self.pos).is_some_and(u8::is_ascii_digit) {
            self.pos += 1;
        }
        &self.source[start..self.pos]
    }

    fn take_hex_digits(&mut self, limit: usize) -> &'a str {
        let start = self.pos;
        while self.pos - start < limit
            && self.bytes.get(self.pos).is_some_and(u8::is_ascii_hexdigit)
        {
            self.pos += 1;
        }
        &self.source[start..self.pos]
    }

    /// Consumes input up to, not including, the first ASCII `terminator`.
    fn take_until(&mut self, terminator: u8) -> &'a str {
        let start = self.pos;
        let rest = &self.bytes[start..];
        self.pos = memchr::memchr(terminator, rest).map_or(self.bytes.len(), |end| start + end);
        &self.source[start..self.pos]
    }

    fn diagnostic(&mut self, position: usize, message: String) {
        self.first_diagnostic_position.get_or_insert(position);
        self.diagnostics.push(message);
    }

    fn expect(&mut self, expected: char) {
        if self.peek() == Some(expected) {
            self.bump();
        } else {
            let at = self.char_index(self.pos);
            self.diagnostic(at, format!("expected '{expected}' at char {at}"));
        }
    }

    /// Scalar index of a byte offset; diagnostics report scalar positions.
    fn char_index(&self, byte: usize) -> usize {
        self.source[..byte].chars().count()
    }

    #[inline]
    fn char_at(&self, pos: usize) -> Option<char> {
        let byte = *self.bytes.get(pos)?;
        if byte.is_ascii() {
            Some(char::from(byte))
        } else {
            self.source[pos..].chars().next()
        }
    }

    #[inline]
    fn peek(&self) -> Option<char> {
        self.char_at(self.pos)
    }

    /// The scalar after the next one.
    fn peek_second(&self) -> Option<char> {
        let first = self.peek()?;
        self.char_at(self.pos + first.len_utf8())
    }

    #[inline]
    fn bump(&mut self) -> Option<char> {
        let ch = self.peek()?;
        self.pos += ch.len_utf8();
        Some(ch)
    }
}

fn normalize_flag_changes(mut branches: Vec<Ast>) -> Ast {
    // Most branches contain no bare option change. They are already in the
    // shape the rewrite below would rebuild, so skip taking them apart.
    let needs_rewrite = |branch: &Ast| match branch {
        Ast::Concat(nodes) => {
            nodes.len() < 2 || nodes.iter().any(|node| flag_change_flags(node).is_some())
        }
        node => flag_change_flags(node).is_some(),
    };
    if !branches.iter().any(needs_rewrite) {
        return alternation_ast(branches);
    }
    for branch_index in 0..branches.len() {
        // Branches without an option-change marker are left in place; only
        // a branch that needs restructuring is unpacked into a sequence.
        if !has_flag_change_marker(&branches[branch_index]) {
            if let Ast::Concat(nodes) = &mut branches[branch_index]
                && nodes.len() < 2
            {
                let nodes = std::mem::take(nodes);
                branches[branch_index] = concat_ast(nodes);
            }
            continue;
        }
        let branch = std::mem::replace(&mut branches[branch_index], Ast::Empty);
        let mut nodes = match branch {
            Ast::Concat(nodes) => nodes,
            node => vec![node],
        };
        let Some(change_index) = nodes
            .iter()
            .position(|node| flag_change_flags(node).is_some())
        else {
            branches[branch_index] = concat_ast(nodes);
            continue;
        };
        let flags = flag_change_flags(&nodes.remove(change_index)).expect("flag marker");
        let prefix = nodes.drain(..change_index).collect::<Vec<_>>();
        let mut remainder = vec![concat_ast(nodes)];
        remainder.extend(branches.drain(branch_index + 1..));
        let scoped_remainder = Ast::Flags {
            flags,
            child: Box::new(normalize_flag_changes(remainder)),
        };
        let mut transformed = prefix;
        transformed.push(scoped_remainder);
        branches[branch_index] = concat_ast(transformed);
        break;
    }
    alternation_ast(branches)
}

/// Whether a parsed branch contains a bare option change (`(?i)`) that
/// `normalize_flag_changes` must scope over the rest of the alternation.
fn has_flag_change_marker(branch: &Ast) -> bool {
    match branch {
        Ast::Concat(nodes) => nodes.iter().any(|node| flag_change_flags(node).is_some()),
        node => flag_change_flags(node).is_some(),
    }
}

fn flag_change_marker(flags: RegexFlags) -> Ast {
    let bits = u8::from(flags.case_insensitive)
        | (u8::from(flags.multi_line) << 1)
        | (u8::from(flags.dot_matches_new_line) << 2)
        | (u8::from(flags.ignore_whitespace) << 3);
    Ast::Unsupported(format!("\0option-change:{bits}"))
}

fn flag_change_flags(ast: &Ast) -> Option<RegexFlags> {
    let Ast::Unsupported(marker) = ast else {
        return None;
    };
    let bits = marker
        .strip_prefix("\0option-change:")?
        .parse::<u8>()
        .ok()?;
    Some(RegexFlags {
        case_insensitive: bits & 1 != 0,
        multi_line: bits & 2 != 0,
        dot_matches_new_line: bits & 4 != 0,
        ignore_whitespace: bits & 8 != 0,
    })
}

fn concat_ast(mut nodes: Vec<Ast>) -> Ast {
    match nodes.len() {
        0 => Ast::Empty,
        1 => nodes.pop().expect("one concat node"),
        _ => Ast::Concat(nodes),
    }
}

fn alternation_ast(mut branches: Vec<Ast>) -> Ast {
    match branches.len() {
        0 => Ast::Empty,
        1 => branches.pop().expect("one alternation branch"),
        _ => Ast::Alternation(branches),
    }
}

/// Appends `node` to the sequence occupying `nodes[base..]`, coalescing
/// adjacent literals (and adjacent literals under identical option
/// snapshots) with the sequence's last node.
fn push_concat_node(nodes: &mut Vec<Ast>, base: usize, node: Ast) {
    let previous = if nodes.len() > base {
        nodes.last_mut()
    } else {
        None
    };
    match (previous, &node) {
        (Some(Ast::Literal(previous)), Ast::Literal(literal)) => previous.push_literal(literal),
        // Keep option snapshots compact. Without this, `(?i:keyword)` becomes
        // one flag node per scalar and defeats literal/alternation fast paths.
        (
            Some(Ast::Flags {
                flags: previous_flags,
                child: previous_child,
            }),
            Ast::Flags { flags, child },
        ) if previous_flags == flags
            && matches!(previous_child.as_ref(), Ast::Literal(_))
            && matches!(child.as_ref(), Ast::Literal(_)) =>
        {
            if let (Ast::Literal(previous), Ast::Literal(literal)) =
                (previous_child.as_mut(), child.as_ref())
            {
                previous.push_literal(literal);
            }
        }
        _ => nodes.push(node),
    }
}

fn is_flag_char(ch: char) -> bool {
    matches!(ch, 'i' | 'm' | 's' | 'x')
}

fn apply_flag(flags: &mut RegexFlags, flag: char, value: bool) {
    match flag {
        'i' => flags.case_insensitive = value,
        'm' => flags.multi_line = value,
        's' => flags.dot_matches_new_line = value,
        'x' => flags.ignore_whitespace = value,
        _ => {}
    }
}

fn unescape_char(ch: char) -> char {
    match ch {
        'n' => '\n',
        'r' => '\r',
        't' => '\t',
        'f' => '\u{000C}',
        'a' => '\u{0007}',
        'e' => '\u{001B}',
        other => other,
    }
}

fn hex_char(digits: &str) -> Option<char> {
    u32::from_str_radix(digits, 16)
        .ok()
        .and_then(char::from_u32)
}

impl fmt::Display for ParsedRegex {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        writeln!(f, "source: {}", self.source)?;
        writeln!(f, "route: {}", self.route_reason())?;
        writeln!(f, "captures: {}", self.capture_count)?;
        writeln!(f, "features: {:?}", self.features)?;
        if !self.diagnostics.is_empty() {
            writeln!(f, "diagnostics: {:?}", self.diagnostics)?;
        }
        writeln!(f, "ast: {:#?}", self.ast)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn classifies_fallback_features() {
        let parsed = parse(r"(?<=foo)(bar)\1\G");
        assert!(parsed.features.lookbehind);
        assert!(parsed.features.backreference);
        assert!(parsed.features.anchor_g);
        assert!(parsed.features.requires_fallback());
        assert_eq!(parsed.capture_count, 1);
    }

    #[test]
    fn deep_group_nesting_degrades_instead_of_overflowing() {
        // Regression: unbounded recursion aborted the process around tens of
        // thousands of nested groups. The parser must degrade gracefully.
        let depth = 200_000;
        let pattern = format!("{}a{}", "(".repeat(depth), ")".repeat(depth));
        let parsed = parse(&pattern);
        assert!(
            parsed
                .diagnostics
                .iter()
                .any(|note| note.contains("nesting depth")),
            "expected a depth diagnostic"
        );
        let contains_unsupported = {
            let mut found = false;
            let mut node = &parsed.ast;
            loop {
                match node {
                    Ast::Unsupported(_) => {
                        found = true;
                        break;
                    }
                    Ast::Group { child, .. } => node = child,
                    _ => break,
                }
            }
            found
        };
        assert!(contains_unsupported, "expected an Unsupported node");
    }

    #[test]
    fn deep_class_nesting_degrades_instead_of_overflowing() {
        let depth = 200_000;
        let pattern = format!("{}a{}", "[".repeat(depth), "]".repeat(depth));
        let parsed = parse(&pattern);
        assert!(
            parsed
                .diagnostics
                .iter()
                .any(|note| note.contains("nesting depth"))
        );
    }

    #[test]
    fn nesting_below_the_limit_still_parses_on_a_small_stack() {
        let parsed_depth = std::thread::Builder::new()
            .stack_size(1024 * 1024)
            .spawn(|| {
                let depth = MAX_PARSE_DEPTH - 2;
                let pattern = format!("{}\\g<1>{}", "(".repeat(depth), ")".repeat(depth));
                let parsed = parse(&pattern);
                assert!(parsed.diagnostics.is_empty());
                parsed.initialize_analysis();
                let mut depth_count = 0usize;
                let mut node = &parsed.ast;
                while let Ast::Group { child, .. } = node {
                    depth_count += 1;
                    node = child;
                }
                depth_count
            })
            .expect("small-stack parser thread starts")
            .join()
            .expect("small-stack parser thread does not overflow");
        assert_eq!(parsed_depth, MAX_PARSE_DEPTH - 2);
    }

    #[test]
    fn parses_named_captures_and_flags() {
        let parsed = parse(r"(?i:(?<name>foo|bar)+)");
        assert!(parsed.features.named_group);
        assert!(parsed.features.inline_flags);
        assert_eq!(parsed.named_captures.get("name"), Some(&1));
    }

    #[test]
    fn parses_posix_class() {
        let parsed = parse(r"[[:alpha:]_][[:alnum:]_]*");
        assert!(parsed.features.unicode_or_posix_class);
        assert!(!parsed.features.requires_fallback());
    }

    #[test]
    fn parses_leading_closing_bracket_as_a_class_literal() {
        let parsed = parse(r"[]),;}]");
        assert_eq!(
            parsed.ast,
            Ast::Class(CharClass {
                bracketed: true,
                negated: false,
                intersections: Vec::new(),
                atoms: vec![
                    ClassAtom::Char(']'),
                    ClassAtom::Char(')'),
                    ClassAtom::Char(','),
                    ClassAtom::Char(';'),
                    ClassAtom::Char('}'),
                ],
            })
        );
    }

    #[test]
    fn parses_oniguruma_nested_non_ascii_class_and_hex_escapes() {
        let parsed = parse(r"[-A-Z[^\x00-\x7F]]");
        let Ast::Class(class) = parsed.ast else {
            panic!("expected class");
        };
        assert_eq!(class.atoms[0], ClassAtom::Char('-'));
        assert_eq!(class.atoms[1], ClassAtom::Range('A', 'Z'));
        assert_eq!(
            class.atoms[2],
            ClassAtom::Nested(Box::new(CharClass {
                bracketed: true,
                negated: true,
                intersections: Vec::new(),
                atoms: vec![ClassAtom::Range('\0', '\u{7f}')],
            }))
        );
    }

    #[test]
    fn parses_oniguruma_multi_codepoint_hex_class_escape() {
        let parsed = parse(r"[^\x{FEFF FFFE FFFF}]");
        let Ast::Class(class) = parsed.ast else {
            panic!("expected class");
        };
        assert!(class.negated);
        assert!(matches!(
            class.atoms.as_slice(),
            [ClassAtom::Nested(nested)]
                if nested.atoms == [
                    ClassAtom::Char('\u{feff}'),
                    ClassAtom::Char('\u{fffe}'),
                    ClassAtom::Char('\u{ffff}'),
                ]
        ));
    }

    #[test]
    fn parses_nested_class_intersection_as_intersected_unions() {
        let parsed = parse(r#"[[\p{S}\p{P}]&&[^]"'(),;\[_`{}]]+"#);
        let Ast::Repeat { node, .. } = parsed.ast else {
            panic!("expected repeated class");
        };
        let Ast::Class(class) = *node else {
            panic!("expected class");
        };
        assert_eq!(class.atoms.len(), 1);
        assert_eq!(class.intersections.len(), 1);
        assert!(matches!(
            &class.atoms[0],
            ClassAtom::Nested(nested)
                if matches!(
                    nested.atoms.as_slice(),
                    [
                        ClassAtom::Unicode { name: symbol, negated: false },
                        ClassAtom::Unicode { name: punctuation, negated: false },
                    ] if symbol == "S" && punctuation == "P"
                )
        ));
        assert!(matches!(
            class.intersections[0].as_slice(),
            [ClassAtom::Nested(nested)]
                if nested.negated
                    && nested.atoms.first() == Some(&ClassAtom::Char(']'))
                    && nested.atoms.contains(&ClassAtom::Char('['))
        ));
    }

    #[test]
    fn intersection_rhs_is_a_union_and_chained_intersections_are_preserved() {
        let parsed = parse(r"[a-w&&[^c-g]z&&[^x]]");
        let Ast::Class(class) = parsed.ast else {
            panic!("expected class");
        };
        assert_eq!(class.atoms, vec![ClassAtom::Range('a', 'w')]);
        assert_eq!(class.intersections.len(), 2);
        assert!(matches!(
            class.intersections[0].as_slice(),
            [ClassAtom::Nested(nested), ClassAtom::Char('z')]
                if nested.negated && nested.atoms == [ClassAtom::Range('c', 'g')]
        ));
        assert!(matches!(
            class.intersections[1].as_slice(),
            [ClassAtom::Nested(nested)]
                if nested.negated && nested.atoms == [ClassAtom::Char('x')]
        ));
    }

    #[test]
    fn coalesces_adjacent_literals() {
        let parsed = parse("return");
        assert_eq!(parsed.ast, Ast::Literal("return".into()));
        // Escaped scalars merge into the preceding run even when the whole
        // branch collapses to one node.
        assert_eq!(parse(r"a\.é").ast, Ast::Literal("a.é".into()));
        assert_eq!(parse(r"\(\\\)x").ast, Ast::Literal(r"(\)x".into()));
        // A quantified escape binds alone, exactly as a quantified scalar.
        let Ast::Concat(nodes) = parse(r"a\.+\-").ast else {
            panic!("expected concat");
        };
        assert_eq!(nodes[0], Ast::Literal("a".into()));
        assert!(
            matches!(&nodes[1], Ast::Repeat { node, .. } if **node == Ast::Literal(".".into()))
        );
        assert_eq!(nodes[2], Ast::Literal("-".into()));
        // Escaped whitespace and comment markers stay literal in extended mode.
        let Ast::Flags { child, .. } = parse(r"(?x: a \ b \# c )").ast else {
            panic!("expected option scope");
        };
        assert!(matches!(child.as_ref(), Ast::Flags { child, .. }
            if **child == Ast::Literal("a b#c".into())));
        assert_eq!(
            parse(r"x\.|y").ast,
            Ast::Alternation(vec![Ast::Literal("x.".into()), Ast::Literal("y".into()),])
        );
        // A trailing option change scopes only the rest of its branch and
        // the following branches, never the preceding literal.
        let Ast::Concat(nodes) = parse("ab(?i)c|d").ast else {
            panic!("expected scoped concat");
        };
        assert_eq!(nodes[0], Ast::Literal("ab".into()));
        let Ast::Flags { child, .. } = &nodes[1] else {
            panic!("expected option scope");
        };
        assert!(matches!(child.as_ref(), Ast::Alternation(branches) if branches.len() == 2));
    }

    #[test]
    fn oversized_numeric_backref_does_not_overflow() {
        let parsed = parse(r"\5555555555555555");
        assert!(parsed.features.backreference);
        assert!(
            matches!(
                parsed.ast,
                Ast::Concat(_) | Ast::Backref(Backref::Number(_))
            ),
            "oversized digit run must parse without panicking"
        );
        assert!(parse(r"\4294967295").features.backreference);
        assert!(matches!(parse(r"(a)\1").ast, Ast::Concat(_)));
    }

    #[test]
    fn multibyte_scalars_parse_by_scalar_not_byte() {
        // A quantifier binds to the whole preceding scalar, whatever its
        // UTF-8 width, and the run before it stays one literal.
        let Ast::Concat(nodes) = parse("日本語+").ast else {
            panic!("expected concat");
        };
        assert_eq!(nodes[0], Ast::Literal("日本".into()));
        assert!(
            matches!(&nodes[1], Ast::Repeat { node, min: 1, .. } if **node == Ast::Literal("語".into()))
        );
        let Ast::Repeat { node, .. } = parse("🛰?").ast else {
            panic!("expected repeat");
        };
        assert_eq!(*node, Ast::Literal("🛰".into()));
        // Escaped punctuation still coalesces across multi-byte neighbours.
        assert_eq!(parse(r"é\.ß\-").ast, Ast::Literal("é.ß-".into()));
        // Extended mode only skips Oniguruma's ASCII separators; NBSP stays
        // literal even when adjacent ASCII space is ignored.
        let Ast::Flags { child, .. } = parse("(?x:a\u{a0}é b)").ast else {
            panic!("expected option scope");
        };
        assert!(matches!(child.as_ref(), Ast::Flags { child, .. }
            if **child == Ast::Literal("a\u{a0}éb".into())));
        // Class ranges and POSIX names read whole scalars.
        let Ast::Class(class) = parse("[α-ω[:alpha:]é]").ast else {
            panic!("expected class");
        };
        assert_eq!(
            class.atoms,
            vec![
                ClassAtom::Range('α', 'ω'),
                ClassAtom::Posix {
                    name: "alpha".to_owned(),
                    negated: false,
                },
                ClassAtom::Char('é'),
            ]
        );
        // Unterminated POSIX names keep the remaining input.
        let Ast::Class(class) = parse("[[:é").ast else {
            panic!("expected class");
        };
        assert_eq!(
            class.atoms,
            vec![ClassAtom::Posix {
                name: "é".to_owned(),
                negated: false,
            }]
        );
    }

    #[test]
    fn diagnostics_report_scalar_positions() {
        assert_eq!(parse("é)").diagnostics, vec!["unmatched ')' at char 1"]);
        assert_eq!(parse("(日本").diagnostics, vec!["expected ')' at char 3"]);
        assert_eq!(
            parse("[é&&[^ß]x]y").ast,
            Ast::Concat(vec![
                Ast::Class(CharClass {
                    bracketed: true,
                    negated: false,
                    intersections: vec![vec![
                        ClassAtom::Nested(Box::new(CharClass {
                            bracketed: true,
                            negated: true,
                            intersections: Vec::new(),
                            atoms: vec![ClassAtom::Char('ß')],
                        })),
                        ClassAtom::Char('x'),
                    ]],
                    atoms: vec![ClassAtom::Char('é')],
                }),
                Ast::Literal("y".into()),
            ])
        );
    }

    #[test]
    fn does_not_coalesce_across_repeats_or_captures() {
        let parsed = parse("ab+c(d)e");
        let Ast::Concat(nodes) = parsed.ast else {
            panic!("expected concat");
        };
        assert_eq!(nodes.first(), Some(&Ast::Literal("a".into())));
        assert!(matches!(nodes.get(1), Some(Ast::Repeat { .. })));
        assert_eq!(nodes.get(2), Some(&Ast::Literal("c".into())));
        assert!(matches!(nodes.get(3), Some(Ast::Group { .. })));
        assert_eq!(nodes.get(4), Some(&Ast::Literal("e".into())));
    }

    #[test]
    fn parses_oniguruma_omitted_lower_repeat_bound() {
        let parsed = parse("`_{,2}");
        let Ast::Concat(nodes) = parsed.ast else {
            panic!("expected concatenation");
        };
        assert!(matches!(
            &nodes[1],
            Ast::Repeat {
                min: 0,
                max: Some(2),
                ..
            }
        ));
    }

    #[test]
    fn only_lexical_braced_exact_repeat_uses_oniguruma_optional_semantics() {
        let parsed = parse("a{2}?");
        assert!(matches!(
            parsed.ast,
            Ast::Repeat {
                min: 0,
                max: Some(1),
                node,
                ..
            } if matches!(
                *node,
                Ast::Repeat {
                    min: 2,
                    max: Some(2),
                    greedy: true,
                    ..
                }
            )
        ));

        let parsed = parse("a{2,2}?");
        assert!(matches!(
            parsed.ast,
            Ast::Repeat {
                min: 2,
                max: Some(2),
                greedy: false,
                ..
            }
        ));
    }

    #[test]
    fn resolves_named_subroutine_targets_to_ast_paths() {
        let parsed = parse(r"(?<pair>a)\g<pair>");
        let Ast::Concat(nodes) = &parsed.ast else {
            panic!("expected concat");
        };
        let Ast::Subroutine(call) = &nodes[1] else {
            panic!("expected subroutine call");
        };
        assert_eq!(call.target, Backref::Name("pair".to_owned()));
        assert_eq!(call.target_path, Some(vec![AstPathStep::Branch(0)]));
    }

    #[test]
    fn resolves_forward_subroutine_targets_after_parsing() {
        let parsed = parse(r"\g<word>(?<word>a)");
        let Ast::Concat(nodes) = &parsed.ast else {
            panic!("expected concat");
        };
        let Ast::Subroutine(call) = &nodes[0] else {
            panic!("expected subroutine call");
        };
        assert_eq!(call.target_path, Some(vec![AstPathStep::Branch(1)]));
    }
}