React、Vue2-x、Vue3-0 的 diff 算法

作者：孫延哲

本文不講解 vDom 實現，mount 掛載，以及 render 函數。只討論三種 diff 算法。VNode 類型不考慮 component、functional-component、Fragment、Teleport。只考慮 Element 和 Text。此文章全部代碼可參考該項目（https://github.com/sunyanzhe/virtual-dom）。

下面的 diff 算法中會出現幾個方法，在這裏進行羅列，並說明其功能

mount(vnode, parent, [refNode]): 通過vnode生成真實的DOM節點。parent爲其父級的真實 DOM 節點，refNode爲真實的DOM節點，其父級節點爲parent。如果refNode不爲空，vnode生成的DOM節點就會插入到refNode之前；如果refNode爲空，那麼vnode生成的DOM節點就作爲最後一個子節點插入到parent中
patch(prevNode, nextNode, parent): 可以簡單的理解爲給當前DOM節點進行更新，並且調用diff算法對比自身的子節點;

一、React-Diff

===============

React 的思路是遞增法。通過對比新的列表中的節點，在原本的列表中的位置是否是遞增，來判斷當前節點是否需要移動。

實現原理

來看這樣一個例子。

nextList爲新的列表，prevList爲舊列表。這個例子我們一眼能看出來，新列表是不需要進行移動的。下面我用react的遞增思想，解釋一下爲什麼新列表中的節點不需要移動。

我們首先遍歷nextList，並且找到每一個節點，在prevList中的位置。

找到位置以後，與上一個節點的位置進行對比，如果當前的位置大於上一個位置，說明當前節點不需要移動。因此我們要定義一個lastIndex來記錄上一個節點的位置。

function foo(prevList, nextList) {
    let lastIndex = 0
    for (let i = 0; i < nextList.length; i++) {
        let nextItem = nextList[i];
        for (let j = 0; j < prevList.length; j++) {
            let prevItem = prevList[j]
            if (nextItem === prevItem) {
                if (j < lastIndex) {
                    // 需要移動節點
                } else {
                    // 不需要移動節點，記錄當前位置，與之後的節點進行對比
                    lastIndex = j
                }
            }
        }
    }
}

在上面的例子中，nextList每個節點在prevList的位置爲0 1 2 3。每一項都要比前一項要大，所以不需要移動，這就是react的diff算法的原理。

找到需要移動的節點

在上一小節中，我們是通過對比值是否相等，查找的對應位置。但是在 vdom 中，每一個節點都是一個 vNode，我們應該如何進行判斷呢？

答案就是key，我們通過對每個節點的key進行賦值，並且讓處於同一children數組下的vnode的key都不相同，以此來確定每個節點的唯一性，並進行新舊列表的對比。

function reactDiff(prevChildren, nextChildren, parent) {
    let lastIndex = 0
    for (let i = 0; i < nextChildren.length; i++) {
        let nextChild = nextChildren[i];
        for (let j = 0; j < prevChildren.length; j++) {
            let prevChild = prevChildren[j]
            if (nextChild.key === prevChild.key) {
                patch(prevChild, nextChild, parent)
                if (j < lastIndex) {
                    // 需要移動節點
                } else {
                    // 不需要移動節點，記錄當前位置，與之後的節點進行對比
                    lastIndex = j
                }
            }
        }
    }
}

移動節點

首先我們先明確一點，移動節點所指的節點是DOM節點。vnode.el指向該節點對應的真實DOM節點。patch方法會將更新過後的DOM節點，賦值給新的vnode的el屬性。

爲了畫圖方便，我們用key的值來表示vnode節點。爲了行文方便，我們把key值爲a的vnode簡寫爲vnode-a，vnode-a對應的真實 DOM 節點爲DOM-A

我們來將上圖的例子代入reactDiff中執行。我們遍歷新列表，並查找vnode在舊列表中的位置。當遍歷到vnode-d時，之前遍歷在舊列表的位置爲0 < 2 < 3，說明A C D這三個節點都是不需要移動的。此時lastIndex = 3, 並進入下一次循環，發現vnode-b在舊列表的index爲1，1 < 3，說明DOM-B要移動。

通過觀察我們能發現，只需要把DOM-B移動到DOM-D之後就可以了。也就是找到需要移動的 VNode，我們稱該 VNode 爲 α，將 α 對應的真實的 DOM 節點移動到，α 在新列表中的前一個 VNode 對應的真實 DOM 的後面。

在上述的例子中，就是將vnode-b對應的真實 DOM 節點DOM-B, 移動到vnode-b在新列表中的前一個VNode——vnode-d對應的真實 DOM 節點DOM-D的後面。

function reactDiff(prevChildren, nextChildren, parent) {
    let lastIndex = 0
    for (let i = 0; i < nextChildren.length; i++) {
        let nextChild = nextChildren[i];
        for (let j = 0; j < prevChildren.length; j++) {
            let prevChild = prevChildren[j]
            if (nextChild.key === prevChild.key) {
                patch(prevChild, nextChild, parent)
                if (j < lastIndex) {
                    // 移動到前一個節點的後面
                    let refNode = nextChildren[i - 1].el.nextSibling;
                    parent.insertBefore(nextChild.el, refNode)
                } else {
                    // 不需要移動節點，記錄當前位置，與之後的節點進行對比
                    lastIndex = j
                }
            }
        }
    }
}

爲什麼是這樣移動的呢？首先我們列表是從頭到尾遍歷的。這就意味着對於當前VNode節點來說，該節點之前的所有節點都是排好序的，如果該節點需要移動，那麼只需要將 DOM 節點移動到前一個vnode節點之後就可以，因爲在新列表中vnode的順序就是這樣的。

添加節點

至此，我們面臨兩個問題：1. 如何發現全新的節點、2. 生成的DOM節點插入到哪裏

