VueにおけるDiffアルゴリズムは、仮想DOMの比較と更新を行うpatch関数によって実現されます。

1. patch関数

patch関数は主に以下の4つの引数を取りますが、主なのは最初の2つです。

• oldVnode: 旧の仮想DOMノード
• vnode: 新しい仮想DOMノード
• hydrating: サーバーサイドレンダリング用のフラグ
• removeOnly: transition-groupコンポーネント用のフラグ

主な処理フローは以下の通りです。

• vnodeが存在せず、oldVnodeが存在する場合、oldVnodeを削除します。
• vnodeが存在し、oldVnodeが存在しない場合、vnodeを作成します。
• 両方が存在する場合は、sameVnode関数を使用して同じノードであるかを確認します。
• 同じノードである場合は、patchVnode関数でテキストや子ノードの変更を確認します。
• 異なるノードである場合は、vnodeをoldVnodeの親ノードにマウントします。
• コンポーネントのルートノードが置き換えられた場合、親ノードを更新し古いノードを削除します。
• サーバーサイドレンダリングの場合、hydratingを使用してoldVnodeと実際のDOMをミックスします。

以下にpatch関数のソースコードを示します。

function isUndef(v) {
  return v === undefined || v === null;
}

function isDef(v) {
  return v !== undefined && v !== null;
}

return function patch(oldVnode, vnode, hydrating, removeOnly) {
  if (isUndef(vnode)) {
    if (isDef(oldVnode)) invokeDestroyHook(oldVnode);
    return;
  }

  let isInitialPatch = false;
  const insertedVnodeQueue = [];

  if (isUndef(oldVnode)) {
    isInitialPatch = true;
    createElm(vnode, insertedVnodeQueue);
  } else {
    const isRealElement = isDef(oldVnode.nodeType);

    if (!isRealElement && sameVnode(oldVnode, vnode)) {
      patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly);
    } else {
      if (isRealElement) {
        if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
          oldVnode.removeAttribute(SSR_ATTR);
          hydrating = true;
        }
        if (hydrating) {
          if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
            invokeInsertHook(vnode, insertedVnodeQueue, true);
            return oldVnode;
          } else if (process.env.NODE_ENV !== 'production') {
            warn('長い警告メッセージ');
          }
        }
        oldVnode = emptyNodeAt(oldVnode);
      }

      const oldElm = oldVnode.elm;
      const parentElm = nodeOps.parentNode(oldElm);

      createElm(
        vnode,
        insertedVnodeQueue,
        oldElm._leaveCb ? null : parentElm,
        nodeOps.nextSibling(oldElm)
      );

      if (isDef(vnode.parent)) {
        let ancestor = vnode.parent;
        const patchable = isPatchable(vnode);
        while (ancestor) {
          for (let i = 0; i < cbs.destroy.length; ++i) {
            cbs.destroy[i](ancestor);
          }
          ancestor.elm = vnode.elm;
          if (patchable) {
            for (let i = 0; i < cbs.create.length; ++i) {
              cbs.create[i](emptyNode, ancestor);
            }
            const insert = ancestor.data.hook.insert;
            if (insert.merged) {
              for (let i = 1; i < insert.fns.length; i++) {
                insert.fns[i]();
              }
            }
          } else {
            registerRef(ancestor);
          }
          ancestor = ancestor.parent;
        }
      }
      if (isDef(parentElm)) {
        removeVnodes([oldVnode], 0, 0);
      } else if (isDef(oldVnode.tag)) {
        invokeDestroyHook(oldVnode);
      }
    }
  }
  invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch);
  return vnode.elm;
};

2. sameVnode

sameVnode関数は、2つの仮想DOMノードが同じものであるかを判定します。

function sameVnode(a, b) {
  return (
    a.key === b.key &&
    a.asyncFactory === b.asyncFactory && (
      (
        a.tag === b.tag &&
        a.isComment === b.isComment &&
        isDef(a.data) === isDef(b.data) &&
        sameInputType(a, b)
      ) || (
        isTrue(a.isAsyncPlaceholder) &&
        isUndef(b.asyncFactory.error)
      )
    )
  );
}

3. patchVnode

patchVnode関数は、同じ仮想DOMノードに対してテキストや子ノードの変更を確認します。

