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

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

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

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

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

在說(shuō)“雙端diff”之前，我們先來(lái)簡(jiǎn)單看看“簡(jiǎn)單diff”。

簡(jiǎn)單diff算法

更新文本節(jié)點(diǎn)

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的性能開(kāi)銷(xiāo)都比較大，比如我們創(chuàng)建一個(gè)DOM的時(shí)候，會(huì)連帶著創(chuàng)建很多的屬性。如果我們想將oldVNode替換成newVNode，最暴力的解法就是卸載所有舊子節(jié)點(diǎn)，掛載所有新的子節(jié)點(diǎn)，這樣就會(huì)頻繁的操作dom。但是我們根據(jù)例子發(fā)現(xiàn)，如果說(shuō)節(jié)點(diǎn)都是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的話(huà)，則需要將舊子節(jié)點(diǎn)中的標(biāo)簽和新子節(jié)點(diǎn)中的標(biāo)簽進(jìn)行一對(duì)一的對(duì)比，如果舊子節(jié)點(diǎn)中的{type: 'p'}和新子節(jié)點(diǎn)中的{type: 'span'}不是相同的標(biāo)簽，會(huì)先卸載{type: 'p'}，然后再掛載{ type:'span'}，這需要執(zhí)行 2 次 DOM 操作。仔細(xì)觀察可以發(fā)現(xiàn)，新舊子節(jié)點(diǎn)僅僅是順序不同，這樣就可以通過(guò)DOM的移動(dòng)來(lái)完成子節(jié)點(diǎn)的更新了。

如果僅僅通過(guò)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" },
];

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

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" },
];

這時(shí)我們找到需要移動(dòng)的元素更新即可了。

如何移動(dòng)呢

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

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

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

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

  }
}

以上是一個(gè)簡(jiǎn)單的demo實(shí)現(xiàn)，則發(fā)現(xiàn)需要對(duì)舊子節(jié)點(diǎn)移動(dòng)兩次才能更新成新的子節(jié)點(diǎn)。

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

雙端diff算法

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

比較方式

在雙端diff算法比較中，每一輪比較都會(huì)分成4個(gè)步驟

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

那又該怎么移動(dòng)呢？

根據(jù)對(duì)比我們發(fā)現(xiàn)，我們?cè)诘谒牟绞菍⑴f子節(jié)點(diǎn)的結(jié)束節(jié)點(diǎn)和新子節(jié)點(diǎn)的開(kāi)始節(jié)點(diǎn)進(jìn)行對(duì)比，發(fā)現(xiàn)節(jié)點(diǎn)可復(fù)用。說(shuō)明節(jié)點(diǎn)’D‘在舊子節(jié)點(diǎn)中是最后一個(gè)節(jié)點(diǎn)，在新子節(jié)點(diǎn)中是第一個(gè)節(jié)點(diǎn)，而我們要操作的是老節(jié)點(diǎn)也就是現(xiàn)有節(jié)點(diǎn)，來(lái)實(shí)現(xiàn)視圖的更新。所以我們只需要將索引 oldEndIdx 指向的虛擬節(jié)點(diǎn)所對(duì)應(yīng)的真實(shí)DOM 移動(dòng)到索引 oldStartIdx 指向的虛擬節(jié)點(diǎn)所對(duì)應(yīng)的真實(shí) 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)) { 
        // 老的開(kāi)始節(jié)點(diǎn) 和 新的開(kāi)始節(jié)點(diǎn)一樣
       ···
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // 老的結(jié)束節(jié)點(diǎn) 和 新的結(jié)束節(jié)點(diǎn)一樣
       ···
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        // 老的開(kāi)始節(jié)點(diǎn) 和 新的結(jié)束節(jié)點(diǎn)一樣
       ···
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        // 老的結(jié)束節(jié)點(diǎn) 和 新的開(kāi)始節(jié)點(diǎn)一樣
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        // 將老的結(jié)束節(jié)點(diǎn) 塞到 老的新節(jié)點(diǎn)之前
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {  // 非理想狀態(tài)下的處理方式
        ···
      }
    } 
  }

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

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

