Vue3組件更新中的DOM?diff算法示例詳解

更新時間：2022年04月11日 16:13:13 作者：風度前端

虛擬dom是當前前端最流行的兩個框架（vue和react）都用到的一種技術(shù),都說他能幫助vue和react提升渲染性能,提升用戶體驗,下面這篇文章主要給大家介紹了關(guān)于Vue3組件更新中的DOM?diff算法的相關(guān)資料,需要的朋友可以參考下

在vue的組件更新過程中，新子節(jié)點數(shù)組相對于舊子節(jié)點數(shù)組的變化，無非是通過更新、刪除、添加和移動節(jié)點來完成，而核心 diff 算法，就是在已知舊子節(jié)點的 DOM 結(jié)構(gòu)、vnode 和新子節(jié)點的 vnode 情況下，以較低的成本完成子節(jié)點的更新為目的，求解生成新子節(jié)點 DOM 的系列操作。

舉例來說，假說我們有一個如下的列表

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="c">c</li>
  <li key="d">d</li>
</ul>

然后我們在中間插入一行，得到一個新列表：

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="d">e</li>
  <li key="c">c</li>
  <li key="d">d</li>
</ul>

在插入操作的前后，它們對應(yīng)渲染生成的 vnode 可以用一張圖表示：

從圖中我們可以直觀地感受到，差異主要在新子節(jié)點中的 b 節(jié)點后面多了一個 e 節(jié)點。

我們再把這個例子稍微修改一下，多添加一個 e 節(jié)點：

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="c">c</li>
  <li key="d">d</li>
  <li key="e">e</li>
</ul>

然后我們刪除中間一項，得到一個新列表：

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="d">d</li>
  <li key="e">e</li>
</ul>

在刪除操作的前后，它們對應(yīng)渲染生成的 vnode 可以用一張圖表示：

我們可以看到，這時差異主要在新子節(jié)點中的 b 節(jié)點后面少了一個 c 節(jié)點。

綜合這兩個例子，我們很容易發(fā)現(xiàn)新舊 children 擁有相同的頭尾節(jié)點。對于相同的節(jié)點，我們只需要做對比更新即可，所以 diff 算法的第一步從頭部開始同步。

同步頭部節(jié)點

我們先來看一下頭部節(jié)點同步的實現(xiàn)代碼：

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開始同步
  // i = 0, e1 = 3, e2 = 4
  // (a b) c d
  // (a b) e c d
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = c2[i]
    if (isSameVNodeType(n1, n2)) {
      // 相同的節(jié)點，遞歸執(zhí)行 patch 更新節(jié)點
      patch(n1, n2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized)
    }
    else {
      break
    }
    i++
  }
}

在整個 diff 的過程，我們需要維護幾個變量：頭部的索引 i、舊子節(jié)點的尾部索引 e1和新子節(jié)點的尾部索引 e2。

同步頭部節(jié)點就是從頭部開始，依次對比新節(jié)點和舊節(jié)點，如果它們相同的則執(zhí)行 patch 更新節(jié)點；如果不同或者索引 i 大于索引 e1 或者 e2，則同步過程結(jié)束。

我們拿第一個例子來說，通過下圖看一下同步頭部節(jié)點后的結(jié)果：

可以看到，完成頭部節(jié)點同步后：i 是 2，e1 是 3，e2 是 4。

同步尾部節(jié)點

接著從尾部開始同步尾部節(jié)點，實現(xiàn)代碼如下：

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開始同步
  // i = 0, e1 = 3, e2 = 4
  // (a b) c d
  // (a b) e c d
  // 2. 從尾部開始同步
  // i = 2, e1 = 3, e2 = 4
  // (a b) (c d)
  // (a b) e (c d)
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = c2[e2]
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized)
    }
    else {
      break
    }
    e1--
    e2--
  }
}

同步尾部節(jié)點就是從尾部開始，依次對比新節(jié)點和舊節(jié)點，如果相同的則執(zhí)行 patch 更新節(jié)點；如果不同或者索引 i 大于索引 e1 或者 e2，則同步過程結(jié)束。

我們來通過下圖看一下同步尾部節(jié)點后的結(jié)果：

