Дисклеймер

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

Если всегда было интересно, как оно там под капотом устроено, а в книге Фриддла или в книге дракона вы не нашли подробностей, то добро пожаловать - будет интересно и очень сложно.

Для понимания потребуются:

• Знания основ теории автоматов (знать и понимать отличия ДКА от НКА)

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

• Начальные знания по языку Rust

• Общие представления отличия различных структур данных друг от друга

Так же прошу сообщать об ошибках и опечатках, чтобы я мог их исправить.

Содержание

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

• Проблемы

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

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

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

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

• По пути с regex-cli

• Поток данных

• Литеральные оптимизации

  • Мотивация литеральных оптимизаций

  • Извлечение литералов

  • Поиск литералов

• Тип данных - НКА

  • Простой пример НКА

  • Оптимизация НКА: разреженное состояние

  • Оптимизация НКА: минимальный автомат для UTF-8

  • Оптимизация НКА: дерево литералов

  • Дальнейшие доработки НКА

• Движки регулярных выражений

  • Общие элементы всех движков регулярных выражений

  • Движок: PikeVM

  • Движок: BoundedBacktracker

  • Движок: однопроходный ДКА

  • Движок: ДКА

  • Движок: гибрид НКА/ДКА

  • Мета движок

• Отличия от RE2

• Стратегия тестирования

• Бенчмаркинг

• Цена вопроса

• Заключение

На протяжении последних нескольких лет, я переписывал крейт 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, чтобы найти смещения групп захвата. При этом, особенно для случаев, когда совпадения достаточно редкие, большая часть работы выполняется гораздо более быстрым ленивым ДКА.

• Если р.в. начинается с префикса, который соответствует небольшому конечному языку, мы можем реализовать префильтр, который ищет включения (occurrences) с этим языком. Каждое такое включение соответствует кандидату на совпадение для всего р.в. Для каждого такого кандидата на совпадение мы уже запускаем полноценный движок р.в., чтобы подтвердить или опровергнуть, что это совпадение нам подходит. Например, 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. (Обычно это очень сильное "нет" в движках р.в. общего назначения, поскольку полностью скомпилированный ДКА не только сильно раздут, но и в худшем случае требуют экспоненциального времени для построения. Это очень не подходит для движков р.в., который используется для компиляции недоверенных шаблонов, или даже в тех случаях, когда требуется вменяемое время компиляции р.в. Построение ДКА может быть неподходящим подходом, особенно когда дело касается Юникода).

По пути с regex-cli

regex-cli - программа, которая сопровождается как часть крейта regex, и которая предоставляет удобный интерфейс командной строки для доступа ко множеству API крейтов regex-syntax, regex-automata и regex. Так же программа включает некоторые полезные утилиты, такие как сериализация полностью скомпилированных ДКА в файл и генерация Rust-кода для их чтения.

Я буду использовать regex-cli на протяжении всего этого поста, так что если вы хотите продолжить, можете установить эту тулзу прямо из репозитория крейта regex:

$ cargo install regex-cli

Вот пара примеров, которые показывают, как влияет Юникод на р.в. .. Сначала, версия, где включен Юникод:

$ regex-cli debug thompson '.' --no-table

thompson::NFA(
>000000: binary-union(2, 1)
 000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 10
 000003: \x80-\xBF => 11
 000004: \xA0-\xBF => 3
 000005: \x80-\xBF => 3
 000006: \x80-\x9F => 3
 000007: \x90-\xBF => 5
 000008: \x80-\xBF => 5
 000009: \x80-\x8F => 5
 000010: sparse(\x00-\t => 11, \x0B-\x7F => 11, \xC2-\xDF => 3, \xE0 => 4, \xE1-\xEC => 5, \xED => 6, \xEE-\xEF => 5, \xF0 => 7, \xF1-\xF3 => 8, \xF4 => 9)
 000011: capture(pid=0, group=0, slot=1) => 12
 000012: MATCH(0)

transition equivalence classes: ByteClasses(0 => [\x00-\t], 1 => [\n], 2 => [\x0B-\x7F], 3 => [\x80-\x8F], 4 => [\x90-\x9F], 5 => [\xA0-\xBF], 6 => [\xC0-\xC1], 7 => [\xC2-\xDF], 8 => [\xE0], 9 => [\xE1-\xEC], 10 => [\xED], 11 => [\xEE-\xEF], 12 => [\xF0], 13 => [\xF1-\xF3], 14 => [\xF4], 15 => [\xF5-\xFF], 16 => [EOI])
)

А вот версия с отключенным Юникодом:

$ regex-cli debug thompson '(?-u:.)' --no-table --no-utf8-syntax

thompson::NFA(
>000000: binary-union(2, 1)
 000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 3
 000003: sparse(\x00-\t => 4, \x0B-\xFF => 4)
 000004: capture(pid=0, group=0, slot=1) => 5
 000005: MATCH(0)

transition equivalence classes: ByteClasses(0 => [\x00-\t], 1 => [\n], 2 => [\x0B-\xFF], 3 => [EOI])
)

На выводе показан НКА Томпсона, скомпилированный крейтом regex-automata для заданного р.в. Команда regex-cli debug может выводить много разных типов данных из экосистемы крейта regex.

$ regex-cli debug
Prints the debug representation of various things from regex-automata and
regex-syntax.

This is useful for ad hoc interactions with objects on the command line. In
general, most objects support the full suite of configuration available in code
via the crate.

USAGE:
    regex-cli debug <command> ...

COMMANDS:
    ast        Print the debug representation of an AST.
    dense      Print the debug representation of a dense DFA.
    hir        Print the debug representation of an HIR.
    literal    Print the debug representation of extracted literals.
    onepass    Print the debug representation of a one-pass DFA.
    sparse     Print the debug representation of a sparse DFA.
    thompson   Print the debug representation of a Thompson NFA.

Так же есть команда regex-cli find, которая может выполнять ad hoc поиск. Например, вот как выполнить мультишаблонный поиск с группами захвата, используя движок р.в. meta:

$ regex-cli find capture meta \
   -p '(?<email>[.\w]+@(?<domain>[.\w]+))' \
   -p '(?<phone>(?<areacode>[0-9]{3})-[0-9]{3}-[0-9]{4})' \
   -y 'foo@example.com, 111-867-5309'
     parse time:  20.713µs
 translate time:  22.116µs
build meta time:  834.731µs
    search time:  142.537µs
  total matches:  2
0:{ 0: 0..15/foo@example.com, 1/email: 0..15/foo@example.com, 2/domain: 4..15/example.com }
1:{ 0: 17..29/111-867-5309, 1/phone: 17..29/111-867-5309, 2/areacode: 17..20/111 }

Загляните в regex-cli README за другими примерами.

Поток данных

Перед тем, как погрузиться в детали, стоит сделать паузу для того, чтобы ознакомиться с терминологией и кратко описать поток данных, проходящий через движок р.в. Т.е., когда вы вызываете Regex::new с каким-то шаблоном, мы отследим преобразования, происходящие с этим шаблоном, которые превращают его в нечто, что может искать совпадения.

• Первым делом строка с шаблоном парсится в Ast (Abstract Syntax Tree). Ast - это структурированное представление шаблона.

• Затем Ast транслируется в Hir (High-Level Intermediate Representation) Hir - это другое структурное представление шаблона, но содержащее гораздо меньше деталей, чем Ast. Вещи, вроде Unicode case folding или Unicode character class reference расширяются в процессе трансляции.

• Следом Hir используется для построения двух сущностей. Первая - это литеральная последовательность (literal sequence), которая соответствует последовательности литералов, извлечённой из шаблона, и которая используется для оптимизации поиска по р.в. в некоторых случаях. При возможности, литеральная последовательность используется для построения префильтра (Prefilter). Вторая сущность - это НКА

• В определённый момент НКА используется для построения различных движков р.в.:

  • PikeVM может работать со всеми возможными р.в., которые поддерживаются парсингом. Так же PikeVM может сообщать смещения для совпавших групп захвата.

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

  • Однопроходный ДКА (one-pass DFA) поддерживает очень ограниченное подмножество р.в., но может находить смещения групп захвата очень быстро.

  • Полностью скомпилированный [плотный ДКА (dense DFA)](https://docs.rs/regex-automata/0.3.*/regex_automata/dfa/dense/struct.DFA.html). Может находить только начало и конец (когда скомбинирован со вторым развёрнутым задом наперёд ДКА) совпадения, но чрезвычайно быстрый. Главный недостаток - алгоритм построения в худшем случае имеет сложность O(2^m) по времени выполнения и памяти.

  • Ленивый ДКА (Lazy DFA), который конструирует себя из НКА во время поиска. В некоторых случаях он может быть медленнее PikeVM, но в большинстве случаев он такой же быстрый, как полностью скомпилированный ДКА, но к тому же без сложности O(2^m) по времени/памяти при конструировании.

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

• Крейт regex является сам по себе лишь тонкой обёрткой над мета движком р.в. из крейта regex-automata.

Мы обсудим каждую из этих сущностей более детально на протяжении поста, но трудно избежать отсылок к некоторым из них на начальных этапах объяснения, до полного их раскрытия. Данная глава, которая даёт самый общий чертёж внутренностей крейта regex, и приведена здесь для введения.

Литеральные оптимизации

В этой главе мы начнём наше путешествие во внутреннее устройство крейта regex и поговорим о критически важной технике оптимизации, которая там используется: извлечение литералов из р.в. Например, р.в. (foo|bar|quux)(\s+\w+) описывает регулярный язык, в котором все элементы языка начинаются либо с foo, либо с bar, либо с quux. В свою очередь, каждое совпадение этого р.в. гарантировано начинается с одного из трёх литералов.

Мотивация литеральных оптимизаций

Так почему же это важно? Почему литералы нас вообще заботят? А это исходит из двух мыслей:

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

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

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

Извлечение литералов

Приведу кое-какие примеры. Для этого мы будем использовать regex-cli и подкоманду regex-cli debug literal для извлечения литералов из р.в. Начнём с простого:

$ regex-cli debug literal 'bar'
           parse time:  13.967µs
       translate time:  7.008µs
      extraction time:  405ns
    optimization time:  1.479µs
                  len:  Some(1)
           is finite?:  true
            is exact?:  true
      min literal len:  Some(3)
      max literal len:  Some(3)
longest common prefix:  Some("bar")
longest common suffix:  Some("bar")

E("bar")

Далее, я буду обрезать вывод команды, потому что она выводит уж очень много информации. Ну теперь давайте разбираться:

• Время парсинга (parse time) показывает, сколько времени занимает преобразование шаблона bar в структурированное значение Ast.

• Время трансляции (translate time) показывает, сколько времени занимает преобразование значения Ast в значение Hir.

• Время извлечения (extraction time) соответствует времени, которое было затрачено преобразование значения Hir в литеральную последовательность.

• Время оптимизации (optimization time) показывает, сколько времени занимает "оптимизация" литеральной последовательности. Это может быть как простым удалением дубликатов литералов, так и таким агрессивным, как сокращение последовательности различными способами, основанными на эвристиках. Мы увидим больше примеров этого позже.

• len - количество литералов в последовательности, которая была извлечена.

• Флаг is finite показывает, имеет ли извлечённая последовательность конечное количество элементов. Бесконечная последовательность представляет собой последовательность всех возможных литералов, и это обычно значит, что литеральные оптимизации невозможны либо не являются целесообразными.

• Флаг is exact показывает, является ли каждый элемент в литеральной последовательности точным или нет (читай далее, т.к. краткое объяснение немного запутанно или я просто тупой и его не понял, поэтому опустил, чтобы не вводить себя и людей в заблуждение некорректным переводом - прим.) An exact literal refers to a literal that reached a match state from the place where literal extraction began. Since this command extracts prefixes, an exact literal corresponds to an overall match of the regex. If a literal is not exact, then it is said to be inexact.

• min literal len - длина в байтах самого короткого литерала в последовательности.

• max literal len - длина в байтах самого длинного литерала в последовательности.

• longest common prefix (наибольший общий префикс) - одиночный литерал, который является префиксом всех элементов в последовательности. Бесконечные последовательности и конечные последовательности, содержащие нуль элементов, не имеют общего префикса. Все остальные последовательности имеют общий префикс, как минимум состоящий из пустой строки.

• longest common suffix (наибольший общий суффикс) - одиночный литерал, который является суффиксом всех элементов в последовательности. Бесконечные последовательности и конечные последовательности, содержащие нуль элементов, не имеют общего суффикса. Все остальные последовательности имеют общий суффикс, как минимум состоящий из пустой строки.

И наконец, после всех метаданных, показана извлечённая последовательность. Т.к. данное р.в. является просто литералом bar, последовательность содержит одиночный конкретный элемент, соответствующий литералу bar. Если bar являлся строгим префиксом, то последовательность была бы той же самой, но уже неточной.

$ regex-cli debug literal --no-table 'bar+'
I("bar")

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

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

$ regex-cli debug literal --no-table 'bar[a-z]'
I("bar")

При извлечении литералов можно подсчитать каждый литерал, например, bara, barb, barc, ..., barz. Но этого не происходит. Почему? Оказывается, что извлечение литералов является одной большой эвристикой. Тёмное искусство (dark art), если хотите. Мы вынуждены вернуться к вопросу почему мы вообще сначала выполняем извлечение литералов: чтобы очень быстро идентифицировать кандидатов на совпадение в стоге перед тем, как использовать более медленный движок р.в. для подтверждения того, есть ли в этом месте совпадение.

Штука в том, что выбор какие литералы искать может быть так же важен, как и выбор каким образом их искать. Алгоритм с самой высокой пропускной способностью не поможет, если стог состоит из миллиона a, а ваше р.в. является простым литералом a. Ключевой момент в том, что хорошая литеральная оптимизация достигает обеих следующих целей:

• Минимизирует число ложно положительных кандидатов. Т.е. большинство отобранных кандидатов являются совпадениями.

• Минимизирует влияние на задержку от поиска. Т.е., когда префильтр активен, в идеале это приводит к работе движка р.в. только на небольшой части стога. Если префильтр часто сообщает о кандидатах, то даже при рейте ложно положительных срабатываний в 0%, влияние на задержку скорее всего ухудшит общее время поиска.

Причина, по которой я называл литеральные оптимизации тёмным искусством (dark art) в том, что невозможно знать до того, как поиск начнётся, каким образом оптимальнее всего выбрать из двух вышеуказанных стратегий. Эти обе стратегии зависят от самого стога, и его сканирование с целью "изучения" почти всегда негативно влияет на общее время поиска. Следовательно, нам приходится угадывать, как минимизировать ложно положительные срабатывания и в тоже время уменьшить влияние на задержку. Вот почему это является тёмным искусством.

К счастью, есть кое-какие общие подходы (guidelines), которым мы можем следовать, чтобы получить хороший результат:

• Меньшая последовательность литералов обычно лучше, чем большая, но не в случае, если элементы чрезвычайно короткие (т.е. длиной 1 или 2 байта). Короткие элементы вероятнее будут совпадать более часто, и в таком случае предпочтительнее от них отказаться. Например, у нас 5000 литералов, которые все ограничиваются ASCII символами в нижнем регистре. Мы могли бы тривиально сократить число литералов к почти 26, взяв первый байт каждого литерала. Но эта новая последовательность литералов вероятно будет возвращать совпадения более часто, что в результате приведёт к удару по задержке и к более высокому рейту ложно положительных срабатываний. И было бы лучше уменьшить последовательность, оставив более длинные литералы, которые с меньшей вероятностью будут возвращать совпадение.

• Длинные литералы в общем лучше, чем короткие, но не в случае огромных последовательностей. Длинные литералы обычно более избирательные, т.е. они приводят к более меньшему рейту ложно положительных совпадений, т.к. вероятность их совпадения меньше. Но никто не хочет произвольно отдавать приоритет длинным литералам. Например, у вас может быть последовательность foobar, foobaz, fooquux, но более подходящая последовательность, скорее всего, будет foo даже с учётом того, что она короче всех трёх этих литералов. Один элемент в последовательности хорош тем, что потенциально означает использование алгоритма для поиска одиночной подстроки (который, вероятно, быстрый).

Извлечение литералов максимально возможно пытается придерживаться вышеперечисленных подходов, но есть и некоторые другие эвристики, которые часто вступают в игру. Например, ASCII пробел (U+0020) необычно распространённый. Если бы последовательность содержала пробел, тогда бы она стала бесконечной после оптимизации, и эффективнее отключить литеральную оптимизацию. Например, это р.в., из которого извлекается три префиксных литерала:

$ regex-cli debug literal --no-table '(?:foo|z|bar)[a-z]+'
I("foo")
I("z")
I("bar")

А вот в этом р.в. этого не происходит. Разница только в том, что z заменили пробелом:

$ regex-cli debug literal --no-table '(?:foo| |bar)[a-z]+'
Seq[∞]

Эта эвристика участвует во время "оптимизирующего" прохода по литеральной последовательности. Эвристика приняла во внимание, что один из литералов является просто пробельным символов, предположила, что это приведёт к более высокому рейту ложно положительных совпадений, и сделала последовательность бесконечной. Когда последовательность бесконечна, это сообщает, что нет небольшого набора конечных литералов, который (скорее всего) можно было бы использовать в качестве хорошего префильтра. Если мы отключаем оптимизацию, то можем увидеть, что пробельный символ входит в последовательность:

$ regex-cli debug literal --no-table --no-optimize '(?:foo| |bar)[a-z]+'
I("foo")
I(" ")
I("bar")

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

$ regex-cli debug literal --no-table 'foo| |bar'
E("foo")
E(" ")
E("bar")

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

Тут стоит пояснить, почему я использую термин литеральная последовательность вместо литерального множества. А именно, порядок следования извлечённых литералов имеет значение. Это имеет значение, потому что крейт regex пытается симулировать Perl-подобную семантику. Т.е. о совпадениях, которые находятся, сообщается так, как если бы использовался поиск с возвратом (backtracking search). Это так же называется leftmost-first совпадениями, и в этом контексте, оператор | не является коммутативным. Например:

$ regex-cli debug literal --no-table 'sam|samwise'
E("sam")

$ regex-cli debug literal --no-table 'samwise|sam'
E("samwise")
E("sam")

Тут две разные последовательности. В первом случае, sam|samwise всегда будет матчить только часть sam, т.к. sam является префиксом samwise и в шаблоне идёт в начале. Поэтому литеральная последовательность, состоящая только из sam, является корректной, т.к. samwise никогда не совпадёт. Во втором случае, samwise|sam может находить обе ветки. Даже при том, что sam является префиксом samwise, из-за того, что samwise идёт первым, оно будет предпочтительнее для совпадения со строкой samwise в стоге.

(Заметка: POSIX движки р.в. не реализует р.в. подобным образом. Вместо этого, в них используется leftmost-longest семантики, когда самое длинное возможное совпадение предпочтительнее. В этом случае оператор | является коммутативным. Некоторые другие движки, такие как Hyperscan реализуют семантики "вернуть все совпадения" или "самое раннее совпадение". В таком случае на стоге abc по р.в. abc|a будет возвращено оба совпадения a и abc).

Наши последние примеры показывают, что извлечение литералов достаточно разумно. Например:

$ regex-cli debug literal --no-table 'abc?de?[x-z]ghi'
I("abcde")
I("abcdx")
I("abcdy")
I("abcdz")
I("abdex")
I("abdey")
I("abdez")
I("abdxg")
I("abdyg")
I("abdzg")

Т.е. извлечение литералов знает, как раскрывать штуки вроде ? и даже небольшие классы символов. Это работает до тех пор, пока размер литеральной последовательности находится в пределах нескольких разных эвристических ограничений. (Замечу, что так же извлечение литералов может перечислить каждый элемент языка, описанным р.в., но оптимизация выбрала сократить последовательность в соответствие с эвристикой.)

Другой пример "интеллекта" заключается в регистронезависимости, включая поддержку Юникода, которая так же учитывается:

$ regex-cli debug literal --no-table '(?i)She'
E("SHE")
E("SHe")
E("ShE")
E("She")
E("sHE")
E("sHe")
E("shE")
E("she")
E("ſHE")
E("ſHe")
E("ſhE")
E("ſhe")

На самом деле это не результат извлечения литералов, реализующую Unicode case folding, а скорее результат трансляции из Ast в Hir, который так же осуществляет case folding:

$ regex-cli debug hir --no-table '(?i)She'
Concat(
    [
        Class(
            {
                'S'..='S',
                's'..='s',
                'ſ'..='ſ',
            },
        ),
        Class(
            {
                'H'..='H',
                'h'..='h',
            },
        ),
        Class(
            {
                'E'..='E',
                'e'..='e',
            },
        ),
    ],
)

Т.е. извлечение литералов воспринимает данное р.в. как что-то эквивалентное [Ssſ][Hh][Ee]. И всё, что оно делает - это раскрывает классы символов, как и в любом другом р.в.

Поиск литералов

Как только мы извлекли кое-какие литералы, нам нужно поднять, как их теперь искать.

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

Есть несколько разных аспектов, применительно к используемому алгоритму из memchr::memmem:

• Его основным алгоритмом является алгоритм Two-Way, который выполняется в худшем случае за O(n) и имеет константную сложность по памяти.

• В случае, когда искомая строка (needle - иголка, далее для краткости и.с.) и стог очень короткие, используется алгоритм Рабина-Карпа.

• На архитектуре x86_64 используется вариант алгоритма "SIMD общего назначения". В общих чертах: сначала выбирается два байта из и.с. (прим. - как правило, не соседних), и с помощью векторных инструкций ищется появление этих двух байт в нужных позициях. Когда найдены эти два байта, проверяется полное совпадение с и.с. (Заметим, что это просто другой вариант механизма префильтра. Мы сперва используем быстрый поиск кандидатов, а затем выполняем шаг более затратной проверки.)

Для алгоритма SIMD общего назначения, вместо того, чтобы всегда выбирать первый и последний байт в и.с., мы выбираем два "редких" байта, в соответствии с распределением. Т.е. мы предполагаем, что байты типа Z встречаются реже, чем байты типа a. Это не всегда так, но мы тут на территории эвристики. Это достаточно хорошо работает на практике. Выбирая байты, которые вероятно редко встречаются в и.с., мы надеемся максимизировать время поиска кандидатов, затрачиваемое векторными инструкциями, и минимизировать число проверок, которые надо будет сделать.

Случай с множеством подстрок немного сложнее: нужно убедиться, что мы рассматриваем литералы как последовательность и приоритезируем совпадения более ранних литералов над совпадениями с литералами, которые идут позже. Так же обычно верно то, что поиск по нескольким подстрокам будет медленнее, чем поиск единственной подстроки, просто потому, что требуется выполнить больше работы. Основным используемым алгоритмом является Teddy, портированный мной из Hyperscan. На высоком уровне он использует векторные инструкции для быстрого обнаружения кандидатов, а затем проверяем их для подтверждения совпадения.

Алгоритм Ахо-Корасик так же используется в некоторых случаях, хотя обычно движок р.в. будет просто предпочитать конструировать ленивый ДКА, т.к. производительность схожая. Ахо-Корасик всё ещё может помочь в качестве префильтра, когда нет возможности использовать ленивый ДКА. Ну и обычно Ахо-Корасик лучше ленивого ДКА, когда число литералов экстремально большое (порядка десятков тысяч).

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

Тип данных - НКА

Если внутри крейта regex и был центральный тип данных, то, по всей вероятности, это был бы НКА (Недетерминированный Конечный Автомат). Если точнее, это НКА Томпсона, что означает, что он был построен алгоритмом, схожим с Томпсоновским алгоритмом конструирования. Этот алгоритм строит НКА из структурированного представления р.в. за время O(m), где m пропорционально размеру р.в. после подсчёта повторений, которые разворачиваются. (Например, a{5} - это aaaaa.) Алгоритм работает, отображая каждый тип р.в. в мини-НКА, а затем определяя правила для комбинирования этих мини-НКА в один большой НКА.

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

Перед тем, как разбираться с НКА более детально, взглянем на простой пример.

Простой пример НКА

Так же, как и в случае извлечения литералов, regex-cli может нам быть полезным, позволяя выводить отладочное представление НКА заданного р.в.:

$ regex-cli debug thompson 'a'
        parse time:  9.856µs
    translate time:  3.005µs
  compile nfa time:  18.51µs
            memory:  700
            states:  6
       pattern len:  1
       capture len:  1
        has empty?:  false
          is utf8?:  true
       is reverse?:  false
   line terminator:  "\n"
       lookset any:  ∅
lookset prefix any:  ∅
lookset prefix all:  ∅

thompson::NFA(
>000000: binary-union(2, 1)
 000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 3
 000003: a => 4
 000004: capture(pid=0, group=0, slot=1) => 5
 000005: MATCH(0)

transition equivalence classes: ByteClasses(0 => [\x00-`], 1 => [a], 2 => [b-\xFF], 3 => [EOI])
)

Далее я буду сокращать вывод только до самого НКА. Так что объясню, что тут значит остальной вывод:

• Тайминги парсинга и трансляции - тоже самое, что и в случае извлечения литералов. Напомню, что это время построения значений Ast и Hir.

• compile nfa time - время построения структуры данных NFA из значения Hir.

• memory - объём кучи, используемой НКА

• states - количество состояний в НКА

• pattern len - количество шаблонов в НКА

• capture len - количество групп захвата (далее - г.з.), скомпилированных в НКА. Когда г.з. задействованы (по-умолчанию это так), тогда в НКА будет как минимум одна г.з., соответствующая всему совпадению.

• has empty? - может ли НКА вернуть пустую строку в качестве совпадения или нет.

• is utf8? - гарантирует ли НКА то, что он никогда не вернёт в качестве совпадения невалидную UTF-8 строку. Это так же включает в себя ограничение на сопоставление пустой строки между code units в UTF-8 codepoint. Например, ???? в юникоде выглядит как \xF0\x9F\x92\xA9. В то время, как пустое р.в. будет возвращать совпадение в каждой позиции, НКА в UTF-8 режиме вернёт совпадение только непосредственно перед \xF0 и после \xA9.

• is reverse? - вернёт ли НКА совпадение для перевёрнутого р.в. Это значит, что НКА вернёт совпадение для языка, описанного изначальным р.в., но если элементы языка будут развёрнуты задом наперёд.

• line terminator - символ окончания строки, который используется для р.в. (?m:^), (?m:$) и ..

• lookset any - множество всех граничных элементов (look-around assertions) в р.в.

• lookset prefix any - множество всех граничных элементов (look-around assertions), которые встречаются в префиксе р.в. При каждом совпадении может совпасть ноль или более этих элементов.

• transition equivalence classes - разбиение всех возможных байтовых значений во множество классов эквивалентности. Смысл в том, что каждый байт в классе эквивалентности может быть рассмотрен как эквивалент другому в зависимости от того, происходит ли совпадение.

Кроме того, ещё выведен и сам НКА. Пробежимся по нему:

>000000: binary-union(2, 1)
 000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 3
 000003: a => 4
 000004: capture(pid=0, group=0, slot=1) => 5
 000005: MATCH(0)

Циркумфлекс (^) перед состоянием 2 означает, что это "якорное" ("anchored") стартовое состояние, в то время, как знак больше (>) перед состоянием 0 означает, что это "неякорное" ("unanchored") стартовое состояние. Первое используется в поиске с учётом якорей (позиционных проверок), а второе - в поиске без учёта якорей.

Неякорный поиск начинается с операции binary-union(2, 1): сначала НКА должен перейти в состояние 2 (состояние захвата - capture state), и только если этот переход завершился неуспехом, то НКА пробует перейти в состояние 1. В нашем случае, состояние 1 матчит (возвращает совпадение) любой байт, и происходит возврат обратно в состояние 0. В результате, состояния 0 и 1 представляют собой неявный префикс (?s-u:.)*? в начале р.в., позволяя находить совпадение в любой части стога (прим.: стог - текст, в котором производится поиск).

Состояние capture - безусловный эпсилон-переход ради побочного эффекта: он заставляет виртуальную машину, выполняющую НКА, сохранить смещение в слот, указанный в этом capture состоянии. Если переходы НКА происходят вне контекста виртуальной машины (или любого другого движка, который поддерживает г.з.), состояния capture просто игнорируются и воспринимаются как безусловные эпсилон-переходы без всяких побочных эффектов. Например, так они обрабатываются в процессе детерминизации - процессе преобразования НКА в ДКА.

Когда НКА оказывается в состоянии 3, производится проверка байта в текущей позиции на его эквивалентность символу a, и если проверка успешна, НКА переходит в состояние 4, которое является ещё одним capture состоянием. И наконец-таки происходит переход в состояние 5, которое является состоянием совпадения с шаблоном под идентификатором 0.

Оптимизация НКА: разреженные состояния

Одна из главных проблем с НКА Томпсона проистекает из того, что делает его достойным выбором для движка р.в. общего назначения: время его построения в худшем случае составляет O(m), но это достигается за счёт очень свободного использования эпсилон-переходов. Эпсилон-переходы - это переход в НКА, который выполняется без потребления входных данных. Это один из двух способов, с помощью которого поиск через симуляцию НКА может реализовать одновременное нахождение в нескольких состояниях (Другой способ - несколько переходов из одного состояния НКА для одного символу из стога.)

Так почему же эпсилон-переходы являются проблемой? Когда выполняется обход НКА (не важно, для поиска или для построения какого-нибудь другого объекта, вроде ДКА), эпсилон-переход представляет собой дополнительные расходы, которые приходится нести, когда он осуществляется. В частности, каждое состояние НКА имеет нечто, которое называется эпсилон-замыканием, и является множеством состояний, которых можно достигнуть (в которых может НКА оказаться), если рекурсивно выполнять эпсилон-переходы. В зависимости от того, в каком состоянии находится НКА, эпсилон-замыкание может перевычисляться множество раз. Эпсилон-замыкание для определённого состояния может меняться во время переходов, потому что некоторые эпсилон-переходы могут быть условными. Например, такими, которые соответствуют позиционным проверкам типа ^, $ и \b.

Давайте взглянем на относительно простую оптимизацию, которую я применил в новом компиляторе НКА. Сначала посмотрим, как крейт regex версии младше 1.9 компилирует р.в. [A-Za-z0-9]:

$ regex-debug compile --bytes '[A-Za-z0-9]'
0000 Save(0) (start)
0001 Split(2, 3)
0002 Bytes(0, 9) (goto: 6)
0003 Split(4, 5)
0004 Bytes(A, Z) (goto: 6)
0005 Bytes(a, z)
0006 Save(1)
0007 Match(0)

(Заметка: regex-debug - более старая версия утилиты командной строки для взаимодействия с крейтом regex. Она больше недоступна, хотя вы всегда можете переключиться на более старый тег в репозитории крейта и собрать её.)

Инструкция Split соответствует состоянию НКА с двумя безусловными эпсилон-переходами (тоже самое, что и инструкция binary-union в предыдущей подглаве). Инструкция Save предназначена для функционирования г.з., а инструкция Bytes - для проверки текущего символа из стога на совпадение с одиночным байтом или на вхождение в непрерывный диапазон байт. В данном случае символьный класс реализован через множество инструкций Split. Так же обратите внимание, что эпсилон-замыкание состояния 0 равно {1, 2, 3, 4, 5} (прим.: потому что в эти состояния НКА может попасть не потребив ни одного байта стога).

А теперь посмотрим, что делает новый компилятор НКА:

$ regex-cli debug thompson --no-table '[A-Za-z0-9]'
thompson::NFA(
>000000: binary-union(2, 1)
 000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 3
 000003: sparse(0-9 => 4, A-Z => 4, a-z => 4)
 000004: capture(pid=0, group=0, slot=1) => 5
 000005: MATCH(0)
)

(Можно игнорировать состояния 0 и 1, так как по некоторым причинам старый НКА не имеет эквивалентный префикс.)

Здесь, вместо эпсилон-переходов, у нас имеется просто состояние НКА sparse. Название sparse (разреженный) отсылает к тому факту, что состояние содержит больше одного непрерывного диапазона байт, которые могут указывать на разные состояния. Оно используется, потому что данное представление не позволяет за постоянное время определить, имеет ли конкретный символ стога переход или нет (т.е. нужно использовать линейный или двоичный поиск, чтобы определить, есть вхождение в указанные диапазоны или нет). Т.о. делается тоже самое, что и в нескольких инструкциях Split в старом НКА, но уже без явных эпсилон-переходов. Это приводит к меньшим накладным расходам, потому что нет необходимости высчитывать эпсилон-замыкание через несколько инструкций Split. Здесь только одно состояние и для поиска следующего перехода требуется проверка на вхождение текущего символа стога в указанные диапазоны.

Основным недостатком данной конкретной оптимизации является то, что разреженное состояние (в текущем представлении НКА) для своей поддержки использует косвенные переходы. Таким образом, это может негативно сказываться на эффективность работы кеш-памяти, а так же в некоторых случаях может приводить к повышенному расходу памяти из кучи. Но накладные расходы при использовании эпсилон-переходов на практике всё равно выше. Возможно, в будущем косвенные переходы будут убраны.

Оптимизация НКА: минимальный автомат для UTF-8

Одним из интересных аспектов старого компилятора НКА было то, что он мог давать на выходе два разных типа НКА: НКА, алфавит которого был определён через Unicode code points, и НКА, алфавит которого был определён через байты. (В таких байт-ориентированных НКА разрешены не только UTF-8 code units, но даже байты, которые никогда не могут быть валидными UTF-8 code point-ами, к примеру, \xFF.) Юникодные НКА принципиально используются при задействовании движков р.в. на основе НКА (таких, как PikeVM или BoundedBacktracker, которых коснёмся позднее), в то время, как байт-ориентированные НКА используются при использовании ленивого ДКА. Байт-ориентированные НКА требуются из-за того, что ленивый ДКА работает с алфавитом, определённым через байты. Иначе возникает трудноразрешимая проблема с производительностью. (Байт-ориентированные НКА могут использоваться и с движками р.в. на основе НКА, но это только в случае, когда р.в. нужно искать строки, невалидные в UTF-8, и т.о. невозможно использовать Юникод алфавит.)

Это приводило как минимум к трём проблемам. Первая в том, что байт-ориентированные НКА часто были медленнее, в основном из проблемы эпсилон-переходов, которая обсуждалась ранее. Это потому, что байт-ориентированные НКА обычно имели больше инструкций Split, в то время, как Юникодные НКА были похоже больше на НКА с состоянием sparse из нового компилятора. Например:

$ regex-debug compile '[A-Za-z0-9]'
0000 Save(0) (start)
0001 '0'-'9', 'A'-'Z', 'a'-'z'
0002 Save(1)
0003 Match(0)

Заметьте, что тут вообще нет инструкций Split.

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

Третья проблема в том, что НКА движкам р.в. нужно работать как с Юникодной, так и с байт-ориентированной версиями НКА. Это привносит сложность и является причиной багов. Скорее всего, проблему можно было бы сгладить лучшим дизайном, но это всё равно усложнение.

Так какое отношение это имеет к UTF-8 автоматам? От байт-ориентированного НКА всё ещё требуется возможность работать с Юникодными классами. Но если алфавитом являются байты, а не code points, то как быть? Это делается встраиванием UTF-8 автомата в НКА. Например, вот НКА (из нового компилятора), который может найти любое скалярное Юникод значение в кодировке UTF-8:

$ regex-cli debug thompson --no-table '(?s:.)'
thompson::NFA(
>000000: binary-union(2, 1)
 000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 10
 000003: \x80-\xBF => 11
 000004: \xA0-\xBF => 3
 000005: \x80-\xBF => 3
 000006: \x80-\x9F => 3
 000007: \x90-\xBF => 5
 000008: \x80-\xBF => 5
 000009: \x80-\x8F => 5
 000010: sparse(\x00-\x7F => 11, \xC2-\xDF => 3, \xE0 => 4, \xE1-\xEC => 5, \xED => 6, \xEE-\xEF => 5, \xF0 => 7, \xF1-\xF3 => 8, \xF4 => 9)
 000011: capture(pid=0, group=0, slot=1) => 12
 000012: MATCH(0)
)

Это достигается следующим образом: начинаем с непрерывного диапазона Юникодных code point-ов и затем генерируем последовательность байт-ориентированных символьных классов, которые находят UTF-8 кодировку этого диапазона code point-ов. Эта функциональность предоставляется модулем utf8 из крейта regex-syntax. Например, вот так выглядело бы р.в. (?s:.):

[0-7F]
[C2-DF][80-BF]
[E0][A0-BF][80-BF]
[E1-EC][80-BF][80-BF]
[ED][80-9F][80-BF]
[EE-EF][80-BF][80-BF]
[F0][90-BF][80-BF][80-BF]
[F1-F3][80-BF][80-BF][80-BF]
[F4][80-8F][80-BF][80-BF]

Трансляция этого в НКА может быть выполнена просто через использование альтернатив. Вроде этого:

[0-7F]|[C2-DF][80-BF]|...|[F4][80-8F][80-BF][80-BF]

И это будет работать и это корректно. Проблема в том, что при этом генерируются очень большие НКА для некоторых очень распространённых случаев. Ясно, что проблема с Юникодом в том, что он привносит экстремально большие символьные классы в р.в. Классы типа \w, например, содержат 139 612 отдельных code point-а (на момент написания). ASCII версия \w содержит только 63 code point-а. Это кардинальная разница, и трюки, которые будут работать для небольшого количества вроде 63 просто не будут масштабироваться до чисел вроде 139 612.

Старый крейт не наивно компилировал UTF-8 автомат, как показано выше. Напротив, существует множество вспомогательных структур в классах, производимых модулем utf8. Старый крейт это замечал и старался сократить р.в. за счёт общих суффиксов, комбинируя их при возможности. Но это всё равно приводило к экстремально большим НКА:

$ regex-debug compile --bytes '\w' | tail -n20
3545 Bytes(\xb0, \xb0) (goto: 3466)
3546 Bytes(\xf0, \xf0) (goto: 3545)
3547 Split(3550, 3551)
3548 Bytes(\x80, \x8c) (goto: 28)
3549 Bytes(\xb1, \xb1) (goto: 3548)
3550 Bytes(\xf0, \xf0) (goto: 3549)
3551 Split(3554, 3555)
3552 Bytes(\x8d, \x8d) (goto: 2431)
3553 Bytes(\xb1, \xb1) (goto: 3552)
3554 Bytes(\xf0, \xf0) (goto: 3553)
3555 Split(3558, 3562)
3556 Bytes(\x84, \x86) (goto: 28)
3557 Bytes(\xa0, \xa0) (goto: 3556)
3558 Bytes(\xf3, \xf3) (goto: 3557)
3559 Bytes(\x80, \xaf) (goto: 3563)
3560 Bytes(\x87, \x87) (goto: 3559)
3561 Bytes(\xa0, \xa0) (goto: 3560)
3562 Bytes(\xf3, \xf3) (goto: 3561)
3563 Save(1)
3564 Match(0)

Заметьте, что тут показано только последние 20 строк вывода. Но в полученном НКА насчитывается 3 564 состояния. Ух. И везде ещё эпсилон-переходы. Это натуральная лажа, и единственная причина, по которой старый крейт так хорошо работает, состоит в том, что ленивый ДКА выручал, компилируя только небольшую часть этого, которая на самом деле использовалась в ДКА.

А теперь посмотрим, что делает новый компилятор НКА:

$ regex-cli debug thompson --no-table '\w' | tail -n20
 000292: \xB0-\xB9 => 310
 000293: sparse(\x84 => 115, \x85 => 291, \x86 => 210, \xAF => 292)
 000294: \x80-\x9F => 310
 000295: sparse(\x80-\x9A => 5, \x9B => 294, \x9C-\xBF => 5)
 000296: sparse(\x80-\x9B => 5, \x9C => 282, \x9D-\x9F => 5, \xA0 => 55, \xA1-\xBF => 5)
 000297: sparse(\x80-\xA1 => 310, \xB0-\xBF => 310)
 000298: sparse(\x80-\xB9 => 5, \xBA => 297, \xBB-\xBF => 5)
 000299: \x80-\xA0 => 310
 000300: sparse(\x80-\xAE => 5, \xAF => 299)
 000301: \x80-\x9D => 310
 000302: sparse(\xA0-\xA7 => 5, \xA8 => 301)
 000303: sparse(\x80-\x8A => 310, \x90-\xBF => 310)
 000304: sparse(\x80-\x8C => 5, \x8D => 303, \x8E-\xBF => 5)
 000305: sparse(\x80-\x8D => 5, \x8E => 236)
 000306: sparse(\x90 => 193, \x91 => 231, \x92 => 235, \x93 => 238, \x94 => 239, \x96 => 247, \x97 => 118, \x98 => 248, \x9A => 250, \x9B => 256, \x9C => 257, \x9D => 276, \x9E => 290, \x9F => 293, \xA0-\xA9 => 118, \xAA => 295, \xAB => 296, \xAC => 298, \xAD => 118, \xAE => 300, \xAF => 302, \xB0 => 118, \xB1 => 304, \xB2 => 305)
 000307: sparse(\x84-\x86 => 5, \x87 => 236)
 000308: \xA0 => 307
 000309: sparse(0-9 => 310, A-Z => 310, _ => 310, a-z => 310, \xC2 => 3, \xC3 => 4, \xC4-\xCA => 5, \xCB => 6, \xCC => 5, \xCD => 7, \xCE => 8, \xCF => 9, \xD0-\xD1 => 5, \xD2 => 10, \xD3 => 5, \xD4 => 11, \xD5 => 12, \xD6 => 13, \xD7 => 14, \xD8 => 15, \xD9 => 16, \xDA => 5, \xDB => 17, \xDC => 18, \xDD => 19, \xDE => 20, \xDF => 21, \xE0 => 53, \xE1 => 93, \xE2 => 109, \xE3 => 116, \xE4 => 117, \xE5-\xE9 => 118, \xEA => 137, \xEB-\xEC => 118, \xED => 140, \xEF => 155, \xF0 => 306, \xF3 => 308)
 000310: capture(pid=0, group=0, slot=1) => 311
 000311: MATCH(0)

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

Новый компилятор НКА добивается такого эффекта за счёт использования алгоритма Дацука для вычисления минимального ДКА из отсортированной последовательности непересекающихся элементов. Это именно то, что мы получаем от модуля utf8. На практике нам нет необходимости генерировать минимальные ДКА, так как это требует использования памяти, но можно пожертвовать строгой минимальностью, чтобы ограничить объём используемой памяти. Но обычно этого вполне достаточно.

Обратный случай не так просто обработать, потому что не существует (насколько мне известно) простого способа обратной сортировки вывода модуля utf8 таким образом, чтобы алгоритм Дацука заработал с ним. Чтобы обойти это, я создал структуру данных, называемую дерево диапазонов (range trie), которая перераспределяет вывод модуля utf8 в обратном порядке, чтобы данные были отсортированы и не пересекались. После этого можно использовать алгоритм Дацука, как в предыдущем случае. Проблема заключается в том, что это может значительно увеличить время, необходимое на построение НКА. По этой причине нужно явно согласиться на это. Смотрим сначала без обратного сжатия (reverse shrinking):

$ regex-cli debug thompson --no-table --no-captures '\w' -r | tail -n20
 001367: \xB1 => 722
 001368: \x80-\x8C => 1367
 001369: \x80-\xBF => 1368
 001370: \x8D => 1367
 001371: \x80-\x8A => 1370
 001372: \x90-\xBF => 1370
 001373: \x8E-\xBF => 1367
 001374: \x80-\xBF => 1373
 001375: \xB2 => 722
 001376: \x80-\x8D => 1375
 001377: \x80-\xBF => 1376
 001378: \x8E => 1375
 001379: \x80-\xAF => 1378
 001380: \xF3 => 1386
 001381: \xA0 => 1380
 001382: \x84-\x86 => 1381
 001383: \x80-\xBF => 1382
 001384: \x87 => 1381
 001385: \x80-\xAF => 1384
 001386: MATCH(0)

А теперь с ним:

$ regex-cli debug thompson --no-table --no-captures '\w' -r --shrink | tail -n20
 000469: sparse(\x90 => 2, \x92 => 2, \x97 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE3 => 488, \xE4 => 488, \xE5-\xE9 => 488, \xEA => 488,
 \xEB-\xEC => 488, \xEF => 488)
 000470: sparse(\x97 => 2, \x9A => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE3 => 488, \xE4 => 488, \xE5-\xE9 => 488, \xEA => 488, \xEB-\xEC
=> 488)
 000471: sparse(\x80 => 3, \x81 => 387, \x82 => 6, \x83 => 387, \x84 => 397, \x85 => 451, \x86 => 174, \x87 => 6, \x88 => 100, \x89 => 100, \x8A => 13, \x8B => 348, \x8C => 14, \x8D => 45
2, \x8E => 16, \x8F => 88, \x90 => 19, \x91 => 62, \x92 => 20, \x93 => 343, \x94 => 21, \x95 => 62, \x96 => 23, \x97 => 61, \x98 => 179, \x99 => 27, \x9A => 27, \x9B => 441, \x9C => 446,
\x9D => 236, \x9E => 28, \x9F => 461, \xA0 => 454, \xA1 => 442, \xA2 => 31, \xA3 => 428, \xA4 => 33, \xA5 => 467, \xA6 => 35, \xA7 => 330, \xA8 => 455, \xA9 => 468, \xAA => 388, \xAB => 4
43, \xAC => 43, \xAD => 414, \xAE => 84, \xAF => 447, \xB0 => 438, \xB1 => 416, \xB2 => 363, \xB3 => 457, \xB4 => 67, \xB5 => 340, \xB6 => 199, \xB7 => 141, \xB8 => 465, \xB9 => 374, \xBA
 => 53, \xBB => 417, \xBC => 459, \xBD => 56, \xBE => 469, \xBF => 470, \xC3 => 488, \xC4-\xCA => 488, \xCC => 488, \xCD => 488, \xCE => 488, \xCF => 488, \xD0-\xD1 => 488, \xD2 => 488, \
xD3 => 488, \xD4 => 488, \xD5 => 488, \xD6 => 488, \xD8 => 488, \xD9 => 488, \xDA => 488, \xDC => 488, \xDD => 488, \xDF => 488)
 000472: sparse(\x91 => 2, \x92 => 2, \x93 => 2, \x97 => 2, \x98 => 2, \x9F => 2, \xA0 => 7, \xA1-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xAE => 2, \xB0 => 2, \xB1 => 2, \
xB2 => 2, \xE1 => 488, \xE2 => 488, \xE3 => 488, \xE4 => 488, \xE5-\xE9 => 488, \xEA => 488, \xEB-\xEC => 488, \xED => 488)
 000473: sparse(\x92 => 2, \x94 => 2, \x97 => 2, \x98 => 2, \x9D => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xAE => 2, \xB0 => 2, \xB1 => 2, \xE1 => 488, \xE3 => 48
8, \xE4 => 488, \xE5-\xE9 => 488, \xEB-\xEC => 488, \xED => 488)
 000474: sparse(\x91 => 2, \x97 => 2, \x98 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE2 => 488, \xE3 => 488, \xE4 => 488, \xE5-\xE9 => 488,
 \xEA => 488, \xEB-\xEC => 488, \xEF => 488)
 000475: sparse(\x90 => 2, \x91 => 2, \x96 => 2, \x97 => 2, \x9C => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE0 => 488, \xE1 => 488, \xE3 =>
488, \xE4 => 488, \xE5-\xE9 => 488, \xEA => 488, \xEB-\xEC => 488)
 000476: sparse(\x90 => 2, \x96 => 2, \x97 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE0 => 488, \xE3 => 488, \xE4 => 488, \xE5-\xE9 => 488,
 \xEA => 488, \xEB-\xEC => 488, \xEF => 488)
 000477: sparse(\x80 => 218, \x81 => 387, \x82 => 6, \x83 => 387, \x84 => 472, \x85 => 451, \x86 => 174, \x87 => 387, \x88 => 12, \x89 => 100, \x8A => 13, \x8B => 348, \x8C => 14, \x8D =>
 452, \x8E => 16, \x8F => 426, \x90 => 19, \x91 => 62, \x92 => 20, \x93 => 473, \x94 => 21, \x95 => 62, \x96 => 23, \x97 => 61, \x98 => 179, \x99 => 157, \x9A => 27, \x9B => 441, \x9C =>
446, \x9D => 236, \x9E => 28, \x9F => 461, \xA0 => 454, \xA1 => 442, \xA2 => 31, \xA3 => 428, \xA4 => 33, \xA5 => 467, \xA6 => 305, \xA7 => 317, \xA8 => 463, \xA9 => 468, \xAA => 388, \xA
B => 443, \xAC => 223, \xAD => 414, \xAE => 43, \xAF => 447, \xB0 => 438, \xB1 => 474, \xB2 => 363, \xB3 => 457, \xB4 => 140, \xB5 => 340, \xB6 => 266, \xB7 => 141, \xB8 => 465, \xB9 => 2
01, \xBA => 108, \xBB => 417, \xBC => 475, \xBD => 476, \xBE => 77, \xBF => 470, \xC3 => 488, \xC4-\xCA => 488, \xCC => 488, \xCE => 488, \xCF => 488, \xD0-\xD1 => 488, \xD2 => 488, \xD3
=> 488, \xD4 => 488, \xD5 => 488, \xD8 => 488, \xD9 => 488, \xDA => 488, \xDC => 488, \xDD => 488)
 000478: sparse(\x97 => 2, \x9D => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xAE => 2, \xB0 => 2, \xB1 => 2, \xE3 => 488, \xE4 => 488, \xE5-\xE9 => 488, \xEA => 488,
 \xEB-\xEC => 488)
 000479: sparse(\x91 => 2, \x96 => 2, \x97 => 2, \x98 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xAE => 2, \xAF => 2, \xB0 => 2, \xB1 => 2, \xE0 => 488, \xE3 => 48
8, \xE4 => 488, \xE5-\xE9 => 488, \xEA => 488, \xEB-\xEC => 488)
 000480: sparse(\x96 => 2, \x97 => 2, \x98 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xAE => 2, \xAF => 2, \xB0 => 2, \xB1 => 2, \xE3 => 488, \xE4 => 488, \xE5-\xE
9 => 488, \xEB-\xEC => 488, \xEF => 488)
 000481: sparse(\x90 => 2, \x97 => 2, \x98 => 2, \x9D => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xAE => 2, \xB0 => 2, \xB1 => 2, \xE0 => 488, \xE1 => 488, \xE3 =>
488, \xE4 => 488, \xE5-\xE9 => 488, \xEB-\xEC => 488, \xEF => 488)
 000482: sparse(\x91 => 2, \x97 => 2, \x98 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xAE => 2, \xB0 => 2, \xB1 => 2, \xE0 => 488, \xE1 => 488, \xE3 => 488, \xE4 =
> 488, \xE5-\xE9 => 488, \xEA => 488, \xEB-\xEC => 488, \xEF => 488)
 000483: sparse(\x91 => 2, \x97 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE0 => 488, \xE1 => 488, \xE2 => 488, \xE3 => 488, \xE4 => 488, \x
E5-\xE9 => 488, \xEA => 488, \xEB-\xEC => 488)
 000484: sparse(\x91 => 2, \x97 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE0 => 488, \xE1 => 488, \xE2 => 488, \xE3 => 488, \xE4 => 488, \x
E5-\xE9 => 488, \xEA => 488, \xEB-\xEC => 488, \xEF => 488)
 000485: sparse(\x97 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE3 => 488, \xE4 => 488, \xE5-\xE9 => 488, \xEA => 488, \xEB-\xEC => 488)
 000486: sparse(\x80 => 4, \x81 => 396, \x82 => 6, \x83 => 387, \x84 => 472, \x85 => 451, \x86 => 174, \x87 => 387, \x88 => 12, \x89 => 100, \x8A => 195, \x8B => 348, \x8C => 14, \x8D =>
452, \x8E => 16, \x8F => 426, \x90 => 19, \x91 => 62, \x92 => 20, \x93 => 473, \x94 => 114, \x95 => 62, \x96 => 23, \x97 => 61, \x98 => 179, \x99 => 27, \x9A => 27, \x9B => 441, \x9C => 4
46, \x9D => 236, \x9E => 28, \x9F => 478, \xA0 => 462, \xA1 => 442, \xA2 => 31, \xA3 => 479, \xA4 => 33, \xA5 => 467, \xA6 => 305, \xA7 => 480, \xA8 => 481, \xA9 => 399, \xAA => 482, \xAB
 => 443, \xAC => 43, \xAD => 414, \xAE => 43, \xAF => 447, \xB0 => 438, \xB1 => 474, \xB2 => 363, \xB3 => 457, \xB4 => 483, \xB5 => 484, \xB6 => 108, \xB7 => 141, \xB8 => 465, \xB9 => 374
, \xBA => 108, \xBB => 417, \xBC => 71, \xBD => 476, \xBE => 57, \xBF => 485, \xC3 => 488, \xC4-\xCA => 488, \xCC => 488, \xCD => 488, \xCE => 488, \xCF => 488, \xD0-\xD1 => 488, \xD2 =>
488, \xD3 => 488, \xD4 => 488, \xD5 => 488, \xD6 => 488, \xD8 => 488, \xD9 => 488, \xDA => 488, \xDB => 488, \xDC => 488, \xDD => 488)
^000487: sparse(0-9 => 488, A-Z => 488, _ => 488, a-z => 488, \x80 => 58, \x81 => 72, \x82 => 78, \x83 => 86, \x84 => 96, \x85 => 111, \x86 => 123, \x87 => 136, \x88 => 143, \x89 => 153,
\x8A => 165, \x8B => 172, \x8C => 177, \x8D => 186, \x8E => 194, \x8F => 202, \x90 => 217, \x91 => 222, \x92 => 224, \x93 => 227, \x94 => 233, \x95 => 238, \x96 => 244, \x97 => 251, \x98
=> 257, \x99 => 258, \x9A => 269, \x9B => 274, \x9C => 279, \x9D => 285, \x9E => 295, \x9F => 298, \xA0 => 312, \xA1 => 315, \xA2 => 320, \xA3 => 322, \xA4 => 328, \xA5 => 333, \xA6 => 33
8, \xA7 => 341, \xA8 => 345, \xA9 => 351, \xAA => 360, \xAB => 365, \xAC => 368, \xAD => 375, \xAE => 383, \xAF => 385, \xB0 => 395, \xB1 => 402, \xB2 => 408, \xB3 => 411, \xB4 => 418, \x
B5 => 425, \xB6 => 429, \xB7 => 435, \xB8 => 440, \xB9 => 444, \xBA => 450, \xBB => 460, \xBC => 466, \xBD => 471, \xBE => 477, \xBF => 486)
 000488: MATCH(0)

Таким образом, сжатие в обратном случае всё ещё значительно помогает в плане генерации более компактных НКА с меньшим количеством состояний. Но из-за влияния на время компиляции оно по-умолчанию отключено. Поэтому оптимизация минимального UTF-8 автомата применяется только к прямым НКА. (Обратные НКА создаются для использования с ДКА, т.к. для ДКА требуется обратное сканирование, чтобы найти начало каждого совпадения.) Однако, мы всё ещё проверяем избыточные суффиксы и объединяем их в обратном случае, когда обратное сжатие не задействовано.

Оптимизация НКА: литеральное дерево

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

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

$ regex-debug compile 'zap|z|zapper'
0000 Save(0) (start)
0001 Split(2, 5)
0002 'z'
0003 'a'
0004 'p' (goto: 13)
0005 Split(6, 7)
0006 'z' (goto: 13)
0007 'z'
0008 'a'
0009 'p'
0010 'p'
0011 'e'
0012 'r'
0013 Save(1)
0014 Match(0)

Здесь мы строим НКА для р.в. zap|z|zapper. Тут он использует вложенные инструкции Split. Начинается со Split(2, 5), которая указывает на начало zap и другую инструкцию Split(6, 7). Вторая инструкция указывает на начало z и zapper. Так что для данного р.в. при поиске совпадения, эпсилон-замыкание всех состояний разбивается на считанное количество для каждого символа в стоге.

В отличие от этого, посмотрим, что делает новый компилятор ДКА:

$ regex-cli debug thompson --no-table 'zap|z|zapper'
thompson::NFA(
>000000: binary-union(2, 1)
 000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 11
 000003: p => 12
 000004: a => 3
 000005: r => 12
 000006: e => 5
 000007: p => 6
 000008: p => 7
 000009: a => 8
 000010: union(4, 12, 9)
 000011: z => 10
 000012: capture(pid=0, group=0, slot=1) => 13
 000013: MATCH(0)

(Снова проигнорируем состояния 0 и 1, которые соответствуют опциональному позиционному префиксу (?s-u:.)*?. Старый компилятор не добавляет эти состояния по некоторым причинам.)

Перед единственным эпсилон-переходом, что мы вообще видим, сначала должна найтись z в состоянии 11. Только после это видно состояние union(4, 12, 9) (Эта инструкция эквивалентна вложенным Split инструкциям в старом компиляторе НКА, но комбинирующая все в одно состояние.) Если бы этот НКА использовался бы для поиска, не было бы необходимости высчитывать эпсилон-замыкание для каждого символа в стоге. Это необходимо было бы сделать только после того, как встретилось z, что гораздо более реже случалось бы. В результате этого, р.в. можно было бы переписать в виде z(?:ap||apper).

Так что же здесь происходит? В этом конкретном случае, это выглядит почти как сокращение общего префикса. Но работающая здесь оптимизация носит гораздо более общий характер. Допустим у нас есть р.в. abc|xyz. Здесь нет общего префикса. Что выдаёт старый компилятор НКА:

$ regex-debug compile 'abc|xyz'
0000 Save(0) (start)
0001 Split(2, 5)
0002 'a'
0003 'b'
0004 'c' (goto: 8)
0005 'x'
0006 'y'
0007 'z'
0008 Save(1)
0009 Match(0)

Здесь мы снова видимо инструкцию Split, которая разветвляет поток на начало abc и затем на xyz.

А теперь новый компилятор НКА:

$ regex-cli debug thompson --no-table 'abc|xyz'
thompson::NFA(
>000000: binary-union(2, 1)
 000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 7
 000003: c => 8
 000004: b => 3
 000005: z => 8
 000006: y => 5
 000007: sparse(a => 4, x => 6)
 000008: capture(pid=0, group=0, slot=1) => 9
 000009: MATCH(0)
)

Здесь вообще нет эпсилон-переходов. Символы a и x размещены в одном разреженном состоянии, каждый символ разветвляет поток на свой соответствующий суффикс, bc и yz.

Компилятор НКА распознал альтернативу литералов, скомпилировал её в дерево, и затем преобразовал это дерево напрямую в НКА способом, который минимизирует количество эпсилон-переходов. Ключевым приёмом оптимизации является обеспечение leftmost-first семантики. Например, в приведённом выше примере есть соблазн переписать его в виде z(?:ap(?:per)?)?. Но это р.в. вернёт не тоже самое! На строке zapper оно вернёт zapper, в то время, как изначальное р.в. zap|z|zapper вернёт zap. Литеральное дерево достигает этого, разбивая переходы в каждом состоянии на фрагменты, где фрагмент создаётся всякий раз, когда встречается совпадение (одного из литералов). Если бы создавалось обычное дерево, то приоритет порядка следования, который требуется для leftmost-first семантики, потерялся при трансляции обратно в НКА.

Дальнейшие доработки НКА

Существует для момента, которые бы я хотел исследовать в качестве будущих работ над НКА.

Первый - это НКА Глушкова. У него хуже временная сложность для компиляции, но имеется преимущество в виде полного отсутствия эпсилон-переходов. Из-за времени компиляции, вероятно, НКА Глушкова не может быть использован в каждом случае, но было бы неплохо использовать его для подмножества более малых р.в. Так же НКА Глушкова, возможно, больше подходит для бит-параллельных техник, которые, к сожалению, недостаточно используются в крейте в данный момент. Один из главных вопросов тут для меня в том, как хорошо НКА Глушкова ведёт себя на больших Юникодных классах. (Возможно, такие критерии будут являться дисквалифицирующими.)

Второй момент - хранение НКА в одном непрерывном участке памяти. Это может сделать шаблоны доступа быстрее и более дружелюбными к кешированию, но более важно то, что это может позволить zero-copy сериализацию и десериализацию. Недостатком этого является сложность кода и, возможно, более широкое использование unsafe-конструкций, но есть и некоторые потенциально приятные выгоды.

Движки регулярных выражений

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

Но зачем иметь так много движков р.в.? Причина в сущности инженерии: реализация движков р.в. с большей функциональностью имеют тенденцию искать данные более медленно, чем движки р.в., которые имеют меньшую функциональность. Мы могли бы использовать только один движок, который поддерживает всю функциональность, которая нам нужна, а именно PikeVM, но скорость поиска многих пользователей, скорее всего, разочаровала бы. Это фундаментально приводит к добавлению других движков. Ни один из других движков не поддерживает полный спектр функциональности, предоставляемой крейтом regex, поэтому движок PikeVM берёт всё на себя.

В дополнение к использованию regex-cli для демонстрации того, как запускать каждый движок р.в., так же для примера будет приведено несколько программ на Rust. Для запуска примеров вам нужно будет создать проект с помощью Cargo и добавить regex-automata в зависимости:

$ cargo init --bin
$ cargo add 'regex-automata@0.3'

Затем можно будет отредактировать файл src/main.rs, добавив туда исходный код, и запустить программу с помощью команды cargo run.

Общие элементы движков регулярных выражений

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

Триада самых важных типов: Input (входные данные), Match (совпадение) и MatchError (ошибка поиска).

Input - небольшая абстракция для задания параметров однократного поиска. Единственный обязательный параметр - стог (haystack), который является последовательностью байт, в котором выполняется поиск. Большинство API для поиска принимают всё, что реализует трейт Into<Input>, а так же &[u8] и &str для которых реализация Into<Input> уже есть. Опциональные параметры включают в себя: диапазон стога, в котором осуществлять поиск; выполнение поиска с учётом якорей (позиционных привязок); жадность - пытаться найти как можно больше или остановить поиск, как только найдено совпадение.

Match представляет собой данные о найденном в стоге совпадении и состоит из двух элементов. Первый элемент - диапазон байт (в виде смещений) в стоге, где найдено совпадение. И второй элемент - PatternID, соответствующий шаблону, который найден. (Каждый движок р.в. в regex-automata имеет первоклассную поддержку поиска по множеству шаблонов. Идентификаторы шаблонов присваиваются, начиная с нуля, на основе автоинкремента в порядке передачи шаблонов конструктору движка.)

MatchError представляет собой ошибку, которая возникла в процессе поиска. Если происходит ошибка, то уже невозможно определить, есть ли совпадение или нет, т.е. результат является неопределённым. По этой причине многие из базовых API возвращают результат в виде Result<Option<Match>, MatchError>. Ошибки в процессе поиска могут возникать по самым разных причинам. Например, ДКА может быть сконфигурирован завершаться немедленно, как только встретится определённая последовательность байт. Другой пример - BoundedBacktracker, который возвращает ошибку, если длина стога превышает сконфигурированный лимит. Одна из главных возможностей мета движка р.в., как мы обсудим позже, это предоставление фасада над композицией движков, который никогда не приводит к возврату ошибки вызывающему коду.

Есть ещё некоторые общие моменты между большинством движков р.в. Например, конструирование большей части движков выполняется через Builder, а настройка - через одно и более значений Config. Обсудим это, как только это встретится далее. Так же смотрите раздел API темы в документации на крейт regex-automata.

Движок: PikeVM

Как упоминалось выше, PikeVM берёт всю ответственность на себя (англ. идиома the buck stops with smb.). Т.е. он поддерживает полный комплект возможностей р.в., которые поддерживаются крейтом regex-syntax, и поддерживает их для любого стога любой длины. Другие же движки р.в. имеют различные ограничения. Например:

• BoundedBacktracker работает только в случаях, когда len(haystack) * len(regex) меньше сконфигурированного значения. На практике это означает, что его можно использовать только с достаточно короткими стогами.

• Однопроходный ДКА работает только с малым подмножеством НКА, которые удовлетворяют критерию однопроходности.

• Ленивый ДКА и полный ДКА не могут сопоставлять границы слов в Юникоде. Оба движка имеют эвристические механизмы для обработки Юникодных границ слов как неюникодных, если стог состоит из ASCII. Но если встречается не-ASCII байты, оба движка завершают работу с ошибкой вместо того, чтобы закончить поиск.

Помимо использования значения Cache, движок PikeVM может быть построен напрямую из НКА без дополнительных трудозатрат. Т.е. поиск работает с помощью "симуляции" самого НКА. (Как ни странно, на этот подход иногда ссылаются как на "ДКА алгоритм"). Фактическая реализация представляет собой виртуальную машины, в которой каждое НКА состояние выполняется как инструкция. PikeVM работает, переходя из одного НКА состояния в следующее и вычисляя эпсилон-переходы налету. Т.к. возможно находиться в нескольких состояниях одновременно, то отслеживается каждое активное состояние, и функция перехода применяется к каждому из этих состояний. Так же движок отслеживает позиции групп захвата.

Главная проблема с движком - производительность, и её причина заключается главным образом в необходимости отслеживать большое количество состояний. Для позиций г.з. требуется сообщать смещения начала и конца совпадения, в тоже время требуется следить за активными состояниями в порядке, гарантирующем в худшем случае временную сложность O(m * n). Т.е., в отличие от подхода с возвратом (backtracking), PikeVM проходит по каждому байту стога, как максимум, константное количество раз, вычисляя все возможные активные состояния в пошаговом режиме блокировки (lock-step). Это добавляет довольно много накладных расходов и может быть усугубляться р.в. с большим количеством эпсилон-переходов. (Это одна из причин, по которой ранее в статье было так много времени посвящено оптимизации НКА в плане исключения эпсилон-переходов.)

Теперь мы немного поговорили о том, как PikeVM работает, так что взглянем на несколько примеров. Здесь приведёт код слегка аннотированной программы на Rust, чтобы продемонстрировать, как использовать движок для поиска.

use regex_automata::{nfa::thompson::pikevm::PikeVM, Match};

fn main() {
    // Создаём PikeVM напрямую из р.в.
    // Но можно создать PikeVM напрямую из НКА,
    //   используя `PikeVM::builder()`
    let re = PikeVM::new(r"\b\w+\b").unwrap();

    // Большинству движков нужна область памяти с возможностью
    //   мутабельности (mutable scratch space), куда можно
    //   писать данные при поиске. У движка Мета есть API,
    //   который прячет этот аспект. Но используя движки напрямую,
    //   эта область памяти нужно явно аллоцировать и передать.
    let mut cache = re.create_cache();

    let mut it = re.find_iter(&mut cache, "Σέρλοκ Χολμς");

    assert_eq!(Some(Match::must(0, 0..12)), it.next());
    assert_eq!(Some(Match::must(0, 13..23)), it.next());
    assert_eq!(None, it.next());
}

И вот пример команды regex-cli, которая делает тоже самое:

$ regex-cli find match pikevm --no-table -p '\b\w+\b' -y 'Σέρλοκ Χολμς'
0:0:12:Σέρλοκ
0:13:23:Χολμς

Обратите на использование Юникодных границ слов в не-ASCII стоге. Только PikeVM, BoundedBacktracker и однопроходный ДКА это поддерживают. Ленивый ДКА и полностью компилируемый ДКА вернули бы в этом случае ошибку.

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

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

use regex_automata::nfa::thompson::pikevm::PikeVM;

fn main() {
    let re = PikeVM::new_many(&[
        r"(?<email>[.\w]+@(?<domain>[.\w]+))",
        r"?(<phone>(?<areacode>[0-9]{3})-[0-9]{3}-[0-9]{4})",
    ])
    .unwrap();

    let mut cache = re.create_cache();

    let hay = "foo@example.com, 11-867-5309";
    let mut it = re.captures_iter(&mut cache, hay);

    let caps = it.next().unwrap();
    assert_eq!(0, caps.pattern().unwrap().as_usize());
    assert_eq!("example.com", &hay[caps.get_group_by_name("domain").unwrap()]);

    let caps = it.next().unwrap();
    assert_eq!(1, caps.pattern().unwrap().as_usize());
    assert_eq!("111", &hay[caps.get_group_by_name("areacode").unwrap()]);

    assert!(it.next().is_none());
}

И тоже самое в виде команды regex-cli:

$ regex-cli find capture pikevm --no-table \
   -p '(?<email>[.\w]+@(?<domain>[.\w]+))' \
   -p '(?<phone>(?<areacode>[0-9]{3})-[0-9]{3}-[0-9]{4})' \
   -y 'foo@example.com, 111-867-5309'
0:{ 0: 0..15/foo@example.com, 1/email: 0..15/foo@example.com, 2/domain: 4..15/example.com }
1:{ 0: 17..29/111-867-5309, 1/phone: 17..29/111-867-5309, 2/areacode: 17..20/111 }

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

Движок: BoundedBacktracker

Движок BoundedBacktracker использует алгоритм с возвратом (backtracking algorithm) для выполнения поиска, используя напрямую НКА Томпсона. Его порой так же (как ни странно) называют "НКА алгоритмом". Ключевое отличие между реализацией в крейте regex-automata и другими реализациями алгоритма бэктрекинга в том, что используется дополнительное состояние, чтобы избежать повторных шагов, которые уже были сделаны в процессе возврата. Это позволяет гарантировать время выполнения в худшем случае O(m * n), но за счёт расширения используемой памяти объёмом O(m * n).

(Теоретически, классический алгоритм бэктрекинга так же технически является ограниченным (bounded), но явное указание Bounded в названии движка BoundedBacktracker означает явное использование ограничения в реализации, чтобы гарантировать O(m * n) время работы в худшем случае.)

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

Вот небольшой пример, похожий на предыдущий пример с PikeVM, но использующий движок BoundedBacktracker:

use regex_automata::{nfa::thompson::backtrack::BoundedBacktracker, Match};

fn main() {
    let re = BoundedBacktracker::new(r"\b\w+\b").unwrap();

    // Движку так же нужен кеш, как и PikeVM. В кеше хранится
    //   информация о том, какие шаги уже выполнены, а так же
    //   в нём находится область памяти для стека вызовов движка
    //   Всё это находится в куче.
    let mut cache = re.create_cache();

    // В отличие от PikeVM, bounded backtracker может вернуть ошибку
    //   при поиске. Это случается, когда `len(regex) * len(haystack)`
    //   превышает значение `Config::visited_capacity`
    let mut it = re.try_find_iter(&mut cache, "Σέρλοκ Χολμς");
    assert_eq!(Some(Ok(Match::must(0, 0..12))), it.next());
    assert_eq!(Some(Ok(Match::must(0, 13..23))), it.next());
    assert_eq!(None, it.next());
}

И тоже самое, используя команду regex-cli:

$ regex-cli find match backtrack --no-table -p '\b\w+\b' -y 'Σέρλοκ Χολμς'
0:0:12:Σέρλοκ
0:13:23:Χολμς

Этот пример должен выглядеть почти идентично примеру с PikeVM. Одно главное отличие в том, что вместо вызова re.find_iter(...) происходит вызов re.try_find_iter(...). Т.е., как упоминалось ранее, движок может вернуть ошибку, если поиск требует больше памяти, чем сконфигурированный лимит. Релевантное значение этого лимита задаётся при помощи Config::visited_capacity. Можно так же узнать по р.в. максимальный размер стога, который можно передать для поиска без возникновения ошибки:

use regex_automata::nfa::thompson::backtrack::BoundedBacktracker;

fn main() {
    let re = BoundedBacktracker::new(r"\b\w+\b").unwrap();
    println!("{:?}", re.max_haystack_len());
}

На момент написания, на моей машине в выводе этой программы фигурировало число 6635. Это выглядит достаточно малым числом, и обусловлено тем, что р.в. на самом деле больше, чем вы могли подумать. А именно, т.к. \w является Юникод-совместимым классом по-умолчанию, и распознаёт около 100 000 различных codepoints. Можно увеличить максимальный размер стога установкой большего значения в Config::visited_capacity, но можно так же его увеличить уменьшением размера нашего р.в., отключив поддержку Юникода:

use regex_automata::nfa::thompson::backtrack::BoundedBacktracker;

fn main() {
    let re = BoundedBacktracker::new(r"(?-u)\b\w+\b").unwrap();
    println!("{:?}", re.max_haystack_len());
}

Теперь в выводе этой программы на моей машине число 233015. Разница почти в два порядка!

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

Движок: Однопроходный ДКА

Прежде, чем обсуждать Однопроходный ДКА, порассуждаем о мотивации существования этого движка более детально. Одним важным аспектом как PikeVM, так и BoundedBacktracker, является то, что они позволяют находить границы групп захвата. Например, воспользуемся PikeVM с помощью regex-cli:

$ regex-cli find capture pikevm --no-table \
   -p '(?<year>[0-9]{4})-(?<month>[0-9]{2})-(?<day>[0-9]{2})' \
   -y '2023-07-02'
0:{ 0: 0..10/2023-07-02, 1/year: 0..4/2023, 2/month: 5..7/07, 3/day: 8..10/02 }

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

use regex::Regex;

fn main() {
    let pat = r"(?<year>[0-9]{4})-(?<month>[0-9]{2})-(?<day>[0-9]{2})";
    let re = Regex::new(pat).unwrap();
    let Some(caps) = re.captures("2023-07-02") else { return };
    println!(" year: {:?}", &caps["year"]);
    println!("month: {:?}", &caps["month"]);
    println!("  day: {:?}", &caps["day"]);
}

Без групп захвата р.в. становятся значительно менее удобными.

Проблема с г.з. в том, что эта концепция не очень вписывается теоретическую модель р.в. и конечных автоматов. (Для этого требуется нечто более выразительная модель, известная как тегированный конечный автомат.) В результате этого г.з. прикручены поверх классического симулятора НКА, в конечном счёте названного PikeVM. Они так же являются частью классического "НКА алгоритма" или бэктрекинга, т.к. найденные границы каждой г.з. могут быть записаны в качестве прогресса поиска с возвратом.

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

Однако, есть один случай, когда мы можем добавить поддержку г.з. в что-то, что выполняется как ДКА: однопроходный ДКА. Можно рассматривать однопроходный ДКА как НКА, который конвертируется в ДКА, в котором каждое состояние соответствует не более, чем одному состоянию НКА. Таким образом, когда выполняется поиск с помощью симуляции НКА, для каждого возможного байта стога существует не более одного состояния, в которое переходит автомат.

Идея для этого случая заключается в том, что нужно хранить только одну копию совпадающих г.з. (В PikeVM нужно хранить до len(regex) копий г.з., т.к. нет возможности заранее узнать, какие из г.з. попадут в окончательное совпадение.) Если удаётся распознать данный случай, то новый ДКА конструируется из НКА за линейное время, и этот ДКА может выполнять поиск таким образом, что обработка каждого символа стога будет выполняться за постоянное количество инструкций ЦПУ.

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

Проблема с однопроходным ДКА в том, что как и обычный ДКА, он использует гораздо больше памяти. (Эту проблему можно обойти, если выделить на конструирование ДКА заранее сконфигурированный фиксированный объём памяти; и если он будет превышен, то операция конструирования завершится ошибкой.) В дополнение ко всему, многие р.в. не являются однопроходными. Например, любой поиск без привязки к началу строки в крейте regex выполняется с добавлением неявного префикса (?s-u:.)*? в начало р.в. Этот префикс сам по себе не является однопроходным, когда за ним следует непустое р.в. Поэтому однопроходный ДКА поддерживает только поиск с позиционными привязками.

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

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

use regex_automata::{dfa::onepass::DFA, Match};

fn main() {
    let re = DFA::new(r"\b\w+\b").unwrap();
    let mut cache = re.create_cache();

    // Однопроходный ДКА не предоставляет никакие API итераторов напрямую,
    //    потому что поддерживает только поиск с начала строки.
    //    Поэтому любой итератор возвращал бы только соседние совпадения.
    //    Такое является валидным юз-кейсом, но эта семантика отличается от
    //    других итераторах в regex-automata
    let Some(m) = re.find(&mut cache, "Σέρλοκ Χολμς") else { return };
    assert_eq!(Match::must(0, 0..12), m);
}

И в виде команды regex-cli:

$ regex-cli find match onepass --no-table --anchored \
   -p '\b\w+\b' \
   -y 'Σέρλοκ Χολμς'
0:0:12:Σέρλοκ

Заметьте, что мы передали флаг --anchored, без которого однопроходный ДКА вернул бы ошибку.

Так же можно выполнять множественный поиск. Даже считая, что р.в. не имеет позиционных привязок, нам не нужно ограничивать себя поиском только в начале стога, по смещению 0:

use regex_automata::{dfa::onepass::DFA, Input, Match};

fn main() {
    let hay = "Σέρλοκ Χολμς";
    let re = DFA::new(r"\b\w+\b").unwrap();
    let mut cache = re.create_cache();

    let Some(m) = re.find(&mut cache, hay) else { return };
    assert_eq!(Match::must(0, 0..12), m);

    let input = Input::new(hay).range(13..);
    let Some(m) = re.find(&mut cache, input) else { return };
    assert_eq!(Match::must(0, 13..23), m);
}

Так же можно использовать абстракцию Input таким же образом с любым другим движком р.в.

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

$ regex-cli find match onepass --no-table --anchored \
   -p '\w+\s+\w+' \
   -y 'Σέρλοκ Χολμς'
failed to compile onepass DFA: one-pass DFA could not be built because pattern is not one-pass: conflicting transition

Но если отключить режим Юникода, тогда р.в. становится однопроходным:

$ regex-cli find match onepass --no-table --anchored \
   -p '(?-u)\w+\s+\w+' \
   -y 'Sherlock Holmes'
0:0:15:Sherlock\x20Holmes

Это произошло по той причине, что когда задействован Юникод, то \w и \s частично перекрываются. Они, конечно же, не перекрываются логически, т.к. пересечение множеств codepoint-ов из \w и \s даёт пустое множество:

$ regex-cli debug hir --no-table '[\w&&\s]'
Class(
    {},
)

Пересечение на самом деле происходит на уровне байт. А переходы в однопроходном ДКА определены через байты. Пересечение означает, что ДКА для выражения \w+\s+\w+ в случае включенного Юникода не удовлетворяет требованию, чтобы каждое состояние в ДКА отображалось не более чем на одно состояние НКА. Т.е. существуют codepoint-ы в \w и \s, которые начинаются с одних и тех же UTF-8 code unit-ов.

Но когда режим Юникода отключен, то не только множества codepoint-ов не перекрываются, но так же нет пересечений на уровне байт. Почему? Потому что codepoint-ы в \w и \s при отключенном Юникоде ограничены codepoint-ами ASCII, и каждый из них всегда кодируется в виде соответствующего одиночного UTF-8 code unit-а.

Из-за скорости следует отдавать предпочтение однопроходному ДКА перед PikeVM и BoundedBacktracker, хотя он конструируется дольше и может использовать больше памяти. Однако же, из-за того, что его можно использовать только для очень ограниченного множества р.в., следует быть готовым к ошибке и переключению на другой движок.

Движок: ДКА

Движок ДКА создаётся из двух уплотнённых ДКА: один отвечает за поиск вперёд, чтобы найти конец совпадения, а второй ДКА отвечает за поиск назад, чтобы найти начало совпадения. (Этот второй ДКА строится переворачиванием конкатенаций в Hir, построением из них НКА, а затем детерминированием этого перевёрнутого НКА в ДКА.) Мы называем эти ДКА "уплотнёнными", чтобы подчеркнуть их отличие от разреженных ДКА. Уплотнённые ДКА используют представление, оптимизированное для скорости поиска за счёт повышенного расхода памяти, в то время, как разреженные ДКА используют представление, оптимизированное для более экономного использование памяти в ущерб скорости поиска.

Полностью компилируемые ДКА обычно не найти в движках р.в. общего назначения, т.к. на их построение в худшем случае уходит O(2^m) времени и памяти, где m пропорционально len(regex). Например, [01]*1[01]{N} компилируется в НКА с приблизительно N состояниями, и т.к. N растёт линейно, то и НКА будет расти линейно. Но соответствующий ДКА имеет приблизительно уже 2^N состояний, и при росте ДКА количество состояний будет расти по экспоненте.

Но проблема с ДКА не ограничивается просто теоретическим поведением в худшем случае. ДКА, в особенности уплотнённые ДКА, имеют склонность к использованию больших объёмов памяти, потому что каждое состояние поддерживает вычисление следующего перехода для любого байта за константное время. Это фундаментально требует больше памяти для предоставления случайного доступа за константное время. А когда вы комбинируете это с большими символьными классами для Юникода, результат может оказаться катастрофическим (disastrous). Для примера сравним размеры для р.в. \w. Сначала НКА (который, как вы помните, можно использовать использовать напрямую в качестве движка р.в. в случае PikeVM и BoundedBacktracker).

$ regex-cli debug thompson '\w' -q
[.. snip ..]
            memory:  17668
[.. snip ..]

Здесь НКА использует 17КБ памяти. Это не так уж мало, но посмотрите что случится, если мы детерминизируем НКА в ДКА:

$ regex-cli debug dense dfa '\w' --start-kind unanchored -q
[.. snip ..]
          memory:  159296
[.. snip ..]

Память распухла до почти 160КБ! (Я ограничил ДКА простым непозиционным ДКА. Если же использовать --start-kind both вместо этого, тогда потребление памяти удвоится). И даже потраченное на минимизацию ДКА время не помогает.

$ regex-cli debug dense dfa '\w' --start-kind unanchored --minimize -q
[.. snip ..]
          memory:  159296
[.. snip ..]

Иногда минимизация помогает, но в этом случае, т.к. мы использовали алгоритм Дацука для построения минимального НКА для UTF-8, то результатом преобразования этого НКА в ДКА и так будет минимально возможный ДКА (и минимизировать его ещё больше крайне затруднительно). Реальная же проблема является следствием уплотнённого представления и того, что наш алфавит определён через байты. Немного лучших результатов можно добиться, если переключиться на разреженное представление:

$ regex-cli debug sparse dfa '\w' --start-kind unanchored -q
[.. snip ..]
          memory:  102257
[.. snip ..]

Но всё ещё больше 100КБ. Символьные классы Юникода и полностью компилируемые ДКА просто плохо сочетаются. И на практике часто бывает так, что компилировать весь символьный класс нет необходимости, т.к. довольно редко приходится искать в текстах с большим разнообразием символов. Более того, большинству поисковых запросов будет вполне достаточно простого ASCII определения \w, которое намного короче.

$ regex-cli debug thompson '(?-u)\w' -q
[.. snip ..]
            memory:  732
[.. snip ..]

$ regex-cli debug dense dfa '(?-u)\w' --start-kind unanchored -q
[.. snip ..]
          memory:  384
[.. snip ..]

В этом случае уплотнённый ДКА на самом деле меньше соответствующего НКА.

Так что с учётом всего выше написанного, зачем движку р.в. общего назначения, такому как крейт regex, вообще нужен движок ДКА с такими огромными недостатками? Разве непомерные аппетиты к памяти не делают его неподходящим? Тут есть два нюанса.

Первый заключается в том, что движок ДКА на самом деле отключен по-умолчанию. Его нужно принудительно включать через perf-dfa-full опцию. Я решил так, потому что полностью компилируемые ДКА не занимают слишком много места в крейте regex, а ленивый ДКА (обсуждаемый далее) является лучшим выбором в большинстве случаев. Однако же, полностью компилируемые ДКА предоставляют некоторые возможности оптимизации, которые сложны для ленивого ДКА, чтобы получить преимущество. Например, в р.в. (?m)^.*$ полностью компилируемый ДКА заметит, что . не будет совпадать с \n. Это можно выяснить просмотром таблицы переходов, где большинство из которых ведут в тоже самое состояние. И следовательно, есть только очень небольшое число возможностей перейти в другое состояние. ДКА находит такие состояния и "ускоряет" их использованием memchr для поиска байт в стоге, которые соответствуют переходу в другое состояние. Это можно увидеть на практике с помощью regex-cli с небольшим бенчмарком. Сперва запустим ускорение состояний ДКА (DFA state acceleration) (оно включено по-умолчанию).

$ regex-cli find match dense -bB -q --repeat 1000000 \
   -p '(?m-u)^.*$' \
   -y 'this is a long line about the quick brown fox that jumped over the lazy dog'
[.. snip ..]
                 search time:  56.600473ms
[.. snip ..]

А теперь отключим эту фичу:

$ regex-cli find match dense -bB -q --repeat 1000000 --no-accelerate \
   -p '(?m-u)^.*$' \
   -y 'this is a long line about the quick brown fox that jumped over the lazy dog'
[.. snip ..]
                 search time:  199.044059ms
[.. snip ..]

Время поиска с включенным ускорением значительно меньше. Так же обратите внимание, что поддержка Юникода отключена. Когда же Юникод включен, . совпадает с любым юникодным скалярным значением. В свою очередь это делает ДКА более сложным и нивелирует ускорение от оптимизации в данном случае:

$ regex-cli find match dense -q --repeat 1000000 \
   -p '(?m)^.*$' \
   -y 'this is a long line about the quick brown fox that jumped over the lazy dog'
[.. snip ..]
                 search time:  204.897593ms
[.. snip ..]

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

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

Вторым аргументом в пользу существования (в крейте) полностью компилируемого ДКА является то, что время поиска в нём крайне мало. Это единственный движок в regex-automata, который не требует мутабельного пространства памяти (Cache) при выполнении поиска. Чтобы убедиться в этом, взглянем на пример:

use regex_automata::{
    dfa::{dense, regex::Regex},
    Match,
};

fn main() {
    let re = Regex::builder()
        // We need to enable heuristic Unicode word boundary support,
        // or else the regex below will fail to compile. Why? Because
        // \b is Unicode-aware by default, and the DFA engines don't
        // support it on haystacks with non-ASCII Unicode codepoints.
        // Enabling this comes with the downside of making it possible
        // for a search to return an error. Namely, when the DFA sees
        // a non-ASCII byte, it transitions to a special sentinel quit
        // state, which in turn causes the search to stop and return an
        // error.
        .dense(dense::Config::new().unicode_word_boundary(true))
        .build(r"\b\w+\b")
        .unwrap();

    // Note that `find_iter` will panic if the underyling search returns
    // an error! You can handle the error by using fallible APIs such as
    // Regex::try_search.
    let mut it = re.find_iter("Sherlock Holmes");
    assert_eq!(Some(Match::must(0, 0..8)), it.next());
    assert_eq!(Some(Match::must(0, 9..15)), it.next());
    assert_eq!(None, it.next());
}

И делаем тоже самое, но командой regex-cli:

$ regex-cli find match dense --no-table --unicode-word-boundary \
   -p '\b\w+\b' \
   -y 'Sherlock Holmes'
0:0:8:Sherlock
0:9:15:Holmes

Заметим, что никакого Cache не требуется. И из-за простоты поискового рантайма ДКА, и из-за того, что его внутреннее устройство проектировалось с оглядкой на это, ДКА можно сериализовать в сырые байты. Тот же ДКА можно десериализовать из них и использовать для поиска в отдельном окружении. При этом не нужны растовские std и alloc, а понадобится только core.

(Сериализация ДКА - это тот юз-кейс, который был одним из мотивов релиза regex-automata 0.1. В данный момент он используется в крейте bstr для реализации некоторых алгоритмов сегментации Юникода.)

Полностью компилируемые ДКА наиболее полезны, когда р.в. не приходится задействовать возможности Юникода или нужен доступ к низкоуровневым API. Например, код ниже демонстрирует ручное вычисление переходов в ДКА:

use regex_automata::{
    dfa::{dense::DFA, Automaton},
    Anchored,
};

fn main() {
    let re = DFA::new(r"\W").unwrap();

    // DFAs can have multiple start states, but only when there are look-around
    // assertions. When there aren't any look-around assertions, as in this
    // case, we can ask for a start state without providing any of the
    // haystack.
    let mut sid = re.universal_start_state(Anchored::No).unwrap();
    // The UTF-8 encoding of ???? is \xF0\x9F\x92\xA9.
    sid = re.next_state(sid, 0xF0);
    sid = re.next_state(sid, 0x9F);
    sid = re.next_state(sid, 0x92);
    sid = re.next_state(sid, 0xA9);
    sid = re.next_eoi_state(sid);
    assert!(re.is_match_state(sid));
}

В этом примере мы обходим ДКА вручную, скармливая ему по одному байту за раз. Этот пример несколько выдуманный, но он показывает которые API вызовы, которые предоставляют низкоуровневый контроль. Ещё больше примеров приведено в документации к трейту Automation, который определяет все низкоуровневые функции ДКА, через которые реализуются разреженные или уплотнённые ДКА.

Движок: Гибрид НКА и ДКА

Гибрид НКА и ДКА, или так называемый "ленивый ДКА" - тоже самое, что и ДКА движок, за исключением того, что таблица переходов строится во время поиска. Другими словами, если полностью компилируемый ДКА является "ahead-of-time compiled", то ленивый - "jist-in-time compiled".

(Называя это JITом, я могу сбить с толку. В данном контексте (касательно р.в.), под JIT обычно понимается компиляция р.в. в машинный код в процессе выполнения (в рантайме), подобно JITу в библиотеке PCRE2. Это не то, что происходит здесь.)

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

use regex_automata::{
    hybrid::{dfa, regex::Regex},
    Match,
};

fn main() {
    let re = Regex::builder()
        // As with the fully compiled DFA, we need to enable heuristic
        // Unicode word boundary support for the lazy DFA as well. It
        // will return an error if a non-ASCII codepoint is seen when
        // the regex contains a Unicode word boundary, just like the
        // full DFA.
        .dfa(dfa::Config::new().unicode_word_boundary(true))
        .build(r"\b\w+\b")
        .unwrap();
    let mut cache = re.create_cache();

    // Note that find_iter will panic if the underyling search returns
    // an error! You can handle the error by using fallible APIs such
    // as Regex::try_search.
    let mut it = re.find_iter(&mut cache, "Sherlock Holmes");
    assert_eq!(Some(Match::must(0, 0..8)), it.next());
    assert_eq!(Some(Match::must(0, 9..15)), it.next());
    assert_eq!(None, it.next());
}

И эквивалент в виде команды regex-cli:

$ regex-cli find match hybrid --no-table --unicode-word-boundary \
   -p '\b\w+\b' \
   -y 'Sherlock Holmes'
0:0:8:Sherlock
0:9:15:Holmes

Этот пример почти идентичен примеру с полностью компилируемым ДКА, кроме параметра Cache. Схожесть распространяется и на низкоуровневые API вызовы:

use regex_automata::{hybrid::dfa::DFA, Input};

fn main() {
    let re = DFA::new(r"\W").unwrap();
    let mut cache = re.create_cache();

    // DFAs can have multiple start states, but only when there are
    // look-around assertions. When there aren't any look-around
    // assertions, as in this case, we can ask for a start state
    // without providing any of the haystack. Full DFAs have a
    // dedicated routine for this because the universality can be
    // checked for us. But lazy DFAs don't compute all of their start
    // states up front. So we just kind of fake it and ask for a start
    // state given some dummy haystack.
    let mut sid = re.start_state_forward(&mut cache, &Input::new("")).unwrap();
    // The UTF-8 encoding of ???? is \xF0\x9F\x92\xA9.
    sid = re.next_state(&mut cache, sid, 0xF0).unwrap();
    sid = re.next_state(&mut cache, sid, 0x9F).unwrap();
    sid = re.next_state(&mut cache, sid, 0x92).unwrap();
    sid = re.next_state(&mut cache, sid, 0xA9).unwrap();
    sid = re.next_eoi_state(&mut cache, sid).unwrap();
    assert!(sid.is_match());
}

Кроме того, что параметр Cache передаётся явным образом, эти вызовы API большей частью одинаковые. Главная разница ещё и в том, что каждая из операций может вернуть ошибку. А именно, в зависимости от метода, возвращается либо MatchError, либо CacheError. MatchError случается, когда невозможно вычислить начальное состояние, потому что автомат перешёл сразу в конечное состояние. (Которое означает, что поиск нужно завершить с ошибкой. Например, это происходит, когда включена поддержка эвристического определения границ слов Юникода (heuristic Unicode word boundary), и при вычислении начального состояния на вход попадает не-ASCII байт.) CacheError случается, когда превышается объём переданного кеша.

На этом моменте стоит поговорить немного больше о кеше, который одновременно является как самой сильной стороной, так и самой большой слабостью. Ленивый ДКА, как упоминалось, функционирует на основе построения таблицы переходов в процессе поиска. Если более подробно, то происходит следующее:

1. Во время инициализации конфигурируется максимальный объём кеша, но аллоцируется не полностью. Это просто число, соответствующее верхней границе того, сколько памяти из кучи можно использовать.

2. Когда вызывающий код запрашивает вычисление перехода для текущего состояния и текущего символа стога, ленивый ДКА смотрит в Cache. Если переход уже был ранее вычислен и сохранён в кеше, то он возвращается "как есть" немедленно. В противном случае, переход - и только этот конкретный переход - вычисляется через детерминирование НКА. В худшем случае этот процесс имеет сложность по времени O(m).

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

4. Опционально можно сконфигурировать ленивый ДКА так, чтобы он возвращал ошибку, если кеш используется неэффективно. Эффективность при этом измеряется в количестве байт стога, в которых происходит поиск, на каждое вычисление состояния ДКА. Если это количество сравнимо с количеством состояний ДКА в кеше, то, вероятнее, даже движок PikeVM будет выполнять поиск быстрее. (Так же используются и другие эвристики, такие как итоговое количество очисток кеша).

Таким образом, не более одного состояния ДКА и не более одного перехода создаётся для каждого байта стога. Поэтому для ленивого ДКА худший случай поиска составляет по времени O(m * n), а по памяти - ограничен объёмом кеша, заданного во время инициализации. И т.к. само построение ленивого ДКА не требует предварительного вычисления каких-либо состояний ДКА (за исключением нескольких базовых состояний), то ленивый ДКА снижает теоретические худшие сложности по времени и памяти, по сравнению с полностью компилируемым ДКА. Т.е. мы избегаем экспоненциальной сложности построения по времени. В общем случае, большинство состояний/переходов кешируются. Т.о. ленивый ДКА в среднем работает за O(n) по времени. На практике, ленивый ДКА и полностью компилируемый ДКА имеют одинаковую производительность поиска.

Так же ленивый ДКА снижает непомерное использование памяти для больших Юникодных символьных классов. Т.к. при этом вычисляется только то, что необходимо, на основе актуальных байт, в которых идёт поиск, то поиск Юникодного \w в стоге, состоящим только из ASCII, требует построения только ASCII-части. В конечном итоге это работает удивительно хорошо на практике.

Ленивый ДКА имеет склонность работать плохо на р.в., которые периодически заполняют кеш и вызывают его очистку. Это может быть результатом того, что р.в. само по себе достаточно большое, или того, что стог состоит из такого набора байт, который вызывает построение очень крупного ДКА. (Р.в. может запросто стать достаточно большим из-за простого указания количества повторений или даже из-за добавления множества шаблонов. Одиночный ленивый ДКА строится для мультишаблонного р.в.) В таких случаях эвристики обычно замечают это и вызывают возврат ошибки. В свою очередь, в контексте мета движка р.в., поиск будет повторен с другим движком р.в. (обычно с PikeVM)

Мета движок

Мета движок р.в. объединяет все вышеперечисленные движки под одним безошибочным API, пытаясь сделать всё возможное в каждой конкретной ситуации. Так же данный API избавляет от необходимости явно создавать и передавать значения Cache при каждом поиске. Движок берёт на себя это, храня значения Cache во внутреннем потокобезопасном пуле. (Движок мета так же предоставляет низкоуровневые вызовы API, которые позволяют передавать значение Cache явным образом. Это полезно, если хочется избежать накладных расходов синхронизации потокобезопасного пула, который используется внутри.)

Конечным результатом является то, что мета движок р.в. очень близко соответствует высокоуровневому API крейта regex. Более того, методы regex::Regex, regex::RegexSet, regex::bytes::Regex и regex::bytes::RegexSet являются лишь небольшими обёртками над мета движком. Так задумано чтобы облегчить переход от высокоуровневых вызовов API, которые покрывают 99% случаев использования, к низкоуровневым вызовам API, которые предоставляют гораздо больше возможностей.

Упрощённо, мета движок внутри реализует следующую логику:

• Если движок р.в. вообще не нужен и поиск можно осуществить используя напрямую алгоритмы поиска одной или множества подстрок, тогда этап построения р.в. (включая НКА) полностью пропускается.

• Если возможно, извлекается литеральная последовательность из префикса р.в., которая используется в качестве Префильтра.

• Если возможно, выбирается "обратная" оптимизация:

  • Если р.в. имеет позиционную привязку к концу строки с помощью $, тогда поиск можно осуществить обратным сканированием стога (от конца к началу). Этот метод называется "обратной якорной" (reverse anchored) оптимизацией.

  • Если в р.в. подходящей для использования в качестве Prefilter последовательности не найдено, но литеральная последовательность может быть извлечена из суффикса р.в., тогда можно осуществить поиск этой последовательности в стоге и проверять совпадение с р.в. в обратном направлении для каждого такого совпадения. Этот метод называется "обратной суффиксной" (reverse suffix) оптимизацией.

  • Если не получилось найти подходящих префиксных и суффиксный литеральных последовательностей, но таковая находится во внутренней части р.в., которая явным образом разделяет его на части, то можно искать в стоге эту последовательность. Мы разделяем р.в. на половины в позициях, в которых была извлечена литеральная последовательность. Первая половина компилируется в обратное р.в. (reverse regex), а вторая - в прямое (forward regex). Когда кандидат найден, мы можем искать начало совпадения, сканируя первую половину в обратном направлении, а затем искать конец совпадения, сканируя вторую половину в прямом направлении (от начала к концу).

• В противном случае мы переходим к "core" стратегии поиска, которая состоит в том, чтобы использовать все доступные движки р.в.: PikeVM, BoundedBacktracker, однопроходный ДКА, ленивый ДКА и полностью компилируемый ДКА. Обязательным является только PikeVM. Эти движки комбинируются следующим образом (упрощённо):

  • Где это возможно, используется ленивый ДКА (или полный ДКА, если доступен) для поиска границ совпадения. Если ДКА возвращает ошибку, то возвращаемся к использованию одного из оставшихся движков (PikeVM, BoundedBacktracker или однопроходного ДКА). ДКА может возвращать ошибку в следующих случаях: р.в. содержит Юникодовскую границу слов, а стог содержит не-ASCII символ; использовался ленивый ДКА и при этом Cache, согласно эвристике, использовался неэффективно.

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

Если подытожить, то можно свести стратегию к двум пунктам:

• Искать литеральные последовательности, где это возможно.

• Избегать использования PikeVM, если это возможно.

Вот и всё. В общем, чем больше времени мы можем потратить на поиск подстрок, тем лучше. И чем меньше времени мы можем потратить непосредственно на работу PikeVM, тем лучше.

Многие движки р.в. производят литеральные оптимизации различного рода. И действительно, самые популярные движки промышленного уровня прикладывают немалые усилия в этом направлении. Гиперскан является здесь золотым стандартом, но, насколько мне известно, большинство других движков р.в. общего назначения не заходят так далеко, как описано выше. (Можно поспорить о том, является ли гиперскан движком р.в. "общего назначения" или нет. Одним из моих личных аргументов против этого является его семантика сопоставлений. Например, \w+ совпадает с abc три раза, потому что гиперскан сообщает о совпадениях по мере продвижения. И, несомненно, это правильный выбор, если учитывать целевую область применения.) Обратные суффиксная и обратная внутренняя оптимизации особенно замудрённые. Они выглядят простыми, но с ними есть проблема в производительности: в худшем случае они приводят к квадратичной сложности (от размера стога).

Рассмотрим р.в. [A-Z].*bcdefghijklmnopq на стоге, в котором bcdefghijklmnopq повторяется снова и снова. Здесь нет "хорошей" префиксной литеральной последовательности, которую можно извлечь. Так что, в соответствие с логикой выше, мета движок попробует использовать "обратную суффиксную" оптимизацию, используя в качестве суффикса bcdefghijklmnopq. Конкретно этот бенчмарк был разработан для наихудшего случая ложно положительных срабатываний: кандидаты встречаются часто, но ни один не приводит к нахождению совпадения. Но это просто плохая эвристика. Само по себе это не приводит к нарушением наших гарантий временной сложности O(m * n). Проблема здесь в том, что каждый раз при совпадении суффикса обратное сканирование включает в себя ещё и .*, и что, в свою очередь, приводит к сканированию стога до его начала. Таким образом, каждый кандидат, найденный по суффиксу, приводит к пересканированию стога в обратном направлении от текущей позиции до его самого начала. Это меняет временную сложность поиска на O(m * n^2). А это плохо.

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

Напротив, мета движок р.в. смягчает это, определяя свои собственные специальные поисковые функции, основанные на движка ДКА. А именно, он определяет функцию поиска, которая останавливает обратное сканирование при достижении определённого смещения в стоге. Это смещение соответствует концу последнего совпадения с суффиксом. Таким образом, если поиск превышает этот смещение, то мы столкнулись с квадратичным поведением. Мета движок определяет этот случай и возвращается к "core" стратегии, описанной выше, жертвуя оптимизацией в пользу соблюдения гарантий сложности по времени.

Примерно та же логика применяется и к оптимизации "reverse inner".

Итак, если вам не нужен низкоуровневый доступ к отдельным движкам р.в., но вы хотите иметь контроль над множеством "крутилок", которые они предоставляют или хотите получить мультишаблонный (multi-pattern) поиск, тогда мета движок является хорошим выбором. Все движки р.в., описанные выше, имеют свои небольшие подводные камни, которые делают их менее идеальными для каждого случая.

Отличия от RE2

Если вы прочитали серию статей Расса Кокса по регулярных выражениям, тогда некоторые части предыдущей главы, вероятно, показались вам знакомыми. А именно, в RE2 есть PikeVM (называемый просто "НКА"), bounded backtracker (называемый "bitstate backtracker"), однопроходный ДКА (называемый "однопроходный НКА") и ленивый ДКА. Там так же есть мета движок р.в. (хотя сам термин не используется), который комбинирует свои внутренние движки р.в. в похожей манере, как описывалось выше. Единственным движком, описанным выше, но которого нет в RE2, является полностью компилируемый ДКА.

Так что, есть ли отличия между RE2 и крейтом regex?

The similarities between them are much greater than the differences, but here’s a high level list of differences:

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

• RE2 опционально поддерживает leftmost-longest семантику в дополнение к семантике leftmost-first. Leftmost-longest семантика - это то, что используют движки р.в. POSIX.

• В RE2 меньше поддержки Юникода. Полностью учесть всё это сложно, потому что RE2 разрешает линковку с ICU, чтобы добавить больше свойств Юникода. Однако, RE2 не позволяет определить \w, \s, \d и \b через Юникод. RE2 так же не поддерживает операции с символьными классами, кроме операции объединения. Например, достаточно трудно сделать в RE2 что-то вроде [\pL&&\p{Greek}], которое соответствует подмножеству символов (codepoints), которые так же являются символами греческого алфавита. (Строго говоря, операции с множествами символьных классов, за исключением объединения, не являются Юникодоспецифическими, но они наиболее полезны именно в контексте больших Юникодных символьных классов.)

• В RE2 версии PikeVM, вероятно, более эффективная работа с памятью.

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

• В RE2 используется единый кеш переходов для всех потоков в случае использования ленивого ДКА, что требует синхронизации. В крейте regex требуется отдельный кеш для каждого потока, что требует больше памяти.

• Крейт regex в данный момент предоставляет regex-syntax и regex-automata в виде отдельно версионированных библиотек, обеспечивая доступ к своим внутренним механизмам. RE2 такого не поддерживает.

• Библиотека regex-automata имеет первоклассную поддержку мультишаблонных р.в. во всех движках. В RE2 есть функциональность в виде "regex set", но она сообщает только о том, какие из шаблонов были обнаружены в стоге. regex-automata, в свою очередь, может так же передавать информацию о том, с чем именно совпало р.в., а так же о смещениях групп захвата для каждого шаблона.

В будущем, надеюсь, я добавлю больше движков в regex-automata. Особенно, мне бы хотелось исследовать НКА Глушкова и параллельного-битового (a bit parallel) движка р.в. Так же хотелось бы исследовать сдвиговые ДКА (shift DFAs).

Стратегия тестирования

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

Моя идея изменить то, каким образом производится тестирование крейта regex, была связана с идеей, что у каждого внутреннего движка был бы свой первоклассный API, через который движок можно было бы тестировать независимо от "главного" движка. Я так же хотел скармливать тесты из любого контекста, а не закапывать их среди макросов или исходного кода. Так что в итоге я остановился на следующем:

• Все тесты располагаются внутри TOML файлов

• Я опубликовал крейт regex-test, который знает, как прочитать эти TOML файлы в виде структурированного представления.

• Я определил единственный юнит-тест на Rust для каждой конфигурации каждого движка р.в., который хотел протестировать. Внутри этого юнит-теста исполняются все тесты из TOML файлов, применимые к тестируемому движку.

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

Есть так же куча других типов тестов. Например, только в regex-automata существует более 450 тестов внутри документации.

Наконец, перед выпуском regex 1.9, я добавил множество дополнительных фуз-тестов. Я получил тонну помощи от Эдисона Крампа (Addison Crump). И было несколько багов, которые я не нашёл бы, если бы не он.

Бенчмаркинг

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

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

Среди 242 замеров, крейт regex 1.9 в среднем в 1.5 раза быстрее, чем regex 1.7.3 по времени поиска. (Я сравнивал с 1.7, а не с 1.8 по той причине, что 1.8 является переходным выпуском, в котором уже имеются наработки, описанные в данной статье. А выпуск 1.9 просто завершил переход.)

$ rebar rank record/all/2023-07-02/*.csv \
   --intersection \
   -M compile \
   -e '^(rust/regex|rust/regexold)$'
Engine         Version  Geometric mean of speed ratios  Benchmark count
------         -------  ------------------------------  ---------------
rust/regex     1.8.4    1.08                            242
rust/regexold  1.7.3    2.61                            242

Но время, необходимое для построения р.в. ухудшилось:

$ rebar rank record/all/2023-07-02/*.csv \
   --intersection \
   -m compile \
   -e '^(rust/regex|rust/regexold)$'
Engine         Version  Geometric mean of speed ratios  Benchmark count
------         -------  ------------------------------  ---------------
rust/regexold  1.7.3    1.07                            28
rust/regex     1.8.4    1.46                            28

Среднее геометрическое, указанное выше, является очень грубой агрегированной метрикой. Я не уверен, что она отражает все улучшения, описанные здесь. Если хочется посмотреть на отдельные замеры и их разницу, можно в команде выше заменить rebar rank на rebar cmp. (И запустить эту команду в корне репозитория rebar после переключения на заданную версию (checkout).)

$ rebar cmp record/all/2023-07-02/*.csv \
   --threshold-min 2 \
   --intersection \
   -M compile \
   -e '^(rust/regex|rust/regexold)$'

Я добавил опцию --threshold-min 2 в команду, чтобы ограничить сравнение только там, где разница превышает 2x.

Цена вопроса

Ни одно доброе дело не остаётся безнаказанным. Так чего же мне стоило переписать всё это?

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

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

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

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

1. Как обсуждалось ранее, я сделал движок полностью компилируемого ДКА опциональным. Этот движок привносит достаточно много кода, а влияние на время поиска не такое радикальное.

2. Я опубликовал новый крейт regex-lite, который выступает в роли почти полной замены крейта regex. Его дизайн основан на оптимизациях почти исключительно ради размера бинарника и времени компиляции в ущерб функциональности (а именно, касательно поддержки Юникода) и производительности. Вы всё ещё получаете гарантию временной сложности в O(m * n), но без пижонской поддержки Юникода и быстрого времени поиска. Но вот размер бинарника и время компиляции гораздо меньше. У regex-lite нет зависимостей (zero dependencies). У него нет общего кода с крейтом regex (включая собственный парсер р.в.).

regex-lite всё ещё что-то вроде эксперимента, но он призван продемонстрировать сложность уменьшения размера кода. Даже несмотря на то, что крейт regex имеет целый ворох возможностей для отключения как оптимизаций, так и Юникод-функциональности, он всё ещё не может приблизиться к размеру бинарника и времени компиляции крейта regex-lite.

Заключение

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

Любые вопросы я рекомендую задавать в соответствующем разделе GitHub Discussions.