Two keys with equal hashes whose hash also agrees with a third key on
every level except the last end up in a collision node that sits below
the last hash level. Removing one of the colliding keys (remove,
removeValue, subscript setter/_modify to nil, subtracting, filter,
symmetricDifference, ...) computed `hash[level]` for that node, which
trips the `assert(!level.isAtBottom)` in `_Hash.subscript` in debug
builds. Collision nodes don't use buckets, and parents replace the
bucket of an inlined child item with their own, so release builds were
not affected.
Skip the bucket lookup at the bottom level, the same way lookups in
`_findInCollision` already do.
`copyNodeAndPushItemIntoNewChild` takes an existing item out of `self` and
pushes it into `newChild`, which is then installed as a child of `self` at
`bucket`. `newChild` therefore sits one level below `self`, but the item was
inserted into it using `self`'s level:
let r = newChild.inserting(level, item, hash)
Navigating with the parent's level picks the wrong hash digit, so the item —
and the subtree it is merged with — end up filed under a path that doesn't
match their hash.
`TreeSet.union` reaches this when it merges an incoming collision node against
an item already occupying that bucket. The result is a set that still reports
the right `count` and still yields every element when iterated, but whose
misplaced members cannot be found by `contains`, since lookup navigates by
hash:
let a1 = RawCollider(1, "A")
let a2 = RawCollider(2, "B")
let c1 = RawCollider(5, "ACAD")
let c2 = RawCollider(6, "ACAD")
let u = TreeSet([a1, a2]).union(TreeSet([c1, c2]))
u.count // 4
Array(u) // [2#B, 1#A, 5#ACAD, 6#ACAD]
u.contains(c1) // false
u.contains(a1) // false
Building the same set directly with `TreeSet([a1, a2, c1, c2])` is unaffected;
only the structural merge paths are.
Insert at `level.descend()` instead.
Enumerating every pair of subsets of the shared `testItems` fixture, 171 of
4096 unions contained at least one member that `contains` could not find.
With this change all 4096 are clean.
Also fix the full invariant check, which could not run on any tree containing
a collision node. Collision nodes store their item count in `itemMap` and
`childMap` rather than a set of occupied buckets, so treating those bitmaps as
buckets walks items that aren't there — a node holding 5 items has
`itemMap._value == 5`, whose bits nominate buckets 0 and 2. The bucket loop now
only runs for regular nodes. Before this, `swift test
-Xswiftc -DCOLLECTIONS_INTERNAL_CHECKS` trapped immediately in
HashTreeCollections; that trap was also what kept the invariant check from
reporting the misplaced nodes above.
Add a regression test alongside the existing `test_union_collision_node_ordering`.
When the BorrowAndMutateAccessors feature is enabled, this code appears to be parsed as if it declared a `read` accessor, rather than a getter passing a closure to the `read` function:
```swift
@inlinable
internal var collisionHash: _Hash {
read { $0.collisionHash }
}
```
Avoid this by adding a `self` prefix, as in `self.read { $0.collisionHash }`.
The `Storage` classes in HashTreeCollections and SortedCollections mark
their `deinit` as `@inlinable` but lack `@_fixed_layout`. Under library
evolution (BUILD_LIBRARY_FOR_DISTRIBUTION=YES), Swift 6.2+ rejects this
with "deinitializer can only be '@inlinable' if the class is
'@_fixed_layout'", because inlining a deinit requires a known layout that
resilient mode deliberately hides.
This mirrors the existing fix already applied to the equivalent storage
classes in DequeModule (_DequeBuffer) and RopeModule (Rope._Storage). As
noted there, this does not make anything ABI stable -- these storage
classes are @usableFromInline internal and never part of the public ABI
surface -- it only lets these modules build with library evolution
enabled.
Fixes#676.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
ManagedBuffer.capacity depends on malloc introspection (e.g.,
`malloc_size`), which is not available on this platform -- and is thus
marked as such.
Here, _HashNode.Storage is a ManagedBuffer. Thankfully, the uses of
.capacity are fairly limited: one for statistic purposes, which we just
completely omit on the platform, and the other, setting a minimum
capacity in the header by the buffer's .capacity; the alternative being
setting that minimum capacity directly.
We are forced to do this due to an Xcode issue (#364) with underscored module names.
This module remains unstable, despite the removal of the underscore. Directly importing it from outside the package remains unsupported. This module and/or its entire contents may go away or change in incompatible ways in any future swift-collections release.