Bug in java.util.regex in sun jdk 6.0.24?

The following code blocks on my system. Why?

System.out.println( Pattern.compile( 
   "^((?:[^'\"][^'\"]*|\"[^\"]*\"|'[^']*')*)/\\*.*?\\*/(.*)$", 
   P开发者_运维技巧attern.MULTILINE | Pattern.DOTALL ).matcher( 
   "\n\n\n\n\n\nUPDATE \"$SCHEMA\" SET \"VERSION\" = 12 WHERE NAME = 'SOMENAMEVALUE';"
   ).matches() );

The pattern (designed to detect comments of the form /*...*/ but not within ' or ") should be fast, as it is deterministic... Why does it take soooo long?

---

You're running into catastrophic backtracking.

Looking at your regex, it's easy to see how .*? and (.*) can match the same content since both also can match the intervening \*/ part (dot matches all, remember). Plus (and even more problematic), they can also match the same stuff that ((?:[^'"][^'"]*|"[^"]*"|'[^']*')*) matches.

The regex engine gets bogged down in trying all the permutations, especially if the string you're testing against is long.

I've just checked your regex against your string in RegexBuddy. It aborts the match attempt after 1.000.000 steps of the regex engine. Java will keep churning on until it gets through all permutations or until a Stack Overflow occurs...

You can greatly improve the performance of your regex by prohibiting backtracking into stuff that has already been matched. You can use atomic groups for this, changing your regex into

^((?>[^'"]+|"[^"]*"|'[^']*')*)(?>/\*.*?\*/)(.*)$

or, as a Java string:

"^((?>[^'\"]+|\"[^\"]*\"|'[^']*')*)(?>/\\*.*?\\*/)(.*)$"

This reduces the number of steps the regex engine has to go through from > 1 million to 58.

Be advised though that this will only find the first occurrence of a comment, so you'll have to apply the regex repeatedly until it fails.

Edit: I just added two slashes that were important for the expressions to work. Yet I had to change more than 6 characters.... :(

---

I recommend that you read Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...).

---

I think it's because of this bit:

(?:[^'\"][^'\"]*|\"[^\"]*\"|'[^']*')*

Removing the second and third alternatives gives you:

(?:[^'\"][^'\"]*)*

or:

(?:[^'\"]+)*

Repeated repeats can take a long time.

---

For comment /* and */ detection I would suggest having a code like this:

String str = "\n\n\n\n\n\nUPDATE \"$SCHEMA\" /*a comment\n\n*/ SET \"VERSION\" = 12 WHERE NAME = 'SOMENAMEVALUE';";
Pattern pt = Pattern.compile("\"[^\"]*\"|'[^']*'|(/\\*.*?\\*/)", 
                             Pattern.MULTILINE | Pattern.DOTALL);
Matcher matcher = pt.matcher(str);
boolean found = false;
while (matcher.find()) {
   if (matcher.group(1) != null) {
      found = true;
      break;
   }
}
if (found)
   System.out.println("Found Comment: [" + matcher.group(1) + ']');
else
   System.out.println("Didn't find Comment");

For above string it prints:

Found Comment: [/*a comment

*/]

But if I change input string to:

String str = "\n\n\n\n\n\nUPDATE \"$SCHEMA\" '/*a comment\n\n*/' SET \"VERSION\" = 12 WHERE NAME = 'SOMENAMEVALUE';";

OR

String str = "\n\n\n\n\n\nUPDATE \"$SCHEMA\" \"/*a comment\n\n*/\" SET \"VERSION\" = 12 WHERE NAME = 'SOMENAMEVALUE';";

Output is:

Didn't find Comment