解析Vue2源码diff算法更新子节点逻辑以及优化

上节讲了对于节点的对比，但如果节点有子节点的话，逻辑会更复杂一点，所以这里学习一下怎么更新子节点。

1.更新子节点

如果新旧节点都有子节点数组的话，通过嵌套循环比对，外层循环新节点的子节点数组，内层循环旧节点，一一对比新旧节点的子节点来更新。以上过程会存在四个情况：

1.1创建子节点

如果新节点的子节点里面某个节点在旧节点子节点里面找不到相同的，说明这个子节点是之前没有的，是需要新增的，直接创建

1.2删除子节点

如果把新节点子节点里面都每一个子节点都循环完了后，发现旧的里面还有未处理的子节点，就说明这些是没用的需要废弃，直接删除

1.3移动子节点

如果找到相同的子节点，但是位置不同，说明需要调整该子节点的位置，就以新节点里的子节点为基准，调整旧里该节点的位置，使之相同。

1.4更新节点

如果找到了相同的子节点，并且所处位置也相同，那么就更新旧里的子节点，使之相同

接下来只用分别处理这四种情况即可

2.源码实现

// 源码位置： /src/core/vdom/patch.jsif (isUndef(idxInOld)) {    // 如果在oldChildren里找不到当前循环的newChildren里的子节点// 新增节点并插入到合适位置createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
} else {// 如果在oldChildren里找到了当前循环的newChildren里的子节点vnodeToMove = oldCh[idxInOld]// 如果两个节点相同if (sameVnode(vnodeToMove, newStartVnode)) {// 调用patchVnode更新节点patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)oldCh[idxInOld] = undefined// canmove表示是否需要移动节点，如果为true表示需要移动，则移动节点，如果为false则不用移动canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)} 
}

首先判断在旧节点里是否能找到当前循环的新节点里的子节点，如果找不到，那就是新增节点并且插入到合适为止；如果找得到，先对比两个节点是否相同，若相同则调用patchVnode更新节点，更新完后再看是否需要移动节点。

可以看到元源码和我们分析的是一模一样的。

但是，再思考一个问题，这样双层循环可以解决问题，但如果节点数量很多，这个算法的时间复杂度会很高，所以vue对此进行了优化。

3.优化介绍

如果有两个子节点数组如下

newChildren = ['新子节点1','新子节点2','新子节点3','新子节点4']
oldChildren = ['旧子节点1','旧子节点2','旧子节点3','旧子节点4']

根据之前的算法，我们接下来操作是这样的：外层循环new数组，用第一个节点去比较old所有节点，找到相同之后到下一个节点，用第二个节点去比对old所有节点…这样看来，其实损耗的时间复杂度是很多的。那么该如何优化呢？

vue是这样优化的，不按顺序去循环两个数组，而是可以先比较这两个数组的特殊位置，比如：

先把newChildren数组里的所有未处理子节点的第一个子节点和oldChildren数组里所有未处理子节点的第一个子节点做比对，如果相同，那就直接进入更新节点的操作；
如果不同，再把newChildren数组里所有未处理子节点的最后一个子节点和oldChildren数组里所有未处理子节点的最后一个子节点做比对，如果相同，那就直接进入更新节点的操作；
如果不同，再把newChildren数组里所有未处理子节点的最后一个子节点和oldChildren数组里所有未处理子节点的第一个子节点做比对，如果相同，那就直接进入更新节点的操作，更新完后再将oldChildren数组里的该节点移动到与newChildren数组里节点相同的位置；
如果不同，再把newChildren数组里所有未处理子节点的第一个子节点和oldChildren数组里所有未处理子节点的最后一个子节点做比对，如果相同，那就直接进入更新节点的操作，更新完后再将oldChildren数组里的该节点移动到与newChildren数组里节点相同的位置；
最后四种情况都试完如果还不同，那就按照之前循环的方式来查找节点。

在上述思路中，把：

newChildren数组里的所有未处理子节点的第一个子节点称为：新前；
newChildren数组里的所有未处理子节点的最后一个子节点称为：新后；
oldChildren数组里的所有未处理子节点的第一个子节点称为：旧前；
oldChildren数组里的所有未处理子节点的最后一个子节点称为：旧后；

接下来看看是如何实施的。

1.新前与旧前比较，如果相同那么直接更新。如果不同：

2.新后与旧后比较，如果相同直接更新，如果不同：

3.新后与旧前比较，如果相同则更新然后需要移动位置直到位置也相同，如果不同：

4.新前与旧后比较，如果相同则同上，如果还是不同的话，只能按照之前的循环方式找了。

在一定的情况下则会减少许多时间复杂度。

4.优化源码

