summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ninep/addr.zig7
-rw-r--r--src/normal.zig3
-rw-r--r--src/regexp.zig151
3 files changed, 69 insertions, 92 deletions
diff --git a/src/ninep/addr.zig b/src/ninep/addr.zig
index 69e6dc77..cc7ca632 100644
--- a/src/ninep/addr.zig
+++ b/src/ninep/addr.zig
@@ -14,7 +14,6 @@ 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";
@@ -198,8 +197,8 @@ pub const Addr = struct {
a.err = "no previous regular expression";
return null;
}
- const rx = regexp_.Regex.compile(pat) catch |err| {
- a.err = if (err == error.TooCostly) e_costly else e_regexp;
+ var rx = regexp_.Regex.compile(pat) catch {
+ a.err = e_regexp;
return null;
};
const found = if (back) found: {
@@ -378,7 +377,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*b*c*d*e*/", e_costly },
+ .{ "/*a/", e_regexp },
}) |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 09e06b13..da707e26 100644
--- a/src/normal.zig
+++ b/src/normal.zig
@@ -92,7 +92,8 @@ pub fn applySelRegex(p: *Pardes, pane: *Pane, t: *Text, pat: []const u8, split:
const snap = pane.sel_snap[0..pane.nsel_snap];
var out: [Text.max_selections]modal.Selection = undefined;
var m: usize = 0;
- if (regexp.Regex.compile(pat)) |re| {
+ if (regexp.Regex.compile(pat)) |compiled| {
+ var re = compiled;
var hay_all = text;
if (for (pat) |c| {
if (std.ascii.isUpper(c)) break false;
diff --git a/src/regexp.zig b/src/regexp.zig
index c758ee81..fe68585d 100644
--- a/src/regexp.zig
+++ b/src/regexp.zig
@@ -2,8 +2,8 @@
//! 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 builtin = @import("builtin");
const mvzr = @import("mvzr");
-const hosted = @import("pardes.zig").hosted;
/// A compiled pattern and how to run it.
///
@@ -13,39 +13,39 @@ const hosted = @import("pardes.zig").hosted;
/// 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`.
+/// mvzr backtracks, and has no bound on its work of its own: `a?` twenty
+/// times then twenty `a`s is 2^20 steps from each start, `a*a*a*a*x` over a line of a
+/// hundred `a`s a second. The search runs with the editor's turn, so it must
+/// come back: build.zig patches a step budget into mvzr's matcher, and a
+/// search that spends `budget` steps (about 300 ms here) stops with
+/// `TooSlow`, found nothing rather than something wrong.
///
/// 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.
+/// and `[^...]` keep mvzr's meaning; and a quadratic pattern over a long
+/// enough line (`\s*(\w+)\s*=` over 20 KB of letters) runs out of budget. 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,
+ /// mvzr steps left to every search with this compiled pattern together,
+ /// so that addr's backward scan and s/S's many calls share one bound.
+ steps: u64 = budget,
- pub const Error = error{ Bad, TooCostly };
+ /// Timed on this machine's ReleaseSafe build: 10M steps of the worst
+ /// patterns take 45-80 ms, and a Debug build is ten times slower.
+ pub const budget: u64 = if (builtin.mode == .Debug) 4_000_000 else 32_000_000;
- pub fn compile(pat: []const u8) Error!Regex {
+ pub fn compile(pat: []const u8) error{Bad}!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| {
@@ -54,7 +54,6 @@ pub const Regex = struct {
// 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];
@@ -63,58 +62,35 @@ pub const Regex = struct {
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;
+ } else if (c == '.' and spans) {
+ piece = "[^\\n]";
}
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 {
+ pub fn find(rx: *Regex, text: []const u8, from: usize, last: usize, hi: usize) error{TooSlow}!?Match {
+ mvzr.steps_left = rx.steps;
+ mvzr.exhausted = false;
+ defer rx.steps = mvzr.steps_left;
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.
@@ -125,27 +101,15 @@ pub const Regex = struct {
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;
+ // matchPos finds nothing at a haystack'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 (mvzr.exhausted) return error.TooSlow;
+ 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;
@@ -166,13 +130,14 @@ 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 = try Regex.compile(c.pat);
+ var 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);
+ var none = try Regex.compile("zzz");
+ try std.testing.expect(try none.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\\"));
}
@@ -180,31 +145,43 @@ test "lines are haystacks: ^ and $ at each line, . never a newline, \\n spans li
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.");
+ var 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");
+ var 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);
+ var empty = try Regex.compile("[]x]");
+ try std.testing.expect(try empty.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);
+test "a search that would backtrack without end runs out of budget, promptly" {
+ var line: [20000]u8 = @splat('a');
+ for ([_][]const u8{ "(a|ab)*c", "a*a*a*a*a*x", ".*.*.*x" }) |pat| {
+ var rx = try Regex.compile(pat);
+ try std.testing.expectError(error.TooSlow, rx.find(&line, 0, line.len, line.len));
}
+ // As long a chain as mvzr compiles, over runs one `a` short of it: 2^20
+ // steps from every start.
+ for (0..line.len / 20) |i| line[i * 20 + 19] = 'b';
+ var chain = try Regex.compile("a?" ** 20 ++ "a" ** 20);
+ try std.testing.expectError(error.TooSlow, chain.find(&line, 0, line.len, line.len));
+}
+
+test "the match is the leftmost, however long the line" {
+ // A window cut into the identifier would find `x... =` from its middle.
+ const text = "let " ++ "x" ** 100 ++ " = 1";
+ var assign = try Regex.compile("\\s*(\\w+)\\s*=");
+ const m = (try assign.find(text, 0, text.len, text.len)).?;
+ try std.testing.expectEqual(@as(usize, 3), m.start);
+ try std.testing.expectEqual(@as(usize, 106), m.end);
+ // Repeats are not counted or capped.
+ var five = try Regex.compile("a*b*c*d*e*f");
+ const f = (try five.find("xxaabbf", 0, 7, 7)).?;
+ try std.testing.expectEqual(@as(usize, 2), f.start);
+ try std.testing.expectEqual(@as(usize, 7), f.end);
}
generated by cgit v1.3 (git 2.53.0) at 2026-10-02 05:48:31 +0000