Borrowing Sequence

借用ベースでイテレーションを行うための新しいプロトコル BorrowingSequence と、その BorrowingIteratorProtocol を導入します。イテレーションの単位は個々の要素ではなく Span<Element> で、一度に連続した要素をまとめて渡すバルクイテレーションになっています。for-in 構文でもそのまま使えます。

BorrowingSequence / BorrowingIteratorProtocol

BorrowingSequence は、Sequence と似た形でありながら、プロトコル自身も Element も non-copyable / non-escapable であってよいように設計されています。

public protocol BorrowingSequence<Element>: ~Copyable, ~Escapable {
  associatedtype Element: ~Copyable
  associatedtype BorrowingIterator:
    BorrowingIteratorProtocol<Element> & ~Copyable & ~Escapable

  @lifetime(borrow self)
  func makeBorrowingIterator() -> BorrowingIterator

  var underestimatedCount: Int { get }
  func _customContainsEquatableElement(_ element: borrowing Element) -> Bool?
}

makeBorrowingIterator() が返すイテレータは、sequence 自身を borrow する lifetime を持ちます。これによって、イテレータは sequence から借用した内部バッファ（典型的には Span）を使って実装できます。

イテレータ側は、next() で要素を1つ返す代わりに、nextSpan(maximumCount:) で 要素の連続領域（Span） をまとめて返します。

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

  @lifetime(&self)
  mutating func nextSpan(maximumCount: Int) -> Span<Element>

  mutating func skip(by maximumOffset: Int) -> Int
}

空の Span を返すことで「もう要素がない」ことを表します。maximumCount で呼び出し側が一度に欲しい要素数の上限を指定できるので、イテレータを inout で別の関数に渡して必要な分だけ消費する、といった使い方にも対応できます。

連続メモリに要素を持つ型（Array のような型）なら、nextSpan を1回呼ぶだけで全要素分の Span を返せます。一方で、リングバッファのように要素が非連続に置かれている型は複数回の呼び出しで複数の span を返し、Range のようにその場で要素を生成する型は、イテレータ内部のストレージに要素を保持したうえで 1 要素分の span を返す、といった実装が可能です。

for-in の脱糖

BorrowingSequence に対する for-in は、おおむね次のようなコードに展開されます。

for element in borrowingSequence {
    f(element)
    g(element)
}

↓

var iterator = borrowingSequence.makeBorrowingIterator()
while true {
    let span = iterator.nextSpan(maximumCount: Int.max)
    if span.isEmpty { break }

    for i in span.indices {
        f(span[i])
        g(span[i])
    }
}

ループ変数 element の代わりに span[i] を使って non-copyable な要素へ直接アクセスできるため、一時変数を経由せずに f / g に渡せます。利用者側の体感は従来の for-in とほぼ同じで、複雑さはコンパイラが吸収してくれます。

標準ライブラリでの採用

各種 Span 系の型と InlineArray が BorrowingSequence に適合し、共通のイテレータ型 SpanIterator<Element> を使います。

extension Span: BorrowingSequence
   where Self: ~Copyable & ~Escapable, Element: ~Copyable
{
   @lifetime(borrow self)
   func makeBorrowingIterator() -> SpanIterator<Element>
}

extension InlineArray: BorrowingSequence
   where Self: ~Copyable & ~Escapable, Element: ~Copyable
{
   @lifetime(borrow self)
   func makeBorrowingIterator() -> SpanIterator<Element>
}

MutableSpan、RawSpan、MutableRawSpan も同様に適合します。

既存の Sequence からのアダプタ

既存の Sequence 適合型も BorrowingSequence に適合できるよう、アダプタが用意されます。BorrowingIteratorAdapter は内部に通常の IteratorProtocol を持ち、next() で取り出した要素をストアドプロパティに保持して、その 1 要素分の span を返します。

extension Sequence {
  public func makeBorrowingIterator() -> BorrowingIteratorAdapter<Iterator> {
    BorrowingIteratorAdapter(iterator: makeIterator())
  }
}

