C # dotnetcore Regex зависает, если ему дана длинная непрерывная строка

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-адресов в пользовательских комментариях.Когда предоставляется нормальный комментарий, он обрабатывается в кратчайшие сроки.Lorem ipsum, состоящий из 100 слов, обрабатывается за 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*)?";

Проверьте, как это регулярное выражение соответствует и как (?:[a-z\u00a1-\uffff0-9]+-?)* развернуто как [a-z\u00a1-\uffff0-9]+(?:-[a-z\u00a1-\uffff0-9]+)*, чтобы соответствовать шаблонам, чтобы каждый последующий шаблон не мог совпадать с одинаковыми символами.Я также слил некоторые негативные взгляды с общими "суффиксами".Обратите внимание, что (?:\S+(?::\S*)?@)? остается нетронутым, так как может потребоваться сопоставить любые : с до последнего : перед остальными совпадающими образцами.