java - sun jdk 6.0.24 中 java.util.regex 中的错误？

Question

我的系统上有以下代码块。为什么？

System.out.println( Pattern.compile( 
   "^((?:[^'\"][^'\"]*|\"[^\"]*\"|'[^']*')*)/\\*.*?\\*/(.*)$", 
   Pattern.MULTILINE | Pattern.DOTALL ).matcher( 
   "\n\n\n\n\n\nUPDATE \"$SCHEMA\" SET \"VERSION\" = 12 WHERE NAME = 'SOMENAMEVALUE';"
   ).matches() );

模式(旨在检测形式为 /*...*/ 但不在 ' 或 " 内的注释)应该是快速，因为它是确定性的...... 为什么要花这么长时间？

Answer 1

你遇到了 catastrophic backtracking .

看看你的正则表达式，很容易看出 .*? 和 (.*) 可以匹配相同的内容，因为两者也可以匹配中间的 \*/ 部分(点匹配所有，记住)。另外(甚至更有问题)，它们还可以匹配 ((?:[^'"][^'"]*|"[^"]*"|'[^']*' )*) 匹配。

正则表达式引擎在尝试所有排列时陷入困境，尤其是当您测试的字符串很长时。

我刚刚根据 RegexBuddy 中的字符串检查了您的正则表达式.它会在正则表达式引擎运行 1.000.000 步后中止匹配尝试。 Java 将继续搅动，直到它完成所有排列或直到发生堆栈溢出...

您可以通过禁止回溯到已经匹配的内容来极大地提高正则表达式的性能。您可以使用 atomic groups为此，将您的正则表达式更改为

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

或者，作为 Java 字符串:

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

这将正则表达式引擎必须经过的步骤数从 > 100 万减少到 58。

请注意，这只会找到第一次出现的评论，因此您必须重复应用正则表达式，直到失败。

编辑:我刚刚添加了两个对表达式起作用很重要的斜杠。然而我不得不改变超过 6 个字符.... :(