xref: /dports/devel/pire/pire-release-0.0.6/README.ru

ЧТО ЭТО
=======

Pire (Perl Incompatible Regular Expressions) — это библиотека,
заточенная на быструю проверку текста большим количеством регулярных
выражений. Она умеет проверять, матчится ли текст паттерну, но умеет
делать это действительно быстро (400 Мб/с вне зависимости от сложности
регулярки). Если же паттернов более одного, их можно объединять,
выполняя за один проход проверку примерно десятью паттернами (с той же скоростью).

Pire может давать гарантии на скорость работы (на нижнем уровне она
просматривает входную строку один раз, подряд, без откатов, и тратит
(на x86 и x86_64) по 5 инструкций на символ), так что в принципе
может использоваться в realtime-задачах.

Расплачиваться за такую скорость приходится ограниченной функциональностью.
В pire нету сложных перловых конструкций типа условных регулярок,
backtracking-а, lookahead-а. Кроме того, pire вообще не занимается
захватом фрагментов сматчившегося текста (хотя в ограниченном варианте
такой захват можно реализовать, см.ниже).

Вся теория, которая делает такую скорость возможной, описана в the Dragon Book,
настоятельно рекомендуемой для изучения.

Pire была разработана в компании Яндекс (изначально как часть робота, но
в итоге развилась в самостоятельный проект).


БЫСТРЫЙ СТАРТ
=============

#include <stdio.h>
#include <vector>
#include <pire/pire.h>

Pire::Scanner CompileRegexp(const char* pattern)
{
	// Переводим шаблон в UCS4
	std::vector<Pire::wchar32> ucs4;
	Pire::Encodings::Utf8().FromLocal(pattern, pattern + strlen(pattern), std::back_inserter(ucs4));
	// или другая кодировка

	return Pire::Lexer(ucs4.begin(), ucs4.end())
		.AddFeature(Pire::Features::CaseInsensitive())	// если хочется нечувствительность к регистру
		.SetEncoding(Pire::Encodings::Utf8())		// Устанавливаем кодировку, в которой будет приходить проверяемый текст
		.Parse() 					// Разбираем шаблон
		.Surround()					// если мы не хотим логику PCRE_ANCHORED
		.Compile<Pire::Scanner>();			// Компилируем регулярку
}

bool Matches(const Pire::Scanner& scanner, const char* ptr, size_t len)
{
	return Pire::Runner(scanner)
		.Begin()	// Начало строки
		.Run(ptr, len)	// Строка
		.End();		// Конец строки
		// Оно неявно кастится к bool
}

int main()
{
	char re[] = "hello\\s+w.+d$";
	char str[] = "Hello world";

	Pire::Scanner sc = CompileRegexp(re);

	bool res = Matches(sc, str, strlen(str));

	printf("String \"%s\" %s \"%s\"\n", str, (res ? "matches" : "doesn't match"), re);

	return 0;
}


КАК ВЫЗЫВАТЬ MATCH
==================

Скомпилированная регулярка хранится в сканере (т.е. конечном автомате, представленом
в виде, оптимизированном для прохода по строке). В Pire есть несколько сканеров
(как минимум Scanner, SlowScanner и SimpleScanner), работа с ними во многом совпадает.

У каждого сканера есть тип State, хранящий состояние автомата, и методы
Initialize(State&), отдающий начальное состояние автомата, Next(State&, char),
переводящий автомат в следующее состояние и Final(const State&), сообщающий,
является ли данное состояние допускающим. Соответственно, чтобы проверить
строчку на соответствие паттерну, необходимо вызвать Initialize(), Next()
на каждую букву, и Final(), чтобы проверить, соответствует ли строчка паттерну.

Существует метод Pire::Run(const Scanner&, Scanner::State&, const char* begin,
const char* end), осуществляющий соптимизированный вызов Scanner::Next() на
каждый символ диапазона.

В паттерне могут попадаться символы начала и конца строки (^ и $). При компиляции
они заменяются специальными символьными символами (sentinels) — BeginMark и EndMark.

