Регулярные выражения и выражения благодарности Робу Пайку.

Я думаю все слышали про регулярные выражения и знают зачем они нужны — по сути они позволяют узнать соответствует ли строка регулярному выражению, и если да — то какие именно участки строки соответствуют каким участкам выражения.

А что если написать свой движок регулярных выражений?

Итак, вспомним, что регулярные выражения — это по сути конечный автомат. Когда мы встречаем какой-то символ — автомат переходит в новое состояние (если это возможно). Например, для выражения ab(cd|ef)g получится такой автомат:

RegEx State Automata

Я не буду вдаваться в подробности о детерминированных и недетерминированных автоматах. Просто будем помнить, что само выражение описывает всевозможные состояния и связи между ними, а входная строка буква за буквой переключает состояния автомата. Здесь, например, в состоянии 2 если на вход поступит буква ‘d’ — перейдем в состояние 3, если буква ‘c’ — в состояние 4. Иногда нельзя будет сказать в какое состояние переходить не заглядывая наперёд строки.

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

Существует великолепная книжка Роба Пайка и (кажется) Брайна Кернигана — The Practice Of Programming (TPOP). Там приводится код простейшего движка для регулярных выражений. Кому лень читать всю книгу — тут описан основной подход и приводятся те самые легендарные 30 строк кода.

Движок способен распознавать начало/конец строки и задавать wildcard — маску для множества одинаковых символов.
Гениальность этой реализации в рекурсивном подходе. Код получается очень лаконичный, а разница в скорости почти не заметна.

Извлекаем больше пользы

Я решил использовать этот код за основу, но получить чуть больше, а именно:

  • Узнавать где начинается соответствие и сколько символов строки попадает под выражение
  • Добавить специальные группы символом — ну хотя бы \d для цифр и \s для пробелов
  • Добавить квантификаторы (ну или как это назвать?) для нахождения 0 и больше вхождений («*»), 1 и больше («+»), 0 или 1 («?») и жадного оператора для 0 и больше («-» — как в Lua)

Попробуем вложиться строчек эдак в 100.

Начинать будем так же — нам нужная единственная главная функция и функция, определяющая соответствие начала строки выражению — regex_match и regex_match_here соответственно:

int regex_match(const char *regex, char *s, int *len) {
	char *p = s;

	/* force match from the beginning of the string */
	if (regex[0] == '^') {
		return (regex_match_here(regex + 1, s, len) ? 0 : -1);
	}

	/* iterate the string to find matching position */
	do {
		*len = 0;
		if (regex_match_here(regex, p, len)) {
			return p - s;
		}
	} while (*p++ != '\0');

	return -1;
}

int regex_match_here(const char *regex, char *s, int *len) {
	// TODO
}

С regex_match все ясно, если «^» — проверяем начало строки, иначе — пляшем слева направо пока не найдем соответствие.

Самое главное находится в regex_match_here:

static int regex_match_here(const char *regex, char *s, int *len) {
	int c = regex[0];

	if (regex[0] == '\0') { /* end of regex = full match */
		return 1;
	} else if (regex[0] == '$' && regex[1] == '\0') { /* check end of string */
		return (*s == '\0');
	} else if (regex[0] == '\\' && regex[1] != '\0') { /* check escaped symbol */
		c = regex[1];
		if (c != '^' && c != '$' && c != '\\' && c != '+' && c != '*' && c != '-' && c != '?') {
			c = c | 0x100;
		}
		regex = regex + 1;
	}
	/* check for special operators *,+,?,- */
	if (regex[1] == '*' || regex[1] == '+' || regex[1] == '-' || regex[1] == '?') {
		return regex_match_quantity(regex[1], c, regex+2, s, len);
	} else if (*s != '\0' && regex_match_group(*s, c)) {
		*len = *len + 1;
		return regex_match_here(regex+1, s+1, len);
	}
	return 0;
}

Здесь проверяем состояние нашего неявного автомата:

  • если выражение закончилось (достигнуто конечное состояние) — вернуть 1, соответствие найдено
  • если в регулярном выражении дошли до последнего символа, и это — «$» (т.е. конец строки) — вернуть 1 если строка тоже закончилась.
  • если нашли «\» — экранирующий символ, но мы имеем дело с особой группой символов. Вообще, в обычном синтаксисе «\» играет две роли — для «\.», «\^», «\$», ‘\?’, ‘\*’, ‘\+’, ‘\-‘ он означает использовать просто символы «.», «^» и т.д. вместо из мета-значений («любой символ», «начало строки», «конец строки», …). Для остальных («\d», «\s», …) он означает использовать мета-значение («любая цифра», «любой пробельный символ», …). Договоримся, что значение выше 256 будут означать мета-символ, т.е. (‘d’|0x100) — это «любая цифра», а ‘d’ — буква ‘d’. Ах да, с точной («.») все будет наоборот. Ну и синтаксис.
  • итак, символ или группу мы считали. Теперь проверяем операторы «+», «*», «?» и «-«. Для них — особая функция проверки regex_match_quantity, а в остальных случаях — просто проверяем попадает ли следующий символ строки в группу и идёт дальше (рекурсивно).

