apple/swift-collections

This system is the Swift Collections library, providing a comprehensive suite of data structures including deques, ordered collections, hash trees, heaps, bitsets, and ropes. It extends standard Swift types with specialized implementations like BigString and TreeSet, while introducing experimental support for non-copyable types and span-based iteration in Swift 6.4. The project also includes a robust benchmarking framework that compares these collections against C++ and Rust implementations to validate performance and memory efficiency.

27 changes.

This period focused on introducing the new SortedCollections module, including initial implementations of B-Tree, SortedDictionary, and SortedSet under experimental feature flags. Concurrently, the codebase underwent significant modernization by adopting Swift 5.5 concurrency features, updating to the Swift 6.2 toolchain, and refactoring core types like Deque and OrderedDictionary for improved safety and performance. The work also included expanding BitCollections with standard library conformances and overhauling project infrastructure and documentation.

28 changes.

This period focused on introducing major new data structures, including the experimental Rope and BigString types for efficient large string handling, as well as the persistent TreeSet and enhanced TreeDictionary. Concurrently, the project significantly expanded its benchmarking infrastructure to include comprehensive performance comparisons against C++ and Foundation libraries, alongside rigorous memory usage analysis. These features were supported by extensive test coverage, internal refactoring of core modules like Heap and HashNode, and improved tooling for Xcode and Swift 6 compatibility.

27 changes.

This period focused on implementing comprehensive support for Swift 6.4's non-copyable and borrowing semantics across the collections library. It introduced new container types like RigidArray, UniqueDeque, and RigidSet, while overhauling existing APIs to use span-based mutation and consumption primitives. The work also included adding internal utilities, performance optimizations, and extensive test coverage to ensure correctness for these ownership-aware features.

The benchmark suite now includes performance comparisons against C++ standard library containers (std::vector, std::deque, std::map, std::unordered\_map, std::unordered\_set, std::priority\_queue, and std::vector\<bool\>) and Apple Foundation types (CFBinaryHeap, CFBitVector). These new benchmarks allow users to measure the performance of Swift Collections relative to established C++ and Foundation implementations for common data structure operations.

Benchmarks/Sources/Benchmarks/Cpp, Benchmarks/Sources/Benchmarks/Foundation · high confidence

A new LLDB synthetic provider (RigidArray.py) has been added to the debugger utilities, enabling more readable inspection of RigidArray instances during debugging sessions. The formatter exposes the internal storage and count, allowing developers to view individual elements directly in the debugger rather than seeing opaque memory structures.

Utils/Debugger/Formatters · high confidence

This change introduces a new benchmarking module for Rust-based VecDeque implementations within the Swift Collections benchmarking suite. The new files, \RustBenchmarks.swift\ and \RustVecDequeBenchmarks.swift\, define a set of performance tests for Rust VecDeque operations including creation from ranges and buffers, push\_back/push\_front with and without capacity reservation, random insertions, and sequential iteration. These benchmarks are gated by the \EnableRustBenchmarks\ compile-time flag and interact with Rust code via C FFI bindings (\rust\vecdeque\\*\ functions).

Benchmarks/Sources/Benchmarks/Rust · high confidence

