TemporaryArray is a ~Copyable and ~Escapable dynamic array whose initial
storage is a borrowed buffer (most usefully a stack allocation vended by
withTemporaryArray(of:capacity:_:)) and which transparently spills over
into freshly allocated heap storage once it outgrows that seed buffer. As
long as the element count stays within a seed buffer that fit on the stack,
the array incurs no heap traffic at all.
Because it can hold a dependency on borrowed (stack) memory, the type is
non-escapable: instances cannot outlive the scope that provides their
initial buffer. Contents are lifted out into an owning container with
take(), which transfers the heap buffer in O(1) if the array has already
spilled, or moves the elements into a fresh UniqueArray otherwise.
The API mirrors UniqueArray (SE-0527), minus the pieces that don't apply
to a non-escapable scratch type (DynamicContainer, MutableContainer, and
RangeReplaceableContainer conformances plus the Drain-based consumer),
plus members unique to its borrow-then-spill design: take(), clone(), and
append(repeating:count:). The seed-buffer initializer is kept internal for
now, with withTemporaryArray as the sole entry point. Equatable/Hashable
and CustomStringConvertible/CustomDebugStringConvertible are implemented
as methods with FIXMEs to add the conformances once those protocols
support ~Copyable/~Escapable types.
The Collection/RangeReplaceable surface and container-protocol conformances
are gated behind the UnstableContainersPreview trait, mirroring UniqueArray;
the core API builds in the default configuration. DocC coverage is added for
the type and the withTemporaryArray entry point.
The `Storage` classes in HashTreeCollections and SortedCollections mark
their `deinit` as `@inlinable` but lack `@_fixed_layout`. Under library
evolution (BUILD_LIBRARY_FOR_DISTRIBUTION=YES), Swift 6.2+ rejects this
with "deinitializer can only be '@inlinable' if the class is
'@_fixed_layout'", because inlining a deinit requires a known layout that
resilient mode deliberately hides.
This mirrors the existing fix already applied to the equivalent storage
classes in DequeModule (_DequeBuffer) and RopeModule (Rope._Storage). As
noted there, this does not make anything ABI stable -- these storage
classes are @usableFromInline internal and never part of the public ABI
surface -- it only lets these modules build with library evolution
enabled.
Fixes#676.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
- UniqueBox is public API, so we cannot remove it in favor of the stdlib’s
- Remove Ref and MutableRef. Keep an internal _MutableRef to work around stdlib limitations.
Reversing an ordered set is a deterministic permutation: the element at offset `i` moves to offset `count - 1 - i`. Hash values are unaffected, so every element stays in its current bucket and only the stored offset needs to be flipped. `reverse()` was instead regenerating the whole hash table from scratch, rehashing every element -- exactly what the existing `// FIXME: Update hash table contents in place.` called out.
Replace `_regenerateHashTable()` with an in-place offset flip (`v -> count - 1 - v`) over the table's buckets, reusing the same bucket-walk idiom as `adjustContents` and `swapBucketValues`. This drops all hash recomputation and the table reallocation.
Reworks the relocation API and extends it to `OrderedDictionary`:
* Renames the index-range move to `moveSubrange(_:to:)` (with a
`RangeExpression` overload) and the by-value move to `move(contentsOf:to:)`,
matching the conventions of `removeSubrange`/`insert(_:at:)`. Adds
`move(fromIndices:to:)`, which takes the source indices directly.
* Factors the element rearrangement into generic
`UnsafeMutableBufferPointer` operations (rotation / rotation+permutation /
scatter) so `OrderedDictionary` relocates its keys and values in lockstep
through the same code, adding only the parallel value move; the hash-table
maintenance stays entirely in `OrderedSet`.
* The hot path runs in O(*d* + *k*) and falls back to O(`count`) for large
moves; bucket maintenance chooses targeted updates or a full rebuild by the
same threshold.
* `move(contentsOf:to:)` ignores elements/keys that aren't present; duplicate
members are detected and trap.
Adds tests (exhaustive hash-table integrity, value alignment under lifetime
tracking) and move benchmarks for both types.
The defaultInternalCapacity and defaultLeafCapacity computations used
Swift.min(16, capacityInBytes / MemoryLayout<Key>.stride), which capped
the node capacity at 16 regardless of element size. This defeated the
byte-budget intent: small elements should yield larger nodes, not be
clamped to 16. Use Swift.max instead so 16 acts as a floor and the
byte budget governs the upper bound, as confirmed by the maintainer
in issue #257.
Fixes#257
Adds two overloads for relocating elements within an `OrderedSet`: one
taking a contiguous `Range<Int>`, and one taking a `Sequence<Element>`.
The moved elements occupy consecutive positions starting at the
destination, in the order they appear in the input.
The hot path runs in O(*d* + *k*) time, where *d* is the distance moved
and *k* is the number of elements moved; the implementation falls back
to O(`count`) for large moves.
The `_trim(first:)` and `_trim(last:)` helpers reassign `self` to the
remaining slice and then build the trimmed result from `self`'s now-updated
`baseAddress`/`count`, so they hand back a region that points into the wrong
place in the buffer.
`UnsafeMutableBufferPointer._trim(first:)` had this exact bug fixed earlier (it
captures `oldStart` before the reassignment), but three sibling helpers were
left untouched:
* `UnsafeBufferPointer._trim(first:)` reads `baseAddress` after advancing
`self`, so the returned prefix starts at the remainder instead of at the
original head.
* `UnsafeBufferPointer._trim(last:)` and
`UnsafeMutableBufferPointer._trim(last:)` recompute `count &- cut` after
shrinking `self`, so the returned suffix starts `cut` elements too early.
For a five-element buffer, `_trim(first: 2)` returned the bytes of `[30, 40]`
rather than `[10, 20]`, and `_trim(last: 2)` returned `[20, 30]` rather than
`[40, 50]`; trimming more than the count walked off the end of the buffer.
Capture the original start (and, for the suffix case, the post-trim count)
before mutating `self`, matching the already-correct `_trim(first:)` on the
mutable buffer. Adds direct tests covering both overloads on both buffer types.
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.
These (and `@_unsafeSelfDependentResult`) are only usable on 6.4 snapshots. As 6.4 hasn’t shipped yet, we need to also make these conditional on the UnstableContainersPreview trait.