Vue diff 演算法解析

Vue diff 演算法

說明

diff 演算法是一種的高效能演算法。
diff 演算法作用於。
採用雙指针的策略可以在不需要遍歷整個樹的情況下，就地更新 DOM，以提高性能。避免了不必要的 DOM 操作。(主要樹節點 patchFlag 若相同, 代表下方節點就不用再更新)
其有兩個特點：
1. 。

解析流程

主要由三個函數嵌套組成：

第一層 patch： patch 函數會找出新舊節點差異，若新舊節點皆為虛擬節點，則使用 patchVnode 函數向下比較子節點差異。

第二層 patchVnode：，都是文本則單純更新文本，。當新的 VNode 列表和舊的 VNode 列表中的某些 VNode 不匹配時，則觸發 updateChildren 協調新舊子節點的變化確保虛擬 DOM 與實際 DOM 同步。

第三層 updateChildren：該函數會遍歷新的 VNode 列表，並嘗試在舊的 VNode 列表中找到匹配的 VNode。會先，同時也作為節點更新的錨點，會將新的 VNode 列表中的順序和舊的 VNode 列表中的順序不一致時進行重排，確保元素在 DOM 中的順序正確。同時也會處理新增的 VNode 和被刪除的 VNode。對於新增的 VNode，會進行創建和插入操作；對於被刪除的 VNode，會進行移除操作。

最終經過上述各項更新返回掛上鉤子函數的實體 DOM。

運作原理

當資料改變時，set 方法會觸發相關的 Dep（Dependency）對象的 notify 方法。Dep 對象用於跟蹤依賴於該資料的所有 Watcher 實例。
Dep.notify 會遍歷所有依賴（Watcher）並呼叫它們的更新方法。這些 Watcher 實例是資料變化時需要重新執行的代碼塊，通常是渲染視圖的 Watcher 或其他自定義的 Watcher。
與渲染視圖相關的 Watcher 會對實際 DOM 調用 patch 函數，patch 負責將虛擬 DOM 與實際 DOM 同步已更新資料跟渲染視圖。
比較方式為在新舊 vnode 中同時使用兩個指針從頭尾開始向中間靠近，通過動態規劃的方式計算出更新過後的 vnode, 在以此 vnode 渲染成真實 DOM。
優點：
1. 新舊 vnode 的頭尾指針比較，可以最大程度地重複使用已有的 DOM 節點。
2. Key 的比較：如果存在 key，Vue 會根據 key 來尋找相同 key 的 vnode，以進行局部更新。 Vue3 則新增 patchFlags 來標示 Vnode 進行優化比較。
3. 優化的比較策略：Vue 會進行一些優化的比較策略，例如判斷是否為相同的內建組件、是否為相同類型的 HTML 標籤等。

/**
 * patch 作用： 當資料改變觸發 patch 時，根據 新舊節點 存在與否以及匹配狀況，最終返回映射過的實體 DOM。
 * patch 流程：
 *         (1) 沒有新節點，有舊節點：舊節點清除鉤子函數將資料重置。(避免 memory leak, side effect)
 *         (2) 沒有舊節點，有新節點：代表節點初始化，直接使用新的 vnode 生成對應的真實 DOM。
 *         (3) 新舊節點都是 虛擬 DOM：執行 patchVnode 向子節點進一步檢查需要更新的項目。
 *         (4) oldVnode 是真實 DOM，舊節點為虛擬 DOM 時：進行 hydration，
 *             hydration 若成功代表 真實 DOM & vnode 虛擬節點成功匹配，最終掛上鉤子返回 oldVnode 真實 DOM。
 *         (5) 替步驟 2 & 4 利用 vnode 生成的實體 DOM 插上鉤子函數，最終返回 vnode 虛擬 DOM 生成的實體 DOM。
 *
 * 比較好記的方式：
 *         (1) 有舊的沒新的, 清除鉤子
 *         (2) 有新的沒舊的, 建立新實體 DOM
 *         (3) 有舊有新都為虛擬 DOM, 使用 patchVnode 向下看子節點要更新文本或是更深的子節點
 *         (4) 有舊有新但舊的是實體 DOM 新的是虛擬節點, 進行 hydration，成功直接返回掛上鉤子的舊實體 DOM,
 *             失敗則用新虛擬節點創建實體 DOM 並套用部分 舊的實體 DOM 的 父節點資訊。
 *         (5) 替步驟 2 & 4 失敗時創建的實體 DOM 掛上鉤子函數。
 *
 * 補：hydration 的目的是將伺服器端生成的靜態 HTML 轉換為具有動態行為的客戶端應用程式。
 *    即將 HTML 套上 JS 方可進行交互
 */

