Vue2.0的Virtual DOM是基于Snabbdom改造的,針對(duì)Children的Diff過程,做了一下詳細(xì)的過程分析以及演示。
-
前言
?? 瀏覽器在渲染
DOM元素的時(shí)候,是非?!嘿F的’,在進(jìn)行DOM更新的時(shí)候,針對(duì)復(fù)雜DOM的局部更新,為了節(jié)省瀏覽器的開支,避免不必要的更新,這個(gè)時(shí)候就需要通過Diff比較來決定更新哪些DOM元素,當(dāng)然,并不是所有的情況都能使Virtual DOM比原生DOM操作要快,這里我就不過多闡述了,好了,進(jìn)入主題
1.0 Snabbdom Diff 方式
?? Snabbdom 在進(jìn)行 Diff 比較的時(shí)候只針對(duì)同層級(jí)進(jìn)行比較,而不會(huì)進(jìn)行跨層級(jí)比較,也就是說,我不會(huì)管你當(dāng)前的 Children 是否一致,這里我只關(guān)心你和他。Snabbdom 更新DOM的方式是 先移 后添加或刪除, Diff 比較是雙向由外向里進(jìn)行比較。

為了方便演示
Snabbdom的Diff的過程,這里我以一個(gè)DOM更新的案例為大家講解
??假設(shè)當(dāng)前
DOMparentElm有9個(gè)DOM元素,
??這里我用數(shù)組模擬oldCh = [null, "A", "B", "C", "D", "E", "F", "G", null]表示,
??其中數(shù)組的每一個(gè)元素代表一個(gè)子節(jié)點(diǎn)DOM,其中兩個(gè)null,表示已經(jīng)移除了,這里加入null的目的是為了后續(xù)分析源碼流程所使用。

??更新后
DOMparentElm有11個(gè)DOM元素,
??這里我用數(shù)組模擬newCh = [null, "A", "F", "E", "M", "O", "I", "E", "B", "G", null]表示,
??其中數(shù)組的每一個(gè)元素代表一個(gè)子節(jié)點(diǎn)DOM,其中兩個(gè)null,表示已經(jīng)移除了,這里加入null的目的是為了后續(xù)分析源碼流程所使用。
2.0 Snabbdom Diff 過程
??首先,我用一張圖來解釋Snabbdom 在找出差異之前是如何進(jìn)行Diff 比較的

