Javascript正则表达式挂起(使用v8)

Question

我正在使用此正则表达式来获取文件中的标记内容.

var regex = new RegExp("<tag:main>((?:.|\\s)*)</tag:main>");

这会导致v8引擎无限期挂起.

现在,如果我使用new RegExp("<tag:main>([\s\S]*)</tag:main>"),一切都很好.

任何人都知道为什么第一个需要太长时间？

Answer 1

这会灾难性地回溯在最后一个结束</tag:main>标记之后出现的长序列空间.考虑主题字符串以100个空格结尾的情况.首先,它将它们全部与.交替的左侧相匹配.这失败了,因为没有结束标记,所以它尝试匹配最后一个字符\s.这也失败了,所以它尝试匹配倒数第二个空格作为a \s和最后一个空格作为a ..失败(仍然没有结束标记)所以它尝试最后一个空格作为\s.当失败时它将第三个到最后一个空格匹配为a \s并尝试所有4种方式来匹配最后两个空格.当失败时,它会尝试将倒数第四个空格作为a \s和最后3个空格中的所有8个方向.然后是16,32等.宇宙在它到达第100个到最后的空间之前结束.

由于灾难性的回溯,不同的VM对regexp匹配的反应不同.有些人只会报告"不匹配".在V8中,它就像编写任何其他无限或近无限循环一样.

使用非贪婪*会做你想要的(你想要在第一个</tag:main>而不是最后一个停止),但仍然会对缺少关闭序列的长串空间进行灾难性的回溯.

确保内括号中的相同字符不能与交替的两侧匹配将减少从指数一到一的问题,该问题在字符串的长度上是线性的.使用字符类而不是替换或放在\n交替栏的右侧. 如果您按下一长串空格,则正则表达式引擎在终止之前不会尝试所有左右 - 左等组合\n,.因此是不相交的.