Как избежать бесконечных циклов в классе регулярных выражений .NET?

StackOverflow https://stackoverflow.com/questions/1200655

  •  05-07-2019
  •  | 
  •  

Вопрос

Получил простую задачу получить выражение 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 попадает в бесконечный цикл, забирая весь процессор, который она получает.

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

Я что-то упускаю?Есть ли способ защититься от бесконечных циклов при совпадении регулярных выражений?

Это было полезно?

Решение

Хорошо, тогда давайте разберемся с этим:

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

(Я предполагаю, что вы имели в виду \"в вашей строке, экранированной C #, а не ""...перевод с 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 раз и продолжайте делать это до тех пор, пока не перестанете.Затем попытайтесь найти и сожрать ] потом.

Шаблон соответствует на основе [^]]* до тех пор, пока он не достигнет ].

Поскольку есть промежуток между ] и ", он не может сожрать ни одного из этих персонажей, но ? после (]") позволяет ему в любом случае возвращать true.

Теперь мы успешно подобрали ([^]]*(]")?) однажды, но в + говорит, что мы должны пытаться продолжать сопоставлять его столько раз, сколько сможем.

Это оставляет нас с:

Input: ] "]

Проблема здесь в том, что этот ввод может совпадать ([^]]*(]")?) ан бесконечный раз, никогда не будучи съеденным, и "+" заставит его просто продолжать пытаться.

По сути, вы сопоставляете "1 или более" ситуаций, когда вы можете сопоставить "0 или 1" с чем-то, за чем следует "0 или 1" с чем-то другим.Поскольку ни один из двух подшаблонов не существует в оставшихся входных данных, он продолжает соответствовать 0 из [^]]\* и 0 из (]")? в бесконечном цикле.

Входные данные никогда не проглатываются, а остальная часть шаблона после знака "+" никогда не оценивается.

(Надеюсь, я получил SO-escape-of-regex-escape прямо выше.)

Другие советы

Проблема здесь в том, что этот ввод может совпадать ([^]]*(]")?) бесконечное количество раз, даже не будучи поглощенным, и "+" заставит его просто продолжать попытки.

Это чертовски серьезная ошибка в .Реализация регулярных выражений NET.Регулярные выражения просто так не работают.Когда вы превращаете их в автоматы, вы автоматически получаете тот факт, что бесконечное повторение пустой строки по-прежнему остается пустой строкой.

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

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

Это показывает, что использование код с чем-либо нетривиальным может быть рискованно.Вы создали код, который может привести к бесконечному циклу, и компилятор регулярных выражений обязался.Ничего нового, чего не было сделано с первых 20, ЕСЛИ X = 0, ТО ПЕРЕХОДИМ к 10.

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

Чтобы ответить на первоначальный вопрос (т.е.как избежать бесконечного цикла с регулярным выражением), это стало легко с .Net 4.5, поскольку вы можете просто передать тайм-аут методам регулярных выражений.Существует внутренний таймер, который остановит цикл регулярных выражений по истечении времени ожидания и вызовет исключение RegexMatchTimeoutException

Например, вы могли бы сделать следующее

string input = "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$";
bool ismatch = Regex.IsMatch(input, pattern, RegexOptions.None, TimeSpan.FromSeconds(5));

Вы можете проверить MSDN для получения более подробной информации

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top