由淺入深讀透 vue 源碼：diff 算法

導語 | 開發者工作中，研究代碼邏輯常需要思考這個問題：數組變更後，具體變更了哪一些元素？變更的位置如何？本文作者陳碧鬆解析並覆寫了針對數組變化的 diff 算法邏輯。希望本文對你有幫助。

diff 方法的運行規則和前提方法

爲了瞭解 diff 方法的運行規則和前提方法，首先我們通過幾個圖快速區別虛擬 node 進行深度優先和同級對比。

深度優先:

同級對比：

如上面圖所示，每次 vnode 都是執行同級對比。（對應 dom 同一個父元素）

代碼邏輯如下圖：

第二，簡單判斷：sameVnode 函數用來進行判斷是否是同一個 vnode 元素。源代碼如下：

如圖所示：

這裏有兩個重要元素：key : 開發者定義的”:key”；sel :  元素 tagName + 元素 id + 元素 class。

sel 的定義源碼如下：

vNode 構建函數：

第三是構建索引。

邏輯如圖：

如何處理元素

儘量不新增 / 刪除 dom。如圖下所示:

如果是相同 vnode，源碼如下：

開始比較

首先會進行時間複雜度 O(n) 的 while 循環，循環條件爲 “遍歷舊節點數組 && 遍歷新節點數組，誰先遍歷完循環就結束”。源碼如下圖:

在每次的循環過程中，會有兩大類判斷方法：

1）首尾比較 & 首尾序號

邏輯：如圖上所示。首先在循環遍歷前標記好新，舊節點數組的開始位置和結束位置的序號：oldStartIdx、oldEndIdx、newStartIdx、newEndIdx；其次在循環遍歷的過程中採用 “****首首比較，尾尾比較，首尾比較 "。

源碼如下：

如果數據爲圖上所示，那麼根據首尾比較方法會有如下圖所示結果，最終全部執行了更新操作：

2）索引比較

**最壞情況, 這裏的時間複雜度也是 O(n)，即整個算法複雜度 O(n)+O(n)。**每次遍歷的過程中可能存在 "新數組節點新增 / 舊數組節點刪除"，那麼前後對比就滿足不了條件。這裏邏輯會進入索引比較：比如這種情況：

那麼循環中會執行一遍，創建舊數組的索引對象。從創建到比較的整個邏輯圖如下：

這裏的源碼如下:

源碼如下:

源碼：

3）當節點遍歷完之後

會存在兩種情況：新數組已經遍歷完，但舊數組沒有遍歷完成；舊數組遍歷完成，但新數組沒有遍歷完成。故源代碼的判斷如下:

舊數組沒有循環完成的效果如下圖所示：

這裏注意一個點，我們每次的節點更新會移動序號，即使被刪除的節點不在一塊最終也會被首尾比較算法 “摞在一塊”（oldStartIdx~oldEndIdx）。上圖所示更加明顯。源碼在這裏就進行批量刪除：

效果如下圖所示:

整體來說，有幾個關鍵點：簡單對比；創建舊數組的索引表；首位對比 & 首尾索引 & vnode 位置移動；索引添加 / 位移；剩餘部分批量處理添加 / 刪除。

經過前後對比 & 索引的過濾後，只會存在新. 末尾節點!== 舊節點及之前的連續的新節點 (!== 舊節點)，所以這裏也被 “摞在一塊”，即 （newStartIdx~newEndIdx）。源碼如下。這樣，整個 diff 的對比算法就已經走完了。核心就是：前後對比 + 索引。

vue3.0 對於 diff 比較前的優化

vue3.0 針對 “無腦”patchVnode 進行了過濾 -- 靜態類型 Vnode 老版的源碼:

這裏，我們再重複下 vue2.x 系列的對比更新邏輯:

新版的 vue3.0 增加了靜態類型 Vnode。如果是靜態類型的 vnode，直接跳過更新，修改新節點引用即可。

comment 類型目前翻到它的源碼也只是更改引用，源碼作者加上了一行註釋。

補充一下，flagment 碎片類型爲新增的 vnode 類型，即：

vue3.0 的過濾判斷源碼如下:

數組比較的應用

由於我們想監聽數組的變化，參考了 diff 算法覆寫類似的邏輯，用來在 update,add,dels 時，代碼層面獲取操作的具體節點明細（新舊節點的位置，內容）。希望本文對你有幫助。

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

猜你喜歡