ferroni 1.5.0

// regexec.rs - Port of regexec.c
// VM executor: bytecode interpreter, match_at, onig_match, onig_search.
//
// This is a 1:1 port of oniguruma's regexec.c (~7,000 LOC).
// Structure mirrors the C original: stack types → stack operations →
// match_at (opcode dispatch) → onig_match → onig_search.

#![allow(non_upper_case_globals)]
#![allow(unused_variables)]
#![allow(unused_assignments)]
#![allow(unused_mut)]

use std::cell::RefCell;
use std::sync::atomic::{AtomicPtr, AtomicU32, AtomicU64, Ordering};
use std::time::Instant;

use crate::oniguruma::*;
use crate::regenc::*;
use crate::regint::*;

/// Callout function type. Receives args and optional user data.
/// Return ONIG_CALLOUT_SUCCESS (0) to continue, ONIG_CALLOUT_FAIL (1) to fail,
/// or a negative error code.
pub type OnigCalloutFunc = fn(args: &OnigCalloutArgs, user_data: *mut std::ffi::c_void) -> i32;

// ============================================================================
// Global Limits (port of C's onig_retry_limit_in_match etc.)
// ============================================================================

static RETRY_LIMIT_IN_MATCH: AtomicU64 = AtomicU64::new(DEFAULT_RETRY_LIMIT_IN_MATCH);
static RETRY_LIMIT_IN_SEARCH: AtomicU64 = AtomicU64::new(DEFAULT_RETRY_LIMIT_IN_SEARCH);
static MATCH_STACK_LIMIT: AtomicU32 = AtomicU32::new(DEFAULT_MATCH_STACK_LIMIT_SIZE);
static TIME_LIMIT: AtomicU64 = AtomicU64::new(DEFAULT_TIME_LIMIT_MSEC);
/// Monotonically changing revision for consumers that cache the four global
/// limits. Setters publish their preceding relaxed limit stores with a Release
/// RMW; an Acquire revision read that observes that change may then reload all
/// four limits relaxed. This avoids four atomic loads on hot searches when no
/// caller has changed a global limit.
static GLOBAL_LIMIT_REVISION: AtomicU64 = AtomicU64::new(0);

#[cfg(test)]
pub(crate) static LIMIT_TEST_LOCK: std::sync::Mutex<()> = std::sync::Mutex::new(());

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_retry_limit_in_match(n: u64) {
    RETRY_LIMIT_IN_MATCH.store(n, Ordering::Relaxed);
    GLOBAL_LIMIT_REVISION.fetch_add(1, Ordering::Release);
}
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_retry_limit_in_match() -> u64 {
    RETRY_LIMIT_IN_MATCH.load(Ordering::Relaxed)
}
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_retry_limit_in_search(n: u64) {
    RETRY_LIMIT_IN_SEARCH.store(n, Ordering::Relaxed);
    GLOBAL_LIMIT_REVISION.fetch_add(1, Ordering::Release);
}
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_retry_limit_in_search() -> u64 {
    RETRY_LIMIT_IN_SEARCH.load(Ordering::Relaxed)
}
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_match_stack_limit(n: u32) {
    MATCH_STACK_LIMIT.store(n, Ordering::Relaxed);
    GLOBAL_LIMIT_REVISION.fetch_add(1, Ordering::Release);
}
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_match_stack_limit() -> u32 {
    MATCH_STACK_LIMIT.load(Ordering::Relaxed)
}

/// Alias for `onig_set_match_stack_limit` (C API compatibility).
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_match_stack_limit_size(n: u32) {
    onig_set_match_stack_limit(n);
}
/// Alias for `onig_get_match_stack_limit` (C API compatibility).
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_match_stack_limit_size() -> u32 {
    onig_get_match_stack_limit()
}
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_time_limit(n: u64) {
    TIME_LIMIT.store(n, Ordering::Relaxed);
    GLOBAL_LIMIT_REVISION.fetch_add(1, Ordering::Release);
}
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_time_limit() -> u64 {
    TIME_LIMIT.load(Ordering::Relaxed)
}

/// Internal revision for caches of the process-global match limits.
#[inline]
pub(crate) fn onig_get_global_limit_revision() -> u64 {
    // Paired with the setters' Release RMWs: if this observes a new
    // revision, following relaxed limit loads see the limits published before
    // it. u64 wrapping is intentionally left to atomic arithmetic; reaching
    // it would require 2^64 process-global limit updates.
    GLOBAL_LIMIT_REVISION.load(Ordering::Acquire)
}

// ============================================================================
// Global Progress/Retraction Callout (port of C's global callout funcs)
// ============================================================================

static PROGRESS_CALLOUT: AtomicPtr<()> = AtomicPtr::new(std::ptr::null_mut());
static RETRACTION_CALLOUT: AtomicPtr<()> = AtomicPtr::new(std::ptr::null_mut());

/// Get the global progress callout function.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_progress_callout() -> Option<OnigCalloutFunc> {
    let p = PROGRESS_CALLOUT.load(Ordering::Relaxed);
    if p.is_null() {
        None
    } else {
        // SAFETY: a non-null pointer in this static was stored by
        // onig_set_progress_callout, which cast an OnigCalloutFunc to
        // *mut (), so the round-trip restores the original fn pointer.
        Some(unsafe { std::mem::transmute::<*mut (), OnigCalloutFunc>(p) })
    }
}

/// Set the global progress callout function.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_progress_callout(f: OnigCalloutFunc) -> i32 {
    let p: *mut () = f as *mut ();
    PROGRESS_CALLOUT.store(p, Ordering::Relaxed);
    ONIG_NORMAL
}

/// Get the global retraction callout function.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_retraction_callout() -> Option<OnigCalloutFunc> {
    let p = RETRACTION_CALLOUT.load(Ordering::Relaxed);
    if p.is_null() {
        None
    } else {
        // SAFETY: a non-null pointer in this static was stored by
        // onig_set_retraction_callout, which cast an OnigCalloutFunc to
        // *mut (), so the round-trip restores the original fn pointer.
        Some(unsafe { std::mem::transmute::<*mut (), OnigCalloutFunc>(p) })
    }
}

/// Set the global retraction callout function.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_retraction_callout(f: OnigCalloutFunc) -> i32 {
    let p: *mut () = f as *mut ();
    RETRACTION_CALLOUT.store(p, Ordering::Relaxed);
    ONIG_NORMAL
}

// ============================================================================
// Global Callback Each Match (port of C's CallbackEachMatch)
// ============================================================================

pub type OnigCallbackEachMatchFunc =
    fn(str_data: &[u8], region: &OnigRegion, user_data: *mut std::ffi::c_void) -> i32;

