liveBook · Manning

Catastrophic backtracking

Catastrophic backtracking is pathological regular-expression matching in which ambiguous alternatives cause exponentially many paths to be explored, potentially causing extreme execution time.

How 2 Manning books explain it

Secrets of the JavaScript Ninja, Third Edition

Catastrophic backtracking is regex backtracking whose possible paths grow exponentially and can exhaust execution time or block a thread.

How it is used
Explains how regex backtracking can turn pattern matching into a performance and denial-of-service risk.
How deep it goes
Traces a failing match through alternative word splits and compares DFA tradeoffs, without detailing sandboxing.
Examples
Uses a roster-matching regex and a near-match ending in an exclamation mark to demonstrate exponential backtracking.
What you can do after
Evaluate regex performance risks and consider a DFA-based engine when safety is a priority.

Read how Secrets of the JavaScript Ninja, Third Edition explains catastrophic backtracking →

Regular Expression Puzzles and AI Coding Assistants

Catastrophic backtracking is regex matching behavior in which an engine explores exponentially many alternatives caused by ambiguous pattern assignments before determining that no match exists.

How it is used
Validates an alternating-block message protocol while exposing regex performance hazards.
How deep it goes
Traces ambiguous group assignments through timing tests and mitigations without detailing matcher internals.
Examples
Tests geometric protocol messages and letter-based alternating strings with valid, malformed, and near-miss endings.
What you can do after
Diagnose/debug with it by timing adversarial failures and applying prevalidation or possessive quantifiers.

Read how Regular Expression Puzzles and AI Coding Assistants explains catastrophic backtracking →

Related concepts

Questions about catastrophic backtracking

What is catastrophic backtracking?

Catastrophic backtracking is pathological regular-expression matching in which ambiguous alternatives cause exponentially many paths to be explored, potentially causing extreme execution time.

Which Manning books explain catastrophic backtracking?

Secrets of the JavaScript Ninja, Third Edition and Regular Expression Puzzles and AI Coding Assistants.

What is the difference between catastrophic backtracking and non-greedy quantifier?

Catastrophic backtracking is pathological regular-expression matching in which ambiguous alternatives cause exponentially many paths to be explored, potentially causing extreme execution time. A non-greedy quantifier matches the fewest repetitions that allow the entire regular expression to match.

What is catastrophic backtracking a kind of?

Catastrophic backtracking is a kind of backtracking. Backtracking is a technique that returns to earlier decisions or states along a path to reconsider choices, explore alternatives, or reconstruct a solution.

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.