From fad6bf0cc7cc2cb579d9ad03147a7014906f6b92 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Tue, 29 Sep 2026 00:36:25 -0300 Subject: A repeat inside a regexp group gives back to what follows the group On aab, /a+ab/ matched but /(a+)ab/ and /(a*)ab/ missed, and so did (.+)_area and ([a-z_]+)_area, in addr, Edit and look alike. mvzr's hasAlt counts a group's own ) as an alternative, so every group with pattern after it takes matchGroup's alternatives branch, which never tries a repeat's shorter matches. No newer mvzr fixes it (trunk is the pinned commit), so the build patches the fetched source as it does the step budget, anchor-checked: when the rest fails after a group, the group's shorter matches are tried, longest first. docs/mvzr-group-backtrack.md is a report for upstream. Co-Authored-By: Claude Opus 5.5 --- build.zig | 35 ++++++++++++++++++++++++++++++++++- 1 file changed, 34 insertions(+), 1 deletion(-) (limited to 'build.zig') diff --git a/build.zig b/build.zig index a78cd442..53cbcda5 100644 --- a/build.zig +++ b/build.zig @@ -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 }); }; -- cgit v1.3