regexr 0.3.1

//! Unified executor for compiled regex patterns.
//!
//! The executor uses a prefilter (when available) to quickly skip to candidate
//! positions before engaging the full regex engine.

use std::sync::RwLock;

use crate::dfa::{EagerDfa, LazyDfa};
use crate::error::Result;
use crate::hir::Hir;
use crate::literal::{extract_literals, Prefilter};
use crate::nfa::tagged::TaggedNfaEngine;
use crate::nfa::{self, Nfa};
use crate::vm::backtracking::{BudgetExhausted, CaptureSlots};
use crate::vm::{
    BacktrackingVm, CodepointClassMatcher, OnePass, PikeVm, PikeVmContext, ShiftOr, ShiftOrWide,
};

#[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
use crate::jit;

use super::{needs_boundary_aware_empty_match, select_engine, select_engine_from_hir, EngineType};

/// Returns true if the byte is a word character (alphanumeric or underscore).
#[inline]
fn is_word_byte(b: u8) -> bool {
    b.is_ascii_alphanumeric() || b == b'_'
}

/// A compiled regex ready for execution.
pub struct CompiledRegex {
    inner: CompiledInner,
    prefilter: Prefilter,
    /// Fallback NFA for captures when using Shift-Or or LazyDfa.
    /// Lazily compiled on first captures() call.
    capture_nfa: RwLock<Option<Nfa>>,
    /// Deterministic capture engine, when the capture NFA is one-pass.
    /// Replaces the PikeVM second pass with a single linear scan.
    one_pass: Option<OnePass>,
    /// Cached PikeVM for capture extraction.
    /// Lazily initialized on first captures() call to avoid cloning NFA repeatedly.
    capture_vm: RwLock<Option<PikeVm>>,
    /// Cached execution context for PikeVM.
    /// Provides pre-allocated storage to avoid allocations on each captures() call.
    capture_ctx: RwLock<Option<PikeVmContext>>,
    /// BacktrackingVm for fast single-pass capture extraction.
    /// Used instead of PikeVM for patterns with captures (no lookaround).
    backtracking_vm: Option<BacktrackingVm>,
    /// BacktrackingJit for fast single-pass capture extraction in JIT mode.
    /// Used by JitShiftOr when pattern has captures.
    /// This is the JIT equivalent of backtracking_vm.
    #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
    backtracking_jit: Option<jit::BacktrackingJit>,
}

impl std::fmt::Debug for CompiledRegex {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("CompiledRegex")
            .field("engine", &self.engine_name())
            .field("prefilter", &self.prefilter)
            .finish_non_exhaustive()
    }
}

#[allow(clippy::large_enum_variant)]
enum CompiledInner {
    PikeVm(PikeVm),
    ShiftOr(ShiftOr),
    /// Wide Shift-Or for patterns with 65-256 positions.
    /// Uses [u64; 4] for 256-bit state vectors.
    ShiftOrWide(ShiftOrWide),
    LazyDfa(RwLock<LazyDfa>),
    /// Pre-materialized DFA for fast matching without JIT.
    /// Used for patterns that benefit from eager state computation.
    EagerDfa(EagerDfa),
    /// Fast codepoint-level matching for single character class patterns.
    CodepointClass(CodepointClassMatcher),
    /// Backtracking VM engine for patterns with backreferences.
    /// Uses PCRE-style backtracking (non-JIT version of BacktrackingJit).
    BacktrackingVm(BacktrackingVm),
    /// Tagged NFA interpreter for patterns with lookaround or non-greedy.
    /// Uses liveness analysis for efficient single-pass capture extraction.
    /// Always available (no JIT required).
    TaggedNfaInterp(TaggedNfaEngine),
    #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
    Jit(jit::CompiledRegex),
    /// Tagged NFA JIT engine for patterns with lookaround or non-greedy.
    /// Uses liveness analysis for efficient single-pass capture extraction.
    /// JIT compiles the NFA to native code for better performance.
    #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
    TaggedNfaJit(jit::TaggedNfaJit),
    /// Backtracking JIT engine for patterns with backreferences.
    /// Uses PCRE-style backtracking for fast backreference matching.
    #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
    Backtracking(jit::BacktrackingJit),
    /// JIT-compiled Shift-Or engine for word boundary patterns.
    #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
    JitShiftOr(jit::JitShiftOr),
}

/// Decides when prefilter-driven verification has stopped paying for itself.
///
/// Verifying one candidate at a time is a win when a failed attempt gives up
/// near the candidate. It is a trap when the pattern consumes a long run before
/// failing and the prefilter keeps most positions: `(?:a|a)+$` over `"aaaa…"`
/// makes every byte a candidate and every attempt scan to the end, so the search
/// costs one engine pass per byte.
///
/// Every engine has a complete linear-time search of its own
/// ([`CompiledRegex::find_engine_from`]), so the escape is to stop verifying and
/// hand the rest of the input to it. This tracks how many attempts have failed
/// and how much input they span: past [`MAX_ATTEMPTS`], a prefilter still
/// keeping more than one position in [`MIN_SELECTIVITY`] is not filtering, and
/// the handoff is taken. A prefilter that is genuinely selective never trips it
/// and keeps the candidate loop for the whole search.
struct PrefilterDrive {
    attempts: usize,
    first_candidate: usize,
}

/// Failed attempts to allow before the selectivity of a prefilter is judged.
/// The handoff costs one engine pass, so this bounds the waste at a constant
/// number of passes rather than one per candidate.
const MAX_ATTEMPTS: usize = 64;

/// One candidate in this many positions is the point below which a prefilter is
/// discarding enough of the input to be worth verifying position by position.
const MIN_SELECTIVITY: usize = 8;

/// Outcome of [`CompiledRegex::captures_one_pass`].
enum OnePassSearch<T> {
    Match(T),
    /// No candidate position matched, so neither will any other.
    NoMatch,
    /// The candidate loop was abandoned; resume the general search here.
    GaveUp(usize),
    /// The prefilter is not a source of anchored start positions.
    NotApplicable,
}

impl PrefilterDrive {
    fn new() -> Self {
        Self {
            attempts: 0,
            first_candidate: 0,
        }
    }

    /// Records a failed attempt at `candidate`. Returns true when the caller
    /// should abandon the loop and search from `candidate` with the engine.
    fn give_up(&mut self, candidate: usize) -> bool {
        if self.attempts == 0 {
            self.first_candidate = candidate;
        }
        self.attempts += 1;
        self.attempts > MAX_ATTEMPTS
            && self.attempts * MIN_SELECTIVITY > candidate - self.first_candidate + 1
    }
}

