Find & Replace — Zig source

//! Find & replace with literal or regex matching, $-substitution
//! ($1 backrefs, $&, $$), case sensitivity, whole-word, and global modes.
//!
//! Language: Zig 0.13 (standard library only)
//! Source:   CosmoDev polyglot showcase port of the find-replace tool,
//!           ported from src/lib/findReplace.ts (the canonical TypeScript
//!           implementation).
//! License:  display source — part of CosmoDev's polyglot tool pages.
//!
//! Zig's standard library has no regex engine, so this port carries a small
//! backtracking one — a find-replace tool's core IS a regex matcher. The
//! pattern compiles to a program of instructions and runs on an explicit
//! backtrack stack (an undo log restores capture slots on backtrack), which
//! reproduces JavaScript's leftmost + preference-order semantics rather
//! than POSIX leftmost-longest. Supported syntax (the common JS core):
//! literals, `.`, classes `[...]` with ranges and negation, escapes
//! `\d \D \w \W \s \S \b \B \n \t \r \f \v` plus identity escapes, groups
//! numbered by open paren, alternation `|`, quantifiers `* + ? {m} {m,}
//! {m,n}` with lazy `?` variants, and anchors `^ $` (line-aware under the
//! multiline flag); a malformed `{...}` is a literal `{`, as in JS.
//! Lookarounds and backreferences are rejected at compile time. Matching is
//! byte-oriented over the UTF-8 input with ASCII classes and ASCII case
//! folding. Worst case is exponential like any backtracking engine;
//! realistic find-replace patterns run linear in practice.
//!
//! Mirrors the live lib: a literal find string is escaped and matched
//! verbatim; an isRegex find is compiled as-is. `\b` wraps the pattern when
//! wholeWord is set. Case-insensitivity folds into byte comparison (the JS
//! i flag) and multiline changes ^/$ anchoring (the JS m flag, applied only
//! for regex finds). Invalid patterns return an error string instead of
//! erroring out, and an empty find is a no-op. Replacement $-substitution
//! (expandReplacement) matches JavaScript's String.replace exactly for the
//! realistic cases: `$$` -> `$`, `$&` -> whole match, `$1`..`$99` ->
//! capture group (literal "$<digits>" when out of range). JS's $` and $'
//! are unsupported.

const std = @import("std");

pub const Options = struct {
    is_regex: bool = false,
    case_sensitive: bool = true,
    whole_word: bool = false,
    global: bool = true,
    multiline: bool = false,
};

pub const FindReplaceResult = struct {
    result: []const u8,
    matches: usize,
    err: ?[]const u8 = null,
};

const PErr = error{ Syntax, OutOfMemory };

// ---- byte classifiers (ASCII, like the JS classes on ASCII input) ----

fn isDigit(c: u8) bool {
    return c >= '0' and c <= '9';
}

fn isWordByte(c: u8) bool {
    return (c >= 'a' and c <= 'z') or (c >= 'A' and c <= 'Z') or isDigit(c) or c == '_';
}

fn isSpace(c: u8) bool {
    return c == ' ' or c == '\t' or c == '\r' or c == '\n' or c == 0x0B or c == 0x0C;
}

fn toLowerAscii(c: u8) u8 {
    return if (c >= 'A' and c <= 'Z') c + 32 else c;
}

fn byteEq(a: u8, b: u8, icase: bool) bool {
    if (a == b) return true;
    if (!icase) return false;
    return toLowerAscii(a) == toLowerAscii(b);
}

/// \b at pos: exactly one side is a word byte (or a bound).
fn atWordBoundary(input: []const u8, pos: usize) bool {
    const before = pos > 0 and isWordByte(input[pos - 1]);
    const after = pos < input.len and isWordByte(input[pos]);
    return before != after;
}

// ---- compiled program ----

