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

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