SE-0234 | Swift Evolution↗

Remove `Sequence.SubSequence`

Proposal: SE-0234↗
Authors: Ben Cohen
Review Manager: John McCall
Status: Implemented (Swift 5.0)

01 何が問題だったのか

標準ライブラリの Sequence プロトコルは、部分列を返すためのメソッド群を次のように宣言していました。

func dropFirst(_:) -> SubSequence
func dropLast(_:) -> SubSequence
func drop(while:) -> SubSequence
func prefix(_:) -> SubSequence
func prefix(while:) -> SubSequence
func suffix(_:) -> SubSequence
func split(separator:) -> [SubSequence]

これらはいずれも Sequence の associated type である SubSequence を返します。デフォルト実装は提供されているため、自作の Sequence 適合型で実装し直す必要はありません。しかし、この「部分列の型をひとつにそろえる」という設計には、次のような無視できない問題がありました。

1 パスのシーケンスでは、各メソッドに最適な戻り値型がそれぞれ違う

1 パスでしか走査できない Sequence にこれらのメソッドを素直に実装しようとすると、メソッドごとに理想的な戻り値の作り方がまったく異なることがわかります。

dropFirst は、先頭 n 要素を捨ててから値を返し始めるラッパー型を返すのが最も自然です。
prefix(_:) は逆に、n 要素を返したら停止するラッパー型です。
suffix と dropLast は末尾を知る必要があるため、いったん全体を走査しながらバッファリングしなければなりません。
drop(while:) は非 @escaping なクロージャを取るため、呼び出し時点で条件に合わない要素まで先読みし、1 要素分バッファリングする必要があります。
prefix(while:) も同様に即時評価が必要で、すべての要素を読みながらバッファリングしなければなりません。

ところがプロトコル要件上、これらはすべて同じ SubSequence 型を返さなければなりません。全部を [Element] にそろえることは理論上可能ですが、prefix(_:) のように遅延評価できる場面でもメモリを確保してしまうことになり、無駄が大きくなります。

型消去による `AnySequence` がパフォーマンスとジェネリクスを阻害する

標準ライブラリはこの問題を、Sequence.SubSequence のデフォルト型を AnySequence<Element> にすることで回避していました。内部では DropFirstSequence や PrefixSequence のような専用のラッパー型が作られ、それらを AnySequence に型消去してから返します。

この型消去には、大きな副作用が 2 つあります。

最適化の壁になり、パフォーマンスが大きく劣化する。 型消去ラッパーは最適化を阻害するため、本来はインライン化できる軽い処理が軽くなりません。実際、型消去をやめて具体的な戻り値型にしたプロトタイプでは、-O ビルドで dropFirst / prefix / drop(while:) などが数十倍速くなるという計測結果が出ています（DropWhileSequence で 76 倍、PrefixSequence で 43 倍など）。

Sequence から Collection への conditional conformance を書けなくなる。 これは、Slice（Collection のデフォルト SubSequence）がベース型に応じて能力を伸ばしていけるのに対し、AnySequence はその名のとおりすべての型情報を消してしまうため、追加の能力を持たせようがないためです。

結果として、Sequence としても Collection としても振る舞える型を作ろうとしたとき、理想的には 1 つの型で済むはずのものが 2 つの型に分裂してしまいます。たとえば標準ライブラリの EnumeratedSequence は本来 1 つの Enumerated 型に統合し、ベースが Collection のときだけ Collection に適合する、という書き方にしたいはずです。

struct Enumerated<Base: Sequence> {
  let _base: Base
}

extension Enumerated: Sequence { /* ... */ }

// ベースが Collection のときだけ Collection に適合したい
extension Enumerated: Collection where Base: Collection {
  // ...
}

ところが Collection は「SubSequence もまた Collection であること」を要求するため、Sequence 側の SubSequence が AnySequence のままではこの conditional conformance が成立しません。そのため実際の標準ライブラリでは、EnumeratedSequence と EnumeratedCollection のように 2 つの別々の型を用意し、enumerated() も 2 通り定義するという回避策が取られてきました。これはコードサイズの点でも、ユーザーのコードに別々の型名が漏れ出す点でも望ましくない状況でした。

本来のメリットは「`Collection` を渡したときに高速化される」程度

そもそも Sequence がこれらのメソッドを associated type 付きのプロトコル要件にしている理由は、「Sequence 向けに書かれたジェネリックアルゴリズムに Collection を渡したときに、Collection 側のより高速な実装に差し替わる」というカスタマイゼーションポイントとしての役割を持たせるためでした。たとえば Array を suffix するときに、線形時間・線形メモリで末尾を集めるのではなく、定数時間でスライスを返せる、といった最適化です。