可以看到，完成尾部節(jié)點同步后：i 是 2，e1 是 1，e2 是 2。

接下來只有 3 種情況要處理：

新子節(jié)點有剩余要添加的新節(jié)點；
舊子節(jié)點有剩余要刪除的多余節(jié)點；
未知子序列

我們繼續(xù)看一下具體是怎樣操作的。

添加新的節(jié)點

首先要判斷新子節(jié)點是否有剩余的情況，如果滿足則添加新子節(jié)點，實現(xiàn)代碼如下：

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開始同步
  // i = 0, e1 = 3, e2 = 4
  // (a b) c d
  // (a b) e c d
  // ...
  // 2. 從尾部開始同步
  // i = 2, e1 = 3, e2 = 4
  // (a b) (c d)
  // (a b) e (c d)
  // 3. 掛載剩余的新節(jié)點
  // i = 2, e1 = 1, e2 = 2
  if (i > e1) {
    if (i <= e2) {
      const nextPos = e2 + 1
      const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor
      while (i <= e2) {
        // 掛載新節(jié)點
        patch(null, c2[i], container, anchor, parentComponent, parentSuspense, isSVG)
        i++
      }
    }
  }
}

如果索引 i 大于尾部索引 e1 且 i 小于 e2，那么從索引 i 開始到索引 e2 之間，我們直接掛載新子樹這部分的節(jié)點。

對我們的例子而言，同步完尾部節(jié)點后 i 是 2，e1 是 1，e2 是 2，此時滿足條件需要添加新的節(jié)點，我們來通過下圖看一下添加后的結(jié)果：

添加完 e 節(jié)點后，舊子節(jié)點的 DOM 和新子節(jié)點對應(yīng)的 vnode 映射一致，也就完成了更新。

刪除多余節(jié)點

如果不滿足添加新節(jié)點的情況，我就要接著判斷舊子節(jié)點是否有剩余，如果滿足則刪除舊子節(jié)點，實現(xiàn)代碼如下：

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開始同步
  // i = 0, e1 = 4, e2 = 3
  // (a b) c d e
  // (a b) d e
  // ...
  // 2. 從尾部開始同步
  // i = 2, e1 = 4, e2 = 3
  // (a b) c (d e)
  // (a b) (d e)
  // 3. 普通序列掛載剩余的新節(jié)點
  // i = 2, e1 = 2, e2 = 1
  // 不滿足
  if (i > e1) {
  }
  // 4. 普通序列刪除多余的舊節(jié)點
  // i = 2, e1 = 2, e2 = 1
  else if (i > e2) {
    while (i <= e1) {
      // 刪除節(jié)點
      unmount(c1[i], parentComponent, parentSuspense, true)
      i++
    }
  }
}

如果索引 i 大于尾部索引 e2，那么從索引 i 開始到索引 e1 之間，我們直接刪除舊子樹這部分的節(jié)點。

第二個例子是就刪除節(jié)點的情況，我們從同步頭部節(jié)點開始，用圖的方式演示這一過程。

首先從頭部同步節(jié)點：

此時的結(jié)果：i 是 2，e1 是 4，e2 是 3。

接著從尾部同步節(jié)點：

此時的結(jié)果：i 是 2，e1 是 2，e2 是 1，滿足刪除條件，因此刪除子節(jié)點中的多余節(jié)點：

刪除完 c 節(jié)點后，舊子節(jié)點的 DOM 和新子節(jié)點對應(yīng)的 vnode 映射一致，也就完成了更新。

處理未知子序列

單純的添加和刪除節(jié)點都是比較理想的情況，操作起來也很容易，但是有些時候并非這么幸運，我們會遇到比較復(fù)雜的未知子序列，這時候 diff 算法會怎么做呢？

我們再通過例子來演示存在未知子序列的情況，假設(shè)一個按照字母表排列的列表：

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="c">c</li>
  <li key="d">d</li>
  <li key="e">e</li>
  <li key="f">f</li>
  <li key="g">g</li>
  <li key="h">h</li>
</ul>

然后我們打亂之前的順序得到一個新列表：

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="e">e</li>
  <li key="d">c</li>
  <li key="c">d</li>
  <li key="i">i</li>
  <li key="g">g</li>
  <li key="h">h</li>
