Позиционная проверка (lookaround) (часть 1)

Вводная информация

Для многих начинающих разработчиков регулярные выражения представляются некими таинственными письменами. Когда-то так казалось и мне, но вскоре я понял, что ничего страшного в них нет. Для того, чтобы понять регулярное выражение, его просто надо разбирать по частям. Чтобы написать более-менее сложное регулярное выражение, надо просто делать это постепенно, начиная с простых вещей и переходя к более сложным конструкциям, отлаживая получившийся результат на каждом шаге. Для любителей Ruby существует очень удобный веб-сервис http://rubular.com, который позволяет в реальном времени совершенно бесплатно отлаживать регулярные выражения. Открыв этот сайт, вы увидите три поля ввода: первое прямо под лейблом "Your regular expression:" служит, как вы можете догадаться, для ввода регулярного выражения. Обратите внимание, что прямые слэши уже обрамляют это поле, поэтому своё регулярное выражение записывайте без них. Маленькое поле справа предназначено для указания флагов, например, i - игнорировать регистр. В нижнем текстовом поле вводится строка, относительно которой будет выполняться регулярное выражение. Справа от этого поля вы увидите результат работы регулярного выражения, либо возникшие ошибки. В нижней части сайта есть небольшая шпаргалка, которая может быть полезна для получения быстрой справки. В общем, ничего лишнего и всё по делу.

Есть также сервис Regex101, который ещё и разбирает регулярные выражения, помогая их понять. Этот сервис позволяет выбрать один из трёх языков: Python, PHP, JS.

