Vue3 diff 原理

[J-DuYa]

代码地址：https://github.com/vuejs/core/blob/main/packages/runtime-core/src/renderer.ts 具体的方法：patchKeyedChildren to 1788 行

Vue3 的 diff 过程分五种情况

1. 同步头部节点
2. 同步尾部节点
3. 添加新的节点
4. 删除旧的节点
5. 处理未知子序列

前提提示 比较是否是同一个节点，是通过标签名和key值（所以key值在 diff 的过程中是比较重要的，能精确的进行 diff 运算）

比较两个节点是否相同的代码

export function isSameVNodeType(n1: VNode, n2: VNode): boolean {
  if (
    __DEV__ &&
    // shapeFlag 表示 vnode 的类型编码
    // 什么时候 shapeFlag 不存在？？？？                                  
    n2.shapeFlag & ShapeFlags.COMPONENT &&
    hmrDirtyComponents.has(n2.type as ConcreteComponent)
  ) {
    // #7042, ensure the vnode being unmounted during HMR
    // bitwise operations to remove keep alive flags
    n1.shapeFlag &= ~ShapeFlags.COMPONENT_SHOULD_KEEP_ALIVE
    n2.shapeFlag &= ~ShapeFlags.COMPONENT_KEPT_ALIVE
    // HMR only: if the component has been hot-updated, force a reload.
    return false
  }

  // 判断新旧节点是否相同的核心
  return n1.type === n2.type && n1.key === n2.key
}

1. 同步头部节点

从头部节点出发，依次比较新节点和旧节点，如果相同则执行 patch 运算更新节点。如果不一样或者索引大于了新节点的长度或者旧节点的长度，则同步结束。

2. 同步尾部节点

从尾部节点出发，依次比较新节点和旧节点，如果相同则执行 patch 运算更新节点。如果不一样或者索引大于了新节点的长度或者旧节点的长度，则同步结束。

3. 添加新节点

索引大于旧节点的长度，但是小于或者等于新节点的长度，将新节点通过 patch 运算进行挂载新节点。

4. 删除旧节点

索引大于新节点的长度，但是小于或者等于旧节点的长度，则执行 umount 运算对旧节点进行卸载。

5. 处理未知子序列

使用最长递增子序列算法实现。具体的算法实现是 ‘贪心算法’ + ‘二分查找算法’ 实现。时间复杂度 O(nlogn)。