Regex Engine Design

The Trieste regex engine is a header-only C++20 NFA-based matcher in include/trieste/regex_engine.h. It compiles UTF-8 regexes with a shunting-yard + Thompson pipeline and simulates them with epoch-based state deduplication.

The engine started as an iregexp-focused implementation, but now includes compatibility extensions used by Trieste parsers and rewrite helpers.

Architecture Overview

The engine processes a regex in four phases:

regex string ──► postfix runes ──► NFA ──► finalization ──► simulation
               (shunting-yard)   (Thompson)  (closures+bitmaps) (parallel)

1. Shunting-yard (regexptopostfix_runes): Converts regex text to a

postfix rune stream with explicit operators.

1. Thompson's construction (postfixtonfa): Walks the postfix sequence

and builds an NFA from StateDef nodes using a fragment stack.

1. Finalization (precomputeepsilonclosures + finalize_states):

Precomputes epsilon closures (with trivial-closure detection) and populates per-state ASCII acceptance bitmaps.

1. Parallel simulation (match / find_prefix): Tracks active NFA

states using precomputed epsilon closures and per-call MatchContext state.

Headers

regexengine.h includes both unicodedata.h and utf8.h.

Public API

RegexEngine(const std::string_view& utf8_regexp);
RegexEngine(const std::string_view& utf8_regexp, SyntaxMode mode);
bool ok() const;
size_t num_captures() const;
SyntaxMode syntax_mode() const;
bool match(const std::string_view& utf8_str) const;
bool match(
  const std::string_view& utf8_str,
  MatchContext& ctx) const;
size_t find_prefix(
  const std::string_view& utf8_str,
  bool at_start = true) const;
size_t find_prefix(
  const std::string_view& utf8_str,
  MatchContext& ctx,
  bool at_start = true) const;
size_t find_prefix(
  const std::string_view& utf8_str,
  std::vector<Capture>& captures,
  bool at_start = true) const;
size_t find_prefix(
  const std::string_view& utf8_str,
  std::vector<Capture>& captures,
  MatchContext& ctx,
  bool at_start = true) const;
SearchResult search(
  const std::string_view& utf8_str,
  size_t start_pos = 0) const;
SearchResult search(
  const std::string_view& utf8_str,
  std::vector<Capture>& captures,
  MatchContext& ctx,
  size_t start_pos = 0) const;

• SyntaxMode::Extended (default) enables the full regex syntax.

SyntaxMode::IregexpStrict restricts to RFC 9485 iregexp.

• ok() returns true when the regex compiled successfully (no errors).
• match() checks full-string match for the given input.
• find_prefix() returns the longest matching prefix length, or npos.
• search() finds the first match anywhere in the string starting from a byte

offset. Returns a SearchResult with matchstart, matchlen, and found(). The capture-aware overload fills group spans and reuses a MatchContext across calls. Used by TRegex::GlobalReplace.

• Capture-aware find_prefix() fills group spans as byte offsets.
• at_start controls whether ^ can match in this invocation. This is used by

wrapper-level scanning logic (for example global replacement probe loops).

• MatchContext is the reusable per-caller/per-thread scratch state for

simulation and stats.

Rune Constants

All constants live in namespace trieste::regex as inline constexpr.

ASCII character constants

Named aliases for ASCII characters that have syntactic meaning in regexes:

Operator sentinel runes

Internal operator tokens placed in the postfix stream. Their values are in the range 0xAFFF00–0xAFFFFF, well outside Unicode, so they cannot collide with literal runes (including escaped operators like \*):

Class-ref sentinels

A label in the range [RuneClassBase, RuneClassMax] (0xBF0000–0xBFFFFF) is not a literal rune but an index into RegexEngine::runeclasses. This allows StateDef to remain unchanged — a class-ref is just a label value that step() dispatches differently.

Helper functions: isclassref(label), classrefindex(label).

Resource limits (RFC 9485 §8)

Utility Functions

decoderune(utf8str, pos)

inline std::pair<rune_t, size_t>
decode_rune(const std::string_view& utf8_str, size_t pos);

