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.ts
## VNode 的设计
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 中的childNodes
text
表示textContent
elm
对应了真实 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
,包含了id
div.some-class.sec-class
,包含了若干class
a[href=www.baidu.com][target=_blank]
,包含了若干attribute
div#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 中的正则表达式