第 30 章 正则引擎 regex

本章导读

xregex 是 XRT 的正则引擎，三个工程决策定义了它的性格：非回溯引擎——匹配时间与输入长度线性相关，灾难回溯（ReDoS）在结构上不存在，不受信任的文本也能安全匹配；编译/匹配分离——xrtRegexCompile 产出不可变的引用计数对象（编译一次处处共享），xregexmatcher 是每次遍历独占的执行缓存（同一文本反复扫描零重复分配）；命名捕获——(?<name>...) 按组名读取，替代脆弱的数字编号。本章讲清这三个决策的用法与收益，正则语法本身按标准子集速查。

30.1引入

两个真实事故。事故一：日志服务用回溯引擎匹配用户提交的过滤表达式，一个 ^(a+)+$ 风格的模式让单条匹配跑了三十秒——队列积压、服务假死；这类"灾难回溯"是回溯引擎的结构性缺陷，模式写法决定了最坏复杂度。事故二：配置解析里 (\w+)=(\d+) 的捕获组靠编号取值——维护者在中间加了一个分组，所有编号右移一位，下游取值全部错位，编译器毫无怨言。

xregex 对两个事故都免疫：非回溯引擎的最坏时间是线性的——不存在"坏模式"，只有"慢一点的模式"；命名捕获 (?<key>\w+)=(?<value>\d+) 按名字取值——加组、改组都不影响既有取值代码。再加上"编译对象不可变可共享、匹配器独占缓存"的生命周期设计，它就是为服务端长期运行准备的引擎。本章收尾还会请出它的受限表亲——xpattern：当匹配的形状是"路由/配置键"这类 {name} 捕获结构、且要一次对几十条模式分发时，它比正则更快也更省心。

30.2概念

生命周期：编译与匹配两层

编译层不可变：同一个 xregex* 被多个线程、多个匹配器共享，永不修改——引用计数（第 30 章同款原语）管它的生死。匹配器层独占：每次遍历持有自己的缓存（回溯位置、捕获槽），同一文本反复扫描时缓存复用——扫一百遍只初始化一次。两层分离让"编译一次、匹配百万次"的成本模型成立。

非回溯：线性保证

回溯引擎在失败时尝试所有路径——某些模式让路径数指数爆炸（ReDoS 的根源）。非回溯引擎（NFA/DFA 派）同时跟踪所有可能状态，每个输入字符只处理一遍——最坏时间与输入长度线性相关。工程含义：匹配耗时有了硬上界，可以放心地用在请求路径与不受信任输入上。代价是对某些模式常数略大——对绝大多数模式无感，换来的是"没有坏模式"的确定性。

命名捕获与替换

(?<name>[A-Za-z_]+)=(?<value>\d+) 定义两个命名组；xrtRegexMatcherCaptureNamed(匹配器, "value", ...) 按名读出文本视图与范围。替换 xrtRegexReplace(编译对象, 文本, 替换, ...) 支持 $1/$2 编号引用（命名组同时有隐含编号）；xrtRegexEscape 把任意文本转义成"字面匹配"的形式——把用户输入拼进模式前必经的一步。xrtRegexFullTest 判"整串完全匹配"，与"找子串"的 Find 语义互补。

当正则太重：结构化模式匹配（pattern）

regex 回答"一个文本对一个模式"；pattern 回答"一个文本对一组模式"——路由表、配置键、命令分发的标准形态。它的语法只有三种元素：字面字段按字节精确匹配；{name} 捕获一个非空字段（不跨越分隔符——默认 /，xpatternconfig.Separators 可配成字节集合）；{*name} 只能位于模式末尾、捕获剩余文本且允许为空。{{ 与 }} 转义字面花括号。没有元语言、没有量词与分支——三个直接后果：非回溯天然成立（无从爆炸）；没有转义陷阱（用户输入永远是被匹配的文本而不是模式成分——坑 2 在这里结构性消失）；匹配锚定完整输入（不做路径规范化、URL 解码或大小写折叠——那些是第 101、104 章的职责，分层即此意）。

结果用三态 xpatternresult 表达：XPATTERN_ERROR / XPATTERN_NONE / XPATTERN_MATCH——未命中不是错误（与第 9 章 xwaitresult 同一哲学：控制流与错误分开）。多模式的生命周期与 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;
}

