At the end of the flowchart in React Source Analysis – Component Updates and Transactions:

The blue boxes are the core code of the Diff algorithm, updateChildren and processUpdates. The Diff algorithm obtains the updates queue of the component and then updates it once.

The code for the Diff algorithm (the main steps of the algorithm will be explained below) :

    _updateChildren: function (nextNestedChildrenElements, transaction, context) {
      var prevChildren = this._renderedChildren;
      var removedNodes = {};
      var nextChildren = this._reconcilerUpdateChildren(prevChildren, nextNestedChildrenElements, removedNodes, transaction, context);
      if(! nextChildren && ! prevChildren) {return;
      }
      var updates = null;
      var name;
      var lastIndex = 0;
      var nextIndex = 0;
      var lastPlacedNode = null;
      for (name in nextChildren) {
        if(! nextChildren.hasOwnProperty(name)) {continue;
        }
        var prevChild = prevChildren && prevChildren[name];
        var nextChild = nextChildren[name];
        if (prevChild === nextChild) {
          updates = enqueue(updates, this.moveChild(prevChild, lastPlacedNode, nextIndex, lastIndex));
          lastIndex = Math.max(prevChild._mountIndex, lastIndex);
          prevChild._mountIndex = nextIndex;
        } else {
          if (prevChild) {
            lastIndex = Math.max(prevChild._mountIndex, lastIndex);
          }
          updates = enqueue(updates, this._mountChildAtIndex(nextChild, lastPlacedNode, nextIndex, transaction, context));
        }
        nextIndex++;
        lastPlacedNode = ReactReconciler.getNativeNode(nextChild);
      }
      for (name in removedNodes) {
        if (removedNodes.hasOwnProperty(name)) {
          updates = enqueue(updates, this._unmountChild(prevChildren[name], removedNodes[name])); }}if (updates) {
        processQueue(this, updates);
      }
      this._renderedChildren = nextChildren;
    }
Copy the code

The Diff algorithm is well explained in Inside the React Stack. It’s just a matter of keeping a few principles in mind and the points that the algorithm optimizes when calculating the Updates queue.

The complexity of the traditional diff algorithm is O(n^3). For details, see “A Survey on Tree Edit Distance and Related Problems”.

This kind of complexity would explode in practice, and even though today’s computers have powerful cpus, a page can’t be so arbitrary.

React made reasonable assumptions and methods to simplify the whole diff process.

  • Scenarios where DOM nodes move across hierarchies are rare and can be ignored. (Reasonable, through the design of the component to ensure the DOM structure as stable as possible, if necessary, through the METHOD of CSS DOM display adjustment, because the creation, deletion and movement of the DOM is as little as possible, each DOM node of the browser is a large object, with many methods and attributes)
  • Two components of the same class will generate similar tree structures, and two components of different classes will generate different tree structures. (Reasonable, the component itself has the function of improving page reusability, that is, abstracting the page structure with similar structure and function (or similar DOM tree structure) into a class of components, so reasonable component abstraction should satisfy this assumption.)
  • A group of nodes at the same level can be distinguished by setting a unique key, so as to further optimize diff. (This is not a hypothesis but a way to improve performance)
  • It is possible for two components of the same class to remain unchanged in their Virtual Dom. React therefore allows developers to determine if a component needs diff analysis via shouldComponentUpdate(). ShouldComponentUpdate () : shouldComponentUpdate() : shouldComponentUpdate() : shouldComponentUpdate() : shouldComponentUpdate() : shouldComponentUpdate() : shouldComponentUpdate() : shouldComponentUpdate() : shouldComponentUpdate() : shouldComponentUpdate() : shouldComponentUpdate( But this is the sei. , writing a bug is not honest)

Based on the above items, React only compares nodes at the same level between old and new trees in the specific Diff process. There are three operations on a node: insert, move, and delete.

The procedure for determining node movement operations is as follows:

If (prevChild === nextChild); if (prevChild === nextChild); if (prevChild == nextChild); if (prevChild === nextChild); If (child._mountIndex < lastIndex), the node will be moved. Otherwise, the node will not be moved. This is a sequential optimization method. LastIndex is constantly updated, indicating that the visited node is at the right-most position (i.e., the largest position) in the old set. If the currently visited node in the new set is larger than lastIndex, it means that the currently visited node is lower in the old set than the last node. This node does not affect the position of other nodes, so it does not need to be added to the difference queue, that is, it does not need to be moved. Only when the accessed node is smaller than lastIndex, it needs to be moved.

If the current accessed node in the new set is larger than lastIndex, it means that the current accessed node in the old set is lower than the previous node. This node does not affect the position of other nodes, so it is not added to the difference queue, that is, no move operation is performed. This means that if a node’s position in the old set is already behind the last node you checked, then that node is already behind the previous diff node in the correct order and does not need to be moved, and the other node needs to be moved.

Another thing to remember is that if you don’t assign a key, React will default to the index value in the loop. The index value here refers to the sequence number of the node traversal, which is equivalent to some people using the index of the list array as the key. This is actually bad, because the key of the node depends on the position of the node and not on the node itself, so if I have a list of 10 nodes, and THE key is 1 to 10 in traversal order, and THEN I add a node at the beginning of the list, and I set the key in the order that the list is traversed, The keys of the original 10 nodes are changed, and the keys of the old and new nodes are incorrectly matched. Remember that when a key is used in React, it indicates the identity of a component. Incorrect or duplicate keys may cause React errors…… so……. A key needs to be a unique identifier associated with the node itself.

Here’s Paul O ‘Shannessy, one of the authors of React:

Key is not really about performance, 1. It’s more about identity (which in turn leads to better performance) an identity

The key of each component becomes the name of the nextChildren&prevChildren object and the value of the name is Component, In the key of the shouldUpdateReactComponent components in the _reconcilerUpdateChildren also has to use.

The operation of adding and deleting nodes is simple as follows:

  • To add a new node, you create a new node and place it in the same position that you traversed in order.
  • To delete the node, the old set is cyclically traversed after the traversal at this level to determine whether there is no node in the new set. If there is no node in the new set, the node is deleted.

Of course, moving, adding, and deleting nodes are not performed immediately, but rather are collected into the Updates array and then updated to the DOM in one go using the processUpdates method.

  processUpdates: function (parentNode, updates) {
    for (var k = 0; k < updates.length; k++) {
      var update = updates[k];
      switch (update.type) {
        case ReactMultiChildUpdateTypes.INSERT_MARKUP:
          insertLazyTreeChildAt(parentNode, update.content, getNodeAfter(parentNode, update.afterNode));
          break;
        case ReactMultiChildUpdateTypes.MOVE_EXISTING:
          moveChild(parentNode, update.fromNode, getNodeAfter(parentNode, update.afterNode));
          break;
        case ReactMultiChildUpdateTypes.SET_MARKUP:
          setInnerHTML(parentNode, update.content);
          break;
        case ReactMultiChildUpdateTypes.TEXT_CONTENT:
          setTextContent(parentNode, update.content);
          break;
        case ReactMultiChildUpdateTypes.REMOVE_NODE:
          removeChild(parentNode, update.fromNode);
          break; }}}Copy the code

The specific operation of the node is the node operation of the specific browser DOM, for example.

function insertLazyTreeChildAt(parentNode, childTree, referenceNode) {
  DOMLazyTree.insertTreeBefore(parentNode, childTree, referenceNode);
}

var insertTreeBefore = createMicrosoftUnsafeLocalFunction(function (parentNode, tree, referenceNode) {
  if (tree.node.nodeType === 11) {
    insertTreeChildren(tree);
    parentNode.insertBefore(tree.node, referenceNode);
  } else{ parentNode.insertBefore(tree.node, referenceNode); insertTreeChildren(tree); }});Copy the code

Node.insertbefore () is the browser’S DOM manipulation API.

To follow the Diff process, step debugging is recommended or look at chestnuts in Deep React Stack. I won’t draw….. here Drawing is very tired….. There are a lot of similar ones on the Internet.

The specific use of key in this paper needs to be further studied. “TBD”

References:

  • React Diff – React Diff
  • Dive into the React technology stack