Vue3 diff算法
# Vue3 diff算法
# 基本原理
首先会对新旧节点数组进行头部对比和尾部对比，如果节点相同，那么就可以直接原地复用而不用移动节点，从而获得较好的性能。首尾对比结束后，有几种情况。
说明：这部分内容的源码在core/renderer.ts at main · vuejs/core · GitHub (opens new window)
# 1. 头部对比
// i为遍历新
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
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
) // patch函数中，如果节点相同会直接返回
} else {
break // 节点类型不同直接退出循环，头部对比结束
}
i++ // 节点相同，进行下一节点的比较
}
# 2. 尾部节点对比
和头部节点对比的逻辑相同
while (i <= e1 && i <= e2) { // e1 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--
}
# 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
null,
(c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i])),
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
i++
}
}
}
# 4. 卸载旧节点
前序对比和尾部对比后，有可能新数组遍历完了，那么旧数组中的多余节点需要卸载。
// 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++
}
}
# 5. 中间部分乱序节点的处理
# 5.1 创建keyToNewIndexMap
为新节点数组的中间部分创建一个key:index的map，方便在遍历旧节点数组时查找对应新节点的索引。
// 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)
}
}
# 5.2 遍历旧数组，进行索引配对
大致过程为：首先创建一个长度和新数组中间部分一样长的数组newIndexToOldIndexMap，数组的索引对应新数组中间部分节点的索引偏移，数组的值为旧数组索引+1。这个数组用于下一步移动节点。遍历旧数组节点，填充newIndexToOldIndexMap，同时记录找到的新数组节点索引是否递增，不是递增说明需要移动，标记一下需要移动moved = true
简化版代码如下：
let patched = 0 // 表示已经匹配的节点数量
const toBePatched = e2 - s2 + 1 // number of new children 如 a b [c d e f] g h , e2 = 2 , s2 = 5
let moved = false // 标记是否需要移动节点
let maxNewIndexSoFar = 0 // 新数组目前的最大索引
// 创建一个 newIndex: oldIndex的数组
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0 // 初始化数组各项为0
//遍历旧节点数组中间部分的节点， 区间为[s1 , e1]
for(let i = s1 ; i <= e1 ; i++){
// 新数组已经被匹配完了，旧数组中多余节点要移除
if (patched >= toBePatched) {
// all new children have been patched so this can only be a removal
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
const newIndex = keyToNewIndexMap.get(c1[i].key) // c1为旧节点数组
if(newIndex === undefined) unmount(c1[i]) // 在新数组中找不到，说明要移除
else{
newIndexToOldIndexMap[newIndex - s2] = i + 1 // 为什么i+1?因为0要填充在新增的节点索引位置
if(newIndex >= maxNewIndexSoFar){
maxNewIndexSoFar = newIndex
}else{
moved = true // 新数组索引不是递增的，需要移动节点
}
patch(
prevChild,
c2[newIndex] as VNode,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
patched++
}
}
# 5.3 移动和渲染
根据数组newIndexToOldIndexMap找到就旧数组的最长递增子序列：
// generate longest stable subsequence only when nodes have moved
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
从后向前遍历新节点数组中间部分，如果节点是新增的节点就直接挂载，如果不是递增序列的节点就移动到正确位置，否则就直接遍历下一节点。
// 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--
}
}
}
# 完整源码
let i = 0
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++
}
// 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--
}
// 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++
}
}
// 5. unknown sequence
// [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
else {
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)
}
}
// 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 // number of new children
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++
}
}
// 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--
}
}
}
}