深入了解Vue3 diff算法

起因

在了解vue源码后，写mini-vue时,分享下对Vue3 diff算法的理解，下面是新旧节点标识ShapeFlags 皆为 ARRAY_CHILDREN的比较

Vue3 核心diff算法

相关变量解释

let i = 0;   // 默认从 节点的第一个元素 开始比较
let e1 = c1.length - 1; //旧元素长度
let e2 = c2.length - 1;	//新元素长度

1.对比新旧元素两端

首先先对比新旧元素的头部进行对比,patch方法就是对元素节点的比较，若头部的key值相等就patch下去，遇到key不相等就不patch了

  while (i <= e1 && i <= e2 && c1[i].key === c2[i].key) {
    patch(c1[i], c2[i], container, anchor);
    i++;
  }
  while (i <= e1 && i <= e2 && c1[e1].key === c2[e2].key) {
    patch(c1[i], c2[i], container, anchor);
    i++;
    e1--;
    e2--;
  }

2.判断是否存在新元素⊆旧元素或者旧元素⊆新元素

若旧元素⊆新元素，则对新元素中新节点进行mount(挂载)操作（此处patch的第一个参数为null就是mount操作） 若新元素⊆旧元素，则对旧元素的旧节点进行unmount（删除）操作

if (i > e1) {
    // 若是 c1，c2中旧节点对比完成，则只剩下c2中新节点，则剩下的全部mount
    for (let j = i; j < e2; j++) {
      const nextPos = e2 + 1;
      const curAnchor = (c2[nextPos] && c2[nextPos].el) || anchor;
      patch(null, c2[j], container, curAnchor);
    }
  } else if (i > e2) {
    // 若是 c1，c2中旧节点对比完成，则只剩下c1中旧节点，则剩下的全部unMount
    for (let j = i; j < e1; j++) {
      unmount(e1[j]);
    }
  } 

3.采用vue2传统diff算法

若都不满足前面的，则采取传统的differ算法，只是不真的对其进行移动和添加，而是将其删除和标记起来，然后判断旧元素中是否存在新元素中的节点，对新节点进行mount操作，对旧节点进行移动和删除，如果需要对旧节点进行移动，则采用 获取最长递增子序列的方法来获取最佳移动方法（这个下篇文章分享下）

  	const map = new Map();
    c1.forEach((prev, j) => {
      map.set(prev.key, { prev, j });
    });
    // maxNewIndexSoFar 如果从旧数组中找到的位置小于naxNewIndexSoFar,则判断它是上升趋势，不需要移动此元素位置 用来判断是否需要移动新的元素
    let maxNewIndexSoFar = 0;
    let move = false;
    let source = new Array(e2 - i + 1).fill(-1);
    let toMounted: any = [];
    for (let k = 0; k < c2.length; k++) {
      const next = c2[k];
      if (map.has(next.key)) {
        const { prev, j } = map.get(next.key);
        patch(prev, next, container, anchor);
        if (j < maxNewIndexSoFar) {
          move = true;
        } else {
          maxNewIndexSoFar = j;
        }
        source[k] = j;
        map.delete(next.key);
      } else {
        toMounted.push(k + i);
      }
    }
    map.forEach(({ prev }) => {
      unmount(prev);
    });
    if (move) {
      // 获取最长递增子序列，-1表示新增
      const seq = getSequence(source);
      let j = seq.length - 1;
      for (let k = source.length - 1; k > 0; k--) {
        if (seq[j] === k) {
          // 不用移动
          j--;
        } else {
          const pos = k + i;
          const nextPos = pos + 1;
          const curAnchor = (c2[nextPos] && c2[nextPos].el) || anchor;
          if (source[k] === -1) {
            // mount
            patch(null, c2[pos], container, curAnchor);
          } else {
            // 移动
            container.insertBefore(c2[pos].el, curAnchor);
          }
        }
      }
    } else if (toMounted.length) {
      for (let k = toMounted.length; k < 0; k--) {
        const pos = toMounted[k];
        const nextPos = pos + 1;
        const curAnchor = (c2[nextPos] && c2[nextPos].el) || anchor;
        patch(null, c2[pos], container, curAnchor);
      }
    }
  }
};

我有什么地方写的不明白和错误的地方，如果jym可以在评论区告诉我，那属实泰裤啦！🙂