perlreguts

СОДЕРЖАНИЕ

• ИМЯ
• ОПИСАНИЕ
• ОБЗОР
  • Краткое примечание о терминах
  • Что такое движок регулярных выражений?
  • Структура программы регулярных выражений
    • Высокий уровень
    • Операции
    • Какой узел regnode следует за ним?
• Обзор процесса
  • Компиляция
    • Разбор графа вызовов и грамматики
    • Сложности разбора
    • Вывод отладки
    • Оптимизация и анализ "дырочного" просмотра
  • Выполнение
    • Оптимизация начальной позиции и отсутствия совпадений
    • Выполнение программы
• РАЗНОЕ
  • Поддержка Юникода и локализации
  • Базовые структуры
    • Структура pprivate Perl
• СМОТРИТЕ ТАКЖЕ
• АВТОР
• ЛИЦЕНЗИЯ
• СПИСОК ЛИТЕРАТУРЫ

ИМЯ

perlreguts - Описание движка регулярных выражений Perl.

ОПИСАНИЕ

Данный документ призван пролить свет на внутренности движка регулярных выражений и его работу. Движок регулярных выражений представляет собой значительную часть кодовой базы perl, но относительно плохо изучен. Данный документ является скромной попыткой решить эту проблему. Он основан на опыте автора, комментариях в исходном коде, других статьях о движке регулярных выражений, отзывах на почтовом списке perl5-porters и, несомненно, на других источниках.

ПРИМЕЧАНИЕ! Следует четко понимать, что поведение и структуры, обсуждаемые в данном документе, отражают состояние движка на момент написания, как автор его понимал. Это НЕ определение API, а чисто справочник по внутреннему устройству для тех, кто хочет модифицировать движок регулярных выражений или понять, как он работает. От читателей данного документа ожидается знание синтаксиса регулярных выражений Perl и их использования в деталях. Если вы хотите узнать основы регулярных выражений Perl, см. perlre. А если вы хотите заменить движок регулярных выражений собственным, см. perlreapi.

ОБЗОР

Краткое примечание о терминах

Существует некоторая дискуссия о том, следует ли говорить "regexp" или "regex". В данном документе мы будем использовать термин "regex", если нет специальной причины этого не делать, в противном случае мы объясним почему.

Когда речь идёт о regex, нам нужно различать их исходную форму кода и внутреннюю форму. В этом документе мы будем использовать термин "шаблон", когда говорим о текстовой форме исходного кода, и термин "программа", когда говорим о внутренней форме представления. Эти термины соответствуют терминам S-regex и B-regex, которые использует Марк Джейсон Доминус в своей статье о "Rx" ([1] в "СПИСКЕ ЛИТЕРАТУРЫ").

Что такое движок регулярных выражений?

Движок регулярных выражений — это программа, которая принимает набор ограничений, заданных на мини-языке, а затем применяет эти ограничения к целевой строке и определяет, удовлетворяет ли эта строка ограничениям. См. perlre для полного определения языка.

Говоря менее величественно, первая часть задачи заключается в преобразовании шаблона во что-то, что компьютер может эффективно использовать для поиска точки совпадения в строке, а вторая часть — это сам поиск.

Для этого нам нужно создать программу путём разбора текста. Затем нам нужно выполнить программу, чтобы найти точку в строке, которая совпадает. И нам нужно сделать всё эффективно.

Структура программы регулярных выражений

Высокий уровень

Хотя это немного запутанно, и некоторые люди возражают против терминологии, стоит взглянуть на комментарий, который присутствует в regexp.h уже много лет:

Это по существу линейное кодирование недетерминированной конечной автомата (сокращённо КФА) (также известной как диаграммы синтаксиса или "нормальная форма железной дороги" в технологии разбора).

Термин "нормальная форма железной дороги" немного экзотический, "диаграмма/таблица синтаксиса" или "диаграмма/таблица железной дороги" являются более распространёнными терминами. Тем не менее, он даёт полезное наглядное представление о программе regex: каждый узел можно рассматривать как единицу пути, с единственным входом и, в большинстве случаев, единственным выходом (есть части пути, которые расходятся, но статистически не много), и всё это образует макет с единственной точкой входа и единственной точкой выхода. Процесс сопоставления можно представить как автомобиль, который движется по пути, причём конкретный маршрут по системе определяется символом, считанным в каждой точке соединения. Автомобиль может сойти с пути в любой момент, но он может продолжать движение только в том случае, если он соответствует пути.

Таким образом, шаблон /foo(?:\w+|\d+|\s+)bar/ можно рассматривать как следующую диаграмму:

     [start]
        |
      <foo>
        |
  +-----+-----+
  |     |     |
<\w+> <\d+> <\s+>
  |     |     |
  +-----+-----+
        |
      <bar>
        |
      [end]

На самом деле, регулярные выражения Perl в наши дни намного сложнее, чем эта структура, но визуализация её таким образом может помочь при попытке сориентироваться, и она довольно точно соответствует текущей реализации.

Более точно, мы скажем, что программа regex — это кодирование графа. Каждый узел в графе соответствует части исходного шаблона regex, например, литеральной строке или ветви, и имеет указатель на узлы, представляющие следующий компонент для сопоставления. Поскольку "узел" и "оператор" уже имеют другие значения в исходном коде Perl, мы будем называть узлы в программе regex "regops".

