- Generated by
1.9.8
|
REAL
Regular Expression Algorithmic Library — constexpr C++20 regex
|
This page is a self-contained tour of REAL for a reader new to regex engines. It follows a pattern from text to a match, explains the data structures that make the engine fast and small, and points at the file or class responsible for each step. It pairs with the per-file API reference generated from the headers.
At a glance. REAL is a linear-time (ReDoS-safe),
constexpr, header-only, dependency-free regex engine: a Thompson NFA simulated by a Pike VM, accelerated by a literal prefilter and a handful of whole-pattern fast paths.
A regular expression denotes a set of strings; matching asks whether, and where, some text belongs to that set. What makes an engine trustworthy is not raw speed but a predictable worst case: it runs on untrusted patterns and untrusted input, so its running time is a security property.
There are two classic engine families:
re, std::regex): try one alternative, and on failure rewind and try the next. Simple and feature-rich, but on some patterns it explores exponentially many paths. On (a+)+b over \(n\) copies of a with no b, the work is \(\Theta(2^{n})\) — a few dozen characters can hang the program. An attacker who controls a pattern or input weaponizes this; it is called ReDoS.regex, REAL): track all the ways the pattern could match so far, advancing them together one character at a time. It never rewinds, so the time is \(O(n\cdot m)\) for input length \(n\) and program size \(m\) — linear in the input, for every pattern.REAL belongs to the second family. Linear time is a guarantee by construction.
What you'll learn: how the pattern string becomes a tree, and why the tree uses array indices instead of pointers.*
real::detail::parser is a hand-written recursive-descent parser: one function per grammar level, calling the next, mirroring the grammar exactly —
\[ \text{alternation} \to \text{sequence}\,(\,\texttt{|}\,\text{sequence})^{*}, \quad \text{sequence} \to (\text{atom}\;\text{quantifier}?)^{*} \]
so real::detail::parser::parse_alternation calls parse_sequence, which calls parse_atom then parse_quantifier. An atom is a literal, a class [...], a group, an anchor or an escape. Each malformed construct throws a real::regex_error carrying the byte offset of the problem, so messages point at the exact spot.
The tree (real::detail::ast) is an index pool: every real::detail::ast_node stores its children and next sibling as int32_t indices* into one std::vector, never as pointers.
constexpr-friendliness: there are no raw pointers to chase (cache-friendly) and no pointer-based ownership (so the whole tree is a literal value the compiler can build during compilation).Scoped inline flags** ((?i:…), (?-x:…), (?ms-i:…)) are handled with a small flag-scope stack** in the parser. The base of the stack is the constructor's flags (a leading (?imsxa) folds into it); entering a scoped group pushes a modified copy for its body and leaves pops it. The parser reads the current flags from the stack top — verbose changes tokenization there and then (insignificant whitespace and # comments), while every node it creates is stamped with the flag set in force where it was parsed (its effective_flags). The compiler then reads those per-node flags, not a global: a class folds under its node's icase, a . includes \n under its node's dotall, ^/$ pick their line-relative form from its node's multiline, and a word boundary carries its ascii word-ness. So one flag can be on for part of a pattern and off for another — the stack decides at parse time, the node bits carry the decision to compilation, and a pattern with no scoped group stamps every node identically and compiles byte-for-byte as before.
real::detail::compiler turns the tree into a flat program of instructions — an NFA in bytecode — by Thompson's construction: each node becomes a small fragment and the fragments are wired together. a(b|c) becomes:
The instruction set (real::detail::opcode) is small: byte/klass consume one input byte if it matches a literal or a 256-bit class; split forks two possibilities (this builds |, *, +, ?); jump is a goto; save records a position into a capture slot; match accepts. There is no loop instruction — a* is a split that enters the body or skips it, with a jump back — and bounded repeats like a{3} are unrolled.
patch_x/patch_y. Centralizing this was the single biggest source of bugs in earlier engines; one disciplined helper makes the fragment wiring provably consistent.What you'll learn: how tracking many states at once avoids backtracking, and the one invariant that makes it linear.*
A backtracker walks one path at a time. The Pike VM (real::detail::pike_vm) keeps a list of live threads — one per program counter the pattern could currently be at — and advances every thread by the same input byte. run loops over input positions; step consumes the byte (a thread whose byte/klass fails dies); and on split/jump/save the epsilon closure follows the no-input edges to enqueue the reachable consuming states.
The one idea that makes this linear is deduplication: at each input position a given program counter is enqueued at most once. real::detail::basic_thread_list stamps each pc with a generation counter, so "already seen?" and clearing the list between positions are both \(O(1)\). With only \(m\) program counters, each of the \(n\) positions does \(O(m)\) work:
\[ T(n) = O(n \cdot m), \qquad \text{independent of the pattern's shape.} \]
That invariant — each state at most once per position — is exactly what a backtracker lacks, and exactly why no input can make REAL blow up.
Matching must pick the leftmost match and, among ties, the greedy / first-alternative one, and report capture groups. REAL keeps the thread list in priority order**: a split explores the preferred branch first, so the first thread to reach match is the one Perl and Python would choose. Captures are save instructions writing offsets into a thread's slots.
The closure could copy every thread's slots at each fork (expensive). Instead it mutates one working-slots array along a depth-first walk and pushes a restore* entry (real::detail::eps_entry) to undo the write when the subtree is done — so capturing costs an undo record, not a slot-array copy.
| Property | Backtracking | DFA | Pike VM (REAL) |
|---|---|---|---|
| Worst-case time | \(\Theta(2^n)\) | \(O(n)\) | \(O(n\cdot m)\) |
| Memory | recursion depth | states (can explode) | \(O(m)\) threads |
| Capture groups | yes | not natively | yes |
| ReDoS-safe | no | yes | yes |
| constexpr-friendly | n/a | no (mutable cache) | yes |
A DFA is faster still — one table lookup per byte — but can need exponentially many states, does not natively yield captures, and its mutable state cache cannot run at compile time. REAL keeps the Pike VM and recovers the constant-factor speed with the fast paths of 7. The fast paths; measured against RE2 (a mature lazy-DFA engine) the combination matches or beats it across the benchmark, so a second engine is not worth its complexity. Backreferences (\1) would force backtracking and forfeit the linear bound, so they are excluded.
What you'll learn: how a byte-at-a-time engine matches whole Unicode codepoints without ever decoding them in the hot loop.*
A character class is a real::detail::char_class — a 256-bit bitmap (four std::uint64_t) whose membership test is a single shift-and-mask:
\[ b \in S \iff \big(\text{bits}[\,b \gg 6\,] \gg (b \,\&\, 63)\big) \,\&\, 1 . \]
\w \d \s are Unicode in text mode (via the generated unicode_props.hpp ranges and the klass_cp opcode), and ASCII in bytes mode or under flags::ascii; case folding is full Unicode for literals/classes (text-mode IGNORECASE, via the generated unicode_fold.hpp orbits), ASCII for the shorthands. The payoff is alignment: a construct that matches a whole codepoint (., a negated class) is compiled to a byte-level alternation over the UTF-8 lead/continuation byte sets (the utf8_*_set of charclass.hpp) —
\[ \texttt{.} \;\equiv\; \underbrace{\text{ascii}}_{1\text{ byte}} \;\big|\; \text{lead}_2\,\text{cont} \;\big|\; \text{lead}_3\,\text{cont}\,\text{cont} \;\big|\; \text{lead}_4\,\text{cont}\,\text{cont}\,\text{cont} \]
so the engine still steps one byte at a time (the thread-list model and the linear bound are untouched), yet a match can only end on a codepoint boundary, because that structure only accepts well-formed sequences. Because class members stay ASCII, a delimiter byte never appears mid-sequence, which is what keeps the boundary guarantee.
The byte-range expansion above is right for . and small classes, but a Unicode shorthand such as \w spans ~771 ranges — expanding it to byte alternatives is ~5000 instructions and, worse, makes the Pike VM step O(number of classes) per byte (a 2000× slowdown for \w+ on ASCII text). The klass_cp opcode (real::detail::opcode) sidesteps both: it keeps the class as a range table and, at a position, decodes one code point and binary-searches it — O(≤4 bytes + log ranges), independent of the class count.
The subtlety is that klass_cp consumes 1–4 bytes but the VM only advances one byte per step. It is emitted as a fixed four-slot chain [klass_cp][cont][cont][cont] (the three cont are ordinary klass utf8_cont ops). klass_cp decides membership on the whole code point, then posts the thread to pos + 1 — like any byte op — entering the chain at the computed offset pc + 1 + (4 − len), so a len-byte code point walks exactly len − 1 continuation ops over the next steps. This is a structural** padding, not a semantic one: because the thread still advances in lock-step, one byte per step, thread priority, per-list dedup and the generation counter are all unchanged — the property that made the ring-buffer alternative unnecessary. A whole-pattern shorthand additionally takes a code-point scan-loop fast path (7. The fast paths) that shares the same membership test, so the two paths cannot disagree.
What you'll learn: the handful of structures that give top speed, minimal memory, and a simple, robust core.*
emit_klass), so the UTF-8 continuation class — emitted dozens of times — is stored once and referenced by index.small_vec<T, N> keeps the first N inline and spills to the heap only beyond that. The common small match therefore allocates nothing, and the size field uses the smallest integer that can index the inline buffer:find_all loop allocates once, then never again — and with the static storage policy, never at all.constexpr. A static_regex builds its program twice: once to measure each array, then to fill exactly-sized constexpr arrays (real::detail::static_vec). No slack, no heap.real::static_regex<"\\d+"> is a distinct type carrying its own program.memchr/memmem used by the prefilter are already vectorized, and an earlier SIMD experiment added thousands of lines for no measurable gain), and no second engine — micro-optimizations are kept only when a benchmark proves them.Linear time bounds the growth, not the constant. analyze_program (prefilter.hpp) inspects the program once and records hints; the engine then shortcuts whenever it can, and otherwise falls back to the Pike VM:
For instance [0-9a-f]{8} compiles to eight identical klass instructions; analyze_program recognizes the fixed-width shape and the engine matches it by scanning eight class bytes in a tight loop — no thread list — which on the benchmark turns its worst relative case into a win over RE2.
constexpr, and by a differential fuzzer that compares against Python's re over tens of thousands of generated patterns (it has caught real engine bugs, including an empty-match divergence and a UTF-8 boundary case).A class loop wrapped in exactly one capturing group — (\w+), ([a-z]+), (\d+), (\w) — used to fall to the general VM (~28× slower) purely to fill the group's slots, even though its body already qualified for a scan-loop fast path. But the group envelops the whole match, so by construction start(1)==start(0) and end(1)==end(0): the fast path mirrors the whole-match span into the group slots with no re-match. The shape detection tolerates exactly one inner save/save pair immediately inside the outer one and records the group slots; the scan loops fill them through one shared helper. Strictly scoped — a lazy body (\w+?), a trailing atom (\w+)x, nesting ((\w+)), a second group (\w+)(\w+), and a non-capturing (?:\w+) all stay on the general VM.
Two candidate optimizations were measured on the general VM (find_iter, 2 MB ASCII). The enveloping-group scan loop shipped; a bulk-copy of the capture-slot snapshot did not clear its bar and the slot snapshot stays a plain per-element loop:
| Optimization | Representative case | Before | After | Verdict |
|---|---|---|---|---|
| Enveloping-group scan loop | (\w+) | 31.5 MB/s | 751 MB/s (24×, ≈ the \w+ fast path 825) | shipped |
| Enveloping-group scan loop | ([a-z]+) | 32 | 660 | shipped |
The fixed-shape fast path (a straight-line run of one-byte-wide byte/klass ops) now tolerates capturing saves interleaved between the runs — (\d{4})-(\d{2})-(\d{2}), (a)(b). Because every consuming op is one byte, each save sits at a compile-time-constant offset from the match start; once the single verifying walk has located [s, e), one linear pass writes each group slot as s + offset — no re-match, no VM. The no-group run keeps its own tight loop (the save-skipping walk is a separate if constexpr instantiation, so there is no branch and no regression on it). Measured find_iter over 2 MB: (\d{4})-(\d{2})-(\d{2}) 39 → 308 MB/s (7.8×, the ungrouped fixed shape runs 433).
\d under re.A) and explicit classes ([0-9]) — a bitmap, one byte each. A text-mode Unicode shorthand (\d, \w) is a klass_cp code-point predicate of variable width, so it does not qualify and stays on the general VM; likewise a variable count ({n,m}, +, *, ?), a nested group, an alternation, or a lookaround. So (\d{1,3}\.){3}\d{1,3} (an IPv4-shaped pattern) is excluded by construction.The other half of add_thread's cost is capture slots. The value model snapshots all slot_count capture values per thread — once when a thread is stepped, once per thread emitted into the next list — which profiling put at a fifth to a third of match time on capture-carrying patterns. The blocks threads carry are, however, mostly identical: forks share a common past and diverge only where a group boundary is crossed. So a thread now holds a capture block by index into a small refcounted pool (real::detail::basic_capture_pool): a split shares the block (increment), and a save — the one write — copies it first only if it is shared (real::detail::basic_capture_pool::cow_write). Block 0 is a canonical all-npos block every seed shares, so seeding a position is one increment, not an allocation. There is no per-thread slot copy and no value-restore journal at all — a branch's block simply travels with it and is released when the branch dies, which replaced the previous mutate-and-restore closure machinery: one capture mechanism, and static_regex (compile-sized, zero-heap) shares it too, its pool a static_vec bounded by the worst-case live-block count.
Measured (find_iter, versus the value model), the gain scales with how many groups a pattern captures:
| Pattern | groups | Speedup |
|---|---|---|
\w+, [a-z]+ (no groups) | 0 | ~1.0× (within the ±2% noise) |
(\w+)=(\w+), (\w+)@(\w+) | 2 | 1.0–1.10× |
(\d{1,3})\.(\d{1,3})\.(\d{1,3})\.(\d{1,3}) | 4 | 1.29× |
(\d{4})-(\d{2})-(\d{2})T(\d{2}):(\d{2}):(\d{2}) | 6 | 1.67× |
So it pays for multi-group extraction — dates, log lines, scanf-style records — and is flat where there is little to share. It is not a universal speedup: the single- and two-group families measure 1.0–1.13×, so the arc's combined 1.5× ambition is not reached on low-capture patterns, and the honest positioning is *"scales with group count."* The cost is static_regex state size — the worst-case block pool roughly doubles it (a documented trade for the one-mechanism engine and for static's share of the win). Correctness is the value model's, exactly: 3.2 M differential cases agree, a refcount Σ-invariant is asserted at every run's end (and holds down to constexpr evaluation), and Valgrind is clean on the capture-heavy loops.
The word-boundary and multi-group capture rows of the rust duel (section E of BENCHMARKS.md) are what a lazy DFA* would close: rust answers a match's span by running a byte-at-a-time DFA that never touches its capture machinery, while REAL's Pike VM always tracks slots. The plan is a two-pass split — a forward DFA finds the match end, then the Pike VM runs only inside the window [start, end) to fill the captures — so the DFA carries the throughput and the Pike VM remains the single source of match semantics.
This subsection is the contract the forward pass must satisfy, written before it is wired in (real::detail::lazy_dfa is the inert scaffolding today). For every eligible pattern (no klass_cp, no lookaround — those keep the general VM; position assertions came later, see 7.10 Delivered: position assertions in the lazy DFAs) and every text:
span(pike) = (s, e) iff the forward pass reports end e and the start-finder reports s. The forward pass is kFirstMatch, not earliest-end and not longest-match: its DFA states are the Pike thread list's program counters in priority order; at a leftmost start it reports the end of the highest-priority thread that reaches match, and a lower-priority accept is suppressed while any higher-priority thread is still alive. (This is why it cannot be real::dfa, whose sets are unordered: a|ab on "ab" must be a (0,1), and aabaa|b on "aabaa" must be aabaa (0,5), not the earlier-ending b (2,3). Both are pinned acids.)kLongest. Given the end e, s is the smallest start with a match on [s, e] — equivalently, the longest match read backward from e. It runs the inverted program (its edges transposed, its consuming bytes kept) as a second cached DFA over the text scanned right-to-left from e, recording an accept every time it reaches the original start and continuing while any thread lives; the last accept (the furthest back) is s, bounded left by the search's resume point (never before it). Crucially this pass needs no priority ordering — priority is a forward concern only, so its states are plain unordered sets and its rule is longest, not first (RE2's reverse DFA is the same). The acid: a*b on "aaab" has e = 4; the reverse must give s = 0 (a reverse-*first* would stop after the b at s = 3 — wrong). Reverse eligibility equals forward eligibility (the same ops are refused).finditer rule carries across the two passes: after an empty match the next may not be empty at the same position (forbid_empty_until_, UTF-8-aligned), enforced on the same slot-0 comparison the Pike loop already uses — the forward pass reports the end, the Pike window applies the rule. The rule binds one position, so the search after an empty match splits in two: the VM, anchored at that position with the rule applied, decides whether a non-empty match starts there, and past it the DFAs search from the next character boundary with the rule lifted. Anchors read the whole text (\A holds at 0, \b reads the byte before), so starting there changes no verdict. Leaving the whole search to the VM had it find every other match of a pattern that can match empty: until 2026-09-26 .* counted lines 700 times slower than .+ (48 ms against 0.07 over 400 KB; now 3.7 ms).O(n·k) two-pass trap. One forward pass or one Pike pass, per search, always linear. The step that crosses the limit returns the dead state, which ends the scan's loop, and the scan reports a quit, the same one a Unicode word boundary next to a non-ASCII byte raises (7.10 Delivered: position assertions in the lazy DFAs); so the test sits on the cache-miss path and at the scan's exit, not on each byte. (Until 2026-09-26 the flag was set and read by nothing, and (a|b)*a(a|b){12}c over random a/b ran at four times the VM's cost; it now runs at 0.9 times.)The kFirstMatch boundary rule was validated out-of-engine against the Pike VM (the two acids, a 198k-case alternation differential, and mixed/nullable adversarials) before any of this was written; the in-repo property-net asserts it at each step from here on.
What it is wired to (and what a Unicode class costs).** pike.hpp routes an eligible search — after the fast paths, at run time, in search mode, past a measured input threshold — through the two passes: the forward DFA finds the end, the reverse finds the start, the Pike VM runs only on that [s, e] window for the groups and the empty-match rule. Eligibility is no lookaround (and, since 7.10 Delivered: position assertions in the lazy DFAs, no position assertion a byte cannot decide); a Unicode \w \d \s (klass_cp) is made representable by expanding it, via the shared utf8_range_sequences, into a byte-range sub-automaton in a byte-program the DFAs own — the Pike program stays byte-identical. That byte-program is large (a \w is thousands of instructions), which surfaced one trap worth recording: the priority cut is O(state size), so on those wide states it must be memoized per state or it dominates (it did: the cut dominated the walk until it was memoized).
When the walks from candidates give way.** With sound first bytes the search does not run the forward pass: it walks an anchored DFA from each candidate, which hands back the start with the end. Inside a long run of candidate bytes that no match ends, each walk rereads what the previous one crossed. anchored_walk_bill bills the walks that find nothing and gives way to one forward pass and one reverse once 8 × walks + bytes read passes 1.5 per byte crossed; the span filler behind count_matches and find_iter then carries on in that pass instead of handing back to the per-match route. Measured over 32 pattern and subject pairs on 2 MB of prose and of log lines (arm64, instructions retired, 2026-09-26), the walks won wherever at most 0.036 walks per byte crossed found nothing (e[a-z]*e: 13 M against 92 M) and lost wherever 0.4 or more did ([a-z]{2}\d: 234 M against 92 M), with nothing between; the score sat at most at 0.43 on one side and at least at 4.65 on the other. The rule stayed within 15 % of the better route on all 32, twelve of them patterns it was not fitted on.
The bilan — what the arc bought, measured ((\w+)@(\w+), default flags).** Against REAL's own pre-arc Pike VM: no-match 7.0×, sparse 6.0×, dense 1.3×. The no-match and sparse subjects — validation, log scanning — are the real win; the DFA rejects or skips an order of magnitude faster than the VM on those subjects. The dense-extraction row barely moves, and the three-column duel against the rust crate (BENCHMARKS.md §E.1) says why and names the two engines REAL has not built, both parked follow-ups:
memchres the required @ at a variable offset and verifies around each hit; REAL's rare-byte hint only covered a fixed offset. This closed the biggest remaining gap line (the date, 201× → 1.6× of rust).The dense floor §7.6 named was the span extractor, and this closed it. A pattern is one-pass when at most one thread crosses any byte matched anchored (RE2's onepass.cc); its captures then fill in a single left-to-right pass, no thread lists. real::detail::onepass classifies a pattern (over the same byte-program the DFAs use, so the default-flags Unicode \w \d \s — made deterministic by the UTF-8 trie — qualifies) and, when eligible, tabulates a capture-writing automaton the router runs on the located window instead of the windowed Pike VM. On dense (\w+)@(\w+) the arc took the full find_iter 4.2× closer to the rust crate's captures_iter — engine parity (BENCHMARKS.md §E.2).
Four findings, each surfaced by profiling before it was fixed (the discipline this arc kept):
std::call_once (thread-safe; the mutable DFA transition caches stay per-iterator). A Moore partition refinement recovers the byte-trie sharing the flood-fill loses (2508 → 660 nodes for the flagship), so the cached table stays small; a memory cap declines a pathological table back to the VM.state*stride + class array (one load) they cut the scan itself, no-match with it.call_once load on the hot path, a result re-binding its unchanged context — each now set once per walk.What one-pass does not touch: the sparse and no-match-prefilter gaps (still the inner-literal-prefilter follow-up above), and assertion-bearing or direct match/fullmatch patterns (a Tier-B follow-up — they stay on the sound windowed VM). Routed one-pass is byte-identical to the pure VM: the differential in tests/test_onepass.cpp proves slot-for-slot equality against the Pike engine.
A portability rule the arc cemented.** The engine headers use no std::hash and no std::unordered_map/set. Their hashing goes through an out-of-line libc++ symbol (__hash_memory on LLVM 19+) that a mismatched compiled-with-recent-headers / linked-against-older-libc++ pair fails to resolve at load time — a toolchain-drift class that is invisible on the machine that built it. Every cache and hash-cons here uses an in-house FNV over bucket-vectors instead (the lazy-DFA pc-set cache, the one-pass minimizer, the UTF-8 trie memo), which also keeps them literal types for constexpr. The standing rule: no std::hash or std::unordered_* in include/real/.**
When the table declines: a run of classes.** A Unicode \w is never one-pass at the byte level, so with groups to fill every window the DFAs found went to the Pike VM. A program of saves, atoms (a byte, a byte class, a code-point class) and greedy atom+ and atom* loops needs no engine: the walk that takes every loop as far as its atom matches, never backing up, chose the preferred branch at every loop whenever it could, so when it reaches match it is the highest-priority path and its groups are the VM's (pike_vm::match_run_shape); it ends where the DFAs said the match ends, since a loop cut short by that bound would put the VM's end past it. When an atom fails the walk – (\w+)(\d+) must give digits back – the VM decides. A group around one repeated atom, (\s)+, is a loop whose body holds saves around the atom: each further round tries the atom first, so the groups keep the last round that completed, as the VM's do. (\w+)\s+(\w+) lost 27 % of its instructions on prose and 28 % on log lines (arm64, 2026-09-26), and it, (\w+)\s*=\s*(\w+) and the inner-literal confirm of (\w+)\s+=\s+(\w+) run no VM window at all, which a counter compiled into the test binary only (vm_window_runs) pins.
The gap §7.6 named — a pattern whose match does not begin with a literal, so no prefix/rare-byte hint helps, but a rare literal sits inside it (the date's -, the email's @). The route mirrors the regex crate's ReverseInner, read before it was written:
!is_constant_evaluated) into its own byte-program stored on the program; a static_regex keeps the core search, sidestepping the constexpr budget.pike_vm::run_inner_literal): memmem the literal → reverse-match the prefix to the match start (the same reverse_dfa the lazy-DFA uses, on the prefix program) → forward-confirm anchored at the start (run_mode::prefix, no re-search) → on failure, resume the scan past the literal hit.The payoff: the date \d{4}-\d{2}-\d{2} on a no-match haystack went from 201× rust to 1.6× — a single memmem, the reverse DFA built lazily only when a candidate is actually found (BENCHMARKS.md §E.5).
Two traps and one lesson worth recording:
npos for every match. It now lives in the VM state, as the lazy-DFA's does in its immutables.storage.hpp's own state type, not pike_state. The route was silently inert (its if constexpr (requires …) false) until the cache fields landed there.((.))a, which the exhaustive corpus flagged with 22440 divergences. The linearity guard is the forward backstop (a candidate before the last confirm's forward reach abandons the scan to the core), not the reverse bound. It read as a missing quality heuristic; it was a one-line wiring bug. (rust's own reverse-suffix optimization had a sibling leftmost bug, found by REAL's differential fuzzer and fixed upstream in rust-lang/regex#1364 — the symmetry is instructive.)Parked follow-ups, named: an alternation-sibling extraction (a literal common to every top-level branch, foo|foobar), and a multi-literal set (memmem-of-several) for patterns with no single required literal.
A short search that reaches the general loop spent most of its time on bookkeeping the subject never amortised: (\w+)@(\w+) over nine bytes cost about 11 000 instructions, nearly all of them thread-list resets and the capture pool, per call. For a subject small enough that a bit per (instruction, position) fits real::detail::bounded_backtrack_bits, the general loop now walks the same program depth first (pike_vm::run_bounded_backtrack): a split's preferred branch first, each start in turn, every pair marked when entered and pruned when reached again. Each pair is entered once, so the O(n x m) bound holds; the stack of pending branches holds slot restores beside them, and spills to the heap past 256.
It gives the VM's answer, not merely a leftmost-first answer, and two properties carry that:
jump into a loop head already entered at this position takes the loop's exit (the VM's guard against an empty iteration). Only the walk at a position marks it, and it marks in the VM's order, so that position's marks are the VM's seen set at the moment of the jump.A program with a lookaround stays on the VM: a lookbehind walk pays for being asked out of order, and a depth-first walk asks out of order. The eligibility is a hint (pattern_hints::bounded_backtrack), so the differentials that blank the hints to reach the plain VM still reach it; the knob bounded_backtrack_route_disabled gives the route-against-VM differential in one binary.
On (\w+)@(\w+) a search over 9 bytes runs about a fifth of the instructions it did on the VM, and one over 63 bytes about an eighth, on x86-64 and arm64 alike.
^, $, \A, \z, \Z, \b, \B, \< and \> no longer take a pattern off the lazy DFAs (a Unicode word boundary with a quit, see the last paragraph). Each assertion is decided by at most two facts: what the byte before the position is, and what the byte after it is (or that the text ends there, or ends with one final newline). The DFAs carry the first fact in the state and read the second from the text.
\n and the ASCII word bytes each get classes of their own (two extra predicates in compute_lazy_alphabet), so any byte of a class tells whether it is a newline and whether it is a word byte.\A and ^ look only behind and are decided while the state is closed. An assertion that looks ahead stays in the state as a pending counter; before the accept test and the step, resolve decides it on the class of the next byte, on the end of the text, or on a final newline (two keys past the classes), and memoizes the result per (state, key).^ in mid-line), so before the first accept the dead state keeps reseeding instead of ending the scan. In text mode no match starts inside a code point: the forward pass does not seed on a continuation byte (an empty \B holds between the two bytes of é). The reverse pass needs no such rule: every consuming path of a text-mode program begins at an ASCII or lead byte, and an empty match sits at an end the forward pass aligned.Walks or one pass, by the same bill. A program with assertions walks from candidates like any other and gives way by anchored_walk_bill (7.6 Delivered: the lazy-DFA two-pass route (the contract, and what it bought)). On 2 MB of prose (arm64, instructions retired, 2026-09-26), count_matches for (?m)[a-z]+ing$ went from 935 M to 80 M instructions and (?a)\bfox\b|\bdog\b, whose candidates are rare, kept its walks at 54 M, against 177 M for the pass; patterns without assertions stayed within 0.2 %. The walks cost a constant factor, so no complexity test sees them: dfa_with_assertions_scans_once_not_once_per_candidate times both queries against the bare forward pass in the same binary, and anchored_walk_bill_verdicts pins the rule.
Unicode word boundaries, and the quit.** In text mode \b, \B, \< and \> use Unicode word-ness, and whether é is a word character is a property of the code point, which no single byte decides. Between two ASCII bytes, though, a Unicode word boundary is an ASCII one: the VM reads the byte itself on each side when it is below 0x80 (word_before and word_after). So the search DFAs carry these boundaries as ASCII ones and quit where one must be decided next to a non-ASCII byte (undecidable_word; \< and \> quit only when the ASCII side does not settle them). The alphabet splits off non-ASCII bytes, and their context is newline and word at once, a value no ASCII byte takes, so no table grows. The quit is tested in holds_ahead and holds_left, which every decision goes through, including those inside a resolution's own closure; resolve then returns a sentinel, quit_state, that is never interned and survives a flush. The scans hand it back in their result (anchored_result::quit, quit_pos), and every caller of the search DFAs gives that search, and only that one, to the VM: a quit is local to where a boundary met a non-ASCII byte, and giving the whole subject to the VM after the first quit cost \b\w+ing\b 44 % more on prose with curly quotes. On 1 MB of ASCII prose (arm64, 2026-09-26), count_matches for \b\w+ing\b went from 10.2 to 2.8 ms; on prose with curly quotes and on French no pattern measured was slower, and \bfox\b|\bdog\b was three times faster, its walks rarely meeting a non-ASCII byte. dfa_unicode_word_boundaries_quit_next_to_non_ascii puts a non-ASCII byte at each place a route could meet it and compares every query with the plain VM.
The headers under include/real/ are partitioned into dependency tiers, and a header may include only from its own tier or a lower one. The rule is executable — tools/check_layers.py (the check-layers gate) fails the build on any upward include, so the layering is a fact, not a comment. Low to high:
core/** — the IR and primitives: program.hpp (opcodes, instr, program_view, code_range), charclass.hpp (the byte-set bitmap), config.hpp (the resource caps).unicode/** — utf8.hpp (codepoint decode), unicode_props.hpp / unicode_fold.hpp (the generated property and case-fold tables). Above core: the tables index the IR's code_range.engine/ + automata/** — one runtime tier: pike.hpp (the VM), prefilter.hpp, assert_eval.hpp, and lazy_dfa.hpp / onepass.hpp / utf8_ranges.hpp. One tier because they interdepend — pike → onepass, and onepass → assert_eval — a dependency allowed within the tier and forbidden across it.frontend/** — ast.hpp (recursive-descent parser) and compiler.hpp (Thompson construction); they consume the runtime's prefilter and utf8_ranges, so they sit above it.real.hpp / dfa.hpp, and storage.hpp, the assembly real::regex drivesstd/** — the std::regex-compatibility drop-in (real::compat): regex.hpp and its parts, built on the public real::regex (root tier). tools/check_layers.py ranks it with root.bindings/** is outside the engine tiers — the C ABI shim, the abi3 Python binding and the Rust crate. The C shim is source-only (compiled into consumers, not installed as a library); see bindings/README.md for the CMake-position rationale. (it orchestrates parse → compile → store, so it depends on every tier below).| Header | Key types / functions | Role |
|---|---|---|
core/config.hpp | max_program_size, max_nesting_depth, … | The resource caps (see 9. Compile time and safety). |
core/charclass.hpp | real::detail::char_class; digit_set…; utf8_*_set | The byte-set bitmap, the ASCII sets, the shared UTF-8 sets. |
core/program.hpp | real::detail::opcode, real::detail::instr, real::flags, real::detail::pattern_hints, real::detail::program_view | The compiled program's vocabulary and a non-owning view of it. |
unicode/utf8.hpp | codepoint_advance | Step one whole codepoint (only to advance past an empty match). |
frontend/ast.hpp | real::detail::ast_node, real::detail::ast, real::detail::parser | Recursive-descent parser → index-pool syntax tree. |
frontend/compiler.hpp | real::detail::compiler | Thompson construction with atomic offset patching. |
engine/prefilter.hpp | analyze_program, find_byte, find_prefix | Search hints, candidate skipping, fast-path shape recognition. |
engine/pike.hpp | real::detail::pike_vm, real::detail::basic_thread_list, real::detail::basic_pike_state | The engine: thread lists, scratch, run loop, fast paths. |
storage.hpp | real::detail::dynamic_storage, real::detail::static_storage, real::detail::small_vec, real::fixed_string | Where the program and scratch live: heap, or exact constexpr arrays. |
real.hpp | real::regex, real::static_regex, real::basic_match_result | The public API: match/search, iteration, replace, split. |
One parse → compile → execute pipeline, parameterized on a storage policy, backs all three memory modes (no second hierarchy): real::detail::dynamic_storage (heap, sized once) and real::detail::static_storage (compile-time, exact arrays — including the hybrid compile-time-pattern / runtime-text mode).
Recorded, not scheduled — deliberate next steps the current design leaves room for:
regex_immutables cold-split buys memory density (984 of real::regex's 1512 bytes) and zero** throughput, since searches never touch it and a warm copy costs 0.366 µs either way; the shared DFA map costs 0 allocations per search; merging the membership row-buffers and compacting row_ready sit inside an 11.3 µs compile paid once per regex. cp_hi_table's dual representation is the one still unpriced — the probe returned at the first match instead of scanning the band, so it needs a full-scan measurement before anyone believes a number about it.regex_set audit, priced. Same discipline as the previous round, same outcome — the ranking came out of measurement, not intuition. regex_set dominates by 10–50×: is_match costs 1237 ns and 13 allocations to return a bool, matches 2329 / 31, which 2380 / 32. Everything else is small: regex_replace into an output iterator does buffer through a string, but that is +265 ns and 2 allocations on a 1425 ns call, not the "medium to high" it was billed as; regex_token_iterator with one submatch is 110 ns / 3; named_groups() is 42 ns / 2 per call (its real defect is the quadratic above, not the call cost); and sub_match comparison allocates nothing** under small-string optimisation — the concern only bites past it, which the audit did not say. Unmeasured: the Python RegexSet staging, and the compat layer's std-route result duplication.pattern_hints. The state_type lift is done (10.1 The inlining budget) and the next layout work is now measurable because of it. pattern_hints is 232 of program_view's 432 bytes and mixes fields read almost everywhere with cold arrays only a few routes consult; splitting it would cut what every route carries. Named rather than started, and with a caveat: this file records past field moves changing throughput by layout, and layout deltas are precisely what the budget lottery made unreadable — those historical figures deserve the same audit the refutations in 10.1 The inlining budget got.namespace real (not real::detail), so the public API cannot grow by accident. The most durable extension of the layering philosophy.automata/immutables.hpp.** The per-regex immutable cache (byte-program, alphabet, one-pass table) currently lives inline in the routing; extracting it would let the router and the tests name it directly.real::regex search path, not a new public automaton.first-accept) mode.** The forward pass currently runs to the greedy end of the leftmost match; stopping at the first accepting state (priority ignored) would give a true "shortest match" end — what the rust regex crate's shortest_match returns. Small, and it would let the Rust binding drop the one residual shortest_match divergence. Parked.friend-across-tier rule. Splitting the Doxygen tree into reference/ and internals/, and forbidding cross-tier friend (the layering gate sees includes, not friendship), are smaller hygiene follow-ups.detail::fnv1a (the FNV-1a accumulator is written three times — onepass, the lazy-DFA hash-cons, and the trie memo); factoring the twice-written compute_eligibility; dropping the one-pass builder's write-only diagnostic breadcrumbs (bail_node_ / bail_class_ / bail_pc_ — the bail reason is read, the location fields are not); deciding consumed_width's fate (inline it or document it as an extension point); and unifying the std::ranges style (only onepass.hpp dissents). Plus the Rust bindings/rust/src/lib.rs split into ffi / error / iter / builder / replace / bytes modules, so the str/bytes parity gap is visible in review rather than a manual diff.Every stage above is constexpr, so real::static_regex is parsed, compiled and matched while your program compiles, and an invalid pattern is a compilation error. Two denial-of-service vectors are closed structurally: ReDoS via input* by the linear-time guarantee, and resource exhaustion via pattern (e.g. a{1000}{1000} unrolling) by the caps in config.hpp on program size, nesting depth, repeat and group counts.
Everything is linear in the subject length. Constants, competitive tables and stamp history live in BENCHMARKS.md; what a timing claim is allowed to say lives in MEASUREMENT.md. This section names the structural properties only.
IGNORECASE.\d \s \w) compile to a single klass_cp predicate, not one branch per range. Wired as a byte-NFA they are unusable on their dominant job (tokenising ASCII text).memchr/memmem.static_regex puts the pattern in the type, so each distinct pattern is a distinct State and a private copy of every route. GCC's --param inline-unit-growth is a fraction of the translation unit: when the cap is hit, remaining inlines are declined in traversal order, and a pattern whose executed path never changed can slow down because of other patterns in the same TU. The state_type lift closed the worst of that multiplication. The diagnosis, the refutations, and the figures are in MEASUREMENT.md and in the comments on real::detail::static_storage. Do not cite a number about this file without reading those.
re, with its rationale. 1.9.8