diff 算法

当新旧 vnode 的子节点都是一组节点时，为了以最小的性能开销完成更新操作，需要比较两组子节点，用于比较的算法就叫作 Diff 算法。核心 Diff 只关心新旧虚拟节点都存在一组子节点的情况。

减少 DOM 操作的性能开销

操作 DOM 的性能开销通常比较大，而渲染器的核心 Diff 算法就是为了解决这个问题而诞生的。

// 旧 vnode
const oldVNode = {
  type: 'div',
  children: [
    { type: 'p', children: '1' },
    { type: 'p', children: '2' },
    { type: 'p', children: '3' }
  ]
}

// 新 vnode
const newVNode = {
  type: 'div',
  children: [
    { type: 'p', children: '4' },
    { type: 'p', children: '5' },
    { type: 'p', children: '6' }
  ]
}

在引入 diff 之前，更新上面节点需要卸载 3 次，挂载 3 次，共 6 次 DOM 操作；通过 diff 算法对比 type 找到复用节点，只需要更新 3 次即可。

DOM 复用与 key

在 DOM 复用的时候，有时只需要移动节点，对于新旧节点只是顺序上的调整，可以引入 key 来标识。

// oldChildren
[
  { type: 'p', children: 'p 节点', key: 'p' },
  { type: 'div', children: 'div 节点', key: 'div' },
  { type: 'span', children: 'span 节点', key: 'span' }
]

// newChildren
[
  { type: 'span', children: 'span 节点', key: 'span' },
  { type: 'p', children: 'p 节点', key: 'p' },
  { type: 'div', children: 'div 节点', key: 'div' }
]

观察上面子节点，如果直接更新会有 6 次 DOM 操作，但上面节点只是顺序不同，为子节点增加 key，在 diff 过程新节点可通过 key 在旧节点中找到对应 DOM 进行复用。

简单 diff

简单 diff 基本步骤：

根据 key 查找可复用节点，更新复用节点；
移动复用节点；
添加新节点；
移除旧节点；

在 patchChildren 找到新旧节点都为数组处理逻辑处，新增 simpleDiff 替换原处理逻辑。

function patchChildren(oldV, newV, container) {
  if (typeof newV.children === 'string') {
    /* 新节点 为 字符串 */
  } else if (Array.isArray(newV.children)) {
    /* 新节点 为 数组 */
    if (Array.isArray(oldV.children)) {
      // 新旧节点都为数组
      oldV.children.forEach(i => unmountElement(i)) 
      newV.children.forEach(i => patch(null, i, container)) 
      simpleDiff(oldV, newV, container) 
    }
  } else {
    /* 新节点 为 不存在 */
  }
}

更新节点

遍历新节点，在旧节点中查找可复用节点，若 key 一致则更新节点。

function simpleDiff(oldV, newV, container) {
  const oldChildren = oldV.children
  const newChildren = newV.children

  // 遍历 新节点
  for (let i = 0; i < newChildren.length; i++) {
    const newChild = newChildren[i]

    // 查找可复用节点
    const findIndex = oldChildren.findIndex(oldChild => newChild.key === oldChild.key)
    if (~findIndex) {
      const oldChild = oldChildren[findIndex]
      patch(oldChild, newChild, container)
    }
  }
}

移动节点

在复用 DOM 时，需要查找需要移动的节点，当节点顺序为曾序时，说明节点不需要移动（即当前 index 大于之前所有的 index）；当节点顺序为降序时，需要节点需要移动（即当前 index 小于之前所有的 index），移动到上一个新节点位置的后面。

// oldChildren
[
  { type: 'p', children: 'p 节点', key: 'p' },         // index 0
  { type: 'div', children: 'div 节点', key: 'div' },   // index 1
  { type: 'span', children: 'span 节点', key: 'span' } // index 2
]

// newChildren 2
[
  { type: 'p', children: 'p 节点', key: 'p' },          // index 0
  { type: 'span', children: 'span 节点', key: 'span' }, // index 2
  { type: 'div', children: 'div 节点', key: 'div' }     // index 1
]

以上新旧节点，diff 过程如下：

取新节点第一项，在旧节点中查找，对应下标是 0；
取新节点第二项，在旧节点中查找，对应下标是 2，2 大于之前已找到元素的下标 0，说明不需要移动；
取新节点第三项，在旧节点中查找，对应下标是 1，1 小于之前已找到元素的小标 2，说明需要移动，移动到 span 的后面；

根据以上逻辑，需要定义一个变量用于记录已遍找到元素在旧节点中的最大小标，并以此来判断当前元素是否需要移动。

