Атомарная группировка, или Ни шагу назад!

0. Присказка

В некотором царстве, в некотором государстве жил-был программист. Звали его, как полагается, Иван. Был он настоящим спецом, обладал всеми Тремя Великими Добродетелями Программиста, то есть был ленив, спесив и нетерпелив. Случилась в том царстве печаль великая: кризис. И выгнали Ваню с работы без выходного пособия. Горевал Ваня долго, а потом собрался с духом и разослал резюме по всему белу свету. Долго ли, коротко ли, вызвали Ваню на собеседование. Требований к соискателю было много, но главное — требовалось хорошо владеть регулярными выражениями. До собеседования — почти месяц, готовься — не хочу. Будучи человеком серьёзным, готовиться Иван решил обстоятельно. 3 недели и 3 дня он лежал на печи, почитывал Хабр и думал, как же неслыханно обстоятельно он будет готовиться. До собеседования остался 1 день. Ванюша мысленно обругал работодателей, которые назначают собеседование так скоро, что совсем подготовиться не успеваешь, слез с печи, сдал пивные бутылки и на вырученные деньги купил книжку по регексам. Читал он её до полного изнеможения, пока не отключился. Утром мы найдём сонную физиономию Ванюши лежащей, как на подушке, на этой самой книжке под Хабракатом.

1. Рекурсия

