moonbitlang / core / 4898

91%

Build Type

push

github

Committed by web-flow

Commit Message

fix(immut/vector): concat no longer builds a radix node with a partial leaf (#3732)

* test(immut/vector): add failing test for concat radix random-access bug

`Vector::concat` can fold a partial leaf into a node still marked as full
(`sizes = None`). Iteration traverses children directly so it stays correct,
but radix random access (`get`/`at`/`set`) indexes the partial leaf out of
bounds.

Add a black-box regression test covering both the minimal 8x17 reproduction
from the issue and a sweep over many chunk sizes/counts, asserting that random
access agrees with iteration. These currently fail.

See https://github.com/moonbitlang/core/issues/3721

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>

* fix(immut/vector): keep sizes when folding a partial leaf into the tree

`Tree::push_end` and `Tree::append_right_leaf` propagated the radix marker
(`sizes = None`) when extending the right spine, even when the appended chunk
was a *partial* leaf. `Vector::concat` hits this through `normalize_tree` when
it folds a partial tail into the tree to make room for the other vector's tail,
producing a `Node(_, None)` that radix indexing wrongly treats as full. The
result: iteration stayed correct but `get`/`at`/`set` indexed out of bounds.

A right-spine append keeps a node radix only when every leaf stays full, i.e.
the appended leaf is itself full (`delta == BRANCHING_FACTOR`). Otherwise the
touched nodes must carry an explicit sizes array. `push_end` always appends a
single value (a partial leaf), so it now always relaxes; `append_right_leaf`
keeps the radix fast path for the full-leaf case used by `push`, and relaxes via
`compute_sizes` otherwise. This covers both the new-branch path and the
spine-absorbed path (a partial leaf can land in a short left-packed subtree).

`new_branch_left` also wrapped a partial leaf in radix (`None`) nodes. On its
own such a node is fine (the partial leaf is at the right edge), but a later
full-leaf `push` wou... (continued)

Coverage Stats

18 of 34 new or added lines in 2 files covered. (52.94%)

2 existing lines in 2 files now uncovered.

15337 of 16796 relevant lines covered (91.31%)

195725.96 hits per line