Files

115 KiB
Raw Permalink Blame History

An Ownership-Aware Container Model for Swift

Table of Contents

Introduction

Over the last several years, we've been gradually building up an ownership model for Swift, to simplify the creation of safe high-performance Swift code. Our goal is to fulfill Swift's mandate to become a high-performance systems programming language, suitable for use in all computing tasks, from the smallest microcontrollers to the largest supercomputers. As many of the target environments need to operate within strict performance constraints, developers who specialize in them expect to have precise, predictable control over runtime behavior, even at the cost of some coding flexibility.

Crucially, Swift needs to satisfy this need without resorting to unsafe interfaces: our aim is to build constructs that can match (or exceed) the performance of legacy systems programming languages, while also avoiding undefined behavior if the interfaces get misused.

As of Swift 6.4, we have implemented a small but quickly growing list of useful data structures that follow these new design priorities:

At first glance, these types have the basic shape of a Swift Collection:

  • Most of them have a generic Element type
  • They have the concept of an Index, modeling an abstract position within their storage
  • They come with subscript operations that provide access to the element at a specific index
  • They provide familiar operations for advancing an index to the next logical position, calculating distances between indices and similar tasks.

However, unlike collections, these types can contain noncopyable elements, and most of them are noncopyable and/or nonescapable types themselves. These are significant complications, as our classic Collection protocols have been built upon the assumption of universal copyability and escapability, and it isn't feasible to factor out these assumptions without breaking the protocols.

Our goal is therefore to construct an ownership-aware analogue of the Collection protocol hierarchy, to allow flexible, high-performance and memory-safe access to the contents of in-memory data structures. The container types above all use one or more pieces of contiguous memory regions for element storage. The model we're introducing works by directly exposing these piecewise contiguous storage chunks through lightweight reference reference types Swift calls "spans". (Spans are the memory-safe analogue of an UnsafeMutableBufferPointer, or a pointer and a count.) Each span type is addressing a single contiguous memory region, and it provides a specific set of operations that facilitates a particular type of access. Spans come in four flavors:

  • Span allows read-only, borrowing access to items stored in fully initialized memory owned by someone else.
  • MutableSpan allows direct mutating access to someone else's fully initialized memory region.
  • OutputSpan allows direct in-place initialization of somebody else's storage.
  • InputSpan allows in-place consumption of items directly from someone else's storage.

We define a container type by its ability to expose its contents as a series of Span instances. Mutable containers can also expose their contents as MutableSpan instances, allowing their elements to be directly mutated in place, without moving them out of the container. "Drainable" containers allow their elements to be incrementally consumed directly out of their storage, via a series of InputSpan instances. Finally, range-replaceable containers implement insertions by exposing a series of OutputSpan instances for clients to populate, directly initializing their storage.

Our container primitives are designed to fit together to enable building high-performance generic algorithms to (say) efficiently transfer data from one container to another with minimal fuss. For example, we can use the DrainableContainer.consumeSubrange(_:) and RangeReplaceableContainer.insert(from:at:) operations to move a subrange of items from one ring buffer and insert them in the middle of another:

struct Gadget: ~Copyable {...}

var target: UniqueDeque<Gadget> = ...
var source: RigidDeque<Gadget> = ...

target.insert(from: source.consumeSubrange(5 ..< 10), at: 2)

Behind the scenes, this is expressed by directly moving data from InputSpan instances provided by source into OutputSpan instances provided by target, with no intermediate buffers. For the common case when Gadget is a bitwise movable type, this effectively boils down to a few memcpy invocations, plus a little administrative work to prepare the moves, and to restore data structure invariants afterwards.

Making Sense of the Design Space

Swift 6.4 introduced protocol Iterable to enable borrowing for-in loops over these new types. The new protocol made several notable choices in the design space of ownership-aware iteration; it is crucial that we identify them so that we can carefully examine the purpose and consequences of each one, and so that we are able to analyze alternative choices. Each specific choice defines a particular design axis; we'll give them names that reflect their purpose.

We do this not to criticize the design of Iterable, but to understand the use cases for which it is best suited, and to allow us to explore the full design space with intention. Identifying design axes allows us to derive a full set of potential abstractions almost mechanically, so that we can analyze them and develop the ones that seem most useful into concrete protocols in the rest of this document.

We list the four axes we are considering below. The rest of this introductory section will define each of these in detail, but their names already give us a hint of their purpose:

  1. Elementwise versus bulk iteration -- iteration may expose a single element at a time, or it may give access to multiple elements all at once.
  2. Iteration by borrowing elements vs iteration by taking elements -- whether iteration transfers ownership of the elements it traverses to the client.
  3. Generative vs visitative iteration -- conforming types may be allowed to materialize their contents on the fly, or iteration may require to merely visit preexisting elements.
  4. Failable and non-failable iteration -- whether iteration is allowed to throw an error.

Under these terms, our classic Sequence models non-failable, generative, elementwise iteration by taking elements.
The new Iterable protocol models failable, generative, bulk iteration by borrowing elements.

In the rest of this document, we'll define three additional core protocols, Container, Producer and Drain (as well as a number of auxiliary protocols refining them). The four core protocols have the following properties and relationships:

Protocol Elementwise/bulk Borrowing/taking Generative/Visitative Failable
Iterable bulk (Span-based) borrowing generative failable
└╴Container bulk (Span-based) borrowing visitative --
Producer bulk (OutputSpan-based) taking generative failable
└╴Drain bulk (InputSpan-based) taking visitative --

We can already use this table to gain some interesting observations:

  • Our proposed new protocols all have a strong preference towards bulk (rather than elementwise) iteration.
  • "Iteration by borrowing" and "iteration by taking" are independent abstractions; they are both useful enough to deserve their separate protocol hierarchies.
  • The design indicates that the generative iteration model is a "wider" or "weaker" abstraction than the "narrower"/"stronger" visitative one; both visitative protocols refine their generative counterparts. This is, to some extent, intuitively understandable: a protocol that only works with preexisting elements can also implement an interface that allows them to be generated on the fly. In exchange, the visitative protocols can provide richer, more specialized abstractions.
  • This design also strongly correlates failability with generative iteration. Neither of our proposed "visitative" protocols is failable. This too follows from the fact that visitative iteration merely accesses elements that already exist; there isn't much possibility for these accesses to fail.

Let's now explore this design space a little further, by looking at the benefits and consequences of each decision.

"Elementwise Iteration" vs "Bulk Iteration"

The classic Sequence models iteration by exposing elements one by one, through its iterator's next() method.

  mutating func next() -> Element?

This model of elementwise iteration is extremely straightforward to understand, and with a little practice we can write a rich variety of elementwise algorithms (almost) without thinking. However, it is not necessarily the most efficient way to iterate over things -- especially not over containers that organize their elements into piecewise contiguous storage chunks.

In elementwise iteration, we need to call a protocol's customizable entry point for each and every item we traverse. The entry point needs to load the iteration's current state, and find (or generate) the next element to visit -- precisely what that means varies wildly between each type we want to iterate over.

This makes it much harder for the compiler to reliably reason about and optimize code using Sequence types; this is especially difficult for sequences whose definitions are hidden behind a resilience boundary. In classic Swift, it isn't uncommon to see performance drop by a factor of hundreds as an operation's implementation moves across resilient module boundaries. As library evolution is a crucial feature of the language, this is rather unfortunate.

The new Iterable protocol resolves this issue by introducing the idea of bulk iteration, where each primitive iteration step exposes multiple items all at once to the client, batched up into a Span instance.

  mutating func nextSpan(maxCount: Int) throws(Failure) -> Span<Element>

Span is a small, frozen type in the Swift Standard Library, eminently amenable to optimizations -- efficiently traversing the elements of a span is a drastically simpler problem than iterating over an arbitrary sequence. Iterable forces conforming types to factor iteration into two distinct layers: clients still invoke custom code to retrieve the next batch of items, but once they have them, accessing the individual elements within each batch becomes dependably cheap.

For iterables that physically store their contents in memory, implementing iteration simply requires exposing spans over their preexisting piecewise contiguous storage chunks -- the bigger the chunks, the more efficient iteration becomes, even if nextSpan's implementation isn't visible to the optimizer.

Click to expand footnote

Of course, it was always possible to factor the implementation of iterators this way, by splitting next() into two layers, with judicious use of @inlinable or even @inline(always) attributes to encourage better performance while we're iterating within a storage chunk. However, this required a deep understanding of the underlying issues, and a large amount of willpower to structure the implementation the right way: this meant that only a select handful of types made an effort, and clients couldn't depend on it.

Iterable forces all conforming types to organize their implementation around this idea, drastically improving clients' ability to reason about performance costs, even in generic contexts.

Bulk iteration is not without drawbacks: it comes with a drastically more complicated interface, increasing the mental load of authoring conforming types, and of solving problems using the protocol.

To understand how Iterable works, we need to learn about what Span is, which requires us to also learn at least a little about nonescapable types. We need to figure out how to resolve a whole new class of compiler errors, and ultimately we need to get comfortable reading lifetime dependency declarations, to allow us to predict what operations we can express and so that we can architect our solutions without constantly fighting compiler diagnostics.

