Проблема поиска с бесконечным возвратом

Некоторые регулярные выражения, с виду являясь простыми, могут выполняться оооочень долго, и даже «подвешивать» интерпретатор JavaScript.

Рано или поздно с этим сталкивается любой разработчик, потому что нечаянно создать такое регулярное выражение –- проще простого.

Типичная ситуация: регулярное выражение работает нормально, но иногда, с некоторыми строками, «подвешивает» интерпретатор и потребляет 100% процессора.

В веб-браузере такой случай «убивает» страницу. Явно плохая ситуация.

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

Так что проблема, несомненно, достойна рассмотрения.

Вступление

План изложения у нас будет таким:

  1. Сначала взглянем на проблему, на то, как это могло произойти.
  2. Потом упростим ситуацию и увидим, почему проблема возникает.
  3. Ну и, наконец, исправим её.

Например, давайте рассмотрим поиск тегов в HTML.

Мы хотим найти все теги с атрибутами (или без них) типа: <a href="..." class="doc" ...>. Нужно, чтобы регулярное выражение работало надёжно, так как HTML приходит из Интернета и может быть некорректным.

В частности, нам нужно, чтобы регулярное выражение находило теги типа: <a test="<>" href="#"> – т.е. с символами < и > внутри атрибутов, так как это поддерживается стандартом HTML.

Простое регулярное выражение <[^>]+> не работает, потому что оно останавливает поиск на первом >, а нам нужно игнорировать <>, если они являются частью атрибута.

// поиск не достигает конца тега - неверно!
alert( '<a test="<>" href="#">'.match(/<[^>]+>/) ); // <a test="<>

Для того, чтобы правильно обрабатывать подобные ситуации, нужно более сложное регулярное выражение. Оно будет иметь вид: <tag (key=value)*>.

  1. Для имени тега tag: \w+,
  2. Для имени атрибута key: \w+,
  3. И значения атрибута value: строка в кавычках "[^"]*".

Если мы подставим это в паттерн, описанный выше, и добавим дополнительные пробелы \s, то получим следующее: <\w+(\s*\w+="[^"]*"\s*)*>.

Это регулярное выражение не идеально! Оно не поддерживает все детали синтаксиса HTML, например, значения без кавычек, есть способы улучшить его, но давайте не будем усложнять. Оно продемонстрирует нам проблему.

Кажется, регулярное выражение работает:

let reg = /<\w+(\s*\w+="[^"]*"\s*)*>/g;

let str='...<a test="<>" href="#">... <b>...';

alert( str.match(reg) ); // <a test="<>" href="#">, <b>

Отлично! Нашло длинный <a test="<>" href="#"> и короткий <b> теги.

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

Бесконечный возврат

Если запустить пример ниже, то он может подвесить браузер (или другую среду, где выполняется JavaScript):

let reg = /<\w+(\s*\w+="[^"]*"\s*)*>/g;

let str = `<tag a="b"  a="b"  a="b"  a="b"  a="b"  a="b"  a="b"  a="b"
  a="b"  a="b"  a="b"  a="b"  a="b"  a="b"  a="b"  a="b"  a="b" a="b"  a="b"  a="b"  a="b"`;

// Этот поиск будет выполняться очень, очень долго
alert( str.match(reg) );

Некоторые интерпретаторы регулярных выражений могут справится с таким поиском, но большинство из них – нет.

В чём же дело? Почему регулярное выражение «зависает» на такой малой строке?

Давайте упростим регулярное выражение, удалив имя тега и кавычки. Теперь мы ищем только атрибуты – пары key=value: <(\s*\w+=\w+\s*)*>.

К сожалению, регулярное выражение всё ещё «зависает»:

// поиск только по атрибутам, разделённым пробелом
let reg = /<(\s*\w+=\w+\s*)*>/g;

let str = `<a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b
  a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b`;

// поиск займёт много-много времени
alert( str.match(reg) );

