React series

React Simple Analog Grammar (I)
Jsx, Composite Events and Refs (II)

The complete code is available for viewing virtualdom-diff

Rendering DOM

Anyone who has experienced PHP template development or JQuery's baptism knows that the simplest and crudest way to render them is to rebuild DOM to replace old DOM, and the problem is obvious.

• High performance consumption
• Unable to save state (focus, scroll, etc.)

Let's first see how many instance attributes are contained in creating an element.

const div = document.createElement('div');
let num = 0;
for (let k in div) {
  num++;
}
console.log(num); // 241

Then the browser searches the matching nodes according to the CSS rules, calculates the merge style layout, in order to avoid recalculating the general browser will save these data. But this is the whole process still consumes a lot of memory and CPU resources.

Virtual DOM

Actually, it also operates on the Dom tree for rendering and updating, but it only performs partial rendering for the modified part, which minimizes the impact. Although the implementation methods are different, the general steps are as follows:

1. Describe the Dom tree structure with Javascript object structure, and then use it to build a real Dom tree to insert documents
2. When the state changes, reconstruct the new Javascript object structure and compare it with the old one.
3. Reconstruct updated views for differences

It's just using Js to do a layer mapping comparison, which is easy to operate and much faster than the direct comparison Dom tree.

Basic Tool Functions

It's just a simplified function of type judgment and cyclic traversal.

function type(obj) {
  return Object.prototype.toString.call(obj).replace(/\[object\s|\]/g, "");
}

function isArray(list) {
  return type(list) === "Array";
}

function isObject(obj) {
  return type(obj) === "Object";
}

function isString(str) {
  return type(str) === "String";
}

function isNotEmptyObj(obj) {
  return isObject(obj) && JSON.stringify(obj) != "{}";
}

function objForEach(obj, fn) {
  isNotEmptyObj(obj) && Object.keys(obj).forEach(fn);
}

function aryForEach(ary, fn) {
  ary.length && ary.forEach(fn);
}

function setAttr(node, key, value) {
  switch (key) {
    case "style":
      node.style.cssText = value;
      break;
    case "value":
      var tagName = node.tagName || "";
      tagName = tagName.toLowerCase();
      if (tagName === "input" || tagName === "textarea") {
        node.value = value;
      } else {
        // if it is not a input or textarea, use `setAttribute` to set
        node.setAttribute(key, value);
      }
      break;
    default:
      node.setAttribute(key, value);
      break;
  }
}

function toArray(data) {
  if (!data) {
    return [];
  }
  const ary = [];
  aryForEach(data, item => {
    ary.push(item);
  });

  return ary;
}

export {
  isArray,
  isObject,
  isString,
  isNotEmptyObj,
  objForEach,
  aryForEach,
  setAttr,
  toArray
};

Related code can be viewed util.js

Javascript Object Structure Description

I used this example before when I talked about JSX, and then we can use this to achieve the effect.

<div className="num" index={1}>
  <span>123456</span>
</div>

"use strict";

React.createElement("div", {
  className: "num",
  index: 1
}, React.createElement("span", null, "123456"));

Create an Element class responsible for converting Javascript object structure to Dom tree structure

import {
  isObject,
  isString,
  isArray,
  isNotEmptyObj,
  objForEach,
  aryForEach
} from "./util";
import { NOKEY } from "./common";

class Element {
  constructor(tagName, props, children) {
    // Analytical parameters
    this.tagName = tagName;
    // Field processing, omitting parameters
    this.props = isObject(props) ? props : {};
    this.children =
      children ||
      (!isNotEmptyObj(this.props) &&
        ((isString(props) && [props]) || (isArray(props) && props))) ||
      [];
    // Whatever the expression after void is, the void operator returns undefined
    this.key = props ? props.key : void NOKEY;

    // Calculate the number of nodes
    let count = 0;
    aryForEach(this.children, (item, index) => {
      if (item instanceof Element) {
        count += item.count;
      } else {
        this.children[index] = "" + item;
      }
      count++;
    });
    this.count = count;
  }

  render() {
    // Construction based on tagName
    const dom = document.createElement(this.tagName);

    // Setting up props
    objForEach(this.props, propName =>
      dom.setAttribute(propName, this.props[propName])
    );

    // Rendering children
    aryForEach(this.children, child => {
      const childDom =
        child instanceof Element
          ? child.render() // If the child node is also a virtual DOM, the DOM node is constructed recursively
          : document.createTextNode(child); // If the string, only the text node is constructed
      dom.appendChild(childDom);
    });
    return dom;
  }
}

// Change the way of parameter transfer, avoid manual instantiation
export default function CreateElement(tagName, props, children) {
  return new Element( tagName, props, children );
}

New example, invoked as follows