Operations for bulk iteration are full of subtle design complications that often don't seem particularly important, but dismissing them can render the abstraction impossible to use in some contexts. For instance, nextSpan's maxCount parameter is there to allow clients to limit the number of elements they receive at a time. Having to accommodate this limit is a significant complication for conforming types, so it is tempting to cut the complexity by force-feeding clients an arbitrary number of items. (After all, clients often set maxCount to Int.max anyway, and don't mind having to potentially deal with millions of items at a time.)

However, consider a client that just wants to look at the first three elements to make a decision about what to do with the rest. Giving this caller four thousand items would put them in an awkward position: they would need to stash the leftovers somewhere, and then process them all before pulling on the iterator again. The spans that nextSpan returns are tied to an exclusive access of the iterator, which (currently at least) makes it impossible to actually store them alongside the iterator in any meaningful way: these clients would be drowned in a sea of elements they cannot process. By simplifying conforming implementations, we would significantly limit the usefulness of the protocol.

Click to expand footnote

Throwing away the iterator and restarting it may seem like a possible workaround, but as Iterable types aren't required to produce the same items on repeated iterations, this cannot be a general solution. It only works on some iterable types, such as the containers we are introducing in this document.

How bulk operations report/handle failures is a similarly subtle but important complication: operations that need to throw errors must be able to properly report partial success, to avoid data loss and to allow clients to identify precisely which element triggered the error. If the fifth element of an Iterable instance happens to trigger an error, it still needs to be possible for clients to reliably access the first four elements -- no matter what value they use for maxCount.

In this document, we consider this added conceptual complexity a reasonable cost of improving the predictability of Swift performance. We're fully embracing bulk iteration across the full spectrum of container operations. Each flavor of iteration will be primarily built around one of the standard span types: Span, MutableSpan, OutputSpan and InputSpan.

"Iteration by Borrowing" vs "Iteration by Taking"

Code iterating over a Sequence gains full ownership of the items it accesses. It can decide to store some of them for later processing, and arbitrarily mutate or discard them as it wishes. Clients do not need to ask permission to do this, as Sequence relinquishes all control over the elements it exposes, as an inherent part of its design.

Sequence elements are (implicitly) required to be copyable, so this places no real restrictions on the kinds of types that can conform to the protocol. Conforming types are not actually required to relinquish control over any of the items they contain just because someone is iterating over them: they can simply return copies of each element while also holding on to their "original" copy.

In contrast, Iterable was designed to support noncopyable elements, which do not allow such simple workarounds. Returning a noncopyable instance means transferring its unique ownership out of the iterable. For container types, this would be a destructive operation, as the contents would have to be physically moved out of the container, emptying it out or entirely consuming it in the process. This would not be workable as the default form of iteration: we naturally expect to be able to iterate over a container multiple times without destroying it in the process.

To avoid this, Iterable instead chooses to return borrowing references to the elements it traverses, not the elements themselves. Clients do not get ownership over the items they access -- they get a temporary window that they can peer through to see a batch of items at a time; but they don't get to break the glass (to modify or consume the items), and once the window moves to the next batch, they lose sight of all previously seen items.

In this document, we'll call the ownership model of Iterable iteration by borrowing, as clients borrow the elements they traverse. The other way to gain access to something is to take ownership of it -- hence, we'll call the model Sequence follows iteration by taking.

Click to expand footnote

People have sometimes referred to "iteration by taking elements" as "consuming iteration". Unfortunately, this is routinely misunderstood to mean that the sequence itself gets consumed, rather than its elements, and that makes it an actively confusing term. "Iteration by taking" is meant to describe what the client does to the elements, not what happens to the source of the iteration.

Of course, the way Iterable only provides read-only, borrowing access to its elements severely limits what clients can do with them. Obviously, we will also need to provide iterator-like constructs that transfer ownership of their elements to the caller, so that it can collect them into a container type, or otherwise mutate/consume them as it wishes. In this document, we model the idea of "iterating by taking elements" with protocol Producer.

A variant of the Iterable approach is one where instead of borrowing references, we provide mutable references to elements -- we change the unit of iteration from Span<Element> to MutableSpan<Element> (or change Ref<Element> to MutableRef<Element>). The source of the elements still retains ownership in this case, but clients are allowed to arbitrarily mutate or even replace them. In this document, we model this approach with protocol MutableContainer. Notably, we only model visitative "muteration"; we are not introducing an Iterable-style, generative protocol for mutating iteration.

"Generative" vs "Visitative Iteration"

Sequence and Iterable both allow their elements to be generated on the fly. We'll be calling this style of traversal generative iteration. This allows a wide spectrum of conforming types, but it complicates performance analysis, as the variable cost of on-demand generation inherently adds a difficult term to the complexity of element access.

Additionally, generative iteration by borrowing (as implemented by Iterable) has the crucial limitation that the client cannot hold on to generated items as they come out of the iterator -- it is only able to see a single batch of them at a time, and the minute it advances the iterator, it loses sight of all the items it previously encountered. Because Iterable allows elements to be generated (and discarded!) on the fly, clients must destroy all references to the elements they see before they can advance to the next batch. This strictly limits the kinds of algorithms we can implement over Iterable: in particular, we cannot define lookup or search algorithms that need to return references to specific elements (such as min() or first(where:)), unless we require Element to be copyable. The elements we want to reference may evaporate the moment we advance the iterator!

Not all iterable types need to generate their items on demand. In particular, many of the most useful data structures physically hold their contents in memory, and they can implement iteration by simply locating their storage chunks and directly exposing spans over them. Arrays, linked lists, hashed sets, hashed dictionaries, ring buffers, search trees, ropes are all examples of such data structures, and of course there are many more.

Data structures with preexisting storage form a highly useful subset of iterables, and it is worth giving them a name; we'll call such types containers, and the traversal they support visitative iteration. These terms emphasize that iterating over a container merely visits its preexisting contents, rather than materializing them on the fly. Locating items in preexisting storage is a far simpler task than generating them; and clients can safely extract and work with references to such items as long as they do not mutate the instance that contains them.

Not all data structures are containers in this sense, of course. For example, Swift's standard String type is a sequence of Character instances, but those instances are not directly stored anywhere in String's storage representation -- they need to be created on the fly, as we iterate over the string instance. String therefore implements generative rather than visitative iteration; it is not a container type. (Of course, it would be possible to build a container of text data; but to do it efficiently, we'd likely need to avoid using Character-style grapheme clusters as its Element.)

Failability

The final design aspect we need to consider is failability: whether we need to allow traversable constructs to throw errors.

The classic Sequence protocol provides no way for conforming types to signal a failure, other than by trapping or by stopping the iteration earlier than expected. For many developers, this feels like a defect -- Sequence allows (or even encourages) conforming types to produce their elements by running arbitrarily complex calculations; and of course those calculations can sometimes legitimately encounter non-fatal problems. The inability to properly signal failure leads to awkward workarounds.

Using the terminology established in the previous section, the ability to fail is therefore a natural expectation for generative constructs.

The Iterable protocol addresses this by defining a Failure associated type and providing a throwing nextSpan method on its iterator. It relies on typed throws so that conforming types that never need to throw can set Never as their failure type, enabling clients to avoid writing error handling code that deals with errors that are guaranteed never to happen.

Failable iteration potentially allows lazy Iterable algorithms (like filter) to take throwing closures, and cleanly propagate errors to clients. In exchange, failability greatly complicates the bulk iteration model, as operations need to be able to properly report partial success.

Click to expand footnote

However, we also expect a filter predicate to be able to throw a different error type than the Iterable's own Failure. We currently lack the means to express that, as the nextSpan method would need to be able to throw either error. We need to do further language-level work -- such as union error types -- to allow us to express such abstractions in a satisfying way.

On the other hand, the ability to fail is far less important for visitative constructs, like Container -- if the items we're visiting already exist in memory at the start of the iteration, there is little reason to take on the complexity of throwing. Therefore, our two visitative protocols (Container and Drain) do not allow throwing.

This greatly simplifies the container model, but it does mean that throwing algorithms like our hypothetical lazy filter can only produce Iterable types -- they cannot return containers, even if their input is one.

Click to expand footnote

Some readers may note a problem with the assumption that accessing storage held in memory cannot possibly fail. While it is true that accessing memory can trigger hardware-level exceptions (e.g., consider I/O errors while accessing memory-mapped files or devices, or running out of physical memory while trying to resolve pretty much any page fault), we lack the means to turn these faults into recoverable errors in Swift.

Additionally, it seems unlikely it would be actually desirable to design container protocols to accommodate a hypothetical future language direction like that: all memory access can potentially fail, including access to instructions while executing program code (which is typically at least partially memory mapped), access to heap-allocated memory (which also commonly relies on page faults to delay actually allocating memory until first access), access to the stack (same problem), etc. Trying to model all these (plus logic issues like integer overflows etc) as locally recoverable errors seems hopeless.

The pragmatic choice is to assume that access to a container's memory can never fail without crashing the entire process. (Perhaps in the fullness of time we may figure out how to carve up Swift processes into cleanly isolated subsystems so that such traps can cause only the triggering subsystem to be abandoned, but the rest of the process can still continue running, to safely perform an orderly shutdown of whatever remains. Or perhaps we could just rely on subprocesses for that; after all, that is a big reason why modern operating systems have them.)

Overview of the Container Protocols

The classic Collection protocol establishes the basic shape of a repeatable sequence with indexing. However, Collection is only a part of Swift's collections story, as it is merely the top of an intricate protocol hierarchy:

Sequence
└╴Collection
  ├╴BidirectionalCollection
  │ └╴RandomAccessCollection
  ├╴MutableCollection
  ├╴RangeReplaceableCollection
  └╴LazyCollectionProtocol

The refining protocols define standard API surface for additional capabilities, enabling us to define useful generic algorithms for solving common tasks. Collection types conform to these protocols as needed to express their capabilities.

Container follows in the same footsteps by defining a standard interface for a repeatable and indexable, ownership-aware iterable type. But it merely defines a baseline shape of a read-only container type. Container types can often do much more than that: some support backward iteration; some support arbitrary element reassignments; some allow clients to change their count by inserting or removing elements. Establishing a shared vocabulary for these capabilities enables us to develop a rich library of generic algorithms that use them. Thus, Container also sits at the top of an elaborate protocol hierarchy:

Iterable
└╴Container
  ├╴BidirectionalContainer
  │ └╴RandomAccessContainer
  ├╴PermutableContainer
  │ └╴MutableContainer
  └╴DrainableContainer
    └╴RangeReplaceableContainer
      └╴DynamicContainer

This new container protocol hierarchy closely matches Collection's design, and should feel immediately familiar to veteran Swift programmers. However, it does have several refinements that address known limitations and new requirements:

  • The functionality of MutableCollection is split across two protocols: PermutableContainer defines a standard interface for containers that support element reordering, while MutableContainer sits on top of that, adding support for arbitrary element replacements.

    This branch of the protocol hierarchy models mutating operations that do not change the count (or general shape) of a container, but merely reorder or replace its contents. The split acknowledges that there is a useful class of data structures whose contents can be reordered but not arbitrary replaced, and that element reordering operations alone still support a rich variety of useful generic algorithms.

  • The functionality of RangeReplaceableCollection is similarly split into three parts:

    • DrainableContainer defines the shape of a shrinkable container: one that allows its elements to be removed by directly consuming them out of its storage.
    • RangeReplaceableContainer adds insertion, append, and replacement operations, establishing the model for adding new items to an existing container. On this level, operations never assume that storage is resizable: we want fixed-capacity containers like OutputSpan to provide a standard set of range-replacement operations.
    • DynamicContainer adds initializer requirements and more flexible insertion operations that require dynamically allocated, easily resizable storage.
  • There is no LazyContainerProtocol -- we expect container algorithms to be lazy by default, whenever possible.

Let us now introduce the actual protocols in detail, starting with Container itself.

A Read-Only Container Model

Protocol Container is our ownership-aware analogue of Collection. It defines the abstract shape of a container type that physically holds its contents in memory, and makes them directly accessible to clients.

The contents of a container can be traversed multiple times, nondestructively. The same container must exhibit identical contents across repeated traversals. Clients must be able to form references to container contents that aren't tied to a specific iteration state, only the container itself. This allows Swift functions to directly return such references to callers, allowing the implementation of a variety of useful container algorithms, including basic search/lookup methods.

Let's start defining the new protocol.

protocol Container<Element>: Iterable, ~Copyable, ~Escapable
where
  Element: ~Copyable,
  Failure == Never
{...}

The Container protocol refines Iterable; Iterable algorithms are able to work with container types with no extra effort. However, not all iterable types can be containers. The requirement that a container's elements must preexist in memory rules out all iterables that generate items on demand; using the terms we established above, we say that iterables model generative iteration, while containers are restricted to visitative semantics.

Container requires Failure to be set to Never: because the contents of a container are required to exist in advance within the container instance, they can always be successfully iterated: there is never a need to throw an error.

Naturally, container types are not required to be copyable, nor escapable. They don't require their elements to be copyable, either. (Support for nonescapable elements is a highly desirable future direction, but we currently lack the means to express it in Swift.)

Counting Elements

As containers physically store their elements, they inherently always have a specific count.

protocol Container<Element>: ... {
  ...
  var count: Int { get }
  ...
}

Repeated invocations of the count property on the same container must return the same value. The returned value must match the number of elements that can be accessed by iterating through the container.

Unlike Collection, types conforming to Container are required to produce their count in constant complexity. This reflects the protocol's focus on predictable performance, and avoids a common worry with Collection. Conforming to this requirement typically requires container implementations to cache their count in an easily accessible stored property, and incrementally update it every time the container changes its size.

Click to expand footnote

One consequence of this requirement is that constructs like lazy filter algorithms cannot practically conform to the protocol. However, they can still conform to Iterable, and that is in fact good enough for the vast majority of their use cases in practice. Notably, custom on-the-fly filtering is inherently incompatible with our emphasis on predictable performance. (After all, the Container protocol exists to focus on high-performance use cases; it would be a mistake to dilute this focus until the protocol becomes indistinguishable from Collection.)

A constant-complexity count also dictates a particular model for representing linked list indices so that splicing operations (i.e., Swift's own variants of the C++ STL's std::list::splice() function family) can update the list's count while themselves remaining O(1). This effectively requires list insertions/removals to invalidate all outstanding indices; however, efficient index validation also appears to require the same rules. (Having range-replacement/splicing operations return a valid index range for the affected region is one way to mitigate this, getting us to approach the same expressivity as STL's iterators without their issues with memory safety. Additionally, we can also choose to revive the Cursor concept, although it would not be inherently more limited than indices: the lack of (easily expressible) cursor ranges is particularly problematic.)

count is required to return a finite integer that fits in Int. This can be a true limitation, as some containers may have more than Int.max elements, despite the protocol's requirement for preexisting storage! The storage requirement does not preclude some containers from linking specific storage chunks multiple times (or simply repeating them), without allocating separate storage for each duplicate run. Such repetitions can cause the count of a container to overflow Int's range, without ever overflowing available memory. While such humongous containers are certainly interesting, we do not consider it crucial to provide dedicated support for them.

In the design we are proposing, humongous containers can choose to either only conform to Iterable, or to trigger a trap if they are ever asked for their count. Client code often invokes count so that it can preallocate storage for related work; obviously that is not going to end well if a container's count exceeds Int.max. (And in fact trapping early is much preferable to allowing the operation to inevitably fail midway through some vast computation.)

If we wanted to support such containers better, one option would be to have count return an optional; another would be to push the property down into a separate FiniteContainer protocol. The overwhelming complexity of these options does not feel to be anywhere in proportion to the practical importance of such cases. Which is not to say they don't exist: tree-based ropes in particular (like Foundation's AttributedString) can easily grow to humongous sizes, by simply concatenating a rope with itself a few dozen times. However, these are mostly just curiosities; such trees are rarely (if ever) practically useful.

