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, 64 insertions, 0 deletions

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.