syntaxmate 0.2.0

use std::{
    ops::{Deref, DerefMut, Range},
    sync::{Arc, OnceLock},
};
use unicode_segmentation::UnicodeSegmentation;

use super::ast::{
    AnchorKind, Ast, AstPathStep, Backref, CharClass, ClassAtom, LookKind, ParsedRegex,
    PerlClassKind, RegexFlags, parse,
};
use super::bytecode::{BytecodeScratch, CompileError, Program};
use super::case_fold::CaseVariants;
use super::{AnchorContext, MatchResult, Matcher, is_unicode_word_char};

pub(crate) const DEFAULT_STEP_BUDGET: usize = 100_000;
const STATE_LIMIT: usize = 2048;
// Most branching expressions stay below this empirically measured fanout;
// reserving it on the first split avoids repeated growth in hot alternations.
const INITIAL_FANOUT_CAPACITY: usize = 16;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct StepBudget {
    limit: usize,
    remaining: usize,
    /// Nested subroutine calls in the recursive evaluator.
    call_depth: u32,
}

/// Subroutine nesting limit, matching the bytecode VM's call stack.
const MAX_SUBROUTINE_DEPTH: u32 = 128;

impl StepBudget {
    pub fn new(steps: usize) -> Self {
        Self {
            limit: steps,
            remaining: steps,
            call_depth: 0,
        }
    }

    pub fn step(&mut self) -> Result<(), BudgetExceeded> {
        if self.remaining == 0 {
            return Err(BudgetExceeded);
        }
        self.remaining -= 1;
        Ok(())
    }

    /// Charges `steps` units of work at once.
    pub(crate) fn charge(&mut self, steps: usize) -> Result<(), BudgetExceeded> {
        if self.remaining < steps {
            self.remaining = 0;
            return Err(BudgetExceeded);
        }
        self.remaining -= steps;
        Ok(())
    }

    pub fn used(&self) -> usize {
        self.limit - self.remaining
    }

    pub fn remaining(&self) -> usize {
        self.remaining
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct BudgetExceeded;

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum FallbackError {
    BudgetExceeded { steps: usize },
    InvalidStart { from: usize },
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct FallbackReport {
    pub result: Option<MatchResult>,
    pub steps: usize,
}

#[derive(Debug, Clone)]
pub struct FallbackMatcher {
    parsed: Arc<ParsedRegex>,
    bytecode: OnceLock<Option<SelectionProgram>>,
    /// Groups the owning pattern replays after selection. When present,
    /// selection may compile with these capture slots so that one program
    /// also serves capture replay instead of compiling the pattern twice.
    shared_captures: Option<Box<[u32]>>,
    special: Option<SpecialFallbackMatcher>,
    start_hint: StartHint,
    budget: usize,
    /// Process-unique id keying scan-local prefilter cursors. Assigned on
    /// first execution so construction does not build the prefilter.
    prefilter_slot: OnceLock<u32>,
}

#[derive(Debug, Clone)]
struct SelectionProgram {
    program: Arc<Program>,
    shares_captures: bool,
}

/// Capture layout requested for one anchored attempt. Selection defers the
/// choice until the attempt survives its cheap rejections.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum CaptureCount {
    Exact(usize),
    Selection,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum StartHint {
    Unanchored,
    /// Every branch begins with one of these anchors, so a match can only
    /// start where one of them holds (`(^|\G)x` needs no per-column scan).
    Anchored(StartAnchors),
}

#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
struct StartAnchors {
    line_start: bool,
    text_start: bool,
    continuation: bool,
}

impl StartAnchors {
    /// Mirrors `anchor_matches` for `^`, `\A`, and `\G`.
    fn allows(self, start: usize, ctx: AnchorContext) -> bool {
        (start == 0 && (self.line_start || (self.text_start && ctx.allow_a)))
            || (self.continuation && ctx.allow_g && start == ctx.g_pos)
    }

    fn union(self, other: Self) -> Self {
        Self {
            line_start: self.line_start || other.line_start,
            text_start: self.text_start || other.text_start,
            continuation: self.continuation || other.continuation,
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum SpecialFallbackMatcher {
    NixFunctionLookahead,
    NixExpressionEndLookahead,
}

impl SpecialFallbackMatcher {
    fn from_source(source: &str) -> Option<Self> {
        match source {
            r##"(?=(\b[A-Z_a-z][-'0-9A-Z_a-z]*\s*[:@]|\{[^"'}]*}\s*:|\{[^"#'/=}]*[,?]))"## => {
                Some(Self::NixFunctionLookahead)
            }
            r#"(?=([]),;}]|\b(else|then)\b))"# => Some(Self::NixExpressionEndLookahead),
            _ => None,
        }
    }

    fn match_at(&self, line: &str, start: usize, capture_count: usize) -> Option<MatchResult> {
        match self {
            Self::NixFunctionLookahead => nix_function_lookahead_match(line, start)
                .map(|capture| zero_width_special_match(start, capture_count, Some(capture))),
            Self::NixExpressionEndLookahead => {
                nix_expression_end_lookahead_match(line, start).map(|(outer, inner)| {
                    let mut matched = zero_width_special_match(start, capture_count, Some(outer));
                    if let Some(inner) = inner
                        && let Some(slot) = matched.captures.get_mut(2)
                    {
                        *slot = Some(inner);
                    }
                    matched
                })
            }
        }
    }
}

fn zero_width_special_match(
    start: usize,
    capture_count: usize,
    first_capture: Option<Range<usize>>,
) -> MatchResult {
    let mut captures = vec![None; capture_count];
    if let Some(whole) = captures.get_mut(0) {
        *whole = Some(start..start);
    }
    if let Some(capture) = first_capture
        && let Some(slot) = captures.get_mut(1)
    {
        *slot = Some(capture);
    }
    MatchResult {
        start,
        end: start,
        captures,
    }
}

fn nix_function_lookahead_match(line: &str, start: usize) -> Option<Range<usize>> {
    if !line.is_char_boundary(start) {
        return None;
    }
    let bytes = line.as_bytes();
    match bytes.get(start).copied()? {
        byte if is_nix_identifier_start(byte) => {
            if !is_word_boundary(line, start) {
                return None;
            }
            let mut pos = start + 1;
            while bytes
                .get(pos)
                .copied()
                .is_some_and(is_nix_identifier_continue)
            {
                pos += 1;
            }
            pos = consume_whitespace(line, pos)?;
            if bytes
                .get(pos)
                .copied()
                .is_some_and(|byte| matches!(byte, b':' | b'@'))
            {
                Some(start..pos + 1)
            } else {
                None
            }
        }
        b'{' => nix_function_attrset_colon_match(line, start)
            .or_else(|| nix_function_attrset_comma_or_question_match(line, start)),
        _ => None,
    }
}

fn nix_function_attrset_colon_match(line: &str, start: usize) -> Option<Range<usize>> {
    let bytes = line.as_bytes();
    let mut pos = start + 1;
    while let Some((ch, next)) = char_at(line, pos) {
        if matches!(ch, '"' | '\'' | '}') {
            break;
        }
        pos = next;
    }
    if bytes.get(pos).copied() != Some(b'}') {
        return None;
    }
    pos = consume_whitespace(line, pos + 1)?;
    (bytes.get(pos).copied() == Some(b':')).then_some(start..pos + 1)
}

fn nix_function_attrset_comma_or_question_match(line: &str, start: usize) -> Option<Range<usize>> {
    let bytes = line.as_bytes();
    let mut pos = start + 1;
    while let Some((ch, next)) = char_at(line, pos) {
        if matches!(ch, '"' | '#' | '\'' | '/' | '=' | '}') {
            break;
        }
        if matches!(ch, ',' | '?') {
            return Some(start..next);
        }
        pos = next;
    }
    bytes
        .get(pos)
        .copied()
        .and_then(|byte| matches!(byte, b',' | b'?').then_some(start..pos + 1))
}

fn nix_expression_end_lookahead_match(
    line: &str,
    start: usize,
) -> Option<(Range<usize>, Option<Range<usize>>)> {
    let bytes = line.as_bytes();
    if bytes
        .get(start)
        .copied()
        .is_some_and(|byte| matches!(byte, b']' | b')' | b',' | b';' | b'}'))
    {
        return Some((start..start + 1, None));
    }
    for word in ["else", "then"] {
        let end = start + word.len();
        if line.get(start..end) == Some(word)
            && is_word_boundary(line, start)
            && is_word_boundary(line, end)
        {
            return Some((start..end, Some(start..end)));
        }
    }
    None
}

fn is_nix_identifier_start(byte: u8) -> bool {
    byte == b'_' || byte.is_ascii_alphabetic()
}

fn is_nix_identifier_continue(byte: u8) -> bool {
    byte == b'_' || byte == b'-' || byte == b'\'' || byte.is_ascii_alphanumeric()
}

#[derive(Debug, Clone, PartialEq, Eq)]
struct VmState {
    pos: usize,
    captures: Vec<Option<Range<usize>>>,
}

/// Most AST nodes produce either no state or one state. Keeping that common
/// result inline avoids a heap allocation at every successful VM step while
/// retaining a `Vec` for genuine backtracking fanout.
#[derive(Debug, Clone, PartialEq, Eq)]
enum VmStates {
    Empty,
    One(VmState),
    Many(Vec<VmState>),
}

/// Capture-free state set used by selection when captures cannot affect the
/// match. Keeping positions inline avoids carrying and cloning empty capture
/// vectors through the recursive evaluator.
#[derive(Debug, Clone, PartialEq, Eq)]
enum PositionStates {
    Empty,
    One(usize),
    Many(Vec<usize>),
}

impl PositionStates {
    fn empty() -> Self {
        Self::Empty
    }

    fn one(position: usize) -> Self {
        Self::One(position)
    }

    fn from_vec(mut positions: Vec<usize>) -> Self {
        match positions.len() {
            0 => Self::Empty,
            1 => Self::One(positions.pop().expect("length checked")),
            _ => Self::Many(positions),
        }
    }

    fn push(&mut self, position: usize) {
        match self {
            Self::Empty => *self = Self::One(position),
            Self::One(_) => {
                let Self::One(first) = std::mem::replace(self, Self::Empty) else {
                    unreachable!("variant checked")
                };
                let mut positions = Vec::with_capacity(INITIAL_FANOUT_CAPACITY);
                positions.push(first);
                positions.push(position);
                *self = Self::Many(positions);
            }
            Self::Many(positions) => positions.push(position),
        }
    }

    fn is_empty(&self) -> bool {
        matches!(self, Self::Empty)
    }

    fn into_first(self) -> Option<usize> {
        match self {
            Self::Empty => None,
            Self::One(position) => Some(position),
            Self::Many(positions) => positions.into_iter().next(),
        }
    }
}

enum PositionStatesIntoIter {
    Empty,
    One(Option<usize>),
    Many(std::vec::IntoIter<usize>),
}

impl Iterator for PositionStatesIntoIter {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        match self {
            Self::Empty => None,
            Self::One(position) => position.take(),
            Self::Many(positions) => positions.next(),
        }
    }
}

impl IntoIterator for PositionStates {
    type Item = usize;
    type IntoIter = PositionStatesIntoIter;

    fn into_iter(self) -> Self::IntoIter {
        match self {
            Self::Empty => PositionStatesIntoIter::Empty,
            Self::One(position) => PositionStatesIntoIter::One(Some(position)),
            Self::Many(positions) => PositionStatesIntoIter::Many(positions.into_iter()),
        }
    }
}

impl VmStates {
    fn empty() -> Self {
        Self::Empty
    }

    fn one(state: VmState) -> Self {
        Self::One(state)
    }

    fn from_vec(mut states: Vec<VmState>) -> Self {
        match states.len() {
            0 => Self::Empty,
            1 => Self::One(states.pop().expect("length checked")),
            _ => Self::Many(states),
        }
    }

    fn push(&mut self, state: VmState) {
        match self {
            Self::Empty => *self = Self::One(state),
            Self::One(_) => {
                let Self::One(first) = std::mem::replace(self, Self::Empty) else {
                    unreachable!("variant checked")
                };
                let mut states = Vec::with_capacity(INITIAL_FANOUT_CAPACITY);
                states.push(first);
                states.push(state);
                *self = Self::Many(states);
            }
            Self::Many(states) => states.push(state),
        }
    }

    fn into_first(self) -> Option<VmState> {
        match self {
            Self::Empty => None,
            Self::One(state) => Some(state),
            Self::Many(states) => states.into_iter().next(),
        }
    }
}

impl Deref for VmStates {
    type Target = [VmState];

    fn deref(&self) -> &Self::Target {
        match self {
            Self::Empty => &[],
            Self::One(state) => std::slice::from_ref(state),
            Self::Many(states) => states,
        }
    }
}

impl DerefMut for VmStates {
    fn deref_mut(&mut self) -> &mut Self::Target {
        match self {
            Self::Empty => &mut [],
            Self::One(state) => std::slice::from_mut(state),
            Self::Many(states) => states,
        }
    }
}

enum VmStatesIntoIter {
    Empty,
    One(Option<VmState>),
    Many(std::vec::IntoIter<VmState>),
}

impl Iterator for VmStatesIntoIter {
    type Item = VmState;

    fn next(&mut self) -> Option<Self::Item> {
        match self {
            Self::Empty => None,
            Self::One(state) => state.take(),
            Self::Many(states) => states.next(),
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        match self {
            Self::Empty => (0, Some(0)),
            Self::One(Some(_)) => (1, Some(1)),
            Self::One(None) => (0, Some(0)),
            Self::Many(states) => states.size_hint(),
        }
    }
}

impl IntoIterator for VmStates {
    type Item = VmState;
    type IntoIter = VmStatesIntoIter;

    fn into_iter(self) -> Self::IntoIter {
        match self {
            Self::Empty => VmStatesIntoIter::Empty,
            Self::One(state) => VmStatesIntoIter::One(Some(state)),
            Self::Many(states) => VmStatesIntoIter::Many(states.into_iter()),
        }
    }
}

impl FallbackMatcher {
    pub fn new(pattern: &str) -> Self {
        Self::with_budget(pattern, DEFAULT_STEP_BUDGET)
    }

    pub fn with_budget(pattern: &str, budget: usize) -> Self {
        Self::from_parsed(Arc::new(parse(pattern)), budget)
    }

    pub(crate) fn from_parsed(parsed: Arc<ParsedRegex>, budget: usize) -> Self {
        let start_hint = start_hint(&parsed.ast);
        let special = SpecialFallbackMatcher::from_source(&parsed.source);
        Self {
            parsed,
            bytecode: OnceLock::new(),
            shared_captures: None,
            special,
            start_hint,
            budget,
            prefilter_slot: OnceLock::new(),
        }
    }

    fn prefilter_slot(&self) -> u32 {
        static NEXT_PREFILTER_SLOT: std::sync::atomic::AtomicU32 =
            std::sync::atomic::AtomicU32::new(0);
        *self.prefilter_slot.get_or_init(|| {
            if self.parsed.prefilter().is_enabled() {
                NEXT_PREFILTER_SLOT.fetch_add(1, std::sync::atomic::Ordering::Relaxed)
            } else {
                u32::MAX
            }
        })
    }

    pub fn parsed(&self) -> &ParsedRegex {
        &self.parsed
    }

    /// Takes ownership of the owning pattern's live capture layout when it
    /// replays captures, returning an empty layout in that case and `live`
    /// otherwise.
    pub(crate) fn share_capture_layout(&mut self, live: Box<[u32]>) -> Box<[u32]> {
        if live.iter().any(|group| *group != 0) {
            self.shared_captures = Some(live);
            Box::default()
        } else {
            live
        }
    }

    pub(crate) fn shared_capture_layout(&self) -> Option<&[u32]> {
        self.shared_captures.as_deref()
    }

    /// The selection program when it was compiled with the shared capture
    /// layout and so can replay captures directly.
    pub(crate) fn shared_capture_program(&self) -> Option<Arc<Program>> {
        self.bytecode.get_or_init(|| self.compile_bytecode());
        self.bytecode
            .get()?
            .as_ref()
            .filter(|selection| selection.shares_captures)
            .map(|selection| Arc::clone(&selection.program))
    }

    /// Whether the required-literal prefilter still admits a match starting
    /// at `start` or later on this line. The prefilter searches the suffix
    /// from `start`, so `false` also holds for every later start.
    pub(crate) fn selection_prefilter_viable(
        &self,
        line: &str,
        start: usize,
        scratch: &mut BytecodeScratch,
    ) -> bool {
        scratch.prefilter_cursors().may_match(
            self.prefilter_slot(),
            self.parsed.prefilter(),
            line,
            start,
        )
    }

    fn bytecode(&self) -> Option<&Program> {
        self.bytecode
            .get_or_init(|| self.compile_bytecode())
            .as_ref()
            .map(|selection| selection.program.as_ref())
    }

    fn compile_bytecode(&self) -> Option<SelectionProgram> {
        if !self.parsed.analysis().bytecode_beneficial() {
            return None;
        }
        // One program can serve both selection and capture replay when the
        // replayed groups do not change its selection shape. Patterns whose
        // matching reads capture state keep their dedicated selection layout.
        // Subroutine calls only write captures, so they can share.
        let features = &self.parsed.features;
        let reads_captures = features.backreference || features.conditional;
        if !reads_captures
            && let Some(live) = self.shared_captures.as_deref()
            && let Some(Ok(program)) =
                Program::compile_selection_captures(&self.parsed, self.parsed.analysis(), live)
        {
            return Some(SelectionProgram {
                program: Arc::new(program),
                shares_captures: true,
            });
        }
        // Subroutine calls need capture slots and routine entries even for
        // position selection; compile with the minimal internal layout so
        // those patterns still avoid the recursive VM. Selection discards
        // captures. Backreference patterns need only the referenced groups
        // for position selection. Keeping them on the bytecode path lets hot
        // C/C++ declaration patterns use the deterministic separator and
        // literal-trie specializations before replaying winner captures.
        // The position-only layout has no capture slots, so these features
        // can never compile there. Skip the doomed attempt instead of
        // discarding a partial compile of a large pattern.
        let position = if reads_captures || features.subroutine {
            Err(CompileError::Subroutine)
        } else {
            Program::compile(&self.parsed)
        };
        position
            .or_else(|error| match error {
                CompileError::Backreference
                | CompileError::Subroutine
                | CompileError::Conditional => Program::compile_captures_with_analysis(
                    &self.parsed,
                    self.parsed.analysis(),
                    &[],
                ),
                other => Err(other),
            })
            .ok()
            .map(|program| SelectionProgram {
                program: Arc::new(program),
                shares_captures: false,
            })
    }

    fn active_bytecode(&self) -> Option<&Program> {
        (position_engine_mode() != PositionEngineMode::Recursive)
            .then(|| self.bytecode())
            .flatten()
    }

    pub fn prefilter_may_match(&self, line: &str, from: usize) -> Option<bool> {
        let prefilter = self.parsed.prefilter();
        prefilter
            .is_enabled()
            .then(|| prefilter.may_match(line, from))
    }

    pub(crate) fn restricted_start_bytes(&self) -> Option<Vec<u8>> {
        let analysis = self.parsed.analysis();
        let bytes = analysis
            .start_bytes()
            .filter(|_| !analysis.start_nullable())?;
        // Ascending byte order, read straight from the bitmap words.
        let mut out = Vec::with_capacity(bytes.len);
        for (word_index, &word) in bytes.bits.iter().enumerate() {
            let mut word = word;
            while word != 0 {
                out.push((word_index * 64) as u8 + word.trailing_zeros() as u8);
                word &= word - 1;
            }
        }
        Some(out)
    }

    pub fn try_find(
        &self,
        line: &str,
        from: usize,
        ctx: AnchorContext,
    ) -> Result<FallbackReport, FallbackError> {
        self.try_find_with_capture_count(line, from, ctx, self.parsed.capture_count as usize + 1)
    }

    pub(crate) fn try_find_for_selection(
        &self,
        line: &str,
        from: usize,
        ctx: AnchorContext,
    ) -> Result<FallbackReport, FallbackError> {
        let capture_count = self.selection_capture_count();
        let mut report = self.try_find_with_capture_count(line, from, ctx, capture_count)?;
        if let Some(result) = &mut report.result {
            result.captures.clear();
        }
        Ok(report)
    }

    fn try_find_with_capture_count(
        &self,
        line: &str,
        from: usize,
        ctx: AnchorContext,
        capture_count: usize,
    ) -> Result<FallbackReport, FallbackError> {
        if !line.is_char_boundary(from) {
            return Err(FallbackError::InvalidStart { from });
        }
        if !self.parsed.prefilter().may_match(line, from) {
            return Ok(FallbackReport {
                result: None,
                steps: 0,
            });
        }
        let mut budget = StepBudget::new(self.budget);
        // One scratch per search: attempts reset it, so later starts reuse
        // its stack capacity instead of allocating afresh.
        let mut scratch = BytecodeScratch::default();
        // A nullable pattern can match empty wherever its zero-width
        // assertions hold (for example `x|(?<=T)` or `a|$`), so only a
        // pattern that must consume a start byte may skip other positions.
        if self.start_hint == StartHint::Unanchored
            && !self.parsed.analysis().start_nullable()
            && let Some(start_bytes) = self.parsed.analysis().start_bytes()
        {
            let hay = line.as_bytes();
            let mut cursor = from;
            while cursor < hay.len() {
                let Some(relative) = start_bytes.find(&hay[cursor..]) else {
                    break;
                };
                let start = cursor + relative;
                if line.is_char_boundary(start)
                    && let Some(result) = self.try_match_at_start_with_capture_count(
                        line,
                        start,
                        ctx,
                        &mut budget,
                        capture_count,
                        &mut scratch,
                    )?
                {
                    return Ok(FallbackReport {
                        result: Some(result),
                        steps: budget.used(),
                    });
                }
                cursor = start.saturating_add(1);
            }
            return Ok(FallbackReport {
                result: None,
                steps: budget.used(),
            });
        }
        for start in self.start_positions(line, from, ctx) {
            if let Some(result) = self.try_match_at_start_with_capture_count(
                line,
                start,
                ctx,
                &mut budget,
                capture_count,
                &mut scratch,
            )? {
                return Ok(FallbackReport {
                    result: Some(result),
                    steps: budget.used(),
                });
            }
        }
        Ok(FallbackReport {
            result: None,
            steps: budget.used(),
        })
    }

    /// Search-only variant used while selecting among a set of rules. Capture
    /// extraction is replayed only for the winning pattern by the tokenizer.
    pub(crate) fn try_find_at_without_captures_with_scratch(
        &self,
        line: &str,
        start: usize,
        ctx: AnchorContext,
        scratch: &mut BytecodeScratch,
    ) -> Result<FallbackReport, FallbackError> {
        // Resolve the selection layout only after the cheap per-start
        // rejections: deciding it may compile bytecode, which is wasted for a
        // candidate whose prefilter or start bytes never admit an attempt.
        self.try_find_at_with_capture_count_and_scratch(
            line,
            start,
            ctx,
            CaptureCount::Selection,
            Some(scratch),
        )
    }

    fn selection_capture_count(&self) -> usize {
        if self.active_bytecode().is_some() {
            0
        } else if self
            .parsed
            .analysis()
            .capture()
            .selection_requires_captures()
        {
            self.parsed.capture_count as usize + 1
        } else {
            0
        }
    }

    pub(crate) fn try_find_at(
        &self,
        line: &str,
        start: usize,
        ctx: AnchorContext,
    ) -> Result<FallbackReport, FallbackError> {
        self.try_find_at_with_capture_count_and_scratch(
            line,
            start,
            ctx,
            CaptureCount::Exact(self.parsed.capture_count as usize + 1),
            None,
        )
    }

    fn try_find_at_with_capture_count_and_scratch(
        &self,
        line: &str,
        start: usize,
        ctx: AnchorContext,
        capture_count: CaptureCount,
        scratch: Option<&mut BytecodeScratch>,
    ) -> Result<FallbackReport, FallbackError> {
        if !line.is_char_boundary(start) {
            return Err(FallbackError::InvalidStart { from: start });
        }
        let mut scratch = scratch;
        let prefilter_viable = match scratch.as_deref_mut() {
            Some(scratch) => scratch.prefilter_cursors().may_match(
                self.prefilter_slot(),
                self.parsed.prefilter(),
                line,
                start,
            ),
            None => self.parsed.prefilter().may_match(line, start),
        };
        if !prefilter_viable {
            return Ok(FallbackReport {
                result: None,
                steps: 0,
            });
        }
        if let StartHint::Anchored(anchors) = self.start_hint
            && !anchors.allows(start, ctx)
        {
            return Ok(FallbackReport {
                result: None,
                steps: 0,
            });
        }
        if let Some(bytes) = self.parsed.analysis().start_bytes()
            && !self.parsed.analysis().start_nullable()
            && line
                .as_bytes()
                .get(start)
                .is_none_or(|byte| !bytes.contains(*byte))
        {
            return Ok(FallbackReport {
                result: None,
                steps: 0,
            });
        }
        let capture_count = match capture_count {
            CaptureCount::Exact(count) => count,
            CaptureCount::Selection => self.selection_capture_count(),
        };
        if let Some(special) = self.special {
            return Ok(FallbackReport {
                result: special.match_at(line, start, capture_count),
                steps: 0,
            });
        }
        let mut budget = StepBudget::new(self.budget);
        let mut local_scratch;
        let scratch = match scratch {
            Some(scratch) => scratch,
            None => {
                local_scratch = BytecodeScratch::default();
                &mut local_scratch
            }
        };
        let result = if capture_count == 0
            && let Some(program) = self.active_bytecode()
        {
            let end = match position_engine_mode() {
                PositionEngineMode::Recursive => {
                    recursive_position_end(&self.parsed, line, start, ctx, &mut budget)?
                }
                PositionEngineMode::Candidate => program
                    .execute(line, start, ctx, &mut budget, scratch)
                    .map_err(|_| FallbackError::BudgetExceeded {
                        steps: budget.used(),
                    })?,
                PositionEngineMode::Shadow => {
                    let mut candidate_budget = StepBudget::new(self.budget);
                    let candidate =
                        program.execute(line, start, ctx, &mut candidate_budget, scratch);
                    let recursive =
                        recursive_position_end(&self.parsed, line, start, ctx, &mut budget)?;
                    if candidate.as_ref().ok().copied() != Some(recursive) {
                        eprintln!(
                            "SYNTAXMATE_VM_MISMATCH pattern={:?} start={} recursive={:?} candidate={:?}",
                            self.parsed.source, start, recursive, candidate
                        );
                    }
                    recursive
                }
            };
            end.map(|end| MatchResult {
                start,
                end,
                captures: Vec::new(),
            })
        } else {
            self.try_match_at_start_with_capture_count(
                line,
                start,
                ctx,
                &mut budget,
                capture_count,
                scratch,
            )?
        };
        Ok(FallbackReport {
            result,
            steps: budget.used(),
        })
    }

    fn start_positions<'a>(
        &self,
        line: &'a str,
        from: usize,
        ctx: AnchorContext,
    ) -> impl Iterator<Item = usize> + 'a {
        let (every, anchored) = match self.start_hint {
            StartHint::Unanchored => (true, [None, None]),
            // Position 0 precedes `g_pos`, preserving leftmost-first order.
            StartHint::Anchored(anchors) => (
                false,
                [0, ctx.g_pos]
                    .map(|start| (start >= from && anchors.allows(start, ctx)).then_some(start)),
            ),
        };
        let [first, second] = anchored;
        let second = second.filter(|start| Some(*start) != first);
        every
            .then(|| char_boundaries_from(line, from))
            .into_iter()
            .flatten()
            .chain(first)
            .chain(second)
    }

    fn try_match_at_start_with_capture_count(
        &self,
        line: &str,
        start: usize,
        ctx: AnchorContext,
        budget: &mut StepBudget,
        capture_count: usize,
        scratch: &mut BytecodeScratch,
    ) -> Result<Option<MatchResult>, FallbackError> {
        if let Some(special) = self.special {
            return Ok(special.match_at(line, start, capture_count));
        }
        if capture_count == 0
            && let Some(program) = self.active_bytecode()
        {
            let end = match position_engine_mode() {
                PositionEngineMode::Recursive => {
                    recursive_position_end(&self.parsed, line, start, ctx, budget)?
                }
                PositionEngineMode::Candidate => program
                    .execute(line, start, ctx, budget, scratch)
                    .map_err(|_| FallbackError::BudgetExceeded {
                        steps: budget.used(),
                    })?,
                PositionEngineMode::Shadow => {
                    let mut candidate_budget = StepBudget::new(self.budget);
                    let candidate =
                        program.execute(line, start, ctx, &mut candidate_budget, scratch);
                    let recursive = recursive_position_end(&self.parsed, line, start, ctx, budget)?;
                    if candidate.as_ref().ok().copied() != Some(recursive) {
                        eprintln!(
                            "SYNTAXMATE_VM_MISMATCH pattern={:?} start={} recursive={:?} candidate={:?}",
                            self.parsed.source, start, recursive, candidate
                        );
                    }
                    recursive
                }
            };
            return Ok(end.map(|end| MatchResult {
                start,
                end,
                captures: Vec::new(),
            }));
        }
        if capture_count == 0 && self.parsed.analysis().capture().position_only_eligible() {
            let end = recursive_position_end(&self.parsed, line, start, ctx, budget)?;
            return Ok(end.map(|end| MatchResult {
                start,
                end,
                captures: Vec::new(),
            }));
        }
        let captures = vec![None; capture_count];
        let state = VmState {
            pos: start,
            captures,
        };
        let matches = match_node(
            &self.parsed.ast,
            line,
            state,
            ctx,
            self.parsed.flags,
            budget,
            &self.parsed,
        )
        .map_err(|_| FallbackError::BudgetExceeded {
            steps: budget.used(),
        })?;
        Ok(matches.into_first().map(|mut matched| {
            if let Some(whole) = matched.captures.get_mut(0) {
                *whole = Some(start..matched.pos);
            }
            MatchResult {
                start,
                end: matched.pos,
                captures: matched.captures,
            }
        }))
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct StartByteSet {
    bits: [u64; 4],
    len: usize,
}

impl StartByteSet {
    pub(crate) fn empty() -> Self {
        Self {
            bits: [0; 4],
            len: 0,
        }
    }

    pub(crate) fn insert(&mut self, byte: u8) {
        if !self.contains(byte) {
            self.bits[byte as usize >> 6] |= 1u64 << (byte & 63);
            self.len += 1;
        }
    }

    pub(crate) fn extend(&mut self, other: &Self) {
        // Word-wise union: large literal alternations merge one set per
        // branch, so a per-byte loop dominated start-byte analysis.
        for (word, other) in self.bits.iter_mut().zip(other.bits) {
            *word |= other;
        }
        self.len = self
            .bits
            .iter()
            .map(|word| word.count_ones() as usize)
            .sum();
    }

    pub(crate) fn contains(&self, byte: u8) -> bool {
        self.bits[byte as usize >> 6] & (1u64 << (byte & 63)) != 0
    }

    pub(crate) fn find(&self, haystack: &[u8]) -> Option<usize> {
        super::prefilter::find_byte_set_bitmap(haystack, &self.bits)
    }

    pub(crate) fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub(crate) fn len(&self) -> usize {
        self.len
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct StartBytes {
    pub(crate) bytes: StartByteSet,
    pub(crate) nullable: bool,
}

pub(crate) fn expand_case_insensitive_start_bytes(bytes: &mut StartByteSet) {
    for byte in b'a'..=b'z' {
        if bytes.contains(byte) || bytes.contains(byte.to_ascii_uppercase()) {
            bytes.insert(byte);
            bytes.insert(byte.to_ascii_uppercase());
        }
    }
    // Unicode simple/full folds can make an ASCII atom match a non-ASCII
    // scalar. Any such UTF-8 scalar starts with one of these lead bytes; keep
    // them as conservative candidates while still skipping unrelated ASCII.
    for byte in 0xc2..=0xf4 {
        bytes.insert(byte);
    }
}

pub(crate) fn first_start_bytes(ast: &Ast) -> Option<StartBytes> {
    match ast {
        Ast::Empty | Ast::Anchor(_) => Some(StartBytes {
            bytes: StartByteSet::empty(),
            nullable: true,
        }),
        Ast::Literal(literal) => {
            let Some(ch) = literal.chars().next() else {
                return Some(StartBytes {
                    bytes: StartByteSet::empty(),
                    nullable: true,
                });
            };
            let mut bytes = StartByteSet::empty();
            if ch.is_ascii() {
                bytes.insert(ch as u8);
                Some(StartBytes {
                    bytes,
                    nullable: false,
                })
            } else {
                None
            }
        }
        Ast::Class(class) => class_start_bytes(class).map(|bytes| StartBytes {
            bytes,
            nullable: false,
        }),
        Ast::Concat(nodes) => concat_start_bytes(nodes),
        Ast::Alternation(branches) => alternation_start_bytes(branches),
        Ast::Repeat { node, min, max, .. } => {
            if *max == Some(0) {
                return Some(StartBytes {
                    bytes: StartByteSet::empty(),
                    nullable: true,
                });
            }
            let mut info = first_start_bytes(node)?;
            info.nullable = *min == 0 || info.nullable;
            Some(info)
        }
        Ast::Group { child, .. } | Ast::Flags { child, .. } => first_start_bytes(child),
        Ast::Look {
            kind: LookKind::Ahead,
            child,
        } => first_start_bytes(child),
        Ast::Look { .. } => Some(StartBytes {
            bytes: StartByteSet::empty(),
            nullable: true,
        }),
        Ast::Dot
        | Ast::Grapheme
        | Ast::Backref(_)
        | Ast::Conditional { .. }
        | Ast::Subroutine(_)
        | Ast::Unsupported(_) => None,
    }
}

pub(crate) fn concat_start_bytes(nodes: &[Ast]) -> Option<StartBytes> {
    let mut out = StartBytes {
        bytes: StartByteSet::empty(),
        nullable: true,
    };
    for node in nodes {
        let info = first_start_bytes(node)?;
        out.bytes.extend(&info.bytes);
        out.nullable &= info.nullable;
        if !info.nullable {
            return Some(out);
        }
    }
    Some(out)
}

fn alternation_start_bytes(branches: &[Ast]) -> Option<StartBytes> {
    let mut out = StartBytes {
        bytes: StartByteSet::empty(),
        nullable: false,
    };
    for branch in branches {
        let info = first_start_bytes(branch)?;
        out.bytes.extend(&info.bytes);
        out.nullable |= info.nullable;
    }
    Some(out)
}

pub(crate) fn class_start_bytes(class: &CharClass) -> Option<StartByteSet> {
    if class.negated {
        return None;
    }
    // Intersections only narrow this first union, so its byte set remains a
    // conservative start hint without having to flatten nested predicates.
    let mut bytes = StartByteSet::empty();
    for atom in &class.atoms {
        match atom {
            ClassAtom::Char(ch) if ch.is_ascii() => bytes.insert(*ch as u8),
            ClassAtom::Char(_) => return None,
            ClassAtom::Range(start, end) if start.is_ascii() && end.is_ascii() => {
                let start = *start as u8;
                let end = *end as u8;
                for byte in start.min(end)..=start.max(end) {
                    bytes.insert(byte);
                }
            }
            ClassAtom::Range(..) => return None,
            ClassAtom::Perl(kind) => insert_perl_start_bytes(&mut bytes, *kind)?,
            ClassAtom::Posix { name, negated } => {
                insert_posix_start_bytes(&mut bytes, name, *negated)?
            }
            ClassAtom::Unicode { .. } => return None,
            ClassAtom::Nested(_) => return None,
        }
    }
    (!bytes.is_empty()).then_some(bytes)
}

fn insert_perl_start_bytes(bytes: &mut StartByteSet, kind: PerlClassKind) -> Option<()> {
    match kind {
        PerlClassKind::Digit => insert_range(bytes, b'0', b'9'),
        // The evaluator intentionally uses Unicode word/whitespace semantics.
        // An ASCII-only byte hint would reject valid non-ASCII starts.
        PerlClassKind::Word | PerlClassKind::Space => return None,
        PerlClassKind::HorizontalSpace => {
            insert_range(bytes, b'0', b'9');
            insert_range(bytes, b'A', b'F');
            insert_range(bytes, b'a', b'f');
        }
        PerlClassKind::VerticalSpace => {
            for byte in [b'\n', 0x0b, 0x0c, b'\r'] {
                bytes.insert(byte);
            }
        }
        PerlClassKind::NotDigit
        | PerlClassKind::NotWord
        | PerlClassKind::NotSpace
        | PerlClassKind::NotHorizontalSpace
        | PerlClassKind::NotVerticalSpace
        | PerlClassKind::NotNewline => return None,
    }
    Some(())
}

fn insert_posix_start_bytes(bytes: &mut StartByteSet, name: &str, negated: bool) -> Option<()> {
    if negated {
        return None;
    }
    match name {
        "digit" => insert_range(bytes, b'0', b'9'),
        "xdigit" => {
            insert_range(bytes, b'0', b'9');
            insert_range(bytes, b'A', b'F');
            insert_range(bytes, b'a', b'f');
        }
        // These predicates are Unicode-aware in `posix_class_contains`.
        "alpha" | "alnum" | "lower" | "upper" | "word" | "space" => return None,
        "blank" => {
            bytes.insert(b'\t');
            bytes.insert(b' ');
        }
        "ascii" => insert_range(bytes, 0, 0x7f),
        _ => return None,
    }
    Some(())
}

fn insert_range(bytes: &mut StartByteSet, start: u8, end: u8) {
    for byte in start..=end {
        bytes.insert(byte);
    }
}

fn match_position_node(
    ast: &Ast,
    line: &str,
    position: usize,
    ctx: AnchorContext,
    flags: RegexFlags,
    budget: &mut StepBudget,
) -> Result<PositionStates, BudgetExceeded> {
    budget.step()?;
    match ast {
        Ast::Empty => Ok(PositionStates::one(position)),
        Ast::Literal(literal) => {
            let end = match_literal_end(line, position, literal, flags);
            Ok(if let Some(end) = end {
                PositionStates::one(end)
            } else {
                PositionStates::empty()
            })
        }
        Ast::Dot => {
            let Some((ch, next)) = char_at(line, position) else {
                return Ok(PositionStates::empty());
            };
            Ok(if ch != '\n' || flags.dot_matches_new_line {
                PositionStates::one(next)
            } else {
                PositionStates::empty()
            })
        }
        Ast::Grapheme => Ok(
            grapheme_end(line, position).map_or_else(PositionStates::empty, PositionStates::one)
        ),
        Ast::Class(class) => {
            let Some((ch, next)) = char_at(line, position) else {
                return Ok(PositionStates::empty());
            };
            Ok(if class_contains(class, ch, flags) {
                PositionStates::one(next)
            } else {
                PositionStates::empty()
            })
        }
        Ast::Anchor(anchor) => Ok(if anchor_matches(*anchor, line, position, ctx) {
            PositionStates::one(position)
        } else {
            PositionStates::empty()
        }),
        Ast::Concat(nodes) => {
            let mut positions = PositionStates::one(position);
            for node in nodes {
                let mut next = PositionStates::empty();
                for position in positions {
                    let matches = match_position_node(node, line, position, ctx, flags, budget)?;
                    push_limited_positions(&mut next, matches);
                }
                if next.is_empty() {
                    return Ok(PositionStates::empty());
                }
                positions = next;
            }
            Ok(positions)
        }
        Ast::Alternation(branches) => {
            if let Some(positions) =
                match_cpp_space_comment_separator_positions(branches, line, position, ctx)
            {
                return Ok(positions);
            }
            let mut out = PositionStates::empty();
            for branch in branches {
                let matches = match_position_node(branch, line, position, ctx, flags, budget)?;
                push_limited_positions(&mut out, matches);
            }
            Ok(out)
        }
        Ast::Repeat {
            node,
            min,
            max,
            greedy,
            possessive,
            atomic,
        } => match_position_repeat(
            node,
            *min,
            *max,
            *greedy,
            *possessive,
            *atomic,
            line,
            position,
            ctx,
            flags,
            budget,
        ),
        Ast::Group { child, .. } => match_position_node(child, line, position, ctx, flags, budget),
        Ast::Flags {
            flags: local,
            child,
        } => match_position_node(child, line, position, ctx, *local, budget),
        Ast::Look { kind, child } => match kind {
            LookKind::Ahead => {
                let matches = match_position_node(child, line, position, ctx, flags, budget)?;
                Ok(if matches.is_empty() {
                    PositionStates::empty()
                } else {
                    PositionStates::one(position)
                })
            }
            LookKind::NotAhead => {
                let matches = match_position_node(child, line, position, ctx, flags, budget)?;
                Ok(if matches.is_empty() {
                    PositionStates::one(position)
                } else {
                    PositionStates::empty()
                })
            }
            LookKind::Behind | LookKind::NotBehind => {
                let matched =
                    position_lookbehind_matches(child, line, position, ctx, flags, budget)?;
                let accepted = if *kind == LookKind::Behind {
                    matched
                } else {
                    !matched
                };
                Ok(if accepted {
                    PositionStates::one(position)
                } else {
                    PositionStates::empty()
                })
            }
        },
        Ast::Backref(_) | Ast::Conditional { .. } | Ast::Subroutine(_) | Ast::Unsupported(_) => {
            Ok(PositionStates::empty())
        }
    }
}

#[cfg(test)]
pub(crate) fn recursive_position_span(
    parsed: &ParsedRegex,
    line: &str,
    start: usize,
    ctx: AnchorContext,
) -> Option<std::ops::Range<usize>> {
    let mut budget = StepBudget::new(DEFAULT_STEP_BUDGET);
    match_position_node(&parsed.ast, line, start, ctx, parsed.flags, &mut budget)
        .ok()?
        .into_first()
        .map(|end| start..end)
}

fn recursive_position_end(
    parsed: &ParsedRegex,
    line: &str,
    start: usize,
    ctx: AnchorContext,
    budget: &mut StepBudget,
) -> Result<Option<usize>, FallbackError> {
    match_position_node(&parsed.ast, line, start, ctx, parsed.flags, budget)
        .map(PositionStates::into_first)
        .map_err(|_| FallbackError::BudgetExceeded {
            steps: budget.used(),
        })
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum PositionEngineMode {
    Recursive,
    Candidate,
    Shadow,
}

pub(crate) fn position_engine_mode() -> PositionEngineMode {
    PositionEngineMode::Candidate
}

pub(crate) fn capture_engine_mode() -> PositionEngineMode {
    PositionEngineMode::Candidate
}

fn position_lookbehind_matches(
    child: &Ast,
    line: &str,
    position: usize,
    ctx: AnchorContext,
    flags: RegexFlags,
    budget: &mut StepBudget,
) -> Result<bool, BudgetExceeded> {
    if let Some(literal) = ast_exact_literal(child)
        && !flags.case_insensitive
    {
        let start = position.saturating_sub(literal.len());
        return Ok(position >= literal.len()
            && line.is_char_boundary(start)
            && line.get(start..position) == Some(literal.as_str()));
    }

    let mut matches_from = |start| -> Result<bool, BudgetExceeded> {
        if !line.is_char_boundary(start) {
            return Ok(false);
        }
        Ok(match_position_node(child, line, start, ctx, flags, budget)?
            .into_iter()
            .any(|end| end == position))
    };

    if let Some((min_width, max_width)) = lookbehind_byte_width_bounds(child, flags) {
        let Some(latest_start) = position.checked_sub(min_width) else {
            return Ok(false);
        };
        let earliest_start = position.saturating_sub(max_width);
        for start in earliest_start..=latest_start {
            if matches_from(start)? {
                return Ok(true);
            }
        }
        return Ok(false);
    }

    for start in char_boundaries_until(line, position) {
        if matches_from(start)? {
            return Ok(true);
        }
    }
    Ok(false)
}

#[allow(clippy::too_many_arguments)]
fn match_position_repeat(
    node: &Ast,
    min: usize,
    max: Option<usize>,
    greedy: bool,
    possessive: bool,
    atomic: bool,
    line: &str,
    position: usize,
    ctx: AnchorContext,
    flags: RegexFlags,
    budget: &mut StepBudget,
) -> Result<PositionStates, BudgetExceeded> {
    // With an exact repetition count there is no repetition-count choice to
    // make possessive. Oniguruma still permits backtracking inside the atom.
    let possessive = possessive && (atomic || max != Some(min));
    if is_simple_repeat_atom(node) {
        let max = max.unwrap_or(usize::MAX);
        let mut positions = Vec::new();
        positions.push(position);
        let mut current = position;
        let mut count = 0usize;
        while count < max {
            budget.step()?;
            let Some(next) = simple_repeat_next(node, line, current, flags) else {
                break;
            };
            if next == current {
                break;
            }
            positions.push(next);
            current = next;
            count += 1;
        }
        if count < min {
            return Ok(PositionStates::empty());
        }
        let accepted = &positions[min..];
        if possessive {
            return Ok(accepted
                .last()
                .copied()
                .map_or_else(PositionStates::empty, PositionStates::one));
        }
        let mut out = Vec::with_capacity(accepted.len().min(STATE_LIMIT));
        if greedy {
            out.extend(accepted.iter().rev().copied().take(STATE_LIMIT));
        } else {
            out.extend(accepted.iter().copied().take(STATE_LIMIT));
        }
        return Ok(PositionStates::from_vec(out));
    }

    if possessive {
        let max = max.unwrap_or_else(|| line.len().saturating_sub(position).saturating_add(1));
        let mut current = position;
        let mut count = 0usize;
        while count < max && (greedy || count < min) {
            budget.step()?;
            let Some(next) = match_position_node(node, line, current, ctx, flags, budget)?
                .into_iter()
                .next()
            else {
                break;
            };
            count += 1;
            if next == current {
                current = next;
                break;
            }
            current = next;
        }
        return Ok(if count >= min {
            PositionStates::one(current)
        } else {
            PositionStates::empty()
        });
    }

    let max = max.unwrap_or_else(|| line.len().saturating_sub(position).saturating_add(1));
    // Preference-ordered DFS emission; see `match_repeat` for the rationale.
    enum Work {
        Visit(usize, usize),
        Accept(usize),
    }
    let mut stack = vec![Work::Visit(0, position)];
    let mut accepted: Vec<usize> = Vec::new();
    while let Some(work) = stack.pop() {
        budget.step()?;
        let (count, current) = match work {
            Work::Accept(position) => {
                if !accepted.contains(&position) {
                    accepted.push(position);
                    if accepted.len() >= STATE_LIMIT {
                        break;
                    }
                }
                continue;
            }
            Work::Visit(count, position) => (count, position),
        };
        if greedy && count >= min {
            stack.push(Work::Accept(current));
        }
        if count < max && stack.len() < STATE_LIMIT {
            let next_positions = match_position_node(node, line, current, ctx, flags, budget)?;
            let push = |next: usize, stack: &mut Vec<Work>| {
                if next == current {
                    if count < min {
                        stack.push(Work::Visit(count + 1, next));
                    }
                    return;
                }
                stack.push(Work::Visit(count + 1, next));
            };
            match next_positions {
                PositionStates::Empty => {}
                PositionStates::One(next) => push(next, &mut stack),
                PositionStates::Many(positions) => {
                    for next in positions.into_iter().rev() {
                        push(next, &mut stack);
                    }
                }
            }
        }
        if !greedy && count >= min {
            stack.push(Work::Accept(current));
        }
    }
    Ok(PositionStates::from_vec(accepted))
}

fn push_limited_positions(target: &mut PositionStates, states: PositionStates) {
    for position in states {
        if match target {
            PositionStates::Empty => 0,
            PositionStates::One(_) => 1,
            PositionStates::Many(positions) => positions.len(),
        } >= STATE_LIMIT
        {
            break;
        }
        target.push(position);
    }
}

impl Matcher for FallbackMatcher {
    fn find(&self, line: &str, from: usize, ctx: AnchorContext) -> Option<MatchResult> {
        self.try_find(line, from, ctx).ok()?.result
    }
}

fn match_node(
    ast: &Ast,
    line: &str,
    state: VmState,
    ctx: AnchorContext,
    flags: RegexFlags,
    budget: &mut StepBudget,
    parsed: &ParsedRegex,
) -> Result<VmStates, BudgetExceeded> {
    budget.step()?;
    match ast {
        Ast::Empty => Ok(VmStates::one(state)),
        Ast::Literal(literal) => match_literal(literal, line, state, flags, budget),
        Ast::Dot => match_dot(line, state, flags),
        Ast::Class(class) => match_class(class, line, state, flags),
        Ast::Grapheme => Ok(
            grapheme_end(line, state.pos).map_or_else(VmStates::empty, |end| {
                VmStates::one(VmState { pos: end, ..state })
            }),
        ),
        Ast::Anchor(anchor) => match_anchor(*anchor, line, state, ctx),
        Ast::Concat(nodes) => match_concat(nodes, line, state, ctx, flags, budget, parsed),
        Ast::Alternation(branches) => {
            if state.captures.is_empty()
                && let Some(states) = match_cpp_space_comment_separator(branches, line, &state, ctx)
            {
                return Ok(states);
            }
            let mut out = VmStates::empty();
            for branch in branches {
                let branch_states =
                    match_node(branch, line, state.clone(), ctx, flags, budget, parsed)?;
                push_limited(&mut out, branch_states);
            }
            Ok(out)
        }
        Ast::Repeat {
            node,
            min,
            max,
            greedy,
            possessive,
            atomic,
        } => match_repeat(
            node,
            *min,
            *max,
            *greedy,
            *possessive,
            *atomic,
            line,
            state,
            ctx,
            flags,
            budget,
            parsed,
        ),
        Ast::Group { index, child, .. } => {
            let start = state.pos;
            let mut out = match_node(child, line, state, ctx, flags, budget, parsed)?;
            if let Some(index) = index.and_then(|index| usize::try_from(index).ok()) {
                for state in out.iter_mut() {
                    if index < state.captures.len() {
                        state.captures[index] = Some(start..state.pos);
                    }
                }
            }
            Ok(out)
        }
        Ast::Look { kind, child } => {
            match_look(*kind, child, line, state, ctx, flags, budget, parsed)
        }
        Ast::Backref(backref) => match_backref(backref, line, state, parsed, flags, budget),
        Ast::Conditional {
            condition,
            matched,
            unmatched,
        } => {
            let is_set = |group: u32| {
                usize::try_from(group)
                    .ok()
                    .and_then(|group| state.captures.get(group))
                    .is_some_and(Option::is_some)
            };
            let group = match condition {
                Backref::Number(group) => is_set(*group),
                // A shared name holds when any group of that name matched.
                Backref::Name(name) => match parsed.duplicate_names.get(name) {
                    Some(groups) => groups.iter().any(|group| is_set(*group)),
                    None => parsed
                        .named_captures
                        .get(name)
                        .is_some_and(|group| is_set(*group)),
                },
            };
            match_node(
                if group { matched } else { unmatched },
                line,
                state,
                ctx,
                flags,
                budget,
                parsed,
            )
        }
        Ast::Subroutine(call) => {
            let group = call
                .target_path
                .as_deref()
                .and_then(|path| ast_at_path(&parsed.ast, path))
                .or_else(|| find_subroutine_group(&parsed.ast, &call.target, parsed));
            let Some(group) = group else {
                return Ok(VmStates::empty());
            };
            // Oniguruma rejects recursion that can re-enter without consuming
            // input, such as `(\g<1>)?`; bound the nesting so it fails
            // instead of overflowing the stack.
            if budget.call_depth >= MAX_SUBROUTINE_DEPTH {
                return Ok(VmStates::empty());
            }
            budget.call_depth += 1;
            let states = match_node(group, line, state, ctx, flags, budget, parsed);
            budget.call_depth -= 1;
            states
        }
        Ast::Flags {
            flags: local,
            child,
        } => match_node(child, line, state, ctx, *local, budget, parsed),
        Ast::Unsupported(_) => Ok(VmStates::empty()),
    }
}

fn match_cpp_space_comment_separator(
    branches: &[Ast],
    line: &str,
    state: &VmState,
    ctx: AnchorContext,
) -> Option<VmStates> {
    let positions = cpp_space_comment_separator_positions(branches, line, state.pos, ctx)?;
    let mut out = VmStates::empty();
    for pos in positions {
        push_limited(
            &mut out,
            VmStates::one(VmState {
                pos,
                ..state.clone()
            }),
        );
    }
    Some(out)
}

fn match_cpp_space_comment_separator_positions(
    branches: &[Ast],
    line: &str,
    position: usize,
    ctx: AnchorContext,
) -> Option<PositionStates> {
    let positions = cpp_space_comment_separator_positions(branches, line, position, ctx)?;
    Some(PositionStates::from_vec(positions))
}

pub(crate) fn cpp_space_comment_separator_positions(
    branches: &[Ast],
    line: &str,
    position: usize,
    ctx: AnchorContext,
) -> Option<Vec<usize>> {
    if !is_cpp_space_comment_separator(branches) {
        return None;
    }
    Some(cpp_space_comment_separator_positions_unchecked(
        line, position, ctx,
    ))
}

pub(crate) fn cpp_space_comment_separator_positions_unchecked(
    line: &str,
    position: usize,
    ctx: AnchorContext,
) -> Vec<usize> {
    let mut out = Vec::new();

    let mut comment_ends = cpp_comment_sequence_ends(line, position);
    comment_ends.reverse();
    out.extend(comment_ends);

    if let Some(pos) = consume_whitespace(line, position).filter(|pos| *pos > position) {
        out.push(pos);
    }
    if previous_char(line, position).is_some_and(|ch| !is_word_char(ch)) {
        out.push(position);
    }
    if char_at(line, position).is_some_and(|(ch, _)| !is_word_char(ch)) {
        out.push(position);
    }
    if position == 0 {
        out.push(position);
    }
    if is_line_end_position(line, position) {
        if line.as_bytes().get(position) == Some(&b'\n') {
            out.push(position + 1);
        }
        out.push(position);
    }
    if ctx.allow_a && position == 0 {
        out.push(position);
    }
    if position == line.len() || line.get(position..).is_some_and(|tail| tail == "\n") {
        out.push(position);
    }

    out
}

fn cpp_comment_sequence_ends(line: &str, start: usize) -> Vec<usize> {
    let mut ends = Vec::new();
    let mut pos = start;
    loop {
        pos = consume_whitespace(line, pos).unwrap_or(pos);
        let Some(after_comment) = consume_c_block_comment(line, pos) else {
            break;
        };
        pos = consume_whitespace(line, after_comment).unwrap_or(after_comment);
        ends.push(pos);
    }
    ends
}

fn consume_whitespace(line: &str, mut pos: usize) -> Option<usize> {
    while let Some((ch, next)) = char_at(line, pos) {
        if !ch.is_whitespace() {
            break;
        }
        pos = next;
    }
    Some(pos)
}

fn consume_c_block_comment(line: &str, pos: usize) -> Option<usize> {
    let rest = line.get(pos..)?;
    if !rest.starts_with("/*") {
        return None;
    }
    let end = rest.get(2..)?.find("*/")?;
    Some(pos + 2 + end + 2)
}

pub(crate) fn is_cpp_space_comment_separator(branches: &[Ast]) -> bool {
    branches.len() >= 6
        && branches.iter().any(is_cpp_comment_sequence_branch)
        && branches.iter().any(is_space_possessive_plus_branch)
        && branches
            .iter()
            .any(|branch| is_not_word_look(branch, LookKind::Behind))
        && branches
            .iter()
            .any(|branch| is_not_word_look(branch, LookKind::Ahead))
        && branches.iter().any(|branch| {
            matches!(
                strip_nonsemantic_group(branch),
                Ast::Anchor(AnchorKind::LineStart)
            )
        })
        && branches.iter().any(is_optional_newline_line_end_branch)
        && branches.iter().any(|branch| {
            matches!(
                strip_nonsemantic_group(branch),
                Ast::Anchor(AnchorKind::TextStart)
            )
        })
        && branches.iter().any(|branch| {
            matches!(
                strip_nonsemantic_group(branch),
                Ast::Anchor(AnchorKind::TextEndOrFinalNewline)
            )
        })
}

pub(crate) fn strip_nonsemantic_group(ast: &Ast) -> &Ast {
    let mut ast = ast;
    while let Ast::Group {
        child, name: None, ..
    } = ast
    {
        ast = child;
    }
    ast
}

fn is_cpp_comment_sequence_branch(ast: &Ast) -> bool {
    let ast = strip_nonsemantic_group(ast);
    let Ast::Repeat {
        node,
        min: 1,
        max: None,
        ..
    } = ast
    else {
        return false;
    };
    let Ast::Concat(nodes) = strip_nonsemantic_group(node) else {
        return false;
    };
    nodes.iter().any(|node| ast_contains_literal(node, "/*"))
        && nodes.iter().any(|node| ast_contains_literal(node, "*/"))
        && nodes.iter().any(is_space_star_branch)
}

fn is_space_star_branch(ast: &Ast) -> bool {
    matches!(
        strip_nonsemantic_group(ast),
        Ast::Repeat {
            node,
            min: 0,
            max: None,
            possessive: true,
            ..
        } if is_perl_class(node, PerlClassKind::Space)
    )
}

fn is_space_possessive_plus_branch(ast: &Ast) -> bool {
    matches!(
        strip_nonsemantic_group(ast),
        Ast::Repeat {
            node,
            min: 1,
            max: None,
            possessive: true,
            ..
        } if is_perl_class(node, PerlClassKind::Space)
    )
}

fn is_not_word_look(ast: &Ast, wanted: LookKind) -> bool {
    matches!(
        strip_nonsemantic_group(ast),
        Ast::Look { kind, child } if *kind == wanted && is_perl_class(child, PerlClassKind::NotWord)
    )
}

fn is_optional_newline_line_end_branch(ast: &Ast) -> bool {
    let Ast::Concat(nodes) = strip_nonsemantic_group(ast) else {
        return false;
    };
    matches!(
        nodes.as_slice(),
        [
            Ast::Repeat {
                node,
                min: 0,
                max: Some(1),
                ..
            },
            Ast::Anchor(AnchorKind::LineEnd)
        ] if matches!(strip_nonsemantic_group(node), Ast::Literal(literal) if literal == "\n")
    )
}

pub(crate) fn is_perl_class(ast: &Ast, wanted: PerlClassKind) -> bool {
    let Ast::Class(class) = strip_nonsemantic_group(ast) else {
        return false;
    };
    !class.negated
        && class.intersections.is_empty()
        && matches!(class.atoms.as_slice(), [ClassAtom::Perl(kind)] if *kind == wanted)
}

fn ast_contains_literal(ast: &Ast, wanted: &str) -> bool {
    match strip_nonsemantic_group(ast) {
        Ast::Literal(literal) => literal == wanted,
        Ast::Concat(nodes) | Ast::Alternation(nodes) => {
            nodes.iter().any(|node| ast_contains_literal(node, wanted))
        }
        Ast::Repeat { node, .. }
        | Ast::Look { child: node, .. }
        | Ast::Flags { child: node, .. } => ast_contains_literal(node, wanted),
        Ast::Conditional {
            matched, unmatched, ..
        } => ast_contains_literal(matched, wanted) || ast_contains_literal(unmatched, wanted),
        _ => false,
    }
}

fn match_concat(
    nodes: &[Ast],
    line: &str,
    state: VmState,
    ctx: AnchorContext,
    flags: RegexFlags,
    budget: &mut StepBudget,
    parsed: &ParsedRegex,
) -> Result<VmStates, BudgetExceeded> {
    let mut states = VmStates::one(state);
    for node in nodes {
        let mut next = VmStates::empty();
        for state in states {
            let states = match_node(node, line, state, ctx, flags, budget, parsed)?;
            push_limited(&mut next, states);
        }
        if next.is_empty() {
            return Ok(VmStates::empty());
        }
        states = next;
    }
    Ok(states)
}

fn match_literal(
    literal: &str,
    line: &str,
    state: VmState,
    flags: RegexFlags,
    _budget: &mut StepBudget,
) -> Result<VmStates, BudgetExceeded> {
    if let Some(end) = match_literal_end(line, state.pos, literal, flags) {
        Ok(VmStates::one(VmState { pos: end, ..state }))
    } else {
        Ok(VmStates::empty())
    }
}

fn match_dot(line: &str, state: VmState, flags: RegexFlags) -> Result<VmStates, BudgetExceeded> {
    let Some((ch, next)) = char_at(line, state.pos) else {
        return Ok(VmStates::empty());
    };
    if ch == '\n' && !flags.dot_matches_new_line {
        return Ok(VmStates::empty());
    }
    Ok(VmStates::one(VmState { pos: next, ..state }))
}

fn match_class(
    class: &CharClass,
    line: &str,
    state: VmState,
    flags: RegexFlags,
) -> Result<VmStates, BudgetExceeded> {
    let Some((ch, next)) = char_at(line, state.pos) else {
        return Ok(VmStates::empty());
    };
    if class_contains(class, ch, flags) {
        Ok(VmStates::one(VmState { pos: next, ..state }))
    } else {
        Ok(VmStates::empty())
    }
}

fn match_anchor(
    anchor: AnchorKind,
    line: &str,
    state: VmState,
    ctx: AnchorContext,
) -> Result<VmStates, BudgetExceeded> {
    let matches = anchor_matches(anchor, line, state.pos, ctx);
    if matches {
        Ok(VmStates::one(state))
    } else {
        Ok(VmStates::empty())
    }
}

pub(crate) fn anchor_matches(
    anchor: AnchorKind,
    line: &str,
    pos: usize,
    ctx: AnchorContext,
) -> bool {
    match anchor {
        AnchorKind::LineStart => pos == 0,
        AnchorKind::LineEnd => is_line_end_position(line, pos),
        // vscode-textmate rewrites Oniguruma `\z` as
        // `$(?!\n)(?<!\n)`. Logical lines carry a synthetic trailing newline,
        // so `\z` must not close document-scoped frames on every line.
        AnchorKind::TextEnd => pos == line.len() && !line.ends_with('\n'),
        AnchorKind::TextEndOrFinalNewline => {
            pos == line.len() || line.get(pos..).is_some_and(|tail| tail == "\n")
        }
        AnchorKind::TextStart => ctx.allow_a && pos == 0,
        AnchorKind::Continuation => ctx.allow_g && pos == ctx.g_pos,
        AnchorKind::WordBoundary => is_word_boundary(line, pos),
        AnchorKind::NotWordBoundary => !is_word_boundary(line, pos),
    }
}

pub(crate) fn is_line_end_position(line: &str, pos: usize) -> bool {
    pos == line.len() || (line.as_bytes().get(pos).copied() == Some(b'\n') && pos + 1 == line.len())
}

#[allow(clippy::too_many_arguments)]
fn match_repeat(
    node: &Ast,
    min: usize,
    max: Option<usize>,
    greedy: bool,
    possessive: bool,
    atomic: bool,
    line: &str,
    state: VmState,
    ctx: AnchorContext,
    flags: RegexFlags,
    budget: &mut StepBudget,
    parsed: &ParsedRegex,
) -> Result<VmStates, BudgetExceeded> {
    // With an exact repetition count there is no repetition-count choice to
    // make possessive. Oniguruma still permits backtracking inside the atom.
    let possessive = possessive && (atomic || max != Some(min));
    if let Some(states) = match_simple_repeat(
        node, min, max, greedy, possessive, line, &state, flags, budget,
    )? {
        return Ok(states);
    }
    if possessive {
        let max = max.unwrap_or_else(|| line.len().saturating_sub(state.pos).saturating_add(1));
        let mut current = state;
        let mut count = 0usize;
        while count < max && (greedy || count < min) {
            budget.step()?;
            let Some(next) = match_node(node, line, current.clone(), ctx, flags, budget, parsed)?
                .into_iter()
                .next()
            else {
                break;
            };
            count += 1;
            let zero_width = next.pos == current.pos && next.captures == current.captures;
            current = next;
            if zero_width {
                break;
            }
        }
        return Ok(if count >= min {
            VmStates::one(current)
        } else {
            VmStates::empty()
        });
    }
    let max = max.unwrap_or_else(|| line.len().saturating_sub(state.pos).saturating_add(1));
    // Emit exit states in Oniguruma preference order with an explicit DFS:
    // a greedy repeat prefers another iteration over exiting, a lazy repeat
    // prefers exiting, and the body's own state order is preserved either
    // way. Sorting by position here would invert the preference of lazy or
    // ordered-alternation bodies inside the repeat.
    enum Work {
        Visit(usize, VmState),
        Accept(VmState),
    }
    let mut stack = vec![Work::Visit(0, state)];
    let mut accepted: Vec<VmState> = Vec::new();
    while let Some(work) = stack.pop() {
        budget.step()?;
        let (count, current) = match work {
            Work::Accept(state) => {
                let duplicate = accepted
                    .iter()
                    .any(|seen| seen.pos == state.pos && seen.captures == state.captures);
                if !duplicate {
                    accepted.push(state);
                    if accepted.len() >= STATE_LIMIT {
                        break;
                    }
                }
                continue;
            }
            Work::Visit(count, state) => (count, state),
        };
        if greedy && count >= min {
            // Popped after the children below, so exiting stays the least
            // preferred continuation of this iteration count.
            stack.push(Work::Accept(current.clone()));
        }
        let mut lazy_accept = (!greedy && count >= min).then(|| current.clone());
        if count < max && stack.len() < STATE_LIMIT {
            let next_states = match_node(node, line, current.clone(), ctx, flags, budget, parsed)?;
            let push = |next: VmState, stack: &mut Vec<Work>| {
                // Zero-width quantified atoms are legal in Oniguruma, but
                // cannot be allowed to loop forever. They must still run
                // enough times to satisfy a finite minimum, and a
                // capture-changing zero-width iteration is meaningful once
                // before it stabilizes.
                if next.pos == current.pos && next.captures == current.captures {
                    if count < min {
                        stack.push(Work::Visit(count + 1, next));
                    }
                    return;
                }
                stack.push(Work::Visit(count + 1, next));
            };
            match next_states {
                VmStates::Empty => {}
                VmStates::One(next) => push(next, &mut stack),
                VmStates::Many(states) => {
                    // Reverse so the body's first-preference state pops first.
                    for next in states.into_iter().rev() {
                        push(next, &mut stack);
                    }
                }
            }
        }
        if let Some(state) = lazy_accept.take() {
            // Pushed after the children, so exiting pops first for lazy.
            stack.push(Work::Accept(state));
        }
    }
    Ok(VmStates::from_vec(accepted))
}

#[allow(clippy::too_many_arguments)]
fn match_simple_repeat(
    node: &Ast,
    min: usize,
    max: Option<usize>,
    greedy: bool,
    possessive: bool,
    line: &str,
    state: &VmState,
    flags: RegexFlags,
    budget: &mut StepBudget,
) -> Result<Option<VmStates>, BudgetExceeded> {
    if !is_simple_repeat_atom(node) {
        return Ok(None);
    }
    let max = max.unwrap_or(usize::MAX);
    let mut positions = Vec::new();
    positions.push(state.pos);
    let mut pos = state.pos;
    let mut count = 0usize;
    while count < max {
        budget.step()?;
        let Some(next) = simple_repeat_next(node, line, pos, flags) else {
            break;
        };
        if next == pos {
            break;
        }
        positions.push(next);
        pos = next;
        count += 1;
    }
    if count < min {
        return Ok(Some(VmStates::empty()));
    }
    let accepted_positions = &positions[min..];
    if possessive {
        let Some(pos) = accepted_positions.last().copied() else {
            return Ok(Some(VmStates::empty()));
        };
        return Ok(Some(VmStates::one(VmState {
            pos,
            captures: state.captures.clone(),
        })));
    }
    let mut states = Vec::with_capacity(accepted_positions.len().min(STATE_LIMIT));
    if greedy {
        for pos in accepted_positions.iter().rev().copied().take(STATE_LIMIT) {
            states.push(VmState {
                pos,
                captures: state.captures.clone(),
            });
        }
    } else {
        for pos in accepted_positions.iter().copied().take(STATE_LIMIT) {
            states.push(VmState {
                pos,
                captures: state.captures.clone(),
            });
        }
    }
    Ok(Some(VmStates::from_vec(states)))
}

fn is_simple_repeat_atom(node: &Ast) -> bool {
    matches!(node, Ast::Literal(literal) if !literal.is_empty())
        || matches!(node, Ast::Class(_) | Ast::Dot)
}

fn simple_repeat_next(node: &Ast, line: &str, pos: usize, flags: RegexFlags) -> Option<usize> {
    match node {
        Ast::Literal(literal) => match_literal_end(line, pos, literal, flags),
        Ast::Class(class) => {
            let (ch, next) = char_at(line, pos)?;
            class_contains(class, ch, flags).then_some(next)
        }
        Ast::Dot => {
            let (ch, next) = char_at(line, pos)?;
            (ch != '\n' || flags.dot_matches_new_line).then_some(next)
        }
        _ => None,
    }
}

#[allow(clippy::too_many_arguments)]
fn match_look(
    kind: LookKind,
    child: &Ast,
    line: &str,
    state: VmState,
    ctx: AnchorContext,
    flags: RegexFlags,
    budget: &mut StepBudget,
    parsed: &ParsedRegex,
) -> Result<VmStates, BudgetExceeded> {
    if kind == LookKind::Ahead {
        let position = state.pos;
        let mut states = match_node(child, line, state, ctx, flags, budget, parsed)?;
        for matched in states.iter_mut() {
            matched.pos = position;
        }
        return Ok(states);
    }
    match kind {
        LookKind::Ahead => unreachable!("positive lookahead returned above"),
        LookKind::NotAhead => {
            let states = match_node(child, line, state.clone(), ctx, flags, budget, parsed)?;
            Ok(if states.is_empty() {
                VmStates::one(state)
            } else {
                VmStates::empty()
            })
        }
        LookKind::Behind | LookKind::NotBehind => {
            let end = state.pos;
            let matched =
                if let Some((min_width, max_width)) = lookbehind_byte_width_bounds(child, flags) {
                    if let Some(latest_start) = end.checked_sub(min_width) {
                        let earliest_start = end.saturating_sub(max_width);
                        lookbehind_state_in_window(
                            child,
                            line,
                            earliest_start,
                            latest_start,
                            end,
                            &state,
                            ctx,
                            flags,
                            budget,
                            parsed,
                        )?
                    } else {
                        None
                    }
                } else {
                    lookbehind_state_in_window(
                        child, line, 0, end, end, &state, ctx, flags, budget, parsed,
                    )?
                };
            match (kind, matched) {
                (LookKind::Behind, Some(mut matched)) => {
                    matched.pos = end;
                    Ok(VmStates::one(matched))
                }
                (LookKind::NotBehind, None) => Ok(VmStates::one(state)),
                (LookKind::Behind, None) | (LookKind::NotBehind, Some(_)) => Ok(VmStates::empty()),
                (LookKind::Ahead | LookKind::NotAhead, _) => unreachable!(),
            }
        }
    }
}

#[allow(clippy::too_many_arguments)]
fn lookbehind_state_in_window(
    child: &Ast,
    line: &str,
    earliest_start: usize,
    latest_start: usize,
    end: usize,
    state: &VmState,
    ctx: AnchorContext,
    flags: RegexFlags,
    budget: &mut StepBudget,
    parsed: &ParsedRegex,
) -> Result<Option<VmState>, BudgetExceeded> {
    // Oniguruma probes variable-width lookbehind from the closest viable
    // boundary backwards. This affects both alternation priority and captures.
    for start in (earliest_start..=latest_start).rev() {
        if !line.is_char_boundary(start) {
            continue;
        }
        let probe = VmState {
            pos: start,
            captures: state.captures.clone(),
        };
        let states = match_node(child, line, probe, ctx, flags, budget, parsed)?;
        if let Some(matched) = states.into_iter().find(|end_state| end_state.pos == end) {
            return Ok(Some(matched));
        }
    }
    Ok(None)
}

/// Bounds on bytes consumed by this engine's scalar literal comparison.
/// Case folding need not preserve UTF-8 width (k/K, s/ſ, ß/ẞ). A folded
/// literal consumes one input scalar per pattern scalar, not its source bytes.
/// These conservative bounds only select probes; matching remains authoritative.
pub(crate) fn literal_byte_width(literal: &str, flags: RegexFlags) -> (usize, usize) {
    if flags.case_insensitive {
        let scalars = literal.chars().count();
        (scalars, scalars.saturating_mul(4))
    } else {
        (literal.len(), literal.len())
    }
}

fn lookbehind_byte_width_bounds(ast: &Ast, flags: RegexFlags) -> Option<(usize, usize)> {
    match ast {
        Ast::Empty | Ast::Anchor(_) | Ast::Look { .. } => Some((0, 0)),
        Ast::Literal(literal) => Some(literal_byte_width(literal, flags)),
        Ast::Dot | Ast::Class(_) => Some((1, 4)),
        Ast::Grapheme => None,
        Ast::Concat(nodes) => {
            let mut min = 0usize;
            let mut max = 0usize;
            for node in nodes {
                let (node_min, node_max) = lookbehind_byte_width_bounds(node, flags)?;
                min = min.saturating_add(node_min);
                max = max.saturating_add(node_max);
            }
            Some((min, max))
        }
        Ast::Alternation(branches) => {
            let mut bounds = branches
                .iter()
                .map(|branch| lookbehind_byte_width_bounds(branch, flags));
            let (mut min, mut max) = bounds.next().unwrap_or(Some((0, 0)))?;
            for bound in bounds {
                let (branch_min, branch_max) = bound?;
                min = min.min(branch_min);
                max = max.max(branch_max);
            }
            Some((min, max))
        }
        Ast::Repeat { node, min, max, .. } => {
            let max = (*max)?;
            let (node_min, node_max) = lookbehind_byte_width_bounds(node, flags)?;
            Some((node_min.saturating_mul(*min), node_max.saturating_mul(max)))
        }
        Ast::Group { child, .. } => lookbehind_byte_width_bounds(child, flags),
        Ast::Flags { flags, child } => lookbehind_byte_width_bounds(child, *flags),
        Ast::Backref(_) | Ast::Conditional { .. } | Ast::Subroutine(_) | Ast::Unsupported(_) => {
            None
        }
    }
}

fn subroutine_index(subroutine: &Backref, parsed: &ParsedRegex) -> Option<u32> {
    Some(match subroutine {
        Backref::Number(index) => *index,
        Backref::Name(name) => *parsed.named_captures.get(name)?,
    })
}

fn find_subroutine_group<'a>(
    ast: &'a Ast,
    subroutine: &Backref,
    parsed: &ParsedRegex,
) -> Option<&'a Ast> {
    let wanted = subroutine_index(subroutine, parsed)?;
    match ast {
        Ast::Group {
            index: Some(index), ..
        } if *index == wanted => Some(ast),
        Ast::Concat(nodes) | Ast::Alternation(nodes) => nodes
            .iter()
            .find_map(|node| find_subroutine_group(node, subroutine, parsed)),
        Ast::Conditional {
            matched, unmatched, ..
        } => find_subroutine_group(matched, subroutine, parsed)
            .or_else(|| find_subroutine_group(unmatched, subroutine, parsed)),
        Ast::Repeat { node, .. }
        | Ast::Group { child: node, .. }
        | Ast::Look { child: node, .. }
        | Ast::Flags { child: node, .. } => find_subroutine_group(node, subroutine, parsed),
        _ => None,
    }
}

fn ast_at_path<'a>(mut ast: &'a Ast, path: &[AstPathStep]) -> Option<&'a Ast> {
    for step in path {
        ast = match (step, ast) {
            (AstPathStep::Branch(index), Ast::Concat(nodes) | Ast::Alternation(nodes)) => {
                nodes.get(*index)?
            }
            (
                AstPathStep::Branch(index),
                Ast::Conditional {
                    matched, unmatched, ..
                },
            ) => match index {
                0 => matched,
                1 => unmatched,
                _ => return None,
            },
            (
                AstPathStep::Child,
                Ast::Repeat { node, .. }
                | Ast::Group { child: node, .. }
                | Ast::Look { child: node, .. }
                | Ast::Flags { child: node, .. },
            ) => node,
            _ => return None,
        };
    }
    Some(ast)
}

fn match_backref(
    backref: &Backref,
    line: &str,
    state: VmState,
    parsed: &ParsedRegex,
    flags: RegexFlags,
    _budget: &mut StepBudget,
) -> Result<VmStates, BudgetExceeded> {
    let backref_end = |index: usize| {
        let range = state.captures.get(index)?.as_ref()?;
        match_literal_end(line, state.pos, line.get(range.clone())?, flags)
    };
    let end = match backref {
        Backref::Number(index) => backref_end(*index as usize),
        // Oniguruma tries same-named groups from the last one, skips unset
        // groups, and commits to the first whose text matches.
        Backref::Name(name) => match parsed.duplicate_names.get(name) {
            Some(groups) => groups
                .iter()
                .rev()
                .find_map(|group| backref_end(*group as usize)),
            None => backref_end(parsed.named_captures.get(name).copied().unwrap_or(0) as usize),
        },
    };
    Ok(end.map_or_else(VmStates::empty, |end| {
        VmStates::one(VmState { pos: end, ..state })
    }))
}

fn ast_exact_literal(ast: &Ast) -> Option<String> {
    match ast {
        Ast::Empty => Some(String::new()),
        Ast::Literal(literal) => Some(literal.as_str().to_owned()),
        Ast::Concat(nodes) => {
            let mut out = String::new();
            for node in nodes {
                out.push_str(&ast_exact_literal(node)?);
            }
            Some(out)
        }
        Ast::Group { child, .. } => ast_exact_literal(child),
        Ast::Flags { flags, child } if !flags.case_insensitive => ast_exact_literal(child),
        _ => None,
    }
}

fn push_limited(out: &mut VmStates, states: VmStates) {
    for state in states {
        if out.len() >= STATE_LIMIT {
            break;
        }
        out.push(state);
    }
}

pub(crate) fn class_contains(class: &CharClass, ch: char, flags: RegexFlags) -> bool {
    let matched = if flags.case_insensitive && class.bracketed {
        // Oniguruma folds a bracketed class once: it builds the literal set,
        // nested classes and intersections included, and admits a scalar
        // when one of its case variants is in that set. Only the top-level
        // negation applies afterwards.
        CaseVariants::new(ch)
            .iter()
            .any(|variant| class_positive_contains(class, variant))
    } else {
        class_positive_contains(class, ch)
    };
    matched != class.negated
}

/// Case-sensitive membership in `class` ignoring its top-level negation.
pub(crate) fn class_positive_contains(class: &CharClass, ch: char) -> bool {
    let union_contains = |atoms: &[ClassAtom]| atoms.iter().any(|atom| atom_contains(atom, ch));
    union_contains(&class.atoms)
        && class
            .intersections
            .iter()
            .all(|atoms| union_contains(atoms))
}

fn atom_contains(atom: &ClassAtom, ch: char) -> bool {
    match atom {
        ClassAtom::Char(expected) => *expected == ch,
        ClassAtom::Range(start, end) => start <= &ch && &ch <= end,
        ClassAtom::Perl(kind) => perl_class_contains(*kind, ch),
        ClassAtom::Posix { name, negated } => {
            let contains = posix_class_contains(name, ch);
            if *negated { !contains } else { contains }
        }
        ClassAtom::Unicode { name, negated } => {
            let contains = unicode_class_contains(name, ch);
            if *negated { !contains } else { contains }
        }
        ClassAtom::Nested(class) => class_positive_contains(class, ch) != class.negated,
    }
}

pub(crate) fn perl_class_contains(kind: PerlClassKind, ch: char) -> bool {
    match kind {
        PerlClassKind::Digit => ch.is_ascii_digit(),
        PerlClassKind::NotDigit => !ch.is_ascii_digit(),
        PerlClassKind::Space => ch.is_whitespace(),
        PerlClassKind::NotSpace => !ch.is_whitespace(),
        PerlClassKind::Word => is_word_char(ch),
        PerlClassKind::NotWord => !is_word_char(ch),
        PerlClassKind::HorizontalSpace => ch.is_ascii_hexdigit(),
        PerlClassKind::NotHorizontalSpace => !ch.is_ascii_hexdigit(),
        PerlClassKind::VerticalSpace => matches!(ch, '\n' | '\r' | '\u{000B}' | '\u{000C}'),
        PerlClassKind::NotVerticalSpace => !matches!(ch, '\n' | '\r' | '\u{000B}' | '\u{000C}'),
        PerlClassKind::NotNewline => ch != '\n',
    }
}

pub(crate) fn posix_class_contains(name: &str, ch: char) -> bool {
    posix_class_predicate(name)(ch)
}

pub(crate) type CharPredicate = fn(char) -> bool;

/// Resolves a POSIX bracket class name (ASCII case-insensitive) once, so
/// callers probing many characters do not repeat the name comparison.
/// Unknown names match nothing.
pub(crate) fn posix_class_predicate(name: &str) -> CharPredicate {
    const CLASSES: [(&str, CharPredicate); 14] = [
        ("alnum", |ch| ch.is_alphanumeric()),
        ("alpha", |ch| ch.is_alphabetic()),
        ("ascii", |ch| ch.is_ascii()),
        ("blank", |ch| matches!(ch, '\t' | ' ')),
        ("cntrl", |ch| ch.is_control()),
        ("digit", |ch| ch.is_ascii_digit()),
        ("graph", |ch| !ch.is_whitespace() && !ch.is_control()),
        ("lower", |ch| ch.is_lowercase()),
        ("print", |ch| !ch.is_control()),
        ("punct", |ch| ch.is_ascii_punctuation()),
        ("space", |ch| ch.is_whitespace()),
        ("upper", |ch| ch.is_uppercase()),
        ("word", is_word_char),
        ("xdigit", |ch| ch.is_ascii_hexdigit()),
    ];
    CLASSES
        .iter()
        .find(|(class, _)| *class == name)
        .or_else(|| {
            CLASSES
                .iter()
                .find(|(class, _)| class.eq_ignore_ascii_case(name))
        })
        .map_or(|_| false, |(_, predicate)| *predicate)
}

pub(crate) fn unicode_class_contains(name: &str, ch: char) -> bool {
    unicode_property(name).contains(name, ch)
}

/// Property selected by a `\p{…}` name. Resolving the name first means a
/// query computes only the Unicode table lookup that property needs, instead
/// of a general-category search for every name plus two script searches for
/// every non-matching category name.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum UnicodeProperty {
    Letter,
    Alphabetic,
    Alnum,
    Ascii,
    Blank,
    Cntrl,
    Digit,
    Graph,
    Lower,
    Print,
    Punct,
    Space,
    Upper,
    Xdigit,
    Number,
    Mark,
    Punctuation,
    Symbol,
    Category(unicode_general_category::GeneralCategory),
    DecimalNumber,
    Separator,
    Word,
    XidStart,
    XidContinue,
    Script,
}

/// Every general category, for resolving two-letter abbreviations.
const GENERAL_CATEGORIES: [unicode_general_category::GeneralCategory; 30] = {
    use unicode_general_category::GeneralCategory as Gc;
    [
        Gc::ClosePunctuation,
        Gc::ConnectorPunctuation,
        Gc::Control,
        Gc::CurrencySymbol,
        Gc::DashPunctuation,
        Gc::DecimalNumber,
        Gc::EnclosingMark,
        Gc::FinalPunctuation,
        Gc::Format,
        Gc::InitialPunctuation,
        Gc::LetterNumber,
        Gc::LineSeparator,
        Gc::LowercaseLetter,
        Gc::MathSymbol,
        Gc::ModifierLetter,
        Gc::ModifierSymbol,
        Gc::NonspacingMark,
        Gc::OpenPunctuation,
        Gc::OtherLetter,
        Gc::OtherNumber,
        Gc::OtherPunctuation,
        Gc::OtherSymbol,
        Gc::ParagraphSeparator,
        Gc::PrivateUse,
        Gc::SpaceSeparator,
        Gc::SpacingMark,
        Gc::Surrogate,
        Gc::TitlecaseLetter,
        Gc::Unassigned,
        Gc::UppercaseLetter,
    ]
};

/// Resolves names in the evaluator's precedence order. A category
/// abbreviation is checked where the evaluator compared it with the
/// character's own category; no later name (a long property name, `XID_*`,
/// or a script name) is also a two-letter category abbreviation, which
/// `unicode_property_resolution_matches_the_reference_evaluator` checks.
fn unicode_property(name: &str) -> UnicodeProperty {
    let is = |candidate: &str| name.eq_ignore_ascii_case(candidate);
    if is("l") || is("letter") {
        UnicodeProperty::Letter
    } else if is("alphabetic") || is("alpha") {
        UnicodeProperty::Alphabetic
    } else if is("alnum") {
        UnicodeProperty::Alnum
    } else if is("ascii") {
        UnicodeProperty::Ascii
    } else if is("blank") {
        UnicodeProperty::Blank
    } else if is("cntrl") {
        UnicodeProperty::Cntrl
    } else if is("digit") {
        UnicodeProperty::Digit
    } else if is("graph") {
        UnicodeProperty::Graph
    } else if is("lower") {
        UnicodeProperty::Lower
    } else if is("print") {
        UnicodeProperty::Print
    } else if is("punct") {
        UnicodeProperty::Punct
    } else if is("space") {
        UnicodeProperty::Space
    } else if is("upper") {
        UnicodeProperty::Upper
    } else if is("xdigit") {
        UnicodeProperty::Xdigit
    } else if is("n") || is("number") {
        UnicodeProperty::Number
    } else if is("m") || is("mark") {
        UnicodeProperty::Mark
    } else if is("p") || is("punctuation") {
        UnicodeProperty::Punctuation
    } else if is("s") || is("symbol") {
        UnicodeProperty::Symbol
    } else if let Some(category) = GENERAL_CATEGORIES
        .iter()
        .find(|category| is(category.abbreviation()))
    {
        UnicodeProperty::Category(*category)
    } else if is("decimal_number") {
        UnicodeProperty::DecimalNumber
    } else if is("z") || is("separator") {
        UnicodeProperty::Separator
    } else if is("word") {
        UnicodeProperty::Word
    } else if let Some(start) = xid_property(name) {
        if start {
            UnicodeProperty::XidStart
        } else {
            UnicodeProperty::XidContinue
        }
    } else {
        UnicodeProperty::Script
    }
}

impl UnicodeProperty {
    fn contains(self, name: &str, ch: char) -> bool {
        use unicode_general_category::{GeneralCategory as Gc, get_general_category};
        use unicode_script::UnicodeScript;

        match self {
            Self::Letter => matches!(
                get_general_category(ch),
                Gc::LowercaseLetter
                    | Gc::ModifierLetter
                    | Gc::OtherLetter
                    | Gc::TitlecaseLetter
                    | Gc::UppercaseLetter
            ),
            Self::Alphabetic => ch.is_alphabetic(),
            Self::Alnum => ch.is_alphanumeric(),
            Self::Ascii => ch.is_ascii(),
            Self::Blank => matches!(ch, '\t' | ' '),
            Self::Cntrl => ch.is_control(),
            Self::Digit => ch.is_ascii_digit(),
            Self::Graph => !ch.is_whitespace() && !ch.is_control(),
            Self::Lower => ch.is_lowercase(),
            Self::Print => !ch.is_control(),
            Self::Punct => ch.is_ascii_punctuation(),
            Self::Space | Self::Separator => ch.is_whitespace(),
            Self::Upper => ch.is_uppercase(),
            Self::Xdigit => ch.is_ascii_hexdigit(),
            Self::Number => matches!(
                get_general_category(ch),
                Gc::DecimalNumber | Gc::LetterNumber | Gc::OtherNumber
            ),
            Self::Mark => matches!(
                get_general_category(ch),
                Gc::EnclosingMark | Gc::NonspacingMark | Gc::SpacingMark
            ),
            Self::Punctuation => matches!(
                get_general_category(ch),
                Gc::ClosePunctuation
                    | Gc::ConnectorPunctuation
                    | Gc::DashPunctuation
                    | Gc::FinalPunctuation
                    | Gc::InitialPunctuation
                    | Gc::OpenPunctuation
                    | Gc::OtherPunctuation
            ),
            Self::Symbol => matches!(
                get_general_category(ch),
                Gc::CurrencySymbol | Gc::MathSymbol | Gc::ModifierSymbol | Gc::OtherSymbol
            ),
            Self::Category(category) => get_general_category(ch) == category,
            Self::DecimalNumber => get_general_category(ch) == Gc::DecimalNumber,
            Self::Word => is_word_char(ch),
            Self::XidStart => unicode_ident::is_xid_start(ch),
            Self::XidContinue => unicode_ident::is_xid_continue(ch),
            Self::Script => {
                let script = ch.script();
                script.full_name().eq_ignore_ascii_case(name)
                    || script.short_name().eq_ignore_ascii_case(name)
            }
        }
    }
}

/// Oniguruma matches property names loosely, ignoring case, spaces,
/// underscores, and hyphens. Returns `Some(true)` for XID_Start and
/// `Some(false)` for XID_Continue.
fn xid_property(name: &str) -> Option<bool> {
    let mut normalized = [0u8; 11];
    let mut len = 0;
    for byte in name
        .bytes()
        .filter(|byte| !matches!(byte, b' ' | b'_' | b'-'))
    {
        *normalized.get_mut(len)? = byte.to_ascii_lowercase();
        len += 1;
    }
    match &normalized[..len] {
        b"xids" | b"xidstart" => Some(true),
        b"xidc" | b"xidcontinue" => Some(false),
        _ => None,
    }
}

fn char_eq(expected: char, actual: char, flags: RegexFlags) -> bool {
    if flags.case_insensitive {
        unicode_case_eq(expected, actual)
    } else {
        expected == actual
    }
}

#[inline]
pub(crate) fn match_literal_end(
    line: &str,
    start: usize,
    literal: &str,
    flags: RegexFlags,
) -> Option<usize> {
    if !flags.case_insensitive {
        let end = start.checked_add(literal.len())?;
        // Byte compare avoids `str::get`'s UTF-8 boundary walk on both ends.
        // Callers feed character boundaries; reject a non-boundary start so
        // malformed probes keep returning no match.
        return (line.is_char_boundary(start)
            && line.as_bytes().get(start..end)? == literal.as_bytes())
        .then_some(end);
    }
    if literal.is_ascii() {
        let end = start.checked_add(literal.len())?;
        if let Some(candidate) = line.as_bytes().get(start..end)
            && candidate.is_ascii()
            && line.is_char_boundary(start)
        {
            return candidate
                .eq_ignore_ascii_case(literal.as_bytes())
                .then_some(end);
        }
        return match_ascii_literal_with_mixed_width_fold(line, start, literal);
    }

    let mut position = start;
    for expected in literal.chars() {
        let (actual, end) = char_at(line, position)?;
        if !unicode_case_eq(expected, actual) {
            return None;
        }
        position = end;
    }
    Some(position)
}

fn match_ascii_literal_with_mixed_width_fold(
    line: &str,
    start: usize,
    literal: &str,
) -> Option<usize> {
    let bytes = line.as_bytes();
    let mut position = start;
    for expected in literal.bytes() {
        let actual = *bytes.get(position)?;
        if actual.is_ascii() {
            if !expected.eq_ignore_ascii_case(&actual) {
                return None;
            }
            position += 1;
        } else if expected.eq_ignore_ascii_case(&b's')
            && bytes.get(position..)?.starts_with(&[0xc5, 0xbf])
        {
            position += 2; // U+017F LONG S
        } else if expected.eq_ignore_ascii_case(&b'k')
            && bytes.get(position..)?.starts_with(&[0xe2, 0x84, 0xaa])
        {
            position += 3; // U+212A KELVIN SIGN
        } else {
            return None;
        }
    }
    Some(position)
}

#[inline]
pub(crate) fn unicode_case_eq(left: char, right: char) -> bool {
    // Case-insensitive regexes are overwhelmingly ASCII. Avoid constructing
    // Unicode case-mapping iterators for that hot path while retaining the
    // Unicode fold for mixed/non-ASCII pairs such as `K` and `K`.
    if left == right {
        return true;
    }
    if left.is_ascii() && right.is_ascii() {
        return left.eq_ignore_ascii_case(&right);
    }
    // Oniguruma uses the default non-Turkic fold: dotless i does not join the
    // ASCII I/i equivalence class.
    if left == '\u{131}' || right == '\u{131}' {
        return false;
    }
    left.to_lowercase().eq(right.to_lowercase()) || left.to_uppercase().eq(right.to_uppercase())
}

/// Full Unicode lowercase and uppercase mappings of one scalar, NUL-padded.
///
/// `unicode_case_eq` re-derives these
/// mappings (a binary search each) for every comparison. Keying the
/// comparison lets hot loops map each input scalar once and compare it
/// against pattern-side keys prepared at compile time. NUL padding is
/// unambiguous: only U+0000 maps to a sequence containing NUL.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct CaseFoldKey {
    ch: char,
    lower: [char; 3],
    upper: [char; 3],
}

impl CaseFoldKey {
    pub(crate) fn ch(&self) -> char {
        self.ch
    }

    /// Identical full case mappings, which make `unicode_case_eq` agree
    /// for every third scalar.
    pub(crate) fn same_mappings(&self, other: &Self) -> bool {
        self.lower == other.lower && self.upper == other.upper
    }

    #[inline]
    pub(crate) fn new(ch: char) -> Self {
        if ch.is_ascii() {
            return Self {
                ch,
                lower: [ch.to_ascii_lowercase(), '\0', '\0'],
                upper: [ch.to_ascii_uppercase(), '\0', '\0'],
            };
        }
        let mut lower = ['\0'; 3];
        for (slot, mapped) in lower.iter_mut().zip(ch.to_lowercase()) {
            *slot = mapped;
        }
        let mut upper = ['\0'; 3];
        for (slot, mapped) in upper.iter_mut().zip(ch.to_uppercase()) {
            *slot = mapped;
        }
        Self { ch, lower, upper }
    }

    /// Exactly `unicode_case_eq(self.ch, other.ch)`.
    #[inline]
    pub(crate) fn case_eq(&self, other: &Self) -> bool {
        if self.ch == other.ch {
            return true;
        }
        if self.ch == '\u{131}' || other.ch == '\u{131}' {
            return false;
        }
        self.lower == other.lower || self.upper == other.upper
    }
}

#[inline]
pub(crate) fn char_at(line: &str, pos: usize) -> Option<(char, usize)> {
    let byte = *line.as_bytes().get(pos)?;
    if byte < 0x80 {
        Some((byte as char, pos + 1))
    } else {
        let ch = line.get(pos..)?.chars().next()?;
        Some((ch, pos + ch.len_utf8()))
    }
}

fn grapheme_end(line: &str, position: usize) -> Option<usize> {
    let grapheme = line.get(position..)?.graphemes(true).next()?;
    Some(position + grapheme.len())
}

/// Every character boundary from `from` through the line end. Callers have
/// already rejected a `from` that is not a boundary.
fn char_boundaries_from(line: &str, from: usize) -> impl Iterator<Item = usize> + '_ {
    line[from..]
        .char_indices()
        .map(move |(index, _)| from + index)
        .chain(std::iter::once(line.len()))
}

fn start_hint(ast: &Ast) -> StartHint {
    start_anchors(ast).map_or(StartHint::Unanchored, StartHint::Anchored)
}

/// Anchors one of which every match must satisfy at its start, or `None`
/// when some branch can begin elsewhere.
fn start_anchors(ast: &Ast) -> Option<StartAnchors> {
    match ast {
        Ast::Anchor(AnchorKind::LineStart) => Some(StartAnchors {
            line_start: true,
            ..StartAnchors::default()
        }),
        Ast::Anchor(AnchorKind::TextStart) => Some(StartAnchors {
            text_start: true,
            ..StartAnchors::default()
        }),
        Ast::Anchor(AnchorKind::Continuation) => Some(StartAnchors {
            continuation: true,
            ..StartAnchors::default()
        }),
        Ast::Concat(nodes) => nodes
            .iter()
            .find(|node| !matches!(node, Ast::Empty))
            .and_then(start_anchors),
        Ast::Alternation(branches) => branches
            .iter()
            .try_fold(StartAnchors::default(), |all, branch| {
                Some(all.union(start_anchors(branch)?))
            }),
        Ast::Group { child, .. } | Ast::Flags { child, .. } => start_anchors(child),
        _ => None,
    }
}

fn char_boundaries_until(line: &str, until: usize) -> Vec<usize> {
    line.char_indices()
        .map(|(index, _)| index)
        .take_while(move |index| *index <= until)
        .chain(std::iter::once(until))
        .collect()
}

fn is_word_boundary(line: &str, pos: usize) -> bool {
    let before = previous_char(line, pos).is_some_and(is_word_char);
    let after = char_at(line, pos)
        .map(|(ch, _)| ch)
        .is_some_and(is_word_char);
    before != after
}

#[inline]
pub(crate) fn previous_char(line: &str, pos: usize) -> Option<char> {
    if pos == 0 || pos > line.len() {
        return None;
    }
    let prev = line.as_bytes()[pos - 1];
    if prev < 0x80 {
        Some(prev as char)
    } else {
        line.get(..pos)?.chars().next_back()
    }
}

fn is_word_char(ch: char) -> bool {
    is_unicode_word_char(ch)
}

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

    fn ctx() -> AnchorContext {
        AnchorContext {
            allow_a: true,
            allow_g: false,
            g_pos: 0,
        }
    }

    /// The evaluator before property names were resolved up front.
    fn unicode_class_contains_reference(name: &str, ch: char) -> bool {
        use unicode_general_category::{GeneralCategory as Gc, get_general_category};
        use unicode_script::UnicodeScript;

        let category = get_general_category(ch);
        let is_letter = matches!(
            category,
            Gc::LowercaseLetter
                | Gc::ModifierLetter
                | Gc::OtherLetter
                | Gc::TitlecaseLetter
                | Gc::UppercaseLetter
        );
        let is_mark = matches!(
            category,
            Gc::EnclosingMark | Gc::NonspacingMark | Gc::SpacingMark
        );
        let is_number = matches!(
            category,
            Gc::DecimalNumber | Gc::LetterNumber | Gc::OtherNumber
        );
        let is_punctuation = matches!(
            category,
            Gc::ClosePunctuation
                | Gc::ConnectorPunctuation
                | Gc::DashPunctuation
                | Gc::FinalPunctuation
                | Gc::InitialPunctuation
                | Gc::OpenPunctuation
                | Gc::OtherPunctuation
        );
        let is_symbol = matches!(
            category,
            Gc::CurrencySymbol | Gc::MathSymbol | Gc::ModifierSymbol | Gc::OtherSymbol
        );
        if name.eq_ignore_ascii_case("l") || name.eq_ignore_ascii_case("letter") {
            is_letter
        } else if name.eq_ignore_ascii_case("alphabetic") {
            ch.is_alphabetic()
        } else if name.eq_ignore_ascii_case("alnum") {
            ch.is_alphanumeric()
        } else if name.eq_ignore_ascii_case("alpha") {
            ch.is_alphabetic()
        } else if name.eq_ignore_ascii_case("ascii") {
            ch.is_ascii()
        } else if name.eq_ignore_ascii_case("blank") {
            matches!(ch, '\t' | ' ')
        } else if name.eq_ignore_ascii_case("cntrl") {
            ch.is_control()
        } else if name.eq_ignore_ascii_case("digit") {
            ch.is_ascii_digit()
        } else if name.eq_ignore_ascii_case("graph") {
            !ch.is_whitespace() && !ch.is_control()
        } else if name.eq_ignore_ascii_case("lower") {
            ch.is_lowercase()
        } else if name.eq_ignore_ascii_case("print") {
            !ch.is_control()
        } else if name.eq_ignore_ascii_case("punct") {
            ch.is_ascii_punctuation()
        } else if name.eq_ignore_ascii_case("space") {
            ch.is_whitespace()
        } else if name.eq_ignore_ascii_case("upper") {
            ch.is_uppercase()
        } else if name.eq_ignore_ascii_case("xdigit") {
            ch.is_ascii_hexdigit()
        } else if name.eq_ignore_ascii_case("n") || name.eq_ignore_ascii_case("number") {
            is_number
        } else if name.eq_ignore_ascii_case("m") || name.eq_ignore_ascii_case("mark") {
            is_mark
        } else if name.eq_ignore_ascii_case("p") || name.eq_ignore_ascii_case("punctuation") {
            is_punctuation
        } else if name.eq_ignore_ascii_case("s") || name.eq_ignore_ascii_case("symbol") {
            is_symbol
        } else if name.eq_ignore_ascii_case(category.abbreviation()) {
            true
        } else if name.eq_ignore_ascii_case("decimal_number") {
            category == Gc::DecimalNumber
        } else if name.eq_ignore_ascii_case("z") || name.eq_ignore_ascii_case("separator") {
            ch.is_whitespace()
        } else if name.eq_ignore_ascii_case("word") {
            is_word_char(ch)
        } else if let Some(start) = xid_property(name) {
            if start {
                unicode_ident::is_xid_start(ch)
            } else {
                unicode_ident::is_xid_continue(ch)
            }
        } else {
            ch.script().full_name().eq_ignore_ascii_case(name)
                || ch.script().short_name().eq_ignore_ascii_case(name)
        }
    }

