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

IT技术 javascript regex v8
2021-01-31 00:05:55

我使用这个正则表达式来获取文件中标签的内容。

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

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

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

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

3个回答

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

由于灾难性的回溯,不同的 VM 对 regexp 匹配有不同的react。有些人会简单地报告“不匹配”。在 V8 中,就像编写任何其他无限或接近无限循环一样。

使用 non-greedy*会做你想做的事(你想在第一个停止</tag:main>,而不是最后一个),但仍然会对缺少结束序列的长空格字符串进行灾难性的回溯。

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

@Martin:在 JavaScript 中,.相当于[^\r\n\u2028\u2029]
2021-04-04 00:05:55
很好的解释。你知道 dot 是否也包含 \r 吗?
2021-04-09 00:05:55

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

我认为问题的一部分很可能是点和 \s 并不相互排斥。

如果我把你的表情改成

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

并在 Regex Buddy 调试器中运行它,如果测试字符串不匹配,它会更快地失败。

oop!如果你让它变得懒惰而不是贪婪,这会阻止问题吗?<tag:main>((?:.|\s)*?)</tag:main>
2021-03-23 00:05:55
.|\s 是匹配所有字符。因为 。匹配除新行以外的所有字符。
2021-04-04 00:05:55
我不认为它会那样做。我将您的 Regex 粘贴到 RegexBuddy 并将其评论树粘贴到我的帖子中。
2021-04-04 00:05:55
我现在已经完全改写了我的答案!
2021-04-09 00:05:55
在粘贴到 RegexBuddy 之前,您应该删除额外的 \。使用 \\ 是因为它是传递给 RegExp 构造函数的 javascript 字符串。
2021-04-12 00:05:55

代替(?:.|\s)*,您可以使用[^]*匹配任何字符,包括各种形式的换行符。

没有交替,所以没有灾难性回溯的风险。