前言

最近学Vue源码，了解了相关的diff算法，下面是我的整理复盘~

为什么需要diff算法?

在Vue里，组件的产出就是虚拟DOM，我们要将新旧节点的VDOM进行比对，这个时候，为了提升性能，尽量去复用节点，减少DOM操作，那么就需要diff算法咯

react的diff算法

let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
  const nextVNode = nextChildren[i]
  let j = 0,
    find = false;
  for (j; j < prevChildren.length; j++) {
    const prevVNode = prevChildren[j]
    if (nextVNode.key === prevVNode.key) {
      find = true
      patch(prevVNode, nextVNode, container)
      if (j < lastIndex) {
        // 需要移动
        const refNode = nextChildren[i - 1].el.nextSibling
        container.insertBefore(prevVNode.el, refNode)
        break
      } else {
        // 更新 lastIndex
        lastIndex = j
      }
    }
  }
  if (!find) {
    // 挂载新节点
    const refNode =
      i - 1 < 0
        ? prevChildren[0].el
        : nextChildren[i - 1].el.nextSibling
    mount(nextVNode, container, false, refNode)
  }
}
// 移除已经不存在的节点
for (let i = 0; i < prevChildren.length; i++) {
  const prevVNode = prevChildren[i]
  const has = nextChildren.find(
    nextVNode => nextVNode.key === prevVNode.key
  )
  if (!has) {
    // 移除
    container.removeChild(prevVNode.el)
  }
}

上面的代码只是核心内容，下面解释一下一些变量：

• nextChildren：新VNode
• prevChildren：旧VNode
• key：节点的唯一标识，下面简单的例子理解一下 key 的值

// 旧的 VNode
const prevVNode = h('div', null, [
  h('p', { key: 'a' }, '节点1'),
  h('p', { key: 'b' }, '节点2'),
  h('p', { key: 'c' }, '节点3')
])

// 新的 VNode
const nextVNode = h('div', null, [
  h('p', { key: 'd' }, '节点4'),
  h('p', { key: 'a' }, '节点1'),
  h('p', { key: 'b' }, '节点2')
])

// h 函数的返回值
return {
    _isVNode: true,
    flags,
    tag,
    data,
    key: data && data.key ? data.key : null,
    children,
    childFlags,
    el: null || container // 要挂载的节点
 }

• el.nextSibling：是一个 DOM 属性，表示节点 el 的下一个兄弟节点（即同一级别的节点中，紧挨着节点 el 后面的节点）。
• insertBefore ：是一个 DOM API 中的方法，它可以在指定节点的父节点的子节点列表中，在指定位置前面插入一个新的子节点。

分析流程：

1. 比较同层的新旧节点，两层for循环，时间复杂度是O(n²)。
2. 新节点的子节点与旧节点的子节点进行比对，因为key值是唯一的，如果相同，那么就调用patch方法，进行比较新旧节点的属性和绑定事件有没有更改过。
3. 可以看到lastIndex的妙用，当进行节点比较时，当旧节点的最后的子节点会使得lastIndex的值不发生改变，于是进入第一个分支，进行节点的插入和替换。
4. find变量用来标记新增的节点，挂载时需要判断是否是第一个节点。
5. 需要通过再一次的遍历，移除不存在的节点。

Vue的双端diff算法

react的diff算法有个很明显的缺点，对于旧节点的最后子节点挂载到最前面时，整个子节点都需要进行移动。比如：旧VNode：A、B、C、D；新VNode：D、A、B、C；

