前言
DOM是很慢的。真正的 DOM 元素非常龐大埂蕊，這是因為標(biāo)準(zhǔn)就是這么設(shè)計的往弓。而且操作它們的時候你要小心翼翼疏唾，輕微的觸碰可能就會導(dǎo)致頁面重排產(chǎn)生回流重繪，這可是殺死性能的罪魁禍?zhǔn)住?/p>
Virtual Dom的原理是用 JavaScript 對象表示 DOM 信息和結(jié)構(gòu)函似，當(dāng)狀態(tài)變更的時候槐脏，重新渲染這個 JavaScript 的對象結(jié)構(gòu)。然后通過新渲染的對象樹去和舊的樹進行對比使用一個diff算法計算差異撇寞，記錄下來的不同就是我們需要對頁面真正的 DOM 操作顿天，然后把它們應(yīng)用在真正的 DOM 樹上，從而減少了頁面的回流和重繪次數(shù)蔑担。
Vue選擇的virtual dom庫是snabbdom牌废，本文是對這個庫的源代碼進行解析，核心會放在diff算法上钟沛。
代碼
項目地址：snabbdom
代碼是typescript畔规，不過我解析的時候會說一些補充的東西讓讀者不會出現(xiàn)因為是typescript所以看不懂的情況。
解析
解析我會從三個大方向上來說恨统，第一個是js模擬的dom節(jié)點vnode的結(jié)構(gòu)叁扫，第二個是diff算法，第三個是有了diff如何打patch的畜埋。
vnode結(jié)構(gòu)(用JS對象模擬DOM樹)
vnode的定義在項目中src文件夾的vnode.ts上
import {Hooks} from './hooks';
import {AttachData} from './helpers/attachto'
import {VNodeStyle} from './modules/style'
import {On} from './modules/eventlisteners'
import {Attrs} from './modules/attributes'
import {Classes} from './modules/class'
import {Props} from './modules/props'
import {Dataset} from './modules/dataset'
import {Hero} from './modules/hero'
export type Key = string | number;
export interface VNode {
sel: string | undefined;
data: VNodeData | undefined;
children: Array<VNode | string> | undefined;
elm: Node | undefined;
text: string | undefined;
key: Key | undefined;
}
export interface VNodeData {
props?: Props;
attrs?: Attrs;
class?: Classes;
style?: VNodeStyle;
dataset?: Dataset;
on?: On;
hero?: Hero;
attachData?: AttachData;
hook?: Hooks;
key?: Key;
ns?: string; // for SVGs
fn?: () => VNode; // for thunks
args?: Array<any>; // for thunks
[key: string]: any; // for any other 3rd party module
}
export function vnode(sel: string | undefined,
data: any | undefined,
children: Array<VNode | string> | undefined,
text: string | undefined,
elm: Element | Text | undefined): VNode {
let key = data === undefined ? undefined : data.key;
return {sel: sel, data: data, children: children,
text: text, elm: elm, key: key};
}
export default vnode;
代碼中定義了兩個interface莫绣，VNode和VNodeData，暴露了一個vnode的構(gòu)造函數(shù)
vnode對象屬性
vnode對象有6個屬性
sel 可以是custom tag,可以是'div','span',etc,代表這個virtual dom的tag name
data, virtual dom數(shù)據(jù),它們與dom element的prop悠鞍、attr的語義類似对室。但是virtual dom包含的數(shù)據(jù)可以更靈活。比如利用./modules/class.js插件,我們在data里面輕松toggle一個類名h('p', {class: {'hide': hideIntro}})
children, 對應(yīng)element的children,但是這是vdom的children咖祭。vdom的實現(xiàn)重點就在對children的patch上
text, 對應(yīng)element.textContent,在children里定義一個string,那么我們會為這個string創(chuàng)建一個textNode
elm, 對dom element的引用
key 用于提示children patch過程,隨后面詳細說明
vnode的創(chuàng)建與渲染
在接下來的說明之前先介紹一個豆知識掩宜，在vue文檔中，同時在這個snabbdom中我們都會看到有個h函數(shù)么翰，這個函數(shù)我之前一直沒理解是什么意思牺汤。
wthat is 'h'
It comes from the term "hyperscript", which is commonly used in many virtual-dom implementations. "Hyperscript" itself stands for "script that generates HTML structures" because HTML is the acronym for "hyper-text markup language".
所以基本上h函數(shù)的意義差不多就是createElement的意思
在snabbdom里面h函數(shù)創(chuàng)建一個vnode并返回，具體實現(xiàn)就不細說了
diff算法(patch)
之前我們在snabbdom的事例里面看到
var snabbdom = require('snabbdom');
var patch = snabbdom.init([ // Init patch function with chosen modules
require('snabbdom/modules/class').default, // makes it easy to toggle classes
require('snabbdom/modules/props').default, // for setting properties on DOM elements
require('snabbdom/modules/style').default, // handles styling on elements with support for animations
require('snabbdom/modules/eventlisteners').default, // attaches event listeners
]);
var h = require('snabbdom/h').default; // helper function for creating vnodes
var container = document.getElementById('container');
var vnode = h('div#container.two.classes', {on: {click: someFn}}, [
h('span', {style: {fontWeight: 'bold'}}, 'This is bold'),
' and this is just normal text',
h('a', {props: {href: '/foo'}}, 'I\'ll take you places!')
]);
// Patch into empty DOM element – this modifies the DOM as a side effect
patch(container, vnode);
var newVnode = h('div#container.two.classes', {on: {click: anotherEventHandler}}, [
h('span', {style: {fontWeight: 'normal', fontStyle: 'italic'}}, 'This is now italic type'),
' and this is still just normal text',
h('a', {props: {href: '/bar'}}, 'I\'ll take you places!')
]);
// Second `patch` invocation
patch(vnode, newVnode); // Snabbdom efficiently updates the old view to the new state
可以看到patch函數(shù)是snabbdom.init出來的浩嫌，而且傳入的參數(shù)既可以是用h函數(shù)返回的一個vnode又可以是實際的dom元素檐迟，現(xiàn)在我們看看init方法的代碼，一些實現(xiàn)鉤子之類的代碼我們就不看了
// snabbdom的init方法
...
export function init(modules: Array<Partial<Module>>, domApi?: DOMAPI) {
...
return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
let i: number, elm: Node, parent: Node;
const insertedVnodeQueue: VNodeQueue = [];
for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();
if (!isVnode(oldVnode)) {
oldVnode = emptyNodeAt(oldVnode);
}
if (sameVnode(oldVnode, vnode)) {
patchVnode(oldVnode, vnode, insertedVnodeQueue);
} else {
elm = oldVnode.elm as Node;
parent = api.parentNode(elm);
createElm(vnode, insertedVnodeQueue);
if (parent !== null) {
api.insertBefore(parent, vnode.elm as Node, api.nextSibling(elm));
removeVnodes(parent, [oldVnode], 0, 0);
}
}
for (i = 0; i < insertedVnodeQueue.length; ++i) {
(((insertedVnodeQueue[i].data as VNodeData).hook as Hooks).insert as any)(insertedVnodeQueue[i]);
}
for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
return vnode;
};
}
先會傳入一個modules码耐，就是一個模組追迟，這些模組會在一些階段加一些鉤子，以此實現(xiàn)一個模組功能骚腥。說到模組功能我就想起了chartjs的模組敦间。模組為第三方開發(fā)者提供了個擴展程序的一個接口，在chartjs里面它使用的是觀察者模式，在一開始會register各個模組每瞒，通過在圖表創(chuàng)建金闽，更新，銷毀等地方寫了notify來通知各個模組剿骨，以此實現(xiàn)了一個模組功能。
回歸patch埠褪，我們它會先判斷是不是sameVnode(通過vnode的key和sel屬性是不是一樣的來判斷)浓利，如果原來不是同一個key的vnode的話那就沒必要用什么diff了，只能直接創(chuàng)建一個新元素钞速。這里我們專注于看如果是同一key同一sel下的vnode發(fā)送了某些變化之后怎么進行patch操作贷掖。
// patchVnode函數(shù)
function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
let i: any, hook: any;
... prepatch的鉤子我也刪了
const elm = vnode.elm = (oldVnode.elm as Node);
let oldCh = oldVnode.children;
let ch = vnode.children;
if (oldVnode === vnode) return;
...update的鉤子，我刪了
if (isUndef(vnode.text)) {
if (isDef(oldCh) && isDef(ch)) {
if (oldCh !== ch) updateChildren(elm, oldCh as Array<VNode>, ch as Array<VNode>, insertedVnodeQueue);
} else if (isDef(ch)) {
if (isDef(oldVnode.text)) api.setTextContent(elm, '');
addVnodes(elm, null, ch as Array<VNode>, 0, (ch as Array<VNode>).length - 1, insertedVnodeQueue);
} else if (isDef(oldCh)) {
removeVnodes(elm, oldCh as Array<VNode>, 0, (oldCh as Array<VNode>).length - 1);
} else if (isDef(oldVnode.text)) {
api.setTextContent(elm, '');
}
} else if (oldVnode.text !== vnode.text) {
api.setTextContent(elm, vnode.text as string);
}
... postpatch鉤子
}
可以看到主要邏輯里面先做了isUndef(vnode.text)的判斷渴语，因為如果不是文本節(jié)點的話是不會有這個屬性的苹威，如果是文本節(jié)點直接setTextContent就行了，如果不是的話我們還要繼續(xù)看驾凶。
在vnode不是文本節(jié)點的時候做了四個判斷
前三個是判斷vnode和oldVnode是不是都有兒子牙甫，或者一個有一個沒有。
第一種情況如果都有兒子的話會調(diào)用updateChildren然后遞歸的調(diào)用patchVnode函數(shù)调违。
第二種情況vnode有兒子而oldVnode沒有窟哺，那差異就可以直接調(diào)用addVnodes在DOM上插入兒子并更新insertedVnodeQueue記錄了。
第三種情況是vnode沒有兒子而oldVnode有技肩，說明差異是兒子的移除且轨，直接調(diào)用removeVnodes在DOM上移除兒子并更新insertedVnodeQueue。
第四種情況就是這個節(jié)點是個文本節(jié)點虚婿，然后差異是oldVnode有text旋奢，vnode沒有了，直接調(diào)用setTextContent設(shè)置值為空
比較核心的還是前后vnode都有孩子的情況也就是updateChildren里面然痊，在進updateChildren函數(shù)之前我還有一點想說的至朗。
兩個樹的完全的 diff 算法是一個時間復(fù)雜度為 O(n^3) 的問題。但是在前端當(dāng)中玷过，你很少會跨越層級地移動DOM元素爽丹。所以 Virtual DOM 只會對同一個層級的元素進行對比：
updateChildren更新兒子
這段邏輯是主要的diff算法部分，有點復(fù)雜辛蚊，我看了2個多小時還結(jié)合其他資料才理解為什么要這樣寫粤蝎。
先貼一下代碼
function updateChildren(parentElm: Node,
oldCh: Array<VNode>,
newCh: Array<VNode>,
insertedVnodeQueue: VNodeQueue) {
let oldStartIdx = 0, 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: any;
let idxInOld: number;
let elmToMove: VNode;
let before: any;
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVnode == null) {
oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
} else if (oldEndVnode == null) {
oldEndVnode = oldCh[--oldEndIdx];
} else if (newStartVnode == null) {
newStartVnode = newCh[++newStartIdx];
} else if (newEndVnode == null) {
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
} else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
api.insertBefore(parentElm, oldStartVnode.elm as Node, api.nextSibling(oldEndVnode.elm as Node));
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
api.insertBefore(parentElm, oldEndVnode.elm as Node, oldStartVnode.elm as Node);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
} else {
if (oldKeyToIdx === undefined) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
}
idxInOld = oldKeyToIdx[newStartVnode.key as string];
if (isUndef(idxInOld)) { // New element
api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
newStartVnode = newCh[++newStartIdx];
} else {
elmToMove = oldCh[idxInOld];
if (elmToMove.sel !== newStartVnode.sel) {
api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
} else {
patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
oldCh[idxInOld] = undefined as any;
api.insertBefore(parentElm, (elmToMove.elm as Node), oldStartVnode.elm as Node);
}
newStartVnode = newCh[++newStartIdx];
}
}
}
if (oldStartIdx > oldEndIdx) {
before = newCh[newEndIdx+1] == null ? null : newCh[newEndIdx+1].elm;
addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
} else if (newStartIdx > newEndIdx) {
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
}
}
我開始閱讀的時候主要的疑惑點就是這一大坨if else，我們先來考慮一下以下幾種情況
newVnode 5 1 2 3 4
oldVnode 1 2 3 4 5
在代碼中首先會進入
else if (sameVnode(oldEndVnode, newStartVnode))
會先遞歸調(diào)用patchNode對這個子vnode打patch
然后把例子中oldVnode的5插入到1前面
} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
api.insertBefore(parentElm, oldEndVnode.elm as Node, oldStartVnode.elm as Node);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
}
有了個例子之后我們看一下我盜的幾個圖袋马，實際的DOM操作只有下面三種情況
上面這種情況的例子是
newVnode 0 2 3 1
oldVnode 0 1 2 3
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
api.insertBefore(parentElm, oldStartVnode.elm as Node, api.nextSibling(oldEndVnode.elm as Node));
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
}
上面這種情況就是我之前舉的例子
newVnode 0 3 12
oldVnode 0 1 2 3
對應(yīng)代碼
} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
api.insertBefore(parentElm, oldEndVnode.elm as Node, oldStartVnode.elm as Node);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
}
上面的情況的例子是newVnode里面的節(jié)點oldVnode里面沒有
newVnode 0 x 1 2 3
oldVnode 0 1 2 3
對應(yīng)代碼
else {
// 這一塊不用在意初澎，這只是一個根據(jù)key去找index的表
if (oldKeyToIdx === undefined) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
}
// 看看當(dāng)前newStartVnode在不在oldVnode里面
idxInOld = oldKeyToIdx[newStartVnode.key as string];
// 這里就是圖中所示插入新節(jié)點到dom
if (isUndef(idxInOld)) { // New element
api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
newStartVnode = newCh[++newStartIdx];
} else {
// 如果在newStartVnode在oldVnode中，
elmToMove = oldCh[idxInOld];
// 如果已經(jīng)不是一個vnode的東西了，直接新建節(jié)點插入到old頭探針之前
if (elmToMove.sel !== newStartVnode.sel) {
api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
} else {
// 如果這個vnode還能搶救碑宴，遞歸調(diào)用patchVnode软啼，把對應(yīng)的elmToMove插入到old頭探針之前
patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
oldCh[idxInOld] = undefined as any;
api.insertBefore(parentElm, (elmToMove.elm as Node), oldStartVnode.elm as Node);
}
newStartVnode = newCh[++newStartIdx];
}
}
結(jié)束的時候，也就是當(dāng)oldVnode或者newVnode有一個遍歷完的時候
如上圖延柠，如果是old先遍歷完祸挪，則剩余的new里面的肯定要插進來啊
對應(yīng)代碼
if (oldStartIdx > oldEndIdx) {
before = newCh[newEndIdx+1] == null ? null : newCh[newEndIdx+1].elm;
addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
}
同理，如果new先遍歷完贞间，說明old里面有些元素要被移除
對應(yīng)代碼
else if (newStartIdx > newEndIdx) {
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
}
到此最麻煩的updateChildren就算解析完了贿条。
