In-depth understanding of VNode and diff algorithm in vue2

Virtual dom and diff algorithm is a difficulty in the learning process of vue and must be mastered in the interview A point of knowledge. The two complement each other and are the core of the vue framework. Today we will summarize the virtual dom and diff algorithms in vue2. (Learning video sharing: vue video tutorial)

What is VNode

We know that render function will be converted into VNode. VNode is actually a tree based on JavaScript objects, using object attributes to describe nodes. In fact, it is just a layer of abstraction of the real DOM. Finally, this tree can be mapped to the real environment through a series of operations.

For example, if there is the following template

<template>
  <span class="demo" v-show="isShow"> This is a span. </span> 
</template>

, replace it with VNode, and it will look like this in the future

{
  tag: "span",
  data: {
    /* 指令集合数组 */
    directives: [
      {
        /* v-show指令 */
        rawName: "v-show",
        expression: "isShow",
        name: "show",
        value: true,
      },
    ],
    /* 静态class */
    staticClass: "demo",
  },
  text: undefined,
  children: [
    /* 子节点是一个文本VNode节点 */
    {
      tag: undefined,
      data: undefined,
      text: "This is a span.",
      children: undefined,
    },
  ],
};

In general , VNode is a JavaScript object. This JavaScript object can completely represent the real DOM.

Why vue uses VNode

The author thinks there are two reasons

• BecauseVirtual DOM It is based on JavaScript objects and does not rely on the real platform environment, so it has cross-platform capabilities, such as browser platforms, Weex, Node, etc.

• Reduce operationsDOM. For any page changes, only VNode is used for operation comparison. Only the last mount update is required. DOM, avoids frequent operations DOM, reduces browser reflow and redrawing, thereby improving page performance.

diff algorithm

Let’s take a look at the diff algorithm## involved in Component update #.

As mentioned before when we talked about dependency collection, the

get method passed to Rendering watcher is actually updateComponentmethod.

updateComponent = () => {
  vm._update(vm._render(), hydrating)
}

new Watcher(vm, updateComponent, noop, {
  before () {
    if (vm._isMounted) {
      callHook(vm, 'beforeUpdate')
    }
  }
}, true /* isRenderWatcher */)

So the component will trigger this method again when the responsive data changes. Next, let’s analyze the _update

method in

updateComponent in detail.

_update

makes a distinction between initial rendering and update in the _update

method, although both are called

__patch__ method, but the parameters passed are different.

// src/core/instance/lifecycle.js

Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) {
  const vm: Component = this
  const prevEl = vm.$el
  const prevVnode = vm._vnode
  vm._vnode = vnode
  // 初次渲染没有 prevVnode，组件更新才会有
  if (!prevVnode) {
    // 初次渲染
    vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */)
  } else {
    // 更新
    vm.$el = vm.__patch__(prevVnode, vnode)
  }
  
  // ...
}

Let’s take a look at __patch__

method

__patch__

patch

The method receives four parameters. Since

oldVnode is vm.$el during initial rendering, it is null, so there is no oldVnode# in initial rendering. ##. <pre class="brush:js;toolbar:false;">// src/core/vdom/patch.js return function patch (oldVnode, vnode, hydrating, removeOnly) { // 新节点不存在，只有oldVnode就直接销毁，然后返回 if (isUndef(vnode)) { if (isDef(oldVnode)) invokeDestroyHook(oldVnode) return } let isInitialPatch = false const insertedVnodeQueue = [] // 没有老节点，直接创建，也就是初始渲染 if (isUndef(oldVnode)) { isInitialPatch = true createElm(vnode, insertedVnodeQueue) } else { const isRealElement = isDef(oldVnode.nodeType) // 不是真实dom，并且是相同节点走patch if (!isRealElement &amp;&amp; sameVnode(oldVnode, vnode)) { // 这里才会涉及到diff算法 patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly) } else { if (isRealElement) { // ... } // replacing existing element const oldElm = oldVnode.elm const parentElm = nodeOps.parentNode(oldElm) // 1.创建一个新节点 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) ) // 2.更新父节点占位符 if (isDef(vnode.parent)) { let ancestor = vnode.parent const patchable = isPatchable(vnode) while (ancestor) { for (let i = 0; i &lt; cbs.destroy.length; ++i) { cbs.destroy[i](ancestor) } ancestor.elm = vnode.elm if (patchable) { for (let i = 0; i &lt; cbs.create.length; ++i) { cbs.create[i](emptyNode, ancestor) } 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 &lt; insert.fns.length; i++) { insert.fns[i]() } } } else { registerRef(ancestor) } ancestor = ancestor.parent } } // 3.删除老节点 if (isDef(parentElm)) { removeVnodes([oldVnode], 0, 0) } else if (isDef(oldVnode.tag)) { invokeDestroyHook(oldVnode) } } } //触发插入钩子 invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch) return vnode.elm }</pre>patchThe approximate process of the method is as follows:

There are no new nodes, only old nodes, and the old nodes are deleted directly.

• Only new nodes are added directly without old nodes.

• If there are both new nodes and old nodes, it will be judged whether they are the same nodes. If they are the same, enter

  pathVnode
.
• patchVnode

  We will focus on the analysis later. If there are both new nodes and old nodes, determine whether they are the same nodes. If they are not the same, delete the old nodes and add new nodes directly.

• Let’s take a look at how it determines that it is the same node.

  // src/core/vdom/patch.js
  
  function sameVnode (a, b) {
    return (
      a.key === b.key &&
      a.asyncFactory === b.asyncFactory && (
        (
          a.tag === b.tag &&
          a.isComment === b.isComment &&
          isDef(a.data) === isDef(b.data) &&
          sameInputType(a, b)
        ) || (
          isTrue(a.isAsyncPlaceholder) &&
          isUndef(b.asyncFactory.error)
        )
      )
    )
  }
  
  function sameInputType (a, b) {
    if (a.tag !== 'input') return true
    let i
    const typeA = isDef(i = a.data) && isDef(i = i.attrs) && i.type
    const typeB = isDef(i = b.data) && isDef(i = i.attrs) && i.type
    return typeA === typeB || isTextInputType(typeA) && isTextInputType(typeB)
  }

To determine whether two

VNode

nodes are the same node, the following conditions need to be met at the same time

key

Same

• All have the same asynchronous component factory function

• tag
(the tag name of the current node)

• isComment
Whether they are both comment nodes

• Whether

  data
(the object corresponding to the current node contains some specific Data information is a VNodeData type)

• When the label is

, the
• type

  must be the sameWhen the

  tag, key, isComment
of two

VNode

are the same, and data is defined or undefined at the same time, and if If the tag is input, the type must be the same. At this time, these two VNode are counted as sameVnode, and patchVnode operations can be performed directly. patchVnode

Let’s analyze the patchVnode method in detail.

// src/core/vdom/patch.js

function patchVnode (
  oldVnode,
  vnode,
  insertedVnodeQueue,
  ownerArray,
  index,
  removeOnly
) {
  // 两个vnode相同则直接返回
  if (oldVnode === vnode) {
    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
  }

  /*
    如果新旧VNode都是静态的，同时它们的key相同（代表同一节点），
    并且新的VNode是clone或者是标记了once（标记v-once属性，只渲染一次），
    那么只需要替换componentInstance即可。
  */
  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
  /*调用prepatch钩子*/
  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)) {
    /*新老节点均有children子节点，则对子节点进行diff操作，调用updateChildren*/
    if (isDef(oldCh) && isDef(ch)) {
      if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
    /*如果只有新节点有子节点，先清空elm文本内容，然后为当前DOM节点加入子节点。*/
    } else if (isDef(ch)) {
      if (process.env.NODE_ENV !== &#39;production&#39;) {
        checkDuplicateKeys(ch)
      }
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, &#39;&#39;)
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
    /*如果只有老节点有子节点，则移除elm所有子节点*/
    } else if (isDef(oldCh)) {
      removeVnodes(oldCh, 0, oldCh.length - 1)
    /*当新老节点都无子节点的时候，因为这个逻辑中新节点text不存在，所以直接去除ele的文本*/
    } else if (isDef(oldVnode.text)) {
      nodeOps.setTextContent(elm, &#39;&#39;)
    }
  // 新节点是文本节点，如果文本不一样就设置新的文本  
  } else if (oldVnode.text !== vnode.text) {
    nodeOps.setTextContent(elm, vnode.text)
  }
  /*调用postpatch钩子*/
  if (isDef(data)) {
    if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
  }
}

patchVnodeThe approximate process of the method is as follows:

