注意啦⚠️ 别让正则把你网站搞垮⚠️⚠️⚠️

引言

事情起源还得从一个需求讲起, 需求内容如下:

1. 假设有串字符串如下:

const str = `Pharmaceuticals progress events.

JSON output:
{
  "name": "moyuanjun",
  "age": 28
}`

1. 现需要从字符串中, 提取到 JSON output: 后面的所有字符串, 后面还需要将其解析为对象(当然这不是本文的重点)

需求本身很简单, 实现起来也容易, 具体方案如下, 那么请问以下实现方法有啥问题呢?

const jsonStr = str.replace(/^(\s|\S|.)*?JSON output:/, '')

由于字符串是 gpt 返回的, 它是不可控的, 这里当字符串为 No, this text is not a transaction event. Therefore, the requested entities cannot be extracted. 时, 通过上文的正则进行匹配时就会导致页面卡住, 这里如果大家好奇的话, 可以尝试将下面代码复制到 浏览器控制台 并执行

'No, this text is not a transaction event. Therefore, the requested entities cannot be extracted.'.replace(/^(\s|\S|.)*?JSON output:/, '')

上面主要问题还是出在正则上, 执行上面正则匹配, 会陷入 回溯 陷阱, 我们可以看下上面正则在 regex101 的测试结果, 从测试结果来看正则的匹配次数是有点夸张的

下面我们来针对 回溯 问题进行展开....

一、正则引擎

传统正则引擎分为 NFA (非确定性有限状态自动机) 和 DFA(确定性有限状态自动机), 那么, 什么是确定型、非确定型、有限状态以及自动机呢?

确定型与非确定型: 假设有一个字符串 abc 需要匹配, 在没有编写正则表达式的前提下, 就能够确定 字符匹配顺序 的就是确定型, 不能确定字符匹配顺序的则为非确定型

有限状态: 所谓有限, 指的是在有限次数内能够得到结果

自动机: 自动机即自动完成, 在我们设置好匹配规则后由引擎自动完成, 不需要人为干预即为自动

根据上面的解释我们可得知 NFA 引擎和 DFA 引擎的主要区别就在于: 在没有编写正则表达式的前提下, 是否能确定字符执行顺序;, 下面我们来简单介绍下这两种引擎:

1.1 NFA 引擎

NFA(Nondeterministic finite automaton)又名 非确定性有限状态自动机, 主要特点如下:

1. 表达式驱动: 由要执行的正则表达式进行驱动的算法, 正则引擎从正则表达式起始位置开始, 尝试与文本进行匹配, 如果匹配成功, 都前进一步, 否则文本一直前进到下一个字符, 直到匹配成功

2. 会记录位置: 当正则表达式需要进行选择时, 它会 选择 一个 路径 进行匹配, 同时会 记录 当前的 位置, 如果选择的路径匹配不成功则需要回退回去, 重新选择一个路径进行尝试, 直到匹配完成, 如果所有可能情况全部匹配不成功, 则本次匹配失败

3. 单个字符可能会检查多次: 从👆🏻可以看出, 字符串中一个字符可能会被多次匹配到, 因为当一条正则路径不通时, 会进行回退

4. 支持零宽断言: 因为具有回退功能, 所以可以很容易实现零宽、断言、捕获、反向引用等功能

最后借用 猪哥 制作的一个小动画, 方便大家理解:

1.2 DFA

DFA(Deterministic finite automaton) 又名 确定性有限自动机, 主要特点如下:

1. 文本驱动: 由要搜索的文本驱动的算法, 文本中的每个字符 DFA 引擎只会查看一次, 简单理解就是对字符串进行一次循环, 每次循环都和正则进行一次匹配, 匹配成功字符串和正则指针都相应的向下移动

2. DFA 引擎会记得所有的匹配可能, 并且每次匹配都会返回其中 最长的匹配, 这么做的目的是为了让后面的匹配能够更加轻松, 正因为如此字符串 nfa not 在 (nfa|nfa not) 中匹配结果为: nfa not

3. 优点: 优点很明显, 由于只会会循环一直字符串、并且会提前记住所有可能情况, 所以相对来说匹配效率是很高的

4. 缺点:

• 它始终将返回最长匹配结果, 无法控制表达式来改变这个规则
• 因为需要记住所以可能情况, 所以正则表达式预编译时间会更长, 占用更多内存
• 没有回退, 所有重复的运算符 都是贪婪 的, 会尽可能匹配更多的内容
• 因为不存在回退, 所以自然不支持零宽断言、捕获、反向引用等功能

最后借用 猪哥 制作的一个小动画, 方便大家理解:

补充说明: 上面只是对传统的两个正则引擎进行简单介绍, 在 JS 中正则引擎使用的则是 NFA 下面我们也只是对 JS 中的正则、以及 回溯 进行简单介绍, 同时在 regex101 中我们选用的语言则是 PHP, 主要是因为在 PHP 用的也是 NFA 引擎并且在 regex101 下会多一个 Regex Debugger 功能(不知道为什么 JS 没有 😭)

二、回溯

我们知道, NFA 引擎是用表达式去匹配文本, 而表达式又有若干 分支 和 范围, 一个分支或者范围匹配失败并不意味着最终匹配失败, 正则引擎会进行回退去尝试 下一个 分支或者范围, 这种行为就被称之为 回溯

类比于迷宫, 想象一下, 面前有两条路, 我们选择了一条, 走到尽头发现是条死路, 只好原路返回尝试另一条路, 则这个原路返回的过程就被称之为 回溯, 它在正则中的含义是 吐出已经匹配过的文本, 同时 正则匹配位置也会进行回退

