path: root/src/regexp.zig

//! How pardes runs a regular expression over text: mvzr's, searched the way
//! sam searches (editors/acme/regx.c). `addr` (src/ninep/addr.zig) and
//! normal mode's `s` and `S` (src/normal.zig) both call it.
const std = @import("std");
const builtin = @import("builtin");
const mvzr = @import("mvzr");

/// A compiled pattern and how to run it.
///
/// sam searches the text as lines: `^` and `$` at any line's start and end,
/// and `.` never a newline. mvzr has no such mode (its `^` and `$` are the
/// haystack's ends, its `.` any byte), so each line is its own haystack, and
/// a pattern that names a newline (`\n`) runs over the whole text with its
/// `.`s made `[^\n]`.
///
/// mvzr backtracks, and has no bound on its work of its own: `a?` twenty
/// times then twenty `a`s is 2^20 steps from each start, `a*a*a*a*x` over a line of a
/// hundred `a`s a second. The search runs with the editor's turn, so it must
/// come back: build.zig patches a step budget into mvzr's matcher, and a
/// search that spends `budget` steps (about 300 ms here) stops with
/// `TooSlow`, found nothing rather than something wrong.
///
/// ponytail: mvzr takes the first alternative that matches, not sam's
/// longest (`gam|gamma` finds `gam`); a search from the middle of a line lets
/// `^` match there unless the pattern starts with it; across lines, `^`, `$`
/// and `[^...]` keep mvzr's meaning; and a quadratic pattern over a long
/// enough line (`\s*(\w+)\s*=` over 20 KB of letters) runs out of budget. A
/// regex engine of sam's own would lift these; the user chose not to have
/// one.
/// mvzr's own `Regex` holds 64 operations, some 64 pattern characters; a
/// search pattern is often longer. Past these a pattern is refused naming
/// the limit (`e_long`).
pub const max_ops = 512;
const Compiled = mvzr.SizedRegex(max_ops, 64);

