47 Commits
Author SHA1 Message Date
Sebastian Turner 6f8f55a5ad [BigString] Resync character breaks after removeSubrange
Signed-off-by: Sebastian Turner <sebastiant3484@gmail.com>
2026-10-20 16:18:03 -07:00
Tony Parker 500233e8c0 Use _addressString in debug description 2026-10-08 17:28:56 -07:00
Tony Parker d014985b5f Build BigString in Embedded Swift - with a custom implementation of grapheme walking instead of using the stdlib 2026-10-08 16:41:20 -07:00
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 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 f9a6df8a55 [_RopeModule] Fix infinite loop while hashing the UTF-8 view of a multi-chunk big substring 2026-04-30 15:29:22 -07:00
Karoy Lorentey 1c69635852 Add SPDX-License-Identifier tags 2026-03-05 19:39:24 -08:00
Karoy Lorentey d9b09ecde8 Update copyright dates 2026-03-05 19:39:20 -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 9503f8fe57 Improve consistency of precondition failure messages
More uniform message strings should feel better, and they should ever so slightly reduce code size.
2026-02-04 10:27:17 -08:00
Alejandro Alonso 691855a60f Bring back _isUTF16TrailingSurrogate 2025-10-14 09:50:14 -07:00
Karoy Lorentey 006ab60c42 Xcode/Collections.xcodeproj: Fix ability to build & test BigString 2025-10-10 15:53:16 -07:00
Karoy Lorentey a7e40d2055 Fix warnings 2025-10-02 18:29:35 -07:00
Alejandro Alonso a1f8f33a5b Make BigString unavailable in embedded 2025-09-30 12:40:09 -07:00
Alejandro Alonso 729869eb6d Use the underscored lifetime attribute 2025-09-30 09:11:47 -07:00
Alejandro Alonso a9bfbeac39 Conditionalize big string sources on 6.2 compiler
add some more
2025-09-30 09:04:52 -07:00
Alejandro Alonso 235030c10b Refactor BigString._Chunk to be its own managed buffer of UTF8 2025-09-30 09:04:19 -07:00
Karoy Lorentey 5f03d1bc24 Adopt availability macros 2025-08-17 13:23:01 -07:00
Karoy Lorentey fc411858ee [BigString] Speed up index distance calculations
This implements a roughly 40-45% improvement for distance measurements over `BigString`’s character and Unicode Scalar views.

Interestingly, we don’t see an improvement for UTF-16 views — I’m guessing this is due to String’s breadcrumbing. (And it will go away with the upcoming UTF8Span-ification of this type.)

The benchmarks I added only show an improvement for multi-chunk big string instances, but this is merely an artifact of the specific algorithm that is being measured — for single-chunk strings, the existing measurement method is already optimal, so the new heuristic never triggers for this particular payload.
2025-06-23 15:21:40 -07:00
Karoy Lorentey 65f99e3eff [BigString] Fix character indexing operations
BigString sometimes miscounted distances in its character view due to alignment issues. Resolve this by overhauling distance calculations in the character metric:

- Introduce a `prefixSize` function in `_StringMetric`, distinct from `distance`.
- In the metric-agnostic index distance algorithm, use `prefixCount` to avoid double-counting characters that cross (or end on) chunk boundaries.
- Simplify `_StringMetric.distance` by requiring that `start <= end`.
- Crucially, change character-index operations to start by rounding each input index down to the nearest character break.
2025-06-17 17:28:02 -07:00
Karoy Lorentey 755c06dd88 Adopt _pointerBitWidth 2024-09-25 14:17:32 -07:00
Karoy Lorentey e4cd17cc53 Remove support code for outdated toolchains 2024-09-25 14:14:48 -07:00
Karoy Lorentey 5e1fe6e8f0 [BigString] Fix accidentally quadratic BigString.init
When ingesting a `String` instance, `BigString` assumes that the input string has a reasonably efficient UTF-8 view.

Unfortunately, that is very much not the case when the input happens to be backed by a bridged NSString object — it appears that in this case, the ingester loop invokes some operation(s) with linear complexity in the size of the entire input, rendering the ingester’s overall complexity quadratic.

The BigString ingester is only expected to operate within a single chunk at the time. It’s unclear precisely which operation triggers the quadratic behavior; ideally we should figure it out and resolve it with a more targeted fix.

