快速 Diff 算法
Vue.js 3 借鉴了 ivi 和 inferno 这两个框架中使用的算法：快速 Diff 算法，这个算法的性能优于 Vue.js 2 中所采用的 双端 Diff 算法.
以下涉及的源码位置均在：
vue-core-3.2.31-main\packages\runtime-core\src\renderer.ts中的patchKeyedChildren函数中
节点预处理
对于 相同位置 的 前置节点 和 后置节点，由于它们在新旧两组子节点中的相对位置不变，因此并 不需要 进行 移动 操作，只需 进行 patch更新 即可.
处理前置节点
通过开启一个 while 循环，从前往后 依次遍历新旧两组子节点：
- 若当前新旧节点 相同，则通过
patch进行 更新 - 若当前新旧节点 不同，则终止循环，即前置节点处理结束
Vue.js 3 中对应源码如下：
// 1. sync from start 处理前置节点 // (a b) c // (a b) d e while (i <= e1 && i <= e2) { const n1 = c1[i] const n2 = (c2[i] = optimized ? cloneIfMounted(c2[i] as VNode) : normalizeVNode(c2[i])) if (isSameVNodeType(n1, n2)) { patch( n1, n2, container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized ) } else { break } i++ } 复制代码
处理后置节点
通过开启一个 while 循环，从后往前 依次遍历新旧两组子节点：
- 若当前新旧节点 相同，则通过
patch进行 更新 - 若当前新旧节点 不同，则终止循环，即后置节点处理结束
Vue.js 3 中对应源码如下：
// 2. sync from end 处理后置节点 // a (b c) // d e (b c) 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( n1, n2, container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized ) } else { break } e1-- e2-- } 复制代码
处理剩余已知公共序列的节点
当完成 节点预处理 后，很可能出现以下两种情况，而这些剩余节点是很容易根据已处理过的前后节点推断出它们的具体位置的：
- 旧节点遍历完成，新节点有剩余，此时意味着有新节点需要挂载，通过
patch将剩余新节点依次进行 挂载 - 新节点遍历完成，旧节点有剩余，此时意味着有旧节点需要卸载，通过
unmount将剩余旧节点依次进行 卸载
Vue.js 3 中对应源码如下：
// 3. common sequence + mount // (a b) // (a b) c // i = 2, e1 = 1, e2 = 2 // (a b) // c (a b) // i = 0, e1 = -1, e2 = 0 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] = optimized ? cloneIfMounted(c2[i] as VNode) : normalizeVNode(c2[i])), container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized ) i++ } } } // 4. common sequence + unmount // (a b) c // (a b) // i = 2, e1 = 2, e2 = 1 // a (b c) // (b c) // i = 0, e1 = 0, e2 = -1 else if (i > e2) { // 新节点遍历完成 while (i <= e1) { // 旧节点还有剩余 // 卸载操作 unmount(c1[i], parentComponent, parentSuspense, true) i++ } } 复制代码
处理剩余未知序列的节点
直接来看 vue.js 3 在源码中举的例子：
旧节点： [i ... e1 + 1] => a b [c d e] f g 新节点： [i ... e2 + 1] => a b [e d c h] f g 当前索引： i = 2, e1 = 4, e2 = 5 复制代码
其中，经过 节点预处理 后的剩余节点，即 [c d e] 和 [e d c h] 的部分是乱序的，针对这部分节点的处理是很关键的：
- 通过
toBePatched保存新节点的数量，即toBePatched = e2 - s2 + 1 - 基于
newChildren的剩余节点，构造基一个形如key: index的keyToNewIndexMap索引映射，本质是一个Map对象 - 遍历旧的一组节点中剩余为处理的节点，进行
patch更新或unmount卸载
- 若当前遍历的 老节点的 key 能在
keyToNewIndexMap中获取到对应的索引值，则说明当前节点是可复用的节点，可通过patch进行 更新，并通过patched记录下当前已 被更新/被复用 的节点数 - 若当前遍历的 老节点的 key 不能在
keyToNewIndexMap中获取到对应的索引值，则说明当前的老节点通过unmount进行卸载 - 若
patched >= toBePatched，则说明所有剩余的新节点都已经在剩余旧节点中找到并更新完成，此时需要对旧节点中剩余老节点通过unmount进行卸载 - 若当前老节点对应新节点中的索引 小于 上一次记录的索引值，则说明当前节点需要移动，将
moved变量标识为true，便于后续基于 最长递增子序列 进行 移动 操作
- 通过以上操作后，可以通过构造一个 最长的稳定子序列 用于后续节点的 移动 操作，即 最长递增子序列算法
- 通过构建
newIndexToOldIndexMap数组，用于存储 当前新节点 在 老节点中 的索引值 - 基于
newIndexToOldIndexMap数组通过getSequence(newIndexToOldIndexMap)得到最长递增子序列，其中相关算法感兴趣的可自行研究 - 从后往前 遍历，其中索引
i指向新的一组子节点的最后一个节点，而索引j指向的是最长递增子序列中的最后一个元素
- 若当前新节点对应老节点中的索引为
0，则说明当前节点需要进行 挂载 - 若
moved为true则说明当前新节点需要进行 移动
Vue.js 3 中对应源码如下：
// 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-- } } } 复制代码
