如何避免.NET RegEx类中的无限循环？

Question

获得一个简单的任务来获取XPath表达式并返回一个与(可能)选择的节点的父节点匹配的前缀.

例:

/aaa/bbb       =>   /aaa
/aaa/bbb/ccc   =>   /aaa/bbb
/aaa/bbb/ccc[@x='1' and @y="/aaa[name='z']"] => /aaa/bbb

因为方括号内的模式可能包含引号内的括号,所以我决定尝试使用正则表达式来实现这一点.这是一段代码片段:

string input =
    "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
                                            //  ^-- remove space for no loop
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$";

System.Text.RegularExpressions.Regex re =
    new System.Text.RegularExpressions.Regex(pattern);
bool ismatch = re.IsMatch(input); // <== Infinite loop in here
// some code based on the match

因为模式是相当规则的,我寻找'/'后面跟着一个标识符,然后是一个在字符串末尾匹配的可选组(....)？$

代码似乎工作但输入字符串的不同值,我发现通过简单地插入一个空格(在注释中显示的位置),.NET IsMatch函数进入一个无限循环,获取它获得的所有CPU .

现在无论这个正则表达式模式是否是最好的(我有更复杂但简化它来显示问题),这似乎表明使用RegEx与任何不重要的事情可能是非常危险的.

我错过了什么吗？有没有办法防止正则表达式匹配中的无限循环？

Answer 1

好吧,让我们打破这个:

Input: /aaa/bbb/ccc[@x='1' and @y="/aaa[name='z'] "]
Pattern: /[a-zA-Z0-9]+(\[([^]]*(]")?)+])?$

(我假设你的意思是"在你的C#-escaped字符串中,而不是"......从VB.NET翻译？)

首先,/ [a-zA-Z0-9] +会吞噬第一个方括号,留下:

Input: [@x='1' and @y="/aaa[name='z'] "]

如果在EOL之前有0或1个实例,则外部组(\ [([^]]*(]"")？)+])？$"应该匹配.所以让我们在内部查看它是否匹配任何内容.

"["立刻被狼吞虎咽,让我们:

Input: @x='1' and @y="/aaa[name='z'] "]
Pattern: ([^]]*(]")?)+]

分解模式:匹配0个或更多非]字符,然后匹配"] 0或1次,并继续这样做,直到你不能.然后尝试找到并吞噬一个].

模式基于[^]]*匹配,直到达到].

由于在]和"之间有一个空格,它不能吞噬这些字符中的任何一个,但是？ after (]")允许它无论如何都返回true.

现在我们已成功匹配([^]]*(]")？)一次,但+表示我们应该尝试不断匹配它.

这让我们:

Input: ] "]

这里的问题是,这种输入可以匹配([^]*(]")？)的无限 +'将迫使它只是不断尝试的时间而没有被吞噬了,和’.

你基本上匹配"1或更多"的情况,你可以匹配"0或1"的东西,然后是"0或1"的其他东西.由于两个子模式都不存在于剩余的输入中,因此它在无限循环中保持匹配[^]]\*的 0和(]")的 0 .

输入永远不会被吞噬,"+"之后的其余模式永远不会被评估.

(希望我在正上方得到了SO-escape-of-regex-escape.)