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 милисекунд
