Hello, Swift Evolution!
Included below is a significant revision of SE-0516: BorrowingSequence. The revision adds some additional detail about the additions, and includes two significant changes:
- The main protocol has been renamed to
Iterableto reflect a more universal role for iteration. All associated types and methods have been renamed to fit. - Borrowing iteration can now throw, with associated
Errortypes added to the protocols.
The PR for the revision can be found here, in case you have minor edits to suggest. Many thanks for any and all feedback on this new direction!
Iterable
- Proposal: SE-0516
- Authors: Nate Cook, Ben Cohen
- Review Manager: Holly Borla
- Status: Returned for revision
- Implementation: swiftlang/swift#86811, swiftlang/swift#87483
- Review: (pitch) (review) (returned for revision)
- Previous Revision: 1
Summary of changes
We propose a new protocol for iteration, Iterable, which provides a universal implementation point for synchronous iteration. Types conforming to Iterable can be noncopyable or nonescapable, can have noncopyable or nonescapable elements, and can throw during iteration. The Swift compiler will support use of this protocol via the familiar for-in syntax.
Changes from Original Version
This version of the proposal includes the following changes from the original BorrowingSequence proposal:
- Renamed to
Iterable: The protocol and all associated types and methods have been renamed to reflect the protocol's more universal role. - Throwing iteration: Both
IterableandIterableIteratorProtocolnow include aFailure: Errorassociated type, enabling typed throws during iteration.
Motivation
The Sequence protocol first appeared alongside collections like Array in the early days of Swift, and has many appealing characteristics, allowing iteration and generic algorithms on sequences based on the simple for-in primitive.
However, it predates the introduction of ~Copyable and ~Escapable, and is fundamentally based around copyable elements, posing a limitation on working with Span types, inline arrays, and other types that use the newer noncopyable and nonescapable features.
Protocols can have requirements loosened on them, such as with the introduction of ~Copyable to Equatable in SE-0499, or using the proposed SE-0503, which would provide language support for associated types to be marked ~Copyable or ~Escapable.
The design challenge with Sequence, though, is more fundamental. A sequence provides access to its elements through an Iterator, and an iterator's next() operation returns an Element?. For a sequence of noncopyable elements, this operation could only be implemented by consuming the elements of the iterated sequence, with the for loop taking ownership of the elements individually.
While consuming iteration is sometimes what you want, borrowing iteration is equally important, serves as a better default for noncopyable elements, and yet cannot be supported by the existing Sequence.
Proposed solution
This proposal introduces a new Iterable protocol, with iteration based around providing Spans of elements instead of individual elements, eliminating the need to copy. This pattern is also more optimizable in many cases where an iterated type is backed by contiguous memory.
Detailed design
The Iterable protocol is defined as:
public protocol Iterable<Element, Failure>: ~Copyable, ~Escapable {
/// A type representing the iterable type's elements.
associatedtype Element: ~Copyable
/// A type representing an error thrown during iteration.
associatedtype Failure: Error = Never
/// A type that provides the iteration interface and
/// encapsulates its iteration state.
associatedtype IterableIterator: IterableIteratorProtocol<Element, Failure> & ~Copyable & ~Escapable
/// Returns a borrowing iterator over the elements of this sequence.
@_lifetime(borrow self)
func makeIterableIterator() -> IterableIterator
/// A value less than or equal to the number of elements in the sequence,
/// calculated nondestructively.
var underestimatedCount: Int { get }
/// Internal customization point for fast `contains(_:)` checks.
func _customContainsEquatableElement(_ element: borrowing Element) -> Bool?
}
// Default implementations
extension Iterable where Self: ~Copyable & ~Escapable, Element: ~Copyable {
public var underestimatedCount: Int { 0 }
public func _customContainsEquatableElement(...) -> Bool? { nil }
}
This protocol shape is very similar to the current Sequence. It has a primary associated type for the element, and a method that hands you an iterator you can use to iterate the elements of the sequence.
The differences from the Sequence protocol are as follows:
Iterableallows conformance by noncopyable and nonescapable types. Note that copyable and escapable types can also conform, but the protocol is designed to not require it.- The
Elementtype is also not required to be copyable. - There is an
IterableIteratorassociated type, and amakeIterableIterator()method that returns one. These play a similar role toIteratorandmakeIterator()onSequence. - The iterator returned by
makeIterableIteratoris constrained to the lifetime of the sequence. This allows the iterator to be implemented in terms of properties borrowed from the sequence or aRefof the sequence itself. Iterabledefines an associatedFailuretype that enables throwing during iteration. Throwing iteration allows the broadest set of types to conform toIterable, including lazy transformations and types with elements that can throw during generation or access.
Note that the names of the associated type and iterator-providing method are specifically chosen to not conflict with existing names on Sequence, allowing a type to have different implementations for both Iterable and Sequence. The underestimatedCount and _customContains... requirements, however, must have the same semantics between the two protocols, and therefore have the same names.
The IterableIteratorProtocol is similar to its analog, but differs a little more:
public protocol IterableIteratorProtocol<Element, Failure>: ~Copyable, ~Escapable {
/// A type representing the iterated elements.
associatedtype Element: ~Copyable
/// A type representing an error thrown during iteration.
associatedtype Failure: Error = Never
/// Returns a span over the next group of contiguous elements, up to the
/// specified maximum number.
@_lifetime(&self)
mutating func nextSpan(maximumCount: Int) throws(Failure) -> Span<Element>
/// Advances this iterator by up to the specified number of elements and
/// returns the number of elements that were actually skipped.
mutating func skip(by maximumOffset: Int) throws(Failure) -> Int
}
// Default implementations
extension IterableIteratorProtocol where Element: ~Copyable {
public mutating func nextSpan() throws(Failure) -> Span<Element> { ... }
public mutating func skip(by maximumOffset: Int) throws(Failure) -> Int { ... }
}
Instead of returning individual elements from a next() method as IteratorProtocol does, IterableIteratorProtocol offers up spans of elements. The iterator indicates there are no more elements to iterate by returning an empty Span.
As with Sequence, once an iterator returns an empty Span, every subsequent call to nextSpan() must return an empty Span as well. An iterator's behavior after throwing an error is undefined: some iterators may treat that as the end of the sequence, some may continue to throw the same error or a different error, and some may resume iteration on the next call. Generic code should therefore not assume any particular behavior, with a recommendation that the error be propagated to the caller.
Iterator and element lifetimes
For noncopyable and/or nonescapable types, the Iterable protocols provide lifetimes that are tightly scoped to the providing types. In general, the IterableIterator of an iterable type is a nonescapable type with a lifetime borrowed from the original type. For example, the iterator for InlineArray is SpanIterator, a nonescapable type that provides access to the array's storage via a Span.
To support a broad range of iterator types, the Span returned from an iterator's nextSpan(...) method has an exclusive access dependency on the iterator (i.e. @_lifetime(&self)). This means that the elements accessed via that span also have an exclusive access dependency, with lifetimes ending on the next call to nextSpan() or another mutating call to the iterator.
For Iterable types with ~Copyable element types, this means that some operations that are common in sequence iteration are not possible to implement:
- Returning an element: In the most general case, a method like
first(where:)cannot be implemented in an extension onIterable, because the selected element's lifetime is tied to the iterator created within the method. - Escaping an element from a loop: For the same reason, the functionality of
first(where:)could not be coded in-place using afor-inloop to find an element and assign it to a variable outside the loop's scope. - Comparing elements across
Spanaccesses: A method likeallEqual(), that checks whether every element in a sequence is equal to every other element, cannot be implemented in the most general case forIterable. Because full iteration of anIterabletype requires callingnextSpan()an unknown number of times, the implementation would require preserving an element across those calls, violating exclusive access.
None of these restrictions apply when an Iterable type's element is Copyable, so these are not new restrictions compared to what Sequence provides. Only operations written to explicitly generalize the implicit Copyable constraint would be bound by the lifetimes.
Span size
The number of elements in each span is determined by both the conforming type and the caller. For the conforming type, the usual implementation will be to provide the largest span possible for each call. In the case of InlineArray, or other contiguously-stored types, this is just a single span for the entire collection.
Examples where nextSpan may be required to be called more than once include:
- Types where elements are held in discontiguous storage, such as a ring buffer. A ring buffer would provide two spans: one from the first element to the end of the buffer, followed by one from the start of the buffer to the last element.
- Types that produce elements on demand, such as a
Range. Because the elements of a range aren't stored directly in memory, the iterator would provide access to a span of a single element at a time. Note that this is how anySequencecan be adapted to conform toIterable(see later in this proposal). - Callers that only process a certain number of elements at a time would pass their limit as
maximumCount, with successive calls tonextSpanuntil the returned span is empty.
Specifying a maximum number of elements is important for use cases where an iterator is passed inout to another function, which consumes only as many elements as it needs and no more. This is required as a result of the bulk iteration model, unlike IteratorProtocol.next(), which returns only one element at a time.
Additionally, the maximum parameter provides a convenience for the caller. Because calling nextSpan is mutating, a caller that can only handle a specific number of elements at a time would otherwise need to write complex code to manage partial usage of a returned span.
The maximum count also gives signal to the iterator that only a specific number of elements are needed, which can be used to produce results more efficiently. For example, a lazily filtered span might want to serve up "runs" of filtered-in elements from the original collection, in which case you really want to know how many the caller actually wants to consume.
Throwing iteration
Both Iterable and IterableIteratorProtocol include a Failure associated type that defaults to Never. When iteration is simply providing access to a type's storage, as with InlineArray and UniqueArray, the Never failure type allows iteration without the try keyword or handling of throwing in the surrounding contexts. However, for types that can fail during iteration, like a lazy filter wrapper, using for-in syntax or calling an iterator's nextSpan() or skip(by:) methods requires the try keyword.
To iterate over a throwing Iterable type, callers use for try element in iterable, similar to iterating over an AsyncSequence. The desugared form of a throwing loop follows the same structure shown in the non-throwing case above, with try added to the nextSpan() call.
Because Failure is a typed-throws associated type, generic algorithms can propagate the failure type exactly. An algorithm declared as throws(Failure) will be non-throwing when the concrete Iterable has a Failure type equal to Never, and will throw the specific error type otherwise. See the example_reduce(into:_:) declaration below for an example.
Use of the new protocols
To illustrate how these new protocols would be used, we can also look at the proposed desugaring of the for-in syntax. The following familiar code:
for element in myIterable {
f(element)
g(element)
}
would cause the compiler to generate code similar to:
var iterator = myIterable.makeIterableIterator()
while true {
let span = iterator.nextSpan(maximumCount: Int.max)
if span.isEmpty { break }
for i in span.indices {
f(span[i])
g(span[i])
}
}
This automatic code generation is often referred to as "desugaring" the loop.
Note, the compiler will not necessarily generate this exact code, but it is illustrative of how a user might use the methods directly. The inner for i in span.indices, followed by access to the individual elements by subscripting with i wherever you would previously have used the loop variable, will be familiar to anyone who has iterated spans of noncopyable elements as they exist today. It allows noncopyable elements to be passed directly into functions like f and g without the need for a temporary variable.
This desugared while loop is more complex than its Sequence equivalent, but the day-to-day usage remains exactly the same, with the added complexity left to the caller.
Example Iterable algorithms
The following two examples, included in this proposal only for illustration, show how some Iterable operations will be as simple as their Sequence counterparts, while others will require more careful manual iteration.
The differences between an implementation of reduce(into:_:) for Sequence and Iterable are only in the parameters' ownership annotations, because we only need access to one element at a time. The implementation itself is essentially identical:
extension Iterable where Element: ~Copyable {
func example_reduce<T: ~Copyable>(
into initial: consuming T,
_ nextPartialResult: (inout T, borrowing Element) -> Void
) throws(Failure) -> T {
var result = initial
for try element in self {
nextPartialResult(&result, element)
}
return result
}
}
In order to properly implement elementsEqual, however, we must use manual iteration to compare spans of equal size between two Iterable types:
extension Iterable where Self: ~Escapable & ~Copyable, Element: ~Copyable & Equatable {
func example_elementsEqual<S: Iterable<Element, Failure>>(
_ rhs: borrowing S
) throws(Failure) -> Bool
where S: ~Escapable & ~Copyable
{
var iter1 = makeIterableIterator()
var iter2 = rhs.makeIterableIterator()
while true {
var span1 = try iter1.nextSpan(maximumCount: .max)
if span1.isEmpty {
// LHS is empty - sequences are equal iff RHS is also empty
let span2 = try iter2.nextSpan(maximumCount: 1)
return span2.isEmpty
}
while span1.count > 0 {
let span2 = try iter2.nextSpan(maximumCount: span1.count)
if span2.isEmpty { return false }
for i in 0..<span2.count {
if span1[i] != span2[i] { return false }
}
span1 = span1.extracting(droppingFirst: span2.count)
}
}
}
}
Standard Library adoption
InlineArray and the various Span types will conform to Iterable.
extension Span: Iterable
where Self: ~Copyable & ~Escapable, Element: ~Copyable
{
@_lifetime(borrow self)
func makeIterableIterator() -> SpanIterator<Element>
}
extension MutableSpan: Iterable
where Self: ~Copyable & ~Escapable, Element: ~Copyable
{
@_lifetime(borrow self)
func makeIterableIterator() -> SpanIterator<Element>
}
extension RawSpan: Iterable {
@_lifetime(borrow self)
func makeIterableIterator() -> SpanIterator<UInt8>
}
extension MutableRawSpan: Iterable {
@_lifetime(borrow self)
func makeIterableIterator() -> SpanIterator<UInt8>
}
extension InlineArray: Iterable
where Self: ~Copyable & ~Escapable, Element: ~Copyable
{
@_lifetime(borrow self)
func makeIterableIterator() -> SpanIterator<Element>
}
Each of these types use a new borrowing iterator type, SpanIterator, that is suitable for types that store their elements in a single contiguous block of memory. The SpanIterator type stores both a Span and the current offsets into the span, to allow flexibility for future kinds of iteration.
/// A borrowing iterator type that provides access to the contents of a single
/// span of elements.
public struct SpanIterator<Element>: IterableIteratorProtocol, ~Copyable, ~Escapable
where Element: ~Copyable
{
public typealias Failure = Never
@_lifetime(copy elements)
public init(_ elements: Span<Element>)
@_lifetime(&self)
public mutating func nextSpan(maximumCount: Int) -> Span<Element>
public mutating func skip(by offset: Int) -> Int
}
Adapters for existing Sequence types
As mentioned above, it is possible given an implementation to Sequence to implement the necessary conformance to Iterable. We propose the following addition to the standard library:
// An adapter type that, given an IteratorProtocol instance, serves up spans
// of each element generated by `next` one at a time.
public struct IterableIteratorAdapter<Iterator: IteratorProtocol>: IterableIteratorProtocol {
public typealias Failure = Never
var iterator: Iterator
var currentValue: Iterator.Element? = nil
public init(iterator: Iterator) {
self.iterator = iterator
}
@_lifetime(&self)
public mutating func nextSpan(maximumCount: Int) -> Span<Iterator.Element> {
// It may be surprising to some readers not used to Swift's ownership
// model that currentValue is a stored property, not just a local variable.
// This is because currentValue must be storage owned by the adapter
// instance, in order to return a span of its contents with the specified lifetime.
currentValue = iterator.next()
// note Optional._span is a private method in the standard library
// that creates an empty or 1-element span of the optional
return currentValue._span
}
}
extension Sequence {
public func makeIterableIterator() -> IterableIteratorAdapter<Iterator> {
IterableIteratorAdapter(iterator: makeIterator())
}
}
Given this, it will be possible for all types conforming to Sequence to also conform to Iterable. The conformance of existing sequence types, like Array, Dictionary, and UnfoldSequence, will be included in a future proposal. Some of these types (such as Array) will merit a custom iterator exposing an underlying Span. For other types, the conformance will trivially make use of the IterableIteratorAdapter shown above.
Suppressed conformance of the IterableIterator associated type
Proposal SE-0503 allows the suppression of Copyable and Escapable on associated types.
Since Element is a primary associated type, users will be able to extend Iterable with algorithms that require copyability by default. For example, an algorithm to return the minimum element requires the ability to copy that minimum element in order to return it. Extensions on Iterable without specifying otherwise will default to Element being copyable, as specified by SE-0503. Swift users unaware of the concept of noncopyable types can extend Iterable without being aware of that feature of the language.
The IterableIterator associated type is not a primary associated type; rather it's an implementation detail of an Iterable type. Therefore, per SE-0503, it will not default to being either copyable or escapable.
This is a highly desirable property. While Sequence iterators are copyable, the actual behavior of a particular iterator when you iterate, copy it, then iterate the copy, is very implementation dependent. The Sequence protocol gives no specifications for how an iterator should behave when you do this in a generic context. As such, writing generic code that relies on being able to copy an iterator is never appropriate.
Additionally, many types (like Span or InlineArray) will require a nonescaping iterator. The preferred behavior for users, even those not aware that noncopyable or nonescapable types exist, is to allow extensions written against Iterable to "just work" on those types, since needing to copy or escape an iterator is rarely bumped into when implementing most sequence algorithms.
Use of @_lifetime
Both Iterable and IterableIteratorProtocol have methods that return a non-escapable type (the IterableIterator and a Span, respectively), with a lifetime tied to self. This will require conforming types to enable the Lifetimes experimental feature.
Using these types – either directly, or via the for syntax – will not generally require use of lifetime annotations or enabling of the experimental feature (unless the user intends to e.g. return the iterator out of a function).
Algorithms written as extensions on Iterable should similarly not commonly need use of lifetime annotations.
for-in loop desugaring when both protocols are available
In order to preserve the performance and semantics of existing code that uses for-in loops, the generated code will only use borrowing iteration for types that only conform to Iterable, or in contexts where only Iterable conformance can be assured.
Existing code written with types that conform to both Iterable and Sequence will call the makeIterator() method and iterate over each element using that approach.
In effect, this means that InlineArray and the span types will be the only ones to use borrowing iteration. Types like Array, if given conformance to Iterable, would continue to use the element-wise Sequence-based iteration model for existing code that they use today.
For the remainder of the proposal, including future directions and alternatives that we considered along the way, please see the full proposal.