//! 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 mvzr = @import("mvzr");
const hosted = @import("pardes.zig").hosted;

/// 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: `a*a*a*a*x` over a line of
/// a hundred `a`s takes a second, and each repeat multiplies the cost by the
/// haystack's length. The search runs with the editor's turn, so it must
/// come back: a pattern with more than four repeats (`*`, `+`, `{}`) is
/// refused, the more repeats the shorter the stretch of a line one mvzr
/// call is given (a line longer than that is searched in overlapping
/// windows), and a search that has run for 300 ms stops with `TooSlow`.
///
/// 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; in a windowed line a match longer than
/// half a window may be missed or `^` match at a window's start. 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,
    /// The most bytes one mvzr call searches.
    window: usize,
    /// When searches with this pattern give up, in milliseconds.
    deadline: i64,

    pub const Error = error{ Bad, TooCostly };

    pub fn compile(pat: []const u8) Error!Regex {
        if (pat.len == 0) return error.Bad;
        var buf: [256]u8 = undefined;
        var len: usize = 0;
        var spans = false;
        var repeats: usize = 0;
        // 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;
            var quantified = 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;
                    quantified = false;
                } else if (in_class) {
                    in_class = c != ']';
                } else if (c == '[') {
                    in_class = true;
                    quantified = false;
                } else if (c == '*' or c == '+' or c == '{' or (c == '?' and !quantified)) {
                    // A lazy or possessive mark after a repeat is the same repeat.
                    if (!emit and !quantified and c != '?') repeats += 1;
                    quantified = c != '?';
                } else {
                    if (c == '.' and spans) piece = "[^\\n]";
                    quantified = false;
                }
                if (!emit) continue;
                if (len + piece.len > buf.len) return error.Bad;
                @memcpy(buf[len..][0..piece.len], piece);
                len += piece.len;
            }
            if (repeats > 4) return error.TooCostly;
        }
        // Sizes from timing mvzr: one call over a window of the worst text
        // for its pattern (`a*a*a*a*x` over `a`s) takes under 40 ms, so the
        // deadline is never overrun by much.
        const window: usize = switch (repeats) {
            0, 1 => 64 * 1024,
            2 => 256,
            3 => 96,
            else => 40,
        };
        return .{
            .re = mvzr.compile(buf[0..len]) orelse return error.Bad,
            .spans = spans,
            .bol = pat[0] == '^',
            .window = window,
            .deadline = nowMs() + 300,
        };
    }

    fn nowMs() i64 {
        if (comptime !hosted) return 0;
        var ts: std.c.timespec = undefined;
        _ = std.c.clock_gettime(.MONOTONIC, &ts);
        return @as(i64, ts.sec) * 1000 + @divTrunc(@as(i64, ts.nsec), 1_000_000);
    }

    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: *const Regex, text: []const u8, from: usize, last: usize, hi: usize) error{TooSlow}!?Match {
        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];
            // A line longer than a window is searched a window at a time,
            // each overlapping the last by half; a match ending at a window's
            // edge that is not the line's is left to the next window, whose
            // `$` is not a false line end.
            var lo = at -| at % @max(1, rx.window / 2);
            while (true) {
                if (comptime hosted) if (nowMs() > rx.deadline) return error.TooSlow;
                const top = @min(line.len, lo + rx.window);
                const hay = line[lo..top];
                const pos = @max(at, lo) - lo;
                // matchPos finds nothing at a haystack's very end, where `$`
                // or an empty match still can.
                const hit: ?[2]usize = if (pos < hay.len)
                    (if (rx.re.matchPos(pos, hay)) |m| .{ lo + m.start, lo + m.end } else null)
                else if (pos == hay.len and top == line.len and rx.re.isMatch(hay[pos..])) .{ lo + pos, lo + pos } else null;
                if (hit) |h| if (top == line.len or h[1] < top) {
                    if (start + h[0] > last) return null;
                    return .{ .start = start + h[0], .end = start + h[1] };
                };
                if (top == line.len or (rx.bol and !rx.spans)) break;
                lo += rx.window / 2;
            }
            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| {
        const 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");
    try std.testing.expect(try (try Regex.compile("zzz")).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.
    const 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.
    const 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.
    try std.testing.expect(try (try Regex.compile("[]x]")).find("x]", 0, 2, 2) == null);
}

test "a pattern that would backtrack without end comes back promptly, refused or cut short" {
    try std.testing.expectError(error.TooCostly, Regex.compile("a*a*a*a*a*x"));
    // Four repeats over a long line of what they match: windows keep each
    // mvzr call small, and the deadline ends the whole search.
    var text: [20000]u8 = @splat('a');
    for (0..20) |i| text[i * 1000 + 999] = '\n';
    for ([_][]const u8{ "a*a*a*a*x", ".*.*.*x", ".*.*x", "(a*)*x", "(a|a)*x" }) |pat| {
        const rx = try Regex.compile(pat);
        const before = Regex.nowMs();
        if (rx.find(&text, 0, text.len, text.len)) |m| {
            try std.testing.expect(m == null);
        } else |err| try std.testing.expectEqual(error.TooSlow, err);
        if (comptime hosted) try std.testing.expect(Regex.nowMs() - before < 2000);
    }
}