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.
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.
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.
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.
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.
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.)