function patch(oldVnode, vnode, hydrating, removeOnly) {
  // 1. 沒有 新節點，直接觸發舊節點的 destory 鉤子，執行一些銷毀組件時的清理工作。
  //    簡單來說因為資料更新才觸發 patch，但節點卻沒有改動(沒有產生新節點)，需要清除舊節點的鉤子將資料重置。
  if (isUndef(vnode)) {
    if (isDef(oldVnode)) invokeDestroyHook(oldVnode);
    return; // 若不存在 oldVnode, 則不需要執行其他的 patch 邏輯，直接結束函數。
  }

  let isInitialPatch = false;
  const insertedVnodeQueue = [];
  // 2. 有 新節點 但沒有 舊節點，代表頁面是剛初始化期間，所以不比較，直接用 新節點 生成 DOM 元素
  if (isUndef(oldVnode)) {
    // empty mount (likely as component), create new root element
    isInitialPatch = true;
    createElm(vnode, insertedVnodeQueue);
  } else { // 同時有 新舊節點
    const isRealElement = isDef(oldVnode.nodeType); // 檢查 oldVnode 是否為真實元素（即 DOM 元素），如果 oldVnode 是真實元素，則表示它不是由 Vue.js 管理的虛擬節點，而是由外部的真實 DOM 元素。
    if (!isRealElement && sameVnode(oldVnode, vnode)) {
      // 3. 如果 oldVnode 不是真實 DOM, 新舊節點的 vnode 又一樣的話，代表可以進行 patchVnode 來更新節點。
      patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly);
    } else {
      // 4. oldVnode 是實體 DOM，又舊節點和新節點不一樣時，建立新節點，刪除舊節點 (下方 return vnode.elm)
      // 此處調用 hidrate 函數，將伺服器生成的 HTML（oldVnode）和 Vue 客戶端應用程式的虛擬節點（vnode）進行節點匹配。

      if (isRealElement) {
        if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
          oldVnode.removeAttribute(SSR_ATTR)
          hydrating = true
        }
        if (isTrue(hydrating)) {
          if (hydrate(oldVnode, vnode, insertedVnodeQueue)) { // 如果 hydrate 成功
            invokeInsertHook(vnode, insertedVnodeQueue, true); // 觸發插入鉤子函數，處理插入節點的相關邏輯。第三個參數 true 表示這是 hydration 階段。
            return oldVnode; // 返回舊節點 oldVnode，表示 hydration 過程成功，並結束 patch 過程。
          }
        }
        // 要嘛不是伺服器渲染，要嘛 hydration 失敗
        // 創建一個空的節點取代 oldVnode 避免程式碼報錯
        oldVnode = emptyNodeAt(oldVnode)
      }

      // !! 當 hydration 失敗，抓取部分 oldVnode 實體 DOM 的部分資料，用 vnode 來創建新的實體 DOM 取代 oldVnode 實體 DOM，並且刪除 oldVnode 實體 DOM。
      // 取代實體元素
        const oldElm = oldVnode.elm
        const parentElm = nodeOps.parentNode(oldElm)

        // 利用 vnode 創建一個實體 DOM，用以取代 oldVnode 實體 DOM
        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)
        }
      }

    }
  }

  // 5. 替步驟 2 新創建的實體 DOM, 以及 步驟 4 hydration 失敗而用 vnode 新建立出來的實體 DOM 掛上鉤子函數
  invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch);
  return vnode.elm;
}

