apple/swift-collections 1.7.0

Swift Collections 1.7.0

on GitHub

This is a feature release raising the minimum required toolchain to Swift 6.2. It formalizes Equatable/Hashable conformances on the ownership-aware container types, adds a new stable OrderedSet operation, and continues to develop the experimental ownership-aware container model behind the UnstableContainersPreview trait. It also includes a number of performance improvements and bug fixes.

New stable APIs

OrderedCollections

• OrderedSet.replace(at:with:) replaces the member at a given index with a new element, returning the element that was removed. Replacing a member with an element that already exists elsewhere in the set is a runtime error. Expected amortized O(1) complexity. (#669)

BasicContainers, DequeModule

• On a Swift 6.4 or later toolchain, RigidArray, UniqueArray, RigidDeque, UniqueDeque, RigidSet, UniqueSet, RigidDictionary, and UniqueDictionary now formally conform to Equatable and Hashable. (The underlying == and hash(into:) members were already available in 1.6.0; what is new is the conformances themselves.) Building with Swift 6.2 or 6.3 still gets you the ==/hash(into:) members, but no conformances.

• RigidDeque.isTriviallyIdentical(to:) and UniqueDeque.isTriviallyIdentical(to:) are now available for every element type, including noncopyable ones. Previously these required Element: Equatable.

• New spelling for the capacity, cloning, and range-replacement operations; see Renamed APIs below. The new names are the stable spelling going forward; the old ones remain as deprecated shims.

Collections umbrella module

The Collections module is back to re-exporting its constituent modules with @_exported import, instead of restating each type as a public typealias (#716). A single
import Collections therefore now brings in the entire contents of BitCollections, DequeModule, HashTreeCollections, HeapModule, and OrderedCollections — including types that previously were not exposed in the Collections module, such as RigidDeque and UniqueDeque. This allows import Collections to work even for clients that have MemberImportVisibility enabled.

Renamed APIs

BasicContainers and DequeModule are stable modules, so every rename below ships with a deprecated shim carrying @available(*, deprecated, renamed:). Existing code keeps compiling, and Xcode/swift build will offer fix-its.

Most of the new names sync this package with the API names recently adopted in the Standard Library in Iterable and UniqueArray.

Performance improvements

• BitSet.count is roughly 3× faster. (#702)
• _Word.allBits is now @inlinable, which unblocks specialization in several
  bit-twiddling paths. (#704)
• OrderedSet.reverse() now reverses the hash table in place instead of
  rebuilding it from scratch. (#668)
• UniqueArray no longer performs duplicate bounds checks on subscript and
  mutation paths. (#699)
• RigidArray's internal representation was split from a (buffer pointer, count) pair into separate pointer, capacity, and count fields. This exposes an unused bit pattern for the compiler to use for representing nil values in optional wrapped arrays, avoiding having to add an out-of-line discriminator. The representation of RigidDictionary was
  adjusted in a similar way. (#692, #717)
• Deque and the TreeSet/TreeDictionary types are no longer using a malloc_size to make use of any "extra" storage allocated. (#700)
• OrderedDictionary.replaceElement now uses exchange(_:with:) on its equal-key path to avoid copying the outgoing value. (#688, #703)
• RigidDictionary now stores a sentinel value rather than nil for its values pointer, removing a branch from value access.

Notable bug fixes

• BitCollections: BitSet.isEqualSet(to:) returned the wrong result when given an empty Range<Int>. A non-empty bit set incorrectly compared equal to an empty range. (#718)
• SortedCollections (UnstableSortedCollections trait): SortedDictionary.Keys, .Values, and .SubSequence had inverted == implementations, so equal instances compared unequal and vice versa. SubSequence equality also now uses tuple comparison rather than an element-by-element loop with the wrong short-circuit. (#697)
• Embedded Swift: the _UniqueCollection fast paths in BitSet.isEqualSet(to:), OrderedSet.isEqualSet(to:), TreeSet.isEqualSet(to:), and TreeSet.symmetricDifference(_:) rely on dynamic conformance checks, which are unavailable in embedded Swift. They are now compiled out with #if !$Embedded. (#715)

Experimental container protocols (UnstableContainersPreview trait)

This is the first swift-collections release that ships a fully operational container protocol hierarchy, including some massive updates. However, things are still subject to change, and we expect to need to make breaking changes as we gain experience using the new constructs. Nothing under this trait is stable API, and source-breaking changes land without deprecations.

New: Documentation/Container-design.md is a work-in-progress document describing the container design implemented in the ContainersPreview module. As of the 1.7.0 release, it explains some of the design decisions behind the container protocols, up to and including MutableContainer. (The Producer hierarchy and the range-replaceable container protocol family is not yet fully covered; we expect those parts to be fleshed out later.)

New SpanPreview module

InputSpan has moved out of ContainersPreview into a new SpanPreview module. SpanPreview holds span-adjacent primitives that are expected to graduate to the standard library, and it is entirely empty unless the UnstableContainersPreview trait is enabled. It also ships basic MutableSpan/OutputSpan helpers for producing and consuming InputSpans.

Some core APIs on the container types require the use of InputSpan, and this change lets these APIs continue to live in their defining module.

SpanPreview is explicitly not part of the package's stable public API, as we expect to soon replace it with the Standard Library's own InputSpan definition.

Dependency inversion

ContainersPreview and the concrete container modules have swapped places in the dependency graph. BasicContainers and DequeModule no longer depend on ContainersPreview; instead ContainersPreview depends on them, and all
container conformances for the concrete types now live there, under Sources/ContainersPreview/Conformances/. (842f125c)

Source-breaking for trait adopters: getting Container (etc.) conformances for RigidArray, UniqueArray, RigidDeque, UniqueDeque, RigidSet, or UniqueSet now requires import ContainersPreview. Importing just BasicContainers or DequeModule gets you the types and their intrinsic operations, but not the protocol conformances.

Standard library adoption

• The locally-defined BorrowingSequence_/BorrowingIteratorProtocol_ protocols have been replaced by the standard library's Iterable and BorrowingIteratorProtocol. The package's own definitions have been removed. (#657)
• Similarly, Ref and MutableRef now ship in the Standard Library rather than being declared in ContainersPreview. (UniqueBox is part of the package's stable API, so its definition continues to remain available. We expect to deprecate it in a future package release.)

New protocols

• Removal and consumption operations were spun off from RangeReplaceableContainer into the new parent protocol DrainableContainer. This protocol models containers supporting partial in-place consumption (and removal) of their contents. Range-replacement operations now all return indices to the subranges they affected, so that we can perform insertions/removals without losing our place in the container. (This is particularly important for linked lists and similar linked data structures capable of performing O(1) insertions/removals.) (#723)
• CountedProducer refines Producer adding a precise count of remaining elements. Drain now refines CountedProducer.
• ContainerDrain refines Drain to allow retrieving a valid index after the items have been drained.
• RangeExpression2 now refines the standard RangeExpression, so that we can use the standard range expression notation over container types. (The name (as well as the protocol itself) is a placeholder, so that we have something that works while we are looking for a better solution.) (#22a94a97)

Reworked core requirements

• Container's core primitive is now nextSpan(after:maxCount:limitedBy:), with optional delimiter arguments; the
  bidirectional counterpart is spanBoundary(before:maxDistance:limitedBy:).
• Container gained makeBorrowingIterator(from:), makeBorrowingIterator(from:to:), and currentIndex(of:) requirements.
• Container now expects its indices to be Comparable again, as we have found a way to provide them in conforming linked list types. (#727)
• [Mutable]Container gained subscript requirements expressed with borrow and mutate accessors.
• Producer.generate(into:) switched to saturating semantics — it now fills the destination when possible, unless it reaches its end or throws. (#728)

New algorithms

• MutableContainer gained bulk update operations (updateSubrange and friends), in both mutating and copying forms, plus a default swapAt implementation for copyable elements. (#724)
• PermutableContainer gained reverse(), shuffle(), moveSubrange(_:to:), and a heap sort.
• Producer gained UnfoldProducer (an unfold-style generator), and
• BorrowingIteratorProtocol gained mapError, and map was fixed; _map2 and _map3 were added alongside it to demonstrate different throwing behaviors. Error handling across the producer/drain algorithms was reviewed.
• New Container conformances for Span, MutableSpan, OutputSpan, and InputSpan.

Experimental hashed containers (UnstableHashedContainers trait)

These types are functional, but they still have known usability gaps in their API surface that prevents us from declaring them API stable.

• The trait no longer needs UnstableContainersPreview to be enabled alongside it. 70dc2389)
• RigidSet and UniqueSet now conform to Container. (#713)
• RigidDictionary and UniqueDictionary gained a keys property and mutableValue(forKey:), which yields in-place mutable access to a stored value. (#698,

Testing and infrastructure

• checkSetAlgebra, a new law checker in _CollectionsTestSupport, verifies set-like types against the SetAlgebra laws — and additionally checks each mutating operation against its non-mutating twin. (#719, #730)
• A Container conformance validator has been added, along the lines of the existing Sequence/Collection conformance checkers, and is now applied to RigidSet, UniqueSet, RigidDeque, and UniqueDeque. (#713, #720)
• New tests cover Deque's storage allocation behavior and MutableContainer's requirements (the latter uncovered and fixed several issues). (#722)
• We added a first draft of a swift-format configuration for this package.
• CI workflows were updated (swiftlang/github-workflows 0.0.11 → 0.0.15, actions/checkout 6 → 7), and the matrix was simplified now that 6.0/6.1 are out of support.
• The unstable Xcode project had its groups converted to folders.

Detailed List of Changes

• Run heap node tests in release by @sorinc03 in #662
• [BasicContainers] Rename reallocate to setCapacity for Rigid and UniqueArray by @Azoy in #667
• Define SwiftStdlib 6.4 with actual version numbers by @lorentey in #670
• Update BorrowingSequence to Iterable by @natecook1000 in #657
• Bump swiftlang/github-workflows/.github/workflows/soundness.yml from 0.0.11 to 0.0.12 by @dependabot[bot] in #678
• Bump swiftlang/github-workflows/.github/workflows/swift_package_test.yml from 0.0.11 to 0.0.12 by @dependabot[bot] in #677
• Fix @inlinable deinit incompatibility with library evolution (HashTree/Sorted storage) by @itej13 in #679
• Bump actions/checkout from 6 to 7 by @dependabot[bot] in #672
• [OrderedCollections] OrderedSet.reverse(): update the hash table in place by @inju2403 in #668
• Fix superset set algebra doc comments by @wjdtjq6 in #674
• Fix typos in doc comments and a DocC article by @wjdtjq6 in #673
• [OrderedCollections] Add OrderedSet.replace(_:at:) by @inju2403 in #669
• Bump swiftlang/github-workflows/.github/workflows/soundness.yml from 0.0.12 to 0.0.13 by @dependabot[bot] in #689
• Bump swiftlang/github-workflows/.github/workflows/swift_package_test.yml from 0.0.12 to 0.0.13 by @dependabot[bot] in #690
• [ContainersPreview] Update Container protocols by @lorentey in #682
• [RigidArray/UniqueArray] Split up the buffer pointer in RIgidArray by @Azoy in #692
• Fix stale paths in internals documentation by @ZayanKhan-12 in #691
• More updates to the container model by @lorentey in #694
• More ContainersPreview updates by @lorentey in #695
• [Rigid/UniqueDictionary] Add mutableValue(forKey:) to new dictionary types by @Azoy in #698
• [OrderedCollections] Share OrderedSet's replace primitive with OrderedDictionary.replaceElement by @inju2403 in #688
• Fix inverted SortedDictionary Keys/Values/SubSequence equality by @Hashim1999164 in #697
• [Deque/HashTree] Remove references to ManagedBuffer.capacity and use the given minCapacity by @Azoy in #700
• [Rigid/UniqueArray] Eliminate some duplicate bounds checks for UniqueArray by @Azoy in #699
• Mark _Word.allBits as @inlinable by @dnadoba in #704
• Improve BitSet.count performance by ~3x by @dnadoba in #702
• [workflows] Update CI workflows by @lorentey in #706
• Name the documented arguments the way the declarations name them by @karpovantonme in #701
• [OrderedCollections] Use exchange(_:with:) in replaceElement's equal-key path by @inju2403 in #703
• [SortedCollections] Name the documented arguments the way the declarations name them by @karpovantonme in #705
• More container updates by @lorentey in #707
• Bump swiftlang/github-workflows/.github/workflows/swift_package_test.yml from 0.0.14 to 0.0.15 by @dependabot[bot] in #712
• Bump swiftlang/github-workflows/.github/workflows/soundness.yml from 0.0.14 to 0.0.15 by @dependabot[bot] in #711
• Conform RigidSet/UniqueSet to Container and add Container validator by @lorentey in #713
• Disable _UniqueCollection fast paths in embedded Swift by @lorentey in #715
• Reinstate exported imports in Collections module by @lorentey in #716
• [RigidDictionary] Store a sentinel value for values ptr if null by @Azoy in #717
• [BitSet] Fix isEqualSet(to: Range) for empty ranges by @dylanpulver in #718
• Refactor DrainableContainer/RangeReplaceableContainer/DynamicContainer by @lorentey in #723
• MutableContainer: Add some bulk update operations by @lorentey in #724
• Container: Reinstate requirement for Comparable indices by @lorentey in #727
• Add checkSetAlgebra, a law checker for set-like types by @Joseph-Cursio in #719
• Fix typos in documentation and comments by @eliorpom-cmd in #725
• [DequeModule] Add tests for Deque's storage allocation behavior by @Joseph-Cursio in #722
• Unbacktick parameter names so DocC binds the parameter docs by @hxperl in #721
• Validate the Container conformance of RigidDeque and UniqueDeque by @Joseph-Cursio in #720
• Producer.generate(into:): Switch to saturating semantics by @lorentey in #728
• Check the mutating form* twins against their non-mutating originals by @Joseph-Cursio in #730
• 1.7.0 release preparations by @lorentey in #729
• Finalize the 1.7.0 release by @lorentey in #731

New Contributors

• @sorinc03 made their first contribution in #662
• @itej13 made their first contribution in #679
• @wjdtjq6 made their first contribution in #674
• @ZayanKhan-12 made their first contribution in #691
• @Hashim1999164 made their first contribution in #697
• @karpovantonme made their first contribution in #701
• @dylanpulver made their first contribution in #718
• @Joseph-Cursio made their first contribution in #719
• @eliorpom-cmd made their first contribution in #725
• @hxperl made their first contribution in #721

Full Changelog: 1.6.0...1.7.0