preface

This article is quite long, the main length is introduced in the DIFF algorithm, before understanding the diFF algorithm, it is necessary to understand why Vue needs the DIFF algorithm, and when Vue will use the DIFF algorithm, let’s take a look at these two problems.

Why does Vue need diff algorithm?

Diff algorithm is an inevitable product of virtual DOM. By comparing the old and new virtual DOM and updating the changes to the real DOM, unnecessary DOM operations can be reduced as much as possible and performance can be improved.

When the state is changed, the related Watcher instance will be notified to update. At this time, the corresponding component will render again and generate a new VNode. There will always be some parts of a component that do not need to be updated. If the whole component is DOM updated, the performance will be greatly affected. Therefore, the DIff algorithm is used to compare the old and new VNodes to find the nodes that need to be updated and then update them. This process is called patch.

In Vue, components are mounted, updated and removed through this patch stage. Before introducing patch, let’s know when Vue will execute patch.

Time when patch is executed

Vue.prototype.$mount

$mount(‘#app’); Vue. Prototype.$mount() actually calls mountComponent

// core/stance/init.js
Vue.prototype._init = function (options) {
  // ...
  const vm = this;
  if(vm.$options.el) { vm.$mount(vm.$options.el); }}// platforms/web/runtime/index.js
Vue.prototype.$mount = function (el, hydrating) {
  el = el && inBrowser ? query(el) : undefined
  return mountComponent(this, el, hydrating)
}
Copy the code

mountComponent

As you know from its name, this function is used to mount components, and executing this function does several things

  1. Call the lifecycle functionbeforeMount
  2. Define a functionupdateComponentThis function is executed internallyvm._updateAnd thevm._updateThe parameter isvm._render()The result is that a new VNode is generated
  3. To create aWatcherInstance, and willupdateComponentAs an argument, this function is called when the component is mounted and updated

Here is the main code involved in mountComponent and Watcher

function mountComponent (vm, el) {
  callHook(vm, 'beforeMount')
  
  updateComponent = () = > {
    vm._update(vm._render(), hydrating)
  }
  
  new Watcher(vm, updateComponent, noop, {
    before () {
      if(vm._isMounted && ! vm._isDestroyed) { callHook(vm,'beforeUpdate')}}},true /* isRenderWatcher */)}// src/core/observer/watcher.js
export default class Watcher {
  constructor(vm, expOrFn, cb, options, isRenderWatcher) {
    this.getter = expOrFn  // updateComponent is stored as a expOrFn parameter in the getter property
    this.value = this.lazy ? undefined : this.get() // called once when mounted
  }
  get () {
    // ...
    value = this.getter.call(vm, vm)
    // ...
  }
  // Notifies the update, calling the getter
  update () {
    if (this.lazy) {
      this.dirty = true
    } else if (this.sync) {
      this.run()
    } else {
      queueWatcher(this) // Run is also called at the end of an asynchronous queue update
    }
  }
  run () {
    // ...
    const value = this.get()
  }
}
Copy the code

vm._update

Now we know that both component mounts and updates call the _update method, which takes the vNode generated by rerender as an argument, internally retrieves the current vNode (preVnode), and then handles it in one of two ways

  • No preVnode: currently there is no old VNode, is mount phase, called__patch__Passing in DOM elements$elAnd the newvnode
  • PreVnode: indicates that the current is the update phase, called__patch__The incomingpreVnodeAnd the newvnode

The same function is called in both cases, but the arguments passed in are different, so the case handling needs to be determined inside __Patch__

Vue.prototype._update = function (vnode, hydrating) {
  var vm = this;
  var prevEl = vm.$el;
  var prevVnode = vm._vnode;
  if(! prevVnode) {// initial render
    vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */);
  } else {
    // updatesvm.$el = vm.__patch__(prevVnode, vnode); }}Copy the code

vm.__patch__

Vm. __patch__ is also a method on the prototype object, as defined below

Patch is only needed in the browser, server rendering does not have the concept of DOM manipulation and mount, so patch is not needed

// src/platforms/web/runtime/index.js
Vue.prototype.__patch__ = inBrowser ? patch : noop
Copy the code

The Patch function is returned by calling createPatchFunction

import * as nodeOps from 'web/runtime/node-ops'
import { createPatchFunction } from 'core/vdom/patch'
import baseModules from 'core/vdom/modules/index'
import platformModules from 'web/runtime/modules/index'

// the directive module should be applied last, after all
// built-in modules have been applied.
const modules = platformModules.concat(baseModules)

export const patch: Function = createPatchFunction({ nodeOps, modules })
Copy the code

CreatePatchFunction accepts two parameters. What are they

  • nodeOpsIs the web platform under some DOM API encapsulation, in the patch stage, naturally, there is no need to operate DOM
  • modulesThey are some core modules, such as ATTr, class, style, event, directive, ref, etc. These modules expose THE API of Create, Update, remove, destory, etc., which will be called in the patch phase

CreatePatchFunction has a lot of code and declared a lot of functions, which is easy to call in each phase of patch. Patch logic is very complex, but here we only focus on the implementation of diff algorithm, and there is no more to introduce. The following is the definition of Patch function

export function createPatchFunction (backend) {
  return function patch (oldVnode, vnode, hydrating, removeOnly) {}}Copy the code

Patch receives oldVnode and VNode, and then processes them according to different values of the two parameters. Finally, it is time to explore the realization principle of Patch. Next, it is time to analyze the code step by step to understand how VUE implements diff algorithm.

Working principle of patch phase

Patch method has a lot of codes, but it is basically just conditional judgment and then different operations are performed. The core code of DIff algorithm is to continue to compare the children of old and new VNodes and how to achieve efficient comparison when they correspond to the same elements. Therefore, we only need to understand the general process here. The following is the flow chart of patch method execution

graph TD patch[Start] --> vnode{vnode is undef? }; vnode -->|undefined| oldVnode1{oldVnode is undef? }; OldVnode1 - > | No undef | remove oldVnode - > return; oldVnode1 -->|undefined| return; vnode -->|No undef| oldVnode2{oldVnode is undef}; oldVnode2 -->|undefined| createEl[createElm]; OldVnode2 - > | vnode && oldVnode | condition judgment} {conditions; Condition - > | ov is VNode instance and samenode | patchVnode; Condition - > | ov is $el | mount; Condition - > | ov is VNode instance and! Samenode | cr/creating a new DOM to remove the old node;

The following is the main code and comments involved. The core process is to qualify sameVnode(oldVnode, vNode) and then call patchVnode, which will be described later

function patch (oldVnode, vnode) {
  // If there is no new vnode, delete the old vnode (if there is one) and return
  if (isUndef(vnode)) {
    if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
    return
  }
  // No oldVnode, no diff
  if (isUndef(oldVnode)) {
    createElm(vnode, insertedVnodeQueue)
  } else {
    // oldVnode and vnode are not undefined/null
    // From the previous call to '__patch__', oldVnode may be a real DOM element or a Vnode instance
    
    const isRealElement = isDef(oldVnode.nodeType)
    // The core of diff algorithm. If oldVnode is not a real DOM, sameVnode is called to determine whether it corresponds to the same element. If it is, patchVnode is called
    if(! isRealElement && sameVnode(oldVnode, vnode)) { patchVnode(oldVnode, vnode, insertedVnodeQueue,null.null, removeOnly)
    } else {
      // Insert a new element
      if (isRealElement) { / *... * / }
      const oldElm = oldVnode.elm
      const parentElm = nodeOps.parentNode(oldElm)
      createElm(vnode, insertedVnodeQueue, oldElm._leaveCb ? null : parentElm, nodeOps.nextSibling(oldElm))
      // Destroy the old node
      if (isDef(parentElm)) {
        removeVnodes([oldVnode], 0.0)}else if (isDef(oldVnode.tag)) {
        invokeDestroyHook(oldVnode)
      }
    }
  }
}
Copy the code

sameVnode

SameVnode is used to determine whether old and new VNodes correspond to the same element. If so, in-place reuse can be considered, such as directly modifying textContent, or continuing recursive comparison of children if there are children, otherwise the comparison will not continue and direct replacement

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)
      )
    )
  )
}
Copy the code

