Commentary: regex-engine

One NFA, two ways to walk it. The same 61 states and the same answer cost 13,631,486 steps one way and 841 the other — and the exponent turns out to live in two adjacent lines you could swap. A study guide for regex.py.

cd regex-engine
python3 demo.py           # the aha (§6) -- about 13s, most of it spent backtracking
python3 demo.py --timing  # adds wall-clock seconds (machine-dependent)
python3 test_regex.py     # 15 tests, ~22s; pins every number this page quotes

1. Orientation

This toy compiles a regular expression into an NFA — a little graph — and then matches by walking that graph. It walks it twice, two different ways, and counts every step.

There is only one graph. That is the thing to hold on to. The two matchers in regex.py are handed the identical object returned by compile_nfa. They are not two algorithms with different data structures; they are two traversal orders over the same 61 states. One of them takes 13,631,486 steps on a 20-character input. The other takes 841. They return the same answer.

By the end you should be able to:

• draw the NFA for a small regex from memory, because there are only three kinds of state and each operator adds a fixed number of them;
• say precisely what a backtracking engine is doing when it hangs, and why the hang is not caused by "backtracking" as such;
• predict which of the two engines wins on a pattern you have not seen — including the common case where the backtracking one wins;
• explain why RE2 and Rust's regex refuse to implement backreferences, and why that refusal is the same decision as the one in §5.6.

2. The problem this mechanism exists to solve

A regular expression is a specification, not a program. a?a?aa says "optionally an a, optionally an a, then two as" — it does not say what order to try things in. Something has to turn that specification into a sequence of decisions, and the honest difficulty is that the specification is ambiguous about work: for the input aa there are several ways to line the input up against the pattern, all of which are "the pattern matched."

An engine has to pick a strategy for exploring those ways, and the competing goals are real:

• Expressive power vs. a complexity guarantee. Backreferences ((a+)\1) and lookaround are genuinely useful, and nobody knows how to implement them without backtracking. Take them, and you give up any bound on running time. Refuse them, and you can promise linear time. RE2 and Rust's regex both refuse; Perl, Java, .NET and Python's re all accept. That is one decision, made two ways, and it explains most of the differences between engines you will ever meet.
• Best case vs. worst case. A backtracker is fast when it guesses right — it commits to one path and runs it to the end with almost no bookkeeping. A simulator carries a set of live states through every character whether it needs to or not. On ordinary patterns the backtracker's optimism pays (§6.4 measures it: it wins by about 1.5×). On adversarial patterns it loses by five orders of magnitude.
• Who supplies the pattern. If you write your own patterns and they are fine today, a backtracker is a perfectly good engineering choice. If a user supplies the pattern, or supplies the input a pattern runs against, the worst case is no longer hypothetical — it is an attack. Cloudflare took down its global HTTP serving for 27 minutes in July 2019 on one deployed regex containing .*(?:.*=.*).

This toy strips the problem to the point where the strategy is the only variable left. No captures, no ranking, no optimisation passes — just one graph and two ways to walk it, both counting.

3. Background you need

The two starred rows carry the result. Thompson's construction is why there is a graph to walk at all, and its one-entry/many-exits invariant is what keeps the compiler to three lines per operator. Epsilon closure is where the entire performance story lives: the closure's seen set is the difference between the two engines, and §6.5 shows that deleting it turns the simulator into the backtracker to the digit.

4. The mental model

A regex compiles to a graph with exactly three kinds of node:

a? becomes a SPLIT whose out enters the body and whose out1 skips it:

Chain three of those in front of aaa and you have pathological(3). Now the two ways to walk it. Take a?a?aa against "aa":

5. Reading the source

5.1 The step unit, declared in the module docstring

THE STEP UNIT
-------------
One step = one arrival at a (state, position) pair.

Both matchers tick that same counter on that same graph, so their numbers are
directly comparable. `add_state` ticks BEFORE consulting `seen`, so arrivals
the simulator discards are still charged to it: it is not allowed to look
cheap by declining to count. (An arrival is charged once. The simulator is
not separately charged for re-reading a state already in its live list; the
commentary, section 6, prices that alternative too.)

