React Diff algorithm (Mom doesn’t have to worry about my diff algorithm anymore)

Video explanation (efficient learning) :Into the study

Previous articles:

1. Introduction and questions

2. React design philosophy

React source code architecture

4. Source directory structure and debugging

5. JSX & core API

Legacy and Concurrent mode entry functions

7. Fiber architecture

8. Render phase

9. The diff algorithm

10. com MIT stage

11. Life cycle

12. Status update process

13. Hooks the source code

14. Handwritten hooks

15.scheduler&Lane

16. Concurrent mode

17.context

18 Event System

19. Write the React mini

20. Summary & Answers to interview questions in Chapter 1

When updating the Fiber nodes in the Render phase, we will call reconcileChildFibers to compare the Current Fiber with the JSX object to build the workInProgress Fiber. JSX is the return value of the Render method or function component of the class component.

In reconcileChildFibers, there are single-node diff and multi-node DIff, depending on the type of newChild

function reconcileChildFibers(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChild: any,
) :Fiber | null {

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

  if (isObject) {
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE:
				// Single node diff
        returnplaceSingleChild( reconcileSingleElement( returnFiber, currentFirstChild, newChild, lanes, ), ); }}/ /...
  
  if (isArray(newChild)) {
     // Multi-node diff
    return reconcileChildrenArray(
        returnFiber,
        currentFirstChild,
        newChild,
        lanes,
      );
  }

  // Delete a node
  return deleteRemainingChildren(returnFiber, currentFirstChild);
}
Copy the code

The main flow of diFF process is as follows:

We know that the complexity of comparing two trees is O(n3) itself, which is an unacceptable magnitude for our application. React proposes three premises to reduce complexity:

  1. Dom is not reused across hierarchies for peer comparisons only

  2. Different types of nodes generate different DOM trees. In this case, old nodes and descendant nodes are destroyed and new nodes are created

  3. Keys can be used to provide reusable clues to the process of element diff, for example:

    const a = (
        <>
          <p key="0">0</p>
          <p key="1">1</p>
        </>
      );
    const b = (
      <>
        <p key="1">1</p>
        <p key="0">0</p>
      </>
    );
    Copy the code

    If without the key elements in a and b, because of different nodes before and after the update text node, cause they can’t reuse, so will destroy the previous node, and the new node, but now have the key, the node b will look for the key in a old try to reuse the same node, finally found just swap places can complete the update, We’ll talk about that later.

    Single node diff

    There are several cases of a single point diff:

    • If the key and type are the same, nodes can be reused
    • The key is marked to delete the node and then create a new node
    • If the key is the same and the type is different, delete the node and its siblings, and then create a new node
    function reconcileSingleElement(
      returnFiber: Fiber,
      currentFirstChild: Fiber | null,
      element: ReactElement
    ) :Fiber {
      const key = element.key;
      let child = currentFirstChild;
      
      // The child node does not perform comparisons for null
      while(child ! = =null) {
    
        // 1
        if (child.key === key) {
    
          // 2
    
          switch (child.tag) {
            / /...
            
            default: {
              if (child.elementType === element.type) {
                // If type is the same, the node can be reused
                return existing;
              }
              // type is different
              break; }}// If the key is the same and the type is different, delete the symbol fiber and its sibling fiber
          deleteRemainingChildren(returnFiber, child);
          break;
        } else {
          // delete the node directly
          deleteChild(returnFiber, child);
        }
        child = child.sibling;
      }
       
      // Create a new Fiber
    }
    
    Copy the code

    Multi-node diff

    Multi-node DIff is complicated, and we discuss it in three cases, where A represents the node before the update and B represents the node after the update

    • Attribute changes

      const a = (
          <>
            <p key="0" name='0'>0</p>
            <p key="1">1</p>
          </>
        );
        const b = (
          <>
            <p key="0" name='00'>0</p>
            <p key="1">1</p>
          </>
        );
      Copy the code
    • Change the type

      const a = (
          <>
            <p key="0">0</p>
            <p key="1">1</p>
          </>
        );
        const b = (
          <>
            <div key="0">0</div>
            <p key="1">1</p>
          </>
        );
      Copy the code
    • The new node

      const a = (
          <>
            <p key="0">0</p>
            <p key="1">1</p>
          </>
        );
        const b = (
          <>
            <p key="0">0</p>
            <p key="1">1</p>
            <p key="2">2</p>
          </>
        );	
      Copy the code
    • The node to delete

      const a = (
          <>
            <p key="0">0</p>
            <p key="1">1</p>
            <p key="2">2</p>
          </>
        );
        const b = (
          <>
            <p key="0">0</p>
            <p key="1">1</p>
          </>
        );
      Copy the code
    • Node position change

      	const a = (
          <>
            <p key="0">0</p>
            <p key="1">1</p>
          </>
        );
        const b = (
          <>
            <p key="1">1</p>
            <p key="0">0</p>
          </>
        );
      Copy the code

    The multi-node diff is traversed three times in the source code. The first traversal deals with node updates (including props and Type updates and deletions), the second traversal deals with other cases (node additions), because in most applications nodes are updated more frequently, and the third traversal deals with bit-node changes

    • First traversal

      Since the old node exists in current Fiber, it is a linked list structure. Remember the Fiber double-cache structure, nodes are connected through child, return and Sibling, while newChildren exists in JSX, so when traversing and comparing, 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

  • Let’s do it the second time

    The second traverse considers three cases

    1. Both newChildren and oldFiber are traversed: the multi-node diff process is finished. 2Copy the code
    1. If newChildren and oldFiber are not traversed, the logic of node movement is entered
  • Third pass

    The main logic is in the placeChild function, for example, the order of the nodes before the update is ABCD and after the update is ACDB

    1. The key of the A in the first position in newChild is the same as the key of the A in the first position in oldFiber, lastPlacedIndex=0

    2. C in the second position of newChild and B in the second position of oldFiber, the key is different out of the first loop, save the BCD in oldFiber in the map

    3. Index=2 > lastPlacedIndex=0 for the second C in newChild, no need to move lastPlacedIndex=2

    4. Index=3 > lastPlacedIndex=2 in oldFiber, no need to move, lastPlacedIndex=3

      1. OldFiber index=1 < lastPlacedIndex=3 for the fourth position B in newChild, moved to the end

        It’s easier to visualize

    For example, the sequence of nodes is ABCD before the update and DABC after the update

    1. D in the first position of newChild and A in the first position of oldFiber have different keys and cannot be reused. Save ABCD in oldFiber in map with lastPlacedIndex=0

    2. OldFiber index=3 > lastPlacedIndex=0 for the first D in newChild, no need to move, lastPlacedIndex=3

    3. Index= 0 < lastPlacedIndex=3 for A in the second position in newChild, moved to the end

    4. OldFiber index=1 < lastPlacedIndex=3 for the third position B in newChild, moved to the end

    5. OldFiber index=2 < lastPlacedIndex=3 for the fourth position C in newChild, moved to the end

      It’s easier to visualize

    The code is as follows:

      function placeChild(newFiber, lastPlacedIndex, newIndex) {
        newFiber.index = newIndex;
    
        if(! shouldTrackSideEffects) {return lastPlacedIndex;
        }
    
     var current = newFiber.alternate;
    
        if(current ! = =null) {
          var oldIndex = current.index;
    
          if (oldIndex < lastPlacedIndex) {
            //oldIndex less than lastPlacedIndex inserts the node last
            newFiber.flags = Placement;
            return lastPlacedIndex;
          } else {
            return oldIndex;// We don't need to move lastPlacedIndex = oldIndex;}}else {
          // Add 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< * >,// The new node array is the JSX array
        lanes: Lanes,// Chapter 12 about lane
      ) :Fiber | null {
    
        let resultingFirstChild: Fiber | null = null;// the first node returned after diff
        let previousNewFiber: Fiber | null = null;// The new node that was compared last time
    
        let oldFiber = currentFirstChild;// Comparing oldFiber
        let lastPlacedIndex = 0;// The last reusable node location or oldFiber location
        let newIdx = 0;// Compare the position in the new node
        let nextOldFiber = null;// Comparing oldFiber
        for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {// First traversal
          if (oldFiber.index > newIdx) {/ / nextOldFiber assignment
            nextOldFiber = oldFiber;
            oldFiber = null;
          } else {
            nextOldFiber = oldFiber.sibling;
          }
          const newFiber = updateSlot(// Update the node, 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) {/ / check shouldTrackSideEffects
            if (oldFiber && newFiber.alternate === null) {
              deleteChild(returnFiber, oldFiber);
            }
          }
          lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);// mark node insertion
          if (previousNewFiber === null) {
            resultingFirstChild = newFiber;
          } else {
            previousNewFiber.sibling = newFiber;
          }
          previousNewFiber = newFiber;
          oldFiber = nextOldFiber;
        }
    
        if (newIdx === newChildren.length) {
          deleteRemainingChildren(returnFiber, oldFiber);// Mark the nodes in oldFiber that are not completely traversed as DELETION
          return resultingFirstChild;
        }
    
        if (oldFiber === null) {
          for (; newIdx < newChildren.length; newIdx++) {// The second pass
            const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
            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;
        }
    
        // Add the rest of oldFiber to the map
        const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
    
        for (; newIdx < newChildren.length; newIdx++) {// The third loop handles the node movement
          const newFiber = updateFromMap(
            existingChildren,
            returnFiber,
            newIdx,
            newChildren[newIdx],
            lanes,
          );
          if(newFiber ! = =null) {
            if (shouldTrackSideEffects) {
              if(newFiber.alternate ! = =null) {
                existingChildren.delete(// Delete the found node
                  newFiber.key === null ? newIdx : newFiber.key,
                );
              }
            }
            lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);// mark the logic for insertion
            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