Vue.js源码学习 —— diff算法

如果您是刚开始准备阅读Vue.js的源码,建议先看一下本系列的Vue.js源码学习 —— 起步,相信会对您后面的阅读有很大帮助。

本篇文章是接着上一篇文章Vue.js源码学习 —— patch的。上一篇文章分析了patch函数和createElm函数的执行过程,今天将继续分析patchVnode函数和updateChildren函数的实现,也是diff算法的核心内容。

今天这篇文章要看的代码主要位于文件core/vdom/patch.js中。

我没有在文章中大量的贴源码,一定要将源码clone到本地哦。

预备知识

在一些面经中总会遇到这样一个问题:Vue 或 React 是怎样使得在patch的过程中diff的时间复杂度从O(n^3)优化到O(n)的呢?

React在其官方文档中对diff算法有详细地说明,建议看一下。因为 Vue 的做法和 React 差不多,先看这个文档的说明,再来看代码理解起来会轻松一些。在文档中有这样一段说明:

这个算法问题有一些通用的解决方案,即生成将一棵树转换成另一棵树的最小操作数。 然而,即使在最前沿的算法中,该算法的复杂程度为 O(n^3),其中 n 是树中元素的数量。

如果在 React 中使用了该算法,那么展示 1000 个元素所需要执行的计算量将在十亿的量级范围。这个开销实在是太过高昂。于是 React 在以下两个假设的基础之上提出了一套 O(n) 的启发式算法:

  1. 两个不同类型的元素会产生出不同的树;
  2. 开发者可以通过 key prop 来暗示哪些子元素在不同的渲染下能保持稳定;

在上一篇文章中分析patch函数的执行流程时,已经可以看到 Vue 对第1点的实现,如果是两个不同类型的节点,会调用createElm函数创建新的DOM元素,再调用removeVnodes函数将旧的节点移除掉。

今天再来看一下两个节点的类型相同时Vue会如何来处理。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
function patchVnode (
oldVnode,
vnode,
insertedVnodeQueue,
ownerArray,
index,
removeOnly
) {
if (oldVnode === vnode) {
return
}

// ...

const elm = vnode.elm = oldVnode.elm

//...

// reuse element for static trees.
// note we only do this if the vnode is cloned -
// if the new node is not cloned it means the render functions have been
// reset by the hot-reload-api and we need to do a proper re-render.
if (isTrue(vnode.isStatic) &&
isTrue(oldVnode.isStatic) &&
vnode.key === oldVnode.key &&
(isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
) {
vnode.componentInstance = oldVnode.componentInstance
return
}

// ...prepatch钩子

const oldCh = oldVnode.children
const ch = vnode.children

// ...update钩子

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)
}

// ... postpatch钩子
}

对于 这种数据结构一般都是用递归来遍历整个树,patchVnode函数也是递归来遍历的,因为在updateChildren函数中又会再调用patchVnode函数。

patchVnode函数中接收的两个参数oldVnodevnode是两个相同类型的节点,处理时会先更新vnode,再更新vnode的子节点,流程如下:

  • 如果oldVnodevnode都指向了相同的节点,那两个节点完全相同的,直接返回。

  • 更新vnode.elm,直接复用oldVnode.elm,不会再重新创建DOM元素。

  • 如果是只渲染一次的元素或组件,直接复用原来组件的实例然后退出函数,不会再创建一次组件的实例。这里其实是对v-once的实现。在Vue官方文档中对v-once的描述如下;

    只渲染元素和组件一次。随后的重新渲染,元素/组件及其所有的子节点将被视为静态内容并跳过。这可以用于优化更新性能。

  • 触发prepatch钩子函数,直接复用原来的组件实例,只去更新propslisteners等。内部的prepatch函数的实现如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    const componentVNodeHooks = {
    prepatch (oldVnode: MountedComponentVNode, vnode: MountedComponentVNode) {
    const options = vnode.componentOptions
    const child = vnode.componentInstance = oldVnode.componentInstance
    updateChildComponent(
    child,
    options.propsData, // updated props
    options.listeners, // updated listeners
    vnode, // new parent vnode
    options.children // new children
    )
    }
    }
  • 触发update钩子,更新DOM元素的属性,还会更新refsdirectives,下面这些函数都会被执行:

    1
    2
    3
    4
    5
    6
    7
    ƒ updateAttrs(oldVnode, vnode),
    ƒ updateClass(oldVnode, vnode),
    ƒ updateDOMListeners(oldVnode, vnode),
    ƒ updateDOMProps(oldVnode, vnode),
    ƒ updateStyle(oldVnode, vnode),
    ƒ update(oldVnode, vnode), // refs
    ƒ updateDirectives(oldVnode, vnode)
  • 如果vnode.text有值,并且跟oldVnode.text不同,会去更新元素的textContent属性为vnode.text

  • 如果vnode.text没有值,这时要看两个节点的子节点了:

    • 如果两个节点都有子节点,调用updateChildren函数更新子节点。

    • 如果只有vnode有子节点,先将原来元素的textContent置为空,然后创建新的子元素添加到DOM中。

    • 如果只有oldVnode有子节点,那就将它的所有子元素从DOM中移除掉。

    • 如果两个节点都没有子节点,将原来元素的textContent置为空。

  • 触发postpatch钩子,通知当前节点patch完成。