The sameVnode core code is as follows. If all the following conditions are met, it is judged as sameVnode

  • keyThe virtual DOM uses a unique key to distinguish elements, which means that the elements are completely independent. If the key is different, it is not sameVnode and is in usev-forAlways add a key when rendering a list to prevent the display from being distorted when adding or deleting elements from the list
  • Tag The tag names must be the same
  • isCommentWhether or not to annotate a node must be both yes and no, in the case of annotating a node, such as using dynamic componentscomponentWhen,isIf false, null, or undefined, vue generates a comment node<! ---->
  • Data contains specific binding data such as style and attrs
  • sameInputTypeIf the same asinputElement, but also satisfytypeThe same

patchVnode

When patchVnode is arrived, it means that the old and new nodes are already sameVnode, but it needs to be processed in various cases. The main code is as follows

function patchVnode (oldVnode, vnode) {
  if (oldVnode === vnode) return
  
  const elm = vnode.elm = oldVnode.elm
  const oldCh = oldVnode.children
  const ch = vnode.children
  
  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);
  }
}
Copy the code

This function does a couple of things

  1. ifoldVnode 和 vnodeIf the value is the same object, return is required
  2. The next step is to determine the condition, first save the vNode corresponding element inelm
  3. ifvnodeIf there are text nodes, update text directly
  4. ifvnodeThere are no text nodes in the following cases
    • If the old and new,vnodeThere arechildren, and does not point to the same arrayupdateChildren, the sublevels are compared first
    • If only the VNode has onechildrenThe calladdVnodesCreate a child, if anyoldVnode.text, to be empty
    • Otherwise, if only oldVnode has itchildren, the implementationremoveVnodesRemove children
    • If no new or old VNode existschildren, only oldVnode has text nodes, so the text is null