const Op = enum {
    char, // one literal byte (case-folded when icase)
    any, // any byte except '\n'
    class, // one byte against a class
    split, // try x first, backtrack to y
    jmp,
    save, // caps[x] = sp (logged for undo)
    bol, // ^ : input start, or after '\n' when multiline
    eol, // $ : input end, or before '\n' when multiline
    wordb, // \b
    nwordb, // \B
    dig, ndig, wrd, nwrd, spc, nspc, // \d \D \w \W \s \S
    match, // accept
};

const Inst = struct {
    op: Op,
    x: u32 = 0, // jmp/split target, or save slot
    y: u32 = 0, // split alternate
    ch: u8 = 0, // char operand
    ci: u32 = 0, // class index
};

const EntryKind = enum { range, digit, not_digit, word, not_word, space, not_space };

const ClassEntry = struct {
    kind: EntryKind,
    lo: u8 = 0,
    hi: u8 = 0,
};

const Class = struct {
    negate: bool,
    entries: []const ClassEntry,
};

fn classMatches(cl: Class, c: u8, icase: bool) bool {
    var hit = false;
    for (cl.entries) |e| {
        const m = switch (e.kind) {
            .range => (c >= e.lo and c <= e.hi) or
                (icase and toLowerAscii(c) >= e.lo and toLowerAscii(c) <= e.hi),
            .digit => isDigit(c),
            .not_digit => !isDigit(c),
            .word => isWordByte(c),
            .not_word => !isWordByte(c),
            .space => isSpace(c),
            .not_space => !isSpace(c),
        };
        if (m) {
            hit = true;
            break;
        }
    }
    return if (cl.negate) !hit else hit;
}

const Prog = struct {
    insts: []const Inst,
    classes: []const Class,
    ngroups: u32, // explicit capture groups; slots = 2 * (n + 1)
    multiline: bool,
    icase: bool,
};

// ---- AST ----

const NodeKind = enum {
    empty, char, any, class, shorth, group, alt, concat,
    star, plus, quest, rangeq, bol, eol, wordb, nwordb,
};

const Node = struct {
    kind: NodeKind,
    ch: u8 = 0, // char operand, or shorthand set (0=digit 1=word 2=space)
    neg: bool = false, // shorthand negated (\D \W \S)
    class_idx: u32 = 0,
    group_no: u32 = 0,
    m: u32 = 0,
    n: u32 = 0,
    has_n: bool = false,
    open: bool = false, // {m,}
    lazy: bool = false,
    child: ?*Node = null, // quantifier / group body
    head: ?*Node = null, // first of a concat / alt sibling list
    next: ?*Node = null, // next sibling
};

const Braces = struct { m: u32, n: u32 = 0, has_n: bool = false, open: bool = false };

