Preface: With the release of the beta version of VUe3.0, the official version of VUe3.0 will come soon. Yu also talked about new features in vue3.0, such as strong typescript support, proxy response principle, virtual dom re-creation, and diff algorithm optimization. Xiaobian here carefully studied the vue3.0beta diff algorithm source code, and hope to share the details and secrets with you.
First of all, let’s consider some of the questions that are easy to ask in a large or medium-sized factory interview:
When is diff used and where is the scope of diff? 2. How does the Diff algorithm work and what does it do? 3 What is the use of key in a v-for loop list 4 Is it really useful to use index as key? What is the best way to use a key?
How do you answer these questions? I’m sure when you finish reading this article, these questions will be solved.
When do we use diff algorithm,diff algorithm scope?
1.1 Scope of diff algorithm
Introduction of patch concept
In the process of vUE Update, different patch methods will be used to patch new and old Vnodes in the process of traversing the child Vnodes. If the corresponding newVnode and oldVnode are found, the real DOM nodes in them can be reused. The performance overhead of repeatedly creating elements is avoided. After all, browsers create and manipulate the real DOM, and the performance costs are high.
In the patch process, if there are many Chidren in the current Vnode, it is necessary to traverse the new children Vnode and the old children Vnode in patch respectively.
The VNode type of Chidren exists
First think about what type of VNode children exist.
① Element The element type is Vnode
In the first case, element vnode will have children Vode, and the three span tags are Chidren vnode
<div>
<span>Apple 🍎</span>
<span>Banana 🍌</span>
<span>Pears 🍐</span>
</div>
Copy the codeIn vue3.0 source code, patchElement is used to process vnodes of element type
② Flagment The fragment type is VNode
In Vue3.0, a fragment concept was introduced. What is a fragment, you may ask? If you create a Vue component, it can only have one root node.
<template>
<span>Apple 🍎</span>
<span>Banana 🍌</span>
<span>Pears 🍐</span>
</template>
Copy the codeThis may cause a warning because a Vue instance representing any Vue component needs to be bound to a single DOM element. The only way to create a component with multiple DOM nodes is to create a functional component without the underlying Vue instance.
Flagment appears with what looks like a normal DOM element, but it’s virtual and doesn’t appear in the DOM tree at all. This allows you to bind component functionality into a single element without creating an extra DOM node.
<Fragment>
<span>Apple 🍎</span>
<span>Banana 🍌</span>
<span>Pears 🍐</span>
</Fragment>
Copy the codeIn the vue3.0 source code, processFragment is used to process vnodes of Fragment type
1.2 patchChildren
From the above, we know the type of Vnode where children exist, so the existence of children requires patch traversal of each child Vnode in turn. Then we need a patchChildren method, and then patch subclass vnode.
patchChildren
Vue3.0 in the patchChildren method has such a section of source code
if (patchFlag > 0) {
if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
/* Diff algorithm for the presence of key */
patchKeyedChildren(
c1 as VNode[],
c2 as VNodeArrayChildren,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
optimized
)
return
} else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
/* If there is no key, patch */
patchUnkeyedChildren(
c1 as VNode[],
c2 as VNodeArrayChildren,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
optimized
)
return}}Copy the codePatchChildren performs real diff or direct patch according to whether there is a key.
Since the Diff algorithm exists in the patchChildren method, and the patchChildren method is used in vNodes of Fragment and Element types, this explains the scope of the Diff algorithm.
1.3 Function of DiFF algorithm?
As we know from the preface, the Vnode with such children needs to perform patch operations successively through the children traversal by patchChildren. If the vnode situation is found again during patch, it will be recursively patch down successively. It is important to find the vNode corresponding to the new vNode.
Let’s use two images to show vNode changes.
The above two figures show how the old and new DOM trees change during an update.
Assuming there is no DIFF algorithm, what will happen to patch in sequence
If there is no DIff algorithm, but direct PatchChildren, the logic shown in the following figure will appear.
For the first time patchChidren 
The second patchChidren 
The third patchChidren‘
The fourth patchChidren
If the DIff algorithm is not used, but the virtual DOM tree is patch in turn, then the above is slightly higherChanging the DOM order, there is no correct pair of new and old Vnodes in the patch process, so none of the old vnodes can be reused. In this way, new nodes need to be created again, which wastes the performance overhead, which is obviously not what we need.
And that’s where the Diff algorithm comes in.
Diff is used to find the old Vnode corresponding to the new Vnode in the process of patch sub-Vnode, reuse real DOM nodes, and avoid unnecessary performance overhead
What exactly does the diff algorithm do?
Before the formal introduction of diff algorithm, there is patchKeyedChildren patchUnkeyedChildren in the process of patchChildren
PatchKeyedChildren is the formal process of starting diff, so what is the role of patchUnkeyedChildren? Let’s see what patchUnkeyedChildren do if there’s no key.
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++) { /* Traverse the old and new Vnodes and patch */
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
patch(
c1[i],
nextChild,
container,
null,
parentComponent,
parentSuspense,
isSVG,
optimized
)
}
if (oldLength > newLength) { /* If the number of old vnodes is greater than the number of new vnodes, delete the redundant vnodes */
unmountChildren(c1, parentComponent, parentSuspense, true, commonLength)
} else { /* /* The number of old vnodes is smaller than the number of new vnodes, creating new vnodes is ah */
mountChildren(
c2,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
optimized,
commonLength
)
}
Copy the codeIt can be concluded that in the case of no key (1), the minimum value is obtained by comparing the length of old and new children, and then the new patch work is carried out for the public part. ② If the number of old nodes is greater than the number of new nodes, remove the extra nodes. ③ If the number of new nodes is greater than the number of old nodes, add new nodes to the new mountChildren.
What about the key case? We use the Diff algorithm, and what does the Diff algorithm do?
What does the patchKeyedChildren method actually do? Let’s start by looking at some declared variables.
/* c1 Old vnode c2 new vnode */
let i = 0 /* Record index */
const l2 = c2.length /* Number of new vNodes */
let e1 = c1.length - 1 /* Index of the last vnode */
let e2 = l2 - 1 /* Index of the last node in the new node */
Copy the codeThe first step is to start from the beginning to the end
(a b) c (a b) d e
/* * * * * * * * * * * * * * *
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
/* Determine whether key and type are equal */
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
parentAnchor,
parentComponent,
parentSuspense,
isSVG,
optimized
)
} else {
break
}
i++
}
Copy the codeThe first thing to do is to find the same vNode from scratch, then patch, if not the same node, then immediately break out of the loop.
The specific process is shown in the figure
isSameVNodeType
export function isSameVNodeType(n1: VNode, n2: VNode) :boolean {
return n1.type === n2.type && n1.key === n2.key
}
Copy the codeIsSameVNodeType is used to check whether the current vNode type and the key of the Vnode are equal
② The second step starts from the end with the former diff
a (b c) d e (b c)
/* If the first step does not complete the patch, immediately start the patch from the back to the front, and immediately break out of the loop */
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,
parentAnchor,
parentComponent,
parentSuspense,
isSVG,
optimized
)
} else {
break
}
e1--
e2--
}
Copy the codeAfter the first step, if it is found that the patch is not finished, the second step is immediately carried out, traversing from the tail and diff forward in turn.
If it is not the same node, break out of the loop immediately.
The specific process is shown in the figure
③ and ④ mainly for the new and delete elements, the premise is that the element has not moved, if there is an element to move to go ⑤ logic.
③ If the old node is not patched but the new node is not patched, create a new Vnode
(a b) (a b) c i = 2, e1 = 1, e2 = 2 (a b) c (a b) i = 0, e1 = -1, e2 = 0
/* If the number of new nodes is greater than the number of old nodes, the remaining nodes will be processed as new vnodes (in this case, the same vnodes have been patched) */
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
while (i <= e2) {
patch( /* Create a new node */
null,
(c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i])),
container,
anchor,
parentComponent,
parentSuspense,
isSVG
)
i++
}
}
}
Copy the codei > e1
If the number of new nodes is greater than the number of old nodes, all the remaining nodes will be treated as new VNodes (this case indicates that the same Vnodes have been patched), that is, all new Vnodes will be created.
The specific logic is shown in the figure
(4) If all the new nodes are patched and the old nodes are left, uninstall all the old nodes
i > e2
(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++
}
}
Copy the codeIf the old node is larger than the new node, all the excess nodes are unloaded (this situation indicates that the same Vnode has been patched).
The specific logic is shown in the figure
(5) Uncertain elements (this situation indicates that no patch finished the same vNode), we can follow the logic of ①② to continue to see
The diff core
The nodes that are not traversed in cases ① and ② are shown in the figure below.
The remaining nodes.
const s1 = i // The first step is to iterate over the index
const s2 = i
const keyToNewIndexMap: Map<string | number, number> = new Map(a)/* Save the new vnode node in map */
for (i = s2; i <= e2; i++) {
if(nextChild.key ! =null) {
keyToNewIndexMap.set(nextChild.key, i)
}
}
let j
let patched = 0
const toBePatched = e2 - s2 + 1 /* Number of new nodes that did not pass path */
let moved = false /* Prove whether */
let maxNewIndexSoFar = 0
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
/* Create an array with each child element being 0 [0, 0, 0, 0, 0, 0, 0, 0, 0,] */
Copy the codeGo through all the new nodes and store the index and corresponding key into map keyToNewIndexMap
KeyToNewIndexMap Map of key -> index
D : 2 E : 3 C : 4 I : 5
Next, declare a new pointer j that records the index of the remaining new nodes. Patched, records the number of new nodes in step ⑤ toBePatched the number of new nodes that have not been patched before step ⑤. Moved represents whether a move has occurred. Our demo has already moved.
NewIndexToOldIndexMap is used to hold an array of new and old node indexes. The index of the newIndexToOldIndexMap array is the index of the new VNode and the value is the index of the old VNode.
The following
for (i = s1; i <= e1; i++) { /* Start iterating over the old node */
const prevChild = c1[i]
if (patched >= toBePatched) { /* The number of patches has been greater than or equal to */
/* if the number of new toBePatched is 0, uninstall the old nodes */
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
let newIndex
/* if the key of the old node exists, find the corresponding index */ by using the key
if(prevChild.key ! =null) {
newIndex = keyToNewIndexMap.get(prevChild.key)
} else { /* if the key of the old node does not exist */
for (j = s2; j <= e2; j++) { /* Iterates over all the remaining new nodes */
if (
newIndexToOldIndexMap[j - s2] === 0 && /* newIndexToOldIndexMap[j-s2] === 0 The new node has not been patched */
isSameVNodeType(prevChild, c2[j] as VNode)
) { /* If a new node is found, assign the index of the new node to newIndex */
newIndex = j
break}}}if (newIndex === undefined) { /* no new node corresponding to the old node is found, delete the current node and uninstall all nodes */
unmount(prevChild, parentComponent, parentSuspense, true)}else {
/* insert the index of the old node into the array where the new node is stored */
newIndexToOldIndexMap[newIndex - s2] = i + 1
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
/* Prove that a node has been moved */
moved = true
}
/* Find a new node to patch nodes */
patch(
prevChild,
c2[newIndex] as VNode,
container,
null,
parentComponent,
parentSuspense,
isSVG,
optimized
)
patched++
}
}
Copy the codeThis code is the heart of diff’s algorithm.
Step 1: Find the index of the corresponding new node through the key of the old node: Start traversing the old node to determine whether there is a key. If there is a key, find the index of the new node through the keyToNewIndexMap of the new node. If there is no key, traverse the remaining new nodes to try to find the corresponding index.
Step 2: If the index proves that there is a corresponding old node, then the old node is directly reused for patch. If no new node corresponding to the old node is found, the current old node is deleted.
Step 3: newIndexToOldIndexMap finds the relationship between the old and new nodes.
Here, we patch all the old Vnodes.
As is shown in
But here’s the problem.
1 Although all the old nodes have been patched. You can figure out how to actually move a DOM element for a node that has already been moved. 2. For the newly added node (node I in the figure), it is not processed. How to deal with it?
/* Move the old node to create a new node */
/* Move the corresponding node according to the longest stable sequence */
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
j = increasingNewIndexSequence.length - 1
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) { /* Create a new vnode */ if there is no old node corresponding to the new one
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG
)
} else if (moved) {
if (j < 0|| i ! == increasingNewIndexSequence[j]) {/* if there is no long */
/* VNode to be moved */
move(nextChild, container, anchor, MoveType.REORDER)
} else {
j--
}
Copy the code⑥ Longest stable sequence
It is preferred to obtain a longest stable sequence through getSequence. In the case of index === 0, that is, the new node (I in the figure) needs to be newly mounted to a new Vnode, and then unified movement operation is performed on the moved nodes
What is the longest stable sequence
For the following original sequence 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, the longest increasing subsequence is 0, 2, 6, 9, 11, 15.
Why do you want the longest stable sequence
Because we need a sequence as the base reference sequence, other nodes that are not in the stable sequence, to move.
conclusion
After the above, we know roughly the process of diff algorithm
1 Compare the node patch from the beginning and find the same node patch. If the node patch is different, jump out immediately.
2. If the first step does not finish the patch, immediately start the patch from the back to the front. If the difference is found, immediately break out of the loop.
3 If the number of new nodes is greater than the number of old nodes, the remaining nodes are treated as new vNodes (in this case, the same Vnodes have been patched).
4 If the number of old nodes is larger than the number of new nodes, uninstall all the excess nodes (this situation indicates that the same VNodes have been patched).
5 Uncertain elements (this situation indicates that no vNode has the same patch) are antithetical to 3 and 4.
1 Set up an array newIndexToOldIndexMap using the map patched patched with the number of new vNodes that have not been compared toBePatched with the number of new vNodes that have not been compared. Each child element is a number in [0, 0, 0, 0, 0, 0, 0,] that records the index of the old node, and the array index is the index of the new node
Start traversing the old node
① If the number of new nodes is 0 in toBePatched, uninstall the old nodes.
② If the key of the old node exists, use the key to find the corresponding index
(3) If the key of the old node does not exist, 1 iterate over all the remaining new nodes. 2 If the new node corresponding to the current old node is found, then assign the index of the new node to newIndex
④ No new node corresponding to the old node is found. Uninstall the current old node.
(5) If the new node corresponding to the old node is found, record the index of the old node in the array storing the new node. (1) If the node moves, the record has moved. (2) Patch The old and new nodes find the new node to carry out patch node traversal
If you move
(1) Find the longest stable sequence according to the index list of new and old nodes of newIndexToOldIndexMap. (2) For newIndexToOldIndexMap -item =0, it is proved that there is no old node, and a new vnode is formed. (3) Move the nodes that have been moved.Copy the codeThe functions of the three keys and how to correct the key.
1 the key role
In the above diFF algorithm, the isSameVNodeType method is used to judge whether the key is equal to the old and new nodes. So what can we conclude from this?
In the V-for loop, the function of key is to judge whether the key of newVnode and OldVnode is equal, so as to reuse the old node corresponding to the new node and save the performance cost.
2 How to Use a Key correctly
Error 1: Use index as key.
Using index as a key is the same as using diff. Why? Here’s a picture to illustrate:
As shown in the figure, when we use index as the key, no matter how we move and delete the node, the diff algorithm will patch from beginning to end (in the figure, all nodes are not effectively reused).
Error 2: Use index to concatenate other values as key.
When the index is used to concatenate other values as the index, each node cannot find the corresponding key. As a result, all nodes cannot be reused and all new Vnodes need to be created again. They all need to be re-created
This is shown here.
(3) Correct usage: use the unique value ID as the key(we can use the id of the data source interacting with the front and back ends as the key).
This is shown here. Each node is reused. The diff algorithm really works.
Four summarizes
Here we are, having solved all the problems we started with, and finally reorganizing the whole process with a mental map. Diff algorithm, did you get it?
Wechat scan code to follow the public account, regularly share technical articles