In the meantime, a blunt stopgap fix is to force-transcode the input string to UTF-8 at the time the ingester is initialized. This unnecessarily wastes some (temporary) memory on holding the transcoded string, but it avoids the quadratic cliff.
2024-07-15 13:13:44 -07:00
Karoy Lorentey 35d5746117 Rename _CollectionsUtilities to InternalCollectionsUtilities
We are forced to do this due to an Xcode issue (#364) with underscored module names.

This module remains unstable, despite the removal of the underscore. Directly importing it from outside the package remains unsupported. This module and/or its entire contents may go away or change in incompatible ways in any future swift-collections release.
2024-05-29 14:00:13 -07:00
Dimitris Apostolou 7539583245 Fix typos
# Conflicts:
#	Sources/SortedCollections/BTree/_BTree+BidirectionalCollection.swift
#	Sources/SortedCollections/BTree/_BTree+UnsafeCursor.swift
#	Sources/SortedCollections/BTree/_BTree.Builder.swift
#	Sources/SortedCollections/BTree/_BTree.swift
#	Sources/SortedCollections/BTree/_Node.Splinter.swift
#	Sources/SortedCollections/BTree/_Node.Storage.swift
#	Sources/SortedCollections/BTree/_Node.UnsafeHandle+Insertion.swift
#	Sources/SortedCollections/BTree/_Node.swift
#	Tests/SortedCollectionsTests/BTree/Node+Join Tests.swift
2024-02-06 15:52:26 -08:00
Karoy Lorentey ffa4a58bc1 Update remaining copyright notices 2024-02-02 16:20:22 -08:00
Karoy Lorentey 5bce3c9ceb [RopeModule] Adopt _specialize and extend adoption of modern generic decl syntax 2024-02-02 16:20:21 -08:00
Karoy Lorentey 73936bba69 Expose a handful of BigString.Index methods
These help implementing conversions between String.Index and BigString.Index.
2023-04-07 19:26:47 -07:00
Karoy Lorentey 28010b2f6c Use COLLECTIONS_INTERNAL_CHECKS 2023-03-21 01:28:13 -07:00
Karoy Lorentey ad82bc3f80 Naming review 2023-03-21 01:21:43 -07:00
Karoy Lorentey 88286b661d BigString: Fix Issue in utf16.distance when endpoint is on the trailing surrogate of the first scalar in a chunk 2023-03-21 01:04:12 -07:00
Karoy Lorentey 6f3f19d1c5 _Rope → Rope 2023-03-20 23:49:57 -07:00
Karoy Lorentey 51ef8613c2 Underscore more internals 2023-03-20 22:27:32 -07:00
Karoy Lorentey 0ad7f0ce38 _BString → BigString 2023-03-20 21:20:30 -07:00
Karoy Lorentey b022b7fee5 Make _BString and _Rope public 2023-03-20 18:36:37 -07:00
Karoy Lorentey b8927d819b BigString: Flesh out views, make them consistent with _BString 2023-03-20 13:12:13 -07:00
Karoy Lorentey cffcd517a2 BigString: Start modernizing 2023-03-20 13:12:13 -07:00
Karoy Lorentey 258d22947c _BString: Review Equatable implementations 2023-03-20 13:12:12 -07:00
Karoy Lorentey abf5dfd260 _BSubstring: Conform to Comparable 2023-03-20 13:12:12 -07:00
Karoy Lorentey a10439bc32 _BString, _BSubstring: Merge character views into top-level types. Add RangeReplaceableCollection conformances.
This emulates the standard String.
2023-03-20 13:12:12 -07:00
Karoy Lorentey 8c1740ad28 _Rope.Index: Merge height into UInt64 storage.
This leaves 56 bits for path data, which should still be plenty.
(We want to allow big strings to grow to 2^48 UTF-8 code units, to
match the standard String; however, there is no practical need to
support any more, and even that is a stretch.)

Add tests to verify that the tree capacity matches expectations
in Release builds. (In Debug builds, we limit the maximum node size,
which drastically reduces capacity. This is okay.)
2023-03-20 13:12:09 -07:00
Karoy Lorentey 8c8cb5622b Restrict BIgString and _BString to Swift 5.8 and macOS 13.3 /iOS 16.4/etc
These types heavily rely on stdlib functionality that ships in
Swift 5.8; they do not run correctly on earlier releases.
2023-03-20 13:12:09 -07:00
Karoy Lorentey 283d4071bc Assorted bug fixes and refinements 2023-03-20 13:12:08 -07:00
Karoy Lorentey eabd941799 Add some operations taking subsequences 2023-03-20 13:12:07 -07:00
Karoy Lorentey 150a165d73 Add experimental rope implementation 2023-03-20 13:11:21 -07:00