Глава 30 Движок регулярных выражений

Ориентация главы

xregex — движок регулярных выражений XRT; три инженерных решения определяют его характер: небэктрекинговый движок — время сопоставления линейно по длине входа, катастрофический бэктрекинг (ReDoS) структурно невозможен, недоверенный текст сопоставляется безопасно; разделение компиляции и сопоставления — xrtRegexCompile порождает неизменяемый объект со счётом ссылок (скомпилировали один раз — разделяете везде), а xregexmatcher — кеш исполнения, эксклюзивный для каждого прохода (повторные сканы одного текста — ноль повторных распределений); именованные захваты — (?<name>...) читаются по имени группы, заменяя хрупкие числовые номера. Глава разъясняет употребление и выигрыш всех трёх решений; сам синтаксис регулярных выражений дан шпаргалкой стандартного подмножества.В финале глава приглашает его ограниченного родича — xpattern: когда форма матчинга — структура захвата {name} (маршруты, ключи конфигурации) и один текст диспетчеризируется против десятков образцов, он быстрее и проще regex.

30.1引入

Две реальные аварии. Первая: служба журналов сопоставляла пользовательские выражения фильтрации бэктрекинговым движком; шаблон в духе ^(a+)+$ гонял одно сопоставление тридцать секунд — очередь росла, сервис впал в анабиоз; такой «катастрофический бэктрекинг» — структурный дефект бэктрекинговых движков: запись шаблона определяет худшую сложность. Вторая: в разборе конфигурации группы захвата (\w+)=(\d+) читались по номерам — мейнтейнер вставил группу в середину, все номера сдвинулись на единицу, все чтения ниже по течению разошлись, а компилятор не сказал ни слова.

xregex невосприимчив к обеим авариям: худший случай небэктрекингового движка линеен — «плохих шаблонов» не бывает, бывают «чуть более медленные»; именованные захваты (?<key>\w+)=(?<value>\d+) читаются по имени — добавление и изменение групп не тревожит существующий код чтения. Добавьте сюда дизайн жизненного цикла «скомпилированный объект неизменяем и разделяем, матчер — эксклюзивный кеш», и вы получите движок, подготовленный к долгой работе на сервере.

30.2概念

Жизненный цикл: два слоя — компиляция и сопоставление

Слой компиляции неизменяем: один и тот же xregex* разделяется многими потоками и многими матчерами и никогда не модифицируется — жизнью и смертью его управляет подсчёт ссылок (тот же примитив, что и в главе 30). Слой матчера эксклюзивен: каждый проход держит собственный кеш (позиции, слоты захвата), и повторные сканы одного текста переиспользуют кеш — сто сканов инициализируются один раз. Разделение слоёв делает выполнимой модель стоимости «скомпилировали один раз — сопоставили миллион раз».

Небэктрекинг: гарантия линейности

Бэктрекинговый движок при неудаче перебирает все пути — некоторые шаблоны взрывают число путей экспоненциально (корень ReDoS). Небэктрекинговый движок (линия NFA/DFA) отслеживает все возможные состояния одновременно и обрабатывает каждый входной символ ровно один раз — худшее время линейно по длине входа. Инженерное следствие: у времени сопоставления есть жёсткий верхний предел — его можно спокойно ставить на пути запросов и на недоверенный вход. Плата — чуть больший постоянный множитель на некоторых шаблонах: незаметно для подавляющего большинства, зато в обмен на определённость «плохих шаблонов нет».

Именованные захваты и замена

(?<name>[A-Za-z_]+)=(?<value>\d+) определяет две именованные группы; xrtRegexMatcherCaptureNamed(匹配器, "value", ...) (матчер, "value", ...) вычитает по имени представление текста и диапазон. Замена xrtRegexReplace(编译对象, 文本, 替换, ...) (скомпилированный объект, текст, замена, ...) поддерживает номерные ссылки $1/$2 (у именованных групп есть и неявные номера); xrtRegexEscape экранирует произвольный текст в форму «сопоставлять буквально» — обязательный шаг перед вклейкой пользовательского ввода в шаблон. xrtRegexFullTest решает «полное совпадение всей строки», дополняя семантику «найти подстроку» у Find.

