Start learning
Part 3/Regular Expressions

Catastrophic backtracking

Some regular expressions look harmless and pass every quick test you throw at them, then one day a particular input makes them run for seconds, minutes, or effectively forever. The engine pins a CPU core at 100% and nothing else gets a turn.

Most people who write regexes hit this eventually. The tell is distinctive: the pattern is correct, it works on your examples, and then one specific string sends it off a cliff.

In a browser, that string freezes the tab. The page stops responding to clicks, and after a while you get the “this page is slowing down your browser” prompt. On the server it’s worse — a single request can peg a Node.js process and stall everything sharing that event loop. This is a real denial-of-service vector (search for “ReDoS”), so it’s worth understanding what actually happens inside the engine.

A regexp that hangs

Say you have a string and you want to check that it’s a run of words — pattern:\w+ — each optionally followed by a single space, pattern:\s?.

The natural way to build it: take “a word plus an optional space”, pattern:\w+\s?, and repeat that group zero or more times with pattern:*. Anchor it at both ends so the whole line has to match:

That gives pattern:^(\w+\s?)*$ — start of line, then any number of “word + optional space” chunks, then end of line.

let regexp = /^(\w+\s?)*$/;

alert( regexp.test("A neat little line") );    // true
alert( regexp.test("Broken: %^&*") );          // false

Looks right. The results are correct. But feed it the wrong string and the engine chews on it long enough to lock up:

let regexp = /^(\w+\s?)*$/;
let str = "Each queued request here stalls the whole event loop!";

// this can take an extremely long time
alert( regexp.test(str) );

Run that and you’ll likely see nothing at all — JavaScript just stops. Events stop firing, the UI freezes (most browsers still let you scroll, and little else), and eventually you’re offered a reload.

To be fair, not every engine falls over here. Some have optimizations that sidestep the problem: V8 from version 8.8 onward handles this particular case, so Chrome 88+ doesn’t hang on it, while Firefox at the time of writing does. You can’t rely on the engine to save you, so let’s see why it happens.

Stripping it down

Why does the engine grind on that string? The full pattern has a couple of moving parts, so let’s cut it down to the essence.

First drop the optional space pattern:\s?, leaving pattern:^(\w+)*$. Then swap pattern:\w for pattern:\d — same behavior, easier to reason about with digits. It still hangs:

let regexp = /^(\d+)*$/;

let str = "012345678901234567890123456789z";

// still extremely slow — careful
alert( regexp.test(str) );

Now, pattern:(\d+)* should look odd to you. The outer pattern:* seems pointless — if you want a number, pattern:\d+ already matches one. And you’re right, this exact pattern is artificial; we got here by simplifying. But the reason it’s slow is the same reason the word version is slow, so once this clicks, the original will too.

Let’s trace pattern:^(\d+)*$ against subject:123456789z. I shortened the digits and there’s a non-digit subject:z on the end — that z is the whole point, because it’s what forces the match to eventually fail.

Here’s the engine’s play-by-play.

Step 1. The engine enters the group and runs pattern:\d+. The pattern:+ is greedy, so it grabs every digit it can:

\d+.......
(123456789)z

All nine digits are consumed, so pattern:\d+ has matched match:123456789. Now the outer pattern:* wants another repetition, but there are no digits left, so it stops with one repetition. Next in the pattern is pattern:$, the end of string. But the engine is sitting on subject:z, not the end. No match:

           X
\d+........$
(123456789)z

Step 2. A dead end means backtrack. The greedy pattern:+ gives back one character, so now pattern:\d+ holds only match:12345678:

\d+.......
(12345678)9z

Step 3. From just after match:12345678, the outer pattern:* gets another go. It runs pattern:\d+ again and matches the leftover match:9:

\d+.......\d+
(12345678)(9)z

Then pattern:$ is tried again, and again it hits subject:z. Still no match:

             X
\d+.......\d+
(12345678)(9)z

Step 4. No match, keep backtracking. The rule is mechanical: the last greedy quantifier shrinks until it hits its minimum, then the one before it shrinks, and so on — every combination gets tried. A few of the many:

First number 7 digits, second number 2 digits:

             X
\d+......\d+
(1234567)(89)z

First number 7 digits, then two 1-digit numbers:

               X
\d+......\d+\d+
(1234567)(8)(9)z

First number 6 digits, then a 3-digit number:

             X
\d+.......\d+
(123456)(789)z

First number 6 digits, then two numbers:

               X
\d+.....\d+ \d+
(123456)(78)(9)z

…and on, and on.

123456789
12345678
9
1234567
89
1234567
8
9
…and every other way to break the run apart
One digit run, many ways to slice it. Every partition of 123456789 into groups is a separate path the engine explores before giving up.

There are a lot of ways to split 123456789 into consecutive numbers. Precisely 2n-1 of them, where n is the length of the run.

  • 123456789 has n=9, so 28 = 256 splittings.
  • At n=20, that’s 219 ≈ half a million.
  • At n=30, over half a billion.

Every split is one path the engine walks before it can conclude “no match”. The work doubles with each extra digit. That’s the whole disaster.

Rather than actually hang your browser, the widget below simulates the backtracker for pattern:^(\d+)*$ and counts how many partial paths it walks before giving up. Drag the slider to add digits and watch the greedy count double with each one (it bails out at two million so the tab survives). Then flip to “Atomic guard” — the same input, but the run is grabbed once and never given back, so the path count barely moves.

interactiveCount the paths: greedy vs. atomic

Back to the words

The word version, pattern:^(\w+\s?)*$ on subject:Every queued request hangs!, blows up for the same reason. A word can be swallowed by one pattern:\w+ or chopped across several:

(request)
(reques)(t)
(reque)(s)(t)
(req)(u)(est)
...

You can see at a glance that the string can’t match — it ends in !, and the pattern wants a word character pattern:\w or a space pattern:\s there. The engine can’t see that. It doggedly tries every way pattern:(\w+\s?)* might carve up the text, including variants with the optional space present, pattern:(\w+\s)*, and absent, pattern:(\w+)*. Since the space is optional and words can be split, the number of combinations explodes just like the digits did.

So what do you do about it?

Maybe switch to lazy matching? It doesn’t help. Replace pattern:\w+ with the lazy pattern:\w+? and the regexp still hangs. Lazy changes the order the combinations are tried, not how many there are. You’re rearranging deck chairs.

Some engines carry optimizations — finite-automaton conversions, heuristics — that dodge the full search. Most don’t, and even the ones that do don’t cover every case. Don’t count on it.

Fix one: remove the ambiguity

There are two solid approaches. The first is to cut down the number of possible splits at the source.

Make the space mandatory instead of optional. Rewrite the pattern as pattern:^(\w+\s)*\w*$ — any number of “word then space” chunks with pattern:(\w+\s)*, then one optional trailing word pattern:\w* (the last word has no space after it). Same set of matching strings, no hang:

let regexp = /^(\w+\s)*\w*$/;
let str = "Each queued request here stalls the whole event loop!";

alert( regexp.test(str) ); // false, and instant

Why did the blow-up vanish? Because the ambiguity did.

In the old pattern, dropping the optional space turns the group into pattern:(\w+)*, and that lets a single word be split many ways. subject:request could be two repetitions:

\w+  \w+
(req)(uest)

The new group is pattern:(\w+\s)* — word followed by a required space. subject:request can’t be two repetitions of pattern:\w+\s, because there’s no space between req and uest. The mandatory space acts as a fence: there’s exactly one way to break the text into word-space chunks, so the engine never explores that combinatorial forest.

Fix two: forbid backtracking

Rewriting isn’t always easy. Here it was a small edit, but for a gnarly pattern it’s often not obvious how to restructure it, and the rewrite tends to come out longer and harder to read. Regexes are dense enough already.

The other approach attacks the mechanism directly: stop the quantifier from backtracking at all.

The root cause is that the engine keeps retrying splits that no human would consider. In pattern:(\d+)*$, once pattern:\d+ has eaten the whole digit run, giving those digits back is pointless — splitting one number into two adjacent numbers matches the exact same text:

\d+........
(123456789)!

\d+...\d+....
(1234)(56789)!

Same characters covered, no new possibilities. So pattern:+ here should never backtrack. Likewise in pattern:^(\w+\s?)*$, we want pattern:\w+ to grab a full word at maximum length and refuse to shrink or split it.

Most modern regex flavors express this with possessive quantifiers: add a pattern:+ after a quantifier and it becomes possessive, matching as much as it can and then never giving any back. You’d write pattern:\d++ instead of pattern:\d+. There are also atomic groups, pattern:(?>...), which lock in whatever’s matched inside the parentheses.

The catch: JavaScript’s regex engine has never supported either. No possessive quantifiers, no atomic groups.

Greedy \d+

grab all digits
dead end?
give one back, retry
give one back, retry
… (many paths)

Possessive \d++

grab all digits
dead end?
fail immediately
(never gives anything back)
— not in JS —

Greedy backtracks and retries; possessive/atomic locks the match and moves on. JavaScript lacks the syntax, so we rebuild the behavior with lookahead.

You can emulate atomic behavior, though, with a lookahead trick.

Lookahead to the rescue

We want a quantifier like pattern:+ that won’t backtrack, because backtracking here is wasted effort. The pattern that grabs the longest pattern:\w+ at the current spot and holds onto it is:

(?=(\w+))\1

Any sub-pattern works in place of pattern:\w+. Let’s take it apart:

  • The lookahead pattern:(?=...) peeks forward from the current position and finds the longest pattern:\w+ it can, without consuming anything.
  • A lookahead doesn’t capture what it saw, so we wrap the pattern:\w+ in its own parentheses. Now the engine memorizes that matched word as group 1.
  • Then pattern:\1 — a backreference to group 1 — actually consumes exactly that whole word.

Read it as: look ahead, grab the entire word into group 1, then step over that exact word with pattern:\1. Because the lookahead captured the whole word at once, pattern:\1 matches all of it as an indivisible unit. There’s no per-character retry left to do — that’s precisely the possessive behavior we wanted.

Here’s the difference in the open. pattern:\w+ in a normal match will happily backtrack to let the rest of the pattern fit; the lookahead version won’t:

alert( "keyboard".match(/\w+board/) );        // keyboard
alert( "keyboard".match(/(?=(\w+))\1board/) ); // null
  1. In the first pattern, pattern:\w+ greedily takes all of subject:keyboard, then backtracks character by character until pattern:board can match the tail — so it settles on pattern:\w+ = match:key, and the whole thing matches.
  2. In the second, pattern:(?=(\w+)) locks subject:keyboard into group 1 and pattern:\1 consumes it whole. Nothing is left over for pattern:board, so there’s no way to complete the match. Result: null.

Type different words below and watch the two patterns disagree. Anything ending in subject:board — subject:keyboard, subject:clipboard, subject:surfboard — matches the greedy pattern (it backtracks to free up the suffix) but returns null for the guarded one (the whole word is swallowed atomically).

interactiveGreedy \w+ backtracks; the lookahead guard doesn't
/\w+board/  → backtracks, matches
key
board
✓ match
/(?=(\w+))\1board/  → no give-back, fails
keyboard
board → nothing left
✗ null
Normal \w+ backtracks to free up 'board'. The lookahead grabs the whole word into \1 with no give-back, so 'board' has nothing left to match.

Drop any pattern you like into pattern:(?=(\w+))\1 when you need to make the pattern:+ after it stop backtracking.

Now the original word-matcher, rebuilt with the lookahead guard:

let regexp = /^((?=(\w+))\2\s?)*$/;

alert( regexp.test("A neat little line") ); // true

let str = "Each queued request here stalls the whole event loop!";

alert( regexp.test(str) ); // false — and it returns instantly

Note it’s pattern:\2 here, not pattern:\1, because the outer group pattern:(...) wrapping the whole repeated chunk is group 1, and the inner pattern:(\w+) is group 2. Counting parentheses to keep backreferences straight is error-prone, so give the group a name — pattern:(?<word>\w+) — and reference it by name with pattern:\k<word>:

// group named ?<word>, referenced as \k<word>
let regexp = /^((?=(?<word>\w+))\k<word>\s?)*$/;

let str = "Each queued request here stalls the whole event loop!";

alert( regexp.test(str) );                 // false
alert( regexp.test("A clean short line") );  // true

Both fixes are safe to run for real — try them. The box starts with the very string that hangs the naive pattern; feed either fix any line you like and it answers instantly, because neither one has a combinatorial forest to explore.

interactiveBoth fixes stay instant — even on the nasty input

The failure mode in this article has a name: catastrophic backtracking. When you see a regexp with nested quantifiers over overlapping character sets — pattern:(\w+)*, pattern:(a+)+, pattern:(.*)* and friends — treat it as a warning sign.