Vue3 源码解析（五）：Patch 算法

与 React 一样，Vue 在处理虚拟 DOM 的更新时，也有自己的 diff 算法 —— patch。

什么是 patch

Vue 在通过 VNode 节点渲染 DOM 时，并不是通过当前的 VNode 节点去暴力的更新 DOM 节点，而是对新旧两个 VNode 节点通过 patch 算法进行比较，然后通过对比结果找出差异的属性或节点进行按需更细。显而易见，patch 能够减少不必要的开销，提升性能。

patch 的过程中主要完成以下几件事情：

创建需要新增的节点
移除已经废弃的节点
移动或修改需要更新的节点

Vue3 的 patch 优化 —— patchFlag

在尤大的多次有关 Vue3 的演讲中，都提及了 patchFlag 对于 patch 的优化，所以在阅读源码时我也是格外留心 patchFlag 的部分。那么 patchFlag 究竟有什么用？

举个例子，当两个节点是同一类型时，这两个节点虽然类型相同，但是可能新节点的属性也发生了变化，所以此时我们还需要对节点的属性进行遍历，才能有效的判断是否需要更新。

那我们来看如下元素：

<div id="bar" :class="foo">Hello World</div>

对于这样一个 div 元素，从前端工程师的角度可以明确的判断出，id=”bar” 以及 children 是文本类型都是静态属性，不会再发生变化了，只需要关注 class 是否改变即可。而如今 Vue3 利用 patchFlag 就做到了这一点，在生成 AST 树后，经过转换器遍历各个节点时，就会根据节点的特点打上对应的 patchFlag。而在 patch 的过程中，仅仅会处理 class 这一个 props，而并不是全量比较。这样的话能减少以及遍历 props 的次数，从而实现性能提升。

patch 是怎么工作的

在讲明白 patch 的作用后，我会带着大家一起来看一下 patch 的源码实现。patch 的源码位于 @runtime-core/src/renderer.ts 的文件中，由于这份文件中代码长度非常长，所以在讲解代码时，会省略非必要的代码，而只将主要逻辑。

因为我希望看文章的你能够收获的是 patch 流程中的逻辑总结，以及注意到重点逻辑即可。并不是每个人都需要去阅读源码的，而贴出部分关键代码，是希望有同学产生兴趣时，想去阅读源码能够有个代码片段参照。

const patch: PatchFn = (
  n1,
  n2,
  container,
  anchor = null,
  parentComponent = null,
  parentSuspense = null,
  isSVG = false,
  slotScopeIds = null,
  optimized = false
) => {
  // patching & 不是相同类型的 VNode，则从节点树中卸载
  if (n1 && !isSameVNodeType(n1, n2)) {
    anchor = getNextHostNode(n1)
    unmount(n1, parentComponent, parentSuspense, true)
    n1 = null
  }
	// PatchFlag 是 BAIL 类型，则跳出优化模式
  if (n2.patchFlag === PatchFlags.BAIL) {
    optimized = false
    n2.dynamicChildren = null
  }

  const { type, ref, shapeFlag } = n2
  switch (type) { // 根据 Vnode 类型判断
    case Text: // 文本类型
      processText(n1, n2, container, anchor)
      break
    case Comment: // 注释类型
      processCommentNode(n1, n2, container, anchor)
      break
    case Static: // 静态节点类型
      if (n1 == null) {
        mountStaticNode(n2, container, anchor, isSVG)
      }
      break
    case Fragment: // Fragment 类型
      processFragment(/* 忽略参数 */)
      break
    default:
      if (shapeFlag & ShapeFlags.ELEMENT) { // 元素类型
        processElement(
          n1,
          n2,
          container,
          anchor,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
      } else if (shapeFlag & ShapeFlags.COMPONENT) { // 组件类型
        processComponent(/* 忽略参数 */)
      } else if (shapeFlag & ShapeFlags.TELEPORT) { // TELEPORT 类型
        ;(type as typeof TeleportImpl).process(/* 忽略参数 */)
      }
  }
}

一起来看上面👆 patch 函数的源码，我们先从入参看起：n1 与 n2 是待比较的两个节点，n1 为旧节点，n2 为新节点。container 是新节点的容器，而 anchor 是一个锚点，用来标识当我们对新旧节点做增删或移动等操作时，以哪个节点为参照物。optimized 参数是是否开启优化模式的标识。其他参数就不一一介绍了，我们暂时不用关心。

我们看第一个 if 条件，当旧节点存在，并且新旧节点不是同一类型时，则将旧节点从节点树中卸载。这就是我们可以总结出的 patch 的第一个逻辑: 当两个节点的类型不同，则直接卸载旧节点。

再看第二个 if 分支条件，如果新节点的 patchFlag 的值是 BAIL ，优化模式会被关闭。这是我们第一次在源码中遇到 patchFlag，不过不用太细究这里，我们接着往下看。

接下来 patch 函数会通过 switch case 来判断节点类型，并分别对不同节点类型执行不同的操作。

这里我们就以 ELEMENT 元素类型来举例，因为各类 HTML 元素是我们大部分时间都在处理的类型，在上方源码中当 case 走到了 default 默认分支，此时通过 shapeFlag 的按位与运算判断出当前 VNode 是一个元素类型，接着调用 processElement 继续 patch 的过程，并将 patch 函数中的参数传递了过去，我就顺着 processElement 函数继续往下分析。

元素的 Patch 过程 —— processElement

processElement 这个函数本身的代码逻辑非常简单，总结起来就一句话：如果存在旧节点，则继续通过 patch 比较新旧两个节点，否则直接挂载新节点。源码如下：

const processElement = (
  n1: VNode | null,
  n2: VNode,
  container: RendererElement,
  anchor: RendererNode | null,
  parentComponent: ComponentInternalInstance | null,
  parentSuspense: SuspenseBoundary | null,
  isSVG: boolean,
  slotScopeIds: string[] | null,
  optimized: boolean
) => {
  // 如果旧节点不存在
  if (n1 == null) {
    mountElement(
      n2,
      container,
      anchor
      /* 后续参数省略 */
    )
  } else {
    patchElement(
      n1,
      n2,
      parentComponent,
      parentSuspense,
      isSVG,
      slotScopeIds,
      optimized
    )
  }
}

当旧节点不存在时直接挂载比较简单，所以为了体现 patch 的流程，我会假设新旧节点都是存在的，顺着 patchElement 继续往下分析。

比较子节点 —— patchElement

在元素类型的 patch 过程中，Vue3 首先会将新旧节点的 props 声明提取出来，因为之后需要对 props 进行 patch 比较。

在比较开始之前会触发一些钩子，比如 VNode 自身的钩子：onVnodeBeforeUpdate，以及元素上绑定的指令的钩子 beforeUpdate。

if ((vnodeHook = newProps.onVnodeBeforeUpdate)) {
  invokeVNodeHook(vnodeHook, parentComponent, n2, n1)
}
if (dirs) {
  invokeDirectiveHook(n2, n1, parentComponent, 'beforeUpdate')
}

更新属性

之后开始比较 props，如果此时元素被标记过 patchFlag，则会通过 patchFlag 进行按需比较，否则会全量的 diff 元素中的 props。

if (patchFlag > 0) {
  if (patchFlag & PatchFlags.FULL_PROPS) {
    // 如果元素的 props 中含有动态的 key，则需要全量比较
    patchProps(
      el,
      n2,
      oldProps,
      newProps,
      parentComponent,
      parentSuspense,
      isSVG
    )
  } else {
    if (patchFlag & PatchFlags.CLASS) {
      if (oldProps.class !== newProps.class) {
        hostPatchProp(el, 'class', null, newProps.class, isSVG)
      }
    }

    if (patchFlag & PatchFlags.STYLE) {
      hostPatchProp(el, 'style', oldProps.style, newProps.style, isSVG)
    }

    if (patchFlag & PatchFlags.PROPS) {
      const propsToUpdate = n2.dynamicProps!
      for (let i = 0; i < propsToUpdate.length; i++) {
        const key = propsToUpdate[i]
        const prev = oldProps[key]
        const next = newProps[key]
        if (
          next !== prev ||
          (hostForcePatchProp && hostForcePatchProp(el, key))
        ) {
          hostPatchProp(
            el,
            key,
            prev,
            next,
            isSVG,
            n1.children as VNode[],
            parentComponent,
            parentSuspense,
            unmountChildren
          )
        }
      }
    }
  }

  if (patchFlag & PatchFlags.TEXT) {
    if (n1.children !== n2.children) {
      hostSetElementText(el, n2.children as string)
    }
  }
} else if (!optimized && dynamicChildren == null) {
  patchProps(
    el,
    n2,
    oldProps,
    newProps,
    parentComponent,
    parentSuspense,
    isSVG
  )
}

我们一起来捋一捋上方的分支条件，并看看 patchFlag 此时做了些什么。

当 patchFlag 为 FULL_PROPS 时，说明此时的元素中，可能包含了动态的 key ，需要进行全量的 props diff。
当 patchFlag 为 CLASS 时，当新旧节点的 class 不一致时，此时会对 class 进行 patch，而当新旧节点的 class 属性完全一致时，不需要进行任何操作。这个 Flag 标记会在元素有动态的 class 绑定时加入。
当 patchFlag 为 STYLE 时，会对 style 进行更新，这是每次 patch 都会进行的，这个 Flag 会在有动态 style 绑定时被加入。
当 patchFlag 为 PROPS 时，需要注意这个 Flag 会在元素拥有动态的属性或者 attrs 绑定时添加，不同于 class 和 style，这些动态的prop 或 attrs 的 key 会被保存下来以便于更快速的迭代。
- PROPS 的比较会将新节点的动态属性提取出来，并遍历这个这个属性中所有的 key，当新旧属性不一致，或者该 key 需要强制更新时，则调用 hostPatchProp 对属性进行更新。
当 patchFlag 为 TEXT 时，如果新旧节点中的子节点是文本发生变化，则调用 hostSetElementText 进行更新。这个 flag 会在元素的子节点只包含动态文本时被添加。

此时当元素拥有 patchFlag 时的分支判断就结束了，我们可以在这些分支判断中，体会到 patchFlag 为 patch 算法的速度提升所做出的努力。

分支走到最后一个 else，若当前不存在优化标记，并且动态子节点也不存在，则直接对 props 进行全量 diff，通过 patchProps 这个函数完成。

对于 props 的比较，受限于篇幅我们就只讲到这里，分支内具体的函数调用就不展开讲了。

更新子节点 —— patchChildren

接下来就会进入最重要的更新子节点的部分。在元素的 patch 过程中，会判断是否存在动态子节点，如果是则调用 patchBlockChildren 仅仅更新动态的子节点，否则会调用 patchChildren 对子节点进行全量更新。

这里我们会看一般情况：patchChildren。

在更新子节点时，首先也是利用 patchFlag 的能力，对子节点进行分类做出不同的处理，为了避免大篇幅的贴源码，这里我给大家总结一下 patchChildren 函数的逻辑，然后我们再重点的看其中通用的部分。

根据 patchFlag 进行判断：
- 如果 patchFlag 是存在 key 值的 Fragment：KEYED_FRAGMENT，则调用 patchKeyedChildren 来继续处理子节点。
- 如果 patchFlag 是没有设置 key 值的 Fragment: UNKEYED_FRAGMENT，则调用 patchUnkeyedChildren 处理没有 key 值的子节点。
根据 shapeFlag （元素类型标记）进行判断：
- 如果新子节点是文本类型，而旧子节点是数组类型，则直接卸载旧节点的子节点。
  - 如果新旧节点类型一致，则直接更新新子节点的文本。
- 如果旧子节点类型是数组类型
  - 如果新子节点也是数组类型，则调用 patchKeyedChildren 进行完整的 diff。
  - 如果新子节点不是数组类型，则说明不存在新子节点，直接从树中卸载旧节点即可。
- 如果旧子节点是文本类型，由于已经在一开始就判断过新子节点是否为文本类型，那么此时可以肯定新子节点肯定不为文本类型，则可以直接将元素的文本置为空字符串。
- 如果新子节点是类型为数组类型，而旧子节点不为数组，说明此时需要在树中挂载新子节点，进行 mount 操作即可。

上述就是 patchChildren 的完整逻辑，这里最复杂的逻辑就是当新旧子节点都为数组类型时调用 patchKeyedChildren 对两个数组进行完整比较。

子节点的更新策略

如何高效的做 diff 算法，最重要的性能瓶颈就是如何更快速的对树中的子节点进行比较，得出需要进行什么具体操作，如果按正常思维去比较，那么时间复杂度至少为 O(n^3)，那么 1000 个子节点的树在进行比较时，至少需要 10 亿次比较，那么无疑这个操作是非常昂贵的。而针对这种情况如何实现一个时间复杂度为 O(n) 的算法，就是前端框架必须考虑的问题。与 React 一样，Vue 中也有 key 来协助标识子节点，帮助框架进行更高效的识别和比较子节点。

Vue2 的子节点优化策略

在我阅读《深入浅出 Vue.js 》这本书时，作者刘博文将 Vue2 的子节点优化策略总结为四类：

新前与旧前
新后与旧后
新后与旧前
新前与旧后

需要注意的是新前指代新子节点索引在最前面的节点，而新后指代新子节点索引在末尾的节点，而旧则指代旧子节点的意思。

当时我阅读此书后，觉得这样的总结非常贴切好记，也很好的帮助了我更浅显易懂的阅读 Vue2 的源码，所以在 Vue3 的子节点更新策略中我依旧打算沿用这样的叫法来描述更新策略。

Vue3 的子节点更新

下面为了讲述的流畅性，以及能够随时看到代码进行参考，我会把 patchKeyedChildren 函数拆分成一个一个的逻辑点，按我们讲述的节奏贴上源码以及对应的图片。

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
  /* 忽略后续逻辑 */
}

