На протяжении последних нескольких лет, я переписывал крейт regex, чтобы лучше задействовать внутреннюю композицию, и сделать её проще для добавления оптимизаций, управляя корректностью. На пути этого переписывания я создал новый крейт regex-automata, который предоставляет другим в пользование большую часть внутренностей крейта regex в виде API. На сколько я знаю, это первая библиотека для регулярных выражений (далее - р.в.), которая раскрывает своё внутреннее устройство в той же степени.

Этот пост содержит обсуждение проблем, с которыми я столкнулся во время переписывания крейта, и как они были решены, а так путеводитель по API крейта regex-automata.

Целевая аудитория: программисты на Rust и все, кому интересно устройство конкретного конечного автомата для р.в. Предполагается опыт в работе с р.в.

Краткий экскурс

В сентябре 2012, в репозитории Rust появился тикет, в котором запрашивалось добавление библиотеки р.в. в дистрибутив Rust. Позже Грейдон Хоар (Graydon Hoare) отметился в этом обсуждении, что они предпочли RE2. Для тех, кто не знает, RE2 - это движок р.в., который использует конечный автомат, чтобы гарантировать в худшем случае время поиска, равное O(m * n), при этом предоставляя Perl-подобный синтаксис, но который не включает в себя возможности, которые неизвестно как эффективно реализовать. Внутреннее устройство RE2 описано его автором, Рассом Коксом (Russ Cox), в серии статей по реализации движка р.в. с использованием конечного автомата.

В апреле 2014, я отметился в обсуждении и написал, что работаю над движком р.в., вдохновлённым крейтом RE2. Я использовал статьи Кокса в качестве чертежа для построения библиотеки р.в. Вскоре после этого я опубликовал RFC для добавления библиотеки р.в. в Rust Distribution. Это было ещё до Rust 1.0 и пакетного менеджера Cargo (второй версии, а не первой), и под "Rust Distribution" понимались rustc, std и несколько вспомогательных библиотек, которые были все связаны вместе. Этот RFC предлагал добавление крейта regex в список этих вспомогательных библиотек.

Десятью днями позднее, RFC был одобрен. На следующий день я засабмитил pull request в rust-lang/rust. Всё быстро завертелось. Отмечу так же, что изначально я назвал крейт regexp. И PR включал в себя обсуждение названия, что в конечном счёте привело к переименованию в regex.

Двумя годами позже, в мае 2016, я написал RFC с релизом regex 1.0. Одобрение заняло несколько месяцев, но на самом деле я зарелизил regex 1.0 только пару лет спустя, в мае 2018.

Перед релизом regex 1.0, я непрерывно работал над полном переосмыслении внутреннего устройства крейта. Из описания коммита в марте 2018:

Переписывание [regex-syntax] должно является первым шагом в попытке пересмотреть полностью крейт regex.

Я точно не знал, куда в тот момент времени я двигался, но в марте 2020 я всерьёз начал работать над переписыванием движков сопоставления (the actual matching engines). Чуть менее трёх лет спустя, полностью переписанный крейт regex 1.9 был зарелизен.

Проблемы

С какими типами проблем столкнулся крейт regex, которые служили оправданием полного переписывания? И более того, зачем публиковать переписанные внутренности в виде отдельного крейта?

Здесь много тем для обсуждения.

Проблема: Сложная композиция

Следуя традиции RE2, regex содержал несколько разных стратегий, с помощью которых можно было реализовать поиск. Иногда сразу несколько стратегий использовались в единственном вызове метода поиска.

В общем, тут две размерности для каждой стратегии, часто ортоганальных друг другу: производительность и функциональность. Более быстрые стратегии так же более ограничены в возможностях. Например, быстрая стратегия может уметь сообщать начало и конец совпадения, но не смещения для каждой группы захвата (capture group) в р.в.

Когда я изначально писал крейт, я реализовал единственную стратегию (PikeVM), и вообще не думал о том, как привнести альтернативные стратегии. Само собой, новые стратегии были органично добавлены:

• BoundedBacktracker, который так же сообщал смещения групп захвата, как и PikeVM, но используя стратегию отката (backtracking). Главное ограничение - объём памяти в O(m * n). Так что эта стратегия может использоваться только для небольших р.в. и объёмов текста (т.н. haystack, дословно "стог сена", далее просто "стог" - прим.). Главное достоинство - эта стратегия обычно быстрее, чем PikeVM.

• Гибрид ДКА/НКА (Детерминированного Конечного Автомата (DFA) и Недетерминированного Конечного Автомата (NFA)), так же известный как Ленивый ДКА ("lazy DFA"), который выполняется очень быстро, но сообщает только начало и конец совпадения. Он полностью игнорирует группы захвата.

• Словесная стратегия, где р.в. представляет собой язык, который одновременно и конечный, и компактный. Например: foo, foo{2}, foo|bar, foo[1-3]. В этом случае мы можем просто использовать одиночный или много подстроковый (multi-substring) поисковый алгоритм без использования движка р.в. вообще.

