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.
pub const Regex = struct {
    re: mvzr.Regex,
    /// 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_anchor = "bad regular expression: in a pattern with \\n, ^ can only come first and $ only just before a \\n";

    /// `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.
    pub fn compile(pat: []const u8) error{ Bad, Anchor }!Regex {
        if (pat.len == 0) return error.Bad;
        var buf: [256]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.Bad;
                @memcpy(buf[len..][0..piece.len], piece);
                len += piece.len;
            }
        }
        return .{
            .re = mvzr.compile(buf[0..len]) orelse return error.Bad,
            .spans = spans,
            .bol = pat[0] == '^',
        };
    }

    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) {
            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 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));
}