可以看出patchVnode函数中对相同类型元素的处理与 React 的文档中描述的基本是一致的。

updateChildren

抽出了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
function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
let oldStartIdx = 0
let newStartIdx = 0

let oldEndIdx = oldCh.length - 1
let newEndIdx = newCh.length - 1

let oldStartVnode = oldCh[0]
let oldEndVnode = oldCh[oldEndIdx]

let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]

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.elm 没有移动
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) {
// 更新节点
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
// oldEndVnode.elm 没有移动
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
// oldStartVnode.elm 向右移动了
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)
// oldEndVnode.elm 向左移动了
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else {
// ...特殊情况的处理
}
}

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)
}
}

updateChildren函数中设置了4个指针oldStartIdxnewStartIdxoldEndIdxnewEndIdx分别从数组oldChnewCh的两端开始向中间扫描,在循环过程中会进行如下处理:

  • oldStartVnode没有值,oldStartIdx指针向右移。

  • oldEndVnode没有值,oldEndIdx指针向左移。

  • oldStartVnodenewStartVnode是相同类型的元素,调用patchVnode更新节点,将oldStartIdxnewStartIdx指针同时向右移。

  • oldEndVnodenewEndVnode是相同类型的元素,调用patchVnode更新节点,将oldEndIdxnewEndIdx指针同时向左移。

  • oldStartVnodenewEndVnode是相同类型的元素,调用patchVnode更新节点,在DOM中将oldStartVnode.elm移动到oldEndVnode.elm的后面,最后将oldStartIdx指针向右移,将newEndIdx指针向左移。

  • oldEndVnodenewStartVnode是相同类型的元素,调用patchVnode更新节点,在DOM中将oldEndVnode.elm移动到oldStartVnode.elm的前面,最后将oldEndIdx指针左移,将newStartIdx指针右移。

在循环结束后的处理如下:

  • 先判断如果oldStartIdx超过了oldEndIdx说明增加了元素,调用addVnodes函数在DOM中添加新元素。

    这其中隐含了一种情况就是此时newStartIdx也大于newEndIdx,但因为在addVnodes函数中做了判断,所以此时什么也不会执行。这时其实就是oldChnewCh中的元素个数相同的时候。

  • 上一条不成立,再判断如果newStartIdx超过了newEndIdx说明删除了元素,调用removeVnodes函数移除从DOM中移除元素。

以上的处理流程就覆盖了oldChnewCh对比会发生的所有改动:

  • 移动了元素
  • 增加了元素
  • 删除了元素

我们还额外注意到了两点:

1. 在有节点类型相同时,就会又调用patchVnode更新节点。
2. 在移动时,移动的只是虚拟节点关联的真实的DOM元素,而虚拟节点本身并没有被移动。

下面咱们画图举例子直观地看一下循环执行的过程。

假如现在有 A、B、C 三个节点,A、B、C 分别是每个节点的key,改动之后节点列表的顺序变成了 B、A、C 。


这次移动了元素,A、B 节点对应的DOM元素发生了交换,但是 A、B节点本身的位置没变,所以oldCh中的还是 A、B、C。


