This is the second day of my participation in the More text Challenge. For more details, see more text Challenge.
Recently just read the Vue source Diff algorithm, just in the more text challenge, did some GIFs and flow charts, illustrated to talk in detail, Vue Diff algorithm.
How does Vue2 update nodes
As we all know, Vue uses HTML-based template syntax that allows developers to declaratively bind the DOM to the data of the underlying Vue instance. When initialized, Vue converts the template syntax into the real DOM and renders it to the page.
<template>
<div>{{msg}}</div>
</template>
<script>
export.default {
data() {
return {
msg: 'HelloWorld'}}}</script>
Copy the codeBut when the data changes, how does Vue update the page?
If you choose to rerender the entire DOM, you will inevitably have to redraw and rearrange the entire DOM tree. In a real project, it is impossible to have only one
sentence. When our pages are very complex, and the changed data affects only a small part of the page data updates, it is definitely not advisable to re-render the page.
In this case, the easiest way is to find the DOM affected by the data change and update only that DOM. This is how Vue updates the page.
After initializing the page, Vue converts the current real DOM into a Virtual DOM and saves it, which is called oldVnode here. Then, when a certain data changes, Vue will create a new virtual DOM — vnode, and then compare vnode with oldVnode to find out what needs to be updated, and then directly modify the corresponding real DOM. When the modification is complete, the vnode is assigned to oldVnode and stored as a reference for the next update.
The difficulty in this update, which is what we are going to talk about today, is the comparison between new and old VNodes, which is often called Diff algorithm.
What is the virtual DOM
We mentioned the Virtual DOM earlier, but what is a Virtual DOM?
We may have printed the real DOM, which is essentially an object, but its elements are numerous, even if it’s a simple few lines of code.
Therefore, in the real DOM, we don’t dare to directly manipulate and change.
This is where the virtual DOM is born. It is also an object, but it is actually extracted from the real DOM data, in the form of an object to simulate the tree structure, to make it more concise and clear.
There is no fixed template for the virtual DOM, and implementations vary from framework to framework, but most of the structure is the same. Let’s use Vue’s virtual DOM as an example.
<div id="app">
<p class="text">HelloWorld</p>
</div>
Copy the codeThe above DOM generates the following virtual DOM (with deletion) through Vue. The object contains the tag, key value, text information and so on of the root node, and also contains the elm attribute to store the real DOM. At the same time, there is a children array to store child nodes, and the structure of child nodes is consistent.
{
"tag": "div"./ / label
"key": undefined, / / key values
"elm": div#app, / / true DOM
"text": undefined, // Text messages
"data": {attrs: {id:"app"}}, // Node properties
"children": [{ // Child attribute
"tag": "p"."key": undefined,
"elm": p.text,
"text": undefined,
"data": {attrs: {class: "text"}},
"children": [{
"tag": undefined,
"key": undefined,
"elm": text,
"text": "helloWorld"."data": undefined,
"children": []}]}Copy the codeWhen we extract some commonly used information, and use the form of object nesting to store the information of child nodes, thus forming a virtual DOM, when we use it for comparison, it will be much simpler than the two real DOM.
In Vue, there is a render function that returns VNode as a virtual DOM. Of course, you can also use virtual-Dom or snabbDOM to experience the virtual DOM.
The realization of the Diff
When using Diff algorithm to compare two nodes, the comparison will only be made at the same level, but not across levels.
process
In Vue, three main methods, patch(), patchVnode() and updateChildren(), are used to implement Diff.
- When we
VueThe page update function is triggered when the responsive data inupdateComponent()How can the trigger be triggered by readingVueSource code to learn or take a look at my previous articleSimple Handwriting for Vue2. X); - At this time
updateComponet()Is calledpatch()Method in which the comparison is made for the same node, and if so, executepatchVnode()Method, start to compare node differences; If it’s not the same node, then replace it, which we’ll talk about later; - in
patchVnode()First, update the node attributes, and then determine if there is a child node, if there is, then executeupdateChildren()Method, the child nodes are compared; If there is no child node, then the node text content judgment update; (Text nodes do not have child nodes) updateChildren()In, the two child node arrays passed in are compared one by one, and when the same node is found, the callpatchVnode()Continue the node difference comparison.
The preparatory work
In order to get a better look at the core code, let’s clear up some functions first.
IsDef and isUndef
In the source code will use isDef() and isUndef() to determine whether vnode exists, essentially is to determine whether vnode is undefined or null, after all, vnode virtual DOM is an object.
export function isUndef (v: any) :boolean %checks {
return v === undefined || v === null
}
export function isDef (v: any) :boolean %checks {
returnv ! = =undefined&& v ! = =null
}
Copy the codesameVnode
In the source code, the sameVnode() method is used to determine whether two nodes are the same. Essentially, it is to determine whether two nodes are the same by judging the static attributes such as key value, tag tag and so on.
Note that the same node does not mean equal nodes, such as
and
are the same node, but they are not equal. In the source code is through vnode1 === vnode2 to determine whether the node is equal.
// Compare the same nodes
function sameVnode(a, b) {
return (
a.key === b.key &&
a.asyncFactory === b.asyncFactory && (
(
a.tag === b.tag &&
a.isComment === b.isComment &&
isDef(a.data) === isDef(b.data) &&
sameInputType(a, b)
) || (
isTrue(a.isAsyncPlaceholder) &&
isUndef(b.asyncFactory.error)
)
)
)
}
function sameInputType(a, b) {
if(a.tag ! = ='input') return true
let i
const typeA = isDef(i = a.data) && isDef(i = i.attrs) && i.type
const typeB = isDef(i = b.data) && isDef(i = i.attrs) && i.type
return typeA === typeB || isTextInputType(typeA) && isTextInputType(typeB)
}
Copy the codepatch
Now it’s time to look at the source code to see how Vue implements the Diff algorithm.
All the following code is only the core code, to see the entire code can see the Vue source (patch file path: github.com/vuejs/vue/b…
First look at the patch() method, which receives the old and new virtual Dom, namely oldVnode, vNode. This function is actually a simple judgment of the old and new virtual Dom, but has not entered the detailed comparison stage.
- In the first place to judge
vnodeIf it does not exist, then the old node will be deleted. - if
vnodeIf there is, then judgeoldVnodeDoes it exist? If it does not exist, it only needs to add the wholevnodeNodes are fine; - if
vnodeandoldVnodeIf both are present, determine whether they are the same node, and if so, this callpatchVnodeMethod, the two nodes are compared and judged in detail. - If the two nodes are not the same, this is usually the initialization page, in which case
oldVnodeIt’s actually trueDomThis is only needed to bevnodeTranslate into realityDomAnd then replace itoldVnodeI won’t go into the details, it’s not within the scope of today’s discussion.
// __patch__ is called when updating
function patch(oldVnode, vnode, hydrating, removeOnly) {
// Check whether the new node exists
if (isUndef(vnode)) {
if (isDef(oldVnode)) invokeDestroyHook(oldVnode) // If the new node does not exist and the old node does exist, delete the node
return
}
// Check whether the old node exists
if (isUndef(oldVnode)) {
// If the old node does not exist and the new node exists, the new node is added
createElm(vnode, insertedVnodeQueue)
} else {
if (sameVnode(oldVnode, vnode)) {
// Compare the new node diff algorithm
patchVnode(oldVnode, vnode, insertedVnodeQueue, null.null, removeOnly)
} else {
// Initialize the page (oldVnode is a real DOM)
oldVnode = emptyNodeAt(oldVnode)
}
// Create a new node
createElm(
vnode,
insertedVnodeQueue,
oldElm._leaveCb ? null : parentElm,
nodeOps.nextSibling(oldElm)
)
}
}
return vnode.elm
}
Copy the code
patchVnode
In patchVnode(), new and old virtual Dom is also received, namely oldVnode and vNode. In this function, it is time to compare and update the two virtual Dom.
- First, judge the two virtuals
DomIs it congruent, that is, there is no change; If yes, terminate the function, otherwise continue; - Second, update the attributes of the node;
- Then judge
vnode.textWhether or not it exists, i.evnodeIs it a text node? If yes, just update the text of the node, otherwise, continue the comparison; - judge
vnodeandoldVnodeIs there a child node?- If both have children, execute
updateChildren()Method to compare and update the child node; - if
vnodeThere are child nodes whileoldVnodeIf not, add all child nodes directly and set the text attribute of the node to null. - if
oldVnodeThere are child nodes whilevnodeIf not, delete all child nodes. - If neither of them has a child node, then judge
oldVnode.textIs there any content? If there is, empty the content.
- If both have children, execute
// Compare two virtual DOM
function patchVnode(oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly) {
// If the two virtual DOM are the same, return directly without comparing
if (oldVnode === vnode) {
return
}
// Get the real DOM
const elm = vnode.elm = oldVnode.elm
// Get the children of the two comparison nodes
const oldCh = oldVnode.children
const ch = vnode.children
// Attribute update
if (isDef(data) && isPatchable(vnode)) {
for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
}
if (isUndef(vnode.text)) { // There is no text -> This is usually the case when there is a child node
if (isDef(oldCh) && isDef(ch)) { // Both new and old nodes have children -> Compare the children
if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) }else if (isDef(ch)) { // The new node has children, the old node has no children -> Add
if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ' ') // If the old node has text, set it to null
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
} else if (isDef(oldCh)) { // The old node has children, the new node has no children -> delete
removeVnodes(oldCh, 0, oldCh.length - 1)}else if (isDef(oldVnode.text)) { // The old node has text, the new node has no text -> Delete text
nodeOps.setTextContent(elm, ' ')}}else if(oldVnode.text ! == vnode.text) {// New and old nodes have different text -> update the text
nodeOps.setTextContent(elm, vnode.text)
}
}
Copy the code
updateChildren
Finally, let’s look at the updateChild method, which is also the hardest part to understand, so I’m going to take you through this step by step, write it by hand, and then look at the source code.
First, this method passes in three important parameters, namely parentElm, the real node of the parent level, which is convenient for direct node operation. OldCh is the child node of oldVnode; NewCh is the child node of Vnode.
OldCh and newCh are both arrays. The function of this method is to compare the two arrays one by one and find the same node. Then run patchVnode to compare and update the remaining nodes.
The easiest way to do this is to iterate over the two arrays, but the complexity of this approach is very large, the time complexity is O(NM), and in our real projects, the page structure is very large and complex, so this scheme is very performance consuming.
In Vue, the main implementation is implemented with four Pointers. The four Pointers start at the beginning and end of the two arrays. So let’s first initialize the necessary variables.
let oldStartIdx = 0; // oldCh the pointer to the left of the array
let oldStartVnode = oldCh[0]; // oldCh array pointer to the left of the corresponding node
let oldEndIdx = oldCh.length - 1; // oldCh Specifies the pointer position to the right of the array
let oldEndVnode = oldCh[oldEndIdx]; // oldCh specifies the node corresponding to the pointer to the right of the array
let newStartIdx = 0; // The pointer to the left of the newCh array
let newStartVnode = newCh[0]; // The node corresponding to the pointer to the left of the newCh array
let newEndIdx = newCh.length - 1; // The pointer to the right of the newCh array
let newEndVnode = newCh[newEndIdx]; // The node corresponding to the pointer to the right of the newCh array
Copy the code
However, these four Pointers don’t stay there forever, they are compared to each other, and if they are the same node, the corresponding two Pointers will move to the other side, until the two overlap, and the cycle is over.
Of course, see here, you will have a lot of questions, but first remember the question, will answer one by one. Let’s go ahead and write a loop.
while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// TODO
}
Copy the codeAnd then we started to compare.
First, oldStartVnode and newStartVnode are compared. If the comparison is the same, we can execute patchVnode statement and move oldStartIdx and newStartIdx.
while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if(sameVnode(oldStartVnode, newStartVnode)){ patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx); oldStartVnode = oldCh[++oldStartIdx]; newStartVnode = newCh[++newStartIdx]; }}Copy the codeIf oldStartVnode and newStartVnode do not match, then oldEndVnode and newEndVnode are compared.
while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if(sameVnode(oldStartVnode, newStartVnode)){
...
}else if(sameVnode(oldEndVnode, newEndVnode)){
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
}
}
Copy the codeBut if the two ends of the comparison and the two ends of the comparison are not the same node, then we start cross-comparing. First, oldStartVnode is compared to newEndVnode.
However, if the cross-comparison matches, you need to pay attention to one problem. In this case, you not only need to compare and update the content of the node, but also need to move the location of the node. Therefore, we can use insertBefore and nextSibling DOM operation methods to achieve this.
while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if(sameVnode(oldStartVnode, newStartVnode)){
...
}else if(sameVnode(oldEndVnode, newEndVnode)){
...
}else if(sameVnode(oldStartVnode, newEndVnode)){
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
// Move the oldStartVnode node to its corresponding position, that is, after oldEndVnode
nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
}
}
Copy the codeIf oldStartVnode and newEndVnode do not match, oldEndVnode and newStartVnode are compared.
while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if(sameVnode(oldStartVnode, newStartVnode)){
...
}else if(sameVnode(oldEndVnode, newEndVnode)){
...
}else if(sameVnode(oldStartVnode, newEndVnode)){
...
}else if(sameVnode(oldEndVnode, newStartVnode)){
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
// Move the oldEndVnode node to its corresponding position, that is, before the oldStartVnode node
nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
}
}
Copy the codeAt this point, if the four comparison methods can not match the same node, we can only use the violent solution to achieve, that is, for newStartVnode, we go through the remaining nodes in oldCh and match one by one.
In Vue, we know that the tag will have an attribute, the key value. In Dom at the same level, if the key has a value, it must be unique. If not set, it defaults to undefined. So we can start by matching keys.
We can create an oldCh key->index mapping table, we can create a function createKeyToOldIdx implementation, return the result with a variable oldKeyToIdx to store.
function createKeyToOldIdx(children, beginIdx, endIdx) {
let i, key
const map = {}
for (i = beginIdx; i <= endIdx; ++i) {
key = children[i].key
if (isDef(key)) map[key] = i
}
return map
}
Copy the codeOldKeyToIdx [newStartVNode.key] = oldKeyToIdx[newStartVNode.key] = oldKeyToIdx[newStartVNode.key] = oldKeyToIdx
However, if newStartVnode does not have a key value, then the only way to do this is to go through the remaining nodes in oldCh and match them one by one to get the index, which can also be wrapped as a function.
function findIdxInOld(node, oldCh, start, end) {
for (let i = start; i < end; i++) {
const c = oldCh[i]
if (isDef(c) && sameVnode(node, c)) return i
}
}
Copy the codeLet’s go back to the hand-written code at this point.
let oldKeyToIdx, idxInOld;
while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if(sameVnode(oldStartVnode, newStartVnode)){
...
}else if(sameVnode(oldEndVnode, newEndVnode)){
...
}else if(sameVnode(oldStartVnode, newEndVnode)){
...
}else if(sameVnode(oldEndVnode, newStartVnode)){
...
}else{
<{key: I}> <{key: I}>
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
// If newStartVnode has a key, match index; If there is no key value, iterate over the remaining old child nodes, one by one matching newStartVnode, and return index for the same node
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
}
}
Copy the codeOf course, it is possible that the idxInOld subscript is empty in this case, in which case the newStartVnode is a completely new node, and we only need to add the new node.
If idxInOld is not empty, we get the corresponding oldVnode and compare it with newStartVnode. If it is the same node, we call patchVnode() and set the corresponding oldVnode to undefined. If they match different nodes, then create a node directly.
Finally, move newStartIdx.
let oldKeyToIdx, idxInOld, vnodeToMove;
while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if(sameVnode(oldStartVnode, newStartVnode)){
...
}else if(sameVnode(oldEndVnode, newEndVnode)){
...
}else if(sameVnode(oldStartVnode, newEndVnode)){
...
}else if(sameVnode(oldEndVnode, newStartVnode)){
...
}else{
<{key: I}> <{key: I}>
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
// If newStartVnode has a key, match index; If there is no key value, iterate over the remaining old child nodes, one by one matching newStartVnode, and return index for the same node
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) {
// If index is not matched, a new node is created
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
} else {
// Get the corresponding old child node
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
// Since idxInOld is between oldStartIdx and oldEndIdx, we can only set it to undefined instead of moving two Pointers
oldCh[idxInOld] = undefined
nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
} else {
// Create a new node if the key is the same but the node is different
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
}
}
// Move the left hand pointer of the new node
newStartVnode = newCh[++newStartIdx]
}
}
Copy the code
The important point here is that if we match oldVnode, we need to set it to undefined, and when we move oldStartIdx and oldEndIdx, we need to skip if the corresponding vnode is undefined.
let oldKeyToIdx, idxInOld, vnodeToMove;
while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
// oldStartVnode moves right when oldStartVnode is undefined
oldStartVnode = oldCh[++oldStartIdx]
} else if (isUndef(oldEndVnode)) {
// When oldEndVnode is undefined, oldEndVnode moves left
oldEndVnode = oldCh[--oldEndIdx]
} else if(sameVnode(oldStartVnode, newStartVnode)){
...
}else if(sameVnode(oldEndVnode, newEndVnode)){
...
}else if(sameVnode(oldStartVnode, newEndVnode)){
...
}else if(sameVnode(oldEndVnode, newStartVnode)){
...
}else{... }}Copy the code
By this time, we had done almost everything, only the finishing touches were left.
If the pointer to oldCh overlaps and passes, and the pointer to newCh does not overlap; Or the other way around.
In this case, if oldCh has redundant Vnodes, we simply delete them; If newCh has redundant Vnodes, we just need to add them.
let oldKeyToIdx, idxInOld, vnodeToMove, refElm;
while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
...
} else if (isUndef(oldEndVnode)) {
...
} else if(sameVnode(oldStartVnode, newStartVnode)){
...
}else if(sameVnode(oldEndVnode, newEndVnode)){
...
}else if(sameVnode(oldStartVnode, newEndVnode)){
...
}else if(sameVnode(oldEndVnode, newStartVnode)){
...
}else{... }if (oldStartIdx > oldEndIdx) {
// When the left pointer of the old node has exceeded the right pointer, add the remaining child node
refElm = isUndef(newCh[newEndIdx + 1])?null : newCh[newEndIdx + 1].elm
addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
} else if (newStartIdx > newEndIdx) {
// Delete the remaining child nodes when the left pointer of the new node has exceeded the right pointer
removeVnodes(oldCh, oldStartIdx, oldEndIdx)
}
}
Copy the codeWe have completed the updateChildren() method. The overall code is as follows:
// Compare two groups of child nodes
function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
// Set the first and last four Pointers and corresponding nodes
let oldStartIdx = 0
let newStartIdx = 0
let oldEndIdx = oldCh.length - 1
let oldStartVnode = oldCh[0]
let oldEndVnode = oldCh[oldEndIdx]
let newEndIdx = newCh.length - 1
let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]
// Diff lookup is the required variable
let oldKeyToIdx, idxInOld, vnodeToMove, refElm
// Loop end condition: the first and last Pointers of the new and old nodes overlap
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
// oldStartVnode moves right when oldStartVnode is undefined
oldStartVnode = oldCh[++oldStartIdx]
} else if (isUndef(oldEndVnode)) {
// When oldEndVnode is undefined, oldEndVnode moves left
oldEndVnode = oldCh[--oldEndIdx]
} else if (sameVnode(oldStartVnode, newStartVnode)) {
// Compare nodes when oldStartVnode is the same as newStartVnode
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
// Update the two Pointers
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) {
// When oldEndVnode is the same as newEndVnode, compare nodes
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
// Update the two Pointers
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) {
// Compare nodes when oldStartVnode is the same as newEndVnode
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
// Move the oldStartVnode node to its corresponding position, that is, after oldEndVnode
nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
// Update the two Pointers
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldEndVnode, newStartVnode)) {
// Compare nodes when oldEndVnode is the same as newStartVnode
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
// Move the oldEndVnode node to its corresponding position, that is, before the oldStartVnode node
nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
// Update the two Pointers
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else { // Brute force uses key matching
<{key: I}> <{key: I}>
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
// If newStartVnode has a key, match index; If there is no key value, iterate over the remaining old child nodes, one by one matching newStartVnode, and return index for the same node
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) {
// If index is not matched, a new node is created
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
} else {
// Get the corresponding old child node
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
// Since idxInOld is between oldStartIdx and oldEndIdx, we can only set it to undefined instead of moving two Pointers
oldCh[idxInOld] = undefined
nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
} else {
// Create a new node if the key is the same but the node is different
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
}
}
// Move the left hand pointer of the new node
newStartVnode = newCh[++newStartIdx]
}
}
if (oldStartIdx > oldEndIdx) {
// When the left pointer of the old node has exceeded the right pointer, add the remaining child node
refElm = isUndef(newCh[newEndIdx + 1])?null : newCh[newEndIdx + 1].elm
addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
} else if (newStartIdx > newEndIdx) {
// Delete the remaining child nodes when the left pointer of the new node has exceeded the right pointer
removeVnodes(oldCh, oldStartIdx, oldEndIdx)
}
}
Copy the codeThe flow chart
Why use a key
As we can see from sameVnode() above, the first criterion we use when comparing two nodes is vnode.key; And when you use violence later, the first choice is to match by key, and what’s the benefit of that? Let’s answer this question with a simple example.
Suppose our new and old nodes are as follows:
<! -- old -->
<div>
<p>A</p>
<p>B</p>
<p>C</p>
</div>
<! -- new -->
<div>
<p>B</p>
<p>C</p>
<p>A</p>
</div>
Copy the codeIn the above example, we can see that
A
has been moved to the end.
But if we didn’t set the key, diff would require A lot of manipulation of the Dom, because when the key is undefined, each p tag is the same node, so diff would change the first A to B, change the second B to C, change the third C to A, I’ve manipulated the Dom three times.
However, if we add key values to each of them, diff only needs to operate the Dom once, that is, move the first node to the last node.
