For an update component, he compares the current component to the Fiber node that it was updated to last time (commonly known as Diff algorithm) and generates a new Fiber node.

Where does the On3 of diff come from

In react architecture, I mentioned that the node that was rendered last time, i.e. the node that was already displayed on the page, was current Fiber. This update is workinProgress Fiber. The React diff algorithm goes from O(n3) to O(n). Here’s how:

  1. Comparing all the nodes in the two trees one by one requires order n ^ 2,
  2. In the process of comparison, it is found that the old node is not found in the new tree, so the old node needs to be deleted. The time complexity of deleting a node of a tree (finding a suitable node to be placed at the deleted location) is O(n), and the time complexity of adding a new node is also O(n). Combined, the complexity of the two trees is O(n³).

Optimization of diff algorithm

To reduce algorithm complexity, the React diff presets three limits:

  1. Apply only to sibling elementsDiff. If aDOM nodeIt crosses the hierarchy in two successive updates, soReactNo attempt will be made to reuse him.
  2. Two different types of elements produce different trees. If the element is controlled bydivintopReact will destroy itdivAnd its descendants, and create a new nodepAnd descendant nodes.
  3. Developers can usekey propTo indicate which child elements will remain stable under different renders. Consider the following example:

The diff algorithm

We start with the Diff’s entry function reconcileChildFibers, which calls different handlers based on the newChild, or JSX object, type.

// Select different diff functions according to the newChild type
function reconcileChildFibers(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChild: any,
) :Fiber | null {
  const isObject = typeof newChild === 'object'&& newChild ! = =null;
  if (isObject) {
    // The object type can be REACT_ELEMENT_TYPE or REACT_PORTAL_TYPE
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE:
        // Calls the reconcileSingleElement to process the reconcileSingleElement
      / / / /... Omit other cases}}if (typeof newChild === 'string' || typeof newChild === 'number') {
    The reconcileSingleTextNode is called
    / /... omit
  }

  if (isArray(newChild)) {
    The reconcileChildrenArray is called to process the reconcileChildrenArray
    / /... omit
  }

  // Some other cases call handlers
  / /... omit

  // If none of the above matches, delete the node
  return deleteRemainingChildren(returnFiber, currentFirstChild);
}
Copy the code

Diff can be divided into two types according to the number of nodes at the same level:

  1. whennewChildA type ofobject,number,string, indicates that there is only one node at the same level
  2. whennewChildA type ofArray, there are multiple nodes at the same level.

Single-node diff

The diff of the individual nodes goes into the reconcileSingleElement method, which essentially does the following

We can roughly look at the source code is how to achieve

  function reconcileSingleElement(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    element: ReactElement,
    lanes: Lanes,
  ) :Fiber {
    const key = element.key;
    let child = currentFirstChild;

    // Identify existing DOM nodes
    while(child ! = =null) {
      // Determine whether the last DOM node can be reused

      / / is the key
      if (child.key === key) {
        switch (child.tag) {
          case Fragment: {
            if (element.type === REACT_FRAGMENT_TYPE) {
              deleteRemainingChildren(returnFiber, child.sibling);
              const existing = useFiber(child, element.props.children);
              existing.return = returnFiber;
              return existing;
            }
            break;
          }
          case Block:
            if (enableBlocksAPI) {
              let type = element.type;
              if (type.$$typeof === REACT_LAZY_TYPE) {
                type = resolveLazyType(type);
              }
              if (type.$$typeof === REACT_BLOCK_TYPE) {
                // The new Block might not be initialized yet. We need to initialize
                // it in case initializing it turns out it would match.
                if (
                  ((type: any): BlockComponent<any, any>)._render ===
                  (child.type: BlockComponent<any, any>)._render
                ) {
                  deleteRemainingChildren(returnFiber, child.sibling);
                  const existing = useFiber(child, element.props);
                  existing.type = type;
                  existing.return = returnFiber;
                  returnexisting; }}}default: {
            if (child.elementType === element.type)
              // If the key is the same and the type is the same, it can be multiplexed
               {
              deleteRemainingChildren(returnFiber, child.sibling);
              const existing = useFiber(child, element.props);
              existing.ref = coerceRef(returnFiber, child, element);
              existing.return = returnFiber;
              return existing;
            }
            break; }}// If the key is the same and the type is different, mark this fiber and its sibling fiber as deleted
        deleteRemainingChildren(returnFiber, child);
        break;
      } else {
        // If the key is different, the flag is deleted
        deleteChild(returnFiber, child);
      }
      child = child.sibling;
    }
    // Create a new fiber
    if (element.type === REACT_FRAGMENT_TYPE) {
      const created = createFiberFromFragment(
        element.props.children,
        returnFiber.mode,
        lanes,
        element.key,
      );
      created.return = returnFiber;
      return created;
    } else {
      const created = createFiberFromElement(element, returnFiber.mode, lanes);
      created.ref = coerceRef(returnFiber, currentFirstChild, element);
      created.return = returnFiber;
      returncreated; }}Copy the code