const Parser = struct {
    pat: []const u8,
    i: usize = 0,
    alloc: std.mem.Allocator,
    prog: std.ArrayList(Inst),
    classes: std.ArrayList(Class),
    ngroups: u32 = 0,
    err_msg: ?[]const u8 = null,

    fn fail(p: *Parser, msg: []const u8) PErr {
        if (p.err_msg == null) p.err_msg = msg;
        return error.Syntax;
    }

    fn peek(p: *const Parser) u8 {
        return if (p.i < p.pat.len) p.pat[p.i] else 0;
    }

    fn newNode(p: *Parser, kind: NodeKind) PErr!*Node {
        const n = try p.alloc.create(Node);
        n.* = .{ .kind = kind };
        return n;
    }

    fn charNode(p: *Parser, ch: u8) PErr!*Node {
        const n = try p.newNode(.char);
        n.ch = ch;
        return n;
    }

    fn shorthandNode(p: *Parser, set: u8, negated: bool) PErr!*Node {
        const n = try p.newNode(.shorth);
        n.ch = set;
        n.neg = negated;
        return n;
    }

    /// alt := concat ('|' concat)* — a single concat collapses to itself.
    fn parseAlt(p: *Parser) PErr!*Node {
        var head: ?*Node = null;
        var tail: ?*Node = null;
        while (true) {
            const c = try p.parseConcat();
            if (head == null) {
                head = c;
            } else {
                tail.?.next = c;
            }
            tail = c;
            if (p.peek() != '|') break;
            p.i += 1;
        }
        if (head.?.next == null) return head.?;
        const a = try p.newNode(.alt);
        a.head = head;
        return a;
    }

    fn parseConcat(p: *Parser) PErr!*Node {
        var head: ?*Node = null;
        var tail: ?*Node = null;
        while (true) {
            const c = p.peek();
            if (c == 0 or c == '|' or c == ')') break;
            const item = try p.parseRepeat();
            if (head == null) {
                head = item;
            } else {
                tail.?.next = item;
            }
            tail = item;
        }
        if (head == null) return try p.newNode(.empty);
        if (head.?.next == null) return head.?;
        const k = try p.newNode(.concat);
        k.head = head;
        return k;
    }

    fn parseRepeat(p: *Parser) PErr!*Node {
        var atom = try p.parseAtom();
        while (true) {
            const q = p.peek();
            if (q == '*' or q == '+' or q == '?') {
                p.i += 1;
                const node = try p.newNode(switch (q) {
                    '*' => .star,
                    '+' => .plus,
                    else => .quest,
                });
                if (p.peek() == '?') {
                    node.lazy = true;
                    p.i += 1;
                }
                node.child = atom;
                atom = node;
                // A second quantifier (a*+) is rejected, as JS does.
                const q2 = p.peek();
                if (q2 == '*' or q2 == '+' or q2 == '?') return p.fail("nested quantifier");
                continue;
            }
            if (q == '{') {
                const b = (try p.parseBraces()) orelse break; // literal '{', as in JS
                const node = try p.newNode(.rangeq);
                node.m = b.m;
                node.n = b.n;
                node.has_n = b.has_n;
                node.open = b.open;
                if (p.peek() == '?') {
                    node.lazy = true;
                    p.i += 1;
                }
                node.child = atom;
                atom = node;
                const q2 = p.peek();
                if (q2 == '*' or q2 == '+' or q2 == '?') return p.fail("nested quantifier");
                continue;
            }
            break;
        }
        return atom;
    }

    /// Try {m} / {m,} / {m,n}; null (position restored) when malformed.
    fn parseBraces(p: *Parser) PErr!?Braces {
        const save = p.i;
        p.i += 1; // '{'
        var m: u32 = 0;
        var got = false;
        while (isDigit(p.peek())) {
            m = m * 10 + (p.peek() - '0');
            p.i += 1;
            got = true;
        }
        if (!got) {
            p.i = save;
            return null;
        }
        var b = Braces{ .m = m, .n = m };
        if (p.peek() == ',') {
            p.i += 1;
            if (p.peek() == '}') {
                p.i += 1;
                b.open = true;
                return b; // {m,}
            }
            var n: u32 = 0;
            var gotn = false;
            while (isDigit(p.peek())) {
                n = n * 10 + (p.peek() - '0');
                p.i += 1;
                gotn = true;
            }
            if (!gotn or p.peek() != '}') {
                p.i = save;
                return null;
            }
            p.i += 1;
            if (n < m) return p.fail("brace range out of order");
            b.n = n;
            b.has_n = true;
            return b; // {m,n}
        }
        if (p.peek() != '}') {
            p.i = save;
            return null;
        }
        p.i += 1;
        return b; // {m} exact
    }

    fn parseAtom(p: *Parser) PErr!*Node {
        const c = p.peek();
        switch (c) {
            0, '|' => return p.fail("missing pattern"),
            '(' => {
                p.i += 1;
                if (p.peek() == '?') return p.fail("group flags / lookarounds not supported");
                p.ngroups += 1;
                const g = p.ngroups;
                const body = try p.parseAlt();
                if (p.peek() != ')') return p.fail("missing ')'");
                p.i += 1;
                const n = try p.newNode(.group);
                n.group_no = g;
                n.child = body;
                return n;
            },
            '[' => return p.parseClass(),
            '.' => {
                p.i += 1;
                return try p.newNode(.any);
            },
            '^' => {
                p.i += 1;
                return try p.newNode(.bol);
            },
            '$' => {
                p.i += 1;
                return try p.newNode(.eol);
            },
            '\\' => {
                p.i += 1;
                const e = p.peek();
                if (e == 0) return p.fail("trailing backslash");
                p.i += 1;
                return try p.escapeNode(e);
            },
            '*', '+', '?' => return p.fail("quantifier with nothing to repeat"),
            else => {
                p.i += 1;
                return try p.charNode(c);
            },
        }
    }

    fn escapeNode(p: *Parser, e: u8) PErr!*Node {
        return switch (e) {
            'd' => try p.shorthandNode(0, false),
            'D' => try p.shorthandNode(0, true),
            'w' => try p.shorthandNode(1, false),
            'W' => try p.shorthandNode(1, true),
            's' => try p.shorthandNode(2, false),
            'S' => try p.shorthandNode(2, true),
            'b' => try p.newNode(.wordb),
            'B' => try p.newNode(.nwordb),
            'n' => try p.charNode('\n'),
            't' => try p.charNode('\t'),
            'r' => try p.charNode('\r'),
            'f' => try p.charNode(0x0C),
            'v' => try p.charNode(0x0B),
            '0' => try p.charNode(0),
            else => try p.charNode(e), // identity escape, as in JS
        };
    }

    fn parseClass(p: *Parser) PErr!*Node {
        p.i += 1; // '['
        var negate = false;
        if (p.peek() == '^') {
            negate = true;
            p.i += 1;
        }
        var entries = std.ArrayList(ClassEntry).init(p.alloc);
        while (true) {
            const c = p.peek();
            if (c == 0) return p.fail("unterminated class");
            if (c == ']') {
                p.i += 1;
                break;
            }
            // One element: escape / shorthand / literal byte, maybe a range.
            var lo: u8 = undefined;
            var shorthand: ?EntryKind = null;
            if (c == '\\') {
                p.i += 1;
                const e = p.peek();
                if (e == 0) return p.fail("trailing backslash in class");
                p.i += 1;
                switch (e) {
                    'd' => shorthand = .digit,
                    'D' => shorthand = .not_digit,
                    'w' => shorthand = .word,
                    'W' => shorthand = .not_word,
                    's' => shorthand = .space,
                    'S' => shorthand = .not_space,
                    'n' => lo = '\n',
                    't' => lo = '\t',
                    'r' => lo = '\r',
                    'f' => lo = 0x0C,
                    'v' => lo = 0x0B,
                    '0' => lo = 0,
                    else => lo = e,
                }
            } else {
                lo = c;
                p.i += 1;
            }
            if (shorthand) |k| {
                try entries.append(.{ .kind = k });
                continue;
            }
            // Range? '-' followed by something other than ']' or the end.
            const can_range = p.i < p.pat.len and p.pat[p.i] == '-' and
                p.i + 1 < p.pat.len and p.pat[p.i + 1] != ']' and p.pat[p.i + 1] != 0;
            if (can_range) {
                p.i += 1; // '-'
                var hi: u8 = undefined;
                const hc = p.peek();
                if (hc == '\\') {
                    p.i += 1;
                    const e = p.peek();
                    if (e == 0) return p.fail("trailing backslash in class");
                    p.i += 1;
                    hi = switch (e) {
                        'n' => '\n',
                        't' => '\t',
                        'r' => '\r',
                        'f' => 0x0C,
                        'v' => 0x0B,
                        '0' => 0,
                        else => e,
                    };
                } else {
                    hi = hc;
                    p.i += 1;
                }
                if (hi < lo) return p.fail("class range out of order");
                try entries.append(.{ .kind = .range, .lo = lo, .hi = hi });
            } else {
                try entries.append(.{ .kind = .range, .lo = lo, .hi = lo });
            }
        }
        const n = try p.newNode(.class);
        n.class_idx = @intCast(p.classes.items.len);
        try p.classes.append(.{ .negate = negate, .entries = entries.items });
        return n;
    }
};

