最近在看一些底层方面的知识。所以想做个系列尝试去聊聊这些比较复杂又很重要的知识点。学习就好比是座大山，只有自己去登山，才能看到不一样的风景，体会更加深刻。今天我们就来聊聊Vue中比较重要的vue虚拟（Virtual ）DOM和diff算法。
虚拟（Virtual ）DOM
Virtual DOM 其实就是一棵以 JavaScript 对象（VNode 节点）作为基础的树，用对象属性来描述节点，相当于在js和真实dom中间加来一个缓存，利用dom diff算法避免没有必要的dom操作，从而提高性能。当然算法有时并不是最优解，因为它需要兼容很多实际中可能发生的情况，比如后续会讲到两个节点的dom树移动。
上几篇文章中讲vue的数据状态管理结合Virtual DOM更容易理解，在vue中一般都是通过修改元素的state,订阅者根据state的变化进行编译渲染，底层的实现可以简单理解为三个步骤：
- 1、用JavaScript对象结构表述dom树的结构，然后用这个树构建一个真正的dom树，插到浏览器的页面中。
- 2、当状态改变了，也就是我们的state做出修改，vue便会重新构造一棵树的对象树，然后用这个新构建出来的树和旧树进行对比（只进行同层对比），记录两棵树之间的差异。
- 3、把2记录的差异在重新应用到步骤1所构建的真正的dom树，视图就更新了。
举例子：有一个 ul>li 列表，在template中的写法是：
<ul id='list'>
<li class='item1'>Item 1</li>
<li class='item2'>Item 2</li>
<li class='item3' style='font-size: 20px'>Item 3</li>
</ul>
vue首先会将template进行编译，这其中包括parse、optimize、generate三个过程。
parse会使用正则等方式解析template模版中的指令、class、style等数据，形成AST，于是我们的ul> li 可能被解析成下面这样
// js模拟DOM结构
var element = {
tagName: 'ul', // 节点标签名
props: { // DOM的属性，用一个对象存储键值对
class: 'item',
id: 'list'
},
children: [ // 该节点的子节点
{tagName: 'li', props: {class: 'item1'}, children: "Item 1"},
{tagName: 'li', props: {class: 'item2'}, children: "Item 2"},
{tagName: 'li', props: {class: 'item3', style: 'font-size: 20px'}, children: "Item 3"},
]
}
optimize过程其实只是为了优化后文diff算法的，如果不加这个过程，那么每层的节点都需要做比对，即使没变的部分也得弄一遍，这也违背了Virtual DOM 最初本质，造成不必要的资源计算和浪费。因此在编译的过程中vue会主动标记static静态节点，个人理解为就是页面一些不变的或者不受state影响的节点。比如我们的ul节点，不论li如何变化ul始终是不会变的，因此在这个编译的过程中可以个ul打上一个标签。当后续update更新视图界面时，patch过程看到这个标签会直接跳过这些静态节点。
最后通过generate 将 AST 转化成 render function 字符串，得到结果是 render 的字符串以及 staticRenderFns 字符串。大家听起来可能很困惑，首先前两步大家应该都差不多知道了，当拿到一个AST时，vue内部有一个叫element ASTs的代码生成器，犹如名字一样generate函数拿到解析好的AST对象，递归AST树，为不同的AST节点创建不同的内部调用的方法，然后组合可执行的JavaScript字符串，等待后面的调用。最后可能会变成这个样子：
function _render() {
with (this) {
return __h__(
'ul',
{staticClass: "list"},
[
" ",
__h__('li', {class: item}, [String((msg))]),
" ",
__h__('li', {class: item}, [String((msg))]),
"",
__h__('li', {class: item}, [String((msg))]),
""
]
)
};
}
整个Virtual DOM生成的过程代码中可简化为如下，有兴趣的同学可以去看具体对应的Vue源码，源码位置在src/compiler/index.js
export const createCompiler = createCompilerCreator(function baseCompile (
template: string,
options: CompilerOptions
): CompiledResult {
// 1.parse，模板字符串 转换成 抽象语法树(AST)
const ast = parse(template.trim(), options)
// 2.optimize，对 AST 进行静态节点标记
if (options.optimize !== false) {
optimize(ast, options)
}
// 3.generate，抽象语法树(AST) 生成 render函数代码字符串
const code = generate(ast, options)
return {
ast,
render: code.render,
staticRenderFns: code.staticRenderFns
}
})
diff算法以及key的作用
在最初的diff算法其实是"不可用的"，因为时间复杂度是O(n^3)。假设一个dom树有1000个节点，第一遍需要遍历tree1，第二遍遍历tree2,最后一遍就是排序组合成新树。因此这1000个节点需要计算1000^3 = 1亿次，这是非常庞大的计算，这种算法基本也不会用。
后面设计者们想出了一些方法，将时间复杂度由O(n^3)变成了O(n)，那么这些设计者是如果实现的？这也就是diff算法的优势所在，也是平常我们所理解到一些知识：
- 1、只比较同一级，不跨级比较
- 2、tag不相同，直接删掉重建，不再深度比较
- 3、tag和key，两者都相同，则认为是相同节点，不在深度比较
这就是一个简单的diff。通过同层的树节点进行比较而非对树进行逐层搜索遍历的方式，所以时间复杂度只有 O(n)。
之前在Virtual DOM中讲到当状态改变了，vue便会重新构造一棵树的对象树，然后用这个新构建出来的树和旧树进行对比。这个过程就是patch。比对得出「差异」，最终将这些「差异」更新到视图上。patch的过程也是vue及react的核心算法，理解起来比较困难。先看一些简单的图形了解diff是如何比较新旧VNode的差异的。
-
场景1：更新删除移动
-
场景2：删除新建
在简单的理解了diff算法实际操作的过程。为了让大家更好的掌握，因为这块还是比较复杂的。接下来将用伪代码的形式分析diff算法是如何进行深度优先遍历，记录差异， Vue的VDOM的diff算法借鉴的是snabbdom，不妨先从snabbdom Example入手
在vue中首先会对新旧两棵树进行深度优先的遍历，这样每个节点都会有一个唯一的标记。在遍历的同时，每遍历一个节点就会把该节点和新的树进行对比，有差异的话就会记录到一个对象里。
/* 创建diff函数，接受新旧量两棵参数 */
function diff (oldTree, newTree) {
var index = 0 //当前节点的标志
var patches = {} //用来记录每个节点差异的对象
dfsWalk(oldTree, newTree, index, patches) // 对两棵树进行深度优先遍历
return patches //返回不同的记录
}
function dfsWalk (oldNode, newNode, index, patches) {
var currentPatch = [] // 定义一个数组将对比oldNode和newNode的不同，记录下来
if (newNode === null) {
// 当执行重新排序时，真正的DOM节点将被删除，因此不需要在这里进行调整
} else if (_.isString(oldNode) && _.isString(newNode)) {
// 判断oldNode、newNode是否是字符串对象或者字符串值
if (newNode !== oldNode) {
//节点不同直接放入到数组中
currentPatch.push({ type: patch.TEXT, content: newNode })
}
} else if (oldNode.tagName === newNode.tagName && oldNode.key === newNode.key) {
// 节点是相同的，diff区分旧节点的props和子节点
// diff处理props
var propsPatches = diffProps(oldNode, newNode)
if (propsPatches) {
currentPatch.push({ type: patch.PROPS, props: propsPatches })
}
// diff处理子节点，如果有‘ignore’这个标志的。diff就忽视这个子节点
if (!isIgnoreChildren(newNode)) {
diffChildren(
oldNode.children,
newNode.children,
index,
patches,
currentPatch
)
}
} else {
// 节点不相同，用新节点直接替换旧节点
currentPatch.push({ type: patch.REPLACE, node: newNode })
}
}
function isIgnoreChildren (node) {
return (node.props && node.props.hasOwnProperty('ignore'))
}
/* 处理子节点diffChildren函数 */
function diffChildren (oldChildren, newChildren, index, patches, currentPatch) {
var diffs = listDiff(oldChildren, newChildren, 'key')
newChildren = diffs.children
if (diffs.moves.length) {
var reorderPatch = { type: patch.REORDER, moves: diffs.moves }
currentPatch.push(reorderPatch)
}
var leftNode = null
var currentNodeIndex = index
oldChildren.forEach(function (child, i) {
var newChild = newChildren[i]
currentNodeIndex = (leftNode && leftNode.count) // 计算节点的标识
? currentNodeIndex + leftNode.count + 1
: currentNodeIndex + 1
dfsWalk(child, newChild, currentNodeIndex, patches) // 深度遍历子节点
leftNode = child
})
}
/* 处理子节点的props diffProps函数 */
function diffProps (oldNode, newNode) {
var count = 0
var oldProps = oldNode.props
var newProps = newNode.props
var key, value
var propsPatches = {}
// Find out different properties
for (key in oldProps) {
value = oldProps[key]
if (newProps[key] !== value) {
count++
propsPatches[key] = newProps[key]
}
}
// Find out new property
for (key in newProps) {
value = newProps[key]
if (!oldProps.hasOwnProperty(key)) {
count++
propsPatches[key] = newProps[key]
}
}
// If properties all are identical
if (count === 0) {
return null
}
return propsPatches
}
// 暴露diff函数
module.exports = diff
感兴趣的话你也可查看简化版的diff。 完整简化版的diff算法
