apple/swift-collections 1.5.0

Swift Collections 1.5.0

on GitHub

This feature release supports Swift toolchain versions 6.0, 6.1, 6.2, and 6.3. It includes the following new features and bug fixes:

Debugging enhancements

The package now defines LLDB data formatters for RigidArray. The formatters are emitted into the executable binary, and they are automatically loaded by LLDB. We expect to implement formatters for (many) more types in subsequent releases.

New stable APIs

• RigidArray and UniqueArray now conform to Equatable when their element type is Equatable. This conformance requires a Swift 6.4 or later toolchain (it relies on SE-0499 generalizations of Equatable/Hashable to support noncopyable conforming types).
• RigidArray and UniqueArray gained an isTriviallyIdentical(to:) operation, which reports whether two instances share their underlying storage allocation. This does not require the element type to be Equatable, and it works with noncopyable elements.
• BitSet gained a makeIterator(from:) shortcut for starting iteration at (or after) a specific member, avoiding a linear scan from the start of the set.
• OrderedDictionary gained a replaceElement(at:withKey:value:) operation that replaces the key-value pair at a given index. The new key is allowed to equal the existing key at that index (in which case only the value is updated).

Experimental hashed containers (UnstableHashedContainers trait)

The Robin-Hood-hashed UniqueSet, RigidSet, UniqueDictionary, and RigidDictionary types in the BasicContainers module continue to evolve behind the UnstableHashedContainers package trait. This release brings a number of correctness fixes and performance improvements:

• Faster removals, with better maxProbeLength maintenance to avoid probe-length bloat.
• Small tables are now scrambled to avoid degenerate patterns on common key distributions.
• A fast-path shortcut for insertions into under-utilized tables.
• Fixes to the insertion algorithm and to RigidDictionary.updateValue(forKey:with:) (the latter exhibited undefined behavior on removals).
• RigidSet.insert(maximumCount:from:) no longer spuriously reports a capacity overflow due to incorrect accounting.
• The UnstableHashedContainers trait can now be enabled independently of UnstableContainersPreview.

These types remain source-unstable for now.

Experimental sorted collections (UnstableSortedCollections trait)

The SortedCollections module's SortedSet has gained the following additions:

• SortedSet now supports value-range subscripts for the full variety of standard range expression types, ClosedRange, PartialRangeFrom, PartialRangeThrough, and PartialRangeUpTo.
• SortedSet.firstIndex(after:) and SortedSet.lastIndex(before:) return the index to the nearest member following or preceding a given value.

This release also fixes several underlying B-tree bugs that were surfaced by these additions.

These types remain source-unstable; they have known API deficiencies that will need to be addressed before they ship.

Experimental container protocols (UnstableContainersPreview trait)

The ContainersPreview module's protocol hierarchy and associated types continue to be developed. Several constructs have been renamed to follow Swift Evolution proposals in flight.

For UniqueBox, Ref and MutableRef, there are deprecated typealiases for the old names, preserving source compatibility.

Other changes to the experimental container model:

• Container.Index no longer needs to conform to Comparable. This allows linked lists to become containers.
• RigidArray, UniqueArray, RigidDeque, and UniqueDeque now conform to the container protocols.
• Added Producer.collect(into:) for collecting a producer's output into a RangeReplaceableContainer.
• Added BorrowingIteratorProtocol.copy() for turning a borrowing iterator into a producer.
• Added filter and map overloads for BorrowingIteratorProtocol, Producer, and Drain.
• BorrowingSequence.first was removed.
• BorrowingSequence, BorrowingIteratorProtocol and their requirements have temporarily gained trailing underscores to avoid naming conflicts with the (provisional) protocol definition in the Standard Library. We expect these definitions to be removed when these protocols officially become part of the stdlib.

The protocol-based APIs in ContainersPreview now require a Swift 6.4 or later toolchain. UniqueBox is source-stable, therefore it continues to require Swift 6.2.

Notable bug fixes

