RegExp和String组合使Chrome崩溃

Question

我有以下RegExp来验证电子邮件地址:

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

在基本电子邮件上运行它可以很好地工作:

/^[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');

但是在长字符串上运行它会导致Chrome崩溃:

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

我注意到它大约有40个字符

这个RegExp是如此密集的是什么？

Answer 1

好的,让我们看看这里发生了什么.幸运的是,您已经将问题简化为应用正则表达式时会发生的情况

(d+)*@

到字符串

ddddd

由于@缺失,显然无法匹配.但是什么阻止了正则表达式引擎快速搞清楚了？

好吧,(d+)*实质上可以通过以下匹配来实现(每个组用空格分隔):

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

所以你有一种方法可以匹配字符串而不会破坏字符串,四种方法可以将其分解为两个字符串,六种方法将其分解为三种,四种方法将其分解为四种,一种方法将其分解为五种字符串.所有这些组合必须由正则表达式引擎检查,然后才能在最终必须面对以下内容时声明匹配失败@.

为什么不早点算出来？好吧,一些正则表达式引擎可以用这样一个简化的例子来做.我打赌拉里沃尔有这个.但是你的实际正则表达式有点复杂,所以我想事先要弄清楚会更难.此外,有一种简单的方法可以确保所有这些组合 - 尝试不会发生.但是我稍后会回来的.

我一直想知道有多少这样的组合会比那些微不足道的五个更长的字符串d:

让我们取一串长度m(可以在m-1不同的位置分开).让我们说吧n = m-1.然后您可以按如下方式计算组合数:

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

第一个和最后一个项目始终为1,但介于两者之间的项目可能会非常大.我们来写一个小的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

好的,似乎工作.让我们尝试更大的东西:

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

嘿,这里有一个模式:ways_to_split(n)等于2**(n-1).有关证明,请参阅数学SE.无论如何.你的正则表达式很O(2^n)复杂.那么,现在你明白为什么这可能需要一段时间......

值得庆幸的是,许多正则表达式引擎提供了对此的保护:占有量词或原子捕获组.

(d++)*

要么

(?>d+)*

两者都确保任何d+匹配的东西不会再次放弃尝试其他组合.好消息,对吧？

好吧,不是你使用JavaScript.它不支持这些功能.

因此,你需要重写你的正则表达式,不要像这样容易回溯:

代替

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

使用

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

或者,不管怎样,还是停止尝试使用正则表达式来验证无法可靠运行的电子邮件地址.