vue源码-diff算法

1.虚拟DOM的核心:diff算法(updateChildren函数)

2.功能: diff 算法的核心，对比新旧节点的 children，更新 DOM

3.执行过程

说明:

1. 要对比两棵树的差异，我们可以取第一棵树的每一个节点依次和第二课树的每一个节点比较，但是这样的时间复杂度为 O(n^3)
2. 在DOM 操作的时候我们很少很少会把一个父节点移动/更新到某一个子节点, 所以找同级别的子节点依次比较，然后再找下一级别的节点比较，这样算法的时间复杂度为 O(n)

在进行同级别节点比较的时候，首先会对新老节点数组的开始和结尾节点设置标记(索引)，遍历的过程中移动索引

1. 在对开始和结束节点比较的时候，总共有四种情况
   • oldStartVnode / newStartVnode (旧开始节点 / 新开始节点)
   • oldEndVnode / newEndVnode (旧结束节点 / 新结束节点)
   • oldStartVnode / oldEndVnode (旧开始节点 / 新结束节点)
   • oldEndVnode / newStartVnode (旧结束节点 / 新开始节点)

• 开始节点和结束节点比较，这两种情况类似
  • oldStartVnode / newStartVnode (旧开始节点 / 新开始节点)
    
  • oldEndVnode / newEndVnode (旧结束节点 / 新结束节点)
    

1. 如果 oldStartVnode 和 newStartVnode 是 sameVnode (key 和 sel 相同)
   • 调用 patchVnode() 对比和更新节点
     
   • 把旧开始和新开始索引往后移动 oldStartIdx++ / oldEndIdx++

1. oldStartVnode / newEndVnode (旧开始节点 / 新结束节点) 相同
   • 调用 patchVnode() 对比和更新节点
     
   • 把 oldStartVnode 对应的 DOM 元素，移动到右边
     • 更新索引

1. oldEndVnode / newStartVnode (旧结束节点 / 新开始节点) 相同
   • 调用 patchVnode() 对比和更新节点
     
   • 把 oldEndVnode 对应的 DOM 元素，移动到左边
     
   • 更新索引

如果不是以上四种情况

• 遍历新节点，使用 newStartNode 的 key 在老节点数组中找相同节点
  
  1. 如果没有找到，说明 newStartNode 是新节点
• 创建新节点对应的 DOM 元素，插入到 DOM 树中
  
  1. 如果找到了
• 判断新节点和找到的老节点的 sel 选择器是否相同
  
• 如果不相同，说明节点被修改了
  • 重新创建对应的 DOM 元素，插入到 DOM 树中
    
• 如果相同，把 elmToMove 对应的 DOM 元素，移动到左边

• 循环结束
  • 当老节点的所有子节点先遍历完 (oldStartIdx > oldEndIdx)，循环结束
    
  • 新节点的所有子节点先遍历完 (newStartIdx > newEndIdx)，循环结束
    

1. 如果老节点的数组先遍历完(oldStartIdx > oldEndIdx)，说明新节点有剩余，把剩余节点批量插入到右边

1. 如果新节点的数组先遍历完(newStartIdx > newEndIdx)，说明老节点有剩余，把剩余节点批量删除

4.核心代码

    // 地址: src/core/vdom/patch.js
    // diff 算法
  // 更新新旧节点的子节点
  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
    // removeOnly is a special flag used only by <transition-group>
    // to ensure removed elements stay in correct relative positions
    // during leaving transitions
    const canMove = !removeOnly
    if (process.env.NODE_ENV !== 'production') {
      checkDuplicateKeys(newCh)
    }
    // diff 算法
    // 当新节点和旧节点都没有遍历完成
    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)) {
        // oldStartVnode 和 newStartVnode 相同(sameVnode)
        // 直接将该 VNode 节点进行 patchVnode
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        // 获取下一组开始节点
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // 直接将该 VNode 节点进行 patchVnode
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        // 获取下一组结束节点
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        // oldStartVnode 和 newEndVnode 相同(sameVnode)
        // 进行 patchVnode，把 oldStartVnode 移动到最后
        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
        // oldEndVnode 和 newStartVnode 相同(sameVnode)
        // 进行 patchVnode，把 oldEndVnode 移动到最前面
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        // 以上四种情况都不满足
        // newStartNode 依次和旧的节点比较
        // 从新的节点开头获取一个，去老节点中查找相同节点
        // 先找新开始节点的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]
          // 如果使用 newStartNode 找到相同的老节点
          if (sameVnode(vnodeToMove, newStartVnode)) {
            // 执行 patchVnode，并且将找到的旧节点移动到最前面
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            oldCh[idxInOld] = undefined
            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
          } else {
            // 如果key相同，但是是不同的元素，创建新元素
            // same key but different element. treat as new element
            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)
    }
  }