perlreguts

СОДЕРЖАНИЕ

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

ИМЯ

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

ОПИСАНИЕ

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

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

ОБЗОР

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

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

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

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

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

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

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

Структура программы Regexp

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

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

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

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

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

Regops

Базовая структура 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 */
};

Другие более крупные структуры, похожие на regnode, определены в regcomp.h. Они почти как подклассы, поскольку имеют те же поля, что и 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 и вещей, неизвестных до выполнения, хранятся в "Структуре Perl's pprivate".

regnode_charclass_posixl

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

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

regnodes.h определяет массив regarglen[], который задаёт размер каждого оператора в единицах 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.

Какой regop следует дальше?

В движке регулярных выражений существуют три различных понятия "следующий", и важно их различать.

• Существует «следующий узел» от данного узла, значение которого редко полезно, за исключением случаев, когда оно совпадает по значению с одним из других, и что иногда код предполагает, что это всегда так.

• Существует «следующая операция» от данной операции/узла. Это операция, физически расположенная после текущей, определяемая размером текущей операции. Это часто полезно, например, при выводе структуры, для обхода мы используем этот порядок. Иногда код предполагает, что «следующий узел» совпадает с «следующей операцией», или, другими словами, предполагает, что размер данного типа операции всегда будет равен одному узлу.

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

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

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

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

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 бит. Есть две специальные операции, которые могут хранить более длинные адреса перехода, 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/, мы видим что-то вроде следующей таблицы. Слева показано, что разбирается, а число указывает, куда пойдёт следующая операция. Информация справа представляет вывод отслеживания графа. Имена выбраны короткими, чтобы сделать его менее плотным на экране. «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)

Как видите, даже если мы проанализировали ветвь и часть, в конечном счёте это была только атомная операция. Конечная программа показывает нам, как всё работает. У нас есть операция EXACT, за которой следует операция END. Число в скобках указывает, куда идёт regnext узла. regnext операции END не используется, так как операции END означают, что мы успешно выполнили сопоставление. Число слева указывает позицию операции в массиве 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)

Теперь у нас есть особый случай. Операция EXACT имеет regnext равный 0. Это потому, что если она соответствует, то она должна попытаться соответствовать себе ещё раз. Операция PLUS обрабатывает фактическое неудачное соответствие EXACT операции и действует соответствующим образом (переходит к узлу 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. Вследствие этого некоторые из узлов regnode были помечены как оптимизированные. Мы видим, что символ $ был преобразован в 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 — основной «рекурсивный цикл» интерпретатора. Фактически, это гигантское операторное выражение, реализующее конечный автомат, где возможными состояниями являются сами regops, а также ряд дополнительных промежуточных и состояний ошибки. Некоторые состояния реализованы как подпрограммы, но основная часть — это встроенный код.

РАЗНОЕ

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

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

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

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

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

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

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

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

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

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

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

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

Кроме того, она содержит два поля, предназначенные для использования движком регулярных выражений, который скомпилировал шаблон. Это члены intflags и pprivate. pprivate — указатель на произвольную структуру, использование и управление которой являются ответственностью компилирующего движка. 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. Во время компиляции regop, которым требуются специальные структуры, добавляет элемент в каждый массив, используя процедуру 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

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

name_list_idx

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

program

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

СМОТРИ ТАКЖЕ

perlreapi

perlre

perlunitut

АВТОР

Yves Orton, 2006.

С отрывками из Perl и вкладами и предложениями от 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/