RegExp y la cadena de combinación se estrella Chrome

Question

tengo la siguiente expresión regular para validar una dirección de correo electrónico:

^[A-Za-z0-9](([_\.\-]?[a-zA-Z0-9]+)*)@([A-Za-z0-9]+)(([\.\-]?[a-zA-Z0-9]+)*)\.([A-Za-z]{2,})$ 

ejecutarlo en un correo electrónico básico funciona de maravilla:

/^[A-Za-z0-9](([_\.\-]?[a-zA-Z0-9]+)*)@([A-Za-z0-9]+)(([\.\-]?[a-zA-Z0-9]+)*)\.([A-Za-z]{2,})$/.test('dave@the-taylors.org'); 

Pero ejecutarlo en una cadena larga se cuelga Chrome:

/^[A-Za-z0-9](([_\.\-]?[a-zA-Z0-9]+)*)@([A-Za-z0-9]+)(([\.\-]?[a-zA-Z0-9]+)*)\.([A-Za-z]{2,})$/.test('dddddddddddddddddddddddddddddddddddddddd'); 

Me he dado cuenta de que se activa alrededor de 40 caracteres

¿Qué tiene este RegExp que es tan intenso?

Answer 1

Bien, veamos qué está pasando aquí. Usted afortunadamente ya ha simplificado el problema a lo que sucede cuando se aplica la expresión regular

(d+)*@ 

a la cadena

ddddd 

que claramente no puede ser igualada porque el @ falta. Pero, ¿qué impide que el motor regex lo descubra rápidamente?

Bueno, (d+)*, en esencia, se puede cumplir con los siguientes resultados (cada grupo separados por espacios):

ddddd 
dddd d 
ddd dd 
dd ddd 
d dddd 
ddd d d 
dd d dd 
d d ddd 
dd dd d 
d dd dd 
d ddd d 
d d d dd 
d d dd d 
d dd d d 
dd d d d 
d d d d d 

Así que hay una manera de hacer coincidir la cadena, sin romper la cadena, cuatro maneras de romper se divide en dos cuerdas, seis maneras de dividirlo en tres, cuatro para dividirlo en cuatro, y uno para dividirlo en cinco cuerdas. Todas estas combinaciones deben ser verificadas por el motor de expresiones regulares antes de que pueda declarar la falla de coincidencia cuando finalmente tenga que enfrentar el siguiente @.

¿Por qué no se da cuenta de eso antes? Bueno, algunos motores de expresiones regulares pueden hacerlo con un ejemplo simplificado. Apuesto a que Larry Wall tiene eso cubierto. Pero tu expresión regular real es un poco más compleja, así que supongo que sería mucho más difícil averiguarlo de antemano. Además, hay una manera simple de garantizar toda esta combinación: el intento no ocurre. Pero volveré a eso más tarde.

me había estado preguntando cómo muchas de estas combinaciones no serían para una cadena más larga que aquellos insignificantes cinco d s:

Tomemos una cadena de longitud m (que se puede cortar aparte en m-1 posiciones diferentes). Digamos n = m-1.A continuación, se puede calcular el número de combinaciones de la siguiente manera:

1 + (n!/(1! * (n-1)!)) + (n!/(2! * (n-2)!)) + ... + (n!/(n! * (n-n)!)) 

Los primeros y últimos artículos son siempre 1, pero los elementos en el medio puede llegar a ser muy grande. Vamos a escribir un pequeño programa de Python:

>>> from math import factorial as f 
>>> def comb(n,x): 
... return f(n) // (f(x) * f(n-x)) 
... 
>>> def ways_to_split(len): 
... return 1 + sum(comb(len-1,x) for x in range(1,len)) 
... 
>>> ways_to_split(5) 
16 

OK, parece que funciona. Vamos a intentar algo más grande:

>>> ways_to_split(10) 
512 
>>> ways_to_split(40) 
549755813888 
>>> ways_to_split(100) 
633825300114114700748351602688 

