Отмена длинного регулярного выражения?
Скажем, что я запускаю службу, где пользователи могут отправлять регулярное выражение для поиска по большому количеству данных. Если пользователь отправляет регулярное выражение, которое очень медленно (т.е. Для возвращения Matcher.find() требуется несколько минут), я хочу, чтобы отменить это совпадение. Единственный способ, которым я могу это сделать, - это следить за тем, как долго выполняется сопоставление, и использовать Thread.stop(), чтобы отменить его, если это необходимо.
Членские переменные:
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(), похоже, не прерывается и может занять очень много времени. Есть ли лучший способ сделать это?
Ответы
Ответ 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 этим, и поточные прерывания будут работать...
Ответ 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();
}
}
}
Большое спасибо за то, что указали мне на это решение в ответ на ненужный сложный question!
Ответ 3
Другим обходным решением было бы ограничить region соединителя, затем вызвать find()
, повторить до тех пор, пока поток не будет прерван или найдено совпадение.
Ответ 4
Возможно, вам нужна новая библиотека, которая реализует алгоритм NFA.
Алгоритм NFA в сотни раз быстрее, чем алгоритм, который используется стандартной библиотекой Java.
И Java std lib чувствителен к входному regexp, что может привести к вашей проблеме - некоторые данные заставляют процессор работать годами.
И таймаут может быть установлен алгоритмом NFA с помощью шагов, которые он использует. Он эффективен, чем решение Thread. Поверьте мне, я использую тайм-аут потока для относительной проблемы, это ужасно для производительности. Я, наконец, исправлю проблему, изменив основной цикл моего алгоритма. Я вставляю контрольную точку в основной цикл, чтобы проверить время.
Подробности можно найти здесь: https://swtch.com/~rsc/regexp/regexp1.html.