これにより、すべての Sequence は自動的に BorrowingSequence としても振る舞えるようになります。Array のような連続メモリ型には、後続の提案でより効率的なカスタム適合（内部 Span を直接返す形）が追加される見込みです。

両方に適合している場合の for-in

BorrowingSequence と Sequence の両方に適合する型（あるいは両方で語れる文脈）では、既存コードの意味・性能を壊さないために、for-in は従来どおり Sequence 側の makeIterator() を使うように脱糖されます。借用イテレーションが使われるのは、BorrowingSequence にしか適合していない型（InlineArray や span 系）や、BorrowingSequence のみを要求するジェネリック文脈に限られます。

アルゴリズム実装での使い心地

reduce(into:_:) のように一度に 1 要素しか見ないアルゴリズムは、Sequence 版とほぼ同じ素直な実装になります。

extension BorrowingSequence {
   func example_reduce<T: ~Copyable>(
      into initial: consuming T,
      _ nextPartialResult: (inout T, borrowing Element) -> Void
   ) -> T {
      var result = initial
      for element in self {
         nextPartialResult(&result, element)
      }
      return result
   }
}

一方、elementsEqual のように 2 つの sequence を同じペースで進めたいアルゴリズムでは、span の長さが揃わないので、nextSpan(maximumCount:) を使いながら手動で揃える実装が必要になります。

var iter1 = makeBorrowingIterator()
var iter2 = rhs.makeBorrowingIterator()
while true {
   var span1 = iter1.nextSpan(maximumCount: .max)
   if span1.isEmpty {
      let span2 = iter2.nextSpan(maximumCount: 1)
      return span2.isEmpty
   }
   while span1.count > 0 {
      let span2 = 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)
   }
}

@lifetime について

makeBorrowingIterator() や nextSpan(maximumCount:) は、戻り値に self への lifetime 依存を持たせる必要があるため、適合型の実装側では Lifetimes という experimental feature の有効化が求められます。一方で、for-in などを通して使う側は、イテレータを関数外へ返すような特殊な場合を除いて lifetime annotation を意識する必要はなく、BorrowingSequence を拡張して書くアルゴリズムでも同様です。

BorrowingIterator のコピー不可・エスケープ不可

primary associated type である Element は、従来どおりデフォルトで copyable として扱われます（SE-0503 の挙動）。そのため、non-copyable を意識せずに BorrowingSequence を拡張しても、min() のように要素をコピーして返すアルゴリズムは普通に書けます。

一方、BorrowingIterator は primary ではないため、デフォルトでは copyable にも escapable にもなりません。Sequence のイテレータはコピー可能ですが、コピー後に両方を進めたときの挙動は型次第で、汎用コードでそれに依存するのは不適切でした。BorrowingIterator を最初から non-copyable / non-escapable にしておくことで、Span や InlineArray のようにそもそもエスケープできないイテレータが必要な型でも、素直に汎用アルゴリズムに載せられます。

今後の展望

今回の提案は「借用によるイテレーション」のみを対象にしていますが、今後の拡張として、次のようなイテレーションの形もそれぞれ別提案で検討される可能性があります。

• consuming iteration（要素を消費しながら取り出す）
• “draining” iteration（要素だけ消費してコンテナ自体は残す）
• mutating iteration（要素を in-place で書き換える）
• generative iteration（UnfoldSequence のようにその場で要素を生成する型向けに、借用イテレーションより効率的なモデル）

また、別提案として、Sequence を BorrowingSequence の refinement に「付け替える」ための仕組みと、Array / Dictionary など既存型の BorrowingSequence 適合の追加が予定されています。これらが入ると、copyable・non-copyable の両方を扱える汎用アルゴリズムを BorrowingSequence 側に統一して書けるようになる見込みです。いずれも現時点で確定しているものではなく、あくまで将来の方向性です。