循环结束了,因为oldStartIdx超过了oldEndIdxnewStartIdx超过了newEndIdx,所以循环结束后不会执行其他操作。

假设现在有 A、B、C 三个节点,A、B、C 分别是每个节点的key,改动之后节点列表的顺序变成了 A、B、D、C 。




最后oldStartIdx超过了oldEndIdx,调用addVnodes函数将D节点关联的元素添加到DOM中。

上面画图举了单纯移动元素和增加元素的情况,你也可以自己画图看一下删除元素的循环过程。我将单纯移动元素的情况用代码实现了一下,你也可以把它放在浏览器中打断点调试一下。代码如下:

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
let child = {
name: 'child',
props: {
items: {
type: Array,
default () { return [] }
}
},
render (h) {
return h('ul', this.items.map(item => {
return h('li', { key: item.id }, `${item.id} : ${ item.name } is a ${ item.type }`)
}))
}
}

new Vue({
el: '#app',
data: {
items: [
{ name: 'alma', type: 'cat', id: 'A' },
{ name: 'ring', type: 'cat', id: 'B' },
{ name: 'winston', type: 'dog', id: 'C' }
]
},
render (h) {
let children = [
h(child, { props: { items: this.items } }), // child 组件
h('button', {
on: {
click: () => {
// 移动了元素
this.items = [
{ name: 'ring', type: 'cat', id: 'B' },
{ name: 'alma', type: 'cat', id: 'A' },
{ name: 'winston', type: 'dog', id: 'C' }
]
}
}
}, 'Click Me')
]

return h('p', children)
}
})

时间复杂度

现在我们把相同类型的两个节点的更新情况也分析完了,再结合上一篇中讲到的不同类型节点的处理,可以发现,diff算法只会在同层级进行比较,这样更新一个VNode树,树中的每个节点最多只会被访问一次,所以现在diff的时间复杂度是O(n)

列表中的节点为什么需要key

再来复习一下sameVnode函数的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)
)
)
)
}

一般情况如果没有提供key,两个tag相同的节点就会认为是相同类型的节点了。为什么把更新组件树的过程称为 打补丁 呢?因为在相同类型的元素之间切换时,会修补已存在的元素,而不是将旧的元素移除然后在同一位置添加一个元素。如果没有提供key,就有可能导致本来不同的元素别识别为相同,会增加DOM操作的次数,降低性能。

下面举例来看一下,没有key时是如何增加DOM操作次数的:

1
2
3
4
5
6
7
8
9
10
11
12
<!--旧的节点-->
<ul>
<li>A : alma is a cat</li>
<li>B : ring is a cat</li>
<li>C : winston is a dog</li>
</ul>
<!--新的节点-->
<ul>
<li>C : winston is a dog</li>
<li>A : alma is a cat</li>
<li>B : ring is a cat</li>
</ul>

下面的li节点都会被认为是相同类型的节点,这样每趟循环都会走进下面这段代码,每次调用patchVnode函数都会触发DOM操作,因为要修改litextContent属性值。

1
2
3
4
5
6
7
8
9
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// ...
else if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
}
// ...
}

如果给li节点提供一个key,只会触发一次DOM操作,将 C 移动到 A 前面。

所以给列表中的节点提供key,可以让diff算法明确知道哪些节点是真正的有改动的,哪些是没有变的,进而减少不必要的DOM操作,提高性能。

如果展示的列表数据有唯一ID,可以用这个ID作为key。有时也会使用数组下标作为key,在数据不会有重新排序的操作的时,这样也是没问题的。如果数组会重新排序,以下标为key时,那在排序后diff算法有可能会将原本不同的元素当成是相同的元素,增加DOM操作,降低性能。而且如果列表是像输入框这样不受控的组件,再以下标为key,经过数组重新排序后,组件中的内容可能会互相篡改。

patchdiff算法到此就了解的差不多了,整个虚拟DOM我们也几乎看完了。下一篇文章说一下Vue实例的挂载过程,把我们之前看过的内容往起串联一下。

本文作者:意林
本文链接:http://shinancao.cn/2020/01/22/Vue-Source-Code-07/
版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!