Vue source code learning (5) diff algorithm analysis

Posted on Edited on In Waline:

Previous article aboutVue Watcher原理分析的文章中After explaining the source code of Vue watcher, the watcher is divided into three categories, namely userWatcher, computeWatcher, and renderWatcher.

One of the main differences between these three is the difference in finding Watcher.value. The value of userWatcher is our observation object, the value of computeWatcher is evaluated through the handler we defined in the computed property, and the value of renderWatcher is the result of updating the view.

The previous blog mainly talked about the first two. There is no detailed explanation of the specific update view process of renderWatcher, that is, update. The main logic of this is the diff algorithm of vue.

This blog will talk about the diff algorithm of vue, and through this algorithm, we will talk about some related precautions when we usually write vue.

Source code analysis

We look directly at what the evaluation function in renderWatcher is. For how this paragraph came about, you can see my last article aboutvue数据驱动原理The blog

1
2
3
4
5
6
7
New Watcher (vm, updateComponent, noop, {//Create a watcher and pass in the updateComponent defined just now, this watcher is a rendering watcher
    before () {
        if (vm._isMounted && !vm._isDestroyed) {
            callHook(vm, 'beforeUpdate')
        }
    }
}, true /* isRenderWatcher */)

This code is the rendering Wacher created during the initialization process of the component, where the second parameter is the evaluation function, which is the function for view update.

1
2
3
UpdateComponent = () => { // define the updateComponent function, using the _update declared above, the first parameter is the component returned by _render, _render defined in core/instance/render.js
    vm._update(vm._render(), hydrating)
}

That is to say, the view update function is to re-call the render function to generate vnode and update the new vnode to the view.

Our main focus now is this update, which is our diff algorithm

_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 stores the node before vnode update, the first time you enter this method, _vnode is empty
    //This step is to assign the vm to activeInstance, which will be the parent node of the current vnode when patch is called
    const restoreActiveInstance = setActiveInstance(vm)
    vm._vnode = vnode
    // Vue.prototype.__patch__ is injected in entry points
    // based on the rendering backend used.
    If (! prevVnode ) { // determine if it is the first render
        // initial render
        //The first parameter of the first render is a real dom node
        vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */)  //_patch方法定义在platform/web/runtime/index.js中
    } else {
        // updates
        If it is update, the first parameter is 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.
}

This function is mainly a backtracking algorithm. First, save the previous global activeInstance to the function closure, and set activeInstance to the current node. At this time, call patch. If you update the sub-node, you can use the global activeInstance as the parent node. After the update is completed, restore the previous instance in the closure.

__patch__

Now it’s our main logic, patch, which is how our diff algorithm updates nodes.

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) {
    //If oldVnode is defined but vnode is not defined, it means that the old node needs to be removed
    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 {
        //Determine whether it is a native dom node
        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
}

This code seems very long, but it can be summed up in the following steps:

  • If oldVnode is defined but vnode is not defined, it means that the old node needs to be removed.
  • If vnode is defined but oldVnode is not defined, just create a new node directly.
  • If it is not a native label and it is the same node, execute the patchVnode algorithm to perform further patches. Why is it the same but still needs to be patched here? Mainly because the judgment of this same node is a preliminary judgment, similar to the Bloom filter, I say the same is not necessarily the same, but I say different is definitely different, and even if the two are really the same, the sub-node may be different. This will be discussed later., this is also the core part of diff.
    If it is not the same node, then do three things: create a new node, update the parent node of the old node, and destroy the old node.

patchVnode

Let’s talk about the third point above in detail

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

This is the core code of patchVnode, which is also divided into the following steps:

  • If the text attribute is not defined, it is not a text node.
    • At this time, if both the old and new nodes have children, execute updateChildren
    • If only the new node has it, mount the children of the new node directly
    • if only the old node has it, delete all the children of the old node
    • if the old node is a text node, then set the text of the old node to an empty string
  • If defined, it means that the new node is a text node, and directly set the text attribute of the old node to the text of the new node.

updateChildren

Now let’s get to the core of the diff algorithm

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//the head pointer of the old sub-node queue
    Let newStartIdx = 0//the head pointer of the new sub-node queue
    Let oldEndIdx = oldCh. length - 1//the tail pointer of the old sub-node queue
    Let oldStartVnode = oldCh [0]//the head pointer of the old sub-node points to the node
    Let oldEndVnode = oldCh [oldEndIdx]//the node pointed to by the tail pointer of the old sub-node
    Let newEndIdx = newCh. length - 1//the tail pointer of the new sub-node queue
    Let newStartVnode = newCh [0]//the node pointed to by the head pointer of the new sub-node queue
    Let newEndVnode = newCh [newEndIdx]//the node pointed to by the tail pointer of the new sub-node queue
    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)) {
        //If the old and new head pointers point to the same node, then recursion patches the sub-node queues of both and moves the head pointers back
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        //If the old and new tail pointers point to the same node, then recursion patches the sub-node queues of both and moves the tail pointers forward
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        //If the old node head pointer points to the same node as the new node tail pointer points to, then recursion patches the sub-node queue of both, moving the node pointed to by the old node head pointer before the node pointed to by the old node tail pointer
        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
        //If the old node tail pointer points to the same node as the new node head pointer points to, then recursion patches the sub-node queue of both, moving the node pointed to by the old node tail pointer before the node pointed to by the old node head pointer
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        //If none of the four comparisons between the head and tail of the new and old sub-nodes are successful, the first step it does is to create a hash according to the key to quickly find out if there is an old node that is not the head and tail that can be moved directly
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
        If it cannot be found, create a new node
        if (isUndef(idxInOld)) { // New element
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {
          //Found, if it is the same node, then both pathc sub-node queue, and then move the found old node to the node pointed to by the head pointer of the old node
          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 the end condition is that the old node queue has been traversed, then insert the new node that has not been traversed directly
    if (oldStartIdx > oldEndIdx) {
      refElm = isUndef (newCh[newEndIdx + 1])? null: newCh[newEndIdx + 1].elm
      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {
      //If the end of the traversal caused by the completion of the new node traversal, remove the remaining old nodes
      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
  }

This code looks very long, in fact, it is very easy to understand, everyone take a look, just give an example to try to understand.

The more important point here is the understanding of the function’nodeOps.insertBefore ', its role is to move the second parameter (the sub-node of the first parameter) in front of the third parameter, not simply insert.

If you really don’t understand, you can go take a look这篇博客。

Precautions

Through the above analysis, we should have a general understanding of the diff algorithm, but in fact there is one thing we have not yet, that is, how sameVnode is defined.

Or just send the code directly.

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

Here you can see that first of all, the key of the two must be the same. This key is the key we usually pass in when rendering the list. Many people will directly use the index of the array. In fact, there will be some problems in doing so.

The first problem is that if I have three identical nodes, now reverse, if my key is index, then all sameVnodes will fail to judge, and the reusable nodes will be destroyed and then newly created, which will affect performance.

The second problem is that if I want to delete the first node, then the key of the second node of oldCh will be the same as the first node of ch, which may cause me to delete the first node but delete the last one.

So we still try not to use the index of the array as the key.