115 Commits
Author SHA1 Message Date
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
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 ddf1a48382 [test] Fix strict memory safety warnings 2026-11-16 11:37:39 -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
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
Karoy Lorentey 612865a2d0 Merge pull request #823 from Joseph-Cursio/fix-816-permutable-noncopyable
Add checkPermutableContainer
2026-11-10 11:01:28 -08:00
Karoy Lorentey de714531cf Merge pull request #837 from sandeepvijayarao09/hashed-containers-fuzz-tests-v2
[BasicContainers] Add differential fuzz tests for the hashed containers
2026-11-06 14:33:11 -08:00
Sandeep Vijayarao ebc8757bd3 Guard the memoizedValue fuzz steps with #available
`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.
2026-11-06 03:35:03 -08:00
Swastik TripathiandClaude Opus 5.5 d3f3684195 [BasicContainers] Mark the new memoizedValue tests as SwiftStdlib 6.4
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>
2026-11-06 13:40:07 +05:30
Sandeep Vijayarao b2f5535d27 [BasicContainers] Add differential fuzz tests for the hashed containers
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.
2026-11-05 18:51:15 -08:00
Karoy Lorentey 3f5e6e427b Merge branch 'main' into fix-unique-dictionary-closure-removal 2026-11-05 18:32:45 -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
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
Joseph CursioandClaude Opus 5.5 476fdaff1b Check OutputSpan with checkPermutableContainer
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>
2026-11-05 16:48:47 -06:00
Joseph CursioandClaude Opus 5.5 71d10cd2f4 Check InputSpan with checkPermutableContainer
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>
2026-11-05 16:48:47 -06:00
Joseph CursioandClaude Opus 5.5 8275b719e3 Check UniqueArray with checkPermutableContainer
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>
2026-11-05 16:48:47 -06:00
Joseph CursioandClaude Opus 5.5 a9967e32eb Check MutableSpan with checkPermutableContainer
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>
2026-11-05 16:48:47 -06:00
Joseph CursioandClaude Opus 5.5 69a2d15395 Check RigidArray with checkPermutableContainer
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>
2026-11-05 16:48:47 -06: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
Karoy Lorentey f4966f7685 Move ArrayLayout to _CollectionsTestSupport 2026-11-04 18:28:30 -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
Joseph CursioandClaude Opus 5.5 fe90f11c44 Check UniqueArray with checkDrainableContainer
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>
2026-11-03 19:16:39 -06:00
Joseph CursioandClaude Opus 5.5 204d1ae40c Check RigidArray with checkDrainableContainer
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>
2026-11-03 19:16:33 -06:00
Joseph CursioandClaude Opus 5.5 d1f377cb2d Check UniqueArray with checkMutableContainer
Run the mutable container checker, which also runs the bidirectional
one, against UniqueArray.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
2026-10-27 04:51:50 -05:00
Joseph CursioandClaude Opus 5.5 bfc228d7b7 Check RigidArray with checkMutableContainer
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>
2026-10-27 04:51:50 -05:00
Karoy Lorentey e13f175180 Review RigidDeque/UniqueDeque tests; add better tests for prepends 2026-10-26 18:01:57 -07:00
SwastikTripathi 0b51424337 Merge pull request #794 from SwastikTripathi/fix/borrowing-map-skip-infinite-loop
[BorrowingMapProducer] Fix skip(by:) hanging at end of iterator
2026-10-22 11:02:24 -07:00
Karoy Lorentey bbdd37ada7 Fix a variety of issues in the nextSpan/previousSpan method family 2026-10-21 19:56:55 -07:00
Karoy Lorentey 83e5f26fba Merge pull request #782 from aashish254/fix-774-rigidset-insert-hang
[BasicContainers] Fix RigidSet/UniqueSet batch insertion never terminating without the preview trait
2026-10-21 16:33:58 -07:00
Karoy Lorentey 4d092451ef Merge pull request #781 from aashish254/fix-772-replace-subrange-returned-range
[BasicContainers] Fix returned range of replaceSubrange(_:addingCount:initializingWith:)
2026-10-21 16:33:43 -07:00
Karoy Lorentey 1209f9e410 Merge pull request #776 from aniketatgithub/fix-771-uniquearray-append-moving
[BasicContainers] Fix UniqueArray.append(moving:) dropping and leaking every element
2026-10-21 16:33:17 -07:00
Aashish bd5960886c [BasicContainers] Fix RigidSet batch-insertion loop never terminating
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).
2026-10-20 21:18:09 +05:45
Aashish 96648ca1d8 Fix replaceSubrange(_:addingCount:initializingWith:) returning a range sized by the requested count
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
2026-10-20 19:45:05 +05:45
Aniket 80d8052b4b [BasicContainers] Fix UniqueArray.append(moving:) dropping and leaking every element
Signed-off-by: Aniket <aniketkomailkro@gmail.com>
2026-10-17 02:21:15 -07:00
Joseph CursioandClaude Opus 5.5 c65469e45f Fix RigidSet.hash(into:) never returning
_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>
2026-10-15 07:29:43 -05:00
Karoy Lorentey 9e7949017a Tests: add unsafe keywords where needed 2026-10-01 11:44:47 -07:00
Karoy Lorentey 44b674265c Update import statements 2026-09-29 15:41:05 -07:00
Karoy Lorentey f1e675acd2 Turn off BorrowingIteratorProtocol.next()
The reference to `Ref` appears to trigger a broken strong linkage to `_swift_initBorrow`, despite the code being only available on macOS/iOS/etc 27.
2026-09-25 15:01:04 -07:00
Karoy Lorentey 9bf8a9763b Merge pull request #729 from lorentey/release-prep
1.7.0 release preparations
2026-09-22 12:42:05 -07:00
Karoy Lorentey 537bf9cbfb Drop support for Swift 6.0 and 6.1
This allows the use of Span types without `#if compiler` guards.
2026-09-21 13:34:39 -07:00
Karoy Lorentey 8e4f078441 Producer.generate(into:): Switch to saturating semantics
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:)`.
2026-09-21 13:07:01 -07:00
Karoy Lorentey f5db7175b3 Merge pull request #724 from lorentey/container-updates
MutableContainer: Add some bulk update operations
2026-09-21 10:10:34 -07:00
Karoy Lorentey d392f0cbff MutableContainer: Add tests; resolve issues uncovered 2026-09-21 09:54:29 -07:00
Karoy Lorentey 3ceaf1ac39 Merge pull request #723 from lorentey/container-updates
Refactor DrainableContainer/RangeReplaceableContainer/DynamicContainer
2026-09-16 13:40:56 -07:00
Karoy Lorentey 5cebba6f29 Refactor DrainableContainer/RangeReplaceableContainer/DynamicContainer
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(_:)`.
2026-09-14 20:37:12 -07:00
Alejandro Alonso e773108091 Make RigidDictionary store a sentinel value for values ptr if null 2026-09-02 14:25:00 -07:00
Karoy Lorentey 1f94ac8f54 Implement (partial) Container validation 2026-09-01 10:14:42 -07:00
Karoy Lorentey 842f125c47 Invert dependencies to ContainersPreview, moving all container APIs there
- 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.
2026-08-25 18:29:58 -07:00
Alejandro Alonso b2a1f89cc6 Add mutableValue(forKey:) to new dictionary types 2026-08-10 17:48:13 -07:00