vue3中的diff算法分析
站长
· 阅读数 44
无论是vue2还是vue3，diff算法的时间复杂度都是O(n)，因为它会将组件结构打平，而不是基于树的结构进行遍历（得益于编译阶段的模板分析，这也是react不能实现的）。diff算法最难处理的是新旧节点都是数组的情况。
关键渲染函数为patchElement，在vue源码中的位置为：vuejs.core\packages\runtime-core\src\renderer.ts（github.com/vuejs/core）… 下文提到的其他函数基本上也在这个文件里。
稳定结构的组件更新（区块）
为了进行优化，对于稳定的结构（不含v-if，v-for），vue会调用patchBlockChildren函数，逐个对新旧VNode进行对比。（关于什么是稳定结构，可以看vue官网的描述：渲染机制 | Vue.js (vuejs.org)）。dynamicChildren，只有结构是稳定的组件才有该属性，因此如果存在这个属性的话，vue就调用patchBlockChildren函数进行更新处理。
if (dynamicChildren) {
// Block 块是一个稳定结构，即不包括v-if v-for，可以进行逐个元素的对比
patchBlockChildren(
/** */
)
/** */
} else if (!optimized) {
// full diff
patchChildren(
/** */
)
}
patchBlockChildren函数内部是这样的：
for (let i = 0; i < newChildren.length; i++) {
const oldVNode = oldChildren[i]
const newVNode = newChildren[i]
// Determine the container (parent element) for the patch.
const container = / ** xxx */ 这里是要获取VNode的外部容器DOM，
// 如果新节点是要直接替换的话，需要挂载到它下面
// 决定如何更新dom
patch(
oldVNode,
newVNode,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
true
)
}
结构不是稳定的组件的更新方式
那么接下来就是如何处理结构不稳定的组件，即存在v-if或v-for，这时新旧子节点就可能不一致了，可能会有新子节点，可能旧节点被移除，当然也可能一致，知识内容变了。最常见的情况就是我们使用v-for对数组进行渲染。
这个时候就是双指针比较、求最长递增子序列这些算法发挥作用的情况了。patchChildren函数内部会判断子组件是否是带有key属性的，如果子组件中存在key属性（不需要全部带有），就会调用patchKeyedChildren函数，否则调用patchUnkeyedChildren函数（这里用patchFlag进行判断是否需要进行比较，对于组件模板定义的组件，patchFlag是在编译阶段生成的，它标记了组件有哪些动态属性，如果为0的话就是不包含动态属性，也就不需要比较）：
patchFlag表示有什么内容需要更新，shapeFlag表示节点类型；
// c1 和 c2是子数组，对子数组进行比较
const c1 = n1 && n1.children
const prevShapeFlag = n1 ? n1.shapeFlag : 0
const c2 = n2.children
const { patchFlag, shapeFlag } = n2
if (patchFlag > 0) {
// 只有在存在patch标记的情况下，才进行比较
if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
patchKeyedChildren(
c1 as VNode[],
c2 as VNodeArrayChildren,
container,
/** */
)
return
} else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
// unkeyed
patchUnkeyedChildren(
c1 as VNode[],
c2 as VNodeArrayChildren,
container,
/** */
)
return
}
}
写下来欣赏一下被大家津津乐道的双指针比较和最长递增子序列算法(patchKeyedChildren函数内部)：
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
// 从头部开始调用path算法，对于相同类型的新旧阶段逐个patch，直到不匹配
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,
/** */
)
} 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,
/** */
)
} else {
break
}
e1--
e2--
}
// 第三种情况，挂载新节点
// i是头部不一致的位置，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) {
// i > e1 旧节点已经到头了
// i <= e2 还有新节点存在，把新节点添加上去
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,
/** */
)
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
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,
/** */
)
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--
}
}
}
}
后续处理
回到patchElement函数，此时我们已经调用完成了patchChildren或patchBlockChildren对稳定或非稳定子数组进行了更新。但是我们完成的是对children的更新，那么组件自身呢？因此更新完子节点后，回到组件自身，对props、css进行更新，执行副作用等。
这也是和vue组件更新的执行过程是一致的——父节点先触发更新-->然后子节点触发更新-->子节点完成更新-->父节点完成更新。
子节点更新时，父节点的props等响应式参数已经发生变化了（本来就是父节点响应式数据变化引起的更新），如果先父节点完成更新，子节点可能又会影响父节点的状态。因此需要子节点完成更新，最后再在父节点上完成更新（即dom内容更新）。
转载自:https://juejin.cn/post/7209192211975864376