32 Commits
Author SHA1 Message Date
Karoy Lorentey e110089b7c Merge pull request #856 from lorentey/small-fixes
An assortment of minor fixes
2026-11-16 14:07:33 -08:00
Karoy Lorentey 10e81940b1 HashTreeCollection._HashNode: Use immortal empty singleton 2026-11-16 11:36:29 -08:00
0z5a 0183be558f [HashTreeCollections] Don't read hash buckets below the last hash level
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.
2026-11-13 08:53:29 +01:00
Karoy Lorentey 9e7949017a Tests: add unsafe keywords where needed 2026-10-01 11:44:47 -07:00
Karoy Lorentey d07dc32dfa Sources: Add unsafe keywords where needed 2026-10-01 11:14:29 -07:00
Karoy Lorentey 5448b9cdb1 Delete distracting comments
Co-authored-by: Karoy Lorentey <klorentey@apple.com>
2026-09-25 13:47:08 -07:00
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
Alejandro Alonso d6c0fe063e Remove references to ManagedBuffer.capacity and use the given minCapacity
Fix errors

Update Deque._UnsafeHandle.swift
2026-08-12 14:09:05 -07:00
Karoy Lorentey 8380ca41da Merge pull request #682 from lorentey/container-updates
[ContainersPreview] Update Container protocols
2026-07-22 13:08:25 -07:00
Karoy Lorentey 00ffe8caec [HashTreeCollections] Avoid parsing issue with func read
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 }`.
2026-07-07 14:18:09 -07:00
Your NameandClaude Opus 4.8 259b4d52c2 Fix @inlinable deinit incompatibility with library evolution
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>
2026-06-29 16:15:00 +05:30
Karoy Lorentey 0ede027242 [HashTreeCollections] Fix invariant violation in some operations
The two-child variant of _HashNode._regularNode did not check bucket ordering before placing children, leading to inaccessible nodes half of the time.
2026-04-30 17:42:27 -07:00
Karoy Lorentey 1c69635852 Add SPDX-License-Identifier tags 2026-03-05 19:39:24 -08:00
Karoy Lorentey d9b09ecde8 Update copyright dates 2026-03-05 19:39:20 -08:00
Karoy Lorentey 099aa3b312 [BasicContainers] Add UniqueSet 2026-02-18 22:05:22 -08:00
Karoy Lorentey fdaf3fe24c [RigidArray, HashTrees] Mark deinitializers inlinable 2026-01-26 10:22:59 -08:00
Karoy Lorentey 3e306a23f1 Merge pull request #550 from AZero13/typo
Typo: symmetric difference should be the xor, not intersection
2025-12-17 16:16:09 -08:00
AZero13 174b3135c3 Compare self.value to other, not itself. 2025-12-06 13:13:09 -05:00
AZero13 3534960194 Typo: symmetric difference should be the xor, not intersection
Otherwise it is the same as the intersection.
2025-12-06 12:50:59 -05:00
Karoy Lorentey a09d7cdf45 Drop support for the Swift 5.9.* toolchains 2025-05-16 13:05:36 -07:00
3405691582andKaroy Lorentey 29cdb59bf9 Update Sources/HashTreeCollections/HashNode/_HashTreeStatistics.swift
Co-authored-by: Karoy Lorentey <klorentey@apple.com>
2025-05-16 00:21:38 -07:00
3405691582 8bbbe287c3 ManagedBuffer.capacity is unavailable on OpenBSD.
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.
2025-05-16 00:21:24 -07:00
Karoy Lorentey 755c06dd88 Adopt _pointerBitWidth 2024-09-25 14:17:32 -07:00
Karoy Lorentey 28f66a0ce5 Mark empty singletons as nonisolated(unsafe) 2024-09-25 14:06:31 -07:00
Karoy Lorentey 35d5746117 Rename _CollectionsUtilities to InternalCollectionsUtilities
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.
2024-05-29 14:00:13 -07:00
Dimitris Apostolou 7539583245 Fix typos
# Conflicts:
#	Sources/SortedCollections/BTree/_BTree+BidirectionalCollection.swift
#	Sources/SortedCollections/BTree/_BTree+UnsafeCursor.swift
#	Sources/SortedCollections/BTree/_BTree.Builder.swift
#	Sources/SortedCollections/BTree/_BTree.swift
#	Sources/SortedCollections/BTree/_Node.Splinter.swift
#	Sources/SortedCollections/BTree/_Node.Storage.swift
#	Sources/SortedCollections/BTree/_Node.UnsafeHandle+Insertion.swift
#	Sources/SortedCollections/BTree/_Node.swift
#	Tests/SortedCollectionsTests/BTree/Node+Join Tests.swift
2024-02-06 15:52:26 -08:00
Karoy Lorentey c33444df6f [HashTreeCollections] Update copyright notices 2024-02-02 16:20:20 -08:00
Karoy Lorentey d1e52208a3 [HashTreeCollections] Modernize declaration syntax of generic functions; adopt _specialize(_:for:) 2024-02-02 16:20:19 -08:00
Karoy Lorentey 9436aab34c [HashTreeCollections] _StorageHeader.swift → _HashNodeHeader.swift 2023-10-18 15:52:05 -07:00
Karoy Lorentey 454c84b5e4 Make most of Rope inlinable 2023-04-10 16:56:30 -07:00
Karoy Lorentey cbab9e3737 Introduce COLLECTIONS_SINGLE_MODULE condition 2023-03-21 18:42:33 -07:00
Karoy Lorentey 424c8ece98 HashTreeCollections: Qualify internal type names with “Hash”
This makes them unique throughout the package, allowing this code to be built as a single, huge module.
2023-03-21 16:37:22 -07:00