共计 10795 个字符，预计需要花费 27 分钟才能阅读完成。
何为虚构 DOM
虚构 DOM 就是一般的 js 对象，其能够用来形容 DOM 对象，然而因为不是真正的 DOM 对象，因而人们把它叫做虚构 DOM。
为何呈现虚构 DOM
- 手动解决 DOM
在晚期的 js 利用中，开发人员须要手动解决 DOM，手动解决不仅代码繁琐，而且须要适配各种浏览器。
- jQuery 操作 DOM
jQuery 对 DOM 解决操作进行了对立封装，由其外部解决浏览器的差别，尽管加重了开发人员的 DOM 操作老本，然而开发人员在开发时还是无奈防止 DOM 操作，无奈分心解决业务逻辑。
- mvvm 框架屏蔽 DOM 操作
mvvm 框架解决了视图和状态之间的同步问题，让开发人员不再须要进行 DOM 操作。然而此时不能保留 DOM 状态，当更新代码时，会整体更新导致 DOM 状态失落。
- 虚构 DOM 晋升渲染能力
用操作虚构 DOM 来代替操作实在 DOM，不仅能够保留 DOM 状态，而且虚构 DOM 在更新时只会批改变动的 DOM，晋升了简单视图的渲染能力。
Snabbdom
Snabbdom 是一个虚构 DOM 库，用其官网的话，其体积小，速度快，可扩大。Vue 框架虚构 DOM 应用的就是 Snabbdom（在其根底上进行了批改），上面将通过解析 Snabbdom 的源码来理解虚构 DOM 和 diff 算法。
根本应用
上面的例子是应用 snabbdom 在页面上输入 hello world。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>snabbdom-demo</title>
<script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom.js"></script>
<script src="https://cdn.bootcss.com/snabbdom/0.7.3/h.js"></script>
</head>
<body>
<div id="app"></div>
<script>
const patch = snabbdom.init([])
const h = snabbdom.h
let old = patch(document.querySelector('#app'), h('div.cls', 'hello world'))
setTimeout(() => {patch(old, h('div.cls', 'hello snabbdom'))
}, 2000);
</script>
</body>
</html>从上例能够看出，snabbdom 在应用的时候蕴含如下两个步骤：
- 调用 init 生成 patch 函数，init 反对传入一个数组，数组中能够蕴含扩大模块。
- 调用 patch 函数对页面 dom 进行比照更新，patch 承受 dom 元素或者 h 函数生成的 vnodes。
h 函数
h 函数最早见于 hyperscript，用于应用 JavaScript 创立超文本。在 snabbdom 中，h 函数用于生成 vnodes。
其实在应用 Vue 的我的项目中，就能够看到 h 函数：
new Vue({
router,
store,
render: h => h(App)
}).$mount('#app')此处 h 函数的作用就是将组件转换为 vnodes。
源码：
export function h(sel: string): VNode
export function h(sel: string, data: VNodeData | null): VNode
export function h(sel: string, children: VNodeChildren): VNode
export function h(sel: string, data: VNodeData | null, children: VNodeChildren): VNode
export function h(sel: any, b?: any, c?: any): VNode {
// .....
// 对传入的参数进行解决，最终调用 vnode 办法生成 vnode 对象
return vnode(sel, data, children, text, undefined)
};
export function vnode(sel: string | undefined,
data: any | undefined,
children: Array<VNode | string> | undefined,
text: string | undefined,
elm: Element | Text | undefined): VNode {
const key = data === undefined ? undefined : data.key
// vnode 函数的作用其实就是将多个数据组装成一个固定格局的对象
return {sel, data, children, text, elm, key}
}h 函数的源码在去除参数判断之后其实非常简单，就是将解决后的用户传参转换为一个 vnode 对象。
init 函数
const patch = snabbdom.init([])从 init 函数的应用就能够看出，其是一个高阶函数，因为其返回一个函数。
在 snabbdom 库中，init 函数用于解决模块，指定 dom 操作 api 及生成回调函数对象 cbs 用于后续 patch 函数应用。
源码：
// modules：模块数组，用于传入扩大模块
// domapi：定义如何操作 dom，通过批改 domapi，能够让 snabbdom 库反对小程序等利用
export function init(modules: Array<Partial<Module>>, domApi?: DOMAPI) {
let i: number
let j: number
// 收集所有的生命周期钩子函数
const cbs: ModuleHooks = {create: [],
update: [],
remove: [],
destroy: [],
pre: [],
post: []}
// 为 api 增加默认值
const api: DOMAPI = domApi !== undefined ? domApi : htmlDomApi
// 遍历所有生命周期
for (i = 0; i < hooks.length; ++i) {cbs[hooks[i]] = []
// 遍历所有模块，如果模块定义了生命周期钩子函数，那么将对应函数增加到 cbs 中
for (j = 0; j < modules.length; ++j) {const hook = modules[j][hooks[i]]
if (hook !== undefined) {(cbs[hooks[i]] as any[]).push(hook)
}
}
}
// ...... 省略一些外部函数
// 返回 patch 函数
return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {// ......}
}工具函数
在解说 patch 函数之前，须要理解一些工具函数：
isVnode
用于判断一个 js 数据是否是 vnode，只须要判断对象是否蕴含 sel 属性（在应用 h 函数生成的 vnode 对象均蕴含 sel 属性），
function isVnode (vnode: any): vnode is VNode {return vnode.sel !== undefined}sameVnode
用于判断两个 vnode 是否雷同，在 snabbdom 中，如果两个 vnode 的 key 和 sel 属性雷同，那么就认为这两个 vnode 雷同。
function sameVnode (vnode1: VNode, vnode2: VNode): boolean {return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel}patch 函数
patch 函数是 snabbdom 库的外围函数，在其外部执行新旧 Vnode 之间的比照，并依据比照的差别更新实在 DOM，执行实现后，会返回新的 Vnode 作为下次比照的旧 Vnode。
patch 的执行过程分为如下几步：
第一步：执行所有的 pre 生命钩子函数。
第二步：用 isVnode 函数判断传入的 oldVnode 是否是一个 Vnode 对象。
- 不是 Vnode 对象，将 oldVnode 转换成空的 Vnode 对象。
第三步：用 sameVnode 函数判断 oldVnode 和 newVnode 是否雷同。
- 如果雷同，调用
patchVnode进行比照更新。 - 如果不雷同，间接删除 oldVnode，将 newVnode 渲染成 dom 增加到页面上。
第四步：执行 insert 和 post 生命钩子函数。
function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
let i: number, elm: Node, parent: Node
const insertedVnodeQueue: VNodeQueue = []
// 1. 执行 pre 钩子函数
for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]()
// 2. 判断 oldVnode 是否是 Vnode
if (!isVnode(oldVnode)) {oldVnode = emptyNodeAt(oldVnode)
}
// 3. 判断 oldVnode 和 newVnode 是否雷同
if (sameVnode(oldVnode, vnode)) {
// 如果雷同就比照更新
patchVnode(oldVnode, vnode, insertedVnodeQueue)
} else {
// 如果不同就替换
elm = oldVnode.elm!
parent = api.parentNode(elm) as Node
// 依据 Vnode 创立 dom
createElm(vnode, insertedVnodeQueue)
if (parent !== null) {api.insertBefore(parent, vnode.elm!, api.nextSibling(elm))
removeVnodes(parent, [oldVnode], 0, 0)
}
}
// 4. 执行 insert 和 post 生命钩子函数
for (i = 0; i < insertedVnodeQueue.length; ++i) {insertedVnodeQueue[i].data!.hook!.insert!(insertedVnodeQueue[i])
}
for (i = 0; i < cbs.post.length; ++i) cbs.post[i]()
return vnode
}patchVnode
patchVnode 函数的作用是比照新旧 Vnode 之间的差别，并依据差别操作实在 dom。
patchVnode 函数的执行过程能够分为以下 4 步：
第一步：执行用户设置的 prepatch 钩子函数。
第二步：执行 update 钩子函数，先执行模块的 update 函数，再执行用户设置的 update 函数。
第三步：判断 newVnode 的 text 属性是否被设置。
- 设置了 text 属性，如果 oldVnode 和 newVnode 的 text 属性值不雷同，那么首先删除 oldVnode 的所有子节点，而后批改 oldVnode 对应的 ele 元素的文本内容。
- 未设置 text 属性
- 如果 oldVnode.children 和 newVnode.children 都有值
调用 updateChildren()
应用 diff 算法比照子节点，更新子节点 - 如果 newVnode.children 有值，oldVnode.children 无值
清空 DOM 元素
调用 addVnodes()，批量增加子节点 - 如果 oldVnode.children 有值，newVnode.children 无值
调用 removeVnodes()，批量移除子节点 - 如果 oldVnode.text 有值
清空 DOM 元素的内容
第四步：执行用户设置的 postpatch 钩子函数。
function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
const hook = vnode.data?.hook
// 1. 执行用户设置的 prepatch 钩子函数
hook?.prepatch?.(oldVnode, vnode)
const elm = vnode.elm = oldVnode.elm!
const oldCh = oldVnode.children as VNode[]
const ch = vnode.children as VNode[]
if (oldVnode === vnode) return
if (vnode.data !== undefined) {
// 2. 执行 update 钩子函数
for (let i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
vnode.data.hook?.update?.(oldVnode, vnode)
}
// 3. 判断 vnode 的 text 属性是否被定义
if (isUndef(vnode.text)) {
// 二者都有 children
if (isDef(oldCh) && isDef(ch)) {if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue)
}
// vnode 有 children，oldVnode 没有
else if (isDef(ch)) {if (isDef(oldVnode.text)) api.setTextContent(elm, '')
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
}
// oldVnode 有 children，vnode 没有
else if (isDef(oldCh)) {removeVnodes(elm, oldCh, 0, oldCh.length - 1)
}
// 都没有 children，oldVnode 有 text
else if (isDef(oldVnode.text)) {api.setTextContent(elm, '')
}
}
// vnode 的 text 属性被定义并且和 oldVnode 的 text 属性值不同
else if (oldVnode.text !== vnode.text) {
// 如果 oldVnode 蕴含子元素
if (isDef(oldCh)) {removeVnodes(elm, oldCh, 0, oldCh.length - 1)
}
// 设置文本节点内容
api.setTextContent(elm, vnode.text!)
}
// 4. 执行用户设置的 postpatch 钩子函数
hook?.postpatch?.(oldVnode, vnode)
}updateChildren
diff 算法 的外围办法，同层比拟新旧节点 children 之间的差别并更新 dom。
一般比照 vs 同层比照
比照节点差别就是比照两个 dom 树之间的差别。
- 一般形式
获取第一颗树的每个节点和第二棵树的每一个节点进行比对，这样比对的工夫复杂度为 O(n^l)，l 示意树节点的层级数，如果一棵树的层级是 3，那么复杂度就是 O(n^3)
- 同层比照
因为在操作 dom 的时候，很少会将一棵 dom 树的父节点挪动更新到其子节点。因而，在比照时，只须要找两棵 dom 树的同级别子节点顺次比照，比对实现后而后再找下一级别的节点进行比对，这样的工夫复杂度为 O(n)。
diff 过程
因为虚构 Dom 的 diff 算法是同层比照两棵 dom 树，因而探索 diff 算法过程，也就是探索某一层级两组节点数组之间的比照过程。
diff 算法能够大抵分成两个步骤，以上面的两个数组为例：
let oldNodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
let newNodes = ['A', 'H', 'F', 'B', 'G']步骤一 重新排列旧的数组
此步骤目标是依据新的数组，将旧的数组重新排列，新数组中的每一项在旧数组中无外乎两种状况：
- 旧数组中存在，调整其到正确地位
如 newNodes 数组中的 B 项在 a 数组中存在，然而 oldNodes 数组中其地位不正确，根据 newNodes 数组的构造，B应该在 F 与G之间，因而须要调整 B 的地位。
- 旧数组不存在，在正确地位插入
如 newNodes 数组中的 H 在 oldNodes 数组中不存在，所以须要将其插入到 oldNodes 数组中，那么插入到哪个地位？依据 newNodes 的构造，应该将 H 插入到 A 的前面。
调整实现之后，oldNodes 应该变成如下：
let oldNodes = ['A', 'H', 'C', 'D', 'E', 'F', 'B', 'G']步骤一实现逻辑
整个步骤一通过一个循环就能够实现，将两个数组的开始、完结索引作为循环变量，每调整一次数组（挪动或者新增），就批改变量指向的索引，直到某一个数组的开始变量大于完结变量，那么阐明此数组中的每一个元素都被遍历过，循环完结。
- 设置循环开始的批示变量
let oldStartIdx = 0
let oldEndIdx = oldCh.length - 1
let oldStartVnode = oldCh[0]
let oldEndVnode = oldCh[oldEndIdx]
let newStartIdx = 0
let newEndIdx = newCh.length - 1
let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]用 8 个变量别离存储：
旧数组：开始索引，开始节点，完结索引，完结节点。
新数组：开始索引，开始节点，完结索引，完结节点。
- 设置循环执行条件
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {// 调整逻辑}当某个数组的开始索引变量大于完结索引变量时，循环完结。
- 调整逻辑
将旧数组的开始完结节点和新数组的开始完结节点进行比照，会呈现以下 5 种状况：
- 新旧数组的开始节点雷同
此种状况下，阐明旧数组中以后开始节点变量存储的开始节点地位是正确的，不须要挪动。
if (sameVnode(oldStartVnode, newStartVnode)) {
// 递归 diff 解决子节点
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
// 将起始节点，起始索引向后挪动一位
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
}- 新旧数组的完结节点雷同
此种状况下，阐明旧数组中以后完结节点变量存储完结节点地位是正确的，不须要挪动。
if (sameVnode(oldEndVnode, newEndVnode)) {patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
// 将完结节点，完结索引向前挪动一位
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
}- 旧数组的开始节点和新数组的完结节点雷同
此种状况下，阐明旧数组中的以后开始节点变量存储的开始节点地位不正确，应该调整到以后旧数组完结节点变量存储的完结节点之后。
也能够用上面的例子示意此种状况：
let oldNodes = ['A', 'B', 'C']
let newNodes = ['D', 'A']oldNodes 数组中的开始节点 A 和 newNodes 的完结节点 A 雷同，此时，如果根据 newNodes 来调整 oldNodes，须要将 A 挪动到 C 的前面。挪动实现后，oldNodes 应该变成：['B', 'C', 'A']。
if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
// 调整开始节点的地位，将其挪动到完结节点的前面
api.insertBefore(parentElm, oldStartVnode.elm!, api.nextSibling(oldEndVnode.elm!))
// 此时旧数组中的开始节点曾经被解决了，须要将开始索引指向下一位
oldStartVnode = oldCh[++oldStartIdx]
// 此时新数组中的完结节点相当于被解决了，须要将完结索引指向前一位
newEndVnode = newCh[--newEndIdx]
}- 旧数组的完结节点和新数组的开始节点雷同
此种状况下，阐明旧数组中以后的完结节点变量存储的完结节点地位不正确，应该将其挪动到旧数组以后开始节点变量存储的开始节点之前。
也就是：
let oldNodes = ['A', 'B', 'C']
let newNodes = ['C', 'D']将 oldNodes 调整为['C', 'A', 'B']
if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
// 将完结节点挪动到开始节点之前
api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!)
// 旧数组中的完结节点指向前一位
oldEndVnode = oldCh[--oldEndIdx]
// 新数组中的开始节点指向后一位
newStartVnode = newCh[++newStartIdx]
}
- 以上状况均不合乎
在这种状况下，只须要判断新数组初始节点在旧数组中是否存在，如果不存在，就在旧数组开始节点之前插入新数组的开始节点。如果存在，就将对应的节点挪动到旧数组开始节点之前。
如：
let oldNodes = ['A', 'B', 'D', 'C']
let newNodes = ['D', 'E']newNodes 的开始节点为 D，其在 oldNodes 数组中存在，所以将D 挪动到 A 节点之前，变为：['D', 'A', 'B', 'C']。
if (oldKeyToIdx === undefined) {
// 创立 key 与索引值的构造数组，不便查找
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
}
// 依据新数组的初始节点在旧数组中查找
idxInOld = oldKeyToIdx[newStartVnode.key as string]
// 不存在
if (isUndef(idxInOld)) {
// 创立一个和新数组开始节点雷同的 dom 节点，插入到旧数组开始节点之前
api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!)
}
// 存在
else {
// 获取旧数组中以后须要挪动的节点
elmToMove = oldCh[idxInOld]
// 如果 sel 不一样，同样认为不同，和不存在的解决逻辑一样
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]步骤二 解决重新排列后的数组
通过步骤一的解决，可能会呈现两种状况：
- 新数组被遍历完，旧数组没有遍历完。
如下例：
let oldNodes = ['A', 'B', 'C']
let newNodes = ['A', 'E']步骤一实现之后，oldNodes 数组变为 ['A', 'E', 'B', 'C']，此时 B 和C没有被遍历到。
在这种状况下，阐明 B 和C在新数组中不存在，间接删掉即可。
- 旧数组被遍历完，新数组没有遍历完。
如下例：
let oldNodes = ['A']
let newNodes = ['A', 'D', 'E']步骤一实现后，oldNodes 数组仍然为 ['A']，此时 newNodes 数组中的D 和E还没有被遍历到。
在这种状况下，阐明 D 和E是新增的元素，在旧数组中必定没有，间接将两个元素减少到相应地位即可。
步骤二实现逻辑
// oldStartIdx <= oldEndIdx 代表旧数组中有元素没有被遍历到
// newStartIdx <= newEndIdx 代表新数组中有元素没有被遍历到
if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
// 如果新数组中有残余元素
if (oldStartIdx > oldEndIdx) {before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm
// 间接将其增加到旧数组的相应地位。addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
} else {
// 如果旧数组中有残余元素
// 间接在旧数组中将其删除
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
}
}模块
snabbdom 为了保障框架的简洁高效，将款式、属性、事件等交给模块解决。
模块的定义非常简单，常见的就是在 create 和 update 生命周期钩子函数中依据用户输出批改 dom 节点。
以 updateAttrs 模块为例：
function updateAttrs (oldVnode: VNode, vnode: VNode): void {
// 比照批改两个 vnode 对应 ele 的 attrs
// ......
}
// 导出一个蕴含 create，update 钩子函数的对象，在 init 的时候，会将钩子函数增加到 cbs 中。export const attributesModule: Module = {create: updateAttrs, update: updateAttrs}