深入了解Vue2中的的雙端diff算法

更新時間：2023年02月08日 10:53:52 作者：mick

雙端Diff在可以解決更多簡單Diff算法處理不了的場景，且比簡單Diff算法性能更好。本文主要來和大家詳細(xì)講講Vue2中的雙端diff算法的實現(xiàn)與使用，需要的可以參考一下

今天又重讀了vue2的核心源碼，主要之前讀vue2源碼的時候純屬的硬記，或者說純粹的為了應(yīng)付面試，導(dǎo)致我們并沒有去細(xì)品源碼中的精妙之處。如果回頭在重讀源碼的時候，發(fā)現(xiàn)其中有很多地方是值得我們深入了解的。比如我們今天要看的“雙端diff”。還記得之前就記得雙端diff對比的口訣”頭頭、尾尾、頭尾、尾頭“,具體對比做了啥事，這種對比有什么好處，可以說是一無所知。今天我們就來好好的看看。

patch可以將vnode渲染成真實的DOM，實際作用是在現(xiàn)有的DOM進(jìn)行修改來完成更新視圖的目的。

在說“雙端diff”之前，我們先來簡單看看“簡單diff”。

簡單diff算法

更新文本節(jié)點

const oldVNode = {
  type: "div",
  children: [{ type: "p", children: " 1" }],
  children: [{ type: "p", children: " 2" }],
  children: [{ type: "p", children: " 3" }],
};

const newVNode = {
  type: "div",
  children: [{ type: "p", children: " 4" }],
  children: [{ type: "p", children: " 5" }],
  children: [{ type: "p", children: " 6" }],
};

我們知道，操作DOM的性能開銷都比較大，比如我們創(chuàng)建一個DOM的時候，會連帶著創(chuàng)建很多的屬性。如果我們想將oldVNode替換成newVNode，最暴力的解法就是卸載所有舊子節(jié)點，掛載所有新的子節(jié)點，這樣就會頻繁的操作dom。但是我們根據(jù)例子發(fā)現(xiàn)，如果說節(jié)點都是p標(biāo)簽，只是內(nèi)容發(fā)生了改變，那是不是就只可以直接修改內(nèi)容了，這樣就不需要頻繁的刪除dom,創(chuàng)建dom了。

key的作用

const oldVNode = [{ type: "p" }, { type: "div" }, { type: "span" }];

const newVNode = [{ type: "span" }, { type: "p" }, { type: "div" }];

根據(jù)上面的例子，如果操作DOM的話，則需要將舊子節(jié)點中的標(biāo)簽和新子節(jié)點中的標(biāo)簽進(jìn)行一對一的對比，如果舊子節(jié)點中的{type: 'p'}和新子節(jié)點中的{type: 'span'}不是相同的標(biāo)簽，會先卸載{type: 'p'}，然后再掛載{ type:'span'}，這需要執(zhí)行 2 次 DOM 操作。仔細(xì)觀察可以發(fā)現(xiàn)，新舊子節(jié)點僅僅是順序不同，這樣就可以通過DOM的移動來完成子節(jié)點的更新了。

如果僅僅通過type判斷，那么type相同，內(nèi)容不同呢。比如：

const oldVNode = [
  { type: "p", children: " 1" },
  { type: "p", children: " 2" },
  { type: "p", children: " 3" },
];

const newVNode = [
  { type: "p", children: " 3" },
  { type: "p", children: " 1" },
  { type: "p", children: " 2" },
];

這里我們確實可以通過移動DOM來完成更新，但是我們現(xiàn)在繼續(xù)用type去判斷還能行嗎？肯定不行的，因為type都是一樣的。這時，我們就需要引入額外的key來作為vnode的標(biāo)識。

const oldVNode = [
  { type: "p", children: " 1", key: " 1" },
  { type: "p", children: " 2", key: " 2" },
  { type: "p", children: " 3", key: " 3" },
];

const newVNode = [
  { type: "p", children: " 3", key: " 3" },
  { type: "p", children: " 1", key: " 1" },
  { type: "p", children: " 2", key: " 2" },
];

