通过 snabbdom 库，来窥探 vue2.x 虚拟DOM 和 Diff 算法
前言
vue2.x 版本中的虚拟DOM 和 Diff 算法借鉴了 snabbdom 库，所以这篇文章以 snabbdom 库代码为例，来分析 虚拟 DOM 和 Diff 算法。本文仅仅是自己对 虚拟 dom 和diff 算法的一些分析和理解，如果有写的不对的地方，还请指正。本篇文章内部代码均是抽离出来的简化版本。想看源码的同学，请自行在 github 上搜索 snabbdom
虚拟 DOM 是什么 ?
虚拟 dom 其实就是由 js 对象，一个包含一些特定属性的对象，特定属性(比如 属性 sel 代表选择器，属性 data 是一个对象，里边包含 key 属性 calss 类名，id 等，children属性是数组，里边包含子节点，每个子节点也是一个包含一些特定属性的对象，text属性是文本节点，elm 表示真实 dom 节点)。这就是 虚拟 DOM 。如下图
在 sanbbdom 中，虚拟 dom 是通过 调用 h() 函数， h() 函数内部调用 vnode() 函数生成。
vnode() 函数
// 函数功能非常简单，就是把传入的 5 个参数组合成对象返回
/**
* sel: 选择器，标签名字
* data: 存放选择器属性， key props 等
* children: 子节点
* text: 文本节点
* elm: 真实dom节点
*/
export default function (sel, data, children, text, elm) {
let key = data.key
return {
sel, data, children, text, elm, key
}
}
h() 函数
import vnode from './vnode'
/**
* 低配版 h 函数，必须接收三个参数，
* 相当于他的重载功能比较弱
* 也就是说，调用的使用形态必须是下面的三种之一
* h('div', {}, '文字') ①
* h('div', {}, []) ②
* h('div', {}, h()) ③
* */
export default function (sel, data, c) {
// 检查参数个数
if (arguments.length !== 3) {
throw Error('参数错误，这是一个简易版本，必须要有三个参数，第二个参数是一个空对象')
}
// 检查参数 c 的类型
if (typeof c === 'string' || typeof c === 'number') {
// 说明现在调用 h 函数是形态 ①
return vnode(sel, data, undefined, c, undefined)
} else if (Array.isArray(c)) {
// 寿命现在调用 h 函数是形态 ②
let children = []
// 遍历 c， 手机 children
for (let i = 0; i < c.length; i++) {
//检查 c[i] 必须是一个对象如果不满足
if (!(typeof c[i] === 'object' && c[i].hasOwnProperty('sel'))) {
throw Error('传入的数组参数中有项不是 h 函数')
}
// 这里不用执行 c[i], 因为你的当我们写 h() 测试用例的时候，已经执行了，此时值需要收集好就行
children.push(c[i])
}
return vnode(sel, data, children, undefined, undefined)
} else if (typeof c === 'object' && c.hasOwnProperty('sel')) {
// 说明现在调用 h 函数是形态 ③
// 传入的 c 是唯一的 children
let children = [c]
return vnode(sel, data, children, undefined, undefined)
} else {
throw Error('传入的第三个参数类型不对')
}
}
h 函数内部的功能是把 传入进来的参数内容变成一个个的虚拟 dom 对象并组建成一颗 虚拟 dom 树结构。
这里进行了判断，如果 c 参数是 字符串或者数字类型说明是 文本节点，直接调用 vnode() 方法 转换成 虚拟 dom 对象，
如果 c 参数是 数组的话，说明是有子节点，需要遍历子节点，放入数组中，并用 vnode 函数包装一下，生成子节点 虚拟 dom 数组。
如果 c 参数是 对象类型，说明也是子节点，需要放入数组中，并用 vnode 函数包装，生成子节点 虚拟 dom 数组
代码示例：
const vnode1 = h('ul', {}, [
h('li', {key: 'A'}, 'A'),
h('li', {key: 'B'}, 'B'),
h('li', {key: 'C'}, 'C'),
h('li', {key: 'D'}, 'D'),
h('li', {key: 'E'}, 'E'),
h('li', {key: 'aa'}, [
h('p', {key: 'a1'}, '哈哈a1'),
h('p', {key: 'a2'}, '嘿嘿a2'),
]),
])
通过调用 h() 函数最后生成的结果如下：
{
sel: 'ul',
data: {},
children: [{
sel: 'li',
data: { key: 'D' },
text: 'D',
key: 'D'
}, {
sel: 'li',
data: { key: 'C' },
text: 'C',
key: 'C'
}, {
sel: 'li',
data: { key: 'B' },
text: 'B',
key: 'B'
}, {
sel: 'li',
data: { key: 'E' },
text: 'E',
key: 'E'
}, {
sel: 'li',
data: { key: 'F' },
text: 'F',
key: 'F'
}, {
sel: 'li',
data: { key: 'G' },
text: 'G',
key: 'G'
}, {
sel: 'li',
data: { key: 'aa' },
children: [{
sel: 'p',
data: { key: 'p1' },
text: '哈哈',
key: 'p1'
}, {
sel: 'p',
data: { key: 'p2' },
text: '嘿嘿',
key: 'p2'
}],
key: 'aa'
}]
}
最后生成的 vnode1 对象在作为patch(oldVnode, newVnode) 函数 的第二个参数传入，最终生成真实 dom 渲染到页面上。
patch() 函数 第一个参数是 旧的 虚拟节点。
patch 函数
import vnode from "./vnode"
import createElement from './createElement'
import patchVnode from './patchVnode'
// 手写 patch 上树 函数
export default function patch (oldVnode, newVnode) {
// console.log(oldVnode, newVnode)
// 判断传入的第一个参数，是DOM 节点还是虚拟节点？
if (oldVnode.sel === '' || oldVnode.sel === undefined) {
// 传入的第一个参数是 DOM 节点，此时要包装为虚拟节点
oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode)
}
// 判断 oldVnode 和 newVnode 是不是同一个节点
if (oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) {
// console.log('是同一个节点')
patchVnode(oldVnode, newVnode)
} else {
// console.log('不是同一个节点，暴力插入新的，然后删除旧的')
let newVnodeElm = createElement(newVnode)
// 插入到老节点之前
if (oldVnode.elm.parentNode && newVnodeElm) {
oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm)
}
// 删除老节点
oldVnode.elm.parentNode.removeChild(oldVnode.elm)
}
}
patch 函数接收两个参数， oldVnode, newVnode ，我们来分析下 patch 函数的内部实现：
1.先判断旧的虚拟DOM 是不是一个真实DOM 节点，如果是，需要把真实DOM 节点包装成 虚拟DOM节点，这里转换成虚拟节点是为了统一格式，和接下来的新老节点对比.
2. 判断新旧vnode 是不是同一个节点，如果是，就执行 patchVnode 函数,这部分放到下边讲解。
3.如果新旧dom 节点不同的话，通过 createElement() 函数通过新的虚拟DOM 树来生成真实DOM 并返回。然后 直接暴力插入新的，然后删除旧的。
这里用来判断新老节点是否相同的条件是 选择器(sel)相同, 并且 key 值也相同，才算是相同节点。这其实就是 key 属性的作用了，就是用来比较 新旧虚拟dom 是否是同一个元素的。
现在接着上边第3条继续来看下 createElement 函数， 第二条的 patchVnode 函数放在后边看
// 真正创建节点，将 vnode 创建为真实DOM 是孤儿节点，不进行插入
export default function createElement (vnode) {
// 创建一个 DOM 节点，这个节点现在还是孤儿节点
let domNode = document.createElement(vnode.sel)
// 有子节点还是有文本 ??
if (vnode.text !== '' && (vnode.children === undefined || vnode.children.length === 0)) {
// 他内部是文字
domNode.innerText = vnode.text
vnode.elm = domNode
} else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
// 他内部是子节点，就要递归创建节点
// console.log(vnode)
for (let i = 0; i < vnode.children.length; i++) {
// 得到当前这个 children
let ch = vnode.children[i]
// 创建出他的DOM， 一旦调用 createElement, 意味着：创建出 DOM 了
// 并且他的 elm 属性指向了创建出的 DOM ，但是还没有上树，是一个孤儿节点
let chDOM = createElement(ch)
// 往父元素中追加节点
domNode.appendChild(chDOM)
}
// 补充 elm 属性
vnode.elm = domNode
}
return vnode.elm
}
分析下createElement函数的功能：
1.首先是先通过js原生的dom操作方法，通过sel 选择器属性，创建出真实的DOM 元素。
2. 然后分两种情况来判断，子节点是文本节点，和子节点还包含子节点，这里因为是简化版本，所以这里只有两种情况，不允许出现兄弟节点或者父子节点之间出现 文字的情况
3. 如果子节点是文本节点，直接生成真实 文本节点，并赋值，这里为了简单，直接使用了 innerText 属性。然后把创建出来的真实的 dom 节点赋值给 elm 属性
4. 如果子节点还包含子元素，也就是 children 数组内还有子元素，这时候就需要遍历 children 数组，然后递归调用 自身，生成真实的dom 节点。也就是重复上边的步骤3, 最后在追加到 父元素中，最后给 elm 属性赋值为 创建出真实 dom,，最后返回 vnode.elm, 这时候的 vnode.elm 已经是真实dom 树结构了
接着继续再来看下 patchVnode
import createElement from "./createElement"
import updateChildren from './updateChildren'
export default function patchVnode (oldVnode, newVnode) {
// console.log(oldVnode, newVnode)
// 判断新旧 vnode 是否是同一个对象
if (oldVnode === newVnode) return
// 判断新的 vnode 有没有 text 属性
if (newVnode.text !== undefined && (newVnode.children === undefined || newVnode.children.length === 0)) {
// 新 vnode 有 text 属性，有 children
if (newVnode.text !== oldVnode.text) {
// 如果新虚拟节点中的 text 和 老的虚拟节点的 text 不同，那么直接让新的 text 写入老的 elm 中即可，
// 如果老的 elm 中有 children 那么也会立即消失掉
oldVnode.elm.innerText = newVnode.text
}
} else {
// 新 vnode 没有 text 属性，没有children 属性
// 判断老的有没有 children
if (oldVnode.children !== undefined && oldVnode.children.length > 0) {
// 老的有children ，新的有 children，此时就是最复杂的情况
updateChildren(oldVnode.elm, oldVnode.children, newVnode.children)
} else {
// 老的没有 children 新的有children
// 清空老的节点的内容
oldVnode.elm.innerHTML = ''
// 遍历新的 vnode 的子节点，创建 DOM， 上树
for (let i = 0; i < newVnode.children.length; i++) {
let dom = createElement(newVnode.children[i])
oldVnode.elm.appendChild(dom)
}
}
}
}
分析: 调用 patchVnode 的前提下是 选择器和 key 都相同，但是这只是这不代表内部的元素也相同，所以才调用了 patchVnode 函数，这个函数的功能也主要是用来比较，新旧vnode 选择器 和 key 都相同的情况下来比较内部元素是否相同，然后做相对应的处理
1.首先判断新旧 dom 是否是相等，也就是同一个引用地址，如果相等的话，说明是完全相同的，直接return 不在继续执行
2.判断 newVnode 有没有 text 属性，如果有，而且 newVnode 的 text 也就是文本节点，和 oldVnode 文本节点不同，直接把 newVnode 的文本节点，赋值给 oldVnode 的文本节点。
3. 如果 newVnode 的 text 节点没有值，说明就是有子节点。
4. 如果 oldVnode 的 children 数组有值，并且 newVnode 的children 也有值，说明新旧 vnode 都有子节点。这时候就是执行 updateChildren 函数，进行最核心的 diff 比较。这里放到下边讲。
5. 如果 oldVnode 的 children 数组没有值，说明是只有 newVnode 有子节点，oldVnode 没有子节点。这时候要清空 oldVnode 的 文本节点，然后把 newVnode 的子节点遍历并通过 clreateElement 生成真实dom 节点追加到旧的vnode 中
接下来继续看 updateChildren(parentElm, oldCh, newCh) 函数，最核心的 diff 算法部分，也是最复杂的部分
// diff 比较算法核心部分
import createElement from "./createElement"
import patchVnode from "./patchVnode"
// 判断是否为同一个元素
function checkSameVnode (a, b) {
return a.sel === b.sel && a.key === b.key
}
export default function updateChildren (parentElm, oldCh, newCh) {
// 声明相关变量
// 旧前
let oldStartIdx = 0
// 新前
let newStartIdx = 0
// 旧后
let oldEndIdx = oldCh.length - 1
// 新后
let newEndIdx = newCh.length - 1
// 旧前节点
let oldStartVnode = oldCh[0]
// 旧后节点
let oldEndVnode = oldCh[oldEndIdx]
// 新前节点
let newStartVnode = newCh[0]
// 新后节点
let newEndVnode = newCh[newEndIdx]
let keyMap = null
// 开始遍历
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVnode == null) {
oldStartVnode = oldCh[++oldStartIdx]
}
else if (oldEndVnode == null) {
oldEndVnode = oldCh[--oldEndIdx]
}
else if (newStartVnode == null) {
newStartVnode = newCh[++newStartIdx]
}
else if (newEndVnode == null) {
newEndVnode = newCh[--newEndVnode]
}
else if (checkSameVnode(oldStartVnode, newStartVnode)) { // 新前和旧前
console.log('①新前和旧前命中')
patchVnode(oldStartVnode, newStartVnode)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
}
else if (checkSameVnode(oldEndVnode, newEndVnode)) { // 新后和旧后
console.log('②新后和旧后命中')
patchVnode(oldEndVnode, newEndVnode)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
}
else if (checkSameVnode(oldStartVnode, newEndVnode)) { // 新后和旧前
console.log('③新后和旧前命中')
// 当 ③新后和旧前命中的时候，此时要移动节点。移动新后指向的这个节点到老节点的旧后之后的后面
patchVnode(oldStartVnode, newEndVnode)
parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
}
else if (checkSameVnode(oldEndVnode, newStartVnode)) { // 新前和旧后
console.log('④新前和旧后命中')
// 当④新前和旧后命中的时候，此时要移动节点，移动新节点指向的节点到老节点旧前之前
patchVnode(oldEndVnode, newStartVnode)
parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
}
else {
console.log('以上四种情况都没匹配到')
// 制作 keyMap 一个映射对象，这样就不用每次都遍历老对象了
if (!keyMap) {
keyMap = {}
// 从 oldStartIdx 开始， 到 oldEndIdx 结束，创建 keyMap 映射对象
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
if (oldCh[i] && oldCh[i].key) {
const key = oldCh[i].key
keyMap[key] = i
}
}
}
// console.log(keyMap)
// 寻找当前这项 （newStartIdx） 这项在 keyMap 中的映射的位置序号
// console.log(keyMap)
const idxInOld = keyMap[newStartVnode.key]
// console.log(idxInOld)
if (idxInOld === undefined) {
// 判断，如果 idxInOld 是 undefined 表示他是全新的项
// 被加入的项（就是newStartVnode 这项）现在还不是真正的DOM 节点
parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm)
} else {
// 如果不是 undefined 不是全新的项，而是要移动
const elmToMove = oldCh[idxInOld]
patchVnode(elmToMove, newStartVnode)
// 把这项设置为 undefined， 表示我已经处理完这项了
oldCh[idxInOld] = undefined
// 移动，调用 insertBefore 也可以实现移动
parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm)
}
// 指针下移，只移动新的头
newStartVnode = newCh[++newStartIdx]
}
}
// 匹配完以后继续看看有没有剩余的，循环结束以后， newStartIdx 小于 newEndIdx
if (newStartIdx <= newEndIdx) {
// console.log(oldStartIdx)
console.log('newVnode 还有剩余节点没处理，是新增项，把所有的剩余的节点，都要追加到 oldEndIdx 之后')
// console.log(newStartIdx, newEndIdx)
// 插入的标杆
const before = oldCh[oldEndIdx - 1] === undefined ? null : oldCh[oldEndIdx - 1].elm
// 循环剩余节点然后插入
// console.log(before)
for (let i = newStartIdx; i <= newEndIdx; i++) {
// insertBefore 方法可以自动识别 null， 如果是 null 就会自动排到队尾去。和 appendChild 是一致了。
// newCh[i] 现在还没有真正的DOM， 所以要调用 createElement() 函数变为DOM
parentElm.insertBefore(createElement(newCh[i]), before)
}
} else if (oldStartIdx <= oldEndIdx) {
console.log('oldVnode 还有剩余节点没有处理，要删除')
// console.log(oldStartIdx, oldEndIdx)
// 批量删除 oldStartIdx 和 oldEndIdx 指针之间的项
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
if (oldCh[i]) {
parentElm.removeChild(oldCh[i].elm)
}
}
}
}
这个方法接受三个参数，第一个参数是是 旧的vnode 的 最外层的真实 dom 节点，是用来比较完成插入真实dom 的时候做为坐标元素使用的，第二个 旧的 vnode 的children 子元素数组，第三个是 新的 vnode 的children 子元素数组
顶部最前边的 八个变量，先解释下，
oldStartIdx = 0 是指针，也就是索引，初始值是 0 ，等于 旧子节点数组的 第一个元素的索引值。称之为 旧前
newStartIdx = 0 是指针，也就是索引，初始值是 0 ，等于 新子节点数组的 第一个元素的索引值 ，称之为 新前
oldEndIdx = oldCh.length - 1 是指针，也是索引，等于 旧子节点数组的 最后的元素的索引值，称之为 旧后。
newEndIdx = newCh.length - 1 是指针，也是索引，等于 新子节点数组的 的最后一个元素的索引值，称之为 新后
oldStartVnode = oldCh[0] 是对象，等于 旧子节点数组的 第一个元素，成为旧前节点
oldEndVnode = oldCh[oldEndIdx] 是对象，等于 旧子节点数组的最后一个元素，称为 旧后节点
newStartVnode = newCh[0] 是对象，等于新子节点数组的第一个元素，称为 新前节点
newEndVnode = newCh[newEndIdx] 是对象，等于新子节点数组的最后一个元素，称为 新后节点。
这里的diff 算法使用了双端比较，所谓双端比较其实是头尾比较和交叉比较，总共四种比较方式:
- 新前节点 和 旧前节点 比较，如果相同， 新前和旧前的指针同时下移，比较新旧子节点数组的第二个元素，如果不同，就要进行第二种比较方式
- 新后节点 和 旧后节点 比较，如果相同， 新后和旧后的指针同时上移，比较新旧子节点数组的倒数第二个元素，如果不同，进行第三种比较方式。
- 新后节点 和 旧前节点 比较，如果相同， 此时说明需要移动节点，移动新后指向的这个节点的元素到 老节点的 旧后指向的节点之后，然后新后指针上移，旧前指针下移，如果不相同的话进行第四种比较方式。
- 新前节点 和 旧后节点 比较，如果相同，此时说明需要移动元素，移动新前指向的这个节点的元素 到 老节点的， 旧前指向的这个节点的之前，然后新前指针下移，旧后指针上移，
这时候需要遍历子节点，然后通过上边的四种方式进行比较，如果以上四种方式都没有匹配到的情况下，需要生成一个 keyMap 对象，这个对象中保存了所有旧的子节点的key 值所对应的索引，
然后在 keyMap 对象中寻找 新前节点的key 值，
如果没有，说明是全新的项，直接插入到 旧前节点 之前，
如果 在 keyMap 对象中找到了 新前节点的 key 值，说明是需要移动节点，然后把 旧的子节点列表中对应的这项，先单独拿出来，在通过 patchVnode 进行比较内部是否还有子节点，然后给旧子节点列表中对应的这项 设置成 undefined , 然后把拿出来的这项插入到 当前旧前节点的前边。做完这些之后，新前指针要下移，
经过上边一系列的匹配和移动节点，最后还有剩余的项，如果是旧节点先虚幻完毕，说明新节点中有要插入的节点，遍历 剩余的节点，都追加到 旧后之后，
如果是新节点先循环完毕，如果老节点中还有剩余的节点，说明他们都是要被删除的节点。遍历剩余节点，并执行删除操作即可。
最后附上一份逻辑分析图
参照上图的逻辑分析代码，会比较清晰一些。
至此 diff 算法叙述完毕，如果有写的不对的地方还请指正。
通过上述文章大致已经了解到 虚拟 dom 和 diff 算法的内部实现原理，下边我们要思考下，为什么要使用 虚拟dom 了
这就要说到真实dom ，其实真实 dom 上的属性很多，远远不止我们工作中常用的 class id data-xxx href 等等属性，下图是输出的 div 元素上的所有属性
由此可见，如果我们频繁操作真实 dom 的情况下，是很耗费性能的，
而 虚拟 DOM 就是用一个原生的 JS 对象去描述一个 DOM 节点，所以它比创建一个 DOM 的代价要小很多
为什么在 vue 元素中使用key属性，到底有什么作用
key属性主要是在 在同级的 新旧虚拟dom 做diff 比较的时候，用来判断是否是同一个元素的唯一标识，通过这个唯一标识，可以快速的比较出是否是同一个元素，还可以生成旧的vnode 的映射，用来检测出可以重复利用的 旧的 vnode 节点，加以复用，并且可以保证渲染顺序的准确性。