dom-diff 概述

比拟只会在同层级进行, 不会跨层级比拟

Vue2.x diff 算法

1.vue2.x dom-diff 算法外围源码

function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
      var oldStartIdx = 0;// 旧节点开始 index
      var newStartIdx = 0;// 新节点开始 index
      var oldEndIdx = oldCh.length - 1;// 旧节点完结 index
      var oldStartVnode = oldCh[0];// 旧节点开始节点 VNode
      var oldEndVnode = oldCh[oldEndIdx];// 旧节点完结节点
      var newEndIdx = newCh.length - 1;// 新节点完结 index
      var newStartVnode = newCh[0];// 新节点开始节点 VNode
      var newEndVnode = newCh[newEndIdx];// 新节点完结虚构节点 VNode

      // 外围 dom-diff 算法
      // 新旧节点两个指针，做比拟
      while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
       //1. 旧开始节点 === undefined
        if (isUndef(oldStartVnode)) {oldStartVnode = oldCh[++oldStartIdx];
      //2. 旧完结节点 === undefined
        } else if (isUndef(oldEndVnode)) {oldEndVnode = oldCh[--oldEndIdx];

      //3. 旧开始节点 === 新开始节点
        } else if (sameVnode(oldStartVnode, newStartVnode)) {patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
          oldStartVnode = oldCh[++oldStartIdx];
          newStartVnode = newCh[++newStartIdx];
          
      //4. 旧完结节点 === 新完结节点
        } else if (sameVnode(oldEndVnode, newEndVnode)) {patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);
          oldEndVnode = oldCh[--oldEndIdx];
          newEndVnode = newCh[--newEndIdx];
          
      //5. 旧开始节点 === 新完结节点
        } else if (sameVnode(oldStartVnode, newEndVnode)) {patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);

          // 操作实在 dom: 将老开始节点搁置在老完结节点的前面, 占了老节点的完结节点地位
          canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm));
          oldStartVnode = oldCh[++oldStartIdx];
          newEndVnode = newCh[--newEndIdx];
          
      //6. 旧完结节点 === 新开始节点
        } else if (sameVnode(oldEndVnode, newStartVnode)) {patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
         
          // 操作实在 dom：将完结节点搁置在开始节点后面，因为这里指针有挪动，作用就是本来的地位
          canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
          oldEndVnode = oldCh[--oldEndIdx];
          newStartVnode = newCh[++newStartIdx];
          
      //7. 都不是
        } else {if (isUndef(oldKeyToIdx)) { 
            // 返回老节点的 key-index 的映射表
            oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx); 
          }

          idxInOld = isDef(newStartVnode.key)
            ? oldKeyToIdx[newStartVnode.key]
            : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);

          //index 不存在，就是新增的元素
          if (isUndef(idxInOld)) { 
            
            // 实操 dom：新增 VNode, 并且增加到 dom 中
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
          } else {
            // 不是新增元素，则挪动
            // 须要挪动的 VNode
            vnodeToMove = oldCh[idxInOld];
            // 比拟须要挪动的 VNode 和当初新开始节点是否雷同
            if (sameVnode(vnodeToMove, newStartVnode)) {
              // 打补丁，以及遍历子节点
              patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
              // 将老虚构 dom 此处的 VNode 删除
              oldCh[idxInOld] = undefined;
                // 实操 dom
              canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);
            } else {createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
            }
          }
          newStartVnode = newCh[++newStartIdx];
        }
      }
      /*
        1. 如果开始下标大于完结下标，阐明遍历老节点遍历完结
        2. 老节点遍历结束，新节点的下标 + 1 的值，增加进去
        3. 如果新节点遍历完了，就删除老节点中开始到完结下标的值
      */
      if (oldStartIdx > oldEndIdx) {refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;
        addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
      } else if (newStartIdx > newEndIdx) {
        // 老的没有遍历完，新的遍历完了
        // 删除老的的节点，从 start 开始，end 完结，包含 end
        // 这里原先挪动了节点，用 undefined 占位，间接删除不影响任何节点
        removeVnodes(oldCh, oldStartIdx, oldEndIdx);
      }
    }

2. 整体逻辑图

3. 案例剖析

realDom
1 2 3 4 5 6 7 8 9 10
//old VNode
l                           r
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
//new VNode
a                             b
[1, 9, 11, 7, 3, 4, 5, 6, 2, 10]

**
留神这里比拟的都是虚构 dom 节点：实在 dom 的挪动不影响虚构 dom 节点值，可参照动图一起看

1. 新旧头比拟，直到第一个不雷同的节点：l 和 a 都向右挪动一位，都为 1
2. 新旧尾比拟，直到第一个不雷同的节点：r  和 b 都向左挪动一位，都为 9

