mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
RigidSet, UniqueSet, RigidDictionary and UniqueDictionary had no Sendable conformance, while the arrays and deques conform when their elements are Sendable. Add the same conditional conformances: unchecked for the rigid containers, which keep their elements behind unsafe pointers, and checked for the unique ones.
356 lines
11 KiB
Swift
356 lines
11 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Collections open source project
|
|
//
|
|
// Copyright (c) 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
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
import XCTest
|
|
#if COLLECTIONS_SINGLE_MODULE
|
|
import Collections
|
|
#else
|
|
import _CollectionsTestSupport
|
|
import InternalCollectionsUtilities
|
|
import BasicContainers
|
|
#endif
|
|
import ContainersPreview
|
|
|
|
#if compiler(>=6.4) && UnstableHashedContainers
|
|
class UniqueSetTests: CollectionTestCase {
|
|
func test_memory_layout() {
|
|
let word = MemoryLayout<Int>.size
|
|
expectEqual(MemoryLayout<UniqueSet<Int>>.stride, 6 * word)
|
|
expectEqual(MemoryLayout<UniqueSet<Int>?>.stride, 6 * word)
|
|
}
|
|
|
|
func test_sendable_conformance_static() {
|
|
// Compile-time assertion: UniqueSet conforms to Sendable when its contents do.
|
|
func requireSendable<T: Sendable & ~Copyable>(_ type: T.Type) {}
|
|
requireSendable(UniqueSet<Int>.self)
|
|
requireSendable(UniqueSet<String>.self)
|
|
}
|
|
|
|
func test_empty() {
|
|
let s = UniqueSet<Int>()
|
|
expectEqual(s.count, 0)
|
|
expectTrue(s.isEmpty)
|
|
expectTrue(s.isFull)
|
|
expectEqual(s.capacity, 0)
|
|
expectEqual(s.freeCapacity, 0)
|
|
}
|
|
|
|
func test_insert_one() {
|
|
withLifetimeTracking { tracker in
|
|
var s = UniqueSet<LifetimeTracked<Int>>()
|
|
let first = tracker.instance(for: 42)
|
|
expectNil(s.insert(first))
|
|
let second = tracker.instance(for: 42)
|
|
expectIdentical(s.insert(second), second)
|
|
|
|
expectTrue(s.contains(first))
|
|
expectTrue(s.contains(second))
|
|
_ = consume first
|
|
expectTrue(s.contains(second))
|
|
|
|
expectEqual(s.count, 1)
|
|
expectFalse(s.isEmpty)
|
|
expectGreaterThanOrEqual(s.capacity, 1)
|
|
}
|
|
}
|
|
|
|
func test_update_one() {
|
|
withLifetimeTracking { tracker in
|
|
var s = UniqueSet<LifetimeTracked<Int>>()
|
|
let first = tracker.instance(for: 42)
|
|
expectNil(s.update(with: first))
|
|
let second = tracker.instance(for: 42)
|
|
expectIdentical(s.update(with: second), first)
|
|
|
|
expectTrue(s.contains(first))
|
|
expectTrue(s.contains(second))
|
|
_ = consume second
|
|
expectTrue(s.contains(first))
|
|
|
|
expectEqual(s.count, 1)
|
|
expectFalse(s.isEmpty)
|
|
expectGreaterThanOrEqual(s.capacity, 1)
|
|
}
|
|
}
|
|
|
|
func test_init_minimumCapacity_growth() {
|
|
// These are the storage capacities we expect to see for a UniqueSet
|
|
// up to size 1000.
|
|
let expected = [0, 1, 2, 4, 7, 14, 28, 56, 112, 224, 448, 896, 1792]
|
|
var actual: Set<Int> = []
|
|
|
|
// Check that we get the expected capacities for each size. UniqueSet
|
|
// should not prematurely allocate more than the size of the closest
|
|
// expected size.
|
|
var j = 0
|
|
withEvery("i", in: 0 ..< 1000) { i in
|
|
let set = UniqueSet<Int>(minimumCapacity: i)
|
|
if i > expected[j] {
|
|
j += 1
|
|
}
|
|
expectEqual(set.capacity, expected[j])
|
|
actual.insert(set.capacity)
|
|
}
|
|
expectEqual(actual.sorted(), expected)
|
|
}
|
|
|
|
func test_insert_many() {
|
|
let c = 1000
|
|
withLifetimeTracking { tracker in
|
|
var set = UniqueSet<LifetimeTracked<Int>>()
|
|
withEvery("i", in: 0 ..< c) { i in
|
|
let new = tracker.instance(for: i)
|
|
let remnant = set.insert(new)
|
|
expectNil(remnant)
|
|
expectEqual(set.count, i + 1)
|
|
expectTrue(set.contains(new))
|
|
}
|
|
expectEqual(set.count, c)
|
|
expectFalse(set.isEmpty)
|
|
expectGreaterThanOrEqual(set.capacity, c)
|
|
|
|
withEvery("j", in: 0 ..< c) { j in
|
|
let dupe = tracker.instance(for: j)
|
|
if set.contains(dupe) {
|
|
expectIdentical(set.insert(dupe), dupe)
|
|
} else {
|
|
expectFailure("\(dupe.payload) not found")
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
func test_insert_growth() {
|
|
// These are the storage capacities we expect to see for a UniqueSet
|
|
// up to size 1000.
|
|
let expectedCapacities = [
|
|
0, 1, 2, 4, 7, 14, 28, 56, 112, 224, 448, 896, 1792
|
|
]
|
|
var j = 0
|
|
|
|
var set = UniqueSet<Int>()
|
|
expectEqual(set.capacity, expectedCapacities[j])
|
|
|
|
withEvery("i", in: 1 ..< 1000) { i in
|
|
set.insert(i)
|
|
if i > expectedCapacities[j] {
|
|
j += 1
|
|
}
|
|
expectEqual(set.capacity, expectedCapacities[j])
|
|
}
|
|
}
|
|
|
|
#if compiler(>=6.4) && UnstableContainersPreview
|
|
@available(SwiftStdlib 6.4, *)
|
|
func test_validate_Container() {
|
|
withEvery("count", in: [0, 10, 100, 1000]) { count in
|
|
withLifetimeTracking { tracker in
|
|
var items: UniqueSet<LifetimeTrackedStruct<Int>> = .init(minimumCapacity: count)
|
|
for i in 0 ..< count {
|
|
guard items.insert(tracker.structInstance(for: i)) == nil else {
|
|
expectFailure("Duplicate item \(i)")
|
|
return
|
|
}
|
|
}
|
|
|
|
// Get expected contents by iterating once.
|
|
var expected: [Int] = []
|
|
for v in items {
|
|
expected.append(v.payload)
|
|
}
|
|
|
|
checkContainer(
|
|
items,
|
|
expectedContents: expected,
|
|
by: { $0.payload == $1 })
|
|
}
|
|
}
|
|
}
|
|
#endif
|
|
|
|
func test_iteration_indexAfter() {
|
|
let c = 1000
|
|
withLifetimeTracking { tracker in
|
|
var s = UniqueSet<LifetimeTracked<Int>>()
|
|
withEvery("payload", in: 0 ..< c) { payload in
|
|
let item = tracker.instance(for: payload)
|
|
s.insert(item)
|
|
|
|
var seen: Set<Int> = []
|
|
var i = s.startIndex
|
|
while i != s.endIndex {
|
|
let payload = s[i].payload
|
|
expectTrue(seen.insert(payload).inserted, "Duplicate item \(payload)")
|
|
i = s.index(after: i)
|
|
}
|
|
expectEqual(seen.count, payload + 1)
|
|
}
|
|
}
|
|
}
|
|
|
|
func test_remove_one() {
|
|
withEvery("cap", in: [0, 1, 2, 4, 10, 100, 500]) { cap in
|
|
let scale = _HTable.minimumScale(forCapacity: cap)
|
|
let count = _HTable.minimumCapacity(forScale: scale)
|
|
withEvery("item", in: 0 ..< count) { item in
|
|
withLifetimeTracking { tracker in
|
|
var set = UniqueSet<LifetimeTracked<Int>>(minimumCapacity: cap)
|
|
expectEqual(set._scale, scale)
|
|
for i in 0 ..< count {
|
|
let instance = tracker.instance(for: i)
|
|
set.insert(instance)
|
|
}
|
|
expectEqual(set.count, count)
|
|
expectEqual(set._scale, scale)
|
|
|
|
let dupe = tracker.instance(for: item)
|
|
let removed = set.remove(dupe)
|
|
expectNotNil(removed) {
|
|
expectNotIdentical($0, dupe)
|
|
expectEqual($0.payload, item)
|
|
}
|
|
expectEqual(set.count, count - 1)
|
|
|
|
let expectedScale = _HTable.minimumScale(forCapacity: count - 1)
|
|
if scale > 0 {
|
|
expectLessThan(expectedScale, scale)
|
|
}
|
|
expectEqual(set._scale, expectedScale)
|
|
|
|
withEvery("j", in: 0 ..< count) { j in
|
|
let found = set.contains(tracker.instance(for: j))
|
|
expectEqual(found, j != item)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
func test_remove_all() {
|
|
withEvery("count", in: [0, 1, 2, 4, 10, 100, 1000]) { count in
|
|
withLifetimeTracking { tracker in
|
|
var set = UniqueSet<LifetimeTracked<Int>>(minimumCapacity: count)
|
|
for i in 0 ..< count {
|
|
let instance = tracker.instance(for: i)
|
|
set.insert(instance)
|
|
}
|
|
expectEqual(set.count, count)
|
|
|
|
withEvery("i", in: 0 ..< count) { i in
|
|
let dupe = tracker.instance(for: i)
|
|
let removed = set.remove(dupe)
|
|
expectNotNil(removed) {
|
|
expectNotIdentical($0, dupe)
|
|
expectEqual($0.payload, i)
|
|
}
|
|
expectEqual(set.count, count - 1 - i)
|
|
expectGreaterThanOrEqual(
|
|
set.count,
|
|
_HTable.minimumCapacity(forScale: set._scale))
|
|
}
|
|
expectEqual(set.count, 0)
|
|
}
|
|
}
|
|
}
|
|
|
|
func test_remove_shrinkage() {
|
|
let c = 1000
|
|
let expectedCapacities = [1792, 448, 112, 28, 4]
|
|
var set = UniqueSet<Int>(minimumCapacity: c)
|
|
for i in 0 ..< c {
|
|
set.insert(i)
|
|
}
|
|
var j = 0
|
|
expectEqual(set.capacity, expectedCapacities[j])
|
|
|
|
withEvery("i", in: 0 ..< c) { i in
|
|
let removed = set.remove(i)
|
|
expectEqual(removed, i)
|
|
expectEqual(set.count, c - i - 1)
|
|
if set.capacity != expectedCapacities[j], j < expectedCapacities.count - 1 {
|
|
j += 1
|
|
}
|
|
expectEqual(set.capacity, expectedCapacities[j])
|
|
}
|
|
}
|
|
|
|
func test_removeAll() {
|
|
withEvery("count", in: [0, 1, 2, 4, 10, 100, 1000]) { count in
|
|
withLifetimeTracking { tracker in
|
|
var set = UniqueSet<LifetimeTracked<Int>>()
|
|
for i in 0 ..< count {
|
|
let instance = tracker.instance(for: i)
|
|
set.insert(instance)
|
|
}
|
|
expectEqual(set.count, count)
|
|
|
|
set.removeAll()
|
|
expectEqual(set.count, 0)
|
|
expectEqual(set.capacity, 0)
|
|
}
|
|
}
|
|
}
|
|
|
|
func test_removeAll_keepingCapacity() {
|
|
withEvery("count", in: [0, 1, 2, 4, 10, 100, 1000]) { count in
|
|
withLifetimeTracking { tracker in
|
|
var set = UniqueSet<LifetimeTracked<Int>>()
|
|
for i in 0 ..< count {
|
|
let instance = tracker.instance(for: i)
|
|
set.insert(instance)
|
|
}
|
|
expectEqual(set.count, count)
|
|
|
|
set.removeAll(keepingCapacity: true)
|
|
expectEqual(set.count, 0)
|
|
expectGreaterThanOrEqual(set.capacity, count)
|
|
}
|
|
}
|
|
}
|
|
|
|
func test_hashable() {
|
|
let contents: [[Int]] = [[], [0], [1], [0, 1], [1, 0], [0, 1, 2], Array(0 ..< 50)]
|
|
withEvery("i", in: contents.indices) { i in
|
|
withEvery("j", in: contents.indices) { j in
|
|
var a = UniqueSet<Int>()
|
|
for item in contents[i] { a.insert(item) }
|
|
var b = UniqueSet<Int>(minimumCapacity: 100)
|
|
for item in contents[j].reversed() { b.insert(item) }
|
|
// FIXME: Use checkHashable when possible
|
|
var goodHash = false
|
|
for seed in 0 ..< 10 {
|
|
var ha = Hasher()
|
|
ha.combine(seed)
|
|
a.hash(into: &ha)
|
|
let hashValueA = ha.finalize()
|
|
|
|
var hb = Hasher()
|
|
hb.combine(seed)
|
|
b.hash(into: &hb)
|
|
let hashValueB = hb.finalize()
|
|
|
|
if Set(contents[i]) == Set(contents[j]) {
|
|
expectEqual(hashValueA, hashValueB)
|
|
goodHash = true
|
|
} else if hashValueA != hashValueB {
|
|
goodHash = true
|
|
}
|
|
}
|
|
expectTrue(goodHash, "Hashing does not differentiate between inequal containers")
|
|
}
|
|
}
|
|
}
|
|
|
|
}
|
|
#endif
|