Javascript 与大写字母相关的正则表达式无限循环

Question

我在 node.js 中创建了一个正则表达式，能够匹配看起来像 URL 的文本部分。但是，在某些文本上，我的正则表达式创建了一个无限循环！

整个正则表达式是：

/(((ftp|https?):\/\/|(www\.))?([a-z\d]+-?)+\.[a-z\d/\-._~:?#@!$&'*+,;=`]+)/gi

但是经过一些debug，我发现死循环只是这部分造成的：/((ftp|https?):\/\/|(www\.))?([a-z\d]+-?)+\./gi

> let r = /((ftp|https?):\/\/|(www\.))?([a-z\d]+-?)+\./gi
> const txt = "www.ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_~:/?#@!$&'*+,;=`"
> r.test(txt)
^CError: Script execution interrupted. // infinite loop

我做了更多的测试来了解这个问题。首先，没有标志：

> r = /((ftp|https?):\/\/|(www\.))?([a-z\d]+-?)+\./
> r.test(txt)
true

令人惊讶的是，它有效！测试 2 只有 g 标志：

> r = /((ftp|https?):\/\/|(www\.))?([a-z\d]+-?)+\./g
> r.test(txt)
true

也可以！测试 3 只有 i 标志：

> r = /((ftp|https?):\/\/|(www\.))?([a-z\d]+-?)+\./i
> r.test(txt)
^CError: Script execution interrupted. // infinite loop

失败...所以我决定删除 i 标志并改用 A-Z：

> r = /((ftp|https?):\/\/|(www\.))?([a-zA-Z\d]+-?)+\./
> r.test(txt)
^CError: Script execution interrupted. // infinite loop

不工作...有人理解这个问题吗？有解决办法吗？

Answer 1

这是灾难性的回溯。

为避免这种现象，请尝试构建一个始终从左到右进行的正则表达式（即匹配失败将停止正则表达式，而不是让它在其他地方尝试某些子部分）。换句话说：不应该有几种方法来匹配你的字符串的一部分（或者正则表达式引擎会尝试所有这些，在某些情况下，这会导致一个指数级大小的可能性树）。

试图了解你的真正目标，我可以提出这个解决方案：

/((ftp|https?):\/\/|(www\.))?([a-z\d]+)(-[a-z\d]+)*\./gi

（这也可能更正确）

另一种解决方案是使用非回溯正则表达式引擎，例如 R2（是的，有一个节点绑定）。根据我的经验，节点中的 R2 比标准正则表达式引擎慢，因此只有当您有用户输入正则表达式时它才有意义，因为当您是正则表达式作者时，您通常可以找到一个非灾难性的正则表达式。

Javascript 与大写字母相关的正则表达式无限循环

Javascript regexp infinite loop related to uppercase letters

javascript

regex

v8

node.js