Vue - diff algorithm - 前端知识

diff What is it? ？diff It's just comparing two trees ,render It'll make two trees , A new tree newVnode, An old tree oldVnode, Then the two trees are compared and updated to find the difference diff, Full name difference, stay vue Inside diff The algorithm is through patch Function to complete , So sometimes it's called patch Algorithm

diff Timing of occurrence

diff When did it happen ？ Of course, we can say that it happens when the data is updated diff, Because data updates will run render Function gets virtual dom Trees , Finally, the page is re rendered .

When a component is created , When the properties or data on which the component depends change , Will run a function ( In the following code updateComponent), This function does two things ：

function _render Create a new virtual dom Trees （vnode tree）
function _update, Pass in _render Generated virtual dom Root node of tree , Compare the old and new trees , Finally complete the real dom Update

The core code is as follows , It's different from the original code , But it's almost the same , It means ：

// vue Constructors function Vue(){ // ... Other code var updateComponent = () => { this._update(this._render()); } new Watcher(updateComponent); // ... Other code }

diff It happened in _update Function is running

Call... First in the code _render Function gets virtual dom The root node , Then incoming _update Function , Will be updateComponent Pass in Watcher in ,watcher Can listen to the process of function execution , Monitor what responsive data is used during function execution and collect dependencies , About watcher Take a look at my last article ： One article for you to understand vue2 The principle of response

_update What are functions doing ？

_update The function receives a vonde Parameters , This is it. new Generated virtual dom Trees , meanwhile ,_update Function through the _vnode attribute , Get used The virtual dom Trees ._update The function first gives the component _vnode Property reassignment , Let it point to the new tree

Simply code ：

