【mini-vue】DIFF算法学习笔记

mini-vue DIFF源码传送门:mini-vue/renderer.ts at master · cuixiaorui/mini-vue (github.com)

  function patchKeyedChildren(
    c1: any[],
    c2: any[],
    container,
    parentAnchor,
    parentComponent
  ) {}

参数：

1. c1，老虚拟节点的子节点
2. c2，新虚拟节点的子节点
3. container，容器，DOM节点
4. parentComponent，父节点的虚拟节点
5. anchor，锚点（插入节点的时候使用）

作用：

1. 创建三个指针i，e1，e2，分别指向0，老节点的尾部，新节点的尾部

       let i = 0;
       const l2 = c2.length;
       let e1 = c1.length - 1;
       let e2 = l2 - 1;

2. 从左往右遍历，如果下标为i的新老节点相同则i++，不同则结束遍历

       const isSameVNodeType = (n1, n2) => {
         return n1.type === n2.type && n1.key === n2.key;
       };
   
       while (i <= e1 && i <= e2) {
         const prevChild = c1[i];
         const nextChild = c2[i];
   
         if (!isSameVNodeType(prevChild, nextChild)) {
           console.log("两个 child 不相等(从左往右比对)");
           console.log(`prevChild:${prevChild}`);
           console.log(`nextChild:${nextChild}`);
           break;
         }
   
         console.log("两个 child 相等，接下来对比这两个 child 节点(从左往右比对)");
         patch(prevChild, nextChild, container, parentAnchor, parentComponent);
         i++;
       }

3. 从右边往左遍历，如果下标为e1的老节点和e2的新节点相同则e1--，e2--，不同则结束遍历

       while (i <= e1 && i <= e2) {
         // 从右向左取值
         const prevChild = c1[e1];
         const nextChild = c2[e2];
   
         if (!isSameVNodeType(prevChild, nextChild)) {
           console.log("两个 child 不相等(从右往左比对)");
           console.log(`prevChild:${prevChild}`);
           console.log(`nextChild:${nextChild}`);
           break;
         }
         console.log("两个 child 相等，接下来对比这两个 child 节点(从右往左比对)");
         patch(prevChild, nextChild, container, parentAnchor, parentComponent);
         e1--;
         e2--;
       }

4. 如果i>e1&&i<=e2，则说明新节点比老节点多，要添加新节点，这里分2种情况，（AB ABCD）与（AB CDAB），如果是添加到尾部直接添加即可，如果添加到首部，需要获取锚点，则个锚点的位置是e2+1，遍历[i, e2]添加新节点

       if (i > e1 && i <= e2) {
         // 如果是这种情况的话就说明 e2 也就是新节点的数量大于旧节点的数量
         // 也就是说新增了 vnode
         // 应该循环 c2
         // 锚点的计算：新的节点有可能需要添加到尾部，也可能添加到头部，所以需要指定添加的问题
         // 要添加的位置是当前的位置(e2 开始)+1
         // 因为对于往左侧添加的话，应该获取到 c2 的第一个元素
         // 所以我们需要从 e2 + 1 取到锚点的位置
         const nextPos = e2 + 1;
         const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor;
         while (i <= e2) {
           console.log(`需要新创建一个 vnode: ${c2[i].key}`);
           patch(null, c2[i], container, anchor, parentComponent);
           i++;
         }
       } 

5. 如果i>e2，则说明老的比新的多，要删除老节点，同样分2种情况（ABCD AB）与（CDAB AB）,遍历[i, e1]删除对应节点

       else if (i > e2 && i <= e1) {
         // 这种情况的话说明新节点的数量是小于旧节点的数量的
         // 那么我们就需要把多余的
         while (i <= e1) {
           console.log(`需要删除当前的 vnode: ${c1[i].key}`);
           hostRemove(c1[i].el);
           i++;
         }
       }

