本篇文章帶大家通過圖文來深入解析下Vue3中的 diff 算法，希望對大家有所幫助！

本篇文章主要分析Vue3 diff算法，通過本文你可以知道：

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

• diff是如何進(jìn)行節(jié)點復(fù)用、移動、卸載

• 并有一個示例題，可以結(jié)合本文進(jìn)行練習(xí)分析

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

• Vnode（https://mp.weixin.qq.com/s/DtFJpA91UPJIevlqaPzcnQ）

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

1.0 diff 無key子節(jié)點

在處理被標(biāo)記為UNKEYED_FRAGMENT時。

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

• 對公共部分循環(huán)遍歷patch。

• patch 結(jié)束，再處理剩余的新舊節(jié)點。

• 如果oldLength > newLength，說明需要對舊節(jié)點進(jìn)行unmount

• 否則，說明有新增節(jié)點，需要進(jìn)行mount;

這里貼下省略后的代碼。

const patchUnkeyedChildren = (c1, c2,...res) => {     c1 = c1 || EMPTY_ARR     c2 = c2 || EMPTY_ARR     // 獲取新舊子節(jié)點的長度     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. 卸載舊節(jié)點     if (oldLength > newLength) {       // remove old       unmountChildren(...)     } else {       // mount new       // 4. 否則掛載新的子節(jié)點       mountChildren(...)     }   }

從上面的代碼可以看出，在處理無key子節(jié)點的時候，邏輯還是非常簡單粗暴的。準(zhǔn)確的說處理無key子節(jié)點的效率并不高。

因為不管是直接對公共部分patch，還是直接對新增節(jié)點進(jìn)行mountChildren（其實是遍歷子節(jié)點，進(jìn)行patch操作），其實都是在遞歸進(jìn)行patch，這就會影響到性能。

2.0 diff 有key子節(jié)點序列

在diff有key子序列的時候，會進(jìn)行細(xì)分處理。主要會經(jīng)過以下一種情況的判斷：

• 起始位置節(jié)點類型相同。
• 結(jié)束位置節(jié)點類型相同。
• 相同部分處理完，有新增節(jié)點。
• 相同部分處理完，有舊節(jié)點需要卸載。
• 首尾相同，但中間部分存在可復(fù)用亂序節(jié)點。

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

• i = 0，指向新舊序列的開始位置
• e1 = oldLength - 1，指向舊序列的結(jié)束位置
• e2 = newLength - 1，指向新序列的結(jié)束位置

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

下面開始分情況進(jìn)行diff處理。

2.1 起始位置節(jié)點類型相同

• 對于起始位置類型相同的節(jié)點，從左向右進(jìn)行diff遍歷。

• 如果新舊節(jié)點類型相同，則進(jìn)行patch處理

• 節(jié)點類型不同，則break，跳出遍歷diff

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

上面上略了部分代碼，但不影響主要邏輯。

從代碼可以知道，遍歷時，利用前面在函數(shù)全局上下文中聲明的三個指針，進(jìn)行遍歷判斷。

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

一旦遇到類型不同的節(jié)點，就會跳出diff遍歷。

2.2 結(jié)束位置節(jié)點類型相同

開始位置相同diff 結(jié)束，會緊接著從序列尾部開始遍歷 diff。

此時需要對尾指針e1、e2進(jìn)行遞減。

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

從代碼可以看出，diff邏輯與第一種基本一樣，相同類型進(jìn)行patch處理。

不同類型break，跳出循環(huán)遍歷。

并且對尾指針進(jìn)行遞減操作。

2.3 相同部分遍歷結(jié)束，新序列中有新增節(jié)點，進(jìn)行掛載

經(jīng)過上面兩種情況的處理，已經(jīng)patch完首尾相同部分的節(jié)點，接下來是對新序列中的新增節(jié)點進(jìn)行patch處理。

在經(jīng)過上面兩種請款處理之后，如果有新增節(jié)點，可能會出現(xiàn) i > e1 && i <= e2的情況。

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

這時會對新增節(jié)點進(jìn)行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，說明有已經(jīng)patch過尾部節(jié)點，     // 否則會獲取父節(jié)點作為錨點     const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor     while (i <= e2) {       patch(null, c2[i], anchor, ...others)       i++     }   } }

從上面的代碼可以知道，patch的時候沒有傳第一個參數(shù)，最終會走mount的邏輯。

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

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

在patch的過程中，會遞增i指針。

并通過nextPos來獲取錨點。

如果nextPos < l2，則以已經(jīng)patch的節(jié)點作為錨點，否則以父節(jié)點作為錨點。

2.4 相同部分遍歷結(jié)束，新序列中少節(jié)點，進(jìn)行卸載

如果處理完收尾相同的節(jié)點，出現(xiàn)i > e2 && i <= e1的情況，則意味著有舊節(jié)點需要進(jìn)行卸載操作。

// 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指針，對舊節(jié)點進(jìn)行卸載。

2.5 亂序情況

這種情況下較為復(fù)雜，但diff的核心邏輯在于通過新舊節(jié)點的位置變化構(gòu)建一個最大遞增子序列，最大子序列能保證通過最小的移動或者patch實現(xiàn)節(jié)點的復(fù)用。

下面一起來看下如何實現(xiàn)的。

2.5.1 為新子節(jié)點構(gòu)建key:index映射

// 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 // 首先為新的子節(jié)點構(gòu)建在新的子序列中 key：index 的映射 // 通過map 創(chuàng)建的新的子節(jié)點 const keyToNewIndexMap = new Map() // 遍歷新的節(jié)點，為新節(jié)點設(shè)置key // i = 2; i <= 5 for (i = s2; i <= e2; i++) {   // 獲取的是新序列中的子節(jié)點   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)   } }

結(jié)合上面的圖和代碼可以知道：

• 在經(jīng)過首尾相同的patch處理之后，i = 2，e1 = 4，e2 = 5

• 經(jīng)過遍歷之后keyToNewIndexMap中，新節(jié)點的key:index的關(guān)系為 E : 2、D : 3 、C : 4、H : 5

• keyToNewIndexMap的作用主要是后面通過遍歷舊子序列，確定可復(fù)用節(jié)點在新的子序列中的位置

2.5.2 從左向右遍歷舊子序列，patch匹配的相同類型的節(jié)點，移除不存在的節(jié)點

經(jīng)過前面的處理，已經(jīng)創(chuàng)建了keyToNewIndexMap。

在開始從左向右遍歷之前，需要知道幾個變量的含義：

// 5.2 loop through old children left to be patched and try to patch // matching nodes & remove nodes that are no longer present // 從舊的子節(jié)點的左側(cè)開始循環(huán)遍歷進(jìn)行patch。 // 并且patch匹配的節(jié)點 并移除不存在的節(jié)點  // 已經(jīng)patch的節(jié)點個數(shù) let patched = 0 // 需要patch的節(jié)點數(shù)量 // 以上圖為例：e2 = 5; s2 = 2; 知道需要patch的節(jié)點個數(shù) // toBePatched = 4 const toBePatched = e2 - s2 + 1 // 用于判斷節(jié)點是否需要移動 // 當(dāng)新舊隊列中出現(xiàn)可復(fù)用節(jié)點交叉時，moved = true let moved = false // used to track whether any node has moved // 用于記錄節(jié)點是否已經(jīng)移動 let maxNewIndexSoFar = 0  // works as Map<newIndex, oldIndex> // 作新舊節(jié)點的下標(biāo)映射 // Note that oldIndex is offset by +1 // 注意 舊節(jié)點的 index 要向右偏移一個下標(biāo)  // and oldIndex = 0 is a special value indicating the new node has // no corresponding old node. // 并且舊節(jié)點Index = 0 是一個特殊的值，用于表示新的節(jié)點中沒有對應(yīng)的舊節(jié)點  // used for determining longest stable subsequence // newIndexToOldIndexMap 用于確定最長遞增子序列 // 新下標(biāo)與舊下標(biāo)的map const newIndexToOldIndexMap = new Array(toBePatched) // 將所有的值初始化為0 // [0, 0, 0, 0] for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0

• 變量 patched 用于記錄已經(jīng)patch的節(jié)點
• 變量 toBePatched 用于記錄需要進(jìn)行patch的節(jié)點個數(shù)
• 變量 moved 用于記錄是否有可復(fù)用節(jié)點發(fā)生交叉
• maxNewIndexSoFar用于記錄當(dāng)舊的子序列中存在沒有設(shè)置key的子節(jié)點，但是該子節(jié)點出現(xiàn)于新的子序列中，且可復(fù)用，最大下標(biāo)。
• 變量newIndexToOldIndexMap用于映射新的子序列中的節(jié)點下標(biāo) 對應(yīng)于 舊的子序列中的節(jié)點的下標(biāo)
• 并且會將newIndexToOldIndexMap初始化為一個全0數(shù)組，[0, 0, 0, 0]

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

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

遍歷的過程中會對patched進(jìn)行累加。

卸載舊節(jié)點

如果patched >= toBePatched，說明新子序列中的子節(jié)點少于舊子序列中的節(jié)點數(shù)量。

需要對舊子節(jié)點進(jìn)行卸載。

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

如果prevChild.key是存在的，會通過前面我們構(gòu)建的keyToNewIndexMap，獲取prevChild在新子序列中的下標(biāo)newIndex。

獲取newIndex

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

以圖為例，可以知道，在遍歷過程中，節(jié)點c、d、e為可復(fù)用節(jié)點，分別對應(yīng)新子序列中的2、3、4的位置。

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

如果舊節(jié)點沒有key怎么辦？

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

如果節(jié)點沒有key，則同樣會取新子序列中，遍歷查找沒有key且兩個新舊類型相同子節(jié)點，并以此節(jié)點的下標(biāo)，作為newIndex。

newIndexToOldIndexMap[j – s2] === 0 說明節(jié)點沒有該節(jié)點沒有key。

如果還沒有獲取到newIndex，說明在新子序列中沒有存在的與 prevChild 相同的子節(jié)點，需要對prevChild進(jìn)行卸載。

if (newIndex === undefined) {   // 沒有對應(yīng)的新節(jié)點 卸載舊的   unmount(prevChild, parentComponent, parentSuspense, true) }

否則，開始根據(jù)newIndex，構(gòu)建keyToNewIndexMap，明確新舊節(jié)點對應(yīng)的下標(biāo)位置。

時刻牢記newIndex是根據(jù)舊節(jié)點獲取的其在新的子序列中的下標(biāo)。

// 這里處理獲取到newIndex的情況 // 開始整理新節(jié)點下標(biāo) Index 對于 相同類型舊節(jié)點在 舊隊列中的映射 // 新節(jié)點下標(biāo)從 s2=2 開始，對應(yīng)的舊節(jié)點下標(biāo)需要偏移一個下標(biāo) // 0 表示當(dāng)前節(jié)點沒有對應(yīng)的舊節(jié)點 // 偏移 1個位置 i從 s1 = 2 開始，s2 = 2 // 4 - 2 獲取下標(biāo) 2，新的 c 節(jié)點對應(yīng)舊 c 節(jié)點的位置下標(biāo) 3 // 3 - 2 獲取下標(biāo) 1，新的 d 節(jié)點對應(yīng)舊 d 節(jié)點的位置下標(biāo) 4 // 2 - 2 獲取下標(biāo) 0，新的 e 節(jié)點對應(yīng)舊 e 節(jié)點的位置下標(biāo) 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 }

在構(gòu)建newIndexToOldIndexMap的同時，會通過判斷newIndex、maxNewIndexSoFa的關(guān)系，確定節(jié)點是否發(fā)生移動。

newIndexToOldIndexMap最后遍歷結(jié)束應(yīng)該為[5, 4, 3, 0]，0說明有舊序列中沒有與心序列中對應(yīng)的節(jié)點，并且該節(jié)點可能是新增節(jié)點。

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

意味著節(jié)點沒有發(fā)生交叉。也就不需要移動可復(fù)用節(jié)點。

否則可復(fù)用節(jié)點發(fā)生了移動，需要對可復(fù)用節(jié)點進(jìn)行move。

遍歷的最后，會對新舊節(jié)點進(jìn)行patch，并對patched進(jìn)行累加，記錄已經(jīng)處理過幾個節(jié)點。

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

經(jīng)過上面的處理，已經(jīng)完成對舊節(jié)點進(jìn)行了卸載，對相對位置保持沒有變化的子節(jié)點進(jìn)行了patch復(fù)用。

接下來就是需要移動可復(fù)用節(jié)點，掛載新子序列中新增節(jié)點。

2.5.3 移動可復(fù)用節(jié)點，掛載新增節(jié)點

這里涉及到一塊比較核心的代碼，也是Vue3 diff效率提升的關(guān)鍵所在。

前面通過newIndexToOldIndexMap，記錄了新舊子節(jié)點變化前后的下標(biāo)映射。

這里會通過getSequence方法獲取一個最大遞增子序列。用于記錄相對位置沒有發(fā)生變化的子節(jié)點的下標(biāo)。

根據(jù)此遞增子序列，可以實現(xiàn)在移動可復(fù)用節(jié)點的時候，只移動相對位置前后發(fā)生變化的子節(jié)點。

做到最小改動。

那什么是最大遞增子序列？

• 子序列是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。
• 而遞增子序列，是數(shù)組派生的子序列，各元素之間保持逐個遞增的關(guān)系。
• 例如：
• 數(shù)組[3, 6, 2, 7] 是數(shù)組 [0, 3, 1, 6, 2, 2, 7] 的最長嚴(yán)格遞增子序列。
• 數(shù)組[2, 3, 7, 101] 是數(shù)組 [10 , 9, 2, 5, 3, 7, 101, 18]的最大遞增子序列。
• 數(shù)組[0, 1, 2, 3] 是數(shù)組 [0, 1, 0, 3, 2, 3]的最大遞增子序列。

已上圖為例，在未處理的亂序節(jié)點中，存在新增節(jié)點N、I、需要卸載的節(jié)點G，及可復(fù)用節(jié)點C、D、E、F。

節(jié)點CDE在新舊子序列中相對位置沒有變換，如果想要通過最小變動實現(xiàn)節(jié)點復(fù)用，我們可以將找出F節(jié)點變化前后的下標(biāo)位置，在新的子序列C節(jié)點之前插入F節(jié)點即可。

最大遞增子序列的作用就是通過新舊節(jié)點變化前后的映射，創(chuàng)建一個遞增數(shù)組，這樣就可以知道哪些節(jié)點在變化前后相對位置沒有發(fā)生變化，哪些節(jié)點需要進(jìn)行移動。

Vue3中的遞增子序列的不同在于，它保存的是可復(fù)用節(jié)點在 newIndexToOldIndexMap的下標(biāo)。而并不是newIndexToOldIndexMap中的元素。

接下來我們看下代碼部分：

// 5.3 move and mount // generate longest stable subsequence only when nodes have moved // 移動節(jié)點 掛載節(jié)點 // 僅當(dāng)節(jié)點被移動后 生成最長遞增子序列 // 經(jīng)過上面操作后，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的節(jié)點作為錨點 // i = 3 for (i = toBePatched - 1; i >= 0; i--) {   // 5 4 3 2   const nextIndex = s2 + i   // 節(jié)點 h  c  d  e    const nextChild = c2[nextIndex]   // 獲取錨點   const anchor =     nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor   // [5, 4, 3, 0] 節(jié)點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     // 如果沒有最長遞增子序列或者 當(dāng)前節(jié)點不在遞增子序列中間     // 則移動節(jié)點     //      if (j < 0 || i !== increasingNewIndexSequence[j]) {       move(nextChild, container, anchor, MoveType.REORDER)     } else {       j--     }   } }

從上面的代碼可以知道：

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

至此我們就完成了Vue3 diff算法的學(xué)習(xí)分析。

這里為大家提供了一個示例，可以結(jié)合本文的分析過程進(jìn)行練習(xí)：

可以只看第一張圖進(jìn)行分析，分析結(jié)束后可以與第二三張圖片進(jìn)行對比。

圖一：

圖二 & 三：

總結(jié)

通過上面的學(xué)習(xí)分析，可以知道，Vue3 的diff算法，會首先進(jìn)行收尾相同節(jié)點的patch處理，結(jié)束后，會掛載新增節(jié)點，卸載舊節(jié)點。

如果子序列的情況較為復(fù)雜，比如出現(xiàn)亂序的情況，則會首先找出可復(fù)用的節(jié)點，并通過可復(fù)用節(jié)點的位置映射構(gòu)建一個最大遞增子序列，通過最大遞增子序列來對節(jié)點進(jìn)行mount & move。以提高diff效率，實現(xiàn)節(jié)點復(fù)用的最大可能性。

【