The original address

Github series of posts

Before you read this article, you need to clarify two concepts. This article won’t give you a lengthy introduction to the React source code implementation or other similar Virtual DOM implementations. They are so complicated that a Virtual DOM implementation should take no more than 50 lines of code. Ok, here are two concepts you need to know:

  • The Virtual DOM is a representation of the real DOM

  • When the Virtual DOM Tree changes, the algorithm will automatically compare the old and new trees to find the difference, and only make minimal changes to the real DOM Tree

This article is to explain these two concepts step by step.

Representation of a DOM tree

First, we need to store the DOM tree in memory. As simple as this, we can represent the DOM tree as a JavaScript Object. Suppose we have a DOM tree that looks like this:



       
    

  
        
  • item 1
    • 

  
        
  • item 2
    • 


       

Copy the code

The corresponding JS object of the DOM tree is as follows:

{type: "ul", props: '} {' class ':' list are children: [{type: "li", props: {}, children: [' item 1]}, {type: 'li', props: {}, children: [' item 2 ']}]}Copy the code

By comparison, we can see that we represent any element in the DOM as:

{type: '... 'and props: {... }, children: [...] }Copy the code

The plain text nodes in the DOM are represented as ordinary JavaScript strings. This is still a simple DOM tree, but if it is a larger tree, we need an auxiliary function to construct the structure:

The function h (type, props,... children) { return { type, props, children }; }Copy the code

Based on this helper function, we can represent the simple DOM tree as follows:

H (' ul ', '} {' class ':' list are h (" li ", {}, "item 1"), h (" li ", {}, "item 2"),);Copy the code

Doesn’t it look a lot clearer? This structure and transformation equation looks a lot like the famous JSX. Take the Babel interpreter for example, which converts the DOM tree mentioned above into the following structure:

The React. The createElement method (" ul ", {className: 'list'}, the React. CreateElement method (" li ", {}, "item 1"), the React. The createElement method (" li ", {}, "item 2"),);Copy the code

To summarize, we can write DOM trees using JSX syntax as follows:


/** @jsx h */

const a = (
 
       
    
   
        
  • item 1
    • 
   
        
  • item 2
    • 
 
       

);
Copy the code

Babel converts JSX to the following format:

Const a = (h (' ul ', '} {the className: 'list are h (" li ", {}, "item 1"), h (" li ", {}, "item 2"),);) ;Copy the code

After h is executed, the entire object is converted to a basic JS object:

Const a = ({type: 'ul', props: {className: 'list'}, children: [{type: 'li', props: {}, children: "Item 1"}, {type: "li", props: {}, children: [' item 2]}});Copy the code

The address for this section on JSFiddle is: here

The complete compiler source code for Babel is:

/** @jsx h */ function h(type, props, ... children) { return { type, props, children }; } const a = (
       
    
    
        
  • item 1
    • 
    
        
  • item 2
    • 
  
       

);

console.log(a);Copy the code

Applying our DOM Representation

Now that the DOM tree can be represented as a pure JS object, the next step is to convert our custom virtual DOM structure into a real DOM tree. Let’s start with some terminology expressions that will be used in the following sections:

  • All real DOM nodes, such as element and text nodes, start with $; $parent, for example, is a real DOM element

  • All Virtual DOM will be represented by the node variable

  • Like React, only one root node can exist, and all other nodes are contained within that root node

The createElement function (props and children) is used to convert the dummy DOM to a real DOM.

Function createElement(node) {if (Typeof Node === 'string') {return document.createTextNode(node); } return document.createElement(node.type); }Copy the code

Since we need to take into account the need to process both text nodes and element nodes, we do a simple branching judgment. This is the simplest implementation. Now we need to consider how to render the child elements. The child nodes of each node may be text nodes or element nodes, in other words, we work our way up the tree of virtual nodes from the root node to the leaf node, essentially constructing it iteratively and then mounting the resulting child node to the parent node with appendChild(). The resulting function looks something like this:

Function createElement(node) {if (Typeof Node === 'string') {return document.createTextNode(node); } const $el = document.createElement(node.type); node.children .map(createElement) .forEach($el.appendChild.bind($el)); return $el; }Copy the code

The JSFiddle debugging for this section is here, and the complete JSX code is:

/** @jsx h */ function h(type, props, ... children) { return { type, props, children }; } function createElement(node) { if (typeof node === 'string') { return document.createTextNode(node); } const $el = document.createElement(node.type); node.children .map(createElement) .forEach($el.appendChild.bind($el)); return $el; } const a = (
       
    
    
        
  • item 1
    • 
    
        
  • item 2
    • 
  
       

);

const $root = document.getElementById('root');
$root.appendChild(createElement(a));Copy the code

Now that we have successfully converted the Virtual DOM into a real DOM node, it is time to consider the algorithm at the heart of the Virtual DOM, namely difference detection. Let’s start by writing a simple Virtual DOM comparison algorithm that guarantees minimal changes to real DOM nodes. First, let’s take a look at a few possible scenarios:

(1) Add some nodes and call appendChild()

(2) Some nodes need to be removed by calling removeChild()

(3) Some nodes become other nodes and need to call replaceChild() to replace them

(4) The label of a node changes or is mounted to another place

In each case, we use the updateElement() function to update the DOM tree, which takes three arguments:

  • $parent represents the root node of the DOM tree where the Virtual DOM is mounted

  • NewNode New Virtual DOM

  • OldNode Old Virtual DOM

There are no old Virtual DOM cases at initialization

If oldNode is empty, we can simply create a new node:


function updateElement($parent, newNode, oldNode) {

  if (!oldNode) {

    $parent.appendChild(

      createElement(newNode)

    );

  }

}
Copy the code

The entire newNode is null, that is, removed from the DOM tree

If newNode is empty, that is, no nodes are mounted on the entire VirtualDOM tree, then we need to remove the node tree corresponding to VirtualDOM from the DOM. The easiest way to do this is to call $parent.removechild () and pass in a reference to the entire real DOM element. In reality, however, we only have the Virtual DOM in memory and no references to the real DOM. If we know how many children the Virtual DOM corresponds to in the real DOM, we can delete them according to the subscript, something like this:

function updateElement($parent, newNode, oldNode, index = 0) { if (! oldNode) { $parent.appendChild( createElement(newNode) ); } else if (! newNode) { $parent.removeChild( $parent.childNodes[index] ); }}Copy the code

The node has changed

First, we need to write a simple comparison equation to compare whether two virtual nodes have changed. Similar to the function for creating elements, we also need to consider text nodes and element nodes:

function changed(node1, node2) { return typeof node1 ! = = typeof 2 | | typeof node1 = = = 'string' && node1! == node2 || node1.type ! == node2.type }Copy the code

With this comparison function and the ordinal number of the real DOM in the parent node of the current Virtual DOM map, we can refine the update function to look like this:

function updateElement($parent, newNode, oldNode, index = 0) { if (! oldNode) { $parent.appendChild( createElement(newNode) ); } else if (! newNode) { $parent.removeChild( $parent.childNodes[index] ); } else if (changed(newNode, oldNode)) { $parent.replaceChild( createElement(newNode), $parent.childNodes[index] ); }}Copy the code

Note that the above comparison function only considers changes in the root node of the Virtual DOM when the node changes. The comparison method is also used to directly compare whether the memory address is a new object, which can be seen from the significance of Immutable.

Diff children

The algorithm mentioned above does not check the child node. In practice, we not only check the root node, but also recursively check if the child node has changed. That is, recursively find the node that has changed.

  • Child node comparison is required only for element nodes; text nodes do not have child nodes

  • During recursion, the current node is passed in as the root node for child node comparison

  • Index is the index of the child node in the parent node


function updateElement($parent, newNode, oldNode, index = 0) {

  if (!oldNode) {

    $parent.appendChild(

      createElement(newNode)

    );

  } else if (!newNode) {

    $parent.removeChild(

      $parent.childNodes[index]

    );

  } else if (changed(newNode, oldNode)) {

    $parent.replaceChild(

      createElement(newNode),

      $parent.childNodes[index]

    );

  } else if (newNode.type) {

    const newLength = newNode.children.length;

    const oldLength = oldNode.children.length;

    for (let i = 0; i < newLength || i < oldLength; i++) {

      updateElement(

        $parent.childNodes[index],

        newNode.children[i],

        oldNode.children[i],

        i

      );

    }

  }

}
Copy the code

The debugging address for the final code is JSFiddle, which gives the following effect:

At this point, we have completed a simple Virtual DOM algorithm, but it is still a long way from the actual Virtual DOM algorithm.

  • In-depth analysis: How to implement a Virtual DOM algorithm

  • My front-end story —-React algorithm is a ghost? !

  • A Virtual DOM and Diffing algorithm: A more complex implementation of Virtual DOM algorithm

  • Simple-virtual-dom: A simple virtual DOM implementation

  • how-to-write-your-own-virtual-dom

  • Virtual DOM Benchmark