impl CompiledRegex {
    /// Returns the name of the engine being used (for debugging).
    pub fn engine_name(&self) -> &'static str {
        match &self.inner {
            CompiledInner::PikeVm(_) => "PikeVm",
            CompiledInner::ShiftOr(_) => "ShiftOr",
            CompiledInner::ShiftOrWide(_) => "ShiftOrWide",
            CompiledInner::LazyDfa(_) => "LazyDfa",
            CompiledInner::EagerDfa(_) => "EagerDfa",
            CompiledInner::CodepointClass(_) => "CodepointClass",
            CompiledInner::BacktrackingVm(_) => "BacktrackingVm",
            CompiledInner::TaggedNfaInterp(_) => "TaggedNfa",
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::Jit(_) => "Jit",
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::TaggedNfaJit(_) => "TaggedNfaJit",
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::Backtracking(_) => "BacktrackingJit",
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::JitShiftOr(_) => "JitShiftOr",
        }
    }

    /// Gets or creates a cached PikeVM and context for capture extraction.
    /// This avoids cloning the NFA and allocating storage on every captures() call.
    fn get_or_init_capture_vm(&self) {
        if self.capture_vm.read().unwrap().is_some() {
            return;
        }
        if let Some(nfa) = self.capture_nfa.read().unwrap().as_ref() {
            let vm = PikeVm::new(nfa.clone());
            let ctx = vm.create_context();
            *self.capture_vm.write().unwrap() = Some(vm);
            *self.capture_ctx.write().unwrap() = Some(ctx);
        }
    }

    /// Returns true if the pattern matches anywhere in the input.
    pub fn is_match(&self, input: &[u8]) -> bool {
        // Fast path: if prefilter can provide full match bounds (TeddyFull),
        // finding any match means there's a match
        if self.prefilter.is_full_match() {
            return self.prefilter.find_full_match(input, 0).is_some();
        }

        // Use prefilter to skip to candidate positions
        if !self.prefilter.is_none() {
            if self.engine_searches_single_pass() {
                let first = self.prefilter.find_candidates(input).next();
                return match first {
                    Some(first) => self.find_engine_from_boundary(input, first).is_some(),
                    None => false,
                };
            }
            let mut drive = PrefilterDrive::new();
            for candidate in self.prefilter.find_candidates(input) {
                if self.is_match_at(input, candidate) {
                    return true;
                }
                if drive.give_up(candidate) {
                    return self.find_engine_from_boundary(input, candidate).is_some();
                }
            }
            return false;
        }

        // No prefilter - check from start
        match &self.inner {
            CompiledInner::PikeVm(vm) => vm.is_match(input),
            CompiledInner::ShiftOr(so) => so.is_match(input),
            CompiledInner::ShiftOrWide(so) => so.is_match(input),
            CompiledInner::LazyDfa(dfa) => dfa.write().unwrap().find(input).is_some(),
            CompiledInner::EagerDfa(dfa) => dfa.find(input).is_some(),
            CompiledInner::CodepointClass(matcher) => matcher.is_match(input),
            CompiledInner::BacktrackingVm(vm) => vm.find(input).is_some(),
            CompiledInner::TaggedNfaInterp(engine) => engine.is_match(input),
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::Jit(jit) => jit.is_match(input),
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::TaggedNfaJit(engine) => engine.is_match(input),
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::Backtracking(jit) => jit.is_match(input),
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::JitShiftOr(jit) => jit.find(input).is_some(),
        }
    }

    /// Whether the engine has no way to test one start position in isolation.
    ///
    /// For these, `find_at_pos` is the *same* unanchored search as
    /// `find_engine_from` — it scans to the end of the input rather than
    /// answering about `pos` alone. Handing them candidates one at a time is
    /// then not just wasteful but quadratic: each of k candidates rescans the
    /// remaining n bytes. `a+b` over 100 KB of text with no match took 146 ms
    /// under the DFA JIT against 0.03 ms interpreted, purely from this.
    ///
    /// The prefilter still pays: it skips to the first candidate, and the single
    /// scan from there finds the leftmost match. That is sound because a
    /// prefilter never rules out a real match start.
    ///
    /// The engines with a genuine anchored primitive — Shift-Or's
    /// `try_match_at`, the DFA families' `find_at` — are driven candidate by
    /// candidate as before.
    #[inline]
    fn engine_searches_single_pass(&self) -> bool {
        match &self.inner {
            CompiledInner::PikeVm(_)
            | CompiledInner::BacktrackingVm(_)
            | CompiledInner::TaggedNfaInterp(_)
            | CompiledInner::CodepointClass(_) => true,
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::Jit(_)
            | CompiledInner::TaggedNfaJit(_)
            | CompiledInner::Backtracking(_) => true,
            _ => false,
        }
    }

    /// Returns true if this regex uses a TeddyFull prefilter.
    /// When true, `find_iter_fast()` can be used for better performance.
    #[inline]
    pub fn is_full_match_prefilter(&self) -> bool {
        self.prefilter.is_full_match()
    }

    /// Returns an optimized iterator for patterns with TeddyFull prefilter.
    /// This returns matches directly from the Teddy SIMD matcher without
    /// going through the NFA/DFA engine.
    ///
    /// Only valid when `is_full_match_prefilter()` returns true.
    #[inline]
    pub fn find_full_matches<'a>(
        &'a self,
        input: &'a [u8],
    ) -> crate::literal::FullMatchIter<'a, 'a> {
        self.prefilter.find_full_matches(input)
    }

    /// Finds the first match, returning (start, end).
    pub fn find(&self, input: &[u8]) -> Option<(usize, usize)> {
        self.find_from(input, 0)
    }

    /// Finds the leftmost match starting at or after `from`, returning (start, end).
    ///
    /// This is the resume point used by iteration. The engines always get the
    /// *whole* input plus a start offset — never a slice beginning at `from` — so
    /// `^`, `\b`/`\B` and lookbehind see the real text to the left of the resume
    /// position. The prefilter stays on the hot path: it is simply scanned from
    /// `from` instead of from 0.
    pub fn find_from(&self, input: &[u8], from: usize) -> Option<(usize, usize)> {
        if from > input.len() {
            return None;
        }
        // A match never starts inside a codepoint. Byte-level constructs (`.`,
        // byte classes) can match a single continuation byte, so an engine
        // scanning start positions will happily report one; the PikeVM and the
        // tagged NFA already refuse those starts, and this makes the rest agree.
        // Rejecting a match and resuming one byte later converges on the
        // leftmost match that does start at a boundary.
        let mut from = from;
        loop {
            let (start, end) = self.find_from_inner(input, from)?;
            if crate::nfa::is_utf8_boundary(input, start) {
                return Some((start, end));
            }
            from = start + 1;
        }
    }

    fn find_from_inner(&self, input: &[u8], from: usize) -> Option<(usize, usize)> {
        // Fast path: if prefilter can provide full match bounds (TeddyFull),
        // return directly without running the NFA
        if self.prefilter.is_full_match() {
            return self.prefilter.find_full_match(input, from);
        }

        // Special handling for InnerByte prefilter
        // InnerByte finds a required byte that appears somewhere in the match,
        // so we need to look back from the found position to find the actual start.
        if self.prefilter.is_inner_byte() {
            let lookback = self.prefilter.inner_byte_lookback();
            let mut search_pos = from;
            let mut drive = PrefilterDrive::new();

            while let Some(inner_pos) = self.prefilter.find_candidate(input, search_pos) {
                // Find the likely start position by looking back for a word boundary
                // (non-word char followed by word char, or start of input).
                // The lookback never reaches behind the resume position.
                let start_pos = inner_pos.saturating_sub(lookback).max(from);
                let mut candidate = start_pos;

                // Find the first word boundary in the lookback window
                for i in (start_pos..inner_pos).rev() {
                    if (i == 0 || !is_word_byte(input[i - 1]))
                        && i < input.len()
                        && is_word_byte(input[i])
                    {
                        candidate = i;
                        break;
                    }
                }

                // Try starting from the candidate position
                if let Some((start, end)) = self.find_at(input, candidate) {
                    return Some((start, end));
                }

                if drive.give_up(inner_pos) {
                    // The caller applies the codepoint-boundary rule.
                    return self.find_engine_from(input, candidate);
                }

                // No match found around this inner byte, skip past it
                search_pos = inner_pos + 1;
            }
            return None;
        }

        // Use prefilter to skip to candidate positions
        // IMPORTANT: Use find_at_pos (exact position) not find_at (linear search from pos)
        // The prefilter already tells us where candidates are - we only need to verify each one.
        if !self.prefilter.is_none() {
            if self.engine_searches_single_pass() {
                // The caller applies the codepoint-boundary rule.
                let first = self.prefilter.find_candidates_from(input, from).next()?;
                return self.find_engine_from(input, first);
            }
            let mut drive = PrefilterDrive::new();
            for candidate in self.prefilter.find_candidates_from(input, from) {
                if let Some(result) = self.find_at_pos(input, candidate) {
                    return Some(result);
                }
                if drive.give_up(candidate) {
                    // The caller applies the codepoint-boundary rule.
                    return self.find_engine_from(input, candidate);
                }
            }
            return None;
        }

        // No prefilter - let the engine scan from the resume position
        self.find_engine_from(input, from)
    }

    /// [`CompiledRegex::find_engine_from`] under the codepoint-boundary rule, for
    /// callers that are not already inside [`CompiledRegex::find_from`]'s loop.
    fn find_engine_from_boundary(&self, input: &[u8], from: usize) -> Option<(usize, usize)> {
        let mut from = from;
        loop {
            let (start, end) = self.find_engine_from(input, from)?;
            if crate::nfa::is_utf8_boundary(input, start) {
                return Some((start, end));
            }
            from = start + 1;
        }
    }

    /// Runs the engine's own unanchored search from `from`, with no prefilter.
    ///
    /// Every engine takes the full input plus a start offset. The two engines
    /// whose generated code has no start-offset parameter (the backtracking and
    /// tagged-NFA JITs) fall back internally to their interpreters for patterns
    /// that read left context, so slicing never hides preceding bytes.
    fn find_engine_from(&self, input: &[u8], from: usize) -> Option<(usize, usize)> {
        match &self.inner {
            CompiledInner::PikeVm(vm) => vm.find_from(input, from),
            CompiledInner::ShiftOr(so) => so.find_at(input, from),
            CompiledInner::ShiftOrWide(so) => so.find_at(input, from),
            CompiledInner::LazyDfa(dfa) => dfa.write().unwrap().find_from(input, from),
            CompiledInner::EagerDfa(dfa) => dfa.find_from(input, from),
            CompiledInner::CodepointClass(matcher) => matcher.find_from(input, from),
            CompiledInner::BacktrackingVm(vm) => vm.find_at(input, from),
            CompiledInner::TaggedNfaInterp(engine) => engine.find_at(input, from),
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::Jit(jit) => jit.find_from(input, from),
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::TaggedNfaJit(engine) => engine.find_at(input, from),
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::Backtracking(jit) => jit.find_from(input, from),
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::JitShiftOr(jit) => jit.find_from(input, from),
        }
    }

    /// Returns capture groups for the first match.
    ///
    /// For Shift-Or, LazyDfa, and JIT engines, this uses a two-pass strategy:
    /// 1. Use the fast engine to find match bounds
    /// 2. Re-run PikeVm at that match start to extract captures
    ///
    /// TaggedNfa performs single-pass capture extraction natively.
    pub fn captures(&self, input: &[u8]) -> Option<Vec<Option<(usize, usize)>>> {
        self.captures_from(input, 0)
    }

    /// Returns capture groups for the first match starting at or after `from`.
    ///
    /// Like [`CompiledRegex::find_from`], the engines receive the whole input and
    /// an explicit start offset, so a resumed search still sees the text to the
    /// left of `from`. All reported slots are absolute input offsets.
    pub fn captures_from(&self, input: &[u8], from: usize) -> Option<Vec<Option<(usize, usize)>>> {
        if from > input.len() {
            return None;
        }
        match &self.inner {
            CompiledInner::PikeVm(vm) => vm.captures_from(input, from),
            CompiledInner::CodepointClass(matcher) => matcher.captures_from(input, from),
            CompiledInner::BacktrackingVm(vm) => {
                // BacktrackingVm does single-pass capture extraction
                vm.captures_from(input, from)
            }
            CompiledInner::TaggedNfaInterp(engine) => {
                // TaggedNfa interpreter does single-pass capture extraction
                engine.captures_from(input, from)
            }
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::TaggedNfaJit(engine) => {
                // TaggedNfa JIT does single-pass capture extraction
                engine.captures_from(input, from)
            }
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::Backtracking(jit) => {
                // Backtracking JIT does single-pass capture extraction
                jit.captures_from(input, from)
            }
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::Jit(_) => {
                // Fast path: if we have BacktrackingVm, use it for single-pass capture extraction
                if let Some(ref backtracking_vm) = self.backtracking_vm {
                    return backtracking_vm.captures_from(input, from);
                }

                // Two-pass capture strategy for DFA JIT (fallback)
                self.captures_two_pass(input, from)
            }
            CompiledInner::ShiftOr(_)
            | CompiledInner::ShiftOrWide(_)
            | CompiledInner::LazyDfa(_)
            | CompiledInner::EagerDfa(_) => {
                // Fast path: if we have BacktrackingVm, use it for single-pass capture extraction
                if let Some(ref backtracking_vm) = self.backtracking_vm {
                    return backtracking_vm.captures_from(input, from);
                }

                self.captures_two_pass(input, from)
            }
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::JitShiftOr(_) => {
                // Use BacktrackingJit for capture extraction if available
                // This is the JIT equivalent of BacktrackingVm used by non-JIT ShiftOr
                if let Some(ref backtracking_jit) = self.backtracking_jit {
                    return backtracking_jit.captures_from(input, from);
                }

                // Fall back to two-pass strategy if no BacktrackingJit
                self.captures_two_pass(input, from)
            }
        }
    }

    /// [`Self::captures_from`] under an explicit step budget.
    ///
    /// [`BudgetExhausted`] means the budget ran out before the search finished. Only the
    /// backtracking engines can report that, and only backreference patterns
    /// reach them: every other engine here is linear in the input and always
    /// returns `Ok`.
    pub fn try_captures_from(
        &self,
        input: &[u8],
        from: usize,
        limit: u64,
    ) -> std::result::Result<Option<CaptureSlots>, BudgetExhausted> {
        if from > input.len() {
            return Ok(None);
        }
        if let Some(ref vm) = self.backtracking_vm {
            return vm.try_captures_from(input, from, limit);
        }
        match &self.inner {
            CompiledInner::BacktrackingVm(vm) => vm.try_captures_from(input, from, limit),
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::Backtracking(jit) => jit.try_captures_from(input, from, limit),
            _ => Ok(self.captures_from(input, from)),
        }
    }

    /// [`Self::find_from`] under an explicit step budget.
    ///
    /// For a backreference pattern this asks the backtracking engine directly
    /// rather than going through the prefilter. A prefilter only skips start
    /// positions that cannot match, so this finds the same match; it just does
    /// not get the prefilter's head start.
    pub fn try_find_from(
        &self,
        input: &[u8],
        from: usize,
        limit: u64,
    ) -> std::result::Result<Option<(usize, usize)>, BudgetExhausted> {
        if from > input.len() {
            return Ok(None);
        }
        match &self.inner {
            CompiledInner::BacktrackingVm(vm) => vm.try_find_at(input, from, limit),
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::Backtracking(jit) => Ok(jit
                .try_captures_from(input, from, limit)?
                .and_then(|c| c[0])),
            _ => Ok(self.find_from(input, from)),
        }
    }

    /// Two-pass capture extraction for engines that only report match bounds:
    /// 1. Find the match bounds with the fast engine (from `from`).
    /// 2. Re-run the cached PikeVM at that exact start position.
    ///
    /// The second pass is given the full input and a start position rather than
    /// a slice starting at the match, so the capture pass evaluates `^`, `\b` and
    /// lookbehind against the same context the first pass used. Slots come back
    /// as absolute offsets.
    ///
    /// A capture NFA is only built when the pattern actually has groups to
    /// extract (see the `capture_nfa` fields set during compilation). With no
    /// groups there is nothing for a second pass to do: the match bounds found in
    /// step 1 *are* the whole capture set, and slot 0 is returned directly.
    ///
    /// Both passes are skipped entirely for a one-pass pattern: [`OnePass`] both
    /// locates the match and writes the slots in a single deterministic scan (see
    /// [`CompiledRegex::captures_one_pass`]), so the match region is walked once
    /// instead of once by the search engine and again by the capture pass.
    fn captures_two_pass(&self, input: &[u8], from: usize) -> Option<Vec<Option<(usize, usize)>>> {
        let mut from = from;
        if let Some(ref one_pass) = self.one_pass {
            match self.captures_one_pass(one_pass, input, from) {
                OnePassSearch::Match(slots) => return Some(slots),
                OnePassSearch::NoMatch => return None,
                // The candidate loop stopped paying for itself; every position
                // before `resume` has already been ruled out.
                OnePassSearch::GaveUp(resume) => from = resume,
                OnePassSearch::NotApplicable => {}
            }
        }

        let (match_start, match_end) = self.find_from(input, from)?;

        if let Some(ref one_pass) = self.one_pass {
            if let Some(slots) = one_pass.captures_at(input, match_start) {
                // The deterministic scan and the search engine must agree on the
                // match bounds; if they somehow do not, defer to the PikeVM.
                if slots.first().copied().flatten() == Some((match_start, match_end)) {
                    return Some(slots);
                }
            }
        }

        // Use cached PikeVM and context to avoid allocations
        self.get_or_init_capture_vm();
        let vm_ref = self.capture_vm.read().unwrap();
        let vm = match vm_ref.as_ref() {
            Some(vm) => vm,
            // Group-less pattern: the full match is the only slot.
            None => return Some(vec![Some((match_start, match_end))]),
        };
        let mut ctx_ref = self.capture_ctx.write().unwrap();
        let ctx = ctx_ref.as_mut()?;

        vm.captures_with_context(input, ctx, match_start)
    }

    /// Drives [`OnePass`] over candidate start positions, so a match is located
    /// and its slots written by the same scan.
    ///
    /// The two-pass path asks the search engine where the match is and then
    /// re-scans it to recover the groups, which walks the match region twice.
    /// `OnePass` is anchored and deterministic: an attempt at a position that
    /// cannot match stops at the first byte with no transition, so trying the
    /// positions the prefilter keeps replaces the search outright.
    ///
    /// Leftmost-first is preserved because candidates arrive in increasing order
    /// and a prefilter only ever skips positions where no match can begin, so the
    /// first position `OnePass` accepts is the leftmost one.
    ///
    /// A failed attempt is bounded by the pattern, not by the input, but it is not
    /// bounded by a *constant*: `(a{1000})b` over a run of `a`s would scan a
    /// thousand bytes per candidate. [`PrefilterDrive`] watches for exactly that
    /// and hands the rest of the input back to the linear-time search.
    fn captures_one_pass(
        &self,
        one_pass: &OnePass,
        input: &[u8],
        from: usize,
    ) -> OnePassSearch<Vec<Option<(usize, usize)>>> {
        // A full-match prefilter already reports the span without running an
        // engine, and an inner-byte one yields positions inside the match rather
        // than starts. Neither is a source of anchored candidates.
        if self.prefilter.is_full_match() || self.prefilter.is_inner_byte() {
            return OnePassSearch::NotApplicable;
        }

        // A candidate iterator stops one short of the end, because no prefilter
        // byte can live at `input.len()`. A nullable pattern can still match
        // there, so end-of-input is always the last position tried.
        let candidates = self
            .prefilter
            .find_candidates_from(input, from)
            .chain(std::iter::once(input.len()));

        // Allocated once for the whole search rather than once per attempt.
        let mut scratch = vec![None; one_pass.slot_count()];
        let mut slots = vec![None; one_pass.slot_count()];

        let mut drive = PrefilterDrive::new();
        for candidate in candidates {
            // A match never starts inside a codepoint; `find_from` applies the
            // same rule to the engines' answers.
            if !crate::nfa::is_utf8_boundary(input, candidate) {
                continue;
            }
            if one_pass.captures_at_into(input, candidate, &mut scratch, &mut slots) {
                return OnePassSearch::Match(slots);
            }
            if drive.give_up(candidate) {
                return OnePassSearch::GaveUp(candidate);
            }
        }
        OnePassSearch::NoMatch
    }

    /// Check if there's a match starting at `pos`.
    ///
    /// This method passes the full input to allow engines to check context
    /// (e.g., for word boundary assertions).
    fn is_match_at(&self, input: &[u8], pos: usize) -> bool {
        self.find_at_pos(input, pos).is_some()
    }

    /// Find a match starting exactly at `pos`.
    ///
    /// This method passes the full input to allow engines to check context
    /// (e.g., for word boundary assertions).
    fn find_at_pos(&self, input: &[u8], pos: usize) -> Option<(usize, usize)> {
        if pos > input.len() {
            return None;
        }
        match &self.inner {
            CompiledInner::PikeVm(vm) => vm.find_at(input, pos),
            CompiledInner::ShiftOr(so) => so.try_match_at(input, pos),
            CompiledInner::ShiftOrWide(so) => so.try_match_at(input, pos),
            CompiledInner::LazyDfa(dfa) => dfa
                .write()
                .unwrap()
                .find_at(input, pos)
                .map(|end| (pos, end)),
            CompiledInner::EagerDfa(dfa) => dfa.find_at(input, pos).map(|end| (pos, end)),
            CompiledInner::CodepointClass(matcher) => {
                // CodepointClass doesn't support word boundaries, use sliced input
                let slice = &input[pos..];
                matcher.find(slice).map(|(s, e)| (pos + s, pos + e))
            }
            CompiledInner::BacktrackingVm(vm) => vm.find_at(input, pos),
            CompiledInner::TaggedNfaInterp(engine) => engine.find_at(input, pos),
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::Jit(jit) => jit.find_at(input, pos),
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::TaggedNfaJit(engine) => engine.find_at(input, pos),
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::Backtracking(jit) => jit.find_at(input, pos),
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            CompiledInner::JitShiftOr(jit) => jit.try_match_at(input, pos),
        }
    }

    /// Find a match starting at or after `pos`.
    fn find_at(&self, input: &[u8], pos: usize) -> Option<(usize, usize)> {
        // Try each position starting from pos
        for start in pos..=input.len() {
            if let Some(result) = self.find_at_pos(input, start) {
                return Some(result);
            }
        }
        None
    }
}

