Virtual DOM 的设计与实现
目前流行的一些前端框架，比如 React 和 Vue，都是用了 Virtual DOM 作为数据和真实 DOM 之间的一层缓冲，并不是直接更新 dom。Virtual DOM 本质上来说是 javascript 对象，用来描述 DOM 结构以及其附加的属性、状态、事件等。
我在学习了 snabbdom 源码后，借鉴其思路写了个简化版 mini-vdom，并使用 mini-vdom 构建了一个 MVVM 库 mini-mvvm。之所以选择 snabbdom ，是因为在比较了一些市面上的 vdom 库，发现 snabbdom 实现尤为巧妙，插件机制可以很方面的组合自己所需。另外就是 Vue 也是魔改了 snabbdom 作为自己 vdom 的底层部分，因此有极大的说服力。
写下这篇文章，一方面验证自己的理解，另一方面分享所学。
为什么要用 Virtual DOM
目前常见的 React，Vue 等前端框架，在设计上都使用了
Virtual DOM（下文中都简称vdom），旨在便于管理 dom，提高性能，以及添加跨平台能力。
统一管理 dom，提高性能
无需去记住复杂的 dom 操作方式，也不需要关心数据更新后哪些有变更。
vdom 封装了这一层，使用者只用更新自己的数据，生成一个新的 vdom，它会自己去找到其中差异的部分，进行更新、添加、删除等操作。 对 dom 的操作是昂贵的，vdom 作为一个缓冲层，使用者可以把自己对 dom 的期望表现在 vdom 上，最后在一个合适的时机去一次性更新真实 dom。
另一方面，提高性能并不是说使用 vdom 就比直接操作 dom 快。
"越封装越慢"，vdom 底层还是调用了普通的操作 dom 的相关 api，这里说的提高性能，说的是可能避免以下情况：
- 多次操作 dom 后的结果可能跟最初相比没有差异，而如果使用
vdom不会触发更新 dom。 - 最终的 dom 跟原始 dom 有差异，而
vdom会用最少的次数，尽可能的复用 dom 去达成更新目的以节约消耗，毕竟 dom 的操作非常昂贵。 - ...想到再加
跨平台能力
上来就说过，vdom 是对 dom 的一种描述，本质是 javascript 对象，或者编译为其它语言的对象，那么换一种宿主环境，就可以让 vdom 在新的平台继续使用，比如去进行 SSR(Server Side Render) ，或者很出名的 React Native。
设想一下 vdom 需要做什么
1
2 +-------------------+
3 | |
4 | template | 理想状态可以通过模板来生成 Virtual DOM
5 | | 或者至少是一个 factory
6 +---------+---------+
7 |
8 |
9 v
10 +---------+---------+ +-------------------+ +-------------------+
11 | | | | | |
12 | 1. VNode +-----> | 2. diff +-----> | 3. patch |
13 | | | | | |
14 +-------------------+ +-------------------+ +-------------------+
15 得到 Virtual DOM 对象， 对比新旧 VNode 把 VNode 表示的dom，
16 我这里起个名字叫 VNode 看看哪些内容需要去更新 更新到真实 dom 上
17如上图，核心步骤是
VNode=>diff=>patch
生成 VNode
其中 VNode最好是可以通过模板来生成，不过这个应该放在业务端去做，可以看看 mini-mvvm，我在其中实现了 Compile 去编译模板，简化了 VNode 的生成，用起来更直观。
作为更底层的 vdom 库，应该只用提供方式去生成 VNode ，至于如何去优化以便于贴合业务，还是交给业务端吧。
diff 对比新旧 VNode
每次都会生成一个完整的新的 VNode ，拿这个跟旧的做对比，找出其中的差异，以及最优调整方式。
有 3 种情况：
- 对于相同的部分，保持不变。
- 不一样，但是可复用。
- 不一样，不能复用。
对比包含了 标签类型（tagName）、节点属性（attributes）、自身状态（props，不同于 attributes）、事件（events），其中 标签类型（tagName） 以及后面会提到的辅助字段 key 会决定节点是否可以复用。
patch 更新到 dom 上
根据 diff 对比，把结果反馈到真实 dom 上，一个好的 diff 算法能够节省大量消耗。
目录结构概览
需求有了，就需要划分模块去实现各步骤。这是我整理的项目目录结构。
1├── dev.scss # 开发阶段所用样式
2├── dev.ts # 开发阶段打包入口
3├── index.ts # 生产环境打包入口
4├── lib
5│ ├── VNode.ts # VNode 模块
6│ ├── h.ts # VNode 的工厂方法
7│ ├── hooks.ts # 为 vdom 提供生命周期的 hook
8│ ├── modules # plugins 目录，VNode 所拥有的各项能力
9│ │ ├── attrs.ts
10│ │ ├── events.ts
11│ │ └── props.ts
12│ └── patch.ts # 把 VNode 挂载到真实 dom
13└── utils # 工具包
14 └── index.tsVNode 的设计
VNode 是
vdom库对真实 dom 描述的最小单元。当 VNode 按照一定的结构组合起来，再添加上更新真实 dom 的能力，就是一个完整的vdom库。
VNode 类
1class VNode {
2 key: string;
3 type: string;
4 data: IVNodeData;
5 children?: VNode[];
6 text?: string;
7 elm?: Element;
8 constructor(type: string, data?: IVNodeData, children?: VNode[], text?: string, elm?: Element);
9 /**
10 * 是否是 VNode
11 *
12 * @static
13 * @param {*} node 要判断的对象
14 * @returns {boolean}
15 * @memberof VNode
16 */
17 static isVNode(node: any): boolean;
18 /**
19 * 是否是可复用的 VNode 对象
20 * 判断依据是 key 跟 tagname 是否相同，既 对于相同类型dom元素尽可能复用
21 *
22 * @static
23 * @param {VNode} oldVnode
24 * @param {VNode} vnode
25 * @returns {boolean}
26 * @memberof VNode
27 */
28 static isSameVNode(oldVnode: VNode, vnode: VNode): boolean;
29}
30
31export interface IVNodeData {
32 key?: string;
33
34 props?: IProps;
35
36 attrs?: IAttrs;
37
38 on?: IListener;
39
40 hook?: IVnodeHook;
41
42 ns?: string;
43}key是 VNode 在同一父节点下的唯一标识，主要用给业务层来决定是否复用 dom。type表示tagName，表示节点的 tag 类型。data是IVNodeData类型，包含了 节点属性、节点状态、事件 等信息。children表示子节点数组，对应了真实 dom 中的childNodestext表示textContentelm对应了真实 dom 元素isVNode和isSameVNode是 VNode 相关的静态方法，作用见注释
h，生成 VNode 的工厂
这么多属性，如果自己去一个一个 new，大概会被烦死吧，，，因此额外提供一个 h 方法，用于快速，便捷的生成 VNode。
1function h(type: string, text?: string): VNode;
2function h(type: string, children?: VNode[]): VNode;
3function h(type: string, data?: IVNodeData, text?: string): VNode;
4function h(type: string, data?: IVNodeData, children?: VNode[]): VNode;乍一看好像提升效率并不太高，很多东西还是要自己写。但是这里的 type 并不是单纯的指标签类型，实际上是 emmet 语法（不包含层级选择）：
div，常规的 tagNamediv#app，包含了iddiv.some-class.sec-class，包含了若干classa[href=www.baidu.com][target=_blank]，包含了若干attributediv#app.some-class[data-hello=world]， 可以把上面这些任意组合起来！
使用这些重载可以节省很多很多代码，只要用一个又臭又长的字符串，就可以表示出一个特别复杂的结构了 >_<#@! ，其中的实现主要是用了正则表达式，感兴趣可以去 mini-vdom 查看具体实现，或者参考我另一篇文章 javascript 中的正则表达式，这里不赘述。
以插件的形式为 VNode 注入能力
snabbdom 在这部分的设计中，把 VNode 各项能力抽象成一种插件，并没有完全集成在自身的 lib 中。我之前看到这一步说实话挺惊奇，这样就为业务层提供了更多的定制化能力。
作为插件的意思是，在设计的过程中，插件并不是跟 lib 强耦合，大家都遵循同一套接口（比如初始化方式，生命周期等），然后打包的时候需要哪个再加哪个。
这部分位于 modules 目录下，包含了 attrs、events、props 三部分，对应了节点的 属性、事件、自身状态。各部分根据自身情况去注册这些接口：
1export type TModuleHookFunc = (oldVnode: VNode, vnode: VNode) => void;
2
3export interface IModuleHook {
4 create?: TModuleHookFunc;
5
6 insert?: TModuleHookFunc;
7
8 update?: TModuleHookFunc;
9
10 destroy?: TModuleHookFunc;
11}以 attrs 为例，这部分模块负责处理节点的属性：
1export function updateAttrs(oldVnode: VNode, vnode: VNode): void {
2 let oldAttrs = oldVnode.data.attrs;
3 let attrs = vnode.data.attrs;
4 const elm = vnode.elm;
5
6 // 两个vnode都不存在 attrs
7 if (!oldAttrs && !attrs) return;
8 // 两个 attrs 是相同的
9 if (oldAttrs === attrs) return;
10
11 oldAttrs = oldAttrs || {};
12 attrs = attrs || {};
13
14 // 更新 attrs
15 for (const key in attrs) {
16 const cur = attrs[key];
17 const old = oldAttrs[key];
18 // 相同就跳过
19 if (cur === old) continue;
20 // 不同就更新
21 elm.setAttribute(key, cur + '');
22 }
23
24 // 对于 oldAttrs 中有，而 attrs 没有的项，去掉
25 for (const key in oldAttrs) {
26 if (!(key in attrs)) {
27 elm.removeAttribute(key);
28 }
29 }
30}
31
32export const attrsModule: IModuleHook = {
33 create: updateAttrs,
34 update: updateAttrs
35};attrs 在 创建、更新 两个阶段会触发模块的处理函数，其它没用到的地方不用加，对应的 hook 会在 vdom 更新的对应生命周期去执行。
diff 和 patch
之所以把 diff 和 patch 放在一起，是因为虽然从逻辑上来看是两个步骤，但实际上是一个整体。 因为 diff 是在 patch 的过程中进行。
第一次 patch，是 VNode 跟空的根 dom 进行对比，所有的 dom 都是新增。
之后的 patch 属于 update，是新旧 VNode 对比，对于不可复用的删除，可复用的更新，新增的部分插入。
对比单节点在更新前后的差异
使用 patchVNode 来更新一个节点。 dom 和 VNode 是一个树状结构，我们在进行 diff 的时候，是从根节点开始进行递归。
注释节点在本篇文章中会忽略掉。
1----------------------------------------------------
2 # 1. 前后没有差异，直接返回
3
4----------------------------------------------------
5 # 2. 两者都是文本节点，则更新 `textContent`
6
7 XX XX
8 X X +-------> X X
9 X X X X
10 X+----+X +-------> X+----+X
11 X X X X
12 X X X X
13
14----------------------------------------------------
15 # 3. 新旧节点都有 children，属于容器节点，则去对比他们 children，执行 `updateChildren`
16
17 +----------+ +----------+
18 | | +-------> | |
19 | | | |
20 | | +-------> | |
21 | | | |
22 +----------+ +----------+
23
24----------------------------------------------------
25 # 新节点是容器节点，旧的是文本节点。删除文本，添加新节点。
26
27 XX +----------+
28 X X +-------> | |
29 X X | |
30 X+----+X +-------> | |
31 X X | |
32 X X +----------+
33
34----------------------------------------------------
35 # 新节点是文本节点，旧的是容器节点。删除容器节点，添加文本节点。
36
37 +----------+ XX
38 | | +-------> X X
39 | | X X
40 | | +-------> X+----+X
41 | | X X
42 +----------+ X X
43
44----------------------------------------------------节点的 新增、删除、更新 等操作，都会触发相应的hook（上文提到的`module`目录下声明的各项能力）
- 前后没有差异，直接返回
- 两者都是文本节点，则更新
textContent - 新旧节点都有 children，属于容器节点，则去对比他们 children，执行
updateChildren - 新节点是容器节点，旧的是文本节点。删除文本，添加新节点。
- 新节点是文本节点，旧的是容器节点。删除容器节点，添加文本节点。
特地画了个图来帮助描述，，，这个就是更新某个节点部分的逻辑，不上代码占位置了。
diff 算法
上面说的是更新某一个节点，更新节点的直接子节点使用的是 updateChildren ，一般说的 diff算法 就指的是这块。一个好的 diff算法 可以在很大程度上决定一个 vdom 库的优劣。
我们循序渐进看一下：
批量全更新
1// 方式一：
2// 如果想无脑点可以直接这样，不复用dom，直接把所有children都更新
3removeVnodes(parentElm, oldChildren);
4addVnodes(parentElm, null, children);不需要去考虑如何复用节点，直接全删掉重新生成。
优点是简单，直观，这个是我写的烦的时候，一怒之下的作品 QAQ 。
复用元素
如何决定一个元素是否可复用？ 上面 VNode 那里的实现有个 isSameVNode 静态方法，判断的依据很简单：
当 tagName 和 key 都相同的时候，这个元素就可以复用
tagName 自不必说，如果节点类型都不一样，当然不能复用。至于 key，是交给业务端去添加，因为一些 dom 可能有些脏状态，比如用户自己添加的，或者自身就带有（比如 input:text 有 value，input:checkbox 有 checked 等）。
Vue 中对 key 有这么一段描述：
key 的特殊 attribute 主要用在 Vue 的虚拟 DOM 算法，在新旧 nodes 对比时辨识 VNodes。如果不使用 key，Vue 会使用一种最大限度减少动态元素并且尽可能的尝试就地修改/复用相同类型元素的算法。而使用 key 时，它会基于 key 的变化重新排列元素顺序，并且会移除 key 不存在的元素。
下面这个算法，可以了解到 key 对 diff 算法的影响。
一个简单的 diff 算法
明白了复用元素的规则，我第一时间就想到了这个算法：从上到下依次循环呗。
- 循环目标 children，找到能复用的节点，就移动到当前位置。
- 没找到能复用的节点，就自己生成一个。
- 循环完毕后，把多余的节点删除，这些是不能复用的部分。
1const oldMirror = oldChildren.slice(); // 用来表示哪些oldchildren被用过，位置信息等
2for (let i = 0; i < children.length; i++) {
3 // 当前vnode
4 const vnode = children[i];
5 // 可以被复用的vnode的索引
6 const oldVnodeIndex = oldMirror.findIndex(node => {
7 return node && VNode.isSameVNode(node, vnode);
8 });
9 // 如果有vnode可以复用
10 if (~oldVnodeIndex) {
11 // console.log(oldVnodeIndex);
12 const oldVnode = oldMirror[oldVnodeIndex];
13
14 // 把之前的置空，表示已经用过。之后仍然存留的要被删除
15 oldMirror[oldVnodeIndex] = undefined;
16 // 调整顺序（如果旧的索引对不上新索引）
17 if (oldVnodeIndex !== i) {
18 parentElm.insertBefore(oldVnode.elm, parentElm.childNodes[i + 1]);
19 }
20 // 比较数据,进行更新
21 // eslint-disable-next-line
22 patchVNode(oldVnode, vnode);
23 }
24 // 不能复用就创建新的
25 else {
26 addVnodes(parentElm, parentElm.childNodes[i + 1], [vnode]);
27 }
28}
29
30// 删除oldchildren中未被复用的部分
31const rmVnodes = oldMirror.filter(n => !!n);
32
33rmVnodes.length && removeVnodes(parentElm, rmVnodes);这个算法非常简单，直观，有效。在对列表进行 修改，添加 操作的时候，表现的非常高效，可读性也不错，易理解。
但是缺点也很明显：如果对列表非尾部的地方，进行 插入，删除 操作，这时候最佳方式应该就是直接进行 插入 或 删除，而这个算法会从上到下依次进行没必要的复用。虽然添加 key 可以一定程度上解决半个问题，避免在 插入 时候的复用，但是不能指望用户里面没有白痴或者懒鬼，所以还是有改善的空间。
更完善的 diff 算法
这个算法的思路来自 snabbdom，在实现上有差异，我把它简化了（可能损失了一些微小的性能？）。
据我了解也是业内相对更通用的 diff 实现，各 vdom 库已经趋于一致。虽然有更优的算法可以在一些更复杂的情况减少 dom 操作，但是复杂度就上去了。大概大部分人觉得，下面的这种实现，可以让 可读性，效率 达到可接受的平衡态吧。
概述
上面那个简单的 diff 算法，是从左到右（从上到下）依次做对比，可以满足 尾部插入，尾部删除 操作，但是对于 非尾部插入，非尾部删除 就力不从心，所以新的算法需要弥补这点。
除了从左到右，再加一种从右到左。 从两端向中间依次进行对比。
1 oldStartIndex oldEndIndex
2 + +
3 | |
4 v v
5 +---+---+ +-------+ +-------+ +-------+ +---+---+
6 | | | | | | | | | |
7old: | | | | | | | | | |
8 | | | | | | | | | |
9 +-------+ +-------+ +-------+ +-------+ +-------+
10
11 +-------+ +-------+ +-------+ +-------+ +-------+
12 | | | | | | | | | |
13new: | | | | | | | | | |
14 | | | | | | | | | |
15 +---+---+ +-------+ +-------+ +-------+ +---+---+
16 ^ ^
17 | |
18 + +
19 newStartIndex newEndIndex原理听起来就是这么简单。但是实现上挺麻烦，这些步骤需要耐心看下去。
假设有 4 个索引，分别是：
oldStartIndex，指向 oldChildren 左边遍历到的节点oldEndIndex，指向 oldChildren 右边遍历到的节点newStartIndex，指向 newChildren 左边遍历到的节点newEndIndex，指向 newChildren 左边遍历到的节点
1while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
2 switch (true) {
3 }
4}不断重复以下对比过程，直到两个数组中任一组的头指针超过尾指针，循环结束。
校验当前指向的节点是否可用
1 // 1. 先校验2个 old start/end vnode 是否为空，当为`undefined`的时候，表示被其它地方复用了
2 // 对 new start/end vnode 也做处理，是因为可能移动后根本没子节点
3 case !oldStartVNode:
4 oldStartVNode = oldChildren[++oldStartIndex];
5 break;
6 case !oldEndVNode:
7 oldEndVNode = oldChildren[--oldEndIndex];
8 break;
9 case !newStartVNode:
10 newStartVNode = children[++newStartIndex];
11 break;
12 case !newEndVNode:
13 newEndVNode = oldChildren[--newEndIndex];
14 break;对于 oldChildren 来说，如果某个节点被复用，可以把它赋值 undefined 作为标记，因此当指向的节点为空时，需要移动指针到下一个。即 oldStartIndex 向右，或 oldEndIndex 向左。
newChildren 也需要添加判断，因为可能新的 children 长度为 0。
首首对比、尾尾对比
1 // 2. 首首、尾尾 对比， 适用于 普通的 插入、删除 节点
2 // 首首比较
3 case VNode.isSameVNode(oldStartVNode, newStartVNode):
4 patchVNode(oldStartVNode, newStartVNode);
5 oldStartVNode = oldChildren[++oldStartIndex];
6 newStartVNode = children[++newStartIndex];
7 break;
8
9 // 尾尾比较
10 case VNode.isSameVNode(oldEndVNode, newEndVNode):
11 patchVNode(oldEndVNode, newEndVNode);
12 oldEndVNode = oldChildren[--oldEndIndex];
13 newEndVNode = children[--newEndIndex];
14 break;首首对比 好说，跟上面那个简单 diff 一样从左往右判断。但是如果用户的行为是向列表首部添加一项，那么继续从左往右就会浪费很多计算量。
在 首首对比 失败后，再进行 尾尾对比，从右向左判断，这样就适用于普通任意位置的 插入、删除 节点。
首尾交叉对比
1 // 3. 旧尾=》新头，旧头=》新尾， 适用于移动了某个节点的情况
2 // 旧尾=》新头，把节点左移
3 // [1, 2, 3]
4 // [3, 1, 2]
5 case VNode.isSameVNode(oldEndVNode, newStartVNode):
6 parentElm.insertBefore(oldEndVNode.elm, parentElm.childNodes[newStartIndex]);
7 patchVNode(oldEndVNode, newStartVNode);
8 oldEndVNode = oldChildren[--oldEndIndex];
9 newStartVNode = children[++newStartIndex];
10 break;
11
12 // 旧头=》新尾，把节点右移
13 // [1, 2, 3]
14 // [2, 3, 1]
15 case VNode.isSameVNode(oldStartVNode, newEndVNode):
16 parentElm.insertBefore(oldEndVNode.elm, oldEndVNode.elm.nextSibling);
17 patchVNode(oldStartVNode, newEndVNode);
18 oldStartVNode = oldChildren[++oldStartIndex];
19 newEndVNode = children[--newEndIndex];
20 break;首尾交叉对比 是交叉对比的一部分，其实跳过这里到下一步也没问题。但是如果添加了这种判断，就为 移动了某个节点 的情况避免了计算消耗，会更快。
旧尾跟新头对比，适用于节点左移的情况
1# example，3 移动到了左边
2old: [1, 2, 3]
3new: [3, 1, 2]旧头跟新尾对比，适用于节点右移的情况
1# example，1 移动到了右边
2old: [1, 2, 3]
3new: [2, 3, 1]交叉对比剩余部分
1 // 4. 交叉对比剩余部分
2 default:
3 // 可以被复用的vnode的索引
4 const oldVnodeIndex = oldChildren.findIndex((node, index) => {
5 return (
6 // 索引在 oldStartIndex ~ oldEndIndex
7 // 之前没有被复用过
8 // 并且可以被复用
9 index >= oldStartIndex &&
10 index <= oldEndIndex &&
11 node &&
12 VNode.isSameVNode(node, newStartVNode)
13 );
14 });
15 // 如果有vnode可以复用
16 if (~oldVnodeIndex) {
17 const oldVnode = oldChildren[oldVnodeIndex];
18
19 // 把之前的置空，表示已经用过。之后仍然存留的要被删除
20 oldChildren[oldVnodeIndex] = undefined;
21 // 调整顺序（如果旧的索引对不上新索引）
22 if (oldVnodeIndex !== newStartIndex) {
23 parentElm.insertBefore(oldVnode.elm, parentElm.childNodes[newStartIndex]);
24 }
25 // 比较数据,进行更新
26 patchVNode(oldVnode, newStartVNode);
27 }
28 // 不能复用就创建新的
29 // old: [1, 2, 3, 4]
30 // new: [1, 5, 2, 3, 6, 4]
31 else {
32 addVnodes(parentElm, parentElm.childNodes[newStartIndex], [newStartVNode]);
33 }
34
35 // 新头 向右移动一位
36 newStartVNode = children[++newStartIndex];
37 break;oldChildren中俩指针中间的部分，属于没被复用的部分。newChildren中俩指针中间的部分，目前没能够找到可复用节点。
对于 newChildren 的剩余部分，依次从 oldChildren 的剩余部分中去找可复用的节点，如果没找到，就生成一个新的去填充，oldChildren 里面如果某一项被复用，就给这个索引位置赋值 undefined 作为标记，下次循环直接跳过。
善后工作
1// 如果循环完毕，还有 oldStartIndex ～ oldEndIndex || newStartIndex ～ newEndIndex 之间还有空余，
2// 表示有旧节点未被删除干净，或者新节点没有完全添加完毕
3
4// 旧的 vnodes 遍历完，新的没有
5// 表示有新的没有添加完毕
6if (oldStartIndex > oldEndIndex && newStartIndex <= newEndIndex) {
7 addVnodes(parentElm, children[newEndIndex + 1]?.elm, children.slice(newStartIndex, newEndIndex + 1));
8}
9// 新的 vnodes 遍历完，旧的没有
10// 表示有旧的没有删除干净
11else if (oldStartIndex <= oldEndIndex && newStartIndex > newEndIndex) {
12 removeVnodes(
13 parentElm,
14 oldChildren.slice(oldStartIndex, oldEndIndex + 1).filter(n => !!n)
15 );
16}这时候有 2 种情况需要处理一下：
oldChildren遍历完，newChildren没有。 表示旧节点都被复用了，还有部分新节点要重新生成。newChildren遍历完，oldChildren没有。 表示新节点都已经生成完毕，旧节点中有一部分没用上，都需要删除。
相关链接
snabbdom
A mini virtual dom lib. 一个轻量级的虚拟 dom 库
基于 virtual dom - mini-vdom 的轻量级 mvvm 库
emmet
javascript 中的正则表达式
