Vue3 diff算法之雙端diff算法詳解

更新時(shí)間：2022年09月04日 16:58:06 作者：無(wú)敵小書(shū)包

雙端Diff在可以解決更多簡(jiǎn)單Diff算法處理不了的場(chǎng)景，且比簡(jiǎn)單Diff算法性能更好。本文將通過(guò)示例為大家詳細(xì)講講雙端diff算法的實(shí)現(xiàn)與使用，需要的可以參考一下

雙端Diff算法

雙端Diff在可以解決更多簡(jiǎn)單Diff算法處理不了的場(chǎng)景，且比簡(jiǎn)單Diff算法性能更好。本篇是以簡(jiǎn)單Diff算法的案例來(lái)展開(kāi)的，不過(guò)沒(méi)有了解簡(jiǎn)單Diff算法直接看雙端Diff算法也是可以看明白的。

雙端比較的原理

引用簡(jiǎn)單Diff算法的例子 - 案例一

oldVNode: {
    type: 'div',
    children: [
      { type: 'p', children: '1', key: '1' },
      { type: 'p', children: '2', key: '2' },
      { type: 'p', children: '3', key: '3' },
    ]
  },
  newVNode: {
    type: 'div',
    children: [
      { type: 'p', children: '3', key: '3' },
      { type: 'p', children: '1', key: '1' },
      { type: 'p', children: '2', key: '2' }
    ]
  }

簡(jiǎn)單Diff的不足

這個(gè)案例使用簡(jiǎn)單Diff算法來(lái)更新它，會(huì)發(fā)生兩次DOM移動(dòng)操作。然而這并不是最優(yōu)解，其實(shí)只需要將 p - 3 節(jié)點(diǎn)移動(dòng)到 p - 1 對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)前面就可以。

這是理論上的，簡(jiǎn)單Diff算法并不能做到這一點(diǎn)，要想實(shí)現(xiàn)還得看雙端Diff算法。

雙端Diff介紹

顧名思義，雙端Diff算法就是同時(shí)對(duì)新舊兩組子節(jié)點(diǎn)兩個(gè)端點(diǎn)進(jìn)行比較的算法，因此需要四個(gè)索引值指向新舊虛擬節(jié)點(diǎn)列表的兩端。

結(jié)合該案例來(lái)看雙端Diff的方式 - 案例二

  newChildren: [
    { type: 'p', children: '4', key: '4' },
    { type: 'p', children: '2', key: '2' },
    { type: 'p', children: '1', key: '1' },
    { type: 'p', children: '3', key: '3' }
  ],
  oldChildren: [
    { type: 'p', children: '1', key: '1' },
    { type: 'p', children: '2', key: '2' },
    { type: 'p', children: '3', key: '3' },
    { type: 'p', children: '4', key: '4' }
  ]

newStartIdx / newEndIdx / oldStartIdx / oldEndIdx四個(gè)指針?lè)謩e指向新節(jié)點(diǎn)的第一個(gè)元素 / 新節(jié)點(diǎn)的最后一個(gè)元素 / 舊節(jié)點(diǎn)的第一個(gè)元素 / 舊節(jié)點(diǎn)的最后一個(gè)元素，指向的這四個(gè)元素稱(chēng)為 oldStartVNode / oldEndVNode / oldStartVNode / oldEndVNode。有了這些信息就可以互相比較了。

Diff流程

第一次diff

第一步：比較舊的一組子節(jié)點(diǎn)中的第一個(gè)子節(jié)點(diǎn) p-1 與新的一組子節(jié)點(diǎn)中的第一個(gè)子節(jié)點(diǎn) P-4，看看它們是否相同。由于兩者的 key 值不同，因此不相同，不可復(fù)用，手是什么都不做。
第二步：比較舊的一組子節(jié)點(diǎn)中的最后一個(gè)子節(jié)點(diǎn) p-4 與新的一組子節(jié)點(diǎn)中的最后一個(gè)子節(jié)點(diǎn) p-3，看看它們是否相同。由于兩者的 key 值不同，因此不相同，不可復(fù)用，于是什么都不做。
第三步：比較日的一組子節(jié)點(diǎn)中的第一個(gè)子節(jié)點(diǎn) p-1與新的一組子節(jié)點(diǎn)中的最后一個(gè)子節(jié)點(diǎn) p-3，看看它們是否相同。由于兩者的 key 值不同，因此不相同，不可復(fù)用，于是什么都不做。
第四步：比較舊的一組子節(jié)點(diǎn)中的最后一個(gè)子節(jié)點(diǎn) p-4 與新的一組子節(jié)點(diǎn)中的第一個(gè)子節(jié)點(diǎn)p-4。由于它們的key 值相同，因此可以進(jìn)行 DOM 復(fù)用。