還是按照我們上面說(shuō)的那4步對(duì)比。此時(shí)，當(dāng)我們執(zhí)行第二步對(duì)比的時(shí)候，發(fā)現(xiàn)老的結(jié)束節(jié)點(diǎn)和新的結(jié)束節(jié)點(diǎn)是一樣的。所以就會(huì)執(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)) { 
        // 老的開(kāi)始節(jié)點(diǎn) 和 新的開(kāi)始節(jié)點(diǎn)一樣
       ···
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // 老的結(jié)束節(jié)點(diǎn) 和 新的結(jié)束節(jié)點(diǎn)一樣
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        // 老的開(kāi)始節(jié)點(diǎn) 和 新的結(jié)束節(jié)點(diǎn)一樣
       ···
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        // 老的結(jié)束節(jié)點(diǎn) 和 新的開(kāi)始節(jié)點(diǎn)一樣
       ···
      } else {  // 非理想狀態(tài)下的處理方式
        ···
      }
    } 
}

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

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

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

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)) { 
        // 老的開(kāi)始節(jié)點(diǎn) 和 新的開(kāi)始節(jié)點(diǎn)一樣
       ···
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // 老的結(jié)束節(jié)點(diǎn) 和 新的結(jié)束節(jié)點(diǎn)一樣
       ···
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        // 老的開(kāi)始節(jié)點(diǎn) 和 新的結(jié)束節(jié)點(diǎn)一樣
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        // 將老的開(kāi)始節(jié)點(diǎn) 塞到 老的結(jié)束節(jié)點(diǎn)后面
        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é)點(diǎn) 和 新的開(kāi)始節(jié)點(diǎn)一樣
       ···
      } else {  // 非理想狀態(tài)下的處理方式
        ···
      }
    } 
}

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

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

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

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

非理想情況的處理方式

比如：

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

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)) { 
        // 老的開(kāi)始節(jié)點(diǎn) 和 新的開(kāi)始節(jié)點(diǎn)一樣
       ···
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // 老的結(jié)束節(jié)點(diǎn) 和 新的結(jié)束節(jié)點(diǎn)一樣
       ···
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        // 老的開(kāi)始節(jié)點(diǎn) 和 新的結(jié)束節(jié)點(diǎn)一樣
       ···
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        // 老的結(jié)束節(jié)點(diǎn) 和 新的開(kāi)始節(jié)點(diǎn)一樣
       ···
      } else {  // 非理想狀態(tài)下的處理方式
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          // 新的一組子節(jié)點(diǎn)的頭部 去 舊的一組節(jié)點(diǎn)中尋找
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
        if (isUndef(idxInOld)) { // New element
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {
          // 拿到新節(jié)點(diǎn)頭部 在舊的一組節(jié)點(diǎn)中對(duì)應(yīng)的節(jié)點(diǎn)
          vnodeToMove = oldCh[idxInOld]
          if (sameVnode(vnodeToMove, newStartVnode)) { // 如果是相同的節(jié)點(diǎn) 則patch 
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            // 將老的節(jié)點(diǎn)中對(duì)應(yīng)的設(shè)置為undefined
            oldCh[idxInOld] = undefined
            // 移動(dòng)節(jié)點(diǎn) 
            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é)點(diǎn)的頭部去舊的一組子節(jié)點(diǎn)中尋找，如果沒(méi)有找到，說(shuō)明這個(gè)節(jié)點(diǎn)是一個(gè)新的節(jié)點(diǎn)，則直接創(chuàng)建節(jié)點(diǎn)。如果找到了，通過(guò)索引去獲取對(duì)應(yīng)的舊節(jié)點(diǎn)的信息，如果節(jié)點(diǎn)可復(fù)用，則需要將當(dāng)前舊節(jié)點(diǎn)移動(dòng)到頭部即可。最后更新新節(jié)點(diǎn)的開(kāi)始節(jié)點(diǎn)的索引位置。