</ul>

在操作前，它們對應(yīng)渲染生成的 vnode 可以用一張圖表示：

我們還是從同步頭部節(jié)點開始，用圖的方式演示這一過程。

首先從頭部同步節(jié)點：

同步頭部節(jié)點后的結(jié)果：i 是 2，e1 是 7，e2 是 7。

接著從尾部同步節(jié)點：

同步尾部節(jié)點后的結(jié)果：i 是 2，e1 是 5，e2 是 5?？梢钥吹剿炔粷M足添加新節(jié)點的條件，也不滿足刪除舊節(jié)點的條件。那么對于這種情況，我們應(yīng)該怎么處理呢？

結(jié)合上圖可以知道，要把舊子節(jié)點的 c、d、e、f 轉(zhuǎn)變成新子節(jié)點的 e、c、d、i。從直觀上看，我們把 e 節(jié)點移動到 c 節(jié)點前面，刪除 f 節(jié)點，然后在 d 節(jié)點后面添加 i 節(jié)點即可。

其實無論多復(fù)雜的情況，最終無非都是通過更新、刪除、添加、移動這些動作來操作節(jié)點，而我們要做的就是找到相對優(yōu)的解。

當兩個節(jié)點類型相同時，我們執(zhí)行更新操作；當新子節(jié)點中沒有舊子節(jié)點中的某些節(jié)點時，我們執(zhí)行刪除操作；當新子節(jié)點中多了舊子節(jié)點中沒有的節(jié)點時，我們執(zhí)行添加操作，這些操作我們在前面已經(jīng)闡述清楚了。相對來說這些操作中最麻煩的就是移動，我們既要判斷哪些節(jié)點需要移動也要清楚如何移動。

移動子節(jié)點

那么什么時候需要移動呢，就是當子節(jié)點排列順序發(fā)生變化的時候，舉個簡單的例子具體看一下：

var prev = [1, 2, 3, 4, 5, 6]
var next = [1, 3, 2, 6, 4, 5]

可以看到，從 prev 變成 next，數(shù)組里的一些元素的順序發(fā)生了變化，我們可以把子節(jié)點類比為元素，現(xiàn)在問題就簡化為我們?nèi)绾斡米钌俚囊苿邮乖仨樞驈?prev 變化為 next 。

一種思路是在 next 中找到一個遞增子序列，比如 [1, 3, 6] 、[1, 2, 4, 5]。之后對 next 數(shù)組進行倒序遍歷，移動所有不在遞增序列中的元素即可。

如果選擇了 [1, 3, 6] 作為遞增子序列，那么在倒序遍歷的過程中，遇到 6、3、1 不動，遇到 5、4、2 移動即可，如下圖所示：

如果選擇了 [1, 2, 4, 5] 作為遞增子序列，那么在倒序遍歷的過程中，遇到 5、4、2、1 不動，遇到 6、3 移動即可，如下圖所示：

可以看到第一種移動了三次，而第二種只移動了兩次，遞增子序列越長，所需要移動元素的次數(shù)越少，所以如何移動的問題就回到了求解最長遞增子序列的問題。我們稍后會詳細講求解最長遞增子序列的算法，所以先回到我們這里的問題，對未知子序列的處理。

我們現(xiàn)在要做的是在新舊子節(jié)點序列中找出相同節(jié)點并更新，找出多余的節(jié)點刪除，找出新的節(jié)點添加，找出是否有需要移動的節(jié)點，如果有該如何移動。

在查找過程中需要對比新舊子序列，那么我們就要遍歷某個序列，如果在遍歷舊子序列的過程中需要判斷某個節(jié)點是否在新子序列中存在，這就需要雙重循環(huán)，而雙重循環(huán)的復(fù)雜度是 O(n2) ，為了優(yōu)化這個復(fù)雜度，我們可以用一種空間換時間的思路，建立索引圖，把時間復(fù)雜度降低到 O(n)。

建立索引圖

所以處理未知子序列的第一步，就是建立索引圖。

通常我們在開發(fā)過程中，會給 v-for 生成的列表中的每一項分配唯一 key 作為項的唯一 ID，這個 key 在 diff 過程中起到很關(guān)鍵的作用。對于新舊子序列中的節(jié)點，我們認為 key 相同的就是同一個節(jié)點，直接執(zhí)行 patch 更新即可。

