上一篇说的是vnode怎样挂载到页面上，但是不可能一个数据的改变就把整个页面的dom都替换掉，这样的话效率也太低了。为了提高效率需要做的就是要找出具体改动的地方，尽量减少更新的dom。这就涉及到虚拟dom树的diff，这里就大概讲讲vue中虚拟dom树的diff算法。
function patchVnode (oldVnode, vnode) {
if (oldVnode === vnode) {
return
}
var data = vnode.data
var elm = vnode.elm = oldVnode.elm
var oldCh = oldVnode.children
var ch = vnode.children
if (!isDef(vnode.text)) {
if (isDef(oldCh) && isDef(ch)) { //若新老vnode都有子节点，则调用updateChildren方法进行diff，更新子节点
if (oldCh !== ch) updateChildren(elm, oldCh, ch)
} else if (isDef(oldCh)) { // 若只存在oldCh, 则移除oldCh对应的节点
removeVnodes(elm, oldCh, 0, oldCh.length -1)
} else if (isDef(ch)) { // 若只存在ch，则添加ch到父节点中
addVnodes(elm, null, ch, 0, ch.length - 1)
} else if (isDef(oldVnode.text)) { // 若都不存在，且oldVnode有text，则清空文本内容
nodeOps.setTextContent(elm, '')
}
} else if (vnode.text !== oldVnode.text){
nodeOps.setTextContent(elm, vnode.text)
}
}
function updateChildren (elm, oldCh, ch) {
var newStartIdx = 0,
oldStartIdx = 0,
newEndIdx = ch.length - 1,
oldEndIdx = oldCh.length - 1,
newStartVnode = ch[newStartIdx],
oldStartVnode = oldCh[oldStartIdx],
newEndVnode = ch[newEndIdx],
oldEndVnode = oldCh[oldEndIdx];
while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (!isDef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx]
} else if (!isDef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx]
// 下面四个if两两对比新旧vnode的头尾
} else if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode)
newStartVnode = ch[++newStartIdx]
oldStartVnode = oldCh[++oldStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode)
newEndVnode = ch[--newEndIdx]
oldEndVnode = oldCh[--oldEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) {
patchVnode(oldStartVnode, newEndVnode)
nodeOps.insertBefore(elm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh(++oldStartIdx)
newEndVnode = ch[--newEndIdx]
} else if (sameVnode(oldEndVnode, newStartVnode)) {
patchVnode(oldEndVnode, newStartVnode)
nodeOps.insertBefore(elm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = ch[++newStartIdx]
}
}
// 循环结束，若oldStartIdx大于oldEndIdx，说明剩余的newVnode是多出来的，调用addVnodes添加到文档中；
// 若newStartIdx > newEndIdx, 则说明剩余的oldVnode是多余的，调用removeVnodes方法删除。
if (oldStartIdx > oldEndIdx) {
var refElm = isDef(ch[newEndIdx + 1]) ? ch[newEndIdx + 1].elm : null
addVnodes(elm, refElm, ch, newStartIdx, newEndIdx)
} else if (newStartIdx > newEndIdx) {
removeVnodes(elm, oldCh, oldStartIdx, oldEndIdx)
}
}
vnode的diff主要是这段代码，patchVnode与updateChildren的循环调用。
patchVnode方法是对比新旧两个vnode，
首先判断新的vnode是否是文本节点，若是，直接把旧vnode对应的dom内容替换为文本。否则，进入一下逻辑：
1.若新老vnode都有子节点，则调用updateChildren方法进行diff，更新子节点（在updateChildren中又会循环调用patchVnode对比每一个子vnode）。
2.若只存在oldCh, 则移除oldCh对应的节点。
3.若只存在ch，则添加ch到父节点中。
4.若都不存在，且oldVnode有text，则清空文本内容。
接下来是关于updateChildren方法，也是vnode的diff算法的主要逻辑：
1.分别为新旧vnode的头尾设置一个标记，分别为newStartIdx, newEndIdx, oldStartIdx, oldEndIdx，循环遍历直到遍历完newVnodes或oldVnodes。
2.对比newStartVnode与oldStartVnode，若是同一个vnode，就调用patchVnode，并把newStartIdx与oldStartIdx分别+1。
3.同理对比newEndVnode与oldEndVnode。
4.对比oldStartVnode与newEndVnode，若是同一个vnode，调用patchVnode，分别对Idx做移位处理，并把oldStartVnode对应的真实dom移到右边。
5.同理对比oldEndVnode, newStartVnode。
6.循环结束，若oldStartIdx > oldEndIdx，说明剩余的newVnode是多出来的，调用addVnodes添加到文档中；若newStartIdx > newEndIdx, 则说明剩余的oldVnode是多余的，调用removeVnodes方法删除。
另外说一下sameVnode的判断逻辑：
// 这段代码是复制的源码中的，我个人实现的代码删除了isComment和sameInputType的判断
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)
)
}
以上updateChildren的逻辑是我按照vue的源码实现的简化的版本，vue源码中和我这里的逻辑不同的地方在于对于有key的节点的处理（相关代码），主要的逻辑为：
1.生成一个key与oldVnodeIdx对应的哈希表。
2.查找当前newStartVnode的key是否在这个哈希表中，是的话就认为是同一个节点，对这两个节点做patchVnode操作，并移动改节点到newStartVnode的位置。
另外，从updateChildren的4,5步操作可以看出，还是挺容易造成sameVnode的误判的，只要tag相同就容易被认为相隔很远的两个节点是同一个节点，从而造成了一大块的dom更新，因此vnode的diff算法只是在效率与正确性上都做了一些取舍，保证大多情况下的处理。因此有时候需要我们自己去提高diff的效率，通过源码我们可以看出给节点加key在一些情况是可以很有效的提升vnode的diff效率。
附上本文详细的代码注释与demo（相关代码）
网友评论