function update(vnode){ //vnode New trees //this._vnode Old trees this._vnode = vnode }

If you only consider updating the virtual dom Trees , This step has been completed , But the ultimate goal is to update the page , So we need diff Compare the nodes of the tree , So you can save the old trees oldVnode For comparison

Simply code ：

<body> <div id="app"></div> <script src="./vue.js"></script> <script> const vm = new Vue({ el: "#app", }); function update(vnode) { //vnode New trees //this._vnode Old trees let oldVnode = vm._vnode; // Keep old trees this._vnode = vnode; // Update the new tree } </script> </body>

contrast oldVnode and vnode That's it , The purpose of comparison is to update the reality dom

Next , Can judge old trees oldVnode Whether there is ：

non-existent ： This is the first time to load a component , So through the internal patch function , Directly traverse the new tree , Generate real... For each node DOM, And then mount it to each node's elm Attribute

Simply code ：

<body> <div id="app"></div> <script src="./vue.js"></script> <script> const vm = new Vue({ el: "#app", }); console.log(vm); function update(vnode) { //vnode New trees //this._vnode Old trees let oldVnode = vm._vnode; // Keep old trees this._vnode = vnode; // Update the new tree // If the old tree oldVnode non-existent if(!oldVnode){ this.__patch__(vm.$el,vnode); } } </script> </body>

There is ： Note that the component has been rendered before , So through the internal patch function , Compare the old and new trees , So as to achieve the following two goals ：

Complete all the real dom The minimization of
Let the nodes of the new tree correspond to the appropriate real dom

patch Function comparison process

Explanation of terms

I'll see the following words later , They all mean the following

1.「 identical 」： It refers to the label type of two virtual nodes and key The values are the same , but input The elements also depend on type attribute . The term is in vue The source code is called sameVnode, It's a function , Used to determine whether two virtual nodes are the same node

example ： Two virtual nodes div Are they the same?

<div> Forensics </div> <div> Front end Hunter </div>

Label types are div,key It's not just about v-for Ergodic , It can also be used in any label , The top two div There is no key value , So all for undefined, So label types and key It's the same value , It doesn't matter if the content is the same , It's another node ： Text node

<div key="fayi"> Forensics </div> <div key="qdls"> Front end Hunter </div>

The above two virtual nodes are different , because key Values are different

<input type="text"> <input type="radio">

The above two virtual nodes are different , because input It's not just about key Value and label type , Also look at type Are they the same?

2.「 New element 」： According to the information provided by a virtual node , Create a reality dom Elements , At the same time mount to the virtual node elm Attribute

3.「 Destroy element 」： Refer to ：vnode.elm.remove()

4.「 to update 」： It refers to comparing and updating two virtual nodes , It only happens on two virtual nodes 「 identical 」 Under the circumstances . The specific process will be described later .

5.「 Compare child nodes 」： It refers to comparing the children of two virtual nodes , The specific process will be described later

Detailed process

Root node comparison

patch Function first compares the root node

If two nodes ：

「 identical 」, Get into 「 to update 」 technological process

Put the old node's real dom Assign to a new node ：newVnode.elm = oldVnode.elem, Old nodes will be recycled by garbage collection mechanism
Compare the properties of the new and old nodes , There are changes in the update to the real dom in
At present, the new and old nodes are processed , Start 「 Compare child nodes 」

No 「 identical 」

New node recursive , 「 New element 」
Old node 「 Destroy element 」

Compare child nodes

fictitious dom The tree has finished , It's just the real thing dom 了 , But it's true dom It's time-consuming ,vue Our principle is to not change if we can , Try not to do anything , stay 「 Compare child nodes 」 when ,vue The starting point of everything , Is for the ：

Try not to do anything
No words , Try to change only element attributes
If not yet , Try to move elements as much as possible , Instead of deleting and creating elements
If it doesn't work , Delete and create elements

Compare the process ：

caption ：

Yellow circle ： Represents the same node type corresponding to the old and new child nodes
Numbers ： Express key value , It is used to distinguish whether it is the same node or not
Blue Square ： It means to compare the old child node with the real one dom
arrow ： Represents the head pointer and tail pointer respectively

Next , All we have to do is compare Old child nodes and New child nodes Between differences , The goal is to change real dom, And the new virtual child node is mapped to the real dom Go inside ,vue Use two pointers to the head and tail of the new and old child tree

step ：

First compare the new tree with the old tree's head pointer , See if the two nodes are the same , As you can see from the picture, it's the same , If it's the same, go to 「 to update 」 technological process ： First of all, the old node's real dom Assign to a new node （ real dom Connect to the new child node ）, Then compare the properties of the old and new nodes in a loop , See if there's anything different , Update the changed to the real dom in , Finally, depth first （ The nodes of a tree come to an end , Take another node ） Recursively loop whether these two new and old child nodes still have child nodes , If there is , The same is true , Let's assume that it doesn't have children . Gray indicates that the processing has been completed , And then the two heads move back

Next , Continue to compare the two head pointers , See if the two nodes are the same , Obviously , The two nodes are different , because key Values are different , Unlike when it doesn't destroy delete from build , Take a shock , detachment ！ As mentioned earlier, try not to operate dom, It's bound to find the same node , One way to the dark , Then it compares the tail pointer , You can see that the tail pointer is the same , It's the same as the first step ： A meal operation as fierce as a tiger , First of all, the old node's real dom Assign to a new node （ real dom Connect to the new child node ）, Then compare the properties of the old and new nodes in a loop , Update the changed to the real dom in , Next, we need to recursively cycle whether these two new and old child nodes still have child nodes , The last two tail hands move forward

Then continue to compare the head pointer , It's obviously different , The tail pointer ？ Are not the same as , because key The value is still different . Then it compares the head pointer with the tail pointer , See if it's the same , You can see the circle of the old node 2 Head pointer and new node circle 2 The tail pointer is the same , So the operation is the same as the first two steps , again A meal operation as fierce as a tiger , The results are as follows ：

What we should pay attention to here is the truth dom It must correspond to the new virtual child node one by one , So in addition to updating and changing places, we have to carry out Position shifting , Move to the back of the old tree tail pointer , Finally, the old tree head pointer moves back , At the end of the new tree, the pointer moves forward , Here's the picture ：

Continue comparison , The old and new head pointers are different , The tail pointer is different , The two are different , Then it will base on the new tree head pointer , Loop the old virtual child node , Look at the new tree circle 3 Whether it exists in the old virtual child node , Where does it exist , Find it and reuse it , attachment , Where there are changes, update to the real dom, The operation is the same as the previous steps , real dom It's going to be... Too Position shifting , Move to the old tree head pointer . Then the new tree head pointer continues to move back to the circle 9 Location , Here's the picture :

Continue comparison , The old and new head pointers are different , The tail pointer is different , But the new tree head pointer is the same as the old tree tail pointer , The operation is the same as the previous steps , But it still needs to move , Move to the old tree head pointer . Then the new tree head pointer moves back , Coincides with the new tree tail pointer , The old tree tail pointer moves forward to the circle 1 Location , Here's the picture ：

Continue comparison , The old and new tree heads have different pointers , The tail pointer is different , The two are different , Then it uses the new tree head pointer as a benchmark , Loop the old virtual child node , Find a circle 8 Does it exist in old trees , As you can see from the diagram , There is no such thing as , At this time, there is really no way , Can only 「 New element 」. Then the new tree head pointer continues to move backward to the circle 2 Location , Pictured ：

When the head pointer moves to the circle 2 When in position , The head pointer is no longer valid , When the head pointer exceeds the tail pointer , The loop ends , From the process, we can see that the new tree completes the loop first , But the old tree still has nodes left , This means that the remaining nodes in the old tree should be deleted , The corresponding reality dom It will also be removed

It's true in the end dom Generation completed , We only created one new element in the whole process , Here's the picture ：

During the interview, I will also be asked about diff The problem of algorithm , Here is the reference answer ：

When components are created and updated ,vue Will perform internal update function , This function uses render Function generated virtual dom Trees , Compare the old and new trees , Find the difference , Finally updated to the real dom

The process of comparing differences is called diff,vue Inside, through a system called patch Function to complete the process

In contrast ,vue Depth first 、 Compare by peer comparison . Peer comparison means that it doesn't compare across structures

When judging whether two nodes are the same ,vue It's through virtual nodes key and tag To judge

say concretely , First, compare the root nodes , If it's the same, the old node is associated with the real dom To the new node , Then update the attributes to the real world as needed dom, Then compare the array of child nodes ; If it's not the same , All real nodes are created recursively according to the information of the new node dom, At the same time, it is linked to the corresponding virtual node , Then remove the old dom.

When comparing its array of child nodes ,vue Two pointers are used for each child node array , Point to the head and the tail respectively , And then keep moving closer to the middle to compare , The goal is to reuse reality as much as possible dom, As little as possible to destroy and create real dom. If you find the same , Then enter the same comparison process as the root node , If you find something different , Then move real dom To the right place .

So it goes on recursively , Until the whole tree does the contrast .