Функция проверки попадания символа в группу простая и легко расширяемая:

static int regex_match_group(int c, int group) {
	if ((group & 0xff) == '.') group ^= 0x100;
	if (group < 0x100) { /* a single char */
		return c == group;
	}
	/* a meta char, like \d, ... */
	switch (group & 0xff) {
		case 'd': return isdigit(c);
		case 's': return isspace(c);
		case 'D': return !isdigit(c);
		case 'S': return !isspace(c);
		case '.': return 1;
	}
	return 0;
}

В этой функции мы смотрим — для простых символов кроме точки — просто сравниваем. Для остальных — проверяем группы. С точкой — все наоборот. Я использую функции из ctypes.h, но для простых групп можно и без них обойтись.

Ну и самый кошмарный код в функции regex_match_quantity:

static int regex_match_quantity(int quant, int c, const char *regex, char *s, int *len) {
	if (quant == '?') {
		if (regex_match_group(*s, c)) {
			*len = *len + 1;
			s = s + 1;
		}
		return regex_match_here(regex, s, len);
	}

	if (quant == '+' || quant == '*') { /* match as much as possible */
		char *p;
		for (p = s; *p != '\0' && regex_match_group(*p, c); p++) {
			*len = *len + 1;
		}
		if (quant == '+' && p == s) {
			return 0;
		}
		do {
			if (regex_match_here(regex, p, len)) {
				return 1;
			}
			*len = *len - 1;
		} while (p-- > s);
	} else if (quant == '-') { /* match as little as possible */
		do {
			if (regex_match_here(regex, s, len)) {
				return 1;
			}
			*len = *len + 1;
		} while (*s != '\0' && regex_match_group(*s++, c));
	}
	return 0;
}

Ну для «?» всегда возвращаем 1, но если символ действительно входит в группу — увеличиваем длину совпадающего региона на 1.

Для жадных операторов «+» и «*», которые захватывают как можно больше символов строки — так и поступаем. Проверяем сколько вообще символов строки может попасть в заданную группу, а затем возвращаемся назад пока не найдем соответствие остатка строки остатку регулярного выражения. Для «+» хотя бы один символ строки должен попасть в группу.

Для нежадного оператора «-» просто идёт слева направо пока не совпадет остаток строки с остатком выражения.

Вот и все. У меня получилось 98 строк. Ни одной зависимости. Из libc — только ctype.h, т.е. при особом умении соберется даже каким-нибудь ущербным SmallC. Также никаких особых плюшек С я не использовал, код должен быть переносим и на другие языки, на тот же Forth.

Весь код — как всегда на bitbucket.
Там же и горстка тестов чтобы быть уверенным что все работает как надо.

Вместо выводов

Спасибо Робу Пайку за элегантный и полезный код. Я понимаю, что для серьезных задач такие микро-регекспы не годятся, но для чего-нибудь простенького в embedded — вполне. Тем более лично я считаю, что не стоит делать и регулярных выражений тьюирнг-полный мега-язык, уж лучше бы был способ комбинирования простых регулярных выражений с примесью некоторой простой логики типа условний-циклов.

Здесь кстати тоже стоит отметить работу Роба Пайка о структурных регулярных выражениях. И его текстовый редактор Sam красочный пример их простоты и мощности. Спасибо, Роб.

P.S. Отдельно спасибо, Роб, за язык Go 🙂

Реклама

codesearch is dead, long live the codesearch!

Это произошло. codesearch.google.com или google.com/codesearch больше нет.
Я пользовался этим сервисом часто, и теперь я даже не знаю что делать.
Но, спасибо Робу Пайку и Россу Коксу, которые тоже тяжело переживают эту утрату.
Они начали новый проект — codesearch.

Проект позволяет очень быстро искать по исходникам, правда только на локальной машине, а не на серверах гугла.

Для неленивых

Проект написан на Go. Поэтому все кто собирать его вручную — сначала установите Go.

Затем:

cd $GOROOT/src/pkg
# Возможно go install может установить все автоматически прямо с сайта,
# но у меня не получилось.
mkdir -p code.google.com/p/codesearch
hg clone https://code.google.com/p/codesearch code.google.com/p/codesearch
cd code.google.com/p/codesearch/lib
# buildall перебирает все архитектуры и собирает под все что можно, 
# изучите его, закомментируйте то что вам не надо (напр. упаковку результатов
# сборки в *.zip), и тогда запускайте.
./buildall

После этого у вас в $GOBIN появятся три утилиты: cindex, csearch, cgrep.

Для ленивых

Качаем утилиты с сайта проекта и распаковываем куда удобно.

Начало работы

Проиндексируем какую-нибудь папку, напр. наш /usr/include:

$ cindex /usr/include

В результате получим «базу» для поиска в файле ~/.csearchindex

UPD: Описанный ниже баг уже оперативно исправили.
У меня в 64-битной Gentoo произошла ошибка, cindex не смог смержить пустую базу в .csearchindex и временную базу по /usr/include (.csearchindex~ — с тильдой в конце). Проблема была в том, что делали mmap для размера в 0 байт (файл-то пустой), получали ошибку, и завершали программу. Не знаю, это баг Go или codesearch, но уже сообщил о нем. Временный фикс:
$ cp ~/.csearchindex\~ ~/.csearchindex
Так ведь у нас мержат пустой файл с непустым? 🙂
Это надо делать только для 1-го запуска cindex. Дальше все как по маслу.

Войдя в азарт я проиндексировал /usr/src/linux и еще пару мелких проектов.
Размер ~/.csearchindex составил около 50 Мб, что в целом неплохо для всех include и ядра линукса.

Поиск

Для поиска я использовал csearch. В результатах отображается файл и (опционально) номер строки. Конечно, не так красиво как было у codesearch, но пользоваться можно. Глядишь — web-интерфейс сделают когда-нибудь.

$ csearch hcd_bus_
/usr/src/linux/drivers/usb/core/generic.c:		rc = hcd_bus_suspend(udev, msg);
/usr/src/linux/drivers/usb/core/generic.c:		rc = hcd_bus_resume(udev, msg);
/usr/src/linux/drivers/usb/core/hcd.c:int hcd_bus_suspend(struct usb_device *rhdev, pm_message_t msg)
/usr/src/linux/drivers/usb/core/hcd.c:int hcd_bus_resume(struct usb_device *rhdev, pm_message_t msg)
/usr/src/linux/include/linux/usb/hcd.h:extern int hcd_bus_suspend(struct usb_device *rhdev, pm_message_t msg);
/usr/src/linux/include/linux/usb/hcd.h:extern int hcd_bus_resume(struct usb_device *rhdev, pm_message_t msg);

time вернул: csearch hcd_bus_ 0.02s user 0.01s system 74% cpu 0.031 total. Неплохой показатель, и глазом не моргнул. Старикашка grep тут бы трудился около минуты.

# Смотрим где объявлены функции для работы с интерфейсами в libusb (поиск по regex)
$ csearch -n "libusb_.+_interface"
2012/01/19 22:46:58 56591902 56594432
/usr/include/libusb-1.0/libusb.h:803:int libusb_claim_interface(libusb_device_handle *dev, int iface);
/usr/include/libusb-1.0/libusb.h:804:int libusb_release_interface(libusb_device_handle *dev, int iface);
/usr/include/libusb-1.0/libusb.h:809:int libusb_set_interface_alt_setting(libusb_device_handle *dev,

А вот бы еще…

Проект свою функцию выполняет — ищет, и ищет очень быстро. Но аппетит разыгрался. Хочу инверсный поиск (все что не regex), хочу текст до и после совпадающей строки, хочу цепочки фильтров, хочу упрощенный синтаксис наряду с regex, хочу красивый интерфейс (ох как непривычно от самого себя такое слышать). Другие пожелания думаю тоже можно в Issue ребятам писать, так что не скромничайте.

А может взять да и форкнуть? И сделать круто? Робу Пайку думаю не до интерфейсов, а вот самому сделать бы да покрасивше.. Или может взять дерево исходников, скажем, ядра или андроида, да сделать проект на Google App Engine для быстрого поиска по этому дереву прям онлайн, чтобы себе репозитории огромные не качать. Круто, да? Ау, есть желающие? У кого какие еще есть идеи?

Усатый-полосатый

Однажды мне пришлось написать.. Ну не важно что именно, важно что при решении задачи нужно было использовать шаблоны (только не те, которые patterns, и не те которые generics, а те которые templates).
Писал я это все на питоне. И вот что я узнал (истины вообщем-то общеизвестные, просто я чайник в питоне, да и в шаблонах тоже). Читать далее