为什么这个正则表达式挂有两个尾部反斜杠,但只有一个正常工作？

Question

我有以下代码使用正则表达式,当我运行它时挂在最后一行:

const char PathSeparator = '\\';
const string PathPrefix = "\\\\";

var reg = new Regex(string.Format("^{0}(([^{1}\r\n\v\f\u2028\u2029]+){1}?)+$", 
    Regex.Escape(PathPrefix), Regex.Escape(PathSeparator.ToString())));

var test = @"\\Inbox\Test123\Intermediate\3322FB69-FE3F-407E-9E15-584382A407A2\\";
var matches = reg.Matches(test);
var group = matches[0].Groups[2];

如果我删除其中一个最终的反斜杠test,它可以正常工作,例如

var test = @"\\Inbox\Test123\Intermediate\3322FB69-FE3F-407E-9E15-584382A407A2\";

有人可以帮我弄清楚它为什么挂？我知道我可以设置超时; 那不是我的问题.

Answer 1

现在你有两个问题

我必须以著名的引言开始这个回答。虽然正则表达式是一个强大的工具，可以有效地解决很多问题（包括这个问题），但如果您不是该主题的专家，它也可能是一个很大的麻烦来源，并且会造成痛苦，而通过使用较低的值是完全可以避免的技术解决方案。

在这种情况下，您可以通过用斜杠分割输入字符串，然后验证自己生成的每个标记（是的，甚至可能使用正则表达式）来简单地完成相同的工作。这样做实际上可能是明智之举，因为它将极大地降低解决方案的复杂性。当未来需要“小调整”（增加复杂性）时，这将非常有价值。

也就是说，让我们看看有趣的事情：发生了什么？

为什么它会永远运行？

因为量词嵌套造成的过度回溯+。使用更温和的示例输入将更容易说明

\\Foo\Bar\Baz\\

让我们看看正则表达式引擎在输入此输入时会尝试匹配什么。

1) 第一次尝试：最里面的组匹配Foo\和Bar\和Baz\。由于尾随，进一步的重复失败\，然后输入结束标记无法匹配，因此尝试被拒绝并且引擎回溯。

请注意，如果尾部斜杠不存在，则正则表达式引擎将声明成功并在此时返回。

2）因为最里面组中的斜杠是可选的，所以下一次尝试是Foo\, Bar\，Baz这显然也失败了。更多的回溯。

3) 下一个候选匹配最里面组的四个重复：Foo\、Bar\、Ba和z\。失败，更多的回溯。

从现在开始，我将通过用单个空格分隔最里面组的重复来简单地列出尝试的匹配：

Foo\ Bar\ Ba z      (i.e. 4 repetitions of length 4, 4, 2, 1, and fails)
Foo\ Bar\ Ba
Foo\ Bar\ B az\
Foo\ Bar\ B az
Foo\ Bar\ B a
Foo\ Bar\

等等。

这里需要注意的是，我们进行了不合理的多次尝试，甚至排除了尾随的“Baz”片段可以成为成功匹配的一部分：我们必须考虑“Baz”，“Ba”+“z”，“ Ba”、“B”+“az”、“B”+“a”和“B”；一般来说，对于长度为 N 的线段，可能性的数量是 N！（阶乘）。正如维基百科所示，阶乘函数的增长超出了人类直观的理解。

由于您的示例输入包含长度为 36 的最后一段，因此尝试将此正则表达式与格式不正确的输入相匹配将永远无法完成。

如何防止这种情况发生？

在这种情况下，这非常简单。因为您知道，对于例如“Baz”，如果整体匹配失败，则尝试将其分割成更小的块是没有意义的（因为这些块需要用斜杠分隔，我们已经知道它们不是因为斜杠）不是尝试匹配的允许部分），请使用原子捕获组：

var reg = new Regex(string.Format(
    "^{0}(?>([^{1}\r\n\v\f\u2028\u2029]+{1}?))+$",
    Regex.Escape(PathPrefix),
    Regex.Escape(PathSeparator.ToString())));

这只会回溯 1 次，而不是 N 次！对于不成功匹配的每个路径段，将失败的时间减少到几乎为零。