我們根據(jù) key 建立新子序列的索引圖，實現(xiàn)如下：

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開始同步
  // i = 0, e1 = 7, e2 = 7
  // (a b) c d e f g h
  // (a b) e c d i g h
  // 2. 從尾部開始同步
  // i = 2, e1 = 7, e2 = 7
  // (a b) c d e f (g h)
  // (a b) e c d i (g h)
  // 3. 普通序列掛載剩余的新節(jié)點， 不滿足
  // 4. 普通序列刪除多余的舊節(jié)點，不滿足
  // i = 2, e1 = 4, e2 = 5
  // 舊子序列開始索引，從 i 開始記錄
  const s1 = i
  // 新子序列開始索引，從 i 開始記錄
  const s2 = i //
  // 5.1 根據(jù) key 建立新子序列的索引圖
  const keyToNewIndexMap = new Map()
  for (i = s2; i <= e2; i++) {
    const nextChild = c2[i]
    keyToNewIndexMap.set(nextChild.key, i)
  }
}

新舊子序列是從 i 開始的，所以我們先用 s1、s2 分別作為新舊子序列的開始索引，接著建立一個 keyToNewIndexMap 的 Map<key, index> 結(jié)構(gòu)，遍歷新子序列，把節(jié)點的 key 和 index 添加到這個 Map 中，注意我們這里假設(shè)所有節(jié)點都是有 key 標識的。

keyToNewIndexMap 存儲的就是新子序列中每個節(jié)點在新子序列中的索引，我們來看一下示例處理后的結(jié)果，如下圖所示：

我們得到了一個值為 {e:2,c:3,d:4,i:5} 的新子序列索引圖。

更新和移除舊節(jié)點

接下來，我們就需要遍歷舊子序列，有相同的節(jié)點就通過 patch 更新，并且移除那些不在新子序列中的節(jié)點，同時找出是否有需要移動的節(jié)點，我們來看一下這部分邏輯的實現(xiàn)：

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開始同步
  // i = 0, e1 = 7, e2 = 7
  // (a b) c d e f g h
  // (a b) e c d i g h
  // 2. 從尾部開始同步
  // i = 2, e1 = 7, e2 = 7
  // (a b) c d e f (g h)
  // (a b) e c d i (g h)
  // 3. 普通序列掛載剩余的新節(jié)點，不滿足
  // 4. 普通序列刪除多余的舊節(jié)點，不滿足
  // i = 2, e1 = 4, e2 = 5
  // 舊子序列開始索引，從 i 開始記錄
  const s1 = i
  // 新子序列開始索引，從 i 開始記錄
  const s2 = i
  // 5.1 根據(jù) key 建立新子序列的索引圖
  // 5.2 正序遍歷舊子序列，找到匹配的節(jié)點更新，刪除不在新子序列中的節(jié)點，判斷是否有移動節(jié)點
  // 新子序列已更新節(jié)點的數(shù)量
  let patched = 0
  // 新子序列待更新節(jié)點的數(shù)量，等于新子序列的長度
  const toBePatched = e2 - s2 + 1
  // 是否存在要移動的節(jié)點
  let moved = false
  // 用于跟蹤判斷是否有節(jié)點移動
  let maxNewIndexSoFar = 0
  // 這個數(shù)組存儲新子序列中的元素在舊子序列節(jié)點的索引，用于確定最長遞增子序列
  const newIndexToOldIndexMap = new Array(toBePatched)
  // 初始化數(shù)組，每個元素的值都是 0
  // 0 是一個特殊的值，如果遍歷完了仍有元素的值為 0，則說明這個新節(jié)點沒有對應(yīng)的舊節(jié)點
  for (i = 0; i < toBePatched; i++)
    newIndexToOldIndexMap[i] = 0
  // 正序遍歷舊子序列
  for (i = s1; i <= e1; i++) {
    // 拿到每一個舊子序列節(jié)點
    const prevChild = c1[i]
    if (patched >= toBePatched) {
      // 所有新的子序列節(jié)點都已經(jīng)更新，剩余的節(jié)點刪除
      unmount(prevChild, parentComponent, parentSuspense, true)
      continue
    }
    // 查找舊子序列中的節(jié)點在新子序列中的索引
    let newIndex = keyToNewIndexMap.get(prevChild.key)
    if (newIndex === undefined) {
      // 找不到說明舊子序列已經(jīng)不存在于新子序列中，則刪除該節(jié)點
      unmount(prevChild, parentComponent, parentSuspense, true)
    }
    else {
      // 更新新子序列中的元素在舊子序列中的索引，這里加 1 偏移，是為了避免 i 為 0 的特殊情況，影響對后續(xù)最長遞增子序列的求解
      newIndexToOldIndexMap[newIndex - s2] = i + 1
      // maxNewIndexSoFar 始終存儲的是上次求值的 newIndex，如果不是一直遞增，則說明有移動
      if (newIndex >= maxNewIndexSoFar) {
        maxNewIndexSoFar = newIndex
      }
      else {
        moved = true
      }
      // 更新新舊子序列中匹配的節(jié)點
      patch(prevChild, c2[newIndex], container, null, parentComponent, parentSuspense, isSVG, optimized)
      patched++
    }
  }
}

