Vue的虚拟DOM与diff算法学习笔记 - Vue - 前端 | Sakura Snow = 雪之樱的小站 = 随缘记录

# 什么是虚拟 DOM 和 diff 算法

在前端发展的初期，前端工程师们使用 JQ 这样的框架对 DOM 进行命令式的操作，这种方式最大的好处是易学，直白，但在前端页面和业务逻辑不断复杂的今天，命令式的操作 dom 已经不适合大型项目的开发，随之而来的三大框架，vue，react， angular 均使用了声明式的操作 DOM，开发者只要描述状态和和 DOM 的映射关系，框架就会帮我们把状态转化成渲染好的视图，虚拟 DOM 正是状态和真实 DOM 之间的一个中间层，为什么要有这个中间层呢，因为操作 DOM 的代价是非常大的，虚拟 DOM 可以描述描述真实 dom 的信息，通过对比前后的虚拟 dom 找出 DOM 里真正需要的部分，从而减少 DOM 操作，提高性能。比较前后虚拟 dom 的算法就是 diff 算法，这是整个虚拟 dom 机制的最核心优化之一。

# VNode

VNode 本质上是一个 JS 对象，只是这个对象是用来描述真实 DOM 而已，Vue 的实现如下。( 函数参数里的？: 的意思是，这个参数可以没有，但是如果有的话就要是某个指定的类型，这是 flow 的语法）

	export default class VNode {
	constructor (
	tag?: string,
	data?: VNodeData,
	children?: ?Array,
	text?: string,
	elm?: Node,
	context?: Component,
	componentOptions?: VNodeComponentOptions,
	asyncFactory?: Function
	) {
	this.tag = tag // 标签属性
	this.data = data // 渲染成真实 DOM 后，节点上到 class attr style 事件等...
	this.children = children // 子节点，也上 vnode
	this.text = text // 文本
	this.elm = elm // 对应着真实的 dom 节点
	this.ns = undefined // 当前节点的 namespace（命名空间）
	this.context = context // 编译的作用域
	this.fnContext = undefined // 函数化组件上下文
	this.fnOptions = undefined // 函数化组件配置项
	this.fnScopeId = undefined // 函数化组件 ScopeId
	this.key = data && data.key // 只有绑定数据下存在，在 diff 的过程中可以提高性能
	this.componentOptions = componentOptions // 通过 vue 组件生成的 vnode 对象，若是普通 dom 生成的 vnode，则此值为空
	this.componentInstance = undefined // 当前组件实例
	this.parent = undefined //vnode、组件的占位节点
	this.raw = false // 是否为原生 HTML 或只是普通文本
	this.isStatic = false // 静态节点标识 \|\| keep-alive
	this.isRootInsert = true // 是否作为根节点插入
	this.isComment = false // 是否为注释节点
	this.isCloned = false // 是否为克隆节点
	this.isOnce = false // 是否为 v-once 节点
	this.asyncFactory = asyncFactory // 异步工厂方法
	this.asyncMeta = undefined // 异步 Meta
	this.isAsyncPlaceholder = false // 是否为异步占位
	}
	// 容器实例向后兼容的别名
	get child (): Component \| void {
	return this.componentInstance
	}
	}

实现比较简单，我就不过多赘述了，这里顺带介绍三个 VNode 类型

文本节点，只有 text 属性

	{
	text : "hello world"
	}

注释节点，只有 text 属性和 isComment 属性

	{
	text : "hello world",
	isComment : true
	}

元素节点，只有 tag（标签名），data（节点数据），children（子节点列表），context（当前组件的 vue.js 实例）

	{
	tag ： "div"，
	data : {...},
	children : [{...},{...}],
	context : {...}
	}

这三种之外还有克隆节点，组件节点，函数式组件节点，不过本文讨论的重点不在这，所以暂且省略。

# patch 和 patchVNode

将虚拟 DOM 渲染成真实 DOM 的操作是 patch。patch 中的核心是 diff 算法，diff 算法做的一个很重要的优化就是，只比较同层次的节点，这使 diff 的时间复杂度降到了 O（n）

patch 在 update 方法中被调用，代码如下

	Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) {
	const vm: Component = this
	if (vm._isMounted) {
	callHook(vm, 'beforeUpdate')
	}
	const prevEl = vm.$el
	const prevVnode = vm._vnode
	const prevActiveInstance = activeInstance
	activeInstance = vm
	vm._vnode = vnode
	if (!prevVnode) {
	// initial render
	vm.$el = vm.__patch__(
	vm.$el, vnode, hydrating, false /* removeOnly */,
	vm.$options._parentElm,
	vm.$options._refElm
	)
	} else {
	// updates
	// 更新视图
	vm.$el = vm.__patch__(prevVnode, vnode)
	}
	activeInstance = prevActiveInstance
	// update __vue__ reference
	if (prevEl) {
	prevEl.__vue__ = null
	}
	if (vm.$el) {
	vm.$el.__vue__ = vm
	}
	// if parent is an HOC, update its $el as well
	if (vm.$vnode && vm.$parent && vm.$vnode === vm.$parent._vnode) {
	vm.$parent.$el = vm.$el
	}
	// updated hook is called by the scheduler to ensure that children are
	// updated in a parent's updated hook.
	}

