How browsers word it
| fjordtools regex tester | This pattern took longer than 1.5 seconds. It may backtrack catastrophically. |
|---|---|
| Browsers and Node | No error: the tab or process stops responding until the match ends |
| Python and Java | No error: one thread runs at full CPU until the match ends |
Common causes
A repeat inside a repeat
(a+)+$ on 26 letters a followed by b takes about two seconds in V8; each extra letter roughly doubles it. The pattern fails at the b, then tries every way to split the a's between the two repeats.
Alternatives that overlap
^(a|aa)+$ can read the same run of a's as many different mixes of a and aa. When the end does not match, all of them are tried.
Two open-ended parts next to each other
Patterns like (.*)*, or .*.*x on a line without an x, give the engine a choice at every position. Only the failing case is slow, so tests on good input pass.
The unambiguous form is fast
a+$ means the same here and has one way to read the text. It fails on a long run of a's in a fraction of a millisecond.
How to fix it
- Remove the inner repeat: (a+)+ matches the same text as a+.
- Make alternatives start with different characters, or merge them: (a|aa)+ is a+.
- Anchor the pattern and use a character class that cannot match the separator, such as [^,]* instead of .*.
- On user input, set a time limit or use a linear-time engine such as RE2.
- Test with a long non-matching input: the tester stops after 1.5 seconds and tells you.