JavaScript的正则expression式挂起(使用V8)

即时通讯使用这个正则expression式来获取文件中的标签的内容。

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

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

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

任何人都有一个想法,为什么第一个花了太长时间?

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

不同的虚拟机对正则expression式匹配有不同的反应,因为灾难性的回溯。 有些人会简单地报告“不匹配”。 在V8中,就像编写任何其他无限或接近无限循环一样。

使用非贪婪的*会做你想做的(你想停在第一个</tag:main> ,而不是最后一个),但是仍然会对缺less结束序列的长空格string进行灾难性的回溯。

确保内括号中的相同字符不能匹配交替的两侧,将问题从一个指数的问题减less到string长度的线性问题。 使用一个字符类而不是交替,或者在交替条的右边放置\n\n是不相交的. 所以如果你碰到一个很长的空格序列,正则expression式引擎在结束之前不会尝试所有的左右等组合。

我认为这是灾难性的回溯。

我认为这个问题的一部分很可能就是这个点和这个点不是相互排斥的。

如果我改变你的表情

 <tag:main>((?:.|[\r\n])*)</tag:main> 

并在Regex Buddydebugging器中运行它,如果testingstring不匹配,它会更快地失败。

而不是(?:.|\s)* ,您可以使用[^]*来匹配任何字符,包括各种forms的换行符。

没有改变,所以没有灾难性回溯的风险。