// p.s. invokeDestroyHook 作用是調用 vnode 的銷毀鉤子函數以及遍歷子節點遞歸地調用銷毀鉤子函數。
// 其作用大致可分成幾點
// (1) 清理定時器和計時器(setTimeout, setInterval等...)，防止 memory leak。
// (2) 解除綁定事件監聽 (解绑事件监听器)，在組件生命周期中，可能透過addEventListener 添加事件監聽器。
//     銷毀鉤子函數提供了一個時機，可以在組件銷毀前移除這些事件監聽器，避免組件已經銷毀但仍存在事件監聽的情況。
// (3) 取消異步任務： 如果組件中有異步任務，如 AJAX 請求等，銷毀鉤子函數可以用於取消這些異步任務，確保在組件銷毀前已完成或取消。
// (4) 清理非 Vue 實例的資源： 在組件中可能使用了一些非 Vue 實例管理的資源，
//     如手動創建的 DOM 元素、WebSocket 連接等。
//     銷毀鉤子函數一樣提供了一個時機，可以在組件銷毀前進行清理。

/**
 * patchVnode 函數作用：包括了檢查靜態節點、動態節點、props、事件等，以判斷 vdom 該如何更新。
 * patchVnode 流程：(1) 找出兩節點對應的真實 DOM，檢查新節點是否為文字節點，如果是，
 *                     則直接更新dom的文字內容為新節點的文字內容
 *                     如果不是則執行下方步驟 2,3,4
 *                 (2) 新節點列表和舊節點列表都不是文本且列表順序不同時，則呼叫 updateChildren 進行節點列表的排序，新增或刪除等操作。
 *                 (3) 只有新節點有子節點，舊節點沒有，代表所有節點都是全新的，直接全部新建，
 *                     新建是指創建出所有新DOM，並且加入進父節點
 *                 (4) 只有舊節點有子節點而新節點沒有，說明更新後的頁面，舊節點全部都不見了，
 *                     代表要把所有的舊節點刪除，也就是直接把 DOM 刪除。
 *
 * 補充：Vue3 多新增了靜態標記 patchFlags 來優化效能，patchFlag 是用來表示 vnode 的屬性和子節點的一個標誌，
 *      它可以將原功能(檢查靜態節點、動態節點、props、事件等信息合併成 patchFlags)用來判斷 vnode 是否需進行更新。
 *      當新舊 vnode 的 patchFlag 相同時，意味著它們的屬性和子節點沒有發生變化，因此可以節省效能，
 *      不需要進行進一步的 DOM 操作。
 *
 */

function patchVnode(
  oldVnode,
  vnode,
  insertedVnodeQueue,
  ownerArray,
  index,
  removeOnly
) {
  if (oldVnode === vnode) return; // 如果新舊節點一樣，不用處理直接 return

  if (isDef(vnode.elm) && isDef(ownerArray)) {
    // 克隆重用的 vnode
    vnode = ownerArray[index] = cloneVNode(vnode);
  }

  const elm = (vnode.elm = oldVnode.elm); // 將 vnode.elm 引用到真實 DOM，elm 修改時，vnode.elm 也會同步變化

  // 異步占位符
  if (isTrue(oldVnode.isAsyncPlaceholder)) {
    if (isDef(vnode.asyncFactory.resolved)) {
      hydrate(oldVnode.elm, vnode, insertedVnodeQueue);
    } else {
      vnode.isAsyncPlaceholder = true;
    }
    return;
  }

  // 重複使用靜態的元素。
  // 注意，僅在 vnode 被克隆時才執行此操作
  // 如果新節點沒有被克隆，則表示渲染函數已經被克隆
  // 透過 hot-reload-api 重置，我們需要進行適當的重新渲染。
  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);
  }
  // 如果 vnode 不是單純的文本節點或者註釋節點，則需要向下比較子節點差異並以此更新實體老節點。
  if (isUndef(vnode.text)) {
    // 並且都具有子節點時
    if (isDef(oldCh) && isDef(ch)) {
      // 當新舊子節點列表不同時，透過 updateChildren 進行新舊節點列表的更新以同步兩者。
      if (oldCh !== ch)
        updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly);
    } else if (isDef(ch)) {
      // 如果只有新的 vnode 有子節點
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, "");
      // elm 在上方已經引用 oldVNode 的實體 DOM 節點，在此更新 elm 相當於直接在老節點上添加 vnode 的 子節點
      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, "");
    }
    // 如果 oldVnode 和 vnode 是文本節點或者註釋節點，且 vnode.text != oldVnode.text ，更新文本內容至 DOM 即可。
  } 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);
  }
}

