由淺入深讀透vue原始碼:diff演算法

語言: CN / TW / HK

圖片

導語 | 開發者工作中,研究程式碼邏輯常需要思考這個問題:陣列變更後,具體變更了哪一些元素?變更的位置如何?本文作者陳碧鬆解析並覆寫了針對陣列變化的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)。每次遍歷的過程中可能存在"新陣列節點新增/舊陣列節點刪除",那麼前後對比就滿足不了條件。這裡邏輯會進入索引比較:比如這種情況:

圖片

那麼迴圈中會執行一遍,建立舊陣列的索引物件。從建立到比較的整個邏輯圖如下:

圖片

這裡的原始碼如下:

圖片

  • 當舊節點不存在新增的節點時,進行當前oldStartIdx位置的新增

    圖片

原始碼如下:

圖片

  • 當舊陣列存在節點,那麼進行位置移動

    圖片

原始碼:

圖片

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時,程式碼層面獲取操作的具體節點明細(新舊節點的位置,內容)。希望本文對你有幫助。

你可能感興趣的騰訊工程師作品

| 優雅應對故障:QQ音樂怎麼做高可用架構體系?

| 最全Go select底層原理,一文學透高頻用法

| 十億人都在用的健康碼,運維體系是怎麼設計的

|詳解全網最快Go泛型跳錶【內附原始碼】

技術盲盒:前端後端AI與演算法運維工程師文化