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

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

谢谢围观