Backtracking catastrófico

Algunas expresiones regulares parecen simples, pero pueden ejecutarse durante demasiado tiempo e incluso “colgar” el motor de JavaScript.

Tarde o temprano la mayoría de los desarrolladores se enfrentan ocasionalmente a este comportamiento. El síntoma típico: una expresión regular funciona bien a veces, pero para ciertas cadenas se “cuelga” consumiendo el 100% de la CPU.

En este caso el navegador sugiere matar el script y recargar la página. No es algo bueno, sin duda.

Para el lado del servidor de JavaScript tal regexp puede colgar el proceso del servidor, que es aún peor. Así que definitivamente deberíamos echarle un vistazo.

Ejemplo

Supongamos que tenemos una cadena y queremos comprobar si está formada por palabras \w+ con un espacio opcional \s? después de cada una.

Una forma obvia de construir una regexp sería tomar una palabra seguida de un espacio opcional \w+\s? y luego repetirla con *.

Esto nos lleva a la regexp ^(\w+\s?)*$ que especifica cero o más palabras de este tipo, que comienzan al principio ^ y terminan al final $ de la línea.

En la práctica:

let regexp = /^(\w+\s?)*$/;

alert( regexp.test("A good string") ); // true
alert( regexp.test("Bad characters: $@#") ); // false

La regexp parece funcionar. El resultado es correcto. Aunque en ciertas cadenas tarda mucho tiempo. Tanto tiempo que el motor de JavaScript se “cuelga” con un consumo del 100% de la CPU.

Si ejecuta el ejemplo de abajo probablemente no se verá nada ya que JavaScript simplemente se “colgará”. El navegador dejará de reaccionar a los eventos, la interfaz de usuario dejará de funcionar (la mayoría de los navegadores sólo permiten el desplazamiento). Después de algún tiempo se sugerirá recargar la página. Así que ten cuidado con esto:

let regexp = /^(\w+\s?)*$/;
let str = "An input string that takes a long time or even makes this regexp hang!";

// tardará mucho tiempo
alert( regexp.test(str) );

Para ser justos observemos que algunos motores de expresión regular pueden manejar este tipo de búsqueda con eficacia, por ejemplo, la versión del motor V8 a partir de la 8.8 puede hacerlo (por lo que Google Chrome 88 no se cuelga aquí) mientras que el navegador Firefox sí se cuelga.

Ejemplo simplificado

¿Qué ocurre? ¿Por qué se cuelga la expresión regular?

Para entenderlo simplifiquemos el ejemplo: elimine los espacios \s?. Entonces se convierte en ^(\w+)*$.

Y, para hacer las cosas más obvias sustituyamos \w por \d. La expresión regular resultante sigue colgando, por ejemplo:

let regexp = /^(\d+)*$/;

let str = "012345678901234567890123456789z";

// tardará mucho tiempo (¡cuidado!)
alert( regexp.test(str) );

¿Qué ocurre con la regexp?

En primer lugar uno puede notar que la regexp (\d+)* es un poco extraña. El cuantificador * parece extraño. Si queremos un número podemos utilizar \d+.

Efectivamente la regexp es artificial; la hemos obtenido simplificando el ejemplo anterior. Pero la razón por la que es lenta es la misma. Así que vamos a entenderlo y entonces el ejemplo anterior se hará evidente.

¿Qué sucede durante la búsqueda de ^(\d+)*$ en la línea 123456789z (acortada un poco para mayor claridad, por favor tenga en cuenta un carácter no numérico z al final, es importante) que tarda tanto?

Esto es lo que hace el motor regexp:

1. En primer lugar el motor regexp intenta encontrar el contenido de los paréntesis: el número d+. El + es codicioso por defecto, por lo que consume todos los dígitos:

   \d+.......
   (123456789)z

   Una vez consumidos todos los dígitos se considera que se ha encontrado el d+ (como 123456789).

   Entonces se aplica el cuantificador de asterisco (\d+)*. Pero no hay más dígitos en el texto, así que el asterisco no da nada.

   El siguiente carácter del patrón es el final de la cadena $. Pero en el texto tenemos z en su lugar, por lo que no hay coincidencia:

              X
   \d+........$
   (123456789)z

2. Como no hay ninguna coincidencia, el cuantificador codicioso + disminuye el recuento de repeticiones, retrocede un carácter.

   Ahora \d+ toma todos los dígitos excepto el último (12345678):

   \d+.......
   (12345678)9z

