科技猎如何中断一个长时间运行的“无限”Java正则表达式
本文由 ImportNew - 人晓 翻译自 ocpsoft。欢迎加入Java小组。转载请参见文章末尾的要求。
如果你处理过大量的正则表达式，那么你对“catastrophic backtracking”的概念一定不陌生，这种情况下处理器被强迫执行指数倍的计算。例如，点击该示例，看看它需要多久完成（应该在5-10秒后超时）。
LongRunningRegexExample.java
public class LongRunningRegexExample
{
public static void main(String[] args) throws InterruptedException
{
final Pattern pattern = Pattern.compile("(0*)*A");
final String input = "00000000000000000000000000";
long startTime = System.currentTimeMillis();
Matcher matcher = pattern.matcher(input);
matcher.find(); // runs for a long time!
System.out.println("Regex took:" + (System.currentTimeMillis() - startTime) + "ms");
}
}
但是，小小的改动就能让该程序立即响应。为什么呢？这里引用Dzone中Andreas Haufler的文章《How to Kill Java with a Regular Expression》，其中提到了这个非常简洁的例子：
-
第一眼看上去像是无限循环的东西会造成catastrophic backtracking
-
意思是说匹配器在输入的末尾并没有检测到”A”。现在外侧的限定符后退一次，内存的则前进一次，如此重复，无法得到结果。
-
因此，匹配器逐步回退，并尝试所有的组合以找出匹配符号。它最终将返回(没有匹配的结果)，但是该过程的复杂性是指数型的(输入中添加一个字符加倍了运行时间)。
所以，我们究竟该采取何种方式避免这种破坏性的影响，我们是否会遇到Java程序运行数天甚至几年的情形?
在你的资源非常充足的情况下，你也许可以简单小心的在你的模式中避免这种情况。但是，如果你正在开发一个接受正则表达式作为输入的应用程序，例如一个在线Java可视化的正则表达式示例，那么你就应该避免这种情情况或是受到拒绝服务器攻击。
幸运的是，答案非常简单，但需要引入一个线程，以及一个非常特殊的字符串序列。我是在StackOverflow上找到该实现的。
InterruptibleRegexExample.java
public class InterruptibleRegexExample
{
public static void main(String[] args) throws InterruptedException
{
final Pattern pattern = Pattern.compile("(0*)*A");
final String input = "00000000000000000000000000";
Runnable runnable = new Runnable() {
@Override
public void run()
{
long startTime = System.currentTimeMillis();
Matcher interruptableMatcher = pattern.matcher(new InterruptibleCharSequence(input));
interruptableMatcher.find(); // runs for a long time!
System.out.println("Regex took:" + (System.currentTimeMillis() - startTime) + "ms");
}
};
Thread thread = new Thread(runnable);
thread.start();
Thread.sleep(500);
thread.interrupt();
}
}
结果很好的中断了正则表达式：
Exception in thread "Thread-2" java.lang.RuntimeException: Die! ... Why won't you DIE!
at org.ocpsoft.tutorial.regex.server.InterruptRegex$InterruptibleCharSequence.charAt(InterruptRegex.java:72)
at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
at java.util.regex.Pattern$Curly.match0(Pattern.java:3760)
at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
你还需要一个InterruptibleCharSequence类，它在某种程度上也会影响性能，但是要比等上一年要好的多：
InterruptibleCharSequence.java
/**
* {@link CharSequence} that notices {@link Thread} interrupts
*
* @author gojomo - http://stackoverflow.com/questions/910740/cancelling-a-long-running-regex-match
*/
private static class InterruptibleCharSequence implements CharSequence {
CharSequence inner;
public InterruptibleCharSequence(CharSequence inner) {
super();
this.inner = inner;
}
@Override
public char charAt(int index) {
if (Thread.currentThread().isInterrupted()) {
throw new RuntimeException("Interrupted!");
}
return inner.charAt(index);
}
@Override
public int length() {
return inner.length();
}
@Override
public CharSequence subSequence(int start, int end) {
return new InterruptibleCharSequence(inner.subSequence(start, end));
}
@Override
public String toString() {
return inner.toString();
}
}
结论
我很开心能学习并撰写这些内容，这篇博客总结了正则表达式的无限运行及解决方案（Java中），希望它能帮到其他遇到该问题的人。愉快的过程！
原文链接： ocpsoft 翻译： ImportNew.com - 人晓
译文链接： http://www.importnew.com/11975.html
[ 转载请保留原文出处、译者和译文链接。]