(Мы узнаем, почему эти стратегии имеют эти компромиссы более подробно в этом блоге)

И вместе с вышеперечисленными стратегиями пришла и их комбинация (композиция):

• Если требуется предоставить смещения для групп захвата, обычно быстрее сначала запустить ленивый ДКА, чтобы найти границы совпадения, а только затем запустить PikeVM или BoundedBacktracker, чтобы найти смещения групп захвата. При этом, особенно для случаев, когда совпадения достаточно редкие, большая часть работы выполняется гораздо более быстрым ленивым ДКА.

• Если р.в. начинается с префикса, который соответствует небольшому конечному языку, мы можем реализовать префильтр, который ищет включения (occurences) с этим языком. Каждое такое включение соответствует кандидату на совпадение для всего р.в. Для каждого такого кандидата на совпадением мы уже запускаем полноценных движок р.в., чтобы подтвердить или опровергнуть, что это совпадение нам подходит. Например, foo\w+ может искать включения строки foo в стоге, и затем запускается р.в. foo\w+ по смещению, с которого включение начинается. Если р.в. возвращает совпадение, просто останавливаемся и сообщаем об этом. В ином случае, перезапускаем поиск подстроки foo дальше в стоге.

С течением времени, я захотел добавить как ещё стратегий, так и способов их комбинирования. Но в органично развивающейся инфраструктуре крейт начал прогибаться под собственным весом. Проще говоря, всё следующее являлось проблемами:

• Не все стратегии были спроектированы так, чтобы комбинироваться с другими. Например, PikeVM была первой стратегией и страдала от этого. Особенно, когда не могла работать с указанием начала и конца поиска в подподследовательности внутри среза, что необходимо при композиции с ленивым ДКА. Как пример: с одной стороны PikeVM могла сообщить о том, что р.в. \babc\b совпадает со строкой abcxyz, если начать поиск по смещению 0 и закончить его по смещению 3. Но завершающий \b не должен возвращать совпадение, так как за c следует x.

• Было трудно разобраться, какую из стратегий использовать для заданного р.в.

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

• Устройство крейта не предполагало факта того, что некоторые стратегии вообще не должны конструироваться (инициализироваться). Например, в один прекрасный момент я реализовал оптимизация для крейта regex (ещё до переписывания), которая просто использовала алгоритм Ахо-Корасик для р.в. типа foo1|foo2|...|fooN, но это было настолько костыльно (it was extremenly hacky) сделано, что в результате инициировалась стратегия НКА Томпсона (Thompson NFA), которая на самом деле вообще не использовалась.

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

Проблема: Сложность тестирования

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

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

Проблема в том, до релиза regex 1.9, что все используемые внутри стратегии не являлись частью публичного API, что осложняло их независимое тестирование. Конечно, можно тестировать публичное API, но логика выбора конкретного внутреннего движка р.в. достаточно сложная. Т.о. не всегда ясно и очевидно, какой внутренний движок р.в. будет использоваться для конкретного р.в. Более того, это ещё может и меняться по мере доработки логики. Так что написание тестов для публичного API не то, что могло бы покрыть тестами все внутренние движки р.в. И даже если бы это было сделано, всё равно дебаг зафейленных тестов был бы более раздражающим, чем необходимым, потому что приходилось бы вдумываться в логику выбора используемой стратегии.

Одним из подходов является размещение тестов внутри крейта, чтобы тесты имели доступ к внутренним API. Но если хочется выполнять одни и те же тесты для всех движков р.в., то требуется спецификация тестов в каком-то структурированном формате и их прогон в цикле по каждому из движков. С тех пор, когда тестовая инфраструктура не была написана для проверки каждой отдельной стратегии, я решил не идти по этому пути.

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

• Я раскрыл некоторые внутренние API, чтобы было возможным конфигурировать и собирать внутренние стратегии извне крейта.

• Я сделал это так, чтобы можно было построить главный тип Regex из этих внутренних API, используя недокументированную реализацию трейта From.

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

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

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

Проблема: запросы к нишевым API

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

Одним из самых популярных из таких запросов было улучшение поддержки мульти-паттернов (multi-pattern). А именно, крейт предоставляет API RegexSet, который позволяет искать совпадения (возможно, перекрывающиеся) по нескольким р.в. сразу. Суть в том, что API возвращал только р.в., для которых нашлись совпадения в стоге. Но нельзя было использовать это API, чтобы получить ещё и смещения и совпадения, или смещения групп захвата. Это было полезным, но не настолько, как могло бы быть, если бы поддерживало полный API Regex.

Как и в случае множества внутренних движков р.в. и стратегии тестирования, API RegexSet был прикручен к существующей реализации довольно-таки хитрым способом. Чтобы сделать его способным возвращать смещения совпадения потребовались бы либо значительный рефакторинг всех существующих движков или переписывание.

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