??Snabbdom 在找出差異之前,每一輪的比較是需要經(jīng)過8項(xiàng)條件比較的,具體比較【條件】如下:
??【1】.判斷
oldCh第一個(gè)節(jié)點(diǎn)元素是不是空的,如果是空的表示DOM已經(jīng)移除,接著進(jìn)行下一輪比較
??【2】.判斷oldCh最后一個(gè)節(jié)點(diǎn)元素是不是空的,如果是空的表示DOM已經(jīng)移除,接著進(jìn)行下一輪比較
??【3】.判斷newCh第一個(gè)節(jié)點(diǎn)元素是不是空的,如果是空的表示DOM已經(jīng)移除,接著進(jìn)行下一輪比較
??【4】.判斷newCh最后一個(gè)節(jié)點(diǎn)元素是不是空的,如果是空的表示DOM已經(jīng)移除,接著進(jìn)行下一輪比較。
??【5】.判斷oldCh與newCh第一個(gè)節(jié)點(diǎn)元素是不是相同,如果相同我們接著進(jìn)行下一輪比較
??【6】.判斷oldCh與newCh最后一個(gè)節(jié)點(diǎn)元素是不是相同,如果相同我們接著進(jìn)行下一輪比較
??【7】.判斷oldCh第一個(gè)節(jié)點(diǎn)元素與newCh的最后一個(gè)節(jié)點(diǎn)元素是否相同,如果相同,就將oldCh第一個(gè)節(jié)點(diǎn)元素進(jìn)行移動(dòng),具體如何移動(dòng),后面我會(huì)詳細(xì)闡述說明。
??【8】.判斷oldCh最后一個(gè)節(jié)點(diǎn)元素與newCh的第一個(gè)節(jié)點(diǎn)元素是否相同,如果相同,就將oldCh最后一個(gè)節(jié)點(diǎn)元素進(jìn)行移動(dòng),具體如何移動(dòng),后面我會(huì)詳細(xì)闡述說明。
??由于 Diff 比較過程是雙向由外向里進(jìn)行比較,所以為了比較過程這里我們?cè)O(shè)置幾個(gè)記錄值
??為了記錄比較過程這里我們?cè)O(shè)置幾個(gè)記錄值
??oldSIdx:初始值為0,表示當(dāng)前oldCh比較隊(duì)列的 初始的節(jié)點(diǎn)位置
??newSIdx:初始值為0,表示當(dāng)前newCh比較隊(duì)列的 初始的節(jié)點(diǎn)位置
??oldEIdx: 初始值為oldCh.length-1,表示當(dāng)前oldCh比較隊(duì)列的末尾的節(jié)點(diǎn)位置
??newEIdx: 初始值為newCh.length-1,表示當(dāng)前newCh比較隊(duì)列的末尾的節(jié)點(diǎn)位置
??oldSnode:初始值為oldCh[0],表示當(dāng)前oldCh比較隊(duì)列的初始節(jié)點(diǎn)
??oldEnode:初始值為oldCh[oldEIdx],表示當(dāng)前oldCh比較隊(duì)列的末尾節(jié)點(diǎn)
??newSnode:初始值為newCh[0],表示當(dāng)前newCh比較隊(duì)列的初始節(jié)點(diǎn)
??newEnode:初始值為newCh[newEIdx],表示當(dāng)前newCh比較隊(duì)列的末尾節(jié)點(diǎn)
??每一輪的
Diff執(zhí)行條件:oldSIdx <= oldEIdx && newSIdx <= newEIdx,也就是說,當(dāng)兩邊的比較有一方的元素已經(jīng)全部比較完畢,那么Diff中止
??初始狀態(tài) :

?? 第1輪Diff 比較:滿足條件【1】 oldCh 第一個(gè)節(jié)點(diǎn)元素是空,執(zhí)行以下步驟, 根據(jù)結(jié)果接著進(jìn)行下一輪比較
??執(zhí)行:
oldSIdx位置加1,oldSnode指向下一個(gè)節(jié)點(diǎn)>oldSnode=[++oldSIdx]

??第1輪Diff 比較結(jié)束后,oldCh 初始記錄點(diǎn)oldSIdx索引+1,由0變?yōu)?code>1,oldSnode指向下一個(gè)節(jié)點(diǎn),由null變?yōu)?code>A。

?? 第2輪Diff 比較:滿足條件【2】 oldCh 最一個(gè)節(jié)點(diǎn)元素是空,,執(zhí)行以下步驟, 根據(jù)結(jié)果接著進(jìn)行下一輪比較
??執(zhí)行:
oldEIdx位置減1,oldEnode指向上一個(gè)節(jié)點(diǎn)>oldEnode=[--oldEIdx]

??第2輪Diff 比較結(jié)束后,oldCh 末尾記錄點(diǎn)oldEIdx索引-1,由8變?yōu)?code>7,oldEnode指向下一個(gè)節(jié)點(diǎn),由null變?yōu)?code>G。

?? 第3Diff 輪比較:滿足條件【3】 newCh 第一個(gè)節(jié)點(diǎn)元素是空,執(zhí)行以下步驟, 根據(jù)結(jié)果接著進(jìn)行下一輪比較
??執(zhí)行:
newSIdx位置加1,newSnode指向下一個(gè)節(jié)點(diǎn)>newSnode=[++newSIdx]

??第3輪Diff 比較結(jié)束后,newCh 初始記錄點(diǎn)newSIdx索引+1,由0變?yōu)?code>1,newSnode指向下一個(gè)節(jié)點(diǎn),由null變?yōu)?code>A。

?? 第4輪Diff 比較:滿足條件【4】 newCh 最一個(gè)節(jié)點(diǎn)元素是空,執(zhí)行以下步驟, 根據(jù)結(jié)果接著進(jìn)行下一輪比較
??執(zhí)行:
newEIdx位置減1,newEnode指向上一個(gè)節(jié)點(diǎn)>newEnode=[--newEIdx]