As a small nod towards infinite/vast containers, Container still provides an isEmpty property that avoids problems with integer overflow:

protocol Container<Element>: ... {
  ...
  var isEmpty: Bool { get }
  ...
}

This comes with a default implementation that simply checks if count is zero. (Collection defines a default implementation for its isEmpty that compares startIndex to endIndex. Given that Container requires its count to have O(1) complexity, it is slightly better to define isEmpty in terms of it, as it avoids having to materialize two index instances.)

Infinite/vast containers can provide their own isEmpty implementation that avoids using count, for example, by following Collection's pattern. (They also need to provide a custom implementation for underestimatedCount, for the same reason.)

Container Indices

As Container refines Iterable, it provides a BorrowingIterator, and we can use this iterator to access the elements of a container in batches, starting from its beginning. However, it would be a shame to stop there: Container can also provide a more flexible model for element access that acknowledges that its contents survive across iteration steps. To help model this, we introduce a slightly adapted version of Collection's familiar Index concept.

protocol Container<Element>: ... {
  ...
  associatedtype Index: Equatable, Comparable, Hashable
  ...
}

Our indices represent abstract positions within containers (just as they do in collections): one useful way to look at them is to say that they're addressing the logical boundaries between neighboring elements, with a "start index" addressing the boundary before the first element, and the "end index" addressing the boundary after the last. A container with five items therefore has six indices, addressing all its various logical positions:

         ┌─────┬─────┬─────┬─────┬─────┐
         │  A  │  B  │  C  │  D  │  E  │
         └─────┴─────┴─────┴─────┴─────┘
         ↑     ↑     ↑     ↑     ↑     ↑
         0     1     2     3     4     5
   (start)                             (end)

Equivalently, we can say that each index addresses a specific element, with the end index addressing an imaginary empty slot after the last item in the container.

Over the years, Swift's indices have proven to be extremely successful abstractions. This incarnation preserves them as copyable and escapable types, so that they can be processed without undue friction. Indices are soft references that are allowed to go stale when the underlying container is mutated; therefore, container operations taking indices are still required to carefully validate their inputs to catch misuse. (We could have chosen to replace indices with a nonescapable abstraction that would avoid this; however, in practice we found that direction to be impractical.)

Every one of the standard container types we've introduced so far (from Span to UniqueArray and beyond) already defines an index that fits this model.

Container indices are required to be Equatable and Comparable, like Collection indices. In addition, Container also requires its indices to be Hashable. This does not put an undue burden on container implementations, but it does allow indices to be collected in sets or used as dictionary keys, enabling use cases such as dynamic filtering or out-of-band storage of data associated with container elements. (Not guaranteeing hashable indices is a long-standing annoyance with Collection.)

To acknowledge our performance goals, we require that equating, comparing and hashing Container indices must all be performed with O(1) complexity.

Now that we have an Index type, we can define all the familiar operations that allow us to navigate within a container:

protocol Container<Element>: ... {
  ...
  var startIndex: Index { get }
  var endIndex: Index { get }
  func index(after index: Index) -> Index
  func formIndex(after index: inout Index)
  func index(_ index: Index, offsetBy n: Int) -> Index
  func formIndex(_ index: inout Index, offsetBy n: inout Int, limitedBy limit: Index)
  func distance(from start: Index, to end: Index) -> Int
  ...
}

startIndex and endIndex work exactly like Collection's corresponding properties, defining the bounds of a half-open range: endIndex returns a valid index that addresses the logical empty slot following the container's last element, while startIndex addresses the container's first element.

index(_:offsetBy:) is the Container analogue of BorrowingIterator's skip(by:) method. It has slightly different semantics though, as it follows Collection's behavior: index(_:offsetBy:) always takes exactly the specified number of steps, and it traps if it runs off the end of the container.

