Intermediate changes

commit_hash:de861c421a4d799c8ac2ece7a8542f74dd5fa180

1 files changed, 213 insertions, 0 deletions

diff --git a/library/cpp/regex/pire/README.md b/library/cpp/regex/pire/README.md
new file mode 100644
index 00000000000..69418fbbbaa
--- /dev/null
+++ b/library/cpp/regex/pire/README.md
@@ -0,0 +1,213 @@
+## Что это
+Pire (Perl Incompatible Regular Expressions) -- это библиотека, заточенная на быструю проверку текста большим количеством регулярных выражений. Она умеет проверять, матчится ли текст паттерну, но умеет делать это действительно быстро (350 Мб/с вне зависимости от сложности регулярки). Если же паттернов более одного, их можно объединять, выполняя за один проход проверку примерно десятью паттернами (с той же скоростью).
+
+Pire может давать гарантии на скорость работы (на нижнем уровне она просматривает входную строку один раз, подряд, без откатов, и тратит (на x86 и x86_64) по 5 инструкций на символ), так что в принципе может использоваться в realtime-задачах.
+
+Расплачиваться за такую скорость приходится ограниченной функциональностью. В pire нету сложных перловых конструкций типа условных регулярок, backtracking-а, lookahead-а. Кроме того, pire вообще не занимается захватом фрагментов сматчившегося текста (хотя в ограниченном варианте такой захват можно реализовать, см.ниже).
+
+Вся теория, которая делает такую скорость возможной, описана в the Dragon Book, настоятельно рекомендуемой для изучения.
+
+
+
+## Fast start
+
+
+```cpp
+Pire::Scanner CompileRegexp(const char* pattern)
+{
+    // Переводим шаблон в UCS4
+    std::vector<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
+}
+```
+
+
+
+## Как вызывать 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 `).
+
+Класс ` 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 `. Внутри Аркадии -- ещё и ` KOI8-R ` и ` Windows-1251 `. Нужные экземпляры классов ` 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 ` (для Аркадии -- ` TOutputStream ` и ` TInputStream ` соответственно) путем вызова ` 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() `).
+   - r -- выполнить ` fsm.Reverse() ` (для нужд ` LongestSuffix() ` / ` ShortestSuffix() `).
+
+
+
+## Расширения Pire
+
+Если вам нужна какая-нибудь функциональность, в Pire отсутствующая, есть вероятность, что её можно реализовать, воспользовавшись существующими в Pire точками расширения или спустившись на уровень ниже.
+
+
+
+### Ещё раз про 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
+Скажем, нам нужен ограниченный захват одного фрагмента в тексте (например, матчить текст шаблону ` /adv_id\s*=\s*['"]([a-z0-9]+)['"]/ ` и извлекать собственно ID).
+   - Заводим два флага для переходов: ` BeginCapture ` и ` EndCapture `\.
+   - Пишем фичу, в которой отслеживаем все скобки. ` Lex() ` возвращает собственно скобку и при этом отсчитывает нужную скобку по порядку.
+   - После того, как нужная закрывающая скобка найдена, в ` Parenthesized() ` фича получает автомат, который матчит то, что в скобках. Расширяем этот автомат на два состояния, переносим делаем новым начальным состоянием предпоследнее, единственным допускающим -- последнее, и соединяем их со старым начальным и допускающими состояниями epsilon-переходами. Эти переходы отмечаем соответственно флагами ` BeginCapture ` и ` EndCapture `\.
+   - Пишем собственный сканер, который при переходе, отмеченном ` BeginCapure ` или ` EndCapture `, отмечает соответствующую позицию во входном потоке.
+      Пример, где всё это реализовано, находится в ` extra/capture.h ` и ` extra/capture.cpp `\.
+