Программа представлена массивом regnode структур, одна или несколько из которых представляют собой одну операцию regop программы. Структура regnode является наименьшей необходимой структурой и имеет структуру поля, которая используется совместно со всеми другими более крупными структурами. (Вне данного документа термин "regnode" иногда используется для обозначения "regop", что может быть путаницей.)

Указатели "next" всех regops, кроме BRANCH, реализуют конкатенацию; указатель "next" с BRANCH с обеих сторон соединяет две альтернативы. [Здесь у нас есть одна из тонких зависимостей синтаксиса: отдельный BRANCH (в отличие от набора их) никогда не конкатенируется ни с чем из-за приоритета операторов.]

Операнд некоторых типов regop — это литеральная строка; для других — это regop, ведущий в подпрограмму. В частности, операнд узла BRANCH — это первая операция regop ветви.

ПРИМЕЧАНИЕ: Как и подсказывает метафора железной дороги, это не древовидная структура: хвост ветви соединяется с элементом, который следует за набором BRANCH. Это похоже на единую линию железнодорожного пути, которая разделяется, когда она входит на станцию или железнодорожную площадку, и вновь соединяется, когда выходит с другой стороны.

Операции

Базовая структура regop определяется в regexp.h следующим образом:

struct regnode {
    U8  flags;    /* Various purposes, sometimes overridden */
    U8  type;     /* Opcode value as specified by regnodes.h */
    U16 next_off; /* Offset in size regnode */
};

В regcomp.h определены и другие более крупные структуры, подобные regnode. Они почти как подклассы, в том смысле, что имеют те же поля, что и regnode, с возможными дополнительными полями, следующими в структуре, и в некоторых случаях конкретное значение (и имя) некоторых базовых полей переопределяются. Ниже приведено более полное описание.

regnode_1

regnode_2

regnode_1 структуры имеют ту же заголовок, за которым следует один четырёхбайтный аргумент; regnode_2 структуры содержат два двухбайтных аргумента:

regnode_1                U32 arg1;
regnode_2                U16 arg1;  U16 arg2;

regnode_string

regnode_string структуры, используемые для литеральных строк, следуют за заголовком с однобайтовой длиной, а затем данными строки. Строки дополняются нулевыми байтами в конце, так что общая длина узла является кратной четырём байтам:

regnode_string           char string[1];
                         U8 str_len; /* overrides flags */

regnode_charclass

Скобочные классы символов представлены regnode_charclass структурами, которые имеют четырёхбайтный аргумент, а затем 32-байтовую (256-битную) битовую карту, указывающую, какие символы в диапазоне Latin1 включены в класс.

regnode_charclass        U32 arg1;
                         char bitmap[ANYOF_BITMAP_SIZE];

Различные флаги, названия которых начинаются с ANYOF_, используются для особых ситуаций. Сопоставления с Latin1 и не известные до выполнения вещи хранятся в "Структуре pprivate Perl".

regnode_charclass_posixl

Также существует более крупная форма структуры класса символов, используемая для представления классов символов POSIX в /l совпадении, которая называется regnode_charclass_posixl, которая имеет дополнительную 32-битную битовую карту, указывающую, какие классы символов POSIX были включены.

regnode_charclass_posixl U32 arg1;
                         char bitmap[ANYOF_BITMAP_SIZE];
                         U32 classflags;

regnodes.h определяет массив PL_regnode_arg_len[], который указывает размер каждого оператора в единицах size regnode (4 байта). Макрос используется для расчёта размера узла EXACT на основе его поля str_len.

regops определены в regnodes.h, который генерируется из regcomp.sym с помощью regcomp.pl. В настоящее время максимальное возможное количество различных regops ограничено 256, причём примерно четверть уже используется.

Набор макросов упрощает и делает более согласованным доступ к полям. К ним относятся OP(), который используется для определения типа структуры, подобной regnode; NEXT_OFF(), который является смещением к следующему узлу (подробнее об этом позже); ARG(), ARG1(), ARG2(), ARG_SET(), и аналоги для чтения и записи аргументов; и STR_LEN(), STRING() и OPERAND() для манипулирования строками и типами regop.

Какой узел regnode следует за ним?

В движке регулярных выражений существуют два разных понятия «следующий узел» (regnode), и важно сохранять их различие в ваших мыслях, поскольку они концептуально перекрываются во многих местах, но там, где они не перекрываются, разница имеет решающее значение. Для большинства типов узлов (regnode) эти два понятия практически идентичны. Два типа — REGNODE_AFTER, который активно используется во время компиляции, но лишь изредка во время выполнения, и regnext, который активно используется во время выполнения, но лишь изредка во время компиляции.

«REGNODE_AFTER»

Это «позиционно следующий узел» (regnode) в скомпилированной программе регулярного выражения. Для меньших типов узлов это regnode_ptr+1 под капотом, но поскольку размеры узлов могут варьироваться и меняться со временем, мы предлагаем макросы, скрывающие подробности.

Он активно используется на стадии компиляции, но используется только несколькими типами узлов (regnode) на стадии выполнения. Он также активно используется в коде для вывода программы регулярных выражений для отладки.