As Container models a forward-only container, its index(_:offsetBy:) operation requires a nonnegative offset. (We'll shortly introduce a BidirectionalContainer refinement that will relax this constraint.)

However, as indices are required to be Comparable, the distance(from:to:) method works whether or not its start argument precedes end, even if we can only iterate forward.

Notably, we replace Collection's classic index(_:offsetBy:limitedBy:) requirement with an improved variant (first introduced on RigidArray/UniqueArray) that reports the number of steps it was unable to take when reaching the limit. This avoids having to figure this out with a separate distance(from:to:) invocation, enabling more efficient use of this operation in situations that need this data; for example, it allows easy single-pass offsetting across concatenated containers. Collection's original index(_:offsetBy:limitedBy:) operation is still available, as a standard algorithm based on the new requirement.

The limit argument here (and also elsewhere throughout the Container interface surface) means a limiting index, intended to cause the operation to stop if it encounters the limit during its execution. A limit of this sort only triggers a stop if the operation needs to actively iterate over it. A limit that the operation never needs to visit has no effect, whether it happens to address a position before or after the visited range. For example, if we're trying to find the index by offsetting position 10 by 5 places forward, a limiting index at position 3 has no effect -- to offset the original position, we only need to visit positions 10, 11, 12, 13, 14, and 15.

These curious semantics come from Collection, and they are a legacy of an early collection design where indices were not required to be comparable. We adopt them for Container for two reasons: first, it is preferable to avoid diverging from Collection behavior where there isn't a strong reason to do otherwise; second, while Container.Index is required to be comparable in this version of this document, we are not yet fully committed to keep it.

Visitative Iteration

The preferred way to iterate over the contents of a Container is to repeatedly invoke its nextSpan operation:

protocol Container<Element>: ... {
  ...
  @_lifetime(borrow self)
  func nextSpan(after index: inout Index) -> Span<Element>
  ...
}

Like the corresponding iterator method on Iterable, this implements bulk iteration: it gives clients access to a batch of items all at once, allowing them to quickly iterate over the returned Span instance without invoking any other Container methods.

However, this nextSpan function is only allowed to mutate an index, not the container itself. Additionally, the spans returned by nextSpan are declared to be scoped to a "borrow" of the container, too. This is the crucial difference from Iterable, whose spans extend (and are tied to) a particular mutation of the iterator. This is what causes Container to fundamentally require its elements to preexist in memory -- it isn't possible for a nextSpan with this signature to materialize items on the fly. Containers are required to implement visitative iteration.

Container.nextSpan returns a Span instance that begins with the container's element that the given index addresses, and runs to the end of the container's storage chunk that contains it. On return, the index is updated to address the item following the last element in the returned span. If the input index is the endIndex, then the method returns an empty span, and leaves the index as is.

This method can be used to efficiently process the items of a container in bulk, by directly iterating over its piecewise contiguous pieces of storage:

     var index = items.startIndex
     while true {
       let span = items.nextSpan(after: &index)
       if span.isEmpty { break }
       // Process items in `span`
     }
     // `index` is now equal to `items.endIndex`

We expect that for-in loops over container types will use this iteration style, to allow clients to form Ref instances over the element that's currently visited by the loop.

The spans returned by nextSpan are not guaranteed to be disjunct. Some containers may use the same storage chunk (or parts of a storage chunk) multiple times, to repeat their contents.

Repeated invocations of nextSpan on the same container and index are guaranteed to expose identical elements, in the same order, and grouped into spans of consistent counts.

Sometimes we don't want to iterate all the way to the end of a container: for instance, we may just want to look at a specific subrange, or we may need to access a specific number of elements. For these cases, Container also provides a delimited variant of nextSpan, modeled after formIndex(_:offsetBy:limitedBy:):

protocol Container<Element>: ... {
  ...
  @_lifetime(borrow self)
  func nextSpan(after index: inout Index, maxCount: Int, limitedBy limit: Index) -> Span<Element>
  ...
}

The maxCount argument gives the caller control over the number of items it receives from the iterator, while limit allows the caller to request that the result never step over a specific index. These parameters let callers avoid overrunning their target, which would significantly complicate container use.

For convenience, Container provides overloads that (effectively) make nextSpan's maxCount and limit arguments optional:

extension Container where Self: ~Copyable & ~Escapable, Element: ~Copyable {
  @_lifetime(borrow self)
  func nextSpan(after index: inout Index, maxCount: Int) -> Span<Element> {
    self.nextSpan(after: &index, maxCount: maxCount, limitedBy: self.endIndex)
  }

  @_lifetime(borrow self)
  func nextSpan(after index: inout Index, limitedBy limit: Index) -> Span<Element> {
    self.nextSpan(after: &index, maxCount: .max, limitedBy: limit)
  }
}

Not all containers are contiguous, so maxCount only sets an upper bound. To read a specific number of items, the caller usually needs to invoke nextSpan in a loop:

var items: some Container<Int>
var index = items.startIndex
var remainder = numberOfItemsToRead
while remainder > 0 {
  let next = items.nextSpan(after: &index, maxCount: remainder)
  guard !next.isEmpty else {
    // Container does not have enough items
    break
  }
  remainder -= next.count
  // Process items in `next`
}

Default Implementations

The more powerful form of nextSpan is a core primitive; by default, most other Container requirements are implemented in terms of it. For example, here is the default implementation of index(_:offsetBy:):

extension Container where Self: ~Copyable & ~Escapable, Element: ~Copyable {
  func index(_ index: Index, offsetBy n: Int) -> Index {
    var index = index
    var n = n
    let end = self.endIndex
    while n > 0 {
      let c = self.nextSpan(after: &index, maxCount: n, limitedBy: end).count
      precondition(c > 0, "Cannot advance index beyond the end of the container")
      n &-= c
    }
    return index
  }
}

Containers often group their contents into piecewise contiguous storage chunks: for example, array types hold all of their elements in a single, contiguous region of memory. As this default implementation iterates over entire chunks, it can be considerably more efficient than stepping through indices one by one, like Collection does. The elements are all required to preexist in memory, so materializing spans over them is relatively cheap -- nextSpan merely needs to locate storage, not populate its contents. Still, it is often possible to implement Container operations more directly (and more efficiently) than by invoking nextSpan, and so it is good practice to do so whenever it leads to measurable improvement.

While bulk iteration is often a performance boost, not all container types benefit from it. Some containers allocate a separate node for each of their elements, so their storage chunks all have just one item each. (Linked lists and binary search trees are two well-known examples.) These container types are still able to implement bulk iteration interfaces, but they become far less effective, as they are reduced to a somewhat overcomplicated form of elementwise iteration. Accordingly, in the worst case the index(_:offsetBy:) implementation above may need to invoke the nextSpan operation n times -- it has the same linear worst-case complexity as Collection's elementwise implementation.

Subscripting

Bulk iteration is nice, but sometimes we do just want to access an individual element addressed by a specific index. For these cases, Container provides an indexing subscript with a borrow accessor:

protocol Container<Element>: ... {
  ...
  subscript(index: Index) -> Element { borrow }
  ...
}

This (alongside all the shared index operations) makes Container instantly familiar to developers who have used Collection. Of course, this indexing subscript is not the same as the classic Collection subscript: it has a borrow accessor, not a getter. As of Swift 6.4, we cannot even put its borrowed result in a local variable; to do that, we need to manually create a borrowing reference by wrapping the result in a Ref instance:

let item = someContainer[index]
      // ^ error: 'someContainer.subscript' is borrowed and cannot be consumed
let item2 = Ref(someContainer[index]) // OK

Interaction with Iterable

ContainerIterator

Container refines Iterable, so it comes with all requirements of the Iterable protocol. The native container operations allow us to create standard implementations for these requirements, so that developers don't need to create a custom iterator type from scratch each time they work on a new container type. The standard iterator adapter is called ContainerIterator, and it serves the same purpose in the Container world as IndexingIterator does for Collection.

A ContainerIterator instance stores a borrowing reference to a container value, alongside a current position inside it:

struct ContainerIterator<
  Base: Container & ~Copyable /*& ~Escapable*/
>: ~Copyable, ~Escapable
where Base.Element: ~Copyable
{
  typealias Element = Base.Element

  internal let _base: Ref<Base> // Note: This requires an escapable Base
  internal let _end: Base.Index
  internal var _position: Base.Index

  init(base: borrowing Base, from start: Base.Index, to end: Base.Index)
}

@available(SwiftStdlib 6.4, *)
extension ContainerIterator: BorrowingIteratorProtocol
where
  Base: ~Copyable /*& ~Escapable*/,
  Base.Element: ~Copyable
{

  @_lifetime(&self)
  mutating func nextSpan(maxCount: Int) -> Span<Element> {
    _base.value.nextSpan(after: &self._position, maxCount: maxCount, limitedBy: _end)
  }

  @_lifetime(self: copy self)
  mutating func skip(by maximumOffset: Int) -> Int { ... }
}

Compare this to IndexingIterator, which holds a copy of its base collection, plus a current index. ContainerIterator implements the same idea, adapted for the borrowing ownership model. (It adds a limiting index to allow iterating over a subrange of elements in a container -- this is intended to substitute for a common use case of Collection slices.)

Conversions Between Indices and Iterators

Container resolves a long-standing Collection limitation by providing standard operations to start an iterator from a specific index (or between two indices), and to retrieve the current index of an existing iterator:

protocol Container<Element>: ... {
  ...
  @_lifetime(borrow self)
  func makeBorrowingIterator(from start: Index, to end: Index) -> BorrowingIterator
  func currentIndex(of iterator: borrowing BorrowingIterator) -> Index
  ...
}

extension Container
where
  Self: ~Copyable & ~Escapable,
  Element: ~Copyable
{
  @_lifetime(borrow self)
  func makeBorrowingIterator() -> BorrowingIterator {
    self.makeBorrowingIterator(from: self.startIndex, to: self.endIndex)
  }

  @_lifetime(borrow self)
  func makeBorrowingIterator(from start: Index) -> BorrowingIterator {
    self.makeBorrowingIterator(from: start, to: self.endIndex)
  }
}

Default Implementations of Iterable requirements

The underestimatedCount of a Container is simply its count:

extension Container
where
  Self: ~Copyable & ~Escapable,
  Element: ~Copyable
{
  var underestimatedCount: Int { self.count }
}

We'd like the Container protocol to declare ContainerIterator as its default borrowing iterator type:

protocol Container<Element>: ... {
  ...
  associatedtype BorrowingIterator = ContainerIterator<Self>
  ...
}

Unfortunately, this isn't currently possible, as Ref is not yet able to address nonescapable targets, and Container does need to allow nonescapable conforming types (such as Span). In its current form, ContainerIterator does not work for those, so nonescapable containers will need to manually implement a suitable iterator type.

However, we can at least supply default implementations for all Iterable-related operations when Iterator happens to be ContainerIterator:

extension Container
where
  Self: ~Copyable,
  Element: ~Copyable,
  BorrowingIterator == ContainerIterator<Self>
{
  @_lifetime(borrow self)
  func makeBorrowingIterator(from start: Index, to end: Index) -> BorrowingIterator {
    ContainerIterator(_borrowing: self, from: start, to: end)
  }

  func currentIndex(of iterator: borrowing BorrowingIterator) -> Index {
    iterator._position
  }
}

Optional Lookup Hooks

Collection defines two customization hooks for quickly looking up the first and last indices of an Equatable element instance. We directly include the same requirements on Container:

protocol Container<Element>: ... {
  ...
  func _customIndexOfEquatableElement(_ element: borrowing Element) -> Index??
  func _customLastIndexOfEquatableElement(_ element: borrowing Element) -> Index??
  ...
}

On Collection, these hooks allow conforming types to customize the standard firstIndex(of:) and lastIndex(of:) operations to implement more efficient algorithms than linear search. For instance, a hashed set type may implement these hooks to provide lookup operations with an expected complexity of O(1).

Like with Collection, these operations come with default implementations that simply return nil, indicating that there is no shortcut available for looking up elements.

Performance Requirements

To achieve predictable performance, Container operations are expected to have the following worst-case complexities:

Operation Complexity
Index.=⁠= O(1)
Index.hash(into:) O(1)
isEmpty O(1)
count O(1)
endIndex O(1) (non-negotiable requirement)
startIndex O(1)
nextSpan(...) O(1)
subscript(_:) O(1)
index(after:) O(1)
formIndex(after:) O(1)
index(_:offsetBy:) O(n)
formIndex(_:offsetBy:) O(n)
formIndex(_:offsetBy:limitedBy:) O(n)
distance(from:to:) O(d) where d is the absolute value of the actual distance
makeBorrowingIterator(...) O(1)
currentIndex(of:) O(1)
_customIndexOfEquatableElement(_:) O(1)
_customLastIndexOfEquatableElement(_:) O(1)

These correspond to similar (sometimes implicit) expectations on Collection's operations, stated more consistently. Of these, only the constant complexity of endIndex is a hard requirement; the others are setting rough expectations that may sometimes need to be violated. All containers are required to clearly document any deviations from the expectations above.

Common examples of containers with unusually high index navigation costs:

  • Containers with sparsely populated storage may need to scan an arbitrarily large number of empty storage slots between valid elements.

    Hashed containers like the standard Set and Dictionary types are prominent examples of this -- their index(after:) implementation has a worst-case complexity that's linear in their storage capacities, which can be arbitrarily larger than their count. (Even when averaged over iterating over the entire contents of a dictionary, index(after:)'s amortized complexity is still O(capacity/count) i.e., the inverse of the current load factor -- which still has no constant upper bound.) This is difficult to mitigate in practice; for example, implementing a minimum load factor would resolve this, but it would lead to constant allocation churn that (in most cases) would be considered much worse than inconsistent iteration speed.

  • Container types built around balanced trees (such as sorted sets or ropes) commonly need to replace/augment many of these complexities with "O(log(count))" terms.

The Full Container protocol

