1371 Commits
Author SHA1 Message Date
Doug Gregor 3b10d15a65 Merge pull request #848 from sandeepvijayarao09/fix-trailing-array-throwing-init
[TrailingElements] Don't deinitialize elements when the initializer throws
2026-11-21 14:50:19 -08:00
Karoy Lorentey 43803b742a Merge pull request #870 from yuvrajtiwary-bitmesraece/bitarray-shift-int-min
[BitCollections] Don't trap in BitArray shifts when the amount is Int.min
2026-11-18 12:08:01 -08:00
Karoy Lorentey 68388f097f Merge pull request #858 from sandeepvijayarao09/fix-rope-distance-shared-leaves
[Rope] Don't take the same-leaf fast path in distance(from:to:in:) for shared leaves
2026-11-18 12:07:44 -08:00
Yuvraj TiwaryandClaude Fable 5.2 09d8daf0b5 [BitCollections] Don't trap in BitArray shifts when the amount is Int.min
`maskingShiftLeft(by:)`, `maskingShiftRight(by:)` and
`resizingShiftLeft(by:)` handle a negative amount by negating it and
shifting the other way, so `Int.min` trapped with an arithmetic
overflow. All three have a defined result for it: an amount of at least
`count` clears or removes every value, which is what `Int.min + 1`
already did.

Clamp the magnitude of a negative amount to `Int.max` in these three.
`resizingShiftRight(by:)` is left alone: a negative amount inserts
values there, and no array can hold as many as `Int.min` asks for.

The masking shifts had no tests. Add tests for both of them over
word-crossing counts and amounts on either side of `count`, for their
doc examples, and for the extreme amounts.