這時我們找到需要移動的元素更新即可了。

如何移動呢

比如我們有三個節(jié)點，我們希望移動將老的節(jié)點更新成為新的節(jié)點，此時我們需要一個變量lastIndex為0來記錄，只要當(dāng)前的節(jié)點索引小于lastIndex,則說明此節(jié)點需要移動。如果當(dāng)前的索引大于等于lastIndex,則說明此節(jié)點不需要移動，并且將當(dāng)前節(jié)點的索引值賦值給lastIndex。

let lastIndex = 0;
for (let i = 0; i < newChildren.length; i++) {
  const newVNode = newChildren[i];
  // 遍歷舊的children
  // 在第一場循環(huán)中定義變量find,代表是否在舊的一組子節(jié)點中找到可復(fù)用的節(jié)點
  let find = false;
  for (let j = 0; j < oldChildren.length; j++) {
    const oldVNode = oldChildren[j];
    // 如果找到具有相同的key值得兩個節(jié)點，說明可以復(fù)用，仍然需要調(diào)用patch函數(shù)更新
    if (newVNode.key === oldVNode.key) {
      patch(oldVNode, newVNode, container);
      if (j < lastIndex) {
        // 如果當(dāng)前找到的節(jié)點在舊children中的索引小于最大索引值lastIndex
        // 說明該節(jié)點對應(yīng)的真實DOM需要移動

        // 先獲取newVnode的前一個vnode, prevVNode
        const prevVNode = newChildren[i - 1];
        if (prevVNode) {
          // 由于我們要將newVnode對應(yīng)的真實DOM移動到prevVNode所對應(yīng)真實DOM后面
          // 所以我們需要獲取prevVNode所對應(yīng)真實DOM的下一個兄弟節(jié)點，并將其作為錨點
          const anchor = prevVNode.el.nextSibling;

          // 調(diào)用insert方法將newVNode對應(yīng)的真實DOM插入到錨點元素前面
          // 也就是preVNode對應(yīng)真實DOM的后面
          insert(newVNode.el, container, anchor);
        }
      } else {
        // 如果當(dāng)前找到的節(jié)點在舊children中的索引不小于最大索引值
        // 則更新lastIndex的值
        lastIndex = j;
      }
      break;
    }

  }
}

以上是一個簡單的demo實現(xiàn)，則發(fā)現(xiàn)需要對舊子節(jié)點移動兩次才能更新成新的子節(jié)點。

但是我們仔細(xì)觀察發(fā)現(xiàn)，其實只需要將C移動到最前面，這一步就可以實現(xiàn)了。此時我們就需要雙端diff算法了

雙端diff算法

雙端diff算法是一種同時對新舊兩組子節(jié)點的兩個斷點進(jìn)行對比的算法。所以我們需要四個索引值，分別指向新舊兩組子節(jié)點的端點。

比較方式

在雙端diff算法比較中，每一輪比較都會分成4個步驟

第一步：舊子節(jié)點的開始節(jié)點和新子節(jié)點的開始節(jié)點進(jìn)行對比，看看他們是否相同。根據(jù)他們的標(biāo)簽和key判斷，兩個節(jié)點不相同，所以什么都不做
第二步：舊子節(jié)點的結(jié)束節(jié)點和新子節(jié)點的結(jié)束節(jié)點進(jìn)行對比，看看他們是否相同。根據(jù)他們的標(biāo)簽和key判斷，兩個節(jié)點不相同，所以什么都不做
第三步：舊子節(jié)點的開始節(jié)點和新子節(jié)點的結(jié)束節(jié)點進(jìn)行對比，看看他們是否相同。根據(jù)他們的標(biāo)簽和key判斷，兩個節(jié)點不相同，所以什么都不做
第四步：舊子節(jié)點的結(jié)束節(jié)點和新子節(jié)點的開始節(jié)點進(jìn)行對比，看看他們是否相同。根據(jù)他們的標(biāo)簽和key判斷，兩個節(jié)點相同，說明節(jié)點可以復(fù)用，此時節(jié)點需要通過移動來更新。

