7-Vue源码之【Diff算法】
为什么需要有 Diff 算法？
由于构建 DOM 的消耗远比 JS 消耗大的多，所以为了尽可能的减少 DOM 操作，框架的前辈们利用 VNode 和 Diff 算法，通过对比前后两个 Vnode 的不同，找出最少 DOM 操作的方式。
这里有个点，Vue2 的 Diff 算法时间复杂度为 O(n) 而 Vue3 的时间复杂度为 O(nlogN) ，那么为何还要换呢？
我们这里讲的时间复杂度，一直都是 JS 层面上的，但实际上 DOM 操作远比 JS 计算来的可怕。 而 Vue3 使用了最长递增子序列，虽然看似时间复杂度高了，但换来的却是更小的 DOM 操作方式。 算法能尽可能的找到 最少量的 DOM 操作，这相当于是用更精确的 JS 计算， 来抵消更大量 DOM 消耗。
key 值的作用
在 Vue3 源码中，会根据 Key 来决定是使用什么方法去更新节点。如果没有 Key ，那么默认会去更新所有节点，如果有 key 会尽可能的去复用节点。
Vue3 Diff
- 从前向后开始遍历
let i = 0
const l2 = c2.length
let e1 = c1.length - 1 // c1 的结束下标
let e2 = l2 - 1 // c2 的结束下标
// 从前向后遍历，如果一直进入 patch
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = (c2[i] = optimized ? cloneIfMounted(c2[i] as VNode) : normalizeVNode(c2[i]))
// 如果类型 和 key 都相似， 那么进入 patch
if (isSameVNodeType(n1, n2)) {
// patch()
} else {
break
}
i++
}
如果上一步中提前 break 出去，则带着 i 进入下一步操作。
- 从后向前遍历
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = (c2[e2] = optimized ? cloneIfMounted(c2[e2] as VNode) : normalizeVNode(c2[e2]))
if (isSameVNodeType(n1, n2)) {
// patch()
} else {
break
}
e1--
e2--
}
前两步骤分别从前向后，在从后向前遍历了一遍。如果都执行到了 patch() 那么则说明前后两个节点数组基本一致。
如果有提前 break 出去，那么 i 和 e1 , e2 的数值就会呈现下列三种情况：
- 初次遍历结束，再根据不同情况选择不同做法
// 1. 旧节点数组都遍历完了，新节点还没遍历完 `e1 < i <= e2`
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
while (i <= e2) {
// 接下来的都是新增的节点，直接 patch(null, c2[i], ...args)
patch(
null,
(c2[i] = optimized ? cloneIfMounted(c2[i] as VNode) : normalizeVNode(c2[i])),
// ...
)
i++
}
}
}
// 2. 新节点数组都遍历完了，但是旧节点数组还存在
else if (i > e2) {
while (i <= e1) {
// 那么久需要删除多余节点
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
}
// 3. 如果新旧节点都没有遍历完
// 这便属于未知情况了，也是Vue3 Diff算法的核心。
else {
// ...详见后续
}
前两种情况好理解，第三种情况，两边都有没遍历完的节点，Vue3 里是采用了 最长递增子序列 来确定 如何移动 DOM 能达到最优的性能
eg：比如新旧节点数组为： -- old 节点数组: ABCDE -- new 节点数组: EABCD
在没有 key 的情况下，vue 调用了 5 次
setElementText去修改节点的文本在有 key 的情况下，头 和 尾都不相同，则属于未知情况 当然我们可以一目了然只需要将
E插入到A前面即可。但 JS 可不能一目了然， 所以需要我们用算法告诉他，算法发现：ABCD属于最长的一个子序列， 这些子序列我们可以不做任何操作，而E不属于这序列， 那么只需要移动它即可(调用move方法)这么算下来，用第二种方法，虽然多了 JS 层级的计算，但是 DOM 却只执行了一次，非常显著的提升
最长递增子序列
要想了解未知情况要如何处理，那么首先需要先了解下 最长递增子序列
const list = [3, 2, 8, 9, 5, 6, 7, 11, 15, 4]
const temp = [0, 1, 2, 3, 4, 5, 6, '7', 8, 9] // 下标
const getSequence = (list) => {
let i = 0
// 【注】 result 存放的是 最长递增序列对应 的 “下标”
// result 中的这些下标在diff算法后续不需要做 move 处理
const result = [0] // 先将下标 0 存储至 result 中
while (i++ <= list.length) {
// 在 Vue 3 Diff 中，0 表示该新节点不在旧节点的中，是需要进行新增的节点
// 所以必须排除 数值为0 的节点
if (list[i] != 0) {
const lastIndex = result[result.length - 1]
// 因为是找最长递增子序列，那么从 0 开始，遇到比 result 最后一个大的即添加
if (list[i] > list[lastIndex]) {
result.push(i)
continue
}
}
}
return result
}
const result = getSequence(list)
console.log({ result }) // { result: [ 0, 2, 3, 7, 8 ] } 【注】是下标，具体值看 temp 数组上面的
上面的操作是将 list 中，比 result 里保存的最后一个下标对应的数 大的下标 都存储进 result 中。
上面的做法可以获得一条 递增 序列，但不一定是最长的序列。
这时候就 Vue3 往里添加了二分法以保证长度最长
const getSequence = (list) => {
let i = 0
// 【注】 result 存放的是 最长递增序列对应 的 “下标”
// result 中的这些下标在diff算法后续不需要做 move 处理
const result = [0] // 先将下标 0 存储至 result 中
while (i++ <= list.length) {
// 在 Vue 3 Diff 中，0 表示该新节点不在旧节点的中，是需要进行新增的节点
// 所以必须排除 数值为0 的节点
if (list[i] != 0) {
const lastIndex = result[result.length - 1]
// 因为是找最长递增子序列，那么从 0 开始，遇到比 result 最后一个大的即添加
if (list[i] > list[lastIndex]) {
result.push(i)
continue
}
// 如果 list[i] 小于则用二分法找出合适的位置(刚好由于 result 是递增的序列，所以可以使用二分法)
+ let start = 0, // 下标
+ end = result.length - 1 // 下标
+ while (start < end) {
+ const min = (start + end) >>> 1
+ if (list[i] > list[result[min]]) {
+ start = min + 1
+ } else {
+ end = min
+ }
+ }
// 上面二分法循环结束，如果 end 位置上对应的数值更大，那么就应该被 i 替换掉
+ if (list[result[end]] > list[i]) {
+ result[end] = i
+ }
}
}
return result
}
// 序列值变化过程
// 3
// 2
// 2 8
// 2 8 9
// 2 5 9
// 2 5 6
// 2 5 6 7
// 2 5 6 7 11
// 2 5 6 7 11 15
// 2 4 6 7 11 15 <--- 不对劲
OK，用上述分别先后获取到了 递增 和 最长 的序列。
但是，我们会注意到，最后那个 4 很不对劲，因为他明明是最后一位，却因为 二分法 跑到了前面，破坏了正确性。
为了保证正确性，我们可以 回溯 我们的序列。
我们假设知道 list 中最大的一个数 15 的前一个数（这里的前一个数指的是 result 中的递增序列）的下标。
比如，正确的顺序 2 5 6 7 11 15 ，那么 15 为 下标8，前一个数 11 为 下标7，以此类推，参考下面的 回溯数组
const back = [*, *, 1, 2, 1, 4, 5, '6', 7, 1] // 回溯
const list = [3, 2, 8, 9, 5, 6, 7, 11, 15, 4]
const temp = [0, 1, 2, 3, 4, 5, 6, '7', 8, 9] // 下标
看得出来，只要我们能有 back 数组存储每个数值的前一个下标。那么我们就可以通过 回溯 ，从最大的 15 开始依次往前推。这样就不怕 二分法替换 导致序列不正确。因为我们前一个总是是正确的。
比如 list 中 6 记录的前一个数值的下标为 下标4，对应的数值为 5，只要 6 是正确的，那么 5 肯定是正确的，以此类推，只要我们最后一个数 15 是正确的，那么整个序列就是正确的了~
4 就是一个错误的典型，他对应的下标是 下标9 ，但是我们所有数都没有对应 下标9 的下标，所以这个错误的就不会被考虑进来。
那么问题就是如何构建这个回溯表了。
const getSequence = (list) => {
+ let back = list.slice()
let i = 0
// 【注】 result 存放的是 最长递增序列对应 的 “下标”
// result 中的这些下标在diff算法后续不需要做 move 处理
const result = [0] // 先将下标 0 存储至 result 中
while (i++ <= list.length) {
// 在 Vue 3 Diff 中，0 表示该新节点不在旧节点的中，是需要进行新增的节点
// 所以必须排除 数值为0 的节点
if (list[i] != 0) {
const lastIndex = result[result.length - 1]
// 因为是找最长递增子序列，那么从 0 开始，遇到比 result 最后一个大的即添加
if (list[i] > list[lastIndex]) {
result.push(i)
+ back[i] = lastIndex // back中存储result下标数组中的前一个
continue
}
// 如果 list[i] 小于则用二分法找出合适的位置(刚好由于 result 是递增的序列，所以可以使用二分法)
let start = 0, // 下标
end = result.length - 1 // 下标
while (start < end) {
const min = (start + end) >>> 1
if (list[i] > list[result[min]]) {
start = min + 1
} else {
end = min
}
}
// 上面二分法循环结束，如果 end 位置上对应的数值更大，那么就应该被 i 替换掉
if (list[result[end]] > list[i]) {
result[end] = i
+ back[i] = result[end - 1] // 因为 result 存储的是 end， 所以back要存储 result[end - 1]
}
}
}
// 开始回溯
+ let len = result.length
+ let last = result[len - 1] // 取出 result 中，最大的数值对应的下标
// 遍历，从后往前改写 result
+ while (len-- > 0) {
+ result[len] = last // 将 last 从后往前存储到 result 中，改写 result 使其正确
+ last = back[last] // 修改 last 为回溯数组对应的下标
+ }
return result
}
可以看到只需要在每次 result 变化的地方，将其前一个值存储到 back 数组里，在到最后从 result 最大值开始回溯即可获取到 正确 的下标数组
这便是最长递增子序列，那么 Vue 又是如何通过这个来优化的呢？
我们再回到源码里，前面我们说了，Vue 的 diff 是先 从前往后，再从后往前，遍历一次。如果两个数组 c1 c2 中存在 type，key 不同的节点（isSameVNodeType），那么就提前退出循环。
如果 c1 已经遍历完成，c2 还存在剩余，那么就遍历 c2 剩余的节点 patch 进去
如果 c2 已经遍历完成，c1 还存在剩余，那么将 c1 的那些多余节点都卸载掉
如果 c1 c2 都没遍历完成，则……
// 【注】 这里的代码，包裹在上面写的 else { // ...详见后续 } 里
// 排除 c1 c2 已遍历过的节点，重新调整 start下标
const s1 = i // c1 的新start下标
const s2 = i // c2 的新start下标
// 5.1 为剩余的新节点数组 c2 构建 key: index 的 Map
// 构建这个Map的目的：如果 后面 c1 能在这里找到对应的 i ，则说明该节点还保留着，且可能发生了位移
const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
for (i = s2; i <= e2; i++) {
const nextChild = (c2[i] = optimized ? cloneIfMounted(c2[i] as VNode) : normalizeVNode(c2[i]))
if (nextChild.key != null) {
keyToNewIndexMap.set(nextChild.key, i)
}
}
// 5.2 循环遍历需要patch的旧节点，并尝试 patch 合适的节点 或者 remove不在的节点
let j
let patched = 0 // 记录已执行patch的新节点数量，用于处理如果在更新时更新过的数量大于需要更新的节点数量，就卸载对应旧节点
// 新数组的节点数量为 e2 - s2 + 1
const toBePatched = e2 - s2 + 1
let moved = false
// 用于跟踪是否有节点已移动 move
let maxNewIndexSoFar = 0
// 创建一个 新旧节点 对应关系的数组，这里全部赋值为 0
// 【注】 0 在这里表示的意思是： 该节点为新增的， 我们先假设 新数组节点 都是新增的
// 在根据后面的判断，来修改 newIndexToOldIndexList
const newIndexToOldIndexList = new Array(toBePatched).fill(0)
for (i = s1; i <= e1; i++) {
const prevChild = c1[i]
// 因为遍历是用旧数组下标 e1 遍历，所以，如果已patched节点数量 大于 新节点应有的节点数量时
if (patched >= toBePatched) {
// 依次卸载掉后续的旧节点
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
let newIndex
// 如果 旧节点有 key，那么就去 keyToNewIndexMap（新节点MAP） 中找找看有没有对应的 index
if (prevChild.key != null) {
newIndex = keyToNewIndexMap.get(prevChild.key) // 有可能没找到，返回 undefined
} else {
// 没有key的节点，尝试在 新节点数组中 匹配相同类型的无key节点
for (j = s2; j <= e2; j++) {
// 如果 prevChild 和 c2 中的某个节点的 key， type 相同，那么尝试用该节点作为 newIndex
// 注意要有 newIndexToOldIndexList[j - s2] === 0 作为前置条件，不等于 0 表示 j - s2 位置上的
// 已经被修改过了，就不需要去判断这个位置
if (newIndexToOldIndexList[j - s2] === 0 && isSameVNodeType(prevChild, c2[j] as VNode)) {
newIndex = j
break
}
}
}
if (newIndex === undefined) {
// 如果没有对应key，且没找到相似的节点，那么卸载该 prevChild
unmount(prevChild, parentComponent, parentSuspense, true)
} else {
// 如果 newIndex 有值，则说明发生了节点移动
// 这里为啥是 i + 1 ？
// 【注】 不能是 i ，因为 i 有可能为 0，而在 Vue 的代码里会把 0 作为 需要新增的节点 标志
// 【注2】 不一定需要 i + 1 这里只是作为一个 递增标志 传递给 getSequence 的
newIndexToOldIndexList[newIndex - s2] = i + 1
// 这里用了 max 来判断，如果 newIndex 大于 max，则需要移动，
// 否则给 moved 设为true ，表示之前移动过
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
// 只要有 newIndex 就需要构建，所以先 patch，至于 newIndexToOldIndexList 是用来处理 节点移动 的
// Vue 的做法是，先 patch 给新的vnode赋值上 el ，位置啥的后面再处理~
patch(prevChild, c2[newIndex] as VNode)
patched++
}
}
这里可能有 keyToNewIndexMap 和 newIndexToOldIndexList 不太好了解，这里举一个例子。
首先我们上面有写过 最长递增子序列 能够帮助 Vue 去判断如何做到最小 DOM 操作。那么这个 最长递增子序列 的父序列要从哪里来？
我们用 ['A', 'B', 'C', 'D', 'E'] 和 [A', 'B', 'E', 'C', 'D'] 来做例子。
// 旧节点： A B C D E
// 新节点： A B E C D
// 经过前两轮判断之后，只剩下
// 旧节点：C D E
// 新节点：E C D
// 需要判断，我们其实一眼就可以看出 C D 在新旧节点中的位置是一致的，符合我们对 最长递增子序列 的判断。
// 那么我们就可以传递给 getSequence([5, 3, 4]) // [5, 3, 4] 是假设值，只是用数字来表示我们的节点
// 这里， 5 是 对应 E节点
// 3 对应 C节点
// 4 对应 D节点
// 这样 getSequence 就会返回 [1, 2]，【注】前面也提过 getSequence 返回的是 递增的子序列 的下标。
// 这里 C 和 D 是递增，分别在 下标1 和 下标2 的位置。所以 getSequence 返回 [1, 2]
// 那么我们就知道了这两个是递增的，当我们在后面遍历的过程中，遇到这2个节点，就不去处理。
// 而因为 E 节点不在这里，所以就需要移动(move)
// 5.3 移动 或 挂载
const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexList) : []
j = increasingNewIndexSequence.length - 1
// 从最后面开始遍历，以便我们可以从最后一个 patch 的节点作为 anchor 往前遍历
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i
const nextChild = c2[nextIndex] as VNode
// 如果 nextIndex + 1 超过最大 length，则需要赋值 parentAnchor
const anchor = nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
// 0 则表示是新增的节点，再次 patch
if (newIndexToOldIndexList[i] === 0) {
patch(null, nextChild, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized)
} else if (moved) {
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, MoveType.REORDER)
} else {
j--
}
}
}
总结
Diff 算法的一切都是为了用相对高效的 JS 计算 取代 低效的 DOM 操作
所以哪怕时间复杂度相对高了些，也不用太在意（取舍，不可兼得）
不过，现在有两个流行的 无虚拟DOM 的框架，solidjs 和 selvetjs ，Vue 也要做 无虚拟DOM 了，感慨技术之发展，后面也去学习学习，瞅瞅原理。
真好奇，没有虚拟 DOM 如何做到那种 DOM 改动的优化，模板感觉还好，毕竟有一层 AST 层了，应该可以好好操作一番， solidjs 是一种跟 React 一样的 jsx 语法，难道是通过 jsx 去弄。。。
（虽然可能虚拟 DOM 在未来会被淘汰，不过我们学的主要是那种设计，思路。。。其次就是这种知识从脑子穿过没留下什么痕迹的感觉很棒，(ㄒ o ㄒ)）
转载自:https://juejin.cn/post/7237520441555370039