A new Swift Package Plugin named RustBuild has been added to the Benchmarks/Plugins directory. This plugin enables the automatic compilation of .rs (Rust) source files included in a Swift target into a static library (lib{name\>.a) using the system's rustc compiler. Users can now integrate Rust code directly into their Swift package targets, with the build process handling the invocation of the Rust toolchain to produce the necessary static library artifact.

Benchmarks/Plugins/RustBuild · high confidence

A new command-line tool, \memory-statistics\, has been added to the \memory-benchmark\ package to measure and compare the memory efficiency of standard \Dictionary\ and \TreeDictionary\ collections. The tool iterates through specified collection sizes, calculates memory usage statistics (such as capacity, item bytes, and gross bytes) for both types, and outputs a CSV report along with average efficiency metrics and node depth details for \TreeDictionary\.

Benchmarks/Sources/memory-benchmark · high confidence

New benchmark source files have been added to the RustBenchmarks module to measure the performance of \std::collections::VecDeque\ operations. The Rust implementation exposes C-compatible functions for creating, destroying, and manipulating deques via integer ranges, buffers, and random insertions, alongside iteration benchmarks. A corresponding Swift file with standard license headers was also added to the module.

Benchmarks/Sources/RustBenchmarks · high confidence

Developers can now iterate over \BigString\ and \BigSubstring\ at different Unicode granularities using new \utf8\, \utf16\, and \unicodeScalars\ properties. These views conform to \BidirectionalCollection\ and \Sequence\, allowing efficient, index-based traversal of the underlying rope structure without materializing a full \String\. The views are available on Swift 6.2+ and are excluded from embedded environments.

Sources/RopeModule/BigString/Views · high confidence

BigString now conforms to key Swift standard library protocols including BidirectionalCollection, Sequence, Equatable, Hashable, Comparable, CustomStringConvertible, and RangeReplaceableCollection. These additions enable idiomatic usage such as iteration, indexing, comparison, hashing, and mutable operations like appending or replacing substrings. The conformances are gated behind availability macros requiring Swift 6.2 and are excluded from embedded environments.

Sources/RopeModule/BigString/Conformances · high confidence

The BigString type is now available on platforms with Swift 6.2 or later, provided the target is not embedded. This new implementation uses a B-tree (rope) structure to efficiently manage large strings, offering optimized operations for indexing, distance calculations, and building strings from chunks. It includes a dedicated Builder for efficient appending and supports various string metrics (characters, unicode scalars, UTF-16, UTF-8) for accurate indexing and distance computations.

Sources/RopeModule/BigString/Basics · high confidence

BitArray now conforms to several Swift standard protocols, enabling it to be used as a Collection, Hashable, Equatable, Codable, and LosslessStringConvertible (with descriptions formatted as binary strings in angle brackets). New capabilities include converting between BitArray and BinaryInteger types, generating random bits via randomBits(count:using:), and manipulating bit sequences with truncateOrExtend, toggleAll, fill, insert, and append methods.

Sources/BitCollections/BitArray · high confidence

The BitSet type in the BitCollections module has been significantly expanded with new conformances and methods. It now conforms to SetAlgebra, providing standard set operations like intersection, union, symmetricDifference, and predicates such as isSubset, isSuperset, and isDisjoint, with overloads that accept other BitSets, ranges, and sequences. It also conforms to Collection and BidirectionalCollection, allowing iteration over set members and subscript access by index. Additional features include Codable support for serialization, Hashable and Equatable conformances, ExpressibleByArrayLiteral for convenient initialization, and random generation utilities. Convenience subscripts for member membership checks and range-based slicing have also been added.

Sources/BitCollections/BitSet · high confidence

The benchmark suite in Benchmarks/Sources/Benchmarks has been significantly expanded and reorganized. New benchmark files have been added for BigString, BitSet, BitArray, Heap, RigidDeque, TreeSet, and UniqueDeque, covering operations such as initialization, iteration, insertion, and removal. Existing benchmarks for Deque, Dictionary, OrderedDictionary, and OrderedSet have been updated to include new test cases for index-based iteration, subscript modification, equality checks (both unique and shared), and specific API behaviors like move operations. Additionally, source files were moved from Benchmarks/Benchmarks to Benchmarks/Sources/Benchmarks, copyright dates were updated to 2026, and SPDX license identifiers were added.

Benchmarks/Sources/Benchmarks · high confidence

The new \SortedDictionary\ type is now available under the \UnstableSortedCollections\ feature flag, providing a collection that maintains its key-value pairs in sorted order. It conforms to \BidirectionalCollection\, \Sequence\, \Equatable\, \Hashable\, \Codable\, and \ExpressibleByDictionaryLiteral\, and exposes \Keys\ and \Values\ views that also conform to \BidirectionalCollection\. The type supports efficient construction from pre-sorted sequences via \sortedKeysWithValues\, allows grouping elements by a key closure, and provides standard mutation methods such as \filter\, \removeAll\, and indexed removal.

Sources/SortedCollections/SortedDictionary · high confidence

The internal \\_BTree\ type is now available under the \UnstableSortedCollections\ feature flag, providing the foundational B-Tree implementation for the SortedCollections library. This change introduces the core data structure along with its essential components: a path-based \Index\ for traversal, \BidirectionalCollection\ and \Sequence\ conformance for iteration, a \Builder\ for efficient bulk construction, and an \UnsafeCursor\ for mutable operations. It also includes support for sub-sequences, debug/reflectable representations, and internal invariant checking to ensure data integrity.

Sources/SortedCollections/BTree · high confidence

The InternalCollectionsUtilities module has been expanded with new internal helpers to support Swift 6.4's borrowing iterator protocol and non-copyable types. This includes \_elementsEqual implementations for BorrowingIteratorProtocol and Iterable, span-based iteration helpers like \_nextSpan and \_makeBorrowingIterator on Span, and additional operations for OutputSpan and MutableSpan such as \_append, \_popLast, \_updateSubrange, and \_trim. The module also adds integer bit-manipulation utilities (e.g., \_roundUpToPowerOfTwo, \_rank, \_bit), lifetime override primitives (\_unsafeImmortalize, \_overrideLifetime), a temporary allocation polyfill (\_withUnsafeTemporaryAllocation), and debugging/description helpers. These changes are gated by compiler version checks and are intended to improve performance and correctness for non-copyable collection operations in Swift 6.4+.

Sources/InternalCollectionsUtilities · high confidence

Adds the \RigidDictionary\ type to the \BasicContainers\ module, providing a dictionary implementation designed for non-copyable (\\~Copyable\) keys and values. This new container supports standard dictionary operations including insertion (\insertValue\, \updateValue\), lookup (\containsKey\, \value\, \mutableValue\), and removal (\removeValue\, \removeAll\). It also exposes iteration capabilities via indices and keys, along with \Equatable\ and \Hashable\ conformances when the underlying types support them. The implementation is gated behind the \UnstableHashedContainers\ feature flag and requires a Swift 6.4 toolchain.

Sources/BasicContainers/RigidDictionary · high confidence

The \Sources/BasicContainers/RigidSet\ module now provides \RigidSet\, a new fixed-capacity, noncopyable hashed container for unique elements. Available on Swift 6.4+ with the \UnstableHashedContainers\ feature, it supports standard operations including initialization, insertion, removal, lookup, and iteration via indices and borrowing iterators. The container also conforms to \Equatable\ and \Hashable\, offers bulk insertion and consumption methods, and includes debugging utilities for inspecting internal hash table structures.

Sources/BasicContainers/RigidSet · high confidence

The new \SortedSet\ type provides a collection that maintains unique elements in ascending sorted order, conforming to \SetAlgebra\, \BidirectionalCollection\, and \Sequence\. Users can create sets from sequences, use array literals, and perform standard set operations like union, intersection, and symmetric difference. The collection supports efficient index-based navigation, value-range subscripts for slicing by element bounds, and serialization via \Codable\. It is currently available under the \UnstableSortedCollections\ feature flag.

Sources/SortedCollections/SortedSet · high confidence

A new TrailingElementsModule has been added to provide facilities for managing memory with a header followed by trailing data. This module introduces the TrailingArray type, which manages a contiguous block of memory starting with a header and followed by a contiguous array of elements, including support for headers with greater alignment than the elements. It also includes the TrailingPadding type for opaque extra padding following a header, and the TrailingElements protocol to define the interface for such header types.

Sources/TrailingElementsModule · high confidence

The \TreeSet\ type is now available in the \HashTreeCollections\ module, providing a persistent (immutable) set backed by a hash tree. Users can create sets from array literals, sequences, or other \TreeSet\ instances, and perform standard \SetAlgebra\ operations such as union, intersection, symmetric difference, and subset checks. The collection supports efficient insertion, removal, and containment checks, with indices that are invalidated upon mutation of any instance sharing the underlying tree structure. It also conforms to \Collection\, \Sequence\, \Hashable\, \Equatable\, and \Sendable\ (when elements are \Sendable\), enabling iteration, debugging, and safe concurrent access.

Sources/HashTreeCollections/TreeSet · high confidence

Adds the \UniqueDictionary\ type to the \BasicContainers\ module, providing a hashed dictionary that enforces unique keys and supports Swift's ownership model (consuming keys and values). Available under the \UnstableHashedContainers\ feature flag with a Swift 6.4+ toolchain, it offers standard dictionary operations including insertion (\insertValue\, \updateValue\), lookup (\containsKey\, \value\, \mutableValue\), removal (\removeValue\, \removeAll\), and iteration via indices. The type also conforms to \Equatable\ and \Hashable\ when its value type does, and includes debugging methods like \\_checkInvariants\ and \\_describe\ to assist with internal state verification.

Sources/BasicContainers/UniqueDictionary · high confidence

A new \UniqueSet\ type is added to the \BasicContainers\ module, providing a hashed set implementation that ensures element uniqueness. The diff introduces the full structural definition and API surface for this container, including initialization, insertion, removal, and lookup operations, as well as conformance to \Equatable\, \Hashable\, and \Iterable\ protocols. It also includes debugging support, index-based iteration, and capacity management features, all gated behind the \UnstableHashedContainers\ feature flag and requiring Swift 6.4 or later.

Sources/BasicContainers/UniqueSet · high confidence

The ContainersPreview module now exposes the \Producer\ and \Drain\ protocols, enabling iteration over container elements by transferring ownership directly to the caller via \OutputSpan\ and \InputSpan\ instances. This change introduces a new consumption-based iteration model that avoids temporary buffers, allowing clients to generate, map, filter, reduce, and collect elements in bulk. The diff adds the core \Producer\ protocol with \generate(into:)\ and \next()\ methods, along with extensions for \map\, \filter\, \reduce\, \collect\, and \unfold\, as well as the \Drain\ protocol for consuming sequences in bulk spans. These APIs are available on Swift 6.4+ with the \UnstableContainersPreview\ flag.

Sources/ContainersPreview/Protocols/Producer · high confidence

Adds a new experimental \Rope\ type to the Swift Collections library, providing an ordered, tree-organized data structure for elements that support custom metrics and summaries. This change introduces the core implementation files in \Sources/RopeModule/Rope/Basics\, including the \Rope\ struct itself, its internal node and storage management (\\_Node\, \\_Storage\), and supporting protocols (\RopeElement\, \RopeSummary\, \RopeMetric\) that enable efficient lookup and mutation operations. The addition also includes a \Builder\ for constructing ropes, debugging utilities for tree visualization, and invariant checks to ensure structural correctness during development.

Sources/RopeModule/Rope/Basics · high confidence

Adds a new internal \UnsafeBitSet\ collection utility in \Sources/InternalCollectionsUtilities\, providing a low-level, unsafe-unowned bitset view over \UInt\ storage. This includes the core \\_UnsafeBitSet\ struct for managing word-based storage, a \\_Word\ extension for bit manipulation primitives (such as counting, setting, and clearing bits), and an \Index\ type to map between linear indices and word/bit positions, enabling efficient bit-set operations for internal use.

Sources/InternalCollectionsUtilities/UnsafeBitSet · high confidence

The \ContainersPreview\ module now provides a new set of container protocols (\Container\, \BidirectionalContainer\, \MutableContainer\, \DrainableContainer\, etc.) designed for Swift 6.4+ that replace traditional index-based access with span-based iteration. Users can now efficiently process contiguous chunks of storage using \nextSpan\ and \nextMutableSpan\, enabling bulk operations like filtering, zipping, and updating without per-element overhead. The API also includes new capabilities for draining elements (\DrainableContainer\), mutable bulk updates (\MutableContainer\), and permutation algorithms like heap sort and shuffle (\PermutableContainer\).

Sources/ContainersPreview/Protocols/Container · high confidence

The ContainersPreview module now includes new internal types, UniqueBox and Shared, to support noncopyable and copy-on-write semantics. UniqueBox provides a heap-allocated wrapper for noncopyable values, with its implementation branching based on the Swift compiler version: it uses standard unsafe pointer operations for Swift 6.2–6.3 and leverages new borrow/mutate syntax for Swift 6.4+. Shared offers a copy-on-write adapter for noncopyable storage, enabling efficient value semantics through unique-reference tracking. These types are currently behind a \#if false guard in Shared.swift, indicating they are part of the preview infrastructure but not yet active in the public API.

Sources/ContainersPreview/Types · high confidence

Developers can now open and build the Collections library directly in Xcode using the new \Collections.xcodeproj\. This project includes build schemes for the main \Collections\ framework and the \ContainersPreview\ framework, along with their respective test targets, allowing for native IDE support for development and debugging.

Xcode/Collections.xcodeproj · high confidence

For users on Swift 6.4 with the UnstableContainersPreview flag enabled, the library now provides a suite of new methods on BorrowingIteratorProtocol and Iterable that operate on non-copyable, non-escapable elements. These additions include copy() to explicitly convert a borrowing iterator into a producer, elementsEqual() for comparing sequences, filter() and map() (with public map and internal \_map2/\_map3 variants) for transformation, mapError() for error handling, reduce() and reduce(into:) for accumulation, and \_spanwiseZip() for pairing spans from two iterators. These APIs allow efficient, borrow-based processing without implicit copying, making the cost of element duplication explicit when using copy().

Sources/ContainersPreview/Protocols/Iterable · high confidence

OrderedSet now supports a comprehensive suite of PartialSetAlgebra operations, including mutating methods like formUnion, formIntersection, and formSymmetricDifference, as well as non-mutating checks such as isSubset, isSuperset, isDisjoint, and isEqualSet. These methods accept other OrderedSets, sequences, or the unordered view, allowing users to perform standard set logic while preserving element order. Additionally, a new diffing capability (difference and applying) enables users to compute and apply changes between two OrderedSet instances, facilitating efficient state synchronization.

Sources/OrderedCollections/OrderedSet · high confidence

The \Documentation/Announcement-benchmarks\ directory now contains the complete set of files used to generate the performance charts in the Swift Collections announcement on swift.org. This includes \Library.json\ and \Theme.json\ for defining chart structures and visual styling, \generate-results.sh\ to reproduce the measurements, \results.json\ with the raw collected data, and \Results.md\ with the rendered summary. Users can now inspect the specific benchmark tasks (such as Deque, OrderedSet, and OrderedDictionary operations) and reproduce the results on their own machines.

Documentation/Announcement-benchmarks · high confidence

The Rope type in the Conformances module now implements the Swift standard library's Sequence and BidirectionalCollection protocols. This enables users to iterate over rope elements using standard for-in loops and provides bidirectional index navigation (prev/next), along with index validation and caching mechanisms to optimize traversal performance.

Sources/RopeModule/Rope/Conformances · high confidence

InputSpan, Span, MutableSpan, OutputSpan, RigidArray, RigidDeque, RigidSet, UniqueArray, UniqueDeque, and UniqueSet now implement the Container family of protocols (including Container, MutableContainer, RandomAccessContainer, BidirectionalContainer, DrainableContainer, RangeReplaceableContainer, and DynamicContainer where applicable). This enables these types to be used with standard container algorithms and provides unified iteration via makeBorrowingIterator and currentIndex, along with span-based traversal methods like nextSpan and spanBoundary. The conformances are available on Swift 6.4+ via the UnstableContainersPreview flag, with some basic index properties available on earlier versions.

Sources/ContainersPreview/Conformances · high confidence

The \TreeDictionary\ type in \Sources/HashTreeCollections/TreeDictionary\ now conforms to \Codable\, \Collection\, \Hashable\, \Equatable\, \CustomStringConvertible\, \CustomDebugStringConvertible\, \CustomReflectable\, and \ExpressibleByDictionaryLiteral\. This enables encoding and decoding \TreeDictionary\ instances to and from JSON and other formats (with optimized paths for String and Int keys), allows iteration using standard Swift collection APIs, supports use as dictionary keys or set elements via \Hashable\, and permits initialization from dictionary literals.

Sources/HashTreeCollections/TreeDictionary · high confidence

The UniqueDeque type in the DequeModule now exposes a comprehensive set of methods for managing elements, specifically designed for non-copyable types. Users can append, prepend, and insert elements using callbacks that populate OutputSpans, or by moving elements from UnsafeMutableBufferPointers and Input/OutputSpans. The type also includes methods to consume subranges, the entire deque, or specific counts from the front or back via InputSpan callbacks, as well as standard removal methods like remove(at:) and removeSubrange. Additionally, UniqueDeque now conforms to Equatable and Hashable (where supported by the compiler version) and provides a clone() method for copying instances.

Sources/DequeModule/UniqueDeque · high confidence

The \Uniqued\ type, which provided an ordered collection of unique elements with hash-table-backed lookups, has been removed from the \Sources/UniquedModule\. This deletion eliminates the entire public API surface for this collection, including its initializers, mutation methods (such as \append\, \insert\, \remove\, and \sort\), \SetAlgebra\ operations (like \union\ and \intersection\), and collection conformances (\RandomAccessCollection\, \Sequence\). Users relying on \Uniqued\ for ordered, deduplicated data will no longer have access to this type or its associated internal storage mechanisms.

Sources/UniquedModule · high confidence

The internal \\_UnsafeBitset\ struct and its associated extensions have been removed from the \Sources/OrderedCollections/Utilities\ module. This change eliminates the local bitmap implementation that was previously used for temporary storage and bit manipulation within the collections library.

Sources/OrderedCollections/Utilities · high confidence

This change introduces a set of internal utility files in the RopeModule to support the new rope implementation. It adds an Optional extension for taking values, StringProtocol extensions for efficient index and offset calculations, and a String.Index ABI layer to expose internal bit-level details required for rope indexing. It also includes a \_CharacterRecognizer wrapper that adapts to Swift 6.2's Unicode API and provides logic for detecting character breaks, along with a specialized debug description for strings that properly handles quoting and escaping.

Sources/RopeModule/Utilities · high confidence

The BigString mutation operations (append, insert, remove, replace, split) and their supporting initializers are now gated behind the @available(SwiftStdlib 6.2, \*) macro, meaning they are only available when compiling with Swift 6.2 or later. Additionally, these operations are conditionally compiled out when the $Embedded flag is set, making BigString modifications unavailable in embedded environments. This change aligns with the broader adoption of modern generic declaration syntax and the dropping of support for Swift 6.0 and 6.1.

Sources/RopeModule/BigString/Operations · high confidence

The internal BigString.\_Chunk implementation has been rewritten to use a Swift ManagedBuffer for UTF-8 storage, replacing the previous structure. This change introduces a new compact Index type that encodes UTF-8 offsets alongside alignment and surrogate flags, enabling precise character, scalar, and UTF-16 index navigation. The chunk now maintains detailed Counts (UTF-8, UTF-16, Unicode scalars, and character boundaries) to support efficient splitting, merging, and rebalancing operations within the rope structure.

Sources/RopeModule/BigString/Chunk · high confidence

BitSet now uses a platform-independent Codable encoding that packs 32-bit words into 64-bit containers to ensure consistent serialization across architectures. The change also introduces internal Range and UInt utility extensions for bit manipulation and bounds clamping, and moves shared slice utilities into the BitCollections module.

Sources/BitCollections/Shared · high confidence

The CMake build configuration has been updated to organize installed Swift libraries and modules into platform- and architecture-specific folders (e.g., \lib/swift/macos/arm64\). This change introduces logic to automatically detect the target architecture and platform from the Swift compiler's target info, ensuring that the installed artifacts are correctly structured for consumption by downstream projects and tools.

cmake · high confidence

The Collections umbrella module now re-exports its constituent modules (BitCollections, DequeModule, HashTreeCollections, HeapModule, and OrderedCollections) via @\_exported import statements, but only when the COLLECTIONS\_SINGLE\_MODULE build flag is not set. This change allows users to import the Collections module and access types from its submodules directly, while supporting a single-module build mode that omits these re-exports to reduce path lengths and build complexity.

Sources/Collections · high confidence

The C++ benchmark sources have been reorganized under the Benchmarks/Sources/CppBenchmarks directory, with all files moved from the previous CppBenchmarks root. This change introduces new benchmark implementations for std::map, std::priority\_queue, and std::vector\<bool\>, alongside updated headers and source files for existing benchmarks (deque, vector, unordered map/set, hashing). The module map has been updated to include the new headers, and license headers have been standardized with updated copyright dates (2021–2026) and SPDX identifiers. A minor fix corrects the include path for the Utils header across all benchmark source files.

Benchmarks/Sources/CppBenchmarks · high confidence

The Deque implementation in this location has been optimized for performance and consistency. Equality checks now short-circuit by comparing counts and checking for referential identity before iterating elements. Storage growth now uses integer arithmetic instead of floating-point calculations to avoid precision issues. The \prepend\ method has been updated to accept \some Collection\ and \some Sequence\ protocols, and internal memory initialization methods have been standardized. Additionally, the \Deque\ type now conforms to \Sendable\ when its element type is \Sendable\, and various internal types have been renamed or restructured for clarity.

Sources/DequeModule/Deque · high confidence

The benchmark tool now includes tests for additional collection types, specifically TreeDictionary, RigidDeque, UniqueDeque, Heap, BitSet, BitArray, TreeSet, BigString, and Foundation (on Apple platforms). It also conditionally includes Rust benchmarks and sorted collection benchmarks (SortedSet, SortedDictionary) when the UnstableSortedCollections flag is enabled. Additionally, the tool now warns users if internal consistency checking is enabled, as this invalidates performance guarantees.

Benchmarks/Sources/benchmark-tool · high confidence

The internal \\_HashTable\ implementation in \Sources/OrderedCollections/HashTable\ has shifted from \internal\ to \package\ access, exposing types like \Bucket\, \BucketIterator\, and \UnsafeHandle\ to the module's consumers. This change also replaces the previous floating-point arithmetic for load factor calculations with integer-based rational number tuples (e.g., \(3, 4)\), ensuring precise capacity and scale computations. Additionally, a fast-path optimization for duplicate detection in unhashed collections was added to improve performance when element types are not known at compile time.

Sources/OrderedCollections/HashTable · high confidence

The Heap module has been reorganized into a dedicated \HeapModule\ package, introducing a new \\_HeapNode\ internal type to manage heap tree structure and a \\_UnsafeHandle\ for low-level buffer operations. The build system now supports a single-module mode via CMake, allowing the heap to be built as part of a larger collection module. Additionally, the module now includes an \ExpressibleByArrayLiteral\ conformance for convenient initialization, a \reserveCapacity\ method to optimize memory allocation, and updated description conformances for better debugging output.

Sources/HeapModule · high confidence

The DequeModule sources have been restructured to support Swift 5.5, introducing ownership and lifetime safety features such as \\~Copyable\ constraints on internal types like \\_UnsafeDequeHandle\ and \\_UnsafeDequeSegments\. The module now uses \@\_alwaysEmitIntoClient\ and \@\_transparent\ attributes to optimize inlining, and exposes \\_DequeSlot\ as a \package\ type for better internal visibility. Several legacy protocol conformances (\MutableCollection\, \RandomAccessCollection\, \RangeReplaceableCollection\, \Sequence\) and utility extensions have been removed or consolidated, reflecting a shift toward a more modern, efficient, and safer internal implementation.

Sources/DequeModule · high confidence

The Utils directory now includes new maintenance scripts: \generate-docs.sh\ for automating API documentation generation, \run-full-tests.sh\ for exercising the package across many build configurations (SPM, CMake, xcodebuild) and platforms before release, and \shuffle-sources.sh\ to help reproduce nondeterministic compiler issues. The existing \run-benchmarks.sh\ script has been updated to invoke \swift\ through \xcrun\ on Darwin and changed to run the \benchmark\ command instead of \swift-collections-benchmark\, reflecting a shift in the benchmarking sub-package structure.

Utils · high confidence

This update refines the OrderedDictionary API for better type safety and concurrency readiness. The index type for the Elements and Values views is now explicitly Int, simplifying iteration and subscripting. Several deprecated methods, including \subscript(offset:)\ and \modifyValue\, have been obsoleted in favor of \elements\[offset\]\ and \updateValue\. A new \replaceElement(at:withKey:value:)\ method allows efficient in-place key replacement. The type now explicitly conforms to Sendable when its Key and Value types are Sendable, and internal descriptions are unified via the InternalCollectionsUtilities module.

Sources/OrderedCollections/OrderedDictionary · high confidence

This change introduces several new configuration files to standardize the development environment and improve project visibility. An \.editorconfig\ file is added to enforce consistent indentation, line endings, and whitespace trimming across different editors and file types. A \.swift-format\ configuration file is introduced to define code formatting rules, such as line length and specific linting behaviors. A CMake build system (\CMakeLists.txt\) is added to support building the project with CMake, including options for single-module builds and specific Swift compiler flags. Documentation is significantly updated: the \README.md\ is rewritten to provide a comprehensive table of contents, detailed descriptions of all stable and experimental modules (including \BasicContainers\, \HashTreeCollections\, and \ContainersPreview\), and instructions for using package traits. The \CODE\_OF\_CONDUCT.md\ is deleted in favor of an inherited org-wide policy. Additionally, a \.license\_header\_template\ and \.licenseignore\ file are added to manage license headers, and the \.gitignore\ is updated to ignore new build artifacts and temporary files.

(repo-wide) · high confidence

The internal \\_HTable\ structure in \Sources/BasicContainers/HashTable\ has been completely rewritten to use a new bitmap-driven architecture. This change introduces a dedicated \Bucket\ type to identify table positions and a \Bitmap\ struct to manage occupancy, replacing previous internal storage mechanisms. The update includes new files for handling bitmap operations, bucket iteration, and item consumption, alongside refactored logic for insertions, removals, and resizing. Users benefit from improved performance characteristics, particularly in removal speed and iteration efficiency, as the new design optimizes how occupied regions are tracked and traversed within the hash table.

Sources/BasicContainers/HashTable · high confidence

The HashNode implementation has been restructured to improve clarity and correctness. New internal types have been introduced to support the hash tree structure: \_AncestorHashSlots for node addressing, \_Bitmap for efficient bucket tracking, \_Bucket for entry identification, \_Hash for hash value representation, and \_HashLevel for tree depth management. The \_HashNode.Builder enum and associated methods now provide a clearer interface for constructing and modifying nodes. Additionally, a bug in the union operation that was misplacing items pushed into a new child has been fixed, and the symmetric difference operation has been corrected to use XOR instead of intersection.

Sources/HashTreeCollections/HashNode · high confidence

The RigidArray implementation has been restructured to use OutputSpan and InputSpan primitives for append, insert, and removal operations, providing more efficient, non-copying mutations for non-copyable elements. Deprecated methods like \reallocate\ and \copy\ have been replaced by \setCapacity\ and \clone\, and \replaceSubrange\ now handles span-based replacements. New consumption methods (\consumeSubrange\, \consumeAll\) allow draining elements into spans. The type now conforms to \Iterable\ (Swift 6.4+), \Equatable\, and \Hashable\ (where applicable), and includes LLDB debug formatters for better inspection.

Sources/BasicContainers/RigidArray · high confidence

The RigidDeque type in the DequeModule has been significantly reworked to support non-copyable (move-only) elements. New methods allow appending, prepending, and inserting elements by initializing output spans via callbacks, as well as moving elements from buffers or spans directly into the deque. A new consumption API (consumeSubrange, consumeAll, consumeFirst, consumeLast) enables removing elements and passing them to a consumer via input spans, with automatic cleanup of unconsumed items. Deprecated methods like replace(removing:addingCount:) have been renamed to replaceSubrange. The type now conforms to Equatable and Hashable (where supported), provides Iterable conformance for borrowing iteration, and includes improved descriptions and initializers.

Sources/DequeModule/RigidDeque · high confidence

The Rope module's mutation and traversal logic has been reorganized into specific operation files (Append, Extract, Find, ForEachWhile, Insert, Join, MutatingForEach, Remove, RemoveSubrange, Split). This change introduces new capabilities such as \extract\ for slicing, \forEachWhile\ for early-termination iteration, and \mutatingForEach\ for in-place modification. It also fixes several behavioral issues, including a crash when calling \replaceSubrange\ or \removeSubrange\ on an empty rope, a copy-on-write violation in \Rope.join\, and incorrect remainder handling in \find\ and \remove\ operations.

Sources/RopeModule/Rope/Operations · high confidence

The UniqueArray container has been reorganized into modular source files and its API has been updated to support non-copyable (borrowing/moving) elements. Key behavioral changes include renaming \reallocate(capacity:)\ to \setCapacity(\_:)\, \copy()\ to \clone()\, and \replaceSubrange\ variants to \replace(removing:)\. New span-based methods like \append(addingCount:initializingWith:)\, \insert(moving:)\, and \consumeSubrange\ allow efficient, zero-copy manipulation of element storage. Additionally, \Equatable\ and \Hashable\ conformances are now available for Swift 6.4+ toolchains, and deprecated APIs have been moved to a dedicated file.

Sources/BasicContainers/UniqueArray · high confidence

The Xcode project build settings have been moved from the project file into dedicated xcconfig files (Collections.xcconfig, CollectionsTests.xcconfig, ContainersPreview.xcconfig, and Shared.xcconfig). This change centralizes configuration for deployment targets, code signing (defaulting to ad-hoc signatures), and Swift compiler flags, including experimental features like Lifetimes and BorrowingSequence, while also introducing a test plan that enables randomized testing via the COLLECTIONS\_RANDOMIZED\_TESTING flag.

Xcode · high confidence

The Swift Collections Xcode workspace has been moved to the Utils/ directory, with all shared schemes migrated from the .swiftpm location to Utils/swift-collections.xcworkspace/xcshareddata/xcschemes. This change updates the schemes to target Xcode 14 (versions 1.7) and disables implicit build dependencies to improve build isolation. Scheme targets have been renamed and reconfigured to match the current module structure, including the addition of schemes for BitCollections, HashTreeCollections (renamed from UniquedModule), and a dedicated memory-benchmark target, while the main Collections scheme now explicitly includes tests for all collection modules.

Utils/swift-collections.xcworkspace · high confidence

Added B-Tree unit tests for SortedCollections; Added LLDB formatter integration tests and tooling; Added OrderedSet diffing tests and updated test infrastructure; Added basic tests for the Collections module; Added comprehensive test suite for HashTreeCollections; Added comprehensive test suite for Heap; Added comprehensive test suites for BitArray, BitSet, and BitSet.Counted; Added comprehensive unit tests for SortedSet; Added test coverage for BasicContainers; Added test coverage for combinatorics, index ranges, and minimal type conformances; Added tests for BigString and Rope modules; Added tests for MutableContainer, MutableRef, MutableSpan, Ref, and UniqueBox; Added tests for SortedDictionary; Added tests for TrailingArray with varied header alignments; Expanded test coverage for Deque, RigidDeque, and UniqueDeque; Expanded test support utilities for collection validation and lifetime tracking; Migrate collection conformance checkers to test support and add sampling controls; New test support types and moved minimal collection helpers; Removal of Uniqued module test suite; Test support library moved to Tests and updated for Swift 6 noncopyable types; Updated OrderedDictionary test suite with invariant checking and refactored helpers.

The Swift Collections package has been updated to require the Swift 6.2 toolchain, introducing support for new experimental language features such as Lifetimes, InoutLifetimeDependence, and BorrowingSequence. The package manifest now defines several new traits to control optional components: UnstableContainersPreview, UnstableSortedCollections, and UnstableHashedContainers, allowing users to opt into source-unstable prototypes and noncopyable container support. Additionally, the benchmarking sub-package has been restructured to support Rust benchmarks via a new EnableRustBenchmarks trait and now depends on swift-collections-benchmark version 0.0.4. Dependency resolution files have been updated to reflect newer versions of swift-argument-parser (1.6.2) and swift-system (1.4.2), and the main package now includes availability macros for Swift Standard Library versions up to 6.5.

(dependencies) · high confidence

Written by watchdog.canine.dev from the codebase's own history, inside the signed delivery this page is composed from.

• CAI 66 → 61 (-5.7)
• Rubric changed (rubric-2026.09.11 → rubric-2026.09.18) — scores are not directly comparable.

• Code Health 92 → 86 (-6.5)
• Architecture 99 → 86 (-13.4)
• Maturity 54 → 54 (+0.5)
• Readiness 65 → 48 (-16.9)
• Security 80 → 85 (+5.6)
• Performance 100 (new)

• Duplicated block (10 lines × 2) (Sources/ContainersPreview/Conformances/UniqueDeque+Container.swift)
• Duplicated block (10 lines × 2) (Sources/DequeModule/RigidDeque/RigidDeque+Append.swift)
• Duplicated block (10 lines × 2) (Sources/DequeModule/RigidDeque/RigidDeque+Prepend.swift)
• Duplicated block (10 lines × 2) (Sources/DequeModule/RigidDeque/RigidDeque+Prepend.swift)
• Duplicated block (10 lines × 2) (Sources/DequeModule/RigidDeque/RigidDeque+Replacements.swift)
• Duplicated block (10 lines × 3) (Sources/BasicContainers/RigidArray/RigidArray+Append.swift)
• Duplicated block (11 lines × 2) (Sources/ContainersPreview/Conformances/RigidDeque+Container.swift)
• Duplicated block (11 lines × 3) (Sources/BasicContainers/RigidArray/RigidArray+Insertions.swift)
• Duplicated block (11 lines × 3) (Sources/BasicContainers/RigidArray/RigidArray+Insertions.swift)
• Duplicated block (11 lines × 3) (Sources/BasicContainers/RigidArray/RigidArray+Replacements.swift)
• Duplicated block (11 lines × 3) (Sources/BasicContainers/RigidArray/RigidArray+Replacements.swift)
• Duplicated block (12 lines × 2) (Sources/ContainersPreview/Conformances/RigidDeque+Container.swift)
• Duplicated block (12 lines × 2) (Sources/DequeModule/RigidDeque/RigidDeque+Prepend.swift)
• Duplicated block (12–14 lines × 3) (Sources/ContainersPreview/Conformances/RigidArray+Container.swift)
• Duplicated block (12–15 lines × 2) (Sources/ContainersPreview/Conformances/RigidDeque+Container.swift)
• Duplicated block (13 lines × 2) (Sources/BasicContainers/RigidArray/RigidArray+Deprecated.swift)
• Duplicated block (13–15 lines × 2) (Sources/DequeModule/RigidDeque/RigidDeque+Prepend.swift)
• Duplicated block (14 lines × 2) (Sources/DequeModule/RigidDeque/RigidDeque+Replacements.swift)
• Duplicated block (15 lines × 2) (Sources/DequeModule/RigidDeque/RigidDeque+Replacements.swift)
• Duplicated block (16 lines × 2) (Sources/DequeModule/RigidDeque/RigidDeque+Insertions.swift)
• …and 52 more

• BitSet.isEqualSet (cognitive 28) (Sources/BitCollections/BitSet/BitSet.swift)
• BitSet.isEqualSet (cyclomatic 18) (Sources/BitCollections/BitSet/BitSet.swift)
• BitSet.isSubset (cognitive 18) (Sources/BitCollections/BitSet/BitSet.swift)
• BorrowingIteratorProtocol._elementsEqual (cognitive 34) (Sources/InternalCollectionsUtilities/BorrowingIteratorProtocol+Equality.swift)
• BorrowingIteratorProtocol._elementsEqual (cyclomatic 19) (Sources/InternalCollectionsUtilities/BorrowingIteratorProtocol+Equality.swift)
• BorrowingIteratorProtocol._spanwiseZip (cognitive 38) (Sources/InternalCollectionsUtilities/BorrowingIteratorProtocol+Equality.swift)
• BorrowingIteratorProtocol._spanwiseZip (cyclomatic 16) (Sources/InternalCollectionsUtilities/BorrowingIteratorProtocol+Equality.swift)
• Container._spanwiseZip (cognitive 22) (Sources/ContainersPreview/Protocols/Container/Container.swift)
• Coverage not measured — Swift suite
• Duplicated block (10 lines × 2) (Sources/BasicContainers/RigidArray/RigidArray+Insertions.swift)
• Duplicated block (10 lines × 2) (Sources/ContainersPreview/Conformances/RigidDeque+Container.swift)
• Duplicated block (10 lines × 2) (Sources/DequeModule/Deque/Deque._UnsafeHandle.swift)
• Duplicated block (10 lines × 2) (Sources/DequeModule/RigidDeque/RigidDeque+Replacements.swift)
• Duplicated block (10 lines × 2) (Sources/InternalCollectionsUtilities/MutableSpan+Extras.swift)
• Duplicated block (10 lines × 3) (Sources/BasicContainers/RigidArray/RigidArray+Replacements.swift)
• Duplicated block (10 lines × 4) (Sources/BasicContainers/RigidArray/RigidArray+Deprecated.swift)
• Duplicated block (103 lines × 2) (Sources/DequeModule/Deque/Deque._UnsafeHandle.swift)
• Duplicated block (10–11 lines × 2) (Sources/BasicContainers/UniqueArray/UniqueArray+Replacements.swift)
• Duplicated block (11 lines × 2) (Sources/ContainersPreview/Conformances/RigidArray+Container.swift)
• Duplicated block (11 lines × 2) (Sources/ContainersPreview/Conformances/RigidArray+Container.swift)
• …and 202 more

• 56 commits — 48 feature/other, 8 fixes

• (repo) — 20 commits
• Sources/ContainersPreview — 7 commits
• (root) — 5 commits
• .github/workflows — 3 commits
• Tests/BasicContainersTests — 3 commits
• Tests/_CollectionsTestSupport — 3 commits
• Sources/BasicContainers — 2 commits
• Sources/HashTreeCollections — 2 commits
• Tests/ContainersTests — 2 commits
• Xcode/Collections.xcodeproj — 2 commits
• Documentation/Container-design.md — 1 commit
• Sources/BitCollections — 1 commit
• Sources/DequeModule — 1 commit
• Sources/InternalCollectionsUtilities — 1 commit
• Sources/RopeModule — 1 commit
• Sources/SortedCollections — 1 commit
• Tests/SortedCollectionsTests — 1 commit

• fix: Fix container validation on some 6.4 nightlies
• fix: Fix errors uncovered by new workflow configuration
• fix: Fix workflow spec
• fix: Merge pull request #725 from eliorpom-cmd/fix-typos-20260918
• fix: Merge pull request #736 from Denimworld12/fix-bitset-counted-update-count
• fix: Merge pull request #737 from Denimworld12/fix-union-wrong-level
• fix: [BitCollections] Fix BitSet.Counted.update(with:) not maintaining the cached count
• fix: [HashTreeCollections] Fix union misplacing items pushed into a new child
• change: Add rudimentary swift-format configuration
• change: Apply batched suggestions from code review
• change: BorrowingIteratorProtocol.map: Hide map2 and map3 behind underscores
• change: Check the mutating form* twins against their non-mutating originals
• change: Container: Reinstate requirement for Comparable indices
• change: Delete distracting comments
• change: Drop bad Iterable tests
• change: Drop support for Swift 6.0 and 6.1
• change: Drop unused Optional._borrow, ._mutate and _insert definitions
• change: Fix typos in documentation and comments
• change: Merge pull request #719 from Joseph-Cursio/check-set-algebra
• change: Merge pull request #720 from Joseph-Cursio/container-conformance-deques
• …and 36 more

• Containers 0 added · 0 removed · contexts 0 added · 1 removed · edges 0 added · 0 removed

• python

Written by watchdog.canine.dev from the codebase's own history, inside the signed delivery this page is composed from.

apple/swift-collections was measured the same way every project in this corpus was: the same rubric, at a pinned commit, with the result published in full. Point a surveyor at a repository you know and see whether you agree with it.