Iterable

借用ベースでイテレーションを行うための新しいプロトコル Iterable と、その IterableIteratorProtocol を導入します。イテレーションの単位は個々の要素ではなく Span<Element> で、一度に連続した要素をまとめて渡すバルクイテレーションになっています。同時に、イテレーション中にエラーを throw できる仕組みも組み込まれており、for-in 構文でもそのまま使えます。

Iterable / IterableIteratorProtocol

Iterable は、Sequence と似た形でありながら、プロトコル自身も Element も non-copyable / non-escapable であってよいように設計されています。さらに、イテレーション中に throw する型に対応するための Failure 関連型を持ちます。

public protocol Iterable<Element, Failure>: ~Copyable, ~Escapable {
  associatedtype Element: ~Copyable
  associatedtype Failure: Error = Never
  associatedtype IterableIterator:
    IterableIteratorProtocol<Element, Failure> & ~Copyable & ~Escapable

  @_lifetime(borrow self)
  func makeIterableIterator() -> IterableIterator

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

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

イテレータ側は、next() で要素を1つ返す代わりに、nextSpan(maximumCount:) で 要素の連続領域（Span） をまとめて返します。Failure を typed throws で伝搬するため、Failure が Never のときは try なしで呼び出せ、それ以外では try が必要になります。

public protocol IterableIteratorProtocol<Element, Failure>: ~Copyable, ~Escapable {
  associatedtype Element: ~Copyable
  associatedtype Failure: Error = Never

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

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

空の Span を返すことで「もう要素がない」ことを表します。Sequence と同様に、一度空の Span を返したら以降の nextSpan(maximumCount:) も空の Span を返さなければなりません。maximumCount で呼び出し側が一度に欲しい要素数の上限を指定できるので、イテレータを inout で別の関数に渡して必要な分だけ消費する、といった使い方にも対応できます。

エラーを throw した後のイテレータの振る舞いは未定義です。終端として扱う実装も、同じエラーを繰り返す実装も、次回呼び出しでイテレーションを再開する実装もあり得ます。汎用コードでは特定の挙動を仮定せず、エラーは呼び出し元に伝搬させるのが推奨です。

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

イテレータと要素の lifetime

non-copyable / non-escapable な型を扱うために、Iterable まわりの lifetime はかなり厳密にスコープされています。IterableIterator は通常、Iterable 型から借用された lifetime を持つ non-escapable 型で、たとえば InlineArray のイテレータは内部ストレージへの Span を提供する SpanIterator です。

nextSpan(maximumCount:) が返す Span は、イテレータへの排他アクセスに依存（@_lifetime(&self)）します。つまり、その Span を介してアクセスできる要素の lifetime は、次の nextSpan 呼び出しやイテレータへの他の mutating 呼び出しで終了します。

このため、Element が non-copyable な Iterable では、Sequence で書けたいくつかの操作が一般形では書けなくなります。

• 要素を返す: first(where:) のような、選び取った要素を返すメソッドはメソッド内で作ったイテレータに lifetime が紐付くため、一般形では Iterable のエクステンションとして実装できません。
• ループの外へ要素を持ち出す: 同じ理由で、for-in の中で見つけた要素をループの外側の変数に代入する書き方もできません。
• 複数の Span 越しに要素を比較する: allEqual() のように、nextSpan を何度も呼び出しながら以前の Span の要素を持ち越して比較するような実装は、排他アクセスに反するため一般形では書けません。

ただし、これらの制約は要素が Copyable のときには適用されません。要素が copyable な Iterable 型では、Sequence と同じ感覚で書けます。

for-in の脱糖

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

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

↓

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])
    }
}

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

Failure が Never 以外の Iterable を回す場合は、AsyncSequence と同じく for try element in iterable の形で書きます。脱糖でも nextSpan() の呼び出しに try が付き、Failure がそのまま typed throws として伝搬します。これによって、example_reduce(into:_:) のような汎用アルゴリズムを throws(Failure) で宣言しておけば、具体型の Failure が Never なら non-throwing に、それ以外なら正確な型でエラーを throw する関数として振る舞います。

標準ライブラリでの採用

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

extension Span: Iterable
   where Self: ~Copyable & ~Escapable, Element: ~Copyable
{
   @_lifetime(borrow self)
   func makeIterableIterator() -> SpanIterator<Element>
}

extension InlineArray: Iterable
   where Self: ~Copyable & ~Escapable, Element: ~Copyable
{
   @_lifetime(borrow self)
   func makeIterableIterator() -> SpanIterator<Element>
}

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

既存の Sequence からのアダプタ

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

extension Sequence {
  public func makeIterableIterator() -> IterableIteratorAdapter<Iterator> {
    IterableIteratorAdapter(iterator: makeIterator())
  }
}

これにより、すべての Sequence は自動的に Iterable としても振る舞えるようになります。Array や Dictionary、UnfoldSequence といった具体型の適合は後続の提案で扱う予定で、Array のような連続メモリ型にはより効率的なカスタムイテレータが用意される見込みです。それ以外の型は IterableIteratorAdapter をそのまま使う形になります。

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

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

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

reduce(into:_:) のように一度に 1 要素しか見ないアルゴリズムは、Sequence 版とほぼ同じ素直な実装になります。throws(Failure) を宣言しておくことで、throwing / non-throwing の両方に対応できます。

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
   }
}

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

var iter1 = makeIterableIterator()
var iter2 = rhs.makeIterableIterator()
while true {
   var span1 = try iter1.nextSpan(maximumCount: .max)
   if span1.isEmpty {
      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)
   }
}

@_lifetime について

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

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

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

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