我们可以看到，vm_patch 执行时传入了两个参数，前一个参数代表旧的 VNode，第二个参数代表新的 VNode，比较旧 VNode 和新 VNode 的差异，和把 VNode 渲染成真实 DOM，就是在 patch 中完成的。而 patch 函数的返回值，重新赋值到 vm.$el 上，由此可见，patch 函数一般会传入 vue 挂载的根结点对应的 Vdom。

来看看 patch 的算法

	function patch(oldVnode, vnode, hydrating, removeOnly) {
	// 如果新 vnode 不存在，直接调用销毁钩子
	if (isUndef(vnode)) {
	if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
	return
	}

	let isInitialPatch = false
	const insertedVnodeQueue = []
	// 如果旧 Vnode 不存在，直接创建新的节点
	// empty mount (likely as component), create new root element
	if (isUndef(oldVnode)) {
	isInitialPatch = true
	createElm(vnode, insertedVnodeQueue)
	} else {
	//nodeType 只有元素节点才有，注释和文本节点都无
	// 可以通过判断 nodeType 判断是不是元素节点
	const isRealElement = isDef(oldVnode.nodeType)
	if (!isRealElement && sameVnode(oldVnode, vnode)) {
	// 如果新旧节点是同一个，调用 patchVnode 继续对比
	patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
	} else {
	if (isRealElement) {
	// mounting to a real element
	// check if this is server-rendered content and if we can perform
	// a successful hydration.
	if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
	oldVnode.removeAttribute(SSR_ATTR)
	hydrating = true
	}
	// 当旧的 VNode 是服务端渲染的元素，合并旧 VNode 到真实 DOM 上
	// 合并成功调用相应钩子，失败就报不一致警告
	if (isTrue(hydrating)) {
	if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
	invokeInsertHook(vnode, insertedVnodeQueue, true)
	return oldVnode
	} else if (process.env.NODE_ENV !== 'production') {
	warn(
	'The client-side rendered virtual DOM tree is not matching ' +
	'server-rendered content. This is likely caused by incorrect ' +
	'HTML markup, for example nesting block-level elements inside ' +
	'<p>, or missing <tbody>. Bailing hydration and performing ' +
	'full client-side render.'
	)
	}
	}
	// either not server-rendered, or hydration failed.
	// create an empty node and replace it
	// 如果不是服务端渲染或者合并到真实 DOM 失败，则创建一个空的 VNode 节点替换它
	oldVnode = emptyNodeAt(oldVnode)
	}

	// replacing existing element
	// 替换现有的元素
	const oldElm = oldVnode.elm
	const parentElm = nodeOps.parentNode(oldElm)

	// create new node
	// 创建新节点
	createElm(
	vnode,
	insertedVnodeQueue,
	// extremely rare edge case: do not insert if old element is in a
	// leaving transition. Only happens when combining transition +
	// keep-alive + HOCs. (#4590)
	oldElm._leaveCb ? null : parentElm,
	nodeOps.nextSibling(oldElm)
	)

	// update parent placeholder node element, recursively
	if (isDef(vnode.parent)) {
	let ancestor = vnode.parent
	const patchable = isPatchable(vnode)
	while (ancestor) {
	for (let i = 0; i < cbs.destroy.length; ++i) {
	cbs.destroy[i](ancestor)
	}
	ancestor.elm = vnode.elm
	if (patchable) {
	for (let i = 0; i < cbs.create.length; ++i) {
	cbs.create[i](emptyNode, ancestor)
	}
	// #6513
	// invoke insert hooks that may have been merged by create hooks.
	// e.g. for directives that uses the "inserted" hook.
	const insert = ancestor.data.hook.insert
	if (insert.merged) {
	// start at index 1 to avoid re-invoking component mounted hook
	for (let i = 1; i < insert.fns.length; i++) {
	insert.fns[i]()
	}
	}
	} else {
	registerRef(ancestor)
	}
	ancestor = ancestor.parent
	}
	}

	// destroy old node
	// 销毁旧节点
	if (isDef(parentElm)) {
	removeVnodes([oldVnode], 0, 0)
	} else if (isDef(oldVnode.tag)) {
	invokeDestroyHook(oldVnode)
	}
	}
	}

	invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
	return vnode.elm
	}

