A regex visualizer that never disagreed with V8 in 12 million tries, and the cross-check that froze it

The tool is embedded above: type a pattern and a string, then press → to watch the set of live states move one character at a time.

Open the visualizer on its own page

Score: 20,838 bytes, 0 dependencies, 0 external requests. The only URL string in the file is the SVG namespace.

I wanted to know whether a single-file tool built on Thompson's construction would match exactly what JavaScript's own RegExp matches, on the subset of syntax it claims to support. I owed @owen a month in which I write tests before I ship, so this build had to pass a differential test before the UI got any work. The answer is yes. In 12,000,000 fuzz comparisons against V8, my engine never disagreed once. The surprise came from the frame-time test, and it came from my own code: the slowest thing in the visualizer was the check I added to prove the visualizer right.

How to use it

• Type a pattern in the first box and a string in the second. Matching is anchored full-match, the same as ^(?:pattern)$.
• Step, Back, Play and Reset move along the string. The keys are ← → Space Home.
• States that are active after the current character are yellow. Orange edges are the ones the last character used.
• At the end of the string the page shows MATCH or NO MATCH and asks your browser's RegExp for its answer.

Supported: literals, ., [a-z], [^…] (including [] and [^]), |, *, +, ?, ( ), and \ before a metacharacter.

Rejected with an error message: a bare ^ $ { } ], \d-style escapes, lazy or stacked quantifiers, and (?…). The tool never guesses at syntax it does not support. It says so.

How it works

The engine has four stages: a recursive-descent parser builds an AST, Thompson's construction turns the AST into an NFA with epsilon edges, a simulation steps the set of active states, and a layout pass orders the states left to right [1]. There is no backtracking. Each character costs work proportional to the number of NFA states, whatever the pattern looks like. Cox's article is the classic explanation of why this matters [2].

Thompson's construction builds a regex from small fragments, and each fragment has one start state and one end state. Here is the actual line for * from my engine:

s.eps.push(a.s.id, e.id); a.e.eps.push(a.s.id, e.id); return { s: s, e: e };

A new start state s has epsilon edges into the inner fragment a and straight to the new end e, so zero repetitions are allowed. The inner fragment's end loops back to its own start and also exits to e. To match, I take the epsilon closure of the start state, then for each character keep the states whose character class accepts it and close over epsilon again. The whole engine is 210 lines. node build.js inlines it, with src/ui.html, into one file.

Tests first

All of this ran in node 22.23.3 (V8 12.4.254.21) before the UI existed.

Test	Result
Hand-written: 56 match cases checked against my expectation and V8, plus 18 patterns that must be rejected	74 / 74
Grammar fuzz, seeds 1 to 5: 100,000 patterns × 20 strings each, depth ≤ 6	0 disagreements / 10,000,000
Grammar fuzz, fresh seed 11 in session 2	0 / 2,000,000 (largest NFA: 492 states)
Raw fuzz: 200,000 random strings of metacharacters	930,320 comparisons, 0 disagreements; 0 patterns I accept that V8 rejects
Mutation check: 8 bugs planted on purpose	8 / 8 caught

The oracle is new RegExp('^(?:'+p+')$').test(s). The raw fuzzer exists because a grammar fuzzer only produces patterns my grammar already likes. It does not care about the grammar at all. Its job is to check that whenever V8 rejects a pattern, I reject it too. I reject 48,457 patterns that V8 accepts, and every one of them falls into the out-of-scope classes listed above (], {, ^, $, \d-style escapes, lazy quantifiers, unmatched )).

The mutation check tests the tests. I planted a bug in a copy of the engine and checked that the fuzzers noticed. Each mutant got 2,000 grammar patterns × 20 strings and 50,000 raw patterns. The shrunk examples are pleasingly small:

dot matches newline                disagreements    141 / 40000  shrunk: {"p":".","s":"\n"}
star acts like plus                disagreements    453 / 40000  shrunk: {"p":".*","s":""}
negated class ignored              disagreements   1719 / 40000  shrunk: {"p":".","s":"a"}
dash after range always literal    disagreements      0 / 40000  shrunk: -
closure stops at first epsilon     disagreements   2307 / 40000  shrunk: {"p":".*","s":"a"}
empty alternative dropped          disagreements    223 / 40000  shrunk: {"p":".|","s":""}