protocol Container<Element>:
  Iterable, ~Copyable, ~Escapable
  where Element: ~Copyable, Failure == Never
{
  associatedtype Index: Equatable, Hashable
  /*associatedtype BorrowingIterator = ContainerIterator<Self>*/

  @_lifetime(borrow self)
  func makeBorrowingIterator(from start: Index, to end: Index) -> BorrowingIterator

  func currentIndex(of iterator: borrowing BorrowingIterator) -> Index

  var isEmpty: Bool { get }
  var count: Int { get }
  var startIndex: Index { get }
  var endIndex: Index { get }

  @_lifetime(borrow self)
  func nextSpan(after index: inout Index) -> Span<Element>

  @_lifetime(borrow self)
  func nextSpan(
    after index: inout Index,
    maxCount: Int,
    limitedBy limit: Index
  ) -> Span<Element>

  subscript(index: Index) -> Element { borrow }

  func index(after index: Index) -> Index
  func formIndex(after index: inout Index)
  func index(_ index: Index, offsetBy n: Int) -> Index
  func formIndex(_ index: inout Index, offsetBy n: inout Int, limitedBy limit: Index)
  func distance(from start: Index, to end: Index) -> Int

  func _customIndexOfEquatableElement(_ element: borrowing Element) -> Index??
  func _customLastIndexOfEquatableElement(_ element: borrowing Element) -> Index??
}

Conforming to Container

Types that wish to conform to protocol Container must, at minimum, complete the following tasks:

  1. Implement an Index type, and an index validation strategy. Dereferencing an index must be both safe and highly efficient: it must be possible to reliably and quickly check that an index represents a valid position in the container, and then use the data inside the index to efficiently find the correct element in the container's storage.

  2. Implement startIndex and endIndex properties. endIndex must be as efficient as possible; it is required to have O(1) complexity, on every container type.

  3. Implement a count property with O(1) complexity. Often, this requires backing it by a stored property that gets incrementally updated every time the container changes its size.

  4. Choose a BorrowingIterator type, and implement the related methods makeBorrowingIterator(from:to:) and currentIndex(of:). The most straightforward choice is to use the standard ContainerIterator type; it provides a reasonable default for most container types.

  5. Implement the nextSpan(after:maxCount:limitedBy:) method. This is the core container primitive: the rest of container operations all come with default implementations based on this one.

  6. If the container is able to look up elements by value, provide custom implementations of _custom[Last]IndexOfEquatableElement so that standard algorithms can avoid falling back to linear searching.

  7. Implement custom implementations for additional container requirements, as needed. It is often possible to supply hand-optimized implementations that exploit the specific details of the container to provide measurably more efficient code than what the standard implementations achieve. Whether it is worth taking the extra effort to do this up front depends on the kind of container we're building, and its intended target use cases.

Once a container type ships in source (or ABI) stable code base, its choices for Index and BorrowingIterator types get baked into its interface, and become tricky (or impossible) to change in future releases. However, the implementations of specific operations can usually be updated; for example, it is usually possible to have a subsequent version replace the default implementation of an operation with a more efficient alternative that is tailor-made for the specific data structure.

Bidirectional Containers

The Container protocol only allows iterating forward -- towards the end index. Some container types also support going the other way, and modeling that with a protocol allows generic algorithms to exploit this capability to solve more problems that they can solve with forward iteration alone.

Our Container model follows in the footsteps of Collection, so we model backwards iteration as a refinement of forward iteration, by introducing a protocol BidirectionalContainer:

protocol BidirectionalContainer<Element>: Container, ~Copyable, ~Escapable
where Element: ~Copyable
{
  func index(before i: Index) -> Index
  func formIndex(before i: inout Index)

  func spanBoundary(before index: Index) -> (index: Index, distance: Int)

  func spanBoundary(
    before index: Index, maxDistance: Int, limitedBy limit: Index
  ) -> (index: Index, distance: Int)

  @_nonoverride func index(_ index: Index, offsetBy n: Int) -> Index
  @_nonoverride func formIndex(_ index: inout Index, offsetBy n: inout Int, limitedBy limit: Index)
}

index(before:) and formIndex(before:) match their equivalent BidirectionalCollection operations, although containers do come with an expectation that they both have O(1) complexity. (Container types that cannot provide these with constant complexity must explicitly document this deviation.)

Given that Container defines nextSpan operations, it is not unreasonable to expect that BidirectionalContainer would come with a previousSpan requirement. That's not the case -- we only provide operations that return indices to the nearest span boundary before the given position. BidirectionalContainer does come with previousSpan operations, but they are expressed as standard algorithms defined in terms of spanBoundary and nextSpan; they aren't customizable entry points themselves.

extension BidirectionalContainer
where Self: ~Copyable & ~Escapable, Element: ~Copyable {
  @_lifetime(borrow self)
  func previousSpan(before index: inout Index, maxCount: Int = Int.max) -> Span<Element> {
    self.previousSpan(before: &index, maxCount: maxCount, limitedBy: self.endIndex)
  }

  @_lifetime(borrow self)
  func previousSpan(
    before index: inout Index,
    maxCount: Int = Int.max,
    limitedBy limit: Index
  ) -> Span<Element> {
    let (i, d) = spanBoundary(before: index, maxDistance: maxCount, limitedBy: limit)
    if d == 0 { return .init() }
    var j = i
    let span = nextSpan(after: &j, limitedBy: index)
    precondition(j == index && span.count <= maxCount, "Invalid BidirectionalContainer")
    index = i
    return span
  }
}

To iterate backwards over a container, we call spanBoundary(before:) to get a suitable start position, then feed it to nextSpan(after:) to get a Span over the next (or rather, previous) batch of elements.

This asymmetry is designed to help us define a mutating iteration model (protocol MutableContainer, with a nextMutableSpan method) without having to also define a BidirectionalMutableContainer to supply a previousMutableSpan operation.

BidirectionalContainer redeclares a couple of Container operations with a @_nonoverride attribute: index(_:offsetBy:) and formIndex(_:offsetBy:limitedBy:). The bidirectional variants of these allow the offset n to be negative, deviating from Container's requirements. Redeclaring these as nonoverriding methods allows types that conform to BidirectionalContainer to provide distinct implementations for the forward-only and bidirectional cases. This is especially useful for types (such as container adapters) that want to be conditionally bidirectional, and can only support negative offsets if (say) their type arguments happen to conform to specific protocols. For example, take a hypothetical container adapter that concatenates two container instances:

struct Concatenated<C1: Container, C2: Container>: Container
where C1.Element == C2.Element {
  typealias Element = C1.Element

  enum Index: Hashable {
    case first(C1.Index)
    case second(C2.Index)
  }

  internal var _first: C1
  internal var _second: C2
  init(_ first: consuming C1, _ second: consuming C2) {...}
  ...

  func index(_ index: Index, offsetBy n: Int) -> Index {
    precondition(n >= 0)
    switch index {
    case .first(var i):
      var n = n
      _first.formIndex(&i, offsetBy: &n, limitedBy: _first.endIndex)
      if n == 0 { return .first(i) }
      return .second(_second.index(_second.startIndex, offsetBy: n))
    case .second(var i):
      return .second(_second.index(i, offsetBy: n))
    }
  }
}

It would be desirable for this type to conform to BidirectionalContainer if both of its components do:

extension Concatenated: BidirectionalContainer
where C1: BidirectionalContainer, C2: BidirectionalContainer {
  ...
  func index(_ index: Index, offsetBy n: Int) -> Index {
    if n >= 0 {
      switch index {
      case .first(var i):
        var n = n
        _first.formIndex(&i, offsetBy: &n, limitedBy: _first.endIndex)
        if n == 0 { return .first(i) }
        return .second(_second.index(_second.startIndex, offsetBy: n))
      case .second(var i):
        return .second(_second.index(i, offsetBy: n))
      }
    } else {
      switch index {
      case .first(var i):
        return .first(_first.index(i, offsetBy: n))
      case .second(var i):
        var r = n
        _second.formIndex(&i, offsetBy: &r, limitedBy: _second.startIndex)
        if r == 0 { return .second(i) }
        return .first(_first.index(_first.endIndex, offsetBy: r))
      }
    }
  }
}

However, unless we redeclare index(_:offsetBy:) in the refining protocol, the Container and BidirectionalContainer protocols would share a single index(_:offsetBy:) requirement, and it must resolve to the unconditional forward-only definition. Swift types can only provide a single implementation for each protocol requirement; therefore the second index(_:offsetBy:) would be ignored by conformance resolutions, and it would only be considered an auxiliary overload of the primary definition. Therefore callers that are generic over BidirectionalContainer would end up only able to call the forward-only implementation. @_nonoverride allows us to let the two definitions be both visible to such clients, without having to invent distinct names for these two operations.

(Of course, we could also have decided to break continuity with Collection, and introduce new names, such as Container.index(_:advancedBy:) and BidirectionalContainer.index(_:decrementedBy:). This makes for fewer surprises for clients, but it results in a messier API surface if a type happens to conform to both Container and Collection protocol hierarchies. Additionally, clients may find it needlessly pedantic to have to invoke distinct operations when navigating forward or back.)

This @_nonoverride business is largely irrelevant for types that conform to BidirectionalContainer without conditions, as such types typically only want to define index(_:offsetBy:)/formIndex(_:offsetBy:limitedBy:) once, with bidirectional semantics.

Random-Access Containers

We also provide a named abstraction for random-access containers that can provide constant complexity operations for finding the element at an arbitrary offset from an index, and for measuring distances between arbitrary indices.

Protocol RandomAccessContainer refines BidirectionalContainer, with minimal new API:

protocol RandomAccessContainer<Element>
: BidirectionalContainer, ~Copyable, ~Escapable
where Element: ~Copyable {
  @_nonoverride func index(_ index: Index, offsetBy n: Int) -> Index
  @_nonoverride func formIndex(_ index: inout Index, offsetBy n: inout Int, limitedBy limit: Index)
  @_nonoverride func distance(from start: Index, to end: Index) -> Int
}

However, the protocol adds strong semantic complexity requirements across all operations -- basically everything has to be O(1):

Operation Complexity
Index.=⁠= O(1)
Index.< O(1)
Index.hash(into:) O(1)
isEmpty O(1)
count O(1)
endIndex O(1)
startIndex O(1)
nextSpan(...) O(1)
subscript(_:) O(1)
index(after:) O(1)
index(before:) O(1)
formIndex(after:) O(1)
formIndex(before:) O(1)
index(_:offsetBy:) O(1)
formIndex(_:offsetBy:) O(1)
formIndex(_:offsetBy:limitedBy:) O(1)
distance(from:to:) O(1)
makeBorrowingIterator(...) O(1)
currentIndex(of:) O(1)
_customIndexOfEquatableElement(_:) O(1)
_customLastIndexOfEquatableElement(_:) O(1)

