Возврат: обзор

Когда жадный квантификатор «выходит за пределы», движок выполняет возврат: он отступает, пробует другую конфигурацию, повторяет попытку. На простых выкройках это является невидимым; на плохо написанных шаблонах оно может стать экспоненциальным и заморозить браузер на несколько секунд. Это корень ReDoS (Обычный выражение «отказ в обслуживании»).

Pattern: .*\d
Sample:  abc123def
Steps:
  1.  .*  consumes everything: "abc123def"
  2.  \d  fails (end of string).
  3.  Backtrack: .* drops 'f' -> "abc123de", \d fails on 'f'.
  4.  Backtrack: .* drops 'ef' -> "abc123d", \d fails on 'e'.
  5.  ... and so on until \d finds a digit: match = "abc123" + "?"... actually
       the pattern matches "abc123" because .* leaves "def" and \d looks at '3'? No: the
       backtrack continues and .* ends up being "abc12", \d=3.  Final match: "abc123".

Двигатель всегда добирается туда, но если жадный квантор содержит еще один жадный квантификатор (например, (a+)+), количество конфигураций попытка может взорваться.

Катастрофические закономерности

Pattern: (a+)+b
Sample:  aaaaaaaaaaaaaaaaaaaaa

Нет завершающего b → шаблон не работает, но движок пытается попасть туда каждый раз. возможный раздел as. Экспоненциальный рост: с 30 a вы можете ждать несколько часов.

Опасности возврата и ReDoS

Если шаблон содержит перекрывающиеся или вложенные квантификаторы (например, (a+)+), механизм оценивает экспоненциальное количество путей, прежде чем произойдет сбой. Замена общих подстановочных знаков исключением классов символов значительно сокращает пути возврата.

Попробуйте это

Обзор упражнения

Дополнительная задача