A brief talk about the diff algorithm in Vue

Overview

The diff algorithm can be said to be a core content of Vue. I only used Vue for some development before, and I didn’t know much about the specific core content. Recently, I happened to read some content in this area. Let’s talk about the implementation of the diff algorithm of Vue2.0. Specifically, we will analyze it from several implemented functions.

Virtual dom

Virtual DOM extracts the data of real DOM and simulates the tree structure in the form of objects.

For example, the following is our real DOM

<div>
   <p>1234</p>
   <div>
       <span>1111</span>
   </div>
</div>

The virtual DOM generated according to the real DOM is as follows

 var Vnode = {
     tag: 'div',
     children: [
         {
             tag: 'p',
             text: '1234'
         },
         {
             tag: 'div',
             children:[
                 {
                     tag: 'span',
                     text: '1111'
                 }
             ]
         }
     ]
 }

principle

The principle of diff is that the current real DOM generates a virtual DOM. When the data of a node in the virtual DOM changes, a new Vnode is generated. Then this Vnode is compared with the old oldVnode. If there is a difference, it is modified directly on the real DOM.

Implementation process

The core of the implementation process of the diff algorithm is patch. The patchVnode, sameVnode and updateChildren methods are worth our attention. The following are explained in turn.

Patch Method

The core logic of patch is to compare two Vnode nodes and then update the differences to the view. The comparison method is peer comparison, rather than looping through each level. If differences are found after comparison, these differences are updated to the view. The comparison method example is as follows

sameVnode function

The function of sameVnode is to determine whether two nodes are the same. The basis for determination is key value, tag, isCommit, whether the input type is consistent, etc. This method has some flaws. When facing the situation where the key value under v-for uses index, it may also be judged as a reusable node.

It is recommended not to use index as the key value.

patchVnode function

// Pass in several parameters, oldVnode represents the old node, vnode represents the new node, readOnly represents whether it is a read-only node function patchVnode (
    oldVnode,
    vnode,
    insertedVnodeQueue,
    ownerArray,
    index,
    removeOnly
  ) {
    if (oldVnode === vnode) { //When the old node and the new node are consistent, no comparison is required, return return
    }

    if (isDef(vnode.elm) && isDef(ownerArray)) {   
      // clone reused vnode
      vnode = ownerArray[index] = cloneVNode(vnode)
    }

    const elm = vnode.elm = oldVnode.elm

    if (isTrue(oldVnode.isAsyncPlaceholder)) {
      if (isDef(vnode.asyncFactory.resolved)) {
        hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
      } else {
        vnode.isAsyncPlaceholder = true
      }
      return
    }

    //Reuse elements of static tree //We will only do this if the vnode is cloned //If the new node is not cloned, it means that the rendering function has been cloned //Reset via 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
    }

    let i
    const data = vnode.data
    if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
      i(oldVnode, vnode)
    }

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

The specific implementation logic is:

1. When the old and new nodes are the same, no changes are needed and the node is returned directly.
2. If both the old and new nodes are static nodes and have the same key, when vnode is a cloned node or a node controlled by the v-once directive, just copy oldVnode.elm and oldVnode.child to vnode.
3. Determine whether the vnode is a comment node or a text node, and then make the following processing
   1. When vnode is a text node or comment node, when vnode.text!== oldVnode.text, only the text content of vnode needs to be updated;
   2. Both oldVnode and vndoe have child nodes. If the child nodes are different, the updateChildren method is called. The specific implementation is as follows
   3. If only vnode has child nodes, determine the environment. If it is not a production environment, call the checkDuplicateKeys method to determine whether the key value is repeated. Then add the current ch to oldVnode
   4. If only oldVnode has child nodes, call the method to delete the current node

updateChildren Function

updateChildren, as the name implies, is a method for updating child nodes. From the above patchVnode method, we can see that this method will be executed when both the new and old nodes have child nodes. Let's take a look at its implementation logic. There are also some example diagrams that you may have seen similar to this. Let's take a look at the code first.

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