Существует набор макросов, которые могут быть использованы для вычисления этого максимально эффективно в зависимости от обстоятельств. Канонический макрос — REGNODE_AFTER(), который является наиболее мощным и должен обрабатывать любой случай, но также потенциально медленнее. Есть два дополнительных макроса для частного случая, когда размер текущего узла (regnode) ИЗВЕСТЕН и постоянен, а также известен его тип или код операции. В этом случае можно использовать REGNODE_AFTER_opcode() или REGNODE_AFTER_type().

В более старых версиях движка регулярных выражений REGNODE_AFTER() назывался NEXTOPER, но это оказалось запутанным, и он был переименован. Также есть REGNODE_BEFORE(), но он небезопасен и не должен использоваться в новом коде.

«regnext»

Это узел (regnode), который можно достичь, перейдя вперёд на значение члена NEXT_OFF() узла (regnode), или в некоторых случаях для более длинных переходов — по полю arg1 структуры regnode_1. Подпрограмма regnext() обрабатывает это прозрачно. В большинстве случаев «regnext» для узла (regnode) — это узел, который должен быть выполнен после успешного совпадения текущего узла, но в некоторых случаях это может быть не так. В типах узлов (regnode) управления циклами и ветвлениями regnext может означать что-то особенное, для узлов BRANCH regnext — это следующий узел BRANCH, который должен быть выполнен, если текущий не выполнился, и некоторые узлы управления циклами устанавливают regnext в конец цикла, чтобы они могли перейти к очистке, если текущая итерация не соответствует.

Большинство типов узлов (regnode) не создают ветвление в потоке выполнения, и, отложив оптимизации, два понятия «следующий» одинаковы. Например, regnext и REGNODE_AFTER кода операции SBOL одинаковы во время компиляции. Основное место, где это не так, — это узлы (regnode) BRANCH, где REGNODE_AFTER представляет начало шаблона в ветвлении, а regnext представляет связь со следующим узлом BRANCH, если текущий не соответствует, или 0, если это последнее ветвление. Логика цикла для квантификаторов также использует подобное различие между двумя типами, где REGNODE_AFTER — это внутренность цикла, а regnext указывает на конец цикла.

Во время компиляции движок может не знать, что такое regnext для данного узла, поэтому во время компиляции regnext используется только там, где это необходимо, и известно, что это правильно. В самом конце фазы компиляции мы проходим по программе регулярных выражений и корректируем данные regnext по мере необходимости, а также выполняем различные оптимизации, которые могут привести к тому, что узлы (regnode), которые были необходимы во время построения, станут излишними, или мы можем заменить большой узел (regnode) на гораздо меньший, заполнив пробел узлами OPTIMIZED regnode. Таким образом, мы можем начать с чего-то вроде этого:

BRANCH
  EXACT "foo"
BRANCH
  EXACT "bar"
EXACT "!"

и заменить его на что-то вроде этого:

TRIE foo|bar
OPTIMIZED
OPTIMIZED
OPTIMIZED
EXACT "!"

regnext для узла TRIE будет узлом OPTIMIZED regnode, и теоретически regnext будет таким же, как REGNODE_AFTER. Но было бы неэффективно выполнять узел OPTIMIZED regnode как пустое действие трижды, поэтому оптимизатор исправляет regnext, чтобы такие узлы пропускались во время выполнения.

Во время фаз выполнения мы используем regnext() почти исключительно и используем REGNODE_AFTER только в особых случаях, когда у него есть определённое значение для данного типа узла (regnode). Например, /x+/ приводит к

PLUS
    EXACT "x"
END

regnext узла PLUS — это узел END, а regnext узла PLUS — это узел EXACT. regnext и REGNODE_AFTER узла EXACT — это узел END.

Обзор процесса

В общих чертах, выполнение сопоставления строки с шаблоном включает следующие шаги:

А. Компиляция

1. Разбор

2. Оптимизация и анализ

Б. Выполнение

3. Оптимизации начальной позиции и отсутствия совпадения

4. Выполнение программы

Местоположение этих шагов в фактическом выполнении программы Perl определяется тем, включает ли шаблон интерполяцию каких-либо строковых переменных. Если интерполяция происходит, то компиляция выполняется во время выполнения. Если этого не происходит, то компиляция выполняется во время компиляции. (Модификатор /o изменяет это, а также qr// в некоторой степени.) Движку это не очень важно.

Компиляция

Этот код в основном находится в файле regcomp.c, вместе с заголовочными файлами regcomp.h, regexp.h и regnodes.h.

Компиляция начинается с pregcomp(), что в основном является оболочкой инициализации, которая передаёт работу двум другим процедурам для выполнения основной задачи: первой является reg(), которая является начальной точкой разбора; вторая, study_chunk(), отвечает за оптимизацию.

Инициализация в pregcomp() в основном включает создание и заполнение данных специальной структуры RExC_state_t (определённой в regcomp.c). Почти все используемые внутри процедуры в regcomp.h принимают указатель на одну из этих структур в качестве первого аргумента с именем pRExC_state. Эта структура используется для хранения состояния компиляции и содержит много полей. Аналогично, существует множество макросов, которые работают с этой переменной: всё, что похоже на RExC_xxxx, — это макрос, который работает с этим указателем/структурой.

reg() — это начало процесса разбора. Он отвечает за разбор произвольного фрагмента шаблона до конца строки или первой встреченной закрывающей скобки в шаблоне. Это означает, что он может использоваться для разбора регулярного выражения верхнего уровня или любой части внутри группирующих скобок. Он также обрабатывает «специальные скобки», которые есть у регулярных выражений Perl. Например, при разборе /x(?:foo)y/, reg() в какой-то момент будет вызван для разбора от символа «?» до и включая «)».