在第四步找到了可以復(fù)用的節(jié)點(diǎn)，說(shuō)明它的真實(shí)DOM節(jié)點(diǎn)可以復(fù)用。對(duì)于可復(fù)用的節(jié)點(diǎn)通過(guò)移動(dòng)操作即可完成更新。

那么該如何移動(dòng)呢？分析下第四步比較過(guò)程的細(xì)節(jié)，第四步比較是比較舊的一組節(jié)點(diǎn)中的最后一個(gè)子節(jié)點(diǎn) 和新的一組子節(jié)點(diǎn)中的第一個(gè)子節(jié)點(diǎn)。這說(shuō)明節(jié)點(diǎn) p - 4 原本是最后一個(gè)子節(jié)點(diǎn)，但在新的順序中，它變成了第一個(gè)子節(jié)點(diǎn)。對(duì)應(yīng)到代碼，就是將索引 oldEndIdx 指向的虛擬節(jié)點(diǎn)所對(duì)應(yīng)的真實(shí)DOM移動(dòng)到索引 oldStartIdx 指向的虛擬節(jié)點(diǎn)所對(duì)應(yīng)的真實(shí)DOM前面。

第一次比較完之后的情況如下：

code

第一次比較對(duì)應(yīng)的代碼

function insert (el, container, anchor) {
  container.insertBefore(el, anchor)
}

function patchChildren (n1, n2, container) {
  if (typeof n2.children === 'string') {
  } else if (Array.isArray(n2.children)) {
    // 到這里說(shuō)明子節(jié)點(diǎn)都是數(shù)組類(lèi)型
    patchKeyedChildren(n1, n2, container)
  }
}

function patchKeyedChildren (n1, n2, container) {
  const oldChildren = n1.children
  const newChildren = n2.children
  // 四個(gè)端點(diǎn)指針
  let newStartIdx = 0
  let newEndIdx = newChildren.length - 1
  let oldStartIdx = 0
  let oldEndIdx = oldChildren.length - 1
  // 四個(gè)端點(diǎn)元素
  let newStartVNode = newChildren[newStartIdx]
  let newEndVNode = newChildren[newEndIdx]
  let oldStartVNode = oldChildren[oldStartIdx]
  let oldEndVNode = oldChildren[oldEndIdx]

  // 開(kāi)始Diff
  if (oldStartVNode.key === newStartVNode.key) {
  //  第一步 oldStartVNode - newStartVNode
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 第二步 oldEndVNode - newEndVNode
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 第三步 oldStartVNode - newEndVNode
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 第四步 oldEndVNode - newStartVNode

    // 調(diào)用patch打補(bǔ)丁
    patch(oldEndVNode, newStartVNode, container)
    // 移動(dòng)DOM操作    oldEndVNode.el移動(dòng) 到 oldStartVNode.el 前面
    insert(oldEndVNode.el, container, oldStartVNode.el)
    // 移動(dòng)DOM操作完成后
    oldEndVNode = oldChildren[--oldEndVNode]
    newStartVNode = newChildren[++newStartVNode]
  }
}

本次Diff完成之后還有其他節(jié)點(diǎn)需要繼續(xù)進(jìn)行，所以需要將diff的過(guò)程放入while循環(huán)中。滿(mǎn)足以下情況時(shí)，說(shuō)明所有節(jié)點(diǎn)更新完畢，因此while的條件為 oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx

第二次diff

第二次diff的情況如圖