我們建立了一個 newIndexToOldIndexMap 的數(shù)組，來存儲新子序列節(jié)點的索引和舊子序列節(jié)點的索引之間的映射關(guān)系，用于確定最長遞增子序列，這個數(shù)組的長度為新子序列的長度，每個元素的初始值設(shè)為 0，它是一個特殊的值，如果遍歷完了仍有元素的值為 0，則說明遍歷舊子序列的過程中沒有處理過這個節(jié)點，這個節(jié)點是新添加的。

下面我們說說具體的操作過程：正序遍歷舊子序列，根據(jù)前面建立的 keyToNewIndexMap 查找舊子序列中的節(jié)點在新子序列中的索引，如果找不到就說明新子序列中沒有該節(jié)點，就刪除它；如果找得到則將它在舊子序列中的索引更新到 newIndexToOldIndexMap 中。

注意這里索引加了長度為 1 的偏移，是為了應(yīng)對 i 為 0 的特殊情況，如果不這樣處理就會影響后續(xù)求解最長遞增子序列。

遍歷過程中，我們用變量 maxNewIndexSoFar 跟蹤判斷節(jié)點是否移動，maxNewIndexSoFar 始終存儲的是上次求值的 newIndex，一旦本次求值的 newIndex 小于 maxNewIndexSoFar，這說明順序遍歷舊子序列的節(jié)點在新子序列中的索引并不是一直遞增的，也就說明存在移動的情況。

除此之外，這個過程中我們也會更新新舊子序列中匹配的節(jié)點，另外如果所有新的子序列節(jié)點都已經(jīng)更新，而對舊子序列遍歷還未結(jié)束，說明剩余的節(jié)點就是多余的，刪除即可。

至此，我們完成了新舊子序列節(jié)點的更新、多余舊節(jié)點的刪除，并且建立了一個 newIndexToOldIndexMap 存儲新子序列節(jié)點的索引和舊子序列節(jié)點的索引之間的映射關(guān)系，并確定是否有移動。

我們來看一下示例處理后的結(jié)果，如下圖所示：

可以看到， c、d、e 節(jié)點被更新，f 節(jié)點被刪除，newIndexToOldIndexMap 的值為 [5, 3, 4 ,0]，此時 moved 也為 true，也就是存在節(jié)點移動的情況。

移動和掛載新節(jié)點