fn setSplit(inst: *Inst, lazy: bool, first: u32, second: u32) void {
    if (lazy) {
        inst.x = second;
        inst.y = first;
    } else {
        inst.x = first;
        inst.y = second;
    }
}

/// Flatten the AST into instruction list. Quantified groups re-emit the
/// same save slots on every iteration, so the last iteration wins (JS).
fn emitNode(p: *Parser, n: *Node) PErr!void {
    switch (n.kind) {
        .empty => {},
        .char => try p.prog.append(.{ .op = .char, .ch = n.ch }),
        .any => try p.prog.append(.{ .op = .any }),
        .class => try p.prog.append(.{ .op = .class, .ci = n.class_idx }),
        .shorth => try p.prog.append(.{ .op = switch (n.ch) {
            0 => if (n.neg) .ndig else .dig,
            1 => if (n.neg) .nwrd else .wrd,
            2 => if (n.neg) .nspc else .spc,
            else => unreachable,
        } }),
        .bol => try p.prog.append(.{ .op = .bol }),
        .eol => try p.prog.append(.{ .op = .eol }),
        .wordb => try p.prog.append(.{ .op = .wordb }),
        .nwordb => try p.prog.append(.{ .op = .nwordb }),
        .group => {
            try p.prog.append(.{ .op = .save, .x = 2 * n.group_no });
            try emitNode(p, n.child.?);
            try p.prog.append(.{ .op = .save, .x = 2 * n.group_no + 1 });
        },
        .concat => {
            var c = n.head;
            while (c) |cc| : (c = cc.next) try emitNode(p, cc);
        },
        .alt => {
            var splits = std.ArrayList(u32).init(p.alloc);
            var jmps = std.ArrayList(u32).init(p.alloc);
            var c = n.head.?;
            while (c.next != null) {
                const sp: u32 = @intCast(p.prog.items.len);
                try p.prog.append(.{ .op = .split, .x = sp + 1, .y = 0 });
                try splits.append(sp);
                try emitNode(p, c);
                const jp: u32 = @intCast(p.prog.items.len);
                try p.prog.append(.{ .op = .jmp, .x = 0 });
                try jmps.append(jp);
                c = c.next.?;
            }
            try emitNode(p, c); // last alternative
            const end: u32 = @intCast(p.prog.items.len);
            for (splits.items, jmps.items) |sp, jp| {
                p.prog.items[sp].y = jp + 1; // next alternative starts after the jmp
                p.prog.items[jp].x = end;
            }
        },
        .star => {
            const sp: u32 = @intCast(p.prog.items.len);
            try p.prog.append(.{ .op = .split, .x = 0, .y = 0 });
            const body_start = p.prog.items.len;
            try emitNode(p, n.child.?);
            const body_len = p.prog.items.len - body_start;
            if (body_len == 0) {
                // Empty body would loop forever — a star of nothing is nothing.
                p.prog.shrinkRetainingCapacity(sp);
                return;
            }
            const after: u32 = @as(u32, @intCast(p.prog.items.len)) + 1;
            try p.prog.append(.{ .op = .jmp, .x = sp });
            setSplit(&p.prog.items[sp], n.lazy, sp + 1, after);
        },
        .plus => {
            const body_start: u32 = @intCast(p.prog.items.len);
            try emitNode(p, n.child.?);
            if (p.prog.items.len == body_start) return; // nothing to repeat
            const sp: u32 = @intCast(p.prog.items.len);
            try p.prog.append(.{ .op = .split, .x = 0, .y = 0 });
            setSplit(&p.prog.items[sp], n.lazy, body_start, sp + 1);
        },
        .quest => {
            const sp: u32 = @intCast(p.prog.items.len);
            try p.prog.append(.{ .op = .split, .x = 0, .y = 0 });
            try emitNode(p, n.child.?);
            const after: u32 = @intCast(p.prog.items.len);
            setSplit(&p.prog.items[sp], n.lazy, sp + 1, after);
        },
        .rangeq => {
            const child = n.child.?;
            if (n.open) {
                if (n.m == 0) {
                    const t = try p.newNode(.star);
                    t.lazy = n.lazy;
                    t.child = child;
                    try emitNode(p, t);
                } else {
                    // {m,}: m copies, the last one loopable (plus).
                    var k: u32 = 0;
                    while (k < n.m) : (k += 1) try emitNode(p, child);
                    const t = try p.newNode(.plus);
                    t.lazy = n.lazy;
                    t.child = child;
                    try emitNode(p, t);
                }
            } else if (!n.has_n) {
                var k: u32 = 0;
                while (k < n.m) : (k += 1) try emitNode(p, child); // {m} exact
            } else if (n.m == 0) {
                var k: u32 = 0;
                while (k < n.n) : (k += 1) { // {0,n}: n optionals
                    const t = try p.newNode(.quest);
                    t.lazy = n.lazy;
                    t.child = child;
                    try emitNode(p, t);
                }
            } else {
                var k: u32 = 0;
                while (k < n.m) : (k += 1) try emitNode(p, child);
                var j: u32 = n.m;
                while (j < n.n) : (j += 1) { // {m,n}: m copies then n-m optionals
                    const t = try p.newNode(.quest);
                    t.lazy = n.lazy;
                    t.child = child;
                    try emitNode(p, t);
                }
            }
        },
    }
}

