This patch release is mostly focusing on evolving the package traits UnstableContainersPreview and UnstableHashedContainers, with the following notable fixes and improvements to the stable parts of the package:

• Make the package documentation build successfully on the DocC that ships in Swift 6.2.
• Avoid using floating point arithmetic to size collection storage in the DequeModule and OrderedCollections modules.

Changes to experimental package traits

The new set and dictionary types enabled by the UnstableHashedContainers trait have now resolved several correctness issues in their implementation of insertions. They have also gained some low-hanging performance optimizations. Like before, these types are in "working prototype" phase, and while they have working implementations of basic primitive operations, we haven't done much work validating their performance yet. Feedback from intrepid early adopters would be very welcome.

The UnstableContainersPreview trait has gained several new protocols and algorithm implementations, working towards one possible working model of a coherent, ownership-aware container/iteration model.

• BidirectionalContainer defines a container that allows iterating over spans backwards, and provides decrement operations on indices -- an analogue of the classic BidirectionalCollection protocol.
• RandomAccessContainer models containers that allow constant-time repositioning of their indices, like RandomAccessCollection.
• MutableContainer is the ownership-aware analogue of MutableCollection -- it models a container type that allows its elements to be arbitrarily reordered and mutated/reassigned without changing the shape of the data structure (that is to say, without invalidating any indices).
• PermutableContainer is an experimental new spinoff of MutableContainer, focusing on reordering items without allowing arbitrary mutations.
• RangeReplaceableContainer is a partial, ownership-aware analogue of RangeReplaceableCollection, providing a full set of insertion/append/removal/consumption operations, with support for fixed-capacity conforming types.
• DynamicContainer rounds out the range-replacement operations with initializer and capacity reservation requirements that can only be implemented by dynamically sized containers.

• We now have working reference implementations of lazy map, reduce and filter operations on borrowing iterators, producers and drains, as well a collect(into:) family of methods to supply "greedy" variants, generating items into a container of the user's choice. Importantly, the algorithms tend to be defined on the iterator types, rather than directly on some sequence/container -- going this way has some interesting benefits (explicitness, no confusion between the various flavors or the existing Sequence algorithms), but they also have notable drawbacks (minor design issues with the borrowing iterator protocol, unknowns on how the pattern would apply to container algorithms, etc.).

    let items: RigidArray<Int> = ...
    let transformed = 
      items.makeBorrowingIterator() // obviously we'd want a better name here, like `borrow()`
      .map { 2 * $0 }
      .collect(into: UniqueArray.self)
    // `transformed` is a UniqueArray instance holding all values in `items`, doubled up 

    let items: RigidArray = ...
    let transformed = 
       items.makeBorrowingIterator()
      .filter { !$0.isMultiple(of: 7) }
      .copy()
      .collect(into: UniqueArray.self)
    // `transformed` holds a copy of all values in `items` that aren't a multiple of 7

    let items: RigidArray = ...
    let transformed = 
       items.consumeAll()
      .filter { !$0.isMultiple(of: 7) }
      .collect(into: UniqueArray.self)
    // `transformed` holds all values that were previously in `items` that aren't a multiple of 7. `items` is now empty.

Like before, these are highly experimental, and they will definitely change in dramatic/radical ways on the way to stabilization. Note that there is no project- or team-wide consensus on any of these constructs. I'm publishing them primarily as a crucial reference point, and to gain a level of shared understanding of the actual problems that need to be resolved, and the consequences of the design path we are on.

What's Changed

• Add some decorative badges in the README by @lorentey in #591
• [Dequemodule, OrderedCollections] Avoid using floating point arithmetic by @lorentey in #592
• Enforce dress code for license headers by @lorentey in #593
• Bump swiftlang/github-workflows/.github/workflows/soundness.yml from 0.0.7 to 0.0.8 by @dependabot[bot] in #595
• Documentation updates for latest DocC by @lorentey in #596
• [BasicContainers] Allow standalone use of the UnstableHashedContainers trait by @lorentey in #597
• Bump swiftlang/github-workflows/.github/workflows/swift_package_test.yml from 0.0.7 to 0.0.8 by @dependabot[bot] in #594
• [ContainersPreview] Rename Producer.generateNext() to next() by @lorentey in #599
• [ContainersPreview] Remove BorrowingSequence.first by @lorentey in #598
• [CI] Enable Android testing by @marcprux in #558
• [BasicContainers] Assorted hashed container fixes and improvements by @lorentey in #601
• Flesh out BorrowingSequence/Container/Producer model a little more by @lorentey in #603
• More exploration of ownership-aware container/iterator algorithms by @lorentey in #605

