Scanner API for Multi-Pattern TextMate Tokenization

Status

Accepted

Context

Ferroni's primary real-world workload is TextMate grammar tokenization, used by syntax highlighters like Shiki and VS Code. TextMate grammars require a multi-pattern scanning interface: given N compiled regexes and a string position, find which regex matches earliest (and among ties, which has priority).

C Oniguruma provides OnigRegSet for multi-pattern matching, but it exposes a low-level C API. The JavaScript ecosystem uses Microsoft's vscode-oniguruma (MIT), which wraps Oniguruma in a higher-level OnigScanner interface tailored to TextMate tokenization. Shiki, VS Code, and other grammar-based tools depend on this specific interface.

To serve as a drop-in replacement for vscode-oniguruma in the Rust/NAPI ecosystem, Ferroni needs an API-compatible scanner layer — not just raw regex compilation and matching.

Decision

Add a Scanner API (src/scanner.rs) that wraps Ferroni's C-ported RegSet internals with a vscode-oniguruma-compatible interface.

API surface

1. Scanner::new(patterns): Compiles a set of regex patterns into a RegSet with pre-computed first-byte dispatch tables and SIMD skip needles. It uses vscode-oniguruma's defaults: Oniguruma syntax and ONIG_OPTION_CAPTURE_GROUP.

2. Scanner::find_next_match(text, start_position): Searches all patterns simultaneously and returns a ScannerMatch containing the winning pattern index and all capture group positions. Supports ScannerFindOptions for anchor control (NOT_BEGIN_STRING, NOT_END_STRING, NOT_BEGIN_POSITION), matching vscode-oniguruma's FindOption flags.

3. ScannerMatch / CaptureIndex: Result types carrying the matched pattern index and byte-offset capture spans. CaptureIndex fields (start, end, length) mirror vscode-oniguruma's output format.

4. ScannerSyntax: Enum selecting the regex syntax variant (Oniguruma, Asis, POSIX Basic/Extended, Java, Perl, Ruby, Python, etc.), matching vscode-oniguruma's Syntax type.

5. ScannerPatternCache and Scanner::with_pattern_cache(patterns, config, cache) (with Scanner::with_backtracking_optimization_and_pattern_cache): opt-in sharing of compiled patterns between scanners, Rust-only (see Pattern cache). Scanner::new and Scanner::with_config keep compiling every pattern.

6. ScannerConfig::prefilter (default true): whether the scanner's searches are decided by the multi-pattern DFA pre-filter of ADR-008, which attempts only the patterns that can match at a position. Both settings find the same match with the same captures; the pre-filter costs construction time and memory per scanner and is a Cargo feature (dfa-prefilter, on by default) as well. Scanner::prefilter_stats reports what it covers. vscode-oniguruma has no such switch; it is Ferroni-only, like the pattern cache.

Layering

  Scanner (public API, vscode-oniguruma-compatible)
    └── RegSet (C-ported internal, ADR-001)
         └── onig_search / onig_match (C-ported VM, ADR-001)

The Scanner does not modify the C-ported control flow. It is an additive layer that:

• Delegates pattern compilation to onig_new() (same as Regex)
• Delegates multi-pattern search to onig_regset_search_fast() (C-ported RegSet)
• Adds result formatting, option translation, and scratch space management

The one change below it is in the RegSet's data: an entry holds its regex as Arc<RegexType> instead of Box<RegexType>, so that sets can share it (see Pattern cache).

Pattern cache

