Vue 3 源码笔记：Diff 算法深度解析 (patchKeyedChildren)

const patchKeyedChildren = (
  oldChildren: any[],
  newChildren: any[],
  container: Element,
  parentAnchor?: Element | null,
) => {
  let i = 0;
  const oldLen = oldChildren.length;
  const newLen = newChildren.length;
  let oldEnd = oldLen - 1;
  let newEnd = newLen - 1;

  // -------------------------------------------------------------
  // 1. 从头同步 (Sync from Start)
  // -------------------------------------------------------------
  while (i <= oldEnd && i <= newEnd) {
    const oldVNode = (oldChildren[i] = normalizeVNode(oldChildren[i]));
    const newVNode = (newChildren[i] = normalizeVNode(newChildren[i]));

    if (isSameVNodeType(oldVNode, newVNode)) {
      patch(oldVNode, newVNode, container);
    } else {
      break;
    }
    i++;
  }

  // -------------------------------------------------------------
  // 2. 从尾同步 (Sync from End)
  // -------------------------------------------------------------
  while (i <= oldEnd && i <= newEnd) {
    const oldVNode = (oldChildren[oldEnd] = normalizeVNode(
      oldChildren[oldEnd],
    ));
    const newVNode = (newChildren[newEnd] = normalizeVNode(
      newChildren[newEnd],
    ));
    if (isSameVNodeType(oldVNode, newVNode)) {
      patch(oldVNode, newVNode, container);
    } else {
      break;
    }
    oldEnd--;
    newEnd--;
  }

  // -------------------------------------------------------------
  // 3. 普通序列 - 新增挂载 (Mount New)
  // -------------------------------------------------------------
  if (i > oldEnd) {
    // 新节点多于旧节点（挂载）
    // 此时 oldEnd < i
    if (i <= newEnd) {
      // 计算锚点：如果后面还有节点，插在它前面；否则插在 container 末尾
      const anchor = newEnd + 1 < newLen ? newChildren[newEnd + 1].el : null;
      while (i <= newEnd) {
        patch(
          null,
          (newChildren[i] = normalizeVNode(newChildren[i])),
          container,
          anchor,
        );
        i++;
      }
    }
  }
  // -------------------------------------------------------------
  // 4. 普通序列 - 删除多余 (Unmount Old)
  // -------------------------------------------------------------
  else if (i > newEnd) {
    // 旧节点多于新节点（卸载）
    // 此时 newEnd < i
    while (i <= oldEnd) {
      unmount(oldChildren[i]);
      i++;
    }
  }
  // -------------------------------------------------------------
  // 5. 乱序序列 (Unknown Sequence) - 核心难点
  // -------------------------------------------------------------
  else {
    // 旧子节点的开始索引
    const oldStartIndex = i;
    // 新子节点的开始索引
    const newStartIndex = i;

    // -----------------------------------------------------------
    // 5.1 构建 Map: { newKey : newIndex }
    // -----------------------------------------------------------
    const keyToNewIndexMap = new Map();
    for (i = newStartIndex; i <= newEnd; i++) {
      const nextChild = normalizeVNode(newChildren[i]);
      if (nextChild.key != null) {
        keyToNewIndexMap.set(nextChild.key, i);
      }
    }

    // -----------------------------------------------------------
    // 5.2 遍历旧节点: Patch 或 Unmount
    // -----------------------------------------------------------
    let j;
    let patched = 0; // 已复用数量
    const toBePatched = newEnd - newStartIndex + 1; // 待处理总数
    let moved = false; // 是否需要移动
    let maxNewIndexSoFar = 0; // 记录遇到的最大新索引，判断是否递增

    // newIndexToOldIndexMap: 索引是新位置，值是 oldIndex + 1
    const newIndexToOldIndexMap = new Array(toBePatched);
    for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0;

    for (i = oldStartIndex; i <= oldEnd; i++) {
      const prevChild = oldChildren[i];

      // 优化：如果新节点已经找齐了，剩下的旧节点直接删
      if (patched >= toBePatched) {
        unmount(prevChild);
        continue;
      }

      let newIndex;
      if (prevChild.key != null) {
        newIndex = keyToNewIndexMap.get(prevChild.key);
      } else {
        // 无 key 查找逻辑 (尝试寻找相同 type 的无 key 节点)
        for (j = newStartIndex; j <= newEnd; j++) {
          if (
            newIndexToOldIndexMap[j - newStartIndex] === 0 &&
            isSameVNodeType(prevChild, newChildren[j])
          ) {
            newIndex = j;
            break;
          }
        }
      }

      // 没找到 -> 删除
      if (newIndex === undefined) {
        unmount(prevChild);
      }
      // 找到了 -> 复用 Patch
      else {
        newIndexToOldIndexMap[newIndex - newStartIndex] = i + 1;

        // 检查是否递增
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex;
        } else {
          moved = true; // 乱序了
        }

        patch(prevChild, newChildren[newIndex], container, null);
        patched++;
      }
    }

    // -----------------------------------------------------------
    // 5.3 移动与挂载 (LIS Algorithm)
    // -----------------------------------------------------------
    // 计算最长递增子序列
    const increasingNewIndexSequence = moved
      ? getSequence(newIndexToOldIndexMap)
      : [];
    j = increasingNewIndexSequence.length - 1;

    // 倒序遍历
    for (i = toBePatched - 1; i >= 0; i--) {
      const nextIndex = newStartIndex + i;
      const nextChild = newChildren[nextIndex];
      // 计算锚点：插在后一个节点前面
      const anchor =
        nextIndex + 1 < newLen ? newChildren[nextIndex + 1].el : parentAnchor;

      // 情况 A: 是新节点 (值为0) -> 挂载
      if (newIndexToOldIndexMap[i] === 0) {
        patch(null, nextChild, container, anchor);
      }
      // 情况 B: 需要移动
      else if (moved) {
        // 如果不在 LIS 中，或者 LIS 已用完 -> 移动
        if (j < 0 || i !== increasingNewIndexSequence[j]) {
          move(nextChild, container, anchor);
        } else {
          // 在 LIS 中 -> 不动
          j--;
        }
      }
    }
  }
};