首先我们来看 patchKeyedChildren 的函数签名部分，该函数参数中的 c1、c2 分别代表旧子节点、新子节点。

而函数开始会声明 4 个变量：

遍历子节点的索引 i = 0
新子节点长度：l2
旧子节点的末尾索引：e1
新子节点的末尾索引：e2

在记住这四个声明出的变量，我们开始看 Vue3 中字子节点的第一个比较策略。

新前与旧前

patch-1

先看这张图，同一行的 C1, C2 节点，就是待比较的两个新旧子节点，比较子节点会从两个子节点的起始索引开始：

当 i = 0 时，比较第 0 个索引，发现 C1 的 A 节点与 C2 节点的 A 节点是同一类型的元素，则会对新旧的 A 节点进行 patch 操作，在这里进行 patch 能够递归的去访问 A 节点下的所有子节点，patch 完成后递增索引 i 。

继续比较，发现 C1 的 B 节点与 C2 的 B 节点也是同一类型的元素，与之前一样对B 节点进行 patch 递归后递增 i 索引。

当比较第三个子节点时，会发现 C1 的 C 节点与 C2 的 D 节点并不是同一类型的节点，所以会 break 跳出新前与旧前的比较循环，于是新前与旧前的比较结束。

而此时已经完成了 C1 和 C2 的子节点的前两个节点的比较。这个比较的过程在源码中是这样的：

