SE-0052 | Swift Evolution↗

Change IteratorType post-nil guarantee

Proposal: SE-0052↗
Authors: Patrick Pijnappel
Review Manager: Chris Lattner
Status: Implemented (Swift 3.0)

01 何が問題だったのか

Swift 2 時点の IteratorType（現在の IteratorProtocol）の next() には、「一度 nil を返した後にもう一度 next() を呼んではいけない」という事前条件がドキュメント上で課されていました。つまり nil を返した後の振る舞いは未定義で、2回目以降の呼び出しで nil 以外の値が返ってきても、クラッシュしても、仕様上は許されていたということです。実際、ドキュメントではその違反に対して preconditionFailure() を投げることすら推奨されていました。

一方で、標準ライブラリが提供していた27種類すべてのイテレータは、一度 nil を返した後は延々と nil を返し続ける実装になっていました。このため多くの利用者は「イテレータは尽きたらずっと nil を返すもの」と自然に思い込み、その前提でコードを書いていました。

たとえば、次のように while let を2回続けて書くコードは、この思い込みに依存した典型例です。

// シーケンスの一部を先に消費し、条件を満たす最初の要素に対して foo を呼ぶ
while let element = iterator.next() {
  if condition(element) {
    foo(element)
    break
  }
}
// 残りの要素に対して bar を呼ぶ
while let element = iterator.next() {
  bar(element)
}

最初のループが途中で break せず最後まで回り切った場合、iterator.next() は一度 nil を返しています。続く2つ目のループで再び next() を呼び出すのは、当時の契約では違反でした。

このような書き方は、標準ライブラリ付属のイテレータを相手にしているうちは期待通りに動きます。ところが、nil を返し続けない独自イテレータを渡された途端、一度尽きたはずのイテレータから値が流れ出してきたり、あるいは preconditionFailure() でクラッシュしたり、といった挙動が表面化します。テストでは気付きにくい、静かなコーナーケースを生み出していました。

契約の非対称性

問題の本質は、「実装者が守るべきこと」と「利用者が暗黙に期待すること」がずれていた点にあります。

利用者側の誤解: 尽きた後のイテレータは nil を返し続けるはず、と思い込みやすい（標準ライブラリの実装がすべてそうなっているため）。
実装者側の誤解: カスタムイテレータを書くとき、契約上は nil を返した後の振る舞いを保証しなくてよい、ということを知っていても守らなくてよい、と解釈しやすい。

どちらの誤解も黙って破綻するうえに、ほとんどの利用シーンでは表に出てきません。また、UTF-8 のデコードのように、利用者側で「すでに nil が来たか」を追加の Bool で管理しなければならない箇所では、最適化で消せない分岐が残り、性能面の不利益も発生していました。

02 どのように解決されるのか

next() の契約を、多くの人が暗黙に期待していた通りに書き換えます。すなわち、一度 nil を返したら、以降の呼び出しはすべて nil を返さなければならない という保証をプロトコル側に昇格させます。

ドキュメント上の文言は次のように変わります（Swift 2 では IteratorType、Swift 3 以降では IteratorProtocol ですが、変更点は同じです）。

変更前:

/// Advance to the next element and return it, or `nil` if no next
/// element exists.
///
/// - Precondition: `next()` has not been applied to a copy of `self`
///   since the copy was made, and no preceding call to `self.next()`
///   has returned `nil`.

変更後:

/// Advance to the next element and return it, or `nil` if no next element
/// exists.  Once `nil` has been returned, all subsequent calls return `nil`.
///
/// - Precondition: `next()` has not been applied to a copy of `self`
///   since the copy was made.

「nil を返した後に next() を呼んではいけない」という利用者側への制約が外れ、代わりに「nil を返した後も nil を返し続ける」という実装者側への保証が加わります。

利用者側への影響

これまで事前条件違反だった、while let を2回続けるような書き方が正当になります。

while let element = iterator.next() {
  if condition(element) {
    foo(element)
    break
  }
}
// 最初のループが最後まで回って nil が返っていても、
// 以降の next() は nil を返し続けるので安全
while let element = iterator.next() {
  bar(element)
}

UTF-8 デコーダのように、「すでに終端に達したか」を自前の Bool で覚えておいて分岐していたコードも、その状態管理を手放せるようになります。呼び出し側の最適化の妨げになっていた分岐が消えるため、ASCII 入力での UTF-8 デコードで約 25% の高速化が見込める、といった効果も報告されています。

実装者側への影響

自前のイテレータを書くときは、一度 nil を返したら以降も nil を返し続けるように実装する責任を負います。標準ライブラリに含まれていた既存のイテレータはいずれも元々この挙動になっていたため、実装側の追加作業はほぼありません。ただし、たとえば「途中で条件を満たさなくなったら nil を返す」タイプのイテレータ（TakeWhileIterator のようなもの）を素朴に書くと、内部状態を再評価した結果 nil 以外の値を再び返してしまう余地があります。このようなケースでは、「もう終わった」ことを覚えるフラグを1つ持たせて、2回目以降は即座に nil を返すようにする必要があります。

struct TakeWhileIterator<Base: IteratorProtocol>: IteratorProtocol {
  var base: Base
  let predicate: (Base.Element) -> Bool
  var finished = false

  mutating func next() -> Base.Element? {
    if finished { return nil }
    guard let element = base.next(), predicate(element) else {
      finished = true
      return nil
    }
    return element
  }
}

呼び出し側がこの保証に依存しない使い方（通常の for in など）をしている場合は、finished フラグとその分岐はコンパイラによって最適化で消えることが多く、性能上のコストも抑えられます。

この変更は Swift 3.0 で取り込まれ、現在の IteratorProtocol の契約として定着しています。