c# - 仅在 .net 中的正则表达式灾难性回溯

Question

我有一个在 http://gskinner.com/RegExr/ 上运行良好的正则表达式和 http://regexhero.net/tester/这是.net。但是它在我的 .net v4.5 代码中超时 (1h+)。

(?<OuterDescription>[ \t]*--[ \t]+Description:[ \t]+(?!\<Description)(?<Description>\S[^\r\n]{1,})((\r\n|\r|\n)(?![ \t]*--[ \t]*Modified)[^\r\n]*)*)

带有示例数据:

-- ========================================================================================================
-- Author:        A Name
-- Create date: 11/26/2012
-- Description:    A description

    --    A multiline description 
        -------------------------------------- Group Name -----------------------------------------
        -- More details
        -- More details
--
--  Modified: 01/7/2012 - Some reason
--  Modified: 12/7/2012 - Some other reason
-- ========================================================================================================

我的代码是这样的

var isMatch = new Regex(pattern, RegexOptions.None, TimeSpan.FromMinutes(1)).IsMatch(_fileText);

希望 OuterDescription 从 -- Description 捕获到 -- Modified 之前

我已将其缩小到接近尾部的 [^\r\n]*。我不知道如何解决这个问题，以免在 C# 中超时

编辑:

感谢您的讨论和回答。它有助于将超时从描述中移出。不幸的是我仍然有问题。这是我目前所拥有的

[ \t]*--[ \t]+={3,}
(\r\n|\n|\r)
(?<OuterAuthor>[ \t]*--[ \t]+
    Author:[ \t]+
    (?!\<Author)
    (?<Author>\S[^\r\n]+))
(\r\n|\n|\r)
(?<OuterCreateDate>[ \t]*--[ \t]+
    Create\ [Dd]ate:[ \t]+
    (?!\<Create)
    (?<CreateDate>\S[^\r\n]{1,}))
(\r\n|\n|\r)
(?<OuterDescription>[ \t]*--[ \t]+
    Description:[ \t]+
    (?!\<Description)
    (?<Description>\S[^\r\n]+)
    (?<MultilineDescription>((\r\n|\r|\n)|[^\r\n]*)*?)
    (?=(
        [ \t]*--[ \t]*Modified)|(
        [ \t]*--[ \t]*={3,})
    ))

这很好用，但是一旦我在此之后添加一些东西，它就会超时。

抱歉，我没有先提到这个，我以为一个小小的贪婪的星际变化将是我所有的问题。为了了解最终图片，我有一个 isAdded bool 值，它将确定我是否检查修改过的行(与描述相同)然后以页眉/页脚结束。像这样

var entireCommentHeaderNamedGroupsRegex = headerFooterRegex + newlineRegex
                                          + authorRegex + newlineRegex
                                          + createDateRegex + newlineRegex
                                          + descriptionRegex + newlineRegex
                                          + (_isAdded ? modifiedRegex + newlineRegex : "")
                                          + headerFooterRegex;

一些未修改时的示例数据:

-- =============================================
-- Author:      Garrett Carson
-- Create date: 10/4/2013
-- Description: This is a test
-- =============================================
CREATE PROCEDURE dbo.ThisIsATest
AS
BEGIN
    PRINT 'This is a test'
END

此外，正如评论中提到的，我对正则表达式(在这种规模上)还很陌生，如果这实际上不是灾难性的回溯，请原谅我的术语。

编辑2

作为最后的编辑，我最终选择了一个穷人的 fsm

string currentState = "LookForAuthor"
foreach (var line in lines) {
    switch currentState {
        case "LookForAuthor" : {
            ... use author regex ... save to author variable ...
            if(found) currentState = "LookForCreateDate"
            else throw new InvalidCommentException();
        }
        case "LookForCreateDate": {
            ... use createDate regex ... save to createDate variable ...
            ...
        }
        ...
    }
}
if (!_isAdded && !(currentState == "Modified-FirstLine" || currentState == "Modified-MoreLines")) {
    throw new InvalidCommentException();
}

然后我重新考虑使用枚举。逐行应用一口大小的正则表达式不再导致超时。

Answer 1

以下似乎对我有用(为清楚起见，使用 RegexOptions.IgnorePatternWhitespace):

@"(?<OuterDescription>[ \t]*--[ \t]+
    Description:[ \t]+
    (?!\<Description)
    (?<Description> \S[^\r\n]{1,})
    (?<MultilineDescription>(\r?\n|[^\r\n]*)*?)
    (?=[ \t]*--[ \t]*Modified)
)";

一般来说，嵌套贪婪量词会导致您遇到的问题。不幸的是，我太累了，无法深入调查，但如果你对出了什么问题感到好奇，我可以记下来稍后再调查