Here we first define several parameters, oldStartIdx (old node first index), oldEndIdx (old node last index), oldStartVnode (old node first element), oldEndVnode (old node last element); similarly, newStartIdx and other four items are the new node first index, etc.

Look at the operations in the while loop, which is also the core content

After determining that it is the same node, the node also needs to continue with the patchVnode method

• If the old first element and the new first element are the same node, the old first index and the new first index are moved right at the same time
• If the old tail element and the new tail element are the same node, the old tail index and the new tail index are shifted left at the same time
• If the old first element and the new last element are at the same node, according to the readonly judgment uploaded by the method, if it is false, then move the old first element to the last index of the old node, and at the same time move the old first index to the right and the new last index to the left.
• If the old tail element and the new first element are at the same node, according to the readonly judgment uploaded by the method, if it is false, then move the old tail element to the previous position of the old node, and at the same time move the old tail index to the left and the new first index to the right.
• If none of the above conditions are met, determine whether there is a Vnode with the same key as newStartVnode in oldCh. If not found, it means it is a new node. Create a new node and insert it.

If a Vnode with the same key as newStartVnode is found, it is named vnodeToMove, and then vnodeToMove is compared with newStartVnode. If they are the same, both are patched again. If removeOnly is false, the Vnode with the same key as newStartVnode, named vnodeToMove.elm, is moved to before oldStartVnode.elm. If the key value is the same, but the nodes are different, a new node is created.

After the While loop, if there are still nodes in the new node array or the old node array, delete or add them according to the specific situation.

When oldStartIdx > oldEndIdx, it means that oldCh is traversed first, which means there are new nodes that are redundant. Add new nodes

When newStartIdx > newEndIdx, it means that the new node is traversed first and there are still old nodes left, so delete the remaining nodes.

Let's take a look at the example picture below

Original node (oldVnode is the old node, Vnode is the new node, and diff is the node array generated after the diff algorithm)

The first time we loop, we find that the old tail element is the same as the new first element, so the old tail element D is moved to the front of the old first index, that is, in front of A. At the same time, the old tail index is moved left and the new first index is moved right.

The second time through the loop, the new first element is the same as the old first element. At this time, the positions of the two elements do not change, and the new and old first indexes move to the right at the same time.

The third loop finds that there is no node in the old element that is the same as the current element, so a new one is added, and F is placed before the old first element. Similarly, the fourth loop is the same. After two loops, a new example graph is generated.

The fifth cycle is the same as the second cycle.

The sixth loop, newStartIdx moves right again

7. After the last move, newStartIdx > newEndIdx, and the while loop has been exited, which proves that newCh is traversed first, and oldCh still has extra nodes, which are directly deleted, so the last node is

The above are several functions related to the diff algorithm and the implementation process of the diff algorithm

Conclusion

The diff algorithm is a core part of the virtual DOM. It compares the same layer and updates the changed parts to the real DOM by comparing the new and old nodes.

The specific implementation methods are patch, patchVnode and updateChildren

The core of patch is that if the new node exists but the old node does not, add it; if the old node exists but the new node does not, delete it; if both exist, determine whether they are the same, if they are the same, call patchVnode for the next step of comparison

The core of patchVnode is: if the new and old nodes are not comments or text nodes, the new node has child nodes, but the old node does not, then add a child node; if the new node has no child nodes, but the old node has child nodes, then delete the child nodes under the old node; if both have child nodes, then call the updateChildren method
The core of updateChildren is to compare the new and old nodes and add, delete or update them.

This is just a preliminary explanation of the diff algorithm of Vue2.0. The deeper principles and whether there are any changes in the diff algorithm of Vue3.0 remain to be learned.

This is the end of this article about the diff algorithm in Vue. For more information about Vue's diff algorithm, please search for previous articles on 123WORDPRESS.COM or continue to browse the following related articles. I hope you will support 123WORDPRESS.COM in the future!