- 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, min of 7–9; ratios are the point). The enveloping-group scan loop shipped; a bulk-copy of the capture-slot snapshot did not clear its bar:
| 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 |
Bulk block-copy of the slot snapshot (add_thread) and reload (load_working) | (a\|b\|c\|d)+ (slot 2) | 14.6 | 15.0 (+2.7%) | rejected |
| Bulk block-copy | (\w)(\w)(\w)(\w)+ (slot 10) | 19.1 | 20.2 (+5.7%) | rejected |
| Bulk block-copy | (abcd\|abc\|ab\|a)+ (slot 4) | 12.5 | 12.1 (−3%) | rejected |
The bulk-copy replaced the per-slot push_back/reload loops with a one-shot block append/copy. It cleared its target (+20–35%) on no case but a single high-thread × high-slot outlier (((a|b)(c|d)(e|f))+, +22%); the median was ~5% — exactly the stl_construct share the control profile attributed to it, so the bytes still had to be copied and only the per-element call overhead could go — and it even regressed some small-slot alternations. Measured, under threshold, not a pure win → rejected, so the slot snapshot stays a plain per-element loop.
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.An idea for capture-heavy parsing patterns that the general VM handles slowly (5–40 MB/s): use the existing real::dfa as a cheap boolean oracle — scan for the smallest position where any match starts — then run the anchored Pike VM only there, for the exact spans and groups. Prototyped standalone (no engine change); the property-net was a clean 0 divergence vs find_iter over acid cases plus ~9,600 random eligible patterns × texts (the oracle ⇒ pike-match assertion never fired), and on representative parsing text it hit the throughput target:
| Pattern | Engine | Prototype | Speedup |
|---|---|---|---|
[a-z]+(::[a-z]+)+ (qualified name) | 34 MB/s | 143 | 4.2× |
([a-z]+):([0-9]+):([a-z]+) (3 groups) | 26 | 139 | 5.3× |
const\|static\|volatile\|… (keyword alt) | 206 | 284 | 1.4× (already fast-pathed) |
"[^"]*" (few false candidates) | 146 | 134 | 0.9× |
Why it was retired anyway.** The win is real only when there are many false candidates that are costly to reject* — and rejecting them means the oracle re-scans the class run from every start, which is O(n·k). On an adversarial long class run ([a-z]+(::[a-z]+)+ over a 40 KB run of a) the prototype collapsed to 0.02 MB/s — ~1500× slower than the engine at that size, and quadratic from there — while find_iter stayed flat at ~30 MB/s (measured linear at 40/80/160 KB). That is the exact worst case the linear-time Pike VM exists to forbid: the two-pass oracle trades away REAL's central ReDoS-safety guarantee for a constant-factor win on structured input. No constant-factor speedup justifies reintroducing quadratic time, even opt-in, so the approach is shelved. DFA build cost was negligible (≤0.1 ms, one-shot).
The general VM's hot inner loop is add_thread — the epsilon-closure walk that, from a program counter, follows split/jump/save/assertion edges (a stack-driven DFS in priority order) until it reaches the consuming instructions, snapshotting capture slots for each. An idea to shrink it, RE2-style: when the closure from a program counter is a tree (acyclic, every pc reached once), linearise it once, at compile, into a flat side-table and interpret that — no DFS stack, no per-node opcode dispatch, just a forward scan with a seen-check per node and save/close bracketing. A cycle (an empty loop such as (a*)*) or a re-convergence keeps the DFS walk.
The mechanism was proven, not asserted.** A REAL_TRACE_ORACLE build ran both walks at every seed and asserted identical output (the same threads, order, and slots) — the DFS is the oracle. Over the whole test corpus and the exhaustive differential fuzzer this held for 3 218 434 cases at 0 divergence; a deliberately corrupted flatten aborted it (teeth-verified). So correctness was never the question — only whether it pays.
Why it was retired anyway — it does not pay, and the terrain says why.** Two measurements settle it:
\d{1,3}(\.\d{1,3}){3}, (a|b)+, \b\w+\b; noise). A seed closure is 3–7 nodes — it stops at the first consuming instruction — so the stack and dispatch it removes were already a sliver of the per-position cost.+-style split-backs the seen-check already dedups; the empty-loop cases that would need it classify as re-convergent and keep the DFS. But those tree closures are 3.3–8.5 nodes each — the same size regime the seed already measured at ~0 %. The closure walk is ~a fifth to a third of total runtime, spread across many tiny closures, and a flatten only removes their stack-and-dispatch part (~40 % of that) — an 8–12 % ceiling, below the bar that would justify a permanent second interpreter in the match loop.That interpreter is the real cost: dead weight the oracle would force every future engine change to keep byte-for-byte correct, bought for noise. The purity rule wins — the DFS closure walk, one code path, stays the only one.
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 position assertion, no klass_cp, no lookaround — those keep the general VM) 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.O(n·k) two-pass trap. One forward pass or one Pike pass, per search, always linear.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 position assertion and no lookaround; 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: 499 → 33 ns/B on dense (\w+)@(\w+)).
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 at ~5–6 ns/B where the VM ground at ~40. 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 from 33.4 to ~8.0 ns/B (4.2×), to 1.14× of 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/.**
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: rust-lang/regex#1373 — 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.
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:
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; the notes below are about program size — how many NFA instructions a pattern compiles to (a small constant per byte matched).
IGNORECASE. abc is 3 byte ops; [0-9]+ and [b-d]+ compile to the same program with or without i.i): a cased ASCII literal or class gains its Unicode fold partners. A literal costs a few ops (k+ is ~10 — it folds to {k, K, Kelvin}); a class costs one branch per code-point range it accepts ([a-z]+ ≈ 18, [A-Za-z]+ ≈ 39). Folding a range pulls in the partners of every cased member; the ranges are coalesced (sorted + merged) so the result stays compact — [a-é]+ is ~43 ops, [à-ÿ]+ ~23, [U+0080-U+FFFF]+ ~29. These are tens of ops, far below the max_program_size cap in config.hpp, and the byte-class DFA collapses them to a handful of states (7–12). A pattern that ever did approach the DFA-state cap degrades to the general Pike VM (dfa_error → fallback), never to OOM.\d \s): a Unicode shorthand expands to one branch per code-point range it accepts, so it is far larger than its ASCII form. Measured program size (instructions / interned classes), text vs flags::ascii: \d+ 386/60 vs 5/1; \s+ 43/14 vs 5/1; [\d.]+ 386/60 vs 5/1; \D 1108/128 vs 19/5 (a complement spans the gaps between digit ranges). Consequences: the single-class scan-loop fast path does not apply (a Unicode \d+ runs on the general VM — still linear); the fixed-width lookbehind budget (255 bytes) tightens because \d now spans up to 4 bytes ((?<=\d{63}) compiles, \d{64} is rejected); and a static_regex over a Unicode shorthand needs a raised constexpr budget (see below). Use flags::ascii (re.A) or an explicit ASCII class ([0-9]) where the ASCII form suffices. The larger \w (771 ranges) only sharpens this, as the throughput measurements below show.\w. In the byte-level Pike VM each thread is stepped one byte at a time and every alternative class branch is evaluated per position, so a large code-point class costs O(number of classes) per byte. Measured find_all throughput, text vs flags::ascii (200 KB subject): \s+ (14 classes) 106 vs 319 MB/s (≈3× slower — fine); \d+ (60 classes) 1.9 vs 311 MB/s (≈163×); \w+ (472 classes) 0.1 vs 344 MB/s (≈2280×). A Unicode \w+ also compiles to ~5042 instructions (\w{3,10} ≈ 50 000, \w+@\w+\.\w+ ≈ 15 000) and costs ~0.9 ms/pattern to build. \w on the byte-NFA path is therefore unusable** for its dominant job (tokenising ASCII text), which vetoed wiring it that way.klass_cp opcode is the fix (measured). A text-mode Unicode shorthand emits a single match-time code-point predicate: decode one code point, test membership (ASCII bitmap below 0x80, a binary search of the range table above), apply negation, then walk the continuation bytes through a computed skip — O(≤4 bytes + log ranges) per position, independent of the class count. \w+, \d+, \s+ each compile to 8 instructions (from 5042 / 386 / 43), one interned class. A whole-pattern shorthand (optionally +) also takes a code-point scan-loop fast path (the analog of the ASCII class+ loop). That loop uses the same tricks as the byte-NFA scan: an ASCII byte tests a byte-indexed table (no decode), and a non-ASCII code point in the two-byte range [U+0080, U+07FF] — where European text lives (Latin, Greek, Cyrillic, Hebrew, Arabic…) — tests a lazily-built page bitmap in one load rather than a ~771-range search; only CJK / astral code points search. Measured find_all throughput vs the flags::ascii ceiling (2 MB subject): \w+ on ASCII text ~**88–90%** of the ceiling (~890 vs ~1000 MB/s), on mixed accented text ~810 MB/s, on heavy non-ASCII ~330 MB/s. The tiny program also lets a text-mode static_regex<"\\w+"> compile within the default constexpr budgets again (no -fconstexpr-steps bump). \b/\B word-ness likewise takes an ASCII shortcut (a byte below 0x80 is a whole code point, so it skips the back-decode), bringing \b\w+\b back to exact parity with the byte-NFA \b[a-z]+\b.\b/\B (or ^/$ in a way the fast paths do not cover) cannot take a scan-loop, so it runs the general Pike VM, whose per-position cost (thread lists, capture slots) is ~20 ns/byte regardless of the class — \b\w+\b and \b[a-z]+\b measure the same. The capture-slot half of that cost is now copy-on-write (§7.5); the closure-walk half is what the lazy-DFA investigation targets for the assertion and multi-group rows (see section E of BENCHMARKS.md, where a \b\w+\b / (\w+)@(\w+) duel against the rust regex crate records the gap).memchr/memmem (already SIMD internally); a hand-written SIMD class scanner was prototyped and removed. It was ~7.7× on a synthetic long single-class run (a 40 KB block of one class) but ~1.1× on representative word text — where runs are short and the loop is dominated by match bookkeeping, not the inner scan — for thousands of lines of intrinsics and a portability burden. unicode_fold.hpp orbit table (~2900 entries) adds ~20 ms to a translation unit that includes real/real.hpp; a static_regex with IGNORECASE folds at compile time (constexpr), which is the usual constexpr cost, not a runtime one. A static_regex over a text-mode Unicode shorthand builds a large constexpr program: it exceeds clang's default -fconstexpr-steps (~1M) and MSVC's /constexpr:steps (100k) — the test build raises both to 33 554 432 (GCC's default is already enough). Consumers using such patterns at compile time may need the same flag; the dynamic real::regex at runtime is unaffected.re, with its rationale. 1.9.8