剖析Vue3.0 diff算法
diff算法的核心就是子节点之间的比对，主要分为两种情况（子节点有key和无key的情况）
if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
patchKeyedChildren(
c1 as VNode[],
c2 as VNodeArrayChildren,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
optimized
)
return
} else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
patchUnkeyedChildren(
c1 as VNode[],
c2 as VNodeArrayChildren,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
optimized
)
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
一.无Key的情况
当元素无key时，我们希望尽可能复用老节点
const patchUnkeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
anchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
optimized: boolean
) => {
c1 = c1 || EMPTY_ARR
c2 = c2 || EMPTY_ARR
const oldLength = c1.length // 老节点长度
const newLength = c2.length // 新节点长度
// 计算能复用的节点
const commonLength = Math.min(oldLength, newLength)
let i
for (i = 0; i < commonLength; i++) {
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
patch(
c1[i],
nextChild,
container,
null,
parentComponent,
parentSuspense,
isSVG,
optimized
)
}
// 老元素多余新元素，将老元素卸载掉
if (oldLength > newLength) {
// remove old
unmountChildren(c1, parentComponent, parentSuspense, true, commonLength)
} else {
// 将多余的新元素挂载到老节点上
mountChildren(
c2,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
optimized,
commonLength
)
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
二.有key的情况
diff算法的核心还是有key的情况的比对
let i = 0 // 开始索引
const l2 = c2.length;
let e1 = c1.length - 1 // 老节点最后的索引
let e2 = l2 - 1 // 新节点最后的索引
1
2
3
4
2
3
4
1.从头开始比对
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,
optimized
)
} else { // 否则跳出循环
break
}
i++
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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,
optimized
)
} else { // 非相同节点跳出循环
break
}
e1-- // 移动指针
e2--
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
3.同序列挂载
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
)
i++
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
新的节点个数多余老节点，（头部插入、尾部插入）
4.同序列卸载
else if (i > e2) {
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
}
1
2
3
4
5
6
2
3
4
5
6
老的节点个数多余新节点，（头部删除、尾部删除）
5.未知序列
5.1 根据key创建映射表
const s1 = i // 确定老节点开始位置
const s2 = i // 确定新节点开始位置
const keyToNewIndexMap: Map<string | number, 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) { // 创建key的映射表
keyToNewIndexMap.set(nextChild.key, i)
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
在这里我们需要将未patch的新节点根据key和索引制作成映射表，为后续复用逻辑做准备
5.2 循环老节点依次进行patch
let j
let patched = 0; // 标记已经patched个数
const toBePatched = e2 - s2 + 1 // 标记还需要patched的个数
let moved = false // 是否需要移动
let maxNewIndexSoFar = 0 // 临时标记
const newIndexToOldIndexMap = new Array(toBePatched) // 根据需要patched的个数创建数组
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
}
// ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
如果新节点没有需要patched，则循环老节点，将老节点依次进行卸载
let newIndex
if (prevChild.key != null) { // 通过老节点的key去新节点中找到对应索引
newIndex = keyToNewIndexMap.get(prevChild.key)
}
if (newIndex === undefined) { // 如果索引不存在则直接删除老节点
unmount(prevChild, parentComponent, parentSuspense, true)
}
1
2
3
4
5
6
7
2
3
4
5
6
7
for (j = s2; j <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j] as VNode)
) {
newIndex = j
break
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
如果老节点无key，则会找到对应新节点看类型是否相同，如果类型相同则进行patch
newIndexToOldIndexMap[newIndex - s2] = i + 1
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
patch(
prevChild,
c2[newIndex] as VNode,
container,
null,
parentComponent,
parentSuspense,
isSVG,
optimized
)
patched++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
标记已经patched过的元素，用于标记最长稳定序列,并且标记元素是否需要移动,最终值为0的则意味着元素没有被patch过
5.3 移动和挂载
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap) // 获取最长稳定序列
: EMPTY_ARR
j = increasingNewIndexSequence.length - 1
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) { // 如果为0 说明是新增元素
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG
)
} else if (moved) {
if (j < 0 || i !== increasingNewIndexSequence[j]) {
// 需要移动
move(nextChild, container, anchor, MoveType.REORDER)
} else {
j-- // 元素不需要移动
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
根据之前计算出来的数组，来确定最长增长稳定序列（不需要做移动的节点），循环新节点如果值为0则说明需要新增元素，否则查看节点是否需要移动
