Регулярные выражения являются неотъемлемой частью разработки программного обеспечения, обеспечивая мощные средства для обработки и анализа текстовых данных. Rust, как современный системный язык с акцентом на безопасность и производительность, имеет официальный пакет regex, который позволяет эффективно и быстро работать с регулярными выражениями. Однако долгое время движок Rust не поддерживал важную особенность — lookbehind-утверждения. В 2025 году появилась реализация этой функциональности, которая существенно расширила возможности работы с регулярными выражениями в Rust. Она привнесла поддержку непредсказуемо длинных captureless lookbehinds — обратных утверждений без групп захвата.
Lookbehind — это специальная конструкция в регулярных выражениях, которая позволяет проверить наличие (или наоборот отсутствие) определённого шаблона непосредственно перед текущей позицией, не включая этот шаблон в сам итог поиска. Такие выражения бывают позитивными и негативными, в зависимости от того, проверяют ли они присутствие или отсутствие совпадения. Важным моментом стало то, что поддержка lookbehind в Rust теперь не ограничена фиксированной или ограниченной длиной, в отличие от популярных движков как PCRE или Python re. Примером служит шаблон (?<=Title:\s+)\w+, который ищет последовательность буквенных символов, идущих после слова "Title:" с пробелом. Такой паттерн успешно различает строки типа "Title: HelloWorld" и "Title: foo", но пропускает строки без корректного префикса или с неправильным форматированием.
Именно гибкость в длине lookbehind является значительным шагом вперёд по сравнению с ограничениями многих других движков. Под капотом реализация реализована в нескольких ключевых компонентах экосистемы Rust. Сам crate regex представляет собой обёртку вокруг regex-automata — библиотеки, предоставляющей различные алгоритмы и реализации конечных автоматов для поиска по регулярным выражениям. Для синтаксического анализа служит отдельный crate regex-syntax, который разбирает строку регулярного выражения, строит AST, а затем трансформирует его в высокоуровневое представление (HIR). Именно на этапе построения HIR происходит обработка и проверка поддерживаемых функций, включая lookbehind, а также определение важных метаданных, таких как минимальная и максимальная длина возможных совпадений.
Само внедрение lookbehind в движок PikeVM, базирующийся на симуляции расширенного НКА, включало добавление новых типов состояний — WriteLookAround и CheckLookAround. Первое служит для фиксации совпадений внутри lookbehind, второе — для проверки их наличия в основном ходе выполнения. Такое разделение позволяет обеспечить универсальность, теоретически расширяя возможности и на lookahead-утверждения. Важной технической деталью стало то, что на начальном этапе все sub-автоматы, представляющие собой основные части регулярного выражения и вложенные lookbehind-выражения, объединялись в один большой НКА с приоритетным порядком обработки. Это обеспечивало корректный порядок проверки вложенных lookbehind.
Однако на практике такое объединение приводило к значительному снижению производительности, поскольку поток с приоритетом lookbehind всегда имел более высокий приоритет и заставлял механизм сканировать всю входную строку до конца без преждевременного возврата результата. Такой подход приводил к непредсказуемому и неприемлемому росту времени работы, особенно при поиске всех совпадений (match-all). Чтобы справиться с этими проблемами, архитектуру переписали так, чтобы сохранять отдельные наборы потоков (threads) для основных автомата и для lookbehind. Это позволяло сразу же прерывать поиск, когда основной автомат завершал работу и регистрировал совпадение, не дожидаясь окончания работы lookbehind. Такой подход значительно повысил производительность и позволил восстановить гарантии линейного времени работы.
Особое внимание в реализации уделялось оптимизациям для bounded lookbehinds — ограниченных по длине обратных утверждений. В отличие от полных unbounded lookbehinds, которые требуют запуска поиска lookbehind с начала всей строки, bounded lookbehinds могут стартовать на позиции, отдалённой не более чем на k символов от тех, где начинается поиск основного регулярного выражения. Вычисление k основывается на комплексном анализе минимальной и максимальной длины шаблонов вокруг выражения lookbehind. Эта оптимизация позволила сократить объём работы по«догонке» lookbehind и обеспечила заметный прирост производительности, достигая в некоторых случаях ускорения до 150 раз. Помимо симуляции НКА, в Rust-движке имеется мощный backtracking-движок, реализованный с мемоизацией (bitstate backtracker), который предназначен для более сложных паттернов и оставляет за собой право попробовать все варианты с эффективным устранением повторов.
Реализация поддержки lookbehind здесь также была выполнена с учётом особенностей backtracking. Ключевой вызов состоял в необходимости выполнять обратный обход строки для проверки lookbehind, что потребовало компиляции lookbehind-подвыражений в обратную сторону. Кроме того, мемоизация в backtracking была усложнена тем, что результаты проверки lookbehind должны быть запомнены отдельно для обеспечения корректной обработки повторных обращений к состояниям. Важным практическим аспектом стал метод оптимизации match-all, в котором движок при поиске всех неперекрывающихся совпадений повторно запускает процедуру поиска с позиции конца предыдущего совпадения. Без дополнительной работы по сохранению информации о потоках lookbehind при повторных поисках это приводило к неоптимальному поведению и квадратичной сложности.
В PikeVM была внедрена логика сохранения активных потоков lookbehind между поисками, что позволило добиться существенного улучшения и сохранить линейную сложность. В целом, внедрение lookbehind стало серьёзным вызовом для архитектуры и реализации движка regex. Работа была выполнена с уделением внимания надежности, корректности и производительности. Благодаря тесной интеграции различных компонентов экосистемы Rust и применению современных алгоритмических решений удалось создать функциональность, ранее почти недостижимую для линейных движков былиход. Benchmark на основе популярных и реально используемых шаблонов из системы сетевого мониторинга Snort подтвердил, что новая реализация работает в разумных временных пределах, демонстрируя сопоставимые с Python re показатели, учитывая разницу в архитектуре движков.
Будущее развитие включает дальнейшее расширение поддержки более сложных конструкций, таких как lookaheads с вложенными capture groups, и углублённую оптимизацию для различных сценариев использования. Появление в экосистеме Rust полноценной и оптимизированной поддержки lookbehind открывает путь для создания более выразительных и высокопроизводительных приложений в сфере обработки текста, сетевого анализа, безопасности и многих других областях. Таким образом, реализация lookbehind в rust-lang/regex — это не просто добавление новой возможности, а целый комплекс инноваций, оптимизаций и архитектурных решений. Она выводит Rust на новый уровень инструментов для работы с регулярными выражениями, одновременно сохраняя высокую скорость и надёжность, что делает эту реализацию одной из лучших в современном программном пространстве.