Когда regex избыточен: структурное сопоставление образцов (pattern)

regex отвечает на «один текст против одного образца»; pattern отвечает на «один текст против набора образцов» — стандартная форма таблиц маршрутизации, ключей конфигурации и диспетчеризации команд. Синтаксис имеет ровно три элемента: литеральные поля совпадают побайтово точно; {name} захватывает одно непустое поле (никогда не пересекая разделитель — по умолчанию /; xpatternconfig.Separators настраивает множество байтов); {*name} может стоять только в конце, захватывая остаток и допуская пустоту. {{ и }} экранируют литеральные фигурные скобки. Никакого метаязыка, квантификаторов и ветвления — три прямых следствия: небэктрекинг выполняется по построению (взрываться нечему); нет ловушек экранирования (ввод пользователя — всегда сопоставляемый текст, никогда ингредиент образца — ловушка 2 здесь структурно исчезает); сопоставление заякорено на полный ввод (без нормализации пути, URL-декодирования или свёртки регистра — это работа глав 102/105; в этом и есть слоистость).

Исход использует трёхзначный xpatternresult: XPATTERN_ERROR / XPATTERN_NONE / XPATTERN_MATCH — промах не ошибка (та же философия, что у xwaitresult главы 9: поток управления отделён от ошибок). Жизненный цикл многих образцов зеркален regex: xrtPatternBuilderCreate регистрирует десятки образцов нарастающе, xrtPatternBuilderCompile компилирует их за один раз в единую детерминированную программу (неизменяемая, долгоживущая; строитель освобождается сразу после); при попадании Match.Value напрямую возвращает бизнес-идентичность, данную при регистрации (скажем "user"), а Match.Index — номер образца — ключ диспетчеризации встроен, не нужно заново разбирать семантику групп захвата. Разовые случаи обходятся xrtPatternExtract — извлечением по всей строке без компиляции. Четыре потолка бюджета (байты образцов / число образцов / захваты / скомпилированные байты) отсекают раздувание памяти недоверенными образцами; ошибки превышения несут байтовое смещение внутри образца (xrtPatternErrorOffset). Разделение одной строкой: нужно «описание формы плюс квантификаторы и ветвление» — regex; нужно «нарезка полей плюс диспетчеризация многих образцов» — pattern — таблица маршрутов главы 105 и классификация журналов главы 138 стоят на этой стороне.

Шпаргалка подмножества синтаксиса

Синтаксис — общее подмножество мейнстримных движков: без обратных ссылок и заглядывания (формы, которые небэктрекинговый движок не поддерживает; документация говорит об этом прямо, а не молча игнорирует).

30.3示例

Полная программа: компиляция, сопоставление и именованный захват

Из образца репозитория examples/text/regex/main.c — извлечение width=128 и height=72 из текста конфигурации:

 */

#include <stdio.h>

#include <xrt.h>



