A pattern with a quantifier inside a quantifier — a repeated group that is itself repeated — can take exponentially long on an input that almost matches but does not. The engine tries every possible way of splitting the input between the two quantifiers before giving up.
Twenty characters of the wrong input can take longer than the age of the universe against the wrong pattern. It has taken down real services, and the pattern that does it looks entirely reasonable.
Why does backtracking explode?
Because a backtracking engine explores alternatives rather than deciding. When a match fails at the end, it returns to the last choice point and tries the next possibility — and nested quantifiers create a number of choice points that doubles with each additional character.
The failure needs an input that gets almost all the way. A string that fails immediately is cheap; one that matches the repeated part fully and then fails on the final character is the expensive case, because every split has to be tried before the failure is certain.
The defence is to avoid nesting quantifiers, to anchor patterns so failure is detected early, and to be suspicious of any pattern applied to input from outside. Some engines avoid the problem entirely by using a different algorithm, at the cost of dropping features like backreferences.
What is worth memorising?
A small set covers most real patterns.
| Piece | Means |
|---|---|
| ^ and $ | start and end of the string |
| . | any character except a newline |
| * + ? | none or more, one or more, none or one |
| {2,5} | between two and five |
| [abc] and [^abc] | one of these, none of these |
| ( ) and (?: ) | capture, and group without capturing |
The dot not matching a newline is the one that surprises people most. It is a default rather than a rule, and there is a flag to change it — which means a pattern tested on one line behaves differently on a paragraph.
Non-capturing groups are worth the extra characters. A pattern full of capture groups you never read makes the results harder to work with and the pattern slower.
What is the difference between greedy and lazy?
How much a quantifier takes before letting the rest of the pattern try. A greedy quantifier consumes as much as possible and gives characters back one at a time; a lazy one takes as little as possible and adds characters as needed.
It is the difference between matching to the last delimiter on a line and matching to the first. Extracting a quoted string with a greedy pattern grabs from the first quote to the last quote on the line, swallowing everything between two separate quoted strings.
A question mark after the quantifier makes it lazy, and it is usually what was wanted when a match comes out too long.
Should you validate with a pattern?
For shape, yes. For meaning, rarely. A pattern is good at answering whether text looks like a postcode, a reference or a date; it cannot answer whether that postcode exists or that date is real.
Email is the standard cautionary case, and the extraction article covers why the fully compliant pattern is unusable and unnecessary. A pragmatic pattern plus an actual delivery attempt beats a perfect pattern with nothing behind it.
Nested structures are the other limit. Anything with arbitrary nesting — HTML, brackets, most programming languages — cannot be matched by a pattern at all, because the notation has no way to count depth. That is a mathematical property rather than a matter of effort.
What about escaping?
Any literal string used inside a pattern needs its special characters escaped first. A dot, a plus, brackets, parentheses and the backslash itself all mean something, so a user-supplied search term inserted raw becomes a pattern rather than a search.
That is a bug and occasionally a vulnerability, since a crafted term can turn a cheap pattern into the exponential kind described above.
Escaping is mechanical and worth doing with a tool rather than by hand, because the set of characters needing it differs slightly between engines.
When is a pattern the wrong tool?
When the text has structure a parser already understands. Pulling a value out of JSON, HTML or CSV with a pattern works on the examples in front of you and fails on the first quoted delimiter, escaped character or attribute in an unexpected order.
The tell is a pattern that keeps growing. Each new failing case adds another alternative, and a pattern nobody can read is one that will be replaced rather than fixed the next time it breaks.
Parsing properly and then matching on the extracted field is almost always shorter as well as correct, which is the rare case where the right answer is also the easier one.
Questions people ask
Are patterns portable between languages? Mostly, and the differences are in lookbehind, named groups and Unicode handling.
Should I comment a long pattern? Yes. Several engines have a mode allowing whitespace and comments inside a pattern.
Is a pattern faster than string functions? Usually slower for a simple contains-or-starts-with check. Use the plain function.
How do I test one safely? Against realistic input including the near-miss cases, which is where the slow ones reveal themselves.
Test it before you ship it. The regex tester shows the matches and groups against sample text as you type, and the regex escaper turns a literal string into a pattern that matches it exactly.