Fixing Catastrophic Backtracking in Regular Expression

by

Your current regex can be written as ^(?:[a-zA-Z]:\\|\\\\)([^\\\/\:*?<>"|]+\\?)+$: pay attention at the ? quantifier (it is equal to {0,1} limiting quantifier) after \\ inside a + quantified group.

Once such a pattern like (a+b?)+ is present inside a pattern, there is a high chance of a catastrophical backtracking. Everything is nice when there is a match, say, c:\12\34\aaaaaaaaaaaaaaaaaaa is matched fine, but once a char that is not allowed appears causing a no-match, (try adding * at the end, c:\12\34\aaaaaaaaaaaaaaaaaaa*), the issue will appear.

To solve this, the quantified subpatterns that can match the same text cannot follow one another in immediate succession. And using optional groups where each subpattern is obligatory enables this.

In most scenarios, you need to replace these pattern parts with unrolled a+(ba+)* (1 or more occurrences of a followed with 0 or more sequences of b (that is no longer optional by itself) and then 1 or more occurrences of a (so, between one a and the next a there must be a b). If you need to match an optional \ at the end (as ^(a+b?)+$ actually may match b at the end of the string), you need to add a b? at the end: a+(ba+)*b?.

So, translating this to your current scenario:

^(?:[a-zA-Z]:\\|\\\\)[^\\\/\:*?<>"|]+(?:\\[^\\\/\:*?<>"|]+)*$

or if the \ is allowed at the end:

^(?:[a-zA-Z]:\\|\\\\)[^\\\/\:*?<>"|]+(?:\\[^\\\/\:*?<>"|]+)*\\?$
                     |      a+       (   b       a+       )* b?

See how it fails gracefully upon a no match, or matches as expected.

As @anubhava suggests, you can further enhance the performance by using possessive quantifiers (or atomic groups instead, since, e.g. .NET regex engine does not support possessives) that disallow any backtracking into the grouped patterns. Once matched, these patterns are not re-tried, thus, failure may come much quicker:

^(?:[a-zA-Z]:\\|\\\\)[^\\\/\:*?<>"|]+(?:\\[^\\\/\:*?<>"|]+)*+\\?$
                                                            ^

or an atomic group example:

^(?:[a-zA-Z]:\\|\\\\)(?>[^\\\/\:*?<>"|]+(?:\\[^\\\/\:*?<>"|]+)*)\\?$
                     ^^^                                       ^

Note that : is not a special regex metacharacter and should not be escaped. Inside a character class, only -, ^, \ and ] usually require escaping, all others are not special there either.

See more about catastrophical backtracking at The Explosive Quantifier Trap.

More Related Contents:

  1. Simple AlphaNumeric Regex (single spacing) without Catastrophic Backtracking
  2. RegEx for Multi-Words Without Numbers and Any Special Characters
  3. How does the () and [] come into play with regex?
  4. What is this pattern “\\s*\\^++\\s*” used for? [duplicate]
  5. How do (*SKIP) or (*F) work on regex?
  6. Regular Expression to find a string included between two characters while EXCLUDING the delimiters
  7. Difference between * and + regex
  8. How to capture multiple repeated groups?
  9. Regex to validate JSON
  10. Regex to match only letters
  11. Regular expression to enforce complex passwords, matching 3 out of 4 rules
  12. Regular expression for a string that does not start with a sequence
  13. How can I use a variable in the replacement side of the Perl substitution operator?
  14. Regex: Specify “space or start of string” and “space or end of string”
  15. Regex to match all permutations of {1,2,3,4} without repetition
  16. Negate characters in Regular Expression [closed]
  17. Have HTML5’s a inputs pattern attribute ignore case
  18. Regex to match 2 digits, optional decimal, two digits
  19. Match Question Mark in mod_rewrite rule regex
  20. When should I not use regular expressions?
  21. Replace a word with multiple lines using sed?
  22. How to use RegEx in Dart?
  23. Regex for youtube URL
  24. .htaccess RewriteRule to path without changing URL
  25. Can extended regex implementations parse HTML?
  26. Regexp for subdomain
  27. Remove everything except a certain pattern
  28. RegEx for allowing alphanumeric at the starting and hyphen thereafter
  29. How does the ? make a quantifier lazy in regex
  30. How does \b work when using regular expressions?

Leave a Comment