源码地址：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）） {undefined

 

        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left

 

      } else if （isUndef（oldEndVnode）） {undefined

 

        oldEndVnode = oldCh[--oldEndIdx]

 

 }

 

遍历判断1： 如果oldStartIdx的节点和newStartIdx节点相同，去patchVnode判断节点内部是否相同，oldStartIdx++，newStartIdx++     （patchVnode是详细比较两个节点内容的函数）

 

else if （sameVnode（oldStartVnode, newStartVnode）） {undefined

 

   // 两个节点相同，直接将该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）） {undefined

 

        // 两个节点相同，直接将该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 {undefined

 

        // 以上四种情况都不满足

 

        // 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）） {undefined

 

            // 两节点相同，执行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之间的节点删除