The diff algorithm is based on updateChildren, and the diff algorithm is based on updateChildren. The diff algorithm is based on updateChildren, and the diff algorithm is based on updateChildren

updateChildren

UpdateChildren is a node that does not need to be updated, reused, added or deleted in the subhierarchy of the old and new VNodes. If the node is directly searched in the two arrays, the time complexity is O(n^2), so direct traversal comparison is obviously not advisable. In order to improve efficiency, Vue adopts the following strategy optimization algorithms in turn

Compare heads and tails

Reordering or modifying an item in a list component does not replace the entire list, where the top and bottom nodes may remain the same, or elements may be moved to another location, or elements may be reused in place. In this case, Vue uses a head-to-tail comparison strategy. Here is the main code

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]
  // ...
  constcanMove = ! removeOnlywhile (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 {
      / /...}}}Copy the code

So what does this part of code do?

  • Create four index subscripts to initialize the heads and tails of the new and old children
  • Use four variables to store the node where the four index subscripts are traversed each time
  • When both arrays are nodes to be compared, the loop makes the following judgments. If the following conditions are true, the loop skips the latter judgments and starts the next cycle directly
    • Without oldStartVnode, simply move oldStartIdx one place back and update the value of oldStartVnode
    • Without oldEndVnode, simply move oldEndIdx forward one position and update the oldEndVnode value
    • Check whether the old and new header vNodes are samevNodespatchVnode, moves the two header Pointers back and updates the values of the corresponding variables
    • Check whether the old and new tail vNodes are samevNodespatchVnode, moves the two tail Pointers forward and updates the values of the corresponding variables
    • Check whether oldStartVnode and newEndVnode are sameVnode, if yes, it indicates that the node runs behind, and callpatchVnode, then move the node to the new location, moving oldStartIdx back and newEndIdx forward
    • As above, determine oldEndVnode and newStartVnode

