Ordered Collection Diffing

標準ライブラリに、コレクション間の差分を表現する CollectionDifference 型と、その生成・適用を行うメソッド群が追加されます（Swift 5.1）。

差分の生成

差分を生成するには BidirectionalCollection の difference(from:) を使います。要素が Equatable であれば引数なしで、そうでない場合は等価判定のクロージャを渡します。

let base = ["a", "b", "c", "d"]
let updated = ["a", "c", "d", "e"]

let diff = updated.difference(from: base)

difference(from:) は、レシーバ側を「変化後の状態」、引数側を「変化前の状態」とみなした差分を返します。計算量は共通要素が多いほど速く、病的な入力でも最悪 O(self.count * other.count) です。要素が Hashable ならさらに高速になります。

返り値の型は次のような構造です。

public struct CollectionDifference<ChangeElement> {
    public enum Change {
        case insert(offset: Int, element: ChangeElement, associatedWith: Int?)
        case remove(offset: Int, element: ChangeElement, associatedWith: Int?)
    }

    public var insertions: [Change] { get }
    public var removals: [Change] { get }

    public func inverse() -> CollectionDifference<ChangeElement>
}

Change は insert と remove の2ケースだけを持ちます。コレクションへの破壊的な操作は本質的にこの2つに集約されるため、差分もこの2ケースで表現されます。offset は、insert では適用後の位置、remove では適用前の位置を指します。

CollectionDifference は自身も Collection に適合しており、要素（Change）を列挙できます。列挙順は「remove を offset の大きい方から小さい方へ」→「insert を offset の小さい方から大きい方へ」と定められていて、この順に素朴に適用するだけで、インデックスのずれを気にせず差分を反映できます。

for change in diff {
    switch change {
    case .remove(offset: let o, element: _, associatedWith: _):
        arr.remove(at: o)
    case .insert(offset: let o, element: let e, associatedWith: _):
        arr.insert(e, at: o)
    }
}

また、inverse() で「逆向きの差分」を、insertions / removals でそれぞれの種類の変更だけを取り出せます。要素が Equatable / Hashable / Codable のときは CollectionDifference 自身もそれらに適合し、差分そのものを比較したり永続化したりできます。

差分の適用

RangeReplaceableCollection の applying(_:) で差分を適用します。

let base = ["a", "b", "c", "d"]
let updated = ["a", "c", "d", "e"]

let diff = updated.difference(from: base)

guard let result = base.applying(diff) else {
    // base と diff が食い違っているときだけ nil になります
    fatalError("incompatible base state")
}
// result == ["a", "c", "d", "e"]

適用が失敗するのは、差分の生成元になった状態と実際のベース状態が食い違っている場合のみで、その場合は nil が返ります。エラー型を投げる設計ではなく、Optional で表現されます。計算量は O(n + c)（n はレシーバの長さ、c は差分に含まれる変更の数）です。

これを組み合わせると、3-way マージのような処理も数行で書けます。

let baseLines = base.components(separatedBy: "\n")
let theirLines = theirs.components(separatedBy: "\n")
let myLines = mine.components(separatedBy: "\n")

let diff = theirLines.difference(from: baseLines)

guard let patchedLines = myLines.applying(diff) else {
    print("Merge conflict applying patch, manual merge required")
    return
}

let patched = patchedLines.joined(separator: "\n")

移動の表現と inferringMoves()

Change に .move のケースはありません。そのかわり associatedWith: を使って、ある remove と insert を対にすることで「移動」や「置換」を表現できる設計になっています。対にする操作は、ChangeElement が Hashable のときに使える inferringMoves() で差分から自動的に行えます。

let diff = updated.difference(from: base).inferringMoves()

inferringMoves() は、差分の中で挿入と削除が1度ずつだけ現れる要素を見つけ、それらを対応する associatedWith: で結び付けた新しい差分を返します。UI でアイテムの移動を挿入・削除とは別にアニメーションしたい場合などに使えます。計算量は O(n) です。

associatedWith: は手で組み立てることもでき、オフセットが同じで要素が異なる対を作れば「置換」、オフセットと要素の両方が異なる対を作れば「移動 + 変更」を表現できます。

// 同じ位置での置換
CollectionDifference<String>([
    .remove(offset: 0, element: "oldvalue", associatedWith: 0),
    .insert(offset: 0, element: "newvalue", associatedWith: 0),
])

Change の直接生成とバリデーション

CollectionDifference には Change のコレクションを受け取る failable イニシャライザもあり、差分を手で組み立てて渡すこともできます。ただし、挿入オフセットの一意性、削除オフセットの一意性、associatedWith: の対称性という3つの条件を満たさない場合は nil が返り、壊れた差分が作られないようになっています。