24 Commits
Author SHA1 Message Date
Karoy Lorentey d07dc32dfa Sources: Add unsafe keywords where needed 2026-10-01 11:14:29 -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
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 225bd07e56 RigidSet, UniqueSet: Add Container conformance 2026-09-01 09:34:05 -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 16e7715941 [BasicContainers] Speed up removals from hashed containers 2026-03-10 23:50:41 -07:00
Karoy Lorentey a8cf90f49c [BasicContainers] Hashed containers: slightly improve maxProbeLength after removals 2026-03-10 23:50:40 -07:00
Karoy Lorentey 5636b32db7 [BasicContainers] Scramble small hashed containers
Don’t just append new items to the end of storage — it misleads clients into assuming that the containers preserve insertion order, when they most certainly don’t do that.

Instead, insert new items into the middle of storage, using an extra swap.
2026-03-10 23:06:08 -07:00
Karoy Lorentey e69d570c59 [BasicContainers] Implement shortcut for insertions
We don’t need to calculate the probe length of the item currently occupying the new item’s ideal bucket — it cannot possibly be lower than the new item’s. This spares one hash operation during insertions that result in a hash collision.
2026-03-10 23:06:08 -07:00
Karoy Lorentey 2a53ad50b0 [BasicContainers] Fix insertion algorithm
Due to a number of cascading off-by-one errors, the maximum probe length could end up getting set lower than the actual value, _sometimes_ rendering some items unreachable.

Weirdly, the issue seems to be rare enough that it somehow never triggered in any of my previous test runs.
2026-03-10 23:06:07 -07:00
Karoy Lorentey 634a0ae766 [BasicContainers] Implement _checkInvariants on hashed containers 2026-03-10 23:04:49 -07:00
Karoy Lorentey 1c69635852 Add SPDX-License-Identifier tags 2026-03-05 19:39:24 -08:00
Karoy Lorentey cef50eee26 [BasicContainers] Fix incorrect wraparound implementation in hashed container insertions with NO_ROBIN_HOOD_HASHING 2026-03-05 15:30:10 -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 978ebeda02 [BasicContainers] Fix spelling of a source file
Renaming `_Htable+Debugging.swift` to `_HTable+Debugging.swift` did not stick — rename the file to `_HTable+Debug.swift` to get rid of the lowercase t for good.
2026-03-02 16:14:20 -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 0538000ffd [BasicContainers] Hashed containers: Add Equatable/Hashable conformances and related methods 2026-02-24 16:40:45 -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 a1902c30aa [BasicContainers] Make _HTable nonfrozen and most of its operations noninlinable
This is a nongeneric type, so it makes sense to see if Swift has matured enough to use opaque/resilient types in high-performance contexts. It would be ideal if the core hash table implementation would remain flexible.

We may need to sprinkle some effect attributes over these.
2026-02-19 17:56:22 -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
Karoy Lorentey 0ed3abd92c Fix some build errors in some configurations 2026-02-16 17:16:02 -08:00
Karoy Lorentey bf9a7033a0 [BasicContainers] Add early drafts for RigidSet/RigidDictionary 2026-02-16 17:15:59 -08:00