我們先來解決第一個問題，找節點還是比較簡單的，我們定義一個find變量值爲false。如果在舊列表找到了key
相同的vnode，就將find的值改爲true。當遍歷結束後判斷find值，如果爲false，說明當前節點爲新節點。

function reactDiff(prevChildren, nextChildren, parent) {
  let lastIndex = 0
  for (let i = 0; i < nextChildren.length; i++) {
    let nextChild = nextChildren[i],
      find = false
    for (let j = 0; j < prevChildren.length; j++) {
      let prevChild = prevChildren[j]
      if (nextChild.key === prevChild.key) {
        find = true
        patch(prevChild, nextChild, parent)
        if (j < lastIndex) {
          // 移動到前一個節點的後面
          let refNode = nextChildren[i - 1].el.nextSibling
          parent.insertBefore(nextChild.el, refNode)
        } else {
          // 不需要移動節點，記錄當前位置，與之後的節點進行對比
          lastIndex = j
        }
        break
      }
    }
    if (!find) {
      // 插入新節點
    }
  }
}

但是這裏有一種特殊情況需要注意，就是新的節點位於新列表的第一個，這時候我們需要找到舊列表第一個節點，將新節點插入到原來第一個節點之前就可以了。

function reactDiff(prevChildren, nextChildren, parent) {
  let lastIndex = 0
  for (let i = 0; i < nextChildren.length; i++) {
    let nextChild = nextChildren[i],
      find = false
    for (let j = 0; j < prevChildren.length; j++) {
      let prevChild = prevChildren[j]
      if (nextChild.key === prevChild.key) {
        find = true
        patch(prevChild, nextChild, parent)
        if (j < lastIndex) {
          // 移動到前一個節點的後面
          let refNode = nextChildren[i - 1].el.nextSibling
          parent.insertBefore(nextChild.el, refNode)
        } else {
          // 不需要移動節點，記錄當前位置，與之後的節點進行對比
          lastIndex = j
        }
        break
      }
    }
    if (!find) {
      // 插入新節點
      let refNode = i <= 0 ? prevChildren[0].el : nextChildren[i - 1].el.nextSibling
      mount(nextChild, parent, refNode)
    }
  }
}

移除節點

有增就有減，當舊的節點不在新列表中時，我們就將其對應的 DOM 節點移除。

function reactDiff(prevChildren, nextChildren, parent) {
  let lastIndex = 0
  for (let i = 0; i < nextChildren.length; i++) {
    let nextChild = nextChildren[i],
      find = false
    for (let j = 0; j < prevChildren.length; j++) {
      let prevChild = prevChildren[j]
      if (nextChild.key === prevChild.key) {
        find = true
        patch(prevChild, nextChild, parent)
        if (j < lastIndex) {
          // 移動到前一個節點的後面
          let refNode = nextChildren[i - 1].el.nextSibling
          parent.insertBefore(nextChild.el, refNode)
        } else {
          // 不需要移動節點，記錄當前位置，與之後的節點進行對比
          lastIndex = j
        }
        break
      }
    }
    if (!find) {
      // 插入新節點
      let refNode = i <= 0 ? prevChildren[0].el : nextChildren[i - 1].el.nextSibling
      mount(nextChild, parent, refNode)
    }
  }
  for (let i = 0; i < prevChildren.length; i++) {
    let prevChild = prevChildren[i],
      key = prevChild.key,
      has = nextChildren.find((item) => item.key === key)
    if (!has) parent.removeChild(prevChild.el)
  }
}

以上就是 React 的 diff 算法的思路。

目前的reactDiff的時間複雜度爲O(m*n)，我們可以用空間換時間，把key與index的關係維護成一個Map，從而將時間複雜度降低爲O(n)，具體的代碼可以查看此項目。

我們接下來看這樣一個例子

根據reactDiff的思路，我們需要先將DOM-A移動到DOM-C之後，然後再將DOM-B移動到DOM-A之後，完成Diff。但是我們通過觀察可以發現，只要將DOM-C移動到DOM-A之前就可以完成Diff。

這裏是有可優化的空間的，接下來我們介紹vue2.x中的diff算法——雙端比較，該算法解決了上述的問題。

二、Vue2.X Diff —— 雙端比較

實現原理

我們先用四個指針指向兩個列表的頭尾

function vue2Diff(prevChildren, nextChildren, parent) {
  let oldStartIndex = 0,
    oldEndIndex = prevChildren.length - 1
  ;(newStartIndex = 0), (newEndIndex = nextChildren.length - 1)
  let oldStartNode = prevChildren[oldStartIndex],
    oldEndNode = prevChildren[oldEndIndex],
    newStartNode = nextChildren[nextStartIndex],
    newEndNode = nextChildren[nextEndIndex]
}

我們根據四個指針找到四個節點，然後進行對比，那麼如何對比呢？我們按照以下四個步驟進行對比

使用舊列表的頭一個節點oldStartNode與新列表的頭一個節點newStartNode對比
使用舊列表的最後一個節點oldEndNode與新列表的最後一個節點newEndNode對比
使用舊列表的頭一個節點oldStartNode與新列表的最後一個節點newEndNode對比
使用舊列表的最後一個節點oldEndNode與新列表的頭一個節點newStartNode對比

function vue2Diff(prevChildren, nextChildren, parent) {
  let oldStartIndex = 0,
    oldEndIndex = prevChildren.length - 1
  ;(newStartIndex = 0), (newEndIndex = nextChildren.length - 1)
  let oldStartNode = prevChildren[oldStartIndex],
    oldEndNode = prevChildren[oldEndIndex],
    newStartNode = nextChildren[newStartIndex],
    newEndNode = nextChildren[newEndIndex]

  if (oldStartNode.key === newStartNode.key) {
  } else if (oldEndNode.key === newEndNode.key) {
  } else if (oldStartNode.key === newEndNode.key) {
  } else if (oldEndNode.key === newStartNode.key) {
  }
}

