diff options
| -rw-r--r-- | build.zig | 35 | ||||
| -rw-r--r-- | docs/mvzr-group-backtrack.md | 64 | ||||
| -rw-r--r-- | src/regexp.zig | 23 |
3 files changed, 121 insertions, 1 deletions
@@ -454,7 +454,40 @@ pub fn build(b: *std.Build) void { \\pub threadlocal var exhausted: bool = false; \\ ; - const patched = b.fmt("{s}{s}{s}{s}", .{ src[0..at], spend, src[at..], budget }); + const budgeted = b.fmt("{s}{s}{s}{s}", .{ src[0..at], spend, src[at..], budget }); + // A group's greedy match never gave back to what follows the group: + // on `aab`, `(a+)ab` missed where `a+ab` matched. hasAlt counts the + // group's own `)` as an alternative, so every group with pattern + // after it takes matchGroup's alternatives branch, which tries each + // alternative's one (greedy) match and gives up. When the rest fails + // after it, try that alternative's shorter matches, longest first + // (docs/mvzr-group-backtrack.md is the report for upstream). + const group_anchor = + \\ const next_match = matchPattern(next_patt, sets, haystack, m1.i); + \\ if (next_match) |m2| { + \\ // Whole group matches, and we can use m2.j + \\ return m2; + \\ } else { // Try our next pattern, if any. + \\ + ; + const group_backoff = + \\ const next_match = matchPattern(next_patt, sets, haystack, m1.i); + \\ if (next_match) |m2| { + \\ // Whole group matches, and we can use m2.j + \\ return m2; + \\ } else { // Try our next pattern, if any. + \\ // pardes's patch (its build.zig): back the group off. + \\ var e = m1.i; + \\ while (e > i) { + \\ e -= 1; + \\ const shorter = matchAlt(remaining_patt, sets, haystack[0..e], i) orelse continue; + \\ if (shorter.i != e) continue; + \\ if (matchPattern(next_patt, sets, haystack, e)) |whole| return whole; + \\ } + \\ + ; + 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"); 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 new file mode 100644 index 00000000..d074af62 --- /dev/null +++ b/docs/mvzr-group-backtrack.md @@ -0,0 +1,64 @@ +# mvzr: a repeat inside a group never gives back to what follows the group + +A report for upstream (https://github.com/mnemnion/mvzr), against trunk +3efcfe3 (0.3.9). pardes patches its fetched copy at build time (build.zig) +until it is fixed there. + +## What happens + +```zig +const mvzr = @import("mvzr"); +// a+ab matches aab; the same with the repeat in a group does not +std.debug.assert(mvzr.compile("a+ab").?.match("aab") != null); +std.debug.assert(mvzr.compile("(a+)ab").?.match("aab") == null); // expected a match +``` + +The same for `(a*)ab` on `aab`, `(.+)_area` and `([a-z_]+)_area` on +`the_total_area`. `\w+_area` and `(\w)+_area` match, as does +`([a-z]+)_area` (whose class cannot eat the `_`, so no giving back is +needed). + +## Why + +`hasAlt` returns true when its scan reaches the group's own closing +`.right` at depth 0: + +```zig +.right => { + if (pump == 0) + return true // the group's own `)`, not an alternative + else + pump -= 1; +}, +``` + +so every group with more pattern after it goes down `matchGroup`'s +alternatives branch. That branch takes each alternative's single match (a +greedy repeat's longest) and, when the pattern after the group fails from +there, moves on to the next alternative; it never tries a shorter match of +the same alternative. The alt-free branch has the same shape. + +## A fix + +Where the pattern after the group fails from an alternative's match, try +that alternative's shorter matches, longest first, before the next +alternative. pardes's patch, in `matchGroup`'s loop: + +```zig +} else { // Try our next pattern, if any. + var e = m1.i; + while (e > i) { + e -= 1; + const shorter = matchAlt(remaining_patt, sets, haystack[0..e], i) orelse continue; + if (shorter.i != e) continue; + if (matchPattern(next_patt, sets, haystack, e)) |whole| return whole; + } + remaining_patt = m1.j; +} +``` + +Matching the alternative against `haystack[0..e]` makes `$` and `\b` see a +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. diff --git a/src/regexp.zig b/src/regexp.zig index 249763c2..97e3dc91 100644 --- a/src/regexp.zig +++ b/src/regexp.zig @@ -235,3 +235,26 @@ test "a \\x without two hex digits is refused, not handed to mvzr to panic on" { var rx = try Regex.compile("\\x41"); try std.testing.expectEqual(@as(usize, 1), (try rx.find("xA", 0, 1, 2)).?.start); } + +test "a repeat inside a group gives back to what follows the group" { + const Case = struct { pat: []const u8, text: []const u8, start: usize, end: usize }; + for ([_]Case{ + .{ .pat = "a+ab", .text = "aab", .start = 0, .end = 3 }, + .{ .pat = "(a+)ab", .text = "aab", .start = 0, .end = 3 }, + .{ .pat = "(a*)ab", .text = "aab", .start = 0, .end = 3 }, + .{ .pat = "(.+)_area", .text = "the_total_area x", .start = 0, .end = 14 }, + .{ .pat = "([a-z_]+)_area", .text = "the_total_area x", .start = 0, .end = 14 }, + .{ .pat = "\\w+_area", .text = "the_total_area x", .start = 0, .end = 14 }, + .{ .pat = "(\\w)+_area", .text = "the_total_area x", .start = 0, .end = 14 }, + .{ .pat = "([a-z]+)_area", .text = "the_total_area x", .start = 4, .end = 14 }, + .{ .pat = "x(ab|a)bc", .text = "xabc", .start = 0, .end = 4 }, + }) |c| { + var rx = try Regex.compile(c.pat); + const m = (try rx.find(c.text, 0, c.text.len, c.text.len)) orelse { + std.debug.print("no match for {s}\n", .{c.pat}); + return error.NoMatch; + }; + try std.testing.expectEqual(c.start, m.start); + try std.testing.expectEqual(c.end, m.end); + } +} |