第一步：比較舊的一組子節(jié)點(diǎn)中的頭部節(jié)點(diǎn) p-1 與新的一組子節(jié)點(diǎn)中的頭部節(jié)點(diǎn) p-2，看看它們是否相同。由于兩者的key 值不同，不可復(fù)用，所以什么都不做。（頭部節(jié)點(diǎn)：頭部素引 oldstartIdx 和 newstartIdx 所指向的節(jié)點(diǎn)）
第二步：比較1的一組子節(jié)點(diǎn)中的尾部節(jié)點(diǎn) p-3與新的一組子節(jié)點(diǎn)中的尾部節(jié)點(diǎn) p-3，兩者的 key 值相同，可以復(fù)用。另外，由于防者都處于尾部，因此不需要對(duì)真實(shí) DOM進(jìn)行移動(dòng)操作，只需要打補(bǔ)丁即可。

第二次diff后新舊節(jié)點(diǎn)的狀態(tài)如下

code

第二次比較對(duì)應(yīng)代碼

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 開(kāi)始Diff
    if (oldStartVNode.key === newStartVNode.key) {
      //  第一步 oldStartVNode - newStartVNode
    } else if (oldEndVNode.key === newEndVNode.key) {
      // 第二步 oldEndVNode - newEndVNode

      // 調(diào)用patch打補(bǔ)丁
      patch(oldEndVNode, newEndVNode, container)
      oldEndVNode = oldChildren[--oldEndIdx]
      newEndVNode = newChildren[--newEndIdx]
    } else if (oldStartVNode.key === newEndVNode.key) {
      // 第三步 oldStartVNode - newEndVNode
    } else if (oldEndVNode.key === newStartVNode.key) {
      // 第四步 oldEndVNode - newStartVNode

      // 調(diào)用patch打補(bǔ)丁
      patch(oldEndVNode, newStartVNode, container)
      // 移動(dòng)DOM操作    oldEndVNode.el移動(dòng) 到 oldStartVNode.el 前面
      insert(oldEndVNode.el, container, oldStartVNode.el)
      // 移動(dòng)DOM操作完成后
      oldEndVNode = oldChildren[--oldEndVNode]
      newStartVNode = newChildren[++newStartVNode]
    }
  }

第三次diff

第三次diff的情況如圖

第一步：比較舊的一組子節(jié)點(diǎn)中的頭部節(jié)點(diǎn)p-1 與新的組子節(jié)點(diǎn)的頭部節(jié)點(diǎn) p-2,看看它們是否相同。由于兩者key值不同不可復(fù)用，因此什么都不做。
第二步：比較舊的一組子節(jié)點(diǎn)中的尾部節(jié)點(diǎn) p-2與新的一組子節(jié)點(diǎn)中的尾部節(jié)點(diǎn) p-1看看它們是否相同，，由于兩者key值不同不可復(fù)用，因此什么都不做。
第三步：比較舊的一組子節(jié)點(diǎn)中的頭部節(jié)點(diǎn)p-1與新的一組子節(jié)申的尾部節(jié)點(diǎn)p-1，兩者的key 值相同，可以復(fù)用。

第三步比較中找到了相同節(jié)點(diǎn)，說(shuō)明 p - 1 原本時(shí)頭部節(jié)點(diǎn)，但在新的順序中，它變成了尾部節(jié)點(diǎn)。因此將p - 1對(duì)應(yīng)的真實(shí)DOM移動(dòng)到舊的子節(jié)點(diǎn)的尾部節(jié)點(diǎn) p - 2 對(duì)應(yīng)的真實(shí)DOM后面

第三次diff后的新舊節(jié)點(diǎn)狀態(tài)如下圖

code

第三次比較對(duì)應(yīng)代碼

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 開(kāi)始Diff
    if (oldStartVNode.key === newStartVNode.key) {
      //  第一步 oldStartVNode - newStartVNode
    } else if (oldEndVNode.key === newEndVNode.key) {
      // 第二步 oldEndVNode - newEndVNode

      // 調(diào)用patch打補(bǔ)丁
      patch(oldEndVNode, newEndVNode, container)
      oldEndVNode = oldChildren[--oldEndIdx]
      newEndVNode = newChildren[--newEndIdx]
    } else if (oldStartVNode.key === newEndVNode.key) {
      // 第三步 oldStartVNode - newEndVNode

      patch(oldStartVNode, newEndVNode, container)
      insert(oldStartVNode.el, container, newEndVNode.el.nextSibling)
      oldStartVNode = oldChildren[++oldStartIdx]
      newEndVNode = newChildren[--newEndIdx]
    } else if (oldEndVNode.key === newStartVNode.key) {
      // 第四步 oldEndVNode - newStartVNode

      // 調(diào)用patch打補(bǔ)丁
      patch(oldEndVNode, newStartVNode, container)
      // 移動(dòng)DOM操作    oldEndVNode.el移動(dòng) 到 oldStartVNode.el 前面
      insert(oldEndVNode.el, container, oldStartVNode.el)
      // 移動(dòng)DOM操作完成后
      oldEndVNode = oldChildren[--oldEndVNode]
      newStartVNode = newChildren[++newStartVNode]
    }
  }