Кроме того, reg() отвечает за разбор одного или нескольких ветвлений в шаблоне и за «завершение их» путём правильной установки указателей на следующий узел. Для выполнения разбора он многократно вызывает regbranch(), который отвечает за обработку до первого встреченного символа |.

regbranch(), в свою очередь, вызывает regpiece(), который обрабатывает «вещи», за которыми следует квантификатор. Для разбора «вещей» вызывается regatom(). Это процедура низкого уровня, которая разбирает константные строки, классы символов и различные специальные символы, такие как $. Если regatom() встречает символ «(», то он, в свою очередь, вызывает reg().

Раньше в процессе разбора участвовало два основных этапа: первый для вычисления размера скомпилированной программы, а второй для её фактической компиляции. Но теперь есть только один основной проход с первоначальной грубой оценкой, основанной на длине входного шаблона, которая увеличивается при необходимости по мере выполнения разбора, а затем обрезается до фактически используемого количества.

Однако может произойти необходимость перезапуска разбора с начала при возникновении различных обстоятельств. Примером является случай, когда программа оказывается настолько большой, что в ней есть переходы, которые не поместятся в обычные 16 бит. Существуют две специальные regops, которые могут хранить более длинные адреса перехода, BRANCHJ и LONGBRANCH. Разбор перезапускается, и вместо обычных более коротких используются эти. Всякий раз, когда требуется перезапустить разбор, функция возвращает ошибку и устанавливает флаг о том, что нужно сделать. Это передаётся в функцию верхнего уровня, которая принимает соответствующие действия и начинает всё заново. В случае необходимости более длинных переходов устанавливается флаг RExC_use_BRANCHJ в структуре RExC_state_t, который функции знают, что нужно проверить, прежде чем решать, как выполнять ветвления.

В большинстве случаев функция, которая обнаруживает проблему, устанавливает соответствующий флаг и сразу возвращает ошибку. В разделе «Осложнения разбора» приведён явный пример того, как это работает. В других случаях, таких как ссылка вперёд на пронумерованную группировку с круглыми скобками, нам необходимо завершить разбор, чтобы узнать, действительно ли эта пронумерованная группировка появляется в шаблоне. В этих случаях разбор просто повторяется в конце с учетом того, сколько групп содержится в нем.

Процедура regtail() вызывается как reg(), так и regbranch(), чтобы правильно «установить указатель хвоста». При выполнении, когда мы доходим до конца ветвления, нам нужно перейти к узлу, следующему за группирующими круглыми скобками. Однако во время разбора мы не знаем, где будет конец, пока не дойдём до него, поэтому, когда мы дойдём, мы должны вернуться и обновить смещения по мере необходимости. regtail используется для облегчения этой задачи.

Особенность процесса разбора заключается в том, что регулярное выражение, такое как /foo/, изначально разбирается в альтернацию с одним ветвлением. Только после этого оптимизатор преобразует альтернации с одним ветвлением в более простую форму.

Граф вызовов разбора и грамматика

Граф вызовов выглядит следующим образом:

reg()                        # parse a top level regex, or inside of
                             # parens
    regbranch()              # parse a single branch of an alternation
        regpiece()           # parse a pattern followed by a quantifier
            regatom()        # parse a simple pattern
                regclass()   #   used to handle a class
                reg()        #   used to handle a parenthesised
                             #   subpattern
                ....
        ...
        regtail()            # finish off the branch
    ...
    regtail()                # finish off the branch sequence. Tie each
                             # branch's tail to the tail of the
                             # sequence
                             # (NEW) In Debug mode this is
                             # regtail_study().

Форма грамматики может быть примерно такой:

atom  : constant | class
quant : '*' | '+' | '?' | '{min,max}'
_branch: piece
       | piece _branch
       | nothing
branch: _branch
      | _branch '|' branch
group : '(' branch ')'
_piece: atom | group
piece : _piece
      | _piece quant

Осложнения разбора

Из вышеизложенного описания следует, что шаблон, содержащий вложенные скобки, приведет к графу вызовов, который циклически проходит через reg(), regbranch(), regpiece(), regatom(), reg(), regbranch() и так далее многократно, пока не будет достигнута самая глубокая степень вложенности. Все вышеперечисленные подпрограммы возвращают указатель на regnode, который обычно является последним добавленным в программу узлом. Однако, существует одна проблема: reg() возвращает NULL при разборе синтаксиса (?:) для встроенных модификаторов, устанавливая флаг TRYAGAIN. Флаг TRYAGAIN распространяется вверх до тех пор, пока он не будет перехвачен в некоторых случаях regatom(), а в остальных случаях безусловно regbranch(). Поэтому он никогда не будет возвращен regbranch() в reg(). Этот флаг позволяет распознавать такие шаблоны, как (?i)+ в качестве ошибок (Квантификатор следует за пустым местом в регулярном выражении; отмечено <-- HERE в m/(?i)+ <-- HERE /).

Еще одна проблема заключается в том, что представление программы отличается, если ей необходимо хранить Unicode, но точно узнать, нужно ли это, не всегда возможно до середины процесса разбора. Представление программы с Unicode больше и не может быть сопоставлено так эффективно. (Дополнительные сведения о причинах см. в разделе "Unicode и поддержка локализации" ниже.) Если шаблон содержит литеральные Unicode-символы, очевидно, что программе необходимо хранить Unicode. В противном случае, парсер оптимистично предполагает, что может быть использовано более эффективное представление, и начинает определение размера на этом основании. Однако, если затем он встретит что-то в шаблоне, что должно храниться в виде Unicode, например, последовательность экранирования \x{...} представляющую литеральный символ, это означает, что все ранее вычисленные размеры необходимо пересчитать, используя значения, соответствующие представлению с Unicode. Это еще один случай, когда разбор необходимо перезапустить, и это делается немедленно. Функция возвращает ошибку и устанавливает флаг RESTART_UTF8 (с помощью макроса REQUIRE_UTF8). Этот запрос на перезапуск распространяется вверх по цепочке вызовов аналогичным образом, пока не будет «перехвачен» в Perl_re_op_compile(), который отмечает шаблон как содержащий Unicode и перезапускает этап определения размера. Возможно также, что конструкции внутри блоков кода во время выполнения потребуют представления с Unicode, что сигнализируется возвращением false из S_compile_runtime_code() в Perl_re_op_compile().

Ранее перезапуск был реализован с помощью longjmp в regatom() обратно в setjmp в Perl_re_op_compile(), но это оказалось проблематичным, так как последняя функция является большой, содержит много автоматических переменных, которые плохо взаимодействуют с возникающим потоком управления setjmp.

Вывод отладки

Начиная с версии perl 5.9.x, вы можете use re Debug => 'PARSE' для просмотра некоторых отслеживающих данных о процессе разбора. Мы начнём с простых шаблонов и перейдём к более сложным.

Итак, когда мы разбираем /foo/, мы видим нечто подобное следующей таблице. Слева показано, что разбирается, а число указывает, куда пойдёт следующий regop. Материал справа - это вывод отслеживания графа. Имена выбраны короткими, чтобы сделать его менее плотным на экране. "tsdy" - это специальная форма regtail(), которая выполняет дополнительный анализ.

>foo<             1    reg
                         brnc
                           piec
                             atom
><                4      tsdy~ EXACT <foo> (EXACT) (1)
                             ~ attach to END (3) offset to 2

Полученная программа выглядит следующим образом:

1: EXACT <foo>(3)
3: END(0)

Как видите, даже несмотря на то, что мы разобрали ветвь и часть, это всё же был только атом. Окончательная программа показывает, как всё работает. У нас есть regop EXACT, за которым следует regop END. Число в скобках указывает, куда идёт regnext узла. regnext regop END не используется, так как regops END означают, что мы успешно выполнили сопоставление. Число слева указывает позицию regop в массиве regnode.

Теперь давайте попробуем более сложный шаблон. Мы добавим квантификатор, так что теперь у нас есть шаблон /foo+/. Мы увидим, что regbranch() дважды вызывает regpiece().

>foo+<            1    reg
                         brnc
                           piec
                             atom
>o+<              3        piec
                             atom
><                6        tail~ EXACT <fo> (1)
                  7      tsdy~ EXACT <fo> (EXACT) (1)
                             ~ PLUS (END) (3)
                             ~ attach to END (6) offset to 3

И в итоге получаем программу:

1: EXACT <fo>(3)
3: PLUS(6)
4:   EXACT <o>(0)
6: END(0)

Теперь у нас есть особый случай. regop EXACT имеет regnext равное 0. Это потому, что если он совпадает, он должен попытаться совпасть снова. regop PLUS обрабатывает фактическую ошибку regop EXACT и действует соответствующим образом (переходя к regnode 6, если EXACT совпало как минимум один раз, или возвращая ошибку, если нет).

Теперь что-то гораздо более сложное: /x(?:foo*|b[a][rR])(foo|bar)$/

>x(?:foo*|b...    1    reg
                         brnc
                           piec
                             atom
>(?:foo*|b[...    3        piec
                             atom
>?:foo*|b[a...                 reg
>foo*|b[a][...                   brnc
                                   piec
                                     atom
>o*|b[a][rR...    5                piec
                                     atom
>|b[a][rR])...    8                tail~ EXACT <fo> (3)
>b[a][rR])(...    9              brnc
                 10                piec
                                     atom
>[a][rR])(f...   12                piec
                                     atom
>a][rR])(fo...                         clas
>[rR])(foo|...   14                tail~ EXACT <b> (10)
                                   piec
                                     atom
>rR])(foo|b...                         clas
>)(foo|bar)...   25                tail~ EXACT <a> (12)
                                 tail~ BRANCH (3)
                 26              tsdy~ BRANCH (END) (9)
                                     ~ attach to TAIL (25) offset to 16
                                 tsdy~ EXACT <fo> (EXACT) (4)
                                     ~ STAR (END) (6)
                                     ~ attach to TAIL (25) offset to 19
                                 tsdy~ EXACT <b> (EXACT) (10)
                                     ~ EXACT <a> (EXACT) (12)
                                     ~ ANYOF[Rr] (END) (14)
                                     ~ attach to TAIL (25) offset to 11
>(foo|bar)$<               tail~ EXACT <x> (1)
                           piec
                             atom
>foo|bar)$<                    reg
                 28              brnc
                                   piec
                                     atom
>|bar)$<         31              tail~ OPEN1 (26)
>bar)$<                          brnc
                 32                piec
                                     atom