pub const Regex = struct {
    re: Compiled,
    /// The literal every match starts with, when the pattern opens with one
    /// (`line 049`, `foo` in `foo.*bar`): a search goes straight to where it
    /// occurs rather than trying mvzr at every line.
    lit: [32]u8 = undefined,
    lit_len: u8 = 0,
    /// The pattern names a newline: it runs over the whole text.
    spans: bool,
    /// The pattern starts with `^`: a search begun mid-line skips the line.
    bol: bool,
    /// mvzr steps left to every search with this compiled pattern together,
    /// so that addr's backward scan and s/S's many calls share one bound.
    steps: u64 = budget,

    /// Timed on this machine's ReleaseSafe build: 10M steps of the worst
    /// patterns take 45-80 ms, and a Debug build is ten times slower.
    pub const budget: u64 = if (builtin.mode == .Debug) 4_000_000 else 32_000_000;

    pub const e_long = std.fmt.comptimePrint("bad regular expression: longer than mvzr's {d} operations (about {d} pattern characters)", .{ max_ops, max_ops });
    pub const e_anchor = "bad regular expression: in a pattern with \\n, ^ can only come first and $ only just before a \\n";
    pub const e_wide = std.fmt.comptimePrint("bad regular expression: a range of runes wider than {d} in [...] is not supported", .{max_range});
    pub const e_negated = "bad regular expression: a [^...] with non-ASCII runes is not supported (mvzr's classes hold bytes)";

    /// The most runes a non-ASCII range in a class is spelled out as.
    pub const max_range = 256;

    /// `Anchor`: a pattern that names a newline has `^` other than first,
    /// or `$` other than just before a `\n`, which mvzr would read as the
    /// ends of the whole text and so never match where sam would.
    /// The plain characters a pattern opens with, each of which every match
    /// must start with: up to the first metacharacter, less the last one
    /// when a quantifier makes it optional or repeated.
    fn literalPrefix(pat: []const u8, out: *[32]u8) u8 {
        // ponytail: any `|` and there is none (a match may start with
        // another branch); a top-level-only check would keep `a(b|c)`'s.
        if (std.mem.indexOfScalar(u8, pat, '|') != null) return 0;
        var n: usize = 0;
        while (n < pat.len and n < out.len) : (n += 1) {
            if (std.mem.indexOfScalar(u8, "\\^$.[]()|*+?{}", pat[n]) != null) break;
            out[n] = pat[n];
        }
        if (n < pat.len and std.mem.indexOfScalar(u8, "*?{", pat[n]) != null) n -|= 1;
        return @intCast(n);
    }

    pub const Error = error{ Bad, Anchor, TooLong, WideRange, NegatedRunes };

    pub fn compile(pat: []const u8) Error!Regex {
        if (pat.len == 0) return error.Bad;
        // mvzr's classes hold bytes: `[éa-z]` is written `(é|[a-z])` for it.
        // The limits apply to the pattern as rewritten.
        var runes: [5 * max_ops + 2]u8 = undefined;
        if (try runeClasses(pat, &runes)) |whole| return compile(whole);
        // mvzr takes `^` only at its pattern's start, so `^def|^ ` (a `^`
        // after a `|`) is written `^(def| )` for it: the same lines. A mix,
        // `^a|b`, has no such spelling and is refused rather than wrong.
        var joined: [5 * max_ops + 2]u8 = undefined;
        if (try anchoredAlternation(pat, &joined)) |whole| return compile(whole);
        // `.` may become `[^\n]`: five bytes for one.
        var buf: [5 * max_ops]u8 = undefined;
        var len: usize = 0;
        var spans = false;
        // Twice over the pattern: the first pass learns whether it names a
        // newline, which the second needs to rewrite its `.`s.
        for ([2]bool{ false, true }) |emit| {
            var i: usize = 0;
            // mvzr ends a class at its first unescaped `]`, even one that
            // comes first (`[]a]` is an empty class, then `a]`); a `]` member
            // is written `\]`.
            var in_class = false;
            while (i < pat.len) : (i += 1) {
                const c = pat[i];
                var piece: []const u8 = pat[i .. i + 1];
                if (c == '\\') {
                    if (i + 1 >= pat.len) return error.Bad;
                    i += 1;
                    piece = pat[i - 1 .. i + 1];
                    if (pat[i] == 'n') spans = true;
                    // mvzr slices two hex digits after `\x` without looking,
                    // so a short one panics it: refuse it here.
                    if (pat[i] == 'x' and (i + 2 >= pat.len or
                        !std.ascii.isHex(pat[i + 1]) or !std.ascii.isHex(pat[i + 2]))) return error.Bad;
                } else if (in_class) {
                    in_class = c != ']';
                } else if (c == '[') {
                    in_class = true;
                } else if (c == '.' and spans) {
                    piece = "[^\\n]";
                } else if (spans and c == '^' and i != 0) {
                    return error.Anchor;
                } else if (spans and c == '$') {
                    // `x$\n` is `x\n`; any other `$` would be the text's end.
                    if (std.mem.startsWith(u8, pat[i + 1 ..], "\\n")) continue;
                    return error.Anchor;
                }
                if (!emit) continue;
                if (len + piece.len > buf.len) return error.TooLong;
                @memcpy(buf[len..][0..piece.len], piece);
                len += piece.len;
            }
        }
        var lit: [32]u8 = undefined;
        const lit_len = if (spans) 0 else literalPrefix(pat, &lit);
        return .{
            .lit = lit,
            .lit_len = lit_len,
            .re = Compiled.compile(buf[0..len]) orelse {
                // Too long, or malformed: told apart by trying it with room.
                if (mvzr.SizedRegex(4 * max_ops, 256).compile(buf[0..len]) != null) return error.TooLong;
                return error.Bad;
            },
            .spans = spans,
            .bol = pat[0] == '^',
        };
    }

    /// `pat` with each class that holds a non-ASCII rune written as an
    /// alternation of its runes and a class of the rest (`[éa-z]` is
    /// `(é|[a-z])`), a range spelled out rune by rune; null when no class
    /// holds one.
    fn runeClasses(pat: []const u8, out: *[5 * max_ops + 2]u8) Error!?[]const u8 {
        var w = std.Io.Writer.fixed(out);
        var any = false;
        var i: usize = 0;
        while (i < pat.len) : (i += 1) {
            const c = pat[i];
            if (c == '\\') {
                w.writeAll(pat[i..@min(i + 2, pat.len)]) catch return error.TooLong;
                i += 1;
                continue;
            }
            if (c != '[') {
                w.writeByte(c) catch return error.TooLong;
                continue;
            }
            // The class's end, as mvzr finds it: the first unescaped `]`.
            var end = i + 1;
            while (end < pat.len and pat[end] != ']') : (end += 1) {
                if (pat[end] == '\\') end += 1;
            }
            if (end >= pat.len) return error.Bad;
            const body = pat[i + 1 .. end];
            if (for (body) |b| {
                if (b >= 0x80) break false;
            } else true) {
                w.writeAll(pat[i .. end + 1]) catch return error.TooLong;
                i = end;
                continue;
            }
            if (body[0] == '^') return error.NegatedRunes;
            any = true;
            try runeClass(body, &w);
            i = end;
        }
        return if (any) w.buffered() else null;
    }

    fn runeClass(body: []const u8, w: *std.Io.Writer) Error!void {
        var ascii: [5 * max_ops]u8 = undefined;
        var n: usize = 0;
        w.writeByte('(') catch return error.TooLong;
        var alts: usize = 0;
        var j: usize = 0;
        while (j < body.len) {
            if (body[j] == '\\') {
                const len: usize = if (j + 1 < body.len and body[j + 1] == 'x') 4 else 2;
                if (j + len > body.len) return error.Bad;
                // An escape at one end of a range whose other end is a rune.
                if (j + len + 1 < body.len and body[j + len] == '-' and body[j + len + 1] >= 0x80) return error.Bad;
                if (n + len > ascii.len) return error.TooLong;
                @memcpy(ascii[n..][0..len], body[j..][0..len]);
                n += len;
                j += len;
                continue;
            }
            const lo, const lo_len = try rune(body[j..]);
            j += lo_len;
            var hi = lo;
            if (j + 1 < body.len and body[j] == '-') {
                if (body[j + 1] == '\\' and lo >= 0x80) return error.Bad;
                if (body[j + 1] != '\\') {
                    hi, const hi_len = try rune(body[j + 1 ..]);
                    j += 1 + hi_len;
                }
            }
            if (hi < lo) return error.Bad;
            if (hi - lo + 1 > max_range) return error.WideRange;
            // Runes that differ only in their last byte go as one
            // alternative, `\xc3[\xa0-\xbf]` for `[à-ÿ]`: 256 runes one a
            // time would pass `max_ops`.
            var run: [4]u8 = undefined;
            var run_len: usize = 0;
            var run_hi: u8 = 0;
            var cp = lo;
            while (cp <= hi + 1) : (cp += 1) {
                var enc: [4]u8 = undefined;
                const len = if (cp > hi) 0 else std.unicode.utf8Encode(cp, &enc) catch continue; // a surrogate
                if (run_len > 0 and (len != run_len or enc[len - 1] != run_hi + 1 or
                    !std.mem.eql(u8, enc[0 .. len - 1], run[0 .. len - 1])))
                {
                    if (alts > 0) w.writeByte('|') catch return error.TooLong;
                    w.writeAll(run[0 .. run_len - 1]) catch return error.TooLong;
                    if (run_hi == run[run_len - 1])
                        w.writeByte(run_hi) catch return error.TooLong
                    else
                        w.print("[\\x{x:0>2}-\\x{x:0>2}]", .{ run[run_len - 1], run_hi }) catch return error.TooLong;
                    alts += 1;
                    run_len = 0;
                }
                if (cp > hi) break;
                if (cp < 0x80) {
                    // `\xHH` rather than the byte: `]`, `^`, `-` and `\`
                    // would otherwise mean something in the class.
                    if (n + 4 > ascii.len) return error.TooLong;
                    _ = std.fmt.bufPrint(ascii[n..][0..4], "\\x{x:0>2}", .{cp}) catch unreachable;
                    n += 4;
                    continue;
                }
                if (run_len == 0) {
                    run = enc;
                    run_len = len;
                }
                run_hi = enc[len - 1];
            }
        }
        if (n > 0) w.print("|[{s}]", .{ascii[0..n]}) catch return error.TooLong;
        w.writeByte(')') catch return error.TooLong;
    }

    /// The rune `s` opens with and its length in bytes.
    fn rune(s: []const u8) error{Bad}!struct { u21, usize } {
        const len = std.unicode.utf8ByteSequenceLength(s[0]) catch return error.Bad;
        if (len > s.len) return error.Bad;
        return .{ std.unicode.utf8Decode(s[0..len]) catch return error.Bad, len };
    }

    /// `^a|^b` as `^(a|b)` in `out`, when the pattern is an alternation at
    /// its top level and every branch starts with `^`; null when it is not
    /// one, or no branch does.
    fn anchoredAlternation(pat: []const u8, out: *[5 * max_ops + 2]u8) error{Bad}!?[]const u8 {
        var bars: [16]usize = undefined;
        var n: usize = 0;
        var depth: usize = 0;
        var in_class = false;
        var i: usize = 0;
        while (i < pat.len) : (i += 1) {
            const c = pat[i];
            if (c == '\\') {
                i += 1;
            } else if (in_class) {
                in_class = c != ']';
            } else if (c == '[') {
                in_class = true;
            } else if (c == '(') {
                depth += 1;
            } else if (c == ')') {
                depth -|= 1;
            } else if (c == '|' and depth == 0) {
                if (n == bars.len) return error.Bad;
                bars[n] = i;
                n += 1;
            }
        }
        if (n == 0) return null;
        var anchored: usize = 0;
        var from: usize = 0;
        for (0..n + 1) |k| {
            const to = if (k < n) bars[k] else pat.len;
            anchored += @intFromBool(to > from and pat[from] == '^');
            from = to + 1;
        }
        if (anchored == 0) return null;
        if (anchored != n + 1) return error.Bad;
        var w = std.Io.Writer.fixed(out);
        w.writeAll("^(") catch return error.Bad;
        from = 0;
        for (0..n + 1) |k| {
            const to = if (k < n) bars[k] else pat.len;
            if (k > 0) w.writeByte('|') catch return error.Bad;
            w.writeAll(pat[from + 1 .. to]) catch return error.Bad;
            from = to + 1;
        }
        w.writeByte(')') catch return error.Bad;
        return w.buffered();
    }

    pub const Match = struct { start: usize, end: usize };

    /// The first match that starts in `from..=last` and ends by `hi`, as
    /// offsets into `text`. The text before `from` still says where lines
    /// begin.
    pub fn find(rx: *Regex, text: []const u8, from: usize, last: usize, hi: usize) error{TooSlow}!?Match {
        mvzr.steps_left = rx.steps;
        mvzr.exhausted = false;
        defer rx.steps = mvzr.steps_left;
        // A `^` pattern that spans lines: mvzr's `^` is its haystack's start,
        // so each line start from `from` on is tried as one.
        // ponytail: a search per line start, each to `hi`; the step budget
        // bounds it.
        if (rx.spans and rx.bol) {
            var s = if (from == 0 or text[from - 1] == '\n') from else (std.mem.indexOfScalarPos(u8, text[0..hi], from, '\n') orelse return null) + 1;
            while (s <= last and s <= hi) {
                const hit = rx.re.match(text[s..hi]);
                if (mvzr.exhausted) return error.TooSlow;
                if (hit) |m| if (m.start == 0) return .{ .start = s, .end = s + m.end };
                s = (std.mem.indexOfScalarPos(u8, text[0..hi], s, '\n') orelse return null) + 1;
            }
            return null;
        }
        var start: usize = if (rx.spans) 0 else if (std.mem.lastIndexOfScalar(u8, text[0..from], '\n')) |nl| nl + 1 else 0;
        var at = from - start;
        // `^` cannot match in the middle of a line.
        if (!rx.spans and rx.bol and at > 0) {
            start = (std.mem.indexOfScalarPos(u8, text[0..hi], from, '\n') orelse return null) + 1;
            at = 0;
        }
        while (start <= hi and start <= last) {
            // A pattern that opens with a literal matches only where it
            // occurs: on to the line where it next does.
            if (rx.lit_len > 0 and !rx.spans) {
                const q = std.mem.indexOfPos(u8, text[0..hi], start + at, rx.lit[0..rx.lit_len]) orelse return null;
                if (q > last) return null;
                if (q > start + at) {
                    const line_start = if (std.mem.lastIndexOfScalar(u8, text[0..q], '\n')) |nl| nl + 1 else 0;
                    if (line_start > start) {
                        start = line_start;
                        at = q - line_start;
                    } else at = q - start;
                    if (rx.bol and at > 0) {
                        start = (std.mem.indexOfScalarPos(u8, text[0..hi], q, '\n') orelse return null) + 1;
                        at = 0;
                        continue;
                    }
                }
            }
            const end = if (rx.spans) hi else std.mem.indexOfScalarPos(u8, text[0..hi], start, '\n') orelse hi;
            const line = text[start..end];
            // matchPos finds nothing at a haystack's very end, where `$` or
            // an empty match still can.
            const hit: ?[2]usize = if (at < line.len)
                (if (rx.re.matchPos(at, line)) |m| .{ m.start, m.end } else null)
            else if (at == line.len and rx.re.isMatch(line[at..])) .{ at, at } else null;
            if (mvzr.exhausted) return error.TooSlow;
            if (hit) |h| {
                if (start + h[0] > last) return null;
                return .{ .start = start + h[0], .end = start + h[1] };
            }
            if (end == hi) return null;
            start = end + 1;
            at = 0;
        }
        return null;
    }
};

