Commit Graph
56 Commits
Author SHA1 Message Date
Guillaume Lessard 8cb5b628ae Rename module to Span 2025-02-21 19:13:48 -08:00
Guillaume Lessard 3f6522fef1 post-rebase compatibility fixes 2024-10-06 11:16:43 -07:00
Karoy Lorentey ca0c7a28b9 wip 2024-09-11 05:48:24 -07:00
Karoy Lorentey 3c66dab3b0 [Deque] Turn Deque<T> into a Shared<RigidDeque<T>> 2024-09-01 20:46:43 -07:00
Karoy Lorentey 75aa5b0755 Hypo → Rigid, Dyno → Dynamic
Let’s try these on for size. The greek prefixes work great, but their capitalization looks bad, and they do not interact well with compound names. (`OrderedHyposet`?)
2024-08-12 13:35:42 -07:00
Karoy Lorentey 816fc78827 [_CollectionsUtilities] Add Unsafe[Mutable]BufferPointer._extracting(unchecked:)
Also, use these to spare some unnecessary instructions.
2024-08-07 19:12:05 -07:00
Karoy Lorentey dface3fb37 [Deque] Mitigate some effects of the lack of an empty Deque singleton 2024-08-07 19:10:29 -07:00
Karoy Lorentey 6322ec54a0 [Deque] Disable runtime exclusivity checking for the ivar of the storage class
It turns out the major slowdowns in individual element add/remove operations were mostly caused by runtime exclusivity checking on `Deque._Storage._value`.
2024-08-07 19:09:09 -07:00
Karoy Lorentey 626e24fede [Deque] Add _UnsafeDequeHandle.reallocate(capacity:) 2024-08-06 20:00:27 -07:00
Karoy Lorentey 5d51572d69 [Deque] Stop using ManagedBuffer
Instead, just have a regular class holding a HypoDeque. This requires two allocations per deque, but it makes representation a lot more straightforward.

