Vue3.0diff算法及原理

ue 3.0 采取的 diff 算法和 2.0 的双端比较有点不同。大概的原理如下

// c1: a b [ c d e ] f g
// c2: a b [ d e c h ] f g


假如有如上的 c1 和 c2 新旧 children，在 diff 的时候，会有一个预处理的过程。

先从前往后比较，当节点不同时，不再往后进行比较。接着又从后往前进行比较，当节点不同时，不再往前进行比较。

经过预处理之后，c1 和 c2 真正需要进行 diff 的部分如下所示：

// c1: c d e
// c2: d e c h


最后利用 “最长递增子序列”，完成上述差异部分的比较，提高 diff 效率。

处理相同的前后节点

预处理过程代码如下所示：

const patchKeyedChildren = (c1,c2,container,parentAnchor,parentComponent,parentSuspense,isSVG,optimized
) => {let i = 0; const l2 = c2.lengthlet e1 = c1.length - 1let e2 = c2.length - 1// 1. sync from startwhile (i <= e1 && i <= e2) {const n1 = c1[i]const n2 = c2[i]if (isSameVNodeType(n1, n2)) {patch(n1,n2,container,parentAnchor,parentComponent,parentSuspense,isSVG,optimized)} else {break}i++}// 2. sync from endwhile (i <= e1 && i <= e2) {const n1 = c1[e1]const n2 = c2[e2]if (isSameVNodeType(n1, n2)) {patch(n1,n2,container,parentAnchor,parentComponent,parentSuspense,isSVG,optimized)} else {break}e1--e2--}
}

仅有节点新增或移除

进行预处理还有一个好处，就是在某些情况下，我们可以明确的知道有节点的新增或者删除。

• 节点新增

i、e1、e2 满足下述关系时，可以认为是有节点新增

// 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 } else if {//
} else {//
}


• 节点移除

i、e1、e2 满足下述关系时，可以认为是有节点被移除

// 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
if (i > e1) {//
} else if (i > e2) {while (i <= e1) {unmount(c1[i], parentComponent, parentSuspense, true)i++}
} else {//
}


有节点移动、新增或删除

有时候情况可能没有上述那么地简单，即 i、e1、e2 并不满足上述两种情形时，我们就要寻找其中需要被移除、新增的节点，又或是判断哪些节点需要进行移动。

为此，我们需要去遍历 c1 中还没有进行处理的节点，然后查看在 c2 中是否有对应的节点（key 相同）。没有，则说明该节点已经被移除，那就执行 unmount 操作。

首先，为了快速确认 c1 的节点在 c2 中是否有对应的节点及所在的位置，对 c2 中的节点建立一个映射 （key: index）

// 5. unknown sequence
// [i ... e1 + 1]: a b [c d e] f g
// [i ... e2 + 1]: a b [d e c h] f g
// i = 2, e1 = 4, e2 = 5
if (i > e1) {//
} else if (i > e2) {//
} else {const s1 = iconst s2 = iconst keyTOnewIndexMap= new Map()// 5.1 build key:index map for newChildrenfor (i = s2; i <= e2; i++) {const nextChild = c2[i]if (nextChild.key !== null) {keyToNewIndexMap.set(nextChild.key, i)}}
}

接着，定义以下几个变量

let j
let patched = 0
const toBePatched = e2 - s2 + 1 // c2 中待处理的节点数目
let moved = false// used to track whether any node has moved
let maxNewIndexSoFar = 0 // 已遍历的待处理的 c1 节点在 c2 中对应的索引最大值// works as Map
// 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 }


然后，遍历 c1 中待处理的节点，判断否 c2 中是有相同 key 的节点存在。

• 没有，说明该节点已经被移除，unmount。
• 有，调用 patch 函数。 并记录节点在 c1 中的索引。同时，记录节点在 c2 中的最大索引，假如节点在 c2 中的索引位置小于这个最大索引，那么说明是有元素需要进行移动。

// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
for (i = s1; i <= e1; i++) {const prevChild = c1[i]// (A)let newIndex if (prevChild.key !== null) {newIndex = keyToNewIndexMap.get(prevChild.key)} else {for (j = s2; i <= e2; j++) {if (newIndexToOldIndexMap[j - s2] === 0 &&isSameVNodeType(prevChild, c2[j])) {newIndex = jbreak}}}if (newIndex === void 0) {unmount(prevChild, parentComponent, parentSuspense, true)} else {newIndexToOldIndexMap[newIndex - s2] = i + 1 // (B)if (newIndex >= maxNewIndexSoFar) {maxNewIndexSoFar = newIndex} else {moved = true}patch(prevChild,c2[i],container,null,parentComponent,parentSuspense,isSVG,optimized)patched++ // (C)}
}


是不是 c1 中的所有节点都需要在 c2 中寻找对应节点，然后调用 patch 呢。

注意到上面的代码 (C)，我们会更新已经 patched 的节点的数目，那么当 patched > toBePatched，可以认为接下来遍历的 c1 中的节点都是多余的了，直接移除就好。

所以在上面的 (A) 处需要补充一下代码

if (patched >= toBePatched) {// all new children have been patched so this can only be a removalunmount(prevChild, parentComponent, parentSuspense, true)continue
}


到这里，就是较难理解的部分了。

开篇我们说过，预处理过后，剩下的节点会借助最长递增子序列来提高 diff 效率。

求解最长递增子序列，主要的目的就是为了减少 dom 元素的移动，也可以理解为最少的 dom 操作。

首先，我们需要求解得到最长递增子序列

// generate longest stable subsequence only when nodes have moved
const increasingNewIndexSequence = moved? getSequence(newIndexToOldIndexMap): EMPTY_ARR


先看看这里的 newIndexToOldIndexMap 的值是什么。

结合一下具体的例子，假设 c1 、c2 如下图所示

定义并初始化 newIndexToOldIndexMap

const newIndexToOldIndexMap = new Array(toBePatched)for (i = 0; i }


toBePatched 即预处理后，c2 中待处理的节点数目。对应这里的例子，会有

toBePatched = 4
newIndexToOldIndexMap = [0, 0, 0, 0]


注意到上面 5.2 遍历 c1 中节点的代码的 (B) 处，有

// 这里是 i + 1，不是 i
// 因为 0 是一个特殊值，表示这个是新增的节点
newIndexToOldIndexMap[newIndex - s2] = i + 1 // (B)


所以处理完 c1 中的节点后，将有

moved = true
newIndexToOldIndexMap = [4, 5, 3, 0]


那么，increasingNewIndexSequence 的值就是 getSequence(newIndexToOldIndexMap) 的返回值

// [4, 5, 3, 0] --> 最长递增子序列是 [4, 5]
// 对应的索引是 [0, 1]
increasingNewIndexSequence = [0, 1]


在求解得到最长递增子序列之后，剩下的就是遍历 c2 中的待处理节点，判断是否节点是否属于新增，是否需要进行移动。

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 + iconst nextChild = c2[nextIndex]const anchor =nextIndex + 1 最长递增子序列为 [] if (j <0 || i !== increasingNewIndexSequence[j]) {move(nextChild, container, anchor, MoveType.REORDER)} else {j--}}
}


最长递增子序列

在计算机科学中，最长递增子序列（longest increasing subsequence）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。 -- 维基百科

对于以下的原始序列0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15最长递增子序列为0, 2, 6, 9, 11, 15.值得注意的是原始序列的最长递增子序列并不一定唯一，对于该原始序列，实际上还有以下两个最长递增子序列0, 4, 6, 9, 11, 15
0, 4, 6, 9, 13, 15


最后

至此，Vue 3.0 的 diff 代码就分析完了，欢迎一起讨论。

具体的代码： renderer.ts

作者：流汗去
链接：https://juejin.cn/post/6844904104834105351
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。