while (i <= e1 && i <= e2) {
  const n1 = c1[i]
  const n2 = (c2[i] = optimized
    ? cloneIfMounted(c2[i] as VNode)
    : normalizeVNode(c2[i]))
  // 比较 n1 与 n2 是否是同一类型的 VNode
  if (isSameVNodeType(n1, n2)) {
    patch(
      n1,
      n2,
      container,
      null,
      parentComponent,
      parentSuspense,
      isSVG,
      slotScopeIds,
      optimized
    )
  } else {
    // 如果 n1 与 n2 不是同一类型，则 break 出 while 循环
    break
  }
  // 递增 i
  i++
}

新后与旧后

在新前与旧前的比较完成后，与 Vue2 中的优化策略一致，会开始新后与旧后的比较。

patch-2

一起来看新后与旧后的示例图片，相信经过新前与旧前的介绍，大家已经能看懂新后与旧后的比较思路了。

通过之前声明的 e1 与 e2 这两个新旧子节点的末尾索引，从最末尾开始比较元素。

按图中的比较则是如下逻辑：

从末尾开始，C1 是 C 节点，而 C2 也是 C 节点，两个节点的类型相同，开始进行 patch 比较，待 patch 完成后，新旧子节点的末尾索引 - 1。
进行第二次比较，C1 的末尾是 B 节点，C2 的末尾是 B 节点，类型相同，进行 patch，之后递减尾部索引。
进行第三次比较，C1 的末尾节点是 A，C2 的末尾节点是 E，类型不同，break 跳出新后与旧后的比较循环。

