230 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
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
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
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
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
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
Karoy Lorentey bbdd37ada7 Fix a variety of issues in the nextSpan/previousSpan method family 2026-10-21 19:56:55 -07:00
Karoy Lorentey 1522a8a85d RigidArray, UniqueArray: Deprecate ancient span methods 2026-10-21 19:39:43 -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 24339ad6a3 CMake: Remove obsolete references to source variables 2026-10-12 12:24:03 -07:00
Karoy Lorentey 1b936eda0b Disable strict memory safety on older toolchains
It would take too much effort to try to mitigate stdlib differences.

Fix low-hanging warnings, but turn off `.strictMemorySafety` on older toolchains by splitting the package manifest.
2026-10-01 13:40:27 -07:00
Karoy Lorentey d07dc32dfa Sources: Add unsafe keywords where needed 2026-10-01 11:14:29 -07:00
Karoy Lorentey c410b3cd3a Remove obsolete/disabled APIs 2026-09-29 15:41:06 -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 45e7f63387 Merge pull request #725 from eliorpom-cmd/fix-typos-20260918
Fix typos in documentation and comments
2026-09-21 12:54:16 -07:00
Karoy Lorentey 561d10ed84 Merge pull request #727 from lorentey/container-updates
Container: Reinstate requirement for Comparable indices
2026-09-21 11:01:37 -07:00
Karoy Lorentey b2424210b4 Container: Reinstate requirement for Comparable indices
I have a linked list prototype that can support comparable indices (and an O(1) `count`); accordingly, reinstate the requirement for index comparability. This eliminates a potential performance footgun for custom containers that define their own Index, as an incomparable index would make `func distance` 2x slower.
2026-09-21 10:41:46 -07:00
Elior Pommier cabf7390ce Fix typos in documentation and comments
Corrects 25 misspellings across DocC articles, design documentation and doc
comments. Prose only: no identifiers, no public API, no behaviour change.

| Typo | Correction | Count |
|---|---|---|
| `offseting` | `offsetting` | 7 |
| `valud` | `value` | 4 |
| `necessarilly` | `necessarily` | 3 |
| `recommmend` | `recommend` | 2 |
| `Mutablility` | `Mutability` | 1 |
| `childs` | `child's` | 1 |
| `constaints` | `constraints` | 1 |
| `destintion` | `destination` | 1 |
| `explan` | `explain` | 1 |
| `forcuses` | `focuses` | 1 |
| `ot` | `or` | 1 |
| `succcess` | `success` | 1 |
| `unqiue` | `unique` | 1 |

Two of these are worth a second look, since they are not pure spelling:

- `_HTable+Removal.swift:18` reads "without marking it as unoccupied ot
  restoring the hash table's other invariants". Read as `or`, matching the
  sentence, and deliberately not as a prefix of `other` later on the line.
- `_Node.UnsafeHandle+Deletion.swift:369` reads "reuse the left childs node".
  Corrected to the possessive `child's` rather than `children`, which is what
  a plain spellchecker suggests but does not fit the sentence.

`valud` is corrected to `value` to match the wording of the equivalent
parameter documentation on `swapAt(_:_:)`.

One change is outside documentation: `CheckContainer.swift:476` fixes
`succcess` inside a test assertion message. It is a human-readable string, not
an expected value, so no test behaviour changes.

Deliberately left alone:

- `isDisjoint(with:)-54iy6` in `OrderedSet.md` is a DocC disambiguation hash,
  not a misspelling.
- `Peristent` in the 2022 ShareableHashedCollections review document, which is
  an archived record of a past review rather than living documentation.

Found with `typos-cli`, then reviewed by hand; the tool's raw output also
flagged identifiers and symbol hashes, which are not included here.
2026-09-18 14:31:47 +02: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 b2110d3563 Use single module conditional 2026-09-02 14:52:44 -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 225bd07e56 RigidSet, UniqueSet: Add Container conformance 2026-09-01 09:34:05 -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
Anton Karpov c2b2092f94 Name the documented arguments the way the declarations name them
Twenty-five doc comments in the shipping modules name an argument that the
declaration below them does not have, so DocC has nothing to bind the
description to and drops it. Nothing warns about this.

Most of them are renames that the comment did not follow, and the file itself
usually holds the proof: RigidDeque.prepend says - maxCount while its own
Complexity line already says newItemCount, and append(copying:) has three
overloads where the oldest still takes newElements and the two newer ones take
items with the older one's wording.

Three entries name an argument that no longer exists at all and are removed
rather than renamed.
2026-08-13 16:29:06 +03:00
Alejandro Alonso d44d6a3a26 Update UniqueArray+Append.swift 2026-08-12 15:04:38 -07:00
Alejandro Alonso 1b511f7652 Update UniqueArray+Append.swift 2026-08-12 14:07:15 -07:00
Alejandro Alonso 6c7ebb3cb9 Update UniqueArray+Append.swift 2026-08-12 13:32:38 -07:00
Alejandro Alonso dad98a58ca Replace inlinable with aEIC 2026-08-12 13:31:02 -07:00
Alejandro Alonso 4fd692f00b Apply review suggestions 2026-08-12 13:29:24 -07:00
Alejandro Alonso f2914d4fb4 Eliminate some duplicate bounds checks for UniqueArray 2026-08-12 12:25:12 -07:00
Alejandro Alonso b2a1f89cc6 Add mutableValue(forKey:) to new dictionary types 2026-08-10 17:48:13 -07:00
Karoy Lorentey 669eb09cea Use Iterable from the Standard Library, replacing the local definition 2026-07-27 13:32:46 -07:00