>)$<             34              tail~ BRANCH (28)
                 36              tsdy~ BRANCH (END) (31)
                                    ~ attach to CLOSE1 (34) offset to 3
                                 tsdy~ EXACT <foo> (EXACT) (29)
                                    ~ attach to CLOSE1 (34) offset to 5
                                 tsdy~ EXACT <bar> (EXACT) (32)
                                    ~ attach to CLOSE1 (34) offset to 2
>$<                        tail~ BRANCH (3)
                               ~ BRANCH (9)
                               ~ TAIL (25)
                           piec
                             atom
><               37        tail~ OPEN1 (26)
                               ~ BRANCH (28)
                               ~ BRANCH (31)
                               ~ CLOSE1 (34)
                 38      tsdy~ EXACT <x> (EXACT) (1)
                             ~ BRANCH (END) (3)
                             ~ BRANCH (END) (9)
                             ~ TAIL (END) (25)
                             ~ OPEN1 (END) (26)
                             ~ BRANCH (END) (28)
                             ~ BRANCH (END) (31)
                             ~ CLOSE1 (END) (34)
                             ~ EOL (END) (36)
                             ~ attach to END (37) offset to 1

Получающаяся программа

 1: EXACT <x>(3)
 3: BRANCH(9)
 4:   EXACT <fo>(6)
 6:   STAR(26)
 7:     EXACT <o>(0)
 9: BRANCH(25)
