Im utilizando esta expresión regular para obtener el contenido de una etiqueta en un archivo.Javascript regex cuelga (usando v8)
var regex = new RegExp("<tag:main>((?:.|\\s)*)</tag:main>");
Esto hace que el motor V8 para colgar indefinidamente.
Ahora, si uso new RegExp("<tag:main>([\s\S]*)</tag:main>"), todo está bien.
¿Alguien tiene una idea de por qué la primera tarda demasiado?
Esto retrocede catastróficamente en largas secuencias de espacios que se producen después de la última etiqueta de cierre </tag:main>. Considere el caso donde la secuencia de asunto termina con 100 espacios. Primero, los compara a todos con el . a la izquierda de la alternancia. Eso falla porque no hay una etiqueta de cierre, por lo que intenta hacer coincidir el último carácter con el \s. Eso también falla, por lo que intenta hacer coincidir el penúltimo espacio como \s y el último espacio como .. Eso falla (aún no hay etiqueta de cierre) por lo que intenta el último espacio como \s. Cuando eso falla, coincide con el penúltimo espacio como \s y prueba las 4 formas de hacer coincidir los dos últimos espacios. Cuando eso falla, intenta el penúltimo espacio como \s y las 8 formas en los últimos 3 espacios. Luego 16, 32, etc. El universo termina antes de que llegue al centésimo penúltimo espacio.
Diferentes máquinas virtuales tienen diferentes reacciones a las coincidencias de expresiones regulares que demoran una eternidad debido a un retroceso catastrófico. Algunos simplemente informarán 'no coincidencia'. En V8 es como escribir cualquier otro ciclo infinito o casi infinito.
El uso no expansivo * va a hacer lo que quiere (desea parar en la primera </tag:main>, no el último), pero todavía va a hacer marcha atrás catastrófico para largas cadenas de espacios en los que la secuencia de cierre están.
Asegurarse de que los mismos caracteres en el soporte interno no pueden coincidir con ambos lados de la alternancia reducirá el problema de uno a uno exponencial que es lineal en la longitud de la cadena. Utilice una clase de caracteres en lugar de una alternancia o ponga \n en el lado derecho de la barra de alternancia. \n es disjunto con ., por lo que si acierta en una secuencia larga de espacios, el motor de expresiones regulares no probará todas las combinaciones izquierda-derecha-izquierda, etc. antes de finalizar.
Buena explicación. ¿Sabes por casualidad si dot incluye \ r también? –
@Martin: en JavaScript, '.' es equivalente a' [^ \ r \ n \ u2028 \ u2029] ' –
@Alan - ¡Gracias! –
Supongo que es catastróficamente un seguimiento posterior.
Creo que parte del problema puede ser que el punto y \ s no son mutuamente excluyentes.
Si cambio su expresión a
<tag:main>((?:.|[\r\n])*)</tag:main>
y ejecutarlo en el depurador de expresiones regulares de amigos que falla mucho más rápido en el caso de que la cadena de prueba no es una coincidencia.
. | \ S es para unir todos los caracteres. Porque . coincide con todos los caracteres excepto la nueva línea. – Engwan
No creo que vaya a hacer eso. Pegué tu Regex en RegexBuddy y pegué su árbol de comentarios en mi publicación. –
Debe eliminar el extra antes de pegar en RegexBuddy. El \\ se usa porque es una cadena javascript pasada al constructor RegExp. – Engwan
En lugar de (?:.|\s)*, puede usar [^]* para que coincida con cualquier carácter, incluidas varias formas de nueva línea.
No hay alternancia, por lo que no hay riesgo de retroceso catastrófico.
la creación de la expresión regular se bloquea o la aplicación de la misma? La línea que publicaste funciona bien para mí – cobbal
La creación no cuelga, solo usándola a través de prueba o coincidencia. usando cadenas largas – Engwan
¿Has probado un partido no codicioso?'var regex = new RegExp (" ((?:. | \\ s) *?) ");'. Su expresión regular puede causar problemas si hay varios elementos de etiqueta en el documento. –