ferroni
GuidePerformanceADRs
Skip to content

Rust-Only Optimizations and Performance Philosophy

Status

Accepted (amends ADR-001)

Context

ADR-001 states: "New features or optimizations should first be contributed upstream to C Oniguruma, then ported — not invented in the Rust port."

This policy served the project well during the initial port: it ensured correctness and prevented accidental divergence. However, Ferroni's primary workload — TextMate grammar tokenization for Shiki — creates performance requirements that the upstream C engine does not face. C Oniguruma is used via WASM in the JavaScript ecosystem (vscode-oniguruma), where compilation and matching overhead is dominated by the WASM boundary, not by regex engine internals.

Ferroni, running natively, exposes regex engine internals as the bottleneck. Specific patterns in real-world TextMate grammars (CSS property lists with 200+ alternations, HTML entity tries with 1,700+ nested branches) require optimizations that do not exist in C Oniguruma and would not benefit the upstream project.

Decision

Allow additive, Rust-only optimizations that do not modify the C-ported core engine, subject to the following criteria:

Acceptance criteria

An optimization may be implemented in Ferroni without upstream contribution when all of the following hold:

  1. Additive: The optimization is a new pass or data structure that layers on top of the C-ported code. It does not modify existing C-ported control flow, data structures, or function signatures.

  2. Guarded: The optimization activates only when specific conditions are met (e.g., alternation has ≥8 pure literal branches). Patterns that do not meet the conditions follow the original C code path unchanged.

  3. Measurable: The optimization produces a demonstrated improvement on a real-world workload (benchmark numbers required in the commit or PR).

  4. Non-regressive: The full C-parity test suite passes without modification. No existing pattern produces different match results. Current test counts come from scripts/count-tests.sh.

  5. Bounded complexity: The optimization has clear worst-case bounds (e.g., MAX_NESTED_TRIE_PATHS = 8192) and does not introduce unbounded memory or time growth.

Current Rust-only optimizations

Opt-in failed-state cache (src/match_cache.rs, regexec.rs, regset.rs)

  • Trigger: the match-cache Cargo feature and an explicit MatchCacheConfig on a regex or scanner. A work counter includes forward bytes since the last backtrack, as well as failures; ordinary short searches keep the fast loops.
  • Eligibility: exhaustive bytecode classification admits regular control flow and captures that matching does not read. Backreferences, look-arounds, subroutine calls, callouts, counted or empty-check repeats, and general atomic groups remain on the original path. A straight-line atomic character run is supported because it has one possible successful exit; the compiler introduces these runs automatically before disjoint literals.
  • Failure invariant: a bit for (instruction, subject position) is committed only after backtracking leaves that state's complete subtree. A successful return or limit error never commits pending states. Active character stars expose each character as a cache point, including low-backtrack loops that would otherwise rescan each suffix.
  • Bounds: the default 16 MiB budget includes failure bits and pending failure records. All patterns in one scanner share it. Compiled metadata and the existing VM stack are outside that cache budget. Budget or allocation failure releases the cache and resumes plain backtracking; existing retry and time limits still apply.
  • Lifetime: standalone searches start fresh and release cache allocations before returning their scratch state to thread-local storage. A scanner keeps failures only for the same immutable OnigString, logical end, options, and global-limit revision. New subjects release old allocations. Caller-supplied string IDs alone do not authorize failure-cache reuse.
  • Fallbacks: backward search, invalid UTF-8, FIND_LONGEST, FIND_NOT_EMPTY, and a nonzero match-stack limit do not use memoization. Regex::is_linear_time() reports pattern eligibility; it is not a guarantee for these modes or after memory-budget fallback. Opted-in searches may finish where uncached execution exhausts a retry limit because they perform less work.
  • Validation: deterministic cache/plain/C comparisons, linear work and retry bounds, shared-budget and invalidation tests, and the match-cache fuzz target. benches/match_cache_bench.rs validates token/capture traces before measuring TypeScript, CSS, Rust, and a pathological grammar expression. The rebuilt implementation still requires an independent review and measured Ferriki adoption before closing #163.
  • Measurements: match cache evaluation, including normal-document overhead, pathological inputs, and the feature-disabled baseline comparison.

Literal trie (src/literal_trie.rs, regcomp.rs)

