javascript - 为什么这个 JavaScript 正则表达式会在浏览器中崩溃？

据我所知，在尝试匹配一组字符时，[ab] 和 (a|b) 在目的上应该是等效的。现在，看看两个正则表达式:

/^(\s|\u00A0)+|(\s|\u00A0)+$/g
/^[\s\u00A0]+|[\s\u00A0]+$/g

它们都应该与字符串开头和结尾的空格匹配(有关正则表达式本身的更多信息，请参阅 Polyfill here 部分)。使用方括号时一切正常，但是当您切换到括号时，即使是最简单的字符串也会导致浏览器似乎无限期地运行。这发生在最新的 Chrome 和 Firefox 上。

This jsfiddle 证明了这一点:

a ="a                                                               b";

// Doesn't work
// alert(a.replace(/^(\s|\u00A0)+|(\s|\u00A0)+$/g,''));
// Works
alert(a.replace(/^[\s\u00A0]+|[\s\u00A0]+$/g,''));

这是浏览器实现正则表达式引擎的一个疯狂的怪癖，还是正则表达式算法的其他原因导致了这种情况？

最佳答案

您看到的问题称为灾难性回溯，如 here 所述。

首先，让我简化和澄清您的测试用例:

a = Array(30).join("\u00a0") + "b";  // A string with 30 consecutive \u00a0
s = Date.now();
t = a.replace(/^(\s|\u00A0)+$/g, '');
console.log(Date.now()-s, a.length);

发生的事情是表达式的第二部分: ^(\s|\u00A0)+$ 。请注意，\s 匹配许多空白字符，包括 \u00A0 本身。这意味着 \s 和 \u00A0 都匹配 30 个 \u00A0 字符中的每一个。

因此，如果您尝试将字符串与 /(\s|\u00A0)+/ 匹配，您会发现每个 2^30 30 个字符空白模式的不同组合都会导致匹配。当正则表达式匹配器匹配前 30 个字符时，它将尝试匹配字符串的结尾 ( $ ) 并失败，因此它会回溯并最终尝试所有 2^30 组合。

您的原始字符串(在 jsfiddle 中，stackflow 中的字符串已经“规范化”到所有空格)是 a \u00a0 \u00a0 ... \u00a0 b，大约有 30 个 \u00a0 字符，因此浏览器花了大约 2^30 的努力来完成。它不会挂起浏览器，但需要几分钟才能完成。

关于javascript - 为什么这个 JavaScript 正则表达式会在浏览器中崩溃？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30760557/