Skip to content

ARCHITECTURE.md

Latest commit

 

History

History
704 lines (622 loc) · 40.9 KB

ARCHITECTURE.md

File metadata and controls

704 lines (622 loc) · 40.9 KB
Raw

EmberRegex Architecture

Two public entry points, one shared front end:

  • Regex[pattern, flags] — a single pattern, matched with Python-style leftmost-first semantics (flags defaults to none; it is compiled as a leading inline group, Regex._pat).
  • RegexSet[patterns] — a multi-pattern database in the shape of Intel Hyperscan: scan once, report every pattern that matches and where.

Everything — parsing, NFA construction, determinization, table generation, engine selection — happens at compile time, inside comptime field initializers. An invalid pattern is a compile error, not a runtime exception, and the emitted binary contains the automaton as constant data.

Shared front end

pattern string
     │
     ▼
  parser.mojo      recursive descent; grammar is
     │             alternation > concat > quantified > atom.
     │             Extracts inline flags ((?i)(?m)(?s)(?x)), named groups,
     │             POSIX classes, (?# comments).
     ▼
   ast.mojo        flat pool of ASTNode + CharSet, indexed by integer
     │             rather than pointer (cache locality, and comptime-
     │             friendly — the interpreter handles Lists of PODs well).
     ▼
   nfa.mojo        Thompson's construction into NFAFragment values.
     │             Records the capability flags engine selection reads:
     │             can_use_dfa, has_lazy, start_anchor.
     ▼
 engine selection  (comptime if — see below)

Flag-dependent behaviour is baked into the states, never checked at runtime: (?m) picks BOL_MULTILINE over BOL, (?i) turns a literal into a two-member charset, (?s) turns . into a full-byte charset. \A and \z lower to plain BOL/EOL and deliberately skip the multiline promotion, which is the only difference between them and ^/$.

CharSet stores sorted non-overlapping ranges plus a 256-bit SIMD bitmap for O(1) byte membership. MatchResult stores a flat slots list — pairs of [start, end] byte offsets, one pair per group, group 0 being the whole match.

UTF-8 mode (utf8.mojo, unicode_tables.mojo)

Every engine here is byte-oriented — that is what makes the DFA tables and the SIMD kernels work at all. (?u) does not change that; it changes what the compiler emits. A codepoint range becomes an alternation of byte-range SEQUENCES, so [α-ω] is one automaton over bytes rather than a byte class that would happily match a lone continuation byte:

[α-ω]  ->  CE B1-BF        (U+03B1 .. U+03BF)
        |  CF 80-89        (U+03C0 .. U+03C9)

Two things make this affordable for the large Unicode classes:

  • The minimal byte automaton (_utf8_trie_fragment in nfa.mojo). One chain per sequence is the obvious construction and it does not scale: \p{L} is 836 sequences ≈ 3600 states behind an 836-way SPLIT chain, so every epsilon closure walks all 836 alternatives. The sequences arrive sorted, so a prefix trie is built by comparing each with its predecessor (at every depth two sequences' ranges are either equal or disjoint and ascending); trie nodes are then hash-consed children-first, merging equal suffixes — UTF-8 repeats itself in its tails, every final 80-BF is one node — which yields the minimal DFA of that acyclic language; and each node emits one multi-range CHARSET per distinct target. \p{L} is 968 states, \p{Ll} 246 (from 1465 with prefix factoring alone). A counted repeat multiplies the class, so this is also what brought (?u)\p{L}{8,13} from 8.5 minutes of compile time to about 2.5 (a from-source -I . build, 2026-09-25).
  • Surrogates are excluded. U+D800..U+DFFF are not Unicode scalar values and have no UTF-8 encoding, so utf8_ranges cuts the block out of any range that spans it (\p{Any}, \p{C}, . under DOTALL). Emitting them would build an automaton accepting ED A0 80 — ill-formed UTF-8.

Case folding. (?iu) is CPython's str-pattern IGNORECASE: a literal matches its whole case orbit (s/S/ſ, k/K/Kelvin sign, Cyrillic and Greek pairs), and a class is closed under orbits before any negation. The orbits are generated from CPython itself (_sre.unicode_tolower plus re._casefix) by tools/gen_case_tables.py into case_tables.mojo, and looked up at comptime through SIMD columns. Backreferences are the exception, as in Python: they compare by simple lowercase (backref_icase_unicode), so ſ does not repeat an s. Without (?u) only ASCII letters fold.

Property tables are generated from the UCD (tools/gen_unicode_tables.py → unicode_tables.mojo, Unicode 17.0) and checked in, so a build needs no Python. They cover every general category and 43 scripts. Everything comes from ONE source (the regex module): deriving categories from CPython's unicodedata and scripts from regex was tried first and is a trap — they are independent UCD copies on independent release cadences, and were 15.1.0 vs 17.0 here, disagreeing on 24 ranges of \p{L} alone. The generator cross-checks each major category against the union of its subcategories.

Big classes still cost real compile time (tens of seconds for \p{L}), because all the automaton construction is comptime work. Lookbehind is refused in UTF-8 mode: it needs a fixed byte width and a codepoint class spans 1-4.

Single-pattern engines (Regex)

Selected fastest-first at compile time:

Condition Engine File
pattern is a literal string SIMD literal scan simd_scan.mojo
prefix + .* + suffix sandwich (startswith/endswith) optimize.mojo
alternation of literals Teddy nibble shuffles teddy.mojo
DFA fits a shuffle tier (16/32/64 states on NEON, 16 on x86) Sheng sheng.mojo
can_use_dfa, ≤ EDFA_STATE_CAP eager comptime DFA (match()) static_dfa.mojo
same, search-family verbs leftmost-first DFA + reverse DFA static_lfdfa.mojo, static_rdfa.mojo
can_use_dfa, CLASSIC table over EDFA_STATE_CAP (or the attempt past EDFA_WORK_BUDGET member-class visits) lazy DFA for match(); its search verbs on the lazy leftmost-first DFA + lazy reverse DFA when the pattern has no anchors or lookaround dfa.mojo, lazy_lf.mojo
captures, one-pass NFA with an alternation loop one-pass DFA: match(), and the span confirm of the lane below (_use_onepass) onepass.mojo
captures, same shape, search-family verbs DFA-bounded span + backtracker on the span (_use_dfa_span) engine.mojo
backrefs / lookaround / captures (match(), not one-pass); also a greedy pattern whose classic table fits but whose leftmost-first table overflowed specialized backtracker backtrack.mojo
backtracker budget exhausted Pike VM executor.mojo
backreference pattern (unbudgeted) whose walk exhausts the stack bound heap-stack backtracker (heapbt_match) — the Pike VM has no BACKREF arm executor.mojo

The eager DFA is the interesting one. Subset construction runs in the comptime interpreter over the comptime NFA; byte equivalence classes bound the per-state work; the transition table and per-state flag bytes materialize as constant data. The runtime engine is a pure table walk with no lazy construction and no fallible path. Three structural passes run over the result, in this order: Hopcroft minimization merges states no input can tell apart (subset construction separates state sets, not languages, so cat|cot|cut|cit keeps four tails where one suffices); match states are then permuted to ids [0, num_match_states) so the per-byte match test is an integer compare; and states that self-loop on all but a few bytes are accelerated — the walker SIMD-scans to the next exit byte instead of stepping the table. Minimization comes first because the other two key off final state ids, and because a self-loop is often only visible once the duplicate states splitting it are merged.

The walker itself (_edfa_walk_from) steps a second, premultiplied copy of the table (edfa_pm_bytes, tables up to 128 states): each entry is its target's row as a byte offset in UInt16 (id << 9, EDFA_PM_DEAD for a dead transition), so a step is one register-offset load from row(byte) + state — the byte half is computed ahead from the input, and the state chain carries no shift-add (sherlock/quotes 287 → 244 µs; the same encoding took a third off the lazy walker below). Two more skips ride the same walk. A ladder (edfa_ladders) is a chain of at least LADDER_MIN (16) plain states that each move to the next on one byte class and leave it on the rest — the counting states of ["'][^"']{0,30}[?!.]["'] after the opening quote — and from rung i one SIMD class scan of the next L - i bytes finds the exit byte, or proves the run outlasts the chain, in place of up to L - i table steps (sherlock/quotes 206 → 159 µs). And acceleration is adaptive: a walk whose skips average under ACCEL_MIN_AVG bytes after ACCEL_PROBATION visits (prose, where the restart state of [a-zA-Z]+x exits on every letter) leaves for the plain loop, and a caller that walks again starts there; ladder scans keep their own tally. The two loops are one function body unrolled twice by a comptime for over the phase, not a call from one instantiation to the other (see Comptime realities: a compiler bug).

That table answers match() — Python's fullmatch, a language-membership question — and nothing else. Its states are sets, so a walk over it ends leftmost-longest, and Python's search is leftmost-first: a|ab on "ab" is a, <.*?> stops at the first >. The search-family verbs run a second table, regex-automata's construction: a state is a priority-ORDERED list of NFA states (DFS of the epsilon closure, a SPLIT's out1 before its out2), a transition whose closure reaches MATCH drops every lower-priority thread, and a restart bit re-adds the start closure as the lowest-priority threads after every byte — the unanchored scan, folded in the way the set lane folds its restart, and cleared by truncation so the walk terminates at the leftmost-first end. The walker is the same table walk in different start states; the same minimization, permutation, acceleration and Sheng masks apply, and the restart-only state self-loops on everything outside the first-byte set, so the acceleration scan is the candidate prefilter. Where the match starts is then recovered by a reverse DFA — the single-pattern form of the set lane's start-of-match automaton — walking leftward from the end, never below the previous match end. Two walks per match, both linear; the old lane's per-position anchored attempts were quadratic on [a-z]+x over a long class run, and its backtracker re-run for the leftmost-first end is gone from this lane.

The reverse walk is a second pass over every match, and on a short match it is most of the per-match cost, so the lane tries the first prefilter candidate anchored first whenever a cheap anchored engine exists for the shape: the classic table when its leftmost-longest end is provably the leftmost-first end (one greedy loop at most — [a-z]+x, .*x), the specialized backtracker for a lazy pattern whose loops are all simple (<.*?>: a byte compare and one SIMD class scan). A success is the match with its start known — no reverse walk; a failure proves nothing starts at that candidate and the unanchored scan takes over from the next one. The wasted walk is bounded by the scan's own walk over the same bytes (the scan keeps the failed attempt's threads alive, at top priority, until they die), so the lane stays linear; a.*?b over a 64 KB run with no b is 3.7 µs here against 2.3 s on the backtracker alone. One attempt per match, never one per candidate. Every materialized table holds its state ids in the narrowest integer type that fits them (edfa_id_dtype: Int8, Int16 or Int32 — the table is the walk's hot data) and is travels as a comptime string literal (static_bytes.mojo): a materialized Array global costs O(n²) in the MLIR→LLVM translation (one folded insertvalue per cell, ~6 s per 128-state table), while a !kgen.string lowers to one static c"..." global that the walkers read through a bitcast pointer — the same load, no per-call copy. EDFA_TABLE_MIN_BYTES (1 KB) still pads the element count.

With a candidate scanner, the leftmost-first walk also stops when it falls back to a bare restart state with nothing matched (Regex._lf_restart_stops) and resumes from the scanner's next candidate — Rust regex's prefilter at the start state. The scanner is a literal filter, or a first-byte class rare enough in text (LF_STOP_MAX_WEIGHT by the rank table: quotes and whitespace, not letters) that stopping beats walking on; a letter-led class re-entered the walk at every word and measured 3.4x slower.

A pattern with no start-anchored scanner may still carry a required inner literal — a byte run every match must contain, sitting after an unbounded loop where no prefix scanner can see it (\w+\.txt must contain ".txt", [a-z]+://[^ ]+ must contain "://"). extract_inner_literal (optimize.mojo) walks the NFA's mandatory spine at comptime — literal states extend a run, zero-width states keep it open, loops make the preceding gap unbounded, alternations contribute min/max over both arms — and keeps the rarest run of ≥ 2 bytes that is not at fixed offset 0 (the prefix scanners' territory). When the leftmost-first lane has no filter prefix and no Teddy prefix (Regex._use_rev_literal, Rust regex's ReverseSuffix/ReverseInner), _lf_next_match memmems the literal (simd_find_literal_rare, the same two-rarest-probe Muła kernel the filter-prefix scanner delegates to) before anything else: no occurrence at or after pos + min_offset is proof of no match — one SIMD pass answers the call (the reverse_suffix_search_64KB / reverse_inner_search_64KB rows measure ~40x on miss-heavy 64 KB) — and when the pre-literal gap is comptime-bounded ([ab]{0,3}foo: at most 3 bytes) the candidate pipeline starts at lit_pos - max_offset.

With an unbounded gap (or a bounded one, when safe) the lane walks leftward from each occurrence over a reverse DFA of the pattern's part before the literal (prefix_nfa → Regex._prdfa, Rust regex's ReverseInner), and confirms the start it finds with an anchored probe on the classic table. Two guards keep that linear. rev_inner_safe (Rust's has_no_earlier_match) admits a pattern only when an earlier match cannot use a later occurrence as its literal: some literal byte is one no prefix state consumes ([a-z]+://), or a separator class disjoint from the literal and the rest of the prefix sits right before the literal (\w+\s+Holmes) or starts the match (\s[a-zA-Z]{0,12}ing\s). And a later occurrence's reverse walk stops at the previous occurrence, its probe must start past the last failed probe's end (Rust's min_pre_start), and an inconclusive walk hands the call to the plain scan. A confirmed start is the match start: when the classic table's end is provably the leftmost-first end it is returned as is, otherwise one forward leftmost-first walk from the start finds the end — no reverse walk. The pivot prefilter may coexist; the literal test simply runs first.

A search also fails fast on a required byte — a byte every match contains — unless another scan already fails fast on it (the pure-literal scan, Teddy, the Teddy prefix, the pivot; a filter prefix only covers its own bytes, so (a|aa)+b still checks for b). Every CHAR state of that byte sits inside a forced chain of CHAR states, and the set of those chains is required too (extract_required_literals): for the AWS-key pattern that is ASIA|AKIA|AROA|AIDA rather than the A in every other line, checked with one Teddy scan. The upgrade is skipped for a single chain, and where the reverse-literal memmem runs anyway: a set scan over a miss would only repeat it.

Capture groups do not keep a pattern off these tables — SAVE states are epsilon to every determinizer — only backreferences and lookaround do. A capture pattern of the admitted shape runs its search-family verbs on the DFA-bounded capture lane (Regex._use_dfa_span, regex-automata's "Core" strategy): the same forward scan and reverse walk give the span, and the specialized backtracker then runs anchored at the start and pinned to end at the end (anchored_end + end_at, over the whole input so $ and \b see the real neighbours) to fill the slots. Its first success on that span is Python's capture assignment: the span is the leftmost-first match, every path before it in NFA priority order fails to reach MATCH at all, and the backtracker explores in that order — so the pinned walk costs what an unpinned walk from the start costs and never reaches the lower-priority assignments with the same span. The lane's miss path is the DFA scan alone (the backtracker-per-candidate lane re-ran (\w+)@(\w+)\.com from every word byte). On this lane the anchored-first attempt on the backtracker is made for every shape, not only lazy ones: a success carries the slots, so a true first candidate costs one backtracker pass — the old lane's cost — and only a false one pays the scan, the reverse walk and the confirm (without the attempt the short-input findall rows measured 1.2-1.7x). The lane's candidate comes from the literal/pivot prefilters or, failing those, a SIMD first-byte class scan. split and a replace without backreferences skip the fill. When the backtracker gives up on a span (budget or depth) the Pike VM runs on exactly that span with the same end pin, never on the whole input — and the walk latches: every later span of the same call goes straight to that VM, built once per walk, so a pattern whose confirm always gives up ((a*)*b) pays one budget per call, not one per match. match() with captures stays on the backtracker unless the pattern is one-pass (next paragraph).

One-pass DFA (onepass.mojo, Regex._use_onepass, regex-automata's onepass): when at most one NFA thread can consume each byte, the path through the NFA for any input is unique, and the capture slots can be written during a single forward table walk with no backtracking. A DFA state is one NFA state (a transition target) plus a position context (start / after \n / mid-line, split by the look-behind word class for \b patterns); expanding it walks the epsilon closure in priority order carrying the SAVE slots passed, and every consuming member contributes transitions tagged with those slot writes. The pattern is NOT one-pass when a later member wants a byte class an earlier one already claimed with a different target or slot set ((a|ab)(c|bcd), (a*)(a*), (a)\b|(a)), or when it carries a backreference or lookaround, or when the automaton exceeds ONEPASS_STATE_CAP (128) / 63 slots. Unlike regex-automata the closure does not stop at MATCH: match() is fullmatch (language membership: (a*?) must fullmatch "aaa") and the capture lane's span confirm already knows its end, so both walkers (onepass_match, pinned to a known [start, end)) run to the pin and require a match state there — the unique path's slot writes are then the only assignment. BOL kinds resolve against the context at build time, $ / (?m)$ / \b before a consuming state restrict its byte classes, and only the conditions on the byte after the end remain as per-state match flags checked once against the whole input.

The one-pass walk replaces the backtracker in exactly two places, both gated on _use_onepass: match() (the whole input), and the capture lane's span confirm (_span_fill_slots, over a span the forward/reverse DFAs already found — exact and O(span), so a one-pass pattern's search verbs never fall to the Pike VM on a pathological confirm). Selection is by SHAPE, not validity alone (onepass_shape): the walk costs ~1.8 ns per byte, so it is taken only where the backtracker is much slower — a general loop (a cyclic SPLIT the backtracker runs by recursion) whose body carries an ALTERNATION, where the backtracker re-tries an arm per character ((?:(x)|y)+, (?:(x)|(y)|z)+, (a|b)*c, (?:(ab)|(cd))+): 4-9x faster at every length, and no SBT_BUDGET / SBT_STACK_BUDGET cliff. A simple loop anywhere, or a general loop without a body alternation (((a)(b))+, (?:([a-z])(\d))+), keeps the backtracker, whose SIMD class runs and cheap short-body recursion win there. The build is its own comptime field, read only where _use_onepass can hold (a capture pattern of the alternation-loop shape), so simple shapes and capture-free patterns never pay for it.

Word boundaries ride all three tables. \b needs the byte on both sides, and a closure only knows the one behind it, so — regex-automata's approach — a DFA state carries the look-behind: the word class of the byte that led to it, recorded only while a word anchor is pending in the set (so \b-free tables are byte-identical to before). The anchor stays a pending member, like an EOL anchor; creating a state resolves it twice, for a word and for a non-word next byte, and the two resolved sets feed the word and the non-word byte classes of its transitions (the classes are cut at the [A-Za-z0-9_] edges when an anchor exists). A resolved continuation that reaches MATCH becomes a conditional match flag (EDFA_MATCH_IF_WORD / _NONWORD) the walker checks against the next byte before consuming it, exactly like EDFA_EOL_AT_NEWLINE; end of input counts as non-word. The mid-line start context splits the same way (start_other / start_other_word), and the reverse DFA mirrors it with the roles swapped: the byte just consumed is the look-ahead, the byte about to be consumed the look-behind, and the entry's liveness becomes RDFA_WB_LEFT_WORD / _NONWORD. The split restart states of the leftmost-first table no longer self-loop on prose (one takes word runs, the other non-word runs), so they are accelerated as a region: a set of flag-free states whose rows agree on every byte outside a sparse exit set — the walker scans to the next exit byte and lands in whichever member the last skipped byte selects. Engine selection is unchanged otherwise; a word anchor whose continuation reaches a BOL kind (\b^) stays off the lanes, as does the runtime lazy DFA, which does not model the anchor. Sets keep word-boundary patterns off their DFA lanes.

Lazy leftmost-first DFA (lazy_lf.mojo, Regex._use_lazy_lf). When the classic table overflows, match() keeps the lazy DFA of dfa.mojo, but the search verbs of an anchor- and lookaround-free pattern build the leftmost-first and reverse automata at runtime instead: the same ordered state lists, truncation and restart bit as the comptime table, interned in an open-addressing table, with transitions per byte class. A transition is stored as its target's row byte offset plus MATCH / START tag bits, so the walker's fast loop is one register-offset load and one unsigned compare per byte, four bytes at a time. On START (the bare restart state) the walk jumps to the next candidate unless those jumps average under LLF_JUMP_MIN_AVG bytes, when the tag is stripped. A single-class repeat ((?u)\p{L}{8,13}, single_class_repeat) skips the reverse walk entirely: every thread steps the same class in unison, so a byte that kills the oldest live thread kills them all and the oldest one's match truncates the rest — the match starts where the walk last left the bare restart state. A cache that stops paying raises, and the call re-runs on the Pike VM.

The specialized backtracker is comptime-specialized per NFA state: each _sbt_try_match[pattern, state_idx] instantiation (the NFA is re-derived inside via the memoized _build_static_nfa(pattern), so symbol names carry the pattern string rather than a printed NFA) handles exactly one state kind with all fields baked in. The body is a comptime if chain over the kind, so every branch belonging to the other kinds is eliminated — what survives is straight-line code for that state, with no runtime dispatch on kind and no field loads for branches that no longer exist. The leaf primitives (_sbt_bitmap_check, _sbt_check_anchor, case folding) are @always_inline, and the acyclic parts of the call graph are small and terminating, so chains inline aggressively.

What it is not is one flat function — _sbt_try_match carries no @always_inline, and could not honour one: a cyclic SPLIT reaches its own instantiation, which is unflattenable in principle. So the general-SPLIT branch is genuine recursion, and the engine carries two independent caps: SBT_BUDGET bounds total work, while SBT_STACK_BUDGET bounds the stack — budget alone does not, since (?:ab)+ recurses once per byte consumed and has overflowed the stack on a 50KB input. Exhausting either falls through to the Pike VM — except for a pattern with a backreference, which the Pike VM cannot execute (a thread's own captures decide the match, so threads cannot be merged by state): such a pattern runs unbudgeted, like Python and PCRE, and when its walk exhausts the stack bound it continues on heapbt_match (executor.mojo), the same leftmost-first walk over the materialized NFA with its frames on a heap List, so it is bounded by memory rather than by the thread's stack. An empty loop iteration ((a*)*) fails that path there, the ECMAScript rule the Pike VM's per-position dedup also yields. Both are gated at compile time on the pattern actually carrying a BACKREF, so no other pattern's binary elaborates them. The stack bound is measured in bytes, not calls: the walk reads the stack pointer at the checked frames and concedes when it drops below a floor taken at _sbt_run entry. A call count cannot do the job — the same frame measures ~120 B in a release build and 600-1500 B under -D ASSERT=all, a 12x spread, plus a further 2.4x between pattern shapes, so the 10,000-call cap this replaced was 1.2 MB in one build and 14.6 MB in the other (which is how (?:a|a{2,})+b on 2000 as came to SIGSEGV under the test flags).

The floor is the higher of two rules, and both are needed:

  • relative — sp - SBT_STACK_BUDGET (4 MiB, half the 8 MiB main-thread default) bounds what this walk may add;
  • absolute — stack_low + SBT_STACK_RESERVE (512 KiB) bounds where the thread's stack actually ends. stack_low comes from pthread_get_stackaddr_np / pthread_get_stacksize_np on macOS and pthread_getattr_np / pthread_attr_getstack on Linux. Without it the relative rule says nothing about what the caller already spent: a caller burning 64 KiB per level around a deep walk returned at 60 levels (~3.9 MiB) and SIGSEGV'd at 64, and a macOS secondary thread (512 KiB by default) never had 4 MiB to give.

Regex.__init__ asks for the thread's range once and caches it; the floor re-asks only when the current stack pointer falls outside the cached range (i.e. the Regex moved threads). Asking per _sbt_run instead measured 1.388x on static_nested_quantifier.

Residual assumptions. The reserve has to cover whatever nests between two checks, and the check sits in the general-SPLIT branch: one cycle of the call graph, measured at ~4.5 KiB, against a 512 KiB reserve. A pattern that nests hundreds of lookarounds between two cyclic splits would push past that — lookaround frames are real and are not check sites. Platforms other than macOS and Linux cannot be asked for their stack bounds and keep the relative rule alone.

Two cyclic shapes avoid the recursion altogether: a greedy or lazy SPLIT whose body is a single ANY/CHAR/CHARSET looping straight back becomes a while loop (is_simple_loop / is_simple_lazy), so a+, [a-z]* and .*? iterate. sbt_depth_plan computes whether anything is left that can still recurse without bound — a cycle in the specialized call graph, which models the simple-loop rewrites, so it is exact rather than an over-approximation of the NFA — and drops the whole guard (floor included) when there is none; measured 1.25-1.6x on recursion-heavy patterns when the check was applied unconditionally. The same pass verifies that the general-SPLIT states form a feedback vertex set of that graph, which is what licenses keeping the check in that one branch instead of on entry to every state.

A counted repetition over a single byte class gets the same treatment, one level up. nfa.mojo expands x{n,m} into n required copies plus either a star loop or m-n optional copies NESTED in ? SPLITs (x{2,4} → xx(x(x)?)?, every skip leaving through one shared exit, as Rust's compiler does) — right for the DFA lanes (one byte class determinizes to m+1 states, linear), ruinous for the backtracker, which pays a function instantiation and a stack frame per copy: a{1,2000} took ~12 minutes to compile. _sbt_counted_shape reads that chain back at compile time and the walker runs it as one bounded loop — consume up to hi, hand back down to lo with the same auto-possessification the simple loop uses, or extend up from lo when lazy. It is exact rather than merely equivalent because a single-class body with no capture inside makes every k-byte path through the chain the same path, which collapses the recursion's binary-order enumeration of the optional copies into a plain count order. Two whole populations are excluded: chains with hi == lo (already a run of tail calls, so there is no frame to save) and any NFA with a general cyclic SPLIT (its exit call is not in tail position, so collapsing free frames into real ones there deepens a walk that already recurses per byte — (?:a|a{2,3})+b on 2000 as went from completing to overflowing).

Search gets its own prefilters: literal prefixes drive a two-rarest-probe memmem (it switches to testing both probe bytes per chunk when the rarer one turns out common in the input, memchr's packed pair), an alternation of literals at the start drives a Teddy scan, required-byte and first-byte bitmaps drive shufti/truffle skips, and the [class]+ P … shape gets a pivot-anchored search that hops between occurrences of a rare byte. On the backtracker lane three more apply. A required literal at a bounded offset narrows the candidates to a window before each occurrence (_use_bt_window). A pattern led by \b and a word byte only tries word starts (_use_word_start). And after a failed attempt, a pattern led by a greedy single-class loop with no backreference skips the rest of that class run (_lead_loop_class): a later start in the run reaches the same run end and only a subset of the continuation positions the failed attempt tried. Teddy itself fingerprints the rarest byte offsets of its literals, not the first ones (in Cyrillic every other byte is a D0/D1 lead), and when every literal has one of ≤ 3 rare bytes at one offset it scans for those instead (Sherlock|Street: a memchr on S).

Two DFA-admission rules are worth knowing because they cut against the "no alternation, no suffix → backtracker" default. A word-boundary pattern whose every match is at least WB_DFA_MIN_LEN (8) bytes rides the leftmost-first lane (\b\w{12,}\b: the backtracker re-checked up to 12 bytes per word it started on), while \b\w+\b, a match per word, stays put. And an unanchored loop whose exit reaches $ / (?m)$ counts as having a suffix: (?m)\w+$ fails for every word that does not end a line, which the table decides in one pass.

Multi-pattern engines (RegexSet)

The contract

Report (id, end) for every position where some match of pattern id ends, regardless of where it started. Duplicates at the same (id, end) collapse; order is nondecreasing end, ties ascending id; unanchored by default. This is Hyperscan's reporting model, and it is what a single pass can actually deliver.

It is not re.finditer: ab|a on "ab" reports end 1 and end 2. Ground truth is therefore an O(n²) sweep (tools/set_oracle.py), not finditer — a trap that has bitten this project more than once.

The union NFA

set_nfa.mojo parses each pattern independently (so inline flags stay per-pattern), demotes captures, splices the fragments into one shared state pool under a SPLIT chain, and tags each MATCH with its report_id.

Backreferences and lookaround are widened here rather than rejected — see "Exact backrefs and lookaround" below.

The engine ladder

litset ──▶ ac ──▶ rose ──▶ mdfa ──▶ bitnfa ──▶ pike
Lane When File
litset every pattern is a plain literal set_literal.mojo
ac all literals, but more than LITSET_MAX of them set_ac.mojo
rose patterns carry required literal factors set_rose.mojo
mdfa general, determinizes within MDFA_STATE_CAP set_dfa.mojo
bitnfa determinization blew up, or EOL-consuming continuations set_bitnfa.mojo
pike word boundaries, or anything above failed set_pike.mojo

litset — bucketed Teddy. The candidate mask stays UInt8 but a bucket holds a list of literal ids, which is Hyperscan's trick for k > 8. No automaton at all, just shuffles.

ac — Aho-Corasick. Teddy unrolls verification per literal, so it stops at 64 patterns; past that a comptime trie over byte classes, with failure links resolved and output links folded into each state's report slice, walks the input one table lookup per byte and reports every literal ending at each position with no failure-link chasing. Build cost is linear in the total literal length — no determinization — and the root state is SIMD-accelerated to the next possible first byte. Caseless literals collapse their case pairs into single byte classes when nothing in the set needs the two bytes distinguished; otherwise the position expands into alternative trie paths, capped.

rose — literal decomposition, Hyperscan's real performance move. Each pattern is walked at comptime for a literal run that every match must contain at a fixed offset from the match start; all factors pool into one Teddy front end, and a per-pattern anchored DFA runs only at candidate positions. Patterns with no usable factor stay resident on the lane below, over their own union NFA, and the two report streams merge. Measured 10.2x over the multi-accept DFA on sparse 64KB input.

Between the two sits a candidate lookaround: the same comptime walk also records the byte classes the pattern's consuming chain requires up to ROSE_LOOK_BYTES positions on either side of the factor (conn=\d+ wants a digit after it; \d{2}:\d{2} WARN \w+ wants four fixed classes before and a \w after), and a Teddy hit whose neighbours disagree — or whose required neighbour falls off either end of the input — never reaches the confirm DFA. Classes wider than ROSE_LOOK_MAX_POP are dropped rather than checked, and dropping one does not hide the narrower ones behind it. Worth ~10% where the factor occurs without its context, neutral where it does not.

mdfa — determinizes .*?(P0|P1|…) with the unanchored start closure folded into every state, so the automaton never dies and never restarts. Each state carries a slice into a flat report pool. Acceleration applies under a hard rule: a state with any report slice is never accelerated, or a skip could jump over a reporting position.

bitnfa — LimEx-style bit-parallel NFA over Glushkov positions. Chain successors ride one global bit-shift; joins, loops and anchor crossings live in an exception table touched only when their bits fire. Construction is linear, which is why it is also the streaming engine.

pike — tagged all-match Pike VM. Permanent bottom rung, and the differential oracle every other lane is tested against.

Start-of-match (scan_som, scan_spans)

The forward lanes deliberately know nothing about where a match began — that is what lets them fold the restart into every state. set_reverse.mojo recovers it afterwards by walking a determinized reverse automaton leftward from each reported end:

forward:  state set = "which NFA states are about to consume input[p]"
reverse:  state set = "which NFA states could be ENTERED at position p"

Anchors mirror the forward design with the roles swapped: walking leftward the byte just consumed is input[p], so EOL resolves during the closure while BOL depends on the byte about to be consumed and defers to per-state slices. Word-boundary sets, which cannot ride a DFA at all, use a SOM-carrying Pike instead.

scan_spans filters that stream to per-id leftmost non-overlapping spans. It is leftmost-longest, not CPython's leftmost-first; they agree for greedy unambiguous patterns, which is most of them.

Streaming (SetStream)

set_stream.mojo. Runs on the bit-parallel NFA regardless of which lane block mode picks — LimEx construction is linear, so every set that can ride an automaton can also stream without paying determinization, and the measured per-byte cost is at parity with the multi-accept DFA.

Stream state is the automaton's own state plus a global offset. Sets whose reports can depend on the byte after the match ($, (?m)$) additionally hold one step, so a match ending on the final byte of a write is reported by the next write or by close() — Hyperscan documents the same caveat. Sets without such anchors pay no latency at all. scan_vectored falls straight out.

Semantic surface

set_semantics.mojo (SINGLEMATCH, QUIET, min_offset/max_offset/min_length, expression info) and set_combine.mojo (logical combinations with ! > & > | precedence). All of it is a filter over the report stream rather than a change to any engine, so the lanes stay exactly as fast for sets that use none of it, and the semantics are identical on every lane instead of needing five implementations.

Exact backrefs and lookaround — where this beats Hyperscan

Hyperscan rejects both constructs; its answers are HS_FLAG_PREFILTER (a superset you confirm yourself) or the separate Chimera library (Hyperscan + libpcre). emberregex already ships exact engines for both, so set_prefilter.mojo does the whole job in one library:

  1. Widen the pattern into a superset the set engines can run — drop lookaround (zero-width and purely restrictive, so dropping only admits more), and replace a backreference with a non-capturing copy of the referenced group's body (the captured text is always in that group's language).
  2. Confirm each candidate on the exact specialized backtracker, anchored at the superset's start-of-match and pinned to the candidate end. A backreference confirm is exact all the way down: it runs unbudgeted and, when the walk exhausts the stack bound, continues on the heap-stack backtracker (heapbt_match) with the same pin — the single-pattern lane's policy, since the Pike VM cannot execute a backreference. A lookaround-only confirm that exhausts its work budget keeps the candidate instead (a superset report, never a missing one).

The pin matters: the engine sees the whole input with an end_at target rather than a truncated slice, because truncating would hide the right-hand context a lookahead asserts about.

Comptime realities

Three constraints shape the code more than anything else:

  • Determinization cost is superlinear in the comptime interpreter. tools/compile_dashboard.py tracks it. Lanes that avoid determinization (litset, rose, bitnfa) are worth real throughput to reach.
  • Comptime parameter values are mangled into symbol names. A function carrying a baked database as a comptime parameter, that the inliner does not fold, emits a symbol containing the whole database — and the linker refuses names past a few MB. Every List field costs a fixed ~1 MB regardless of length; the same data as Array costs ~4 chars per element. Hence RoseView and ReverseView: POD scalars in the parameter, bulk data in separate Arrays.
  • Walkers that take a table as a comptime parameter are @always_inline for the same reason: out of line, _edfa_walk_from printed its 1 MB table into its own symbol name and the link failed. An inlined callee must not materialize a comptime value its caller also materializes, either (a Mojo 1.1.0 bug, reproduced in tools/repro_inline_materialize_lifetime.mojo): the two copies share one stack slot whose lifetime ends at the caller's last use, and the callee reads it anyway. The adaptive walker once handed off to its plain instantiation that way and read garbage flags under -D ASSERT=all.
  • Baked lanes hold zero per-instance state, so scan needs no mut self and no scratch object. Keeping the bit-parallel NFA as the always-builds fallback is partly what lets the API stay non-mutating and thread-safe.

Testing

Every engine is differentially tested against the tagged Pike reference across LCG-generated inputs at chunk-boundary-adjacent lengths, including bytes ≥ 0x80. Set semantics are ground-truthed against CPython via tools/set_oracle.py — sweep_ctx, a context-preserving sweep that is sound for anchors and lookaround where a naive region-bounded sweep is not. Streaming is checked by exhaustive block/stream equivalence over every 2- and 3-way chunk split.

Benches live in bench/bench.mojo (single pattern) and bench/bench_set.mojo (sets), each row pinned by a coverage test so a benchmark cannot silently time the no-match path.