The main purpose of this article is to let everyone: really, thoroughly understand the virtual DOM and diff algorithm, so what is really, thoroughly understand? It’s us who have to knock the bottom out of them! fromHow the virtual DOM is generated by the render function (h function) (handwritten H function)And to thePrinciple of diFF algorithm (handwritten DIFF algorithm)And the lastHow the virtual DOM turns into the real DOM through diff (in fact, the virtual DOM turns back into the real DOM is covered in the diff algorithm), in order to facilitate everyone to understand, the article may involve more points, the content is longer, I hope you patience fine, finally, I hope you point a big guyWow!!!!!!.

Ok, without further ado, officially enter the topic of the article, so that you really, thoroughly master the virtual DOM and diff algorithm. Next, we implement the virtual DOM and diff algorithms step by step.

A brief introduction to the virtual DOM and diff algorithms

Let’s start with a simple example of the virtual DOM and diff algorithm: Let’s say we have a house diagram, and now we need to modify the house diagram as follows:

In fact, it’s a game of finding fault, let’s find out what’s different. Now, I’ve circled the differences,

Now that we know what to do, how do we do it? The most stupid method is to completely tear down and rebuild again, but in reality, we certainly will not dismantle and build again, so low efficiency, and the cost is too expensive. It’s done, but it’s not a minimal update, so what we want is diff,

So what is a diff? In fact,diffIn our case, it’s an algorithm that represents the least amount of updates, and it’s going to be refined and compared to the least amount of updates. As you can see, it’s cheaper, it’s not expensive, and it’s optimized, so correspondence is critical in our Vue underlayer.

Ok, now back to our Vue, the above diagram is equivalent to DOM nodes in Vue, we need to modify these nodes (add and delete), and thenUpdate the DOM as little as possible, which will avoid our performance overhead.

/ / the original DOM<div class="box">
        <h2>The title</h2>
        <ul>
            <li>1</li>
            <li>2</li>
            <li>3</li>
        </ul>
    </div>
Copy the code

// Modified DOM<div class="box">
        <h2>The title</h2>
        <span>The qingfeng-xiangguang fracture</span>
        <ul>
            <li>1</li>
            <li>2</li>
            <li>3</li>
            <li>4</li>
        </ul>
    </div>
Copy the code

Here, we can use diff algorithm for fine comparison, to achieve the minimum update. Now that we’ve seen what a DIff is, let’s take a look at what a virtual DOM is.

<div class="box">
        <h2>The title</h2>
        <ul>
            <li>1</li>
            <li>2</li>
            <li>3</li>
        </ul>
    </div>
Copy the code

{
    sel: "div".elm: undefined.// Indicates that the virtual node is not in the tree
    key: undefined.// Unique identifier
    data: {
        class: { "box" : true}},children: [{sel: "h2".data: {},
            text: "Title"
        },
        {
            sel: "ul".data: {},
            children: [{sel: li, data: {}, text: "1"},
                { sel: li, data: {}, text: "2"},
                { sel: li, data: {}, text: "3"}]}]}Copy the code

It can be seen from observation that the virtual DOM is a JavsScript object, which contains SEL selector, data data, text text content, children child tags, etc., nested layer by layer. This represents a virtual DOM structure, and processing the virtual DOM is always simpler and more efficient than processing the real DOM, so the diff algorithm takes place on the virtual DOM. Note that the diff algorithm takes place on the virtual DOM.

Why do we need a Virtual DOM?

First, we all know that a secret to front-end performance optimization is as much as possibleReduce DOM manipulationNot only is DOM relatively slow, but changing the DOM can cause browser problemsRefluxing and repaintingThese can degrade performance, so we need the virtual DOM inPatch (Compare old and new virtual DOM updates to update views)Process as much as possibleThe differences are updated to the DOM onceThis ensures that the DOM will not suffer from poor performance.
Secondly, useVirtual DOMThe DOM does not need to be updated immediately after changing the current state. Instead, the updated content is updated without any processing for the unchanged contentThe differences were compared before and after.
Finally, and the original purpose of the Virtual DOM, is to be bettercross-platformNode.js, for example, doesn’t have the DOM if you want to implement itSSR (Server-side rendering)One way is to use the Virtual DOM, which is itself a JavaScript object.

H function (create virtual DOM)

Function h is used to create a virtual node (vNode). The first parameter is the label name, the component’s option object, and the function. The second parameter is the attribute of the label (optional)

 h('a', {props: {href: 'http://www.baidu.com'}, "Baidu"})
Copy the code

The virtual node corresponding to the above function h is:

{ sel: 'a'.data: { props: {href: 'http://www.baidu.com'}}, text: "Baidu"}
Copy the code

The actual DOM nodes are:

<a href = "http://www.baidu.com">baidu</a>
Copy the code

We can also use nested h functions, such as:

h('ul', {}, [
    h('li', {}, '1'),
    h('li', {}, '2'),
    h('li', {}, '3'),])Copy the code

Nested h functions generate a virtual DOM tree.