    #[test]
    fn unicode_property_resolution_matches_the_reference_evaluator() {
        use unicode_script::UnicodeScript;

        let mut names = vec![
            "l",
            "L",
            "letter",
            "Letter",
            "alphabetic",
            "alnum",
            "alpha",
            "ascii",
            "blank",
            "cntrl",
            "digit",
            "graph",
            "lower",
            "print",
            "punct",
            "space",
            "upper",
            "xdigit",
            "n",
            "number",
            "m",
            "mark",
            "p",
            "punctuation",
            "s",
            "symbol",
            "decimal_number",
            "z",
            "separator",
            "word",
            "XID_Start",
            "xidc",
            "Xid-Continue",
            "Latin",
            "latn",
            "Greek",
            "Han",
            "Hiragana",
            "Cyrillic",
            "Common",
            "Yi",
            "unknown_property",
        ]
        .into_iter()
        .map(str::to_owned)
        .collect::<Vec<_>>();
        for category in GENERAL_CATEGORIES {
            names.push(category.abbreviation().to_owned());
            names.push(category.abbreviation().to_ascii_lowercase());
            names.push(category.abbreviation().to_ascii_uppercase());
        }
        // Every scalar below U+3000 and a stride of the rest cover each
        // property's ASCII, Latin, and astral behavior.
        let scalars = (0..=0x10ffffu32)
            .filter(|scalar| *scalar < 0x3000 || scalar % 13 == 0)
            .filter_map(char::from_u32);
        for ch in scalars {
            for name in &names {
                assert_eq!(
                    unicode_class_contains(name, ch),
                    unicode_class_contains_reference(name, ch),
                    "{name} {ch:?}"
                );
            }
        }
        // No script name collides with a category abbreviation, so resolving
        // abbreviations before script names is exact.
        for ch in (0..=0x10ffffu32).filter_map(char::from_u32) {
            let script = ch.script();
            for category in GENERAL_CATEGORIES {
                assert!(
                    !script
                        .full_name()
                        .eq_ignore_ascii_case(category.abbreviation())
                );
                assert!(
                    !script
                        .short_name()
                        .eq_ignore_ascii_case(category.abbreviation())
                );
            }
        }
    }

