Anulowanie długo działającego dopasowania do wyrażenia regularnego?

Question

Powiedz, że korzystam z usługi, w której użytkownicy mogą przesłać wyrażenie regularne w celu przeszukiwania dużej ilości danych. Jeśli użytkownik prześle wyrażenie, które jest bardzo powolne (tj. Wraca do zwrócenia Matcher.find() minut), chcę sposób na anulowanie tego dopasowania. Jedyny sposób, w jaki mogę to zrobić, to mieć inny wątek monitorujący, jak długo trwa mecz i użyć Thread.stop(), aby anulować, jeśli to konieczne.

zmienne użytkownika: gwint

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

Matcher: gwint

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 
} 

Monitor:

synchronized (lock) { 
    while (! finished) { 
     try { 
      lock.wait(REGEX_TIMEOUT); 

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

Czytałem java.sun.com/j2se/1.4.2/ docs/guide/misc/threadPrimitiveDeprecation.html i myślę, że to użycie jest bezpieczne, ponieważ kontroluję, gdzie ThreadDeath jest generowany przez synchronizację i ha ndle go i jedynymi uszkodzonymi obiektami mogą być moje instancje Pattern i Matcher, które i tak zostaną odrzucone. Myślę, że to zrywa Thread.stop(), ponieważ nie przerzucam błędu, ale tak naprawdę nie chcę, aby wątek umarł, wystarczy przerwać metodę find().

Do tej pory udało mi się uniknąć używania tych nieaktualnych komponentów API, ale metoda Matcher.find() nie wydaje się być przerywana i może zająć bardzo dużo czasu. Czy istnieje lepszy sposób to zrobić?

Answer 1

Od 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(); 
    } 
} 

Owiń CharSequence z tym jednym i wątek przerwania będzie działać ...

Answer 2

Innym Rozwiązaniem byłoby ograniczyć region z dopasowującego, następnie zadzwonić find() , powtarzanie do momentu przerwania wątku lub znalezienia dopasowania.

Answer 3

Przy odrobinie zmienności możliwe jest uniknięcie stosowania dodatkowych tematów na tym:

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(); 
     } 
    } 

} 

Wielkie dzięki dawce dla wskazujące mnie do tego rozwiązania w odpowiedzi na niepotrzebne skomplikowanej question!

Answer 4

Może potrzebna jest nowa biblioteka, która implementuje algorytm NFA.

Algorytm NFA jest setki razy szybszy niż algorytm używany w standardowej bibliotece Java.

Java std lib jest wrażliwa na wyrażenie regularne, co może spowodować wystąpienie problemu - niektóre dane wejściowe sprawiają, że procesor działa przez wiele lat.

Limit czasu można ustawić za pomocą algorytmu NFA, wykonując czynności, których używa. Jest skuteczniejszy niż rozwiązanie gwintowe. Zaufaj mi Używam timeout wątku do względnego problemu, to jest okropne dla wydajności. W końcu naprawiam problem modyfikując główną pętlę mojego narzędzia algorytmu. Wstawiam punkt kontrolny do głównej pętli, żeby przetestować czas.

Szczegóły można znaleźć tutaj: https://swtch.com/~rsc/regexp/regexp1.html.