A TextMate grammar creates one scanner per rule context, and the same pattern strings recur across them. In the captured Ferriki sessions (benches/*_scanner/trace.json), the C++ grammar's 96 scanners hold 4,026 patterns, 250 of them distinct; SCSS has 600 in 20 scanners (104 distinct), Java 866 in 27 (115 distinct). Most of the work of constructing every scanner went into compiling patterns that had already been compiled. This is a cold-start cost: the first highlight of a grammar in a process.

ScannerPatternCache maps a pattern's text, compile options, syntax and backtracking optimization choice to its compiled RegexType, which carries everything a scanner keeps per pattern besides its search state (bytecode, optimizer data, the Rust-only plans, backtracking warnings and rewrites). A scanner built with the cache reuses the patterns it holds and compiles and adds the others.

• Explicit, caller-owned, not process-wide. The caller knows when a grammar is loaded and dropped; a process-wide cache would keep every pattern for the life of the process or need an eviction policy of its own. Compilation also reads process-wide settings (onig_set_capture_num_limit, onig_set_parse_depth_limit, onig_set_ast_node_limit, user-defined Unicode properties, callout names) and runs the warning callbacks; a process-wide cache would freeze them for every caller, while a caller's cache is cleared by its owner after changing them. Finally, the cache takes &mut and needs no lock inside Ferroni; callers that build scanners on several threads put it behind a Mutex or keep one per thread. vscode-oniguruma has no such cache, so Scanner::new and Scanner::with_config stay as they were.
• Scope is the caller's choice. The cache is keyed by pattern and compile settings, not by grammar: one cache per grammar shares within that grammar and is freed with it, and one cache for every grammar a highlighter loads also shares between grammars. That matters for related grammars (in the Shiki grammar collection, TypeScript and TSX have 351 of their 362 and 375 regex source strings in common) and for grammars that embed others, such as Vue, Svelte, Astro, Markdown and MDX, whose scanners are built over the embedded grammar's patterns again. Unrelated grammars share little: the captured C++, Java and SCSS sessions have 441 distinct patterns together against 469 counted per session. The wider the scope, the longer its patterns live.
• Lifetime. The cache and the scanners hold strong references; a compiled pattern is freed with the last of them, and so are the pre-filter automata of a pattern list (see below). clear() and dropping the cache never affect built scanners, and the cache never evicts by itself. A construction that fails (a pattern does not compile, or the RegSet refuses the set) leaves the cache as it was.
• What is shared. The compiled regex; the seek approximation of the DFA pre-filter (ADR-008) that was derived with it, in its compact encoding; and the pre-filter automata of every pattern list a scanner was built over. The cache keys the automata by the ids of the list's patterns, every scanner it builds over the same list holds the same handle (AutomataCell), and the first of them to search with the pre-filter builds them; they are read-only once built, while the lazy DFA caches that fill as a scanner searches stay the scanner's own. Every RegSet builds its own entries (region, fallback memo, gates, start filters, first-instruction tests, routing flags) and its own pre-filter state, and every scanner its own per-regex cache entries. Searches take &RegexType; the only interior mutability inside it is two OnceLocks (the required-literal searcher and the folded-alternation automaton), built on first use from the regex's immutable data. A scanner built from the cache therefore returns exactly what one built without it returns. In the captured sessions, 52 of the C++ grammar's 96 scanners repeat another scanner's pattern list (C 10 of 29, Java 4 of 27, PHP 3 of 35, SCSS 1 of 20); ADR-008 has what the sharing saves.
• Threads. RegexType is Send and Sync from its fields alone (no unsafe impl), so Arc<RegexType>, the RegSet, the cache and every scanner are Send and Sync, as a compile-time assertion states. None of them is UnwindSafe, under a Box as under an Arc: RegexType holds an OnigEncoding trait object.
• Search cost. Dereferencing an Arc costs what dereferencing a Box does: one pointer load, with the reference counts skipped at a constant offset. Searches never touch the counts.
• C API. onig_regset_new, onig_regset_add, onig_regset_replace and onig_regset_get_regex keep their signatures and semantics; a Box<RegexType> they receive moves into an Arc (one copy of the 1,096-byte struct). The sharing path is the Rust-only onig_regset_new_shared next to them.

Constructing every scanner of a captured session, release build on an Apple M1 Ultra: instructions per construction (median of five interleaved runs, two run lengths subtracted) and minimum wall-clock. The cached rows start from an empty cache, so they include compiling each distinct pattern once.

With every scanner of the session alive, the peak memory footprint above the loaded fixture falls from 97.9 to 12.4 MiB for C++, from 24.5 to 4.4 MiB for SCSS and from 5.7 to 1.9 MiB for Java; uncached scanners stay within 0.2 MiB of before. Replaying the captured calls through uncached scanners takes the same instructions as before (C++ −0.00%, Java +0.07%, SCSS +0.04%; minimum cycles −0.4%, +0.1%, −0.3%). Through cached scanners it takes 0.04–0.13% more instructions and 2–6% fewer minimum cycles than through uncached ones. scanner_compile_bench reproduces the construction comparison (<name> and <name>_pattern_cache).

Relationship to ADR-005

ADR-005 defines the idiomatic Rust API layer (Regex, RegexBuilder, Match, Captures). The Scanner extends this layer with a domain-specific API for TextMate tokenization. It is not a general-purpose regex API but a purpose-built interface for the grammar tokenization use case.

Rationale

• Drop-in compatibility: Shiki and other tools can switch from vscode-oniguruma (WASM) to Ferroni (native) with minimal API translation.
• Execution: The Scanner runs natively and uses RegSet's first-byte dispatch and skip needle (see ADR-007). Scanner comparisons need complete captured call sequences and their own operation boundaries; general regex measurements do not establish highlighting performance.
• Zero internal disruption: The Scanner is purely additive — no C-ported control flow or function signature is modified; only the RegSet entry's ownership of its regex changed (Arc for Box) to let scanners share compiled patterns. The full 1,695-test C-parity suite passes unchanged.
• Cold start: Sharing compiled patterns takes 80–90% out of constructing a grammar's scanners and leaves the search path as it was. It is an opt-in next to the vscode-oniguruma-shaped constructors, so that those keep their behavior and the caller decides how long compiled patterns live.

Consequences

• src/scanner.rs is a substantial module (~66 KB) with its own test suite.
• The smallvec crate is a dependency for the capture spans of ScannerMatch. They are read through ScannerMatch::captures(); since 2.0 smallvec is not part of the public API.
• The Scanner API is Ferroni-specific — it does not exist in C Oniguruma. This is acceptable because it layers on top of (rather than modifying) the C-ported internals, consistent with ADR-001's parity goal.
• Future Scanner changes should maintain vscode-oniguruma interface compatibility to avoid breaking downstream integrations (Shiki, ferriki).
• Grammar loaders that build many scanners can share compiled patterns, and the pre-filter automata of repeated pattern lists, through a ScannerPatternCache they own; nothing is cached across callers. Anything that would let a search write into a RegexType or into the shared automata must keep that state per RegSet entry or per scanner instead, since both may be shared.
• The default capture behavior matches vscode-oniguruma: unnamed groups remain captures when a pattern also contains named groups, and numbered backreferences remain available. Callers can select different behavior with an explicit ScannerConfig.