下面是新后与旧后的比较源码：

while (i <= e1 && i <= e2) {
  const n1 = c1[e1]
  const n2 = (c2[e2] = optimized
    ? cloneIfMounted(c2[e2] as VNode)
    : normalizeVNode(c2[e2]))
  // 比较 n1 与 n2 是否是同一类型的 VNode
  if (isSameVNodeType(n1, n2)) {
    patch(
      n1,
      n2,
      container,
      null,
      parentComponent,
      parentSuspense,
      isSVG,
      slotScopeIds,
      optimized
    )
  } else {
    // 如果 n1 与 n2 不是同一类型，则 break 出 while 循环
    break
  }
  // 完成 patch 操作后，尾部索引递减
  e1--
  e2--
}

常规顺序的新子节点挂载

当我们完成了前两轮的比较后，此时往往能在常规的序号上发现一些新子节点中存在，而旧子节点中没有的元素，此时就需要将这些新增的子节点插入。

patch-3

如图，当新前与旧前的比较完成后，此时索引 i 已经递增的超过 C1 子节点的长度，此时 i = 2，并且 i 还小于等于 C2 子节点的长度，于是可以判定在新子节点中还有节点没有被遍历到，此时旧子节点已经全部遍历完，所以将未被遍历的子节点全部插入即可。

对应这张图，应该插入 C 节点。

这个挂载过程的源码如下，参考一下源码中的注释：

// 当旧子节点被遍历完
if (i > e1) {
  // 新节点还有元素未被遍历完
  if (i <= e2) {
    const nextPos = e2 + 1
    // 确定好锚点元素
    const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
    // 遍历剩余的新子节点
    while (i <= e2) {
    	// patch 时第一个参数传入 null，代表没有旧节点，直接将新节点插入即可
      patch(
        null,
        (c2[i] = optimized
          ? cloneIfMounted(c2[i] as VNode)
          : normalizeVNode(c2[i])),
        container,
        anchor,
        parentComponent,
        parentSuspense,
        isSVG,
        slotScopeIds,
        optimized
      )
      i++
    }
  }
}

常规顺序的移除多余节点

与上面的挂载逻辑相对应的是移除多余的旧子节点。

当新子节点已经全部遍历完时，如果此时旧子节点还有元素未被遍历，那么可以判定剩余的旧子节点已经不再需要了，所以直接将剩余旧子节点移除即可。

patch-4

从图中来看，C1 与 C2 在通过新后与旧后的比较完成后，此时旧子节点 C1 中还剩余 A 节点，新节点中已经没有需要比较的节点了，所以直接移除 A 节点即可。

在源码中对应的逻辑也很简单：

// 如果新子节点已被遍历完
else if (i > e2) {
  // 就子节点未被遍历完
  while (i <= e1) {
    // 调用 unmount 卸载旧子节点
    unmount(c1[i], parentComponent, parentSuspense, true)
    // 递增索引
    i++
  }
}

未知顺序的子节点比较

在上述理想情况处理完成后，我们将要面对剩下不能确定元素位置的场景了。

patch-5

一起先来看一下这张图，可以看到新旧子节点中都挂载了比较多的元素，当我们通过新前与旧前，新后与旧后的比较后，还剩余中间部分的不确定顺序的节点了。旧子节点中的 CDE，新子节点中的 EDCH。

