See through the Virtual DOM

I am a non-professional front-end programmer, if there is a harvest, please also like 👍, more wonderful articles can also pay attention to my wechat public number [South Orange front-end]😘, we can communicate more.

What is?

The essence of a Virtual DOM is an object with three attributes: Tag, attrs, and children. We can use this object to represent nodes in a page.

var element = {
  tag: 'ul'.// Node label name
  attrs: { // A DOM property that uses an object to store key-value pairs
    id: 'list'
  },
  children: [ // Children of this node
    {tag: 'li'.attrs: {class: 'item'}, children: ["Item 1"] {},tag: 'li'.attrs: {class: 'item'}, children: ["Item 2"] {},tag: 'li'.attrs: {class: 'item'}, children: ["Item 3"]},]}Copy the code

The corresponding HTML node looks like this:

<ul id='list'>
  <li class='item'>Item 1</li>
  <li class='item'>Item 2</li>
  <li class='item'>Item 3</li>
</ul>
Copy the code

Why is that?

Imagine such a scene, if we want to draw a table on the web, we traverse the back-end to data and then create the corresponding tags inserted into the page, if the back-end data to the changed, so we need to traverse the back-end data, and then create the corresponding node, and then inserted into the page.



If we still want to use JS to manipulate the elements in the table, then with the increase of data and manipulation capabilities, JS code will become very cumbersome and difficult to maintain.



Those of you who are working on the front end should know that there are serious performance problems. Because Javascript has many standards, browsers make DOM elements very complex to meet these standards, which greatly increases the amount of work behind the DOM manipulation. This is the first level structure of a DIV node.













In order to reduce the amount of JS code we have a number of MVVM frameworks to help us, essentially what these frameworks do is listenstate(data)Then update the view. But implementations of these frameworks differ in the way they are implemented, including AngularDirty checking, VueDepend on the collectionAnd so on, and what is said hereVirtual DOM (Virtual DOM)It’s actually a method, mostly used by React.



It works by representing elements in a page with an object, known as the virtual DOM. We then generate real element nodes based on the virtual DOM and insert them into the page when the data or element in the page changes resulting in the correspondingVirtual DOM changes, we just use an algorithm to traverse our

1. Use JS objects to simulate DOM trees

We need to use a constructor to generate the object. The constructor is used for the following reasons:

• It is convenient for us to use recursion when we create corresponding nodes later
• Facilitate subsequent type checking of child elements

function Element (tag, attrs, children) {
  this.tagName = tagName
  this.props = props
  this.children = children
}

function el(tag, attrs, children) {
  return new Element(tag, attrs, children)
}
Copy the code

Then generate the objects we need:

var ul = el('ul', {id: 'list'}, [
  el('li', {class: 'item'},'Item 1']),
  el('li', {class: 'item'},'Item 2']),
  el('li', {class: 'item'},'Item 3']])Copy the code

Then you can generate the required DOM nodes from the object, which is important:

        Element.prototype.render = function(){
            let el = document.createElement(this.tag);
            let attrs = this.attrs;
            for(let attrName in attrs) {
                let attrValue = attrs[attrName];
                el.setAttribute(attrName,attrValue);
            }
            
            let children = this.children || [];
            children.forEach( child= > {
                let childEle = (child instanceof Element)? // Determine whether child elements are nodes
                child.render(): // Continue rendering if recursively
                document.createTextNode(child); // Otherwise, create a text node
                el.appendChild(childEle);
            });
            return el;
        }
        
        let ulRoot = ul.render();
        document.body.appendChild(ulRoot);
Copy the code

// diff function to compare two trees
function diff (oldTree, newTree) {
  var index = 0 // Flag of the current node
  var patches = {} // The object used to record the differences between each node
  dfsWalk(oldTree, newTree, index, patches)
  return patches
}