Oye, hay un patrón aquí: ways_to_split(n) es igual a 2**(n-1). Ver Mathematics SE para una prueba. De todas formas. Su expresión regular tiene O(2^n) complejidad. Bueno, ahora ves por qué eso podría llevar un tiempo ...

Afortunadamente, muchos motores regex ofrecen protección contra esto: cuantificadores posesivos o grupos de captura atómica.

(d++)* 

o

(?>d+)* 

tanto asegurarse de que lo ha emparejado d+ no será cedido otra vez por intentar otras combinaciones. Buenas noticias, ¿verdad?

Bueno, no si utiliza JavaScript. No es compatible con ninguna de esas características.

Por lo tanto, sea necesario volver a escribir su expresión regular no ser susceptibles a dar marcha atrás como esto:

En lugar de

(([_\.\-]?[a-zA-Z0-9]+)*) 

uso

[a-zA-Z0-9]+([_.-][a-zA-Z0-9]+)* 

O deja de tratar de utilizar una expresión regular para validar una dirección de correo electrónico que no funciona confiablemente, nunca, de todos modos.

Answer 2

Creo que está relacionado con su expresión regular, no con la longitud de la cadena. Utilicé la siguiente expresión regular para la validación del correo electrónico y no se colgó en Chrome ...

/^(([^<>()[\]\\.,;:\s@\"]+(\.[^<>()[\]\\.,;:\s@\"]+)*)|(\".+\"))@((\[[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\])|(([a-zA-Z\-0-9]+\.)+[a-zA-Z]{2,}))$/.test('dddddddddddddddddddddddddddddddddddddddd'); 

Answer 3

No valide los correos electrónicos con expresión regular. Creo que esto era un conocimiento común desde hace unos veinte años. Es muy complejo. Un ejemplo de validación casi completa está aquí http://www.ex-parrot.com/~pdw/Mail-RFC822-Address.html e incluso eso no implementa completamente el estándar. Es mucho más simple escribir una función que haga lo mismo. Cuando puede validar partes del correo electrónico por separado, se vuelve trivial. Además, como es tu caso, la función haría esto mucho más rápido.

Answer 4

La raíz del problema está aquí:

[_.-]? 

Si el primer [A-Za-z0-9]+ (que quedaron fuera del +, por cierto) se queda sin caracteres alfanuméricos para consumir, y el siguiente carácter no es uno de los caracteres separadores ([_.-]), el intento de coincidencia debería fallar inmediatamente.

¿Qué pasa con su expresión regular es que las primeras aperturas [A-Za-z0-9]+ dar marcha atrás, renunciar a los personajes que sólo acertaron una por una, y dejar que el segundo [A-Za-z0-9]+ (dentro del bucle *) tratar a juego en su lugar. Hay muchas combinaciones que tiene que probar (como la respuesta de Tim tesis explica ☺), y todo es perfectamente inútil.

Ahora echar un vistazo a esto:

^[A-Za-z0-9]+([_.-][a-zA-Z0-9]+)*@[A-Za-z0-9]+([.-][a-zA-Z0-9]+)*\.[A-Za-z]{2,}$ 

Esta expresión regular no se entra en el bucle * a menos que realmente ve uno de los caracteres de separación.La subexpresión dentro del * puede ser opcional, pero sea lo que hace partido imprescindible comenzar con _, . o -. Del mismo modo, si la expresión regular logra hacer coincidir la parte local y el siguiente carácter no es @, rescata de inmediato, donde el suyo entra en otro paroxismo de retroceso.

De acuerdo con RegexBuddy, su expresión regular toma 57 pasos para que coincida con dave@the-taylors.org, donde la mía lo hace en 17 pasos. Y donde el tuyo se bloquea en la otra cadena, el mío informa una coincidencia fallida en 5 pasos.

La moraleja es: nunca use un cuantificador ? o * en algo que no sea realmente opcional.

---

responsabilidad: no estoy respaldando el uso de este o cualquier otra expresión regular para que coincida con direcciones de correo electrónico. Solo estoy explicando qué pasa con la expresión regular en la pregunta.