int main(void)
{
	/* 命名组 (?<name>...) (?<value>...)：语义比数字下标清晰。 */
	xregex* pRegex = xrtRegexCompile(
		XRT_STR_LITERAL("(?<name>[A-Za-z]+)=(?<value>\\d+)")
	);
	xregexmatcher* pMatcher;
	xregexcapture Name;
	xregexcapture Value;
	xstrview Text = XRT_STR_LITERAL("width=128 height=72");
	str sLiteral;
	size_t iLiteralSize;

	if ( pRegex == NULL ) {
		return 1;
	}

	/* 匹配器持有正则的自身引用：这里可先释放本地引用。 */
	pMatcher = xrtRegexMatcherCreate(pRegex);
	xrtRegexRelease(pRegex);
	if ( pMatcher == NULL ) {
		return 2;
	}

	


	 */
	for ( xregexresult Result = xrtRegexMatcherFind(pMatcher, Text, 0);
		 Result == XREGEX_MATCH;
		 Result = xrtRegexMatcherNext(pMatcher) ) {
		if ( !xrtRegexMatcherCaptureNamed(pMatcher, XRT_STR_LITERAL("name"), &Name) ||
			 !xrtRegexMatcherCaptureNamed(pMatcher, XRT_STR_LITERAL("value"), &Value) ) {
			xrtRegexMatcherFree(pMatcher);
			return 3;
		}
		printf(
			"%.*s = %.*s\n",
			(int)Name.Text.Size,
			Name.Text.Data,
			(int)Value.Text.Size,
			Value.Text.Data
		);
	}
	xrtRegexMatcherFree(pMatcher);

	


	 */
	sLiteral = xrtRegexEscape(XRT_STR_LITERAL("file[1].txt"), &iLiteralSize);
	if ( sLiteral == NULL ) {
		return 4;
	}
	pRegex = xrtRegexCompile(xrtStrViewN(sLiteral, iLiteralSize));
	xrtFree(sLiteral);
	if ( pRegex == NULL ) {
		return 5;
	}
	if ( xrtRegexFullTest(pRegex, XRT_STR_LITERAL("file[1].txt")) != XREGEX_MATCH ) {
		xrtRegexRelease(pRegex);
		return 6;
	}
	xrtRegexRelease(pRegex);
	return 0;
}

Что только что произошло. (1) xrtRegexCompile компилирует один раз в неизменяемый объект — здесь он используется локально и в конце Release-ится; в долгоживущих сценариях он висит на глобальной переменной (компиляция на старте, освобождение на выходе), и каждое сопоставление лишь берёт ссылку. (2) После создания матчера Find находит первое совпадение от смещения 0 — группа (?<key>...) захватывает пару имён. (3) CaptureNamed("key") и CaptureNamed("value") вычитают представления по имени — это устойчивее к рефакторингу, чем номерное чтение $1/$2. (4) В цикле Next продвигает к следующему совпадению — width и height отсканированы и выведены каждый; кеш матчера переиспользуется между сопоставлениями. (5) Весь процесс несёт ноль риска «катастрофического бэктрекинга» — небэктрекинговый движок сканирует линейно на любом шаблоне.

Полная программа: замена и экранирование

Из examples/text/regex_replace/main.c — массовая перезапись name=value в name: value:

 */

#include <stdio.h>

#include <xrt.h>



int main(void)
{
	/* 两个命名组：name 与 value（数字编号分别是 1、2）。 */
	xregex* pRegex = xrtRegexCompile(
		XRT_STR_LITERAL("(?<name>[A-Za-z_]+)=(?<value>\\d+)")
	);
	str sResult;

	if ( pRegex == NULL ) {
		return 1;
	}

	/* "name=value" → "name: value"：$1 组与 $2 组各就各位。 */
	sResult = xrtRegexReplace(
		pRegex,
		XRT_STR_LITERAL("width=128 height=72"),
		XRT_STR_LITERAL("${name}: $2")
	);
	xrtRegexRelease(pRegex);
	if ( sResult == NULL ) {
		return 2;
	}
	puts(sResult);
	xrtFree(sResult);
	return 0;
}