На этом мы закончим с демонстрацией практического примера и перейдём к разбору происходящего и способам устранения проблемы.

Подробный пример

Чтобы сделать пример ещё проще, давайте рассмотрим (\d+)*$.

Это регулярное выражение имеет ту же проблему. В большинстве движков регулярных выражений этот поиск занимает очень много времени (осторожно – может «зависнуть»):

alert( '12345678901234567890123456789123456789z'.match(/(\d+)*$/) );

В чём же дело, что не так с регулярным выражением?

Внимательный читатель, посмотрев на него, наверняка удивится, ведь он «какой-то странный». Квантификатор * здесь выглядит лишним. Если хочется найти число, то с тем же успехом можно искать \d+$.

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

Что же происходит во время поиска по паттерну (\d+)*$ в строке 123456789z?

  1. Первым делом, движок регулярных выражений пытается найти \d+. Плюс + является жадным по умолчанию, так что он хватает все цифры, какие может:

    \d+.......
    (123456789)z
  2. Затем движок пытается применить квантификатор *, но больше цифр нет, так что звёздочка ничего не даёт.

  3. Далее по шаблону ожидается конец строки $, а в тексте символ z, так что соответствий нет:

               X
    \d+........$
    (123456789)z
  4. Так как соответствие не найдено, то «жадный» квантификатор + отступает на один символ (возврат).

    Теперь \d+ – это все цифры, за исключением последней:

    \d+.......
    (12345678)9z
  5. Далее движок снова пытается найти совпадение, начиная уже с новой позиции (9).

    Звёздочка (\d+)* теперь может быть применена –- она даёт число 9:

    \d+.......\d+
    (12345678)(9)z

    Движок пытается найти $, но это ему не удаётся – на его пути опять z:

                 X
    \d+.......\d+
    (12345678)(9)z
  6. Так как совпадения нет, то поисковой движок продолжает отступать назад, уменьшая количество повторений для \d+ до 7 цифр, а остаток строки 89 становится вторым \d+:

                 X
    \d+......\d+
    (1234567)(89)z

    …увы, всё ещё нет соответствия для $.

    Поисковый движок снова должен отступить назад. В общем, возврат работает так: последний жадный квантификатор понижает количество повторений до тех пор, пока это возможно. Затем понижает предыдущий «жадный» квантификатор и т.д. В нашем случае последний «жадный» квантификатор – это второй \d+, сокращающий 89 до 8, а звёздочка берёт 9:

                   X
    \d+......\d+\d+
    (1234567)(8)(9)z
  7. …опять неудача. Второй и третий \d+ отступили до конца, так что первый квантификатор сокращает совпадение до 123456, а звёздочка берёт оставшееся:

                 X
    \d+.......\d+
    (123456)(789)z

    И снова нет совпадения. Процесс повторяется: последний «жадный» квантификатор освобождает один символ (9):

                   X
    \d+.....\d+ \d+
    (123456)(78)(9)z
  8. …и так далее.

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

Что же делать?

Может нам стоит использовать «ленивый» режим?

К сожалению, нет: если мы заменим \d+ на \d+?, то регулярное выражение всё ещё будет «зависать» (осторожно! Может «подвесить» браузер):

//  доооолго
alert( '12345678901234567890123456789123456789z'.match(/(\d+?)*$/) );

"Ленивые" регулярные выражения делают то же самое, но в обратном порядке.

Просто подумайте о том, как будет в этом случае работать поисковый движок.

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

Назад к тегам

В примере выше, когда в строке <a=b a=b a=b a=b мы ищем теги по паттерну <(\s*\w+=\w+\s*)*>, происходит то же самое.

В конце строки нет >, поэтому совпадение невозможно, но движок не в курсе этого и, отступая, пробует другие комбинации (\s*\w+=\w+\s*):

(a=b a=b a=b) (a=b)
(a=b a=b) (a=b a=b)
(a=b) (a=b a=b a=b)
...

