Why does Python's re pattern ^(\d+)+$ hang on a crafted 30-character string?

## What the engine is actually doing Python's `re` is a **backtracking** engine. A compiled pattern is a small program, and matching walks it, remembering choice points; when a branch fails, the engine returns to the most recent choice point and tries the next alternative. That design is what makes backreferences and lookaround possible, and it is also what makes some patterns exponential. The trigger is **ambiguity**: two or more ways for the same characters to be consumed by the same pattern. `(\d+)+` is the textbook case. Against `"111"`, the outer `+` can iterate once with the inner `\d+` taking all three digits, or twice as 1+11 or 11+1, or three times as 1+1+1. For n digits there are 2**(n-1) partitions, and each is a distinct path the engine may have to explore. Crucially, this costs nothing on a **match**. The engine stops the moment one arrangement succeeds, and the first one it tries — greedy, take everything — usually works. The blow-up needs a **failure** after a long ambiguous prefix. Append a single character the pattern cannot accept, and the engine is obliged to try every partition before it can honestly report "no match": ```python import re, time p = re.compile(r"^(\d+)+$") for n in (24, 26, 28, 30): s = "1" * n + "x" t = time.perf_counter(); p.match(s); print(n, round(time.perf_counter() - t, 2)) # 24 0.49 26 1.95 28 8.04 30 31.14 ``` Doubling every two characters is the signature. A 40-character field would run for hours. ## The shapes to recognize in review The nested quantifier `(x+)+` is only the clearest form. In real code the ambiguity usually hides: - `(a|a)*`, `(a|ab)*` — alternatives that can both match the same text. - `(\s*\w+\s*,)*` — the `\s*` on both ends of the group overlap, so whitespace can be claimed by either side. - `^(.*,)*$` over a comma-separated field, where `.` can also match the comma. - Long chains of optional groups, which is why hand-written email and URL patterns are a classic source. The rule of thumb: if two parts of the pattern can consume the same character, and one of them is inside a repetition, look harder. ## How it shows up in production Consider a CSV import for a payroll system that validates each row's amount column with a pattern of this shape. Ninety-nine percent of rows match on the first try and cost nothing. Then one row arrives with forty digits and a stray character — a typo, or a deliberate probe — and the worker pins one core and never returns. The failure mode is nastier than a crash because *nothing is raised*. The importer's `try/except Exception: log_and_continue` around each row never fires; the call simply does not come back. Liveness probes that only check the HTTP port still pass, the queue drains no further, and the operator sees a stuck worker with no traceback anywhere. A swallowed-exception habit does not even get the chance to swallow anything here — there is no exception, and that is exactly why the incident takes so long to diagnose. You cannot rescue it from outside, either. `re` accepts no timeout argument, and the match runs as a single call into C, so a watchdog thread cannot reliably interrupt it. `faulthandler.dump_traceback_later()` is the useful tool: arm it before the parse and it will dump every thread's stack if the deadline passes, and the stack will point straight into the `re` call and the pattern's line. ## Fixing it **First, remove the ambiguity.** `^\d+$` accepts exactly the same strings as `^(\d+)+$` and runs in linear time. Most catastrophic patterns in real code are like this — the nesting was never doing anything. **Second, forbid giving back.** Python 3.11 added possessive quantifiers (`*+`, `++`, `?+`, `{m,n}+`) and atomic groups (`(?>...)`). Both consume greedily and refuse to hand characters back on failure, which collapses the choice points: ```python re.compile(r"^(\d++)+$").match("1" * 30 + "x") # None, instantly re.compile(r"^(?>\d+)+$").match("1" * 30 + "x") # None, instantly ``` On 3.10 and earlier neither syntax exists, so rewriting the pattern is the only in-language fix. **Third, bound the input.** Check `len(field)` before matching. A cap that is generous for real data still turns an exponential into a small constant, and it is one line in the validator. **Fourth, never compile a pattern that came from a user.** If a feature genuinely needs client-supplied patterns, run the match in a separate process with `subprocess.run(..., timeout=...)` so a hang is bounded and recoverable, or use a third-party finite-automaton engine that guarantees linear time at the cost of backreferences and lookaround. Finally, treat it as testable. Patterns applied to untrusted input deserve a unit test that asserts a near-miss input completes inside a small time budget — that is the check that catches the next ambiguous pattern before it reaches a queue worker.