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 [c d e] 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[c]] < 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;
}