javascript - 为什么这段代码会导致 Chrome 卡住？

Question

我正在尝试调试我的应用程序中的一个问题，我已将其缩小为涉及导致 Chrome 阻塞的正则表达式的特定情况!在 Firefox 中尝试相同的代码工作正常。此外，如果我减少我的“示例”文本以在其上运行正则表达式，它也可以工作。

那么是什么给了？

这是 jsfiddle:http://jsfiddle.net/XWKRb/1/(这将完全无法初始化，因为如果您得到与我相同的结果，Chrome 会窒息)

我放在 jsfiddle 中的代码是:

var rgx = /^(\d+([,|;]?\d*))*$/;
var sample = '40162690,40162755,40162691,40168355,40168357,40162726,40162752,40162729,40428707 ,40162740,40162546';
alert("Test is "+rgx.test(sample));

也许有更好的方法来编写我的正则表达式来避免这个问题？目标是正则表达式应捕获一串由逗号或分号分隔的数字。

Answer 1

你有一个 catastrophic backtracking 的经典案例:

^(\d+([,|;]?\d*))*$
    ^      ^  ^  ^
    |      |  |  ---- zero or more repetitions of the group 
    |      |  ------- zero or more digits
    |      ---------- zero or one comma, pipe or semicolon
    ----------------- one or more digits

包含一个重复组，其中包含可选元素，其中一个元素本身是重复的。现在忽略分隔符，你基本上有正则表达式

^(\d+\d*)*$

在最坏的情况下，这会导致您的正则表达式必须检查的排列呈指数级增长。

一旦在您的字符串中找到除了允许的字符之外的另一个字符(例如示例中的空格)，正则表达式肯定会失败 - 但引擎需要很长时间才能解决这个问题。一些浏览器会检测到这种失控的正则表达式匹配，但 Chrome 似乎希望渡过难关。

为了说明这一点，在 RegexBuddy 中测试您的正则表达式显示以下内容:

Input             Steps to determine a non-match
1,1X                   23
12,21X                119
123,321X              723
1234,4321X          4,743
12345,54321X       31,991
123456,654321X    217,995
1234567,7654321X  attempt aborted after 1,000,000 steps