深入分析 Vue 3 源码中 `patch` 函数的 Diff 算法，特别是针对数组头部/尾部移动的“快速路径”（`fast path`）优化。

各位观众，晚上好！今天咱们不聊诗和远方，就聊聊 Vue 3 源码里那个磨人的小妖精 —— patch 函数的 Diff 算法。尤其是它对数组头部/尾部移动的“快速路径”（fast path）优化，这可是个能让你的 Vue 应用跑得更溜的小秘密。

开场白：Diff 的重要性

想象一下，你用 Vue 做了一个列表，用户添加、删除、移动了几项。如果每次修改都直接暴力地重新渲染整个列表，那性能简直要上天台。所以，聪明的 Vue 就采用了 Diff 算法，只更新真正变化的部分。patch 函数就是这个算法的核心执行者。

`patch` 函数：舞台上的总导演

patch 函数的任务，简单来说，就是比较新旧两个 VNode (Virtual DOM Node)，然后把差异应用到真实 DOM 上。它就像个总导演，指挥着演员们（DOM 元素）根据剧本（新 VNode）调整自己的表演。

函数签名先认识一下：

function patch(
  n1: VNode | null, // 旧 VNode
  n2: VNode | null, // 新 VNode
  container: RendererElement, // 容器，要挂载或更新的 DOM 元素
  anchor: RendererNode | null = null, // 锚点，用于插入 DOM 元素
  parentComponent: ComponentInternalInstance | null = null, // 父组件实例
  parentSuspense: SuspenseBoundary | null = null, // 父 Suspense 组件
  isSVG: boolean = false, // 是否是 SVG
  optimized: boolean = false // 是否优化
)

数组 Diff：重头戏登场

patch 函数处理各种类型的 VNode，但今天我们聚焦在数组类型的 VNode 上，也就是列表渲染。

当新旧 VNode 都是数组时，patch 函数会调用一个更精细的 Diff 算法来找出差异。这个算法的目标是：

尽量复用旧的 DOM 元素，避免不必要的创建和销毁。
尽可能少地移动 DOM 元素，减少浏览器的重排（reflow）操作。

Diff 算法的演进：从简单到复杂

最简单的 Diff 算法，就是暴力遍历，找到每个新节点在旧节点中的位置，然后进行相应的操作。但这种算法的复杂度是 O(n^2)，效率太低。

Vue 3 的 Diff 算法，在借鉴了 snabbdom 的基础上，做了很多优化。它主要分三个阶段：

头部/尾部优化（fast path）：处理两端相同的节点。
简单序列 Diff：处理添加或删除节点的情况。
最长递增子序列 Diff：处理乱序移动的情况。

今天我们重点讲解第一阶段的 头部/尾部优化。

头部/尾部优化：快刀斩乱麻

这个阶段的目标是，快速处理新旧数组头部和尾部相同的节点。它可以处理以下几种情况：

头部新增节点：新数组头部比旧数组头部多了一些节点。
头部删除节点：旧数组头部比新数组头部多了一些节点。
尾部新增节点：新数组尾部比旧数组尾部多了一些节点。
尾部删除节点：旧数组尾部比新数组尾部多了一些节点。

这种优化之所以有效，是因为在实际应用中，很多列表的修改都发生在头部或尾部。

代码剖析：`patchKeyedChildren` 函数

头部/尾部优化的代码主要在 patchKeyedChildren 函数中，我们截取关键部分进行分析：

function patchKeyedChildren(
  n1: VNode,
  n2: VNode,
  container: RendererElement,
  anchor: RendererNode | null,
  parentComponent: ComponentInternalInstance | null,
  parentSuspense: SuspenseBoundary | null,
  isSVG: boolean,
  optimized: boolean
) {
  const oldChildren = n1.children as VNode[];
  const newChildren = n2.children as VNode[];

  let i = 0;
  const l2 = newChildren.length;
  let e1 = oldChildren.length - 1; // 旧数组的尾部索引
  let e2 = l2 - 1; // 新数组的尾部索引

  // 1. 从头部开始比较，找到相同的前缀
  while (i <= e1 && i <= e2) {
    const n1 = oldChildren[i];
    const n2 = newChildren[i];
    if (isSameVNodeType(n1, n2)) {
      patch(
        n1,
        n2,
        container,
        anchor,
        parentComponent,
        parentSuspense,
        isSVG,
        optimized
      );
    } else {
      break;
    }
    i++;
  }

  // 2. 从尾部开始比较，找到相同的后缀
  while (i <= e1 && i <= e2) {
    const n1 = oldChildren[e1];
    const n2 = newChildren[e2];
    if (isSameVNodeType(n1, n2)) {
      patch(
        n1,
        n2,
        container,
        anchor,
        parentComponent,
        parentSuspense,
        isSVG,
        optimized
      );
    } else {
      break;
    }
    e1--;
    e2--;
  }

  // 3. 处理新增节点
  if (i > e1) {
    if (i <= e2) {
      const nextPos = e2 + 1;
      const anchor = nextPos < l2 ? newChildren[nextPos].el : anchor;
      while (i <= e2) {
        patch(
          null,
          newChildren[i],
          container,
          anchor,
          parentComponent,
          parentSuspense,
          isSVG,
          optimized
        );
        i++;
      }
    }
  }

  // 4. 处理删除节点
  else if (i > e2) {
    while (i <= e1) {
      unmount(oldChildren[i], parentComponent, parentSuspense, true);
      i++;
    }
  }

  // 5. 处理乱序移动
  else {
    // ... (后面会讲)
  }
}