New Contributors

• @marcprux made their first contribution in #558

Full Changelog: 1.4.0...1.4.1

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

New ownership-aware ring buffer and hashed container implementations

In the DequeModule module, we have two new source-stable types that provide ownership-aware ring buffer implementations:

• struct UniqueDeque<Element> is a uniquely held, dynamically resizing, noncopyable deque.
• struct RigidDeque<Element> is a fixed-capacity deque implementation.

RigidDeque/UniqueDeque are to Deque like RigidArray/UniqueArray are to Array -- they provide noncopyable embodiments of the same basic data structure, with many of the same operations.

In the BasicContainers module, this release adds previews of four new types, implementing ownership-aware hashed containers:

• struct UniqueSet<Element> is a uniquely held, dynamically resizing set.
• struct RigidSet<Element> is a fixed-capacity set.
• struct UniqueDictionary<Key, Value> is a uniquely held, dynamically resizing dictionary.
• struct RigidDictionary<Key, Value> is a fixed-capacity dictionary.

These are direct analogues of the standard Set and Dictionary types. These types are built on top of the Equatable and Hashable protocol generalizations that were proposed in SE-0499; as that proposal is not yet implemented in any shipping toolchain, these new types are shipping as source-unstable previews, conditional on a new UnstableHashedContainers package trait. The final API of these types will also deeply depend on the struct Borrow and struct Inout proposals (and potentially other language/stdlib improvements) that are currently working their way through the Swift Evolution process. Accordingly, we may need to make source-breaking changes to the interfaces of these types -- they are not ready to be blessed as Public API. However, we encourage intrepid engineers to try them on for size, and report pain points. (Of which we expect there will be many in this first preview.)

We continue the pattern of Rigid- and Unique- naming prefixes with these new types:

• The Unique types (UniqueArray, UniqueDeque, UniqueSet, UniqueDictionary etc.) are dynamically self-sizing containers that automatically reallocate their storage as needed to best accommodate their contents; the Unique prefix was chosen to highlight that these types are always uniquely held, avoiding the complications of mutating shared copies.
• The Rigid types remove dynamic sizing, and they operate strictly within an explicitly configured capacity. Dynamic sizing is not always appropriate -- when targeting space- or time-constrained environments (think embedded use cases or real-time work), it is preferable to avoid implicit reallocations, and to instead choose to have explicit control over when (and if) storage is reallocated, and to what size. This is where the Rigid types come in: their instances are created with a specific capacity and it is a runtime error to exceed that. This makes them quite inflexible (hence the "rigid" qualifier), but in exchange, their operations provide far stricter complexity guarantees: they exhibit no random runtime latency spikes, and they can trivially fit in strict memory budgets.

Early drafts of borrowing sequence, generative iteration and container protocols

This release includes highly experimental but working implementations of new protocols supplying ownership-aware alternatives to the classic Sequence/Collection protocol hierarchy. These protocols and the generic operations built on top of them can be turned on by enabling the UnstableContainersPreview package trait.

• protocol BorrowingSequence<Element> models borrowing sequences with ephemeral lifetimes. (This is already progressing through Swift Evolution.)
• protocol Container<Element> models constructs that physically store their contents, and can expose stable spans over them.
• protocol Producer<Element, ProducerError> models a generative iterator -- a construct that generates items demand.
• protocol Drain<Element> refines Producer to model an in-place consumable elements -- primarily for use around container types.

In this version, the package has developed these protocols just enough to implement basic generic operations for moving data between containers like UniqueArray and RigidDeque. As we gain experience using these, future releases may start adding basic generic algorithms, more protocols (bidirectional, random-access, (per)mutable, range-replaceable containers etc.) convenience adapters, and other features -- or we may end up entirely overhauling or simply discarding some/all of them. Accordingly, the experimental interfaces enabled by UnstableContainersPreview are not source stable, and they are not intended for production use. We expect the eventual production version of these (or whatever designs they evolve into) to ship in the Swift Standard Library. We do highly recommend interested folks to try playing with these, to get a feel for the strange problems of Ownership.

Besides these protocols, the package also defines rudimentary substitutes of some basic primitives that belong in the Standard Library:

• struct InputSpan<Element> the dual of OutputSpan -- while OutputSpan is primarily for moving items into somebody else's storage, InputSpan enables safely moving items out of storage.
• struct Borrow<Target> represents a borrowing reference to an item. (This package models this with a pointer, which is an ill-fitting substitute for the real implementation in the stdlib.)
• struct Inout<Target> represents a mutating reference to an item.

A formal way to access SortedSet and SortedDictionary types

The SortedCollections module contains (preexisting) early drafts of two sorted collection types SortedSet and SortedDictionary, built on top of an in-memory B-tree implementation. This release defines an UnstableSortedCollections package trait that can be used to enable building these types for experimentation without manually modifying the package. Like in previous releases, these implementations remain unfinished in this release, with known API issues; accordingly, these types remain unstable. (Issue #1 remains open.) Future package releases may change their interface in ways that break source compatibility, or they may remove these types altogether.

Minor interface-level changes

• The Collections module no longer uses the unstable @_exported import feature. Instead, it publishes public typealiases of every type that it previously reexported from DequeModule, OrderedCollections, BitCollections, HeapModule and HashTreeCollections.

• We renamed some RigidArray/UniqueArray operations to improve their clarity at the point of use. The old names are still available, but deprecated.

  Old name	New name
  append(count:initializingWith:)	append(addingCount:initializingWith:)
  insert(count:at:initializingWith:)	insert(addingCount:at:initializingWith:)
  replaceSubrange(_:newCount:initializingWith:)	replace(removing:addingCount:initializingWith:)
  replaceSubrange(_:moving:)	replace(removing:moving:)
  replaceSubrange(_:copying:)	replace(removing:copying:)
  copy()	clone()
  copy(capacity:)	clone(capacity:)

• We have now defined a complete set of OutputSpan/InputSpan-based append/insert/replace/consume primitives, fully generalized to be implementable by piecewise contiguous containers. These operations pave the way for a Container-based analogue of the classic RangeReplaceableCollection protocol, with most of the user-facing operations becoming standard generic algorithms built on top of these primitives:

  mutating func append<E: Error>(
      addingCount newItemCount: Int,
      initializingWith initializer: (inout OutputSpan<Elemen...
  

This feature release supports Swift toolchain versions 6.0, 6.1 and 6.2, and it includes the following improvements:

BasicContainers module

This new module collects ownership-aware, low-level variants of existing data structures in the core standard library. In this release, this module consists of two array variants, UniqueArray and RigidArray.

These new types are provided as less flexible, noncopyable alternatives to the classic Array type. The standard Array implements value semantics with the copy-on-write optimization; this inherently requires elements to be copyable, and it is itself copyable.

struct UniqueArray<Element> is a noncopyable array variant that takes away Array's copy-on-write behavior, enabling support for noncopyable elements. This type's noncopyability means mutations can always assume that the array is uniquely owned, with no shared copies (hence the name!). This means that array mutations such as mutating an element at an index can behave much more predictably, with no unexpected performance spikes due to having to copy shared storage.

struct RigidArray<Element> goes even further, by also disabling dynamic resizing. Rigid arrays have a fixed capacity: they are initialized with room for a particular number of elements, and they never implicitly grow (nor shrink) their storage. When a rigid array's count reaches its capacity, it becomes unable to add any new items -- inserting into a full array is considered a programming error. This makes this a quite inflexible (or rigid) type indeed, as avoiding storage overflow requires careful, up front planning on the resource needs of the task at hand. In exchange, rigid arrays can have extremely predictable performance characteristics.

UniqueArray is a great default choice when a task just needs an array type that is able store noncopyable elements. RigidArray is best reserved for use cases that require absolute, pedantic control over memory use or latency -- such as control software running in environments with extremely limited memory, or when a certain task must always be completed in some given amount of time.

The Unique and Rigid prefixes applied here establish a general naming convention for low-level variants of the classic copy-on-write data structure implementations. Future releases are expected to flesh out our zoo of container types by adding Unique and Rigid variants of the existing Set, Dictionary, Deque, Heap and other constructs, with type names such as as RigidDictionary and UniqueDeque.

TrailingElementsModule module

This new module ships a new TrailingArray construct, a preview of a new low-level, ownership-aware variant of ManagedBuffer. This is primarily intended as a interoperability helper for C constructs that consist of a fixed-size header directly followed by variable-size storage buffer.

ContainersPreview module

This module is intended to contain previews of an upcoming ownership-aware container model. In this initial release, this module consists of just one construct: struct Box<T>.

Box is a wrapper type that forms a noncopyable, heap allocated box around an arbitrary value.

What's Changed

• Merge release/1.1 to main by @lorentey in #204
• Merge relase/1.1 to main, without taking any changes by @lorentey in #206
• [Heap] Add methods to replace minimum/maximum (redux) by @lorentey in #208
• Persistent collections updates (part 10) by @lorentey in #207
• Update CMakeLists.txt by @compnerd in #215
• Merge latest changes from release/1.1 to main by @lorentey in #220
• Merge branch release/1.1 to main by @lorentey in #231
• [SortedCollections] Disable tests with @testable imports in release builds by @lorentey in #232
• [Hashtable] Minor Documentation Fix (Typo) by @nickkohrn in #241
• Merge branch release/1.1 to main by @lorentey in #248
• Update README.md by @glessard in #251
• [OrderedDictionary] Explicitly mention in documentation that keys/values are ordered by @warpling in #254
• build: support ARM64 spelling by @compnerd in #282
• Merge release/1.1 to main by @lorentey in #284
• Update release checklist by @lorentey in #323
• build: update the build rules for adjusted tree layout by @compnerd in #331
• build: support using swift-collections in larger projects by @compnerd in #330
• Merge release/1.1 to main by @lorentey in #332
• build: support building in Debug mode on Windows by @compnerd in #333
• Bugfix Incorrect Assert in BTree.removeFirst/removeLast by @LeoNavel in #349
• Fix typos by @rex4539 in #356
• Merge branch release/1.1 to main by @lorentey in #358
• Merge.1.1→main by @lorentey in #361
• Add post-merge CI support by @shahmishal in #367
• Update CODEOWNERS by @lorentey in #375
• Merge release/1.1 to main by @lorentey in #386
• Merge release/1.1 to main by @lorentey in #410
• [BTree][NFC] Rephrase some comments by @lorentey in #427
• [CI] Pull Request testing support via GitHub Actions by @shahmishal in #426
• [OrderedDictionary Documentation] fix a typo by @Gyuni in #445
• Install swiftmodules with full module triple by @etcwilde in #470
• [OrderedSet] Add OrderedSet.appending(contentsOf:) by @pm-dev in #452
• ManagedBuffer.capacity is unavailable on OpenBSD. by @3405691582 in #456
• Align Heap._UnsafeHandle min/maxValue tie-breaking with Swift.min/max by @DakshinD in #455
• Add Heap.removeAll(where:) by @DakshinD in #454
• Merge release/1.2 to main by @lorentey in #450
• Disable SortedCollections module by @lorentey in #479
• Enable MemberImportVisibility and fix issues uncovered by @lorentey in #480
• fix comment for OrderedSet.appending(contentsOf:) by @ozumin in #478
• Bump requirements of nested benchmarking package by @lorentey in #481
• Fix CMake build by @etcwilde in #482
• Merge changes on release/1.2 to main branch by @lorentey in #487
• Enable macOS testing on GitHub Actions by @shahmishal in #483
• Fix API documentation links in README.md by @azarovalex in #490
• Skip Xcode 16.0 and 16.1 in PR workflow by @natecook1000 in #493
• Fix OrderedSet example usage by @azarovalex in #491
• Add support for embedded Swift mode by @parkera in #494
• Include DequeModule in the Foundation toolchain build by @cthielen in #495
• Fix CMake build for release/1.2 by @cthielen in #498
• fix minor typo in init docs for Deque.swift by @t089 in #503
• [SortedSet] Fix subtreeCount inconsistency after remove at index by @brianchang928 in #502
• Add the missing COLLECTIONS_SINGLE_MODULE when import InternalCollectionsUtils by @faimin in #501
• [SortedCollections] Fix incorrect offset calculation in BTree.findAnyIndex by @brianchang928 in #506
• [SortedCollections] Fix B-tree root reduction during element removal causing data loss by @brianchang928 in #507
• Add checks for Wasm compatibility to pull_request.yml by @MaxDesiatov in #509
• First round of noncopyable constructs: Box, RigidArray, DynamicArray by @lorentey in #508
• [actions] exclude Xcode 26 beta 6 by @glessard in #514
• Add "trailing elements" module with facilities for tail-allocated storage by @DougGregor in #513
• [Xcode] Add trailing elements to xcodeproj by @Azoy in https://github.com...

This is a patch release updating the CMake build configuration that is used to build Swift toolchains. There were no changes to the package.

What's Changed

• 1.1: Includes the DequeModule for use in the Foundation toolchain build by @cthielen #500

Full Changelog: 1.1.5...1.1.6

This is a patch release with the following minor improvements:

• BigString sometimes miscounted distances in its character view, resulting in an invalid collection conformance. This is now fixed. (#485)
• BigString's Unicode Scalar and character views now make better use of known lengths of the text chunks stored in the tree, resulting in significantly improved performance for their distance measurements. (#486)
• The Foundation-specific toolchain configuration was updated to include the Deque type. (#496)

What's Changed

• [BigString] Fix character indexing operations by @lorentey in #485
• [BigString] Harvest some low-hanging performance fruit by @lorentey in #486
• Include DequeModule in the Foundation toolchain build by @cthielen in #496

Full Changelog: 1.2.0...1.2.1

This is a patch release updating the CMake build configuration that is used to build Swift toolchains. There were no changes to the package.

What's Changed

• 1.1: Use full module triple for Swift modules by @etcwilde in #492

Full Changelog: 1.1.4...1.1.5

This feature release includes the following improvements:

• The package now compiles without warnings using Swift 6.0 and 6.1.
• New functionality:
  • Heap.removeAll(where:) (#454)
  • OrderedSet.appending(contentsOf:) (#452)
• Bug fixes and performance improvements:
  • Heap operations now agree on the identity of the maximal element, even if it has duplicates (#439)
  • OrderedSet now runs faster in unspecialized generic contexts (#433)
  • Building on OpenBSD no longer requires ManagedBuffer.capacity (#456)

This version supports Swift toolchain versions 5.10, 6.0 and 6.1.

What's Changed

• Set up release/1.2 branch by @lorentey in #423
• Optimize unspecialized OrderedSet.init and OrderedSet.firstIndex(of:) by @dnadoba in #433
• fix amd64 support by @michael-yuji in #447
• [cmake] Install libraries in standard directories by @Steelskin in #446
• [1.2][OrderedDictionary] fix a typo by @lorentey in #449
• [release/1.2] [CI] Add support for GitHub Actions by @shahmishal in #453
• Reimplement _specialize(_:for:) for the 5.9 stdlib by @lorentey in #472
• Add .editorconfig by @lorentey in #471
• Cherry pick recent PRs destined for 1.2 by @lorentey in #473
• Drop support for the Swift 5.9.* toolchains by @lorentey in #475
• [Rope] Resolve deprecation warnings on String.Index._description by @lorentey in #474

New Contributors

• @dnadoba made their first contribution in #433
• @michael-yuji made their first contribution in #447
• @Steelskin made their first contribution in #446

Full Changelog: 1.1.4...1.2.0

This patch release consists of changes to the (unstable) CMake configuration. It includes no code level modifications.

This is expected to be the last planned release in the 1.1 release series. The next tagged release will be 1.2.0, bumping the required Swift toolchain to 5.9.

What's Changed

• Add more file in Sources/BitCollections/CMakeLists.txt by @lamtrinhdev in #419
• [Build] Use SWIFT_SYSTEM_NAME rather than just lowercasing. by @al45tair in #421
• [CMake] Handle riscv64 by @futurejones in #422

New Contributors

• @lamtrinhdev made their first contribution in #419
• @al45tair made their first contribution in #421
• @futurejones made their first contribution in #422

Full Changelog: 1.1.3...1.1.4

This patch release ships bug fixes for issues discovered since 1.1.2.

What's Changed

• [BigString] Fix accidentally quadratic BigString.init by @lorentey in #405
• add 'final' keyword to class by @quokkaKyu in #403
• [CMake] Add support for WebAssembly target architectures by @kateinoigakukun in #408
• [concurrency] conform Deque.Iterator to unchecked-Sendable by @glessard in #414

New Contributors

• @quokkaKyu made their first contribution in #403
• @kateinoigakukun made their first contribution in #408

Full Changelog: 1.1.2...1.1.3

This patch release updates the (unstable) CMake build configuration to support the swift-foundation project.

There were no changes outside of the CMake configuration.

What's Changed

• Install the Foundation toolchain module during the static swift build by @jmschonfeld in #391
• [CMake] Reduce path lengths in single-module build by @jmschonfeld in #392
• Reduce the size of the _FoundationCollections toolchain module by @jmschonfeld in #395

Full Changelog: 1.1.1...1.1.2