??第4輪Diff 比較結(jié)束后,newCh 末尾記錄點(diǎn)newEIdx索引-1,由10變?yōu)?code>9,newEnode指向下一個(gè)節(jié)點(diǎn),由null變?yōu)?code>G。

?? 第5輪Diff 比較:滿足條件【5】 oldCh 與 newCh 第一個(gè)節(jié)點(diǎn)元素相同,執(zhí)行以下步驟, 根據(jù)結(jié)果接著進(jìn)行下一輪比較
??執(zhí)行:
??oldSIdx位置加1,oldSnode指向下一個(gè)節(jié)點(diǎn)>oldSnode=[++oldSIdx]
??newSIdx位置加1,newSnode指向下一個(gè)節(jié)點(diǎn)>newSnode=[++newSIdx]

??第5輪Diff 比較結(jié)束后:
??oldCh 初始記錄點(diǎn)oldSIdx索引+1,由1變?yōu)?code>2,oldSnode指向下一個(gè)節(jié)點(diǎn),由A變?yōu)?code>B。
??newCh 初始記錄點(diǎn)newSIdx索引+1,由1變?yōu)?code>2,newSnode指向下一個(gè)節(jié)點(diǎn),由A變?yōu)?code>F。

?? 第6輪Diff 比較:滿足條件【6】 oldCh 與 newCh 最后一個(gè)節(jié)點(diǎn)元素相同,執(zhí)行以下步驟, 根據(jù)結(jié)果接著進(jìn)行下一輪比較
??執(zhí)行:
??oldEIdx位置減1,oldEnode指向上一個(gè)節(jié)點(diǎn)>oldEnode=[--oldEIdx]
??newEIdx位置減1,newEnode指向上一個(gè)節(jié)點(diǎn)>newEnode=[--newEIdx]

??第6輪Diff 比較結(jié)束后:
??oldCh 末尾記錄點(diǎn)oldEIdx索引-1,由7變?yōu)?code>6,oldEnode指向上一個(gè)節(jié)點(diǎn),由G變?yōu)?code>F。
??newCh 末尾記錄點(diǎn)newEIdx索引-1,由9變?yōu)?code>8,newEnode指向上一個(gè)節(jié)點(diǎn),由G變?yōu)?code>B。

?? 看到這里,不知道各位有沒有發(fā)現(xiàn),每一輪的比較,在滿足
Diff算法的前 6 種判斷條件下,父節(jié)點(diǎn)parentElm是沒有發(fā)生任何變化的,那么,接下來就是見證奇跡的時(shí)刻!
?? 第7輪Diff 比較:滿足條件【7】 oldCh 第一個(gè)節(jié)點(diǎn)元素與 newCh 最后一個(gè)節(jié)點(diǎn)元素相同,執(zhí)行以下步驟, 根據(jù)結(jié)果接著進(jìn)行下一輪比較
??執(zhí)行:
??我們首先將當(dāng)前的oldSnode(B)元素移動(dòng)插入到當(dāng)前oldEnode(F)元素的后面
??oldSIdx位置加1,oldSnode指向下一個(gè)節(jié)點(diǎn)>oldSnode=[++oldSIdx]
??newEIdx位置減1,newEnode指向上一個(gè)節(jié)點(diǎn)>newEnode=[--newEIdx]

??第7輪Diff 比較結(jié)束后:
??parentElm更新DOM,將當(dāng)前的oldSnode(B)元素移動(dòng)插入到當(dāng)前oldEnode(F)元素的后面
??oldCh 初始記錄點(diǎn)oldSIdx索引+1,由2變?yōu)?code>3,oldSnode指向下一個(gè)節(jié)點(diǎn),由B變?yōu)?code>C。
??newCh 末尾記錄點(diǎn)newEIdx索引-1,由8變?yōu)?code>7,newEnode指向上一個(gè)節(jié)點(diǎn),由B變?yōu)?code>E。

