React principle: Reconcile (Diff) algorithm

After explaining how functional and class components compute state updates, this article will cover the reconcile process, known as the Diff algorithm.

Reconcile is the process for building the workInProgress tree

The diff entry for the class component is in finishClassComponent

function finishClassComponent(current, workInProgress, Component, shouldUpdate, hasContext, renderLanes) {
  markRef(current, workInProgress);
  vardidCaptureError = (workInProgress.flags & DidCapture) ! == NoFlags;if(! shouldUpdate && ! didCaptureError) {// The component should be updated according to the shouldComponentUpdate lifecycle
    if (hasContext) {
      invalidateContextProvider(workInProgress, Component, false);
    }

    return bailoutOnAlreadyFinishedWork(current, workInProgress, renderLanes);
  }

  var instance = workInProgress.stateNode;

  ReactCurrentOwner$1.current = workInProgress;
  var nextChildren;

  if (didCaptureError && typeofComponent.getDerivedStateFromError ! = ='function') {
    // An error occurred
    nextChildren = null; { stopProfilerTimerIfRunning(); }}else {
    {
      setIsRendering(true);
      // Execute the render method
      nextChildren = instance.render();
      if ( workInProgress.mode & StrictMode) {
        // Strict mode
        disableLogs();
        try {
          instance.render();
        } finally {
          reenableLogs();
        }
      }
      setIsRendering(false);
    }
  }

  workInProgress.flags |= PerformedWork;

  if(current ! = =null && didCaptureError) {
    forceUnmountCurrentAndReconcile(current, workInProgress, nextChildren, renderLanes);
  } else {
    // The entry of diff
    reconcileChildren(current, workInProgress, nextChildren, renderLanes);
  }

  workInProgress.memoizedState = instance.state;

  if (hasContext) {
    invalidateContextProvider(workInProgress, Component, true);
  }

  return workInProgress.child;
}
Copy the code

For function components, it calls reconcileChildren to enter diff in updateFunctionComponent, after renderWithHooks

The entry function

The reconcileChildren method is defined as follows:

function reconcileChildren(current, workInProgress, nextChildren, renderLanes) {
  if (current === null) {
    workInProgress.child = mountChildFibers(workInProgress, null, nextChildren, renderLanes);
  } else{ workInProgress.child = reconcileChildFibers(workInProgress, current.child, nextChildren, renderLanes); }}Copy the code

The mountChildFibers method is executed when the component is first loaded, and the reconcileChildFibers method is executed when it is updated, which are defined as follows:

var reconcileChildFibers = ChildReconciler(true);
var mountChildFibers = ChildReconciler(false);
Copy the code

Then look at ChildReconciler

function ChildReconciler(shouldTrackSideEffects) {
    // ... 
    return reconcileChildFibers
}
Copy the code

ShouldTrackSideEffects says whether there are side effects. When the component is first mounted, there are obviously no side effects. Component updates may involve element deletion, insertion, etc., so shouldTrackSideEffects should be true. Next, look at the return value of this method: reconcileChildFibers

function reconcileChildFibers(returnFiber, currentFirstChild, newChild, lanes) {
    var isUnkeyedTopLevelFragment = typeof newChild === 'object'&& newChild ! = =null && newChild.type === REACT_FRAGMENT_TYPE && newChild.key === null;

    if (isUnkeyedTopLevelFragment) {
      newChild = newChild.props.children;
    }

    var isObject = typeof newChild === 'object'&& newChild ! = =null;

    if (isObject) {
      switch (newChild.$$typeof) {
        case REACT_ELEMENT_TYPE:
          return placeSingleChild(reconcileSingleElement(returnFiber, currentFirstChild, newChild, lanes));
      }
        // ...
    }
    
    // ...

    if (isArray$1(newChild)) {
      return reconcileChildrenArray(returnFiber, currentFirstChild, newChild, lanes);
    }
    // ...
}
Copy the code

This method diff depending on the node type: for example, it executes reconcileSingleElement for a single React element, and reconcileChildrenArray for multiple elements. This is also known as single-node diFF and multi-node DIFF, which will be analyzed below. Before we go back to analyzing it, let’s look at the parameters for reconcileChildFibers:

Diff algorithm objects: the old fiber tree and the JSX returned by the Render method

< span style = “color: RGB (0, 0, 0); color: RGB (0, 0);

Single node diff

Single-node DIFF refers to the DIFF process when the new node is a single node. There are three possible scenarios for single-node DIff:

1. The oldfiberIs empty
2. The oldfiberThere’s a node
3. The oldfiberThere are multiple nodes

Single-node DIFF is easy. You just need to find a node in the old fiber that has the same key and type as the new JSX node, and then delete the remaining old nodes. If not, delete all old nodes and create new ones.

  function reconcileSingleElement(returnFiber, currentFirstChild, element, lanes) {
    var key = element.key;
    var child = currentFirstChild;
    // Loop through all the old fiber nodes in currentFirstChild layer
    while(child ! = =null) {
      if (child.key === key) {
        switch (child.tag) {
          // ...
          default:
            {
              if (child.elementType === element.type || (
               isCompatibleFamilyForHotReloading(child, element) )) {
                // Since the diff node is a single node, delete all the remaining nodes after finding the node with the same key and type
                deleteRemainingChildren(returnFiber, child.sibling);
		// Create a new fiber from the old fiber
                var _existing3 = useFiber(child, element.props);
                _existing3.ref = coerceRef(returnFiber, child, element);
                _existing3.return = returnFiber;
		/ /...
                // Return a new fiber when a node with the same key and type is found
                return _existing3;
              }
              break; }}// The key is the same, but the type is different
        deleteRemainingChildren(returnFiber, child);
        break;
      } else {
        // If the key is different, delete the old fiber
        deleteChild(returnFiber, child);
      }
      child = child.sibling;
    }
    // Create a new fiber based on JSX when no node with the same key and type is found
    if (element.type === REACT_FRAGMENT_TYPE) {
      var created = createFiberFromFragment(element.props.children, returnFiber.mode, lanes, element.key);
      created.return = returnFiber;
      return created;
    } else {
      var _created4 = createFiberFromElement(element, returnFiber.mode, lanes);

      _created4.ref = coerceRef(returnFiber, currentFirstChild, element);
      _created4.return = returnFiber;
      return_created4; }}Copy the code

A few points to note here:

1. In deleteChild (deleteRemainingChildren, deleteChild is also called within deleteRemainingChildren), a Deletion tag is placed on the fiber to indicate that the old node is being deleted (note that the node is not actually deleted, but tagged).

2. If the node to be deleted has child nodes, only the node to be deleted is tagged

3. When a reusable fiber node (with the same key and type) is found, a new fiber node is created and the alternate property is set between the new fiber node and the old one. However, when multiplexing is not possible, the alternate connection between the old and new fibers does not exist.

4. As you may have noticed, since the old fiber is tagged with Deletion tag, what about the new fiber node? Notice that reconcileChildFibers have this code:

   return placeSingleChild(reconcileSingleElement(returnFiber, currentFirstChild, newChild, lanes));
   Copy the code

   The new node is tagged with Placement only in the placeSingleChild method

Fiber reuse: Instead of using the old fiber object directly, we create a new fiber object in the workInProgress tree, and the properties in the new object are changed to the properties in the new JSX. Fiber is reused only if the key and type are the same. When fiber multiplexing occurs, alternate connections are used between old and new fiber nodes. When fiber multiplexing does not occur, there is no mutual reference between old and new fibers. This is very important.

Multi-node diff

After looking at single-node DIff, take a look at multi-node DIff. Back to the reconcileChildFibers method, there’s a special treatment here

function reconcileChildFibers(returnFiber, currentFirstChild, newChild, lanes) {
    var isUnkeyedTopLevelFragment = typeof newChild === 'object'&& newChild ! = =null && newChild.type === REACT_FRAGMENT_TYPE && newChild.key === null;
    // If the new JSX node is a Fragment node without a key, fetch its children
    if (isUnkeyedTopLevelFragment) {
      newChild = newChild.props.children;
    }
    // Multinode diff
    if (isArray$1(newChild)) {
      returnreconcileChildrenArray(returnFiber, currentFirstChild, newChild, lanes); }}Copy the code