test "lines are haystacks: ^ and $ at each line, . never a newline, \\n spans lines" {
    const text = "alpha beta\nbeta gamma\ngamma\n";
    const Case = struct { pat: []const u8, from: usize, start: usize, end: usize };
    for ([_]Case{
        .{ .pat = "^beta", .from = 0, .start = 11, .end = 15 },
        .{ .pat = "beta$", .from = 0, .start = 6, .end = 10 },
        .{ .pat = "a.*", .from = 0, .start = 0, .end = 10 },
        .{ .pat = "a\\nbeta", .from = 0, .start = 9, .end = 15 },
        .{ .pat = "t.\\nbeta", .from = 0, .start = 8, .end = 15 },
        .{ .pat = "^", .from = 1, .start = 11, .end = 11 },
    }) |c| {
        var rx = try Regex.compile(c.pat);
        const m = (try rx.find(text, c.from, text.len, text.len)).?;
        try std.testing.expectEqual(c.start, m.start);
        try std.testing.expectEqual(c.end, m.end);
    }
    _ = try Regex.compile("a.*a\\nq");
    // `^` at every line start and `$` before a newline, when a pattern
    // spans lines; anywhere else they are refused, never silently wrong.
    const defs = "x = 1\ndef a\n\ndef b\n";
    var def = try Regex.compile("^def .*\\n");
    const d = (try def.find(defs, 0, defs.len, defs.len)).?;
    try std.testing.expectEqual(@as(usize, 6), d.start);
    try std.testing.expectEqual(@as(usize, 12), d.end);
    try std.testing.expectEqual(@as(usize, 13), (try def.find(defs, 7, defs.len, defs.len)).?.start);
    var blank = try Regex.compile("^\\n");
    try std.testing.expectEqual(@as(usize, 12), (try blank.find(defs, 0, defs.len, defs.len)).?.start);
    var dollar = try Regex.compile("1$\\n");
    try std.testing.expectEqual(@as(usize, 4), (try dollar.find(defs, 0, defs.len, defs.len)).?.start);
    try std.testing.expectError(error.Anchor, Regex.compile("(^|\\n)def"));
    try std.testing.expectError(error.Anchor, Regex.compile("a$\\nb$"));
    var none = try Regex.compile("zzz");
    try std.testing.expect(try none.find(text, 0, text.len, text.len) == null);
    try std.testing.expectError(error.Bad, Regex.compile(""));
    try std.testing.expectError(error.Bad, Regex.compile("a\\"));
}

