Как обрабатывать бесконечные совпадения из пользовательских регулярных выражений

Question

Давайте рассмотрим две следующие строки в C # (с использованием фреймворка .NET 3.5)

Regex regex = new Regex(@"^((E|e)t )?(M|m)oi (?<NewName>[A-Za-z]\.?\w*((\-|\s)?[A-Za-z]?\w{1,})+)$", RegexOptions.Compiled | RegexOptions.IgnoreCase);
Match m = regex.Match("moi aussi jaimerai etre un ordinateur pour pas m'énnerver ");

(извините, это французская программа:))

Когда они выполняются, процесс застревает в методе Match() и никогда не завершается. Я предполагаю, что есть некоторая проблема с пробелами в шаблоне регулярных выражений, но я хотел бы не изменять шаблон (на самом деле он установлен вне программы конечными пользователями моего инструмента), а иметь возможность остановить процесс (например, с таймаутом).

Знает ли кто-нибудь, является ли это общеизвестной проблемой с регулярным выражением .NET и существует ли простой способ обойти ее, или мне нужно поточить эти строки и прервать их при необходимости (определенно, мне бы не хотелось сделать это).

Answer 1

Если я ввожу выражение в Regexbuddy, оно выдает следующее сообщение

Попытка совпадения была прервана рано потому что регулярное выражение слишком сложный. Двигатель регулярных выражений вы планируете использовать его с не может справиться это вообще и крах. Уважать "катастрофический откат" в файл справки, чтобы узнать, как этого избежать ситуация.

Глядя вверх катастрофический откат дает следующее объяснение

Регулярные выражения убегающих: катастрофическое возвращение назад
Рассмотрим регулярное выражение (x + x +) + y. Прежде чем кричать от ужаса и сказать этот надуманный пример должен быть записывается как xx + y, чтобы точно соответствовать то же самое без тех ужасно вложенных квантификаторы: просто предположим, что каждый «х» представляет собой нечто более сложное, с определенными строками, которые сопоставляются оба "х". Смотрите раздел на HTML файлы ниже для реального примера.

Посмотрим, что произойдет, когда вы подадите заявку это регулярное выражение в xxxxxxxxxxy. Первый х + будет соответствовать всем 10 х символов. второй х + терпит неудачу. Первый х + потом возвращается к 9 матчам, а второй забирает оставшиеся х. Группа сейчас подобрана один раз. группа повторяется, но терпит неудачу при первом х +. Так как одно повторение было достаточно, группа совпадает. Y соответствует y и общее совпадение найденный. Регулярное выражение объявлено функциональный код доставляется на клиент, и его компьютер взрывается. Почти.

Вышеуказанное регулярное выражение становится ужасным, когда вы отсутствует в строке темы. Когда у не получается, двигатель регулярных выражений откатывается. В группе есть один итерация, в которую он может вернуться. второй х + соответствует только один х, так что не могу вернуться. Но первый х + может отказаться от одного х. Второй х + быстро соответствует хх. У группы снова есть один итерации, не выполнит следующую, и у меня не получается. Возвращаясь снова, второй х + теперь имеет один возврат положение, уменьшая себя, чтобы соответствовать х. Группа пробует вторую итерацию. Первый х + соответствует, но второй застрял в конце строки. Снова возвращаемся, первый х + в первая итерация группы уменьшает сам до 7 символов. Второй х + соответствует ххх. Сбой у, второй х + уменьшается до хх, а затем х. Теперь группа может соответствовать второй итерации, с одним х для каждого х +. Но это (7,1), (1,1) комбинация тоже терпит неудачу. Так оно переходит к (6,4), а затем (6,2) (1,1) а затем (6,1), (2,1) и затем (6,1), (1,2) и тогда я думаю, что вы начинаете чтобы получить дрейф.

Если вы попробуете это регулярное выражение для строки 10x в отладчике RegexBuddy, это займет 2558 шагов, чтобы выяснить окончательный у пропал, отсутствует. Для строки 11x это нужно 5118 шагов. За 12 требуется 10238 шагов. Очевидно, у нас есть экспоненциальная сложность O (2 ^ n) здесь. В 21x отладчик кланяется в 2.8 миллион шагов, диагностирование плохого случая катастрофического возврата.

RegexBuddy прощает обнаруживает, что он идет по кругу , и прерывает попытку матча. Другие регулярные выражения движки (например .NET) будут продолжать работать навсегда , в то время как другие потерпят крах с переполнение стека (как Perl, перед версия 5.10). Переполнения стека особенно неприятно на винде, так как они имеют тенденцию делать ваше заявление исчезают без следа или объяснения. Будьте очень осторожны, если вы запускаете веб сервис, который позволяет пользователям предоставлять их собственные регулярные выражения. люди с небольшим опытом регулярных выражений есть удивительное умение придумывать экспоненциально сложный регулярный выражения.

Полагаю, вам придется обрабатывать это в коде. Я бы посоветовал вам связаться с автором Regexbuddy и спросить, что нужно для обнаружения этого сценария.

Answer 2

Я думаю, вы должны просто запустить совпадение с регулярным выражением в отдельном потоке и позволить ему прервать его, если будет достигнут определенный максимальный срок.

Answer 3

Мне кажется, что в этом случае совпадение регулярных выражений растет в геометрической прогрессии. Смотрите блог BCL .

Лучшее решение - установить время ожидания для регулярных выражений, не связываясь с потоками.

Смотрите здесь, как удалить строки со временем ожидания .

Answer 4

Проблема в том, что в вашем регулярном выражении есть вложенные "циклы", которые делают его ужасно неэффективным (так что это в основном требует вечности из-за сложности выражения).

Если вы скажете, что хотите соответствовать, я могу попытаться найти более эффективное регулярное выражение для этого.

Answer 5

Как правило, регулярные выражения могут занять больше времени, чем вы ожидаете. Вы должны поэкспериментировать с регулярным выражением, использующим такой инструмент, как Regulator.