第四次diff

第三次diff的情況如圖

第一步：比較舊的一組子節(jié)點(diǎn)的頭部節(jié)點(diǎn) p - 2 與新的一組子節(jié)點(diǎn)中的頭部節(jié)點(diǎn) p - 2。發(fā)現(xiàn)兩者key值相同，可以復(fù)用。但兩者在新舊兩組子節(jié)點(diǎn)中都是頭部節(jié)點(diǎn)，因此不需要移動(dòng)，只需要patch函數(shù)打補(bǔ)丁即可。

diff結(jié)果如圖

最后while條件為假，退出diff

code

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 開(kāi)始Diff
    if (oldStartVNode.key === newStartVNode.key) {
      //  第一步 oldStartVNode - newStartVNode

      patch(oldStartVNode, newStartVNode, container)
      oldStartVNode = oldChildren[++oldStartIdx]
      newStartVNode = newChildren[++newStartIdx]
    } else if (oldEndVNode.key === newEndVNode.key) {
      // 第二步 oldEndVNode - newEndVNode

      // 調(diào)用patch打補(bǔ)丁
      patch(oldEndVNode, newEndVNode, container)
      oldEndVNode = oldChildren[--oldEndIdx]
      newEndVNode = newChildren[--newEndIdx]
    } else if (oldStartVNode.key === newEndVNode.key) {
      // 第三步 oldStartVNode - newEndVNode

      patch(oldStartVNode, newEndVNode, container)
      insert(oldStartVNode.el, container, newEndVNode.el.nextSibling)
      oldStartVNode = oldChildren[++oldStartIdx]
      newEndVNode = newChildren[--newEndIdx]
    } else if (oldEndVNode.key === newStartVNode.key) {
      // 第四步 oldEndVNode - newStartVNode

      // 調(diào)用patch打補(bǔ)丁
      patch(oldEndVNode, newStartVNode, container)
      // 移動(dòng)DOM操作    oldEndVNode.el移動(dòng) 到 oldStartVNode.el 前面
      insert(oldEndVNode.el, container, oldStartVNode.el)
      // 移動(dòng)DOM操作完成后
      oldEndVNode = oldChildren[--oldEndVNode]
      newStartVNode = newChildren[++newStartVNode]
    }
  }

雙端Diff的優(yōu)勢(shì)

回到最開(kāi)始的例子，使用雙端Diff比較的時(shí)候，第一次循環(huán)的步驟四就能找到對(duì)應(yīng) p - 3的節(jié)點(diǎn)，然后將其移動(dòng)到p - 1之前。

只需要一次DOM操作就能完成更新。

非理想情況的處理方式

上面是一個(gè)比較理想的例子，四個(gè)步驟分別都能匹配到對(duì)應(yīng)的元素，實(shí)際上并非所有情況都能匹配到。

比如 - 案例三

  newChildren: [
    { type: 'p', children: '2', key: '2' },
    { type: 'p', children: '4', key: '4' },
    { type: 'p', children: '1', key: '1' },
    { type: 'p', children: '3', key: '3' }
  ],
  oldChildren: [
    { type: 'p', children: '1', key: '1' },
    { type: 'p', children: '2', key: '2' },
    { type: 'p', children: '3', key: '3' },
    { type: 'p', children: '4', key: '4' }
  ]

進(jìn)行第一輪比較時(shí)，無(wú)法命中四個(gè)步驟中的任何一步。

p - 1 === p - 2
p - 4 === p - 3
p - 1 === p - 3
p - 4 === p - 2

