Virtual DOM/domDiff

We often say that virtual DOM is the DOM node simulated by JS objects, and domDiff is the DOM change caused by an operation calculated by a specific algorithm. Virtual DOM is used in Both React and Vue. I will not say much about Vue only at the level of usage. I know more about virtual DOM in React, so I will talk about virtual DOM in React. The code involved in virtual DOM in React is mainly divided into the following three parts, the core of which is the domDiff algorithm in the second step:

  • Render JSX(or createElement API) into the virtual DOM
  • Recalculate the virtual DOM after state or property changes and generate a patch object (domDiff)
  • This patch object updates the DOM node in the view

The virtual DOM is not necessarily faster

Any frontiersman knows that DOM manipulation is a performance killer because it can cause pages to backflow or redraw. It is much more cost-effective to reduce DOM operations by a little more up-front computation. However, the phrase “using the virtual DOM is faster” does not necessarily apply to all scenarios. For example: a page has a button, click on the number plus one, it is definitely faster to directly manipulate the DOM. Using the virtual DOM is nothing more than an increase in computation and code. Even in complex cases, browsers are optimized for our DOM manipulation, and most browsers batch it based on how long and how many times we do it, so direct DOM manipulation isn’t necessarily slow. So why do current frameworks use the virtual DOM? This is because using the virtual DOM can increase the performance lower limit of your code and greatly optimize the performance cost of manipulating the DOM in large quantities. These frameworks also ensure that performance is acceptable even in the few scenarios where the VIRTUAL DOM is not great. Also, we like the fact that React, Vue, and others use the VIRTUAL DOM framework not just because they’re fast, but for many more important reasons. For example, React is friendly to functional programming, vUE has excellent development experience, etc. At present, there are a lot of people comparing these two frameworks and arguing with each other in the community. I think it is more meaningful to explore the principles of the two frameworks when you know both of them.

How to implement domDiff

Implementing domDiff is divided into four steps:

  1. Use JS to simulate real DOM nodes
  2. Convert the virtual DOM into the real DOM and insert it into the page
  3. When a change occurs, the difference between the two trees is compared and the difference object is generated
  4. Update the real DOM based on the difference objects

Let me draw you a picture:

To explain this picture: first of all, look at the first red block. It refers to the mapping of the real DOM to the virtual DOM. In fact, there is no process in React, we directly write the virtual DOM(JSX), but this virtual DOM represents the real DOM. When the virtual DOM changes, as in the figure above, its third P and son2 in the second P are removed. At this time, we will calculate a difference object patches according to the changes before and after. The key value of this differential object is the index of the traversal of the old DOM node, which is used to find that node. The attribute value is the change of the record, in this case remove, which means delete. Finally, the old DOM node is modified according to the index of each item in patches to the corresponding position.

How does the code do that?

Create a real DOM using the virtual DOM

The following code is the entry file, we simulate a virtual DOM called oldEle, we here is written dead. In React, JSX syntax is parsed by Babel to get an abstract syntax tree (AST), and then virtual DOM is generated. If you’re interested in Babel conversions, check out the other article getting Started with Babel — Implementing an ES6 Class Converter.

import { createElement } from './createElement'

let oldEle = createElement('div', { class: 'father' }, [
    createElement('h1', { style:'color:red'},'son1']),
    createElement('h2', { style:'color:blue'},'son2']),
    createElement('h3', { style:'color:red'},'son3'])
])
document.body.appendChild(oldEle.render())
Copy the code

The following file exports the createElement method. It’s a new Element class that calls its render method to convert the virtual DOM into the real DOM.

class Element {
    constructor(tagName, attrs, childs) {
        this.tagName = tagName
        this.attrs = attrs
        this.childs = childs
    }
    render() {
        let element = document.createElement(this.tagName)
        let attrs = this.attrs
        letChilds = this.childs // Set propertiesfor (let attr in attrs) {
            setAttr(element, Attr, attrs[Attr])} // Create and insert child nodesfor (let i = 0; i < childs.length; i++) {
            let child = childs[i]
            console.log(111, child instanceof Element)
            let childElement = child instanceof Element ? child.render() : document.createTextNode(child)
            element.appendChild(childElement)
        }
        return element
    }
}
function setAttr(ele, attr, value) {
    switch (attr) {
        case 'style':
            ele.style.cssText = value
            break;
        case 'value':
            let tageName = ele.tagName.toLowerCase()
            if (tagName == 'input' || tagName == 'textarea') {
                ele.value = value
            } else {
                ele.setAttribute(attr, value)
            }
            break;
        default:
            ele.setAttribute(attr, value)
            break; }}function createElement(tagName, props, child) {
    return new Element(tagName, props, child)
}
module.exports = { createElement }
Copy the code

Now the code is ready to run, and the result is shown below:

Let’s continue with the domDIff algorithm

