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

2次阅读

共计 2591 个字符，预计需要花费 7 分钟才能阅读完成。

前些日子在做线上验品抽检需要，在开发发动检测工作页面时遇到一个字段校验的诉求，具体要求：“用户能够填入多组 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.