Co-Authored-By: Claude Fable 5.2 <noreply@anthropic.com>
2026-11-18 12:00:05 +05:30
Karoy Lorentey 8c409d4e06 [RigidDictionary] Deallocate values buffer on deinit (#869)
Oops, empty RigidDictionary instances leaked their values buffers on deinit.
2026-11-17 20:51:22 -08:00
Karoy Lorentey a06a54fe39 [RigidDictionary] Deallocate values buffer on deinit
Oops, empty RigidDictionary instances leaked their values buffers on deinit.
2026-11-17 14:59:40 -08:00
Sandeep Vijayarao 503047e77a [Rope] Don't take the same-leaf fast path in distance(from:to:in:) for shared leaves
A rope may contain the same leaf node at multiple positions (e.g. after
appending a rope to itself, or inserting a BigString slice into its own
base). Rope.distance(from:to:in:) assumed that two indices with the same
cached leaf reference address the same position in the tree, and returned
a distance computed only from their leaf slots. Also compare the paths
above the leaf level before taking the fast path.

This made BigString's character/scalar/UTF-16 distances and
index(_:offsetBy:) return wrong results (including indices with a bogus
utf8Offset) after such operations.
2026-11-16 18:50:37 -08:00
SandeepVijayarao 86da5fc128 Merge pull request #846 from sandeepvijayarao09/fix-bitset-bitpattern-negative
[BitCollections] Don't keep sign extension bits in BitSet(bitPattern:)
2026-11-16 14:27:24 -08:00
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 24bb9e4610 Merge pull request #855 from unaltolga/fix-hashed-containers-sendable
[BasicContainers] Make the hashed containers Sendable
2026-11-16 14:07:16 -08:00
Karoy Lorentey af94796d89 Merge pull request #850 from 0z5a/fix/hash-tree-bottom-collision-removal
[HashTreeCollections] Don't read hash buckets below the last hash level
2026-11-16 14:06:43 -08:00
Karoy Lorentey 10e81940b1 HashTreeCollection._HashNode: Use immortal empty singleton 2026-11-16 11:36:29 -08:00
Karoy Lorentey 8f033f1450 MutableContainer.updateElements: Keep consistent with MutableSpan proposal 2026-11-16 11:35:33 -08:00
Tolga Unal c211bc56af [BasicContainers] Make the hashed containers Sendable
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.
2026-11-16 11:38:37 -05: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
Sandeep Vijayarao a46a543feb [TrailingElements] Don't deinitialize elements when the initializer throws
`TrailingArray.init(header:initializingTrailingElementsWith:)` created
the value with just its header, then ran the initializer. If the
initializer threw, the half-built value was destroyed, so `deinit`
deinitialized all `trailingCount` elements, even though the output span
had already deinitialized the ones it had initialized and the rest were
never initialized. `withTemporaryValue(header:initializingTrailingElementsWith:body:)`
had the same problem through the `defer` in `_withTemporaryValue`. With
non-trivial elements (e.g. class references) both crashed.

Initialize the trailing elements before creating the `TrailingArray`,
and if the initializer throws, only deinitialize the header (and free the
heap storage) before rethrowing.
2026-11-11 00:24:31 -08:00
Sandeep Vijayarao 1f4913eb96 [BitCollections] Don't trap on BitSet[members:] closed ranges ending at Int.max
`BitSet[members:]` resolved range expressions against
`Int.min ..< Int.max`. A closed range ending at `Int.max`
(`bits[members: ...Int.max]`, `bits[members: 0 ... Int.max]`) needs the
index after `Int.max`, so it trapped with "Index out of bounds", while
`..<Int.max` and `0...` worked.

Resolve against a small internal collection of all `Int` values whose
`index(after:)` saturates at `Int.max`. `Int.max` can never be a bit set
member, so `lower ... Int.max` resolving to `lower ..< Int.max` doesn't
change which members are selected. `BitSet.Counted[members:]` forwards
to `BitSet`, so it's fixed too.
2026-11-11 00:19:39 -08:00
Karoy Lorentey 88754449ab Merge pull request #845 from aashish254/codex/812-container-iterator-boundary
Fix ContainerIterator skip bounds
2026-11-10 11:16:20 -08:00
Karoy Lorentey 78be6a1820 Merge pull request #844 from SwastikTripathi/undeprecate-withkeys
[BasicContainers] Un-deprecate withKeys while keys is miscompiled
2026-11-10 11:15:53 -08:00
Karoy Lorentey 827fef0660 Merge pull request #817 from Joseph-Cursio/drainable-container-check
Add checkDrainableContainer and fix RigidArray's consumeLast recursion
2026-11-10 11:01:51 -08:00
Aashish fc11462e69 Fix ContainerIterator skip bounds 2026-11-09 21:42:36 +05:45
Swastik TripathiandClaude Opus 5.5 b0d9a5ebbb [BasicContainers] Un-deprecate withKeys while keys is miscompiled
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
2026-11-07 09:12:34 +05:30
Karoy Lorentey 8d0a2dfceb Deque: Make the empty singleton immortal 2026-11-06 16:06:08 -08:00
Sandeep Vijayarao 9a699a1952 [BasicContainers] Don't resolve the hole before shrinking in UniqueDictionary
Resolves the FIXME added in #836: when removing an entry through
`updateValue(forKey:with:)` triggers shrinking, there is no need to
restore the hash table's invariants first, since resizing rehashes every
item anyway.

Factor the part of `RigidDictionary._punchHole(at:)` that doesn't touch
the value slot into `_punchHole(withMovedValueAt:)`, and use it on the
shrink path of `UniqueDictionary._removeEntry(withMovedValueAt:)`, which
now mirrors `_removeValue(at:)`.
2026-11-05 18:54:31 -08:00
Karoy Lorentey 3f5e6e427b Merge branch 'main' into fix-unique-dictionary-closure-removal 2026-11-05 18:32:45 -08:00
Karoy Lorentey 1518b4eb3c Merge pull request #835 from sandeepvijayarao09/fix-memoized-value-bucket
[BasicContainers] Fix memoizedValue returning another key's value
2026-11-05 18:30:14 -08:00
Karoy Lorentey dbc1c194de Add performance FIXME 2026-11-05 18:29:11 -08:00
Sandeep Vijayarao 1735b98380 [BasicContainers] Fix double destroy in UniqueDictionary.updateValue(forKey:with:)
When the updater closure removes an existing entry (sets the value to
nil), `UniqueDictionary.updateValue(forKey:with:)` called
`_removeValue(at:)`. But the value had already been moved out of its
slot before calling the updater, and `_removeValue(at:)` moves it out
again and discards the result, destroying uninitialized memory. This
leads to crashes or memory corruption.

`RigidDictionary.updateValue(forKey:with:)` already handles this case
correctly, by deinitializing just the key and resolving the hole.

Add `UniqueDictionary._removeEntry(withMovedValueAt:)`, which does the
same and then shrinks storage under the same condition as
`_removeValue(at:)`, and use it for the removal path.
2026-11-05 18:17:48 -08:00
Karoy Lorentey 8b5cd1bb39 Remove misleading notes in docs
Co-authored-by: Karoy Lorentey <klorentey@apple.com>
2026-11-05 18:04:11 -08:00
Karoy Lorentey d804d39ca6 Work around optimizer bug in Swift 6.2 even harder 2026-11-05 17:57:03 -08:00
Sandeep VijayaraoandClaude Opus 5.5 c8cc9a7d4c [BasicContainers] Fix memoizedValue returning another key's value
`RigidDictionary._insertNew` (and `RigidSet._insertNew`) returned the
bucket reported by the hash table's `insertNew_Small`/`insertNew_Large`.
That is where the *last displaced* item ends up, not the new item: small
tables swap the new item into the middle and move the old middle item to
the end, and hashed tables do Robin Hood swaps along the probe sequence.
Whenever a swap happened, the returned bucket held some other entry.

`memoizedValue(forKey:_:)` on `RigidDictionary` and `UniqueDictionary`
returns a reference to the value at that bucket, so inserting a new key
often returned the value of a different key.

Track the first bucket the swapper writes the new item into, and return
that (or the final bucket if nothing was swapped). The hash table's own
return value is still used to initialize the displaced item, and its
other user (rehashing in `migrateItems_Large`) is unchanged.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
2026-11-05 17:51:08 -08:00
Karoy Lorentey daeac4ebb8 Stop catering to toolchains older than Swift 6.2 2026-11-05 17:40:50 -08:00
Karoy Lorentey a99833003c Work around optimizer bug in Swift 6.2 (memory leaks due to miscompiled bulk deinitialization) 2026-11-05 17:40:46 -08:00
Karoy Lorentey c4562ee2c1 Work around miscompilation issue with Ref to non-@addressable borrows 2026-11-05 16:49:20 -08:00
Karoy Lorentey f17980c2c5 Stop using @_addressableForDependencies 2026-11-05 16:29:46 -08:00
Karoy Lorentey 71893e4144 Resolve strict memory safety warnings with UnstableHashedContainers trait 2026-11-05 14:23:27 -08:00
Karoy Lorentey f7952f9e34 Merge pull request #830 from unaltolga/fix-unique-deque-iterable
[DequeModule] Make UniqueDeque Iterable without ContainersPreview
2026-11-05 14:13:21 -08:00
Karoy Lorentey 54086ee4f2 Merge pull request #829 from sandeepvijayarao09/fix-sorted-dictionary-modify-root
[SortedCollections] Collapse an empty root after removing a root key through _modify
2026-11-05 13:57:07 -08:00
Karoy Lorentey 13045ef84c Merge pull request #825 from sainadth/fix-heap-check-invariants-access
[Heap] Make _checkInvariants() public in internal checks builds
2026-11-05 13:40:49 -08:00
Karoy Lorentey 24b919a5ba Merge pull request #828 from lorentey/fix-permutable-container-algorithms
Fix some container algorithms
2026-11-05 13:40:23 -08:00
Tolga Unal 68fd4f2cc8 [DequeModule] Make UniqueDeque Iterable without ContainersPreview
842f125c removed the trait conditions around the Iterable APIs, but
UniqueDeque only got its conformance through Container in ContainersPreview.
RigidDeque had no underestimatedCount, so it was 0 through Iterable.
2026-11-05 09:09:48 -05:00
Sandeep Vijayarao 3a80514ab6 [SortedCollections] Collapse an empty root after removing a root key through _modify
UnsafeCursor.removeElement(hasValueHole:) only collapsed an empty root
inside the loop that walks up the cursor's path, which never runs when
the removed key is in the root. Removing such a key with d[key].take()
could leave the root as an internal node with no keys and one child.
Collapse the root after the loop so every path depth is covered.

Fixes #811
2026-11-04 19:17:52 -08:00
Karoy Lorentey 7b578e5bfb Review and fix filter implementations
- Define a separate `filter` result on Iterable vs BorrowingIteratorProtocol
- Fix handling of delimited iterators in Container.filter
- Add fixmes for throwing
- Inlinability and other small fixes
2026-11-04 18:28:38 -08:00
Tolga Unal 9927f05e42 [BasicContainers] Make UniqueDictionary Equatable and Hashable with noncopyable contents
73ec3d341 made the other containers conform to Equatable/Hashable with
noncopyable contents, but UniqueDictionary was missed. The Hashable
extensions of RigidDictionary were also missing `Key: ~Copyable`.
2026-11-04 19:29:14 -05:00
sainadth c9286ec384 [Heap] Make _checkInvariants() public in internal checks builds
`Heap._checkInvariants()` was `internal` when COLLECTIONS_INTERNAL_CHECKS
is defined but `public` otherwise, so code outside `HeapModule` compiled
normally and then failed in an internal checks build.

Make both declarations `public`, matching `OrderedSet`,
`OrderedDictionary`, `BitSet` and `BitArray`, and add a test that calls it
through a plain `import HeapModule`.

Fixes #813
2026-11-04 13:10:43 -06:00
Joseph CursioandClaude Opus 5.5 c1ff9b9063 Build RigidArray's consumeLast drain without recursing
RigidArray's _customConsumeLast(_:) hook called consumeLast(_:), but
RigidArray has no one-argument consumeLast of its own, so the call went
to DrainableContainer.consumeLast(_:), which starts by calling the
hook. Every call to consumeLast(_:) on a RigidArray, directly or
through generic code, recursed until the stack overflowed.

Have the hook check the count and return consumeSubrange(_:) over the
last n items directly, the way consumeLast(_:consumingWith:) does.

Fixes #814.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
2026-11-03 19:16:00 -06:00
Karoy Lorentey b14ab924a5 Fix PermutableContainer algorithms 2026-11-03 16:04:44 -08:00
e7d8cd2203 [ContainersPreview] Fix append(copying:) recursion and wrapped insert(copying:at:) (#819)
* [ContainersPreview] Fix append(copying:) recursion and wrapped insert(copying:at:)

The RangeReplaceableContainer extension's append(copying:) passed a
contiguous source's buffer back to itself and never returned.
_insertCollection copied the whole buffer on every initializer call, which
trapped when a deque's gap wrapped around the end of its storage. Copy only
what fits on each call, as replaceSubrange(_:copying:) already does.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

* Delete Tests/DequeTests/RangeReplaceableContainerCopyingTests.swift

Let's drop the tests for now; we'll need a less involved way to exercise such algorithms.

---------

Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
Co-authored-by: Karoy Lorentey <klorentey@apple.com>
2026-11-03 14:57:43 -08:00
Karoy Lorentey 5bb5daddbb Merge pull request #807 from SwastikTripathi/docs-examples
Fix doc comment examples in OrderedDictionary, BitArray and SortedDictionary
2026-11-03 14:22:34 -08:00
Karoy Lorentey 9d026ae383 Merge pull request #808 from HuzaifaChaudary/fix/bitarray-wide-signed-conversion
[BitCollections] sign extend BitArray conversions to integers wider than a word
2026-11-03 14:22:18 -08:00