Please elaborate the diff algorithm of Vue

Forensic medicine 2021-05-04 15:45:15
elaborate diff algorithm vue


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 _updata, 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 
}
 Copy 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
}
 Copy code 

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>
 Copy code 

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

image.png

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

image.png

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>
 Copy code 
  • 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 :
  1. Complete all the real dom The minimization of
  2. Let the nodes of the new tree correspond to the appropriate real dom

image.png

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

image.png

example : Two virtual nodes div Are they the same?

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

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>
 Copy code 

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

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

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

image.png

patch Function first compares the root node

If two nodes :

  • 「 identical 」, Get into 「 to update 」 technological process
  1. 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
  2. Compare the properties of the new and old nodes , There are changes in the update to the real dom in
  3. At present, the new and old nodes are processed , Start 「 Compare child nodes 」
  • No 「 identical 」
  1. New node recursive , 「 New element 」
  2. 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 :

 Unnamed drawing .png

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 :

  1. 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

 Unnamed drawing .png

  1. 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

 Unnamed drawing .png

  1. 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 :

 Unnamed drawing .png

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 :

 Unnamed drawing .png

  1. 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 :

 Unnamed drawing .png

  1. 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 :

 Unnamed drawing .png

  1. 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 :

 Unnamed drawing .png

  1. 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

 Unnamed drawing .png

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

 Unnamed drawing .png

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 .
 Copy code 

Okay , That's what I share , Everyone for diff Algorithm There are other understandings that can be discussed in the comments section ~

I hope you like it Give me a hand ~ , I'll be more motivated

版权声明
本文为[Forensic medicine]所创,转载请带上原文链接,感谢
https://qdmana.com/2021/05/20210504154431370y.html

  1. Two way linked list: I'm no longer one-way driving
  2. Vue event and form processing
  3. Reactive TraderCloud实时外汇开源交易平台
  4. Reactive tradercloud real time foreign exchange open source trading platform
  5. Node.js REST API的10个最佳实践
  6. Ten best practices of node.js rest API
  7. Fiddler advanced usage
  8. Process from Vue template to render
  9. Promise up (asynchronous or synchronous)
  10. Principle and implementation of promise
  11. Vs code plug in sharing - run code
  12. Vue practical notes (1) introduction of Ant Design
  13. Vue actual combat notes (2) introduction of element plus
  14. Introduction to webpack
  15. Webpack construction process
  16. Vue notes
  17. The experience and lessons of moving from ruby megalith architecture to go microservice
  18. Using leancloud to add artitalk module to hexo blog
  19. Implementation of chrome request filtering extension
  20. Detailed introduction of beer import declaration elements and label quarantine [import knowledge]
  21. Gallop workflow engine design series 01 process element design
  22. VUE移动端音乐APP学习【十六】:播放器歌词显示开发
  23. Vue Mobile Music App learning [16]: player lyrics display development
  24. jquery cookie
  25. jquery cookie
  26. 体面编码之JavaScript
  27. JavaScript for decent coding
  28. React17 系统精讲 结合TS打造旅游电商平台
  29. React17 system combined with TS to build tourism e-commerce platform
  30. 2021-05-04 hot news
  31. HttpSession对象与Cooike的关系 以及 Cookie对象构造函数问题
  32. gRPC-Web:替代REST的gRPC的Javascript库包
  33. The relationship between httpsession object and cooike and the construction of cookie object
  34. Grpc Web: a JavaScript library package to replace rest grpc
  35. Building reactive rest API with Java - kalpa Senanayake
  36. PDF转HTML工具——用springboot包装pdf2htmlEX命令行工具
  37. Pdf to HTML tool -- Wrapping pdf2htmlex command line tool with springboot
  38. PDF转HTML工具——用springboot包装pdf2htmlEX命令行工具
  39. Pdf to HTML tool -- Wrapping pdf2htmlex command line tool with springboot
  40. Vue.js比jQuery更容易学习
  41. Node.js的Reactor模式 与异步编程
  42. Vue. JS is easier to learn than jQuery
  43. Reactor mode of node.js and asynchronous programming
  44. 详解JavaScript中的正则表达式
  45. Explain regular expressions in JavaScript
  46. 详解JavaScript中的正则表达式
  47. Explain regular expressions in JavaScript
  48. JS: closure
  49. Write your own promise in promises / A + specification
  50. Analysis of the core mechanism of webpack from loader, plugin to egg
  51. On the import and export of webpack
  52. Interpretation of lodash source code (2)
  53. Hexo series (5) writing articles
  54. 有人用过JMeter或用HttpUnit写过测试吗????
  55. Has anyone ever used JMeter or written tests in httpUnit????
  56. JavaScript异步编程4——Promise错误处理
  57. Leetcode 1846. Reduce and rearrange the largest element of an array
  58. JavaScript asynchronous programming 4 -- promise error handling
  59. SQLite是一种经典的无服务器Serverless
  60. 通过Spring Boot Webflux实现Reactor Kafka