當舊列表的頭一個節點oldStartNode與新列表的頭一個節點newStartNode對比時key相同。那麼舊列表的頭指針oldStartIndex與新列表的頭指針newStartIndex同時向後移動一位。
當舊列表的最後一個節點oldEndNode與新列表的最後一個節點newEndNode對比時key相同。那麼舊列表的尾指針oldEndIndex與新列表的尾指針newEndIndex同時向前移動一位。
當舊列表的頭一個節點oldStartNode與新列表的最後一個節點newEndNode對比時key相同。那麼舊列表的頭指針oldStartIndex向後移動一位；新列表的尾指針newEndIndex向前移動一位。
當舊列表的最後一個節點oldEndNode與新列表的頭一個節點newStartNode對比時key相同。那麼舊列表的尾指針oldEndIndex向前移動一位；新列表的頭指針newStartIndex向後移動一位。

function vue2Diff(prevChildren, nextChildren, parent) {
  let oldStartIndex = 0,
    oldEndIndex = prevChildren.length - 1,
    newStartIndex = 0,
    newEndIndex = nextChildren.length - 1
  let oldStartNode = prevChildren[oldStartIndex],
    oldEndNode = prevChildren[oldEndIndex],
    newStartNode = nextChildren[newStartIndex],
    newEndNode = nextChildren[newEndIndex]

  if (oldStartNode.key === newStartNode.key) {
    patch(oldvStartNode, newStartNode, parent)

    oldStartIndex++
    newStartIndex++
    oldStartNode = prevChildren[oldStartIndex]
    newStartNode = nextChildren[newStartIndex]
  } else if (oldEndNode.key === newEndNode.key) {
    patch(oldEndNode, newEndNode, parent)

    oldEndIndex--
    newEndIndex--
    oldEndNode = prevChildren[oldEndIndex]
    newEndNode = nextChildren[newEndIndex]
  } else if (oldStartNode.key === newEndNode.key) {
    patch(oldStartNode, newEndNode, parent)

    oldStartIndex++
    newEndIndex--
    oldStartNode = prevChildren[oldStartIndex]
    newEndNode = nextChildren[newEndIndex]
  } else if (oldEndNode.key === newStartNode.key) {
    patch(oldEndNode, newStartNode, parent)

    oldEndIndex--
    nextStartIndex++
    oldEndNode = prevChildren[oldEndIndex]
    newStartNode = nextChildren[newStartIndex]
  }
}

function vue2Diff(prevChildren, nextChildren, parent) {
  let oldStartIndex = 0,
    oldEndIndex = prevChildren.length - 1,
    newStartIndex = 0,
    newEndIndex = nextChildren.length - 1
  let oldStartNode = prevChildren[oldStartIndex],
    oldEndNode = prevChildren[oldEndIndex],
    newStartNode = nextChildren[newStartIndex],
    newEndNode = nextChildren[newEndIndex]
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartNode.key === newStartNode.key) {
      patch(oldStartNode, newStartNode, parent)

      oldStartIndex++
      newStartIndex++
      oldStartNode = prevChildren[oldStartIndex]
      newStartNode = nextChildren[newStartIndex]
    } else if (oldEndNode.key === newEndNode.key) {
      patch(oldEndNode, newEndNode, parent)

      oldEndIndex--
      newndIndex--
      oldEndNode = prevChildren[oldEndIndex]
      newEndNode = nextChildren[newEndIndex]
    } else if (oldStartNode.key === newEndNode.key) {
      patch(oldvStartNode, newEndNode, parent)

      oldStartIndex++
      newEndIndex--
      oldStartNode = prevChildren[oldStartIndex]
      newEndNode = nextChildren[newEndIndex]
    } else if (oldEndNode.key === newStartNode.key) {
      patch(oldEndNode, newStartNode, parent)

      oldEndIndex--
      newStartIndex++
      oldEndNode = prevChildren[oldEndIndex]
      newStartNode = nextChildren[newStartIndex]
    }
  }
}

至此整體的循環我們就全部完成了，下面我們需要考慮這樣兩個問題：

什麼情況下DOM節點需要移動
DOM節點如何移動

我們來解決第一個問題：什麼情況下需要移動，我們還是以上圖爲例。

當我們在第一個循環時，在第四步發現舊列表的尾節點oldEndNode與新列表的頭節點newStartNode的key相同，是可複用的DOM節點。通過觀察我們可以發現，原本在舊列表末尾的節點，卻是新列表中的開頭節點，沒有人比他更靠前，因爲他是第一個，所以我們只需要把當前的節點移動到原本舊列表中的第一個節點之前，讓它成爲第一個節點即可。

function vue2Diff(prevChildren, nextChildren, parent) {
  // ...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartNode.key === newStartNode.key) {
      // ...
    } else if (oldEndNode.key === newEndNode.key) {
      // ...
    } else if (oldStartNode.key === newEndNode.key) {
      // ...
    } else if (oldEndNode.key === newStartNode.key) {
      patch(oldEndNode, newStartNode, parent)
      // 移動到舊列表頭節點之前
      parent.insertBefore(oldEndNode.el, oldStartNode.el)

      oldEndIndex--
      newStartIndex++
      oldEndNode = prevChildren[oldEndIndex]
      newStartNode = nextChildren[newStartIndex]
    }
  }
}

然後我們進入第二次循環，我們在第二步發現，舊列表的尾節點oldEndNode和新列表的尾節點newEndNode爲複用節點。原本在舊列表中就是尾節點，在新列表中也是尾節點，說明該節點不需要移動，所以我們什麼都不需要做。