一般的, NFA,如果匹配失败, 会尝试进行 回溯, 因为它并不知道后面还有没有可能匹配成功, 他是蒙在鼓里的, 但是 DFA 从一开始就知道所有的可能匹配, 因为在预编译时就它就已经存储了所以可能情况, 所以正则编写的好坏对 NFA 来说是特别的重要的

引擎会真正按照正则表达式进行匹配, 让你选择达到完全匹配所需的每个步骤, 所以我们必须很谨慎地告诉它, 首先检查哪种选择才能达到您的期望, 你也有机会调整正则表达式, 以最大程度地减少回溯并尽早进行匹配

三、量词

3.1 在 JS 中量词表示要匹配的字符或表达式的数量, 常见的量词有:

字符	含义
{n}	n 是一个正整数, 匹配了前面一个字符刚好出现了 n 次
{n,}	n 是一个正整数, 匹配前一个字符至少出现了 n 次
{n,m}	n 和 m 都是整数。匹配前面的字符至少 n 次，最多 m 次, 如果 n 或者 m 的值是 0, 这个值被忽略
*	匹配前一个表达式 0 次或 多次, 等价于 {0,}
+	匹配前面一个表达式 1 次或者 多次, 等价于 {1,}
?	匹配前面一个表达式 0 次或者 1 次, 等价于 {0,1}

3.2 贪婪 与 非贪婪

模式	描述	匹配规则
贪婪模式	默认使用量词时就是贪婪模式	尽可能多 的匹配内容
非贪婪模式	量词后加 ?, 如: *?、+?、??、{n,m}?	尽可能少 的匹配内容

3.3 贪婪模式下的回溯

现在我们看一个简单例子, 有如下正则 .*c 以及待匹配字符串 bbbcaaaaaaaaa, 下面我们使用 regex101 来进行测试

这里选择 Debugger 查看整个正则匹配流程(重点看 回溯)

从图中可以看出, .* 会优先匹配到所有内容, 然后在匹配字符串 c 时, 只要匹配失败, 字符串匹配位置就会进行回退(吐出一个字符), 然后再次进行匹配, 如此反复直到匹配到字符串 c

3.4 解决办法

针对上文回溯问题, 下面我们来简单优化下正则, 来避免 回溯

1. 使用非贪婪模式: .*?c

1. 使用反向字符集: [^c]*c

3.5 绝对不用「量词嵌套」

特别特别需要注意的是, 嵌套的量词 将会制造指数级的回溯, 下面我们就以 .*c 以及 (.+)*c 为例, 从 regex101 测试结果来看, 相同匹配字符串 .*c 需要 13 个步骤, (.+)*c 则直接飚到 61144 了, 但最终这两个表达式匹配到的结果却是一样的

四、多选分支

已知在 JS 中正则可使用 | 定义多个分支, 例如: x|y 可匹配 x 或者 y,

那么正则在匹配过程中如果遇到多选分支时, 引擎则会按照 从左到右 的顺序检查表达式中的多选分支, 如果某个分支匹配失败, 表达式和字符串都会进行回退(回溯), 然后选择另一个分支进行尝试... 这个过程会不断重复, 直到完成全局匹配，或所有的分支都尝试穷尽为止

4.1 回溯现象

假设有正则表达式 num(1234567890|1234567891) 待匹配字符串如下 num1234567891, 下面我们使用 regex101 来进行测试

这里选择 Debugger 查看整个正则匹配流程(重点看 回溯)

4.2 优化手段

1. 提取多选分支中的必须元素: num123456789(0|1)

1. 高优先级分支提前: num123456789(1|0)

由于正则引擎遇到分支是按照 从左到右 的顺序, 来选择分支进行匹配的, 所以我们可以通过调整分支的顺序来提高匹配效率

1. 使用字符组: num123456789[01]

这里我们还可以使用字符组 [], 和 | 不同的是它不存在分支选择问题, 本质上分支越多, 可能的回溯次数越多, 所以如果可以我们需要尽可能减少分支

五、其他正则优化手段

• 使用非捕获型括号 (): 如果不需要引用括号内的文本, 请使用非捕获括号, 不但能节省捕获的时间, 而且会减少回溯使用的状态的数量, 从两方面提高速度
• 不要滥用字符组 []: 不使用只包含一个字符的字符组, 需要付出处理字符组的代价
• 分析待匹配字符串, 将最可能匹配的分支放在前面
• 正则进行适当拆分: /最明确的规则/.test() && /更细的规则/.test(str)
• 必要时可以考虑更换正则引擎, 比如使用 DFA
• 使用检测工具进行测试, 比如: regex101
• 使用有明显确定的特征的具体字符、字符组代替通配符, 说白了尽可能描述清楚你的正则

六、回到正文

回到我们最开始的那个正则, 可以优化如下

'No, this text is not a transaction event. Therefore, the requested entities cannot be extracted.'.replace(/^[\s\S]*?JSON output:/, '')

在 regex101 的测试结果如下, 从测试结果来看前后性能提升可不是一点两点

七、参考:

• 正则表达式是如何让你的网页卡住的
• 一个正则导致浏览器页面卡死
• 正则表达式优化 - 避免灾难性回溯
• 正则引擎的几种分类
• 正则表达式引擎执行原理——从未如此清晰!
• 深入正则表达式(3):正则表达式工作引擎流程分析与原理释义...