ReviewOS

zig-utils/zig-js

Strings: replace and split by UTF-16 code unit

#624
Closed chris opened this 8 days ago ·
8 days ago

Parent: #473 Related security/performance parent: #493 Builds on: #622, #623

Problem

The plain-string paths for String.prototype.replace, replaceAll, and non-empty-separator split search the engine's WTF-8 backing bytes. ECMAScript defines these searches, match positions, and substrings over UTF-16 code units. Consequently, a separator or search string containing one surrogate half cannot match that half inside an astral scalar, replacement callback positions can diverge, and replaceAll("") skips the boundary between the two halves of an astral scalar.

Required implementation

  • Reuse the exact UTF-16 matcher introduced by #622/#623 instead of byte offsets on non-ASCII strings.
  • Preserve an allocation-free ASCII fast path.
  • Collect replaceAll match positions before invoking replacement callbacks, per ECMA-262, while keeping the scan bounded-linear and non-overlapping.
  • Assemble preceding/trailing replacement spans and split substrings in UTF-16 space, including boundaries inside astral scalars and lone surrogates.
  • Keep matcher scratch bounded, explicitly owned, and released on success and error paths.
  • Do not implement repeated-from-zero searches, byte-offset approximations, input-specific shortcuts, or third-party matching.

Acceptance

  • Focused tests cover astral high/low-half searches and separators, lone surrogates, empty search strings, overlaps, callback positions/order, substitution tokens, limits, and ASCII behavior.
  • Exact parent/candidate Test262 accounting for replace, replaceAll, and split has no regressions.
  • Focused normal and TSan tests pass without leaks.
  • The full parallel unit suite passes.
  • Growth/adversarial probes establish bounded-linear matching work and bounded scratch lifetime.

Specification

  • ECMA-262 String.prototype.replace uses StringIndexOf and UTF-16 substring boundaries.
  • replaceAll first builds the complete non-overlapping match-position list, advancing by max(1, searchLength).
  • split repeatedly applies StringIndexOf and forms UTF-16 substrings.
8 days ago

Implemented and pushed to main in fix(strings): replace and split by UTF-16 units (#624).

Evidence:

  • Exact parent runner cc08f845daa6f5877a27afff5fd558f5f8dc80c4c732694a4e2b18bae1531fe3; candidate 635441d18d9204d849b1598bf5e539d7c8f368ece46ccb8a05ae1a16e14b361c.
  • Test262: replace 55→55, replaceAll 45→45, split 120→120; 220→220 total, zero failures/flips.
  • Focused UTF-16 tests: 11/11 normal, no leaks. Replacement/split behavior: 1/1 under TSan, no leaks. Allocation-failure sweep covers every matcher/position-scratch failure point.
  • Full parallel units: 1,738 passed, 1 skipped, 0 failed, 0 leaked.
  • Dependency audit: 15 classified edges, 0 migration targets, 60 classified tools.

The non-ASCII path is a single bounded-linear KMP scan over abstract UTF-16 code units. replaceAll freezes compact non-overlapping positions before callbacks; output slicing preserves surrogate-half boundaries. Proven-equivalent ASCII paths retain direct byte search/split.

Sign in to comment on this issue.