{
            sel: "ul".elm: undefined.key: undefined.data: {},
            children: [{sel: li, elm: undefined.key: undefined.data: {}, text: "1"},
                { sel: li, elm: undefined.key: undefined.data: {}, text: "2"},
                { sel: li, elm: undefined.key: undefined.data: {}, text: "3"}}]Copy the code

Ok, so now that we’ve seen how h functions are used, let’s write a castrated version of h.

Handwritten h function

Our handwritten function considers only three cases (with three arguments), as follows:

Situation (1) : h (' div ', {}, 'text') (2) : h (' div ', {}, []) (3) : h (' div ', {}, h ())Copy the code

Before writing the h function, we need to declare a function to create a virtual node

// vnode.js returns the virtual node
export default function(sel, data, children, text, elm) {
    // SEL selector, data property, children child node, text text content, real DOM node bound to elm virtual node
    const key = data.key
    return {
        sel,
        data,
        children,
        text,
        elm,
        key
    }
}
Copy the code

After the declaration of vnode function, we formally write h function, the idea is as follows:

Check whether the third argument isA string or a number. If it is a string or number, return vNode directly
Check whether the third argument is a singleAn array of. Declare aAn array of, which is used toStorage child nodeWe need to check whether each item is an object (because vNode returns an object and must have sel), but we don’t need to execute each item because h has already been executed in the array. In fact, the function is not called recursively (calling itself), but is nested layer by layer
Check whether all three parameters are oneobject. Assign this object directly tochildrenAnd will returnvnode

// h.js function
import vnode from "./vnode";
Div ('div', {}, 'text ');
If ('div', {}, [])
// case ③ : h('div', {}, h())
export default function (sel, data, c) {
    // Determine whether three arguments are passed
    if (arguments.length ! = =3) 
        throw Error('The arguments passed in must be three arguments') 
    // Determine the type of c
    if (typeof c === 'string' || typeof c === 'number') {
        / / is (1)
        return vnode(sel, data, undefined, c, undefined)}else if(Array.isArray(c)) {
        / / (2)
        / / traverse
        let children = []
        for(let i = 0; i < c.length; i++) {
            // The child must be an h function
            if(! (typeof c[i] === 'object' && c[i].hasOwnProperty('sel')))
                throw Error('There's an item in the array that's not h.')
            // The collection of child nodes does not need to be performed because the array is already called h
            children.push(c[i])
        }
        return vnode(sel, data, children, undefined.undefined)}else if (typeof c === 'object' && c.hasOwnProperty('sel')) {
        // Put the child node directly into children
        let children = [c]
        return vnode(sel, data, children, undefined.undefined)}else {
        throw Error('Incorrect format of argument passed in')}}Copy the code

With the above code, we have implemented the basic functions of a simple H function.

Feel the Diff algorithm

Before we get to diff, let’s get a feel for the power of diff. Let’s take a quick example using snabbdom.

import {
    init,
    classModule,
    propsModule,
    styleModule,
    eventListenersModule,
    h,
} from "snabbdom";
// Create patch function
const patch = init([
    classModule, 
    propsModule, 
    styleModule, 
    eventListenersModule, 
]);
// Put the virtual node on the tree
const container = document.getElementById("container");
const btn = document.getElementById("btn");
// Create a virtual node
const myVnode1 = h('ul', {}, [
    h('li', {}, 'A'),
    h('li', {}, 'B'),
    h('li', {}, 'C'),
    h('li', {}, 'D')
])
patch(container, myVnode1)
const myVnode2 = h('ul', {}, [
    h('li', {}, 'A'),
    h('li', {}, 'B'),
    h('li', {}, 'C'),
    h('li', {}, 'D'),
    h('li', {}, 'E'),
])
btn.addEventListener('click'.() = > {
    / / on the tree
    patch(myVnode1,myVnode2)
})
Copy the code

When we click to change the DOM, we find that a new li tag will be added with the content of E. It is difficult to tell whether the single click event will beThe old virtual DOMReplace them allNew virtual DOMAnd then render it into the real DOM, again directly in theThe old virtual DOMThe top is directly behindAdd a nodeSo, here we can subtly open the test tool and directly modify the label content. If all the tags are removed after clicking, the label content will be changed. If the content is not changed, it will be added last.

Click to change the DOM structure:

Sure enough, the content of the previous modification did not change, which can be verified is carried outDiff algorithm refined comparison, to the minimum amount of updates. So the question is, what if I add a node in front of it? Add a node directly in front of it as you add it at the end. Let’s give it a try and see how it works:

.const container = document.getElementById("container");
const btn = document.getElementById("btn");
// Create a virtual node
const myVnode1 = h('ul', {}, [
    h('li', {}, 'A'),
    h('li', {}, 'B'),
    h('li', {}, 'C'),
    h('li', {}, 'D')
])
patch(container, myVnode1)
const myVnode2 = h('ul', {}, [
    h('li', {}, 'E'),  // Move E to the front
    h('li', {}, 'A'),
    h('li', {}, 'B'),
    h('li', {}, 'C'),
    h('li', {}, 'D'),
])
btn.addEventListener('click'.() = > {
    / / on the tree
    patch(myVnode1,myVnode2)
})
Copy the code

