正则表达式导致无限挂起

Question

我有以下正则表达式，它从不计算并无限挂起:

import java.util.regex.Matcher
String AUTOGENERATED_HEADER = "#-=-=-= AUTOGENERATED HEADER =-=-=-"
String AUTOGENERATED_FOOTER = "#-=-=-= AUTOGENERATED FOOTER =-=-=-"

String messages = '''#-=-=-= AUTOGENERATED HEADER =-=-=-
a=b
c=d
x=y
#-=-=-= AUTOGENERATED FOOTER =-=-=-
'''


Matcher matcher = messages =~ /${AUTOGENERATED_HEADER}[\r\n]+((.*[\r\n]*)*)${AUTOGENERATED_FOOTER}/
matcher.find()​

问题出在 (.*[\r\n]*) 部分。当我将其更改为 (.*[\r\n]+) 时，它起作用了。

您可以尝试使用正则表达式 here .任何人都可以解释这怎么可能吗？

Answer 1

这里是一个灾难性的回溯案例。参见 your regex demo .罪魁祸首是包含在其他子模式中的 (.*[\r\n]*)* 部分。嵌套的量词会导致过多的回溯，您可以在 regex101.com 的 regex 调试器页面上看到这一点。

一个解决方案是使用惰性点匹配:将 [\r\n]+((.*[\r\n]*)*) 替换为.*? 并在模式的开头添加 (?s) 修饰符，或使用展开版本(这对于长输入来说更好，但需要一些硬编码).

参见 (?s)#-=-=-= AUTOGENERATED HEADER =-=-=-.*?#-=-=-= AUTOGENERATED FOOTER =-=-=-在行动中。使用

Matcher matcher = messages =~ /(?s)${AUTOGENERATED_HEADER}.*?${AUTOGENERATED_FOOTER}/