代码解读：

初始化：定义了 i，e1，e2 三个索引。i 从头部开始，e1 和 e2 分别指向旧数组和新数组的尾部。
头部比较：while (i <= e1 && i <= e2) 循环从头部开始比较新旧数组的节点。如果 isSameVNodeType(n1, n2) 返回 true，说明这两个节点是相同的，可以进行 patch 操作复用旧的 DOM 元素。否则，跳出循环。
尾部比较：while (i <= e1 && i <= e2) 循环从尾部开始比较新旧数组的节点。逻辑和头部比较类似。
新增节点：如果 i > e1，说明旧数组已经遍历完了，但新数组还有剩余节点，这些节点需要新增。anchor 用于指定插入位置，如果 nextPos < l2，说明新数组后面还有节点，插入位置就是新数组下一个节点对应的 DOM 元素。否则，插入到 anchor 指定的位置（通常是父元素的末尾）。
删除节点：如果 i > e2，说明新数组已经遍历完了，但旧数组还有剩余节点，这些节点需要删除。unmount 函数用于卸载 VNode 对应的 DOM 元素。

例子说明

为了更好地理解这个过程，我们举几个例子：

例子 1：头部新增节点

旧数组：[A, B, C]
新数组：[X, Y, A, B, C]

头部比较：i 从 0 开始，比较 A 和 X，发现不同，跳出循环。i = 0。
尾部比较：e1 指向 C，e2 指向 C，发现相同，patch(C, C)，e1--，e2--。
继续比较，直到 i > e1 && i > e2 不成立，尾部循环结束。i = 0, e1 = -1, e2 = 1
新增节点：i > e1 成立，i <= e2 成立，说明新数组还有剩余节点 X 和 Y 需要新增。
将 X 和 Y 插入到 A 对应的 DOM 元素之前。

例子 2：尾部删除节点

旧数组：[A, B, C, D]
新数组：[A, B, C]

头部比较：i 从 0 开始，比较 A 和 A，发现相同，patch(A, A)，i++。
继续比较，直到 i > e1 && i > e2 不成立，头部循环结束。i = 3, e1 = 3, e2 = 2
尾部比较：i > e1 && i > e2 不成立，跳过。
删除节点：i > e2 成立，说明旧数组还有剩余节点 D 需要删除。
卸载 D 对应的 DOM 元素。

例子 3：头部删除，尾部新增

旧数组：[A, B, C]
新数组：[B, C, D]

头部比较：i 从 0 开始，比较 A 和 B，发现不同，跳出循环。i = 0。
尾部比较：e1 指向 C，e2 指向 D，发现不同，跳出循环。e1 = 2, e2 = 2
头部尾部循环结束，i = 0, e1 = 2, e2 = 2。此时 i <= e1 && i <= e2 成立, 走到 else 分支，进行乱序 diff。

表格总结

为了更清晰地展示头部/尾部优化的过程，我们可以用一个表格来总结：

步骤	条件	操作
头部比较	`i <= e1 && i <= e2 && isSameVNodeType(n1, n2)`	`patch(n1, n2)`，`i++`
尾部比较	`i <= e1 && i <= e2 && isSameVNodeType(n1, n2)`	`patch(n1, n2)`，`e1--`，`e2--`
新增节点	`i > e1 && i <= e2`	找到插入位置 `anchor`，循环插入 `newChildren[i]` 到 `anchor` 之前，`i++`
删除节点	`i > e2 && i <= e1`	循环卸载 `oldChildren[i]`，`i++`

`isSameVNodeType`：判断节点是否相同

在 patchKeyedChildren 函数中，isSameVNodeType 函数用于判断两个 VNode 是否可以复用。它主要比较以下几个方面：

类型（type）：例如都是 div，span，或者都是组件。
Key：如果都定义了 key 属性，则 key 值必须相同。

function isSameVNodeType(n1: VNode, n2: VNode): boolean {
  return n1.type === n2.type && n1.key === n2.key;
}

性能分析

头部/尾部优化之所以能提升性能，是因为它可以：

减少 DOM 操作：对于头部和尾部相同的节点，直接复用旧的 DOM 元素，避免了不必要的创建和销毁。
减少重排（reflow）：对于头部或尾部的新增节点，只需要插入到正确的位置，避免了大规模的元素移动。

深入思考

Key 的重要性：key 属性是 Diff 算法的关键。如果没有 key，Vue 只能通过索引来判断节点是否相同，这会导致很多不必要的 DOM 操作。所以，在列表渲染时，一定要加上 key 属性，并且 key 值要具有唯一性。
什么时候使用数组 Diff：只有当新旧 VNode 都是数组时，才会触发数组 Diff 算法。
patchKeyedChildren 的局限性：头部/尾部优化只能处理两端相同的节点。对于乱序移动的节点，需要使用更复杂的算法（最长递增子序列 Diff）。

总结

今天我们深入分析了 Vue 3 源码中 patch 函数的 Diff 算法，特别是针对数组头部/尾部移动的“快速路径”优化。

头部/尾部优化是 Vue 3 Diff 算法的第一步，也是最重要的一步。它可以快速处理常见的列表更新场景，提升应用的性能。

理解了这些原理，你就能更好地利用 Vue 3 的性能优化特性，写出更高效的代码。

下次有机会，我们再聊聊 Diff 算法的其他阶段，比如简单序列 Diff 和最长递增子序列 Diff。感谢大家的观看！