3. Entonces el motor intenta continuar la búsqueda desde la siguiente posición (justo después de 12345678).

   Se puede aplicar el asterisco patrón:(\d+)* : da una coincidencia más de patrón:\d+, el número 9:

   \d+.......\d+
   (12345678)(9)z

   El motor intenta coincidir con $ de nuevo, pero falla, porque encuentra z en su lugar:

                X
   \d+.......\d+
   (12345678)(9)z

4. No hay coincidencia así que el motor continuará con el retroceso disminuyendo el número de repeticiones. El retroceso generalmente funciona así: el último cuantificador codicioso disminuye el número de repeticiones hasta llegar al mínimo. Entonces el cuantificador codicioso anterior disminuye, y así sucesivamente.

   Se intentan todas las combinaciones posibles. Estos son sus ejemplos.

   El primer número \d+ tiene 7 dígitos y luego un número de 2 dígitos:

                X
   \d+......\d+
   (1234567)(89)z

   El primer número tiene 7 dígitos y luego dos números de 1 dígito cada uno:

                  X
   \d+......\d+\d+
   (1234567)(8)(9)z

   El primer número tiene 6 dígitos y luego un número de 3 dígitos:

                X
   \d+.......\d+
   (123456)(789)z

   El primer número tiene 6 dígitos, y luego 2 números:

                  X
   \d+.....\d+ \d+
   (123456)(78)(9)z

   …Y así sucesivamente.

Hay muchas formas de dividir una secuencia de dígitos 123456789 en números. Para ser precisos, hay 2n-1, donde n es la longitud de la secuencia.

• Para 123456789 tenemos n=9, lo que da 511 combinaciones.
• Para una secuencia más larga con “n=20” hay alrededor de un millón (1048575) de combinaciones.
• Para n=30 – mil veces más (1073741823 combinaciones).

Probar cada una de ellas es precisamente la razón por la que la búsqueda lleva tanto tiempo.

Volver a las palabras y cadenas

Lo mismo ocurre en nuestro primer ejemplo, cuando buscamos palabras por el patrón ^(\w+\s?)*$ en la cadena An input that hangs!.

La razón es que una palabra puede representarse como un \w+ o muchos:

(input)
(inpu)(t)
(inp)(u)(t)
(in)(p)(ut)
...

Para un humano es obvio que puede no haber coincidencia porque la cadena termina con un signo de exclamación ! pero la expresión regular espera un carácter denominativo \w o un espacio \s al final. Pero el motor no lo sabe.

El motor prueba todas las combinaciones de cómo la regexp (\w+\s?)* puede “consumir” la cadena, incluyendo las variantes con espacios (\w+\s)* y sin ellos (\w+)* (porque los espacios \s? son opcionales). Como hay muchas combinaciones de este tipo (lo hemos visto con dígitos), la búsqueda lleva muchísimo tiempo.

¿Qué hacer?

¿Debemos activar el lazy mode?

Desgraciadamente eso no ayudará: si sustituimos \w+ por \w+? la regexp seguirá colgada. El orden de las combinaciones cambiará, pero no su número total.

Algunos motores de expresiones regulares hacen análisis complicados y automatizaciones finitas que permiten evitar pasar por todas las combinaciones o hacerlo mucho más rápido, pero la mayoría de los motores no lo hacen. Además, eso no siempre ayuda.

¿Cómo solucionarlo?

Hay dos enfoques principales para solucionar el problema.

El primero es reducir el número de combinaciones posibles.

Hagamos que el espacio no sea opcional reescribiendo la expresión regular como ^(\w+\s)*\w*$ buscaremos cualquier número de palabras seguidas de un espacio (\w+\s)*, y luego (opcionalmente) una palabra final \w*.

Esta regexp es equivalente a la anterior (coincide con lo mismo) y funciona bien:

let regexp = /^(\w+\s)*\w*$/;
let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false

¿Por qué ha desaparecido el problema?

Porque ahora el espacio es obligatorio.

La regexp anterior, si omitimos el espacio, se convierte en (\w+)*, dando lugar a muchas combinaciones de \w+ dentro de una misma palabra

Así, input podría coincidir con dos repeticiones de \w+ así:

\w+  \w+
(inp)(ut)

El nuevo patrón es diferente: (\w+\s)* especifica repeticiones de palabras seguidas de un espacio. La cadena input no puede coincidir con dos repeticiones de \w+\s, porque el espacio es obligatorio.

Ahora se ahorra el tiempo necesario para probar un montón de combinaciones (en realidad la mayoría).

Previniendo el backtracking

Sin embargo no siempre es conveniente reescribir una regexp. En el ejemplo anterior era fácil, pero no siempre es obvio cómo hacerlo.

