Diff算法与Patch过程

Vue采用双端对比Diff算法，通过 sameVNode 快速判断，递归patch子节点实现最小DOM操作。

sameVNode 节点对比

function sameVNode(a, b): boolean {
  return (
    a.key === b.key &&
    a.tag === b.tag &&
    a.isComment === b.isComment &&
    isDef(a.data) === isDef(b.data) &&
    sameInputType(a, b)
  )
}

key和tag相同认为是同一节点，可复用DOM，只更新属性。

patch 入口

function patch(oldVnode, vnode, hydrating) {
  if (isUndef(vnode)) {
    // 新VNode为空，销毁旧节点
    if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
    return
  }
  
  let isInitialPatch = false
  
  if (isRealElement(oldVnode)) {
    // 首次渲染: 真实DOM转为VNode
    oldVnode = emptyNodeAt(oldVnode)
  }
  
  if (sameVnode(oldVnode, vnode)) {
    // 同类型节点: 对比更新
    patchVnode(oldVnode, vnode, insertedVnodeQueue)
  } else {
    // 不同类型: 替换节点
    const oldElm = oldVnode.elm
    const parentElm = nodeOps.parentNode(oldElm)
    createElm(vnode, insertedVnodeQueue, parentElm, nodeOps.nextSibling(oldElm))
    removeVnodes(parentElm, [oldVnode], 0, 0)
  }
  
  return vnode.elm
}

同类型节点调用 patchVnode 更新，不同类型创建新的替换旧的。

patchVNode 节点更新

function patchVnode(oldVnode, vnode, insertedVnodeQueue) {
  vnode.elm = oldVnode.elm  // 复用DOM
  
  if (isDef(vnode.data)) {
    invokeUpdateHooks(oldVnode, vnode)
  }
  
  const oldCh = oldVnode.children
  const ch = vnode.children
  
  if (isUndef(vnode.text)) {
    if (isDef(oldCh) && isDef(ch)) {
      // 都有子节点: diff子节点
      if (oldCh !== ch) updateChildren(elm, oldCh, ch)
    } else if (isDef(ch)) {
      // 新有子节点: 创建新子节点
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
      addVnodes(elm, null, ch, 0, ch.length - 1)
    } else if (isDef(oldCh)) {
      // 旧有子节点: 移除旧子节点
      removeVnodes(elm, oldCh, 0, oldCh.length - 1)
    } else {
      // 都无子节点: 清空文本
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
    }
  } else {
    // 新节点有文本: 替换
    if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, vnode.text)
  }
}

四种情况：都有子节点diff、新有创建、旧有移除、清空文本。

updateChildren 子节点Diff

function updateChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0
  let newStartIdx = 0
  let oldEndIdx = oldCh.length - 1
  let newEndIdx = newCh.length - 1
  
  let oldStartVnode = oldCh[0]
  let oldEndVnode = oldCh[oldEndIdx]
  let newStartVnode = newCh[0]
  let newEndVnode = newCh[newEndIdx]
  
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (isUndef(oldStartVnode)) {
      oldStartVnode = oldCh[++oldStartIdx]
    } else if (isUndef(oldEndVnode)) {
      oldEndVnode = oldCh[--oldEndIdx]
    }
    // 四种对比
    else if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      patchVnode(oldStartVnode, newEndVnode)
      nodeOps.insertBefore(parentElm, oldStartVnode.elm, oldEndVnode.elm.nextSibling)
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      patchVnode(oldEndVnode, newStartVnode)
      nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    } else {
      // 都不匹配: 按key查找
      const idxInOld = findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
      if (isUndef(idxInOld)) {
        createElm(newStartVnode, parentElm, oldStartVnode.elm)
      } else {
        const vnodeToMove = oldCh[idxInOld]
        patchVnode(vnodeToMove, newStartVnode)
        oldCh[idxInOld] = undefined
        nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
      }
      newStartVnode = newCh[++newStartIdx]
    }
  }
  
  // 循环结束处理
  if (oldStartIdx > oldEndIdx) {
    // 旧节点先遍历完: 添加新节点
    addVnodes(parentElm, newCh[newEndIdx + 1]?.elm, newCh, newStartIdx, newEndIdx)
  } else {
    // 新节点先遍历完: 移除旧节点
    removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
  }
}

双端对比：头头、尾尾、头尾、尾头四种情况，都不匹配时按key查找。

四种对比场景

// 1. 头头相同: A B C D -> A E F
//    A复用，指针都后移

// 2. 尾尾相同: A B C D -> E F D
//    D复用，指针都前移

// 3. 头尾相同: A B C D -> D E F
//    A移到末尾，oldStart后移，newEnd前移

// 4. 尾头相同: A B C D -> D E F
//    D移到开头，oldEnd前移，newStart后移

通过四种对比最小化DOM移动操作。

要点总结

• sameVNode 通过key和tag判断是否同一节点可复用
• patch对比同类型调用 patchVnode，不同类型创建替换
• patchVnode 处理四种子节点情况：都有、新有、旧有、都无
• updateChildren 双端对比：头头、尾尾、头尾、尾头
• 都不匹配时通过key在旧节点中查找可复用节点
• 遍历结束旧多移除、新多添加