Vue3源码解读-快速Diff算法

1、前言

Vue的Diff算法是用来比较虚拟DOM和实在DOM的差异，并将差异运用到实在DOM上，以完结高效的更新。Diff算法主要包含三个过程：树的遍历、节点的比较和差异的运用。

在树的遍历进程中，Diff算法会递归地遍历虚拟DOM树和实在DOM树，并比较它们的节点。这个进程是从根节点开端，逐层向下遍历，经过比较节点的标签、特点、子节点等信息，来确认是否有差异存在。

节点的比较是Diff算法的中心部分，它会对虚拟DOM和实在DOM的节点进行详细的比较。在比较进程中，会考虑节点的类型、标签、特点等方面的差异，并将这些差异记录下来。

差异的运用是将记录下来的差异运用到实在DOM上，以完结对DOM的更新。这个进程是经过操作实在DOM的API来完结的，比方增加、删去、修改节点等操作。

经过这些过程，Vue的Diff算法可以精确、快速地更新DOM，提高运用的功能和用户体会。它可以最小化DOM的操作，只对有差异的部分进行更新，防止不必要的重绘和重排，然后提高页面的渲染功率。

2、流程概述

Vue3源码解读-快速Diff算法

3、源码详解

3.1 patchChildren函数

patchChildren函数源码

当组件更新的时分会走到patchChildren函数，以下是patchChildren的函数的详细完结：

const patchChildren: PatchChildrenFn = (...) => {
    // 取一哈新旧虚拟节点的子节点
    const c1 = n1 && n1.children
    const prevShapeFlag = n1 ? n1.shapeFlag : 0
    const c2 = n2.children
    const { patchFlag, shapeFlag } = n2
    if (patchFlag > 0) {
      // patchFlag > 0 就表示子节点含有动态特点，如：动态style、动态class、动态案牍等
      if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
        // 子节点带 key
        patchKeyedChildren(...)
        return
      } else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
        // 子节点不带 key
        patchUnkeyedChildren(...)
        return
      }
    }
    // 子节点存在3种可能的状况：文本、数组、没有子节点
    if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
      // 新虚拟节点的子节点是文本
      if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
        // 对应的旧虚拟节点的子节点是数组
        // 卸载旧虚拟节点的数组子节点
        unmountChildren(c1 as VNode[], parentComponent, parentSuspense)
      }
      // 再挂载新虚拟节点的文簿本节点
      if (c2 !== c1) {
        hostSetElementText(container, c2 as string)
      }
    } else {
      if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
        // 旧虚拟节点的子节点是数组
        if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
          // 新虚拟节点的子节点也是数组，做全量diff
          patchKeyedChildren(...)
        } else {
          // 能走到这就阐明新虚拟节点没有子节点，这儿只需求卸载久虚拟节点的子节点
          unmountChildren(c1 as VNode[], parentComponent, parentSuspense, true)
        }
      } else {
        // 走到这就阐明
        // 旧虚拟节点的子节点要么是文本要么也没有子节点
        // 新虚拟节点的子节点要么是数组要么就没有子节点
        if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
          // 旧虚拟节点的子节点是文本，更新
          hostSetElementText(container, '')
        }
        if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
          // 新虚拟节点的子节点是数组，挂载
          mountChildren(...)
        }
      }
    }
  }

从patchChildren函数的源码中咱们可以知道，Vue3在比较新旧两组子节点的时分会选用以下两种方法处理：

  • 假如新的子节点没有key特点，那么就会调用patchUnkeyedChildren函数来对新旧两组子节点进行Diff比较；
  • 假如新的子节点没有key特点，那么就会调用patchkeyedChildren函数来对新旧两组子节点进行Diff比较；

那么，patchUnkeyedChildren和patchkeyedChildren函数处理节点有什么区别呢？咱们接着往下看。

3.2 patchUnkeyedChildren函数

假如新的子节点没有key特点，那么就会调用patchUnkeyedChildren函数来对新旧两组子节点进行Diff比较。该函数的代码如下所示：

patchUnkeyedChildren源码

