Because to learn Vue source code, its DIff algorithm is around but a knowledge point. In the learning process, I have learned about the library Snabbdom, which should be improved by Vue, so I can better understand the DIff algorithm of Vue
Snabbdom
The famous virtual DOM library is the ancestor of diff algorithm
What is the Diff algorithm
The diff algorithm is used to calculate the changed parts of the Virtual Dom. Because the Vue React framework only uses state changes to automatically update views, it calculates the smallest changes when data changes, rather than re-rendering the entire page, to save performance.
Diff effect display
Description: The page content is originally rendered with five elements in the array [A, B, C, D, E]. When the button is clicked, the data changes to [Q, A, B, C, D, E], and the page elements change accordingly with minimal changes. How to judge the minimum change in usage. Since the smallest change, that the same A, B, C, D, E node is certainly didn’t do any processing, if we put these nodes after initialization page rendering, through the console change for any content, click the button after the content of these nodes without any processing, we can know the nodes to be skipped the diff processing, didn’t do any processing, It is concluded that when the data changes, the page also adopts the minimum performance update operation.
Tips: If you don’t care about performance, of course you can wipe it all out and re-render it with new data.
The effect is shown below.
What is the virtual DOM
Use JS objects to describe the DOM hierarchy. All properties in the DOM have corresponding properties in the virtual DOM.
See Diff’s strength above, then why add a noun: virtual DOM. Because it involves a comparison algorithm between old and new nodes. For the sake of performance, the real DOM can not be directly compared, so it needs to be converted to the virtual DOM. The virtual DOM is basically a JS object, but it describes the structure of DOM elements according to certain rules, so it is called the virtual DOM. Its structure is roughly similar to the following.
The page elements are as follows
<div id="app">
<p class="text">hello world!!!</p>
</div>
Copy the codeThis is what happens when you convert to the virtual DOM
{
tag: 'div'.props: {
id: 'app'
},
chidren: [{tag: 'p'.props: {
className: 'text'
},
chidren: [].text: 'hello world!!! '}}]Copy the codeI read some articles, the structure is similar, but the details are different. Don’t worry, if you write the diff algorithm yourself, the corresponding rules for changing the real DOM into the virtual DOM can be customized.
Analysis of the
-
How is the virtual DOM generated by the render function (h function)
The h function is used to generate virtual nodes (vNodes)
-
Call h like this
-
h("li", {key:'A'.class: { class: 'mine'}},"A") Copy the code -
You get a virtual node like this
-
The corresponding real DOM node looks like this:
<li class="mine">A</li> Copy the code -
What are the properties of a virtual node
{ children: undefined./ / item data: {}, / / properties, and so on elm: undefined.// The corresponding real DOM node key: undefined.// Unique key attribute sel: div, Sign / / table text: 'I'm an empty box' // Internal text content } Copy the code
-
-
Principle of Diff algorithm
- Core function patch
- It takes two arguments: the first argument can be an element selected by the old virtual node or element selector, and the second argument is the new virtual node
- When the first parameter is the element selected by the element selector, render the page directly by processing the virtual node of the second parameter
- If the first parameter is a virtual node, you need to compare it with the second virtual node parameter to process different node processing logic
-
How does the virtual DOM diff into the real DOM
In fact, the return of the virtual DOM to the real DOM is covered in the diff algorithm
Code implementation
H function implementation
Morphological analysis:
Simple processing, there are three forms (there is a parameter length judgment processing in the source code, here is simply three parameters)
- Form (1) :
Js h("div", {}," text ") - Form (2) :
js h("div", {} , []) - Form (3) :
js h("div", {} , h())
Code implementation
// First there is a function that returns a virtual node object based on the parameters received, as follows
function vNode(sel, data, children, text, elm){
return {
sel,
data,
children,
text,
elm,
key: data.key
}
}
// The low version of the h function must accept three arguments
function h(sel,data,c){
// Check the number of parameters
if(arguments.length ! = =3) {throw new Error('Parameters must be three')}// Check the type of c
if(typeof c === "string" || typeof c === "number") {// In the form 1, call vNode directly to return the result
return vNode(sel, data, undefined,c,undefined)}else if(Array.isArray(c)){
2 / / form
let children = []
for (let index = 0; index < c.length; index++) {
const element = c[index]; // call h again, return the result
// Element must be an object
if(typeofelement ! = ="object" && element.hasOwnProperty('sel')) {throw new Error("One of the array arguments passed in is not an H function.")}// There is no need to execute element because h is already executed when hasOwnProperty is called and element is a virtual node
children.push(element)
}
return vNode(sel, data, children, undefined.undefined)}else if(typeof c === "object" && c.hasOwnProperty('sel')) {/ / 3
C has already called h when hasOwnProperty is called above, and returns a virtual node
let children = c
return vNode(sel, data,children,undefined.undefined)}else {
throw new Error("Parameter format error")}}Copy the codeImplementation of patch function
tips
You can see from the initial DIff GIF, it’s really a minimal update, and of course the key is important, because the key is the unique identifier of this node, telling the DIff algorithm that it’s the same DOM before and after the update
In addition, only when the node is the same, fine comparison is carried out, otherwise it is violent deletion of the old, insert the new. Extension question: how to define the same virtual node? Answer: The selectors are the same and the key is the same
Only the same layer comparison, not cross-layer comparison. Even if it is the same piece of virtual node, but cross layer, sorry, fine comparison does not go through you, but violent delete old, insert new
Question: : Diff is not a hand in hand, so does this really affect efficiency?
A: Some operations in the actual VUE development, the above 2 and 3 will not encounter extreme cases, so this is a reasonable optimization mechanism
For example, no one would write a code snippet like this
<div>
<section v-if="isFlag">
<p>A</p>
<p>B</p>
<p>C</p>
</section>
<p v-if=! "" isFlag">A</p>
<p v-if=! "" isFlag">B</p>
<p v-if=! "" isFlag">C</p>
</div>
Copy the codeStep analysis:
patch( oldVNode, newVNode )
-
When the patch function is called, it checks whether the oldVnode is a virtual node. If the oldVnode is a DOM node, it wraps the oldVnode as a virtual node.
-
OldVNode and newVNode are the same node, and how are they the same node?
-
If oldVNode and newVNode are not the same node, delete the old one and insert the new one
Note: When a node is created, its children need to be created and inserted recursively
-
If oldVNode and newVNode are the same node, a fine comparison is required
-
Continue refined comparison and judgment processing
-
Are oldVNode and newVNode the same object in memory? If so, skip it and do nothing
-
If not, check whether newVNode has the text attribute
-
If newVNode has a text attribute, check whether the text attribute in newVNode is the same as that in oldVNode
- If it’s the same, what’s good
- Alter the innerText of oldVNode to the text property of newVNode. Elm alter the innerText of elm to the text property of newVNode. Because when innerText is changed to newVNode’s text, the children property in the old node is automatically removed **)
-
If newVNode does not have the text attribute, it means that newVNode has the children attribute. Check whether oldVNode has the children attribute
-
If oldVNode doesn’t have children, that means oldVNode has text, The innerText in oldvNode. elm is emptied and the children child DOM node is inserted into oldvNode. elm
-
If oldVNode has children, here is oldVNode newVNode has children nodes, and this is the end judgment comparison.
-
Here we need to mention the four hit lookup. NewVNode header and tail: new before and new after, oldVNode header and tail: old before and old after. Why this algorithm is good is because it fits people’s programming habits.
-
Define four Pointers newStartIndex, newEndIndex, oldStartIndex, oldEndIndex, and four Pointers corresponding to four nodes: NewStartNode, newEndNode, oldStartNode, oldEndNode; The while loop is executed when oldStartIndex<=oldEndIndex && newStartIndex <= newEndIndex,
The comparison sequence is successively new before new after new, new after old, new after old, new before old, new before old, new before old, hit a direct next cycle, otherwise the next hit, if four are not hit, in separate processing
-
NewStartNode: Check whether newStartNode and oldStartNode are the same node
- If it is: Call patchVNode(oldStartNode, newStartNode) function for node processing, and newStartIndex++ oldStartIndex++, The corresponding newStartNode and oldStartNode are also updated
- If not: go to the second step, compare the new after, the old after
-
Old after new: Check whether newEndNode and oldEndNode are the same node
- If yes, call patchVNode(oldEndNode, newEndNode) function for node processing, and –oldEndIndex and –newEndIndex, corresponding oldEndNode and newEndNode should also be updated
- If not, proceed to the third step, compare the new after, the old before
-
Check whether newEndNode and oldStartNode are the same node
- If so, call patchVNode(oldStartNode, newEndNode) for node processing and move the old node to the end of the unprocessed node (oldEndvNode.elm), note: InsertBefore The existing node deletes the original node information, and newEndIndex– and ++oldStartIndex, oldStartNode and newEndNode are updated
- If not, proceed to step 4, comparing the new before and the old after
-
Check whether newStartNode and oldEndNode are the same node
- If yes, call patchVNode(oldEndNode, newStartNode) for node processing and move the old node to the front of the old unprocessed node (i.e. Oldstartvnode.elm), note: InsertBefore The existing node deletes the original node information, and oldEndIndex– and ++newStartIndex, oldEndNode and newStartNode are updated
- If not, it needs to be dealt with separately and proceed to Step 5
-
If none is hit, you need to determine whether the current newStartNode appears in the old node
- If not, it is new, so create the newStartNode as a real DOM and insert it before oldStartvNode. elm, then update the ++newStartIndex and newStartNode Pointers
- If so, the position has changed, then fetch the node corresponding to the current newStartNode in oldChildren, (that is, find newStartNode subscript in oldChildren, such as k, and call patchVNode(oldChildren[k], newStartNode) to update the node). Then set the current oldChildren subscript k to undefined. If undefined is encountered in the next loop, add the judgment lift and skip processing. Also, insert the node information before the current oldStartvNode. elm (that is, before the unprocessed node), and update the ++newStartIndex and newStartNode Pointers
- Question answer: why insert the item before the unprocessed node after setting it as undefined? Because the updated information only updates the information in the old node and does not move its position, so after the node at the old subscript is set to undefined, the updated node information saved before is moved to the front of the unprocessed node
-
Repeat the preceding operations until the loop condition oldStartIndex<=oldEndIndex && newStartIndex <= newEndIndex is not met
-
At the end of the loop, you have to make a judgment
- ifThe new front is less than or equal to the new rearNote These nodes requirenew, the new position is in front of the unprocessed node, loop between the current newStartIndex and newEndIndex, and add it in front of oldStartvNode. elm
- Question: why oldStartvNode. elm?
- If the former is less than or equal to the latter, these nodes need to be deleted
- ifThe new front is less than or equal to the new rearNote These nodes requirenew, the new position is in front of the unprocessed node, loop between the current newStartIndex and newEndIndex, and add it in front of oldStartvNode. elm
-
Flowchart screenshot
If you can’t see clearly above, please refer to the picture below:
Finish writing the function
function patch(oldVNode, newVNode){
// Determine whether the first argument passed in is a Dom node or a virtual node
if(oldVNode.sel == "" || oldVNode.sel == undefined) {// The first argument passed in is the DOM node, which is wrapped as a virtual node
oldVNode = vNode(oldVNode.tagName.toLowerCase(), {}, [], undefined, oldVNode)
}
// Check whether oldVNode and newVnode are the same node
if(checkSameNode(newVNode, oldVNode)){
patchVNode(oldVNode, newVNode)
}else{
// Not the same node, need to force insert new, delete old
// Insert the page here before the old node
let newVNodeElm = creatElement(newVNode)
if(oldVNode.elm.parentNode && newVNodeElm){
oldVNode.elm.parentNode.insertBefore(newVNodeElm, oldVNode.elm)
// Delete the old node
oldVNode.elm.parentNode.removeChild(oldVNode.elm)
}
}
}
function vNode(sel, data, children, text, elm){
return {
sel, data, children, text, elm, key: data.key
}
}
// Check if it is the same node
function checkSameNode(a,b){
return a.sel === b.sel && a.key === b.key
}
// The vNode is an orphan node
export default function createElement(vNode){
let domNode = document.createElement(vNode.sel)
// Does it have child nodes or text?
if(vNode.text ! = =' ' && (vNode.children == undefined || vNode.children.length === 0)) {// It contains text
domNode.innerText = vNode.text
}else if(Array.isArray(vNode.children) && vNode.children.length > 0) {// It contains child nodes, which need to be recursed
for (let index = 0; index < vNode.children.length; index++) {
// Get the current children
const element = vNode.children[index];
// Create its DOM, once the call to createElement means that the DOM is created, and its ELM property points to it
// The dom created is not yet on the tree and is an orphan node
let elementDom = createElement(element)
domNode.appendChild(elementDom)
}
}
// Add the elm attribute
vNode.elm = domNode
/ / returns the elm
return vNode.elm
}
// Compare the same virtual node
function patchVNode(oldVNode, newVNode){
// Check whether old and new vNodes are the same object
if(oldVNode === newVNode){
console.log("It's the same object.")
return
}
// Check whether newVNNode contains a text attribute
if(newVNode.text ! = =undefined && (newVNode.children === undefined || newVNode.children.length == 0)) {// newVNode has a text attribute
if(newVNode.text ! == oldVNode.text ){ oldVNode.elm.innerText = newVNode.text } }else {
// newVNode does not have a text attribute, that is, a children attribute
// Check whether oldVNode has children
if(oldVNode.children ! = =undefined && oldVNode.children.length >0) {// Old has children, which is the most complicated case, newVNode, oldVNode both have children
updateChildren(oldVNode.elm, oldVNode.children, newVNode.children)
}else{
// oldVNode has no children,newVNode has children
oldVNode.elm.innerText = ""
newVNode.children.forEach(item= > {
let domNode = createElement(item)
oldVNode.elm.appendChild(domNode)
})
}
}
}
// oldVNode and newVNode both have the children attribute
function updateChildren(parentElm, oldChildren, newChildren){
/ / the old before
let oldStartIndex = 0
/ / new front
let newStartIndex = 0
/ / after the old
let oldEndIndex = oldChildren.length - 1
/ / new after
let newEndIndex = newChildren.length - 1
// Old former node
let oldStartVNode = oldChildren[0]
// Old back node
let oldEndVNNode = oldChildren[oldEndIndex]
// New front node
let newStartVNode = newChildren[0]
// New post-node
let newEndVNode = newChildren[newEndIndex]
// Set of keys in the old node
let keyMap
while(oldStartIndex<=oldEndIndex && newStartIndex <= newEndIndex){
// If the old start node does not exist, undefined was set earlier
if(oldStartVNode == null) {// Note that undefined == null is true
oldStartVNode = oldChildren[++oldStartIndex]
}else if(oldEndVNNode == null){
oldEndVNNode = oldChildren[--oldEndIndex]
}else if(newStartVNode == null){
newStartVNode = newChildren[++newStartIndex]
}else if(newEndVNode == null){
newEndVNode = newChildren[--newEndIndex]
}
if(checkSameNode(newStartVNode, oldStartVNode)){
// The new node is the same as the old node
console.log("① The new one is the same as the old one")
patchVNode(oldStartVNode, newStartVNode)
oldStartVNode = oldChildren[++oldStartIndex]
newStartVNode = newChildren[++newStartIndex]
}else if(checkSameNode(newEndVNode, oldEndVNNode)){
// The new node is the same as the old node
console.log("② The new queen is the same as the old queen")
patchVNode(oldEndVNNode, newEndVNode)
oldEndVNNode = oldChildren[--oldEndIndex]
newEndVNode = newChildren[--newEndIndex]
}else if(checkSameNode(newEndVNode, oldStartVNode)){
// The new node is the same as the old node
console.log(③ The new queen is the same as the old one.)
patchVNode(oldStartVNode, newEndVNode)
// When the new queen matches the old one, it is necessary to move the node. Move the node pointed by the new one to the old one
// TODO query: why not set undefined? Does insertBefore affect whether the node will be deleted after moving?
parentElm.insertBefore(oldStartVNode.elm, oldEndVNNode.elm.nextSibling)
oldStartVNode = oldChildren[++oldStartIndex]
newEndVNode = newChildren[--newEndIndex]
}else if(checkSameNode(newStartVNode, oldEndVNNode)){
// The new node is the same as the old node
console.log("④ The new front is the same as the old one")
// To move the node, move the new node to the front of the old node
patchVNode(oldEndVNNode, newStartVNode)
// TODO query: why not set undefined? Does insertBefore affect whether the node will be deleted after moving?
// Note that insertBefore deletes the original node information
parentElm.insertBefore(oldEndVNNode.elm, oldStartVNode.elm)
oldEndVNNode = oldChildren[--oldEndIndex]
newStartVNode = newChildren[++newStartIndex]
}else {
console.log("None of them hit.")
// Continue to see if there are any left
if(! keyMap){ keyMap = {}for (let index = oldStartIndex; index < oldEndIndex; index++) {
const key = oldChildren[index].key
if(key ! = =undefined){
keyMap[key] = index
}
}
}
// Find the location of the current item (newStartIndex) in the keyMap
const idxInOld = keyMap[newStartVNode.key]
if(idxInOld == null) {// If idxInOld is undefined, it is a new project
parentElm.insertBefore(createElement(newStartVNode), oldStartVNode.elm)
}else{
console.log("If it's not undefined it's not a new item and needs to be moved.")
// If undefined, the project is not new and needs to be moved
const elmToMove = oldChildren[idxInOld]
patchVNode(elmToMove, newStartVNode)
// Set this item to undefined to indicate that the item has been processed
oldChildren[idxInOld] = undefined
// Move, insertBefore can also move
// Move to the front of oldStartIndex
parentElm.insertBefore(elmToMove.elm, oldStartVNode.elm)
}
newStartVNode = newChildren[++newStartIndex]
}
}
// At the end of the loop, the number of new nodes is less than or equal to that of new nodes
// Insert the node to be added before the new node
if(newStartIndex <= newEndIndex){
console.log('New node needs new')
for (let index = newStartIndex; index <= newEndIndex; index++) {
parentElm.insertBefore(createElement(newChildren[index]), oldStartVNode.elm)
}
}else if(oldStartIndex <= oldEndIndex){
console.log("Old nodes need to be deleted.")
// At the end of the loop, these nodes need to be deleted
for (let index = oldStartIndex; index <= oldEndIndex; index++) {
// There is a node marked undefined
oldChildren[index] && parentElm.removeChild(oldChildren[index].elm)
}
}
}
Copy the codeThe end of the
The resources
Virtual DOM and Diff algorithms for Vue source code Parsing
Recommended reading
Immortal Zhu [Vue principle] Diff – source version of the Diff process