因此只能通過(guò)額外的步驟來(lái)處理非理想情況。頭部尾部都不能命中，那么舊看非頭/尾部的節(jié)點(diǎn)能否命中，拿新的一組子節(jié)點(diǎn)的頭部節(jié)點(diǎn)去舊的一組子節(jié)點(diǎn)中查找。

在舊的一組子節(jié)點(diǎn)中，找到與新的一組子節(jié)點(diǎn)頭部節(jié)點(diǎn)具有相同key值的節(jié)點(diǎn)，意味著要將找到的子節(jié)點(diǎn)移動(dòng)到真實(shí)DOM的頭部。

查找結(jié)果如圖

code

對(duì)應(yīng)功能代碼

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 開(kāi)始Diff
    if (oldStartVNode.key === newStartVNode.key) {
      //  第一步 oldStartVNode - newStartVNode
    } else if (oldEndVNode.key === newEndVNode.key) {
      // 第二步 oldEndVNode - newEndVNode
    } else if (oldStartVNode.key === newEndVNode.key) {
      // 第三步 oldStartVNode - newEndVNode
    } else if (oldEndVNode.key === newStartVNode.key) {
      // 第四步 oldEndVNode - newStartVNode
    } else {
      // 上面四個(gè)步驟都沒(méi)有命中

      // 遍歷舊的一組子節(jié)點(diǎn)，視圖尋找與newStartVNode擁有相同key值的節(jié)點(diǎn)
      // idInOld就是新的一組子節(jié)點(diǎn)的頭部節(jié)點(diǎn)在舊的一組子節(jié)點(diǎn)中的索引
      const idInOld = oldChildren.findIndex(
        node => node.key === newStartVNode.key
      )
      // idInOld > 0說(shuō)明找到了可復(fù)用的節(jié)點(diǎn)，并且需要將其對(duì)應(yīng)的真實(shí)DOM移動(dòng)到頭部
      if (idInOld > 0) {
        // 找到匹配到的節(jié)點(diǎn)，也就是需要移動(dòng)的節(jié)點(diǎn)
        const vNodeToMove = oldChildren[idInOld]
        // 調(diào)用 patch 更新
        patch(vNodeToMove, newStartVNode, container)
        // 將vNodeToMove插入到頭部節(jié)點(diǎn)oldStartVNode.el之前
        insert(vNodeToMove.el, container, oldStartVNode.el)
        // 由于位置 idInOld 處的節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)DOM已經(jīng)發(fā)生移動(dòng)，因此將其設(shè)置為 undefined
        oldChildren[idInOld] = undefined
        // 最后更新 newStartVNode 到下一個(gè)位置
        newStartVNode = newChildren[++newStartVNode]
      }

    }
  }

接下來(lái)第二個(gè)和第三個(gè)新節(jié)點(diǎn)都可以通過(guò)雙端對(duì)比找到匹配的節(jié)點(diǎn)，過(guò)程與第二個(gè)案例同理。

直到最后一個(gè)節(jié)點(diǎn)，此時(shí)舊節(jié)點(diǎn)列表的頭部節(jié)點(diǎn)是 undefined，因?yàn)樵摴?jié)點(diǎn)已經(jīng)被處理過(guò)了，所以不需要再處理它，直接跳過(guò)即可。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 開(kāi)始Diff
    // 如果頭部或尾部節(jié)點(diǎn)為undefined，說(shuō)明已經(jīng)處理過(guò)了，直接跳過(guò)
    if (!oldStartVNode) {
      oldStartVNode = oldChildren[++oldStartIdx]
    } else if (!oldEndVNode) {
      oldEndVNode = oldChildren[--oldEndIdx]
    } else if (oldStartVNode.key === newStartVNode.key) {
      //  第一步 oldStartVNode - newStartVNode
    } else if (oldEndVNode.key === newEndVNode.key) {
      // 第二步 oldEndVNode - newEndVNode
    } else if (oldStartVNode.key === newEndVNode.key) {
      // 第三步 oldStartVNode - newEndVNode
    } else if (oldEndVNode.key === newStartVNode.key) {
      // 第四步 oldEndVNode - newStartVNode
    } else {
      }
    }
  }

接下來(lái)的情況與上個(gè)案例同理。

添加新元素

當(dāng)我們拿新的一組子節(jié)點(diǎn)中的頭部節(jié)點(diǎn)去舊的一組子節(jié)點(diǎn)中尋找可復(fù)用節(jié)點(diǎn)時(shí)，并不是一定能找到。

