Vue Diff Algorithm

[sufuwang]

概述

Vue Diff 算法的迭代历程：简单 Diff 算法 => 双端 Diff 算法 => 快速 Diff 算法

简单 Diff 算法思路简单，但它的 VDom 移位策略性能较差，双端 Diff 算法和快速 Diff 算法是通过修改 VDom 的对比策略来追求极致性能，双端 Diff 算法使用平行和交叉对比的方式来进行移位的判断，所以需要大量的对比，不是较好的解决办法，快速 Diff 算法借助最长递增子序列，仅需少量对比即可得知需要移位的 VDom 。在此基础上，快速 Diff 算法借鉴文本 Diff 算法对 VDom 进行预处理，以减少 VDom 的对比范围

[sufuwang]

简单 Diff 算法

1. 使用 Key 来修改可以复用的 DOM 节点

2. 根据 Key 值，判断哪些节点需要移位：缓存一个新节点在旧节点集合中的最大索引 maxIndex ，新 VDom 索引小于这个最大索引 maxIndex 时，表明当前节点需要被移位

   const oldVDoms = [
    { key: 0, type: 'p', children: 'o-0' },
    { key: 1, type: 'p', children: 'o-1' },
    { key: 2, type: 'p', children: 'o-2' },
   ]
   
   const newVDoms = [
    { key: 2, type: 'p', children: 'n-0' },
    { key: 0, type: 'p', children: 'n-1' },
    { key: 1, type: 'p', children: 'n-2' },
   ]
   
   // 遍历 newVDoms ，使用 Key 值判断索引
   // 1. newVDoms[0] 在 oldVDoms 的索引是 2 , 则当前最大索引是 2
   // 2. newVDoms[1] 在 oldVDoms 的索引是 0 , 当前索引 < 最大索引, 所以 newVDoms[1] 需要移动
   // 3. newVDoms[2] 在 oldVDoms 的索引是 1 , 当前索引 < 最大索引, 所以 newVDoms[2] 需要移动

3. 以最大索引 maxIndex 所处的 DOM 元素为起点，按照 newVDoms 的顺序修改 DOM 元素位置
4. 若 newVDoms 中有节点不存在于 oldVDoms ，表现为 Key 不存在，按照 newVDoms 的顺序挂载新 DOM 节点
5. 若 oldVDoms 中有节点不存在于 newVDoms，表现为 Key 不存在，则根据 Key 删除对应 DOM 节点

[sufuwang]

简单 Diff 算法的弊端

1. 简单 Diff 算法在判断哪些节点需要移位时，存在性能问题

   const oldVDoms = [
    { key: 0, type: 'p', children: 'o-0' },
    { key: 1, type: 'p', children: 'o-1' },
    { key: 2, type: 'p', children: 'o-2' },
   ]
   
   const newVDoms = [
    { key: 2, type: 'p', children: 'n-0' },
    { key: 0, type: 'p', children: 'n-1' },
    { key: 1, type: 'p', children: 'n-2' },
   ]
   
   // 简单 Diff 算法需要移动 Key 为 0 和 1 的两个 DOM 节点
   // 最优的移位策略应该是移动 Key 为 2 的 DOM 节点即可

双端 Diff 算法的优点

1. 在相同场景下，双端 Diff 算法所需要的 DOM 移动次数 <= 简单 Diff 算法所需要的 DOM 移动次数

[sufuwang]

双端 Diff 算法

双端 Diff 算法在一次对比中，对 2 个新 VDom 和 2 个旧 VDom 分别进行横向和交叉对比

const newVDoms = [
  { key: 2, type: 'p', children: 'n-0' },
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },
]

// 1. 第一次对比: newStartIndex = 0, newEndIndex = 2, oldStartIndex = 0, oldEndIndex = 2
//    a. newVDoms[0] & oldVDoms[0]
//    b. newVDoms[2] & oldVDoms[2]
//    c. newVDoms[2] & oldVDoms[0]
//    d. newVDoms[0] & oldVDoms[2]
//    第 a,b,c 种情况，VDom 的 Key 不同，表示不可以复用，则不做任何操作
//    第 d 种情况下两个 VDom 的 Key 相同，表示可以复用，则更新节点，因为 d 属于交叉对比，则需要移位
//    所有操作结束后，更新所有索引。因为刚才操作的是 newStartIndex & oldEndIndex 位置上的索引
//    所以对 newStartIndex 加 1，对 oldEndIndex 减 1，故 newStartIndex = 1, newEndIndex = 2, oldStartIndex = 0, oldEndIndex = 1

