本文为原创文章，未获授权禁止转载，侵权必究！
本篇是 Vue3 源码解析系列第 18 篇，关注专栏
前言
上一篇我们分析了 diff 算法的前四步逻辑，第五步 乱序比对 逻辑 Vue 又分了三步来进行，那什么是 乱序比对 呢？我们知道节点的比较存在新增、删除、位置交换、内容更替等场景，通过前四步逻辑处理完后，剩余的节点依旧存在上述多种情况，这时我们就要采用 乱序比对 逻辑，接下来我们针对该逻辑逐一分析。
案例
首先引入 h 、 render函数，先渲染 vnode1 对象，它包含五个子节点 a b c d e，key 为 1 2 3 4 5，两秒后更新渲染 vnode2 对象，为了区分我们修改其内容，内容分别为 new-a new-c new-b new-f new-f，key 为 1 3 2 6 5。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Document</title>
<script src="../../../dist/vue.global.js"></script>
</head>
<body>
<div id="app"></div>
<script>
const { h, render } = Vue
const vnode1 = h('ul', [
h('li', { key: 1 }, 'a'),
h('li', { key: 2 }, 'b'),
h('li', { key: 3 }, 'c'),
h('li', { key: 4 }, 'd'),
h('li', { key: 5 }, 'e')
])
render(vnode1, document.querySelector('#app'))
setTimeout(() => {
const vnode2 = h('ul', [
h('li', { key: 1 }, 'new-a'),
h('li', { key: 3 }, 'new-c'),
h('li', { key: 2 }, 'new-b'),
h('li', { key: 6 }, 'new-f'),
h('li', { key: 5 }, 'new-e')
])
render(vnode2, document.querySelector('#app'))
}, 2000)
</script>
</body>
</html>
案例分析
通过上述案例，我们得知，a e 节点只是更新了内容，而 b c 节点需交替位置，d 节点需删除，f 节点需新增。接下来我们执行 diff 算法逻辑，先执行第一步 自前向后，第一个节点比较 type 和 key 相同，执行 patch 挂载更新，此时页面呈现：
由于第二节点比较 key 不同，直接 break 跳出循环，执行第二步逻辑 自后向前，最后个节点比较 type 和 key 相同，执行 patch 挂载更新，此时页面呈现：
第三、第四步逻辑条件均未满足，执行第五步逻辑即 乱序比对。
根据案例，还剩余 b c d 节点未处理，当前 e1 = 3（旧节点结束下标）、e2 = 3（新节点结束下标）、i = 1（开始节点下标）、l2 = 5（新节点数量），可以看出 e1 对应旧节点的 d，e2 对应新节点的 new-f，i 分别对应旧节点的 b 和新节点的 new-c：
最长递增子序列
而 乱序比对 逻辑中，Vue 使用了 最长递增子序列 这样的一个概念。那什么是最长递增子序列呢？维基百科 这样定义： 在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。
举个例子：
旧节点：1, 2, 3, 4, 5, 6
新节点：1, 3, 2, 4, 6, 5
我们根据新节点生成 递增子序列（非最长且并不是唯一的），其结果为：
- 1, 3, 6
- 1, 2, 4, 5
- …
先依据第一个 1, 3, 6，这三个不动，那么就要移动 2, 4, 5 三个做对应的移动，而依据 1, 2, 4, 5，则只需移动 3, 6 两个。至此，我们可以理解为 递增子序列 最长的一个移动次数最少。
而 Vue 中通过 getSequence 方法来获取 最长递增子序列，该方法定义在 packages/runtime-core/src/renderer.ts 文件中：
function getSequence(arr: number[]): number[] {
const p = arr.slice()
const result = [0]
let i, j, u, v, c
const len = arr.length
for (i = 0; i < len; i++) {
const arrI = arr[i]
if (arrI !== 0) {
j = result[result.length - 1]
if (arr[j] < arrI) {
p[i] = j
result.push(i)
continue
}
u = 0
v = result.length - 1
while (u < v) {
c = (u + v) >> 1
if (arr[result[c]] < arrI) {
u = c + 1
} else {
v = c
}
}
if (arrI < arr[result[u]]) {
if (u > 0) {
p[i] = result[u - 1]
}
result[u] = i
}
}
}
u = result.length
v = result[u - 1]
while (u-- > 0) {
result[u] = v
v = p[v]
}
return result
}
这里稍微有点区别，该方法是获取 最长递增子序列的下标，根据上面例子，最长递增子序列为 1, 2, 4, 5 则下标就是 0, 2, 3, 5，我们可以将该方法抽离出来写个例子：
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Document</title>
</head>
<body>
<script>
function getSequence(arr) {
// p 是一个最终的回溯数组，它会在最终的 result 回溯中被使用
// 它会在每次 result 发生变化时，记录 result 更新前最后一个索引的值
const p = arr.slice() // 浅拷贝数组
// 定义返回值（最长递增子序列下标），因为下标从 0 开始，所以它的初始值为 0
const result = [0]
let i, j, u, v, c
const len = arr.length // 数组长度
for (i = 0; i < len; i++) {
// 遍历
const arrI = arr[i] // 数组当前值
if (arrI !== 0) {
j = result[result.length - 1] // 下标数组最后一个元素 即：当前 result 中保存的最大值的下标
if (arr[j] < arrI) {
// 下标数组最后一个对应数组的值 和 当前数组值比较
p[i] = j
result.push(i)
continue
}
// 不满足 arr[j] < arrI 的条件，就证明目前 result 中的最后位置保存着最大数值的下标。
// 但是这个下标并不一定是一个递增的序列，比如： [1, 3] 和 [1, 2]
// 所以我们还需要确定当前的序列是递增的。
// 计算方式就是通过：二分查找来进行的
u = 0 // 初始下标
v = result.length - 1 // 最终下标
while (u < v) {
// 二分查找
c = (u + v) >> 1 // 找中间位
if (arr[result[c]] < arrI) {
// u（初始下标）= 中间位 + 1 从中间向右移动一位，作为初始下标。
//（下次直接从中间开始，往后计算即可）
u = c + 1
} else {
// v（最终下标） = 中间位。即：下次直接从 0 开始，计算到中间位置 即可。
v = c
}
}
// arrI < arr[result[u]] 证明当前 result 中存在的下标 不是 递增序列，则需要进行替换
if (arrI < arr[result[u]]) {
if (u > 0) {
p[i] = result[u - 1]
}
result[u] = i // 替换为递增序列
}
}
}
// 回溯逻辑
// 重新定义 u。此时：u = result 的长度
u = result.length
// 重新定义 v。此时 v = result 的最后一个元素
v = result[u - 1]
// 自后向前处理 result，利用 p 中所保存的索引值，进行最后的一次回溯
while (u-- > 0) {
result[u] = v
v = p[v]
}
return result
}
console.log(getSequence([1, 3, 2, 4, 6, 5]))
</script>
</body>
</html>
p 浅拷贝一份传入的数组，由于数组下标是从 0 开始的，所以 result 初始值为 [0]。之后遍历数组，判断当前值不为 0，接着设置 j 为 下标数组 result 最后一个元素，即当前 result 中保存的最大值的下标。
然后根据下标值 j 获取到传入数组对应的值 arr[j] 和 当前值 arrI 比较，我们直接从第二次遍历查看，j = 0，i = 1，此时 p 没修改前：
修改后 p[i] = j ：
可见 p 作用它会在 result 发生变化时，记录 result 更新前最后一个索引值，之后再将当前下标 i 插入 result 中，此时结果为：
第三次遍历，arr[j] < arr[i] 即 3 < 2 不满足条件，就证明目前 result 中的最后位置保存着最大数值的下标，但这个下标并不一定是一个递增的序列，比如： [1, 3] 和 [1, 2]，所以我们还需要确定当前的序列是递增的，计算方式就是通过 二分查找 来进行。
后续执行 while 遍历，我们可以理解为这段是 二分查找。u 为初始下标，v 为最终下标，当前 v 为 1，(0 + 1) >> 1 右移算出中间位 c，当前右移 1 位，等于 1 除以 2 得到 0。
之后从 result 中根据 c（中间位） 取出中间位的下标，然后利用中间位的下标，从传入的数组 arr 中取出对应的值 arr[result[c]]，和当前值 arrI 比较。如果小于，则 u（初始下标）= 中间位 + 1，即：从中间向右移动一位，作为初始下标（下次直接从中间开始，往后计算即可）。否则 v（最终下标）= 中间位，即：下次直接从 0 开始，计算到中间位置 即可。
根据计算得到目标下标位 u，此时为 1：
利用 u 从 result 中获取 下标，然后拿到 arr 中对应的值 arr[result[u]] 和当前值 arrI 比较。如果 arrI < arr[result[u]] ，则证明当前 result 中存在的下标 不是 递增序列，则需要进行替换。当前 2 < 3 满足条件，重新计算 p 和 result 值：
遍历完成，此时 result、p 对应的值：
最后一段逻辑做了回溯处理，与原来一致，我们再看下打印的结果：
乱序比对
讲完了 最长递增子序列，我们回过来再看下第五段逻辑：
else {
// 旧子节点的开始索引
const s1 = i // prev starting index
// 新子节点的开始索引
const s2 = i // next starting index
// 5.1 build key:index map for newChildren
// 5.1 创建一个 <key（新节点的 key）:index（新节点的位置）> 的 Map 对象 keyToNewIndexMap。
// 通过该对象可知：新的 child（根据 key 判断指定 child） 更新后的位置（根据对应的 index 判断）在哪里
const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
// 通过循环为 keyToNewIndexMap 填充值
for (i = s2; i <= e2; i++) {
// 从 c2 中根据开始索引获取每一个 child
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
// child 必须存在 key（这也是为什么 v-for 必须要有 key 的原因）
if (nextChild.key != null) {
if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {
warn(
`Duplicate keys found during update:`,
JSON.stringify(nextChild.key),
`Make sure keys are unique.`
)
}
// 把 key 和 对应的索引，放到 keyToNewIndexMap 对象中
keyToNewIndexMap.set(nextChild.key, i)
}
}
// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
// 5.2 循环 oldChildren ，并尝试进行 patch（打补丁）或 unmount（删除）旧节点
let j
// 记录已经修复的新节点数量
let patched = 0
// 新节点待修补的数量 = e2 - s2 + 1
const toBePatched = e2 - s2 + 1
// 标记位：节点是否需要移动
let moved = false
// used to track whether any node has moved
// 配合 moved 进行使用，它始终保存当前最大的 index 值
let maxNewIndexSoFar = 0
// works as Map<newIndex, oldIndex>
// Note that oldIndex is offset by +1
// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// used for determining longest stable subsequence
// 创建一个 Array 的对象，用来确定最长递增子序列。
// 它的下标表示：新节点的下标（newIndex），不计算已处理的节点，元素表示：对应旧节点的下标（oldIndex），永远 +1
// 但是，需要特别注意的是：oldIndex 的值应该永远 +1
//（因为 0 代表了特殊含义，他表示 新节点没有找到对应的旧节点，此时需要新增新节点）。
// 即：旧节点下标为 0， 但是记录时会被记录为 1
const newIndexToOldIndexMap = new Array(toBePatched)
// 遍历 toBePatched ，为 newIndexToOldIndexMap 进行初始化，初始化时，所有的元素为 0
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
// 遍历 e1，获取旧节点，
// 如果当前 已经处理的节点数量 > 待处理的节点数量，
// 那么就证明：所有的节点都已经更新完成，剩余的旧节点全部删除即可
for (i = s1; i <= e1; i++) {
// 获取旧节点
const prevChild = c1[i]
// 如果当前 已经处理的节点数量 > 待处理的节点数量，
// 那么就证明：所有的节点都已经更新完成，剩余的旧节点全部删除即可
if (patched >= toBePatched) {
// all new children have been patched so this can only be a removal
// 所有的节点都已经更新完成，剩余的旧节点全部删除即可
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
// 新节点需要存在的位置，需要根据旧节点来进行寻找（包含已处理的节点）
let newIndex
// 旧节点的 key 存在时
if (prevChild.key != null) {
// 根据旧节点的 key，从 keyToNewIndexMap 中可以获取到新节点对应的位置
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
// key-less node, try to locate a key-less node of the same type
// 旧节点的 key 不存在（无 key 节点）
// 那么我们就遍历所有的新节点，找到 没有找到对应旧节点的新节点，并且该新节点可以和旧节点匹配，
// 如果能找到，那么 newIndex = 该新节点索引
for (j = s2; j <= e2; j++) {
// 找到 没有找到对应旧节点的新节点，并且该新节点可以和旧节点匹配
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j] as VNode)
) {
// 如果能找到，那么 newIndex = 该新节点索引
newIndex = j
break
}
}
}
// 最终没有找到新节点的索引，则证明：当前旧节点没有对应的新节点
if (newIndex === undefined) {
// 此时，直接删除即可
unmount(prevChild, parentComponent, parentSuspense, true)
}
// 没有进入 if，则表示：当前旧节点找到了对应的新节点，
// 那么接下来就是要判断对于该新节点而言，是要 patch（打补丁）还是 move（移动）
else {
// 为 newIndexToOldIndexMap 填充值：
// 下标表示：新节点的下标（newIndex），不计算已处理的节点。元素表示：对应旧节点的下标（oldIndex），永远 +1
// 因为 newIndex 包含已处理的节点，所以需要减去 s2，表示：不计算已处理的节点
newIndexToOldIndexMap[newIndex - s2] = i + 1
// maxNewIndexSoFar 会存储当前最大的 newIndex，它应该是一个递增的，
// 如果没有递增，则证明有节点需要移动
if (newIndex >= maxNewIndexSoFar) {
// 持续递增
maxNewIndexSoFar = newIndex
} else {
// 没有递增，则需要移动，moved = true
moved = true
}
// 打补丁
patch(
prevChild,
c2[newIndex] as VNode,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
// 自增已处理的节点数量
patched++
}
}
// 5.3 move and mount
// generate longest stable subsequence only when nodes have moved
// 仅当节点需要移动的时候，我们才需要生成最长递增子序列，否则只需要有一个空数组即可
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
// j >= 0 表示：初始值为 最长递增子序列的最后下标
// j < 0 表示：不存在最长递增子序列。
j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
// 倒序循环，以便我们可以使用最后修补的节点作为锚点
for (i = toBePatched - 1; i >= 0; i--) {
// nextIndex（需要更新的新节点下标） = s2 + i
const nextIndex = s2 + i
// 根据 nextIndex 拿到要处理的 新节点
const nextChild = c2[nextIndex] as VNode
// 获取锚点（是否超过了最长长度）
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
// 如果 newIndexToOldIndexMap 中保存的 value = 0，
// 则表示：新节点没有用对应的旧节点，此时需要挂载新节点
if (newIndexToOldIndexMap[i] === 0) {
// mount new
// 挂载新节点
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
}
// moved 为 true，表示需要移动
else if (moved) {
// move if:
// There is no stable subsequence (e.g. a reverse)
// OR current node is not among the stable sequence
// j < 0 表示：不存在 最长递增子序列
// i !== increasingNewIndexSequence[j] 表示：当前节点不在最后位置
// 那么此时就需要 move （移动）
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, MoveType.REORDER)
} else {
// j 随着循环递减
j--
}
}
}
}
该逻辑又分了三部分来进行处理，结合案例，a e 节点已处理完毕，还剩余 b c d 节点未处理。当前 e1 = 3（旧节点结束下标）、e2 = 3（新节点结束下标）、i = 1（开始节点下标）、l2 = 5（新节点数量）。我们先看下第一段逻辑：
const s1 = i // prev starting index
const s2 = i // next starting index
// 5.1 build key:index map for newChildren
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) {
if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {
warn(
`Duplicate keys found during update:`,
JSON.stringify(nextChild.key),
`Make sure keys are unique.`
)
}
keyToNewIndexMap.set(nextChild.key, i)
}
}
该逻辑主要是构建 keyToNewIndexMap map对象，将新节点的 key 作为 键，新节点的 下标 作为 值。s1 为旧节点的开始下标，s2 为新节点的开始下标，e2 为新节点的结束下标。
之后遍历新节点，先获取当前新节点 new-c，判断当前新节点的 key 是否存在，这也就是为什么 v-for 必须设置 key 的原因，对于当前判断 key 必须存在且不能重复，接着将 新节点的 key 作为 键，新节点的 下标 作为 值 来设置 keyToNewIndexMap 对象，遍历执行完，结果为：
new-c new-b new-f 的 key 和 下标 对应关系：
下面执行第二段逻辑：
// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
let j
let patched = 0
const toBePatched = e2 - s2 + 1
let moved = false
// used to track whether any node has moved
let maxNewIndexSoFar = 0
// works as Map<newIndex, oldIndex>
// Note that oldIndex is offset by +1
// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// used for determining longest stable subsequence
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
for (i = s1; i <= e1; i++) {
const prevChild = c1[i]
if (patched >= toBePatched) {
// all new children have been patched so this can only be a removal
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
let newIndex
if (prevChild.key != null) {
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
// key-less node, try to locate a key-less node of the same type
for (j = s2; j <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j] as VNode)
) {
newIndex = j
break
}
}
}
if (newIndex === undefined) {
unmount(prevChild, parentComponent, parentSuspense, true)
} else {
newIndexToOldIndexMap[newIndex - s2] = i + 1
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
patch(
prevChild,
c2[newIndex] as VNode,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
patched++
}
}
其实 Vue 注释已经写的很清楚了，该逻辑主要是遍历旧节点，尝试打补丁或者删除节点。
这里 j 我们暂时先不管；patched 记录已经修复的新节点数量，比如当前还剩三个节点未修复，默认是 0；toBePatched 是新节点待修复数量，当前为 3；moved 为标记，代表当前节点是否需要移动；maxNewIndexSoFar 是配合 moved 是否有节点移动，保存着最大 newIndex 值；newIndexToOldIndexMap 为数组，它的下标表示新节点的下标，元素表示旧节点的下标，Vue 通过数组形式来表示 map <newIndex，oldIndex> 中数据。
另外还需注意的是，当前数组的下标是不计算已经处理好的节点。 换句话说，根据案例，第一个节点 new-a 已经处理完毕，下标是 0；而第二个节点 new-c 待处理，下标是 1。那对于 map <newIndex，oldIndex> 而言，new-c 存放时是不会计算已经处理好的节点，当前数组的下标 0 就代表 new-c 节点。
而元素为旧节点的下标，但是必须 +1（根据注释），这是为什么呢？
后续执行遍历，将 newIndexToOldIndexMap 设置默认值都为 0。这里的 0 存在特殊含义，会在第三段逻辑中使用，所以当值表示旧节点下标时就不能再设置为 0，旧节点下标就必须 +1。
接着遍历旧节点，s1 为旧节点的开始下标，e1 为旧节点的结束下标，第一次遍历，此时 prevChild 当前旧节点为 b。之后根据判断 patched >= toBePatched，前面我们得知 patched 表示已经处理的节点数量，toBePatched 表示待处理的节点数量。当 patched >= toBePatched 时，就表示所有节点都处理完毕，执行 unmount 方法删除旧节点即可。当前 patched = 0、toBePatched = 3 不满足条件，执行后续逻辑。
定义 newIndex 变量，表示新节点存放的位置，它需要根据旧节点来进行寻找。但是我们前面讲到 newIndexToOldIndexMap 的下标 newIndex 是不计算已经处理好的节点，而这里的 newIndex 是计算已经处理好的节点，也就是说对于 new-c 节点下标为 1，假如要将下标设置给 newIndexToOldIndexMap，需要 减1。
当前旧节点 b 存在 key 为 2，新节点下标 newIndex 通过 keyToNewIndexMap 根据旧节点 key 获取，此时为 2：
旧节点 key 如果不存在，执行 else 逻辑，该逻辑是遍历所有的新节点，找到 没有找到 对应旧节点的新节点，并且该新节点可以和旧节点匹配，如果能找到，那么 newIndex = 该新节点的索引。
之后判断 newIndex 是否为空，为空则表示没有找到新节点的索引，即当前旧节点没有对应的新节点，直接 unmount 删除即可，根据案例旧节点 d 存在该场景。
此时 newIndex 存在，执行 else 逻辑。我们知道 newIndexToOldIndexMap 数组下标保存的是 新节点的下标且不去计算已处理的新节点，那么怎么计算不处理的新节点呢？当前 newIndex 是计算已处理新节点的，s2 为已处理新节点的开始下标，那么 newIndex - s2 剩余的就表示未处理的新节点，value 元素 表示 旧节点下标 且永远 +1。
当前 newIndex 是 2，s2 是 1 表示第一个节点 new-a 已经处理完，newIndex - s2 = 1，所以 new-c 下标为 0，new-b 下标为 1，newIndexToOldIndexMap[1] 就是 new-b 节点，结果为 2。
而 maxNewIndexSoFar 会存储当前最大的 newIndex，它应该是一个递增的，如果没有递增，则证明有节点需要移动。通过上面我们分析的 最长递增子序列，不符合递增子序列的，我们就需要判断是否进行移动，移动即 moved = true
接着执行 patch 更新节点，当前旧节点为 b，新节点为 new-b，此时页面呈现：
之后下一轮遍历，旧节点 c，新节点为 new-c，此时页面呈现：
第三次遍历，newIndex 为空表示未找到新节点索引，直接删除旧节点 d，页面呈现：
下面执行第三段逻辑：
// 5.3 move and mount
// generate longest stable subsequence only when nodes have moved
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i
const nextChild = c2[nextIndex] as VNode
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
if (newIndexToOldIndexMap[i] === 0) {
// mount new
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else if (moved) {
// move if:
// There is no stable subsequence (e.g. a reverse)
// OR current node is not among the stable sequence
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, MoveType.REORDER)
} else {
j--
}
}
}
当前显示结果和原节点对比，我们发现还有些区别，new-b 和 new-c 节点需要移动，new-f 节点需要新增：
该逻辑主要进行移动和挂载的处理，需要配合最长递增子序列。
当前 moved = true，通过 getSequence 方法获取最长递增子序列的下标数组，即 [1]：
j 的初始值是最长递增子序列最后值的下标，当前为 0。接着执行遍历，可以看出循环是倒叙的，toBePatched 表示待处理的节点。nextIndex = s2 + i 表示新节点需要更新的下标，通过下标获取当前新节点 c2[nextIndex]，当前为 new-f 元素。
之后通过计算获取 anchor 锚点，nextIndex + 1 表示当前节点的后面一个节点的长度，l2 为新节点长度，nextIndex + 1 < l2 表示是否超过新节点长度，没超过锚点就为当前节点的后面一个节点，当前为 new-e 节点，表示要插入该节点前面。
接着根据判断 newIndexToOldIndexMap[i] === 0 表示新节点没有对应的旧节点，需要进行挂载操作，当前 new-f 节点未匹配到，执行挂载，此时页面呈现：
第二次循环，当前 nextChild 为 new-b 节点，锚点为 new-f 节点，根据判断需要执行移动逻辑。而 j < 0 表示不存在递增子序列，我们可以理解为：当 j 初始值最长递增子序列为 1 时，j 为 0，当最长递增子序列为 0 时， j 为 -1；也就是说 j 一旦小于 0，就表示最长递增子序列不存在。
i !== increasingNewIndexSequence[j] 表示当前节点不在最后位置，我们可以理解为： 当 j > 0 表示最长递增子序列最后一个下标，再用 j 获取最长递增子序列最后一个元素，如果不等于当前节点的 i，就表示当前节点不在最后位置。
根据判断执行 j--，表示当前页面未发生变化，也就是 new-b 未移动。new-b 未移动则表示 new-c 需要移动，此时页面呈现：
第三次循环，当前 nextChild 为 new-c 节点，锚点为 new-b 节点，此时 j = -1，不存在最长递增子序列，执行 move 方法：
const move: MoveFn = (
vnode,
container,
anchor,
moveType,
parentSuspense = null
) => {
const { el, type, transition, children, shapeFlag } = vnode
if (shapeFlag & ShapeFlags.COMPONENT) {
move(vnode.component!.subTree, container, anchor, moveType)
return
}
if (__FEATURE_SUSPENSE__ && shapeFlag & ShapeFlags.SUSPENSE) {
vnode.suspense!.move(container, anchor, moveType)
return
}
if (shapeFlag & ShapeFlags.TELEPORT) {
;(type as typeof TeleportImpl).move(vnode, container, anchor, internals)
return
}
if (type === Fragment) {
hostInsert(el!, container, anchor)
for (let i = 0; i < (children as VNode[]).length; i++) {
move((children as VNode[])[i], container, anchor, moveType)
}
hostInsert(vnode.anchor!, container, anchor)
return
}
if (type === Static) {
moveStaticNode(vnode, container, anchor)
return
}
// single nodes
const needTransition =
moveType !== MoveType.REORDER &&
shapeFlag & ShapeFlags.ELEMENT &&
transition
if (needTransition) {
if (moveType === MoveType.ENTER) {
transition!.beforeEnter(el!)
hostInsert(el!, container, anchor)
queuePostRenderEffect(() => transition!.enter(el!), parentSuspense)
} else {
const { leave, delayLeave, afterLeave } = transition!
const remove = () => hostInsert(el!, container, anchor)
const performLeave = () => {
leave(el!, () => {
remove()
afterLeave && afterLeave()
})
}
if (delayLeave) {
delayLeave(el!, remove, performLeave)
} else {
performLeave()
}
}
} else {
hostInsert(el!, container, anchor)
}
}
将 new-c 节点移动到 new-b 节点前面，此时页面呈现：
至此，我们所有节点都处理完毕。
总结
diff算法的第五段逻辑即乱序比对分为三步骤来处理。- 第一步构建
keyToNewIndexMap对象，将新节点的key作为键，新节点的下标作为值。 - 第二步循环旧节点，尝试
打补丁或者删除节点。 - 第三步
移动和挂载节点的处理，需要配合最长递增子序列。
Vue3 源码实现
Vue3 源码解析系列
- Vue3源码解析之 源码调试
- Vue3源码解析之 reactive
- Vue3源码解析之 ref
- Vue3源码解析之 computed
- Vue3源码解析之 watch
- Vue3源码解析之 runtime
- Vue3源码解析之 h
- Vue3源码解析之 render（一）
- Vue3源码解析之 render（二）
- Vue3源码解析之 render（三）
- Vue3源码解析之 render（四）
- Vue3源码解析之 render component（一）
- Vue3源码解析之 render component（二）
- Vue3源码解析之 render component（三）
- Vue3源码解析之 render component（四）
- Vue3源码解析之 render component（五）
- Vue3源码解析之 diff（一）
- Vue3源码解析之 diff（二）
原文链接：https://juejin.cn/post/7321569896454127627 作者：JasonChen
