// regcomp.rs - Port of regcomp.c
// Compiler: converts AST (Node trees) into bytecode (Operation arrays).
//
// This is a 1:1 port of oniguruma's regcomp.c (~8,500 LOC).
// Structure mirrors the C original: operation management → string compilation →
// cclass compilation → quantifier compilation → bag compilation → anchor compilation →
// tree compilation → entry point.
#![allow(non_upper_case_globals)]
#![allow(unused_variables)]
#![allow(unused_assignments)]
#![allow(unused_mut)]
use std::sync::atomic::{AtomicU32, Ordering};
use crate::oniguruma::*;
use crate::regenc::*;
use crate::regint::*;
use crate::regparse_types::*;
// ============================================================================
// Global Default Case Fold Flag (port of C's OnigDefaultCaseFoldFlag)
// ============================================================================
static DEFAULT_CASE_FOLD_FLAG: AtomicU32 = AtomicU32::new(ONIGENC_CASE_FOLD_MIN);
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_get_default_case_fold_flag() -> OnigCaseFoldType {
DEFAULT_CASE_FOLD_FLAG.load(Ordering::Relaxed)
}
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn onig_set_default_case_fold_flag(flag: OnigCaseFoldType) -> i32 {
DEFAULT_CASE_FOLD_FLAG.store(flag, Ordering::Relaxed);
0
}
/// Maximum `{n}` exact count that gets unrolled into flat bytecode.
/// Beyond this threshold we fall back to the REPEAT/REPEAT_INC loop.
const EXACT_REPEAT_UNROLL_THRESHOLD: i32 = 16;
/// Maximum bytecode size of a finite greedy range that is expanded inline.
///
/// This mirrors Oniguruma's `QUANTIFIER_EXPAND_LIMIT_SIZE` guard. Larger
/// `{n,m}` ranges use the bounded REPEAT/REPEAT_INC bytecode instead.
const QUANTIFIER_EXPAND_LIMIT_SIZE: OnigLen = 10;
/// Get encoded character length from a byte slice (for optimization functions).
fn enclen(enc: OnigEncoding, p: &[u8], _offset: usize) -> usize {
if p.is_empty() {
return 1;
}
enc.mbc_enc_len(p)
}
// ============================================================================
// Constants (matching C OPSIZE_* and SIZE_INC)
// ============================================================================
// All operations are 1 slot in the ops array (matching C where every OPSIZE_* = 1)
const SIZE_INC: i32 = 1;
const OPSIZE_ANYCHAR_STAR: i32 = 1;
const OPSIZE_ANYCHAR_STAR_PEEK_NEXT: i32 = 1;
const OPSIZE_JUMP: i32 = 1;
const OPSIZE_PUSH: i32 = 1;
const OPSIZE_PUSH_SUPER: i32 = 1;
const OPSIZE_POP: i32 = 1;
const OPSIZE_POP_TO_MARK: i32 = 1;
const OPSIZE_PUSH_OR_JUMP_EXACT1: i32 = 1;
const OPSIZE_PUSH_IF_PEEK_NEXT: i32 = 1;
const OPSIZE_REPEAT: i32 = 1;
const OPSIZE_REPEAT_INC: i32 = 1;
const OPSIZE_REPEAT_INC_NG: i32 = 1;
const OPSIZE_WORD_BOUNDARY: i32 = 1;
const OPSIZE_BACKREF: i32 = 1;
const OPSIZE_FAIL: i32 = 1;
const OPSIZE_MEM_START: i32 = 1;
const OPSIZE_MEM_START_PUSH: i32 = 1;
const OPSIZE_MEM_END_PUSH: i32 = 1;
const OPSIZE_MEM_END_PUSH_REC: i32 = 1;
const OPSIZE_MEM_END: i32 = 1;
const OPSIZE_MEM_END_REC: i32 = 1;
const OPSIZE_EMPTY_CHECK_START: i32 = 1;
const OPSIZE_EMPTY_CHECK_END: i32 = 1;
const OPSIZE_CHECK_POSITION: i32 = 1;
const OPSIZE_CALL: i32 = 1;
const OPSIZE_RETURN: i32 = 1;
const OPSIZE_MOVE: i32 = 1;
const OPSIZE_STEP_BACK_START: i32 = 1;
const OPSIZE_STEP_BACK_NEXT: i32 = 1;
const OPSIZE_CUT_TO_MARK: i32 = 1;
const OPSIZE_MARK: i32 = 1;
const OPSIZE_SAVE_VAL: i32 = 1;
const OPSIZE_UPDATE_VAR: i32 = 1;
// ============================================================================
// Operation management
// ============================================================================
/// Add an operation with the given opcode and payload to the regex's ops array.
/// Returns the index of the newly added operation.
fn add_op(reg: &mut RegexType, opcode: OpCode, payload: OperationPayload) -> i32 {
let idx = reg.ops.len();
reg.ops.push(Operation { opcode, payload });
idx as i32
}
/// Get the index of the current (last) operation.
#[cfg_attr(coverage_nightly, coverage(off))]
fn ops_curr_offset(reg: &RegexType) -> i32 {
(reg.ops.len() as i32) - 1
}
// ============================================================================
// Utility functions
// ============================================================================
/// Safe multiplication comparison: a * b > limit
#[cfg_attr(coverage_nightly, coverage(off))]
fn len_multiply_cmp(a: OnigLen, b: i32, limit: OnigLen) -> bool {
if a == 0 || b == 0 {
return false;
}
if a > limit / (b as OnigLen) {
return true;
}
a * (b as OnigLen) > limit
}
/// Whether a finite greedy range can use inline expansion without producing
/// excessive bytecode. Port of the expansion guard in `compile_quantifier_node`.
fn can_expand_finite_greedy_quantifier(body_len: i32, upper: i32) -> bool {
upper == 1
|| (body_len >= 0
&& upper >= 0
&& !len_multiply_cmp(
body_len as OnigLen + OPSIZE_PUSH as OnigLen,
upper,
QUANTIFIER_EXPAND_LIMIT_SIZE,
))
}
/// Whether a quantifier body contains a recursive subexpression call.
///
/// The REPEAT VM path is not yet equivalent for recursive calls, but an
/// unrelated call elsewhere in the pattern must not disable the finite-range
/// expansion limit. Recursion is annotated during the call-resolution pass
/// before compilation starts.
fn quantifier_body_contains_recursion(node: &Node) -> bool {
if node.has_status(ND_ST_RECURSION) {
return true;
}
match &node.inner {
NodeInner::List(cons) | NodeInner::Alt(cons) => {
quantifier_body_contains_recursion(&cons.car)
|| cons
.cdr
.as_deref()
.is_some_and(quantifier_body_contains_recursion)
}
NodeInner::Quant(qn) => qn
.body
.as_deref()
.is_some_and(quantifier_body_contains_recursion),
NodeInner::Anchor(an) => an
.body
.as_deref()
.is_some_and(quantifier_body_contains_recursion),
NodeInner::Call(cn) => cn
.body
.as_deref()
.is_some_and(quantifier_body_contains_recursion),
NodeInner::Bag(bag) => {
bag.body
.as_deref()
.is_some_and(quantifier_body_contains_recursion)
|| match &bag.bag_data {
BagData::IfElse {
then_node,
else_node,
} => {
then_node
.as_deref()
.is_some_and(quantifier_body_contains_recursion)
|| else_node
.as_deref()
.is_some_and(quantifier_body_contains_recursion)
}
_ => false,
}
}
_ => false,
}
}
/// Add two lengths safely, capping at INFINITE_LEN.
pub fn distance_add(d1: OnigLen, d2: OnigLen) -> OnigLen {
if d1 == INFINITE_LEN || d2 == INFINITE_LEN {
INFINITE_LEN
} else if d1 <= INFINITE_LEN - d2 {
d1 + d2
} else {
INFINITE_LEN
}
}
/// Multiply a length by a count safely, capping at INFINITE_LEN.
fn distance_multiply(d: OnigLen, m: i32) -> OnigLen {
if m == 0 {
return 0;
}
if d >= INFINITE_LEN / (m as OnigLen) {
return INFINITE_LEN;
}
d * (m as OnigLen)
}
/// Check if a bitset is empty (all zeros).
fn bitset_is_empty(bs: &BitSet) -> bool {
bs.iter().all(|&slot| slot == 0)
}
/// Check if a node is a "strict real" node (actually matches characters).
fn is_strict_real_node(node: &Node) -> bool {
matches!(
node.inner,
NodeInner::String(_) | NodeInner::CClass(_) | NodeInner::CType(_)
)
}
// ============================================================================
// get_tree_head_literal / is_exclusive / tune_next (C lines 3043-4743)
// ============================================================================
/// Walk the AST to find the leading literal node.
/// If `exact` is true, only String nodes (not IGNORECASE) qualify.
/// If `exact` is false, CType and CClass nodes also qualify.
/// Returns a reference to the found node, or None.
fn get_tree_head_literal<'a>(node: &'a Node, exact: bool, _reg: &RegexType) -> Option<&'a Node> {
match &node.inner {
NodeInner::BackRef(_) | NodeInner::Alt(_) | NodeInner::Call(_) => None,
NodeInner::CType(ct) => {
if ct.ctype == CTYPE_ANYCHAR {
None
} else if !exact {
Some(node)
} else {
None
}
}
NodeInner::CClass(_) => {
if !exact {
Some(node)
} else {
None
}
}
NodeInner::List(cons) => get_tree_head_literal(&cons.car, exact, _reg),
NodeInner::String(sn) => {
if sn.s.is_empty() {
return None;
}
// ND_IS_REAL_IGNORECASE = IGNORECASE && !CRUDE
let is_real_ic = (node.status & ND_ST_IGNORECASE) != 0 && !sn.is_crude();
if !exact || !is_real_ic {
Some(node)
} else {
None
}
}
NodeInner::Quant(qn) => {
if qn.lower > 0 {
if let Some(he) = qn.head_exact {
// head_exact is already extracted; but it's a u8, not a node ref.
// For the recursive case, re-derive from body.
None // Fall through to body check
} else {
qn.body
.as_ref()
.and_then(|b| get_tree_head_literal(b, exact, _reg))
}
} else {
None
}
}
NodeInner::Bag(bn) => match bn.bag_type {
BagType::Option | BagType::Memory | BagType::StopBacktrack => bn
.body
.as_ref()
.and_then(|b| get_tree_head_literal(b, exact, _reg)),
_ => None,
},
NodeInner::Anchor(an) => {
if an.anchor_type == ANCR_PREC_READ {
an.body
.as_ref()
.and_then(|b| get_tree_head_literal(b, exact, _reg))
} else {
None
}
}
_ => None,
}
}
/// Extract the first byte from a head literal node (String only, for exact matching).
fn get_head_literal_byte(node: &Node, exact: bool, reg: &RegexType) -> Option<u8> {
let n = get_tree_head_literal(node, exact, reg)?;
if let NodeInner::String(sn) = &n.inner {
if !sn.s.is_empty() && sn.s[0] != 0 {
return Some(sn.s[0]);
}
}
None
}
/// Check if a codepoint is in a character class.
fn onig_is_code_in_cc(enc: OnigEncoding, code: OnigCodePoint, cc: &CClassNode) -> bool {
let in_bs = if (code as usize) < SINGLE_BYTE_SIZE {
bitset_at(&cc.bs, code as usize)
} else {
false
};
let in_mbuf = if let Some(ref mbuf) = cc.mbuf {
onig_is_in_code_range_bbuf(mbuf, code)
} else {
false
};
let result = in_bs || in_mbuf;
if cc.is_not() {
!result
} else {
result
}
}
/// Check if code ranges in a BBuf contain a codepoint.
/// BBuf stores code ranges as packed u32 values in native-endian bytes.
fn onig_is_in_code_range_bbuf(mbuf: &BBuf, code: OnigCodePoint) -> bool {
let data = &mbuf.data;
if data.len() < 4 {
return false;
}
let read_u32 = |offset: usize| -> u32 {
if offset + 4 > data.len() {
return 0;
}
u32::from_ne_bytes([
data[offset],
data[offset + 1],
data[offset + 2],
data[offset + 3],
])
};
let n = read_u32(0) as usize;
let mut low = 0usize;
let mut high = n;
while low < high {
let mid = (low + high) / 2;
let from = read_u32((mid * 2 + 1) * 4);
let to = read_u32((mid * 2 + 2) * 4);
if code < from {
high = mid;
} else if code > to {
low = mid + 1;
} else {
return true;
}
}
false
}
/// Check if two head-literal nodes are mutually exclusive.
/// If they are, a quantifier before x followed by y can be made possessive.
fn is_exclusive(x: &Node, y: &Node, reg: &RegexType) -> bool {
// Dispatch on x type, with swap for certain y types
match (&x.inner, &y.inner) {
// CType × CType
(NodeInner::CType(xct), NodeInner::CType(yct)) => {
if xct.ctype == CTYPE_ANYCHAR || yct.ctype == CTYPE_ANYCHAR {
return false;
}
xct.ctype == yct.ctype && xct.not != yct.not && xct.ascii_mode == yct.ascii_mode
}
// CType × CClass or CType × String → swap and retry
(NodeInner::CType(_), NodeInner::CClass(_)) => is_exclusive(y, x, reg),
(NodeInner::CType(_), NodeInner::String(_)) => is_exclusive(y, x, reg),
// CClass × CType
(NodeInner::CClass(xc), NodeInner::CType(yct)) => {
if yct.ctype == CTYPE_ANYCHAR {
return false;
}
if yct.ctype != ONIGENC_CTYPE_WORD as i32 {
return false;
}
if !yct.not {
// \w: check if any word chars are in the class
if xc.mbuf.is_some() || xc.is_not() {
return false;
}
let range = if yct.ascii_mode {
128
} else {
SINGLE_BYTE_SIZE
};
for i in 0..range {
if bitset_at(&xc.bs, i) && is_code_word(reg.enc, i as OnigCodePoint) {
return false;
}
}
true
} else {
// \W: check if any non-word chars are in the class
if xc.mbuf.is_some() || xc.is_not() {
return false;
}
let range = if yct.ascii_mode {
128
} else {
SINGLE_BYTE_SIZE
};
for i in 0..range {
if !is_code_word(reg.enc, i as OnigCodePoint) && bitset_at(&xc.bs, i) {
return false;
}
}
for i in range..SINGLE_BYTE_SIZE {
if bitset_at(&xc.bs, i) {
return false;
}
}
true
}
}
// CClass × CClass
(NodeInner::CClass(xc), NodeInner::CClass(yc)) => {
for i in 0..SINGLE_BYTE_SIZE {
let xv = bitset_at(&xc.bs, i);
let x_in = if xc.is_not() { !xv } else { xv };
if x_in {
let yv = bitset_at(&yc.bs, i);
let y_in = if yc.is_not() { !yv } else { yv };
if y_in {
return false;
}
}
}
// If either has no mbuf and is not negated, they can't overlap on multi-byte
if (xc.mbuf.is_none() && !xc.is_not()) || (yc.mbuf.is_none() && !yc.is_not()) {
return true;
}
false
}
// CClass × String → swap
(NodeInner::CClass(_), NodeInner::String(_)) => is_exclusive(y, x, reg),
// String × CType
(NodeInner::String(xs), NodeInner::CType(yct)) => {
if xs.s.is_empty() {
return false;
}
if yct.ctype == CTYPE_ANYCHAR {
return false;
}
if yct.ctype == ONIGENC_CTYPE_WORD as i32 {
let is_word = if !yct.ascii_mode {
is_mbc_word(reg.enc, &xs.s)
} else {
is_mbc_word_ascii(reg.enc, &xs.s)
};
return if is_word { yct.not } else { !yct.not };
}
false
}
// String × CClass
(NodeInner::String(xs), NodeInner::CClass(yc)) => {
if xs.s.is_empty() {
return false;
}
let code = reg.enc.mbc_to_code(&xs.s, xs.s.len());
!onig_is_code_in_cc(reg.enc, code, yc)
}
// String × String
(NodeInner::String(xs), NodeInner::String(ys)) => {
if xs.s.is_empty() || ys.s.is_empty() {
return false;
}
let len = xs.s.len().min(ys.s.len());
for i in 0..len {
if xs.s[i] != ys.s[i] {
return true;
}
}
false
}
_ => false,
}
}
/// Check if a character is a "word" character.
fn is_code_word(enc: OnigEncoding, code: OnigCodePoint) -> bool {
if code < 128 {
let c = code as u8;
c.is_ascii_alphanumeric() || c == b'_'
} else {
enc.is_code_ctype(code, ONIGENC_CTYPE_WORD)
}
}
/// Check if the first character in buf is a word character.
fn is_mbc_word(enc: OnigEncoding, buf: &[u8]) -> bool {
if buf.is_empty() {
return false;
}
let code = enc.mbc_to_code(buf, buf.len());
is_code_word(enc, code)
}
/// Check if the first character in buf is an ASCII word character.
fn is_mbc_word_ascii(_enc: OnigEncoding, buf: &[u8]) -> bool {
if buf.is_empty() {
return false;
}
let c = buf[0];
c.is_ascii_alphanumeric() || c == b'_'
}
/// tune_next: propagate next-node info to optimize quantifiers.
/// Sets qn.next_head_exact for PushIfPeekNext optimization.
/// Auto-possessifies when body and next are exclusive.
fn tune_next(node: &mut Node, next_node: &Node, reg: &RegexType) -> i32 {
tune_next_inner(node, next_node, reg, false)
}
fn tune_next_inner(node: &mut Node, next_node: &Node, reg: &RegexType, called: bool) -> i32 {
let status = node.status;
match &mut node.inner {
NodeInner::Quant(qn) => {
let mut replacement = None;
if qn.greedy && is_infinite_repeat(qn.upper) {
if !called {
if let Some(byte) = get_head_literal_byte(next_node, true, reg) {
qn.next_head_exact = Some(byte);
}
}
if qn.lower <= 1 {
let should_possessify = qn.body.as_ref().is_some_and(|body| {
is_strict_real_node(body)
&& get_tree_head_literal(body, false, reg).is_some_and(|x| {
get_tree_head_literal(next_node, false, reg)
.is_some_and(|y| is_exclusive(x, y, reg))
})
});
if should_possessify {
let body = qn.body.take().expect("quantifier body was checked above");
replacement = Some(NodeInner::Bag(BagNode {
body: Some(Box::new(Node {
inner: NodeInner::Quant(QuantNode {
body: Some(body),
lower: qn.lower,
upper: qn.upper,
greedy: qn.greedy,
emptiness: qn.emptiness,
head_exact: qn.head_exact.take(),
next_head_exact: qn.next_head_exact.take(),
include_referred: qn.include_referred,
empty_status_mem: qn.empty_status_mem,
}),
status,
parent: std::ptr::null_mut(),
})),
bag_type: BagType::StopBacktrack,
bag_data: BagData::StopBacktrack,
min_len: 0,
max_len: INFINITE_LEN,
min_char_len: 0,
max_char_len: INFINITE_LEN,
opt_count: 0,
}));
}
}
}
if let Some(inner) = replacement {
node.inner = inner;
node.status |= ND_ST_STRICT_REAL_REPEAT;
}
0
}
NodeInner::Bag(bn) if bn.bag_type == BagType::Memory => {
let called = called || (status & ND_ST_CALLED) != 0;
match bn.body.as_mut() {
Some(body) => tune_next_inner(body, next_node, reg, called),
None => 0,
}
}
_ => 0,
}
}
// ============================================================================
// String compilation
// ============================================================================
/// Select the opcode for a string of given byte length and encoding char width.
fn select_str_opcode(mb_len: i32, str_len: i32) -> OpCode {
if mb_len == 1 {
match str_len {
1 => OpCode::Str1,
2 => OpCode::Str2,
3 => OpCode::Str3,
4 => OpCode::Str4,
5 => OpCode::Str5,
_ => OpCode::StrN,
}
} else if mb_len == 2 {
match str_len {
1 => OpCode::StrMb2n1,
2 => OpCode::StrMb2n2,
3 => OpCode::StrMb2n3,
_ => OpCode::StrMb2n,
}
} else if mb_len == 3 {
OpCode::StrMb3n
} else {
OpCode::StrMbn
}
}
/// Calculate bytecode length for adding a compiled string segment.
fn add_compile_string_length(_s: &[u8], mb_len: i32, str_len: i32) -> i32 {
SIZE_INC
}
/// Add a compiled string segment to the bytecode.
fn add_compile_string(reg: &mut RegexType, s: &[u8], mb_len: i32, str_len: i32) -> i32 {
let op = select_str_opcode(mb_len, str_len);
let byte_len = mb_len * str_len;
let payload = if mb_len == 1 && str_len <= 5 {
// Single-byte encoding, Str1-Str5: use compact Exact payload
let mut buf = [0u8; 16];
buf[..byte_len as usize].copy_from_slice(&s[..byte_len as usize]);
OperationPayload::Exact { s: buf }
} else if mb_len == 1 {
// Single-byte encoding, StrN: use ExactN payload
OperationPayload::ExactN {
s: s[..byte_len as usize].to_vec(),
n: str_len,
}
} else {
// Multi-byte encoding: always use ExactLenN with byte count
OperationPayload::ExactLenN {
s: s[..byte_len as usize].to_vec(),
n: byte_len, // total byte count
len: mb_len, // bytes per character
}
};
add_op(reg, op, payload);
0
}
/// Calculate bytecode length for a string node.
fn compile_length_string_node(node: &Node, reg: &RegexType) -> i32 {
let sn = node.as_str().unwrap();
let enc = reg.enc;
if sn.s.is_empty() {
return 0;
}
let mut len = 0i32;
let mut pos = 0usize;
let slen = sn.s.len();
while pos < slen {
let first_len = enc.mbc_enc_len(&sn.s[pos..]);
let mut run = 1;
let next = pos + first_len;
let mut p = next;
// Group consecutive characters with the same mb_len
while p < slen {
let enc_len = enc.mbc_enc_len(&sn.s[p..]);
if enc_len != first_len {
break;
}
run += 1;
p += enc_len;
}
len += add_compile_string_length(&sn.s[pos..], first_len as i32, run);
pos = p;
}
len
}
/// Calculate bytecode length for a "crude" string node.
fn compile_length_string_crude_node(node: &Node, reg: &RegexType) -> i32 {
let sn = node.as_str().unwrap();
if sn.s.is_empty() {
return 0;
}
SIZE_INC
}
/// Compile a string node to bytecode.
fn compile_string_node(node: &Node, reg: &mut RegexType) -> i32 {
let sn = node.as_str().unwrap();
let enc = reg.enc;
if sn.s.is_empty() {
return 0;
}
let mut pos = 0usize;
let slen = sn.s.len();
while pos < slen {
let first_len = enc.mbc_enc_len(&sn.s[pos..]);
let mut run = 1;
let next = pos + first_len;
let mut p = next;
while p < slen {
let enc_len = enc.mbc_enc_len(&sn.s[p..]);
if enc_len != first_len {
break;
}
run += 1;
p += enc_len;
}
let r = add_compile_string(reg, &sn.s[pos..], first_len as i32, run);
if r != 0 {
return r;
}
pos = p;
}
0
}
/// Compile a crude string node to bytecode.
fn compile_string_crude_node(node: &Node, reg: &mut RegexType) -> i32 {
let sn = node.as_str().unwrap();
if sn.s.is_empty() {
return 0;
}
let byte_len = sn.s.len();
let payload = if byte_len <= 16 {
let mut buf = [0u8; 16];
buf[..byte_len].copy_from_slice(&sn.s[..byte_len]);
OperationPayload::Exact { s: buf }
} else {
OperationPayload::ExactN {
s: sn.s.clone(),
n: byte_len as i32,
}
};
add_op(reg, select_str_opcode(1, byte_len as i32), payload);
0
}
// ============================================================================
// Character class compilation
// ============================================================================
/// Calculate bytecode length for a character class node.
fn compile_length_cclass_node(cc: &CClassNode, reg: &RegexType) -> i32 {
SIZE_INC
}
/// Convert a BBuf byte buffer to a Vec<u32> for direct indexing at execution time.
/// BBuf stores code ranges as packed u32 values in native-endian bytes.
fn bbuf_to_u32_vec(data: &[u8]) -> Vec<u32> {
data.chunks_exact(4)
.map(|chunk| u32::from_ne_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]))
.collect()
}
fn detect_cclass_ascii_fast(bs: &BitSet) -> CClassAsciiFastKind {
let mut first: Option<u8> = None;
let mut second: Option<u8> = None;
for i in 0..SINGLE_BYTE_SIZE {
if bitset_at(bs, i) {
let b = i as u8;
if first.is_none() {
first = Some(b);
} else if second.is_none() {
second = Some(b);
} else {
return CClassAsciiFastKind::None;
}
}
}
match (first, second) {
(Some(a), None) if a < 0x80 => CClassAsciiFastKind::Eq(a),
(Some(a), Some(b))
if a < 0x80
&& b < 0x80
&& a.is_ascii_alphabetic()
&& b.is_ascii_alphabetic()
&& (a ^ b) == 0x20 =>
{
CClassAsciiFastKind::EqFoldLower(a | 0x20)
}
_ => CClassAsciiFastKind::None,
}
}
/// Compile a character class node to bytecode.
fn compile_cclass_node(cc: &CClassNode, reg: &mut RegexType) -> i32 {
let has_mb = cc.mbuf.is_some();
let has_sb = !bitset_is_empty(&cc.bs);
if has_mb && has_sb {
// Mixed single-byte and multi-byte
let opcode = if cc.is_not() {
OpCode::CClassMixNot
} else {
OpCode::CClassMix
};
let mb_data = cc
.mbuf
.as_ref()
.map(|b| bbuf_to_u32_vec(&b.data))
.unwrap_or_default();
add_op(
reg,
opcode,
OperationPayload::CClassMix {
mb: mb_data,
bsp: Box::new(cc.bs),
},
);
} else if has_mb {
// Multi-byte only
let opcode = if cc.is_not() {
OpCode::CClassMbNot
} else {
OpCode::CClassMb
};
let mb_data = cc
.mbuf
.as_ref()
.map(|b| bbuf_to_u32_vec(&b.data))
.unwrap_or_default();
add_op(reg, opcode, OperationPayload::CClassMb { mb: mb_data });
} else {
// Single-byte only
let opcode = if cc.is_not() {
OpCode::CClassNot
} else {
OpCode::CClass
};
let ascii_fast = detect_cclass_ascii_fast(&cc.bs);
add_op(
reg,
opcode,
OperationPayload::CClass {
bsp: Box::new(cc.bs),
ascii_fast,
},
);
}
0
}
// ============================================================================
// Repeat range management
// ============================================================================
/// Register a repeat range entry. Returns the repeat ID.
fn entry_repeat_range(reg: &mut RegexType, lower: i32, upper: i32) -> Result<i32, i32> {
let id = reg.num_repeat;
reg.num_repeat += 1;
reg.repeat_range.push(RepeatRange {
lower,
upper,
u_offset: 0,
});
Ok(id)
}
// ============================================================================
// Quantifier compilation
// ============================================================================
/// Compile a quantifier body wrapped with empty-match check if needed.
/// Collect a bitmask of capture group regnums present in a node tree.
fn collect_mem_status(node: &Node) -> u32 {
let mut status: u32 = 0;
match &node.inner {
NodeInner::List(_) | NodeInner::Alt(_) => {
let mut cur = node;
loop {
let (car, cdr) = match &cur.inner {
NodeInner::List(cons) => (&cons.car, &cons.cdr),
NodeInner::Alt(cons) => (&cons.car, &cons.cdr),
_ => break,
};
status |= collect_mem_status(car);
match cdr {
Some(next) => cur = next,
None => break,
}
}
}
NodeInner::Quant(qn) => {
if let Some(ref body) = qn.body {
status |= collect_mem_status(body);
}
}
NodeInner::Bag(bn) => {
if bn.bag_type == BagType::Memory {
if let BagData::Memory { regnum, .. } = bn.bag_data {
if regnum > 0 && regnum < 31 {
status |= 1u32 << regnum;
}
}
}
if let Some(ref body) = bn.body {
status |= collect_mem_status(body);
}
}
_ => {}
}
status
}
fn compile_quant_body_with_empty_check(
node: &Node,
reg: &mut RegexType,
env: &ParseEnv,
emptiness: BodyEmptyType,
qn_empty_status_mem: u32,
) -> i32 {
let is_empty = emptiness != BodyEmptyType::NotEmpty;
let saved_mem = reg.num_empty_check;
if is_empty {
reg.num_empty_check += 1;
add_op(
reg,
OpCode::EmptyCheckStart,
OperationPayload::EmptyCheckStart { mem: saved_mem },
);
}
let r = compile_tree(node, reg, env);
if r != 0 {
return r;
}
if is_empty {
let mem = saved_mem;
let empty_status_mem = if emptiness == BodyEmptyType::MayBeEmptyMem
|| emptiness == BodyEmptyType::MayBeEmptyRec
{
if qn_empty_status_mem != 0 {
qn_empty_status_mem
} else {
collect_mem_status(node)
}
} else {
0
};
let opcode = match emptiness {
BodyEmptyType::MayBeEmptyMem => {
if qn_empty_status_mem != 0 {
OpCode::EmptyCheckEndMemst
} else {
// No external backrefs to tracked captures → use plain empty check
OpCode::EmptyCheckEnd
}
}
BodyEmptyType::MayBeEmptyRec => OpCode::EmptyCheckEndMemstPush,
_ => OpCode::EmptyCheckEnd,
};
add_op(
reg,
opcode,
OperationPayload::EmptyCheckEnd {
mem,
empty_status_mem,
},
);
}
0
}
/// Compile a node N times (for expanding small-count quantifiers).
fn compile_tree_n_times(node: &Node, n: i32, reg: &mut RegexType, env: &ParseEnv) -> i32 {
for _ in 0..n {
let r = compile_tree(node, reg, env);
if r != 0 {
return r;
}
}
0
}
/// Check if this is a greedy infinite repeat of a character class [class]* / [class]+
fn is_cclass_infinite_greedy(qn: &QuantNode) -> bool {
qn.greedy
&& is_infinite_repeat(qn.upper)
&& qn.lower <= 1
&& qn
.body
.as_ref()
.is_some_and(|b| matches!(b.inner, NodeInner::CClass(_)))
}
/// Check if this is a greedy infinite repeat of \w or \W.
/// Returns Some((not, ascii_mode)) if match.
fn is_word_ctype_infinite_greedy(qn: &QuantNode) -> Option<(bool, bool)> {
if qn.greedy && is_infinite_repeat(qn.upper) && qn.lower <= 1 {
if let Some(body) = &qn.body {
if let NodeInner::CType(ct) = &body.inner {
if ct.ctype == ONIGENC_CTYPE_WORD as i32 {
return Some((ct.not, ct.ascii_mode));
}
}
}
}
None
}
/// Check if this is a greedy infinite repeat of `(?:CClass|...)`
/// where the first alternative is a non-negated character class.
/// Returns the CClass and the remaining alternatives (cdr) if matched.
fn is_alt_cclass_first_infinite_greedy(qn: &QuantNode) -> Option<(&CClassNode, &Node)> {
if !qn.greedy || !is_infinite_repeat(qn.upper) || qn.lower > 1 {
return None;
}
if qn.emptiness != BodyEmptyType::NotEmpty {
return None;
}
let body = qn.body.as_ref()?;
if let NodeInner::Alt(cons) = &body.inner {
if let NodeInner::CClass(cc) = &cons.car.inner {
if !cc.is_not() {
if let Some(cdr) = &cons.cdr {
return Some((cc, cdr));
}
}
}
}
None
}
/// Compile a character class star node (CClassStar/CClassMixStar/CClassMbStar).
/// Returns 0 on success, -1 if the class is negated (caller should fall through).
fn compile_cclass_star_node(cc: &CClassNode, reg: &mut RegexType) -> i32 {
if cc.is_not() {
return -1;
}
let has_mb = cc.mbuf.is_some();
let has_sb = !bitset_is_empty(&cc.bs);
if has_mb && has_sb {
let mb_data = cc
.mbuf
.as_ref()
.map(|b| bbuf_to_u32_vec(&b.data))
.unwrap_or_default();
add_op(
reg,
OpCode::CClassMixStar,
OperationPayload::CClassMix {
mb: mb_data,
bsp: Box::new(cc.bs),
},
);
} else if has_mb {
let mb_data = cc
.mbuf
.as_ref()
.map(|b| bbuf_to_u32_vec(&b.data))
.unwrap_or_default();
add_op(
reg,
OpCode::CClassMbStar,
OperationPayload::CClassMb { mb: mb_data },
);
} else {
let ascii_fast = detect_cclass_ascii_fast(&cc.bs);
add_op(
reg,
OpCode::CClassStar,
OperationPayload::CClass {
bsp: Box::new(cc.bs),
ascii_fast,
},
);
}
0
}
/// Check if a quantifier node represents .* or .+ (anychar infinite greedy).
///
/// Keep backref-bearing patterns on the generic quantifier path. The specialized
/// ANYCHAR_STAR opcodes precompute all exit points up front, which is unsafe for
/// backref-heavy patterns like `(.*)a\\1f` that rely on conservative backtracking.
fn is_anychar_infinite_greedy(qn: &QuantNode, env: &ParseEnv) -> bool {
if env.backref_num == 0 && qn.greedy && is_infinite_repeat(qn.upper) && qn.lower <= 1 {
if let Some(body) = &qn.body {
return matches!(body.inner, NodeInner::CType(ref ct) if ct.ctype == CTYPE_ANYCHAR);
}
}
false
}
/// Check if the body of a CType node has MULTILINE flag set.
fn is_anychar_multiline(body: &Node) -> bool {
matches!(&body.inner, NodeInner::CType(_) if (body.status & ND_ST_MULTILINE) != 0)
}
/// Calculate bytecode length for a quantifier node.
fn compile_length_quantifier_node(qn: &QuantNode, reg: &RegexType, env: &ParseEnv) -> i32 {
let body = qn.body.as_ref().unwrap();
if qn.upper == 0 {
if qn.include_referred != 0 {
// {0} with CALLED group: JUMP + body
let tlen = compile_length_tree(body, reg, env);
return OPSIZE_JUMP + tlen;
}
// {0} matches nothing
if is_anychar_infinite_greedy(qn, env) {
return SIZE_INC;
}
return 0;
}
// AnyChar star/plus optimization
if is_anychar_infinite_greedy(qn, env) {
let tlen = compile_length_tree(body, reg, env);
if qn.next_head_exact.is_some() {
return OPSIZE_ANYCHAR_STAR_PEEK_NEXT + tlen * qn.lower;
}
return SIZE_INC + tlen * qn.lower;
}
// CClass star/plus optimization: [class]* or [class]+
if is_cclass_infinite_greedy(qn) {
if let Some(cc) = body.as_cclass() {
if !cc.is_not() {
let tlen = compile_length_tree(body, reg, env);
return SIZE_INC + tlen * qn.lower;
}
}
}
// Word ctype star/plus optimization: \w* or \w+
if let Some((not, _ascii_mode)) = is_word_ctype_infinite_greedy(qn) {
if !not {
let tlen = compile_length_tree(body, reg, env);
return SIZE_INC + tlen * qn.lower;
}
}
// Alt-CClass fusion: (?:CClass|B)* or (?:CClass|B)+
if let Some((_cc, cdr)) = is_alt_cclass_first_infinite_greedy(qn) {
let cdr_len = compile_length_tree(cdr, reg, env);
let body_len = compile_length_tree(body, reg, env);
// Layout: [body × lower] + CClassStar(1) + PUSH(1) + cdr + JUMP(1)
return body_len * qn.lower + SIZE_INC + OPSIZE_PUSH + cdr_len + OPSIZE_JUMP;
}
let is_empty = qn.emptiness != BodyEmptyType::NotEmpty;
let body_len = compile_length_tree(body, reg, env);
if body_len < 0 {
return body_len;
}
let empty_len = if is_empty {
OPSIZE_EMPTY_CHECK_START + OPSIZE_EMPTY_CHECK_END
} else {
0
};
let mod_tlen = body_len + empty_len;
if is_infinite_repeat(qn.upper) {
if qn.lower <= 1 {
// *, +, *?, +?
// Use appropriate opsize based on head_exact/next_head_exact
let push_size = if qn.greedy && qn.head_exact.is_some() {
OPSIZE_PUSH_OR_JUMP_EXACT1
} else if qn.greedy && qn.next_head_exact.is_some() {
OPSIZE_PUSH_IF_PEEK_NEXT
} else {
OPSIZE_PUSH
};
body_len * qn.lower + push_size + mod_tlen + OPSIZE_JUMP
} else {
// {n,} or {n,}?
let n_body_len = compile_length_tree_n_times(body, qn.lower, reg, env);
n_body_len + OPSIZE_PUSH + mod_tlen + OPSIZE_JUMP
}
} else if qn.upper == 0 {
0
} else if !is_infinite_repeat(qn.upper) && qn.lower == qn.upper {
// {n,n} exact repeat
if qn.lower == 1 {
body_len
} else if !is_empty && qn.include_referred == 0 && qn.lower <= EXACT_REPEAT_UNROLL_THRESHOLD
{
// Unroll small exact repeats into flat bytecode
body_len * qn.lower
} else {
// Use REPEAT opcodes for larger exact counts
OPSIZE_REPEAT + mod_tlen + OPSIZE_REPEAT_INC
}
} else if !qn.greedy && qn.upper == 1 && qn.lower == 0 {
// ?? path: PUSH + JUMP + body
OPSIZE_PUSH + OPSIZE_JUMP + body_len
} else if qn.greedy
&& !is_infinite_repeat(qn.upper)
// The REPEAT VM path has not yet reached parity for recursive calls.
// Preserve the established expansion behavior for those expressions.
&& (quantifier_body_contains_recursion(body)
|| can_expand_finite_greedy_quantifier(body_len, qn.upper))
{
// Greedy expansion: lower*body + (upper-lower)*(PUSH+body)
let n = qn.upper - qn.lower;
let iteration_len = match body_len.checked_add(OPSIZE_PUSH) {
Some(len) => len,
None => return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE,
};
let mandatory_len = match body_len.checked_mul(qn.lower) {
Some(len) => len,
None => return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE,
};
let optional_len = match iteration_len.checked_mul(n) {
Some(len) => len,
None => return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE,
};
match mandatory_len.checked_add(optional_len) {
Some(len) => len,
None => ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE,
}
} else {
// {n,m} range repeat (lazy non-trivial)
OPSIZE_REPEAT + mod_tlen + OPSIZE_REPEAT_INC
}
}
/// Calculate compile length for N repetitions of a node.
fn compile_length_tree_n_times(node: &Node, n: i32, reg: &RegexType, env: &ParseEnv) -> i32 {
let len = compile_length_tree(node, reg, env);
if len < 0 {
return len;
}
len * n
}
/// Compile a quantifier node to bytecode.
fn compile_quantifier_node(qn: &QuantNode, reg: &mut RegexType, env: &ParseEnv) -> i32 {
let body = qn.body.as_ref().unwrap();
if qn.upper == 0 {
if qn.include_referred != 0 {
// {0} with CALLED group: JUMP over body, then compile body
let tlen = compile_length_tree(body, reg, env);
add_op(
reg,
OpCode::Jump,
OperationPayload::Jump {
addr: tlen + SIZE_INC,
},
);
return compile_tree(body, reg, env);
}
return 0;
}
// AnyChar star/plus with peek optimization: .* or .+
if is_anychar_infinite_greedy(qn, env) {
let r = compile_tree_n_times(body, qn.lower, reg, env);
if r != 0 {
return r;
}
if let Some(c) = qn.next_head_exact {
let opcode = if is_anychar_multiline(body) {
OpCode::AnyCharMlStarPeekNext
} else {
OpCode::AnyCharStarPeekNext
};
add_op(reg, opcode, OperationPayload::AnyCharStarPeekNext { c });
} else {
let opcode = if is_anychar_multiline(body) {
OpCode::AnyCharMlStar
} else {
OpCode::AnyCharStar
};
add_op(reg, opcode, OperationPayload::None);
}
return 0;
}
// CClass star/plus optimization: [class]* or [class]+
if is_cclass_infinite_greedy(qn) {
if let Some(cc) = body.as_cclass() {
if !cc.is_not() {
let r = compile_tree_n_times(body, qn.lower, reg, env);
if r != 0 {
return r;
}
// Use PeekNext variant for ASCII-only classes when next byte is known
if let Some(c) = qn.next_head_exact {
let has_mb = cc.mbuf.is_some();
if !has_mb {
// ASCII-only bitset: use CClassStarPeekNext
add_op(
reg,
OpCode::CClassStarPeekNext,
OperationPayload::CClassStarPeekNext {
bsp: Box::new(cc.bs),
c,
},
);
return 0;
}
}
compile_cclass_star_node(cc, reg);
return 0;
}
}
}
// Word ctype star/plus optimization: \w* or \w+
if let Some((not, ascii_mode)) = is_word_ctype_infinite_greedy(qn) {
if !not {
let r = compile_tree_n_times(body, qn.lower, reg, env);
if r != 0 {
return r;
}
if ascii_mode {
if let Some(c) = qn.next_head_exact {
add_op(
reg,
OpCode::WordAsciiStarPeekNext,
OperationPayload::WordAsciiStarPeekNext { c },
);
return 0;
}
}
let opcode = if ascii_mode {
OpCode::WordAsciiStar
} else {
OpCode::WordStar
};
add_op(reg, opcode, OperationPayload::None);
return 0;
}
}
// Alt-CClass fusion: (?:CClass|B)* → CClassStar + PUSH exit + [B] + JUMP loop
if let Some((cc, cdr)) = is_alt_cclass_first_infinite_greedy(qn) {
// For +: compile one mandatory match of the full alternation first
if qn.lower == 1 {
let r = compile_tree(body, reg, env);
if r != 0 {
return r;
}
}
// Emit CClassStar for the first branch's character class
compile_cclass_star_node(cc, reg);
// PUSH exit: skip over cdr + JUMP to exit the loop
let cdr_len = compile_length_tree(cdr, reg, env);
let push_addr = SIZE_INC + cdr_len + OPSIZE_JUMP;
add_op(
reg,
OpCode::Push,
OperationPayload::Push { addr: push_addr },
);
// Compile remaining alternation branches (B, or B|C|...)
let r = compile_tree(cdr, reg, env);
if r != 0 {
return r;
}
// JUMP back to CClassStar
let jump_addr = -(SIZE_INC + OPSIZE_PUSH + cdr_len);
add_op(
reg,
OpCode::Jump,
OperationPayload::Jump { addr: jump_addr },
);
return 0;
}
let is_empty = qn.emptiness != BodyEmptyType::NotEmpty;
let body_len = compile_length_tree(body, reg, env);
if body_len < 0 {
return body_len;
}
let empty_len = if is_empty {
OPSIZE_EMPTY_CHECK_START + OPSIZE_EMPTY_CHECK_END
} else {
0
};
let mod_tlen = body_len + empty_len;
if is_infinite_repeat(qn.upper) {
if qn.lower <= 1 {
if qn.greedy {
// a* or a+
if qn.lower == 1 {
// a+ : body first, then loop
compile_tree_n_times(body, 1, reg, env);
}
// Emit PUSH variant based on head_exact / next_head_exact
let addr;
if let Some(c) = qn.head_exact {
// PushOrJumpExact1: push alt if char matches, else jump
add_op(
reg,
OpCode::PushOrJumpExact1,
OperationPayload::PushOrJumpExact1 {
addr: SIZE_INC + mod_tlen + OPSIZE_JUMP,
c,
},
);
let r = compile_quant_body_with_empty_check(
body,
reg,
env,
qn.emptiness,
qn.empty_status_mem,
);
if r != 0 {
return r;
}
addr = -(mod_tlen + OPSIZE_PUSH_OR_JUMP_EXACT1);
} else if let Some(c) = qn.next_head_exact {
// PushIfPeekNext: push alt only if next char matches peek
add_op(
reg,
OpCode::PushIfPeekNext,
OperationPayload::PushIfPeekNext {
addr: SIZE_INC + mod_tlen + OPSIZE_JUMP,
c,
},
);
let r = compile_quant_body_with_empty_check(
body,
reg,
env,
qn.emptiness,
qn.empty_status_mem,
);
if r != 0 {
return r;
}
addr = -(mod_tlen + OPSIZE_PUSH_IF_PEEK_NEXT);
} else {
// Regular PUSH
add_op(
reg,
OpCode::Push,
OperationPayload::Push {
addr: SIZE_INC + mod_tlen + OPSIZE_JUMP,
},
);
let r = compile_quant_body_with_empty_check(
body,
reg,
env,
qn.emptiness,
qn.empty_status_mem,
);
if r != 0 {
return r;
}
addr = -(mod_tlen + OPSIZE_PUSH);
}
add_op(reg, OpCode::Jump, OperationPayload::Jump { addr });
} else {
// a*? or a+?
if qn.lower == 1 {
compile_tree_n_times(body, 1, reg, env);
}
// JUMP forward → body → PUSH back
// C: COP(reg)->jump.addr = mod_tlen + SIZE_INC;
add_op(
reg,
OpCode::Jump,
OperationPayload::Jump {
addr: mod_tlen + SIZE_INC,
},
);
let r = compile_quant_body_with_empty_check(
body,
reg,
env,
qn.emptiness,
qn.empty_status_mem,
);
if r != 0 {
return r;
}
// C: COP(reg)->push.addr = -mod_tlen;
add_op(
reg,
OpCode::Push,
OperationPayload::Push { addr: -mod_tlen },
);
}
} else {
// {n,} with n >= 2
// Compile body n times, then loop
let r = compile_tree_n_times(body, qn.lower, reg, env);
if r != 0 {
return r;
}
if qn.greedy {
add_op(
reg,
OpCode::Push,
OperationPayload::Push {
addr: SIZE_INC + mod_tlen + OPSIZE_JUMP,
},
);
let r = compile_quant_body_with_empty_check(
body,
reg,
env,
qn.emptiness,
qn.empty_status_mem,
);
if r != 0 {
return r;
}
// C: addr = -(mod_tlen + (int)OPSIZE_PUSH);
add_op(
reg,
OpCode::Jump,
OperationPayload::Jump {
addr: -(mod_tlen + OPSIZE_PUSH),
},
);
} else {
// C: COP(reg)->jump.addr = mod_tlen + SIZE_INC;
add_op(
reg,
OpCode::Jump,
OperationPayload::Jump {
addr: mod_tlen + SIZE_INC,
},
);
let r = compile_quant_body_with_empty_check(
body,
reg,
env,
qn.emptiness,
qn.empty_status_mem,
);
if r != 0 {
return r;
}
// C: COP(reg)->push.addr = -mod_tlen;
add_op(
reg,
OpCode::Push,
OperationPayload::Push { addr: -mod_tlen },
);
}
}
} else if qn.lower == qn.upper {
// {n} exact repeat
if qn.lower == 1 {
return compile_tree(body, reg, env);
}
// Unroll small exact repeats into flat bytecode (no REPEAT/REPEAT_INC overhead)
if !is_empty && qn.include_referred == 0 && qn.lower <= EXACT_REPEAT_UNROLL_THRESHOLD {
return compile_tree_n_times(body, qn.lower, reg, env);
}
// Use REPEAT opcode for large or empty-body repeats
let id = entry_repeat_range(reg, qn.lower, qn.upper);
if let Err(e) = id {
return e;
}
let id = id.unwrap();
add_op(
reg,
OpCode::Repeat,
OperationPayload::Repeat {
id,
addr: SIZE_INC + mod_tlen + OPSIZE_REPEAT_INC,
},
);
// Patch u_offset to point to the body start (op after REPEAT)
reg.repeat_range[id as usize].u_offset = reg.ops.len() as i32;
let r =
compile_quant_body_with_empty_check(body, reg, env, qn.emptiness, qn.empty_status_mem);
if r != 0 {
return r;
}
add_op(
reg,
if qn.greedy {
OpCode::RepeatInc
} else {
OpCode::RepeatIncNg
},
OperationPayload::RepeatInc { id },
);
} else if !qn.greedy && qn.upper == 1 && qn.lower == 0 {
// ?? path: PUSH(skip JUMP + SIZE_INC) + JUMP(skip body + SIZE_INC) + body
// C: COP(reg)->push.addr = SIZE_INC + OPSIZE_JUMP;
add_op(
reg,
OpCode::Push,
OperationPayload::Push {
addr: SIZE_INC + OPSIZE_JUMP,
},
);
// C: COP(reg)->jump.addr = body_len + SIZE_INC;
add_op(
reg,
OpCode::Jump,
OperationPayload::Jump {
addr: body_len + SIZE_INC,
},
);
let r = compile_tree(body, reg, env);
if r != 0 {
return r;
}
} else if qn.greedy
&& !is_infinite_repeat(qn.upper)
// Keep this in sync with compile_length_quantifier_node above.
&& (quantifier_body_contains_recursion(body)
|| can_expand_finite_greedy_quantifier(body_len, qn.upper))
{
// Greedy expansion: body*lower + (upper-lower) * (PUSH + body)
let r = compile_tree_n_times(body, qn.lower, reg, env);
if r != 0 {
return r;
}
let n = qn.upper - qn.lower;
let iteration_len = match body_len.checked_add(OPSIZE_PUSH) {
Some(len) => len,
None => return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE,
};
for i in 0..n {
let push_addr = match (n - i).checked_mul(iteration_len) {
Some(addr) => addr,
None => return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE,
};
add_op(
reg,
OpCode::Push,
OperationPayload::Push { addr: push_addr },
);
let r = compile_tree(body, reg, env);
if r != 0 {
return r;
}
}
} else {
// {n,m} range repeat (lazy non-trivial)
let id = entry_repeat_range(reg, qn.lower, qn.upper);
if let Err(e) = id {
return e;
}
let id = id.unwrap();
let opcode = if qn.greedy {
OpCode::Repeat
} else {
OpCode::RepeatNg
};
add_op(
reg,
opcode,
OperationPayload::Repeat {
id,
addr: SIZE_INC + mod_tlen + OPSIZE_REPEAT_INC,
},
);
// Patch u_offset to point to the body start (op after REPEAT)
reg.repeat_range[id as usize].u_offset = reg.ops.len() as i32;
let r =
compile_quant_body_with_empty_check(body, reg, env, qn.emptiness, qn.empty_status_mem);
if r != 0 {
return r;
}
add_op(
reg,
if qn.greedy {
OpCode::RepeatInc
} else {
OpCode::RepeatIncNg
},
OperationPayload::RepeatInc { id },
);
}
0
}
// ============================================================================
// Bag (group) compilation
// ============================================================================
/// Calculate bytecode length for a bag node.
fn compile_length_bag_node(
bag: &BagNode,
node_status: u32,
reg: &RegexType,
env: &ParseEnv,
) -> i32 {
let body = bag.body.as_ref();
match bag.bag_type {
BagType::Memory => {
let body_len = if let Some(b) = body {
compile_length_tree(b, reg, env)
} else {
0
};
if body_len < 0 {
return body_len;
}
let regnum = match &bag.bag_data {
BagData::Memory { regnum, .. } => *regnum,
_ => 0,
};
if regnum == 0 && (node_status & ND_ST_CALLED) != 0 {
// \g<0> wrapper: CALL + JUMP + body + RETURN (no MEM_START/END)
return OPSIZE_CALL + OPSIZE_JUMP + body_len + OPSIZE_RETURN;
}
let mut len = OPSIZE_MEM_START + body_len + OPSIZE_MEM_END;
if (node_status & ND_ST_CALLED) != 0 {
// Called group: CALL + JUMP + (MEM_START + body + MEM_END + RETURN)
len += OPSIZE_CALL + OPSIZE_JUMP + OPSIZE_RETURN;
}
len
}
BagType::StopBacktrack => {
let body_len = if let Some(b) = body {
compile_length_tree(b, reg, env)
} else {
0
};
if body_len < 0 {
return body_len;
}
// MARK + body + CUT_TO_MARK
OPSIZE_MARK + body_len + OPSIZE_CUT_TO_MARK
}
BagType::Option => {
let body_len = if let Some(b) = body {
compile_length_tree(b, reg, env)
} else {
0
};
if body_len < 0 {
return body_len;
}
body_len
}
BagType::IfElse => {
// Conditional: MARK + PUSH + condition + CUT_TO_MARK + then + JUMP + CUT_TO_MARK + else
let cond_len = if let Some(b) = body {
compile_length_tree(b, reg, env)
} else {
0
};
if cond_len < 0 {
return cond_len;
}
let mut len = OPSIZE_PUSH + OPSIZE_MARK + cond_len + OPSIZE_CUT_TO_MARK;
if let BagData::IfElse {
ref then_node,
ref else_node,
} = bag.bag_data
{
if let Some(ref then_n) = then_node {
let tlen = compile_length_tree(then_n, reg, env);
if tlen < 0 {
return tlen;
}
len += tlen;
}
len += OPSIZE_JUMP + OPSIZE_CUT_TO_MARK;
if let Some(ref else_n) = else_node {
let elen = compile_length_tree(else_n, reg, env);
if elen < 0 {
return elen;
}
len += elen;
}
}
len
}
}
}
/// Compile a bag memory (capture group) node.
fn compile_bag_memory_node(
bag: &BagNode,
node_status: u32,
reg: &mut RegexType,
env: &ParseEnv,
) -> i32 {
let regnum = match &bag.bag_data {
BagData::Memory { regnum, .. } => *regnum,
_ => return ONIGERR_TYPE_BUG,
};
let is_called = (node_status & ND_ST_CALLED) != 0;
if is_called {
// Called group: emit CALL + JUMP wrapper
let body_len = if let Some(body) = &bag.body {
compile_length_tree(body, reg, env)
} else {
0
};
if body_len < 0 {
return body_len;
}
if regnum == 0 {
// \g<0> wrapper: simpler layout without MEM_START/END
// Layout: CALL(entry) + JUMP(skip) + [entry: body + RETURN]
let callable_len = body_len + OPSIZE_RETURN;
let call_idx = reg.ops.len();
let entry_addr = (call_idx + 2) as i32;
add_op(
reg,
OpCode::Call,
OperationPayload::Call { addr: entry_addr },
);
add_op(
reg,
OpCode::Jump,
OperationPayload::Jump {
addr: callable_len + SIZE_INC,
},
);
let called_addr = reg.ops.len() as i32;
if reg.called_addrs.is_empty() {
reg.called_addrs.resize(1, -1);
}
reg.called_addrs[0] = called_addr;
if let Some(body) = &bag.body {
let r = compile_tree(body, reg, env);
if r != 0 {
return r;
}
}
add_op(reg, OpCode::Return, OperationPayload::Return);
return 0;
}
// Regular called group: CALL + JUMP + MEM_START + body + MEM_END + RETURN
let callable_len = OPSIZE_MEM_START + body_len + OPSIZE_MEM_END + OPSIZE_RETURN;
let call_idx = reg.ops.len();
let entry_addr = (call_idx + 2) as i32;
add_op(
reg,
OpCode::Call,
OperationPayload::Call { addr: entry_addr },
);
add_op(
reg,
OpCode::Jump,
OperationPayload::Jump {
addr: callable_len + SIZE_INC,
},
);
let called_addr = reg.ops.len() as i32;
if reg.called_addrs.len() <= regnum as usize {
reg.called_addrs.resize(regnum as usize + 1, -1);
}
reg.called_addrs[regnum as usize] = called_addr;
}
// Determine if we need push variants
let need_push = mem_status_at(reg.push_mem_start, regnum as usize);
if need_push {
add_op(
reg,
OpCode::MemStartPush,
OperationPayload::MemoryStart { num: regnum },
);
} else {
add_op(
reg,
OpCode::MemStart,
OperationPayload::MemoryStart { num: regnum },
);
}
if let Some(body) = &bag.body {
let r = compile_tree(body, reg, env);
if r != 0 {
return r;
}
}
let need_push_end = mem_status_at(reg.push_mem_end, regnum as usize);
let is_recursion = (node_status & ND_ST_RECURSION) != 0;
if need_push_end {
let opcode = if is_recursion {
OpCode::MemEndPushRec
} else {
OpCode::MemEndPush
};
add_op(reg, opcode, OperationPayload::MemoryEnd { num: regnum });
} else {
let opcode = if is_recursion {
OpCode::MemEndRec
} else {
OpCode::MemEnd
};
add_op(reg, opcode, OperationPayload::MemoryEnd { num: regnum });
}
if is_called {
add_op(reg, OpCode::Return, OperationPayload::Return);
}
0
}
/// Compile a bag node to bytecode.
fn compile_bag_node(bag: &BagNode, node_status: u32, reg: &mut RegexType, env: &ParseEnv) -> i32 {
match bag.bag_type {
BagType::Memory => compile_bag_memory_node(bag, node_status, reg, env),
BagType::StopBacktrack => {
let id = reg.num_call; // use call count as mark ID
reg.num_call += 1;
add_op(
reg,
OpCode::Mark,
OperationPayload::Mark { id, save_pos: true },
);
if let Some(body) = &bag.body {
let r = compile_tree(body, reg, env);
if r != 0 {
return r;
}
}
add_op(
reg,
OpCode::CutToMark,
OperationPayload::CutToMark {
id,
restore_pos: false,
},
);
0
}
BagType::Option => {
// Option change: just compile the body with the option set.
// The option was already applied to the parse env during parsing.
if let Some(body) = &bag.body {
return compile_tree(body, reg, env);
}
0
}
BagType::IfElse => {
let id = reg.num_call;
reg.num_call += 1;
// Emit MARK
add_op(
reg,
OpCode::Mark,
OperationPayload::Mark {
id,
save_pos: false,
},
);
// Calculate condition and then lengths for PUSH address
let cond_len = if let Some(body) = &bag.body {
compile_length_tree(body, reg, env)
} else {
0
};
if cond_len < 0 {
return cond_len;
}
let then_len = if let BagData::IfElse { ref then_node, .. } = bag.bag_data {
then_node
.as_ref()
.map_or(0, |then_n| compile_length_tree(then_n, reg, env))
} else {
0
};
if then_len < 0 {
return then_len;
}
let jump_len = cond_len + OPSIZE_CUT_TO_MARK + then_len + OPSIZE_JUMP;
// Emit PUSH to else section
add_op(
reg,
OpCode::Push,
OperationPayload::Push {
addr: SIZE_INC + jump_len,
},
);
// Emit condition
if let Some(body) = &bag.body {
let r = compile_tree(body, reg, env);
if r != 0 {
return r;
}
}
// On condition success, cut mark
add_op(
reg,
OpCode::CutToMark,
OperationPayload::CutToMark {
id,
restore_pos: false,
},
);
// Emit then branch
if let BagData::IfElse {
ref then_node,
ref else_node,
} = bag.bag_data
{
if let Some(ref then_n) = then_node {
let r = compile_tree(then_n, reg, env);
if r != 0 {
return r;
}
}
// Calculate else length for JUMP
let else_len = if let Some(ref else_n) = else_node {
compile_length_tree(else_n, reg, env)
} else {
0
};
if else_len < 0 {
return else_len;
}
// Jump over else
add_op(
reg,
OpCode::Jump,
OperationPayload::Jump {
addr: OPSIZE_CUT_TO_MARK + else_len + SIZE_INC,
},
);
// On condition failure, cut mark
add_op(
reg,
OpCode::CutToMark,
OperationPayload::CutToMark {
id,
restore_pos: false,
},
);
// Emit else branch
if let Some(ref else_n) = else_node {
let r = compile_tree(else_n, reg, env);
if r != 0 {
return r;
}
}
}
0
}
}
}
// ============================================================================
// Anchor compilation
// ============================================================================
/// Calculate bytecode length for an anchor node.
fn compile_length_anchor_node(an: &AnchorNode, reg: &RegexType, env: &ParseEnv) -> i32 {
let at = an.anchor_type;
if at == ANCR_PREC_READ {
// (?=...) positive lookahead: MARK + body + CUT_TO_MARK
let body_len = if let Some(body) = &an.body {
compile_length_tree(body, reg, env)
} else {
0
};
if body_len < 0 {
return body_len;
}
OPSIZE_MARK + body_len + OPSIZE_CUT_TO_MARK
} else if at == ANCR_PREC_READ_NOT {
// (?!...) negative lookahead: PUSH + MARK + body + POP_TO_MARK + POP + FAIL
let body_len = if let Some(body) = &an.body {
compile_length_tree(body, reg, env)
} else {
0
};
if body_len < 0 {
return body_len;
}
OPSIZE_PUSH + OPSIZE_MARK + body_len + OPSIZE_POP_TO_MARK + OPSIZE_POP + OPSIZE_FAIL
} else if at == ANCR_LOOK_BEHIND {
// (?<=...) positive lookbehind
let body_len = if let Some(body) = &an.body {
compile_length_tree(body, reg, env)
} else {
0
};
if body_len < 0 {
return body_len;
}
if an.char_min_len == an.char_max_len {
// Fixed-length
OPSIZE_MARK + OPSIZE_STEP_BACK_START + body_len + OPSIZE_CUT_TO_MARK
} else {
// Variable-length: SAVE_VAL + UPDATE_VAR + MARK + PUSH + JUMP +
// UPDATE_VAR + FAIL + [SAVE_VAL] + STEP_BACK_START + STEP_BACK_NEXT +
// body + [UPDATE_VAR] + CHECK_POSITION + CUT_TO_MARK + UPDATE_VAR
let mut len = OPSIZE_SAVE_VAL
+ OPSIZE_UPDATE_VAR
+ OPSIZE_MARK
+ OPSIZE_PUSH
+ OPSIZE_JUMP
+ OPSIZE_UPDATE_VAR
+ OPSIZE_FAIL
+ OPSIZE_STEP_BACK_START
+ OPSIZE_STEP_BACK_NEXT
+ body_len
+ OPSIZE_CHECK_POSITION
+ OPSIZE_CUT_TO_MARK
+ OPSIZE_UPDATE_VAR;
if (env.flags & PE_FLAG_HAS_ABSENT_STOPPER) != 0 {
len += OPSIZE_SAVE_VAL + OPSIZE_UPDATE_VAR;
}
len
}
} else if at == ANCR_LOOK_BEHIND_NOT {
// (?<!...) negative lookbehind
let body_len = if let Some(body) = &an.body {
compile_length_tree(body, reg, env)
} else {
0
};
if body_len < 0 {
return body_len;
}
if an.char_min_len == an.char_max_len {
// Fixed-length
OPSIZE_MARK
+ OPSIZE_PUSH
+ OPSIZE_STEP_BACK_START
+ body_len
+ OPSIZE_POP_TO_MARK
+ OPSIZE_FAIL
+ OPSIZE_POP
} else {
// Variable-length: SAVE_VAL + UPDATE_VAR + MARK + PUSH +
// [SAVE_VAL] + STEP_BACK_START + STEP_BACK_NEXT + body + [UPDATE_VAR] +
// CHECK_POSITION + POP_TO_MARK + UPDATE_VAR + POP + FAIL +
// UPDATE_VAR + POP + POP
let mut len = OPSIZE_SAVE_VAL
+ OPSIZE_UPDATE_VAR
+ OPSIZE_MARK
+ OPSIZE_PUSH
+ OPSIZE_STEP_BACK_START
+ OPSIZE_STEP_BACK_NEXT
+ body_len
+ OPSIZE_CHECK_POSITION
+ OPSIZE_POP_TO_MARK
+ OPSIZE_UPDATE_VAR
+ OPSIZE_POP
+ OPSIZE_FAIL
+ OPSIZE_UPDATE_VAR
+ OPSIZE_POP
+ OPSIZE_POP;
if (env.flags & PE_FLAG_HAS_ABSENT_STOPPER) != 0 {
len += OPSIZE_SAVE_VAL + OPSIZE_UPDATE_VAR;
}
len
}
} else {
// Simple anchors: ^, $, \b, \B, \A, \z, etc.
SIZE_INC
}
}
/// Compile an anchor node to bytecode.
fn compile_anchor_node(
an: &AnchorNode,
node_status: u32,
reg: &mut RegexType,
env: &ParseEnv,
) -> i32 {
let at = an.anchor_type;
if at == ANCR_PREC_READ {
// (?=...) positive lookahead
let id = reg.num_call;
reg.num_call += 1;
add_op(
reg,
OpCode::Mark,
OperationPayload::Mark { id, save_pos: true },
);
if let Some(body) = &an.body {
let r = compile_tree(body, reg, env);
if r != 0 {
return r;
}
}
add_op(
reg,
OpCode::CutToMark,
OperationPayload::CutToMark {
id,
restore_pos: true,
},
);
return 0;
}
if at == ANCR_PREC_READ_NOT {
// (?!...) negative lookahead
let body_len = if let Some(body) = &an.body {
compile_length_tree(body, reg, env)
} else {
0
};
let id = reg.num_call;
reg.num_call += 1;
// PUSH past the fail section (C: SIZE_INC + MARK + body + POP_TO_MARK + POP + FAIL)
let push_addr =
SIZE_INC + OPSIZE_MARK + body_len + OPSIZE_POP_TO_MARK + OPSIZE_POP + OPSIZE_FAIL;
add_op(
reg,
OpCode::Push,
OperationPayload::Push { addr: push_addr },
);
add_op(
reg,
OpCode::Mark,
OperationPayload::Mark {
id,
save_pos: false,
},
);
if let Some(body) = &an.body {
let r = compile_tree(body, reg, env);
if r != 0 {
return r;
}
}
add_op(reg, OpCode::PopToMark, OperationPayload::PopToMark { id });
add_op(reg, OpCode::Pop, OperationPayload::None);
add_op(reg, OpCode::Fail, OperationPayload::None);
return 0;
}
if at == ANCR_LOOK_BEHIND {
if an.char_min_len == an.char_max_len {
// (?<=...) positive lookbehind — fixed-length
let id = reg.num_call;
reg.num_call += 1;
add_op(
reg,
OpCode::Mark,
OperationPayload::Mark { id, save_pos: true },
);
let char_len = an.char_min_len as i32;
add_op(
reg,
OpCode::StepBackStart,
OperationPayload::StepBackStart {
initial: char_len,
remaining: 0,
addr: 1,
},
);
if let Some(body) = &an.body {
let r = compile_tree(body, reg, env);
if r != 0 {
return r;
}
}
add_op(
reg,
OpCode::CutToMark,
OperationPayload::CutToMark {
id,
restore_pos: true,
},
);
} else {
// (?<=...) positive lookbehind — variable-length
let mid1 = reg.num_call;
reg.num_call += 1;
let mid2 = reg.num_call;
reg.num_call += 1;
// SAVE_VAL(RightRange, mid1)
add_op(
reg,
OpCode::SaveVal,
OperationPayload::SaveVal {
save_type: SaveType::RightRange,
id: mid1,
},
);
// UPDATE_VAR(RightRangeToS)
add_op(
reg,
OpCode::UpdateVar,
OperationPayload::UpdateVar {
var_type: UpdateVarType::RightRangeToS,
id: 0,
clear: false,
},
);
// MARK(mid2, save_pos=false)
add_op(
reg,
OpCode::Mark,
OperationPayload::Mark {
id: mid2,
save_pos: false,
},
);
// PUSH(addr → JUMP instruction, i.e. skip past JUMP to UPDATE_VAR)
// PUSH is at position X, JUMP at X+1, UPDATE_VAR at X+2
// So alt target = X + SIZE_INC + OPSIZE_JUMP = X + 2 → UPDATE_VAR
add_op(
reg,
OpCode::Push,
OperationPayload::Push {
addr: SIZE_INC + OPSIZE_JUMP,
},
);
// JUMP(addr → past UPDATE_VAR + FAIL to STEP_BACK_START)
add_op(
reg,
OpCode::Jump,
OperationPayload::Jump {
addr: SIZE_INC + OPSIZE_UPDATE_VAR + OPSIZE_FAIL,
},
);
// UPDATE_VAR(RightRangeFromStack, mid1, clear=false) — fail path restores right_range
add_op(
reg,
OpCode::UpdateVar,
OperationPayload::UpdateVar {
var_type: UpdateVarType::RightRangeFromStack,
id: mid1,
clear: false,
},
);
// FAIL
add_op(reg, OpCode::Fail, OperationPayload::None);
// Absent stopper: save right-range before step-back
let mid3 = if (env.flags & PE_FLAG_HAS_ABSENT_STOPPER) != 0 {
let mid3 = reg.num_call;
reg.num_call += 1;
add_op(
reg,
OpCode::SaveVal,
OperationPayload::SaveVal {
save_type: SaveType::RightRange,
id: mid3,
},
);
mid3
} else {
0
};
// STEP_BACK_START(initial=min, remaining=max-min, addr=2)
let diff = if an.char_max_len != INFINITE_LEN {
(an.char_max_len - an.char_min_len) as i32
} else {
INFINITE_LEN as i32
};
add_op(
reg,
OpCode::StepBackStart,
OperationPayload::StepBackStart {
initial: an.char_min_len as i32,
remaining: diff,
addr: 2,
},
);
// STEP_BACK_NEXT
add_op(reg, OpCode::StepBackNext, OperationPayload::None);
// <body>
if let Some(body) = &an.body {
let r = compile_tree(body, reg, env);
if r != 0 {
return r;
}
}
// Absent stopper: restore right-range after body
if (env.flags & PE_FLAG_HAS_ABSENT_STOPPER) != 0 {
add_op(
reg,
OpCode::UpdateVar,
OperationPayload::UpdateVar {
var_type: UpdateVarType::RightRangeFromStack,
id: mid3,
clear: false,
},
);
}
// CHECK_POSITION(CurrentRightRange)
add_op(
reg,
OpCode::CheckPosition,
OperationPayload::CheckPosition {
check_type: CheckPositionType::CurrentRightRange,
},
);
// CUT_TO_MARK(mid2, restore_pos=false)
add_op(
reg,
OpCode::CutToMark,
OperationPayload::CutToMark {
id: mid2,
restore_pos: false,
},
);
// UPDATE_VAR(RightRangeFromStack, mid1, clear=true)
add_op(
reg,
OpCode::UpdateVar,
OperationPayload::UpdateVar {
var_type: UpdateVarType::RightRangeFromStack,
id: mid1,
clear: true,
},
);
}
return 0;
}
if at == ANCR_LOOK_BEHIND_NOT {
let body_len = if let Some(body) = &an.body {
compile_length_tree(body, reg, env)
} else {
0
};
if an.char_min_len == an.char_max_len {
// (?<!...) negative lookbehind — fixed-length
let id = reg.num_call;
reg.num_call += 1;
add_op(
reg,
OpCode::Mark,
OperationPayload::Mark {
id,
save_pos: false,
},
);
let push_addr =
SIZE_INC + OPSIZE_STEP_BACK_START + body_len + OPSIZE_POP_TO_MARK + OPSIZE_FAIL;
add_op(
reg,
OpCode::Push,
OperationPayload::Push { addr: push_addr },
);
let char_len = an.char_min_len as i32;
add_op(
reg,
OpCode::StepBackStart,
OperationPayload::StepBackStart {
initial: char_len,
remaining: 0,
addr: 1,
},
);
if let Some(body) = &an.body {
let r = compile_tree(body, reg, env);
if r != 0 {
return r;
}
}
add_op(reg, OpCode::PopToMark, OperationPayload::PopToMark { id });
add_op(reg, OpCode::Fail, OperationPayload::None);
add_op(reg, OpCode::Pop, OperationPayload::None);
} else {
// (?<!...) negative lookbehind — variable-length
let mid1 = reg.num_call;
reg.num_call += 1;
let mid2 = reg.num_call;
reg.num_call += 1;
// SAVE_VAL(RightRange, mid1)
add_op(
reg,
OpCode::SaveVal,
OperationPayload::SaveVal {
save_type: SaveType::RightRange,
id: mid1,
},
);
// UPDATE_VAR(RightRangeToS)
add_op(
reg,
OpCode::UpdateVar,
OperationPayload::UpdateVar {
var_type: UpdateVarType::RightRangeToS,
id: 0,
clear: false,
},
);
// MARK(mid2, save_pos=false)
add_op(
reg,
OpCode::Mark,
OperationPayload::Mark {
id: mid2,
save_pos: false,
},
);
// PUSH(addr → success path past body-matched-fail section)
// From PUSH: skip [SAVE_VAL] + STEP_BACK_START + STEP_BACK_NEXT + body +
// [UPDATE_VAR] + CHECK_POSITION + POP_TO_MARK + UPDATE_VAR + POP + FAIL
let mut push_addr = SIZE_INC
+ OPSIZE_STEP_BACK_START
+ OPSIZE_STEP_BACK_NEXT
+ body_len
+ OPSIZE_CHECK_POSITION
+ OPSIZE_POP_TO_MARK
+ OPSIZE_UPDATE_VAR
+ OPSIZE_POP
+ OPSIZE_FAIL;
if (env.flags & PE_FLAG_HAS_ABSENT_STOPPER) != 0 {
push_addr += OPSIZE_SAVE_VAL + OPSIZE_UPDATE_VAR;
}
add_op(
reg,
OpCode::Push,
OperationPayload::Push { addr: push_addr },
);
// Absent stopper: save right-range before step-back
let mid3 = if (env.flags & PE_FLAG_HAS_ABSENT_STOPPER) != 0 {
let mid3 = reg.num_call;
reg.num_call += 1;
add_op(
reg,
OpCode::SaveVal,
OperationPayload::SaveVal {
save_type: SaveType::RightRange,
id: mid3,
},
);
mid3
} else {
0
};
// STEP_BACK_START(initial=min, remaining=max-min, addr=2)
let diff = if an.char_max_len != INFINITE_LEN {
(an.char_max_len - an.char_min_len) as i32
} else {
INFINITE_LEN as i32
};
add_op(
reg,
OpCode::StepBackStart,
OperationPayload::StepBackStart {
initial: an.char_min_len as i32,
remaining: diff,
addr: 2,
},
);
// STEP_BACK_NEXT
add_op(reg, OpCode::StepBackNext, OperationPayload::None);
// <body>
if let Some(body) = &an.body {
let r = compile_tree(body, reg, env);
if r != 0 {
return r;
}
}
// Absent stopper: restore right-range after body
if (env.flags & PE_FLAG_HAS_ABSENT_STOPPER) != 0 {
add_op(
reg,
OpCode::UpdateVar,
OperationPayload::UpdateVar {
var_type: UpdateVarType::RightRangeFromStack,
id: mid3,
clear: false,
},
);
}
// CHECK_POSITION(CurrentRightRange) — body matched here, verify position
add_op(
reg,
OpCode::CheckPosition,
OperationPayload::CheckPosition {
check_type: CheckPositionType::CurrentRightRange,
},
);
// POP_TO_MARK(mid2) — body succeeded: clean up mark
add_op(
reg,
OpCode::PopToMark,
OperationPayload::PopToMark { id: mid2 },
);
// UPDATE_VAR(RightRangeFromStack, mid1, clear=false) — restore right_range
add_op(
reg,
OpCode::UpdateVar,
OperationPayload::UpdateVar {
var_type: UpdateVarType::RightRangeFromStack,
id: mid1,
clear: false,
},
);
// POP — discard outer PUSH's SaveVal
add_op(reg, OpCode::Pop, OperationPayload::None);
// FAIL — negative lookbehind: body match = overall failure
add_op(reg, OpCode::Fail, OperationPayload::None);
// === Success path (body failed at all positions) ===
// UPDATE_VAR(RightRangeFromStack, mid1, clear=false) — restore right_range
add_op(
reg,
OpCode::UpdateVar,
OperationPayload::UpdateVar {
var_type: UpdateVarType::RightRangeFromStack,
id: mid1,
clear: false,
},
);
// POP — discard Mark
add_op(reg, OpCode::Pop, OperationPayload::None);
// POP — discard SaveVal
add_op(reg, OpCode::Pop, OperationPayload::None);
}
return 0;
}
// Simple anchors
match at {
ANCR_BEGIN_BUF => {
add_op(reg, OpCode::BeginBuf, OperationPayload::None);
}
ANCR_END_BUF => {
add_op(reg, OpCode::EndBuf, OperationPayload::None);
}
ANCR_BEGIN_LINE => {
add_op(reg, OpCode::BeginLine, OperationPayload::None);
}
ANCR_END_LINE => {
add_op(reg, OpCode::EndLine, OperationPayload::None);
}
ANCR_SEMI_END_BUF => {
add_op(reg, OpCode::SemiEndBuf, OperationPayload::None);
}
ANCR_BEGIN_POSITION => {
add_op(
reg,
OpCode::CheckPosition,
OperationPayload::CheckPosition {
check_type: CheckPositionType::SearchStart,
},
);
}
ANCR_WORD_BOUNDARY => {
let mode = if an.ascii_mode { 1 } else { 0 };
add_op(
reg,
OpCode::WordBoundary,
OperationPayload::WordBoundary { mode },
);
}
ANCR_NO_WORD_BOUNDARY => {
let mode = if an.ascii_mode { 1 } else { 0 };
add_op(
reg,
OpCode::NoWordBoundary,
OperationPayload::WordBoundary { mode },
);
}
ANCR_WORD_BEGIN => {
let mode = if an.ascii_mode { 1 } else { 0 };
add_op(
reg,
OpCode::WordBegin,
OperationPayload::WordBoundary { mode },
);
}
ANCR_WORD_END => {
let mode = if an.ascii_mode { 1 } else { 0 };
add_op(
reg,
OpCode::WordEnd,
OperationPayload::WordBoundary { mode },
);
}
ANCR_TEXT_SEGMENT_BOUNDARY | ANCR_NO_TEXT_SEGMENT_BOUNDARY => {
let boundary_type = if (node_status & ND_ST_TEXT_SEGMENT_WORD) != 0 {
TextSegmentBoundaryType::Word
} else {
TextSegmentBoundaryType::ExtendedGraphemeCluster
};
let not = at == ANCR_NO_TEXT_SEGMENT_BOUNDARY;
add_op(
reg,
OpCode::TextSegmentBoundary,
OperationPayload::TextSegmentBoundary { boundary_type, not },
);
}
_ => {
return ONIGERR_TYPE_BUG;
}
}
0
}
// ============================================================================
// Gimmick compilation
// ============================================================================
/// Calculate bytecode length for a gimmick node.
fn compile_length_gimmick_node(gn: &GimmickNode) -> i32 {
match gn.gimmick_type {
GimmickType::Fail => SIZE_INC,
GimmickType::Save => OPSIZE_SAVE_VAL,
GimmickType::UpdateVar => OPSIZE_UPDATE_VAR,
GimmickType::Callout => SIZE_INC,
}
}
/// Compile a gimmick node to bytecode.
fn compile_gimmick_node(gn: &GimmickNode, reg: &mut RegexType, env: &ParseEnv) -> i32 {
match gn.gimmick_type {
GimmickType::Fail => {
add_op(reg, OpCode::Fail, OperationPayload::None);
}
GimmickType::Save => {
let save_type = match gn.detail_type {
1 => SaveType::S,
2 => SaveType::RightRange,
_ => SaveType::Keep,
};
add_op(
reg,
OpCode::SaveVal,
OperationPayload::SaveVal {
save_type,
id: gn.id,
},
);
}
GimmickType::UpdateVar => {
let var_type = match gn.detail_type {
1 => UpdateVarType::SFromStack,
2 => UpdateVarType::RightRangeFromStack,
3 => UpdateVarType::RightRangeFromSStack,
4 => UpdateVarType::RightRangeToS,
5 => UpdateVarType::RightRangeInit,
_ => UpdateVarType::KeepFromStackLast,
};
add_op(
reg,
OpCode::UpdateVar,
OperationPayload::UpdateVar {
var_type,
id: gn.id,
clear: false,
},
);
}
GimmickType::Callout => {
if gn.detail_type == OnigCalloutOf::Name as i32 {
add_op(
reg,
OpCode::CalloutName,
OperationPayload::CalloutName {
num: gn.num,
id: gn.id,
},
);
} else {
add_op(
reg,
OpCode::CalloutContents,
OperationPayload::CalloutContents { num: gn.num },
);
}
}
}
0
}
// ============================================================================
// Main compilation passes
// ============================================================================
/// Pass 1: Calculate the bytecode length needed for a node tree.
/// Returns the number of operations that will be generated.
pub fn compile_length_tree(node: &Node, reg: &RegexType, env: &ParseEnv) -> i32 {
// Literal alternation trie: single AltLiterals opcode.
if node.has_status(ND_ST_LITERAL_ALT) {
return SIZE_INC;
}
match &node.inner {
NodeInner::List(cons) => {
let mut len = 0i32;
// Compile car
len += compile_length_tree(&cons.car, reg, env);
// Walk cdr chain
let mut cur = cons.cdr.as_ref();
while let Some(next) = cur {
if let NodeInner::List(c) = &next.inner {
len += compile_length_tree(&c.car, reg, env);
cur = c.cdr.as_ref();
} else {
len += compile_length_tree(next, reg, env);
break;
}
}
len
}
NodeInner::Alt(cons) => {
// For alternation, each branch needs PUSH + body + JUMP (except last)
let mut total = 0i32;
let mut n_alts = 0i32;
// First alternative
let first_len = compile_length_tree(&cons.car, reg, env);
total += first_len;
n_alts += 1;
let mut cur = cons.cdr.as_ref();
while let Some(next) = cur {
if let NodeInner::Alt(c) = &next.inner {
let branch_len = compile_length_tree(&c.car, reg, env);
total += branch_len;
n_alts += 1;
cur = c.cdr.as_ref();
} else {
let branch_len = compile_length_tree(next, reg, env);
total += branch_len;
n_alts += 1;
cur = None;
}
}
// Each branch except the last needs PUSH + JUMP
total += (n_alts - 1) * (OPSIZE_PUSH + OPSIZE_JUMP);
total
}
NodeInner::String(_) => {
let sn = node.as_str().unwrap();
if sn.is_crude() {
compile_length_string_crude_node(node, reg)
} else {
compile_length_string_node(node, reg)
}
}
NodeInner::CClass(cc) => compile_length_cclass_node(cc, reg),
NodeInner::CType(ct) => SIZE_INC,
NodeInner::BackRef(_br) => OPSIZE_BACKREF,
NodeInner::Quant(qn) => compile_length_quantifier_node(qn, reg, env),
NodeInner::Bag(bag) => compile_length_bag_node(bag, node.status, reg, env),
NodeInner::Anchor(an) => compile_length_anchor_node(an, reg, env),
NodeInner::Gimmick(gn) => compile_length_gimmick_node(gn),
NodeInner::Call(_) => OPSIZE_CALL,
}
}
/// Pass 2: Generate bytecode operations from the node tree.
/// Returns 0 on success or a negative error code.
pub fn compile_tree(node: &Node, reg: &mut RegexType, env: &ParseEnv) -> i32 {
// Literal alternation trie: emit single AltLiterals opcode.
if node.has_status(ND_ST_LITERAL_ALT) {
if let NodeInner::String(ref sn) = node.inner {
let trie_idx = u32::from_le_bytes([sn.s[0], sn.s[1], sn.s[2], sn.s[3]]);
add_op(
reg,
OpCode::AltLiterals,
OperationPayload::AltLiterals { trie_idx },
);
return 0;
}
}
match &node.inner {
NodeInner::List(cons) => {
let r = compile_tree(&cons.car, reg, env);
if r != 0 {
return r;
}
let mut cur = cons.cdr.as_ref();
while let Some(next) = cur {
if let NodeInner::List(c) = &next.inner {
let r = compile_tree(&c.car, reg, env);
if r != 0 {
return r;
}
cur = c.cdr.as_ref();
} else {
return compile_tree(next, reg, env);
}
}
0
}
NodeInner::Alt(cons) => {
// Check if this Alt has SUPER status (used by absent function)
let is_super = node.has_status(ND_ST_SUPER);
let push_opcode = if is_super {
OpCode::PushSuper
} else {
OpCode::Push
};
// Collect all alternatives to calculate lengths
let mut branches: Vec<&Node> = Vec::new();
branches.push(&cons.car);
let mut cur = cons.cdr.as_ref();
while let Some(next) = cur {
if let NodeInner::Alt(c) = &next.inner {
branches.push(&c.car);
cur = c.cdr.as_ref();
} else {
branches.push(next);
cur = None;
}
}
let n = branches.len();
if n == 1 {
return compile_tree(branches[0], reg, env);
}
// Pre-calculate branch lengths
let mut branch_lens: Vec<i32> = Vec::with_capacity(n);
for b in &branches {
branch_lens.push(compile_length_tree(b, reg, env));
}
// Calculate total length to find goal position
// Layout: for each branch i < n-1: PUSH + body_i + JUMP; last branch: body_{n-1}
let mut total_len = 0i32;
for (i, branch_len) in branch_lens.iter().enumerate() {
total_len += branch_len;
if i < n - 1 {
total_len += OPSIZE_PUSH + OPSIZE_JUMP;
}
}
let goal = reg.ops.len() as i32 + total_len;
for (i, branch) in branches.iter().enumerate() {
if i < n - 1 {
// PUSH to next alternative (skip over body + JUMP)
let push_addr = SIZE_INC + branch_lens[i] + OPSIZE_JUMP;
add_op(reg, push_opcode, OperationPayload::Push { addr: push_addr });
}
let r = compile_tree(branch, reg, env);
if r != 0 {
return r;
}
if i < n - 1 {
// JUMP to end of alternation (goal position)
let jump_addr = goal - reg.ops.len() as i32;
add_op(
reg,
OpCode::Jump,
OperationPayload::Jump { addr: jump_addr },
);
}
}
0
}
NodeInner::String(_) => {
let sn = node.as_str().unwrap();
if sn.is_crude() {
compile_string_crude_node(node, reg)
} else {
compile_string_node(node, reg)
}
}
NodeInner::CClass(cc) => compile_cclass_node(cc, reg),
NodeInner::CType(ct) => {
let opcode = match ct.ctype as u32 {
ONIGENC_CTYPE_WORD => {
if ct.not {
if ct.ascii_mode {
OpCode::NoWordAscii
} else {
OpCode::NoWord
}
} else {
if ct.ascii_mode {
OpCode::WordAscii
} else {
OpCode::Word
}
}
}
_ => {
// Anychar type
if node.has_status(ND_ST_MULTILINE) {
OpCode::AnyCharMl
} else {
OpCode::AnyChar
}
}
};
add_op(reg, opcode, OperationPayload::None);
0
}
NodeInner::BackRef(br) => {
let refs = br.back_refs();
if node.has_status(ND_ST_CHECKER) {
// BackRef checker for conditionals: (?(1)then|else)
let ns = refs.to_vec();
let opcode = if node.has_status(ND_ST_NEST_LEVEL) {
OpCode::BackRefCheckWithLevel
} else {
OpCode::BackRefCheck
};
add_op(
reg,
opcode,
OperationPayload::BackRefGeneral {
num: refs.len() as i32,
ns,
nest_level: br.nest_level,
},
);
} else if node.has_status(ND_ST_NEST_LEVEL) {
// Level-based backref for recursion: \k<1+3>
let ns = refs.to_vec();
let opcode = if node.has_status(ND_ST_IGNORECASE) {
OpCode::BackRefWithLevelIc
} else {
OpCode::BackRefWithLevel
};
add_op(
reg,
opcode,
OperationPayload::BackRefGeneral {
num: refs.len() as i32,
ns,
nest_level: br.nest_level,
},
);
} else if refs.len() == 1 {
let n = refs[0];
if node.has_status(ND_ST_IGNORECASE) {
add_op(
reg,
OpCode::BackRefNIc,
OperationPayload::BackRefN { n1: n },
);
} else {
match n {
1 => {
add_op(reg, OpCode::BackRef1, OperationPayload::None);
}
2 => {
add_op(reg, OpCode::BackRef2, OperationPayload::None);
}
_ => {
add_op(reg, OpCode::BackRefN, OperationPayload::BackRefN { n1: n });
}
}
}
} else {
// Multi backref
let ns = refs.to_vec();
if node.has_status(ND_ST_IGNORECASE) {
add_op(
reg,
OpCode::BackRefMultiIc,
OperationPayload::BackRefGeneral {
num: refs.len() as i32,
ns,
nest_level: 0,
},
);
} else {
add_op(
reg,
OpCode::BackRefMulti,
OperationPayload::BackRefGeneral {
num: refs.len() as i32,
ns,
nest_level: 0,
},
);
}
}
0
}
NodeInner::Quant(qn) => compile_quantifier_node(qn, reg, env),
NodeInner::Bag(bag) => compile_bag_node(bag, node.status, reg, env),
NodeInner::Anchor(an) => compile_anchor_node(an, node.status, reg, env),
NodeInner::Gimmick(gn) => compile_gimmick_node(gn, reg, env),
NodeInner::Call(call) => {
// Look up the called_addr for this group
let gnum = call.called_gnum as usize;
let addr = if gnum < reg.called_addrs.len() && reg.called_addrs[gnum] >= 0 {
reg.called_addrs[gnum]
} else {
0 // Will be patched later if not yet compiled
};
add_op(reg, OpCode::Call, OperationPayload::Call { addr });
// Record for later patching if the group hasn't been compiled yet
if gnum >= reg.called_addrs.len() || reg.called_addrs[gnum] < 0 {
// Store the index of this OP_CALL for patching
let call_idx = reg.ops.len() - 1;
reg.unset_call_addrs.push((call_idx, gnum as i32));
}
0
}
}
}
// ============================================================================
// Entry points
// ============================================================================
/// Helper: check if mem_status bit 0 is on (meaning "all on")
#[inline]
fn mem_status_is_all_on(stats: MemStatusType) -> bool {
(stats & 1) != 0
}
// ============================================================================
// tune_tree state flags (matching C's IN_* defines from regcomp.c:4481)
// ============================================================================
const IN_ALT: i32 = 1 << 0;
const IN_NOT: i32 = 1 << 1;
const IN_REAL_REPEAT: i32 = 1 << 2;
const IN_VAR_REPEAT: i32 = 1 << 3;
const IN_MULTI_ENTRY: i32 = 1 << 5;
const IN_ZERO_REPEAT: i32 = 1 << 4;
const IN_PREC_READ: i32 = 1 << 6;
const IN_LOOK_BEHIND: i32 = 1 << 7;
const IN_PEEK: i32 = 1 << 8;
/// Calculate minimum byte length a node can match.
/// Mirrors C's node_min_byte_len() from regcomp.c.
fn node_min_byte_len(node: &Node, env: &ParseEnv) -> OnigLen {
match &node.inner {
NodeInner::String(sn) => sn.s.len() as OnigLen,
NodeInner::CType(_) | NodeInner::CClass(_) => env.enc.min_enc_len() as OnigLen,
NodeInner::List(_) => {
let mut len: OnigLen = 0;
let mut cur = node;
while let NodeInner::List(cons) = &cur.inner {
let tmin = node_min_byte_len(&cons.car, env);
len = distance_add(len, tmin);
match &cons.cdr {
Some(next) => cur = next,
None => break,
}
}
len
}
NodeInner::Alt(_) => {
let mut len: OnigLen = 0;
let mut first = true;
let mut cur = node;
while let NodeInner::Alt(cons) = &cur.inner {
let tmin = node_min_byte_len(&cons.car, env);
if first {
len = tmin;
first = false;
} else if len > tmin {
len = tmin;
}
match &cons.cdr {
Some(next) => cur = next,
None => break,
}
}
len
}
NodeInner::Quant(qn) => {
if qn.lower > 0 {
if let Some(ref body) = qn.body {
let len = node_min_byte_len(body, env);
distance_multiply(len, qn.lower)
} else {
0
}
} else {
0
}
}
NodeInner::Bag(bn) => {
match bn.bag_type {
BagType::Option | BagType::StopBacktrack => {
if let Some(ref body) = bn.body {
node_min_byte_len(body, env)
} else {
0
}
}
BagType::Memory => {
// Do not cache through a shared node reference. Calls are
// conservatively treated as empty below, so this ownership-tree
// traversal cannot recurse through a self-reference.
if let Some(body) = &bn.body {
node_min_byte_len(body, env)
} else {
0
}
}
BagType::IfElse => {
if let BagData::IfElse {
ref then_node,
ref else_node,
} = bn.bag_data
{
let mut len = if let Some(ref body) = bn.body {
node_min_byte_len(body, env)
} else {
0
};
if let Some(ref then_n) = then_node {
len += node_min_byte_len(then_n, env);
}
let elen = if let Some(ref else_n) = else_node {
node_min_byte_len(else_n, env)
} else {
0
};
if elen < len {
elen
} else {
len
}
} else {
0
}
}
}
}
NodeInner::BackRef(br) => {
if node.has_status(ND_ST_CHECKER) {
0
} else {
// Simplified: return 0 for backrefs (safe minimum)
0
}
}
// Following a call would re-enter a self-referential raw pointer. Zero is
// a conservative minimum and merely prevents unsound optimizations.
NodeInner::Call(_) => 0,
NodeInner::Anchor(_) | NodeInner::Gimmick(_) => 0,
}
}
/// Check if a quantifier body contains capture groups (Memory bags).
/// Returns the appropriate emptiness type. Mirrors C's quantifiers_memory_node_info().
fn quantifiers_memory_node_info(node: &Node) -> BodyEmptyType {
let mut r = BodyEmptyType::MayBeEmpty;
match &node.inner {
NodeInner::List(_) | NodeInner::Alt(_) => {
let mut cur = node;
loop {
let (car, cdr) = match &cur.inner {
NodeInner::List(cons) => (&cons.car, &cons.cdr),
NodeInner::Alt(cons) => (&cons.car, &cons.cdr),
_ => break,
};
let v = quantifiers_memory_node_info(car);
if v as i32 > r as i32 {
r = v;
}
match cdr {
Some(next) => cur = next,
None => break,
}
}
}
NodeInner::Quant(qn) => {
if qn.upper != 0 {
if let Some(ref body) = qn.body {
r = quantifiers_memory_node_info(body);
}
}
}
NodeInner::Bag(bn) => match bn.bag_type {
BagType::Memory => {
return BodyEmptyType::MayBeEmptyMem;
}
BagType::Option | BagType::StopBacktrack => {
if let Some(ref body) = bn.body {
r = quantifiers_memory_node_info(body);
}
}
BagType::IfElse => {
if let Some(ref body) = bn.body {
r = quantifiers_memory_node_info(body);
}
if let BagData::IfElse {
ref then_node,
ref else_node,
} = bn.bag_data
{
if let Some(ref then_n) = then_node {
let v = quantifiers_memory_node_info(then_n);
if v as i32 > r as i32 {
r = v;
}
}
if let Some(ref else_n) = else_node {
let v = quantifiers_memory_node_info(else_n);
if v as i32 > r as i32 {
r = v;
}
}
}
}
},
_ => {}
}
r
}
/// Get min and max byte_len across case-fold items.
/// Mirrors C's get_min_max_byte_len_case_fold_items().
fn get_min_max_byte_len_case_fold_items(
n: i32,
items: &[OnigCaseFoldCodeItem],
) -> (OnigLen, OnigLen) {
let mut min_len: OnigLen = INFINITE_LEN;
let mut max_len: OnigLen = 0;
for item in items.iter().take(n as usize) {
let len = item.byte_len as OnigLen;
if len < min_len {
min_len = len;
}
if len > max_len {
max_len = len;
}
}
(min_len, max_len)
}
/// Expand a case-insensitive string node into CClass/List nodes.
/// Mirrors C's unravel_case_fold_string() from regcomp.c.
///
/// For each character in the string:
/// - If it has case-fold alternatives (e.g. 'c' -> 'C'), create a CClass node [cC]
/// - Otherwise, accumulate into a plain string node
/// - Combine all resulting nodes into a List
fn unravel_case_fold_string(node: &mut Node, reg: &mut RegexType, state: i32) -> i32 {
let enc = reg.enc;
let in_look_behind = (state & IN_LOOK_BEHIND) != 0;
// Extract string bytes and clear ignorecase flag
let s_bytes = if let NodeInner::String(ref sn) = node.inner {
sn.s.clone()
} else {
return ONIG_NORMAL;
};
node.status_remove(ND_ST_IGNORECASE);
let mut items = vec![
OnigCaseFoldCodeItem {
byte_len: 0,
code_len: 0,
code: [0; ONIGENC_MAX_COMP_CASE_FOLD_CODE_LEN]
};
ONIGENC_GET_CASE_FOLD_CODES_MAX_NUM
];
let mut nodes: Vec<Box<Node>> = Vec::new();
let mut pending: Vec<u8> = Vec::new(); // accumulate non-foldable chars
let mut pos = 0;
while pos < s_bytes.len() {
let one_len = enc.mbc_enc_len(&s_bytes[pos..]);
let mut n = enc.get_case_fold_codes_by_str(
reg.case_fold_flag,
&s_bytes[pos..],
s_bytes.len(),
&mut items,
);
if n > 0 {
// Flush pending plain string
if !pending.is_empty() {
nodes.push(node_new_str(&pending));
pending.clear();
}
if in_look_behind {
// In lookbehind: only allow same-byte-length single-codepoint folds
let q = pos + one_len;
// If first item's byte_len differs from one_len, re-query with shorter end
if items[0].byte_len != one_len as i32 {
n = enc.get_case_fold_codes_by_str(
reg.case_fold_flag,
&s_bytes[pos..q],
q - pos,
&mut items,
);
}
// Check if any same-byte-length single-code fold exists
let found = items
.iter()
.take(n as usize)
.any(|item| item.byte_len == one_len as i32 && item.code_len == 1);
if !found {
// No valid fold for lookbehind — keep as plain string
pending.extend_from_slice(&s_bytes[pos..q]);
pos = q;
} else {
// Build CClass with original + same-length folds
let mut cc_node = node_new_cclass();
let cc = cc_node.as_cclass_mut().unwrap();
let code = enc.mbc_to_code(&s_bytes[pos..], s_bytes.len() - pos);
crate::regparse::add_code_into_cc(cc, code, enc);
for item in items.iter().take(n as usize) {
if item.byte_len == one_len as i32 && item.code_len == 1 {
crate::regparse::add_code_into_cc(cc, item.code[0], enc);
}
}
nodes.push(cc_node);
pos = q;
}
} else {
// Normal (non-lookbehind) case fold
// Check if all items are single-codepoint folds
let all_single = items.iter().take(n as usize).all(|item| item.code_len == 1);
if all_single {
// All single-char: create CClass with original + alternatives
let mut cc_node = node_new_cclass();
let cc = cc_node.as_cclass_mut().unwrap();
let code = enc.mbc_to_code(&s_bytes[pos..], s_bytes.len() - pos);
crate::regparse::add_code_into_cc(cc, code, enc);
for item in items.iter().take(n as usize) {
crate::regparse::add_code_into_cc(cc, item.code[0], enc);
}
nodes.push(cc_node);
pos += one_len;
} else {
// Multi-char folds present: create Alt with string alternatives
let (min_byte_len, max_byte_len_val) =
get_min_max_byte_len_case_fold_items(n, &items);
if min_byte_len != max_byte_len_val {
return ONIGERR_PARSER_BUG;
}
let max_byte_len = max_byte_len_val as usize;
// First alternative: original string bytes
let orig_str = &s_bytes[pos..pos + max_byte_len];
let mut alt_node: Box<Node> = node_new_alt(node_new_str(orig_str), None);
let mut curr = &mut alt_node;
for item in items.iter().take(n as usize) {
// Convert codepoints to string bytes
let mut buf = Vec::new();
let mut tmp = [0u8; 6]; // max UTF-8 bytes per codepoint
for ci in 0..(item.code_len as usize) {
let blen = enc.code_to_mbc(item.code[ci], &mut tmp);
buf.extend_from_slice(&tmp[..blen as usize]);
}
let new_alt = node_new_alt(node_new_str(&buf), None);
// Append to chain
if let NodeInner::Alt(ref mut ca) = curr.inner {
ca.cdr = Some(new_alt);
curr = ca.cdr.as_mut().unwrap();
}
}
nodes.push(alt_node);
pos += max_byte_len;
}
}
} else {
// No case fold: accumulate into pending string
pending.extend_from_slice(&s_bytes[pos..pos + one_len]);
pos += one_len;
}
}
// Flush any remaining pending string
if !pending.is_empty() {
nodes.push(node_new_str(&pending));
}
// Build result: single node or List
if nodes.is_empty() {
node.inner = NodeInner::String(StrNode {
s: Vec::new(),
flag: 0,
});
} else if nodes.len() == 1 {
let n = nodes.pop().unwrap();
*node = *n;
} else {
// Build List from right to left
let mut list: Option<Box<Node>> = None;
for n in nodes.into_iter().rev() {
list = Some(node_new_list(n, list));
}
*node = *list.unwrap();
}
ONIG_NORMAL
}
// ============================================================================
// Lookbehind support: node_char_len, tune_look_behind, divide_look_behind_alternatives
// ============================================================================
/// Result of computing character length for a node subtree.
enum CharLenResult {
Fixed(OnigLen),
Variable(OnigLen, OnigLen),
}
/// Compute character count (not byte count) for a node subtree.
fn node_char_len(node: &Node, enc: OnigEncoding) -> CharLenResult {
match &node.inner {
NodeInner::String(sn) => {
let n = onigenc_strlen(enc, &sn.s, 0, sn.s.len());
CharLenResult::Fixed(n as OnigLen)
}
NodeInner::CType(_) | NodeInner::CClass(_) => CharLenResult::Fixed(1),
NodeInner::List(_) => {
let mut sum: OnigLen = 0;
let mut variable = false;
let mut min_sum: OnigLen = 0;
let mut max_sum: OnigLen = 0;
let mut cur = node;
while let NodeInner::List(cons) = &cur.inner {
match node_char_len(&cons.car, enc) {
CharLenResult::Fixed(n) => {
if variable {
min_sum = distance_add(min_sum, n);
max_sum = distance_add(max_sum, n);
} else {
sum = distance_add(sum, n);
}
}
CharLenResult::Variable(mn, mx) => {
if !variable {
min_sum = sum;
max_sum = sum;
variable = true;
}
min_sum = distance_add(min_sum, mn);
max_sum = distance_add(max_sum, mx);
}
}
match &cons.cdr {
Some(next) => cur = next,
None => break,
}
}
if variable {
CharLenResult::Variable(min_sum, max_sum)
} else {
CharLenResult::Fixed(sum)
}
}
NodeInner::Alt(_) => {
let mut min: OnigLen = OnigLen::MAX;
let mut max: OnigLen = 0;
let mut cur = node;
while let NodeInner::Alt(cons) = &cur.inner {
let (mn, mx) = match node_char_len(&cons.car, enc) {
CharLenResult::Fixed(n) => (n, n),
CharLenResult::Variable(mn, mx) => (mn, mx),
};
if mn < min {
min = mn;
}
if mx > max {
max = mx;
}
match &cons.cdr {
Some(next) => cur = next,
None => break,
}
}
if min == max {
CharLenResult::Fixed(min)
} else {
CharLenResult::Variable(min, max)
}
}
NodeInner::Quant(qn) => {
if let Some(ref body) = qn.body {
match node_char_len(body, enc) {
CharLenResult::Fixed(n) => {
let lo = distance_multiply(n, qn.lower);
let hi = if qn.upper == INFINITE_REPEAT {
INFINITE_LEN
} else {
distance_multiply(n, qn.upper)
};
if lo == hi {
CharLenResult::Fixed(lo)
} else {
CharLenResult::Variable(lo, hi)
}
}
CharLenResult::Variable(mn, mx) => {
let lo = distance_multiply(mn, qn.lower);
let hi = if qn.upper == INFINITE_REPEAT {
INFINITE_LEN
} else {
distance_multiply(mx, qn.upper)
};
CharLenResult::Variable(lo, hi)
}
}
} else {
CharLenResult::Fixed(0)
}
}
NodeInner::Bag(bn) => {
if let BagData::IfElse {
ref then_node,
ref else_node,
} = bn.bag_data
{
// Condition (body) may consume input (non-backref pattern conditions)
// or be zero-width (backref checker conditions).
let cond_len = if let Some(ref body) = bn.body {
if body.has_status(ND_ST_CHECKER) {
// Backref checker: zero length
(0 as OnigLen, 0 as OnigLen)
} else {
match node_char_len(body, enc) {
CharLenResult::Fixed(n) => (n, n),
CharLenResult::Variable(mn, mx) => (mn, mx),
}
}
} else {
(0, 0)
};
let then_len = if let Some(ref n) = then_node {
match node_char_len(n, enc) {
CharLenResult::Fixed(n) => (n, n),
CharLenResult::Variable(mn, mx) => (mn, mx),
}
} else {
(0, 0)
};
let else_len = if let Some(ref n) = else_node {
match node_char_len(n, enc) {
CharLenResult::Fixed(n) => (n, n),
CharLenResult::Variable(mn, mx) => (mn, mx),
}
} else {
(0, 0)
};
// Success path: condition + then; Failure path: else
let success_min = distance_add(cond_len.0, then_len.0);
let success_max = distance_add(cond_len.1, then_len.1);
let min = std::cmp::min(success_min, else_len.0);
let max = std::cmp::max(success_max, else_len.1);
if min == max {
CharLenResult::Fixed(min)
} else {
CharLenResult::Variable(min, max)
}
} else if let Some(ref body) = bn.body {
node_char_len(body, enc)
} else {
CharLenResult::Fixed(0)
}
}
NodeInner::Anchor(_) => CharLenResult::Fixed(0),
NodeInner::BackRef(_) => CharLenResult::Variable(0, INFINITE_LEN),
NodeInner::Call(ref cn) => {
// Follow the call target to compute the character length of the called group
if !cn.target_node.is_null() {
// SAFETY: `target_node` is non-null (checked above) and was set by
// resolve_call_references/refresh_call_targets to the called group's
// Bag node inside this same live tree; only shared reads follow.
let target = unsafe { &*cn.target_node };
node_char_len(target, enc)
} else {
CharLenResult::Fixed(0)
}
}
_ => CharLenResult::Fixed(0),
}
}
/// Divide variable-length lookbehind with Alt body into per-branch fixed-length lookbehinds.
/// For positive: Alt(Anchor(LB,a), Anchor(LB,b)) — any branch must match (OR).
/// For negative: List(Anchor(LB_NOT,a), Anchor(LB_NOT,b)) — all branches must pass (AND).
fn divide_look_behind_alt(node: &mut Node, anchor_type: i32, enc: OnigEncoding) -> i32 {
// Extract anchor fields
let (body, ascii_mode) = if let NodeInner::Anchor(ref mut an) = node.inner {
(an.body.take().unwrap(), an.ascii_mode)
} else {
return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
};
// Collect all Alt branches
let mut branches: Vec<Box<Node>> = Vec::new();
let mut cur = body;
loop {
if let NodeInner::Alt(cons) = cur.inner {
branches.push(cons.car);
match cons.cdr {
Some(next) => cur = next,
None => break,
}
} else {
branches.push(cur);
break;
}
}
let use_list = anchor_type == ANCR_LOOK_BEHIND_NOT;
// Build new node tree of anchors, from last to first
let mut result: Option<Box<Node>> = None;
for branch in branches.into_iter().rev() {
let char_len = match node_char_len(&branch, enc) {
CharLenResult::Fixed(n) => n,
CharLenResult::Variable(_, _) => return ONIGERR_INVALID_LOOK_BEHIND_PATTERN,
};
let mut anchor = node_new_anchor(anchor_type);
if let NodeInner::Anchor(ref mut an) = anchor.inner {
an.body = Some(branch);
an.char_min_len = char_len;
an.char_max_len = char_len;
an.ascii_mode = ascii_mode;
}
if use_list {
// Negative lookbehind: ALL branches must pass (List = AND)
result = Some(node_new_list(anchor, result));
} else {
// Positive lookbehind: ANY branch must match (Alt = OR)
result = Some(node_new_alt(anchor, result));
}
}
// Replace the original node with the new tree
if let Some(new_node) = result {
*node = *new_node;
}
ONIG_NORMAL
}
/// Check if a node is an Alt where all top-level branches are individually fixed-length.
/// Returns true only if: node is Alt, and every branch has CharLenResult::Fixed.
fn is_alt_all_branches_fixed(node: &Node, enc: OnigEncoding) -> bool {
let mut cur = node;
loop {
if let NodeInner::Alt(cons) = &cur.inner {
match node_char_len(&cons.car, enc) {
CharLenResult::Fixed(_) => {}
CharLenResult::Variable(_, _) => return false,
}
match &cons.cdr {
Some(next) => cur = next,
None => return true,
}
} else {
return false;
}
}
}
/// Check if a node tree contains absent stoppers (ND_ST_ABSENT_WITH_SIDE_EFFECTS).
/// Returns true if invalid nodes are found inside lookbehind.
/// C: check_node_in_look_behind (simplified — we only need the absent stopper check).
// Allowed node types in lookbehind (C: ALLOWED_TYPE_IN_LB)
const ALLOWED_TYPE_IN_LB: u32 = ND_BIT_LIST
| ND_BIT_ALT
| ND_BIT_STRING
| ND_BIT_CCLASS
| ND_BIT_CTYPE
| ND_BIT_ANCHOR
| ND_BIT_BAG
| ND_BIT_QUANT
| ND_BIT_CALL
| ND_BIT_BACKREF
| ND_BIT_GIMMICK;
// Allowed bag types: positive lookbehind allows Memory; negative does not
const ALLOWED_BAG_IN_LB: u32 = (1 << BagType::Memory as u32)
| (1 << BagType::Option as u32)
| (1 << BagType::StopBacktrack as u32)
| (1 << BagType::IfElse as u32);
const ALLOWED_BAG_IN_LB_NOT: u32 = (1 << BagType::Option as u32)
| (1 << BagType::StopBacktrack as u32)
| (1 << BagType::IfElse as u32);
// Allowed anchor types in positive/negative lookbehind
const ALLOWED_ANCHOR_IN_LB: i32 = ANCR_LOOK_BEHIND
| ANCR_BEGIN_LINE
| ANCR_END_LINE
| ANCR_BEGIN_BUF
| ANCR_BEGIN_POSITION
| ANCR_WORD_BOUNDARY
| ANCR_NO_WORD_BOUNDARY
| ANCR_WORD_BEGIN
| ANCR_WORD_END
| ANCR_TEXT_SEGMENT_BOUNDARY
| ANCR_NO_TEXT_SEGMENT_BOUNDARY;
const ALLOWED_ANCHOR_IN_LB_NOT: i32 = ANCR_LOOK_BEHIND
| ANCR_LOOK_BEHIND_NOT
| ANCR_BEGIN_LINE
| ANCR_END_LINE
| ANCR_BEGIN_BUF
| ANCR_BEGIN_POSITION
| ANCR_WORD_BOUNDARY
| ANCR_NO_WORD_BOUNDARY
| ANCR_WORD_BEGIN
| ANCR_WORD_END
| ANCR_TEXT_SEGMENT_BOUNDARY
| ANCR_NO_TEXT_SEGMENT_BOUNDARY;
/// Check if node tree is valid within a lookbehind call target.
/// Returns 0 = ok, 1 = forbidden.
fn check_called_node_in_look_behind(node: &Node, _not: bool) -> i32 {
match &node.inner {
NodeInner::List(cons) | NodeInner::Alt(cons) => {
let mut r = check_called_node_in_look_behind(&cons.car, _not);
if r == 0 {
if let Some(ref cdr) = cons.cdr {
r = check_called_node_in_look_behind(cdr, _not);
}
}
r
}
NodeInner::Quant(qn) => {
if let Some(ref body) = qn.body {
check_called_node_in_look_behind(body, _not)
} else {
0
}
}
NodeInner::Bag(en) => {
if en.bag_type == BagType::Memory {
if node.has_status(ND_ST_MARK1) {
return 0;
}
// Note: can't mutate here to add MARK1, but recursion cycles are
// already broken by tune_call. Just check the body.
if let Some(ref body) = en.body {
return check_called_node_in_look_behind(body, _not);
}
0
} else {
let mut r = 0;
if let Some(ref body) = en.body {
r = check_called_node_in_look_behind(body, _not);
}
if r == 0 {
if let BagData::IfElse {
ref then_node,
ref else_node,
} = en.bag_data
{
if let Some(ref tn) = then_node {
r = check_called_node_in_look_behind(tn, _not);
if r != 0 {
return r;
}
}
if let Some(ref en) = else_node {
r = check_called_node_in_look_behind(en, _not);
}
}
}
r
}
}
NodeInner::Anchor(an) => {
if let Some(ref body) = an.body {
check_called_node_in_look_behind(body, _not)
} else {
0
}
}
NodeInner::Gimmick(_) => {
if node.has_status(ND_ST_ABSENT_WITH_SIDE_EFFECTS) {
1
} else {
0
}
}
_ => 0,
}
}
/// Full validation of nodes in lookbehind. Returns 0 = ok, 1 = forbidden.
/// `not`: true for negative lookbehind.
/// `used`: set to true if the body contains backrefs, called groups, or SAVE_KEEP.
fn check_node_in_look_behind(
node: &Node,
not: bool,
used: &mut bool,
syntax: &OnigSyntaxType,
) -> i32 {
let type_bit = node.node_type_bit();
if (type_bit & ALLOWED_TYPE_IN_LB) == 0 {
return 1;
}
match &node.inner {
NodeInner::List(cons) | NodeInner::Alt(cons) => {
let mut r = check_node_in_look_behind(&cons.car, not, used, syntax);
if r == 0 {
if let Some(ref cdr) = cons.cdr {
r = check_node_in_look_behind(cdr, not, used, syntax);
}
}
r
}
NodeInner::Quant(qn) => {
if let Some(ref body) = qn.body {
check_node_in_look_behind(body, not, used, syntax)
} else {
0
}
}
NodeInner::Bag(en) => {
let mut bag_mask = if not {
ALLOWED_BAG_IN_LB_NOT
} else {
ALLOWED_BAG_IN_LB
};
if not && is_syntax_bv(syntax, FERRONI_SYN_ALLOW_CAPTURE_IN_NEGATIVE_LOOK_BEHIND) {
bag_mask |= 1 << BagType::Memory as u32;
}
if ((1 << en.bag_type as u32) & bag_mask) == 0 {
return 1;
}
let mut r = 0;
if let Some(ref body) = en.body {
r = check_node_in_look_behind(body, not, used, syntax);
if r != 0 {
return r;
}
}
if en.bag_type == BagType::Memory {
if node.has_status(ND_ST_BACKREF)
|| node.has_status(ND_ST_CALLED)
|| node.has_status(ND_ST_REFERENCED)
{
*used = true;
}
} else if let BagData::IfElse {
ref then_node,
ref else_node,
} = en.bag_data
{
if let Some(ref tn) = then_node {
r = check_node_in_look_behind(tn, not, used, syntax);
if r != 0 {
return r;
}
}
if let Some(ref en) = else_node {
r = check_node_in_look_behind(en, not, used, syntax);
}
}
r
}
NodeInner::Anchor(an) => {
let mut anchor_mask = if not {
ALLOWED_ANCHOR_IN_LB_NOT
} else {
ALLOWED_ANCHOR_IN_LB
};
if not && is_syntax_bv(syntax, FERRONI_SYN_ALLOW_LOOK_AHEAD_IN_NEGATIVE_LOOK_BEHIND) {
anchor_mask |= ANCR_PREC_READ | ANCR_PREC_READ_NOT;
}
if (an.anchor_type & anchor_mask) == 0 {
return 1;
}
if let Some(ref body) = an.body {
check_node_in_look_behind(body, not, used, syntax)
} else {
0
}
}
NodeInner::Call(ref cn) => {
if node.has_status(ND_ST_RECURSION) {
*used = true;
0
} else if !cn.target_node.is_null() {
// SAFETY: `target_node` is non-null (checked above) and was set by
// resolve_call_references/refresh_call_targets to the called group's
// Bag node inside this same live tree; only shared reads follow.
let target = unsafe { &*cn.target_node };
check_called_node_in_look_behind(target, not)
} else {
0
}
}
NodeInner::Gimmick(ref gn) => {
if node.has_status(ND_ST_ABSENT_WITH_SIDE_EFFECTS) {
return 1;
}
if gn.gimmick_type == GimmickType::Save && gn.detail_type == SaveType::Keep as i32 {
*used = true;
}
0
}
_ => 0,
}
}
/// Reduce quantifiers in lookbehind: set upper = lower for simple body quantifiers.
/// C: node_reduce_in_look_behind — returns true if node should be removed (upper==0).
fn node_reduce_in_look_behind(node: &mut Node) -> bool {
if let NodeInner::Quant(ref mut qn) = node.inner {
if let Some(ref body) = qn.body {
let reducible = matches!(
body.inner,
NodeInner::String(_)
| NodeInner::CType(_)
| NodeInner::CClass(_)
| NodeInner::BackRef(_)
);
if reducible {
qn.upper = qn.lower;
return qn.upper == 0;
}
}
}
false
}
/// C: list_reduce_in_look_behind
fn list_reduce_in_look_behind(node: &mut Node) {
match node.inner {
NodeInner::Quant(_) => {
node_reduce_in_look_behind(node);
}
NodeInner::List(_) => {
// Walk the list, reducing each car
let mut cur = node as *mut Node;
loop {
// SAFETY: `cur` starts as the exclusive `&mut node` argument and is
// only advanced to the boxed cdr of the cons it points to, so it
// always points to a live node in the exclusively borrowed chain.
unsafe {
if let NodeInner::List(ref mut cons) = (*cur).inner {
let removed = node_reduce_in_look_behind(&mut cons.car);
if !removed {
// Only continue if the current node was reduced (removed)
// C: "if (r <= 0) break" — r>0 means removed, keep going
break;
}
if let Some(ref mut cdr) = cons.cdr {
cur = cdr.as_mut() as *mut Node;
} else {
break;
}
} else {
break;
}
}
}
}
_ => {}
}
}
/// C: alt_reduce_in_look_behind
fn alt_reduce_in_look_behind(node: &mut Node) {
match node.inner {
NodeInner::Alt(_) => {
let mut cur = node as *mut Node;
loop {
// SAFETY: `cur` starts as the exclusive `&mut node` argument and is
// only advanced to the boxed cdr of the cons it points to, so it
// always points to a live node in the exclusively borrowed chain.
unsafe {
if let NodeInner::Alt(ref mut cons) = (*cur).inner {
list_reduce_in_look_behind(&mut cons.car);
if let Some(ref mut cdr) = cons.cdr {
cur = cdr.as_mut() as *mut Node;
} else {
break;
}
} else {
break;
}
}
}
}
_ => {
list_reduce_in_look_behind(node);
}
}
}
/// Strip redundant multi-char case-fold alternatives from a CClass body in a lookbehind.
///
/// When `(?i)` is active, the parser wraps a CClass into `Alt(CClass, str1, str2, ...)`
/// where each string is a multi-char case fold (e.g., ß→"ss"). In a lookbehind, this
/// causes O(N) separate lookbehind anchors to be created, each costing ~7 ops.
///
/// If the last codepoint of every multi-char fold string is already in the CClass,
/// the multi-char alternatives are redundant: the single-char CClass check already
/// rejects/accepts those positions. We can safely collapse back to just the CClass.
fn strip_redundant_casefold_alts_in_lookbehind(node: &mut Node, enc: OnigEncoding) {
let body = if let NodeInner::Anchor(ref mut an) = node.inner {
if let Some(ref mut body) = an.body {
body
} else {
return;
}
} else {
return;
};
// Check if body is Alt(CClass, ...) — the pattern generated by case-fold expansion
let cc_ptr: *const CClassNode = if let NodeInner::Alt(ref cons) = body.inner {
if let NodeInner::CClass(ref cc) = cons.car.inner {
cc as *const CClassNode
} else {
return;
}
} else {
return;
};
// Walk the cdr chain and check each string alternative
let all_covered = {
// SAFETY: `cc_ptr` was taken just above from the CClass in the first Alt
// branch of `body`; the walk below only reads the chain and never mutates
// `body`, so the pointee stays live while `cc` is in use.
let cc = unsafe { &*cc_ptr };
let mut cur: &Node = body;
let mut has_alts = false;
let mut covered = true;
while let NodeInner::Alt(cons) = &cur.inner {
let next = match cons.cdr.as_deref() {
Some(node) => node,
None => break,
};
// Each node in the cdr chain is either another Alt or the last branch
let branch = if let NodeInner::Alt(ref cons2) = next.inner {
&cons2.car
} else {
// Last branch is the node itself
next
};
// Check if this branch is a String node (multi-char fold)
if let NodeInner::String(ref sn) = branch.inner {
if sn.s.is_empty() {
covered = false;
break;
}
has_alts = true;
// Decode the last codepoint from the string
let bytes = &sn.s;
let last_code = decode_last_codepoint(bytes, enc);
if !onig_is_code_in_cc(enc, last_code, cc) {
covered = false;
break;
}
} else {
// Non-string alternative — don't optimize
covered = false;
break;
}
// Move to next in chain
if let NodeInner::Alt(_) = next.inner {
cur = next;
} else {
break;
}
}
has_alts && covered
};
if all_covered {
// Collapse: replace Alt(CClass, str1, str2, ...) with just the CClass node
let old_inner = std::mem::replace(
&mut body.inner,
NodeInner::String(StrNode {
s: Vec::new(),
flag: 0,
}),
);
if let NodeInner::Alt(cons) = old_inner {
**body = *cons.car;
}
}
}
/// Decode the last codepoint from a UTF-8 byte slice.
fn decode_last_codepoint(bytes: &[u8], enc: OnigEncoding) -> OnigCodePoint {
if bytes.is_empty() {
return 0;
}
// Walk forward through the string to find the start of the last character
let mut pos = 0;
let mut last_pos = 0;
while pos < bytes.len() {
last_pos = pos;
let clen = enc.mbc_enc_len(&bytes[pos..]);
if clen == 0 {
break;
}
pos += clen;
}
enc.mbc_to_code(&bytes[last_pos..], bytes.len())
}
/// Tune a lookbehind anchor: compute char lengths and split variable-length alternatives.
fn tune_look_behind(node: &mut Node, enc: OnigEncoding, syntax: &OnigSyntaxType) -> i32 {
let (anchor_type, has_body) = if let NodeInner::Anchor(ref an) = node.inner {
(an.anchor_type, an.body.is_some())
} else {
return 0;
};
if !has_body {
return 0;
}
// Strip redundant multi-char case-fold alternatives from CClass in lookbehind.
//
// Under (?i), the parser expands a CClass like [-\w] into
// Alt(CClass[-\w...], "ss", "fi", "fl", ...)
// because characters like ß case-fold to "ss". In a lookbehind, this causes
// divide_look_behind_alt to create ~100 separate lookbehind anchors (one per
// multi-char fold), each with its own Mark/Push/StepBack/body/PopToMark/Fail/Pop.
//
// These multi-char alternatives are redundant when the last character of each
// fold sequence is already in the CClass. For [-\w], every multi-char fold of
// a word character ends with a word character (e.g., ß→"ss", fi→"fi"), so the
// single-char CClass check already covers all cases.
strip_redundant_casefold_alts_in_lookbehind(node, enc);
// Full validation of nodes inside lookbehind (C: check_node_in_look_behind)
let mut lb_used = false;
{
let is_not = anchor_type == ANCR_LOOK_BEHIND_NOT;
let body = if let NodeInner::Anchor(ref an) = node.inner {
an.body.as_ref().unwrap()
} else {
return 0;
};
let r = check_node_in_look_behind(body, is_not, &mut lb_used, syntax);
if r < 0 {
return r;
}
if r > 0 {
return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
}
}
let body_char_len = {
let body = if let NodeInner::Anchor(ref an) = node.inner {
an.body.as_ref().unwrap()
} else {
return 0;
};
node_char_len(body, enc)
};
// Overflow check (C: #177)
const LOOK_BEHIND_MAX_CHAR_LEN: OnigLen = 65535;
let (cmin, cmax) = match body_char_len {
CharLenResult::Fixed(n) => (n, n),
CharLenResult::Variable(mn, mx) => (mn, mx),
};
if (cmax != INFINITE_LEN && cmax > LOOK_BEHIND_MAX_CHAR_LEN) || cmin > LOOK_BEHIND_MAX_CHAR_LEN
{
return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
}
match body_char_len {
CharLenResult::Fixed(len) => {
if let NodeInner::Anchor(ref mut an) = node.inner {
an.char_min_len = len;
an.char_max_len = len;
}
ONIG_NORMAL
}
CharLenResult::Variable(min, max) => {
// Check if body is Alt with all branches individually fixed-length
// (C's CHAR_LEN_TOP_ALT_FIXED case)
let top_alt_fixed = if let NodeInner::Anchor(ref an) = node.inner {
if let Some(ref body) = an.body {
is_alt_all_branches_fixed(body, enc)
} else {
false
}
} else {
false
};
if top_alt_fixed {
// All alt branches are fixed-length, just different sizes
if is_syntax_bv(syntax, ONIG_SYN_DIFFERENT_LEN_ALT_LOOK_BEHIND) {
let r = divide_look_behind_alt(node, anchor_type, enc);
if r == ONIG_NORMAL {
return r;
}
// Should not fail here since we checked all branches are fixed
}
// Fall through to variable-length path
if is_syntax_bv(syntax, ONIG_SYN_VARIABLE_LEN_LOOK_BEHIND) {
if min == INFINITE_LEN {
return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
}
if let NodeInner::Anchor(ref mut an) = node.inner {
an.char_min_len = min;
an.char_max_len = max;
}
ONIG_NORMAL
} else {
ONIGERR_INVALID_LOOK_BEHIND_PATTERN
}
} else {
// Either non-alt body, or alt with variable-length branches
if !is_syntax_bv(syntax, ONIG_SYN_VARIABLE_LEN_LOOK_BEHIND) {
return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
}
if min == INFINITE_LEN {
return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
}
if let NodeInner::Anchor(ref mut an) = node.inner {
an.char_min_len = min;
an.char_max_len = max;
}
ONIG_NORMAL
}
}
}
}
/// Resolve all \g<name>/\g<num> call references in the tree.
/// Sets called_gnum on Call nodes and marks target groups as CALLED.
fn resolve_call_references(node: &mut Node, reg: &mut RegexType, env: &mut ParseEnv) -> i32 {
match &mut node.inner {
NodeInner::Call(call) => {
// Resolve the call target
let mem_node_ptr;
if call.by_number {
let gnum = call.called_gnum;
if gnum > env.num_mem || gnum < 0 {
return ONIGERR_UNDEFINED_GROUP_REFERENCE;
}
mem_node_ptr = env.mem_env(gnum as usize).mem_node;
} else {
// Named call - look up name
let name = call.name.clone();
if let Some(ref nt) = reg.name_table {
if let Some(nums) = nt.name_to_group_numbers(&name) {
if nums.len() != 1 {
return ONIGERR_MULTIPLEX_DEFINITION_NAME_CALL;
}
call.called_gnum = nums[0];
mem_node_ptr = env.mem_env(nums[0] as usize).mem_node;
} else {
return ONIGERR_UNDEFINED_NAME_REFERENCE;
}
} else {
return ONIGERR_UNDEFINED_NAME_REFERENCE;
}
}
// Link the call node to its target (so recursive_call_check can follow calls)
// Note: we store the raw pointer as a non-owning reference (the target node
// is owned by the tree, not by this call). We wrap it in Box without ownership.
if !mem_node_ptr.is_null() {
// Store target pointer for recursion detection (not owning)
call.target_node = mem_node_ptr;
}
0
}
NodeInner::List(cons) | NodeInner::Alt(cons) => {
let r = resolve_call_references(&mut cons.car, reg, env);
if r != 0 {
return r;
}
if let Some(ref mut cdr) = cons.cdr {
resolve_call_references(cdr, reg, env)
} else {
0
}
}
NodeInner::Quant(qn) => {
if let Some(ref mut body) = qn.body {
resolve_call_references(body, reg, env)
} else {
0
}
}
NodeInner::Bag(bn) => {
if let Some(ref mut body) = bn.body {
let r = resolve_call_references(body, reg, env);
if r != 0 {
return r;
}
}
if let BagData::IfElse {
ref mut then_node,
ref mut else_node,
} = bn.bag_data
{
if let Some(ref mut then_n) = then_node {
let r = resolve_call_references(then_n, reg, env);
if r != 0 {
return r;
}
}
if let Some(ref mut else_n) = else_node {
let r = resolve_call_references(else_n, reg, env);
if r != 0 {
return r;
}
}
}
0
}
NodeInner::Anchor(an) => {
if let Some(ref mut body) = an.body {
resolve_call_references(body, reg, env)
} else {
0
}
}
_ => 0,
}
}
fn collect_called_groups(node: &Node, groups: &mut Vec<i32>) {
match &node.inner {
NodeInner::Call(call) => groups.push(call.called_gnum),
NodeInner::List(cons) | NodeInner::Alt(cons) => {
collect_called_groups(&cons.car, groups);
if let Some(cdr) = &cons.cdr {
collect_called_groups(cdr, groups);
}
}
NodeInner::Quant(qn) => {
if let Some(body) = &qn.body {
collect_called_groups(body, groups);
}
}
NodeInner::Bag(bn) => {
if let Some(body) = &bn.body {
collect_called_groups(body, groups);
}
if let BagData::IfElse {
then_node,
else_node,
} = &bn.bag_data
{
if let Some(then_node) = then_node {
collect_called_groups(then_node, groups);
}
if let Some(else_node) = else_node {
collect_called_groups(else_node, groups);
}
}
}
NodeInner::Anchor(an) => {
if let Some(body) = &an.body {
collect_called_groups(body, groups);
}
}
_ => {}
}
}
fn mark_called_groups(node: &mut Node, groups: &[i32]) {
if let NodeInner::Bag(bn) = &node.inner {
if bn.bag_type == BagType::Memory && groups.contains(&bn.regnum()) {
node.status_add(ND_ST_CALLED);
}
}
match &mut node.inner {
NodeInner::List(cons) | NodeInner::Alt(cons) => {
mark_called_groups(&mut cons.car, groups);
if let Some(cdr) = &mut cons.cdr {
mark_called_groups(cdr, groups);
}
}
NodeInner::Quant(qn) => {
if let Some(body) = &mut qn.body {
mark_called_groups(body, groups);
}
}
NodeInner::Bag(bn) => {
if let Some(body) = &mut bn.body {
mark_called_groups(body, groups);
}
if let BagData::IfElse {
then_node,
else_node,
} = &mut bn.bag_data
{
if let Some(then_node) = then_node {
mark_called_groups(then_node, groups);
}
if let Some(else_node) = else_node {
mark_called_groups(else_node, groups);
}
}
}
NodeInner::Anchor(an) => {
if let Some(body) = &mut an.body {
mark_called_groups(body, groups);
}
}
_ => {}
}
}
fn mark_called_groups_as_multi_entry(node: &mut Node) {
let is_called = node.has_status(ND_ST_CALLED);
match &mut node.inner {
NodeInner::List(cons) | NodeInner::Alt(cons) => {
mark_called_groups_as_multi_entry(&mut cons.car);
if let Some(cdr) = &mut cons.cdr {
mark_called_groups_as_multi_entry(cdr);
}
}
NodeInner::Quant(qn) => {
if let Some(body) = &mut qn.body {
mark_called_groups_as_multi_entry(body);
}
}
NodeInner::Bag(bn) => {
if bn.bag_type == BagType::Memory && is_called {
if let BagData::Memory { entry_count, .. } = &mut bn.bag_data {
// A call graph can enter a group through recursive paths that
// are not representable as a single tree borrow. Treating every
// called group as multi-entry is conservative: it only disables
// single-entry optimizations while keeping traversal alias-free.
*entry_count = (*entry_count).max(2);
}
}
if let Some(body) = &mut bn.body {
mark_called_groups_as_multi_entry(body);
}
if let BagData::IfElse {
then_node,
else_node,
} = &mut bn.bag_data
{
if let Some(then_node) = then_node {
mark_called_groups_as_multi_entry(then_node);
}
if let Some(else_node) = else_node {
mark_called_groups_as_multi_entry(else_node);
}
}
}
NodeInner::Anchor(an) => {
if let Some(body) = &mut an.body {
mark_called_groups_as_multi_entry(body);
}
}
_ => {}
}
}
fn collect_call_edges(node: &Node, current_groups: &mut Vec<usize>, edges: &mut [Vec<usize>]) {
match &node.inner {
NodeInner::Call(call) => {
let target = call.called_gnum as usize;
if target < edges.len() {
for &group in current_groups.iter() {
edges[group].push(target);
}
}
}
NodeInner::List(cons) | NodeInner::Alt(cons) => {
collect_call_edges(&cons.car, current_groups, edges);
if let Some(cdr) = &cons.cdr {
collect_call_edges(cdr, current_groups, edges);
}
}
NodeInner::Quant(qn) => {
if let Some(body) = &qn.body {
collect_call_edges(body, current_groups, edges);
}
}
NodeInner::Bag(bn) => {
let is_memory = bn.bag_type == BagType::Memory;
if is_memory {
let group = bn.regnum() as usize;
for &parent in current_groups.iter() {
if parent != group {
edges[parent].push(group);
}
}
current_groups.push(group);
}
if let Some(body) = &bn.body {
collect_call_edges(body, current_groups, edges);
}
if let BagData::IfElse {
then_node,
else_node,
} = &bn.bag_data
{
if let Some(then_node) = then_node {
collect_call_edges(then_node, current_groups, edges);
}
if let Some(else_node) = else_node {
collect_call_edges(else_node, current_groups, edges);
}
}
if is_memory {
current_groups.pop();
}
}
NodeInner::Anchor(an) => {
if let Some(body) = &an.body {
collect_call_edges(body, current_groups, edges);
}
}
_ => {}
}
}
fn reaches_group(edges: &[Vec<usize>], from: usize, target: usize, seen: &mut [bool]) -> bool {
if from == target {
return true;
}
if seen[from] {
return false;
}
seen[from] = true;
edges[from]
.iter()
.copied()
.any(|next| reaches_group(edges, next, target, seen))
}
fn node_contains_called_group(node: &Node) -> bool {
if node.has_status(ND_ST_CALLED) {
return true;
}
match &node.inner {
NodeInner::List(cons) | NodeInner::Alt(cons) => {
node_contains_called_group(&cons.car)
|| cons.cdr.as_deref().is_some_and(node_contains_called_group)
}
NodeInner::Quant(qn) => qn.body.as_deref().is_some_and(node_contains_called_group),
NodeInner::Bag(bn) => {
bn.body.as_deref().is_some_and(node_contains_called_group)
|| match &bn.bag_data {
BagData::IfElse {
then_node,
else_node,
} => {
then_node.as_deref().is_some_and(node_contains_called_group)
|| else_node.as_deref().is_some_and(node_contains_called_group)
}
_ => false,
}
}
NodeInner::Anchor(an) => an.body.as_deref().is_some_and(node_contains_called_group),
_ => false,
}
}
fn apply_call_graph_state(
node: &mut Node,
current_groups: &mut Vec<usize>,
edges: &[Vec<usize>],
recursive: &[bool],
env: &mut ParseEnv,
) {
let mut recursive_group = None;
match &mut node.inner {
NodeInner::List(cons) | NodeInner::Alt(cons) => {
apply_call_graph_state(&mut cons.car, current_groups, edges, recursive, env);
if let Some(cdr) = &mut cons.cdr {
apply_call_graph_state(cdr, current_groups, edges, recursive, env);
}
}
NodeInner::Quant(qn) => {
if qn.upper == 0 && qn.body.as_deref().is_some_and(node_contains_called_group) {
qn.include_referred = 1;
}
if let Some(body) = &mut qn.body {
apply_call_graph_state(body, current_groups, edges, recursive, env);
}
}
NodeInner::Bag(bn) => {
let is_memory = bn.bag_type == BagType::Memory;
if is_memory {
let regnum = bn.regnum() as usize;
if recursive.get(regnum).copied().unwrap_or(false) {
recursive_group = Some(regnum);
}
current_groups.push(regnum);
}
if let Some(body) = &mut bn.body {
apply_call_graph_state(body, current_groups, edges, recursive, env);
}
if let BagData::IfElse {
then_node,
else_node,
} = &mut bn.bag_data
{
if let Some(then_node) = then_node {
apply_call_graph_state(then_node, current_groups, edges, recursive, env);
}
if let Some(else_node) = else_node {
apply_call_graph_state(else_node, current_groups, edges, recursive, env);
}
}
if is_memory {
current_groups.pop();
}
}
NodeInner::Anchor(an) => {
if let Some(body) = &mut an.body {
apply_call_graph_state(body, current_groups, edges, recursive, env);
}
}
NodeInner::Call(call) => {
let target = call.called_gnum as usize;
if target < edges.len()
&& current_groups.iter().copied().any(|group| {
let mut seen = vec![false; edges.len()];
reaches_group(edges, target, group, &mut seen)
})
{
node.status_add(ND_ST_RECURSION);
}
}
_ => {}
}
if let Some(regnum) = recursive_group {
node.status_add(ND_ST_RECURSION);
env.backtrack_mem |= 1u32 << regnum;
}
}
fn analyze_call_graph(root: &mut Node, env: &mut ParseEnv) -> Vec<bool> {
let mut edges = vec![Vec::new(); env.num_mem.max(0) as usize + 1];
let mut current_groups = vec![0];
collect_call_edges(root, &mut current_groups, &mut edges);
let recursive = (0..edges.len())
.map(|group| {
edges[group].iter().copied().any(|next| {
let mut seen = vec![false; edges.len()];
reaches_group(&edges, next, group, &mut seen)
})
})
.collect::<Vec<_>>();
apply_call_graph_state(root, &mut current_groups, &edges, &recursive, env);
recursive
}
fn must_recurse_without_consuming(node: &Node, must_recurse: &[bool], env: &ParseEnv) -> bool {
match &node.inner {
NodeInner::List(cons) => {
let mut cur = node;
while let NodeInner::List(cons) = &cur.inner {
if must_recurse_without_consuming(&cons.car, must_recurse, env) {
return true;
}
if node_min_byte_len(&cons.car, env) != 0 {
return false;
}
match &cons.cdr {
Some(cdr) => cur = cdr,
None => break,
}
}
false
}
NodeInner::Alt(cons) => {
let mut cur = node;
while let NodeInner::Alt(cons) = &cur.inner {
if !must_recurse_without_consuming(&cons.car, must_recurse, env) {
return false;
}
match &cons.cdr {
Some(cdr) => cur = cdr,
None => break,
}
}
true
}
NodeInner::Quant(qn) => {
qn.lower != 0
&& qn
.body
.as_deref()
.is_some_and(|body| must_recurse_without_consuming(body, must_recurse, env))
}
NodeInner::Bag(bn) => {
if let Some(body) = &bn.body {
if must_recurse_without_consuming(body, must_recurse, env) {
return true;
}
if node_min_byte_len(body, env) != 0 {
return false;
}
}
match &bn.bag_data {
BagData::IfElse {
then_node,
else_node,
} => {
then_node.as_deref().is_some_and(|then_node| {
must_recurse_without_consuming(then_node, must_recurse, env)
}) && else_node.as_deref().map_or(true, |else_node| {
must_recurse_without_consuming(else_node, must_recurse, env)
})
}
_ => false,
}
}
NodeInner::Anchor(an) => an
.body
.as_deref()
.is_some_and(|body| must_recurse_without_consuming(body, must_recurse, env)),
NodeInner::Call(call) => must_recurse
.get(call.called_gnum as usize)
.copied()
.unwrap_or(false),
_ => false,
}
}
fn update_must_recurse_groups(
node: &Node,
recursive: &[bool],
current: &[bool],
next: &mut [bool],
env: &ParseEnv,
) {
match &node.inner {
NodeInner::List(cons) | NodeInner::Alt(cons) => {
update_must_recurse_groups(&cons.car, recursive, current, next, env);
if let Some(cdr) = &cons.cdr {
update_must_recurse_groups(cdr, recursive, current, next, env);
}
}
NodeInner::Quant(qn) => {
if let Some(body) = &qn.body {
update_must_recurse_groups(body, recursive, current, next, env);
}
}
NodeInner::Bag(bn) => {
if bn.bag_type == BagType::Memory {
let regnum = bn.regnum() as usize;
if recursive.get(regnum).copied().unwrap_or(false) {
next[regnum] = bn
.body
.as_deref()
.is_some_and(|body| must_recurse_without_consuming(body, current, env));
}
}
if let Some(body) = &bn.body {
update_must_recurse_groups(body, recursive, current, next, env);
}
if let BagData::IfElse {
then_node,
else_node,
} = &bn.bag_data
{
if let Some(then_node) = then_node {
update_must_recurse_groups(then_node, recursive, current, next, env);
}
if let Some(else_node) = else_node {
update_must_recurse_groups(else_node, recursive, current, next, env);
}
}
}
NodeInner::Anchor(an) => {
if let Some(body) = &an.body {
update_must_recurse_groups(body, recursive, current, next, env);
}
}
_ => {}
}
}
fn analyze_must_recurse_groups(root: &Node, recursive: &[bool], env: &ParseEnv) -> Vec<bool> {
let mut current = recursive.to_vec();
loop {
let mut next = current.clone();
update_must_recurse_groups(root, recursive, ¤t, &mut next, env);
if next == current {
return current;
}
current = next;
}
}
fn has_never_ending_recursion(node: &Node, recursive: &[bool], must_recurse: &[bool]) -> bool {
match &node.inner {
NodeInner::List(cons) | NodeInner::Alt(cons) => {
has_never_ending_recursion(&cons.car, recursive, must_recurse)
|| cons
.cdr
.as_deref()
.is_some_and(|cdr| has_never_ending_recursion(cdr, recursive, must_recurse))
}
NodeInner::Quant(qn) => qn
.body
.as_deref()
.is_some_and(|body| has_never_ending_recursion(body, recursive, must_recurse)),
NodeInner::Bag(bn) => {
let regnum = bn.regnum() as usize;
let recursive_memory = bn.bag_type == BagType::Memory
&& recursive.get(regnum).copied().unwrap_or(false)
&& node.has_status(ND_ST_CALLED)
&& must_recurse.get(regnum).copied().unwrap_or(false);
recursive_memory
|| bn
.body
.as_deref()
.is_some_and(|body| has_never_ending_recursion(body, recursive, must_recurse))
|| match &bn.bag_data {
BagData::IfElse {
then_node,
else_node,
} => {
then_node.as_deref().is_some_and(|node| {
has_never_ending_recursion(node, recursive, must_recurse)
}) || else_node.as_deref().is_some_and(|node| {
has_never_ending_recursion(node, recursive, must_recurse)
})
}
_ => false,
}
}
NodeInner::Anchor(an) => an
.body
.as_deref()
.is_some_and(|body| has_never_ending_recursion(body, recursive, must_recurse)),
_ => false,
}
}
// ============================================================================
// disable_noname_group_capture — CAPTURE_ONLY_NAMED_GROUP support
// When syntax has this flag and named groups exist, unnamed groups become
// non-capturing and group numbers are renumbered to only include named groups.
// ============================================================================
/// Traverse tree: assign new sequential numbers to named groups, remove unnamed BAG_MEMORY.
/// Returns 1 when node was replaced (parent may need to reduce nested quantifiers).
fn make_named_capture_number_map(
node: &mut Node,
map: &mut [GroupNumMap],
counter: &mut i32,
) -> i32 {
let node_type = node.node_type();
match node_type {
NodeType::List | NodeType::Alt => {
let cur = node as *mut Node;
// SAFETY: `p` starts as the exclusive `&mut node` argument and only
// advances to the boxed cdr, so every deref is of a live node; `car`
// and `cdr` are disjoint fields, so recursing into car while holding
// the cdr pointer creates no overlapping &mut (this pass follows no
// call targets).
unsafe {
let mut p = cur;
while let NodeInner::List(ref mut cons) | NodeInner::Alt(ref mut cons) = (*p).inner
{
let car_ptr = &mut *cons.car as *mut Node;
let cdr_opt = cons.cdr.as_mut().map(|c| &mut **c as *mut Node);
let r = make_named_capture_number_map(&mut *car_ptr, map, counter);
if r < 0 {
return r;
}
match cdr_opt {
Some(next) => p = next,
None => break,
}
}
}
0
}
NodeType::Quant => {
let body_ptr: Option<*mut Node> = if let NodeInner::Quant(ref mut qn) = node.inner {
qn.body.as_mut().map(|b| &mut **b as *mut Node)
} else {
None
};
if let Some(bp) = body_ptr {
// SAFETY: `bp` points to the quantifier's boxed body, extracted above
// to end the borrow of `node.inner`; no other reference to the body
// exists during the call.
let r = unsafe { make_named_capture_number_map(&mut *bp, map, counter) };
if r < 0 {
return r;
}
// If node was replaced and became a quantifier, could reduce nested quantifiers
// (rare case, skip for now like C's onig_reduce_nested_quantifier)
}
0
}
NodeType::Bag => {
let is_memory =
matches!(&node.inner, NodeInner::Bag(ref bn) if bn.bag_type == BagType::Memory);
let is_named = node.has_status(ND_ST_NAMED_GROUP);
if is_memory && !is_named {
// Unnamed group — remove bag wrapper, replace node with its body
let body = if let NodeInner::Bag(ref mut bn) = node.inner {
bn.body.take()
} else {
None
};
if let Some(body) = body {
let body = *body;
node.inner = body.inner;
node.status = body.status;
} else {
node.inner = NodeInner::String(StrNode {
s: Vec::new(),
flag: 0,
});
}
let r = make_named_capture_number_map(node, map, counter);
if r < 0 {
return r;
}
return 1;
}
if is_memory && is_named {
if let NodeInner::Bag(ref mut bn) = node.inner {
*counter += 1;
if let BagData::Memory { ref mut regnum, .. } = bn.bag_data {
map[*regnum as usize].new_val = *counter;
*regnum = *counter;
}
if let Some(ref mut body) = bn.body {
let r = make_named_capture_number_map(body, map, counter);
if r < 0 {
return r;
}
}
}
return 0;
}
// IfElse or other bag types
// SAFETY: `node_ptr` is the exclusive `&mut node` argument; plain
// reborrow used to recurse into the bag's children.
unsafe {
let node_ptr = node as *mut Node;
if let NodeInner::Bag(ref mut bn) = (*node_ptr).inner {
if bn.bag_type == BagType::IfElse {
if let Some(ref mut body) = bn.body {
let r = make_named_capture_number_map(body, map, counter);
if r < 0 {
return r;
}
}
if let BagData::IfElse {
ref mut then_node,
ref mut else_node,
} = bn.bag_data
{
if let Some(ref mut tn) = then_node {
let r = make_named_capture_number_map(tn, map, counter);
if r < 0 {
return r;
}
}
if let Some(ref mut en) = else_node {
let r = make_named_capture_number_map(en, map, counter);
if r < 0 {
return r;
}
}
}
} else {
if let Some(ref mut body) = bn.body {
let r = make_named_capture_number_map(body, map, counter);
if r < 0 {
return r;
}
}
}
}
}
0
}
NodeType::Anchor => {
if let NodeInner::Anchor(ref mut a) = node.inner {
if let Some(ref mut body) = a.body {
let r = make_named_capture_number_map(body, map, counter);
if r < 0 {
return r;
}
}
}
0
}
_ => 0,
}
}
/// Renumber backrefs in a single backref node using the group number map.
fn renumber_backref_node(node: &mut Node, map: &[GroupNumMap]) -> i32 {
if !node.has_status(ND_ST_BY_NAME) {
return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
}
if let NodeInner::BackRef(ref mut br) = node.inner {
let old_num = br.back_num as usize;
let mut pos = 0usize;
if let Some(ref mut dyn_refs) = br.back_dynamic {
for i in 0..old_num {
let n = map[dyn_refs[i] as usize].new_val;
if n > 0 {
dyn_refs[pos] = n;
pos += 1;
}
}
} else {
for i in 0..old_num {
let n = map[br.back_static[i] as usize].new_val;
if n > 0 {
br.back_static[pos] = n;
pos += 1;
}
}
}
br.back_num = pos as i32;
}
0
}
/// Traverse tree to renumber all backrefs using the group number map.
fn renumber_backref_traverse(node: &mut Node, map: &[GroupNumMap]) -> i32 {
match node.node_type() {
NodeType::List | NodeType::Alt => {
let cur = node as *mut Node;
// SAFETY: `p` starts as the exclusive `&mut node` argument and only
// advances to the boxed cdr, so every deref is of a live node; `car`
// and `cdr` are disjoint fields, so recursing into car while holding
// the cdr pointer creates no overlapping &mut (this pass follows no
// call targets).
unsafe {
let mut p = cur;
while let NodeInner::List(ref mut cons) | NodeInner::Alt(ref mut cons) =
&mut (*p).inner
{
let car_ptr = &mut *cons.car as *mut Node;
let cdr_opt = cons.cdr.as_mut().map(|c| &mut **c as *mut Node);
let r = renumber_backref_traverse(&mut *car_ptr, map);
if r != 0 {
return r;
}
match cdr_opt {
Some(next) => {
p = next;
}
None => break,
}
}
}
0
}
NodeType::Quant => {
if let NodeInner::Quant(ref mut qn) = node.inner {
if let Some(ref mut body) = qn.body {
return renumber_backref_traverse(body, map);
}
}
0
}
NodeType::Bag => {
// SAFETY: `node_ptr` is the exclusive `&mut node` argument; plain
// reborrow used to recurse into the bag's children.
unsafe {
let node_ptr = node as *mut Node;
if let NodeInner::Bag(ref mut bn) = (*node_ptr).inner {
if let Some(ref mut body) = bn.body {
let r = renumber_backref_traverse(body, map);
if r != 0 {
return r;
}
}
if bn.bag_type == BagType::IfElse {
if let BagData::IfElse {
ref mut then_node,
ref mut else_node,
} = bn.bag_data
{
if let Some(ref mut tn) = then_node {
let r = renumber_backref_traverse(tn, map);
if r != 0 {
return r;
}
}
if let Some(ref mut en) = else_node {
let r = renumber_backref_traverse(en, map);
if r != 0 {
return r;
}
}
}
}
}
}
0
}
NodeType::BackRef => renumber_backref_node(node, map),
NodeType::Anchor => {
if let NodeInner::Anchor(ref mut a) = node.inner {
if let Some(ref mut body) = a.body {
return renumber_backref_traverse(body, map);
}
}
0
}
_ => 0,
}
}
/// Check that no numbered (non-named) backrefs exist in the tree.
/// Called when all captures are named (num_named == num_mem).
fn numbered_ref_check(node: &Node) -> i32 {
match &node.inner {
NodeInner::List(cons) | NodeInner::Alt(cons) => {
let r = numbered_ref_check(&cons.car);
if r != 0 {
return r;
}
if let Some(ref next) = cons.cdr {
return numbered_ref_check(next);
}
0
}
NodeInner::Quant(ref qn) => {
if let Some(ref body) = qn.body {
numbered_ref_check(body)
} else {
0
}
}
NodeInner::Anchor(ref a) => {
if let Some(ref body) = a.body {
numbered_ref_check(body)
} else {
0
}
}
NodeInner::Bag(ref bn) => {
if let Some(ref body) = bn.body {
let r = numbered_ref_check(body);
if r != 0 {
return r;
}
}
if bn.bag_type == BagType::IfElse {
if let BagData::IfElse {
ref then_node,
ref else_node,
} = bn.bag_data
{
if let Some(ref tn) = then_node {
let r = numbered_ref_check(tn);
if r != 0 {
return r;
}
}
if let Some(ref en) = else_node {
let r = numbered_ref_check(en);
if r != 0 {
return r;
}
}
}
}
0
}
NodeInner::BackRef(_) => {
if !node.has_status(ND_ST_BY_NAME) {
ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED
} else {
0
}
}
_ => 0,
}
}
/// When CAPTURE_ONLY_NAMED_GROUP is active and both named and unnamed groups
/// exist, remove unnamed captures and renumber everything to only use named groups.
fn disable_noname_group_capture(root: &mut Node, reg: &mut RegexType, env: &mut ParseEnv) -> i32 {
let num_mem = env.num_mem as usize;
let mut map: Vec<GroupNumMap> = (0..=num_mem).map(|_| GroupNumMap { new_val: 0 }).collect();
let mut counter: i32 = 0;
let r = make_named_capture_number_map(root, &mut map, &mut counter);
if r < 0 {
return r;
}
let r = renumber_backref_traverse(root, &map);
if r != 0 {
return r;
}
// Compact mem_env: shift named entries down to fill gaps left by removed unnamed groups
let mut pos: usize = 1;
for (i, map_entry) in map.iter().enumerate().skip(1).take(num_mem) {
if map_entry.new_val > 0 {
if pos != i {
let src_node = env.mem_env(i).mem_node;
let src_empty = env.mem_env(i).empty_repeat_node;
let dst = env.mem_env_mut(pos);
dst.mem_node = src_node;
dst.empty_repeat_node = src_empty;
}
pos += 1;
}
}
// Update cap_history bitmap with renumbered groups
let loc = env.cap_history;
env.cap_history = 0;
for (i, map_entry) in map
.iter()
.enumerate()
.skip(1)
.take(std::cmp::min(num_mem, 31))
{
if (loc & (1u32 << i)) != 0 {
let new_val = map_entry.new_val;
if new_val > 0 && new_val <= 31 {
env.cap_history |= 1u32 << (new_val as u32);
}
}
}
env.num_mem = env.num_named;
reg.num_mem = env.num_named;
// Renumber name table entries
if let Some(ref mut nt) = reg.name_table {
for entry in nt.entries.values_mut() {
for back_ref in entry.back_refs.iter_mut() {
let idx = *back_ref as usize;
if idx < map.len() {
*back_ref = map[idx].new_val;
}
}
}
}
0
}
// ============================================================================
// Call-node tuning: tune_call + tune_called_state
// ============================================================================
/// C: tune_call — mark zero-repeat contexts and adjust entry counts.
/// Call reference resolution is already handled by resolve_call_references.
fn tune_call(node: &mut Node, state: i32) {
let np = node as *mut Node;
// SAFETY: `np` is the exclusive `&mut node` argument; all derefs are
// reborrows of it or of boxed cdr nodes reached from it, and the raw
// pointer only serves to update `status` around borrows of `inner`
// (disjoint fields). This pass follows no call targets.
unsafe {
match &mut (*np).inner {
NodeInner::List(_) | NodeInner::Alt(_) => {
let mut cur = np;
while let NodeInner::List(c) | NodeInner::Alt(c) = &mut (*cur).inner {
tune_call(&mut c.car, state);
match &mut c.cdr {
Some(ref mut next) => cur = next.as_mut() as *mut Node,
None => break,
}
}
}
NodeInner::Quant(qn) => {
let s = if qn.upper == 0 {
state | IN_ZERO_REPEAT
} else {
state
};
if let Some(ref mut body) = qn.body {
tune_call(body, s);
}
}
NodeInner::Anchor(an) => {
if let Some(ref mut body) = an.body {
tune_call(body, state);
}
}
NodeInner::Bag(bn) => {
let bt = bn.bag_type;
if bt == BagType::Memory {
if (state & IN_ZERO_REPEAT) != 0 {
(*np).status_add(ND_ST_IN_ZERO_REPEAT);
if let NodeInner::Bag(ref mut bn) = (*np).inner {
if let BagData::Memory {
ref mut entry_count,
..
} = bn.bag_data
{
*entry_count -= 1;
}
if let Some(ref mut body) = bn.body {
tune_call(body, state);
}
}
} else if let Some(ref mut body) = bn.body {
tune_call(body, state);
}
} else if bt == BagType::IfElse {
if let Some(ref mut body) = bn.body {
tune_call(body, state);
}
if let BagData::IfElse {
ref mut then_node,
ref mut else_node,
} = bn.bag_data
{
if let Some(ref mut t) = then_node {
tune_call(t, state);
}
if let Some(ref mut e) = else_node {
tune_call(e, state);
}
}
} else if let Some(ref mut body) = bn.body {
tune_call(body, state);
}
}
NodeInner::Call(cn) => {
if (state & IN_ZERO_REPEAT) != 0 {
(*np).status_add(ND_ST_IN_ZERO_REPEAT);
cn.entry_count -= 1;
}
}
_ => {}
}
}
}
/// C: tune_called_state_call — propagate state flags through called nodes.
///
/// Internal compiler pass that propagates state bits (IN_ALT, IN_PEEK,
/// IN_REAL_REPEAT, etc.) through the call graph of subroutine-call nodes.
/// Only reachable when the pattern uses `\g<name>` or `(?R)` in specific
/// contexts. Tested indirectly through compat_utf8 suite.
#[cfg_attr(coverage_nightly, coverage(off))]
fn tune_called_state_call(node: &mut Node, state: i32) {
let np = node as *mut Node;
// SAFETY: `np` is the exclusive `&mut node` argument; derefs are reborrows
// of it or of boxed cdr nodes, and the raw pointer only updates `status`
// around borrows of `inner` (disjoint fields). Re-entry through call
// cycles is cut by the MARK1 guard on Bag Memory nodes.
unsafe {
match &mut (*np).inner {
NodeInner::Alt(_) => {
let s = state | IN_ALT;
let mut cur = np;
while let NodeInner::Alt(c) | NodeInner::List(c) = &mut (*cur).inner {
tune_called_state_call(&mut c.car, s);
match &mut c.cdr {
Some(ref mut next) => cur = next.as_mut() as *mut Node,
None => break,
}
}
}
NodeInner::List(_) => {
let mut cur = np;
while let NodeInner::List(c) | NodeInner::Alt(c) = &mut (*cur).inner {
tune_called_state_call(&mut c.car, state);
match &mut c.cdr {
Some(ref mut next) => cur = next.as_mut() as *mut Node,
None => break,
}
}
}
NodeInner::Quant(qn) => {
let mut s = state;
if is_infinite_repeat(qn.upper) || qn.upper >= 2 {
s |= IN_REAL_REPEAT;
}
if qn.lower != qn.upper {
s |= IN_VAR_REPEAT;
}
if (state & IN_PEEK) != 0 {
(*np).status_add(ND_ST_INPEEK);
}
if let Some(ref mut body) = qn.body {
tune_called_state_call(body, s);
}
}
NodeInner::Anchor(an) => match an.anchor_type {
ANCR_PREC_READ_NOT | ANCR_LOOK_BEHIND_NOT => {
if let Some(ref mut body) = an.body {
tune_called_state_call(body, state | IN_NOT | IN_PEEK);
}
}
ANCR_PREC_READ | ANCR_LOOK_BEHIND => {
if let Some(ref mut body) = an.body {
tune_called_state_call(body, state | IN_PEEK);
}
}
_ => {}
},
NodeInner::Bag(bn) => {
let bt = bn.bag_type;
if bt == BagType::Memory {
if (*np).has_status(ND_ST_MARK1) {
if let NodeInner::Bag(ref mut bn) = (*np).inner {
if let BagData::Memory {
ref mut called_state,
..
} = bn.bag_data
{
if (!*called_state & state) != 0 {
*called_state |= state;
if let Some(ref mut body) = bn.body {
tune_called_state_call(body, state);
}
}
}
}
} else {
(*np).status_add(ND_ST_MARK1);
if let NodeInner::Bag(ref mut bn) = (*np).inner {
if let BagData::Memory {
ref mut called_state,
..
} = bn.bag_data
{
*called_state |= state;
}
if let Some(ref mut body) = bn.body {
tune_called_state_call(body, state);
}
}
(*np).status_remove(ND_ST_MARK1);
}
} else if bt == BagType::IfElse {
let s = state | IN_ALT;
if let Some(ref mut body) = bn.body {
tune_called_state_call(body, s);
}
if let BagData::IfElse {
ref mut then_node,
ref mut else_node,
} = bn.bag_data
{
if let Some(ref mut t) = then_node {
tune_called_state_call(t, s);
}
if let Some(ref mut e) = else_node {
tune_called_state_call(e, s);
}
}
} else if let Some(ref mut body) = bn.body {
tune_called_state_call(body, state);
}
}
NodeInner::Call(cn) => {
if (state & IN_PEEK) != 0 {
(*np).status_add(ND_ST_INPEEK);
}
if (state & IN_REAL_REPEAT) != 0 {
(*np).status_add(ND_ST_IN_REAL_REPEAT);
}
if let Some(ref mut body) = cn.body {
tune_called_state_call(body, state);
}
}
_ => {}
}
}
}
/// C: tune_called_state — propagate state flags down the tree, entering called groups.
fn tune_called_state(node: &mut Node, state: i32) {
let np = node as *mut Node;
// SAFETY: `np` is the exclusive `&mut node` argument; all derefs are
// reborrows of it or of boxed cdr nodes reached from it. Called groups are
// entered only through tune_called_state_call, which guards call cycles
// with MARK1.
unsafe {
match &mut (*np).inner {
NodeInner::Alt(_) => {
let s = state | IN_ALT;
let mut cur = np;
while let NodeInner::Alt(c) | NodeInner::List(c) = &mut (*cur).inner {
tune_called_state(&mut c.car, s);
match &mut c.cdr {
Some(ref mut next) => cur = next.as_mut() as *mut Node,
None => break,
}
}
}
NodeInner::List(_) => {
let mut cur = np;
while let NodeInner::List(c) | NodeInner::Alt(c) = &mut (*cur).inner {
tune_called_state(&mut c.car, state);
match &mut c.cdr {
Some(ref mut next) => cur = next.as_mut() as *mut Node,
None => break,
}
}
}
NodeInner::Call(_) => {
if (state & IN_PEEK) != 0 {
(*np).status_add(ND_ST_INPEEK);
}
if (state & IN_REAL_REPEAT) != 0 {
(*np).status_add(ND_ST_IN_REAL_REPEAT);
}
tune_called_state_call(&mut *np, state);
}
NodeInner::Bag(bn) => {
let bt = bn.bag_type;
match bt {
BagType::Memory => {
let mut s = state;
if let BagData::Memory {
entry_count,
ref mut called_state,
..
} = bn.bag_data
{
if entry_count > 1 {
s |= IN_MULTI_ENTRY;
}
*called_state |= s;
}
if let Some(ref mut body) = bn.body {
tune_called_state(body, s);
}
}
BagType::Option | BagType::StopBacktrack => {
if let Some(ref mut body) = bn.body {
tune_called_state(body, state);
}
}
BagType::IfElse => {
let s = state | IN_ALT;
if let Some(ref mut body) = bn.body {
tune_called_state(body, s);
}
if let BagData::IfElse {
ref mut then_node,
ref mut else_node,
} = bn.bag_data
{
if let Some(ref mut t) = then_node {
tune_called_state(t, s);
}
if let Some(ref mut e) = else_node {
tune_called_state(e, s);
}
}
}
}
}
NodeInner::Quant(qn) => {
let mut s = state;
if is_infinite_repeat(qn.upper) || qn.upper >= 2 {
s |= IN_REAL_REPEAT;
}
if qn.lower != qn.upper {
s |= IN_VAR_REPEAT;
}
if (state & IN_PEEK) != 0 {
(*np).status_add(ND_ST_INPEEK);
}
if let Some(ref mut body) = qn.body {
tune_called_state(body, s);
}
}
NodeInner::Anchor(an) => match an.anchor_type {
ANCR_PREC_READ_NOT | ANCR_LOOK_BEHIND_NOT => {
if let Some(ref mut body) = an.body {
tune_called_state(body, state | IN_NOT | IN_PEEK);
}
}
ANCR_PREC_READ | ANCR_LOOK_BEHIND => {
if let Some(ref mut body) = an.body {
tune_called_state(body, state | IN_PEEK);
}
}
_ => {}
},
_ => {}
}
}
}
// ============================================================================
// Literal alternation detection — replaces pure literal Alt trees with trie
// ============================================================================
/// Minimum number of literal alternatives to trigger trie optimization.
const LITERAL_ALT_THRESHOLD: usize = 4;
/// Maximum number of extracted paths from nested alternation structures.
/// Prevents exponential blowup from deeply nested optionals.
const MAX_NESTED_TRIE_PATHS: usize = 8192;
/// Info about one branch in an Alt cons-chain.
struct AltBranchInfo {
/// Index of this branch in the Alt cons-chain (0-based).
index: usize,
/// Whether this branch is a literal (plain string or nested structure
/// that was successfully extracted into literal paths).
is_literal: bool,
/// The literal byte sequences extracted from this branch.
/// A plain string branch has exactly one entry; a nested structure
/// may have multiple. Empty if `is_literal` is false.
literals: Vec<Vec<u8>>,
}
/// Walk the AST and detect semantically safe literal alternations. When found,
/// build a `LiteralTrie` and replace the complete alternation with one trie
/// node. Partial rewrites are intentionally excluded: moving literal branches
/// ahead of non-literal ones changes ordered-alternation semantics.
///
/// **Must be called before `tune_tree`** so that case-fold expansion has not
/// yet rewritten the string nodes.
pub fn detect_literal_alternations(
node: &mut Node,
reg: &mut RegexType,
backrefed_mem: MemStatusType,
) {
detect_literal_alternations_inner(node, reg, false, backrefed_mem);
}
/// Recurse into the children of a node for literal alternation detection.
fn recurse_into_children(
node: &mut Node,
reg: &mut RegexType,
in_anchor: bool,
backrefed_mem: MemStatusType,
) {
match &mut node.inner {
NodeInner::List(_) | NodeInner::Alt(_) => {
let mut cur: *mut Node = node;
// SAFETY: `cur` starts as the exclusive `&mut node` argument and only
// advances to the boxed cdr; `car` and `cdr` are disjoint fields, so
// recursing into car (which may rewrite that subtree in place) never
// aliases the cdr chain still being walked.
unsafe {
while let NodeInner::List(ref mut cons) | NodeInner::Alt(ref mut cons) =
(*cur).inner
{
let car = &mut *cons.car as *mut Node;
let cdr = &mut cons.cdr;
detect_literal_alternations_inner(&mut *car, reg, in_anchor, backrefed_mem);
match cdr {
Some(ref mut next) => cur = &mut **next,
None => break,
};
}
}
}
NodeInner::Quant(ref mut qn) => {
if let Some(ref mut body) = qn.body {
detect_literal_alternations_inner(body, reg, in_anchor, backrefed_mem);
}
}
NodeInner::Bag(ref mut bn) => {
if let Some(ref mut body) = bn.body {
detect_literal_alternations_inner(body, reg, in_anchor, backrefed_mem);
}
}
NodeInner::Anchor(ref mut an) => {
if let Some(ref mut body) = an.body {
detect_literal_alternations_inner(body, reg, true, backrefed_mem);
}
}
_ => {}
}
}
/// Try to trie-optimize an Alt node using nested extraction. Returns true
/// if optimization was applied (full or partial).
fn try_trie_optimize_alt(
node: &mut Node,
reg: &mut RegexType,
backrefed_mem: MemStatusType,
) -> bool {
// Collect info about each branch.
let mut branches: Vec<AltBranchInfo> = Vec::new();
let mut case_insensitive = false;
let mut literal_count = 0usize;
let mut all_plain_strings = true;
{
let mut cur: *const Node = node;
let mut idx = 0usize;
// SAFETY: `cur` starts as the exclusive `&mut node` argument (demoted to
// shared) and only advances to boxed cdr nodes, so every deref is of a
// live node; this walk and classify_branch perform reads only.
unsafe {
loop {
let (car, cdr) = match &(*cur).inner {
NodeInner::Alt(ref cons) => (&*cons.car as *const Node, &cons.cdr),
_ => {
all_plain_strings &=
matches!(&(*cur).inner, NodeInner::String(sn) if !sn.is_crude());
let info = classify_branch(&*cur, backrefed_mem);
if info.is_literal && (*cur).has_status(ND_ST_IGNORECASE) {
case_insensitive = true;
}
if info.is_literal {
literal_count += info.literals.len();
}
branches.push(AltBranchInfo { index: idx, ..info });
break;
}
};
all_plain_strings &=
matches!(&(*car).inner, NodeInner::String(sn) if !sn.is_crude());
let info = classify_branch(&*car, backrefed_mem);
if info.is_literal && (*car).has_status(ND_ST_IGNORECASE) {
case_insensitive = true;
}
if info.is_literal {
literal_count += info.literals.len();
}
branches.push(AltBranchInfo { index: idx, ..info });
idx += 1;
match cdr {
Some(ref next) => cur = &**next,
None => break,
}
}
}
}
let all_literal = branches.iter().all(|b| b.is_literal);
if literal_count < LITERAL_ALT_THRESHOLD
|| !all_literal
|| !all_plain_strings
|| case_insensitive
|| reg.options.intersects(ONIG_OPTION_IGNORECASE)
{
return false;
}
// The trie returns the longest terminal. That is equivalent to ordered
// alternation only when no two literals have a prefix relationship.
let mut literals: Vec<Vec<u8>> = branches
.iter()
.flat_map(|b| b.literals.iter().cloned())
.collect();
// A lexicographic ordering places every possible extension immediately
// after its prefix. Checking adjacent pairs avoids a quadratic scan for
// large, generated literal alternations.
literals.sort_unstable();
if literals
.windows(2)
.any(|pair| pair[1].starts_with(pair[0].as_slice()))
{
return false;
}
let literal_refs: Vec<&[u8]> = literals.iter().map(|v| v.as_slice()).collect();
let trie = crate::literal_trie::LiteralTrie::build(&literal_refs, false);
let trie_idx = reg.literal_tries.len() as u32;
reg.literal_tries.push(trie);
node.inner = NodeInner::String(StrNode {
s: trie_idx.to_le_bytes().to_vec(),
flag: 0,
});
node.status_add(ND_ST_LITERAL_ALT);
true
}
fn detect_literal_alternations_inner(
node: &mut Node,
reg: &mut RegexType,
in_anchor: bool,
backrefed_mem: MemStatusType,
) {
// Try top-down: if this node is an Alt (not in anchor), try nested
// extraction BEFORE recursing into children. This prevents inner Alts
// from being trie-optimized first (which makes them opaque to outer
// extraction).
if matches!(node.inner, NodeInner::Alt(_))
&& !in_anchor
&& try_trie_optimize_alt(node, reg, backrefed_mem)
{
// Successfully trie-optimized this complete literal alternation.
recurse_into_children(node, reg, in_anchor, backrefed_mem);
return;
}
// Recurse into children, then retry flat-check on this Alt.
recurse_into_children(node, reg, in_anchor, backrefed_mem);
// After recursion, retry on this Alt. Inner Alts may now be trie
// nodes; classify_branch handles that via check_literal_branch.
if matches!(node.inner, NodeInner::Alt(_)) && !in_anchor {
try_trie_optimize_alt(node, reg, backrefed_mem);
}
}
/// Recursively extract all possible literal byte sequences from a nested AST
/// branch. Handles String, List (sequence), Alt (fork), Bag (non-capturing or
/// non-backreferenced capturing groups), and Quant(0,1) (optional `?`).
///
/// Returns `None` if any sub-expression is non-literal (CClass, CType, complex
/// Quant, Anchor, BackRef, etc.). The `limit` prevents exponential blowup.
fn extract_literal_paths(
node: *const Node,
current_prefixes: Vec<Vec<u8>>,
limit: usize,
backrefed_mem: MemStatusType,
) -> Option<Vec<Vec<u8>>> {
if current_prefixes.len() > limit {
return None;
}
// SAFETY: callers pass `node` pointing at a live node of the tree currently
// borrowed by try_trie_optimize_alt (classify_branch derives it from a
// reference; recursive calls pass children of the dereferenced node), and
// only shared reads are performed.
unsafe {
match &(*node).inner {
NodeInner::String(ref sn) => {
if sn.is_crude() || (*node).has_status(ND_ST_LITERAL_ALT) {
return None;
}
// Append this string's bytes to each prefix
let result: Vec<Vec<u8>> = current_prefixes
.into_iter()
.map(|mut prefix| {
prefix.extend_from_slice(&sn.s);
prefix
})
.collect();
Some(result)
}
NodeInner::List(ref cons) => {
// Sequence: walk car then cdr, threading prefixes through
let car: *const Node = &*cons.car;
let after_car = extract_literal_paths(car, current_prefixes, limit, backrefed_mem)?;
if after_car.len() > limit {
return None;
}
match &cons.cdr {
Some(ref next) => {
let cdr: *const Node = &**next;
extract_literal_paths(cdr, after_car, limit, backrefed_mem)
}
None => Some(after_car),
}
}
NodeInner::Alt(ref cons) => {
// Fork: recurse into each branch, collect all resulting paths
let mut all_paths: Vec<Vec<u8>> = Vec::new();
let mut cur: *const Node = node;
loop {
let (car, cdr) = match &(*cur).inner {
NodeInner::Alt(ref cons) => (&*cons.car as *const Node, &cons.cdr),
_ => {
// Last node in the chain (not wrapped in Alt)
let branch_paths = extract_literal_paths(
cur,
current_prefixes.clone(),
limit,
backrefed_mem,
)?;
all_paths.extend(branch_paths);
if all_paths.len() > limit {
return None;
}
break;
}
};
let branch_paths =
extract_literal_paths(car, current_prefixes.clone(), limit, backrefed_mem)?;
all_paths.extend(branch_paths);
if all_paths.len() > limit {
return None;
}
match cdr {
Some(ref next) => cur = &**next,
None => break,
}
}
Some(all_paths)
}
NodeInner::Bag(ref bn) => {
match bn.bag_type {
BagType::Memory => {
// Capturing group: only safe if not backreferenced
if mem_status_at(backrefed_mem, bn.regnum() as usize) {
return None;
}
match &bn.body {
Some(ref body) => {
let body_ptr: *const Node = &**body;
extract_literal_paths(
body_ptr,
current_prefixes,
limit,
backrefed_mem,
)
}
None => Some(current_prefixes),
}
}
BagType::Option => {
// Non-capturing group (?:...) or option group
match &bn.body {
Some(ref body) => {
let body_ptr: *const Node = &**body;
extract_literal_paths(
body_ptr,
current_prefixes,
limit,
backrefed_mem,
)
}
None => Some(current_prefixes),
}
}
_ => None, // StopBacktrack, IfElse — not literal
}
}
NodeInner::Quant(ref qn) => {
if qn.lower == 0 && qn.upper == 1 {
// Optional `?`: fork into "with" and "without" paths
match &qn.body {
Some(ref body) => {
let body_ptr: *const Node = &**body;
let with_paths = extract_literal_paths(
body_ptr,
current_prefixes.clone(),
limit,
backrefed_mem,
)?;
let mut all = current_prefixes; // "without" paths
all.extend(with_paths);
if all.len() > limit {
return None;
}
Some(all)
}
None => Some(current_prefixes),
}
} else {
None // Complex quantifier — not literal
}
}
// CClass, CType, BackRef, Anchor, Call, Gimmick — not literal
_ => None,
}
}
}
/// Classify a branch as literal or non-literal. Tries the fast path
/// (`check_literal_branch`) first, then falls back to `extract_literal_paths`
/// for nested structures.
fn classify_branch(node: *const Node, backrefed_mem: MemStatusType) -> AltBranchInfo {
let (is_lit, lit) = check_literal_branch(node);
if is_lit {
return AltBranchInfo {
index: 0, // caller will override
is_literal: true,
literals: vec![lit],
};
}
// Try nested extraction
if let Some(paths) =
extract_literal_paths(node, vec![Vec::new()], MAX_NESTED_TRIE_PATHS, backrefed_mem)
{
if !paths.is_empty() && paths.iter().all(|p| !p.is_empty()) {
return AltBranchInfo {
index: 0,
is_literal: true,
literals: paths,
};
}
}
AltBranchInfo {
index: 0,
is_literal: false,
literals: Vec::new(),
}
}
/// Check if a node is a plain literal string (non-crude, no ND_ST_LITERAL_ALT).
fn check_literal_branch(node: *const Node) -> (bool, Vec<u8>) {
// SAFETY: callers pass `node` pointing at a live node of the currently
// borrowed tree (derived from references in try_trie_optimize_alt and
// classify_branch); only shared reads are performed.
unsafe {
if (*node).has_status(ND_ST_LITERAL_ALT) {
return (false, Vec::new());
}
if let NodeInner::String(ref sn) = (*node).inner {
if !sn.is_crude() {
return (true, sn.s.clone());
}
}
(false, Vec::new())
}
}
/// Extract specific branches (by index) from an Alt cons-chain.
/// Returns the extracted nodes in the order of their indices.
fn extract_alt_branches(alt_node: &mut Node, indices: &[usize], out: &mut Vec<Node>) {
// Walk the Alt cons-chain and collect the nodes at the given indices.
let mut idx = 0usize;
let mut cur: *mut Node = alt_node;
// SAFETY: `cur` starts as the exclusive `&mut alt_node` argument and only
// advances to boxed cdr nodes, so every deref is of a live, exclusively
// borrowed node; the mem::replace calls swap out whole cars (or the tail
// node) without touching the chain links still to be walked.
unsafe {
loop {
match &mut (*cur).inner {
NodeInner::Alt(ref mut cons) => {
if indices.contains(&idx) {
// Take the car node
let taken = std::mem::replace(
&mut cons.car,
Box::new(Node {
status: 0,
parent: std::ptr::null_mut(),
inner: NodeInner::String(StrNode {
s: Vec::new(),
flag: 0,
}),
}),
);
out.push(*taken);
}
idx += 1;
match cons.cdr {
Some(ref mut next) => cur = &mut **next,
None => break,
}
}
_ => {
// Last node (tail) — check if it's in the indices
if indices.contains(&idx) {
let placeholder = Node {
status: 0,
parent: std::ptr::null_mut(),
inner: NodeInner::String(StrNode {
s: Vec::new(),
flag: 0,
}),
};
let taken = std::mem::replace(&mut *cur, placeholder);
out.push(taken);
}
break;
}
}
}
}
}
/// Tree tuning pass - sets emptiness on quantifier nodes and propagates state.
/// Mirrors C's tune_tree() from regcomp.c.
pub fn tune_tree(node: &mut Node, reg: &mut RegexType, state: i32, env: &mut ParseEnv) -> i32 {
// Skip nodes already optimized as literal alternation tries.
if node.has_status(ND_ST_LITERAL_ALT) {
return 0;
}
// Case-fold expansion: before the main match to get full &mut Node access
if let NodeInner::String(ref sn) = node.inner {
if node.has_status(ND_ST_IGNORECASE) && !sn.is_crude() {
let r = unravel_case_fold_string(node, reg, state);
if r != 0 {
return r;
}
// After expansion, the node may have changed type (CClass, List, etc.)
// Recurse to tune the expanded tree
return tune_tree(node, reg, state, env);
}
}
match &mut node.inner {
NodeInner::List(_) => {
// Walk the list: tune each element, then call tune_next for sequential pairs
let mut cur: *mut Node = node;
let mut prev: *mut Node = std::ptr::null_mut();
// SAFETY: `cur` starts as the exclusive `&mut node` argument and only
// advances to boxed cdr nodes. `prev` points at the previous
// element's car — a node distinct from the current `cons.car` — so
// the `&mut *prev` passed to tune_next does not alias the `&cons.car`
// passed alongside it; tune_tree rewrites cars in place and never
// moves or frees their boxed allocations.
unsafe {
while let NodeInner::List(ref mut cons) = (*cur).inner {
let r = tune_tree(&mut cons.car, reg, state, env);
if r != 0 {
return r;
}
// Call tune_next on previous node with current as next
if !prev.is_null() {
let r = tune_next(&mut *prev, &cons.car, reg);
if r != 0 {
return r;
}
}
prev = &mut *cons.car;
match cons.cdr {
Some(ref mut next) => cur = &mut **next,
None => break,
}
}
}
0
}
NodeInner::Alt(_) => {
let mut cur: *mut Node = node;
// SAFETY: `cur` starts as the exclusive `&mut node` argument and only
// advances to boxed cdr nodes, so every deref is of a live,
// exclusively borrowed node.
unsafe {
while let NodeInner::Alt(ref mut cons) = (*cur).inner {
let r = tune_tree(&mut cons.car, reg, state | IN_ALT, env);
if r != 0 {
return r;
}
match cons.cdr {
Some(ref mut next) => cur = &mut **next,
None => break,
}
}
}
0
}
NodeInner::Quant(ref mut qn) => {
// Propagate repeat status flags
if (state & IN_REAL_REPEAT) != 0 {
node.status |= ND_ST_IN_REAL_REPEAT;
}
if (state & IN_MULTI_ENTRY) != 0 {
node.status |= ND_ST_IN_MULTI_ENTRY;
}
// Check if body can match empty
if is_infinite_repeat(qn.upper) || qn.upper >= 1 {
if let Some(ref body) = qn.body {
let d = node_min_byte_len(body, env);
if d == 0 {
// Use quantifiers_memory_node_info to detect captures in body
qn.emptiness = quantifiers_memory_node_info(body);
}
}
}
// Update state for recursive call
let mut new_state = state;
if is_infinite_repeat(qn.upper) || qn.upper >= 2 {
new_state |= IN_REAL_REPEAT;
}
if qn.lower != qn.upper {
new_state |= IN_VAR_REPEAT;
}
// Recurse into body
if let Some(ref mut body) = qn.body {
let r = tune_tree(body, reg, new_state, env);
if r != 0 {
return r;
}
}
// Expand string: "abc"{3} => "abcabcabc"
const EXPAND_STRING_MAX_LENGTH: i32 = 100;
if let Some(ref body) = qn.body {
if let NodeInner::String(ref sn) = body.inner {
if !is_infinite_repeat(qn.lower)
&& qn.lower == qn.upper
&& qn.lower > 1
&& qn.lower <= EXPAND_STRING_MAX_LENGTH
{
let len = sn.s.len() as i32;
if len * qn.lower <= EXPAND_STRING_MAX_LENGTH {
let n = qn.lower as usize;
let orig_bytes = sn.s.clone();
let flag = sn.flag;
// Build expanded string
let mut expanded = Vec::with_capacity(orig_bytes.len() * n);
for _ in 0..n {
expanded.extend_from_slice(&orig_bytes);
}
// Replace quantifier node with string node
let mut str_node = node_new_str(&expanded);
if let NodeInner::String(ref mut esn) = str_node.inner {
esn.flag = flag;
}
str_node.status = node.status;
*node = *str_node;
return 0;
}
}
}
}
// Set head_exact: extract leading literal byte from body
if qn.greedy && qn.emptiness == BodyEmptyType::NotEmpty {
if let Some(ref body) = qn.body {
if let NodeInner::Quant(ref tqn) = body.inner {
// Propagate head_exact from nested quantifier
if tqn.head_exact.is_some() {
qn.head_exact = tqn.head_exact;
}
} else {
qn.head_exact = get_head_literal_byte(body, true, reg);
}
}
}
0
}
NodeInner::Bag(ref mut bn) => {
match bn.bag_type {
BagType::Option => {
let saved_options = reg.options;
if let BagData::Option { options } = bn.bag_data {
reg.options = options;
}
let r = if let Some(ref mut body) = bn.body {
tune_tree(body, reg, state, env)
} else {
0
};
reg.options = saved_options;
r
}
BagType::Memory => {
// Propagate called_state into state (C: state |= en->m.called_state)
let mut state = state;
if let BagData::Memory { called_state, .. } = bn.bag_data {
state |= called_state;
}
if (state & (IN_ALT | IN_NOT | IN_VAR_REPEAT | IN_MULTI_ENTRY)) != 0
|| (node.status & ND_ST_RECURSION) != 0
{
// Backtrack mem needed for captures in alternation/variable repeat/recursion
if let BagData::Memory { regnum, .. } = bn.bag_data {
mem_status_on(&mut env.backtrack_mem, regnum as usize);
}
}
if let Some(ref mut body) = bn.body {
tune_tree(body, reg, state, env)
} else {
0
}
}
BagType::StopBacktrack => {
if let Some(ref mut body) = bn.body {
tune_tree(body, reg, state, env)
} else {
0
}
}
BagType::IfElse => {
if let Some(ref mut body) = bn.body {
let r = tune_tree(body, reg, state | IN_ALT, env);
if r != 0 {
return r;
}
}
if let BagData::IfElse {
ref mut then_node,
ref mut else_node,
} = bn.bag_data
{
if let Some(ref mut then_n) = then_node {
let r = tune_tree(then_n, reg, state | IN_ALT, env);
if r != 0 {
return r;
}
}
if let Some(ref mut else_n) = else_node {
let r = tune_tree(else_n, reg, state | IN_ALT, env);
if r != 0 {
return r;
}
}
}
0
}
}
}
NodeInner::Anchor(ref mut an) => {
let at = an.anchor_type;
// For lookbehind anchors, compute char lengths (may transform node into Alt)
if at == ANCR_LOOK_BEHIND || at == ANCR_LOOK_BEHIND_NOT {
let enc = env.enc;
let r = tune_look_behind(node, enc, &env.syntax);
if r != 0 {
return r;
}
// tune_look_behind may have transformed node into an Alt;
// if so, recurse on the new node structure
if !matches!(node.inner, NodeInner::Anchor(_)) {
return tune_tree(node, reg, state, env);
}
}
// Now recurse into the body
if let NodeInner::Anchor(ref mut an) = node.inner {
let anchor_type = an.anchor_type;
if let Some(ref mut body) = an.body {
let new_state = if anchor_type == ANCR_PREC_READ {
state | IN_PREC_READ
} else if anchor_type == ANCR_PREC_READ_NOT {
state | IN_PREC_READ | IN_NOT
} else if anchor_type == ANCR_LOOK_BEHIND_NOT {
state | IN_NOT | IN_LOOK_BEHIND
} else if anchor_type == ANCR_LOOK_BEHIND {
state | IN_LOOK_BEHIND
} else {
state
};
let r = tune_tree(body, reg, new_state, env);
if r != 0 {
return r;
}
// Reduce quantifiers in lookbehind (upper = lower)
if anchor_type == ANCR_LOOK_BEHIND || anchor_type == ANCR_LOOK_BEHIND_NOT {
alt_reduce_in_look_behind(body);
}
0
} else {
0
}
} else {
0
}
}
NodeInner::BackRef(ref br) => {
// Set backrefed_mem for each referenced group
for &back in br.back_refs() {
if back > 0 {
mem_status_on(&mut env.backrefed_mem, back as usize);
}
}
0
}
// Terminal nodes - nothing to tune
NodeInner::String(_)
| NodeInner::CType(_)
| NodeInner::CClass(_)
| NodeInner::Call(_)
| NodeInner::Gimmick(_) => 0,
}
}
// ============================================================================
// setup_empty_status_mem: compute qn.empty_status_mem for quantifiers
// ============================================================================
/// Pass 1: For each quantifier with emptiness >= MayBeEmptyMem, set
/// empty_repeat_node on all captures in its body.
fn mark_empty_repeat_node(node: &mut Node, env: &mut ParseEnv) {
let node_ptr = node as *mut Node;
match &mut node.inner {
NodeInner::Quant(ref mut qn) => {
let is_empty = qn.emptiness == BodyEmptyType::MayBeEmptyMem
|| qn.emptiness == BodyEmptyType::MayBeEmptyRec;
if is_empty {
if let Some(ref body) = qn.body {
set_empty_repeat_node_in_body(body, node_ptr as *const Node, env);
}
}
if let Some(ref mut body) = qn.body {
mark_empty_repeat_node(body, env);
}
}
NodeInner::List(_) | NodeInner::Alt(_) => {
let mut cur: *mut Node = node;
// SAFETY: `cur` starts as the exclusive `&mut node` argument and only
// advances to boxed cdr nodes, so every deref is of a live,
// exclusively borrowed node; the recursion into car borrows a field
// disjoint from the cdr link.
unsafe {
while let NodeInner::List(ref mut cons) | NodeInner::Alt(ref mut cons) =
(*cur).inner
{
mark_empty_repeat_node(cons.car.as_mut(), env);
match cons.cdr {
Some(ref mut next) => cur = &mut **next,
None => break,
}
}
}
}
NodeInner::Bag(ref mut bn) => {
if let Some(ref mut body) = bn.body {
mark_empty_repeat_node(body, env);
}
if let BagData::IfElse {
ref mut then_node,
ref mut else_node,
} = bn.bag_data
{
if let Some(ref mut t) = then_node {
mark_empty_repeat_node(t, env);
}
if let Some(ref mut e) = else_node {
mark_empty_repeat_node(e, env);
}
}
}
NodeInner::Anchor(ref mut an) => {
if let Some(ref mut body) = an.body {
mark_empty_repeat_node(body, env);
}
}
_ => {}
}
}
/// Helper: set empty_repeat_node for all BAG_MEMORY nodes in `node`.
fn set_empty_repeat_node_in_body(node: &Node, quant_ptr: *const Node, env: &mut ParseEnv) {
match &node.inner {
NodeInner::Bag(bn) => {
if bn.bag_type == BagType::Memory {
if let BagData::Memory { regnum, .. } = bn.bag_data {
let regnum = regnum as usize;
let entry = env.mem_env_mut(regnum);
entry.empty_repeat_node = quant_ptr as *mut Node;
}
}
if let Some(ref body) = bn.body {
set_empty_repeat_node_in_body(body, quant_ptr, env);
}
if let BagData::IfElse {
ref then_node,
ref else_node,
} = bn.bag_data
{
if let Some(ref t) = then_node {
set_empty_repeat_node_in_body(t, quant_ptr, env);
}
if let Some(ref e) = else_node {
set_empty_repeat_node_in_body(e, quant_ptr, env);
}
}
}
NodeInner::List(_) | NodeInner::Alt(_) => {
let mut cur: &Node = node;
while let NodeInner::List(cons) | NodeInner::Alt(cons) = &cur.inner {
set_empty_repeat_node_in_body(&cons.car, quant_ptr, env);
match &cons.cdr {
Some(ref next) => cur = next,
None => break,
}
}
}
NodeInner::Quant(qn) => {
if let Some(ref body) = qn.body {
set_empty_repeat_node_in_body(body, quant_ptr, env);
}
}
NodeInner::Anchor(an) => {
if let Some(ref body) = an.body {
set_empty_repeat_node_in_body(body, quant_ptr, env);
}
}
_ => {}
}
}
/// Pass 2: Walk tree with a stack of enclosing empty-quantifier pointers.
/// When a backref is found, check if its target's empty_repeat_node is NOT
/// in the enclosing stack → set empty_status_mem on that quantifier.
fn resolve_empty_status_backrefs(
node: &mut Node,
enclosing_quants: &mut Vec<*const Node>,
env: &ParseEnv,
) {
let node_ptr = node as *const Node;
match &mut node.inner {
NodeInner::Quant(ref mut qn) => {
let is_empty_quant = qn.emptiness == BodyEmptyType::MayBeEmptyMem
|| qn.emptiness == BodyEmptyType::MayBeEmptyRec;
if is_empty_quant {
enclosing_quants.push(node_ptr);
}
if let Some(ref mut body) = qn.body {
resolve_empty_status_backrefs(body, enclosing_quants, env);
}
if is_empty_quant {
enclosing_quants.pop();
}
}
NodeInner::BackRef(ref br) => {
for &back in br.back_refs() {
if back <= 0 {
continue;
}
let back = back as usize;
let entry = env.mem_env(back);
let er_node = entry.empty_repeat_node;
if !er_node.is_null() {
// Check if the backref is inside the quantifier
if !enclosing_quants.contains(&(er_node as *const Node)) {
// Backref is OUTSIDE the quantifier → set empty_status_mem
// SAFETY: `er_node` was set by mark_empty_repeat_node (pass 1)
// to a Quant node in this same tree, which has not been
// restructured since, so it is live. Every empty quantifier
// on the current traversal path is in `enclosing_quants`, so
// the contains() check above guarantees `er_node` is not a
// node this traversal currently borrows.
unsafe {
if let NodeInner::Quant(ref mut qn) = (*er_node).inner {
qn.empty_status_mem |= 1u32 << back;
(*er_node).status |= ND_ST_EMPTY_STATUS_CHECK;
}
}
}
}
}
}
NodeInner::List(_) | NodeInner::Alt(_) => {
let mut cur: *mut Node = node;
// SAFETY: `cur` starts as the exclusive `&mut node` argument and only
// advances to boxed cdr nodes, so every deref is of a live,
// exclusively borrowed node; the recursion into car borrows a field
// disjoint from the cdr link.
unsafe {
while let NodeInner::List(ref mut cons) | NodeInner::Alt(ref mut cons) =
(*cur).inner
{
resolve_empty_status_backrefs(cons.car.as_mut(), enclosing_quants, env);
match cons.cdr {
Some(ref mut next) => cur = &mut **next,
None => break,
}
}
}
}
NodeInner::Bag(ref mut bn) => {
if let Some(ref mut body) = bn.body {
resolve_empty_status_backrefs(body, enclosing_quants, env);
}
if let BagData::IfElse {
ref mut then_node,
ref mut else_node,
} = bn.bag_data
{
if let Some(ref mut t) = then_node {
resolve_empty_status_backrefs(t, enclosing_quants, env);
}
if let Some(ref mut e) = else_node {
resolve_empty_status_backrefs(e, enclosing_quants, env);
}
}
}
NodeInner::Anchor(ref mut an) => {
if let Some(ref mut body) = an.body {
resolve_empty_status_backrefs(body, enclosing_quants, env);
}
}
_ => {}
}
}
/// Compute qn.empty_status_mem for all quantifiers in the tree.
fn setup_empty_status_mem(root: &mut Node, env: &mut ParseEnv) {
// Pass 1: mark empty_repeat_node on captures inside empty quantifiers
mark_empty_repeat_node(root, env);
// Pass 2: resolve backrefs to set empty_status_mem
let mut enclosing = Vec::new();
resolve_empty_status_backrefs(root, &mut enclosing, env);
}
fn refresh_capture_nodes(node: &mut Node, env: &mut ParseEnv) {
let node_ptr = node as *mut Node;
match &mut node.inner {
NodeInner::List(cons) | NodeInner::Alt(cons) => {
refresh_capture_nodes(cons.car.as_mut(), env);
if let Some(cdr) = cons.cdr.as_mut() {
refresh_capture_nodes(cdr.as_mut(), env);
}
}
NodeInner::Quant(qn) => {
if let Some(body) = qn.body.as_mut() {
refresh_capture_nodes(body.as_mut(), env);
}
}
NodeInner::Bag(bn) => {
if bn.bag_type == BagType::Memory {
let regnum = bn.regnum() as usize;
if regnum <= env.num_mem as usize {
env.mem_env_mut(regnum).mem_node = node_ptr;
}
}
if let Some(body) = bn.body.as_mut() {
refresh_capture_nodes(body.as_mut(), env);
}
if let BagData::IfElse {
then_node,
else_node,
} = &mut bn.bag_data
{
if let Some(then_n) = then_node.as_mut() {
refresh_capture_nodes(then_n.as_mut(), env);
}
if let Some(else_n) = else_node.as_mut() {
refresh_capture_nodes(else_n.as_mut(), env);
}
}
}
NodeInner::Anchor(an) => {
if let Some(body) = an.body.as_mut() {
refresh_capture_nodes(body.as_mut(), env);
}
if let Some(lead) = an.lead_node.as_mut() {
refresh_capture_nodes(lead.as_mut(), env);
}
}
NodeInner::Call(cn) => {
if let Some(body) = cn.body.as_mut() {
refresh_capture_nodes(body.as_mut(), env);
}
}
_ => {}
}
}
fn refresh_call_targets(node: &mut Node, env: &ParseEnv) {
match &mut node.inner {
NodeInner::List(cons) | NodeInner::Alt(cons) => {
refresh_call_targets(cons.car.as_mut(), env);
if let Some(cdr) = cons.cdr.as_mut() {
refresh_call_targets(cdr.as_mut(), env);
}
}
NodeInner::Quant(qn) => {
if let Some(body) = qn.body.as_mut() {
refresh_call_targets(body.as_mut(), env);
}
}
NodeInner::Bag(bn) => {
if let Some(body) = bn.body.as_mut() {
refresh_call_targets(body.as_mut(), env);
}
if let BagData::IfElse {
then_node,
else_node,
} = &mut bn.bag_data
{
if let Some(then_n) = then_node.as_mut() {
refresh_call_targets(then_n.as_mut(), env);
}
if let Some(else_n) = else_node.as_mut() {
refresh_call_targets(else_n.as_mut(), env);
}
}
}
NodeInner::Anchor(an) => {
if let Some(body) = an.body.as_mut() {
refresh_call_targets(body.as_mut(), env);
}
if let Some(lead) = an.lead_node.as_mut() {
refresh_call_targets(lead.as_mut(), env);
}
}
NodeInner::Call(cn) => {
cn.target_node = if cn.called_gnum > 0 && cn.called_gnum <= env.num_mem {
env.mem_env(cn.called_gnum as usize).mem_node
} else {
std::ptr::null_mut()
};
if let Some(body) = cn.body.as_mut() {
refresh_call_targets(body.as_mut(), env);
}
}
_ => {}
}
}
fn refresh_node_references(root: &mut Node, env: &mut ParseEnv) {
if env.num_mem <= 0 && env.num_call <= 0 {
return;
}
for i in 1..=env.num_mem as usize {
env.mem_env_mut(i).mem_node = std::ptr::null_mut();
}
refresh_capture_nodes(root, env);
if env.num_call > 0 {
refresh_call_targets(root, env);
}
}
/// Flatten a List node into a Vec of car elements.
fn flatten_list(mut node: Node) -> Vec<Node> {
let mut items = Vec::new();
loop {
match node.inner {
NodeInner::List(cons) => {
items.push(*cons.car);
match cons.cdr {
Some(next) => node = *next,
None => break,
}
}
_ => {
// Shouldn't happen - the last cdr should be None
items.push(node);
break;
}
}
}
items
}
/// Rebuild a List node from a Vec of car elements.
fn rebuild_list(items: Vec<Node>) -> Box<Node> {
let mut items = items;
assert!(!items.is_empty());
let mut result = Box::new(Node {
status: 0,
parent: std::ptr::null_mut(),
inner: NodeInner::List(ConsAltNode {
car: Box::new(items.pop().unwrap()),
cdr: None,
}),
});
while let Some(item) = items.pop() {
result = Box::new(Node {
status: 0,
parent: std::ptr::null_mut(),
inner: NodeInner::List(ConsAltNode {
car: Box::new(item),
cdr: Some(result),
}),
});
}
result
}
/// Consolidate adjacent string nodes in the parse tree.
/// Mirrors C's reduce_string_list() from regcomp.c.
pub fn reduce_string_list(node: &mut Node, _enc: OnigEncoding) -> i32 {
match &mut node.inner {
NodeInner::List(_) => {
// Take ownership of the list, flatten, merge, rebuild
let placeholder = NodeInner::String(StrNode {
s: Vec::new(),
flag: 0,
});
let old_inner = std::mem::replace(&mut node.inner, placeholder);
let list_node = Box::new(Node {
status: 0,
parent: std::ptr::null_mut(),
inner: old_inner,
});
let mut items = flatten_list(*list_node);
// First recurse into non-string children
for item in items.iter_mut() {
if item.node_type() != NodeType::String {
let r = reduce_string_list(item, _enc);
if r != 0 {
// Rebuild and put back before returning error
node.inner = rebuild_list(items).inner;
return r;
}
}
}
// Merge adjacent string nodes with same flags and status
let mut merged: Vec<Node> = Vec::new();
for item in items {
if item.node_type() == NodeType::String {
let can_merge = if let Some(last) = merged.last() {
if last.node_type() == NodeType::String {
let last_str = last.as_str().unwrap();
let curr_str = item.as_str().unwrap();
last_str.flag == curr_str.flag && last.status == item.status
} else {
false
}
} else {
false
};
if can_merge {
let curr_bytes = item.as_str().unwrap().s.clone();
let last = merged.last_mut().unwrap();
last.as_str_mut().unwrap().s.extend_from_slice(&curr_bytes);
} else {
merged.push(item);
}
} else {
merged.push(item);
}
}
// Rebuild the list
if merged.len() == 1 {
// Single node: unwrap from list
let single = merged.into_iter().next().unwrap();
*node = single;
} else {
node.inner = rebuild_list(merged).inner;
}
0
}
NodeInner::Alt(_) => {
// Recurse into each alternative
let saved_status = node.status; // preserve flags like ND_ST_SUPER
let placeholder = NodeInner::String(StrNode {
s: Vec::new(),
flag: 0,
});
let old_inner = std::mem::replace(&mut node.inner, placeholder);
let alt_node = Box::new(Node {
status: 0,
parent: std::ptr::null_mut(),
inner: old_inner,
});
// Flatten the alt chain
let mut items = Vec::new();
let mut current: Option<Box<Node>> = Some(alt_node);
while let Some(n) = current {
match n.inner {
NodeInner::Alt(cons) => {
items.push(cons.car);
current = cons.cdr;
}
_ => {
items.push(n);
current = None;
}
}
}
// Recurse into each alternative
for item in items.iter_mut() {
let r = reduce_string_list(item, _enc);
if r != 0 {
// Rebuild alt chain and put back
let mut result = Node {
status: 0,
parent: std::ptr::null_mut(),
inner: NodeInner::Alt(ConsAltNode {
car: items.pop().unwrap(),
cdr: None,
}),
};
while let Some(item) = items.pop() {
result = Node {
status: 0,
parent: std::ptr::null_mut(),
inner: NodeInner::Alt(ConsAltNode {
car: item,
cdr: Some(Box::new(result)),
}),
};
}
*node = result;
return r;
}
}
// Rebuild alt chain, preserving the original root status (e.g. ND_ST_SUPER)
let mut items_rev: Vec<Box<Node>> = items;
let last = items_rev.pop().unwrap();
let mut result = Node {
status: 0,
parent: std::ptr::null_mut(),
inner: NodeInner::Alt(ConsAltNode {
car: last,
cdr: None,
}),
};
while let Some(item) = items_rev.pop() {
result = Node {
status: 0,
parent: std::ptr::null_mut(),
inner: NodeInner::Alt(ConsAltNode {
car: item,
cdr: Some(Box::new(result)),
}),
};
}
result.status = saved_status;
*node = result;
0
}
NodeInner::Quant(ref mut q) => {
if let Some(ref mut body) = q.body {
reduce_string_list(body, _enc)
} else {
0
}
}
NodeInner::Anchor(ref mut a) => {
if let Some(ref mut body) = a.body {
let r = reduce_string_list(body, _enc);
if r != 0 {
return r;
}
}
0
}
NodeInner::Bag(ref mut b) => {
if let Some(ref mut body) = b.body {
let r = reduce_string_list(body, _enc);
if r != 0 {
return r;
}
}
if let BagData::IfElse {
ref mut then_node,
ref mut else_node,
} = b.bag_data
{
if let Some(ref mut then_n) = then_node {
let r = reduce_string_list(then_n, _enc);
if r != 0 {
return r;
}
}
if let Some(ref mut else_n) = else_node {
let r = reduce_string_list(else_n, _enc);
if r != 0 {
return r;
}
}
}
0
}
_ => 0,
}
}
/// Simple compilation from a pre-parsed AST tree.
/// Used internally and by tests that parse separately.
#[cfg_attr(coverage_nightly, coverage(off))]
pub fn compile_from_tree(root: &Node, reg: &mut RegexType, env: &ParseEnv) -> i32 {
// Clear previous bytecode
reg.ops.clear();
// Compile the tree to bytecode
let r = compile_tree(root, reg, env);
if r != 0 {
return r;
}
// Add OP_END
add_op(reg, OpCode::End, OperationPayload::None);
refresh_capture_tracking_requirement(reg);
0
}
fn opcode_requires_capture_tracking(opcode: OpCode) -> bool {
matches!(
opcode,
OpCode::BackRef1
| OpCode::BackRef2
| OpCode::BackRefN
| OpCode::BackRefNIc
| OpCode::BackRefMulti
| OpCode::BackRefMultiIc
| OpCode::BackRefWithLevel
| OpCode::BackRefWithLevelIc
| OpCode::BackRefCheck
| OpCode::BackRefCheckWithLevel
| OpCode::MemStartPush
| OpCode::MemEndPush
| OpCode::MemEndPushRec
| OpCode::MemEndRec
| OpCode::EmptyCheckEndMemst
| OpCode::EmptyCheckEndMemstPush
| OpCode::Call
)
}
fn refresh_capture_tracking_requirement(reg: &mut RegexType) {
reg.needs_capture_tracking = reg
.ops
.iter()
.any(|op| opcode_requires_capture_tracking(op.opcode));
}
// ============================================================================
// Optimization subsystem — mirrors C's regcomp.c lines 5881-7064
// ============================================================================
const MAX_ND_OPT_INFO_REF_COUNT: i32 = 5;
fn map_position_value(enc: OnigEncoding, i: usize) -> i32 {
static VALS: [i16; 128] = [
5, 1, 1, 1, 1, 1, 1, 1, 1, 10, 10, 1, 1, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 12, 4, 7, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5,
5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 5, 6, 5, 5, 5, 5, 6, 6, 6, 6, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 5, 5, 5, 5, 1,
];
if i < VALS.len() {
if i == 0 && enc.min_enc_len() > 1 {
20
} else {
VALS[i] as i32
}
} else {
4
}
}
fn distance_value(mm: &MinMaxLen) -> i32 {
static DIST_VALS: [i16; 100] = [
1000, 500, 333, 250, 200, 167, 143, 125, 111, 100, 91, 83, 77, 71, 67, 63, 59, 56, 53, 50,
48, 45, 43, 42, 40, 38, 37, 36, 34, 33, 32, 31, 30, 29, 29, 28, 27, 26, 26, 25, 24, 24, 23,
23, 22, 22, 21, 21, 20, 20, 20, 19, 19, 19, 18, 18, 18, 17, 17, 17, 16, 16, 16, 16, 15, 15,
15, 15, 14, 14, 14, 14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 11, 11, 11,
11, 11, 11, 11, 11, 11, 10, 10, 10, 10, 10,
];
if mm.max == INFINITE_LEN {
return 0;
}
let d = (mm.max - mm.min) as usize;
if d < DIST_VALS.len() {
DIST_VALS[d] as i32
} else {
1
}
}
fn comp_distance_value(d1: &MinMaxLen, d2: &MinMaxLen, v1: i32, v2: i32) -> i32 {
if v2 <= 0 {
return -1;
}
if v1 <= 0 {
return 1;
}
let v1 = v1 * distance_value(d1);
let v2 = v2 * distance_value(d2);
if v2 > v1 {
return 1;
}
if v2 < v1 {
return -1;
}
if d2.min < d1.min {
return 1;
}
if d2.min > d1.min {
return -1;
}
0
}
fn concat_opt_anc_info(
to: &mut OptAnc,
left: &OptAnc,
right: &OptAnc,
left_len: OnigLen,
right_len: OnigLen,
) {
to.clear();
to.left = left.left;
if left_len == 0 {
to.left |= right.left;
}
to.right = right.right;
if right_len == 0 {
to.right |= left.right;
} else {
to.right |= left.right & ANCR_PREC_READ_NOT;
}
}
fn is_left_anchor(a: i32) -> bool {
!(a == ANCR_END_BUF
|| a == ANCR_SEMI_END_BUF
|| a == ANCR_END_LINE
|| a == ANCR_PREC_READ
|| a == ANCR_PREC_READ_NOT)
}
fn is_set_opt_anc_info(to: &OptAnc, anc: i32) -> bool {
(to.left & anc) != 0 || (to.right & anc) != 0
}
fn add_opt_anc_info(to: &mut OptAnc, anc: i32) {
if is_left_anchor(anc) {
to.left |= anc;
} else {
to.right |= anc;
}
}
fn remove_opt_anc_info(to: &mut OptAnc, anc: i32) {
if is_left_anchor(anc) {
to.left &= !anc;
} else {
to.right &= !anc;
}
}
fn alt_merge_opt_anc_info(to: &mut OptAnc, add: &OptAnc) {
to.left &= add.left;
to.right &= add.right;
}
fn concat_opt_exact(to: &mut OptStr, add: &OptStr, enc: OnigEncoding) -> i32 {
let mut r = 0;
let mut i = to.len;
let mut p = 0usize; // index into add.s
let end = add.len;
while p < end {
let len = enclen(enc, &add.s[p..], p);
if i + len > OPT_EXACT_MAXLEN {
r = 1;
break;
}
for j in 0..len {
if p >= end {
break;
}
to.s[i] = add.s[p];
i += 1;
p += 1;
let _ = j;
}
}
to.len = i;
to.reach_end = if p == end { add.reach_end } else { 0 };
let mut tanc = OptAnc::new();
concat_opt_anc_info(&mut tanc, &to.anc, &add.anc, 1, 1);
if to.reach_end == 0 {
tanc.right = 0;
}
to.anc = tanc;
r
}
fn concat_opt_exact_str(to: &mut OptStr, s: &[u8], enc: OnigEncoding) {
let mut i = to.len;
let mut p = 0usize;
while p < s.len() && i < OPT_EXACT_MAXLEN {
let len = enclen(enc, &s[p..], p);
if i + len > OPT_EXACT_MAXLEN {
break;
}
for _ in 0..len {
if p >= s.len() {
break;
}
to.s[i] = s[p];
i += 1;
p += 1;
}
}
to.len = i;
if p >= s.len() {
to.reach_end = 1;
}
}
fn alt_merge_opt_exact(to: &mut OptStr, add: &OptStr, env_enc: OnigEncoding) {
if add.len == 0 || to.len == 0 {
to.clear();
return;
}
if !to.mm.is_equal(&add.mm) {
to.clear();
return;
}
let mut i = 0;
while i < to.len && i < add.len {
if to.s[i] != add.s[i] {
break;
}
let len = enclen(env_enc, &to.s[i..], i);
let mut ok = true;
for j in 1..len {
if i + j >= to.len || i + j >= add.len || to.s[i + j] != add.s[i + j] {
ok = false;
break;
}
}
if !ok {
break;
}
i += len;
}
if add.reach_end == 0 || i < add.len || i < to.len {
to.reach_end = 0;
}
to.len = i;
alt_merge_opt_anc_info(&mut to.anc, &add.anc);
if to.reach_end == 0 {
to.anc.right = 0;
}
}
fn select_opt_exact(enc: OnigEncoding, now: &mut OptStr, alt: &OptStr) {
let mut vn = now.len as i32;
let mut va = alt.len as i32;
if va == 0 {
return;
}
if vn == 0 {
*now = *alt;
return;
}
if vn <= 2 && va <= 2 {
va = map_position_value(enc, now.s[0] as usize);
vn = map_position_value(enc, alt.s[0] as usize);
if now.len > 1 {
vn += 5;
}
if alt.len > 1 {
va += 5;
}
}
vn *= 2;
va *= 2;
if comp_distance_value(&now.mm, &alt.mm, vn, va) > 0 {
*now = *alt;
}
}
fn add_char_opt_map(m: &mut OptMap, c: u8, enc: OnigEncoding) {
if m.map[c as usize] == 0 {
m.map[c as usize] = 1;
m.value += map_position_value(enc, c as usize);
}
}
fn select_opt_map(now: &mut OptMap, alt: &OptMap) {
let z: i32 = 1 << 15;
if alt.value == 0 {
return;
}
if now.value == 0 {
*now = *alt;
return;
}
let vn = z / now.value;
let va = z / alt.value;
if comp_distance_value(&now.mm, &alt.mm, vn, va) > 0 {
*now = *alt;
}
}
fn comp_opt_exact_or_map(e: &OptStr, m: &OptMap) -> i32 {
const COMP_EM_BASE: i32 = 20;
if m.value <= 0 {
return -1;
}
let case_value = 3;
let ae = COMP_EM_BASE * e.len as i32 * case_value;
let am = COMP_EM_BASE * 5 * 2 / m.value;
comp_distance_value(&e.mm, &m.mm, ae, am)
}
fn alt_merge_opt_map(enc: OnigEncoding, to: &mut OptMap, add: &OptMap) {
if to.value == 0 {
return;
}
if add.value == 0 || to.mm.max < add.mm.min {
to.clear();
return;
}
to.mm.alt_merge(&add.mm);
let mut val = 0;
for i in 0..CHAR_MAP_SIZE {
if add.map[i] != 0 {
to.map[i] = 1;
}
if to.map[i] != 0 {
val += map_position_value(enc, i);
}
}
to.value = val;
alt_merge_opt_anc_info(&mut to.anc, &add.anc);
}
fn set_bound_node_opt_info(opt: &mut OptNode, plen: &MinMaxLen) {
opt.sb.mm = *plen;
opt.spr.mm = *plen;
opt.map.mm = *plen;
}
fn concat_left_node_opt_info(enc: OnigEncoding, to: &mut OptNode, add: &mut OptNode) {
let mut tanc = OptAnc::new();
concat_opt_anc_info(&mut tanc, &to.anc, &add.anc, to.len.max, add.len.max);
to.anc = tanc;
if add.sb.len > 0 && to.len.max == 0 {
let mut tanc2 = OptAnc::new();
concat_opt_anc_info(&mut tanc2, &to.anc, &add.sb.anc, to.len.max, add.len.max);
add.sb.anc = tanc2;
}
if add.map.value > 0 && to.len.max == 0 && add.map.mm.max == 0 {
add.map.anc.left |= to.anc.left;
}
let sb_reach = to.sb.reach_end;
let sm_reach = to.sm.reach_end;
if add.len.max != 0 {
to.sb.reach_end = 0;
to.sm.reach_end = 0;
}
if add.sb.len > 0 {
if sb_reach != 0 {
concat_opt_exact(&mut to.sb, &add.sb, enc);
add.sb.clear();
} else if sm_reach != 0 {
concat_opt_exact(&mut to.sm, &add.sb, enc);
add.sb.clear();
}
}
select_opt_exact(enc, &mut to.sm, &add.sb);
select_opt_exact(enc, &mut to.sm, &add.sm);
if to.spr.len > 0 {
if add.len.max > 0 {
if to.spr.mm.max == 0 {
select_opt_exact(enc, &mut to.sb, &to.spr.clone());
} else {
select_opt_exact(enc, &mut to.sm, &to.spr.clone());
}
}
} else if add.spr.len > 0 {
to.spr = add.spr;
}
select_opt_map(&mut to.map, &add.map);
to.len.add(&add.len);
}
fn alt_merge_node_opt_info(to: &mut OptNode, add: &OptNode, env_enc: OnigEncoding) {
alt_merge_opt_anc_info(&mut to.anc, &add.anc);
alt_merge_opt_exact(&mut to.sb, &add.sb, env_enc);
alt_merge_opt_exact(&mut to.sm, &add.sm, env_enc);
alt_merge_opt_exact(&mut to.spr, &add.spr, env_enc);
alt_merge_opt_map(env_enc, &mut to.map, &add.map);
to.len.alt_merge(&add.len);
}
fn node_max_byte_len(node: &Node, env: &ParseEnv) -> OnigLen {
match &node.inner {
NodeInner::List(_) => {
let mut len: OnigLen = 0;
let mut cur = node;
while let NodeInner::List(cons) = &cur.inner {
let tmax = node_max_byte_len(&cons.car, env);
len = distance_add(len, tmax);
match &cons.cdr {
Some(next) => cur = next,
None => break,
}
}
len
}
NodeInner::Alt(_) => {
let mut len: OnigLen = 0;
let mut cur = node;
while let NodeInner::Alt(cons) = &cur.inner {
let tmax = node_max_byte_len(&cons.car, env);
if len < tmax {
len = tmax;
}
match &cons.cdr {
Some(next) => cur = next,
None => break,
}
}
len
}
NodeInner::String(sn) => sn.s.len() as OnigLen,
NodeInner::CType(_) | NodeInner::CClass(_) => env.enc.max_enc_len() as OnigLen,
NodeInner::BackRef(_) => {
if node.has_status(ND_ST_CHECKER) {
0
} else {
// Following a backreference would leave the ownership tree through
// a raw capture pointer. An unbounded maximum is conservative and
// only disables optimizations that require a finite upper bound.
INFINITE_LEN
}
}
// Calls are self-referential AST edges. Staying inside the ownership tree
// avoids aliasing their raw targets; an infinite maximum is conservative.
NodeInner::Call(_) => INFINITE_LEN,
NodeInner::Quant(qn) => {
if qn.upper == 0 {
0
} else if let Some(ref body) = qn.body {
let len = node_max_byte_len(body, env);
if len != 0 {
if !is_infinite_repeat(qn.upper) {
distance_multiply(len, qn.upper)
} else {
INFINITE_LEN
}
} else {
0
}
} else {
0
}
}
NodeInner::Bag(bn) => match bn.bag_type {
BagType::Memory => {
// Calls and backreferences above are conservative leaves, so this
// traversal cannot cycle and needs no mutation-based cache.
if let Some(ref body) = bn.body {
node_max_byte_len(body, env)
} else {
0
}
}
BagType::Option | BagType::StopBacktrack => {
if let Some(ref body) = bn.body {
node_max_byte_len(body, env)
} else {
0
}
}
BagType::IfElse => {
if let BagData::IfElse {
ref then_node,
ref else_node,
} = bn.bag_data
{
let mut len = if let Some(ref body) = bn.body {
node_max_byte_len(body, env)
} else {
0
};
if let Some(ref then_n) = then_node {
let tlen = node_max_byte_len(then_n, env);
len = distance_add(len, tlen);
}
let elen = if let Some(ref else_n) = else_node {
node_max_byte_len(else_n, env)
} else {
0
};
if elen > len {
elen
} else {
len
}
} else {
0
}
}
},
NodeInner::Anchor(_) | NodeInner::Gimmick(_) => 0,
}
}
fn optimize_nodes(
node: &Node,
opt: &mut OptNode,
env_enc: OnigEncoding,
env_mm: &mut MinMaxLen,
scan_env: &ParseEnv,
) -> i32 {
let enc = env_enc;
opt.clear();
set_bound_node_opt_info(opt, env_mm);
// Literal alternation trie: we don't know the exact match length
// (it's variable), so just set min=1, max=large and skip detailed opts.
if node.has_status(ND_ST_LITERAL_ALT) {
opt.len.set(1, INFINITE_LEN);
return 0;
}
match &node.inner {
NodeInner::List(_) => {
let mut nenv_mm = *env_mm;
let mut cur = node;
while let NodeInner::List(cons) = &cur.inner {
let mut xo = OptNode::new();
let r = optimize_nodes(&cons.car, &mut xo, enc, &mut nenv_mm, scan_env);
if r != 0 {
return r;
}
nenv_mm.add(&xo.len);
concat_left_node_opt_info(enc, opt, &mut xo);
match &cons.cdr {
Some(next) => cur = next,
None => break,
}
}
}
NodeInner::Alt(_) => {
let mut first = true;
let mut cur = node;
while let NodeInner::Alt(cons) = &cur.inner {
let mut xo = OptNode::new();
let r = optimize_nodes(&cons.car, &mut xo, enc, env_mm, scan_env);
if r != 0 {
return r;
}
if first {
*opt = xo;
first = false;
} else {
alt_merge_node_opt_info(opt, &xo, enc);
}
match &cons.cdr {
Some(next) => cur = next,
None => break,
}
}
}
NodeInner::String(sn) => {
let slen = sn.s.len();
concat_opt_exact_str(&mut opt.sb, &sn.s, enc);
if slen > 0 {
add_char_opt_map(&mut opt.map, sn.s[0], enc);
}
opt.len.set(slen as OnigLen, slen as OnigLen);
}
NodeInner::CClass(cc) => {
if cc.mbuf.is_some() || cc.is_not() {
let min = enc.min_enc_len() as OnigLen;
let max = enc.max_enc_len() as OnigLen;
// Even with multi-byte ranges or negation, compute the ASCII
// part of the map from the bitset. For non-ASCII lead bytes
// (0x80-0xFF), mark them all as possible since any multi-byte
// sequence could start there.
for i in 0..SINGLE_BYTE_SIZE {
let z = bitset_at(&cc.bs, i);
if (z && !cc.is_not()) || (!z && cc.is_not()) {
add_char_opt_map(&mut opt.map, i as u8, enc);
}
}
// This branch is entered when cc.mbuf.is_some() || cc.is_not().
// In both cases, multi-byte characters may match, so mark all
// lead bytes >= 0x80 as possible.
for i in 0x80..SINGLE_BYTE_SIZE {
add_char_opt_map(&mut opt.map, i as u8, enc);
}
opt.len.set(min, max);
} else {
for i in 0..SINGLE_BYTE_SIZE {
let z = bitset_at(&cc.bs, i);
if (z && !cc.is_not()) || (!z && cc.is_not()) {
add_char_opt_map(&mut opt.map, i as u8, enc);
}
}
opt.len.set(1, 1);
}
}
NodeInner::CType(ct) => {
let max = enc.max_enc_len() as OnigLen;
let min = if max == 1 {
1
} else {
enc.min_enc_len() as OnigLen
};
// Compute first-byte map for word, space, and digit types.
// For multi-byte encodings (UTF-8), limit positive matches to ASCII
// range (0-127) since those are the only single-byte characters.
match ct.ctype {
CTYPE_ANYCHAR => { /* nothing to add to map */ }
_ if ct.ctype == crate::oniguruma::ONIGENC_CTYPE_WORD as i32
|| ct.ctype == crate::oniguruma::ONIGENC_CTYPE_SPACE as i32
|| ct.ctype == crate::oniguruma::ONIGENC_CTYPE_DIGIT as i32 =>
{
let ctype_u32 = ct.ctype as u32;
let range = if ct.ascii_mode || max > 1 {
128
} else {
SINGLE_BYTE_SIZE
};
if ct.not {
for i in 0..range {
if !enc.is_code_ctype(i as u32, ctype_u32) {
add_char_opt_map(&mut opt.map, i as u8, enc);
}
}
for i in range..SINGLE_BYTE_SIZE {
add_char_opt_map(&mut opt.map, i as u8, enc);
}
} else {
for i in 0..range {
if enc.is_code_ctype(i as u32, ctype_u32) {
add_char_opt_map(&mut opt.map, i as u8, enc);
}
}
if max > 1 && !ct.ascii_mode {
// Non-ASCII-mode: Unicode spaces/words/digits may
// start with lead bytes >= 0x80
for i in 0x80..SINGLE_BYTE_SIZE {
add_char_opt_map(&mut opt.map, i as u8, enc);
}
}
}
}
_ => {}
}
opt.len.set(min, max);
}
NodeInner::Anchor(an) => {
match an.anchor_type {
ANCR_BEGIN_BUF | ANCR_BEGIN_POSITION | ANCR_BEGIN_LINE | ANCR_END_BUF
| ANCR_SEMI_END_BUF | ANCR_END_LINE | ANCR_PREC_READ_NOT | ANCR_LOOK_BEHIND => {
add_opt_anc_info(&mut opt.anc, an.anchor_type);
}
ANCR_PREC_READ => {
if let Some(ref body) = an.body {
let mut xo = OptNode::new();
let r = optimize_nodes(body, &mut xo, enc, env_mm, scan_env);
if r == 0 {
if xo.sb.len > 0 {
opt.spr = xo.sb;
} else if xo.sm.len > 0 {
opt.spr = xo.sm;
}
opt.spr.reach_end = 0;
if xo.map.value > 0 {
opt.map = xo.map;
}
}
}
}
_ => { /* ANCR_LOOK_BEHIND_NOT etc. */ }
}
}
NodeInner::BackRef(_br) => {
if !node.has_status(ND_ST_CHECKER) {
let min = node_min_byte_len(node, scan_env);
let max = node_max_byte_len(node, scan_env);
opt.len.set(min, max);
}
}
// Calls are self-referential AST edges. Use conservative optimization
// bounds instead of following their raw target pointers.
NodeInner::Call(_) => opt.len.set(0, INFINITE_LEN),
NodeInner::Quant(qn) => {
if qn.upper == 0 {
opt.len.set(0, 0);
} else if let Some(ref body) = qn.body {
let mut xo = OptNode::new();
let r = optimize_nodes(body, &mut xo, enc, env_mm, scan_env);
if r != 0 {
return r;
}
if qn.lower > 0 {
*opt = xo.clone();
if xo.sb.len > 0 && xo.sb.reach_end != 0 {
let mut i = 2;
while i <= qn.lower && !opt.sb.is_full() {
let rc = concat_opt_exact(&mut opt.sb, &xo.sb, enc);
if rc > 0 {
break;
}
i += 1;
}
if i < qn.lower {
opt.sb.reach_end = 0;
}
}
if qn.lower != qn.upper {
opt.sb.reach_end = 0;
opt.sm.reach_end = 0;
}
if qn.lower > 1 {
opt.sm.reach_end = 0;
}
}
let max = if is_infinite_repeat(qn.upper) {
if env_mm.max == 0 && body.is_anychar() && qn.greedy {
if body.has_status(ND_ST_MULTILINE) {
add_opt_anc_info(&mut opt.anc, ANCR_ANYCHAR_INF_ML);
} else {
add_opt_anc_info(&mut opt.anc, ANCR_ANYCHAR_INF);
}
}
if xo.len.max > 0 {
INFINITE_LEN
} else {
0
}
} else {
distance_multiply(xo.len.max, qn.upper)
};
let min = distance_multiply(xo.len.min, qn.lower);
opt.len.set(min, max);
}
}
NodeInner::Bag(bn) => match bn.bag_type {
BagType::StopBacktrack | BagType::Option => {
if let Some(ref body) = bn.body {
let r = optimize_nodes(body, opt, enc, env_mm, scan_env);
if r != 0 {
return r;
}
}
}
BagType::Memory => {
if let Some(ref body) = bn.body {
let r = optimize_nodes(body, opt, enc, env_mm, scan_env);
if r != 0 {
return r;
}
if is_set_opt_anc_info(&opt.anc, ANCR_ANYCHAR_INF_MASK)
&& mem_status_at(scan_env.backrefed_mem, bn.regnum() as usize)
{
remove_opt_anc_info(&mut opt.anc, ANCR_ANYCHAR_INF_MASK);
}
}
}
BagType::IfElse => {
if let BagData::IfElse {
ref then_node,
ref else_node,
} = bn.bag_data
{
if else_node.is_some() {
let mut nenv_mm = *env_mm;
if let Some(ref body) = bn.body {
let mut xo = OptNode::new();
let r = optimize_nodes(body, &mut xo, enc, &mut nenv_mm, scan_env);
if r != 0 {
return r;
}
nenv_mm.add(&xo.len);
concat_left_node_opt_info(enc, opt, &mut xo);
}
if let Some(ref then_n) = then_node {
let mut xo = OptNode::new();
let r = optimize_nodes(then_n, &mut xo, enc, &mut nenv_mm, scan_env);
if r != 0 {
return r;
}
concat_left_node_opt_info(enc, opt, &mut xo);
}
if let Some(ref else_n) = else_node {
let mut xo = OptNode::new();
let r = optimize_nodes(else_n, &mut xo, enc, env_mm, scan_env);
if r != 0 {
return r;
}
alt_merge_node_opt_info(opt, &xo, enc);
}
}
}
}
},
NodeInner::Gimmick(_) => {}
}
0
}
/// Build Sunday quick search / BMH skip table for exact string matching.
/// Mirrors C's set_sunday_quick_search_or_bmh_skip_table.
fn set_sunday_quick_search_or_bmh_skip_table(
enc: OnigEncoding,
s: &[u8],
skip: &mut [u8; CHAR_MAP_SIZE],
roffset: &mut i32,
) -> i32 {
let mut offset = crate::regenc::enc_get_skip_offset(enc) as i32;
if offset == 7 {
// ENC_SKIP_OFFSET_1_OR_0
let mut p = 0;
loop {
let len = enclen(enc, &s[p..], p);
if p + len >= s.len() {
offset = if len == 1 { 1 } else { 0 };
break;
}
p += len;
}
}
let slen = s.len() as i32;
if slen + offset >= 255 {
return ONIGERR_PARSER_BUG;
}
*roffset = offset;
skip.fill((slen + offset) as u8);
let mut p = 0;
while p < s.len() {
let clen = {
let l = enclen(enc, &s[p..], p);
if p + l > s.len() {
s.len() - p
} else {
l
}
};
let remaining = (s.len() - p) as i32;
for j in 0..clen {
let z = remaining - j as i32 + (offset - 1);
if z <= 0 {
break;
}
skip[s[p + j] as usize] = z as u8;
}
p += clen;
}
0
}
fn set_optimize_exact(reg: &mut RegexType, e: &OptStr) -> i32 {
if e.len == 0 {
return 0;
}
reg.exact = e.s[..e.len].to_vec();
let allow_reverse = reg.enc.is_allowed_reverse_match(®.exact);
if e.len >= 2 || (e.len >= 1 && allow_reverse) {
let exact_copy = reg.exact.clone();
let r = set_sunday_quick_search_or_bmh_skip_table(
reg.enc,
&exact_copy,
&mut reg.map,
&mut reg.map_offset,
);
if r != 0 {
return r;
}
reg.optimize = if allow_reverse {
OptimizeType::StrFast
} else {
OptimizeType::StrFastStepForward
};
} else {
reg.optimize = OptimizeType::Str;
}
reg.dist_min = e.mm.min;
reg.dist_max = e.mm.max;
if reg.dist_min != INFINITE_LEN {
reg.threshold_len = (reg.dist_min as i32) + (reg.exact.len() as i32);
}
0
}
fn set_optimize_map(reg: &mut RegexType, m: &OptMap) {
reg.map = m.map;
reg.optimize = OptimizeType::Map;
reg.dist_min = m.mm.min;
reg.dist_max = m.mm.max;
if reg.dist_min != INFINITE_LEN {
reg.threshold_len = (reg.dist_min as i32) + (reg.enc.min_enc_len() as i32);
}
// Precompute distinct set bytes for SIMD-accelerated map_search.
// Only accelerate when all set bytes are ASCII (< 0x80) to avoid
// false positives from UTF-8 continuation bytes.
let mut bytes = [0u8; 3];
let mut count: u8 = 0;
for i in 0..CHAR_MAP_SIZE {
if m.map[i] != 0 {
if count >= 3 || i >= 0x80 {
count = 0;
break;
}
bytes[count as usize] = i as u8;
count += 1;
}
}
reg.map_bytes = bytes;
reg.map_byte_count = count;
}
fn set_sub_anchor(reg: &mut RegexType, anc: &OptAnc) {
reg.sub_anchor |= anc.left & ANCR_BEGIN_LINE;
reg.sub_anchor |= anc.right & ANCR_END_LINE;
}
fn set_optimize_info_from_tree(root: &Node, reg: &mut RegexType, scan_env: &ParseEnv) -> i32 {
let mut env_mm = MinMaxLen::new();
let mut opt = OptNode::new();
let r = optimize_nodes(root, &mut opt, reg.enc, &mut env_mm, scan_env);
if r != 0 {
return r;
}
reg.anchor = opt.anc.left
& (ANCR_BEGIN_BUF
| ANCR_BEGIN_POSITION
| ANCR_ANYCHAR_INF
| ANCR_ANYCHAR_INF_ML
| ANCR_LOOK_BEHIND);
if (opt.anc.left & (ANCR_LOOK_BEHIND | ANCR_PREC_READ_NOT)) != 0 {
reg.anchor &= !ANCR_ANYCHAR_INF_ML;
}
reg.anchor |= opt.anc.right & (ANCR_END_BUF | ANCR_SEMI_END_BUF | ANCR_PREC_READ_NOT);
if (reg.anchor & (ANCR_END_BUF | ANCR_SEMI_END_BUF)) != 0 {
reg.anc_dist_min = opt.len.min;
reg.anc_dist_max = opt.len.max;
}
// Save first-byte map for regset dispatch before the main optimization
// choice potentially overwrites reg.map with BMH skip table data.
if opt.map.value > 0 && opt.map.mm.min == 0 {
reg.first_byte_map = opt.map.map;
reg.has_first_byte_map = true;
}
if opt.sb.len > 0 || opt.sm.len > 0 {
select_opt_exact(reg.enc, &mut opt.sb, &opt.sm);
if opt.map.value > 0 && comp_opt_exact_or_map(&opt.sb, &opt.map) > 0 {
set_optimize_map(reg, &opt.map);
set_sub_anchor(reg, &opt.map.anc);
} else {
let r = set_optimize_exact(reg, &opt.sb);
if r != 0 {
return r;
}
set_sub_anchor(reg, &opt.sb.anc);
}
} else if opt.map.value > 0 {
set_optimize_map(reg, &opt.map);
set_sub_anchor(reg, &opt.map.anc);
} else {
reg.sub_anchor |= opt.anc.left & ANCR_BEGIN_LINE;
if opt.len.max == 0 {
reg.sub_anchor |= opt.anc.right & ANCR_END_LINE;
}
}
0
}
/// Full compilation entry point - mirrors C's onig_compile().
/// Parses pattern, compiles to bytecode, sets up mem status and stack_pop_level.
pub fn onig_compile(reg: &mut RegexType, pattern: &[u8]) -> i32 {
// Clear previous bytecode
reg.ops.clear();
// Parse the pattern into AST
let mut env = ParseEnv {
options: reg.options,
case_fold_flag: reg.case_fold_flag,
enc: reg.enc,
syntax: reg.syntax.clone(),
cap_history: 0,
backtrack_mem: 0,
backrefed_mem: 0,
pattern: std::ptr::null(),
pattern_end: std::ptr::null(),
error: std::ptr::null(),
error_end: std::ptr::null(),
reg: reg as *mut RegexType,
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,
};
let mut root = match crate::regparse::onig_parse_tree(pattern, reg, &mut env) {
Ok(node) => node,
Err(e) => return e,
};
// CAPTURE_ONLY_NAMED_GROUP: when named groups exist, disable unnamed captures
if env.num_named > 0
&& is_syntax_bv(&env.syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP)
&& !opton_capture_group(reg.options)
{
let r = if env.num_named != env.num_mem {
disable_noname_group_capture(&mut root, reg, &mut env)
} else {
numbered_ref_check(&root)
};
if r != 0 {
return r;
}
}
// Optimize: consolidate adjacent string nodes (mirrors C's reduce_string_list)
let r = reduce_string_list(&mut root, reg.enc);
if r != 0 {
return r;
}
refresh_node_references(&mut root, &mut env);
// Resolve subroutine call references before tune_tree
if env.num_call > 0 {
let r = resolve_call_references(&mut root, reg, &mut env);
if r != 0 {
return r;
}
let mut called_groups = Vec::new();
collect_called_groups(&root, &mut called_groups);
mark_called_groups(&mut root, &called_groups);
// Mark zero-repeat contexts and adjust entry counts
tune_call(&mut root, 0);
// Conservatively avoid single-entry optimizations for called groups.
// The historical transitive traversal followed self-referential raw
// pointers and was not alias-safe under Miri.
mark_called_groups_as_multi_entry(&mut root);
// Analyze subroutine-call cycles without re-entering the AST through
// self-referential raw pointers.
let recursive_groups = analyze_call_graph(&mut root, &mut env);
// A zero-length recursive group cannot make progress and would recurse
// forever. This graph check avoids re-entering the AST through raw
// self-references while preserving the compiler's rejection behavior.
let must_recurse_groups = analyze_must_recurse_groups(&root, &recursive_groups, &env);
if has_never_ending_recursion(&root, &recursive_groups, &must_recurse_groups) {
return ONIGERR_NEVER_ENDING_RECURSION;
}
// Propagate state flags (IN_ALT, IN_REAL_REPEAT, etc.) through called groups
tune_called_state(&mut root, 0);
}
// Detect literal alternations and replace with trie (before tune_tree
// so case-fold expansion hasn't rewritten the string nodes yet).
detect_literal_alternations(&mut root, reg, env.backrefed_mem);
refresh_node_references(&mut root, &mut env);
// Tune tree: detect empty loops, propagate state (mirrors C's tune_tree)
let r = tune_tree(&mut root, reg, 0, &mut env);
if r != 0 {
return r;
}
refresh_node_references(&mut root, &mut env);
// Compute empty_status_mem for quantifiers (determines EmptyCheckEnd vs EmptyCheckEndMemst)
setup_empty_status_mem(&mut root, &mut env);
// Set capture/mem tracking from parse env (mirrors C's onig_compile post-parse setup)
reg.capture_history = env.cap_history;
reg.push_mem_start = env.backtrack_mem | env.cap_history;
reg.num_mem = env.num_mem;
// Set push_mem_end
if mem_status_is_all_on(reg.push_mem_start) {
reg.push_mem_end = env.backrefed_mem | env.cap_history;
} else {
reg.push_mem_end = reg.push_mem_start & (env.backrefed_mem | env.cap_history);
}
// Initialize mark/save ID counter from parse env to avoid collisions
// (C uses ID_ENTRY(env, id) which shares env->id_num between parser and compiler)
reg.num_call = env.id_num;
// Compile the tree to bytecode
let r = compile_tree(&root, reg, &env);
if r != 0 {
return r;
}
// Patch unresolved subroutine call addresses
if !reg.unset_call_addrs.is_empty() {
for &(op_idx, gnum) in ®.unset_call_addrs.clone() {
let gnum = gnum as usize;
if gnum < reg.called_addrs.len() && reg.called_addrs[gnum] >= 0 {
let addr = reg.called_addrs[gnum];
reg.ops[op_idx].payload = OperationPayload::Call { addr };
}
}
}
// Emit UPDATE_VAR(KeepFromStackLast) before OP_END if \K was used
if env.keep_num > 0 {
add_op(
reg,
OpCode::UpdateVar,
OperationPayload::UpdateVar {
var_type: UpdateVarType::KeepFromStackLast,
id: 0,
clear: false,
},
);
}
// Add OP_END
add_op(reg, OpCode::End, OperationPayload::None);
// If callouts exist, set push_mem_end (C: callout_num != 0 → push_mem_end = push_mem_start)
if let Some(ref ext) = reg.extp {
if ext.callout_num != 0 {
reg.push_mem_end = reg.push_mem_start;
}
}
// Set stack pop level based on what captures/features are used
let has_callouts = reg.extp.as_ref().is_some_and(|e| e.callout_num != 0);
if reg.push_mem_end != 0
|| reg.num_repeat != 0
|| reg.num_empty_check != 0
|| reg.num_call > 0
|| has_callouts
{
reg.stack_pop_level = StackPopLevel::All;
} else if reg.push_mem_start != 0 {
reg.stack_pop_level = StackPopLevel::MemStart;
} else {
reg.stack_pop_level = StackPopLevel::Free;
}
// Set optimization info (exact string, char map, anchors) from parse tree
let r = set_optimize_info_from_tree(&root, reg, &env);
if r != 0 {
return r;
}
// Build Aho-Corasick automaton for literal alternation patterns.
// This enables a single-pass scan instead of position-by-position matching.
// Supports both bare `alpha|beta` and captured `(alpha|beta)`.
if let Some((trie_idx, has_capture)) = detect_ac_eligible(reg) {
let trie = ®.literal_tries[trie_idx];
let ac = aho_corasick::AhoCorasick::builder()
.match_kind(aho_corasick::MatchKind::LeftmostFirst)
.ascii_case_insensitive(trie.is_case_insensitive())
.build(trie.literals());
if let Ok(ac) = ac {
reg.ac_alt = Some(ac);
reg.ac_alt_has_capture = has_capture;
}
}
refresh_capture_tracking_requirement(reg);
0
}
/// Detect if a compiled regex is eligible for Aho-Corasick fast path.
/// Returns `(trie_idx, has_capture)` if eligible.
///
/// Accepted patterns (no anchors):
/// - `AltLiterals, End` (bare alternation, no capture)
/// - `MemStart, AltLiterals, MemEnd, End` (single capture group)
/// - `MemStartPush, AltLiterals, MemEndPush, End` (single capture group, push variant)
fn detect_ac_eligible(reg: &RegexType) -> Option<(usize, bool)> {
if reg.anchor != 0 || reg.sub_anchor != 0 {
return None;
}
let ops = ®.ops;
let opcodes: Vec<OpCode> = ops.iter().map(|op| op.opcode).collect();
let (alt_idx, has_capture) = match opcodes.as_slice() {
[OpCode::AltLiterals, OpCode::End] if reg.num_mem == 0 => (0, false),
[OpCode::MemStart, OpCode::AltLiterals, OpCode::MemEnd, OpCode::End]
if reg.num_mem == 1 =>
{
(1, true)
}
[OpCode::MemStartPush, OpCode::AltLiterals, OpCode::MemEndPush, OpCode::End]
if reg.num_mem == 1 =>
{
(1, true)
}
_ => return None,
};
if let OperationPayload::AltLiterals { trie_idx } = ops[alt_idx].payload {
Some((trie_idx as usize, has_capture))
} else {
None
}
}
/// Create and compile a new regex - mirrors C's onig_new().
/// This is the main public API entry point.
pub fn onig_new(
pattern: &[u8],
option: OnigOptionType,
enc: OnigEncoding,
syntax: &OnigSyntaxType,
) -> Result<RegexType, crate::error::RegexError> {
// Validate options
if option.intersects(ONIG_OPTION_DONT_CAPTURE_GROUP)
&& option.intersects(ONIG_OPTION_CAPTURE_GROUP)
{
return Err(ONIGERR_INVALID_COMBINATION_OF_OPTIONS.into());
}
// Apply syntax default options (mirrors onig_reg_init)
let mut effective_option = option;
let syn = syntax;
if option.intersects(ONIG_OPTION_NEGATE_SINGLELINE) {
effective_option |= syn.options;
effective_option &= !ONIG_OPTION_SINGLELINE;
} else {
effective_option |= syn.options;
}
// Case fold flag setup
let mut case_fold_flag = ONIGENC_CASE_FOLD_MIN;
if effective_option.intersects(ONIG_OPTION_IGNORECASE_IS_ASCII) {
case_fold_flag &=
!(INTERNAL_ONIGENC_CASE_FOLD_MULTI_CHAR | ONIGENC_CASE_FOLD_TURKISH_AZERI);
case_fold_flag |= ONIGENC_CASE_FOLD_ASCII_ONLY;
}
let mut 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: effective_option,
syntax: syntax.clone(),
case_fold_flag,
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,
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 r = onig_compile(&mut reg, pattern);
if r != 0 {
return Err(r.into());
}
Ok(reg)
}
// ============================================================================
// Tests
// ============================================================================
#[cfg(test)]
mod tests {
use super::*;
use crate::regparse;
use crate::regsyntax::OnigSyntaxOniguruma;
fn make_test_context() -> (RegexType, ParseEnv) {
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: &crate::encodings::utf8::ONIG_ENCODING_UTF8,
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,
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: &crate::encodings::utf8::ONIG_ENCODING_UTF8,
syntax: OnigSyntaxOniguruma.clone(),
cap_history: 0,
backtrack_mem: 0,
backrefed_mem: 0,
pattern: std::ptr::null(),
pattern_end: std::ptr::null(),
error: std::ptr::null(),
error_end: std::ptr::null(),
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,
};
(reg, env)
}
fn parse_and_compile(pattern: &[u8]) -> Result<RegexType, i32> {
let (mut reg, mut env) = make_test_context();
let root = regparse::onig_parse_tree(pattern, &mut reg, &mut env)?;
let r = compile_from_tree(&root, &mut reg, &env);
if r != 0 {
return Err(r);
}
Ok(reg)
}
#[test]
fn compiled_regex_owns_caller_supplied_syntax() {
let mut reg = {
let mut syntax = OnigSyntaxOniguruma.clone();
syntax.op = 0;
onig_new(
b"literal",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&syntax,
)
.unwrap()
};
assert_eq!(reg.syntax.op, 0);
assert_eq!(onig_compile(&mut reg, b"literal"), 0);
}
#[test]
fn compile_literal_string() {
let reg = parse_and_compile(b"abc").unwrap();
assert!(!reg.ops.is_empty());
// Should have string op + END
let last = reg.ops.last().unwrap();
assert_eq!(last.opcode, OpCode::End);
}
#[test]
fn compile_alternation() {
let reg = parse_and_compile(b"a|b").unwrap();
// Should have PUSH + "a" + JUMP + "b" + END
assert!(reg.ops.len() >= 4);
assert_eq!(reg.ops[0].opcode, OpCode::Push);
assert_eq!(reg.ops.last().unwrap().opcode, OpCode::End);
}
#[test]
fn compile_star_quantifier() {
let reg = parse_and_compile(b"a*").unwrap();
// Should have PUSH + Str1 + JUMP + END
assert!(reg.ops.len() >= 3);
assert_eq!(reg.ops.last().unwrap().opcode, OpCode::End);
// Check that a PUSH and JUMP are present
let has_push = reg.ops.iter().any(|op| op.opcode == OpCode::Push);
let has_jump = reg.ops.iter().any(|op| op.opcode == OpCode::Jump);
assert!(has_push, "expected PUSH for a*");
assert!(has_jump, "expected JUMP for a*");
}
#[test]
fn compile_plus_quantifier() {
let reg = parse_and_compile(b"a+").unwrap();
// a+ = body + PUSH + body + JUMP
assert!(reg.ops.len() >= 3);
assert_eq!(reg.ops.last().unwrap().opcode, OpCode::End);
}
#[test]
fn compile_capture_group() {
let reg = parse_and_compile(b"(a)").unwrap();
let has_mem_start = reg
.ops
.iter()
.any(|op| op.opcode == OpCode::MemStart || op.opcode == OpCode::MemStartPush);
let has_mem_end = reg
.ops
.iter()
.any(|op| op.opcode == OpCode::MemEnd || op.opcode == OpCode::MemEndPush);
assert!(has_mem_start, "expected MemStart for (a)");
assert!(has_mem_end, "expected MemEnd for (a)");
}
#[test]
fn compile_char_class() {
let reg = parse_and_compile(b"[abc]").unwrap();
let has_cclass = reg.ops.iter().any(|op| op.opcode == OpCode::CClass);
assert!(has_cclass, "expected CClass for [abc]");
}
#[test]
fn compile_anchor_begin() {
let reg = parse_and_compile(b"^a").unwrap();
assert_eq!(reg.ops[0].opcode, OpCode::BeginLine);
}
#[test]
fn compile_word_type() {
let reg = parse_and_compile(b"\\w").unwrap();
let has_word = reg
.ops
.iter()
.any(|op| op.opcode == OpCode::Word || op.opcode == OpCode::WordAscii);
assert!(has_word, "expected Word for \\w");
}
#[test]
fn compile_interval_quantifier() {
// a{2,5} is compiled via greedy expansion: body*2 + 3*(PUSH+body)
let reg = parse_and_compile(b"a{2,5}").unwrap();
let has_push = reg.ops.iter().any(|op| op.opcode == OpCode::Push);
assert!(has_push, "expected Push for a{{2,5}} greedy expansion");
assert!(
!reg.ops.iter().any(|op| op.opcode == OpCode::Repeat),
"small interval should remain expanded"
);
}
#[test]
fn compile_over_limit_interval_quantifier_uses_repeat_bytecode() {
// This is intentionally small enough to stay safe on the vulnerable
// compiler path, while exceeding the upstream 10-op expansion budget.
let reg = parse_and_compile(b"a{6,7}").unwrap();
assert!(
reg.ops.iter().any(|op| op.opcode == OpCode::Repeat),
"over-limit interval should use bounded repeat bytecode"
);
assert_eq!(reg.repeat_range.len(), 1);
assert_eq!(reg.repeat_range[0].lower, 6);
assert_eq!(reg.repeat_range[0].upper, 7);
let re = crate::api::Regex::new("a{6,7}").unwrap();
assert!(re.is_match("aaaaaa"));
assert!(re.is_match("aaaaaaa"));
assert!(!re.is_match("aaaaa"));
}
#[test]
fn compile_over_limit_interval_with_unrelated_call_uses_repeat_bytecode() {
let mut reg = make_test_context().0;
assert_eq!(onig_compile(&mut reg, b"(?<digit>\\d)\\g<digit>a{6,7}"), 0);
assert!(
reg.ops.iter().any(|op| op.opcode == OpCode::Repeat),
"an unrelated subexpression call must not bypass the expansion limit"
);
assert_eq!(reg.repeat_range.len(), 1);
assert_eq!(reg.repeat_range[0].lower, 6);
assert_eq!(reg.repeat_range[0].upper, 7);
let re = crate::api::Regex::new(r"(?<digit>\d)\g<digit>a{6,7}").unwrap();
assert!(re.is_match("11aaaaaa"));
assert!(re.is_match("11aaaaaaa"));
assert!(!re.is_match("11aaaaa"));
}
#[test]
fn compile_complex_pattern() {
let reg = parse_and_compile(b"^[a-z]+\\d{2,4}$").unwrap();
assert_eq!(reg.ops.last().unwrap().opcode, OpCode::End);
// Just verify it compiles without error
}
#[test]
fn compile_empty_pattern() {
let reg = parse_and_compile(b"").unwrap();
assert_eq!(reg.ops.len(), 1); // Just END
assert_eq!(reg.ops[0].opcode, OpCode::End);
}
#[test]
fn compile_non_capturing_group() {
let reg = parse_and_compile(b"(?:abc)").unwrap();
// Non-capturing group should not emit MemStart/MemEnd
let has_mem_start = reg
.ops
.iter()
.any(|op| op.opcode == OpCode::MemStart || op.opcode == OpCode::MemStartPush);
assert!(
!has_mem_start,
"non-capturing group should not have MemStart"
);
assert_eq!(reg.ops.last().unwrap().opcode, OpCode::End);
}
#[test]
fn compile_lookahead() {
let reg = parse_and_compile(b"(?=abc)").unwrap();
let has_mark = reg.ops.iter().any(|op| op.opcode == OpCode::Mark);
let has_cut = reg.ops.iter().any(|op| op.opcode == OpCode::CutToMark);
assert!(has_mark, "expected Mark for lookahead");
assert!(has_cut, "expected CutToMark for lookahead");
}
#[test]
fn compile_negative_lookahead() {
let reg = parse_and_compile(b"(?!abc)").unwrap();
let has_fail = reg.ops.iter().any(|op| op.opcode == OpCode::Fail);
assert!(has_fail, "expected Fail for negative lookahead");
}
// ---- onig_new API tests ----
#[test]
fn onig_new_basic() {
let reg = onig_new(
b"abc",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&OnigSyntaxOniguruma,
)
.unwrap();
assert!(!reg.ops.is_empty());
assert_eq!(reg.ops.last().unwrap().opcode, OpCode::End);
}
#[test]
fn onig_new_with_captures() {
let reg = onig_new(
b"(a)(b)",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&OnigSyntaxOniguruma,
)
.unwrap();
assert_eq!(reg.num_mem, 2);
}
#[test]
fn onig_new_stack_pop_level_free() {
// Simple pattern with no captures => StackPopLevel::Free
let reg = onig_new(
b"abc",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&OnigSyntaxOniguruma,
)
.unwrap();
assert_eq!(reg.stack_pop_level, StackPopLevel::Free);
}
#[test]
fn onig_new_invalid_pattern() {
let result = onig_new(
b"(",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&OnigSyntaxOniguruma,
);
assert!(result.is_err());
}
#[test]
fn reduce_string_list_merges() {
// Parse "abc" - parser produces 3 single-char string nodes in a list
// reduce_string_list should merge them into one "abc" node
let (mut reg, mut env) = make_test_context();
let mut root = regparse::onig_parse_tree(b"abc", &mut reg, &mut env).unwrap();
// Before reduction, count the tree structure
let before_type = root.node_type();
// Apply reduction
let r = reduce_string_list(&mut root, env.enc);
assert_eq!(r, 0);
// After reduction, "abc" should be a single string node (not a list)
assert_eq!(root.node_type(), NodeType::String);
let s = root.as_str().unwrap();
assert_eq!(s.s, b"abc");
}
#[test]
fn reduce_string_list_preserves_non_strings() {
// "a.b" has string-dot-string, so strings cannot merge across the dot
let (mut reg, mut env) = make_test_context();
let mut root = regparse::onig_parse_tree(b"a.b", &mut reg, &mut env).unwrap();
let r = reduce_string_list(&mut root, env.enc);
assert_eq!(r, 0);
// Should still be a list with 3 elements
assert_eq!(root.node_type(), NodeType::List);
}
#[test]
fn test_never_ending_recursion_direct() {
let mut reg = make_test_context().0;
let r = onig_compile(&mut reg, b"(?<abc>\\g<abc>)");
assert_eq!(r, ONIGERR_NEVER_ENDING_RECURSION);
}
#[test]
fn test_never_ending_recursion_conditional() {
let mut reg = make_test_context().0;
let r = onig_compile(&mut reg, b"(()(?(2)\\g<1>))");
assert_eq!(r, ONIGERR_NEVER_ENDING_RECURSION);
}
#[test]
fn nullable_terminating_recursive_alternative_is_valid() {
let mut reg = make_test_context().0;
let r = onig_compile(&mut reg, b"(?<n>|a\\g<n>)+");
assert_eq!(r, ONIG_NORMAL);
}
#[test]
fn mutually_recursive_group_with_nullable_exit_is_valid() {
let mut reg = make_test_context().0;
let r = onig_compile(&mut reg, b"\\A(?<n>|a\\g<m>)\\z|\\zEND (?<m>\\g<n>)");
assert_eq!(r, ONIG_NORMAL);
}
#[test]
fn zero_repeat_called_group_keeps_callable_bytecode() {
let reg = onig_new(
b"(?P<name>abc){0}(?P>name)",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&crate::regsyntax::OnigSyntaxPython,
)
.unwrap();
assert!(
reg.called_addrs.get(1).is_some_and(|addr| *addr > 0),
"a group referenced outside a zero repeat must still be emitted"
);
}
#[test]
fn casefold_lookbehind_cclass_no_bloat() {
// Regression test: (?i) with [-\w] in a lookbehind must not generate
// hundreds of redundant multi-char case-fold lookbehind blocks.
// Without the optimization, (?i)(?<![-\w])x generates ~846 ops;
// with it, it should be ~9 ops (same as without (?i)).
let reg_ic = onig_new(
br"(?<![-\w])x",
ONIG_OPTION_IGNORECASE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&OnigSyntaxOniguruma,
)
.unwrap();
let reg_no_ic = onig_new(
br"(?<![-\w])x",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&OnigSyntaxOniguruma,
)
.unwrap();
// With optimization, both should produce the same number of ops
assert_eq!(
reg_ic.ops.len(),
reg_no_ic.ops.len(),
"(?i)(?<![-\\w])x should not bloat: got {} ops vs {} without (?i)",
reg_ic.ops.len(),
reg_no_ic.ops.len()
);
}
#[test]
fn literal_alt_trie_triggers() {
// 10 pure literal alternations — above threshold of 8
// Use onig_new (full pipeline) to include detect_literal_alternations
let reg = onig_new(
b"alpha|beta|gamma|delta|epsilon|zeta|eta|theta|iota|kappa",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&crate::regsyntax::OnigSyntaxOniguruma,
)
.unwrap();
assert_eq!(
reg.literal_tries.len(),
1,
"expected 1 literal trie, got {}",
reg.literal_tries.len()
);
let has_alt_literals = reg.ops.iter().any(|op| op.opcode == OpCode::AltLiterals);
assert!(has_alt_literals, "expected AltLiterals opcode in bytecode");
// Should NOT have Push/Jump from normal Alt compilation
let has_push = reg.ops.iter().any(|op| op.opcode == OpCode::Push);
assert!(
!has_push,
"should not have Push opcode for trie-optimized alt"
);
}
#[test]
fn literal_alt_trie_rejects_out_of_order_prefixes() {
// The prefix pair is intentionally non-adjacent in source order. The
// eligibility check must still leave this alternation on the ordered
// backtracking path.
let reg = onig_new(
b"foobarbaz|a1|a2|a3|a4|a5|a6|a7|a8|foo",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&crate::regsyntax::OnigSyntaxOniguruma,
)
.unwrap();
assert!(reg.literal_tries.is_empty());
}
#[test]
fn literal_alt_trie_below_threshold() {
// 3 alternations — below threshold, should NOT trigger
let reg = onig_new(
b"a|bb|ccc",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&crate::regsyntax::OnigSyntaxOniguruma,
)
.unwrap();
assert_eq!(reg.literal_tries.len(), 0);
let has_alt_literals = reg.ops.iter().any(|op| op.opcode == OpCode::AltLiterals);
assert!(!has_alt_literals);
}
#[test]
fn literal_alt_trie_match_works() {
use crate::api::Regex;
let re = Regex::new("alpha|beta|gamma|delta|epsilon|zeta|eta|theta|iota|kappa").unwrap();
// Match "eta" in "the eta value"
let m = re.find("the eta value").unwrap();
assert_eq!(m.start(), 4);
assert_eq!(m.end(), 7);
}
#[test]
fn literal_alt_trie_no_match() {
use crate::api::Regex;
let re = Regex::new("alpha|beta|gamma|delta|epsilon|zeta|eta|theta|iota|kappa").unwrap();
let result = re.find("no match here");
assert!(result.is_none());
}
#[test]
fn literal_alt_trie_mixed_non_literal_no_trigger() {
// Partial trie rewrites would reorder literal and non-literal branches.
let reg = onig_new(
b"a|bb|ccc|dd|eee|ff|ggg|hh|\\d+",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&crate::regsyntax::OnigSyntaxOniguruma,
)
.unwrap();
assert!(reg.literal_tries.is_empty());
let has_push = reg.ops.iter().any(|op| op.opcode == OpCode::Push);
assert!(
has_push,
"partial trie should still have Push for non-literal branch"
);
}
#[test]
fn literal_alt_trie_partial_match() {
// Mixed alternatives retain their original ordered branches.
use crate::api::Regex;
let re = Regex::new("alpha|beta|gamma|delta|epsilon|zeta|eta|theta|iota|[xy]z").unwrap();
assert!(re.as_raw().literal_tries.is_empty());
// Match a literal branch
let m = re.find("the eta value").unwrap();
assert_eq!(m.as_str(), "eta");
// Match the non-literal branch
let m2 = re.find("the xz value").unwrap();
assert_eq!(m2.as_str(), "xz");
}
#[test]
fn literal_alt_trie_too_few_literals_with_non_literal() {
// Only 2 literal + 1 non-literal = below threshold
let reg = onig_new(
b"a|bb|\\d+",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&crate::regsyntax::OnigSyntaxOniguruma,
)
.unwrap();
assert_eq!(reg.literal_tries.len(), 0);
}
#[test]
fn literal_alt_trie_inside_group() {
// CSS-like pattern: alternation inside non-capturing group with lookbehind/lookahead
let reg = onig_new(
b"(?:alpha|beta|gamma|delta|epsilon|zeta|eta|theta|iota|kappa)",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&crate::regsyntax::OnigSyntaxOniguruma,
)
.unwrap();
assert_eq!(
reg.literal_tries.len(),
1,
"should detect alt inside non-capturing group, got {}",
reg.literal_tries.len()
);
}
#[test]
fn literal_alt_trie_case_insensitive() {
// Case-insensitive alternatives stay on the general case-folding path.
let reg = onig_new(
b"(?i)(?:alpha|beta|gamma|delta|epsilon|zeta|eta|theta|iota|kappa)",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&crate::regsyntax::OnigSyntaxOniguruma,
)
.unwrap();
assert!(reg.literal_tries.is_empty());
// Verify case-insensitive matching
use crate::api::Regex;
let re =
Regex::new("(?i)(?:alpha|beta|gamma|delta|epsilon|zeta|eta|theta|iota|kappa)").unwrap();
let m = re.find("DELTA value").unwrap();
assert_eq!(m.as_str(), "DELTA");
}
#[test]
fn literal_alt_trie_css_like_pattern() {
// Mimics CSS property-names: (?i)(?<![-\w])(?:prop1|prop2|...)(?![-\w])
use crate::api::Regex;
let re = Regex::new(
r"(?i)(?<![-\w])(?:color|content|cursor|display|direction|float|font|height|left|margin|padding|position|right|top|width|z-index)(?![-\w])",
)
.unwrap();
assert!(re.as_raw().literal_tries.is_empty());
let has_alt_literals = re
.as_raw()
.ops
.iter()
.any(|op| op.opcode == OpCode::AltLiterals);
assert!(!has_alt_literals);
let m = re.find(" display: none").unwrap();
assert_eq!(m.as_str(), "display");
// Case insensitive
let m2 = re.find(" DISPLAY: none").unwrap();
assert_eq!(m2.as_str(), "DISPLAY");
// Should not match partial words
assert!(re.find("displaying").is_none());
}
// --- Nested alternation trie tests ---
#[test]
fn nested_alt_trie_simple() {
// a(b|c)d → should extract ["abd", "acd"] and trigger trie
// Need enough branches to exceed threshold, so use multiple nested alts
use crate::api::Regex;
let re = Regex::new("a(b|c|d|e|f)g").unwrap();
assert!(
!re.as_raw().literal_tries.is_empty(),
"nested alternation a(b|c|d|e|f)g should trigger trie"
);
let m = re.find("xaegx").unwrap();
assert_eq!(m.as_str(), "aeg");
let m2 = re.find("xacgx").unwrap();
assert_eq!(m2.as_str(), "acg");
}
#[test]
fn nested_alt_trie_optional() {
// Optional paths stay on the general Alt path to retain branch order.
use crate::api::Regex;
let re = Regex::new("ab(cd)?ef|abgh|abij|abkl|abmn").unwrap();
assert!(re.as_raw().literal_tries.is_empty());
// With optional present
let m = re.find("xabcdefx").unwrap();
assert_eq!(m.as_str(), "abcdef");
// Without optional
let m2 = re.find("xabefx").unwrap();
assert_eq!(m2.as_str(), "abef");
// Plain branch
let m3 = re.find("xabghx").unwrap();
assert_eq!(m3.as_str(), "abgh");
}
#[test]
fn nested_alt_trie_partial_with_cclass() {
// Mixed: nested structure with one CClass branch → partial optimization
use crate::api::Regex;
let re = Regex::new(r"a(b|c|d|e|f)g|[xy]z").unwrap();
assert!(
!re.as_raw().literal_tries.is_empty(),
"nested alt with partial non-literal should trigger partial trie"
);
// Match literal branch
let m = re.find("xabgx").unwrap();
assert_eq!(m.as_str(), "abg");
// Match non-literal branch
let m2 = re.find("xxzx").unwrap();
assert_eq!(m2.as_str(), "xz");
}
#[test]
fn nested_alt_trie_entity_like() {
// Mimics HTML entity pattern structure: nested trie encoded as regex
use crate::api::Regex;
let re = Regex::new(
"a(s(ymp(eq)?|cr|t)|n(d(slope|and)?|g(le|st|msd)?|e))|b(a(ck(sim(eq)?|prime|cong|epsilon)|r(vee|wed))|o(x(times|plus|minus|dl|dr|ul|ur|v[lrhHV]|h[dDuU])|t)|u(ll(et)?|mp(e(q)?)?)|l(ock|k[34])|e(caus(e)?|rnou|tween|mptyv)|ig(c(ap|up|irc)|o(dot|plus|times)|tri(angle(down|up|left|right)|angle)|s(qcup|tar)|vee|wedge)|n(ot|e(quiv)?)|r(eve|vbar)|s(cr|ol(b|hsub)?|im(e)?)|(?:N|b)rk|f(r|isht)|karow|pf|scr)",
)
.unwrap();
assert!(
!re.as_raw().literal_tries.is_empty(),
"entity-like nested pattern should trigger trie"
);
// Match some entity names
let m = re.find("xasymp;").unwrap();
assert_eq!(m.as_str(), "asymp");
let m2 = re.find("xasympeq;").unwrap();
assert_eq!(m2.as_str(), "asympeq");
let m3 = re.find("xandslope;").unwrap();
assert_eq!(m3.as_str(), "andslope");
let m4 = re.find("xboxplus;").unwrap();
assert_eq!(m4.as_str(), "boxplus");
}
#[test]
fn nested_alt_trie_backreferenced_capture_skipped() {
// Backreferenced capture group should NOT be optimized
use crate::api::Regex;
let re = Regex::new(r"(a|b|c|d|e)\1").unwrap();
// This should NOT trigger trie because the capture is backreferenced
// The alt itself has 5 branches but each is simple, so it might trigger
// for the inner alt. The key test is that it still works correctly.
let m = re.find("xaax").unwrap();
assert_eq!(m.as_str(), "aa");
assert!(re.find("xabx").is_none());
}
#[test]
fn nested_alt_trie_non_capturing_group() {
// Non-capturing group should be transparent
use crate::api::Regex;
let re = Regex::new("(?:a(?:b|c|d|e|f)g)").unwrap();
assert!(
!re.as_raw().literal_tries.is_empty(),
"nested alt in non-capturing groups should trigger trie"
);
let m = re.find("xadgx").unwrap();
assert_eq!(m.as_str(), "adg");
}
#[test]
fn nested_alt_trie_entity_diagnostic() {
// Compile the full HTML entity pattern to verify nested extraction
let reg = onig_new(
b"a(s(ymp(eq)?|cr|t)|n(d(slope|and)?|g(s(t|ph)|zarr|e|le|rt(vb(d)?)?|msd(aa)?)?|e)|c(y|irc|d|ute)?|tilde|o(pf|gon)|uml|p(id|os|prox(eq)?|acir)?|elig|f(r)?|l(pha|e(ph|fsym))|acute|ring|grave|m(p|a(cr|lg))|breve)|b(s(cr|im(e)?|ol(hsub|b)?|emi)|c(y|ong)|ig(s(tar|qcup)|c(irc|up|ap)|triangle(down|up)|o(times|dot|plus)|uplus|vee|wedge)|o(t(tom)?|pf|wtie)|u(ll(et)?|mp(e(q)?)?)|prime|e(caus(e)?|t(h|ween|a)|psi|rnou|mptyv)|karow|fr|l(ock|a(nk|ck(square|triangle(down|left|right)?|lozenge)))|a(ck(sim(eq)?|cong|prime|epsilon)|r(vee|wed(ge)?))|r(eve|vbar)|brk(tbrk)?)|c(s(cr|u(p(e)?|b(e)?))|h(cy|i|eck(mark)?)|ylcty|c(irc|ups(sm)?|edil|a(ps|ron))|tdot|ir(scir|c(eq|le(d(circ|dash|ast)))?|e|fnint|mid)?|o(n(int|g(dot)?)|p(y(sr)?|f|rod)|lon(e(q)?)?|m(p(fn|le(xes|ment))?|ma(t)?))|dot|u(darr(l|r)|p(s|c(up|ap)|or|dot|brcap)?|e(sc|pr)|vee|wed|larr(p)?|r(vearrow(left|right)|ly(eq(succ|prec)|vee|wedge)|arr(m)?|ren))|e(nt(erdot)?|dil|mptyv)|fr|lubs(uit)?|a(cute|p(s|c(up|ap)|dot|and|brcup)?|r(on|et))|r(oss|arr))|d(s(cr|trok|ol)|c(y|aron)|t(dot|ri(f)?)|i(sin|e|v(ide(ontimes)?|onx)?|am(s|ond(suit)?)?|gamma)|o(t(square|plus|eq(dot)?|minus)?|ublebarwedge|pf|wn(harpoon(left|right)|downarrows|arrow)|llar)|d(otseq|a(rr|gger))?|u(har|arr)|jcy|e(lta|g|mptyv)|f(isht|r)|lc(orn|rop)|a(sh(v)?|leth|rr|gger)|r(c(orn|rop)|bkarow)|bkarow|blac)",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&crate::regsyntax::OnigSyntaxOniguruma,
)
.unwrap();
eprintln!(
"Entity subset: {} literal tries, {} ops",
reg.literal_tries.len(),
reg.ops.len()
);
let alt_lit_count = reg
.ops
.iter()
.filter(|op| op.opcode == OpCode::AltLiterals)
.count();
let push_count = reg
.ops
.iter()
.filter(|op| op.opcode == OpCode::Push)
.count();
assert!(
!reg.literal_tries.is_empty(),
"entity pattern should produce at least 1 trie"
);
// Nested branches keep their normal ordered backtracking operations.
assert!(push_count > 0, "expected ordered Alt operations");
}
#[test]
fn dump_named_capture_bytecode() {
let pat = b"(?<year>\\d{4})-(?<month>\\d{2})-(?<day>\\d{2})";
let reg = onig_new(
pat,
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&crate::regsyntax::OnigSyntaxOniguruma,
)
.unwrap();
eprintln!("Bytecode ({} ops):", reg.ops.len());
for (i, op) in reg.ops.iter().enumerate() {
eprintln!(" [{:3}] {:?}", i, op.opcode);
}
eprintln!("push_mem_start: {}", reg.push_mem_start);
eprintln!("push_mem_end: {}", reg.push_mem_end);
}
#[test]
fn option_only_group_mid_pattern_keeps_ignorecase_semantics() {
let reg = onig_new(
b"a(?i)b|c",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&crate::regsyntax::OnigSyntaxOniguruma,
)
.unwrap();
assert!(
reg.ops.iter().any(|op| op.opcode == OpCode::CClass),
"expected case-folded branch bytecode"
);
let input_b = b"aB";
let input_c = b"aC";
let (result_b, _) = crate::regexec::onig_match(
®,
input_b,
input_b.len(),
0,
Some(OnigRegion::new()),
ONIG_OPTION_NONE,
);
let (result_c, _) = crate::regexec::onig_match(
®,
input_c,
input_c.len(),
0,
Some(OnigRegion::new()),
ONIG_OPTION_NONE,
);
assert_eq!(result_b, 2, "expected aB to match");
assert_eq!(result_c, 2, "expected aC to match");
}
#[test]
fn repeated_compile_absent_expr_backref_does_not_overflow() {
for _ in 0..2 {
let reg = onig_new(
br"(a)(?~|b|\1)",
ONIG_OPTION_NONE,
&crate::encodings::utf8::ONIG_ENCODING_UTF8,
&crate::regsyntax::OnigSyntaxOniguruma,
)
.unwrap();
std::mem::forget(reg);
}
}
}