案例四

newChildren: [
    { type: 'p', children: '4', key: '4' },
    { type: 'p', children: '1', key: '1' },
    { type: 'p', children: '3', key: '3' },
    { type: 'p', children: '2', key: '2' }
  ],
  oldChildren: [
    { type: 'p', children: '1', key: '1' },
    { type: 'p', children: '2', key: '2' },
    { type: 'p', children: '3', key: '3' }
  ]

雙端查找沒(méi)有匹配到

循環(huán)查找也沒(méi)有匹配到

p - 4經(jīng)過(guò)雙端對(duì)比，循環(huán)查找都沒(méi)有找到匹配的節(jié)點(diǎn)，說(shuō)明 p - 4 是一個(gè)新增節(jié)點(diǎn)，應(yīng)該將它創(chuàng)建并掛載到正確的位置。

那么應(yīng)該掛載到什么位置呢，因?yàn)楣?jié)點(diǎn)p - 4時(shí)新的一組子節(jié)點(diǎn)中的頭部節(jié)點(diǎn)，所以只需要將它掛載到當(dāng)前頭部節(jié)點(diǎn)之前即可。頭部節(jié)點(diǎn)指的是舊的一組子節(jié)點(diǎn)中的頭部節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)DOM節(jié)點(diǎn) p - 1。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 開(kāi)始Diff
    if (oldStartVNode.key === newStartVNode.key) {
      //  第一步 oldStartVNode - newStartVNode
    } else if (oldEndVNode.key === newEndVNode.key) {
      // 第二步 oldEndVNode - newEndVNode
    } else if (oldStartVNode.key === newEndVNode.key) {
      // 第三步 oldStartVNode - newEndVNode
    } else if (oldEndVNode.key === newStartVNode.key) {
      // 第四步 oldEndVNode - newStartVNode
    } else {
      // 上面四個(gè)步驟都沒(méi)有命中

      // 遍歷舊的一組子節(jié)點(diǎn)，視圖尋找與newStartVNode擁有相同key值的節(jié)點(diǎn)
      // idInOld就是新的一組子節(jié)點(diǎn)的頭部節(jié)點(diǎn)在舊的一組子節(jié)點(diǎn)中的索引
      const idInOld = oldChildren.findIndex(
        node => node.key === newStartVNode.key
      )
      // idInOld > 0說(shuō)明找到了可復(fù)用的節(jié)點(diǎn)，并且需要將其對(duì)應(yīng)的真實(shí)DOM移動(dòng)到頭部
      if (idInOld > 0) {
        // 找到匹配到的節(jié)點(diǎn)，也就是需要移動(dòng)的節(jié)點(diǎn)
        const vNodeToMove = oldChildren[idInOld]
        // 調(diào)用 patch 更新
        patch(vNodeToMove, newStartVNode, container)
        // 將vNodeToMove插入到頭部節(jié)點(diǎn)oldStartVNode.el之前
        insert(vNodeToMove.el, container, oldStartVNode.el)
        // 由于位置 idInOld 處的節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)DOM已經(jīng)發(fā)生移動(dòng)，因此將其設(shè)置為 undefined
        oldChildren[idInOld] = undefined
        // 最后更新 newStartVNode 到下一個(gè)位置
        newStartVNode = newChildren[++newStartVNode]
      } else {
        // 將 newStartVNode作為新節(jié)點(diǎn)掛載到頭部，使用當(dāng)前頭部節(jié)點(diǎn) oldStartVNode.el 作為錨點(diǎn)
        patch(null, newStartVNode, container, oldStartVNode.el)
      }
      // 更新頭部節(jié)點(diǎn)
      newStartVNode = newChildren[++newStartIdx]
    }
  }

當(dāng)條件 idInOld > 0不成立時(shí)，說(shuō)明沒(méi)有可以復(fù)用的節(jié)點(diǎn)，又由于newStartVNode是頭部節(jié)點(diǎn)，因此應(yīng)該將其作為新的頭部節(jié)點(diǎn)進(jìn)行掛載操作。

剩下節(jié)點(diǎn)的操作類(lèi)似于案例二。

