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 <[email protected]>

1 files changed, 34 insertions, 1 deletions

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 });
     };