取消长时间运行的正则expression式匹配？

假设我正在运行一项服务，用户可以提交正则expression式来search大量数据。 如果用户提交一个非常缓慢的正则expression式（即Matcher.find（）需要几分钟才能返回），我想要一种方法来取消匹配。 我能想到的唯一方法是让另一个线程监视匹配的时间，如果需要的话使用Thread.stop（）来取消它。

成员variables：

long REGEX_TIMEOUT = 30000L; Object lock = new Object(); boolean finished = false; Thread matcherThread; 

匹配线程：

 try { matcherThread = Thread.currentThread(); // imagine code to start monitor thread is here try { matched = matcher.find(); } finally { synchronized (lock) { finished = true; lock.notifyAll(); } } } catch (ThreadDeath td) { // send angry message to client // handle error without rethrowing td } 

监视器线程：

 synchronized (lock) { while (! finished) { try { lock.wait(REGEX_TIMEOUT); if (! finished) { matcherThread.stop(); } } catch (InterruptedException ex) { // ignore, top level method in dedicated thread, etc.. } } } 

我读过java.sun.com/j2se/1.4.2/docs/guide/misc/threadPrimitiveDeprecation.html，我认为这个用法是安全的，因为我通过同步控制ThreadDeath在哪里抛出，并处理它，唯一的损坏对象可能是我的Pattern和Matcher实例，无论如何都将被丢弃。 我认为这打破了Thread.stop（），因为我没有重新抛出这个错误，但是我不是真的想死掉这个线程，只是放弃find（）方法。

到目前为止，我设法避免使用这些被弃用的API组件，但Matcher.find（）似乎不可中断，并且可能需要很长时间才能返回。 有没有更好的方法来做到这一点？

Answer 1

来自Heritrix：（ crawler.archive.org ）

 /** * CharSequence that noticed thread interrupts -- as might be necessary * to recover from a loose regex on unexpected challenging input. * * @author gojomo */ public class InterruptibleCharSequence implements CharSequence { CharSequence inner; // public long counter = 0; public InterruptibleCharSequence(CharSequence inner) { super(); this.inner = inner; } public char charAt(int index) { if (Thread.interrupted()) { // clears flag if set throw new RuntimeException(new InterruptedException()); } // counter++; return inner.charAt(index); } public int length() { return inner.length(); } public CharSequence subSequence(int start, int end) { return new InterruptibleCharSequence(inner.subSequence(start, end)); } @Override public String toString() { return inner.toString(); } } 

用这个包裹你的CharSequence和线程中断将工作…

Answer 2

有了一些变化，可以避免使用额外的线程：

 public class RegularExpressionUtils { // demonstrates behavior for regular expression running into catastrophic backtracking for given input public static void main(String[] args) { Matcher matcher = createMatcherWithTimeout( "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx", "(x+x+)+y", 2000); System.out.println(matcher.matches()); } public static Matcher createMatcherWithTimeout(String stringToMatch, String regularExpression, int timeoutMillis) { Pattern pattern = Pattern.compile(regularExpression); return createMatcherWithTimeout(stringToMatch, pattern, timeoutMillis); } public static Matcher createMatcherWithTimeout(String stringToMatch, Pattern regularExpressionPattern, int timeoutMillis) { CharSequence charSequence = new TimeoutRegexCharSequence(stringToMatch, timeoutMillis, stringToMatch, regularExpressionPattern.pattern()); return regularExpressionPattern.matcher(charSequence); } private static class TimeoutRegexCharSequence implements CharSequence { private final CharSequence inner; private final int timeoutMillis; private final long timeoutTime; private final String stringToMatch; private final String regularExpression; public TimeoutRegexCharSequence(CharSequence inner, int timeoutMillis, String stringToMatch, String regularExpression) { super(); this.inner = inner; this.timeoutMillis = timeoutMillis; this.stringToMatch = stringToMatch; this.regularExpression = regularExpression; timeoutTime = System.currentTimeMillis() + timeoutMillis; } public char charAt(int index) { if (System.currentTimeMillis() > timeoutTime) { throw new RuntimeException("Timeout occurred after " + timeoutMillis + "ms while processing regular expression '" + regularExpression + "' on input '" + stringToMatch + "'!"); } return inner.charAt(index); } public int length() { return inner.length(); } public CharSequence subSequence(int start, int end) { return new TimeoutRegexCharSequence(inner.subSequence(start, end), timeoutMillis, stringToMatch, regularExpression); } @Override public String toString() { return inner.toString(); } } } 

非常感谢，指点我这个解决scheme来回答一个不必要的复杂问题 ！

Answer 3

另一个解决方法是限制匹配器的区域 ，然后调用find() ，直到线程中断或find匹配。

Answer 4

也许你需要的是一个实现NFAalgorithm的新的lib。

NFAalgorithm比Java标准库使用的algorithm快数百倍。

Java std lib对input的正则expression式很敏感，这可能会让你的问题发生 – 有些input会使CPU运行多年。

超时可以由NFAalgorithm通过它使用的步骤来设置。 它比Thread解决scheme更有效。 相信我，我使用线程超时来解决一个相对的问题，这对于性能来说太可怕了。 我最后通过修改我的algorithm实现的主循环来修复这个问题。 我插入一些检查点到主循环来testing时间。

详细信息可以在这里find： https ： //swtch.com/~rsc/regexp/regexp1.html 。