相爱相杀——正则与浏览器间的爱恨情仇

在腾爷《作为一个前端,可以如何机智地弄坏一台电脑?》之后,我就觉得需要学习这种低调奢华有内涵的文(biao)章(ti)名(dang)。

嘿嘿嘿,你看,你被我骗进来了吧!

正则优化——回溯、环视与原子组

首先,让我用一个正则,谋杀你的浏览器。复制以下代码在console执行。

var innocentString = "By the name of the regexp, sentence your browser to die";
var evilReg = /(.+.+)+X/;
evilReg.test(innocentString);

什么?弄不坏你?那么恭喜,你的chrome/safari版本更新很及时。不怕死的换IE/Firefox试试?

我反正是信了。。。。。。。

从执行正则匹配到返回匹配结果中间都发生了什么?

大致来说,经过以下几个步骤:

  • 编译 : 当创建一个正则对象,无论是正则字面量还是RegExp构造函数,浏览器都会先验证匹配模式,并将之转化为一个原生代码程序,用于执行接下来的匹配工作。
  • 设置匹配位置 : 即匹配过程的基准位置。接下来的匹配工作从这里开始,初始状态是待匹配字符串的第一个字符,匹配失败的回溯则是上一次匹配的下一个位置。另外,大家熟知的 lastIndex 属性就是指定这个匹配位置。
  • 匹配字符串字元 : 指定开始位置之后,正则开始逐个检查待匹配文本和匹配模式。
  • 回溯 : 匹配字元失败时,匹配位置回到之前位置+1的地方,然后继续匹配其他路径
  • 结束 : 如果在某个位置发现完全匹配,那么匹配成功。否则执行回溯。如果回溯所有路径均没有匹配成功,那么就返回匹配失败。

回溯

回溯是正则表达式匹配过程的基础,可以说,正则功能的实现就是依赖回溯。不过既然放在这里讨论,就说明它是一把双刃剑,在提供强大功能的同时,也产生了昂贵的计算消耗。如果使用不当,就像上面那个evilReg一样,对浏览器造成直接影响。

正则匹配文本时,顺序是从左到右测试字符串组成部分,寻找匹配项。但当遭遇贪婪匹配(*,+,{x,})或分支匹配(x|y)时,正则需要尝试更多匹配路径,相应的回溯也会增加。

var text = '<title>javascript</title>';
/<title>javascript<\/title>/.test(text);
/<title>(java|javascript)<\/title>/.test(text);
/<title>.*<\/title>/.test(text);

上面三个匹配规则举例,第一个规则完全符合,没有回溯。

第二个正则,前面的< title >标签立刻被找到,接下来正则遭遇分支处理,按顺序从左到右选择进行匹配,对于java四个字符匹配成功,但是在s字元匹配失败,这时候执行回溯到最近的决策点,选择第二个分支选项,匹配成功。

第三个正则的过程大概是这样:

  • < title > (这里经过7步,匹配7个字元)
  • < title >javascript< /title > (.*一直匹配到最尾,贪婪匹配失败,回溯)
  • < title >javascript(经过8次回溯,.*匹配了javascript,继续执行<匹配结束标签成功)
  • < title >javascript< /title > (匹配成功)

从上面的过程可以看到,正则表达式越宽泛,可能执行的匹配和回溯过程就越多。那么反过来说,正则表达式越具体,可能执行的匹配和回溯过程就越少。

蛤蟆神功第一式 : 尽量具体化正则表达式以减少回溯

顺便一说:懒惰匹配的匹配过程与贪婪是相反的,尽管在唯一的文本段落中它们的匹配结果相同。

嵌套的贪婪量词

现在回到文章开头那个坑爹的正则,就是这个货

var innocentString = "By the name of the regexp, sentence your browser to die.";
var evilReg = /(.+.+)+X/;
evilReg.test(innocentString);

这中间发生了什么从而让浏览器欲仙欲死呢? 可以看到,这个正则存在两个连续的贪婪量词,并且可以分组重复。假设待匹配文本的长度量级为n。那么连续的贪婪量词可以在和为n之内进行任意组合,并且每一个组合可能还有n次分组重复的可能。算法复杂度高达.......... 高达也算不出来

咳咳好吧,算法复杂度高达O(2n)。n每高一丢丢,消耗就涨得飞起。

当然我相信没有人会真的写出上面那个愚蠢的正则表达式。但是在某些复杂的场景中,贪婪量词的嵌套情况还是大大存在的,这里也许需要更多的思考。我们就不得不提到一个法宝。

原子组

很多正则表达式引擎都支持原子组,原子组的特点是它将组内的所有回溯位置全部丢弃。简单说就是,把这一串非捕获组当作一个字元来处理。原子组的写法是(?>...)

例如:

var str = "TomAndJerry";
var reg = /tom(?>and)jerry/i;

在这个正则的匹配过程中,tom匹配完成后,直接向后找and而不是a,查找and是一步操作,中间不回溯。

令人蛋疼的是,js作为世界上最美妙的语言,居然不支持原子组。

不支持怎么办?前端工程师遇到“不支持”是怎么做的?没错,模拟。

怎么模拟呢?唉,我们又需要另一个法宝。

环视

环视是一组匹配位置的规则,类似于^和$,只匹配位置,不占字符,是零宽度的。有些地方也叫做零宽度断言

关于环视具体细节不赘述,总之根据查找方向和匹配与不匹配共分为四种:

  • (?=...) 正向肯定环视
  • (?!...) 正向否定环视
  • (?=<...) 逆向肯定环视
  • (?!<...) 逆向否定环视

