C# dotnetcore 正则表达式在给定长且完整的字符串时挂起

Question

我有一个正则表达式，当它试图匹配一个长的、完整的字符串时挂起。这是一个示例控制台应用程序:

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example
{
    public static void Main()
    {
        Stopwatch sw;
        string pattern = @"(?:(?:https?|ftps?):\/\/)?(?:\S+(?::\S*)?@)?(?:(?!10(?:\.\d{1,3}){3})(?!127(?:\.\d{1,3}){3})(?!169\.254(?:\.\d{1,3}){2})(?!192\.168(?:\.\d{1,3}){2})(?!172\.(?:1[6-9]|2\d|3[0-1])(?:\.\d{1,3}){2})(?:[1-9]\d?|1\d\d|2[01]\d|22[0-3])(?:\.(?:1?\d{1,2}|2[0-4]\d|25[0-5])){2}(?:\.(?:[1-9]\d?|1\d\d|2[0-4]\d|25[0-4]))|(?:(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)(?:\.(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)*(?:\.(?:[a-z\u00a1-\uffff]{2,})))(?::\d{2,5})?(?:\/[^\s]*)?";
        string input = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";

        Console.WriteLine("Press any key to match regex.");
        Console.ReadKey();
        Console.WriteLine("Starting regex...");

        sw = Stopwatch.StartNew();
        Match m = Regex.Match(input, pattern, RegexOptions.IgnoreCase | RegexOptions.Multiline);
        sw.Stop();


        Console.WriteLine($"Regex completed in {sw.Elapsed}. Press any key to exit.");
        Console.ReadKey();
    }
}

Regex 用于在用户生成的评论中查找 URL。当提供普通评论时，它会立即处理。它处理一个 100 字的 lorem ipsum 大约需要 36 毫秒。一旦引入了一个完整的长字符串，正则表达式就会挂起，据我所知，它永远不会完成处理。该字符串不需要重复相同的字符。

如有任何帮助或见解，我们将不胜感激。

Answer 1

你的正则表达式的主要问题是在 */+ 量化组中有可选模式和强制性模式，参见 (?:[a-z\u00a1-\uffff0-9]+-?)*。当正则表达式引擎开始尝试所有可能的路由来匹配字符串时，这可能会导致(使用长的不匹配字符串)行为，并且可能会出现太多，以至于系统似乎卡住:灾难性的回溯.

因此，如果您打算使用简化的解决方案，则应避免使用类似的模式，使用

(?:(?:https?|ftp)://)(?:-\.)?[^\s/?.#-]+(?:\.[^\s/?.#-]+)*(?:/\S*)?

其中 (?:[^\s/?\.#-]+\.?)+ 展开为 [^\s/?.#-]+(? :\.[^\s/?.#-]+)*。虽然它更长，但与可选模式在量化组内时相比，引擎失败的速度要快得多。

如果你想修复原来的模式，使用

string pattern = @"(?:(?:http|ftp)s?://)?(?:\S+(?::\S*)?@)?(?:(?!1(?:0|27)(?:\.\d{1,3}){3})(?!1(?:69\.254|92\.168|72\.(?:1[6-9]|2\d|3[0-1]))(?:\.\d{1,3}){2})(?:[1-9]\d?|1\d\d|2[01]\d|22[0-3])(?:\.(?:1?\d{1,2}|2[0-4]\d|25[0-5])){2}(?:\.(?:[1-9]\d?|1\d\d|2[0-4]\d|25[0-4]))|(?:[a-z\u00a1-\uffff0-9]+(?:-[a-z\u00a1-\uffff0-9]+)*)(?:\.[a-z\u00a1-\uffff0-9]+(?:-[a-z\u00a1-\uffff0-9]+)*)*(?:\.[a-z\u00a1-\uffff]{2,}))(?::\d{2,5})?(?:/\S*)?";

检查如何 this regex matches以及 (?:[a-z\u00a1-\uffff0-9]+-?)* 是如何展开为 [a-z\u00a1-\uffff0-9]+(?:-[a-z\u00a1-\uffff0-9]+)* 来匹配模式，以便每个后续模式都无法匹配相同的字符。我还将一些负面前瞻与常见的“后缀”合并。请注意 (?:\S+(?::\S*)?@)? 保持不变，因为它可能需要匹配任何 : 直到最后一个 : 在其余的匹配模式之前。