Decodes one rune from utf8str at byte offset pos. Returns {runevalue, bytesconsumed}. ASCII fast path: if the byte at pos is < 128, returns immediately without calling utf8torune. Used by all simulation loops — callers must ensure pos < utf8str.size().

Key Data Structures

RuneClass

A sorted, non-overlapping set of [lo, hi] inclusive rune_t intervals. Used to represent dot (.), character classes ([a-z]), and Unicode categories (\p{L}).

Fields:

• ranges — std::vector<std::pair<runet, runet>> of sorted intervals.
• asciibitmap[2] — uint64t[2] bit-per-codepoint bitmap for runes

0–127. ascii_bitmap[r >> 6] >> (r & 63) & 1 tests membership in O(1). Rebuilt automatically by normalize(), complement(), and dot().

Methods:

• contains(rune_t) — ASCII bitmap check for r < 128, else O(log k)

binary search on ranges.

• add_range(lo, hi) — push a range without normalizing. Call finalize()

when done.

• merge(other) — append another class's ranges without normalizing. Call

finalize() when done.

• finalize() — sort, merge overlapping ranges, and rebuild the ASCII

bitmap. Must be called after all add_range/merge calls are complete, before the class is used for matching or complement().

• complement() — complement over Unicode scalar values (0–0xD7FF,

0xE000–0x10FFFF), excluding surrogates. Requires finalized input.

• dot() — static factory returning all Unicode scalar values.

Private:

• rebuildasciibitmap() — scans ranges and sets bits for runes 0–127.

RuneClass objects are stored in a std::vector<RuneClass> runeclasses member on RegexEngine. makeclassref(rc) appends a class and returns the corresponding class-ref sentinel for use in the postfix stream.

StateDef

Each NFA state is a StateDef, stored contiguously in a pre-reserved std::vector<StateDef> ownedstates. Referenced internally via raw pointer alias State = StateDef*.

Fields:

• label — the rune this state matches, a class-ref sentinel (dispatched via

RuneClass::contains()), or Split/Match for control states.

• next — primary successor state.
• next_alt — secondary successor (used only by Split states).
• closure_index — dense state index for closure cache and dedup.
• asciiaccept[2] — uint64t[2] per-state bitmap. Populated by

finalizestates(): class-ref states copy their RuneClass's asciibitmap, literal states with label < 128 set the single corresponding bit, all others remain zero. Enables step() to bypass isclassref/classrefindex/contains for ASCII runes.

• trivialclosure — bool, set by precomputeepsilon_closures().

True when the state's epsilon closure is {self} for all 8 flag combinations (always true for literal/class-ref/Match states). Enables add_state() to skip the closure cache lookup.

Ownership/lifetime model:

• The constructor computes the postfix first, then reserves

ownedstates with capacity 2 * postfix.size() + 1 to guarantee no reallocation during Thompson construction. This keeps raw State pointers (including Frag::dangling targets) stable.

• createstate() appends a StateDef to ownedstates_ and returns a

raw pointer to it.

• All construction temporaries (the fragment stack, closure-computation

epoch vectors) are function-local — they exist only during the constructor call and are destroyed automatically.

• RegexEngine is explicitly non-copyable and movable to keep raw-pointer

ownership semantics safe and obvious.

MatchContext

MatchContext is public API with private internals (friend to RegexEngine). It holds per-call mutable state:

• noncapturingcurrentstates, noncapturingnextstates — scratch vectors

for non-capturing simulation.

• visited_states — per-state epoch vector for dedup (used when > 128

states).

• visitedbits[2] — uint64_t[2] bitset for dedup when ≤ 128 states

(BitsetMaxStates). Faster than epoch-based dedup for small NFAs.

• usebitset — chosen at bindengine() time based on statecount.
• capture_frames — contiguous arena for capture slot storage.
• capturetraversalstack — std::vector<std::pair<State, sizet>>

reusable stack for iterative addstatecapturing.

• epoch_counter — monotonic counter for epoch-based dedup.
• Optional MatchStats (gated by TRIESTEREGEXENGINEENABLESTATS).