3. 旧头和新尾比拟，雷同的话，开始挪动实在的 dom：

   • 旧头实在 dom 挪动到旧尾紧跟其后的兄弟节点的后面：实在 dom 中，2 挪动到 10 后面，原生节点插入方式实现
   • 指针挪动：旧开始指针向右挪动一位，新完结指针向左挪动一位 此时，l  变成了 2，b  变成了 8
   • 此时的实在 dom 为：1 3 4 5 6 7 8 9 2 10 

4. 旧尾和新头比拟，雷同的话，挪动实在 dom：

   • 旧尾实在 dom 挪动到旧头节点的 el 的后面：实在 dom 中，9 挪动到 3 的后面
   • 旧尾指针向左挪动一位，新头指针向右挪动一位，此时，a 变成了 2，r 变成了 8
   • 此时的实在 dom 为：1 9 3 4 5 6 7 8 2 10

5. 此时四个指针曾经不满足下面四种状况了，就须要进一步解决

   1. 首先 遍历残余老节点，返回一个 key:oldIndex 映射表
   2. 新节点的开始节点在这个映射表中能找到对应的 oldIndex，阐明在老节点中存在这个节点，只须要挪动即可
   3. 如果不存在，则须要新建节点，并且插入到指定的地位

接着剖析案例：

• 剩下的老节点为：[3, 4, 5, 6, 7, 8]  映射表为 {3: 2, 4: 3, 5: 4, 6: 5, 7: 6, 8: 7} 

剩下的新节点的为 [11, 7, 3, 4, 5, 6]  此时 11 在映射表中，没有查问到，阐明是新增的节点

1. 接着剖析：此时老节点残余 3,4,5,6,7,8 新节点残余 7,3,4,5,6 此时又合乎状况五。

   • 先找到 7 在老节点的 index , 依据映射表，oldIndex 为 6 阐明在老节点中存在，只须要挪动
   • 将 7 实在 dom 中的 el 挪动到老开始节点的 el 后面，也就是实在 dom 中 3 的后面
   • 将老节点中 oldIndex 这个节点设置为 undefined，前面会讲作用
   • 新开始指针向右挪动一位，a 变成了 4
   • 此时的实在 dom :1 9 11 7 3 4 5 6 8 2 10
2. 此时老节点残余 3,4,5,6,7,8 新节点残余 3,4,5,6 此时合乎状况一，头头比拟，遍历完新节点，循环完结

3. 接下来是循环完结后的解决，也就是查看新旧节点是否都齐全遍历

   1. 此时旧节点还未齐全遍历，剩下 7,8 , 阐明这是须要删除的节点
   2. 因为 7 是被挪动的节点，在挪动之后，将其虚构节点数组中的地位设置成了 undefined 防止了后续将其删除
   3. 依据 8 虚构节点的 elm 属性，将其实在 dom 中的 el 删除

总结：整个 Vue2.x 的 dom-diff 过程就实现了，须要留神的几点是，

1. 双指针遍历的是，新旧的虚构节点数组，不是实在 dom
2. 老节点都有 elm 属性，指向实在的节点，节点的插入和删除都是依附这个属性
3. Vue2.x 尽可能在复用本来的 dom
4. 尽量应用 key，在不应用 key 时，所有的节点比照都是雷同的，比照状况都是走的头头比拟，节点都是间接比照而后进行批改解决，比复用挪动老节点效率低。

Vue3.x diff 算法