// 没有 key 标识的子节点的 patch 进程，即 diff 进程
  const patchUnkeyedChildren = (
    c1: VNode[],
    c2: VNodeArrayChildren,
    container: RendererElement,
    anchor: RendererNode | null,
    parentComponent: ComponentInternalInstance | null,
    parentSuspense: SuspenseBoundary | null,
    isSVG: boolean,
    slotScopeIds: string[] | null,
    optimized: boolean
  ) => {
    // 旧子节点
    c1 = c1 || EMPTY_ARR
    // 新子节点
    c2 = c2 || EMPTY_ARR
    // 旧的一组子节点的长度
    const oldLength = c1.length
    // 新的一组子节点的长度
    const newLength = c2.length
    // 两组子节点的公共长度，即两者中较短的那一组子节点的长度
    const commonLength = Math.min(oldLength, newLength)
    let i
    // 遍历commonLength，调用patch函数进行更新
    for (i = 0; i < commonLength; i++) {
      const nextChild = (c2[i] = optimized
        ? cloneIfMounted(c2[i] as VNode)
        : normalizeVNode(c2[i]))
      patch(
        c1[i],
        nextChild,
        container,
        null,
        parentComponent,
        parentSuspense,
        isSVG,
        slotScopeIds,
        optimized
      )
    }
    // 假如旧的一组子节点的长度大于新的一组子节点的长度，阐明有旧的子节点需求卸载
    if (oldLength > newLength) {
      // remove old
      unmountChildren(
        c1,
        parentComponent,
        parentSuspense,
        true,
        false,
        commonLength
      )
    } else {
      // 阐明是有新子节点需求挂载
      // mount new
      mountChildren(
        c2,
        container,
        anchor,
        parentComponent,
        parentSuspense,
        isSVG,
        slotScopeIds,
        optimized,
        commonLength
      )
    }
  }

如上面代码所示，处理过程如下：

  1. 求新旧两组子节点各自的长度，然后求出两组子节点的公共长度commonLength；
  2. 遍历commonLength，调用patch函数进行更新；
  3. 公共长度内的子节点更新完毕，进行以下操作：
    1. 假如新的一组子节点的长度更长，阐明新的子节点需求挂载，调用mountChildren函数进行挂载；
    2. 不然阐明旧子节点需求卸载，调用unmount函数卸载旧节点；

3.3 patchKeyedChildren函数

假如新的子节点有key特点，那么就会调用patchkeyedChildren函数来对新旧两组子节点进行Diff比较。该函数的代码如下所示：

patchkeyedChildren源码

3.3.1 快速diff算法预处理过程

快速 Diff 算法包含预处理过程，这其实是借鉴了纯文本 Diff 算法的思路。快速diff算法的预处理是别离处理新旧节点中的前置节点和后置节点。

3.3.2 处理前置节点

前置节点节点处理

let i = 0
// 新的一组子节点的长度
const l2 = c2.length
// 旧子节点的尾部索引
let e1 = c1.length - 1 // prev ending index
// 新子节点的尾部索引
let e2 = l2 - 1 // next ending index
// 从头部开端同步，处理相同的同步节点
// 1. sync from start
// (a b) c
// (a b) d e
while (i <= e1 && i <= e2) {
  const n1 = c1[i]
  const n2 = (c2[i] = optimized
    ? cloneIfMounted(c2[i] as VNode)
    : normalizeVNode(c2[i]))
  if (isSameVNodeType(n1, n2)) {
    // 相同的节点，递归履行patch更新节点
    patch(
      n1,
      n2,
      container,
      null,
      parentComponent,
      parentSuspense,
      isSVG,
      slotScopeIds,
      optimized
    )
  } else {
    // 遇到了 key 不同的节点，那就直接退出循环，相同前置节点(a b)的更新处理完结
    break
  }
  i++
}

在这段代码中，咱们运用while循环查找一切相同的前置节点，并调用patch函数进行打补丁，直到遇到key值不同的节点停止。这样就完结了前置节点的更新。

Vue3源码解读-快速Diff算法

图1、前置节点处理

3.3.3 处理后置节点

后置节点处理

// 2. sync from end
// a (b c)
// d e (b c)
while (i <= e1 && i <= e2) {
  // 旧的后置节点
  const n1 = c1[e1]
  // 新的后置节点
  const n2 = (c2[e2] = optimized
    ? cloneIfMounted(c2[e2] as VNode)
    : normalizeVNode(c2[e2]))
  // 新旧后置节点相同，调用 patch 函数打补丁
  if (isSameVNodeType(n1, n2)) {
    patch(
      n1,
      n2,
      container,
      null,
      parentComponent,
      parentSuspense,
      isSVG,
      slotScopeIds,
      optimized
    )
  } else {
    // 遇到了 key 不同的节点，退出循环，相同后置节(b c)点的更新处理完结
    break
  }
  // 新旧后置节点索引递减，即从后往前遍历两组子节点
  e1--
  e2--
}

