Ambiguous

The pattern is not slow. ^(a+)+$ matches exactly the strings ^a+$ matches, and there is no sense in which one of those is a harder question than the other. What is slow is one particular way of answering it, and that way is the one shipped in V8, PCRE, Python’s re, Java’s Pattern and Ruby’s Onigmo.

Both panes here walk the same graph. The pattern is compiled once, by Thompson’s construction, into character nodes and epsilon splits — six nodes for ^(a+)+$. Both walks live in the same grid of (node, position) cells: six rows by n+2 columns, 132 cells at twenty characters. The top pane goes depth-first, greedy branch first, and backs up when it fails. The bottom pane goes left to right, carrying the whole set of live nodes at once. Nothing else differs. Not the graph, not the semantics, not the answer.

The two numbers

Every count below is cell entries — one step is one entry into one (node, position) cell, the same unit for both walks — on aⁿ followed by one character that makes the match impossible. These are not fits. They hold exactly, as integers, at all fifteen lengths from 6 to 20:

At twenty characters that is 5,242,877 against 82, a factor of 63,938. The email check in the fifth row is nine nodes rather than six and looks nothing like the toy in the first, and it costs the identical number of steps at every length tested — the shape of the ambiguity is the whole cost, and the rest of the pattern is decoration.

The growth is 2.000× per character, measured over twenty lengths, on all four of the exponential patterns. Not “about two”. Two.

Where the factor of two comes from, and it is not the engine

There are 2ⁿ⁻¹ ways to cut a run of n as into one or more non-empty pieces — 524,288 ways for twenty. Each of those is a distinct way for (a+)+ to have matched, and each has to be ruled out before the engine can say no. The backtracking count is 10·2ⁿ⁻¹ − 3: exactly ten cell entries per cut, every time.

That is the real definition of the bug. The pattern is ambiguous — more than one parse per string — and a backtracker’s job description is to try parses. A pattern with one parse per string has nothing to enumerate, which is why ^a+$ is 3n + 2 and why rewriting the pattern works at all. It is not that ^a+$ is “simpler”. It is that it is unambiguous.

The memo table and the live set are the same object

Turn on memo and the top pane stops glowing. Its cells go flat teal, its counter drops to 58, and the two panes become pixel-identical — because a memo over (node, position) and a set of live nodes per position are two names for the same table, and the grid on screen is it.

That is not an approximation. On every failing input tested — 175 pairs of pattern and length — memoised backtracking and the one-pass simulation report the same integer, not merely the same order of growth. The backtracker already had nowhere else to be: at twenty characters it visits 82 distinct cells, the same 82 the simulation visits, out of 132 in the grid. It just goes back to them five million times.

Why nobody notices until it is an outage

Switch the input to one that matches. At twenty characters, backtracking takes 46 steps and the simulation takes 83. The backtracker is cheaper — on all three exponential patterns — because it stops at the first parse that works while the simulation carries every live alternative to the end.

So the cost is only ever paid on a string that fails. Your tests pass. Your staging traffic is fine. The input that costs seconds is specifically the one your validator was written to reject, which is the one an attacker sends. The profile of this bug is: fast for everybody, forever, until someone types the wrong thing on purpose.

The same asymmetry decides what a budget buys. Ten million steps is 20 characters of backtracking on ^(a+)+$, or 2,499,999 characters of the one-pass walk. A request-size limit is not a defence; 20 is well under every limit anyone writes.

The guard, and where it stops helping

^(a*)*$ is the row that breaks the pattern of the table: 4n + 5 in both panes. The inner star can match nothing, so the outer one could loop at the same position forever, and the walk here refuses to enter a cell that is already on its current path. That one guard flattens this pattern completely.

V8 does not have it in that form. Measured in the same headless Chromium that took the screenshots, as a ratio of the engine’s own timings at 16 and 20 characters so a busy machine cancels out of the answer:

The guard is a per-path prune. The memo is the same prune applied globally, and globally is where the complexity class changes. Production engines stop at the first because the second is in tension with reporting capture groups, which is also the honest reason the whole industry still ships a backtracker: Thompson’s walk cannot do backreferences at all, and once you have promised backreferences you have promised the exponent.

Running it

• pattern picks the shape. length is how many repeated characters go in front of the tail.
• input: fails / matches flips the tail. This is the control that matters — the same pattern at the same length, one costing five million steps and the other forty-six.
• memo: on collapses the top pane into the bottom one.
• step / play runs both walks on one shared step clock, which is the point: the bottom pane finishes in the first second and then sits there holding the answer while the top one grinds. to end jumps to the finished picture (the event log only keeps the first 300,000 steps; past that, animating is pointless anyway).
• time V8 runs the platform’s own engine on the current pattern and length and blocks the page while it does. For the first row it also times ^a+$ for comparison. At length 20 that is the demo deliberately freezing itself.

The colour is log-scaled visit count on a shared ceiling, so the bottom pane’s flat teal is literally “one visit” and the top pane’s red is six orders of magnitude above it.

The code

src/ambiguous.mjs is framework-free and has no dependencies. compile(src) gives the NFA; backtrack(nfa, input, { memo }) and simulate(nfa, input) are the two walks, both returning a visits array over the grid, so anything that can draw a heatmap can draw this. stepSweep, reach, growth and nativeGrowth are the measurement helpers the numbers above came from.

The syntax subset is deliberate: literals, ., \w \d \s and their negations, [...] classes, groups, alternation, * + ? with lazy forms, and ^ $. No {m,n}, no lookaround, and no backreferences — which is the one feature that would make the fast walk impossible rather than merely inconvenient. Captures are not tracked, so these walks answer yes or no, not “what matched”.

The control

None of this means anything if the two walks are not actually computing the right answer. agreement() runs every pattern against the platform’s own RegExp on random strings over the relevant alphabet: 4,200 cases, three walks each, zero disagreements. The screenshot script (scripts/screenshot-demo.mjs) re-checks all 63 claims on this page against the module running in a real browser, and refuses to write the thumbnail if any of them has drifted.