Rust-Only Optimizations and Performance Philosophy

Status

Accepted (amends ADR-001). ADR-017 amends its rule for searches that reach a limit.

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. Where C stops at a retry, stack or time limit, ADR-017 decides what Ferroni may return instead.

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

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, or inside an otherwise unanchored negative lookahead, 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). Positive lookahead, lookbehind, and nested assertions retain the original path; mixed literal runs are compacted only outside assertions.
• 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 byte length range and start bytes. A folded trie also carries each literal as unravel_case_fold_string would expand it (runs of plain bytes, letter classes, multi-character segments), and C's optimizer pass reads that form (optimize_unravelled), so the expression keeps C's optimizer: in (?i)(?<=\s)(align|…|zero)(?=\s=) C searches for the = 4 to 15 bytes ahead rather than for the words' first letters. Where that form leaves C without a map, the Rust-only start maps take the trie's start bytes. Over the 573 Shiki patterns with a folded trie, 445 now get C's optimizer and 125 a Rust-only start map where C has none (before: 329 and 124, with 120 deviating from C); the remaining 3 put a folded trie beside other branches, whose maps C merges in branch order. Compiling all Shiki patterns takes 0.8% more instructions.
• 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
• Negative-lookahead extension: On the captured C++ workload, scanner replay takes 40–44% less time and finished inline HTML takes 35–36% less time. Uncached C++ scanner construction plus teardown costs 3–5% more. The isolated comparison retains the paired 20-format HTML measurements, focused outlier repeats, compiler costs, and parity checks. Trie storage remains bounded by the accepted literal input and uses the existing construction and matching paths.

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 they filter (see Selective extra start maps below), 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.

Pure literal patterns (src/regcomp.rs, src/regexec.rs, src/api.rs)