This is in the source rather than only on this page because a benchmark whose unit lives in the prose is a benchmark nobody can check. The headline of this toy is a ratio, and a ratio between two counters is worth exactly as much as the claim that they count the same thing. §6.2 and §6.5 are both attempts to break that claim.

5.2 add_concat — making concatenation visible

def add_concat(pattern):
    """Insert an explicit CONCAT token wherever juxtaposition means "then".

    A token boundary is a concatenation unless the left side is still open
    (`(`, `|`) or the right side is a closer or a postfix operator.
    """
    out = []
    previous = None
    for char in pattern:
        if previous is not None:
            if previous not in "(|" + CONCAT and char not in ")|*+?":
                out.append(CONCAT)
        out.append(char)
        previous = char
    return "".join(out)

Regex has an operator you cannot see. ab means "a then b", but the "then" is written as nothing at all, and a shunting-yard parser cannot shunt an operator that isn't in the input. So the first thing the toy does is insert one — CONCAT = "\x01", a character no realistic pattern contains.

The two membership tests are the whole rule, and they are asymmetric on purpose. The left side must not be open (( or | — nothing has been produced yet to concatenate to). The right side must not be a closer or a postfix operator (), |, *, +, ? — these attach to what precedes them rather than starting a new term). Everything else is a juxtaposition, and juxtaposition means concatenation.

5.3 compile_nfa — three lines per operator, and the reason it can be three

        elif token == "?":
            fragment = stack.pop()
            split = State(SPLIT)
            split.out = fragment.start
            # `out` points at the body and `out1` (the skip) is left dangling.
            # The backtracker tries `out` first, so THIS is where greed lives.
            stack.append(Fragment(split, fragment.dangling + [(split, "out1")]))
        elif token == "*":
            fragment = stack.pop()
            split = State(SPLIT)
            split.out = fragment.start
            patch(fragment.dangling, split)  # loop the body back to the split
            stack.append(Fragment(split, [(split, "out1")]))

Look at what these lines don't do: they never inspect fragment. ? doesn't care whether its body is one character or a 200-state sub-expression. That is bought by the Fragment invariant — one entry point, any number of dangling exits — and it is the reason Thompson's construction is a page of code instead of a chapter.

The dangling list holds (state, "out1") pairs rather than states, because an unfinished arrow has no target yet; it is a slot. Naming the slot lets patch fill it in later without the fragment remembering which kind of arrow it was.

? and * differ by exactly one line. ? passes the body's exits through (fragment.dangling + ...), so the body runs at most once. * patches them back to the split (patch(fragment.dangling, split)), so the body can run again. And + — three lines further down — is * with fragment.start instead of split as the entry point, which is precisely what "one or more" means: you arrive inside the body before you are ever offered the exit.

5.4 match_backtrack — nine lines, and one of them is the exponent

    steps = 0
    stack = [(start, 0)]
    while stack:
        state, pos = stack.pop()
        steps += 1
        if steps > budget:
            return GAVE_UP, steps
        if state.kind == MATCH:
            if pos == len(text):
                return True, steps
        elif state.kind == SPLIT:
            # LIFO: whichever is pushed second is explored first.
            first, second = (state.out, state.out1) if greedy else (state.out1, state.out)
            stack.append((second, pos))
            stack.append((first, pos))
        elif pos < len(text) and state.accepts(text[pos]):
            stack.append((state.out, pos + 1))
    return False, steps

The stack is explicit rather than recursive, for two reasons. It is more faithful — PCRE and friends keep their own backtrack stack rather than leaning on the C stack — and it makes budget the only thing that can stop this function. With recursion, (a*)*b raises RecursionError at whatever depth Python happens to allow, and the real failure mode (an unbounded search) gets disguised as an implementation detail of the host language.

budget is therefore not a testing convenience bolted on for the demo. It is load-bearing: without it this function does not terminate on a pattern whose NFA contains an epsilon cycle, and GAVE_UP is the honest third verdict. That is exactly the timeout a production engine reports, and §6.6 runs it.

