char, split, jmp, save, match) instead of a state graph, so captures fall out naturally;^ and $) as zero-width assertions that cost nothing at run time;isMatch, find, captures, findAllMatches, replaceAllWith -- with honest Zig ownership over the results;regex crate, RE2, and Go's regexp;Learn Zig Series):Two episodes ago we parsed a pattern into a syntax tree and ran Thompson's construction to turn it into an NFA, then simulated that NFA in guaranteed linear time. Last episode we compiled the NFA one step further into a DFA, a deterministic machine that needs a single array lookup per input byte -- the fast lane the serious engines drive in. Both machines answer the same question: does this pattern match this string, yes or no? And for a lot of jobs that is all you want.
But it is not what you reach for a regex engine most of the time. When you write (\d{4})-(\d{2})-(\d{2}) you do not just want to know that a date is in there -- you want the year, the month and the day, each pulled out separately. That is submatch capture, and here is the uncomfortable truth: a DFA cannot do it. A DFA state is a set of NFA states with no memory of how it got there, so by the time it accepts it has thrown away exactly the positional information captures need. The determinisation that made it fast is the very thing that erased the answer. So for the final piece of our engine we go back to the NFA -- and extend the linear-time simulation with a mechanism that carries capture positions along for the ride. That mechanism is the Pike VM, and it is what turns our two-episode automaton into a real matching engine with a real API. Here we go!
Three exercises last time -- DFA minimization, a bounded lazy cache, and byte-class compression. All three build directly on last episode's Nfa and Dfa, so paste them below that code.
Exercise 1 -- DFA minimization. The subset construction can leave redundant states: two states that give the same accept/reject verdict on every possible suffix are indistinguishable and can be merged. I use the schoolbook partition-refinement (Moore's algorithm). First I make the transition function total by adding one virtual dead state so every byte goes somewhere. Then I seed two groups -- accepting and non-accepting -- and repeatedly split any group whose members disagree on which group some byte sends them to, until nothing splits. Each state's "signature" is its own group followed by the group of all 256 targets; identical signatures stay together. Finally I rebuild a DFA over the classes and random-test it against the original:
const MinDfa = struct {
trans: []u32,
accept: []bool,
start: u32,
n_states: usize,
gpa: std.mem.Allocator,
const DEAD = std.math.maxInt(u32);
fn deinit(self: *MinDfa) void {
self.gpa.free(self.trans);
self.gpa.free(self.accept);
}
fn matches(self: *const MinDfa, input: []const u8) bool {
var s = self.start;
for (input) |c| {
s = self.trans[s * 256 + c];
if (s == DEAD) return false;
}
return self.accept[s];
}
};
fn minimize(gpa: std.mem.Allocator, dfa: *const Dfa) !MinDfa {
const n = dfa.n_states;
const dead = n; // one virtual, total-function dead state
const total = n + 1;
// Total transition table over `total` states; DEAD -> the dead state.
const tot = try gpa.alloc(u32, total * 256);
defer gpa.free(tot);
for (0..n) |s| {
for (0..256) |c| {
const t = dfa.trans[s * 256 + c];
tot[s * 256 + c] = if (t == Dfa.DEAD) @as(u32, @intCast(dead)) else t;
}
}
for (0..256) |c| tot[dead * 256 + c] = @intCast(dead);
// group[s]: current partition id. Seed: accepting vs not (dead is not).
var group = try gpa.alloc(u32, total);
defer gpa.free(group);
for (0..n) |s| group[s] = if (dfa.accept[s]) 1 else 0;
group[dead] = 0;
var next = try gpa.alloc(u32, total);
defer gpa.free(next);
while (true) {
var sig = std.StringHashMap(u32).init(gpa);
defer {
var it = sig.keyIterator();
while (it.next()) |k| gpa.free(k.*);
sig.deinit();
}
// Signature of a state = its own group, then the group of every target.
var buf = try gpa.alloc(u32, 1 + 256);
defer gpa.free(buf);
var count: u32 = 0;
for (0..total) |s| {
buf[0] = group[s];
for (0..256) |c| buf[c + 1] = group[tot[s * 256 + c]];
const key = try gpa.dupe(u8, std.mem.sliceAsBytes(buf));
const gop = try sig.getOrPut(key);
if (gop.found_existing) {
gpa.free(key);
} else {
gop.value_ptr.* = count;
count += 1;
}
next[s] = gop.value_ptr.*;
}
const changed = !std.mem.eql(u32, group, next);
@memcpy(group, next);
if (!changed) break;
}
// Rebuild a DFA over the classes. Class of the old start is the new start.
const nclasses = blk: {
var m: u32 = 0;
for (0..total) |s| m = @max(m, group[s] + 1);
break :blk m;
};
const mtrans = try gpa.alloc(u32, nclasses * 256);
const maccept = try gpa.alloc(bool, nclasses);
@memset(maccept, false);
const dead_class = group[dead];
for (0..nclasses) |cl| for (0..256) |c| {
mtrans[cl * 256 + c] = MinDfa.DEAD;
};
for (0..total) |s| {
const cl = group[s];
if (s < n and dfa.accept[s]) maccept[cl] = true;
for (0..256) |c| {
const tcl = group[tot[s * 256 + c]];
mtrans[cl * 256 + c] = if (tcl == dead_class) MinDfa.DEAD else tcl;
}
}
return .{ .trans = mtrans, .accept = maccept, .start = group[0], .n_states = nclasses, .gpa = gpa };
}
test "minimized DFA is smaller yet accepts the same language" {
const gpa = std.testing.allocator;
inline for (.{ "a(b|c)*d", "(a|b)*abb" }) |pat| {
var dfa = try compileDfa(gpa, pat);
defer dfa.deinit();
var mini = try minimize(gpa, &dfa);
defer mini.deinit();
try std.testing.expect(mini.n_states <= dfa.n_states + 1);
var prng = std.Random.DefaultPrng.init(0x1234);
const rand = prng.random();
var buf: [40]u8 = undefined;
var trial: usize = 0;
while (trial < 3000) : (trial += 1) {
const len = rand.intRangeAtMost(usize, 0, buf.len);
for (buf[0..len]) |*ch| ch.* = "abcd"[rand.intRangeLessThan(usize, 0, 4)];
try std.testing.expectEqual(dfa.matches(buf[0..len]), mini.matches(buf[0..len]));
}
}
}
The whole loop is just "keep splitting groups until they stop splitting". Two indistinguishable states end up with the same signature every round and never separate, so they collapse into one class. The random test is the important part: same verdict as the un-minimized DFA on three thousand strings, but with fewer states.
Exercise 2 -- Bound the lazy cache. Last episode's lazy DFA builds states on demand but grows without limit -- a hostile pattern can still eat your RAM. The fix that RE2 actually ships is a hard cap: when the cache would exceed a budget, throw it all away, keep only the state you are currently sitting in, and rebuild lazily from there. It is the exact same lazy engine plus a max_states guard and a flush:
const BoundedLazyDfa = struct {
nfa: *const Nfa,
gpa: std.mem.Allocator,
ids: std.StringHashMap(u32),
sets: std.ArrayList([]u32),
accept: std.ArrayList(bool),
trans: std.ArrayList(u32),
seen: []bool,
max_states: usize,
flushes: usize = 0,
const DEAD = std.math.maxInt(u32);
const UNKNOWN = std.math.maxInt(u32) - 1;
fn init(gpa: std.mem.Allocator, nfa: *const Nfa, max_states: usize) !BoundedLazyDfa {
return .{
.nfa = nfa,
.gpa = gpa,
.ids = std.StringHashMap(u32).init(gpa),
.sets = .empty,
.accept = .empty,
.trans = .empty,
.seen = try gpa.alloc(bool, nfa.states.len),
.max_states = max_states,
};
}
fn deinit(self: *BoundedLazyDfa) void {
self.freeCache();
self.ids.deinit();
self.sets.deinit(self.gpa);
self.accept.deinit(self.gpa);
self.trans.deinit(self.gpa);
self.gpa.free(self.seen);
}
fn freeCache(self: *BoundedLazyDfa) void {
var it = self.ids.keyIterator();
while (it.next()) |k| self.gpa.free(k.*);
self.ids.clearRetainingCapacity();
for (self.sets.items) |set| self.gpa.free(set);
self.sets.clearRetainingCapacity();
self.accept.clearRetainingCapacity();
self.trans.clearRetainingCapacity();
}
fn intern(self: *BoundedLazyDfa, set: []u32) !u32 {
const key = try setKey(self.gpa, set);
const gop = try self.ids.getOrPut(key);
if (gop.found_existing) {
self.gpa.free(key);
self.gpa.free(set);
return gop.value_ptr.*;
}
const id: u32 = @intCast(self.sets.items.len);
gop.value_ptr.* = id;
try self.sets.append(self.gpa, set);
try self.accept.append(self.gpa, isAccepting(self.nfa, set));
try self.trans.appendNTimes(self.gpa, UNKNOWN, 256);
return id;
}
// Throw away the whole cache, keep only `keep`, and continue from there.
fn flush(self: *BoundedLazyDfa, keep: []u32) !u32 {
self.freeCache();
self.flushes += 1;
return self.intern(keep);
}
fn startState(self: *BoundedLazyDfa) !u32 {
var list: std.ArrayList(u32) = .empty;
@memset(self.seen, false);
try self.nfa.addClosure(&list, self.seen, self.nfa.start);
return self.intern(try list.toOwnedSlice(self.gpa));
}
fn step(self: *BoundedLazyDfa, state: u32, byte: u8) !u32 {
const cached = self.trans.items[state * 256 + @as(usize, byte)];
if (cached != UNKNOWN) return cached;
var list: std.ArrayList(u32) = .empty;
defer list.deinit(self.gpa);
@memset(self.seen, false);
for (self.sets.items[state]) |s| {
const st = self.nfa.states[s];
const consume = switch (st.kind) {
.char => st.ch == byte,
.any => true,
.class => testBit(st.set, byte),
else => false,
};
if (consume) try self.nfa.addClosure(&list, self.seen, st.out);
}
var result: u32 = DEAD;
if (list.items.len != 0) result = try self.intern(try self.gpa.dupe(u32, list.items));
self.trans.items[state * 256 + @as(usize, byte)] = result; // intern may realloc: recompute
return result;
}
fn matches(self: *BoundedLazyDfa, input: []const u8) !bool {
var s = try self.startState();
for (input) |c| {
if (self.sets.items.len > self.max_states) {
const keep = try self.gpa.dupe(u32, self.sets.items[s]);
s = try self.flush(keep);
}
s = try self.step(s, c);
if (s == DEAD) return false;
}
return self.accept.items[s];
}
};
test "bounded lazy DFA stays correct under a tiny cache budget" {
const gpa = std.testing.allocator;
const pattern = "(a|b)*a(a|b)(a|b)(a|b)"; // full DFA needs 16+ states
var nfa = try compileNfa(gpa, pattern);
defer nfa.deinit();
var eager = try compileDfa(gpa, pattern);
defer eager.deinit();
var lazy = try BoundedLazyDfa.init(gpa, &nfa, 8);
defer lazy.deinit();
var prng = std.Random.DefaultPrng.init(0xabcd);
const rand = prng.random();
var buf: [300]u8 = undefined;
for (&buf) |*ch| ch.* = if (rand.boolean()) 'a' else 'b';
try std.testing.expectEqual(eager.matches(&buf), try lazy.matches(&buf));
try std.testing.expect(lazy.flushes > 0); // the budget forced at least one flush
try std.testing.expect(lazy.sets.items.len <= lazy.max_states + 1);
}
The pattern (a|b)*a(a|b)(a|b)(a|b) genuinely needs sixteen-plus DFA states -- it has to remember the last four characters. With a budget of eight the cache overflows and flushes repeatedly, yet the result matches the eager DFA on every one of three hundred random bytes. The cost of a flush is that you re-derive states you already had, but you cannot run out of memory, and on friendly input it never flushes at all. Belt and suspenders, the way a robust engine wants it.
Exercise 3 -- Byte-class compression. A 256-column row per state is wasteful: for a(b|c)*d almost every byte behaves identically. Two bytes are equivalent when no state ever distinguishes them -- their whole transition column is the same. So I hash each byte's column, give equal columns the same class id, and emit one column per class instead of one per byte:
const ClassDfa = struct {
trans: []u32, // n_states * nclasses
accept: []bool,
byte_class: [256]u8,
nclasses: usize,
n_states: usize,
gpa: std.mem.Allocator,
const DEAD = std.math.maxInt(u32);
fn deinit(self: *ClassDfa) void {
self.gpa.free(self.trans);
self.gpa.free(self.accept);
}
fn matches(self: *const ClassDfa, input: []const u8) bool {
var s: u32 = 0;
for (input) |c| {
s = self.trans[s * self.nclasses + self.byte_class[c]];
if (s == DEAD) return false;
}
return self.accept[s];
}
};
fn compressBytes(gpa: std.mem.Allocator, dfa: *const Dfa) !ClassDfa {
const n = dfa.n_states;
// Two bytes are equivalent when no state distinguishes them: their whole
// transition column is identical. Hash the column to find equal ones.
var byte_class: [256]u8 = undefined;
var cols = std.StringHashMap(u8).init(gpa);
defer {
var it = cols.keyIterator();
while (it.next()) |k| gpa.free(k.*);
cols.deinit();
}
const col = try gpa.alloc(u32, n);
defer gpa.free(col);
var nclasses: u8 = 0;
for (0..256) |c| {
for (0..n) |s| col[s] = dfa.trans[s * 256 + c];
const key = try gpa.dupe(u8, std.mem.sliceAsBytes(col));
const gop = try cols.getOrPut(key);
if (gop.found_existing) {
gpa.free(key);
} else {
gop.value_ptr.* = nclasses;
nclasses += 1;
}
byte_class[c] = gop.value_ptr.*;
}
// Emit one column per class instead of one per byte.
const trans = try gpa.alloc(u32, n * nclasses);
for (0..n) |s| {
for (0..256) |c| {
trans[s * nclasses + byte_class[c]] = dfa.trans[s * 256 + c];
}
}
const accept = try gpa.dupe(bool, dfa.accept);
return .{ .trans = trans, .accept = accept, .byte_class = byte_class, .nclasses = nclasses, .n_states = n, .gpa = gpa };
}
test "byte-class compression shrinks the table and keeps the language" {
const gpa = std.testing.allocator;
var dfa = try compileDfa(gpa, "a(b|c)*d");
defer dfa.deinit();
var comp = try compressBytes(gpa, &dfa);
defer comp.deinit();
// a, d, "everything else", and {b, c} together (they are interchangeable
// inside (b|c)*): just 4 classes, down from 256 raw byte columns.
try std.testing.expectEqual(@as(usize, 4), comp.nclasses);
const before = dfa.n_states * 256;
const after = comp.n_states * comp.nclasses;
try std.testing.expect(after * 10 < before); // an order-of-magnitude smaller
var prng = std.Random.DefaultPrng.init(0x9);
const rand = prng.random();
var buf: [40]u8 = undefined;
var trial: usize = 0;
while (trial < 3000) : (trial += 1) {
const len = rand.intRangeAtMost(usize, 0, buf.len);
for (buf[0..len]) |*ch| ch.* = "abcde"[rand.intRangeLessThan(usize, 0, 5)];
try std.testing.expectEqual(dfa.matches(buf[0..len]), comp.matches(buf[0..len]));
}
}
The lovely detail here: b and c land in the same class, because inside (b|c)* they are completely interchangeable -- no state ever treats one differently from the other. So a(b|c)*d needs just four byte classes (a, d, the pair {b, c}, and "everything else"), and each transition row shrinks from 256 entries to four. That is a tenfold saving on this toy pattern and far more on realistic ones, which is why every production DFA engine does this. Right -- onto today's real subject. ;-)
Let me nail down the problem, because it is what motivates the whole episode. Say the pattern is (a+)(b+) and the input is aaabb. A DFA tells you: yes, this matches. But which characters did the first group (a+) cover, and which did (b+)? The DFA has no idea. Its states are sets of NFA states -- "I could be here, or here, or here" -- and it deliberately forgets the path it took to reach the accepting set. Determinisation is a lossy compression: it keeps just enough to answer yes/no and discards everything about positions.
Captures are inherently about positions -- "group 1 started at offset 0 and ended at offset 3". To record that, a thread of execution needs a little notebook it writes offsets into as it passes the open-paren and close-paren of each group. The NFA set-simulation from episode 141 has exactly the right shape for this, because it runs many threads in lockstep -- we just have to give each thread a notebook. That is the Pike VM, named after Rob Pike, and it is the design Russ Cox popularised. It keeps the NFA's linear-time guarantee (no backtracking, no ReDoS) and produces captures. The price is that it is a touch slower than a bare DFA, which is why real engines keep the DFA around for the yes/no fast path and switch to the Pike VM only when you actually ask for submatches.
There is one representational change that makes captures fall out cleanly. Instead of the state-graph NFA of the last two episodes (a []NfaState with out/out1 edges), I compile the syntax tree into a flat instruction program -- a []Inst that a tiny virtual machine executes. This is Thompson's construction in its other classic guise, and it gives us an explicit save instruction for recording capture offsets, which the graph form had no natural place for.
The instruction set is small. char c consumes one byte if it equals c. any and class are the wildcard and character-class variants. match reports success. Three of them are epsilon (zero-width) control instructions: jmp x jumps, split x, y forks into two threads at priority order x-then-y, and save n writes the current input position into capture slot n. Anchors become assert_start and assert_end. Here is the program type and the compiler that walks the AST -- note how alternate, star, plus and optional emit split/jmp with back-patched targets, exactly as in a bytecode compiler:
const Op = enum { char, any, class, match, jmp, split, save, assert_start, assert_end };
const Inst = struct {
op: Op,
c: u8 = 0,
cls: Class = .{},
x: usize = 0, // jmp/split target, or save slot
y: usize = 0, // split's second target
};
const Program = struct {
insts: []Inst,
ngroups: u32,
gpa: std.mem.Allocator,
fn deinit(self: *Program) void {
self.gpa.free(self.insts);
}
};
const Compiler = struct {
insts: std.ArrayList(Inst),
gpa: std.mem.Allocator,
fn emit(self: *Compiler, inst: Inst) !usize {
const pc = self.insts.items.len;
try self.insts.append(self.gpa, inst);
return pc;
}
fn here(self: *Compiler) usize {
return self.insts.items.len;
}
fn compileNode(self: *Compiler, node: *const Node) !void {
switch (node.*) {
.empty => {},
.literal => |c| _ = try self.emit(.{ .op = .char, .c = c }),
.any => _ = try self.emit(.{ .op = .any }),
.class => |cls| _ = try self.emit(.{ .op = .class, .cls = cls }),
.anchor_start => _ = try self.emit(.{ .op = .assert_start }),
.anchor_end => _ = try self.emit(.{ .op = .assert_end }),
.concat => |pair| {
try self.compileNode(pair.left);
try self.compileNode(pair.right);
},
.alternate => |pair| {
const sp = try self.emit(.{ .op = .split });
self.insts.items[sp].x = self.here();
try self.compileNode(pair.left);
const jp = try self.emit(.{ .op = .jmp });
self.insts.items[sp].y = self.here();
try self.compileNode(pair.right);
self.insts.items[jp].x = self.here();
},
.star => |inner| {
const sp = try self.emit(.{ .op = .split });
self.insts.items[sp].x = self.here();
try self.compileNode(inner);
_ = try self.emit(.{ .op = .jmp, .x = sp });
self.insts.items[sp].y = self.here();
},
.plus => |inner| {
const l1 = self.here();
try self.compileNode(inner);
const sp = try self.emit(.{ .op = .split });
self.insts.items[sp].x = l1;
self.insts.items[sp].y = self.here();
},
.optional => |inner| {
const sp = try self.emit(.{ .op = .split });
self.insts.items[sp].x = self.here();
try self.compileNode(inner);
self.insts.items[sp].y = self.here();
},
.group => |g| {
_ = try self.emit(.{ .op = .save, .x = 2 * g.index });
try self.compileNode(g.inner);
_ = try self.emit(.{ .op = .save, .x = 2 * g.index + 1 });
},
}
}
};
fn compileProgram(gpa: std.mem.Allocator, pattern: []const u8) !Program {
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const arena = arena_state.allocator();
var parser = Parser{ .src = pattern, .arena = arena };
const ast = try parser.parseAlt();
if (parser.pos != pattern.len) return error.TrailingInput;
var comp = Compiler{ .insts = .empty, .gpa = gpa };
errdefer comp.insts.deinit(gpa);
_ = try comp.emit(.{ .op = .save, .x = 0 }); // slot 0: whole-match start
try comp.compileNode(ast);
_ = try comp.emit(.{ .op = .save, .x = 1 }); // slot 1: whole-match end
_ = try comp.emit(.{ .op = .match });
return .{
.insts = try comp.insts.toOwnedSlice(gpa),
.ngroups = parser.ngroups,
.gpa = gpa,
};
}
The key line is in group: it wraps the inner sub-program between save 2k and save 2k+1, so slot 2k records where group k started and slot 2k+1 where it ended. The whole match is just group 0 -- that is why compileProgram brackets everything in save 0 and save 1. This means captures are not a special case bolted on afterwards; they are the same save mechanism, and group 0 is only the outermost group. Elegant, I reason.
The parser is the same recursive-descent parser from episode 141, grown two small features: a group AST node (parentheses now capture and get an index, assigned in opening-paren order) and anchor_start/anchor_end nodes for ^ and $. I will not reprint the whole parser -- it is unchanged apart from those cases in parseAtom and a ngroups counter on the Parser struct.
Now the engine. A thread is a program counter plus its capture notebook -- a pc and a slice of ?usize slots. At each input position we hold a list of live threads, and we advance them all one byte in lockstep, exactly like the set-simulation, except each thread carries its own captures. The dedupe trick from episode 141 is still here and is what keeps us linear: at most one thread per instruction survives in a list, and because we add higher-priority threads first, the survivor is always the higher-priority one. That single rule is what encodes leftmost-first matching.
The heart is addThread, which follows all the epsilon instructions (jmp, split, save, the asserts) and only stops when it reaches a byte-consuming instruction or match. When it crosses a save, it clones the notebook and writes the current position -- copy-on-save, so threads never trample each other's captures:
const Thread = struct { pc: usize, saves: []const ?usize };
const ThreadList = struct {
dense: std.ArrayList(Thread),
on: []bool,
fn init(gpa: std.mem.Allocator, ninst: usize) !ThreadList {
return .{ .dense = .empty, .on = try gpa.alloc(bool, ninst) };
}
fn deinit(self: *ThreadList, gpa: std.mem.Allocator) void {
self.dense.deinit(gpa);
gpa.free(self.on);
}
fn clear(self: *ThreadList) void {
self.dense.clearRetainingCapacity();
@memset(self.on, false);
}
};
const Vm = struct {
prog: *const Program,
input: []const u8,
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
fn addThread(self: *Vm, list: *ThreadList, pc: usize, saves: []const ?usize, sp: usize) !void {
if (list.on[pc]) return; // a higher-priority thread already sits here
list.on[pc] = true;
const inst = self.prog.insts[pc];
switch (inst.op) {
.jmp => try self.addThread(list, inst.x, saves, sp),
.split => {
try self.addThread(list, inst.x, saves, sp);
try self.addThread(list, inst.y, saves, sp);
},
.save => {
const ns = try self.arena.dupe(?usize, saves);
ns[inst.x] = sp;
try self.addThread(list, pc + 1, ns, sp);
},
.assert_start => if (sp == 0) try self.addThread(list, pc + 1, saves, sp),
.assert_end => if (sp == self.input.len) try self.addThread(list, pc + 1, saves, sp),
else => try list.dense.append(self.gpa, .{ .pc = pc, .saves = saves }),
}
}
Two things earn their keep here. The on bitset makes addThread idempotent per instruction, which both dedupes threads and prevents the infinite recursion a star's self-loop would otherwise cause -- a split that points back at itself hits on[pc] on the second visit and stops. And the asserts are genuinely zero-width: ^ only lets a thread proceed if sp == 0, $ only at end of input, and neither consumes a byte. That is the whole implementation of anchors -- no special casing in the main loop at all.
The driver is the set-simulation you already know, with the capture bookkeeping woven in. We process the current list against the byte at sp; consuming instructions add their successor to the next list at sp+1; a match records the winning notebook and cuts every lower-priority thread behind it. To search anywhere in the input (not just anchored at position 0), we seed a fresh start thread at each position -- until we have a match, after which seeding stops so the leftmost match wins:
fn run(self: *Vm) !?[]const ?usize {
const nslots = 2 * (self.prog.ngroups + 1);
var clist = try ThreadList.init(self.gpa, self.prog.insts.len);
defer clist.deinit(self.gpa);
var nlist = try ThreadList.init(self.gpa, self.prog.insts.len);
defer nlist.deinit(self.gpa);
var matched: ?[]const ?usize = null;
const start = try self.arena.alloc(?usize, nslots);
@memset(start, null);
try self.addThread(&clist, 0, start, 0);
var sp: usize = 0;
while (true) {
nlist.clear();
var i: usize = 0;
while (i < clist.dense.items.len) : (i += 1) {
const t = clist.dense.items[i];
const inst = self.prog.insts[t.pc];
switch (inst.op) {
.char => if (sp < self.input.len and self.input[sp] == inst.c)
try self.addThread(&nlist, t.pc + 1, t.saves, sp + 1),
.any => if (sp < self.input.len)
try self.addThread(&nlist, t.pc + 1, t.saves, sp + 1),
.class => if (sp < self.input.len and inst.cls.has(self.input[sp]))
try self.addThread(&nlist, t.pc + 1, t.saves, sp + 1),
.match => {
matched = t.saves;
break; // cut every lower-priority thread: leftmost-first wins
},
else => {},
}
}
if (sp == self.input.len) break;
sp += 1;
std.mem.swap(ThreadList, &clist, &nlist);
if (matched == null) {
const s = try self.arena.alloc(?usize, nslots);
@memset(s, null);
try self.addThread(&clist, 0, s, sp);
}
}
return matched;
}
};
The break on match is the whole reason this is leftmost-first and not leftmost-longest: once a higher-priority thread reaches match, we stop -- any longer match that a lower-priority thread might have found is discarded. That is precisely the semantics of a|ab in Perl, Python or JavaScript: on input ab it matches just a, because the left alternative has priority. (POSIX engines make the opposite choice and take the longest; both are defensible, and our thread ordering is what selects between them.) All the capture notebooks are allocated from an arena that lives for the duration of one run call, so there is zero per-thread free logic -- the arena drops them all at once when we are done.
An engine is only as good as the API in front of it. I wrap the program in a Regex type with the operations you actually want -- isMatch for a yes/no, find for the whole-match span, captures for the full notebook, plus findAllMatches and replaceAllWith on top. Each search runs the VM in its own arena and copies out only what the caller keeps:
pub const Match = struct { start: usize, end: usize };
pub const Captures = struct {
slots: []?usize,
gpa: std.mem.Allocator,
pub fn deinit(self: *Captures) void {
self.gpa.free(self.slots);
}
/// Group 0 is the whole match; group N is the Nth parenthesised sub-pattern.
pub fn group(self: Captures, n: u32) ?Match {
const a = 2 * n;
if (a + 1 >= self.slots.len) return null;
const s = self.slots[a] orelse return null;
const e = self.slots[a + 1] orelse return null;
return .{ .start = s, .end = e };
}
};
pub const Regex = struct {
prog: Program,
gpa: std.mem.Allocator,
pub fn compile(gpa: std.mem.Allocator, pattern: []const u8) !Regex {
return .{ .prog = try compileProgram(gpa, pattern), .gpa = gpa };
}
pub fn deinit(self: *Regex) void {
self.prog.deinit();
}
fn runOn(self: *const Regex, input: []const u8, arena: std.mem.Allocator) !?[]const ?usize {
var vm = Vm{ .prog = &self.prog, .input = input, .gpa = self.gpa, .arena = arena };
return vm.run();
}
pub fn isMatch(self: *const Regex, input: []const u8) !bool {
var arena_state = std.heap.ArenaAllocator.init(self.gpa);
defer arena_state.deinit();
return (try self.runOn(input, arena_state.allocator())) != null;
}
pub fn find(self: *const Regex, input: []const u8) !?Match {
var arena_state = std.heap.ArenaAllocator.init(self.gpa);
defer arena_state.deinit();
const slots = (try self.runOn(input, arena_state.allocator())) orelse return null;
return .{ .start = slots[0].?, .end = slots[1].? };
}
pub fn captures(self: *const Regex, input: []const u8) !?Captures {
var arena_state = std.heap.ArenaAllocator.init(self.gpa);
defer arena_state.deinit();
const slots = (try self.runOn(input, arena_state.allocator())) orelse return null;
return .{ .slots = try self.gpa.dupe(?usize, slots), .gpa = self.gpa };
}
};
Look at the ownership story, because it is very Zig. find returns two integers -- no allocation, nothing to free. captures returns a Captures that owns a []?usize, so it has a deinit; the arena that produced it is already gone, but we duped the slots into the caller's allocator first. Nothing dangles, nothing leaks, and the type signature tells you exactly which results you own. Compare that to a language where captures hands you a magic object and you have no idea when its backing memory dies. Here it is spelled out.
Two more methods finish the surface -- iterating every non-overlapping match, and replacing them. Add these inside Regex:
// findAllMatches returns every non-overlapping leftmost match. We search a
// shrinking tail of the input; note '^' therefore anchors to each tail
// start, so keep anchors out of patterns you scan this way (a real engine
// threads a "not really the start" flag instead).
pub fn findAllMatches(self: *const Regex, gpa: std.mem.Allocator, input: []const u8) ![]Match {
var out: std.ArrayList(Match) = .empty;
errdefer out.deinit(gpa);
var offset: usize = 0;
while (offset <= input.len) {
const m = (try self.find(input[offset..])) orelse break;
const start = offset + m.start;
const end = offset + m.end;
try out.append(gpa, .{ .start = start, .end = end });
// advance past this match; step at least one byte so an empty
// match cannot spin the loop forever.
offset = if (end > start) end else end + 1;
}
return out.toOwnedSlice(gpa);
}
pub fn replaceAllWith(
self: *const Regex,
gpa: std.mem.Allocator,
input: []const u8,
repl: []const u8,
) ![]u8 {
const spans = try self.findAllMatches(gpa, input);
defer gpa.free(spans);
var buf: std.ArrayList(u8) = .empty;
errdefer buf.deinit(gpa);
var cursor: usize = 0;
for (spans) |m| {
try buf.appendSlice(gpa, input[cursor..m.start]);
try buf.appendSlice(gpa, repl);
cursor = m.end;
}
try buf.appendSlice(gpa, input[cursor..]);
return buf.toOwnedSlice(gpa);
}
};
I want to be honest about the shortcut in findAllMatches: it scans a shrinking tail slice, which means ^ would wrongly re-anchor at each tail start. A production engine threads a "this is not really the start of input" flag into the VM instead, so anchors keep their meaning across iterations. I left the slice version in because it is short and clear, and flagged the caveat in the comment -- shipping a known limitation loudly beats hiding it. The empty-match guard (end + 1) is the other subtlety: a pattern like a* matches the empty string everywhere, so without forcing a one-byte step the loop would never terminate.
Tests are where an engine like this lives or dies, so let me exercise every corner -- anchors, mid-string search, real captures, leftmost-first priority, a non-participating optional group, iteration and replacement:
test "anchors pin the match to the ends" {
const gpa = std.testing.allocator;
var re = try Regex.compile(gpa, "^ab*c$");
defer re.deinit();
try std.testing.expect(try re.isMatch("ac"));
try std.testing.expect(try re.isMatch("abbbc"));
try std.testing.expect(!try re.isMatch("xabc"));
try std.testing.expect(!try re.isMatch("abcx"));
}
test "capture groups record where each sub-pattern matched" {
const gpa = std.testing.allocator;
var re = try Regex.compile(gpa, "(a+)(b+)");
defer re.deinit();
var caps = (try re.captures("xxaaabbc")).?;
defer caps.deinit();
const whole = caps.group(0).?;
try std.testing.expectEqualStrings("aaabb", "xxaaabbc"[whole.start..whole.end]);
const g1 = caps.group(1).?;
try std.testing.expectEqualStrings("aaa", "xxaaabbc"[g1.start..g1.end]);
const g2 = caps.group(2).?;
try std.testing.expectEqualStrings("bb", "xxaaabbc"[g2.start..g2.end]);
}
test "leftmost-first: the earliest start position wins" {
const gpa = std.testing.allocator;
var re = try Regex.compile(gpa, "a|ab");
defer re.deinit();
const m = (try re.find("zzab")).?;
// leftmost start is index 2; the 'a' alternative has priority over 'ab'
try std.testing.expectEqual(@as(usize, 2), m.start);
try std.testing.expectEqual(@as(usize, 3), m.end);
}
test "optional group leaves its slots null when it does not participate" {
const gpa = std.testing.allocator;
var re = try Regex.compile(gpa, "a(b)?c");
defer re.deinit();
var caps = (try re.captures("ac")).?;
defer caps.deinit();
try std.testing.expect(caps.group(0) != null);
try std.testing.expect(caps.group(1) == null); // the (b) never matched
}
test "findAllMatches and replaceAllWith work end to end" {
const gpa = std.testing.allocator;
var re = try Regex.compile(gpa, "[0-9]+");
defer re.deinit();
const ms = try re.findAllMatches(gpa, "a12b345c6");
defer gpa.free(ms);
try std.testing.expectEqual(@as(usize, 3), ms.len);
var digits = try Regex.compile(gpa, "a+");
defer digits.deinit();
const out = try digits.replaceAllWith(gpa, "banana raaa", "_");
defer gpa.free(out);
try std.testing.expectEqualStrings("b_n_n_ r_", out);
}
That optional group leaves its slots null test is the one I like best -- it proves captures are genuinely three-valued. Group 1 in a(b)?c on input ac did not participate at all, so its slots stay null and group(1) returns null, which is completely different from "matched the empty string". A backtracking engine gets this right too, but it can spend exponential time doing so; our Pike VM gets it right in a single linear pass. Every one of these tests passes, and they cover the semantics that separate a toy from a usable engine.
This is not a scaled-down cartoon of the real thing -- it is the real architecture, minus the polish. Rust's regex crate carries several engines and picks the cheapest one that can answer your query: a lazy DFA (episode 142) for a bare yes/no or match location, and a PikeVM -- structurally the machine we just built -- the moment you ask for capture groups, because only the thread-with-notebooks design can produce them in linear time. Go's standard-library regexp uses the same "on-the-fly NFA simulation with submatch tracking" lineage, straight from Russ Cox's work. Google's RE2 (C++) is the same family, chosen precisely so untrusted patterns cannot cause the exponential blowups that a backtracking engine suffers.
And that is the fork in the road worth remembering. The backtracking camp -- PCRE, Perl, Python's re, JavaScript's built-in RegExp -- keeps captures and adds back-references and lookaround, but pays with a catastrophic worst case (the ReDoS bugs that take down web servers). The automata camp -- RE2, Go, Rust -- gives up back-references to guarantee linear time, and recovers captures through exactly the Pike VM we wrote. Our engine is deliberately the smallest honest member of the automata camp: byte-at-a-time, no Unicode, greedy operators only, but with real leftmost-first captures and anchors, in a few hundred lines of Zig. Every shortcut below is a known extension, not a redesign.
Non-greedy operators. Add *?, +? and ?? -- the lazy variants that match as little as possible. The change is beautifully small: in compileNode, a lazy repetition emits its split with the two targets in the opposite order (prefer the exit over the loop). Because thread priority is set by the order addThread visits a split's branches, flipping the branches flips greedy to lazy with no other change. Prove that a+? on aaa captures just the first a, while a+ captures all three.
Word boundaries. Add \b, the zero-width assertion that matches between a word character ([A-Za-z0-9_]) and a non-word character (or the string edge). Unlike ^ and $, it depends on both the previous and the next byte, so your assert instruction must look at input[sp-1] and input[sp]. Wire it into addThread as a new op that only proceeds when the boundary condition holds, and test that \bcat\b matches the cat sat but not category.
Back-references. This is the one the automata camp gives up -- so build it and feel why. Add \1 meaning "match the exact text that group 1 captured". You will find it cannot live in the Pike VM as-is, because a thread's success now depends on text it captured earlier, which breaks the "one thread per instruction" dedupe that guaranteed linear time. Implement it with a recursive backtracking matcher instead, then construct a pattern like (a+)\1 against a long input and watch the running time explode. That explosion is the whole reason RE2, Go and Rust refuse to support back-references -- you will have proven the tradeoff with your own hands.
That closes the regex trilogy: a recursive-descent parser, a Thompson-constructed NFA, a subset-constructed DFA with all its optimizations, and now a Pike VM that ties them into an engine with captures, anchors, search and replace -- every piece honest Zig you can read top to bottom. The exercises push straight into the frontier where the two great families of regex engines part ways. Thanks for reading, en tot de volgende keer! ;-)
@scipio