/ 循环更新子节点function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {let oldStartIdx = 0               // oldChildren开始索引let oldEndIdx = oldCh.length - 1   // oldChildren结束索引let oldStartVnode = oldCh[0]        // oldChildren中所有未处理节点中的第一个let oldEndVnode = oldCh[oldEndIdx]   // oldChildren中所有未处理节点中的最后一个let newStartIdx = 0               // newChildren开始索引let newEndIdx = newCh.length - 1   // newChildren结束索引let newStartVnode = newCh[0]        // newChildren中所有未处理节点中的第一个let newEndVnode = newCh[newEndIdx]  // newChildren中所有未处理节点中的最后一个let oldKeyToIdx, idxInOld, vnodeToMove, refElm// removeOnly is a special flag used only by <transition-group>// to ensure removed elements stay in correct relative positions// during leaving transitionsconst canMove = !removeOnlyif (process.env.NODE_ENV !== 'production') {checkDuplicateKeys(newCh)}// 以"新前"、"新后"、"旧前"、"旧后"的方式开始比对节点while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if (isUndef(oldStartVnode)) {oldStartVnode = oldCh[++oldStartIdx] // 如果oldStartVnode不存在，则直接跳过，比对下一个} else if (isUndef(oldEndVnode)) {oldEndVnode = oldCh[--oldEndIdx]} else if (sameVnode(oldStartVnode, newStartVnode)) {// 如果新前与旧前节点相同，就把两个节点进行patch更新patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)oldStartVnode = oldCh[++oldStartIdx]newStartVnode = newCh[++newStartIdx]} else if (sameVnode(oldEndVnode, newEndVnode)) {// 如果新后与旧后节点相同，就把两个节点进行patch更新patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)oldEndVnode = oldCh[--oldEndIdx]newEndVnode = newCh[--newEndIdx]} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right// 如果新后与旧前节点相同，先把两个节点进行patch更新，然后把旧前节点移动到oldChilren中所有未处理节点之后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// 如果新前与旧后节点相同，先把两个节点进行patch更新，然后把旧后节点移动到oldChilren中所有未处理节点之前patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)oldEndVnode = oldCh[--oldEndIdx]newStartVnode = newCh[++newStartIdx]} else {// 如果不属于以上四种情况，就进行常规的循环比对patchif (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)idxInOld = isDef(newStartVnode.key)? oldKeyToIdx[newStartVnode.key]: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)// 如果在oldChildren里找不到当前循环的newChildren里的子节点if (isUndef(idxInOld)) { // New element// 新增节点并插入到合适位置createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)} else {// 如果在oldChildren里找到了当前循环的newChildren里的子节点vnodeToMove = oldCh[idxInOld]// 如果两个节点相同if (sameVnode(vnodeToMove, newStartVnode)) {// 调用patchVnode更新节点patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)oldCh[idxInOld] = undefined// canmove表示是否需要移动节点，如果为true表示需要移动，则移动节点，如果为false则不用移动canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)} else {// same key but different element. treat as new elementcreateElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)}}newStartVnode = newCh[++newStartIdx]}}if (oldStartIdx > oldEndIdx) {/*** 如果oldChildren比newChildren先循环完毕，* 那么newChildren里面剩余的节点都是需要新增的节点，* 把[newStartIdx, newEndIdx]之间的所有节点都插入到DOM中*/refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elmaddVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)} else if (newStartIdx > newEndIdx) {/*** 如果newChildren比oldChildren先循环完毕，* 那么oldChildren里面剩余的节点都是需要删除的节点，* 把[oldStartIdx, oldEndIdx]之间的所有节点都删除*/removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)}}

在我们的优化策略中，节点有可能从前面对比，也有可能从后面对比，所以我们有可能处理第一个也有可能处理最后一个，所以我们循环就不能简单的从前往后或者从后往前，而是应该从两边往中间。类似于一个双指针。

首先，我们先准备4个变量：

newStartIdx:newChildren数组里开始位置的下标；
newEndIdx:newChildren数组里结束位置的下标；
oldStartIdx:oldChildren数组里开始位置的下标；
oldEndIdx:oldChildren数组里结束位置的下标；

在循环的时候，每处理一个节点，就将下标向图中箭头所指的方向移动一个位置，开始位置所表示的节点被处理后，就向后移动一个位置；结束位置所表示的节点被处理后，就向前移动一个位置；由于我们的优化策略都是新旧节点两两更新的，所以一次更新将会移动两个节点。说的再直白一点就是：newStartIdx和oldStartIdx只能往后移动（只会加），newEndIdx和oldEndIdx只能往前移动（只会减）。

当开始位置大于结束位置时，表示所有节点都已经遍历过了。

那么我们开始解析源码：

1.如果oldStartVnode不存在，则直接跳过，将oldStartIdx加一

// 以"新前"、"新后"、"旧前"、"旧后"的方式开始比对节点
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if (isUndef(oldStartVnode)) {oldStartVnode = oldCh[++oldStartIdx] }
}

2.如果oldEndVnode不存在，则直接跳过，将oldEndIdx减一

else if (isUndef(oldEndVnode)) {oldEndVnode = oldCh[--oldEndIdx]
}

3.如果新前与旧前相同了，就把两个节点进行patch更新，同时oldStartIdx和newStartIdx都加一

else if (sameVnode(oldStartVnode, newStartVnode)) {patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)oldStartVnode = oldCh[++oldStartIdx]newStartVnode = newCh[++newStartIdx]
}

4.如果新后与旧后相同了，进行patch更新，同时oldEndIdx和newEndIdx都减一

else if (sameVnode(oldEndVnode, newEndVnode)) {patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)oldEndVnode = oldCh[--oldEndIdx]newEndVnode = newCh[--newEndIdx]
}

5.如果新后与旧前相同，进行patch更新，然后把旧节点移动到oldChild中所有未处理节点之后，最后把oldStartIdx加一，newEndIdx减一

else if (sameVnode(oldStartVnode, newEndVnode)) { patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))oldStartVnode = oldCh[++oldStartIdx]newEndVnode = newCh[--newEndIdx]
}

6.如果新前与旧后相同，进行更新，然后把旧后节点移动到oldChild所有未处理节点之前，把newStartIdx加一，oldEndIdx减一

else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved leftpatchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)oldEndVnode = oldCh[--oldEndIdx]newStartVnode = newCh[++newStartIdx]
}