test "a pattern opening with a literal finds what a search from each line finds" {
    const text = "alpha beta\nbeta gamma\ngamma alpha\nfoo line 049999 x\n";
    for ([_][]const u8{ "beta", "gam+a", "line 049999", "alph?a", "a.*a", "^gamma", "o+", "h$|zz", "beta|x" }) |pat| {
        var fast = try Regex.compile(pat);
        var slow = try Regex.compile(pat);
        slow.lit_len = 0;
        var from: usize = 0;
        while (from < text.len) : (from += 1) {
            const a = try fast.find(text, from, text.len, text.len);
            const b = try slow.find(text, from, text.len, text.len);
            try std.testing.expectEqual(b == null, a == null);
            if (a) |m| try std.testing.expectEqual(b.?.start, m.start);
        }
    }
}

test "a class with non-ASCII runes matches those runes: [éa-z], a range of them, and refuses a wide range or [^é]" {
    const text = "1 é 2 b 3 ü 4 ñ\n";
    var mixed = try Regex.compile("[éa-z]+");
    try std.testing.expectEqual(@as(usize, 2), (try mixed.find(text, 0, text.len, text.len)).?.start);
    const m = (try mixed.find(text, 5, text.len, text.len)).?;
    try std.testing.expectEqualStrings("b", text[m.start..m.end]);
    var range = try Regex.compile("3 [à-ÿ]");
    const r = (try range.find(text, 0, text.len, text.len)).?;
    try std.testing.expectEqualStrings("3 ü", text[r.start..r.end]);
    // An ASCII member that means something in a class stays a member.
    var odd = try Regex.compile("[ñ\\]^-]");
    try std.testing.expectEqual(@as(usize, 16), (try odd.find(text, 0, text.len, text.len)).?.start);
    var none = try Regex.compile("[ö]");
    try std.testing.expect(try none.find(text, 0, text.len, text.len) == null);
    try std.testing.expectError(error.WideRange, Regex.compile("[ā-ӿ]"));
    try std.testing.expectError(error.NegatedRunes, Regex.compile("[^é]"));
    try std.testing.expectError(error.Bad, Regex.compile("[é"));
    try std.testing.expectError(error.Bad, Regex.compile("[ÿ-à]"));
    // A full 256-rune range fits the limit as rewritten.
    var wide = try Regex.compile("x[Ā-ǿ]");
    try std.testing.expectEqual(@as(usize, 2), (try wide.find("ǿxǿ", 0, 5, 5)).?.start);
    var kana = try Regex.compile("[ぁ-ゟ]"); // 3 bytes, across a last-byte wrap
    try std.testing.expectEqual(@as(usize, 1), (try kana.find("aゞ", 0, 4, 4)).?.start);
    try std.testing.expectError(error.WideRange, Regex.compile("[Ā-Ȁ]"));
}

