Chapter 30 The Regex Engine

Chapter Orientation

xregex is XRT's regex engine; three engineering decisions define its character: a non-backtracking engine — matching time is linear in input length, catastrophic backtracking (ReDoS) is structurally impossible, and untrusted text can be matched safely; compile/match separation — xrtRegexCompile produces an immutable reference-counted object (compile once, share everywhere), while xregexmatcher is an execution cache exclusive to each traversal (repeated scans of the same text do zero re-allocation); and named captures — (?<name>...) read by group name, replacing fragile numeric indices. This chapter makes the usage and payoff of the three decisions clear; the regex syntax itself is covered as a standard-subset cheat sheet. The chapter closes by bringing in its restricted cousin — xpattern: when the matching shape is a {name}-capture structure like routes or configuration keys and one text must dispatch against dozens of patterns, it is faster and simpler than regex.

30.1引入

Two real incidents. Incident one: a log service matched user-submitted filter expressions with a backtracking engine; a ^(a+)+$-style pattern made a single match run for thirty seconds — queues backed up, the service went catatonic. This "catastrophic backtracking" is a structural defect of backtracking engines: the way a pattern is written determines its worst-case complexity. Incident two: in config parsing, the capture groups of (\w+)=(\d+) were read by number — a maintainer inserted one group in the middle, every index shifted by one, all downstream reads misaligned, and the compiler complained about nothing.

xregex is immune to both incidents: a non-backtracking engine's worst case is linear — there are no "evil patterns", only "slightly slower patterns"; the named captures of (?<key>\w+)=(?<value>\d+) are read by name — adding or changing groups never disturbs existing read code. Add the lifecycle design of "compiled objects immutable and shareable, matchers exclusive caches", and you have an engine built for long-running servers.

30.2概念

Lifecycle: the compile and match layers

The compile layer is immutable: the same xregex* is shared by multiple threads and multiple matchers and never modified — reference counting (the same primitive as Chapter 30) manages its life and death. The matcher layer is exclusive: each traversal holds its own cache (backtrack positions, capture slots), and repeated scans of the same text reuse that cache — a hundred scans initialize once. The two-layer separation makes the "compile once, match a million times" cost model hold.

Non-backtracking: the linear guarantee

A backtracking engine, on failure, tries every path — some patterns make the path count explode exponentially (the root of ReDoS). A non-backtracking engine (NFA/DFA descent) tracks all possible states simultaneously and processes each input character exactly once — worst-case time is linear in input length. The engineering meaning: matching time has a hard upper bound, so it can be used confidently on request paths and untrusted input. The cost is a slightly larger constant on some patterns — imperceptible for the overwhelming majority, in exchange for the certainty that "there are no evil patterns".

Named captures and replacement

(?<name>[A-Za-z_]+)=(?<value>\d+) defines two named groups; xrtRegexMatcherCaptureNamed(匹配器, "value", ...) (matcher, "value", ...) reads out the text view and range by name. Replacement xrtRegexReplace(编译对象, 文本, 替换, ...) (compiled object, text, replacement, ...) supports $1/$2 numeric references (named groups carry implicit numbers too); xrtRegexEscape escapes arbitrary text into a "match literally" form — the mandatory step before splicing user input into a pattern. xrtRegexFullTest decides "whole-string exact match", complementing Find's "find a substring" semantics.

When regex is too heavy: structured pattern matching (pattern)

Regex answers "one text against one pattern"; pattern answers "one text against a set of patterns" — the standard shape of routing tables, configuration keys, and command dispatch. Its syntax has exactly three elements: literal fields match bytes exactly; {name} captures one non-empty field (never crossing a separator — / by default; xpatternconfig.Separators configures the byte set); {*name} may only sit at the end, capturing the remainder and allowing empty. {{ and }} escape literal braces. No metalanguage, no quantifiers or alternation — three immediate consequences: non-backtracking holds by construction (nothing to explode); no escaping traps (user input is always the text being matched, never a pattern ingredient — pitfall 2 structurally disappears here); matching is anchored to the full input (no path normalization, URL decoding, or case folding — those are Chapter 102/105 jobs; layering is the point).