同理，如果是舊列表的頭節點oldStartNode和新列表的頭節點newStartNode爲複用節點，我們也什麼都不需要做。

進入第三次循環，我們在第三部發現，舊列表的頭節點oldStartNode和新列表的尾節點newEndNode爲複用節點。到這一步聰明如你肯定就一眼可以看出來了，我們只要將DOM-A移動到DOM-B後面就可以了。

依照慣例我們還是解釋一下，原本舊列表中是頭節點，然後在新列表中是尾節點。那麼只要在舊列表中把當前的節點移動到原本尾節點的後面，就可以了。

function vue2Diff(prevChildren, nextChildren, parent) {
  // ...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartNode.key === newStartNode.key) {
      // ...
    } else if (oldEndNode.key === newEndNode.key) {
      // ...
    } else if (oldStartNode.key === newEndNode.key) {
      patch(oldStartNode, newEndNode, parent)
      parent.insertBefore(oldStartNode.el, oldEndNode.el.nextSibling)

      oldStartIndex++
      newEndIndex--
      oldStartNode = prevChildren[oldStartIndex]
      newEndNode = nextChildren[newEndIndex]
    } else if (oldEndNode.key === newStartNode.key) {
      //...
    }
  }
}

OK，進入最後一個循環。在第一步舊列表頭節點oldStartNode與新列表頭節點newStartNode位置相同，所以啥也不用做。然後結束循環，這就是Vue2 雙端比較的原理。

非理想情況

上一小節，我們講了雙端比較的原理，但是有一種特殊情況，當四次對比都沒找到複用節點時，我們只能拿新列表的第一個節點去舊列表中找與其key相同的節點。

function vue2Diff(prevChildren, nextChildren, parent) {
  //...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartNode.key === newStartNode.key) {
      //...
    } else if (oldEndNode.key === newEndNode.key) {
      //...
    } else if (oldStartNode.key === newEndNode.key) {
      //...
    } else if (oldEndNode.key === newStartNode.key) {
      //...
    } else {
      // 在舊列表中找到 和新列表頭節點key 相同的節點
      let newKey = newStartNode.key,
        oldIndex = prevChildren.findIndex((child) => child.key === newKey)
    }
  }
}

找節點的時候其實會有兩種情況：一種在舊列表中找到了，另一種情況是沒找到。我們先以上圖爲例，說一下找到的情況。

當我們在舊列表中找到對應的VNode，我們只需要將找到的節點的DOM元素，移動到開頭就可以了。這裏的邏輯其實和第四步的邏輯是一樣的，只不過第四步是移動的尾節點，這裏是移動找到的節點。DOM移動後，由我們將舊列表中的節點改爲undefined，這是至關重要的一步，因爲我們已經做了節點的移動了所以我們不需要進行再次的對比了。最後我們將頭指針newStartIndex向後移一位。

function vue2Diff(prevChildren, nextChildren, parent) {
  //...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartNode.key === newStartNode.key) {
      //...
    } else if (oldEndNode.key === newEndNode.key) {
      //...
    } else if (oldStartNode.key === newEndNode.key) {
      //...
    } else if (oldEndNode.key === newStartNode.key) {
      //...
    } else {
      // 在舊列表中找到 和新列表頭節點key 相同的節點
      let newtKey = newStartNode.key,
        oldIndex = prevChildren.findIndex((child) => child.key === newKey)

      if (oldIndex > -1) {
        let oldNode = prevChildren[oldIndex]
        patch(oldNode, newStartNode, parent)
        parent.insertBefore(oldNode.el, oldStartNode.el)
        prevChildren[oldIndex] = undefined
      }
      newStartNode = nextChildren[++newStartIndex]
    }
  }
}

如果在舊列表中沒有找到複用節點呢？很簡單，直接創建一個新的節點放到最前面就可以了，然後後移頭指針newStartIndex。

function vue2Diff(prevChildren, nextChildren, parent) {
  //...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartNode.key === newStartNode.key) {
      //...
    } else if (oldEndNode.key === newEndNode.key) {
      //...
    } else if (oldStartNode.key === newEndNode.key) {
      //...
    } else if (oldEndNode.key === newStartNode.key) {
      //...
    } else {
      // 在舊列表中找到 和新列表頭節點key 相同的節點
      let newtKey = newStartNode.key,
        oldIndex = prevChildren.findIndex((child) => child.key === newKey)

      if (oldIndex > -1) {
        let oldNode = prevChildren[oldIndex]
        patch(oldNode, newStartNode, parent)
        parent.insertBefore(oldNode.el, oldStartNode.el)
        prevChildren[oldIndex] = undefined
      } else {
        mount(newStartNode, parent, oldStartNode.el)
      }
      newStartNode = nextChildren[++newStartIndex]
    }
  }
}

最後當舊列表遍歷到undefind時就跳過當前節點。

function vue2Diff(prevChildren, nextChildren, parent) {
  //...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartNode === undefind) {
      oldStartNode = prevChildren[++oldStartIndex]
    } else if (oldEndNode === undefind) {
      oldEndNode = prevChildren[--oldEndIndex]
    } else if (oldStartNode.key === newStartNode.key) {
      //...
    } else if (oldEndNode.key === newEndNode.key) {
      //...
    } else if (oldStartNode.key === newEndNode.key) {
      //...
    } else if (oldEndNode.key === newStartNode.key) {
      //...
    } else {
      // ...
    }
  }
}

添加節點

我們先來看一個例子

這個例子非常簡單，幾次循環都是尾節點相同，尾指針一直向前移動，直到循環結束，如下圖：