The two stack.append lines are the subject of §6.3. Because a stack is LIFO, the one pushed second is explored first — so pushing second then first means first wins, and first is state.out, the body. greedy is a parameter only so the demo can price the identical match both ways. A real engine has no such freedom: once you report capture groups, greedy order is part of what * is defined to mean, not a tuning knob.

5.5 match_thompson — and the four characters that are the whole algorithm

    steps = 0

    def add_state(state, live, seen):
        """Walk the epsilon closure, appending CHAR/MATCH states to `live`."""
        nonlocal steps
        steps += 1  # charged before the `seen` check, on purpose
        if state.sid in seen:
            return
        seen.add(state.sid)
        if state.kind == SPLIT:
            add_state(state.out, live, seen)
            add_state(state.out1, live, seen)
        else:
            live.append(state)

    live, seen = [], set()
    add_state(start, live, seen)
    for char in text:
        following, seen = [], set()
        for state in live:
            if state.accepts(char):
                add_state(state.out, following, seen)
        live = following
        if not live:
            break  # nothing is live; no later character can revive anything
    return any(state.kind == MATCH for state in live), steps

Compare this to §5.4 and notice how much is the same. Both functions follow both arrows of a SPLIT. Both advance on a matching CHAR. Both start from start at position 0. The differences are two:

1. live is swept once per input character (breadth) instead of a stack being popped to exhaustion (depth);
2. seen — a fresh set per position — refuses an arrival at a state already reached at this position.

The second one is the algorithm. Everything else is presentation. §6.5 deletes it and gets the backtracker's step counts back, exactly.

seen is rebuilt per position (following, seen = [], set()) rather than kept for the whole match, and it has to be: a state that was live at position 3 may legitimately be live again at position 7. What is forbidden is being live twice at the same position, because a second arrival at the same (state, position) pair can only lead where the first one already went. That sentence is the entire proof of the linear bound.

5.6 The line that could have cheated

        steps += 1  # charged before the `seen` check, on purpose

One line above the if state.sid in seen: return. Move it one line down and the simulator stops paying for arrivals it rejects — which is arguably more "real," since a rejected arrival does almost no work. It would also take the headline from 841 to 651 (§6.2 runs it), improving a ratio this page is built on by 29%.

It stays where it is. When a toy's entire output is a comparison, the counter that flatters the side you are advocating is the one that has to be argued for, not the one that gets adopted quietly.

6. The demo, and what it proves

python3 demo.py, captured in full. It is byte-identical across runs — diffed two consecutive runs to confirm — because there is no clock, no RNG and no hashing anywhere in the counted path.

6.1 The headline, derived

Neither column is quoted here without arithmetic behind it. Both curves have closed forms, and test_the_closed_forms_reproduce_every_measured_row asserts them against every row above:

The shape is the point: 2ⁿ⁻¹ is the number of ways to distribute the input over the n optional a?s, and the linear factor is how deep each of those attempts runs before it fails. Exactly one of the 1,048,576 assignments works — the one where every a? declines — and greedy order proposes it last.

Where the 841 comes from, counted per position:

The initial epsilon closure charges 41 arrivals. Then each of the 20 characters charges (61 − 2k), shrinking by 2 per position as the a? chain is consumed and can no longer be re-entered. The sum is 20 · 61 − 2 · (1+2+…+20) = 1,220 − 420 = 800, plus the opening 41 = 841.

And the guarantee, visible as a number: 61 states × 21 positions = 1,281 is the ceiling the seen set imposes, and 841 sits under it. The backtracker respects no such ceiling; 13,631,486 is over ten thousand times the total number of (state, position) pairs that exist — a factor of 10,641, which it can only achieve by arriving at the same pair over and over.

The ratio: 13,631,486 ÷ 841 = 16,208.7×, on the same graph, for the same verdict.

6.2 The accounting disclosure

The headline is a ratio between two counters, so the counters deserve suspicion. Two ways to attack them, both run.

Charge the simulator more. The shipped meter charges one step per arrival but does not separately charge for re-reading a state already sitting in the live list during the character sweep. Charge that too:

841 becomes 1,261 and the ratio falls from 16,209× to 10,810×. Four orders of magnitude either way; the accounting choice is not what produces the result.

Charge the simulator less. Moving steps += 1 below the seen check (§5.6) goes the other way:

The toy ships the meter that makes its own headline smaller. Between 651 and 1,261 there is roughly a factor of two, and the result is the same at either end.

6.3 What the exponent is actually made of

This is the most surprising thing in the toy, and it is one line.

At n = 20: 13,631,486 → 41, a factor of 332,475, from swapping two adjacent stack.append calls. The engine is still a backtracker. It still walks depth-first, still commits to a path, still reconsiders. It is still right — test_branch_order_never_changes_an_answer checks all 762 (pattern, text) pairs over six patterns and finds no verdict changed.

The reason is visible in the arithmetic of §6.1: exactly one of the 2²⁰ assignments matches, the one where every a? declines, and greedy order puts it last in the enumeration. Skip-first order puts it first, so the walk goes straight down the correct path — 41 steps, which is 2 per character plus change.

So why not just ship skip-first? Because it is a different guess, not a better algorithm — and it is not even available to a real engine:

Identical to the digit. When there is no match, order cannot help, because every path has to be refuted before you can say "no". A reordering only ever moves which inputs are cheap; it never removes the exponent. And in a real engine the order isn't yours to choose at all: once * has to report what it captured, greedy is part of the definition, which is the point Cox makes about split instruction priority in the virtual-machine article in §10.

6.4 Boundary — the backtracker wins on ordinary patterns

The place where the whole effect vanishes, and then reverses:

a*b on 200 as and a b: 404 backtracking steps against 604 simulator steps. The simulator loses by 1.5×, and it loses for a good reason — it is paying to carry a set of live states through 201 positions when only one path was ever live. The backtracker's optimism is correct here: it guesses the greedy path, the greedy path is right, and it never reconsiders.

The last row is the degenerate case. aaaa… (40 literal as) compiles to a graph containing no SPLIT at all — only 40 CHAR states and a MATCH — so there is nothing to be clever about and both engines spend exactly 41 steps.

6.5 Boundary — the pattern is not what is pathological

Two more ways the effect disappears, both about the input rather than the pattern.

The same 61-state NFA that costs 13.6 million steps costs 41 on "baaaa…". One wrong character at position 0 refutes every branch before any branching has happened, so there is no tree to explore. Move that same wrong character to the end and the cost comes straight back (12,582,910) — the whole tree must be explored to reach the failure.

That is why "is this regex dangerous?" is not a question about the regex. a?ⁿaⁿ is perfectly cheap on almost all inputs. It is expensive on the inputs an attacker picks.

And here is the direct proof that the two engines really are one algorithm plus a set:

Delete four characters' worth of bookkeeping from add_state and the simulator produces the backtracker's step counts exactly — 13,631,486 at n = 20, not approximately, not in the same ballpark, identically. Whatever else is different between §5.4 and §5.5, it is not where the performance lives. The seen set is the algorithm.

6.6 The other failure mode: a cycle that consumes nothing

(a*)* puts a star around something that can match the empty string. The inner a* can complete without consuming input, the outer * loops back, and the NFA has a cycle of SPLITs with no CHAR on it. Depth-first search enters that cycle and never leaves — not "slowly", never. The budget is the only reason the first column terminates at all.

Look at the first row: the answer is True and it is trivially so, the input is a single b. The backtracker cannot report it, because it descends into the epsilon cycle before it ever considers the branch that would succeed. This is not an exponent; it is non-termination, and no budget size fixes it — test_the_budget_is_the_only_thing_that_stops_the_backtracker runs budgets of 10, 1,000 and 250,000 and gets GAVE_UP at exactly budget + 1 every time.

The simulator answers in 6 steps, and agrees with CPython's re. The seen set closes the cycle after one pass — the second arrival at a state it has already reached at this position is exactly the arrival that would have looped, and it is refused.