与处理前置节点相同，在while循环内，需求调用patch函数进行打补丁，然后递减两个索引e1、e2，直到遇到类型不同且key值不同的节点停止，这样就完结了后置节点的更新。当处理完后置节点后的状态如下图所示。

Vue3源码解读-快速Diff算法

图2、处理后置节点

3.3.4 处理新增节点

新增节点处理

当前置节点和后置节点处理完毕后，旧的一组子节点已经悉数被处理了，但是在新的一组子节点中，还留传了一个未被处理的节点p-4，这个节点是新增的节点。如何得出这个结论呢？咱们可以根据索引i、e1、e2之间的关系：

  • 条件一：e1 < i：阐明在预处理进程中，一切的旧节点都处理完毕了；
  • 条件二：e2 ≥ i：阐明在预处理进程中，在新的一组子节点中，依然有未被处理的节点，而这些留传的节点江北视为新增节点。

假如条件一和条件二一起建立，阐明在新的一组子节点中，存在留传节点，且这些节点都是新增节点。因而，咱们需求将它们挂载到正确的方位。

// 3. common sequence + mount
// (a b)
// (a b) c
// i = 2, e1 = 1, e2 = 2
// (a b)
// c (a b)
// i = 0, e1 = -1, e2 = 0
// i > e1 阐明在预处理的进程中，一切的旧子节点处理完毕额
if (i > e1) {
  // i <= e2 阐明在预处理往后，在新的一组子节点中，依然有未被处理的节点，这些留传的节点将被视作新增节点
  if (i <= e2) {
    // 锚点的索引
    const nextPos = e2 + 1
    // 锚点元素
    const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
    // 选用 while 循环，调用 patch 函数逐个挂载新增节点
    while (i <= e2) {
      patch(
        null,
        (c2[i] = optimized
          ? cloneIfMounted(c2[i] as VNode)
          : normalizeVNode(c2[i])),
        container,
        anchor,
        parentComponent,
        parentSuspense,
        isSVG,
        slotScopeIds,
        optimized
      )
      i++
    }
  }
}

在这段代码中：

  • 核算锚点的索引值（nextPos）为e2 + 1;
  • 假如小于新的一组子节点的数量，则阐明锚点元素在新的一组子节点中，直接运用(c2[nextPos] as VNode).el，不然阐明索引c2对应的节点已经是尾部节点了，这时锚点元素是parentAnchor；
  • 找到锚点元素后，运用一个while循环，将i和e2之间的节点作为新节点挂载；

如下图所示：

Vue3源码解读-快速Diff算法

图3、处理新增节点

3.3.5 处理删去节点

删去节点处理

当相同的前置节点和后置节点悉数被处理完毕后，新的一组子节点已经悉数被处理完毕，而就得一组子节点中留传了一个节点p-2，实践上，留传的节点可能有多个，如下图所示：

// 4. common sequence + unmount
// (a b) c
// (a b)
// i = 2, e1 = 2, e2 = 1
// a (b c)
// (b c)
// i = 0, e1 = 0, e2 = -1
else if (i > e2) {
  while (i <= e1) {
    unmount(c1[i], parentComponent, parentSuspense, true)
    i++
  }
}

在上面的源码中，当满意i > e2 && i ≤ e1时，则敞开一个while循环，并调用unmount函数将i到e1之间的节点悉数删去。 到这儿，根据抱负状况下，处理完前置节点和后置节点后，新旧两组子节点总有一组的子节点悉数被处理完毕。一切的操作只需求简单地更新、挂载、卸载节点即可。

Vue3源码解读-快速Diff算法

图4、处理删去节点

3.3.6 非抱负状况下的未处理节点

上面的给出比如都比较抱负化，当完结前置和后置节点的处理后，新旧两组子节点总会有一组子节点悉数被处理完毕，但有的状况比较杂乱。

下面咱们给出非抱负状况下的比如，经过上面的前置和后置处理后，新子节点和旧子节点都有未被处理的节点，如下图所示：

Vue3源码解读-快速Diff算法

图5、非抱负状况，处理完前置和后置节点的状态

在这种非抱负状况下，索引i、e1、e2不满意下面两个条件中的任何一个：

  • i > e1 && i < e2(新增节点的状况)
  • i > e2 && i < e1(卸载旧节点的状况)