作为旁观者，我们很清楚这时需要对 CDE 进行移动，而对 H 节点需要插入。让我们一起来看一下 patch 是如何完成这个任务的：

声明 s1、s2 两个变量，并将此时遍历的前序索引 i 赋值给 s1、s2。s1、s2 分别表示新旧子节点的起始索引。

以 s2 为起始节点，e2 为结束条件，遍历新子节点，用新子节点中子节点的 key 为键，索引 i 为值，生成一个 Map 对象, 存放原始索引。

如果此时发现有子节点中有重复的键，就会发出一个所有 Vue 开发者都很熟悉的警告:Duplicate keys found during update xxx, Make sure keys are unique。

const s1 = i // 旧子节点的起始索引
const s2 = i // 新子节点的起始索引
  
// 对新子节点，创建一个索引的 map 对象
const keyToNewIndexMap: Map<string | number, 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) {
    // 如果是 DEV 环境，且 keyToNewIndexMap 已经存在当前节点的 key 值，则警告。
    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)
  }
}

声明变量 toBePatched，计算还有几个节点需要被 patch。声明变量 patched = 0，记录 patch 的节点数。
声明一个 newIndexToOldIndexMap 的数组，用于后续确定最长递增子序列，newIndexToOldIndexMap 数组大小为 toBePatched 的长度，并将数组内所有元素初始化为 0。
- newIndexToOldIndexMap，形式是 Map<newIndex, oldIndex>
- 需要注意的是里面存储的 oldIndex 是索引是偏移 +1 的。
- oldIndex = 0 是一个特殊值，表示新子节点中没有对应的旧子节点。
遍历旧子节点，将当前被遍历的子节点标记为 prevChild。
- 如果 patched 大于等于 toBePatched，说明需要被 patch 的节点已经全部比较完毕，则可以将剩余的 prevChild 移除。
- 否则声明变量 newIndex。
- 如果 prevChild 的 key 不为空，则从 keyToIndexMap 中取 prevChild.key 的值，将获取到的值赋值给 newIndex。
- 如果 newIndex 没有值，则说明在新子节点中没有对应的旧子节点，直接移除 prevChild 旧子节点。
- 否则在 newIndexToOldIndexMap 中存下新的索引，并标记当前索引移动的最远位置或增加移动标记，并对新旧子节点进行 patch 比较。
- 在完成 patch 后，将 patched 计数递增。

以上逻辑的代码如下：

/**
 * 遍历旧子节点，尝试 patch 比较需要被 patch 的节点，并且移除不会再出现的子节点
 */
let j
let patched = 0
const toBePatched = e2 - s2 + 1
let moved = false
// 用于跟踪是否有节点发生移动
let maxNewIndexSoFar = 0
// 用于确定最长递增子序列
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) {
    // 所有新节点都被 patch 了，所以剩下的只需要移除
    unmount(prevChild, parentComponent, parentSuspense, true)
    continue
  }
  let newIndex
  if (prevChild.key != null) {
    newIndex = keyToNewIndexMap.get(prevChild.key)
  } else {
    // 对于找不到 key 的节点，尝试去定位相同 type 的节点
		/* 忽略逻辑 */
  }
  // 如果旧子节点不能匹配到对应的新子节点，则移除该旧子节点
  if (newIndex === undefined) {
    unmount(prevChild, parentComponent, parentSuspense, true)
  } else {
    // 在 newIndexToOldIndexMap 记录下被 patch 的节点的索引
    newIndexToOldIndexMap[newIndex - s2] = i + 1
    // 如果 newIndex 的索引大于最远移动的索引，则更新
    if (newIndex >= maxNewIndexSoFar) {
      maxNewIndexSoFar = newIndex
    } else {
      // 否则标记 moved 为 true
      moved = true
    }
    // 对新旧子节点进行 patch
    patch(
      prevChild,
      c2[newIndex] as VNode,
      container,
      null,
      parentComponent,
      parentSuspense,
      isSVG,
      slotScopeIds,
      optimized
    )
    // patch 完毕后，递增 patched 计数。
    patched++
  }
}