6.7 Wall clock, under a banner

Step counts are properties of an algorithm. Seconds are properties of a machine, so demo.py keeps them behind --timing and this page reports them only with the hardware named: macOS 26.5.2, Apple M1 Max (arm64), Python 3.15.0a8.

Two things worth noticing. First, the measured wall-clock ratio (16,115×) lands within 1% of the step-count ratio (16,209×) — which is the evidence that the step counter is measuring something real and not an artefact of where the ticks were placed. Across four runs the backtracker took 1.673 s, 1.673 s, 1.673 s and 1.688 s, while the ratio ranged from 15,699× to 17,266×. Note where that spread comes from: not from the backtracker, which is stable to under 1%, but from the simulator's 0.0001 s, which is close enough to timer resolution to be mostly noise. The seconds move; the step counts do not.

7. Design decisions and roads not taken

7.1 One graph, two walkers — instead of two independent engines

The obvious build is a backtracking matcher over the parse tree and a separate NFA simulator, which is how the two are usually presented. Rejected, because it would have made the headline unfalsifiable: two different data structures give you no way to argue that a "step" means the same thing on both sides. Sharing the graph turns the comparison into a controlled experiment, and it paid off directly — §6.5's result (delete seen, get the backtracker's exact counts) is only available to a design where both walkers see the same states.

7.2 A step budget instead of restricting the syntax

(a*)*b makes the backtracker non-terminating. The alternative was to declare nested nullable quantifiers out of subset and never build such a pattern. Rejected: it hides the more interesting of the two failure modes behind a syntax rule, and the budget is not a workaround — it is what production engines actually do. Python's re has no such guard and simply runs until it finishes; engines that must survive hostile patterns either add a match timeout or change algorithm, and Cloudflare's post-mortem chose the latter (§10). GAVE_UP is a faithful third verdict, not a testing convenience.

7.3 An explicit stack instead of recursion

Recursion is shorter and reads better. It also means (a*)*b dies of RecursionError at whatever depth Python allows, which would have made the demo's most interesting row look like a language limit rather than an algorithmic one. The explicit stack costs three lines and makes budget the single stopping condition.

7.4 Postfix instead of an AST

Thompson's construction is naturally a stack machine — pop the fragments an operator needs, push one back — so postfix makes compile_nfa one flat loop with no recursion. An AST would need a recursive walk to say the same thing. The cost is that error messages are poor and the empty alternative a| is unsupported (it pops a fragment that was never pushed); see §8.

7.5 No DFA, which is the famous absent third algorithm

The standard next move is to convert the NFA to a DFA, or better, to cache DFA states lazily as they are discovered — this is what makes grep and RE2 fast rather than merely bounded. It is left out because it changes the subject. The DFA's win is over Thompson simulation (it removes the per-character set manipulation); it has nothing to say about backtracking, which is what this toy is comparing. Adding it would double the code and give the reader three curves where the interesting story is between two. Cox's second article (§10) is where to go next.

7.6 No leftmost-first submatch semantics

The greedy parameter of §6.3 is only defensible because this toy has no capture groups. The moment an engine has to report what (a*) matched, the order it explores branches in becomes observable in the output, and greedy stops being a strategy and becomes part of the specification. This is the real reason production backtrackers cannot simply adopt the 41-step ordering — and it is also why Thompson simulation as written here cannot report captures at all. Pike's VM adds per-thread capture slots to fix that; it is the subject of §10's second Cox article.

8. What's simplified vs. the real thing