• HashTreeCollections: Fixed an invariant violation that could be triggered by some operations on TreeSet/TreeDictionary.
• _RopeModule: Fixed an infinite loop when hashing the UTF-8 view of a multi-chunk big substring.
• BitCollections: Fixed a bogus precondition in BitArray.insert(repeating:count:at:); fixed BitSet.isSubset(of: Range<Int>) to correctly examine elements above the range's upper word.
• HeapModule: Fixed Heap.insert(contentsOf:) to use a wrapping multiply in its Floyd-heuristic computation; added a missing bounds assertion in Heap._UnsafeHandle.swapAt(_:with:).
• OrderedCollections: Fixed OrderedSet crash on negative capacity values; minor fixes in _HashTable.UnsafeHandle.
• DequeModule: Fixed sizing issue in UniqueDeque.replace(removing:addingCount:initializingWith:); fixed a missing argument validation in RigidDeque.nextMutableSpan(after:maximumCount:); RigidDeque.consume(_:consumingWith:) now closes the resulting gap before returning; added zero-count fast-paths; replace/prepend operations taking a Collection now verify that the source's count matches its contents.
• BasicContainers: Fixed an overallocation issue in UniqueArray.replace(removing:copying:); fixed a partial-initialization correctness issue in RigidArray.replace(removing:consumingWith:addingCount:initializingWith:).

What's Changed

• Add tests that build the ContainersPreview module by @natecook1000 in #610
• Add a workflow that performs a CMake build by @natecook1000 in #612
• Align BorrowingSequence implementation with proposal by @natecook1000 in #609
• Bump swiftlang/github-workflows/.github/workflows/swift_package_test.yml from 0.0.8 to 0.0.9 by @dependabot[bot] in #615
• Bump swiftlang/github-workflows/.github/workflows/soundness.yml from 0.0.8 to 0.0.9 by @dependabot[bot] in #614
• Fix lifetime requirements rigidly enforced in the latest nightlies by @lorentey in #617
• Track array proposal by @lorentey in #619
• Bump swiftlang/github-workflows/.github/workflows/soundness.yml from 0.0.9 to 0.0.10 by @dependabot[bot] in #620
• OrderedSet: Don't crash on negative capacity values by @thisismanan in #622
• [ContainersPreview] Don’t require Container.Index to conform to Comparable by @lorentey in #623
• Adjust experimental workflows by @lorentey in #626
• BitSet Add BitSet.makeIterator(from:) by @lorentey in #627
• [BasicContainers] RigidSet.insert(maximumCount:from:): Fix spurious capacity overflow caused by incorrect accounting by @lorentey in #628
• [BasicContainers] RigidArray.replace(removing:consumingWith:addingCount:initializingWith:): Fix correctness issue with partial initialization by @lorentey in #629
• [BasicContainers] UniqueArray.replace(removing:copying): Fix overallocation issue by @lorentey in #630
• Fix _trim(first:) returning wrong buffer region by @FranzBusch in #631
• Bump swiftlang/github-workflows/.github/workflows/soundness.yml from 0.0.10 to 0.0.11 by @dependabot[bot] in #625
• [OrderedCollections] Add OrderedDictionary.replaceElement(at:withKey:… by @inju2403 in #616
• [ContainersPreview] Producer.ProducerError ⟹ Producer.Failure by @lorentey in #634
• fix: reserveCapacity DocC link in RigidArray by @manojmahapatra in #633
• [BasicContainers, DequeModule]: Assorted fixes by @lorentey in #632
• [Debugging] Add lldb data formatter for RigidArray by @kastiglione in #607
• [HashTreeCollections] Fix invariant violation in _HashNode._regularNode by @lorentey in #635
• [BitCollections] Fix small issues by @lorentey in #637
• [HeapModule, SortedCollections] Assorted tool-assisted fixes and adjustments by @lorentey in #639
• [BasicContainers] Enable APIs scheduled to ship in 1.5.0 by @lorentey in #641
• [BasicContainers] Fix copypasta in UniqueArray.edit’s docs by @lorentey in #642
• Rename Box to UniqueBox; align API surface with SE-0517 by @lorentey in #640
• Bump swiftlang/github-workflows/.github/workflows/swift_package_test.yml from 0.0.9 to 0.0.11 by @dependabot[bot] in #624
• Use the defines from traits directly by @FranzBusch in #644
• [ContainersPreview] struct Borrow ⟹ struct Ref by @lorentey in #643
• [ContainersPreview] struct Inout ⟹ struct MutableRef by @lorentey in #646
• 1.5.0 release preparations by @lorentey in #647

New Contributors

• @thisismanan made their first contribution in #622
• @FranzBusch made their first contribution in #631
• @inju2403 made their first contribution in #616
• @manojmahapatra made their first contribution in #633
• @kastiglione made their first contribution in #607

Full Changelog: 1.4.1...1.5.0