test "a pattern past 64 characters compiles, and one past the limit says so" {
    var long = try Regex.compile("a" ** 200);
    const text = "x" ++ "a" ** 200 ++ "\n";
    try std.testing.expectEqual(@as(usize, 1), (try long.find(text, 0, text.len, text.len)).?.start);
    try std.testing.expectError(error.TooLong, Regex.compile("a" ** (max_ops + 8)));
    try std.testing.expectError(error.Bad, Regex.compile("a[b"));
}

test "a ^ after | anchors that branch: ^def|^  finds a line that starts either way, and a mix is refused" {
    const text = "x def\n a\ndef b\n";
    var both = try Regex.compile("^def|^ ");
    try std.testing.expectEqual(@as(usize, 6), (try both.find(text, 0, text.len, text.len)).?.start);
    try std.testing.expectEqual(@as(usize, 9), (try both.find(text, 7, text.len, text.len)).?.start);
    try std.testing.expectError(error.Bad, Regex.compile("^def|x"));
    var plain = try Regex.compile("a|b");
    try std.testing.expectEqual(@as(usize, 7), (try plain.find(text, 0, text.len, text.len)).?.start);
}

test "a quoted backslash before n is no newline, and a class ends where mvzr ends it" {
    // `\\n` is a backslash then an n: the pattern stays on one line, so its
    // `.` is not made [^\n] and does match within the line.
    var slash = try Regex.compile("a\\\\n.");
    try std.testing.expect(!slash.spans);
    try std.testing.expectEqual(@as(usize, 0), (try slash.find("a\\nX", 0, 4, 4)).?.start);
    // `[\]x]` is a class of `]` and `x`: the escaped `]` does not end it,
    // so the `*` after it is a repeat and the `.` a newline's rewrite.
    var class = try Regex.compile("[\\]x]*y.\\n");
    try std.testing.expect(class.spans);
    try std.testing.expectEqual(@as(usize, 1), (try class.find("-]x]y!\nz", 0, 8, 8)).?.start);
    try std.testing.expect(try class.find("-]x]y\n\n", 0, 7, 7) == null);
    // mvzr reads `[]x]` as an empty class then `x]`, which nothing matches.
    var empty = try Regex.compile("[]x]");
    try std.testing.expect(try empty.find("x]", 0, 2, 2) == null);
}