const Compiled = union(enum) {
    prog: Prog,
    bad: []const u8, // syntax error message
};

/// Compile the pattern with the case and multiline modes baked in.
fn compile(alloc: std.mem.Allocator, pattern: []const u8, icase: bool, multiline: bool) error{OutOfMemory}!Compiled {
    var p = Parser{
        .pat = pattern,
        .alloc = alloc,
        .prog = std.ArrayList(Inst).init(alloc),
        .classes = std.ArrayList(Class).init(alloc),
    };
    const root = p.parseAlt() catch |e| return switch (e) {
        error.Syntax => Compiled{ .bad = p.err_msg orelse "invalid pattern" },
        error.OutOfMemory => return error.OutOfMemory,
    };
    if (p.i != pattern.len) {
        return Compiled{ .bad = "unbalanced ')'" };
    }
    emitNode(&p, root) catch |e| return switch (e) {
        error.Syntax => Compiled{ .bad = p.err_msg orelse "invalid pattern" },
        error.OutOfMemory => return error.OutOfMemory,
    };
    // Wrap the whole expression: save 0 ... save 1 ... match.
    try p.prog.insert(0, .{ .op = .save, .x = 0 });
    try p.prog.append(.{ .op = .save, .x = 1 });
    try p.prog.append(.{ .op = .match });
    return Compiled{ .prog = .{
        .insts = p.prog.items,
        .classes = p.classes.items,
        .ngroups = p.ngroups,
        .multiline = multiline,
        .icase = icase,
    } };
}