10:   EXACT <ba>(14)
12:   OPTIMIZED (2 nodes)
14:   ANYOF[Rr](26)
25: TAIL(26)
26: OPEN1(28)
28:   TRIE-EXACT(34)
      [StS:1 Wds:2 Cs:6 Uq:5 #Sts:7 Mn:3 Mx:3 Stcls:bf]
        <foo>
        <bar>
30:   OPTIMIZED (4 nodes)
34: CLOSE1(36)
36: EOL(37)
37: END(0)

Здесь мы можем видеть гораздо более сложную программу с различными оптимизациями. В узле 10 мы видим пример, где класс символов, содержащий только один символ, был преобразован в узел EXACT. Мы также можем видеть, где целая альтернатива была преобразована в узел TRIE-EXACT. В результате некоторые regnodes были помечены как исключённые в результате оптимизации. Мы можем видеть, что символ $ был преобразован в regop EOL, специальный фрагмент кода, который ищет \n или конец строки.

Следующий указатель для BRANCH интересен тем, что он указывает на то, куда следует перейти, если ветвь не совпадает. При выполнении, если движок пытается перейти от ветви к regnext, которое не является ветвью, тогда движок будет знать, что весь набор ветвей потерпел неудачу.

Оптимизация и анализ с просмотром

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

'ababababababababababab' =~ /(a|b)*z/

Часть (a|b)* может совпадать с каждым символом в строке и затем каждый раз терпит неудачу, потому что в строке нет z. Таким образом, мы явно можем избежать использования движка регулярных выражений, если в строке нет z. Аналогично, в шаблоне:

/foo(\w+)bar/

В этом случае мы знаем, что строка должна содержать foo, за которой должна следовать bar. Мы можем использовать быстрый алгоритм Бойера-Мура, реализованный в fbm_instr(), чтобы найти местоположение этих строк. Если их нет, нам не нужно прибегать к более дорогостоящему движку регулярных выражений. Ещё лучше, если они есть, то мы можем использовать их положения, чтобы уменьшить область поиска, которую движок регулярных выражений должен охватить, чтобы определить, соответствует ли весь шаблон.

Существует множество аспектов шаблона, которые могут быть использованы для облегчения оптимизации по этим линиям:

• якорные фиксированные строки

• плавающие фиксированные строки

• минимальные и максимальные требования к длине

• стартовый класс

• начало/конец строки

Другой формой оптимизации может быть пост-разборная "оптимизация с просмотром", где неэффективные конструкции заменяются более эффективными. regops TAIL, которые используются во время разбора для обозначения конца ветвей и конца групп, являются примерами этого. Эти regops используются в качестве заглушек во время построения и «всегда совпадают», поэтому их можно «оптимизировать», заставив ссылки на TAIL указывать на то, на что указывает TAIL, тем самым «пропуская» узел.

Еще одна оптимизация, которая может произойти, - это "слияние EXACT", где два последовательных узла EXACT объединяются в один regop. Еще более агрессивной формой этого является преобразование последовательности ветвей в форме EXACT BRANCH ... EXACT в regop TRIE-EXACT.

Всё это происходит в подпрограмме study_chunk(), которая использует специальную структуру scan_data_t для хранения выполненного анализа и выполняет "оптимизацию с просмотром" по ходу дела.

Код, связанный с study_chunk(), чрезвычайно запутанный. Будьте осторожны. :-)

