Pattern.matches() da StackOverflowError

Question

Estoy usando Pattern.matches de java para hacer coincidir un bloque de datos con una expresión regular. El bloque de datos puede ser una sola línea o múltiples líneas. El problema es que una vez que mis datos se convierten en más de 15 líneas (típicamente más de 17-18 líneas), empiezo a recibir stackoverflowerror. Para datos de menos de 15 líneas, la expresión regular funciona bien.

la expresión regular es de este formato:
nombre de dominio -> espacio ->, -> espacio -> número -> espacio ->, -> espacio -> número -> nueva línea

String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$"; 

Los datos bloque que utilizo para la prueba en contra de esta expresión regular es este

abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 

este es el código:

String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$"; 
boolean valid = Pattern.matches(regex, data); //fails here 

Answer 1

No puedo decirte el motivo de este error; la expresión regular está bien y no está sujeta a un retroceso catastrófico ni a ningún otro error obvio.

Tal vez se puede reducir el número de puestos de rastreo hasta que el motor de expresiones regulares ahorra mediante el uso de possessive quantifiers (++ en lugar de +, en lugar de *+*, {2,}+ en lugar de {2,} etc.). Además, no es necesario los grupos de captura (gracias Thomas), así que les he cambiado en los no captura:

"(?:(?:[a-zA-Z0-9][a-zA-Z0-9-]*+\\.)++([a-zA-Z]{2,}+)\\s*+,\\s*+\\d++\\s*+,\\s*+\\d++(\r?+\n)?+)++" 

Esto no va a cambiar el comportamiento de la expresión regular (a excepción de la eliminación de los anclajes innecesarios ya que está usando Pattern.matches()), pero quizás ayude a evitar StackOverflows. No tengo instalado un Java SDK, pero no puedo probarlo solo.

Answer 2

He reproducido este problema, pero solo para cadenas mucho más grandes.

$ java -version 
java version "1.6.0_22" 
OpenJDK Runtime Environment (IcedTea6 1.10.2) (6b22-1.10.2-0ubuntu1~11.04.1) 
OpenJDK 64-Bit Server VM (build 20.0-b11, mixed mode) 

Mi código de prueba:

public class Testje 
{ 
    public static void main(String... args) 
    { 
     String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$"; 
     String data = ""; 
     for (int i = 0; i<224; i++) data += "abc.com, 123, 456\n"; 
     System.out.println(data.matches(regex)); 
    } 
} 

Para algo más pequeño que 224 porque para el bucle, el código se ejecuta bien. Para 224 y más copias de esa línea, obtengo un gran rastro de pila.

Oh, tenga en cuenta que el uso de (?: Grupos no cambia el tamaño de la cadena que todavía funciona

Answer 3

Se podría tratar de utilizar grupos atómicos ((?>expression)) para evitar el retroceso:.

Aquí está una prueba esto falló con un bloque de 1.000 líneas utilizando su expresión regular pero funcionaba ahora (toma un tiempo, por lo que sólo probado con 20000 :)):

String regex = "(?>(?>[a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+(?>[a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(?>\\r?\\n)?)+"; 

StringBuilder input = new StringBuilder(); 

for(int i = 0; i < 1000000; ++i) { 
    input.append("abc.com, 123, 456\n"); 
} 

Pattern p = Pattern.compile(regex); 
Matcher m = p.matcher(input); 

System.out.println(m.matches()); 

Así que después de todo, podría todavía ser un retroceso problema de ing.

Actualización: simplemente deje que la prueba se ejecute con 20000 líneas y aún así no falló. Eso es al menos 20 veces más que antes. :)

Actualización 2: mirando mi prueba nuevamente encontré la parte lenta, la concatenación de cadenas. (o..O).Actualicé la prueba y usé 1 millón de líneas, todavía no falla. :)

Answer 4

El problema es que su expresión regular es demasiado complicada. Cada línea de entrada que procesa da como resultado (creo) 10 puntos de retroceso, y al menos algunos de ellos parecen ser manejados por la recursión del motor de expresiones regulares. Eso podría ser unos pocos cientos de marcos de pila que serían suficientes para darle StackOverflowError.

OMI, resulta necesario modificar el patrón de modo que coincidirá con un grupo/línea de datos. Luego, llame al Matcher.find repetidamente para analizar cada línea. Espero que encuentres que esto es más rápido.

---

Optimizar la expresión regular de otras maneras sin dejar de intentar hacer coincidir todo el bloque de una vez, probablemente no funcionará. Puede lograr que coincida N veces más líneas de datos, pero a medida que aumenta el número de líneas en la entrada es probable que vuelva a encontrarse con el mismo problema.

Y aunque consiga que funcione como una expresión regular multilínea, existe la posibilidad de que no funcione con otras implementaciones de las bibliotecas regex de Java; p.ej. en Oracle JRE más antiguas o implementaciones que no son de Oracle.

---

Estoy de acuerdo con las otras respuestas que este no es un ejemplo de "retroceso catastrófico". Más bien es una interacción entre la forma en que el motor de expresiones regulares maneja los puntos de retroceso, y el hecho de que hay demasiados cuando le das varias líneas de entrada.