React checks whether the key is the same or not. React checks whether the key is the same or not.

  • Same type: can be reused
  • Different types: executedeleteRemainingChildrenwillchildAnd their brothers,fiberAll marked for deletion.

Multi-node DIff

If it is a diff of multiple nodes, its children property is an array of nodes. The newChild parameter for reconcileChildFibers is of type Array, which corresponds within the reconcileChildFibers function as follows

// Diff between multiple nodes
if (isArray(newChild)) {
  return reconcileChildrenArray(
    returnFiber,
    currentFirstChild,
    newChild,
    lanes,
  );
}
Copy the code

Diff of multiple nodes is complicated and can be divided into the following situations:

  • Node updates
    • Changes to the attributes of a node
    • The type of the node changes
  • Adding and deleting nodes
  • Changes in the position of nodes

Note:

When we do array-related algorithms, we often use double Pointers to traverse both the head and the tail of an array to make it more efficient, but we don’t do that here.

Although the JSX object newChildren updated this time is in the form of an array, current Fiber is compared with each component in newChildren. The fiber nodes at the same level are single-linked lists formed by sibling pointer links, that is, dual-pointer traversal is not supported.

That is, newChildren[0] is compared with Fiber and newChildren[1] is compared with fiber.sibling.

So you can’t use two-pointer optimization

React prioritizes node updates because most of the development is node updates.

First iteration

First let newChildren[I] compare with oldFiber, then let I ++, nextOldFiber = oldFiber.sibling. In the first iteration, three cases are processed, of which the first and second cases end the first loop

  1. The key is different. The first loop ends
  2. NewChildren or oldFiber traversal completes the first loop
  3. Key is different from type. OldFiber is marked as DELETION
  4. The same key and type can be reused

After newChildren traversal was completed, oldFiber was not traversed. After the first traversal was completed, nodes that were not traversed in oldFiber were marked as DELETION, that is, deleted DELETION Tag

The code for the first iteration:

for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
      if (oldFiber.index > newIdx) {
        nextOldFiber = oldFiber; / / nextOldFiber assignment
        oldFiber = null;
      } else {
        nextOldFiber = oldFiber.sibling; // nextOldFiber assigns the sibling of oldFiber
      }
      const newFiber = updateSlot( NewFiber = null if the key is different
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        lanes,
      );
      if (newFiber === null) {
        if (oldFiber === null) {
          oldFiber = nextOldFiber;
        }
        break; // Jump out of the first walk
      }
      if (shouldTrackSideEffects) {
        if (oldFiber && newFiber.alternate === null) {
          // Slot is matched, but existing Fiber is not reused, and existing child is deleted.
          deleteChild(returnFiber, oldFiber);
        }
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); // Marks the position of the inserted node
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
      oldFiber = nextOldFiber;
    }
Copy the code

Second round of traversal

  1. Both newChildren and oldFiber are traversed: the multi-node diff process is complete
  2. OldFiber traverses and marks the remaining nodes of newChildren as Placement, i.e. inserted tags
  3. If newChildren and oldFiber are not traversed, the logic of node movement is entered

Second round of traversal source code:

for (; newIdx < newChildren.length; newIdx++) {
        const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);// Create new nodes
        if (newFiber === null) {
          continue;
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); // Insert the new node
        if (previousNewFiber === null) { 
          resultingFirstChild = newFiber;
        } else {
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
      return resultingFirstChild;// returns the first node after diff
    }
Copy the code

The third iteration

The main logic for the third iteration, in the placeChild function, is that the order of the nodes before the update is ABCD and after the update is ACDB, assuming that the type is the same

  1. A in the first position in newChildren and A in the first position in oldFiber have the same reusable key, lastPlacedIndex=0.
  2. C in the second position of newChildren and B in the second position of oldFiber, with different keys, jump out of the first loop and save the BCD in oldFiber in the map
  3. If we continue to iterate over newChildren, the second C in newChildren is index=2 > lastPlacedIndex=0 in oldFiber, we don’t need to move it, lastPlacedIndex=2
  4. The third D in newChildren is index=3 > lastPlacedIndex=2 in oldFiber, no need to move, lastPlacedIndex=3
  5. Index= 1 < lastPlacedIndex=3 in oldFiber for the fourth position B in newChildren, moved to the end

Let’s look at another example:

  1. The first time through, the key is different, so we save the whole oldFiber in the map,lastPlacedIndex=0
  2. Continuing through newChildren, the first node D exists in oldFiber, index = 3 > lastPlacedIndex = 0, no need to move
  3. The second node A exists in oldFiber, index = 0 < lastPlacedIndex = 3, and moves to the end
  4. The third node B exists in oldFiber, index = 1 < lastPlacedIndex = 3, and moves to the end
  5. The fourth node C exists in oldFiber, index = 2 < lastPlacedIndex = 3, and moves to the end