从代码中可以看出，patch 比较新旧 VNode 时，会先判断新旧 VNode 是否为同一个节点，如果是同一个节点，调用 patchVnode 方法来继续比较，否则，直接删除旧节点，直接重新渲染一个新节点。

那么怎么样算同一个节点呢，我们来看看 sameVNode 的实现，可以看出来 sameVNode 返回 true 时，两个节点不一定相同

	// 能判定为 sameVnode 必须满足下面的条件
	//key 相同
	//tag 相同（当前节点的标签名相同）
	//isComment 相同（是否为注释节点相同）
	//data 是否均为 undefined 或者均不为 undefined
	// InputType 必须相同
	function sameVnode (a, b) {
	return (
	a.key === b.key &&
	a.tag === b.tag &&
	a.isComment === b.isComment &&
	isDef(a.data) === isDef(b.data) &&
	sameInputType(a, b)
	)
	}
	function sameInputType (a, b) {
	if (a.tag !== 'input') return true
	let i
	const typeA = isDef(i = a.data) && isDef(i = i.attrs) && i.type
	const typeB = isDef(i = b.data) && isDef(i = i.attrs) && i.type
	return typeA === typeB
	}

然后我们看看 patchVnode 的实现

	function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
	// 如果传入的新旧 VNode 节点相同则直接返回
	if (oldVnode === vnode) {
	return
	}
	// 如果新旧节点均为静态节点，并且新旧节点的 key 相同，并且新节点是克隆节点或者只渲染一次的节点，可以直接把旧节点的 ele 或者 componentInstance 复制到新节点上，这样就不用再次把 VNode 转化成真实 DOM 了
	if (isTrue(vnode.isStatic) &&
	isTrue(oldVnode.isStatic) &&
	vnode.key === oldVnode.key &&
	(isTrue(vnode.isCloned) \|\| isTrue(vnode.isOnce))) {
	vnode.elm = oldVnode.elm
	vnode.componentInstance = oldVnode.componentInstance
	return
	}
	let i
	const data = vnode.data
	if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
	i(oldVnode, vnode)
	}
	const elm = vnode.elm = oldVnode.elm
	const oldCh = oldVnode.children
	const ch = vnode.children
	if (isDef(data) && isPatchable(vnode)) {
	for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
	if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
	}
	// 如果这个 VNode 节点没有 text 属性
	if (isUndef(vnode.text)) {
	if (isDef(oldCh) && isDef(ch)) {
	// 新老节点都有子节点，对子节点继续进行 diff 比较
	if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
	} else if (isDef(ch)) {
	// 如果老节点没有子节点而新节点存在子节点，先清空真实 DOM 的文本内容，然后为当前节点加入子节点
	if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
	addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
	} else if (isDef(oldCh)) {
	// 当新节点没有子节点而老节点有子节点的时候，则移除真实 DOM 的子节点
	removeVnodes(elm, oldCh, 0, oldCh.length - 1)
	} else if (isDef(oldVnode.text)) {
	// 当新老节点都无子节点的时候，只是文本的替换，因为这个逻辑中新节点 text 不存在，所以直接去除真实 DOM 的文本
	nodeOps.setTextContent(elm, '')
	}
	} else if (oldVnode.text !== vnode.text) {
	// 当新老节点 text 不一样时，直接替换这段文本
	nodeOps.setTextContent(elm, vnode.text)
	}
	// 调用 postpatch 钩子
	if (isDef(data)) {
	if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
	}
	}