Detects alternations consisting entirely of literal strings and replaces them at compile time with a compact trie. The VM executes a single AltLiterals trie walk instead of backtracking through N branches.

  • Trigger: Alternation outside look-arounds with ≥4 literals where every branch is a plain string (the nested path extractor for a(b|c)d|e(f|g)h is not reached while plain strings are required). Case-sensitive, or case-insensitive ASCII literals in UTF-8 (folded trie).
  • Data structure: LiteralTrie — sorted child arrays with binary search. Ordered-alternation semantics: the match continues with the literal that comes first and pushes the other matching literals (prefixes) as backtracking alternatives. A folded trie also accepts what unravel_case_fold_string would (Kelvin sign, long s, ß/ffi-style segments), derived from the same case-fold queries.
  • Optimizer: the trie node carries the alternation's length range and start bytes.
  • Impact: CSS tokenization 35% faster (3.76x → 2.46x vs JS); CSS codeToHtml reaches JS parity (1.65x → 1.04x)
  • Bounds: MAX_NESTED_TRIE_PATHS = 8192 caps path extraction; CClass expansion limited to ≤16 single-byte members per class
  • Detailed analysis: /perf/html-entity-trie-optimization

RegSet first-byte dispatch and skip needle (src/regset.rs)

Pre-computes a 256-entry lookup table mapping each possible input byte to the subset of regexes that could match starting with that byte. Combined with a SIMD skip needle (via memchr) to advance past positions where no regex can match.

  • Trigger: Always active for RegSet (Scanner) workloads
  • Data structure: first_byte_candidates: Box<[Vec<u16>; 256]>, SkipNeedle (1-3 byte memchr)
  • Impact: 44% reduction in RegSet position-lead search overhead
  • Extends: ADR-007 (SIMD via memchr)
  • C's optimizer still decides: the table only narrows the positions an entry is attempted at. An entry whose optimizer has a distance is dispatched by its bytecode start bytes but attempted only where C's optimizer admits the position (sr[i]); the check runs after an attempt with a match or an error, or before every attempt where callouts or a search retry budget can observe it. The extra class and type byte maps (optimize_nodes with start_maps) serve only where C has no optimizer, and as a routing hint (start_dispatch).
  • Windowed table scan: with fallback entries in the set the table is scanned in windows (256 bytes, then four times as large), and the fallback entries are asked for an event inside each window, so an early fallback match ends the search as C's position-by-position search does.

Compiled forward literal finder (src/regcomp.rs, src/regexec.rs)

  • Trigger: the existing optimizer selects StrFast with an exact string longer than one byte.
  • Execution: compilation creates an owned memchr::memmem::Finder, reused by forward literal searches. The optimizer's string, distance bounds, search slice, candidate positions, and VM attempts remain unchanged. Single-byte searches still use memchr; backward and encoding-step searches keep their existing paths.
  • Bounds: one optional pointer per compiled regex; eligible expressions additionally own a boxed finder and a copy of the exact string, bounded by OPT_EXACT_MAXLEN (24 bytes). Search adds no allocation or shared mutable state. No new dependency or unsafe code.
  • Validation and measurements: simple-pattern profiling, including bounded-search and limit comparisons against the previous search path, cache/C parity, compilation costs, memory layout, and repeated workload measurements.

Unicode class range lookup (src/regexec.rs)

  • Trigger: multibyte character classes with more than four sorted intervals.
  • Execution: after the existing table-length and endpoint checks, is_in_code_range views the range words as pairs and searches for the containing interval. It returns immediately for an inclusive hit; otherwise it searches the left or right subslice, excluding the tested midpoint. Each iteration strictly shrinks the slice. This preserves C's membership result for sorted, disjoint intervals without requiring its lower-bound search to finish at a leaf. Small-table fast paths remain unchanged.
  • Bounds: logarithmic search, constant auxiliary space, no allocations, new metadata, generated-table changes, dependencies, or unsafe code. Encoding, byte consumption, backtracking, and limits keep their existing paths.
  • Validation and measurements: Unicode interval search refinement, including an exhaustive Unicode-range sweep, malformed table bounds, cache/plain/C checks, rejected alternatives, and a repeated 41-case before/after matrix. The earlier partition-search evaluations remain linked as historical evidence.