Reuse model:

• Reuse a context across calls in one caller/thread.
• Do not use the same context concurrently across threads.
• Each match call binds the context to the engine, allowing safe context reuse

across different compiled engine instances.

MatchStats

Optional counters (gated by TRIESTEREGEXENGINEENABLESTATS):

• rune_steps — total input positions processed.
• activestatestotal — cumulative active states across steps.
• maxactivestates — peak active state count.
• classrefchecks — class-ref dispatch count (non-ASCII path only).
• literal_checks — literal label comparisons (non-ASCII path only).

Capture and Thread

• Capture stores [start, end) byte offsets and a matched() helper.
• Capture-aware simulation uses Thread { state, caps_frame } where

caps_frame indexes a contiguous capture-frame arena.

• Capture slot storage is held in MatchContext's frame arena with fixed frame

width 2 * numcaptures.

• Capture open/close epsilon transitions clone frame contents, update one slot,

and continue traversal so sibling branches keep independent capture state.

Frag

A fragment of an NFA under construction:

• start — the entry state of the fragment.
• dangling — a std::list<State*> of raw pointers into the next or

next_alt members of states within the fragment. patch() sets them all to point to a given target state.

ClosureSpan

A lightweight view into the flat closure cache:

• data — pointer into closurecacheflat_.
• size — number of states in this closure.

Returned by epsilonclosurecached().

Phase Details

Phase 1: Shunting-yard (regexptopostfix_runes)

Converts infix regex syntax to postfix tokens with:

• implicit concatenation (Catenation)
• alternation (Alternation)
• quantifiers (?, *, +, {n}, {n,m}, {n,})
• lazy quantifiers (??, *?, +?)
• assertions (\b, ^, $)
• groups (capturing and non-capturing (?:...))
• class refs (dot, bracket classes, unicode categories, shorthands)

Escape Handling

The parser accepts these escapes:

Inside bracket classes, unicode categories and shorthand classes are merged into the bracket class.

Range Quantifiers

Range quantifiers ({n}, {n,m}, {n,}) are handled by postfix expansion — the atom's postfix tokens are extracted and replicated. This keeps postfixtonfa unchanged. Tracking variables:

Expansion formula (postfix notation, Cat is the Catenation operator):

Nested quantifiers (e.g. a*{2}) are rejected as malformed. Expansion size is checked upfront against MaxPostfixSize.

Rejected Syntax

The following patterns are rejected as malformed:

• Bare ] or } outside their context.
• Empty character class [] or [^].
• Inverted ranges [z-a].
• Range quantifiers exceeding MaxRepetition.
• Unterminated constructs ([abc, a{, a\).
• Unknown/unsupported escapes.

Phase 2: Thompson's construction (postfixtonfa)

Walks the postfix runes left-to-right, maintaining a stack of Frag objects:

The postfix size is checked against MaxStates before construction begins. Stack underflow sets errorcode and returns the accept state as a safe sentinel.

Phase 3: Finalization

Two functions run after Thompson construction:

precomputeepsilonclosures(): For every state and for all 8 flag combinations (boundary × atstart × atend), computes the full epsilon closure and stores it in a flat array (closurecacheflat) indexed via an offset table (closurecacheoffsets). Also sets trivial_closure = true on any state whose closure is {self} for all 8 combinations. Total closure entries are bounded by MaxClosureCacheEntries. The epoch vector and counter used for cycle detection are local to this function.

finalizestates(): Populates asciiaccept[2] on each state: class-ref states copy the RuneClass's asciibitmap, literal states with label < 128 set their single bit, all others stay zero. Since ownedstates_ is already contiguous (pre-reserved vector<StateDef>), no copy or pointer remapping is needed.

Phase 4: Simulation (match, find_prefix)

Uses the standard Thompson NFA simulation with several fast paths:

1. start_list seeds the initial active set via epsilon closure.
2. For each input rune, step builds the next state set. The loop has two

branches: - ASCII fast path (rune < 128): for each active state, test the per-state asciiaccept bitmap. This single bit-test replaces the entire class-ref dispatch chain (isclassref → classrefindex → runeclasses[] → RuneClass::contains()). - Non-ASCII fallback: for each active state, dispatch via isclass_ref(label) + contains(rune) or literal equality.

1. Conditional epsilon states use booleans threaded through simulation:

- boundarymatch for \b - atstart for ^ - at_end for $

1. addstate() has a trivial-closure shortcut: if state->trivialclosure

is true, the state is added directly with dedup, bypassing the closure cache lookup entirely. Otherwise the flat closure cache is consulted.

1. Input decoding uses decode_rune() which has an ASCII fast path avoiding

the full utf8torune call for bytes < 128.

Conditional detection: detectconditionalstates() scans the NFA for WordBoundary, StartAnchor, or EndAnchor. When absent, simulation skips iswordchar() calls and passes constant false for all boundary/anchor parameters, providing separate code paths for conditional and non-conditional patterns.

Capture-aware simulation (addstatecapturing): Iterative (stack-based) epsilon traversal using capturetraversalstack in MatchContext. Pushes nextalt before next so next is popped first (greedy DFS ordering). Capture open/close transitions clone the capture frame and update one slot before continuing. The stack is reused across calls via MatchContext.

Epoch-based deduplication: For NFAs with > 128 states, MatchContext tracks per-state epochs in a visited-state vector. A per-context epoch counter increments before each step, and addstate skips states already marked in the current epoch. For NFAs with ≤ 128 states, a 128-bit bitset (visitedbits_[2]) is used instead for faster clear and test.

Error Handling

The engine uses an errorcode field (type ErrorCode) rather than exceptions or error tokens:

• Set during regexptopostfix_runes (invalid syntax, invalid escapes,

resource limits) or postfixtonfa (stack underflow, state limit).

• Once set, match() returns false immediately.
• Callers should check ok() after construction, or inspect error_code()

and error() for a human-readable message.

Performance Notes

Compile+match advantage

Trieste's NFA compile is much cheaper than RE2's DFA. On benchmarks, the compile+match ratio (cm_ratio) is ~0.31x (Trieste ~3x faster than RE2 overall). This makes the engine well-suited for single-use patterns.

Match-only gap

The match-only ratio (mratio) is ~2.6x. This is structural: RE2's DFA does O(1) work per rune after warmup, while NFA simulation is O(activestates) per rune. The gap is largest on patterns with many steps and high active state counts.

Key optimizations

• Per-state ASCII bitmap: ascii_accept[2] on StateDef unifies

class-ref and literal dispatch into a single bit-test for runes < 128. Eliminates the isclassref → classrefindex → runeclasses[] → contains() chain for the common case.

• RuneClass ASCII bitmap: ascii_bitmap[2] on RuneClass provides O(1)

membership test for runes < 128, avoiding binary search on ranges. Unicode category bitmaps are precomputed at compile time in unicode_data.h.

• Trivial-closure shortcut: States whose epsilon closure is always

{self} (literal, class-ref, Match states) skip the closure cache lookup in add_state().

• ASCII decoderune bypass: decoderune() returns immediately for

bytes < 128 without calling utf8torune.

• Bitset dedup: NFAs with ≤ 128 states use a 128-bit bitset for

visited-state tracking instead of epoch-based vector dedup.

• Flat closure cache: closurecacheflat + closurecacheoffsets

store precomputed epsilon closures in contiguous memory, indexed by (closure_index << 3) | flags.

• Pre-reserved contiguous storage: ownedstates is a

vector<StateDef> reserved upfront based on postfix size, so all states are contiguous in memory for cache-friendly simulation without a separate compaction pass.

• Iterative capturing traversal: addstatecapturing uses an explicit

stack (capturetraversalstack_ in MatchContext) instead of recursion, eliminating per-epsilon function-call overhead.

• Capture-frame arena: capture-aware simulation avoids per-thread vector

copies by storing capture slots in a contiguous arena.

• Non-capturing scratch reuse: match() and non-capturing

find_prefix() reuse MatchContext vectors to avoid per-call allocations.

• Optional stats: TRIESTEREGEXENGINEENABLESTATS gates counters

stored in MatchContext and exposed via MatchContext::stats().

unicode_data.h Extensions

Beyond the auto-generated Unicode 15.1 General Category range tables, unicode_data.h contains compile-time ASCII bitmap infrastructure:

• AsciiBitmap — struct with uint64_t words[2].
• computeasciibitmap<N>(ranges) — constexpr template that scans a

range table and produces an AsciiBitmap for runes 0–127.

• 36 inline constexpr AsciiBitmap constants (one per Unicode General

Category), precomputed at compile time.

• CategoryInfo struct extended with AsciiBitmap ascii_bitmap field.
• find_category() returns precomputed bitmaps alongside range data.

These precomputed bitmaps are used when constructing a RuneClass from a Unicode category, avoiding runtime bitmap computation.

Behavior Notes

• Empty pattern compiles to an accept-only NFA.
• find_prefix() can produce zero-length matches.
• Anchors are implemented in-engine (^, $) and do not require wrapper-only

emulation.

• The engine operates on UTF-8 codepoint decoding, but capture offsets are byte

offsets (matching existing parser/rewrite expectations).

Additional Syntax Coverage

Beyond the core iregexp-compatible pieces, parser support includes:

• Capturing and non-capturing groups: ( ... ), (?: ... ).
• Capture operators in postfix/NFA: CaptureGroup + i wraps fragments with

epsilon CaptureOpen + i and CaptureClose + i states.

• Lazy quantifiers: ??, *?, +? (implemented by swapped Split

branch preference in Thompson construction).

• POSIX classes inside brackets: [:alpha:], [:digit:], [:alnum:],

[:blank:], [:space:], [:xdigit:], [:upper:], [:lower:], [:print:], [:graph:], [:cntrl:], [:punct:], [:ascii:].

Conventions

• Namespace: trieste::regex for the engine; trieste::unicode for

category data.

• inline constexpr for namespace-scope rune constants and resource

limits.

• **StateDef*** aliased as State; owned by ownedstates (a

pre-reserved vector<StateDef>).

• Thread-safety model: Engine matching methods are const and engine state

is read-only after construction. Thread safety depends on context usage: sharing one MatchContext across threads is unsafe; using separate contexts per thread is safe.

• Header-only: The engine is regex_engine.h; category data is in

unicode_data.h (auto-generated from Unicode 15.1 UnicodeData.txt).

Modification Guidelines

When extending the regex engine:

1. New set-based matchers (e.g. new Unicode properties): Create a

RuneClass, store it via makeclassref(), and emit the class-ref in the postfix stream. No changes to StateDef or postfixtonfa needed. The ASCII bitmap will be computed automatically by normalize().

1. New operators: Assign a sentinel rune in the 0xAFFF00 range and update

parsing plus NFA construction.

1. New conditional epsilon states: Update both add_state and

addstatecapturing, and thread required context booleans through startlist/step/findprefix call paths. Update the 3-bit flag encoding in closure_flags() and increase the slot multiplier from 8.

1. Testing: Add test cases to test/regexenginetest.cc. Test positive

matches, negative matches, and malformed pattern rejection for any new error conditions. For assertions, include both full match and prefix/probe scenarios.

1. Benchmarking: Run test/regexenginebenchmark.cc to verify

performance impact. Compare cmratio and mratio against baseline. To produce a chart and markdown report from multiple benchmark passes, run: `` .venv/bin/python .github/skills/regex-engine/benchmark_chart.py ` This script runs the benchmark N times (default 5, with warmup), computes medians, and outputs a PNG chart + markdown report. Pass --input <json>` to re-render from previously saved data without re-running benchmarks.

1. Keep phases separate: Parsing (shunting-yard), construction (Thompson),

compaction (closures + arena), and simulation are cleanly separated. Changes should respect these boundaries.

1. Unicode data: If upgrading the Unicode version, regenerate

unicodedata.h from the new UnicodeData.txt. Remember to also update the computeascii_bitmap constants and CategoryInfo entries.