// 2. 第二次对比: newStartIndex = 1, newEndIndex = 2, oldStartIndex = 0, oldEndIndex = 1
//    a. newVDoms[1] & oldVDoms[0]
//    b. newVDoms[2] & oldVDoms[1]
//    c. newVDoms[1] & oldVDoms[1]
//    d. newVDoms[2] & oldVDoms[0]
//    第 c,d 种情况，VDom 的 Key 不同，表示不可以复用，则不做任何操作
//    第 a,b 种情况下两个 VDom 的 Key 相同，表示可以复用，则更新节点即可
//    所有操作结束后，更新索引。因为刚才操作的是 newStartIndex & newEndIndex & oldStartIndex & oldEndIndex 位置上的索引
//    所以对 newStartIndex & oldStartIndex 加 1，对 newEndIndex & oldEndIndex 减 1，故 newStartIndex = 2, newEndIndex = 1, oldStartIndex = 1, oldEndIndex = 0

//    因为 newEndIndex > newStartIndex & oldStartIndex > oldEndIndex，所以结束循环

极端情况下的双端 Diff 算法

每次对比时，不是一定会出现可复用的 VDom，需要一些额外的操作，来打破这种窘境

const newVDoms = [
  { key: 2, type: 'p', children: 'n-0' },
  { key: 3, type: 'p', children: 'o-3' },
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },
  { key: 3, type: 'p', children: 'o-3' },
]

// 1. 第一次对比: newStartIndex = 0, newEndIndex = 3, oldStartIndex = 0, oldEndIndex = 3
//    a. newVDoms[0] & oldVDoms[0]
//    b. newVDoms[3] & oldVDoms[3]
//    c. newVDoms[3] & oldVDoms[0]
//    d. newVDoms[0] & oldVDoms[3]
//    会发现这四种对比，发现可以复用的 VDom

// 2. 额外的操作: 遍历 oldVDoms，找到可以复用的 VDom（索引为 tarIndex），更新对应元素后，把 oldVDom[tarIndex] 置为 undefined，然后 newStartIndex 加 1

const newVDoms = [
  { key: 2, type: 'p', children: 'n-0' },
  { key: 3, type: 'p', children: 'o-3' },  // newStartIndex
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },  // newEndIndex
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex
  { key: 1, type: 'p', children: 'o-1' },
  undefined,
  { key: 3, type: 'p', children: 'o-3' },  // oldEndIndex
]
// 3. 第二次对比: newStartIndex = 1, newEndIndex = 3, oldStartIndex = 0, oldEndIndex = 3

新增 VDom

// 第一次对比
const newVDoms = [
  { key: 4, type: 'p', children: 'n-0' },  // newStartIndex
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },
  { key: 2, type: 'p', children: 'n-3' },  // newEndIndex
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },  // oldEndIndex
]

// 第二次对比
const newVDoms = [
  { key: 4, type: 'p', children: 'n-0' },  // newStartIndex
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },  // newEndIndex
  { key: 2, type: 'p', children: 'n-3' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex
  { key: 1, type: 'p', children: 'o-1' },  // oldEndIndex
  { key: 2, type: 'p', children: 'o-2' },
]

// 第三次对比
const newVDoms = [
  { key: 4, type: 'p', children: 'n-0' },  // newStartIndex
  { key: 0, type: 'p', children: 'n-1' },  // newEndIndex
  { key: 1, type: 'p', children: 'n-2' },
  { key: 2, type: 'p', children: 'n-3' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex oldEndIndex
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },
]

// 第四次对比
const newVDoms = [
  { key: 4, type: 'p', children: 'n-0' },  // newStartIndex newEndIndex
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },
  { key: 2, type: 'p', children: 'n-3' },
]
const oldVDoms = [             // oldEndIndex
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },
]
// oldVDoms 已经遍历完毕，所以索引 newStartIndex 对应的元素应该被新增

删除 VDom

// 第一次对比
const newVDoms = [
  { key: 0, type: 'p', children: 'n-1' },  // newStartIndex
  { key: 1, type: 'p', children: 'n-2' },  // newEndIndex
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },  // oldEndIndex
]

// 第二次对比
const newVDoms = [
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },  // newStartIndex newEndIndex
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },  // oldStartIndex
  { key: 2, type: 'p', children: 'o-2' },  // oldEndIndex
]

// 第三次对比
const newVDoms = [
  { key: 0, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },  // newEndIndex
]                                          // newStartIndex
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },  // oldStartIndex oldEndIndex
]
// newVDoms 已经遍历完毕，所以索引 oldStartIndex 对应的元素应该被删除

[sufuwang]

快速 Diff 算法

前置 VDom 和后置 VDom

这是快速 Diff 算法的预处理阶段，借鉴文本 Diff 算法，对 VDoms 的前缀元素和后缀元素进行 DOM 更新，这个过程中不会涉及 DOM 移位