Как исправить?

Таких комбинаций много, поэтому это и занимает много времени.

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

Например, в выражении (\d+)*$ для человека очевидно, что в (\d+)* не нужно «откатывать» +. От того, что вместо одного\d+ у нас будет два независимых\d+\d+, ничего не изменится:

\d+........
(123456789)z

\d+...\d+....
(1234)(56789)z

Вернёмся к более реальному примеру: <(\s*\w+=\w+\s*)*>. Нам нужно найти пары name=value (все возможные).

Что бы мы хотели сделать, так это исключить бэктрекинг.

Никаких «откатов» здесь не нужно.

Другими словами, если мы нашли три пары name=value, а > после них найти не можем, то не нужно понижать число повторений. Последнего (>) точно нет после предыдущих двух пар name=value (мы «откатились» на одну пару name=value, там находится эта пара):

(name=value) name=value

В современных регулярных выражениях для решения этой проблемы придумали сверхжадные («possessive») квантификаторы, которые вообще не используют возврат. То есть, они даже проще, чем «жадные» – берут максимальное количество символов и всё. Поиск продолжается дальше. Также есть «атомарные скобочные группы» – средство, запрещающее перебор внутри скобок.

К сожалению, в JavaScript они все не поддерживаются.

Предпросмотр в помощь!

Но мы можем исключить бэктрекинг с помощью предпросмотра.

Паттерн, совершающий максимальное количество повторений без возврата, выглядит так: (?=(a+))\1.

Другими словами:

  • Предпросмотр ?= ищет максимальное количество a+, доступных с текущей позиции.
  • А затем они «берутся в результат» обратной ссылкой \1 (\1 соответствует содержимому вторых скобок, т.е. a+)

Возврат в этой логике в принципе не предусмотрен, поскольку предпросмотр «откатываться» не умеет. То есть, если предпросмотр нашёл 5 a+, и в результате поиск не удался, то он не будет откатываться на 4 повторения.

На заметку:

Больше о связи между сверхжадных квантификаторов и предпросмотра вы можете найти в статьях Regex: Emulate Atomic Grouping (and Possessive Quantifiers) with LookAhead и Mimicking Atomic Groups.

Такой метод нивелирует проблему.

Исправим регулярное выражение для поиска тега с атрибутами <\w+(\s*\w+=(\w+|"[^"]*")\s*)*>, описанное в начале главы. Используем предпросмотр, чтобы запретить откат на меньшее количество пар name=value:

// регулярное выражение для поиска 'name=value'
let attrReg = /(\s*\w+=(\w+|"[^"]*")\s*)/

// используем new RegExp() чтобы красиво вставить его исходную строку (source) в (?=(a+))\1
let fixedReg = new RegExp(`<\\w+(?=(${attrReg.source}*))\\1>`, 'g');

let goodInput = '...<a test="<>" href="#">... <b>...';

let badInput = `<tag a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b
  a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b  a=b`;

alert( goodInput.match(fixedReg) ); // <a test="<>" href="#">, <b>
alert( badInput.match(fixedReg) ); // null (нет результатов, отработало быстро!)

Отлично, всё работает! Нашло как длинный тег <a test="<>" href="#">, так и одинокий <b>, и (!) не «вешает» интерпретатор при некорректных данных.

Обратите внимание на свойство attrReg.source. Объект RegExp предоставляет доступ к своей исходной (source) строке. Это удобно, когда мы хотим вставить одно регулярное выражение в другое.

Карта учебника

Комментарии

перед тем как писать…
  • Если вам кажется, что в статье что-то не так - вместо комментария напишите на GitHub.
  • Для одной строки кода используйте тег <code>, для нескольких строк кода — тег <pre>, если больше 10 строк — ссылку на песочницу (plnkr, JSBin, codepen…)
  • Если что-то непонятно в статье — пишите, что именно и с какого места.