// ---- backtracking VM ----

const Thread = struct { pc: u32, sp: u32, undo_len: usize };
const UndoEntry = struct { slot: u32, old: ?u32 };

/// Anchored match at `start`. On success caps holds slot bounds:
/// caps[0]/caps[1] = whole match, caps[2g]/caps[2g+1] = group g (null when
/// the group did not participate). The undo log restores slots when a
/// thread backtracks past their saves.
fn matchAt(
    prog: Prog,
    input: []const u8,
    start: usize,
    caps: []?u32,
    stack: *std.ArrayList(Thread),
    undo: *std.ArrayList(UndoEntry),
) bool {
    stack.clearRetainingCapacity();
    undo.clearRetainingCapacity();
    @memset(caps, null);
    var pc: u32 = 0;
    var sp: u32 = @intCast(start);
    while (true) {
        const inst = prog.insts[pc];
        var alive = true;
        switch (inst.op) {
            .char => if (sp < input.len and byteEq(input[sp], inst.ch, prog.icase)) {
                sp += 1;
                pc += 1;
            } else {
                alive = false;
            },
            .any => if (sp < input.len and input[sp] != '\n') {
                sp += 1;
                pc += 1;
            } else {
                alive = false;
            },
            .class => if (sp < input.len and classMatches(prog.classes[inst.ci], input[sp], prog.icase)) {
                sp += 1;
                pc += 1;
            } else {
                alive = false;
            },
            .dig, .ndig, .wrd, .nwrd, .spc, .nspc => if (sp < input.len) {
                const b = input[sp];
                const hit = switch (inst.op) {
                    .dig => isDigit(b),
                    .ndig => !isDigit(b),
                    .wrd => isWordByte(b),
                    .nwrd => !isWordByte(b),
                    .spc => isSpace(b),
                    .nspc => !isSpace(b),
                    else => unreachable,
                };
                if (hit) {
                    sp += 1;
                    pc += 1;
                } else {
                    alive = false;
                }
            } else {
                alive = false;
            },
            .split => {
                stack.append(.{ .pc = inst.y, .sp = sp, .undo_len = undo.items.len }) catch return false;
                pc = inst.x;
            },
            .jmp => pc = inst.x,
            .save => {
                if (inst.x < caps.len) {
                    undo.append(.{ .slot = inst.x, .old = caps[inst.x] }) catch return false;
                    caps[inst.x] = sp;
                }
                pc += 1;
            },
            .bol => if (sp == 0 or (prog.multiline and input[sp - 1] == '\n')) {
                pc += 1;
            } else {
                alive = false;
            },
            .eol => if (sp == input.len or (prog.multiline and input[sp] == '\n')) {
                pc += 1;
            } else {
                alive = false;
            },
            .wordb => if (atWordBoundary(input, sp)) {
                pc += 1;
            } else {
                alive = false;
            },
            .nwordb => if (!atWordBoundary(input, sp)) {
                pc += 1;
            } else {
                alive = false;
            },
            .match => return true,
        }
        if (!alive) {
            const f = stack.pop() orelse return false;
            while (undo.items.len > f.undo_len) {
                const e = undo.pop().?;
                caps[e.slot] = e.old;
            }
            pc = f.pc;
            sp = f.sp;
        }
    }
}

