Vue源码学习（五） diff算法解析

发表于 更新于 分类于 Waline：

上篇关于Vue Watcher原理分析的文章中，在解释了Vue watcher的源码之后，将watcher分为了三类，分别是userWatcher，computeWatcher，以及renderWatcher。

这三者的主要不同之一就是求Watcher.value时的不同，userWatcher的value就是我们的观察对象，computeWatcher的value求值是通过我们在computed属性中定义的handler，而renderWatcher的value就是更新视图的结果。

上篇博客中主要讲的是前两者，对于renderWatcher的具体的更新视图的流程没有详细解释，也就是update，这其中最主要的逻辑就是vue的diff算法。

这篇博客就来讲一下vue的diff算法，并通过这个算法来讲一下啊我们平时写vue时的一点相关的注意事项。

源码分析

我们直接看renderWatcher中的求值函数是什么，对于这一段是怎么来的，可以看我的上篇关于vue数据驱动原理的博客

1
2
3
4
5
6
7
new Watcher(vm, updateComponent, noop, {  //创建一个watcher，并传入刚才定义好的updateComponent，这个watcher是一个渲染watcher
    before () {
        if (vm._isMounted && !vm._isDestroyed) {
            callHook(vm, 'beforeUpdate')
        }
    }
}, true /* isRenderWatcher */)

这段代码就是组件在初始化过程中创建的渲染Wacher，其中第二个参数就是求值函数，也就是视图更新的函数。

1
2
3
updateComponent = () => { //定义updateComponent函数,調用上面声明的_update,第一个参数是_render返回的组件,_render定义在core/instance/render.js中
    vm._update(vm._render(), hydrating)
}

也就是说视图更新函数就是重新调用render函数生成vnode，并把新的vnode更新到视图上。

我们现在主要的关注点就是这个update，也就是我们的diff算法

_update

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
Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) {
    const vm: Component = this
    const prevEl = vm.$el
    const prevVnode = vm._vnode // _vnode存储的就是vnode update之前的节点，第一次进入本方法，_vnode是空
    // 这一步是将vm赋值给activeInstance，等会调用patch的时候作为当前vnode的父节点
    const restoreActiveInstance = setActiveInstance(vm)
    vm._vnode = vnode
    // Vue.prototype.__patch__ is injected in entry points
    // based on the rendering backend used.
    if (!prevVnode) { // 判断是否是初次渲染
        // initial render
        // 初次渲染第一个参数是一个真实的dom节点
        vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */)  //_patch方法定义在platform/web/runtime/index.js中
    } else {
        // updates
        // 如果是update，那第一个参数就是vnode了
        vm.$el = vm.__patch__(prevVnode, vnode)
    }
    restoreActiveInstance()
    // update __vue__ reference
    if (prevEl) {
        prevEl.__vue__ = null
    }
    if (vm.$el) {
        vm.$el.__vue__ = vm
    }
    // if parent is an HOC, update its $el as well
    if (vm.$vnode && vm.$parent && vm.$vnode === vm.$parent._vnode) {
        vm.$parent.$el = vm.$el
    }
    // updated hook is called by the scheduler to ensure that children are
    // updated in a parent's updated hook.
}

这个函数主要就是一个回溯算法，首先将之前全局的activeInstance保存到函数闭包中，并将activeInstance置为当前的节点，这个时候去调用patch如果更新子节点就可以用全局的activeInstance作为父节点，更新完成之后再将闭包中的之前的instance回复回来。

__patch__

现在就是我们最主要的逻辑了，patch，也就是我们的diff算法是如何更新节点的。

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
return function patch (oldVnode, vnode, hydrating, removeOnly) {
    //如果定义了oldVnode但是没有定义vnode，说明是要移除旧的节点
    if (isUndef(vnode)) {
        if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
        return
    }

    let isInitialPatch = false
    const insertedVnodeQueue = []

    if (isUndef(oldVnode)) {
        // empty mount (likely as component), create new root element
        isInitialPatch = true
        createElm(vnode, insertedVnodeQueue)
    } else {
        //判断是否是原生的dom节点
        const isRealElement = isDef(oldVnode.nodeType)
        if (!isRealElement && sameVnode(oldVnode, vnode)) {
            // patch existing root node
            patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
        } else {
            if (isRealElement) {
                // mounting to a real element
                // check if this is server-rendered content and if we can perform
                // a successful hydration.
                if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
                    oldVnode.removeAttribute(SSR_ATTR)
                    hydrating = true
                }
                if (isTrue(hydrating)) {
                    if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
                        invokeInsertHook(vnode, insertedVnodeQueue, true)
                        return oldVnode
                    } else if (process.env.NODE_ENV !== 'production') {
                        warn(
                            'The client-side rendered virtual DOM tree is not matching ' +
                            'server-rendered content. This is likely caused by incorrect ' +
                            'HTML markup, for example nesting block-level elements inside ' +
                            '<p>, or missing <tbody>. Bailing hydration and performing ' +
                            'full client-side render.'
                        )
                    }
                }
                // either not server-rendered, or hydration failed.
                // create an empty node and replace it
                oldVnode = emptyNodeAt(oldVnode)
            }

            // 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(parentElm, [oldVnode], 0, 0)
            } else if (isDef(oldVnode.tag)) {
                invokeDestroyHook(oldVnode)
            }
        }
    }

    invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
    return vnode.elm
}