Adjacent ASCII class runs (src/regcomp.rs, src/regexec.rs)

  • Trigger: consecutive identical, non-negated CClass instructions whose bitsets contain only ASCII bytes, with an ASCII-compatible encoding. Existing equality/case-pair fast paths remain unchanged.
  • Execution: a post-compile pass marks each eligible prefix with CClassRun. All instruction addresses remain valid, including branches into a suffix. Each dispatch checks at most 255 bytes and preserves the failure position. Fused one-instruction look-behinds still evaluate only their original class. Backward searches whose matching range extends past the logical end execute classes one at a time to preserve the existing clamp.
  • Bounds: one linear pass over bytecode, existing bitsets reused, no extra heap allocation, dependency, or unsafe code. Longer runs continue at their remaining suffix.
  • Validation and measurements: ASCII class run evaluation. Tests compare raw results, captures, and deterministic limit outcomes against unbatched instructions, including malformed UTF-8 and backward or bounded searches. The opt-in cache and C differential suite also exercise the new opcode.

Leading atomic ASCII class search filter (src/regexec.rs)

  • Trigger: the forward position loop sees exactly the compiler's leading atomic [class]+literal bytecode, with identical positive ASCII class bitsets and a disjoint one-byte literal. Capturing, anchored, alternating, and multibyte prefixes stay on the original path.
  • Execution: a class run ending at the wrong delimiter cannot match from any suffix, so the filter skips that run. A run ending at the right delimiter still enters the VM, including every interior start if the tail fails. The run end is remembered to avoid repeating the prefix scan.
  • Fallbacks: a per-match retry limit of one, any search retry budget, stack or time limit, callouts, or a configured match cache disables the filter. Every skipped prefix would consume exactly one retry and cannot enter its tail; higher per-match limits therefore keep their original outcomes.
  • Bounds: constant scratch space, linear prefix scanning, no new compiled metadata, opcode, allocation, dependency, or unsafe code. Backward and equal-endpoint searches retain their existing paths.
  • Validation and measurements: atomic class prefix evaluation, including 500,736 exact original-path comparisons, C/cache differential cases, repeated general workloads, and broader scanner/search/compilation checks.

Leading class runs and bytecode start bytes (src/leading_run.rs, src/regexec.rs)

  • Trigger: the expression starts with a class run C+ (CClass, CClassMix, Word or WordAscii head and star with one class, optionally inside capture or atomic groups), or its bytecode start map excludes some byte. This is the case where C's optimizer string sits at an unbounded distance from the match start ([\w.+-]+@… selects @ at 1..∞), so C attempts every position.
  • Execution: a compile-time plan changes only which positions reach the VM; bytecode and C's optimizer choice are unchanged.
    • After a failed attempt, the search continues at the end of its run. Every later start in the run tries a subset of the same end positions with the same state.
    • An atomic run followed by a literal outside the class is searched from the literal. memmem finds the occurrence, the search scans back to the start of its run, and only that position is attempted.
    • The bytecode start map (derive_start_byte_map) filters the fallthrough loop behind an unbounded optimizer and bounded windows wider than one position.
  • Observability: every left-out attempt would fail with at most the backtracks of an attempt that already failed, or with a count known at compile time: one for the reverse scan, miss_retries for the start map. The plans stay off for FIND_LONGEST, a search retry budget, stack or time limits, a per-match limit at or below that count, callouts and the match cache. Back references, conditions, position checks, \K, calls, absent operators and capture-aware empty checks disable the run plan.
  • Malformed UTF-8: the reverse scan needs a valid UTF-8 segment, and falls back to attempting each position otherwise. A malformed lead byte lets the VM's run step over a byte the scan stops at. The forward scan steps like the VM's star loops and stops early where the VM could decide differently.
  • Bounds: one boxed plan and one boxed 256-byte map per eligible expression. The scans are linear; the reverse scan never passes the previous occurrence. The paths are out of line. No new dependency or unsafe code.
  • Impact: email-like scans 22–31×, number extraction 11×, [a-z]+ing\b, \w+ing\b and captured log fields 2.6–2.9×. Other expressions change by −1.5% to +1.4% in instructions, and TextMate scanner searches by at most ±0.2%.
  • Validation and measurements: leading-run skips. Tests compare results, capture bounds and limit errors with the original path, exhaustively on small inputs with malformed UTF-8 and on 4,000 generated expressions.

