Learn Zig Series (#141) - Regex: Thompson NFA

avatar

Learn Zig Series (#141) - Regex: Thompson NFA

zig.png

What will I learn?

  • What a regular expression really is underneath the syntax -- a description of a tiny state machine, not a magic string;
  • Why the fast, industrial regex engines use an NFA and a set-of-states simulation in stead of the recursive backtracking most tutorials teach;
  • How to parse a pattern into an AST with the recursive-descent parser we built back in episodes 131 to 133;
  • How Thompson's construction turns that tree into an NFA by wiring together little fragments with dangling out-edges;
  • How to simulate the NFA over an input by tracking all the states it could be in at once, giving guaranteed linear-time matching;
  • Why this approach is immune to the catastrophic-backtracking blowups (ReDoS) that take down real web servers;
  • How Zig's tagged unions, explicit error sets and index-based graphs keep the whole thing honest;
  • Three exercises that push the engine toward character classes, substring search, and the door to the next stage.

Requirements

  • A working modern computer running macOS, Windows or Ubuntu;
  • An installed Zig 0.14+ distribution (download from ziglang.org);
  • The recursive-descent parser and AST from episodes 131 to 133 fresh in mind -- today we reuse that exact shape;
  • Tagged unions from episode 6 and allocators from episode 7 in your back pocket;
  • The ambition to learn Zig programming.

Difficulty

  • Advanced

Curriculum (of the Learn Zig Series):

Learn Zig Series (#141) - Regex: Thompson NFA

Last episode we made our little language runtime stop interpreting and start generating machine code. Today we build a different kind of small compiler, and one you almost certainly use ten times a day without thinking about it: a regular expression engine. A regex is not magic. When you write a(b|c)*d, you are describing a tiny machine -- a graph of states with labelled edges -- and matching a string is just walking that graph. We are going to build the whole pipeline from scratch: parse the pattern into a syntax tree (with the exact recursive-descent parser shape from episodes 131 to 133), turn that tree into a state machine with a beautiful 1968 trick called Thompson's construction, and then simulate that machine in guaranteed linear time. No backtracking, no exponential blowups, no ReDoS. Here we go!

Solutions to Episode 140 Exercises

Three exercises last time, all extending our template JIT. Full code for each.

Exercise 1 -- A division op, and a guard. Add .div to the template JIT. Signed 64-bit division on x86-64 is idiv, which divides the 128-bit value in rdx:rax by its operand, so rax must first be sign-extended into rdx with cqo. The template is pop rcx ; pop rax ; cqo ; idiv rcx ; push rax, and we prove it against an interpreter oracle extended with @divTrunc:

const std = @import("std");
const posix = std.posix;
const linux = std.os.linux;

const Op = union(enum) { push: i64, add, sub, mul, div };

const Jit = struct {
    code: std.ArrayList(u8),

    fn init() Jit {
        return .{ .code = .empty };
    }
    fn deinit(self: *Jit, a: std.mem.Allocator) void {
        self.code.deinit(a);
    }
    fn emit(self: *Jit, a: std.mem.Allocator, bs: []const u8) !void {
        try self.code.appendSlice(a, bs);
    }
    fn compile(self: *Jit, a: std.mem.Allocator, program: []const Op) !void {
        for (program) |op| switch (op) {
            .push => |v| {
                try self.emit(a, &[_]u8{ 0x48, 0xB8 }); // mov rax, imm64
                try self.emit(a, &std.mem.toBytes(v));
                try self.emit(a, &[_]u8{0x50}); // push rax
            },
            .add => try self.emit(a, &[_]u8{ 0x59, 0x58, 0x48, 0x01, 0xC8, 0x50 }),
            .sub => try self.emit(a, &[_]u8{ 0x59, 0x58, 0x48, 0x29, 0xC8, 0x50 }),
            .mul => try self.emit(a, &[_]u8{ 0x59, 0x58, 0x48, 0x0F, 0xAF, 0xC1, 0x50 }),
            // pop rcx ; pop rax ; cqo ; idiv rcx ; push rax
            .div => try self.emit(a, &[_]u8{ 0x59, 0x58, 0x48, 0x99, 0x48, 0xF7, 0xF9, 0x50 }),
        };
        try self.emit(a, &[_]u8{ 0x58, 0xC3 }); // pop rax ; ret
    }
    fn finalize(self: *Jit) !*const fn () callconv(.c) i64 {
        const mem = try posix.mmap(
            null,
            self.code.items.len,
            .{ .READ = true, .WRITE = true },
            .{ .TYPE = .PRIVATE, .ANONYMOUS = true },
            -1,
            0,
        );
        errdefer posix.munmap(mem);
        @memcpy(mem[0..self.code.items.len], self.code.items);
        const rc = linux.mprotect(mem.ptr, mem.len, .{ .READ = true, .EXEC = true });
        if (posix.errno(rc) != .SUCCESS) return error.ProtectFailed;
        return @ptrCast(mem.ptr);
    }
};

fn interpret(program: []const Op) i64 {
    var stack: [64]i64 = undefined;
    var sp: usize = 0;
    for (program) |op| switch (op) {
        .push => |v| {
            stack[sp] = v;
            sp += 1;
        },
        .add => {
            sp -= 1;
            stack[sp - 1] += stack[sp];
        },
        .sub => {
            sp -= 1;
            stack[sp - 1] -= stack[sp];
        },
        .mul => {
            sp -= 1;
            stack[sp - 1] *= stack[sp];
        },
        .div => {
            sp -= 1;
            stack[sp - 1] = @divTrunc(stack[sp - 1], stack[sp]);
        },
    };
    return stack[sp - 1];
}

test "jit division agrees with the interpreter oracle" {
    const a = std.testing.allocator;
    const programs = [_][]const Op{
        &[_]Op{ .{ .push = 20 }, .{ .push = 4 }, .div }, // 5
        &[_]Op{ .{ .push = 100 }, .{ .push = 3 }, .div }, // 33
        &[_]Op{ .{ .push = 84 }, .{ .push = 2 }, .div, .{ .push = 3 }, .div }, // 14
        &[_]Op{ .{ .push = -20 }, .{ .push = 3 }, .div }, // -6, truncates toward zero
    };
    for (programs) |program| {
        var j = Jit.init();
        defer j.deinit(a);
        try j.compile(a, program);
        const f = try j.finalize();
        defer {
            const base: [*]align(std.heap.page_size_min) u8 = @constCast(@ptrCast(@alignCast(f)));
            posix.munmap(base[0..j.code.items.len]);
        }
        try std.testing.expectEqual(interpret(program), f());
    }
}

As for the divisor-zero question: on x86-64, idiv by zero raises a hardware #DE fault, which the OS delivers as SIGFPE and your process dies. There is no soft error to catch -- the CPU traps before any Zig code runs again. The guard belongs in the generated code, right before the idiv: emit a test rcx, rcx ; jz <handler> so a zero divisor jumps to a snippet that returns a sentinel (or an out-of-band error flag) in stead of dividing. That means computing a relative jump offset, which is exactly the machinery the next kind of code generator needs -- so I left it as the thinking part of the exercise.

Exercise 2 -- A one-argument function. Add an .arg op that pushes the incoming argument. Per the System V calling convention the first integer argument arrives in rdi, so .arg is a single byte, push rdi (0x57). Compile arg arg mul to square the input, finalize to a *const fn (i64) callconv(.c) i64, and test:

const std = @import("std");
const posix = std.posix;
const linux = std.os.linux;

const Op = union(enum) { push: i64, arg, add, sub, mul };

const Jit = struct {
    code: std.ArrayList(u8),

    fn init() Jit {
        return .{ .code = .empty };
    }
    fn deinit(self: *Jit, a: std.mem.Allocator) void {
        self.code.deinit(a);
    }
    fn emit(self: *Jit, a: std.mem.Allocator, bs: []const u8) !void {
        try self.code.appendSlice(a, bs);
    }
    fn compile(self: *Jit, a: std.mem.Allocator, program: []const Op) !void {
        for (program) |op| switch (op) {
            .push => |v| {
                try self.emit(a, &[_]u8{ 0x48, 0xB8 });
                try self.emit(a, &std.mem.toBytes(v));
                try self.emit(a, &[_]u8{0x50});
            },
            .arg => try self.emit(a, &[_]u8{0x57}), // push rdi (arg0 in System V)
            .add => try self.emit(a, &[_]u8{ 0x59, 0x58, 0x48, 0x01, 0xC8, 0x50 }),
            .sub => try self.emit(a, &[_]u8{ 0x59, 0x58, 0x48, 0x29, 0xC8, 0x50 }),
            .mul => try self.emit(a, &[_]u8{ 0x59, 0x58, 0x48, 0x0F, 0xAF, 0xC1, 0x50 }),
        };
        try self.emit(a, &[_]u8{ 0x58, 0xC3 });
    }
    fn finalize(self: *Jit) !*const fn (i64) callconv(.c) i64 {
        const mem = try posix.mmap(
            null,
            self.code.items.len,
            .{ .READ = true, .WRITE = true },
            .{ .TYPE = .PRIVATE, .ANONYMOUS = true },
            -1,
            0,
        );
        errdefer posix.munmap(mem);
        @memcpy(mem[0..self.code.items.len], self.code.items);
        const rc = linux.mprotect(mem.ptr, mem.len, .{ .READ = true, .EXEC = true });
        if (posix.errno(rc) != .SUCCESS) return error.ProtectFailed;
        return @ptrCast(mem.ptr);
    }
};

test "a JIT-compiled function that squares its argument" {
    const a = std.testing.allocator;
    var j = Jit.init();
    defer j.deinit(a);

    const program = [_]Op{ .arg, .arg, .mul }; // x * x
    try j.compile(a, &program);
    const square = try j.finalize();
    defer {
        const base: [*]align(std.heap.page_size_min) u8 = @constCast(@ptrCast(@alignCast(square)));
        posix.munmap(base[0..j.code.items.len]);
    }

    try std.testing.expectEqual(@as(i64, 0), square(0));
    try std.testing.expectEqual(@as(i64, 49), square(7));
    try std.testing.expectEqual(@as(i64, 144), square(12));
    try std.testing.expectEqual(@as(i64, 100), square(-10));
}

The whole trick is that push rdi drops the argument onto the same CPU stack every other op already uses, so arg composes with mul exactly like a push would. That is the first step toward JIT-compiling functions that take real parameters.

Exercise 3 -- Instruction-cache safety and cleanup. Wrap the mapping in a CompiledFn struct that owns the base pointer and length, exposes the typed function pointer, and frees itself with munmap -- then add the instruction-cache flush that non-x86 targets need:

const std = @import("std");
const builtin = @import("builtin");
const posix = std.posix;
const linux = std.os.linux;

fn CompiledFn(comptime Fn: type) type {
    return struct {
        base: []align(std.heap.page_size_min) u8,
        func: *const Fn,

        const Self = @This();

        fn init(code: []const u8) !Self {
            const mem = try posix.mmap(
                null,
                code.len,
                .{ .READ = true, .WRITE = true },
                .{ .TYPE = .PRIVATE, .ANONYMOUS = true },
                -1,
                0,
            );
            errdefer posix.munmap(mem);
            @memcpy(mem[0..code.len], code);

            const rc = linux.mprotect(mem.ptr, mem.len, .{ .READ = true, .EXEC = true });
            if (posix.errno(rc) != .SUCCESS) return error.ProtectFailed;

            // x86-64 keeps the instruction and data caches coherent in hardware,
            // so freshly written bytes are runnable immediately. AArch64 does NOT:
            // the CPU may still hold stale instructions for this address, so a
            // portable JIT must flush the i-cache here before the first call.
            if (builtin.cpu.arch == .aarch64) {
                asm volatile (
                    \\ic ivau, %[addr]
                    \\dsb ish
                    \\isb
                    :
                    : [addr] "r" (mem.ptr),
                    : .{ .memory = true });
            }

            return .{ .base = mem, .func = @ptrCast(mem.ptr) };
        }
        fn deinit(self: Self) void {
            posix.munmap(self.base);
        }
    };
}

test "CompiledFn owns and frees its executable mapping" {
    // mov eax, edi ; add eax, esi ; ret  -- returns arg0 + arg1
    const code = [_]u8{ 0x89, 0xF8, 0x01, 0xF0, 0xC3 };
    const Add = CompiledFn(fn (i32, i32) callconv(.c) i32);
    const add = try Add.init(&code);
    defer add.deinit();

    try std.testing.expectEqual(@as(i32, 9), add.func(4, 5));
    try std.testing.expectEqual(@as(i32, 0), add.func(-3, 3));
}

Storing the whole slice (base), not just the pointer, is what makes munmap possible -- the kernel needs the length back. The i-cache flush is a no-op on x86-64 because the hardware snoops writes to code pages for you, but on ARM the data cache and instruction cache are separate and can disagree, so you must explicitly evict and re-synchronise before the CPU is allowed to trust the new bytes. Right, on to regex.

A regex is a description of a machine

Here is the mental shift that makes everything else click. A regular expression is not a string-searching instruction; it is a specification of a finite automaton. The pattern ab*c describes a machine with a handful of states: "I am waiting for an a", "I have seen the a, now I will accept any number of bs", "now I want a c", "I am done". Matching a string means feeding it to that machine one character at a time and asking, at the end, whether the machine is in an accepting state. That is all a regex fundamentally is, and Stephen Kleene proved back in the 1950s that this class of machines and this class of patterns are exactly equivalent.

There are two families of machine. A DFA (deterministic finite automaton) is in exactly one state at a time -- feed it a character and it moves to precisely one next state. Fast, but building one directly from a pattern can blow up in size. An NFA (nondeterministic finite automaton) is allowed to be in several states at once and to take "free" moves between states without consuming any input (these are called epsilon transitions). The NFA is trivially easy to build from a pattern, and -- this is the key insight -- we can simulate its nondeterminism by simply tracking the whole set of states it could currently be in. Today we build and simulate the NFA. Turning it into a DFA is a story for another day.

Why not just backtrack? (a word about ReDoS)

Most regex tutorials, and quite some real libraries (Perl, Python's re, JavaScript, PCRE, Java's java.util.regex), match by backtracking: try one alternative, and if it fails later, rewind and try the next. It is easy to write and it supports fancy features like backreferences. But it has a catastrophic failure mode. Feed the pattern a?a?a?aaa (three optional as followed by three required ones), or the classic (a+)+$, a string that almost matches, and the backtracker explores an exponential number of ways to split the input. A pattern of length n can take O(2^n) time on an input of a few dozen characters. This is not hypothetical -- it is a real denial-of-service vector called ReDoS, and it has taken down production services at Cloudflare and Stack Overflow, among others, when a user-supplied string hit a vulnerable pattern.

The NFA simulation we are about to build cannot do this. Because it tracks the set of reachable states rather than trying paths one at a time, it does at most O(states) work per input character, for a total of O(n * m) where n is the input length and m is the pattern size. Ken Thompson published this method in 1968, and it is the beating heart of the fast, safe regex engines -- Go's regexp, Rust's regex crate, Google's RE2. Correct AND immune to blowups. Wowzers.

Parsing the pattern into a tree

Before we can build a machine we need to understand the pattern's structure, and that means parsing. This is a lovely callback: we built a recursive-descent parser and an AST in episodes 131 to 133, and the exact same skeleton applies here. Our little regex dialect supports literals, . (any character), grouping with (), alternation with |, and the three quantifiers * (zero or more), + (one or more), and ? (zero or one). The AST is a tagged union -- the same tool from episode 6 that has served us all series long:

const Node = union(enum) {
    literal: u8,
    any,
    concat: struct { left: *Node, right: *Node },
    alternate: struct { left: *Node, right: *Node },
    star: *Node,
    plus: *Node,
    optional: *Node,
};

The grammar has the classic precedence ladder: alternation binds loosest, then concatenation, then the quantifiers bind tightest, with parentheses and single characters at the bottom. Each precedence level becomes one function, and each function calls the next level down -- that is the whole recursive-descent recipe:

const Parser = struct {
    src: []const u8,
    pos: usize = 0,
    arena: std.mem.Allocator,

    fn peek(self: *Parser) ?u8 {
        if (self.pos >= self.src.len) return null;
        return self.src[self.pos];
    }
    fn advance(self: *Parser) u8 {
        const c = self.src[self.pos];
        self.pos += 1;
        return c;
    }
    fn create(self: *Parser, node: Node) !*Node {
        const p = try self.arena.create(Node);
        p.* = node;
        return p;
    }

    const ParseError = error{ UnexpectedEnd, UnbalancedParen, UnexpectedToken, OutOfMemory };

    fn parseAlt(self: *Parser) ParseError!*Node {
        var left = try self.parseConcat();
        while (self.peek() == '|') {
            _ = self.advance();
            const right = try self.parseConcat();
            left = try self.create(.{ .alternate = .{ .left = left, .right = right } });
        }
        return left;
    }
    fn parseConcat(self: *Parser) ParseError!*Node {
        var left = try self.parseRepeat();
        while (self.peek()) |c| {
            if (c == '|' or c == ')') break;
            const right = try self.parseRepeat();
            left = try self.create(.{ .concat = .{ .left = left, .right = right } });
        }
        return left;
    }
    fn parseRepeat(self: *Parser) ParseError!*Node {
        var node = try self.parseAtom();
        while (self.peek()) |c| switch (c) {
            '*' => {
                _ = self.advance();
                node = try self.create(.{ .star = node });
            },
            '+' => {
                _ = self.advance();
                node = try self.create(.{ .plus = node });
            },
            '?' => {
                _ = self.advance();
                node = try self.create(.{ .optional = node });
            },
            else => break,
        };
        return node;
    }
    fn parseAtom(self: *Parser) ParseError!*Node {
        const c = self.peek() orelse return error.UnexpectedEnd;
        switch (c) {
            '(' => {
                _ = self.advance();
                const inner = try self.parseAlt();
                if (self.peek() != ')') return error.UnbalancedParen;
                _ = self.advance();
                return inner;
            },
            '.' => {
                _ = self.advance();
                return self.create(.any);
            },
            ')', '|', '*', '+', '?' => return error.UnexpectedToken,
            else => {
                _ = self.advance();
                return self.create(.{ .literal = c });
            },
        }
    }
};

One Zig detail worth pausing on. These four functions are mutually recursive -- parseAtom calls parseAlt for the inside of a group -- and if I had let Zig infer each one's error set, the inference would chase its own tail and the compiler would (rightly) reject it with a "dependency loop" error. The fix is to name the error set explicitly (ParseError) and annotate the return types with it. This is one of those places where Zig's honesty about errors forces you to break a cycle you might not have noticed in a language that quietly papers over it. I allocate every node from an arena (episode 7), so the entire tree is freed in one shot when compilation finishes -- no per-node bookkeeping.

Thompson's construction: fragments with dangling wires

Now the elegant part. We walk the AST and, for each node, emit a small piece of NFA -- a fragment -- then wire fragments together. Each NFA state is one of four kinds: it matches a specific character, it matches any character, it is a split (two epsilon out-edges -- this is where the nondeterminism lives), or it is the final match state. I store states in a flat list and refer to them by index, which sidesteps the pointer-juggling that makes this fiddly in C:

const NfaKind = enum { char, any, split, match };
const NfaState = struct {
    kind: NfaKind,
    ch: u8 = 0,
    out: u32 = 0,
    out1: u32 = 0,
};

The clever bit of Thompson's construction is how it handles half-finished connections. When I build the fragment for a, I create a char state -- but I do not yet know what comes after the a, so its out edge is a dangling wire, a hole to be filled in later by whatever fragment gets concatenated next. I track those holes as a little list, and each combining operation patches the holes of one fragment to point at the start of the next. A fragment is therefore "a start state, plus the set of out-edges still hanging loose":

const Hole = struct { state: u32, slot: u1 };
const Fragment = struct { start: u32, holes: []Hole };

const Builder = struct {
    states: std.ArrayList(NfaState),
    gpa: std.mem.Allocator,

    fn addState(self: *Builder, s: NfaState) !u32 {
        const idx: u32 = @intCast(self.states.items.len);
        try self.states.append(self.gpa, s);
        return idx;
    }
    fn patch(self: *Builder, holes: []const Hole, target: u32) void {
        for (holes) |h| {
            if (h.slot == 0) {
                self.states.items[h.state].out = target;
            } else {
                self.states.items[h.state].out1 = target;
            }
        }
    }
    fn build(self: *Builder, node: *const Node, arena: std.mem.Allocator) !Fragment {
        switch (node.*) {
            .literal => |c| {
                const s = try self.addState(.{ .kind = .char, .ch = c });
                const holes = try arena.alloc(Hole, 1);
                holes[0] = .{ .state = s, .slot = 0 };
                return .{ .start = s, .holes = holes };
            },
            .any => {
                const s = try self.addState(.{ .kind = .any });
                const holes = try arena.alloc(Hole, 1);
                holes[0] = .{ .state = s, .slot = 0 };
                return .{ .start = s, .holes = holes };
            },
            .concat => |pair| {
                const f1 = try self.build(pair.left, arena);
                const f2 = try self.build(pair.right, arena);
                self.patch(f1.holes, f2.start); // wire f1's loose ends into f2
                return .{ .start = f1.start, .holes = f2.holes };
            },
            .alternate => |pair| {
                const f1 = try self.build(pair.left, arena);
                const f2 = try self.build(pair.right, arena);
                // a split state that can go into either branch for free
                const s = try self.addState(.{ .kind = .split, .out = f1.start, .out1 = f2.start });
                const holes = try arena.alloc(Hole, f1.holes.len + f2.holes.len);
                @memcpy(holes[0..f1.holes.len], f1.holes);
                @memcpy(holes[f1.holes.len..], f2.holes);
                return .{ .start = s, .holes = holes };
            },
            .star => |inner| {
                const f = try self.build(inner, arena);
                const s = try self.addState(.{ .kind = .split, .out = f.start });
                self.patch(f.holes, s); // loop the body back to the split
                const holes = try arena.alloc(Hole, 1);
                holes[0] = .{ .state = s, .slot = 1 }; // the "skip it" edge
                return .{ .start = s, .holes = holes };
            },
            .plus => |inner| {
                const f = try self.build(inner, arena);
                const s = try self.addState(.{ .kind = .split, .out = f.start });
                self.patch(f.holes, s);
                const holes = try arena.alloc(Hole, 1);
                holes[0] = .{ .state = s, .slot = 1 };
                return .{ .start = f.start, .holes = holes }; // must run body once
            },
            .optional => |inner| {
                const f = try self.build(inner, arena);
                const s = try self.addState(.{ .kind = .split, .out = f.start });
                const holes = try arena.alloc(Hole, f.holes.len + 1);
                @memcpy(holes[0..f.holes.len], f.holes);
                holes[f.holes.len] = .{ .state = s, .slot = 1 };
                return .{ .start = s, .holes = holes };
            },
        }
    }
};

Study the three quantifiers, because they are where the epsilon magic happens. A split state has two out-edges and consumes nothing -- reaching it means the machine is simultaneously pursuing both edges. For star, the split's first edge leads into the body and the body loops back to the split (zero-or-more times), while the split's second edge is the loose "skip it entirely" wire. plus is almost identical but the fragment's start is the body itself, so the body must run at least once. optional splits between "run the body" and "skip it" with no loop. Concatenation just patches the loose ends of the left fragment straight into the start of the right. Four tiny rules, and they compose to express any pattern in the language.

Simulating the machine: many states at once

The NFA is built; now we run it. The whole idea is to never guess which branch to take -- we follow all of them by keeping a set of currently-active states. Before consuming any character we compute the epsilon-closure of the start state: follow every free split edge until we reach states that actually want to consume input (or the match state). Then for each input character, we look at every active state, keep the ones whose character matches, follow their out-edges (again taking the epsilon-closure), and that becomes the active set for the next character. At the end, if the match state is in the active set, the string matched:

const Regex = struct {
    states: []NfaState,
    start: u32,
    gpa: std.mem.Allocator,

    fn deinit(self: *Regex) void {
        self.gpa.free(self.states);
    }

    // Epsilon-closure: follow free split edges, collect input-consuming states.
    fn addToList(self: *const Regex, list: *std.ArrayList(u32), seen: []bool, s: u32) !void {
        if (seen[s]) return; // the `seen` guard is what stops loops like a* hanging
        seen[s] = true;
        const st = self.states[s];
        if (st.kind == .split) {
            try self.addToList(list, seen, st.out);
            try self.addToList(list, seen, st.out1);
        } else {
            try list.append(self.gpa, s);
        }
    }

    fn matches(self: *const Regex, input: []const u8) !bool {
        const seen = try self.gpa.alloc(bool, self.states.len);
        defer self.gpa.free(seen);

        var clist: std.ArrayList(u32) = .empty; // current active set
        defer clist.deinit(self.gpa);
        var nlist: std.ArrayList(u32) = .empty; // next active set
        defer nlist.deinit(self.gpa);

        @memset(seen, false);
        try self.addToList(&clist, seen, self.start);

        for (input) |c| {
            @memset(seen, false);
            nlist.clearRetainingCapacity();
            for (clist.items) |s| {
                const st = self.states[s];
                const consume = switch (st.kind) {
                    .char => st.ch == c,
                    .any => true,
                    else => false,
                };
                if (consume) try self.addToList(&nlist, seen, st.out);
            }
            std.mem.swap(std.ArrayList(u32), &clist, &nlist);
        }
        for (clist.items) |s| {
            if (self.states[s].kind == .match) return true;
        }
        return false;
    }
};

fn compile(gpa: std.mem.Allocator, pattern: []const u8) !Regex {
    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 builder = Builder{ .states = .empty, .gpa = gpa };
    errdefer builder.states.deinit(gpa);
    const frag = try builder.build(ast, arena);
    const match_state = try builder.addState(.{ .kind = .match });
    builder.patch(frag.holes, match_state); // loose ends of the whole pattern -> match
    const states = try builder.states.toOwnedSlice(gpa);
    return .{ .states = states, .start = frag.start, .gpa = gpa };
}

test "the regex engine matches across the whole feature set" {
    var re = try compile(std.testing.allocator, "a(b|c)*d");
    defer re.deinit();
    try std.testing.expect(try re.matches("ad"));
    try std.testing.expect(try re.matches("abd"));
    try std.testing.expect(try re.matches("abcbcbcd"));
    try std.testing.expect(!try re.matches("abce"));
    try std.testing.expect(!try re.matches("ab"));
}

The seen array is doing double duty and it is the linchpin of the guarantee. Within one step it dedupes the active set (a state is added at most once), and it is what prevents an infinite loop when following the back-edge of a star -- reach a split you have already visited this step, and addToList returns immediately. Because each state enters the active list at most once per character, the inner work is bounded by the number of states, so the total is O(input * states). Notice too that matches treats the pattern as anchored at both ends -- we start at start and require reaching match after consuming the whole input. Substring search (matching anywhere inside a larger text) is a small extension, which I have parked in the exercises.

Proving it, and staying fast

Correctness for a matcher is slippery -- it is easy to pass a handful of hand-picked cases and still be subtly wrong. So beyond example-based tests, I like a property test: state an invariant that must hold for any input, then throw thousands of random inputs at it. Here, (a|b)* must match every possible string of as and bs (including the empty one), and a(a|b)*b must match exactly the strings that start with a, end with b, and are at least two long. If the engine ever disagrees with that independent predicate, the test fails and hands me the offending input:

test "property test over many random inputs stays correct and linear" {
    const gpa = std.testing.allocator;

    var any_ab = try compile(gpa, "(a|b)*");
    defer any_ab.deinit();
    var a_to_b = try compile(gpa, "a(a|b)*b");
    defer a_to_b.deinit();

    var prng = std.Random.DefaultPrng.init(0x5eed);
    const rand = prng.random();
    var buf: [200]u8 = undefined;

    var trial: usize = 0;
    while (trial < 2000) : (trial += 1) {
        const len = rand.intRangeAtMost(usize, 0, buf.len);
        for (buf[0..len]) |*ch| ch.* = if (rand.boolean()) 'a' else 'b';
        const s = buf[0..len];

        try std.testing.expect(try any_ab.matches(s));

        const expected = len >= 2 and s[0] == 'a' and s[len - 1] == 'b';
        try std.testing.expectEqual(expected, try a_to_b.matches(s));
    }
}

Two thousand random strings, some two hundred characters long, and the whole test finishes in a blink -- which is itself the point. Hand that same a?a?a?... shape to a backtracking engine and it would still be chewing on it long after you gave up. The NFA does not care how "ambiguous" the pattern looks, because it never explores paths one at a time; it explores them all in lockstep. That is the difference between O(n * m) and O(2^n) made concrete.

How C, Rust, and Go do it

This is not a toy technique dressed up for a tutorial -- it is what the serious engines actually do, and the split runs right down the middle of the ecosystem. The backtracking camp (PCRE in C, Perl, Python's re, Ruby, Java, JavaScript's built-in RegExp) trades worst-case safety for features like backreferences and lookaround, and every one of them can be brought to its knees by a malicious pattern-plus-input. The automaton camp chose the other trade. Google's RE2 (C++), which Russ Cox wrote after documenting exactly this Thompson method, guarantees linear-time matching and is used across Google's infrastructure precisely because untrusted users supply the patterns. Go's standard-library regexp is built on the same ideas -- linear time, no backreferences, no ReDoS. Rust's regex crate is a finite-automaton engine too, famous for being both safe and blisteringly fast, using a lazily-built DFA on top of exactly the NFA structure we just wrote. So the thing you built today is not a simplified imitation of the real ones -- it is the actual foundation they stand on, minus the years of optimisation.

Our version is deliberately the smallest honest thing that works: no character classes, no anchors, no captures, no Unicode, and it rebuilds the epsilon-closure from scratch every step. Every one of those is a known, well-trodden extension rather than a redesign. The single biggest speedup, and the natural next move, is to stop recomputing state-sets that you have seen before -- cache them, and the NFA quietly turns into something that visits one state per character in stead of a set. But that is a subject for its own episode. ;-)

Exercises

  1. Character classes. Extend the parser and NFA to support [abc] (match any one of the listed characters) and ranges like [a-z]. Add a class node to the AST that stores a 256-bit set (a [32]u8 bitset, or a std.StaticBitSet(256)), a matching class NFA state, and the consume logic in matches. Test that [a-f]+ matches "cafe" but not "code" (the o is out of range).

  2. Substring search. Right now matches is anchored at both ends. Add a search method that returns true if the pattern matches anywhere inside the input, not only the whole string. The classic trick is to add a fresh copy of the start-state's closure into the active set at every input position (so a new match attempt can begin at each character). Test that searching for b+c succeeds inside "aaabbbcxx".

  3. Cache the state sets. Instrument matches to record, for each step, the sorted list of active state indices, and count how many distinct active sets ever occur across a long input. You will find the number is small and bounded -- far smaller than the input length -- which means you are recomputing the same closures over and over. Add a cache keyed by the state-set so a set you have seen before returns instantly. This memoisation is the exact seam where linear-set simulation turns into something faster still.

That is a complete regular expression engine -- parser, Thompson-constructed NFA, and a linear-time set simulation -- in a couple hundred lines of Zig, and immune by construction to the blowups that plague the backtracking crowd. Thanks for reading -- de groeten, en tot de volgende! ;-)

@scipio

stem stemsocial steemstem zig programming
0
0
0.000
1 comments
avatar

scipio! you're still here!! I have massive headache so I can't read all this rn.. but I hope to come back :D

0
0
0.000
Reply