As you can see, multi-node DIFF is the new JSX DIFF policy when there are multiple nodes.

First of all, React’s DIFF strategy is not to reuse nodes at any cost, but to reuse nodes on the basis of guaranteed efficiency. For example, when a component is moved across a hierarchy, even though it is only in position, React does not reuse the node. This is also discussed in many articles, so I will not expand it. Let’s look at react’s multi-node DIff strategy.

< span style = “color: RGB (0, 0, 0); color: RGB (0, 0);

First, a couple of variables

var resultingFirstChild = null;   // The first fiber node in the new fiber list

var newIdx = 0;                   // To loop through a pointer in the new JSX array
var previousNewFiber = null;      // In the new fiber list, select the fiber before the current one

var oldFiber = currentFirstChild; // The pointer used to loop the old fiber node
var nextOldFiber = null;          // In the old fiber list, the next fiber from the current fiber list

// The right most fiber node in the old fiber tree does not need to be moved. The position of the fiber node in the old fiber tree is described below
var lastPlacedIndex = 0;          
Copy the code

The first part

Let’s start with the first part of multi-node DIFF: the loop for node updates

// Loop the new fiber and the old fiber
for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
  if (oldFiber.index > newIdx) {
    nextOldFiber = oldFiber;
    oldFiber = null;
  } else {
    nextOldFiber = oldFiber.sibling;
  }
  // Update the fiber node
  // If the new JSX returns null, or if the new and old fiber have different keys, updateSlot returns null
  // If the new fiber has the same key, but the type is different, or if the old fiber does not exist, then the fiber cannot be reused.
  // If both old and new fibers exist and can be reused, then reuse fiber
  var newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx], lanes);
  // If newFiber is null, jump out of the loop
  if (newFiber === null) {
    if (oldFiber === null) {
      oldFiber = nextOldFiber;
    }
    break;
  }
  // Component update, shouldTrackSideEffects is true
  // The component mounts, shouldTrackSideEffects is false, as mentioned earlier
  if (shouldTrackSideEffects) {
    // If there is no fiber multiplexing, the old fiber is deleted
    if (oldFiber && newFiber.alternate === null) { deleteChild(returnFiber, oldFiber); }}// Determine the location of the new fiber. The placeChild method is covered separately below
  lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
  // Record the first node in the new fiber
  if (previousNewFiber === null) {
    resultingFirstChild = newFiber;
  } else {
    previousNewFiber.sibling = newFiber;
  }
  previousNewFiber = newFiber;
  oldFiber = nextOldFiber;
}
Copy the code

As you can see, the loop only breaks in the middle if the new JSX returns null, or if the new and old fiber have different keys. If you break out of the loop, you skip parts 2 and 3 and go straight to part 4

The second part

If the loop ends normally and there is no break, the second part is entered:

// If the new fiber is traversed, delete the remaining nodes in the old fiber and return resultingFirstChild
if (newIdx === newChildren.length) {
  deleteRemainingChildren(returnFiber, oldFiber);
  return resultingFirstChild;
}
Copy the code

The third part

Here’s part three:

// If the traversal of the old fiber is complete, the remaining new fiber is a new node
if (oldFiber === null) {
  for (; newIdx < newChildren.length; newIdx++) {
    var _newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
    if (_newFiber === null) {
      continue;
    }
    // Place the new node
    lastPlacedIndex = placeChild(_newFiber, lastPlacedIndex, newIdx);
    if (previousNewFiber === null) {
      resultingFirstChild = _newFiber;
    } else {
      previousNewFiber.sibling = _newFiber;
    }
    previousNewFiber = _newFiber;
  }
  return resultingFirstChild;
}
Copy the code

Note here that if the first part of the loop exits in the middle of the loop, both old and new fibers will not complete the loop, so instead of going to the second and third parts, they will go directly to the fourth part.

The fourth part

// Put the remaining nodes in the old fiber list into a map. The key is the key of the fiber list or the index of the position in the old fiber list, and the value is the node in the fiber list
var existingChildren = mapRemainingChildren(returnFiber, oldFiber);