Además una regexp reescrita suele ser más compleja y eso no es bueno. Las regexps son suficientemente complejas sin necesidad de esfuerzos adicionales.

Por suerte hay un enfoque alternativo. Podemos prohibir el retroceso para el cuantificador.

La raíz del problema es que el motor de regexp intenta muchas combinaciones que son obviamente erróneas para un humano.

Por ejemplo, en la regexp (\d+)*$ es obvio para un humano que patrón:+ no debería retroceder. Si sustituimos un patrón:\d+ por dos \d+\d+ separados nada cambia:

\d+........
(123456789)!

\d+...\d+....
(1234)(56789)!

Y en el ejemplo original ^(\w+\s?)*$ podemos querer prohibir el backtracking en \w+. Es decir: \w+ debe coincidir con una palabra entera, con la máxima longitud posible. No es necesario reducir el número de repeticiones en \w+ o dividirlo en dos palabras \w+\w+ y así sucesivamente.

Los motores de expresiones regulares modernos admiten cuantificadores posesivos para ello. Los cuantificadores regulares se convierten en posesivos si añadimos + después de ellos. Es decir, usamos \d++ en lugar de \d+ para evitar que + retroceda.

Los cuantificadores posesivos son de hecho más simples que los “regulares”. Simplemente coinciden con todos los que pueden sin ningún tipo de retroceso. El proceso de búsqueda sin retroceso es más sencillo.

También existen los llamados “grupos de captura atómicos”, una forma de desactivar el retroceso dentro de los paréntesis.

…Pero la mala noticia es que, por desgracia, en JavaScript no están soportados.

Sin embargo, podemos emularlos utilizando “lookahead transform”.

Lookahead al rescate!

Así que hemos llegado a temas realmente avanzados. Nos gustaría que un cuantificador como + no retrocediera porque a veces retroceder no tiene sentido.

El patrón para tomar tantas repeticiones de \w como sea posible sin retroceder es: (?=(\w+))\1. Por supuesto, podríamos tomar otro patrón en lugar de \w.

Puede parecer extraño, pero en realidad es una transformación muy sencilla.

Vamos a descifrarla:

• Lookahead ?= busca la palabra más larga \w+ a partir de la posición actual.
• El contenido de los paréntesis con ?=... no es memorizado por el motor así que envuelva \w+ en paréntesis. Entonces el motor memorizará su contenido
• …y nos permitirá hacer referencia a él en el patrón como \1.

Es decir: miramos hacia adelante y si hay una palabra \w+, entonces la emparejamos como \1.

¿Por qué? Porque el lookahead encuentra una palabra \w+ como un todo y la capturamos en el patrón con \1. Así que esencialmente implementamos un cuantificador posesivo más +. Captura sólo la palabra entera patrón:\w+, no una parte de ella.

Por ejemplo, en la palabra JavaScript no sólo puede coincidir con Java sino que deja fuera Script para que coincida con el resto del patrón.

He aquí la comparación de dos patrones:

alert( "JavaScript".match(/\w+Script/)); // JavaScript
alert( "JavaScript".match(/(?=(\w+))\1Script/)); // null

1. En la primera variante, \w+ captura primero la palabra completa JavaScript, pero luego + retrocede carácter por carácter, para intentar coincidir con el resto del patrón, hasta que finalmente tiene éxito (cuando \w+ coincide con Java).
2. En la segunda variante (?=(\w+)) mira hacia adelante y encuentra la palabra JavaScript, que está incluida en el patrón como un todo por \1, por lo que no hay manera de encontrar Script después de ella.

Podemos poner una expresión regular más compleja en (?=(\w+))\1 en lugar de \w, cuando necesitemos prohibir el retroceso para + después de ella.

Reescribamos el primer ejemplo utilizando lookahead para evitar el backtracking:

let regexp = /^((?=(\w+))\2\s?)*$/;

alert( regexp.test("A good string") ); // true

let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false, funciona, ¡y rápido!

Aquí se utiliza \2 en lugar de \1 porque hay paréntesis exteriores adicionales. Para evitar enredarnos con los números, podríamos dar a los paréntesis un nombre, por ejemplo (?<word>\w+).

// nombramos a los parentesis ?<word>, y los referenciamos como \k<word>
let regexp = /^((?=(?<word>\w+))\k<word>\s?)*$/;

let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false

alert( regexp.test("A correct string") ); // true

El problema descrito en este artículo se llama “backtracking catastrófico”.

Cubrimos dos formas de resolverlo:

• Reescribir la regexp para reducir el número de combinaciones posibles.
• Evitar el retroceso.