Silent wrong answers on everyday patterns. Every row was executed through zig-js (Debug ad1ca106, zig-regex 73cc22d) against node v24.4.1. JavaScriptCore agrees with node.
| program | node | zig-js |
|---|---|---|
/(\d){2,4}/.exec("12") | ["12","2"] | ["12",null] |
/(a){1,3}/.exec("a") | ["a","a"] | ["a",null] |
/ab|abcd/i.exec("abcd") | ["ab"] | ["abcd"] |
/(?:ab)?(?:abcd)?/.exec("abcd") | ["ab"] | ["abcd"] |
/(a|ab)(c|bcd)(d*)/.exec("abcd") (ECMA-262's own example) | ["abcd","a","bcd",""] | ["abcd","ab","c","d"] |
/(a*){3}/.exec("aa"), /(a*){2,3}/.exec("aa") | ["aa",""] | ["aa","aa"] |
/(a?){2}/.exec("a") | ["a",""] | ["a","a"] |
The same wrong result appears with g, i, y, ^/$ anchors, (d+)? and d?. Forcing the backtracker with a (?=…) prefix gives node's answer every time.
Cause (read, and reproduced by a line-by-line model of compiler.zig + vm.zig):
vm.zigis not a priority-ordered Pike VM.addEpsilonClosure/followEpsilons(vm.zig:369-440) build the closure breadth-first with first-arrival dedup, so a (state, position) pair goes to the path with the fewest epsilon hops. The priority order thatcompiler.zigalready encodes in its transition order is ignored.- Acceptance is leftmost-longest (vm.zig:242-339): a later, longer accept overwrites an earlier, higher-priority one. ECMAScript is leftmost-first (22.2.2.3 MatchTwoAlternatives / RepeatMatcher).
- The same leftmost-longest end comes back for capture-free patterns on the DFA path (
findWithDfa, regex.zig:737-746). That is why/ab|abcd/imatchesabcd./iskips the literal-set fast path. - RepeatMatcher loop rules are missing. There is no empty-iteration check (step 2.b), and the loop-back edges don't clear the iteration's captures (step 4). Meanwhile
compileOptional's skip edge clears the previous copy's captures, which is what makes/(\d){2,4}/lose its capture.
Fix direction (all gated on flags.ecmascript, so PCRE/WAF behaviour is unchanged):
- a priority DFS closure with leftmost-first acceptance, and an explicit stack rather than recursion (#23);
- compiler loop marks for step 2.b, with clearing on iteration entry instead of on the skip edge;
- the capture-free DFA end replaced by the VM's leftmost-first end.
A differential test should fuzz the fixed VM against the backtracker. A JS model of this design matched node on 143,862 exec runs over 23,977 Thompson-routable patterns, but that is a model: the Zig port needs its own gate.
Note: PCRE/Perl are leftmost-first backtrackers too, so points 1, 2 and 4 are also wrong for non-ECMAScript users. Gating keeps their current behaviour until that is decided separately.