咱们需求增加新的else分支来处理这种非抱负的状况，源码如下：

非抱负状况处理源码

第1步：构建索引表keyToNewIndexMap

给新子节点构建一张索引表keyToNewIndexMap，目的是用来存储节点key和节点方位的索引，可以在O(n)时间杂乱度下获取到旧节点，提高查找功能。构建keyToNewIndexMap索引表的源码如下：

构建索引表源码

// 预处理完后，未处理节点的第一个未处理节点的索引方位
const s1 = i // prev starting index
const s2 = i // next starting index
// 构建新的一组子节点中未处理的key和索引方位的映射，是为了解决功能问题
// 5.1 build key:index map for newChildren
const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
for (i = s2; i <= e2; i++) {
  const nextChild = (c2[i] = optimized
    ? cloneIfMounted(c2[i] as VNode)
    : normalizeVNode(c2[i]))
  if (nextChild.key != null) {
    if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {
      warn(
        `Duplicate keys found during update:`,
        JSON.stringify(nextChild.key),
        `Make sure keys are unique.`
      )
    }
    // 将新节点的key和索引方位增加到map调集中
    keyToNewIndexMap.set(nextChild.key, i)
  }
}

Vue3源码解读-快速Diff算法

图6、构建keyToNewIndexMap索引表

第2步：构建newIndexToOldIndexMap数组

为了在后面快速找到需求移动的节点，需求构建newIndexToOldIndexMap数组，它的长度等于经过预处理后未处理的新子点数量，并且初始值都是0。其源码如下：

构建newIndexToOldIndexMap数组源码

let j
// 代表更新过节点数量
let patched = 0
// 新的一组节点中剩下未处理节点的数量
const toBePatched = e2 - s2 + 1
// 标识节点是否需求移动节点
let moved = false
// 代表遍历旧的一组子节点的进程中遇到的最大索引值
// used to track whether any node has moved
let maxNewIndexSoFar = 0
// 构建一个索引映射数组，存储新的一组子节点在旧的一组子节点的方位索引（存储的是新的一组子节点中的节点在旧的一组子节点中的方位索引）
// works as Map<newIndex, oldIndex>
// Note that oldIndex is offset by +1
// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// used for determining longest stable subsequence
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0

第3步：填充newIndexToOldIndexMap数组

填充的目的是将newIndexToOldIndexMap数组中的元素存储的是新的一组子节点中的节点在旧的一组子节点中的方位索引。

填充newIndexToOldIndexMap数组

// 遍历旧的一组子节点中剩下未处理的节点
for (i = s1; i <= e1; i++) {
  // 旧数组中剩下未处理的节点
  const prevChild = c1[i]
  // 假如更新过的节点数量大于需求更新的节点数量，则卸载剩下的节点
  if (patched >= toBePatched) {
    // all new children have been patched so this can only be a removal
    unmount(prevChild, parentComponent, parentSuspense, true)
    continue
  }
  // 新的一组子节点中未被处理节点在新子节点中的方位索引
  let newIndex
  if (prevChild.key != null) {
    // 从索引表中获取与旧节点具有相同key的新节点在新的一组子节点中的方位索引
    newIndex = keyToNewIndexMap.get(prevChild.key)
  } else {
    // 旧子节点没有 key ，那么尝试在新的一组子节点中查找具有相同类型的没有key的新子节点
    // key-less node, try to locate a key-less node of the same type
    for (j = s2; j <= e2; j++) {
      if (
        newIndexToOldIndexMap[j - s2] === 0 &&
        isSameVNodeType(prevChild, c2[j] as VNode)
      ) {
        newIndex = j
        break
      }
    }
  }
  // 假如在新的一组子节点中没有找到与旧的一组子节点中具有相同key 或相同类型的子节点，
  // 阐明该旧子节点在新的一组子节点中已经不存在了，需求将其卸载
  if (newIndex === undefined) {
    unmount(prevChild, parentComponent, parentSuspense, true)
  } else {
    // 填充 索引映射数组
    newIndexToOldIndexMap[newIndex - s2] = i + 1
    // 经过比较 newIndex 和 maxNewIndexSoFar 的值来判别节点是否需求移动
    if (newIndex >= maxNewIndexSoFar) {
      // 假如在遍历进程中遇到的索引值出现递加趋势，则阐明不需求移动节点
      maxNewIndexSoFar = newIndex
    } else {
      // 不然需求移动
      moved = true
    }
    // 调用patch函数完结更新
    patch(
      prevChild,
      c2[newIndex] as VNode,
      container,
      null,
      parentComponent,
      parentSuspense,
      isSVG,
      slotScopeIds,
      optimized
    )
    // 每更新一个节点，都将patched变量+1
    patched++
  }
}

