Vue diff算法

在 vue 中会维护一个和 DOM 节点对应的 vnode 对象

vnode 的 children 数组中对应子节点的 vnode 对象，所以在 vue 中通过 vnode 和真实的 DOM 树进行映射，我们也称之为虚拟树。

正是有了虚拟树，当数据更新时。我们可以对比新数据构建的 vnode 和老数据构建的 oldVnode 的差异，来实现精准更新。

而我们对比差异的算法就是采用的 diff。

通过 diff 对比虚拟树的差异，将差异通过打补丁（patch）的方式更新到对应的真实 DOM 节点上。

patch函数

由上就可以知道patch函数是 diff 流程的入口函数

首先我们要知道，patch会先在页面渲染的时候加载一次，然后就在vnode改变的时候调用。

  1. // 首次渲染是DOM元素，后面是vnode
  2. function patch (oldVnode: VNode | Element, vnode: VNode): VNode {
  3.     let i: number, elm: Node, parent: Node
  4.     const insertedVnodeQueue: VNodeQueue = []
  5.     for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]()
  7.     // 不是一个vnode就创建一个空的vnode并关联在DOM元素上
  8.     if (!isVnode(oldVnode)) {
  9.       // 创建一个空的vnode，并关联DOM元素
  10.       oldVnode = emptyNodeAt(oldVnode)
  11.     }
  13.     if (sameVnode(oldVnode, vnode)) {
  14.       // key、tag相同，说明是同一个vnode
  15.       patchVnode(oldVnode, vnode, insertedVnodeQueue)
  16.     } else {
  17.       // key、tag不相同，说明是不同的vnode
  18.       elm = oldVnode.elm!
  19.       parent = api.parentNode(elm) as Node
  21.       // 创建新的DOM元素
  22.       createElm(vnode, insertedVnodeQueue)
  24.       if (parent !== null) {
  25.         // 插入新的DOM元素
  26.         api.insertBefore(parent, vnode.elm!, api.nextSibling(elm))
  27.         // 移除老的DOM元素
  28.         removeVnodes(parent, [oldVnode], 0, 0)
  29.       }
  30.     }
  31.     return vnode
  32.   }

61Vue diff算法源码浅析 - 图1

整个逻辑就如下：

如果两个节点都是一样的，那么就深入检查他们的子节点。如果两个节点不一样那就说明Vnode完全被改变了，就可以直接替换oldVnode。

  1. // 判断新旧节点是否一样
  2. function sameVnode (a, b) {
  3.   return (
  4.     a.key === b.key &&  // key值
  5.     a.tag === b.tag &&  // 标签名
  6.     a.isComment === b.isComment &&  // 是否为注释节点
  7.     // 是否都定义了data，data包含一些具体信息，例如onclick , style
  8.     isDef(a.data) === isDef(b.data) &&  
  9.     sameInputType(a, b) // 当标签是<input>的时候，type必须相同
  10.   )
  11. }

从代码中可以看到，会判断新旧vnode的 key , tag等是否相等，如果相等就是同一个vnode.

patchVnode

如果2个节点是一样的，就会进入patchVnode的方法，判断他的子节点和文本节点。这里也就是对可复用节点进行打补丁，也就是派发更新。

  1.   function patchVnode (oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
  2.        ...
  3.     // vonde为新的vnode oldvnnode为老的vnode
  4.     // 设置vnode关联的DOM元素 
  5.     const elm = vnode.elm = oldVnode.elm!
  7.     // 老children
  8.     const oldCh = oldVnode.children as VNode[]
  10.     // 新children
  11.     const ch = vnode.children as VNode[]
  13.     if (oldVnode === vnode) return
  14.     ...
  15.     // 新vnode 无text 有children
  16.     if (isUndef(vnode.text)) {
  17.       // 新vnode 有children 老vnode 有chidren
  18.       if (isDef(oldCh) && isDef(ch)) {
  19.         if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue)
  20.       // 新vnode 有children 旧vnode 无children 有text
  21.       } else if (isDef(ch)) {
  22.         // 清空text
  23.         if (isDef(oldVnode.text)) api.setTextContent(elm, '')
  24.         // 添加children
  25.         addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
  27.       // 新vnode 无children 旧vnode 有children
  28.       } else if (isDef(oldCh)) {
  29.         // 移除children
  30.         removeVnodes(elm, oldCh, 0, oldCh.length - 1)
  32.       // 老vnode 有text
  33.       } else if (isDef(oldVnode.text)) {
  34.         // 清空text
  35.         api.setTextContent(elm, '')
  36.       }
  37.     // 新vnode 有text 无children
  38.     // 老vnode text 不等于 新vnode text
  39.     } else if (oldVnode.text !== vnode.text) {
  40.       // 老vnode 有children
  41.       if (isDef(oldCh)) {
  42.         // 移除老vnode children
  43.         removeVnodes(elm, oldCh, 0, oldCh.length - 1)
  44.       }
  45.       // 设置新vnode text
  46.       api.setTextContent(elm, vnode.text!)
  47.     }
  48.     hook?.postpatch?.(oldVnode, vnode)
  49.   }

patchVnode函数的逻辑：

  1. 找到对应的 DOM 节点 elm，并且赋值给新的vnode.elm
  2. 判断新节点类型（vnode.text），如果是文本节点，更新 elm 文本即可
  3. 非文本节点下，判断新老节点的子节点
  4. 如果新老节点都有子节点，走子节点的同层比较流程 updateChildren
  5. 如果只有新节点有子节点，直接使用 addVnodes 为 elm 添加子节点（先删除文本）
  6. 如果只有旧节点有子节点，使用 removeVnodes 移除即可
  7. 如果都没有子节点，判断旧数据是否有文本节点，有则清空。

