//! 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 fn compile(pat: []const u8) error{Bad}!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;
                } else if (in_class) {
                    in_class = c != ']';
                } else if (c == '[') {
                    in_class = true;
                } else if (c == '.' and spans) {
                    piece = "[^\\n]";
                }
                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;
        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");
    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);
}