记录正则表达式引发的血案

遇到问题

前些日子在做线上验品抽检需求，在开发发起检测任务页面时遇到一个字段校验的诉求，具体要求：“用户可以填入多组 ID，每组 ID 可以由商品 ID 和 SKU ID 共同构成，也可以只由其中一种 ID 构成，两种 ID 之间通过冒号分隔；每组 ID 之间又需要通过英文逗号分隔”。这不就是一个表单字段格式校验场景吗？因此很自然的想到使用正则表达式来处理，在捣腾了几分钟之后写好一个正则表达式：

/^(((d+:d+)+)|(,(d+:d+)+)|(d)+|(,(d+)+)){0,}$/

在 chrome 浏览器控制台简单测试了一下顺利通过！很完美~ 可是打包发到日常环境后，测试妹子找到我反馈说“这个页面很卡，而且是卡死的那种！”。

定位问题

经过排查后发现每次都是填入了商品 ID 之后发生的页面假死，于是断定问题应该是出在表单字段的 validator 函数，当我把这个 validator 函数注释之后发现页面恢复正常！但是这个 validator 函数是 formily 提供出来的钩子函数，钩子函数本身不会有问题，而且我在钩子函数里面的自定义逻辑也很简单，因此可以笃定问题出在正则表达式判断这里！ 但是我在 chrome 控制台里面明明测试的很丝滑，怎么会出现卡死呢？！于是让测试妹子把用例发我一看：

10253:23091,10253:23091,10253:23091,10253:23091,10253:23091,10253:23091,10253:23091,10253:23091,10253:23091,10253:23091,10253:23091,10253:23091,10253:23091,10253:23091,10253:23091

然后再把前面那段正则表达式语句进行可视化分析： 原来是我自己的用例太过简单，根本没有触发到正则的性能问题。以前一直听说正则表达式可能会造成性能问题，但由于一直都没有真正遇到过，所以也没有真正上心去了解正则执行原理，于是乎触发到知识盲区造成这个 bug。

如何解决

问题发生的原因虽然被定位到，但是我不太可能在短时间内写出一个符合需求的高性能正则表达式，因为测试妹子还等着我修掉 bug 后继续往下走。于是我准备先用一个临时方案来解决，临时方案的思路：把当前这个复杂度大的校验规则，分解为几个简单的校验规则，再把他们一起的结果串联起来。具体实现如下图： 把用户填入的很长很复杂的字符串按照英文逗号为分隔符的规则先进行分组，然后再用一个简单的正则表达式去判断每组 ID 的格式是否满足，因为每组 ID 的长度都不长，所以不会触发性能问题。 在解决燃眉之急后，我就开始搜集正则表达式相关的学习资料和博客，在 ATA 上搜索到好几篇与我的问题高度相似的文章《一个由正则表达式引发的血案》、《一个正则表达式flag引发的血案》、《正则表达式的RegExp.test函数》，但是这些文章各有侧重点，而我期望的是更加系统和全面的学习资料。经过一番搜索后，终于在豆瓣上发现了《精通正则表达式》这本书。不过我自己目前还没啃完，所以下面不会讲原理，等后面看完了再来写个读后感和引擎原理分析~ 在看书的过程中我发现一个新问题：不是每个业务场景都需要我们写出一个高性能的正则表达式，我们在开发业务的时候更多想要的是“如何快速发现性能低劣的正则表达式？”——简而言之，有一个工具能在我们编写代码的过程中去分析正则表达式的性能并给出反馈！

工具沉淀

带着上面的想法我去调研了 vscode 插件和 eslint 插件：

• vscode 插件生态中有很多 regex 相关的插件，不过大都是集中在如何快速预览和如何快速提供常用的正则表达式
• eslint 插件生态提供了 eslint-plugin-optimize-regex、eslint-plugin-vuln-regex-detector，前者主要是在对现有的正则表达式提供优化建议，没有做回溯风险校验；后者只做了回溯风险校验，并且很久没有维护了

vscode 插件这条路相比于 eslint 插件要更重一些，而且不好落进团队规范里面，因此决定自研一个 eslint 插件集优化建议和回溯风险于一体。 在正式落代码之前需要弄清楚两个问题：

• 如何度量正则表达式复杂度？
• 如何智能地给出优化建议？

这两个问题对于正则入门级选手的我来说实在是太难，经过一番调研之后发现早就有前辈在研究这些问题并且给出了一套理论依据——star height，以及一个成熟的正则表达式处理工具——regexp-tree。果然站在巨人的肩膀上不仅看得又高又远，而且代码撸得也飞快~ 花了半天时间就完成了 eslint-plugin-analyze-regex 插件的第一个版本，运行效果如下：

总结感想

• 关于个人：如果我对正则表达式很熟悉并且没有知识盲区，那就不会遇到这个问题，也就不会去看相关资料，同时也不会感觉到啃书的效率低，更不会想到用 eslint 插件来降低正则表达式使用成本
• 关于工具：本质上是借助 regexp-tree 提供的解析、优化能力来实现核心功能，然后再以 eslint 插件的形式来透出。对于开发者而言，毫无违和感并且开发体验一致

虽然在解决问题的整个过程中，有很多技术点（如：正则引擎、回溯、星高问题、regex-tree 原理、eslint 原理及插件机制）没有深入进去吃透并扒出来细讲，但是与正则相关的一些知识面逐渐扩充，这也算是一种收获吧！

参考文献

• 《正则表达式 30 分钟入门教程》
• 《精通正则表达式》
• 《失控的正则表达式》
• 正则表达式可视化工具
• NPM 包: regexp-tree
• NPM 包: safe-regex
• working-with-rules
• ESLint selectors
• Star height: The star height is a measure for the structural complexity of regular expressions
• RegExp Tree: a regular expressions processor
• vuln-regex-detector: Detect vulnerable regexes in your project. REDOS, catastrophic backtracking.