修复正则表达式中的灾难性回溯问题

Question

问题

我在使用以下正则表达式来检查有效的文件路径：

^(?:[a-zA-Z]\:\\|\\\\)([^\\\/\:\*\?\<\>\"\|]+(\\){0,1})+$

使用测试字符串 V:\Sample Names\Libraries\DeveloperLib\DeveloperComDlgs\res 被识别为有效。我甚至可以在字符串开头添加无效字符而没有问题。但是，当我向字符串末尾添加无效字符时，网页由于灾难性回溯而冻结。

是什么导致了这个正则表达式字符串的问题？

---

分解正则表达式

完整字符串： ^(?:[a-zA-Z]\:\\|\\\\)([^\\\/\:\*\?\<\>\"\|]+(\\){0,1})+$

第一组： (?:[a-zA-Z]\:\\|\\\\)

• 检查以下两者之一
  • 大写或小写字母后跟冒号和反斜杠
  • 双反斜杠

第二组： ([^\\\/\:\*\?\<\>\"\|]+(\\){0,1})

• 第一部分： [^\\\/\:\*\?\<\>\"\|]+
  • 确保没有非法字符 (\ / : * ? < > " | )
• 第二部分： (\\){0,1}
  • 检查分节之间的反斜杠，如有必要，则重复多次

我认为问题可能是 {0, 1} 导致的，因为它允许回溯，但我不确定。你有什么想法吗？

- Sara Fuerst

---

如果你的模式包含类似于(a+b?)+这样的内容，它很容易出现灾难性回溯。请改为a+(ba+)*。 - Wiktor Stribiżew

@WiktorStribiżew 所以在这种情况下，a = [^\\\/\:\*\?\<\>\"\|]，而 b = (\\){0,1}？ - Sara Fuerst

是的，请查看 https://regex101.com/r/dLiB9a/1 - Wiktor Stribiżew

^(?:[a-zA-Z]:|\\)(?:\\[^\\\/:*?<>"|]+)+\\?$ - Casimir et Hippolyte

实际上@CasimiretHippolyte的答案最好，如果有可用的所有格量词，我只会添加一个：^(?>[a-zA-Z]:|\\)(?:\\[^\\\/:*?<>\"|]+)++\\?$ 如果不允许尾随反斜杠，则为：^(?>[a-zA-Z]:|\\)(?:\\[^\\\/:*?<>\"|]+)++$。 - anubhava

Answer 1

你当前的正则表达式可以写成^(?:[a-zA-Z]:\\|\\\\)([^\\\/\:*?<>"|]+\\?)+$：注意在一个+量化组中的\\后面的?量化器（它等同于{0,1}限制量化器）。一旦类似于(a+b?) +的模式出现在模式中，就有可能出现灾难性的回溯。当匹配成功时，一切都很好，比如说，c:\12\34\aaaaaaaaaaaaaaaaaaa被很好地匹配了, 但是一旦出现不允许的字符导致无法匹配（尝试在末尾添加*，c:\12\34\aaaaaaaaaaaaaaaaaaa*），问题将出现。为了解决这个问题，可以使用可选组，其中每个子模式是强制性的，从而使可以匹配相同文本的量化的子模式不能紧接着彼此跟随。

在大多数情况下，您需要用展开的模式部分 a+(ba+)*（1个或多个出现的a，后跟0个或多个序列的b（不再是可选的）然后是1个或多个a（因此，在一个a和下一个a之间必须有一个b）来替换这些模式部分。如果您需要匹配末尾的可选\（因为^(a+b?)+$实际上可以匹配字符串末尾的b），则需要在末尾添加b?：a+(ba+)*b?。

因此，将其翻译为您当前的情况：

^(?:[a-zA-Z]:\\|\\\\)[^\\\/\:*?<>"|]+(?:\\[^\\\/\:*?<>"|]+)*$

或者如果允许在结尾处使用\：

^(?:[a-zA-Z]:\\|\\\\)[^\\\/\:*?<>"|]+(?:\\[^\\\/\:*?<>"|]+)*\\?$
                     |      a+       (   b       a+       )* b?

看看它在没有匹配时如何优雅地失败，或者如预期般匹配。

正如@anubhava所建议的那样，您可以进一步增强性能，通过使用占有量词（或原子组，因为例如.NET正则表达式引擎不支持占有量词）禁止回溯到分组模式中。一旦匹配成功，这些模式不会重新尝试，因此，失败可能会更快：

^(?:[a-zA-Z]:\\|\\\\)[^\\\/\:*?<>"|]+(?:\\[^\\\/\:*?<>"|]+)*+\\?$
                                                            ^

或原子组示例：

^(?:[a-zA-Z]:\\|\\\\)(?>[^\\\/\:*?<>"|]+(?:\\[^\\\/\:*?<>"|]+)*)\\?$
                     ^^^                                       ^                          

请注意，:不是特殊的正则表达式元字符，不应该进行转义。在字符类内部，只有-、^、\和]通常需要转义，其他所有字符也不是特殊的。了解有关The Explosive Quantifier Trap的更多信息，其中涉及到。

- Wiktor Stribiżew