• Trigger: the whole program is one string op (Str1–Str5 or StrN) followed by End, and the optimizer's StrFast string is those bytes. No captures, anchors, distances, callouts or \K. Case folding and multibyte strings (StrMb*) keep the VM. The flag is RegexType::pure_literal, set by detect_pure_literal when compilation ends.
• Execution: a search that sees all of its subject (right_range is the end) and starts before its range takes the first occurrence of the string at or after its start, if that occurrence begins before the range. The match bounds fill the region as the one attempt would. Regex::find family searches (find_from) and find_iter cursors skip the search state altogether. Backward, anchored (start == range), narrower-right-range searches, and searches with FIND_LONGEST, FIND_NOT_EMPTY, MATCH_WHOLE_STRING or the string validity check keep the VM.
• Bounds: one flag and a few option checks per search; no allocation, metadata beyond the flag, dependency or unsafe code. The search reuses the optimizer's finder.
• Why no limit can observe it: with the whole subject visible, every occurrence the optimizer finds is a complete match, so the first attempt succeeds without backtracking, and no failed attempt can count toward a retry, stack or time limit.
• Impact (callgrind instructions, benches/production_regex literal_*, find_at on an 88-byte line): about 1,066 → 250 per search for GET at offset 0 (−77%); literal_middle −76%, literal_end −73%, literal_absent −66%. The four literal cases together: −74%. Compilation of the literal cases moves +0.9%, within the layout noise the non-literal compile controls show (uuid_v4 −0.1%, fluent_bit −0.9%). Non-literal controls: uuid_v4 search −1.5%, fluent_bit search −0.5%.
• Validation: unit tests check the flag against the bytecode (plain strings set it; ignore-case, dot, anchors, captures, lookahead, alternation, empty and multibyte strings do not). They compare results and regions with the VM path (a test switch) over every start, range and cut end on ASCII and malformed subjects, with and without a region, under each option that keeps the VM, and on the narrowed-range route RegSet uses. The validity-option and retry-limit cases are checked separately.

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, or callouts 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, or a head narrower than the star's 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.
  • The head may also be narrower than the run, its single bytes and multibyte ranges within the run's class ([A-Z_a-z]\w*, [A-Z_a-z][_\w\d]*). A later start in the run then either fails at the head or reads the same run to the same end, so only an attempt that read the head, at an ASCII byte, stands for the rest of its run; the reverse scan stays off. In the Shiki corpus this takes haxe's ([A-Z_a-z]\w*)(?=\s*:) from 1.38× to 0.47× C's time and d's ([A-Z_a-z][_\w\d]*)\s*(?=[(;=])(;)? from 1.29× to 0.50×.
  • 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, and callouts. 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.

RegSet failed-run skips (src/leading_run.rs, src/regset.rs)

• Trigger: a position-lead fallback entry has a leading-run plan and C's optimizer admits an unbounded range. After an actual failed attempt, later starts inside its run try a subset of the same tail positions. The same skip helper is shared with the individual regex search.
• Whole assertions: a sole positive lookahead can also plan \w?C* when the class contains every ASCII word byte. The optional word, compiled program, grammar expression and C optimizer stay unchanged. Its scan stops before non-ASCII bytes. A restored attempt position followed by a consuming suffix has no plan: (?=[a-z]*a)b must still try the later b in aba.
• Guards: callouts, start-sensitive instructions, back references, capture-aware empty checks, FIND_LONGEST, search retry budgets, stack and time limits retain the original path. FIND_NOT_EMPTY disables assertion skips because it may reject an already successful assertion after its cut. With a per-match retry limit, an optional-word assertion only skips after an ASCII word start: that failed attempt tried both prefix paths and bounds later attempts' retries. Nested leading marks disable the optional-word extension.
• Bounds: reuse the existing boxed plan and add two flags. At most eight scans of the compiled instructions inspect leading marks; no pattern expansion, opcode, dependency or unsafe code is added. A runtime scan stays within the subject. Crossing a competing match's start bound finishes only that fallback entry.
• Impact: the captured Java document replay takes 35.5% / 36.7% less time in two ABBA pairs. Finished Java inline HTML takes 17.6% / 23.0% less time on the large curated fixture and beats both Shiki backends in both sizes and runs. The full 20-format comparison gains one format (14/20 to 15/20), with no repeated large regression. Source-pinned reports and ordinary build receipts are available in the Git history.
• Validation: the Java replay validates every winner and capture against C. The RegSet matrix compares the original path with skips over bounded starts, Unicode and malformed input, captures, competing patterns, memoized and plain searches, and deterministic match/search/stack limits. The individual-search assertion regression covers restored starts.

RegSet required literals (src/required_literals.rs, src/regset.rs)

• Trigger: a RegSet fallback entry whose optimizer (C's) leaves the match start unbounded. Its search checks once that the optimizer's string or byte map occurs, then attempts every position up to the end of the subject.

• Required literals: literals one of which every successful attempt from p contains at some q >= p, ending by the end of the subject. Where the optimizer has an exact string, it is that string: C's search relies on every match holding it. Where it has a byte map, compilation reads a set from the tuned parse tree, in one walk over the nodes every match runs:

  • a string gives its bytes, a class of at most four ASCII bytes its members, a case-sensitive literal trie its literals;
  • a concatenation keeps its most selective element: the longest shortest literal (lengths from four bytes rank equally), then the fewest literals, then the rarest bytes;
  • an alternation gives the union if every branch has a set, at most 64 literals, without literals that hold another;
  • capture, option and atomic groups, quantifiers with a minimum of at least one, and positive look-aheads give their body's set;
  • look-behind, negative look-arounds, back references, calls (their group counts where it stands), conditions, optional parts, other classes and types give nothing.

  A case-insensitive string counts only through the exact alternatives tune_tree unravels it into (st as st|sT|St|ST|ſt|ſT|ſt|st), never through a class with non-ASCII members (k holds the Kelvin sign) or a folded trie. Expressions with \K, absent operators or callouts get no set.

• Execution: before the optimizer's search, the fallback search looks for the first occurrence from its start (memchr, memmem, or Aho-Corasick for several literals, built on first use). Without one the entry has no event. Positions up to an occurrence are attempted as before; a position past it looks for the next one, and past the last one the search ends. An attempt at the search start alone (attempt_fallback_entry_at_start) is left out when no occurrence lies ahead. The memo records these searches like any other; entries it leaves out (callouts, position checks) stay out of it.

• Soundness: an attempt from p keeps an invariant: every byte between the VM's position outside look-behind and p is a trailing byte (0x80–0xBF). No required literal starts with one, so each occurrence the attempt reads lies at or after p. Moving forward keeps the invariant (a call runs its group from the current position), and so does going back: a look-ahead, a fixed-length look-behind and backtracking return to where they began, a negative look-behind of variable length leaves through the alternative it pushed at its position, and a positive one goes on only where its body ends at its position (CheckPosition against the right range it set there). \G only tests the position. Without a look-behind lead (below) the position never lies before p, whatever strings the expression holds. The program is compiled from the tuned tree, whose strings compile to exact byte comparisons. A left-out attempt has no occurrence at or after its start, so it cannot match. An occurrence that does not start at a character boundary only admits more positions.

• Look-behind leads: a look-behind of variable length that ends in a literal checks that literal first (OpCode::Move): it steps back as many characters as the literal has, matches its bytes forward, and a positive one goes on where they end. For a string C accepts, that end keeps the invariant. Ferroni also accepts \x{140000}–\x{1FFFFF}, which C rejects (USE_CHECK_VALIDITY_OF_STRING_IN_TREE): their lead bytes F5–F7 are one-byte characters to the length table, so \s*(?<=y*\x{140000})ABC matches at 10 of yyy\xF5\x80\x80\x80ABCD by reading ABC at 7..10. Entries with such a check, negative ones included, keep every attempt; applying the filter to them waits for C's string validity check.

• Observability: no callouts (checked with the look-behind leads when an entry is added or replaced, required_literals_are_safe), and no search retry budget, stack or time limit, FIND_LONGEST, or limit on calls per search for a program with calls. A left-out attempt fails, but it may first reach the retry limit in match. C then reports ONIGERR_RETRY_LIMIT_IN_MATCH_OVER, and Ferroni the next event or no match (see Consequences). With the default limit of 10,000,000 backtracks, that takes an attempt which backtracks that often although no match is possible.

• Bounds: one boxed set per eligible expression, a copy of the optimizer's string or at most 64 literals; finders are built on first use. The analysis visits only the nodes every match runs, each once. A search scans the subject once for each occurrence it passes. No new dependency or unsafe code.

• Impact: captured scanner replays, instructions / minimum cycles: C++ −59% / −57%, Java −64% / −62%, SCSS −12% / −10%. Constructing the captured C++ scanner set takes 0.3% more instructions (median of seven runs); SCSS and Java construction stays within the noise of ±0.5%. scanner_compile_bench in two interleaved runs: C++ 240 / 243 ms before, 236 / 235 ms after; SCSS 55.6 / 55.0 ms before, 55.8 / 56.2 ms after. Entries with position checks but no look-behind lead followed (7 of the 9 such distinct patterns with a set in the captured C++ trace, among them the hot (?<!(?:\W|^)(?:reinterpret_cast|…)) entries): C++ another −7.6% / −8.4% and −7.1% in two runs; the Java and SCSS traces have no such entries.

• Not applied: unions beyond 64 literals ((unsigned|…|int)|(uint_least32_t|…)|[A-Z_a-z]\w*_t in the C++ grammar); individual searches (onig_search); entries with a look-behind lead, 2 of the 94 distinct patterns with a set in the captured C++ trace ((?<=(?:\W|^)return)), which would save less than another 1% of its replay's instructions.

• Validation: unit tests for each rule, with and without a set. A RegSet matrix compares the program with and without the filter over memoized, plain and per-regex searches, bounded starts and ranges, captures, Unicode and malformed input, and match, search, stack and call limits; its position checks are \G and look-behinds without a lead in front of, behind and around the literal, over multibyte subjects, stray trailing bytes and F4 and F5 sequences. It allows only the retry-limit difference, and then requires the result of a search without that limit. A generated test combines these position checks with look-behind leads. Regression tests keep the \x{140000} look-behind's match and keep a "no event" the filter decides for an entry with a position check out of the memo. The C++, Java and SCSS replays validate every winner and capture against C.

RegSet first-instruction rejects (src/regset.rs, src/regexec.rs)

• Trigger: a RegSet entry whose first instruction is a word boundary (\b, \B), a line start (^) or a fused one-instruction look-behind (LookBehindOp). The first-byte dispatch cannot see these zero-width tests, and many attempts fail at them: about 61% of the attempts in the captured SCSS replay, 41% in Java and 16% in C++. The test is derived when the entry is added or replaced (first_op_test); other entries pay one predictable branch per attempt.
• Execution: the table scan and the fallback searches evaluate the test at the candidate position before the attempt (first_op_fails), with the VM's own helpers: the word-boundary check with its ASCII fast path (is_word_boundary_ascii_fast), look_behind_body_matches with the attempt's right range (the subject's end), and the BeginLine arm's rules for NOTBOL, the subject end and the previous character head. A failing test leaves the attempt out, and with it the VM's entry and exit and the region hand-over. Literal and class first instructions are not tested: the dispatch has already checked their first byte, and at most 0.3% of the attempts fail there.
• Observability: the left-out attempt would fail at its first instruction with exactly one backtrack and no other effect; the skip resets the MatchArg as that attempt does and counts the retry. The tests stay off for a search retry budget, a per-match limit of one, stack or time limits, FIND_LONGEST and callouts, as the leading-run plans do. A gated table entry consults its optimizer as for any failed attempt, the fallback memo and failed-run skips see the same failure, and none of the tested instructions reads the search start. FIND_NOT_EMPTY is only read at a match end.
• Bounds: one small field per entry and one out-of-line evaluation per tested attempt. No new opcode, allocation, dependency or unsafe code. onig_search and the per-regex scanner route's table entries keep their path.
• Impact: per replay of the captured scanner traces, SCSS −12.8% instructions (minimum cycles −11.0% and −12.6% in two interleaved runs), Java −4.3% (−6.3%, −5.6%), C++ −1.4% (−2.5%, +0.5%). General onig_search workloads (validation, extraction, Unicode words, redaction) stay within their run-to-run spread of about ±0.1% in instructions.
• Validation: unit tests compare the test with the VM attempt at every byte position of ASCII, multibyte and malformed subjects and shortened ends, and check that other first instructions and callouts keep the attempt. A RegSet matrix compares results, winners, captures and limit errors with the tests off, over table and fallback entries, plain, fast and memoized searches, and the limits that turn them off. A census counts the grammar patterns that get a test. All three traces validate against C.

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, and callouts. 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
• Word boundaries: \b / \B between two ASCII bytes look both bytes up in a 256-byte is_word_ascii table instead of calling is_word_boundary, whose prev_char_head asks the encoding for its flags through a virtual call. Both encodings are ASCII-compatible (ADR-003), so a byte below 0x80 is a whole character, and both word modes classify it alike. The start, the end and non-ASCII neighbors keep the full check; a test compares both for every byte pair. Captured scanner replays take 9.1% fewer instructions for Java, 1.3% for C++ and 0.9% for SCSS.

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; the retry limit in match does not turn it off (see Consequences). 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. A search with a region (onig_search, RegSet fallback entries) tracks captures only in one attempt: at first its attempt at the start position, the common case of a scanner match, and now the first attempt it makes (see Empty matches and first-attempt captures); the other attempts run untracked, and a match among them runs again with tracking to fill the region. That second pass does not count against the retry limits. Tracking every attempt would cost a failing attempt its capture pushes; running the start attempt untracked as well would repeat every match at the start, which doubled the cost of a capture in a loop such as (.)*. The other attempts run untracked only where the repeated match should cost less than tracking every attempt (two_pass_capture_fill_pays): with push captures, unless the optimizer finds a literal at the match start, whose candidates often match; without them, which leaves an untracked attempt little to save, unless . repeats without an upper bound (.*?, (.)+) and a match may run to the end of the line. Otherwise every attempt records its captures, as in C. Liquid's \((.(?!\.\.))+\) goes from 1.78× to 1.18× C's instructions and vyper's \s*([^#(.\\_[:alpha:]\s].*?)(?=#|$) from 1.86× to 1.25×. A length bound alone is not enough: tracking every attempt of \s*\b(case|match) or of keyword alternations behind a look-behind costs 5–10% more than repeating their short matches.
• 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/regcomp.rs, src/regexec.rs): a fixed-length look-behind whose body compiles to one class, string or word-type (\w, \W) instruction runs as LookBehindOp plus that instruction, without backtracking entries. Every other look-behind keeps the upstream sequence. A positive one goes on where its body ends, as C's CUT_TO_MARK without restoring the position does: over valid UTF-8 that is where it started, over malformed UTF-8 the step back over continuation bytes can end it before or past that. A negative one whose body fails counts the backtrack that the upstream sequence takes at the body's failing instruction, and the guard analysis counts it too, so retry limits trip where they would. The match stack limit decides as it does for the upstream sequence: the look-behind checks it where the MARK (and, for a negative one, the PUSH) would push, with the count of entries those pushes hold, and the guarded pushes below push under a limit. Found from the structure of C's regexec.c, not verified against C: fused_look_behinds_match_the_upstream_stack_limit_boundary compares the fused and the upstream forms at every limit from 1 to 24. A one-character look-behind whose body is \w, \W or a class (CClass, CClassRun, CClassMix) and whose character before the position is ASCII is decided directly (look_behind_ascii_end): the same result as the general step back and instruction, without its call and dispatch. Other characters take the general path. A negative one whose body is \w or a one-byte string (Str1) in UTF-8 is decided inline in the matcher with the same decision: the byte before the position is ASCII, and the body is tested against that byte (a one-byte string) or with the word test (\w). Its failing body counts the backtrack and checks the stack limit as above. The Rust-only fused look-behind tests (fused_look_behinds_match_the_upstream_sequence) cover both bodies. Steady-lane impact of the inline decision alone (measure2, instructions per batch): python_markdown_smart_strong_em_re 18,668 → 17,172 and python_markdown_smart_emphasis_re 32,288 → 27,795. Impact (callgrind instructions, net of the empty loop, 200 iterations of the production cases' timed loops): python_markdown_smart_strong_em_re 27.44M → 20.52M with the fused \w look-behind, then 18.70M with the direct decision; python_markdown_smart_emphasis_re 30.78M → 30.35M; rails_underscore_regex_step 64.85M → 63.67M; jinja_float_token 56.79M → 56.93M, from the extra test on its look-behinds, which keep the general path; uuid_v4 and fluent_bit_apache stay within 0.01%. The steady cases semver_version_parse and ipv6_validation do not use look-behinds and stay within 0.01%.
• 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. In UTF-8 a class with multibyte members contributes the lead bytes whose characters can decode into its ranges, not every byte from 0x80 up: the decoder takes a character's high bits from its lead byte whatever the continuation bytes hold, so each lead byte reaches one fixed block of codes, overlong and malformed forms included (E0 8E A9 decodes to Ω). The pass reads each large class once per expression. Under (?i), the branches of a class's case folds that start with a Greek or Armenian class then no longer run on every non-ASCII character of the text. 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, a match stack limit, callouts or FIND_LONGEST such guards always push: a skipped push would leave out an entry that the limit counts.
• 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 match stack limit (the loop pushes one entry per character there, as C does), and with a guard count that depends on checks. The lazy capture seek (PushLazyAnyChar) falls back under a match stack limit for the same reason.
• Impact: \[.*?\] 3.0×, ".*?" 1.8×, <.*?> 2.3×, <(\w+)[^>]*>.*?</\1> 3.9×. TextMate scanner searches +0.6% to +1.0% (layout of match_at_vm).
• Literal seek (PushLazyAnyChar, src/regcomp.rs: lazy_literal_byte, backref_literal_first_bytes): the seek also applies when the loop's capture end is followed by negative one-character look-behinds and then the literal, which is either a plain string or a back reference to a group. The group must have a plain, case-sensitive, non-empty string as its capture, and every read of it must follow the capture on its path (the analysis of backref_groups_needing_push). The byte the seek looks for is fixed at compile time and stored in the instruction (PushLazyAnyChar { addr, c }). Every position the seek skips fails at that byte: a look-behind only rejects a position, and a back reference compares its first byte first. The capture ends of a skipped position are overwritten at the stop, before anything reads them: the stop is a position the loop visits, and the capture ends come first in the path, so the attempt there writes them again. The skipped attempts are not counted, as ADR-017 allows; the loop's own jumps are counted as before. Not applied: a case-insensitive group or back reference, an empty, optional or alternative group, a read before the group, a look-behind before a capture end, calls, and a non-ASCII first byte (the seek falls back on it, as before). Patterns with a back reference get one more walk of the tree at compile time.
• Validation: lazy_literal_seek_matches_the_instruction_loop compares the seek with the loop run one instruction at a time and with a program compiled without push guards, over edge and random subjects (multibyte, malformed, empty, literal at the end, failing look-behinds, empty groups) and under retry, search and stack limits: a finished search equals the unlimited result, and an unlimited finish never becomes a limit error. Each pattern is listed with whether the seek must be planned for it. tests/lazy_literal_seek.rs compares the results and captures with C Oniguruma on valid UTF-8 subjects.
• Impact of the literal seek (steady lane, measure2, instructions per batch): python_markdown_smart_strong_em_re 18,668 → 9,009 (−52%), python_markdown_smart_emphasis_re 32,288 → 13,291 (−59%), with the inline look-behind of Fused one-instruction look-behinds under Second 2026-09 pass. jinja_float_token 61,810 → 61,135 (−1%, from its (?<!\.) look-behind), fluent_bit_apache and semver_version_parse stay within 0.03%, and the tokenizer tiktoken_cl100k_base (five batches) 2,290,132 → 2,287,149.
• Bounds: out of line behind one opcode check; one byte in the instruction; one tree walk at compile time for patterns with back references.

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.

Grapheme breaks between ASCII bytes (src/unicode/mod.rs)

• Trigger: onigenc_egcb_is_break_position at a position strictly inside the logical end, with both the byte before it and the byte at it below 0x80, in the built-in UTF-8 or ASCII encoding (ADR-003). The check is by address: a user-defined ASCII-compatible encoding may have ASCII-valued trail bytes.
• Execution: the answer is "no break" only for CR LF (GB3); every other ASCII pair breaks. No ASCII code point has a Grapheme_Cluster_Break class that GB6-GB13 act on, and a test checks the answer against the general rules for every ASCII pair and for mixed and invalid byte strings.
• Bounds: a comparison of two bytes before the general rules; no memory.
• Impact: an ASCII-only \X{1} scan takes 25% fewer instructions (callgrind, on a scratch ASCII text outside the catalog). Pairs that are not ASCII-only gain nothing: symfony_grapheme pays about 0.6% more (layout of the guard, measured).

Two-stage grapheme break property table (src/unicode/mod.rs)

• Trigger: egcb_get_type for a code point below U+10000. Every grapheme break decision that is not an ASCII pair (see above) asks it for both characters, and the GB11 and GB12/GB13 look-behinds ask it again (\X, \y, \Y).
• Execution: a 256-entry index from each high byte to a block of 256 properties by low byte. Equal blocks are stored once. The table is built on first use by one sweep over EGCB_RANGES, which is generated from the UCD (ADR-015), so it follows the Unicode version of the data. Code points above U+FFFF keep the binary search.
• Observability: none. The table answers the binary search for every code point.
• Bounds: 45 distinct blocks for Unicode 18.0.0, about 11.5 KiB on the heap per process that searches with a grapheme break (\X and the other EGCB users). The one-time build takes about 0.36M instructions (release, callgrind, net of an empty test). No allocation after the build, no unsafe code.
• Validation: egcb_table_matches_the_binary_search_for_every_code_point compares every code point from 0 to U+10FFFF, surrogates excepted, with the binary search. egcb_ranges_are_sorted_and_disjoint checks the precondition of the build, and egcb_table_blocks_are_distinct the deduplication.
• Impact (callgrind instructions per steady batch, production lane; before = the base without this entry or the ASCII entry above, after = both): symfony_grapheme_chunks_1 31,041 → 28,827 (−7.1%), symfony_grapheme_chunks_2 8,058 → 7,385 (−8.3%). Controls: mastodon_hashtag_regex_step 101,393 → 101,393, uuid_v4 5,341 → 5,327, tiktoken_o200k_base (tokenizer corpus, 5 batches) 2,072,394 → 2,072,394.

\X as one grapheme-boundary instruction (src/regparse.rs, src/regcomp.rs, src/regexec.rs)

Upstream's \X is the atomic group (?>\O(?:\Y\O)*): a multiline any-character, then a loop that takes each further character while no extended grapheme cluster boundary lies before it. Its compiled form is Mark, AnyCharMl, Push, TextSegmentBoundary, AnyCharMl, Jump, CutToMark, with a stack entry and a dispatch per character.

• Trigger: \X (not (?y{w})\X) outside look-behinds. The parser marks the group with BagData::TextSegment only when no look-behind body encloses it (look_behind_depth), and the compiler checks the shape before it emits the instruction; any other shape keeps the atomic group.
• Execution: GraphemeCluster runs grapheme_cluster_end, which takes the same steps as the loop: the first character where one fits before the range end, then each further character while onigenc_egcb_is_break_position (judged against the string end) reports no boundary and the character fits before the range end. The atomic group keeps that position, so the instruction pushes no entries and never gives back.
• Observability: none for results. Stack entries and retries that the loop counted are not counted; ADR-017 allows that where C stops at a limit, and Ferroni never stops at one where C finishes. A long cluster no longer reaches a match stack limit that upstream's loop reaches (a_long_cluster_needs_no_stack_entries).
• Bounds: no allocation, no data, no unsafe code; one loop per \X step, over the characters the cluster covers.
• Validation: grapheme_cluster_matches_the_upstream_sequence compares the instruction with the atomic group (switched off in tests) for 24 patterns over 15 subjects (CRLF, combining marks, ZWJ emoji, regional indicators, Hangul, prepended and variation-selector code points, malformed UTF-8), at every start and every range end, with captures, alternations and anchors. With the ffi feature it also compares with C where the range is past the start. The look-behind and word-variant cases check the emitted instructions.
• Impact (callgrind instructions per steady batch, production lane; base origin/main 2a692ca): symfony_grapheme_chunks_1 28,791 → 26,383 (−8.4%), symfony_grapheme_chunks_2 7,383 → 6,671 (−9.6%). Controls: mastodon_hashtag_regex_step 101,393 → 101,424 (+0.03%), wordpress_shortcode_captures 48,444 → 48,470 (+0.05%), uuid_v4 5,110 → 5,107, tiktoken_o200k_base (tokenizer corpus, 5 batches) 2,072,888 → 2,072,888.

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.

Specialized negated byte-class runs (src/regexec.rs)

• Trigger: the existing CClassNotStar instruction. Its equality, ASCII case-pair, or bitset test is selected once per run, instead of inside each character test. Equality and case-pair runs with at least 32 bytes remaining also try memchr or memchr2, accepting the result only when the entire skipped prefix is ASCII.
• Execution: the specialized character walker and the ASCII scan create the same lazy backtrack entry as the original loop. A non-ASCII prefix keeps the character walker: a malformed UTF-8 head can consume an ASCII delimiter as a trail byte, so finding that byte alone cannot decide the run. Bytecode, captures, character boundaries, and retry/stack bookkeeping are unchanged.
• Bounds: no new allocation, dependency, unsafe code, or compiled-pattern data. The extra scans are linear in the current run. The measured comparison executable's text segment grows by 16 KiB (0.25%); downstream code size depends on its build.
• Validation: C compatibility and integration suites, the prefilter self-check with serial tests, and differential comparisons with bounded character repeats over ASCII, Unicode, malformed UTF-8, captures, backtracking, and forward/backward search ranges.
• Impact: local Apple M1 Ultra steady-batch measurements against 7e67f04, three paired processes per case with padded environments: Fluent Bit Nginx −14.3%, Apache −6.3%, ferrolink attribute splitting −3.9%, and markup scanning −4.0%. A follow-up across eight environment alignments measured markup at −3.4%, with cl100k at +0.9% and the short two-grapheme case at +1.9%. These are case-specific elapsed-time changes, not a whole-application or cross-platform claim. The local diagnostic retains all 29 executable production/tokenizer cases, alignment-sensitive controls, raw samples, source provenance, and validation logs.

Possessive negated byte-class runs (src/regexec.rs)

• Trigger: CClassNotStar immediately followed by PopStarChoices, with no configured match stack limit. This is the existing compiler representation of a possessive negated byte-class loop.
• Execution: the character walker consumes the same characters but omits the backtrack entries that the following pop would discard. It also omits the checks needed only to retrace malformed byte input, then advances past the pop. No retry is removed: those choices could never be taken. A configured stack limit keeps both original instructions and their temporary entries. Possession selection and the byte walker stay in separate out-of-line helpers; the VM receives the run end and next instruction by value.
• Bounds: no allocation, dependency, unsafe code, new opcode, or compiled-pattern data. The linked benchmark's instruction section grows by 3,840 bytes (0.098%); its text segment stays the same size. Avoiding temporary entries can avoid the hard stack cap, consistent with ADR-017's rule for work left out.
• Validation: 155,520 fused/reference comparisons cover UTF-8 and ASCII, malformed bytes, captures, backreferences, look-aheads, search options, retry limits, logical ends, and forward/backward ranges. A separate test crosses configured stack-limit boundaries. The reference switch exists only in test builds.
• Impact: the original in-dispatch implementation improved HTML and Jinja strings but a broader verification confirmed Semver hyphen ranges at +5.90%. Neither Semver program executes the new opcode path; the added logic changes generated code in the shared VM. Keeping selection and scanning separately out of line reduces the slowdown. In the revised local Apple M1 Ultra matrix against 164bb80, all 29 cases receive 16 paired comparisons: HTML markup −7.00%, Jinja strings −3.07%, Jinja integers −0.13%, Semver version −0.28%, and Semver hyphen +1.13%. No median slowdown reaches 3%, but the Semver hyphen interval still extends to +6.20%; Jinja strings do not exceed a 3% gain in both cycles. An independent 64-pair confirmation over 32 layouts puts Semver hyphen at −0.32% (descriptive interval −0.67% to +0.17%), Jinja strings at −4.82% (both cycles beyond −3%), and Jinja integers at +0.09%. Its same-binary Semver control is −0.24%. The full matrix and wider confirmation are reported separately. The fix investigation records the independent wider-layout confirmation, rejected alternatives, profiles, disassembly, all raw measurements, and exact source/build provenance. These are workload-specific local results, not a cross-platform guarantee.

Counted character repeats (src/regcomp.rs, src/regexec.rs)

• Trigger: a greedy C{n,m} (m >= 2, with a range C does not expand inline) or C{n,} (n >= 2) whose body is one character instruction that cannot be empty: a class with no multibyte members (negated or not), one ASCII byte (also case-folded), or .. Lazy ranges, captures, multibyte literals and classes whose case folding adds multibyte members keep Repeat.
• Execution: CClassRepeat and AnyCharRepeat take as many characters as allowed, then give back one at a time down to n, in the counter loop's order, with one lazy backtrack range per run instead of a RepeatInc and an Alt per character. A run of one-byte characters followed by a literal gives back only the positions that hold the literal's first byte, as C's PUSH_IF_PEEK_NEXT does.
• Limits (ADR-017): the loop never counts more retries than C. C's REPEAT counts every give-back, as this loop does; its {n,} expansion pushes only where the follower can start, and so does this loop for one-byte runs. Other {n,} bodies that cannot be empty keep the expansion up to 1,024 instructions (INFINITE_EXPAND_LIMIT_SIZE; the grammars and the production catalog need at most 126) and take C's REPEAT past that: the expansion grows with the count, and nested counts multiply it (the pattern-compile fuzzer's }{1,}{26666,}{1,}{26666,} compiled for over three minutes into some 20 GB).
• Bounds: the bitset of the class in the instruction; no stack scan for the count.
• Impact (callgrind instructions per steady batch, production lane): semver_version_parse 155,656 → 98,122 (−37%), semver_hyphen_range_captures 41,491 → 40,186 (−3.1%). Controls without a counted loop on the measured path moved with the code layout, which was not isolated: uuid_v4 5,120 → 4,967 (−3.0%), ipv4_validation 4,725 → 4,563 (−3.4%), jinja_float_token 61,814 → 60,169 (−2.7%). django_email_domain 2,279,615 → 2,255,545 (−1.1%) has one counted loop, in the xn-- alternative of its top-level domain, which no measured input reaches. tiktoken_o200k_base (tokenizer corpus, 5 batches) 2,072,743 → 2,072,081 (−0.03%); its only bounded repeat, \p{N}{1,3}, is a multibyte class and keeps Repeat.
• Validation: src/counted_repeat_tests.rs compares the loop with the counter loop (a test toggle) over bodies, bounds, followers, multibyte and malformed subjects and every start offset, with C Oniguruma under the ffi feature, and checks the retry and stack limits against C and the counter loop.

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.

Selective extra start maps (src/regcomp.rs)

Where C finds no optimizer, the extra class and type byte maps (optimize_nodes with start_maps) can give the search a start map. A map at the match start is searched once for every position it admits, which costs a fair part of a failed attempt, so it pays only where it leaves out bytes that text actually holds.

• Rule (extra_start_map_filters): a map at the match start becomes the search optimizer when the bytes it leaves out are worth at least 1/20 of the ASCII bytes' position value, on C's own frequency scale (map_position_value: 12 for space, 10 for tab and newline, 6 for letters and digits, 4–7 for punctuation, 606 for all ASCII bytes). Maps behind a line anchor, whose search also steps to line starts, are kept as before, and so are maps at a distance above 0: they are searched once per window, which the bytecode start map narrows, or once per search where the distance is unbounded, and there they keep a RegSet entry a fallback entry with a start filter.
• Otherwise: the search attempts every position, as C's does. The map still routes RegSet dispatch (first_byte_map), whose table costs the same for any map, so the scanner routes every entry as before.
• Threshold: per-pattern instructions over the 718 Shiki patterns with such a map put the break-even between 1/20 and 1/10 of the value; at 1/20 only maps whose search measured slower are dropped. Maps that leave out only a backslash ([^\\]), quotes, brackets, or tab and space fall below it; \S (whitespace, worth 44) stays above.
• Bytecode start maps: the window and fall-through filters (window_start_map, search_start_map) cost one table lookup per position, not a search. Dropping their weak maps measured no gain, so they stay.
• Impact (instructions retired, a search from every start of every line of a mixed 213-line corpus, all 14,950 Shiki patterns): the 51 patterns whose map is dropped take 15% fewer in total (−35% to +2.2%); [^\\]$ and (?=[^\\])$ go from 1.84× and 1.95× C's instructions to 1.20× and 1.46×. All patterns together −0.08%, with unchanged results. Scanner replays (C++, Java, SCSS) and grammar compilation stay within ±0.2%, their run-to-run spread.
• Alternations (branch_start_map): C's merge drops an alternation's map where the branches' best maps sit at different distances, and a sequence often prefers the map of a later item, as the case folds a class adds beside it do ([aA]ʾ takes the map of ʾ). With the extra maps, where that merge leaves no map, the branches' maps at their start (each the map of the branch's first item, where that item reads a character) give every byte a match can start with. Without it, (?i)[-.\w]+ searched every position.
• Bounds: one pass over the 256 map bytes per expression with an extra map; no new data.

Exact lead bytes of multibyte class members after a look-behind (src/regcomp.rs)

The extra start map of a class with multibyte members takes every byte from 0x80 up, because any lead byte may start one. After a leading look-behind, every such byte before the first match costs a failed attempt (700–1,000 instructions each), though a UTF-8 character of a small explicit set has few lead bytes.

• Trigger (utf8_class_lead_bytes, narrow_leads): the extra map of a pattern whose leading node is a fixed-length positive look-behind (look_behind_reach above 0), in UTF-8, for a class that is not negated and whose multibyte part is at most 16 single code points. Other classes keep every byte from 0x80 up.
• Rule: a byte from 0x80 up is a lead when it is a character of its own (length 1) that the bitset holds, or the lead of a longer character whose decoded code is a multibyte member. The decoder masks every continuation byte to its low six bits, so a lead of length n reaches the codes from its base up to base + 2^(6(n-1)) - 1, overlong forms included. U+FF03 is reached from EF and from the overlong F0 8F BC 83, which both this engine and C match, so F0 stays in the set.
• Execution: compile time only; the map is a superset of the bytes a match can start with, so the search makes the same attempts from the bytes it keeps. Nothing changes at match time.
• Observability: none. A look-behind still restricts the start positions as before (start_map_may_skip).
• Bounds: one pass over at most 16 code points and the class's bitset, into a 256-bit set; no allocation at match time.
• Validation: narrowed_class_leads_match_the_full_high_bytes compares every search of 14 patterns (look-behinds, (?i), negated and range classes, an emoji, an overlong sequence) over nine mixed subjects, from every start, with the map that keeps every byte from 0x80 up; with the ffi feature it also compares with C. It also checks that U+FF03 gives exactly EF and F0.
• Impact (callgrind instructions per steady batch, production lane; base origin/main 2a692ca): mastodon_hashtag_regex_step 101,393 → 98,589 (−2.8%). The search stops at the first match, so only the attempts before it are saved: the benchmark inputs have a few non-ASCII bytes before their hashtags. Controls: wordpress_shortcode_captures 48,444 → 48,470 (+0.05%), uuid_v4 5,110 → 5,108, tiktoken_o200k_base (tokenizer corpus, 5 batches) 2,072,888 → 2,072,888.

Attempts continued in the VM (src/regexec.rs)

Where a forward search attempts position after position and each attempt fails at once ((\1), \s*(;), (?<=})|(?=#)), the fixed cost of an attempt dominates: the call into match_at_impl, its prologue (stack and capture arrays, limits, the invariants the compiler loads for the dispatch loop) and its epilogue.

• Trigger: the forward position-by-position loop of onig_search_inner_core_with_right_range (no optimizer, or C's optimizer with an unbounded distance falling through to it), for expressions without callouts. The attempt of a two-pass capture search that records captures (its first, see Empty matches and first-attempt captures) keeps its own call, since it alone records them.
• Execution: the steps between two attempts (C: the search retry check, the loop condition and s += enclen(...), plus the Rust-only start filters and leading-run skips) live in ForwardScan. The search loop runs them after an attempt that returns; match_at_impl runs the same steps where an attempt fails at the bottom of its stack, resets the state its prologue sets up (stack with the bottom sentinel, capture arrays, retry budget of the attempt, call nesting, guard state, best_len/best_s), and goes on with the next attempt at p = 0. A match, an error or the end of the range ends the call as before; scan.at gives the attempt's start.
• Observability: none. Every attempt runs, counts its retries into the search's count and checks the search budget at the same point as before, and stack and time limits see the same stacks and backtracks. FIND_LONGEST attempts that reach the bottom after a match still return.
• Impact (instructions retired, a search from every start of every line of the shared 213-line corpus, Ferroni / C): (\1) 1.52× → 1.09×, \s*(;) 1.70× → 1.35×, (?<=})|(?=#) 1.47× → 1.18×, (\1)|(\n) 1.71× → 1.40×; over the 89 Shiki patterns at or above 1.3× C's time, 1.58× → 1.35× in total. A full Shiki perfscan (time, every pattern) and the captured scanner replays (cycles) improve or stay within their spread.
• Bounds: no new data or allocation; the reset is the prologue's work without the call. Per-attempt state added to match_at_impl's prologue must also be reset in attempt_failed!, or later attempts of a scan would inherit it.

Case-fold alternatives in look-behinds (src/regcomp.rs)

Under (?i), the parser expands a class holding a character with a multi-character fold into Alt(class, "ss", "fi", …). In a look-behind, C then divides the alternatives into one look-behind each; (?i)(?<![-\w]) gets about a hundred.

• Rule (strip_redundant_casefold_alts_in_lookbehind): where the last character of every such fold string is in the class, the look-behind keeps only the class. A fold string that ends here means its last character, which the class holds, ends here too, so the class alone decides the same positions.
• Syntax: the strip turns branches of different lengths into one fixed-length class, so it runs only where the syntax allows those branches (ONIG_SYN_DIFFERENT_LEN_ALT_LOOK_BEHIND or ONIG_SYN_VARIABLE_LEN_LOOK_BEHIND). Perl, Perl_NG and Python reject the look-behind with ONIGERR_INVALID_LOOK_BEHIND_PATTERN, as C does. All Shiki patterns, compiled in six syntaxes with no options, IGNORECASE and CAPTURE_GROUP, give C's compile results.

Guard chain skip gates (src/regcomp.rs, src/regexec.rs, src/regint.rs)

• Trigger: a chain of at least eight guarded pushes (PushOrJumpExact1, PushOrJumpByteSet) in which each guard's push and skip target is the next guard, as for the alternatives of an alternation. A case-fold class with multi-character folds under (?i) makes such a chain: (?i)[[:word:]] compiles to 1795 instructions, about 45 string alternatives behind the class, and every backtrack into it walked all of them.
• Rule (attach_guard_skip_gates): every guard whose successor is a guard gets a GuardSkipGate in RegexType::skip_gates, which holds the union of the byte sets of the guards from it on, the sum of their counted backtracks, the address of the first instruction that is not a guard, and the number of guards covered. Gates are attached only where they cover at least MIN_GATED_LINKS (8) guards; a shorter chain keeps the one-by-one walk, since its check costs about what the walk saves. The guard's skip_gate is an index into the table.
• Execution: when the current byte is outside the union, every guard of the chain would miss, so the VM jumps to that instruction and counts the sum at once. Otherwise the guard runs as before. The bytecode, every guard's own address, byte set and count, and the stack are unchanged; the gate never pushes.
• Observability: the sum equals the counts of the one-by-one walk. The gate is taken only where none of those counts can reach the retry limit in match or a search budget, and no time limit or match stack limit is set; elsewhere the guard runs as before, so a limit trips at the same backtrack and at the same stack entry.
• Bounds: one 32-byte set and three integers per attached gate, built in one pass over the bytecode at compile time. No opcode, allocation per match, dependency or unsafe code.
• Replaces the bounded walk of failed forward guards that 42bb9c9 (#362) added to the VM (skip_failed_ascii_guards). That walk ran the same byte tests one guard at a time without returning to the dispatcher; it saved about 20% of the Django domain pattern's instructions but cost 1–12% on most other production patterns (callgrind, std mode: semver_hyphen_range_captures +12.5%, fluent_bit_nginx +7.3%, django_email_local_part +7.3%, tiktoken_cl100k +6.9%), because every failed guard entered it. A gate decides a whole chain with one byte test and exists only where a chain is long, so the walk was removed; its differential test now compares the gated and the ungated program.
• Impact (instructions, measure.sh, against perf/regex-runtime at 3fa1a91, which still included the batched guard walk): django_email_domain std 441.7 M to 252.3 M (−43%, 20 iterations); django_url_regex std 923.5 M to 837.8 M (−9%, 5 iterations); django_email_local_part std 81.4 M to 82.1 M (+0.9%, 200 iterations); uuid_v4 std unchanged; tiktoken_o200k std 216.7 M to 218.2 M (+0.7%, 20 iterations); tiktoken_cl100k std 238.7 M to 241.1 M (+1.0%). With gates on every chain of two or more guards the domain pattern was the same (253.6 M) and the tokenizer cases were +3.5% and +4.4%, which is why the threshold is eight; four guards is +3.0% on tiktoken_o200k. Compile cost was measured before the rebase only: django_email_domain compile 2.18 G to 2.21 G (+1.0%, 20 compiles). The batched guard walk and the gates overlap only on long chains: with gates on, disabling the walk costs django_email_domain +1.6%, and it costs django_email_local_part about 6% and tiktoken_o200k about 5%; the local-part pattern has no gates, so that cost is the walk itself.
• Validation: skip_gates_match_the_one_by_one_walk compares the gated and the ungated program (SKIP_GATES_DISABLED) over 40 patterns with ignore-case classes, 14 inputs and every start position: results, regions, counted backtracks, and results under per-match and search limits of 1 to 12 and at the counted total. skip_gates_keep_the_retry_limit_boundary checks the public API's boundary against the ungated program.

Literal after zero-width checks and class repetitions (src/leading_run.rs, src/regexec.rs, src/regset.rs)

Grammars put look-behinds with many alternatives, anchors and \s* in front of a literal ((?<=[!(+,:=>?\[]|^await|…|^return)\s*(\{), (?i)\s*(text:)). C's optimizer finds nothing at a fixed distance, so it attempts every position and runs every look-behind alternative there.

• Trigger (plan_literal_prefix): the expression reads zero-width checks (anchors, look-arounds, alternatives of them), class and type repetitions and single classes, optionally in groups, and then a case-sensitive literal whose first byte is ASCII and outside those classes. Expressions with a leading-check jump (^, a look-behind at a literal) keep it; it already lands on fewer starts.
• Execution: memmem finds the next occurrence, the search scans back over the class bytes before it, and only the starts of that run up to the occurrence are attempted. A start before the run would have to cross a byte outside the classes. The RegSet position-lead fallback skips the same starts; there it looks for the occurrence only 64 bytes past the entry's stop and, finding none, keeps every start whose class run reaches past that window.
• Observability: a left-out attempt fails with at most paths × (cost + 2) backtracks, from the tree's alternatives, bounded repetitions and checks. The plan stays off for FIND_LONGEST, a search retry budget, stack or time limits, a per-match limit at or below that bound (or any per-match limit where a repetition is unbounded), and callouts.
• Malformed UTF-8: the scan back needs a valid segment, and every position is attempted otherwise; a non-ASCII byte that a class may hold keeps every start.
• Impact (time, a search from every start of every line of the shared 213-line corpus, Ferroni / C): the angular, JavaScript and vue-vine look-behinds 1.29–1.34× → 0.09–0.10×, crystal's 1.36× → 0.10×, haxe's (?<=trace|…)\s*(\() 1.14× → 0.10×, mermaid's (?i)\s*(…:) about 1.1× → 0.15×; 187 Shiki patterns gain more than 10%, with unchanged results over all of them. Scanner replays (instructions): SCSS −1.8%, C++ and Java within ±0.1%; grammar compilation +0.1–0.4%.
• Bounds: one boxed plan per eligible expression (a memmem finder and a 256-bit class); the scans are linear. No new dependency or unsafe code.

Start maps after a leading look-behind (src/first_bytes.rs, src/regset.rs, src/regexec.rs, src/regcomp.rs)

The Rust-only start maps decide by the byte at a start. A fixed-length positive look-behind before the first character a match reads (look_behind_reach) can, over malformed UTF-8 or from inside a character, make the match read bytes before or past that start, as in C (#259).

• Rule (start_map_may_skip): a map leaves out a start only where the characters the look-behind steps back over line up: each lead, found by stepping back over continuation bytes, reads forward to where its step began. That costs one comparison where the bytes before the start are ASCII.
• Sites: the position loop's start filters, window and bytecode start maps, the RegSet fallback start filters and its per-entry searches, and the leading-run and literal-prefix admission. The RegSet table attempts the entries a Rust-only map routes (look_behind_entries) wherever the characters do not line up, in index order, and its needle stops at non-ASCII bytes for them; its threshold pre-filter does not reject such a start. Push guards end at a positive look-behind.
• Extra map as optimizer: C's map search cannot ask the rule, so where an extra start map is the optimizer (extra_map_optimizer) and a leading look-behind can move the start, the search goes without it (map_search_bypassed), as C without an optimizer does, threshold included. The map then filters the position loop where it sits at the match start.
• Valid UTF-8: a scanner's subject is a &str, where every character lines up. Its RegSet searches (onig_regset_search_utf8, onig_regset_entry_search) skip the checks and keep the extra map search. The flag lives in the set, not in MatchArg: a field there changed the VM's code generation and cost 3% in the Java replay.
• Impact (instructions retired against #260): the search workload −1.2%, scanner replays SCSS and Java +1.0%, C++ +0.8%, grammar compilation +0.7%. Tests compare fused and upstream look-behinds and look-behind-led RegSets with C on malformed UTF-8.

DFA pre-filter for RegSet searches (src/dfa_prefilter.rs, src/regset.rs, src/scanner.rs)

A TextMate scanner asks its set for the earliest match of any pattern, and most of the attempts the position-lead search makes fail: in the captured C++ replay, 70% of the cycles go into losing attempts, 40–70% in the Java, C and PHP replays, 20% in SCSS. The pre-filter decides, before any attempt, which entries can match where. It was prototyped in the spike #320 (refs #252).

Ferroni's two-stage scanner pre-filter was inspired by Keith Hall's seek-filter proposal and his implementation in fancy-regex. His design uses a conservative regular approximation to find candidate positions before the backtracking engine verifies the full pattern. Ferroni adapts that idea to its Oniguruma port with a multi-pattern DFA built on regex-automata; fancy-regex's RegexSet also informed the scanner design.

• Seeks (dfa_prefilter::derive): a pattern's tuned parse tree is written as an over-approximation in regex-automata's HIR, its seek: wherever the pattern can match, the seek matches too, never fewer places. Literals, classes, concatenation, alternation and repetition are exact; groups are transparent; look-behinds, negative look-aheads, \G, \K and text-segment boundaries become empty; back references and calls become (?s:.)*; a positive look-ahead keeps its body where nothing consuming follows it; a conditional is the condition followed by its then branch, or its else branch (a group-number condition is a zero-width check, any other reads what it consumes); \W is every non-ASCII character and the ASCII non-word bytes (the complement is taken over the exact ASCII set, never over a widened one); a negative look at a class that holds every ASCII word character ((?<!\w), (?<![-\w]), (?![.:\w])) becomes the ASCII half boundary it is contained in, so a keyword list behind it is not a candidate inside every identifier; a Unicode word boundary becomes the ASCII boundary or either half boundary. Classes are byte-based: the ASCII members exactly, any non-ASCII member as one UTF-8 sequence; any character is an ASCII byte or such a sequence (one byte would miss .x at éx). Case-insensitive strings go in as the tuner unravels them; a folded literal trie as its ASCII case variants plus one escape for the non-ASCII folds it accepts: up to L - 1 ASCII characters, a fold, then up to L - 1 characters of any kind, for the longest literal L, so the escape ends where the literal can end and what follows the trie is read from there. Counted repetitions above 64 become unbounded, a repetition of a repetition is flattened to a superset. A seek that matches at every position (a look-behind alone, a*, anything starting with (?s:.)*) narrows nothing: its entry is searched on its own.
• Automata (Automata, shared by the sets over one pattern list through an AutomataCell and built by the first of them that searches with the pre-filter; SetPrefilter is a set's own part, its lazy DFA caches and search state): an overlapping lazy DFA over the covered seeks names the entries whose seek matches at a position, and a pair of lazy DFAs (forward and reverse, the strategy of regex-automata's meta regex) finds the next position where any of them matches. regset_search_body_prefilter attempts, at the current position, every entry in index order: the entries the automata do not cover (their seek matches everywhere: (?<=\)), \G ?) ahead of every covered one first, one attempt each (none where the fallback memo already rules the position out), then the covered candidates the DFA's anchored scan names there merged with the other uncovered entries, so an uncovered entry behind a candidate that matched is never attempted (["a", ".*(?<=z)"]: the second entry's one attempt reads and backtracks over the rest of the line, and attempting it ahead of the winner made tokenizing 40,000 a 3,400× slower). Where no seek matches at the position, the uncovered entries are searched first, over a window, as the position-lead search searches them (the fallback ones through search_fallback_entries, with its memo and its growing windows; the table ones position by position): an uncovered event within the window (OWN_EVENT_WALKS, 256 positions) bounds what the covered entries can still decide, and bounded anchored walks at the positions up to it, where some entry's bytes dispatch, settle that without the search DFAs, which would read on to the next covered seek match or the end of the line (["(?<=b)a?", "a[ab]{2}a"] on ba…: 125× for 160 KB). Only without one, the covered entries are searched, within the window only (candidate_in), so that no call reads further than it decides: where the set has a long seek, a walk at the first position first (a greedy seek matching there would make the search read on to its match end to report that start: ["(?<=z)a[ab]*a", "a"] on ba… read the rest of the line on every call, 3,500× for 80 KB even with a stable identity, the token moving past what the memo knew); then the search DFAs over the window extended by the bounded seeks' maximum length, which finds every bounded seek's match that starts in the window, and the long seeks, whose matches may end past the span, walked at the positions up to that find where their bytes dispatch. Nothing in the window moves the search to the next one, four times the positions looked at so far, so a line without a match is read in a few rounds (["(?<=b)a?", "a[ab]{2}a"] on x×100+ba… without an identity read the rest of the line on every call). With a stable string identity, what the windows found is kept for every later search of the subject (MetaMemo: no entry can decide in a span, one can at a position; the loop head's walks extend the span), so a line is read once over all its tokens. The stretch up to the find is left to the uncovered entries. A decision bounds everything after it, so the uncovered entries are never searched past the current best: with ["a", "(?<=z)"], tokenizing 20,000 a in order costs the same with and without the pre-filter (it cost 4,200× more while the uncovered entry was searched to the end of the subject before the covered ones). The candidates are attempted in index order with the attempt the position-lead search would make (attempt_entry_at: the first-byte table's dispatch for a table entry, C's optimizer admission for a fallback or gated entry from the per-search gate cache, the any-char-star and \G rules, the start filters and first-instruction tests); the first event decides, and without one the search goes on one character later. A candidate position inside a character, which only a seek with a raw byte admits, is skipped. The walks of a subject searched again are kept as well (CandidateMemo: per position, the candidates a walk found there, valid for every search of the subject since a walk reads the subject from its position and asks admission there, which depend on the subject only): recording starts once a search of the subject starts no later than the previous one did, which a tokenizing pass never does (every call starts at the last match's end), so a line tokenized once pays nothing (recording every walk from a subject's second search on cost the captured C replay 10% of its instructions), and a line tokenized again reuses the positions it walks again, as the position-lead search reuses its fallback memo. That memo is why battle_bench's hot single-line rows, which tokenize one OnigString over and over, ran the flat TypeScript scanner (279 patterns, 277 covered, 47,000 NFA states) at 3.3× the time without the pre-filter (8.2 against 2.5 µs for 7 tokens: every call walked 50 bytes and asked admission for the long seeks, while the position-lead search had every fallback entry's result memoized) although its document row, where every line is cold, ran at 0.18×; with the walks kept, and a match state recorded once per walk rather than at every byte of a word, the line takes 1.4× (3.6 µs) and the Rust rows gain another 20%, while the cold Rust document row pays 5% for the per-walk bookkeeping.
• Bounds on a search: the anchored scan reads at most CANDIDATE_SCAN_BYTES (256) past a position and declares every covered entry a candidate where the DFA is still alive there (64 cost the C++ replay 30%, its identifiers and keyword alternations run past 64 bytes; SCSS and PHP did not move). The scan also stops as soon as every covered entry has been recorded, where nothing more can be learned: tokenizing a word run in order with [(?<=\.)\w+, a] on 20,000 a, where both seeks match after one byte but \w+ stays alive, read 256 bytes from every position (18 ms against 1.0 without the pre-filter) and now reads one (2.4 ms against 1.5). The same shape with an entry the search never attempts ([(?<=\.)\w+, \w+:, \d+, a]: \w+: keeps the DFA alive through the run while C's optimizer rules it out for the whole subject, its : being absent, and \d+ is not dispatched on an a) took 270× the time without the pre-filter, so the walk also stops once every entry that can still be recorded is one the search would not attempt at the position. A seek whose matches are at most LONG_SEEK_BYTES (16) long has settled after that many bytes (matched or dead), so only the longer and the unbounded seeks can keep a walk alive past that; of those not yet recorded and dispatched on the byte, the walk asks the search which entries it admits at the position (covered_entry_admits_at: the anchors, the threshold, the start filter and the optimizer's range from the per-search gate cache), and stops once every admitted one has been recorded. Asking costs about as much as a long walk (asked before every walk, it cost the C++ replay 57% more instructions and SCSS 89%; asked once the bounded seeks had settled, still 8% and 31%), while no walk of the captured replays reaches the bound, so a walk asks right after the bounded seeks settled only while the set's walks keep running to the bound or ending by such an ask (ask_early), and otherwise after LONG_WALK_BYTES (64): the replays ask in fewer than 0.1% of their walks and stay within 1% of their instructions, the two shapes above take 1.6× and 1.5× the time without the pre-filter, and [(?<=\.)[a-z]+, [a-z]+\(, b, a], 100 ms on both paths, stays at 1.2×. After PREFILTER_FAILED_POSITIONS (64) candidate positions in a row whose attempts all failed, the pre-filter gives the search up and the position-lead search takes it from the start. Without these two, a seek that matches at every position of a long run while the pattern fails there (\w+ for (?<=\.)\w+ on 40,000 a) made the search read the rest of the run from every position: 10 s against 0.5 ms without the pre-filter; with them it is within 1.2× of the search without the pre-filter at 10,000, 20,000 and 40,000 characters, and linear. fancy-regex's RegexSet has the same loop shape, which is why this was measured. The budget is never reached in the captured replays: the longest run of failing candidate positions is 21 (PHP; C++ 13, Java 10, SCSS and C 6, over 6,700–8,800 runs each). Asking the DFA at the current position first also spares the search DFAs, whose leftmost-first search has to find where a match ends, at every candidate position; the keyword-list seeks of SCSS paid most for that, and the SCSS replays halved (the table below predates it).
• Trigger: scanner sets (onig_regset_new_shared); the dfa-prefilter Cargo feature, on by default, and ScannerConfig::prefilter, on by default. The feature enables regex-automata's perf-literal and perf-inline, regex-automata's literal prefilters (#327): up to 2.0.0 only Ferroni's own benches had them, through the features their dev-dependencies (regex, fancy-regex) unify in, so a crate depending on 2.0.0 replayed the captured traces 3–10% slower than the published numbers (C 10%, JSON 8%, Astro 6%, SCSS 5%, C++ 3%, PHP within noise; a downstream-shaped build against the same code with those dev-dependencies added), and with the two features it matches them (within 2.3% of the instructions and 3.3% of the time, either way). Only scanner patterns derive a seek (onig_new_for_scanner), and the regex does not carry it: it is kept in a compact encoding (SeekCode: the HIR's nodes in pre-order, a few hundred bytes where the HIR holds tens of KiB; decoding rebuilds the HIR through the smart constructors that built it, which are stable on their own output, as a debug assertion and a test over every seek of the captured grammars check), the set holds it until ScannerConfig::prefilter_warmup searches the pre-filter would have decided have passed and the next one builds the automata (32 by default; see Warm-up and tiny sets), and a ScannerPatternCache keeps one per distinct pattern and the automata of every pattern list (ADR-006). The C API's sets build no pre-filter.
• Warm-up and tiny sets (#327): Ferriki's JSON highlighting took 10–14% longer with the pre-filter and its Astro highlighting 17–34%, both reproduced in Rust alone through the captured replays (benches/json_scanner, benches/astro_scanner) and Ferriki's own pipeline (JSON 3.1 against 2.7 ms per large document, Astro 18.4 against 13.7). Two causes. Ferriki recompiles an end rule whose back references resolve to new text, 64 scanner instances per pass of the large Astro document, each answering one or two calls before the next replaces it; each paid the seek derivation at compile (the pass's constructions 2.5 → 4.5 ms) and the automata build at its first search (3.8 ms per pass), while the long-lived sets' searches took 1.7 ms against 3.6 without the pre-filter: the replay with those instances rebuilt per pass took 12.5 ms against 6.8. A set now builds its automata by the search after prefilter_warmup (32) searches the pre-filter would have decided; a scanner searched fewer times never builds them. The churn replay takes 6.5 ms against 6.7 without the pre-filter, and the first replay of a trace, which builds the automata of the sets it touches, 71 ms uncached and 45 through the cache for C++ against 192 and 119 (31 of its 96 sets build), 56 against 122 for Astro (39 of 153), 86 against 88 for SCSS (its sets are all hot) and 11 against 13 for Java; the steady state is unchanged (below). The six JSON sets, 3 to 11 patterns over 24 to 104 NFA states, took 1.5 to 2.5 times their time with the pre-filter (the replay 0.50 ms against 0.27). A calibration over the seven replays with the test-only work counters (VM attempts, first-instruction rejections, table-scan bytes, the optimizer's forward-search bytes, walks, scan steps, search DFA searches) found that on the six JSON sets the pre-filter avoids no VM attempt and no forward-search byte at all — the first-byte table and the first-instruction tests already reject what its walks reject — and that the losing sets of the other replays avoid at most one attempt and 41 forward-search bytes per call, where the sets that gain most avoid tens of attempts (C++ group 58: 58 of 60 per call). Sets of at most 12 covered entries over at most 128 NFA states lose more than they gain in every replay: without their automata each replay is faster, by 7 µs on C++ to 216 µs on JSON (summed per set); 11 of them gain, at most 9 µs over their calls (C++ group 81 and Astro group 86, two patterns each), and the next winners hold more states (a Java set of 10 patterns over 200 states gains 110 µs over its 192 calls; a C set of 8 over 214). Such a set builds no automata (TINY_SET_ENTRIES, TINY_SET_NFA_STATES) unless the scanner asks for the pre-filter from the first search (prefilter_warmup(0), for tests): the JSON replay takes 0.275 ms against 0.268 without the pre-filter (two-round ABBA Criterion, in the table below; a fixed-iteration replay times both at 0.270 ms, and the difference is not explained), the Astro replay 1.70 against 3.60, and the other replays are unchanged. A retirement by measured payoff was tried in three forms and left out: an estimate of the attempts the table would make from the dispatch counts at the walked positions misjudges winners whose savings are fallback-entry searches (C++ group 78: 0.1 estimated against 13.9 avoided attempts per call); a work count of both paths, taken on alternating searches, retires sets whose avoided attempts are few but deep (PHP group 8, 1.4 ms of the replay's 1.8), because an attempt counts one unit whatever the VM reads; and a timing of both paths needs the lazy DFA's state creation told from its steady state and a clock that wasm targets lack. The remaining 1.8.0 → 2.0.0 cost of the JSON replay without the pre-filter (0.224 → 0.265 ms, +18%) is a sum of small per-call costs of the first-instruction word boundaries, the shared compiled patterns, the character class fixes of 1.9.0 and the extensible scanner types, each paired with larger gains elsewhere (the Astro replay fell from 4.7 to 3.6 ms over the same releases); none is reverted here.
• Observability: the pre-filter leaves out attempts that cannot match, whose backtracks and subexpression calls a limit would count; C makes them and may stop at the limit. So it decides only a search under Ferroni's defaults (10,000,000 retries per match, no search retry budget, stack, time or subexpression call limit); a search under a limit of the caller's own keeps C's attempts, and the limit errors of every scanner route stay C-identical (limit_errors_match_c_on_every_route_and_call_history). It stays off for FINDLONGEST, for sets with callouts, and for a search that starts inside a character (find_next_match takes any byte offset; the seeks read whole characters, and C attempts that position). The default retry limit is still a limit: a losing attempt the pre-filter leaves out can exhaust it on the search without the pre-filter ((a+)+b before c on a run of a), so a call the pre-filter decides stays on the scanner's RegSet route, and the per-regex route, which has no pre-filter, never answers an identical call differently (onig_regset_prefilter_decides). Over time one scanner can still answer an identical call two ways: a set searches without the pre-filter for its first prefilter_warmup searches and with it afterwards (see _Warm-up and tiny sets), and a retirement switches it back for good, so where a left-out attempt would exhaust the default retry limit, the answer changes once at each switch (a set of six patterns led by (a+)+b and c, on 27 a before c b: no match for the first 32 identical calls, c from the 33rd; through the cache route later, by the calls it sent to the per-regex route, which do not count toward the warm-up). Both paths find the same match, in the same time order, with the same captures: a matrix compares them on every route and find option over the constructs the seek approximates, and tests/compat_prefilter_differential.rs compares them over every pattern/text pair of the compat files the scanner accepts, at every character boundary.
• Bounds: MAX_NFA_STATES (65,536) bounds what one set builds and keeps; the NFA size limit is 16 MiB, the lazy DFA caches 2 MiB (search DFAs) and 1 MiB (overlapping) per set. The cache caps were measured again once the automata were built lazily: a full replay fills a hot set's overlapping cache to 882 KiB of its 1 MiB (SCSS; C++ 620 KiB, PHP 692 KiB) and its search caches to 1.36 MiB (PHP; C++ 987 KiB) without one clear, so they stay; lower caps would clear on these replays, and would not shrink the other sets' caches, which hold only the states they visited (PrefilterStats::cache_memory_usage). A set whose overlapping DFA cannot reuse its cache retires the pre-filter for good: the DFA gives up once its cache was cleared MIN_CACHE_CLEARS (3) times while it had searched fewer than MIN_BYTES_PER_STATE (20) bytes per state it holds (regex-automata's own efficiency check, which the walk feeds its progress; the search DFAs give up on the same clear count, and at 10 bytes per state, as the meta regex's own lazy DFAs), the walk ends as at the bound, and the set drops its automata after the search and searches as the position-lead search does from then on (retire_prefilter, PrefilterStats::retired), which is the search the pre-filter stood in for. The flat scanner of battle_bench over all 117 patterns of the CSS grammar is such a set: 116 case-insensitive property lists in one automaton make every DFA state hold thousands of NFA states, so a 1 MiB cache holds a few hundred of them, and tokenizing the CSS document, where a \G-anchored zero-width entry wins at every position, walked up to 256 bytes from every position ([^;]*-like seeks keep the DFA alive) and cleared the cache every 30 calls, 100 µs a call against 0.4 without the pre-filter: the document took 17 ms against 0.24, and 13 ms against 0.10 line by line. It retires within its first pass and takes 1.00×. The replays never clear a cache, so nothing retires there. The state bound is a complexity bound, not a break-even: measured per scanner group over the captured replays (prefilter_census example, groups mode), size does not tell which sets lose. C++ sets of 25,000 NFA states take a quarter of their time, the PHP set of 37,437 states 2%, while the hot SCSS set (group 8, 17,500 states, keyword lists behind the first-byte table and first-instruction tests, which already reject most attempts cheaply) takes 13% more, and SCSS sets of the same size take 25–60%. After the review fixes (class members read as the matcher reads them, the escape of a folded trie ending where its literal can end), a two-round ABBA put SCSS group 8 at 0.99 of the time without the pre-filter and left the C++ and PHP cases within 0.02 of the table below; with the candidate scan running first (see Bounds on a search), SCSS group 8 takes 0.55 and the SCSS document 0.55 (two rounds: 1.09 → 0.593 ms and 2.69 → 1.47 ms), the C++ and PHP cases again within 0.02. With the uncovered entries searched inside the loop (see Automata), a two-round ABBA left the SCSS cases at 0.55 and 0.57 and the C++, C and PHP cases within 0.02 of these numbers, and the SCSS replay within 2% of its instructions before: the search DFAs are asked only where no seek matches at the current position, and a set the automata cover entirely readies no fallback memo (a first version of that loop did both after every failed candidate position and every call, 8–10% of the SCSS replay's instructions). A runtime probe that times a set's first searches on both paths was tried and dropped: the lazy DFAs build their states on first use, so a hot set's first replay runs 2.5–4× slower than its steady state (C++ group 78: 11.7 ms, then 1.6 ms against 7.0 without; SCSS group 8: 4.6 ms, then 1.2 against 1.05; the whole C++ trace: 34 ms, then 3.4 against 13), and the probe turned off the sets that gain most.
• Costs (prefilter_census example, census and replay modes, release build with a counting allocator, min of three constructions): a scanner pays in three steps. Compiling a pattern derives and encodes its seek: constructing every scanner of a trace with the pre-filter takes 1.1–1.6× the time without it (C++ 236 → 320 ms uncached and 24.5 → 32.2 ms through one pattern cache; SCSS 63 → 94 and 8.5 → 12.0; C 22.7 → 30.0 and 2.6 → 3.1; PHP 190 → 222 and 59.7 → 73.9; Java 5.1 → 8.2 and 1.1 → 1.5), and the scanners then hold within 2 MiB of what they hold without it (C++ 97.4 against 95.6 MiB uncached, 11.1 against 11.0 cached; the encoded seeks of the 250 distinct C++ patterns take 0.1 MiB in the cache, 0.6 KiB each, PHP 0.9 KiB, SCSS 0.8 KiB). The first version built the automata in the constructor from a live HIR per seek: 1.5–2.9× the construction time (C++ 459 ms uncached, 154 ms cached), 187 MiB and 108 MiB held, 22–31 KiB per seek in the cache (C++ 5.4 MiB, PHP 7.9 MiB). The automata are built by the first search the pre-filter decides, about 2 ms per set (decoding its seeks, then two NFA compilations, the forward one shared by the overlapping DFA and the forward search DFA, and the reverse one; the meta regex it replaced compiled both again, the forward one with capture states; the build's instructions fell from 797 M to 577 M on the C++ trace, 1.32 G to 0.86 G on SCSS and 98 M to 63 M on Java, callgrind over one replay), so the first replay of a trace, which touches nearly every set, takes what the constructor took before (C++ 192 ms uncached and 119 ms through the cache against 3.3 ms once built; SCSS 88 and 79 against 1.4; C 45 and 25 against 1.1; PHP 83 and 73 against 1.6; Java 13 and 11 against 1.1), while a scanner that never searches never pays it, which is most of them in a highlighter that holds hundreds of grammars. Scanners built from one pattern cache over the same pattern list share the automata (52 of the 96 C++ scanners repeat another's list, 10 of 29 for C, 4 of 27 Java, 3 of 35 PHP, 1 of 20 SCSS): after the replay the C++ automata hold 24.4 MiB instead of 38.2 and the heap 84 MiB instead of 110 (C 4.1 instead of 7.9 MiB and 16.6 instead of 22.5; PHP 50.9 instead of 60.1; SCSS 38.4 instead of 43.6). The rest is the scanners' lazy DFA caches, which fill as they search: 34.6 MiB over the 94 C++ sets after the replay, up to 1.5 MiB for one set, 12.2 MiB for SCSS, 10.4 for PHP, 7.8 for C. The replay driver's maximum RSS over 30 replays is 112 MiB through the cache against 140 before (C 28 against 34, PHP 74 against 78, SCSS 58 against 59) and 222 MiB uncached as before, against 115 and 29 without the pre-filter (the spike kept a live HIR per compiled pattern and reached 279 MiB).
• Impact (ABBA Criterion, min of three, same binary with ScannerConfig::prefilter off and on, fancy-regex's RegexSet from the same run, M1 Ultra):

• Not applied: sets whose automata would exceed the bound; entries with callouts; searches under limits of the caller's own; the per-regex cache route of the scanner, which combines per-entry searches.
• Validation: unit tests pin the seek of each construct, and that a pattern compiled without the pre-filter, with callouts or under another encoding has none. The matrix test above, the pattern-cache comparison and the limit tests run with the pre-filter on; the library tests also run without the feature. The C++, Java, SCSS, C and PHP replays validate every winner and capture against the captured Shiki results, and C++, Java and SCSS against C. Three checks find what hand-written tests miss (the five review rounds of #321 found unsound seeks for \W, the folded trie's suffix, consuming conditions and nested negated classes, and parity gaps in admission, interior byte offsets and route equality): the prefilter-self-check Cargo feature (self_check_prefilter_decision) runs the position-lead search after every search the pre-filter decides, on the same set with the pre-filter bypassed, and panics with the pattern set, subject, start and options unless both decide alike, registers included (the one accepted difference is the position-lead search exhausting the default retry limit in an attempt the pre-filter left out, see Observability); CI runs the scanner suites with it. The prefilter-differential fuzz target compares a scanner with the pre-filter against one without it from every byte offset under every find option, through the cache and UTF-16 routes, over patterns a generator writes from the constructs the seek approximates and over the compat pairs and review regressions as a seed corpus; the fuzz crate builds with the self-check, so the scanner targets check every search they make. tests/ferriki_corpus_differential.rs does the same over every rule's pattern list of a TextMate grammar corpus, tokenizing sample files line by line from every match end (FERRONI_GRAMMAR_DIR, FERRONI_SAMPLE_DIR; see CONTRIBUTING.md). A unit test retires the flat CSS grammar set over a stylesheet and compares every token with the search without the pre-filter, before and after the retirement; another tokenizes a line three times and checks that the third pass walks a quarter of the steps while another identity with the same content walks them all.
• Walk bookkeeping (PatternBits in src/dfa_prefilter.rs, the reused scratch_msa in src/regset.rs): a walk records its candidates in a bitset over the pattern IDs, not a PatternSet with one bool per pattern, and the position-lead MatchArg is boxed, so taking it out of the set and putting it back moves a pointer. Warmed callgrind instructions per replay iteration (prefilter_census replay, the count at five iterations less the count at three, over two), main against this change: C++ 95.6 M to 92.0 M (-3.9%), SCSS 20.8 M to 19.1 M (-7.9%), Java 18.3 M to 17.0 M (-7.1%). A table of pattern masks per match state was measured and dropped: it saved 2.6% on SCSS and 0.4% on C++, and cost 2.6% on Java.
• Match-state recording out of line (record_match, record_needed in src/dfa_prefilter.rs): a walk records the patterns of a match state in a function kept out of line, so the bitset's fields do not compete for registers in the byte loop. Inlined, Ferriki's arm64 addon (fat LTO, one codegen unit) kept the DFA state ID on the stack on every byte, and large TypeScript and TSX took about 10% longer with 2.2.1 than with 2.1.0. Out of line, they take 9.9% and 9.7% less time than unchanged 2.2.1 on an M1 Ultra (median worker change; 3.2% less over the 40-case run), with identical HTML. Keeping only PatternBits::insert out of line recovers the same time but costs a call per recorded pattern: +8–9% instructions on the SCSS replay, against +0.5–1.4% for out-of-line recording. Ferroni's own replay drivers keep the state ID in a register with either build profile and do not show the effect, so the time is measured in the consumer.

Single-pattern seek for standard searches (src/api.rs, src/dfa_prefilter.rs, src/dfa_prefilter/accept.rs)

The DFA pre-filter above serves a scanner's sets. A Regex searched in a steady loop still answered every standard call with the matcher, although the production corpus's validators (uuid, IPv4, IPv6) and its backtracking-heavy patterns (django) run most of their searches on texts that fail early or match early. The seek of a single pattern, the same over-approximation, now answers those calls where it can.

• Trigger: a standard is_match* method, or a standard find* or capture method (find, find_at, find_bytes, find_bytes_at, captures, captures_at, captures_bytes, captures_bytes_at, through the search gate below), on a Regex built with the seek. Not the *_with methods, not the iterators. RegexBuilder::dfa turns the seek on or off; it is on by default with the dfa-prefilter feature and has no effect without it. A pure literal has no seek, and neither has a seek that matches everywhere, a seek with callouts, or a pattern that is not UTF-8. A seek whose NFA would exceed MAX_NFA_STATES is cut before compilation, by an upper estimate of its NFA size, and the regex then has no automaton.
• Compilation: the seek is derived in the same compilation as the program (onig_new_for_single_seek, the seek choice of RustOnlyCompile), from the tuned tree, and kept encoded. Its lazy DFA is built by the first search that consults it (LazySeek, a OnceLock the clones share; a concurrent first search waits for it), not by RegexBuilder::build: the iterators and the *_with methods never consult the seek, and many regexes are never searched at all. Compiling all 34,676 patterns of the 260 tm-grammars takes 989 ms instead of 1,440 ms; the Django domain validator compiles in 1.37 ms instead of 1.76 ms, and its first is_match takes 0.38 ms instead of 0.01 ms, the same in total. There is no second compilation. The automaton is boxed: inline, it grew every compiled regex. The walk writes a single regex's alternations branch by branch, where the scanner's seek shortcuts a class-led alternation as a repetition of its class (ipv4's octet alternation is exact only that way). A trailing \Z ($ without multi-line anchors, the harness's setting for these patterns) reads as (?:\n)?\z, which is exact where nothing follows it. The scanner's seeks are unchanged.
• Exactness (SeekCode::exact): the walk flags every construct the seek approximates. A positive class lists its non-ASCII members one by one when there are at most 16 (a case fold adds the Kelvin sign to k and the long s to s, so a case-insensitive class of letters qualifies); other classes with non-ASCII members are inexact unless they hold all or none of the non-ASCII characters. Also inexact: case folds of strings and multi-character folds, back references, conditions, look-arounds, atomic groups and possessive quantifiers written in the pattern (the seek keeps every way a body matches, the matcher only its first, so (?>abc|ab)c has no match in abc, and its seek does), \G, Unicode word boundaries and \b in any mode but ASCII, \Z anywhere but at the end, counted repetitions above MAX_COUNTED_REPEAT, the range cutter of the absent operator, and gimmicks other than \K. The repeats the compiler makes possessive itself are exact: tune_next makes [a-z]+ in ^[a-z]+@[a-z]+\.com$ an atomic group when the item after it can never match where the body does (C's exclusivity test), which keeps the language: no iteration the repeat could give back lets the item match, so the walk writes the bag as its repetition. Only that pass sets ND_ST_STRICT_REAL_REPEAT on a bag, so the walk (automatic_possessive) tells those bags from the user-written ones, which stay inexact. \A, \z and $ are exact, ^ is exact where a byte follows it in its sequence or branch (the matcher does not hold ^ at the end of a subject after a final newline, and the seek does), and the options NOTBOL, NOTEOL and FIND_NOT_EMPTY make any seek inexact. The tests pin each of these (seeks_are_exact_exactly_where_the_matcher_reads_alike).
• Retry bound: none. The seek computes no static bound on the retries of an attempt. The "match" answer used to need one, so that the process-wide limits could not stop the matcher short of it. Under ADR-017 it needs none, so a pattern with an unbounded repetition (^[a-z@.]+@[a-z.]+\.com$) is answered like a bounded one.
• Answers (seek_answer): "no match" (Some(false)) whenever the lazy DFA finds no seek match from start, under every limit: the matcher can only find a match the seek describes, and a limit can only turn a match into "no match". "Match" (Some(true)) only for is_match* (find* needs the match's bounds), and only when the seek is exact. The argument: an exact seek accepts a text exactly where the matcher finds a match, so its match is the matcher's match with no limit. Under a process-wide limit that would stop the matcher, C stops with an error, and Ferroni answers the result C gives without that limit (ADR-017, rule 2); the seek reports no error, and it never stops where C completes (rule 3). Every other case goes to the matcher. The *_with methods, whose limits are the caller's, never reach the seek.
• Accept seek (derive_accept, SingleSeek::accept_answer): under (?i), a class whose characters have multi-character case folds ([a-z¡-￿0-9] holds ß and ff) comes with an alternative for each string they fold to, built as C builds it (ss as [sSſ][sSſ], ff, st, ...: about seventy per occurrence). Kept, they push the precise seek past MAX_NFA_STATES, and the scanner's seek that stands in for it is inexact, so the django validators ran the matcher on every match. For an inexact seek whose tree has such strings, the walk writes a second seek, an under-approximation whose every match is a match of the pattern at the same start. It leaves the fold strings out (branches of an alternation led by a class that are strings, alternations of strings, or sequences of strings and small classes that stand for at most 64 strings; dropping branches outside negative look-arounds and user atomic groups only removes matches), writes classes as exact UTF-8 (ClassUnicode), folds a one-character negative look-ahead or look-behind into the neighboring item where that item reads a character on every path (\.(?!-)C{1,63}(?<!-) is \.(?:D C{0,61} D|D), D being C without -; an alternation takes the look into each branch, a nullable item splits into its reading and its empty paths), writes the atomic groups C's tune_next makes of a repetition before an item that cannot start where its body does (status STRICT_REAL_REPEAT) as the plain repetition, which matches the same, and writes the anchors as the exact seek does. Any other construct leaves the pattern without an accept seek: back references, calls, conditions, positive look-arounds and other negative ones, user atomic groups and possessive quantifiers, Unicode \w and word boundaries, \G, case-insensitive tries and strings the tuner left whole, and the options NOTBOL, NOTEOL and FIND_NOT_EMPTY. So does a pattern with no fold strings to leave out (a quick scan of the tree decides): its accept seek would be exact, but it keeps the counted repetitions the seek widens, and such automata cost 6 to 9 times the whole compilation of semver_version_parse and semver_hyphen_range_captures, patterns that are only asked for captures. An accept seek's estimate is bounded by a quarter of MAX_NFA_STATES.
• Accept answers: is_match* asks the accept seek first. Its match is a match of the pattern, so "match" follows as for an exact seek (ADR-017, rule 2). Where it finds none, the answer is "no match" if the text from start contains none of the left-out strings, tested by a superset in one pass (any non-ASCII byte, the one-byte strings, and the first two bytes of each longer ASCII one: ss, ff, fi, fl, st in their case variants for the django classes): no path of the pattern through a left-out string can match there, so the accept seek is exact on that text, and its "no match" is the matcher's under every limit. Otherwise the seek and the matcher answer as before; find* never consults the accept seek. The accept seek's lazy DFA sits in the same SingleSeek, and its cache in the same pool entry as the seek's.
• Guards: a seek reads characters. Its answers are the matcher's only for valid UTF-8 and a start on a character boundary, so the _bytes methods check the text (only when the seek decides, in the is_match case, and the &str methods know it), and any other text goes to the matcher. A lazy DFA that gives up answers nothing.
• Automaton: regex-automata's hybrid lazy DFA over the seek (1 MiB cache, earliest search). Its caches sit in a util::pool::Pool, so a thread that searches takes no lock (the pool's owner fast path). The seek reads ASCII look-arounds only, so the DFA never quits. The automaton is shared by the clones of a Regex.
• Validation: tests/single_regex_reject.rs compares every standard answer with *_with(SearchOptions::new()), which runs the matcher without this path, for each pattern built both with the option on and with dfa(false), over 50 hand-written patterns (anchors and multi-line anchors, folds, non-ASCII classes, look-arounds, back references, atomic groups, absent operators, \K, \G, $ at the end of a pattern, (x+x+)+y|.*), the production and tokenizer catalogs, and random UTF-8 and byte subjects. The pathological pattern on thirty xs matches everywhere, so it has no seek, and both builds agree with the matcher and with each other, errors included. A pattern with an unbounded repetition, searched with a retry limit that stops the matcher, checks that the seek answers the matcher's result without the limit. auto_possessive_repeats_agree_with_the_matcher runs the repeats the compiler makes possessive, and user-written atomic groups beside them, on explicit and random subjects; a randomized run over 12,000 generated patterns of such repeats (not committed) agreed on 2.1 million answers, and mutating the walk to take every atomic group for an automatic one fails the differential tests. Unit tests pin the eager build, the option, the exactness of the catalog validators' seeks and of an unbounded pattern's seek, the answers of an exact seek under a tiny retry limit, and the guards. The scanner's suites and the compat differential are unchanged. For the accept seek, unit tests in src/dfa_prefilter/accept.rs pin the django validators' accept seeks and triggers, the folded looks, and the constructs that leave a pattern without one, and compare every answer of the accept seek with the matcher (dfa(false), no retry limit) from every start, over 27 patterns with an accept seek (both django validators with and without their flags, folded looks, nullable neighbors, tune_next repetitions, Unicode classes, anchors, \K, a case-sensitive trie) and 5 without, and some 700 subjects: host names and URLs with ß, ẞ, ſ, ff, st and the strings they fold to, hyphens at label ends, labels of 60 to 64 characters, and random ones; mutating any rule of the walk or of the triggers fails it. tests/single_regex_reject.rs adds such patterns and host subjects, and with the ffi feature compares the standard is_match of the catalog patterns with C on the catalog inputs and the host subjects (catalog_is_match_agrees_with_c). With prefilter-self-check, every answer of an accept seek runs the matcher too and panics where the matcher completes with another result.
• Impact (callgrind instructions of the timed loop, net of the empty loop; 200 iterations unless noted; baseline main at 3b38e91, the commit before this change; the harness compiles each case once inside the measured window, so every row includes one automaton build):

The captures controls of this table did not consult the seek when it was measured: most of their difference is the one automaton build inside the measured window (about 280,000 instructions for jinja_string_token); what remains per search is under 1%, code layout around the standard methods. With dfa(false) the compile is the baseline's (+0.04% for uuid_v4). The capture gate below makes the captures methods consult the seek, with its own measurements.

• Search gate (src/api.rs, SeekGate): the capture and find* methods take only the seek's rejection (Some(false)), and a rejection returns None under every limit, as the matcher's answer does. The find* methods consulted the seek on every call until the gate covered them: on a lexer-style loop of find_bytes_at over markup, where nearly every search finds a match, the seek's scan to the next match came on top of the matcher's own, and the loop took 49.4 ms against 28.8 ms for find_iter_bytes on the same 9.2 MB (318 pages of HTML, one thread); with the gate it takes 31.6 ms. A rejection saves the matcher's attempts on the text; a consultation costs about 300 instructions (a seek search from the start). The gate keeps an exponentially weighted rate of its consultations' rejections (each new answer weighs 1/8) and consults while it is open. It starts open, closes below 250 per mille, and while closed consults one search in 32 on average as a probe, opening again at 375 per mille. The break-even of 375 uses a rejection saving of 800 instructions, the low end of the estimates from the two production cases that reject (jinja_float_token, about 800; fluent_bit_nginx, about 5,000). The gate's state is relaxed atomics in the regex's shared state, so clones and threads share it as they share the seek's cache pool; a lost update costs time at most. The gate writes that state only when it changes, since threads that keep storing the same value still take the cache line from each other, and a steady rejection rate reaches a fixed point (0 or 993). The closed gate's probes are independent draws from a per-thread xorshift generator rather than a shared counter: counting every passed search in one atomic made every search write it, and a thread-local counter would alias between regexes a thread alternates between. Iterators and the *_with methods do not consult it.
• Observability: no result changes, since the gate only chooses which searches run the seek. capture_gate_never_changes_a_capture_result forces the gate on, off and adaptive over the capture methods and find_at at every character boundary, against captures_*_with and find_at_with; capture_gate_follows_the_rejection_rate pins the opening and closing and the probes; capture_gate_is_shared_and_thread_safe runs clones on four threads.
• Bounds: one SeekGate (a rate and a flag) per regex and one u32 generator state per thread, no allocation.
• Impact (callgrind instructions per batch, production catalog, steady lane, 20 batches; the tokenizer row 5 batches; the anchored column is the start-anchored path below, without the capture gate):

Over the anchored path, the gate's remaining cost comes from the probes and the first consultations: the lazy DFA builds the states of each text it reads for the first time, which a longer steady run pays only once. Probes every 64 searches instead of 32 gave semver_version_parse 152,102 and jinja_float_token 62,461 (less of the gain), so the interval stays 32.

• Impact after ADR-017 (callgrind instructions per batch of the steady lane, measure2.sh; baseline main at 17f6412, the commit before the change; the benchmark's own validation compares each output with the oracle): ipv6_validation 57,053 to 6,485 (-88.6%), django_email_local_part 85,062 to 23,006 (-72.9%), uuid_v4 5,330 to 5,094 (-4.4%; a control whose accepted matches no longer read the process-wide limits, the likely cause, not profiled), django_url_regex 28,504,955 to 28,502,925 (-0.01%), semver_version_parse 155,656 unchanged.
• Impact of automatic possessification (measure2.sh, steady lane, per batch; the seek of a case changes only where its pattern has such a repeat that is otherwise exact): no catalog seek changes exactness, so the rows are unchanged within layout noise: django_email_local_part 23,002 to 23,001, ipv6_validation 6,520 to 6,494, uuid_v4 5,132 to 5,116, uuid_shape 10,141 to 10,125, ipv4_validation 4,722 to 4,718, django_url_regex 28,502,987 to 28,503,000, django_email_domain 2,279,626 to 2,279,630 (baseline origin/main at 2a692ca). The validators and django_email_local_part were exact already; django_email_domain and django_url_regex stay inexact (negative look-arounds, Unicode classes), as do the other catalog patterns with such repeats (fluent_bit_*, through \S; jinja_float_token, through \G).
• Impact of the accept seek (callgrind instructions per batch of the steady lane, measure2.sh; baseline main at 2a692ca, the commit before the change; the benchmark's own validation compares each output with the oracle): django_email_domain 2,279,631 to 99,112 (-95.7%), django_url_regex 28,502,947 to 690,909 (-97.6%); controls with exact seeks and no accept seek django_email_local_part 23,000 to 23,222 (+1.0%), ipv6_validation 6,520 to 6,563 (+0.7%), uuid_v4 5,110 to 5,172 (+1.2%; the baseline itself measured 4,964 to 5,110 across builds), and semver_version_parse (captures) 154,930 to 155,227 (+0.2%). Compile (measure.sh … compile 20, a hundred compilations): django_url 3,187,086,762 to 3,817,132,242 (+19.8%), django_email_domain 2,940,137,898 to 3,493,044,350 (+18.8%), mostly the accept seek's NFA (some 2,300 states, 72 and 77 KB); patterns without fold strings pay the scan of the tree only (uuid_v4 +0.4%, fluent_bit_apache +1.3%, semver_version_parse +1.7%, within the 1 to 3% the baseline varies between builds). The accept seek's cache held 86 and 202 KB after the two cases' inputs.
• Bounds: per regex one lazy DFA over at most MAX_NFA_STATES NFA states, and for a pattern with fold strings one more over at most a quarter of that by estimate, each with a cache of at most 1 MiB per thread that searches with it, built with the regex. Compile time is the cost that matters: the rows above, and the option lets a pattern that is compiled once and searched rarely pay none of it.

Start-anchored search (src/regexec.rs)

A pattern that begins with \A or \G can match only at the search start (ANCR_BEGIN_BUF, ANCR_BEGIN_POSITION). The general forward search still ran its loop, its start setup and its optimizer windows, to make the one attempt that remains.

• Trigger: a non-longest forward search from start < end of a pattern whose anchor flags include ANCR_BEGIN_BUF or ANCR_BEGIN_POSITION, with start before the search range, no RegSet start filter, no callouts and no bypassed map search. The \A case with start != 0 returns no match before the attempt, as it did before.
• Execution: anchored_start_search, called from the anchor block of onig_search_inner_core_impl. It applies the threshold check, then the optimizer's answer on start, which C's forward search gives first: OptimizeType::None admits it; a map with no distance and no sub-anchor tests the byte at start; any other optimizer runs forward_search over [start, start + 1) with the bound the general loop uses. A rejection returns no match with no attempt, so Ferroni never makes more attempts than C. An admitted start is attempted once with match_at, and the search's retry budget is checked after the attempt as the loop checks it.
• Observability: the general loop's attempts at positions an anchor excludes are not made, so counts of retries and limit errors can differ from the general path. ADR-017 allows this: C makes the same single attempt (its anchor sets the range to start + 1), so Ferroni attempts no position C would not, and where C stops at a limit Ferroni returns C's result or C's error. Results are those of the general path and of C: anchored_start_search_matches_the_general_path compares the path with the test toggle over 22 patterns, 14 subjects (multibyte, newline, malformed UTF-8), every start and range, four options, and the bounds-only path; anchored_start_search_matches_c compares onig_search with C over the valid subjects, every group, with NONE and FIND_NOT_EMPTY. FIND_LONGEST keeps the general path: on \Aab in ab from 0 to 2 that path returns a match where C returns none, a difference that is not from this change (the general path is unchanged) and is not yet explained.
• Bounds: no allocation and no compiled data; one comparison of the anchor flags on every search.
• Impact: see the table in the capture gate bullet above (the anchored column). The largest gains are on the captures patterns that start with ^ or \A and reject early (fluent_bit_apache, fluent_bit_nginx, the jinja tokens); uuid_v4 and python_markdown_smart_strong_em_re are within half a percent. The tokenizer corpus has no anchored pattern and is unchanged.

Direct anchored capture search (src/regexec.rs, src/api.rs)

The start-anchored search above still reached its one attempt through the forward wrappers (search_in_range, search_in_range_inner, the two-pass capture fill and the core loop), which for such a search do nothing else. A standard capture method on a start-anchored pattern now makes that attempt directly, and the captures of jinja, semver and fluent-bit patterns, which reject or match at their start, pay for the wrappers no more.

• Trigger: captures, captures_at, captures_bytes or captures_bytes_at, on a pattern whose anchor flags include ANCR_BEGIN_POSITION, or ANCR_BEGIN_BUF with a start of 0, searched forward from start < text.len(). The regex must have no AC automaton and no pure literal, and neither its options nor the search's (NONE) include FIND_LONGEST or the validity check. The anchored-start path must apply (no callouts, no bypassed map search; anchored_start_applies). Every other search, and every iterator and *_with method, runs onig_search as before.
• Execution: onig_search_captures calls anchored_captures_search, which takes the thread's cached MatchArg with the region, empties history_root and makes the attempt of anchored_start_run (the body of anchored_start_search, split out so both paths share it). The attempt records the captures of a region with groups, as the two-pass fill's first attempt does, and the fill has no second pass to make. The core loop's resize and clear is deferred: a match rewrites every register 0..=num_mem in populate_region_for_match, so the region is cleared only where no match is found (no match, or a limit error), and the registers are then left as the core loop leaves them.
• Observability: results, registers, the empty history and the limit errors are the general path's. anchored_captures_match_the_general_path compares the direct path with onig_search (anchored path on and off) for 22 anchored patterns, 14 subjects and every start, over a region holding stale registers; anchored_captures_match_the_general_path_through_the_api compares the public methods with captures_*_with for seven patterns, two of them without groups, on nine subjects, sharing the thread's cached region; anchored_captures_at_a_later_begin_buf_make_no_attempt pins that \A at a later start makes no attempt, so a search retry limit does not report one; anchored_captures_clear_the_region_when_nothing_matches pins the clear; anchored_captures_of_a_find_longest_pattern_match_the_general_path covers FIND_LONGEST patterns. Mutation checks: dropping the start-0 check fails the retry-limit test; dropping the no-match clear and dropping the history reset each fail the match test. The FIND_LONGEST, pure-literal, AC and start < text.len() guards mirror the general path's early returns; no test distinguishes them, since they are result-equivalent for the patterns tried (an AC automaton is never built for an anchored pattern, detect_ac_eligible requires no anchor).
• Bounds: no allocation and no compiled data. One predicate test per standard capture call, and no extra cache state.
• Impact: callgrind instructions per batch, production catalog, steady lane, 20 batches, against origin/main built from the same tree; the tokenizer row 5 batches. The targets are the captures patterns above; the other rows are controls.

The eight target cases together go from 325,260 to 303,449 instructions (-6.7%). The direct path is the single-search captures path. The iterator (all_captures), replace, grapheme and is_match rows do not reach it, and their changes of -1.1% to +0.4% are layout noise. The python_markdown_* rows are \G captures that reach it. Per call the saving is the wrappers' frames and the cleared registers that a match overwrites; a captures call still pays the seek gate, the MatchArg and region handoffs, and the attempt, which dominates these patterns.

Per-search limits on the cached MatchArg (src/api.rs, src/regexec.rs)

The *_with methods run their searches on the thread-cached MatchArg that the standard methods use, under the limits of their SearchOptions. Before, each search built a fresh MatchArg and an OnigMatchParam. Options that set no limit take the standard path, and find_with and find_iter_with use the bounds-only path where the standard method does. Only a limit error that the standard methods discard is reported.

• Trigger: any *_with search. SearchOptions::new() (no per-search limit) runs the standard code path.
• Execution: SearchLimits carries the four limits. take_cached_msa and MatchArg::reset_with_limits write all four on every reset, so the limits of one search never reach a later search that takes the cache. The iterators keep the limits and apply them to each step.
• Observability: the bounds-only path and the region path report the same limit errors. A limit on the match stack keeps the capture bookkeeping on untracked runs, and the second pass of a region search consumes no retry budget. bounds_and_region_paths_report_the_same_limit_errors compares the two paths under several limits.
• Bounds: no new allocation or compiled data; one SearchLimits value per search and iterator.
• Impact (callgrind instructions of the timed loop, 200 iterations, net of the empty loop; _with runs use SearchOptions::new()): uuid_v4 is_match 20.35M → 15.55M; jinja_string_token captures_at 9.96M → 6.11M; django_email_local_part is_match 105.5M → 80.2M; literal_first find 1.71M → 1.03M. Against the standard method in the same build, _with is +2.7%, +6.1%, +2.7% and −0.0% respectively. The standard methods move by +0.2%, +0.6%, +0.2% and −5.3%: find no longer resets its MatchArg twice.

Iteration restart without the optimizer's scan (src/regexec.rs)

Each search of an iteration restarts from the previous match end. Two per-search costs of that restart are removed where no result can change.

• Trigger: a bounds-only search (find, find_iter) takes the core search directly, without the region-path wrappers, unless the two-pass capture fill applies. An unbounded search (dist_max infinite) whose map optimizer has its byte at the attempt start set skips the optimizer's check of that start, since the check would return that start at once.
• Execution: the core search calls map_candidate_at before forward_search. The check holds only with a map optimizer, no minimum distance and no sub-anchor, and the byte at the start inside the map.
• Observability: the skipped check returns the start with no bytes read, so the test-only forward-search byte count is unchanged. The attempts that follow are the same. find_iter_map_candidates_at_and_after_the_start checks the iteration results on candidate, non-candidate and multibyte starts, empty matches, look-behind and \G.
• Bounds: no allocation and no compiled data.
• Impact (callgrind instructions of the timed loop, net of the empty loop, std mode, baseline regex-integration against this branch): tiktoken (tokenizer catalog, 20 iterations, both cases) 490.5M → 424.9M, −13.4%. mastodon_hashtag all-captures 58.07M → 57.20M, −1.5%; wordpress_shortcode all-captures 33.20M → 32.56M, −1.9%. The single-search controls rise by 0.02% to 0.08% (uuid_v4 +0.06%, uuid_shape +0.06%, ipv4_validation +0.05%, fluent_bit_apache +0.08%, literal_first +0.08%); the extra check on each search costs a few instructions.

Iterator-held search state (src/api.rs, src/regexec.rs)

An iterator runs one search per match. Its searches had rebuilt the same state each time: a captures iterator took the thread's cached MatchArg, reset it, and put it back after every match, and both iterators read the program through the AssertUnwindSafe wrapper on every search.

• Trigger: every step of Regex::find_iter and find_iter_bytes (bounds-only), captures_iter and captures_iter_bytes, and their _with forms.
• Execution: CaptureMatches holds one MatchArg for its life. Its region sits in the MatchArg between searches, and a yielded Captures takes it, as before. Each search calls MatchArg::reset_for_iteration, the reset of reset_with_limits without the region, and search_in_range_inner, the call search_in_range makes. The MatchArg returns to the thread cache when the iterator drops. Both iterators keep a reference to the program, and onig_search_bounds is inlined into the bounds step.
• Also: the second pass of a captured search and the empty-match rule of MatchCursor are unchanged. The bounds path skips the pure_literal_first call for patterns that are not pure literals; the function answers None for them. The unbounded map search replaces the or_else closures of its start filter with the same sequence of if tests.
• Observability: none. Limits are still read for each search, from the process-wide settings when the iterator has no limits of its own, so a limit set between two matches applies to the next search (find_iter_reads_the_process_wide_limits_for_each_search and captures_iter_reads_the_process_wide_limits_for_each_search; each fails if the limits are read once at construction). Retry and stack budgets, captures and errors are unchanged, and the full unit suite compares the iterators with repeated searches as before.
• Bounds: one MatchArg per live captures iterator, the same allocation the thread cache holds for a search. Its stack is released as before when it grows past MAX_CACHED_STACK_ENTRIES.
• Impact (callgrind instructions per batch of the standard API, ferroni build against the origin/main build, same harness): tiktoken_cl100k_base 2,182,743 → 2,120,280 (−2.9%); tiktoken_o200k_base 2,072,398 → 2,014,463 (−2.8%); mastodon_hashtag_regex_step 71,585 → 70,375 (−1.7%); rails_underscore_regex_step 57,038 → 56,708 (−0.6%); symfony_grapheme_chunks_1 22,318 → 21,237 (−4.8%) and _2 5,752 → 5,495 (−4.5%); wordpress_shortcode_captures 44,317 → 43,383 (−2.1%). The single-search controls move between −0.7% (uuid_v4) and +0.4%; the largest rise, python_markdown_smart_strong_em_re at +0.41%, is not explained yet and stays under the +1% limit.
• Not done: a specialized bounds path for the unbounded map case was measured and was 0.9% slower, so it was not kept. Most of the remaining per-search cost is the attempt machinery (ForwardScan, the start filter and the entry of onig_search_inner_core_impl), not the iteration state.

Fixed costs of a search (src/regexec.rs, src/regenc.rs)

Three per-search costs that every entry point pays are removed where no result can change.

• Trigger: a captures search (captures_at and its relatives) of a pattern whose optimizer map is not the only start filter, and any search that steps over an ASCII byte in a UTF-8 subject.
• Capture-fill precheck: the two-pass capture fill calls capture_map_search only where its first checks can pass: map optimizer, no anchor or sub-anchor, distance 0, no ac_alt, no capture tracking and no any-char run. The other patterns go straight to the core loop, as the call returned at once for them.
• Cached MatchArg in a Cell: the thread's cached MatchArg is taken and put back whole, never borrowed, so the per-search take and store lose the borrow-flag checks of a RefCell.
• UTF-8 by address: onigenc_is_ascii_compatible_encoding recognizes the UTF-8 static by its address before it calls the virtual flag. The UTF-8 flag includes the ASCII-compatible bit, so the answer is the same; other encodings still ask their flag. The check runs for every ASCII byte the matcher steps over (enclen), which is why match-heavy cases gain most.
• Observability: none. Attempts, retry counts, limits and captures are unchanged; the full test suite and the prefilter self-check pass.
• Bounds: no allocation and no compiled data.
• Impact (callgrind instructions, std mode, 200 iterations, net of the empty loop; baseline iter-restart against this branch): uuid_v4 14.86M → 13.33M (−10.3%); uuid_shape 30.72M → 28.89M (−6.0%); jinja_string_token 5.79M → 5.52M (−4.6%); jinja_integer_token 12.29M → 11.73M (−4.6%); fluent_bit_apache 20.84M → 20.46M (−1.8%); fluent_bit_nginx 36.56M → 35.78M (−2.1%); ipv4_validation 26.71M → 26.08M (−2.4%); semver_hyphen_range_captures 35.68M → 35.35M (−0.9%). _with runs: uuid_v4 15.27M → 13.73M (−10.0%), jinja_string_token 6.14M → 5.87M (−4.3%). The tokenizer corpus (all_matches, 20 iterations) is unchanged within 0.02%, and the literal control moves by +0.14%.

Compile-path passes (src/backtrack_lint.rs, src/regcomp.rs, src/leading_run.rs)

• Shared finder: a literal prefix whose bytes equal the exact-string needle clones that finder instead of building a second one (GET).
• Backtracking check: the first-byte sets of classes and types come from their bitsets a word at a time, and types from the per-thread code_ctype_bitset cache; chains are walked without collecting them.
• Optimizer maps: add_bitset_opt_map sums the position values from the table, with byte 0 corrected for the encoding as in alt_merge_opt_map, and sets the map bytes eight at a time from a 256-entry table.
• Allocations: string reduction appends merged bytes straight from the node and reserves its output; the empty-repeat check reuses one chain buffer for the cells of a list.
• Output: unchanged. A unit test compares the map operation with the per-byte rule, a golden test pins the findings for 34 class and type patterns, and a differential run of the check over 12,000 generated patterns gave identical warnings.
• Impact (callgrind instructions, compile mode, 200 compiles; django_email_domain 20): the Apache log pattern −21%, semver_version_parse −13%, ipv6_validation −3%, django_email_domain −1%, GET −2%. The Apache log pattern in search mode moved by 0.3%.
• Bounds: no memory beyond a 2 KiB constant table; no change to what is compiled.

Empty matches and first-attempt captures (src/api.rs, src/regexec.rs, src/regcomp.rs)

• Trigger: (a) a search with a region that records captures in two passes (can_use_two_pass_capture_fill: groups, no FIND_LONGEST, no time limit, no callouts); the attempt that records captures is now the first attempt the search makes, not only the attempt at its start (see Untracked push captures under Scanner fast paths from the 2026-09 profiling pass). (b) find_iter and captures_iter, after an empty match, for programs without \G, \K or callouts (RegexType::skip_repeated_empty_search, set when compilation ends).
• Execution: the first attempt of a two-pass search records its captures (MatchArg::capture_position holds FIRST_ATTEMPT until that attempt runs). A match there needs no second pass; a match at a later attempt still runs again to record its captures. After an empty match at p, MatchCursor::accept moves the cursor one character past p when the match is yielded, so the search from p, which could only find that empty match again, does not run. An empty match at the end of the text ends the iteration. CaptureMatches takes its next region from the thread cache, which the yielded Captures returns when it is dropped.
• Observability: the iterators yield the same matches and captures. The work saved is the repeated search after each empty match and the second pass of a match the first attempt already recorded; the retry budget of a search can only shrink (ADR-017). Recording captures changes no match and no backtrack count: a failure counts once in either mode, and needs_capture_tracking already keeps tracking on wherever a capture can decide a match. Patterns with \G, \K or callouts keep the repeated search.
• Validation: unit tests compare find_iter and captures_iter, with and without the step, against the repeated search over empty-match patterns on ASCII, multibyte and invalid UTF-8 text; a test counts one VM attempt per empty match; captures are checked for matches whose first attempt fails and for matches found by the map search. tests/iteration_empty_matches.rs (ffi) drives C's onig_search with the same rule over every string of up to four characters.
• Impact (callgrind instructions per steady batch, measure2.sh, before to after): mastodon_hashtag_regex_step 101,390 to 75,796 (−25%), rails_underscore_regex_step 69,456 to 54,011 (−22%), symfony_grapheme_chunks_1 31,041 to 26,708 (−14%), symfony_grapheme_chunks_2 8,058 to 7,114 (−12%), wordpress_shortcode_captures 48,446 to 44,950 (−7%). Controls: semver_hyphen_range_captures +0.15%, jinja_string_token +0.23%, ipv6_validation −0.01%, and the tokenizer corpus (tiktoken_cl100k_base, tiktoken_o200k_base, 5 batches) unchanged to 0.01%. These are instruction counts, not wall-clock time.
• Bounds: one flag per compiled program and one Option<usize> value in MatchArg (the two-pass state it already had); no allocation beyond the thread's cached region, no dependency, no unsafe code. The core search loop keeps its code: an extra comparison in its per-search setup moved the tokenizer corpus by about 0.5%, so the first attempt is claimed where the attempt is dispatched, which costs nothing for searches without a region.

Possessive stars across optional groups, alternations and end anchors (src/possessify.rs, src/regcomp.rs, src/regexec.rs)

C's tune_next makes a greedy X* or X+ possessive when the node right after it starts with a character X cannot match. It reads that one node only, so the star in [^\s:@/]+(?::[^\s:@/]*)?@ (django_url_regex), whose next node is optional, keeps every choice: on a 64 KB host that is not followed by @, it gives the run back one character at a time and tries the rest at each position. PCRE2's automatic possessification looks further; this pass does too.

• Trigger: a greedy * or + over one class, the word type or one ASCII byte that compiles to a plain star instruction (no peek-next byte), outside look-arounds, atomic groups and conditions, in an ASCII-compatible encoding, in a pattern without back references, subroutine calls or callouts. Its follower, what comes after it up to the end of the pattern through group ends, branch ends and the next pass of an enclosing repeat, must fail at every position whose character the body matches. The walk passes elements that can match only the empty string there: optional groups and repeats whose start the body excludes, alternations, look-aheads, word and line boundaries, \K. It stops with a proof at a character, class or string the body excludes (C's is_exclusive), at an alternation whose branches all do, at \z, and at $ or \Z when the body cannot match a newline. A look-behind, back reference, call, condition, literal trie, gimmick or the end of the pattern stops it without one, and so do 256 visited nodes.
• Why results are unchanged: the star gives back to a position p only after a further iteration matched there, so the character at p is one the body matches, and p lies before the end of the subject, where \z fails and $ and \Z hold only at a newline. The follower cannot match from such a p, so the only run that can lead to a match is the longest, which the greedy star tries first. FIND_LONGEST and FIND_NOT_EMPTY only search on after a match, and the given-back positions hold none; NOTEOL and MATCH_WHOLE_STRING only make the follower fail more often.
• Execution: the pass runs after tune_tree and marks the repeat (QuantNode::possessive_star); the tree keeps its shape, so the optimizer, the seek (its exactness included) and the other tree analyses read what they read before. The star instruction is followed by PopStarChoices, which pops the entries that resume at it, the choices the star just pushed. Unlike an atomic group's mark and cut, which leave the mark and the voided entries on the stack, it leaves nothing: the possessive star never needs more stack than its greedy form. The bytecode walks of first_bytes read it as an instruction that consumes nothing, which it is where they reach it: after a star that consumed nothing.
• Observability: under ADR-017. The backtracks left out are not counted, so a retry or time limit that stops C (and the greedy program) can let Ferroni finish, with the result C gives without the limit; where C finishes, the results are identical.
• Not applied: lazy and bounded repeats (the analysis found that an atomic rewrite of a bounded repeat over a case-fold alternation changes results), bodies with captures or of more than one character, and the end of the pattern, where the follower accepts and nothing is given back anyway.
• Validation: src/possessify/tests.rs pins which stars qualify, the production patterns included, and compares the possessive program with the greedy one (a test toggle) and with C: 700 generated patterns of the covered shapes plus absent-operator and \K cases, under IGNORECASE, SINGLELINE, MULTILINE, FIND_LONGEST and FIND_NOT_EMPTY and the search options NOTEOL and MATCH_WHOLE_STRING, on subjects with multibyte, malformed and newline characters, from several starts, captures included (C only on valid UTF-8, where malformed input is outside this change). Hand-written cases where a shorter run would match, Perl's $, ADR-017's three cases against C under retry limits, and the stack of a repeated group complete it. Mutations of the newline rule, the repeated-body rule and the optional-repeat rule each fail these tests.
• Impact (callgrind instructions per batch of the steady lane, measure2.sh, 20 batches, the tokenizer cases 5; baseline main at 2a692ca; the benchmark's own validation compares each output with the oracle):

django_url_regex gains three possessive stars and fluent_bit_apache one ( + before \S* and a quote); the other cases have none and move by code layout. PopStarChoices runs out of line: inline in the matcher's loop, it cost the controls 0.2% to 0.7%.

• Bounds: one walk of the tuned tree per compilation, at most 256 follower nodes per candidate star, and one instruction per possessive star. Compiling django_url_regex (measure.sh compile mode, 20 compiles) takes 3,187,088,513 instructions before and 3,179,623,508 after (-0.2%).

Possessive one-character repeats without stack growth (src/regcomp.rs, src/leading_run.rs, src/regexec.rs)

C compiles a stop-backtrack bag whose body is a greedy * or + over one strict real node (STRICT_REAL_REPEAT: set by tune_next for automatic possessification and by tune_tree for (?>a*), a*+ and a++) to PUSH, body, POP, JUMP. Every pass pops the choice it pushed, so the repeat holds one entry while it runs and leaves none. Ferroni compiled every stop-backtrack bag to MARK and CUT_TO_MARK, which leave the mark and the voided choices on the stack. In a repeated group they add up: (?:[a-z]+;)*z on 1,000 repetitions of a; needed 1,004 entries, where C needs at most 320, so a match stack limit stopped Ferroni where C completes (ADR-017, rule 3).

• C's structure (ADR-001): compile_bag_node and compile_length_bag_node take C's branch, and a body without a star instruction (a string, \d, \S, .) runs C's loop. The flag is read from the bag's shape (strict_real_repeat), which is what both C sites test: every node status bit is in use, and ND_ST_STRICT_REAL_REPEAT keeps marking only the automatic bags, which the seek writes as plain repetitions (dfa_prefilter::automatic_possessive). A literal trie (ND_ST_LITERAL_ALT) is an alternation in C and not a strict real node, and neither is an empty string, as in C: (?:)++ as a PUSH/POP loop would never advance.
• Rust-only part: a body with a star instruction (a class, one ASCII byte or \w; has_star_instruction) runs as that instruction followed by PopStarChoices, as the stars of the pass above do, instead of one PUSH/POP round per character. Over valid UTF-8 the star pushes one entry per run and PopStarChoices pops it before the next instruction; C's loop holds one as well. Over malformed UTF-8, where a multibyte run cannot step back by character heads, the star pushes one entry per character until PopStarChoices pops them, as it did between the mark and the cut. The peek-next forms are not used here: they only save pushes before the follower's byte, which the run never contains.
• Plans that read the bytecode: leading_run takes a star followed by PopStarChoices as an atomic run for its literal plan, as it took a run between a mark and its cut. atomic_ascii_class_prefix recognizes the class, CClassStar, PopStarChoices and literal sequence instead of the mark-and-cut one, and still leaves out a NUL literal, which C's tune_next never gives a star as its peek-next byte.
• Observability: results are unchanged, since the repeat is atomic in both forms. The repeat pushes and pops fewer entries; under ADR-017, a stack limit that stopped Ferroni where C completes no longer does. C checks the stack limit only when its stack grows past 320 entries (160 to start with, then one unchecked doubling), so searches that fit there complete in C under any limit; that floor is not part of this change.
• Validation: tests/stack_limit_parity.rs (feature ffi) finds, for repeated groups around automatic and source-written possessive repeats with and without star instructions, captures included, the least match stack limit from 320 at which C completes on 1, 10 and 1,000 repetitions, and requires Ferroni's result at that limit, one above and twice it to equal C's. Without the change it fails at the first such case. The existing differential tests of the possessive stars, the literal tries and the class prefix filter pass, the filter's against the program with the filter turned off. The grammar census counts 50 more guarded pushes: the PUSH of C's loop gets a byte-set guard.
• Impact (Criterion steady lane of production_regex_bench, Ferroni engine, wall clock on an Apple Silicon Mac, 1 s warm-up and 3 s measurement, two rounds alternating baseline and change; baseline main at a243f18; a local diagnostic, not a publication run): the bytecode changes for five of the 27 catalog cases, jinja_float_token (-3.1%, -4.7%), django_url_regex (+0.0%, -0.2%), fluent_bit_apache (-1.3%, -1.5%), fluent_bit_nginx (-3.0%, -2.3%) and wordpress_shortcode_captures (-1.9%, -4.7%). Cases with unchanged bytecode moved by -3.2% to +3.6% in the same runs (uuid_v4 -0.6% and +0.1%, ipv6_validation +1.3% and +0.5%), so the change shows no regression and no speed-up beyond that noise. Its aim is the stack bound, not speed.
• Bounds: no new instruction or analysis; one check of the bag's shape per stop-backtrack bag at compile time.

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. ADR-017 states the general rule: Ferroni never does more work than C and never returns a result other than C's or the one C would return without the limit; the cases below predate it. A search prefilter that proves there is no match (a required byte or literal missing from the subject, or from the rest of it) 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).
• A retry limit in match of only a few backtracks shows two more differences, which are accepted rather than gated. The start filters leave out attempts C makes: a RegSet fallback entry's start map, and onig_search's under an unbounded optimizer, step over a position whose byte cannot start a match without counting the backtracks C's failed attempt takes there. A limit at or below that count stops C with ONIGERR_RETRY_LIMIT_IN_MATCH_OVER where Ferroni goes on to its result: at limits 1 and 2, \s*(\[) in a set with x on ab [, and ([$A-Z_a-z][$\w]*)\s*(\() on auto summarize(const searched from 4, match in Ferroni and stop in C; from a limit of 3 both agree. The reverse shows at a limit of 1, where every failed attempt stops the search: the table scan can attempt an entry at a position C's optimizer excludes, so ^ab in a set with x on cab\nab x stops in Ferroni and matches in C. Matching C at such limits would take a bound on the backtracks of every left-out attempt and a check of it in every search, for limits far below any practical setting; the default is 10,000,000.
• The Scanner's memo and per-regex cache route never change a result, limit errors included: a fallback entry uses the positions C's regset_search_body_position_lead lets its optimizer admit (forward_search), less those its start filter excludes (see above), with failed-run skips only where the failed attempt proves later starts cannot match or introduce a limit error, 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. Required literals leave out attempts after the last occurrence in every route alike; only the retry limit in match can tell (see above). The DFA pre-filter decides a search only under the default limits, so a limit of the caller's own sees C's attempts on every route.
• The single-pattern seek of a Regex (see Single-pattern seek for standard searches) has no divergence from the matcher without limits. Under a limit it follows ADR-017: its "no match" answers, and those of its accept seek, are the matcher's under every limit, and the "match" answers of an exact seek or an accept seek, given to is_match only, are the matcher's result without the limit where a retry limit, the stack cap or the time limit would stop the matcher. find and captures run the matcher and report no match there, so under such a limit is_match can report a match that find does not. The seek itself reports no error.
• 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.