Выполнение

Выполнение регулярного выражения, как правило, включает два этапа: первый - это поиск начальной точки в строке, с которой мы должны начать соответствие, а второй - запуск интерпретатора regop.

Если мы можем сказать, что нет допустимой начальной точки, то мы не будем беспокоиться о запуске интерпретатора. Аналогично, если по результатам анализа мы знаем, что не можем найти быстрый путь к начальной позиции, мы переходим сразу к интерпретатору.

Два входные точки - re_intuit_start() и pregexec(). Эти функции имеют несколько тесные взаимосвязи, перекрытия в своих функциях, и pregexec() даже может вызывать re_intuit_start() самостоятельно. Тем не менее, другие части исходного кода perl могут вызывать либо одну, либо обе.

Выполнение самого интерпретатора раньше было рекурсивным, но благодаря усилиям Дэйва Митчелла в версии 5.9.x, это изменилось: теперь на куче поддерживается внутренний стек, и функция полностью итерационная. Это может быть сложным, так как код довольно консервативно относится к тому, какой информацией он хранит, в результате чего две последующие строки кода фактически могут работать в совершенно разных контекстах из-за имитируемой рекурсии.

Оптимизация начальной позиции и отсутствия совпадения

re_intuit_start() отвечает за обработку начальных позиций и оптимизаций отсутствия совпадений, как это определено результатами анализа, выполненного study_chunk() (и описанного в разделе "Оптимизация и анализ с просмотром").

Основная структура этой процедуры состоит в поиске начальных и/или конечных точек, где может произойти совпадение, и в проверке того, достаточно ли длинной строка для совпадения с шаблоном. Она пытается использовать более эффективные методы вместо менее эффективных и может включать значительную взаимную проверку ограничений для нахождения места в строке, которое соответствует шаблону. Например, она может попытаться определить, что заданная фиксированная строка должна не только присутствовать, но и находиться на определённом расстоянии от конца строки, или что-то подобное.

Она вызывает несколько других процедур, таких как fbm_instr(), которая выполняет быстрое соответствие по Бойеру-Муру, и find_byclass(), которая отвечает за нахождение начала с использованием первого обязательного regop в программе.

Когда критерии оптимизации выполнены, вызывается reg_try() для выполнения сопоставления.

Выполнение программы

pregexec() является основной точкой входа для запуска регулярного выражения. Он включает в себя поддержку инициализации состояния интерпретатора регулярных выражений, запуск re_intuit_start(), если это необходимо, и запуск интерпретатора на строке с различными начальными позициями по мере необходимости. Когда требуется использование интерпретатора регулярных выражений, pregexec() вызывает regtry().

regtry() является точкой входа в интерпретатор регулярных выражений. Он ожидает в качестве аргументов указатель на структуру regmatch_info и указатель на строку. Он возвращает целое число 1 для успеха и 0 для неудачи. По сути, это оболочка подготовки к regmatch().

regmatch — это основной «рекурсивный цикл» интерпретатора. По сути, это гигантское операторное выражение case, реализующее конечный автомат, где возможные состояния — это сами regops, плюс ряд дополнительных промежуточных и состояний ошибки. Некоторые состояния реализованы как подпрограммы, но основная часть — это встроенный код.

РАЗНОЕ

Поддержка Юникода и локализации

При работе со строками, содержащими символы, которые не могут быть представлены с помощью набора символов с восьмиразрядным кодированием, Perl использует внутреннее представление, являющееся расширенной версией кодирования UTF-8 Юникода [2]. Оно использует один байт для представления символов из набора ASCII и последовательности из двух или более байтов для всех остальных символов. (См. perlunitut для получения дополнительной информации о взаимосвязи между UTF-8 и кодированием Perl, utf8. Разница не важна для данного обсуждения.)

Как бы вы ни рассматривали ситуацию, поддержка Юникода будет проблематичной в движке регулярных выражений. Трюки, которые могут сработать, когда у вас есть 256 возможных символов, часто не масштабируются для обработки размера набора символов UTF-8. Вещи, которые вы можете принять как должное при использовании ASCII, могут не быть верными в случае Юникода. Например, в ASCII можно предположить, что sizeof(char1) == sizeof(char2), но в UTF-8 это не так. Сворачивание регистра Юникода намного сложнее, чем простые правила ASCII, и даже при отсутствии использования Юникода, но только локальных кодировок с одним байтом, ситуация может быть сложной (например, малая латинская буква острый S (U+00DF, ß) должна совпадать с 'SS' в локальном регистронезависимом поиске).

Усложняет задачу то, что поддержка UTF-8 была добавлена в движок регулярных выражений (как и в Perl) позже, что неизбежно усложнило ситуацию. Очевидно, проще разработать движок регулярных выражений с поддержкой Юникода с самого начала, чем перестраивать его для движка, не имеющего такой поддержки.