此時oldEndIndex以及小於了oldStartIndex，但是新列表中還有剩餘的節點，我們只需要將剩餘的節點依次插入到oldStartNode的DOM之前就可以了。爲什麼是插入oldStartNode之前呢？原因是剩餘的節點在新列表的位置是位於oldStartNode之前的，如果剩餘節點是在oldStartNode之後，oldStartNode就會先行對比，這個需要思考一下，其實還是與第四步的思路一樣。

function vue2Diff(prevChildren, nextChildren, parent) {
  //...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    // ...
  }
  if (oldEndIndex < oldStartIndex) {
    for (let i = newStartIndex; i <= newEndIndex; i++) {
      mount(nextChildren[i], parent, prevStartNode.el)
    }
  }
}

移除節點

與上一小節的情況相反，當新列表的newEndIndex小於newStartIndex時，我們將舊列表剩餘的節點刪除即可。這裏我們需要注意，舊列表的undefind。在第二小節中我們提到過，當頭尾節點都不相同時，我們會去舊列表中找新列表的第一個節點，移動完 DOM 節點後，將舊列表的那個節點改爲undefind。所以我們在最後的刪除時，需要注意這些undefind，遇到的話跳過當前循環即可。

function vue2Diff(prevChildren, nextChildren, parent) {
  //...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    // ...
  }
  if (oldEndIndex < oldStartIndex) {
    for (let i = newStartIndex; i <= newEndIndex; i++) {
      mount(nextChildren[i], parent, prevStartNode.el)
    }
  } else if (newEndIndex < newStartIndex) {
    for (let i = oldStartIndex; i <= oldEndIndex; i++) {
      if (prevChildren[i]) {
        partent.removeChild(prevChildren[i].el)
      }
    }
  }
}

小結

至此雙端比較全部完成，以下是全部代碼。

function vue2diff(prevChildren, nextChildren, parent) {
  let oldStartIndex = 0,
    newStartIndex = 0,
    oldStartIndex = prevChildren.length - 1,
    newStartIndex = nextChildren.length - 1,
    oldStartNode = prevChildren[oldStartIndex],
    oldEndNode = prevChildren[oldStartIndex],
    newStartNode = nextChildren[newStartIndex],
    newEndNode = nextChildren[newStartIndex]
  while (oldStartIndex <= oldStartIndex && newStartIndex <= newStartIndex) {
    if (oldStartNode === undefined) {
      oldStartNode = prevChildren[++oldStartIndex]
    } else if (oldEndNode === undefined) {
      oldEndNode = prevChildren[--oldStartIndex]
    } else if (oldStartNode.key === newStartNode.key) {
      patch(oldStartNode, newStartNode, parent)

      oldStartIndex++
      newStartIndex++
      oldStartNode = prevChildren[oldStartIndex]
      newStartNode = nextChildren[newStartIndex]
    } else if (oldEndNode.key === newEndNode.key) {
      patch(oldEndNode, newEndNode, parent)

      oldStartIndex--
      newStartIndex--
      oldEndNode = prevChildren[oldStartIndex]
      newEndNode = nextChildren[newStartIndex]
    } else if (oldStartNode.key === newEndNode.key) {
      patch(oldStartNode, newEndNode, parent)
      parent.insertBefore(oldStartNode.el, oldEndNode.el.nextSibling)
      oldStartIndex++
      newStartIndex--
      oldStartNode = prevChildren[oldStartIndex]
      newEndNode = nextChildren[newStartIndex]
    } else if (oldEndNode.key === newStartNode.key) {
      patch(oldEndNode, newStartNode, parent)
      parent.insertBefore(oldEndNode.el, oldStartNode.el)
      oldStartIndex--
      newStartIndex++
      oldEndNode = prevChildren[oldStartIndex]
      newStartNode = nextChildren[newStartIndex]
    } else {
      let newKey = newStartNode.key,
        oldIndex = prevChildren.findIndex((child) => child && child.key === newKey)
      if (oldIndex === -1) {
        mount(newStartNode, parent, oldStartNode.el)
      } else {
        let prevNode = prevChildren[oldIndex]
        patch(prevNode, newStartNode, parent)
        parent.insertBefore(prevNode.el, oldStartNode.el)
        prevChildren[oldIndex] = undefined
      }
      newStartIndex++
      newStartNode = nextChildren[newStartIndex]
    }
  }
  if (newStartIndex > newStartIndex) {
    while (oldStartIndex <= oldStartIndex) {
      if (!prevChildren[oldStartIndex]) {
        oldStartIndex++
        continue
      }
      parent.removeChild(prevChildren[oldStartIndex++].el)
    }
  } else if (oldStartIndex > oldStartIndex) {
    while (newStartIndex <= newStartIndex) {
      mount(nextChildren[newStartIndex++], parent, oldStartNode.el)
    }
  }
}

三、 Vue3 Diff —— 最長遞增子序列

vue3的diff借鑑於 inferno，該算法其中有兩個理念。第一個是相同的前置與後置元素的預處理；第二個則是最長遞增子序列，此思想與React的diff類似又不盡相同。下面我們來一一介紹。

前置與後置的預處理

我們看這兩段文字

Hello World

Hey World

其實就簡單的看一眼我們就能發現，這兩段文字是有一部分是相同的，這些文字是不需要修改也不需要移動的，真正需要進行修改中間的幾個字母，所以diff就變成以下部分：

text1: 'llo'
text2: 'y'

接下來換成vnode，我們以下圖爲例。

圖中的被綠色框起來的節點，他們是不需要移動的，只需要進行打補丁patch就可以了。我們把該邏輯寫成代碼。

