VirtualDOM 是 react 在组件化开发场景下，针对 DOM 重排重绘性能瓶颈作出的重要优化方案，而他最具价值的核心功能是如何识别并保存新旧节点数据结构之间差异的方法，也即是 diff 算法。毫无疑问的是 diff 算法的复杂度与效率是决定 VirtualDOM 能够带来性能提升效果的关键因素。因此，在 VirtualDOM 方案被提出之后，社区中不断涌现出对 diff 的改进算法，引用司徒正美的经典介绍：
最开始经典的深度优先遍历 DFS 算法，其复杂度为 O(n^3)，存在高昂的 diff 成本，然后是 cito.js 的横空出世，它对今后所有虚拟 DOM 的算法都有重大影响。它采用两端同时进行比较的算法，将 diff 速度拉高到几个层次。紧随其后的是 kivi.js，在 cito.js 的基出提出两项优化方案，使用 key 实现移动追踪及基于 key 的编辑长度距离算法应用（算法复杂度 为 O(n^2)）。但这样的 diff 算法太过复杂了，于是后来者 snabbdom 将 kivi.js 进行简化，去掉编辑长度距离算法，调整两端比较算法。速度略有损失，但可读性大大提高。再之后，就是著名的 vue2.0 把 snabbdom 整个库整合掉了。
因此目前 VirtualDOM 的主流 diff 算法趋向一致，在主要 diff 思路上，snabbdom 与 react 的 reconilation 方式基本相同。
virtual dom 中心思想
如果没有理解 virtual dom 的构建思想, 那么你可以参考这篇精致文章 Boiling React Down to a Few Lines in jQueryvirtual dom 优化开发的方式是：通过 vnode, 来实现无状态组件, 结合单向数据流(undirectional data flow), 进行 UI 更新, 整体代码结构是：
var newVnode = render(vnode, state)
var oldVnode = patch(oldVnode, newVnode)
state.dispatch(‘change’)
var newVnode = render(vnode, state)
var oldVnode = patch(oldVnode, newVnode)
virtual dom 库选择
在众多 virtual dom 库中, 我们选择 snabbdom 库, 原因有很多：
1.snabbdom 性能排名靠前, 虽然这个 benchmark 的参考性不高 2。snabbdom 示例丰富 3.snabbdom 具有一定的生态圈, 如 motorcycle.js,cycle-snabbdom,cerebral4.snabbdom 实现的十分优雅, 使用的是 recursive 方式调用 patch, 对比 infernojs 优化痕迹明显的代码,snabbdom 更易读。5. 在阅读过程中发现,snabbdom 的模块化, 插件支持做得极佳
snabbdom 的工作方式
我们来查看 snabbdom 基本使用方式。
// snabbdom 在./snabbdom.js
var snabbdom = require(‘snabbdom’)
// 初始化 snabbdom, 得到 patch。随后, 我们可以看到 snabbdom 设计的精妙之处
var patch = snabbdom.init([
require(‘snabbdom/modules/class’),
require(‘snabbdom/modules/props’),
require(‘snabbdom/modules/style’),
require(‘snabbdom/modules/eventlisteners’)
])
// h 是一个生成 vnode 的包装函数,factory 模式？对生成 vnode 更精细的包装就是使用 jsx
// 在工程里, 我们通常使用 webpack 或者 browserify 对 jsx 编译
var h = require(‘snabbdom/h’)
// 构造一个 virtual dom, 在实际中, 我们通常希望一个无状态的 vnode
// 并且我们通过 state 来创造 vnode
// react 使用具有 render 方法的对象来作为组件, 这个组件可以接受 props 和 state
// 在 snabbdom 里面, 我们同样可以实现类似效果
// function component(state){return h(…)}
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!’)
]
)
// 得到初始的容器, 注意 container 是一个 dom element
var container = document.getElementById(‘container’)
// 将 vnode patch 到 container 中
// patch 函数会对第一个参数做处理, 如果第一个参数不是 vnode, 那么就把它包装成 vnode
// patch 过后,vnode 发生变化, 代表了现在 virtual dom 的状态
patch(container, vnode)
// 创建一个新的 vnode
var newVnode =
h(
‘div#container.two.classes’,
{on: {click: anotherEventHandler}},
[
h(‘span’, {style: {fontWeight: ‘normal’, fontStyle: ‘italics’}},
‘This is now italics’),
‘ and this is still just normal text’,
h(‘a’, {props: {href: ‘/bar’}}, ‘I\’ll take you places!’)
]
)
// 将新的 vnode patch 到 vnode 上, 现在 newVnode 代表 vdom 的状态
patch(vnode, newVnode)
vnode 的定义
阅读 vdom 实现, 首先弄清楚 vnode 的定义
vnode 的定义在./vnode.js 中 vnode 具备的属性
1.tagName 可以是 custom tag, 可以是 ’div’,’span’,etc, 代表这个 virtual dom 的 tag name2.data, virtual dom 数据, 它们与 dom element 的 prop、attr 的语义类似。但是 virtual dom 包含的数据可以更灵活。比如利用./modules/class.js 插件, 我们在 data 里面轻松 toggle 一个类名
h(‘p’, {class: {‘hide’: hideIntro}})
children, 对应 element 的 children, 但是这是 vdom 的 children。vdom 的实现重点就在对 children 的 patch 上
text, 对应 element.textContent, 在 children 里定义一个 string, 那么我们会为这个 string 创建一个 textNode
elm, 对 dom element 的引用
key, 用于提示 children patch 过程, 随后将详细说明
h 参数
随后是 h 函数的包装
h 的实现在./h.js
包装函数一共注意三点
对 svg 的包装, 创建 svg 需要 namespace
将 vdom.text 统一转化为 string 类型
将 vdom.children 中的 string element 转化为 textNode
与 dom api 的对接
实现在./htmldomapi.js
采用 adapter 模式, 对 dom api 进行包装, 然后将 htmldomapi 作为默认的浏览器接口这种设计很机智。在扩展 snabbdom 的兼容性的时候, 只需要改变 snabbdom.init 使用的浏览器接口, 而不用改变 patch 等方法的实现
snabbdom 的 patch 解析
snabbdom 的核心内容实现在./snabbdom.js。snabbdom 的核心实现不到三百行(233 sloc), 非常简短。
在 snabbdom 里面实现了 snabbdom 的 virtual dom diff 算法与 virtual dom lifecycle hook 支持。virtual dom diffvdom diff 是 virtual dom 的核心算法,snabbdom 的实现原理与 react 官方文档 Reconciliation 一致总结起来有：
对两个树结构进行完整的 diff 和 patch, 复杂度增长为 O(n^3), 几乎不可用
对两个数结构进行启发式 diff, 将大大节省开销
一篇阅读量颇丰的文章 React’s diff algorithm 也说明的就是启发过程, 可惜, 没有实际的代码参照。现在, 我们根据 snabbdom 代码来看启发规则的运用, 结束后, 你会明白 virtual dom 的实现有多简单。
首先来到 snabbdom.js 中 init 函数的 return 语句
return function(oldVnode, vnode) {
var i, elm, parent;
// insertedVnodeQueue 存在于整个 patch 过程
// 用于收集 patch 中新插入的 vnode
var insertedVnodeQueue = [];
// 在进行 patch 之前, 我们需要运行 prepatch hook
// cbs 是 init 函数变量, 即, 这个 return 语句中函数的闭包
// 这里, 我们不理会 lifecycle hook, 而只关注 vdom diff 算法
for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();
// 如果 oldVnode 不是 vnode(在第一次调用时,oldVnode 是 dom element)
// 那么用 emptyNodeAt 函数来将其包装为 vnode
if (isUndef(oldVnode.sel)) {
oldVnode = emptyNodeAt(oldVnode);
}
// sameVnode 是上述“值不值得 patch”的核心
// sameVnode 实现很简单, 查看两个 vnode 的 key 与 sel 是否分别相同
// ()=>{vnode1.key === vnode2.key && vnode1.sel === vnode2.
// 比较语义不同的结构没有意义, 比如 diff 一个 ’div’ 和 ’span’
// 而应该移除 div, 根据 span vnode 插入新的 span
// diff 两个 key 不相同的 vnode 同样没有意义
// 指定 key 就是为了区分 element
// 对于不同 key 的 element, 不应该去根据 newVnode 来改变 oldVnode 的数据
// 而应该移除不再 oldVnode, 添加 newVnode
if (sameVnode(oldVnode, vnode)) {
// oldVnode 与 vnode 的 sel 和 key 分别相同, 那么这两个 vnode 值得去比较
//patchVnode 根据 vnode 来更新 oldVnode
patchVnode(oldVnode, vnode, insertedVnodeQueue);
} else {
// 不值得去 patch 的, 我们就暴力点
// 移除 oldVnode, 根据 newVnode 创建 elm, 并添加至 parent 中
elm = oldVnode.elm;
parent = api.parentNode(elm);
// createElm 根据 vnode 创建 element
createElm(vnode, insertedVnodeQueue);
if (parent !== null) {
// 将新创建的 element 添加到 parent 中
api.insertBefore(parent, vnode.elm, api.nextSibling(elm));
// 同时移除 oldVnode
removeVnodes(parent, [oldVnode], 0, 0);
}
}
// 结束以后, 调用插入 vnode 的 insert hook
for (i = 0; i < insertedVnodeQueue.length; ++i) {
insertedVnodeQueue[i].data.hook.insert(insertedVnodeQueue[i]);
}
// 整个 patch 结束, 调用 cbs 中的 post hook
for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
return vnode;
};
“`
### 然后我们阅读 patch 的过程
“`
function patchVnode(oldVnode, vnode, insertedVnodeQueue) {
var i, hook;
// 如前, 在 patch 之前, 调用 prepatch hook, 但是这个是 vnode 在 data 里定义的 prepatch hook, 而不是全局定义的 prepatch hook
if (isDef(i = vnode.data) && isDef(hook = i.hook) && isDef(i = hook.prepatch)) {
i(oldVnode, vnode);
}
var elm = vnode.elm = oldVnode.elm, oldCh = oldVnode.children, ch = vnode.children;
// 如果 oldVnode 和 vnode 引用相同, 则没必要比较。在良好设计的 vdom 里, 大部分时间我们都在执行这个返回语句。
if (oldVnode === vnode) return;
// 如果两次引用不同, 那说明新的 vnode 创建了
// 与之前一样, 我们先看这两个 vnode 值不值得去 patch
if (!sameVnode(oldVnode, vnode)) {
// 这四条语句是否与 init 返回函数里那四条相同？
var parentElm = api.parentNode(oldVnode.elm);
elm = createElm(vnode, insertedVnodeQueue);
api.insertBefore(parentElm, elm, oldVnode.elm);
removeVnodes(parentElm, [oldVnode], 0, 0);
return;
}
// 这两个 vnode 值得去 patch
// 我们先 patch vnode,patch 的方法就是先调用全局的 update hook
// 然后调用 vnode.data 定义的 update hook
if (isDef(vnode.data)) {
for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode);
i = vnode.data.hook;
if (isDef(i) && isDef(i = i.update)) i(oldVnode, vnode);
}
// patch 两个 vnode 的 text 和 children
// 查看 vnode.text 定义
// vdom 中规定, 具有 text 属性的 vnode 不应该具备 children
// 对于 <p>foo:<b>123</b></p> 的良好写法是
// h(‘p’, [ ‘foo:’, h(‘b’, ‘123’)]), 而非
// h(‘p’, ‘foo:’, [h(‘b’, ‘123’)])
if (isUndef(vnode.text)) {
// vnode 不是 text node, 我们再查看他们是否有 children
if (isDef(oldCh) && isDef(ch)) {
// 两个 vnode 都有 children, 那么就调用 updateChildren
if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);
} else if (isDef(ch)) {
// 只有新的 vnode 有 children, 那么添加 vnode 的 children
if (isDef(oldVnode.text)) api.setTextContent(elm, ”);
addVnodes(elm, null, ch, 0, ch.length – 1, insertedVnodeQueue);
} else if (isDef(oldCh)) {
// 只有旧 vnode 有 children, 那么移除 oldCh
removeVnodes(elm, oldCh, 0, oldCh.length – 1);
} else if (isDef(oldVnode.text)) {
// 两者都没有 children, 并且 oldVnode.text 不为空,vnode.text 未定义, 则清空 elm.textContent
api.setTextContent(elm, ”);
}
} else if (oldVnode.text !== vnode.text) {
// vnode 是一个 text node, 我们改变对应的 elm.textContent
// 在这里我们使用 api.setText api
api.setTextContent(elm, vnode.text);
}
if (isDef(hook) && isDef(i = hook.postpatch)) {
i(oldVnode, vnode);
}
}
patch 的实现是否简单明了？甚至有觉得“啊？这就 patch 完了”的感觉。当然, 我们还差最后一个, 这个是重头戏——updateChildren。
最后阅读 updateChildren*
updateChildren 的代码较长且密集, 但是算法十分简单 oldCh 是一个包含 oldVnode 的 children 数组,newCh 同理我们先遍历两个数组(while 语句), 维护四个变量
遍历 oldCh 的头索引 – oldStartIdx
遍历 oldCh 的尾索引 – oldEndIdx
遍历 newCh 的头索引 – newStartIdx
遍历 newCh 的尾索引 – newEndIdx
当 oldStartIdx > oldEndIdx 或者 newStartIdx > newOldStartIdx 的时候停止遍历。
遍历过程中有五种比较前四种比较
oldStartVnode 和 newStartVnode, 两者 elm 相对位置不变, 若值得 (sameVnode) 比较, 这 patch 这两个 vnode
oldEndVnode 和 newEndVnode, 同上,elm 相对位置不变, 做相同 patch 检测
oldStartVnode 和 newEndVnode, 如果 oldStartVnode 和 newEndVnode 值得比较, 说明 oldCh 中的这 - – oldStartVnode.elm 向右移动了。那么执行 api.insertBefore(parentElm,oldStartVnode.elm, api.nextSibling(oldEndVnode.elm))调整它的位置
oldEndVnode 和 newStartVnode, 同上, 但这是 oldVnode.elm 向左移, 需要调整它的位置
最后一种比较
利用 vnode.key, 在 ul>li* n 的结构里, 我们很有可能使用 key 来标志 li 的唯一性, 那么我们就会来到最后一种情况。这个时候, 我们先产生一个 index-key 表(createKeyToOldIdx), 然后根据这个表来进行更改。
更改规则
如果 newVnode.key 不在表中, 那么这个 newVnode 就是新的 vnode, 将其插入如果 newVnode.key 在表中, 那么对应的 oldVnode 存在, 我们需要 patch 这两个 vnode, 并在 patch 之后, 将这个 oldVnode 置为 undefined(oldCh[idxInOld] = undefined), 同时将 oldVnode.elm 位置变换到当前 oldStartIdx 之前, 以免影响接下来的遍历
遍历结束后, 检查四个变量, 对移除剩余的 oldCh 或添加剩余的 newChpatch 总结阅读完 init 函数 return 语句,patch,updateChildren, 我们可以理解整个 diff 和 patch 的过程
有些函数 createElm,removeVnodes 并不重要
lifecycle hook
阅读完 virtual dom diff 算法实现后, 我们可能会奇怪, 关于 style、class、attr 的 patch 在哪里？这些实现都在 modules, 并通过 lifecycle 发挥作用 snabbdom 的生命周期钩子函数定义在 core doc – hook 中。再查看 modules 里的 class 会发现,class module 通过两个 hook 钩子来对 elm 的 class 进行 patch。这两个钩子是 create 和 update。回到 init 函数, 这两个钩子在函数体开头注册
for (i = 0; i < hooks.length; ++i) {
cbs[hooks[i]] = [];
for (j = 0; j < modules.length; ++j) {
if (modules[j][hooks[i]] !== undefined)
cbs[hooks[i]].push(modules[j][hooks[i]]);
}
}
create hook 在 createElm 中调用。createElm 是唯一添加 vnode 的方法, 所以 insertedVnodeQueue.push 只发生在 createElm 中。