Click change DOM structure

Oh and clear!!!!! Instead, you’ll notice that the text is completely changed, which means that the ORIGINAL DOM is removed and the new one is put back on the tree. At this point, you might be wondering if the Diff algorithm isn’t that powerful, but you’d be wrong to think so. Think back to learning Vue when traversing DOM nodesEmphasize the unique identifier keyKey comes into play here. Let’s take a look at the effect with key:

.const myVnode1 = h('ul', {}, [
    h('li', { key: "A" }, 'A'),
    h('li', { key: "B" }, 'B'),
    h('li', { key: "C" }, 'C'),
    h('li', { key: "D" }, 'D')
])
patch(container, myVnode1)
const myVnode2 = h('ul', {}, [
    h('li', { key: "E" }, 'E'),
    h('li', { key: "A" }, 'A'),
    h('li', { key: "B" }, 'B'),
    h('li', { key: "C" }, 'C'),
    h('li', { key: "D" }, 'D'),])...Copy the code

Click change DOM structure

At this point, you can see what key does in the loop. We can derive thatConclusion aKey is the unique identifier of the current nodeThe diff algorithmBefore and after the change they areSame DOM node.

When we modify the parent node, the parent node of the old and new virtual DOM is not the same node. Continue to observe how diff algorithm is analyzed

const myVnode1 = h('ul', {}, [
    h('li', { key: "A" }, 'A'),
    h('li', { key: "B" }, 'B'),
    h('li', { key: "C" }, 'C'),
    h('li', { key: "D" }, 'D')
])
patch(container, myVnode1)
const myVnode2 = h('ol', {}, [
    h('li', { key: "A" }, 'A'),
    h('li', { key: "B" }, 'B'),
    h('li', { key: "C" }, 'C'),
    h('li', { key: "D" }, 'D'),])Copy the code

Dot changes the DOM structureYou will notice that the old node is completely removed and the new node is re-placed on the tree. We can derive thatConclusion twoIs this:

Only if it isSame Virtual Node.The diff algorithmOnly fine comparison, otherwise it is violence to delete the old, insert the new. The criteria for identifying a virtual node are as follows: The selectors and keys of a virtual node are the same.

What if it is the same virtual node, but the child nodes are not compared in the same layer?

