How a Regex Engine Actually Steps Through a Match

A regex pattern reads like a declarative description of what counts as a match. What actually runs underneath is nothing like that — it's a sequential search that tries one interpretation, fails, and tries another, one character at a time. "It can backtrack" is the one-line summary most people know. Here's what that search actually looks like, step by step, on a real pattern.

A greedy quantifier takes everything first, then gives it back one at a time

a+ means "one or more a, as many as possible." Against input "aaa", that's not a one-shot decision — the engine has to actually consume characters greedily, hit a wall, and retreat:

a+ eats all three as immediately, because greedy means "try consuming more before trying to stop." Then the pattern still needs one more literal a — and there's nothing left. Only at that point does the engine backtrack: it gives a+ back exactly one character (down to matching two as instead of three), tries the final a again, and this time it has something to match against. The whole pattern succeeds, matching all three characters — but it took six steps and one real backtrack to get there, not one.

Alternation tries branches in order and stops at the first match — not the longest

cat|category against the input "category" looks like it should obviously match the whole word. It doesn't:

pattern: cat|category
input:   "category"
matched text: "cat"

Alternation is tried strictly left to right, and the engine stops at the first branch that works — it never looks ahead to see whether a later branch would match more.cat matches at position 0 and the engine is satisfied; category never even gets tried. This is the opposite of how some other matching systems behave (POSIX-style engines are required to find the longest match), and it's the reason branch order in an alternation isn't cosmetic — putting the more specific option first is a real behavior change, not just a style preference.

Two exact shapes that make backtracking blow up

"Catastrophic backtracking" isn't a vague risk — it comes from specific, recognizable shapes in a pattern. A quantifier wrapped around another unbounded quantifier gives the engine multiple ways to divide the same input between the two:

(a+)+b   against a long run of "a" with no trailing "b"
→ flagged: nested unbounded repetition detected

and an alternation repeated by a quantifier is just as dangerous when its branches overlap, since the engine has multiple ways to split the same text across repetitions of the group:

(a|ab)+b   against a long run of "a" with no trailing "b"
→ flagged: alternation repeated, branches can match the same text

A plain a+b against the same kind of input triggers neither warning — a single unbounded quantifier backtracks linearly, giving back one character at a time just like the a+a example above. The danger is specifically in the nesting: two quantifiers, or a quantifier around an ambiguous alternation, multiply the number of ways the engine can fail to match, rather than just trying each one once.

Visualizing a catastrophic pattern without actually hanging

Showing the step-by-step trace for a genuinely catastrophic pattern is itself a problem — the whole point is that it can take an astronomical number of steps to finish failing. The fix is a hard budget: stop tracing after a fixed number of steps and report that the trace was aborted rather than silently freezing:

(a+)+$ against thirty "a"s followed by "!"
→ aborted after 20,000 steps, no match found

Real-world catastrophic input can take millions of times longer than that to actually finish failing — the budget exists precisely so a demonstration of the problem doesn't become the problem.

Try it yourself

Regex Debugger runs every example above for real — paste any pattern and input and step through exactly what the engine tries, in order, including every backtrack, with the same two risk shapes flagged automatically before you even run it. For the broader question of which patterns to avoid writing in the first place, see Regex Performance Tips. Both run entirely in your browser.