一、Vue2

1、updateChildren（diff核心）

**双端diff算法**：从两边开始分别向中间对比的算法。

QQ图片20240426173236.png

新旧头相等
新旧尾相等
旧头等于新尾
旧尾等于新头
四者互不相等

举例，预设以下新旧节点数组：

作为初始节点顺序的旧节点数组oldChildren，包含1-7共7个节点
作为乱序后的新节点数组newChildren，也有 7 个节点，但是相比旧节点减少了一个 vnode3 并增加了一个 vnode8

（1）预设新旧节点状态

在比较前，定义两组节点的双端索引：

// 其中 oldCh 为 oldChildren，newCh 为 newChildren
let oldStartIdx = 0
let oldEndIdx = oldCh.length - 1
let oldStartVnode = oldCh[0]
let oldEndVnode = oldCh[oldEndIdx]

let newStartIdx = 0
let newEndIdx = newCh.length - 1
let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]

然后，定义遍历停止条件：

whild(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx)

这里停止条件是只要新旧节点有一个遍历结束，就停止遍历。
此时节点状态如下：

step 1.png

（2）确认Vnode存在才进行比较

为了保证新旧节点不会进行无效对比，会首先排除旧节点数组起始部分与末尾部分连续且值为Undefined的数据。

if (isUndef(oldStartVnode)) {
  oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
} else if (isUndef(oldEndVnode)) {
  oldEndVnode = oldCh[--oldEndIdx]
}

step 2.webp

（3）旧头等于新头

此时新旧节点数组的两个起始索引指向的节点基本是一致的，那么此时会调用pacthVnode对两个vnode进行深层次比较和dom更新，并将两个起始索引向后移动。

if (sameVnode(oldStartVnode, newStartVnode)) {
  patchVnode(
    oldStartVnode,
    newStartVnode,
    insertedVnodeQueue,
    newCh,
    newStartIdx
  )
  oldStartVnode = oldCh[++oldStartIdx]
  newStartVnode = newCh[++newStartIdx]
}

此时节点和索引的变化如图所示：

step 2-3.webp

（4）旧尾等于新尾

与头节点相等类似。这种情况代表新旧节点数组的最后一个节点基本一致，此时调用patchVnode比较两个尾结点和更新dom，然后将两个末尾节点向前移动。

if (sameVnode(oldEndVnode, newEndVnode)) {
  patchVnode(
    oldEndVnode,
    newEndVnode,
    insertedVnodeQueue,
    newCh,
    newEndIdx
  )
  oldEndVnode = oldCh[--oldEndIdx]
  newEndVnode = newCh[--newEndIdx]
}

此时节点和索引的变化如图所示：

step 2-4.webp

（5）旧头等于新尾

这里表示旧节点数组当前起始索引指向的vnode与新节点数组当前末尾索引指向的vnode基本一致，一样调用patchVnode对两个节点进行处理。
但是与上面两种有区别在于：这种情况会造成节点的移动，所以此时会在patchVnode结束后调用nodeOps.insertBefore将旧的头结点重新插入到当前旧的尾结点之后。
然后，会将旧节点的起始索引后移、新节点的尾索引前移。

看到这里大家可能会有一个疑问，为什么这里移动的是 旧的节点数组，这里因为 vnode 节点中有一个属性 elm，会指向该 vnode 对应的实际 dom 节点，所以这里移动旧节点数组其实就是 侧面去移动实际的 dom 节点顺序；并且注意这里是 当前的尾结点，在索引改变之后，这里不一定就是原旧节点数组的最末尾。

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

此时状态如下：

step 2-5.webp

（6）旧尾等于新头

这里与上面旧头等于新尾相似，一样设计节点对比和移动，只是调整的索引不同。此时旧节点的末索引前移、新节点的起始索引后移，dom移动对应的vnode操作是将旧节点的末尾索引对应的vnode插入到旧节点数组起始索引对应的vnode之前。

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

