前言#
这一步在昨天我们分析了，不过由于这块对于八股文来说还是比较重要的，所以单独抽出来搞一篇文章
坏蛋Dan：vue runtime源码分析学习——day6：patch打补丁part2:根据不同类型进行patch处理
diff算法#
这里的diff算法相信大家都比较熟悉了，这个是vue面试八股文基本绕不过的点。
我们今天来跟着源码分析下到底是怎么做的。
例子模拟#
在开始分析之前，我们需要搞一个例子，这样可视化方便分析。
现在我们有一组旧的节点集合[a, b, c, d];
新的具体情况具体分析
1. 从前往后同步#
const l2 = c2.length
let e1 = c1.length - 1 // prev ending index
let e2 = l2 - 1 // next ending index
// 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的条件是按最短的那个来的，也就是短桶规则。
此时我们模拟新的节点集合是[a, b, d, e]
这个时候则是：
先是从前往后，如果类型和key有一点不同就直接跳过，如果相同就递归调用patch。
2. 从后往前同步#
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--
}和上面的逻辑一样，不过这次是从后往前。
模拟例子：[a, b, d]
你可能会有些担心这里和前面从前往后同步的节点patch重复了。
其实完全没必要担心，观察下我们的这个i，它并没有被重置，也就是说它是整个patch过程共用的一个索引，而我们的这个第二步从后往前同步的操作则是为了第一步执行完了还有遗漏的节点
我们再来看个例子
模拟的例子还是[a, b, d]
可以看到每部分patch的内容是不同的,这里是并集，也就是ABD都被patch了。
另外还有一点就是patch阶段第一部分：判断两个节点是否引用的同一块内存空间，如果是则直接return，所以完全没必要担心。
这里遗漏的也可能是新节点，因为我们是根据短桶效应来实现的。所以哪个短，哪个先跑完。剩下的就被遗漏了。
3. 常规序列 + mount(common sequence + mount)#
在开始分析之前，我们需要先确认下我们的三个标志位：
假设我们这里的例子是 旧的：[a, b, c, d]，而新的: [a, b, d]，那么最短的就是新的那组。e1表示旧的数组length - 1，初始值是3; e2表示新的数组length - 1，初始值是2；而i的初始值为0。
- i：从前往后第一次匹配到不相同节点的索引值，最大值是e2 + 1即新的数组后面几个元素被删掉了的场景。在这里在上面的这个假设中的值是2，也就是就数组c和新数组d匹配不上，break之后的值。
- e1：在我们的这个假设里，走完第二步之后值是2。它的最小值是i - 1。
- e2：在我们的这个假设里，走完第二步之后值是1。它的最小值是i - 1。
e1和e2都为最小值的场景既是没有发生顺序上的变化。
不过需要注意，可能存在-1的场景，比如旧：[a, b, c, d]，新：[e, a, b, c, d]，此时i为0，而在执行第二步的时候由于后面两个是一样的，导致多执行了一次让e1变成了-1。
为什么要分析这三个标志位之间的关系呢？因为我们需要清晰知道这三个字段的逻辑，这样分析起来才能通顺。
看完上面的几个图，大家应该发现了我们前面两步并没有将它们彻底处理完毕，会有节点被遗漏。比如旧的[a, b, c, d]，新的[a, b, c, d, e]或者[e, a, b, c, d]，这个时候e会被遗漏。
来看下代码
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++
}
}
}e1小于i的会是什么场景呢？
只有头或者尾部新增了节点的场景，也就是这个例子： 旧的[a, b, c, d]，新的[a, b, c, d, e]或者[e, a, b, c, d]
所以此时的旧节点数组全都匹配完毕了，剩下的都是新增的节点放在头或者尾。这个时候只需要patch i到e2之间的内容即可。
总结下：我们第三步就是把头尾任意一方新增了节点的场景给处理了。
注意，这里只处理任意一方加上，而不是头尾都有，第三步还无法处理这个问题。
4. 常规序列 + unmount(common sequence + unmount)#
else if (i > e2) {
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
}这个就好理解了，第三步是旧节点被匹配完了，现在变成新节点被匹配完了，还剩下头或者尾任意一处地方还剩下一些旧节点需要被移除。
第四步也无法处理头尾两头都有移除的场景
注意，这里可以看出我们的每一步都不是必要的，有可能不符合条件被跳过。
在进入下一步分析之前，我们来稍微总结下我们现在可以处理哪些场景：
- 节点集合中多个连续节点被删除，注意是连续。执行逻辑是第一步 + 第二步。例子：旧的[a, b, c, d]，新的[a, d]。
- 节点集合中多个连续节点被替换，注意是连续。执行逻辑是第一步 + 第二步 + 第三步。例子：[a, b, c, d]，新的[a, b, e, f, c, d]。
- 节点列表集合中头/尾连续节点新增/删除，注意是连续：
- 头连续新增：执行逻辑是第二步 + 第三步。例子：旧的[a, b, c, d]，新的[e, f, a, b, c, d]
- 尾连续新增：执行逻辑是第一步 + 第三步。例子：旧的[a, b, c, d]，新的[a, b, c, d, e, f]。
- 头连续删除：执行逻辑是第二步 + 第四步。例子：旧的[a, b, c, d]，新的[c, d]。
- 尾连续删除：执行逻辑是第一步 + 第四步。例子：旧的[a, b, c, d]，新的[a, b]。
现在还不能处理：
- 头尾都有新增/删除或者头尾一方删除一方新增的场景或者头尾有修改（即删除 + 新增）的场景。例子：
- 头尾都有新增：旧的[a, b, c, d]，新的[e, a, b, c, d, f]。
- 头尾都有删除：旧的[a, b, c, d]，新的[b, c]。
- 头尾一方删除一方新增：旧的[a, b, c, d]，新的[b, c, d, e]。
- 头/尾(包括头 + 尾)有修改：旧的[a, b, c, d]，新的[e, b, c, f]。
- 列表中间不连续删除/新增，例子：
- 不连续删除：旧的[a, b, c, d, e]，新的[a, c, e]。
- 不连续新增：旧的[a, b, c, d]，新的[a, e, b, f, c, g, d]。
- 不连续新增 + 删除（即修改）：旧的[a, b, c, d, e]，新的[a, c, f, d, e]
总结下，如果新旧任意一方在前面两步中被匹配完了，也就是e1/e2 < i的情况，那么这个时候我们就可以处理。反之则不行。
5. 不规则序列(unknown sequence)#
代码稍微有些长。
我们一块一块来分析
5.1 为新的节点创建key:index的map
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)
}
}这里直接给e2一组数组，创建一个key: index的map，也就是keyToNewIndexMap。
这里还有一个我们非常常见的warn，那就是key值重复的时候。
这个keyToNewIndexMap表示的是新数组中存在旧数据的节点（不包括前面四步patch处理过的）的key和它所在的位置index。
5.2 遍历旧节点组，尝试patch匹配到的节点以及移除匹配不到的节点
// 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++
}
}- patched：这个字段是用来记录当前到底搞到了多少个节点了，如果超出新数组里剩余的数量，那旧数组中的遍历剩下的节点就可以直接删除了。
- toBePatched：它表示剩余的需要被patch的节点个数，由于索引是从0开始，所以这里给它加1。
- moved：这个字段表示存在有节点被移动了位置。
- maxNewIndexSoFar：这个应该是用来跟踪是否有节点被moved了。
- newIndexToOldIndexMap：用来表示最长的稳定子序列，也就是删除/新增的连续的子序列最长的长度。它的作用相当于Map，这里需要注意oldIndex都是+ 1的，如果其中一个元素的oldIndex为0，那么就表示这个节点是新增的，没有与之对应的旧节点。
先给newIndexToOldIndexMap填充toBePatched个0，表示这些节点都是需要被patch的。
然后循环旧节点数组中还没有识别过的节点，i从s1开始，也就是第五步之前的i的值，而结束的位置是e1。
如果patched大于toBePatched，那么就将剩下循环中的旧节点移除,因为此时新的数组早已经处理完毕了。
接着如果旧节点的key不是null，那么这里就拿来和keyToNewIndexMap里的新节点的key做匹配，然后赋值给newIndex，这里就是在通过key匹配新旧节点。
这个keyToNewIndexMap前面说过它的类型是Map表示新的数组中依旧保留的旧节点（不包括前面四步patch处理过的）的key以及它的位置index。
如果匹配到了，那这个节点就可以保留，并且它最新的位置也就是index也已经知道了，就不用费劲脑子去知道它在新的数组里的状态是移动还是其它场景了。
而如果key不存在，那么表示这个旧节点之前就没有设置key（这是一种不好的习惯）这个时候只能尽力去匹配了，如果newIndexToOldIndexMap里还有元素是0，那就表示这个节点并没有被匹配过，可能是这个没有设置key的旧节点的对应节点。
当然，也有可能不是，所以这里还需要进一步判断，调用isSameVNodeType来判断下这俩节点是否是同一个type，这里已经尽力了，可能还是有问题，所以我们开发的时候得带上key就是这个原因。
而如果旧节点的key不为null，但是却在新的里面也匹配不到，那么这个节点就可以被抛弃了，直接调用unmount方法将它移除。
如果newIndex不为undefined，那么就表示这个旧的节点有对应的新的节点，且这个newIndex就是这个旧节点在新节点里的位置。此时将newIndexToOldIndexMap里的newIndex索引对应的元素标记为i + 1，表示这个旧节点已经心有所属了。
如果newIndex大于等于maxNewIndexSoFar，那么就将newIndex的值赋值给maxNewIndexSoFar，表示这个子序列是连续的，而如果不是，那么将moved标志位置为true，表示这个序列断开了。
然后再调用patch方法将这俩新旧节点进行打补丁处理。
5.3 move 和 mount, 仅当节点们被moved时创建最长的稳定子序列
// 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--
}
}
}- getSequence：这个方法我们就不看了，简单的说就是一个计算最长递增子序列的算法，简单的举个例子：0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15的最长递增子序列是0, 2, 6, 9, 11, 15.，当然并不一定只有一个，这个是其中一个。具体可以看：https://en.wikipedia.org/wiki/Longest_increasing_subsequence
这一步就是在处理新的节点，由于前面5.2中我们是按顺序自增匹配的，因为里面可能存在没有key的旧节点找到新节点的场景，所以从后往前找命中还没有patch的新增节点的概率更大一些。
如果找到newIndexToOldIndexMap里面为0的元素，那就代表这个元素对应的下标值在新数组中对应的节点是新增的还没有被patch。
这个时候将它patch掉，那么到这里，我们的diff就完全匹配完了。
总结#
其实不是很难，主要是要考虑的场景很多。
有一点需要注意，实际上上面说的diff算法只是一小块diff逻辑。diff是在patch函数执行那一刻的时候就开始了，而不是专指这里的diff算法。
编辑于 2023-03-08 18:10・IP 属地广东