C Engine Internals

C Engine Internals

The C extension is the gem's selling point: a single-pass, multi-pattern engine that scans a string once for all 89 patterns and stays O(N) in the input length. This page is the guided tour. The full research narrative — every prototype, every dead end, the benchmark data — lives in the research log; this page summarizes and points there.

The pipeline: NFA → bytecode → lazy DFA

Each pattern travels the same road at load time and on first use:

1. Regex → Thompson NFA. At mm_init() (load time), every built-in pattern is compiled from a POSIX ERE into a Thompson NFA. Boundary-wrapped patterns are first expanded with their word-boundary group (^|[^0-9A-Za-z])(…)([^0-9A-Za-z]|$) so the boundary is part of the automaton, not a post-check.
2. NFA → bytecode. The NFA is lowered to a compact bytecode VM program (v11 introduced this; the interpreter is a tight switch over char-class, split, jump, and match ops). This replaced pointer-chasing NFA simulation and was a major constant-factor win.
3. Bytecode → lazy DFA. On first use, each pattern's DFA states are built lazily and cached (interned) as the scan discovers them. This is the v18 breakthrough: instead of stepping every NFA thread per byte, the engine memoizes (state, byte) → next state transitions. Cold first byte builds a state; every subsequent occurrence is a table lookup. v18.1 lowered anchors so all patterns run on the DFA path.

How a single scan runs

DataRedactor.redact(text) / scan(text):

1. Hand the input to the v19 engine, which scans the buffer once and emits (pattern_id, start, length) events for every enabled pattern.
2. Two selective-merge passes collapse the most common pattern classes into shared scans — a pure-digit group and an IBAN union — so dozens of digit/IBAN patterns don't each re-walk the buffer. This is the v19 addition on top of v18.1.
3. mm_resolve reduces overlapping events to a non-overlapping set under longest-match-wins: keep the longest span at each position; the lower pattern index breaks equal-length ties. (This biases toward redacting more when uncertain — a 40-char secret is redacted whole rather than leaking the bytes past a shorter prefix match.)
4. redact rewrites the surviving spans to placeholders in one buffer build (preserving the boundary chars of boundary-wrapped matches); scan returns the events with byte offsets into the original string.

Custom patterns (add_pattern) run on the glibc regexec path after the built-in scan — required for correct UTF-8 diacritic matching. See Custom Patterns & Name Patterns.

The v19 story (the short version)

The engine got here through ~19 numbered prototypes. The turning points:

Prototype	Idea	Result
v1–v3	glibc regexec, then Onigmo, then Onigmo per pattern	baseline; per-pattern regex is slow at 88 patterns
v5	Aho-Corasick + Onigmo + Boyer-Moore infix pre-filter	fast, but pulls in dependencies
v11	Thompson bytecode VM	removes pointer-chasing; big constant-factor win
v14	literal + first-byte pre-filter	skip patterns that can't match here
v18	per-pattern lazy DFA transition cache	★ breakthrough — memoized transitions
v18.1	anchor lowering → 100% of patterns on the DFA path	★
v19	v18.1 + merged pure-digit group + IBAN union pass	★ best zero-dependency engine — shipped

v19 is the current production engine and the best zero-dependency result: no Onigmo, no PCRE2, no Aho-Corasick library — pure C over Ruby stdlib only, per the project's no-runtime-dependencies rule.

Full blow-by-blow, including the ideas that didn't work (BM pre-filter making glibc slower in v6, the v14 generation-counter cross-call corruption bug), is in research log §5–§6.

Memory & concurrency

• All C-side working buffers are heap-allocated and freed before the call returns. The only Ruby-managed allocation is the final result String, so GC can't collect anything mid-scan.
• Compiled patterns are immutable and shared (read-only after mm_init()). All per-scan mutable state — NFA scratch and the lazy-DFA cache — lives in per-thread storage, freed automatically when the thread exits.
• For inputs above a few KB, redact releases the GVL around the built-in scan, so a big redaction on one thread doesn't block other Ruby threads.

Details and the guarantees are in the FAQ and the README's Thread safety section.

Where the code lives

• Pattern data (the only file you edit to add a pattern): ext/data_redactor/patterns.c / patterns.h
• Full research narrative and benchmarks: docs/research_log.md
• Benchmark methodology: Performance & Benchmarks