苹果在WWDC2019的session中公开了iOS13一些新的系统API， 其中对于非常稳定的UITableView和UICollectionView这2个控件，各自新增了一套Diffable DataSource的API。
本文从why, what, how的角度出发，并结合一个优秀的第三方库IGListKit来分析下如何实现一套Diffable DataSource。
我们先来看第一个问题， 为什么需要一个Diffable DataSource？
要回答这个问题，我们先来看业务上一个最常见的场景，例如用户手动刷新了下聊天列表，可能因为各种原因列表数据源发生了一些增删改的变化，此时我们该如何对应地刷新整个列表呢？
一般有两类方法：
-
粗暴方法
[self.tableView reloadData]; -
精巧方法
[self.tableView beginUpdates]; [self.tableView deleteRowsAtIndexPaths:@[indexPath] withRowAnimation:UITableViewRowAnimationAutomatic]; [self.models safeRemoveObjectAtIndex:indexPath.row]; [self.tableView endUpdates];
粗暴的方法最简单，几乎不可能出现数据源不一致导致的异常等情况,但在数据量很大的情况下有一些性能的瓶颈，尤其在低端机型上。
精巧的方法，需要手动去计算数据源的变化，并使用对应的API去更新，如下:
- (void)insertRowsAtIndexPaths:(NSArray<NSIndexPath *> *)indexPaths withRowAnimation:(UITableViewRowAnimation)animation;
- (void)deleteRowsAtIndexPaths:(NSArray<NSIndexPath *> *)indexPaths withRowAnimation:(UITableViewRowAnimation)animation;
- (void)moveRowAtIndexPath:(NSIndexPath *)indexPath toIndexPath:(NSIndexPath *)newIndexPath;
因为是手动diff数据源并调用相关API，如果计算不准确就容易引起NSInternalInconsistencyException。
在苹果出现Diffable data source API之前，就有很多地方库实现了通过Diff数据源来实现既傻瓜又高效的列表刷新方式，比如IGListKit和DeepDiff，我们无法看到苹果Diffable DataSource的源码，但可以通过回顾下第三方库IGList的源码来大概看下，是能如何实现一个基于高效Diff算法的列表刷新的:
首先要实现一个Diffable Datasource，需要数据源能够告诉我们，他们是否"一样"。
在IGListKit中，需要实现IGListDiffable协议
@protocol IGListDiffable
- (nonnull id<NSObject>)diffIdentifier;
- (BOOL)isEqualToDiffableObject:(nullable id<IGListDiffable>)object;
@end
其中第一个接口来标示是否是同一个数据源，而第二个接口来标示它是否自身需要update
在判断数据之间是否”一样“之后，需要一个高效的Diff算法来计算出旧数据源更新到新数据源所需的"最短编辑距离"，并调用相应Api完成列表的更新。
IGListKit diff函数实现的是Paul Heckel的算法，它的时间复杂度为O(M+N)（M和N为新旧数据源的长度）。
IGlistKit diff函数的入参主要是新旧两个数据源数组:
NSArray<id<IGListDiffable>> *oldArray,
NSArray<id<IGListDiffable>> *newArray,
其中新旧数据源中的每一个数据都有一个对应的IGListEntry对象来表示和参与计算：
/// Used to track data stats while diffing.
struct IGListEntry {
/// The number of times the data occurs in the old array
NSInteger oldCounter = 0;
/// The number of times the data occurs in the new array
NSInteger newCounter = 0;
/// The indexes of the data in the old array
stack<NSInteger> oldIndexes;
/// Flag marking if the data has been updated between arrays by checking the isEqual: method
BOOL updated = NO;
};
IGListEntry的结构和作用见上面代码中的注释，还是非常清晰的。
我们再来看整个diff算法的核心流程：
为newArray里的每个数据创建一个IGListEntry，将其newCounter计数+1，并push一个NSNotFound到entry的oldIndexes占位
-
为oldArray里的每个数据创建一个IGlistEntry（如果步骤1已创建的话则是获取），将其oldCounter计数+1, 并push index到oldIndexes中。
这里需要注意的是，oldArray是根据index倒序遍历的，这样是为了对应oldIndexes使用的stack
通过遍历newArray对应的Entry List处理同时在新旧数据里出现的数据，当从oldIndexes pop出第一个元素不为NSNotFound，则代表这个数据在新旧数据源中都存在，并通过标记这个数据是否更新
遍历所有老的数据源，如果他没有出现在新数据源中，则标记为delete，并加入到delete容器中
-
遍历所有新的数据源，
如果他没有出现在老的数据源中，则标记为insert，并加入到insert容器中
否则将其加入到update容器中，并通过比较delete和insert时记录的indexOffset来判断它是一个move还是update
从上面可以看出，这个Diff算法的空间和时间复杂度都是O(M+N)，可以很好处理长列表的case（传统LCS算法的复杂度需要O(N^2)！），且封装了最后patch操作中offset相关的很多计算，杜绝了自己手动进行更新时极容易出的index计算错误导致的NSInternalInconsistencyException，只需要数据层实现IGListDiffable协议，就可以实现傻瓜又高效的列表刷新。
这也符合所有框架设计的哲学:
将复杂易错的逻辑抽取封装在久经考验的代码中，让使用者只需要控制少量不容易犯错的”傻瓜“逻辑即可完成复杂的业务需求开发。
最后用Dart复刻了一遍IGListkit的diff算法 代码在这里可以直接在线玩: diff in dart
参考资料：
A better way to update UICollectionView data in Swift with diff framework
Diff应用：从LCS到UICollectionView
