Vue - diff algorithm

Souleigh 2021-06-17 21:52:18
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 :
  1. Complete all the real dom The minimization of

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

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

  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

  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 :

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 :

  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 :

  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 :

  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 :

  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

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 .

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

  1. HTML + CSS + JavaScript to achieve cool Fireworks (cloud like particle text 3D opening)
  2. HTML + CSS + JavaScript realizes 520 advertising love tree (including music), which is necessary for programmers to express themselves
  3. Solve the problem of Web front-end deployment server (it can be deployed online without a server)
  4. HTML + CSS + JS make wedding countdown web page template (520 / Tanabata Valentine's Day / programmer advertisement)
  5. What else can driverless minibus do besides "Park connection"?
  6. Cloud native leads the era of all cloud development
  7. NRM mirror source management tool
  8. Bring it to you, flex Jiugong
  9. Lolstyle UI component development practice (II) -- button group component
  10. Deconstruction assignment in ES6
  11. Luo 2 peerless Tang clan was officially launched. The official gave a key point, and the broadcast time was implied
  12. 20初识前端HTML(1)
  13. 当新零售遇上 Serverless
  14. 20 initial knowledge of front-end HTML (1)
  15. When new retail meets serverless
  16. [golang] - go into go language lesson 5 type conversion
  17. [golang] - go into go language lesson 6 conditional expression
  18. HTML5(八)——SVG 之 path 详解
  19. HTML5 (8) -- detailed explanation of SVG path
  20. 需要开通VIP以后页面内容才能复制怎么办?控制台禁用javascript即可
  21. Web前端|CSS入门教程(超详细的CSS使用讲解,适合前端初学者)
  22. 实践积累 —— 用Vue3简单写一个单行横向滚动组件
  23. Serverless 全能选手,再下一城
  24. What if you need to open a VIP to copy the page content? Just disable JavaScript on the console
  25. Web front end | CSS introductory tutorial (super detailed CSS explanation, suitable for front-end beginners)
  26. Practice accumulation - write a single line horizontal scroll component simply with vue3
  27. Dili Reba is thin again. She looks elegant and high in a strapless hollow skirt, and her "palm waist" is beautiful to a new height
  28. Serverless all-round player, next city
  29. The difference between MySQL semi synchronous replication and lossless semi synchronous replication
  30. Vue表单设计器的终极解决方案
  31. The ultimate solution for Vue form designer
  32. Nginx从理论到实践超详细笔记
  33. Yu Shuxin's red backless swimsuit is split to the waist and tail, with a concave convex figure and excessive color matching, and his face is white to dazzling
  34. Nginx ultra detailed notes from theory to practice
  35. 【动画消消乐|CSS】086.炫酷水波浪Loading过渡动画
  36. typecho全站启用https
  37. CCTV has another popular employee. The off-site interpretation is very professional, and the appearance ability is no less than that of Wang Bingbing
  38. [animation Xiaole | CSS] 086. Cool water wave loading transition animation
  39. Enable HTTPS in Typecho
  40. 50天用JavaScript完成50个web项目,我学到了什么?
  41. 根据JavaScript中原生的XMLHttpRequest实现jQuery的Ajax
  42. What have I learned from completing 50 web projects with JavaScript in 50 days?
  43. "My neighbor doesn't grow up" has hit the whole network. There are countless horse music circles, and actor Zhou Xiaochuan has successfully made a circle
  44. 根据JavaScript中原生的XMLHttpRequest实现jQuery的Ajax
  45. Implement the Ajax of jQuery according to the native XMLHttpRequest in JavaScript
  46. Implement the Ajax of jQuery according to the native XMLHttpRequest in JavaScript
  47. 30 + women still wear less T-shirts and jeans. If they wear them like stars, they will lose weight
  48. 数栈技术分享前端篇:TS,看你哪里逃~
  49. Several stack technology sharing front end: TS, see where you escape~
  50. 舍弃Kong和Nginx,Apache APISIX 在趣链科技 BaaS 平台的落地实践
  51. Abandon the landing practice of Kong and nginx, Apache apisik on the baas platform of fun chain technology
  52. 浪迹天涯king教你用elementui做复杂的表格,去处理报表数据(合并表头,合并表体行和列)
  53. 前端HTML两万字图文大总结,快来看看你会多少!【️熬夜整理&建议收藏️】
  54. Wandering around the world king teaches you to use elementui to make complex tables and process report data (merge header, merge table body rows and columns)
  55. 路由刷新数据丢失 - vuex数据读取的问题
  56. Front end HTML 20000 word graphic summary, come and see how much you can【 Stay up late to sort out & suggestions]
  57. Route refresh data loss - vuex data reading problem
  58. Systemctl系统启动Nginx服务脚本
  59. Systemctl system startup nginx service script
  60. sleepless