function simpleDiff(oldV, newV, container) {
  const oldChildren = oldV.children
  const newChildren = newV.children

  // 记录最大下标
  let lastIndex = 0

  // 遍历 新节点
  for (let i = 0; i < newChildren.length; i++) {
    const newChild = newChildren[i]

    // 查找可复用节点
    const findIndex = oldChildren.findIndex(oldChild => newChild.key === oldChild.key)
    if (~findIndex) {
      const oldChild = oldChildren[findIndex]
      patch(oldChild, newChild, container)

      if (findIndex < lastIndex) { 
        // 小于最大下标，需要移动，移动到上一个节点后面
        const preVNode = newChildren[i - 1] 
        const anchor = preVNode._el.nextSibling 
        container.insertBefore(oldChild._el, anchor) 
      } else { 
        // 大于最大下标，不移动，更新最大下标
        lastIndex = findIndex 
      } 
    }
  }
}

新增节点

如果在旧节点查找不到新节点，此时需要新增挂载，并且需要指定挂载位置，需要修改 mountElement 让其支持指定挂载的位置，同时 patch 也要多一个参数用于传递给 mountElement。

function simpleDiff(oldV, newV, container) {
  // ...

  // 遍历 新节点
  for (let i = 0; i < newChildren.length; i++) {
    // 查找可复用节点
    const findIndex = oldChildren.findIndex(oldChild => newChild.key === oldChild.key)
    if (~findIndex) {
      // ...
    } else { 
      // 新增节点，需要指定挂载位置
      const preVNode = newChildren[i - 1] 
      const anchor = preVNode._el.nextSibling 
      patch(null, newChild, container, anchor) 
    } 
  }
}

修改 patch 多一个 anchor 参数，仅仅是为了给 mountElement 传参。

function patch(oldV, newV, container, anchor) {
  // ...

  mountElement(newV, container) 
  mountElement(newV, container, anchor) 

  // ...
}

修改 mountElement，支持指定元素前插入，当 anchor 为 null，默认插入到尾部，效果等同于 appendChild。

function mountElement(vNode, container, anchor = null) {
  // ...

  container.appendChild(el) 
  container.insertBefore(el, anchor) 
}

卸载节点

当旧节点在新节点中不存在时，此时需要卸载节点，这步操作是在新节点更新完之后。

function simpleDiff(oldV, newV, container) {
  // ...

  // 遍历 新节点
  for (let i = 0; i < newChildren.length; i++) {
    // ...
  }

  for (let i = 0; i < oldChildren.length; i++) { 
    // 在新节点中查找旧节点
    const oldChild = oldChildren[i] 
    const find = newChildren.find(child => child.key === oldChild.key) 
    if (!find) { 
      // 找不，卸载
      unmountElement(oldChild) 
    } 
  } 
}

双端 diff

vue2 采用双端 diff

双端 diff 需要四个索引值，分别指向新旧两组子节点的端点，然后进行双端比较，先首位各自比较，再交叉比较：

比较新节点 newStartIdx 与旧节点 oldStartIdx，匹配成功则更新节点，此时无需移动节点，newStartIdx 与 oldStartIdx 自增 +1；否则下一步比较；
比较新节点 newEndIdx 与旧节点 oldEndIdx，匹配成功则更新节点，此时无需移动节点，newEndIdx 与 oldEndIdx 自减 -1；否则下一步比较；
比较新节点 newEndIdx 与旧节点 oldStartIdx，匹配成功则更新节点，此时需要将 oldStartIdx 节点移动到 oldEndIdx 之后，newEndIdx 自减 -1，oldStartIdx 自增 +1；否则下一步比较；
比较新节点 newStartIdx 与旧节点 oldEndIdx，匹配成功则更新节点，此时需要将 oldEndIdx 节点移动到 oldStartIdx 之前，newStartIdx 自增 +1，oldEndIdx 自减 -1；

如此一直循环下去，直到新节点或旧节点的首尾下标出现交叉情况。

正在加载图表...

新增一个 doubleDiff 函数替换掉 simpleDiff，doubleDiff 内容如下：