?? 第8輪Diff 比較:滿足條件【8】 oldCh 最后一個(gè)節(jié)點(diǎn)元素與 newCh 第一個(gè)節(jié)點(diǎn)元素相同,執(zhí)行以下步驟, 根據(jù)結(jié)果接著進(jìn)行下一輪比較
??執(zhí)行:
??我們首先將當(dāng)前的oldEnode(F)元素插入到當(dāng)前oldSnode(C)元素的前面
??oldEIdx位置減1,oldEnode指向上一個(gè)節(jié)點(diǎn)>oldEnode=[--oldEIdx]
??newSIdx位置加1,newSnode指向下一個(gè)節(jié)點(diǎn)>newSnode=[++newSIdx]

??第8輪Diff 比較結(jié)束后:
??parentElm更新DOM,將當(dāng)前的oldEnode(F)元素插入到當(dāng)前oldSnode(C)元素的前面
??oldCh 末尾記錄點(diǎn)oldEIdx索引-1,由6變?yōu)?code>5,oldEnode指向上一個(gè)節(jié)點(diǎn),由F變?yōu)?code>E。
??newCh 初始記錄點(diǎn)newSIdx索引+1,由2變?yōu)?code>3,newSnode指向下一個(gè)節(jié)點(diǎn),由F變?yōu)?code>E。

?? 第9輪Diff 比較:滿足條件【6】 oldCh 與 newCh 最后一個(gè)節(jié)點(diǎn)元素相同,執(zhí)行以下步驟, 根據(jù)結(jié)果接著進(jìn)行下一輪比較
??執(zhí)行:
??oldEIdx位置減1,oldEnode指向上一個(gè)節(jié)點(diǎn)>oldEnode=[--oldEIdx]
??newEIdx位置減1,newEnode指向上一個(gè)節(jié)點(diǎn)>newEnode=[--newEIdx]

??第9輪Diff 比較結(jié)束后:
??oldCh 末尾記錄點(diǎn)oldEIdx索引-1,由5變?yōu)?code>4,oldEnode指向上一個(gè)節(jié)點(diǎn),由E變?yōu)?code>D。
??newCh 末尾記錄點(diǎn)newEIdx索引-1,由7變?yōu)?code>6,newEnode指向上一個(gè)節(jié)點(diǎn),由E變?yōu)?code>I。

?? 看到這里,經(jīng)過以上每一輪的比較,基本上前 8 種
Diff條件都已經(jīng)差不多全部執(zhí)行了,接下來的就是我們找出差異之后的DOM更新了。
?? 第10輪Diff 比較:前 8 種Diff條件都不滿足,則需要新增節(jié)點(diǎn)
?? 執(zhí)行以下步驟, 根據(jù)結(jié)果接著進(jìn)行下一輪比較
??執(zhí)行:
??parentElm更新DOM,將當(dāng)前的oldEnode(E)元素插入到當(dāng)前oldSnode(C)元素的前面
??newSIdx位置+1,newSnode指向下一個(gè)節(jié)點(diǎn)>newSnode=[++newSIdx]

??第10輪Diff 比較結(jié)束后:
??parentElm更新DOM,將當(dāng)前的oldEnode(E)元素插入到當(dāng)前oldSnode(C)元素的前面
??newCh 初始記錄點(diǎn)newSIdx索引+1,由3變?yōu)?code>4,newSnode指向下一個(gè)節(jié)點(diǎn),由E變?yōu)?code>M。

?? 第11輪Diff 比較:前 8 種Diff條件都不滿足,則需要新增節(jié)點(diǎn)
?? 執(zhí)行以下步驟,根據(jù)結(jié)果接著進(jìn)行下一輪比較
??執(zhí)行:
??parentElm更新DOM,將當(dāng)前的oldEnode(M)元素插入到當(dāng)前oldSnode(C)元素的前面
??newSIdx位置+1,newSnode指向下一個(gè)節(jié)點(diǎn)>newSnode=[++newSIdx]

??第11輪Diff 比較結(jié)束后:
??parentElm更新DOM,將當(dāng)前的oldEnode(M)元素插入到當(dāng)前oldSnode(C)元素的前面
??newCh 初始記錄點(diǎn)newSIdx索引+1,由4變?yōu)?code>5,newSnode指向下一個(gè)節(jié)點(diǎn),由M變?yōu)?code>O。

