Annullamento di una corrispondenza regolare nell'esecuzione prolungata?

Question

Dire che sto eseguendo un servizio in cui gli utenti possono inviare un'espressione regolare per cercare tra molti dati. Se l'utente invia una regex molto lenta (ad esempio, occorrono pochi minuti per Matcher.find() per tornare), voglio un modo per cancellare quella corrispondenza. L'unico modo che posso pensare di fare questo è di avere un altro thread monitor per quanto tempo sta prendendo una partita e usare Thread.stop() per cancellarlo se necessario.

variabili membro: filetto

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

Matcher: filo

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.. 
     } 
    } 
} 

ho letto java.sun.com/j2se/1.4.2/ docs/guide/misc/threadPrimitiveDeprecation.html e penso che questo utilizzo sia sicuro poiché sto controllando dove ThreadDeath viene lanciato tramite sincronizzazione e ha e gli unici oggetti danneggiati potrebbero essere le mie istanze Pattern and Matcher che verranno comunque scartate. Penso che questo rompa Thread.stop() perché non sto rilanciando l'errore, ma non voglio che il thread muoia, basta interrompere il metodo find().

Sono riuscito a evitare di utilizzare questi componenti API deprecati finora, ma Matcher.find() non sembra essere interrompibile e può richiedere molto tempo per restituire. C'è un modo migliore per farlo?

Answer 1

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

Avvolgere la CharSequence con questo e filo interrupt lavoreranno ...

Answer 2

Un'altra soluzione potrebbe essere quella di limitare il region del matcher, quindi chiamare find() , ripetendo finché il thread non viene interrotto o viene trovata una corrispondenza.

Answer 3

con una piccola variante, è possibile evitare l'uso di thread aggiuntivi per questo:

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

} 

Grazie mille a dawce per me che punta a questa soluzione in risposta ad una inutile complicata question!

Answer 4

Forse quello che ti serve è una nuova libreria che implementa l'algoritmo NFA.

L'algoritmo NFA è centinaia di volte più veloce rispetto l'algoritmo che viene utilizzato da libreria standard di Java.

E il lib std Java è sensibile alla regexp di ingresso, che può rendere il vostro problema accadere - alcuni input far girare CPU per anni.

E il timeout può essere impostato dall'algoritmo NFA tramite i passaggi che utilizza. È efficace rispetto alla soluzione Thread. Fidati di me uso il timeout del thread per un problema relativo, è orribile per le prestazioni. Finalmente risolvo il problema modificando il loop principale del mio algoritmo. Inserisco alcuni punti di controllo sul loop principale per testare l'ora.

Il dettaglio può essere trovato qui: https://swtch.com/~rsc/regexp/regexp1.html.