Всем привет! Я Даниил, java разработчик в Just AI, и в этой статье я расскажу, как мы столкнулись с проблемой backtracking’а в регулярных выражениях и как ее решили с помощью библиотеки re2j.

Вот что будет в статье:

• каким образом проблема бэктрекинга в регулярных выражениях настигла и нас

• как мы с ней боролись, используя бибилотеку re2j

• какие сложности и неочевидные нюансы работы с re2j вас могут ожидать

Что такое этот ваш бэктрекинг?

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

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

По теме рассказано и написано много, но уверен, что я не последний, кто поднимает ее.

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

Как мы столкнулись с этой проблемой

Мы делаем JAICP - платформа, позволяющая создавать чат-ботов и удобно работать с информацией, проходящей через них. Через ботов могут проходить чувствительные данные, поэтому мы тщательно следим, что они не попали не в те руки. Для этого мы маскируем / обфусцируем информацию.

Для наглядности результат обфускации выглядит примерно следующим образом:

Ключевым моментом является то, что клиенты могут самостоятельно задавать регулярные выражения. Тем самым указывая, какие данные являются чувствительными и на что нужно эти данные заменить.

Ловим проблему

Теперь мы знаем, что у нас за задача. Для решения мы будем использовать всем привычные регулярные выражения в Java, но вот подойдут ли они нам под все условия в стандартном виде?

Давайте посмотрим на один достаточно безобидный пример, который у нас является базовым сценарием использования. А именно сокрытие email адреса в сообщениях пользователей:

Т.е. мы заменяем найденные email адреса на xxxx@xxxx.xx, все просто. Используем для поиска email’ов следующее регулярное выражение:

[a-z0-9!#$%&'*+/=?^_{|}~-]+(?:\\.[a-z0-9!#$%&'*+/=?^_{|}~-]+)*@(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\\\\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?

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

Посмотрим, сколько будет выполняться следующий код, использующий стандартный java движок:

String inputText = TestUtils.getRandomLongWord("test@test.com");
Matcher matcher = Pattern.compile(TestUtils.emailRegex).matcher(inputText);
matcher.replaceAll("XXX@XXX.XX");

В данном и последующих примерах мы будем генерировать рандомный длинный текст, встраивая туда искомый фрагмент. В примере выше это вымышленный email адрес. ...+UUID.randomUUID()+"test@test.com"+UUID.randomUUID() Вызов randomUUID делаем в нашем примере 500 раз, а искомый текст вставляем после каждого 10ого вызова. Замеры времени производились на i7-10510U CPU 1.80GHz × 8 и jdk 1.8

Время выполнения-36 милисекунд

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

Все то же самое, но UUID.random()+UUID.random()

String inputText = TestUtils.getRandomLongWord("test@test.com");
Matcher matcher = Pattern.compile(TestUtils.emailRegex).matcher(inputText);
matcher.replaceAll("XXX");

Время выполнения-8879 милисекунд

???? кажется, мы поймали проблему backtracking’а.

Решение проблемы с email

Для решения возникшей проблемы мы воспользуемся библиотекой Re2j.

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

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

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

Неужели Re2j действительно поможет нам избежать наших 9 секунд? Давайте посмотрим! Для проверки нам достаточно лишь заменить стандартный Pattern на com.google.re2j.Pattern

com.google.re2j.Pattern.compile(emailRegex)
		.matcher(TestUtils.getRandomLongWord(""))
		.replaceAll("XXX")

Теперь наше время выполнения примерно 88 милисекунд????????????

Выглядит круто!

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

Что там по производительности?

Для этих целей мы будем использовать JMH benchmark - популярный инструмент для замера времени выполнения java кода.

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

@Benchmark
@BenchmarkMode(Mode.AverageTime)
@Fork(value = 1)
@Warmup(iterations = 2)
@Measurement(iterations = 5)
public void standartRegexWithEmailDataBenchmark(MyState myState, Blackhole blackhole) {
    myState.standartEmailRegex
        .matcher(myState.emailInputTextWords)
        .replaceAll("XXX");
}

Где standartEmailRegex это java.util.regex.Pattern.compile(TestUtils.emailRegex)

Среднее время работы replaceAll для паттерна с email:

• Стандартный java pattern - 0.004 секунды

• Re2j pattern - 0.002 секунды

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

Как насчет кейса с большим словарем?

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

Посмотрим на примере словаря американских городов: Бостон, Чикаго, Вашингтон... Он в свою очередь превращается в регулярное выражение: Бостон|Чикаго|Вашингтон...

Мы используем другие данные, не города, но для примера я достал все города США с сайта вот таким страшным или не очень js выражением: Array.from(document.getElementsByClassName("topic-content pt-sm-15")[0].getElementsByTagName("section")).slice(1).flatMap(x => Array.from(x.children[1].children)).map(x => x.outerText) Итого получился словарь размером 1950 элементов, меньше, чем у нас в словаре, но все же выглядит внушительно.

Получается у нас есть классический java.util.regex Pattern

java.util.regex.Pattern.compile(String.join("|", TestUtils.usCitiesAndTowns))

И com.google.re2j Pattern

com.google.re2j.Pattern.compile(String.join("|", TestUtils.usCitiesAndTowns));

Во всех наших примерах паттерны выглядят полностью одинаково, но re2j не полноценно заменяет интерфейс стандартных регулярных выражений в java, поэтому нужно проверять github библиотеки.

Здесь мы также воспользуемся JMH для замера времени выполнения.

Среднее время работы replaceAll для паттерна с городами:

• Стандартный java pattern - 0.147 секунды

• Re2j pattern - 0.625 секунды

Они говорят нам о том, что вариант с Re2j в 4 с лишним раза медленнее, чем стандартный java regex????

А что там с размером паттерна?

Еще одним неочевидным показателем, который стоит проверить, является размер нашего скомпилированного патерна.

Когда мы пишем, например, Pattern.compile("\\\\d{2}"), то даже не задумываемся, что размер такого объекта может быть проблемой.

А может ли?

Для замера мы будем использовать ObjectSizeCalculator.getObjectSize из пакета nashorn, который уже не доступен в версиях JDK новее, чем 8, но в JDK 8 его вполне можно использовать.

А замерять мы будем вот такую конструкцию:

Pattern.compile(String.join("|", TestUtils.usCitiesAndTowns)

где TestUtils.usCitiesAndTowns - это огромный словарь из примера выше

Итого финальный вызов выглядит следующим образом: ObjectSizeCalculator.getObjectSize(Pattern.compile(String.join("|", TestUtils.usCitiesAndTowns)))

• com.google.re2j.Pattern - 1026872 bytes (~1mb)

• java.util.regex.Pattern - 197608 bytes (~0.2mb)

Получил разницу в 5 раз!!! ????

Паттерн на re2j занимает места в 5 раз больше, чем стандартный.

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

Заключение

Мы рассмотрели возможности библиотеки re2j с разных сторон и подсветили важные и порой неочевидные ее недостатки.

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

Подводя итог:

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

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

• Производительность решения может показывать противоположные результаты

• Скомпилированный Pattern будет занимать в разы больше места, и это может стать проблемой.

• Re2j не поддерживает весь синтаксис регулярных выражений, который поддерживает стандартная java реализация.

P.S. Весь код доступен на github.