SE-0516: Borrowing Sequence

Evolution Proposal Reviews
1

Hello, Swift community!

The review of SE-0516: Borrowing Sequence begins now and runs through March 17, 2026.

Reviews are an important part of the Swift evolution process. All review feedback should be either on this forum thread or, if you would like to keep your feedback private, directly to me as the review manager by email or DM. When contacting the review manager directly, please put "SE-0516" in the subject line.

Trying it out

The toolchain with the latest implementation is currently building - I will update the review thread with the toolchain links for macOS, Linux, and Windows when they're ready later today.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  • What is your evaluation of the proposal?
  • Is the problem being addressed significant enough to warrant a change to Swift?
  • Does this proposal fit well with the feel and direction of Swift?
  • If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  • How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at:

swift-evolution/process.md at main · swiftlang/swift-evolution · GitHub

Thank you,

Holly Borla
Review Manager

10 Likes
[Pitch] Borrowing Sequence
[Returned for revision] SE-0516: Borrowing Sequence
2

I feel like this is a miss for a few reasons:

  • It's a really clunky protocol; it'd be a shame for this to be "the way to write sequences". Sequence is pretty easy. Rust's Iterator is easier in most circumstances. This is worse.
  • It seems to be "too soon" — it doesn't handle nonescaping elements, and doesn't seem like it'll be extensible to nonescaping elements in the future, given that they require lifetime annotations. I don't think nonescaping elements are an edge-case or uncommon need. So won't we just be back here in 6-12 months when lifetimes have caught up, trying to specify BorrowingNonescapingSequence?
  • It seems to be "too soon" — implementing it requires using the Lifetimes experimental feature. This was promised to be stable, but broke source-compatibility between 6.2 and 6.3 already. I don't trust that implementations of BorrowingSequence made for 6.4 will compile in 6.5.
  • I don't like that this isn't "replacing" Sequence, since there are cases that Sequence supports but BorrowingSequence does not. I'd like to see more discussion of whether there is a design that allows for a true one-size-fits-all?

Thoughts about a more one-size-fits-all solution:

Are we just ignoring Rust's prior art here? In Rust:

  • Iterator can be over values or borrows, and might or might not itself be escaping depending on which one.
  • There's only standardization on how to get a consuming iterator from a container. This means that for loops can be less ergonomic (for item in container consumes the container, for item in container.iter() is an ad-hoc standard to get a borrowing iterator, but it allows for other options like for item in container.drain(3..14) to get an iterator that consumes items in a specified range of a Vec, for example.

