In-depth analysis of the principle of diff algorithm in vue2.x

The diff algorithm is an efficient algorithm that compares tree nodes at the same level, avoiding the need to search and traverse the tree layer by layer. This article will give you an in-depth analysis of the principles of the diff algorithm in vue2.x. I hope it will be helpful to you!

I have read a lot of source code analysis articles and read the source code at least twice. After all, I still want to write it myself as a kind of record and study for myself. Focus on the comments and summary, don’t worry too much about the rest, you will gain more by comparing the summary with the source code review process and comments

Definition of the update method

After the render function is generated, the mounting method will be called, and diff calculation will be performed during mounting. During initialization, since there is no old virtual node, the real dom node will be compared with the virtual node for the first time. For comparison, since the virtual node is not a native node, a replacement operation will be performed for the first time. (Learning video sharing: vue video tutorial)

// /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
    const restoreActiveInstance = setActiveInstance(vm)
    vm._vnode = vnode // 当前render函数产生的虚拟节点,保存后以便下次做对比
    if (!prevVnode) {
      vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false) //初次渲染
    } else {
      vm.$el = vm.__patch__(prevVnode, vnode)
    }
   ...
  }

The two main branches of the diff algorithm

The main body will have two major branches: front and rear virtual The nodes are consistent, but the front and back virtual nodes are inconsistent

// /src/core/vdom/patch.js
export function createPatchFunction (backend) {
  ...
  return function patch (oldVnode, vnode, hydrating, removeOnly) {
    ...
      if (!isRealElement && sameVnode(oldVnode, vnode)) {
        ...// 前后虚拟节点一致的方法
      } else {
        ...// 前后虚拟节点不一致的方法
      }
  }
}

The front and back virtual nodes are inconsistent

It is divided into three steps: 1. Create a new node, 2. Update the parent placeholder Node, 3. Delete the old node
When the component is mounted for the first time, the two are different. Later, it will be judged that if it is a real dom, it will be converted into a virtual node and replaced

if (isRealElement) {
  ...
  //需要diff 所以将第一次的真实节点转换成虚拟节点
  oldVnode = emptyNodeAt(oldVnode) //<div id="app"></div>
}
// 拿到父类的dom节点
const oldElm = oldVnode.elm //app
const parentElm = nodeOps.parentNode(oldElm) // body
//创建新dom节点 内部包含组件逻辑
createElm(
  vnode,
  insertedVnodeQueue,
  oldElm._leaveCb ? null : parentElm,
  nodeOps.nextSibling(oldElm)
)
//更新父的占位符节点 (组件更新相关)
if (isDef(vnode.parent)) {
  // 在生成render函数时会生成占位符节点<Dialog>提示</Dialog> => <div>提示</div> <Dialog></Dialog>就是占位符节点
  let ancestor = vnode.parent
  // 判断是否可挂载
  const patchable = isPatchable(vnode)
  while (ancestor) {
    for (let i = 0; i < cbs.destroy.length; ++i) {
      cbs.destroy[i](ancestor)
    }
    //更新父占位符的element
    ancestor.elm = vnode.elm
    if (patchable) {
      ...
    } else {
      registerRef(ancestor)
    }
    ancestor = ancestor.parent
  }
}
// 删除旧节点
if (isDef(parentElm)) {
  removeVnodes([oldVnode], 0, 0)
} else if (isDef(oldVnode.tag)) {
  invokeDestroyHook(oldVnode)
}

The front and rear virtual nodes are consistent

• First determine whether the new node is text, if so, set the text directly, if not, continue to determine
• The new and old nodes have children, in-depth comparison (Key points)
• The new node has children, but the old node does not, so add new nodes in a loop
• The new node does not have children, but the old node has children, delete the old node directly

function patchVnode (oldVnode,vnode,insertedVnodeQueue,ownerArray,index,removeOnly) {
    const elm = vnode.elm = oldVnode.elm

    let i
    const data = vnode.data 
    // 是组件vnode,在组件更新会调用组件的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)
    }
    // 是否是text
    if (isUndef(vnode.text)) {
      // 新旧节点都有children
      if (isDef(oldCh) && isDef(ch)) {
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
      // 新有 老没有 children 循环创建新节点
      } else if (isDef(ch)) {
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, &#39;&#39;)
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      // 新没有 老有 children 直接删除老节点
      } else if (isDef(oldCh)) {
        removeVnodes(oldCh, 0, oldCh.length - 1)
      // 新老都没有 children 老的是文本 就置为空
      } else if (isDef(oldVnode.text)) {
        nodeOps.setTextContent(elm, &#39;&#39;)
      }
    // 是text 直接设置文本
    } 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)
    }
  }

