深入解析Vue3中的 diff 演演算法(圖文詳解)

2022-01-19 22:00:07
本篇文章帶大家通過圖文來深入解析下Vue3中的 diff 演演算法,希望對大家有所幫助!

本篇文章主要分析Vue3 diff演演算法,通過本文你可以知道:

  • diff的主要過程,核心邏輯

  • diff是如何進行節點複用、移動、解除安裝

  • 並有一個範例題,可以結合本文進行練習分析

如果你還不是特別瞭解Vnode、渲染器的patch流程,建議先閱讀下面兩篇文章:

  • Vnode(https://mp.weixin.qq.com/s/DtFJpA91UPJIevlqaPzcnQ)

  • 渲染器分析(https://mp.weixin.qq.com/s/hzpNGWFCLMC2vJNSmP2vsQ)

1.0 diffkey子節點

在處理被標記為UNKEYED_FRAGMENT時。

  • 首先會通過新舊自序列獲取最小共同長度commonLength

  • 對公共部分迴圈遍歷patch

  • patch 結束,再處理剩餘的新舊節點。

  • 如果oldLength > newLength,說明需要對舊節點進行unmount

  • 否則,說明有新增節點,需要進行mount;

1.png

這裡貼下省略後的程式碼。

const patchUnkeyedChildren = (c1, c2,...res) => {
    c1 = c1 || EMPTY_ARR
    c2 = c2 || EMPTY_ARR
    // 獲取新舊子節點的長度
    const oldLength = c1.length
    const newLength = c2.length
    // 1. 取得公共長度。最小長度
    const commonLength = Math.min(oldLength, newLength)
    let i
    // 2. patch公共部分
    for (i = 0; i < commonLength; i++) { 
      patch(...)
    }
    // 3. 解除安裝舊節點
    if (oldLength > newLength) {
      // remove old
      unmountChildren(...)
    } else {
      // mount new
      // 4. 否則掛載新的子節點
      mountChildren(...)
    }
  }

從上面的程式碼可以看出,在處理無key子節點的時候,邏輯還是非常簡單粗暴的。準確的說處理無key子節點的效率並不高。

因為不管是直接對公共部分patch,還是直接對新增節點進行mountChildren(其實是遍歷子節點,進行patch操作),其實都是在遞迴進行patch,這就會影響到效能。

2.0 diffkey子節點序列

diffkey子序列的時候,會進行細分處理。主要會經過以下一種情況的判斷:

  • 起始位置節點型別相同。
  • 結束位置節點型別相同。
  • 相同部分處理完,有新增節點。
  • 相同部分處理完,有舊節點需要解除安裝。
  • 首尾相同,但中間部分存在可複用亂序節點。

在開始階段,會先生面三個指正,分別是:

  • i = 0,指向新舊序列的開始位置
  • e1 = oldLength - 1,指向舊序列的結束位置
  • e2 = newLength - 1,指向新序列的結束位置

2.png

let i = 0
const l2 = c2.length
let e1 = c1.length - 1 // prev ending index
let e2 = l2 - 1 // next ending index

下面開始分情況進行diff處理。

2.1 起始位置節點型別相同

3.png

  • 對於起始位置型別相同的節點,從左向右進行diff遍歷。

  • 如果新舊節點型別相同,則進行patch處理

  • 節點型別不同,則break,跳出遍歷diff

//  i <= 2 && i <= 3
while (i <= e1 && i <= e2) {
  const n1 = c1[i]
  const n2 = c2[i]
  if (isSameVNodeType(n1, n2)) {
    // 如果是相同的節點型別,則進行遞迴patch
    patch(...)
  } else {
    // 否則退出
    break
  }
  i++
}

上面上略了部分程式碼,但不影響主要邏輯。

從程式碼可以知道,遍歷時,利用前面在函數全域性上下文中宣告的三個指標,進行遍歷判斷。

保證能充分遍歷到開始位置相同的位置,i <= e1 && i <= e2

一旦遇到型別不同的節點,就會跳出diff遍歷。

2.2 結束位置節點型別相同

4.png

開始位置相同diff 結束,會緊接著從序列尾部開始遍歷 diff

此時需要對尾指標e1、e2進行遞減。

//  i <= 2 && i <= 3
// 結束後: e1 = 0 e2 =  1
while (i <= e1 && i <= e2) {
  const n1 = c1[e1]
  const n2 = c2[e2]
  if (isSameVNodeType(n1, n2)) {
    // 相同的節點型別
    patch(...)
  } else {
    // 否則退出
    break
  }
  e1--
  e2--
}

從程式碼可以看出,diff邏輯與第一種基本一樣,相同型別進行patch處理。

不同型別break,跳出迴圈遍歷。

並且對尾指標進行遞減操作。

2.3 相同部分遍歷結束,新序列中有新增節點,進行掛載

經過上面兩種情況的處理,已經patch完首尾相同部分的節點,接下來是對新序列中的新增節點進行patch處理。

5.png

在經過上面兩種請款處理之後,如果有新增節點,可能會出現 i > e1 && i <= e2的情況。

這種情況下意味著新的子節點序列中有新增節點。

這時會對新增節點進行patch

// 3. common sequence + mount
// (a b)
// (a b) c
// i = 2, e1 = 1, e2 = 2
// (a b)
// c (a b)
// i = 0, e1 = -1, e2 = 0
if (i > e1) {
  if (i <= e2) {
    const nextPos = e2 + 1
    // nextPos < l2,說明有已經patch過尾部節點,
    // 否則會獲取父節點作為錨點
    const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor
    while (i <= e2) {
      patch(null, c2[i], anchor, ...others)
      i++
    }
  }
}

從上面的程式碼可以知道,patch的時候沒有傳第一個引數,最終會走mount的邏輯。

可以看這篇 主要分析patch的過程

https://mp.weixin.qq.com/s/hzpNGWFCLMC2vJNSmP2vsQ

patch的過程中,會遞增i指標。

並通過nextPos來獲取錨點。

如果nextPos < l2,則以已經patch的節點作為錨點,否則以父節點作為錨點。

2.4 相同部分遍歷結束,新序列中少節點,進行解除安裝

6.png

如果處理完收尾相同的節點,出現i > e2 && i <= e1的情況,則意味著有舊節點需要進行解除安裝操作。

// 4. common sequence + unmount
// (a b) c
// (a b)
// i = 2, e1 = 2, e2 = 1
// a (b c)
// (b c)
// i = 0, e1 = 0, e2 = -1
// 公共序列 解除安裝舊的
else if (i > e2) {
  while (i <= e1) {
    unmount(c1[i], parentComponent, parentSuspense, true)
    i++
  }
}

通過程式碼可以知道,這種情況下,會遞增i指標,對舊節點進行解除安裝。

2.5 亂序情況

這種情況下較為複雜,但diff的核心邏輯在於通過新舊節點的位置變化構建一個最大遞增子序列,最大子序列能保證通過最小的移動或者patch實現節點的複用。

下面一起來看下如何實現的。

7.png

2.5.1 為新子節點構建key:index對映

8.png

// 5. 亂序的情況
// [i ... e1 + 1]: a b [c d e] f g
// [i ... e2 + 1]: a b [e d c h] f g
// i = 2, e1 = 4, e2 = 5

const s1 = i // s1 = 2
const s2 = i // s2 = 2

// 5.1 build key:index map for newChildren
// 首先為新的子節點構建在新的子序列中 key:index 的對映
// 通過map 建立的新的子節點
const keyToNewIndexMap = new Map()
// 遍歷新的節點,為新節點設定key
// i = 2; i <= 5
for (i = s2; i <= e2; i++) {
  // 獲取的是新序列中的子節點
  const nextChild = c2[i];
  if (nextChild.key != null) {
    // nextChild.key 已存在
    // a b [e d c h] f g
    // e:2 d:3 c:4 h:5
    keyToNewIndexMap.set(nextChild.key, i)
  }
}

結合上面的圖和程式碼可以知道:

  • 在經過首尾相同的patch處理之後,i = 2,e1 = 4,e2 = 5

  • 經過遍歷之後keyToNewIndexMap中,新節點的key:index的關係為 E : 2、D : 3 、C : 4、H : 5

  • keyToNewIndexMap的作用主要是後面通過遍歷舊子序列,確定可複用節點在新的子序列中的位置

2.5.2 從左向右遍歷舊子序列,patch匹配的相同型別的節點,移除不存在的節點

經過前面的處理,已經建立了keyToNewIndexMap

在開始從左向右遍歷之前,需要知道幾個變數的含義:

// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
// 從舊的子節點的左側開始迴圈遍歷進行patch。
// 並且patch匹配的節點 並移除不存在的節點

// 已經patch的節點個數
let patched = 0
// 需要patch的節點數量
// 以上圖為例:e2 = 5; s2 = 2; 知道需要patch的節點個數
// toBePatched = 4
const toBePatched = e2 - s2 + 1
// 用於判斷節點是否需要移動
// 當新舊佇列中出現可複用節點交叉時,moved = true
let moved = false
// used to track whether any node has moved
// 用於記錄節點是否已經移動
let maxNewIndexSoFar = 0

// works as Map<newIndex, oldIndex>
// 作新舊節點的下標對映
// Note that oldIndex is offset by +1
// 注意 舊節點的 index 要向右偏移一個下標

// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// 並且舊節點Index = 0 是一個特殊的值,用於表示新的節點中沒有對應的舊節點

// used for determining longest stable subsequence
// newIndexToOldIndexMap 用於確定最長遞增子序列
// 新下標與舊下標的map
const newIndexToOldIndexMap = new Array(toBePatched)
// 將所有的值初始化為0
// [0, 0, 0, 0]
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
  • 變數 patched 用於記錄已經patch的節點
  • 變數 toBePatched 用於記錄需要進行patch的節點個數
  • 變數 moved 用於記錄是否有可複用節點發生交叉
  • maxNewIndexSoFar用於記錄當舊的子序列中存在沒有設定key的子節點,但是該子節點出現於新的子序列中,且可複用,最大下標。
  • 變數newIndexToOldIndexMap用於對映新的子序列中的節點下標 對應於 舊的子序列中的節點的下標
  • 並且會將newIndexToOldIndexMap初始化為一個全0陣列,[0, 0, 0, 0]

9.png

知道了這些變數的含義之後 我們就可以開始從左向右遍歷子序列了。

遍歷的時候,需要首先遍歷舊子序列,起點是s1,終點是e1

遍歷的過程中會對patched進行累加。

解除安裝舊節點

如果patched >= toBePatched,說明新子序列中的子節點少於舊子序列中的節點數量。

需要對舊子節點進行解除安裝。

// 遍歷未處理舊序列中子節點
for (i = s1; i <= e1; i++) {
    // 獲取舊節點
    // 會逐個獲取 c d e
    const prevChild = c1[i]
    // 如果已經patch 的數量 >= 需要進行patch的節點個數
    
    // patched剛開始為 0
    // patched >= 4
    if (patched >= toBePatched) {
      // all new children have been patched so this can only be a removal
      // 這說明所有的新節點已經被patch 因此可以移除舊的
      unmount(prevChild, parentComponent, parentSuspense, true)
      continue
    }
}

如果prevChild.key是存在的,會通過前面我們構建的keyToNewIndexMap,獲取prevChild在新子序列中的下標newIndex

獲取newIndex

// 新節點下標
let newIndex
if (prevChild.key != null) {
  // 舊的節點肯定有key, 
  // 根據舊節點key  獲取相同型別的新的子節點  在 新的佇列中對應節點位置
  // 這個時候 因為c d e 是原來的節點 並且有key
  // h 是新增節點 舊節點中沒有 獲取不到 對應的index 會走else
  // 所以newIndex在開始時會有如下情況
  /**
   * node  newIndex
   *  c       4
   *  d       3
   *  e       2
   * */ 
  // 這裡是可以獲取到newIndex的
  newIndex = keyToNewIndexMap.get(prevChild.key)
}

以圖為例,可以知道,在遍歷過程中,節點c、d、e為可複用節點,分別對應新子序列中的2、3、4的位置。

newIndex可以取到的值為4、3、2

如果舊節點沒有key怎麼辦?

// key-less node, try to locate a key-less node of the same type
// 如果舊的節點沒有key
// 則會查詢沒有key的 且為相同型別的新節點在 新節點佇列中 的位置
// j = 2: j <= 5
for (j = s2; j <= e2; j++) {
  if (
    newIndexToOldIndexMap[j - s2] === 0 &&
    // 判斷是否是新舊節點是否相同
    isSameVNodeType(prevChild, c2[j])
  ) {
    // 獲取到相同型別節點的下標
    newIndex = j
    break
  }
}

如果節點沒有key,則同樣會取新子序列中,遍歷查詢沒有key且兩個新舊型別相同子節點,並以此節點的下標,作為newIndex

newIndexToOldIndexMap[j - s2] === 0 說明節點沒有該節點沒有key。

如果還沒有獲取到newIndex,說明在新子序列中沒有存在的與 prevChild 相同的子節點,需要對prevChild進行解除安裝。

if (newIndex === undefined) {
  // 沒有對應的新節點 解除安裝舊的
  unmount(prevChild, parentComponent, parentSuspense, true)
}

否則,開始根據newIndex,構建keyToNewIndexMap,明確新舊節點對應的下標位置。

時刻牢記newIndex是根據舊節點獲取的其在新的子序列中的下標。

// 這裡處理獲取到newIndex的情況
// 開始整理新節點下標 Index 對於 相同型別舊節點在 舊佇列中的對映
// 新節點下標從 s2=2 開始,對應的舊節點下標需要偏移一個下標
// 0 表示當前節點沒有對應的舊節點
// 偏移 1個位置 i從 s1 = 2 開始,s2 = 2
// 4 - 2 獲取下標 2,新的 c 節點對應舊 c 節點的位置下標 3
// 3 - 2 獲取下標 1,新的 d 節點對應舊 d 節點的位置下標 4
// 2 - 2 獲取下標 0,新的 e 節點對應舊 e 節點的位置下標 5
// [0, 0, 0, 0] => [5, 4, 3, 0]
// [2,3,4,5] = [5, 4, 3, 0]
newIndexToOldIndexMap[newIndex - s2] = i + 1
// newIndex 會取 4 3 2
/** 
 *   newIndex  maxNewIndexSoFar   moved
 *       4            0          false
 *       3            4           true
 *       2        
 * 
 * */ 
if (newIndex >= maxNewIndexSoFar) {
  maxNewIndexSoFar = newIndex
} else {
  moved = true
}

在構建newIndexToOldIndexMap的同時,會通過判斷newIndexmaxNewIndexSoFa的關係,確定節點是否發生移動。

newIndexToOldIndexMap最後遍歷結束應該為[5, 4, 3, 0]0說明有舊序列中沒有與心序列中對應的節點,並且該節點可能是新增節點。

如果新舊節點在序列中相對位置保持始終不變,則maxNewIndexSoFar會隨著newIndex的遞增而遞增。

意味著節點沒有發生交叉。也就不需要移動可複用節點。

否則可複用節點發生了移動,需要對可複用節點進行move

遍歷的最後,會對新舊節點進行patch,並對patched進行累加,記錄已經處理過幾個節點。

// 進行遞迴patch
/**
 * old   new
 *  c     c
 *  d     d
 *  e     e 
*/
patch(
  prevChild,
  c2[newIndex],
  container,
  null,
  parentComponent,
  parentSuspense,
  isSVG,
  slotScopeIds,
  optimized
)
// 已經patch的
patched++

經過上面的處理,已經完成對舊節點進行了解除安裝,對相對位置保持沒有變化的子節點進行了patch複用。

接下來就是需要移動可複用節點,掛載新子序列中新增節點。

2.5.3 移動可複用節點,掛載新增節點

這裡涉及到一塊比較核心的程式碼,也是Vue3 diff效率提升的關鍵所在。

前面通過newIndexToOldIndexMap,記錄了新舊子節點變化前後的下標對映。

這裡會通過getSequence方法獲取一個最大遞增子序列。用於記錄相對位置沒有發生變化的子節點的下標。

根據此遞增子序列,可以實現在移動可複用節點的時候,只移動相對位置前後發生變化的子節點。

做到最小改動。

那什麼是最大遞增子序列?

  • 子序列是由陣列派生而來的序列,刪除(或不刪除)陣列中的元素而不改變其餘元素的順序。
  • 而遞增子序列,是陣列派生的子序列,各元素之間保持逐個遞增的關係。
  • 例如:
  • 陣列[3, 6, 2, 7] 是陣列 [0, 3, 1, 6, 2, 2, 7] 的最長嚴格遞增子序列。
  • 陣列[2, 3, 7, 101] 是陣列 [10 , 9, 2, 5, 3, 7, 101, 18]的最大遞增子序列。
  • 陣列[0, 1, 2, 3] 是陣列 [0, 1, 0, 3, 2, 3]的最大遞增子序列。

10.png

已上圖為例,在未處理的亂序節點中,存在新增節點N、I、需要解除安裝的節點G,及可複用節點C、D、E、F

節點CDE在新舊子序列中相對位置沒有變換,如果想要通過最小變動實現節點複用,我們可以將找出F節點變化前後的下標位置,在新的子序列C節點之前插入F節點即可。

最大遞增子序列的作用就是通過新舊節點變化前後的對映,建立一個遞增陣列,這樣就可以知道哪些節點在變化前後相對位置沒有發生變化,哪些節點需要進行移動。

Vue3中的遞增子序列的不同在於,它儲存的是可複用節點在 newIndexToOldIndexMap的下標。而並不是newIndexToOldIndexMap中的元素。

接下來我們看下程式碼部分:

// 5.3 move and mount
// generate longest stable subsequence only when nodes have moved
// 移動節點 掛載節點
// 僅當節點被移動後 生成最長遞增子序列
// 經過上面操作後,newIndexToOldIndexMap = [5, 4, 3, 0]
// 得到 increasingNewIndexSequence = [2]
const increasingNewIndexSequence = moved
  ? getSequence(newIndexToOldIndexMap)
  : EMPTY_ARR
// j = 0
j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
// 從後向前遍歷 以便於可以用最新的被patch的節點作為錨點
// i = 3
for (i = toBePatched - 1; i >= 0; i--) {
  // 5 4 3 2
  const nextIndex = s2 + i
  // 節點 h  c  d  e 
  const nextChild = c2[nextIndex]
  // 獲取錨點
  const anchor =
    nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor
  // [5, 4, 3, 0] 節點h會被patch,其實是mount
  //  c  d  e 會被移動
  if (newIndexToOldIndexMap[i] === 0) {
    // mount new
    // 掛載新的
    patch(
      null,
      nextChild,
      container,
      anchor,
      ...
    )
  } else if (moved) {
    // move if:
    // There is no stable subsequence (e.g. a reverse)
    // OR current node is not among the stable sequence
    // 如果沒有最長遞增子序列或者 當前節點不在遞增子序列中間
    // 則移動節點
    // 
    if (j < 0 || i !== increasingNewIndexSequence[j]) {
      move(nextChild, container, anchor, MoveType.REORDER)
    } else {
      j--
    }
  }
}

11.png

從上面的程式碼可以知道:

  • 通過newIndexToOldIndexMap獲取的最大遞增子序列是[2]
  • j = 0
  • 遍歷的時候從右向左遍歷,這樣可以獲取到錨點,如果有已經經過patch的兄弟節點,則以兄弟節點作為錨點,否則以父節點作為錨點
  • newIndexToOldIndexMap[i] === 0,說明是新增節點。需要對節點進行mount,這時只需給patch的第一個引數傳null即可。可以知道首先會對h節點進行patch
  • 否則會判斷moved是否為true。通過前面的分析,我們知道節點C & 節點E在前後變化中發生了位置移動。
  • 故這裡會移動節點,我們知道 j 此時為0i 此時為**2**,i !== increasingNewIndexSequence[j]true,並不會移動C節點,而是執行 j--
  • 後面因為 j < 0,會對 D、E節點進行移動。

至此我們就完成了Vue3 diff演演算法的學習分析。

這裡為大家提供了一個範例,可以結合本文的分析過程進行練習:

可以只看第一張圖進行分析,分析結束後可以與第二三張圖片進行對比。

圖一:

12.png

圖二 & 三:

13.png

14.png

總結

通過上面的學習分析,可以知道,Vue3diff演演算法,會首先進行收尾相同節點的patch處理,結束後,會掛載新增節點,解除安裝舊節點。

如果子序列的情況較為複雜,比如出現亂序的情況,則會首先找出可複用的節點,並通過可複用節點的位置對映構建一個最大遞增子序列,通過最大遞增子序列來對節點進行mount & move。以提高diff效率,實現節點複用的最大可能性。

【相關推薦:】

以上就是深入解析Vue3中的 diff 演演算法(圖文詳解)的詳細內容,更多請關注TW511.COM其它相關文章!