skip to content

Which pattern shapes in Python's `re` module risk catastrophic backtracking?

level: juniorimportance: should knowfreq 30%

answer

  1. More than one way to match the same text
  2. Look under a star or a plus
  3. A quantifier inside a repeated group
  4. Overlapping alternation branches
  5. Cost is paid on failure, not on a match

basics

~20 s

Ambiguous repetition: a quantifier nested inside a repeated group such as (a+)+, or a repeated alternation whose branches overlap such as (a|a)*. Both are cheap until the input almost matches, and then the engine tries every possible split.

solid answer

~40 s

The dangerous shape is a repeated construct that can match the same text in more than one way. The textbook case is a nested quantifier — `(a+)+`, `(a*)*`, `(\d+)*` — where the outer repeat and the inner repeat compete for the same characters. The same ambiguity appears in a repeated group whose parts overlap, like `(\s*\w+)*` or `(a|ab)*`. None of these is slow on its own: the blow-up needs an input that almost matches and then fails at the end, typically because of a trailing anchor or literal the text does not satisfy. `re.compile()` accepts every one of these without complaint, so nothing warns you at build time; the cost only shows up at match time, on one unlucky input.

code

python · 8 lines
python
import re

risky = [r"(a+)+$", r"(a|a)+$", r"(\s*\w+)*$", r"(\d+)*$"]
for pattern in risky:
    re.compile(pattern)  # every one compiles cleanly - nothing warns you

safe = [r"a+b+$", r"[ab]+$", r"\d{3}-\d{4}$"]
print(len(risky), "ambiguous,", len(safe), "unambiguous")

go deeper

for a junior

Be able to point at (a+)+ or (\s*\w+)* in a diff and say why the nesting is the problem. Recall that the slow input is one that almost matches and then fails.

for a middle

Explain what ambiguity means concretely — name two different ways the same substring could be carved up by the pattern — and show the rewrite that removes the nesting.

for a senior

Expect to be asked where such patterns come from in a real codebase: log parsers, header and email-address validators, patterns edited by several people over time. Have a review rule you actually apply.

for a principal

Own the policy: which patterns may touch untrusted input at all, whether user-supplied patterns are ever accepted, and where regex should be replaced by a real parser or plain string methods.

## What the engine is actually doing Python's `re` module is a **backtracking** matcher. When a pattern reaches a point where two continuations are possible — take one more repetition, or stop and move on — the engine saves the alternative on a stack, walks down one branch, and if that branch eventually fails it pops the saved state and tries the other. For most patterns this search finds an answer almost immediately. The pathological case is a pattern where the number of distinct branches grows exponentially with the input length, and an input that forces the engine to explore all of them before it can say "no match". ## The property that makes a pattern dangerous: ambiguity A pattern is **ambiguous** when there is more than one way for it to match the same span of text. Ambiguity under a repetition is what turns into exponential search. **1. A quantifier nested inside a repeated group.** `(a+)+`, `(a*)*`, `(x+){2,}`, `(\d+)*`. Against the text `aaaa`, the inner `a+` can take one, two, three or four `a`s, and the outer `+` repeats whatever is left — so the same four characters can be carved up as `4`, `3+1`, `2+2`, `1+1+2`, and so on. Every one of those carvings is a distinct state the engine can back into. **2. A repeated group whose body can consume the same text two ways.** `(\s*\w+)*` is the realistic version of the same defect: `\s*` may match nothing, so a run of word characters can be split between iterations in many places. `(a|ab)*` and `(x|xy)+` have the same shape — the branches of the alternation overlap. **3. A repeated alternation with duplicate or overlapping branches.** `(a|a)*` is the caricature; `(one|o\w+)*` is what it looks like in real code after a few edits. **4. Adjacent unbounded repeats over the same character class.** `.*.*=.*` or `\d+\d+` — the boundary between the two repeats can be placed anywhere. ## What is *not* dangerous `a+b+`, `[ab]+$`, `\d{3}-\d{4}`, a single `.*` — these are unambiguous or only linearly ambiguous, and they run in time proportional to the input. Greedy versus lazy makes no difference to this: `(a+?)+` is exactly as explosive as `(a+)+`. Bounded repeats limit the damage but do not eliminate it — `(a{1,3})*` is far tamer than `(a+)+` but is still ambiguous. ## The trigger is a near-match, not a match This is the part candidates most often miss. A pattern that *matches* usually returns on the first or second attempt, because the greedy first guess is often right. The exponential cost is paid on **failure**: the engine must prove that *no* arrangement works, and proving a negative means enumerating the whole search space. So the expensive input is the one that looks almost right — the correct characters followed by one wrong one, or a missing terminator at the end. That is why these bugs survive every test in the suite and then arrive from a user. `re.search()` makes it slightly worse than `re.fullmatch()`: search retries the whole pattern at every starting offset, multiplying the per-offset cost by the length of the string. ## Nothing warns you `re.compile()` validates syntax, not cost. All four shapes above compile cleanly and there is no stdlib linter, no complexity budget and no timeout parameter anywhere in `re`. The only defences are review discipline — treat a nested quantifier in a code review as a finding on its own — plus the pattern-level fixes (collapse `(a+)+` to `a+`, make alternation branches disjoint, anchor the pattern) and, since 3.11, atomic groups and possessive quantifiers, which tell the engine not to keep the alternatives at all. A rule of thumb that catches most real cases: **if you can point at two different ways the pattern could match the same substring, and that construct sits under a `*`, `+` or `{m,}`, you have the shape.**

  • Does switching `(a+)+` to the lazy form `(a+?)+?` help?
    No. Lazy quantifiers change the order in which the engine tries the alternatives, not how many alternatives exist. The search space for an ambiguous repetition is the same size either way, so a failing input still forces the engine through all of it. Laziness changes which match you get when several are possible; it is not a performance fix.
  • Why does a suite of unit tests never catch one of these patterns?
    Because tests feed inputs that match, and a matching input usually returns on the engine's first greedy guess. The exponential path is only walked when the pattern must prove failure on a long near-match. Unless someone deliberately writes a near-miss input at a realistic length, the pattern looks instant in every test.

saying these in an interview costs you the question

  • Thinks any `.*` or long pattern is automatically dangerous
  • Believes the lazy `*?` form fixes the blow-up
  • Says `re.compile()` would reject a pathological pattern
  • Thinks the slow case is a long matching input
  • Confuses pattern length with matching cost

context

resolving links…