Re2j вместо стандартного regEx в Java: в каких случаях и как использовать

Всем привет! Я Даниил, 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.