A regex can be perfectly correct and still be a terrible validator. Catastrophic backtracking occurs when ambiguous repeated groups let a matcher repeatedly redistribute the same characters among alternatives, only to discover near the end that the required terminator or final structure is absent. The number of attempted assignments can grow exponentially with input length. section 3.1 section 3.2
The nearly valid message trap
Consider messages made from alternating type-1 and type-2 symbol blocks, ending in !. Some symbols belong to both block alphabets, so a long run can be split between neighboring blocks in many ways. A valid message and an early mismatch return quickly; a long ambiguous message ending in X, or lacking !, can take roughly twice as long for each added character. section 3.1
Quick match |
'■▲○◉□▫□▪●◉◉▫▪▪●●□□▲▲○○◉■◉■▲▲□□◉▲!' is Valid
| Checked in 0.00 seconds
Quick failure |
'■▲○◉■▲▫▪●●■◉■▲▲◉◉◉■□□□▫▫▪●●●▫■◉■!' is Invalid
| Checked in 0.00 seconds
Failure | '▲□□▲▲□□▲▲▲□□□□□□□□▲▲□▲□▲□▲X' is Invalid
| Checked in 4.42 seconds
Slow failure | '▲□□▲▲▲□□▲▲▲□□□□□□□□▲▲□▲□▲□▲X' is Invalid
| Checked in 8.62 seconds
Exponential | '▲▲▲▲▲▲□□▲▲▲□□□□□□□□▲▲□▲□▲□▲▲X' is Invalid
| Checked in 17.59 seconds
One more symbol | '▲▲▲▲□▲□□▲▲□▲□□□□□□□□▲▲□▲□▲□▲▲' is Invalid
| Checked in 31.53 seconds
Compare quick matches with increasingly long near-misses. The slow cases differ by only a few symbols, yet their rejection times climb from seconds to tens of seconds. section 3.1
Do not assume that changing a quantifier’s greediness solves the problem. A non-greedy outer repetition changes the search order, not the underlying ambiguity; the proposed “nocat” pattern takes almost 15 seconds on one failing string while the original rejects it immediately. A benchmark is a better critic than a reassuring name or a plausible-looking regex. section 3.3
Two approaches reduce the danger, with different scopes:
- Prevalidate with a lookahead that the full input contains only allowed symbols and ends in the terminator. This fast check rejects many hostile failures before alternating-block matching begins, though it does not eliminate every backtracking case. section 3.2
- Use a possessive quantifier where available. The repeated alternating group then cannot surrender characters for later reinterpretation; the demonstrated Python pattern quickly accepts the valid string and rejects the missing-terminator string. section 3.3
The broader lesson is deliberately unglamorous: test validators with long inputs that are almost valid, especially when repeated alternatives overlap. Mathematical acceptance is only half the contract; prompt rejection of malformed input is the other half. section 3.1 section 3.3
