正则表达式性能浅析

发表于 更新于 分类于 本文字数： 2k 阅读时长 ≈ 7 分钟

正则表达式性能问题

今天重温了一下 js 中正则的回溯失控问题。先丢一个问题出来：/(A+A+)+B/.test (‘AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA’)，结果是怎样？别盲目相信自己，拷到浏览器上跑跑试试？？ （建议在新的空 tab 页上尝试）

发现问题没？

如果你真的放在一个新的 tab 页上尝试过了，你会发现，页面 pending 住了！不管你用的是啥浏览器，牛逼的 chrome，还是被咱们鄙视的 IE，都毫无例外地卡住了页面（safari 是个例外，它检测到正则陷入循环时会终止匹配）。啥，正则还有循环？没听过或者没想过这个问题？其实我也是才开始接触这个问题。那我们一起来学习一下吧。（讲真，我确实是一边看书，一边写代码尝试（一边强制关闭浏览器），一边写笔记）

什么是回溯？

首先要理解正则表达式的工作原理：

  1. 编译。就是创建了一个正则表达式对象（直接量或者是 RegExp 构造）
  2. 设置起始位置。这个 lastIndex 属性值只会作为 exec 和 test 方法的起始搜索位置，并且还需要正则表达式地标志中含有 g（全局）。但是如果是从第 4 步失败后转到这里来的这种情况下，此位置则是上一次匹配的位置的下一个字符的位置。
  3. 匹配每个正则表达式字元。逐个检查正则表达式模式。当一个特定的字元匹配失败时，会尝试回溯到之前尝试匹配的位置上，然后尝试其他可能的路径（这里有点抽象，等哈结合图片来说）
  4. 匹配成功或失败。发现了一个完全匹配，宣布匹配成功。如果所有可能路径都没匹配到，那么回退到第二步，从下一个字符开始。如果所有字符都经历了这个过程还没匹配成功，宣布匹配失败。（这里的匹配失败所尝试的次数，在正则表达式没写好的情况下，可能会是匹配成功的次数的数百万倍，耗时也是数百万倍）

然后可以说说什么是回溯了。

当遇到量词或者分支时，正则引擎需要决定下一步如果处理（如 *, +? 或 {2,} 等，或 | 分支）。下面结合具体梨子来说明这个过程。

打两个例子

分支与回溯

/h(ello|appy) hippo/.test(‘hello there, happy hippo’);

  1. 首先编译。
  2. 因为没有 g，所以不用设置起始位置，默认就是字符串的起始位置 0。
  3. 开始第一次匹配。这里为了方便，我把字符串叫做 str。正则第一个字符为 h，匹配到 str [0]。然后遇到分支，（分支是从左到右依次尝试），记下当前位置（后面回溯会用到）；匹配 ello，刚好匹配 str [1-4]，然后正则后面是个空格，匹配 str [5]，然后是正则 hippo 开头的 h，不匹配 there 的 t，于是回溯到上一位置（h 后面遇到的分支那里），尝试 appy，不匹配 ello。从 str [0] 开始的这一次匹配宣布失败。从 str [1] 开始匹配。h 不匹配 str [1]。一直到 happy 这里。h 匹配到正则的第一个字元，a 不匹配分支的左侧，但匹配分支的右侧，一直到 hippo 都成功匹配。最后宣告匹配成功。
  4. 匹配成功。

这是一个简单的过程。

重复与回溯

1
2
3
4
5
6
var str = `<div>this is a test div.<p>A p in div</p><p> Another p in a same div</p></div>`;
// test1 贪婪模式
/<p>.*<\/p>/.test(str);

// test2 惰性模式
/<p>.*?<\/p>/.test(str);

我们先来瞅一下 test1 贪婪模式下的匹配过程（直接从第三步开始说了哈）。

  • 字符串前面直到第一个 <p> 标签前都不能匹配，跳到第一个 < p > 这里。字符串 < p > 成功匹配到正则的 < p>，然后正则后面是非换行的任意字符并且尽可能多（贪婪模式），所以直接一次性匹配到了最后的 </div>。没问题吧？然后正则表达式要匹配 p 标签的结束了，’<’字符。但是字符串都匹配到底了，怎么办呢？回溯呀。回溯到倒数第一个字符之前，就是 > 字符。但是 > 字符也不匹配 <，继续回溯。直到回溯到最后一个 </p > 标签时，匹配成功。因此，test1 下匹配到的是：<p>A p in div</p><p> Another p in a same div</p>

再看一下 test2 惰性模式下：

  • 字符串前面直到第一个 <p> 标签前都不能匹配，跳到第一个 < p > 这里。字符串 < p > 成功匹配到正则的 < p>，然后正则后面是非换行的任意字符并且尽可能少（非贪婪模式），所以就是 0 个字符，然后由正则的 </p > 结束标签中的 < 字符去匹配字符串 < p>A p in div</p > 中的 A 字符，不匹配。于是.*? 就将 A 字符作为匹配内容放入其下，下一步用 < 去匹配空格，不匹配，把空格加入.*? 的匹配内容当中，继续。< 不匹配 p 字符.. 直到第一个 </p > 标签到来，宣布匹配成功。因此，test2 下匹配到的是：<p>A p in div</p>

重点：回溯失控

首先我们要明白一点，匹配成功很轻松，有一个成功就成功；匹配失败很痛苦，必须把所有情况都尝试完了，如果全都不能成功，那就真的失败了。就像 js 中的 some 和 every 的感觉。举个梨子：

1
/<html>[\s\S]*?<head>[\s\S]*?<title>[\s\S]*?<\/title>[\s\S]*?<\/head>[\s\S]*?<body>[\s\S]*?<\/body>[\s\S]*?<\/html>

以上正则表达式通常用来检查是否是正确的 html 文档结构。通常情况下是没有问题：匹配成功的话。但是，如果文档缺少一个结束标志的话，会进入大量的回溯：倒数第一个 [\s\S]? 匹配失败后，会回退到倒数第二个 [\s\S]?，使倒数第二个多匹配一个字符，然后继续匹配。当倒数第二个 [\s\S]? 尝试完所有情况后，会回溯到倒数第三个 [\s\S]? 继续尝试…

解决方案

既然存在这类问题，那么势必会有相应的解决方案，对于这个，是什么呢？一个主要思路是具体化字符串匹配模式。比如.*? 可以换成具体的 [^”\r\n] 等（虽然感觉也没怎么具体，但至少减少了 3 种情况）

使用预查和反向引用的模拟原子组

一旦原子组中存在一个正则表达式，该组的任何回溯位置都会被丢弃。原子组中的量词不会记录回溯点。但 js 中并没有原子组。但预查也是原子组。所以使用这种方式可以写出以下的匹配式：

1
/<html>(?=([\s\S]*?<head>))\1(?=([\s\S]*?<title>))\2(?=([\s\S]*?<\/title>))\3(?=([\s\S]*?<\/head>))\4(?=([\s\S]*?<body>))\5(?=([\s\S]*?<\/body>))\6[\s\S]*?<\/html>

使用上面的表达式，在最后一个 [\s\S]*? 扩展至字符串末尾时会立刻匹配失败，因为没有可返回的回溯点。

注意问题

避免嵌套的量词，正如第一行的问题，/(A+A+)+B/.test (‘AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA’)，正因为 (A+A+) 与外面的 + 构成了好多好多的组合，3400 万次回溯。预防这类问题的关键是确保正则表达式地两个部分不能对字符串的相同部分进行匹配。重写为 / AA+B / 可以修复这个问题。