• No captures, and that is the big one. (a)(b) matches here but the engine cannot tell you that group 1 was a. Real engines carry a set of save-slots per thread (Pike's VM), which is what makes submatch extraction cost more than membership testing, and what makes POSIX leftmost-longest semantics genuinely hard. See §7.6.
• No backreferences, no lookaround — and this is a feature, not a shortcut. (a+)\1 is not a regular language and cannot be expressed as an NFA at all. Every engine that supports it must backtrack, which is precisely why RE2 and Rust's regex refuse to. This toy's subset is the subset that has a linear-time algorithm; the omission is the lesson.
• No character classes, anchors, or counted repetition. [a-z], ^, $, {2,5} are all missing. None would change the story — {2,5} is expanded to copies of the body in real implementations, which is exactly how a?a?a?… gets written by accident in production.
• Anchored fullmatch only. No search. A real engine finds a match anywhere by prefixing .*? or by restarting at each position, and the choice of how interacts badly with the exponent — an unanchored backtracking search over an n-character input is n restarts of the tree in §6.1.
• a| (empty alternative) is unsupported. compile_nfa raises IndexError: pop from empty list. CPython's re accepts it. A production parser has a real grammar with an explicit epsilon production; this one has a stack and an assert.
• No optimisation pass whatsoever. Real engines do literal-prefix extraction, memoization of (state, position) pairs — which, note, is precisely §6.5's seen set applied to a backtracker, and is how some engines get a polynomial bound without abandoning backtracking — and lazy DFA construction. The toy compiles what you wrote and runs it.
• Recursion in add_state. The epsilon closure is recursive, bounded by the state count. A 5,000-state pattern would overflow Python's stack where the backtracker (§7.3) would not. A production simulator uses an explicit worklist.
• One process, one match, no concurrency. No compiled-pattern cache, which is the first thing a real engine adds — CPython's re caches 512 compiled patterns (re._MAXCACHE), which is why re.fullmatch in a loop is not as catastrophic as it looks.

9. Check yourself

Answer before expanding. Each answer is derivable from the source, and each was verified by running it.

10. Further reading

Every link below was fetched and confirmed live when this was written.

• Russ Cox: Regular Expression Matching Can Be Simple And Fast (2007) — the article this toy is a hand-built replica of, and the one to read first. It uses the same a?ⁿaⁿ family, and reports that Perl "requires over sixty seconds to match a 29-character string" where the Thompson NFA "requires twenty microseconds" — a million-fold gap, which is §6.1's 16,209× carried out another nine characters. Cox's graphs are wall-clock where this page leads with steps; §6.7 is where the two meet.
• Russ Cox: Regular Expression Matching: the Virtual Machine Approach (2009) — the sequel, and the direct answer to §7.5 and §7.6. It recasts the NFA as bytecode (char, match, jmp, split), shows the backtracking and Thompson matchers as two schedulers over the same program — which is exactly this toy's one-graph-two-walkers design — and then adds save instructions to get capture groups. Its treatment of split priority is §6.3's swap, done properly.
• Wikipedia: Thompson's construction — the construction in §5.3, with the state-count bound (linear in the size of the expression) stated formally. Useful for checking that test_construction_produces_the_expected_graph's "3 states per n" is the general rule and not an accident of this pattern family.
• RE2 — the production answer. Written "with an explicit goal of being able to handle regular expressions from untrusted users without risk," guaranteeing "match time is linear in the length of the input string," and omitting backreferences and lookaround because they have only backtracking solutions. That is §8's omissions list, as a shipping product's design rationale.
• Rust's regex crate documentation — the same trade, stated as an API contract: "worst case O(m * n) time complexity." Read the untrusted-input section against question 5 above; its size_limit on compiled patterns is precisely the "not fixed" half of that answer.
• Cloudflare: Details of the Cloudflare outage on July 2, 2019 — §6.5 with the stakes attached. One deployed WAF rule containing .*(?:.*=.*) drove CPU to ~100% "on every CPU core that handles HTTP/HTTPS traffic on the Cloudflare network worldwide" for 27 minutes. The post-mortem's remedy is this page's §7: move to "either the re2 or Rust regex engine which both have run-time guarantees."
• OWASP: Regular expression Denial of Service (ReDoS) — the attacker's-eye view, with a catalogue of "evil regex" shapes ((a+)+$, ([a-zA-Z]+)*$, (a|aa)+$, (a|a?)+$) that generalises this toy's single family. Its worked example — ^(a+)+$ giving 16 paths on aaaaX and 65,536 on aaaaaaaaaaaaaaaaX, "double for each additional a" — is §6.1's 2ⁿ counted a different way.