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