/**
 * updateChildren 函數作用：利用新舊節點的頭尾雙指針，處理虛擬 DOM 中 "子節點" 的更新。如 v-for 產生的子節點。
 * updateChildren 流程：(1) 當新舊節點的頭指針都還沒超越尾指針，迴圈進行子節點比較。
 *                     (2) 先讓 舊 頭尾指針定錨，找不到頭尾指針就持續推進直到找到兩者。
 *                     (3) 新舊"頭"指針對應節點是相同節點，執行 patchVnode 檢查兩點，並將兩者指針向中間推進。
 *                     (4) 新舊"尾"指針對應節點是相同節點，執行 patchVnode 檢查兩點，並將兩者指針向中間推進。
 *                     (5) 舊頭指針 = 新尾指針，執行 patchVnode 檢查兩點，並將兩者指針向中間推進。
 *                     (6) 舊尾指針 = 指針新頭，執行 patchVnode 檢查兩點，並將兩者指針向中間推進。
 *                     (7) 都不是上述情況，開始看能不能找到 oldCh 之中和 當前 新頭指針節點 相同 key 的節點
 *                        (7-1) 找不到，則先新增一個節點
 *                        (7-2) 找得到，且相同節點
 *                        (7-3) 找得到，但不同節點，則先新增一個節點
 *                        (7-4) 不論上路結果，最後 新頭指針 皆向右推進
 *                     (8) 至此迴圈已經結束，如果舊的頭指針 超過 舊的 尾指針，代表 新節點 比 舊節點 多，所以需要 新增節點。
 *                                        反之，代表舊節點 比 新節點多，代表進行 刪除節點 動作。
 */