The following examples illustrate that p node has three child elements a, B and C, and component update is triggered after reordering (regardless of addition and deletion). At this time, the following steps are used to compare the sub-levels

  1. oldStartVnode 与 newStartVnodeThe values are both A, consistent with sameVnode, and patchVnode is directly invoked to change oldStartVnode to B and newStartVnode to C. At this time, oldStartIdx = 1 and newStartIdx = 1, and other parameters remain unchanged
  2. The second time, we found a matchsameVnode(oldStartVnode, newEndVnode)First call patchVnode to compare the sub-level first. After the sub-level processing is completed, move B to the new position, and then change oldStartVnode to C and newEndVnode to C. At this point, oldStartIdx = 2. newEndIdx = 1
  3. The third time, we found a matchsameVnode(oldStartVnode, newStartVnode), call patchVnode, oldStartIdx = 3, newStartIdx = 2
  4. Exit the loop to complete the diff operation
    p               p
  / | \    ==>    / | \
 a  b  c         a  c  b
Copy the code

Use keys to create mappings

Since only four nodes can be compared at a time, if the node moves to the middle, the above method will not be able to find the matching node. Instead, we can only find the node matching newStartVnode in oldch. We usually add a key. Establish oldch key to IDX map, directly through the newStartVnode key can find the corresponding oldVnode, other nodes with different keys naturally do not need to consider

Find the corresponding oldVnode by key, and then compare whether it is sameVnode. If yes, call patchVnode, move oldVnode to a new location after completing diff of subtree, otherwise create a new node

function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
  let oldKeyToIdx, idxInOld, vnodeToMove, refElm
  
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if {
      // ...
    } else {
      if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
      idxInOld = isDef(newStartVnode.key)
        ? oldKeyToIdx[newStartVnode.key] // Use key directly to find the mapping table
        : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)  // There is no key
      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]
    }
  }
}
Copy the code

Take another example to illustrate that the P node has four child elements a, B, C and D, and component updates are triggered after reordering. At this time, the following steps are used to compare the sub-levels

  1. In this case, the head and tail comparison can not find the condition
  2. Now I’m going to use key to find,newStartVnodeOldch = 2; oldch = 2; oldch = 2; oldch = 2newStartVnodeChange it to a, and the next round can quickly find the position of A in oldch by pairwise comparison
  3. Compare until diff is done to exit the loop
     p                 p
  / / \ \    ==>    / / \ \
 a  b  c d         c a  d  b
Copy the code

Traversal search

Without the key, we would have to go through oldch one by one and call findIdxInOld for the search. Here the time complexity would be high, but with the key added, it would not go this far, just as a backstop

Additions or deletions

If oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx, there must be a condition that fails to exit the loop. If oldStartIdx > oldEndIdx, there must be a new node. Call addVnodes to batch create nodes. The other way around is to remove some old nodes.

function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {}
  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)
  }
}
Copy the code

At this point, the diff operation of a component update process is completed, and nodes that are updated, added, and deleted are updated to the real DOM one by one. Then the next Watcher call is continued until all Watcher updates are complete, and the nextTick callback is executed.

conclusion

Diff algorithm is the optimal solution between the two extremes of full DOM update and O(n^3) precise search. It not only finds the nodes that need to be updated as much as possible and eliminates unnecessary DOM updates, but also takes into account the complexity of the algorithm to avoid performance problems. Diff algorithm has the following two characteristics:

  • Depth-first: If the old and new vNodes are Samevnodes, the children are compared first. This operation is recursive. If the old and new VNodes are not Samevnodes, the comparison will not continue, because the probability of reusable children is low, and even if they exist, the continued comparison is not worth the loss
  • Same-layer comparison: only the nodes of the same layer will be compared. If there is more than one layer in the middle after the update, this situation is directly judged as not comparable, directly update or delete all, but generally we will not write such code

After learning the principles of the DIFF algorithm, we can consciously write higher-quality code to help the DIFF algorithm execute more efficiently, for example

  • usev-forRender the list, to add a key to improve the efficiency of judgment, search, but also to prevent elements from being incorrectly reused bugs
  • usev-if/v-elseControl element switching without adding keys allows VUE to reuse elements efficiently
  • Combining the concepts of depth-first and same-layer comparison, the hierarchical relationship of nodes is optimized to improve the efficiency of patch as much as possible