第 5 章 · runtime-core（三）：更新与 diff——patch 的第二人生

第 3 章跳过了所有 n1 !== null 的分支，现在回来补上。更新链路从数据变化开始：

count.value++ → trigger → 渲染 effect 的 scheduler → 微任务队列 → instance.update()
  → render 重新执行 → 新 subTree
  → patch(旧subTree, 新subTree)
       └─ patchElement
            ├─ patchProps        # 对比属性
            └─ patchChildren     # 对比孩子 —— 双端 diff 在这里

阅读策略：从外往里剥洋葱——先看两棵树怎么对齐（同类型才细比），再看单个元素怎么比（props/children），最后攻 diff 这道算法题。

5.1 patch 的对齐规则：类型不同,直接放弃治疗

更新时 patch(n1, n2) 的第一件事是判断新旧节点"是不是同一个东西"：

function isSameVNodeType(n1, n2) {
  return n1.type === n2.type && n1.key === n2.key
}

function patch(n1, n2, container, parentComponent, anchor) {
  if (n1 && !isSameVNodeType(n1, n2)) {
    // div 变成了 p？拆掉重建，不做精细对比
    unmount(n1)
    n1 = null            // ★ 置 null 后走挂载分支——更新退化为挂载
  }
  // ...后续与第 3 章相同的分发
}

为什么类型不同就整棵放弃：理论上 div→p 也可以搬运孩子，但"类型都变了、子树大概率也面目全非"是一个统计上划算的假设。React 的 reconciliation 有同样的启发式。diff 算法的第一课不是算法,是"接受 O(n³) 最优解不可行,用启发式换 O(n)"的工程决断（两棵树的最小编辑距离是 O(n³) 的,Vue/React 都靠"同层比较 + 类型不同即重建 + key 提示身份"三条假设砍到 O(n)）。

n1 = null 那行的手法回味一下:把"重建"表达为"当作首次挂载",不写第二套逻辑——第 3 章说过"挂载是更新的退化情形",这里是反向运用。

5.2 patchElement 之一：patchProps

function patchElement(n1, n2, parentComponent, anchor) {
  const oldProps = n1.props ?? {}
  const newProps = n2.props ?? {}
  const el = (n2.el = n1.el)     // ★ 新 vnode 继承真实 DOM 引用（第 3 章埋的桥）

  patchChildren(n1, n2, el, parentComponent, anchor)
  patchProps(el, oldProps, newProps)
}

function patchProps(el, oldProps, newProps) {
  // 遍历新的：值变了 → 更新；新增 → 添加
  for (const key in newProps) {
    const prev = oldProps[key]
    const next = newProps[key]
    if (prev !== next) hostPatchProp(el, key, prev, next)
  }
  // 遍历旧的：新的里没有 → 删除
  for (const key in oldProps) {
    if (!(key in newProps)) hostPatchProp(el, key, oldProps[key], null)
  }
}

n2.el = n1.el 是更新链路的第一行也是最重要的一行：新 vnode 是 render 刚产出的纯数据，不知道自己对应页面上哪个元素；旧 vnode 知道（挂载时回填的）。这行"传家宝交接"之后,下一轮更新时 n2 又成了别人的 n1。漏掉它,更新第二次就全线崩——初学者手写 mini-vue 最高频的 bug。

两次遍历的模式：对比两个键值集合,标准解法就是"正向遍历新集合处理增/改,反向遍历旧集合处理删"。这个模式在 patchChildren 的乱序区、在真源码的 class/style 对比里反复出现。注意删除时传 null 作为 next——回看第 3 章 runtime-dom 的 patchProp,nextVal == null 走 removeAttribute 分支,接口两端又一次成对咬合。

5.3 patchElement 之二：patchChildren——先处理 4 种形态组合

children 只有两种形态（文本 / 数组）,新旧组合共 4 种。diff 只发生在"数组 → 数组"一种情况里,先把另外三种简单情况写完——这个"先枚举簿记情形、把难题隔离到最后一个分支"的写法本身就值得学：

function patchChildren(n1, n2, container, parentComponent, anchor) {
  const prevShapeFlag = n1.shapeFlag
  const { shapeFlag } = n2

  if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
    // 新的是文本
    if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
      unmountChildren(n1.children)               // 数组→文本：先拆旧孩子
    }
    if (n1.children !== n2.children) {
      hostSetElementText(container, n2.children) // 文本→文本：直接换字
    }
  } else {
    // 新的是数组
    if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
      hostSetElementText(container, '')          // 文本→数组：清字
      mountChildren(n2.children, container, parentComponent)  // 全量挂载
    } else {
      // ★ 数组→数组：唯一需要 diff 的情况
      patchKeyedChildren(n1.children, n2.children, container, parentComponent, anchor)
    }
  }
}