接下來，就到了處理未知子序列的最后一個流程，移動和掛載新節(jié)點，我們來看一下這部分邏輯的實現(xiàn)：

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開始同步
  // i = 0, e1 = 6, e2 = 7
  // (a b) c d e f g
  // (a b) e c d h f g
  // 2. 從尾部開始同步
  // i = 2, e1 = 6, e2 = 7
  // (a b) c (d e)
  // (a b) (d e)
  // 3. 普通序列掛載剩余的新節(jié)點， 不滿足
  // 4. 普通序列刪除多余的節(jié)點，不滿足
  // i = 2, e1 = 4, e2 = 5
  // 舊子節(jié)點開始索引，從 i 開始記錄
  const s1 = i
  // 新子節(jié)點開始索引，從 i 開始記錄
  const s2 = i //
  // 5.1 根據(jù) key 建立新子序列的索引圖
  // 5.2 正序遍歷舊子序列，找到匹配的節(jié)點更新，刪除不在新子序列中的節(jié)點，判斷是否有移動節(jié)點
  // 5.3 移動和掛載新節(jié)點
  // 僅當節(jié)點移動時生成最長遞增子序列
  const increasingNewIndexSequence = moved
    ? getSequence(newIndexToOldIndexMap)
    : EMPTY_ARR
  let j = increasingNewIndexSequence.length - 1
  // 倒序遍歷以便我們可以使用最后更新的節(jié)點作為錨點
  for (i = toBePatched - 1; i >= 0; i--) {
    const nextIndex = s2 + i
    const nextChild = c2[nextIndex]
    // 錨點指向上一個更新的節(jié)點，如果 nextIndex 超過新子節(jié)點的長度，則指向 parentAnchor
    const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor
    if (newIndexToOldIndexMap[i] === 0) {
      // 掛載新的子節(jié)點
     patch(null, nextChild, container, anchor, parentComponent, parentSuspense, isSVG)
    }
    else if (moved) {
      // 沒有最長遞增子序列（reverse 的場景）或者當前的節(jié)點索引不在最長遞增子序列中，需要移動
      if (j < 0 || i !== increasingNewIndexSequence[j]) {
        move(nextChild, container, anchor, 2)
      }
      else {
        // 倒序遞增子序列
        j--
      }
    }
  }
}

我們前面已經(jīng)判斷了是否移動，如果 moved 為 true 就通過 getSequence(newIndexToOldIndexMap) 計算最長遞增子序列。

接著我們采用倒序的方式遍歷新子序列，因為倒序遍歷可以方便我們使用最后更新的節(jié)點作為錨點。在倒序的過程中，錨點指向上一個更新的節(jié)點，然后判斷 newIndexToOldIndexMap[i] 是否為 0，如果是則表示這是新節(jié)點，就需要掛載它；接著判斷是否存在節(jié)點移動的情況，如果存在的話則看節(jié)點的索引是不是在最長遞增子序列中，如果在則倒序最長遞增子序列，否則把它移動到錨點的前面。

為了便于你更直觀地理解，我們用前面的例子展示一下這個過程，此時 toBePatched 的值為 4，j 的值為 1，最長遞增子序列 increasingNewIndexSequence 的值是 [1, 2]。在倒序新子序列的過程中，首先遇到節(jié)點 i，發(fā)現(xiàn)它在 newIndexToOldIndexMap 中的值是 0，則說明它是新節(jié)點，我們需要掛載它；然后繼續(xù)遍歷遇到節(jié)點 d，因為 moved 為 true，且 d 的索引存在于最長遞增子序列中，則執(zhí)行 j-- 倒序最長遞增子序列，j 此時為 0；接著繼續(xù)遍歷遇到節(jié)點 c，它和 d 一樣，索引也存在于最長遞增子序列中，則執(zhí)行 j--，j 此時為 -1；接著繼續(xù)遍歷遇到節(jié)點 e，此時 j 是 -1 并且 e 的索引也不在最長遞增子序列中，所以做一次移動操作，把 e 節(jié)點移到上一個更新的節(jié)點，也就是 c 節(jié)點的前面。

新子序列倒序完成，即完成了新節(jié)點的插入和舊節(jié)點的移動操作，也就完成了整個核心 diff 算法對節(jié)點的更新。

我們來看一下示例處理后的結(jié)果，如下圖所示：

可以看到新子序列中的新節(jié)點 i 被掛載，舊子序列中的節(jié)點 e 移動到了 c 節(jié)點前面，至此，我們就在已知舊子節(jié)點 DOM 結(jié)構(gòu)和 vnode、新子節(jié)點 vnode 的情況下，求解出生成新子節(jié)點的 DOM 的更新、移動、刪除、新增等系列操作，并且以一種較小成本的方式完成 DOM 更新。

我們知道了子節(jié)點更新調(diào)用的是 patch 方法， Vue.js 正是通過這種遞歸的方式完成了整個組件樹的更新。