So what if,

  • We adjust IteratorProtocol to allow nonescaping implementors & nonescaping Element
  • The compiler's for syntax gets special support for IteratorProtocol<T> (current), IteratorProtocol<Borrow<T>> (new) and IteratorProtocol<Span<T>> (new):
    • When iterating sequences of Borrow, the iteration variable is implicitly shorthand for borrow.value (so you don't have to manually deref the borrow on each use within the loop)
    • When iterating sequences of Span, the iteration variable is implicitly shorthand for span[i]. This is more or less equivalent to BorrowingIteratorProtocol from the current proposal.
  • Sequence remains shorthand for "i can get a copying, escapable iterator"
  • We create an ad-hoc standard for getting a borrowing iterator, eg. for element in container.borrow(). I suggest this because it avoids ambiguity over "which kind of iterator is this for loop using" compared to having both Sequence and BorrowingSequence, and also makes it clear that offering other kinds of iterator through other ad-hoc methods is reasonable (see drain)
23 Likes
3

Would this support for inout element in array { ... } ?

1 Like
4

Another alternative direction could be to introduce the ability to syntactically overload the for loop without conforming to a protocol.

With property wrappers, SE-0258 explains the rationale for using a syntactic approach instead of a protocol:

I think a similar argument applies to iteration. Just like the wrappedValue property of a property wrapper (or the subscript operator of an arbitrary type), iteration can have many different kinds of ownership/mutability for both the collection and its elements. Furthermore, different iterators can have different lifetime semantics. The lifetime of elements yielded from a Span is different from those yielded from an Array, which is different from those yielded from a Range. Non-escapable elements would introduce even more nuances. The proposal acknowledges that the lifetime annotation @_lifetime(&self) is, for some types, more restrictive than necessary. I also think it's probably too early to decide which lifetime semantics would be most useful for generic algorithms. (Edit: The throws and async effects also add other dimensions of variation.)

Personally, I think it would be nice if writing a coroutine/generator became the syntax for overloading the for loop.

5 Likes
5

Comparing this to the for loop section of the Ownership Manifesto, it seems like the intention there was to use ownership declarations on the iteration variable to distinguish between different types of iteration, e.g.

for borrowing employee in company.employees {
  newCompany.employees.append(employee)
}

Would this be a way for users of the API to be able to choose whether they want iteration from Sequence or BorrowingSequence?

The manifesto also shows generators as the mechanism by which other types of iteration could be implemented. Was that considered as an option for this?

9 Likes
6 
  /// 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) -> Int

Can this intentionally under-skip? ie, could this return 0 even if it’s not at the end?

1 Like
7

Just chiming in here with a few nitty-gritty API naming comments:

  /// Returns a span over the next group of contiguous elements, up to the
  /// specified maximum number.
  @lifetime(&self)
  mutating func nextSpan(maximumCount: Int) -> Span<Element>

Standard library convention is to use "max" rather than "maximum" (with the limited exception of a specific IEEE floating-point API, which is its own bag of fish).

Additionally, there's no need here to state the return type in the name of this API—there isn't a need to disambiguate from next() -> Element as they differ in the number of arguments, and Span is an entirely reasonable return type (and probably the only one): therefore, something like next(maxCount: 4) would suffice.

(Nit: Elsewhere, "up to n" is the terminology we use for 0..<n, whereas I believe the intention here is that the count of the returned span is the closed range 0...n.)

Finally, it would be helpful to specify—and I believe all the stated use cases could guarantee this—that the returned span is empty if and only if we're at the end. The text strongly suggests that is the case, but in parts it technically leaves open the possibility of a conforming type which sporadically returns an empty span and then subsequently a non-empty span.

  /// 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) -> Int

Standard library precedent already includes the term "offset"—e.g., index(_:offsetBy:limitedBy:)—or "advance"—e.g. advanced(by:). I think it's fair to avoid using drop or pop (given differences in how those APIs behave), but we don't need to coin yet another verb here.

Given that "offset" was already thought fit for the internal parameter name, I think it's a great choice here for the API itself, clearer than "skip" as it eliminates doubts as to inclusivity of the start or end. If the ambiguity as to whether that's a verb or noun is thought to be disqualifying, then advance(by:) is fine too for an active verb, in my view.

It would be good to clarify the scenarios under which the supplied argument isn't the number of elements actually offset or advanced: if it's only when there aren't enough elements at the end, then by: is great as an argument label--and I wonder if the API should be @discardableResult; if there are other scenarios in which it may happen other than running off the end, then byMax: would be more fitting here to emphasize that (though I wonder if it should still be @discardableResult).

6 Likes
8

I’d like to note a subtle lifetime quirk. The proposed BorrowingIteratorProtocol’s nextSpan looks like this:

public protocol BorrowingIteratorProtocol<Element>: ~Copyable, ~Escapable {
  associatedtype Element: ~Copyable
  
  /// Returns a span over the next group of contiguous elements, up to the
  /// specified maximum number.
  @lifetime(&self)
  mutating func nextSpan(maximumCount: Int) -> Span<Element>
  
  // ...
}

The lifetime of the returned Span is tied to the lifetime of the iterator, not the sequence. This means it would not be possible to write generic algorithms that need to persist a borrow of an element beyond the scope of a for-loop. For example, take this generic search over noncopyable elements:

extension BorrowingSequence 
    where Self: ~Copyable & ~Escapable, 
          Element: ~Copyable, Equatable {

  @lifetime(borrow self)
  func first(_ e: Element) -> Borrow<Element>? {
    var found: Borrow<Element>? = nil
    for x in self {
      if x == e {
        found = x
        break
      }
    }
    return found
  }
}

I’m trying to find and return a Borrow of the first matching element, but I can’t write it like this. Based on this proposal, the function body would correspond to this desugaring:

@lifetime(borrow self)
func first(_ e: Element) -> Borrow<Element>? {
  var found: Borrow<Element>? = nil
  do {  // desugared for-in loop with early 'break'
    var iterator = self.makeBorrowingIterator()
    var endIteration = false
    while !endIteration {
      let span = iterator.nextSpan(maximumCount: Int.max)
      if span.isEmpty { break }
      for i in span.indices {
        let x: Borrow<Element> = span[i]
        if x == e {
          found = x   // <-- illegal escape of the borrow 'x' to outer scope
          endIteration = true
          break
        }
      }
    }
  } // end 'do'
  return found
}

The do-block denotes the lexical scope of the original for-in loop. The lifetime of each Span returned by nextSpan is tied to the var iterator ‘s lifetime, which ends whenever the loop exits. So, I can’t store a borrow of the found element outside this do-block (i.e., the original for-loop) regardless of whether I use Borrow<T> or a pair of Span<Element> + an index.

I can only workaround this by taking the iterator as an argument to my first function and writing-out the desugared version using it, which I think is rather clumsy.

For algorithms that need to make two-passes over a BorrowingSequence within the same function, where the first pass is collecting borrows of interesting elements, the for-in syntax won’t work either. I’d have to drop down to using makeBorrowingIterator manually to keep the first iterator live during the second pass.

7 Likes
9

No. Rather, we're learning from Swift's prior art (IteratorProtocol), which just like Rust's Iterator, is based around returning one element at a time. This is simpler, but without optimization can be a real problem for performance. I think it is tempting here to think of "simple" and "elegant" as the same thing – but this isn't the case here. Rather, the simplicity leads to inelgance in the code that is generated. A wooden plank is simple, but inelegant as a way of crossing anything wider than a stream.

Ultimately, you want loops to compile down to something radically different from how they logically appear in the surface language. In the ideal and common case of a single contiguous blob of storage, you want to be able to eliminate things like bounds checks and function calls entirely and have a loop become just advancing a pointer over direct memory access until it reaches the end. Depending on what you're doing in the loop, the compiler may use pointers to objects in memory, or it may load things into registers, or even vectorize the loop using SIMD instructions.

Those assembly instructions will likely, and hopefully, bear little resemblance to the on the face of it much higher level "one at a time, call a function that returns an optional of the element type, unwrap that optional, and use the unwrapped value". Achieving this uses the well-known compiler technique of 1) inline the heck out of everything, and 2) throw the often hundreds of lines of IR that spills out at the optimizer, and cross your fingers. Unfortunately this technique is prone to failure, and you can end up with something closer to the surface-level logic even at the compiled binary.