Comparison of old and new nodes with children

// /src/core/vdom/patch.js
 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
    // 满足新节点开始索引小于新节点结束索引,旧节点开始索引小于旧节点结束索引
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) { // 是否定义老节点开始元素
        oldStartVnode = oldCh[++oldStartIdx]
      } else if (isUndef(oldEndVnode)) {// 是否定义老节点结束元素
        oldEndVnode = oldCh[--oldEndIdx]
        // 头(旧节点开始元素)头(新节点开始元素)对比 例如四个li,末尾新增一个li,这种情况头头对比性能高
      } else if (sameVnode(oldStartVnode, newStartVnode)) { // sameVnode判断key和tag是否相同
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) { // 尾尾对比 例如四个li,头部新增一个li,这种情况尾尾对比性能高
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) {// 头尾对比 节点反转优化 reverse
        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)) { // 尾头对比
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else { // 乱序对比(核心diff,其他方式为优化)
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
        if (isUndef(idxInOld)) {
          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 {
            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)
    }
  }

Notes

• key cannot use index in some cases, because the index before and after the change is the same Yes, when adding an element to the head, if you use the index as the key, an update error will occur. Vue will understand it as adding an element at the end (because the keys before and after are all 0)
• In various comparisons In this case, as long as the two are found to be the same, the children
• will be recursively compared. In the out-of-order comparison, the key plays a great role. Without a key, update errors will occur, and the reuse effect cannot be achieved.
• The diff comparison isdepth first, same layer comparison

Summary

When mounting, the template will be updated after going through the diff algorithm. For the first time, the real dom node will be compared with the generated virtual node, and the generated virtual node will be stored for subsequent updates and comparisons. The diff algorithm only needs to be divided into two branches, the front and rear virtual nodes are consistent and the front and rear virtual nodes are inconsistent. When the front and rear virtual nodes are inconsistent, a new node will be created, the parent placeholder will be updated, and the old node will be deleted. If the old node is a real node, convert it to a virtual node, get the parent node of the old node and replace the old node. When the front and rear virtual nodes are consistent, it will first determine whether the new node is text, and if the value is added directly, if not compare the attributes first, and then determine if the new node has children and the old node has no children, the new node children will be added directly. If the new node has children, the new node will be added directly. If the node does not exist but the old node does, the children of the old node will be removed. If the old and new nodes have children, double pointers will be used to compare the same layer, through head-to-head comparison, tail-to-tail comparison, head-to-tail comparison, tail-to-head comparison, and out-of-order comparison. Continuously iteratively judge and update them to maximize the use of old nodes. If there are redundant new nodes, they will be added, and redundant old nodes will be deleted. Finally, the compared virtual nodes will be returned and stored as the next time Old node to compare to.

• Head-to-head comparison
  If the new and old starting elements are the same vnode, recursively call the patchVnode method for deep comparison, and then move the index to the next element
• Tail-to-tail comparison
  If the old and new end elements are the same vnode, recursively call the patchVnode method for deep comparison, and then move the index to the previous element
• Head-to-tail comparison
  Compare the start element of the old node with the old node Compare the tail elements. If the same, call the patchVnode method recursively for deep comparison. Then move the old node element to the end, move the head pointer of the old node to the next one, and move the tail pointer of the new node to the previous one. For example, old: A, B, C, new: C, B, A. For the first comparison, move the old A to the back of C
• tail and head comparison
  Move the tail element of the old node to the start element of the old node For comparison, call the patchVnode method recursively for deep comparison. Then move the old node element to the front, move the tail pointer of the old node to the previous one, and move the head pointer of the new node to the next one. For example, old: A, B, C, new: C, B, A, D. For the first comparison, the old C is moved to the front of A.
• Out-of-order comparison
  will be based on the key and correspondence before comparison. The index of the old node will be generated into the mapping table. During out-of-order comparison, the current key will be used to find the key of the old node. If it can be reused, the node will be moved to the beginning of the old node and the children will be compared recursively. If it cannot be reused, a new one will be created and inserted into the old one. at the beginning of the node. Then move the new index to the next element

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

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