5.4 双端 diff：一道"双指针 + 哈希表 + LIS"的算法综合题

问题定义

旧孩子数组 c1、新孩子数组 c2,元素带 key。要求把 DOM 从 c1 的状态变成 c2 的状态,尽量复用节点（同 key 的 patch 而不是重建）、尽量少移动 DOM（DOM 移动比 JS 计算贵几个量级）。

总策略：先易后难,层层缩小问题规模

现实中的列表更新绝大多数是"头部插入一条""尾部追加一条""删中间一条"——两端大概率是稳定的。算法据此分五步,前四步用 O(1) 判断吃掉简单情形,只有真正乱序的中段才动用重型武器：

步骤1  头对头比：  相同就 patch,指针 i 右移,直到不同
步骤2  尾对尾比：  相同就 patch,e1/e2 左移,直到不同
步骤3  旧的先耗尽（i > e1）→ 新的剩余部分全是新增,挂载
步骤4  新的先耗尽（i > e2）→ 旧的剩余部分全是多余,删除
步骤5  中间乱序区 → 建索引表 + 标记复用 + LIS 求最少移动

步骤 1-4 的代码

function patchKeyedChildren(c1, c2, container, parentComponent, parentAnchor) {
  let i = 0
  let e1 = c1.length - 1
  let e2 = c2.length - 1

  // ---- 步骤1：左端同步 ----
  while (i <= e1 && i <= e2) {
    if (!isSameVNodeType(c1[i], c2[i])) break
    patch(c1[i], c2[i], container, parentComponent, parentAnchor)  // 同节点,递归细比
    i++
  }

  // ---- 步骤2：右端同步 ----
  while (i <= e1 && i <= e2) {
    if (!isSameVNodeType(c1[e1], c2[e2])) break
    patch(c1[e1], c2[e2], container, parentComponent, parentAnchor)
    e1--; e2--
  }

  if (i > e1) {
    // ---- 步骤3：旧的耗尽,新的还有 → 挂载新增 ----
    if (i <= e2) {
      // ★ anchor：插在"新序列中下一个已就位节点"的前面
      const nextPos = e2 + 1
      const anchor = nextPos < c2.length ? c2[nextPos].el : null
      while (i <= e2) {
        patch(null, c2[i], container, parentComponent, anchor)
        i++
      }
    }
  } else if (i > e2) {
    // ---- 步骤4：新的耗尽,旧的还有 → 删除多余 ----
    while (i <= e1) {
      hostRemove(c1[i].el)
      i++
    }
  } else {
    // ---- 步骤5：中间乱序区,见下 ----
  }
}

anchor 参数为什么此时才登场：挂载新节点时,insert(el, container) 只能追加到末尾。头部插入的场景（a b → c a b,步骤 1、2 都比不动,直接进步骤 3）需要"插到 a 前面"——insertBefore 需要参照物。参照物哪里找？新序列里紧挨着新增区右边的那个节点（c2[e2+1]）一定已经在 DOM 里（它要么属于步骤 2 已处理的稳定尾部,要么本来就在）,拿它的 el 做 anchor。这就是为什么 patch/insert 的签名从第 3 章开始就拖着一个大多数时候是 null 的 anchor 参数——为最难的调用方设计签名,简单调用方传 null。

步骤 5：乱序区