Данный пост представляет собой частичный перевод с английского статьи "Mastering Lookahead and Lookbehind" (http://www.rexegg.com/regex-lookarounds.html). Мои комментарии по ходу изложения будут помечены курсивом или добавлены в выноски. Приятного чтения.

Вступление

Трюк с позиционной проверкой в регулярных выражениях часто кажется сложным для новичков. Я думаю, что вы быстро его поймёте, если сумеете усвоить одну простую истину. Она состоит в том, что когда регулярное выражение осуществляет опережающую или ретроспективную позиционную проверку (в оригинальном тексте используются термины "lookahead" и "lookbehind"), оно остаётся на том же месте в строке, не продвигаясь дальше. Вы можете использовать ещё три позиционных проверки подряд после вызова первой, но регулярное выражение останется на том же месте. Вообще говоря, это очень полезная техника.

Пример позиционной проверки: простая валидация пароля

Давайте попробуем написать регулярное выражение, которое проверяет, соответствует ли пароль требованиям безопасности. Описанная здесь техника может быть полезна для анализа других данных, которые вы хотите проверить (например, e-mail адрес или телефонный номер).

Наш пароль должен соответствовать следующим четырём требованиям безопасности:

  1. Он должен иметь от 6 до 10 символов, причём символами могут быть только буква, цифра или нижнее подчёркивание.
  2. В нём должна присутствовать хотя бы одна буква строчного регистра.
  3. В нём должна присутствовать хотя бы одна буква прописного регистра.
  4. В нём должна присутствовать хотя бы одна цифра.

Наша стратегия будет такова: мы останемся в самом начале строки и несколько раз осуществим опережающую позиционную проверку (будем как бы "заглядывать" вперёд). С её помощью мы проверим количество символов в строке, наличие букв прописного регистра и соответствие другим требованиям. Если проверка была успешной, то мы знаем, что наша строка соответствует требованиям... И наше регулярное выражение радостно "проглотит" его с помощью простой конструкции .*.

Для тех, кто не знает, что такое .*, поясню. В регулярных выражениях . (точка) означает соответствие любому одному символу: букве, цифре, специальному символу, пробелу... Соответственно, написав .. мы объясняем нашему регулярному выражению, что в строке следует искать два любых символа. Если же мы работаем со строками переменной длины, то нужен другой подход. * (звёздочка) означает, что предшествующий ей символ может встречаться в строке сколько угодно раз подряд, включая 0 (то есть не встречаться вообще). Таким образом, запись .* означает, что в строке может сколько угодно раз встречаться любой символ, либо эта строка может быть пустой (нулевой длины). Вы можете открыть Rubular прямо сейчас и проверить это: наберите в поле для регулярного выражения .*, а в поле для текста - любую последовательность символов. Вы увидите, что в любом случае Rubular пометит синим цветом всю строку. Кстати, сравните * с + (плюс), который означает, что предшествующий символ может встречаться подряд 1 и более раз, то есть запись .+ означает, что в строке могут быть любые символы, но она не может быть нулевой длины. Вы также можете открыть irb в своей консоли и ввести следующий код:

puts "Match found!" if ''.match(/.*/)

На экране вы должны увидеть строку "Match found!". Если вы её не увидели - мир сошёл с ума и близится Апокалипсис. Выглядите на улицу - может, уже началось?

На самом деле позиционная проверка - это своего рода условное выражение. Оно гласит следующее: "Если ты видишь X или если ты не видишь Y, то помечай это как найденное соответствие".

Начнём с условия №1. Поиск строки, в которую могут входить только буквы, цифры или нижние подчёркивания и длина которой должна составлять от 6 до 10 символов, мы можем осуществить вот таким простым способом (здесь и далее прямые слэши в начале и конце опущены):

\w{6,10}

\w означает, что на данной позиции может быть одна буква, цифра или нижнее подчёркивание. Запись {6,10} говорит о том, что предшествующий символ может встречаться от 6 до 10 раз подряд (включая границы). Если мы, например, напишем {6,}, то символ может встречаться от 6 раз до бесконечности.

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

^(?=\w{6,10})

^ - привязка к началу строки в общем случае (см. примечание ниже). Круглые скобки и запись ?= - это сам механизм забегания.

Мы не хотим, чтобы в строке были другие символы, поэтому мы добавим символ доллара:

^(?=\w{6,10}$)

$ (символ доллара) - привязка к концу строки в общем случае (см. примечание ниже), то есть на этом строка должна кончаться и далее ничего не должно быть.

Обратите внимание! Руководство, перевод которого представлен здесь, не ориентировано на какой-то конкретный язык программирования. Во многих языках в качестве привязки к концу строки действительно используется символ доллара (например, в PHP). Однако в Ruby этот символ означает немного иное; помимо этого также существует также запись \z. В чём разница? $ означает конец линии, а \z - конец всей строки. Абсолютно аналогичная ситуация с символом ^, который означает начало линии, а \A - начало всей строки. Вы понимаете, что строка не обязательно состоит из одной линии. Например, когда вы печаете текст на компьютере, то периодически нажимаете клавишу Enter, чтобы перейти на новую строку - это и есть линия в нашей терминологии. При нажатии клавиши Enter в конец строки добавляется символ \n - переход на новую строку (могут добавляться другие символы, но не будем об этом). Так вот $ работает только до того, как попадётся первый символ перехода на новую строку. Чем это грозит? Предположим, у нас есть регулярное выражение для проверки корректности введённого пользователем e-mail адреса. Здесь мы не будем разбирать, как его написать - суть примера не в этом. Пусть оно будет совсем простым (не используйте его в реальных приложениях!):

^\w+@\w+\.\w+$

Это регулярное выражение говорит о том, что в начале должны быть любые буквы, цифры или нижние подчёркивания (должен быть хотя бы один символ из перечисленных), затем должна идти собака, снова то же самое, затем точка (обратите внимание, что перед точкой стоит обратный слэш \ - он экранирует точку; если этого не сделать, то она будет воспринята как соответствие любому символу, а не точка как таковая), затем снова буквы, цифры или нижние подчёркивания. Присутствует также привязка к началу и концу линии. Таким образом, вот такой e-mail будет вполне корректен с точки зрения регулярного выражения: test@example.com (проверьте на Rubular), а такой some_strange_text!!! - нет. Однако вот такой e-mail test@example.com\nsome_strange_text!!! тоже будет корректен, ведь привязка к концу строки работает только до первого символа \n! Если мы запишем наше регулярное выражение иначе

\A\w+@\w+\.\w+\z

то строка test@example.com\nsome_strange_text!!! уже не будет валидной, потому что привязка осуществлена к началу и концу всей строки, сколько бы линий в ней не было. Обратите внимание, что Rubular, к сожалению, не сможет помочь проиллюстрировать этот пример, вместо него используйте irb:

"test@example.com\nsome_strange_text!!!".match(/^\w+@\w+\.\w+$/) # => MatchData "test@example.com"
'test@example.com\nsome_strange_text!!!'.match(/^\w+@\w+\.\w+$/) # => nil
"test@example.com\nsome_strange_text!!!".match(/\A\w+@\w+\.\w+\z/) # => nil
'test@example.com\nsome_strange_text!!!'.match(/\A\w+@\w+\.\w+\z/) # => nil

Обратите внимание на кавычки - они должны быть двойными, чтобы Ruby интерпретировал текст строки. Если они будут одинарными, то содержимое строки не будет интерпретировано и \n будет расценен не как возврат строки, а просто как два символа. Таким образом, первая строка вернёт найденное совпадение, а вторая не вернёт именно по этой причине. 3 и 4 строки также ничего не вернут, потому что мы сделали корректную привязку.

И, наконец, если во время позиционной проверки мы нашли совпадение, то помечаем всю строку как соответствующую:

^(?=\w{6,10}$).*

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

Сначала проверим, что в строке есть хотя бы одна буква строчного регистра:

(?=.*?[a-z])

Само собой, будет осуществляться поиск буквы строчного регистра английского алфавита. Если нам интересны также русские буквы, то следует модифицировать запись так: (?=.*?[a-zа-я]).

Как это работает? Запись .*? означает "ленивое" соответствие; регулярное выражение будет "проглатывать" всё до тех пор, пока не встретит букву строчного регистра (фактически это значит то, что в строке может быть всё, что угодно, но там обязательно должна быть хотя бы одна буква строчного регистра). Как только мы закончим позиционную проверку, мы вернёмся в самое начало строки, то есть на самом деле регулярное выражение ничего не "проглотит".

Теперь мы можем соединить два написанных регулярных выражения в одно:

^(?=\w{6,10}$)(?=.*?[a-z]).*

Мы осуществляем две опережающие позиционные проверки подряд, и если мы удовлетворены тем, что увидели, то "проглатываем" всю строку, то есть помечаем её как соответствующую нашему выражению.

Аналогично сделаем проверку условия №3 (хотя бы одна буква прописного регистра):

(?=.*?[A-Z])

и условия №4 (хотя бы одна цифра):

(?=.*?\d)

Объединив все части в единое целое, мы получим наше регулярное выражение для проверки корректности вводимого пароля:

^(?=\w{6,10}$)(?=.*?[a-z])(?=.*?[A-Z])(?=.*?\d).*

Обратите внимание! Данный пример с паролем был представлен только для того, чтобы проиллюстрировать концепцию позиционных проверок в регулярных выражениях. В реальности ограничивать пользователей на максимальную длину пароля (по крайней мере, десятью символами), а тем более заставлять их использовать только буквы, цифры или нижние подчёркивания (без специальных символов) - это очень плохая идея, потому что таким образом вы помогаете потенциальному злоумышленнику: для подбора пароля ему потребуется меньше времени, ведь он точно знает, что специальных символов в пароле быть не может (откуда он это знает? попробует завести пароль со специальным символов и получит ошибку). Кроме того, чем длинее пароль, тем, конечно, больше времени требуется для его подбора. Например, веб-сервисы, которые работают со сторого конфиденциальными данными пользователя, могут требовать пароли длиной от 15 символов (а рекомендуют длину от 20).

На сайте Gibson Research Corporation есть веб-сервис, который позволяет прикинуть, сколько времени потребуется, чтобы подобрать брутфорсом (перебором) заданный пароль. Например, пароль длиной 19 символов, имеющий 2 буквы прописного регистра, 14 строчного и 3 специальных символа, подбирается в случае онлайн-атаки (принимая количество попыток в секунду равное 1000) за 1.47 * 10 ^ 24 веков, в случае оффлайн-атаки (100 млрд попыток в секунду) - за 14.67 * 10 ^ 15 веков, в случае множественного подбора (100 трлн попыток в секунду) - за 4.67 * 10 ^ 12 веков. Всего-то. Для сравнения: пароль из четырёх букв прописного регистра подбирается за 8 минут в онлайне и практически мгновенно в двух других случаях. Поиграйте с этим сервисом, он показывает интересные результаты.

Что же, на этом пока всё, свои вопросы и пожелания оставляйте в комментариях. Увидимся во второй части!

Следуйте за мной в Твиттере, чтобы первым узнавать о новых статьях >>