新增節(jié)點(diǎn)可能在最后一次匹配到 - 案例五

  newChildren: [
    { type: 'p', children: '4', key: '4' },
    { type: 'p', children: '1', key: '1' },
    { type: 'p', children: '2', key: '2' },
    { type: 'p', children: '3', key: '3' }
  ],
  oldChildren: [
    { type: 'p', children: '1', key: '1' },
    { type: 'p', children: '2', key: '2' },
    { type: 'p', children: '3', key: '3' }
  ]

這里省去雙端匹配的流程

由于變量oldStartIdx 的值大于oldEndIdx的值，滿(mǎn)足更新停止的條件，更新停止了。但看圖可知，p - 4在整個(gè)更新過(guò)程中被一樓了，沒(méi)有得到任何處理。

因此可得：新的一組子節(jié)點(diǎn)中有一六得節(jié)點(diǎn)需要作為新節(jié)點(diǎn)掛載。索引值位于newStartIdx 和 newEndIdx 之間得所有節(jié)點(diǎn)都是新節(jié)點(diǎn)。掛載時(shí)得錨點(diǎn)仍然使用當(dāng)前頭部節(jié)點(diǎn) oldStartVNode.el。

因?yàn)榇藭r(shí)舊節(jié)點(diǎn)列表中得節(jié)點(diǎn)可能為undefined，因此可能出現(xiàn)問(wèn)題；但新節(jié)點(diǎn)列表得順序已經(jīng)被更新了，所以更新過(guò)得新節(jié)點(diǎn)對(duì)應(yīng)得真實(shí)DOM順序都已經(jīng)重新牌列，便可以取錨點(diǎn)：

const anchor = newChildren[newEndIdx + 1] ? newChildren[newEndIdx + 1].el : null

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  
  }
  // 說(shuō)明有新節(jié)點(diǎn)需要掛載
  if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
    for (let i = newStartIdx; i < newEndIdx; i++) {
      const anchor = newChildren[newEndIdx + 1] ? newChildren[newEndIdx + 1].el : null
      patch(null, newChildren[i], container, anchor)
    }
  }

移除不存在得節(jié)點(diǎn)

除了新增節(jié)點(diǎn)得問(wèn)題后，還可能存在需要移除的節(jié)點(diǎn) - 案例六

  newChildren: [
    { type: 'p', children: '1', key: '1' },
    { type: 'p', children: '3', key: '3' }
  ],
  oldChildren: [
    { type: 'p', children: '1', key: '1' },
    { type: 'p', children: '2', key: '2' },
    { type: 'p', children: '3', key: '3' }
  ]

第一次、第二次循環(huán)的步驟于案例二同理

新節(jié)點(diǎn)更新完之后，發(fā)現(xiàn)還存在未處理的舊節(jié)點(diǎn)，這便是需要?jiǎng)h除的節(jié)點(diǎn)。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  
  }
  // 說(shuō)明有新節(jié)點(diǎn)需要掛載
  if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
    for (let i = newStartIdx; i < newEndIdx; i++) {
      const anchor = newChildren[newEndIdx + 1] ? newChildren[newEndIdx + 1].el : null
      patch(null, newChildren[i], container, anchor)
    }
  } else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {
    // 有需要?jiǎng)h除的節(jié)點(diǎn)
    for (let i = oldStartIdx; i < oldEndIdx; i++) {
      unmount(oldChildren[i])
    }
  }

雙端Diff完整代碼

