Согласно Википедии, Oniguruma означает «колесница дьявола» в переводе с японского.
Мы все знакомы с регулярными выражениями. Они являются «швейцарским армейским ножом разработчика». Чтобы вы не искали, какой бы текст не разбирали, вы всегда можете сделать это используя регулярные выражения. На самом деле, вероятно, вы начали использовать регулярные выражения гораздо раньше, чем стали использовать Ruby — они уже давно включены в большинство популярных языков программирования: Perl, JavaScript, PHP, Java и прочие. Ruby появился в середине 1990-х годов, тогда как регулярные выражения еще в 1960-х, то есть почти на 30 лет раньше!
Но как на самом деле работают регулярные выражения?
Если вы хотите узнать больше о информационных технологиях, стоящих за движком регулярных выражений, вы обязаны прочитать фантастическую серию статей от Russ Cox:
- Regular Expression Matching Can Be Simple And Fast (2007)
- Regular Expression Matching: the Virtual Machine Approach (2009)
- Regular Expression Matching in the Wild (2010)
Я не хочу заново повторять все, что написал Russ. Но я быстро отмечу, что Ruby использует «Non-recursive Backtracking Implementation» (реализация с нерекурсивным обратным ходом), которая обсуждается в его второй статье, что приводит к экспоненциальному падению производительности, точно так же, как и при работе с регулярными выражениями в Perl. Другими словами, Ruby не использует наиболее оптимальный Thompson NFA (алгоритм Томпсона для недетерминированных конечных автоматов), про который Russ рассказывает в своей первой статье.
Сегодня я собираюсь внимательно рассмотреть Oniguruma, движок регулярных выражений, который встроен в Ruby. Используя некоторые простые графические схемы и несколько примеров регулярных выражений я проиллюстрирую, как он работает. Читайте дальше, чтобы получить представление о том, что происходит внутри Ruby каждый раз, когда вы используете регулярные выражения, вероятно, там много того, о чем вы даже не догадывались.
Oniguruma
Начиная с версии 1.9 в MRI для обработки регулярных выражений используется немного модифицированная версия открытой C библиотеки, с названием «Oniguruma», которая так же используется и в PHP. Наряду с поддержкой всех стандартных функций регулярных выражений, она так же поддерживает многобайтовые символы, такие, например, как текст на японском.
На очень высоком уровне, вот что происходит, когда регулярное выражение проходит через Oniguruma:
На первом шаге, Oniguruma читает шаблон регулярного выражения, разбивает его на лексемы и переводит в древовидную структуру, содержащую набор синтаксических узлов — Abstract Syntax Tree (AST). Это очень похоже на то, как сам интерпретатор обрабатывает ваш Ruby-код. На самом деле, можно думать о механизме регулярных выражений Oniguruma, как о втором языке программирования, встроенном прямо в Ruby. Всякий раз, когда вы используете регулярные выражения в коде, вы действительно создаете вторую программу на совершенно другом языке. После разбора шаблона регулярного выражения, Oniguruma компилирует его в набор инструкций, которые затем выполняются на виртуальной машине. Эти инструкции реализуют конечный автомат, который Russ Cox описывает в своих статьях.
Затем, когда вы на самом деле производите поиск по регулярному выражению, виртуальная машина Oniguruma выполняет его, просто обрабатывая инструкции, которые были предварительно скомпилированы, применяя их к заданной строке.
На этой неделе, чтобы понять, как Oniguruma работает, и сравнить с тем, о чем пишет Russ Cox, я пересобрал Ruby 2.0 с установленными флагами ONIG_DEBUG_COMPILE и ONIG_DEBUG_MATCH. Установка этих флагов позволила мне увидеть много отладочных сообщений, когда я провел поиск по нескольким регулярным выражениям. В них я увидел, в какие инструкции виртуальной машины были скомпилированы шаблоны, и как она их выполняла. Вот, что я нашел…
Пример 1: Соответствие строке
Вот очень простой скрипт на Ruby, который ищет слово «brown» в заданной строке:
str = "The quick brown fox jumps over the lazy dog."
p str.match(/brown/)
Когда я запускаю этот код пересобранным интерпретатором Ruby, я наблюдаю много дополнительного отладочного вывода (гораздо больше, чем я покажу):
$ ruby regex.rb
PATTERN: /brown/ (US-ASCII)
optimize: EXACT_BM
exact: [brown]: length: 5
code length: 7
0:[exact5:brown] 6:[end]
match_at: str: 140261368903056 (0x7f912511b590) etc ...
size: 44, start offset: 10
10> "brown f..." [exact5:brown]
15> " fox ju..." [end]
#<MatchData "brown">
Ключевым моментом является следующее "0:[exact5:brown] 6:[end]" — эта строка описывает две команды виртуальной машины, составленные Oniguruma при компиляции шаблона /brown/. Вот как эта программа выглядит:
Вы можете думать об этой схеме как о конечном автомате для поиска /brown/:
exact5:brownпроверяет заданную строку на текущей позиции на наличие 5 букв «brown»;endозначает, что поиск закончен, возвращает найденные совпадения и останавливает выполнение.
При выполнении поиска по регулярному выражению Oniguruma выполняет эти инструкции на виртуальной машине с заданной строкой. Давайте рассмотрим, как это работает в моем примере. Во-первых, "exact5:brown" применяется для заданной строки в том месте, где находится слово «brown»:
Как Oniguruma знает с какого места строки ей начать? Получается, что она содержит оптимизатор, который решает, откуда начать поиск на основе заданной строки и первой инструкции виртуальной машины. Вы можете увидеть это выше: "optimize: EXACT_BM.. exact: [brown]: length: 5.. start offset: 10". В этом случае, поскольку было точно известно, что надо искать слово «brown», Oniguruma перепрыгнул на позицию, где первый раз появляется это слово. Да, я знаю, что это звучит как хак, но на самом деле это всего лишь простая оптимизация ускорения поиска в общих регулярных выражениях.
Затем, Oniguruma выполняет инструкцию "exact5:brown", проверяя, совпадают ли следующие 5 символов с шаблоном или нет. Так как они совпадают, Oniguruma перемещается на позицию после них и выполняет следующую инструкцию:
Теперь выполняется последняя инструкция, которая просто означает, что все завершено. Всякий раз, когда виртуальная машина выполняет "end", она останавливает выполнение, объявляет успех и возвращает совпадающую строку.
Пример 2: Соответствие одной из двух строк
Давайте возьмем более сложный пример и посмотрим, что произойдет — в этом шаблоне я хочу искать вхождение в строку либо «black», либо «brown»:
str = "The quick brown fox jumps over the lazy dog."
p str.match(/black|brown/)
Запускаем еще раз:
$ ruby regex.rb
PATTERN: /black|brown/ (US-ASCII)
optimize: EXACT
exact: [b]: length: 1
code length: 23
0:[push:(11)] 5:[exact5:black] 11:[jump:(6)] 16:[exact5:brown] 22:[end]
match_at: str: 140614855412048 (0x7fe37281c950), ...
size: 44, start offset: 10
10> "brown f..." [push:(11)]
10> "brown f..." [exact5:black]
10> "brown f..." [exact5:brown]
15> " fox ju..." [end]
#<MatchData "brown">
Опять же, ключевым здесь является "0:[push:(11)] 5:[exact5:black] 11:[jump:(6)] 16:[exact5:brown] 22:[end]". Это программа виртуальной машины, которая выполняет поиск нашего шаблона /black|brown/:
Тут все несколько сложнее! Прежде всего, вы можете заметить, что оптимизатор теперь ищет только букву «b»: "optimize: EXACT.. exact: [b]: length: 1". Это потому, что слова «black» и «brown» оба начинаются с этой буквы.
Теперь пошагово разберем выполнение этой программы:
Команда "push" выполняется на позиции первого нахождения буквы «b». Она передает следующую команду и место в исходной строке в то, что называется «Backtrack Stack» (стек обратного хода):
Чуть позже мы увидим, что «Backtrack Stack» это ключевое место в работе Oniguruma. Она использует его для нахождения альтернативных путей поиска в заданной строке, если первый путь не привел к результату. Давайте продолжим с этим примером, и вы увидите, что я имею в виду.
Итак, мы собираемся перейти к выполнению команды "exact5:black", но в строке есть только слово «brown». Это означает, что совпадения не будут найдены, и поиск не будет успешен. Тем не менее, прежде чем вернуть результат, Oniguruma проверит стек на наличие альтернативных путей поиска. В данном случае, там есть еще "exact5.brown" — вторая часть моего регулярного выражения /black|brown/. Теперь Oniguruma достает эту команду и продолжает выполнение:
Теперь здесь есть совпадение, так что Oniguruma перемещается на 5 символов и переходит к следующей инструкции:
Мы вновь достигли команды "end", так что просто возвращаем совпавшее значение.
Пример 3: Конструкция *
Теперь мой последний пример. Давайте посмотрим, что происходит, когда я использую следующее регулярное выражение:
str = "The quick brown fox jumps over the lazy dog."
p str.match(/brown.*/)
Мы хотим найти вхождение «brown», а затем любую последовательность символов до конца строки. Посмотрим отладочный вывод:
$ ruby regex.rb
PATTERN: /brown.*/ (US-ASCII)
optimize: EXACT_BM
exact: [brown]: length: 5
code length: 8
0:[exact5:brown] 6:[anychar*] 7:[end]
match_at: str: 140284579067040 (0x7f968c80b4a0), ...
size: 44, start offset: 10
10> "brown f..." [exact5:brown]
15> " fox ju..." [anychar*]
44> "" [end]
#<MatchData "brown fox jumps over the lazy dog.">
И вот у нас новый конечный автомат:
На этот раз вы можете увидеть новую инструкцию виртуальной машины Oniguruma: "anychar*". Как вы можете догадаться, она представляет синтаксический шаблон ".*". Давайте вновь посмотрим, что происходит на каждом шаге:
Мы вновь начали с 10 позиции в строке, там где первый раз появляется «brown», и вновь нашли совпадение, в результате Oniguruma проходит далее и переходит к выполнению следующей инструкции:
Следующая инструкция "anychar*", и вот как она работает:
- Во-первых, она соответствует любому символу, поэтому всегда смещает выполнение на один символ;
- Но, вместо перехода к следующей команде, Oniguruma возвращается назад и выполняет эту инструкцию еще раз, но уже для нового символа;
- Она так же записывает в стек текущий символ и следующую команду, в данном случае "
end".
Теперь Oniguruma просто проходит по всей части строки, повторяя эти инструкции для каждого символа «brown fox jumps over the lazy dog.». Так как она проходит по всей оставшейся части строки, она вновь и вновь записывает инструкцию "end" в стек:
И вновь:
И наконец она достигает конца исходной строки:
На сей раз "anychar*" не находит совпадений, так как в строке больше нет символов. Что происходит в таких случаях, когда команда не может найти совпадение? Как и в предыдущем примере, Oniguruma достанет команду из стека и продолжит поиск с ней. Таким образом, в данном случае, будет выполнена команда "end" с указанием последней позиции совпадения в строке. Это значит, что Oniguruma получит весь текст до конца строки «brown fox jumps over the lazy dog.»
Но зачем класть инструкцию "anychar*" в стек после каждого символа? Причина в том, что если бы здесь было еще несколько шаблонов после ".*", или ".*" являлось встроенным внутрь более сложного общего выражения, то становилось бы не ясно, который из отрезков исходной строки в конечном итоге привел бы к полному совпадению. Возможно, Oniguruma пришлось бы попробовать все варианты. В этом простом примере шаблон корректен до конца строки, поэтому нет необходимости доставать более одной команды из стека.
Одна интересная деталь. Если вы добавите еще команд после ".*", например, если будете искать /.*brown/, то Oniguruma не будет использовать инструкцию "anychar*". Вместо этого, она будет использовать другую похожую команду, например, "anychar*-peek-next:b". Работает она примерно как и "anychar*", но вместо того, чтобы каждый раз класть в стек следующую позицию в строке, она кладет в стек только позицию совпадения, в данном случае, с «b». Эта оптимизация работает потому, что Oniguruma знает, что следующий символ должен быть «b».
Патология шаблонов регулярных выражений
Я упомянул выше, что Ruby покажет такую же плохую работу, что и Perl, если дать ему очень сложный шаблон регулярного выражения. На самом деле очень легко воспроизвести это на своем компьютере. Попробуйте выполнить очень простой пример поиска по регулярному выражению:
str = "aaa"
p str.match(/a?a?a?aaa/)
Он должен выполниться очень быстро:
$ time ruby regex.rb
#<MatchData "aaa">
ruby regex.rb 0.02s user 0.01s system 30% cpu 0.080 total
Однако, если вы повторите его используя 29 повторений вместо 3, то время на нахождение вхождения будет иметь взрывной рост, как Russ показывает на графике слева в его первой статье:
str = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa" # 29 repetitions
p str.match(/a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaa/)
Выполнение с 29 вхождениями:
$ time ruby regex.rb
#<MatchData "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa">
ruby regex.rb 17.09s user 0.01s system 99% cpu 17.098 total
Или с 30 вхождениями:
$ time ruby regex.rb
#<MatchData "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa">
ruby regex.rb 34.00s user 0.01s system 99% cpu 34.025 total
Для 31 вхождения время составляет 67 секунд и увеличивается в геометрической прогрессии. Причина этого в том, что алгоритм, который использует Oniguruma проходит по списку возможных комбинаций, который растет в геометрической прогрессии относительно длины шаблона регулярного выражения. Этого бы не происходило, если бы Oniguruma и Ruby использовали алгоритм Томпсона, о котором рассказывал Russ!
Поверхностное объяснение
Как я уже говорил, здесь просто поверхностное объяснение того, что Oniguruma и Ruby могут делать. Как вы наверное знаете, есть много, очень много, операторов и опций регулярных выражений, которые можно использовать, каждая из них имеет соответствующие инструкции внутри виртуальной машины. Кроме того, мои примеры были чрезвычайно просты и понятны — в обычных приложениях у вас могут быть очень сложные регулярные выражения, которые компилируются в сотни различных инструкций виртуальной машины Oniguruma, что создает множество различных путей при поиске нужного выражения.
Тем не менее, основная идея всегда будет той же. Каждое регулярное выражение компилируется в ряд инструкций виртуальной машины, которая представляет собой конечный автомат. Когда Oniguruma при поиске заходит в тупик, она будет выбирать другой вариант пути к цели из стека, каждый из которых мог быть оставлен оператором "anychar*" или другой подобной командой.
Автор: stdfox
