SE-0516: Borrowing Sequence

Evolution Proposal Reviews
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