Random-access container (and collection) indices are largely isomorphic to integer offsets, and we are often able to increment/decrement them independent of their container. Indeed, well-designed random-access containers often use simple Int values as their index; Span, InlineArray, UniqueArray all use integer indices, and so do RigidArray, RigidDeque and UniqueDeque in swift-collections. To exploit this, and to simplify creating conforming types, RandomAccessContainer provides efficient default implementations for most indexing operations if Index is Strideable:

extension RandomAccessContainer
where
  Self: ~Copyable & ~Escapable,
  Element: ~Copyable,
  Index: Strideable,
  Index.Stride == Int
{
  var isEmpty: Bool { startIndex == endIndex }
  var count: Int { startIndex.distance(to: endIndex) }
  func index(after index: Index) -> Index { index.advanced(by: 1) }
  func index(before index: Index) -> Index { index.advanced(by: -1) }
  public func formIndex(after index: inout Index) { index = index.advanced(by: 1) }
  public func formIndex(before index: inout Index) { index = index.advanced(by: -1) }
  func distance(from start: Index, to end: Index) -> Int { start.distance(to: end) }
  func index(_ index: Index, offsetBy n: Int) -> Index { index.advanced(by: n) }
  func formIndex(
    _ index: inout Index, offsetBy distance: inout Int, limitedBy limit: Index
  ) {
    index.advance(by: &distance, limitedBy: limit)
  }
}

These definitions avoid traversing container storage (like the nextSpan-based implementations did in earlier sections), and we expect their simpler definitions to optimize better. However, they do not check that their input indices are valid in the container, and when given invalid input, they tend to return invalid indices. (For instance, an index(_:offsetBy:) defined this way typically allows offsetting the index beyond the end of the container.) The idea is that index validation is deferred until the client attempts to actually use the index to access an element. This saves some index validation overhead, while still fully guaranteeing memory safety. However, delaying the detection of errors makes debugging a little harder, as mistakes are not be caught by (and reported as coming from) the specific operations that actually trigger them.

Based on our expectations for predictably good container performance, we believe this to be a good compromise. Luckily, Collection types already routinely behave the same way, so the looser validation is not going to come as a surprise.

Mutable Containers

It is relatively straightforward to augment our read-only container model with new operations that allow in-place mutations. We'll follow in the footsteps of MutableCollection by defining a MutableContainer protocol. However, we carve it into two separate levels, by first introducing an intermediate protocol that focuses on reordering.

protocol PermutableContainer

Protocol PermutableContainer adds a single requirement to Container, the mutating method swapAt:

protocol PermutableContainer<Element>: Container, ~Copyable, ~Escapable
where Element: ~Copyable
{
  @_lifetime(self: copy self)
  mutating func swapAt(_ i: Index, _ j: Index)
}

(FIXME: Consider adding range sliding and rotation operations as direct requirements.)

Like its MutableCollection counterpart, swapAt swaps the two elements addressed by the given indices. (Doing nothing if i == j.) Swapping elements does not invalidate any existing index in the container; it merely changes the elements that the two indices are addressing.

The single swapAt operation on PermutableContainer enables us to develop a variety of useful generic algorithms, including for reversing, shuffling and sorting elements, or moving subranges within a container.

Carving out a new protocol focusing on reordering contents allows us to express a number of useful generic algorithms on container types that are permutable, but cannot conform to the full MutableContainer protocol. This is sometimes the case with container types that set constraints on their elements that aren't expressed as type constraints on the Element type, or with containers that have content-dependent layouts.

For example, the OrderedSet type in swift-collections has both of these properties: it makes use of hashing to ensure that its elements are all distinct (under ==), and to support fast lookup operations. The requirement for distinctness is not enforced by a type constraint on the Element type; rather, it is enforced at runtime, through hashing. An element's storage location in the hash table is based on a hash value derived from its actual value. Allowing an element to get mutated inside the hash table would invalidate its location, rendering the table useless.

Click to expand footnote

One idea to allow hashed containers to allow in-place mutations would be to have the container clean up after each mutation by rehashing affected elements, potentially discarding duplicates. As we'll see, this is not compatible with a MutableContainer conformance, as (1) the protocol does not allow the container to run any postprocessing/cleanup operations on updated elements, and (2) the protocol requires that its mutations do not invalidate any indices. Rehashing elements or removing duplicates would run afoul of both constraints.

Unlike most other container operations, we define no bulk variant of swapAt. We don't have a PermutableSpan type that could express reorderable regions of memory, and even if we defined one, iterating over the permutable spans of a container would not let us express any of the algorithms above! To do that, we'd need to invent a way to access the spans of a container all at once, and we need to have an operation to swap elements between them, and only between them. This is not possible in current Swift, so PermutableContainer only supports pairwise swaps.

Click to expand footnote

Another way to support "bulk" reordering would be to define a standard type that represents an arbitrary n-ary permutation, and define an operation that applies it to a concrete permutable container instance. Unfortunately, this would not be a lightweight abstraction: the permutation representation itself would be quite expensive, and it is unclear if any container types could implement this operation in a way that's meaningfully more efficient than a generic algorithm based on swapAt.

protocol MutableContainer

The MutableContainer protocol refines PermutableContainer by adding operations to gain direct mutable access to the container's storage:

protocol MutableContainer<Element>: PermutableContainer, ~Copyable, ~Escapable
where Element: ~Copyable {
  subscript(index: Index) -> Element { borrow mutate }

  @_lifetime(&self)
  mutating func nextMutableSpan(after index: inout Index) -> MutableSpan<Element>

  @_lifetime(&self)
  mutating func nextMutableSpan(
    after index: inout Index,
    maxCount: Int,
    limitedBy limit: Index
  ) -> MutableSpan<Element>
}

The refined subscript provides a mutate accessor for elementwise access. For example, here is one way to increment all integers stored inside a mutable container:

extension MutableContainer where Self: ~Copyable & ~Escapable, Element: BinaryInteger {
  mutating func incrementAll() {
    var i = self.startIndex
    while i != self.endIndex {
      self[i] += 1
      self.formIndex(after: &i)
    }
  }
}

The two nextMutableSpan operations are the mutating variants of the borrowing nextSpan on Container. We can use them to reduce the number of protocol witness invocations from three per visited item (or two with a cached endIndex) to just one:

extension MutableContainer where Self: ~Copyable & ~Escapable, Element: BinaryInteger {
  mutating func incrementAll() {
    var index = self.startIndex
    while true {
      var span = self.nextMutableSpan(after: &index)
      guard !span.isEmpty else { break }
      for i in span.indices {
        span[i] += 1
      }
    }
  }
}

(Note how the subscript is now invoked on a MutableSpan instance that is a standard type with an easily optimizable implementation.)