// Depth-first traversal of both trees
function dfsWalk (oldNode, newNode, index, patches) {
  // Compare oldNode with newNodepatches[index] = [...]  diffChildren(oldNode.children, newNode.children, index, patches) }// Iterate over the child nodes
function diffChildren (oldChildren, newChildren, index, patches) {
  var leftNode = null
  var currentNodeIndex = index
  oldChildren.forEach(function (child, i) {
    var newChild = newChildren[i]
    currentNodeIndex = (leftNode && leftNode.count) // Compute node id
      ? currentNodeIndex + leftNode.count + 1
      : currentNodeIndex + 1
    dfsWalk(child, newChild, currentNodeIndex, patches) // Depth traverses the child nodes
    leftNode = child
  })
}
Copy the code

patches[0] = [{difference}, {difference}, ...] // Use an array to store the differences between old and new nodes
Copy the code

3. Compare the differences between two nodes

How do we compare two trees? What does the patch look like? Because there may be many differences between two nodes, such as tag name, div and SPAN, attribute value and text content in tag, etc., we first divide these differences into four types:

1. Replace the original node, such as div with section
2. Move, delete, and add child nodes, such as the div child node above, interchanging p and ul
3. The attributes of the node are modified
4. For text nodes, the text content may change. For example, change the content of text node 2 above to Virtual DOM 2.

The corresponding;

var REPLACE = 0
var REORDER = 1
var PROPS = 2
var TEXT = 3
Copy the code

If the tag name is changed from div to section, we need to replace the previous node directly:

patches[0] = [{
  type: REPALCE,
  node: newNode // el('section', props, children)
}]
Copy the code

If you add container to a div, record:

patches[0] = [{
  type: REPALCE,
  node: newNode // el('section', props, children)
}, {
  type: PROPS,
  props: {
    id: "container"}}]Copy the code

If the text node is different, then we need to record it:

patches[2] = [{
  type: TEXT,
  content: "Virtual DOM2"
}]
Copy the code

We can record all the changes in the tags, attributes, and text of the node. So if the position of the node at the same level is changed, for example, the child node of the div was P, SPAN, and section, and now it is SPAN, section, and P, should we completely replace the previous three tags? This is obviously expensive, and creating the DOM and then inserting it is an expensive operation. We just need to use the algorithm to move it around.

This algorithm is called the list comparison algorithm.

Suppose the order of the old nodes is like this:

a b c d e f g h i
Copy the code

The node is now deleted, inserted, and moved. Add j node, delete E node, move H node: The order of new nodes is as follows:

a b c h d f g i j
Copy the code

So how to use the simplest delete, move, add to complete the old to the new change?

Now that you know the order of old and new, minimize insert and delete (move can be thought of as a combination of delete and insert). Abstract, this problem is actually Edition Distance of string. The most common solution algorithm is Levenshtein Distance, which is solved by dynamic programming and the time complexity is O(M * N). But we don’t really need to achieve the minimum operation, we just need to optimize some of the more common movement cases, sacrifice some DOM operations, so that the algorithm time complexity is linear (O(Max (M, N)). Specific algorithm details are more, here is not tired, interested can refer to the code.

The resulting patch looks like this:

patches[0] = [{
  type: REORDER,
  moves: [{remove or insert}, {remove or insert}, ...]
}]
Copy the code

Note that many times the names of two nodes may be the same, so we need to add a unique token key to each node. We use the key when comparing lists, so that we can reuse nodes when they are just moving around. We then use depth-first traversal of the virtual DOM tree to compare the current nodes in the traversal to those in the new tree and record any differences. After obtaining patches, we need to modify the nodes in the page according to the patches. The complete diff algorithm code can be found in diff.js.

function patch (node, patches) {
  var walker = {index: 0}
  dfsWalk(node, walker, patches)
}

function dfsWalk (node, walker, patches) {
  var currentPatches = patches[walker.index] // Extract the difference of the current node from patches

  var len = node.childNodes
    ? node.childNodes.length
    : 0
  for (var i = 0; i < len; i++) { // Depth traverses the child nodes
    var child = node.childNodes[i]
    walker.index++
    dfsWalk(child, walker, patches)
  }

  if (currentPatches) {
    applyPatches(node, currentPatches) // Perform DOM manipulation on the current node}}Copy the code

function applyPatches (node, currentPatches) {
  currentPatches.forEach(function (currentPatch) {
    switch (currentPatch.type) {
      case REPLACE:
        node.parentNode.replaceChild(currentPatch.node.render(), node)
        break
      case REORDER:
        reorderChildren(node, currentPatch.moves)
        break
      case PROPS:
        setProps(node, currentPatch.props)
        break
      case TEXT:
        node.textContent = currentPatch.content
        break
      default:
        throw new Error('Unknown patch type ' + currentPatch.type)
    }
  })
}
Copy the code

5. To summarize

Finally, we can find that the complete virtual DOM algorithm is actually divided into three parts. We can outline the specific process. We first need to generate the virtual DOM using the Element constructor, then use the Render method to convert it into a real DOM object to insert into the page. When the data in the page is modified to obtain a new virtual DOM tree, the method of Diff is used to traverse the old virtual DOM object and the new virtual DOM tree for comparison to obtain patches. Then the patch method is introduced to change the page with the real DOM object. This process is also depth-first traversal of real DOM nodes to find patches corresponding to the current node from patches for node operation. The last thing I want to say is that the render method that generates the virtual DOM into a real object is important to understand. This is the original topic of the previous byte test.

// 1. Build the virtual DOM
var tree = el('div', {'id': 'container'}, [
    el('h1', {style: 'color: blue'},'simple virtal dom']),
    el('p'['Hello, virtual-dom']),
    el('ul', [el('li')]])// 2. Build the real DOM from the virtual DOM
var root = tree.render()
document.body.appendChild(root)

// 3. Generate a new virtual DOM
var newTree = el('div', {'id': 'container'}, [
    el('h1', {style: 'color: red'},'simple virtal dom']),
    el('p'['Hello, virtual-dom']),
    el('ul', [el('li'), el('li')]])// 4. Compare two virtual DOM trees
var patches = diff(tree, newTree)

// 5. Apply changes to real DOM elements
patch(root, patches)
Copy the code

The complete code implemented in this article is stored on Github for study only.