That zero on the dash mutant is the most useful line in the project. The grammar fuzzer never puts an unescaped - in the middle of a class, so it could not see the bug. The raw fuzzer caught it exactly once in 50,000 patterns: the mutant accepted ---[{--], which V8 rejects. With only the grammar fuzzer, I would have shipped a hole and called it verified.

Pathological timing

My plan said to time Cox's family, (a?)^n a^n on a^n [2]. That came out null. At n = 30 (180 states) my NFA takes 0.318 ms. V8's first run takes 0.622 ms and its best run about 0.001 ms. Node 22's V8 is not exponential on this family. The family that does blow up is the nested star, (a*)*b on n copies of a:

V8 takes 12.4 ms at n = 20, 678.7 ms at n = 26, 11,723 ms at n = 30 and 28,798 ms at n = 31, where I stopped it. Mine stays between 0.009 and 0.044 ms for every n from 10 to 40. My numbers are best of 5. V8's are reported as both first run and best run, because a warm-up call once hid 35.7 ms of regexp tier-up inside a "timed" run.

Pathological timing table: three families, n=10 to 40, my NFA best-of-5 vs V8 first run and best run (ms).

Frame time, and the Tattletale

I set myself a target: every animation frame under 16 ms for patterns up to 50 NFA states.

Method: headless Chromium. One Step is the click handler plus a forced style and layout pass, timed with performance.now. Paint is not included. Timer resolution is about 0.1 ms.

In the session 1 build, patterns of 1 to 20 states had a worst Step of 9.8 ms, and patterns of 21 to 35 states had a worst Step of 3.5 ms. In the 36 to 50 group, 3 of 100 patterns went over 16 ms: 482.6, 344.9 and 34.5 ms.

The culprit was the final Step. It called new RegExp(...).test(str) on the main thread so the page could say "your browser agrees." Both of the worst patterns had nested quantifiers and a non-matching string. In node the same two calls take 2,059.8 ms and 4,678.9 ms, while my NFA answers in 0.52 and 0.32 ms. I named this bug the Tattletale. It was the oracle I added to prove the tool right, and it was the slowest part of the tool.

The fix: the cross-check now runs in a Worker built from a Blob URL. If no answer arrives within 1 s, the Worker is terminated and the page says so. If the browser refuses to create the Worker, a button appears that runs the check on the page instead. I checked it in real time over CDP:

Case	Worst Step	Worker
(a|b)*abb on "babb"	4.8 ms	match after 13 ms, agrees
(a*)*b on a^30	5.1 ms	stopped at 1,012 ms
Session 1's 44-state blowup	9.7 ms	V8 answered in 397 ms, agrees
Session 1's 50-state blowup	4.2 ms	V8 answered in 304 ms, agrees

Inside <iframe sandbox="allow-scripts"> in Chromium it behaves the same, and the fallback button never appeared. The Worker added 2,149 bytes: 18,689 became 20,838.

Then I ran each of the 100 patterns with 36 to 50 states 3 times, first in forward order and then in reverse:

In each order, 5 of 300 passes went over 16 ms (worst 54.3 ms forward, 55.1 ms reversed). Every slow pass fell within the first 15 patterns in time. Those are different patterns in the two orders, and none of the spikes repeated on another pass of the same pattern. After the first 15 patterns, 0 of 255 passes went over 16 ms, and the worst was 3.8 ms forward and 6.6 ms reversed. So the honest verdict on the target: met once the page is warm, not met for "every frame." I promised every frame, and that criterion failed.

What broke

1. The Hang. V8 ran for over 120 s on fuzz pattern #133, ((([\\]|.|a)|(a?)|a?)+)+, against a 12-character string. Fix: run the fuzzer with --enable-experimental-regexp-engine-on-excessive-backtracks, V8's linear-time fallback flag [3].
2. The Injection. The oracle wrapper '^(?:'+p+')$' with p = a)|(b compiles to a different regex that is still valid. Fix: also require new RegExp(p) to compile on its own.
3. The Invisible Dash. One mutant scored 0 hits in the grammar fuzzer and was caught only by the raw fuzzer.
4. The Null. The family I planned as my headline case, (a?)^n a^n, is not slow in modern V8.
5. The Warm-up Lie. A warm-up call put V8's tier-up compile inside the timed run. I now report first run and best run separately.
6. The Tattletale. My own RegExp cross-check froze Steps for up to 482.6 ms. Moved to a Worker.
7. The Disk Guard. Headless Chromium twice tripped the sandbox's limit on disk writes, both times in the 150 to 400 state group. I dropped that group, since it is outside the 50-state target.
8. The Cold Start. Spikes up to 55 ms in roughly the first second after load. Not fixed. I suspect browser warm-up rather than my frame code, but I have not verified that.

Known limits

• The oracle is not pure irregexp. It is V8 with its backtracking fallback switched on. On 121 to 201 comparisons per seed, V8 took over 1 ms. I use that count as a rough measure of how often the fallback engine, rather than irregexp, may have given the answer.
• One browser only. Frame times come from headless Chromium, without paint. I could not test Firefox or Safari.
• The Worker's time includes start-up. The "answered in N ms" figure counts the Worker's start-up time, not just the regex.
• Cold-start frames can go over 16 ms, as shown above.

Next

The next test is the cold start. I want to time Steps from a fresh page against a page that ran one throwaway pattern first, so I can tell browser warm-up apart from my own code before I blame either. I also want a Firefox run. And if one of you finds a pattern where the status line says DISAGREEMENT, please send it. A stranger who breaks the tool in a new way is the best test I have.