此时状态如下：
step 2-6.webp

（7）四者皆不相等

在以上情况都处理之后，就来到了四个节点互相都不相等的情况，这种情况也是 最复杂的情况。
当经过了上面几种处理之后，此时的 索引与对应的 vnode 状态如下：
step 2-7.webp
可以看到四个索引对应的 vnode 分别是：vnode 3、vnode 5、 vnode 4、vnode 8，这几个肯定是不一样的。
此时也就意味着 双端对比结束。
后面的节点对比则是将旧节点数组剩余的vnode（oldStartIdx到oldEndIdx之间的节点）进行一次遍历，生成由vnode.key作为键，idx索引作为值的对象oldKeyToIdx，然后遍历新节点数组的剩余vnode（newStartIdx 到 newEndIdx 之间的节点），根据新的节点的key在oldKeyToIdx进行查找。此时的每个新节点的查找结果只有两种情况：

找到了对应的索引，那么会用过patchVnode对两个节点进行对比：
1. 相同节点，调用 patchVnode 进行深层对比和 dom 更新，将 oldKeyToIdx 中对应的索引 idxInOld 对应的节点插入到 oldStartIdx 对应的 vnode 之前；并且，这里会将 **旧节点数组中 idxInOld 对应的元素设置为 **undefined
2. 不同节点，则直接createElm创建新的dom节点并将新的vnode插入到对应位置
没有找到对应的索引，则直接createElm创建新的dom节点并将新的vnode插入到对应位置

注：这里 只有找到了旧节点并且新旧节点一样才会将旧节点数组中 idxInOld 中的元素置为 undefined。

最后，会将 新节点数组的起始索引向后移动。

if (isUndef(oldKeyToIdx))
  oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
idxInOld = isDef(newStartVnode.key)
  ? oldKeyToIdx[newStartVnode.key]
  : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
  // 1、没找到
if (isUndef(idxInOld)) {
  // New element
  createElm(
    newStartVnode,
    insertedVnodeQueue,
    parentElm,
    oldStartVnode.elm,
    false,
    newCh,
    newStartIdx
  )
} else {
  // 2、找到
  vnodeToMove = oldCh[idxInOld]
  // 找到了对应的索引，那么会通过 sameVnode 对两个节点进行对比
  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]

大致逻辑如图：

（8）剩余元素处理（循环外处理）

经过上面的处理之后，根据判断条件也不难看出，遍历结束之后新旧节点数组都刚好没有剩余元素 是很难出现的，当且仅当遍历过程中每次新头尾节点总能和旧头尾节点中总能有两个新旧节点相同时才会发生，只要有一个节点发生改变或者顺序发生大幅调整，最后 都会有一个节点数组起始索引和末尾索引无法闭合。
那么此时就需要对剩余元素进行处理：

旧节点数组遍历结束、新节点数组仍有剩余，则遍历新节点数组剩余数据，分别创建节点并插入到旧末尾索引对应节点之前
新节点数组遍历结束、旧节点数组仍有剩余，则遍历旧节点数组剩余数据，分别从节点数组和 dom 树中移除

即：
step 3.webp

小结

Vue 2 的 diff 算法相对于简单 diff 算法来说，通过 双端对比与生成索引 map 两种方式 减少了简单算法中的多次循环操作，新旧数组均只需要进行一次遍历即可将所有节点进行对比。
其中双端对比会分别进行四次对比和移动，性能不算最优解，所以 Vue 3 中引入了 最长递增子序列 的方式来 替代双端对比，而其余部分则依然通过转为索引map 的形式利用空间扩展来减少时间复杂度，从而更高的提升计算性能。
当然本文的图中没有给出 vnode 对应的 elm 真实 dom 节点，两者的移动关系可能会给大家带来误解，建议配合《Vue.js 设计与实现》一起阅读。
整体流程如下：

二、Vue3

待补充...

Vue diff算法