Java Regex muere en el desbordamiento de la pila: necesita una versión mejor

Question

Estoy trabajando en un JMD (Java MarkDown) (un puerto Java de MarkDownSharp) pero estoy teniendo un problema con una expresión regular en particular. Para el archivo de Markdown_Documentation_Syntax.text esta expresión regular muere:

private static final String BLOCK_TAGS_1 = "p|div|h[1-6]|blockquote|pre|table|dl|ol|ul|script|noscript|form|fieldset|iframe|math|ins|del"; 
private static final String BLOCKS_NESTED_PATTERN = String.format("" + 
     "(" +      // save in $1 
     "^" +      // start of line (with MULTILINE) 
     "<(%s)" +     // start tag = $2 
     "\\b" +     // word break 
     "(.*\\n)*?" +    // any number of lines, minimally matching 
     "</\\2>" +     // the matching end tag 
     "[ \\t]*" +    // trailing spaces/tags 
     "(?=\\n+|\\Z)" +   // followed by a newline or end of 
     ")", BLOCK_TAGS_1); 

que se traduce en:

(^<(p|div|h[1-6]|blockquote|pre|table|dl|ol|ul|script|noscript|form|fieldset|iframe|math|ins|del)\b(.*\n)*?</\2>[ \t]*(?=\n+|\Z)) 

Este patrón está buscando etiquetas de bloque aceptados que se anclan en el comienzo de una línea, seguido de cualquier número de líneas y luego terminan con una etiqueta coincidente seguida de una nueva línea o un terminador de cadena. Esto genera:

java.lang.StackOverflowError 
    at java.util.regex.Pattern$Curly.match(Pattern.java:3744) 
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168) 
    at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357) 
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227) 
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366) 
    at java.util.regex.Pattern$Curly.match0(Pattern.java:3782) 
    at java.util.regex.Pattern$Curly.match(Pattern.java:3744) 
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168) 
    at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357) 
     ... 

Esto puede ser tratado mediante el aumento del espacio de pila para Java (por defecto a 128k/400k para oss/ss IIRC), pero la expresión anterior es lento de todos modos.

Así que estoy buscando un gurú regex que pueda hacerlo mejor (o al menos explicar el problema de rendimiento con este patrón). La versión de C# es un poco lenta pero funciona bien. PHP parece no tener problemas con esto tampoco.

Editar: Esto es en JDK6u17 que se ejecuta en Windows 7 64 Ultimate.

Answer 1

Esta parte:

(.*\n)*? 

implicará un montón de retroceso innecesario debido a la anidada * y puesto que hay caracteres que tienen que coincidir después.

que acaba de ejecutar una referencia rápida en el Perl en algunas cadenas arbitrarias y conseguimos una mejora 13-15% simplemente cambiando esa pieza a

(?>.*\n)*? 

lo que hace no captura, subgrupo independiente. Eso le da dos beneficios, ya no desperdicia tiempo capturando la cadena correspondiente, y lo más importante, ya no da marcha atrás en el .* más interno, que de todos modos es una pérdida de tiempo. No hay forma de que solo una parte de eso * resulte en una coincidencia válida, por lo que hacerlo explícitamente o nada podría ayudar.

No sé si eso es una mejora suficiente en este caso, sin embargo.

Answer 2

Si bien la mejora del patrón ayuda y es aconsejable, el patrón de coincidencia de Java es recursivo y, en general, es mejor cambiar a una solución iterativa.

Cuando tuve problemas similares, cambié a jregex (http://jregex.sourceforge.net/) y eso funcionó para mí.

La coincidencia de patrón puede haber tenido éxito ahora con la solución mejorada, pero puede fallar si se proporcionó un texto 10 veces mayor.

PS

: Lo siento por necromancing un viejo tema, pero este hilo es altamente clasificado en Google y que sería beneficioso para las personas si lo pongo aquí

Answer 3

El sub-expresión: "(.*\\n)*?" (y la versión mejorada respuesta aceptada: "(?>.*\n)*?") , ambos tienen un problema: no coinciden con un elemento de bloque escrito en una línea.En otras palabras, no logran igualar esta:

<div>one-liner</div> 

Si este no es el comportamiento deseado, una solución correcta (y mucho más eficiente) es simplemente usar:

.*?

Y a su vez en modo de línea única.