核心 diff 算法中最復(fù)雜就是求解最長遞增子序列，下面我們再來詳細學習一下這個算法。

最長遞增子序列

求解最長遞增子序列是一道經(jīng)典的算法題，多數(shù)解法是使用動態(tài)規(guī)劃的思想，算法的時間復(fù)雜度是 O(n2)，而 Vue.js 內(nèi)部使用的是維基百科提供的一套“貪心 + 二分查找”的算法，貪心算法的時間復(fù)雜度是 O(n)，二分查找的時間復(fù)雜度是 O(logn)，所以它的總時間復(fù)雜度是 O(nlogn)。

單純地看代碼并不好理解，我們用示例來看一下這個子序列的求解過程。

假設(shè)我們有這個樣一個數(shù)組 arr：[2, 1, 5, 3, 6, 4, 8, 9, 7]，求解它最長遞增子序列的步驟如下：

最終求得最長遞增子序列的值就是 [1, 3, 4, 8, 9]。

通過演示我們可以得到這個算法的主要思路：對數(shù)組遍歷，依次求解長度為 i 時的最長遞增子序列，當 i 元素大于 i - 1 的元素時，添加 i 元素并更新最長子序列；否則往前查找直到找到一個比 i 小的元素，然后插在該元素后面并更新對應(yīng)的最長遞增子序列。

這種做法的主要目的是讓遞增序列的差盡可能的小，從而可以獲得更長的遞增子序列，這便是一種貪心算法的思想。

了解了算法的大致思想后，接下來我們看一下源碼實現(xiàn)：

function getSequence (arr) {
  const p = arr.slice()
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        // 存儲在 result 更新前的最后一個索引的值
        p[i] = j
        result.push(i)
        continue
      }
      u = 0
      v = result.length - 1
      // 二分搜索，查找比 arrI 小的節(jié)點，更新 result 的值
      while (u < v) {
        c = ((u + v) / 2) | 0
        if (arr[result[c]] < arrI) {
          u = c + 1
        }
        else {
          v = c
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]
        }
        result[u] = i
      }
    }
  }
  u = result.length
  v = result[u - 1]

  // 回溯數(shù)組 p，找到最終的索引
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

其中 result 存儲的是長度為 i 的遞增子序列最小末尾值的索引。比如我們上述例子的第九步，在對數(shù)組 p 回溯之前， result 值就是 [1, 3, 4, 7, 9] ，這不是最長遞增子序列，它只是存儲的對應(yīng)長度遞增子序列的最小末尾。因此在整個遍歷過程中會額外用一個數(shù)組 p，來存儲在每次更新 result 前最后一個索引的值，并且它的 key 是這次要更新的 result 值：

j = result[result.length - 1]
p[i] = j
result.push(i)

從 result 最后一個元素 9 對應(yīng)的索引 7 開始回溯，可以看到 p[7] = 6，p[6] = 5，p[5] = 3，p[3] = 1，所以通過對 p 的回溯，得到最終的 result 值是 [1, 3 ,5 ,6 ,7]，也就找到最長遞增子序列的最終索引了。這里要注意，我們求解的是最長子序列索引值，它的每個元素其實對應(yīng)的是數(shù)組的下標。對于我們的例子而言，[2, 1, 5, 3, 6, 4, 8, 9, 7] 的最長子序列是 [1, 3, 4, 8, 9]，而我們求解的 [1, 3 ,5 ,6 ,7] 就是最長子序列中元素在原數(shù)組中的下標所構(gòu)成的新數(shù)組。

總結(jié)

本文分析了組件更新流程中的diff算法，對于普通元素節(jié)點的更新，主要是更新一些屬性，以及它的子節(jié)點。子節(jié)點的更新又分為多種情況，其中最復(fù)雜的情況為數(shù)組到數(shù)組的更新，內(nèi)部又根據(jù)不同情況分成幾個流程去 diff，遇到需要移動的情況還要去求解子節(jié)點的最長遞增子序列。

整個更新過程還是利用了樹的深度遍歷，遞歸執(zhí)行 patch 方法，最終完成了整個組件樹的更新。

下面，我們通過一張圖來更加直觀感受組件的更新流程：