1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
# 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] != ')') {
```
|