它们匹配:后(前)面满足(不满足)匹配规则的位置

说得我自己都快晕菜了,简单说就是:

var reg = /\b(?=re)[A-Za-z]+\b/;

它匹配 以re开头的单词,其中(?=re)匹配以re开头的单词的前面的位置

我们模拟原子组所需要的就是正向肯定环视。

顺便说下,令人更蛋疼的是,js作为世界上最美妙的语言,居然不支持逆向环视。

模拟原子组

既然我们可以用环视匹配到零宽度位置,再加上一个捕获组,不就可以实现原子组了吗?下面有请猫和老鼠组合。

var str = "TomAndJerry";

现在我们要把and当成原子组拿出来,先匹配and前面的位置:

var reg = /(?=and)/i;

然后获取and并且把它塞到原本的位置

var reg = /(?=(and))\1/i;

然后组合全部正则

var str = "TomAndJerry";
var reg = /tom(?=(and))\1jerry/i;

搞定!这样我们完美模拟了原子组,接下来去解决回溯问题。

var innocentString = "By the name of the regexp, sentence your browser to die.";
var evilReg = /(.+.+)+X/;
evilReg.test(innocentString);

我们说了,这里由于贪婪量词嵌套导致了回溯失控问题,那么我们把内层的贪婪量词原子化,消除回溯灾难,试试。

var innocentString = "By the name of the regexp, sentence your browser to die.";
var evilReg = /(?=(.+.+))\1+X/;
evilReg.test(innocentString);

腰不酸了,腿不疼了,一口气上五楼,不费劲儿~~~~

蛤蟆神功第二式 : 模拟原子组以解决嵌套贪婪量词造成的回溯失控问题

其他一些

分支

前面我们讲了分支也会增加回溯,虽然相对来说分支造成的影响小得多,但是也还是有优化的空间。

比如:

var reg = /(java|javascript)$/;

改为

var reg = /java(?:script)?$/;

又比如

var reg = /cat|hat/;

改为

var reg = /[ch]at/;

暂存

跟DOM节点一样,把正则存起来用,尤其是在循环里。减少编译过程。

while (/this is no good/.test(str1)) {
    str2.match(/this is really not good/);
}

改为

var reg1 = /this is good/;
var reg2 = /this is really good/;
while (reg1.test(str1)) {
    str2.match(reg2);
}

拆分

把太复杂的正则拆开分布用

var bigString = '@R%$YE$F#@...F$#F#@F#$G#F$';
bigString.replace(/complex reg/, "...");

改成

var bigString = '@R%$YE$F#@...F$#F#@F#$G#F$';
bigString.replace(/simple reg/, "...").replace(/simple reg/, "...");

既然是文章就要有个总结

  • 某些性能问题也许就潜藏在平常开发容易忽视的细节中
  • 代码的世界有些东西看似容易其实水很深
  • js的征途是星辰大海

谢谢围观

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数说工作室

2. PRXPARSE () | 正则表达式的“阿赖耶识”

阿赖耶识...为宇宙万有之本,含藏万有,使之存而不失,故称藏识。又因其能含藏生长万有之种子,故亦称种子识。 ——《佛光大辞典》 佛家说人有九识,除眼、耳、鼻、...

3356
来自专栏Android知识点总结

1.计算机编程通之字节与数据类型

797
来自专栏java工会

深度思考编程的艺术

1658
来自专栏java一日一条

重构 改善既有代码的设计--笔记

查看一个类是否“过大”,这里有一个小技巧分享给大家。就是看两点:1)这个类实例变量太多,必然会有Duplicated Code(重复代码) 2)类内如果有太多代...

804
来自专栏写代码的海盗

分水岭 golang入坑系列

第三式开篇语有些负面, 所以这里就不贴了。有兴趣的自己可以去看看 https://andy-zhangtao.gitbooks.io/golang/conten...

3784
来自专栏MasiMaro 的技术博文

windows 纤程

纤程本质上也是线程,是多任务系统的一部分,纤程为一个线程准并行方式调用多个不同函数提供了一种可能,它本身可以作为一种轻量级的线程使用。它与线程在本质上没有区别,...

892
来自专栏AI研习社

NBA 史上实力最弱的球队是哪个?用 Python + SQL 我们找到了答案

文中部分代码会有“代码补完”字样的注释,是留给读者自己补完并在线评测的,相当于小作业,这里就请大家自行脑补吧。(编者注:每个需要补充的部分都给出了提示信息) ...

3294
来自专栏小小挖掘机

一道简单的sql语句题

这是很早之前面的,第一次面数据分析的面试,当时还傻乎乎的以为数据分析和数据挖掘是一回事呢。结果才发现,数据分析岗位大多注重的是数据库的能力,比如sql语句的考察...

3083
来自专栏阿杜的世界

《重构》阅读笔记-代码的坏味道

开发者必须通过实践培养自己的经验和直觉,培养出自己的判断力:学会判断一个类内有多少个实例变量算是太大、学会判断一个函数内有多少行代码才算太长。

572
来自专栏数说工作室

正则表达式的“阿赖耶识”| 【SAS Says·扩展篇】正则表达式

阿赖耶识...为宇宙万有之本,含藏万有,使之存而不失,故称藏识。又因其能含藏生长万有之种子,故亦称种子识。 ——《佛光大辞典》 佛家说人有九识,除眼、耳、鼻、舌...

3213

扫码关注云+社区