灾难性回溯

前言

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

开发者们很容易一不小心就写出这类正则表达式，所以我们迟早会面对这种意外问题。

典型的症状就是 —— 一个正则表达式有时能正常工作，但对于某些特定的字符串就会消耗 100% 的 CPU 算力，出现“挂起”现象。

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

在服务器端 JavaScript 中，在使用这种正则表达式处理用户数据时可能会引发程序漏洞。

一个小例子

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

我们使用一个这样的正则 ^(\w+\s?)*$，它指定了 0 个或更多个此类的字符。

我们运行一下：

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

console.log(regexp.test("A good string")); // true
console.log(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 to hang!";

// 会耗费大量时间
console.log( regexp.test(str) );

有些正则引擎能够处理好这种查询，但大多数引擎对此都无能为力。

简化的例子

问题在哪？为何正则表达式会「挂起」？

为了理解它，我们来简化一下例子：移除空格符 \s?，使其成为 ^(\w+)*$。

同时为了让问题更显著，再用 \d 替换掉 \w。这个新的正则表达式执行时仍然会挂起，比如：

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

let str = "012345678901234567890123456789!";

// 会耗费大量时间
console.log(regexp.test(str));

所以正则到底哪里出了问题？

首先，有人可能发现了这个正则 (\d+)* 有点奇怪，量词 * 有点画蛇添足。如果我们要匹配数字，那我们可以使用 \d+。

实际上，正则表达式是非常死板、机械化的。造成它运行缓慢的原因和上面我们看到的那样，所以让我们来理解它运作过程，然后问题的原因就会显而易见了。

回溯分析

这里使用123456789!做例子（简写方便举例），正则表达式还是之前的/^(\d+)*$/。

当在123456789!中查询 ^(\d+)*$ 时到底发生了什么，要耗时这么久呢？

1. 首先，正则引擎尝试查一个数字 \d+。加号 + 默认为贪婪模式，所以它囊括/消耗（consume）了所有数字：

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

   然后它尝试应用星号量词，但是此时已经没有更多数字了，所以星号匹配不到任何东西。

   模式中接下来的 $ 匹配字符串的结束，但是我们例子的文字中有 !，所以匹配失败，没有匹配结果：

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

2. 由于没有匹配结果，贪婪量词 + 的重复匹配次数会减一，并往前回溯一个字符。

   现在 \d+ 会匹配除了最后一个数字之外的所有数字：

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

3. 然后引擎尝试从新位置 (9) 继续搜索。

   星号 (\d+)* 可以成功应用 – 它匹配到了数字 9 ：

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

   引擎再次去尝试匹配 $，但是失败了，因为它遇到了 !：

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

4. 没有匹配结果，所以引擎继续回溯，减少重复匹配次数。回溯的运行过程基本上是这样的：最后一个贪婪量词逐渐减少重复匹配次数，然后前一个贪婪量词再减少重复匹配次数，以此类推。

   它会尝试所有可能的排列组合，这里是他们的例子：

   第一串数字 \d+ 有 7 位数，后面跟着一串 2 位数的数字：

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

   第一串数字有 7 位数，后面跟着两串数字，每串数字各有 1 位数：

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

   第一串数字有 6 位数，后面跟着一串 3 位数的数字：

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

   第一串数字有 6 位数，后面跟着两串数字：

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

   ……以此类推。

像 123456789 这样一串数字，分割成多个数的话有好几种分割方式。准确的说，如果这数字长度是 n ，则共有 2^n^-1 种方式去分割它。

假设 n=20，那么就有差不多一百万种排列组合，假设 n=30，那就得再乘上一千倍。正因为要尝试每种排列组合，所以才导致会消耗这么多时间。

那我们该怎么办？

我们应转而使用懒惰模式吗？

不幸的是，这没用：如果我们用 \d+? 去替代 \d+，它还是会挂起。排列组合的顺序会变化，但是总数不变。

有些正则表达式引擎应经过严密的测试，并自带一种能够避免遍历所有排列组合的有限自动机来优化速度。但并不是所有引擎能够做到，也不是在所有场合下都有效果。

回到字符和字符串

在我们第一个例子中，当我们用 ^(\w+\s?)*$ 这种模式在字符串 An input that hangs! 中查找字符时，也遇到了相同的问题。

原因是 \w+ 可以用来表示一个或多个字符：

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

对于我们人类来说，很显然它们无法匹配成功，因为例子中的字符串以感叹号 ! 结尾，然而正则表达式期望在末尾有一个词语式字符 \w 或者空格 \s 来结尾。正则引擎理解不了这种状况。

它尝试了所有 (\w+\s?)* 的排列组合试图去囊括整个字符串，包含了带空格 (\w+\s)* 的情形和不带空格 (\w+)* 的情形（因为 \s? 是可选的）。由于各种排列组合的数量太多了，所以耗费了大量时间去查询。

如何解决问题？

主要有 2 种解决方法。

第一种去试着减少各种排列组合的数量。

我们用把正则重写成 ^(\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 to hang!";

console.log(regexp.test(str)); // false

为什么问题消失了？

现在星号 * 跟在 \w+\s 后面，而不是 \w+\s? 后面。这意味着它无法匹配一个拥有多个连续单字字符串 \w+ 的单词，也就省下了原本去尝试这些排列组合的时间。

举个例子，之前那个模式 (\w+\s?)* 可能以两个 \w+ 的方式来匹配单词 string：

\w+\w+
string

之前那个模式/^(\w+\s?)*$/，由于存在可选的 \s，它允许 \w+、\w+\s 和 \w+\w+ 等等的变体形式。

我们重写之后的 (\w+\s)* 就不存在这些情况：它可能会是 \w+\s 或者 \w+\s\w+\s，但不可能是 \w+\w+。所以总体上，排列组合的可能性大大减少了。

防止回溯

有时候重写正则会比较麻烦，而且要推敲如何重写正则恐怕也并非易事。

另一种思路是禁止量词的回溯。

有些正则表达式我们人眼一看就知道无法匹配成功，但正则引擎还是会硬去尝试很多它的排列组合。

比如，正则 (\d+)*$ 中 + 对于我们人类来说很明显不应去回溯，就算我们用两个独立的 \d+\d+ 去替换一个 \d+，也是根本没作用的：

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

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

原先的那个例子 ^(\w+\s?)*$ 中我们可能希望禁止在 \w+ 这里去进行回溯。逻辑是： \w+ 应当尽可能多地去匹配一个完整的单词。在 \w+ 这里减少重复次数，然后将之进行分割，形成 \w+\w+，这类的做法没有任何意义。

为此，现代正则表达式引擎支持占有型量词（Possessive Quantifiers）。它们就像贪婪量词一样，但是不会进行回溯（所以比一般的正则量词更简单）。

它们也被成为“原子捕获分组（atomic capturing groups）” – 能够在括号内禁止回溯。

不幸的是，JavaScript 并不支持它，但是仍有其他办法。

用前瞻视角解决问题

我们可以使用前瞻断言来防止回溯。

在不进行回溯的前提下，我们用 (?=(\w+))\1 这个模式就可以尽可能多地重复匹配 \w：

来解读一下：

• 前瞻断言 ?= 从当前位置开始，向前查找最长的单词 \w+。
• 引擎默认不会去记录 ?=... 括号中的内容。为了记录它们，所以我们把 \w+ 放入括号中，这样引擎会记录括号中的内容了。
• ……然后用 \1 来引用括号中的内容。

它的逻辑是：我们先进行前瞻查找 – 如果有符合 \w+ 的单词，我们就可以用 \1 来匹配。

为什么？因为前瞻断言查找到一个单词 \w+，将其作为一个整体，然后进行捕获形成 \1 。所以我们最终实现了一种占有型加号 + 量词。它只将 \w+ 作为一个整体来捕获，而不会只捕获它的某一部分。

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

下面是 2 个模式的对比：

console.log("JavaScript".match(/\w+Script/)); // [ 'JavaScript', index: 0, input: 'JavaScript', groups: undefined ]
console.log("JavaScript".match(/(?=(\w+))\1Script/)); // null

1. 第一个变体 \w+ 首先捕获整个 JavaScript 单词，然而接下来 + 会一个字一个字地进行回溯，试图匹配整个模式的其余部分，直到 \w+ 匹配到了 Java 时，它最终才匹配成功。
2. 第二个变体 (?=(\w+)) 前瞻查找并匹配整个单词 JavaScript，然后把整个单词作为一个整体包含进 \1 中，所以在它后面就无法查找到 Script 了。

当我们需要禁止 + 进行回溯的话，我们只要把 (?=(\w+))\1 中的 \w 替换成更复杂的正则表达式就能实现了。

我们现在用前瞻断言重写第一个例子中的正则来防止回溯吧：

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

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

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

console.log(regexp.test(str)); // false，执行得很快！

这里我们用 \2 代替 \1，因为这里附加了额外的外部括号。为了防止数字产生混淆，我们可以给括号命名，例如 (?<word>\w+)。

// 括号被命名为 ?<word>，使用 \k<word> 来引用
let regexp = /^((?=(?<word>\w+))\k<word>\s?)*$/;

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

console.log(regexp.test(str)); // false

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

总结

1. 正则表达式的量词+、*、?，默认都是贪婪匹配模式，会匹配尽可能多的字符。

2. 贪婪模式下，匹配后的字符串，如果不满足紧接着的正则规则，会进行回溯，比如：

   /^(\d+)*$/：这个正则表示，以数字为开头，然后尽可能多的匹配连续数字（这个正则是为了演示灾难性回溯硬写的，不用考虑合理性），这里面有两个贪婪量词+ *

   1. 正好匹配的情况

      如下面这个例子，\d+会尽可能多的匹配数字，所以匹配到了0123456789，然后使用贪婪量词*再次匹配捕获组1中的规则，没有可以匹配的字符了，然后匹配结尾符$，正好是结尾，所以就匹配成功了。这个字符串并没有发生回溯。

      let str = '0123456789'
      let reg = /^(\d+)*$/
      console.log(reg.test(str)) // true

   2. 回溯的情况

      下面这种情况就会发生灾难性回溯，

      let str = '0123456789!'
      let reg = /^(\d+)*$/
      
      // 如果字符串很长的话，会耗费大量时间，甚至可能挂起引擎
      console.log(reg.test(str)) // false

      let str = '0123456789!'
      let reg = /^(\d+)*$/
      console.log(reg.test(str)) // false
      
      // 会有各种匹配结果
      (0123456789)! // 不符合 开始第1次回溯 + 回溯
      (012345678)(9)! // 不符合 开始第2次回溯  + 回溯
      (01234567)(89)! // 不符合 开始第3次回溯  *回溯    
      (01234567)(8)(9)! // 不符合 开始第4次回溯  +回溯
      (0123456)(789)! // 不符合 开始第5次回溯  *回溯    
      (0123456)(78)(9)! // 不符合 开始第6次回溯  *回溯   
      (0123456)(7)(8)(9)! // 不符合 开始第7次回溯  +回溯      
      (012345)(6789)! // 不符合 开始第8次回溯  *回溯
      // ... 以此类推
      // 最后都不符合 所以返回false
      // 但是一旦 回溯的次数特别多时，引擎就会挂起，或者崩溃

   3. 避免灾难性回溯

      1. 减少回溯次数，比如上面的例子，*完全没有必要，我们把它删除掉，这样就少了很多回溯的次数。

         let str = '0123456789!'
         // 减少回溯次数
         let reg = /^\d+$/
         console.log(reg.test(str)) // false

      2. 使用后瞻断言，来防止回溯，比如：

         let str = '0123456789!'
         // 后瞻断言防止回溯
         let reg = /^(?=(\d+))\1*$/
         console.log(reg.test(str)) // false

         括号里的后瞻断言默认是不会进入到捕获组中的，所以可以再用括号包裹一下，就是例子中的(\d+)，即\1，被捕获组捕获到的字符串会记录在捕获组返回的结果数组中，并不会发生回溯，分析一下上面的例子

         let str = '0123456789!'
         let reg = /^(?=(\d+))\1*$/
         console.log(reg.test(str)) // false
         
         // 后瞻断言(?=(\d+))捕获到了
         (0123456789) // 此时的\1就是这一串字符串
         (^(0123456789)!) // 接着匹配 *，此时的* 会重复前面的\1，因为只有一个!号了，所以没有匹配到
         (^(0123456789)!) // 接着匹配 $，此时的$ 会判断是否以前面的\1为结尾，但是此时结尾是感叹号，没有匹配到，
         // 最终返回false 捕获组\1中的结果并不会发生回溯

         还可以结合命名组使用

         let str = '0123456789!'
         let reg = /^(?=(?<number>\d+))\k<number>*$/
         console.log(reg.test(str)) // false

参考

https://zh.javascript.info/regexp-catastrophic-backtracking#li-zi