patch中的双端比较快速算法
const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, namespace, slotScopeIds, optimized) => {
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1;
let e2 = l2 - 1;
while (i <= e1 && i <= e2) {
const n1 = c1[i];
const n2 = c2[i] = optimized ? cloneIfMounted(c2[i]) : normalizeVNode(c2[i]);
if (isSameVNodeType(n1, n2)) {
patch(n1, n2, container, null, parentComponent, parentSuspense, namespace, slotScopeIds, optimized);
} else {
break;
}
i++;
}
while (i <= e1 && i <= e2) {
const n1 = c1[e1];
const n2 = c2[e2] = optimized ? cloneIfMounted(c2[e2]) : normalizeVNode(c2[e2]);
if (isSameVNodeType(n1, n2)) {
patch(n1, n2, container, null, parentComponent, parentSuspense, namespace, slotScopeIds, optimized)
} else {
break;
}
e1--;
e2--;
}
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1;
const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor;
while (i <= e2) {
patch(null, c2[i] = optimized ? cloneIfMounted(c2[i]) : normalizeVNode(c2[i]), container, anchor, parentComponent, parentSuspense, namespace, slotScopeIds, optimized);
i++;
}
}
} else if (i > e2) {
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true);
i++;
}
} else {
const s1 = i;
const s2 = i;
const keyToNewIndexMap = new Map();
for (i = s2; i <= e2; i++) {
const nextChild = c2[i] = optimized ? cloneIfMounted(c2[i]) : normalizeVNode(c2[i]);
if (nextChild.key != null) {
keyToNewIndexMap.set(nextChild.key, i);
}
}
let j;
let patched = 0;
const toBePatched = e2 - s2 + 1;
let moved = false;
let maxNewIndexSoFar = 0;
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) {
unmount(prevChild, parentComponent, parentSuspense, true);
continue;
}
let newIndex;
if (prevChild.key != null) {
newIndex = keyToNewIndexMap.get(prevChild.key);
} else {
for (j = s2; j <= e2; j++) {
if (newIndexToOldIndexMap[j - s2] === 0 && isSameVNodeType(prevChild, c2[j])) {
newIndex = j;
break;
}
}
}
if (newIndex === void 0) {
unmount(prevChild, parentComponent, parentSuspense, true);
} else {
newIndexToOldIndexMap[newIndex - s2] = i + 1;
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex;
} else {
moved = true;
}
patch(prevChild, c2[newIndex], container, null, parentComponent, parentSuspense, namespace, slotScopeIds, optimized);
patched++;
}
}
const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : shared.EMPTY_ARR;
j = increasingNewIndexSequence.length - 1;
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i;
const nextChild = c2[nextIndex];
const anchorVNode = c2[nextIndex + 1];
const anchor = nextIndex + 1 < 12 ? (anchorVNode.el || anchorVNode.placeholder) : parentAnchor;
if (newIndexToOldIndexMap[i] === 0) {
patch(null, nextChild, container, anchor, parentComponent, parentSuspense, namespace, slotScopeIds, optimized)
} else if (moved) {
if (j < 0 || i !== increasingNewIndexSequence[j]) {
moved(nextChild, container, anchor, 2)
} 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
编辑 (opens new window)
上次更新: 2025/09/25, 09:41:26