From a945c035ce9e3d5fda81a05f95f3ea1788a19ece Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Tue, 29 Sep 2026 13:43:52 -0300 Subject: A ^ after | anchors its branch: ^def|^ finds lines starting either way mvzr takes ^ only at its pattern's start, so in ^def|^ the second branch never matched mid-text. An alternation whose every top-level branch starts with ^ is now compiled as ^(def| ); a mix of anchored and unanchored branches is refused rather than silently wrong. Co-Authored-By: Claude Opus 5.5 --- .agents/skills/pardes-9p/SKILL.md | 4 +-- docs/fs.md | 11 ++++--- src/regexp.zig | 65 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 73 insertions(+), 7 deletions(-) diff --git a/.agents/skills/pardes-9p/SKILL.md b/.agents/skills/pardes-9p/SKILL.md index a91b4861..16e90dc9 100644 --- a/.agents/skills/pardes-9p/SKILL.md +++ b/.agents/skills/pardes-9p/SKILL.md @@ -289,8 +289,8 @@ through 14:2 inclusive), whose regexps are mvzr's searched as sam searches: newline, the leftmost match wins (the first alternative there, not the longest). In a pattern with `\n`, `^` works only first (`^def .*\n` finds every def line) and `$` only just before a `\n`; anywhere else the pattern is -refused, not silently unmatched. `^` inside an alternation (`^def|^ `) holds -only where the search starts: fine in `x` over lines or `g`, not mid-line. An expression is evaluated from the current address (the last one +refused, not silently unmatched. `^def|^ ` finds lines starting either way +(every branch anchored; a mix like `^def|x` is refused). An expression is evaluated from the current address (the last one written, or just past the last `data` write): `.` is that address, not the selection, `/re/` searches on from its end and wraps unless `limit` is set, `?re?` or `-/re/` searches back, `#100,#50` fails `addresses out of order`, diff --git a/docs/fs.md b/docs/fs.md index 088d1c92..339c14ba 100644 --- a/docs/fs.md +++ b/docs/fs.md @@ -703,10 +703,11 @@ matches at every line start, and `$` may stand just before a `\n` (where it changes nothing). Any other `^` or `$` in such a pattern, `(^|\n)def` or `a\nb$`, is refused, EINVAL, with `bad regular expression: in a pattern with \n, ^ can only come first and $ only just before a \n`, since mvzr would read it as the start or end of the -whole text: never a search that silently finds nothing. Within a line, `^` -inside an alternation (`^def|^ `) matches only where the search starts, so it -works from a line's start (an `x` over lines, a `g` on one) and not from its -middle: an mvzr limit. An expression is +whole text: never a search that silently finds nothing. An alternation +whose every branch starts with `^` (`^def|^ `) finds a line that starts +either way (it is taken as `^(def| )`); one that mixes anchored and +unanchored branches (`^def|x`) is refused, `bad regular expression`, since +mvzr keeps `^` only first. An expression is evaluated from the current address, the range last written to `addr` (or left by the last `data` write, just past it), as acme evaluates it from `w->addr` (xfid.c:446): `.` is that address, not the selection (`dot` is @@ -718,7 +719,7 @@ otherwise wraps to the start of the text; `?re?` and `-/re/` find the last match ending before the range, wrapping to the text's last. The match is the leftmost, but of the alternatives at that place mvzr takes the first that matches where sam takes the longest (`/gam|gamma/` finds `gam`); in a search begun in the -middle of a line, `^` inside an alternation can match there; and in a +middle of a line, `^` inside a group can match there; and in a pattern that spans lines, `^`, `$` and `[^...]` keep mvzr's own meaning. mvzr backtracks without bound of its own (`a?` twenty times then twenty `a`s is 2^20 steps from each place it tries), and a search holds the editor, so pardes patches a diff --git a/src/regexp.zig b/src/regexp.zig index 27b3c0ba..ca396ff1 100644 --- a/src/regexp.zig +++ b/src/regexp.zig @@ -48,6 +48,11 @@ pub const Regex = struct { /// ends of the whole text and so never match where sam would. pub fn compile(pat: []const u8) error{ Bad, Anchor }!Regex { if (pat.len == 0) return error.Bad; + // mvzr takes `^` only at its pattern's start, so `^def|^ ` (a `^` + // after a `|`) is written `^(def| )` for it: the same lines. A mix, + // `^a|b`, has no such spelling and is refused rather than wrong. + var joined: [258]u8 = undefined; + if (try anchoredAlternation(pat, &joined)) |whole| return compile(whole); var buf: [256]u8 = undefined; var len: usize = 0; var spans = false; @@ -97,6 +102,56 @@ pub const Regex = struct { }; } + /// `^a|^b` as `^(a|b)` in `out`, when the pattern is an alternation at + /// its top level and every branch starts with `^`; null when it is not + /// one, or no branch does. + fn anchoredAlternation(pat: []const u8, out: *[258]u8) error{Bad}!?[]const u8 { + var bars: [16]usize = undefined; + var n: usize = 0; + var depth: usize = 0; + var in_class = false; + var i: usize = 0; + while (i < pat.len) : (i += 1) { + const c = pat[i]; + if (c == '\\') { + i += 1; + } else if (in_class) { + in_class = c != ']'; + } else if (c == '[') { + in_class = true; + } else if (c == '(') { + depth += 1; + } else if (c == ')') { + depth -|= 1; + } else if (c == '|' and depth == 0) { + if (n == bars.len) return error.Bad; + bars[n] = i; + n += 1; + } + } + if (n == 0) return null; + var anchored: usize = 0; + var from: usize = 0; + for (0..n + 1) |k| { + const to = if (k < n) bars[k] else pat.len; + anchored += @intFromBool(to > from and pat[from] == '^'); + from = to + 1; + } + if (anchored == 0) return null; + if (anchored != n + 1) return error.Bad; + var w = std.Io.Writer.fixed(out); + w.writeAll("^(") catch return error.Bad; + from = 0; + for (0..n + 1) |k| { + const to = if (k < n) bars[k] else pat.len; + if (k > 0) w.writeByte('|') catch return error.Bad; + w.writeAll(pat[from + 1 .. to]) catch return error.Bad; + from = to + 1; + } + w.writeByte(')') catch return error.Bad; + return w.buffered(); + } + pub const Match = struct { start: usize, end: usize }; /// The first match that starts in `from..=last` and ends by `hi`, as @@ -185,6 +240,16 @@ test "lines are haystacks: ^ and $ at each line, . never a newline, \\n spans li try std.testing.expectError(error.Bad, Regex.compile("a\\")); } +test "a ^ after | anchors that branch: ^def|^ finds a line that starts either way, and a mix is refused" { + const text = "x def\n a\ndef b\n"; + var both = try Regex.compile("^def|^ "); + try std.testing.expectEqual(@as(usize, 6), (try both.find(text, 0, text.len, text.len)).?.start); + try std.testing.expectEqual(@as(usize, 9), (try both.find(text, 7, text.len, text.len)).?.start); + try std.testing.expectError(error.Bad, Regex.compile("^def|x")); + var plain = try Regex.compile("a|b"); + try std.testing.expectEqual(@as(usize, 7), (try plain.find(text, 0, text.len, text.len)).?.start); +} + 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. -- cgit v1.3