灾难性回溯

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

大多数开发人员迟早都会遇到这种行为。典型的症状是，正则表达式有时可以正常工作，但对于某些字符串，它会“挂起”，占用100%的CPU。

在这种情况下，网页浏览器会建议终止脚本并重新加载页面。这当然不是一件好事。

对于服务器端 JavaScript，这样的正则表达式可能会挂起服务器进程，这更糟糕。因此，我们绝对应该看看它。

示例

假设我们有一个字符串，我们想检查它是否由单词 \w+ 组成，每个单词后面可以有一个可选的空格 \s?。

构建正则表达式的明显方法是取一个单词，后面跟着一个可选的空格 \w+\s?，然后用 * 重复它。

这将我们引向正则表达式 ^(\w+\s?)*$，它指定零个或多个这样的单词，从开头 ^ 开始，并在行尾 $ 结束。

在行动中

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

alert( regexp.test("A good string") ); // true
alert( regexp.test("Bad characters: $@#") ); // false

正则表达式似乎有效。结果是正确的。虽然，在某些字符串上，它需要很长时间。时间之长以至于 JavaScript 引擎会以 100% 的 CPU 占用率“挂起”。

如果您运行下面的示例，您可能不会看到任何东西，因为 JavaScript 只是会“挂起”。网页浏览器将停止对事件做出反应，UI 将停止工作（大多数浏览器只允许滚动）。一段时间后，它会建议重新加载页面。所以要小心这一点。

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

// will take a very long time
alert( regexp.test(str) );

公平地说，让我们注意到，一些正则表达式引擎可以有效地处理这种搜索，例如从 8.8 版本开始的 V8 引擎可以做到这一点（因此 Google Chrome 88 不会在这里挂起），而 Firefox 浏览器会挂起。

简化示例

问题出在哪里？为什么正则表达式会挂起？

为了理解这一点，让我们简化示例：删除空格 \s?。然后它变成 ^(\w+)*$。

并且，为了使事情更明显，让我们用 \d 替换 \w。生成的正则表达式仍然会挂起，例如

let regexp = /^(\d+)*$/;

let str = "012345678901234567890123456789z";

// will take a very long time (careful!)
alert( regexp.test(str) );

那么正则表达式有什么问题？

首先，人们可能会注意到正则表达式 (\d+)* 有点奇怪。量词 * 看起来多余。如果我们想要一个数字，我们可以使用 \d+。

事实上，正则表达式是人为的；我们通过简化之前的示例得到了它。但它慢的原因是一样的。所以让我们理解它，然后之前的例子就会变得很明显。

在行 123456789z 中搜索 ^(\d+)*$ 时会发生什么（为了清晰起见，稍微缩短了一下，请注意末尾的非数字字符 z，这一点很重要），为什么它需要这么长时间？

以下是正则表达式引擎所做的

1. 首先，正则表达式引擎尝试找到括号的内容：数字 \d+。默认情况下，加号 + 是贪婪的，因此它会消耗所有数字

   \d+.......
   (123456789)z

   消耗完所有数字后，\d+ 被认为已找到（作为 123456789）。

   然后，星号量词 (\d+)* 应用。但是文本中没有更多数字，所以星号不会给出任何东西。

   模式中的下一个字符是字符串结尾 $。但在文本中我们有 z，所以没有匹配

              X
   \d+........$
   (123456789)z

2. 由于没有匹配，贪婪量词 + 会减少重复次数，向后回溯一个字符。

   现在 \d+ 获取除最后一个以外的所有数字 (12345678)

   \d+.......
   (12345678)9z

3. 然后引擎尝试从下一个位置（紧接在 12345678 之后）继续搜索。

   星号 (\d+)* 可以应用 - 它会匹配 \d+ 的另一个匹配项，数字 9

   \d+.......\d+
   (12345678)(9)z

   引擎尝试再次匹配 $，但失败了，因为它遇到了 z

                X
   \d+.......\d+
   (12345678)(9)z

4. 没有匹配项，因此引擎将继续回溯，减少重复次数。回溯通常按以下方式工作：最后一个贪婪量词会减少重复次数，直到达到最小值。然后，前一个贪婪量词会减少，依此类推。

   所有可能的组合都会尝试。以下是它们的示例。

   第一个数字 \d+ 有 7 位数字，然后是一个 2 位数字

                X
   \d+......\d+
   (1234567)(89)z

   第一个数字有 7 位数字，然后是两个 1 位数字

                  X
   \d+......\d+\d+
   (1234567)(8)(9)z

   第一个数字有 6 位数字，然后是一个 3 位数字

                X
   \d+.......\d+
   (123456)(789)z

   第一个数字有 6 位数字，然后是 2 个数字

                  X
   \d+.....\d+ \d+
   (123456)(78)(9)z

   …等等。

有很多方法可以将数字序列 123456789 分割成数字。准确地说，有 2n-1 种方法，其中 n 是序列的长度。

• 对于 123456789，我们有 n=9，这给出了 511 种组合。
• 对于长度为 n=20 的更长序列，大约有一百万 (1048575) 种组合。
• 对于 n=30 - 多一千倍 (1073741823 种组合)。

尝试每一种组合正是搜索花费如此长时间的原因。

回到单词和字符串

在我们的第一个示例中，当我们在字符串 An input that hangs! 中根据模式 ^(\w+\s?)*$ 查找单词时，也会发生类似的事情。

原因是单词可以表示为一个 \w+ 或多个

(input)
(inpu)(t)
(inp)(u)(t)
(in)(p)(ut)
...

对于人类来说，很明显可能没有匹配，因为字符串以感叹号!结尾，但正则表达式期望结尾处是单词字符\w或空格\s。但引擎并不知道这一点。