Что только что произошло. (1) Тот же шаблон с именованными группами, на этот раз через xrtRegexReplace — $1 и $2 ссылаются на группы захвата (у именованных групп неявные номера 1 и 2). (2) Продукт замены — владеющая строка (освобождение xrtFree). (3) В этом образце Escape не понадобился, но запишите: перед вклейкой пользовательского ввода в шаблон обязателен xrtRegexEscape — скобки во вводе вроде a(b суть синтаксические символы; без экранирования получится нелегальный шаблон или ложное сопоставление (герой ловушки 2).

Полная программа: pattern — захват {name} в стиле маршрутов

Из репозиторного образца examples/text/pattern/main.c — один образец маршрута; попадание и есть диспетчеризация:

 */

#define XRT_MODULE_PATTERN
#include <xrt.h>

#include <stdio.h>



int main(void)
{
	xpatternbuilder* pBuilder = xrtPatternBuilderCreate();

	/* 规格四元组：模板 / 业务标识 / 预算标志（0=默认）。 */
	xpatternspec Spec = {
		XRT_STR_INIT("/users/{group}/item-{id}.json"),
		(ptr)"user",
		0,
		0
	};
	xpattern* pPattern;
	xpatternmatch Match;
	xstrview arrCapture[2];

	/* 注册一条模式（真实路由表会注册几十条再一次编译）。 */
	if ( (pBuilder == NULL) ||
		 (xrtPatternBuilderAdd(pBuilder, &Spec) == XPATTERN_ID_INVALID) ) {
		xrtPatternBuilderFree(pBuilder);
		return 1;
	}

	/* 编译产物不可变、可长期持有；构建器即可释放。 */
	pPattern = xrtPatternBuilderCompile(pBuilder);
	xrtPatternBuilderFree(pBuilder);
	if ( pPattern == NULL ) {
		return 1;
	}

	



	 */
	if ( xrtPatternMatch(
		pPattern,
		XRT_STR_LITERAL("/users/admin/item-42.json"),
		arrCapture,
		2u,
		&Match
	) == XPATTERN_MATCH ) {
		printf(
			"kind=%s group=%.*s id=%.*s\n",
			(cstr)Match.Value,
			(int)arrCapture[0].Size,
			arrCapture[0].Data,
			(int)arrCapture[1].Size,
			arrCapture[1].Data
		);
	}
	xrtPatternRelease(pPattern);
	return 0;
}

Что только что произошло. (1) Четвёрка xpatternspec: шаблон, бизнес-идентичность ("user" — ключ диспетчеризации попадания), флаги бюджета; настоящая таблица маршрутов регистрирует десятки до одной компиляции. (2) Нарастающая регистрация строителем → Compile даёт неизменяемый объект → строитель можно освободить немедленно — та же дисциплина жизненного цикла, что у скомпилированного объекта regex. (3) xrtPatternMatch пишет захваты в массив вызывающего в порядке объявления шаблона (group первым, id вторым); захваты — представления, заимствующие ввод (дисциплина главы 3). (4) Одна строка вывода даёт все три элемента диспетчеризации: Match.Value (какой класс маршрута), два захваченных сегмента (параметры) — весь вход HTTP-обработчика маршрута умещается в этой строке.

30.4契约

• Гарантия линейности: небэктрекинговый движок; худшее время сопоставления линейно по длине входа — катастрофического бэктрекинга не существует.
• Двухслойный жизненный цикл: скомпилированный объект неизменяем и разделяется счётом ссылок; кеш матчера эксклюзивен, по одному на проход.
• Именованные захваты: определение (?<name>...), чтение CaptureNamed; номерная ссылка $1 тоже доступна.
• Дисциплина экранирования: динамическое содержимое обязано пройти xrtRegexEscape перед входом в шаблон.
• Разграничение семантик: Find ищет подстроку, FullTest решает всю строку — выбирайте по потребности, не имитируйте через ^...$.
• Подмножество синтаксиса: общее ядро мейнстрима; обратные ссылки и заглядывание не поддерживаются — документировано явно, без умолчаний.
• Границы pattern: якорь на полную строку; захваты заимствуют входной текст; ошибки живут в домене xrt.pattern, xrtPatternErrorOffset даёт байтовое смещение в образце; промах — это NONE, не ошибка.

От примеров к инженерии: три хозяина регулярных выражений

Слой валидации: проверка легальности ввода (правила имени пользователя, форматы SKU) — шаблоны статически компилируются в глобальные, на каждый запрос строится только матчер, FullTest решает всю строку. Три дисциплины валидационных шаблонов: якорить где можно (^...$ или семантика FullTest), белый список множеств символов лучше чёрного, сообщение об отказе объясняет формат. Слой извлечения: добыча данных из полуструктурного текста (поля журналов, строки конфигурации) — именованные захваты плюс полный скан Next, результаты уходят в дерево значений или бизнес-структуры; это одна из промежуточных станций текстового конвейера главы 36. Слой замены: шаблонная перепись (конвертация форматов, маскирование данных) — ссылки на захваты Replace держат логику пересборки внутри строки замены. Всем трём слоям общая дисциплина производительности: компиляция на старте, сопоставление на горячем пути — хорошая форма ловушки 1 и есть общий каркас кода всех трёх.

Разделение труда со строковым семейством и глобами

Когда три инструмента сопоставления текста из главы 25 уступают место регулярным выражениям? Буквенный поиск (найти фиксированный ERROR) — xrtStrFind, накладные расходы регулярных выражений не нужны; простые глоб-шаблоны (*.log) — xrtStrGlob, проще и быстрее; структурные шаблоны« («три цифры в группе, соединены дефисами») — вотчина регулярных выражений. Мнемоника: если шаблон формулируется одной фразой — хватит строкового инструмента; «описание формы» требует регулярного выражения**. Цена злоупотребления — не только производительность: читаемость, сопровождаемость и ловушки экранирования (ловушка 2) все ждут своего часа; код с правильно выбранным инструментом объясняет сам себя на ревью.

Взгляд на тестирование: шаблон — тоже код

Регулярный шаблон — сгущённый код, и он заслуживает кодового обращения. Три привычки: именовайте шаблоны — static const char* PATTERN_SKU = "..." плюс комментарий о намерении, а не россыпь по точкам вызова; наборы граничных случаев — каждому шаблону тройка «должен совпасть/не должен/граница» (пересадка идеи граничных значений главы 26), регресс при каждом изменении шаблона; выборочный замер производительности — прогоняйте показательные входы через статистику главы 6 или простое таймирование, подтверждая отсутствие сюрпризов в константах. Воспроизводимая случайность главы 11 (генерация уродливых входов с фиксированным семенем) даёт фаззингу шаблонов готовый инструмент — эти дисциплины будут систематизированы вновь в главе 132.

Типичные ошибки

bool handle(const char* sFilter)
{
	xregex* pRegex = xrtRegexCompile((xstrview){ sFilter, strlen(sFilter) });
	/* ... одно сопоставление ... */
	xrtRegexRelease(pRegex);   /* компиляция+освобождение на каждый запрос - автомат построен зря */
}

/* компиляция один раз на старте, глобальное разделение */
static xregex* gFilter;
void init(void) { gFilter = xrtRegexCompile(XRT_STR_LITERAL("...")); }
bool handle(const char* sText)
{
	/* строим только матчер (лёгкий); скомпилированный объект даёт ссылку */
	xregexmatcher* M = xrtRegexMatcherCreate(gFilter, Text);
	/* ... Find/Next ... */
	xrtRegexMatcherFree(M);
}

xstrview UserInput = ...;
xstrbuf Pat;
xrtStrBufInit(&Pat);
xrtStrBufAppend(&Pat, XRT_STR_LITERAL("^"));
xrtStrBufAppend(&Pat, UserInput);          /* "(admin)" входит в шаблон - синтаксические символы! */
xrtStrBufAppend(&Pat, XRT_STR_LITERAL("$"));
str sPat = xrtStrBufTake(&Pat);
xregex* R = xrtRegexCompile((xstrview){ sPat, strlen(sPat) });   /* компиляция падает или инъекция */

xstrbuf Pat;
xrtStrBufInit(&Pat);
xrtStrBufAppend(&Pat, XRT_STR_LITERAL("^"));
str sEscaped = xrtRegexEscape(UserInput, NULL);
xrtStrBufAppend(&Pat, (xstrview){ sEscaped, strlen(sEscaped) });  /* после экранирования - чистый литерал */
xrtFree(sEscaped);
xrtStrBufAppend(&Pat, XRT_STR_LITERAL("$"));

Практические задания

Итоги