The outcome uses the three-state xpatternresult: XPATTERN_ERROR / XPATTERN_NONE / XPATTERN_MATCH — a miss is not an error (the same philosophy as Chapter 9's xwaitresult: control flow separated from errors). The multi-pattern lifecycle mirrors regex: xrtPatternBuilderCreate registers dozens of patterns incrementally, xrtPatternBuilderCompile compiles them once into a single deterministic program (immutable, long-lived; the builder is freed right after); on a hit, Match.Value directly returns the business identity given at registration (say "user") and Match.Index the pattern number — the dispatch key is built in, no capture-group semantics to re-parse. One-shot cases can use xrtPatternExtract for whole-string extraction without compiling. Four budget ceilings (pattern bytes / pattern count / captures / compiled bytes) block untrusted patterns from ballooning memory; overflow errors carry the in-pattern byte offset (xrtPatternErrorOffset). The division in one line: need "shape description plus quantifiers and alternation" — regex; need "field splitting plus multi-pattern dispatch" — pattern — Chapter 105's routing table and Chapter 138's log classification both stand on this side.

Syntax-subset cheat sheet

The syntax is the common subset of mainstream regex — no backreferences and no lookahead (forms the non-backtracking engine does not support; the documentation says so explicitly rather than silently ignoring them).

30.3示例

Complete program: compile, match, and named capture

From the repository sample examples/text/regex/main.c — extracting width=128 and height=72 from configuration text:

 */

#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;
}

What just happened. (1) xrtRegexCompile compiles once to an immutable object — this example uses it locally and Releases at the end; in long-running scenarios it hangs on a global (compiled at startup, released at shutdown), and each match merely borrows a reference. (2) After the matcher is created, Find locates the first match from offset 0 — the (?<key>...) group captures the name pair. (3) CaptureNamed("key") and CaptureNamed("value") read out text views by name — more refactor-proof than $1/$2 numeric reads. (4) In the loop, Next advances to the next match — width and height each scanned and printed; the matcher's cache is reused across matches. (5) The whole process carries zero "catastrophic backtracking" risk — the non-backtracking engine scans linearly for any pattern.

Complete program: replacement and escaping

From examples/text/regex_replace/main.c — batch-rewriting name=value into 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;
}

What just happened. (1) The same named-group pattern, this time through xrtRegexReplace — $1 and $2 reference the capture groups (named groups carry the implicit numbers 1, 2). (2) The replacement product is an owning string (freed with xrtFree). (3) This sample doesn't use Escape, but note it here: before user input is spliced into a pattern, xrtRegexEscape is mandatory — the parentheses in a user input like a(b are syntax characters; unescaped, they form an illegal pattern or a wrong match (Pitfall 2's protagonist).

Complete program: pattern — routing-style {name} capture

From the repository example examples/text/pattern/main.c — one route pattern; a hit is a dispatch:

 */

#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;
}

What just happened. (1) The xpatternspec quadruple: template, business identity ("user" — the dispatch key of the hit), budget flags; a real routing table registers dozens before one compile. (2) Builder incremental registration → Compile yields an immutable object → the builder can be freed immediately — the same lifecycle discipline as the regex compiled object. (3) xrtPatternMatch writes captures into the caller's array in template declaration order (group first, id second); captures are views borrowing the input text (Chapter 3's discipline). (4) One output line yields all three dispatch essentials: Match.Value (which route class), two captured segments (the parameters) — the entire input of an HTTP route handler is in that line.

30.4契约

• Linear guarantee: non-backtracking engine; worst-case matching time is linear in input length — no catastrophic-backtracking patterns exist.
• Two-layer lifecycle: the compiled object is immutable and shared by reference counting; the matcher's cache is exclusive, one per traversal.
• Named captures: defined with (?<name>...), read with CaptureNamed; the numeric reference $1 remains available.
• Escaping discipline: dynamic content must pass xrtRegexEscape before entering a pattern.
• Semantic distinction: Find finds substrings, FullTest decides whole strings — choose by need; don't simulate with ^...$.
• Syntax subset: the mainstream common subset; backreferences and lookahead unsupported — documented explicitly, not silently.
• pattern boundary: full-string anchored; captures borrow the input text; errors live in the xrt.pattern domain with xrtPatternErrorOffset giving the in-pattern byte offset; a miss is NONE, not an error.