1. Vue3.x dom-diff 外围源码

      const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
        let i = 0;
        const l2 = c2.length;
        let e1 = c1.length - 1; // prev ending index
        let e2 = l2 - 1; // next ending index
        // 1. sync from start
        // (a b) c
        // (a b) d e
        while (i <= e1 && i <= e2) {const n1 = c1[i];
            const n2 = (c2[i] = optimized
                ? cloneIfMounted(c2[i])
                : normalizeVNode(c2[i]));
            if (isSameVNodeType(n1, n2)) {patch(n1, n2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized);
            }
            else {break;}
            i++;
        }
        // 2. sync from end
        // a (b c)
        // d e (b c)
        while (i <= e1 && i <= e2) {
            // 获取开端的值
            const n1 = c1[e1];
            const n2 = (c2[e2] = optimized
                ? cloneIfMounted(c2[e2])
                : normalizeVNode(c2[e2]));
            if (isSameVNodeType(n1, n2)) {patch(n1, n2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized);
            }
            else {break;}
            e1--;
            e2--;
        }
        // 3. common sequence + mount
        // (a b)
        // (a b) c
        // i = 2, e1 = 1, e2 = 2
        // (a b)
        // c (a b)
        // i = 0, e1 = -1, e2 = 0
        // 旧节点遍历齐全，patch c2 剩下的节点
        if (i > e1) {if (i <= e2) {
                const nextPos = e2 + 1;
                const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor;
                while (i <= e2) {patch(null, (c2[i] = optimized
                        ? cloneIfMounted(c2[i])
                        : normalizeVNode(c2[i])), container, anchor, parentComponent, parentSuspense, isSVG);
                    i++;
                }
            }
        }
        // 4. common sequence + unmount
        // (a b) c
        // (a b)
        // i = 2, e1 = 2, e2 = 1
        // a (b c)
        // (b c)
        // i = 0, e1 = 0, e2 = -1
        // 新节点遍历齐全，卸载老节点上的多余节点
        else if (i > e2) {while (i <= e1) {unmount(c1[i], parentComponent, parentSuspense, true);
                i++;
            }
        }
        // 5. unknown sequence
        // [i ... e1 + 1]: a b  f g
        // [i ... e2 + 1]: a b [e d c h] f g
        // i = 2, e1 = 4, e2 = 5
        else {
            const s1 = i; // prev starting index
            const s2 = i; // next starting index
            // 5.1 build key:index map for newChildren
            const keyToNewIndexMap = new Map();
            for (i = s2; i <= e2; i++) {const nextChild = (c2[i] = optimized
                    ? cloneIfMounted(c2[i])
                    : normalizeVNode(c2[i]));
                if (nextChild.key != null) {if ((process.env.NODE_ENV !== 'production') && keyToNewIndexMap.has(nextChild.key)) {warn(`Duplicate keys found during update:`, JSON.stringify(nextChild.key), `Make sure keys are unique.`);
                    }
                    keyToNewIndexMap.set(nextChild.key, i);
                }
            }

            // 5.2 loop through old children left to be patched and try to patch
            // matching nodes & remove nodes that are no longer present
            let j;
            let patched = 0;
            const toBePatched = e2 - s2 + 1;
            let moved = false;
            let maxNewIndexSoFar = 0;  // used to track whether any node has moved
            // works as Map<newIndex, oldIndex>
            // Note that oldIndex is offset by +1
            // and oldIndex = 0 is a special value indicating the new node has
            // no corresponding old node.
            // used for determining longest stable subsequence
            const newIndexToOldIndexMap = new Array(toBePatched);
            for (i = 0; i < toBePatched; i++)
                newIndexToOldIndexMap[i] = 0;
            // 先遍历老节点
            for (i = s1; i <= e1; i++) {
                // 老的子节点
                const prevChild = c1[i];

                // 挂载实现，删除以后老的子节点
                if (patched >= toBePatched) {unmount(prevChild, parentComponent, parentSuspense, true);
                    continue;
                }

                // 获取 newIndex
                let newIndex;
                if (prevChild.key != null) {newIndex = keyToNewIndexMap.get(prevChild.key);
                }
                else {
                    // key-less node, try to locate a key-less node of the same type
                    // 没有 key 的节点，尝试去定位一个与其雷同类型的节点
                    // 遍历新节点
                    for (j = s2; j <= e2; j++) {
                        // 遍历 s2 到 e2，找出和 prevChild 类型雷同的节点，并将 j 赋值给 newIndex
                        if (newIndexToOldIndexMap[j - s2] === 0 && isSameVNodeType(prevChild, c2[j])) {
                            newIndex = j;
                            break;
                        }
                    }
                }

                //newIndex 不存在，则卸载节点
                if (newIndex === undefined) {unmount(prevChild, parentComponent, parentSuspense, true);
                }
                else {
                    // 新节点存在
                    newIndexToOldIndexMap[newIndex - s2] = i + 1; // i 为 s1
                    if (newIndex >= maxNewIndexSoFar) {maxNewIndexSoFar = newIndex;}
                    else {moved = true;}
                    patch(prevChild, c2[newIndex], container, null, parentComponent, parentSuspense, isSVG, optimized);
                    patched++;
                }
            }

            // 5.3 move and mount
            // generate longest stable subsequence only when nodes have moved
            // 新节点数组中最大升序子集，返回的是 index 汇合
            const increasingNewIndexSequence = moved
                ? getSequence(newIndexToOldIndexMap)
                : EMPTY_ARR;
            j = increasingNewIndexSequence.length - 1;
    
            // 向后循环，以便咱们能够应用最初一个补丁节点作为锚
            for (i = toBePatched - 1; i >= 0; i--) {
                // 新的子节点下标和新的子节点
                const nextIndex = s2 + i;
                const nextChild = c2[nextIndex];
                //nextIndex 前面一个节点为锚点
                const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor;
                // 为 0 则是新增
                if (newIndexToOldIndexMap[i] === 0) {
                    // 挂载新节点
                    patch(null, nextChild, container, anchor, parentComponent, parentSuspense, isSVG);
                }
                else if (moved) {
                    // 在没有稳固升序子集的的状况，或者当初的节点不在稳固升序子集外面，则挪动
                    // i 是遍历须要挪动节点汇合的指针，从后往前 
                    // j 是从后往前遍历 increasingNewIndexSequence 的指针
                    // j<0 则最长升序子集遍历实现 i!== 子序列中的值，阐明须要挪动
                    if (j < 0 || i !== increasingNewIndexSequence[j]) {move(nextChild, container, anchor, 2 /* REORDER */);
                    }
                    else {j--;}
                }
            }
        }
    };