刚才发生了什么。 ① xrtRegexCompile 编译一次得到不可变对象——本例局部使用、结尾 Release；长期场景挂在全局（启动编译、退出释放），每次匹配只借引用。② 匹配器创建后 Find 从偏移 0 找首个匹配——(?<key>...) 捕获组名对。③ CaptureNamed("key") 与 CaptureNamed("value") 按名读出文本视图——比 $1/$2 的编号取值抗重构。④ 循环里 Next 推进到下一个匹配——width 与 height 各扫一遍输出；匹配器的缓存在两次匹配间复用。⑤ 整个过程零"灾难回溯"风险——非回溯引擎对任何模式都是线性扫描。

完整程序：替换与转义

来自 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;
}

刚才发生了什么。 ① 同样的命名组模式，这次走 xrtRegexReplace——$1 与 $2 引用捕获组（命名组有隐含编号 1、2）。② 替换产物是拥有式字符串（xrtFree 释放）。③ 这个示例没有用 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;
}

刚才发生了什么。 ① xpatternspec 规格四元组：模板、业务标识（"user"——命中的分发键）、预算标志；真实路由表会注册几十条再一次编译。② Builder 增量注册 → Compile 产出不可变对象 → 构建器即可释放——与 regex 编译对象同一生命周期纪律。③ xrtPatternMatch 捕获按模板声明顺序写入调用方数组（group 在前、id 在后），捕获是借用输入文本的视图（第 3 章纪律）。④ 输出行一次拿到三个分发要素：Match.Value（哪类路由）、两个捕获段（参数值）——HTTP 路由处理器的全部输入就在这一行里。

30.4契约

• 线性保证：非回溯引擎，最坏匹配时间与输入长度线性相关——不存在灾难回溯模式。
• 两层生命周期：编译对象不可变、引用计数共享；匹配器独占缓存、每次遍历一个。
• 命名捕获：(?<name>...) 定义、CaptureNamed 读取；编号引用 $1 同时可用。
• 转义纪律：动态内容进模式前必经 xrtRegexEscape。
• 语义区分：Find 找子串、FullTest 判整串——按需求选，不要用 ^...$ 模拟。
• 语法子集：主流公共子集；回溯引用与前瞻不支持——文档写明而非静默。
• pattern 边界：完整串锚定；捕获借用输入文本；错误在 xrt.pattern 域、xrtPatternErrorOffset 给模式内字节位置；未命中是 NONE 不是错误。

从示例到工程：正则的三个宿主

验证层：输入合法性检查（用户名规则、SKU 格式）——模式静态编译为全局，每请求只建匹配器、FullTest 判整串。验证模式的三个纪律：尽量锚定（^...$ 或 FullTest 语义）、字符集白名单优于黑名单、失败消息带上格式说明。提取层：从半结构化文本抽数据（日志字段、配置行）——命名捕获 + Next 全扫，提取结果进值树或业务结构；这是第 36 章文本管线的中间站之一。替换层：模板化改写（格式转换、脱敏）——Replace 的捕获引用把重组逻辑留在替换串里。三层都适用同一条性能纪律：编译在启动、匹配在热路径——坑 1 的 good 形态是三层共同的代码骨架。

与字符串族、通配的分工

第 25 章的三种文本匹配工具什么时候让位给正则？字面查找（找固定的 ERROR）用 xrtStrFind——不需要正则的开销；简单通配（*.log）用 xrtStrGlob——更简单更快；结构模式（"三个数字一段、用横线连接"）才是正则的领地。口诀：模式能用一句话说清就能用字符串工具；需要"形状描述"才上正则。滥用正则的代价不只是性能——可读性、可维护性、转义陷阱（坑 2）全在等着；用对了工具的代码，评审时自己会解释自己。

一个测试观：模式也是代码

正则模式是浓缩的代码——它该享受代码的待遇。三个习惯：模式命名——static const char* PATTERN_SKU = "..." 加一句注释说明意图，不要散落在调用点；边界用例集——每个模式配"应命中/不应命中/边界"三组样例（第 26 章边界值思想的移植），模式修改时回归；性能抽样——用第 6 章统计或简单计时对代表性输入跑一遍，确认无常数意外。第 11 章的可复现随机（固定种子生成畸形输入）给模式的模糊测试提供了现成工具——这些纪律在第 133 章测试体系会再次系统化。

常见错误

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("$"));

编程练习

小结