Files
Nikhil Gupta ab29aa793d [HashTreeCollections] Fix union misplacing items pushed into a new child
`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`.
2026-09-25 14:11:23 +05:30

114 lines
3.6 KiB
Swift

//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Collections open source project
//
// Copyright (c) 2022 - 2026 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
// SPDX-License-Identifier: Apache-2.0 WITH Swift-exception
//
//===----------------------------------------------------------------------===//
extension _HashNodeHeader {
#if COLLECTIONS_INTERNAL_CHECKS
@usableFromInline @inline(never)
internal func _invariantCheck() {
precondition(bytesFree <= byteCapacity)
if isCollisionNode {
precondition(itemMap == childMap)
precondition(!itemMap.isEmpty)
} else {
precondition(itemMap.intersection(childMap).isEmpty)
}
}
#else
@inlinable @inline(__always)
internal func _invariantCheck() {}
#endif
}
extension _HashNode {
#if COLLECTIONS_INTERNAL_CHECKS
@usableFromInline @inline(never)
internal func _invariantCheck() {
raw.storage.header._invariantCheck()
read {
let itemBytes = $0.itemCount * MemoryLayout<Element>.stride
if $0.isCollisionNode {
let hashBytes = MemoryLayout<_Hash>.stride
assert($0.itemCount >= 1)
assert($0.childCount == 0)
assert(itemBytes + $0.bytesFree + hashBytes == $0.byteCapacity)
assert($0.collisionHash == _Hash($0[item: .zero].key))
} else {
let childBytes = $0.childCount * MemoryLayout<_HashNode>.stride
assert(itemBytes + $0.bytesFree + childBytes == $0.byteCapacity)
}
let actualCount = $0.children.reduce($0.itemCount, { $0 + $1.count })
assert(actualCount == self.count)
}
}
#else
@inlinable @inline(__always)
internal func _invariantCheck() {}
#endif
@inlinable @inline(__always)
public func _fullInvariantCheck() {
self._fullInvariantCheck(.top, .emptyPath)
}
#if COLLECTIONS_INTERNAL_CHECKS
@inlinable @inline(never)
internal func _fullInvariantCheck(_ level: _HashLevel, _ path: _Hash) {
_invariantCheck()
read {
precondition(level.isAtRoot || !hasSingletonItem)
precondition(!isAtrophied)
if $0.isCollisionNode {
precondition(count == $0.itemCount)
precondition(count > 0)
let hash = $0.collisionHash
precondition(
hash.isEqual(to: path, upTo: level),
"Misplaced collision node: \(path) isn't a prefix of \(hash)")
for item in $0.reverseItems {
precondition(_Hash(item.key) == hash)
}
} else {
// Note: collision nodes store their item count in `itemMap`/`childMap`
// rather than a set of occupied buckets, so the loop below is only
// meaningful for regular nodes.
var itemSlot: _HashSlot = .zero
var childSlot: _HashSlot = .zero
for b in 0 ..< UInt(_Bitmap.capacity) {
let bucket = _Bucket(b)
let path = path.appending(bucket, at: level)
if $0.itemMap.contains(bucket) {
let key = $0[item: itemSlot].key
let hash = _Hash(key)
precondition(
hash.isEqual(to: path, upTo: level.descend()),
"Misplaced key '\(key)': \(path) isn't a prefix of \(hash)")
itemSlot = itemSlot.next()
}
if $0.hasChildren && $0.childMap.contains(bucket) {
$0[child: childSlot]._fullInvariantCheck(level.descend(), path)
childSlot = childSlot.next()
}
}
}
}
}
#else
@inlinable @inline(__always)
internal func _fullInvariantCheck(_ level: _HashLevel, _ path: _Hash) {}
#endif
}