前言
Angular原生实现了两个工具类:DefaultKeyValueDiffer和DefaultIterableDiffer,它们分别用来检查两个对象或两个数组之间的差别(也就是diff)。典型的使用场景是:检查某个变量在两个时刻之间是否发生了改变、发生了什么样的改变,在这篇文章中,我们称它为变更检测。
请将diff与change detection区分开来。
Angular的变化检测默认只比较对象的引用是否改变,但是我们可以通过DoCheck生命周期钩子来做一些额外的检测,比如检查对象是否增加删除改动了某些属性、检查数组是否增加删除移动了某些条目。这个时候变更检测就可以派上用场了。 举个例子,NgForOf指令内部就是通过DefaultIterableDiffer 来检测输入数组发生了怎样的变化,从而能够用最小的代价去更新DOM。
这两个工具类中包含的算法可以说是十分通用的,甚至可以移植到其他框架、语言去。除此之外,掌握这种变更检测算法也能够帮助我们更好地理解、使用NgForOf ,甚至编写自己的结构型指令。
在我们通过源码了解它们的算法之前,我先简单地介绍一下Differ是如何使用的。
如何在Angular中使用Differ
要使用这两个工具类,并不需要(也不应该)自己创建这两个类的实例,BrowserModule已经将将它们注册在注入器中。
以下代码展示了如何获取和使用DefaultKeyValueDiffer:
import { Component,KeyValueDiffers,KeyValueDiffer } from '@angular/core';
@Component({
selector: 'app-root',templateUrl: './app.component.html'
})
export class AppComponent {
constructor(keyValueDiffers: KeyValueDiffers) {
const someObj: any = { a: 1,b: 2 };
console.log('KeyValueDiffers"',keyValueDiffers);
const defaultKeyValueDifferFactory = keyValueDiffers.find(someObj);
console.log('defaultKeyValueDifferFactory:',defaultKeyValueDifferFactory);
console.log('test defaultKeyValueDifferFactory.supports:',defaultKeyValueDifferFactory.supports({}),defaultKeyValueDifferFactory.supports([]),defaultKeyValueDifferFactory.supports('string')
)
const defaultKeyValueDiffer = defaultKeyValueDifferFactory.create();
console.log('defaultKeyValueDiffer:',defaultKeyValueDiffer);
const changes1 = defaultKeyValueDiffer.diff(someObj);
console.log('changes1:')
changes1.forEachAddedItem((r) => {
console.log(r.key,r.previousValue,r.currentValue);
});
console.log('--------------------')
delete someObj.a;
someObj.c = 'new value';
const changes2 = defaultKeyValueDiffer.diff(someObj);
console.log('changes2:')
changes2.forEachAddedItem((r) => {
console.log(r.key,r.currentValue);
});
changes2.forEachRemovedItem((r) => {
console.log(r.key,r.currentValue);
});
console.log('--------------------')
}
}
DefaultIterableDiffer的使用是完全类似的。你也可以参考api文档。
你可以从这个例子初步体会到“抽象”的威力。使用者调用interface KeyValueDiffer定义的API,而完全不知道(也不需要知道)背后DefaultKeyValueDiffer这个类的存在。
更棒的是,我们等一下可以看到,我们可以自己实现特殊用途的KeyValueDiffer工具类(工具类实现这个接口),然后这个工具类就能被加入到KeyValueDiffers 中,从而能在应用的指定范围内分发,因此这套系统(可以命名为“Differ供应系统”)具有很强的可扩展性。
KeyValueDiffer
先抛开DefaultKeyValueDiffer本身不谈,我们先从源码来看看KeyValueDiffer供应系统是如何实现的。
KeyValueDiffer供应系统
这个系统主要由3个类或接口组成:KeyValueDiffers类,KeyValueDifferFactory接口,KeyValueDiffer接口。
从前面的使用示例可以看出,使用者最开始需要通过依赖注入拿到KeyValueDiffers类的实例:
constructor(keyValueDiffers: KeyValueDiffers)
ApplicationModule已经注册了这个服务的provider,我们的AppModule在引入BrowserModule的时候会得到这个provider。
有意思的是,Angular注册的_keyValueDiffersFactory直接返回同一个KeyValueDiffers实例,因此,这个根KeyValueDiffers是全局唯一的,即使你在同一个页面运行多个Angular程序。效果等同于在Platform Injector注册了这个服务。
好,使用者已经可以获取到KeyValueDiffers实例了,它是干什么的呢?
KeyValueDiffers持有一些KeyValueDifferFactory,并且可以通过find方法返回支持指定对象kv的Differ的工厂(某种Differ只支持某种特定的对象,比如说,我们可以实现一个专门支持Date的Differ)。
KeyValueDiffers的静态方法create可以在创建新实例的时候指定一个"parent",新的实例会获得parent拥有的factories,类似于继承。注意到concat时,自己的factories在前面,parent的factories在后面,而find方法是从前往后查找的,因此find先查找自己拥有的factories,再检查parent的factories。
KeyValueDiffers的静态方法extend,注释已经写得很清楚了,并且源码也很简单,它是生成一个StaticProvider的工具函数。你可以将KeyValueDiffers注册在某个的依赖注入层级上,从而在此层级以下的组件、指令能够通过依赖注入获取它。
在我们通过find方法得到KeyValueDifferFactory以后,可以通过KeyValueDifferFactory.supports 检查KeyValueDiffer是否支持某个对象的变更检测,然后可以通过KeyValueDifferFactory.create 获得新的KeyValueDiffer对象。显然每种KeyValueDiffer必须有一个对应的KeyValueDifferFactory,比如DefaultKeyValueDiffer有自己的DefaultKeyValueDifferFactory。因此我们在实现自己的Differ的时候要实现Factory和Differ来分别implements这两个接口。
假设我们不实现自己的KeyValueDiffer,从KeyValueDiffers获取到DefaultKeyValueDifferFactory以后,直接调用DefaultKeyValueDifferFactory.create() 就可以获得DefaultKeyValueDiffer对象,就像最前面的例子一样。通过KeyValueDiffer.diff(obj) 可以追踪obj与上次调用diff传入的obj相比,发生了哪些改变。至此,"KeyValueDiffer供应系统"的使命就完成了。
这套KeyValueDiffer供应系统有以下优点:
- 扩展性好,你可以自己实现KeyValueDiffer(比如Date的变更检测)。只要分别用class实现KeyValueDifferFactory和KeyValueDiffer接口,然后KeyValueDiffers就可以帮助你分发你的KeyValueDifferFactory。并且,使用者通过统一的API来与Factory和Differ进行交互。
- KeyValueDiffers的继承关系类似于注入器的层级关系,帮助你简化KeyValueDiffers的创建,理清
find 的查找顺序。
- 将KeyValueDiffers注册在某个ngModule providers或者Component providers中(不要覆盖掉ApplicationModule注册的KeyValueDiffers!否则你无法获取到DeafultDiffer)。通过控制KeyValueDiffers的依赖注入有效范围,你可以控制你的KeyValueDiffers的分发范围。
DefaultKeyValueDiffer
让我们从源码研究它。
注意到它同时实现了KeyValueDiffer和KeyValueChanges接口,因此这个类不仅要发现新旧对象之间变更,而且要给用户提供遍历这些变化的API。
既然Differ要检测“变化”,那么它就要存储状态,也就是上次调用diff传入的obj是怎么样的。从类成员可以看出,每个Differ对象要存储obj的所有条目,分别通过Map和链表。用户能够通过forEachItem 遍历当前obj的所有属性。 此外,为了存储有用的信息,还定义了4个链表,分别是_previousMapHead (旧obj的所有属性) _changesHead _additionsHead _removalsHead 。如果用户想要获取这4个信息,可以分别调用forEachPreviousItem (遍历旧obj的所有属性) forEachChangedItem forEachAddedItem forEachRemovedItem 来遍历这些列表。
有这么多的链表,为了节约内存,一个链表条目,有各种不同的链表next指针,可以同时作为多个链表的成员。
剩下的所有函数都是围绕diff 来服务的。可以看到diff基本上相当于直接调用check。check就包含了变更检测算法:
- 调用
reset() 为迁移到下一个状态作准备(包括:更新_previousMapHead 链表,更新每个record的 _nextPrevious 指针和previousValue ,清空_changesHead _additionsHead _removalsHead 链表)
-
遍历新传入的obj 的每个属性,依次与_mapHead 比较(_mapHead 存储的还是旧obj的record)。
- 如果key相同,则比较value,如果value不同,则更新这个record并将它加入
_changesHead 链表。
- 如果key都不相同,那么有可能这个key在链表的后面。因此在
_getOrCreateRecordForKey 方法中,先尝试从_records Map找到这个key,如果找到了就比较其value是否与新obj中的value相同(如果不同的话就_addToChanges ),然后将它暂时从_mapHead链表中删除,_getOrCreateRecordForKey 返回这个record(等一下会插入到链表的正确位置); 如果在Map找不到这个key,说明这是一个新加入的属性,则创建一个新的record并加入_additionsHead 链表,_getOrCreateRecordForKey 返回这个新建的record(等一下再插入到_mapHead 链表中)。_getOrCreateRecordForKey 执行完毕以后,将返回的record插入_mapHead链表的正确位置。
- 新传入的obj的每个属性都遍历过以后,如果
_mapHead 链表中还有尚未访问的record,这些record都是被删除的。将它们从_mapHead 移除、加入_removalsHead 、从_records 中删除这些条目、更新这些record的状态。
实现这个算法时要理清楚什么时候更新_changesHead _additionsHead _removalsHead链表,也就是什么情况意味着发现了change、addition、removal。这在上面的表述中已经说明了。 理清楚了这一点以后,剩下的就是维护链表的操作了。同时维护这么多的链表确实是一件很容易出错的事情。
IterableDiffer
IterableDiffer用来对数组或类数组对象进行变更检测。
IterableDiffer供应系统
IterableDiffer供应系统与KeyValueDiffer供应系统非常类似,这里只讨论几个比较重要的地方:
- IterableChanges.forEachOperation可以让用户知道,这个数组的上次变更中做了哪些操作。也就是说从旧arr经历哪些增加、删除、移动能够变成新arr。注意这些操作不一定是实际发生在旧arr上的,毕竟有不止一种操作能够将旧arr变成新arr。
- IterableDiffer通过trackByFn来确定新arr中的某个项与旧arr中某个项是否相同。而刚才的DefaultKeyValueDiffer是直接通过looseIdentical来判断新旧value是否相同的(大致等同于===判断)。
-
IterableChanges.forEachIdentityChange 可以让用户看到所有trackById相同但Identity变化(相当于a!==b)的那些条目。
DefaultIterableDiffer
那些简单的,或者DefaultKeyValueDiffer 也有的类成员我就不一一介绍了。
与前面类似地,变更检测的逻辑封装在_check函数中。让我们从这里开始。
-
this._reset() 进行初步的状态更新。包括:更新_previousItHead 链表,更新每个record的 _nextPrevious 指针,重置previousIndex ,清空_additionsHead _movesHead _removalsHead _identityChangesHead 链表。
- 判断
Array.isArray(collection) ,由于DefaultIterableDiffer支持一些类数组对象,因此在判断不成功的时候会执行另一种算法来检测变更。我们不妨假设检测正常数组的变更。
-
对于collection (新数组)的每个项,执行以下操作(用下标index 来遍历collection ):
-
this._trackByFn(index,item) 计算当前项的标识值。**如果新旧数组之间的两个项的标识值相等,我们就认为它们是同一个项,不管identity是否一样(即不管a===b是否成立),我们都认为顺序没有变化。
-
比较_itHead 链表(旧数组)的第index 个项(命名为item1)与collection 的第index 个项(命名为item2),它们标识值 是否相同:
- 如果新数组的所有项都遍历完了,
_itHead 链表后面还有没访问到的项,则这些项是被删除的。使用_truncate从链表中删掉它们,并记录它们的删除(_addToRemovals )。_truncate 除此之外还做一些收尾工作:将检测变更时用来查询的_unlinkedRecords Map清空(这些是被删除的项,它们已经被执行_addToRemovals 了),然后将各种链表尾的next赋值为null(我们之前加入链表的时候都没有考虑它是不是链表尾)。
可以看出,算法的重点在于第3步的for循环。for循环刚开始的时候,_itHead 链表还是旧数组的状态。然后经过一轮循环,就修改_itHead 链表,将正确的项移动到_itHead 链表的index位置。因此,这个for循环从左向右逐项更新_itHead 链表,使得它有越来越长的前缀与新数组匹配。
DefaultIterableDiffer.forEachOperation
diff 执行完毕以后,变更的信息就存储在DefaultIterableDiffer 的那些链表中了,用户可以通过IterableChanges.forEachOperation 得到一系列数组操作(增加删除移动),这些操作能将旧数组更新为新数组。注意,这些数组操作是通过计算得到的,不一定是实际发生在旧数组上的操作。
forEachOperation 是如何通过变更信息计算出可能发生的操作序列呢?看源码之前,首先应该思考它的思路是怎么样的,否则这段代码会看得非常费劲。 发生在数组上的变更操作无非三种:增加项、删除项、移动项(两个项的交换可以看作两次移动)。其中,移动项又可以分为向前移动(下标变小)和向后移动(下标变大)。我们之前已经提到过,将某个项向前移动时,它所“经过”的那些项的下标会+1。这种下标+1只是其他移动的副产品,不应该算作真正的向后移动。比如对于变更[a,b,c]=>[c,b] ,我们自然的想法是“c从2移动到0”,而bc下标的增加不应另算作变更。 进一步思考,如果项item的下标增加,其实全都是因为item后面的一些项移动到了item前面(现在仅考虑移动项,不考虑增加项)。也就是说,向后移动都可以替换为其他项的向前移动,我们不再需要考虑向后移动了。 举个例子,[a,c,d]=>[d,a] 的变更操作序列是:d向前移动到0位置,c向前移动到1位置,b向前移动到2位置,a不需要自己移动!
forEachOperation 的计算操作序列算法可以简述如下(先只考虑移动项,不考虑有增加项和删除项的情况): 遍历_itHead 链表(此时diff 已经执行完,_itHead 链表的顺序与新数组相同),对于每一项record ,依次检查其临时下标和目标下标(在源码中分别命名为adjPreviousIndex 和currentIndex )。临时下标的意思是,旧数组刚执行完已计算出的操作所得到的临时状态中,这个项的下标。目标下标的意思是,这个项在最终目标数组中的下标。比如,计算[a,a] 的变更操作序列时,已经计算出“d移动到0,b移动到1”,旧数组执行完这两个操作以后的临时状态为[d,c] ,a的临时下标为2,c的临时下标为3,目标下标始终分别是3和2。
- 如果
adjPreviousIndex===currentIndex ,说明在当前状态中,这个项恰好处于目标位置,不需要移动。
- 如果
adjPreviousIndex>currentIndex ,说明在当前状态中,这个项需要被向前移动,才能到达目标位置。这个if就是判断这个情况的。
- 按照这个算法执行,不可能出现
adjPreviousIndex<currentIndex 的情况。
其实adjPreviousIndex 和currentIndex 分别表示【不忽略增加、删除项情况下的】临时下标和目标下标。通过以下两个减法,能计算出【忽略增加、删除项的情况下的——也就是说假设被增加、删除的项从来都不存在】临时下标和目标下标:
const localMovePreviousIndex = adjPreviousIndex - addRemoveOffset;
const localCurrentIndex = currentIndex ! - addRemoveOffset;
因为addRemoveOffset 变量记录了到目前为止的计算中,已经增加了多少个项(如果删除的项比增加的多,则这个值为负数),所以减掉这个数以后就是(忽略被增加的项的情况下的)临时下标和目标下标。
那么adjPreviousIndex (临时下标)是如何得到的呢?adjPreviousIndex的计算函数需要知道【item在旧数组的下标:previousIndex】、【刚刚讲过的addRemoveOffset】、【item被多少个向前移动的项“经过”:moveOffset】,结果adjPreviousIndex 就是三者之和,它就是“item在【旧数组执行完已知操作以后的临时数组】中的下标”。
既然我们需要知道各个项被多少个向前移动的项“经过”,那么我们应该在向前移动某项的时候就记录它经过了哪些项。比如[a,d]=>[a,d,b] 计算出第一个操作“d移动到1”,d向前移动的时候依次经过c,b,因此它们的moveOffset要+1;接下来计算出第二个操作“c向前移动到2”,经过b,因此b的moveOffset要再次+1。这个for循环就是做这个事情的:
for (let i = 0; i < localMovePreviousIndex; i++) {
const offset = i < moveOffsets.length ? moveOffsets[i] : (moveOffsets[i] = 0);
// 对于每个可能被经过的项(旧数组第i项),计算它在临时数组(仅仅考移动的项,不考虑增加、删除的项)中的下标
const index = offset + i;
// 判断它是不是在临时数组的[localMovePreviousIndex,localCurrentIndex)范围
if (localCurrentIndex <= index && index < localMovePreviousIndex) {
// 如果是,说明这一项是被“经过”的
moveOffsets[i] = offset + 1;
}
}
这个for循环比较难懂,这里解释一下:
- Angular使用
moveOffsets 这个数组来存储各个项的moveOffset 。这个数组以previousIndex(旧数组中的下标)为索引。
- for循环的范围是
(let i = 0; i < localMovePreviousIndex; i++) ,如何理解?我们正在检查临时数组(旧数组执行完已知操作以后的临时状态,忽略增加、删除的项)的第localCurrentIndex 个项,此时我们发现localMovePreviousIndex != localCurrentIndex。因此这个向要从临时数组的localMovePreviousIndex 位置移动到localCurrentIndex 位置。因此临时数组下标范围[localMovePreviousIndex,localCurrentIndex)中的项都需要moveOffset+=1。为了更新moveOffset,我们需要知道这些项在【旧数组】中的下标。可是我们怎么知道这些项在【旧数组】中的下标呢?我们无法从【临时下标】计算出【旧数组下标】。但是我们能够确定的是这些项在旧数组的下标肯定小于localMovePreviousIndex (因为这些项肯定还没有被向前移动,它们只能被那些【向前移动的项】“经过”,下标只可能增加),于是我们就对【旧数组中所有下标小于localMovePreviousIndex 的每个项】计算它们在【临时数组】中的下标(这就是for循环的范围由来),然后判断它在【临时数组】中的下标是否处于范围[localMovePreviousIndex,localCurrentIndex),如果是的话我们就更新moveOffsets[i] 。
总结一下这个算法的思路: 算法接受一个临时数组和一个目标数组(最开始临时数组是旧数组)。这个算法不断从临时数组构造一个新的临时数组,使得新的临时数组有更长的前缀匹配目标数组,直到构造出的临时数组与目标数组完全相同。如何构造新的临时数组呢?将临时数组中的某一项向前移动,移动到正确的位置。比如临时数组是[a,e] ,目标数组是[a,e] ,我们构造出的下一个临时数组是[a,e] (b向前移动到正确的位置),使得新的临时数组有更长的前缀与目标数组匹配(前缀a,b )。 继续重复这个过程,使得新的临时数组有更长的前缀匹配目标数组,直到构造出的临时数组与目标数组完全相同。
在实现的时候,Angular并没有直接存储临时数组,而是通过一个
moveOffsets 数组,表示如何通过移动旧数组的项得到临时数组(这也是为什么moveOffsets是以previousIndex(旧数组中的下标)为索引的)。
刚才对于forEachOperation 的讨论我们经常忽略项的增加和删除。其实增加、删除项对其他项的下标也有影响,道理类似,只不过这次我们只需要用addRemoveOffset 变量记录【到目前为止的计算中,已经增加了多少个项】(如果删除的项比增加的多,则这个值为负数),然后【在通过原下标计算临时下标的时候】加上这个值就好了。
刚才对于forEachOperation 的讨论中,我们也没有说明【在什么情况我们要计算出一个项的增加或删除操作】。所有要被删除的项,在diff 执行完毕后都被放到了_removalsHead 链表中。诚然,我们可以在计算出所有移动操作之前先将删除操作输出,但是Angular似乎觉得这样不够自然。按照我们上面的算法,【旧数组】的每一步操作,逐渐使得【更长的旧数组前缀与新数组匹配】,而先执行所有删除操作会破坏这种【从左往右逐一匹配】的感觉。因此Angular实现的forEachOperation ,对_itHead 从左往右匹配,当匹配到被删除项的时候,再执行删除操作: 在遍历_itHead 链表时,正在匹配的项在目标数组的下标是nextIt.currentIndex,如果nextIt.currentIndex>=【nextRemove的临时下标】(此时这个三元表达式的值是nextRemove),就要输出删除nextRemove的操作(如果我们不删除也不移动nextRemove,此时应该轮到nextRemove被匹配了)。比如[a,e] ,遍历到_itHead (新数组)的c 时,临时数组为[d,c] ,发现nextRemove(在这个例子中是b)在临时数组中的c 之前出现(nextIt.currentIndex>=【nextRemove的临时下标】),因此这一步不匹配c ,而先删除b 。
实例
以Angular的一个单元测试为例:
[0,1,2,3,4,5] =>
[6,7,8]
在diff的过程中,_itHead 和_unlinkedRecords 的变化过程如下(括号中的项是被放入_unlinkedRecords 的,加粗表示这部分_itHead 前缀已经与目标数组相匹配):
0 1 2 3 4 5 () 6 1 2 3 4 5 (0) 6 2 3 4 5 (0 1) 6 2 7 4 5 (0 1 3) 6 2 7 0 5 (1 3 4) 6 2 7 0 4 (1 3 5) 6 2 7 0 4 8 (1 3 5)
因此diff完成以后,DefaultIterableDiffer 内部的链表处于如下状态([] 表示该项下标的变化):
collection: ['6[null->0]','2[2->1]','7[null->2]','0[0->3]','4','8[null->5]'],previous: ['0[0->3]','1[1->null]','3[3->null]','5[5->null]'],additions: ['6[null->0]',moves: ['2[2->1]','0[0->3]'],removals: ['1[1->null]','5[5->null]']
diff完成以后就可以通过forEachOperation 来获取(逻辑上的)更新操作了。forEachOperation 会输出如下更新操作,这些操作能将旧数组更新为当前数组。(() 中表示此次操作造成的临时下标的变化,[] 中表示这一项在就旧组中的下标,也就是item.previousIndex )
'INSERT 6 (VOID -> 0)','MOVE 2 (3 -> 1) [o=2]','INSERT 7 (VOID -> 2)','REMOVE 1 (4 -> VOID) [o=1]','REMOVE 3 (4 -> VOID) [o=3]','REMOVE 5 (5 -> VOID) [o=5]','INSERT 8 (VOID -> 5)'
forEachOperation 的执行过程中,构造出的临时数组如下: 0 1 2 3 4 5 6 0 1 2 3 4 5 // 'INSERT 6 (VOID -> 0)', 6 2 0 1 3 4 5 // 'MOVE 2 (3 -> 1) [o=2]', 6 2 7 0 1 3 4 5 // 'INSERT 7 (VOID -> 2)', 6 2 7 0 1 3 4 5 // 0 不需要移动 6 2 7 0 3 4 5 // 'REMOVE 1 (4 -> VOID) [o=1]', 6 2 7 0 4 5 // 'REMOVE 3 (4 -> VOID) [o=3]', 6 2 7 0 4 5 // 4 不需要移动 6 2 7 0 4 // 'REMOVE 5 (5 -> VOID) [o=5]', 6 2 7 0 4 8 // 'INSERT 8 (VOID -> 5)'
小练习:
[a,e]=>[a,e,f,d] 的diff 过程、forEachOperation 输出是怎么样的?
更多范例可以查看Angular的相关单元测试。
至此,变更算法已经介绍完了,上面的介绍忽略了一些维护链表的细节和边界情况的考虑,有兴趣的读者可以自己阅读一遍源代码。 (编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|