【总结】1243- 浅析 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 | 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 | 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 替换老 DOM
patch 函数其实就是 init 方法的返回值，所以找到 init 的源码：
export function init(modules: Array>, 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)
回复“加群”与大佬们一起交流学习~