Так же были другие запросы на дополнительные API:

• Возможность выполнять якорный поиск без необходимости включения ^ в шаблон. Это особенно полезно в контексте выполнения р.в. на части стога, в котором заведомо известно, что есть совпадение, но где хочется извлечь текст в группах захвата. Это так же полезно в контексте использования итератора, кототорый только сообщает о соседних совпадениях. Крейт regex мог бы быть дополнен поддержкой всего этого, но нет простого способа расширения существующих API, кроме как дублирования всех методов поиска или необходимости создания опции "якорного режима" (anchored mode), которую следует передавать в API (Чего можно добиться, если просто добавить ^ в начало р.в.).

• Возможность запускать поиск по р.в. без их внутренней синхронизации, чтобы получить mutable scratch space. Это может понадобиться в определённых случаях, чтобы избежать накладных расходов на синхронизацию. Но чтобы это сделать, пришлось бы так же дублировать все API и предоставлять новый тип, который представлял бы функциональность для "mutable scratch space".

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

Опубликованный отдельно версионированный новый крейт, который содержит большую часть внутренностей крейта regex, предоставил "передышку" для большого числа API, которые требуются людям, без необходимости загромождать API общего назначения, на котором и лежит большая часть всех случаев использования р.в. А именно, ориентируя этот крейт на экспертные случаи использования, мы не делаем вид, что пытаемся сохранить API компактным и простым. Наоборот, как вы увидим, API крейта regex-automata многословный и сложный. И сделав его отдельной версией, мы можем выпускать релизы с ломающими изменениями гораздо быстрее, чем для крейта regex.

Эта мотивация не так сильно отличается от мотивов, что привели к публикации крейта regex-syntax. А именно, некоторым людям (включая меня) хотелось иметь доступ к парсеру р.в. в своих проектах. Я определённо не хотел вытаскивать парсер в крейте regex наружу, потому что это добавляло бы сложности и к тому же мне хотелось иметь возможность дорабатывать его и его типы независимо от крейта regex. (Именно поэтому крейт regex-syntax имеет большее число ломающих релизов, чем сам крейт regex). Вынеся парсер в отдельный крейт, я смог одновременно использовать его и как деталь реализации крейта regex, и так же сделать его доступным для использования другими.

Проблема: полностью компилируемые ДКА

Рождение regex-automata на самом деле не было результатом моего крестового похода на переписывание крейта regex, а совпало с желанием сделать полностью компилируемые ДКА, сериализовав их и затем предоставить поисковый рантайм, который мог бы десериализовать (с zero-cost-подходом) эти ДКА и использовать их для поиска. Я использовал изначальную версию regex-automata для построения ДКА, реализовав различные алгоритмы для Юникода внутри крейта bstr.

В процессе создания начальной версии regex-automata, я понял, что мне нужно перестроить структуру данных НКА и компилятор для них, что было очень похоже на то, что было обнаружено в крейте regex. В определённый момент я начал задаваться вопрос, как бы можно было бы переиспользовать этот код, посколько он достаточно нетривиален и полон мест, где происходит довольно много интересных оптимизаций.

Я немного задумался о создании нового крейта что-то вроде regex-nfa, от которого могли бы зависеть бы крейты и regex и regex-automata. Но после дальнейших размышлений стало ясно, что гораздо больше кода можно расшарить между этими крейтами. Например, большая часть процесса детерминизации может быть написана в общем виде так, что могла бы работать как для полностью скомпилированных ДКА, так и для ленивых ДКА.

На тот момент правильная граница абстракции казалась ближе к "движку р.в.", чем к "просто НКА". Поэтому я пересмотрел крейт regex-automata как не столько просто ДКА, а скорее как зверинец движков р.в. План в тот момент был, грубо говоря, чтобы поместить все движки р.в. в крейт regex-automata, а крейт regex сделать просто тонкой обёрткой поверх него. Устроив всё подобным образом, это должно уменьшить трудности при переходе от крейта regex на regex-automata, если понадобится доступ к более низкоуровневым API.

Таким образом, мы можмешь строить полностью компилируемые ДКА, используя тот же самый код, который использует крейт regex для своих ленивых ДКА. И тот же самый код, что крейт regex использует для конвертирования распарсенного представления шаблона в НКА. Хех, в некоторых случаях это даже делает возможным использовать полностью скомпилированные ДКА внутри крейта regex. (Обычно это очень сильное "нет" в движках р.в. общего назначения, посколько полностью скомпилированный ДКА не только сильно раздут, но и в худшем случае требуют экспоненциального времени для построения. Это очень не подходит для движков р.в., который используется для компиляции недоверенных шаблонов, или даже в тех случаях, когда требуется вменяемое время компиляции р.в. Построение ДКА может быть неподходящим подходом, особенно когда дело касается Юникода).