test "a search that would backtrack without end runs out of budget, promptly" {
    var line: [20000]u8 = @splat('a');
    for ([_][]const u8{ "(a|ab)*c", "a*a*a*a*a*x", ".*.*.*x" }) |pat| {
        var rx = try Regex.compile(pat);
        try std.testing.expectError(error.TooSlow, rx.find(&line, 0, line.len, line.len));
    }
    // As long a chain as mvzr compiles, over runs one `a` short of it: 2^20
    // steps from every start.
    for (0..line.len / 20) |i| line[i * 20 + 19] = 'b';
    var chain = try Regex.compile("a?" ** 20 ++ "a" ** 20);
    try std.testing.expectError(error.TooSlow, chain.find(&line, 0, line.len, line.len));
}

test "the match is the leftmost, however long the line" {
    // A window cut into the identifier would find `x... =` from its middle.
    const text = "let " ++ "x" ** 100 ++ " = 1";
    var assign = try Regex.compile("\\s*(\\w+)\\s*=");
    const m = (try assign.find(text, 0, text.len, text.len)).?;
    try std.testing.expectEqual(@as(usize, 3), m.start);
    try std.testing.expectEqual(@as(usize, 106), m.end);
    // Repeats are not counted or capped.
    var five = try Regex.compile("a*b*c*d*e*f");
    const f = (try five.find("xxaabbf", 0, 7, 7)).?;
    try std.testing.expectEqual(@as(usize, 2), f.start);
    try std.testing.expectEqual(@as(usize, 7), f.end);
}