const myVnode1 = h('div', {}, [
    h('li', { key: "A" }, 'A'),
    h('li', { key: "B" }, 'B'),
    h('li', { key: "C" }, 'C'),
    h('li', { key: "D" }, 'D')
])
patch(container, myVnode1)
const myVnode2 = h('div', {}, h('section', {},
    [
        h('li', { key: "A" }, 'A'),
        h('li', { key: "B" }, 'B'),
        h('li', { key: "C" }, 'C'),
        h('li', { key: "D" }, 'D')))Copy the code

Click change DOM structure

You can see that the DOM structure now has an extra layer of section tags wrapped around it, and then the content of the text changes, so we can deriveConclusion three:

The diff algorithmonlyCompare at the same level, not across levels. Even if it is the same piece of virtual nodes, but across layers, not fine comparison, but forcibly delete the old, and then insert the new.

In summary, three conclusions of diff algorithm are drawn:

keyIs the unique identifier of the current nodeThe diff algorithmBefore and after the change they areSame DOM node.
Only if it isSame Virtual Node.The diff algorithmOnly fine comparison, otherwise it is violence to delete the old, insert the new. Criteria for identifying a virtual node:Selectors (SEL) are the sameandThe key is the same.
The diff algorithmonlyCompare at the same level, not across levels. Even if it is the same piece of virtual nodes, but across layers, not fine comparison, but forcibly delete the old, and then insert the new.

If you look at this, you’ve learned a lot about the Diff algorithm.

The patch function

The main functions of patch function are:To judge whether it is the same node type, it is fine comparison, not violent deletion and insertion.

We can simply draw the current main flow chart of patch function as follows:

// patch.js The patch function
import vnode from "./vnode";
import sameVnode from "./sameVnode";
import createElement from "./createElement";
export default function (oldVnode, newVnode) {
    // Check whether the oldVnode is a virtual node
    if (oldVnode.sel == ' ' || oldVnode.sel == undefined) {
        // console.log(' not a virtual node ');
        // Create virtual DOM
        oldVnode = emptyNodeAt(oldVnode)
    }
    // Check if it is the same node
    if (sameNode(oldVnode, newVnode)) {
        console.log('It's the same node');
    } else {
        // Forcibly delete old nodes and insert new nodes
        // Pass in two parameters and insert the created node into the position of the specified benchmark
        createElement(newVnode, oldVnode.elm)
    }
}
// Create virtual DOM
function emptyNodeAt (elm) {
    return vnode(elm.tagName.toLowerCase(), {}, [], undefined, elm)
}
Copy the code

Before ascending the tree in the DOM, we need to understand the insertBefore () and appendChild () methods in the DOM, because only when you really know how to use them will it be easier to write the tree below.

AppendChild () method

AppendChild () method: Add a new child node to the end of the node’s child node list. Example: appendChild (newChild). Note: The appendChild () method adds a new node at the end of the child node in the parent node. (relative to the parent).

<body>
    <div class="box">
        <span>The qingfeng-xiangguang fracture</span>
        <ul>
            <li>1</li>
            <li>2</li>
        </ul>
    </div>
    <script>
        const box = document.querySelector('.box')
        const appendDom = document.createElement('div')
        appendDom.style.backgroundColor = 'blue'
        appendDom.style.height = 100 + 'px'
        appendDom.style.width = 100 + 'px'
        // Append a div to the end of the box
        box.appendChild(appendDom)
    </script>
</body>
Copy the code

You’ll notice that the div you’re creating is nested inside the box, and the div is a child of the box, and the box is a child of the div.

InsertBefore () method

The insertBefore() method: inserts a new child node before an existing byte point. Example: insertBefore(newChild,rechild). Note: The insertBefore () method adds a new node before an existing one. (relative to child nodes).

<body>
    <div class="box">
        <span>The qingfeng-xiangguang fracture</span>
        <ul>
            <li>1</li>
            <li>2</li>
        </ul>
    </div>
    <script>
        const box = document.querySelector('.box')
        const insertDom = document.createElement('p')
        insertDom.innerText = 'I am insertDOM'
        // Add a new node before box in the body
        box.parentNode.insertBefore(insertDom, box)
    </script>
</body>
Copy the code

We find that box and div are on the same level and are siblings.

Handling different nodes

SameVnode function

Function: Compares whether two nodes are the same node

// sameVnode.js
export default function sameVnode(oldVnode, newVnode) {
    return (oldVnode.data ? oldVnode.data.key : undefined) === (newVnode.data ? newVnode.data.key : undefined) && oldVnode.sel == newVnode.sel
}
Copy the code

Handwriting on the tree for the first time

Now that we understand the appendChild () and insertBefore () methods above, we begin to put the real DOM on the tree and render the page.

// patch.js The patch function
import vnode from "./vnode";
import sameVnode from "./sameVnode";
import createElement from "./createElement";
export default function (oldVnode, newVnode) {
    // Check whether the oldVnode is a virtual node
    if (oldVnode.sel == ' ' || oldVnode.sel == undefined) {
        // console.log(' not a virtual node ');
        // Create virtual DOM
        oldVnode = emptyNodeAt(oldVnode)
    }
    // Check if it is the same node
    if (sameNode(oldVnode, newVnode)) {
        console.log('It's the same node');
    } else {
        // Forcibly delete old nodes and insert new nodes
        // Pass in two parameters and insert the created node into the position of the specified benchmark
        createElement(newVnode, oldVnode.elm)
    }
}
// Create virtual DOM
function emptyNodeAt (elm) {
    return vnode(elm.tagName.toLowerCase(), {}, [], undefined, elm)
}
Copy the code

Patch is used to determine whether a node is the same, so we need to declare a createElement function to create the real DOM.

The createElement method function

CreateElement is mainly used to create the real DOM of the child node.

// createElement.js
export default function createElement(vnode,pivot) {
    // Create a node in the upper tree
    let domNode = document.createElement(vnode.sel)
    // Check whether there is text content or child nodes
    if(vnode.text ! =' ' && (vnode.children == undefined || vnode.children.length == 0)) {
        // The text content is assigned directly
        domNode.innerText = vnode.text
        // Add a node to the body
        The insertBefore() method inserts a new child node in front of an existing byte point. Relative to the child node
        pivot.parentNode.insertBefore(domNode, pivot)
    } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
        // There are child nodes}}Copy the code

// index.js
import patch from "./mysnabbdom/patch";
import h from './mysnabbdom/h'
const container = document.getElementById("container");
// Create a virtual node
const myVnode1 = h('h1', {}, 'words')
patch(container, myVnode1)
Copy the code

We have successfully rendered the created real DOM to the page, but this is only the simplest case, which is the case where the third argument to h is a string, so when the third argument is an array, there is no way to go up the tree. Now we need to optimize the createElement function further to achieve a recursive tree.

Create child nodes recursively

We see that the createElement function takes two arguments when we first go up the tree: Inside createElement we use insertBefore () to do this. To do this we need to know which node is already in the tree. Of course, When there is text (the third parameter is a string or number), we can find the position to be inserted, but when there is children, we cannot determine the position of the benchmark. Therefore, we need to put the work of uptree into the patch function. The createElement function just creates the node.

// index.js
import patch from "./mysnabbdom/patch";
import h from './mysnabbdom/h'
const container = document.getElementById("container");
// Create a virtual node
const myVnode1 = h('ul', {}, [
    h('li', {}, 'A'),
    h('li', {}, 'B'),
    h('li', {}, 'C'),
    h('li', {}, 'D')
])
patch(container, myVnode1)
Copy the code

// patch.js
import vnode from "./vnode";
import sameVnode from "./sameVnode";
import createElement from "./createElement";
export default function (oldVnode, newVnode) {
    // Check whether the oldVnode is a virtual node
    if (oldVnode.sel == ' ' || oldVnode.sel == undefined) {
        // console.log(' not a virtual node ');
        // Create virtual DOM
        oldVnode = emptyNodeAt(oldVnode)
    }
    // Check if it is the same node
    if (sameNode(oldVnode, newVnode)) {
        console.log('It's the same node');
    } else {
        // Forcibly delete old nodes and insert new nodes
        // The passed argument returns a real DOM for the created virtual DOM node
        let newVnodeElm = createElement(newVnode)
        console.log(newVnodeElm);
        // oldvNode.elm.parentNode for body adds a new node in front of the old one in body
        if (oldVnode.elm.parentNode && oldVnode.elm) {
            oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm)
        }
        // Delete the old node
        oldVnode.elm.parentNode.removeChild(oldVnode.elm)
    }
}
// Create virtual DOM
function emptyNodeAt (elm) {
    return vnode(elm.tagName.toLowerCase(), {}, [], undefined, elm)
}
Copy the code

Perfect the createElement function

// CreateElement.js is only responsible for creating the real node
export default function createElement(vnode) {
    // Create a node in the upper tree
    let domNode = document.createElement(vnode.sel)
    // Check whether there is text content or child nodes
    if(vnode.text ! =' ' && (vnode.children == undefined || vnode.children.length == 0)) {
        // The text content is assigned directly
        domNode.innerText = vnode.text
        // Add a node to the body
        The insertBefore() method inserts a new child node in front of an existing byte point. Relative to the child node
    } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
        // There are child nodes
        for(let i = 0; i < vnode.children.length; i++) {
            // console.log(vnode.children[i]);
            let ch = vnode.children[i]
            Once createElement is called, the DOM is created and the ELM property points to the created DOM
            let chDom = createElement(ch)
            // Add node with appendChild because the last real DOM(domVnode in this case) has already been generated before iterating through the next one so you can use appendChild
            domNode.appendChild(chDom)
        }
    }
    vnode.elm = domNode
    return vnode.elm
}
Copy the code

CreateElem (createElem) {createElem (createElem) {createElem (createElem);

First of all, the one we started withSel for the new virtual DOMThe property is ul, and the real DOM node is ulThe createElement method functionFound in the new virtual DOMThere are children attributeThe children property contains the h function.
Second, go into the for loop, get the first item in children, and then againCall the crateElement functioncreateReal DOMWhen the ul is created, the first call to createElement will return the created virtual DOMAppendChild method ()Append to ul, and so on, and execute the following array entries.
Finally, the good will be createdAll real DOMBack out, inThe patch functionUpper middle tree.

Execute the above code and the test results are as follows:Perfect! We have succeeded in rendering recursive child nodes to the page recursively, no matter how many layers are nested.

Before, we implemented not the same node, delete the old node and insert the new node operation, below, we will implement the same node is the relevant operation, this is the most important part of the article, diff algorithm is included in it!!

Processing the same node

In the above flowchart of patch function, we have removed the old node by force and then inserted the new node when dealing with different nodes. Now we make a fine comparison when dealing with the same node and continue to improve the main flow diagram of patch function:

If oldVnode has a children property and newVnode has a children property, then oldVnode has a children propertyMention a pointWhen weWhen DOM manipulation is performed, the DOM structure is automatically destroyed when the text content replaces the DOMThe innerText changes and the DOM structure is destroyed, so we don’t have to check whether the oldVnode has the children property.If a DOM node is inserted, the Text content will not be destroyed, so we need to delete it manually.This is why, after the flowchart, we need to manually delete the Text of oldVnode when adding children of newVnodeThe Text of newVnode is assigned directlytooldVnode.elm.innerTextThe reason why.

Knowing how the above flow chart works, we continue to write the code of the same node in the patch function.

// patch.js
import vnode from "./vnode";
import sameVnode from "./sameVnode";
import createElement from "./createElement";
export default function (oldVnode, newVnode) {
    // Check whether the oldVnode is a virtual node
    if (oldVnode.sel == ' ' || oldVnode.sel == undefined) {
        // console.log(' not a virtual node ');
        // Create virtual DOM
        oldVnode = emptyNodeAt(oldVnode)
    }
    // Check if it is the same node
    if (sameNode(oldVnode, newVnode)) {
        console.log('It's the same node');
        // Whether it is the same object
        if (oldVnode === newVnode) return
        // Whether newVnode has text
        if (newVnode.text && (newVnode.children == undefined || newVnode.children.length == 0)) {
            // Check whether the text of newVnode and oldVnode are the same
            if(! (newVnode.text === oldVnode.text)) {// Assign text directly to oldvNode.elm.innerText where the CJildred DOM structure of oldVnode is automatically destroyed
                oldVnode.elm.innerText = newVnode.text
            }
            // means newVnode has children
        } else {
            // Whether oldVnode has the children attribute
            if(oldVnode.children ! =undefined && oldVnode.children.length > 0) {
                // oldVnode has the children attribute
            } else {
                // oldVnode has no children attribute
                // Manually delete the text of oldVnode
                oldVnode.elm.innerText = ' '
                / / traverse
                for (let i = 0; i < newVnode.children.length; i++) {
                    let dom = createElement(newVnode.children[i])
                    // Append to oldvNode.elm
                    oldVnode.elm.appendChild(dom)
                }
            }
        }
    } else {
        // Forcibly delete old nodes and insert new nodes
        // The passed argument returns a real DOM for the created virtual DOM node
        let newVnodeElm = createElement(newVnode)
        console.log(newVnodeElm);
        // oldvNode.elm.parentNode for body adds a new node in front of the old one in body
        if (oldVnode.elm.parentNode && oldVnode.elm) {
            oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm)
        }
        // Delete the old node
        oldVnode.elm.parentNode.removeChild(oldVnode.elm)
    }
}
// Create virtual DOM
function emptyNodeAt(elm) {
    return vnode(elm.tagName.toLowerCase(), {}, [], undefined, elm)
}
Copy the code

.// Create a virtual node
const myVnode1 = h('ul', {}, 'oldVnode have text')

patch(container, myVnode1)
const myVnode2 = h('ul', {}, [
    h('li', {}, 'A'),
    h('li', {}, 'B'),
    h('li', {}, 'C'),
    h('li', {}, 'D')
])
btn.addEventListener('click'.() = > {
    patch(myVnode1, myVnode2)
})
Copy the code

OldVnode has Tex and newVnode has children as follows:

.// Create a virtual node
const myVnode1 = h('ul', {}, [
    h('li', {}, 'A'),
    h('li', {}, 'B'),
    h('li', {}, 'C'),
    h('li', {}, 'D')
])

patch(container, myVnode1)
const myVnode2 = h('ul', {}, 'newVnode have text')
btn.addEventListener('click'.() = > {
    patch(myVnode1, myVnode2)
})

Copy the code

OldVode with children and newVnode with text look like this:

Perfect! Now all we need is the diff.

PatchVnode function

In the patch function, we need to divide the comparison with the same node into a separate module patchVnode function, which is convenient for us to carry out recursive operation in diff algorithm.

The main function of patchVnode is:

Check whether newVnode and oldVnode refer to the same object. If so, return
If they both have text and are not equal, or if oldVnode has children and newVnode does not, then set the text node of oldvNode. elm to the text node of newVnode.
If oldVnode has no children and newVnode does, add the children of newVnode to oldvNode. elm after the implementation, and then delete the text of oldvNode. elm
If both have child nodes, it is important to perform the updateChildren function to compare the children

// patchVnode.js
export default function patchVnode(oldVnode, newVnode) {
    // Whether it is the same object
    if (oldVnode === newVnode) return
    // Whether newVnode has text
    if (newVnode.text && (newVnode.children == undefined || newVnode.children.length == 0)) {
        // Check whether the text of newVnode and oldVnode are the same
        if(! (newVnode.text === oldVnode.text)) {// Assign text directly to oldvNode.elm.innerText where the CJildred DOM structure of oldVnode is automatically destroyed
            oldVnode.elm.innerText = newVnode.text
        }
        NewVnode has children
    } else {
        // Whether oldVnode has the children attribute
        if(oldVnode.children ! =undefined && oldVnode.children.length > 0) {
            // oldVnode has the children attribute
        } else {
            // oldVnode has no children attribute
            // Manually delete the text of oldVnode
            oldVnode.elm.innerText = ' '
            / / traverse
            for (let i = 0; i < newVnode.children.length; i++) {
                let dom = createElement(newVnode.children[i])
                // Append to oldvNode.elm
                oldVnode.elm.appendChild(dom)
            }
        }
    }
}
Copy the code

The diff algorithm

The comparison of diFF algorithms is carried out in the form of double Pointers, which are the old front pointer, old back pointer, new front pointer and new back pointer respectively (the front pointer moves down and the back pointer moves up).

Four optimization strategies: (Hit: key and SEL should be the same)

(1),The old and the new
(2),New queen and old queen
(3),The new queen and the old one
(4),New before and old after

Note: when only the first one is not hit, the second one will be taken, and so on. If all four are not hit, it needs to be searched through a loop. Move only if the pointer is hit, otherwise not move.

The new and the oldCopy the code

If the loop completes the existing node first, the new node must have nodes to be inserted.

The new and the oldCopy the code

If the new node completes first and the old node still has remaining nodes, it indicates that there are nodes to be deleted from the old node.

Multiple deletions:If only case 1 is hit, and the remaining three are not hit, the loop needs to be iterated to findThe corresponding node in the old nodeAnd then inThe old virtual node sets this node to undefined. The nodes to be deleted are between the old node and the old node (including the old node and the old node).

The new and the oldCopy the code

当③ The new queen hits the old oneI want to move the node, move itThe node to which the new back pointsTo the old nodeThe back of the oldAnd findThe corresponding node in the old nodeAnd then inThe old virtual node sets this node to undefined.

The new before and afterCopy the code

When (4) the new front and the old back match, move the node. Move the node pointing to the new front to the old front of the old node, and find the corresponding node in the old node, and set this node to undefined in the old virtual node.

Ok, after the above dynamic explanation of the four hit methods, dynamic GIF images with watermarks, may not be very comfortable to look at, but of course understanding is the most important, so we started to handwritten diff algorithm code.

UpdateChildren function

The updateChildren () method does a fine comparison and then updates the child nodes. Here is a lot of code, need to be patient to read.

import createElement from "./createElement";
import patchVnode from "./patchVnode";
import sameVnode from "./sameVnode";
export default function updateChildren(parentElm, oldCh, newCh) {
    //parentElm is used to move oldCh children newCh children
    // console.log(parentElm, oldCh, newCh);
    / / the old before
    let oldStartIndex = 0
    / / after the old
    let oldEndIndex = oldCh.length - 1
    / / new front
    let newStartIndex = 0
    / / after the old
    let newEndIndex = newCh.length - 1
    // Old former node
    let oldStartVnode = oldCh[0]
    // Old back node
    let oldEndVnode = oldCh[oldEndIndex]
    // New front node
    let newStartVnode = newCh[0]
    // New post-node
    let newEndVnode = newCh[newEndIndex]
    / / store mapkey
    let keyMap
    // Loop condition old before <= old after && new before <= new after
    while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
        // First you need to determine whether it has been processed
        if (oldCh[oldStartIndex] == undefined) {
            oldStartVnode = oldCh[++oldStartIndex]
        } else if (oldCh[oldStartIndex] == undefined) {
            oldEndVnode = oldCh[--oldEndIndex]
        } else if (newCh[newStartIndex] == undefined) {
            newStartVnode = newCh[++newStartIndex]
        } else if (newCh[newEndIndex] == undefined) {
            newEndVnode = newCh[--newEndIndex]
        } else if (sameVnode(oldStartVnode, newStartVnode)) {
            // new and old before hit
            console.log('①, new before and old before hit ');
            // Call patchVnode to compare the object text children of the two nodes
            patchVnode(oldStartVnode, newStartVnode)
            // Move the pointer down to change the node
            oldStartVnode = oldCh[++oldStartIndex]
            newStartVnode = newCh[++newStartIndex]

        } else if (sameVnode(oldEndVnode, newEndVnode)) {
            // after the new and old hit
            console.log('②, after the new and the old hit ');
            // Call patchVnode to compare the object text children of the two nodes
            patchVnode(oldStartVnode, newStartVnode)
            // Moves the pointer down and changes the node
            oldEndVnode = oldCh[--oldEndIndex]
            newEndVnode = newCh[--newEndIndex]
        } else if (sameVnode(oldStartVnode, newEndVnode)) {
            // the new and the old before the match
            patchVnode(oldStartVnode, newEndVnode)
            console.log(newEndVnode);
            // Move node when ③ new and old hit, then move node,
            // Move the node pointed to by the new node to the end of the old node, find the corresponding node in the old node, and set this node to undefined in the old virtual node.
            parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
            // In the animation above, hit ③ was inserted after the old node so use nextSibling
            // Moves the pointer down and changes the node
            oldStartVnode = oldCh[++oldStartIndex]
            newEndVnode = newCh[--newEndIndex]
        } else if (sameVnode(oldEndVnode, newStartVnode)) {
            // new before and old after hit
            patchVnode(oldEndVnode, newStartVnode)
            // Move the node
            // When '④ new before' and 'old after' match, move the node, move the node pointing to 'new before (old after pointing to the same node)' to 'old before' of the old node.
            // And find the corresponding node in the 'old node', then set this node to undefined in the 'old virtual node'
            parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
            // Moves the pointer down and changes the node
            oldEndVnode = oldCh[--oldEndIndex]
            newStartVnode = newCh[++newStartIndex]
        } else {
            // None of the four hits
            console.log(11);
            //kepMap serves as a cache without traversing objects every time
            if(! keyMap) { keyMap = {}// Iterate over the old node
                for (let i = oldStartIndex; i <= oldEndIndex; i++) {
                    // Get the key of the old node
                    const key = oldCh[i].data.key
                    if(key ! =undefined) {
                        // The key is not empty and is stored in a keyMap object
                        keyMap[key] = i
                    }
                }
            }
            // Fetch the key in newCh and find its position in keyMap and map it to oldCh
            const oldIndex = keyMap[newStartVnode.key]
            if (oldIndex == undefined) {
                / / new
                console.log(111);
                parentElm.insertBefore(createElement(newStartVnode),oldStartVnode.elm)
            } else {
                // Move the position
                // Take out the item to move
                const elmToMove = oldCh[oldIndex]
                // Check whether the selectors are the same
                patchVnode(elmToMove, newStartVnode)
                // The tag has already been processed
                oldCh[oldIndex] = undefined
                // Move the node to the front of the old because the old before and after will be deleted
                parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm)
            }
            // Move only new nodes
            newStartVnode = newCh[++newStartIndex]
        }
    }
    // There are still nodes left at the end of the loop
    if (newStartIndex <= newEndIndex) {
        // Indicates that the new node has unprocessed nodes, which means that nodes need to be added
        console.log('New node');
        // Create a benchmark
        console.log(newCh[newEndIndex + 1]);
        But we write the code in the new virtual node, elm set undefined, so there will always be a small bug inserted behind
        // let before = newCh[newEndIndex + 1] == null ? null : newCh[newEndIndex + 1].elm
        // oldStartIndex oldCh[oldStartIndex]. Elm
        for (let i = newStartIndex; i <= newEndIndex; i++) {
            The crateElement function is used to create a new real DOM node
            // insertBefore automatically recognizes null
            parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartIndex].elm)
        }
    } else if (oldStartIndex <= oldEndIndex) {
        // Indicates that the old node has unprocessed nodes, which means that the node needs to be deleted
        console.log('Delete node');
        for (let i = oldStartIndex; i <= oldEndIndex; i++) {
            if(oldCh[i]) parentElm.removeChild(oldCh[i].elm)
        }
    }
}
Copy the code

Well, the above is Vue2 virtual DO M and diff algorithm castrated version of the code, there may be some bugs in the above code, but this will not affect your understanding of the DIFF algorithm, only you carefully taste, will certainly gain!! Finally, I’ll touch on my own understanding of the virtual DOM and diff algorithms

My understanding of virtual DOM and diff algorithms in Vue

In Javascript, rendering the real DOM is very expensive. If we modify some data, rendering directly to the real DOM will cause backflow and redrawing of the entire DOM tree. So is it possible to implement just updating the small piece of DOM we modify without causing the whole DOM to update? At this point, we need to generate the virtual DOM according to the real DOM first. When the data of a node of the virtual DOM is changed, a new Vnode will be generated. Then, the new Vnode will be compared with the old Vnodde and the differences will be directly modified to the real DOM. Then change the value of the old Vnode to the new Vnode. The process of diff algorithm is to call the patch function, compare the old and new nodes, and patch the real DOM at the same time. When the diff algorithm is used to compare old and new nodes, only same-level comparisons are made. In the Patch method, the old and new virtual nodes are first compared to see if they are the same node. If they are not, the old node is removed and a new virtual node is inserted. Then the createElement function is used to create the real DOM and render it to the real DOM tree. If it is the same node, use the patchVnode function to compare the old and new nodes, including attribute update, text update, and child node update. Both old and new nodes have child nodes, then diff algorithm is required and updateChildren method is called. If the new node has no text content while the old node has text content, You need to delete the text of the old node and then add child nodes. If the new node has text content, the text content of the old node is directly replaced. The updateChildren method extracts the children of both the old and new nodes, and then loops through the four optimization strategies using a two-pointer method. They are: ①, comparison between the new and the old before ②, comparison between the new and the old after ③, comparison between the new and the old before ④, comparison between the new and the old after. If four optimization strategy methods were not hit, will compare traversal method (source were used in the Map object in the cache, speed up the rate of comparison), if the set key, the key will be used for comparison, find the child nodes of the current new node mapping position in the Map, if not, you will need to add a node, If it exists, the node needs to be moved. Finally, after the loop ends, if the new node has any remaining nodes, the node needs to be added, and if the old node has any remaining nodes, the node needs to be deleted.

Above, is my understanding of Vue2 virtual DOM and diff algorithm, I hope to read this article for your understanding of Vue2 virtual DOM and diff algorithm help!! Finally, I hope you can give a thumbs-up ！！！！

The relevant source code in the article has been sent to Gitee. If you need to obtain it, you can stamp me to obtain the source code at ！！！！

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Vue virtual DOM and Diff algorithm

A brief introduction to the virtual DOM and diff algorithms

Why do we need a Virtual DOM?

H function (create virtual DOM)

Handwritten h function

Feel the Diff algorithm

The patch function

AppendChild () method

InsertBefore () method

Handling different nodes

SameVnode function

Handwriting on the tree for the first time

The createElement method function

Create child nodes recursively

Perfect the createElement function

Processing the same node

PatchVnode function

The diff algorithm

UpdateChildren function

My understanding of virtual DOM and diff algorithms in Vue

Vue virtual DOM and Diff algorithm

A brief introduction to the virtual DOM and diff algorithms

Why do we need a Virtual DOM?

H function (create virtual DOM)

Handwritten h function

Feel the Diff algorithm

The patch function

AppendChild () method

InsertBefore () method

Handling different nodes

SameVnode function

Handwriting on the tree for the first time

The createElement method function

Create child nodes recursively

Perfect the createElement function

Processing the same node

PatchVnode function

The diff algorithm

UpdateChildren function

My understanding of virtual DOM and diff algorithms in Vue

Related Posts

Understand this, call, apply, bind all at once

Css3 attribute box-reflect

The React project uses Mota to write object-oriented business model