/// Compiles an NFA into an executable regex (legacy API).
/// Note: This cannot use Shift-Or as it requires HIR for Glushkov construction.
/// Also cannot use prefilter (requires HIR for literal extraction).
pub fn compile(nfa: Nfa) -> Result<CompiledRegex> {
    let engine = select_engine(&nfa);

    let (inner, capture_nfa) = match engine {
        EngineType::PikeVm => (CompiledInner::PikeVm(PikeVm::new(nfa)), None),
        EngineType::BacktrackingVm => {
            // NFA-based compilation can't use BacktrackingVm (needs HIR)
            // Fall back to PikeVm which also handles backrefs
            (CompiledInner::PikeVm(PikeVm::new(nfa)), None)
        }
        EngineType::ShiftOr | EngineType::ShiftOrWide => {
            // NFA-based compilation can't use Shift-Or (needs Glushkov from HIR)
            // Fall back to LazyDfa, keep NFA for captures
            let capture_nfa = Some(nfa.clone());
            (
                CompiledInner::LazyDfa(RwLock::new(LazyDfa::new(nfa))),
                capture_nfa,
            )
        }
        EngineType::LazyDfa => {
            let capture_nfa = Some(nfa.clone());
            (
                CompiledInner::LazyDfa(RwLock::new(LazyDfa::new(nfa))),
                capture_nfa,
            )
        }
        #[cfg(feature = "jit")]
        EngineType::Jit => {
            // JIT not implemented yet, fall back to LazyDfa
            let capture_nfa = Some(nfa.clone());
            (
                CompiledInner::LazyDfa(RwLock::new(LazyDfa::new(nfa))),
                capture_nfa,
            )
        }
    };

    let one_pass = capture_nfa.as_ref().and_then(OnePass::compile);

    Ok(CompiledRegex {
        inner,
        prefilter: Prefilter::None, // Can't extract literals from NFA
        capture_nfa: RwLock::new(capture_nfa),
        one_pass,
        capture_vm: RwLock::new(None),
        capture_ctx: RwLock::new(None),
        backtracking_vm: None,
        #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
        backtracking_jit: None,
    })
}

