Commit Graph
1140 Commits
Author SHA1 Message Date
David Nadoba 3a07388528 Add TemporaryArray: a stack-seeded, heap-spilling scratch array
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.
2026-07-09 15:16:13 -07:00
Karoy Lorentey 90f26545ce Merge pull request #673 from wjdtjq6/fix/doc-comment-typos
Fix typos in doc comments and a DocC article
2026-07-07 15:09:13 -07:00
Karoy Lorentey 638c62cd7b Merge pull request #674 from wjdtjq6/fix/superset-doc-comments
Fix superset set algebra doc comments
2026-07-07 15:08:52 -07:00
Karoy Lorentey 957813c2f4 Merge pull request #668 from inju2403/perf/orderedset-reverse-in-place
[OrderedCollections] OrderedSet.reverse(): update the hash table in place
2026-07-07 14:44:03 -07:00
wjdtjq6 62a08e503e docs: fix typos in doc comments and DocC article 2026-07-02 21:17:11 +09:00
Your NameandClaude Opus 4.8 259b4d52c2 Fix @inlinable deinit incompatibility with library evolution
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>
2026-06-29 16:15:00 +05:30
wjdtjq6 646274ed7c docs: fix superset set algebra comments 2026-06-23 13:21:36 +09:00
Karoy Lorentey 3d68fc1107 Clean up the UniqueBox/Ref/MutableRef situation
- 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.
2026-06-17 18:29:41 -07:00
Karoy Lorentey 51c9e4ead8 Fix IterableIteratorProtocol.map; add map2 and map3 with different throwing behavior 2026-06-17 18:24:03 -07:00
Karoy Lorentey 7c853751c6 Add IterableIteratorProtocol.mapError 2026-06-17 18:24:03 -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
Karoy Lorentey 816b887369 Update CMake and Xcode build configurations 2026-06-17 14:40:07 -07:00
Nate Cook c039a18a0e Switch to using stdlib Ref and UniqueBox 2026-06-17 14:27:29 -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
Karoy Lorentey 28e9d98a7e Fix deprecation warnings 2026-06-17 13:48:54 -07:00
Alejandro Alonso 06423d7329 Fix broken docs 2026-06-17 13:48:54 -07:00
Alejandro AlonsoandKaroy Lorentey 2a39308613 Update Sources/BasicContainers/UniqueArray/UniqueArray.swift
Co-authored-by: Karoy Lorentey <klorentey@apple.com>
2026-06-17 13:48:54 -07:00
Alejandro AlonsoandKaroy Lorentey eb5c24f71a Update Sources/BasicContainers/RigidArray/RigidArray.swift
Co-authored-by: Karoy Lorentey <klorentey@apple.com>
2026-06-17 13:48:54 -07:00
Alejandro AlonsoandKaroy Lorentey c6a1dabfd0 Update Sources/BasicContainers/RigidArray/RigidArray+Deprecated.swift
Co-authored-by: Karoy Lorentey <klorentey@apple.com>
2026-06-17 13:48:53 -07:00
Alejandro Alonso 6da58357a3 Rename reallocate to setCapacity for Rigid and UniqueArray
Update UniqueArray.swift

Update UniqueArray.swift
2026-06-17 13:48:53 -07:00
inju2403 86ddbd9705 [OrderedCollections] OrderedSet.reverse(): update the hash table in place
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.
2026-06-12 08:57:42 +09:00
Karoy Lorentey af174fe447 Merge pull request #662 from sorinc03/fix/heap-node-tests-release
Run heap node tests in release
2026-06-09 15:03:37 -07:00
Karoy Lorentey e31c04143e Update CMake & Xcode build configurations 2026-06-05 18:45:56 -07:00
Karoy Lorentey 5c8d97dccb Merge pull request #660 from apple/dn/ordered-set-move
[OrderedCollections] Add move operations
2026-06-05 17:45:16 -07:00
David Nadoba 72f074a23a [OrderedCollections] Use pre-removal destination index for move APIs 2026-06-05 17:05:03 -07:00
David Nadoba 5a6af29d55 [OrderedCollections] Refine move APIs and simplify no-op check 2026-06-05 14:44:22 -07:00
David Nadoba a83773321e [OrderedCollections] Rework move APIs and extend to OrderedDictionary
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.
2026-06-04 22:33:54 -07:00
Sorin Cioban bdd6b79403 Use package access for heap test helper 2026-06-04 10:18:09 +01:00
Sorin Cioban 49887191bb Run heap node tests in release 2026-05-31 23:10:33 +01:00
Aditya Singh ce67d512d5 [SortedCollections] Fix _BTree default node capacity capping at 16
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
2026-05-29 00:52:15 -07:00
David Nadoba 508f36f48d [OrderedSet] Add move(_:toOffset:)
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.
2026-05-25 23:01:28 -07:00
Aditya Singh 0a3dcfd3a8 [InternalCollectionsUtilities] Fix _trim returning the wrong buffer region
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.
2026-05-24 18:22:45 -07:00
Guoye Zhang 8cacd3c125 Add missing availability to Borrow 2026-05-18 17:50:20 -07:00
Karoy Lorentey 1b3ec29d61 [Collections] Declare generic arguments on forwarding typealiases
Otherwise the typealiases do not work as intended on public API that mentions them in client modules.
2026-05-15 17:02:45 -07:00
Karoy Lorentey a731a7fdad [BasicContainers] Don’t define LLDB formatter symbol on Wasm
While we’re here, follow our explicit access control rule when defining the variable.
2026-05-12 15:33:22 -07:00
Franz Busch f674e13c3d Guard UniqueBox.borrow correctly
Correctly guard the `borrow` method behind the compiler version
2026-05-11 14:43:54 +02:00
Karoy Lorentey c38e47d03e [BasicContainers, DequeModule] Avoid using deprecated API 2026-05-07 16:17:20 -07:00
Karoy Lorentey 72ee2bf645 [BasicContainers] Update CMakeLists.txt 2026-05-07 16:16:57 -07:00
Karoy Lorentey f83bd74aea Move FormatterFixtures into a nested package 2026-05-07 16:15:02 -07:00
Karoy Lorentey 16d6b8e1fe [ContainersPreview] Inout ⟹ MutableRef 2026-05-06 18:28:07 -07:00
Karoy Lorentey 1fd366764d [ContainersPreview] Ref: Fix fallback implementation; make sure we have deprecated aliases for old names 2026-05-06 18:00:13 -07:00
Karoy Lorentey 18c58bcca4 [ContainersPreview] Ref: Disable Builtin.Borrow for now 2026-05-06 18:00:13 -07:00
Karoy Lorentey a6fd64697a [ContainersPreview] Borrow ⟹ Ref
Also update the type’s public API surface to reflect SE-0519, leaving deprecated aliases for the old names.
2026-05-06 18:00:13 -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 12eb78f778 Merge pull request #640 from lorentey/uniquebox
Rename `Box` to `UniqueBox`; align API surface with SE-0517
2026-05-05 17:47:42 -07:00
Karoy Lorentey bb7839ae50 Merge pull request #642 from lorentey/doc-fix
[BasicContainers] Fix copypasta in `UniqueArray.edit`’s docs
2026-05-05 17:31:51 -07:00
Karoy Lorentey 3a55ce888c [ContainersPreview] UniqueBox.value: Avoid using borrow/mutate on old compilers
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.
2026-05-05 17:31:09 -07:00
Karoy Lorentey 146056a641 [ContainersPreview] Box ⟹ UniqueBox
Also update the type’s public API surface to reflect SE-0517, leaving deprecated aliases for the old names.
2026-05-05 17:31:05 -07:00