在遍历完旧子节点后，我们已经移除了不必要的旧子节点，并且依旧存在于新节点中的对应的旧子节点都进行了 patch 比较，接下来我们需要遍历一下新子节点，仅仅只从后往前遍历需要被 patch 的部分，目的是对于新增的子节点进行插入，对于需要移动的子节点进行同级的移动。逻辑描述如下：

如果有 moved 标记，则从 newIndexToOldIndexMap 中找到最长递增子序列，并将 j 赋值为最长递增子序列数组的末尾索引。
从后往前的遍历新子节点，这样可以使我们确定锚点元素的位置。
声明 newIndex = s2 + i，即为最后一个需要被 patch 的节点。
获取锚点元素。
如果这个需要被 patch 的节点，i 索引在 newIndexToOldIndexMap 中的值为 0。还记得我之前提示的，0 是一个特殊值，代表该节点在旧子节点中没有对应的节点吧。那么对于没有对应节点的元素，我们就对它采用插入操作。
如果 newIndexToOldIndexMap 中有对应索引，但是存在 moved 标记，说明节点可能移动，应该继续判断。
- 如果 j < 0，说明最长递增子序列中的所有节点都已经处理过。或者当索引 i 不等于最长增长子序列中索引 j 对应的值时，说明该节点并不处在一个相对稳定的位置，则需要进行移动操作。
- 如果满足上述条件，j 索引递减，不用处理该节点。

上述逻辑代码如下：

/**
 * 移动和挂载
 */
// 当节点被移动时，创建最长递增子序列
const increasingNewIndexSequence = moved
  ? getSequence(newIndexToOldIndexMap)
  : EMPTY_ARR
j = increasingNewIndexSequence.length - 1
// 为了能方便的获取锚点，选择从后向前遍历
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) {
		// 如果在 newIndexToOldIndexMap 中找不到对应的索引，则新增节点
    patch(
      null,
      nextChild,
      container,
      anchor,
      parentComponent,
      parentSuspense,
      isSVG,
      slotScopeIds,
      optimized
    )
  } else if (moved) {
    // 如果不是一个稳定的子序列，或者当前节点不在递增子序列上时，需要移动
    if (j < 0 || i !== increasingNewIndexSequence[j]) {
      move(nextChild, container, anchor, MoveType.REORDER)
    } else {
      j--
    }
  }
}

至此对于存在键值的子节点的更新就结束了，跟着我一起看下来，如果能仔细将源码和逻辑结合在一起看，那么我相信理解子节点更新的源码是十分容易的一件事。

总结

在本文中，我介绍了 patch 的作用，也讲解了 Vue3 在更新节点时通过 patchFlag 标记加快速度进行性能优化。

之后讲解了 patch 函数的流程，并以元素 ELEMENT 类型为例顺着函数的调用流程一直往下分析，直至介绍子节点的更新。

在子节点的更新中我们对比了 Vue2 与 Vue3 的更新策略的不同，并详细讲解了 Vue3 遇到存在 key 值的子节点是如何进行比较的。

在此我可以将 Vue3 的子节点更新总结为 5 个步骤：

1、新前与旧前的比较。

2、新后与旧后的比较。

3、常规序列的新增操作。

4、常规序列的移除操作。

5、未知顺序的处理。

5.1 对新子节点建立 key 与索引的 map：keyToNewIndexMap 。

5.2 遍历旧子节点对能够匹配到的旧节点进行 patch 操作，对于不会存在的旧子节点进行移除操作。

5.3 对新子节点进行移动或新增操作。

以上 5 点即是 Vue3 中非常重要的子节点更新过程，如果觉得文章太长不看的朋友也可以直接了当的看总结。

如果这篇文章能够帮助到你了解 Vue3 中的 patch 过程以及子节点更新策略，希望能给本文点一个喜欢❤️。如果想继续追踪后续文章，也可以关注我的账号，再次谢谢能阅读至此的你。

李晓的博客