Практически все regops, которые предполагают просмотр входной строки, имеют два случая — один для UTF-8, а другой — нет. На самом деле, часто бывает сложнее, так как шаблон также может быть в формате UTF-8.

При внесении изменений необходимо быть осторожным, чтобы правильно обработать UTF-8, как во время компиляции, так и во время выполнения, включая случаи несоответствия строки и шаблона.

Основные структуры

Структура regexp, описанная в perlreapi, является общей для всех движков регулярных выражений. Два из её полей предназначены для внутреннего использования движка регулярных выражений, который скомпилировал шаблон. Это поля intflags и pprivate. pprivate — это указатель типа void на произвольную структуру, использование и управление которой возлагается на движок компиляции. Perl никогда не будет изменять эти значения. В случае стандартного движка структура, на которую указывает pprivate, называется regexp_internal.

Её поля pprivate и intflags содержат данные, специфичные для каждого движка.

Для хранения скомпилированного регулярного выражения используются две структуры. Одна, структура regexp, описанная в perlreapi, заполняется используемым движком, и некоторые её поля считываются Perl для реализации таких функций, как строковое представление qr//.

Другая структура указана через указатель в поле regexp структуры pprivate и, помимо intflags, в той же структуре считается собственностью движка регулярных выражений, который скомпилировал регулярное выражение.

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

Кроме того, она содержит два поля, предназначенных для внутреннего использования движка регулярных выражений, который скомпилировал шаблон. Это поля intflags и pprivate. pprivate — это указатель типа void на произвольную структуру, использование и управление которой возлагается на движок компиляции. Perl никогда не будет изменять эти значения.

Как упоминалось ранее, в случае стандартных движков pprivate будет указывать на структуру regexp_internal, которая содержит скомпилированную программу и любые дополнительные данные, частные для реализации движка регулярных выражений.

Структура pprivate Perl

Следующая структура используется как структура pprivate в движке регулярных выражений Perl. Поскольку она специфична для Perl, она представляет интерес только для других реализаций движков.

typedef struct regexp_internal {
    regnode *regstclass;
    struct reg_data *data;
    struct reg_code_blocks *code_blocks;
    U32 proglen;
    U32 name_list_idx;
    regnode program[1];
} regexp_internal;

Описание атрибутов приведено ниже:

regstclass

Специальный regop, используемый re_intuit_start() для проверки, может ли шаблон соответствовать в определённой позиции. Например, если движок регулярных выражений знает, что шаблон должен начинаться с 'Z', он может сканировать строку до тех пор, пока не найдёт 'Z', а затем запустит движок регулярных выражений с этой позиции. Процедура, обрабатывающая это, называется find_by_class(). Иногда это поле указывает на regop, встроенный в программу, а иногда — на независимый синтетический regop, созданный оптимизатором.

data

Это поле указывает на структуру reg_data, которая определяется следующим образом

struct reg_data {
    U32 count;
    U8 *what;
    void* data[1];
};

Эта структура используется для обработки структур данных, которые движок регулярных выражений должен обрабатывать специально во время операции клонирования или освобождения скомпилированного результата. Каждый элемент массива data имеет соответствующий элемент в массиве what. Во время компиляции regops, которым необходимы специальные структуры для хранения, добавляют элемент в каждый массив с помощью процедуры add_data() и затем хранят индекс в regop.

В современных версиях Perl 0-й элемент этой структуры зарезервирован и НИКОГДА не используется для хранения каких-либо полезных данных. Это позволяет тем, кому нужно индексировать в этот массив, представлять «отсутствие значения».

code_blocks

Эта необязательная структура используется для управления конструкциями (?{}) в шаблоне. Она состоит из следующих структур.

/* record the position of a (?{...}) within a pattern */
struct reg_code_block {
    STRLEN start;
    STRLEN end;
    OP     *block;
    REGEXP *src_regex;
};

/* array of reg_code_block's plus header info */
struct reg_code_blocks {
    int refcnt; /* we may be pointed to from a regex
                   and from the savestack */
    int  count; /* how many code blocks */
    struct reg_code_block *cb; /* array of reg_code_block's */
};

proglen

Хранит длину скомпилированной программы в единицах regops.

name_list_idx

Это индекс в массиве data, где хранится массив AV, содержащий имена любых именованных буферов захвата в шаблоне, если таковые имеются. Он используется только в отладочной версии движка регулярных выражений и когда RXp_PAREN_NAMES(prog) равно true. Он будет равен 0, если таких данных нет.

program

Скомпилированная программа. Встроена в структуру, так что вся структура может рассматриваться как один блок.

См. также

perlreapi

perlre

perlunitut

АВТОР

Автор: Yves Orton, 2006.

С отрывками из Perl и contributions и suggestions от Ronald J. Kimball, Dave Mitchell, Dominic Dunlop, Mark Jason Dominus, Stephen McCamant и David Landgren.

Теперь поддерживается Perl 5 Porters.

ЛИЦЕНЗИЯ

Такие же условия, как и в Perl.

ССЫЛКИ

[1] https://perl.plover.com/Rx/paper/

[2] https://www.unicode.org/