function vue3Diff(prevChildren, nextChildren, parent) {
  let j = 0,
    prevEnd = prevChildren.length - 1,
    nextEnd = nextChildren.length - 1,
    prevNode = prevChildren[j],
    nextNode = nextChildren[j]
  while (prevNode.key === nextNode.key) {
    patch(prevNode, nextNode, parent)
    j++
    prevNode = prevChildren[j]
    nextNode = nextChildren[j]
  }

  prevNode = prevChildren[prevEnd]
  nextNode = prevChildren[nextEnd]

  while (prevNode.key === nextNode.key) {
    patch(prevNode, nextNode, parent)
    prevEnd--
    nextEnd--
    prevNode = prevChildren[prevEnd]
    nextNode = prevChildren[nextEnd]
  }
}

這時候，我們就需要考慮邊界情況了，這裏有兩種情況。一種是j > prevEnd；另一種是j > nextEnd。

我們以這張圖爲例，此時j > prevEnd且j <= nextEnd，我們只需要把新列表中j到nextEnd之間剩下的節點插入進去就可以了。相反，如果j > nextEnd時，我們把舊列表中j到prevEnd之間的節點刪除就可以了。

function vue3Diff(prevChildren, nextChildren, parent) {
  // ...
  if (j > prevEnd && j <= nextEnd) {
    let nextpos = nextEnd + 1,
      refNode = nextpos >= nextChildren.length ? null : nextChildren[nextpos].el
    while (j <= nextEnd) mount(nextChildren[j++], parent, refNode)
  } else if (j > nextEnd && j <= prevEnd) {
    while (j <= prevEnd) parent.removeChild(prevChildren[j++].el)
  }
}

我們再繼續思考，在我們while循環時，指針是從兩端向內逐漸靠攏的，所以我們應該在循環中就應該去判斷邊界情況，我們使用label語法，當我們觸發邊界情況時，退出全部的循環，直接進入判斷。代碼如下：

function vue3Diff(prevChildren, nextChildren, parent) {
  let j = 0,
    prevEnd = prevChildren.length - 1,
    nextEnd = nextChildren.length - 1,
    prevNode = prevChildren[j],
    nextNode = nextChildren[j]
  // label語法
  outer: {
    while (prevNode.key === nextNode.key) {
      patch(prevNode, nextNode, parent)
      j++
      // 循環中如果觸發邊界情況，直接break，執行outer之後的判斷
      if (j > prevEnd || j > nextEnd) break outer
      prevNode = prevChildren[j]
      nextNode = nextChildren[j]
    }

    prevNode = prevChildren[prevEnd]
    nextNode = prevChildren[nextEnd]

    while (prevNode.key === nextNode.key) {
      patch(prevNode, nextNode, parent)
      prevEnd--
      nextEnd--
      // 循環中如果觸發邊界情況，直接break，執行outer之後的判斷
      if (j > prevEnd || j > nextEnd) break outer
      prevNode = prevChildren[prevEnd]
      nextNode = prevChildren[nextEnd]
    }
  }

  // 邊界情況的判斷
  if (j > prevEnd && j <= nextEnd) {
    let nextpos = nextEnd + 1,
      refNode = nextpos >= nextChildren.length ? null : nextChildren[nextpos].el
    while (j <= nextEnd) mount(nextChildren[j++], parent, refNode)
  } else if (j > nextEnd && j <= prevEnd) {
    while (j <= prevEnd) parent.removeChild(prevChildren[j++].el)
  }
}

判斷是否需要移動

其實幾個算法看下來，套路已經很明顯了，就是找到移動的節點，然後給他移動到正確的位置。把該加的新節點添加好，把該刪的舊節點刪了，整個算法就結束了。這個算法也不例外，我們接下來看一下它是如何做的。

當前/後置的預處理結束後，我們進入真正的diff環節。首先，我們先根據新列表剩餘的節點數量，創建一個source數組，並將數組填滿-1。

我們先寫這塊邏輯。

function vue3Diff(prevChildren, nextChildren, parent) {
  //...
  outer: {
    // ...
  }

  // 邊界情況的判斷
  if (j > prevEnd && j <= nextEnd) {
    // ...
  } else if (j > nextEnd && j <= prevEnd) {
    // ...
  } else {
    let prevStart = j,
      nextStart = j,
      nextLeft = nextEnd - nextStart + 1, // 新列表中剩餘的節點長度
      source = new Array(nextLeft).fill(-1) // 創建數組，填滿-1
  }
}

那麼這個source數組，是要做什麼的呢？他就是來做新舊節點的對應關係的，我們將新節點在舊列表的位置存儲在該數組中，我們在根據source計算出它的最長遞增子序列用於移動 DOM 節點。爲此，我們先建立一個對象存儲當前新列表中的節點與index的關係，再去舊列表中去找位置。

在找節點時要注意，如果舊節點在新列表中沒有的話，直接刪除就好。除此之外，我們還需要一個數量表示記錄我們已經patch過的節點，如果數量已經與新列表剩餘的節點數量一樣，那麼剩下的舊節點我們就直接刪除了就可以了。

function vue3Diff(prevChildren, nextChildren, parent) {
  //...
  outer: {
    // ...
  }

  // 邊界情況的判斷
  if (j > prevEnd && j <= nextEnd) {
    // ...
  } else if (j > nextEnd && j <= prevEnd) {
    // ...
  } else {
    let prevStart = j,
      nextStart = j,
      nextLeft = nextEnd - nextStart + 1, // 新列表中剩餘的節點長度
      source = new Array(nextLeft).fill(-1), // 創建數組，填滿-1
      nextIndexMap = {}, // 新列表節點與index的映射
      patched = 0 // 已更新過的節點的數量

    // 保存映射關係
    for (let i = nextStart; i <= nextEnd; i++) {
      let key = nextChildren[i].key
      nextIndexMap[key] = i
    }

    // 去舊列表找位置
    for (let i = prevStart; i <= prevEnd; i++) {
      let prevNode = prevChildren[i],
        prevKey = prevNode.key,
        nextIndex = nextIndexMap[prevKey]
      // 新列表中沒有該節點 或者 已經更新了全部的新節點，直接刪除舊節點
      if (nextIndex === undefind || patched >= nextLeft) {
        parent.removeChild(prevNode.el)
        continue
      }
      // 找到對應的節點
      let nextNode = nextChildren[nextIndex]
      patch(prevNode, nextNode, parent)
      // 給source賦值
      source[nextIndex - nextStart] = i
      patched++
    }
  }
}

