源码地址：https://github.com/vuejs/vue
模块路径：srccorevdompatch.js
问题：diff算法主要是对相同节点的子节点进行的比较和更新，也就是相同级别节点的比较算法。dom对比更新，本着尽量减少dom的销毁和重建，所以diff算法尽量先移动，后增删
过程分析
比较旧VNode节点oldCh和新VNode节点newCh，创建四个索引进行比较：
两个索引oldStartIdx（旧VNode开始位置）和oldEndIdx（旧VNode结束位置）分别指向oldCh的开始和结束下标
两个索引newStartIdx（新VNode开始位置）和newEndIdx（新VNode开始位置）分别指向newCh的开始和结束下标
并创建四个索引位置对应的VNode节点oldStartVnode，oldEndVnode，newStartVnode，newEndVnode，代码如下：
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, vnodeToMove, refElm
- *
根据索引遍历节点 while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx）：
首先是异常情况判断，然后根据当前节点情况判断是否以下四种情况
if (isUndef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
} else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx]
}
遍历判断1： 如果oldStartIdx的节点和newStartIdx节点相同，去patchVnode判断节点内部是否相同，oldStartIdx++，newStartIdx++ (patchVnode是详细比较两个节点内容的函数)
else if (sameVnode(oldStartVnode, newStartVnode)) {
// 两个节点相同，直接将该VNode节点进行patchVnode
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
}
遍历判断2： 如果oldEndIdx的节点和newEndIdx节点相同，去patchVnode判断节点内部是否相同，oldEndIdx--，newEndIdx--
else if (sameVnode(oldEndVnode, newEndVnode)) {
// 两个节点相同，直接将该VNode节点进行patchVnode
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
}
遍历判断3： 如果oldStartIdx的节点和newEndIdx节点相同，去patchVnode判断节点内部是否相同，oldStartIdx++，newEndIdx--，把oldStartIdx对应节点向右移动
else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
// 进行patchVnode，把oldStartVnode移到最后
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
//canMove移动oldStartVnode节点到oldEndVnode后面
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
}
遍历判断4： 如果oldEndIdx的节点和newStartIdx节点相同，去patchVnode判断节点内部是否相同，oldEndIdx--，newStartIdx++，把oldEndIdx对应节点向左移动
else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
// oldEndVnode 和 newStartVnode相同，进行patchVnode
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
//，把oldEndVnode 移动到最前面
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
}
遍历判断5： 如果上述四种情况都不存在，则用新VNode当前的newStartVnode去旧VNode里找（尽量不新建dom，找到了就移动，找不到再新建）
如果找到了，则调用patchVnode去比较详细内容，并且移动这个节点到newStartIdx位置，
如果没找到，则创建新节点并插入
else {
// 以上四种情况都不满足
// newStartVnode依次和旧的节点进行比较
// 从新的节点开通取一个，去老节点中查找相同节点
// 先找新开始节点的key和老节点相同的索引，如果没找到再通过sameVnode找
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
// 如果没找到，创建节点并插入到最前面
if (isUndef(idxInOld)) { // 没找到 New element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
} else { //找到了 获取要移动的老节点
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
// 两节点相同，执行patchVnode
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldCh[idxInOld] = undefined
//并将找到的旧节点移动到最前面
canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
} else {// 两节点不同，创建新元素
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
}
}
newStartVnode = newCh[++newStartIdx]//移动索引
}
- *
遍历完成（走出while循环时说明肯定有新/旧节点被遍历完了）：
结束判断1：当结束时 oldStartIdx > oldEndIdx ，说明旧节点遍历完了，新节点没遍历完，则说明新节点比老节点多，把newStartIdx >到newEndIdx直接的节点插入到老节点后面
结束判断2：当结束时 newStartIdx > newEndIdx ，说明新节点遍历完了，旧节点没遍历完，则说明老节点比新节点多，把的oldStartIdx到oldEndIdx之间的节点删除
- *
举例
举例1（删除节点）：
3次遍历判断1，从前面依次往后遍历3次 [1,2,3] 都相同，索引走3次，此时oldStartIdx=3，newStartIdx=3（>newEndIdx跳出循环），oldEndIdx=4,newEndIdx=2（这两个没动）
遍历结束，此时oldStartIdx > oldEndIdx，说明旧节点有剩余，执行结束判断2，删除oldCh的 [4,5] 元素，结束
举例2（移动节点）：
2次遍历判断1，从前面开始对比2次，[1，2]相同，索引往后走2布，oldStartIdx=2，newStartIdx=2，oldEndIdx=onewEndIdx=4（没动）
1次遍历判断2，从后面开始对比，[ 5 ]相同，索引往前都1步，oldEndIdx=onewEndIdx=3（各减一次）
1次遍历判断3，判断
oldCh的oldStartIdx(2)节点[3]
newCh的newEndIdx(3)节点[3]
节点相同，所以 oldCh的[3]节点向右移动（移动到oldEndVnode后面，此时oldCh的[3,4]位置互换为[4,3]）
oldStartIdx++（3)，newEndIdx--(3)
2次遍历判断1，这次比较的时候是，oldCh的oldStartIdx(3)节点[3]和newCh的newEndIdx(3)节点[3]比较，节点相同，再比较依次，索引移动走出while循环，结束
遍历结束
核心代码：
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, vnodeToMove, refElm const canMove = !removeOnly if (process.env.NODE_ENV !== 'production') { checkDuplicateKeys(newCh) } 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, newCh, newStartIdx) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx] } else if (sameVnode(oldEndVnode, newEndVnode)) { patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx) oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx] } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx) 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, newCh, newStartIdx) canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm) oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx] } else { // 以上四种情况都不满足 // newStartVnode依次和旧的节点进行比较 // 从新的节点开通取一个，去老节点中查找相同节点 // 先找新开始节点的key和老节点相同的索引，如果没找到再通过sameVnode找 if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) // 如果没找到，创建节点并插入到最前面 if (isUndef(idxInOld)) { // New element createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx) } else { // 获取要移动的老节点 vnodeToMove = oldCh[idxInOld] if (sameVnode(vnodeToMove, newStartVnode)) { // 如果使用newStartVnode 找到相同的老节点 // 执行patchVnode，并将找到的旧节点移动到最前面 patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx) oldCh[idxInOld] = undefined canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm) } else { // same key but different element. treat as new element // 如果key相同，但是是不同的元素，创建新元素 createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx) } } newStartVnode = newCh[++newStartIdx] } } // 当结束时 oldStartIdx > oldEndIdx ，说明旧节点遍历完了，新节点没遍历完 if (oldStartIdx > oldEndIdx) { // 说明新节点比老节点多，把剩下的节点插入到老节点后面 refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue) } else if (newStartIdx > newEndIdx) { // 当结束时 newStartIdx > newEndIdx ，说明新节点遍历完了，旧节点没遍历完 removeVnodes(oldCh, oldStartIdx, oldEndIdx) } }