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

Question

据我所知，[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,''));

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

Answer 1

如解释的那样，您看到的问题称为灾难性回溯 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 的努力才能完成。它不会挂起浏览器，但需要几分钟才能完成。