Javascript正则表达式卡住了（使用v8引擎）

Question

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

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

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

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

有人知道为什么第一个方法需要太长时间吗？

- Heinrich Lee Yu

---

正则表达式的创建卡住了还是应用它的时候？你发布的代码行在我这里运行良好。 - cobbal

创建不会挂起，只有在测试或匹配时使用它。使用长字符串。 - Heinrich Lee Yu

你尝试过非贪婪匹配吗？var regex = new RegExp("<tag:main>((?:.|\\s)*?)</tag:main>"); 如果文档中有多个标签元素，你的正则表达式可能会引起问题。 - Andy E

Answer 1

这会在最后一个闭合的<tag:main>标签之后出现长空格序列时发生灾难性的回溯。考虑字符串以100个空格结尾的情况。首先，它将所有这些空格与交替符左侧的.匹配。由于没有关闭标签，所以匹配失败，然后它尝试使用\s将最后一个字符进行匹配。这也失败了，所以它尝试将倒数第二个空格作为\s，并将最后一个空格作为.进行匹配。这仍然失败了（仍然没有关闭标签），所以它尝试将最后一个空格作为\s进行匹配。当这也失败时，它将把倒数第三个空格作为\s进行匹配，并尝试以全部四种方式匹配最后两个空格，如果再次失败，则将倒数第四个空格作为\s进行匹配，并在最后三个空格上尝试所有八种方式，然后是16、32等。在它达到倒数100个空格之前，宇宙就已经结束了。

不同的虚拟机对由于灾难性回溯而导致的正则表达式匹配问题有不同的反应。有些会简单地报告“无匹配项”。在V8中，它就像编写任何其他无限或接近无限循环一样。

使用非贪婪*将做到您想要的（您希望停止在第一个</tag:main>而不是最后一个），但对于缺少关闭序列的长空格字符串仍会发生灾难性的回溯。

确保内部括号中的相同字符不能同时匹配交替符的两侧，将问题从指数级降低到与字符串长度成线性比例。使用字符类代替交替符或将\n放在交替竖杠的右边。如果遇到长序列的空格，则正则表达式引擎不会在终止之前尝试所有的左-右-左等组合，因为\n和.是不相交的。

- Erik Corry

---

好的解释。你知道点号是否也包括 \r 吗？ - Martin Smith

在JavaScript中，.等同于[^\r\n\u2028\u2029]。 - Alan Moore

Answer 2

我猜测它正在进行灾难性的回溯。

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

如果我将您的表达式更改为

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

当你在Regex Buddy调试器中运行它并且测试字符串不匹配时，它会更快地失败。

- Martin Smith

---

.|\s 用于匹配所有字符。因为 . 匹配除换行符以外的所有字符。 - Heinrich Lee Yu

我不认为它会这样做。我将你的正则表达式粘贴到RegexBuddy中，并将其注释树粘贴到我的帖子中。 - Martin Smith

在将文本粘贴到RegexBuddy之前，您应该删除额外的\。使用\是因为它是传递给RegExp构造函数的JavaScript字符串。 - Heinrich Lee Yu

糟糕！如果你把它变成懒惰模式而不是贪婪模式，这会停止问题吗？ - Martin Smith

我已经完全重写了我的答案！ - Martin Smith

Answer 3

你可以使用[^]*来匹配包括各种形式的换行符在内的任何字符，而不是使用(?:.|\s)*。

由于没有备选项，因此不存在灾难性回溯的风险。

- Jim Shark