1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
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);
}
|
