Regex Pattern Catastrophic backtracking

by

Never use * when + is what you mean. The first thing I noticed about your regex is that almost everything is optional. Only the opening and closing square brackets are required, and I’m pretty sure you don’t want to treat [] as a valid input.

One of the biggest causes of runaway backtracking is to have two or more alternatives that can match the same things. That’s what you’ve got with the |[\p{N}]* part. The regex engine has to try every conceivable path through the string before it gives up, so all those \p{N}* constructs get into an endless tug-of-war over every group of digits.

But there’s no point trying to fix those problems, because the overall structure is wrong. I think this is what you’re looking for:

^\[\p{N}+\](?:,\[\p{N}+\])*$

After it consumes the first token ([1234567]), if the next thing in the string is not a comma or the end of the string, it fails immediately. If it does see a comma, it must go on to match another complete token ([89023432]), or it fails immediately.

That’s probably the most important thing to remember when you’re creating a regex: if it’s going to fail, you want it to fail as quickly as possible. You can use features like atomic groups and possessive quantifiers toward that end, but if you get the structure of the regex right, you rarely need them. Backtracking is not inevitable.

More Related Contents:

  1. Catastrophic backtracking shouldn’t be happening on this regex
  2. Program is saying all my valid inputs are invalid (REGEX code Issue maybe?) [closed]
  3. How to split a string if any chracter is found in java
  4. How to escape text for regular expression in Java
  5. Split string to equal length substrings in Java
  6. Why in Java 8 split sometimes removes empty strings at start of result array?
  7. Unicode equivalents for \w and \b in Java regular expressions?
  8. Using Regular Expressions to Extract a Value in Java
  9. Java RegEx meta character (.) and ordinary dot?
  10. Getting the text that follows after the regex match
  11. How can I count the number of matches for a regex?
  12. What is the regex to extract all the emojis from a string?
  13. Splitting string with pipe character (“|”) [duplicate]
  14. Java equivalent to PHP’s preg_replace_callback
  15. java.lang.StackOverflowError while using a RegEx to Parse big strings
  16. Split regex to extract Strings of contiguous characters
  17. Java regex – overlapping matches
  18. Find everything between two XML tags with RegEx
  19. Parsing CSV input with a RegEx in java
  20. simple java regex throwing illegalstateexception [duplicate]
  21. Range of valid character for a base 64 encoding
  22. Regex: ?: notation (Question mark and colon notation) [duplicate]
  23. Java Pattern Matcher: create new or reset?
  24. Regular Expression for matching parentheses
  25. Java Regex – Using String’s replaceAll method to replace newlines
  26. Replace a String between two Strings
  27. Does Pattern.compile cache?
  28. Regex to remove spaces between numbers only
  29. Java Counting # of occurrences of a word in a string
  30. Get group names in java regex

Leave a Comment