React Diff algorithm completely read

preface

Diff algorithm is also a high-frequency test in the front-end interview, so how to give the interviewer a full mark answer? Is it as simple as “depth first, level by level”? This is too short…… !

All right, let’s get down to business

Single node diff

Single-node diff is simpler. Find the old fiber node with the same key and type. If the old fiber node exists, reuse it and delete the remaining nodes, otherwise create a new fiber node (which means that the subtree rooted in this node needs to be rebuilt). Let’s take a look at the core source of the single-node DIff

function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement,
  lanes: Lanes
) :Fiber {
  const key = element.key;
  let child = currentFirstChild;
  // Traverses the same hierarchy of old Fiber nodes
  while(child ! = =null) {
    if (child.key === key) {
      const elementType = element.type;
      // Find a node with the same key and type in the old fiber node. If found, reuse the node and delete the redundant nodes to exit the loop
      if (child.elementType === elementType) {
        deleteRemainingChildren(returnFiber, child.sibling);
        const existing = useFiber(child, element.props);
        existing.ref = coerceRef(returnFiber, child, element);
        existing.return = returnFiber;
        return existing;
      }
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      // If the fiber node does not match, delete it
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }

  // The node with the same key and type cannot be matched from the old fiber, so it needs to be regenerated
  const created = createFiberFromElement(element, returnFiber.mode, lanes);
  created.return = returnFiber;
  return created;
}

Copy the code

Multi-node diff

Here we go. Pay attention. Multiple nodes is the essence

At present, there are 3 Li’s on the page, the content and key are 1, 2 and 3 respectively (fiberThe tree is shown below.)

Now I want to make the page into 3 Li’s, with contents and keys 1, 3, and 2 respectively, and their corresponding ReactElement structure is

[{$$typeof: REACT_ELEMENT_TYPE, type: 'li'.props: {children: 1}, key: 1. }, {$$typeof: REACT_ELEMENT_TYPE, type: 'li'.props: {children: 3}, key: 3. }, {$$typeof: REACT_ELEMENT_TYPE, type: 'li'.props: {children: 2}, key: 2. },]Copy the code

So what does react do?

• I’m going to define onelastPlacedIndexUsed as a baseline position to determine whether the old node needs to be moved. The initial value is 0
• The first round iterates through the newchildrennamelyReactElementIf the key and type are the same, it means that the fiber node can be reused. Otherwise, it exits the first cycle. Compare the index value of oldFiber with lastPlaceIndex. If oldIndex<lastPlaceIndex, it means that the newly generated fiber node needs to be moved. Mark with Placement. LastPlaceIndex remains unchanged, otherwiselastPlaceIndex=oldIndex
• After the first loop is complete, there are three scenarios: 1. NewChildren are all iterated (ideally, just delete the remaining oldFibers); 2. 2. OldFibers are traversed, but newChildren are not traversed (this isn’t that complicated, just create fiber nodes for the remaining newChildren); 3. NewChildren and oldFibers are not iterated (the most complicated case requires a second loop)
• The remaining oldFibers are stored in the map. OldFiber uses the key as the map key if there is a key, index as the map key if there is no key, and oldFiber as the map value
• The second loop starts, traversing the untraversed newChildren: find from the mapnewChild.key||newIndexOldFiber of key. If oldFiber exists, use it (if type is the same, reuse it; if type is different, generate it)newFiber, then remove the oldFiber from the map, and then put the oldFiber ifnewFiberIt’s recycled. It existsalternate.newFiber.alternate == oldFiberIf oldIndex<lastPlaceIndex, the newly generated fiber node needs to be re-inserted, marked with Placement, and lastPlaceIndex remains unchanged, otherwiselastPlaceIndex=oldIndex; ifnewFiberIs regenerated, thennewFiber.alternate == nullType directlyPlacementLabel, lastPlaceIndex stays the same.
• After the second loop, delete the remaining oldFiber in the map

The complex process is shown below:

Let’s look at the implementation of the React Diff code snippet

function reconcileChildrenArray(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChildren: Array<*>,
  lanes: Lanes
) :Fiber | null {

  let resultingFirstChild: Fiber | null = null;
  let previousNewFiber: Fiber | null = null;

  let oldFiber = currentFirstChild;
  let lastPlacedIndex = 0;
  let newIdx = 0;
  let nextOldFiber = null;
  // The first round of traversal
  for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
    // ...
    nextOldFiber = oldFiber.sibling;
    // If type and key are the same, reuse the fiber node to return a newFiber, otherwise return null, and exit the first loop
    const newFiber = updateSlot(
      returnFiber,
      oldFiber,
      newChildren[newIdx],
      lanes
    );
    if (newFiber === null) {
      // ...
      break;
    }
    if (oldFiber && newFiber.alternate === null) {
      // If newFiber is not reused, mark oldFiber as deleted
      deleteChild(returnFiber, oldFiber);
    }
    // flag whether newFiber needs to be re-inserted
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
    oldFiber = nextOldFiber;
  }

  // The first loop is complete, newChildren traversal is complete, and the excess oldFiber is deleted
  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) {
    // The old fiber is traversed, but the newChildren is not traversed, so we need to generate fiber and mark it as needing to be inserted
    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
      if (newFiber === null) {
        continue;
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
    return resultingFirstChild;
  }

  / / the remaining oldFiber in the map, the key = oldFiber. Key | | oldFiber. Index
  const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

  // Iterate over the rest of newChildren
  for (; newIdx < newChildren.length; newIdx++) {
    / / query whether there is oldFiber can reuse from the map, according to the newChild. Key | | newIndex to query, have, reuse, not regenerate
    const newFiber = updateFromMap(
      existingChildren,
      returnFiber,
      newIdx,
      newChildren[newIdx],
      lanes
    );
    if(newFiber ! = =null) {
      // newFiber is generated
      if(newFiber.alternate ! = =null) {
        // Remove oldFiber from map that has already been multiplexed
        existingChildren.delete(newFiber.key === null ? newIdx : newFiber.key);
      }
      // Determine whether the node needs to be moved
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else{ previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; }}// Delete the remaining oldFiber in the map
  existingChildren.forEach((child) = > deleteChild(returnFiber, child));

  return resultingFirstChild;
}

Copy the code

Question? What happens if some keys in oldFibers are the same during diff?