regex

A from-scratch, linear-time regular-expression engine for cheatah — import regex.

The pattern compiles to a Thompson NFA and runs as a lazy DFA (the RE2 approach), so a match is O(n) in the input length with no backtracking. It cannot blow up on adversarial patterns the way std::regex (which hangs) and backtracking engines like Boost.Regex (which throws rather than hang) do. It is statically typed and never allocates an intermediate string: matching touches only your input bytes (as a string_view) and integer program-counters. find returns the matched bytes as an owned str (no borrow, nothing to dangle), plus offsets so you can slice your own input zero-copy instead if you prefer.

Using it from cheatah

Compile once, match many

compile is the expensive step; matching is cheap and reuses a warm DFA cache. Compile a pattern once and reuse it.

import io
import regex

let re = regex.compile("[0-9]+")

let text = "order 4567 shipped"
io.print(regex.search(re, text))          # True  — matches somewhere in `text`
io.print(regex.full_match(re, "4567"))    # True  — the WHOLE string is digits
io.print(regex.full_match(re, "x4567"))   # False — full match is anchored at both ends

find returns the leftmost-longest match: matched, the byte offsets begin/end, and text — an owned str. The library copies the matched bytes into text, so it is always safe to keep, pass around, or return; there is no borrowing and nothing can dangle (cheatah is C++ — somewhere we own the string, and here that owner is text itself).

let re   = regex.compile("[a-z]+@[a-z.]+")
let text = "contact bob@example.com now"
let m    = regex.find(re, text)
if m.matched {
    io.print(m.text)            # bob@example.com  — an owned str, safe to keep
    io.print(m.begin, m.end)    # 8 23             — byte offsets into your input
}

Even off a throwaway literal it is safe — m.text owns its bytes:

let m = regex.find(re, "contact bob@example.com now")
io.print(m.text)                # bob@example.com — fine; the copy outlives the temporary

Zero-copy when you want it. The matching engine itself never allocates an intermediate string; the only allocation on a hit is text's one copy. If you don't want even that, ignore text and slice your own (already-owned) input with the offsets — no copy at all:

let text = "contact bob@example.com now"
let m    = regex.find(re, text)
if m.matched {
    io.print(text[m.begin:m.end])   # bob@example.com — sliced from your own string
}

A worked example — pull every number out of a line

import io
import regex

fn main() {
    let re = regex.compile("[0-9]+")
    let line = "2026-07-02 id=48213 status=200 bytes=1274"
    let rest = line
    for _ in range(0, 10) {
        let m = regex.find(re, rest)
        if not m.matched { break }
        io.print("number:", m.text)    # an owned str — no copy needed, it already owns its bytes
        rest = rest[m.end:]            # advance past this match
    }
}

main()

Supported syntax

Backreferences and lookaround are intentionally unsupported — they are exactly the features that force backtracking and the exponential blow-ups this engine exists to avoid.

Performance

Four engines — cheatah, std::regex, Boost.Regex and Google RE2 — race the same programs over identical inputs in the standalone benchmark project stdlib/regex/bench/ (it fetches and builds all three rivals from pinned sources; nothing is ever linked into cheatah itself). Every timed case is output-verified across all engines first — the binary aborts if any engine disagrees on any benchmarked input — and a differential suite (rxdiff) additionally checks cheatah against RE2-as-oracle on thousands of generated inputs.

Representative medians below; the full table follows, and carries its own tally — a count restated in prose is a count that drifts the moment anyone re-measures, and this one already had. Pinned P-core, medians over interleaved repetitions. Boost's single win is compiling a 64-byte pure literal: analysis Boost skips and match time repays.

Two 16 MB literal scans — run_padded_literal_16M and sweep_16M — sit close enough to the 1.15× threshold that they change verdict between runs: one measurement had them losing to RE2 at 1.18× and 1.27×, the next had them at parity. They are memcmp-bound rather than automaton-bound, so the comparison is really between two prefilters doing almost identical work. RXBENCH_ASSERT=1 fails on any RE2 loss and will therefore go red on these occasionally; the response to that is to read the margin, not to widen the threshold.

