//! 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");

/// 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]`.
/// 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. 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,

    pub fn compile(pat: []const u8) ?Regex {
        if (pat.len == 0) return null;
        const spans = std.mem.indexOf(u8, pat, "\\n") != null;
        var buf: [256]u8 = undefined;
        var len: usize = 0;
        var i: usize = 0;
        var in_class = false;
        while (i < pat.len) : (i += 1) {
            const c = pat[i];
            const piece: []const u8 = if (c == '\\') piece: {
                if (i + 1 >= pat.len) return null;
                i += 1;
                break :piece pat[i - 1 .. i + 1];
            } else if (c == '.' and spans and !in_class) "[^\\n]" else pat[i .. i + 1];
            if (len + piece.len > buf.len) return null;
            if (c == '[') in_class = true;
            if (c == ']') in_class = false;
            @memcpy(buf[len..][0..piece.len], piece);
            len += piece.len;
        }
        return .{ .re = mvzr.compile(buf[0..len]) orelse return null, .spans = spans, .bol = pat[0] == '^' };
    }

    /// 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) ?struct { start: usize, end: usize } {
        if (rx.spans) {
            const m = rx.re.matchPos(from, text[0..hi]) orelse return null;
            return if (m.start <= last) .{ .start = m.start, .end = m.end } else null;
        }
        var start = 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.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 = std.mem.indexOfScalarPos(u8, text[0..hi], start, '\n') orelse hi;
            const line = text[start..end];
            // matchPos finds nothing at a line'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 (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| {
        const rx = Regex.compile(c.pat).?;
        const m = 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 std.testing.expect(Regex.compile("a.*a\\nq") != null);
    try std.testing.expect((Regex.compile("zzz").?).find(text, 0, text.len, text.len) == null);
    try std.testing.expect(Regex.compile("") == null);
    try std.testing.expect(Regex.compile("a\\") == null);
}