# 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.

# 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] != ')') {
```