2. 整体逻辑图

和 vue2.x 比照，Vue3.0 没有采纳双指针遍历的形式，而是单指针循环，先遍历头部节点，直到第一个不同节点；而后再尾部遍历，直到第一个不同的节点。而后做新旧节点是否遍历实现的判断，如果遍历实现则进行挂载或删除。以上状况都不是，则进行外围逻辑比照。Vue3.x 中勾销了头尾 / 尾头的比拟，只有头尾遇到不同的节点，那么其中的节点都进入未知序列外围逻辑的比拟。先看一下外围比照的逻辑图
此处的 unknown sequence 就是上例中的除去头尾雷同项的两头项

3. 案例剖析

还是下面的案例

realDom
1 2 3 4 5 6 7 8 9 10
//old VNode
s1                           e1
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
//new VNode
s2                            e2
[1, 9, 11, 7, 3, 4, 5, 6, 2, 10]

头尾比拟后，次要是两头项的比拟。
oldch:：[2, 3, 4, 5, 6, 7, 8, 9] 
newch：[9, 11, 7, 3, 4, 5, 6, 2] 
联合动图

1. 首先遍历新的子节点，生成一个新节点本身 key 和 index 的映射表：keyToNewIndexMap 

0: {9 => 1}
1: {11 => 2}
2: {7 => 3}
3: {3 => 4}
4: {4 => 5}
5: {5 => 6}
6: {6 => 7}
7: {2 => 8}

1. 遍历旧节点

   1. 通过旧节点的 key，在中 keyToNewIndexMap 查问在新节点 index
   2. 如果 newIndex 没有，则删除节点
   3. 如果有，就生成一个 {newIndex : oldIndex+1}映射表 : newIndexToOldIndexMap 

[9,0,7,3,4,5,6,2]

1. 通过 newIndexToOldIndexMap 获取最长升序子序列的 index 汇合，increasingNewIndexSequence 

[3,4,5,6]

1. newch : [9, 11, 7, 3, 4, 5, 6, 2]

   newIndexToOldIndexMap: [9, 0, 7, 3, 4, 5, 6, 2] 

increasingNewIndexSequence: [3, 4, 5, 6] 

• 须要比拟的项的数量为 8，用 toBePatched 示意，以数组项指针的模式从后往前循环，同时遍历 newch 和 newIndexToOldIndexMap
• 同时最长升序子序列也从后往前遍历，将其遍历的值和下面遍历的数组指针比拟
• newIndexToOldIndexMap 指针在 increasingNewIndexSequence 项中没有的时候，对应的 newch 中的节点就须要挪动；存在的话，则不需挪动
• newIndexToOldIndexMap 中值为 0 的时候，对应的 newch 中的项就为新增节点
• 锚点为，指针挪动到 newCh 节点的前面节点

Vue3.x 的 dom diff 通过和最长升序子序列的的比照，将节点挪动操作最小化，大大晋升了效率。感兴趣的能够钻研下最长升序子序列。

4. 最长升序子序列算法

function getSequence(arr) {const p = arr.slice();
    const result = [0];
    let i, j, u, v, c;
    const len = arr.length;
    for (i = 0; i < len; i++) {const arrI = arr[i];
            j = result[result.length - 1];
            if (arr[j] < arrI) {p[i] = j;
                result.push(i);
                continue;
            }
            u = 0;
            v = result.length - 1;
            while (u < v) {c = ((u + v) / 2) | 0;
                if (arr[result] < arrI) {u = c + 1;}
                else {v = c;}
            }
            if (arrI < arr[result[u]]) {if (u > 0) {p[i] = result[u - 1];
                }
                result[u] = i;
            }
    }
    u = result.length;
    v = result[u - 1];
    while (u-- > 0) {result[u] = v;
        v = p[v];
    }
    return result;
}