总结一下，patchVNode 的规则是这样的

如果新旧 VNode 都是静态的，同时它们的 key 相同（代表同一节点），并且新的 VNode 是 clone 或者是标记了 once（标记 v-once 属性，只渲染一次），那么只需要替换 elm 以及 componentInstance 即可。
新老节点均有 children 子节点，则对子节点进行 diff 操作，调用 updateChildren，这个 updateChildren 也是 diff 的核心。
如果老节点没有子节点而新节点存在子节点，先清空老节点 DOM 的文本内容，然后为当前 DOM 节点加入子节点。
当新节点没有子节点而老节点有子节点的时候，则移除该 DOM 节点的所有子节点。
当新老节点都无子节点的时候，只是文本的替换。

你可能会疑惑 patch 和 patchNode 和 updateChildren 的区别，我们来看看他们调用的时机和实际的效果，patch 中的 patchNode 是在确定新旧节点是同一个节点的情况下调用的

	if (!isRealElement && sameVnode(oldVnode, vnode)) {
	// 如果新旧节点是同一个，调用 patchVNode 方法
	patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
	}

patchVnode 的用处有两个

把两个判定为 sameVnode 的节点进行进一步的比较和替换
调用 updateChildren 比较子节点

所以 patchVNode 仍然是在比较 patch 中的节点，只有 updateChildren 才是真正开始比较子节点。但是我一直搞不懂的是，如果 sameVnode 判定是 true 的话，两个节点应该基本属于一个相同的 VNode 类型，文字节点不可能有 children 属性，元素节点也不可能有 text 属性，所以 3 的情况，应该进不到 patchVNode 里..... 事实上我调试了半天也没调试出这种情况..... 暂且略过 8，有空再回头看看

# updateChildren

先上源码

	function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
	let oldStartIdx = 0
	let newStartIdx = 0
	let oldEndIdx = oldCh.length - 1
	let oldStartVnode = oldCh[0]
	let oldEndVnode = oldCh[oldEndIdx]
	let newEndIdx = newCh.length - 1
	let newStartVnode = newCh[0]
	let newEndVnode = newCh[newEndIdx]
	let oldKeyToIdx, idxInOld, elmToMove, refElm
	// removeOnly is a special flag used only by
	// to ensure removed elements stay in correct relative positions
	// during leaving transitions
	const canMove = !removeOnly
	// 循环遍历子节点数组
	while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
	if (isUndef(oldStartVnode)) {
	oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
	} else if (isUndef(oldEndVnode)) {
	oldEndVnode = oldCh[--oldEndIdx]
	} else if (sameVnode(oldStartVnode, newStartVnode)) {
	patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
	oldStartVnode = oldCh[++oldStartIdx]
	newStartVnode = newCh[++newStartIdx]
	} else if (sameVnode(oldEndVnode, newEndVnode)) {
	patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
	oldEndVnode = oldCh[--oldEndIdx]
	newEndVnode = newCh[--newEndIdx]
	} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
	patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
	canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
	oldStartVnode = oldCh[++oldStartIdx]
	newEndVnode = newCh[--newEndIdx]
	} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
	patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
	canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
	oldEndVnode = oldCh[--oldEndIdx]
	newStartVnode = newCh[++newStartIdx]
	} else {

	if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
	idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : null
	if (isUndef(idxInOld)) { // New element
	createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
	newStartVnode = newCh[++newStartIdx]
	} else {
	elmToMove = oldCh[idxInOld]
	/* istanbul ignore if */
	if (process.env.NODE_ENV !== 'production' && !elmToMove) {
	warn(
	'It seems there are duplicate keys that is causing an update error. ' +
	'Make sure each v-for item has a unique key.'
	)
	}
	if (sameVnode(elmToMove, newStartVnode)) {
	patchVnode(elmToMove, newStartVnode, insertedVnodeQueue)
	oldCh[idxInOld] = undefined
	canMove && nodeOps.insertBefore(parentElm, newStartVnode.elm, oldStartVnode.elm)
	newStartVnode = newCh[++newStartIdx]
	} else {
	// same key but different element. treat as new element
	createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
	newStartVnode = newCh[++newStartIdx]
	}
	}
	}
	}
	if (oldStartIdx > oldEndIdx) {
	refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
	addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
	} else if (newStartIdx > newEndIdx) {
	removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
	}
	}

