SE-0232 | Swift Evolution↗

Remove Some Customization Points from the Standard Library’s `Collection` Hierarchy

Proposal: SE-0232↗
Authors: Ben Cohen
Review Manager: Ted Kremenek
Status: Implemented (Swift 5.0)

01 何が問題だったのか

標準ライブラリの Sequence / Collection / BidirectionalCollection には、次のようなメソッド・プロパティが「プロトコル要件」として宣言されていました。

Sequence の map、filter、forEach
Collection の first、prefix(upTo:)、prefix(through:)、suffix(from:)
BidirectionalCollection の last

これらはいわゆる customization point（カスタマイズポイント）で、プロトコル本体に要件として書いた上で extension で既定実装を与える、というパターンで定義されていました。準拠型が独自実装を与えれば、ジェネリックな文脈（別の extension メソッドからの呼び出しなど）でも動的ディスパッチでその独自実装が呼ばれます。

カスタマイズポイントを置く二つの目的

カスタマイズポイントは一般に次の二つの目的で導入されます。

観測可能な振る舞いを変えたい場合。たとえば「要素を追加する」メソッドを、Set 型は重複を弾き、Bag 型は重複を許す、というように型ごとに意味を変えたいケースです。
より効率的な実装を与えたい場合。たとえば前方向にしか進めない Collection の count は既定ではO(n)ですが、ランダムアクセスでなくても自分の count を定数時間で知っている型はあり得ます。

今回対象のメソッドでは上記の目的が成り立たない

問題は、今回削除の対象になった map / filter / forEach / first / last / prefix(upTo:) / prefix(through:) / suffix(from:) について、この二つの理由がどちらも説得力を持たないという点です。

理由1（振る舞いを変える）は該当しません。これらのメソッドは意味論が明確で、既定の観測可能な振る舞いと違うことをしていたらむしろバグです。たとえば MyCollection.first が「先頭要素を返す」以外の追加の副作用を持つのは、ほぼ確実に設計ミスです。
理由2（高速化）も実用的なユースケースを見つけにくい状態でした。suffix(from:) のように既定実装自体がほぼ自明で、差し替える余地がないものもあります。forEach は resilient な型で「イテレータへの self のコピーによる参照カウント増を避ける」といった微小な最適化の余地があるものの、そのために「もしかしたら forEach の方が速いかも」と書き換える文化を奨励するのは、むしろ有害でした。実際、forEach を早期脱出するために throw と try? で制御フローをハックするコードが書かれ、デバッガのエラーブレークポイント利用を妨げる例も出ていました。

一方で、カスタマイズポイントはタダでは置けません。プロトコル要件ひとつひとつが witness table のエントリとなり、コンパイル時間・バイナリサイズ・実行時性能にわずかずつコストをかけていました。効果が薄いのにコストだけ払っている状態です。

ABI 安定化後は「減らす」ことができない

さらに決定的だったのが ABI 安定性とのタイミングです。一度 ABI が固定された標準ライブラリからは、カスタマイズポイントを追加することはできても削除することはできなくなります。Swift 5.0 で標準ライブラリの ABI 安定化を宣言する前に整理しておかないと、この負債は永久に残ります。

move-only 型を見据えた `first` / `last` の扱い

first と last にはもう一つ別の事情がありました。将来導入される予定の move-only 型（Array を含む）では、要素を返すには「取り出して所有権ごと返す」（popLast() のような API）か「借用して返す」（subscript のような API）の二択になります。Optional にラップして返すという形はそのどちらにも収まりません。汎用の実装として「subscript で先頭要素を得て、それを Optional に move し、Optional を返す」という流れは、move-only 型に対しては書けないのです。

そのため、move-only 要素を持つコレクションが Collection に適合できる余地を残すには、first と last を プロトコル要件から外しておく 必要があります。要件から外しておけば、将来 Element: Copyable に制約された extension としてのみ提供する、といった調整が可能になります。

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

この提案は、標準ライブラリの以下のメンバをプロトコル要件から取り除き、extension の既定実装としてのみ提供する 形に整理します。

Sequence の map、filter、forEach
Collection の first、prefix(upTo:)、prefix(through:)、suffix(from:)
BidirectionalCollection の last

要件からは消えますが、既定実装はそのまま残るため、ユーザー視点での機能は変わりません。[1, 2, 3].map { $0 * 2 } も array.first も collection.suffix(from: i) も、これまでどおり使えます。

let numbers = [1, 2, 3, 4]
let doubled = numbers.map { $0 * 2 }  // [2, 4, 6, 8]
let evens = numbers.filter { $0.isMultiple(of: 2) }  // [2, 4]
numbers.forEach { print($0) }

let head = numbers.first  // Optional(1)
let tail = numbers.last   // Optional(4)
let suffix = numbers.suffix(from: 2)  // [3, 4]

何が変わるのか

変化は主に型の作者側に現れます。これまでは Collection に適合する独自型で first や last を上書き（override）すると、ジェネリックな文脈でもその実装が動的ディスパッチで呼ばれていました。今後はプロトコル要件ではなくなるため、extension で定義したメソッドを override したときと同じ扱いになります。具体的には、静的型として独自型が見えている箇所では自分の実装が呼ばれますが、Collection として抽象化された文脈では既定実装が呼ばれます。

struct MyCollection: Collection {
  // ... 必須要件の実装 ...

  // ここで独自の first を書いても、
  // Collection として扱われる場面では既定実装が呼ばれるようになる
  var first: Element? { /* ... */ }
}

意味論的に「先頭要素を返す」以外のことをしているまともな実装は存在しないはずなので、実害はほとんどないという判断です。「first を override すると副作用が動く」ようなコードに依存していた場合は、別の設計に改める必要があります。

今回取り除かれた意味

標準ライブラリの軽量化。プロトコル要件を減らすことで、witness table のエントリが減り、コンパイル時間・バイナリサイズ・実行時性能にわずかながらプラスに働きます。また、「forEach の方が速いかもしれない」という根拠の薄い micro-optimization を誘発しにくくなります。
ABI 安定化前の整理。一度 ABI を固定するとカスタマイズポイントは削除不能になるため、Swift 5.0 の ABI 安定化前に確実に片付ける意味がありました。
move-only 型への布石。first / last を要件から外したことで、将来 move-only 要素を含むコレクションを Collection に適合させる際にも、これらを Element: Copyable 前提の extension として提供し直す、といった調整が可能になります。Optional に包んで返すことが move-only 要素と相性が悪いため、要件として残しておくと将来の拡張の足かせになっていました。

将来の見通し

move-only 型が正式に導入された段階で、言語側に「Optional へ借用したまま入れる」ような機能が加わる可能性もあり、その場合は move-only 要素を持つコレクションにも first に相当するプロパティが提供できるようになるかもしれません。ただしこれは speculative な話で、本提案ではあくまで「将来の選択肢を残すために要件から外す」という保守的な立ち位置に留めています。

Remove Some Customization Points from the Standard Library’s Collection Hierarchy