1. If the old and new nodes are the same, return directly. <p>2.如果新旧VNode都是静态的，同时它们的key相同（代表同一节点），并且新的VNode是clone或者是标记了once（标记v-once属性，只渲染一次），那么只需要替换componentInstance即可。</p> <p>3.新节点不是文本节点，新老节点均有<code>children子节点，则对子节点进行diff操作，调用updateChildren，这个updateChildren是diff算法的核心，后面我们会重点说。

4.新节点不是文本节点，如果老节点没有子节点而新节点存在子节点，先清空老节点DOM的文本内容，然后为当前DOM节点加入子节点。

5.新节点不是文本节点，当新节点没有子节点而老节点有子节点的时候，则移除该DOM节点的所有子节点。

6.新节点不是文本节点，并且新老节点都无子节点的时候，只需要将老节点文本清空。

7.新节点是文本节点，并且新老节点文本不一样，则进行文本的替换。

updateChildren(diff算法核心)

updateChildren是diff算法的核心，下面我们来重点分析。

这两张图代表旧的VNode与新VNode进行patch的过程，他们只是在同层级的VNode之间进行比较得到变化（相同颜色的方块代表互相进行比较的VNode节点），然后修改变化的视图，所以十分高效。所以Diff算法是:深度优先算法。 时间复杂度:O(n)

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

  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]
    // 老 VNode 节点的头部与新 VNode 节点的头部是相同的 VNode 节点，直接进行 patchVnode，同时 oldStartIdx 与 newStartIdx 向后移动一位。
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    // 两个 VNode 的结尾是相同的 VNode，同样进行 patchVnode 操作。并将 oldEndVnode 与 newEndVnode 向前移动一位。
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    // oldStartVnode 与 newEndVnode 符合 sameVnode 的时候，
    // 将 oldStartVnode.elm 这个节点直接移动到 oldEndVnode.elm 这个节点的后面即可。
    // 然后 oldStartIdx 向后移动一位，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]
    // oldEndVnode 与 newStartVnode 符合 sameVnode 时，
    // 将 oldEndVnode.elm 插入到 oldStartVnode.elm 前面。
    // oldEndIdx 向前移动一位，newStartIdx 向后移动一位。
    } 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 {
      // createKeyToOldIdx 的作用是产生 key 与 index 索引对应的一个 map 表
      if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
      idxInOld = isDef(newStartVnode.key)
        ? oldKeyToIdx[newStartVnode.key]
        : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
      // 如果没有找到相同的节点，则通过 createElm 创建一个新节点，并将 newStartIdx 向后移动一位。
      if (isUndef(idxInOld)) { // New element
        createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
      } else {
        vnodeToMove = oldCh[idxInOld]
        // 如果找到了节点，同时它符合 sameVnode，则将这两个节点进行 patchVnode，将该位置的老节点赋值 undefined
        // 同时将 newStartVnode.elm 插入到 oldStartVnode.elm 的前面
        if (sameVnode(vnodeToMove, newStartVnode)) {
          patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
          oldCh[idxInOld] = undefined
          canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
        } else {
          // 如果不符合 sameVnode，只能创建一个新节点插入到 parentElm 的子节点中，newStartIdx 往后移动一位。
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        }
      }
      newStartVnode = newCh[++newStartIdx]
    }
  }
  // 当 while 循环结束以后，如果 oldStartIdx > oldEndIdx，说明老节点比对完了，但是新节点还有多的，
  // 需要将新节点插入到真实 DOM 中去，调用 addVnodes 将这些节点插入即可。
  if (oldStartIdx > oldEndIdx) {
    refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
    addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
  // 如果满足 newStartIdx > newEndIdx 条件，说明新节点比对完了，老节点还有多，
  // 将这些无用的老节点通过 removeVnodes 批量删除即可。
  } else if (newStartIdx > newEndIdx) {
    removeVnodes(oldCh, oldStartIdx, oldEndIdx)
  }
}

vue2的diff算法采用的是双端比较，所谓双端比较就是新列表和旧列表两个列表的头与尾互相对比，在对比的过程中指针会逐渐向内靠拢，直到某一个列表的节点全部遍历过，对比停止。

首尾对比的四种情况

我们首先来看看首尾对比的四种情况。

• 使用旧列表的头一个节点oldStartNode与新列表的头一个节点newStartNode对比