    #[test]
    fn selection_rejected_by_prefilter_does_not_compile_bytecode() {
        let matcher = FallbackMatcher::new(r"(?=\w)(?:alpha|beta)+ *keyword");
        let mut scratch = BytecodeScratch::default();
        let report = matcher
            .try_find_at_without_captures_with_scratch("alpha beta", 0, ctx(), &mut scratch)
            .unwrap();
        assert_eq!(report.result, None);
        assert!(matcher.bytecode.get().is_none());

        let report = matcher
            .try_find_at_without_captures_with_scratch("alpha keyword", 0, ctx(), &mut scratch)
            .unwrap();
        let result = report.result.expect("selection match");
        assert_eq!(result.start..result.end, 0..13);
        assert!(matcher.bytecode.get().is_some());
    }

    #[test]
    fn unicode_case_folded_tries_keep_non_transitive_case_pairs() {
        // `ϑ` and `ϴ` are both case-equal to `θ` but not to each other.
        // Expectations checked against vscode-oniguruma.
        for (pattern, line, span) in [
            (r"(?i)(?:(?:ϴ|θ)y|éz|eq|e)(?!x)", "ϑy!", 0..3),
            (r"(?i)(?:ϴx|θy|éz|eq)", "ϑy", 0..3),
            (r"(?i)(?:éz|θy|eq)", "ΘY", 0..3),
        ] {
            let matcher = FallbackMatcher::new(pattern);
            let mut scratch = BytecodeScratch::default();
            let found = matcher
                .try_find_at_without_captures_with_scratch(line, 0, ctx(), &mut scratch)
                .unwrap()
                .result
                .map(|result| result.start..result.end);
            assert_eq!(found, Some(span), "{pattern} on {line:?}");
        }
    }