三个子任务：旧有新无 → 删；两边都有 → patch + 可能移动；旧无新有 → 挂载。

  } else {
    const s1 = i          // 乱序区在旧数组的起点
    const s2 = i          // 乱序区在新数组的起点

    // ① key → 新索引 的哈希表：O(1) 判断"旧节点还在不在"
    const keyToNewIndexMap = new Map()
    for (let j = s2; j <= e2; j++) keyToNewIndexMap.set(c2[j].key, j)

    // ② newIndexToOldIndexMap[新区内下标] = 旧下标+1；0 表示"新增,旧里没有"
    const toBePatched = e2 - s2 + 1
    const newIndexToOldIndexMap = new Array(toBePatched).fill(0)

    let moved = false
    let maxNewIndexSoFar = 0
    let patched = 0

    // ③ 遍历旧乱序区：删 or patch
    for (let j = s1; j <= e1; j++) {
      const prevChild = c1[j]

      if (patched >= toBePatched) {        // 新的已全部对上号,剩下的旧节点必删
        hostRemove(prevChild.el)
        continue
      }

      // 找这个旧节点在新序列里的位置
      let newIndex
      if (prevChild.key != null) {
        newIndex = keyToNewIndexMap.get(prevChild.key)     // O(1)
      } else {
        for (let k = s2; k <= e2; k++) {                   // 没 key：O(n) 硬找
          if (isSameVNodeType(prevChild, c2[k])) { newIndex = k; break }
        }
      }

      if (newIndex === undefined) {
        hostRemove(prevChild.el)           // 新序列里没有 → 删
      } else {
        // 顺便检测"相对顺序是否被打乱"：newIndex 一旦不再单调递增,就存在移动
        if (newIndex >= maxNewIndexSoFar) maxNewIndexSoFar = newIndex
        else moved = true

        newIndexToOldIndexMap[newIndex - s2] = j + 1   // +1 是为了把 0 留给"新增"
        patch(prevChild, c2[newIndex], container, parentComponent, null)
        patched++
      }
    }

    // ④ 求最长递增子序列：这些位置的节点相对顺序没乱,可以不动
    const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : []
    let j = increasingNewIndexSequence.length - 1

    // ⑤ 从右往左遍历新乱序区：挂载新增 / 移动错位
    for (let k = toBePatched - 1; k >= 0; k--) {
      const nextIndex = s2 + k
      const nextChild = c2[nextIndex]
      const anchor = nextIndex + 1 < c2.length ? c2[nextIndex + 1].el : null

      if (newIndexToOldIndexMap[k] === 0) {
        patch(null, nextChild, container, parentComponent, anchor)   // 新增
      } else if (moved) {
        if (j < 0 || k !== increasingNewIndexSequence[j]) {
          hostInsert(nextChild.el, container, anchor)                // 移动
        } else {
          j--                                                        // 在 LIS 里,不动
        }
      }
    }
  }

逐段解释（这段代码信息密度全书最高,慢读）

① 哈希表换扫描：没有它,每个旧节点找新位置是 O(n),整段 O(n²)。这就是列表必须写 key 的机器视角理由——有 key 走 Map 的 O(1),没 key 退化到内层 for。（key 用 index 为什么坏事？index-key 在头部插入时全体错位,isSameVNodeType 全判"相同",导致逐个 patch 内容而不是移动节点,复用彻底失效——现在你能从代码层面解释这道高频面试题了。）

② +1 留 0 的编码技巧：newIndexToOldIndexMap 要同时表达"对应旧节点的下标"和"没有对应（新增）"两种信息。旧下标本身可以是 0,于是全体 +1,腾出 0 做哨兵。用值域腾挪塞进带外信息——和算法题里"用负号标记访问过"同一族。

③ moved 的检测：如果旧节点们在新序列里的位置 newIndex 是单调递增的,说明相对顺序没变,一个都不用移（也就不必算 LIS——moved ? getSequence(...) : [] 这个短路是纯优化）。一旦出现逆序,moved = true。

④ 为什么是最长递增子序列：能"不动"的节点集合,必须在新旧两个序列里保持相同的相对顺序——对应到 newIndexToOldIndexMap（按新位置排列的旧下标）上,就是一个递增子序列。想移动次数最少,就要"不动的"最多,即最长递增子序列。LIS 之外的节点逐个 insertBefore 到位。这是 LeetCode 300 的工业应用现场,mini-vue 的 getSequence 用的是 O(n log n) 贪心+二分,还额外回溯出下标序列（不只是长度）——比裸题多一步,值得亲手实现。

⑤ 为什么从右往左遍历：移动/插入都靠 anchor（插到某节点前面）,而 anchor 必须是已经就位的节点。从右往左处理,位置 k 的 anchor（位置 k+1 的节点）要么属于稳定尾部、要么上一轮刚处理完——永远可用。从左往右则 anchor 还没就位。处理顺序由依赖方向决定：每一步依赖右邻,就从最右开始。

拿纸笔手推一遍（不做这步等于没读）

c1: a b [c d e] f g          c2: a b [e c d] f g
步骤1: a、b 相同 → i=2 停在 c≠e
步骤2: g、f 相同 → e1=4, e2=4 停在 e≠d
乱序区  旧: c(2) d(3) e(4)    新: e(2) c(3) d(4)    s1=s2=2, toBePatched=3

① keyToNewIndexMap: {e→2, c→3, d→4}
③ 遍历旧: c→newIndex=3, max=3        map=[0,4,0]  (记 3+1)
          d→newIndex=4, max=4        map=[0,4,5]... 

  （按 map[newIndex-s2]=旧下标+1 逐个填：
     c: map[1]=3   d: map[2]=4   e: map[0]=5 且 2<max=4 → moved=true）
  最终 newIndexToOldIndexMap = [5, 3, 4]

