Catastrophic Backtracking & When Not to Use Regex
In short: when a match fails, the engine doesn't give up — it
backtracks, giving characters back to an earlier quantifier and trying a
different split of the text. Most patterns have only a few ways to split
their text, so backtracking is instant. A repeated group whose body can
match the same text more than one way — (a+)+, (\w+\s?)* — has
exponentially many ways, and the engine tries every one before admitting
defeat: each extra character can double the time. Python's re has no
timeout, so the fix is to rewrite the pattern with a mandatory separator
between repetitions, bound the input length, or reach for a hand-written
scanner instead of a regex at all.
Quarry has a feature request from operations: let us type our own search
patterns. A reasonable ask — and it hides the most famous performance bug in
text processing. This lesson measures that blow-up on your own machine,
explains exactly where it comes from, and builds safe_match(): the guard
every operator-supplied pattern passes through before Quarry lets it near a
file.
Let operators search the yard with their own pattern
Here's a pattern that looks harmless: (a+)+b — "one or more runs of a's,
then a b". Against a string of a's that ends in c instead of b, it has to
fail. Time how long failing takes:
Read your own numbers down the right column: every two extra characters
roughly quadruple the time — the signature of 2ⁿ. Now run the same
experiment with the pattern rewritten as a+b, which accepts exactly the
same strings:
Flat. Same language, same answer, completely different cost. Whatever's going on is about the shape of the pattern, not what it matches.
Remember the engine's rule: when something fails, it backtracks and tries
another way to consume the same text. (a+)+ has an enormous number of other
ways. For aaaa, the outer + can use one inner run of four, or 3+1, 1+3,
2+2, 2+1+1, 1+2+1, 1+1+2, or 1+1+1+1 — eight carvings, each one reaching the
end, finding c where it wanted b, and failing. The engine won't give up
until it has tried them all.
def carvings(n):
if n == 0:
return 1
return sum(carvings(n - first) for first in range(1, n + 1))
print(carvings(5), carvings(10))At a generous million attempts per second, (a+)+b failing on n
characters takes about 2ⁿ microseconds:
| characters | time to fail |
|---|---|
| 20 | about 1 second |
| 26 | over a minute |
| 35 | about 9.5 hours |
A log line is often longer than that. The rewritten a+b fails in a few
dozen steps, well under a millisecond.
Catch the risky shape before it ever runs
Catastrophic backtracking needs two ingredients: a repeated group —
(…)+, (…)* or (…){n,} — whose body can match the same text in more
than one way from one repetition to the next. (\w+\s?)* is a common
attempt at "words separated by spaces" that qualifies, because \s? is
optional, so abc can be one word or three. Compare \d+(?:,\d+)*: every
repetition must begin with a mandatory comma, so 12,345,6 only splits
one way. Safe.
That gives a rule Quarry can check mechanically: inside a repeated group,
if every element is itself optional or repeated, the group is dangerous. A
mandatory literal separator breaks the ambiguity. It's a heuristic — it
misses overlapping alternatives like (a|aa)+ — but it catches the shapes
behind nearly every real incident.
GROUP finds a parenthesised body with no parentheses inside it, followed by
a repeating quantifier, skipping over a ?: or ?P<name> prefix.
ATOM.findall turns the body into (atom, quantifier) pairs; if every pair
has a quantifier, nothing in a repetition is mandatory, and the group is
flagged.
import re
ATOM = re.compile(r"(\\.|\[[^\]]*\]|[^|])([+*?]|\{\d*,?\d*\})?")
print(ATOM.findall(r",\d+"))Three more defences belong beside the rewrite: bound the input length
(exponential cost is harmless on tiny inputs); since Python 3.11,
possessive quantifiers and atomic groups (a++, (?>…)) never give back
what they took, so (?>a+)+b fails instantly; and, sometimes, don't use a
regex at all.
When a scanner beats a regex
A regex is the right tool for a flat shape. It's the wrong one when a
plain string method will do ("ERROR" in line can't backtrack), when the
structure nests (balanced brackets, JSON — re can't count nesting
depth), when the rules are about meaning (valid dates, checksums), or
when the pattern has become unreadable.
A hand-written scanner — a loop with an index that looks at one character, decides what kind of token starts there, and consumes it — is longer than a regex but runs in plainly linear time, nothing to backtrack into. This one splits a tail into words, but has a bug:
The last word goes missing. Run it, find the line responsible, and fix it without changing how the loop scans.
The next lesson builds a real scanner for Quarry's log tails.
Quick practice
import re
print(bool(re.fullmatch(r"\d+(?:,\d+)*", "12,345,6")))import re
GROUP = re.compile(r"\((?:\?:|\?P<\w+>)?([^()]*)\)(?:[+*]|\{\d+,\d*\})")
ATOM = re.compile(r"(\\.|\[[^\]]*\]|[^|])([+*?]|\{\d*,?\d*\})?")
def is_risky(pattern):
for group in GROUP.finditer(pattern):
for branch in group.group(1).split("|"):
atoms = ATOM.findall(branch)
if atoms and all(q for _, q in atoms):
return True
return False
print(is_risky(r"(a|aa)+"))🎯 Your turn
Write safe_match(pattern, text, max_len), the guard every operator-supplied
pattern goes through. Check in this order and return one of four strings:
"too-long"iftextis longer thanmax_len,"risky-pattern"if the pattern has a repeated group in which every element is optional or repeated (use theGROUP/ATOMcheck from this lesson),- otherwise
"match"ifre.search(pattern, text)finds something, else"no-match".
safe_match(r"\d+ms", "took=312ms", 100)→"match"safe_match(r"(a+)+b", "aaaa", 100)→"risky-pattern"safe_match(r"ERROR", "all good", 100)→"no-match"
Hint — the two cheap checks come first so the expensive one only ever runs on bounded input with a pattern that passed inspection.
Then press ▶ Run and hit ✓ Check. ✅