One caveat here is to minimize the need to move nodes from the back to the front. From the example above, we can see that when we go from ABCD to DABC, instead of moving D to the front, we move D to the back.

The third pass through the source:

for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = updateFromMap( // Get fiber from map
        existingChildren,
        returnFiber,
        newIdx,
        newChildren[newIdx],
        lanes,
      );
      if(newFiber ! = =null) {
        if (shouldTrackSideEffects) {
          if(newFiber.alternate ! = =null) {
            // The new fiber is a workinProgress, but there is a current,
            // To reuse this fiber, we need to remove it from childList instead of adding deletionList
            existingChildren.delete( // Find the deleted node
              newFiber.key === null? newIdx : newFiber.key, ); }}// mark it as insert logic to get lastPlacedIndex
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); 
        if (previousNewFiber === null) {
          resultingFirstChild = newFiber;
        } else{ previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; }}Copy the code

The whole process source code:

  function placeChild(newFiber: Fiber, lastPlacedIndex: number, newIndex: number,) :number {
    newFiber.index = newIndex;
    if(! shouldTrackSideEffects) {// Noop.
      return lastPlacedIndex;
    }
    const current = newFiber.alternate;
    if(current ! = =null) {
      const oldIndex = current.index;
      if (oldIndex < lastPlacedIndex) {
        // oldIndex < lastPlacedIndex inserts the node after it
        newFiber.flags = Placement;
        return lastPlacedIndex;
      } else {
        // No need to move
        returnoldIndex; }}else {
      // This is a new insert
      newFiber.flags = Placement;
      returnlastPlacedIndex; }}Copy the code
 function reconcileChildrenArray(
    returnFiber: Fiber, // Parent fiber node
    currentFirstChild: Fiber | null.// the first node in childs
    newChildren: Array< * >,// Array of new nodes
    lanes: Lanes, / / priority
  ) :Fiber | null {
    let resultingFirstChild: Fiber | null = null; // the first node returned after diff
    let previousNewFiber: Fiber | null = null; // The node of the new node compared last time

    let oldFiber = currentFirstChild; // Comparing oldFiber
    let lastPlacedIndex = 0; // The location of the node or oldFiber that could be reused last time
    let newIdx = 0; // Compare the position in the new node
    let nextOldFiber = null; // Comparing oldFiber

    // Start the first iteration
    for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
      if (oldFiber.index > newIdx) {
        nextOldFiber = oldFiber; / / nextOldFiber assignment
        oldFiber = null;
      } else {
        nextOldFiber = oldFiber.sibling; // nextOldFiber assigns the sibling of oldFiber
      }
      const newFiber = updateSlot( NewFiber = null if the key is different
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        lanes,
      );
      if (newFiber === null) {
        if (oldFiber === null) {
          oldFiber = nextOldFiber;
        }
        break;
      }
      if (shouldTrackSideEffects) {
        if (oldFiber && newFiber.alternate === null) {
          // Slot is matched, but existing Fiber is not reused, and existing child is deleted.
          deleteChild(returnFiber, oldFiber);
        }
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); // Marks the position of the inserted node
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
      oldFiber = nextOldFiber;
    }

    if (newIdx === newChildren.length) {
      // We've reached the end of the new children. We can delete the rest.
      deleteRemainingChildren(returnFiber, oldFiber);
      return resultingFirstChild;
    }

    if (oldFiber === null) {
      // Process the new node for the second time
      for (; newIdx < newChildren.length; newIdx++) {
        const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);// Create new nodes
        if (newFiber === null) {
          continue;
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); // Insert the new node
        if (previousNewFiber === null) { // returns the first node after diff
          resultingFirstChild = newFiber;
        } else {
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
      return resultingFirstChild;
    }

    // Add the rest of oldFiber to the map
    const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

    // The third loop handles the node movement
    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = updateFromMap( // Get fiber from map
        existingChildren,
        returnFiber,
        newIdx,
        newChildren[newIdx],
        lanes,
      );
      if(newFiber ! = =null) {
        if (shouldTrackSideEffects) {
          if(newFiber.alternate ! = =null) {
            // The new fiber is a workinProgress, but there is a current,
            // To reuse this fiber, we need to remove it from childList instead of adding deletionList
            existingChildren.delete( // Find the deleted node
              newFiber.key === null? newIdx : newFiber.key, ); }}// mark it as insert logic to get lastPlacedIndex
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); 
        if (previousNewFiber === null) {
          resultingFirstChild = newFiber;
        } else{ previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; }}if (shouldTrackSideEffects) {
      // Delete the remaining nodes in existingChildren
      existingChildren.forEach(child= > deleteChild(returnFiber, child));
    }

    return resultingFirstChild;
  }
Copy the code