一、前言
如果不了解 virtual dom，要理解 diff 的过程是比较困难的。
虚拟 dom 对应的是真实 dom，使用 document.CreateElement 和 document.CreateTextNode 创建的就是真实节点。
vue2.0 才开始使用了 virtual dom，有向 react 靠拢的意思。
文章首发地址：https://www.mwcxs.top/page/56…
二、虚拟 dom
首先，我们先看一下真实的 dom，打印出一个空元素的第一层属性，可以看到标准让元素实现的东西太多了。
如果每次都重新生成新的元素，对性能是巨大的浪费。
var mydiv = document.createElement(‘div’);
for(var item in mydiv){
console.log(item);
}
到底什么是 virtual dom 呢？通俗易懂的来说就是用一个简单的对象去代替复杂的 dom 对象。
举个简单的例子，我们在 body 里插入一个 class 为 a 的 div。
var mydiv = document.createElement(‘div’);
mydiv.className = ‘a’;
document.body.appendChild(mydiv);
对于这个 div 我们可以用一个简单的对象 mydivVirtual 代表它，它存储了对应 dom 的一些重要参数，在改变 dom 之前，会先比较相应虚拟 dom 的数据，如果需要改变，才会将改变应用到真实 dom 上。
// 伪代码
var mydivVirtual = {
tagName: ‘DIV’,
className: ‘a’
};
var newmydivVirtual = {
tagName: ‘DIV’,
className: ‘b’
}
if(mydivVirtual.tagName !== newmydivVirtual.tagName || mydivVirtual.className !== newmydivVirtual.className){
change(mydiv)
}
// 会执行相应的修改 mydiv.className = ‘b’;
// 最后 <div class=’b’></div>
为什么不直接修改 dom 而需要加一层 virtual dom 呢？很多时候手工优化 dom 确实会比 virtual dom 效率高，对于比较简单的 dom 结构用手工优化没有问题，但当页面结构很庞大，结构很复杂时，手工优化会花去大量时间，而且可维护性也不高，不能保证每个人都有手工优化的能力。至此，virtual dom 的解决方案应运而生。
virtual dom 是“解决过多的操作 dom 影响性能”的一种解决方案。
virtual dom 很多时候都不是最优的操作，但它具有普适性，在效率、可维护性之间达平衡。
virutal dom 的意义：
1、提供一种简单对象去代替复杂的 dom 对象，从而优化 dom 操作
2、提供一个中间层，js 去写 ui，ios 安卓之类的负责渲染，就像 reactNative 一样。
三、diff 算法
vue 的 diff 位于 patch.js 文件中，该算法来源于 snabbdom，复杂度为 O(n)。了解 diff 过程可以让我们更高效的使用框架。
一篇相当经典的文章 React’s diff algorithm 中的图，react 的 diff 其实和 vue 的 diff 大同小异。所以这张图能很好的解释过程。
特点：1、比较只会在同层级进行, 不会跨层级比较。
举个形象的例子
<!– 之前 –>
<div> <!– 层级 1 –>
<p> <!– 层级 2 –>
<b> aoy </b> <!– 层级 3 –>
<span>diff</Span>
</P>
</div>
<!– 之后 –>
<div> <!– 层级 1 –>
<p> <!– 层级 2 –>
<b> aoy </b> <!– 层级 3 –>
</p>
<span>diff</Span>
</div>
我们可能期望将 <span> 直接移动到 <p> 的后边，这是最优的操作。
但是实际的 diff 操作是：1、移除 <p> 里的 <span>；2、在创建一个新的 <span> 插到 <p> 的后边。因为新加的 <span> 在层级 2，旧的在层级 3，属于不同层级的比较。
四、源码分析
vue 的 diff 位于 patch.js 文件中，diff 的过程就是调用 patch 函数，就像打补丁一样修改真实 dom。
4.1patch 方法
function patch (oldVnode, vnode) {
if (sameVnode(oldVnode, vnode)) {
patchVnode(oldVnode, vnode)
} else {
const oEl = oldVnode.el
let parentEle = api.parentNode(oEl)
createEle(vnode)
if (parentEle !== null) {
api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl))
api.removeChild(parentEle, oldVnode.el)
oldVnode = null
}
}
return vnode
}
patch 函数有两个参数，vnode 和 oldVnode，也就是新旧两个虚拟节点。
在这之前，我们先了解完整的 vnode 都有什么属性，举个一个简单的例子:
// body 下的 <div id=”v” class=”classA”><div> 对应的 oldVnode 就是
{
el: div // 对真实的节点的引用，本例中就是 document.querySelector(‘#id.classA’)
tagName: ‘DIV’, // 节点的标签
sel: ‘div#v.classA’ // 节点的选择器
data: null, // 一个存储节点属性的对象，对应节点的 el[prop] 属性，例如 onclick , style
children: [], // 存储子节点的数组，每个子节点也是 vnode 结构
text: null, // 如果是文本节点，对应文本节点的 textContent，否则为 null
}
el 属性引用的是此 virtual dom 对应的真实 dom，patch 的 vnode 参数的 el 最初是 null，因为 patch 之前它还没有对应的真实 dom。
patch 的第一部分
if (sameVnode(oldVnode, vnode)) {
patchVnode(oldVnode, vnode)
}
sameVnode 函数就是看这两个节点是否值得比较，代码相当简单：
function sameVnode(oldVnode, vnode){
return vnode.key === oldVnode.key && vnode.sel === oldVnode.sel
}
两个 vnode 的 key 和 sel 相同才去比较它们，比如 p 和 span，div.classA 和 div.classB 都被认为是不同结构而不去比较它们。
如果值得比较会执行 patchVnode(oldVnode, vnode)，稍后会详细讲 patchVnode 函数。
当节点不值得比较，进入 else 中
else {
const oEl = oldVnode.el
let parentEle = api.parentNode(oEl)
createEle(vnode)
if (parentEle !== null) {
api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl))
api.removeChild(parentEle, oldVnode.el)
oldVnode = null
}
}
过程如下：
取得 oldvnode.el 的父节点，parentEle 是真实 domcreateEle(vnode) 会为 vnode 创建它的真实 dom，令 vnode.el = 真实 domparentEle 将新的 dom 插入，移除旧的 dom 当不值得比较时，新节点直接把老节点整个替换了最后
return vnode
patch 最后会返回 vnode，vnode 和进入 patch 之前的不同在哪？没错，就是 vnode.el，唯一的改变就是之前 vnode.el = null, 而现在它引用的是对应的真实 dom。
var oldVnode = patch (oldVnode, vnode) 至此完成一个 patch 过程。
4.2patchNode 方法
两个节点值得比较时，会调用 patchVnode 函数
patchVnode (oldVnode, vnode) {
const el = vnode.el = oldVnode.el
let i, oldCh = oldVnode.children, ch = vnode.children
if (oldVnode === vnode) return
if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {
api.setTextContent(el, vnode.text)
}else {
updateEle(el, vnode, oldVnode)
if (oldCh && ch && oldCh !== ch) {
updateChildren(el, oldCh, ch)
}else if (ch){
createEle(vnode) //create el’s children dom
}else if (oldCh){
api.removeChildren(el)
}
}
}
const el = vnode.el = oldVnode.el，让 vnode.el 引用到现在的真实 dom，当 el 修改时，vnode.el 会同步变化。
节点的比较有 5 种情况：
1、if (oldVnode === vnode)，他们的引用一致，可以认为没有变化。
2、if(oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text)，文本节点的比较，需要修改，则会调用 Node.textContent = vnode.text。
3、if(oldCh && ch && oldCh !== ch), 两个节点都有子节点，而且它们不一样，这样我们会调用 updateChildren 函数比较子节点，这是 diff 的核心，后边会讲到。
4、else if (ch)，只有新的节点有子节点，调用 createEle(vnode)，vnode.el 已经引用了老的 dom 节点，createEle 函数会在老 dom 节点上添加子节点。
5、else if (oldCh)，新节点没有子节点，老节点有子节点，直接删除老节点。
4.3updateChildren 方法
updateChildren (parentElm, oldCh, newCh) {
let oldStartIdx = 0, 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
let idxInOld
let elmToMove
let before
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVnode == null) {// 对于 vnode.key 的比较，会把 oldVnode = null
oldStartVnode = oldCh[++oldStartIdx]
}else if (oldEndVnode == null) {
oldEndVnode = oldCh[–oldEndIdx]
}else if (newStartVnode == null) {
newStartVnode = newCh[++newStartIdx]
}else if (newEndVnode == null) {
newEndVnode = newCh[–newEndIdx]
}else if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
}else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode)
oldEndVnode = oldCh[–oldEndIdx]
newEndVnode = newCh[–newEndIdx]
}else if (sameVnode(oldStartVnode, newEndVnode)) {
patchVnode(oldStartVnode, newEndVnode)
api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[–newEndIdx]
}else if (sameVnode(oldEndVnode, newStartVnode)) {
patchVnode(oldEndVnode, newStartVnode)
api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
oldEndVnode = oldCh[–oldEndIdx]
newStartVnode = newCh[++newStartIdx]
}else {
// 使用 key 时的比较
if (oldKeyToIdx === undefined) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 有 key 生成 index 表
}
idxInOld = oldKeyToIdx[newStartVnode.key]
if (!idxInOld) {
api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
newStartVnode = newCh[++newStartIdx]
}
else {
elmToMove = oldCh[idxInOld]
if (elmToMove.sel !== newStartVnode.sel) {
api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
}else {
patchVnode(elmToMove, newStartVnode)
oldCh[idxInOld] = null
api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
}
newStartVnode = newCh[++newStartIdx]
}
}
}
if (oldStartIdx > oldEndIdx) {
before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
}else if (newStartIdx > newEndIdx) {
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
}
}
直接看源码可能比较难以滤清其中的关系，我们通过图来看一下
首先，在新老两个 VNode 节点的左右头尾两侧都有一个变量标记，在遍历过程中这几个变量都会向中间靠拢。
当 oldStartIdx <= oldEndIdx 或者 newStartIdx <= newEndIdx 时结束循环。
索引与 VNode 节点的对应关系：
oldStartIdx => oldStartVnode
oldEndIdx => oldEndVnode
newStartIdx => newStartVnode
newEndIdx => newEndVnode
在遍历中，如果存在 key，并且满足 sameVnode，会将该 DOM 节点进行复用，否则则会创建一个新的 DOM 节点。
首先，oldStartVnode、oldEndVnode 与 newStartVnode、newEndVnode 两两比较一共有 2 *2= 4 种比较方法。
当新老 VNode 节点的 start 或者 end 满足 sameVnode 时，也就是 sameVnode(oldStartVnode, newStartVnode) 或者 sameVnode(oldEndVnode, newEndVnode)，直接将该 VNode 节点进行 patchVnode 即可。
如果 oldStartVnode 与 newEndVnode 满足 sameVnode，即 sameVnode(oldStartVnode, newEndVnode)。
这时候说明 oldStartVnode 已经跑到了 oldEndVnode 后面去了，进行 patchVnode 的同时还需要将真实 DOM 节点移动到 oldEndVnode 的后面。
如果 oldEndVnode 与 newStartVnode 满足 sameVnode，即 sameVnode(oldEndVnode, newStartVnode)。
这说明 oldEndVnode 跑到了 oldStartVnode 的前面，进行 patchVnode 的同时真实的 DOM 节点移动到了 oldStartVnode 的前面。
如果以上情况均不符合，则通过 createKeyToOldIdx 会得到一个 oldKeyToIdx，里面存放了一个 key 为旧的 VNode，value 为对应 index 序列的哈希表。从这个哈希表中可以找到是否有与 newStartVnode 一致 key 的旧的 VNode 节点，如果同时满足 sameVnode，patchVnode 的同时会将这个真实 DOM（elmToMove）移动到 oldStartVnode 对应的真实 DOM 的前面。
当然也有可能 newStartVnode 在旧的 VNode 节点找不到一致的 key，或者是即便 key 相同却不是 sameVnode，这个时候会调用 createElm 创建一个新的 DOM 节点。
到这里循环已经结束了，那么剩下我们还需要处理多余或者不够的真实 DOM 节点。