From examples to engineering: three hosts of regex

Validation layer: input legality checks (username rules, SKU formats) — patterns compile statically into globals; each request only builds a matcher, and FullTest decides whole strings. Three disciplines for validation patterns: anchor whenever possible (^...$ or FullTest semantics), whitelist character sets over blacklists, and failure messages that explain the format. Extraction layer: pulling data from semi-structured text (log fields, config lines) — named captures plus a full Next scan, with extraction results going into a value tree or business structs; this is one midway station of Chapter 36's text pipeline. Replacement layer: templated rewriting (format conversion, data masking) — Replace's capture references keep the reassembly logic inside the replacement string. All three layers share one performance discipline: compile at startup, match on the hot path — Pitfall 1's good form is the shared code skeleton of all three.

The division of labor with the string family and globs

When do Chapter 25's three text-matching tools yield to regex? Literal search (finding a fixed ERROR) uses xrtStrFind — no regex overhead needed; simple globs (*.log) use xrtStrGlob — simpler and faster; structural patterns ("three digits per group, joined by hyphens") are regex territory. The mnemonic: if the pattern can be stated in one sentence, a string tool suffices; only "shape descriptions" need regex. The cost of regex abuse is not just performance — readability, maintainability, and escape traps (Pitfall 2) all lie in wait; code that uses the right tool explains itself in review.

A testing view: patterns are code too

A regex pattern is condensed code — it deserves code's treatment. Three habits: name your patterns — static const char* PATTERN_SKU = "..." plus a one-line comment on intent, not scattered across call sites; boundary case sets — every pattern ships with "should match / should not match / boundary" sample groups (a transplant of Chapter 26's boundary-value thinking), regression-run when the pattern changes; performance sampling — run representative inputs through Chapter 6's statistics or simple timing to confirm no constant surprises. Chapter 11's reproducible randomness (fixed-seed malformed input generation) hands pattern fuzzing a ready-made tool — these disciplines will be systematized again in Chapter 133's testing framework.

Common Mistakes

bool handle(const char* sFilter)
{
	xregex* pRegex = xrtRegexCompile((xstrview){ sFilter, strlen(sFilter) });
	/* ... match once ... */
	xrtRegexRelease(pRegex);   /* compile+release per request - the automaton was built for nothing */
}

/* compile once at startup, share globally */
static xregex* gFilter;
void init(void) { gFilter = xrtRegexCompile(XRT_STR_LITERAL("...")); }
bool handle(const char* sText)
{
	/* build only the matcher (light); the compiled object lends a reference */
	xregexmatcher* M = xrtRegexMatcherCreate(gFilter, Text);
	/* ... Find/Next ... */
	xrtRegexMatcherFree(M);
}

xstrview UserInput = ...;
xstrbuf Pat;
xrtStrBufInit(&Pat);
xrtStrBufAppend(&Pat, XRT_STR_LITERAL("^"));
xrtStrBufAppend(&Pat, UserInput);          /* "(admin)" enters the pattern - syntax characters! */
xrtStrBufAppend(&Pat, XRT_STR_LITERAL("$"));
str sPat = xrtStrBufTake(&Pat);
xregex* R = xrtRegexCompile((xstrview){ sPat, strlen(sPat) });   /* compile fails or injection */

xstrbuf Pat;
xrtStrBufInit(&Pat);
xrtStrBufAppend(&Pat, XRT_STR_LITERAL("^"));
str sEscaped = xrtRegexEscape(UserInput, NULL);
xrtStrBufAppend(&Pat, (xstrview){ sEscaped, strlen(sEscaped) });  /* escaped, it is a pure literal */
xrtFree(sEscaped);
xrtStrBufAppend(&Pat, XRT_STR_LITERAL("$"));

Programming Exercises

Summary