    #[test]
    fn backreference_and_subroutine_selection_use_capture_layout_bytecode() {
        for (pattern, line, span) in [
            (r"(?=\w)(\w)x\1", "zaxa", 1..4),
            (r"(?=\w)(a|b)\g<1>c", "zabc", 1..4),
            (r"(?=\w)(a)?(?(1)b|c)", "zc", 1..2),
        ] {
            let matcher = FallbackMatcher::new(pattern);
            let mut scratch = BytecodeScratch::default();
            let found = (0..=line.len()).find_map(|start| {
                matcher
                    .try_find_at_without_captures_with_scratch(line, start, ctx(), &mut scratch)
                    .unwrap()
                    .result
            });
            let found = found.unwrap_or_else(|| panic!("{pattern} should match {line:?}"));
            assert_eq!(found.start..found.end, span, "{pattern}");
            if matcher.parsed.analysis().bytecode_beneficial() {
                assert!(
                    matcher.bytecode.get().is_some_and(Option::is_some),
                    "{pattern}"
                );
            }
        }
    }

    #[test]
    fn matches_literals_and_captures() {
        let matcher = FallbackMatcher::new(r"(foo)\1");
        let report = matcher.try_find("xxfoofoo", 0, ctx()).unwrap();
        let result = report.result.as_ref().unwrap();
        assert_eq!(result.start..result.end, 2..8);
        assert_eq!(result.captures[1], Some(2..5));
    }