// 当新的 children 中有多个子节点时，会执行该 case 语句块
let oldStartIdx = 0 // 定义旧节点开始索引
let oldEndIdx = prevChildren.length - 1 // 定义旧节点结束索引
let newStartIdx = 0 // 定义新节点开始索引
let newEndIdx = nextChildren.length - 1 // 定义新节点结束索引
let oldStartVNode = prevChildren[oldStartIdx] // 定义旧节点开始位置对应的虚拟节点
let oldEndVNode = prevChildren[oldEndIdx] // 定义旧节点结束位置对应的虚拟节点
let newStartVNode = nextChildren[newStartIdx] // 定义新节点开始位置对应的虚拟节点
let newEndVNode = nextChildren[newEndIdx] // 定义新节点结束位置对应的虚拟节点

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { // 循环比较旧节点和新节点
  if (!oldStartVNode) { 
  // 如果旧节点开始位置的虚拟节点不存在，则将旧节点开始索引增加，并重新定义旧节点开始位置对应的虚拟节点
    oldStartVNode = prevChildren[++oldStartIdx]
  } else if (!oldEndVNode) { 
  // 如果旧节点结束位置的虚拟节点不存在，则将旧节点结束索引减少，并重新定义旧节点结束位置对应的虚拟节点
    oldEndVNode = prevChildren[--oldEndIdx]
  } else if (oldStartVNode.key === newStartVNode.key) { 
  // 如果旧节点开始位置虚拟节点的 key 和新节点开始位置虚拟节点的 key 相同，则进行 patch 操作
    patch(oldStartVNode, newStartVNode, container)
    oldStartVNode = prevChildren[++oldStartIdx]// 对旧节点开始索引和新节点开始索引都加 1，表示这两个节点已经匹配完成
    newStartVNode = nextChildren[++newStartIdx]
  } else if (oldEndVNode.key === newEndVNode.key) { 
  // 如果旧节点结束位置虚拟节点的 key 和新节点结束位置虚拟节点的 key 相同，则进行 patch 操作
    patch(oldEndVNode, newEndVNode, container)
    oldEndVNode = prevChildren[--oldEndIdx] // 对旧节点结束索引和新节点结束索引都减 1，表示两个节点已经匹配完成
    newEndVNode = nextChildren[--newEndIdx]
  } else if (oldStartVNode.key === newEndVNode.key) { 
  // 如果旧节点开始位置虚拟节点的 key 和新节点结束位置虚拟节点的 key 相同，则进行 patch 操作
    patch(oldStartVNode, newEndVNode, container) // 这个操作是将旧节点开始位置虚拟节点移动到旧节点结束位置之后，并更新其对应的真实节点的位置
    container.insertBefore(
      oldStartVNode.el,
      oldEndVNode.el.nextSibling
    )
    oldStartVNode = prevChildren[++oldStartIdx] // 对旧节点开始索引和新节点结束索引都加 1，表示这两个节点已经匹配完成
    newEndVNode = nextChildren[--newEndIdx]
  } else if (oldEndVNode.key === newStartVNode.key) { 
  // 如果旧节点结束位置虚拟节点的 key 和新节点开始位置虚拟节点的 key 相同，则进行 patch 操作
    patch(oldEndVNode, newStartVNode, container) // 这个操作是将旧节点结束位置虚拟节点移动到旧节点开始位置之前，并更新其对应的真实节点的位置
    container.insertBefore(oldEndVNode.el, oldStartVNode.el)
    oldEndVNode = prevChildren[--oldEndIdx] // 对旧节点结束索引和新节点开始索引都减 1，表示两个节点已经匹配完成
    newStartVNode = nextChildren[++newStartIdx]
  } else {
    const idxInOld = prevChildren.findIndex( // 查找新节点开始位置虚拟节点在旧节点中的位置，并返回对应的索引
      node => node.key === newStartVNode.key
    )
    if (idxInOld >= 0) { // 如果返回的索引不小于 0，则说明新节点开始位置虚拟节点在旧节点中存在
      const vnodeToMove = prevChildren[idxInOld] // 根据返回的索引，找到旧节点中对应的虚拟节点，并将其移动到旧节点开始位置之前，并更新其对应的真实节点的位置
      patch(vnodeToMove, newStartVNode, container)
      prevChildren[idxInOld] = undefined // 将该虚拟节点在旧节点中的位置设为 undefined，表示其已经被移动过了
      container.insertBefore(vnodeToMove.el, oldStartVNode.el)
    } else { // 如果返回的索引小于 0，则说明新节点开始位置虚拟节点在旧节点中不存在
      // 新节点
      mount(newStartVNode, container, false, oldStartVNode.el) // 在旧节点开始位置之前插入新节点，并创建其对应的真实节点
    }
    newStartVNode = nextChildren[++newStartIdx] // 对新节点开始索引加 1，表示该节点已经处理完成
  }
}
if (oldEndIdx < oldStartIdx) { // 如果旧节点结束索引小于旧节点开始索引，则说明旧节点已经全部处理完成，此时需要将剩余的新节点添加到真实 DOM 中
  // 添加新节点
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    mount(nextChildren[i], container, false, oldStartVNode.el)
  }
}

分析流程：

下面几种情况：

• 旧节点的头指针和尾指针是否为空，重新指向位置。在后续的处理节点过程中，会使某些旧节点赋值为undefined。
• 头头和尾尾比较，进行patch函数调用，再使新旧头节点向下移动。
• 头尾和尾头比较，进行patch函数调用，再将新节点进行调用。insertBefore方法，和拿到el.nextSibling属性，进行DOM的插入操作，再使指针分别移动。
• 上面情况都不符合时，通过遍历去比对key值，能找到则进行patch操作，使该旧节点值为undefined，不能找到则进行mount方法的调用，进行挂载新节点，此时仅需要新节点头指针进行移动。

