源码地址：https://github.com/vuejs/vue
模块路径：src\core\vdom\patch.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)
}
}