// 1. Building Virtual DOM
const tree = createElement("div", { id: "root" }, [
  createElement("h1", { style: "color: blue" }, ["Tittle1"]),
  createElement("p", ["Hello, virtual-dom"]),
  createElement("ul", [
    createElement("li", { key: 1 }, ["li1"]),
    createElement("li", { key: 2 }, ["li2"]),
    createElement("li", { key: 3 }, ["li3"]),
    createElement("li", { key: 4 }, ["li4"])
  ])
]);

// 2. Building Real DOM through Virtual DOM
const root = tree.render();
document.body.appendChild(root);

After running, we can get the result normally, so the first step is finished. There are more different types of tags, and the corresponding event state is skipped first.

The interface is shown in the figure.

The Javascript structure is shown in Figure 1

The structural prototype is as follows

Related code can be viewed element.js

diff algorithm

This is the most critical step in the whole implementation, because it determines the speed of computation and the number of Dom s to operate on.

Let's create a new Dom tree for comparison

// 3. Generating a new virtual DOM
const newTree = createElement("div", { id: "container" }, [
  createElement("h1", { style: "color: red" }, ["Title2"]),
  createElement("h3", ["Hello, virtual-dom"]),
  createElement("ul", [
    createElement("li", { key: 3 }, ["li3"]),
    createElement("li", { key: 1 }, ["li1"]),
    createElement("li", { key: 2 }, ["li2"]),
    createElement("li", { key: 5 }, ["li5"])
  ])
]);

The Javascript structure is shown in Figure 1

tree diff

The complexity of traditional diff algorithm is O(n^3), but it is very rare for Dom to cross-level. So React only compares Dom nodes at the same level and converts the problem of O(n^3) complexity into that of O(n) complexity.

The big problem is that when a node moves across the hierarchy, it does not move but directly replaces the entire node, so keep in mind this performance problem.

component diff

• Change in a component will result in a top-down replacement of the component as a whole
• Virtual DOM comparisons are made between components of the same type
• React provides a shouldComponentUpdate to decide whether to update

Migrating dynamic components to underlying nodes as much as possible can improve performance

element diff

Element operations are just a few. We define several types as state markers.

const REPLACE = "replace";
const REORDER = "reorder";
const PROPS = "props";
const TEXT = "text";
const NOKEY = "no_key"

export {
  REPLACE,
  REORDER,
  PROPS,
  TEXT,
  NOKEY
}

Among them, NOKEY is the default for those components that do not define keys. React adds unique keys to distinguish the same group of sub-nodes at the same level and displaces them instead of replacing them directly. This is especially critical for overall performance.

Let's first differentiate between different types.

import { isString, objForEach, aryForEach, isNotEmptyObj } from "./util";
import { REPLACE, REORDER, PROPS, TEXT } from "./common";
import listDiff from "list-diff2";

/**
 *
 * @param {Old Dom Tree} oTree
 * @param {New Dom Tree} nTree
 * Returns the difference record
 */
function diff(oTree, nTree) {
  // Node Location
  let index = 0;
  // Difference record
  const patches = {};
  dfsWalk(oTree, nTree, index, patches);
  return patches;
}

function dfsWalk(oNode, nNode, index, patches) {
  const currentPatch = [];

  // First render
  if (nNode === null) return;

  // They are all in string form and do not replace text directly.
  if (isString(oNode) && isString(nNode)) {
    oNode !== nNode &&
      currentPatch.push({
        type: TEXT,
        content: nNode
      });
    // Same label and same key
  } else if (oNode.tagName === nNode.tagName && oNode.key === nNode.key) {
    // At least one party is worth it
    if (isNotEmptyObj(oNode.props) || isNotEmptyObj(nNode.props)) {
      // Computation of props results
      const propsPatches = diffProps(oNode, nNode);
      // If there are differences, reorder
      propsPatches &&
        currentPatch.push({
          type: PROPS,
          props: propsPatches
        });
    }
    // children comparison
    if (
      !(!isNotEmptyObj(nNode.props) && nNode.props.hasOwnProperty("ignore"))
    ) {
      (oNode.children.length || nNode.children.length) &&
        diffChildren(
          oNode.children,
          nNode.children,
          index,
          patches,
          currentPatch
        );
    }
  } else {
    // If they don't meet the above requirements, they should be replaced directly.
    currentPatch.push({ type: REPLACE, node: nNode });
  }

  // Final comparison results
  currentPatch.length && (patches[index] = currentPatch);
}

Comparison of props attributes between old and new nodes

/**
 *
 * @param {Old node} oNode
 * @param {New Node} nNode
 */
function diffProps(oNode, nNode) {
  let isChange = false;
  const oProps = oNode.props;
  const nProps = nNode.props;
  // Node attribute record
  const propsPatched = {};

  // Replace/add attributes
  objForEach(oProps, key => {
    if (nProps[key] !== oProps[key] || !oProps.hasOwnProperty(key)) {
      !isChange && (isChange = true);
      propsPatched[key] = nProps[key];
    }
  });

  return !isChange ? null : propsPatched;
}