它尝试了正则表达式(\w+\s?)*如何“消耗”字符串的所有组合，包括带有空格(\w+\s)*和不带空格(\w+)*的变体（因为空格\s?是可选的）。由于有许多这样的组合（我们在数字中已经看到了），搜索需要很长时间。

该怎么办呢？

我们应该打开懒惰模式吗？

不幸的是，这不会有帮助：如果我们将\w+替换为\w+?，正则表达式仍然会挂起。组合的顺序会改变，但总数不会改变。

一些正则表达式引擎有复杂的测试和有限自动机，可以避免遍历所有组合或使其速度更快，但大多数引擎没有，而且这并不总是有效。

如何修复？

解决这个问题主要有两种方法。

第一种是减少可能的组合数量。

让我们通过将正则表达式重写为^(\w+\s)*\w*$来使空格变为非可选的——我们将查找任意数量的单词后跟一个空格(\w+\s)*，然后（可选地）是一个最后的单词\w*。

这个正则表达式等价于之前的正则表达式（匹配相同的内容），并且运行良好。

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

alert( regexp.test(str) ); // false

为什么问题消失了？

这是因为现在空格是强制性的。

之前的正则表达式，如果我们省略空格，就会变成(\w+)*，导致在一个单词内出现许多\w+的组合。

所以input可以匹配为\w+的两次重复，就像这样。

\w+  \w+
(inp)(ut)

新的模式不同：(\w+\s)*指定了单词后跟空格的重复！input字符串不能匹配为\w+\s的两次重复，因为空格是强制性的。

现在节省了尝试大量（实际上是大多数）组合所需的时间。

防止回溯

虽然重写正则表达式并不总是方便。在上面的例子中，它很容易，但并不总是很明显如何做到这一点。

此外，重写的正则表达式通常更复杂，这不是好事。正则表达式本身就足够复杂了，不需要额外的努力。

幸运的是，有一种替代方法。我们可以禁止量词的回溯。

问题的根源在于正则表达式引擎尝试了许多对人类来说显然错误的组合。

例如，在正则表达式 (\d+)*$ 中，对于人类来说很明显，+ 不应该回溯。如果我们将一个 \d+ 替换为两个单独的 \d+\d+，则不会有任何变化。

\d+........
(123456789)!

\d+...\d+....
(1234)(56789)!

在原始示例 ^(\w+\s?)*$ 中，我们可能希望禁止 \w+ 中的回溯。也就是说：\w+ 应该匹配整个单词，并具有最大的可能长度。没有必要降低 \w+ 中的重复次数，或者将其拆分为两个单词 \w+\w+ 等等。

现代正则表达式引擎为此支持占有量词。如果我们在量词后面添加 +，则常规量词将变为占有量词。也就是说，我们使用 \d++ 而不是 \d+ 来阻止 + 回溯。

占有量词实际上比“常规”量词更简单。它们只是尽可能多地匹配，而不会进行任何回溯。没有回溯的搜索过程更简单。

还有一些所谓的“原子捕获组”——一种在括号内禁用回溯的方法。

…但不幸的是，在 JavaScript 中不支持它们。

不过，我们可以使用“前瞻转换”来模拟它们。

前瞻来救援！

因此，我们已经接触到真正的高级主题。我们希望量词，例如 + 不回溯，因为有时回溯没有意义。

要尽可能多地重复 \w 而不回溯的模式是：(?=(\w+))\1。当然，我们可以使用其他模式来代替 \w。

这可能看起来很奇怪，但实际上这是一个非常简单的转换。

让我们来解读它

• 前瞻 ?= 向前查找从当前位置开始的最长单词 \w+。
• 带有 ?=... 的圆括号的内容不会被引擎记忆，因此将 \w+ 包含在圆括号中。然后引擎将记忆其内容
• …并允许我们在模式中将其引用为 \1。

也就是说：我们向前看 - 如果存在单词 \w+，则将其匹配为 \1。

为什么？这是因为前瞻将单词 \w+ 作为一个整体找到，我们使用 \1 将其捕获到模式中。因此，我们实际上实现了占有量词 +。它只捕获整个单词 \w+，而不是其一部分。

例如，在单词 JavaScript 中，它可能不仅匹配 Java，而且可能忽略 Script 以匹配模式的其余部分。

以下是两种模式的比较

alert( "JavaScript".match(/\w+Script/)); // JavaScript
alert( "JavaScript".match(/(?=(\w+))\1Script/)); // null

1. 在第一个变体中，\w+ 首先捕获整个单词 JavaScript，但随后 + 按字符逐个回溯，以尝试匹配模式的其余部分，直到最终成功（当 \w+ 匹配 Java 时）。
2. 在第二个变体中，(?=(\w+)) 向前看并找到单词 JavaScript，该单词作为整体包含在模式中，由 \1 表示，因此在它之后没有办法找到 Script。

当我们需要禁止 + 之后的回溯时，我们可以将更复杂的正则表达式放入 (?=(\w+))\1 而不是 \w 中。

让我们使用前瞻重写第一个示例以防止回溯

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

alert( regexp.test("A good string") ); // true

let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false, works and fast!

这里使用 \2 而不是 \1，因为存在额外的外部圆括号。为了避免弄乱数字，我们可以给圆括号命名，例如 (?<word>\w+)。

// parentheses are named ?<word>, referenced as \k<word>
let regexp = /^((?=(?<word>\w+))\k<word>\s?)*$/;

let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false

alert( regexp.test("A correct string") ); // true

本文中描述的问题称为“灾难性回溯”。

我们介绍了两种解决方法

• 重写正则表达式以降低可能的组合数量。
• 防止回溯。