liveBook · Manning

Backtracking

As explained in Secrets of the JavaScript Ninja, Third Edition

Regex backtracking is a matching strategy that revisits earlier choices to try alternative paths when later matching fails.

Why can a regex take far longer to reject a string than to accept one? The answer can be backtracking: when a later part of a pattern fails, the regex engine revisits an earlier choice and tries a different way to match. section 12.6.3

Giving a character back

Consider /[1-9][0-9]*\s+[a-z]+s/ against "27 dresses". The greedy [a-z]+ first consumes all of "dresses", leaving nothing for the final s. The engine gives back the last character: [a-z]+ now matches "dresse", and s matches the remaining character. section 12.6.3

A greedy + or * consumes as much as it can, but its first choice is not necessarily final. The engine can try shorter matches when a subsequent term fails. A long word with an s near its beginning may require many retries before this pattern finds its match; individual retries are cheap, but the number of possible choices matters. section 12.6.3

Listing 12.13 A regex with catastrophic backtracking
const rosterRegex = /^(?:\w+\s*)+$/; #A

console.assert( #B
  rosterRegex.test("Hattori Yoshi Fuma"), #B
  "A genuine roster is accepted instantly", #B
); #B

const attack = #C
  "I will erase your existence from this realm!"; #C
const start = performance.now(); #C
rosterRegex.test(attack); #C
const elapsed = performance.now() - start; #C
console.log(
  `Rejecting the attack string took ${elapsed.toFixed(0)}ms`,
);

The roster test uses /^(?:\w+\s*)+$/ and times its rejection of a nonmatching string. It demonstrates the performance danger: a pattern with exponentially many backtracking possibilities can spend a long time failing, blocking the JavaScript thread until those possibilities are exhausted. section 12.6.3 section 12.7

How Secrets of the JavaScript Ninja, Third Edition covers it

How deep it goes
Works through character-by-character retries and a timed catastrophic case, without specifying a particular engine implementation.
Examples
Uses a number-and-word pattern matching "27 dresses" and a timed roster regex rejecting an attack string.
What it assumes
Assumes basic regex pattern reading while explaining greedy choices and retries from a concrete match.
What you can do after
Diagnose/debug with it when a greedy regex matches unexpectedly or takes too long to reject input.
How it connects
Connects greedy quantifiers, regex state machines, catastrophic backtracking, and JavaScript thread blocking.

Also explained in

Compare how 9 books explain backtracking →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Secrets of the JavaScript Ninja, Third Edition. The section links point to the parts of the book it draws on.