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

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

Video explanation (efficient learning) :Into the study

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:

Dom is not reused across hierarchies for peer comparisons only
Different types of nodes generate different DOM trees. In this case, old nodes and descendant nodes are destroyed and new nodes are created

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

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
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
Index=2 > lastPlacedIndex=0 for the second C in newChild, no need to move lastPlacedIndex=2
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

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
OldFiber index=3 > lastPlacedIndex=0 for the first D in newChild, no need to move, lastPlacedIndex=3
Index= 0 < lastPlacedIndex=3 for A in the second position in newChild, moved to the end
OldFiber index=1 < lastPlacedIndex=3 for the third position B in newChild, moved to the end
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

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

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