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

Если внутри крейта 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-конструкций, но есть и некоторые потенциально приятные выгоды.