// Loop through the rest of the new JSX array
for (; newIdx < newChildren.length; newIdx++) {
  // If the new JSX returns null and the updateFromMap returns NULL, skip the round
  // The new JSX does not return null, find the old fiber from existingChildren that is the same as the new JSX key, and see if you can reuse the fiber
  var _newFiber2 = updateFromMap(existingChildren, returnFiber, newIdx, newChildren[newIdx], lanes);

  if(_newFiber2 ! = =null) {
    if (shouldTrackSideEffects) {
      if(_newFiber2.alternate ! = =null) {
        // If the new fiber is not empty and the old fiber is reused, it indicates that there is a correspondence between the new fiber and the old fiber. Delete the old fiber from existingChildren
        existingChildren.delete(_newFiber2.key === null? newIdx : _newFiber2.key); }}// Place the new fiber
    lastPlacedIndex = placeChild(_newFiber2, lastPlacedIndex, newIdx);
    if (previousNewFiber === null) {
      resultingFirstChild = _newFiber2;
    } else{ previousNewFiber.sibling = _newFiber2; } previousNewFiber = _newFiber2; }}Copy the code

The fifth part

As a final step, iterate through existingChildren, removing the old fiber node and returning the first node of the new fiber list

if (shouldTrackSideEffects) {
  existingChildren.forEach(function (child) {
    return deleteChild(returnFiber, child);
  });
}

return resultingFirstChild;
Copy the code

In this way, beginWork will get the return value of this function, and return to performUnitOfWork, used to modify the global variable workInProgress, so as to continue to execute the workLoopSync loop.

PlaceChild method

PlaceChild is used to determine the location of the new fiber node in the new Fiber list and return the lastPlacedIndex mentioned earlier. Let’s look at the code

function placeChild(newFiber, lastPlacedIndex, newIndex) {
    // Determine the location index of the new fiber node
    newFiber.index = newIndex;
    if(! shouldTrackSideEffects) {// No action is taken
      return lastPlacedIndex;
    }
    var current = newFiber.alternate;
    if(current ! = =null) {
      // If current is not null, the new fiber is associated with the old fiber
      var oldIndex = current.index;
      if (oldIndex < lastPlacedIndex) {
        // The old fiber is on the left of lastPlacedIndex. No need to update lastPlacedIndex
        newFiber.flags = Placement;
        return lastPlacedIndex;
      } else {
        // The old fiber is on the right side of the lastPlacedIndex, indicating that in the new fiber list, the corresponding node has moved
        returnoldIndex; }}else {
      // If current is null, the new fiber is inserted directly
      newFiber.flags = Placement;
      returnlastPlacedIndex; }}Copy the code

Here’s an example:

Fiber -> fiber -> fiber -> fiber -> fiber -> fiber -> fiber -> fiber -> fiber -> fiber -> fiber -> fiberCopy the code

1. whennewIndexZero, enter the first part of the loop, and execute toplaceChildMethods, as old as newfiberNodes are associated, socurrentNot empty, butoldIndexandlastPlacedIndexIt’s all 0, so it returnsoldIndex
2. whennewIndexIs 1, which is the same as the first step, which also returnsoldIndex(1).lastPlacedIndexTo 1
3. whennewIndexIf it is 2, it breaks out of the first part of the loop, goes into the fourth part, and executes toplaceChildMethod,newFiberIs node D,currentAs the oldfiberD node of the linked list, socurrentDon’t empty,oldIndex3,lastPlacedIndexIs 1, so return 3,lastPlacedIndexInto 3
4. whennewIndexIs 3. The process is the same as step 3.lastPlacedIndexInto 4
5. whennewIndexIf the value is 4, go toplaceChildMethod,newFiberIs node C,currentAs the oldfiberThe C node of the linked list,currentDon’t empty,oldIndexTo 2,lastPlacedIndexTheta is 4, and at this pointoldIndexLess thanlastPlacedIndex, soreactIt is believed that C node has been moved, and the Placement tag is placed on it

So, lastPlacedIndex is the index of the position of the most right-leaning fiber node in the old fiber list that does not need to be moved.

Finally, let’s have a picture of the overall flow