# vue diff算法
var oldCh = [1, 2, 3, 4] // 老元素
var newCh = [4, 2, 3, 1, 5, 6] // 新元素
var oldStartIdx = 0; // 老开始
var newStartIdx = 0; // 新开始
var oldEndIdx = oldCh.length - 1; // 老结束
var newEndIdx = newCh.length - 1; // 新结束
var oldStartVnode = oldCh[0]; // 老第一个元素
var newStartVnode = newCh[0]; // 新第一个元素
var oldEndVnode = oldCh[oldEndIdx]; // 老结束元素
var newEndVnode = newCh[newEndIdx]; // 新结束元素
var oldKeyToIdx, idxInOld, vnodeToMove, refElm;
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
// 如果旧首已经是undefined 说明已经被移动了
oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
} else if (isUndef(oldEndVnode)) {
// 如果旧尾已经是undefined 说明已经被移动了
oldEndVnode = oldCh[--oldEndIdx];
} else if (sameVnode(oldStartVnode, newStartVnode)) { // 旧首 和 新首 相同
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
// 如果旧首和新首相同，新老节点的【开始索引】都 加 1
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
} else if (sameVnode(oldEndVnode, newEndVnode)) { // 旧尾 和 新尾
//如果旧尾和新尾一样， 新老节点的【结束索引】都 减 1
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right 旧首 和 新尾
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);
// 将旧首移动到 最后面
// 如果旧首和新尾相同
// 旧节点的【开始索引加 1】 新节点的【结束索引】减 1
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm));
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left 旧尾 和 新首
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
// 将 旧尾 移动到 最前面
// 如果旧尾 和 新首相同
// 新节点的【开始索引加 1】 旧节点的【结束索引】减 1
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
} else {
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
// 把老的vnode的 数组的下标和key做一对一映射 {key: index}
// key是节点绑定的key，index是该key对应的元素的下标
// 用新首的key在 老vnode中寻找一个key相等的，看是否可以找到
idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
// 如果没找到就说明这是新的元素，需要新建
if (isUndef(idxInOld)) { // New element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
} else {
vnodeToMove = oldCh[idxInOld];
// 找到了相同的key，判断是不是一样的元素，如果是一样的元素就进行patchVnode
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
oldCh[idxInOld] = undefined;
// 把在旧Vnode中找到的与新Vnode相同key的元素移到旧Vnode的第一个
canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);
} else {
// 虽然key一样但是不是相同的标签，所有也需要进行新建元素
// same key but different element. treat as new element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
}
}
// 新首 进行下一个元素对比
newStartVnode = newCh[++newStartIdx];
}
}
if (oldStartIdx > oldEndIdx) {
// oldCh 先遍历完成,则证明 newCh 还有多余节点，需要新增这些节点
refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;
addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
} else if (newStartIdx > newEndIdx) {
// newCh 先遍历完成,则证明 oldCh 还有多余节点，需要删除这些节点
removeVnodes(oldCh, oldStartIdx, oldEndIdx);
}
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
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
# debug调试记录
<script src="./vue.js"></script>
<div id="app"><div v-for="item in list" :key="item">{{item}}</div></div>
<script>
var vm = new Vue({
el:'#app',
data() {
return {
list:['111', '222','333','555']
}
},
mounted() {
setTimeout(() => {
this.list = ['111', '444','222','333','666']
})
},
})
</script>
<pre>
<code>
旧数据 ['111', '222','333','555']
新数据 ['111', '444','222','333','666']
<div id="app"><div v-for="item in list" :key="item">{{item}}</div></div>
</code>
第一次diff
['111', '222','333','555']
['111', '444','222','333','666']
var oldStartIdx = 0;
var newStartIdx = 0;
var oldEndIdx = 3
var newEndIdx = 4
var oldKeyToIdx, idxInOld, vnodeToMove, refElm
新首 的key是 111 ，旧首的key是 111
sameVode() = true
经过diff后发现什么都没变。所以进行复用
oldStartIdx ++
newStartIdx++
第二次 diff
var oldStartIdx = 1;
var newStartIdx = 1;
var oldEndIdx = 3
var newEndIdx = 4
['111', '222','333','555']
['111', '444','222','333','666']
新首 的key是 444 旧首的key是 222
所以执行
if (isUndef(oldKeyToIdx)) { oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx); }
执行完毕后
oldKeyToIdx = {
"222": 1,
"333": 2,
"555": 3
}
newStartVnode.key 此时是 '444'
idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
idxInOld = undefined
因为 444未找到，所以新建
if (isUndef(idxInOld)) { // New element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
}
newStartIdx ++
第三次diff
var oldStartIdx = 1;
var newStartIdx = 2;
var oldEndIdx = 3
var newEndIdx = 4
oldKeyToIdx = {
"222": 1,
"333": 2,
"555": 3
}
idxInOld, vnodeToMove, refElm 都是 undefined
['111', '222','333','555']
['111', '444','222','333','666']
此时 新首的key '222' 旧首的key也是 '222'
sameVode() = true
经过diff后发现什么都没变。所以进行复用
oldStartIdx++
newStartIdx++
第四次diff
var oldStartIdx = 2;
var newStartIdx = 3;
var oldEndIdx = 3
var newEndIdx = 4
oldKeyToIdx = {
"222": 1,
"333": 2,
"555": 3
}
idxInOld, vnodeToMove, refElm 都是 undefined
['111', '222','333','555']
['111', '444','222','333','666']
此时 新首的key '333' 旧首的key也是 '333'
sameVode() = true
经过diff后发现什么都没变。所以进行复用
oldStartIdx++
newStartIdx++
第五次diff
var oldStartIdx = 3;
var newStartIdx = 4;
var oldEndIdx = 3
var newEndIdx = 4
oldKeyToIdx = {
"222": 1,
"333": 2,
"555": 3
}
['111', '222','333','555']
['111', '444','222','333','666']
idxInOld, vnodeToMove, refElm 都是 undefined
此时 新首的key '666' 旧首的key是 '555'
if (isUndef(idxInOld)) { // New element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
}
newStartIdx ++
第六次diff
var oldStartIdx = 3;
var newStartIdx = 5;
var oldEndIdx = 3
var newEndIdx = 4
oldKeyToIdx = {
"222": 1,
"333": 2,
"555": 3
}
['111', '222','333','555']
['111', '444','222','333','666']
idxInOld, vnodeToMove, refElm 都是 undefined
此时 由于 newStartIdx > newEndIdx ，所以执行
else if (newStartIdx > newEndIdx) {
把剩余的旧元素都进行删除操作
removeVnodes(oldCh, oldStartIdx, oldEndIdx);
}
</pre>
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
# debug调试记录2
<script src="./vue.js"></script>
<div id="app"><div v-for="item in list" :key="item">{{item}}</div></div>
<script>
var vm = new Vue({
el:'#app',
data() {
return {
list:['111', '222','333','555']
}
},
mounted() {
setTimeout(() => {
this.list = ['111', '444','333','222','666']
})
},
})
</script>
<pre>
<code>
旧数据 ['111', '222','333','555']
新数据 ['111', '444','333','222','666']
<div v-for="item in list" :key="item">{{item}}</div>
</code>
第一次diff
['111', '222','333','555']
['111', '444','333','222','666']
{
"oldStartIdx":0,
"newStartIdx":0,
"oldEndIdx":3,
"newEndIdx":4,
"oldStartVnode":"111",
"newStartVnode":"111",
"oldEndVnode":"555",
"newEndVnode":"666"
}
新首 的key是 111 ，旧首的key是 111
sameVode() = true
经过diff后发现什么都没变。所以进行复用
oldStartIdx ++
newStartIdx++
第二次 diff
{
"oldStartIdx":1,
"newStartIdx":1,
"oldEndIdx":3,
"newEndIdx":4,
"oldStartVnode":"222",
"newStartVnode":"444",
"oldEndVnode":"555",
"newEndVnode":"666"
}
['111', '222','333','555']
['111', '444','333','222','666']
新首 的key是 444 旧首的key是 222
所以执行
if (isUndef(oldKeyToIdx)) { oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx); }
执行完毕后
oldKeyToIdx = {
"222": 1,
"333": 2,
"555": 3
}
newStartVnode.key 此时是 '444'
idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
idxInOld = undefined
因为 444未找到，所以新建
if (isUndef(idxInOld)) { // New element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
}
newStartIdx ++
第三次diff
{
"oldStartIdx":1,
"newStartIdx":2,
"oldEndIdx":3,
"newEndIdx":4,
"oldStartVnode":"222",
"newStartVnode":"333",
"oldEndVnode":"555",
"newEndVnode":"666",
"oldKeyToIdx":{
"222":1,
"333":2,
"555":3
}
}
['111', '222','333','555']
['111', '444','333','222','666']
vnodeToMove = oldCh[idxInOld];
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
oldCh[idxInOld] = undefined;
canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);
}
newStartIdx++
第四次diff
{
"oldStartIdx":1,
"newStartIdx":3,
"oldEndIdx":3,
"newEndIdx":4,
"oldStartVnode":"222",
"newStartVnode":"222",
"oldEndVnode":"555",
"newEndVnode":"666",
"oldKeyToIdx":{
"222":1,
"333":2,
"555":3
},
"idxInOld":2,
"vnodeToMove":"333"
}
['111', '222',undefined,'555']
['111', '444','333','222','666']
sameVode() = true
经过diff后发现什么都没变。所以进行复用
oldStartIdx ++
newStartIdx ++
第5次diff
{
"oldStartIdx":2,
"newStartIdx":4,
"oldEndIdx":3,
"newEndIdx":4,
"newStartVnode":"666",
"oldEndVnode":"555",
"newEndVnode":"666",
"oldKeyToIdx":{
"222":1,
"333":2,
"555":3
},
"idxInOld":2,
"vnodeToMove":"333"
}
['111', '222',undefined,'555']
['111', '444','333','222','666']
oldStartVnode 已经被移动了，
if (isUndef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
}
第6次diff
{
"oldStartIdx":3,
"newStartIdx":4,
"oldEndIdx":3,
"newEndIdx":4,
"oldStartVnode":"555",
"newStartVnode":"666",
"oldEndVnode":"555",
"newEndVnode":"666",
"oldKeyToIdx":{
"222":1,
"333":2,
"555":3
},
"idxInOld":2,
"vnodeToMove":"333"
}
idxInOld = undefined
['111', '222',undefined,'555']
['111', '444','333','222','666']
if (isUndef(idxInOld)) { // New element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
}
newStartIdx > newEndIdx所以跳出循环执行删除操作
if (oldStartIdx > oldEndIdx) {
refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;
addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
} else if (newStartIdx > newEndIdx) {
removeVnodes(oldCh, oldStartIdx, oldEndIdx);
}
</pre>
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224