Retroceso Catastrófico
El retroceso catastrófico es un fenómeno en las expresiones regulares donde el motor tarda una cantidad excesiva de tiempo en evaluar ciertos patrones, lo que provoca una degradación significativa del rendimiento. Este problema puede ocurrir cuando el motor de expresiones regulares intenta repetidamente hacer coincidir partes de la cadena de diferentes maneras, especialmente con patrones complejos que involucran cuantificadores anidados.
¿Qué causa el retroceso catastrófico?
El retroceso catastrófico suele ocurrir al usar cuantificadores anidados en expresiones regulares. Estos cuantificadores permiten que las partes del patrón se hagan coincidir de múltiples maneras, lo que hace que el motor retroceda excesivamente. Aquí hay un ejemplo:
Si no tarda mucho en tu computadora, puedes agregar otro carácter a a la str. Entonces, ¿por qué está tomando tanto tiempo? Analicémoslo. El patrón /^(a+)+$/ consiste en:
^que afirma la posición al inicio de la cadena.(a+)que hace coincidir uno o más caracteresa.+que permite que el grupo anterior(a+)se repita una o más veces.$que afirma la posición al final de la cadena.
Ahora, el proceso de coincidencia es:
- Coincidencia inicial: El motor comienza al inicio de la cadena (
^). - Coincidencia del primer grupo: El motor hace coincidir el primer
a+, consumiendo todos los caracteresa(aaa...). - Cuantificador externo: El
+externo permite que el motor repita el grupo(a+).
Cuando el motor llega al signo de exclamación (!), no puede hacer coincidirlo con el patrón, lo que hace que la coincidencia falle. En este punto, comienza el retroceso:
- Intento de retroceso: El motor retrocede para dividir repetidamente los caracteres
acoincidentes entre los cuantificadores internosa+y externos+. Reevalúa cada división para ver si una partición diferente puede hacer coincidir el patrón hasta el final de la cadena. - Crecimiento exponencial: Este proceso de retroceso puede crecer exponencialmente a medida que el motor intenta cada forma posible de particionar la cadena de caracteres
aen diferentes grupos que potencialmente podrían coincidir con(a+)+.
Para una cadena de n caracteres a, el número de formas de particionarlas en grupos para (a+)+ puede ser considerable, lo que hace que el tiempo de evaluación aumente drásticamente.
Identificación de patrones propensos al retroceso catastrófico
Los patrones particularmente propensos al retroceso catastrófico a menudo incluyen:
- Cuantificadores anidados (p. ej.,
(a+)+) - Clases de caracteres superpuestas (p. ej.,
([a-zA-Z0-9_]+)+) - Subpatrones ambiguos que pueden coincidir de muchas maneras
Estrategias para prevenir el retroceso catastrófico
Para prevenir el retroceso catastrófico, considera las siguientes estrategias:
1. Reestructurar los cuantificadores anidados
Los cuantificadores no codiciosos no previenen el retroceso catastrófico en patrones anidados. En su lugar, reestructura la expresión regular para eliminar los cuantificadores anidados o usa cuantificadores acotados.
2. Optimiza tus expresiones regulares
Simplifica tus expresiones regulares para evitar complejidad y anidamiento innecesarios. Asegúrate de que cada parte del patrón sea lo más específica posible.
Ejemplos prácticos y soluciones
Ejemplo 1: Coincidencia de etiquetas HTML anidadas
Un caso de uso común para las expresiones regulares es hacer coincidir etiquetas HTML anidadas, lo que puede llevar fácilmente a un retroceso catastrófico si no se maneja correctamente. Nota: Las expresiones regulares generalmente no son adecuadas para analizar estructuras HTML arbitrarias o profundamente anidadas; utiliza un analizador HTML adecuado para documentos complejos.
Patrón problemático
Patrón mejorado
Ejemplo 2: Coincidencia de patrones repetidos
Patrón problemático
Patrón mejorado
Conclusión
El retroceso catastrófico puede afectar gravemente el rendimiento de tus aplicaciones JavaScript al usar expresiones regulares. Al comprender las causas e implementar estrategias como reestructurar patrones, evitar cuantificadores anidados y usar cuantificadores acotados, puedes prevenir estos problemas de rendimiento. Siempre prueba tus expresiones regulares con varias longitudes y complejidades de entrada para garantizar que funcionen de manera eficiente.
Práctica
¿Cuáles son las causas comunes del retroceso catastrófico en las expresiones regulares?