| ReDoS (a|aa)+$, N=28 | 3.4 ns | — | — | 28.1 ns | 8.2× | | ReDoS at 16 MB (a|a)*c | 3.927 ms | — | — | 19.393 ms | 4.9× |

The complete comparison — every benchmarked case, all four engines

Tally — vs std: 64 faster / 0 parity / 0 slower; vs boost: 59 faster / 4 parity / 1 slower; vs re2: 68 faster / 15 parity / 0 slower.

cheatah ties or beats RE2 on every case.

Honest reading. RE2 is timed in its out-of-box configuration (UTF-8, leftmost-first) — the configuration real RE2 users get; offsets are cross-checked against RE2's longest-match + Latin-1 mode, which matches cheatah's documented leftmost-longest byte semantics. Rows where both engines sit at memory bandwidth (large absent scans that reduce to memchr) cannot separate meaningfully and score as parity — that is physics, not engine quality. On the pathological inputs, std::regex runs exponentially (seconds at N=28; unrunnable at 16 MB — those rows exclude it) and Boost aborts with a "complexity exceeded" exception; cheatah and RE2 both stay linear, and cheatah answers faster. Because it is a DFA, no input can ever make cheatah backtrack.

Reproduce:

cmake -S stdlib/regex/bench -B build/regexbench -DCMAKE_BUILD_TYPE=Release
cmake --build build/regexbench -j
./build/regexbench/rxdiff                       # differential tests vs RE2-as-oracle
taskset -c 4 env RXBENCH_ASSERT=1 RXBENCH_TABLE=/tmp/rxtable.md \
    ./build/regexbench/rxbench --benchmark_repetitions=7 \
    --benchmark_enable_random_interleaving=true \
    --benchmark_report_aggregates_only=true     # exit 0 = no case slower than RE2

(taskset pins to one performance core on hybrid CPUs; RXBENCH_ASSERT=1 makes the run fail if cheatah is slower than RE2 anywhere; RXBENCH_TABLE writes the full Markdown table.)

--benchmark_enable_random_interleaving matters more here than the repetition count. All four engines are registered per case, so without it cheatah's seven repetitions run as one block, then std::regex's, then Boost's, then RE2's — and any clock or thermal drift over that window lands on whichever engine ran last rather than cancelling out of the ratio. Interleaved, the repetitions of all four are scattered through the run, which is what makes a per-case rival / cheatah figure a property of the engines rather than of the ordering.

Design

• Lazy DFA over a Thompson NFA — linear time, no backtracking, ReDoS-proof.

• One load per byte. Transition entries store the next state's row byte-offset directly, so the hot loop's carried dependency is a single [table + state + byte*4] load; the accept flag lives in a 257th slot of each row and is tested off the critical path.

• Single-pass unanchored search. The compiled-in .*? prefix keeps every start position alive in one DFA state, so an absent pattern costs exactly one visit per byte — no per-candidate restarts, O(n) always.

• Reversed program for $. A pattern anchored only at the end runs backward from the end of the input: one pass answers existence and yields the leftmost begin, and a wrong tail dies in a handful of bytes.

• Acceleration armed in the start state. While no partial match is alive, the scan jumps: memchr for a single required first byte; for a required literal chain, memchr+verify that flips to a 32-wide branchless front+back block compare under a false-positive storm; a first-set LUT otherwise.

• Self-loop skipping. Bytes the start state maps back onto itself are learned into a LUT and skipped wholesale; and whenever any state maps a byte onto itself, the entire consecutive run of that byte is jumped with an 8-byte SWAR scan — long padding/whitespace runs cost almost nothing.

• find candidate budget. Leftmost-longest is decided per candidate start (with the same skip battery between candidates); on candidate-dense absent input, a budget triggers one O(n) existence pass instead of quadratic scanning.

• Value-semantic Pattern — shares a compiled program + reusable DFA cache (start states included), so copying is cheap and a warm pattern's search allocates nothing.

• Zero intermediate-string allocation — matching touches only the input bytes; find's only allocation is the one owned copy of the matched bytes (skippable via the offsets).