上面的源码解析如下：

  1. 运用for循环遍历旧子节点，在遍历进程假如发现已经更新的节点数量patched大于需求更新的节点数量toBePatched，则调用unmount将剩下的旧节点悉数卸载掉；
  2. 拿旧节点的key值去索引表keyToNewIndexMap去查找该节点在新节点中的方位newIndex;
  3. 假如newIndex不存在，则阐明该节点在新节点已经不存在，则调用unmount函数卸载它；
  4. 假如newIndex存在，则阐明该节点在新节点中存在，则调用patch函数更新打补丁，并填充newIndexToOldIndexMap数组；

在这段代码中，增加了两个变量moved和maxNewIndexSoFar变量，其间，moved的初始值是false，代表是否需求移动节点，maxNewIndexSoFar初始值为0，代表遍历旧节点进程中遇到的最大索引值。假如在遍历进程中遇到的索引值呈递加趋势，则不需求移动节点，不然就需求移动节点。

Vue3源码解读-快速Diff算法

图7、构建newIndexToOldIndexMap数组

第4步：判别节点是否需求移动

4.1 核算最长递加序列

const increasingNewIndexSequence = moved
  ? getSequence(newIndexToOldIndexMap) // [0, 1]
  : EMPTY_ARR

getSequence函数回来的是最长递加序列中的元素在newIndexToOldIndexMap数组的方位索引。

Vue3源码解读-快速Diff算法

图8、核算最长递加序列

4.2 从头编号

本过程疏忽掉经过预处理的前置节点和后置节点，对新旧未处理的节点索引值进行从头编号。

Vue3源码解读-快速Diff算法

图9、从头编号

4.3 重置索引i,j的指向，辅佐节点移动

索引j指向最长递加序列中最终一个节点的方位，索引i指向新子节点最终一个方位。

Vue3源码解读-快速Diff算法

图10、重置索引i、j

然后敞开一个for循环，让索引i、j依照箭头的方向移动，见第5步。

第5步：移动or挂载节点？

5.1 newIndexToOldIndexMap[i]的值为0：挂载节点

假如newIndexToOldIndexMap[i]的值为0，则阐明索引为i的节点是全新的节点，运用patch函数将其挂载到容器中。

挂载节点源码

if (newIndexToOldIndexMap[i] === 0) {
  // mount new
  patch(
    null,
    nextChild,
    container,
    anchor,
    parentComponent,
    parentSuspense,
    isSVG,
    slotScopeIds,
    optimized
  )
}

5.2 i ≠ seq[j]时，移动节点

当索引i和索引j指向的子序列元素时，该节点对应的实在DOM需求移动。

移动节点源码

if (j < 0 || i !== increasingNewIndexSequence[j]) {
  // 当指向新的一组子节点的元素索引 i 不等于索引 j指向的子序列的元素时，
  // 该节点对应的实在DOM元素需求移动
  move(nextChild, container, anchor, MoveType.REORDER)
}

Vue3源码解读-快速Diff算法

图11、移动节点

如上图所示，此刻索引 i 的值为 2 ，索引 j 的值为 1 ，因而 2 !== seq[1] 建立，因而，节点 p-2 对应的实在节点需求移动。

5.3 i == seq[j]时，无需移动节点

当i == seq[j]时，阐明该方位的节点不需求移动，此刻只需求让索引 j 依照图中箭头方向移动即可，即让变量 j 递减，进入下一次的循环比较。

Vue3源码解读-快速Diff算法

图12、j—，持续下一次循环

如上图所示，此刻索引 i 的值为 1 ，索引 j 的值也为 1 ，因而 1 === seq[1] 建立，节点 p-4 对应的实在节点不需求移动，只需求让变量 j 递减即可。移动挂载节点操作的完整代码如下：

