vue3 DOM Diff + 最长递增子序列 + 伪代码实现

五个步骤

1. 处理前置节点
2. 处理后置节点
3. 处理仅新增节点
4. 处理仅卸载节点
5. 处理其他情况

对应源码

core/packages/runtime-core/src/renderer.ts at 2ffe3d5b3e953b63d4743b1e2bc242d50916b545 · vuejs/core (github.com)

1. sync from start（core/packages/runtime-core/src/renderer.ts at 2ffe3d5b3e953b63d4743b1e2bc242d50916b545 · vuejs/core (github.com)）
2. sync from end（core/packages/runtime-core/src/renderer.ts at 2ffe3d5b3e953b63d4743b1e2bc242d50916b545 · vuejs/core (github.com)）
3. common sequence + mount （core/packages/runtime-core/src/renderer.ts at 2ffe3d5b3e953b63d4743b1e2bc242d50916b545 · vuejs/core (github.com)）
4. common sequence + unmount （core/packages/runtime-core/src/renderer.ts at 2ffe3d5b3e953b63d4743b1e2bc242d50916b545 · vuejs/core (github.com)）
5. unknown sequence （core/packages/runtime-core/src/renderer.ts at 2ffe3d5b3e953b63d4743b1e2bc242d50916b545 · vuejs/core (github.com)）

情况分析

预处理

对于步骤1/2，是比较好理解的，比如

let oldList = [1, 2, 3, 4, 5, 6, 7]
let newList = [1, 2, 6, 4, 5, 8, 7]

那么在步骤一中就可以对比出 1/2，步骤二中可以对比出 7。中间的剩余部分就是需要剩余步骤进行对比的序列。

仅新增节点

let oldList = [1, 2, 3, 4, 5, 7]
let newList = [1, 2, 3, 4, 5, 6, 7]

假设步骤一中处理前置节点，记录变量 i ，i <= 5 之前都是可以由步骤一处理的。

假设步骤二中处理后置节点，记录遍历e1、e2分别为旧节点与新节点的最后元素索引，那么同样 e1 > 4 / e2 > 5 之后都是可以由步骤二处理的。

这里存在 e1 < i <= e2，则说明是仅新增节点的情况，然后把 i 到 e2 之间的节点进行全量新增即可。

仅卸载节点

let oldList = [1, 2, 3, 4, 5, 6, 7]
let newList = [1, 2, 3, 4, 5, 7]

假设步骤一中处理前置节点，记录变量 i ，i <= 5 之前都是可以由步骤一处理的。

假设步骤二中处理后置节点，记录遍历e1、e2分别为旧节点与新节点的最后元素索引，那么同样 e1 > 5 / e2 > 4 之后都是可以由步骤二处理的。

这里存在 e2 < i <= e1，则说明是仅新增节点的情况，然后把 i 到 e2 之间的节点进行全量卸载即可。

处理其他情况

举个例子：

let oldList = [1, 2, 3, 4, 5, 6, 7]
let newList = [1, 2, 6, 4, 5, 8, 7]

这种情况，前置节点 1/2，后置节点 7 由步骤一和步骤二完成，但是此时 i <= 1，e1 > 5，e2 > 5都是步骤一二可处理的。但 e1 === e2，不满足前面两种情况。

旧节点[3, 4, 5, 6] 与 新节点[6, 4, 5, 8] 两个序列中，3是需要卸载的，6是需要移动的，8是需要新增的，而4/5则是需要复用的。那么vue3是怎么处理这样的序列的呢。

源码在这：core/packages/runtime-core/src/renderer.ts at 2ffe3d5b3e953b63d4743b1e2bc242d50916b545 · vuejs/core (github.com)

生成映射

遍历旧节点，给对应新节点生成映射表，初始化映射为与新节点长度相同的数组，并填充初始值为-1，像这里的映射表生成为[-1,-1,-1,-1]

很明显在遍历旧节点3的时候，在新节点中找不到，可以确定要卸载节点3。而 4/5/6 都能找到，则给他们在映射表对应的位置赋值他们在原数组中的索引，最终变为[5,3,4,-1]。

有了这么个映射表索引之后大概就能看出来，在新节点中还存在与旧节点相同顺序的节点序列，旧节点索引为3/4的节点在新节点中仍然是连在一块的，那么就可以请出我们的最长递增子序列了

最长递增子序列

大概就是从映射表[5,3,4,-1]中找出3/4，但vue3中则是找出他们的索引，即[1,2]。

更新

现在我们有：

映射表：[5, 3, 4, -1]

新节点：[6, 4, 5, 8]

最长递增子序列 indexOfLIS：[1, 2]

