moonbitlang / core / 6203

91%

push

github

perf(list): single-pass two-pointer has_suffix, rename is_suffix/is_prefix (#4109)

Supersedes the approach in #3840. The old is_suffix reversed both lists
(two O(n)/O(m) allocations); #3840 proposed length + drop + prefix
comparison, which is allocation-free but still walks self twice
(2n + m steps: two length() traversals, then drop, then the compare).

This version is a single pass in n + m steps with no allocation and no
length() calls: advance a lead pointer one node per suffix node (proving
on the way that the suffix is not longer), then slide lead and a lag
pointer together until lead falls off the end — lag then sits exactly
suffix.length() nodes from the end, the only window where the suffix can
match — and an element-wise comparison of that equal-length window
decides. List == is deliberately not used for the window: its
physical-equality shortcut would declare a NaN-carrying list a suffix of
itself, changing the observable element-wise behavior (caught by Codex
CLI review; pinned by a regression test). An empty suffix returns true
without touching the list.

Benchmarks (moon bench --release, list n=100K, suffix m=50K unless
noted; old rev-based / #3840's drop-based / this):

  native:  match        1.33ms / 418us / 287us
           mismatch-1st 1.34ms / 315us / 184us
           shared tail  1.34ms / 394us / 272us
           tiny m=10    833us  / 305us / 154us
           empty m=0    817us  / 302us / 6.7ns
  js:      match        621us  / 337us / 200us
           shared tail  469us  / 332us / 194us
           empty m=0    260us  / 234us / 8.1ns
  wasm-gc: match        783us  / 312us / 221us
           shared tail  745us  / 318us / 211us
           empty m=0    263us  / 237us / 7.5ns

Also renames is_suffix -> has_suffix and is_prefix -> has_prefix with
#alias(is_..., deprecated), matching the String and Bytes conventions
(String::has_suffix itself carries ends_with as a deprecated alias).
All call sites in tests, docstrings and the README ar... (continued)

9 of 10 new or added lines in 1 file covered. (90.0%)

16301 of 17969 relevant lines covered (90.72%)

331835.44 hits per line