A New Model for Collections and Indices

インデックスを進める責務を インデックス自身からコレクションへ移します。インデックスはもはや単なる「位置を表す値」であり、Comparable を満たすだけでよくなります。進む・戻る・距離を測る、といった操作はすべてコレクション側のメソッドとして提供されます。Swift 3.0 で実装されています。

インデックス移動の新しい API

従来の i.successor() などは、次のようにコレクションのメソッド呼び出しに置き換わります。

// Before (Swift 2)
let j = i.successor()
let k = i.predecessor()
let m = i.advancedBy(5)
let d = i.distanceTo(j)

// After (Swift 3)
let j = c.index(after: i)
let k = c.index(before: i)
let m = c.index(i, offsetBy: 5)
let d = c.distance(from: i, to: j)

具体的には、Collection プロトコルに次のような API が追加されます（抜粋）。

protocol Collection {
  associatedtype Index: Comparable
  associatedtype IndexDistance: SignedInteger = Int
  associatedtype Indices: Collection = DefaultIndices<Self>

  var startIndex: Index { get }
  var endIndex: Index { get }
  var indices: Indices { get }

  func index(after i: Index) -> Index
  func formIndex(after i: inout Index)

  func index(_ i: Index, offsetBy n: IndexDistance) -> Index
  func index(_ i: Index, offsetBy n: IndexDistance, limitedBy limit: Index) -> Index
  func formIndex(_ i: inout Index, offsetBy n: IndexDistance)
  func formIndex(_ i: inout Index, offsetBy n: IndexDistance, limitedBy limit: Index)

  func distance(from start: Index, to end: Index) -> IndexDistance
}

protocol BidirectionalCollection: Collection {
  func index(before i: Index) -> Index
  func formIndex(before i: inout Index)
}

formIndex 系のメソッドは、インデックスを in-place で進めるバージョンです。以前は _successorInPlace のように非公開だったものが、重たいインデックス型（AnyIndex など）を扱うときの性能面の選択肢として公式 API に昇格しました。

c.index(i, offsetBy: n, limitedBy: limit) は、n ステップ進めるか、limit に当たるかの早い方で止まるバリエーションで、境界を越えないようにインデックスを動かしたい場面で便利です。

distance(from:to:) は、BidirectionalCollection でなければ start <= end が事前条件となります。インデックスが Comparable になったおかげで、この事前条件を型レベルで意味付けできるようになりました。

プロトコル階層の組み替え

ForwardIndex / BidirectionalIndex / RandomAccessIndex という「インデックス側の」プロトコルはすべて廃止され、Collection 側に BidirectionalCollection と RandomAccessCollection が導入されました。ランダムアクセス性はコレクション側の責務になったという位置付けです。

                     +--------+
                     |Sequence|
                     +---+----+
                         |
                    +----+-----+
                    |Collection|
                    +----+-----+
                         |
          +--------------+-------------+
          |              |             |
          |     +--------+--------+    |
          |     |MutableCollection|    |
          |     +-----------------+    |
          |                            |
+---------+-------------+    +---------+----------------+
|BidirectionalCollection|    |RangeReplaceableCollection|
+---------+-------------+    +--------------------------+
          |
 +--------+-------------+
 |RandomAccessCollection|
 +----------------------+

具体型は複数のプロトコルを組み合わせて宣言します。

struct Array<Element>
  : RandomAccessCollection,
    MutableCollection,
    RangeReplaceableCollection { ... }

struct UnicodeScalarView: BidirectionalCollection { ... }

RandomAccessCollection は構文上の新しい要求を追加しません。代わりに、c.index(i, offsetBy: n) の計算量を O(1) に締めるといった 性能の保証 を与えます。一方 BidirectionalCollection は index(before:) を要求します。

関連型 Indices と for ... in c.indices

Swift 2 では c.indices は Range<Index> を返していました。新しいモデルではインデックス単独で次へ進めないため、Range<Index> はもはや Collection として振る舞えません。そこで Collection に関連型 Indices が追加され、for index in c.indices { ... } のようなコードが引き続き書けるようになっています。

デフォルト実装として、元のコレクションを保持したまま反復する DefaultIndices<C> / DefaultBidirectionalIndices<C> / DefaultRandomAccessIndices<C> が用意されます。Array のようにインデックスが整数で自己完結しているコレクションは、typealias Indices = CountableRange<Index> を指定して、コレクションへの参照を持たない軽量な型を使います。

