Vue 源码学习之 diff 算法

前言

之所以写这篇文章,一个是因为最近看了 vue 的相关源码,也看了不少大佬们对 diff 算法的分析,本着学习的态度,总结一下自己对 diff 算法的一些理解,不求能比大佬们讲的出色,只希望能讲清楚自己学习 diff 算法的心路历程,还有一个比较重要的原因是之前在群里看到有人问为什么 v-for 遍历的时候需要指定 key,众说纷纭,甚至还有人说是因为不指定会报错,一脸懵逼。。。

virtual dom

在分析 vue diff 实现之前,我们还需要理解什么是 virtual dom,只有理解了什么是 virtual dom,才能更好的理解 diff。
那么什么是 virtual dom 呢?在我看来,virtual dom 就是一棵以 JS 对象(VNode 节点)作为基础的树,用对象属性来描述节点,最终可以通过一系列的操作将这颗树反映到真实的环境上。

diff

理解了 virtual dom,我们再来看 diff 算法,所谓的 diff 算法,就是我们先根据真实的 dom 结构生成一颗 virtual dom,当 virtual dom 某个节点的数据改变后会生成一个新的 Vnode,然后将 Vnode 和 oldVnode 作对比,发现有不一样的地方就直接修改在真实的 dom 上,然后使 oldVnode 的值为 Vnode。而 vue 中 diff 的过程就是调用名为 patch 的函数,比较新旧节点,一边比较一边给真实的 dom 打补丁。

传统 diff 算法

比较两棵树的差异,在传统的算法中,我们会去循环遍历一颗树的每个节点,与另一棵树的每个节点去对比,这其中的时间复杂度为 O(n^2),寻找到差异后,还需要计算最小的转换方式,最终时间复杂度为 O(n^3)。

Vue diff 策略

Vue 2.0 引入了 virtual dom,并且和 React 采取了类似的 diff 策略,通过逐级的去比较两颗节点树的差异,这大大降低了复杂性,而且精准度上损失也不大,因为在Web应用程序中将组件树不同级的移动比较是非常罕见的,该算法最终的时间复杂度为 O(n)。

在这里插入图片描述

源码分析(代码只保留核心部分)

vue 中这一块的代码都放在 patch.js 下,算法基于 Snabbdom

patch

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
function patch (oldVnode, vnode, hydrating, removeOnly) {
// somecode
const isRealElement = isDef(oldVnode.nodeType)
if (!isRealElement && sameVnode(oldVnode, vnode)) {
// patch existing root node
patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
} else {
// somecode
// replacing existing element
const oldElm = oldVnode.elm
const parentElm = nodeOps.parentNode(oldElm)

// create new node
createElm(
vnode,
insertedVnodeQueue,
// extremely rare edge case: do not insert if old element is in a
// leaving transition. Only happens when combining transition +
// keep-alive + HOCs. (#4590)
oldElm._leaveCb ? null : parentElm,
nodeOps.nextSibling(oldElm)
)

// update parent placeholder node element, recursively
if (isDef(vnode.parent)) {
let ancestor = vnode.parent
const patchable = isPatchable(vnode)
while (ancestor) {
for (let i = 0; i < cbs.destroy.length; ++i) {
cbs.destroy[i](ancestor)
}
ancestor.elm = vnode.elm
if (patchable) {
for (let i = 0; i < cbs.create.length; ++i) {
cbs.create[i](emptyNode, ancestor)
}
// #6513
// invoke insert hooks that may have been merged by create hooks.
// e.g. for directives that uses the "inserted" hook.
const insert = ancestor.data.hook.insert
if (insert.merged) {
// start at index 1 to avoid re-invoking component mounted hook
for (let i = 1; i < insert.fns.length; i++) {
insert.fns[i]()
}
}
} else {
registerRef(ancestor)
}
ancestor = ancestor.parent
}
}

// destroy old node
if (isDef(parentElm)) {
removeVnodes([oldVnode], 0, 0)
} else if (isDef(oldVnode.tag)) {
invokeDestroyHook(oldVnode)
}
}
}

patch 函数中 oldVnode,vnode 分别代表旧的节点和新的节点,首先判断这两个节点是否是同一节点,如果不是同一节点,直接在父节点中,用 vnode 生成新的 dom 结构,并替换掉 oldVnode。如果是同一节点,则会去执行 patchVnode。下面就是判断是否为同一节点的方法:sameVnode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function sameVnode (a, b) {
return (
a.key === b.key && (
(
a.tag === b.tag &&
a.isComment === b.isComment &&
isDef(a.data) === isDef(b.data) &&
sameInputType(a, b)
) || (
isTrue(a.isAsyncPlaceholder) &&
a.asyncFactory === b.asyncFactory &&
isUndef(b.asyncFactory.error)
)
)
)
}

function sameInputType (a, b) {
if (a.tag !== 'input') return true
let i
const typeA = isDef(i = a.data) && isDef(i = i.attrs) && i.type
const typeB = isDef(i = b.data) && isDef(i = i.attrs) && i.type
return typeA === typeB || isTextInputType(typeA) && isTextInputType(typeB)
}

patchVnode