function updateChildren(
  parentElm,
  oldCh,
  newCh,
  insertedVnodeQueue,
  removeOnly
) {
  // 新舊節點頭尾指針
  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];
  let oldKeyToIdx, idxInOld, vnodeToMove, refElm;

  // removeOnly is a special flag used only by <transition-group>
  // to ensure removed elements stay in correct relative positions
  // during leaving transitions
  const canMove = !removeOnly; // canMove 的條件，如果為真，則表示在更新過程中可以移動節點。

  // 舊的頭指針 <= 舊的尾指針
  // 當 舊的頭指針 超越 舊的尾指針 or 新的頭指針 超越 新的尾指針，表示 diff 比較結束，跳出循環
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (isUndef(oldStartVnode)) {
      // 舊節點 第一個 child 不存在, 舊節點 和 舊頭指針 都向 右 移動一單位
      oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
    } else if (isUndef(oldEndVnode)) {
      // 舊節點 最後一個 child 不存在, 舊節點 和 舊尾指針都向 左 移動一單位
      oldEndVnode = oldCh[--oldEndIdx];
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      // 新舊 "頭" 節點是同一節點，patchVnode 比較兩節點，接著 新舊"頭"指針 同時向 右 推進
      patchVnode(
        oldStartVnode,
        newStartVnode,
        insertedVnodeQueue,
        newCh,
        newStartIdx
      );
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      // 新舊 "尾" 節點是同一節點，patchVnode 比較兩節點，接著 新舊"尾"指針 同時向 右 推進
      test(a, b);
      patchVnode(
        oldEndVnode,
        newEndVnode,
        insertedVnodeQueue,
        newCh,
        newEndIdx
      );
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      // 舊頭節點 == 新尾節點，patchVnode 比較兩節點， 頭舊節點 向 → 推進，尾新節點向 ← 推進，分別推進頭尾
      // Vnode moved right
      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 比較兩節點， 尾舊節點 向 ← 推進，頭新節點向 → 推進，分別推進尾頭
      // Vnode moved left
      patchVnode(
        oldEndVnode,
        newStartVnode,
        insertedVnodeQueue,
        newCh,
        newStartIdx
      );
      canMove &&
        nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      // 如果都不能匹配
      // 在 oldChildren 中和 newStartVnode 找看看是否有相同 key 的 Vnode
      if (isUndef(oldKeyToIdx))
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      idxInOld = isDef(newStartVnode.key)
        ? oldKeyToIdx[newStartVnode.key]
        : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
      if (isUndef(idxInOld)) {
        // 如果找不到相同 key, 代表 newStartVnode 是一個新節點，所以新增一個節點
        createElm(
          newStartVnode,
          insertedVnodeQueue,
          parentElm,
          oldStartVnode.elm,
          false,
          newCh,
          newStartIdx
        );
      } else {
        // 如果找得到和 newStartVnode 相同 key 的 Vnode，叫vnodeToMove，
        vnodeToMove = oldCh[idxInOld]; // 把 vnodeToMove 變成 oldCh 中與 newStartVnode 相對應 key 的節點
        if (sameVnode(vnodeToMove, newStartVnode)) {
          // 如果兩個 key 相同的節點是同一個節點
          patchVnode(
            vnodeToMove,
            newStartVnode,
            insertedVnodeQueue,
            newCh,
            newStartIdx
          );
          oldCh[idxInOld] = undefined; // 相當於標記已經處理過的舊VNode，(因爲已經匹配過 下次到此節點也就不用匹配，用於優化 diff 算法效率)
          canMove &&
            nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);
          // 將 vnodeToMove.elm（即找到相同 key 的 舊的DOM元素）插入到 oldStartVnode.elm（即原來在舊節點 oldStartIdx 位置）的前面。
          // !!! 等同於將該相同 key 舊元素， 丟到當前舊頭指針的位置之前 (oldStartIdx - 1)。(要和新頭指針位置對應，又不影響舊頭指針位置，所以 - 1)
          // 既不會影響 舊頭指針 運行，也完成了對於該節點的更新和移動。
        } else {
          // key 相同，但節點不相同，則建立一個新節點放到 newStartIdx 位置
          createElm(
            newStartVnode,
            insertedVnodeQueue,
            parentElm,
            oldStartVnode.elm,
            false,
            newCh,
            newStartIdx
          );
        }
        // p.s.: 不設 key，newCh 和 oldCh 只進行頭尾兩端的比較，設 key 後，還會從 用 key 生成的對象 oldKeyToIdx 中查詢匹配的節點，
        // 所以替節點設置 key 可以更高效的利用 DOM。
      }
      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);
  }
}

心得

在看過原始碼知道實現邏輯後，總算能明白每個階段所做的事情，越是一步步拆解這些函數，越能體會到開源者的思維細膩程度。像是比較的原則，排序的方式，樹的遍歷順序，如何整合 SSR 等等，或許開源者的追求對於大部分商用產品的世界來說有點過於邊際效應，但對開發者而言，從中學到的思考模式，反而更能反思自己開發產品的流程和方式是否不夠嚴謹，也對於前端應用的演算法跟特性有更深的認識。

Vue diff 演算法解析