// 前置 VDom 的对比: 从第一个 VDom 向前遍历
// 前置 VDom 的第一次对比
const newVDoms = [
  { key: 0, type: 'p', children: 'n-0' },  // newStartIndex
  { key: 2, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex
  { key: 1, type: 'p', children: 'o-1' },
]

// 前置 VDom 的第二次对比
const newVDoms = [
  { key: 0, type: 'p', children: 'n-0' },
  { key: 2, type: 'p', children: 'n-1' },  // newStartIndex
  { key: 1, type: 'p', children: 'n-2' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },  // oldStartIndex
]
// 此时 newVDoms[newStartIndex].key !== oldVDoms[oldStartIndex].key
// 所以停止遍历

// 后置 VDom 的对比: 从最后一个 VDom 向前遍历
// 后置 VDom 的第一次对比
const newVDoms = [
  { key: 0, type: 'p', children: 'n-0' },
  { key: 2, type: 'p', children: 'n-1' },
  { key: 1, type: 'p', children: 'n-2' },  // newEndIndex
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },  // oldEndIndex
]

// 后置 VDom 的第二次对比
const newVDoms = [
  { key: 0, type: 'p', children: 'n-0' },
  { key: 2, type: 'p', children: 'n-1' },  // newEndIndex
  { key: 1, type: 'p', children: 'n-2' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldEndIndex
  { key: 1, type: 'p', children: 'o-1' },
]
// 此时 newVDoms[newEndIndex].key !== oldVDoms[oldEndIndex].key
// 所以停止遍历

新增和删除 VDom

前面的代码示例中，最后的索引对比结果是 oldEndIndex 小于 oldStartIndex 表明不需要删除 DOM 节点， newStartIndex 小于 newEndIndex 表明需要新增 DOM 节点。索引对比情况反之，则需要删除 DOM 节点

VDom 移位

快速 Diff 算法借助 newVDoms 索引表和最长递增子序列完成移位判断

const newVDoms = [
  { key: 0, type: 'p', children: 'n-0' },  // newStartIndex
  { key: 3, type: 'p', children: 'n-1' },
  { key: 4, type: 'p', children: 'n-2' },
  { key: 2, type: 'p', children: 'n-3' },
  { key: 7, type: 'p', children: 'n-4' },
  { key: 5, type: 'p', children: 'n-5' },  // newEndIndex
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },  // oldStartIndex
  { key: 1, type: 'p', children: 'o-1' },
  { key: 2, type: 'p', children: 'o-2' },
  { key: 3, type: 'p', children: 'o-3' },
  { key: 4, type: 'p', children: 'o-4' },
  { key: 5, type: 'p', children: 'o-5' },  // oldEndIndex
]

// 1. 判断前置 VDom 和 后置 VDom
const newVDoms = [
  { key: 0, type: 'p', children: 'n-0' },
  { key: 3, type: 'p', children: 'n-1' },  // newStartIndex
  { key: 4, type: 'p', children: 'n-2' },
  { key: 2, type: 'p', children: 'n-3' },
  { key: 7, type: 'p', children: 'n-4' },  // newEndIndex
  { key: 5, type: 'p', children: 'n-5' },
]
const oldVDoms = [
  { key: 0, type: 'p', children: 'o-0' },
  { key: 1, type: 'p', children: 'o-1' },  // oldStartIndex
  { key: 2, type: 'p', children: 'o-2' },
  { key: 3, type: 'p', children: 'o-3' },
  { key: 4, type: 'p', children: 'o-4' },  // oldEndIndex
  { key: 5, type: 'p', children: 'o-5' },
]

// 后面的逻辑，不包括已经更新的前缀 VDom 和后缀 VDom

// 2. 建立 newVDoms 的索引表: { [newVDom.key]: newVDoms.indexof(VDom) }
//    => { 3:0, 4:1, 2:2, 7:3 }

// 3. 建立 source 数组: [ oldVDoms.indexof(newVDom.key) ]
//    => [2, 3, 1, -1]

// 4. 根据 source 数组，计算最长递增子序列
//    [2, 3, 1, -1] => [2, 3] => [0, 1]

// 5. 遍历最长递增子序列与 oldVDoms.slice(oldStartIndex, oldEndIndex + 1)
//    所以索引为 oldStartIndex 和 oldStartIndex + 1 的两个 oldVDom 不用进行移位
//    又因为 source 数组的最后一项是 -1，即 oldVDoms 中不存在此 newVDom
//    故索引为 oldStartIndex + 2 的 oldVDom 需要进行移位
//    故索引为 newStartIndex + 3 的 newVDom 需要进行新增