• oldVnodeとvnodeの参照が同じであれば、変更がないため即座に返します。
• oldVnodeが非同期コンポーネントの場合、チェックをスキップします。
• 両方のノードが静的であり、同じキーを持ち、vnodeがクローンまたはv-onceディレクティブで制御されている場合、oldVnodeのプロパティをvnodeにコピーして返します。
• vnodeがテキストノードまたはコメントノードではない場合
• 両方のノードに子ノードがあり、それらが異なる場合、updateChildren関数で子ノードを更新します。
• 新しいノードだけに子ノードがある場合、addVnodes関数で子ノードを作成します。
• 古いノードだけに子ノードがある場合、removeVnodes関数で子ノードを削除します。
• vnodeのテキストが未定義の場合は、vnode.elmのテキストを削除します。
• vnodeがテキストノードであり、テキスト内容が異なる場合は、テキストを更新します。

function patchVnode(oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly) {
  if (oldVnode === vnode) return;

  let elm = vnode.elm = oldVnode.elm;

  if (isTrue(oldVnode.isAsyncPlaceholder)) {
    if (isDef(vnode.asyncFactory.resolved)) {
      hydrate(oldVnode.elm, vnode, insertedVnodeQueue);
    } else {
      vnode.isAsyncPlaceholder = true;
    }
    return;
  }

  if (isTrue(vnode.isStatic) &&
    isTrue(oldVnode.isStatic) &&
    vnode.key === oldVnode.key &&
    (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
  ) {
    vnode.componentInstance = oldVnode.componentInstance;
    return;
  }

  let i;
  const data = vnode.data;
  if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
    i(oldVnode, vnode);
  }

  const oldCh = oldVnode.children;
  const ch = vnode.children;

  if (isDef(data) && isPatchable(vnode)) {
    for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode);
    if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode);
  }

  if (isUndef(vnode.text)) {
    if (isDef(oldCh) && isDef(ch)) {
      if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly);
    } else if (isDef(ch)) {
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '');
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
    } else if (isDef(oldCh)) {
      removeVnodes(oldCh, 0, oldCh.length - 1);
    } else if (isDef(oldVnode.text)) {
      nodeOps.setTextContent(elm, '');
    }
  } else if (oldVnode.text !== vnode.text) {
    nodeOps.setTextContent(elm, vnode.text);
  }

  if (isDef(data)) {
    if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode);
  }
}

4. updateChildren

updateChildren関数は、両方の仮想DOMノードに子ノードがあり、それらが異なる場合に子ノードを比較します。

主な処理フローは以下の通りです。

• 2つのリストをループで比較します。ループ終了条件は、いずれかのリストの開始インデックスと終了インデックスが重なる場合です。
• 各ループでは以下の4つの比較を行います。
• 新しいリストの先頭と古いリストの先頭を比較
• 新しいリストの末尾と古いリストの末尾を比較
• 新しいリストの先頭と古いリストの末尾を比較
• 新しいリストの末尾と古いリストの先頭を比較
• いずれかの比較が一致した場合は、patchVnode関数でノードのテキストや子ノードの変更を確認し、比較インデックスを移動させます。
• どの比較にも一致しない場合は、新しいリストの先頭ノードのキーを古いリストから探します。
• 見つからなかった場合は、新しいノードを作成します。
• 見つかった場合は、タグが同じかどうかを確認します。
• 同じタグであれば、patchVnode関数で更新し、古いリストの先頭前に挿入します。
• 異なるタグであれば、新しいノードを作成します。
• 古いリストの方が先に走りきった場合は、新しいリストの残りのノードを追加します。
• 新しいリストの方が先に走りきった場合は、古いリストの残りのノードを削除します。

このアルゴリズムは、リストの逆順操作を検出しやすくすることで、Diffの効率を向上させています。

function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
  let oldStartIdx = 0;
  let newStartIdx = 0;
  let oldEndIdx = oldCh.length - 1;
  let oldStartVnode = oldCh[0];
  let oldEndVnode = oldCh[oldEndIdx];
  let newEndIdx = newCh.length - 1;
  let newStartVnode = newCh[0];
  let newEndVnode = newCh[newEndIdx];
  let oldKeyToIdx, idxInOld, vnodeToMove, refElm;

  const canMove = !removeOnly;

  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, insertedVnodeQueue, newCh, newStartIdx);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);
      canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm));
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
      canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      idxInOld = isDef(newStartVnode.key)
        ? oldKeyToIdx[newStartVnode.key]
        : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);

      if (isUndef(idxInOld)) {
        createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
      } else {
        vnodeToMove = oldCh[idxInOld];
        if (sameVnode(vnodeToMove, newStartVnode)) {
          patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
          oldCh[idxInOld] = undefined;
          canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);
        } else {
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
        }
      }
      newStartVnode = newCh[++newStartIdx];
    }
  }

  if (oldStartIdx > oldEndIdx) {
    refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;
    addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
  } else if (newStartIdx > newEndIdx) {
    removeVnodes(oldCh, oldStartIdx, oldEndIdx);
  }
}