devinran

1年前
  • 1682

    浏览
  • 5

    评论
  • 2

    收藏

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

本文作者:imweb devinran 原文出处:imweb社区 未经同意,禁止转载

在腾爷《作为一个前端,可以如何机智地弄坏一台电脑?》之后,我就觉得需要学习这种低调奢华有内涵的文(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的征途是星辰大海

谢谢围观

5 条评论