40 Commits
Author SHA1 Message Date
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 d07dc32dfa Sources: Add unsafe keywords where needed 2026-10-01 11:14:29 -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
Karoy Lorentey 669eb09cea Use Iterable from the Standard Library, replacing the local definition 2026-07-27 13:32:46 -07:00
Karoy Lorentey ff695132ed Bump availability of Iterable_ and Container protocols to SwiftStdlib 6.4
This is preparing for switching over to the stdlib’s definition of `protocol Iterable`, assuming it will land with macOS 27/iOS 27 etc availability; `Container` is refining `Iterable`, so it needs matching availability.

If `Iterable` won’t ship in Swift 6.4, then we’ll need to bump this again.
2026-07-07 14:22:45 -07:00
Karoy Lorentey d0b4c4c215 IterableIterator_ → BorrowingIterator_ 2026-07-07 14:21:53 -07:00
Karoy Lorentey bb0dc189ef maximumCount → maxCount
While we’re here, adjust `RigidSet.insert(maximumCount:initializingWith:)` and similar APIs to be consistent with RangeReplaceableContainer’s methods.
2026-07-07 14:21:53 -07:00
Karoy Lorentey e8b09ade25 Add subscript requirements to [Mutable]Container with borrow/mutate accessors 2026-06-22 20:10:22 -07:00
Karoy Lorentey 73ec3d3416 [BasicContainers, DequeModule] Clean up Equatable/Hashable conformances
Make sure all types conditionally conform to Equatable/Hashable, even if their contents happen to be noncopyable.
2026-06-18 12:56:23 -07:00
Karoy Lorentey bced34defa Review error handling 2026-06-17 18:24:03 -07:00
Karoy Lorentey 85cdb77d25 Fix build issues 2026-06-17 16:17:36 -07:00
Nate Cook dca015d7e8 Align Iterable with proposal
Adds throwing and ~Escapable elements
2026-06-17 14:27:29 -07:00
Nate Cook 4bda43f4a9 Renaming BorrowingSequence_ to Iterable_ 2026-06-17 14:27:29 -07:00
Franz Busch 3c373b900c Use the defines from traits directly
Package traits already pass defines with their trait name when building. Instead of adding our own conditional defines based on the traits we can use the trait provided defines directly. I observed that various tooling behaves better with the trait provided defines.
2026-05-06 07:41:02 -07:00
Karoy Lorentey e0ec6b0976 UniqueSet: Fix copypasta 2026-03-27 11:59:41 -07:00
Karoy Lorentey 685ef74751 Fix {Rigid,Unique}{Set,Dictionary} 2026-03-27 11:47:03 -07:00
Nate Cook a99a015934 Disambiguate ContainersPreview and stdlib
Adds trailing underscores to the BorrowingSequence protocols and
requirements, in order to allow both parallel conformances and
the ability to evolve the requirements in this package.
2026-03-27 07:41:32 -05:00
Karoy Lorentey 4c04822689 [ContainersPreview] Exhibit B in the case against prototyping things in the stdlib 😳 2026-03-26 18:13:22 -07:00
Karoy Lorentey d2d3b917ca [BasicContainers, ContainersPreview, DequeModule] More SuppressedAssociatedTypesWithDefaults fixups 2026-03-26 18:12:41 -07:00
Karoy Lorentey 419e2f7df2 [ContainersPreview] Exhibit A in the case against prototyping things in the stdlib 😞 2026-03-26 17:14:45 -07:00
Karoy Lorentey fda65e149b [BasicContainers] Hashed containers: Make _checkInvariants() dump the hash table on failure 2026-03-11 00:31:37 -07:00
Karoy Lorentey 634a0ae766 [BasicContainers] Implement _checkInvariants on hashed containers 2026-03-10 23:04:49 -07:00
Karoy Lorentey de436301e5 [BasicContainers] Allow standalone use of the UnstableHashedContainers trait
Oops, I lost a change that allowed enabling the UnstableHashedContainers trait without also opting into UnstableContainersPreview. Reimplement this functionality.
2026-03-09 15:59:38 -07:00
Karoy Lorentey 5605e14682 [BasicContainers] Avoid defining set/dictionary types unless UnstableHashedContainers is enabled 2026-03-06 11:17:39 -08:00
Karoy Lorentey 1c69635852 Add SPDX-License-Identifier tags 2026-03-05 19:39:24 -08:00
Karoy Lorentey 214d75cb73 BorrowingSequence: estimatedCount ⟹ underestimatedCount
EstimatedCount is largely pointless. Knowing the exact count does enable a fast negative path for `elementsEqual`, but we can otherwise make do with just the (much simpler to understand/deal with) `underestimatedCount` that already exists on `Sequence`.
2026-03-05 15:33:27 -08:00
Karoy Lorentey ffdc48e67e [BasicContainers] Finalize requirements for hashed containers
- UnstableNoncopyableKeys → UnstableHashedContainers
- Delete the GeneralizedEquatable and GeneralizedHashable protocols, replacing them with the standard generalizations in the 6.4 stdlib
- Require Swift 6.4 for {Rigid,Unique}{Set,Dictionary}.
2026-03-03 16:01:45 -08:00
Karoy Lorentey 5f166046f1 [BasicContainers] Add some missing module imports 2026-02-27 14:56:18 -08:00
Karoy Lorentey b7545b990b [BasicContainers] Add bulk insertions to hashed set types 2026-02-27 13:36:37 -08:00
Karoy Lorentey 318ac805ea [BasicContainers] Add Index to hashed containers. Implement dictionary iteration using indices 2026-02-27 12:19:54 -08:00
Karoy Lorentey 087197dc1a [BasicContainers] Add removeAll() to hashed containers 2026-02-26 16:27:56 -08:00
Karoy Lorentey 0538000ffd [BasicContainers] Hashed containers: Add Equatable/Hashable conformances and related methods 2026-02-24 16:40:45 -08:00
Karoy Lorentey 2654a0711e [BasicContainers] Add removal operations to dictionaries 2026-02-23 13:59:36 -08:00
Karoy Lorentey 992bff5b87 [BasicContainers] Implement UniqueDictionary insertions 2026-02-23 13:58:31 -08:00
Karoy Lorentey a14f9eb61c [BasicContainers] Add missing imports of ContainersPreview 2026-02-23 13:56:38 -08:00
Karoy Lorentey 3941dab5b0 [BasicContainers] Implement removals on RigidSet and UniqueSet
Dictionaries are still to be done.
2026-02-20 18:19:51 -08:00
Karoy Lorentey d318a65867 [BasicContainers] Add UniqueDictionary 2026-02-19 17:57:34 -08:00
Karoy Lorentey 0cf34cc3a9 [BasicContainers] Improved debug output for hashed containers
- Allow bitmap visualization to be included/omitted as needed
- Visualize chain length distribution for both successful and unsuccessful lookups