So while this "seems simple, but it's not really what you want at the machine level" model mostly works out, there are lots of cases where it doesn't and you fall off the performance cliff:

  • In debug mode, where the optimizer doesn't eliminate many abstractions;
  • In complex code, where the optimizer can't chew through enough of the abstractions; and
  • With dynamically dispatched sequences, where you're not able to inline calls to next into the caller.

Now this last one is super important. It doesn't apply as much to Rust, which doesn't have a stable ABI or unspecialized generics, though you still can have dyn Iterator sometimes. But in Swift, it's really important to be able to write non-inlinable code in an ABI-stable framework that takes some BorrowingSequence and not have terrible performance when you pass it an Array.

This is the big difference with the bulk iteration approach of BorrowingSequence because it serves up a concrete type of Span<Element>. The call to makeBorrowingIterator and nextSpan may be dynamically dispatched, but once you have the span, you get to specialize iteration of it on the other side of the boundary. In the case of a single contiguously-stored collection, you only have to do that once.

This is what the increased complexity of serving up spans instead of elements gets you – a much more optimizable design. It also opens up more possibilities for e.g. optimizing the span operations even in debug mode, where more complex intraprocedural optimizations are undesirable (e.g. because they interfere with things like stepping in the debugger).

Note however that the complexity is not very "in your face" for many users.

In the case of consumers of the interface, nearly all code will continue to just be written against for loops, which just happen to desugar differently unbeknownst to the user. Yes there are some (relatively uncommon) cases where you cannot write a for loop with Sequence and have to reach directly for the iterator, and those algorithms are made more complex by the provision of spans. My feeling here is we should see how much of a problem this is, and provide a helper that re-creates the single-element next() operation if needed (you basically just call nextSpan(maximumCount: 1) and return the single element). Whether this is worth it probably will follow from real-world adoption feedback.

In the case of conformances: In a lot of cases, a user-defined type conforming to Sequence is a wrapper on top of another sequence-conforming type, and implementing the conformance will involve delegating to the wrapped type. In these cases, conforming to BorrowingSequence will take similar code, just forwarding on to nextSpan instead of next.

The proposal outlines an adaptor that allows a Sequence to also conform to BorrowingSequence. This makes it trivial for types that serve up elements one at a time to conform. The future direction of re-parenting Sequence on top of BorrowingSequence will mean this happens automatically.

21 Likes
10

Apologies for forgetting to post these! You can try out this proposal by downloading a development snapshot of the main branch from March 4th or later (at swift.org/install) and enabling the BorrowingSequence experimental feature flag.

Holly Borla
Review Manager

1 Like
11

The BorrowingSequence protocol is defined as:

public protocol BorrowingSequence<Element>: ~Copyable, ~Escapable {

  /* REDACTED */

  /// Internal customization point for fast `contains(_:)` checks.
  func _customContainsEquatableElement(_ element: borrowing Element) -> Bool?
}

Should the hidden _custom…EquatableElement(_:) requirements be formalized? I imagine that most developers won't have seen them before, because they aren't included in the "generated interface" or documentation (for Sequence and Collection). Outside of the standard library, the hidden requirements are implemented by apple/swift-collections, but they aren't implemented by apple/swift-algorithms.

2 Likes
12

Sorry for coming in late here, but I wonder whether the authors considered introducing support for throwing sequences like we have in AsyncSequence. This would involve introducing a Failure associated type to the protocols, which is then used as the thrown error type for nextSpan and skip, e.g.,