找到位置後，我們觀察這個重新賦值後的source，我們可以看出，如果是全新的節點的話，其在source數組中對應的值就是初始的-1，通過這一步我們可以區分出來哪個爲全新的節點，哪個是可複用的。

其次，我們要判斷是否需要移動。那麼如何判斷移動呢？很簡單，和React一樣我們用遞增法，如果我們找到的index是一直遞增的，說明不需要移動任何節點。我們通過設置一個變量來保存是否需要移動的狀態。

function vue3Diff(prevChildren, nextChildren, parent) {
  //...
  outer: {
    // ...
  }

  // 邊界情況的判斷
  if (j > prevEnd && j <= nextEnd) {
    // ...
  } else if (j > nextEnd && j <= prevEnd) {
    // ...
  } else {
    let prevStart = j,
      nextStart = j,
      nextLeft = nextEnd - nextStart + 1, // 新列表中剩餘的節點長度
      source = new Array(nextLeft).fill(-1), // 創建數組，填滿-1
      nextIndexMap = {}, // 新列表節點與index的映射
      patched = 0,
      move = false, // 是否移動
      lastIndex = 0 // 記錄上一次的位置

    // 保存映射關係
    for (let i = nextStart; i <= nextEnd; i++) {
      let key = nextChildren[i].key
      nextIndexMap[key] = i
    }

    // 去舊列表找位置
    for (let i = prevStart; i <= prevEnd; i++) {
      let prevNode = prevChildren[i],
        prevKey = prevNode.key,
        nextIndex = nextIndexMap[prevKey]
      // 新列表中沒有該節點 或者 已經更新了全部的新節點，直接刪除舊節點
      if (nextIndex === undefind || patched >= nextLeft) {
        parent.removeChild(prevNode.el)
        continue
      }
      // 找到對應的節點
      let nextNode = nextChildren[nextIndex]
      patch(prevNode, nextNode, parent)
      // 給source賦值
      source[nextIndex - nextStart] = i
      patched++

      // 遞增方法，判斷是否需要移動
      if (nextIndex < lastIndex) {
        move = false
      } else {
        lastIndex = nextIndex
      }
    }

    if (move) {
      // 需要移動
    } else {
      //不需要移動
    }
  }
}

DOM 如何移動

判斷完是否需要移動後，我們就需要考慮如何移動了。一旦需要進行 DOM 移動，我們首先要做的就是找到source的最長遞增子序列。

function vue3Diff(prevChildren, nextChildren, parent) {
  //...
  if (move) {
    const seq = lis(source) // [0, 1]
    // 需要移動
  } else {
    //不需要移動
  }
}

什麼是最長遞增子序列：給定一個數值序列，找到它的一個子序列，並且子序列中的值是遞增的，子序列中的元素在原序列中不一定連續。

例如給定數值序列爲：[0, 8, 4, 12]。

那麼它的最長遞增子序列就是：[0, 8, 12]。

當然答案可能有多種情況，例如：[0, 4, 12] 也是可以的。

我們在下一節單獨講解最長遞增子序列

上面的代碼中，我們調用lis 函數求出數組source的最長遞增子序列爲[ 0, 1 ]。我們知道 source 數組的值爲 [2, 3, 1, -1]，很顯然最長遞增子序列應該是[ 2, 3 ]，但爲什麼計算出的結果是[ 0, 1 ]呢？其實[ 0, 1 ]代表的是最長遞增子序列中的各個元素在source數組中的位置索引，如下圖所示：

我們根據source，對新列表進行重新編號，並找出了最長遞增子序列。

我們從後向前進行遍歷source每一項。此時會出現三種情況：

當前的值爲-1，這說明該節點是全新的節點，又由於我們是從後向前遍歷，我們直接創建好 DOM 節點插入到隊尾就可以了。
當前的索引爲最長遞增子序列中的值，也就是i === seq[j]，這說說明該節點不需要移動
當前的索引不是最長遞增子序列中的值，那麼說明該 DOM 節點需要移動，這裏也很好理解，我們也是直接將 DOM 節點插入到隊尾就可以了，因爲隊尾是排好序的。

function vue3Diff(prevChildren, nextChildren, parent) {
  //...
  if (move) {
   // 需要移動
	const seq = lis(source); // [0, 1]
    let j = seq.length - 1;  // 最長子序列的指針
    // 從後向前遍歷
    for (let i = nextLeft - 1；i >= 0; i--) {
      let pos = nextStart + i, // 對應新列表的index
        nextNode = nextChildren[pos],	// 找到vnode
      	nextPos = pos + 1，    // 下一個節點的位置，用於移動DOM
        refNode = nextPos >= nextChildren.length ? null : nextChildren[nextPos].el, //DOM節點
        cur = source[i];  // 當前source的值，用來判斷節點是否需要移動

      if (cur === -1) {
        // 情況1，該節點是全新節點
      	mount(nextNode, parent, refNode)
      } else if (cur === seq[j]) {
        // 情況2，是遞增子序列，該節點不需要移動
        // 讓j指向下一個
        j--
      } else {
        // 情況3，不是遞增子序列，該節點需要移動
        parent.insetBefore(nextNode.el, refNode)
      }
    }

  } else {
  //不需要移動

  }
}

說完了需要移動的情況，再說說不需要移動的情況。如果不需要移動的話，我們只需要判斷是否有全新的節點給他添加進去就可以了。具體代碼如下：

