`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>
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.
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.
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.
`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.
`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.
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:)`.
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.
`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>
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.
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
- 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
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`.
`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
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>
* [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>