Если одну и ту же строчку требуется прогнать через два сканера, то можно воспользоваться
специальной функцией Pire::Run(const Scanner1&, const Scanner2&, Scanner1::State&,
Scanner2::State&, const char* begin, const char* end), которая работает несколько
быстрее, чем два последовательных вызова обычной Run().

Наконец, есть специальный класс RunHelper, облегчающий работу с циклом
Initialize-Step-Run-Step-Final и позволяющий записать его в виде одного выражения (см.пример).

Существуют ещё четыре функции, полезные при организации лексического разбора:
LongestPrefix(), LongestSuffix(), ShortestPrefix() и ShortestSuffix(). Они возвращают
наибольший/наименьший префикс/суффикс строки, допускаемый паттерном. Для использования
в LongestSuffix() и ShortestSuffix() автомат надо предварительно «вывернуть наизнанку»
(при помощи Fsm::Reverse()).


СКЛЕЙКА СКАНЕРОВ
================

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

Сканеры объединяются функцией Pire::Scanner::Glue(). В результате получается сканер,
который за один проход проверяет строку на соответствие всем содержащимся в нём
паттернам. Общее количество паттернов возвращает Scanner::RegexpsCount(). Вместо
Final() имеет смысл вызвать AcceptedRegexps(const State&), возвращающая пару
итераторов (с семантикой [begin,end)), указывающую на диапазон номеров регулярок,
которым соответствует прочитанная строка.

Номера начинаются с нуля, при склейке двух сканеров все номера правого сдвигаются на
количество регулярок в левом.

Склеенные сканеры в свою очередь можно склеить между собой. В то же время процесс склейки
нельзя повторять до бесконечности, потому как количество состояний в полученном автомате
растёт экспоненциально с каждым добавленным паттерном. Иногда имеет смысл ограничить
размер полученного автомата, указав ненулевой параметр maxSize в Glue(). В таком случае
при превышении указанного размера возвращается пустой автомат (Size() == 0, Empty() == true).


РАЗБОР РЕГУЛЯРНОГО ВЫРАЖЕНИЯ
============================

До сих пор речь велась о том, как гонять по тексту уже готовый сканер,
но не говорилось о том, откуда этот сканер взять. Самый простой способ получить
сканер — это сконструировать его из строки, содержащей регулярное выражение,
воспользовавшись классом Pire::Lexer.

