Как избежать бесконечных циклов в классе регулярных выражений .NET?
-
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 для получения более подробной информации