Leading-check jumps (src/leading_run.rs, src/regexec.rs)

  • Trigger: the expression starts, after zero-width captures, marks and word boundaries, with ^, with byte classes or literals (at least two, one with at most three bytes), with a literal alternation (AltLiterals; folded tries as in the next entry), or with a positive look-behind at an ASCII literal ((?<=took=)). The leading-run plans above also accept C* runs and runs behind \b whose class holds only word characters in the boundary's sense.
  • Execution: the search moves its start to the next position that can pass these leading checks, then runs C's optimizer and loops unchanged from there:
    • the rarest leading class is found with memchr and the other classes are checked;
    • ^ jumps to the next line start, following BeginLine's rules: NOTBOL, never the end, and the previous character head found by stepping back over 0x80..=0xBF in every encoding;
    • the alternation is found with Aho-Corasick, built on first use;
    • a look-behind literal is found with memmem, and the search starts right behind it. The look-behind holds at p exactly when the literal ends at p, since ASCII bytes are character heads.
  • Observability: every position a jump passes would fail its first check with exactly one backtrack. The jumps share the leading-run gates: they stay off for FIND_LONGEST, a search retry budget, stack or time limits, a per-match limit of one, callouts and the match cache. A jump over bytes that are not valid UTF-8 is not taken, and a jump in a range-bounded position loop never passes that loop's last attempt.
  • Not applied: expressions whose C optimizer already searches a string at the match start (for ^, with its line-anchor check). Also bare alternations, which take ac_alt.
  • Bounds: at most 16 leading classes per expression, and one lazily built automaton per alternation. The scans are linear, and no new dependency or unsafe code is added.
  • Impact: \s*,\s* 14×, \b\w+\( 11×, (?i)regex 9.2×, ^\s*// 6.9×, (?i)regular expression 4.4×, keyword alternations 3.2×; look-behind literals (2026-09 iteration round): (?<=took=)\d+ 21×. Other expressions change by −1.4% to +2.2% in instructions. TextMate scanner searches change by at most ±0.2%, and their compilation by at most +0.6%.
  • Validation and measurements: leading-check jumps.

Case-insensitive literal alternations (src/leading_run.rs, src/literal_trie.rs)

  • Trigger: the leading-check jump of an expression that starts with a folded literal trie, such as (?i)(?:error|warn|fatal) (see the literal trie entry). Its literals are ASCII.
  • Execution: an Aho-Corasick automaton over exact bytes finds the next ASCII case variant of a literal. It holds the case variants of the longest literal prefixes that stay within 64 strings, and so keeps the vectorized prefilter that ASCII case folding would switch off. The folded trie also matches non-ASCII input (Kelvin sign for k, ß for ss). Its walk reads ASCII one literal byte at a time and stops at a non-ASCII byte it cannot read. Such a match therefore starts at most the longest literal minus one byte before the first non-ASCII byte it holds, and the walk reads that byte. Those starts stay candidates. A 256-bit table of the lead bytes the walk can read rejects the other non-ASCII bytes, and the walk and the prefilter share one reader (CaseFolds::read).
  • Observability: the gates of the leading-check jumps.
  • Bounds: one lazily built automaton of at most 64 prefixes per trie, plus 32 bytes per folded trie. The scan runs in windows of 256 bytes, then twice as large each time, so a search scans in proportion to the distance it moves. No new dependency or unsafe code.
  • Impact: (?i)(?:error|warn|fatal|panic) over a log 9.2× (from 19× to 2.1× behind regex), over prose 3.0×, keyword alternations over code 1.7×, mostly non-ASCII text 3.2×.
  • Validation and measurements: case-insensitive alternations and grammar compilation.

Line starts after .* (src/regexec.rs)

  • Trigger: C's forward loop for an expression with ANCR_ANYCHAR_INF (a leading .*), which attempts only line starts.
  • Execution: after a failed attempt, memchr finds the next newline instead of the character loop. It applies where the bytes up to the newline are valid UTF-8 or the encoding is single-byte, so the character steps would land on the same position. Otherwise the loop steps as before. The skip runs out of line; inlined, it changed the code of the other position loops in the same function.
  • Bounds: a memchr and a UTF-8 check over the skipped bytes, no new data.
  • Impact: ^.*status.*$ −51% instructions.
  • Validation and measurements: case-insensitive alternations and grammar compilation.

ASCII fast paths in VM execution (src/regexec.rs)

Short-circuit encoding-aware functions (enclen, prev_char_head, WordStar traversal) for ASCII bytes, avoiding full UTF-8 decode on the hot path.

  • Trigger: Input byte < 0x80
  • Impact: Low single-digit percentage gains; primarily reduces constant factors in tight loops
  • Bounds: Single if guard per call site; no additional memory

Scanner fast paths from the 2026-09 profiling pass (src/regexec.rs, src/regset.rs, src/regparse.rs)

  • Negated class star opcodes: [^...]* / [^...]+ loops, including the Alt-CClass fusion, run as CClassNotStar / CClassMbNotStar / CClassMixNotStar with one lazy backtrack entry per run. All star opcodes share one loop that verifies every character boundary and falls back to one backtrack entry per character on malformed UTF-8.
  • Start-filtered fallback searches: RegSet fallback entries with an unbounded optimizer distance skip positions whose byte the bytecode-derived start map excludes. Only used without callouts, position checks, or a search retry budget. onig_search skips the same way under an unbounded (C) optimizer where the extra byte maps pin the start bytes down.
  • Untracked push captures: MEM_START_PUSH / MEM_END_PUSH skip their bookkeeping when no region is requested and captures cannot influence matching; kept when a match stack limit is set.
  • Range-driven case-fold expansion: (?i) classes are expanded by walking their ranges through the sorted fold keys.
  • Impact: CSS tokenize -79%, TypeScript documents tokenized line by line -25%, CSS grammar compile -11% (wall clock).
  • Detailed analysis: /perf/performance-structure-analysis

Second 2026-09 pass (src/regset.rs, src/first_bytes.rs, src/regcomp.rs, src/regexec.rs, src/regparse.rs, src/literal_trie.rs)

  • Contiguous fallback candidates: RegSet fallback entries keep their skip flags, settled no-match position and newest memo results in one array; the walk stops once a decision at the start position precedes the remaining entries.
  • Literal trie extensions: prefixes with ordered backtracking, case-insensitive folded tries, and optimizer information on the trie node (see the literal trie entry above).
  • Word-level class scans and streamed ctype ranges in compilation; the compiled output is unchanged.
  • Table-driven optimizer maps (src/regcomp.rs): optimize_nodes takes the codes below 0x80 of \w / \s / \d from a per-thread bitset instead of one is_code_ctype call per code, adds the members of a class or type in one branch-free pass and the bytes from 0x80 up in one fill, and alt_merge_opt_map sums the position values from one table. The optimizer output is unchanged (every field compared over 157,000 sweep and grammar patterns, three option sets, UTF-8 and ASCII).
  • Start bytes through positive look-aheads: the RegSet start-map derivation reads the body of a positive look-ahead that cannot match empty, so look-ahead-led fallback entries get a start filter.
  • Fused one-instruction look-behinds (src/regexec.rs): a fixed-length look-behind whose body compiles to one class or string instruction runs as LookBehindOp plus that instruction, without backtracking entries. Every other look-behind keeps the upstream sequence.
  • Guarded backtrack pushes (src/first_bytes.rs): a post-compile pass turns a Push whose main path can only start with some bytes into PushOrJumpExact1 (one byte, upstream's instruction) or the Rust-only PushOrJumpByteSet, so the VM skips the push when the current byte rules the main path out. The derivation only passes instructions whose effects backtracking undoes and gives up after 64 instructions. The skipped push still counts the backtracks the push would take against the retry and time limits: a loop that grows the stack without consuming input is bounded only by those limits, and without the count it pushed three times as many entries as C before the limit tripped. The count is derived at compile time by running the main path on a model of the backtracking stack; the model follows negative look-arounds whose body cannot consume the current byte. Where the count depends on the position (a look-behind or check in front of nested pushes; at most six checks), the guard counts the largest count, but only while nothing but the retry limit in match reads the count; if that upper bound trips the limit, the attempt starts over with those guards pushing, which counts exactly. With a search budget, a time limit, callouts or FIND_LONGEST such guards always push.
  • Fast-path census: grammar_fast_path_census asserts how many grammar patterns reach each of these paths, fused look-behinds and push guards included.
  • Impact: warm TypeScript line -57%, TypeScript document -44%, Rust document -37%, CSS document -33%, CSS grammar compile -25%, TypeScript compile -15% (wall clock).
  • Detailed analysis: /perf/performance-structure-analysis#second-pass

Match bounds without a region (src/api.rs, src/regexec.rs)

  • Trigger: Regex::find_iter, find_iter_bytes, find and find_bytes, which return only match bounds, for expressions without \K and without FIND_LONGEST.
  • Execution: the search runs without a region (onig_search_bounds). The match ends at its attempt position plus the match length, which OP_END records in the MatchArg. The iterator keeps one MatchArg for all its searches instead of taking and resetting the thread's cached one per match. Expressions with groups also skip the tracked second pass that filled the region.
  • Also: as in C, the inner search functions return the position and leave the region in the MatchArg; the entry points take it out once.
  • Impact: iterating \d+, \w+, identifiers and whitespace splits takes 22–24% fewer instructions.
  • Validation and measurements: match iteration, lazy loops and look-behind anchors.

Fused lazy .*?c loop (src/regexec.rs)

  • Trigger: a PushOrJumpExact1 with an ASCII byte that jumps back to the AnyChar or AnyCharMl right before it, which is how .*?c compiles.
  • Execution: memchr finds the loop's stop, the byte or a newline where the dot does not match one. The loop's jumps count their retries at once, capped at the limit where single retries would stop, so limit errors do not change.
  • Falls back: over bytes that are not valid UTF-8, with a time limit, with a guard count that depends on checks, and with the match cache.
  • Bounds: out of line behind one opcode check; no new data.
  • Impact: \[.*?\] 3.0×, ".*?" 1.8×, <.*?> 2.3×, <(\w+)[^>]*>.*?</\1> 3.9×. TextMate scanner searches +0.6% to +1.0% (layout of match_at_vm).

Chunked map search (src/regint.rs, src/regexec.rs)

  • Trigger: C's map optimizer with more than three bytes, whose ASCII part fits in six ranges, in an ASCII-compatible encoding.
  • Execution: after 16 bytes without a candidate, the search tests eight ASCII bytes at a time against the ranges (SWAR). Chunks holding a non-ASCII byte are walked character by character, as before.
  • Impact: \d+ over prose and [A-Z][A-Z_]+ over code take 42–44% fewer instructions. Searches with close matches stay at their cost because of the 16-byte start.

Bitmaps for Unicode ctypes (src/unicode/mod.rs)

  • Trigger: onigenc_unicode_is_code_ctype for a code below U+10000 and a table with at least 16 ranges.
  • Execution: a bitmap of the table's BMP part, built on first use, replaces the binary search.
  • Bounds: 8 KiB per table a process queries, at most one per table (641 tables).
  • Impact: part of the \w+ improvement over non-ASCII text (−27% instructions with the region-free iteration).

Grammar compilation caches (src/regparse.rs, src/regcomp.rs)

  • Ctype ranges: into a class without multibyte ranges, a Unicode ctype ([:alpha:], \w, \p{…}) adds the same bits and ranges every time. They are kept per thread, for up to 32 ctypes.
  • Case-fold expansions: the expansion of a (?i) class depends only on its bits and ranges, the case-fold flag and the encoding. Classes with at least 32 multibyte ranges keep it per thread, up to 32 expansions.
  • Optimizer maps: map merges gather eight map bytes into bits with one multiplication and visit only the members they add.
  • Output: unchanged. Tests compare each cache with the path it replaces, on first and repeated use, and the map operations with the byte loops.
  • Bounds: per thread, at most 32 ctype entries and 32 expansions, each the size of the class it stands for (a few KiB for \w). Lookups compare the whole key.
  • Impact: grammar compilation −38% instructions for CSS, −15% for TypeScript, −6% for Rust (CSS 25.6 → 17.3 ms).
  • Measurements: case-insensitive alternations and grammar compilation.

Single-byte star loops (src/regcomp.rs)

  • Trigger: a greedy c* / c+ whose body is one ASCII byte, outside a literal trie. The body compiles to a single Str1 c, which matches what [c] matches, so the loop compiles to CClassStar (or CClassStarPeekNext) with a one-member set, like the class stars above.
  • Why: upstream's PUSH_OR_JUMP_EXACT1; STR_1; JUMP loop costs three dispatches and one backtrack entry per character. In a variable-length look-behind that loop runs once per step-back position, so it dominated (?<=x|a*b) and (?<!x|a*b)c.
  • Impact: (?<=x|a*b) over 1,000 characters 1.49 s → 96 ms (C: 583 ms); (?<!x|a*b)c 4.25 ms → 0.27 ms (C: 1.70 ms), measured after the matcher fixes of the same pass.
  • Bounds: one lazy backtrack entry per run, as for every star opcode, so a match stack limit counts the run once rather than per character; no extra memory.

Capture pushes for back-referenced groups (src/regcomp.rs)

C's tune_tree pushes the captures of every back-referenced group (backtrack_mem), and its own comment calls that conservative. After tune_tree, backref_groups_needing_push pushes such a group only where a restore can be observed.

  • Trigger: a back-referenced group keeps plain MEM_START / MEM_END when its capture node occurs once, every node above it is a list, an option, a capture or an atomic group, and every back reference or condition that reads it sits in a later element of a list that also holds the group. Such a group runs exactly once per attempt, and every path to a read passes the whole group again after any backtrack, so the stale value a missing push could leave is never read. It is not in a loop body either, so the capture-aware empty checks never compare it.
  • Falls back to C: a read before or inside the group; a group under a quantifier, alternation, look-around or condition; a level back reference (\k<n+0>); subroutine calls, callouts, \K or absent operators anywhere in the pattern; groups past the 31 status bits.
  • Impact (release search, best of three interleaved runs): (?i)(\w)\1 -10%, \b(\w+)\s+\1\b -7%, (["'])(?:\\.|(?!\1).)*\1 -10%, heredoc openers and bodies -5% to -9%, <(\w+)[^>]*>.*?</\1> -5%; patterns without back references unchanged.
  • Bounds: one tree walk that stores the path to each back-referenced group and each read; comparing a read costs its depth.
  • Not applied: {n,} over a body that may be empty keeps C's REPEAT. Unrolling even a body whose only empty pass is its last alternative makes every later mandatory copy retry paths that already failed; (?:(ab|cd|ef|gh|ij)?){3,}z got about six times slower.

Rationale

  • Upstream-first is impractical for workload-specific optimizations. C Oniguruma's maintainer focuses on correctness and Unicode compliance, not TextMate grammar throughput. Contributing a Rust-inspired trie optimization to a C codebase with different constraints is not a productive use of either project's time.
  • The core engine remains 1:1 with C. All optimizations are additive passes that transform the AST before compilation or add pre-filter data structures around the existing VM. The C-ported regparse.rs, regcomp.rs (core), regexec.rs (core), and regenc.rs remain structurally faithful.
  • ADR-001's goal is preserved. The intent of the upstream-first rule was to prevent accidental divergence that makes future C updates hard to apply. Additive optimizations do not interfere with C-to-Rust diffing — they are clearly separated new code that can be toggled or removed without affecting the ported baseline.

Consequences

  • Ferroni's compiled bytecode may differ from C Oniguruma for patterns that trigger the trie optimizer. Match results remain identical, but internal representations diverge.
  • Retry limits are the one place where the optimizations can show. A search prefilter that proves there is no match (a required byte or literal missing from the subject) reports "no match" without running the matcher, where C runs into the retry limit and reports ONIGERR_RETRY_LIMIT_IN_MATCH_OVER; for example (?:a*a?)*\d against sixteen a. This difference is deliberate. Rust-only instructions that replace a C sequence (literal tries, star loops) can also take fewer backtracks than C's sequence, so a search close to the limit may finish in Ferroni and stop in C. Guarded pushes count exactly the backtracks they save (see above).
  • The Scanner's memo and per-regex cache route never change a result, limit errors included: a fallback entry attempts exactly the positions C's regset_search_body_position_lead lets its optimizer admit (forward_search), the memo keeps only matches and no-match results, never errors, and the per-regex route combines the same per-entry searches. A search retry budget, which makes a result depend on where its search began, bypasses both.
  • Future C Oniguruma updates can still be applied by diffing against the C-ported baseline. Optimization passes are clearly separated in the compilation pipeline.
  • Each new optimization must document its trigger conditions, bounds, and benchmark results — either in this ADR (for significant changes) or in /perf/ (for detailed analysis).
  • Performance documentation in /perf/ serves as the detailed log; this ADR serves as the policy and index.