function patchKeyedChildren (n1, n2, container) {
  const oldChildren = n1.children
  const newChildren = n2.children
  // 四個(gè)端點(diǎn)指針
  let newStartIdx = 0
  let newEndIdx = newChildren.length - 1
  let oldStartIdx = 0
  let oldEndIdx = oldChildren.length - 1
  // 四個(gè)端點(diǎn)元素
  let newStartVNode = newChildren[newStartIdx]
  let newEndVNode = newChildren[newEndIdx]
  let oldStartVNode = oldChildren[oldStartIdx]
  let oldEndVNode = oldChildren[oldEndIdx]

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 開(kāi)始Diff
    // 如果頭部或尾部節(jié)點(diǎn)為undefined，說(shuō)明已經(jīng)處理過(guò)了，直接跳過(guò)
    if (!oldStartVNode) {
      oldStartVNode = oldChildren[++oldStartIdx]
    } else if (!oldEndVNode) {
      oldEndVNode = oldChildren[--oldEndIdx]
    } else if (oldStartVNode.key === newStartVNode.key) {
      //  第一步 oldStartVNode - newStartVNode

      patch(oldStartVNode, newStartVNode, container)
      oldStartVNode = oldChildren[++oldStartIdx]
      newStartVNode = newChildren[++newStartIdx]
    } else if (oldEndVNode.key === newEndVNode.key) {
      // 第二步 oldEndVNode - newEndVNode

      // 調(diào)用patch打補(bǔ)丁
      patch(oldEndVNode, newEndVNode, container)
      oldEndVNode = oldChildren[--oldEndIdx]
      newEndVNode = newChildren[--newEndIdx]
    } else if (oldStartVNode.key === newEndVNode.key) {
      // 第三步 oldStartVNode - newEndVNode

      patch(oldStartVNode, newEndVNode, container)
      insert(oldStartVNode.el, container, newEndVNode.el.nextSibling)
      oldStartVNode = oldChildren[++oldStartIdx]
      newEndVNode = newChildren[--newEndIdx]
    } else if (oldEndVNode.key === newStartVNode.key) {
      // 第四步 oldEndVNode - newStartVNode

      // 調(diào)用patch打補(bǔ)丁
      patch(oldEndVNode, newStartVNode, container)
      // 移動(dòng)DOM操作    oldEndVNode.el移動(dòng) 到 oldStartVNode.el 前面
      insert(oldEndVNode.el, container, oldStartVNode.el)
      // 移動(dòng)DOM操作完成后
      oldEndVNode = oldChildren[--oldEndVNode]
      newStartVNode = newChildren[++newStartVNode]
    } else {
      // 上面四個(gè)步驟都沒(méi)有命中

      // 遍歷舊的一組子節(jié)點(diǎn)，視圖尋找與newStartVNode擁有相同key值的節(jié)點(diǎn)
      // idInOld就是新的一組子節(jié)點(diǎn)的頭部節(jié)點(diǎn)在舊的一組子節(jié)點(diǎn)中的索引
      const idInOld = oldChildren.findIndex(
        node => node.key === newStartVNode.key
      )
      // idInOld > 0說(shuō)明找到了可復(fù)用的節(jié)點(diǎn)，并且需要將其對(duì)應(yīng)的真實(shí)DOM移動(dòng)到頭部
      if (idInOld > 0) {
        // 找到匹配到的節(jié)點(diǎn)，也就是需要移動(dòng)的節(jié)點(diǎn)
        const vNodeToMove = oldChildren[idInOld]
        // 調(diào)用 patch 更新
        patch(vNodeToMove, newStartVNode, container)
        // 將vNodeToMove插入到頭部節(jié)點(diǎn)oldStartVNode.el之前
        insert(vNodeToMove.el, container, oldStartVNode.el)
        // 由于位置 idInOld 處的節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)DOM已經(jīng)發(fā)生移動(dòng)，因此將其設(shè)置為 undefined
        oldChildren[idInOld] = undefined
        // 最后更新 newStartVNode 到下一個(gè)位置
        newStartVNode = newChildren[++newStartVNode]
      } else {
        // 將 newStartVNode作為新節(jié)點(diǎn)掛載到頭部，使用當(dāng)前頭部節(jié)點(diǎn) oldStartVNode.el 作為錨點(diǎn)
        patch(null, newStartVNode, container, oldStartVNode.el)
      }
      // 更新頭部節(jié)點(diǎn)
      newStartVNode = newChildren[++newStartIdx]
    }
  }

  if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
    // 說(shuō)明有新節(jié)點(diǎn)需要掛載
    for (let i = newStartIdx; i < newEndIdx; i++) {
      const anchor = newChildren[newEndIdx + 1] ? newChildren[newEndIdx + 1].el : null
      patch(null, newChildren[i], container, anchor)
    }
  } else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {
    // 有需要?jiǎng)h除的節(jié)點(diǎn)
    for (let i = oldStartIdx; i < oldEndIdx; i++) {
      unmount(oldChildren[i])
    }
  }
}

以上就是Vue3 diff算法之雙端diff算法詳解的詳細(xì)內(nèi)容，更多關(guān)于Vue3雙端diff算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: