Давно ничего не писал, поэтому разбавим конец пятницы простыми, но не всегда очевидными иcканиями в Nginx.

В этом веб-сервере есть замечательная директива map, которая позволяет существенно упростить и сократить конфиги. Суть директивы в том, что она позволяет создать новую переменную, значение которой зависит от значений одной или нескольких исходных переменных. Ещё большую силу директива приобретает при использовании регулярных выражений, но при этом забывается, об одном важном моменте. Выдержка из мануала:

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

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

Как известно, конфиг Nginx, в основном, декларативен. Это касается и директивы map, и, не смотря на то, что она расположена в контексте http, её вычисление не происходит до момента обработки запроса. То есть при использовании результирующей переменной в контекстах server, location, if и т.п. мы "подставляем" не готовый результат вычисления, а лишь "формулу" по который этот результат будет вычислен в нужный момент. В этой конфигурационной казуистике не возникает проблем до того момента, пока мы не используем регулярные выражения. А именно регулярные выражения с выделениями. А ещё точнее, регулярные выражения с неименованными выделениями. Проще показать на примере.

Допустим у нас есть домен example.com с множеством поддоменов 3-го уровня, а-ля ru.example.com, en.example.com, de.example.com и т.д., и мы хотим их перенаправить на новые поддомены ru.example.org, en.example.org, de.example.org и т.п. Вместо того чтобы описывать сотни строк редиректов мы поступим вот так:

map $host $redirect_host {  default "example.org";  "~^(\S+)\.example\.com$"  $1.example.org;}server {    listen       *:80;    server_name  .example.com;  location / {        rewrite ^(.*)$ https://$redirect_host$1 permanent;    }

Здесь мы ошибочно ожидали, что при запросе ru.example.com произойдет вычисление регулярки в map и, соответственно, попав в location переменная $redirect_host будет содержать значение ru.example.org, однако на деле это не так:

$ GET -Sd ru.example.comGET http://ru.example.com301 Moved PermanentlyGET https://ru.example.orgru

Оказалось, что на момент исполнения запроса наша переменная равна ru.example.orgru. Всё из-за того, что мы пренебрегли предупреждением "переменные вычисляются только в момент использования", а в нашем rewrite оказалась некая регулярка вложенная в регулярку.

Самый простой вариант решения - не использовать regexp одновременно и в map и в месте вычисления переменной, например, для данного конкретного случая это может выглядеть так:

map $host $redirect_host {  default "example.org";  "~^(\S+)\.example\.com$"  $1.example.org;}server {    listen       *:80;    server_name  .example.com;    location / {        return 301 https://$redirect_host$request_uri;    }}

Но что делать, если альтернативного решения без регулярок нет (ну или просто очень хочется).
Пробуем использовать именованные выделения в map:

map $host $redirect_host {  default "example.org";  "~^(?<domainlevel3>\S+)\.example\.com$"  $domainlevel3.example.org;}server {    listen       *:80;    server_name  .example.com;    location / {        rewrite ^(.*)$ https://$redirect_host$1 permanent;    }}

Попытка не увенчалась успехом:

$ GET -Sd ru.example.comGET http://ru.example.com301 Moved PermanentlyGET https://ru.example.orgru

так как наше неименованное выделение $1 получит результат именованного $domainlevel3. То есть необходимо использовать именованные выделения в обеих регулярках:

map $host $redirect_host {  default "example.org";  "~^(?<domainlevel3>\S+)\.example\.com$"  $domainlevel3.example.org;}server {    listen       *:80;    server_name  .example.com;    location / {        rewrite ^(?<requri>.*)$ https://$redirect_host$requri permanent;    }}

И теперь всё работает как ожидалось:

$ GET -Sd ru.example.comGET http://ru.example.com301 Moved PermanentlyGET https://ru.example.org/

Регулярные выражения (их еще называют regexp, или regex) это механизм для поиска и замены текста. В строке, файле, нескольких файлах... Их используют разработчики в коде приложения, тестировщики в автотестах, да просто при работе в командной строке!

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

Например, на вход приходит дата рождения в формате ДД.ММ.ГГГГГ. Вам надо передать ее дальше, но уже в формате ГГГГ-ММ-ДД. Как это сделать с помощью простого поиска? Вы же не знаете заранее, какая именно дата будет.

А регулярное выражение позволяет задать шаблон найди мне цифры в таком-то формате.

Для чего применяют регулярные выражения?

1. Удалить все файлы, начинающиеся на test (чистим за собой тестовые данные)

2. Найти все логи

3. grep-нуть логи

4. Найти все даты

5. ...

А еще для замены например, чтобы изменить формат всех дат в файле. Если дата одна, можно изменить вручную. А если их 200, проще написать регулярку и подменить автоматически. Тем более что регулярные выражения поддерживаются даже простым блокнотом (в Notepad++ они точно есть).

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

Содержание

1. Где пощупать

2. Поиск текста

3. Поиск любого символа

4. Поиск по набору символов

5. Перечисление вариантов

6. Метасимволы

7. Спецсимволы

8. Квантификаторы (количество повторений)

9. Позиция внутри строки

10. Использование ссылки назад

11. Просмотр вперед и назад

12. Замена

13. Статьи и книги по теме

14. Итого

1. Поиск текста

2. Поиск любого символа

3. Поиск по набору символов

4. Перечисление вариантов

5. Метасимволы

6. Спецсимволы

7. Квантификаторы (количество повторений)

8. Замена

9. Итого

Где пощупать

Любое регулярное выражение из статьи вы можете сразу пощупать. Так будет понятнее, о чем речь в статье вставили пример из статьи, потом поигрались сами, делая шаг влево, шаг вправо. Где тренироваться:

1. Notepad++ (установить Search Mode Regular expression)

2. Regex101 (мой фаворит в онлайн вариантах)

3. Myregexp

4. Regexr

Инструменты есть, теперь начнём

Поиск текста

Самый простой вариант регэкспа. Работает как простой поиск ищет точно такую же строку, как вы ввели.

Текст: Море, море, океан

Regex: море

Найдет: Море, море, океан

Выделение курсивом не поможет моментально ухватить суть, что именно нашел regex, а выделить цветом в статье я не могу. Атрибут BACKGROUND-COLOR не сработал, поэтому я буду дублировать регулярки текстом (чтобы можно было скопировать себе) и рисунком, чтобы показать, что именно regex нашел:

Обратите внимание, нашлось именно море, а не первое Море. Регулярные выражения регистрозависимые!

Хотя, конечно, есть варианты. В JavaScript можно указать дополнительный флажок i, чтобы не учитывать регистр при поиске. В блокноте (notepad++) тоже есть галка Match case. Но учтите, что это не функция по умолчанию. И всегда стоит проверить, регистрозависимая ваша реализация поиска, или нет.

А что будет, если у нас несколько вхождений искомого слова?

Текст: Море, море, море, океан

Regex: море

Найдет: Море, море, море, океан

По умолчанию большинство механизмов обработки регэкспа вернет только первое вхождение. В JavaScript есть флаг g (global), с ним можно получить массив, содержащий все вхождения.

А что, если у нас искомое слово не само по себе, это часть слова? Регулярное выражение найдет его:

Текст: Море, 55мореон, океан

Regex: море

Найдет: Море, 55мореон, океан

Это поведение по умолчанию. Для поиска это даже хорошо. Вот, допустим, я помню, что недавно в чате коллега рассказывала какую-то историю про интересный баг в игре. Что-то там связанное с кораблем... Но что именно? Уже не помню. Как найти?

Если поиск работает только по точному совпадению, мне придется перебирать все падежи для слова корабль. А если он работает по включению, я просто не буду писать окончание, и все равно найду нужный текст:

Regex: корабл

Найдет:

На корабле

И тут корабль

У корабля

Это статический, заранее заданный текст. Но его можно найти и без регулярок. Регулярные выражения особенно хороши, когда мы не знаем точно, что мы ищем. Мы знаем часть слова, или шаблон.

Поиск любого символа

. найдет любой символ (один).

Текст:

Аня

Ася

Оля

Аля

Валя

Regex: А.я

Результат:

Аня

Ася

Оля

Аля

Валя

Точка найдет вообще любой символ, включая цифры, спецсисимволы, даже пробелы. Так что кроме нормальных имен, мы найдем и такие значения:

А6я

А&я

А я

Учтите это при поиске! Точка очень удобный символ, но в то же время очень опасный если используете ее, обязательно тестируйте получившееся регулярное выражение. Найдет ли оно то, что нужно? А лишнее не найдет?

Точку точка тоже найдет!

Regex: file.

Найдет:

file.txt

file1.txt

file2.xls

Но что, если нам надо найти именно точку? Скажем, мы хотим найти все файлы с расширением txt и пишем такой шаблон:

Regex: .txt

Результат:

file.txt

log.txt

file.png

1txt.doc

one_txt.jpg

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

Но если мы хотим найти именно точку, то нужно ее заэкранировать то есть добавить перед ней обратный слеш:

Regex: \.txt

Результат:

file.txt

log.txt

file.png

1txt.doc

one_txt.jpg

Также мы будем поступать со всеми спецсимволами. Хотим найти именно такой символ в тексте? Добавляем перед ним обратный слеш.

Правило поиска для точки:

. любой символ

\. точка

Поиск по набору символов

Допустим, мы хотим найти имена Алла, Анна в списке. Можно попробовать поиск через точку, но кроме нормальных имен, вернется всякая фигня:

Regex: А..а

Результат:

Анна

Алла

аоикА74арплт

Аркан

А^&а

Абба

Если же мы хотим именно Анну да Аллу, вместо точки нужно использовать диапазон допустимых значений. Ставим квадратные скобки, а внутри них перечисляем нужные символы:

Regex: А[нл][нл]а

Результат:

Анна

Алла

аоикА74арплт

Аркан

А^&а

Абба

Вот теперь результат уже лучше! Да, нам все еще может вернуться Анла, но такие ошибки исправим чуть позже.

Как работают квадратные скобки? Внутри них мы указываем набор допустимых символов. Это может быть перечисление нужных букв, или указание диапазона:

[нл] только н и л

[а-я] все русские буквы в нижнем регистре от а до я (кроме ё)

[А-Я] все заглавные русские буквы

[А-Яа-яЁё] все русские буквы

[a-z] латиница мелким шрифтом

[a-zA-Z] все английские буквы

[0-9] любая цифра

[В-Ю] буквы от В до Ю (да, диапазон это не только от А до Я)

[А-ГО-Р] буквы от А до Г и от О до Р

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

[абв] только а, б или в

[а б в] а, б, в, или пробел (что может привести к нежелательному результату)

[а, б, в] а, б, в, пробел или запятая

Единственный допустимый разделитель это дефис. Если система видит дефис внутри квадратных скобок значит, это диапазон:

• Символ до дефиса начало диапазона

• Символ после конец

Один символ! Не два или десять, а один! Учтете это, если захотите написать что-то типа [1-31]. Нет, это не диапазон от 1 до 31, эта запись читается так:

• Диапазон от 1 до 3

• И число 1

Здесь отсутствие разделителей играет злую шутку с нашим сознанием. Ведь кажется, что мы написали диапазон от 1 до 31! Но нет. Поэтому, если вы пишете регулярные выражения, очень важно их тестировать. Не зря же мы тестировщики! Проверьте то, что написали! Особенно, если с помощью регулярного выражения вы пытаетесь что-то удалить =)) Как бы не удалили лишнее...

Указание диапазона вместо точки помогает отсеять заведомо плохие данные:

Regex: А.я или А[а-я]я

Результат для обоих:

Аня

Ася

Оля

Аля

Результат для А.я:

А6я

А&я

А я

^ внутри [] означает исключение:

[^0-9] любой символ, кроме цифр

[^ёЁ] любой символ, кроме буквы ё

[^а-в8] любой символ, кроме букв а, б, в и цифры 8

Например, мы хотим найти все txt файлы, кроме разбитых на кусочки заканчивающихся на цифру:

Regex: [^0-9]\.txt

Результат:

file.txt

log.txt

file_1.txt

1.txt

Так как квадратные скобки являются спецсимволами, то их нельзя найти в тексте без экранирования:

Regex: fruits[0]

Найдет: fruits0

Не найдет: fruits[0]

Это регулярное выражение говорит найди мне текст fruits, а потом число 0. Квадратные скобки не экранированы значит, внутри будет набор допустимых символов.

Если мы хотим найти именно 0-левой элемент массива фруктов, надо записать так:

Regex: fruits\[0\]

Найдет: fruits[0]

Не найдет: fruits0

А если мы хотим найти все элементы массива фруктов, мы внутри экранированных квадратных скобок ставим неэкранированные!

Regex: fruits\[[0-9]\]

Найдет:

fruits[0] = апельсин;

fruits[1] = яблоко;

fruits[2] = лимон;

Не найдет:

cat[0] = чеширский кот;

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

Без паники! Если вы видите сложное регулярное выражение, то просто разберите его по частям. Помните про основу эффективного тайм-менеджмента? Слона надо есть по частям.

Допустим, после отпуска накопилась гора писем. Смотришь на нее и сразу впадаешь в уныние:

Ууууууу, я это за день не закончу!

Проблема в том, что груз задачи мешает работать. Мы ведь понимаем, что это надолго. А большую задачу делать не хочется... Поэтому мы ее откладываем, беремся за задачи поменьше. В итоге да, день прошел, а мы не успели закончить.

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

Разберем по частям регулярное выражение fruits\[[0-9]\]

Сначала идет просто текст fruits.

Потом обратный слеш. Ага, он что-то экранирует.

Что именно? Квадратную скобку. Значит, это просто квадратная скобка в моем тексте fruits[

Дальше снова квадратная скобка. Она не экранирована значит, это набор допустимых значений. Ищем закрывающую квадратную скобку.

Нашли. Наш набор: [0-9]. То есть любое число. Но одно. Там не может быть 10, 11 или 325, потому что квадратные скобки без квантификатора (о них мы поговорим чуть позже) заменяют ровно один символ.

Пока получается: fruits[любое однозназначное число

Дальше снова обратный слеш. То есть следующий за ним спецсимвол будет просто символом в моем тексте.

А следующий символ ]

Получается выражение: fruits[любое однозназначное число]

Наше выражение найдет значения массива фруктов! Не только нулевое, но и первое, и пятое... Вплоть до девятого:

Regex: fruits\[[0-9]\]

Найдет:

fruits[0] = апельсин;

fruits[1] = яблоко;

fruits[9] = лимон;

Не найдет:

fruits[10] = банан;

fruits[325] = абрикос ;

Как найти вообще все значения массива, см дальше, в разделе квантификаторы.

А пока давайте посмотрим, как с помощью диапазонов можно найти все даты.

Какой у даты шаблон? Мы рассмотрим ДД.ММ.ГГГГ:

• 2 цифры дня

• точка

• 2 цифры месяца

• точка

• 4 цифры года

Запишем в виде регулярного выражения: [0-9][0-9]\.[0-9][0-9]\.[0-9][0-9][0-9][0-9].

Напомню, что мы не можем записать диапазон [1-31]. Потому что это будет значить не диапазон от 1 до 31, а диапазон от 1 до 3, плюс число 1. Поэтому пишем шаблон для каждой цифры отдельно.

В принципе, такое выражение найдет нам даты среди другого текста. Но что, если с помощью регулярки мы проверяем введенную пользователем дату? Подойдет ли такой regexp?

Давайте его протестируем! Как насчет 8888 года или 99 месяца, а?

Regex: [0-9][0-9]\.[0-9][0-9]\.[0-9][0-9][0-9][0-9]

Найдет:

01.01.1999

05.08.2015

Тоже найдет:

08.08.8888

99.99.2000

Попробуем ограничить:

• День недели может быть максимум 31 первая цифра [0-3]

• Максимальный месяц 12 первая цифра [01]

• Год или 19.., или 20.. первая цифра [12], а вторая [09]

Вот, уже лучше, явно плохие данные регулярка отсекла. Надо признать, она отсечет довольно много тестовых данных, ведь обычно, когда хотят именно сломать, то фигачат именно 9999 год или 99 месяц...

Однако если мы присмотримся внимательнее к регулярному выражению, то сможем найти в нем дыры:

Regex: [0-3][0-9]\.[0-1][0-9]\.[12][09][0-9][0-9]

Не найдет:

08.08.8888

99.99.2000

Но найдет:

33.01.2000

01.19.1999

05.06.2999

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

Перечисление вариантов

Квадртатные скобки [] помогают перечислить варианты для одного символа. Если же мы хотим перечислить слова, то лучше использовать вертикальную черту |.

Regex: Оля|Олечка|Котик

Найдет:

Оля

Олечка

Котик

Не найдет:

Оленька

Котенка

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

Regex: А(н|л)я

Найдет:

Аня

Аля

Круглые скобки обозначают группу символов. В этой группе у нас или буква н, или буква л. Зачем нужны скобки? Показать, где начинается и заканчивается группа. Иначе вертикальная черта применится ко всем символам мы будем искать или Ан, или ля:

Regex: Ан|ля

Найдет:

Аня

Аля

Оля

Малюля

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

Эти 2 варианта вернут одно и то же:

• А(н|л)я

• А[нл]я

Но для замены одной буквы лучше использовать [], так как сравнение с символьным классом выполняется проще, чем обработка группы с проверкой на все её возможные модификаторы.

Давайте вернемся к задаче проверить введенную пользователем дату с помощью регулярных выражений. Мы пробовали записать для дня диапазон [0-3][0-9], но он пропускает значения 33, 35, 39... Это нехорошо!

Тогда распишем ТЗ подробнее. Та-а-а-ак... Если первая цифра:

• 0 вторая может от 1 до 9 (даты 00 быть не может)

• 1, 2 вторая может от 0 до 9

• 3 вторая только 0 или 1

Составим регулярные выражения на каждый пункт:

• 0[1-9]

• [12][0-9]

• 3[01]

А теперь осталось их соединить в одно выражение! Получаем: 0[1-9]|[12][0-9]|3[01]

По аналогии разбираем месяц и год. Но это остается вам для домашнего задания

Раннее утро, десятая чашка кофе, безуспешные попытки понять почему ваше клиентское (или еще хуже серверное) java-приложение намертво зависло при вычислении простого регекспа на небольшой строке Если подобная ситуация уже возникала в вашей жизни, вы уже наверняка знаете про бэктрекинг и темную сторону регулярных выражений. Остальным добро пожаловать под кат!

Бэктрекинг, или вечное ожидание результата

Проблема бэктрекинга при матчинге регулярных выражений уже неоднократно поднималась в различных статьях на хабре (раз, два, три), поэтому опишем ее суть без погружения в детали. Рассмотрим простой синтетический пример типичный экземпляр из так называемых "evil regexes" (аналог изначально представлен тут):

@Testpublic void testRegexJDK8Only() {  final Pattern pattern = Pattern.compile("(0*)*1");  Assert.assertFalse(pattern.matcher("0000000000000000000000000000000000000000").matches());}

Напомню: символ * в регулярных выражениях ("ноль или несколько символов") называется квантификатором. Им же являются такие символы, как ?, +, {n} (n количество повторений группы или символа).

Если запустить код на JDK8 (почему на более актуальных версиях воспроизводиться не будет опишем далее), то JVM будет очень долго вычислять результат работы метода matches(). Едва ли вам удастся его дождаться, не состарившись на несколько месяцев или даже лет.

Что же пошло не так? Стандартная реализация Pattern/Matcher из пакета java.util.regex будет искать решение из теста следующим образом:

1. * - жадный квантификатор, поскольку всегда будет пытаться захватить в себе как можно большее количество символов. Так, в нашем случае группа (0)захватит полностью всю строку, звезда снаружи группы увидит, что может повториться ровно один раз, а единицы в строке не окажется. Первая проверка на соответствие провалилась.

2. Произведем откат (backtrack) к начальному состоянию. Мы попытались захватить максимальную группу из нулей и нас ждал провал; давайте теперь возьмём на один нолик меньше. Тогда группа (0) захватит все нули без одного, снаружи группы укажет на наличие единственной группы, а оставшийся ноль не равен единице. Снова провал.

3. Снова откатываемся к начальному состоянию и забираем группой (0) все нули без двух последних. Но ведь оставшиеся два нуля тоже могут заматчиться группой (0)! И теперь эта группа тоже попытается сначала захватить два нуля, после чего попытается взять один ноль, и после этого произойдет откат и попытка матчинга строки уже без трех нулей.

Легко догадаться, что по мере уменьшения "начальной" жадной группы будет появляться множество вариаций соседних групп (0), которые также придется откатывать и проверять все большее количество комбинаций. Сложность будет расти экспоненциально; при наличии достаточного количества нулей в строке прямо как в нашем примере возникнет так называемый катастрофический бэктрекинг, который и приведет к печальным последствиям.

"Но ведь пример абсолютно синтетический! А в жизни так бывает?" - резонно спросите вы. Ответ вполне ожидаем: бывает, и очень часто. Например, для решения бизнес-задачи программисту необходимо составить регулярку, проверяющую, что в строке есть не более 10 слов, разделенных пробелами и знаками препинания. Не заморачиваясь с аккуратным созданием регекспа, на свет может появиться следующий код:

@Testpublic void testRegexAnyJDK() {final Pattern pattern = Pattern.compile("([A-Za-z,.!?]+( |\\-|\\')?){1,10}");  Assert.assertFalse(pattern.matcher("scUojcUOWpBImlSBLxoCTfWxGPvaNhczGpvxsiqagxdHPNTTeqkoOeL3FlxKROMrMzJDf7rvgvSc72kQ").matches());}

Представленная тестовая строка имеет длину 80 символов и сгенерирована случайным образом. Она не заставит JVM на JDK8+ работать вечно всего лишь около 30 минут но этого уже достаточно, чтобы нанести вашему приложению существенный вред. В случае разработки серверных приложений риск многократно увеличивается из-за возможности проведения ReDoS-атак. Причиной же подобного поведения, как и в первом примере, является бэктрекинг, а именно сочетание квантификаторов "+" внутри группы и "{1,10}" снаружи.

Война с бэктрекингом или с разработчиками Java SDK?

Чем запутаннее паттерн, тем сложнее для неопытного человека увидеть проблемы в регулярном выражении. Причем речь сейчас идет вовсе не о внешних пользователях, использующих ваше ПО, а о разработчиках. Так, с конца нулевых было создано значительное количество тикетов с жалобой на бесконечно работающий матчинг. Несколько примеров: JDK-5026912, JDK-7006761, JDK-8139263. Реже можно встретить жалобы на StackOverflowError, который тоже типичен при проведении матчинга (JDK-5050507). Все подобные баги закрывались с одними и теми же формулировками: "неэффективный регексп", "катастрофический бектрекинг", "не является багом".

Альтернативным предложением сообщества в ответ на невозможность "починить" алгоритм было внедрение таймаута при применении регулярного выражения или другого способа остановить матчинг, если тот выполняется слишком долго. Подобный подход можно относительно легко реализовать самостоятельно (например, часто его можно встретить на сервисах для проверки регулярных выражений - таких как этот), но предложение реализации таймаута в API java.util.regex также неоднократно выдвигалось и к разработчикам JDK (тикеты JDK-8234713, JDK-8054028, JDK-7178072). Первый тикет все еще не имеет исполнителя; два остальных были закрыты, поскольку "правильным решением будет улучшить реализацию, которая лучше справляется с кейсами, в которых наблюдается деградация" (пруф).

Доработки алгоритма действительно происходили. Так, в JDK9 реализовано следующее улучшение: каждый раз, когда применяется жадный квантификатор, не соответствующий данным для проверки, выставляется курсор, указывающий на позицию в проверяемом выражении. При повторной проверке после отката достаточно убедиться, что если для текущей позиции проверка уже была провалена, продолжение текущего подхода лишено смысла и проводиться не будет (JDK-6328855, пояснение). Это позволило исключить бесконечный матчинг в тесте testRegexJDK8Only() начиная с версии jdk9-b119, однако второй тест вызывает задержки вне зависимости от версии JDK. Более того, при наличии обратных ссылок в регулярных выражениях оптимизация не используется.

Опасный враг: внешнее управление

Публикации, упомянутые в самом начале статьи, отлично раскрывают варианты оптимизации регулярных выражений, в результате чего катастрофический бектрекинг перестает быть опасным врагом; для сложных случаев потребуется дополнительная экспертиза, но в целом регулярное выражение можно почти всегда записать "безопасным" образом. Да и проверить себя тоже можно, например, на npmjs.com. Проблема остается при составлении очень сложных регулярок, а также в тех сценариях, когда регулярное выражение задается не программистом, а аналитиком, заказчиком после передачи решения, или же пользователем. В последнем случае управление сложностью регулярного выражения оказывается снаружи и вам придется позаботиться о том, чтобы при любых условиях приложение продолжало корректную работу.

Использование стандартной библиотеки в таком случае, очевидно, не лучший выбор. К счастью, существуют сторонние фреймворки, позволяющие производить матчинг за линейное время. Одним из таких фреймворков является RE2, под капотом которого используется DFA - подход. Не будем вдаваться в детали реализации и подробно описывать разницу подходов; отметим лишь его растущую популярность RE2 используется как дефолтный движок в Rust, а также активно применяется во множестве продуктов экосистемы Google. Для JDK7+ существует RE2/J, которая является прямым портом из C++ - версии библиотеки.

В конце января 2021 года был опубликован драфт JEP-а, в котором предлагается создать движок для регулярных выражений с матчингом за линейное время, и одним из основных подходов в реализации является именно RE2.

RE2/J - серебряная пуля?

Может показаться, что переход на RE2/J отличный выбор практически для каждого проекта. Какова цена линейного времени выполнения?

• У RE2/J отсутствует ряд методов API у Matcher;

• Синтаксис регулярных выражений совпадает не полностью (у RE2/J отствутет часть конструкций, в том числе обратные ссылки, backreferences). Вполне вероятно, после замены импорта ваша регулярка перестанет корректно распознаваться;

• Несмотря на то, что формально код принадлежит Google, библиотека не является официальной, а основным ее мейнтейнером является единственный разработчик Джеймс Ринг.

• Разработчик фреймворка подчеркивает: "Основная задача RE2/J заключается в обеспечении линейного времени выполнения матчинга при наличии регулярных выражений от внешних источников. Если все регулярные выражения находятся под контролем разработчика, вероятно, использование java.util.regex является лучшим выбором".

Надеюсь, этих пунктов достаточно, чтобы убедиться: RE2/J не серебряная пуля; фреймворк не является бескомпромиссным решением для проверки на соответствие регулярным выражениям. Реализация при создании кода повлечет ограниченный функционал, а прямая замена импорта в уже существующем коде может негативно сказаться на стабильности работы приложения.

Итоги

1. Даже простые регулярные выражения при невнимательном написании могут сделать ваш продукт уязвимым для ReDoS.

2. Движков регулярных выражений, которые были бы одновременно максимально функциональны, быстры и стабильны, не существует.

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

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