scrobble.life
StemSocial

Learn Zig Series (#155) - Mini Project: Regex Engine - Matching

scipio@scipio (71)22h

Learn Zig Series (#155) - Mini Project: Regex Engine - Matching

zig.png

Part of a multi-episode project

What will I learn?

  • How to run the NFA we built last episode -- feeding it text and getting back a yes-or-no answer, without ever backtracking;
  • The single most important trick in the whole engine: tracking the set of states the machine is in all at once, advancing every one of them in lockstep, one input byte at a time;
  • Why the epsilon-closure walk we wrote for testing last time turns out to be the beating heart of the matcher, and how to grow it from a throwaway helper into a reusable StateSet;
  • How to write an anchored full match (does the pattern match the whole string) and an unanchored search (does it match anywhere), and how one small re-seeding change turns the first into the second;
  • Why Zig's flat []State and u32 indices let us keep two state-sets and ping-pong between them with a single pointer swap and zero allocation per input byte;
  • How to test a matcher against the exact patterns that hang naive engines, and prove ours stays linear on a hundred thousand characters;
  • What "catastrophic backtracking" really is, why our design is immune to it, and how C, Rust and Go make the same guarantee.

Requirements

  • A working modern computer running macOS, Windows or Ubuntu;
  • An installed Zig 0.14+ distribution (download from ziglang.org) -- the code here is written and tested against Zig 0.16;
  • The NFA from episode 154 -- its State, Nfa and Symbol types and the build() function -- because today we simulate exactly that machine; if you skipped it, read it first, this half does not stand alone;
  • Allocators (the arena) from episode 7 and tagged unions from episode 6 are the two language features we lean on hardest;
  • The ambition to learn Zig programming.

Difficulty

  • Advanced

Curriculum (of the Learn Zig Series):

Learn Zig Series (#155) - Mini Project: Regex Engine - Matching

Last episode we built a machine and then, slightly cruelly, refused to run it. We took a pattern like a(b|c)*d, parsed it into a tree, and walked that tree with Thompson's construction to wire up a nondeterministic finite automaton -- a flat []State of states joined by labelled edges (consume a byte) and epsilon edges (free, consume nothing). We even wrote a little epsilon-closure walk called epsAdd to test the wiring, and I told you, twice, to keep that idea in your pocket. Today we cash it in. By the end of this post the engine actually matches text, and -- this is the part I care about -- it matches in guaranteed linear time, immune to the catastrophic blow-up that hangs the regex engines shipped in Perl, Python and JavaScript. That is not a small claim, and it is the whole reason we did the work the way we did.

Let me recap the types from episode 154 in one block, because everything today attaches to them. If your file from last time is open, this is already there:

const std = @import("std");

const Symbol = union(enum) { literal: u8, any };

const State = struct {
    symbol: ?Symbol = null, // a labelled (input-consuming) edge, or null for none
    symbol_target: u32 = 0, // where that labelled edge goes
    eps: [2]?u32 = .{ null, null }, // up to two free (epsilon) edges
    accept: bool = false,
};

const Nfa = struct {
    states: []State,
    start: u32,
};

A state is either a consuming state (it has a symbol and a symbol_target, and no epsilon edges) or a branching state (it has one or two epsilon edges and no symbol). Thompson's construction never produces a state that is both, which is a fact we are about to exploit hard. build(arena, pattern) from last episode hands us a finished Nfa. Here we go!

The one idea: be in many states at once

The word nondeterministic in NFA is the crux, and it trips people up, so let us kill the confusion right now. A deterministic machine, reading a byte, moves to exactly one next state -- easy to run, you just follow the arrow. Our machine is not like that. Standing on a split state, feeding it nothing, it can follow both epsilon edges. Standing on the accept state of a * loop, it can loop back or exit. So "which state is the machine in?" has no single answer -- it is in a whole set of states simultaneously.

The naive way to handle nondeterminism is to guess: try one branch, and if the match fails, back up and try the other. That is backtracking, and it is exactly the design that explodes. The good way -- Thompson's way, and Ken Thompson published it in 1968 -- is to refuse to guess. In stead of exploring one path at a time, we track every state the machine could possibly be in, all at once, and advance the entire set by one input byte in lockstep. There is no backtracking because there is nothing to back up from: we already carry all the possibilities forward together.

Because the NFA has at most 2n states for a pattern of length n, the "set of possible states" can never contain more than 2n entries. Advancing it one byte is at most O(n) work. Text of length m therefore costs O(n * m) -- linear in the text, no matter how nasty the pattern. That bound is the entire payoff, and you will see it hold at the end on a pattern that would otherwise hang for a small eternity.

A reusable state set

We need a container for "the set of states the machine is currently in." Two operations dominate: adding a state (and, because epsilon edges are free, everything reachable from it for free), and iterating the members to advance them. We also want to clear it cheaply between input bytes.

I could reach for std.AutoHashMap, but this is the kind of place where Zig invites you to notice you know more than a general container does. The universe of possible members is tiny and fixed -- state ids 0..n -- so the perfect representation is a bool array indexed by id (membership test in one load) paired with a flat list of the ids actually present (iteration without scanning n slots). Both are sized exactly nfa.states.len, allocated once:

const StateSet = struct {
    ids: []u32, // the members, in insertion order
    len: usize, // how many are live
    on: []bool, // on[id] == true iff id is a member

    fn init(arena: std.mem.Allocator, n: usize) !StateSet {
        return .{
            .ids = try arena.alloc(u32, n),
            .len = 0,
            .on = try arena.alloc(bool, n),
        };
    }

    fn clear(self: *StateSet) void {
        for (self.ids[0..self.len]) |id| self.on[id] = false;
        self.len = 0;
    }
};

Notice clear is O(len), not O(n): it only touches the on flags it actually set, using the ids list as its own undo log. On a big pattern where only a handful of states are live at a time, that is the difference between clearing three flags and memset-ing ten thousand. This is a small thing, but it is the kind of small thing that adds up in a hot loop, and Zig makes the cost visible enough that you think about it.

The epsilon-closure, promoted

Here is the moment I promised. Adding a state to the set is not just "flip one flag" -- because epsilon edges are free, adding a state means also adding everything reachable from it through epsilon edges. That is the epsilon-closure, and it is the exact same walk as last episode's epsAdd, only now it writes into our StateSet in stead of a bare visited array:

fn addState(nfa: Nfa, set: *StateSet, id: u32) void {
    if (set.on[id]) return; // already in the set -- and this stops cycles
    set.on[id] = true;
    set.ids[set.len] = id;
    set.len += 1;
    for (nfa.states[id].eps) |maybe| {
        if (maybe) |t| addState(nfa, set, t);
    }
}

Three lines of bookkeeping, then recurse down both epsilon edges. The if (set.on[id]) return guard is doing double duty: it keeps the set free of duplicates, and it is what makes an a* loop (whose body's accept epsilon-edges back to its own start) terminate in stead of spinning forever. A * creates a genuine cycle of epsilon edges, and without that visited-check the closure would recurse until the stack gave out. With it, every state is visited at most once, so the closure is O(n) and always halts. That is the whole reason the [2]?u32 slots hold indices we can mark, not pointers we would chase blindly.

One step of the machine

Now the lockstep advance. Given the current set of states and one input byte c, produce the next set. The rule is simple and reads straight off the state type: for each consuming state currently live, if its symbol matches c, then the state its labelled edge points at becomes live in the next set (and, via addState, so does that state's epsilon-closure). Branching states -- the ones with null symbol -- contribute nothing here; their job was already done when the closure pulled them in.

fn step(nfa: Nfa, current: StateSet, next: *StateSet, c: u8) void {
    next.clear();
    for (current.ids[0..current.len]) |id| {
        const sym = nfa.states[id].symbol orelse continue; // skip branch states
        const consumes = switch (sym) {
            .literal => |lit| lit == c,
            .any => true, // '.' matches any single byte
        };
        if (consumes) addState(nfa, next, nfa.states[id].symbol_target);
    }
}

That orelse continue is the tagged-union payoff again: "this state has no labelled edge" is a first-class null, so we skip it without a special-case sentinel. The switch over Symbol is exhaustive -- if a later episode adds character classes as a third Symbol variant, this switch stops compiling until we handle it, which is exactly the reminder you want. And every state we add flows through the epsilon-closure, so the next set is always closed: it already contains every state reachable for free. Keeping the set closed at all times is the invariant that makes the match check at the end a one-liner.

Anchored matching: does it match the whole string

We have all the parts. An anchored match asks: does the pattern match the entire text, start to finish? Seed the set with the closure of the start state, step it once per input byte, and at the end ask whether any live state is an accept state:

fn matches(arena: std.mem.Allocator, nfa: Nfa, text: []const u8) !bool {
    var a = try StateSet.init(arena, nfa.states.len);
    var b = try StateSet.init(arena, nfa.states.len);
    var current = &a;
    var next = &b;

    current.clear();
    addState(nfa, current, nfa.start); // the closure of the start is our seed
    for (text) |c| {
        step(nfa, current.*, next, c);
        const tmp = current; // ping-pong: next becomes current
        current = next;
        next = tmp;
        if (current.len == 0) return false; // no live states -- give up early
    }
    for (current.ids[0..current.len]) |id| {
        if (nfa.states[id].accept) return true;
    }
    return false;
}

Two things earn their keep here. First, the ping-pong: we allocate two state-sets up front and swap the current/next pointers each byte, so the main loop does zero allocation -- no per-character garbage, no allocator in the hot path at all. Because a StateSet is just two slices and a length, swapping is a three-line pointer shuffle. Second, if (current.len == 0) return false: once the live set empties, no future byte can revive it (you cannot step out of nothing), so we bail immediately in stead of grinding through the rest of a megabyte. On a non-matching input that dies early, that turns a full scan into a short one.

Unanchored search: does it match anywhere

Anchored matching is the strict question. The one you usually want -- the one grep asks -- is unanchored: does the pattern occur somewhere in the text? The clever bit is how little has to change. A match may begin at any position, so at every step we also inject the start state's closure into the live set, and we succeed the instant any accept state goes live:

fn anyAccept(nfa: Nfa, set: StateSet) bool {
    for (set.ids[0..set.len]) |id| {
        if (nfa.states[id].accept) return true;
    }
    return false;
}

fn search(arena: std.mem.Allocator, nfa: Nfa, text: []const u8) !bool {
    var a = try StateSet.init(arena, nfa.states.len);
    var b = try StateSet.init(arena, nfa.states.len);
    var current = &a;
    var next = &b;

    current.clear();
    addState(nfa, current, nfa.start);
    if (anyAccept(nfa, current.*)) return true; // pattern matches empty, at pos 0
    for (text) |c| {
        step(nfa, current.*, next, c);
        addState(nfa, next, nfa.start); // a fresh match may start right here
        const tmp = current;
        current = next;
        next = tmp;
        if (anyAccept(nfa, current.*)) return true;
    }
    return false;
}

The single new line -- addState(nfa, next, nfa.start) after each step -- is the entire difference between "match the whole thing" and "find it anywhere." It is the moral equivalent of wrapping the pattern in an implicit .* on the left, but done at simulation time for free in stead of by growing the machine. And because the StateSet de-duplicates, re-seeding the start every byte costs nothing when those states are already live -- the if (set.on[id]) return guard swallows the repeat. Notice too that many potential matches are being tracked in parallel: a match that started at byte 0 and another that started at byte 40 are both just states in the same set, advancing together, no separate bookkeeping. That is the nondeterminism working for us.

Testing behaviour, at last

Last episode we could only test structure -- "is the graph wired right?" Now we can test behaviour, and the tests read like a specification of the dialect. Each one builds a pattern with build() and asserts what should and should not match:

test "literals and concatenation" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const nfa = try build(arena.allocator(), "abc");
    try std.testing.expect(try matches(arena.allocator(), nfa, "abc"));
    try std.testing.expect(!try matches(arena.allocator(), nfa, "ab")); // too short
    try std.testing.expect(!try matches(arena.allocator(), nfa, "abcd")); // trailing junk
}

That first test already pins down the anchored semantics: abc matches abc and nothing shorter or longer, because we ask for an accept state after consuming the whole text. Now the operators, each with a should-match and a should-not:

test "alternation, star, plus, opt and the wildcard" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const a = arena.allocator();

    const alt = try build(a, "gr(a|e)y");
    try std.testing.expect(try matches(a, alt, "gray"));
    try std.testing.expect(try matches(a, alt, "grey"));
    try std.testing.expect(!try matches(a, alt, "groy"));

    const star = try build(a, "ab*c");
    try std.testing.expect(try matches(a, star, "ac")); // zero b's
    try std.testing.expect(try matches(a, star, "abbbbc")); // many b's

    const dot = try build(a, "a.c");
    try std.testing.expect(try matches(a, dot, "axc"));
    try std.testing.expect(!try matches(a, dot, "ac")); // '.' needs one byte
}

And the unanchored search, which is the one you would actually reach for when scanning a haystack:

test "search finds a match anywhere in the haystack" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const a = arena.allocator();
    const nfa = try build(a, "b(a|n)+");
    try std.testing.expect(try search(a, nfa, "a wild banana appears"));
    try std.testing.expect(!try search(a, nfa, "no fruit here"));
}

Run zig test and these go green against Zig 0.16. What I like about testing a matcher this way is that the tests are legible to anyone who knows regexes at all -- gr(a|e)y should match gray and grey but not groy, and there it is. When you later add a feature (say character classes), you write the failing test first in exactly this shape, and the red-green loop from episode 12 guides the whole extension. Behavioural tests like these are also where you catch the off-by-one mistakes that structural tests cannot see: a.c matching ac would be a bug the graph-shape tests would happily wave through.

Performance: the pattern that hangs everyone else

Now the demonstration I have been building toward for two episodes. There is a famous class of patterns -- (a+)+, (a|a)*, (a*)* -- that reduce backtracking engines to a crawl. Feed (a+)+b a string of forty as followed by no b, and a backtracking engine tries every possible way to split those as between the inner and outer + before finally admitting there is no b -- an exponential number of splits. That is ReDoS, and it is a real, exploited denial-of-service class: an attacker submits one short string to a form and pins a CPU core. Our engine does not care, because it never splits anything -- it carries the whole state set forward once per byte. Let us prove it, at a scale a backtracker could never survive:

test "pathological pattern stays linear on 100k bytes" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const a = arena.allocator();
    const nfa = try build(a, "(a+)+b");

    const text = try a.alloc(u8, 100_000);
    @memset(text, 'a'); // all a's, no b -- the backtracker's worst nightmare

    try std.testing.expect(!try matches(a, nfa, text)); // no 'b' -> no match
}

The mere fact that this test finishes -- instantly, faster than the arena took to hand out the buffer -- is the proof. A backtracking engine on the same input with only fourty as would still be chewing after the heat death of your patience. Ours walks the hundred thousand bytes once, each byte touching a handful of states, and returns. That is O(n * m) you can feel. And nota bene: the linear guarantee is structural, not a tuning trick -- the preallocated []State, the u32 indices and the ping-pong buffers are constant-factor niceties on top, but the immunity to blow-up comes from the algorithm itself refusing to backtrack.

The same machine in C, Rust and Go

Building the simulator makes the design decisions of the production engines legible. C is the origin: Russ Cox's superb regex article series simulates the Thompson NFA with essentially this loop -- a current and a next list of states, a per-step increment to avoid clearing, and an addstate that follows split edges recursively. The bones are identical; what Zig gives us over the C is the arena (no manual free of the state lists) and the tagged ?Symbol (no sentinel opcodes). Go's standard regexp is the industrial descendant of that C -- Cox wrote it too -- and it guarantees the same linear worst case for precisely the reason ours does: it will not backtrack, ever, which is why reaching for Go's regexp on untrusted input is a safe default and reaching for a backtracking engine is not. Rust's regex crate is the speed champion and takes the idea furthest: it builds this same NFA, frequently compiles onward to a DFA (the subject-conversion we sketched back in episode 142), and bolts on SIMD literal prefiltering -- but its headline promise, the one its author defends at length, is the very guarantee we just demonstrated: no catastrophic backtracking, linear time, always. Our engine is a teaching-sized member of that exact family. The four languages differ in memory strategy and constant factors; they agree completely on the thing that matters, which is that guessing-and-backing-up is a trap and set-based simulation is the way out.

Where we go next, and what you built

Stand back and look at the whole two-episode arc. You wrote a recursive-descent parser that turns a(b|c)*d into a tree; a Thompson compiler that walks the tree and wires an NFA into a single arena slice whose size you could prove in advance; and now a simulator that runs that NFA over text in guaranteed linear time, in both anchored and unanchored flavours, allocating nothing per byte. That is a genuine regular expression engine -- small, correct, and fast in the way that actually matters -- built from absolutely nothing but the language and its allocators. Almost nobody who uses regexes daily could write one; you now can.

There is plenty of room to grow it, and the shape of the code invites it. Character classes like [a-z] are a new Symbol variant and a small parser addition -- and the exhaustive switch in step will tell you every place that needs a new case, which is the type system doing your code review. Anchors (^, $), capturing groups that report where a submatch landed, non-greedy operators -- each is a bounded extension of what is already here, and each is a good weekend. But the core, the engine that cannot be tricked into hanging, is done. Next time we turn away from parsing-and-simulating and point the series at a different corner of systems work -- keep the idea of "track a set, advance it in lockstep" with you, because it is one of those algorithmic shapes that shows up far beyond regexes once you know to look for it. Thanks for reading, and I will see you in the next one! ;-)

@scipio

Comments · 1