At present, most of the analysis of Vue3 is about double-pointer comparison and the generation of the longest incremental subsequence, but the combination with the source code is relatively small. This article tries to do some analysis combined with the source code to help you deepen your understanding of the vue diff algorithm. At the same time, other articles seem to have less conceptual analysis of Vue 3 “blocks”, and this article also makes some explanations. The most difficult part of the diff algorithm is case 5 (5. unknown sequence, see the code below), this article does not describe this algorithm in detail, but more about how Vue decides to call these algorithms Yes, if you want to know about this aspect, you can read other articles (Talk about the core diff algorithm of vue2 and vue3 – Nuggets (juejin.cn)), they explain this aspect in more detail.
Whether it is vue2 or vue3, the time complexity of the diff algorithm is O(n), because it flattens the component structure instead of traversing the tree-based structure (thanks to the compilation phase Template analysis, which is also not possible with react). The most difficult thing for the diff algorithm to deal with is the case where both old and new nodes are arrays.
The key rendering function is patchElement, and its location in the vue source code is: vuejs.core\packages\runtime-core\src\renderer.ts（github.com/vuejs/ core)… The other functions mentioned below are basically in this file.
Component updates (blocks) for stable structures
For optimization, for a stable structure (excluding v-if, v-for), Vue will call the patchBlockChildren function to compare the old and new VNodes one by one. (For what is a stable structure, you can see the description on the official website of vue: rendering mechanism | Vue.js (vuejs.org)). dynamicChildren, only components with a stable structure have this attribute, so if this attribute exists, vue will call the patchBlockChildren function for update processing.
if (dynamicChildren) {<!-- -->
// The Block block is a stable structure, that is, it does not include v-if v-for, and can be compared element by element
patchBlockChildren(
/** */
)
/** */
} else if (!optimized) {<!-- -->
// full diff
patchChildren(
/** */
)
}
The patchBlockChildren function looks like this:
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 */ Here is to get the external container DOM of VNode,
// If the new node is to be replaced directly, it needs to be mounted under it
// decide how to update the dom
patch(
oldVNode,
newVNode,
container,
null,
parentComponent,
parent Suspense,
isSVG,
slotScopeIds,
true
)
}
Structure is not a stable way to update components
Then the next step is how to deal with structurally unstable components, that is, if there is v-if or v-for, then the old and new child nodes may Inconsistent, there may be new child nodes, old nodes may be removed, of course, they may be consistent, and the knowledge content has changed. The most common case is that we use v-for to render arrays.
At this time, the algorithms such as double-pointer comparison and finding the longest increasing subsequence come into play. The patchChildren function internally judges whether the subcomponent has the key attribute, if there is a key attribute in the subcomponent (not all of them need to be included) , the patchKeyedChildren function will be called, otherwise the patchUnkeyedChildren function will be called (patchFlag is used here to determine whether a comparison is required, and for components defined by component templates, patchFlag is generated during the compilation phase , which marks the dynamic properties of the component, if it is 0, it does not contain dynamic properties, and there is no need to compare):
patchFlag indicates what content needs to be updated, and shapeFlag indicates the node type;
// c1 and c2 are sub-arrays, compare the sub-arrays
const c1 = n1 & & n1.children
const prevShapeFlag = n1 ? n1. shapeFlag : 0
const c2 = n2.children
const {<!-- --> patchFlag, shapeFlag } = n2
if (patchFlag > 0) {<!-- -->
// Compare only if there is a patch tag
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
}
}
Write it down to appreciate the double pointer comparison and longest increasing subsequence algorithm (inside the patchKeyedChildren function) that everyone talks about:
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
// Call the path algorithm from the head, patch one by one for the old and new stages of the same type, until there is no match
while (i <= e1 & amp; & amp; 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)
// Same as above, synchronous tail
while (i <= e1 & amp; & amp; 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--
}
// In the third case, mount a new node
// i is the inconsistent position of the head, e1 is the inconsistent subscript at the end of the old node array, and e2 is the inconsistent subscript at the end of the new node array
// 3. common sequence + mount
// Two matching situations, the new array has new nodes to 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 old node has reached the end
// i <= e2 and new nodes exist, add new nodes
if (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
while (i <= e2) {
patch(
null, // no old node exists
(c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i])),
container,
/** */
)
i + +
}
}
}
// 4. common sequence + unmount
// In the fourth case, uninstall the old node
// (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) {
// The new node has been traversed, there are still old nodes left, uninstall the old node
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i + +
}
}
/** After that, the situation is more complicated. The old child nodes and the new child nodes have not been traversed.
* Consider how best to reuse old nodes
*/
// 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
// space for time, resume index table
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__ & amp; & amp; 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 & amp; remove nodes that are no longer present
// Match old and new nodes and unload old nodes that don't exist
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 & amp; & amp;
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
// Generate the longest increasing subsequence (let the least elements need to be 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,
parent Suspense,
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--
}
}
}
}
Follow-up processing
Back to the patchElement function, we have already called patchChildren or patchBlockChildren to update the stable or unstable sub-array. But what we have done is update the children, so what about the component itself? So after updating the child nodes, go back to the component itself, update props, css, perform side effects, etc.
This is also consistent with the execution process of the vue component update – the parent node first triggers the update -> then the child node triggers the update -> the child node completes the update -> the parent node completes the update.
When the child node is updated, the responsive parameters such as the props of the parent node have changed (it is the update caused by the change of the parent node’s responsive data). If the parent node completes the update first, the child node may affect the state of the parent node. Therefore, the child node needs to complete the update, and finally the update is completed on the parent node (that is, the dom content update).