;
?? 第12輪Diff 比較:前 8 種Diff條件都不滿足,則需要新增節(jié)點(diǎn)
?? 執(zhí)行以下步驟, 根據(jù)結(jié)果接著進(jìn)行下一輪比較
??執(zhí)行:
??parentElm更新DOM,將當(dāng)前的oldEnode(O)元素插入到當(dāng)前oldSnode(C)元素的前面
??newSIdx位置+1,newSnode指向下一個(gè)節(jié)點(diǎn)>newSnode=[++newSIdx]

??第12輪Diff 比較結(jié)束后:
??parentElm更新DOM,將當(dāng)前的oldEnode(O)元素插入到當(dāng)前oldSnode(C)元素的前面
??newCh 初始記錄點(diǎn)newSIdx索引+1,由5變?yōu)?code>6,newSnode指向下一個(gè)節(jié)點(diǎn),由M變?yōu)?code>O。

?? 第13輪Diff 比較:前 8 種Diff條件都不滿足,則需要新增節(jié)點(diǎn)
?? 執(zhí)行以下步驟, 根據(jù)結(jié)果接著進(jìn)行下一輪比較
??執(zhí)行:
??parentElm更新DOM,將當(dāng)前的oldEnode(I)元素插入到當(dāng)前oldSnode(C)元素的前面
??newSIdx位置+1,newSnode指向下一個(gè)節(jié)點(diǎn)>newSnode=[++newSIdx]

??第13輪Diff 比較結(jié)束后:
??parentElm更新DOM,將當(dāng)前的oldEnode(I)元素插入到當(dāng)前oldSnode(C)元素的前面
??newCh 初始記錄點(diǎn)newSIdx索引+1,由6變?yōu)?code>7,newSnode指向下一個(gè)節(jié)點(diǎn),由I變?yōu)?code>E。
??此時(shí) newSIdx > newEIdx,已經(jīng)不能滿足下一輪Diff 比較的條件,Diff 比較比較結(jié)束

??經(jīng)過13輪的新舊子節(jié)點(diǎn)Diff比較,parentElm通過將舊節(jié)點(diǎn)移動(dòng),新節(jié)點(diǎn)增加,進(jìn)行了DOM的更新,接下來就是根據(jù)最終oldCh 與newCh剩余情況進(jìn)行parentElm的刪除或者新增。
??如果當(dāng)前newCh[newSIdx,newEIdx]有剩余,說明還有需要新增的元素,那么我們根據(jù)剩余的節(jié)點(diǎn)區(qū)間,依次插入到最終比較的newEnode后面。
??如果當(dāng)前oldCh[oldSIdx,oldEIdx]有剩余,說明這些元素是需要?jiǎng)h除的,那么我們根據(jù)剩余的節(jié)點(diǎn)區(qū)間,依次刪除。