しかし、このメリットは型消去による具体型側のパフォーマンス劣化という大きな代償と引き換えに成り立っています。ジェネリックなケースを少し速くするために、具体型のケースを大きく遅くしているわけで、割に合いません。

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

Sequence から SubSequence という associated type を取り除き、SubSequence は Collection 以降のプロトコルにだけ存在するように整理します。あわせて、Sequence が要件として持っていた dropFirst / dropLast / prefix / suffix / drop(while:) / prefix(while:) / split はプロトコル要件ではなくなり、普通の extension メソッドとして提供されます。それぞれのメソッドは、用途に最も合った具体的な型を返すようになります。

新しいシグネチャ

Sequence 上のこれらのメソッドは、次のように具体型を返す extension として再定義されます。

extension Sequence {
  public func dropFirst(_ k: Int = 1) -> DropFirstSequence<Self>
  public func dropLast(_ k: Int = 1) -> [Element]
  public func suffix(_ maxLength: Int) -> [Element]
  public func prefix(_ maxLength: Int) -> PrefixSequence<Self>
  public func drop(while predicate: (Element) throws -> Bool) rethrows -> DropWhileSequence<Self>
  public func prefix(while predicate: (Element) throws -> Bool) rethrows -> [Element]
  public func split(
    maxSplits: Int = Int.max,
    omittingEmptySubsequences: Bool = true,
    whereSeparator isSeparator: (Element) throws -> Bool
  ) rethrows -> [ArraySlice<Element>]
}

ポイントは次のとおりです。

dropFirst / prefix(_:) / drop(while:) は遅延評価できるので、専用のラッパー型（DropFirstSequence / PrefixSequence / DropWhileSequence）を返します。これらは以前からアンダースコア付きで標準ライブラリ内に存在していたものが、正式な公開 API に格上げされます。
dropLast / suffix / prefix(while:) は結局全要素を読む必要があるので、素直に [Element] を返します。
split はそれぞれの区切りの結果を配列のスライスとして返すのが自然なので、[ArraySlice<Element>] を返します。

SubSequence は Collection 以降の associated type として残り続け、Collection 上の dropFirst などは引き続き SubSequence を返します。ただし、これらのメソッドは Collection でもプロトコル要件（カスタマイゼーションポイント）ではなく、extension としてのみ提供される形に整理されます（SE-0232 で prefix(upTo:) などに対して行われたのと同じ方向性です）。

利用側の書き方

通常の使い方はこれまでと変わりません。Sequence に対して dropFirst や prefix を呼ぶと、型消去された AnySequence ではなく具体的なラッパー型が返ります。

func firstFive<S: Sequence>(of s: S) -> PrefixSequence<S> {
  return s.prefix(5)
}

// 末尾系は全走査が必要なので配列で返る
func lastTwo<S: Sequence>(of s: S) -> [S.Element] {
  return s.suffix(2)
}

戻り値の型が具体的になることで、最適化器が中身まで見通せるようになり、多くのケースで大幅な高速化が得られます（元 proposal の計測では数十倍オーダーの改善例が報告されています）。

標準ライブラリの型の整理

この変更にともなって、これまで Sequence 用と Collection 用に分裂していた型や、2 つに分かれていたプロトコルを整理できるようになります。

LazySequenceProtocol と LazyCollectionProtocol は 1 つのプロトコルに統合されます。
次の型は Sequence 版と Collection 版が 1 つに統合され、Collection 版は typealias でソース互換のために残されます。
- FlattenSequence / FlattenCollection
- LazySequence / LazyCollection
- LazyMapSequence / LazyMapCollection
- LazyFilterSequence / LazyFilterCollection
- LazyDropWhileSequence / LazyDropWhileCollection
- LazyPrefixWhileSequence / LazyPrefixWhileCollection
次の型は、ベースが Collection のときに conditional conformance で Collection にも適合できるようになります。
- EnumeratedSequence
- JoinedSequence
- Zip2Sequence

これにより、「enumerated() を Sequence 用と Collection 用で 2 回定義する」といった重複がなくなり、ライブラリ側もユーザー側もコードが単純になります。

ソース互換性についての注意

この変更はソース互換性を破ります。具体的には、Sequence.SubSequence を明示的に参照していたコードは動かなくなります。たとえば次のような独自 extension は書けなくなります。

extension Sequence {
  func dropTwo() -> SubSequence { // Sequence に SubSequence がなくなる
    return dropFirst(2)
  }
}

このようなコードは、戻り値の型を DropFirstSequence<Self> のような具体型に書き換える必要があります。また、自前で Sequence の SubSequence をカスタマイズしていた型も動かなくなりますが、これは元々 split まで含めて自力で実装しなければならないほぼ不可能な作業であり、実際にはほとんど存在しなかったケースです。

Remove Sequence.SubSequence