Skip to content

Taxonomy

Catastrophic backtracking

A regular expression whose cost explodes on an input that never matches.

What it looks like

  • Nested quantifiers: (a+)+, (\s*\w+)*.
  • Alternation where the branches can match the same text.
  • A pattern applied to input of unbounded length.

Why it survives review

It matches everything it is supposed to match, quickly, and every test passes in microseconds. The failure needs a specific *non-matching* input — usually a long run of the repeated character followed by something that breaks the match — and no test suite contains one.

How to see it

  1. Look for a quantifier inside a group that is itself quantified. That shape is the whole class.
  2. Ask what the engine does on a long input that *almost* matches, not on one that does.
  3. For anything that touches user input, prefer an explicit parser to a clever pattern. A regex is not free.

A minimal pair

Correct

const pattern = /^\w+(?:,\w+)*$/;

Defective

const pattern = /^(\w+,?)+$/;

Thirty word characters followed by a ! takes the correct build microseconds and the defective one longer than the request timeout.

Practise it

No exercise in the corpus sets this class yet. The lesson stands on its own — the corpus grows by adding subjects, and pretending otherwise would hide the gap.