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

在腾爷《作为一个前端,可以如何机智地弄坏一台电脑?》之后,我就觉得需要学习这种低调奢华有内涵的文(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 条评论
登录 后参与评论

相关文章

来自专栏吴裕超

es6 Object的几个新方法

ES5 的 Object.preventExtensions 则可以阻止给对象添加新属性

813
来自专栏信数据得永生

JavaScript 编程精解 中文第三版 二、程序结构

37215
来自专栏北京马哥教育

鲜为人知的 Python 语法

所有人(好吧,不是所有人)都知道 python 是一门用途广泛、易读、而且容易入门的编程语言。

681
来自专栏pangguoming

IEnumerable 使用foreach 详解

自己实现迭代器 yield的使用 怎样高性能的随机取IEnumerable中的值 我们先思考几个问题: 为什么在foreach中不能修改item的值? 要实现f...

3214
来自专栏一个会写诗的程序员的博客

从 JavaScript 到 TypeScript

TypeScript 并不是一个完全新的语言, 它是 JavaScript 的超集,为 JavaScript 的生态增加了类型机制,并最终将代码编译为纯粹的 J...

963
来自专栏java达人

最有价值的50道java面试题(一)

来自骆昊的技术专栏 1、面向对象的特征有哪些方面? 答:面向对象的特征主要有以下几个方面: 1)抽象:抽象是将一类对象的共同特征总结出来构造类的过程,...

22310
来自专栏数据科学与人工智能

【Python环境】Python函数式编程指南(1):概述

1. 函数式编程概述 1.1. 什么是函数式编程? 函数式编程使用一系列的函数解决问题。函数仅接受输入并产生输出,不包含任何能影响产生输出的内部状态。任何情况下...

2076
来自专栏程序员八阿哥

王老板Python面试(4):Python面试攻略(嗨谈篇)

答:*args表示可变参数(variadic arguments),它允许你传入0个或任意个无名参数,这些参数在函数调用时自动组装为一个tuple; **kwa...

812
来自专栏deepcc

javascript 中的 delete

3408
来自专栏企鹅号快讯

列表和元组有什么区别

如果有了解过python中的列表和元组,你可能会知道相对于列表,元组是不可变的,也就是说元组中的数据不能随意更改。除了列表是用中括号表示而元组是用小括号表示之外...

2087

扫码关注云+社区