summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ninep/addr.zig22
-rw-r--r--src/normal.zig5
-rw-r--r--src/regexp.zig190
3 files changed, 168 insertions, 49 deletions
diff --git a/src/ninep/addr.zig b/src/ninep/addr.zig
index 347a2d11..69e6dc77 100644
--- a/src/ninep/addr.zig
+++ b/src/ninep/addr.zig
@@ -14,6 +14,8 @@ fn clip(n: usize) u32 {
pub const e_no_match = "no match for regexp";
pub const e_range = "address out of range";
pub const e_regexp = "bad regular expression";
+pub const e_costly = "regular expression has more than four repeats";
+pub const e_slow = "regular expression search took too long";
pub const e_syntax = "bad address syntax";
pub const Addr = struct {
@@ -196,8 +198,8 @@ pub const Addr = struct {
a.err = "no previous regular expression";
return null;
}
- const rx = regexp_.Regex.compile(pat) orelse {
- a.err = e_regexp;
+ const rx = regexp_.Regex.compile(pat) catch |err| {
+ a.err = if (err == error.TooCostly) e_costly else e_regexp;
return null;
};
const found = if (back) found: {
@@ -205,7 +207,10 @@ pub const Addr = struct {
var before: ?Range = null;
var at: usize = 0;
while (at <= a.text.len) {
- const m = rx.find(a.text, at, a.text.len, a.text.len) orelse break;
+ const m = (rx.find(a.text, at, a.text.len, a.text.len) catch {
+ a.err = e_slow;
+ return null;
+ }) orelse break;
const found_range: Range = .{ .q0 = clip(m.start), .q1 = clip(m.end) };
if (found_range.q1 <= r.q0) before = found_range;
last = found_range;
@@ -215,7 +220,14 @@ pub const Addr = struct {
} else found: {
const hi = if (a.lim) |l| @min(@as(usize, l.q1), a.text.len) else a.text.len;
const from = @min(@as(usize, r.q1), hi);
- const m = rx.find(a.text, from, hi, hi) orelse (if (a.lim != null or from == 0) null else rx.find(a.text, 0, from - 1, hi)) orelse break :found null;
+ const ahead = rx.find(a.text, from, hi, hi) catch {
+ a.err = e_slow;
+ return null;
+ };
+ const m = ahead orelse (if (a.lim != null or from == 0) null else rx.find(a.text, 0, from - 1, hi) catch {
+ a.err = e_slow;
+ return null;
+ }) orelse break :found null;
break :found Range{ .q0 = clip(m.start), .q1 = clip(m.end) };
};
return found orelse {
@@ -366,7 +378,7 @@ test "the address language, form by form" {
for ([_][2][]const u8{
.{ "zzz", e_syntax }, .{ "/nomatch/", e_no_match }, .{ "99", e_range },
.{ "#999", e_range }, .{ "/a[/", e_regexp }, .{ "/(a/", e_regexp },
- .{ "/*a/", e_regexp },
+ .{ "/*a/", e_regexp }, .{ "/a*b*c*d*e*/", e_costly },
}) |c| {
_ = th.wr(p, addr, "#0");
try testing.expectEqualStrings(c[1], th.wr(p, addr, c[0]).reply.ename);
diff --git a/src/normal.zig b/src/normal.zig
index 8c5f232d..09e06b13 100644
--- a/src/normal.zig
+++ b/src/normal.zig
@@ -110,7 +110,8 @@ pub fn applySelRegex(p: *Pardes, pane: *Pane, t: *Text, pat: []const u8, split:
var at = from;
var piece = from; // split: where the next piece begins
while (at < to and m < Text.max_selections) {
- const hit_at = re.find(hay_all, at, to, to) orelse break;
+ // A search too slow to finish keeps what it found so far.
+ const hit_at = (re.find(hay_all, at, to, to) catch break) orelse break;
if (split) {
out[m] = .{ .anchor = piece, .head = hit_at.start };
m += 1;
@@ -127,7 +128,7 @@ pub fn applySelRegex(p: *Pardes, pane: *Pane, t: *Text, pat: []const u8, split:
m += 1;
}
}
- }
+ } else |_| {}
if (m == 0) {
// the text CAN move under an armed prompt (a tag chord runs a
// builtin), and these are raw offsets into the surface as it was
diff --git a/src/regexp.zig b/src/regexp.zig
index 665e51d5..c758ee81 100644
--- a/src/regexp.zig
+++ b/src/regexp.zig
@@ -3,6 +3,7 @@
//! 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.
///
@@ -11,67 +12,140 @@ const mvzr = @import("mvzr");
/// 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. A regex engine of sam's own would lift
-/// these; the user chose not to have one.
+/// 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 fn compile(pat: []const u8) ?Regex {
- if (pat.len == 0) return null;
- const spans = std.mem.indexOf(u8, pat, "\\n") != null;
+ 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 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;
+ 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;
}
- return .{ .re = mvzr.compile(buf[0..len]) orelse return null, .spans = spans, .bol = pat[0] == '^' };
+ // 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) ?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;
+ 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.bol and at > 0) {
+ 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 = std.mem.indexOfScalarPos(u8, text[0..hi], start, '\n') orelse hi;
+ 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 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] };
+ // 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;
@@ -92,13 +166,45 @@ test "lines are haystacks: ^ and $ at each line, . never a newline, \\n spans li
.{ .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).?;
+ 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 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);
+ _ = 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);
+ }
}
generated by cgit v1.3 (git 2.53.0) at 2026-10-02 08:04:43 +0000