На собеседовании Ивану дали такую задачу. Написать регекс, который матчит выражение в круглых скобках (...), причем внутри скобок может быть множество выражений в других круглых скобках, вероятно, вложенных. Например: в цепочке
sin(2*pi/tan(.7+b*tanh(b/2)))+8*cos(b/4)
регекс должен матчить (находить) содержимое 1-й пары скобок:
(2*pi/tan(.7+b*tanh(b/2)))
Однако, регекс не должен матчить такую часть цепочки, в которой скобки не сбалансированы (открытые скобки не закрываются или, наоборот, закрываются скобки, которые вовсе не были открыты). Например, обрабатывая цепочку
(sin(b/2)
регекс должен найти (b/2), проигнорировав 1-ю скобку, т. к. она не закрывается. А в следующей цепочке
2*pi)*(r*r
регекс вообще не должен ничего найти, т. к. ни одной пары «правильных» скобок тут нет. И ещё одно ограничение состоит в том, что «пустые» скобки () запрещено матчить, т. е. внутри пары скобок должно быть хоть какое-то содержимое.
Короче говоря, нужно матчить «корректное» выражение в скобках, которое может содержать подвыражения с вложенными скобками, причем пустые скобки () не считаются корректными.
Иван выписывает примерные выражения и мотает на ус:
1) искомое выражение — это нечто в скобках.
2) Внутри скобок может быть либо нечто без скобок, и тогда всё просто:
(3.14 * R * R)
… либо нечто в скобках:
(2 * sin(pi/2))
Стоп! В последнем случае внутри скобок уже не просто «нечто в скобках», а сначала «нечто без скобок» 2 * sin, и лишь затем «нечто в скобках» (pi/2)!
И становится понятно, что внутри скобок «нечто без скобок» и «нечто в скобках» могут встречаться сколько угодно раз:
(2 * (a+8.5) * sin(pi/2) / (b - 1e-8)).
Задать «нечто без скобок» на языке регексов совсем просто: [^)(]+. Как задать альтернативу (нечто без скобок ЛИБО нечто в скобках) и «сколько угодно раз», тоже просто: метасимволы | и +. Но что же такое «нечто в скобках» и как это написать на языке регексов?
«Нечто в скобках»… «Нечто в скобках»… Где-то оно уже встречалось… А-а, вот: пункт
1) искомое выражение — это нечто в скобках. Что же такое это «нечто в скобках»? Если искомое выражение — это нечто в скобках, то нечто в скобках — это… искомое выражение! Эврика!
Ивану приходит в голову такая грамматика:
искомое-выраж ::= ( { выраж-без-скобок | искомое-выраж }+ )
Где + означает «1 и более раз», { a | b } означает «a или b», выделенные жирным шрифтом скобки означают сами символы скобок, а
выраж-без-скобок ::= любой-символ-кроме-скобок +
Т. е. определение искомого выражения получается рекурсивным. Но как это написать на языке регексов? Разве может регекс включать сам себя? Иван думал бы, что это невозможно, но вы забыли — он же целый месяц усердно готовился! Он вспомнил, что в современных движках регексов это возможно: в любом месте внутри регекса
(?R)
означает ссылку на весь регекс целиком. Иван пишет следующий регекс (с ключом /x, который значит, что все пробельные символы, включая переводы строк, не учитываются, а также возможны комментарии после символа # ):
/
\( # открывающая скобка
(
[^)(]+ # выраж-без-скобок
| # либо
(?R) # ссылка на этот регекс целиком
)+ # 1 или более раз
\) # закрывающая скобка
/x

Иван проверяет регекс на нескольких примерах цепочек (благо, на интервью разрешено прогонять тестовые программы, нельзя лишь заходить в Интернет и читать документацию):
there are no parentheses here
(a + b)
sin((pi/180)*deg + theta)
1+(1+1/(1+1/(2+1/(1+1/(1+1/(4+1/(1+1/(1+1/(6+1/(1+1/(1+1/(8+1))))))))))))
sin)a - b(
sin(a - b(
sin(a * (b+1)
и регекс с ними со всеми справляется как положено. Довольный, Иван показывает решение интервьюеру. Happy end, занавес? Но почему статья названа так, как она названа??
Интервьюер спрашивает, что должен (если должен) найти регекс в следующей цепочке:
(you're gonna fail sonny unless you correct it (your regex)
Прочитав и побледнев, Ванюша, тем не менее, не моргнув глазом отвечает, что, раз 1-я скобка нигде не закрывается, регекс должен найти 2-ю пару скобок: (your regex). Его просят проверить. Иван вбивает эту цепочку в свой проверочный скрипт (Perl):
#!/usr/bin/perl -wl
use strict;

my $string = "(you're gonna fail sonny unless you correct it (your regex)";
print $string;

if ( $string =~ / \( ( [^)(]+ | (?R) )+ \) /x ) {
print "Match: $&";
} else {
print "Not matched!"
}


Проверив синтаксис, Иван запускает скрипт и… и ничего не происходит, скрипт как будто «зависает». Не говорит ни «да», ни «нет». Иван и интервьюер молча смотрят на это секунд 10. За это время Иван из бледного становится ярко-розовым: он уже явно чувствует подвох. Но чтО он сделал не так?? В этот момент лэптоп, на котором был запущен (и до сих пор почему-то не завершился) скрипт, начинает отчетливо гудеть, хотя до тех пор работал бесшумно. Интервьюер, чтобы прервать неловко затянувшуюся паузу, предлагает Ивану чашку чая или кофе. «А пока пьёте, как раз и подумаете, чтО может быть не так», — добавляет он. Проходит еще полчаса, Иван выпивает 2 чашки кофе и одну — чая с лимоном, но идей, почему скрипт ведет себя так загадочно, у него нет. Интервьюер с Иваном расстаются, сотрудники отдела HR царя-батюшки делают у себя пометку: «кандидат отклонен по результатам собеседования». А мы переходим к пункту

2. Катастрофический откат

Что же происходило с регексом Ивана? Попытаемся понять, как происходила работа регекса
/ \( ( [^)(]+ | (?R) )+ \) /x
на «злополучной» цепочке
(you're gonna fail sonny unless you correct it (your regex)

1. Скобка в регексе матчит скобку в цепочке
2. [^)(]+ матчит you're gonna fail sonny unless you correct it и «упирается» в открывающую скобку, которую «скушать» не может
3. Альтернатива (...|...) стоит с жадным квантификатором +, поэтому движок регексов пробует найти (...|...) еще раз. Первая ветвь [^)(]+ альтернативы сразу, увидев открывающую скобку (, говорит «не могу матчить»
4. Движок переходит ко 2-й альтернативе: (?R). Это не что иное, как весь регекс сначала. А в цепочке осталось (your regex). Тут всё просто: скобка ( в регексе матчит скобку ( в цепочке, затем [^)(]+ матчит your regex, затем (других вхождений альтернативы (...|...) движок в оставшейся части цепочки не обнаруживает: нет ни «не-скобки», ни открывающей скобки) движок переходит к закрывающей скобке ) в регексе. И она матчит скобку ) в цепочке.
5. Отлично, движку удалось матчить (?R) части исходной цепочки (your regex)
6. В цепочке мы подошли к концу, больше символов не осталось. Квантификатор в (...|...)+ жаден, и движок регексов пытается найти ещё одну альтернативу (...|...), но у него это не получается: в пустой оставшейся части цепочки он не находит ни не-скобки, ни открывающей скобки, с которой могла бы начаться ветвь (?R)
7. Итак, ещё одну альтернативу найти не удаётся. Что ж, у всякой жадности должны быть границы. Движок «довольствуется» уже найденными 2-мя вхождениями альтернативы в цепочку и переходит к следующей части регекса. Это закрывающая скобка ). Но в цепочке скобки нет: в цепочке вообще к этому моменту пусто, всё уже отматчили предыдущие части регекса. Матчить открывающую скобку из регекса нечему.
8. Что делает движок регексов дальше? Сдаётся и говорит, что матча нет? Ни в коем случае. Он помнит, что последнее выражение с квантификатором [^)(]+ было жадным и, возможно, «съело» слишком много, не оставив ничего следующим частям регекса. Происходит откат движка регексов назад.
9. Движок помнил, что в предыдущий раз [^)(]+ «съел» цепочку your regex. Он заставляет [^)(]+ «отдать» 1 символ, x, для следующих частей регекса. Т. е. в цепочке остается: x). А в регексе мы внутри альтернативы (...|...)+
10. Т. к. + жаден, движок пытается найти ещё 1 альтернативу (...|...), и у него это получается, т. к. 1-я ветвь альтернативы, [^)(]+, замечательно матчит символ x, оставшийся в цепочке.

Так можно продолжать очень долго, но тут, на самом деле, уже всплыла проблема, корень зла, изъян нашего регекса. В цепочке your regex, которая с точки зрения человека является одним неделимым токеном выраж-без-скобок, наш движок регексов нашел 2 токена: your rege и x, которые распределились по «разным экземплярам» регекса [^)(]+. Если убрать из исходного регекса:
/ \( ( [^)(]+ | (?R) )+ \) /x
всё «лишнее», всё, что требует для матча наличия символов ')' или '(' в цепочке (а в цепочке your regex заведомо нет этих символов) то останется лишь:
/ ( [^)(]+ )+ /x
И тут проблема становится ещё более явной. Ведь your regex можно матчить и как 1 токен your regex, и как 2 your rege и x, и как you и r regex, и как 3, 4,… или даже 10 отдельных токенов, каждый из которых состоит из одного символа! Число вариантов разбиения цепочки your regex на токены огромно. И регекс / ( [^)(]+ )+ /x подразумевает, при необходимости, перебор всех этих вариантов. Почему же Иван сразу, при проверке тестовых цепочек, не заметил этой проблемы? Потому что в том случае имела место обычная удача: хотя число вариантов разбиения цепочки было огромно, но 1-й же вариант разбиения (когда [^)(]+, будучи жадным, захватывает весь текст без скобок целиком) оказывался удачным, находился матч, и у движка регексов просто не было нужды откатываться. В случае же цепочки, данной интервьюером, все было хуже, т. к. ни 1-й, ни 2-й, ни 100 000 000-й вариант разбиения длинной строки на токены не давал матч, т. к. пытался найти закрывающую скобку, которой просто не было. Поэтому в последнем случае движок регексов будет откатываться, пробуя всё новые и новые варианты разбиения, но так и не найдёт матч за разумное время. Это и называется катастрофическим откатом.

3. Атомарная группировка

Можно ли предотвратить эту проблему? Да, причем очень легко. Проблема в том, что «глупый» движок регексов откатывается до греческих календ, в то время как человеку одного взгляда достаточно, чтобы понять: откатываться там бесполезно. Никакое разбиение your regex (и предшествующей части цепочки) на части не поможет отыскать недостающую закрывающую скобку. Существует способ сказать движку регексов: «в этом месте не пытайся откатываться, даже если это приведет к отсутствию полного матча».
(?> .....)
это называется «атомарная группировка», и означает примерно «внутри части регекса, находящейся между (?> и ), откат запрещен». Или, точнее, по-другому. Пусть (?>X), где X — некоторый регекс, является частью большего регекса A(?>X)B (A и B — тоже какие-то регексы). Пусть на вход этого большего регекса подали цепочку ab, причем здесь a и b — не единичные символы, а некоторые цепочки символов. Пусть начальная часть A большего регекса уже нашла соответствие («отматчила») цепочку a. Движок регексов переходит к регексу (?>X), а в обрабатываемой цепочке указатель символов стоит сразу за цепочкой a (и сразу перед b). В этом случае атомарная группировка (?>X) работает так, как будто абсолютно отдельному, независимому, регексу X подали на вход цепочку b. И X «не знает» и ему всё равно, стоит ли после него какой-то ещё регекс B и получится ли у B что-то матчить. X работает, как будто кроме него никаких регексов больше нет. И если, в частности, X содержит что-то с жадным квантификатором:
(?> [^)(]+ )
то атомарная группировка не позволит этой «жадной» части откатываться. Если мы сразу захватили целиком цепочку your regex, то так тому и быть, ни шагу назад!
Изменив наш регекс для нахождения текста в скобках, мы решили бы проблему:
/ \( (?> [^)(]+ | (?R) )+ \) /x

В статье Cверхжадные квантификаторы мы рассмотрели квантификаторы ++, *+ и т. п. Оказывается, сверхжадные квантификаторы — это частный случай атомарной группировки. И мы могли бы добиться того же эффекта (избавиться от катастрофического отката), сделав квантификаторы в исходном регексе сверхжадными:
/ \( ( [^)(]++ | (?R) )+ \) /x
или, ещё лучше,
/ \( ( [^)(]++ | (?R) )++ \) /x

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