最后对映射表进行倒序遍历，索引为k，同时设一个变量z，初始值为 indexOfLIS.length - 1。

• 遇到-1，我们就能知道是旧节点中没有的节点，需要新增，对应的位置则是节点8。
• 遇到非-1，我们比对索引，如果存在 k===indexOfLIS[z]，就说明当前的节点处在最长递增子序列中，可以直接复用，同时 z -= 1。
• 遇到非-1，同时不存在k===indexOfLIS[z]，则说明当前节点需要由旧节点移动到此处。

我要看代码

Vue3Diff

/**
 * @param {number[]} oldList
 * @param {number[]} newList
 */
function Vue3Diff(oldList, newList) {
  console.log('------------------------- 1. sync from start -------------------------');
  let i = 0;
  while (i < oldList.length && i < newList.length) {
    if (oldList[i] === newList[i]) {
      console.log(`patch ${newList[i]}`);
      i++;
    } else {
      break;
    }
  }
  if (i === newList.length) {
    return console.log('same');
  }

  console.log('------------------------- 2. sync from end -------------------------');
  let e1 = oldList.length - 1;
  let e2 = newList.length - 1;
  while (e1 >= i && e2 >= i) {
    if (oldList[e1] === newList[e2]) {
      console.log(`patch ${newList[e2]}`);
      e1--;
      e2--;
    } else {
      break;
    }
  }

  // console.log({ i, e1, e2 })

  if (e1 < i && i <= e2) {
    console.log('------------------------- 3. common sequence + mount -------------------------');
    for (let j = i; j <= e2; j++) {
      console.log('add', newList[j]);
    }
  }

  else if (e2 < i && i <= e1) {
    console.log('------------------------- 4. common sequence + unmount -------------------------');
    for (let j = i; j <= e1; j++) {
      console.log('remove', oldList[j]);
    }
  }

  else {
    console.log('------------------------- 5. unknown sequence -------------------------');
    let s1 = i;
    let s2 = i;
    let diffArr = newList.slice(s2, e2 + 1);
    const newIndexToOldIndexMap = new Array(diffArr.length).fill(-1);
    for (let j = s1; j <= e1; j++) {
      let index = diffArr.findIndex(_ => oldList[j] === _);
      if (index >= 0) {
        newIndexToOldIndexMap[index] = j;
      } else {
        console.log(`remove ${oldList[j]}`);
      }
    }
    let indexOfMapLIS = IndexOfLIS(newIndexToOldIndexMap)
    // console.log(newIndexToOldIndexMap, indexOfMapLIS, diffArr);

    let k = newIndexToOldIndexMap.length - 1;
    let z = indexOfMapLIS.length - 1;
    for (let j = k; j >= 0; j -= 1) {
      let node = diffArr[j];
      if (newIndexToOldIndexMap[j] < 0) console.log(`add ${node}`);
      else if (j === indexOfMapLIS[z]) {
        console.log(`patch ${node}`);
        z -= 1;
      } else {
        console.log(`move ${node}`);
      }
    }
  }
}

IndexOfLIS

这里最后改造了一下，回溯的时候回溯索引而不是原始值。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function IndexOfLIS(nums) {
  // 记录回溯下标
  let recalls = [undefined];

  // 记录最新贪心序列以及对应下标
  let res = [nums[0]];
  let idxRes = [0];


  for (let i = 1; i < nums.length; i++) {
    // 大于push
    if (nums[i] > res[res.length - 1]) {
      recalls.push(idxRes[idxRes.length - 1])
      res.push(nums[i])
      idxRes.push(i)
    }
    // 等于略过
    else if (nums[i] == res[res.length - 1]) {
      continue
    }
    // 小于找位置插入
    else {
      // 查找
      let l = 0, r = res.length - 1;
      while (l < r) {
        let mid = (l + r) >> 1;
        if (res[mid] >= nums[i]) {
          r = mid
        } else {
          l = mid + 1
        }
      }

      recalls.push(idxRes[l - 1])
      res[l] = nums[i]
      idxRes[l] = i
    }
  }
  // console.log(recalls)
  // console.log(res)
  // console.log(idxRes)

  // 回溯
  for (let i = res.length - 1; i > 0; i--) {
    res[i - 1] = recalls[idxRes[i]]
    idxRes[i - 1] = idxRes[i]
  }
  res[res.length - 1] = idxRes[idxRes.length - 1];
  return res;
}

测试

let oldList = [1, 2, 3, 4, 5, 6, 7]
let newList = [1, 2, 4, 6, 5, 8, 7]
Vue3Diff(oldList, newList)

结果