Regex Engine

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 (regexp_to_postfix_runes): Converts regex text to a postfix rune stream with explicit operators.
2. Thompson's construction (postfix_to_nfa): Walks the postfix sequence and builds an NFA from StateDef nodes using a fragment stack.
3. Finalization (precompute_epsilon_closures + finalize_states): Precomputes epsilon closures (with trivial-closure detection) and populates per-state ASCII acceptance bitmaps.
4. Parallel simulation (match / find_prefix): Tracks active NFA states using precomputed epsilon closures and per-call MatchContext state.

Headers

regex_engine.h includes both unicode_data.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 match_start, match_len, 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::rune_classes_. This allows StateDef to remain unchanged — a class-ref is just a label value that step() dispatches differently.

Helper functions: is_class_ref(label), class_ref_index(label).

Resource limits (RFC 9485 §8)

Utility Functions

decode_rune(utf8_str, pos)

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

Decodes one rune from utf8_str at byte offset pos. Returns {rune_value, bytes_consumed}. ASCII fast path: if the byte at pos is < 128, returns immediately without calling utf8_to_rune. Used by all simulation loops — callers must ensure pos < utf8_str.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<rune_t, rune_t>> of sorted intervals.
• ascii_bitmap[2] — uint64_t[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:

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

RuneClass objects are stored in a std::vector<RuneClass> rune_classes_ member on RegexEngine. make_class_ref(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> owned_states_. 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.
• ascii_accept[2] — uint64_t[2] per-state bitmap. Populated by finalize_states(): class-ref states copy their RuneClass's ascii_bitmap, literal states with label < 128 set the single corresponding bit, all others remain zero. Enables step() to bypass is_class_ref/class_ref_index/contains for ASCII runes.
• trivial_closure — bool, set by precompute_epsilon_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 owned_states_ with capacity 2 * postfix.size() + 1 to guarantee no reallocation during Thompson construction. This keeps raw State pointers (including Frag::dangling targets) stable.
• create_state() appends a StateDef to owned_states_ 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:

• noncapturing_current_states, noncapturing_next_states — scratch vectors for non-capturing simulation.
• visited_states — per-state epoch vector for dedup (used when > 128 states).
• visited_bits_[2] — uint64_t[2] bitset for dedup when ≤ 128 states (BitsetMaxStates). Faster than epoch-based dedup for small NFAs.
• use_bitset_ — chosen at bind_engine() time based on state_count.
• capture_frames — contiguous arena for capture slot storage.
• capture_traversal_stack_ — std::vector<std::pair<State, size_t>> reusable stack for iterative add_state_capturing.
• epoch_counter — monotonic counter for epoch-based dedup.
• Optional MatchStats (gated by TRIESTE_REGEX_ENGINE_ENABLE_STATS).

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 TRIESTE_REGEX_ENGINE_ENABLE_STATS):

• rune_steps — total input positions processed.
• active_states_total — cumulative active states across steps.
• max_active_states — peak active state count.
• class_ref_checks — 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 * num_captures_.
• 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 closure_cache_flat_.
• size — number of states in this closure.

Returned by epsilon_closure_cached().

Phase Details

Phase 1: Shunting-yard (regexp_to_postfix_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 postfix_to_nfa 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 (postfix_to_nfa)

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 error_code_ and returns the accept state as a safe sentinel.

Phase 3: Finalization

Two functions run after Thompson construction:

precompute_epsilon_closures(): For every state and for all 8 flag combinations (boundary × at_start × at_end), computes the full epsilon closure and stores it in a flat array (closure_cache_flat_) indexed via an offset table (closure_cache_offsets_). 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.

finalize_states(): Populates ascii_accept[2] on each state: class-ref states copy the RuneClass's ascii_bitmap, literal states with label < 128 set their single bit, all others stay zero. Since owned_states_ 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 ascii_accept bitmap. This single bit-test replaces the entire class-ref dispatch chain (is_class_ref → class_ref_index → rune_classes_[] → RuneClass::contains()).
   • Non-ASCII fallback: for each active state, dispatch via is_class_ref(label) + contains(rune) or literal equality.
3. Conditional epsilon states use booleans threaded through simulation:
   • boundary_match for \b
   • at_start for ^
   • at_end for $
4. add_state() has a trivial-closure shortcut: if state->trivial_closure is true, the state is added directly with dedup, bypassing the closure cache lookup entirely. Otherwise the flat closure cache is consulted.
5. Input decoding uses decode_rune() which has an ASCII fast path avoiding the full utf8_to_rune call for bytes < 128.

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

Capture-aware simulation (add_state_capturing): Iterative (stack-based) epsilon traversal using capture_traversal_stack_ in MatchContext. Pushes next_alt 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 add_state skips states already marked in the current epoch. For NFAs with ≤ 128 states, a 128-bit bitset (visited_bits_[2]) is used instead for faster clear and test.

Error Handling

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

• Set during regexp_to_postfix_runes (invalid syntax, invalid escapes, resource limits) or postfix_to_nfa (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 (m_ratio) is ~2.6x. This is structural: RE2's DFA does O(1) work per rune after warmup, while NFA simulation is O(active_states) 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 is_class_ref → class_ref_index → rune_classes_[] → 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 decode_rune bypass: decode_rune() returns immediately for bytes < 128 without calling utf8_to_rune.
• Bitset dedup: NFAs with ≤ 128 states use a 128-bit bitset for visited-state tracking instead of epoch-based vector dedup.
• Flat closure cache: closure_cache_flat_ + closure_cache_offsets_ store precomputed epsilon closures in contiguous memory, indexed by (closure_index << 3) | flags.
• Pre-reserved contiguous storage: owned_states_ 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: add_state_capturing uses an explicit stack (capture_traversal_stack_ 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: TRIESTE_REGEX_ENGINE_ENABLE_STATS 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].
• compute_ascii_bitmap<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 owned_states_ (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 make_class_ref(), and emit the class-ref in the postfix stream. No changes to StateDef or postfix_to_nfa needed. The ASCII bitmap will be computed automatically by normalize().
2. New operators: Assign a sentinel rune in the 0xAFFF00 range and update parsing plus NFA construction.
3. New conditional epsilon states: Update both add_state and add_state_capturing, and thread required context booleans through start_list/step/find_prefix call paths. Update the 3-bit flag encoding in closure_flags() and increase the slot multiplier from 8.
4. Testing: Add test cases to test/regex_engine_test.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.
5. Benchmarking: Run test/regex_engine_benchmark.cc to verify performance impact. Compare cm_ratio and m_ratio 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.
6. Keep phases separate: Parsing (shunting-yard), construction (Thompson), compaction (closures + arena), and simulation are cleanly separated. Changes should respect these boundaries.
7. Unicode data: If upgrading the Unicode version, regenerate unicode_data.h from the new UnicodeData.txt. Remember to also update the compute_ascii_bitmap constants and CategoryInfo entries.