ただし、DefaultIndices 系はコレクション自身を保持するため、c.indices を使って反復しながら c を変更すると、copy-on-write によってコピーが発生する可能性があります。反復中に c をミュートしたい場合は、次のように index(after:) で自前に進めるスタイルに切り替えます。

var c = [10, 20, 30, 40, 50]
var i = c.startIndex
while i != c.endIndex {
    c[i] /= 5
    i = c.index(after: i)
}
// c == [2, 4, 6, 8, 10]

範囲型の整理: Range / ClosedRange と Countable 版

Range<T>・ClosedInterval<T>・OpenInterval<T> という Swift 2 の三種の神器は、新しいモデルでは四つの範囲型に再編されます。

• Range<Bound> と ClosedRange<Bound>: Bound: Comparable を要求する一般の範囲。それぞれ半開区間と閉区間です。ClosedRange が独立した型として導入されたおかげで、Int.max のような最大値を含む閉区間をトラップなしで表現できます。
• CountableRange<Bound> と CountableClosedRange<Bound>: Bound: Strideable（かつ Stride: Integer）の場合にのみ使える、RandomAccessCollection に適合したバージョン。for i in 0..<10 のように反復できるのはこちらです。

Countable 付きの二つは、Swift が条件付き適合（conditional conformance）をサポートしたあかつきには Range と ClosedRange に統合できる、という位置づけで追加されています。

共通の API はおおむね次のようなシグネチャです。

public struct Range<Bound: Comparable>: Equatable {
  init(uncheckedBounds: (lower: Bound, upper: Bound))
  func contains(_ value: Bound) -> Bool
  func overlaps(_ other: Self) -> Bool
  var isEmpty: Bool { get }
  var lowerBound: Bound { get }
  var upperBound: Bound { get }
  func clamped(to limits: Self) -> Self
}

いくつか押さえておきたい点があります。

• 一般の範囲は Bound: Comparable しか要求しないので、startIndex / endIndex という呼称を改め、lowerBound / upperBound になりました。汎用の範囲はもはや Collection ではなく、あくまで「二つの境界値を持つ値」です。
• 範囲型同士の変換は、ラベルなしの init として提供されます。たとえば半開区間から閉区間への変換は次のとおりです。

let a: CountableRange<Int> = 1..<10
let b = CountableClosedRange(a)  // 1...9

• ClosedInterval / OpenInterval にあった clamp は、使用箇所で意味順が直感的でなかったため、clamped(to:) に改名されました。self を limits にクランプした結果を返します。

既存コードへの影響

このモデル変更は Collection 全般の前提を書き換えるため、影響範囲は広いものの、多くのコードはそのまま動きます。変更が要らない代表例は次のとおりです。

• Array / ArraySlice / ContiguousArray とそのインデックスを扱うだけのコード。
• インデックスを受け渡しはするが、自分では進めないコード（index(of:)、min()、sort()、prefix(_:)、prefix(upTo:) といった既存アルゴリズムのシグネチャは変わりません）。
• for ... in c.indices { ... } による反復。

一方、変更が必要な代表例 は次のとおりです。

• インデックスを自分で進めているコード。i.successor() / i.predecessor() / i.advancedBy(_:) / i.distanceTo(_:) は、対応するコレクション側のメソッドに書き換える必要があります。

// Before
var i = c.index { $0 % 2 == 0 }
let j = i.successor()
print(c[j])

// After
var i = c.index { $0 % 2 == 0 }   // アルゴリズムの API は不変
let j = c.index(after: i)         // インデックスを進めるのはコレクション側
print(c[j])                       // 添字アクセスはそのまま

機械的な置換ではなく、「どのコレクションから得たインデックスか」を踏まえて書き換える必要があるため、マイグレータによる自動変換は一般には不可能です。

• カスタムコレクションを実装しているコード。プロトコルの要件が変わったため、最低限、インデックス側にあったメソッドをコレクション側のメソッドに移植する必要があります。この移植自体は機械的な作業で、「動かすだけ」ならそれで十分です。ただし、このモデル改修の本来の利点である「インデックスが軽量になる」というメリットを得るには、インデックスの表現を見直して、ストレージへの参照を外せないか検討することになります。