Something went wrong. Try again.
A regular expression library for Zig with PCRE semantics, four engines behind one API, and a JIT for x86-64 and aarch64.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Differential fuzzing across every engine.//!//! The engines are independent implementations of one specification, which//! makes them checkable against each other: for any pattern and any input//! they must report the same matches and the same captures. This generates//! both, runs each engine that can handle the pattern, and compares.//!//! Patterns are built from a grammar rather than from raw bytes, so the//! fuzzer spends its time on the engines instead of on the parser rejecting//! noise, and both are drawn from deliberately tiny, overlapping alphabets//! so that matches, backtracking, and ambiguity actually happen. Those//! alphabets include multi-byte codepoints and bytes that are not valid//! UTF-8, which is what reaches the decoder's fallback, the helper paths the//! JIT takes for non-ASCII, and the lead-byte handling in the prefilter.//!//! The generator is driven through `Source`, which reads its decisions either//! from the fuzzer's `Smith` or from a seeded PRNG. Both are wired up: `zig//! build test` runs thousands of seeded cases every time, and `zig build test//! --fuzz` hands the same generator to the coverage-guided fuzzer.//!//! The coverage-guided fuzzer needs the test binary compiled by LLVM, which//! is why `build.zig` sets `use_llvm` on it: the self-hosted backend Debug//! otherwise uses emits no coverage instrumentation, and `--fuzz` then ends//! with "pcs_len was zero" rather than a report. That message, or a panic in//! the build runner, is the tooling; a finding says "input saved to" above//! the report.const std = @import("std");const zregex = @import("root.zig");const Regex = zregex.Regex;const Span = zregex.Span;const gen = @import("pattern_gen");const fuzz_options = @import("fuzz_options");const Source = gen.Source;const Builder = gen.Builder;const chunks = gen.chunks;
/// One engine configuration to compare. Not every one applies to every/// pattern: the Pike VM and the lazy DFA cannot run backreferences or/// lookaround, and the JIT is only present where it could be generated.const Config = struct { name: []const u8, apply: *const fn (*Regex) void, /// Whether this configuration can run a pattern needing the backtracker. handles_backtrack_only: bool, /// Run against the copy compiled with AVX2 forced off. The x86-64 JIT has /// two vector code generators and picks between them at compile time, so /// the one the host CPU does not select is never reached otherwise -- /// on a machine with AVX2, that is the whole SSE2 path. sse2: bool = false,};
const configs = [_]Config{ .{ .name = "jit", .handles_backtrack_only = true, .apply = struct { fn f(re: *Regex) void { re.jit_mode = .on; } }.f, }, .{ .name = "jit-sse2", .handles_backtrack_only = true, .sse2 = true, .apply = struct { fn f(re: *Regex) void { re.jit_mode = .on; } }.f, }, .{ .name = "dfa", .handles_backtrack_only = false, .apply = struct { fn f(re: *Regex) void { re.jit_mode = .off; re.dfa_mode = .on; } }.f, }, .{ // The lazy DFA gives up when its state cache fills and hands the // subject to the Pike VM, which must reach the same answer. At the // real ceiling of 512 states almost no pattern gets there, // so this pins it low enough that most of them do. .name = "dfa-tiny-cache", .handles_backtrack_only = false, .apply = struct { fn f(re: *Regex) void { re.jit_mode = .off; re.dfa_mode = .on; re.dfa_max_states = 4; } }.f, }, .{ .name = "pike", .handles_backtrack_only = false, .apply = struct { fn f(re: *Regex) void { re.jit_mode = .off; re.dfa_mode = .off; } }.f, }, .{ .name = "backtrack", .handles_backtrack_only = true, .apply = struct { fn f(re: *Regex) void { re.jit_mode = .off; // Sound for any program: the backtracker implements every // instruction, including the ones the Pike VM cannot. re.fallback_engine = .backtrack; re.memo = true; } }.f, }, .{ .name = "backtrack-nomemo", .handles_backtrack_only = true, .apply = struct { fn f(re: *Regex) void { re.jit_mode = .off; re.fallback_engine = .backtrack; re.memo = false; } }.f, },};
/// Whether a second compilation with AVX2 forced off would exercise anything/// the first does not. Only the x86-64 backend has two vector widths, and a/// host without AVX2 already emits the SSE2 one.const sse2_worth_testing = zregex.jit_available and @import("builtin").cpu.arch == .x86_64;
/// Properties that must hold of any result, whatever engine produced it and/// whether or not the engines agree with each other. Cross-checking finds/// disagreements; this finds the things they could get wrong together.fn checkInvariants( re: *const Regex, haystack: []const u8, m: zregex.Match, prev_end: ?usize,) !void { const span = m.span(); try std.testing.expect(span.start <= span.end); try std.testing.expect(span.end <= haystack.len); // Group 0 is the match and always participates. try std.testing.expect(m.groups[0] != null); try std.testing.expectEqual(re.group_count, m.groups.len); for (m.groups) |g| { // A capture may sit outside the match — a lookahead can record one // past the end — but never outside the haystack. if (g) |sp| { try std.testing.expect(sp.start <= sp.end); try std.testing.expect(sp.end <= haystack.len); } } // Iteration moves forward and never returns overlapping matches. if (prev_end) |pe| try std.testing.expect(span.start >= pe);}
/// Every match in `haystack`, flattened to spans so the results of two/// configurations can be compared directly.///fn collect( gpa: std.mem.Allocator, re: *const Regex, haystack: []const u8, out: *std.ArrayList(?Span),) !void { var it = re.iterator(gpa, haystack); defer it.deinit(); var count: usize = 0; var prev: ?Span = null; while (try it.next()) |m| { var mm = m; defer mm.deinit(gpa); try checkInvariants(re, haystack, mm, if (prev) |p| p.end else null);
// Every reported match must be refindable: searching from exactly // its start has to reproduce it, span and captures alike. Scanning // into a position and starting at it are different paths -- the // prefilter skips, the JIT seeds, lookbehind reads context -- and a // match only one of them can see would otherwise pass every // cross-engine comparison, since the engines would agree with each // other both times. The exception is a match the iterator produced // by retrying after an empty one at the same position: a fresh // search there finds the empty match first, by design. const sp = mm.span(); const retry_product = if (prev) |p| p.start == p.end and p.start == sp.start else false; if (!retry_product) refind: { // Running out of budget says nothing about refindability. const again = re.findAt(gpa, haystack, sp.start) catch |err| switch (err) { error.StepLimitExceeded => break :refind, else => return err, }; if (again) |a| { var aa = a; defer aa.deinit(gpa); std.testing.expectEqualSlices(?Span, mm.groups, aa.groups) catch |err| { std.debug.print( "refind at {d} changed the match\nhaystack={f}\n", .{ sp.start, std.zig.fmtString(haystack) }, ); return err; }; } else { std.debug.print( "match at {d}..{d} not refindable\nhaystack={f}\n", .{ sp.start, sp.end, std.zig.fmtString(haystack) }, ); return error.TestUnexpectedResult; } }
prev = sp; try out.appendSlice(gpa, mm.groups); count += 1; // A pathological pattern should not turn one fuzz case into a hang; // agreement over the first matches is just as strong a signal. if (count >= 64) break; }}
/// Generate one pattern and one haystack, run every applicable engine, and/// require them to report the same matches and captures.fn oneCase(src: Source) anyerror!void { const gpa = std.testing.allocator;
var b = Builder{ .src = src, .gpa = gpa }; // Every so often, build something far bigger than the default: deep // nesting, a long program, and enough capture groups to run past what a // small pattern ever allocates. if (src.index(8) == 0) { b.depth_limit = 7; b.length_limit = 400; b.group_limit = 40; } defer b.buf.deinit(gpa); try b.sequence(0); if (b.buf.items.len == 0) return; const pattern = b.buf.items;
// Usually the defaults, but now and then a flag is set for the whole // pattern rather than written into it. `compileWithFlags` starts the // parser from a different state than `(?i:...)` mutating it partway, and // a top-level flag reaches constructs an inline group never wraps -- the // `^` and `$` of an unparenthesised alternation, for one. const flags: zregex.Flags = if (src.index(4) == 0) .{ .case_insensitive = src.boolean(), .multiline = src.boolean(), .dot_all = src.boolean(), } else .{};
var re = Regex.compileWithFlags(gpa, pattern, flags) catch return; // invalid is fine defer re.deinit(); // Keep a runaway pattern from stalling the fuzzer; a configuration that // gives up is skipped rather than compared. re.max_steps = 100_000;
// The same pattern again with AVX2 forced off. Which vector code the // x86-64 JIT emits is decided while compiling, so the generator the host // CPU does not select cannot be reached by flipping a field afterwards -- // it needs its own `Regex`. Everything else about the two is identical, // which is exactly what makes them comparable. var re_sse2: ?Regex = null; defer if (re_sse2) |*r| r.deinit(); if (sse2_worth_testing) { zregex.overrideAvx2(false); defer zregex.overrideAvx2(null); if (Regex.compileWithFlags(gpa, pattern, flags)) |alt| { re_sse2 = alt; re_sse2.?.max_steps = re.max_steps; } else |_| {} }
var hay: std.ArrayList(u8) = .empty; defer hay.deinit(gpa); // Most haystacks stay short, where a bug is easiest to read back. Some // are long, with long runs of one character: nothing shorter than a // vector block ever reaches the SIMD scanners, the lead-run skip, or a // prefilter search that has to cross real distance. if (src.intRange(u8, 0, 3) == 0) { const runs = src.intRange(u8, 1, 8); for (0..runs) |_| { const piece = chunks[src.index(chunks.len)]; const n = src.intRange(u16, 1, 200); for (0..n) |_| try hay.appendSlice(gpa, piece); try hay.appendSlice(gpa, chunks[src.index(chunks.len)]); } } else { const hay_len = src.intRange(u8, 0, 24); for (0..hay_len) |_| try hay.appendSlice(gpa, chunks[src.index(chunks.len)]); }
const needs_backtrack = re.fallback_engine == .backtrack;
var reference: std.ArrayList(?Span) = .empty; defer reference.deinit(gpa); var reference_name: []const u8 = "";
var actual: std.ArrayList(?Span) = .empty; defer actual.deinit(gpa);
// A few offsets to search from, the same ones for every configuration. var starts: [4]usize = undefined; var start_count: usize = 0; if (hay.items.len != 0) { while (start_count < starts.len) : (start_count += 1) { starts[start_count] = src.index(hay.items.len + 1); } }
configs: for (configs) |cfg| { if (needs_backtrack and !cfg.handles_backtrack_only) continue; const base = if (cfg.sse2) (re_sse2 orelse continue) else re; if (std.mem.startsWith(u8, cfg.name, "jit") and base.jit_code == null) continue;
var probe = base; cfg.apply(&probe); actual.clearRetainingCapacity(); collect(gpa, &probe, hay.items, &actual) catch |err| switch (err) { error.StepLimitExceeded => continue :configs, else => return err, };
// Searching from an offset is its own path: assertions and lookbehind // have to see the text before the start, which `find` never exercises. for (starts[0..start_count]) |st| { if (st > hay.items.len) continue; // Giving up part way would leave this configuration with fewer // results than the reference and read as a disagreement, so a // configuration that runs out of budget is dropped whole. const m = probe.findAt(gpa, hay.items, st) catch |err| switch (err) { error.StepLimitExceeded => continue :configs, else => return err, }; if (m) |mm| { var owned = mm; defer owned.deinit(gpa); try actual.append(gpa, owned.span()); } else { try actual.append(gpa, null); } }
// `isMatch` is not `find` with the captures thrown away: the lazy DFA // answers it in a mode of its own that never materialises them, and // the JIT has a separate entry point too. Either could disagree with // `find` about whether there is a match at all. if (probe.isMatch(gpa, hay.items)) |yes| { if (probe.find(gpa, hay.items)) |found| { if (found) |m| { var mm = m; mm.deinit(gpa); } std.testing.expectEqual(found != null, yes) catch |err| { std.debug.print( "pattern={s}\nhaystack={f}\n{s}: isMatch={} but find={}\n", .{ pattern, std.zig.fmtString(hay.items), cfg.name, yes, found != null }, ); return err; }; } else |err| switch (err) { error.StepLimitExceeded => {}, else => return err, } } else |err| switch (err) { error.StepLimitExceeded => {}, else => return err, }
if (reference_name.len == 0) { reference_name = cfg.name; reference.clearRetainingCapacity(); try reference.appendSlice(gpa, actual.items); continue; } std.testing.expectEqualSlices(?Span, reference.items, actual.items) catch |err| { std.debug.print( "pattern={s}\nhaystack={f}\n{s} and {s} disagree\n", .{ pattern, std.zig.fmtString(hay.items), reference_name, cfg.name }, ); return err; }; }}
fn testOne(_: void, smith: *std.testing.Smith) anyerror!void { return oneCase(.{ .smith = smith });}
test "engines agree under fuzzing" { try std.testing.fuzz({}, testOne, .{});}
/// `isMatch` and `find` must never disagree about whether there is a match.fn checkIsMatch(gpa: std.mem.Allocator, re: *const Regex, haystack: []const u8) !void { const found = re.find(gpa, haystack) catch |err| switch (err) { error.StepLimitExceeded => return, else => return err, }; const yes = re.isMatch(gpa, haystack) catch |err| switch (err) { error.StepLimitExceeded => return, else => return err, }; if (found) |m| { var mm = m; mm.deinit(gpa); } try std.testing.expectEqual(found != null, yes);}
test "arbitrary bytes never crash the parser or the engines" { const gpa = std.testing.allocator; var prng = std.Random.DefaultPrng.init(0x50a7_7e12); const rand = prng.random(); var pattern: [24]u8 = undefined; var hay: [16]u8 = undefined; // Mostly syntax characters, so that random input has a real chance of // parsing and reaching the engines rather than being rejected at once. const soup = "ab01()[]{}|*+?.^$\\-,:<>=! \u{e9}"; for (0..20000) |_| { const plen = rand.uintLessThan(usize, pattern.len); for (pattern[0..plen]) |*c| c.* = soup[rand.uintLessThan(usize, soup.len)]; var re = Regex.compile(gpa, pattern[0..plen]) catch continue; defer re.deinit(); re.max_steps = 10_000; const hlen = rand.uintLessThan(usize, hay.len); for (hay[0..hlen]) |*c| c.* = soup[rand.uintLessThan(usize, soup.len)]; try checkIsMatch(gpa, &re, hay[0..hlen]); }}
/// Passes everything through to `child` except growing in place, which it/// always refuses. `checkAllAllocationFailures` needs every run of a case to/// make the same allocations, and whether the testing allocator can grow a/// block in place depends on what earlier runs left beside it: a container/// whose `remap` succeeds once and fails the next time allocates once more,/// and the check reports it as nondeterministic. A refused resize is always/// allowed by the `Allocator` contract, so this only takes away a choice.const NoGrowAllocator = struct { child: std.mem.Allocator,
fn allocator(self: *NoGrowAllocator) std.mem.Allocator { return .{ .ptr = self, .vtable = &.{ .alloc = alloc, .resize = resize, .remap = remap, .free = free, } }; }
fn alloc(ctx: *anyopaque, len: usize, alignment: std.mem.Alignment, ret_addr: usize) ?[*]u8 { const self: *NoGrowAllocator = @ptrCast(@alignCast(ctx)); return self.child.rawAlloc(len, alignment, ret_addr); }
fn resize(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) bool { const self: *NoGrowAllocator = @ptrCast(@alignCast(ctx)); if (new_len > memory.len) return false; return self.child.rawResize(memory, alignment, new_len, ret_addr); }
fn remap(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) ?[*]u8 { const self: *NoGrowAllocator = @ptrCast(@alignCast(ctx)); if (new_len > memory.len) return null; return self.child.rawRemap(memory, alignment, new_len, ret_addr); }
fn free(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, ret_addr: usize) void { const self: *NoGrowAllocator = @ptrCast(@alignCast(ctx)); self.child.rawFree(memory, alignment, ret_addr); }};
/// Compile `pattern` and run the whole public surface over `hay`, letting/// every allocation error out. Written for `checkAllAllocationFailures`, which/// calls it once per allocation the successful run makes, failing that one.fn allocFailureCase( gpa: std.mem.Allocator, pattern: []const u8, hay: []const u8, engine: zregex.Engine, memo: bool,) anyerror!void { var re = Regex.compile(gpa, pattern) catch |err| switch (err) { error.OutOfMemory => return err, // A pattern this generator will not compile is not what is being // tested, and the caller has already seen it compile once. else => return, }; defer re.deinit(); re.max_steps = 10_000; re.memo = memo; if (re.fallback_engine == .pike) re.fallback_engine = engine;
if (re.find(gpa, hay)) |m| { if (m) |found| { var mm = found; mm.deinit(gpa); } } else |err| switch (err) { error.OutOfMemory => return err, error.StepLimitExceeded => {}, }
_ = re.isMatch(gpa, hay) catch |err| switch (err) { error.OutOfMemory => return err, error.StepLimitExceeded => {}, };
var it = re.iterator(gpa, hay); defer it.deinit(); var seen: usize = 0; while (seen < 8) : (seen += 1) { const step = it.next() catch |err| switch (err) { error.OutOfMemory => return err, error.StepLimitExceeded => break, }; var mm = step orelse break; mm.deinit(gpa); }}
test "no allocation failure leaks or is swallowed" { // Every other test runs with memory always available, so the paths taken // when an allocation fails partway are otherwise never executed: what has // been allocated by then still has to be released, and the error still // has to reach the caller rather than being reported as a clean result. // // `checkAllAllocationFailures` reruns each case once per allocation, // failing a different one each time, so the case count here is small on // purpose -- the work is quadratic in what a single case allocates. var prng = std.Random.DefaultPrng.init(0x0a11_0c_fa11); const src = Source{ .random = prng.random() }; const gpa = std.testing.allocator; var no_grow: NoGrowAllocator = .{ .child = gpa }; const backing = no_grow.allocator();
for (0..fuzz_options.alloc_cases) |_| { var b = Builder{ .src = src, .gpa = gpa }; defer b.buf.deinit(gpa); try b.sequence(0); if (b.buf.items.len == 0) continue;
var hay: std.ArrayList(u8) = .empty; defer hay.deinit(gpa); const hay_len = src.intRange(u8, 0, 12); for (0..hay_len) |_| try hay.appendSlice(gpa, chunks[src.index(chunks.len)]);
// The two fallbacks allocate quite differently -- the backtracker has // an explicit stack and a memo table the Pike VM has no equivalent of. for ([_]zregex.Engine{ .pike, .backtrack }) |engine| { // Without the memo, every allocation failure must come back out // as one: a run that reports a clean result after an allocation // was refused has lost an error somewhere. try std.testing.checkAllAllocationFailures( backing, allocFailureCase, .{ b.buf.items, hay.items, engine, false }, );
// With it, that last part cannot be required. `std.HashMap` // answers a `getOrPut` whose growth failed by looking the key up // anyway and reporting it found when it is already there -- the // memo's question is answered, so nothing is wrong, but from the // outside it looks like a swallowed error. Leaks are still // faults, and this is the only run that reaches the memo at all. std.testing.checkAllAllocationFailures( backing, allocFailureCase, .{ b.buf.items, hay.items, engine, true }, ) catch |err| switch (err) { error.SwallowedOutOfMemoryError => {}, else => return err, }; } }}
test "engines agree on randomized patterns" { // Fixed seed so a failure is reproducible and CI is deterministic; this // is the cheap standing check that every build pays for. A longer run is // `zig build test -Dfuzz-cases=200000 -Dfuzz-seed=<n>`, walking the seed // to reach the patterns one stream never produces. var prng = std.Random.DefaultPrng.init(fuzz_options.seed); for (0..fuzz_options.cases) |_| try oneCase(.{ .random = prng.random() });}