那又該怎么移動呢？

根據(jù)對比我們發(fā)現(xiàn)，我們在第四步是將舊子節(jié)點的結(jié)束節(jié)點和新子節(jié)點的開始節(jié)點進(jìn)行對比，發(fā)現(xiàn)節(jié)點可復(fù)用。說明節(jié)點’D‘在舊子節(jié)點中是最后一個節(jié)點，在新子節(jié)點中是第一個節(jié)點，而我們要操作的是老節(jié)點也就是現(xiàn)有節(jié)點，來實現(xiàn)視圖的更新。所以我們只需要將索引 oldEndIdx 指向的虛擬節(jié)點所對應(yīng)的真實DOM 移動到索引 oldStartIdx 指向的虛擬節(jié)點所對應(yīng)的真實 DOM前面。我們看下源碼：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
      } else if (isUndef(oldEndVnode)) {
        oldEndVnode = oldCh[--oldEndIdx]
      } else if (sameVnode(oldStartVnode, newStartVnode)) { 
        // 老的開始節(jié)點 和 新的開始節(jié)點一樣
       ···
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // 老的結(jié)束節(jié)點 和 新的結(jié)束節(jié)點一樣
       ···
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        // 老的開始節(jié)點 和 新的結(jié)束節(jié)點一樣
       ···
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        // 老的結(jié)束節(jié)點 和 新的開始節(jié)點一樣
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        // 將老的結(jié)束節(jié)點 塞到 老的新節(jié)點之前
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {  // 非理想狀態(tài)下的處理方式
        ···
      }
    } 
  }

從源碼中我們看到執(zhí)行了patchVnode。這個函數(shù)其實就是將需要對比的兩個新老節(jié)點進(jìn)行打補(bǔ)丁，因為我們此時只能確認(rèn)新老節(jié)點他們的標(biāo)簽和key是一樣的，并不代表他們的內(nèi)容一樣，所以需要先更新節(jié)點的內(nèi)容，然后再修改節(jié)點的位置。最后我們只需要以頭部元素oldStartVNode.elm 作為錨點，將尾部元素 oldEndVNode.elm 移動到錨點前面即可。最后涉及的兩個索引分別是oldEndIdx和newStartIdx，所以我們需要更新兩者的值，讓它們各自朝正確的方向前進(jìn)一步，并指向下一個節(jié)點。

接著繼續(xù)進(jìn)行下一輪對比：

還是按照我們上面說的那4步對比。此時，當(dāng)我們執(zhí)行第二步對比的時候，發(fā)現(xiàn)老的結(jié)束節(jié)點和新的結(jié)束節(jié)點是一樣的。所以就會執(zhí)行以下操作：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
      } else if (isUndef(oldEndVnode)) {
        oldEndVnode = oldCh[--oldEndIdx]
      } else if (sameVnode(oldStartVnode, newStartVnode)) { 
        // 老的開始節(jié)點 和 新的開始節(jié)點一樣
       ···
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // 老的結(jié)束節(jié)點 和 新的結(jié)束節(jié)點一樣
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        // 老的開始節(jié)點 和 新的結(jié)束節(jié)點一樣
       ···
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        // 老的結(jié)束節(jié)點 和 新的開始節(jié)點一樣
       ···
      } else {  // 非理想狀態(tài)下的處理方式
        ···
      }
    } 
}

這里就只需要通過patchVnode更新新舊子節(jié)點的內(nèi)容，然后更新oldEndIdx和newStartIdx，讓它們各自朝正確的方向前進(jìn)一步，并指向下一個節(jié)點。

接著繼續(xù)進(jìn)行下一輪對比：

