一起学习正则表达式（七）回溯陷阱
思维导图
转载请注明出处：https://www.jianshu.com/p/40f8988ba339
本文出自 容华谢后的博客
往期回顾：
0.写在前面
在上一篇文章中，我们学习了正则表达式的匹配原理，在我们常用的开发语言中，大多数都是采用的传统型 NFA 引擎，也就是非确定性有穷自动机。
NFA 引擎以正则为主导，就是拿着正则看文本，会发生回溯，文本的同一部分，有可能会被反复测试很多次，在最坏的情况下，它的执行速度可能会非常慢，那什么是最坏的情况呢，一起来看一看。
1.回溯
在第二篇文章量词与贪婪中，我们了解到，表示次数的量词默认是贪婪的，在贪婪模式下，会尽可能最大长度的去匹配目标文本。
举个栗子，我们现在的需求是找到以字母 dy 结尾的单词或句子，我们可以很快的写出正则表达式：
目标文本：Toady is such a beautify day.
正则表达式：.+dy
看下结果：
贪婪匹配
可以看到匹配了31次才找到我们想要的内容，这31次都做了哪些工作，来看下：
贪婪匹配过程
正则中的 .+ 在一开始就匹配到了文本的全部内容，然后拿着正则看文本，正则中还剩下 dy 没有匹配，去文本中查找，发现已经没有字符可以匹配了，于是向前回溯，吐出句号，用正则再次对比，发现还没有匹配上，于是继续向前回溯，吐出字母 a，再次对比，还没有匹配上，就这样反反复复的向前回溯，终于找到了 Toady 这个单词，匹配结束。
这样写出的正则表达式性能肯定是有问题的，如果目标文本再长一点，再加上几个选择分支，回溯步骤直接就要上天，于是我们利用学过的知识，简单修改下：
目标文本：Toady is such a beautify day.
正则表达式：.+?dy
在量词后面加上一个问号，就代表当前量词的匹配行为是非贪婪模式，非贪婪模式虽然也会发生回溯，但是不会一上来就把目标文本一口气都吃掉，从而节省了很多匹配步骤，先再看结果：
非贪婪匹配
可以看到只用了6次就成功的匹配到了，再看下匹配的过程：
非贪婪匹配过程
2.Lazada 卖家中心案例
这是一个真实的案例，来自阿里技术微信公众号上的发文，Lazada 卖家中心店铺名检验规则比较复杂，名称中可以出现下面这些组合：
-
英文字母大小写
-
数字
-
越南文
-
一些特殊字符，如 “&”、“-”、“_” 等
负责开发的同学随手就写出了下面的正则表达式：
^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$
看起来很长，但其实就是两个选择分支，我们来简化下：
^([条件分支1]|[条件分支2])+$
在内部测试的时候，没有发现什么问题，然后就上线运行了，在运营的过程中，经常会遇到服务器CPU狂飙到100%的情况，于是就找啊找，终于找到竟然是这样一个正则引起的问题，一个小小的正则竟然可以让服务器直接崩溃，这是为什么呢，一起来看下：
我们用一段文本来测试下：
Lazada 正则校验
示例：https://regex101.com/r/dTzUyx/1
可以看到，一个很短的字符串，NFA 引擎竟然尝试了1万多次，由于是贪婪匹配，第一个分支可以匹配上 Talk is Cheap 这部分，接着后面的逗号匹配失败，使用第二个分支继续匹配，还是失败，此时贪婪匹配的过程就结束了。
接着 NFA 引擎用后面的 $ 来进行匹配，但此处不是文本结尾，匹配不上，开始回溯，吐出第一个分支匹配上的最后一个字母 p，用第二个分支匹配，第二个分支匹配上了字母 p，但是还是匹配不上逗号。
Lazada 匹配过程
继续回溯，吐出第二个分支匹配上的字母 p，然后再继续吐出第一个分支匹配上的字母 a，再用第二个分支匹配字母 a 和 p，最后还是没有匹配上，继续吐出第二个分支匹配上的字母 p，用第一个分支再次匹配，由此进入了死亡循环，如果测试的文本增加一位，那么整体的匹配步骤就会直接翻倍。
那么该如何解决这个问题呢，也很简单，直接使用独占模式就可以，在量词加号的后面，再加上一个 + 号，就变成了独占模式，独占模式不会发生回溯，匹配失败就直接返回失败了，不会引发性能问题：
^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])++$
Lazada 独占模式
还可以去掉两个分支中的重复条件 A-Za-z：
^([0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$
Lazada 去除重复条件
这样修改之后，只用了57次就匹配完成了，所以切记，如果你写的正则表达式中有多个分支条件，里面的条件千万不要重复。
3.避坑指南
在见识了正则回溯的威力之后，发现如果对正则不了解，还是很容易写出存在性能问题的正则表达式的，下面我们来总结下那些我们在平时开发中容易踩到的坑：
3.0 避免不同分支重复匹配
在上文中，我们已经讲到了，如果正则中存在多个条件分支，其中各个分支中的条件千万不要重复。
3.1 提前编译好正则
编程语言中一般都自带“编译”方法，我们可以在使用正则之前提前编译好，这样就不用每次使用的时候去反复构造状态机，从而提升正则匹配的性能：
import re
# 先编译好，再使用
reg = re.compile(r'ab?c')
reg.findall('abc')
# 直接使用
re.findall(r'ab?c', 'abc')
3.2 提取出公共部分
比如我们匹配 http 或 https，有的同学会写成 http|https，可以直接优化成 https?
3.3 出现可能性大的放左边
由于正则是从左到右匹配的，把出现概率大的放左边，域名中 .com 的使用是比 .net 多的，所以我们可以写成 .(?:com|net)\b，而不是 .(?:net|com)\b。
3.4 只在必要时才使用子组
有些同学为了写出来的正则表达式更加易读，会故意在表达式中加一些括号用于区分，因为正则是默认保存子组的，正则引擎必须做一些额外工作来保存匹配到的内容，这会降低正则的匹配性能，如果后续不会再用到这个子组，记得加上 ?: 不保存子组。
3.5 警惕嵌套的子组重复
如果一个组里面包含重复，接着这个组整体也可以重复，比如 (.) 这个正则，匹配的次数会呈指数级增长，所以尽量不要写这样的正则。
3.6 测试性能的方法
我们写好正则之后，可以通过 regex101.com 这个网站来测试正则的匹配次数和性能，还可以debug调试，非常方便。
4.写在最后
最后在总结下上面讲到的内容：
思维导图
到这里，正则表达式的回溯陷阱就讲完了，如果有问题可以给我留言评论，谢谢。
正则表达式在线校验工具：https://regex101.com/
