epoxy 源码笔记1：Diffing 算法
最近开始阅读学习 epoxy 的源码，开个新的系列来记录一下学习成功。
本系列文章不对 epoxy 是什么进行讲解，直接讲解其中的部分源码内容。
如果相比较文字，您更喜欢直接阅读代码+注释，那么您可以跳到文章末尾的 总结 一节，该小节包含了一个完整的，带注释讲解的源码。
目录
源码
本文主要讲解 Collection+Diff.swift 文件中的 makeChangeset(from:) 方法，该方法可以快速比较出两个集合之间的区别，同时返回增删改的索引集合。
首先贴一下相关的源码：
// MARK: - Collection
extension Collection where Element: Diffable, Index == Int {
/// Diffs two collections (e.g. `Array`s) of `Diffable` items, returning an `IndexChangeset`
/// representing the minimal set of changes to get from the other collection to this collection.
///
/// - Parameters:
/// - from other: The collection of old data.
public func makeChangeset(from other: Self) -> IndexChangeset {
// Arranging the elements contiguously prior to diffing improves performance by ~40%.
let new = ContiguousArray(self)
let old = ContiguousArray(other)
/// The entries in both this and the other collection, keyed by their `dataID`s.
var entries = [AnyHashable: Entry](minimumCapacity: new.count)
var duplicates = [Entry]()
var newResults = ContiguousArray<NewRecord>()
newResults.reserveCapacity(new.count)
for index in new.indices {
let id = new[index].diffIdentifier
let entry = entries[id, default: Entry()]
if entry.trackNewIndex(index) {
duplicates.append(entry)
}
entries[id] = entry
newResults.append(NewRecord(entry: entry))
}
var oldResults = ContiguousArray<OldRecord>()
oldResults.reserveCapacity(old.count)
for index in old.indices {
let id = old[index].diffIdentifier
let entry = entries[id]
entry?.pushOldIndex(index)
oldResults.append(OldRecord(entry: entry))
}
for newIndex in new.indices {
let entry = newResults[newIndex].entry
if let oldIndex = entry.popOldIndex() {
let newItem = new[newIndex]
let oldItem = other[oldIndex]
if !oldItem.isDiffableItemEqual(to: newItem) {
entry.isUpdated = true
}
newResults[newIndex].correspondingOldIndex = oldIndex
oldResults[oldIndex].correspondingNewIndex = newIndex
}
}
var deletes = [Int]()
var deleteOffsets = [Int]()
deleteOffsets.reserveCapacity(old.count)
var runningDeleteOffset = 0
for index in old.indices {
deleteOffsets.append(runningDeleteOffset)
let record = oldResults[index]
if record.correspondingNewIndex == nil {
deletes.append(index)
runningDeleteOffset += 1
}
}
var inserts = [Int]()
var updates = [(Int, Int)]()
var moves = [(Int, Int)]()
var insertOffsets = [Int]()
insertOffsets.reserveCapacity(new.count)
var runningInsertOffset = 0
for index in new.indices {
insertOffsets.append(runningInsertOffset)
let record = newResults[index]
if let oldArrayIndex = record.correspondingOldIndex {
if record.entry.isUpdated {
updates.append((oldArrayIndex, index))
}
let insertOffset = insertOffsets[index]
let deleteOffset = deleteOffsets[oldArrayIndex]
if (oldArrayIndex - deleteOffset + insertOffset) != index {
moves.append((oldArrayIndex, index))
}
} else {
inserts.append(index)
runningInsertOffset += 1
}
}
EpoxyLogger.shared.assert(
old.count + inserts.count - deletes.count == new.count,
"Failed sanity check for old count with changes matching new count.")
return IndexChangeset(
inserts: inserts,
deletes: deletes,
updates: updates,
moves: moves,
newIndices: oldResults.map { $0.correspondingNewIndex },
duplicates: duplicates.map { $0.newIndices })
}
// MARK: - Entry
/// A bookkeeping refrence type for the diffing algorithm.
private final class Entry {
// MARK: Internal
private(set) var oldIndices = [Int]()
private(set) var newIndices = [Int]()
var isUpdated = false
/// Tracks an index from the new indices, returning `true` if this entry has previously tracked
/// a new index as a means to identify duplicates and `false` otherwise.
func trackNewIndex(_ index: Int) -> Bool {
let previouslyEmpty = newIndices.isEmpty
newIndices.append(index)
// We've encountered a duplicate, return true so we can track it.
if !previouslyEmpty, newIndices.count == 2 {
return true
}
return false
}
func pushOldIndex(_ index: Int) {
oldIndices.append(index)
}
func popOldIndex() -> Int? {
guard currentOldIndex < oldIndices.endIndex else {
return nil
}
defer {
currentOldIndex += 1
}
return oldIndices[currentOldIndex]
}
// MARK: Private
private var currentOldIndex = 0
}
// MARK: - OldRecord
/// A bookkeeping type for pairing up an old element with its new index.
private struct OldRecord {
var entry: Entry?
var correspondingNewIndex: Int? = nil
}
// MARK: - NewRecord
/// A bookkeeping type for pairing up a new element with its old index.
private struct NewRecord {
var entry: Entry
var correspondingOldIndex: Int? = nil
}
makeChangeset(from:) 方法是 Collection<Diffable> 的一个扩展，实际使用时你可以简单的理解为一个 [Diffable]。方法接收一个同类型的集合，返回一个 IndexChangeset 类型的结构体。
返回值暂且忽略，咱们直接来看函数体。
ContiguousArray
let new = ContiguousArray(self)
let old = ContiguousArray(other)
函数体内首先将 self 和 other 转换为 ContiguousArray 类型的数组。从变量名上我们可以得知，self 代表着新的集合，而 other 代表着旧的的集合，也就是被比较的集合。
ContiguousArray 和 Array 类似，区别在于 ContiguousArray 能保证子元素在内存中是连续存储的，也就是说它是一块连续的内存，这就允许 CPU 通过指针进行连续访问，大幅提升性能。而 Array 我们大家都知道，它的内部使用了 “缓冲区”，逻辑上是连续的，但是内存上未必是连续的。
因为在后续的算法中，self 和 other 的大小是固定的，不会发生变化，所以这里将其转换为 ContiguousArray 是更好的选择。
通过源码中的注释我们也能知道，将 self 和 other 转换为 ContiguousArray 类型，可以提升大约 40% 的性能。
后文中，将使用
new代表self，使用old代表other。和这里的变量声明保持同步。
预填充数组
毕竟是一个讲究效率的算法，后文中随处可见 .init(minimumCapacity:) 、 reserveCapacity(_:) 方法，这些方法的作用是一样的：设置数组的长度。
我们都知道 Swift 数组扩容通常是直接 *2。上一节中我们有提到，整个算法中数据源的大小是已知的，那么作为一个讲究效率的算法，我们可以在创建数组的同时就设定好数组的大小，避免在后续操作中触发数组的自动扩容，减少因为扩容而带来的性能损耗。
entries
var entries = [AnyHashable: Entry](minimumCapacity: new.count)
entries 这个字典变量的作用是，将 new 和 old 中，使用相同 id 的元素索引值对应起来。
现在这么讲可能比较抽象，后面结合逻辑一起来谈。
记录新元素
var newResults = ContiguousArray<NewRecord>()
newResults.reserveCapacity(new.count)
for index in new.indices {
let id = new[index].diffIdentifier
let entry = entries[id, default: Entry()]
if entry.trackNewIndex(index) {
duplicates.append(entry)
}
entries[id] = entry
newResults.append(NewRecord(entry: entry))
}
代码首先使用新序列的索引进行遍历，使用对应元素的 id，尝试去 entries 中查找元素。
这里使用了一个小技巧：Dictionay 的
default。当不存在 id 对应的元素时，将返回default对应的内容。这里即是返回一个空的Entry对象。
稍后讲解 Entry 对象和 trackNewIndex(_:) 方法的具体内容，先大致说一下：
Entry对象用来记录 “拥有同一个 id 的两个元素，其在新、旧两个数组中的位置”。trackNewIndex(_:)方法接收索引作为参数，并存储到Entry对象中。同时该方法会返回这个Entry对象是否已经在之前出现过（相当于一个重复检查）。
现在我们就可以知道这个 for 循环大致的含义和作用了：
它遍历新数组，首先根据 id 将数组元素存储到 entries 对象中，其次对该数组做一个 “重复检查”，并记录下重复的次数。
Entry 对象和 trackNewIndex(_:) 方法
Entry 对象是一个结构体，它的完整声明比较长，这里我就不再重复贴了，读者可以翻到最上面 自行查看。
我们先把目光集中在 newIndices 这个属性以及 trackNewIndex(_:) 方法上。
trackNewIndex(_:) 方法的实现为：
/// Tracks an index from the new indices, returning `true` if this entry has previously tracked a new index as a means to identify duplicates and `false` otherwise.
func trackNewIndex(_ index: Int) -> Bool {
let previouslyEmpty = newIndices.isEmpty
newIndices.append(index)
// We've encountered a duplicate, return true so we can track it.
if !previouslyEmpty, newIndices.count == 2 {
return true
}
return false
}
该方法将参数存储到 newIndices 里。这是它的作用之一：记录该 id 在新数组（new）中的位置。
然后判断，如果 newIndices 中的元素等于 2，则意味着出现了重复。这很好理解，newIndices 大于 1 意味着同一个 id 出现了两次。不过截止到发文我也没能理解，为什么是 == 2 而不是 >= 2。结合后文推断，猜测是不希望 duplicates 中出现重复的元素。
记录旧元素
var oldResults = ContiguousArray<OldRecord>()
oldResults.reserveCapacity(old.count)
for index in old.indices {
let id = old[index].diffIdentifier
let entry = entries[id]
entry?.pushOldIndex(index)
oldResults.append(OldRecord(entry: entry))
}
记录旧元素的逻辑比记录新元素的逻辑要简单一些：当我们通过 id，如果在 entries 映射表中查到对应元素时（意味着该 id 存在对应的新元素），则存储该元素在旧数据中的索引值。否则不进行存储（因为 entries 的意思是存储 “新-旧” 的对应关系，不存在新，那么旧就没有意义）。
NewRecord & OldRecord
在遍历新集合和旧集合的循环中，末尾都是创建了一个对应的 XXRecord 对象。这两个类型的声明比较相似，除了存储对应的 Entry 之外，还带有一个 Int? 类型的 correspondingXXXIndex 属性，该属性默认是 nil。
correspondingOldIndex 意味着在新集合中，该元素在旧集合中的位置。
correspondingNewIndex 意味着在旧集合中，该元素在新集合中的位置。
如果是 nil，则意味着该元素在另外的集合中不存在。
这两个属性都在后面的算法中起到了重要的作用。
确定元素变动
for newIndex in new.indices {
let entry = newResults[newIndex].entry
if let oldIndex = entry.popOldIndex() {
let newItem = new[newIndex]
let oldItem = other[oldIndex]
if !oldItem.isDiffableItemEqual(to: newItem) {
entry.isUpdated = true
}
newResults[newIndex].correspondingOldIndex = oldIndex
oldResults[oldIndex].correspondingNewIndex = newIndex
}
}
这个对新集合的遍历，确定了两个集合之间元素的变动。
首先是对新集合的遍历，因为 newResults 可以说就是 new 通过 map 得到的，所以可以使用 newIndex 直接从 newResults 中进行取值，而不用担心是否会越界。
你应该还记得，entry 对象中存储着该 id 对应的元素在新、老集合中对应的索引。如果在新、老集合中不存在，那么对应的索引也就不存在。所以通过 popOldIndex() 方法（通过方法名也能看出它的作用），可以通过 entry 对象判断是否存在旧的元素。
到这一步我们应该能知道：如果 newResults 中的某一个元素的 correspondingOldIndex 是 nil，那么该元素就是新增的。那么反过来，oldResults 中的逻辑也是一样的。
实际上上一节中，关于
correspondingOldIndex和correspondingNewIndex这两个属性的作用，也是我通过这个循环推断出来的。
接着往下看。如果存在旧的元素，那么我们就要比较新旧两个元素是否一致，如果不一致，则通过 entry.isUpdated 记录该元素发生了更新。
最后在 newResults 和 oldResults 中记录该元素在另外一个数组中的位置。
中场休息
到了这里，其实我们可以小结一下，先总结一下 newResults、oldResults 和 entries 三个变量的作用。
entries 的主要就是将新旧两个数组，通过相同的 id 做一个匹配，同时记录相应的索引。匹配到一起之后用来创建 newResults 和 oldResults 对象。该变量主要作用于算法的前半部分，为创建 newResults 和 oldResults 而生，创建完之后它的任务就结束了。
newResults 和 oldResults 这两个变量最主要的作用，按我的理解就是：“通过一个Int 类型的可选值，记录了 entry 的前世今生”。
correspondingXXXIndex 的存在有两个含义：
- 是否为空意味着有前世，或者有今生
- 不只是有，还能拿到对应的位置
感慨一下如果没有 “可选值” 这个概念，则需要借助
Bool+Int两个变量来完成这个工作。或者判断一下nil？
删除、新增与移动
在得到 newResults 和 oldResults 两个对象后，要计算出两个集合之间的差异就比较简单了。
删除
后面的算法首先处理的是删除操作。
var deletes = [Int]()
var deleteOffsets = [Int]()
deleteOffsets.reserveCapacity(old.count)
var runningDeleteOffset = 0
for index in old.indices {
deleteOffsets.append(runningDeleteOffset)
let record = oldResults[index]
if record.correspondingNewIndex == nil {
deletes.append(index)
runningDeleteOffset += 1
}
}
其实上文已经做了解释：如果 correspondingNewIndex 是 nil，则意味着该元素是被删除的元素。所以这次是对 old 进行遍历，而不是遍历 new 。
除了将被删除的元素记录到 deletes 之外，该循环还将 “在这个位置之前，有多少个被删除了多少个元素” 记录到了 deleteOffsets 数组中。
例如 [1, 2, 3, 4, 5, 6, 7] 和 [2, 3, 5, 7] 这两个集合做比较，那么 deleteOffsets 的值就是 [0, 1, 1, 1, 2, 2, 3]。代表着 “5这个元素之前，有两个元素被删除掉了”。
该算法是先将
runningDeleteOffset添加到deleteOffsets里，再做递增操作。所以记录的是 “本元素之前，被删除了多少个元素”。
新增和移动
var inserts = [Int]()
var updates = [(Int, Int)]()
var moves = [(Int, Int)]()
var insertOffsets = [Int]()
insertOffsets.reserveCapacity(new.count)
var runningInsertOffset = 0
for index in new.indices {
insertOffsets.append(runningInsertOffset)
let record = newResults[index]
if let oldArrayIndex = record.correspondingOldIndex {
if record.entry.isUpdated {
updates.append((oldArrayIndex, index))
}
let insertOffset = insertOffsets[index]
let deleteOffset = deleteOffsets[oldArrayIndex]
if (oldArrayIndex - deleteOffset + insertOffset) != index {
moves.append((oldArrayIndex, index))
}
} else {
inserts.append(index)
runningInsertOffset += 1
}
}
首先我们发现遍历的开头，用了 record.correspondingOldIndex 来做判断，意味着 “该元素有没有对应的老元素”。
然后从下往上看 else 的逻辑，和删除的时候一样，这次循环通过 inserts 记录了 “该元素之前，插入了多少个元素”。这里我就不用具体的例子举例了，大家应该可以明白。
那么再回到 if 里的逻辑，首先 isUpdated 是之前已经判断过了的。
那么 (oldArrayIndex - deleteOffset + insertOffset) != index 该怎么理解呢？
首先我们明确每个参数的含义：
index是某个元素在 “新集合” 中的位置。oldArrayIndex是该元素在 “旧集合” 中的位置。deleteOffset意味着该元素之前删除了几个元素。insertOffset意味着该元素之前添加了几个元素。
那么我们就可以理解了：对于旧集合而言，如果去掉被删除的，再加上新增的，如果索引位置不变，那么该元素的位置没有发生移动。
通过具体的例子来看一下：
[1, 2, 3, 4, 5, 6, 7] 和 [2, 3, 7, 5]。我们遍历的是后者，即新集合。deleteOffsets 是 [0, 1, 1, 1, 2, 2, 3]。
假设此时我们遍历到了新集合中的 3。
那么 index 是 1，oldArrayIndex 是 2，deleteOffset 是 1，insertOffset 是 0。表达式为 2 - 1 - 0 == 1，不符合条件（注意代码中用的是 != 号），那么则不会添加到 moves 里，意味着 3 这个元素没有被移动。
再假设此时我们遍历到了新集合中的 7。
那么 index 是 2，oldArrayIndex 是 6，deleteOffset 是 3，insertOffset 是 0。表达式为 6 - 3 - 0 != 2，符合条件，所以判断 7 发生了移动。
最后遍历到 5 的时候，
index 是 3，oldArrayIndex 是 4，deleteOffset 是 2，insertOffset 是 0。表达式为 4 - 2 - 0 != 3，符合条件，所以判5 也是发生了移动。
这样，我们就可以筛选出哪些元素发生了移动。
总结
epoxy 的 Diffing 算法大体可以分为一下几个部分：
- 将输入转换为
ContiguousArray类型，提升效率。 - 使用哈希表，将同一个
id的元素从新旧两个集合中摘出来，做匹配，同时记录原本的位置。 - 利用这个哈希表，配合 LCS 算法，找出哪些元素被删除，哪些元素是新增的。
- 根据需求，进一步将第三步的结果进行处理。
最后贴上一下我自己对源代码做的注释：
/// 对两个 `Diffable` 元素集合（例如 `Array`）进行差异化处理，返回一个 `IndexChangeset`，表示从 `other` 到此集合的最小更改集合。
///
/// - Parameters:
/// - from other: 旧数据集合。
public func makeChangeset(from other: Self) -> IndexChangeset {
// 在进行差异化处理之前将元素连续排列可以提高大约40%的性能。
let new = ContiguousArray(self)
let old = ContiguousArray(other)
// 通过 `dataID`，将 `self` 和 `other` 的对应元素存储到 `entries` 里。
var entries = [AnyHashable: Entry](minimumCapacity: new.count)
var duplicates = [Entry]()
// 用来记录新元素（`self`）和旧索引的一个对应关系
var newResults = ContiguousArray<NewRecord>()
newResults.reserveCapacity(new.count)
//
for index in new.indices {
// `new` 其实就是 `self`，从 `self` 里拿标识符
let id = new[index].diffIdentifier
let entry = entries[id, default: Entry()]
// 1. 记录这个新元素的位置
// 2. 判断当前数组的重复性，因为是数组，所以内部数据有可能会有重复的情况。
if entry.trackNewIndex(index) {
duplicates.append(entry)
}
entries[id] = entry
// `correspondingOldIndex` 默认是 `nil`
newResults.append(NewRecord(entry: entry))
}
// 用来记录旧元素（`other`）和新索引的一个对应关系
var oldResults = ContiguousArray<OldRecord>()
oldResults.reserveCapacity(old.count)
for index in old.indices {
// 从 `other` 里拿标识符
let id = old[index].diffIdentifier
// 用 `other` 的 `id`，去 `self` 里找对应的值
let entry = entries[id]
// 如果找到的话，就将旧的索引存储到 `entry` 里。
// `entry` 里既存储了新（`self`）的索引，又存储了旧（`other`）的索引。
// 因为 `id` 是一样的，所以就通过 `id` 把新旧两个元素的索引对应起来了。
entry?.pushOldIndex(index)
// `correspondingNewIndex` 默认是 `nil`
oldResults.append(OldRecord(entry: entry))
}
for newIndex in new.indices {
// `newResults` 是通过遍历 new 得到的
// 所以 `index` 是一致的，可以直接用 `new` 的 `index` 拿到 `newResults` 的元素
let entry = newResults[newIndex].entry
// 如果存在新元素对应的老元素的话，可能对应更新操作
if let oldIndex = entry.popOldIndex() {
let newItem = new[newIndex]
let oldItem = other[oldIndex]
// 如果两个对象不相等，则是更新操作
if !oldItem.isDiffableItemEqual(to: newItem) {
entry.isUpdated = true
}
// 记录两个元素相对的位置
// 可能从 `old` 更新到 `new`，所以索引是有需要的
newResults[newIndex].correspondingOldIndex = oldIndex
oldResults[oldIndex].correspondingNewIndex = newIndex
}
}
// 删除操作
var deletes = [Int]()
var deleteOffsets = [Int]()
deleteOffsets.reserveCapacity(old.count)
var runningDeleteOffset = 0
for index in old.indices {
deleteOffsets.append(runningDeleteOffset)
let record = oldResults[index]
// 这里等于 `nil`，意味着在上一个循环中，没有匹配到对应的 `new` 元素
// 所以意味着在 `new` 数组中，没有该元素存在，所以该元素被删除了
if record.correspondingNewIndex == nil {
deletes.append(index)
runningDeleteOffset += 1
}
}
var inserts = [Int]()
var updates = [(Int, Int)]()
var moves = [(Int, Int)]()
var insertOffsets = [Int]()
insertOffsets.reserveCapacity(new.count)
var runningInsertOffset = 0
for index in new.indices {
insertOffsets.append(runningInsertOffset)
let record = newResults[index]
// 有新，有老
if let oldArrayIndex = record.correspondingOldIndex {
if record.entry.isUpdated {
// 更新，记录元素的对应关系
updates.append((oldArrayIndex, index))
}
// `insertOffsets` 和 `deleteOffsets` 里的值，类似于 `[0, 0, 1, 1, 1]` 这种形式
// 其长度分别等于 `new` 和 `old`，所以直接使用对应的 `index` 取值不会导致溢出
let insertOffset = insertOffsets[index]
let deleteOffset = deleteOffsets[oldArrayIndex]
// 旧位置 - 删除了的元素个数 + 新增了的元素个数 != 新位置 -> 移动了
if (oldArrayIndex - deleteOffset + insertOffset) != index {
moves.append((oldArrayIndex, index))
}
}
// 有新，没老
else {
// 意味着新的元素相对于老的元素来说是插入进来的
inserts.append(index)
runningInsertOffset += 1
}
}
EpoxyLogger.shared.assert(
old.count + inserts.count - deletes.count == new.count,
"Failed sanity check for old count with changes matching new count.")
return IndexChangeset(
inserts: inserts,
deletes: deletes,
updates: updates,
moves: moves,
newIndices: oldResults.map { $0.correspondingNewIndex },
duplicates: duplicates.map { $0.newIndices })
}
后记
文章算是写完了，但是感慨自己虽然花了很多时间，算是 “弄明白” 了本算法，但是也仅限于看懂，然后感慨它的精妙。甚至不敢肯定以后遇到相似的需求时，能用上该算法。哎，希望今后还能有所长进。