How Zeetah works: a fast regex meta engine for Zig
Most regex libraries run every pattern on one matcher. Zeetah is a meta engine: when you compile a pattern it analyzes it and picks the cheapest matcher that is still correct. A plain word becomes a SIMD substring search, a typical pattern becomes a linear-time DFA, and only patterns that truly need it (backreferences, lookaround) use a backtracker, which runs under a step budget. You call one API, and the engine picks the machine.
From pattern to matcher
Compiling a pattern runs a short pipeline. Every stage is plain Zig with no dependencies, and the same code runs at run time
(Regex.compile) and at compile time (zeetah.Pattern).
- ParseA recursive-descent parser turns the pattern straight into HIR, a flat high-level IR. There is no separate lexer or AST.
- AnalyzeA pure pass over the HIR finds literal prefixes and suffixes, anchors, a required byte, and whether the pattern is regular at all.
- PlanThe planner picks a strategy from that analysis alone. It never looks at the text being searched, which is why it can also run at compile time.
- BuildA Thompson NFA is built and turned into a DFA (subset construction plus minimization), or into one of the specialized executors.
- MatchPrefilters skip text that cannot match; the chosen executor finds the match; capture groups are filled in afterwards, only over the matched span.
Choosing an engine
Zeetah has fifteen executors. The tester's status line shows which one your pattern got; these are the main ones.
| Engine | Chosen for | How it runs |
|---|---|---|
literal | plain text or a small set of words, including case-insensitive ones (cat|dog) | SIMD substring or Teddy multi-literal search, no automaton |
lit_prefix | a pattern that starts with a literal (hello.*world) | find the prefix with SIMD, confirm with a DFA |
reverse_suffix | a rare literal at the end and a weak start | no suffix in the text proves there is no match; otherwise a DFA |
dfa | the general regular case | one table lookup per byte, linear time |
lazy_dfa | DFAs too big to build up front, and assertions such as \b, \B and mid-pattern ^/$ | the same DFA, built state by state while matching |
dense_search | narrow unanchored shapes | a single pass over the input with no restarts |
class_span | one repeated class: [a-z]+, \d{2,}, \b\w+\b | 64-byte bitmask scan (see SIMD) |
class_seq | fixed-length class sequences: \d{2}:\d{2}:\d{2} | Shift-And over bitmasks |
boundary_lits | keyword lists: \b(?:if|else|while)\b | multi-literal or word-hash search plus an O(1) \b check |
literal_alt | a dictionary too large for an automaton | a byte-budgeted trie walk |
dup_word | repeated words: \b(\w+)\s+\1\b | a dedicated linear scan |
dfa_edge_look | a regular body with a one-byte lookaround at the end (\w+(?=!)) | DFA with the lookaround folded in |
backtrack | backreferences, lookaround, atomic groups | step-budgeted backtracker behind a regular prefilter |
split_alt | alternations mixing both kinds | regular branches on a DFA, the rest on the backtracker |
bt_look | \Z and line-anchored (?m)^ patterns | line-by-line DFA, or a bounded backtracker |
Try it: in the tester, [0-9]+ runs on class_span, [0-9]{2}:[0-9]{2} on
class_seq, zeetah with the i flag on literal, and \b(\w+)\s+\1\b on
backtrack.
Skipping work with prefilters
Before any automaton runs, Zeetah tries to rule text out cheaply:
- Required byte. If every match must contain a certain byte and one
memchrfinds none, the answer is "no match" without running the pattern at all. - Required literal. A rare mandatory substring is located first, and the match start is recovered from it.
- First-byte set. The set of bytes a match can start with, scanned with vector instructions.
- Teddy and Aho-Corasick. SIMD and automaton based search for several literals at once.
- Seek. For backtracking patterns, a regular over-approximation of the pattern runs as a fast DFA to skip positions where no match can start.
Prefilters may let through false candidates, which the real matcher then rejects, but they never skip a real match.
SIMD inside
Several executors treat the input as 64-byte blocks and work on all 64 bytes at once:
- Character-class runs (
class_span). Each block is classified into a 64-bit mask, one bit per byte ("is this byte in the class?"). Run starts aremask & ~(mask << 1); count-trailing-zeros jumps to the next one and popcount counts them, so[a-z]+never walks byte by byte. This technique is inspired by Validark's accelerated Zig tokenizer. - Fixed-length sequences (
class_seq). Each class gets its own mask; shifting and ANDing the masks marks every position where the whole sequence ends, for all 64 positions in a few instructions. - Keyword sets (
boundary_lits). Word runs are walked off the same bitmask, rejected by length and first and last byte with two bit tests, and only then hash-checked. - Teddy. Nibble lookup tables find candidate positions for up to eight literals at once; case-insensitive literals are folded into the tables rather than lowercased.
On ARM these use NEON (ld4, tbl) and on x86 SSSE3/AVX2 (pshufb). The WebAssembly
build in the tester uses portable SIMD128 vectors.
Linear time and the ReDoS contract
Catastrophic backtracking (ReDoS) is when a pattern like (a+)+$ takes exponential time on input such as
aaaa…X. Zeetah avoids it by construction:
- Regular patterns are linear. They compile to a DFA, one table lookup per byte.
(a+)+$,(a*)*$and(.*)*$compile and run in linear time; they are not rejected. If a DFA would be too big, Zeetah builds it lazily instead of falling back to backtracking. - Backtracking is bounded. Only backreferences, lookaround and atomic groups need a backtracker. It runs under a
step budget proportional to the input and a recursion limit, and returns
error.MatchBudgetExceededinstead of hanging. - Compilation is bounded. Patterns too large to build fail with
error.PatternTooComplexat compile time.
Compile time and run time
Because planning never reads the input, the whole pipeline can run inside the Zig compiler.
zeetah.Pattern("…", .{}) parses, plans and builds the matcher at comptime and stores the finished
DFA (or literal scanner, or backtracker) in the binary's read-only data. The result is a type with static methods: no
allocator, no deinit, no compile step at run time. It supports the same syntax as the runtime
Regex; anything it cannot build is a compile error.
Match semantics
- Leftmost-first, like Perl, PCRE, RE2 and Rust: the first alternative that matches wins, and every engine agrees on the same match. Randomized differential tests pin the engines to each other.
- Byte-oriented. The engine works on bytes:
.matches one byte,\w\d\bare ASCII and\p{…}covers the Latin-1 range. A codepoint-aware Unicode mode is reserved as a future opt-in flag. - Captures on demand.
findreturns only the match span.capturesthen re-runs a small engine over just that span to fill in the groups, so captures never cost a second pass over the whole text.