    #[test]
    fn line_end_matches_before_trailing_newline() {
        let matcher = FallbackMatcher::new(r"foo$");
        let report = matcher.try_find("foo\n", 0, ctx()).unwrap();
        let result = report.result.as_ref().unwrap();
        assert_eq!(result.start..result.end, 0..3);
    }

    #[test]
    fn newline_sequence_escape_handles_crlf_and_unicode_newlines() {
        for line in ["\r\n", "\u{0085}", "\u{2028}", "\u{2029}"] {
            let matcher = FallbackMatcher::new(r"^\R$");
            let result = matcher.find(line, 0, ctx()).unwrap();
            assert_eq!(result.start..result.end, 0..line.len(), "{line:?}");
        }
    }

    #[test]
    fn nullable_start_filter_does_not_skip_a_later_line_end() {
        let matcher = FallbackMatcher::new(r#"($|(?="""))"#);
        let result = matcher.find("# comment\n", 1, ctx()).unwrap();
        assert_eq!(result.start..result.end, 9..9);
    }

    #[test]
    fn nullable_start_filter_does_not_skip_a_later_lookbehind() {
        let matcher = FallbackMatcher::new(r"x|(?<=T)");
        let result = matcher.find("= Ty", 0, ctx()).unwrap();
        assert_eq!(result.start..result.end, 3..3);
        let matcher = FallbackMatcher::new(r"(?<=\S)(?<![=])|(?=\n)");
        let result = matcher.find("= Typst\n", 0, ctx()).unwrap();
        assert_eq!(result.start..result.end, 3..3);
    }

    #[test]
    fn anchor_alternation_only_starts_at_its_anchors() {
        let matcher = FallbackMatcher::new(r"(^|\G)(?!y)");
        assert_eq!(
            matcher.start_hint,
            StartHint::Anchored(StartAnchors {
                line_start: true,
                continuation: true,
                ..StartAnchors::default()
            })
        );
        let at_g = AnchorContext {
            allow_a: false,
            allow_g: true,
            g_pos: 2,
        };
        // Nullable, so every column used to be tried; only `^` and `\G` can hold.
        let result = matcher.find("abcy", 0, at_g).unwrap();
        assert_eq!(result.start..result.end, 0..0);
        let result = matcher.find("abcy", 1, at_g).unwrap();
        assert_eq!(result.start..result.end, 2..2);
        assert!(matcher.find("abyc", 1, at_g).is_none());

        // `\G` at column 0 is the same start as `^`, tried once.
        let matcher = FallbackMatcher::new(r"(^|\G)x");
        let at_zero = AnchorContext { g_pos: 0, ..at_g };
        assert_eq!(matcher.find("xx", 0, at_zero).unwrap().start, 0);
        assert!(matcher.find("xx", 1, at_zero).is_none());

        // One unanchored branch keeps the per-column scan.
        let matcher = FallbackMatcher::new(r"(^|a)b");
        assert_eq!(matcher.start_hint, StartHint::Unanchored);
        assert_eq!(matcher.find("xab", 0, ctx()).unwrap().start, 1);
    }

    #[test]
    fn supports_named_backrefs() {
        let matcher = FallbackMatcher::new(r"(?<x>a)\k<x>");
        let result = matcher.find("zaa", 0, ctx()).unwrap();
        assert_eq!(result.start..result.end, 1..3);
    }

    #[test]
    fn supports_recursive_oniguruma_subroutine_calls() {
        let matcher = FallbackMatcher::new(r"(?<parens>\((?:[^()]|\g<parens>)*\))");
        let result = matcher.find("x((a)(b))y", 0, ctx()).unwrap();
        assert_eq!(result.start..result.end, 1..9);
    }

    #[test]
    fn folded_ascii_classes_admit_kelvin_and_long_s_on_every_path() {
        // Expectations checked against vscode-oniguruma.
        for (pattern, line, span) in [
            (r"(?i)(?:[[:ascii:]]x|yz)", "\u{212a}x", 0..4),
            (r"(?i:[[:ascii:]])*(?-i:\x{212a})|zz", "\u{212a}", 0..3),
            (r"(?i)(?:[[[:ascii:]]]x|yz)", "\u{17f}x", 0..3),
        ] {
            let matcher = FallbackMatcher::new(pattern);
            let mut scratch = BytecodeScratch::default();
            let selected = matcher
                .try_find_at_without_captures_with_scratch(line, 0, ctx(), &mut scratch)
                .unwrap()
                .result
                .map(|result| result.start..result.end);
            assert_eq!(selected, Some(span.clone()), "{pattern} on {line:?}");
            let found = matcher
                .find(line, 0, ctx())
                .map(|result| result.start..result.end);
            assert_eq!(found, Some(span), "{pattern} on {line:?}");
        }
    }

    #[test]
    fn unbounded_zero_width_recursion_fails_without_overflowing() {
        for pattern in [r"(\g<1>)?", r"(\g<1>+)?", r"(\g<1>++)", r"(?<n>a|\g<n>)"] {
            let matcher = FallbackMatcher::new(pattern);
            let _ = matcher.try_find_at("a", 0, ctx());
        }
        let nested = FallbackMatcher::new(r"(?<n>\((?:[^()]|\g<n>)*\))");
        let line = format!("{}{}", "(".repeat(100), ")".repeat(100));
        let found = nested
            .find(&line, 0, ctx())
            .map(|result| result.start..result.end);
        assert_eq!(found, Some(0..line.len()));
    }

    #[test]
    fn plus_after_an_interval_repeats_it() {
        // Expectations checked against vscode-oniguruma.
        for (pattern, line, expected) in [
            (r"^a{1,2}+a$", "aa", true),
            (r"^a{2}+$", "aaaa", true),
            (r"^a{2}+$", "aaa", false),
            (r"^a{1,}+a$", "aa", true),
            (r"^a{,2}+a$", "aa", true),
            (r"^a++a$", "aa", false),
        ] {
            let found = FallbackMatcher::new(pattern).find(line, 0, ctx()).is_some();
            assert_eq!(found, expected, "{pattern} on {line:?}");
        }
    }

    #[test]
    fn duplicate_names_in_backrefs_and_conditionals_follow_oniguruma() {
        // Expectations checked against vscode-oniguruma.
        for (pattern, line, expected) in [
            (r"(?<x>a)(?<x>b)\k<x>", "abab", Some(0..3)),
            (r"(?<x>a)(?<x>ab)\k<x>", "aababx", Some(0..5)),
            (r"(?<x>a)(?<x>ab)\k<x>b", "aabab", None),
            (r"(?<x>ab)(?<x>a)\k<x>b", "abaab", Some(0..5)),
            (r"(?:(?<x>a)|(?<x>b))\k<x>", "bb", Some(0..2)),
            (r"(?:(?<x>a)|(?<x>b))\k<x>", "ab", None),
            (r"(?:(?<n>a)|(?<n>b))(?(<n>)x|y)", "ax", Some(0..2)),
            (r"(?:(?<n>a)|(?<n>b))(?(<n>)x|y)", "bx", Some(0..2)),
            (r"(?:(?<n>a)|(?<n>b))(?(<n>)x|y)", "ay", None),
            (r"(?<a>x)(?<a>y)?(?(<a>)z|w)", "xw", None),
        ] {
            let matcher = FallbackMatcher::new(pattern);
            let found = matcher
                .find(line, 0, ctx())
                .map(|result| result.start..result.end);
            assert_eq!(found, expected, "{pattern} on {line:?}");
        }
    }

    #[test]
    fn supports_oniguruma_print_property() {
        let matcher = FallbackMatcher::new(r"^\p{print}+$");
        assert!(matcher.find("café λ🚀", 0, ctx()).is_some());
        assert!(matcher.find("bad\0", 0, ctx()).is_none());
    }

    #[test]
    fn supports_oniguruma_xid_properties_with_loose_names() {
        let label = FallbackMatcher::new(r"^<[_\p{XIDS}][-.:_\p{XIDC}]*>$");
        assert!(label.find("<intro-2.東京>", 0, ctx()).is_some());
        assert!(label.find("<2intro>", 0, ctx()).is_none());
        let loose = FallbackMatcher::new(r"^\p{xid start}\p{Xid-Continue}+$");
        assert!(loose.find("a1_λ", 0, ctx()).is_some());
        assert!(loose.find("1a", 0, ctx()).is_none());
    }

    #[test]
    fn supports_oniguruma_alphabetic_property_inside_classes() {
        let matcher = FallbackMatcher::new(r"^[.:_\p{Alphabetic}\p{N}]+$");
        assert!(matcher.find("alpha:λ_三7", 0, ctx()).is_some());
        assert!(matcher.find("not alphabetic!", 0, ctx()).is_none());
    }

    #[test]
    fn supports_oniguruma_nested_class_intersection_and_subtraction() {
        let operators = FallbackMatcher::new(r#"^[[\p{S}\p{P}]&&[^]"'(),;\[_`{}]]+$"#);
        for sample in ["+", "→", "🚀", "!", ".:"] {
            assert!(operators.find(sample, 0, ctx()).is_some(), "{sample:?}");
        }
        for sample in ["a", "7", " ", "]", "\"", "'", "(", "_", "`", "{"] {
            assert!(operators.find(sample, 0, ctx()).is_none(), "{sample:?}");
        }

        let rhs_union = FallbackMatcher::new(r"^[a-w&&[^c-g]z]+$");
        assert!(rhs_union.find("abhw", 0, ctx()).is_some());
        assert!(rhs_union.find("c", 0, ctx()).is_none());
        assert!(rhs_union.find("g", 0, ctx()).is_none());
        assert!(rhs_union.find("z", 0, ctx()).is_none());

        let chained = FallbackMatcher::new(r"^[a-z&&[^aeiou]&&[^x-z]]+$");
        assert!(chained.find("bcd", 0, ctx()).is_some());
        assert!(chained.find("a", 0, ctx()).is_none());
        assert!(chained.find("z", 0, ctx()).is_none());
    }

    #[test]
    fn supports_unicode_general_category_properties() {
        for (property, sample) in [
            ("Cc", "\u{1}"),
            ("Cf", "\u{200d}"),
            ("Ll", "a"),
            ("Lm", "ʰ"),
            ("Lo", "文"),
            ("Lt", "Dž"),
            ("Lu", "A"),
            ("Mc", "ा"),
            ("Me", "⃝"),
            ("Mn", "\u{301}"),
            ("Nl", "Ⅻ"),
            ("No", "½"),
            ("Pc", "_"),
            ("Sc", "$"),
            ("Sk", "^"),
            ("Sm", "+"),
            ("So", "🚀"),
        ] {
            let pattern = format!(r"^\p{{{property}}}+$");
            let matcher = FallbackMatcher::new(&pattern);
            assert!(matcher.find(sample, 0, ctx()).is_some(), "{property}");
        }
        for (property, sample) in [("M", "\u{301}"), ("P", "!"), ("S", "🚀")] {
            let pattern = format!(r"^\p{{{property}}}+$");
            let matcher = FallbackMatcher::new(&pattern);
            assert!(matcher.find(sample, 0, ctx()).is_some(), "{property}");
        }
        let greek = FallbackMatcher::new(r"^\p{Greek}+$");
        assert!(greek.find("αΩ", 0, ctx()).is_some());
        assert!(greek.find("Latin", 0, ctx()).is_none());
    }

    #[test]
    fn scoped_case_insensitive_flags_do_not_get_case_sensitive_start_bytes() {
        let matcher = FallbackMatcher::new(r"(?i:DOCTYPE)");
        assert_eq!(matcher.find("doctype", 0, ctx()).unwrap().start, 0);
    }

    #[test]
    fn case_insensitive_literals_fold_non_ascii_scalars() {
        for (pattern, sample) in [
            (r"(?i)Выбрать|Истина|НРег", "ВЫБРАТЬ"),
            (r"(?i)Выбрать|Истина|НРег", "истина"),
            (r"(?i)Выбрать|Истина|НРег", "нрег"),
            (r"(?i)kelvin", "KELVIN"),
            (r"(?i)ſtone", "STONE"),
            (r"(?i)ask", "aſK"),
            (r"(?i)skate", "sKATE"),
            (r"(?i)ẞ", "ß"),
        ] {
            let matcher = FallbackMatcher::new(pattern);
            let matched = matcher.find(sample, 0, ctx()).expect(sample);
            assert_eq!(matched.start..matched.end, 0..sample.len());
        }
    }

    #[test]
    fn unicode_case_comparator_keeps_ascii_and_mixed_folds_exact() {
        for left in '\0'..='\u{7f}' {
            for right in '\0'..='\u{7f}' {
                assert_eq!(
                    unicode_case_eq(left, right),
                    left.eq_ignore_ascii_case(&right),
                    "{left:?} vs {right:?}"
                );
            }
        }
        assert!(unicode_case_eq('K', 'K'));
        assert!(unicode_case_eq('s', 'ſ'));
        assert!(unicode_case_eq('ß', 'ẞ'));
        assert!(!unicode_case_eq('i', 'İ'));
        assert!(!unicode_case_eq('i', 'ı'));
    }

    /// Scalars that exercise ASCII, Latin-1, Cyrillic, Greek final sigma,
    /// multi-scalar mappings, dotless/dotted i, Kelvin/long s folds, and
    /// mismatched Unicode table versions.
    fn case_probe_scalars() -> Vec<char> {
        let mut scalars: Vec<char> = ('\0'..='\u{24f}')
            .chain('\u{370}'..='\u{3ff}')
            .chain('\u{400}'..='\u{52f}')
            .chain('\u{1e00}'..='\u{1fff}')
            .chain('\u{2100}'..='\u{218f}')
            .chain('\u{24b6}'..='\u{24e9}')
            .chain('\u{a640}'..='\u{a7ff}')
            .chain('\u{ff21}'..='\u{ff5a}')
            .chain(['\u{10400}', '\u{10428}', '\u{1e900}', '\u{1e922}'])
            .collect();
        scalars.sort_unstable();
        scalars.dedup();
        scalars
    }

    #[test]
    fn case_fold_keys_agree_with_unicode_case_comparator() {
        let scalars = case_probe_scalars();
        let keys: Vec<CaseFoldKey> = scalars.iter().copied().map(CaseFoldKey::new).collect();
        for (left, left_key) in scalars.iter().zip(&keys) {
            for (right, right_key) in scalars.iter().zip(&keys) {
                assert_eq!(
                    left_key.case_eq(right_key),
                    unicode_case_eq(*left, *right),
                    "{left:?} vs {right:?}"
                );
            }
        }
    }

    #[test]
    fn case_insensitive_classes_fold_their_literal_set_once() {
        // Expectations checked against vscode-oniguruma.
        for (pattern, line, expected) in [
            (r"(?i)[a-{]", "A", true),
            (r"(?i)[a-{]", "\\", false),
            (r"(?i)[a-{]", "`", false),
            (r"(?i)[Z-a]", "_", true),
            (r"(?i)[Z-a]", "b", false),
            (r"(?i)[@-C]", "c", true),
            (r"(?i)[a-z]", "\u{212a}", true),
            (r"(?i)[\x{2100}-\x{2200}]", "k", true),
            (r"(?i)[σ-σ]", "ς", true),
            (r"(?i)[h-j]", "\u{131}", false),
            (r"(?i)[A-Z&&a-z]", "a", false),
            (r"(?i)[^A-Z&&a-z]", "a", true),
            (r"(?i)[\x{2120}-\x{2130}&&k]", "K", false),
            (r"(?i)[^[^a]]", "A", false),
            (r"(?i)[\w&&[^a]]", "A", true),
            (r"(?i)[^a-z]", "K", false),
            (r"(?i)[^k]", "\u{212a}", false),
            (r"(?i)[\p{Lu}]", "a", true),
            (r"(?i)[^\p{Lu}]", "a", false),
            (r"(?i)[[:upper:]]", "a", true),
            (r"(?i)[^[:upper:]]", "a", false),
            // Escapes outside brackets are not folded.
            (r"(?i)\p{Lu}", "a", false),
            (r"(?i)\P{Lu}", "A", false),
        ] {
            let found = FallbackMatcher::new(pattern).find(line, 0, ctx()).is_some();
            assert_eq!(found, expected, "{pattern} on {line:?}");
        }
    }

    #[test]
    fn case_insensitive_ascii_ranges_accept_unicode_simple_folds() {
        let matcher = FallbackMatcher::new(r"(?i)^[A-Z]+$");
        for sample in ["ſ", "K"] {
            assert!(matcher.find(sample, 0, ctx()).is_some(), "{sample:?}");
        }
    }

    #[test]
    fn alphabetic_property_includes_derived_alphabetic_marks() {
        let matcher = FallbackMatcher::new(r"^\p{Alphabetic}+$");
        for sample in ["\u{0345}", "\u{05b0}"] {
            assert!(matcher.find(sample, 0, ctx()).is_some(), "{sample:?}");
        }
        let letters = FallbackMatcher::new(r"^\p{L}+$");
        assert!(letters.find("\u{0345}", 0, ctx()).is_none());
    }

    #[test]
    fn supports_lookahead() {
        let matcher = FallbackMatcher::new(r"foo(?=bar)");
        let result = matcher.find("xxfoobar", 0, ctx()).unwrap();
        assert_eq!(result.start..result.end, 2..5);
    }

    #[test]
    fn positive_lookahead_preserves_captures() {
        let matcher = FallbackMatcher::new(r"(^|\G)(\s*)(`{3,}|~{3,})\s*(?=([^`]*)?$)");
        let result = matcher.find("```text\n", 0, ctx()).unwrap();
        assert_eq!(result.start..result.end, 0..3);
        assert_eq!(result.captures[4], Some(3..8));
    }

    #[test]
    fn supports_lookbehind() {
        let matcher = FallbackMatcher::new(r"(?<=foo)bar");
        let result = matcher.find("xxfoobar", 0, ctx()).unwrap();
        assert_eq!(result.start..result.end, 5..8);
    }

    #[test]
    fn positive_lookbehind_preserves_captures_and_scoped_flags() {
        let captured = FallbackMatcher::new(r"(?<=(a))b")
            .find("ab", 0, ctx())
            .unwrap();
        assert_eq!(captured.start..captured.end, 1..2);
        assert_eq!(captured.captures[1], Some(0..1));

        let variable = FallbackMatcher::new(r"(?<=(a|aa))b")
            .find("aab", 0, ctx())
            .unwrap();
        assert_eq!(variable.start..variable.end, 2..3);
        assert_eq!(variable.captures[1], Some(1..2));

        let backref = FallbackMatcher::new(r"(?<=(a))\1")
            .find("aa", 0, ctx())
            .unwrap();
        assert_eq!(backref.start..backref.end, 1..2);
        assert_eq!(backref.captures[1], Some(0..1));

        let scoped = FallbackMatcher::new(r"(?<=(?i:foo))bar")
            .find("FOObar", 0, ctx())
            .unwrap();
        assert_eq!(scoped.start..scoped.end, 3..6);
    }

    #[test]
    fn folded_lookbehind_uses_input_byte_widths() {
        for (pattern, line, start) in [
            (r"(?<=(?i:k))x", "Kx", 3),
            (r"(?<=(?i:K))x", "kx", 1),
            (r"(?i)(?<=s)x", "ſx", 2),
            (r"(?i)(?<=ſ)x", "sx", 1),
            (r"(?<=(?i:(k|s)))x", "🛰Kx", 7),
            (r"(?<=(?i:k){2})x", "kKx", 4),
        ] {
            let parsed = parse(pattern);
            let result = FallbackMatcher::new(pattern).find(line, 0, ctx()).unwrap();
            assert_eq!(result.start..result.end, start..line.len(), "{pattern}");
            assert_eq!(
                recursive_position_span(&parsed, line, start, ctx()),
                Some(start..line.len()),
                "{pattern}"
            );
        }
        for (pattern, line) in [(r"(?<!(?i:k))x", "Kx"), (r"(?i)(?<!s)x", "ſx")] {
            assert!(FallbackMatcher::new(pattern).find(line, 0, ctx()).is_none());
        }
    }

    #[test]
    fn exact_lookbehind_honors_case_insensitive_flag() {
        let matcher = FallbackMatcher::new(r"(?i)(?<=foo)bar");
        let result = matcher.find("xxFOObar", 0, ctx()).unwrap();

        assert_eq!(result.start..result.end, 5..8);
    }

    #[test]
    fn extended_mode_ignores_unescaped_whitespace_and_comments() {
        let spaced = FallbackMatcher::new("(?x:a b)")
            .find("ab", 0, ctx())
            .unwrap();
        assert_eq!(spaced.start..spaced.end, 0..2);

        let commented = FallbackMatcher::new("(?x:a # comment\n b)")
            .find("ab", 0, ctx())
            .unwrap();
        assert_eq!(commented.start..commented.end, 0..2);

        let escaped = FallbackMatcher::new(r"(?x:a\ b)")
            .find("a b", 0, ctx())
            .unwrap();
        assert_eq!(escaped.start..escaped.end, 0..3);
    }

    #[test]
    fn bounded_lookbehind_searches_only_width_window() {
        let matcher = FallbackMatcher::new(r"(?<=[A-Z]|return|case)foo");
        let report = matcher
            .try_find("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa returnfoo", 0, ctx())
            .unwrap();
        let result = report.result.as_ref().unwrap();

        assert_eq!(result.start..result.end, 39..42);
        assert!(report.steps < 80, "{report:#?}");
    }

    #[test]
    fn bounded_lookbehind_handles_multibyte_character_width() {
        let matcher = FallbackMatcher::new(r"(?<=.)bar");
        let result = matcher.find("ébar", 0, ctx()).unwrap();

        assert_eq!(result.start..result.end, 2..5);
    }

    #[test]
    fn bounded_negative_lookbehind_succeeds_when_prefix_is_too_short() {
        let matcher = FallbackMatcher::new(r"(?<!foo)bar");
        let result = matcher.find("bar", 0, ctx()).unwrap();

        assert_eq!(result.start..result.end, 0..3);
    }

    #[test]
    fn simple_repeat_fast_path_preserves_greedy_order() {
        let matcher = FallbackMatcher::new(r"a*ab");
        let result = matcher.find("aaab", 0, ctx()).unwrap();

        assert_eq!(result.start..result.end, 0..4);
    }

    #[test]
    fn possessive_simple_repeat_does_not_backtrack() {
        let matcher = FallbackMatcher::new(r"a*+ab");
        let report = matcher.try_find("aaab", 0, ctx()).unwrap();

        assert_eq!(report.result, None);
    }

    #[test]
    fn atomic_and_compound_possessive_repeats_commit_ordered_paths() {
        assert!(
            FallbackMatcher::new(r"(?>a|ab)c")
                .try_find("abc", 0, ctx())
                .unwrap()
                .result
                .is_none()
        );
        let committed = FallbackMatcher::new(r"(?>ab|a)c")
            .find("abc", 0, ctx())
            .unwrap();
        assert_eq!(committed.start..committed.end, 0..3);
        assert!(
            FallbackMatcher::new(r"(a|ab)++c")
                .try_find("abc", 0, ctx())
                .unwrap()
                .result
                .is_none()
        );
        let control = FallbackMatcher::new(r"(a|ab)+c")
            .find("abc", 0, ctx())
            .unwrap();
        assert_eq!(control.start..control.end, 0..3);

        let exact = FallbackMatcher::new(r"(a|ab){1}+c")
            .find("abc", 0, ctx())
            .unwrap();
        assert_eq!(exact.start..exact.end, 0..3);
        assert_eq!(exact.captures[1], Some(0..2));

        let zero_width = FallbackMatcher::new(r"(a?){2}+a")
            .find("a", 0, ctx())
            .unwrap();
        assert_eq!(zero_width.start..zero_width.end, 0..1);
        assert_eq!(zero_width.captures[1], Some(0..0));
    }

    #[test]
    fn c_family_space_comment_separator_fast_path_matches_shape() {
        let parsed = parse(
            r"((?:\s*+(/\*)((?:[^*]++|\*+(?!/))*+(\*/))\s*+)+|\s++|(?<=\W)|(?=\W)|^|\n?$|\A|\Z)",
        );
        let Ast::Group { child, .. } = &parsed.ast else {
            panic!("unexpected ast: {:#?}", parsed.ast);
        };
        let Ast::Alternation(branches) = child.as_ref() else {
            panic!("unexpected child: {child:#?}");
        };
        assert!(is_cpp_space_comment_separator(branches));
        let positions =
            match_cpp_space_comment_separator_positions(branches, "  /* ok */  value", 0, ctx())
                .expect("fast path applies")
                .into_iter()
                .collect::<Vec<_>>();
        assert_eq!(positions.first().copied(), Some("  /* ok */  ".len()));
    }

    #[test]
    fn h_class_matches_hex_digits() {
        let matcher = FallbackMatcher::new(r"\h+");
        let result = matcher.find("xx c0ffee", 0, ctx()).unwrap();
        assert_eq!(result.start..result.end, 3..9);

        let matcher = FallbackMatcher::new(r"\H+");
        let result = matcher.find("c0ffee tail", 0, ctx()).unwrap();
        assert_eq!(result.start..result.end, 6..8);
    }

    #[test]
    fn g_anchor_uses_context() {
        let matcher = FallbackMatcher::new(r"\Gfoo");
        let result = matcher
            .find(
                "xxfoo",
                0,
                AnchorContext {
                    allow_a: false,
                    allow_g: true,
                    g_pos: 2,
                },
            )
            .unwrap();
        assert_eq!(result.start..result.end, 2..5);
    }

    #[test]
    fn budget_kills_pathological_pattern() {
        let matcher = FallbackMatcher::with_budget(r"(a+)+b", 10);
        let error = matcher.try_find("aaaaaaaaaaaa", 0, ctx()).unwrap_err();
        assert!(matches!(error, FallbackError::BudgetExceeded { .. }));
    }

    #[test]
    fn prefilter_skips_fallback_without_vm_steps() {
        let matcher = FallbackMatcher::new(r"foo(?=bar)");
        let report = matcher.try_find("no match here", 0, ctx()).unwrap();

        assert_eq!(report.result, None);
        assert_eq!(report.steps, 0);
        assert_eq!(matcher.prefilter_may_match("no match here", 0), Some(false));
    }

    #[test]
    fn start_byte_hint_skips_to_positive_lookahead_candidates() {
        let matcher = FallbackMatcher::new(r"(?=[;)])(?<!\\)");
        let report = matcher.try_find("aaaaaaaaaaaaaaaa;", 0, ctx()).unwrap();
        let result = report.result.as_ref().unwrap();

        assert_eq!(result.start..result.end, 16..16);
        assert!(report.steps < 12, "{report:#?}");
        assert_eq!(matcher.restricted_start_bytes(), Some(vec![b')', b';']));
    }

    #[test]
    fn start_byte_hint_handles_nullable_prefix_before_literal() {
        let matcher = FallbackMatcher::new(r"(?=[\t ]*#)(?<!\\)");
        let report = matcher.try_find("abc   # comment", 0, ctx()).unwrap();
        let result = report.result.as_ref().unwrap();

        assert_eq!(result.start..result.end, 3..3);
        assert!(report.steps < 32, "{report:#?}");
    }

    #[test]
    fn nix_function_lookahead_specialization_matches_capture_shape() {
        let matcher = FallbackMatcher::new(
            r##"(?=(\b[A-Z_a-z][-'0-9A-Z_a-z]*\s*[:@]|\{[^"'}]*}\s*:|\{[^"#'/=}]*[,?]))"##,
        );
        let result = matcher
            .find("{ pkgs ? import <nixpkgs> {} }:", 0, ctx())
            .unwrap();
        assert_eq!(result.start..result.end, 0..0);
        assert_eq!(result.captures, vec![Some(0..0), Some(0..8)]);

        let result = matcher.find("name @ value", 0, ctx()).unwrap();
        assert_eq!(result.start..result.end, 0..0);
        assert_eq!(result.captures, vec![Some(0..0), Some(0..6)]);
    }

    #[test]
    fn nix_expression_end_lookahead_specialization_matches_capture_shape() {
        let matcher = FallbackMatcher::new(r#"(?=([]),;}]|\b(else|then)\b))"#);
        let result = matcher.find(", next", 0, ctx()).unwrap();
        assert_eq!(result.captures, vec![Some(0..0), Some(0..1), None]);

        let result = matcher.find("then value", 0, ctx()).unwrap();
        assert_eq!(result.captures, vec![Some(0..0), Some(0..4), Some(0..4)]);
    }

    #[test]
    fn case_insensitive_start_hints_include_unicode_lead_bytes() {
        let matcher = FallbackMatcher::new(r"(?i)foo");
        let result = matcher.find("xxFOO", 0, ctx()).unwrap();
        assert_eq!(result.start..result.end, 2..5);
        let bytes = matcher.restricted_start_bytes().unwrap();
        assert!(bytes.contains(&b'F'));
        assert!(bytes.contains(&b'f'));
        assert!((0xc2..=0xf4).all(|byte| bytes.contains(&byte)));
    }

    #[test]
    fn unicode_capable_classes_do_not_receive_ascii_only_start_hints() {
        for pattern in [r"\w+", r"\s+", r"[[:alpha:]]+", r"[[:word:]]+"] {
            let line = if pattern == r"\s+" { "\u{2003}" } else { "λ" };
            let matcher = FallbackMatcher::new(pattern);
            let result = matcher.find(line, 0, ctx()).unwrap();
            assert_eq!(result.start..result.end, 0..line.len(), "{pattern}");
            assert!(matcher.restricted_start_bytes().is_none(), "{pattern}");
        }
    }

    #[test]
    fn anchored_fallback_searches_only_anchor_position() {
        let matcher = FallbackMatcher::new(r"^foo(?=bar)");
        let report = matcher.try_find("xfoobar", 0, ctx()).unwrap();

        assert_eq!(report.result, None);
        assert!(report.steps < 10, "{report:#?}");
    }

    #[test]
    fn returns_utf8_boundary_offsets() {
        let matcher = FallbackMatcher::new("é+");
        let result = matcher.find("xéé", 0, ctx()).unwrap();
        assert_eq!(result.start, 1);
        assert_eq!(result.end, 5);
        assert!("xéé".is_char_boundary(result.start));
        assert!("xéé".is_char_boundary(result.end));
    }

    #[test]
    fn nullable_pattern_matches_empty_without_start_byte() {
        let matcher = FallbackMatcher::new(r"a?");
        let result = matcher.find("xxx", 0, ctx()).unwrap();
        assert_eq!(result.start..result.end, 0..0);
    }

    #[test]
    fn finite_zero_width_repeats_satisfy_their_minimum() {
        let matcher = FallbackMatcher::new(r"(?:){2}a");
        let result = matcher.find("a", 0, ctx()).unwrap();
        assert_eq!(result.start..result.end, 0..1);
    }

    #[test]
    fn exact_start_replay_preserves_captures() {
        let matcher = FallbackMatcher::new(r"(foo)");
        let report = matcher.try_find_at("xxfoo", 2, ctx()).unwrap();
        let result = report.result.unwrap();

        assert_eq!(result.start..result.end, 2..5);
        assert_eq!(result.captures, vec![Some(2..5), Some(2..5)]);
        assert_eq!(matcher.try_find_at("xxfoo", 1, ctx()).unwrap().result, None);
    }

    #[test]
    fn position_only_selection_matches_capture_vm_spans() {
        for (pattern, line) in [
            (r"(a|aa)*a", "xxaaaa"),
            (r"(ab|a)+?b", "xxaaab"),
            (r"(([A-Z])|[a-z])+[0-9]", "__Abz7"),
            (r"(?:a?)*b", "xxaaab"),
            (r"(?i:(ab|c))+D", "__ABcD"),
            (r"(é|λ)+z", "xéλz"),
            (r"(?=(a|aa)+b)a+b", "xxaaab"),
            (r"(?!foo)([a-z])+[0-9]", "foo bar7"),
            (r"(?<=(a|aa))b", "xxaab"),
            (r"(?<!foo)([a-z])+[0-9]", "foo bar7"),
            (r"(?<par>\((?:[^()]|\g<par>)*\))", "x((a)(b))"),
        ] {
            let matcher = FallbackMatcher::new(pattern);
            let full = matcher.try_find(line, 0, ctx()).unwrap().result;
            let selected = matcher
                .try_find_for_selection(line, 0, ctx())
                .unwrap()
                .result;
            assert_eq!(
                selected.as_ref().map(|result| result.start..result.end),
                full.as_ref().map(|result| result.start..result.end),
                "pattern {pattern:?}"
            );
            assert!(selected.is_none_or(|result| result.captures.is_empty()));
        }
    }
}