投身烈火
Keep Walking

Picodom中的diff算法补完

上次看 Picodom 代码的时候,patch 函数中有段代码没怎么看懂,所以就没分析,算是挖下了坑。经过这几天的思考,我终于把逻辑想明白了,今儿咱就来把这个坑给填上~(美错儿,我今天又要划水了,来打我呀打我呀打我呀~)

逻辑梳理

上次看到 Picodom 中 的 patch 函数中,逻辑分为三个分支,分别是新增节点(没有oldNode),修改节点(newNode和oldNode标签名一样),替换节点(newNode和oldNode标签名不一样)。其中,新增节点和替换节点的操作比较简单。单修改节点的操作,除了要修改节点本身的属性外,还要对比更新节点的子节点,逻辑比较复杂,直接讲代码的话不太容易看出其中的逻辑,咱们先来梳理一下。

说到子节点变化,一般会分为以下这几种情况:

  1. 增加新节点:有可能在旧列表的最开始,中间或者之后添加
  2. 复用旧节点:还记得之前看的代码中,Picodom 会把节点的 key 属性特殊对待吗?这里就是把 key 作为节点的唯一标识的,只要 key 对上了就认为是能复用,dom节点不用新建,不过位置有可能发生变化
  3. 删除旧节点:删除单个或者多个节点
  4. 把以上这些情况综合起来~

如图,比如像下面这种情况:

01

其实这逻辑说起来感觉还挺简单,但是如何用代码实现呢?我们先说下 Picodom 的处理方法,以上图为例。

遍历新节点列表,新节点列表和旧节点列表里各取一个,作为当前新节点和当前旧节点,对比他们,这俩节点 key 不一样,而且在旧节点列表里也没有找到这个节点,于是在当前旧节点前添加新节点,当前新节点切换到下一节点。

02

当前新节点和当前旧节点 key 不一样,但是在旧节点列表里能找到,就把找到的旧节点插入到当前旧节点前面,当前新节点切换到下一节点。

03

对新节点列表中的 4 和 7 的处理和前面一样,就不再多说了。处理过他们之后,取到的当前新节点和当前旧节点的 key 是一样的。这时把新旧节点都传入 patch 函数,递归处理这两个节点。处理过之后,当前新节点和当前旧节点都切换到下一节点。

04

根据之前的步骤,把 2 也处理了,最后当前新节点是 8 ,当前旧节点是 3 ,8 是新增的,所以插入到 3 前面。

05

最后将未用到的旧节点删除掉,既把 3 删掉,得到最终结果。

实现

ok,让我们来看下 Picodom 是如何用代码来实现上述逻辑的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
// ...
var len = node.children.length
// 新子节点vnode列表的长度
var oldLen = oldNode.children.length
// 旧子节点vnode列表的长度
var reusableChildren = {}
// 可复用节点列表
var oldElements = []
// 旧子节点dom列表
var newKeys = {}
// 这边变量用来标记新子节点列表中复用的节点
for (var i = 0; i < oldLen; i++) {
var oldElement = element.childNodes[i]
oldElements[i] = oldElement
var oldChild = oldNode.children[i]
var oldKey = getKeyFrom(oldChild)
if (null != oldKey) {
reusableChildren[oldKey] = [oldElement, oldChil]
}
}
// 上面这个循环是在遍历旧子节点vnode列表,把有key的挑出来,放到可复用节点列表里
var i = 0
var j = 0
// i是旧子节点vnode列表的索引,j是新子节点vnode列表的索引
while (j < len) {
// 遍历新子节点vnode列表
var oldElement = oldElements[i]
// 取当前旧节点dom
var oldChild = oldNode.children[i]
// 取当前旧节点vnode
var newChild = node.children[j]
// 取当前新节点vnode
var oldKey = getKeyFrom(oldChild)
// 取当前旧节点的key
if (newKeys[oldKey]) {
i++
continue
}
// 上面这个判断是为了跳过已经被使用过的旧子节点
var newKey = getKeyFrom(newChild)
// 取当前新节点的key
var reusableChild = reusableChildren[newKey] || []
// 取当前新节点key对应的可复用节点
if (null == newKey) {
if (null == oldKey) {
patch(element, oldElement, oldChild, newChild)
j++
// 如果新节点和旧节点都没有key则在当前旧节点对应的dom节点前插入新节点
// 然后切换当前新节点
}
i++
// 这里的处理方式让人很难理解,为啥是新节点和旧节点都没有key的时候才插入?
// 我感觉这样处理主要是为了处理文本节点……因为文本节点是肯定没有key的
// 另外如果新节点里出现了一个没有key的节点,
// 那么上面这段逻辑就会一直切换的当前旧节点,
// 直到找到一个同样没有key的旧节点,再用patch对比两个节点,
// 如果一直没有找到没有key的旧节点,最后oldElement和oldChild都是null,
// 相当于在旧节点列表最后添加一个新的节点,
// 此时当前旧节点已经切到旧节点列表最后了,
// 所以后续的所有操作都是往旧节点列表最后添加新的节点
} else {
if (oldKey === newKey) {
patch(element, reusableChild[0], reusableChild[1], newChild)
i++
// 如果新节点和旧节点的key相同,则用patch再去对比这两个节点
} else if (reusableChild[0]) {
element.insertBefore(reusableChild[0], oldElement)
patch(element, reusableChild[0], reusableChild[1], newChild)
// 如果key不相同但是存在可复用节点,则把可复用节点插入到当前旧节点前面
} else {
patch(element, oldElement, null, newChild)
// 如果key不同而且不存在可复用节点,则在当前旧节点前面插入个新节点
}
j++
// 切换当前新节点
newKeys[newKey] = newChild
// 记录已经使用的节点的key,后续可以用来过滤出已经使用的可复用节点
}
}
// 根据key复用旧节点
while (i < oldLen) {
var oldChild = oldNode.children[i]
var oldKey = getKeyFrom(oldChild)
if (null == oldKey) {
removeElement(element, oldElements[i], oldChild)
}
i++
}
// 移除没有key的旧节点
for (var i in reusableChildren) {
var reusableChild = reusableChildren[i]
var reusableNode = reusableChild[1]
if (!newKeys[reusableNode.data.key]) {
removeElement(element, reusableChild[0], reusableNode)
}
}
// 根据新节点的key过滤并移除掉已经使用的可复用节点
// ...

思考

看过代码之后我们会发现,如果出现没有key的节点那么之前那套算法的效率就会变差,因为有可能需要遍历整个旧节点列表之后才能对比,这也就是不难理解为啥之前版本的react会自动生成一个datareact-id了……从这个角度来看,感觉给节点加上唯一key做表示可以提升界面更新的效率,不知道react或者vue里这么搞是不是有效……

06

好的那么由于时间不足,本期的博客就先写到这里,如果不出意外的话,maybe可能也许大概下周五会更新吧,能不能准时更新,就全看米娜桑点赞转发安利留言的热情了~!

白了个白~!