¿Cancela una coincidencia de expresiones regulares de larga ejecución?

Question

Digamos que estoy ejecutando un servicio donde los usuarios pueden enviar una expresión regular para buscar a través de una gran cantidad de datos. Si el usuario envía una expresión regular que es muy lenta (es decir, demora minutos para que Matcher.find() regrese), quiero una manera de cancelar esa coincidencia. La única forma en que puedo pensar en hacer esto es hacer que otro subproceso controle cuánto tiempo lleva una coincidencia y use Thread.stop() para cancelarlo si es necesario.

las variables de miembro: hilo

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

Matcher: Hilo de

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

He leído java.sun.com/j2se/1.4.2/ docs/guide/misc/threadPrimitiveDeprecation.html y creo que este uso es seguro ya que estoy controlando dónde se lanza ThreadDeath a través de la sincronización y ha ndle y los únicos objetos dañados podrían ser mis instancias de Pattern y Matcher que se descartarán de todos modos. Creo que esto rompe Thread.stop() porque no estoy volviendo a lanzar el error, pero realmente no quiero que el hilo muera, solo aborte el método find().

He logrado evitar el uso de estos componentes de API obsoletos hasta el momento, pero Matcher.find() no parece ser interrumpible y puede demorar mucho tiempo en regresar. ¿Hay alguna forma mejor de hacer esto?

Answer 1

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

Envuelva su CharSequence con éste y el hilo interrupciones trabajarán ...

Answer 2

Otra solución sería limitar la region del emparejador, a continuación, llamar find() , repitiendo hasta que se interrumpa el hilo o se encuentre una coincidencia.

Answer 3

Con un poco de variación es posible evitar el uso de hilos adicionales para esto:

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

} 

Muchas gracias a dawce por dirigirme a esta solución en respuesta a una innecesaria complicada question!

Answer 4

Tal vez lo que necesita es una nueva lib que implementa el algoritmo de NFA.

El algoritmo de NFA es cientos veces más rápido que el algoritmo que utiliza la biblioteca estándar de Java.

Y Java std lib es sensible a la expresión regular de entrada, lo que puede hacer que su problema suceda, algunas entradas hacen que la CPU funcione durante años.

Y el tiempo de espera se puede establecer mediante el algoritmo NFA mediante los pasos que utiliza. Es efectivo que la solución Thread. Confíe en mí. Uso el tiempo de espera de subprocesos para un problema relativo, es horrible para el rendimiento. Finalmente soluciono el problema modificando el ciclo principal de mi implementación de algoritmo. Inserto un punto de control en el ciclo principal para probar la hora.

El detalle se puede encontrar aquí: https://swtch.com/~rsc/regexp/regexp1.html.