test "a \\x without two hex digits is refused, not handed to mvzr to panic on" {
    for ([_][]const u8{ "\\x", "a\\x1", "\\x1b[\\x", "[\\x]", "\\xg1" }) |pat|
        try std.testing.expectError(error.Bad, Regex.compile(pat));
    var rx = try Regex.compile("\\x41");
    try std.testing.expectEqual(@as(usize, 1), (try rx.find("xA", 0, 1, 2)).?.start);
}

test "a repeat inside a group gives back to what follows the group" {
    const Case = struct { pat: []const u8, text: []const u8, start: usize, end: usize };
    for ([_]Case{
        .{ .pat = "a+ab", .text = "aab", .start = 0, .end = 3 },
        .{ .pat = "(a+)ab", .text = "aab", .start = 0, .end = 3 },
        .{ .pat = "(a*)ab", .text = "aab", .start = 0, .end = 3 },
        .{ .pat = "(.+)_area", .text = "the_total_area x", .start = 0, .end = 14 },
        .{ .pat = "([a-z_]+)_area", .text = "the_total_area x", .start = 0, .end = 14 },
        .{ .pat = "\\w+_area", .text = "the_total_area x", .start = 0, .end = 14 },
        .{ .pat = "(\\w)+_area", .text = "the_total_area x", .start = 0, .end = 14 },
        .{ .pat = "([a-z]+)_area", .text = "the_total_area x", .start = 4, .end = 14 },
        .{ .pat = "x(ab|a)bc", .text = "xabc", .start = 0, .end = 4 },
    }) |c| {
        var rx = try Regex.compile(c.pat);
        const m = (try rx.find(c.text, 0, c.text.len, c.text.len)) orelse {
            std.debug.print("no match for {s}\n", .{c.pat});
            return error.NoMatch;
        };
        try std.testing.expectEqual(c.start, m.start);
        try std.testing.expectEqual(c.end, m.end);
    }
}

test "`$` may end any alternative, not only the last" {
    const Case = struct { pat: []const u8, text: []const u8, start: usize, end: usize };
    for ([_]Case{
        .{ .pat = "h$|zz", .text = "xh", .start = 1, .end = 2 },
        .{ .pat = "zz|h$", .text = "xh", .start = 1, .end = 2 },
        .{ .pat = "h$|zz", .text = "hx zz", .start = 3, .end = 5 },
        .{ .pat = "(h$|zz)", .text = "xh", .start = 1, .end = 2 },
    }) |c| {
        var rx = try Regex.compile(c.pat);
        const m = (try rx.find(c.text, 0, c.text.len, c.text.len)).?;
        try std.testing.expectEqual(c.start, m.start);
        try std.testing.expectEqual(c.end, m.end);
    }
    var only = try Regex.compile("h$|zz");
    try std.testing.expectEqual(null, try only.find("hx", 0, 2, 2));
}