ReviewOS

zig-utils/zig-regex

ECMAScript captures and match ends follow leftmost-longest, not leftmost-first: /(\d){2,4}/ on "12" loses its capture

#27
Closed glennmichael123 opened this 9 days ago ·
9 days ago

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.

programnodezig-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):

  1. vm.zig is 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 that compiler.zig already encodes in its transition order is ignored.
  2. 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).
  3. 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/i matches abcd. /i skips the literal-set fast path.
  4. 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.

9 days ago

Taking this too, as the next change after the multiline and backreference fixes. It is a VM rework, so it gets its own differential gate.

9 days ago

Fixed in bc14170. The VM is now priority-ordered and leftmost-first, the compiler lowers quantifiers by RepeatMatcher's rules, and the lazy DFA's match-end mode is ordered like RE2's; all of it is gated on ecmascript.

Evidence:

  • A 43-row node-verified table passes; on the committed engine it fails on its first row.
  • In the fuzz differential (35,980 runs), the Thompson engine now agrees with node on every run: 964 fixed, 0 regressed.
  • test-core: 366/366.
  • ReleaseFast ECMAScript throughput is unchanged within noise, with an exec loop about +4%.

The remaining disagreements are all on the backtracker, filed separately. The zig-js pin and pinned cases follow.

9 days ago

Downstream corpus check for the fix in bc14170, run from zig-js against test262 (Debug, test262-bin, one binary built at 6e805ad and one at bc14170, same corpus, --diag per subtree):

  • 73 subtree groups covering the RegExp and String-with-regexp surface (RegExp/**, String/match, matchAll, replace, replaceAll, search, split, literals-regexp), 1,970 passes on both sides, identical row for row.
  • The one failure, literals-regexp 1 fail, is present on both binaries and predates this change.
  • character-class-escape-non-whitespace.js needs more than the 3 GB memory ceiling in Debug on either binary, so it ran as an every-16th-code-unit replica: OK replica-ok on both.
  • property-escapes/generated was sampled every 20th file (31 of 613); all identical.

So the leftmost-first change flips no test262 case in either direction — consistent with the 43-row golden table and the 35,980-run node differential already posted here.

Sign in to comment on this issue.