mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
`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`.
114 lines
3.6 KiB
Swift
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
|
|
}
|
|
|