vue diff实现

Vue 的 Diff 算法实现

Vue 的虚拟 DOM Diff 算法（即 patch 过程）通过高效比较新旧虚拟节点（VNode）来最小化 DOM 操作。其核心逻辑基于 同层比较 和 双端比较 策略，以下是关键实现要点：

核心流程

同层比较
Diff 只在同一层级的 VNode 间进行，跨层级移动节点会直接销毁并重建，避免递归遍历带来的性能损耗。

双端比较
通过四个指针（新旧节点的头尾索引）逐步向中间靠拢，优先处理以下四种简单情况：

1. 旧头 vs 新头
2. 旧尾 vs 新尾
3. 旧头 vs 新尾
4. 旧尾 vs 新头

若均不匹配，则通过 key 查找可复用的节点。

关键代码逻辑

1. 节点复用条件
判断两个 VNode 是否可复用：

function sameVnode(a, b) {
  return (
    a.key === b.key && // key 相同
    a.tag === b.tag && // 标签类型相同
    a.isComment === b.isComment && // 注释节点相同
    isDef(a.data) === isDef(b.data) && // 数据属性存在性一致
    sameInputType(a, b) // 输入类型相同（针对 input 元素）
  )
}

2. 双端比较实现
以下是简化后的核心逻辑：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (isUndef(oldStartVnode)) {
    oldStartVnode = oldCh[++oldStartIdx]
  } 
  else if (isUndef(oldEndVnode)) {
    oldEndVnode = oldCh[--oldEndIdx]
  }
  // 情况1：旧头 == 新头
  else if (sameVnode(oldStartVnode, newStartVnode)) {
    patchVnode(oldStartVnode, newStartVnode)
    oldStartVnode = oldCh[++oldStartIdx]
    newStartVnode = newCh[++newStartIdx]
  }
  // 情况2：旧尾 == 新尾
  else if (sameVnode(oldEndVnode, newEndVnode)) {
    patchVnode(oldEndVnode, newEndVnode)
    oldEndVnode = oldCh[--oldEndIdx]
    newEndVnode = newCh[--newEndIdx]
  }
  // 情况3：旧头 == 新尾（节点右移）
  else if (sameVnode(oldStartVnode, newEndVnode)) {
    patchVnode(oldStartVnode, newEndVnode)
    insertBefore(parentElm, oldStartVnode.elm, nextSibling(oldEndVnode.elm))
    oldStartVnode = oldCh[++oldStartIdx]
    newEndVnode = newCh[--newEndIdx]
  }
  // 情况4：旧尾 == 新头（节点左移）
  else if (sameVnode(oldEndVnode, newStartVnode)) {
    patchVnode(oldEndVnode, newStartVnode)
    insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
    oldEndVnode = oldCh[--oldEndIdx]
    newStartVnode = newCh[++newStartIdx]
  }
  // 情况5：通过 key 查找可复用节点
  else {
    const idxInOld = findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
    if (isUndef(idxInOld)) {
      createElm(newStartVnode, parentElm, oldStartVnode.elm)
    } 
    else {
      const vnodeToMove = oldCh[idxInOld]
      patchVnode(vnodeToMove, newStartVnode)
      insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
      oldCh[idxInOld] = undefined
    }
    newStartVnode = newCh[++newStartIdx]
  }
}

3. 剩余节点处理
循环结束后，若新旧节点列表有剩余：

• 新列表有剩余：批量新增节点
• 旧列表有剩余：批量删除节点

优化策略

key 的作用
key 是节点复用的关键标识。若未设置 key，Vue 会默认按位置复用，可能导致状态错乱或性能下降。

静态节点标记
编译阶段标记静态节点（isStatic），Diff 时直接跳过比较，提升性能。

复杂度分析

• 最优情况：头尾匹配时达到 O(n) 复杂度。
• 最差情况：无 key 或乱序时退化为 O(n²)，但实际场景中通过 key 优化可避免。

通过这种策略，Vue 在大多数实际应用中能高效更新 DOM，减少不必要的渲染开销。