Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 38 ยท Performance and ReDoS

How Backtracking Works

See how a backtracking regex engine really matches text. Follow greedy and lazy quantifiers, alternation order and failure paths step by step, and learn to count the work a pattern does.

Most regex surprises have one explanation: the engine is a backtracking machine. It reads your pattern from left to right and tries to match it against the text from left to right. Whenever a choice leads to a dead end, it goes back to the most recent choice and tries the next option. If you can imagine that process, you can predict what a pattern will match, what it will skip, and how long it will take.

This lesson builds the mental model. The next one, catastrophic backtracking, shows how the same process can become dangerously slow.

Choice points

An engine makes a decision at three kinds of places:

  1. Alternation a|b|c: try a; if the rest of the pattern fails afterwards, try b, then c.
  2. Quantifiers x*, x+, x?, x{2,5}: how many repetitions to take.
  3. Start positions: if no match begins at index 0, try index 1, then 2, and so on.

A greedy quantifier takes as many repetitions as it can first, then gives them back one at a time if later parts of the pattern fail. A lazy quantifier (*?, +?) takes as few as possible first and grows when needed.

flowchart TD
  A["Pattern ^(.*)([0-9]+)$ on the text abc123"] --> B["The dot-star grabs everything: abc123"]
  B --> C["The digit group needs a digit but the text is used up: fail"]
  C --> D["Give back one character: group 1 is abc12, group 2 tries 3"]
  D --> E["$ matches end: success"]

Greedy matching: take everything, then hand characters back until the rest fits.

Watching greedy and lazy

Node.js Greedy versus lazy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

The last two lines show backtracking in action: \d+ first takes 12345, fails because \d needs one more digit, gives back 5, and the match succeeds with 1234 and 5. With the lazy version, \d+? takes just 1 and the final \d takes 2.

Alternation order matters

The engine tries alternatives left to right and accepts the first one that lets the whole pattern succeed. It does not look for the longest or "best" match.

Node.js First match wins

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

The consequence: put longer or more specific alternatives first, or restructure with a shared prefix (foo(?:bar)?).

Counting the work

The cost of a match is roughly the number of states the engine visits. We can see it by timing a pattern against inputs that nearly match. A nearly-matching input forces the engine to try many ways before giving up.

Node.js Work grows with input size

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

The second loop is the interesting one. At start index 0, a* consumes all the a characters, finds no c, and backs off one step at a time. Then the engine retries at start index 1, and so on. That is about nยฒ/2 steps, so doubling the input roughly quadruples the time. Real engines add optimizations in some cases, so timings vary by pattern. The anchored version above shows the fix: with ^ there is only one start position to try. The general shape is what matters.

Where backtracking is useful

Backtracking is not a defect. It is what makes these features possible:

  • backreferences ((\w+) \1),
  • lookaround assertions,
  • lazy quantifiers and flexible alternation,
  • captures that keep their last value.

You get speed back by helping the engine make fewer wrong guesses:

  • Anchor patterns (^, \b) so fewer start positions are tried.
  • Be specific: [^"]* beats .*?" because it cannot overshoot.
  • Put the most distinctive literal early so failures are found fast.
  • Avoid overlapping choices: if two alternatives or two adjacent quantifiers can match the same characters, there are many ways to split the text, and the engine may try them all.

A trace you can reason about

Take /^(a|ab)(c|bcd)$/ and the input abcd:

  1. Group 1 tries a: success, position 1.
  2. Group 2 tries c at position 1: the text is b; fail. Try bcd: success, position 4.
  3. $ matches at the end. Match found, with groups a and bcd.

Now input abc:

  1. Group 1 a; group 2 c fails at b; bcd fails (only bc is left).
  2. Back to group 1, next alternative ab: position 2.
  3. Group 2 c matches position 2; $ matches. Groups are ab and c.

The engine backtracked into group 1 because group 2 could not complete. This is the same mechanism behind greedy quantifiers.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does "<a><b>".match(/<.*>/)[0] return?

    The greedy dot takes everything up to the end, then backs off just far enough to find the last closing bracket.
  2. 2. How does the engine choose between alternatives in foo|foobar?

    Alternation is ordered. In foo|foobar the first branch matches foo, so foobar is never reached on its own.
  3. 3. Why is [^"]* usually faster and safer than .*? before a closing quote?

    A negated class stops at the delimiter by definition, so the engine never has to try different lengths.
  4. 4. Why can /a*c/ be slow on a long string of a characters with no c?

    Each start index scans the remaining a characters before failing, which gives roughly quadratic work.

Summary

  • A backtracking engine tries choices left to right and returns to the last choice when a path fails.
  • Greedy quantifiers take the most and give back; lazy quantifiers take the least and grow.
  • Alternation is ordered; the first branch that lets the whole pattern succeed wins.
  • Work grows with how many ways the engine can split the text; failing matches cost the most.
  • Anchors, specific classes and non-overlapping choices reduce wasted steps.

Next: Catastrophic Backtracking and ReDoS