Regular expressions are one of those tools we use without asking how they work. Then one day a pattern like (a+)+$ meets a long input, and a service hangs. That failure has a name, catastrophic backtracking, and it is not a law of nature. It comes from one way of implementing regexes. There is another way, older and based on automata, that runs in time linear in the input no matter what the pattern is.

Russ Cox described that approach in a well-known series of articles. regex-engine is my implementation of it in Rust, written from scratch: a parser, a Thompson NFA, a Pike VM and a lazy DFA. It does not backtrack, and its results are checked against the regex crate by differential testing. This post is about what I built and what it teaches.

What I built

The engine is a pipeline of four stages.

1. The parser (parser.rs) is a recursive descent parser that produces an AST. Every literal, class and escape becomes a sorted list of char ranges, so the later stages only ever see one kind of leaf.

2. The Thompson NFA (nfa.rs) compiles the AST into a small instruction set: Class (match one char in some ranges), Split (try two branches), Save (record a capture position), Look (the ^ and $ assertions) and Match. Split is ordered: the first branch has priority, and that is the whole difference between greedy and lazy quantifiers. Counted repetition like {2,5} is expanded into copies.

3. The Pike VM (pikevm.rs) simulates all the NFA threads in lockstep, one input character at a time, in priority order. Each thread carries its own copy of the capture slots. When a thread matches, the lower-priority threads are cut, which gives leftmost-first semantics, the same rule Perl-style engines follow. It is used for find, captures and find_iter.

4. The lazy DFA (dfa.rs) builds DFA states, each one a set of NFA states, on demand while scanning, and caches the transitions: 128-entry tables for ASCII plus a map for other characters. The search is unanchored (the NFA start state is re-added after each character), and $ assertions stay pending until the end of the input. The cache is flushed when it passes 4096 states, so memory stays bounded. It is used for is_match, and as a quick reject before running the Pike VM.

The syntax it supports: literals, . (any char but \n), classes [a-z], [^...], []a], [a-], the escapes \d \w \s \D \W \S with ASCII definitions, \n \t \r \f \v, escaped punctuation, the anchors ^ and $ (start and end of text), groups ( ) and (?: ), alternation |, the quantifiers * + ? {n} {n,} {n,m} and their lazy forms *? +? ?? {n,m}?.

How to use it

Add it to a Rust project as a git dependency:

cargo add --git https://github.com/AbdeldjalilChougui/regex-engine 

The API will look familiar if you have used the regex crate:

use regex_engine::Regex; let re = Regex::new(r"(\w+)@(\w+)\.(com|org)")?; assert!(re.is_match("mail bob@example.org")); // lazy DFA let caps = re.captures("mail bob@example.org").unwrap(); // Pike VM let m = re.find("x 12 345").map(|m| (m.start, m.end)); let all = re.find_iter("a@b.com c@d.org"); 

Note which engine answers which question. is_match only needs yes or no, so it goes to the DFA. captures needs group positions, which a DFA does not track, so it goes to the Pike VM.

The repository also has a tiny grep. Clone it and run:

git clone https://github.com/AbdeldjalilChougui/regex-engine cd regex-engine cargo run --release --bin rgrep -- [-o] '<pattern>' file... 

What I learned

Linear time comes from never going back. A backtracking engine tries one path through the pattern, and on failure rewinds the input and tries another. The Pike VM instead advances every possible path together and reads each input character once. The number of live threads is bounded by the size of the NFA, so the work per character is bounded too. Patterns that hang a backtracker are ordinary here.

Priority is the hard part, not matching. Deciding whether a string matches is easy with an NFA. Deciding which match to report, and which captures, is where the care goes. The order of the two branches of every Split, and the order in which threads are stepped, encode all of it.

A small compilation choice changes the captures. e* is compiled as a single loop, or as (e+)? when e can match the empty string. This is the same choice the regex crate makes, and the shape changes which captures a Pike VM reports. I did not find that by reading. The differential tests found it.

A DFA is a cache of the NFA simulation. Each DFA state is just "the set of NFA states I could be in". Building all of them ahead of time can blow up, so the lazy DFA builds only the ones the input actually reaches, and throws the cache away when it grows too large. That one idea explains why a DFA is fast and why it is still safe.

Differential testing is worth more than hand-written cases. tests/differential.rs generates random patterns (nested groups, alternations, every quantifier form, classes, escapes, anchors) and random haystacks. For each pair it checks is_match on both the DFA and the Pike VM, plus find, captures and find_iter, against the regex crate. When a case fails, examples/minimize.rs shrinks it to a minimal reproduction. That is how the (e+)? capture-priority issue was found.

cargo test # unit tests + differential (200 patterns in debug) cargo test --release --test differential # 4000 random patterns x 25 haystacks DIFF_PATTERNS=20000 cargo test --release --test differential 

Things to know

This is a learning project. The README lists the limits:

  • Missing syntax. No flags ((?i), (?m), (?s)), no \b, no Unicode classes (\p{..}), no named groups, no nested classes or class set operations.
  • ASCII classes. \d \w \s are ASCII-only, while regex defaults to Unicode. The differential tests use ASCII haystacks, where the two agree.
  • The DFA only answers is_match. Match positions come from the Pike VM, which is much slower than a real DFA-based search.
  • Regex is not Sync, because the DFA cache sits in a RefCell.

For real work, use the regex crate. It is the reference this project is tested against.

Why I built it

I wanted to understand why some regex engines can promise linear time and others cannot. Russ Cox's articles explain the theory clearly, and they are the right place to start. But the theory fits on a page, and the difficulty is in the details the page skips: capture groups, greedy versus lazy, empty matches, anchors inside an unanchored search. Writing the engine is how those details become concrete.

Having a mature engine to compare against made the project much more honest. Without the differential tests I would have a regex engine that passes the cases I thought of. With them, I have one that agrees with regex on thousands of random patterns, within the syntax both support.

Get the code

The source, the differential tests and the minimizer are on GitHub: https://github.com/AbdeldjalilChougui/regex-engine. It's MIT licensed. Issues and pull requests are welcome. Russ Cox's articles are at swtch.com/~rsc/regexp/.

Originally published at abdeldjalilchougui.biz.