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.
`memoizedValue(forKey:_:)` and `Ref.value` need SwiftStdlib 6.4, so the
fuzz tests failed to compile on macOS with the UnstableHashedContainers
trait (CI only enables that trait on Linux). Skip just that operation
on older platforms instead of marking the whole tests unavailable.
test_memoizedValue_returnsNewlyInsertedValue in RigidDictionaryTests and
UniqueDictionaryTests calls memoizedValue(forKey:_:), which needs
SwiftStdlib 6.4, but the tests had no availability attribute. With the
UnstableHashedContainers trait on macOS, BasicContainersTests failed to
build ("'memoizedValue(forKey:_:)' is only available in macOS 27.0 or
newer"). Add the same @available attribute test_memoizedValue_one uses.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Run random sequences of operations on RigidSet, UniqueSet,
RigidDictionary and UniqueDictionary, and after each step compare them
against a standard Set/Dictionary model: count, contents (via index
iteration), positive and negative lookups, and `_checkInvariants()`.
The operations cover insert/update/remove, the closure form of
`updateValue(forKey:with:)`, `memoizedValue(forKey:_:)`, `reallocate`/
`reserveCapacity`, `removeAll` (with and without keeping capacity),
Rigid <-> Unique conversions via `init(consuming:)`, and `_consumeAll`.
Keys use a configurable number of distinct hash values, from no
collisions down to a single collision chain, and all elements are
lifetime-tracked to catch leaks and double destroys.
These tests found the bugs fixed in #835 and #836.
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>
Also run the permutable container checker against an OutputSpan, over the
same layouts as RigidArray.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Also run the permutable container checker against an InputSpan, over the
same layouts as RigidArray. InputSpan.swapAt(_:_:) is the only span
implementation of swapAt in this package, and a no-op version of it
passes every other test.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Run the permutable container checker against UniqueArray, over arrays of
up to ten items, full and with spare capacity.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Also run the permutable container checker against the mutable span of a
RigidArray, over the same layouts. MutableSpan is nonescapable, so this
also runs the checker on a nonescapable container.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Run the permutable container checker against RigidArray, over arrays of
up to ten items, full and with spare capacity.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
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`.
Run the drainable container checker against UniqueArray, over arrays of
up to six items, full and with spare capacity. UniqueArray doesn't
override the _customConsumeLast(_:) hook, so it passes with #814's fix
reverted.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Run the drainable container checker against RigidArray, over arrays of
up to six items, full and with spare capacity. With #814's fix
reverted, the test crashes on its first consumeLast(_:) call, with
DrainableContainer.consumeLast(_:) and RigidArray._customConsumeLast(_:)
calling each other until the stack overflows.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Run the mutable container checker, which also runs the bidirectional
one, against RigidArray. With #793's nextMutableSpan fix reverted, it
fails with the index not advancing.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
insert(addingCount:initializingWith:) batches elements through a
temporary OutputSpan and loops while `remainder > 0`. When the
`UnstableContainersPreview` trait is disabled, the span's `defer`
handler moved elements out of the temporary buffer but never decremented
`remainder`, so the loop spun forever whenever the initializer didn't
fill every batch. Update `remainder` the same way the preview branch
already does, and add a regression test (issue #774).
The closure-based replaceSubrange overloads on RigidArray (and, through
them, UniqueArray and the generic RangeReplaceableContainer overloads)
returned subrange.lowerBound ..< subrange.lowerBound + newItemCount even
when the initializer performed a short fill, so the returned range could
cover old elements that were never replaced and extend past endIndex.
Return the number of items actually initialized (span.count), matching
insert(addingCount:at:initializingWith:).
Fixes#772
_rawHashValue(seed:) looped on nextSpan() without checking for the
empty span the iterator returns once it is exhausted, so hashing any
RigidSet or UniqueSet spun forever. Break on an empty span, as == does.
Add test_hashable for both types, modeled on RigidArrayTests: equal
sets built with different capacities and insertion orders must hash
equally. Both tests hang without the fix.
Fixes#765.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
This noticeable simplifies client code, as clients invariably want to fully populate their buffer (when possible). It also is consistent with the semantics of `Iterable.skip(by:)`.
Range replacement operations generally need to invalidate all indices, and that means that we lose our position in the container after each insertion/removal, unless we happen to be using a container with looser index invalidation (such as arrays or deques).
A linked list is an example for a container type where insertions/removals need to invalidate all indices — as we need to track index validation using a single version counter that is stored in the list’s head. However, it would not be acceptable to lose our place whenever we insert a new item to the list; therefore, to mitigate the validation issue, this commit changes all range-replacement operations to return a valid index range to the affected items in the container.
This is a radical break from `RangeReplaceableCollection`. It fixes a long-standing defect with it, but it also makes it tricky to conform the same type to both protocol families, as the two require the “same” methods to return different types (`Void` vs `Range<Index>`).
Given that the LSG has intentionally diverged `UniqueArray.removeAll()` from RangeReplaceableCollection semantics, I expect this isn’t going to be an issue. For example, types with existing collection conformances can expose container views, mitigating such semantic differences.
To allow SubrangeConsumers to work without losing position, add a new protocol, `ContainerDrain` with a consuming `finalize` operation that returns a valid index in the resulting container state.
While we’re here, apply the API tweaks from SE-0527:
- Revert the `replace(removing:…:)` names, rolling back to `replaceSubrange(_:…:)` .
- Similarly, rename `consume(_:)` → `consumeSubrange(_:)`
- Rename `reallocate(capacity:)` → `setCapacity(_:)`.
- Move `InputSpan` into its own module, `SpanPreview`. Add dependencies to it.
- Invert dependencies to `ContainersPreview`, so that no production target imports it, but it now depends on its previous dependents.
- Move all generic APIs and conformances using `Producer`/`Drain`/`Container` to the `ContainersPreview` module.
- Remove `UnstableContainersPreview` conditions around `Iterable` APIs
In summary, importing `BasicContainers` and `DequeModule` continue to get us the basic definitions for `RigidArray`, `UniqueSet`, `RigidDeque` etc., without most of their unstable APIs. (With the exception of core APIs that require `InputSpan`.)
To get any API that uses an unstable protocol like `Container` or `Drain`, we’ll now need to import `ContainersPreview` in addition to the type-defining module.
This will provide a slightly less horrible migration path when (if) the container/producer protocol family gets adopted/adapted into the stdlib.