1 files changed, 104 insertions, 0 deletions
diff --git a/src/regexp.zig b/src/regexp.zig
new file mode 100644
index 00000000..665e51d5
--- /dev/null
+++ b/src/regexp.zig
@@ -0,0 +1,104 @@
+//! 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);
+}