④ LIS of [5,3,4] → 值 [3,4] → 下标序列 [1,2]
⑤ 从右往左:
   k=2 (d): map[2]=4≠0, moved, k===seq[j=1]=2 → 不动, j=0
   k=1 (c): map[1]=3≠0, k===seq[0]=1        → 不动, j=-1
   k=0 (e): map[0]=5≠0, j<0                 → 移动! insertBefore(e.el, c.el)

结论: 7 个节点的重排,DOM 操作只有一次 —— 把 e 移到 c 前面。

自己再推一组 a b c → b c a（答案：移动 a 一次,而不是移动 b、c 两次）,推对了这一节才算过关。

5.5 组件的更新：props 变了怎么办

元素更新讲完了,组件 vnode 的更新（父组件重渲染,给子组件传的 props 变了）走另一条路：

function updateComponent(n1, n2) {
  const instance = (n2.component = n1.component)   // 实例传家宝交接（同 el）
  if (shouldUpdateComponent(n1, n2)) {             // props 真变了才更新
    instance.next = n2          // ★ 把"下一个 vnode"寄存到实例上
    instance.update()           // 手动触发它的渲染 effect（就是 setupRenderEffect 返回的 runner）
  } else {
    n2.el = n1.el
    instance.vnode = n2
  }
}

渲染 effect 里相应多了一段（第 3 章 setupRenderEffect 的更新分支开头）：

const { next, vnode } = instance
if (next) {
  next.el = vnode.el
  updateComponentPreRender(instance, next)   // instance.vnode = next; instance.props = next.props
}

为什么绕一圈用 instance.next 寄存,而不是直接改 props？ 因为"重新渲染"这个动作只有一个入口——instance.update（那个 effect runner）,数据变化触发它、父组件更新也触发它。父更新场景需要在 render 之前先换掉 props,于是把新 vnode 挂在 next 上,effect 里检查到有 next 就先做换血。所有更新殊途同归到同一个入口,入口前用字段传递"额外行李"——这个模式在 React 的 fiber.pendingProps 上也能看到。

5.6 scheduler 与 nextTick：更新为什么是异步的

失败用例

it('nextTick', async () => {
  const count = ref(0)
  const spy = vi.fn()
  effect(() => { spy(); count.value })  // 想象这是组件的渲染 effect

  for (let i = 0; i < 100; i++) count.value++
  expect(spy).toHaveBeenCalledTimes(1)  // ★ 同步改 100 次,只渲染了最初那 1 次

  await nextTick()
  expect(spy).toHaveBeenCalledTimes(2)  // 微任务里补了 1 次——总共 2 次,而不是 101 次
})

实现

// scheduler.ts
const queue: any[] = []
let isFlushPending = false
const p = Promise.resolve()

export function queueJobs(job) {
  if (!queue.includes(job)) queue.push(job)   // ★ 去重：同一个组件排一次就够
  queueFlush()
}

function queueFlush() {
  if (isFlushPending) return                  // ★ 一个微任务在途,不再重复安排
  isFlushPending = true
  p.then(() => {
    isFlushPending = false
    let job
    while ((job = queue.shift())) job()
  })
}

export function nextTick(fn?) {
  return fn ? p.then(fn) : p
}

组件的渲染 effect 传的 scheduler 就是 () => queueJobs(instance.update)（第 3 章末尾）。串起来：

count.value++  ×100
  → trigger ×100 → scheduler ×100
      → queueJobs：前 1 次入队,后 99 次被 includes 挡掉
      → queueFlush：第 1 次安排微任务,后 99 次被 isFlushPending 挡掉
  同步代码跑完 → 微任务执行 → instance.update() 跑 1 次 → render + patch 1 次

两级去重（任务去重 + 冲刷去重）是这 20 行的全部内容。nextTick(fn) 则朴素得可爱：把你的 fn 也排到同一个 Promise 的 then 链上——微任务 FIFO,排在刷新任务之后,所以 fn 执行时 DOM 已更新。"为什么 nextTick 能拿到最新 DOM"这道面试题,答案就是"因为它和更新任务共用一个 Promise,且排在后面"。

自测

n2.el = n1.el 为什么是更新链路的命根子？组件更新里对应的"传家宝交接"是哪行？
双端 diff 五个步骤各处理什么情形？为什么先比两端？
newIndexToOldIndexMap 为什么要 +1？moved 标志怎么检测出来的？
为什么"最少移动"归结为 LIS？步骤⑤为什么必须从右往左？
key 用 index 会导致什么？用代码层面的机制解释（提示：isSameVNodeType + keyToNewIndexMap）。
同步改 100 次数据只 render 一次,靠哪两级去重？nextTick 为什么能拿到新 DOM？
（手撕）实现 getSequence（O(n log n),返回下标序列）,用 [5,3,4]、[10,9,2,5,3,7,101,18] 验证。

05-runtime-更新与diff