// looping backwards so that we can use last patched node as anchor
for (i = toBePatched - 1; i >= 0; i--) {
  const nextIndex = s2 + i
  // 新子节点
  const nextChild = c2[nextIndex] as VNode
  // 锚点
  const anchor =
    nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
  if (newIndexToOldIndexMap[i] === 0) {
    // mount new
    patch(
      null,
      nextChild,
      container,
      anchor,
      parentComponent,
      parentSuspense,
      isSVG,
      slotScopeIds,
      optimized
    )
  } else if (moved) {
    // 这儿是需求移动节点的状况
    // i 指向的是新的一组子节点中元素的方位索引
    // j 指向的是最长递加序列中元素的方位索引
    // move if:
    // There is no stable subsequence (e.g. a reverse)
    // OR current node is not among the stable sequence
    if (j < 0 || i !== increasingNewIndexSequence[j]) {
      // 当指向新的一组子节点的元素索引 i 不等于索引 j指向的子序列的元素时，
      // 该节点对应的实在DOM元素需求移动
      move(nextChild, container, anchor, MoveType.REORDER)
    } else {
      // 当i === seq[j]时，阐明该方位的节点不需求移动，即让索引j递减
      j--
    }
  }
}

Vue3整个快速Diff进程的完整代码如下：

patchKeyedChildren算法源码

