深入 Vue2.x 的虛擬 DOM diff 原理
一、前言
Vue的核心是雙向綁定和虛擬DOM(下文我們簡(jiǎn)稱為vdom)，關(guān)于雙向綁定可以參閱木琴的文章《剖析Vue原理&實(shí)現(xiàn)雙向綁定MVVM》，vdom是樹狀結(jié)構(gòu)，其節(jié)點(diǎn)為vnode，vnode和瀏覽器DOM中的Node一一對(duì)應(yīng)，通過vnode的elm屬性可以訪問到對(duì)應(yīng)的Node。
vdom因?yàn)槭羌兇獾腏S對(duì)象，所以操作它會(huì)很高效，但是vdom的變更最終會(huì)轉(zhuǎn)換成DOM操作，為了實(shí)現(xiàn)高效的DOM操作，一套高效的虛擬DOM diff算法顯得很有必要。
Vue的diff算法是基于snabbdom改造過來的，感興趣的朋友可以選擇查閱。
這是一張很經(jīng)典的圖，出自《React’s diff algorithm》，Vue的diff算法也同樣，即僅在同級(jí)的vnode間做diff，遞歸地進(jìn)行同級(jí)vnode的diff，最終實(shí)現(xiàn)整個(gè)DOM樹的更新。那同級(jí)vnode diff的細(xì)節(jié)又是怎樣的呢?正是本文所要講的。
二、例子
我們?cè)谙挛闹袑⑹褂眠@個(gè)簡(jiǎn)化的例子來講述diff的過程
如上圖的例子，更新前是1到10排列的Node列表，更新后是亂序排列的Node列表。羅列一下圖中有以下幾種類型的節(jié)點(diǎn)變化情況：
(1)、頭部相同、尾部相同的節(jié)點(diǎn)：如1、10
(2)、頭尾相同的節(jié)點(diǎn)：如2、9(處理完頭部相同、尾部相同節(jié)點(diǎn)之后)
(3)、新增的節(jié)點(diǎn)：11
(4)、刪除的節(jié)點(diǎn)：8
(5)、其他節(jié)點(diǎn)：3、4、5、6、7
三、簡(jiǎn)單的diff
簡(jiǎn)單的diff算法可以這樣設(shè)計(jì)：
逐個(gè)遍歷newVdom的節(jié)點(diǎn)，找到它在oldVdom中的位置，如果找到了就移動(dòng)對(duì)應(yīng)的DOM元素，如果沒找到說明是新增節(jié)點(diǎn)，則新建一個(gè)節(jié)點(diǎn)插入。遍歷完成之后如果oldVdom中還有沒處理過的節(jié)點(diǎn)，則說明這些節(jié)點(diǎn)在newVdom中被刪除了，刪除它們即可。
仔細(xì)思考一下，幾乎每一步都要做移動(dòng)DOM的操作，這在DOM整體結(jié)構(gòu)變化不大時(shí)的開銷是很大的，實(shí)際上DOM變化不大的情況現(xiàn)實(shí)中經(jīng)常發(fā)生，很多時(shí)候我們只需要變更某個(gè)節(jié)點(diǎn)的文本而已。
接下來我們看一下Vue的diff實(shí)現(xiàn)
四、Vue的diff實(shí)現(xiàn)
上圖例子中我畫上了oldStart+oldEnd，newStart+newEnd這樣2對(duì)指針，分別對(duì)應(yīng)oldVdom和newVdom的起點(diǎn)和終點(diǎn)。起止點(diǎn)之前的節(jié)點(diǎn)是待處理的節(jié)點(diǎn)，Vue不斷對(duì)vnode進(jìn)行處理同時(shí)移動(dòng)指針直到其中任意一對(duì)起點(diǎn)和終點(diǎn)相遇。處理過的節(jié)點(diǎn)Vue會(huì)在oldVdom和newVdom中同時(shí)將它標(biāo)記為已處理(標(biāo)記方法后文中有介紹)。Vue通過以下措施來提升diff的性能。
(一)、優(yōu)先處理特殊場(chǎng)景
(1)、頭部的同類型節(jié)點(diǎn)、尾部的同類型節(jié)點(diǎn)
這類節(jié)點(diǎn)更新前后位置沒有發(fā)生變化，所以不用移動(dòng)它們對(duì)應(yīng)的DOM
(2)、頭尾/尾頭的同類型節(jié)點(diǎn)
這類節(jié)點(diǎn)位置很明確，不需要再花心思查找，直接移動(dòng)DOM就好
處理了這些場(chǎng)景之后，一方面一些不需要做移動(dòng)的DOM得到快速處理，另一方面待處理節(jié)點(diǎn)變少，縮小了后續(xù)操作的處理范圍，性能也得到提升。
(二)、“原地復(fù)用”
“原地復(fù)用”是指Vue會(huì)盡可能復(fù)用DOM，盡可能不發(fā)生DOM的移動(dòng)。Vue在判斷更新前后指針是否指向同一個(gè)節(jié)點(diǎn)，其實(shí)不要求它們真實(shí)引用同一個(gè)DOM節(jié)點(diǎn)，實(shí)際上它僅判斷指向的是否是同類節(jié)點(diǎn)(比如2個(gè)不同的div，在DOM上它們是不一樣的，但是它們屬于同類節(jié)點(diǎn))，如果是同類節(jié)點(diǎn)，那么Vue會(huì)直接復(fù)用DOM，這樣的好處是不需要移動(dòng)DOM。再看上面的實(shí)例，假如10個(gè)節(jié)點(diǎn)都是div，那么整個(gè)diff過程中就沒有移動(dòng)DOM的操作了。
“原地復(fù)用”在Vue的官方文檔中有提到，雖然帶來了好處，但是也會(huì)產(chǎn)生一些問題，朋友們可以復(fù)習(xí)一下
https://cn.vuejs.org/v2/guide/list.html#key
https://cn.vuejs.org/v2/guide/conditional.html#用-key-管理可復(fù)用的元素
五、按步解剖實(shí)例
(一)、整體視圖
先看一張整體視圖，整個(gè)diff分兩部分：
(1)、***部分是一個(gè)循環(huán)，循環(huán)內(nèi)部是一個(gè)分支邏輯，每次循環(huán)只會(huì)進(jìn)入其中的一個(gè)分支，每次循環(huán)會(huì)處理一個(gè)節(jié)點(diǎn)，處理之后將節(jié)點(diǎn)標(biāo)記為已處理(oldVdom和newVdom都要進(jìn)行標(biāo)記，如果節(jié)點(diǎn)只出現(xiàn)在其中某一個(gè)vdom中，則另一個(gè)vdom中不需要進(jìn)行標(biāo)記)，標(biāo)記的方法有2種，當(dāng)節(jié)點(diǎn)正好在vdom的指針處，移動(dòng)指針將它排除到未處理列表之外即可，否則就要采用其他方法，Vue的做法是將節(jié)點(diǎn)設(shè)置為undefined。
(2)、循環(huán)結(jié)束之后，可能newVdom或者oldVdom中還有未處理的節(jié)點(diǎn)，如果是newVdom中有未處理節(jié)點(diǎn)，則這些節(jié)點(diǎn)是新增節(jié)點(diǎn)，做新增處理。如果是oldVdom中有這類節(jié)點(diǎn)，則這些是需要?jiǎng)h除的節(jié)點(diǎn)，相應(yīng)在DOM樹中刪除之
整個(gè)過程是逐步找到更新前后vdom的差異，然后將差異反應(yīng)到DOM樹上(也就是patch)，特別要提一下Vue的patch是即時(shí)的，并不是打包所有修改***一起操作DOM(React則是將更新放入隊(duì)列后集中處理)，朋友們會(huì)問這樣做性能很差吧?實(shí)際上現(xiàn)代瀏覽器對(duì)這樣的DOM操作做了優(yōu)化，并無差別。
(二)、逐步解析
(1)、處理頭部的同類型節(jié)點(diǎn)，即oldStart和newStart指向同類節(jié)點(diǎn)的情況，如下圖中的節(jié)點(diǎn)1
這種情況下，將節(jié)點(diǎn)1的變更更新到DOM，然后對(duì)其進(jìn)行標(biāo)記，標(biāo)記方法是oldStart和newStart后移1位即可，過程中不需要移動(dòng)DOM(更新DOM或許是要的，比如屬性變更了，文本內(nèi)容變更了等等)
(2)、處理尾部的同類型節(jié)點(diǎn)，即oldEnd和newEnd指向同類節(jié)點(diǎn)的情況，如下圖中的節(jié)點(diǎn)10
與情況(1)類似，這種情況下，將節(jié)點(diǎn)10的變更更新到DOM，然后oldEnd和newEnd前移1位進(jìn)行標(biāo)記，同樣也不需要移動(dòng)DOM
(3)、處理頭尾/尾頭的同類型節(jié)點(diǎn)，即oldStart和newEnd，以及oldEnd和newStart指向同類節(jié)點(diǎn)的情況，如下圖中的節(jié)點(diǎn)2和節(jié)點(diǎn)9
先看節(jié)點(diǎn)2，其實(shí)是往后移了，移到哪里?移到oldEnd指向的節(jié)點(diǎn)(即節(jié)點(diǎn)9)后面，移動(dòng)之后標(biāo)記該節(jié)點(diǎn)，將oldStart后移1位，newEnd前移一位
操作結(jié)束之后情況如下圖
同樣地，節(jié)點(diǎn)9也是類似的處理，處理完之后成了下面這樣
(4)、處理新增的節(jié)點(diǎn)
newStart來到了節(jié)點(diǎn)11的位置，在oldVdom中找不到節(jié)點(diǎn)11，說明它是新增的
那么就創(chuàng)建一個(gè)新的節(jié)點(diǎn)，插入DOM樹，插到什么位置?插到oldStart指向的節(jié)點(diǎn)(即節(jié)點(diǎn)3)前面，然后將newStart后移1位標(biāo)記為已處理(注意oldVdom中沒有節(jié)點(diǎn)11，所以標(biāo)記過程中它的指針不需要移動(dòng))，處理之后如下圖
(5)、處理更新的節(jié)點(diǎn)
經(jīng)過第(4)步之后，newStart來到了節(jié)點(diǎn)7的位置，在oldVdom中能找到它而且不在指針位置(查找oldVdom中oldStart到oldEnd區(qū)間內(nèi)的節(jié)點(diǎn))，說明它的位置移動(dòng)了
那么需要在DOM樹中移動(dòng)它，移到哪里?移到oldStart指向的節(jié)點(diǎn)(即節(jié)點(diǎn)3)前面，與此同時(shí)將節(jié)點(diǎn)標(biāo)記為已處理，跟前面幾種情況有點(diǎn)不同，newVdom中該節(jié)點(diǎn)在指針下，可以移動(dòng)newStart進(jìn)行標(biāo)記，而在oldVdom中該節(jié)點(diǎn)不在指針處，所以采用設(shè)置為undefined的方式來標(biāo)記(一定要標(biāo)記嗎?后面會(huì)提到)
處理之后就成了下面這樣
(6)、處理3、4、5、6節(jié)點(diǎn)
經(jīng)過第(5)步處理之后，我們看到了令人欣慰的一幕，newStart和oldStart又指向了同一個(gè)節(jié)點(diǎn)(即都指向節(jié)點(diǎn)3)，很簡(jiǎn)單，按照(1)中的做法只需移動(dòng)指針即可，非常高效，3、4、5、6都如此處理，處理完之后如下圖
(7)、處理需刪除的節(jié)點(diǎn)
經(jīng)過前6步處理之后(實(shí)際上前6步是循環(huán)進(jìn)行的)，朋友們看newStart跨過了newEnd，它們相遇啦!而這個(gè)時(shí)候，oldStart和oldEnd還沒有相遇，說明這2個(gè)指針之間的節(jié)點(diǎn)(包括它們指向的節(jié)點(diǎn)，即上圖中的節(jié)點(diǎn)7、節(jié)點(diǎn)8)是此次更新中被刪掉的節(jié)點(diǎn)。
OK，那我們?cè)贒OM樹中將它們刪除，再回到前面我們對(duì)節(jié)點(diǎn)7做了標(biāo)記，為什么標(biāo)記是必需的?標(biāo)記的目的是告訴Vue它已經(jīng)處理過了，是需要出現(xiàn)在新DOM中的節(jié)點(diǎn)，不要?jiǎng)h除它，所以在這里只需刪除節(jié)點(diǎn)8。
在應(yīng)用中也可能會(huì)遇到oldVdom的起止點(diǎn)相遇了，但是newVdom的起止點(diǎn)沒有相遇的情況，這個(gè)時(shí)候需要對(duì)newVdom中的未處理節(jié)點(diǎn)進(jìn)行處理，這類節(jié)點(diǎn)屬于更新中被加入的節(jié)點(diǎn)，需要將他們插入到DOM樹中。
至此，整個(gè)diff過程結(jié)束了
Vue的diff算法與動(dòng)態(tài)規(guī)劃算法中的經(jīng)典案例“計(jì)算a到b的最小編輯距離”看上去有些相似，實(shí)際完全不同，Vue的diff相對(duì)來說輕量很多，感興趣的朋友可以查閱相關(guān)資料進(jìn)行了解。
原文鏈接：https://www.qcloud.com/community/article/648055
作者：汪玉林
【本文是51CTO專欄作者“騰訊云技術(shù)社區(qū)”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)通過51CTO聯(lián)系原作者獲取授權(quán)】