當(dāng)對比到第三步的時候，發(fā)現(xiàn)老的開始節(jié)點和新的結(jié)束節(jié)點一樣

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
      } else if (isUndef(oldEndVnode)) {
        oldEndVnode = oldCh[--oldEndIdx]
      } else if (sameVnode(oldStartVnode, newStartVnode)) { 
        // 老的開始節(jié)點 和 新的開始節(jié)點一樣
       ···
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // 老的結(jié)束節(jié)點 和 新的結(jié)束節(jié)點一樣
       ···
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        // 老的開始節(jié)點 和 新的結(jié)束節(jié)點一樣
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        // 將老的開始節(jié)點 塞到 老的結(jié)束節(jié)點后面
        canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
        oldStartVnode = oldCh[++oldStartIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        // 老的結(jié)束節(jié)點 和 新的開始節(jié)點一樣
       ···
      } else {  // 非理想狀態(tài)下的處理方式
        ···
      }
    } 
}

首先通過patchVnode更新新舊子節(jié)點的內(nèi)容。舊的一組子節(jié)點的頭部節(jié)點與新的一組子節(jié)點的尾部節(jié)點匹配，則說明該舊節(jié)點所對應(yīng)的真實 DOM 節(jié)點需要移動到尾部。因此，我們需要獲取當(dāng)前尾部節(jié)點的下一個兄弟節(jié)點作為錨點，即 oldEndVNode.el.nextSibling。最后，更新相關(guān)索引到下一個位置。

接著繼續(xù)進(jìn)行下一輪對比：

這里就只需要通過patchVnode更新新舊子節(jié)點的內(nèi)容,發(fā)現(xiàn)內(nèi)容一樣什么都不做，然后更新oldEndIdx和newStartIdx，讓它們各自朝正確的方向前進(jìn)一步，并指向下一個節(jié)點，這就退出了循環(huán)。

以上是理想情況下的處理方式，當(dāng)然還有非理想情況下的處理方式

非理想情況的處理方式

比如：

此時我們發(fā)現(xiàn)之前說的情況都無法命中，所以我們只能通過增加額外的步驟去處理。由于我們都是對比的頭部和尾部，既然都無法命中，那就試試非頭部、非尾部節(jié)點能否復(fù)用。此時我們可以發(fā)現(xiàn)新子節(jié)點中頭部節(jié)點和舊子節(jié)點中的第二個節(jié)點是可以復(fù)用的，所以只需要將舊子節(jié)點中的第二個節(jié)點移動到當(dāng)前舊子節(jié)點的頭部即可。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
      } else if (isUndef(oldEndVnode)) {
        oldEndVnode = oldCh[--oldEndIdx]
      } else if (sameVnode(oldStartVnode, newStartVnode)) { 
        // 老的開始節(jié)點 和 新的開始節(jié)點一樣
       ···
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // 老的結(jié)束節(jié)點 和 新的結(jié)束節(jié)點一樣
       ···
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        // 老的開始節(jié)點 和 新的結(jié)束節(jié)點一樣
       ···
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        // 老的結(jié)束節(jié)點 和 新的開始節(jié)點一樣
       ···
      } else {  // 非理想狀態(tài)下的處理方式
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          // 新的一組子節(jié)點的頭部 去 舊的一組節(jié)點中尋找
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
        if (isUndef(idxInOld)) { // New element
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {
          // 拿到新節(jié)點頭部 在舊的一組節(jié)點中對應(yīng)的節(jié)點
          vnodeToMove = oldCh[idxInOld]
          if (sameVnode(vnodeToMove, newStartVnode)) { // 如果是相同的節(jié)點 則patch 
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            // 將老的節(jié)點中對應(yīng)的設(shè)置為undefined
            oldCh[idxInOld] = undefined
            // 移動節(jié)點 
            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
          } else {
            // same key but different element. treat as new element
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
          }
        }
        newStartVnode = newCh[++newStartIdx]
      }
    } 
}

首先那新的子節(jié)點的頭部去舊的一組子節(jié)點中尋找，如果沒有找到，說明這個節(jié)點是一個新的節(jié)點，則直接創(chuàng)建節(jié)點。如果找到了，通過索引去獲取對應(yīng)的舊節(jié)點的信息，如果節(jié)點可復(fù)用，則需要將當(dāng)前舊節(jié)點移動到頭部即可。最后更新新節(jié)點的開始節(jié)點的索引位置。