All these operations provide direct mutable access to the container's storage, with minimal overhead. In effect, the container's job reduces to simply locating the particular elements in its storage: it gets no chance to postprocess the result of the mutation in any way. The MutableSpan instances (and mutate accessor's inout reference result) are directly returned to the caller, who can arbitrarily mutate the referenced elements. However, the caller cannot consume any of them without putting something back in exchange. When the caller completes its mutation, it destroys its mutable reference, thus completing the exclusive access that began with the invocation of the mutating container operation that returned it. However, the container does not get a callback when the access completes -- it cannot run any cleanup after the mutation.

There is a large number of container types that can conform to MutableContainer: this includes all contiguous mutable iterable types in the Swift 6.4 Standard Library (MutableSpan, OutputSpan, InlineArray, UniqueArray), as well as piecewise contiguous data structure implementations such the ring buffer implementations in swift-collections, or linked lists.

Notably, the inability to consume items means that MutableContainer cannot provide a fully generic default implementation for PermutableContainer.swapAt. Instead, it only provides a partial default implementation that only applies if Element happens to be copyable; it works by creating two temporary copies:

extension MutableContainer
where Self: ~Copyable & ~Escapable, Element: Copyable
{
  mutating func swapAt(_ i: Index, _ j: Index) {
    let copy = self[i] // First copy
    self[i] = self[j] // Second copy
    self[j] = copy
  }
}

Mutable containers with noncopyable elements must manually provide a direct implementation of the core swapAt primitive.

Click to expand footnote

It would also be possible to provide a default implementation for swapAt for containers with contiguous storage, by invoking swapAt on the container's single mutable storage span.

protocol ContiguousMutableContainer: // Example only
  RandomAccessContainer,
  MutableContainer,
  ~Copyable,
  ~Escapable
where Element: ~Copyable {
  var mutableSpan: MutableSpan<Element> { borrow mutate }
}

extension ContiguousMutableContainer
where Self: ~Copyable & ~Escapable, Element: ~Copyable
{
  mutating func swapAt(_ i: Index, _ j: Index) {
    let offset1 = self.distance(from: self.startIndex, to: i)
    let offset2 = offset1 + self.distance(from: i, to: j)
    self.mutableSpan.swapAt(i, j)
  }
}

It seems like a waste to introduce a whole new protocol just to be able to supply a default swapAt, though.

Or we could change swapAt to take a valid element outside the container to facilitate the exchange. Here is one way to do the latter:

extension MutableContainer
where Self: ~Copyable & ~Escapable, Element: ~Copyable
{
  mutating func swapAt(_ i: Index, _ j: Index, using scratch: inout Element) {
    swap(&self[i], &scratch)
    swap(&self[j], &scratch)
    swap(&self[i], &scratch)
    // scratch is back to its original value
  }
}

Of these three, copying elements seems the most practical; therefore

There are remarkably few interesting generic algorithms that operate on MutableContainer; we expect most generic code will simply perform an elementwise mutation, such as the incrementAll implementations above. However, the ability to express that is already worth the price of admission! Mutating iterations are a common need, and it is reasonable to spend a protocol on making them pleasant. For example, we could teach Swift's for-in loops to efficiently iterate over inout references to a mutable container's elements, with a nice, succinct syntax:

extension MutableContainer where Self: ~Copyable & ~Escapable, Element: BinaryInteger {
  mutating func incrementAll() {
    for inout item in &self { // Example syntax
      item += 1
    }
  }
}

Interaction with BidirectionalContainer

MutableContainer provides the reason why BidirectionalContainer is built around the spanBoundary(before:) method, rather than previousSpan(before:), which would be the obvious choice. By making backward bulk iteration work by identifying the closest span boundary before the supplied index, we have decoupled it from the specific choice of the span type. Therefore, bidirectional mutable containers can build their previousMutableSpan(before:) requirement the same way as we did previousSpan: by building on the same spanBoundary(before:) operation:

@available(SwiftStdlib 6.4, *)
extension MutableContainer
where
  Self: BidirectionalContainer & ~Copyable & ~Escapable,
  Element: ~Copyable
{
  @_lifetime(&self)
  mutating func previousMutableSpan(
    before index: inout Index
  ) -> MutableSpan<Element> {
    let start = self.spanBoundary(before: index).index
    var i = start
    let span = self.nextMutableSpan(after: &i, limitedBy: index)
    precondition(i == index, "Invalid BidirectionalContainer")
    return span
  }

  @_lifetime(&self)
  mutating func previousMutableSpan(
    before index: inout Index,
    maxCount: Int,
    limitedBy limit: Index
  ) -> MutableSpan<Element> {
    let start = self.spanBoundary(
      before: index,
      maxDistance: maxCount,
      limitedBy: limit
    ).index
    var i = start
    let span = self.nextMutableSpan(after: &i, limitedBy: index)
    precondition(i == index, "Invalid BidirectionalContainer")
    index = start
    return span
  }
}

This way, we can avoid having to define a separate BidirectionalMutableContainer protocol just to carry these.

Producers

Protocol Iterable allows clients to iterate over a conforming type by borrowing elements. However, we also need a model for iterating by taking, where the iterator transfers the ownership of its elements to the client, to do with them as it pleases.

We model this form of iteration with the protocol Producer.

protocol Producer<Element, Failure>: ~Copyable, ~Escapable {
  associatedtype Element: ~Copyable

  associatedtype Failure: Error = Never

  // Core requirement:

  @discardableResult
  mutating func generate(
    into target: inout OutputSpan<Element>
  ) throws(Failure) -> Int

  // Requirements with default implementations:

  var underestimatedCount: Int { get }
  mutating func skip(by n: inout Int) throws(Failure)
  mutating func next() throws(Failure) -> Element?
}

Producers are allowed to be noncopyable and/or nonescapable types, and they may have noncopyable elements. (Support for nonescapable elements is deferred until we gain better support for managing their lifetime dependencies.)

Iterating Over a Producer

The generate(into:) member requirement forms the core producer operation: it models failable, generative, bulk iteration by taking elements.

  @discardableResult
  mutating func generate(
    into target: inout OutputSpan<Element>
  ) throws(Failure) -> Int

This operation generates the next batch of items into the supplied output span instance, which should have room for at least one new element. Repeatedly calling this method produces, in order, all the elements of the underlying sequence. The operation fully populates the given output span, unless it hits the end of the producer or encounters a failure. The returned integer is the number of items generated: as soon as the sequence has run out of elements, all subsequent calls return 0 without appending any new items to their target.

Click to expand footnote

(Passing a target with no free capacity is a precondition violation. The operation may result in a runtime error in this case, but it is also allowed to unconditionally return zero in this case, whether or not the producer is at its end. There is no way to test if the producer has reached its end without asking it to generate at least one new item.)

The ownership of all generated elements is transferred to the caller of this method -- it can arbitrarily store, mutate, consume or discard them as needed, even across invocations of this method. The elements are allowed to survive indefinitely, even after the producer has been destroyed.

Click to expand footnote

(Of course, this statement will need to be revised when/if we add support for nonescapable elements.)

The generate(into:) operation may throw an error if it encounters an issue while trying to generate the upcoming next item in the sequence. Failure may happen midway through populating target, in which case the output span will still gain new items, despite the error. (Those items have been successfully generated, and do not necessarily need to be discarded.)

This protocol does not specify the meaning of a failure, or the precise state of the iterator after an error is thrown; however, the error must not trigger runtime traps in subsequent attempts at iteration. (After a failure, conforming types may choose to produce new items, or signal the end of the iteration, or throw another error, which may or may not match the first.)

Absent of more specific information, generic code should stop iterating, discard the producer and rethrow the error when it encounters a failure. Generic code is encouraged to preserve the items that got successfully produced before the throw (including ones appended by the call that ultimately ended in failure); however, whether this is possible (or desirable) ultimately depends on the specific problem that the algorithm is solving.

For example, here is how we can append the elements of an arbitrary Producer to the end of a UniqueArray:

extension UniqueArray where Element: ~Copyable {
  mutating func append<
    E: Error,
    P: Producer<Element, E> & ~Copyable & ~Escapable
  >(
    from producer: consuming P
  ) throws(E)
  where P.Element: ~Copyable
  {
    var done = false
    repeat {
      let c = Swift.max(1, Swift.max(producer.underestimatedCount, self.freeCapacity))
      try self.append(addingCount: c) { target throws(E) in
         try producer.generate(into: &target)
         if !target.isFull {
           done = true
           return
         }
      }
    } while !done
  }
}

Note how the elements are generated in bulk, directly populating array storage -- the operation progresses as efficiently as possible, avoiding moving elements through any temporary variables or buffers. We make best use of underestimatedCount to avoid resizing the array more times than necessary.

If the producer throws an error, then this algorithm leaves the array in a valid state, containing every element that was successfully generated -- however, the array may be left with unnecessarily allocated free capacity. The client who attempted the append is free decide to keep those elements appended (by simply doing nothing), or to get rid of them: the correct choice depends on the specific problem it is solving. The default behavior is to keep partial results, as doing anything else would lead to potential data loss.

(Later on, we'll introduce a DynamicContainer protocol that will define a variant of this append algorithm on a generic dynamically allocated container. As UniqueArray will conform to DynamicContainer, it does not need to actually define this operation: it gets it for free.)

Creating a Producer

The Producer protocol does not define a standard way to create a producer instance. This is because there is no satisfying way to model this: some producers are naturally created with borrowing methods, some mutating, and some consuming, and the operations usually come with a custom parameters.

For example, a basic example of a commonly useful producer type is the result of a generative lazy map algorithm over an Iterable:

extension Iterable {
  @_lifetime(borrow self)
  borrowing func map<T: ~Copyable>(
    _ transform: @escaping (borrowing Element) throws(Failure) -> T
  ) -> BorrowingMapProducer<Self, T> { ... }
}

BorrowingMapProducer would conform to Producer by running the given transformation on each element borrowed from the underlying Iterable. Notably, func map here only needs to borrow the iterable, but the resulting producer is still able to transfer ownership of the generated items to the client.

Another common class of producers are for consuming a subrange of items out of a container type, such as the UniqueArray operation below:

extension UniqueArray where Element: ~Copyable {
  struct SubrangeConsumer: Producer, ~Copyable, ~Escapable { ... }

  @_lifetime(&self)
  mutating func consumeSubrange(_ subrange: Range<Index>) -> SubrangeConsumer {
    ...
  }
}

UniqueArray.SubrangeConsumer conforms to Producer by moving the specified elements out of the array and into the supplied output spans. The subrange consumer extends the duration of the mutation of the array that produced it -- the array is in an inconsistent state while it is being consumed from. When the SubrangeConsumer is destroyed, its deinitializer restores the array's invariants by closing the resulting gap in array storage and updating its count to reflect the removals.

(Later on, we'll introduce the DrainableContainer protocol to standardize the SubrangeConsumer shape, allowing us to express in-place consumption and to supply a small family of useful generic algorithms built around it.)

Note how the Producer protocol defines an iterator shape, not a sequence. It is the "taking" analogue of BorrowingIterator. We do not provide a producer analogue of the Iterable protocol.

Iterable provides a uniform way to create a borrowing iterator, but there is no way to (usefully) unify producer creation like that. For example, the borrowing func map(_:) and mutating func consume(_:) operations above are two prominent instances of Producer creation. Neither their ownership modifiers nor their parameter lists lend themselves to easy unification: the parameters are naturally unique, and the modifiers can only be unified by requiring them both to be consuming -- which would be unacceptable. (We can't have a borrowing map or a partial consumption consume the entire container they're invoked on!)

Additionally, many producers are inherently nonrepeatable: for instance, a SubrangeConsumer can only move the subrange of elements out of its underlying container a single time: once it has transferred their ownership to the client, it cannot do so again.

These two features combine to make it undesirable to try defining a uniform way to create a producer. If we tried, we would end up with something like the protocol below:

protocol Produceable: ~Copyable, ~Escapable { // EXAMPLE, NOT A REAL PROTOCOL
  associatedtype Producer: Swift.Producer, ~Copyable, ~Escapable
  @_lifetime(copy self) // ?!
  consuming func makeProducer() -> Producer
  var underestimatedCount: Int { get }
}

Of course, the issue is that makeProducer would be defined as a consuming method with no arguments, and with a name that fails to clarify what we're iterating over. To make the map method and the SubrangeConsumer construct above work, we'd need to have them return either separate Produceable value only for it to be almost immediately consumed, or (more likely) to have them return a type that conforms to both Producer and Produceable. In practice, Produceable would provide no practical benefit -- separating it out would complicate our design for no good reason.

Default Implementations on Producer

extension Producer where Self: ~Copyable & ~Escapable, Element: ~Copyable {
  var underestimatedCount: Int { 0 }

  mutating func skip(by n: inout Int) throws(Failure) {
    precondition(n > 0, "Cannot skip fewer than one item")
    let maxBufferSize = _producerBufferSize
    return try withTemporaryAllocation(
      of: Element.self,
      capacity: Swift.min(maxBufferSize, n)
    ) { buffer throws(Failure) in
      repeat {
        defer {
          n &-= buffer.count
          buffer.removeAll()
        }
        try self.generate(into: &buffer)
        if !buffer.isFull { return }
      } while n > 0
    }
  }

  mutating func skip(by n: Int) throws(Failure) -> Int {
    var remainder = n
    try self.skip(by: &remainder)
    return n - remainder
  }

  mutating func next() throws(Failure) -> Element? {
    try withTemporaryAllocation(
      of: Element.self, capacity: 1
    ) { buffer throws(Failure) in
      guard try self.generate(into: &buffer) else { return nil }
      return buffer.removeLast()
    }
  }
}

Counted Producers

/// A producer with an exact count.
public protocol CountedProducer<Element, Failure>: ~Copyable, ~Escapable, Producer
where Element: ~Copyable
{
  var count: Int { get }
}

extension CountedProducer where Self: ~Copyable & ~Escapable, Element: ~Copyable {
  var underestimatedCount: Int {
    count
  }
}

In-Place Consumption

struct InputSpan

struct InputSpan<Element: ~Copyable>: ~Copyable, ~Escapable {
  deinit
  init()
  init(buffer: UnsafeMutableBufferPointer<Element>, initializedCount: Int)
  consuming func finalize(for buffer: UnsafeMutableBufferPointer<Element>) -> Int

  var count: Int { get }
  var freeCapacity: Int { get }
  var isEmpty: Bool { get }
  var isFull: Bool { get }

  typealias Index = Int
  var startIndex: Index { get }
  var endIndex: Index { get }
  var indices: Range<Index> { get }

  subscript(_ index: Int) -> Element { borrow mutate }
  subscript(unchecked index: Int) -> Element { borrow mutate }

  mutating func swapAt(_ i: Index, _ j: Index)
  mutating func swapAt(unchecked i: Index, unchecked j: Index)

  mutating func prepend(_ value: consuming Element)
  mutating func removeFirst() -> Element
  mutating func removeFirst(_ k: Int)
  mutating func popFirst() -> Element?
  mutating func removeAll()
  mutating func prepend(moving source: UnsafeMutableBufferPointer<Element>)
  mutating func prepend(repeating repeatedValue: Element, count: Int) where Element: Copyable
  mutating func prepend(copying source: UnsafeBufferPointer<Element>) where Element: Copyable
  mutating func prepend(copying source: borrowing Span<Element>) where Element: Copyable

  var span: Span<Element> { get }
  var mutableSpan: MutableSpan<Element> { @_lifetime(&self) mutating get }

  @_lifetime(self: copy self)
  mutating func withUnsafeMutableBufferPointer<E: Error, R: ~Copyable>(
    _ body: (UnsafeMutableBufferPointer<Element>, inout Int) throws(E) -> R
  ) throws(E) -> R

  mutating func consumePrefix(upTo n: Int) -> InputSpan<Element>
}

protocol Drain

/// A type that supplies the values of an in-place consumable sequence through
/// a series of `InputSpan` instances. This iterator-like construct allows
/// directly consuming elements from some container's storage, in bulk,
/// without requiring them to be moved into any temporary buffer.
///
/// Drains are inherently also producers -- they can produce items by simply
/// moving their consumable contents to the client-supplied series of
/// output spans.
protocol Drain<Element>: CountedProducer, ~Copyable, ~Escapable
where Element: ~Copyable, Failure == Never
{
  /// Returns the next span of consumable items in the sequence underlying this
  /// drain, of at most the specified maximum count. A `maxCount` of nil
  /// indicates no limit, meaning that the client is able to process an
  /// arbitrarily large number of elements.
  ///
  /// Repeatedly calling this method returns, in order, all the elements of the
  /// underlying consumable sequence. As soon as the sequence has run out of
  /// elements, all subsequent calls return empty spans.
  ///
  /// While the returned input spans exist, they continue to mutate the drain,
  /// extending the exclusive access initiated by the call to
  /// `drainNext(maxCount:)`. To call this (or any other) method again, the
  /// returned input span needs to be consumed or otherwise destroyed.
  ///
  /// Once this method returns, the contents of the resulting input span are
  /// already destined for consumption, either gradually by invoking explicit
  /// methods such as `InputSpan.popFirst`, or all at once when
  /// the input span is destroyed. There is no way to "put items back" into
  /// the consumable sequence, other than by moving them into a
  /// temporary location and later reinserting them into the underlying
  /// construct through some type-specific operations.
  ///
  /// - Parameter maxCount: The maximum number of items that the client
  ///       is prepared to consume, or nil if the client is able to process an
  ///       arbitrary number of elements. If this is non-nil, then it must be a
  ///       positive integer.
  /// - Returns: An input span of at most the specified maximum count (if any),
  ///       containing the next elements of the underlying consumable sequence.
  ///       This method returns an empty span to indicate that it has reached
  ///       the end of the sequence.
  @_lifetime(&self)
  @_lifetime(self: copy self)
  mutating func drainNext(maxCount: Int) -> InputSpan<Element>
  // TODO: The primary use case does not need this to throw; do we need to allow that?
  // Note: making this failable is not entirely straightforward, as there is no
  // easy way to signal partial success -- conforming implementations
  // would likely need to store errors they encounter midway through a
  // chunk and report them at the beginning of the next iteration.
  // I take this as an indication that we don't need to do that.
  // (Contrast with this `Producer.generate(into:)`; the shape of that method
  // allows it to partially populate its client-supplied target and still
  // report an error.)
  //
  // Note: We can also express this with a higher-order shape:
  //
  //     mutating func drainNext<E: Error, R: ~Copyable>(
  //       _ body: (inout InputSpan<Element>) throws(E) -> R
  //     ) throws(E) -> R
  //
  // This would allow partial consumption, eliminating the need for
  // `maxCount`, but at the cost of having to deal with closures --
  // it can be tricky to elegantly flow data/control in & out higher-order
  // functions. Allowing the function argument to throw also precludes
  // the drain itself from throwing, unless they are both required
  // to use the same error type, which would be impractical.
}
extension Drain where Self: ~Copyable & ~Escapable, Element: ~Copyable  {
  @_lifetime(&self)
  mutating func drainNext() -> InputSpan<Element> {
    drainNext(maxCount: Int.max)
  }

  @_lifetime(target: copy target)
  mutating func generate(
    into target: inout OutputSpan<Element>
  ) throws(Never) -> Int {
    var c = 0
    while !target.isFull {
      var source = self.drainNext(maxCount: target.freeCapacity)
      guard !source.isEmpty else { break }
      c += source.count
      target._append(moving: &source)
    }
    return c
  }

  @_lifetime(self: copy self)
  public mutating func skip(by n: inout Int) {
    precondition(n >= 0, "Cannot skip a negative number of elements")
    while n > 0 {
      let span = drainNext(maxCount: n)
      guard !span.isEmpty else { return }
      n &-= span.count
    }
  }
}

Operations over Container Subranges

Index Ranges and Range Expressions

protocol RangeExpression2<Bound>: RangeExpression { // Oof
  override associatedtype Bound: Comparable

  func relative<C: Container & ~Copyable & ~Escapable>(
    to container: borrowing C
  ) -> Range<Bound> where C.Index == Bound, C.Element: ~Copyable

  override func contains(_ element: Bound) -> Bool
}

extension Range: RangeExpression2 {...}
extension ClosedRange: RangeExpression2 {...}
extension PartialRangeFrom: RangeExpression2 {...}
extension PartialRangeUpTo: RangeExpression2 {...}
extension PartialRangeThrough: RangeExpression2 {...}

Drainable Containers

public protocol ContainerDrain<Element>: Drain, ~Copyable, ~Escapable
where Element: ~Copyable
{
  associatedtype Index
  consuming func finalize() -> Index
}
protocol DrainableContainer<Element>
: Container, ~Copyable, ~Escapable
where Element: ~Copyable {
  // MARK: Core requirements

  associatedtype SubrangeConsumer:
    ContainerDrain<Element> & ~Copyable & ~Escapable
  where SubrangeConsumer.Index == Index

  @_lifetime(&self)
  mutating func consumeSubrange(_ subrange: Range<Index>) -> SubrangeConsumer

  // FIXME: `consumeAll(where:)`
  // FIXME: `removeAll(where:)`
  // These should ideally be using SubrangeConsumer, but that requires Drain
  // to support partial consumption -- a large complication.

  // MARK: Requirements with default implementations

  /// Removes and returns the element at the specified position.
  ///
  /// - Parameter index: The position of the element to remove. `index` must be
  ///   a valid index that is not equal to the end index.
  ///   On return, `index` is updated to address the position following the
  ///   removed element.
  /// - Returns: The removed element.
  @discardableResult
  mutating func remove(at index: inout Index) -> Element

  @discardableResult
  mutating func consumeSubrange(
    _ bounds: Range<Index>,
    consumingWith consumer: (inout InputSpan<Element>) -> Void
  ) -> Index

  @discardableResult
  mutating func removeSubrange(_ bounds: Range<Index>) -> Index

  mutating func removeAll()
  mutating func removeFirst(_ n: Int)
  mutating func _customRemoveLast() -> Element?

  @_lifetime(&self)
  mutating func _customConsumeLast(_ n: Int) -> SubrangeConsumer?

  mutating func _customRemoveLast(_ n: Int) -> Bool
}

(FIXME: We need consumeAll(where:)/removeAll(where:) methods, ideally implemented through SubrangeConsumer. This would require Drain to allow partial draining (by clients leaving some items in the InputSpan instances), which seems unlikely to be viable, but it's worth a try.)

Consuming Subranges

Removing Subranges

Range-Replaceable Containers

protocol RangeReplaceableContainer<Element>
: DrainableContainer, ~Copyable, ~Escapable
where Element: ~Copyable
{
  // MARK: Core requirements

  var freeCapacity: Int { get }

  /// - Returns: A valid index range addressing the newly inserted items.
  @discardableResult
  mutating func replaceSubrange<E: Error>(
    _ subrange: Range<Index>,
    consumingWith consumer: (inout InputSpan<Element>) -> Void,
    addingCount newItemCount: Int,
    initializingWith initializer: (inout OutputSpan<Element>) throws(E) -> Void
  ) throws(E) -> Range<Index>

  // MARK: Requirements with default implementations

  /// - Returns: A valid index range addressing the newly inserted items.
  @discardableResult
  mutating func insert<E: Error>(
    addingCount newItemCount: Int,
    at index: Index,
    initializingWith initializer: (inout OutputSpan<Element>) throws(E) -> Void
  ) throws(E) -> Range<Index>

  /// - Returns: A valid index addressing the newly inserted item.
  @discardableResult
  mutating func insert(_ item: consuming Element, at index: Index) -> Index

  /// - Returns: A valid index range addressing the newly inserted items.
  @discardableResult
  mutating func append<E: Error>(
    addingCount newItemCount: Int,
    initializingWith initializer: (inout OutputSpan<Element>) throws(E) -> Void
  ) throws(E) -> Range<Index>

  /// - Returns: A valid index addressing the newly inserted item.
  @discardableResult
  mutating func append(_ item: consuming Element) -> Index
}

(TODO: Go through the myriad standard algorithms, either here or in thematic sections below.)

Adding Elements to a Container

Replacing Subranges

Dynamic Containers

protocol DynamicContainer<Element>: RangeReplaceableContainer, ~Copyable
where Element: ~Copyable
{
  init()
  init(minimumCapacity: Int)

  mutating func reserveCapacity(_ minimumCapacity: Int)

  /// The number of items that can be added to the container without forcing
  /// it to allocate extra storage. This is primarily intended to serve as a
  /// hint for the batch size of appends, to allow bulk operation even if
  /// the number of items to be appended is not known in advance.
  ///
  /// If the container does not have simple, predictable allocation behavior,
  /// then this should return the size of the container's primitive allocation
  /// unit. For example, in a balanced rope that organizes its contents into a
  /// tree of fixed-capacity nodes, it may be a good choice to use the maximum
  /// node size as the (constant) free capacity, even though it may not
  /// correlate exactly with actual allocation behavior.
  ///
  /// If a container always reports a free capacity of 0, then appending a
  /// sequence of items of an unknown size may run slower than expected.
  ///
  /// - Complexity: O(1)
  var freeCapacity: Int { get }
}

(TODO: Describe the standard algorithms.)

Sample Conformances

UniqueDeque

LinkedList

Rejected Directions

Non-Comparable Indices

Cursors

Index Rounding Operations

protocol ContiguousContainer

Potential Future Directions

Support for Nonescapable Element Types

Factoring Indexing Out of Containers

(protocol Indexable with no element access; allows indexable producers, with the cost of greatly increased conceptual complexity.)

A Protocol for Directly Initializing Storage