这段代码看似很长，其实总结起来就是以下几步：

  • 如果定义了oldVnode但是没有定义vnode，说明是要移除旧的节点。
  • 如果定义了vnode但是没有定义oldVnode，直接创建新节点就好。
  • 如果不是原生标签并且是相同的节点，就执行patchVnode算法，去进行进一步的patch，这里为什么明明是相同的却还要patch呢？主要是因为这个相同节点的判断是一个初步的判断，类似于布隆过滤器，我说相同不一定相同，但是我说不同就是一定不同，而且就算二者真的相同，子节点也可能不同，这个待会在讲，这个也是diff最核心的部分。
  • 如果不是相同节点，那就做三件事：创建新节点，更新旧节点的父节点，销毁旧节点。

patchVnode

我们再来详细讲一下上面的第三点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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(elm, oldCh, 0, oldCh.length - 1)
    } else if (isDef(oldVnode.text)) {
        nodeOps.setTextContent(elm, '')
    }
} else if (oldVnode.text !== vnode.text) {
    nodeOps.setTextContent(elm, vnode.text)
}

这就是patchVnode的核心代码，也是分为以下几步：

  • 如果没定义text属性，说明不是文本节点。
    • 这个时候如果新旧节点都有children，那就执行updateChildren
    • 如果只有新节点有，就把新节点的children直接挂载
    • 如果只有旧节点有，那就把所有旧节点的children删除
    • 如果旧节点是文本节点，那就把旧节点的文本置为空字符串
  • 如果定义了，说明新节点是文本节点，直接把旧节点的text属性置为新节点的text

updateChildren

现在我们进入和diff算法最核心的部分

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
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)) {
        // 如果新旧的头指针指向的节点相同，则递归patch二者的子节点队列，并把二者头指针向后移动
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // 如果新旧的尾指针指向的节点相同，则递归patch二者的子节点队列，并把二者尾指针向前移动
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        // 如果旧节点头指针指向的节点与新节点尾指针指向的节点相同，则递归patch二者的子节点队列，把旧节点头指针指向的节点移动到旧节点尾指针指向的节点之前
        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
        // 如果旧节点尾指针指向的节点与新节点头指针指向的节点相同，则递归patch二者的子节点队列，把旧节点尾指针指向的节点移动到旧节点头指针指向的节点之前
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        //如果新旧子节点的头尾四次比较都没有一次成功的，它第一步做的其实根据key是创建一个hash，用于快速找到是否存在一个不是头尾的旧节点可以直接移动过来
        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 {
          // 找到了，如果是相同节点，则pathc二者子节点队列，然后把找到的旧节点移动到旧节点头指针指向的节点之后
          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(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
  }

这段代码看起来很长，其实也很容易懂，大家自己看一看，随便举个例子试一下就明白了。

这里比较重要的一点是对 nodeOps.insertBefore这个函数的理解，它的作用是将第一个参数中的第二个参数（第一个参数的子节点）移动到第三个参数前面，不是单纯的insert。

如果大家实在不明白，可以去看一下这篇博客。

注意事项

通过上述的分析，我们对diff算法应该有了个大致的了解，但其实有一点我们还没有将，那就是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要相同，这个key就是我们平时列表渲染时传入的key，很多人都会直接用数组的index，其实这样做会有一些问题。

第一个问题就是如果我有三个相同的节点，现在reverse，如果我的key是index，那么所有的sameVnode都会判断失败，明明可以重用的节点却被销毁然后新建了，这对性能会有影响。

第二个问题是如果我要删除第一个节点，那么oldCh第二个节点的key就会与ch的第一个节点相同，这就可能导致我本来想删除第一个节点，却删除了最后一个节点。

所以说我们还是尽量不要用数组的index作为key。