From 78c60342022bc44307ad789aaef163ab96ebd08b Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Mon, 28 Sep 2026 11:48:17 -0300 Subject: A regular expression search comes back: costly patterns refused, long lines windowed, 300 ms deadline mvzr backtracks with no bound on its work (a*a*a*a*x over a hundred a's takes a second, each repeat multiplying by the haystack length), and a search runs holding the editor's turn, so one pasted pattern froze the editor. pardes does not write or vendor a regex engine, so regexp.zig bounds what it hands mvzr: more than four repeats is refused, a line longer than a window sized from measured worst cases is searched in half-overlapping windows, and a deadline stops the search. addr names each failure; normal s/S keeps what it found. The prescan also stops reading an escaped backslash before n as a newline, and ends a class where mvzr does. Co-Authored-By: Claude Opus 5.5 --- src/regexp.zig | 190 ++++++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 148 insertions(+), 42 deletions(-) (limited to 'src/regexp.zig') 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); + } } -- cgit v1.3