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

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}导致问题的原因，因为这允许回溯，但我不确定。有什么想法吗？

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]:\\|\\\\)(?>[^\\\/\:*?<>"|]+(?:\\[^\\\/\:*?<>"|]+)*)\\?$
                     ^^^                                       ^                          

请注意，这:不是特殊的正则表达式元字符，不应转义。在字符类中，只有-, ^,\和]通常需要转义，所有其他字符在那里也并不特殊。

有关灾难性回溯的更多信息，请参阅爆炸量词陷阱。