Explain the diff algorithm of vue in detail
1. How does vue update nodes when data changes?
You should know that rendering a real dom costs a lot. For example, sometimes when we modify some data, if we directly render it to the real dom, it will cause the redrawing and rearrangement of the whole dom tree. Is it possible that we only update the modified dom instead of the whole dom? diff algorithm can help us.
First, we generate a virtual DOM according to the real dom. When the data of a node in the virtual DOM changes, a new Vnode will be generated. Then, we compare Vnode with oldVnode. If we find any differences, we will directly modify it on the real DOM, and then make the value of oldVnode Vnode vnode.
diff calls a function called patch to compare the old and new nodes and patch the real DOM while comparing them.
2. What is the difference between virtual Dom and real DOM?
virtual DOM extracts the real DOM data and simulates the tree structure in the form of objects. For example, DOM is like this:
<div>
<p>
123
</p>
</div>
Corresponding virtual DOM (pseudo code):
var Vnode = {
tag: 'div',
children:[
{ tag:'p',text:'123' }
]
}
Warm tip: VNode and oldVNode are both objects. You must remember.
3.diff comparison method?
When diff algorithm is used to compare old and new nodes, the comparison will only be carried out at the same level, not cross level.
<div>
<p>
123
</p>
</div>
<div>
<span>456</span>
</div>
The above code will separate two divs in the same layer and p and span in the second layer, but will not compare div and span. One seen elsewhere
diff flow chart
When the data changes, the set method will call Dep.notify to notify all subscribers of the Watcher, and the subscribers will call patch to patch the real DOM and update the corresponding view.
make a concrete analysis
patch
Let's see how patch is patched (the code only keeps the core part)
function patch(oldVnode,vnode){
// some code
if(sameVnode(oldVnode,vnode)){
patchVnode(oldVnode,vnode)
}else{
const oEl = oldVnode.el // The real element node corresponding to the current oldVnode
let parentEle = api.parenNode(oEl) // Parent element
cerateEle(vnode) // Generate new elements based on Vnode
if(parenEle !== null){
api.insertBefore(parentEle,vnode.el,api.nextSibling(oEl)) // Add new element to parent element
api.removeChild(parentEle,oldVnode.el) // Remove previous old element nodes
oldVnode = null
}
}
// some code
return vnode
}
The patch function receives two parameters oldVnode and Vnode, representing the new node and the previous old node respectively
- Judge whether the two nodes are worth comparing. If they are worth comparing, execute patchVnode
function sameVnode(a,b) {
return (
a.key === b.key && // key value
a.tag === b.tag && // Tag name
a.isComment === b.isComment && // Is it a comment node
// Whether data is defined. Data contains some specific information, such as onclick and style
isDef(a.data) === isDef(b.data) &&
sameInputType(a,b) // When the tag is < input >, the type must be the same
)
}
- If it is not worth comparing, replace oldVnode with Vnode
If both nodes are the same, drill down to their child nodes. If the two nodes are different, it means that Vnode has been completely changed, and oldVnode can be directly replaced.
Although the two nodes are different, what if their child nodes are the same? Don't forget, diff is compared layer by layer. If the first layer is different, we won't continue to compare the second layer in depth. (I wonder if this is a disadvantage? The same child nodes cannot be reused...)
patchVnode
When we determine that the two nodes are worth comparing, we will point out the patchVnode method for the two nodes. So what does this method do?
patchVnode (oldVnode, vnode) {
const el = vnode.el = oldVnode.el
let i, oldCh = oldVnode.children, ch = vnode.children
if (oldVnode === vnode) return
if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {
api.setTextContent(el, vnode.text)
}else {
updateEle(el, vnode, oldVnode)
if (oldCh && ch && oldCh !== ch) {
updateChildren(el, oldCh, ch)
}else if (ch){
createEle(vnode) //create el's children dom
}else if (oldCh){
api.removeChildren(el)
}
}
}
updateChildren
There is a large amount of code, which is inconvenient to explain line by line, so the following is described in combination with some example diagrams.
updateChildren (parentElm, oldCh, newCh) {
let oldStartIdx = 0, 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]
let oldKeyToIdx
let idxInOld
let elmToMove
let before
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVnode == null) { // For vnode The comparison of key will set oldVnode = null
oldStartVnode = oldCh[++oldStartIdx]
}else if (oldEndVnode == null) {
oldEndVnode = oldCh[--oldEndIdx]
}else if (newStartVnode == null) {
newStartVnode = newCh[++newStartIdx]
}else if (newEndVnode == null) {
newEndVnode = newCh[--newEndIdx]
}else if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
}else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
}else if (sameVnode(oldStartVnode, newEndVnode)) {
patchVnode(oldStartVnode, newEndVnode)
api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
}else if (sameVnode(oldEndVnode, newStartVnode)) {
patchVnode(oldEndVnode, newStartVnode)
api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
}else {
// Comparison when using key
if (oldKeyToIdx === undefined) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // index table generated with key
}
idxInOld = oldKeyToIdx[newStartVnode.key]
if (!idxInOld) {
api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
newStartVnode = newCh[++newStartIdx]
}
else {
elmToMove = oldCh[idxInOld]
if (elmToMove.sel !== newStartVnode.sel) {
api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
}else {
patchVnode(elmToMove, newStartVnode)
oldCh[idxInOld] = null
api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
}
newStartVnode = newCh[++newStartIdx]
}
}
}
if (oldStartIdx > oldEndIdx) {
before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
}else if (newStartIdx > newEndIdx) {
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
}
}
Let's talk about what this function does first
- Extract the child node Vch of Vnode and the child node oldCh of oldVnode
- oldCh and vCh have two head and tail variables StartIdx and EndIdx respectively. Their two variables are compared with each other, and there are four comparison methods in total. If none of the four comparisons match, if the key is set, the key will be used for comparison. During the comparison, the variable will lean towards the middle. Once StartIdx > EndIdx indicates that at least one of oldCh and vCh has been traversed, the comparison will be ended.
Graphic updateChildren
Finally came to this part. I believe many people are confused about the above summary. Let's talk about it. (I drew all these by myself. Please recommend easy-to-use drawing tools...)
.
The pink parts are oldCh and vCh
We take them out and point to their head child and tail child with s and e pointers, respectively
Now, compare oldS, oldE, S and E for sameVnode. There are four comparison methods. When two of them can match, the corresponding node in the real dom will move to the corresponding position of Vnode. This sentence is a little windy. For example
- If oldS and E match, the first node in the real dom will move to the last
- If oldE and S match, the last node in the real dom will move to the front, and the two pointers on the match will move to the middle
- If none of the four matches is successful, there are two cases
- If the old and new child nodes have keys, a hash table will be generated according to the oldChild'S keys, and the keys of S will be matched with the hash table. If the matching is successful, it will be judged whether S and the matching node are samenodes. If so, the successful node will be moved to the front in the real dom. Otherwise, the corresponding node generated by S will be inserted into the corresponding oldS position in the DOM, and the S pointer will move to the middle, The node in the matched old is set to null.
- If there is no key, directly insert the new node generated by S into the real DOM (ps: this can explain why the key needs to be set in v-for. If there is no key, only four matches will be made, even if there are reusable nodes in the pointer, they can not be reused)
Configure another graph (assuming that all nodes in the following figure have keys and the keys are their own values) 
- First step
oldS = a, oldE = d； S = a, E = b; Copy code
If oldS and S match, the a node in the dom will be placed first. If it is already the first node, it will not matter. At this time, the position of the dom is: a b d
- Step 2
oldS = b, oldE = d； S = c, E = b; Copy code
When oldS and E match, move the original node b to the last, because e is the last node, and their positions should be the same. This is what said above: when two of them can match, the corresponding nodes in the real dom will move to the corresponding positions of Vnode. At this time, the position of dom is: a d b
- Step 3
oldS = d, oldE = d； S = c, E = d; Copy code
oldE and E match, and the position remains unchanged. At this time, the position of dom is: a d b
- Step 4
oldS++; oldE--; oldS > oldE; Copy code
The traversal ends, indicating that oldCh traverses first. Insert the remaining vCh nodes into the real dom according to their own index. At this time, the dom position is: a c d b
One simulation is completed.
There are two conditions for the end of this matching process:
- Olds > olde means that oldCh is traversed first, and then the redundant vCh is added to the dom according to the index (as shown in the figure above)
- S > e means that vCh traverses first, then delete the redundant nodes with interval [oldS, oldE] in the real dom
Here's another example. You can try to simulate it yourself as above
When these nodes sameVnode successfully, patchVnode will be executed immediately. You can take a look at the above code
if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode)
}
Copy code
In this way, it recurses layer by layer until all child nodes in oldVnode and Vnode are compared. All the patches of dom have also been completed. Would it be much easier to look back at the code of updateChildren now?
summary
The above is the whole process of diff algorithm. Put a summary diagram sent at the beginning of the article. You can try to look at this diagram and recall the process of diff.