3.0 代碼模擬過程
基于Snabbdom,通過數(shù)組來表示DOM節(jié)點(diǎn)元素,這里我稍微改造了一下,基于數(shù)組操作來模擬DOM的更新
/**
* author:Echonessy
* des:
* date:2020.07.05
* target: Diff 算法模擬
* */
let oldCh = [null,"A","B","C","D","E","F","G",null];
let newCh = [null,"A","F","E","M","O","I","E","B","G",null];
// let oldCh = [null,"A","B","C","D","E","F","G",null];
// let newCh = [null,"A","F","C","D","E","M","O","I","E","B","G",null];
let parentElm = oldCh.slice();
diff(parentElm,oldCh,newCh);
// 判斷節(jié)點(diǎn)是否相同
export function same(vnode1, vnode2) {
return vnode1 === vnode2
}
// 模擬DOM節(jié)點(diǎn)插入與移動(dòng)
function insertBerfore(parent,newNode,referenceNode,order) {
switch (order) {
case 'left':parent.splice(parent.indexOf(referenceNode),0,newNode);parent.splice(parent.indexOf(newNode.split('-')[1]),1);break;
case 'right':parent.splice(parent.indexOf(referenceNode),0,newNode);parent.splice(parent.lastIndexOf(newNode.split('-')[1]),1);break;
case 'diff':parent.splice(parent.indexOf(referenceNode.indexOf('-')!=-1?referenceNode.split('-')[1]:referenceNode),0,newNode);break;
case 'add':parent.splice(parent.lastIndexOf(referenceNode),0,newNode);break;
}
}
// 移除vNode
export function removeVnodes(parentElm,vnodes,startIdx,endIdx){
// 循環(huán)vnodes
for (; startIdx <= endIdx; ++startIdx) {
let ch = vnodes[startIdx];
if (ch != null) {
var index = parentElm.indexOf(ch);
parentElm.splice(index, 1)
}
}
}
// 添加vNode
function addVnodes(parentElm,before,vnodes,startIdx,endIdx) {
for (; startIdx <= endIdx; ++startIdx) {
const ch = vnodes[startIdx];
if (ch != null) {
insertBerfore(parentElm,'new-'+ch,before,'add')
}
}
}
// diff 過程
function diff(parentElm,oldCh,newCh) {
console.log('初始')
console.log(oldCh)
console.log(newCh)
console.log(parentElm)
let oldSIdx = 0, newSIdx = 0;
let oldEIdx = oldCh.length - 1;
let oldSnode = oldCh[0];
let oldEnode = oldCh[oldEIdx];
let newEIdx = newCh.length - 1;
let newStnode = newCh[0];
let newEnode = newCh[newEIdx];
let conunt = 0; // 計(jì)數(shù)器,記錄循環(huán)次數(shù)
// 兩數(shù)組比較結(jié)束之前,循環(huán)調(diào)用Diff
while (oldSIdx <= oldEIdx && newSIdx <= newEIdx){
if (oldSnode == null) {
oldSnode = oldCh[++oldSIdx];
} else if (oldEnode == null) {
oldEnode = oldCh[--oldEIdx];
} else if (newStnode == null) {
newStnode = newCh[++newSIdx];
} else if (newEnode == null) {
newEnode = newCh[--newEIdx];
} else if (same(oldSnode, newStnode)){
oldSnode = oldCh[++oldSIdx];
newStnode = newCh[++newSIdx];
} else if (same(oldEnode, newEnode)) {
oldEnode = oldCh[--oldEIdx];
newEnode = newCh[--newEIdx];
}else if (same(oldSnode, newEnode)) {
insertBerfore(parentElm,'old-'+oldSnode,oldCh[oldEIdx+1],'left');
oldSnode = oldCh[++oldSIdx];
newEnode = newCh[--newEIdx];
}else if (same(oldEnode, newStnode)) {
insertBerfore(parentElm,'old-'+oldEnode,oldCh[oldSIdx],'right');
oldEnode = oldCh[--oldEIdx];
newStnode = newCh[++newSIdx];
} else {
insertBerfore(parentElm,'new-'+newStnode,oldCh[oldSIdx],'diff');
newStnode = newCh[++newSIdx];
}
console.log('------------------------------------------------------------------')
console.log('第'+ (++conunt) + '次對(duì)比,oldSIdx:'+oldSIdx + ' oldEIdx:' +oldEIdx + ' newSIdx:'+newSIdx+ ' newEIdx:'+newEIdx )
console.log(oldCh.slice(oldSIdx,oldEIdx+1))
console.log(newCh.slice(newSIdx,newEIdx+1))
console.log(parentElm);
}
// 最后比較完成之后
if (oldSIdx <= oldEIdx || newSIdx <= newEIdx) {
console.log('Diff 對(duì)比結(jié)束')
console.log(oldCh)
console.log(newCh)
if (oldSIdx > oldEIdx) {
// 'old-'用來模擬區(qū)分新舊節(jié)點(diǎn)
console.log('新增節(jié)點(diǎn)')
let before =newCh[newEIdx+1] == null ? null : 'old-'+ newCh[newEIdx+1];
addVnodes(parentElm, before, newCh, newSIdx, newEIdx);
} else {
console.log('移除節(jié)點(diǎn)')
removeVnodes(parentElm, oldCh, oldSIdx, oldEIdx);
}
console.log('模擬DOM更新完成')
console.log(parentElm);
}
}
4.0 附件
Snabbdom 源代碼地址:https://github.com/snabbdom/snabbdom