Contrast of child elements between old and new nodes

/**
 *  Peer comparison
 * @param {*} oChildren
 * @param {*} nChildren
 * @param {*} index
 * @param {*} patches
 * @param {*} currentPatch
 */
function diffChildren(oChildren, nChildren, index, patches, currentPatch) {
  // Relatively Simplified Moving Path
  const diffs = listDiff(oChildren, nChildren, "key");

  // Retention element
  nChildren = diffs.children;

  // Record sort displacement
  diffs.moves.length &&
    currentPatch.push({ type: REORDER, moves: diffs.moves });

  // depth-first traversal
  let leftNode = null;
  let currentNodeIndex = index;
  aryForEach(oChildren, (_item, _index) => {
    const nChild = nChildren[_index];
    currentNodeIndex =
      leftNode && leftNode.count
        ? currentNodeIndex + leftNode.count + 1
        : currentNodeIndex + 1;
    _item !== nChild && dfsWalk(_item, nChild, currentNodeIndex, patches);
    leftNode = _item;
  });
}

The prototype of depth traversal is as follows

listDiff comes from list-diff The minimum amount of movement can be obtained through key attributes. moves is a paving instruction for the third step of updating the view. The official description is as follows

Diff two lists in time O(n). I The algorithm finding the minimal amount of moves is Levenshtein distance which is O(n*m). This algorithm is not the best but is enougth for front-end DOM list manipulation.

This project is mostly influenced by virtual-dom algorithm.

Call comparison

// 4. Compare the differences between two virtual DOM trees
const patches = diff(tree, newTree);

The differences are as follows.

Related code can be viewed diff.js

update the view

Deep traversal

import {
  isString,
  isObject,
  objForEach,
  aryForEach,
  setAttr,
  toArray
} from "./util";
import { REPLACE, REORDER, PROPS, TEXT, NOKEY } from "./common";

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

// Deep traversal update
function dfsWalk(node, walker, patches) {
  const currentPatches = patches[walker.index];

  node.childNodes &&
    aryForEach(node.childNodes, item => {
      walker.index++;
      dfsWalk(item, walker, patches);
    });

  currentPatches && applyPatches(node, currentPatches);
}

Corresponding Processing for Different Signs

// Update type
function applyPatches(node, currentPatches) {
  aryForEach(currentPatches, item => {
    switch (item.type) {
      case REPLACE:
        const nNode = isString(item.node)
          ? document.createTextNode(item.node)
          : item.node.render();
        node.parentNode.replaceChild(nNode, node);
        break;
      case REORDER:
        reorderChildren(node, item.moves);
        break;
      case PROPS:
        setProps(node, item.props);
        break;
      case TEXT:
        if (node.textContent) {
          // Use plain text
          node.textContent = item.content;
        } else {
          // Only valid for CDATA fragments, comment, Processing Instruction nodes, or text nodes
          node.nodeValue = item.content;
        }
        break;
      default:
        throw new Error("Unknown patch type " + item.type);
    }
  });
}

Let's start with simple attribute substitution

// modify attribute
function setProps(node, props) {
  objForEach(props, key => {
    if (props[key] === void NOKEY) {
      node.removeAttribute(key);
    } else {
      setAttr(node, key, props[key]);
    }
  });
}

Finally, list rendering

// List sort rendering
function reorderChildren(node, moves) {
  const staticNodeList = toArray(node.childNodes);
  const maps = {};

  aryForEach(staticNodeList, node => {
    // Element
    if (node.nodeType === 1) {
      const key = node.getAttribute("key");
      key && (maps[key] = node);
    }
  });

  aryForEach(moves, move => {
    const index = move.index;
    // 0: Delete 1: Replace
    if (move.type === 0) {
      // Find the corresponding node to delete
      staticNodeList[index] === node.childNodes[index] &&
        node.removeChild(node.childNodes[index]);
      staticNodeList.splice(index, 1);
    } else if (move.type === 1) {
      let insertNode;
      if (maps[move.item.key]) {
        // Delete and return nodes
        insertNode = node.removeChild(maps[move.item.key]);
        // Get the delete node location
        staticNodeList.splice(Array.prototype.indexOf.call(node.childNodes, maps[move.item.key]), 1);
      } else {
        // Create Nodes
        insertNode = isObject(move.item)
          ? move.item.render()
          : document.createTextNode(move.item);
      }
      // Synchronize staticNodeList information
      staticNodeList.splice(index, 0, insertNode);
      // Operating Dom
      node.insertBefore(insertNode, node.childNodes[index] || null);
    }
  });
}

export default patch;

When this step is completed, we can directly apply the view effect.

// 4. Compare the differences between two virtual DOM trees
const patches = diff(tree, newTree);

// 5. Apply changes to real DOM elements
patch(root, patches);

The result is shown in the figure.

Related code can be viewed patch.js

Reference resources

Deep Analysis: How to Implement a Virtual DOM Algorithms