diff options
| -rw-r--r-- | build.zig | 19 | ||||
| -rw-r--r-- | docs/mvzr-group-backtrack.md | 22 | ||||
| -rw-r--r-- | src/regexp.zig | 17 |
3 files changed, 57 insertions, 1 deletions
@@ -500,7 +500,24 @@ pub fn build(b: *std.Build) void { \\ ; if (std.mem.count(u8, budgeted, group_anchor) != 1) @panic("mvzr's matchGroup changed: redo its group backtracking in build.zig"); - const patched = std.mem.replaceOwned(u8, b.allocator, budgeted, group_anchor, group_backoff) catch @panic("OOM"); + const backed = std.mem.replaceOwned(u8, b.allocator, budgeted, group_anchor, group_backoff) catch @panic("OOM"); + // `$` is refused anywhere but last, so `h$|zz` was a bad pattern + // while `zz|h$` was fine. An alternative or a group ends at `|` and + // `)`, and the matcher's `.end` ends the alternative it is in, so + // `$` may stand before either (docs/mvzr-group-backtrack.md). + const end_anchor = + \\ '$' => { + \\ if (i + 1 < in.len) { + \\ + ; + const end_before_alt = + \\ '$' => { + \\ // pardes's patch (its build.zig): `$` may end an alternative. + \\ if (i + 1 < in.len and in[i + 1] != '|' and in[i + 1] != ')') { + \\ + ; + if (std.mem.count(u8, backed, end_anchor) != 1) @panic("mvzr's parser changed: redo its `$` before `|` in build.zig"); + const patched = std.mem.replaceOwned(u8, b.allocator, backed, end_anchor, end_before_alt) catch @panic("OOM"); break :mvzr b.createModule(.{ .root_source_file = b.addWriteFiles().add("mvzr.zig", patched), .target = target, .optimize = optimize }); }; diff --git a/docs/mvzr-group-backtrack.md b/docs/mvzr-group-backtrack.md index d074af62..867336a3 100644 --- a/docs/mvzr-group-backtrack.md +++ b/docs/mvzr-group-backtrack.md @@ -62,3 +62,25 @@ string end at `e`, so a group ending in either can accept a cut the full string would not; a continuation-passing matcher (each repeat trying the rest of the whole pattern) would be the full fix. `hasAlt` returning false at the group's own `)` is worth fixing too. + +# mvzr: `$` before `|` is a bad pattern + +A second report, same trunk. `compile` refuses `$` anywhere but at the +very end of the pattern, so an anchored alternative must come last: + +```zig +std.debug.assert(mvzr.compile("zz|h$") != null); +std.debug.assert(mvzr.compile("h$|zz") == null); // expected a regex +std.debug.assert(mvzr.compile("(h$|zz)") == null); // likewise +``` + +The parser's check is `if (i + 1 < in.len) bad_string = true`. The +matcher already handles `.end` inside an alternative: `matchAlt` and +`matchGroup` hand `matchPattern` each alternative as its own slice, and +`.end` returns an empty rest, which ends that slice. So `$` can stand +before `|` or `)` as well as last; pardes's patch: + +```zig +'$' => { + if (i + 1 < in.len and in[i + 1] != '|' and in[i + 1] != ')') { +``` diff --git a/src/regexp.zig b/src/regexp.zig index 97e3dc91..64e1d75a 100644 --- a/src/regexp.zig +++ b/src/regexp.zig @@ -258,3 +258,20 @@ test "a repeat inside a group gives back to what follows the group" { try std.testing.expectEqual(c.end, m.end); } } + +test "`$` may end any alternative, not only the last" { + const Case = struct { pat: []const u8, text: []const u8, start: usize, end: usize }; + for ([_]Case{ + .{ .pat = "h$|zz", .text = "xh", .start = 1, .end = 2 }, + .{ .pat = "zz|h$", .text = "xh", .start = 1, .end = 2 }, + .{ .pat = "h$|zz", .text = "hx zz", .start = 3, .end = 5 }, + .{ .pat = "(h$|zz)", .text = "xh", .start = 1, .end = 2 }, + }) |c| { + var rx = try Regex.compile(c.pat); + const m = (try rx.find(c.text, 0, c.text.len, c.text.len)).?; + try std.testing.expectEqual(c.start, m.start); + try std.testing.expectEqual(c.end, m.end); + } + var only = try Regex.compile("h$|zz"); + try std.testing.expectEqual(null, try only.find("hx", 0, 2, 2)); +} |