> Beware of patterns that contain nested indefinite repeats. These can take a long time to run when applied to a string that does not match.
To say that it takes a "long time" is an understatement: the time taken would be exponential, specifically 2^n, where n is the number of "a" characters. This behavior could lead to a "regular expression denial of service" (ReDoS) if you run such a expression on user-provided input.
To not be hit by ReDoS, do one (or maybe more than one) of the three things:
* Write your expression so that it is not vulnerable. https://www.regular-expressions.info/redos.html is a good resource (both the "atomic" and "possessive" options are available in PHP/PCRE). Use a "ReDoS detector" or "regex linter" if your eyeballs can't catch all the issues.
* Set up some limits for preg_match. Use `ini_set(...)` on the values mentioned on https://www.php.net/manual/en/pcre.configuration.php. Reducing the limits might cause regexes to fail, but that is usually better than stalling your whole server.
* Use a different regex implementation. There used to be an RE2 extension; not any more!
Производительность
Некоторые элементы, которые могут встречаться в шаблонах, являются более эффективными, чем ряд других. Например, гораздо эффективней использовать символьный класс [aeiou] вместо набора альтернатив (a|e|i|o|u). Как правило, более простая конструкция является более эффективной. Книга Джеффри Фридла содержит много обсуждений вопроса оптимизации регулярных выражений.
Если шаблон начинается с .* и используется флаг
PCRE_DOTALL,
шаблон неявно заякоривается, так как он может совпадать только
в начале строки. Но если
PCRE_DOTALL
не используется, PCRE не может выполнить соответствующую оптимизацию,
так как В этой ситуации метасимвол «.» не соответствует символу начала
строки (если обрабатываемые данные содержат переводы строк, такой шаблон
может соответствовать шаблону не от начала строки, а от позиции
непосредственно после перевода строки).
Например, применяя шаблон
(.*) second
к строке «first\nand second» (где \n обозначает символ
перевода строки), значение, захваченное первой подмаской, будет «and».
Чтобы обработать все возможные точки соответствия, PCRE пытается
сопоставить шаблон после каждого символа перевода строки.
Если вы используете подобные шаблоны для обработки данных, не содержащих переводы строк, для лучшей производительности используйте модификатор PCRE_DOTALL, либо начинайте шаблон с ^.* для указания явного заякоривания. Это предотвратит PCRE от поиска символов новых строк и дополнительных попыток сопоставить шаблон с каждой такой найденной позицией.
Избегайте шаблонов, которые содержат вложенные неограниченные повторения.
Сопоставление их со строками, не содержащими совпадений, занимает
длительное время. Рассмотрим пример шаблона
(a+)*
Он может соответствовать «aaaa» тридцатью тремя различными способами, и эта цифра очень быстро растёт при увеличении строки. (В данном примере, квантификатор * может совпадать 0, 1, 2, 3 или 4 раза, и для каждого такого случая, кроме нуля, квантификатор + также может совпадать различное число раз.) Если остаток шаблона таков, что все совпадение терпит неудачу, PCRE должна попробовать все возможные варианты совпадения, что может потребовать огромного количества времени.
При помощи оптимизации можно отловить наиболее простые случаи, такие как
(a+)*b
где следом идёт литеральный символ. Прежде, чем производить стандартную
процедуру поиска, PCRE проверяет в последующей подстроке наличие
символа «b», и, в случае отсутствия такового, попытка сопоставления
немедленно завершается неудачей. Однако, когда последующего литерала нет,
оптимизация не может быть применена. Вы можете ощутить разницу, сравнив поведение
(a+)*\d
с поведением приведённого выше шаблона. Первый определяет
невозможность сопоставления практически сразу же, при сопоставлении
со строкой состоящей из символов «a», в то время как второй
тратит длительное время на поиск в строках длиннее 20 символов.
add a note
User Contributed Notes 1 note
arthur200126 at gmail dot com ¶
9 months ago