// ---- find & replace ----

/// Escape regex metacharacters so a literal find string matches verbatim.
fn escapePattern(alloc: std.mem.Allocator, s: []const u8) error{OutOfMemory}![]const u8 {
    var out = std.ArrayList(u8).init(alloc);
    for (s) |c| {
        switch (c) {
            '.', '*', '+', '?', '(', ')', '[', ']', '{', '}', '|', '^', '$', '\\' => try out.append('\\'),
            else => {},
        }
        try out.append(c);
    }
    return out.items;
}

/// Group g's text from capture slots; "" when it did not participate.
fn groupText(caps: []const ?u32, input: []const u8, g: usize) []const u8 {
    const so = caps[2 * g] orelse return "";
    const eo = caps[2 * g + 1] orelse return "";
    if (so > eo or eo > input.len) return "";
    return input[so..eo];
}

/// Apply JS String.replace $-substitution for one match.
///   "$$" -> "$";  "$&" -> whole match;  "$1".."$99" -> capture group N
///   (literal "$<digits>" when N is out of range, matching JS).
fn expandReplacement(alloc: std.mem.Allocator, tpl: []const u8, input: []const u8, caps: []const ?u32) error{OutOfMemory}![]const u8 {
    const num_groups = caps.len / 2 - 1;
    var out = std.ArrayList(u8).init(alloc);
    var i: usize = 0;
    while (i < tpl.len) {
        const c = tpl[i];
        if (c != '$') {
            try out.append(c);
            i += 1;
            continue;
        }
        const nxt: u8 = if (i + 1 < tpl.len) tpl[i + 1] else 0;
        if (nxt == '$') {
            try out.append('$');
            i += 2;
        } else if (nxt == '&') {
            try out.appendSlice(groupText(caps, input, 0));
            i += 2;
        } else if (isDigit(nxt)) {
            const d1: usize = nxt - '0';
            // Greedily try a second digit ($nn), matching JS.
            if (i + 2 < tpl.len and isDigit(tpl[i + 2])) {
                const d2 = d1 * 10 + (tpl[i + 2] - '0');
                if (d2 >= 1 and d2 <= num_groups) {
                    try out.appendSlice(groupText(caps, input, d2));
                    i += 3;
                    continue;
                }
            }
            if (d1 >= 1 and d1 <= num_groups) {
                try out.appendSlice(groupText(caps, input, d1));
                i += 2;
            } else {
                try out.append('$');
                try out.append(nxt);
                i += 2;
            }
        } else {
            try out.append('$');
            i += 1;
        }
    }
    return out.items;
}

