本文作者: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试试?
我反正是信了。。。。。。。
大致来说,经过以下几个步骤:
回溯是正则表达式匹配过程的基础,可以说,正则功能的实现就是依赖回溯。不过既然放在这里讨论,就说明它是一把双刃剑,在提供强大功能的同时,也产生了昂贵的计算消耗。如果使用不当,就像上面那个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字元匹配失败,这时候执行回溯到最近的决策点,选择第二个分支选项,匹配成功。
第三个正则的过程大概是这样:
从上面的过程可以看到,正则表达式越宽泛,可能执行的匹配和回溯过程就越多。那么反过来说,正则表达式越具体,可能执行的匹配和回溯过程就越少。
蛤蟆神功第一式 : 尽量具体化正则表达式以减少回溯
顺便一说:懒惰匹配的匹配过程与贪婪是相反的,尽管在唯一的文本段落中它们的匹配结果相同。
现在回到文章开头那个坑爹的正则,就是这个货
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/, "...");
谢谢围观