public protocol BorrowingSequence<Element, Failure>: ~Copyable, ~Escapable {
  associatedtype Element: ~Copyable
  associatedtype Failure: Error
  associatedtype BorrowingIterator: BorrowingIteratorProtocol<Element, Failure > & ~Copyable & ~Escapable
  // ...
}

public protocol BorrowingIteratorProtocol<Element, Failure>: ~Copyable, ~Escapable {
  associatedtype Element: ~Copyable
  associatedtype Failure: Error

  @lifetime(&self)
  mutating func nextSpan(maximumCount: Int) throws(Failure) -> Span<Element>
  
  mutating func skip(by maximumOffset: Int) throws(Failure) -> Int
}

I've seen this request come up a few times, but I personally care about it with respect to (borrowed) sequence algorithms. We have a discrepancy in the normal Sequence protocols between the eager algorithms like filter and map, where the closure can throw, and the lazy versions of those algorithms, which must take non-throwing closures because sequences can't throw.

Capturing the Failure type in the BorrowedSequence protocol lets us model this. Here's a very rough sketch, where it's admittedly annoying to have the overloading on filter:

struct LazyFilter<Seq: BorrowingSequence & ~Copyable & ~Escapable, Failure: Error>: BorrowingSequence, ~Copyable, ~Escapable {
  // ...
  typealias Element = Seq.Element
  init(seq: Seq, body: (Element) throws(Failure) -> Bool)  { ... }
}

extension BorrowedSequence where Self: ~Copyable & ~Escapable {
  // propagate the failure type from the underlying sequence
  func filter(body: (Element) throws(Failure) -> Bool) -> LazyFilter<Self, Failure> { ... }

  // take the closure's failure type
  func filter<ClosureFailure: Error>(body: (Element) throws(ClosureFailure) -> Bool) 
    -> LazyFilter<Self, ClosureFailure> where Failure == Never { ... }
}

My inclination is that, for borrowing sequence, the normal set of sequence algorithms should be lazy by default, using noncopyable and nonescapable types like LazyFilter above to enable algorithm composition without intermediate copies of the data. Including support for throwing sequences isn't strictly necessary to make this kind of laziness work, but it would make the result nicer.

Doug

9 Likes
13

+1

First off, I would like to say I am very excited to see progress in this area. Since Swift 2.0 I have periodically attempted to write ergonomic MachO parsers in Swift. We use MachO parsers in many places where copies and/or allocations are problematic, so in order to consider it for those uses we need to be able to build it using embedded (and potentially non-allocating) Swift, as well as utilizing ~Copyable and ~Escapable types in various places. The current lack of something like BorrowingSequence means it is not possible to ergonomically iterate through MachO loadCommands and segments.

Ideally I want to be able to write something like:

struct MachO: ~Escapable {
    @_lifetime(copy bytes)
    init(bytes: RawSpan) throws {
        // ...
    }
    enum LoadCommand: ~Copyable {
        case uuidCommand(UUID)
        case segmentCommand(Segment)
        // ...
    }
    struct LoadCommandSequence: BorrowingSequence<LoadCommand> {
       // ...
    }
    struct Segment: ~Copyable  {
        let name: String
    }
    struct SegmentSequence: BorrowingSequence<Segment> {
       // We might be able to avoid defining this type if we have lazy algs,
       // in which case segments could be a filter and a transform on loadCommands
    }
    let loadCommands: LoadCommandSequence
    let segments: SegmentSequence
}

func printUuidAndSegmentInfo(macho: MachO) throws {
    for loadCommand in macho.loadCommands {
        switch loadCommand {
        case .uuidCommand(let uuid): print("UUID \(uuidCommand)")
        case .segmentCommand(let segment): print("Segment name \(segmentCommand.name)")
        default: continue
        }
    }
}

I had a few minutes to port my test parser to borrowing sequence, and excluding the desugaring support and lack of builtin error handling it all seems to work.

A few other quick thoughts:

+1 to Doug’s comments on adding throws support… One of the issues we have with MachO parsing is that it is not practical read the entire binary up front, but we also need to be able to handle malformed binaries. In the example above we could hit a malformed loadCommand. Having some type of wrapper return result type is certainly viable, but it feels less ergonomic.

With respect to the adding complexity over IteratorProtocol to allow efficient usages of Spans for contiguous ranges of elements I think it is worthwhile here to allow for the performance benefits Ben mentioned, despite the fact that I do not believe they will work in the case of parsing MachO load commands due to the variable length encoding of the commands. While it might add a little boilerplate to my implementation to always return a one element Span I don’t think that is onerous, at least not in the context of code that is already opting into ~Escapable and ~Copyable types, but if we wanted to ship a convenience interface or adapter of some sort so those of us are not returning spans can just return the next object I would not object.

2 Likes
14

Thank you to everyone who participated in this review! The proposal has been returned for revision:

Holly Borla
Review Manager

1 Like