当两个节点被认定为同一节点时,会调用 patchVnode 函数。

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
function patchVnode (
oldVnode,
vnode,
insertedVnodeQueue,
ownerArray,
index,
removeOnly
) {
if (oldVnode === vnode) {
return
}

// somecode

const oldCh = oldVnode.children
const ch = vnode.children
if (isDef(data) && isPatchable(vnode)) {
for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
}
if (isUndef(vnode.text)) {
if (isDef(oldCh) && isDef(ch)) {
if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
} else if (isDef(ch)) {
if (process.env.NODE_ENV !== 'production') {
checkDuplicateKeys(ch)
}
if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
} else if (isDef(oldCh)) {
removeVnodes(oldCh, 0, oldCh.length - 1)
} else if (isDef(oldVnode.text)) {
nodeOps.setTextContent(elm, '')
}
} else if (oldVnode.text !== vnode.text) {
nodeOps.setTextContent(elm, vnode.text)
}
if (isDef(data)) {
if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
}
}

从以上代码中,不难看出,两个节点比较时有这么几种情况

  1. 两个节点引用相同,直接跳过此次比较
  2. 两个节点中 text 字段值不一样(包括 vnode 中没有 text 字段的值,而 oldVnode 中有),会用 vnode 的 text 替换 oldVnode 的,nodeOps.setTextContent(elm, vnode.text)
  3. 两个节点都有 children 时,会调用 updateChildren 函数,这也是 diff 算法的核心。
  4. oldVnode 节点有 children,而 vnode 没有,会移除 oldVnode 中所有的子节点
  5. vnode 节点中有 children,而 oldVnode 没有,会在老的 dom 节点上添加所有的子节点

updateChildren

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
function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
let oldStartIdx = 0
let newStartIdx = 0
let oldEndIdx = oldCh.length - 1
let oldStartVnode = oldCh[0]
let oldEndVnode = oldCh[oldEndIdx]
let newEndIdx = newCh.length - 1
let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]
let oldKeyToIdx, idxInOld, vnodeToMove, refElm

// removeOnly is a special flag used only by <transition-group>
// to ensure removed elements stay in correct relative positions
// during leaving transitions
const canMove = !removeOnly

if (process.env.NODE_ENV !== 'production') {
checkDuplicateKeys(newCh)
}

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
} else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx]
} else if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else {
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) { // New element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
} else {
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldCh[idxInOld] = undefined
canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
} else {
// same key but different element. treat as new element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
}
}
newStartVnode = newCh[++newStartIdx]
}
}
if (oldStartIdx > oldEndIdx) {
refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
} else if (newStartIdx > newEndIdx) {
removeVnodes(oldCh, oldStartIdx, oldEndIdx)
}
}

代码乍一看,让人头有点大,这里盗用大佬的一张图,以便我们更好的理解这个过程。

在这里插入图片描述

看图,再看代码,这个函数主要做了这么件事

  1. 分别用两个指针(startIndex, endIndex)表示 oldCh 和 newCh 的头尾节点
  2. 对指针所对应的节点做一个两两比较,判断是否属于同一节点
  3. 如果4种比较都没有匹配,那么判断是否有 key,有 key,就会用 key 去做一个比较
  4. 比较的过程中,指针往中间靠,当有一个 startIndex > endIndex,则表示有一个已经遍历完了,比较结束

两两比较的过程如下:

  1. oldStartVnode => newStartVnode,调用 patchVnode 函数,并且指针都后移一位
  2. oldEndVnode => newEndVnode,调用 patchVnode 函数,并且指针都前移一位
  3. oldStartVnode => newEndVnode,说明 oldStartVnode 出现在了 oldEndVnode 后边,调用 patchVnode 函数,并且将 oldStartVnode 移动到 oldEndVnode 节点后面,oldCh 的 startIndex 指针后移一位,newCh 的 endIndex 指针前移一位
  4. oldEndVnode => newStartVnode, 说明 oldEndVnode 出现在了 oldStartVnode 前边,调用 patchVnode 函数,并且将 oldEndVnode 移动到 oldStartVnode 节点前面,oldCh 的 endIndex 指针前移一位,newCh 的 startIndex 指针后移一位

举个?

这里直接用大佬的例子来描述整个 diff 的过程,温馨提示,如果看图不太明确的,可以拿起笔,自己在纸上画一下整个 diff 的过程更能加深印象哟~

  1. a,b,c,d,e假设是4个不同的元素,我们没有设置key时,b没有复用,而是直接创建新的,删除旧的

在这里插入图片描述

  1. 当我们给4个元素加上唯一key时,b得到了的复用。

在这里插入图片描述

总结

以上就是 diff 算法的全过程,总结一下就是这几个点:

  1. 尽量不要跨层级的修改dom
  2. 设置key可以最大化的利用节点
  3. diff的效率并不是每种情况下都是最优的

写在最后

本文旨在帮助大家了解 diff 全过程,对该过程了如指掌的大佬请自动忽略,另,文中大量借鉴了网上大佬们的言论和图,想看大佬原文的请移步以下一些文章。

  1. 解析vue2.0的diff算法
  2. 详解vue的diff算法
  3. VirtualDOM与diff(Vue实现)
  4. 理解 Virtual DOM
  5. React’s diff algorithm
查看评论