灾难性回溯

一起看海

有些正则表达式看起来很简单，但执行起来耗时却非常长，甚至会导致 JavaScript 引擎“挂起”。

大多数开发者迟早会遇到这样的情况。典型的症状就是 —— 正则表达式有时可以正常工作，但对于某些字符串，它会消耗 100% 的 CPU 算力，出现“挂起”的现象。

在这种情况下，Web 浏览器会建议终止脚本并重新加载页面。这显然不是我们愿意看到的。

对于服务器端 JavaScript，这样的正则表达式可能会挂起服务器进程，这甚至更糟。所以我们绝对应该研究研究它。

举例
假设，我们现在有一个字符串，我们想检查其中是否包含一些后面跟着可选空格 \s? 的单词 \w+。

构造此正则表达式最显而易见的方式是一个单词后跟着一个可选空格 \w+\s?，然后用 * 重复它。

写成正则表达式即 ^(\w+\s?)*$，它指定 0 个及以上这样的词，从开头 ^ 开始，并在行的结尾 $ 结束。

运行一下：

let regexp = /^(\w+\s?)*$/;

alert( regexp.test("A good string") ); // true
alert( regexp.test("Bad characters: $@#") ); // false
这似乎能正常工作。结果是正确的。但在特定的字符串上，它会消耗很多时间。它耗时太久以至于让 CPU 会跑满 100% 负载，导致 JavaScript 引擎“挂起”。

如果你运行下面这个例子，由于 JavaScript 会进导致“挂起”，所以你可能什么结果都看不到。此时浏览器会停止对事件的响应，UI 也会停止工作。一段时间之后，浏览器会建议重新加载页面。所以请谨慎对待：

let regexp = /^(\w+\s?)*$/;
let str = "An input string that takes a long time or even makes this regexp hang!";

// 会耗费很长时间
alert( regexp.test(str) );
有一些正则表达式引擎可以很好地处理这样的搜索，例如从 8.8 版本开始的 V8 引擎（因此 88 及以上版本的 Google Chrome 不会在这里挂起），而火狐（Firefox）浏览器确实会挂起。