Check out this sample test output for Robin Hood hashing:

```
⌗ large@11 1536/1792/2048, maxProbeLength: 11, totalProbeLength: 3712, maxOccupiedRun: 68
  ├╴[00000000] □□■■■■□□∙□■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■□■■■■■■∙□□□■□■□□∙□□□■■□■■∙■■■■■■■■
  ├╴[00000064] □□■□□■■■∙■■■■□■□□∙□■■■■■■■∙■■■■■■■■∙■■□□□□■□∙■□■□■■■■∙■■■■■■□□∙■■■■■■■■
  ├╴[00000128] ■■■■■■■■∙■■■□□□■□∙■■□■□■■□∙□■■■■■□■∙■■■■■■■■∙□■■■■■■■∙■■■■□■□■∙■□■□□■□□
  ├╴[00000192] ■□■■□■■■∙■■■■□■□■∙□□□□□■■□∙■■■■■■■■∙■■■□■■□■∙□■□■■□□■∙■■■■■■■■∙■■■■■■■■
  ├╴[00000256] ■■■■■■□□∙■■■■■■■□∙□■■■■■■□∙□■■■■■■□∙□□■■□□■□∙□□□■■■■□∙□■■■■□■■∙■■■■■■■■
  ├╴[00000320] ■■■■■■■■∙□■■■■■■■∙■■■■■■■□∙□■■□□■□□∙□□□■■□□■∙■■■■■□■□∙■□■■■■■□∙■■■■■■■■
  ├╴[00000384] ■■■■■■■■∙■■■■■□□■∙□□■■■■□□∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙□■■□□■□■∙□□■■□■■■
  ├╴[00000448] ■■■■□■■■∙■■■□■■■□∙□□□■□■■■∙■■■□□■■■∙■■■□□□□□∙□■■■■■■■∙■■■■■■■■∙■■■■■■■■
  ├╴[00000512] ■■■■■□□□∙□□■■□■■■∙■■■□■■■■∙■■■■■■■■∙■■■■■■■□∙□■■■■□□■∙■■■■■■■■∙■■■■■■■■
  ├╴[00000576] □□□■■■□■∙■■■□■■■■∙■■■■■■■■∙■■■■■■■■∙■■□■■■■■∙■■■■■■■■∙■■□□■□□□∙■■■□□□■□
  ├╴[00000640] □■■□□■■□∙□□□□■■■■∙□■■□■■■□∙□■■□■■■■∙■■■■■■■■∙■□□■■■■■∙■■■■■□□□∙■■■■■■■□
  ├╴[00000704] ■■■■■■■□∙■■■■□□□■∙■■□■□■■■∙■■■■■■■■∙■■■■□■■■∙□□□■□■■■∙□□□■□□□□∙□□□■□■■■
  ├╴[00000768] □■■■■■□■∙□■■□□□■■∙■■■■■■■□∙■■■■■■■■∙■■■■■■■□∙□■■■□■■□∙■□■■□■■■∙■■■■□■□■
  ├╴[00000832] ■□□■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■□□∙□□■■■■■■∙□□■■■■■■∙■■■■■■■■∙□■□■■■■■
  ├╴[00000896] ■■■■■■■■∙■■■■■□□■∙■■■□□□□■∙■■□□■■■■∙■□□■■■■□∙■■■□□■■□∙□□■■□■■■∙□■□□■■■■
  ├╴[00000960] ■■■■■□■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■□∙□■□■■■■■∙■■■■□□■■
  ├╴[00001024] ■■■■■■□□∙■■■■□■■□∙■■■■■■■□∙□□□■■■□□∙■■■□■■□■∙■□■■□□□■∙■■■■■■■■∙□□□□□□□□
  ├╴[00001088] ■■□□□□■□∙■■□□□□□■∙■□□■■■■■∙■■■□□□□■∙■■■■■■■■∙■■■■■■■■∙■■■■□□□□∙■■□■□■■■
  ├╴[00001152] ■■■□□■■□∙□■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■□■■□■■■∙■□■■□■■□∙□■■■■□■■
  ├╴[00001216] ■■■■■■■■∙■■□■□■■■∙■■■■■■■■∙□□■■□□□■∙□□□□□□□□∙□□■■■■■■∙■■■■■■■■∙■■■□□■■■
  ├╴[00001280] ■■■■■■■□∙■■□■■■■■∙■■■■■■□□∙■□□■■■■■∙■■■■■■■■∙■□□■□■□■∙■■■■■■■■∙■■■■■■■■
  ├╴[00001344] ■■■■■■■■∙■□■□■■□□∙■■■■□■□□∙□■■□■□□■∙□■□■■■■■∙■■■□■■■□∙□□■■■■■■∙■■■■■■■■
  ├╴[00001408] ■■■■■■■■∙■■■■■■■■∙■■■■■□□■∙■■■□■■■■∙■■□■■■■■∙■■■□■■■■∙■■□□■□□□∙■□■■■■■■
  ├╴[00001472] ■■■■■□■□∙■■□□□□□■∙□□□□□■■□∙■□□■■□■□∙■■■■■■■■∙■■■■■■■■∙□□□□■■■■∙■□■□□■■■
  ├╴[00001536] ■■■■■■■■∙□□□■■□■□∙□■■□■■□□∙□■□■■□□□∙■■■■■□□■∙■□■■■■■■∙■■■■■■■■∙■□□■□□□□
  ├╴[00001600] ■■■■■■■■∙■■■■□□■□∙□□■■□■■■∙■■■■■■■□∙□■□□■■□■∙■□■■■□■■∙■■■■■■■■∙□□■■■■■■
  ├╴[00001664] ■■■■■■■■∙□■■■□□■■∙■■■□■□■□∙■■■■■■□■∙■■■□■■■■∙■■■■■■■□∙□□□□■■■■∙■■■■□■■■
  ├╴[00001728] ■■■■■■■■∙■□□■■■■■∙■■□□■■□□∙■■■■■■■■∙■■■□□□■■∙□□■■■■■■∙■■■■■■■■∙■■■■■■■■
  ├╴[00001792] ■■■■■■■■∙■■■■■■■■∙■□□□■■□■∙□□■■□□□□∙□■■□■□□■∙□□■■■■□□∙■■■■■■■■∙■■■■■■■■
  ├╴[00001856] ■■■■■■■□∙■■■■■■■□∙□■□■□■■□∙■□□□■■■■∙■□■■□■■□∙□□■□■□■■∙■□□□□■■■∙■■■■■■■■
  ├╴[00001920] ■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■□□■□■□□
  └╴[00001984] ■□□■□□■■∙□■■■■■■□∙□□□□■■■■∙■□□□■■■■∙■■■■■■■■∙■■□■□■■■∙■■■□■■□□∙■□□■■□■□
Chain length distribution (for successful lookups):
   AVG: 2.416
     1: **************************************************************************** 549
     2: ******************************************************** 408
     3: ************************************* 264
     4: ******************** 142
     5: ************** 96
     6: ******* 51
     7: *** 17
     8: * 4
     9: * 1
    10: * 3
    11: * 1
Chain length distribution (for unsuccessful lookups):
   AVG: 4.428
     0: **************************************************************************** 511
     1: **************************************** 269
     2: ***************************** 191
     3: ******************* 129
     4: ***************** 111
     5: ************** 94
     6: ************* 85
     7: *********** 70
     8: ********* 60
     9: ********* 55
    10: ******** 50
    11: ************************************************************** 422
```
2026-02-19 12:10:26 -08:00
Karoy Lorentey 099aa3b312 [BasicContainers] Add UniqueSet 2026-02-18 22:05:22 -08:00