function vue3Diff(prevChildren, nextChildren, parent) {
  //...
  if (move) {
	const seq = lis(source); // [0, 1]
    let j = seq.length - 1;  // 最長子序列的指針
    // 從後向前遍歷
    for (let i = nextLeft - 1；i >= 0; i--) {
      let pos = nextStart + i, // 對應新列表的index
        nextNode = nextChildren[pos],	// 找到vnode
      	nextPos = pos + 1，    // 下一個節點的位置，用於移動DOM
        refNode = nextPos >= nextChildren.length ? null : nextChildren[nextPos].el, //DOM節點
        cur = source[i];  // 當前source的值，用來判斷節點是否需要移動

      if (cur === -1) {
        // 情況1，該節點是全新節點
      	mount(nextNode, parent, refNode)
      } else if (cur === seq[j]) {
        // 情況2，是遞增子序列，該節點不需要移動
        // 讓j指向下一個
        j--
      } else {
        // 情況3，不是遞增子序列，該節點需要移動
        parent.insetBefore(nextNode.el, refNode)
      }
    }
  } else {
    //不需要移動
    for (let i = nextLeft - 1；i >= 0; i--) {
      let cur = source[i];  // 當前source的值，用來判斷節點是否需要移動

      if (cur === -1) {
       let pos = nextStart + i, // 對應新列表的index
          nextNode = nextChildren[pos],	// 找到vnode
          nextPos = pos + 1，    // 下一個節點的位置，用於移動DOM
          refNode = nextPos >= nextChildren.length ? null : nextChildren[nextPos].el, //DOM節點
      	mount(nextNode, parent, refNode)
      }
    }
  }
}

至此vue3.0的 diff 完成。

最長遞增子序列

leetcode 有原題，官方解析很清晰，看不懂我講的可以去看看官方解析。

我們以該數組爲例

;[10, 9, 2, 5, 3, 8, 7, 13]

我們可以使用動態規劃的思想考慮這個問題。動態規劃的思想是將一個大的問題分解成多個小的子問題，並嘗試得到這些子問題的最優解，子問題的最優解有可能會在更大的問題中被利用，這樣通過小問題的最優解最終求得大問題的最優解。

我們先假設只有一個值的數組[13]，那麼該數組的最長遞增子序列就是[13]自己本身，其長度爲1。那麼我們認爲每一項的遞增序列的長度值均爲 1

那麼我們這次給數組增加一個值[7, 13], 由於7 < 13，所以該數組的最長遞增子序列是[7, 13]，那麼該長度爲2。那麼我們是否可以認爲，當[7]小於[13]時，以[7]爲頭的遞增序列的長度是，[7]的長度和[13]的長度的和，即1 + 1 = 2。

ok，我們基於這種思想來給計算一下該數組。我們先將每個值的初始賦值爲1

首先 7 < 13 那麼7對應的長度就是13的長度再加 1，1 + 1 = 2

繼續，我們對比8。我們首先和7比，發現不滿足遞增，但是沒關係我們還可以繼續和13比，8 < 13滿足遞增，那麼8的長度也是13的長度在加一，長度爲2

我們再對比3，我們先讓其與8進行對比，3 < 8，那麼3的長度是8的長度加一，此時3的長度爲3。但是還沒結束，我們還需要讓3與7對比。同樣3 < 7，此時我們需要在計算出一個長度是7的長度加一同樣是3，我們對比兩個長度，如果原本的長度沒有本次計算出的長度值大的話，我們進行替換，反之則我們保留原本的值。由於3 === 3，我們選擇不替換。最後，我們讓3與13進行對比，同樣的3 < 13，此時計算出的長度爲2，比原本的長度3要小，我們選擇保留原本的值。

之後的計算依次類推，最後的結果是這樣的

我們從中取最大的值4，該值代表的最長遞增子序列的個數。代碼如下：

function lis(arr) {
  let len = arr.length,
    dp = new Array(len).fill(1) // 用於保存長度
  for (let i = len - 1; i >= 0; i--) {
    let cur = arr[i]
    for (let j = i + 1; j < len; j++) {
      let next = arr[j]
      // 如果是遞增 取更大的長度值
      if (cur < next) dp[i] = Math.max(dp[j] + 1, dp[i])
    }
  }
  return Math.max(...dp)
}

至此爲止，我們講完了基礎的最長遞增子序列。然而在vue3.0中，我們需要的是最長遞增子序列在原本數組中的索引。所以我們還需要在創建一個數組用於保存每個值的最長子序列所對應在數組中的index。具體代碼如下：

function lis(arr) {
  let len = arr.length,
    res = [],
    dp = new Array(len).fill(1)
  // 存默認index
  for (let i = 0; i < len; i++) {
    res.push([i])
  }
  for (let i = len - 1; i >= 0; i--) {
    let cur = arr[i],
      nextIndex = undefined
    // 如果爲-1 直接跳過，因爲-1代表的是新節點，不需要進行排序
    if (cur === -1) continue
    for (let j = i + 1; j < len; j++) {
      let next = arr[j]
      // 滿足遞增條件
      if (cur < next) {
        let max = dp[j] + 1
        // 當前長度是否比原本的長度要大
        if (max > dp[i]) {
          dp[i] = max
          nextIndex = j
        }
      }
    }
    // 記錄滿足條件的值，對應在數組中的index
    if (nextIndex !== undefined) res[i].push(...res[nextIndex])
  }
  let index = dp.reduce((prev, cur, i, arr) => (cur > arr[prev] ? i : prev), dp.length - 1)
  // 返回最長的遞增子序列的index
  return result[index]
}

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/1K0rw0ypDzdEetTDofOIIg

二、Vue2.X Diff —— 雙端比較

三、 Vue3 Diff —— 最長遞增子序列

猜你喜歡