How My Regex Tester Survives Catastrophic Backtracking

A name field on a form accepts “Mohamed Abdelrahman Elsayed Ibrahim” in an instant. Add an exclamation mark at the end and the same check takes about 24 seconds on my laptop. The pattern behind the field is ^(\w+\s?)*$, and it has a problem called catastrophic backtracking.

When I built ToolOnTap’s regex tester, this was the case I worried about most. A tester runs whatever pattern you type, on every keystroke, against whatever text you paste. If one of those runs takes 24 seconds on the main thread, the whole tab freezes with it. This article explains why that happens and how the tester stays usable anyway.

Why a regex can take minutes

JavaScript’s regex engine is a backtracking engine. When part of a pattern can match in more than one way, the engine picks one, carries on, and if the rest fails, it comes back and tries the next way.

Nested repetition changes that. Take the shortest version of the problem, ^(a+)+$, and the text aaaaaaaaaaaaaaaaaaaa!. The inner a+ can take any number of a’s, and the outer + can repeat it any number of times. So a run of 20 a’s can be split into groups in 2¹⁹ ways, which is 524,288: one group of 20, a group of 19 and a group of 1, and so on. The ! at the end means $ can never match, so the engine tries every split before it gives up.

Every extra a doubles the number of splits. That’s what I saw when I timed it in Node 20:

The last row is the important one. The pattern is fast when the text matches. It explodes only when the text almost matches, which is why this kind of bug passes tests and then shows up in production with one odd input.

The name-field pattern from the start has the same shape. \w+ repeats inside (…)*, and \s? is optional, so a word like “Abdelrahman” can be cut into pieces in many ways. A version that gives each part a distinct job, ^\w+(?:\s\w+)*$, rejects the same text with the ! in about 0.02 ms. Every space now has to be a real space between two words, so there’s only one way to read the text.

A regex can’t be stopped halfway

My first idea was to measure time inside the matching loop and give up after a limit. That doesn’t work. RegExp.prototype.exec is one synchronous call. Once it starts, no JavaScript runs on that thread until it returns, so no timer fires and no flag gets checked. There is no option to pass to the engine that limits its steps either.

What you can stop is a whole thread. A Web Worker runs its code on a separate thread, and the page can call terminate() on it at any time, even in the middle of a regex. The worker dies, the page carries on.

So the tester never runs your pattern on the page itself. The worker, workers/regex.worker.ts, is short. It builds the regex, finds the matches, runs the replacement if Replace is on, and posts everything back with how long it took:

ctx.onmessage = ({ data: job }) => {
  const built = buildRegex(job.pattern, job.flags)
  if (!built.ok) { ctx.postMessage({ id: job.id, ok: false, error: built.error }); return }
  const start = performance.now()
  const { matches, total } = findMatches(built.regex, job.text, job.limit)
  const replaced = job.replacement === null ? null : replaceText(built.regex, job.text, job.replacement)
  ctx.postMessage({ id: job.id, ok: true, matches, total, replaced, ms: performance.now() - start })
}

That ms value is the time you see next to the match count.

The 1.5 second limit

The other half lives in composables/useRegexRunner.ts. It sends each job to the worker and starts a timer next to it:

    clearTimeout(timer)
    timer = setTimeout(() => {
      if (id !== seq) return
      stop()
      reply.value = null
      status.value = 'timeout'
    }, TIME_LIMIT)
    worker.postMessage({ ...job, id })

TIME_LIMIT is 1500 milliseconds. If the worker answers in time, the timer is cleared and the results show. If not, stop() terminates the worker and the page says: “Stopped after 1.5 seconds: this pattern backtracks too much on this text. Look for nested repetition such as (a+)+ or overlapping alternatives.”

A few details took more thought than the timer itself:

• Every job has a number. seq goes up with each new job, and a reply whose id isn’t the latest one is ignored. Without it, a slow answer for the pattern you typed two keystrokes ago could replace the answer for the pattern you have now.
• A new keystroke kills a busy worker. If a job is still running when the next one arrives, the runner terminates the worker first. Waiting for a stuck job to finish would make every later keystroke wait too.
• The next job gets a fresh worker. After terminate() the worker is gone for good, so run() creates a new one the next time.
• The worker loads on first use. It’s imported with ?worker the first time you change something, so it ships as its own plain .js file and isn’t part of the page’s first download. The example you see when the page opens, a date pattern, is matched once during rendering, because it’s my own pattern and known to be fast.

Typing also waits 120 ms after your last keystroke before it sends a job, so typing a word doesn’t start and kill ten workers.

1.5 seconds is a judgment call. It’s long enough that a heavy but healthy pattern on a big log file finishes, and short enough that you don’t wonder whether the page has crashed.

Big inputs: limits on what comes back

A fast pattern can still produce too much output. \w with the g flag on a long document gives a match for every word. So the worker counts every match but keeps the details (position and groups) of the first 1,000 only. The table lists 200, and highlighting covers the first 50,000 characters of the text. The match count at the top is still the real total.

Reading a pattern in plain English

Stopping a slow pattern is half of the job. The other half is helping you see why it’s slow, and for that the tester explains the pattern piece by piece. The explainer in utils/regex.ts is a small hand-written scanner. It walks the pattern once, keeps track of how deep it is inside groups, and attaches each quantifier to the piece before it. For the pattern above it gives:

^ = Start of the text
(…)+ = Group 1 (captured), repeated one or more times, as many as possible
  a+ = The character a, one or more times, as many as possible
) = End of group
$ = End of the text

Seen this way, the problem is easy to spot. A line that says “one or more times” sits inside a group that is also “repeated one or more times”. That’s the shape to look for. The explainer doesn’t try to detect it automatically, because a nested quantifier is only dangerous when the inner and outer parts can match the same characters, and telling those cases apart reliably is much harder than spotting them by eye.

A few rules in the scanner exist because the regex syntax is less regular than it looks:

• A quantifier after plain text applies only to the last character, so abc? reads as “the text ab” then “the character c, optional”.
• A quantifier after ) repeats the whole group, so it’s shown on the group’s first line.
• \b means a word boundary outside square brackets and a backspace character inside them.
• ^ and $ read as “start of a line” and “end of a line” when the m flag is on.

What the tester can’t promise

The tester uses your browser’s own engine, so a pattern that passes here behaves the same in your front-end code and, with the same engine, in Node.js. The flip side is that a pattern can be fast in one engine and slow in another, and a time limit only protects the page. If your server runs the same pattern on user input, it has no such limit, and a single request can keep a thread busy. When the tester stops your pattern, treat it as a bug report for your code.

You can try all of this, including ^(a+)+$, in the regex tester. The other developer tools are on the developer tools page.