//keyIndex records the traversal orderlet keyIndex = 0
function diff(oldEle, newEle) {
    let patches = {}
    keyIndex = 0
    walk(patches, 0, oldEle, newEle)
    returnPatches} // Analyze the changesfunction walk(patches, index, oldEle, newEle) {
    letCurrentPatches = []; currentPatches = []if(! newEle) { currentPatches.push({type: 'remove'})}else if(oldele. tagName == newele. tagName) {// compare the sons of the walkChild(patches, currentPatches, oldele. childs, Newele.childs)} // Determine if the current node has changed, and if so, put the patch in the patch setif (currentPatches.length) {
        patches[index] = currentPatches
    }
}
function walkChild(patches, currentPatches, oldChilds, newChilds) {
    if (oldChilds) {
        for (let i = 0; i < oldChilds.length; i++) {
            let oldChild = oldChilds[i]
            let newChild = newChilds[i]
            walk(patches, ++keyIndex, oldChild, newChild)
        }
    }
}
module.exports = { diff }
Copy the code

The above code is a super-simplified version of the domDiff algorithm:

  • First declare a variable to record the order of traversal
  • The walk method is executed to analyze the change, and if the two elements have the same tagName, the child nodes are recursively traversed

There should be a lot of logic in the walk, but I only dealt with one case where the element was removed. There should be all sorts of additions, substitutions, and a lot of boundary checking involved. The real domDiff algorithm is complex, its complexity should be O(n3), and React has made a series of compromises to reduce the complexity to linear. I just choose a case here to do a demonstration, interested can see the source code or search some related articles. This article is called “shallow in, shallow out” after all, very shallow…

Ok, so let’s run this algorithm and see what happens:

import { createElement } from './createElement'
import { diff } from './diff'

let oldEle = createElement('div', { class: 'father' }, [
    createElement('h1', { style: 'color:red'},'son1']),
    createElement('h2', { style: 'color:blue'},'son2']),
    createElement('h3', { style: 'color:red'},'son3']])let newEle = createElement('div', { class: 'father' }, [
    createElement('h1', { style: 'color:red'},'son1']),
    createElement('h2', { style: 'color:blue' }, [])
])
console.log(diff(oldEle, newEle))
Copy the code

I created a new element in the entry file to represent the changed virtual DOM. It has two elements deleted, one H3 and one text node SON2. In theory, there should be two records.

As we can see, there are two attributes in the output patches object. The attribute name is the traversal serial number of this element, and the attribute value is the recorded information. We traverse to find the old DOM node through the serial number, and make corresponding updates through the information in the attribute value.

Update the view

Let’s see how to update the view with the patches object we obtained:

let index = 0;
let allPatches;
function patch(root, patches) {
    allPatches = patches
    walk(root)
}
function walk(root) {
    let currentPatches = allPatches[index]
    index++
    (root.childNodes || []) && root.childNodes.forEach(child => {
        walk(child)
    })
    if (currentPatches) {
        doPatch(root, currentPatches)
    }
}
function doPatch(ele, currentPatches) {
    currentPatches.forEach(currentPatch => {
        if (currentPatch.type == 'remove') {
            ele.parentNode.removeChild(ele)
        }
    })
}
module.exports = { patch }
Copy the code

The patch method exported from the file has two parameters: root is the real DOM node, and patches are the patch object. We use the same means as we use to traverse the virtual DOM (first order, depth first) to traverse the real nodes, which is very important, because we record which node changes through the key attribute of the patches object. The same traversal will ensure that our correspondence is correct. The doPatch method is simple. If the type is “remove”, remove the DOM node. In fact, this method should not be so simple, it should also deal with a lot of things, such as delete, interchange, and in fact, it should also determine the changes in the attribute and do the corresponding processing. I’m not going to say I couldn’t write it at all… Now let’s apply the patch method:

import { createElement } from './createElement'
import { diff } from './diff'
import { patch } from './patch'

let oldEle = createElement('div', { class: 'father' }, [
    createElement('h1', { style: 'color:red'},'son1']),
    createElement('h2', { style: 'color:blue'},'son2']),
    createElement('h3', { style: 'color:green'},'son3']])let newEle = createElement('div', { class: 'father' }, [
    createElement('h1', { style: 'color:red'},'son1']),
    createElement('h2', { style: 'color:green'}, [])] // The patch method is used to patch the original root node and update it to the new nodelet root = oldEle.render()
let patches = diff(oldEle, newEle)
patch(root, patches)
document.body.appendChild(root) 
Copy the code

Ok, let’s execute the code and see what happens to the view:

We see that the H3 tag is missing, the H2 tag is still there, but the text node SON2 is missing, just as we would expect. At this point, the algorithm has been written, and the code posted above is posted by module, and it is complete and running.

Unresolved issues

There are many problems that this algorithm does not deal with, such as:

  • Attribute changes are not handled
  • Only deletions are handled, additions and substitutions are not
  • If you remove the first element, all subsequent elements will be considered different and replaced due to misindexing. React uses the key attribute to solve this problem, and also compromises performance.
  • Of course, there are many, many optimizations

The last

The above code is just a simple implementation of the core ideas in React, just for you to understand the idea of domDiff algorithm, such as my description let you have a little interest in domDiff or a little help to you, I am very happy.