/// Compiles an HIR into an executable regex.
/// This is the preferred API as it can use Shift-Or for small patterns
/// and prefilters for SIMD-accelerated candidate detection.
pub fn compile_from_hir(hir: &Hir) -> Result<CompiledRegex> {
    // Fast path: if the pattern is a single character class, use CodepointClassMatcher.
    // This is MUCH faster than byte-level DFA for Unicode patterns like [^α-ω].
    if let Some(ref codepoint_class) = hir.props.codepoint_class {
        return Ok(CompiledRegex {
            inner: CompiledInner::CodepointClass(CodepointClassMatcher::new(
                codepoint_class.clone(),
            )),
            prefilter: Prefilter::None,
            capture_nfa: RwLock::new(None),
            one_pass: None,
            capture_vm: RwLock::new(None),
            capture_ctx: RwLock::new(None),
            backtracking_vm: None,
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            backtracking_jit: None,
        });
    }

    // Patterns with lookaround → TaggedNfa interpreter (it handles lookahead via
    // the step model). Non-greedy quantifiers, however, need the precise thread
    // priority of the Pike VM: the step model does not represent non-greedy
    // faithfully (e.g. a bounded repeat followed by `+?` lets the lazy match
    // zero), so any non-greedy pattern falls through to `select_engine_from_hir`,
    // which routes it to PikeVm. (Non-greedy is not on the tiktoken hot path.)
    if hir.props.has_lookaround && !hir.props.has_non_greedy {
        let literals = extract_literals(hir);
        let prefilter = Prefilter::from_literals(&literals);
        let nfa = nfa::compile(hir)?;
        let engine = TaggedNfaEngine::new(nfa);
        return Ok(CompiledRegex {
            inner: CompiledInner::TaggedNfaInterp(engine),
            prefilter,
            capture_nfa: RwLock::new(None),
            one_pass: None,
            capture_vm: RwLock::new(None),
            capture_ctx: RwLock::new(None),
            backtracking_vm: None,
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            backtracking_jit: None,
        });
    }

    // Extract literals for prefilter
    // Word boundaries: NOW SUPPORTED! The executor passes full input context
    // to engines via find_at_pos(), allowing proper word boundary checking.
    // Anchors: NOW SUPPORTED! LazyDFA/JIT handle start anchor optimization
    // internally, so prefilter can still be used for patterns with anchors.
    let literals = extract_literals(hir);
    let mut prefilter = Prefilter::from_literals(&literals);

    // Capture extraction is a hybrid: `find` uses the fast automaton engine, and
    // the slots come from a second pass (see `captures_two_pass`).
    //
    // That second pass is the PikeVM unless the pattern has backreferences. A
    // backreference makes the match depend on what earlier groups captured,
    // which only a backtracking engine represents, and it is the one construct
    // worth paying for: backtracking explores an unbounded search tree, so it
    // answers under a step budget rather than the linear bound every other
    // engine here meets. Routing capture-only patterns through it — which is
    // what this used to do for *any* pattern with a group — silently gave every
    // `captures()` call that same unbounded cost.
    let needs_backtracking = hir.props.has_backrefs;

    let engine = select_engine_from_hir(hir);

    // The PikeVM owns the leftmost-first match decision, so a full-match literal
    // prefilter must not short-circuit it (see `Prefilter::into_candidate_only`).
    if engine == EngineType::PikeVm {
        prefilter = prefilter.into_candidate_only();
    }

    let (inner, capture_nfa) = match engine {
        EngineType::PikeVm => {
            let nfa = nfa::compile(hir)?;
            (CompiledInner::PikeVm(PikeVm::new(nfa)), None)
        }
        EngineType::BacktrackingVm => {
            // BacktrackingVm for patterns with backreferences
            // This maintains parity with BacktrackingJit for JIT builds
            (
                CompiledInner::BacktrackingVm(BacktrackingVm::new(hir)),
                None,
            )
        }
        EngineType::ShiftOr => {
            // Use Glushkov NFA for Shift-Or
            // Keep Thompson NFA for captures (two-pass strategy)
            // Use from_hir_with_anchors for patterns with non-multiline anchors
            let shift_or = if hir.props.has_anchors {
                ShiftOr::from_hir_with_anchors(hir)
            } else {
                ShiftOr::from_hir(hir)
            };
            match shift_or {
                Some(so) => {
                    let capture_nfa = nfa::compile(hir)?;
                    (CompiledInner::ShiftOr(so), Some(capture_nfa))
                }
                None => {
                    // Fall back to LazyDfa
                    let nfa = nfa::compile(hir)?;
                    let capture_nfa = Some(nfa.clone());
                    (
                        CompiledInner::LazyDfa(RwLock::new(LazyDfa::new(nfa))),
                        capture_nfa,
                    )
                }
            }
        }
        EngineType::ShiftOrWide => {
            // Use Wide Glushkov NFA for ShiftOrWide (65-256 positions)
            // Keep Thompson NFA for captures (two-pass strategy)
            match ShiftOrWide::from_hir(hir) {
                Some(so) => {
                    let capture_nfa = nfa::compile(hir)?;
                    (CompiledInner::ShiftOrWide(so), Some(capture_nfa))
                }
                None => {
                    // Fall back to LazyDfa
                    let nfa = nfa::compile(hir)?;
                    let capture_nfa = Some(nfa.clone());
                    (
                        CompiledInner::LazyDfa(RwLock::new(LazyDfa::new(nfa))),
                        capture_nfa,
                    )
                }
            }
        }
        EngineType::LazyDfa => {
            let nfa = nfa::compile(hir)?;
            let capture_nfa = Some(nfa.clone());

            // Use LazyDfa (not EagerDfa) for:
            // - Large Unicode classes: avoid state explosion during materialization
            // - Patterns with anchors: EagerDfa doesn't handle anchors correctly
            // EagerDfa creates all reachable states upfront, which can be millions
            // for large Unicode classes.
            if hir.props.has_large_unicode_class || hir.props.has_anchors {
                (
                    CompiledInner::LazyDfa(RwLock::new(LazyDfa::new(nfa))),
                    capture_nfa,
                )
            } else {
                // Use EagerDfa for better non-JIT performance on simple patterns.
                // EagerDfa pre-computes all states upfront, eliminating hash lookups.
                let mut lazy = LazyDfa::new(nfa);
                let eager = EagerDfa::from_lazy(&mut lazy);
                (CompiledInner::EagerDfa(eager), capture_nfa)
            }
        }
        #[cfg(feature = "jit")]
        EngineType::Jit => {
            // JIT not implemented yet, fall back to EagerDfa or LazyDfa
            let nfa = nfa::compile(hir)?;
            let capture_nfa = Some(nfa.clone());

            // Use LazyDfa for patterns with large Unicode classes or anchors
            if hir.props.has_large_unicode_class || hir.props.has_anchors {
                (
                    CompiledInner::LazyDfa(RwLock::new(LazyDfa::new(nfa))),
                    capture_nfa,
                )
            } else {
                let mut lazy = LazyDfa::new(nfa);
                let eager = EagerDfa::from_lazy(&mut lazy);
                (CompiledInner::EagerDfa(eager), capture_nfa)
            }
        }
    };

    // Backreference patterns need single-pass backtracking capture extraction;
    // everything else goes through the PikeVM second pass.
    let backtracking_vm = if needs_backtracking {
        Some(BacktrackingVm::new(hir))
    } else {
        None
    };

    let one_pass = capture_nfa.as_ref().and_then(OnePass::compile);

    Ok(CompiledRegex {
        inner,
        prefilter,
        capture_nfa: RwLock::new(capture_nfa),
        one_pass,
        capture_vm: RwLock::new(None),
        capture_ctx: RwLock::new(None),
        backtracking_vm,
        #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
        backtracking_jit: None,
    })
}

