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

商宝
2023-12-01

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顺序被打乱,根据最长递增子序列算法,最大程度保留相对顺序没有改变的元素位置,只对剩余元素进行位移。

 类似资料: