vue3 数组子节点diff
站长
· 阅读数 48
快速diff五步
1. 从头部同步对比
const patchKeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
parentAnchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) => {
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1; // prev ending index
let e2 = c2.length - 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];
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
} else {
break;
}
i++;
}
}
记住四个变量：
i :当前对比的头部标记索引；l2：新数组子节点的长度；e2：新数组子节点尾部标记索引； e1：旧数组子节点尾部标记索引。
export function isSameVNodeType(n1: VNode, n2: VNode): boolean {
return n1.type === n2.type && n1.key === n2.key
}
可以看出，只要是n1和n2是相同节点，就会一直循环patch，i=2时，子节点不相等，开始进入下一步，从尾部开始对比
2. 从尾部同步对比
const patchKeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
parentAnchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) => {
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1; // prev ending index
let e2 = c2.length - 1; // next ending index
// 1. sync from start
// 2. sync from end
// a (b c)
// d e (b c)
while (i <= e1 && i <= e2) {
const n1 = c1[e1];
const n2 = c2[e2] ;
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
} else {
break;
}
e1--;
e2--;
}
}
从后往前比对，当b和c不是同一节点，就停止，此时e2=2,e1=1,i=2，接着下一步
3. 添加新节点
const patchKeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
parentAnchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) => {
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1; // prev ending index
let e2 = c2.length - 1; // next ending index
// 1. sync from start
// 2. sync from end
// 3. common sequence + mount
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++;
}
}
}
从图中，此时，i>e1,i<=e2，所以进入第三步，通过while循环，把多余的新节点全部添加到DOM
4. 删除旧节点
const patchKeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
parentAnchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) => {
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1; // prev ending index
let e2 = c2.length - 1; // next ending index
// 1. sync from start
// 2. sync from end
// 3. common sequence + mount
if (i > e1) {
//...
} else if (i > e2) { // 4. common sequence + unmount
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true);
i++;
}
}
多余节点情况如图所示，当从头部开始比对，当子节点c ≠ 子节点d，此时i = 2；然后接着从尾部对比，当子节点c ≠ 子节点b，此时e1=2,e2=1，i>e2,i<=e1,通过while循环，把多余的旧节点全部删除。
以上4步都是比较理想的子节点比对顺序，还有最复杂的一种是不明确的子节点顺序
5. 不知道子节点顺序，需要移动
像图中这种情况，i<e1,i<e2,走不到第3步和第4步的逻辑，那么就需要找到最多可以复用的节点，进行移动，然后该增加的增加，该删除的删除
5.1 建立新子节点 key->index 的映射关系
const patchKeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
parentAnchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) => {
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1; // prev ending index
let e2 = c2.length - 1; // next ending index
// 1. sync from start
// 2. sync from end
// 3. common sequence + mount
if (i > e1) {
//...
// 4. common sequence + unmount
} else if (i > e2) {
//...
// 5. unknown sequence
} else {
const s1 = i; // prev starting index
const s2 = i; // next starting index
// 5.1 build key:index map for newChildren
const keyToNewIndexMap = new Map();
for (i = s2; i <= e2; i++) {
const nextChild = c2[i];
if (nextChild.key != null) {
keyToNewIndexMap.set(nextChild.key, i);
}
}
}
keyToNewIndexMap就是新子节点中还未patch对比的那些子节点（从i到e2）的key和索引建立的映射
5.2 循环旧子节点:相同的patch，多余的remove
const patchKeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
parentAnchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) => {
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1; // prev ending index
let e2 = c2.length - 1; // next ending index
// 1. sync from start
// 2. sync from end
// 3. common sequence + mount
if (i > e1) {
//...
// 4. common sequence + unmount
} else if (i > e2) {
//...
// 5. unknown sequence
} else {
const s1 = i; // prev starting index
const s2 = i; // next starting index
// 5.1 build key:index map for newChildren
const keyToNewIndexMap = new Map();
// ...
// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
let patched = 0; //新子节点中已经patch更新过的数量
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
// 当前旧节点没有key，就只能遍历新子节点找它在新子节点中的索引
for (j = s2; j <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j])
) {
newIndex = j;
break;
}
}
}
if (newIndex === undefined) {
// 在新子节点中找不到这个旧节点，就删除
unmount(prevChild, parentComponent, parentSuspense, true);
} else {
// 更新新子节点中的元素在旧子节点中的索引
// newIndexToOldIndexMap的元素为0意味着旧节点中找不到可以复用的给新节点
newIndexToOldIndexMap[newIndex - s2] = i + 1;
if (newIndex >= maxNewIndexSoFar) {
//maxNewIndexSoFar 保存的是上次求值旧子节点的在新子节点中位置
//旧子节点是按顺序遍历的，旧：abc 新：deabc
//像这种旧节点在新节点中找到的也是递增的顺序
maxNewIndexSoFar = newIndex;
} else {
// 说明旧子节点在新子节点的位置不是递增了
// 旧：abcd 新:dabc
// 旧节点遍历到d，nexIndex就变成0，而maxNewIndexSoFar是3
// 这种情况就是需要移动节点了
moved = true;
}
// 遍历旧节点，找到可以复用的，和新子节点patch
patch(
prevChild,
c2[newIndex],
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
// 更新数量
patched++;
}
}
}
5.3 移动和新增
const patchKeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
parentAnchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) => {
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1; // prev ending index
let e2 = c2.length - 1; // next ending index
// 1. sync from start
// 2. sync from end
// 3. common sequence + mount
if (i > e1) {
//...
// 4. common sequence + unmount
} else if (i > e2) {
//...
// 5. unknown sequence // 需要进行移动操作
} else {
const s1 = i; // prev starting index
const s2 = i; // next starting index
// 5.1 build key:index map for newChildren
//...
// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
//...
// 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];
const anchor = nextIndex + 1 < l2 ? (c2[nextIndex + 1]).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
// 没有最长递增子序列（reverse 情况）
// 或者当前的节点索引不在最长递增子序列中，就要要移动
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, MoveType.REORDER);
} else {
j--;
}
}
}
}
};
总结
能移动的尽量移动，移动性能好过新增DOM，但是移动也最好是移动次数最少，那就需要求最长递增子序列来使移动次数最少。
key的重要性
如果没有key
下面这个例子没有v-for没有给key
<script setup>
import { ref } from '@vue/reactivity'
const lists = ref(['a', ' b', 'c', 'd'])
function changeList() {
lists.value.reverse()
}
</script>
<template>
<div class="App">
<div v-for="item in lists">{{ item }}</div>
<button @click="changeList">改变列表</button>
</div>
</template>
就会进入patchUnkeyedChildren
const patchUnkeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
anchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
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];
patch(
c1[i],
nextChild,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
);
}
if (oldLength > newLength) {
// remove old
unmountChildren(
c1,
parentComponent,
parentSuspense,
true,
false,
commonLength
);
} else {
// mount new
mountChildren(
c2,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized,
commonLength
);
}
};
可以看出，先求出新旧子节点最小的长度，然后循环，把新旧子节点按位置取出来进行patch，如果新子节点长度大于旧子节点，就挂载新子节点，否则移除旧子节点。
在上面这个例子中只是简单的文本变化，假如abcd都是比较复杂的组件，a和d就要进行patch,如果ad里面的属性、DOM结构差异很大，就会多出许多操作，极大浪费性能。
如果使用index作为key
看一个反转数组的例子
<script setup>
import { ref } from '@vue/reactivity'
const lists = ref(['a', ' b', 'c', 'd'])
function changeList() {
lists.value.reverse()
}
</script>
<template>
<div class="App">
<div v-for="(item, index) in lists" :key="index">{{ item }}</div>
<button @click="changeList">改变列表</button>
</div>
</template>
会进入patchKeyedChildren
可以看出，d和a的key一样都是0，会依次进行patch，不能找到正确的旧节点，跟上面没有key的效果一样。
如果是删除的情况：
<script setup>
import { ref } from '@vue/reactivity'
const lists = ref(['a', 'b', 'c', 'd'])
function changeList() {
lists.value.shift()
}
</script>
<template>
<div class="App">
<div v-for="(item, index) in lists" :key="index">{{ item }}</div>
<button @click="changeList">改变列表</button>
</div>
</template>
明明是删除了a，bcd可以复用，但结果是b-a,c-b,d-c进行patch，最后把旧节点多出来的d删除了，不能正确找到旧节点复用，也是相当于没有key
使用随机数作为key
<script setup>
import { ref } from '@vue/reactivity'
const lists = ref(['a', 'b', 'c', 'd'])
function changeList() {
lists.value.push('e')
}
</script>
<template>
<div class="App">
<div v-for="item in lists" :key="Math.random()">{{ item }}</div>
<button @click="changeList">改变列表</button>
</div>
</template>
这种情况是有key，但是key都对不上，这里就会走到上面diff步骤5.2，先把旧子节点全部删除，然后再走到diff5.3全部增加新子节点
对比vue2的diff
vue2双端diff： 新头和旧头； 新尾和旧尾；新尾和旧头；新头和旧尾；乱序情况
Vue3中头头、尾尾比较后，新的增加，多余旧的删除，没有头尾比较，Vue3第5步就是在对vue2的后3步做优化：基于最长递增子序列做最少的移动、新增、删除，vue2 diff的后面3步就是移动，新增，删除，
转载自:https://juejin.cn/post/7283151626785423420