liveBook · Manning

Greedy matching

As explained in Secrets of the JavaScript Ninja, Third Edition

Greedy repetition consumes as many consecutive characters satisfying its term as possible while still allowing the overall match.

When a regular expression contains a repetition operator, how much should that operator consume? By default, it is greedy: it first takes as many consecutive matching characters as it can. That choice is tentative, because later terms in the pattern must still match. section 12.2.2 section 12.6.3

Two adjacent bracketed strings

Against `<Ninjas><Unite!>`, `/<.*>/` matches the entire string: `.*` continues past the first `>`. Append `?` to the repetition operator to make it nongreedy. `/<.*?>/` matches only `<Ninjas>`, consuming just enough to reach a match. section 12.2.2

Greedy does not mean the first choice is final. For `/[1-9][0-9]*\s+[a-z]+s/` against `27 dresses`, `[a-z]+` initially consumes `dresses`. The final `s` then has nothing left to match, so the engine backtracks one character: `[a-z]+` keeps `dresse`, and `s` matches the last character. On a longer word whose only `s` occurs early, the engine must give back characters repeatedly before it can resolve the match. 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`,
);

This timed JavaScript example contrasts a quickly accepted string with an input that is slow to reject under a pattern with repeated terms. It illustrates why backtracking behavior matters when assessing regex performance. section 12.6.3

How Secrets of the JavaScript Ninja, Third Edition covers it

How deep it goes
Explains consumption and character-by-character backtracking, then illustrates the performance risk with a timed pattern.
Examples
Compares bracketed-string matches, traces the match of `27 dresses`, and times rejection by a repeated-term regex.
What you can do after
Diagnose/debug with it when a regex consumes more text than intended or takes unexpectedly long to reject input.
How it connects
Connects repetition operators and nongreedy matching to backtracking and regular-expression performance.

Also explained in

Compare how 4 books explain greedy matching →

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.