6. 除去以上情况，就到了最后的中间对比阶段了（无优化版，比较易于理解）

   1. 创建新的指针s1=i，s2=i，以及一个map用于存储新节点的key与新节点的下标index，moved判断

            let s1 = i;
            let s2 = i;
            const keyToNewIndexMap = new Map();

   2. 遍历[s2, e2]将{key, 下标index}存储到map中

            // 先把 key 和 newIndex 绑定好，方便后续基于 key 找到 newIndex
            // 时间复杂度是 O(1)
            for (let i = s2; i <= e2; i++) {
              const nextChild = c2[i];
              keyToNewIndexMap.set(nextChild.key, i);
            }

   3. 遍历[s1, e1]

            for (i = s1; i <= e1; i++) {
              const prevChild = c1[i];
              // ......
            }

      1. 如果遍历到的这个老节点有key，并且map中有对应的key，则从map中获取新节点对应的下标

                 let newIndex;
                 if (prevChild.key != null) {
                   // 这里就可以通过key快速的查找了， 看看在新的里面这个节点存在不存在
                   // 时间复杂度O(1)
                   newIndex = keyToNewIndexMap.get(prevChild.key);
                 }

      2. 否则再遍历一遍[s2, e2]，如果找到了同样的节点则记录新节点对应的下标（可见map哈希表是很好的空间换时间的方案，用来降低时间复杂度）

                 else {
                   // 如果没key 的话，那么只能是遍历所有的新节点来确定当前节点存在不存在了
                   // 时间复杂度O(n)
                   for (let j = s2; j <= e2; j++) {
                     if (isSameVNodeType(prevChild, c2[j])) {
                       newIndex = j;
                       break;
                     }
                   }
                 }

      3. 如果都没找到，则卸载这个老节点

                 // 因为有可能 nextIndex 的值为0（0也是正常值）
                 // 所以需要通过值是不是 undefined 或者 null 来判断
                 if (newIndex === undefined) {
                   // 当前节点的key 不存在于 newChildren 中，需要把当前节点给删除掉
                   hostRemove(prevChild.el);
                 }

      4. 如果找到了，把新节点的下标作为key，老节点的下标作为value进行存储到数组newIndexToOldIndex，不好解释看伪代码，arr[新节点的下标 - 新节点的起始下标s2] = 老节点的下标 + 1，并进行挂载patch(老节点, 新节点)，（虽然新老节点key相同，但是可能props有不同，这里patch主要是处理新老节点可能不同的props等）

                 else {
                   // 新老节点都存在
                   console.log("新老节点都存在");
                   // 把新节点的索引和老的节点的索引建立映射关系
                   // i + 1 是因为 i 有可能是0 (0 的话会被认为新节点在老的节点中不存在)
                   newIndexToOldIndexMap[newIndex - s2] = i + 1;
                   // 来确定中间的节点是不是需要移动
                   // 新的 newIndex 如果一直是升序的话，那么就说明没有移动
                   // 所以我们可以记录最后一个节点在新的里面的索引，然后看看是不是升序
                   // 不是升序的话，我们就可以确定节点移动过了
                   if (newIndex >= maxNewIndexSoFar) {
                     maxNewIndexSoFar = newIndex;
                   } else {
                     moved = true;
                   }
         
                   patch(prevChild, c2[newIndex], container, null, parentComponent);
                   patched++;
                 }

   4. 求数组newIndexToOldIndex的最长递增子序列

            // 利用最长递增子序列来优化移动逻辑
            // 因为元素是升序的话，那么这些元素就是不需要移动的
            // 而我们就可以通过最长递增子序列来获取到升序的列表
            // 在移动的时候我们去对比这个列表，如果对比上的话，就说明当前元素不需要移动
            // 通过 moved 来进行优化，如果没有移动过的话 那么就不需要执行算法
            // getSequence 返回的是 newIndexToOldIndexMap 的索引值
            // 所以后面我们可以直接遍历索引值来处理，也就是直接使用 toBePatched 即可
            const increasingNewIndexSequence = moved
              ? getSequence(newIndexToOldIndexMap)
              : [];

      解释：

      1. [2, 1, 5, 3, 4]的最长递增子序列为[2, 3, 4]或[1, 3, 4]

      2. 假设老、新children分别为AB(CDEZ)FG AB(DCYE)FG

         newIndexToOldIndexMap[newIndex - s2] = i + 1

         newIndexToOldIndexMap: [4, 3, 0, 5] (新节点中的D在老节点的位置4，C在3，Y不在老节点中至0，E在5)

         对数组newIndexToOldIndexMap求最长递增子序列的结果为increasingNewIndexSequence: [1, 3] ([4, 3, 0, 5]最长递增子序列为[3, 5]，3的下标为1，5的下标为3)

   5. 从后往前遍历[s2, e2]，（从后往前的原因是insertBefore需要知道后一个元素即锚点）

            for (let i = toBePatched - 1; i >= 0; i--) {
              // 确定当前要处理的节点索引
              const nextIndex = s2 + i;
              const nextChild = c2[nextIndex];
              // 锚点等于当前节点索引+1
              // 也就是当前节点的后面一个节点(又因为是倒遍历，所以锚点是位置确定的节点)
              const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor;
              // ......
            }

      1. 创建指针j指向计算出的最长递增子序列increasingNewIndexSequence的尾部

               let j = increasingNewIndexSequence.length - 1;

      2. 如果该新节点不在老节点中，则在对应锚点前插入该节点

                 if (newIndexToOldIndexMap[i] === 0) {
                   // 说明新节点在老的里面不存在
                   // 需要创建
                   patch(null, nextChild, container, anchor, parentComponent);
                 }

      3. 如果在子序列中则说明不需要移动该节点，j--，指针往前

                   else {
                     // 这里就是命中了  index 和 最长递增子序列的值
                     // 所以可以移动指针了
                     j--;
                   }

      4. 如果不在子序列中（这个节点在老节点中，但是不在最长递增子序列中，我们需要移动该节点），在对应锚点前插入该节点

                   // 需要移动
                   // 1. j 已经没有了 说明剩下的都需要移动了
                   // 2. 最长子序列里面的值和当前的值匹配不上， 说明当前元素需要移动
                   if (j < 0 || increasingNewIndexSequence[j] !== i) {
                     // 移动的话使用 insert 即可
                     hostInsert(nextChild.el, container, anchor);
                   }

小结：

最大程度复用vnode，只会对完全不同的元素进行更新。如果vnode顺序被打乱，根据最长递增子序列算法，最大程度保留相对顺序没有改变的元素位置，只对剩余元素进行位移。