Zero Mismatches Was the Bug

I wrote two regex engines from scratch, about 300 lines of JavaScript between them. One is a backtracker, the design behind the regexes in JavaScript, Python, Perl and PCRE. The other is a Thompson NFA, the design behind RE2, Go and Rust. They share a parser for a small subset: literals, ., character classes, * + ?, | and parentheses.

The speed difference is the famous part, and it showed up right on cue. What I actually learned came from the testing.

The famous part

Give (a+)+b a string of n a's and no b. There's no match, but a backtracker has to prove it by trying every way to split the a's between the inner and outer +. That's 2ⁿ ways. The NFA engine never picks a path. It walks all of them at once, keeping a set of the states it could be in, so its work is at most (states × length).

Steps are function calls for the backtracker and states visited for the NFA. V8 times are one run in Node; my NFA took under 0.1 ms on every row.

Five more a's make V8 thirty-two times slower. That's the bug class behind real outages, where one bad pattern meets one long input and a server pins its CPU.

A fuzzer that never failed

To check both engines, I wrote a differential fuzzer. It generates random patterns over the letters a and b, nested up to four levels, plus random short strings. Then it asks my two engines and JavaScript's own RegExp whether the whole string matches, and complains about any disagreement.

First run: 200,000 cases, zero mismatches.

That should have felt good. It didn't, because code I just wrote is never that right. So I tested the test: I planted eight bugs in the engines, one at a time, and reran the fuzzer against each. This is called mutation testing. If a planted bug survives, the tests can't see that kind of mistake.

Six of the eight were caught. Two survived:

• Deleting an end-of-input check in the NFA. It survived because the check was dead code. An earlier line already guaranteed it. Nervous code, not wrong code. I deleted it.
• Making * lazy instead of greedy. That's a real change in meaning, and the fuzzer couldn't see it at all.

The second one is the lesson. I was asking a yes/no question: does the whole string match? Greediness never changes that answer. It only changes which match you get. A whole dimension of regex behavior was invisible to my test, and "zero mismatches" was measuring that blind spot, not the code.

Asking a better question

So I changed what gets compared. Both engines now do what exec does: find the leftmost match and report where it starts and ends. Greedy and lazy give different ends, so the fuzzer can see them now.

For the NFA, that meant upgrading to a Pike VM. Its threads are kept in the order a backtracker would try them, each remembers where it started, and the first one to finish wins.

Rerun: out of 100,000 cases, the backtracker disagreed with JavaScript 405 times and the NFA 675 times. Here's the smallest:

/b(a*|b)?/.exec("bb")    JavaScript: "bb"    both mine: "b"

My engines reasoned like this: the ? tries its body first. The body is a*|b, its first choice is a*, and a* happily matches nothing. Done, the match is "b".

JavaScript has a rule I only half knew. When a ?, a *, or any repeat after the first of a + makes a pass that consumes nothing, that pass counts as a failure, and the engine backtracks to look for a pass that does consume something. Here, that means b, so the match is "bb". The spec says it in one line: if min is zero and the pass ended where it started, return failure. ? is just a repeat of zero or one, so the rule applies to it too.

I knew the rule for *, because without it (a*)* loops forever, and my backtracker already had it there. I hadn't applied it to ?, where there's no loop to protect, so it never occurred to me. A one-line fix.

Teaching the NFA to remember

The NFA was harder, and more interesting. A backtracker follows one path at a time, so "did this pass consume anything?" is just a comparison of two positions. The NFA's whole trick is that it forgets paths. It only tracks which states are live, and two paths that reach the same state get merged. But "this pass was empty" is a fact about the path, not the state.

The fix was to put a little path back. Each thread now carries a list of loops it has entered since it last consumed a character. Reaching the end of a loop's body while that loop is still on the list means the pass was empty, so that path dies. Consuming a character clears the list. Two threads only merge if they're in the same state and have the same list.

That costs something. The live set can grow by a factor of two for each level of loop nesting. That factor depends on the pattern, not the input, so the engine stays linear in the length of the string, which was the whole point.

A nice surprise from mutation testing: deleting that new check doesn't produce wrong answers. It makes the engine recurse forever, because every loop around the empty cycle adds the loop to the list again. The rule that makes the answers right is also what makes the walk finish.

After

700,000 random cases across five seeds, zero mismatches for both engines, and this time I believe it. I reran all eleven planted bugs against the final code. The lazy-* one that used to slip through now trips about one case in six.

One survived, and it's my favorite. Delete the line that merges NFA threads sitting in the same state, and every answer stays correct. What changes is the cost: on (a|aa)*c against 22 a's, the NFA's work goes from 159 steps to 1.3 million, growing about tenfold every five characters. Without the merge, the NFA is a backtracker in disguise, trying every path. Its answers are fine. A correctness fuzzer can't see speed, so this one needs a different kind of test: a step count that has to stay small on inputs like the ones in the table above.

The general lesson, which I'll forget and relearn: a test that has never failed hasn't told you anything yet. Before trusting a green run, break the code on purpose and watch it go red.

Try it

Both engines, live. Type a pattern (same small syntax: no anchors, captures, or \d-style shortcuts) and a subject. The chart runs both engines on every prefix of the subject and plots the work on a log scale. A straight line going up on a log scale means exponential.

The source is one file. Everything I left out (captures, anchors, lookaround, backreferences) is real work. Backreferences are the one an NFA can't do at all: matching "the same text as group 1" needs memory of the path, which is exactly what the NFA throws away. That's why backtracking engines are still everywhere.