javascript - Jquery .replace 使浏览器崩溃

Question

这行代码(我相信)查找以 foo 开头并以 bar 结尾的子字符串，其中包含任何内容(包括换行符)，并将其从字符串中删除。

zip = string.replace(/foo(.|\s)*bar/, '');

出于某种原因，当我在其中放入一个非常大的字符串时，其中很大一部分不在 foo 和 bar 之间，它会使 Chrome 崩溃。 Chrome 不显示任何错误消息，控制台也不显示，但选项卡卡住，除了关闭之外拒绝执行任何操作。

外部内容相对较小时，不会崩溃，而 foo 和 bar 内部内容较多时，不会崩溃。这并不是因为字符串太大，JS 对字符串没有限制，并且其他 .replace 函数也可以处理相同大小的字符串。可能是正则表达式写得不好还是什么？

Answer 1

浏览器因正则表达式 /foo(.|\s)*bar/ 崩溃，而 /foo[\s\S]*bar/ 则不然由于回溯 hell ，皮特建议。

(未优化的)NFA 正则表达式引擎将尝试第一个分支，如果匹配失败，它将回溯到第二个分支。更好的引擎会分析语法，将.和\s组合成一个字符类，这样就不会浪费时间回溯。

让我们考虑这个输入:

foo           notba     other

对于正则表达式 /foo(.|\s)*bar/，因为空格 (ASCII 32) 可以匹配 . 和 \s，在.分支匹配失败后，会尝试\s分支:

foo           notba     other
   ^^^^^^^^^^^     ^^^^^

空格字符的数量是正则表达式引擎探索的二叉树的层数。如果字符串包含 foo 但不包含 bar，时间复杂度会随着空白字符的数量呈指数增长。

考虑pete的修改/foo[\s\S]*bar/，没有分支，因为所有内容都已由字符类检查过，所以当我们失败时回溯时，我们不会'没有任何未探索的分支，将很快返回失败。