static CALLBACK_EACH_MATCH: AtomicPtr<()> = AtomicPtr::new(std::ptr::null_mut());

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_callback_each_match() -> Option<OnigCallbackEachMatchFunc> {
    let p = CALLBACK_EACH_MATCH.load(Ordering::Relaxed);
    if p.is_null() {
        None
    } else {
        // SAFETY: a non-null pointer in this static was stored by
        // onig_set_callback_each_match, which cast an
        // OnigCallbackEachMatchFunc to *mut (), so the round-trip restores
        // the original fn pointer.
        Some(unsafe { std::mem::transmute::<*mut (), OnigCallbackEachMatchFunc>(p) })
    }
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_callback_each_match(f: OnigCallbackEachMatchFunc) -> i32 {
    let p: *mut () = f as *mut ();
    CALLBACK_EACH_MATCH.store(p, Ordering::Relaxed);
    ONIG_NORMAL
}

// ============================================================================
// Region Management (port of C's onig_region_* functions)
// ============================================================================

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_region_new() -> OnigRegion {
    OnigRegion::new()
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_region_init(region: &mut OnigRegion) {
    region.init();
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_region_clear(region: &mut OnigRegion) {
    region.clear();
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_region_resize(region: &mut OnigRegion, n: i32) -> i32 {
    region.resize(n);
    ONIG_NORMAL
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_region_set(region: &mut OnigRegion, at: i32, beg: i32, end: i32) -> i32 {
    region.set(at, beg, end)
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_region_copy(to: &mut OnigRegion, from: &OnigRegion) {
    to.copy_from(from);
}

// ============================================================================
// Regex Accessors (port of C's onig_get_*/onig_number_of_* functions)
// ============================================================================

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_encoding(reg: &RegexType) -> OnigEncoding {
    reg.enc
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_options(reg: &RegexType) -> OnigOptionType {
    reg.options
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_case_fold_flag(reg: &RegexType) -> OnigCaseFoldType {
    reg.case_fold_flag
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_syntax(reg: &RegexType) -> &OnigSyntaxType {
    &reg.syntax
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_number_of_captures(reg: &RegexType) -> i32 {
    reg.num_mem
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_number_of_capture_histories(reg: &RegexType) -> i32 {
    let mut n = 0;
    for i in 0..=ONIG_MAX_CAPTURE_HISTORY_GROUP {
        if mem_status_at(reg.capture_history, i) {
            n += 1;
        }
    }
    n
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_capture_tree(region: &OnigRegion) -> Option<&OnigCaptureTreeNode> {
    region.history_root.as_deref()
}

// ============================================================================
// Name Table Queries (port of C's onig_name_to_* / onig_foreach_name)
// ============================================================================

/// Returns the number of group numbers for the given name, and a slice of them.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_name_to_group_numbers<'a>(reg: &'a RegexType, name: &[u8]) -> Result<&'a [i32], i32> {
    if let Some(ref nt) = reg.name_table {
        if let Some(entry) = nt.find(name) {
            Ok(&entry.back_refs)
        } else {
            Err(ONIGERR_UNDEFINED_NAME_REFERENCE)
        }
    } else {
        Err(ONIGERR_UNDEFINED_NAME_REFERENCE)
    }
}

/// Resolve an ambiguous named backref to a single group number using region state.
/// If multiple groups share a name, returns the last one that participated in the match.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_name_to_backref_number(
    reg: &RegexType,
    name: &[u8],
    region: Option<&OnigRegion>,
) -> Result<i32, i32> {
    let nums = onig_name_to_group_numbers(reg, name)?;
    if nums.is_empty() {
        return Err(ONIGERR_PARSER_BUG);
    }
    if nums.len() == 1 {
        return Ok(nums[0]);
    }
    // Multiple groups share this name — pick the last one that matched
    if let Some(region) = region {
        for i in (0..nums.len()).rev() {
            let idx = nums[i] as usize;
            if idx < region.beg.len() && region.beg[idx] != ONIG_REGION_NOTPOS {
                return Ok(nums[i]);
            }
        }
    }
    Ok(nums[nums.len() - 1])
}

/// Iterate over all name entries. Callback receives (name, back_refs).
/// If callback returns non-zero, iteration stops and that value is returned.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_foreach_name<F>(reg: &RegexType, mut callback: F) -> i32
where
    F: FnMut(&[u8], &[i32]) -> i32,
{
    if let Some(ref nt) = reg.name_table {
        for entry in nt.entries.values() {
            let r = callback(&entry.name, &entry.back_refs);
            if r != 0 {
                return r;
            }
        }
    }
    ONIG_NORMAL
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_number_of_names(reg: &RegexType) -> i32 {
    if let Some(ref nt) = reg.name_table {
        nt.entries.len() as i32
    } else {
        0
    }
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_noname_group_capture_is_active(reg: &RegexType) -> bool {
    if opton_dont_capture_group(reg.options) {
        return false;
    }
    if onig_number_of_names(reg) > 0 {
        if is_syntax_bv(&reg.syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP)
            && !opton_capture_group(reg.options)
        {
            return false;
        }
    }
    true
}

// ============================================================================
// Utility + Version (port of regversion.c + regexec.c globals)
// ============================================================================

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_version() -> &'static str {
    "6.9.10"
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_copyright() -> &'static str {
    "Oniguruma 6.9.10 : Copyright (C) 2002-2024 K.Kosako"
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_init() -> i32 {
    ONIG_NORMAL
}
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_initialize() -> i32 {
    ONIG_NORMAL
}
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_end() -> i32 {
    ONIG_NORMAL
}

static SUBEXP_CALL_LIMIT_IN_SEARCH: AtomicU64 = AtomicU64::new(DEFAULT_SUBEXP_CALL_LIMIT_IN_SEARCH);
static SUBEXP_CALL_MAX_NEST_LEVEL: AtomicU32 =
    AtomicU32::new(DEFAULT_SUBEXP_CALL_MAX_NEST_LEVEL as u32);

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_subexp_call_limit_in_search() -> u64 {
    SUBEXP_CALL_LIMIT_IN_SEARCH.load(Ordering::Relaxed)
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_subexp_call_limit_in_search(n: u64) -> i32 {
    SUBEXP_CALL_LIMIT_IN_SEARCH.store(n, Ordering::Relaxed);
    ONIG_NORMAL
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_subexp_call_max_nest_level() -> i32 {
    SUBEXP_CALL_MAX_NEST_LEVEL.load(Ordering::Relaxed) as i32
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_subexp_call_max_nest_level(level: i32) -> i32 {
    SUBEXP_CALL_MAX_NEST_LEVEL.store(level as u32, Ordering::Relaxed);
    ONIG_NORMAL
}

/// Scan for all non-overlapping matches of `reg` in `str_data`.
/// For each match, calls `callback(match_count, match_position, region)`.
/// If callback returns non-zero, scanning stops and that value is returned.
/// Otherwise returns the total number of matches found.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_scan<F>(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    region: OnigRegion,
    option: OnigOptionType,
    mut callback: F,
) -> (i32, OnigRegion)
where
    F: FnMut(i32, i32, &OnigRegion) -> i32,
{
    let enc = reg.enc;
    let mut n: i32 = 0;
    let mut start = 0usize;
    let mut region = region;
    let mut option = option;

    if opton_check_validity_of_string(option) {
        if !enc.is_valid_mbc_string(&str_data[..end]) {
            return (ONIGERR_INVALID_WIDE_CHAR_VALUE, region);
        }
        option &= !ONIG_OPTION_CHECK_VALIDITY_OF_STRING;
    }

    loop {
        let (r, returned_region) =
            onig_search(reg, str_data, end, start, end, Some(region), option);
        region = returned_region.unwrap_or_else(OnigRegion::new);

        if r >= 0 {
            let rs = callback(n, r, &region);
            n += 1;
            if rs != 0 {
                return (rs, region);
            }
            if region.num_regs > 0 && region.end[0] == start as i32 {
                if start >= end {
                    break;
                }
                start += enclen(enc, str_data, start);
            } else if region.num_regs > 0 {
                start = region.end[0] as usize;
            } else {
                break;
            }
            if start > end {
                break;
            }
        } else if r == ONIG_MISMATCH {
            break;
        } else {
            // error
            return (r, region);
        }
    }

    (n, region)
}

// ============================================================================
// OnigMatchParam (per-search limit overrides)
// ============================================================================

pub struct OnigMatchParam {
    pub match_stack_limit: u32,
    pub retry_limit_in_match: u64,
    pub retry_limit_in_search: u64,
    pub time_limit: u64,
    pub progress_callout: Option<OnigCalloutFunc>,
    pub retraction_callout: Option<OnigCalloutFunc>,
    pub callout_user_data: *mut std::ffi::c_void,
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_new_match_param() -> OnigMatchParam {
    let mut mp = OnigMatchParam {
        match_stack_limit: 0,
        retry_limit_in_match: 0,
        retry_limit_in_search: 0,
        time_limit: 0,
        progress_callout: None,
        retraction_callout: None,
        callout_user_data: std::ptr::null_mut(),
    };
    onig_initialize_match_param(&mut mp);
    mp
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_initialize_match_param(mp: &mut OnigMatchParam) -> i32 {
    mp.match_stack_limit = MATCH_STACK_LIMIT.load(Ordering::Relaxed);
    mp.retry_limit_in_match = RETRY_LIMIT_IN_MATCH.load(Ordering::Relaxed);
    mp.retry_limit_in_search = RETRY_LIMIT_IN_SEARCH.load(Ordering::Relaxed);
    mp.time_limit = TIME_LIMIT.load(Ordering::Relaxed);
    mp.progress_callout = onig_get_progress_callout();
    mp.retraction_callout = onig_get_retraction_callout();
    mp.callout_user_data = std::ptr::null_mut();
    ONIG_NORMAL
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_match_stack_limit_size_of_match_param(mp: &mut OnigMatchParam, limit: u32) -> i32 {
    mp.match_stack_limit = limit;
    ONIG_NORMAL
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_retry_limit_in_match_of_match_param(mp: &mut OnigMatchParam, limit: u64) -> i32 {
    mp.retry_limit_in_match = limit;
    ONIG_NORMAL
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_retry_limit_in_search_of_match_param(mp: &mut OnigMatchParam, limit: u64) -> i32 {
    mp.retry_limit_in_search = limit;
    ONIG_NORMAL
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_time_limit_of_match_param(mp: &mut OnigMatchParam, limit: u64) -> i32 {
    mp.time_limit = limit;
    ONIG_NORMAL
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_progress_callout_of_match_param(
    mp: &mut OnigMatchParam,
    f: Option<OnigCalloutFunc>,
) -> i32 {
    mp.progress_callout = f;
    ONIG_NORMAL
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_retraction_callout_of_match_param(
    mp: &mut OnigMatchParam,
    f: Option<OnigCalloutFunc>,
) -> i32 {
    mp.retraction_callout = f;
    ONIG_NORMAL
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_callout_user_data_of_match_param(
    mp: &mut OnigMatchParam,
    user_data: *mut std::ffi::c_void,
) -> i32 {
    mp.callout_user_data = user_data;
    ONIG_NORMAL
}

// ============================================================================
// OnigCalloutArgs (port of C's OnigCalloutArgsStruct)
// ============================================================================

/// Callout arguments passed to callout functions.
/// Provides access to match state at the point of the callout.
pub struct OnigCalloutArgs {
    pub callout_in: OnigCalloutIn,
    pub name_id: i32,
    pub num: i32,
    pub regex: *const RegexType,
    pub string: *const u8,
    pub string_end: *const u8,
    pub start: *const u8,
    pub right_range: *const u8,
    pub current: *const u8,
    pub retry_in_match_counter: u64,
    // String data for safe access
    str_data: *const u8,
    str_len: usize,
    // Callout data array (for by_callout_args accessor functions)
    pub(crate) callout_data: *mut Vec<[i64; ONIG_CALLOUT_DATA_SLOT_NUM]>,
    // Pointer to MatchArg for builtins that need to write back (e.g. SKIP)
    pub(crate) msa: *mut MatchArg,
}

impl OnigCalloutArgs {
    #[cfg_attr(coverage_nightly, coverage(off))]
    #[allow(clippy::too_many_arguments)]
    pub(crate) fn new(
        callout_in: OnigCalloutIn,
        name_id: i32,
        num: i32,
        reg: &RegexType,
        str_data: &[u8],
        end: usize,
        start: usize,
        right_range: usize,
        current: usize,
        retry_counter: u64,
    ) -> Self {
        OnigCalloutArgs {
            callout_in,
            name_id,
            num,
            regex: reg as *const RegexType,
            string: str_data.as_ptr(),
            // SAFETY: the match engine passes `end` as the subject length in
            // bytes (end <= str_data.len()), so the offset stays inside or
            // one past the end of the `str_data` allocation.
            string_end: unsafe { str_data.as_ptr().add(end) },
            // SAFETY: the match engine passes `start` as a byte offset into
            // the subject (start <= str_data.len()), so the offset stays
            // inside or one past the end of the `str_data` allocation.
            start: unsafe { str_data.as_ptr().add(start) },
            // SAFETY: the match engine passes `right_range` as a byte offset
            // into the subject (right_range <= str_data.len()), so the offset
            // stays inside or one past the end of the `str_data` allocation.
            right_range: unsafe { str_data.as_ptr().add(right_range) },
            // SAFETY: the match engine passes `current` as a byte offset into
            // the subject (current <= str_data.len()), so the offset stays
            // inside or one past the end of the `str_data` allocation.
            current: unsafe { str_data.as_ptr().add(current) },
            retry_in_match_counter: retry_counter,
            str_data: str_data.as_ptr(),
            str_len: str_data.len(),
            callout_data: std::ptr::null_mut(),
            msa: std::ptr::null_mut(),
        }
    }
}

// --- OnigCalloutArgs accessor functions ---

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_callout_num_by_callout_args(args: &OnigCalloutArgs) -> i32 {
    args.num
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_callout_in_by_callout_args(args: &OnigCalloutArgs) -> OnigCalloutIn {
    args.callout_in
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_name_id_by_callout_args(args: &OnigCalloutArgs) -> i32 {
    args.name_id
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_contents_by_callout_args(_args: &OnigCalloutArgs) -> Option<&[u8]> {
    // Contents of (?{...}) callouts are not stored in CalloutListEntry
    // in the current implementation. Returns None.
    None
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_args_num_by_callout_args(args: &OnigCalloutArgs) -> i32 {
    // SAFETY: args.regex was set in OnigCalloutArgs::new from a `&RegexType`
    // that the match engine keeps borrowed for as long as it hands these args
    // to callout functions, so the pointer is valid and aligned here.
    let reg = unsafe { &*args.regex };
    if let Some(ref ext) = reg.extp {
        let idx = (args.num - 1) as usize;
        if idx < ext.callout_list.len() {
            return ext.callout_list[idx].args.len() as i32;
        }
    }
    0
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_passed_args_num_by_callout_args(args: &OnigCalloutArgs) -> i32 {
    // SAFETY: args.regex was set in OnigCalloutArgs::new from a `&RegexType`
    // that the match engine keeps borrowed for as long as it hands these args
    // to callout functions, so the pointer is valid and aligned here.
    let reg = unsafe { &*args.regex };
    if let Some(ref ext) = reg.extp {
        let idx = (args.num - 1) as usize;
        if idx < ext.callout_list.len() {
            return ext.callout_list[idx].args.len() as i32;
        }
    }
    0
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_arg_by_callout_args(args: &OnigCalloutArgs, index: i32) -> Option<&CalloutArg> {
    // SAFETY: args.regex was set in OnigCalloutArgs::new from a `&RegexType`
    // that the match engine keeps borrowed for as long as it hands these args
    // to callout functions, so the pointer is valid and aligned here.
    let reg = unsafe { &*args.regex };
    if let Some(ref ext) = reg.extp {
        let idx = (args.num - 1) as usize;
        if idx < ext.callout_list.len() {
            let entry = &ext.callout_list[idx];
            if (index as usize) < entry.args.len() {
                return Some(&entry.args[index as usize]);
            }
        }
    }
    None
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_string_by_callout_args(args: &OnigCalloutArgs) -> *const u8 {
    args.string
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_string_end_by_callout_args(args: &OnigCalloutArgs) -> *const u8 {
    args.string_end
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_start_by_callout_args(args: &OnigCalloutArgs) -> *const u8 {
    args.start
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_right_range_by_callout_args(args: &OnigCalloutArgs) -> *const u8 {
    args.right_range
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_current_by_callout_args(args: &OnigCalloutArgs) -> *const u8 {
    args.current
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_regex_by_callout_args(args: &OnigCalloutArgs) -> *const RegexType {
    args.regex
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_retry_counter_by_callout_args(args: &OnigCalloutArgs) -> u64 {
    args.retry_in_match_counter
}

/// Get the end position of callout contents.
/// For content callouts (?{...}), returns the end pointer of the content.
/// Returns null for name callouts.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_contents_end_by_callout_args(args: &OnigCalloutArgs) -> *const u8 {
    // SAFETY: args.regex was set in OnigCalloutArgs::new from a `&RegexType`
    // that the match engine keeps borrowed for as long as it hands these args
    // to callout functions, so the pointer is valid and aligned here.
    let reg = unsafe { &*args.regex };
    if let Some(ref ext) = reg.extp {
        let idx = (args.num - 1) as usize;
        if idx < ext.callout_list.len() {
            let entry = &ext.callout_list[idx];
            if entry.of == OnigCalloutOf::Contents as i32 {
                if let Some(ref content_end) = entry.content_end {
                    return content_end.as_ptr();
                }
            }
        }
    }
    std::ptr::null()
}

// ============================================================================
// Callout Data Access (port of C's onig_get/set_callout_data)
// ============================================================================

/// Get callout data from a callout's data slot.
/// `callout_num` is 1-based, `slot` ranges 0..ONIG_CALLOUT_DATA_SLOT_NUM.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_callout_data(
    reg: &RegexType,
    callout_data: &[[i64; ONIG_CALLOUT_DATA_SLOT_NUM]],
    callout_num: i32,
    slot: i32,
) -> Option<i64> {
    if callout_num < 1 || slot < 0 || slot >= ONIG_CALLOUT_DATA_SLOT_NUM as i32 {
        return None;
    }
    let idx = (callout_num - 1) as usize;
    if idx >= callout_data.len() {
        return None;
    }
    Some(callout_data[idx][slot as usize])
}

/// Set callout data in a callout's data slot.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_callout_data(
    callout_data: &mut [[i64; ONIG_CALLOUT_DATA_SLOT_NUM]],
    callout_num: i32,
    slot: i32,
    val: i64,
) -> i32 {
    if callout_num < 1 || slot < 0 || slot >= ONIG_CALLOUT_DATA_SLOT_NUM as i32 {
        return ONIGERR_INVALID_ARGUMENT;
    }
    let idx = (callout_num - 1) as usize;
    if idx >= callout_data.len() {
        return ONIGERR_INVALID_ARGUMENT;
    }
    callout_data[idx][slot as usize] = val;
    ONIG_NORMAL
}

// ============================================================================
// Callout Tag Query Functions
// ============================================================================

/// Get the callout number for a given tag in the regex - mirrors C's
/// onig_get_callout_num_by_tag(), which reports an unknown tag as
/// ONIGERR_INVALID_CALLOUT_TAG_NAME.
pub fn onig_get_callout_num_by_tag(reg: &RegexType, tag: &[u8]) -> i32 {
    if let Some(ref ext) = reg.extp {
        if let Some(ref table) = ext.tag_table {
            if let Some(&num) = table.get(tag) {
                return num;
            }
        }
    }
    ONIGERR_INVALID_CALLOUT_TAG_NAME
}

/// Check if a callout has a tag.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_callout_tag_is_exist_at_callout_num(reg: &RegexType, callout_num: i32) -> bool {
    if let Some(ref ext) = reg.extp {
        let idx = (callout_num - 1) as usize;
        if idx < ext.callout_list.len() {
            return ext.callout_list[idx].tag.is_some();
        }
    }
    false
}

/// Get the tag for a given callout number.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_callout_tag(reg: &RegexType, callout_num: i32) -> Option<&[u8]> {
    if let Some(ref ext) = reg.extp {
        let idx = (callout_num - 1) as usize;
        if idx < ext.callout_list.len() {
            return ext.callout_list[idx].tag.as_deref();
        }
    }
    None
}

/// Get the byte offset of the tag start in the pattern for a given callout number.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_callout_tag_start(reg: &RegexType, callout_num: i32) -> Option<usize> {
    if let Some(ref ext) = reg.extp {
        let idx = (callout_num - 1) as usize;
        if idx < ext.callout_list.len() && ext.callout_list[idx].tag.is_some() {
            return Some(ext.callout_list[idx].tag_start);
        }
    }
    None
}

/// Get the byte offset of the tag end in the pattern for a given callout number.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_callout_tag_end(reg: &RegexType, callout_num: i32) -> Option<usize> {
    if let Some(ref ext) = reg.extp {
        let idx = (callout_num - 1) as usize;
        if idx < ext.callout_list.len() && ext.callout_list[idx].tag.is_some() {
            return Some(ext.callout_list[idx].tag_end);
        }
    }
    None
}

// ============================================================================
// Callout Data by_callout_args variants
// (port of C's onig_get/set_callout_data_by_callout_args*)
// ============================================================================

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_callout_data_by_callout_args(
    args: &OnigCalloutArgs,
    callout_num: i32,
    slot: i32,
) -> Option<i64> {
    // SAFETY: args.regex was set in OnigCalloutArgs::new from a `&RegexType`
    // that the match engine keeps borrowed for as long as it hands these args
    // to callout functions, so the pointer is valid and aligned here.
    let reg = unsafe { &*args.regex };
    if args.callout_data.is_null() {
        return None;
    }
    // SAFETY: non-null was checked above. Whoever stores a non-null
    // callout_data must point it at the match engine's live callout-data
    // vector and hold no mutable reference to it while the callout runs, so
    // the shared borrow is sound for the duration of this call.
    let cd = unsafe { &*args.callout_data };
    onig_get_callout_data(reg, cd, callout_num, slot)
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_callout_data_by_callout_args(
    args: &OnigCalloutArgs,
    callout_num: i32,
    slot: i32,
    val: i64,
) -> i32 {
    if args.callout_data.is_null() {
        return ONIGERR_INVALID_ARGUMENT;
    }
    // SAFETY: non-null was checked above. Whoever stores a non-null
    // callout_data must point it at the match engine's live callout-data
    // vector and hold no other reference to it while the callout runs, so
    // the unique borrow is sound for the duration of this call.
    let cd = unsafe { &mut *args.callout_data };
    onig_set_callout_data(cd, callout_num, slot, val)
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_callout_data_by_callout_args_self(
    args: &OnigCalloutArgs,
    slot: i32,
) -> Option<i64> {
    onig_get_callout_data_by_callout_args(args, args.num, slot)
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_callout_data_by_callout_args_self(
    args: &OnigCalloutArgs,
    slot: i32,
    val: i64,
) -> i32 {
    onig_set_callout_data_by_callout_args(args, args.num, slot, val)
}

/// Get callout data without clearing old values.
/// In the Rust implementation, this behaves identically to onig_get_callout_data
/// since the Rust version does not implement the clear-on-access pattern.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_callout_data_dont_clear_old(
    reg: &RegexType,
    callout_data: &[[i64; ONIG_CALLOUT_DATA_SLOT_NUM]],
    callout_num: i32,
    slot: i32,
) -> Option<i64> {
    onig_get_callout_data(reg, callout_data, callout_num, slot)
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_callout_data_by_callout_args_self_dont_clear_old(
    args: &OnigCalloutArgs,
    slot: i32,
) -> Option<i64> {
    onig_get_callout_data_by_callout_args_self(args, slot)
}

/// Get callout data by tag name.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_callout_data_by_tag(
    reg: &RegexType,
    callout_data: &[[i64; ONIG_CALLOUT_DATA_SLOT_NUM]],
    tag: &[u8],
    slot: i32,
) -> Option<i64> {
    let num = onig_get_callout_num_by_tag(reg, tag);
    if num < 1 {
        return None;
    }
    onig_get_callout_data(reg, callout_data, num, slot)
}

/// Set callout data by tag name.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_callout_data_by_tag(
    reg: &RegexType,
    callout_data: &mut [[i64; ONIG_CALLOUT_DATA_SLOT_NUM]],
    tag: &[u8],
    slot: i32,
    val: i64,
) -> i32 {
    let num = onig_get_callout_num_by_tag(reg, tag);
    if num < 1 {
        return ONIGERR_INVALID_CALLOUT_TAG_NAME;
    }
    onig_set_callout_data(callout_data, num, slot, val)
}

/// Get callout data by tag name without clearing old values.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_callout_data_by_tag_dont_clear_old(
    reg: &RegexType,
    callout_data: &[[i64; ONIG_CALLOUT_DATA_SLOT_NUM]],
    tag: &[u8],
    slot: i32,
) -> Option<i64> {
    onig_get_callout_data_by_tag(reg, callout_data, tag, slot)
}

// ============================================================================
// Callout Introspection
// (port of C's onig_get_capture_range_in_callout, onig_get_used_stack_size_in_callout)
// ============================================================================

/// Get the capture range for a given memory number during a callout.
/// Returns (begin, end) byte offsets, or ONIG_REGION_NOTPOS if not matched.
///
/// Note: This function requires OnigCalloutArgs to be constructed with stack
/// state from the VM. Currently only available when user callout functions are
/// called from within the match execution.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_capture_range_in_callout(
    _args: &OnigCalloutArgs,
    mem_num: i32,
) -> Result<(i32, i32), i32> {
    if mem_num <= 0 {
        return Err(ONIGERR_INVALID_ARGUMENT);
    }
    // Stack-based capture tracking not yet exposed through OnigCalloutArgs.
    // Returns NOTPOS for now.
    Ok((ONIG_REGION_NOTPOS, ONIG_REGION_NOTPOS))
}

/// Get the current used stack size during a callout.
/// Returns (used_num, used_bytes).
///
/// Note: This function requires OnigCalloutArgs to be constructed with stack
/// state from the VM.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_used_stack_size_in_callout(_args: &OnigCalloutArgs) -> (i32, i32) {
    // Stack size tracking not yet exposed through OnigCalloutArgs.
    (0, 0)
}

// ============================================================================
// Builtin Callout Public API
// (port of C's onig_builtin_fail, onig_builtin_mismatch, etc.)
// ============================================================================

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_builtin_fail(_args: &OnigCalloutArgs, _user_data: *mut std::ffi::c_void) -> i32 {
    ONIG_CALLOUT_FAIL
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_builtin_mismatch(_args: &OnigCalloutArgs, _user_data: *mut std::ffi::c_void) -> i32 {
    ONIG_MISMATCH
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_builtin_error(args: &OnigCalloutArgs, _user_data: *mut std::ffi::c_void) -> i32 {
    // SAFETY: args.regex was set in OnigCalloutArgs::new from a `&RegexType`
    // that the match engine keeps borrowed for as long as it hands these args
    // to callout functions, so the pointer is valid and aligned here.
    let reg = unsafe { &*args.regex };
    if let Some(ref ext) = reg.extp {
        let idx = (args.num - 1) as usize;
        if idx < ext.callout_list.len() {
            let entry = &ext.callout_list[idx];
            if !entry.args.is_empty() {
                if let CalloutArg::Long(n) = &entry.args[0] {
                    let n = *n as i32;
                    if n >= 0 {
                        return ONIGERR_INVALID_CALLOUT_BODY;
                    }
                    return n;
                }
            }
        }
    }
    ONIGERR_INVALID_CALLOUT_BODY
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_builtin_count(args: &OnigCalloutArgs, _user_data: *mut std::ffi::c_void) -> i32 {
    if args.callout_data.is_null() {
        return ONIG_CALLOUT_FAIL;
    }
    // SAFETY: non-null was checked above. Whoever stores a non-null
    // callout_data must point it at the match engine's live callout-data
    // vector and hold no other reference to it while the callout runs, so
    // the unique borrow is sound for the duration of this call.
    let cd = unsafe { &mut *args.callout_data };
    let num = args.num;
    if num < 1 {
        return ONIG_CALLOUT_FAIL;
    }
    let idx = (num - 1) as usize;
    if idx >= cd.len() {
        return ONIG_CALLOUT_FAIL;
    }

    // SAFETY: args.regex was set in OnigCalloutArgs::new from a `&RegexType`
    // that the match engine keeps borrowed for as long as it hands these args
    // to callout functions, so the pointer is valid and aligned here.
    let reg = unsafe { &*args.regex };
    let count_type = if let Some(ref ext) = reg.extp {
        if idx < ext.callout_list.len() && !ext.callout_list[idx].args.is_empty() {
            match &ext.callout_list[idx].args[0] {
                CalloutArg::Char(c) => *c,
                _ => b'>',
            }
        } else {
            b'>'
        }
    } else {
        b'>'
    };

    let is_retraction = args.callout_in == OnigCalloutIn::Retraction;
    let slots = &mut cd[idx];

    if is_retraction {
        if count_type == b'<' {
            slots[0] += 1;
        } else if count_type == b'X' {
            slots[0] -= 1;
        }
        slots[2] += 1;
    } else {
        if count_type != b'<' {
            slots[0] += 1;
        }
        slots[1] += 1;
    }

    ONIG_CALLOUT_SUCCESS
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_builtin_total_count(args: &OnigCalloutArgs, _user_data: *mut std::ffi::c_void) -> i32 {
    // total_count is the same as count but without clearing old data.
    // In Rust, count already doesn't clear old data, so they are equivalent.
    onig_builtin_count(args, _user_data)
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_builtin_max(args: &OnigCalloutArgs, _user_data: *mut std::ffi::c_void) -> i32 {
    if args.callout_data.is_null() {
        return ONIG_CALLOUT_FAIL;
    }
    // SAFETY: non-null was checked above. Whoever stores a non-null
    // callout_data must point it at the match engine's live callout-data
    // vector and hold no other reference to it while the callout runs, so
    // the unique borrow is sound for the duration of this call.
    let cd = unsafe { &mut *args.callout_data };
    let num = args.num;
    if num < 1 {
        return ONIG_CALLOUT_FAIL;
    }
    let idx = (num - 1) as usize;
    if idx >= cd.len() {
        return ONIG_CALLOUT_FAIL;
    }

    // SAFETY: args.regex was set in OnigCalloutArgs::new from a `&RegexType`
    // that the match engine keeps borrowed for as long as it hands these args
    // to callout functions, so the pointer is valid and aligned here.
    let reg = unsafe { &*args.regex };
    let ext = match reg.extp.as_ref() {
        Some(e) => e,
        None => return ONIG_CALLOUT_FAIL,
    };
    if idx >= ext.callout_list.len() {
        return ONIG_CALLOUT_FAIL;
    }
    let entry = &ext.callout_list[idx];

    let max_val = if !entry.args.is_empty() {
        resolve_callout_arg(&entry.args[0], &ext.callout_list, cd)
    } else {
        0
    };

    let count_type = if entry.args.len() > 1 {
        match &entry.args[1] {
            CalloutArg::Char(c) => *c,
            _ => b'>',
        }
    } else {
        b'>'
    };

    let is_retraction = args.callout_in == OnigCalloutIn::Retraction;
    let slots = &mut cd[idx];

    if is_retraction {
        if count_type == b'<' {
            if slots[0] >= max_val {
                return ONIG_CALLOUT_FAIL;
            }
            slots[0] += 1;
        } else if count_type == b'X' {
            slots[0] -= 1;
        }
    } else {
        if count_type != b'<' {
            if slots[0] >= max_val {
                return ONIG_CALLOUT_FAIL;
            }
            slots[0] += 1;
        }
    }

    ONIG_CALLOUT_SUCCESS
}

/// Built-in SKIP callout. When a match fails, the search loop advances
/// to at least the position recorded by SKIP, avoiding redundant attempts.
/// Port of C's onig_builtin_skip (regexec.c:6642-6648).
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_builtin_skip(args: &OnigCalloutArgs, _user_data: *mut std::ffi::c_void) -> i32 {
    if args.callout_in == OnigCalloutIn::Retraction {
        return ONIG_CALLOUT_SUCCESS;
    }

    let current = if args.str_data.is_null() {
        0
    } else {
        // SAFETY: `current` was computed in OnigCalloutArgs::new as
        // `str_data.as_ptr().add(current)` from the same base pointer that
        // was stored in `str_data`, so both pointers lie within the same
        // allocation and current >= str_data; the offset is therefore valid
        // and non-negative.
        unsafe { args.current.offset_from(args.str_data) as usize }
    };

    if !args.msa.is_null() {
        // SAFETY: non-null was checked above. Whoever stores a non-null msa
        // must point it at the MatchArg of the match in progress, kept alive
        // and otherwise unreferenced by the match engine while the callout
        // runs, so the unique borrow is sound for the duration of this call.
        let msa = unsafe { &mut *args.msa };
        if current > msa.skip_search {
            msa.skip_search = current;
        }
    }

    ONIG_CALLOUT_SUCCESS
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_builtin_cmp(args: &OnigCalloutArgs, _user_data: *mut std::ffi::c_void) -> i32 {
    if args.callout_data.is_null() {
        return ONIG_CALLOUT_FAIL;
    }
    // SAFETY: non-null was checked above. Whoever stores a non-null
    // callout_data must point it at the match engine's live callout-data
    // vector and hold no other reference to it while the callout runs, so
    // the unique borrow is sound for the duration of this call.
    let cd = unsafe { &mut *args.callout_data };
    let num = args.num;
    if num < 1 {
        return ONIG_CALLOUT_FAIL;
    }
    let idx = (num - 1) as usize;
    if idx >= cd.len() {
        return ONIG_CALLOUT_FAIL;
    }

    // SAFETY: args.regex was set in OnigCalloutArgs::new from a `&RegexType`
    // that the match engine keeps borrowed for as long as it hands these args
    // to callout functions, so the pointer is valid and aligned here.
    let reg = unsafe { &*args.regex };
    let ext = match reg.extp.as_ref() {
        Some(e) => e,
        None => return ONIG_CALLOUT_FAIL,
    };
    if idx >= ext.callout_list.len() || ext.callout_list[idx].args.len() < 3 {
        return ONIG_CALLOUT_FAIL;
    }
    let entry = &ext.callout_list[idx];

    let lv = resolve_callout_arg(&entry.args[0], &ext.callout_list, cd);
    let rv = resolve_callout_arg(&entry.args[2], &ext.callout_list, cd);

    // The op is stored in slot 0 after first parse; or read from args[1]
    let op = cd[idx][0];
    if op == 0 {
        // First call: parse the op string from args[1]
        let op_val = match &entry.args[1] {
            CalloutArg::Str(s) => {
                if s == b"==" {
                    1
                } else if s == b"!=" {
                    2
                } else if s == b"<" {
                    3
                } else if s == b">" {
                    4
                } else if s == b"<=" {
                    5
                } else if s == b">=" {
                    6
                } else {
                    return ONIGERR_INVALID_CALLOUT_ARG;
                }
            }
            _ => return ONIGERR_INVALID_CALLOUT_ARG,
        };
        cd[idx][0] = op_val;
        let result = match op_val {
            1 => lv == rv,
            2 => lv != rv,
            3 => lv < rv,
            4 => lv > rv,
            5 => lv <= rv,
            6 => lv >= rv,
            _ => false,
        };
        if result {
            ONIG_CALLOUT_SUCCESS
        } else {
            ONIG_CALLOUT_FAIL
        }
    } else {
        let result = match op {
            1 => lv == rv,
            2 => lv != rv,
            3 => lv < rv,
            4 => lv > rv,
            5 => lv <= rv,
            6 => lv >= rv,
            _ => false,
        };
        if result {
            ONIG_CALLOUT_SUCCESS
        } else {
            ONIG_CALLOUT_FAIL
        }
    }
}

// ============================================================================
// Stack Types (port of StackType / STK_* constants)
// ============================================================================

/// Memory pointer - tracks capture group start/end positions.
/// Compact representation of C's StkPtrType union { StackIndex i; UChar* s; }
///
/// Encodes three states in a single `usize` to minimize StackEntry size:
/// - `usize::MAX` = Invalid (not yet matched)
/// - Bit 63 set = stack index (lower 63 bits)
/// - Bit 63 clear = string position
#[derive(Clone, Copy, Debug)]
struct MemPtr(usize);

const MEM_PTR_INVALID: usize = usize::MAX;
const MEM_PTR_STACK_BIT: usize = 1 << (usize::BITS - 1);

impl MemPtr {
    #[inline(always)]
    const fn invalid() -> Self {
        MemPtr(MEM_PTR_INVALID)
    }

    #[inline(always)]
    const fn pos(p: usize) -> Self {
        MemPtr(p)
    }

    #[inline(always)]
    const fn stack_idx(i: usize) -> Self {
        MemPtr(i | MEM_PTR_STACK_BIT)
    }

    #[inline(always)]
    const fn is_invalid(self) -> bool {
        self.0 == MEM_PTR_INVALID
    }

    #[inline(always)]
    const fn is_stack_idx(self) -> bool {
        !self.is_invalid() && (self.0 & MEM_PTR_STACK_BIT) != 0
    }

    #[inline(always)]
    const fn as_pos(self) -> Option<usize> {
        if self.is_invalid() || (self.0 & MEM_PTR_STACK_BIT) != 0 {
            None
        } else {
            Some(self.0)
        }
    }

    #[inline(always)]
    const fn as_stack_idx(self) -> Option<usize> {
        if self.is_stack_idx() {
            Some(self.0 & !MEM_PTR_STACK_BIT)
        } else {
            None
        }
    }
}

/// Stack entry - corresponds to C's StackType struct.
/// Uses enum to distinguish entry types instead of C's type field + union.
#[derive(Clone)]
enum StackEntry {
    /// Choice point (STK_ALT / STK_SUPER_ALT) - alternate path for backtracking.
    Alt {
        pcode: usize,   // bytecode index to jump to on backtrack
        pstr: usize,    // string position to restore
        zid: i32,       // remaining count for StepBackNext (-1 = unused)
        is_super: bool, // true for SUPER_ALT (survives CutToMark)
    },
    /// Capture group start (STK_MEM_START)
    MemStart {
        zid: usize,
        pstr: usize,
        prev_start: MemPtr,
        prev_end: MemPtr,
    },
    /// Capture group end (STK_MEM_END)
    MemEnd {
        zid: usize,
        pstr: usize,
        prev_start: MemPtr,
        prev_end: MemPtr,
    },
    /// Capture group end marker (STK_MEM_END_MARK) - for recursive groups
    MemEndMark { zid: usize },
    /// Repeat counter (STK_REPEAT_INC)
    RepeatInc { zid: usize, count: i32 },
    /// Empty check start marker (STK_EMPTY_CHECK_START)
    EmptyCheckStart { zid: usize, pstr: usize },
    /// Empty check end marker (STK_EMPTY_CHECK_END)
    EmptyCheckEnd { zid: usize },
    /// Named checkpoint (STK_MARK) - for lookaheads/lookbehinds
    Mark {
        zid: usize,
        pos: Option<usize>, // saved string position (if save_pos)
    },
    /// Saved value (STK_SAVE_VAL)
    SaveVal {
        zid: usize,
        save_type: SaveType,
        v: usize,
    },
    /// Call frame return address (STK_CALL_FRAME)
    CallFrame { ret_addr: usize },
    /// Return marker (STK_RETURN)
    Return,
    /// Callout entry (STK_CALLOUT) - for retraction callbacks
    Callout {
        num: i32, // callout list index (1-based)
        id: i32,  // builtin id (for name callouts) or ONIG_NON_NAME_ID
    },
    /// Lazy choice point for star opcodes - represents a range of backtrack positions.
    /// Instead of pushing one Alt per matched character, we push a single AltLazy
    /// covering the entire matched range. On backtrack, we peel off one character
    /// and re-push for the remaining range.
    AltLazy {
        pcode: usize,      // bytecode index to jump to on backtrack
        pstr: usize,       // current (rightmost) backtrack position
        pstr_start: usize, // leftmost position (don't go below this)
        ascii: bool,       // true = all chars are 1 byte (can decrement by 1)
        peek_byte: u8,     // if non-zero, only try positions where str_data[pos] == peek_byte
    },
    /// Voided entry (STK_VOID) - dead space, skipped during pops
    Void,
}

impl StackEntry {
    /// Returns true if this entry is an ALT (choice point) that stops STACK_POP.
    #[inline]
    #[cfg_attr(coverage_nightly, coverage(off))]
    fn is_alt(&self) -> bool {
        matches!(self, StackEntry::Alt { .. } | StackEntry::AltLazy { .. })
    }

    /// Returns true if this entry needs handling during pop at ALL level.
    #[inline]
    #[cfg_attr(coverage_nightly, coverage(off))]
    fn is_pop_handled(&self) -> bool {
        matches!(
            self,
            StackEntry::MemStart { .. }
                | StackEntry::MemEnd { .. }
                | StackEntry::RepeatInc { .. }
                | StackEntry::EmptyCheckStart { .. }
                | StackEntry::CallFrame { .. }
                | StackEntry::Return
        )
    }
}

// Sentinel value for the bottom ALT entry's pcode
const FINISH_PCODE: usize = usize::MAX;

// ============================================================================
// MatchArg - runtime match state (port of C's MatchArg)
// ============================================================================

pub struct MatchArg {
    pub options: OnigOptionType,
    pub region: Option<OnigRegion>,
    pub start: usize, // search start position (for \G anchor)
    pub best_len: i32,
    pub best_s: usize,
    /// Skip target position set by `onig_builtin_skip`. The search loop
    /// advances past this position after a mismatch.
    pub skip_search: usize,
    // Safety limits
    pub retry_limit_in_match: u64,
    pub retry_limit_in_search: u64,
    pub retry_limit_in_search_counter: u64,
    pub match_stack_limit: u32,
    pub time_limit: u64, // milliseconds, 0 = unlimited
    /// OP_CALLs made by this search (C: `msa->subexp_call_in_search_counter`),
    /// counted only while `onig_set_subexp_call_limit_in_search` is non-zero.
    subexp_call_in_search_counter: u64,
    /// Backtracks since the last clock read (C: `msa->time_counter`). Shared by
    /// every start position of one search, like C's per-search counter.
    time_counter: u64,
    /// Deadline fixed when the search starts (C: `TIME_LIMIT_INIT`). `None`
    /// without a limit, or when the limit is too large to represent.
    time_end: Option<Instant>,
    // Reusable VM state (avoids heap allocation per match_at call)
    stack: Vec<StackEntry>,
    mem_start_stk: Vec<MemPtr>,
    mem_end_stk: Vec<MemPtr>,
}

const CHECK_TIME_INTERVAL: u64 = 512;

impl MatchArg {
    pub(crate) fn new(
        reg: &RegexType,
        option: OnigOptionType,
        region: Option<OnigRegion>,
        start: usize,
    ) -> Self {
        let mut msa = MatchArg {
            options: option | reg.options,
            region,
            start,
            best_len: ONIG_MISMATCH,
            best_s: 0,
            skip_search: 0,
            retry_limit_in_match: RETRY_LIMIT_IN_MATCH.load(Ordering::Relaxed),
            retry_limit_in_search: RETRY_LIMIT_IN_SEARCH.load(Ordering::Relaxed),
            retry_limit_in_search_counter: 0,
            match_stack_limit: MATCH_STACK_LIMIT.load(Ordering::Relaxed),
            time_limit: TIME_LIMIT.load(Ordering::Relaxed),
            time_counter: 0,
            time_end: None,
            subexp_call_in_search_counter: 0,
            stack: Vec::with_capacity(INIT_MATCH_STACK_SIZE),
            mem_start_stk: Vec::new(),
            mem_end_stk: Vec::new(),
        };
        msa.start_time_limit();
        msa
    }

    #[cfg_attr(coverage_nightly, coverage(off))]
    fn from_param(
        reg: &RegexType,
        option: OnigOptionType,
        region: Option<OnigRegion>,
        start: usize,
        mp: &OnigMatchParam,
    ) -> Self {
        let mut msa = MatchArg {
            options: option | reg.options,
            region,
            start,
            best_len: ONIG_MISMATCH,
            best_s: 0,
            skip_search: 0,
            retry_limit_in_match: mp.retry_limit_in_match,
            retry_limit_in_search: mp.retry_limit_in_search,
            retry_limit_in_search_counter: 0,
            match_stack_limit: mp.match_stack_limit,
            time_limit: mp.time_limit,
            time_counter: 0,
            time_end: None,
            subexp_call_in_search_counter: 0,
            stack: Vec::with_capacity(INIT_MATCH_STACK_SIZE),
            mem_start_stk: Vec::new(),
            mem_end_stk: Vec::new(),
        };
        msa.start_time_limit();
        msa
    }

    /// Full reset for thread-local reuse: re-reads global limits, keeps allocated buffers.
    fn reset_full(
        &mut self,
        reg: &RegexType,
        option: OnigOptionType,
        region: Option<OnigRegion>,
        start: usize,
    ) {
        self.options = option | reg.options;
        self.region = region;
        self.start = start;
        self.best_len = ONIG_MISMATCH;
        self.best_s = 0;
        self.skip_search = 0;
        self.retry_limit_in_match = RETRY_LIMIT_IN_MATCH.load(Ordering::Relaxed);
        self.retry_limit_in_search = RETRY_LIMIT_IN_SEARCH.load(Ordering::Relaxed);
        self.retry_limit_in_search_counter = 0;
        self.subexp_call_in_search_counter = 0;
        self.match_stack_limit = MATCH_STACK_LIMIT.load(Ordering::Relaxed);
        self.time_limit = TIME_LIMIT.load(Ordering::Relaxed);
        self.start_time_limit();
    }

    /// Reset mutable state for a new search, keeping allocated buffers.
    pub(crate) fn reset_for_search(
        &mut self,
        reg: &RegexType,
        option: OnigOptionType,
        region: Option<OnigRegion>,
        start: usize,
    ) {
        self.options = option | reg.options;
        self.region = region;
        self.start = start;
        self.best_len = ONIG_MISMATCH;
        self.best_s = 0;
        self.skip_search = 0;
        self.retry_limit_in_search_counter = 0;
        self.subexp_call_in_search_counter = 0;
        self.start_time_limit();
    }

    /// Light reset for reusing MatchArg across multiple onig_match calls
    /// within a regset loop. Keeps allocated buffers and region ownership.
    pub(crate) fn reset_for_match(
        &mut self,
        reg: &RegexType,
        option: OnigOptionType,
        start: usize,
    ) {
        self.options = option | reg.options;
        self.start = start;
        self.best_len = ONIG_MISMATCH;
        self.best_s = 0;
    }

    /// Start the time limit for a new search (C: `TIME_LIMIT_INIT`).
    #[inline]
    fn start_time_limit(&mut self) {
        self.time_counter = 0;
        self.time_end = if self.time_limit == 0 {
            None
        } else {
            Instant::now().checked_add(std::time::Duration::from_millis(self.time_limit))
        };
    }

    /// Count one backtrack and read the clock every `CHECK_TIME_INTERVAL`
    /// backtracks (C: `CHECK_TIME_LIMIT_IN_MATCH`). Returns true once the
    /// deadline has passed.
    #[inline]
    #[cfg_attr(coverage_nightly, coverage(off))]
    fn check_time_limit(&mut self) -> bool {
        self.time_counter += 1;
        if self.time_counter < CHECK_TIME_INTERVAL {
            return false;
        }
        self.time_counter = 0;
        self.time_end.is_some_and(|end| Instant::now() > end)
    }
}

// ============================================================================
// Stack limit check
// ============================================================================

/// Check stack size against match_stack_limit. Returns Err with error code if exceeded.
#[inline]
#[cfg_attr(coverage_nightly, coverage(off))]
fn check_stack_limit(stack_len: usize, limit: u32) -> Result<(), i32> {
    if limit != 0 && stack_len >= limit as usize {
        return Err(ONIGERR_MATCH_STACK_LIMIT_OVER);
    }
    Ok(())
}

// ============================================================================
// Stack operations (port of STACK_PUSH_* / STACK_POP macros)
// ============================================================================

/// Pop stack entries until an ALT (choice point) is found.
/// Restores mem_start_stk/mem_end_stk as needed based on pop_level.
/// Handles callout retraction when reg/callout_data are provided.
/// Returns Some((pcode, pstr, zid)) from the ALT entry, or None if stack is empty.
#[allow(clippy::too_many_arguments)]
fn stack_pop(
    stack: &mut Vec<StackEntry>,
    pop_level: StackPopLevel,
    mem_start_stk: &mut [MemPtr],
    mem_end_stk: &mut [MemPtr],
    reg: &RegexType,
    callout_data: &mut Vec<[i64; ONIG_CALLOUT_DATA_SLOT_NUM]>,
    str_data: &[u8],
    subexp_call_nest_counter: &mut u64,
) -> Option<(usize, usize, i32)> {
    loop {
        let entry = stack.pop()?;
        match entry {
            StackEntry::Alt {
                pcode, pstr, zid, ..
            } => {
                return Some((pcode, pstr, zid));
            }
            StackEntry::AltLazy {
                pcode,
                pstr,
                pstr_start,
                ascii,
                peek_byte,
            } => {
                // Peel off one character and re-push for the remaining range.
                // If peek_byte is set, use memrchr to skip positions where the
                // next byte can't match, instead of decrementing by 1.
                if pstr > pstr_start {
                    let prev = if peek_byte != 0 {
                        // Search backward for the peek byte
                        let search_end = pstr - pstr_start;
                        memchr::memrchr(peek_byte, &str_data[pstr_start..pstr])
                    } else if ascii {
                        Some(pstr - 1)
                    } else {
                        Some(prev_char_head(reg.enc, pstr_start, pstr, str_data))
                    };
                    if let Some(prev_pos) = prev {
                        let prev_abs = if peek_byte != 0 {
                            pstr_start + prev_pos
                        } else {
                            prev_pos
                        };
                        if prev_abs >= pstr_start {
                            stack.push(StackEntry::AltLazy {
                                pcode,
                                pstr: prev_abs,
                                pstr_start,
                                ascii,
                                peek_byte,
                            });
                        }
                    }
                }
                return Some((pcode, pstr, -1));
            }
            _ => match pop_level {
                StackPopLevel::Free => {
                    // Skip non-ALT entries without restoration
                }
                StackPopLevel::MemStart => {
                    // Restore MEM_START entries only
                    if let StackEntry::MemStart {
                        zid,
                        prev_start,
                        prev_end,
                        ..
                    } = &entry
                    {
                        mem_start_stk[*zid] = *prev_start;
                        mem_end_stk[*zid] = *prev_end;
                    }
                }
                StackPopLevel::All => {
                    // Restore all handled entries
                    match &entry {
                        StackEntry::MemStart {
                            zid,
                            prev_start,
                            prev_end,
                            ..
                        } => {
                            mem_start_stk[*zid] = *prev_start;
                            mem_end_stk[*zid] = *prev_end;
                        }
                        StackEntry::MemEnd {
                            zid,
                            prev_start,
                            prev_end,
                            ..
                        } => {
                            mem_start_stk[*zid] = *prev_start;
                            mem_end_stk[*zid] = *prev_end;
                        }
                        StackEntry::Callout { num, id } => {
                            // Retraction callback
                            run_builtin_callout_retraction(reg, *num, *id, callout_data);
                        }
                        // C: POP_CALL
                        StackEntry::Return => {
                            *subexp_call_nest_counter = subexp_call_nest_counter.wrapping_add(1);
                        }
                        StackEntry::CallFrame { .. } => {
                            *subexp_call_nest_counter = subexp_call_nest_counter.wrapping_sub(1);
                        }
                        // RepeatInc, EmptyCheckStart: handled implicitly
                        // (popping removes them)
                        _ => {}
                    }
                }
            },
        }
    }
}

/// Pop stack entries until a Mark with matching zid is found (STACK_POP_TO_MARK).
/// Removes ALL entries. Restores mem_start_stk/mem_end_stk from every popped
/// MemStart/MemEnd entry, so captures set inside a failed (?!..) or (?<!..)
/// body are rolled back, and popped CallFrame/Return entries adjust the call
/// nest counter (C: POP_CALL). Like C, callouts are not retracted here.
/// Returns the saved position from the Mark entry (if any).
fn stack_pop_to_mark(
    stack: &mut Vec<StackEntry>,
    mark_id: usize,
    mem_start_stk: &mut [MemPtr],
    mem_end_stk: &mut [MemPtr],
    subexp_call_nest_counter: &mut u64,
) -> Option<usize> {
    loop {
        let entry = stack.pop()?;
        match &entry {
            StackEntry::Mark { zid, pos } if *zid == mark_id => {
                return *pos;
            }
            StackEntry::MemStart {
                zid,
                prev_start,
                prev_end,
                ..
            } => {
                mem_start_stk[*zid] = *prev_start;
                mem_end_stk[*zid] = *prev_end;
            }
            StackEntry::MemEnd {
                zid,
                prev_start,
                prev_end,
                ..
            } => {
                mem_start_stk[*zid] = *prev_start;
                mem_end_stk[*zid] = *prev_end;
            }
            // C: POP_CALL
            StackEntry::Return => {
                *subexp_call_nest_counter = subexp_call_nest_counter.wrapping_add(1);
            }
            StackEntry::CallFrame { .. } => {
                *subexp_call_nest_counter = subexp_call_nest_counter.wrapping_sub(1);
            }
            _ => {}
        }
    }
}

/// Void stack entries until a Mark with matching zid is found (STACK_TO_VOID_TO_MARK).
/// Only voids "void targets" (regular Alt, EmptyCheckStart, EmptyCheckEnd, Mark) by setting
/// them to Void. Preserves non-void targets (SuperAlt, SaveVal, MemStart, MemEnd, RepeatInc,
/// etc.) in place.
/// Returns the mark's saved position. Preserves Super Alt entries and Marks with different IDs.
fn stack_void_to_mark(stack: &mut [StackEntry], mark_id: usize) -> Option<usize> {
    let mut i = stack.len();
    while i > 0 {
        i -= 1;
        // Check if this is the target Mark
        if let StackEntry::Mark { zid, pos } = &stack[i] {
            if *zid == mark_id {
                let saved_pos = *pos;
                stack[i] = StackEntry::Void;
                return saved_pos;
            }
            // Different id mark: don't void, just skip
            continue;
        }
        // Void targets (C: STK_MASK_TO_VOID_TARGET): regular Alt,
        // EmptyCheckStart and EmptyCheckEnd.
        // Super Alt (is_super=true) is NOT voided — it survives cuts
        let is_void_target = matches!(
            &stack[i],
            StackEntry::Alt {
                is_super: false,
                ..
            } | StackEntry::AltLazy { .. }
                | StackEntry::EmptyCheckStart { .. }
                | StackEntry::EmptyCheckEnd { .. }
        );
        if is_void_target {
            stack[i] = StackEntry::Void;
        }
    }
    None
}

/// Search backwards through the stack for the most recent RepeatInc with matching zid.
/// Returns the count from that entry.
///
/// C: STACK_GET_REPEAT_COUNT_SEARCH. The entries of a subexpression call
/// that has already returned (from its STK_CALL_FRAME up to the matching
/// STK_RETURN) belong to another run of the same repeat, so the scan skips
/// them.
fn stack_get_repeat_count(stack: &[StackEntry], zid: usize) -> i32 {
    let mut k = stack.len();
    while k > 0 {
        k -= 1;
        match &stack[k] {
            StackEntry::RepeatInc { zid: id, count } if *id == zid => return *count,
            StackEntry::Return => {
                let mut level: i32 = -1;
                while k > 0 {
                    k -= 1;
                    match &stack[k] {
                        StackEntry::CallFrame { .. } => {
                            level += 1;
                            if level == 0 {
                                break;
                            }
                        }
                        StackEntry::Return => level -= 1,
                        _ => {}
                    }
                }
            }
            _ => {}
        }
    }
    0
}

/// Check if the empty check for the given zid matches the same string position.
/// Returns true if the string position hasn't advanced (empty match).
fn stack_empty_check(stack: &[StackEntry], zid: usize, s: usize) -> bool {
    for entry in stack.iter().rev() {
        if let StackEntry::EmptyCheckStart { zid: id, pstr } = entry {
            if *id == zid {
                return *pstr == s;
            }
        }
    }
    false
}

/// C: `STACK_AT(ptr.i)->u.mem.pstr` -- the string position of the capture
/// start or end that a saved `mem_start_stk`/`mem_end_stk` value refers to.
/// C only ever reads stack indices here; the port also accepts a plain
/// position, which is what a non-push capture op stores.
fn mem_ptr_pstr(stack: &[StackEntry], ptr: MemPtr) -> Option<usize> {
    if let Some(pos) = ptr.as_pos() {
        return Some(pos);
    }
    match stack.get(ptr.as_stack_idx()?)? {
        StackEntry::MemStart { pstr, .. } | StackEntry::MemEnd { pstr, .. } => Some(*pstr),
        _ => None,
    }
}

/// The per-capture test of C's STACK_EMPTY_CHECK_MEM and
/// STACK_EMPTY_CHECK_MEM_REC (USE_RIGID_CHECK_CAPTURES_IN_EMPTY_REPEAT).
///
/// `kk_*` are the saved start/end of the MEM_START pushed inside the
/// iteration (the capture before the iteration), `k_*` the saved start and
/// the position of the MEM_END that closed it (the capture after it). The
/// iteration changed the capture unless both are the same range, or both are
/// empty ranges.
fn empty_check_mem_changed(
    stack: &[StackEntry],
    kk_prev_start: MemPtr,
    kk_prev_end: MemPtr,
    k_prev_start: MemPtr,
    k_pstr: usize,
) -> bool {
    if kk_prev_end.is_invalid() {
        return true;
    }
    let (Some(old_end), Some(old_start), Some(new_start)) = (
        mem_ptr_pstr(stack, kk_prev_end),
        mem_ptr_pstr(stack, kk_prev_start),
        mem_ptr_pstr(stack, k_prev_start),
    ) else {
        // Unreachable when the saved indices are valid, as in C. Treat the
        // capture as unchanged so the loop still terminates.
        return false;
    };
    (old_end != k_pstr || old_start != new_start) && (new_start != k_pstr || old_start != old_end)
}

/// Memory-aware empty check (C: STACK_EMPTY_CHECK_MEM).
///
/// Returns true only if the string position has not advanced since the
/// matching EMPTY_CHECK_START *and* no capture in `empty_status_mem` changed
/// during the iteration.
fn stack_empty_check_mem(
    stack: &[StackEntry],
    zid: usize,
    s: usize,
    empty_status_mem: u32,
) -> bool {
    // GET_EMPTY_CHECK_START
    let Some(klow) = stack
        .iter()
        .rposition(|e| matches!(e, StackEntry::EmptyCheckStart { zid: id, .. } if *id == zid))
    else {
        return false;
    };
    if let StackEntry::EmptyCheckStart { pstr, .. } = &stack[klow] {
        if *pstr != s {
            return false;
        }
    }

    let mut ms = empty_status_mem;
    let mut k = stack.len();
    while k > klow {
        k -= 1;
        if let StackEntry::MemEnd {
            zid: mem,
            pstr: k_pstr,
            prev_start: k_prev_start,
            ..
        } = &stack[k]
        {
            if mem_status_limit_at(ms, *mem) {
                for kk in klow..k {
                    if let StackEntry::MemStart {
                        zid: kk_mem,
                        prev_start,
                        prev_end,
                        ..
                    } = &stack[kk]
                    {
                        if kk_mem == mem {
                            if empty_check_mem_changed(
                                stack,
                                *prev_start,
                                *prev_end,
                                *k_prev_start,
                                *k_pstr,
                            ) {
                                return false;
                            }
                            ms &= !(1u32 << *mem);
                            break;
                        }
                    }
                }
                if ms == 0 {
                    break;
                }
            }
        }
    }
    true
}

/// Memory-aware empty check for a loop whose body may recurse
/// (C: STACK_EMPTY_CHECK_MEM_REC).
///
/// A recursive call can run the same loop again, so the stack may hold
/// EMPTY_CHECK_START entries of nested runs. Every non-empty iteration of
/// such a loop pushes an EMPTY_CHECK_END (see OP_EMPTY_CHECK_END_MEMST_PUSH),
/// and `level` pairs them up so the scan skips completed iterations.
fn stack_empty_check_mem_rec(
    stack: &[StackEntry],
    zid: usize,
    s: usize,
    empty_status_mem: u32,
) -> bool {
    let mut level: i32 = 0;
    let mut klow = stack.len();
    loop {
        // STACK_BASE_CHECK
        if klow == 0 {
            return false;
        }
        klow -= 1;
        match &stack[klow] {
            StackEntry::EmptyCheckStart { zid: id, pstr } if *id == zid => {
                if level != 0 {
                    level -= 1;
                    continue;
                }
                if *pstr != s {
                    return false;
                }
                if empty_status_mem == 0 {
                    return true;
                }
                let mut ms = empty_status_mem;
                let mut k = stack.len();
                while k > klow {
                    k -= 1;
                    match &stack[k] {
                        StackEntry::MemEnd {
                            zid: mem,
                            pstr: k_pstr,
                            prev_start: k_prev_start,
                            ..
                        } => {
                            if level == 0 && mem_status_limit_at(ms, *mem) {
                                for kk in klow + 1..k {
                                    match &stack[kk] {
                                        StackEntry::MemStart {
                                            zid: kk_mem,
                                            prev_start,
                                            prev_end,
                                            ..
                                        } if kk_mem == mem => {
                                            if empty_check_mem_changed(
                                                stack,
                                                *prev_start,
                                                *prev_end,
                                                *k_prev_start,
                                                *k_pstr,
                                            ) {
                                                return false;
                                            }
                                            ms &= !(1u32 << *mem);
                                            break;
                                        }
                                        StackEntry::EmptyCheckStart { zid: id, .. }
                                            if *id == zid =>
                                        {
                                            level += 1;
                                        }
                                        StackEntry::EmptyCheckEnd { zid: id } if *id == zid => {
                                            level -= 1;
                                        }
                                        _ => {}
                                    }
                                }
                                level = 0;
                                if ms == 0 {
                                    break;
                                }
                            }
                        }
                        StackEntry::EmptyCheckStart { zid: id, .. } if *id == zid => {
                            level += 1;
                        }
                        StackEntry::EmptyCheckEnd { zid: id } if *id == zid => {
                            level -= 1;
                        }
                        _ => {}
                    }
                }
                return true;
            }
            StackEntry::EmptyCheckEnd { zid: id } if *id == zid => {
                level += 1;
            }
            _ => {}
        }
    }
}

/// Get the saved value for a given save_type and zid from the stack.
/// Search stack for last SaveVal by type only (C: STACK_GET_SAVE_VAL_TYPE_LAST)
fn stack_get_save_val_type_last(stack: &[StackEntry], save_type: SaveType) -> Option<usize> {
    for entry in stack.iter().rev() {
        if let StackEntry::SaveVal {
            save_type: st, v, ..
        } = entry
        {
            if *st == save_type {
                return Some(*v);
            }
        }
    }
    None
}

/// Search stack for last SaveVal by type AND id (C: STACK_GET_SAVE_VAL_TYPE_LAST_ID)
fn stack_get_save_val_last(stack: &[StackEntry], save_type: SaveType, zid: usize) -> Option<usize> {
    for entry in stack.iter().rev() {
        if let StackEntry::SaveVal {
            zid: id,
            save_type: st,
            v,
        } = entry
        {
            if *id == zid && *st == save_type {
                return Some(*v);
            }
        }
    }
    None
}

/// Build capture history tree from the match stack.
/// Mirrors C's make_capture_history_tree().
/// Returns 0 on child node ending, 1 on root node ending, or negative error.
fn make_capture_history_tree(
    node: &mut OnigCaptureTreeNode,
    k: &mut usize,
    stack: &[StackEntry],
    stk_top: usize,
    reg: &RegexType,
) -> i32 {
    while *k < stk_top {
        match &stack[*k] {
            StackEntry::MemStart { zid, pstr, .. } => {
                let n = *zid;
                if n <= ONIG_MAX_CAPTURE_HISTORY_GROUP && mem_status_at(reg.capture_history, n) {
                    let mut child = Box::new(OnigCaptureTreeNode::new());
                    child.group = n as i32;
                    child.beg = *pstr as i32;
                    node.add_child(child);
                    let child_idx = node.childs.len() - 1;
                    *k += 1;
                    let r = make_capture_history_tree(
                        &mut node.childs[child_idx],
                        k,
                        stack,
                        stk_top,
                        reg,
                    );
                    if r < 0 {
                        return r;
                    }
                    // After recursive call, k points to the matching MemEnd
                    if let StackEntry::MemEnd { pstr: end_pstr, .. } = &stack[*k] {
                        node.childs[child_idx].end = *end_pstr as i32;
                    }
                }
            }
            StackEntry::MemEnd { zid, pstr, .. } => {
                if *zid == node.group as usize {
                    node.end = *pstr as i32;
                    return 0;
                }
            }
            _ => {}
        }
        *k += 1;
    }
    1 // root node ending
}

/// Get the string position where a capture group starts.
fn get_mem_start(
    reg: &RegexType,
    stack: &[StackEntry],
    mem_start_stk: &[MemPtr],
    idx: usize,
) -> Option<usize> {
    let v = mem_start_stk[idx];
    if v.is_invalid() {
        None
    } else if let Some(pos) = v.as_pos() {
        Some(pos)
    } else if let Some(si) = v.as_stack_idx() {
        if si >= stack.len() {
            None
        } else if let StackEntry::MemStart { pstr, .. } = &stack[si] {
            Some(*pstr)
        } else {
            None
        }
    } else {
        None
    }
}

/// Get the string position where a capture group ends.
fn get_mem_end(
    reg: &RegexType,
    stack: &[StackEntry],
    mem_end_stk: &[MemPtr],
    idx: usize,
) -> Option<usize> {
    let v = mem_end_stk[idx];
    if v.is_invalid() {
        None
    } else if let Some(pos) = v.as_pos() {
        Some(pos)
    } else if let Some(si) = v.as_stack_idx() {
        if si >= stack.len() {
            None
        } else if let StackEntry::MemEnd { pstr, .. } = &stack[si] {
            Some(*pstr)
        } else {
            None
        }
    } else {
        None
    }
}

#[inline(never)]
#[allow(clippy::too_many_arguments)]
fn populate_region_for_match(
    region: &mut OnigRegion,
    reg: &RegexType,
    num_mem: usize,
    keep: usize,
    s: usize,
    stack: &[StackEntry],
    mem_start_stk: &[MemPtr],
    mem_end_stk: &[MemPtr],
) -> Result<(), i32> {
    let region_regs = num_mem + 1;
    if region.num_regs != region_regs as i32 {
        region.resize(region_regs as i32);
    }
    region.beg[0] = keep as i32;
    region.end[0] = s as i32;

    if reg.push_mem_start == 0 && reg.push_mem_end == 0 {
        for i in 1..=num_mem {
            let mem_start = mem_start_stk[i].0;
            let mem_end = mem_end_stk[i].0;
            if mem_start != MEM_PTR_INVALID && mem_end != MEM_PTR_INVALID {
                region.beg[i] = mem_start as i32;
                region.end[i] = mem_end as i32;
            } else {
                region.beg[i] = ONIG_REGION_NOTPOS;
                region.end[i] = ONIG_REGION_NOTPOS;
            }
        }
    } else {
        for i in 1..=num_mem {
            if let Some(mem_end) = get_mem_end(reg, stack, mem_end_stk, i) {
                let mem_start = get_mem_start(reg, stack, mem_start_stk, i);
                region.beg[i] = mem_start.map(|v| v as i32).unwrap_or(ONIG_REGION_NOTPOS);
                region.end[i] = mem_end as i32;
            } else {
                region.beg[i] = ONIG_REGION_NOTPOS;
                region.end[i] = ONIG_REGION_NOTPOS;
            }
        }
    }

    if USE_CAPTURE_HISTORY && reg.capture_history != 0 {
        let node = region
            .history_root
            .get_or_insert_with(|| Box::new(OnigCaptureTreeNode::new()));
        node.clear();
        node.group = 0;
        node.beg = keep as i32;
        node.end = s as i32;
        let mut stkp = 0usize;
        let stk_top = stack.len();
        let r = make_capture_history_tree(node, &mut stkp, stack, stk_top, reg);
        if r < 0 {
            return Err(r);
        }
    }

    Ok(())
}

/// Level-aware scan for the matching MEM_START of a recursive capture group.
/// Mirrors C's STACK_GET_MEM_START macro — counts MemEnd/MemEndMark entries
/// to track nesting level, finds MemStart at level 0.
fn stack_get_mem_start_for_rec(
    stack: &[StackEntry],
    mem: usize,
    push_mem_start: u32,
) -> (MemPtr, usize) {
    let mut level: i32 = 0;
    let mut k = stack.len();
    while k > 0 {
        k -= 1;
        match &stack[k] {
            StackEntry::MemEnd { zid, .. } | StackEntry::MemEndMark { zid } if *zid == mem => {
                level += 1;
            }
            StackEntry::MemStart { zid, pstr, .. } if *zid == mem => {
                if level == 0 {
                    // Found matching start at correct level
                    if mem_status_at(push_mem_start, mem) {
                        return (MemPtr::stack_idx(k), *pstr);
                    } else {
                        return (MemPtr::pos(*pstr), *pstr);
                    }
                }
                level -= 1;
            }
            _ => {}
        }
    }
    (MemPtr::invalid(), 0)
}

/// Match a backref at a specific nesting level in the recursion stack.
/// Walks the stack backwards counting CallFrame/Return to find the right level,
/// then matches the captured text at that level against current position.
#[cfg_attr(coverage_nightly, coverage(off))]
#[allow(clippy::too_many_arguments)]
fn backref_match_at_nested_level(
    reg: &RegexType,
    stack: &[StackEntry],
    ignore_case: bool,
    case_fold_flag: OnigCaseFoldType,
    nest: i32,
    mem_num: i32,
    mems: &[i32],
    s: &mut usize,
    str_data: &[u8],
    end: usize,
) -> bool {
    let mut level: i32 = 0;
    let mut pend: Option<usize> = None;
    let mut k = stack.len();

    while k > 0 {
        k -= 1;
        match &stack[k] {
            StackEntry::CallFrame { .. } => {
                level -= 1;
            }
            StackEntry::Return => {
                level += 1;
            }
            StackEntry::MemStart { zid, pstr, .. } if level == nest => {
                if mem_is_in_mems(*zid, mem_num, mems) {
                    if let Some(pe) = pend {
                        let pstart = *pstr;
                        let cap_len = pe - pstart;
                        if cap_len > end - *s {
                            return false;
                        }
                        if ignore_case {
                            if !string_cmp_ic(reg.enc, case_fold_flag, str_data, pstart, s, cap_len)
                            {
                                return false;
                            }
                        } else {
                            if str_data[pstart..pe] != str_data[*s..*s + cap_len] {
                                return false;
                            }
                            *s += cap_len;
                        }
                        return true;
                    }
                }
            }
            StackEntry::MemEnd { zid, pstr, .. } if level == nest => {
                if mem_is_in_mems(*zid, mem_num, mems) {
                    pend = Some(*pstr);
                }
            }
            _ => {}
        }
    }
    false
}

/// Check if a backref capture exists at a specific nesting level.
///
/// Companion to `backref_match_at_nested_level` (already excluded).
/// Only reachable via `\k<name+level>` check opcodes in recursive patterns.
#[cfg_attr(coverage_nightly, coverage(off))]
fn backref_check_at_nested_level(
    stack: &[StackEntry],
    nest: i32,
    mem_num: i32,
    mems: &[i32],
) -> bool {
    let mut level: i32 = 0;
    let mut k = stack.len();

    while k > 0 {
        k -= 1;
        match &stack[k] {
            StackEntry::CallFrame { .. } => {
                level -= 1;
            }
            StackEntry::Return => {
                level += 1;
            }
            StackEntry::MemStart { zid, .. } if level == nest => {
                if mem_is_in_mems(*zid, mem_num, mems) {
                    return true;
                }
            }
            _ => {}
        }
    }
    false
}

#[inline]
#[cfg_attr(coverage_nightly, coverage(off))]
fn mem_is_in_mems(mem: usize, num: i32, mems: &[i32]) -> bool {
    for candidate in mems.iter().take(num as usize) {
        if mem == *candidate as usize {
            return true;
        }
    }
    false
}

// ============================================================================
// Helper functions
// ============================================================================

/// Check if a byte is a word character (ASCII-only).
#[inline]
fn is_word_ascii(c: u8) -> bool {
    c.is_ascii_alphanumeric() || c == b'_'
}

/// Check if the character at position s is a word character (encoding-aware).
/// Uses the encoding's Unicode-aware is_code_ctype for multi-byte encodings.
#[inline]
fn is_word_char_at(enc: OnigEncoding, str_data: &[u8], s: usize, end: usize) -> bool {
    if s >= end {
        return false;
    }
    let b = str_data[s];
    if b < 0x80 {
        return is_word_ascii(b);
    }
    let code = enc.mbc_to_code(&str_data[s..], end.saturating_sub(s));
    enc.is_code_ctype(code, ONIGENC_CTYPE_WORD)
}

/// Check if position is a word character in ASCII-aware mode.
/// mode == 0: full Unicode word check, mode != 0: ASCII-only word check.
#[inline]
fn is_word_char_ascii_mode(
    enc: OnigEncoding,
    str_data: &[u8],
    s: usize,
    end: usize,
    mode: ModeType,
) -> bool {
    if mode == 0 {
        return is_word_char_at(enc, str_data, s, end);
    }
    // ASCII-only: only a-z, A-Z, 0-9, _ are word characters
    if s >= end {
        return false;
    }
    let b = str_data[s];
    b < 0x80 && is_word_ascii(b)
}

/// Fast literal compare at `s` for VM exact-string opcodes.
///
/// For short lengths, a manual byte loop avoids libc `memcmp` call overhead
/// on the hottest matching path.
#[inline(always)]
fn exact_eq_at(str_data: &[u8], s: usize, exact: &[u8], len: usize) -> bool {
    match len {
        0 => true,
        1 => str_data[s] == exact[0],
        2 => str_data[s] == exact[0] && str_data[s + 1] == exact[1],
        3 => str_data[s] == exact[0] && str_data[s + 1] == exact[1] && str_data[s + 2] == exact[2],
        4 => {
            str_data[s] == exact[0]
                && str_data[s + 1] == exact[1]
                && str_data[s + 2] == exact[2]
                && str_data[s + 3] == exact[3]
        }
        5 => {
            str_data[s] == exact[0]
                && str_data[s + 1] == exact[1]
                && str_data[s + 2] == exact[2]
                && str_data[s + 3] == exact[3]
                && str_data[s + 4] == exact[4]
        }
        6 => {
            str_data[s] == exact[0]
                && str_data[s + 1] == exact[1]
                && str_data[s + 2] == exact[2]
                && str_data[s + 3] == exact[3]
                && str_data[s + 4] == exact[4]
                && str_data[s + 5] == exact[5]
        }
        7 => {
            str_data[s] == exact[0]
                && str_data[s + 1] == exact[1]
                && str_data[s + 2] == exact[2]
                && str_data[s + 3] == exact[3]
                && str_data[s + 4] == exact[4]
                && str_data[s + 5] == exact[5]
                && str_data[s + 6] == exact[6]
        }
        8 => {
            str_data[s] == exact[0]
                && str_data[s + 1] == exact[1]
                && str_data[s + 2] == exact[2]
                && str_data[s + 3] == exact[3]
                && str_data[s + 4] == exact[4]
                && str_data[s + 5] == exact[5]
                && str_data[s + 6] == exact[6]
                && str_data[s + 7] == exact[7]
        }
        9..=16 => {
            let mut i = 0usize;
            while i < len {
                if str_data[s + i] != exact[i] {
                    return false;
                }
                i += 1;
            }
            true
        }
        _ => str_data[s..s + len] == exact[..len],
    }
}

/// Get the start of the previous character (left_adjust_char_head).
#[inline]
fn prev_char_head(enc: OnigEncoding, start: usize, s: usize, str_data: &[u8]) -> usize {
    if s <= start {
        return s;
    }
    // Fast path for ASCII in ASCII-compatible encodings (UTF-8, etc.).
    if str_data[s - 1] < 0x80 && onigenc_is_ascii_compatible_encoding(enc) {
        return s - 1;
    }
    enc.left_adjust_char_head(start, s - 1, str_data)
}

/// Check word boundary at position s (encoding-aware, mode-aware).
/// mode == 0: Unicode word, mode != 0: ASCII-only word.
fn is_word_boundary(
    enc: OnigEncoding,
    str_data: &[u8],
    s: usize,
    end: usize,
    mode: ModeType,
) -> bool {
    let at_start = s == 0;
    let at_end = s >= end;

    if at_start && at_end {
        return false;
    }
    if at_start {
        return is_word_char_ascii_mode(enc, str_data, s, end, mode);
    }
    if at_end {
        let prev = prev_char_head(enc, 0, s, str_data);
        return is_word_char_ascii_mode(enc, str_data, prev, end, mode);
    }

    let prev = prev_char_head(enc, 0, s, str_data);
    let prev_word = is_word_char_ascii_mode(enc, str_data, prev, end, mode);
    let curr_word = is_word_char_ascii_mode(enc, str_data, s, end, mode);
    prev_word != curr_word
}

/// Check if position s is at the start of a word (encoding-aware, mode-aware).
#[cfg_attr(coverage_nightly, coverage(off))]
fn is_word_begin(enc: OnigEncoding, str_data: &[u8], s: usize, end: usize, mode: ModeType) -> bool {
    if s >= end {
        return false;
    }
    if !is_word_char_ascii_mode(enc, str_data, s, end, mode) {
        return false;
    }
    if s == 0 {
        return true;
    }
    let prev = prev_char_head(enc, 0, s, str_data);
    !is_word_char_ascii_mode(enc, str_data, prev, end, mode)
}

/// Check if position s is at the end of a word (encoding-aware, mode-aware).
#[cfg_attr(coverage_nightly, coverage(off))]
fn is_word_end(enc: OnigEncoding, str_data: &[u8], s: usize, end: usize, mode: ModeType) -> bool {
    if s == 0 {
        return false;
    }
    let prev = prev_char_head(enc, 0, s, str_data);
    if !is_word_char_ascii_mode(enc, str_data, prev, end, mode) {
        return false;
    }
    if s >= end {
        return true;
    }
    !is_word_char_ascii_mode(enc, str_data, s, end, mode)
}

/// Check if a code point is in a multi-byte range table.
/// The table format is: data[0] = n (range count), followed by n pairs of (from, to).
/// Binary search, matching C's onig_is_in_code_range exactly.
#[inline]
pub(crate) fn is_in_code_range(data: &[u32], code: OnigCodePoint) -> bool {
    if data.len() < 3 {
        return false;
    }
    let n = data[0] as usize;
    if n == 0 {
        return false;
    }
    let pair_len = n.saturating_mul(2);
    let needed = 1usize.saturating_add(pair_len);
    if data.len() < needed {
        return false;
    }
    let ranges = &data[1..needed];

    let first_low = ranges[0];
    if code < first_low {
        return false;
    }
    let last_high = ranges[pair_len - 1];
    if code > last_high {
        return false;
    }

    // Common fast path for classes like [^\x00-\x7F] encoded as a single
    // multi-byte range [0x80..MAX].
    if n == 1 {
        return true;
    }

    // Small range tables are faster with a straight scan than binary search.
    if n <= 4 {
        let mut i = 0usize;
        while i < n {
            let lo = ranges[i * 2];
            let hi = ranges[i * 2 + 1];
            if code < lo {
                return false;
            }
            if code <= hi {
                return true;
            }
            i += 1;
        }
        return false;
    }

    let mut low: usize = 0;
    let mut high: usize = n;
    while low < high {
        let x = (low + high) >> 1;
        if code > ranges[x * 2 + 1] {
            low = x + 1;
        } else {
            high = x;
        }
    }

    low < n && code >= ranges[low * 2]
}

/// Get the character length at position s for the given encoding.
#[inline]
fn enclen(enc: OnigEncoding, str_data: &[u8], s: usize) -> usize {
    if s >= str_data.len() {
        return 1;
    }
    // Hot path: ASCII byte in ASCII-compatible encoding is always length 1.
    if str_data[s] < 0x80 && onigenc_is_ascii_compatible_encoding(enc) {
        return 1;
    }
    enc.mbc_enc_len(&str_data[s..])
}

/// Advance over one character without moving past the logical end of input.
///
/// A UTF-8 lead byte can report a character length larger than the remaining
/// input when callers use the byte API with truncated input. The matcher must
/// consume the available bytes in that case, rather than retaining an offset
/// beyond `end` for a later opcode or match region.
#[inline]
fn advance_char_to_end(enc: OnigEncoding, str_data: &[u8], s: usize, end: usize) -> usize {
    s.saturating_add(enclen(enc, str_data, s)).min(end)
}

/// Case-insensitive string comparison using encoding-aware case folding.
/// Compares `mblen` bytes starting at `s1_pos` with bytes starting at `*s2_pos`.
/// Advances `*s2_pos` past consumed bytes on success. Returns true if equal.
/// Case-insensitive string comparison for backref matching at nested levels.
/// Only reachable via `\k<name+level>` with ignore-case in recursive patterns.
#[cfg_attr(coverage_nightly, coverage(off))]
fn string_cmp_ic(
    enc: OnigEncoding,
    case_fold_flag: OnigCaseFoldType,
    data: &[u8],
    s1_pos: usize,
    s2_pos: &mut usize,
    mblen: usize,
) -> bool {
    let mut buf1 = [0u8; ONIGENC_MBC_CASE_FOLD_MAXLEN];
    let mut buf2 = [0u8; ONIGENC_MBC_CASE_FOLD_MAXLEN];
    let end1 = s1_pos + mblen;
    let end2 = *s2_pos + mblen;
    let mut p1 = s1_pos;
    let mut p2 = *s2_pos;

    while p1 < end1 {
        let len1 = enc.mbc_case_fold(case_fold_flag, &mut p1, end1, data, &mut buf1);
        let len2 = enc.mbc_case_fold(case_fold_flag, &mut p2, end2, data, &mut buf2);
        if len1 != len2 {
            return false;
        }
        if buf1[..len1 as usize] != buf2[..len2 as usize] {
            return false;
        }
        if p2 >= end2 {
            if p1 < end1 {
                return false;
            }
            break;
        }
    }

    *s2_pos = p2;
    true
}

// ============================================================================
// Builtin callout functions
// ============================================================================

/// Run a builtin callout in the progress direction.
/// Returns ONIG_CALLOUT_SUCCESS or ONIG_CALLOUT_FAIL.
fn run_builtin_callout(
    reg: &RegexType,
    num: i32,
    _id: i32,
    is_retraction: bool,
    callout_data: &mut [[i64; ONIG_CALLOUT_DATA_SLOT_NUM]],
    current_s: usize,
    msa: &mut MatchArg,
) -> i32 {
    let ext = match reg.extp.as_ref() {
        Some(e) => e,
        None => return ONIG_CALLOUT_SUCCESS,
    };
    if num < 1 || (num as usize) > ext.callout_list.len() {
        return ONIG_CALLOUT_SUCCESS;
    }
    let entry = &ext.callout_list[(num - 1) as usize];
    let idx = (num - 1) as usize;

    match entry.builtin_id {
        CALLOUT_BUILTIN_MAX => {
            let max_val = resolve_callout_arg(&entry.args[0], &ext.callout_list, callout_data);
            builtin_max(entry, is_retraction, &mut callout_data[idx], max_val)
        }
        CALLOUT_BUILTIN_COUNT => builtin_count(entry, is_retraction, &mut callout_data[idx]),
        CALLOUT_BUILTIN_CMP => {
            let lv = resolve_callout_arg(&entry.args[0], &ext.callout_list, callout_data);
            let rv = resolve_callout_arg(&entry.args[2], &ext.callout_list, callout_data);
            builtin_cmp(entry, &mut callout_data[idx], lv, rv)
        }
        CALLOUT_BUILTIN_SKIP => {
            if !is_retraction && current_s > msa.skip_search {
                msa.skip_search = current_s;
            }
            ONIG_CALLOUT_SUCCESS
        }
        _ => ONIG_CALLOUT_SUCCESS,
    }
}

/// Run a builtin callout in the retraction direction (called from stack_pop).
///
/// Callout retraction is triggered during backtracking when a callout was
/// previously executed in the forward direction. This is internal engine
/// bookkeeping for `(*MAX)` / `(*COUNT)` callouts and not directly testable
/// without exposing callout internals.
#[cfg_attr(coverage_nightly, coverage(off))]
fn run_builtin_callout_retraction(
    reg: &RegexType,
    num: i32,
    _id: i32,
    callout_data: &mut [[i64; ONIG_CALLOUT_DATA_SLOT_NUM]],
) {
    let ext = match reg.extp.as_ref() {
        Some(e) => e,
        None => return,
    };
    if num < 1 || (num as usize) > ext.callout_list.len() {
        return;
    }
    let entry = &ext.callout_list[(num - 1) as usize];
    let slots = &mut callout_data[(num - 1) as usize];

    match entry.builtin_id {
        CALLOUT_BUILTIN_MAX => {
            // Retraction for MAX: same logic as progress but with is_retraction=true
            // We can't pass the full callout_data for tag resolution here since we already
            // have a mutable borrow. But MAX retraction only reads slots[0] (its own counter).
            let count_type = if entry.args.len() > 1 {
                match &entry.args[1] {
                    CalloutArg::Char(c) => *c,
                    _ => b'X',
                }
            } else {
                b'X'
            };
            if count_type == b'<' {
                // retraction + '<': increment and check
                let max_val = resolve_callout_arg(&entry.args[0], &[], &[]);
                if slots[0] >= max_val {
                    // fail — but retraction result is ignored per C code
                } else {
                    slots[0] += 1;
                }
            } else if count_type == b'X' {
                // retraction + 'X': decrement
                slots[0] -= 1;
            }
            // retraction + '>': no-op
        }
        CALLOUT_BUILTIN_COUNT => {
            let count_type = if !entry.args.is_empty() {
                match &entry.args[0] {
                    CalloutArg::Char(c) => *c,
                    _ => b'>',
                }
            } else {
                b'>'
            };
            // Retraction: slot 2
            if count_type == b'<' {
                slots[0] += 1;
            } else if count_type == b'X' {
                slots[0] -= 1;
            }
            // slot 2 (retraction counter) increment
            slots[2] += 1;
        }
        _ => {}
    }
}

/// Resolve a callout argument: Long value directly or Tag → lookup slot[0] of tagged callout.
#[cfg_attr(coverage_nightly, coverage(off))]
fn resolve_callout_arg(
    arg: &CalloutArg,
    ext_callout_list: &[CalloutListEntry],
    all_data: &[[i64; ONIG_CALLOUT_DATA_SLOT_NUM]],
) -> i64 {
    match arg {
        CalloutArg::Long(n) => *n,
        CalloutArg::Tag(tag) => {
            for (i, e) in ext_callout_list.iter().enumerate() {
                if let Some(ref t) = e.tag {
                    if t == tag && i < all_data.len() {
                        return all_data[i][0];
                    }
                }
            }
            0
        }
        _ => 0,
    }
}

/// Builtin callout implementation for `(*MAX{n})`.
/// Internal engine bookkeeping not directly testable via the public API.
#[cfg_attr(coverage_nightly, coverage(off))]
fn builtin_max(
    entry: &CalloutListEntry,
    is_retraction: bool,
    slots: &mut [i64; ONIG_CALLOUT_DATA_SLOT_NUM],
    max_val: i64,
) -> i32 {
    // slots[0] = current count
    let count_type = if entry.args.len() > 1 {
        match &entry.args[1] {
            CalloutArg::Char(c) => *c,
            _ => b'X',
        }
    } else {
        b'X'
    };

    if is_retraction {
        if count_type == b'<' {
            if slots[0] >= max_val {
                return ONIG_CALLOUT_FAIL;
            }
            slots[0] += 1;
        } else if count_type == b'X' {
            slots[0] -= 1;
        }
    } else {
        if count_type != b'<' {
            if slots[0] >= max_val {
                return ONIG_CALLOUT_FAIL;
            }
            slots[0] += 1;
        }
    }

    ONIG_CALLOUT_SUCCESS
}

/// Builtin callout implementation for `(*COUNT)`.
#[cfg_attr(coverage_nightly, coverage(off))]
fn builtin_count(
    entry: &CalloutListEntry,
    is_retraction: bool,
    slots: &mut [i64; ONIG_CALLOUT_DATA_SLOT_NUM],
) -> i32 {
    // slots[0] = main counter (progress - retraction adjusted)
    // slots[1] = progress counter
    // slots[2] = retraction counter
    let count_type = if !entry.args.is_empty() {
        match &entry.args[0] {
            CalloutArg::Char(c) => *c,
            _ => b'>',
        }
    } else {
        b'>'
    };

    if is_retraction {
        if count_type == b'<' {
            slots[0] += 1;
        } else if count_type == b'X' {
            slots[0] -= 1;
        }
        // slot 2 (retraction counter)
        slots[2] += 1;
    } else {
        if count_type != b'<' {
            slots[0] += 1;
        }
        // slot 1 (progress counter)
        slots[1] += 1;
    }

    ONIG_CALLOUT_SUCCESS
}

/// Builtin callout implementation for `(*CMP{...})`.
#[cfg_attr(coverage_nightly, coverage(off))]
fn builtin_cmp(
    entry: &CalloutListEntry,
    slots: &mut [i64; ONIG_CALLOUT_DATA_SLOT_NUM],
    lv: i64,
    rv: i64,
) -> i32 {
    // CMP is progress-only
    if entry.args.len() < 3 {
        return ONIG_CALLOUT_FAIL;
    }

    // Parse op on first call, cache in slots[0]
    let op = if slots[3] == 0 {
        // First call: parse operator string
        let op_val = match &entry.args[1] {
            CalloutArg::Str(s) => parse_cmp_op(s),
            CalloutArg::Char(c) => parse_cmp_op(&[*c]),
            _ => return ONIG_CALLOUT_FAIL,
        };
        slots[3] = 1; // mark as initialized
        slots[4] = op_val as i64;
        op_val
    } else {
        slots[4] as i32
    };

    let result = match op {
        0 => lv == rv, // ==
        1 => lv != rv, // !=
        2 => lv < rv,  // <
        3 => lv > rv,  // >
        4 => lv <= rv, // <=
        5 => lv >= rv, // >=
        _ => false,
    };

    if result {
        ONIG_CALLOUT_SUCCESS
    } else {
        ONIG_CALLOUT_FAIL
    }
}

#[cfg_attr(coverage_nightly, coverage(off))]
fn parse_cmp_op(s: &[u8]) -> i32 {
    match s {
        b"==" => 0,
        b"!=" => 1,
        b"<" => 2,
        b">" => 3,
        b"<=" => 4,
        b">=" => 5,
        _ => -1,
    }
}

/// Whether stepping back from `next` with `prev_char_head` lands on `x`, the
/// start of the character a star loop's forward scan consumed as `x..next`.
///
/// Star opcodes record a run as one `AltLazy` entry and retrace it with
/// `prev_char_head`. On malformed multibyte input that can skip a boundary or
/// land inside a sequence the scan consumed whole, so such runs fall back to
/// one backtrack entry per character (`push_char_boundaries`). In UTF-8 the
/// check reads the continuation bytes instead of calling into the encoding.
#[inline(always)]
fn steps_back_to(enc: OnigEncoding, str_data: &[u8], start: usize, x: usize, next: usize) -> bool {
    if std::ptr::addr_eq(enc, &crate::encodings::utf8::ONIG_ENCODING_UTF8) {
        str_data[x + 1..next].iter().all(|&b| b & 0xC0 == 0x80)
            && (x == start || str_data[x] & 0xC0 != 0x80)
    } else {
        prev_char_head(enc, start, next, str_data) == x
    }
}

/// Push the backtrack points of a greedy single-character loop that consumed
/// `start..end`: one `AltLazy` range when stepping back retraces the scan
/// (`exact_heads`), otherwise one entry per character boundary.
#[inline(always)]
#[allow(clippy::too_many_arguments)]
fn push_char_run(
    stack: &mut Vec<StackEntry>,
    pcode: usize,
    enc: OnigEncoding,
    str_data: &[u8],
    start: usize,
    end: usize,
    single_byte: bool,
    exact_heads: bool,
) {
    if end <= start {
        return;
    }
    if single_byte {
        stack.push(StackEntry::AltLazy {
            pcode,
            pstr: end - 1,
            pstr_start: start,
            ascii: true,
            peek_byte: 0,
        });
    } else if exact_heads {
        stack.push(StackEntry::AltLazy {
            pcode,
            pstr: prev_char_head(enc, start, end, str_data),
            pstr_start: start,
            ascii: false,
            peek_byte: 0,
        });
    } else {
        push_char_boundaries(stack, pcode, enc, str_data, start, end);
    }
}

/// Greedy run of a negated single-character loop (`[^class]*`) from `start`.
///
/// `ascii_member(b)` and `member_end(x)` (for a non-ASCII byte at `x`, the
/// position after its character) mirror the loop's single-character opcode,
/// so the run consumes exactly what the unoptimized `PUSH; CCLASS_NOT; JUMP`
/// loop consumes. Out of line: negated loops are long (strings, comments),
/// and their code inlined into `match_at_impl` slowed unrelated patterns.
/// Returns the end of the run.
#[inline(never)]
#[allow(clippy::too_many_arguments)]
fn greedy_char_loop(
    stack: &mut Vec<StackEntry>,
    pcode: usize,
    enc: OnigEncoding,
    str_data: &[u8],
    start: usize,
    right_range: usize,
    ascii_member: impl Fn(u8) -> bool,
    member_end: impl Fn(usize) -> Option<usize>,
) -> usize {
    let mut s = start;
    let mut single_byte = true;
    let mut exact_heads = true;
    while s < right_range {
        let b = str_data[s];
        if b < 0x80 {
            if !ascii_member(b) {
                break;
            }
            s += 1;
            continue;
        }
        let Some(next) = member_end(s) else {
            break;
        };
        single_byte &= next == s + 1;
        exact_heads &= steps_back_to(enc, str_data, start, s, next);
        s = next;
    }
    push_char_run(
        stack,
        pcode,
        enc,
        str_data,
        start,
        s,
        single_byte,
        exact_heads,
    );
    s
}

/// Push one backtrack entry per character boundary of `start..run_end`, as
/// the unoptimized loop does. Only reached for malformed multibyte input.
///
/// Every single-character opcode behind the star loops steps over an ASCII
/// byte by one and over anything else by `enclen`, where a character cut by
/// the range ends the run, so the boundaries are retraced without calling
/// the loop's character test again.
#[cold]
#[inline(never)]
fn push_char_boundaries(
    stack: &mut Vec<StackEntry>,
    pcode: usize,
    enc: OnigEncoding,
    str_data: &[u8],
    start: usize,
    run_end: usize,
) {
    let mut x = start;
    while x < run_end {
        stack.push(StackEntry::Alt {
            pcode,
            pstr: x,
            zid: -1,
            is_super: false,
        });
        x = x.saturating_add(enclen(enc, str_data, x)).min(run_end);
    }
}

/// Match a literal alternation compiled to a trie at `s`, as the ordered
/// alternation would: continue with the literal that comes first and, when
/// several literals match (one is a prefix of another), leave the others as
/// backtracking alternatives in alternation order, resuming at `next_pcode`
/// after their end. Returns the length of the first match.
#[inline(never)]
fn match_literal_trie(
    stack: &mut Vec<StackEntry>,
    trie: &crate::literal_trie::LiteralTrie,
    str_data: &[u8],
    s: usize,
    right_range: usize,
    next_pcode: usize,
) -> Option<usize> {
    let (len, others) = trie.first_match(str_data, s, right_range)?;
    if others {
        let matches = trie.matches_in_order(str_data, s, right_range);
        for &(_, alternative) in matches[1..].iter().rev() {
            stack.push(StackEntry::Alt {
                pcode: next_pcode,
                pstr: s + alternative,
                zid: -1,
                is_super: false,
            });
        }
    }
    Some(len)
}

/// `LookBehindOp`: STEP_BACK_START by `char_len` characters from `s`, then
/// the body instruction `body` at that position. Out of line: code added to
/// `match_at_impl` shifts its layout (see the performance analysis).
#[inline(never)]
fn look_behind_body_matches(
    body: &Operation,
    char_len: u32,
    enc: OnigEncoding,
    str_data: &[u8],
    s: usize,
    right_range: usize,
    end: usize,
) -> bool {
    onigenc_step_back(enc, 0, s, str_data, char_len as usize)
        .is_some_and(|at| single_op_matches(body, enc, str_data, at, right_range, end))
}

/// Whether the single-character or string instruction `op` matches at `s`,
/// exactly as the VM executes it. `LookBehindOp` checks its body with it at
/// the position it stepped back to.
#[inline]
fn single_op_matches(
    op: &Operation,
    enc: OnigEncoding,
    str_data: &[u8],
    s: usize,
    right_range: usize,
    end: usize,
) -> bool {
    let available = right_range.saturating_sub(s);
    match (op.opcode, &op.payload) {
        (
            OpCode::Str1 | OpCode::Str2 | OpCode::Str3 | OpCode::Str4 | OpCode::Str5,
            OperationPayload::Exact { s: exact },
        ) => {
            let n = op.opcode as usize - OpCode::Str1 as usize + 1;
            available >= n && exact[..n] == str_data[s..s + n]
        }
        (OpCode::StrN, OperationPayload::ExactN { s: exact, n }) => {
            let n = *n as usize;
            available >= n && exact_eq_at(str_data, s, exact, n)
        }
        (
            OpCode::StrMb2n1
            | OpCode::StrMb2n2
            | OpCode::StrMb2n3
            | OpCode::StrMb2n
            | OpCode::StrMb3n
            | OpCode::StrMbn,
            OperationPayload::ExactLenN { s: exact, n, .. },
        ) => {
            let n = *n as usize;
            available >= n && exact_eq_at(str_data, s, exact, n)
        }
        (OpCode::CClass | OpCode::CClassNot, OperationPayload::CClass { bsp, ascii_fast }) => {
            if available == 0 {
                return false;
            }
            let b = str_data[s];
            let in_class = match *ascii_fast {
                CClassAsciiFastKind::Eq(c) => b == c,
                CClassAsciiFastKind::EqFoldLower(lower) => b < 0x80 && (b | 0x20) == lower,
                CClassAsciiFastKind::None => bitset_at(bsp, b as usize),
            };
            in_class != (op.opcode == OpCode::CClassNot)
        }
        (OpCode::CClassMb | OpCode::CClassMbNot, OperationPayload::CClassMb { mb }) => {
            let not = op.opcode == OpCode::CClassMbNot;
            if available == 0 {
                return false;
            }
            let b = str_data[s];
            if b < 0x80 {
                return is_in_code_range(mb, b as OnigCodePoint) != not;
            }
            if s + enclen(enc, str_data, s) > right_range {
                // A truncated character matches only the negated class.
                return not;
            }
            let code = enc.mbc_to_code(&str_data[s..], end.saturating_sub(s));
            is_in_code_range(mb, code) != not
        }
        (OpCode::CClassMix | OpCode::CClassMixNot, OperationPayload::CClassMix { bsp, mb }) => {
            let not = op.opcode == OpCode::CClassMixNot;
            if available == 0 {
                return false;
            }
            let b = str_data[s];
            if b < 0x80 {
                return bitset_at(bsp, b as usize) != not;
            }
            let len = enclen(enc, str_data, s);
            if s + len > right_range {
                return not;
            }
            let in_class = if len == 1 {
                bitset_at(bsp, b as usize)
            } else {
                let code = enc.mbc_to_code(&str_data[s..], end.saturating_sub(s));
                is_in_code_range(mb, code)
                    || ((code as usize) < SINGLE_BYTE_SIZE && bitset_at(bsp, code as usize))
            };
            in_class != not
        }
        _ => unreachable!("look-behind body is a single character or string instruction"),
    }
}

// ============================================================================
// match_at - the core VM executor (port of C's match_at function)
// ============================================================================

/// Execute the bytecode VM starting at position `sstart` in the string.
/// Returns match length on success, ONIG_MISMATCH (-1) on failure.
///
/// Parameters match C's match_at(reg, str, end, in_right_range, sstart, msa):
/// - reg: compiled regex with bytecode in reg.ops
/// - str_data: the input string bytes
/// - end: end position in str_data
/// - in_right_range: right boundary for matching
/// - sstart: position to start matching at
/// - msa: mutable match state (options, region, etc.)
#[inline(always)]
fn match_at(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    in_right_range: usize,
    sstart: usize,
    msa: &mut MatchArg,
) -> i32 {
    // Untracked runs skip the MemStartPush/MemEndPush stack entries. With a
    // match stack limit configured that would change when the limit trips,
    // so such runs keep the bookkeeping to stay observably identical to C.
    if msa.region.is_some()
        || reg.needs_capture_tracking
        || (msa.match_stack_limit != 0 && (reg.push_mem_start | reg.push_mem_end) != 0)
    {
        match_at_impl::<true>(reg, str_data, end, in_right_range, sstart, msa)
    } else {
        match_at_impl::<false>(reg, str_data, end, in_right_range, sstart, msa)
    }
}

fn match_at_impl<const TRACK_CAPTURES: bool>(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    in_right_range: usize,
    sstart: usize,
    msa: &mut MatchArg,
) -> i32 {
    let mut p: usize = 0; // bytecode index into reg.ops
    let mut s: usize = sstart; // current string position
    let mut right_range: usize = in_right_range;
    let pop_level = reg.stack_pop_level;
    let num_mem = reg.num_mem as usize;
    let enc = reg.enc;
    let options = msa.options;

    // Reuse stack and capture-group arrays from MatchArg (avoids heap alloc per call)
    let mut stack = std::mem::take(&mut msa.stack);
    stack.clear();
    let mut mem_start_stk = std::mem::take(&mut msa.mem_start_stk);
    if TRACK_CAPTURES {
        let need = num_mem + 1;
        mem_start_stk.resize(need, MemPtr::invalid());
        mem_start_stk.fill(MemPtr::invalid());
    } else {
        mem_start_stk.clear();
    }
    let mut mem_end_stk = std::mem::take(&mut msa.mem_end_stk);
    if TRACK_CAPTURES {
        let need = num_mem + 1;
        mem_end_stk.resize(need, MemPtr::invalid());
        mem_end_stk.fill(MemPtr::invalid());
    } else {
        mem_end_stk.clear();
    }

    let mut keep: usize = sstart;
    let mut best_len: i32 = ONIG_MISMATCH;
    let mut last_alt_zid: i32 = -1;

    // Safety limits. As in C, the budget left in the search caps the retries
    // of this match, so one start position cannot overrun the search limit.
    let mut retry_limit_in_match = msa.retry_limit_in_match;
    if msa.retry_limit_in_search != 0 {
        let rem = msa
            .retry_limit_in_search
            .saturating_sub(msa.retry_limit_in_search_counter);
        if rem < retry_limit_in_match || retry_limit_in_match == 0 {
            retry_limit_in_match = rem;
        }
    }
    let mut retry_in_match_counter: u64 = 0;
    let match_stack_limit = msa.match_stack_limit;
    let time_limit_ms = msa.time_limit;

    // Subexpression call limits (C: `subexp_call_nest_counter`,
    // `SubexpCallMaxNestLevel` and `SubexpCallLimitInSearch`). Like C, the
    // int nest level is compared as an unsigned long, so a negative level
    // never trips.
    let mut subexp_call_nest_counter: u64 = 0;
    let subexp_call_max_nest_level = onig_get_subexp_call_max_nest_level() as i64 as u64;
    let subexp_call_limit_in_search = onig_get_subexp_call_limit_in_search();

    // Callout data: per-callout mutable slots (indexed by callout num - 1)
    let callout_count = reg.extp.as_ref().map_or(0, |e| e.callout_num as usize);
    let mut callout_data: Vec<[i64; ONIG_CALLOUT_DATA_SLOT_NUM]> =
        vec![[0i64; ONIG_CALLOUT_DATA_SLOT_NUM]; callout_count];

    // Push bottom sentinel (like C's STACK_PUSH_BOTTOM with FinishCode)
    stack.push(StackEntry::Alt {
        pcode: FINISH_PCODE,
        pstr: 0,
        zid: -1,
        is_super: false,
    });

    // ---- Main dispatch loop ----
    loop {
        if p >= reg.ops.len() {
            break;
        }

        // Stack limit check (checked once per opcode, like C's STACK_PUSH macro)
        if match_stack_limit != 0 && stack.len() >= match_stack_limit as usize {
            best_len = ONIGERR_MATCH_STACK_LIMIT_OVER;
            break;
        }

        let opcode = reg.ops[p].opcode;
        let mut goto_fail = false;

        match opcode {
            // ================================================================
            // OP_FINISH - reached bottom sentinel, return result
            // ================================================================
            OpCode::Finish => {
                break;
            }

            // ================================================================
            // OP_END - successful match, populate region
            // ================================================================
            OpCode::End => {
                // Check MATCH_WHOLE_STRING option
                if opton_match_whole_string(options) && s < end {
                    goto_fail = true;
                } else {
                    let n = (s - sstart) as i32;
                    if n == 0 && opton_find_not_empty(options) {
                        goto_fail = true;
                    } else if n > best_len {
                        best_len = n;

                        // Populate region with capture groups
                        if let Some(ref mut region) = msa.region {
                            if let Err(err) = populate_region_for_match(
                                region,
                                reg,
                                num_mem,
                                keep,
                                s,
                                &stack,
                                &mem_start_stk,
                                &mem_end_stk,
                            ) {
                                best_len = err;
                                break;
                            }
                        }

                        // For non-FIND_LONGEST, return immediately
                        if !opton_find_longest(options) {
                            msa.stack = stack;
                            msa.mem_start_stk = mem_start_stk;
                            msa.mem_end_stk = mem_end_stk;
                            return best_len;
                        }

                        // FIND_LONGEST: save best and continue searching
                        msa.best_len = best_len;
                        msa.best_s = sstart;
                        goto_fail = true; // backtrack to try longer matches
                    } else {
                        // FIND_LONGEST but shorter/equal match: backtrack for more
                        goto_fail = true;
                    }
                }
            }

            // ================================================================
            // OP_STR1..STR5 - match 1-5 literal bytes
            // ================================================================
            OpCode::Str1 => {
                if s >= right_range {
                    goto_fail = true;
                } else if let OperationPayload::Exact { s: ref exact } = reg.ops[p].payload {
                    if exact[0] != str_data[s] {
                        goto_fail = true;
                    } else {
                        s += 1;
                        p += 1;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::Str2 => {
                if right_range.saturating_sub(s) < 2 {
                    goto_fail = true;
                } else if let OperationPayload::Exact { s: ref exact } = reg.ops[p].payload {
                    if exact[0] != str_data[s] || exact[1] != str_data[s + 1] {
                        goto_fail = true;
                    } else {
                        s += 2;
                        p += 1;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::Str3 => {
                if right_range.saturating_sub(s) < 3 {
                    goto_fail = true;
                } else if let OperationPayload::Exact { s: ref exact } = reg.ops[p].payload {
                    if exact[0] != str_data[s]
                        || exact[1] != str_data[s + 1]
                        || exact[2] != str_data[s + 2]
                    {
                        goto_fail = true;
                    } else {
                        s += 3;
                        p += 1;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::Str4 => {
                if right_range.saturating_sub(s) < 4 {
                    goto_fail = true;
                } else if let OperationPayload::Exact { s: ref exact } = reg.ops[p].payload {
                    if exact[0] != str_data[s]
                        || exact[1] != str_data[s + 1]
                        || exact[2] != str_data[s + 2]
                        || exact[3] != str_data[s + 3]
                    {
                        goto_fail = true;
                    } else {
                        s += 4;
                        p += 1;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::Str5 => {
                if right_range.saturating_sub(s) < 5 {
                    goto_fail = true;
                } else if let OperationPayload::Exact { s: ref exact } = reg.ops[p].payload {
                    if exact[0] != str_data[s]
                        || exact[1] != str_data[s + 1]
                        || exact[2] != str_data[s + 2]
                        || exact[3] != str_data[s + 3]
                        || exact[4] != str_data[s + 4]
                    {
                        goto_fail = true;
                    } else {
                        s += 5;
                        p += 1;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::StrN => {
                if let OperationPayload::ExactN { s: ref exact, n } = reg.ops[p].payload {
                    let n = n as usize;
                    if right_range.saturating_sub(s) < n || !exact_eq_at(str_data, s, exact, n) {
                        goto_fail = true;
                    } else {
                        s += n;
                        p += 1;
                    }
                } else {
                    goto_fail = true;
                }
            }

            // MB string opcodes (for multibyte encodings)
            OpCode::StrMb2n1
            | OpCode::StrMb2n2
            | OpCode::StrMb2n3
            | OpCode::StrMb2n
            | OpCode::StrMb3n
            | OpCode::StrMbn => {
                // Multi-byte string comparison. ExactLenN.n = total byte count.
                if let OperationPayload::ExactLenN {
                    s: ref exact, n, ..
                } = reg.ops[p].payload
                {
                    let byte_len = n as usize;
                    if right_range.saturating_sub(s) < byte_len
                        || !exact_eq_at(str_data, s, exact, byte_len)
                    {
                        goto_fail = true;
                    } else {
                        s += byte_len;
                        p += 1;
                    }
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_CCLASS / OP_CCLASS_NOT - character class matching
            // ================================================================
            OpCode::CClass => {
                if s >= right_range {
                    goto_fail = true;
                } else if let OperationPayload::CClass {
                    ref bsp,
                    ascii_fast,
                } = reg.ops[p].payload
                {
                    match ascii_fast {
                        CClassAsciiFastKind::Eq(c) => {
                            if str_data[s] != c {
                                goto_fail = true;
                            } else {
                                s += 1;
                                p += 1;
                            }
                        }
                        CClassAsciiFastKind::EqFoldLower(lower) => {
                            let b = str_data[s];
                            if b >= 0x80 || (b | 0x20) != lower {
                                goto_fail = true;
                            } else {
                                s += 1;
                                p += 1;
                            }
                        }
                        CClassAsciiFastKind::None => {
                            let b = str_data[s];
                            if !bitset_at(bsp, b as usize) {
                                goto_fail = true;
                            } else {
                                s = advance_char_to_end(enc, str_data, s, end);
                                p += 1;
                            }
                        }
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::CClassNot => {
                if s >= right_range {
                    goto_fail = true;
                } else if let OperationPayload::CClass {
                    ref bsp,
                    ascii_fast,
                } = reg.ops[p].payload
                {
                    match ascii_fast {
                        CClassAsciiFastKind::Eq(c) => {
                            let b = str_data[s];
                            if b == c {
                                goto_fail = true;
                            } else {
                                s = advance_char_to_end(enc, str_data, s, end);
                                p += 1;
                            }
                        }
                        CClassAsciiFastKind::EqFoldLower(lower) => {
                            let b = str_data[s];
                            if b < 0x80 && (b | 0x20) == lower {
                                goto_fail = true;
                            } else {
                                s = advance_char_to_end(enc, str_data, s, end);
                                p += 1;
                            }
                        }
                        CClassAsciiFastKind::None => {
                            let b = str_data[s];
                            if bitset_at(bsp, b as usize) {
                                goto_fail = true;
                            } else {
                                s = advance_char_to_end(enc, str_data, s, end);
                                p += 1;
                            }
                        }
                    }
                } else {
                    goto_fail = true;
                }
            }

            // MB character class (multibyte)
            OpCode::CClassMb => {
                if s >= right_range {
                    goto_fail = true;
                } else if let OperationPayload::CClassMb { ref mb } = reg.ops[p].payload {
                    let b = str_data[s];
                    if b < 0x80 {
                        if !is_in_code_range(mb, b as OnigCodePoint) {
                            goto_fail = true;
                        } else {
                            s += 1;
                            p += 1;
                        }
                    } else {
                        let mb_len = enclen(enc, str_data, s);
                        if s + mb_len > right_range {
                            goto_fail = true;
                        } else {
                            let code = enc.mbc_to_code(&str_data[s..], end.saturating_sub(s));
                            if !is_in_code_range(mb, code) {
                                goto_fail = true;
                            } else {
                                s += mb_len;
                                p += 1;
                            }
                        }
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::CClassMbNot => {
                if s >= right_range {
                    goto_fail = true;
                } else if let OperationPayload::CClassMb { ref mb } = reg.ops[p].payload {
                    let b = str_data[s];
                    if b < 0x80 {
                        if is_in_code_range(mb, b as OnigCodePoint) {
                            goto_fail = true;
                        } else {
                            s += 1;
                            p += 1;
                        }
                    } else {
                        let mb_len = enclen(enc, str_data, s);
                        if s + mb_len > right_range {
                            // Upstream treats a multibyte character truncated
                            // by the logical end as matching a negated class.
                            s = right_range;
                            p += 1;
                        } else {
                            let code = enc.mbc_to_code(&str_data[s..], end.saturating_sub(s));
                            if is_in_code_range(mb, code) {
                                goto_fail = true;
                            } else {
                                s += mb_len;
                                p += 1;
                            }
                        }
                    }
                } else {
                    goto_fail = true;
                }
            }

            // Mixed character class (single-byte bitset + multibyte ranges)
            OpCode::CClassMix | OpCode::CClassMixNot => {
                let not = opcode == OpCode::CClassMixNot;
                if s >= right_range {
                    goto_fail = true;
                } else if let OperationPayload::CClassMix { ref bsp, ref mb } = reg.ops[p].payload {
                    let b = str_data[s];
                    if b < 0x80 {
                        let in_class = bitset_at(bsp, b as usize);
                        if in_class == not {
                            goto_fail = true;
                        } else {
                            s += 1;
                            p += 1;
                        }
                    } else {
                        let len = enclen(enc, str_data, s);
                        if s + len > right_range {
                            if not {
                                // Keep CClassMixNot consistent with CClassMbNot
                                // and consume the trailing truncated character.
                                s = right_range;
                                p += 1;
                            } else {
                                goto_fail = true;
                            }
                        } else {
                            let in_class = if len == 1 {
                                bitset_at(bsp, b as usize)
                            } else {
                                let code = enc.mbc_to_code(&str_data[s..], end.saturating_sub(s));
                                if is_in_code_range(mb, code) {
                                    true
                                } else if (code as usize) < SINGLE_BYTE_SIZE {
                                    bitset_at(bsp, code as usize)
                                } else {
                                    false
                                }
                            };
                            if in_class == not {
                                goto_fail = true;
                            } else {
                                s += len;
                                p += 1;
                            }
                        }
                    }
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_ANYCHAR / OP_ANYCHAR_ML - match any character
            // ================================================================
            OpCode::AnyChar => {
                if right_range.saturating_sub(s) < 1 {
                    goto_fail = true;
                } else {
                    let n = enclen(enc, str_data, s);
                    if right_range.saturating_sub(s) < n {
                        goto_fail = true;
                    } else if enc.is_mbc_newline(&str_data[s..], end) {
                        goto_fail = true; // ANYCHAR doesn't match newline
                    } else {
                        s += n;
                        p += 1;
                    }
                }
            }

            OpCode::AnyCharMl => {
                if right_range.saturating_sub(s) < 1 {
                    goto_fail = true;
                } else {
                    let n = enclen(enc, str_data, s);
                    if right_range.saturating_sub(s) < n {
                        goto_fail = true;
                    } else {
                        s += n; // ANYCHAR_ML matches newlines too
                        p += 1;
                    }
                }
            }

            // ================================================================
            // OP_ANYCHAR_STAR / OP_ANYCHAR_ML_STAR - .* optimization
            // ================================================================
            OpCode::AnyCharStar => {
                // Use SIMD to find newline boundary, then push Alt entries up to that point.
                // In UTF-8/ASCII, 0x0a can only appear as a complete single-byte character,
                // so memchr finds the exact newline position.
                let nl_limit =
                    memchr::memchr(b'\n', &str_data[s..right_range]).map_or(right_range, |i| s + i);
                while s < nl_limit {
                    let n = enclen(enc, str_data, s);
                    if s + n > nl_limit {
                        break;
                    }
                    stack.push(StackEntry::Alt {
                        pcode: p + 1,
                        pstr: s,
                        zid: -1,
                        is_super: false,
                    });
                    s += n;
                }
                p += 1;
            }

            OpCode::AnyCharMlStar => {
                while s < right_range {
                    let n = enclen(enc, str_data, s);
                    if s + n > right_range {
                        break;
                    }
                    stack.push(StackEntry::Alt {
                        pcode: p + 1,
                        pstr: s,
                        zid: -1,
                        is_super: false,
                    });
                    s += n;
                }
                p += 1;
            }

            OpCode::AnyCharStarPeekNext => {
                if let OperationPayload::AnyCharStarPeekNext { c } = reg.ops[p].payload {
                    // Find newline boundary with SIMD
                    let nl_limit = memchr::memchr(b'\n', &str_data[s..right_range])
                        .map_or(right_range, |i| s + i);
                    if c < 0x80 {
                        // ASCII peek byte: use SIMD to find all occurrences directly.
                        // In UTF-8, bytes < 0x80 can only be leading (single-byte) characters,
                        // so every memchr hit is a valid character start.
                        let mut iter_pos = s;
                        while let Some(i) = memchr::memchr(c, &str_data[iter_pos..nl_limit]) {
                            let pos = iter_pos + i;
                            stack.push(StackEntry::Alt {
                                pcode: p + 1,
                                pstr: pos,
                                zid: -1,
                                is_super: false,
                            });
                            iter_pos = pos + 1;
                        }
                        s = nl_limit;
                    } else {
                        // Non-ASCII peek: fall back to per-character loop
                        while s < nl_limit {
                            let n = enclen(enc, str_data, s);
                            if s + n > nl_limit {
                                break;
                            }
                            if s < end && str_data[s] == c {
                                stack.push(StackEntry::Alt {
                                    pcode: p + 1,
                                    pstr: s,
                                    zid: -1,
                                    is_super: false,
                                });
                            }
                            s += n;
                        }
                    }
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            OpCode::AnyCharMlStarPeekNext => {
                if let OperationPayload::AnyCharStarPeekNext { c } = reg.ops[p].payload {
                    if c < 0x80 {
                        // ASCII peek byte: use SIMD to find all occurrences directly.
                        // No newline check needed in multiline mode.
                        let mut iter_pos = s;
                        while let Some(i) = memchr::memchr(c, &str_data[iter_pos..right_range]) {
                            let pos = iter_pos + i;
                            stack.push(StackEntry::Alt {
                                pcode: p + 1,
                                pstr: pos,
                                zid: -1,
                                is_super: false,
                            });
                            iter_pos = pos + 1;
                        }
                        s = right_range;
                    } else {
                        // Non-ASCII peek: fall back to per-character loop
                        while s < right_range {
                            let n = enclen(enc, str_data, s);
                            if s + n > right_range {
                                break;
                            }
                            if s < end && str_data[s] == c {
                                stack.push(StackEntry::Alt {
                                    pcode: p + 1,
                                    pstr: s,
                                    zid: -1,
                                    is_super: false,
                                });
                            }
                            s += n;
                        }
                    }
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // CClass star opcodes - greedy [class]* / [class]+ optimization
            // ================================================================
            OpCode::CClassStar => {
                if let OperationPayload::CClass {
                    ref bsp,
                    ascii_fast,
                } = reg.ops[p].payload
                {
                    let start = s;
                    match ascii_fast {
                        CClassAsciiFastKind::Eq(c) => {
                            while s < right_range {
                                if str_data[s] != c {
                                    break;
                                }
                                s += 1;
                            }
                        }
                        CClassAsciiFastKind::EqFoldLower(lower) => {
                            while s < right_range {
                                let c = str_data[s];
                                if c >= 0x80 || (c | 0x20) != lower {
                                    break;
                                }
                                s += 1;
                            }
                        }
                        CClassAsciiFastKind::None => {
                            while s < right_range {
                                let c = str_data[s];
                                if !bitset_at(bsp, c as usize) {
                                    break;
                                }
                                s += 1;
                            }
                        }
                    }
                    if s > start {
                        stack.push(StackEntry::AltLazy {
                            pcode: p + 1,
                            pstr: s - 1,
                            pstr_start: start,
                            ascii: true,
                            peek_byte: 0,
                        });
                    }
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            OpCode::CClassMixStar => {
                if let OperationPayload::CClassMix { ref bsp, ref mb } = reg.ops[p].payload {
                    let start = s;
                    let mut exact_heads = true;
                    while s < right_range {
                        let b = str_data[s];
                        if b < 0x80 {
                            if !bitset_at(bsp, b as usize) {
                                break;
                            }
                            s += 1;
                            continue;
                        }

                        let len = enclen(enc, str_data, s);
                        if s + len > right_range {
                            break;
                        }

                        let in_class = if len == 1 {
                            bitset_at(bsp, b as usize)
                        } else {
                            let code = enc.mbc_to_code(&str_data[s..], end.saturating_sub(s));
                            if is_in_code_range(mb, code) {
                                true
                            } else if (code as usize) < SINGLE_BYTE_SIZE {
                                bitset_at(bsp, code as usize)
                            } else {
                                false
                            }
                        };
                        if !in_class {
                            break;
                        }
                        exact_heads &= steps_back_to(enc, str_data, start, s, s + len);
                        s += len;
                    }
                    push_char_run(
                        &mut stack,
                        p + 1,
                        enc,
                        str_data,
                        start,
                        s,
                        false,
                        exact_heads,
                    );
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            OpCode::CClassMbStar => {
                if let OperationPayload::CClassMb { ref mb } = reg.ops[p].payload {
                    let start = s;
                    let mut exact_heads = true;
                    while s < right_range {
                        let mb_len = enclen(enc, str_data, s);
                        if s + mb_len > right_range {
                            break;
                        }
                        let code = enc.mbc_to_code(&str_data[s..], end.saturating_sub(s));
                        if !is_in_code_range(mb, code) {
                            break;
                        }
                        if str_data[s] >= 0x80 {
                            exact_heads &= steps_back_to(enc, str_data, start, s, s + mb_len);
                        }
                        s += mb_len;
                    }
                    push_char_run(
                        &mut stack,
                        p + 1,
                        enc,
                        str_data,
                        start,
                        s,
                        false,
                        exact_heads,
                    );
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            // Negated class star opcodes: each mirrors its single-character
            // opcode (CClassNot / CClassMbNot / CClassMixNot) per character.
            OpCode::CClassNotStar => {
                if let OperationPayload::CClass {
                    ref bsp,
                    ascii_fast,
                } = reg.ops[p].payload
                {
                    let excluded = |b: u8| match ascii_fast {
                        CClassAsciiFastKind::Eq(c) => b == c,
                        CClassAsciiFastKind::EqFoldLower(lower) => b < 0x80 && (b | 0x20) == lower,
                        CClassAsciiFastKind::None => bitset_at(bsp, b as usize),
                    };
                    s = greedy_char_loop(
                        &mut stack,
                        p + 1,
                        enc,
                        str_data,
                        s,
                        right_range,
                        |b| !excluded(b),
                        |x| {
                            (!excluded(str_data[x]))
                                .then(|| advance_char_to_end(enc, str_data, x, end))
                        },
                    );
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            OpCode::CClassMbNotStar => {
                if let OperationPayload::CClassMb { ref mb } = reg.ops[p].payload {
                    s = greedy_char_loop(
                        &mut stack,
                        p + 1,
                        enc,
                        str_data,
                        s,
                        right_range,
                        |b| !is_in_code_range(mb, b as OnigCodePoint),
                        |x| {
                            let mb_len = enclen(enc, str_data, x);
                            if x + mb_len > right_range {
                                // A truncated character matches a negated class.
                                return Some(right_range);
                            }
                            let code = enc.mbc_to_code(&str_data[x..], end.saturating_sub(x));
                            (!is_in_code_range(mb, code)).then_some(x + mb_len)
                        },
                    );
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            OpCode::CClassMixNotStar => {
                if let OperationPayload::CClassMix { ref bsp, ref mb } = reg.ops[p].payload {
                    s = greedy_char_loop(
                        &mut stack,
                        p + 1,
                        enc,
                        str_data,
                        s,
                        right_range,
                        |b| !bitset_at(bsp, b as usize),
                        |x| {
                            let b = str_data[x];
                            let len = enclen(enc, str_data, x);
                            if x + len > right_range {
                                // A truncated character matches a negated class.
                                return Some(right_range);
                            }
                            let in_class = if len == 1 {
                                bitset_at(bsp, b as usize)
                            } else {
                                let code = enc.mbc_to_code(&str_data[x..], end.saturating_sub(x));
                                is_in_code_range(mb, code)
                                    || ((code as usize) < SINGLE_BYTE_SIZE
                                        && bitset_at(bsp, code as usize))
                            };
                            (!in_class).then_some(x + len)
                        },
                    );
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // Word star opcodes - greedy \w* / \w+ optimization
            // ================================================================
            OpCode::WordStar => {
                let start = s;
                if enc_is_singlebyte(enc) {
                    while s < right_range {
                        if !is_word_char_at(enc, str_data, s, end) {
                            break;
                        }
                        s += 1;
                    }
                    if s > start {
                        stack.push(StackEntry::AltLazy {
                            pcode: p + 1,
                            pstr: s - 1,
                            pstr_start: start,
                            ascii: true,
                            peek_byte: 0,
                        });
                    }
                } else if onigenc_is_ascii_compatible_encoding(enc) {
                    let mut ascii_only = true;
                    let mut exact_heads = true;
                    while s < right_range {
                        let b = str_data[s];
                        if b < 0x80 {
                            if !is_word_ascii(b) {
                                break;
                            }
                            s += 1;
                        } else {
                            if !is_word_char_at(enc, str_data, s, end) {
                                break;
                            }
                            ascii_only = false;
                            let next = advance_char_to_end(enc, str_data, s, end);
                            exact_heads &= steps_back_to(enc, str_data, start, s, next);
                            s = next;
                        }
                    }
                    push_char_run(
                        &mut stack,
                        p + 1,
                        enc,
                        str_data,
                        start,
                        s,
                        ascii_only,
                        exact_heads,
                    );
                } else {
                    let mut exact_heads = true;
                    while s < right_range {
                        if !is_word_char_at(enc, str_data, s, end) {
                            break;
                        }
                        let next = advance_char_to_end(enc, str_data, s, end);
                        exact_heads &= steps_back_to(enc, str_data, start, s, next);
                        s = next;
                    }
                    push_char_run(
                        &mut stack,
                        p + 1,
                        enc,
                        str_data,
                        start,
                        s,
                        false,
                        exact_heads,
                    );
                }
                p += 1;
            }

            OpCode::WordAsciiStar => {
                let start = s;
                while s < right_range {
                    if !is_word_ascii(str_data[s]) {
                        break;
                    }
                    s += 1;
                }
                if s > start {
                    stack.push(StackEntry::AltLazy {
                        pcode: p + 1,
                        pstr: s - 1,
                        pstr_start: start,
                        ascii: true,
                        peek_byte: 0,
                    });
                }
                p += 1;
            }

            // ================================================================
            // PeekNext star variants - only backtrack to positions matching peek byte
            // ================================================================
            OpCode::CClassStarPeekNext => {
                if let OperationPayload::CClassStarPeekNext { ref bsp, c } = reg.ops[p].payload {
                    let start = s;
                    while s < right_range {
                        let ch = str_data[s];
                        if !bitset_at(bsp, ch as usize) {
                            break;
                        }
                        s += 1;
                    }
                    if s > start {
                        stack.push(StackEntry::AltLazy {
                            pcode: p + 1,
                            pstr: s - 1,
                            pstr_start: start,
                            ascii: true,
                            peek_byte: c,
                        });
                    }
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            OpCode::WordAsciiStarPeekNext => {
                if let OperationPayload::WordAsciiStarPeekNext { c } = reg.ops[p].payload {
                    let start = s;
                    while s < right_range {
                        if !is_word_ascii(str_data[s]) {
                            break;
                        }
                        s += 1;
                    }
                    if s > start {
                        stack.push(StackEntry::AltLazy {
                            pcode: p + 1,
                            pstr: s - 1,
                            pstr_start: start,
                            ascii: true,
                            peek_byte: c,
                        });
                    }
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // Word / NoWord - \w and \W character type matching
            // ================================================================
            OpCode::Word => {
                if s >= right_range || !is_word_char_at(enc, str_data, s, end) {
                    goto_fail = true;
                } else {
                    s = advance_char_to_end(enc, str_data, s, end);
                    p += 1;
                }
            }

            OpCode::WordAscii => {
                if s >= right_range || !is_word_ascii(str_data[s]) {
                    goto_fail = true;
                } else {
                    s += 1;
                    p += 1;
                }
            }

            OpCode::NoWord => {
                if s >= right_range || is_word_char_at(enc, str_data, s, end) {
                    goto_fail = true;
                } else {
                    s = advance_char_to_end(enc, str_data, s, end);
                    p += 1;
                }
            }

            OpCode::NoWordAscii => {
                if s >= right_range || is_word_ascii(str_data[s]) {
                    goto_fail = true;
                } else {
                    s = advance_char_to_end(enc, str_data, s, end);
                    p += 1;
                }
            }

            // ================================================================
            // Word boundary opcodes
            // ================================================================
            OpCode::WordBoundary => {
                let mode = if let OperationPayload::WordBoundary { mode } = reg.ops[p].payload {
                    mode
                } else {
                    0
                };
                if !is_word_boundary(enc, str_data, s, end, mode) {
                    goto_fail = true;
                } else {
                    p += 1;
                }
            }

            OpCode::NoWordBoundary => {
                let mode = if let OperationPayload::WordBoundary { mode } = reg.ops[p].payload {
                    mode
                } else {
                    0
                };
                if is_word_boundary(enc, str_data, s, end, mode) {
                    goto_fail = true;
                } else {
                    p += 1;
                }
            }

            OpCode::WordBegin => {
                let mode = if let OperationPayload::WordBoundary { mode } = reg.ops[p].payload {
                    mode
                } else {
                    0
                };
                if !is_word_begin(enc, str_data, s, end, mode) {
                    goto_fail = true;
                } else {
                    p += 1;
                }
            }

            OpCode::WordEnd => {
                let mode = if let OperationPayload::WordBoundary { mode } = reg.ops[p].payload {
                    mode
                } else {
                    0
                };
                if !is_word_end(enc, str_data, s, end, mode) {
                    goto_fail = true;
                } else {
                    p += 1;
                }
            }

            OpCode::TextSegmentBoundary => {
                if let OperationPayload::TextSegmentBoundary { boundary_type, not } =
                    reg.ops[p].payload
                {
                    let is_break = match boundary_type {
                        TextSegmentBoundaryType::ExtendedGraphemeCluster => {
                            crate::unicode::onigenc_egcb_is_break_position(enc, str_data, s, 0, end)
                        }
                        TextSegmentBoundaryType::Word => {
                            crate::unicode::onigenc_wb_is_break_position(enc, str_data, s, 0, end)
                        }
                    };
                    let result = if not { !is_break } else { is_break };
                    if result {
                        p += 1;
                    } else {
                        goto_fail = true;
                    }
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // Position anchors
            // ================================================================
            OpCode::BeginBuf => {
                if s != 0 || opton_notbol(options) || opton_not_begin_string(options) {
                    goto_fail = true;
                } else {
                    p += 1;
                }
            }

            OpCode::EndBuf => {
                if s != end || opton_noteol(options) || opton_not_end_string(options) {
                    goto_fail = true;
                } else {
                    p += 1;
                }
            }

            OpCode::BeginLine => {
                if s == 0 {
                    if opton_notbol(options) {
                        goto_fail = true;
                    } else {
                        p += 1;
                    }
                } else if s != end {
                    // C: `else if (! ON_STR_END(s))` -- a newline at the very
                    // end of the subject does not start another line.
                    let sprev = onigenc_get_prev_char_head(enc, str_data, 0, s);
                    if enc.is_mbc_newline(&str_data[sprev..], end) {
                        p += 1;
                    } else {
                        goto_fail = true;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::EndLine => {
                if s == end {
                    if opton_noteol(options) {
                        goto_fail = true;
                    } else {
                        p += 1;
                    }
                } else if enc.is_mbc_newline(&str_data[s..], end) {
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            OpCode::SemiEndBuf => {
                // Match end of string or before final newline
                let is_before_end = s == end || (s + 1 == end && str_data[s] == b'\n');
                if !is_before_end || opton_noteol(options) || opton_not_end_string(options) {
                    goto_fail = true;
                } else {
                    p += 1;
                }
            }

            OpCode::CheckPosition => {
                if let OperationPayload::CheckPosition { check_type } = reg.ops[p].payload {
                    match check_type {
                        CheckPositionType::SearchStart => {
                            if s != msa.start || opton_not_begin_position(options) {
                                goto_fail = true;
                            } else {
                                p += 1;
                            }
                        }
                        CheckPositionType::CurrentRightRange => {
                            if s != right_range {
                                goto_fail = true;
                            } else {
                                p += 1;
                            }
                        }
                    }
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // Back references
            // ================================================================
            OpCode::BackRef1 => {
                if num_mem < 1 {
                    goto_fail = true;
                } else if let (Some(ms), Some(me)) = (
                    get_mem_start(reg, &stack, &mem_start_stk, 1),
                    get_mem_end(reg, &stack, &mem_end_stk, 1),
                ) {
                    let ref_len = me.saturating_sub(ms); // C: a negative n matches empty
                    if right_range.saturating_sub(s) < ref_len
                        || str_data[s..s + ref_len] != str_data[ms..ms + ref_len]
                    {
                        goto_fail = true;
                    } else {
                        s += ref_len;
                        p += 1;
                    }
                } else if (reg.syntax.behavior & FERRONI_SYN_UNMATCHED_BACKREF_MATCHES_EMPTY) != 0 {
                    p += 1;
                } else {
                    goto_fail = true; // group not yet matched
                }
            }

            OpCode::BackRef2 => {
                if num_mem < 2 {
                    goto_fail = true;
                } else if let (Some(ms), Some(me)) = (
                    get_mem_start(reg, &stack, &mem_start_stk, 2),
                    get_mem_end(reg, &stack, &mem_end_stk, 2),
                ) {
                    let ref_len = me.saturating_sub(ms); // C: a negative n matches empty
                    if right_range.saturating_sub(s) < ref_len
                        || str_data[s..s + ref_len] != str_data[ms..ms + ref_len]
                    {
                        goto_fail = true;
                    } else {
                        s += ref_len;
                        p += 1;
                    }
                } else if (reg.syntax.behavior & FERRONI_SYN_UNMATCHED_BACKREF_MATCHES_EMPTY) != 0 {
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            OpCode::BackRefN => {
                if let OperationPayload::BackRefN { n1 } = reg.ops[p].payload {
                    let n1 = n1 as usize;
                    if n1 > num_mem {
                        goto_fail = true;
                    } else if let (Some(ms), Some(me)) = (
                        get_mem_start(reg, &stack, &mem_start_stk, n1),
                        get_mem_end(reg, &stack, &mem_end_stk, n1),
                    ) {
                        let ref_len = me.saturating_sub(ms); // C: a negative n matches empty
                        if right_range.saturating_sub(s) < ref_len
                            || str_data[s..s + ref_len] != str_data[ms..ms + ref_len]
                        {
                            goto_fail = true;
                        } else {
                            s += ref_len;
                            p += 1;
                        }
                    } else if (reg.syntax.behavior & FERRONI_SYN_UNMATCHED_BACKREF_MATCHES_EMPTY)
                        != 0
                    {
                        p += 1;
                    } else {
                        goto_fail = true;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::BackRefNIc => {
                if let OperationPayload::BackRefN { n1 } = reg.ops[p].payload {
                    let n1 = n1 as usize;
                    if n1 > num_mem {
                        goto_fail = true;
                    } else if let (Some(ms), Some(me)) = (
                        get_mem_start(reg, &stack, &mem_start_stk, n1),
                        get_mem_end(reg, &stack, &mem_end_stk, n1),
                    ) {
                        let ref_len = me.saturating_sub(ms); // C: a negative n matches empty
                        if ref_len != 0
                            && (right_range.saturating_sub(s) < ref_len
                                || !string_cmp_ic(
                                    enc,
                                    reg.case_fold_flag,
                                    str_data,
                                    ms,
                                    &mut s,
                                    ref_len,
                                ))
                        {
                            goto_fail = true;
                        } else {
                            p += 1;
                        }
                    } else if (reg.syntax.behavior & FERRONI_SYN_UNMATCHED_BACKREF_MATCHES_EMPTY)
                        != 0
                    {
                        p += 1;
                    } else {
                        goto_fail = true;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::BackRefMulti => {
                if let OperationPayload::BackRefGeneral { num, ns, .. } = &reg.ops[p].payload {
                    let tlen = *num as usize;
                    let mut matched = false;
                    let mut participated = false;
                    for mem in ns.iter().take(tlen).map(|mem| *mem as usize) {
                        if mem > num_mem {
                            continue;
                        }
                        if let (Some(ms), Some(me)) = (
                            get_mem_start(reg, &stack, &mem_start_stk, mem),
                            get_mem_end(reg, &stack, &mem_end_stk, mem),
                        ) {
                            participated = true;
                            let ref_len = me.saturating_sub(ms); // C: a negative n matches empty
                            if ref_len != 0 {
                                if right_range.saturating_sub(s) < ref_len {
                                    continue;
                                }
                                if str_data[s..s + ref_len] != str_data[ms..ms + ref_len] {
                                    continue;
                                }
                                s += ref_len;
                            }
                            matched = true;
                            break;
                        }
                    }
                    if !participated
                        && (reg.syntax.behavior & FERRONI_SYN_UNMATCHED_BACKREF_MATCHES_EMPTY) != 0
                    {
                        matched = true;
                    }
                    if matched {
                        p += 1;
                    } else {
                        goto_fail = true;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::BackRefMultiIc => {
                if let OperationPayload::BackRefGeneral { num, ns, .. } = &reg.ops[p].payload {
                    let tlen = *num as usize;
                    let mut matched = false;
                    let mut participated = false;
                    for mem in ns.iter().take(tlen).map(|mem| *mem as usize) {
                        if mem > num_mem {
                            continue;
                        }
                        if let (Some(ms), Some(me)) = (
                            get_mem_start(reg, &stack, &mem_start_stk, mem),
                            get_mem_end(reg, &stack, &mem_end_stk, mem),
                        ) {
                            participated = true;
                            let ref_len = me.saturating_sub(ms); // C: a negative n matches empty
                            if ref_len != 0 {
                                if right_range.saturating_sub(s) < ref_len {
                                    continue;
                                }
                                let mut swork = s;
                                if !string_cmp_ic(
                                    enc,
                                    reg.case_fold_flag,
                                    str_data,
                                    ms,
                                    &mut swork,
                                    ref_len,
                                ) {
                                    continue;
                                }
                                s = swork;
                            }
                            matched = true;
                            break;
                        }
                    }
                    if !participated
                        && (reg.syntax.behavior & FERRONI_SYN_UNMATCHED_BACKREF_MATCHES_EMPTY) != 0
                    {
                        matched = true;
                    }
                    if matched {
                        p += 1;
                    } else {
                        goto_fail = true;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::BackRefCheck => {
                if let OperationPayload::BackRefGeneral { num, ns, .. } = &reg.ops[p].payload {
                    let tlen = *num as usize;
                    let mut found = false;
                    for mem in ns.iter().take(tlen).map(|mem| *mem as usize) {
                        if mem > num_mem {
                            continue;
                        }
                        if get_mem_start(reg, &stack, &mem_start_stk, mem).is_some()
                            && get_mem_end(reg, &stack, &mem_end_stk, mem).is_some()
                        {
                            found = true;
                            break;
                        }
                    }
                    if found {
                        p += 1;
                    } else {
                        goto_fail = true;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::BackRefWithLevel | OpCode::BackRefWithLevelIc => {
                if let OperationPayload::BackRefGeneral {
                    num,
                    ns,
                    nest_level,
                } = &reg.ops[p].payload
                {
                    let ignore_case = reg.ops[p].opcode == OpCode::BackRefWithLevelIc;
                    if backref_match_at_nested_level(
                        reg,
                        &stack,
                        ignore_case,
                        reg.case_fold_flag,
                        *nest_level,
                        *num,
                        ns,
                        &mut s,
                        str_data,
                        end,
                    ) {
                        p += 1;
                    } else {
                        goto_fail = true;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::BackRefCheckWithLevel => {
                if let OperationPayload::BackRefGeneral {
                    num,
                    ns,
                    nest_level,
                } = &reg.ops[p].payload
                {
                    let found = if backref_check_at_nested_level(&stack, *nest_level, *num, ns) {
                        true
                    } else if *nest_level == 0 {
                        // At level 0, also check mem arrays directly (group may use
                        // non-push MemStart with no stack entry)
                        let tlen = *num as usize;
                        let mut f = false;
                        for mem in ns.iter().take(tlen).map(|mem| *mem as usize) {
                            if mem > num_mem {
                                continue;
                            }
                            if get_mem_start(reg, &stack, &mem_start_stk, mem).is_some()
                                && get_mem_end(reg, &stack, &mem_end_stk, mem).is_some()
                            {
                                f = true;
                                break;
                            }
                        }
                        f
                    } else {
                        false
                    };
                    if found {
                        p += 1;
                    } else {
                        goto_fail = true;
                    }
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // Memory (capture group) operations
            // ================================================================
            OpCode::MemStart => {
                if let OperationPayload::MemoryStart { num } = reg.ops[p].payload {
                    // C sets only the start (regexec.c OP_MEM_START); the end
                    // of an earlier pass stays in place until MEM_END, so a
                    // capture can read as start > end if the pass fails.
                    if TRACK_CAPTURES {
                        mem_start_stk[num as usize] = MemPtr::pos(s);
                    }
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            OpCode::MemStartPush => {
                if let OperationPayload::MemoryStart { num } = reg.ops[p].payload {
                    // The pushed entry only restores this capture on
                    // backtracking. Opcodes that read captures while matching
                    // force TRACK_CAPTURES (see `needs_capture_tracking`), so
                    // an untracked run can drop the bookkeeping.
                    if TRACK_CAPTURES {
                        let num = num as usize;
                        let prev_start = mem_start_stk[num];
                        let prev_end = mem_end_stk[num];
                        let si = stack.len();
                        stack.push(StackEntry::MemStart {
                            zid: num,
                            pstr: s,
                            prev_start,
                            prev_end,
                        });
                        mem_start_stk[num] = MemPtr::stack_idx(si);
                        mem_end_stk[num] = MemPtr::invalid();
                    }
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            OpCode::MemEnd => {
                if let OperationPayload::MemoryEnd { num } = reg.ops[p].payload {
                    if TRACK_CAPTURES {
                        let num = num as usize;
                        mem_end_stk[num] = MemPtr::pos(s);
                    }
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            OpCode::MemEndPush => {
                if let OperationPayload::MemoryEnd { num } = reg.ops[p].payload {
                    // See OpCode::MemStartPush for why untracked runs skip this.
                    if TRACK_CAPTURES {
                        let num = num as usize;
                        let prev_start = mem_start_stk[num];
                        let prev_end = mem_end_stk[num];
                        let si = stack.len();
                        stack.push(StackEntry::MemEnd {
                            zid: num,
                            pstr: s,
                            prev_start,
                            prev_end,
                        });
                        mem_end_stk[num] = MemPtr::stack_idx(si);
                    }
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            OpCode::MemEndPushRec => {
                // Recursive capture end (push variant): find matching MEM_START,
                // push MEM_END, update start/end tracking
                if let OperationPayload::MemoryEnd { num } = reg.ops[p].payload {
                    let mem = num as usize;
                    let (start_ptr, _) =
                        stack_get_mem_start_for_rec(&stack, mem, reg.push_mem_start);
                    let si = stack.len();
                    stack.push(StackEntry::MemEnd {
                        zid: mem,
                        pstr: s,
                        prev_start: mem_start_stk[mem],
                        prev_end: mem_end_stk[mem],
                    });
                    mem_start_stk[mem] = start_ptr;
                    mem_end_stk[mem] = MemPtr::stack_idx(si);
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            OpCode::MemEndRec => {
                // Recursive capture end (non-push variant): find matching MEM_START,
                // update start/end, push MemEndMark for level tracking
                if let OperationPayload::MemoryEnd { num } = reg.ops[p].payload {
                    let mem = num as usize;
                    mem_end_stk[mem] = MemPtr::pos(s);
                    let (start_ptr, _) =
                        stack_get_mem_start_for_rec(&stack, mem, reg.push_mem_start);
                    mem_start_stk[mem] = start_ptr;
                    stack.push(StackEntry::MemEndMark { zid: mem });
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_FAIL - backtrack
            // ================================================================
            OpCode::Fail => {
                goto_fail = true;
            }

            // ================================================================
            // OP_JUMP - unconditional jump
            // ================================================================
            OpCode::Jump => {
                if let OperationPayload::Jump { addr } = reg.ops[p].payload {
                    p = (p as i32 + addr) as usize;
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_PUSH / OP_PUSH_SUPER - push choice point (alternation)
            // ================================================================
            OpCode::Push | OpCode::PushSuper => {
                if let OperationPayload::Push { addr } = reg.ops[p].payload {
                    let alt_target = (p as i32 + addr) as usize;
                    let is_super = reg.ops[p].opcode == OpCode::PushSuper;
                    stack.push(StackEntry::Alt {
                        pcode: alt_target,
                        pstr: s,
                        zid: -1,
                        is_super,
                    });
                    p += 1; // try main path first
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_POP - discard top stack entry
            // ================================================================
            OpCode::Pop => {
                stack.pop();
                p += 1;
            }

            // ================================================================
            // OP_POP_TO_MARK - pop until Mark with matching id
            // ================================================================
            OpCode::PopToMark => {
                if let OperationPayload::PopToMark { id } = reg.ops[p].payload {
                    stack_pop_to_mark(
                        &mut stack,
                        id as usize,
                        &mut mem_start_stk,
                        &mut mem_end_stk,
                        &mut subexp_call_nest_counter,
                    );
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_PUSH_OR_JUMP_EXACT1 - optimized push for exact char
            // ================================================================
            OpCode::PushOrJumpExact1 => {
                if let OperationPayload::PushOrJumpExact1 { addr, c } = reg.ops[p].payload {
                    if s < right_range && str_data[s] == c {
                        // Character matches: push alternative and continue
                        let alt_target = (p as i32 + addr) as usize;
                        stack.push(StackEntry::Alt {
                            pcode: alt_target,
                            pstr: s,
                            zid: -1,
                            is_super: false,
                        });
                        p += 1;
                    } else {
                        // Character doesn't match: jump
                        p = (p as i32 + addr) as usize;
                    }
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // Rust-only (ADR-008): PUSH_OR_JUMP_EXACT1 with a byte set
            // ================================================================
            OpCode::PushOrJumpByteSet => {
                if let OperationPayload::PushOrJumpByteSet { addr, ref bsp } = reg.ops[p].payload {
                    if s < right_range && bitset_at(bsp, str_data[s] as usize) {
                        stack.push(StackEntry::Alt {
                            pcode: (p as i32 + addr) as usize,
                            pstr: s,
                            zid: -1,
                            is_super: false,
                        });
                        p += 1;
                    } else {
                        p = (p as i32 + addr) as usize;
                    }
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_PUSH_IF_PEEK_NEXT - push only if next char matches
            // ================================================================
            OpCode::PushIfPeekNext => {
                if let OperationPayload::PushIfPeekNext { addr, c } = reg.ops[p].payload {
                    if s < right_range && str_data[s] == c {
                        let alt_target = (p as i32 + addr) as usize;
                        stack.push(StackEntry::Alt {
                            pcode: alt_target,
                            pstr: s,
                            zid: -1,
                            is_super: false,
                        });
                    }
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_REPEAT / OP_REPEAT_NG - initialize repeat counter
            // ================================================================
            OpCode::Repeat | OpCode::RepeatNg => {
                if let OperationPayload::Repeat { id, addr } = reg.ops[p].payload {
                    let id = id as usize;
                    // Push initial repeat count = 0
                    stack.push(StackEntry::RepeatInc { zid: id, count: 0 });

                    if reg.repeat_range[id].lower == 0 {
                        // Can skip the loop body entirely
                        let alt_target = (p as i32 + addr) as usize;
                        if opcode == OpCode::Repeat {
                            // Greedy: push skip as alternative, try body first
                            stack.push(StackEntry::Alt {
                                pcode: alt_target,
                                pstr: s,
                                zid: -1,
                                is_super: false,
                            });
                        } else {
                            // Non-greedy: push body as alternative, try skip first
                            stack.push(StackEntry::Alt {
                                pcode: p + 1,
                                pstr: s,
                                zid: -1,
                                is_super: false,
                            });
                            p = alt_target;
                            continue;
                        }
                    }
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_REPEAT_INC / OP_REPEAT_INC_NG - increment and check repeat
            // ================================================================
            OpCode::RepeatInc => {
                if let OperationPayload::RepeatInc { id } = reg.ops[p].payload {
                    let id = id as usize;
                    let count = stack_get_repeat_count(&stack, id) + 1;
                    let lower = reg.repeat_range[id].lower;
                    let upper = reg.repeat_range[id].upper;
                    let body_start = reg.repeat_range[id].u_offset as usize;

                    // C order for greedy: branch first, then push count
                    if upper != INFINITE_REPEAT && count >= upper {
                        p += 1;
                    } else if count >= lower {
                        p += 1;
                        stack.push(StackEntry::Alt {
                            pcode: p,
                            pstr: s,
                            zid: -1,
                            is_super: false,
                        });
                        p = body_start;
                    } else {
                        p = body_start;
                    }
                    // Count pushed AFTER Alt — gets popped on backtrack (correct for greedy)
                    stack.push(StackEntry::RepeatInc { zid: id, count });
                } else {
                    goto_fail = true;
                }
            }

            OpCode::RepeatIncNg => {
                if let OperationPayload::RepeatInc { id } = reg.ops[p].payload {
                    let id = id as usize;
                    let count = stack_get_repeat_count(&stack, id) + 1;
                    let lower = reg.repeat_range[id].lower;
                    let upper = reg.repeat_range[id].upper;
                    let body_start = reg.repeat_range[id].u_offset as usize;

                    // C order for non-greedy: push count FIRST, then branch
                    // Count pushed BEFORE Alt — survives backtrack (correct for lazy)
                    stack.push(StackEntry::RepeatInc { zid: id, count });

                    if upper != INFINITE_REPEAT && count == upper {
                        p += 1;
                    } else if count >= lower {
                        stack.push(StackEntry::Alt {
                            pcode: body_start,
                            pstr: s,
                            zid: -1,
                            is_super: false,
                        });
                        p += 1;
                    } else {
                        p = body_start;
                    }
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_EMPTY_CHECK_START / END - detect empty match in loops
            // ================================================================
            OpCode::EmptyCheckStart => {
                if let OperationPayload::EmptyCheckStart { mem } = reg.ops[p].payload {
                    let mem = mem as usize;
                    stack.push(StackEntry::EmptyCheckStart { zid: mem, pstr: s });
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            OpCode::EmptyCheckEnd => {
                if let OperationPayload::EmptyCheckEnd { mem, .. } = reg.ops[p].payload {
                    let mem = mem as usize;
                    let is_empty = stack_empty_check(&stack, mem, s);
                    p += 1;
                    if is_empty {
                        // Empty loop detected — skip the next instruction
                        // (JUMP, PUSH, REPEAT_INC, or REPEAT_INC_NG) to break the loop.
                        // Mirrors C: empty_check_found: INC_OP;
                        p += 1;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::EmptyCheckEndMemst => {
                if let OperationPayload::EmptyCheckEnd {
                    mem,
                    empty_status_mem,
                } = reg.ops[p].payload
                {
                    let is_empty = stack_empty_check_mem(&stack, mem as usize, s, empty_status_mem);
                    p += 1;
                    if is_empty {
                        // Truly empty → skip next op (JUMP back)
                        p += 1;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::EmptyCheckEndMemstPush => {
                if let OperationPayload::EmptyCheckEnd {
                    mem,
                    empty_status_mem,
                } = reg.ops[p].payload
                {
                    let mem = mem as usize;
                    let is_empty = stack_empty_check_mem_rec(&stack, mem, s, empty_status_mem);
                    p += 1;
                    if is_empty {
                        // Truly empty → skip next op (JUMP back)
                        p += 1;
                    } else {
                        // C: STACK_PUSH_EMPTY_CHECK_END -- marks the iteration
                        // as complete for scans from recursive runs.
                        stack.push(StackEntry::EmptyCheckEnd { zid: mem });
                    }
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_MOVE - move string position
            // ================================================================
            OpCode::Move => {
                if let OperationPayload::Move { n } = reg.ops[p].payload {
                    if n < 0 {
                        // Step back n characters (encoding-aware)
                        match onigenc_step_back(enc, 0, s, str_data, (-n) as usize) {
                            Some(new_s) => {
                                s = new_s;
                                p += 1;
                            }
                            None => {
                                goto_fail = true;
                            }
                        }
                    } else {
                        // Step forward n characters
                        match onigenc_step(enc, s, end, str_data, n as usize) {
                            Some(new_s) => {
                                s = new_s;
                                p += 1;
                            }
                            None => {
                                goto_fail = true;
                            }
                        }
                    }
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // Rust-only (ADR-008): a look-behind with a one-instruction body
            // ================================================================
            OpCode::LookBehindOp => {
                if let OperationPayload::LookBehindOp { char_len, not } = reg.ops[p].payload {
                    let matched = look_behind_body_matches(
                        &reg.ops[p + 1],
                        char_len,
                        enc,
                        str_data,
                        s,
                        right_range,
                        end,
                    );
                    if matched != not {
                        p += 2;
                    } else {
                        goto_fail = true;
                    }
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_STEP_BACK_START / NEXT - lookbehind support
            // ================================================================
            OpCode::StepBackStart => {
                if let OperationPayload::StepBackStart {
                    initial,
                    remaining,
                    addr,
                } = reg.ops[p].payload
                {
                    let initial = initial as usize;
                    // Step back 'initial' characters (encoding-aware)
                    if initial != 0 {
                        match onigenc_step_back(enc, 0, s, str_data, initial) {
                            Some(new_s) => {
                                s = new_s;
                            }
                            None => {
                                goto_fail = true;
                            }
                        }
                    }
                    if !goto_fail {
                        if remaining != 0 {
                            // Variable-length: push Alt with remaining count, jump to addr
                            stack.push(StackEntry::Alt {
                                pcode: p + 1,
                                pstr: s,
                                zid: remaining,
                                is_super: false,
                            });
                            p = (p as i32 + addr) as usize;
                        } else {
                            p += 1;
                        }
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::StepBackNext => {
                // last_alt_zid was set by the backtrack that jumped here
                let mut remaining = last_alt_zid;
                if remaining != INFINITE_LEN as i32 {
                    remaining -= 1;
                }
                match onigenc_step_back(enc, 0, s, str_data, 1) {
                    Some(new_s) => {
                        s = new_s;
                    }
                    None => {
                        goto_fail = true;
                    }
                }
                if !goto_fail {
                    if remaining != 0 {
                        stack.push(StackEntry::Alt {
                            pcode: p,
                            pstr: s,
                            zid: remaining,
                            is_super: false,
                        });
                    }
                    p += 1;
                }
            }

            // ================================================================
            // OP_MARK - push a named checkpoint
            // ================================================================
            OpCode::Mark => {
                if let OperationPayload::Mark { id, save_pos } = reg.ops[p].payload {
                    let id = id as usize;
                    let pos = if save_pos { Some(s) } else { None };
                    stack.push(StackEntry::Mark { zid: id, pos });
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_CUT_TO_MARK - void entries to mark, optionally restore position
            // C always uses STACK_TO_VOID_TO_MARK (not POP_TO_MARK)
            // ================================================================
            OpCode::CutToMark => {
                if let OperationPayload::CutToMark { id, restore_pos } = reg.ops[p].payload {
                    let id = id as usize;
                    let saved_pos = stack_void_to_mark(&mut stack, id);
                    if restore_pos {
                        if let Some(pos) = saved_pos {
                            s = pos;
                        }
                    }
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_SAVE_VAL - save a value on the stack
            // ================================================================
            OpCode::SaveVal => {
                if let OperationPayload::SaveVal { save_type, id } = reg.ops[p].payload {
                    let id = id as usize;
                    let v = match save_type {
                        SaveType::Keep => s,
                        SaveType::S => s,
                        SaveType::RightRange => right_range,
                    };
                    stack.push(StackEntry::SaveVal {
                        zid: id,
                        save_type,
                        v,
                    });
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_UPDATE_VAR - update a variable from the stack
            // ================================================================
            OpCode::UpdateVar => {
                if let OperationPayload::UpdateVar {
                    var_type,
                    id,
                    clear,
                } = reg.ops[p].payload
                {
                    let id = id as usize;
                    match var_type {
                        UpdateVarType::KeepFromStackLast => {
                            if let Some(v) = stack_get_save_val_type_last(&stack, SaveType::Keep) {
                                keep = v;
                            }
                        }
                        UpdateVarType::SFromStack => {
                            if let Some(v) = stack_get_save_val_last(&stack, SaveType::S, id) {
                                s = v;
                            }
                        }
                        UpdateVarType::RightRangeFromStack => {
                            if let Some(v) =
                                stack_get_save_val_last(&stack, SaveType::RightRange, id)
                            {
                                right_range = v;
                            }
                        }
                        UpdateVarType::RightRangeFromSStack => {
                            if let Some(v) = stack_get_save_val_last(&stack, SaveType::S, id) {
                                right_range = v;
                            }
                        }
                        UpdateVarType::RightRangeToS => {
                            right_range = s;
                        }
                        UpdateVarType::RightRangeInit => {
                            right_range = in_right_range;
                        }
                    }
                    p += 1;
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // OP_CALL / OP_RETURN - subroutine call/return
            // ================================================================
            OpCode::Call => {
                if let OperationPayload::Call { addr } = reg.ops[p].payload {
                    if subexp_call_nest_counter == subexp_call_max_nest_level {
                        goto_fail = true;
                    } else {
                        subexp_call_nest_counter += 1;
                        if subexp_call_limit_in_search != 0 {
                            msa.subexp_call_in_search_counter += 1;
                            if msa.subexp_call_in_search_counter > subexp_call_limit_in_search {
                                best_len = ONIGERR_SUBEXP_CALL_LIMIT_IN_SEARCH_OVER;
                                break;
                            }
                        }
                        let addr = addr as usize;
                        stack.push(StackEntry::CallFrame { ret_addr: p + 1 });
                        p = addr;
                    }
                } else {
                    goto_fail = true;
                }
            }

            OpCode::Return => {
                // Search backwards for CallFrame, skipping nested Return markers.
                // Each STK_RETURN increments the level; each STK_CALL_FRAME decrements.
                let mut level = 0i32;
                let mut ret_addr = None;
                for i in (0..stack.len()).rev() {
                    match &stack[i] {
                        StackEntry::CallFrame { ret_addr: ra } => {
                            if level == 0 {
                                ret_addr = Some(*ra);
                                break;
                            }
                            level -= 1;
                        }
                        StackEntry::Return => {
                            level += 1;
                        }
                        _ => {}
                    }
                }
                if let Some(ra) = ret_addr {
                    stack.push(StackEntry::Return);
                    subexp_call_nest_counter = subexp_call_nest_counter.wrapping_sub(1);
                    p = ra;
                } else {
                    goto_fail = true;
                }
            }

            // ================================================================
            // Callout opcodes
            // ================================================================
            OpCode::CalloutContents => {
                // Callout of contents: always succeeds (we don't execute user code)
                let num = match &reg.ops[p].payload {
                    OperationPayload::CalloutContents { num } => *num,
                    _ => 0,
                };
                if let Some(ref ext) = reg.extp {
                    if num >= 1 && (num as usize) <= ext.callout_list.len() {
                        let entry = &ext.callout_list[(num - 1) as usize];
                        if (entry.callout_in & CALLOUT_IN_RETRACTION) != 0 {
                            stack.push(StackEntry::Callout {
                                num,
                                id: ONIG_NON_NAME_ID,
                            });
                        }
                    }
                }
                p += 1;
            }
            OpCode::AltLiterals => {
                if let OperationPayload::AltLiterals { trie_idx } = reg.ops[p].payload {
                    let trie = &reg.literal_tries[trie_idx as usize];
                    if let Some(match_len) =
                        match_literal_trie(&mut stack, trie, str_data, s, right_range, p + 1)
                    {
                        s += match_len;
                        p += 1;
                    } else {
                        goto_fail = true;
                    }
                } else {
                    goto_fail = true;
                }
            }
            OpCode::CalloutName => {
                let (num, id) = match &reg.ops[p].payload {
                    OperationPayload::CalloutName { num, id } => (*num, *id),
                    _ => (0, 0),
                };
                let call_result =
                    run_builtin_callout(reg, num, id, false, &mut callout_data, s, msa);
                if call_result == ONIG_CALLOUT_FAIL {
                    goto_fail = true;
                } else {
                    // Push retraction entry if needed
                    if let Some(ref ext) = reg.extp {
                        if num >= 1 && (num as usize) <= ext.callout_list.len() {
                            let entry = &ext.callout_list[(num - 1) as usize];
                            if (entry.callout_in & CALLOUT_IN_RETRACTION) != 0 {
                                stack.push(StackEntry::Callout { num, id });
                            }
                        }
                    }
                    p += 1;
                }
            }
        }

        // Handle failure (backtracking)
        if goto_fail {
            // Retry limit check
            retry_in_match_counter += 1;
            if retry_limit_in_match != 0 && retry_in_match_counter > retry_limit_in_match {
                best_len = if msa.retry_limit_in_match != 0
                    && retry_in_match_counter > msa.retry_limit_in_match
                {
                    ONIGERR_RETRY_LIMIT_IN_MATCH_OVER
                } else {
                    ONIGERR_RETRY_LIMIT_IN_SEARCH_OVER
                };
                break;
            }
            // Time limit check (every CHECK_TIME_INTERVAL retries of the search)
            if time_limit_ms > 0 && msa.check_time_limit() {
                best_len = ONIGERR_TIME_LIMIT_OVER;
                break;
            }

            let pop_result = stack_pop(
                &mut stack,
                pop_level,
                &mut mem_start_stk,
                &mut mem_end_stk,
                reg,
                &mut callout_data,
                str_data,
                &mut subexp_call_nest_counter,
            );
            match pop_result {
                Some((pcode, pstr, alt_zid)) => {
                    if pcode == FINISH_PCODE {
                        // Hit bottom sentinel - no more alternatives
                        break;
                    }
                    p = pcode;
                    s = pstr;
                    last_alt_zid = alt_zid;
                }
                None => {
                    // Stack empty - match failed
                    break;
                }
            }
        }
    }

    // Accumulate retry counter into search counter
    msa.retry_limit_in_search_counter += retry_in_match_counter;

    // Return reusable buffers to MatchArg for next call
    msa.stack = stack;
    msa.mem_start_stk = mem_start_stk;
    msa.mem_end_stk = mem_end_stk;

    best_len
}

// ============================================================================
// onig_match - match at a specific position (port of C's onig_match)
// ============================================================================

/// Try to match the regex at exactly position `at` in the string.
/// Returns the match length on success, ONIG_MISMATCH (-1) on failure.
///
/// Parameters:
/// - reg: compiled regex
/// - str_data: the input string bytes
/// - end: end position (typically str_data.len())
/// - at: position to try matching at
/// - region: optional region to fill with capture group positions
/// - option: match options
pub fn onig_match(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    at: usize,
    region: Option<OnigRegion>,
    option: OnigOptionType,
) -> (i32, Option<OnigRegion>) {
    thread_local! {
        static CACHED_MSA: RefCell<Option<MatchArg>> = const { RefCell::new(None) };
    }

    let mut msa = match CACHED_MSA.with(|c| c.borrow_mut().take()) {
        Some(mut cached) => {
            cached.reset_full(reg, option, region, at);
            cached
        }
        None => MatchArg::new(reg, option, region, at),
    };

    if opton_check_validity_of_string(msa.options) && !reg.enc.is_valid_mbc_string(&str_data[..end])
    {
        let result = (ONIGERR_INVALID_WIDE_CHAR_VALUE, msa.region.take());
        CACHED_MSA.with(|c| *c.borrow_mut() = Some(msa));
        return result;
    }

    if let Some(ref mut r) = msa.region {
        r.resize(reg.num_mem + 1);
        r.clear();
    }

    let result = match_at(reg, str_data, end, end, at, &mut msa);

    // Handle FIND_LONGEST
    let result = if opton_find_longest(msa.options) && result == ONIG_MISMATCH {
        if msa.best_len >= 0 {
            msa.best_len
        } else {
            result
        }
    } else {
        result
    };

    let region = msa.region.take();
    CACHED_MSA.with(|c| *c.borrow_mut() = Some(msa));
    (result, region)
}

/// Fast match path for regset: reuses an existing MatchArg, skips string
/// validation (already done by caller), and skips region resize (caller manages).
pub(crate) fn onig_match_with_msa_start(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    at: usize,
    start: usize,
    option: OnigOptionType,
    msa: &mut MatchArg,
) -> i32 {
    msa.reset_for_match(reg, option, start);

    match_at(reg, str_data, end, end, at, msa)
}

/// Fast match path where search start (`\\G` anchor position) equals `at`.
///
/// Thin wrapper around `onig_match_with_msa_start` used by regset search.
/// Covered indirectly via regset tests; excluded to avoid instrumentation overhead.
#[cfg_attr(coverage_nightly, coverage(off))]
pub(crate) fn onig_match_with_msa(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    at: usize,
    option: OnigOptionType,
    msa: &mut MatchArg,
) -> i32 {
    onig_match_with_msa_start(reg, str_data, end, at, at, option, msa)
}

#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_match_with_param(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    at: usize,
    region: Option<OnigRegion>,
    option: OnigOptionType,
    mp: &OnigMatchParam,
) -> (i32, Option<OnigRegion>) {
    let mut msa = MatchArg::from_param(reg, option, region, at, mp);

    if opton_check_validity_of_string(msa.options) && !reg.enc.is_valid_mbc_string(&str_data[..end])
    {
        return (ONIGERR_INVALID_WIDE_CHAR_VALUE, msa.region.take());
    }

    if let Some(ref mut r) = msa.region {
        r.resize(reg.num_mem + 1);
        r.clear();
    }

    let result = match_at(reg, str_data, end, end, at, &mut msa);

    let result = if opton_find_longest(msa.options) && result == ONIG_MISMATCH {
        if msa.best_len >= 0 {
            msa.best_len
        } else {
            result
        }
    } else {
        result
    };

    (result, msa.region)
}

// ============================================================================
// onig_search - search for a match anywhere in the string
// ============================================================================

// Search for the regex pattern in the string, trying each position from
// `start` to `range`. Returns the match position on success, ONIG_MISMATCH
// (-1) on failure, given a compiled regex `reg`. The entry points themselves
// are `onig_search` and `onig_search_with_param` further down this file.
// ============================================================================
// Search optimization functions — mirrors C's regexec.c lines 5168-5645
// ============================================================================

/// Search helper.
///
///   Naive string search. Mirrors C's slow_search.
///   Uses SIMD-accelerated memchr::memmem for the actual byte search.
#[cfg_attr(coverage_nightly, coverage(off))]
fn slow_search(
    _enc: OnigEncoding,
    target: &[u8],
    text: &[u8],
    text_start: usize,
    text_end: usize,
    text_range: usize,
) -> Option<usize> {
    if target.is_empty() {
        return Some(text_start);
    }
    let tlen = target.len();
    // Search can find matches starting up to limit, needing tlen bytes available.
    let mut search_end = text_end.min(text_range + tlen.saturating_sub(1));
    if search_end > text_end {
        search_end = text_end;
    }
    if text_start + tlen > search_end {
        return None;
    }

    let haystack = &text[text_start..search_end];
    if tlen == 1 {
        memchr::memchr(target[0], haystack).map(|i| text_start + i)
    } else {
        memchr::memmem::find(haystack, target).map(|i| text_start + i)
    }
}

/// Sunday quick search (BMH variant). Mirrors C's sunday_quick_search.
/// Uses SIMD-accelerated memchr::memmem for the actual byte search.
fn sunday_quick_search(
    _reg: &RegexType,
    target: &[u8],
    text: &[u8],
    text_start: usize,
    text_end: usize,
    text_range: usize,
) -> Option<usize> {
    let tlen = target.len();
    if tlen == 0 {
        return Some(text_start);
    }

    // Compute the search end: we can find matches starting up to text_range,
    // but need tlen bytes available, so search within text[text_start..search_end].
    let search_end = if tlen > text_end.saturating_sub(text_range) {
        if tlen > text_end.saturating_sub(text_start) {
            return None;
        }
        text_end
    } else {
        text_range + tlen
    };
    // C: `while (s < end)`; a start at or past the range finds nothing.
    if text_start >= search_end {
        return None;
    }

    let haystack = &text[text_start..search_end];
    if tlen == 1 {
        memchr::memchr(target[0], haystack).map(|i| text_start + i)
    } else {
        memchr::memmem::find(haystack, target).map(|i| text_start + i)
    }
}

/// Sunday quick search with step forward for multi-byte safe operation.
/// Mirrors C's sunday_quick_search_step_forward.
#[cfg_attr(coverage_nightly, coverage(off))]
fn sunday_quick_search_step_forward(
    reg: &RegexType,
    target: &[u8],
    text: &[u8],
    text_start: usize,
    text_end: usize,
    text_range: usize,
) -> Option<usize> {
    let enc = reg.enc;
    let tlen = target.len();
    if tlen == 0 {
        return Some(text_start);
    }
    let tail_idx = tlen - 1;
    let mut end = text_range;
    if tail_idx > text_end.saturating_sub(end) {
        end = text_end.saturating_sub(tail_idx);
    }

    let map_offset = reg.map_offset as usize;
    let mut s = text_start;
    while s < end {
        let se = s + tail_idx;
        let mut p = se;
        let mut t = tail_idx;
        loop {
            if text[p] != target[t] {
                break;
            }
            if t == 0 {
                return Some(s);
            }
            p -= 1;
            t -= 1;
        }
        if se + map_offset >= text_end {
            break;
        }
        let skip = reg.map[text[se + map_offset] as usize] as usize;
        let next = s + skip;
        if next < end {
            s = onigenc_get_right_adjust_char_head(enc, text, s, next);
        } else {
            break;
        }
    }
    None
}

/// Character map search. Mirrors C's map_search.
/// Uses SIMD-accelerated memchr when the map has 1-3 distinct ASCII bytes.
fn map_search(
    enc: OnigEncoding,
    reg: &RegexType,
    text: &[u8],
    text_start: usize,
    text_range: usize,
) -> Option<usize> {
    // C: `while (s < text_range)`; a start at or past the range finds
    // nothing. An optimizer retry can leave the start there after stepping
    // over a multibyte character.
    if text_start >= text_range {
        return None;
    }
    let haystack = &text[text_start..text_range];
    match reg.map_byte_count {
        1 => memchr::memchr(reg.map_bytes[0], haystack).map(|i| text_start + i),
        2 => memchr::memchr2(reg.map_bytes[0], reg.map_bytes[1], haystack).map(|i| text_start + i),
        3 => memchr::memchr3(
            reg.map_bytes[0],
            reg.map_bytes[1],
            reg.map_bytes[2],
            haystack,
        )
        .map(|i| text_start + i),
        _ => {
            let map = &reg.map;
            let mut s = text_start;
            while s < text_range {
                if map[text[s] as usize] != 0 {
                    return Some(s);
                }
                s += enclen(enc, text, s);
            }
            None
        }
    }
}

/// Whether C's backward scans (`s = onigenc_get_prev_char_head(enc,
/// adjust_text, s)` starting at `first`) visit `pos`: the first position
/// itself, even inside a character, and every character head below it.
#[inline]
fn backward_scan_visits(
    enc: OnigEncoding,
    text: &[u8],
    adjust_text: usize,
    first: usize,
    pos: usize,
) -> bool {
    pos == first || left_adjust_char_head(enc, text, adjust_text, pos) == pos
}

/// Backward naive string search. Mirrors C's slow_search_backward: the scan
/// starts at `search_start` (or at the last position where the target fits,
/// left-adjusted) and steps back by characters while it is >= `text_start`.
/// Uses SIMD-accelerated memchr::memmem for the byte search and skips hits
/// that C's character stepping would not visit.
fn slow_search_backward(
    enc: OnigEncoding,
    target: &[u8],
    text: &[u8],
    text_start: usize,
    adjust_text: usize,
    text_end: usize,
    search_start: usize,
) -> Option<usize> {
    let tlen = target.len();
    if tlen == 0 {
        return Some(search_start);
    }
    // C: s = text_end - tlen; s > text_start ? text_start : LEFT_ADJUST(s)
    let last_fit = text_end.checked_sub(tlen)?;
    let first = if last_fit > search_start {
        search_start
    } else {
        left_adjust_char_head(enc, text, adjust_text, last_fit)
    };
    let mut right = first;
    while right >= text_start {
        let found = if tlen == 1 {
            memchr::memrchr(target[0], &text[text_start..=right])
        } else {
            memchr::memmem::rfind(&text[text_start..right + tlen], target)
        };
        let pos = text_start + found?;
        if backward_scan_visits(enc, text, adjust_text, first, pos) {
            return Some(pos);
        }
        if pos == 0 {
            break;
        }
        right = pos - 1;
    }
    None
}

/// Backward character map search. Mirrors C's map_search_backward: the scan
/// starts at `search_start` and steps back by characters while it is not
/// below `text_start`, so a start below `text_start` finds nothing.
/// Uses SIMD-accelerated memrchr when the map has 1-3 distinct ASCII bytes
/// and skips hits that C's character stepping would not visit.
#[cfg_attr(coverage_nightly, coverage(off))]
fn map_search_backward(
    enc: OnigEncoding,
    reg: &RegexType,
    text: &[u8],
    text_start: usize,
    adjust_text: usize,
    search_start: usize,
) -> Option<usize> {
    let first = search_start;
    let mut right = search_start;
    while right >= text_start {
        let haystack = &text[text_start..=right];
        let found = match reg.map_byte_count {
            1 => memchr::memrchr(reg.map_bytes[0], haystack),
            2 => memchr::memrchr2(reg.map_bytes[0], reg.map_bytes[1], haystack),
            3 => memchr::memrchr3(
                reg.map_bytes[0],
                reg.map_bytes[1],
                reg.map_bytes[2],
                haystack,
            ),
            _ => {
                // C's loop, one character at a time.
                let mut s = right;
                loop {
                    if reg.map[text[s] as usize] != 0 {
                        return Some(s);
                    }
                    if s <= adjust_text {
                        return None;
                    }
                    s = left_adjust_char_head(enc, text, adjust_text, s - 1);
                    if s < text_start {
                        return None;
                    }
                }
            }
        };
        let pos = text_start + found?;
        if backward_scan_visits(enc, text, adjust_text, first, pos) {
            return Some(pos);
        }
        if pos == 0 {
            break;
        }
        right = pos - 1;
    }
    None
}

/// Left-adjust char head (ONIGENC_LEFT_ADJUST_CHAR_HEAD).
/// For UTF-8: walk backward from pos to find char boundary at or before pos.
fn left_adjust_char_head(_enc: OnigEncoding, _text: &[u8], start: usize, pos: usize) -> usize {
    if pos <= start {
        return start;
    }
    let mut p = pos;
    while p > start && _text[p] & 0xC0 == 0x80 {
        p -= 1;
    }
    p
}

/// Backward search using optimization strategy.
/// Returns Some((low, high)) if a candidate was found, None otherwise.
fn backward_search(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    search_start: usize,
    min_range: usize,
    adjrange: usize,
) -> Option<(usize, usize)> {
    let mut p = search_start;
    loop {
        let found = match reg.optimize {
            OptimizeType::Str | OptimizeType::StrFast | OptimizeType::StrFastStepForward => {
                slow_search_backward(reg.enc, &reg.exact, str_data, min_range, adjrange, end, p)
            }
            OptimizeType::Map => {
                map_search_backward(reg.enc, reg, str_data, min_range, adjrange, p)
            }
            OptimizeType::None => {
                return None;
            }
        };

        p = found?;

        // Validate sub_anchor
        if reg.sub_anchor != 0 {
            let mut retry = false;
            if (reg.sub_anchor & ANCR_BEGIN_LINE) != 0 && p > 0 {
                let prev = onigenc_get_prev_char_head(reg.enc, str_data, 0, p);
                if !is_mbc_newline(reg.enc, str_data, prev, end) {
                    retry = true;
                }
            }
            if !retry && (reg.sub_anchor & ANCR_END_LINE) != 0 {
                if p >= end {
                    // at end, check previous
                    let prev = onigenc_get_prev_char_head(reg.enc, str_data, adjrange, p);
                    if prev < adjrange {
                        return None;
                    }
                    if is_mbc_newline(reg.enc, str_data, prev, end) {
                        p = prev;
                        continue;
                    }
                } else if !is_mbc_newline(reg.enc, str_data, p, end) {
                    retry = true;
                }
            }
            if retry {
                if p == 0 {
                    return None;
                }
                p = onigenc_get_prev_char_head(reg.enc, str_data, adjrange, p);
                if p < adjrange {
                    return None;
                }
                continue;
            }
        }

        // Calculate low/high range
        if reg.dist_max != INFINITE_LEN {
            let low = p.saturating_sub(reg.dist_max as usize);

            let high = if reg.dist_min != 0 {
                p.saturating_sub(reg.dist_min as usize)
            } else {
                p
            };

            let high = onigenc_get_right_adjust_char_head(reg.enc, str_data, adjrange, high);
            return Some((low, high));
        }

        return Some((0, p));
    }
}

/// Get right-adjusted char head for multi-byte encoding.
/// Mirrors C's onigenc_get_right_adjust_char_head: left-adjust first, then
/// advance by one character if the result is before s.
fn onigenc_get_right_adjust_char_head(
    enc: OnigEncoding,
    text: &[u8],
    start: usize,
    s: usize,
) -> usize {
    let p = left_adjust_char_head(enc, text, start, s);
    if p < s { p + enclen(enc, text, p) } else { p }
}

/// Forward search using optimization strategy.
/// Returns Some((low, high)) if a candidate was found, None otherwise.
fn forward_search(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    start: usize,
    range: usize,
) -> Option<(usize, usize)> {
    let mut p = start;
    if reg.dist_min != 0 {
        if end.saturating_sub(p) <= reg.dist_min as usize {
            return None;
        }
        if enc_is_singlebyte(reg.enc) {
            p += reg.dist_min as usize;
        } else {
            let target = p + reg.dist_min as usize;
            while p < target && p < end {
                p = advance_char_to_end(reg.enc, str_data, p, end);
            }
        }
    }

    let mut pprev: Option<usize> = None;
    loop {
        // Search for the optimization target
        let found = match reg.optimize {
            OptimizeType::Str => slow_search(reg.enc, &reg.exact, str_data, p, end, range),
            OptimizeType::StrFast => sunday_quick_search(reg, &reg.exact, str_data, p, end, range),
            OptimizeType::StrFastStepForward => {
                sunday_quick_search_step_forward(reg, &reg.exact, str_data, p, end, range)
            }
            OptimizeType::Map => map_search(reg.enc, reg, str_data, p, range),
            OptimizeType::None => {
                return None;
            }
        };

        p = match found {
            Some(pos) if pos < range => pos,
            _ => return None,
        };

        if p.saturating_sub(start) < reg.dist_min as usize {
            pprev = Some(p);
            p = advance_char_to_end(reg.enc, str_data, p, end);
            continue; // retry
        }

        // Validate sub_anchor
        if reg.sub_anchor != 0 {
            let mut retry = false;
            if (reg.sub_anchor & ANCR_BEGIN_LINE) != 0 && p > 0 {
                let prev = pprev.unwrap_or(0);
                let prev_pos = onigenc_get_prev_char_head(reg.enc, str_data, prev, p);
                if !is_mbc_newline(reg.enc, str_data, prev_pos, end) {
                    retry = true;
                }
            }
            if !retry && (reg.sub_anchor & ANCR_END_LINE) != 0 {
                if p >= end {
                    // at end - OK for some cases
                } else if !is_mbc_newline(reg.enc, str_data, p, end) {
                    retry = true;
                }
            }
            if retry {
                // A truncated multibyte lead byte reports a length past
                // `end`; stay inside the haystack as the outer loops do.
                pprev = Some(p);
                p = advance_char_to_end(reg.enc, str_data, p, end);
                continue; // retry
            }
        }

        // Calculate low/high range
        let (low, high);
        if reg.dist_max == 0 {
            low = p;
            high = p;
        } else {
            if reg.dist_max != INFINITE_LEN {
                if p.saturating_sub(0) < reg.dist_max as usize {
                    low = 0;
                } else {
                    let mut l = p - reg.dist_max as usize;
                    if l > start {
                        l = onigenc_get_right_adjust_char_head(reg.enc, str_data, start, l);
                    }
                    low = l;
                }
            } else {
                low = start; // infinite dist_max: any position from start
            }
            if p.saturating_sub(0) < reg.dist_min as usize {
                high = 0;
            } else {
                high = p - reg.dist_min as usize;
            }
        }
        return Some((low, high));
    }
}

/// Check if encoding is single-byte.
fn enc_is_singlebyte(enc: OnigEncoding) -> bool {
    enc.max_enc_len() == 1
}

/// Get previous character head position.
fn onigenc_get_prev_char_head(
    _enc: OnigEncoding,
    _text: &[u8],
    _start: usize,
    pos: usize,
) -> usize {
    if pos == 0 {
        return 0;
    }
    // For UTF-8: walk backwards past continuation bytes
    let mut p = pos - 1;
    while p > 0 && _text[p] & 0xC0 == 0x80 {
        p -= 1;
    }
    p
}

/// Check if position is a newline.
fn is_mbc_newline(_enc: OnigEncoding, text: &[u8], pos: usize, end: usize) -> bool {
    if pos >= end {
        return false;
    }
    text[pos] == b'\n'
}

/// - str_data: the input string bytes
/// - end: end position (typically str_data.len())
/// - start: starting search position
/// - range: search range end (exclusive for forward search)
/// - region: optional region to fill with capture group positions
/// - option: match options
pub fn onig_search(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    start: usize,
    range: usize,
    region: Option<OnigRegion>,
    option: OnigOptionType,
) -> (i32, Option<OnigRegion>) {
    // The following is an expanded code of onig_search_with_param() (C).
    let data_range = if range > start { range } else { end };
    search_in_range(
        reg, str_data, end, start, range, data_range, region, option, None,
    )
}

/// Port of C's `search_in_range()`: match starts are taken from
/// `[start, range]`, while every attempt may consume the subject up to
/// `data_range` (C: `MATCH_AND_RETURN_CHECK(data_range)`). `onig_search`
/// passes `range` itself (or `end` for a backward search); a regex-lead
/// RegSet search narrows `range` to its current winner but keeps the
/// original range as `data_range`.
#[allow(clippy::too_many_arguments)]
pub(crate) fn search_in_range(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    start: usize,
    range: usize,
    data_range: usize,
    region: Option<OnigRegion>,
    option: OnigOptionType,
    mp: Option<&OnigMatchParam>,
) -> (i32, Option<OnigRegion>) {
    if let Some(mp) = mp {
        let mut msa = MatchArg::from_param(reg, option, region, start, mp);
        return search_in_range_inner(reg, str_data, end, start, range, data_range, &mut msa);
    }

    thread_local! {
        static CACHED_MSA: RefCell<Option<MatchArg>> = const { RefCell::new(None) };
    }

    // Reuse a cached MatchArg to avoid heap allocation per search.
    // .take() makes this safe for re-entrant calls (e.g. from callouts).
    let mut msa = match CACHED_MSA.with(|c| c.borrow_mut().take()) {
        Some(mut cached) => {
            cached.reset_full(reg, option, region, start);
            cached
        }
        None => MatchArg::new(reg, option, region, start),
    };

    let result = search_in_range_inner(reg, str_data, end, start, range, data_range, &mut msa);

    // Return the MSA to cache (region already taken out by inner).
    CACHED_MSA.with(|c| {
        *c.borrow_mut() = Some(msa);
    });

    result
}

/// Search reusing a pre-allocated MatchArg. Preserves buffer capacity.
pub(crate) fn onig_search_with_msa(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    start: usize,
    range: usize,
    msa: &mut MatchArg,
) -> (i32, Option<OnigRegion>) {
    let data_range = if range > start { range } else { end };
    search_in_range_inner(reg, str_data, end, start, range, data_range, msa)
}

/// Search positions in `[start, range]` while allowing a match to consume up
/// to `right_range`. RegSet uses this to stop considering candidate starts
/// once they can no longer beat its current winner without truncating a match
/// that begins before that winner.
#[allow(clippy::too_many_arguments)]
///
/// `start_filter`, when given, is a start-byte map proven from the bytecode:
/// positions whose byte it excludes cannot start a match and are stepped over
/// by the position-by-position loop (see `onig_search_inner_core_with_right_range`).
pub(crate) fn onig_search_with_msa_and_right_range(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    start: usize,
    range: usize,
    right_range: usize,
    start_filter: Option<&[u8; CHAR_MAP_SIZE]>,
    msa: &mut MatchArg,
) -> (i32, Option<OnigRegion>) {
    let end = end.min(str_data.len());
    let range = range.min(end);
    let right_range = right_range.min(end);
    if start > end || right_range < start {
        return (ONIG_MISMATCH, msa.region.take());
    }

    if can_use_two_pass_capture_fill(reg, start, range, msa) {
        return onig_search_inner_two_pass(
            reg,
            str_data,
            end,
            start,
            range,
            right_range,
            false,
            start_filter,
            msa,
        );
    }
    onig_search_inner_core_with_right_range(
        reg,
        str_data,
        end,
        start,
        range,
        right_range,
        false,
        start_filter,
        msa,
    )
}

#[cfg_attr(coverage_nightly, coverage(off))]
#[allow(clippy::too_many_arguments)]
pub fn onig_search_with_param(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    start: usize,
    range: usize,
    region: Option<OnigRegion>,
    option: OnigOptionType,
    mp: &OnigMatchParam,
) -> (i32, Option<OnigRegion>) {
    let data_range = if range > start { range } else { end };
    search_in_range(
        reg,
        str_data,
        end,
        start,
        range,
        data_range,
        region,
        option,
        Some(mp),
    )
}

#[inline]
fn can_use_two_pass_capture_fill(
    reg: &RegexType,
    start: usize,
    range: usize,
    msa: &MatchArg,
) -> bool {
    start < range
        && msa.region.is_some()
        && !opton_find_longest(msa.options)
        && !reg.needs_capture_tracking
        && reg.extp.as_ref().is_none_or(|ext| ext.callout_num == 0)
        // Keep this off when wall-time limiting is active: second pass is extra work.
        && msa.time_limit == 0
}

#[allow(clippy::too_many_arguments)]
fn onig_search_inner_two_pass(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    start: usize,
    range: usize,
    right_range: usize,
    find_longest_across_positions: bool,
    start_filter: Option<&[u8; CHAR_MAP_SIZE]>,
    msa: &mut MatchArg,
) -> (i32, Option<OnigRegion>) {
    let mut region = match msa.region.take() {
        Some(r) => r,
        None => {
            return onig_search_inner_core_with_right_range(
                reg,
                str_data,
                end,
                start,
                range,
                right_range,
                find_longest_across_positions,
                start_filter,
                msa,
            );
        }
    };
    region.resize(reg.num_mem + 1);
    region.clear();

    let (match_start, _) = onig_search_inner_core_with_right_range(
        reg,
        str_data,
        end,
        start,
        range,
        right_range,
        find_longest_across_positions,
        start_filter,
        msa,
    );
    if match_start < 0 {
        msa.region = Some(region);
        return (match_start, msa.region.take());
    }

    msa.region = Some(region);
    msa.best_len = ONIG_MISMATCH;
    msa.best_s = 0;

    let retry_counter_before = msa.retry_limit_in_search_counter;
    let retry_limit_in_match_before = msa.retry_limit_in_match;
    let retry_limit_in_search_before = msa.retry_limit_in_search;
    // Second pass is implementation-only; avoid consuming retry budget.
    msa.retry_limit_in_match = 0;
    msa.retry_limit_in_search = 0;
    // Forward searches attempt every candidate with `right_range` as the
    // match boundary, so the second pass uses the same one.
    let r = match_at(reg, str_data, end, right_range, match_start as usize, msa);
    msa.retry_limit_in_match = retry_limit_in_match_before;
    msa.retry_limit_in_search = retry_limit_in_search_before;
    msa.retry_limit_in_search_counter = retry_counter_before;
    if r < ONIG_MISMATCH {
        return (r, msa.region.take());
    }
    if r == ONIG_MISMATCH {
        // Conservative fallback: preserve semantics if second pass diverges.
        return onig_search_inner_core_with_right_range(
            reg,
            str_data,
            end,
            start,
            range,
            right_range,
            find_longest_across_positions,
            start_filter,
            msa,
        );
    }

    (match_start, msa.region.take())
}

fn search_in_range_inner(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    start: usize,
    range: usize,
    data_range: usize,
    msa: &mut MatchArg,
) -> (i32, Option<OnigRegion>) {
    // The C API accepts an end pointer into the supplied buffer. Normalize
    // Rust indices once at the public-search boundary so every optimizer sees
    // a valid slice, and reject a start outside the logical string.
    let end = end.min(str_data.len());
    let range = range.min(end);
    let data_range = data_range.min(end);
    if start > end {
        return (ONIG_MISMATCH, msa.region.take());
    }

    if can_use_two_pass_capture_fill(reg, start, range, msa) {
        // A forward range bounds each attempt by `data_range`; see
        // `onig_search_inner_core`.
        return onig_search_inner_two_pass(
            reg, str_data, end, start, range, data_range, true, None, msa,
        );
    }
    onig_search_inner_core(reg, str_data, end, start, range, data_range, msa)
}

fn onig_search_inner_core(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    start: usize,
    range: usize,
    data_range: usize,
    msa: &mut MatchArg,
) -> (i32, Option<OnigRegion>) {
    let right_range = if start == range && start < end {
        (start + enclen(reg.enc, str_data, start)).min(end)
    } else if range > start {
        data_range
    } else {
        end
    };
    onig_search_inner_core_with_right_range(
        reg,
        str_data,
        end,
        start,
        range,
        right_range,
        true,
        None,
        msa,
    )
}

#[allow(clippy::too_many_arguments)]
fn onig_search_inner_core_with_right_range(
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    start: usize,
    range: usize,
    right_range: usize,
    find_longest_across_positions: bool,
    start_filter: Option<&[u8; CHAR_MAP_SIZE]>,
    msa: &mut MatchArg,
) -> (i32, Option<OnigRegion>) {
    let enc = reg.enc;
    // Skipping an attempt is unobservable except through the search retry
    // budget, which counts every failed attempt.
    let start_filter = start_filter.filter(|_| msa.retry_limit_in_search == 0);
    // Position-led RegSet searches still honor FIND_LONGEST within each
    // attempted position, but must return the earliest successful position.
    // Public onig_search retains its historical global-longest behavior.
    let find_longest = find_longest_across_positions && opton_find_longest(msa.options);
    let mut best_start: i32 = ONIG_MISMATCH;
    let mut best_len: i32 = ONIG_MISMATCH;

    if opton_check_validity_of_string(msa.options) && !enc.is_valid_mbc_string(&str_data[..end]) {
        return (ONIGERR_INVALID_WIDE_CHAR_VALUE, msa.region.take());
    }

    // Resize region once before entering search loops (matches C behavior)
    if let Some(ref mut r) = msa.region {
        r.resize(reg.num_mem + 1);
        r.clear();
    }

    // C treats start == range (before the logical end) as an anchored attempt
    // at exactly start, whose match extent is one encoded character. It is
    // neither a forward empty range nor a backward search.
    //
    // Deliberate divergence: C sends this case down its backward path, whose
    // optimized loop (`while (PTR_GE(s, low))`) is not bounded by `range`
    // and can return a match before `start` (`^.{2}c` on "abc\nabc\n" with
    // start = range = 4 yields 0 in C). Ferroni only tries `start`.
    if start == range && start < end {
        msa.best_len = ONIG_MISMATCH;
        msa.best_s = 0;
        let r = match_at(reg, str_data, end, right_range, start, msa);
        if r < ONIG_MISMATCH {
            return (r, msa.region.take());
        }
        if r != ONIG_MISMATCH {
            return (start as i32, msa.region.take());
        }
        return (ONIG_MISMATCH, msa.region.take());
    }

    // Aho-Corasick fast path for literal alternations.
    // Single-pass scan replaces the position-by-position loop entirely.
    // Works for both bare `alpha|beta` and captured `(alpha|beta)`.
    if let Some(ref ac) = reg.ac_alt {
        if start <= range && !find_longest {
            // Matches start in `[start, range]` and may extend to
            // `right_range` (C's `data_range`).
            let search_end = right_range.min(end);
            if let Some(mat) = ac
                .find(&str_data[start..search_end])
                .filter(|mat| start + mat.start() <= range)
            {
                let match_start = start + mat.start();
                let match_end = start + mat.end();
                if let Some(ref mut r) = msa.region {
                    r.beg[0] = match_start as i32;
                    r.end[0] = match_end as i32;
                    if reg.ac_alt_has_capture {
                        r.beg[1] = match_start as i32;
                        r.end[1] = match_end as i32;
                    }
                }
                return (match_start as i32, msa.region.take());
            }
            return (ONIG_MISMATCH, msa.region.take());
        }
        // backward search or find_longest: fall through to normal path
    }

    if start > range {
        // Backward search: start > range, search from start down to range
        if end == 0 {
            return (ONIG_MISMATCH, msa.region.take());
        }

        // orig_start is the right boundary for matching (upper range)
        let orig_start = if start < end {
            let elen = enclen(enc, str_data, start);
            start + elen
        } else {
            end
        };

        // s starts at start (same as C: s = (UChar*)start)
        let mut s = start;

        // Macro-like helper for match_at + result handling in backward search
        macro_rules! backward_match_and_check {
            ($s:expr, $orig_start:expr) => {{
                if let Some(ref mut r) = msa.region {
                    r.clear();
                }
                msa.best_len = ONIG_MISMATCH;
                msa.best_s = 0;
                let r = match_at(reg, str_data, end, $orig_start, $s, msa);
                if r != ONIG_MISMATCH {
                    if r < 0 {
                        return (r, msa.region.take());
                    }
                    if find_longest {
                        let match_len = if msa.best_len >= 0 { msa.best_len } else { r };
                        if best_len == ONIG_MISMATCH || match_len > best_len {
                            best_start = $s as i32;
                            best_len = match_len;
                        }
                    } else {
                        return ($s as i32, msa.region.take());
                    }
                }
                if msa.retry_limit_in_search != 0
                    && msa.retry_limit_in_search_counter > msa.retry_limit_in_search
                {
                    return (ONIGERR_RETRY_LIMIT_IN_SEARCH_OVER, msa.region.take());
                }
            }};
        }

        if reg.optimize != OptimizeType::None {
            // Threshold length check (inside optimize branch, matching C)
            if (end as i32 - range as i32) < reg.threshold_len {
                return (ONIG_MISMATCH, msa.region.take());
            }

            let adjrange = if range < end {
                left_adjust_char_head(enc, str_data, 0, range)
            } else {
                end
            };

            let min_range = if end.saturating_sub(range) > reg.dist_min as usize {
                range + reg.dist_min as usize
            } else {
                end
            };

            if reg.dist_max != INFINITE_LEN {
                // C: do { ... } while (PTR_GE(s, range));
                // Use usize::MAX as sentinel for C's NULL (past-beginning)
                loop {
                    let sch_start = if end.saturating_sub(s) > reg.dist_max as usize {
                        s + reg.dist_max as usize
                    } else {
                        onigenc_get_prev_char_head(enc, str_data, 0, end)
                    };

                    if let Some((low, high)) =
                        backward_search(reg, str_data, end, sch_start, min_range, adjrange)
                    {
                        if s > high {
                            s = high;
                        }
                        while s >= low {
                            backward_match_and_check!(s, orig_start);
                            if s == 0 {
                                s = usize::MAX; // sentinel: past beginning (C returns NULL)
                                break;
                            }
                            s = onigenc_get_prev_char_head(enc, str_data, 0, s);
                        }
                    } else {
                        return finish_search(
                            find_longest,
                            best_start,
                            best_len,
                            reg,
                            str_data,
                            end,
                            orig_start,
                            msa,
                        );
                    }

                    if s == usize::MAX || s < range {
                        break;
                    }
                }
                return finish_search(
                    find_longest,
                    best_start,
                    best_len,
                    reg,
                    str_data,
                    end,
                    orig_start,
                    msa,
                );
            } else {
                // dist_max == INFINITE_LEN: single backward_search as gate
                let sch_start = onigenc_get_prev_char_head(enc, str_data, 0, end);
                if backward_search(reg, str_data, end, sch_start, min_range, adjrange).is_none() {
                    return (ONIG_MISMATCH, msa.region.take());
                }
            }
        }

        // Fallthrough: position-by-position loop (optimize == None or infinite dist_max gate passed)
        // C: do { MATCH; s = onigenc_get_prev_char_head(enc, str, s); }
        //    while (PTR_GE(s, range));
        // A range inside a character is not rounded down: the head below it
        // is not tried.
        loop {
            backward_match_and_check!(s, orig_start);
            if s == 0 {
                break; // C: prev_char_head returns NULL at str
            }
            s = onigenc_get_prev_char_head(enc, str_data, 0, s);
            if s < range {
                break;
            }
        }

        return finish_search(
            find_longest,
            best_start,
            best_len,
            reg,
            str_data,
            end,
            orig_start,
            msa,
        );
    }

    let mut cur_start = start;
    let mut cur_range = range;
    let data_range = right_range;

    // === Anchor optimization: narrow search range ===
    if reg.anchor != 0 && start < end {
        if (reg.anchor & ANCR_BEGIN_POSITION) != 0 {
            // search start-position only
            if range > start {
                cur_range = start + 1;
            } else {
                cur_range = start;
            }
        } else if (reg.anchor & ANCR_BEGIN_BUF) != 0 {
            // search str-position only (must start at 0)
            if range > start {
                if start != 0 {
                    return (ONIG_MISMATCH, msa.region.take());
                }
                cur_range = 1;
            } else {
                return (ONIG_MISMATCH, msa.region.take());
            }
        } else if (reg.anchor & ANCR_END_BUF) != 0 {
            let min_semi_end = end;
            let max_semi_end = end;
            if (max_semi_end as OnigLen) < reg.anc_dist_min {
                return (ONIG_MISMATCH, msa.region.take());
            }
            if range > start {
                if reg.anc_dist_max != INFINITE_LEN
                    && min_semi_end.saturating_sub(start) > reg.anc_dist_max as usize
                {
                    cur_start = min_semi_end - reg.anc_dist_max as usize;
                }
                if max_semi_end.saturating_sub(cur_range.saturating_sub(1))
                    < reg.anc_dist_min as usize
                {
                    if max_semi_end + 1 < reg.anc_dist_min as usize {
                        return (ONIG_MISMATCH, msa.region.take());
                    } else {
                        cur_range = max_semi_end - reg.anc_dist_min as usize + 1;
                    }
                }
                if cur_start > cur_range {
                    return (ONIG_MISMATCH, msa.region.take());
                }
            }
        } else if (reg.anchor & ANCR_SEMI_END_BUF) != 0 {
            let mut min_semi_end = end;
            let max_semi_end = end;
            // Check if last char before end is newline
            if end > 0 && str_data[end - 1] == b'\n' {
                min_semi_end = end - 1;
            }
            if (max_semi_end as OnigLen) < reg.anc_dist_min {
                return (ONIG_MISMATCH, msa.region.take());
            }
            if range > start {
                if reg.anc_dist_max != INFINITE_LEN
                    && min_semi_end.saturating_sub(start) > reg.anc_dist_max as usize
                {
                    cur_start = min_semi_end - reg.anc_dist_max as usize;
                }
                if max_semi_end.saturating_sub(cur_range.saturating_sub(1))
                    < reg.anc_dist_min as usize
                {
                    if max_semi_end + 1 < reg.anc_dist_min as usize {
                        return (ONIG_MISMATCH, msa.region.take());
                    } else {
                        cur_range = max_semi_end - reg.anc_dist_min as usize + 1;
                    }
                }
                if cur_start > cur_range {
                    return (ONIG_MISMATCH, msa.region.take());
                }
            }
        } else if (reg.anchor & ANCR_ANYCHAR_INF_ML) != 0 && range > start {
            // start-position only
            if range > start {
                cur_range = start + 1;
            }
        }
    } else if start == end {
        // Empty string
        if reg.threshold_len == 0 {
            let mut s = start;
            if let Some(ref mut r) = msa.region {
                r.clear();
            }
            msa.best_len = ONIG_MISMATCH;
            msa.best_s = 0;
            let r = match_at(reg, str_data, end, end, s, msa);
            if r < ONIG_MISMATCH {
                return (r, msa.region.take());
            } // error
            if r != ONIG_MISMATCH {
                return (s as i32, msa.region.take());
            }
        }
        return (ONIG_MISMATCH, msa.region.take());
    }

    // === Threshold length check ===
    if (end as i32 - cur_start as i32) < reg.threshold_len {
        return (ONIG_MISMATCH, msa.region.take());
    }

    // === Forward search ===
    let mut s = cur_start;

    // Use optimization if available
    if reg.optimize != OptimizeType::None {
        // Calculate search range for optimization
        let sch_range = if reg.dist_max != 0 {
            if reg.dist_max == INFINITE_LEN || end.saturating_sub(cur_range) < reg.dist_max as usize
            {
                end
            } else {
                cur_range + reg.dist_max as usize
            }
        } else {
            cur_range
        };

        if reg.dist_max != INFINITE_LEN {
            // Finite dist_max: iterate with forward_search
            while let Some((low, high)) = forward_search(reg, str_data, end, s, sch_range) {
                if s < low {
                    s = low;
                }
                while s <= high {
                    if let Some(ref mut r) = msa.region {
                        r.clear();
                    }
                    msa.best_len = ONIG_MISMATCH;
                    msa.best_s = 0;
                    let r = match_at(reg, str_data, end, data_range, s, msa);
                    if r != ONIG_MISMATCH {
                        if r < 0 {
                            return (r, msa.region.take());
                        } // error
                        if find_longest {
                            let match_len = if msa.best_len >= 0 { msa.best_len } else { r };
                            if best_len == ONIG_MISMATCH || match_len > best_len {
                                best_start = s as i32;
                                best_len = match_len;
                            }
                        } else {
                            return (s as i32, msa.region.take());
                        }
                    }
                    if msa.retry_limit_in_search != 0
                        && msa.retry_limit_in_search_counter > msa.retry_limit_in_search
                    {
                        return (ONIGERR_RETRY_LIMIT_IN_SEARCH_OVER, msa.region.take());
                    }
                    // A truncated multibyte lead byte reports a length past
                    // `end`. C steps past the buffer here and its NUL
                    // terminator hides that; Rust stays inside the haystack
                    // and lets the next attempt run at the logical end.
                    s = advance_char_to_end(enc, str_data, s, end);
                    if msa.skip_search > s {
                        s = msa.skip_search;
                    }
                }
                if s >= cur_range {
                    break;
                }
            }
            // C: goto mismatch -- optimized search exhausted, do not fall
            // through to the byte-by-byte loop below.
            return finish_search(
                find_longest,
                best_start,
                best_len,
                reg,
                str_data,
                end,
                data_range,
                msa,
            );
        } else {
            // Infinite dist_max: just check once, then fall through to normal loop
            if forward_search(reg, str_data, end, s, sch_range).is_none() {
                return finish_search(
                    find_longest,
                    best_start,
                    best_len,
                    reg,
                    str_data,
                    end,
                    data_range,
                    msa,
                );
            }
            // ANCR_ANYCHAR_INF: skip past newlines
            if (reg.anchor & ANCR_ANYCHAR_INF) != 0
                && (reg.anchor & (ANCR_LOOK_BEHIND | ANCR_PREC_READ_NOT)) == 0
            {
                while s < cur_range {
                    if let Some(ref mut r) = msa.region {
                        r.clear();
                    }
                    msa.best_len = ONIG_MISMATCH;
                    msa.best_s = 0;
                    let r = match_at(reg, str_data, end, data_range, s, msa);
                    if r != ONIG_MISMATCH {
                        if r < 0 {
                            return (r, msa.region.take());
                        }
                        if find_longest {
                            let match_len = if msa.best_len >= 0 { msa.best_len } else { r };
                            if best_len == ONIG_MISMATCH || match_len > best_len {
                                best_start = s as i32;
                                best_len = match_len;
                            }
                        } else {
                            return (s as i32, msa.region.take());
                        }
                    }
                    if msa.retry_limit_in_search != 0
                        && msa.retry_limit_in_search_counter > msa.retry_limit_in_search
                    {
                        return (ONIGERR_RETRY_LIMIT_IN_SEARCH_OVER, msa.region.take());
                    }
                    let prev = s;
                    s = advance_char_to_end(enc, str_data, s, end);
                    if msa.skip_search > s {
                        s = msa.skip_search;
                    }
                    // Skip past non-newline chars
                    while s < cur_range && !is_mbc_newline(enc, str_data, prev, end) {
                        let prev2 = s;
                        s = advance_char_to_end(enc, str_data, s, end);
                        if is_mbc_newline(enc, str_data, prev2, end) {
                            break;
                        }
                    }
                }
                return finish_search(
                    find_longest,
                    best_start,
                    best_len,
                    reg,
                    str_data,
                    end,
                    data_range,
                    msa,
                );
            }
            // Fall through to normal position loop below
        }
    }

    // Normal position-by-position search (no optimization or fallthrough)
    if best_start == ONIG_MISMATCH {
        loop {
            if let Some(filter) = start_filter {
                // No match starts on an excluded byte. The range limit and the
                // logical end are still attempted, as the loop below does.
                while s < cur_range && s < end && filter[str_data[s] as usize] == 0 {
                    s = advance_char_to_end(enc, str_data, s, end);
                }
            }
            if let Some(ref mut r) = msa.region {
                r.clear();
            }
            msa.best_len = ONIG_MISMATCH;
            msa.best_s = 0;
            let r = match_at(reg, str_data, end, data_range, s, msa);
            if r != ONIG_MISMATCH {
                if r < 0 {
                    return (r, msa.region.take());
                }
                if find_longest {
                    let match_len = if msa.best_len >= 0 { msa.best_len } else { r };
                    if best_len == ONIG_MISMATCH || match_len > best_len {
                        best_start = s as i32;
                        best_len = match_len;
                    }
                } else {
                    return (s as i32, msa.region.take());
                }
            }
            if msa.retry_limit_in_search != 0
                && msa.retry_limit_in_search_counter > msa.retry_limit_in_search
            {
                return (ONIGERR_RETRY_LIMIT_IN_SEARCH_OVER, msa.region.take());
            }
            if s >= cur_range {
                break;
            }
            if s >= end {
                break;
            }
            s = advance_char_to_end(enc, str_data, s, end);
            if msa.skip_search > s {
                s = msa.skip_search;
            }
        }
    }

    finish_search(
        find_longest,
        best_start,
        best_len,
        reg,
        str_data,
        end,
        data_range,
        msa,
    )
}

#[allow(clippy::too_many_arguments)]
fn finish_search(
    find_longest: bool,
    best_start: i32,
    best_len: i32,
    reg: &RegexType,
    str_data: &[u8],
    end: usize,
    upper_range: usize,
    msa: &mut MatchArg,
) -> (i32, Option<OnigRegion>) {
    if find_longest && best_start != ONIG_MISMATCH {
        if let Some(ref mut r) = msa.region {
            r.clear();
        }
        msa.best_len = ONIG_MISMATCH;
        msa.best_s = 0;
        // Replay the winner with the upper range every attempt used (C:
        // MATCH_AND_RETURN_CHECK(orig_start / data_range)); C keeps the
        // region that attempt recorded.
        match_at(reg, str_data, end, upper_range, best_start as usize, msa);
        return (best_start, msa.region.take());
    }
    (ONIG_MISMATCH, msa.region.take())
}

// ============================================================================
// Tests
// ============================================================================

#[cfg(test)]
mod tests {
    use super::*;
    use crate::regcomp;
    use crate::regparse;
    use crate::regparse_types::ParseEnv;

    fn make_test_context() -> (RegexType, ParseEnv) {
        use crate::regsyntax::OnigSyntaxOniguruma;
        let enc: OnigEncoding = &crate::encodings::utf8::ONIG_ENCODING_UTF8;
        let reg = RegexType {
            ops: Vec::new(),
            string_pool: Vec::new(),
            num_mem: 0,
            num_repeat: 0,
            num_empty_check: 0,
            num_call: 0,
            capture_history: 0,
            push_mem_start: 0,
            push_mem_end: 0,
            stack_pop_level: StackPopLevel::Free,
            repeat_range: Vec::new(),
            enc,
            options: ONIG_OPTION_NONE,
            syntax: OnigSyntaxOniguruma.clone(),
            case_fold_flag: ONIGENC_CASE_FOLD_MIN,
            name_table: None,
            optimize: OptimizeType::None,
            threshold_len: 0,
            anchor: 0,
            anc_dist_min: 0,
            anc_dist_max: 0,
            sub_anchor: 0,
            exact: Vec::new(),
            map: [0u8; CHAR_MAP_SIZE],
            map_offset: 0,
            map_bytes: [0u8; 3],
            map_byte_count: 0,
            dist_min: 0,
            dist_max: 0,
            needs_capture_tracking: false,
            keep_moves_match_start: false,
            first_byte_map: [0u8; CHAR_MAP_SIZE],
            has_first_byte_map: false,
            called_addrs: vec![],
            unset_call_addrs: vec![],
            extp: None,
            literal_tries: Vec::new(),
            ac_alt: None,
            ac_alt_has_capture: false,
        };
        let env = ParseEnv {
            options: OnigOptionType::empty(),
            case_fold_flag: 0,
            enc,
            syntax: OnigSyntaxOniguruma.clone(),
            cap_history: 0,
            backtrack_mem: 0,
            backrefed_mem: 0,
            pattern: std::ptr::null(),
            pattern_end: std::ptr::null(),
            error: None,
            reg: std::ptr::null_mut(),
            num_call: 0,
            num_mem: 0,
            num_named: 0,
            mem_alloc: 0,
            mem_env_static: Default::default(),
            mem_env_dynamic: None,
            backref_num: 0,
            keep_num: 0,
            id_num: 0,
            save_alloc_num: 0,
            saves: None,
            unset_addr_list: None,
            parse_depth: 0,
            ast_node_count: 0,
            flags: 0,
            recursive_mem: Vec::new(),
            group_min_len: Vec::new(),
        };
        (reg, env)
    }

    fn compile_and_match(pattern: &[u8], input: &[u8]) -> (i32, Option<OnigRegion>) {
        let (mut reg, mut env) = make_test_context();
        let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env).unwrap();
        let r = regcomp::compile_from_tree(&root, &mut reg, &env);
        assert_eq!(
            r,
            0,
            "compile failed for {:?}",
            std::str::from_utf8(pattern)
        );
        onig_match(
            &reg,
            input,
            input.len(),
            0,
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
        )
    }

    fn compile_and_search(pattern: &[u8], input: &[u8]) -> (i32, Option<OnigRegion>) {
        let (mut reg, mut env) = make_test_context();
        let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env).unwrap();
        let r = regcomp::compile_from_tree(&root, &mut reg, &env);
        assert_eq!(
            r,
            0,
            "compile failed for {:?}",
            std::str::from_utf8(pattern)
        );
        onig_search(
            &reg,
            input,
            input.len(),
            0,
            input.len(),
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
        )
    }

    fn compile_regex(pattern: &[u8]) -> RegexType {
        let (mut reg, mut env) = make_test_context();
        let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env).unwrap();
        let r = regcomp::compile_from_tree(&root, &mut reg, &env);
        assert_eq!(
            r,
            0,
            "compile failed for {:?}",
            std::str::from_utf8(pattern)
        );
        reg
    }

    #[test]
    fn search_start_equal_range_is_a_bounded_anchored_attempt() {
        let text = b"aaaa";
        let reg = compile_regex(b"a");
        let (position, region) = onig_search(
            &reg,
            text,
            text.len(),
            2,
            2,
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
        );
        assert_eq!(position, 2);
        assert_eq!(region.unwrap().end[0], 3);

        let text = b"aab";
        let reg = compile_regex(b"a*");
        let (position, region) = onig_search(
            &reg,
            text,
            text.len(),
            0,
            0,
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
        );
        assert_eq!(position, 0);
        assert_eq!(region.unwrap().end[0], 1);
    }

    #[test]
    fn search_normalizes_out_of_range_endpoints() {
        let text = b"abc";
        let reg = compile_regex(b"(?=b)");

        for (end, start, range, expected) in [
            (text.len(), 0, 100, 1),
            (100, 0, 100, 1),
            (text.len(), 100, 0, ONIG_MISMATCH),
        ] {
            let (position, _) = onig_search(
                &reg,
                text,
                end,
                start,
                range,
                Some(OnigRegion::new()),
                ONIG_OPTION_NONE,
            );
            assert_eq!(
                position, expected,
                "end={end}, start={start}, range={range}"
            );
        }
    }

    fn has_opcode(reg: &RegexType, opcode: OpCode) -> bool {
        reg.ops.iter().any(|op| op.opcode == opcode)
    }

    fn opcode_names(reg: &RegexType) -> String {
        reg.ops
            .iter()
            .map(|op| format!("{:?}", op.opcode))
            .collect::<Vec<_>>()
            .join(", ")
    }

    fn make_code_range_table(ranges: &[(u32, u32)]) -> Vec<u32> {
        let mut out = Vec::with_capacity(1 + ranges.len() * 2);
        out.push(ranges.len() as u32);
        for (lo, hi) in ranges {
            out.push(*lo);
            out.push(*hi);
        }
        out
    }

    #[test]
    fn named_capture_can_skip_tracking_when_region_is_none() {
        let reg = compile_regex(b"(?<year>\\d{4})-(?<month>\\d{2})-(?<day>\\d{2})");
        assert!(
            !reg.needs_capture_tracking,
            "plain captures without backrefs should not require tracking when region is absent"
        );

        let text = b"Event on 2025-12-31 at venue, next on 2026-01-15.";
        let (pos, region) = onig_search(
            &reg,
            text,
            text.len(),
            0,
            text.len(),
            None,
            ONIG_OPTION_NONE,
        );
        assert_eq!(pos, 9);
        assert!(region.is_none());
    }

    #[test]
    fn named_capture_region_reuse_mismatch_resets_slots() {
        let reg = compile_regex(b"(?<year>\\d{4})-(?<month>\\d{2})-(?<day>\\d{2})");
        assert!(!reg.needs_capture_tracking);
        assert_eq!(reg.push_mem_start, 0);
        assert_eq!(reg.push_mem_end, 0);

        let mut region = Some(onig_region_new());

        let text_hit = b"Event on 2025-12-31 at venue.";
        let (pos_hit, returned) = onig_search(
            &reg,
            text_hit,
            text_hit.len(),
            0,
            text_hit.len(),
            region,
            ONIG_OPTION_NONE,
        );
        assert_eq!(pos_hit, 9);
        region = returned;
        let hit = region.as_ref().expect("region after hit");
        assert_eq!(hit.beg[0], 9);
        assert_eq!(hit.end[0], 19);
        assert_eq!(hit.beg[1], 9);
        assert_eq!(hit.end[1], 13);
        assert_eq!(hit.beg[2], 14);
        assert_eq!(hit.end[2], 16);
        assert_eq!(hit.beg[3], 17);
        assert_eq!(hit.end[3], 19);

        let text_miss = b"Event on xx-yy-zz at venue.";
        let (pos_miss, returned) = onig_search(
            &reg,
            text_miss,
            text_miss.len(),
            0,
            text_miss.len(),
            region,
            ONIG_OPTION_NONE,
        );
        assert_eq!(pos_miss, ONIG_MISMATCH);
        let miss = returned.expect("region after miss");
        for i in 0..=reg.num_mem as usize {
            assert_eq!(miss.beg[i], ONIG_REGION_NOTPOS, "beg[{}]", i);
            assert_eq!(miss.end[i], ONIG_REGION_NOTPOS, "end[{}]", i);
        }
    }

    #[test]
    fn backref_still_requires_capture_tracking_without_region() {
        let reg = compile_regex(b"(\\w+) \\1");
        assert!(
            reg.needs_capture_tracking,
            "backrefs depend on capture tracking even when region is absent"
        );

        let text = b"the the quick";
        let (pos, region) = onig_search(
            &reg,
            text,
            text.len(),
            0,
            text.len(),
            None,
            ONIG_OPTION_NONE,
        );
        assert_eq!(pos, 0);
        assert!(region.is_none());
    }

    fn compile_full(pattern: &[u8]) -> RegexType {
        crate::regcomp::onig_new(
            pattern,
            ONIG_OPTION_NONE,
            &crate::encodings::utf8::ONIG_ENCODING_UTF8,
            &crate::regsyntax::OnigSyntaxOniguruma,
        )
        .expect("pattern compiles")
    }

    #[test]
    fn backtracked_push_captures_do_not_require_tracking() {
        let _lock = LIMIT_TEST_LOCK.lock().unwrap();
        // A capture inside a repeat compiles to MEM_START_PUSH/MEM_END_PUSH so
        // that backtracking can restore it. Only the region observes that, so
        // a region-free search must not pay for the bookkeeping.
        let reg = compile_full(b"(?:(a)|b)*ab");
        assert_ne!(reg.push_mem_start | reg.push_mem_end, 0);
        assert!(reg.ops.iter().any(|op| op.opcode == OpCode::MemStartPush));
        assert!(!reg.needs_capture_tracking);

        // (input, match start, match end, group 1 start, group 1 end)
        type Case = (&'static [u8], i32, i32, i32, i32);
        let cases: [Case; 2] = [
            // The iteration that captured `a` is backtracked away, so its
            // capture must be restored to unset.
            (b"xbab", 1, 4, ONIG_REGION_NOTPOS, ONIG_REGION_NOTPOS),
            (b"xaab", 1, 4, 1, 2),
        ];
        for (text, beg, end, g1_beg, g1_end) in cases {
            let (pos, region) = onig_search(
                &reg,
                text,
                text.len(),
                0,
                text.len(),
                None,
                ONIG_OPTION_NONE,
            );
            assert_eq!(pos, beg);
            assert!(region.is_none());

            let (pos, region) = onig_search(
                &reg,
                text,
                text.len(),
                0,
                text.len(),
                Some(OnigRegion::new()),
                ONIG_OPTION_NONE,
            );
            assert_eq!(pos, beg);
            let region = region.expect("region");
            assert_eq!((region.beg[0], region.end[0]), (beg, end));
            assert_eq!((region.beg[1], region.end[1]), (g1_beg, g1_end));
        }
    }

    #[test]
    fn match_stack_limit_counts_push_captures_with_and_without_region() {
        // Untracked runs drop the push-capture stack entries. A configured
        // stack limit must still trip exactly where a region-tracking run
        // (and C) trips it.
        let reg = compile_full(b"(?:(a)|b)*c");
        let mut text = vec![b'a'; 64];
        text.push(b'c');

        let mut saw_limit = false;
        let mut saw_match = false;
        for limit in 1..400 {
            let mut mp = onig_new_match_param();
            onig_set_match_stack_limit_size_of_match_param(&mut mp, limit);
            let (without_region, _) = onig_search_with_param(
                &reg,
                &text,
                text.len(),
                0,
                text.len(),
                None,
                ONIG_OPTION_NONE,
                &mp,
            );
            let (with_region, _) = onig_search_with_param(
                &reg,
                &text,
                text.len(),
                0,
                text.len(),
                Some(OnigRegion::new()),
                ONIG_OPTION_NONE,
                &mp,
            );
            assert_eq!(without_region, with_region, "stack limit {limit}");
            saw_limit |= with_region == ONIGERR_MATCH_STACK_LIMIT_OVER;
            saw_match |= with_region == 0;
        }
        assert!(
            saw_limit && saw_match,
            "the limit range must cover both outcomes"
        );
    }

    #[test]
    fn negated_class_loops_compile_to_star_opcodes() {
        for (pattern, opcode) in [
            (&b"[^\"]+"[..], OpCode::CClassNotStar),
            (b"[^\\x{100}]*x", OpCode::CClassMbNotStar),
            (b"[^a\\x{100}]*x", OpCode::CClassMixNotStar),
            // Alt-CClass fusion over a negated first branch.
            (b"(?:[^\"\\\\]|\\\\.)*\"", OpCode::CClassNotStar),
        ] {
            let reg = compile_full(pattern);
            assert!(
                reg.ops.iter().any(|op| op.opcode == opcode),
                "{:?} should use {opcode:?}",
                std::str::from_utf8(pattern)
            );
        }
    }

    #[test]
    fn negated_class_star_backtracks_through_every_character() {
        let _lock = LIMIT_TEST_LOCK.lock().unwrap();
        // (pattern, input, expected match)
        type Case = (&'static [u8], &'static [u8], (i32, i32));
        let cases: [Case; 5] = [
            (b"[^\"]*x", b"abxcdx\"x", (0, 6)),
            (b"(?:[^\"\\\\]|\\\\.)+\"", b"a\\\"b\"c", (0, 5)),
            (
                b"[^\\x{100}]+\\x{e9}",
                "d\u{e9}j\u{e0} \u{e9}t\u{e9}".as_bytes(),
                (0, 12),
            ),
            (
                b"[^a\\x{100}]*b",
                "x\u{e9}b\u{e9}b\u{100}b".as_bytes(),
                (0, 7),
            ),
            // A stray continuation byte after `\u{e9}` is a one-byte character
            // at 3, the only boundary followed by `.b`. Stepping back from the
            // end with prev_char_head would skip it (4 -> 1).
            (b"[^\"]*(?=.b)", b"a\xc3\xa9\x80b", (0, 3)),
        ];
        for (pattern, input, expected) in cases {
            let reg = compile_full(pattern);
            let (pos, region) = onig_search(
                &reg,
                input,
                input.len(),
                0,
                input.len(),
                Some(OnigRegion::new()),
                ONIG_OPTION_NONE,
            );
            let region = region.expect("region");
            assert_eq!(
                (pos, (region.beg[0], region.end[0])),
                (expected.0, expected),
                "{:?}",
                std::str::from_utf8(pattern)
            );
        }
    }

    #[test]
    fn star_opcodes_match_the_generic_loop_on_malformed_utf8() {
        let _lock = LIMIT_TEST_LOCK.lock().unwrap();
        // `{0,50}` keeps the generic PUSH/JUMP loop, whose backtrack points
        // are exactly the boundaries of the forward scan. Truncated and
        // stray multibyte sequences make `prev_char_head` disagree with
        // those boundaries, so the star opcodes must not rely on it there.
        let inputs: [&[u8]; 5] = [
            b"x\xc3ab",
            b"\xc3\xa9\xa9ab",
            b"ab\xe2\x82a b",
            b"\xf0\x9f\x98a b",
            b"a\xc3\xa9\x80b",
        ];
        for (class, opcode) in [
            ("[\\x{80}-\\x{10ffff}]", OpCode::CClassMbStar),
            ("[\\x{80}-\\x{10ffff}a-z]", OpCode::CClassMixStar),
            ("[^\\x{100}]", OpCode::CClassMbNotStar),
            ("[^\"\\x{100}]", OpCode::CClassMixNotStar),
            ("[^\"]", OpCode::CClassNotStar),
            ("\\w", OpCode::WordStar),
        ] {
            for tail in ["(?=.b)", "(?=a)", "(?= )"] {
                let star = format!("{class}*{tail}");
                let generic = format!("{class}{{0,50}}{tail}");
                let star_reg = compile_full(star.as_bytes());
                assert!(star_reg.ops.iter().any(|op| op.opcode == opcode), "{star}");
                let generic_reg = compile_full(generic.as_bytes());
                for input in inputs {
                    let run = |reg: &RegexType| {
                        let (pos, region) = onig_search(
                            reg,
                            input,
                            input.len(),
                            0,
                            input.len(),
                            Some(OnigRegion::new()),
                            ONIG_OPTION_NONE,
                        );
                        let region = region.expect("region");
                        (pos, region.beg[0], region.end[0])
                    };
                    assert_eq!(run(&star_reg), run(&generic_reg), "{star} on {input:x?}");
                }
            }
        }
    }

    #[test]
    fn populate_region_ignores_out_of_bounds_capture_stack_refs() {
        let (mut reg, _) = make_test_context();
        reg.num_mem = 1;
        reg.push_mem_start = 1;
        reg.push_mem_end = 1;

        let stack = vec![StackEntry::Alt {
            pcode: FINISH_PCODE,
            pstr: 0,
            zid: -1,
            is_super: false,
        }];
        let mem_start_stk = vec![MemPtr::invalid(), MemPtr::stack_idx(4)];
        let mem_end_stk = vec![MemPtr::invalid(), MemPtr::stack_idx(5)];

        let mut region = OnigRegion::new();
        populate_region_for_match(
            &mut region,
            &reg,
            1,
            0,
            1,
            &stack,
            &mem_start_stk,
            &mem_end_stk,
        )
        .unwrap();

        assert_eq!(region.beg[0], 0);
        assert_eq!(region.end[0], 1);
        assert_eq!(region.beg[1], ONIG_REGION_NOTPOS);
        assert_eq!(region.end[1], ONIG_REGION_NOTPOS);
    }

    #[test]
    fn is_in_code_range_fast_paths() {
        assert!(!is_in_code_range(&[], 0x41));
        assert!(!is_in_code_range(&[0], 0x41));

        let single = make_code_range_table(&[(0x80, 0x10FFFF)]);
        assert!(!is_in_code_range(&single, 0x7F));
        assert!(is_in_code_range(&single, 0x80));
        assert!(is_in_code_range(&single, 0x4E00));
        assert!(!is_in_code_range(&single, 0x110000));

        let small = make_code_range_table(&[(0x20, 0x2F), (0x40, 0x4F)]);
        assert!(!is_in_code_range(&small, 0x10));
        assert!(is_in_code_range(&small, 0x20));
        assert!(!is_in_code_range(&small, 0x35));
        assert!(is_in_code_range(&small, 0x45));

        let many = make_code_range_table(&[
            (0x0100, 0x010F),
            (0x0200, 0x020F),
            (0x0300, 0x030F),
            (0x0400, 0x040F),
            (0x0500, 0x050F),
        ]);
        assert!(!is_in_code_range(&many, 0x00FF));
        assert!(is_in_code_range(&many, 0x0405));
        assert!(!is_in_code_range(&many, 0x0600));
    }

    #[test]
    fn cclass_mb_ascii_fast_path_matches_and_misses() {
        let reg = compile_regex("[ぁ-ん]".as_bytes());
        assert!(
            has_opcode(&reg, OpCode::CClassMb),
            "expected CClassMb, got: {}",
            opcode_names(&reg)
        );

        let (ascii_miss, _) = compile_and_match("[ぁ-ん]".as_bytes(), b"a");
        assert_eq!(ascii_miss, ONIG_MISMATCH);

        let (multibyte_hit, _) = compile_and_match("[ぁ-ん]".as_bytes(), "あ".as_bytes());
        assert_eq!(multibyte_hit, "あ".len() as i32);
    }

    #[test]
    fn cclass_mb_not_ascii_fast_path_matches_and_misses() {
        let reg = compile_regex("[^ぁ-ん]".as_bytes());
        assert!(
            has_opcode(&reg, OpCode::CClassMbNot) || has_opcode(&reg, OpCode::CClassMixNot),
            "expected CClassMbNot/CClassMixNot, got: {}",
            opcode_names(&reg)
        );

        let (ascii_hit, _) = compile_and_match("[^ぁ-ん]".as_bytes(), b"a");
        assert_eq!(ascii_hit, 1);

        let (multibyte_miss, _) = compile_and_match("[^ぁ-ん]".as_bytes(), "あ".as_bytes());
        assert_eq!(multibyte_miss, ONIG_MISMATCH);
    }

    #[test]
    fn logical_end_truncates_multibyte_decoding_and_matches_negated_classes() {
        let truncated = [0xE2, 0x82];
        let reg = compile_regex(br"\S+");
        let (position, region) = onig_search(
            &reg,
            &truncated,
            truncated.len(),
            0,
            truncated.len(),
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
        );
        assert_eq!(position, 0);
        assert_eq!(region.unwrap().end[0], truncated.len() as i32);

        // `\xC2\xA1` is U+00A1 (not a word character), but its leading byte
        // alone decodes as U+00C2 (a word character). This distinguishes the
        // logical end from the physical slice length.
        let split_character = [0xC2, 0xA1];
        let reg = compile_regex(br"\w");
        let (position, region) = onig_search(
            &reg,
            &split_character,
            1,
            0,
            1,
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
        );
        assert_eq!(position, 0);
        assert_eq!(region.unwrap().end[0], 1);
    }

    #[test]
    fn cclass_mix_and_star_fast_paths() {
        let reg = compile_regex("[aぁ]".as_bytes());
        assert!(
            has_opcode(&reg, OpCode::CClassMix),
            "expected CClassMix, got: {}",
            opcode_names(&reg)
        );

        let (ascii_hit, _) = compile_and_match("[aぁ]".as_bytes(), b"a");
        assert_eq!(ascii_hit, 1);
        let (multibyte_hit, _) = compile_and_match("[aぁ]".as_bytes(), "ぁ".as_bytes());
        assert_eq!(multibyte_hit, "ぁ".len() as i32);

        let reg_star = compile_regex("[aぁ]*".as_bytes());
        assert!(
            has_opcode(&reg_star, OpCode::CClassMixStar),
            "expected CClassMixStar, got: {}",
            opcode_names(&reg_star)
        );
        let (star_hit, _) = compile_and_match("[aぁ]*".as_bytes(), "aaぁ".as_bytes());
        assert_eq!(star_hit, "aaぁ".len() as i32);
    }

    #[test]
    fn cclass_ascii_fast_kind_for_fold_pair() {
        let reg = compile_regex("[xX]".as_bytes());
        let cclass_op = reg
            .ops
            .iter()
            .find(|op| op.opcode == OpCode::CClass)
            .expect("expected CClass opcode");
        if let OperationPayload::CClass { ascii_fast, .. } = cclass_op.payload {
            assert_eq!(ascii_fast, CClassAsciiFastKind::EqFoldLower(b'x'));
        } else {
            panic!("expected CClass payload");
        }

        let (lower_hit, _) = compile_and_match("[xX]".as_bytes(), b"x");
        assert_eq!(lower_hit, 1);
        let (upper_hit, _) = compile_and_match("[xX]".as_bytes(), b"X");
        assert_eq!(upper_hit, 1);
        let (miss, _) = compile_and_match("[xX]".as_bytes(), b"y");
        assert_eq!(miss, ONIG_MISMATCH);
    }

    #[test]
    fn cclass_not_ascii_fast_kind_for_fold_pair() {
        let reg = compile_regex("[^xX]".as_bytes());
        let cclass_not_op = reg
            .ops
            .iter()
            .find(|op| op.opcode == OpCode::CClassNot)
            .expect("expected CClassNot opcode");
        if let OperationPayload::CClass { ascii_fast, .. } = cclass_not_op.payload {
            assert_eq!(ascii_fast, CClassAsciiFastKind::EqFoldLower(b'x'));
        } else {
            panic!("expected CClass payload");
        }

        let (miss, _) = compile_and_match("[^xX]".as_bytes(), b"X");
        assert_eq!(miss, ONIG_MISMATCH);
        let (hit, _) = compile_and_match("[^xX]".as_bytes(), b"y");
        assert_eq!(hit, 1);
    }

    #[test]
    fn cclass_star_ascii_fast_kind_for_fold_pair() {
        let reg = compile_regex("[xX]*".as_bytes());
        let cclass_star_op = reg
            .ops
            .iter()
            .find(|op| op.opcode == OpCode::CClassStar)
            .expect("expected CClassStar opcode");
        if let OperationPayload::CClass { ascii_fast, .. } = cclass_star_op.payload {
            assert_eq!(ascii_fast, CClassAsciiFastKind::EqFoldLower(b'x'));
        } else {
            panic!("expected CClass payload");
        }

        let (star_hit, _) = compile_and_match("[xX]*".as_bytes(), b"XxXy");
        assert_eq!(star_hit, 3);
    }

    // ---- Basic literal matching ----

    #[test]
    fn match_literal_abc() {
        let (r, _) = compile_and_match(b"abc", b"abc");
        assert_eq!(r, 3); // matched 3 bytes
    }

    #[test]
    fn match_literal_fail() {
        let (r, _) = compile_and_match(b"abc", b"abd");
        assert_eq!(r, ONIG_MISMATCH);
    }

    #[test]
    fn match_literal_too_short() {
        let (r, _) = compile_and_match(b"abcd", b"abc");
        assert_eq!(r, ONIG_MISMATCH);
    }

    #[test]
    fn match_empty_pattern() {
        let (r, _) = compile_and_match(b"", b"abc");
        assert_eq!(r, 0); // empty pattern matches with length 0
    }

    #[test]
    fn match_single_char() {
        let (r, _) = compile_and_match(b"x", b"xyz");
        assert_eq!(r, 1);
    }

    // ---- Dot (anychar) ----

    #[test]
    fn match_dot() {
        let (r, _) = compile_and_match(b"a.c", b"abc");
        assert_eq!(r, 3);
    }

    #[test]
    fn match_dot_no_newline() {
        let (r, _) = compile_and_match(b"a.c", b"a\nc");
        assert_eq!(r, ONIG_MISMATCH); // dot doesn't match newline
    }

    // ---- Alternation ----

    #[test]
    fn match_alternation_first() {
        let (r, _) = compile_and_match(b"a|b", b"a");
        assert_eq!(r, 1);
    }

    #[test]
    fn match_alternation_second() {
        let (r, _) = compile_and_match(b"a|b", b"b");
        assert_eq!(r, 1);
    }

    #[test]
    fn match_alternation_fail() {
        let (r, _) = compile_and_match(b"a|b", b"c");
        assert_eq!(r, ONIG_MISMATCH);
    }

    // ---- Quantifiers ----

    #[test]
    fn match_star() {
        let (r, _) = compile_and_match(b"a*", b"aaa");
        assert_eq!(r, 3);
    }

    #[test]
    fn match_star_empty() {
        let (r, _) = compile_and_match(b"a*", b"bbb");
        assert_eq!(r, 0); // a* can match empty
    }

    #[test]
    fn match_plus() {
        let (r, _) = compile_and_match(b"a+", b"aaa");
        assert_eq!(r, 3);
    }

    #[test]
    fn match_plus_fail() {
        let (r, _) = compile_and_match(b"a+", b"bbb");
        assert_eq!(r, ONIG_MISMATCH);
    }

    #[test]
    fn match_question() {
        let (r, _) = compile_and_match(b"a?b", b"ab");
        assert_eq!(r, 2);
    }

    #[test]
    fn match_question_without() {
        let (r, _) = compile_and_match(b"a?b", b"b");
        assert_eq!(r, 1);
    }

    #[test]
    fn match_lazy_star() {
        // a*? should match as few as possible from position 0
        let (r, _) = compile_and_match(b"a*?", b"aaa");
        assert_eq!(r, 0); // lazy: match empty
    }

    // ---- Character classes ----

    #[test]
    fn match_char_class() {
        let (r, _) = compile_and_match(b"[abc]", b"b");
        assert_eq!(r, 1);
    }

    #[test]
    fn match_char_class_fail() {
        let (r, _) = compile_and_match(b"[abc]", b"d");
        assert_eq!(r, ONIG_MISMATCH);
    }

    #[test]
    fn match_char_class_range() {
        let (r, _) = compile_and_match(b"[a-z]", b"m");
        assert_eq!(r, 1);
    }

    #[test]
    fn match_char_class_negated() {
        let (r, _) = compile_and_match(b"[^abc]", b"d");
        assert_eq!(r, 1);
    }

    #[test]
    fn match_char_class_negated_fail() {
        let (r, _) = compile_and_match(b"[^abc]", b"a");
        assert_eq!(r, ONIG_MISMATCH);
    }

    // ---- Anchors ----

    #[test]
    fn match_begin_anchor() {
        let (r, _) = compile_and_match(b"^abc", b"abc");
        assert_eq!(r, 3);
    }

    #[test]
    fn match_end_anchor() {
        let (r, _) = compile_and_match(b"abc$", b"abc");
        assert_eq!(r, 3);
    }

    #[test]
    fn match_begin_end_anchors() {
        let (r, _) = compile_and_match(b"^abc$", b"abc");
        assert_eq!(r, 3);
    }

    // ---- Capture groups ----

    #[test]
    fn match_capture_group() {
        let (r, region) = compile_and_match(b"(abc)", b"abc");
        assert_eq!(r, 3);
        let region = region.unwrap();
        assert!(region.num_regs >= 2);
        assert_eq!(region.beg[0], 0);
        assert_eq!(region.end[0], 3);
        assert_eq!(region.beg[1], 0);
        assert_eq!(region.end[1], 3);
    }

    #[test]
    fn match_multiple_captures() {
        let (r, region) = compile_and_match(b"(a)(b)(c)", b"abc");
        assert_eq!(r, 3);
        let region = region.unwrap();
        assert!(region.num_regs >= 4);
        // Group 0: full match
        assert_eq!(region.beg[0], 0);
        assert_eq!(region.end[0], 3);
        // Group 1: a
        assert_eq!(region.beg[1], 0);
        assert_eq!(region.end[1], 1);
        // Group 2: b
        assert_eq!(region.beg[2], 1);
        assert_eq!(region.end[2], 2);
        // Group 3: c
        assert_eq!(region.beg[3], 2);
        assert_eq!(region.end[3], 3);
    }

    #[test]
    fn match_non_capturing_group() {
        let (r, _) = compile_and_match(b"(?:abc)", b"abc");
        assert_eq!(r, 3);
    }

    // ---- Search (find anywhere in string) ----

    #[test]
    fn search_literal() {
        let (pos, _) = compile_and_search(b"bc", b"abcdef");
        assert_eq!(pos, 1); // found at position 1
    }

    #[test]
    fn search_literal_not_found() {
        let (pos, _) = compile_and_search(b"xyz", b"abcdef");
        assert_eq!(pos, ONIG_MISMATCH);
    }

    #[test]
    fn search_at_start() {
        let (pos, _) = compile_and_search(b"abc", b"abcdef");
        assert_eq!(pos, 0);
    }

    #[test]
    fn search_at_end() {
        let (pos, _) = compile_and_search(b"ef", b"abcdef");
        assert_eq!(pos, 4);
    }

    #[test]
    fn search_with_captures() {
        let (pos, region) = compile_and_search(b"(b)(c)", b"abcdef");
        assert_eq!(pos, 1);
        let region = region.unwrap();
        assert_eq!(region.beg[1], 1);
        assert_eq!(region.end[1], 2);
        assert_eq!(region.beg[2], 2);
        assert_eq!(region.end[2], 3);
    }

    #[test]
    fn search_with_quantifier() {
        let (pos, _) = compile_and_search(b"a+", b"bbaab");
        assert_eq!(pos, 2);
    }

    // ---- Complex patterns ----

    #[test]
    fn match_word_boundary() {
        let (pos, _) = compile_and_search(b"\\bfoo\\b", b"a foo b");
        assert_eq!(pos, 2);
    }

    #[test]
    fn match_complex_alternation() {
        let (r, _) = compile_and_match(b"abc|def|ghi", b"def");
        assert_eq!(r, 3);
    }

    #[test]
    fn match_nested_groups() {
        let (r, region) = compile_and_match(b"((a)(b))", b"ab");
        assert_eq!(r, 2);
        let region = region.unwrap();
        // Group 1: ab
        assert_eq!(region.beg[1], 0);
        assert_eq!(region.end[1], 2);
        // Group 2: a
        assert_eq!(region.beg[2], 0);
        assert_eq!(region.end[2], 1);
        // Group 3: b
        assert_eq!(region.beg[3], 1);
        assert_eq!(region.end[3], 2);
    }

    #[test]
    fn match_dot_star() {
        let (r, _) = compile_and_match(b"a.*b", b"aXXXb");
        assert_eq!(r, 5);
    }

    #[test]
    fn match_backtracking() {
        // Pattern: a.*b matches "axb" - requires backtracking
        let (r, _) = compile_and_match(b"a.*b", b"axb");
        assert_eq!(r, 3);
    }

    #[test]
    fn match_interval_quantifier() {
        let (r, _) = compile_and_match(b"a{3}", b"aaa");
        assert_eq!(r, 3);
    }

    #[test]
    fn match_interval_quantifier_fail() {
        let (r, _) = compile_and_match(b"a{3}", b"aa");
        assert_eq!(r, ONIG_MISMATCH);
    }

    #[test]
    fn match_interval_range() {
        let (r, _) = compile_and_match(b"a{2,4}", b"aaa");
        assert_eq!(r, 3);
    }

    #[test]
    fn match_interval_range_min() {
        let (r, _) = compile_and_match(b"a{2,4}", b"aa");
        assert_eq!(r, 2);
    }

    #[test]
    fn match_digit_class() {
        let (r, _) = compile_and_match(b"\\d+", b"123");
        assert_eq!(r, 3);
    }

    #[test]
    fn match_word_class() {
        let (r, _) = compile_and_match(b"\\w+", b"abc123_");
        assert_eq!(r, 7);
    }

    #[test]
    fn search_email_like() {
        let (pos, _) = compile_and_search(b"\\w+@\\w+", b"send to user@host ok");
        assert_eq!(pos, 8); // "user@host" starts at position 8
    }

    #[test]
    fn match_escaped_special() {
        let (r, _) = compile_and_match(b"a\\.b", b"a.b");
        assert_eq!(r, 3);
    }

    #[test]
    fn match_back_reference() {
        let (r, _) = compile_and_match(b"(a)\\1", b"aa");
        assert_eq!(r, 2);
    }

    #[test]
    fn match_back_reference_fail() {
        let (r, _) = compile_and_match(b"(a)\\1", b"ab");
        assert_eq!(r, ONIG_MISMATCH);
    }

    // ---- Safety limits ----

    // Safety limit tests use a lock to avoid interfering with each other
    // (since limits are global statics).
    #[test]
    fn global_limit_setters_publish_a_new_revision() {
        let _lock = LIMIT_TEST_LOCK.lock().unwrap();
        let old_retry_match = onig_get_retry_limit_in_match();
        let old_retry_search = onig_get_retry_limit_in_search();
        let old_stack = onig_get_match_stack_limit();
        let old_time = onig_get_time_limit();
        let mut revision = onig_get_global_limit_revision();

        onig_set_retry_limit_in_match(old_retry_match);
        assert_ne!(onig_get_global_limit_revision(), revision);
        revision = onig_get_global_limit_revision();
        onig_set_retry_limit_in_search(old_retry_search);
        assert_ne!(onig_get_global_limit_revision(), revision);
        revision = onig_get_global_limit_revision();
        onig_set_match_stack_limit(old_stack);
        assert_ne!(onig_get_global_limit_revision(), revision);
        revision = onig_get_global_limit_revision();
        onig_set_time_limit(old_time);
        assert_ne!(onig_get_global_limit_revision(), revision);
    }

    #[test]
    fn retry_limit_in_match() {
        let _lock = LIMIT_TEST_LOCK.lock().unwrap();

        // (a*)*b against "aaa..." causes catastrophic backtracking
        let (mut reg, mut env) = make_test_context();
        let pattern = b"(a*)*b";
        let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env).unwrap();
        let r = regcomp::compile_from_tree(&root, &mut reg, &env);
        assert_eq!(r, 0);

        let input = b"aaaaaaaaaa"; // 10 'a's, no 'b'

        // Save old limits, set low retry limit
        let old_retry = onig_get_retry_limit_in_match();
        let old_stack = onig_get_match_stack_limit();
        let old_time = onig_get_time_limit();
        onig_set_retry_limit_in_match(100);
        onig_set_match_stack_limit(0); // unlimited
        onig_set_time_limit(0); // unlimited

        let (result, _) = onig_search(
            &reg,
            input,
            input.len(),
            0,
            input.len(),
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
        );
        assert_eq!(result, ONIGERR_RETRY_LIMIT_IN_MATCH_OVER);

        // Restore
        onig_set_retry_limit_in_match(old_retry);
        onig_set_match_stack_limit(old_stack);
        onig_set_time_limit(old_time);
    }

    #[test]
    fn stack_limit_over() {
        let _lock = LIMIT_TEST_LOCK.lock().unwrap();

        // Use onig_match directly to avoid forward_search optimization
        let (mut reg, mut env) = make_test_context();
        let pattern = b".*.*.*.*.*";
        let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env).unwrap();
        let r = regcomp::compile_from_tree(&root, &mut reg, &env);
        assert_eq!(r, 0);

        let input = b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; // 30 chars

        // Set very low stack limit, disable retry limit
        let old_retry = onig_get_retry_limit_in_match();
        let old_stack = onig_get_match_stack_limit();
        let old_time = onig_get_time_limit();
        onig_set_retry_limit_in_match(0); // unlimited
        onig_set_match_stack_limit(20);
        onig_set_time_limit(0); // unlimited

        let (result, _) = onig_match(
            &reg,
            input,
            input.len(),
            0,
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
        );
        assert_eq!(result, ONIGERR_MATCH_STACK_LIMIT_OVER);

        // Restore
        onig_set_retry_limit_in_match(old_retry);
        onig_set_match_stack_limit(old_stack);
        onig_set_time_limit(old_time);
    }

    #[test]
    fn time_limit_over() {
        let _lock = LIMIT_TEST_LOCK.lock().unwrap();

        let (mut reg, mut env) = make_test_context();
        let pattern = b"(a*)*b";
        let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env).unwrap();
        let r = regcomp::compile_from_tree(&root, &mut reg, &env);
        assert_eq!(r, 0);

        let input = b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; // 30 'a's

        // Set 1ms time limit, disable other limits
        let old_retry = onig_get_retry_limit_in_match();
        let old_stack = onig_get_match_stack_limit();
        let old_time = onig_get_time_limit();
        onig_set_retry_limit_in_match(0); // unlimited
        onig_set_match_stack_limit(0); // unlimited
        onig_set_time_limit(1);

        let (result, _) = onig_search(
            &reg,
            input,
            input.len(),
            0,
            input.len(),
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
        );
        assert_eq!(result, ONIGERR_TIME_LIMIT_OVER);

        // Restore
        onig_set_retry_limit_in_match(old_retry);
        onig_set_match_stack_limit(old_stack);
        onig_set_time_limit(old_time);
    }

    #[test]
    fn retry_limit_in_search_caps_the_first_match_attempt() {
        // C caps retry_limit_in_match by the search budget still left, so the
        // very first start position already stops at the search limit.
        let (mut reg, mut env) = make_test_context();
        let pattern = b"(a+)+b";
        let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env).unwrap();
        let r = regcomp::compile_from_tree(&root, &mut reg, &env);
        assert_eq!(r, 0);

        let input = vec![b'a'; 40];
        let mut mp = onig_new_match_param();
        mp.retry_limit_in_match = 0;
        mp.retry_limit_in_search = 1_000;
        mp.time_limit = 0;

        let started = Instant::now();
        let (result, _) = onig_search_with_param(
            &reg,
            &input,
            input.len(),
            0,
            input.len(),
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
            &mp,
        );
        assert_eq!(result, ONIGERR_RETRY_LIMIT_IN_SEARCH_OVER);
        assert!(started.elapsed() < std::time::Duration::from_secs(1));

        // A tighter per-match limit still reports itself.
        mp.retry_limit_in_match = 100;
        let (result, _) = onig_search_with_param(
            &reg,
            &input,
            input.len(),
            0,
            input.len(),
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
            &mp,
        );
        assert_eq!(result, ONIGERR_RETRY_LIMIT_IN_MATCH_OVER);
    }

    #[test]
    fn time_limit_counts_backtracks_across_start_positions() {
        // Each start position backtracks fewer than CHECK_TIME_INTERVAL times,
        // so a per-position counter never reads the clock. C keeps the counter
        // and the deadline per search (TIME_LIMIT_INIT, CHECK_TIME_LIMIT_IN_MATCH).
        let (mut reg, mut env) = make_test_context();
        let pattern = b"a{1,400}?(?=b)";
        let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env).unwrap();
        let r = regcomp::compile_from_tree(&root, &mut reg, &env);
        assert_eq!(r, 0);

        let input = vec![b'a'; 500_000];
        let mut mp = onig_new_match_param();
        mp.retry_limit_in_match = 0;
        mp.retry_limit_in_search = 0;
        onig_set_time_limit_of_match_param(&mut mp, 10);

        let started = Instant::now();
        let (result, _) = onig_search_with_param(
            &reg,
            &input,
            input.len(),
            0,
            input.len(),
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
            &mp,
        );
        assert_eq!(result, ONIGERR_TIME_LIMIT_OVER);
        // Without the per-search counter this search runs for seconds.
        assert!(started.elapsed() < std::time::Duration::from_millis(1000));
    }

    #[test]
    fn limits_zero_means_unlimited() {
        // Verify default limits (0 = unlimited) don't interfere with normal matching
        let (r, _) = compile_and_match(b"a*b", b"aaab");
        assert_eq!(r, 4);
    }

    // ---- Backward search ----

    #[test]
    fn backward_search_basic() {
        // Search backward from end to find last occurrence
        let (mut reg, mut env) = make_test_context();
        let pattern = b"ab";
        let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env).unwrap();
        let r = regcomp::compile_from_tree(&root, &mut reg, &env);
        assert_eq!(r, 0);

        let input = b"xxabxxabxx"; // "ab" at positions 2 and 6
        // Backward search: start=10 (end), range=0 (beginning)
        let (result, _) = onig_search(
            &reg,
            input,
            input.len(),
            input.len(),
            0,
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
        );
        // Should find the last "ab" at position 6
        assert_eq!(result, 6);
    }

    #[test]
    fn backward_search_at_start() {
        let (mut reg, mut env) = make_test_context();
        let pattern = b"he";
        let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env).unwrap();
        let r = regcomp::compile_from_tree(&root, &mut reg, &env);
        assert_eq!(r, 0);

        let input = b"hello";
        let (result, _) = onig_search(
            &reg,
            input,
            input.len(),
            input.len(),
            0,
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
        );
        assert_eq!(result, 0);
    }

    #[test]
    fn backward_search_no_match() {
        let (mut reg, mut env) = make_test_context();
        let pattern = b"xyz";
        let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env).unwrap();
        let r = regcomp::compile_from_tree(&root, &mut reg, &env);
        assert_eq!(r, 0);

        let input = b"hello world";
        let (result, _) = onig_search(
            &reg,
            input,
            input.len(),
            input.len(),
            0,
            Some(OnigRegion::new()),
            ONIG_OPTION_NONE,
        );
        assert_eq!(result, ONIG_MISMATCH);
    }

    #[test]
    fn forward_search_rejects_min_distance_beyond_the_slice() {
        let (mut reg, mut env) = make_test_context();
        let pattern = b"a";
        let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env).unwrap();
        assert_eq!(regcomp::compile_from_tree(&root, &mut reg, &env), 0);

        // This models optimizer metadata whose minimum distance exceeds the
        // available input, without constructing an invalid C pointer range.
        reg.dist_min = OnigLen::MAX - 1;
        assert_eq!(forward_search(&reg, b"a", 1, 0, 1), None);
    }

    #[test]
    fn backward_search_saturates_distance_bounds_at_the_slice_start() {
        let (mut reg, mut env) = make_test_context();
        let pattern = b"ab";
        let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env).unwrap();
        assert_eq!(regcomp::compile_from_tree(&root, &mut reg, &env), 0);

        reg.optimize = OptimizeType::Str;
        reg.exact = pattern.to_vec();
        reg.dist_min = OnigLen::MAX - 1;
        reg.dist_max = OnigLen::MAX - 1;
        assert_eq!(backward_search(&reg, b"ab", 2, 0, 0, 0), Some((0, 0)));
    }

    #[test]
    fn optimized_search_bounds_large_finite_distances_to_the_slice() {
        let (mut reg, mut env) = make_test_context();
        let pattern = b"a";
        let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env).unwrap();
        assert_eq!(regcomp::compile_from_tree(&root, &mut reg, &env), 0);
        reg.dist_max = OnigLen::MAX - 1;

        let input = b"a";
        let (forward, _) = onig_search(
            &reg,
            input,
            input.len(),
            0,
            input.len(),
            None,
            ONIG_OPTION_NONE,
        );
        assert_eq!(forward, 0);

        let (backward, _) = onig_search(
            &reg,
            input,
            input.len(),
            input.len(),
            0,
            None,
            ONIG_OPTION_NONE,
        );
        assert_eq!(backward, 0);
    }
}