图解举例具体分析：

diff整体策略为：深度优先，同层比较

1. 比较只会在同层级进行, 不会跨层级比较

1. 比较的过程中，循环从两边向中间收拢

下面举个vue通过diff算法更新的例子：

新旧VNode节点如下图所示：

第一次循环后，发现旧节点D与新节点D相同，直接复用旧节点D作为diff后的第一个真实节点，同时旧节点endIndex移动到C，新节点的 startIndex 移动到了 C，我们可以看到进行了container.insertBefore(oldEndVNode.el, oldStartVNode.el)函数的调用，进行了一次DOM的插入操作。

第二次循环后，同样是旧节点的末尾和新节点的开头(都是 C)相同，同理，diff 后创建了 C 的真实节点插入到第一次创建的 D 节点后面。同时旧节点的 endIndex 移动到了 B，新节点的 startIndex 移动到了 E

第三次循环中，发现E没有找到，这时候只能直接创建新的真实节点 E，插入到第二次创建的 C 节点之后。同时新节点的 startIndex 移动到了 A。旧节点的 startIndex 和 endIndex 都保持不动

第四次循环中，发现了新旧节点的开头(都是 A)相同，于是 diff 后创建了 A 的真实节点，插入到前一次创建的 E 节点后面。同时旧节点的 startIndex 移动到了 B，新节点的startIndex 移动到了 B

第五次循环中，情形同第四次循环一样，因此 diff 后创建了 B 真实节点 插入到前一次创建的 A 节点后面。同时旧节点的 startIndex移动到了 C，新节点的 startIndex 移动到了 F

新节点的 startIndex 已经大于 endIndex 了，需要创建 newStartIdx 和 newEndIdx 之间的所有节点，也就是节点F，直接创建 F 节点对应的真实节点放到 B 节点后面

什么时候需要diff？

Vue3又对diff做了什么优化？

vue3在diff算法中相比vue2增加了静态标记

关于这个静态标记，其作用是为了会发生变化的地方添加一个flag标记，下次发生变化的时候直接找该地方进行比较

下图这里，已经标记静态节点的p标签在diff过程中则不会比较，把性能进一步提高

关于静态类型枚举如下

export const enum PatchFlags {
  TEXT = 1,// 动态的文本节点
  CLASS = 1 << 1,  // 2 动态的 class
  STYLE = 1 << 2,  // 4 动态的 style
  PROPS = 1 << 3,  // 8 动态属性，不包括类名和样式
  FULL_PROPS = 1 << 4,  // 16 动态 key，当 key 变化时需要完整的 diff 算法做比较
  HYDRATE_EVENTS = 1 << 5,  // 32 表示带有事件监听器的节点
  STABLE_FRAGMENT = 1 << 6,   // 64 一个不会改变子节点顺序的 Fragment
  KEYED_FRAGMENT = 1 << 7, // 128 带有 key 属性的 Fragment
  UNKEYED_FRAGMENT = 1 << 8, // 256 子节点没有 key 的 Fragment
  NEED_PATCH = 1 << 9,   // 512
  DYNAMIC_SLOTS = 1 << 10,  // 动态 solt
  HOISTED = -1,  // 特殊标志是负整数表示永远不会用作 diff
  BAIL = -2 // 一个特殊的标志，指代差异算法
}

Vue3中对不参与更新的元素，会做静态提升，只会被创建一次，在渲染时直接复用

这样就免去了重复的创建节点，大型应用会受益于这个改动，免去了重复的创建操作，优化了运行时候的内存占用

<span>你好</span>

<div>{{ message }}</div>

没有做静态提升之前

export function render(_ctx, _cache, $props, $setup, $data, $options) {
  return (_openBlock(), _createBlock(_Fragment, null, [
    _createVNode("span", null, "你好"),
    _createVNode("div", null, _toDisplayString(_ctx.message), 1 /* TEXT */)
  ], 64 /* STABLE_FRAGMENT */))
}

做了静态提升之后

const _hoisted_1 = /*#__PURE__*/_createVNode("span", null, "你好", -1 /* HOISTED */)

export function render(_ctx, _cache, $props, $setup, $data, $options) {
  return (_openBlock(), _createBlock(_Fragment, null, [
    _hoisted_1,
    _createVNode("div", null, _toDisplayString(_ctx.message), 1 /* TEXT */)
  ], 64 /* STABLE_FRAGMENT */))
}

// Check the console for the AST

• 静态内容_hoisted_1被放置在render 函数外
• 每次渲染的时候只要取 _hoisted_1 即可
• 同时 _hoisted_1 被打上了 PatchFlag ，静态标记值为 -1
• 特殊标志是负整数表示永远不会用于 Diff