Строка, задающая регулярное выражение, имеет стандартный синтаксис, похожий
на POSIX regexps. Поддерживаются стандартные возможности (a|b, a*, a+, ., [a-z],
a{3}, a{3,5}, a{3,}) и классы символов (\w (буква), \W (не буква), \d (цифра),
\D (не цифра), \s (whitespace), \S (не whitespace)). Кроме того, могут быть добавлены
операции a&b (пересечение, см. Fsm::operator &) и ~a (инверсия, см. Fsm::Complement).
Помимо этого, для Fsm::SlowCapturingScanner есть возможность использовать нежадные аналоги
повторений - операторы *?, +?, ??. В этом сканере данные операторы будут принимать
как можно более короткие выражения, в отличие от жадных аналогов (которые, наоборот, принимают
как можно более длинные.

Lexer принимает регулярку в кодировке UCS-4, как диапазон из wchar32 (или любых других
типов, неявно преобразовывающихся к wchar32). Таким образом, если регулярное выражение
задано как const char* regexp и все символы в ней есть в latin-1, можно просто вызвать
lexer.Assign(regexp, regexp + strlen(regexp)), но если оно задано в UTF-8 или KOI8-R —-
то его для начала нужно явно перевести в UCS-4.

lexer.SetEncoding() указывает кодировку, в которой будут поступать строки для
сопоставления с выражением (ещё раз: она не указывает кодировку самого регулярного
выражения!). Это необходимо, поскольку сканер работает уже не на уровне символов,
а на уровне байтов, а, скажем, точка (один любой символ) в UTF-8 —- это весьма
нетривиальная конструкция.

Тонкая настройка лексера возможна посредством добавления туда «фич» (Pire::Feature),
которые можно добавлять к лексеру вызовами lexer.AddFeature(). Скажем,
нечувствительность к регистру реализована фичей Pire::CaseInsensitive.

После настройки лексера следует вызвать lexer.Parse(), который вернёт разобранный
конечный автомат (Pire::Fsm). Его можно скомпилировать в сканер, вызвав
Fsm::Compile<Pire::Scanner>().

Иногда шаблон регулярки оказывается слишком сложным, чтобы его можно было скомпилировать
в детерминированный автомат разумного размера. В этом случае Fsm::Compile() раскрутит
исключение. Если хочется обрабатывать такую ситуацию, может иметь смысл явно
вызвать Fsm::Determine(size_t maxSize) и, если он возвратил false, не пытаться
компилировать автомат в Pire::Scanner, а ограничиться Pire::SlowScanner-ом (см. далее).


РУЧНОЕ ПОСТРОЕНИЕ АВТОМАТА
==========================

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

    * Конструктор по умолчанию — создаёт автомат, допускающий пустую строку.
    * MakeFalse() — создаёт автомат, не допускающий ни одной строки.
    * Size() — размер автомата (количество состояний).
    * Append(unsigned char c) — добавляет в автомат переход для матча символа c.
    * AppendStrings(const vector<string>&) — добавляет в автомат переходы для
      матча хотя бы одной из переданных строк.
    * operator + (const Fsm&) — возвращает конкатенацию автоматов (допускающую
      строки, делящиеся на две части так, что первая допускается первым автоматом,
      а вторая — вторым).
    * operator | (const Fsm&) — возвращает объединение (union) авмоматов (допускающее
      строки, допускаемые хотя бы одним автоматом).
    * operator * () — возвращает итерацию автоматов (допускающую строки,
      представляющие собой повторение строки, допускаемой исходным автоматом,
      0 или более раз (т.н. звезда Клини)).
    * operator ~ () — возвращает инверсию автомата (допускающего строки, которые
      не допускаются исходным автоматом).
    * operator & (const Fsm&) — возвращает пересечение автоматов (допускающее строки,
      которые допускаются обоими автоматами).
    * operator * (size_t n) — возвращает автомат, допускающий строки, представляющие
      собой повторение строки, допускаемой исходным автоматом, ровно n раз.
    * Surrounded() — возвращает автомат, допускающий любые строки, содержащие в себе
      строку, допускаемую исходным автоматом (т.е. добавляет в начало и в конец по /.*/).
    * operator +=, operator |=, Iterate, Complement, operator &=, operator *=, и
      Surround, двойственные к семи выше описанным.
    * Reverse() — возвращает автомат, допускающий строки, являющиеся зеркальным
      обращением строк, допускаемых исходным автоматом.

Возможно комбинированное построение автомата (например,
(lexer1.Parse() | lexer2.Parse()).Compile<Scanner>()). Таким образом возможно, например,
прочитать из файла список паттернов, скомпилировать их в Fsm'ы и объединить их все
в один большой Fsm, который скомпилировать в сканер.


СКАНЕРЫ
=======

В Pire существует три сканера: Scanner, SimpleScanner и SlowScanner.

    * Scanner — это основная рабочая лошадка всего Pire. До сих пор речь велась именно о нём.
    * SimpleScanner — это более простая версия сканера, пригодная для проверки
      текста одной несложной регуляркой. Она не поддерживает склейки автоматов,
      и её таблица переходов несколько больше, чем в Scanner-е, зато SimpleScanner
      работает приблизительно на треть быстрее.
    * SlowScanner — работает крайне медленно, но не требует детерминизации автомата и,
      таким образом, может использоваться при матче сложных конструкций типа /x.{50}$/,
      которые не могут быть скомпилированы в Scanner.

Нужный тип сканера может быть получен вызовом нужной специализации метода Fsm::Compile()
(или явным конструированием нужного сканера из Fsm-а).


КОДИРОВКИ
=========

«Из коробки» Pire поддерживает кодировки Latin-1 и UTF-8. Нужные экземпляры классов
Pire::Encoding могут быть получены вызовами соотвествующих функций из namespace Pire::Encodings.

При желании можно добавить поддержку других кодировок, понаследовавшись от Pire::Encoding.
В наследованном классе следует переопределить методы:

    * wchar32 FromLocal(const char*& begin, const char* end) — читает и возвращает очередной
      символ входного потока, продвигает begin. В случае невалидной последовательности
      на входе кидает исключение.
    * std::string ToLocal(wchar32) — возвращает байтовое представление символа в данной
      кодировке. Если символ в данной кодировке непредставим, возвращает пустую строку.
    * AppendDot(Fsm&) — добавляет к конечному автомату фрагмент, допускающий один любой
      символ в данной кодировке.

После этого экземпляр такого класса можно передать в lexer.SetEncoding() наравне со встроенными.


СЕРИАЛИЗАЦИЯ, MMAP() И INLINING
===============================

Построенные сканеры могут быть сохранены в std::ostream или загружены из std::istream
путем вызова Scanner::Save() и Scanner::Load() (аналогично для других сканеров).

Если сканер был сохранен в файл, а файл потом при-mmap()-лен в память, то вместо вызова
Scanner::Load() можно воспользоваться Scanner::Mmap(), который не будет выполняеть
копирования таблицы переходов (которая может быть очень большой). Mmap() возвращает
указатель на первый байт после сериализованного представления регулярки.

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

Сериализованное представление сканера непереносимо между архитектурами (даже между x86 и x86_64).
При попытке прочитать/приммапить регулярку, сериализованную на другой архитектуре, будет exception.

Если же в коде есть необходимость использовать одно и то же заранее определённое регулярное
выражение, то можно, конечно, написать static const Scanner = Pire::Lexer(«...»).Parse().Compile(),
но в таком варианте компиляция выражения будет происходить при каждом запуске программы,
что может быть достаточно неприятным, особенно если шаблон достаточно сложный. Чтобы
избежать таких задержек, выражение можно скомпилировать в сканер, сериализовать его,
подставить сериализованное представление в код в виде строкового литерала, а затем вызвать
на нём Scanner::Mmap(). Всё это делает программа pire_inline, которая принимает на вход файл
с кодом на C++, ищет там все вхождения PIRE_REGEXP("pattern", "flags") вне комментариев и строк
и заменяет их на выражение, возвращающее автомат с готовой предвычисленной таблицей переходов.

В строчке с флагами могут находиться следующие символы:

    * i — нечувствительность к регистру;
    * u — скомпилировать регулярку в UTF-8;
    * s — обрамить регулярку .* с каждой стороны;
    * a — включить поддержку операторов & и ~ в регулярках (см.выше);
    * g — выполнить преобразование fsm = ~fsm.Surrounded() + fsm (для нужд Scan()).


РАСШИРЕНИЯ PIRE
===============

Если требуется какая-нибудь функциональность, в Pire отсутствующая, есть вероятность,
что её можно реализовать, воспользовавшись существующими в Pire точками расширения
или спустившись на уровень ниже (возможно, до этого стоит прочитать Dragon Book).


** ЕЩЕ РАЗ ПРО FSM

Fsm — это конечный автомат с выходом. Соответственно, в нём есть множество состояний
(пронумерованных целыми числами от 0 до Fsm::Size() – 1), для каждого состояния и
каждой буквы задано множество состояний, в которые по этой букве из этого состояния
можно перейти (возможно, это множество пусто), одно состояние объявлено начальным,
а часть состояний отмечены допускающими.

Для манипуляции этими данными у Fsm есть функции:

    * Size(), Resize();
    * Destinations(), Connected(), Connect();
    * Initial(), SetInitial();
    * Finals(), IsFinal(), SetFinal(), ClearFinal().

Кроме того, с каждым состоянием и каждым переходом автомата может быть ассоциировано
битовое поле флагов. Флаги переходов называются выходами (outputs, поскольку реализуют
классический КА с выходом), для работы с ними предназначены функции Output(),
SetOutput() и ClearOutputs(). Флаги состояний называются тегами и поддерживаются
функциями Tag() и SetTag().

При детерминизации или ином объединении состояний все флаги объединяются побитовым ИЛИ.

Ещё ряд функций не принадлежит никакой группе:

    * Divert(size_t from, size_t to, size_t dest) — разрывает все переходы из `from' в `to'
      и перенаправляет их в состояние dest. Все флаги, которыми были помечены переходы,
      переносятся на новые переходы.
    * Import(const Fsm&) — копирует внешний автомат внутрь данного. Все его состояния
      сдвигаются на количество состояний в данном. Сами состояния никак не подсоединяются.
    * DeadStates() — возвращает набор состояний, из которых недостижимо ни одно из допускающих
      состояний.
    * RemoveEpsilons() — ликивдирует в автомате все epsilon-переходы (переходы из одного
      состояния в другое по пустой строке).


** ЕЩЕ РАЗ ПРО LEXER И FEATURE

Основная функция Lexer-а — это разбирать входную строку на последовательность
термов (Pire::Term).

Feature — это возможность изменить поведение лексера. У фичи есть три основные
возможности:

    * Обработать фрагмент паттерна каким-либо своим способом, вернув терм
      (функции Accepts() и Lex());
    * Изменить уже выделенный терм (Alter());
    * Изменить выделенный фрагмент конечного автомата, заключенный
      в круглые скобки (Parenthesized()).

Если фича разбирает фрагмент паттерна, то она должна реализовывать функцию
Accepts(wchar32), которая возвращает true, если передаваемый символ является
началом последовательности символов, воспринимаемой фичей, и функцию Lex(),
которая собственно и осуществляет лексический разбор (если Accepts() вернула
false, Lex() вызвана не будет). Внутри фичи доступны стандартные функции
работы с входным потоком: GetChar(), PeekChar() и UngetChar(). Если
Accepts() вернула true, а уже внутри Lex()-а стало понятно, что последовательность
не подходит, можно положить её всю обратно посредством UngetChar(), а затем
вернуть пустой Term(), показав тем самым лексеру, что фича отказалась
обрабатывать поток.

В лексере может быть несколько фич, они отсортированы по приоритету и объединены
в цепочку. Lex() и Accepts() вызываются от большего приоритета к меньшему
до тех пор, пока какая-нибудь фича не обработает входной поток с получением
терма. Этот терм пропускается в обратном порядке через Feature::Alter().

При чтении закрывающей круглой скобки фрагмент автомата, соовтетствующий
находящемуся в скобках фрагменту регулярки, прогоняется через
Feature::Parenthesized(), опять-таки в порядке возрастания приоритетов.

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


** ПРИМЕР: CapturingScanner

Скажем, нам нужен ограниченный захват одного фрагмента в тексте (например, матчить текст
шаблону /id\s*=\s*['"]([a-z0–9]+)['"]/ и извлекать собственно ID).

    * Заводим два флага для переходов: BeginCapture и EndCapture.
    * Пишем фичу, в которой отслеживаем все скобки. Lex() возвращает собственно
      скобку и при этом отсчитывает нужную скобку по порядку.
    * После того, как нужная закрывающая скобка найдена, в Parenthesized() фича получает
      автомат, который матчит то, что в скобках. Расширяем этот автомат на два состояния,
      переносим делаем новым начальным состоянием предпоследнее, единственным допускающим —-
      последнее, и соединяем их со старым начальным и допускающими состояниями
      epsilon-переходами. Эти переходы отмечаем соответственно флагами
      BeginCapture и EndCapture.
    * Пишем собственный сканер, который при переходе, отмеченном BeginCapure или EndCapture,
      отмечает соответствующую позицию во входном потоке.

Пример, где всё это реализовано, находится в extra/capture.h и extra/capture.cpp.