// 有key标识的两组子节点的patch进程，即diff进程
  // can be all-keyed or mixed
  const patchKeyedChildren = (
    c1: VNode[],
    c2: VNodeArrayChildren,
    container: RendererElement,
    parentAnchor: RendererNode | null,
    parentComponent: ComponentInternalInstance | null,
    parentSuspense: SuspenseBoundary | null,
    isSVG: boolean,
    slotScopeIds: string[] | null,
    optimized: boolean
  ) => {
    let i = 0
    // 新的一组子节点的长度
    const l2 = c2.length
    // 旧子节点的尾部索引
    let e1 = c1.length - 1 // prev ending index
    // 新子节点的尾部索引
    let e2 = l2 - 1 // next ending index
    // 从头部开端同步，处理相同的同步节点
    // 1. sync from start
    // (a b) c
    // (a b) d e
    while (i <= e1 && i <= e2) {
      const n1 = c1[i]
      const n2 = (c2[i] = optimized
        ? cloneIfMounted(c2[i] as VNode)
        : normalizeVNode(c2[i]))
      if (isSameVNodeType(n1, n2)) {
        // 相同的节点，递归履行patch更新节点
        patch(
          n1,
          n2,
          container,
          null,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
      } else {
        // 遇到了 key 不同的节点，那就直接退出循环，相同前置节点(a b)的更新处理完结
        break
      }
      i++
    }
    // 2. sync from end
    // a (b c)
    // d e (b c)
    while (i <= e1 && i <= e2) {
      // 旧的后置节点
      const n1 = c1[e1]
      // 新的后置节点
      const n2 = (c2[e2] = optimized
        ? cloneIfMounted(c2[e2] as VNode)
        : normalizeVNode(c2[e2]))
      // 新旧后置节点相同，调用 patch 函数打补丁
      if (isSameVNodeType(n1, n2)) {
        patch(
          n1,
          n2,
          container,
          null,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
      } else {
        // 遇到了 key 不同的节点，退出循环，相同后置节(b c)点的更新处理完结
        break
      }
      // 新旧后置节点索引递减，即从后往前遍历两组子节点
      e1--
      e2--
    }
    // 3. common sequence + mount
    // (a b)
    // (a b) c
    // i = 2, e1 = 1, e2 = 2
    // (a b)
    // c (a b)
    // i = 0, e1 = -1, e2 = 0
    // i > e1 阐明在预处理的进程中，一切的旧子节点处理完毕额
    if (i > e1) {
      // i <= e2 阐明在预处理往后，在新的一组子节点中，依然有未被处理的节点，这些留传的节点将被视作新增节点
      if (i <= e2) {
        // 锚点的索引
        const nextPos = e2 + 1
        // 锚点元素
        const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
        // 选用 while 循环，调用 patch 函数逐个挂载新增节点
        while (i <= e2) {
          patch(
            null,
            (c2[i] = optimized
              ? cloneIfMounted(c2[i] as VNode)
              : normalizeVNode(c2[i])),
            container,
            anchor,
            parentComponent,
            parentSuspense,
            isSVG,
            slotScopeIds,
            optimized
          )
          i++
        }
      }
    }
    // 4. common sequence + unmount
    // (a b) c
    // (a b)
    // i = 2, e1 = 2, e2 = 1
    // a (b c)
    // (b c)
    // i = 0, e1 = 0, e2 = -1
    // i > e2 阐明新的一组子节点已经悉数处理完毕了
    else if (i > e2) {
      // i <= e1 阐明在旧的一组子节点中还有留传的节点未被处理，这些节点是需求卸载的
      while (i <= e1) {
        // 敞开一个 while 循环，并调用 unmount 函数逐个卸载这些留传节点
        unmount(c1[i], parentComponent, parentSuspense, true)
        i++
      }
    }
    // 5. unknown sequence
    // [i ... e1 + 1]: a b [c d e] f g
    // [i ... e2 + 1]: a b [e d c h] f g
    // i = 2, e1 = 4, e2 = 5
    else {
      // 预处理完后，未处理节点的第一个未处理节点的索引方位
      const s1 = i // prev starting index
      const s2 = i // next starting index
      // 构建新的一组子节点中未处理的key和索引方位的映射，是为了解决功能问题
      // 5.1 build key:index map for newChildren
      const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
      for (i = s2; i <= e2; i++) {
        const nextChild = (c2[i] = optimized
          ? cloneIfMounted(c2[i] as VNode)
          : normalizeVNode(c2[i]))
        if (nextChild.key != null) {
          if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {
            warn(
              `Duplicate keys found during update:`,
              JSON.stringify(nextChild.key),
              `Make sure keys are unique.`
            )
          }
          // 将新节点的key和索引方位增加到map调集中
          keyToNewIndexMap.set(nextChild.key, i)
        }
      }
      // 当组件的子节点发生变化时，需求对新旧子节点数组进行diff，并更具diff成果更新DOM。在diff进程中，可能会有一些旧子节点数组中剩下未被处理的节点。这些节点需求在 diff 完毕后进行处理，包含尝试与新子节点数组中的节点进行匹配并 patch，以及删去已经不存在的节点。
      // 5.2 loop through old children left to be patched and try to patch
      // matching nodes & remove nodes that are no longer present
      let j
      // 代表更新过节点数量
      let patched = 0
      // 新的一组节点中剩下未处理节点的数量
      const toBePatched = e2 - s2 + 1
      // 标识节点是否需求移动节点
      let moved = false
      // 代表遍历旧的一组子节点的进程中遇到的最大索引值
      // used to track whether any node has moved
      let maxNewIndexSoFar = 0
      // 构建一个索引映射数组，存储新的一组子节点在旧的一组子节点的方位索引（存储的是新的一组子节点中的节点在旧的一组子节点中的方位索引）
      // works as Map<newIndex, oldIndex>
      // Note that oldIndex is offset by +1
      // and oldIndex = 0 is a special value indicating the new node has
      // no corresponding old node.
      // used for determining longest stable subsequence
      const newIndexToOldIndexMap = new Array(toBePatched)
      for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
      // 遍历旧的一组子节点中剩下未处理的节点
      for (i = s1; i <= e1; i++) {
        // 旧数组中剩下未处理的节点
        const prevChild = c1[i]
        // 假如更新过的节点数量大于需求更新的节点数量，则卸载剩下的节点
        if (patched >= toBePatched) {
          // all new children have been patched so this can only be a removal
          unmount(prevChild, parentComponent, parentSuspense, true)
          continue
        }
        // 新的一组子节点中未被处理节点在新子节点中的方位索引
        let newIndex
        if (prevChild.key != null) {
          // 从索引表中获取与旧节点具有相同key的新节点在新的一组子节点中的方位索引
          newIndex = keyToNewIndexMap.get(prevChild.key)
        } else {
          // 旧子节点没有 key ，那么尝试在新的一组子节点中查找具有相同类型的没有key的新子节点
          // key-less node, try to locate a key-less node of the same type
          for (j = s2; j <= e2; j++) {
            if (
              newIndexToOldIndexMap[j - s2] === 0 &&
              isSameVNodeType(prevChild, c2[j] as VNode)
            ) {
              newIndex = j
              break
            }
          }
        }
        // 假如在新的一组子节点中没有找到与旧的一组子节点中具有相同key 或相同类型的子节点，
        // 阐明该旧子节点在新的一组子节点中已经不存在了，需求将其卸载
        if (newIndex === undefined) {
          unmount(prevChild, parentComponent, parentSuspense, true)
        } else {
          // 填充 索引映射数组
          newIndexToOldIndexMap[newIndex - s2] = i + 1
          // 经过比较 newIndex 和 maxNewIndexSoFar 的值来判别节点是否需求移动
          if (newIndex >= maxNewIndexSoFar) {
            // 假如在遍历进程中遇到的索引值出现递加趋势，则阐明不需求移动节点
            maxNewIndexSoFar = newIndex
          } else {
            // 不然需求移动
            moved = true
          }
          // 调用patch函数完结更新
          patch(
            prevChild,
            c2[newIndex] as VNode,
            container,
            null,
            parentComponent,
            parentSuspense,
            isSVG,
            slotScopeIds,
            optimized
          )
          // 每更新一个节点，都将patched变量+1
          patched++
        }
      }
      // 核算最长递加序列
      // 5.3 move and mount
      // generate longest stable subsequence only when nodes have moved
      const increasingNewIndexSequence = moved
        ? getSequence(newIndexToOldIndexMap)
        : EMPTY_ARR
      // 索引j指向最长递加序列的最终一个元素
      j = increasingNewIndexSequence.length - 1
      // i指向新的一组子节点的最终一个元素
      // looping backwards so that we can use last patched node as anchor
      for (i = toBePatched - 1; i >= 0; i--) {
        const nextIndex = s2 + i
        // 新子节点
        const nextChild = c2[nextIndex] as VNode
        // 锚点
        const anchor =
          nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
        if (newIndexToOldIndexMap[i] === 0) {
          // mount new
          patch(
            null,
            nextChild,
            container,
            anchor,
            parentComponent,
            parentSuspense,
            isSVG,
            slotScopeIds,
            optimized
          )
        } else if (moved) {
          // 这儿是需求移动节点的状况
          // i 指向的是新的一组子节点中元素的方位索引
          // j 指向的是最长递加序列中元素的方位索引
          // move if:
          // There is no stable subsequence (e.g. a reverse)
          // OR current node is not among the stable sequence
          if (j < 0 || i !== increasingNewIndexSequence[j]) {
            // 当指向新的一组子节点的元素索引 i 不等于索引 j指向的子序列的元素时，
            // 该节点对应的实在DOM元素需求移动
            move(nextChild, container, anchor, MoveType.REORDER)
          } else {
            // 当i === seq[j]时，阐明该方位的节点不需求移动，即让索引j递减
            j--
          }
        }
      }
    }
  }

4、总结

4.1 Vue2的Diff算法-双端diff算法

Vue2选用的diff算法叫双端diff算法。这是一种用于虚拟DOM比较和更新的算法，它经过一起从新旧两个虚拟DOM树的两头开端遍历，以最小化操作的数量来完结高效的更新。

详细而言，双端diff算法分为以下几个过程：

  1. 首先，算法会比较新旧两个虚拟DOM树的根节点。假如两个根节点不同，算法会直接替换旧的根节点。
  2. 接下来，算法会比较新旧两个根节点的子节点。它会从新旧两个子节点数组的两头开端遍历，一起比较相应方位的节点。假如节点相同，则持续比较下一个方位的节点；假如节点不同，则算法会根据必定的规矩进行节点的替换、移动或删去操作。
  3. 假如新旧两个子节点数组的长度不同，算法会根据差异的方位进行节点的插入或删去操作。

总的来说，双端diff算法经过从两头一起遍历虚拟DOM树，可以更高效地找到节点的差异，并进行相应的更新操作。这种算法在实践运用中可以大大提高更新的功能和功率。

4.2 Vue3的diff算法-快速diff算法

Vue3与Vue2比较，引入了更高效的Diff算法-快速diff算法。它选用了预处理思路，先处理前置节点和后置节点。然后，算法会依照必定的规矩，将虚拟DOM分成几个不同的状况进行处理，包含新旧虚拟DOM完全相同、只要部分节点发生变化、新增节点、删去节点等状况。针对不同的状况，算法会采取不同的策略来进行DOM更新。经过引入新的Diff算法，Vue3在功能上有了显着的提高。它可以更快速地响运用户的操作，并且在大规模数据更新时，也可以更高效地进行DOM更新。这使得Vue3在实践项目中可以处理更杂乱的场景，并且供给更好的用户体会。

总结来说，Vue3的Diff算法比较Vue2，具有更高的功能和更好的用户体会。它可以更快速地进行DOM更新，并且经过一系列的优化策略，减少了不必要的操作，提高了全体的功能表现。

5、参考资料

[1] Vue官网

[2] Vuejs规划与完结

欢迎关注我的大众号：前端Talkking