Содержание

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

• Проблемы

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

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

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

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

• По пути с regex-cli

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

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

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

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

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

По пути с 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. На высоком уровне он использует векторные инструкции для быстрого обнаружения кандидатов, а затем проверяем их для подтверждения совпадения.

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

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