function doubleDiff(oldV, newV, container) {
  const oldChildren = oldV.children
  const newChildren = newV.children

  // 双端下标
  let newStartIdx = 0
  let newEndIdx = newChildren.length - 1
  let oldStartIdx = 0
  let oldEndIdx = oldChildren.length - 1

  // 新节点 或 旧节点 的首尾下标出现交叉 退出循环
  while (newStartIdx <= newEndIdx && oldStartIdx <= oldEndIdx) {
    let newStartVNode = newChildren[newStartIdx]
    let newEndVNode = newChildren[newEndIdx]
    let oldStartVNode = oldChildren[oldStartIdx]
    let oldEndVNode = oldChildren[oldEndIdx]

    if (newStartVNode.key === oldStartVNode.key) {
      // 新首 与 旧首
      patch(oldStartVNode, newStartVNode, container)
      newStartVNode = newChildren[++newStartIdx]
      oldStartVNode = oldChildren[++oldStartIdx]
    } else if (newEndVNode.key === oldEndVNode.key) {
      // 新尾 与 旧尾
      patch(oldEndVNode, newEndVNode, container)
      newEndVNode = newChildren[--newEndIdx]
      oldEndVNode = oldChildren[--oldEndIdx]
    } else if (newEndVNode.key === oldStartVNode.key) {
      // 新尾 与 旧首
      patch(oldStartVNode, newEndVNode, container)
      container.insertBefore(oldStartVNode._el, oldEndVNode._el.nextSibling)
      newEndVNode = newChildren[--newEndIdx]
      oldStartVNode = oldChildren[++oldStartIdx]
    } else if (newStartVNode.key === oldEndVNode.key) {
      // 新首 与 旧尾
      patch(oldEndVNode, newStartVNode, container)
      container.insertBefore(oldEndVNode._el, oldStartVNode._el)
      newStartVNode = newChildren[++newStartIdx]
      oldEndVNode = oldChildren[--oldEndIdx]
    }
  }
}

接下来补充一下交叉比较完后依然没有匹配到的情况，这种需要拿新节点 newStartVNode 去旧节点中匹配，找到则更新节点，并将节点移动到 oldStartVNode 之前；否则在 oldStartVNode 之前插入一个新节点。

function doubleDiff(oldV, newV, container) {
  // ...

  // 新节点 或 旧节点 的首尾下标出现交叉 退出循环
  while (newStartIdx <= newEndIdx && oldStartIdx <= oldEndIdx) {
    // ...

    if (!oldStartVNode) { 
      // 标记，说明节点已处理，跳过
      oldStartIdx++
    } else if (newStartVNode.key === oldStartVNode.key) { 
    if (newStartVNode.key === oldStartVNode.key) {  
      // 新首 与 旧首
    } else if (newEndVNode.key === oldEndVNode.key) {
      // 新尾 与 旧尾
    } else if (newEndVNode.key === oldStartVNode.key) {
      // 新尾 与 旧首
    } else if (newStartVNode.key === oldEndVNode.key) {
      // 新首 与 旧尾
    } else {  
      // 在旧节点中查找 新首
      const findIndex = oldChildren.findIndex(oldVNode => oldVNode.key === newStartVNode.key)  
      if (~findIndex) {  
        // 找到更新，并移动
        patch(oldChildren[findIndex], newStartVNode, container)  
        container.insertBefore(oldChildren[findIndex]._el, oldStartVNode._el)  
        // 处理过改节点了，标记一下，下次遇到直接跳过
        oldChildren[findIndex] = undefined
      } else { 
        // 未找到，直接插入
        patch(null, newStartVNode, container, oldStartVNode._el) 
      } 
      newStartVNode = newChildren[++newStartIdx] 
    }
  }
}

完善交叉逻辑后，当 while 循环结束后，会出现三种情况：

新节点完全复用旧节点，新节点无新增，旧节点无多余，这种情况不需要处理；
旧节点被完全复用，新节点有剩余没有插入，这时需要循环剩余新增节点，逐个插入到 oldStartVNode 之前；
新节点更新完毕，旧节点有剩余，这时需要循环剩余旧节点，逐个移除；

function doubleDiff(oldV, newV, container) {
  // ...

  if (oldEndIdx < oldStartIdx && newEndIdx >= newStartIdx) { 
    // 新节点有剩余
    for (let i = newStartIdx; i <= newEndIdx; i++) { 
      patch(null, newChildren[i], container, newStartVNode._el) 
    } 
  } else if (oldEndIdx >= oldStartIdx && newEndIdx < newStartIdx) { 
  // 旧节点有剩余
    for (let i = oldStartIdx; i <= oldEndIdx; i++) { 
      unmountElement(oldChildren[i]) 
    } 
  } 
}

快速 diff

vue3 采用快速 diff

todo...

diff 算法 ​

减少 DOM 操作的性能开销 ​

DOM 复用 与 key ​

简单 diff ​

更新节点 ​

移动节点 ​

新增节点 ​

卸载节点 ​

双端 diff ​

快速 diff ​