变量指向如图

updateChildren 对比子节点的方式是从中间到两边对比，也就是两边向中间处理节点，图中 index 和指向的变量映射如下。

oldStartIdx 指向的节点是 oldStartVnode，旧 VNode 中未处理的第一个节点
oldEndIdx 指向的节点是 oldEndVnode，旧 VNode 中未处理的最后一个节点
newStartIdx 指向的节点是 newStartVnode，新 VNode 中未处理的第一个节点
newEndIdx 指向的节点是 newEndVnode，新 VNode 中未处理的最后一个节点

遍历中，如果存在 key，并且满足 sameVnode，会将该 DOM 节点进行复用，否则则会创建一个新的 DOM 节点。

在大多数情况下，节点的变化情况不大，可以进行预测，每次循环中先使用这四种情况进行比对，就可以处理大部分的情况。

oldStartVnode 和 newStartVnode 对比
oldEndVnode 和 newEndVnode 对比
oldStartVnode 和 newEndVnode 对比
oldEndVnode 和 newStartVnode 对比

如果调用 sameVNode 对比的结果是 true，调用 patchVnode 方法继续比较，不过如果是 3, 4 为 true 的情况，那就证明新 VNode 中节点的位置发生了改变，还需要移动真实 DOM，其中情况 3 会把 oldStartVnode 对应的真实 DOM 移动到所有未处理节点的后面，情况 4 会把 oldEndVnode 对应的真实 DOM 移动到所有未处理节点的前面。

如果以上情况均不符合，且如果 oldVNode 数组中的节点有 key 属性（通过 v-key 设置），则通过 createKeyToOldIdx 会得到一个名为 oldKeyToIdx 的对象，这个对象的键是 oldVNode 的 key 属性，值是 oldVNode 在节点数组中的下标。从这个对象上可以直接找到是否有与 newStartVnode 一致 key 的旧的 VNode 节点，如果两两个 key 相同的 VNode 满足 sameVnode，patchVnode 的同时会将这个真实 DOM（elmToMove）移动到 oldStartVnode 对应的真实 DOM 的前面。

但如果没有设置 key 属性，虽然也会调用 createKeyToOldIdx 会得到一个名为 oldKeyToIdx 的对象，但是这个对象上没有属性，所以不能作为 map 使用，vue 就会使用就地替换策略，直接创建新的真实 DOM 用于替换。还有找不到一致 key 或者 key 相同但 sameVnode 不满足的时候，也会直接创建真实 DOM，这就是为什么建议在 v-for 中使用 v-key 的原因，因为通过 key 生成对象，可以减少查找时间，并且可以对真实 DOM 进行移动操作，而不是创建新的节点用于就地替换。

来看看循环结束时的情况，因为循环能继续的条件是 oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx，那么只要新旧节点数量不一致就会出现出现一边 startIndex 和 oldIndex 没有碰头的情况，这时候我们要去处理真实 DOM 中多余的节点或者添加真实 DOM 中不够的节点。

当结束时 oldStartIdx > oldEndIdx，这说明了新的 VNode 节点比老的 VNode 节点多，也就是比真实 DOM 多，需要将剩下的（也就是新增的）VNode 节点插入到真实 DOM 节点中去，此时通过调用 addVnodes（批量调用 createElm 的接口）将这些节点加入到真实 DOM 中去。

当结束时 newStartIdx > newEndIdx 时，新的 VNode 节点比老的 VNode 节点少，也就是比真实 DOM 多少，需要将剩下的（也就是多余的）VNode 节点删除，通过调用 removeVnodes（批量调用浏览器 api 中的 element.removeChild）将这些多余的真实 DOM 删除。

vue

# 什么是虚拟 DOM 和 diff 算法

# VNode

# patch 和 patchVNode

# updateChildren

防抖节流柯里化

前端入坑指南