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

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.

Variables de miembros:

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

Subproceso de Matcher:

 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 } 

Hilo del 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 lo manejo y el único dañado los objetos 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 la API en desuso hasta el momento, pero Matcher.find () no parece ser interrumpible y puede tardar mucho tiempo en regresar. ¿Hay alguna forma mejor de hacer esto?

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 este y las interrupciones del hilo funcionarán …

Con una pequeña 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 por dirigirme a esta solución en respuesta a una pregunta innecesaria y complicada!

Otra solución sería limitar la región de la coincidencia, luego llame a find() , repitiendo hasta que se interrumpa el hilo o se encuentre una coincidencia.

Quizás lo que necesitas es una nueva lib que implemente el algoritmo de NFA.

El algoritmo de NFA es cientos veces más rápido que el algoritmo utilizado por 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; algunos datos de entrada hacen que la CPU funcione durante años.

Y el tiempo de espera puede establecerse mediante el algoritmo NFA a través de 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 .