• 使用旧列表的最后一个节点oldEndNode与新列表的最后一个节点newEndNode对比

• 使用旧列表的头一个节点oldStartNode与新列表的最后一个节点newEndNode对比

• 使用旧列表的最后一个节点oldEndNode与新列表的头一个节点newStartNode对比

首先是 oldStartVnode 与 newStartVnode 符合 sameVnode 时，说明老 VNode 节点的头部与新 VNode 节点的头部是相同的 VNode 节点，直接进行 patchVnode，同时 oldStartIdx 与 newStartIdx 向后移动一位。

其次是 oldEndVnode 与 newEndVnode 符合 sameVnode，也就是两个 VNode 的结尾是相同的 VNode，同样进行 patchVnode 操作并将 oldEndVnode 与 newEndVnode 向前移动一位。

接下来是两种交叉的情况。

先是 oldStartVnode 与 newEndVnode 符合 sameVnode 的时候，也就是老 VNode 节点的头部与新 VNode 节点的尾部是同一节点的时候，将 oldStartVnode.elm 这个节点直接移动到 oldEndVnode.elm 这个节点的后面即可。然后 oldStartIdx 向后移动一位，newEndIdx 向前移动一位。

同理，oldEndVnode 与 newStartVnode 符合 sameVnode 时，也就是老 VNode 节点的尾部与新 VNode 节点的头部是同一节点的时候，将 oldEndVnode.elm 插入到 oldStartVnode.elm 前面。同样的，oldEndIdx 向前移动一位，newStartIdx 向后移动一位。

Finally, when none of the above situations are met, how to deal with this situation?

Search and compare

That is search and comparison.

First generate a map## corresponding to the key of oldVnode and the index index through the createKeyToOldIdx method. # surface.

Then we can quickly obtain the same

key# from oldKeyToIdx (the return value of createKeyToOldIdx) based on newStartVnode.key ## The index of the node idxInOld, and then find the same node. There are three situations here

If the same node is not found, create a new node through
• createElm

  and newStartIdx Move backward one position.

If a node is found and it matches
• sameVnode

  , then patchVnode will be performed on these two nodes and the old node at that location will be assigned a value. undefined (If there is a new node with the same key as the node later, it can be detected and prompted to have a duplicate key), and insert newStartVnode.elm into oldStartVnode.elm in front. In the same way, newStartIdx moves one position backward.

If it does not match
• sameVnode

  , you can only create a new node and insert it into parentElm Among the child nodes of , newStartIdx moves back one position.

Add and delete nodes

The last step is easy, when

while

After the loop ends, if oldStartIdx > oldEndIdx, it means that the old nodes have been compared, but there are still many new nodes. The new nodes need to be inserted into the real DOM and call addVnodes Just insert these nodes.

Similarly, if the condition of

newStartIdx > newEndIdx

is met, it means that the new node comparison is completed and there are still many old nodes. These useless old nodes Nodes can be deleted in batches through removeVnodes.

Summary

Diff algorithm is a comparison algorithm

. Compare the two old virtual DOM and new virtual DOM, compare which virtual node has changed, find this virtual node, and update only this virtual The real node corresponding to the node, instead of updating other nodes whose data has not changed, achieves accuratelyupdating the real DOM, thereby improving efficiency and performance.

Accuracy

is mainly reflected in the fact that the diff algorithm first finds reusable nodes, and then moves them to the correct position. When the element is not found, create a new node.

Extension

Why do you need to use key in vue and what is its role?

key

is the only mark of vnode in Vue, through this key, diff Operations can be more accurate and faster.

is more accurate: because with

key
1. it is not reused in place, in sameNode function a.key === b.key In-place reuse can be avoided during comparison. So it will be more accurate. Faster: Use the uniqueness of
key
2. to generate a map object to obtain the corresponding node, which is faster than the traversal method.

Why is it not recommended to use index as key

Use it when our list only involves display and does not involve sorting, deletion, and addition## There is no problem with #index

as

key. Because the index at this time is unique on each element. But if it involves sorting, deleting, or adding, you can no longer use index

as the

key, because the key of each element does not No more unique. It is not a unique key and does not help the diff algorithm. Writing it is the same as not writing it.

(Learning video sharing: web front-end development, Basic programming video)

The above is the detailed content of In-depth understanding of VNode and diff algorithm in vue2. For more information, please follow other related articles on the PHP Chinese website!