/// Compiles an HIR using PikeVM (default, no JIT).
///
/// PikeVM is a thread-based NFA simulator that supports all regex features
/// including backreferences, lookarounds, and non-greedy quantifiers.
/// It's slower than JIT but handles all patterns correctly.
pub fn compile_with_pikevm(hir: &Hir) -> Result<CompiledRegex> {
    let literals = extract_literals(hir);
    // Word boundaries and anchors: NOW SUPPORTED via full input context.
    // Demote any full-match prefilter to candidate-only: the PikeVM is the
    // leftmost-first authority and must determine the match span itself. A
    // full-match literal prefilter resolves overlaps by length/order, not by
    // alternation branch priority (`ab|a` → it returns "a", PikeVM needs "ab"),
    // and all alternations are routed here.
    let prefilter = Prefilter::from_literals(&literals).into_candidate_only();
    let nfa = nfa::compile(hir)?;

    Ok(CompiledRegex {
        inner: CompiledInner::PikeVm(PikeVm::new(nfa)),
        prefilter,
        capture_nfa: RwLock::new(None),
        one_pass: None,
        capture_vm: RwLock::new(None),
        capture_ctx: RwLock::new(None),
        backtracking_vm: None,
        #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
        backtracking_jit: None,
    })
}

/// Compiles an HIR with JIT compilation for maximum performance.
///
/// JIT compiles the pattern to native machine code for fast matching.
/// Ideal for patterns that will be matched many times (e.g., tokenization).
///
/// Engine selection strategy:
/// 0. Single character class → CodepointClassMatcher (fastest for Unicode)
/// 1. Complex Unicode patterns → LazyDfa (skip JIT to avoid state explosion)
/// 2. Patterns with backrefs/lookaround/non-greedy → TaggedNfa (liveness-optimized)
/// 3. Simple patterns → DFA JIT
pub fn compile_with_jit(hir: &Hir) -> Result<CompiledRegex> {
    // 0. Single character class → CodepointClassMatcher (fastest for Unicode)
    if let Some(ref codepoint_class) = hir.props.codepoint_class {
        return Ok(CompiledRegex {
            inner: CompiledInner::CodepointClass(CodepointClassMatcher::new(
                codepoint_class.clone(),
            )),
            prefilter: Prefilter::None,
            capture_nfa: RwLock::new(None),
            one_pass: None,
            capture_vm: RwLock::new(None),
            capture_ctx: RwLock::new(None),
            backtracking_vm: None,
            #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
            backtracking_jit: None,
        });
    }

    // Non-greedy quantifiers → PikeVm, checked BEFORE the large-unicode-class and
    // lookaround routes (which would otherwise grab codepoint lazy patterns like
    // `\S+?`). The step-based TaggedNfa(JIT) does not represent non-greedy
    // faithfully (a bounded repeat followed by `+?` can let the lazy match zero);
    // PikeVm has the precise thread-priority semantics. Backref patterns are left
    // for the backtracking engine below.
    if hir.props.has_non_greedy && !hir.props.has_backrefs {
        // `compile_with_pikevm` demotes any full-match literal prefilter to
        // candidate-only so it cannot short-circuit the leftmost-first match
        // (e.g. `a+?| $`, a non-greedy branch in an alternation).
        return compile_with_pikevm(hir);
    }

    // A word boundary guarding an empty match (`\Ba*`, `\b(?:xy)?`) is not
    // representable in the DFA JIT — see `needs_boundary_aware_empty_match`.
    // Backreference patterns are left for the backtracking engine below, which
    // evaluates assertions positionally and so is unaffected.
    if needs_boundary_aware_empty_match(hir) && !hir.props.has_backrefs {
        return compile_with_pikevm(hir);
    }

    // A multiline anchor guarding an empty match (`\s*(?m)$`) has the same
    // problem in the DFA JIT: the empty match at a line end is only valid
    // because of the byte that follows, which the JIT has already committed to
    // by the time it decides to accept — it reports the final match and drops
    // the interior ones. The interpreted DFA resolves the anchor positionally
    // and gets this right, so hand the pattern back to the ordinary selection
    // rather than to the PikeVM.
    if hir.props.has_multiline_anchors
        && crate::hir::matches_empty(&hir.expr)
        && !hir.props.has_backrefs
    {
        return compile_from_hir(hir);
    }

    // 1. Complex Unicode patterns with large unicode classes → TaggedNfa JIT
    // These patterns use CodepointClass instructions which DFA cannot handle.
    // Route them to TaggedNfa JIT which supports CodepointClass.
    // (Backreference patterns are excluded — TaggedNfa can't handle backrefs;
    // they must reach the backtracking engine below even when they also contain
    // a large unicode class such as Unicode `\s`.)
    #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
    if hir.props.has_large_unicode_class && !hir.props.has_backrefs {
        let literals = extract_literals(hir);
        let prefilter = Prefilter::from_literals(&literals);
        let nfa = nfa::compile(hir)?;
        match jit::compile_tagged_nfa(&nfa) {
            Ok(engine) => {
                return Ok(CompiledRegex {
                    inner: CompiledInner::TaggedNfaJit(engine),
                    prefilter,
                    capture_nfa: RwLock::new(None),
                    one_pass: None,
                    capture_vm: RwLock::new(None),
                    capture_ctx: RwLock::new(None),
                    backtracking_vm: None,
                    backtracking_jit: None,
                });
            }
            Err(_e) => {
                // TaggedNfa JIT failed - fall back to TaggedNfa interpreter
                #[cfg(debug_assertions)]
                eprintln!("[regexr] TaggedNfaJit failed for large unicode class, falling back to interpreter: {}", _e);
                let engine = TaggedNfaEngine::new(nfa);
                return Ok(CompiledRegex {
                    inner: CompiledInner::TaggedNfaInterp(engine),
                    prefilter,
                    capture_nfa: RwLock::new(None),
                    one_pass: None,
                    capture_vm: RwLock::new(None),
                    capture_ctx: RwLock::new(None),
                    backtracking_vm: None,
                    backtracking_jit: None,
                });
            }
        }
    }

    // Non-JIT: Large unicode classes go to TaggedNfa interpreter (but not
    // backreference patterns — TaggedNfa can't handle backrefs).
    #[cfg(not(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64"))))]
    if hir.props.has_large_unicode_class && !hir.props.has_backrefs {
        let literals = extract_literals(hir);
        let prefilter = Prefilter::from_literals(&literals);
        let nfa = nfa::compile(hir)?;
        let engine = TaggedNfaEngine::new(nfa);
        return Ok(CompiledRegex {
            inner: CompiledInner::TaggedNfaInterp(engine),
            prefilter,
            capture_nfa: RwLock::new(None),
            one_pass: None,
            capture_vm: RwLock::new(None),
            capture_ctx: RwLock::new(None),
            backtracking_vm: None,
        });
    }

    // 2. Patterns with backreferences → Backtracking JIT (only way to handle backrefs)
    // Backtracking JIT is required for backreferences since DFA cannot handle them.
    #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
    if hir.props.has_backrefs && !hir.props.has_lookaround {
        let literals = extract_literals(hir);
        let prefilter = Prefilter::from_literals(&literals);
        match jit::compile_backtracking(hir) {
            Ok(jit_regex) => {
                return Ok(CompiledRegex {
                    inner: CompiledInner::Backtracking(jit_regex),
                    prefilter,
                    capture_nfa: RwLock::new(None),
                    one_pass: None,
                    capture_vm: RwLock::new(None),
                    capture_ctx: RwLock::new(None),
                    backtracking_vm: None,
                    #[cfg(all(
                        feature = "jit",
                        any(target_arch = "x86_64", target_arch = "aarch64")
                    ))]
                    backtracking_jit: None,
                });
            }
            Err(_) => {
                // Backtracking JIT failed (e.g. the pattern also contains a large
                // Unicode class like Unicode `\s`). Fall back to the BacktrackingVm
                // interpreter, which handles backreferences — PikeVM does not.
                return Ok(CompiledRegex {
                    inner: CompiledInner::BacktrackingVm(BacktrackingVm::new(hir)),
                    prefilter,
                    capture_nfa: RwLock::new(None),
                    one_pass: None,
                    capture_vm: RwLock::new(None),
                    capture_ctx: RwLock::new(None),
                    backtracking_vm: None,
                    backtracking_jit: None,
                });
            }
        }
    }

    // 2a. Patterns with lookaround → TaggedNfa JIT (handles lookahead via the
    // step model with memoized lookaround evaluation).
    //
    // NOTE: Patterns with captures but NO non-greedy/lookaround should use DFA JIT
    // because DFA JIT is much faster. DFA JIT handles captures via two-pass:
    // 1. Fast DFA JIT for find()
    // 2. PikeVM on matched substring for captures() only when needed
    #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
    if hir.props.has_lookaround {
        let literals = extract_literals(hir);
        let prefilter = Prefilter::from_literals(&literals);
        let nfa = nfa::compile(hir)?;
        match jit::compile_tagged_nfa(&nfa) {
            Ok(engine) => {
                return Ok(CompiledRegex {
                    inner: CompiledInner::TaggedNfaJit(engine),
                    prefilter,
                    capture_nfa: RwLock::new(None),
                    one_pass: None,
                    capture_vm: RwLock::new(None),
                    capture_ctx: RwLock::new(None),
                    backtracking_vm: None,
                    backtracking_jit: None,
                });
            }
            Err(_e) => {
                // TaggedNfa JIT failed (e.g., lookahead with captures not yet supported).
                // Fall back to TaggedNfa interpreter which handles all cases correctly.
                #[cfg(debug_assertions)]
                eprintln!(
                    "[regexr] TaggedNfaJit failed, falling back to interpreter: {}",
                    _e
                );
                let engine = TaggedNfaEngine::new(nfa);
                return Ok(CompiledRegex {
                    inner: CompiledInner::TaggedNfaInterp(engine),
                    prefilter,
                    capture_nfa: RwLock::new(None),
                    one_pass: None,
                    capture_vm: RwLock::new(None),
                    capture_ctx: RwLock::new(None),
                    backtracking_vm: None,
                    backtracking_jit: None,
                });
            }
        }
    }

    // Fall back to TaggedNfa interpreter when JIT feature is not available
    // Note: TaggedNfa interpreter is now always available (faster than PikeVm for lookaround)
    #[cfg(not(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64"))))]
    if hir.props.has_lookaround || hir.props.has_non_greedy {
        let literals = extract_literals(hir);
        let prefilter = Prefilter::from_literals(&literals);
        let nfa = nfa::compile(hir)?;
        let engine = TaggedNfaEngine::new(nfa);
        return Ok(CompiledRegex {
            inner: CompiledInner::TaggedNfaInterp(engine),
            prefilter,
            capture_nfa: RwLock::new(None),
            one_pass: None,
            capture_vm: RwLock::new(None),
            capture_ctx: RwLock::new(None),
            backtracking_vm: None,
        });
    }

    // Backreferences without the JIT go to the same `BacktrackingVm` that
    // `compile_from_hir` picks, NOT the PikeVM.
    //
    // The PikeVM does handle backreferences, but only as a last resort: a
    // backreference breaks its per-position state deduplication (two threads in
    // one state are no longer interchangeable when their captures differ), so it
    // restarts the whole simulation at every start position — quadratic where
    // the backtracking engine is not. Selecting it here made `jit(true)` on a
    // build without the JIT feature *slower* than plain `Regex::new`, which
    // inverts what the flag means.
    #[cfg(not(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64"))))]
    if hir.props.has_backrefs {
        let literals = extract_literals(hir);
        return Ok(CompiledRegex {
            inner: CompiledInner::BacktrackingVm(BacktrackingVm::new(hir)),
            prefilter: Prefilter::from_literals(&literals),
            capture_nfa: RwLock::new(None),
            one_pass: None,
            capture_vm: RwLock::new(None),
            capture_ctx: RwLock::new(None),
            backtracking_vm: None,
        });
    }

    // Alternations require leftmost-first branch priority. The DFA JIT and
    // JitShiftOr below resolve to the first/longest accepting state and so return
    // the wrong branch (`ab|a` → `a`, `\d+|\w+` → the longer `\w+`). Route any
    // alternation to the ordered PikeVM instead. (Patterns with lookaround,
    // backrefs, non-greedy or codepoint classes were already dispatched above.)
    if crate::engine::selector::hir_has_alternation(&hir.expr) {
        return compile_with_pikevm(hir);
    }

    // An alternation — including the one a negated class lowers to — belongs on
    // the DFA rather than Shift-Or, whose step walks the live positions and so
    // costs more the more branches there are. `select_engine_from_hir` already
    // routes it there, and this path has to agree: without it `jit(true)` reached
    // JitShiftOr and ran the tokenizer's alternation ~20% SLOWER than
    // `Regex::new`, which is the one thing asking for the JIT must never do.
    if crate::engine::selector::hir_contains_alternation(&hir.expr) {
        return compile_from_hir(hir);
    }

    // One repeated byte class is answered by a scan in the interpreted ShiftOr,
    // and no engine on this path beats it: JitShiftOr compiles the bit-parallel
    // automaton the scan replaces, and the DFA JIT is slower still. `\w+` — the
    // tokenizer pattern — is ~2x slower under either than interpreted.
    if crate::vm::is_class_run_shape(hir) {
        return compile_from_hir(hir);
    }

    // A word boundary plus an effective prefilter is the DFA JIT's worst shape,
    // and the interpreted engines' best. The prefilter finds a literal, but the
    // boundary is exactly what makes those candidates fail — "the" inside
    // "their" — and the DFA JIT has no anchored entry point, so a failed
    // candidate turns into a scan of everything after it rather than a rejection.
    // The engines `compile_from_hir` picks verify one position and move on, which
    // is why `\bthe\b` runs ~2.5x faster there. Selecting a worse engine than
    // `Regex::new` is the one thing `jit(true)` must never do.
    if hir.props.has_word_boundary && !hir.props.has_backrefs {
        let literals = extract_literals(hir);
        if Prefilter::from_literals(&literals).is_effective() {
            return compile_from_hir(hir);
        }
    }

    // 3. Small patterns without effective prefilter → JitShiftOr
    // ShiftOr's bit-parallel algorithm is faster than DFA JIT for patterns with
    // many alternations and no common prefix (no effective prefilter).
    // DFA JIT excels when there's a good prefilter to skip non-matching positions.
    #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
    {
        use crate::vm::is_shift_or_compatible;
        let literals = extract_literals(hir);
        let prefilter = Prefilter::from_literals(&literals);

        // Use JitShiftOr when:
        // 1. Pattern is ShiftOr-compatible (≤64 positions, no multiline anchors/word boundaries)
        // 2. No effective prefilter (DFA JIT doesn't benefit as much)
        if !prefilter.is_effective() && is_shift_or_compatible(hir) {
            let shift_or = if hir.props.has_anchors {
                crate::vm::ShiftOr::from_hir_with_anchors(hir)
            } else {
                crate::vm::ShiftOr::from_hir(hir)
            };
            // A pattern the interpreter answers with a class-run scan must not
            // be JIT-compiled: the generated code runs the bit-parallel
            // automaton, which is exactly what the scan replaces. `\w+` is 2x
            // slower JIT-compiled than interpreted.
            if let Some(shift_or) = shift_or {
                if let Some(jit_shift_or) = jit::JitShiftOr::compile(&shift_or) {
                    let capture_nfa = if hir.props.capture_count > 0 {
                        nfa::compile(hir).ok()
                    } else {
                        None
                    };

                    // Only backreferences justify backtracking for captures; see
                    // `compile_from_hir`. Everything else takes the PikeVM
                    // second pass, which is linear in the input.
                    let needs_backtracking = hir.props.has_backrefs;
                    let backtracking_vm = if needs_backtracking {
                        Some(BacktrackingVm::new(hir))
                    } else {
                        None
                    };
                    let backtracking_jit = if needs_backtracking {
                        jit::compile_backtracking(hir).ok()
                    } else {
                        None
                    };

                    let one_pass = capture_nfa.as_ref().and_then(OnePass::compile);

                    return Ok(CompiledRegex {
                        inner: CompiledInner::JitShiftOr(jit_shift_or),
                        prefilter,
                        capture_nfa: RwLock::new(capture_nfa),
                        one_pass,
                        capture_vm: RwLock::new(None),
                        capture_ctx: RwLock::new(None),
                        backtracking_vm,
                        backtracking_jit,
                    });
                }
            }
        }
    }

    // 4. Simple patterns with effective prefilter → DFA JIT
    // DFA JIT benefits from prefilter to quickly skip non-matching positions.
    #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
    {
        let literals = extract_literals(hir);
        let prefilter = Prefilter::from_literals(&literals);
        let nfa = nfa::compile(hir)?;
        let capture_nfa = Some(nfa.clone());
        let one_pass = capture_nfa.as_ref().and_then(OnePass::compile);
        let mut dfa = LazyDfa::new(nfa);

        // Only backreferences justify backtracking for captures; see
        // `compile_from_hir`.
        let backtracking_vm = if hir.props.has_backrefs {
            Some(BacktrackingVm::new(hir))
        } else {
            None
        };

        match jit::compile_dfa(&mut dfa) {
            Ok(jit_regex) => {
                return Ok(CompiledRegex {
                    inner: CompiledInner::Jit(jit_regex),
                    prefilter,
                    capture_nfa: RwLock::new(capture_nfa),
                    one_pass,
                    capture_vm: RwLock::new(None),
                    capture_ctx: RwLock::new(None),
                    backtracking_vm,
                    backtracking_jit: None,
                });
            }
            Err(_) => {
                // DFA JIT failed, fall back to standard engine selection
            }
        }
    }

    // JIT not available or failed - fall back to standard engine selection
    compile_from_hir(hir)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::hir::translate;
    use crate::nfa::compile as nfa_compile;
    use crate::parser::parse;

    fn make_regex(pattern: &str) -> CompiledRegex {
        let ast = parse(pattern).unwrap();
        let hir = translate(&ast).unwrap();
        // Use HIR-based compilation to enable Shift-Or
        compile_from_hir(&hir).unwrap()
    }

    fn make_regex_legacy(pattern: &str) -> CompiledRegex {
        let ast = parse(pattern).unwrap();
        let hir = translate(&ast).unwrap();
        let nfa = nfa_compile(&hir).unwrap();
        compile(nfa).unwrap()
    }

    #[test]
    fn test_is_match() {
        let re = make_regex("hello");
        assert!(re.is_match(b"hello world"));
        assert!(!re.is_match(b"goodbye"));
    }

    #[test]
    fn test_find() {
        let re = make_regex("world");
        assert_eq!(re.find(b"hello world"), Some((6, 11)));
    }

    #[test]
    fn test_alternation() {
        let re = make_regex("cat|dog");
        assert!(re.is_match(b"I have a cat"));
        assert!(re.is_match(b"I have a dog"));
        assert!(!re.is_match(b"I have a bird"));
    }

    #[test]
    fn test_class() {
        let re = make_regex("[0-9]+");
        assert!(re.is_match(b"abc123def"));
        assert!(!re.is_match(b"abcdef"));
    }

    #[test]
    fn test_legacy_api() {
        // Test NFA-based compilation (uses LazyDfa, not Shift-Or)
        let re = make_regex_legacy("hello");
        assert!(re.is_match(b"hello world"));
        assert!(!re.is_match(b"goodbye"));
    }

    // Prefilter integration tests

    #[test]
    fn test_prefilter_single_literal() {
        // Pattern with literal prefix - simple literal pattern (no . or classes)
        let re = make_regex("hello");
        assert!(re.is_match(b"say hello world"));
        assert!(re.is_match(b"hello"));
        assert!(!re.is_match(b"goodbye"));
    }

    #[test]
    fn test_prefilter_literal_extraction() {
        // Test that literal extraction works
        let ast = parse("needle").unwrap();
        let hir = translate(&ast).unwrap();
        let lits = crate::literal::extract_literals(&hir);
        assert_eq!(lits.prefixes.len(), 1, "Should have 1 prefix");
        assert_eq!(lits.prefixes[0], b"needle", "Prefix should be 'needle'");
    }

    #[test]
    fn test_prefilter_with_dot_star() {
        // Test pattern with .* (uses character class)
        let re = make_regex("hello.*world");
        // Direct matches
        assert!(re.is_match(b"hello world"));
        assert!(re.is_match(b"helloworld"));
        assert!(re.is_match(b"hello to the world"));
        // With prefilter skip
        assert!(re.is_match(b"say hello world"));
        assert!(re.is_match(b"say hello to the world"));
        // Non-matches
        assert!(!re.is_match(b"hello"));
        assert!(!re.is_match(b"world"));
    }

    #[test]
    fn test_prefilter_alternation() {
        // Alternation pattern should extract multiple prefixes for Teddy
        let re = make_regex("cat|dog|bird");
        assert!(re.is_match(b"I have a cat"));
        assert!(re.is_match(b"I have a dog"));
        assert!(re.is_match(b"I have a bird"));
        assert!(!re.is_match(b"I have a fish"));
    }

    #[test]
    fn test_prefilter_find_position() {
        // Verify prefilter returns correct position
        let re = make_regex("needle");
        let haystack = b"xxxxxxxxxxxxxxxxxneedlexxxxxxxx";
        let result = re.find(haystack);
        assert_eq!(result, Some((17, 23)));
    }

    #[test]
    fn test_prefilter_large_input() {
        // Test prefilter with large input to exercise SIMD path
        let re = make_regex("needle");
        let mut haystack = vec![b'x'; 10000];
        haystack[5000..5006].copy_from_slice(b"needle");
        assert_eq!(re.find(&haystack), Some((5000, 5006)));
    }

    #[test]
    fn test_prefilter_no_match() {
        // Prefilter should correctly report no match
        let re = make_regex("needle");
        let haystack = vec![b'x'; 10000];
        assert_eq!(re.find(&haystack), None);
        assert!(!re.is_match(&haystack));
    }

    #[test]
    fn test_prefilter_multiple_matches() {
        // Prefilter should find first match
        let re = make_regex("ab");
        assert_eq!(re.find(b"xxxxabxxxxabxxxx"), Some((4, 6)));
    }

    #[test]
    fn test_no_prefilter_class_start() {
        // Patterns starting with class shouldn't have prefilter
        let re = make_regex("[abc]hello");
        assert!(re.is_match(b"ahello"));
        assert!(re.is_match(b"bhello"));
        assert!(!re.is_match(b"dhello"));
    }

    // TaggedNfa integration tests (backrefs, lookaround, non-greedy)
    // These patterns trigger the TaggedNfaEngine path when JIT is enabled

    #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
    mod tagged_nfa_integration {
        use super::*;
        use crate::engine::compile_with_jit;

        fn make_jit_regex(pattern: &str) -> CompiledRegex {
            let ast = parse(pattern).unwrap();
            let hir = translate(&ast).unwrap();
            compile_with_jit(&hir).unwrap()
        }

        #[test]
        fn test_backref_simple() {
            // Pattern with backref should use TaggedNfa
            let re = make_jit_regex(r"(a)\1");
            assert!(re.is_match(b"aa"));
            assert!(!re.is_match(b"ab"));
            assert_eq!(re.find(b"aa"), Some((0, 2)));
        }

        #[test]
        fn test_backref_captures() {
            // Verify captures work with backrefs
            let re = make_jit_regex(r"(abc)\1");
            let caps = re.captures(b"abcabc").unwrap();
            assert_eq!(caps.len(), 2); // Group 0 + Group 1
            assert_eq!(caps[0], Some((0, 6))); // Full match
            assert_eq!(caps[1], Some((0, 3))); // Group 1: "abc"
        }

        #[test]
        fn test_positive_lookahead() {
            // Positive lookahead
            let re = make_jit_regex(r"a(?=b)");
            assert!(re.is_match(b"ab"));
            assert!(!re.is_match(b"ac"));
            assert_eq!(re.find(b"ab"), Some((0, 1))); // Only 'a' matched
        }

        #[test]
        fn test_negative_lookahead() {
            // Negative lookahead
            let re = make_jit_regex(r"a(?!b)");
            assert!(re.is_match(b"ac"));
            assert!(!re.is_match(b"ab"));
            assert_eq!(re.find(b"ac"), Some((0, 1)));
        }

        #[test]
        fn test_positive_lookbehind() {
            // Positive lookbehind
            let re = make_jit_regex(r"(?<=a)b");
            assert!(re.is_match(b"ab"));
            assert!(!re.is_match(b"cb"));
            assert_eq!(re.find(b"ab"), Some((1, 2))); // Only 'b' matched
        }

        #[test]
        fn test_negative_lookbehind() {
            // Negative lookbehind
            let re = make_jit_regex(r"(?<!a)b");
            assert!(re.is_match(b"cb"));
            assert!(!re.is_match(b"ab"));
            assert_eq!(re.find(b"cb"), Some((1, 2)));
        }

        #[test]
        fn test_non_greedy_star() {
            // Non-greedy quantifier
            let re = make_jit_regex(r"a*?b");
            assert_eq!(re.find(b"b"), Some((0, 1))); // Zero a's
            assert_eq!(re.find(b"ab"), Some((0, 2))); // One a
            assert_eq!(re.find(b"aaab"), Some((0, 4))); // Multiple a's
        }

        #[test]
        fn test_non_greedy_plus() {
            // Non-greedy plus
            let re = make_jit_regex(r"a+?b");
            assert_eq!(re.find(b"ab"), Some((0, 2))); // One a
            assert_eq!(re.find(b"aaab"), Some((0, 4))); // Multiple a's
            assert_eq!(re.find(b"b"), None); // Need at least one a
        }

        #[test]
        fn test_complex_lookahead_with_capture() {
            // Lookahead with capture group
            let re = make_jit_regex(r"(foo)(?=bar)");
            assert!(re.is_match(b"foobar"));
            assert!(!re.is_match(b"foobaz"));
            let caps = re.captures(b"foobar").unwrap();
            assert_eq!(caps[0], Some((0, 3))); // Full match: "foo"
            assert_eq!(caps[1], Some((0, 3))); // Group 1: "foo"
        }

        #[test]
        fn test_nested_backrefs() {
            // Nested capture with backref
            let re = make_jit_regex(r"((a)(b))\1");
            assert!(re.is_match(b"abab"));
            assert!(!re.is_match(b"abba"));
            assert_eq!(re.find(b"abab"), Some((0, 4)));
        }

        #[test]
        fn test_find_at_with_backref() {
            // Test find_at functionality with backref pattern
            let re = make_jit_regex(r"(x)\1");
            // Input: "axxbxx"
            //        012345
            // First match at position 1: "xx"
            // Second match at position 4: "xx"
            let input = b"axxbxx";
            assert_eq!(re.find(input), Some((1, 3)));
        }
    }
}