/// Replace occurrences of `find` with `replacement`. Never errors on
/// pattern syntax (that lands in `.err`); only allocation can fail. All
/// returned memory belongs to `alloc` (an arena in the demo below).
pub fn findReplace(
    alloc: std.mem.Allocator,
    input: []const u8,
    find: []const u8,
    replacement: []const u8,
    o: Options,
) error{OutOfMemory}!FindReplaceResult {
    if (find.len == 0) return .{ .result = input, .matches = 0 }; // empty find is a no-op

    var pattern: []const u8 = find;
    if (!o.is_regex) {
        pattern = try escapePattern(alloc, find);
    }
    if (o.whole_word) {
        var wrapped = std.ArrayList(u8).init(alloc);
        try wrapped.ensureTotalCapacity(pattern.len + 4);
        try wrapped.appendSlice("\\b");
        try wrapped.appendSlice(pattern);
        try wrapped.appendSlice("\\b");
        pattern = wrapped.items;
    }

    // Multiline applies only to regex finds, mirroring the lib.
    const compiled = try compile(alloc, pattern, !o.case_sensitive, o.is_regex and o.multiline);
    const prog = switch (compiled) {
        .prog => |pr| pr,
        .bad => |msg| return .{ .result = input, .matches = 0, .err = msg },
    };

    const caps = try alloc.alloc(?u32, 2 * (prog.ngroups + 1));
    var stack = std.ArrayList(Thread).init(alloc);
    var undo = std.ArrayList(UndoEntry).init(alloc);

    var out = std.ArrayList(u8).init(alloc);
    var last: usize = 0;
    var pos: usize = 0;
    var matches: usize = 0;
    while (pos <= input.len) {
        // Leftmost match: anchored attempts from each position in turn.
        var start = pos;
        var found = false;
        while (start <= input.len) : (start += 1) {
            if (matchAt(prog, input, start, caps, &stack, &undo)) {
                found = true;
                break;
            }
        }
        if (!found) break;
        const so: usize = caps[0] orelse start;
        const eo: usize = caps[1] orelse start;
        try out.appendSlice(input[last..so]);
        try out.appendSlice(try expandReplacement(alloc, replacement, input, caps));
        matches += 1;
        last = eo;
        if (!o.global) break;
        if (eo == so) { // empty match: copy one byte and step, like JS
            if (eo < input.len) {
                try out.append(input[eo]);
                last = eo + 1;
            }
            pos = last;
        } else {
            pos = eo;
        }
    }
    try out.appendSlice(input[last..]);

    if (matches != 0 and !o.global) {
        matches = 1 + prog.ngroups; // JS String.match length quirk
    }
    return .{ .result = out.items, .matches = matches };
}

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    const r = try findReplace(
        arena.allocator(),
        "Hello World world",
        "world",
        "Universe",
        .{ .case_sensitive = false },
    );
    if (r.err) |e| {
        std.debug.print("error: {s}\n", .{e});
    } else {
        std.debug.print("{s}  ({d} matches)\n", .{ r.result, r.matches });
    }
}