淺析 Snabbdom 中 vnode 和 diff 算法
本文首發於政採雲前端團隊博客：淺析 Snabbdom 中 vnode 和 diff 算法
https://www.zoo.team/article/snabbdom-vnode
一、一些必要的概念解釋
1、什麼是虛擬 DOM
目前前端使用最多的就是 vue 或 react 了，我們在學習這兩個框架的過程中，總有一個繞不開的話題：vnode，也就是虛擬 DOM。什麼是虛擬 DOM，引用一段 vue 官方的解釋就是：
“
一個用 JavaScript 生成名爲 Virtual Dom 的 DOM 副本。
也就是說，虛擬 DOM** 只是一個普通的 js 對象**。我們都知道，對於 DOM 頻繁的進行增刪改查，成本很高，既然虛擬 DOM 只是一個 js 對象，那我們用操作對象的方式來代替操作 DOM，最後一次性的更改 DOM，那麼一定程度上就能使得我們的 UI 更新更高效。
2、什麼是 diff 算法
既然虛擬 DOM 的最終任務就是用計算出來的結果來修改 DOM，那麼更新 DOM 還是不更新 DOM，怎麼更新 DOM。這就需要藉助 diff 算法來給出最終答案。
“
diff 算法是用來計算新老 DOM 之間差異性的一種計算算法。
3、Snabbdom 是什麼
“
Snabbdom 是一個虛擬 DOM 庫，專注提供簡單、模塊性的體驗，以及強大的功能和性能。
可能很多人都沒聽說過這個庫，其實 vue 中虛擬 DOM 這一塊就是借鑑的 Snabbdom，但是，它相比 vue 更加簡單和純粹，所以學習 Snabbdom 也能幫助我們理解 vue 中虛擬 DOM 相關的知識。
二、Snabbdom 中 diff 算法的源碼解析
1、Snabbdom 的使用
下面先來看看 Snabbdom 的簡單的使用
import {
init,
classModule,
propsModule,
styleModule,
eventListenersModule,
h,
} from "snabbdom";
const patch = init([
// Init patch function with chosen modules
classModule, // makes it easy to toggle classes
propsModule, // for setting properties on DOM elements
styleModule, // handles styling on elements with support for animations
eventListenersModule, // attaches event listeners
]);
// 創建一個 vnode
var vnode = h('div#container.two.classes', {on: {click: someFn}}, [
h('span', {style: {fontWeight: 'bold'}}, '這只是普通文本'),
' and this is just normal text',
h('a', {props: {href: '/foo'}}, '這是一個鏈接!')
]);
// 選擇容器
var container = document.getElementById('container');
// 將 vnode patch 到容器中
patch(container, vnode);
// 生成一個新的 vnode
var newVnode = h('div#container.two.classes', {on: {click: anotherEventHandler}}, [
h('span', {style: {fontWeight: 'normal', fontStyle: 'italic'}}, '現在是斜體類型文本'),
' and this is still just normal text',
h('a', {props: {href: '/bar'}}, '這是一個鏈接!')
]);
// 用新 DOM 替換老 DOM
patch(vnode, newVnode);上面的 demo 演示的流程就是：首先創建一個 vnode，patch 到選擇的容器中，然後再創建一個新的 vnode，用老的 vnode 去替換新的 vnode。這裏要注意的是，patch 方法的第一個參數，可以是一個 vnode 類型，也可以是一個 Element 類型，下面會介紹對這兩種參數類型的處理。
其實上面這種初始化容器中的 DOM 和新老 DOM 的替換，我們在使用 vue 的過程，也是大量用到的，只不過 vue 替我們解決了繁瑣的計算過程。
2、vnode 的生成過程
首先我們先來看看 vnode 生成過程，也就是下面這一塊：
var vnode = h('div#container.two.classes', {on: {click: someFn}}, [
h('span', {style: {fontWeight: 'bold'}}, '這是加粗的類型'),
' and this is just normal text',
h('a', {props: {href: '/foo'}}, '這是一個鏈接!')
]);上面的核心點就是 h 函數，它接受三個參數，第一個是標籤，第二個是屬性，第三個是子節點，其中子節點也可以是一個 h 函數的返回值。
下面貼上 h 函數的源碼：
export function h(sel: any, b?: any, c?: any): VNode {
let data: VNodeData = {};
let children: any;
let text: any;
let i: number;
if (c !== undefined) {
if (b !== null) {
data = b;
}
if (is.array(c)) {
children = c;
} else if (is.primitive(c)) {
text = c.toString();
} else if (c && c.sel) {
children = [c];
}
} else if (b !== undefined && b !== null) {
// c 是 undefined，b 有可能是 children 類型
if (is.array(b)) {
children = b;
} else if (is.primitive(b)) {
text = b.toString();
} else if (b && b.sel) {
children = [b];
} else {
data = b;
}
}
if (children !== undefined) {
for (i = 0; i < children.length; ++i) {
// 這裏 children 有可能是一個 h 函數的返回值，也有可能是一個 text 文本
if (is.primitive(children[i]))
children[i] = vnode(
undefined,
undefined,
undefined,
children[i],
undefined
);
}
}
// 對於 svg 標籤的處理
if (
sel[0] === "s" &&
sel[1] === "v" &&
sel[2] === "g" &&
(sel.length === 3 || sel[3] === "." || sel[3] === "#")
) {
addNS(data, children, sel);
}
return vnode(sel, data, children, text, undefined);
}上面這段代碼首先是做了一些函數傳參的處理，它允許傳入的參數更加靈活。其次，調用 vnode 方法生成生成子節點的 vnode 和自己本身的 vnode，下面再接着看一下 vnode 函數的實現邏輯。
export function vnode(
sel: string | undefined,
data: any | undefined,
children: Array<VNode | string> | undefined,
text: string | undefined,
elm: Element | Text | undefined
): VNode {
const key = data === undefined ? undefined : data.key;
return { sel, data, children, text, elm, key };
}vnode 函數的實現的函數很簡單，就是返回一個 js 對象，所以本質上一個 vnode 就是一個如下結構的 js 對象。
{
sel: string | undefined;
data: any | undefined;
children: Array<VNode | string> | undefined,
text: string | undefined,
elm: Element | Text | undefined,
key: string | undefined
}每一個 children 也可能是一個 vnode，這樣就組裝成了一個 vnode 樹形結構。
3、patch 過程
瞭解完了 vnode 的生成過程，我們接下來就是將 vnode patch 到容器中，也就是下面的這兩段代碼。
patch(container, vnode); // 將 vnode patch 到容器中和
patch(vnode, newVnode); // 用新 DOM 替換老 DOMpatch 函數其實就是 init 方法的返回值，所以找到 init 的源碼：
export function init(modules: Array<Partial<Module>>, domApi?: DOMAPI) {
// dom 操作 api
const api: DOMAPI = domApi !== undefined ? domApi : htmlDomApi;
function emptyNodeAt() {}
function createRmCb() {}
// 根據 vnode 創建一個 dom 樹
function createElm() {}
function addVnodes() {}
function invokeDestroyHook() {}
function removeVnodes() {}
function updateChildren() {}
function patchVnode() {}
return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
let elm: Node, parent: Node;
// 如果不是 vnode(第一次調用 patch 時)，
// 那麼就是 Element 類型，直接創建一個空對象
// 空對象的 elm 值等於 oldVnode
if (!isVnode(oldVnode)) {
oldVnode = emptyNodeAt(oldVnode);
}
// 如果滿足 sameVnode
if (sameVnode(oldVnode, vnode)) {
patchVnode(oldVnode, vnode, insertedVnodeQueue);
} else {
elm = oldVnode.elm!;
parent = api.parentNode(elm) as Node;
createElm(vnode);
if (parent !== null) {
api.insertBefore(parent, vnode.elm!, api.nextSibling(elm));
removeVnodes(parent, [oldVnode], 0, 0);
}
}
return vnode;
};
}這裏有一部分關於 hooks 的執行時機的代碼，由於本文主要是研究 diff 過程的，所以關於 hooks 的執行邏輯，代碼中就沒有貼進來了，感興趣的同學可以研究下官方的源碼。可以看到上面的代碼就是返回 patch 函數，當我們調用 patch(container, vnode) 或 patch(vnode, newVnode) 的時候，就會執行該方法；
再看一下 patch 函數的實現邏輯：
1、對 vnode，也就是第一個參數類型做了判斷，因爲 vnode 有可能是一個 VNode 實例，也有可能是一個 Element 實例。
2、比較新老節點的根節點是否相同，這裏比較邏輯的是判斷新老節點的 key、sel 和 data.is 這三者都相等，才認爲相同。
function sameVnode(vnode1: VNode, vnode2: VNode): boolean {
const isSameKey = vnode1.key === vnode2.key;
const isSameIs = vnode1.data?.is === vnode2.data?.is;
const isSameSel = vnode1.sel === vnode2.sel;
return isSameSel && isSameKey && isSameIs;
}3、相同的邏輯我們先跳過，先看 sameVnode(oldVnode, vnode) 返回 false 的情況。先調用 createElm(vnode, insertedVnodeQueue) 創建 DOM 樹，然後再將新創建的 DOM 樹直接 append 到容器的父節點下，直接替換子節點。
最後，爲了幫助大家理解整個 patch 的過程，我用一張圖來描述這個過程：
4、新老節點的 diff
上面 patch 函數的實現邏輯中，當 sameVnode(oldVnode, vnode) 返回 true 時，會執行 patchVnode 方法，patchVnode 其實就是用來比較新老節點的差異，計算出一個新的節點的。一起來看看 patchVnode 的比較實現：
function patchVnode(
oldVnode: VNode,
vnode: VNode,
insertedVnodeQueue: VNodeQueue
) {
const elm = (vnode.elm = oldVnode.elm)!;
const oldCh = oldVnode.children as VNode[];
const ch = vnode.children as VNode[];
// 如果新老節點相等，則不用替換
if (oldVnode === vnode) return;
// 如果新節點的子節點不是 textNode 類型。
if (isUndef(vnode.text)) {
if (isDef(oldCh) && isDef(ch)) {
// 如果新節點的子節點類型和老節點的子節點類型都是 children 類型
if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);
} else if (isDef(ch)) {
// 如果新節點的子節點類型是 children 類型，老節點的類型是 text 類型
if (isDef(oldVnode.text)) api.setTextContent(elm, "");
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
} else if (isDef(oldCh)) {
// 如果老節點的子節點類型是 children 類型，新節點沒有子節點
removeVnodes(elm, oldCh, 0, oldCh.length - 1);
} else if (isDef(oldVnode.text)) {
// 如果老節點的子節點類型是 text 類型，新節點沒有子節點
api.setTextContent(elm, "");
}
} else if (oldVnode.text !== vnode.text) {
// 如果新節點的子節點是 text 類型。
if (isDef(oldCh)) {
removeVnodes(elm, oldCh, 0, oldCh.length - 1);
}
api.setTextContent(elm, vnode.text!);
}
}這裏首先是判斷 oldVnode 與 vnode 是否相等，如果相等，那就不用繼續比較了；如果不相等，先執行新節點的 update 生命週期。因爲根節點通過 sameVnode 方法比較過後， Snabbdom 就認爲 vnode 和 oldVnode 的根節點是相等的，就不用更新根節點了。所以接下來就直接處理子節點的更新，這裏爲了方便大家理解，我先放一張子節點的比較的流程圖。
上面我們在生成 vnode 的時候，根據節點類型，分別給 text 和 children 的值做了計算。所以，一個 vnode 的子節點 text 和 children 屬性不可能同時有值。所以根據流程圖，子節點對比的過程如下：
1、新節點的 children 爲空，直接拿新節點的 text 和老節點的 text (不存在則爲空) 做比較，相等不動，不相等直接替換。
2、新節點的節點 children 不爲空，老節點的 children 爲空，直接用新節點替換老節點。
3、新節點的 children 和老節點的 children 皆不爲空，執行 updateChildren()。
5、子節點的深度 diff
上面在新節點的 children 和老節點的 children 皆不爲空的情況下，執行 updateChildren(elm, oldCh, ch, insertedVnodeQueue) 進行了深度比較，下面再來分析子節點的比較。
function updateChildren(
parentElm: Node,
oldCh: VNode[],
newCh: VNode[],
insertedVnodeQueue: VNodeQueue
) {
let oldStartIdx = 0;
let newStartIdx = 0;
let oldEndIdx = oldCh.length - 1;
let oldStartVnode = oldCh[0];
let oldEndVnode = oldCh[oldEndIdx];
let newEndIdx = newCh.length - 1;
let newStartVnode = newCh[0];
let newEndVnode = newCh[newEndIdx];
let oldKeyToIdx: KeyToIndexMap | undefined;
let idxInOld: number;
let elmToMove: VNode;
let before: any;
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVnode == null) {
// 老節點開始位置爲 null
oldStartVnode = oldCh[++oldStartIdx];
} else if (oldEndVnode == null) {
// 老節點結束位置爲 null
oldEndVnode = oldCh[--oldEndIdx];
} else if (newStartVnode == null) {
// 新節點開始位置爲 null
newStartVnode = newCh[++newStartIdx];
} else if (newEndVnode == null) {
// 新節點結束位置爲 null
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldStartVnode, newStartVnode)) {
// 老節點開始位置與新節點開始位置 diff
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
} else if (sameVnode(oldEndVnode, newEndVnode)) {
// 老節點結束位置與新節點結束位置 diff
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldStartVnode, newEndVnode)) {
// 老節點結束位置與新節點開始位置 diff
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
api.insertBefore(
parentElm,
oldStartVnode.elm!,
api.nextSibling(oldEndVnode.elm!)
);
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldEndVnode, newStartVnode)) {
// 老節點開始位置與新節點結束位置 diff
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
} else {
if (oldKeyToIdx === undefined) {
// 將老節點轉換成 map 結構
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
}
// 在 map 中找新節點的開始位置
idxInOld = oldKeyToIdx[newStartVnode.key as string];
if (isUndef(idxInOld)) {
// 如果沒找到，新節點開始位置是新元素
api.insertBefore(
parentElm,
createElm(newStartVnode, insertedVnodeQueue),
oldStartVnode.elm!
);
} else { // 如果找到了，則比較兩個節點的選擇器是否相等
elmToMove = oldCh[idxInOld];
if (elmToMove.sel !== newStartVnode.sel) {
// 如果不相等，新節點開始位置是新元素
api.insertBefore(
parentElm,
createElm(newStartVnode, insertedVnodeQueue),
oldStartVnode.elm!
);
} else { // 如果相等，則認爲是相同的元素
patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
oldCh[idxInOld] = undefined as any;
api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);
}
}
// 新節點開始位置右移
newStartVnode = newCh[++newStartIdx];
}
}
if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
// 如果遍歷完了
if (oldStartIdx > oldEndIdx) {
// 如果有殘餘的新節點未參與 diff，則全部 append 到父元素中
before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm;
addVnodes(
parentElm,
before,
newCh,
newStartIdx,
newEndIdx,
insertedVnodeQueue
);
} else {
// 如果有殘餘的老節點未參與 diff，則全部移除
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
}
}
}子節點的 diff 應該算是整個整個 diff 過程當中最複雜的環節了，所以還是按照慣例，先上圖：
結合代碼和流程圖來看：
1、首先是判斷新老節點的開始和結束位置是否爲 null；如果爲 null，則將對應節點的位置左移（開始位置）或者右移（結束位置）。
2、然後依次拿新節點的開始位置與老節點的開始位置、新節點的結束位置與老節點的結束位置、新節點的結束位置與老節點的開始位置和新節點的開始位置與老節點的結束位置做對比，對比的邏輯依然是前面提到的 sameVnode 函數。如果匹配到，則再次進入 patchVnode 中，並且，對應的位置分別左移（開始位置）或右移（結束位置）；如果匹配不到，則在所有老的子節點中尋找新節點開始位置的 vnode。
3、當循環條件 oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx 不滿足時，檢查新子節點中是否有殘餘的子節點未參與 diff 過程，如果有，則插入所有殘餘新子節點；檢查老的子節點，是否有殘餘的子節點未參與 diff 過程，如果有，則刪除所有殘餘老子節點。
三、總結
由於本文只是討論 Snabbdom 的 vnode 的生成和 diff 過程，其他還有很多地方沒有深挖，但是建議大家有空可以去看看 Snabbdom 的源碼，裏面有很多非常棒的設計思路值得我們去學習的。
四、參考
- Snabbdom 官方倉庫 (https://github.com/snabbdom/snabbdom/tree/master)
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/K5apaEp1LuLEnrBKB47Csw