I do not have a workable solution for empty singletons, though.
2024-08-06 19:17:04 -07:00
Karoy Lorentey f64adedbf4 [Future] _CollectionsUtilities → InternalCollectionsUtilities 2024-08-06 11:33:20 -07:00
Karoy Lorentey a81352a313 [Future] BorrowingIterator: Make copyable; fix nextChunk’s lifetime constraint 2024-08-06 10:50:07 -07:00
Karoy Lorentey 944f4ab1fe [Deque] Delete old _UnsafeHandle type 2024-08-06 10:49:13 -07:00
Karoy Lorentey 3310a4c21c [Deque] Add HypoDeque and DynoDeque 2024-08-06 10:45:21 -07:00
Karoy Lorentey d58c5b60a5 Merge branch 'main' into future
# Conflicts:
#	Sources/CMakeLists.txt
#	Sources/InternalCollectionsUtilities/Compatibility/UnsafeMutableBufferPointer+SE-0370.swift.gyb
#	Sources/InternalCollectionsUtilities/Compatibility/UnsafeMutablePointer+SE-0370.swift.gyb
#	Sources/InternalCollectionsUtilities/Compatibility/UnsafeRawPointer extensions.swift.gyb
#	Sources/InternalCollectionsUtilities/Compatibility/autogenerated/UnsafeMutableBufferPointer+SE-0370.swift
#	Sources/InternalCollectionsUtilities/Compatibility/autogenerated/UnsafeMutablePointer+SE-0370.swift
#	Sources/InternalCollectionsUtilities/Compatibility/autogenerated/UnsafeRawPointer extensions.swift
#	Sources/InternalCollectionsUtilities/Specialize.swift.gyb
#	Sources/InternalCollectionsUtilities/autogenerated/Specialize.swift
2024-08-05 20:31:30 -07:00
Karoy Lorentey f14a18d7a6 Mark empty singletons as nonisolated(unsafe) 2024-08-05 19:37:20 -07:00
quokkakyu 6b8276e252 add 'final' keyword to class 2024-07-15 09:27:27 +09:00
Jeremy Schonfeld 3e120b48bb [CMake] Reduce path lengths in single-module build (#392)
* Eliminate relative paths from the cmake single-module build

* Attempt to reduce length of paths in single module build
2024-06-26 08:39:11 -07:00
Jeremy Schonfeld ee97538f5b Add Single Module Build Mode to CMake for Foundation (#385)
* Add new single-module and foundation-toolchain-module modes to CMake build

* Fix allowable client flag syntax
2024-06-03 16:15:50 -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
Karoy Lorentey ead6314a1c [Deque]: Fix bogus assert in Deque._Storage._ensureUnique
A non-unique reference to a storage instance can legitimately become unique at any point, due to other references (say, held, by another thread) getting destroyed.

`Deque`’s `ensureUnique` implementation currently invokes the uniqueness check two times in quick succession, expecting it to return false both times. In rare circumstances, this can lead to a spurious trap in concurrent environments.

Fix this by avoiding calling `isUnique` more than once.
2024-05-24 13:13:00 -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 55db6d936c Remove workaround for SR-14663
Our updated minimum toolchain requirement is Swift 5.7, and the stdlib in that version has the fix included.

We’ve seen reports that the bug may not deploy back in all cases to earlier OS releases, but it still seems worth trying to remove the workaround, as it has some undesirable runtime implications.
2024-01-31 19:34:37 -08:00
Karoy Lorentey e27e422927 [Deque] Update copyright notices 2024-01-31 19:34:36 -08:00
Karoy Lorentey 04ee7c0b1d [Deque] Modernize generic declaration syntax 2024-01-31 19:34:34 -08:00
Karoy Lorentey 1a0ac8c06c Merge branch 'release/1.0' into release/1.1
# Conflicts:
#	Sources/DequeModule/CMakeLists.txt
#	Sources/DequeModule/Deque+Collection.swift
#	Sources/DequeModule/Deque+Sendable.swift
#	Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Elements.SubSequence.swift
#	Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Elements.swift
#	Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Sendable.swift
#	Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Sequence.swift
#	Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Values.swift
#	Sources/OrderedCollections/OrderedSet/OrderedSet+Sendable.swift
#	Sources/OrderedCollections/OrderedSet/OrderedSet+SubSequence.swift
#	Sources/OrderedCollections/OrderedSet/OrderedSet+UnorderedView.swift
#	Sources/OrderedCollections/OrderedSet/OrderedSet+UnstableInternals.swift
2023-12-21 15:17:15 -08:00
Karoy Lorentey cdcf9e606a Update CMake configuration 2023-12-19 17:45:02 -08:00
Karoy Lorentey 8bfcaddd5f [1.0] Update copyright dates 2023-12-18 15:35:56 -08:00
Karoy Lorentey 7d43c07a71 Backport Sendable conformances on all public types
Resolves #317
2023-12-18 15:25:38 -08:00
Rick van Voorden 2122327782 deque storage equality helper 2023-12-12 14:16:21 -08:00
Rick van Voorden 22306e061a check deque equality with buffer identity 2023-12-11 19:30:34 -08:00
Karoy Lorentey 09c09f0f73 Fix CustomStringConvertible/CustomDebugStringConvertible conformances
- For CustomStringConvertible, `description` should print elements using `String(reflecting:)` rather than `String(describing:)`, to avoid element output from interfering with syntactically relevant punctuation within structured list displays.
- To make this work without making displays overly verbose, make `debugDescription` mostly the same as `description`, except for escaping raw string displays when and if needed.
- Avoid printing type names in `debugDescription` — it is generally not helpful, as the type is already easily accessible elsewhere. Including it makes for overly verbose displays when the type serves as an Element of a collection.
- Avoid having `debugDescription` return the empty string — it can be confusing when such a description appears in list displays.

Resolves #301.
2023-07-06 17:25:11 -07:00
Karoy Lorentey a8dad62bc9 Remove obsolete swift(>=5.5)/swift(>=5.6) checks 2023-04-10 18:33:52 -07:00
Karoy Lorentey cbab9e3737 Introduce COLLECTIONS_SINGLE_MODULE condition 2023-03-21 18:42:33 -07:00
Karoy Lorentey 141c3939bf [DocC] Add documentation bundles for all three targets 2022-12-06 18:41:04 -08:00
Karoy Lorentey b2f254384d [doc] Add some flesh to DocC structure
# Conflicts:
#	Sources/BitCollections/BitCollections.docc/Extensions/BitArray.md
#	Sources/BitCollections/BitCollections.docc/Extensions/BitSet.Counted.md
#	Sources/BitCollections/BitCollections.docc/Extensions/BitSet.md
#	Sources/OrderedCollections/OrderedCollections.docc/Extensions/OrderedSet.UnorderedView.md
#	Sources/OrderedCollections/OrderedCollections.docc/Extensions/OrderedSet.md
2022-10-28 12:34:14 -07:00
Karoy Lorentey 86bce28835 [docs] Start working on DocC support 2022-10-28 12:34:14 -07:00
Karoy Lorentey f76630db8e [Internals] Add missing internal checking predicates & docs for all 2022-10-18 22:13:19 -07:00
Karoy Lorentey 5aed92655d [CMake] Update CMake build configuration 2022-10-11 13:11:37 -07:00
Karoy Lorentey 48ac82c029 [Deque] Modernize code base for Swift 5.5 2022-10-09 20:11:51 -07:00
Karoy Lorentey da5284d433 [Deque] Deque, Deque.Iterator: Explicitly conform to Sendable when Element is Sendable 2022-10-05 11:35:54 -07:00
Karoy Lorentey 12e3867ccb [Collections] Allow determining if internal checking is enabled
In the benchmark target, complain loudly if consistency checks
are enabled.
2022-09-19 21:25:07 -07:00
Karoy Lorentey 77edbef16d [_CollectionsUtilities] Restore original debug descriptions 2022-09-13 23:45:22 -07:00
Karoy Lorentey dd76591970 [_CollectionsUtilities] New module. Use it to unify description/debugDescription implementations 2022-09-12 12:47:04 -07:00
Karoy Lorentey 87c78de6b4 [Deque] Force-inline the subscript’s _modify accessor to work around a performance issue
Resolves #164.

(cherry picked from commit 98cd753866)
2022-08-31 17:13:53 -07:00
Karoy Lorentey 98cd753866 [Deque] Force-inline the subscript’s _modify accessor to work around a performance issue
Resolves #164.
2022-08-31 13:53:52 -07:00
Károly Lőrentey efefae5653 [Deque] append(contentsOf:): Use exponential capacity reservation
Depending on the supplied sequence, `Deque.append(contentsOf:)` currently reserves just enough capacity as it needs to perform the append. This isn't right -- it can result in O(n) reallocs instead of O(log(n)) when items are incrementally appended in constant-sized `append(contents:)` batches.
2021-11-15 16:12:28 -08:00
Karoy Lorentey 56b82b1b7f Freeze some types for consistency with their inlinable initializers
Note: @frozen does *not* mean that we actually consider these struct types frozen. Their layout may arbitrarily change between even minor releases.
2021-08-30 15:31:12 -07:00
ejmarchant 5ff8c003b0 Fix documentation for types conforming to ExpressibleByArrayLiteral or ExpressibleByDictionaryLiteral (#82)
# Conflicts:
#	Sources/PriorityQueueModule/Heap+ExpressibleByArrayLiteral.swift
2021-08-19 19:26:41 -07:00
Karoy Lorentey fa45de1018 Work around another MergeModules crash (#62)
* [utils] Add utility for shuffling sources to help reproduce MergeModules issues

* [Deque] Collapse Sequence/Collection conformances into a single file

The MergeModules phase in the compiler is broken: it isn’t always able to correctly handle circular dependencies across source files, like the ones that keep organically popping up with Sequence/Collection conformances that are defined in separate files.

Such dependencies sometimes triggers a compiler crash, depending on some (unknown) environmental parameters.

Trying to manually find and eliminate these circular dependencies has not proved productive. Instead, roll all Collection conformances into a single, huge source file.

* [Deque] Update CMakeLists
2021-07-08 17:02:00 -07:00