updateChildren

  1.  function updateChildren (parentElm: Node,
  2.     oldCh: VNode[],
  3.     newCh: VNode[],
  4.     insertedVnodeQueue: VNodeQueue) {
  5.     let oldStartIdx = 0
  6.     let newStartIdx = 0
  7.     let oldEndIdx = oldCh.length - 1
  8.     let oldStartVnode = oldCh[0]
  9.     let oldEndVnode = oldCh[oldEndIdx]
  10.     let newEndIdx = newCh.length - 1
  11.     let newStartVnode = newCh[0]
  12.     let newEndVnode = newCh[newEndIdx]
  13.     let oldKeyToIdx: KeyToIndexMap | undefined
  14.     let idxInOld: number
  15.     let elmToMove: VNode
  16.     let before: any
  18.     while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  19.       if (oldStartVnode == null) {
  20.         oldStartVnode = oldCh[++oldStartIdx] // Vnode might have been moved left
  21.       } else if (oldEndVnode == null) {
  22.         oldEndVnode = oldCh[--oldEndIdx]
  23.       } else if (newStartVnode == null) {
  24.         newStartVnode = newCh[++newStartIdx]
  25.       } else if (newEndVnode == null) {
  26.         newEndVnode = newCh[--newEndIdx]
  28.       // 老开始和新开始对比
  29.       } else if (sameVnode(oldStartVnode, newStartVnode)) {
  30.         patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
  31.         oldStartVnode = oldCh[++oldStartIdx]
  32.         newStartVnode = newCh[++newStartIdx]
  34.       // 老结束和新结束对比
  35.       } else if (sameVnode(oldEndVnode, newEndVnode)) {
  36.         patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
  37.         oldEndVnode = oldCh[--oldEndIdx]
  38.         newEndVnode = newCh[--newEndIdx]
  40.       // 老开始和新结束对比
  41.       } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
  42.         patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
  43.         api.insertBefore(parentElm, oldStartVnode.elm!, api.nextSibling(oldEndVnode.elm!))
  44.         oldStartVnode = oldCh[++oldStartIdx]
  45.         newEndVnode = newCh[--newEndIdx]
  47.       // 老结束和新开始对比
  48.       } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
  49.         patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
  50.         api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!)
  51.         oldEndVnode = oldCh[--oldEndIdx]
  52.         newStartVnode = newCh[++newStartIdx]
  54.       // 以上四种情况都没有命中
  55.       } else {
  56.         if (oldKeyToIdx === undefined) {
  57.           oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
  58.         }
  60.         // 拿到新开始的key，在老children里去找有没有某个节点有对应这个key
  61.         idxInOld = oldKeyToIdx[newStartVnode.key as string]
  62.         // 没有在老children里找到对应的
  63.         if (isUndef(idxInOld)) { // New element
  64.           api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!)
  66.         // 在老children里找到了对应的
  67.         } else {
  68.           // 找到了对应key的元素（key相等）
  69.           elmToMove = oldCh[idxInOld]
  71.           // key相等 判断tag是否相等
  72.           if (elmToMove.sel !== newStartVnode.sel) {
  73.             // key相等 tag不相等
  74.             api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!)
  75.           } else {
  76.             // key相等 tag相等
  77.             patchVnode(elmToMove, newStartVnode, insertedVnodeQueue)
  78.             oldCh[idxInOld] = undefined as any
  79.             api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!)
  80.           }
  81.         }
  82.         newStartVnode = newCh[++newStartIdx]
  83.       }
  84.     }
  85.     if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
  86.       if (oldStartIdx > oldEndIdx) {
  87.         before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm
  88.         addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
  89.       } else {
  90.         removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
  91.       }
  92.     }
  93.   }

61Vue diff算法源码浅析 - 图2

从图中可以看到 会有四个指针（oldStartVnode,oldEndVnode, newStartVnode, newEndVnode）分别指向，新老children节点的头尾。

判断逻辑是这样的。

第一步：判断（oldStartVnode, newStartVnode）他俩指正指的vnode是否匹配上了，如果匹配上了，oldStartVnode，newStartVnode指针向右移动，真实DOM的位置不变。
第二步：(oldEndVnode, newEndVnode) 他俩是否匹配上了，如果匹配上了，oldEndVnode, newEndVnode指针向左移动，真实DOM的位置不变。

第三步：(oldStartVnode, newEndVnode)判断是否匹配上了，如果匹配上了那么真实DOM中的第一个节点会移到最后

第四步：(oldEndVnode, newStartVnode)判断匹配上了，如果匹配上了那么真实DOM中的最后一个节点会移到最前，匹配上的两个指针向中间移动。

第五步：如果四种匹配没有一对是成功的，分为两种情况

  • 如果新旧子节点都存在key，那么会根据oldChild的key生成一张hash表，用newStartVnode的key与hash表做匹配，匹配成功就判断newStartVnode和匹配节点是否为sameNode，如果是，就在真实DOM中将成功的节点移到最前面，否则，将newStartVnode生成对应的节点插入到DOM中对应的oldS位置，newStartVnode指针向中间移动，被匹配old中的节点置为null。
  • 如果没有key,则直接将newStartVnode生成新的节点插入真实DOM（ps：这下可以解释为什么v-for的时候需要设置key了，如果没有key那么就只会做四种匹配，就算指针中间有可复用的节点都不能被复用了）

参考文章

详解vue的diff算法 (juejin.cn)