Когда поиск совпадения превращается в перебор
Регулярное выражение — это шаблон, по которому программа ищет или проверяет текст. Некоторые движки выполняют такую проверку с возвратом: если выбранный путь не сработал, они возвращаются к развилке и пробуют другой вариант.
Пока шаблон однозначен, это обычно быстро. Но если в нём есть несколько способов сопоставить один и тот же фрагмент — например, повторяющиеся части, допускающие разные разбиения строки, — число вариантов может резко вырасти. Особенно опасен случай, когда длинная строка почти подходит, но в самом конце обнаруживается символ, из-за которого всё выражение не совпадает. Движку приходится проверять множество разбиений, прежде чем признать неудачу.
Почему страдает всё приложение
Проверка выполняется как обычная работа программы. Если она надолго занимает поток, который обслуживает запросы или пользовательский интерфейс, новые задачи ждут своей очереди. В результате страница может перестать реагировать, а сервер — медленно отвечать или исчерпать доступные ресурсы. Это явление называют катастрофическим возвратом: «катастрофа» здесь означает резкий рост времени вычисления, а не особый тип ошибки в самом тексте.
Как снизить риск
Разработчики проверяют выражение не только на типичных строках, но и на длинных почти подходящих строках. Помогают более однозначные шаблоны, ограничения на длину входных данных и тайм-ауты для проверки. В некоторых движках можно выбрать алгоритм, который избегает такого перебора, хотя он может поддерживать не все возможности регулярных выражений.
Поэтому короткий шаблон не обязательно безопасен: важнее, сколько альтернатив он заставляет движок рассматривать, когда совпадение срывается в последний момент.
