11.2 判断是否需要进行 DOM 移动操作

预处理后如果新旧子节点两边都还有剩余，就进入需要移动节点的非理想情况：先用 source 数组记录「新节点 → 旧节点索引」的映射，再用递增的 k 值（maxNewIndexSoFar）判断节点的相对顺序是否被打乱。

一、三种 Diff 算法的共同规则

无论是简单 Diff、双端 Diff 还是快速 Diff，都遵循同样的两条规则：

判断是否有节点需要移动，以及应该如何移动；
找出那些需要被添加或移除的节点。

快速 Diff 判断「是否需要移动」的思路与简单 Diff 类似：遍历过程中遇到的位置索引如果一直递增，说明相对顺序没变；一旦出现回退，就说明需要移动节点。

二、source 数组的作用

source 存储「新的一组子节点中的节点」在「旧的一组子节点」中的位置索引。
之后用 source 计算最长递增子序列，确定哪些节点不需要移动（见 11.3）。
source[i] === -1 表示下标 i 对应的新节点在旧节点中找不到可复用节点，是新增节点。

三、第一版：两层嵌套循环填充 source（O(n²)）

oldStart 与 newStart 都等于预处理结束后的 j；
count 为剩余未处理的新节点数量：newEnd - j + 1；
source 下标从 0 开始，而剩余节点的索引未必从 0 开始，所以用 k - newStart 作为下标。

} else {
  // 非理想情况
  const count = newEnd - j + 1
  const source = new Array(count)
  source.fill(-1)

  const oldStart = j
  const newStart = j

  for (let i = oldStart; i <= oldEnd; i++) {
    const oldVNode = oldChildren[i]
    for (let k = newStart; k <= newEnd; k++) {
      const newVNode = newChildren[k]
      // 找到拥有相同 key 值的可复用节点
      if (oldVNode.key === newVNode.key) {
        patch(oldVNode, newVNode, container)
        source[k - newStart] = i // 值 i 是该节点在旧节点中的位置索引
      }
    }
  }
}

source 的下标是新节点位置（k - newStart），值是旧节点位置 i，两者不要搞混。

四、优化：用索引表把复杂度降到 O(n)

两层嵌套循环的复杂度是 O(n1 × n2)，即 O(n²)。改进办法：先为新节点建一张 key → 位置索引 的索引表（keyIndex，Vue 源码中名为 keyToNewIndexMap），再遍历旧节点查表，两个 for 变成非嵌套关系，复杂度降为 O(n)。

const keyIndex = {}
for (let i = newStart; i <= newEnd; i++) {
  keyIndex[newChildren[i].key] = i
}

for (let i = oldStart; i <= oldEnd; i++) {
  const oldVNode = oldChildren[i]
  // 通过索引表快速找到新节点中相同 key 的位置
  const k = keyIndex[oldVNode.key]
  if (typeof k !== 'undefined') {
    const newVNode = newChildren[k]
    patch(oldVNode, newVNode, container)
    source[k - newStart] = i
  } else {
    // 索引表里查不到 → 该旧节点在新节点中已被删除
    unmount(oldVNode)
  }
}

五、判断是否需要移动：moved 与 pos

moved：初始 false，代表是否需要移动节点；
pos（Vue 源码中的 maxNewIndexSoFar）：初始 0，代表遍历旧节点过程中遇到的最大索引值 k；
判断规则：k < pos → 新节点索引出现回退，说明相对顺序被破坏 → moved = true；否则更新 pos = k；
patched：记录已经更新过的旧节点数量，达到需要更新的新节点数量 count 后，多出来的旧节点一律卸载。

let moved = false // 是否需要移动节点
let pos = 0 // 遍历旧节点过程中遇到的最大索引值 k
let patched = 0 // 已更新的旧节点数量

for (let i = oldStart; i <= oldEnd; i++) {
  const oldVNode = oldChildren[i]
  if (patched < count) {
    const k = keyIndex[oldVNode.key]
    if (typeof k !== 'undefined') {
      const newVNode = newChildren[k]
      patch(oldVNode, newVNode, container)
      patched++
      source[k - newStart] = i
      if (k < pos) {
        // 索引回退 → 需要移动节点
        moved = true
      } else {
        pos = k
      }
    } else {
      unmount(oldVNode)
    }
  } else {
    // 新节点已全部处理完，剩余的旧节点是多余的
    unmount(oldVNode)
  }
}

source 被填充（值不为 -1）只说明该新节点能复用某个旧节点；真正判断「要不要移动」的是 pos / moved。 pos 只记录最大值：只要后续的 k 一直不小于 pos，顺序就没变过；一旦小于 pos，就必然存在需要移动的节点。

六、示例

旧：1 2 3 4 6 5；新：1 3 4 2 7 5
预处理：前置只复用 key1；后置只复用 key5
剩余新节点：3 4 2 7 → count = 4，newStart = 1
keyIndex = { 3: 1, 4: 2, 2: 3, 7: 4 }

i（旧索引）	oldVNode.key	k	source 变化	moved / pos
1	2	3	`source[2] = 1`	`k=3 > pos=0` → `pos = 3`
2	3	1	`source[0] = 2`	`k=1 < pos=3` → `moved = true`
3	4	2	`source[1] = 3`	`k=2 < pos=3` → `moved = true`
4	6	查不到	不变	找不到 → `unmount`

最终 source = [2, 3, 1, -1]、moved = true；其中 -1（下标 3）对应 key7，是新增节点。

七、易错点

source[k - newStart] = i：下标是新节点位置（与 newStart 的差值），值是旧节点位置 i。卸载有两处：索引表查不到（旧节点被删除）、patched 超出 count（多余的旧节点），两处都要调用 unmount。 patched 与 count 的比较：已更新数达到待更新数后，剩余旧节点的 key 已不可能命中索引表，直接卸载即可（patched < count 与 patched <= count 在此等价）。