javascript - JS里的正则匹配会出现无穷解最终导致浏览器卡死

Question

为什么下面的正则会让浏览器卡死呢？

tag_re = '"';
text = "ccccc\nddddddddasdfasdfasdfasdfasdfasdfaddddsdfasahtml\n`";
console.log(text.match(new RegExp('^(.+?|\\n[^\\n])*?[^`]' + tag_re + '[^`]')));

Answer 1

儘量不要用嵌套的非貪婪模式，尤其是通配的那種，尤其尤其是可有可無的那種，尤其尤其尤其是可能無法匹配的那種。要體會正則引擎把所有組合嘗試之後才發現本來就可以確定無法匹配的時候的心情。。。還是在人家辛辛苦苦把每一個可能匹配記下來的情況下。。。這樣對待人家人家不生氣就怪了~

(.+?|\n[^\n])*?[^`]```[^`]

改成

(?:[^`]|`{1,2}(?!`)|`{4,}|\n(?!\n))*```

Answer 2

应该是 浏览器 JS正则引擎 实现的问题. 实际测一下:

text = "ccccc\nddddddddasdfasdfasdfasdfasdfasdfaddddsdfasahtml\n`";
console.log(text.match(new RegExp('^(.+?|\\n[^\\n])*?[^`]```[^`]')));

IE10中瞬间返回; Chrome38.0.2125.101瞬间返回; FireFox33 中浏览器死掉.

在perl中运行类似的正则的话, 可以在debug中看到:

Intuit: trying to determine minimum start position...
  Did not find floating substr "```"...
Match rejected by optimizer

因为找不到 ```, 直接没有过正则就返回了.

Answer 3

我还是尝试答一下吧
^(.+?|\\n[^\\n])*?这里有两处使用到了忽略优先两次?，那么整个正则表达式尝试匹配时首先跳过这段，先尝试后面的[^]```[^]的规则，如果后面的规则无法匹配就会回到^(.+?|\\n[^\\n])*开始匹配。

由于这是个分支结构，所以它首先尝试匹配.+?，但是这里还是忽略优先的情况，所以跳过，先尝试匹配后面的分支，\n[^\n]，当后面的分支无法匹配时候会回到原来的带忽略优先的量词的规则.+。