Note: The conclusions of this article are based on React 17.0.2. If there is any discrepancy, please refer to the corresponding source code

The introduction

The first part of the beginWork phase of the React coordination process was introduced in the previous article. In this article, we will introduce the second part.

beginWork

Again, let’s simplify the code and focus only on the parts of interest:

function beginWork(
  current: Fiber | null,
  workInProgress: Fiber,
  renderLanes: Lanes,
) :Fiber | null {... workInProgress.lanes = NoLanes;switch (workInProgress.tag) {
    case IndeterminateComponent:
    ...
    case LazyComponent:
    ...
    case FunctionComponent:
    ...
    case ClassComponent:
    ...
    case HostRoot:
    ...
    case HostComponent:
    ...
    case HostText:
    ...
}
Copy the code

The workinProgress. tag is first used to determine what type of FiberNode is being processed, and different UPDATE methods are invoked for each type. These methods have very different names, but they all end up with two lines of code:

  reconcileChildren(current, workInProgress, nextChildren, renderLanes);
  return workInProgress.child;
Copy the code

Where workInProgress is the current FiberNode being processed, current is the last updated FiberNode paired with workInProgress (which may not exist), NextChildren are the new children of the update workInProgress (ReactElement array), and renderLanes are related to update priorities.

Here’s what Reconci Children does:

export function reconcileChildren(
  current: Fiber | null,
  workInProgress: Fiber,
  nextChildren: any,
  renderLanes: Lanes,
) {
  if (current === null) {
    workInProgress.child = mountChildFibers(
      workInProgress,
      null,
      nextChildren,
      renderLanes,
    );
  } else{ workInProgress.child = reconcileChildFibers( workInProgress, current.child, nextChildren, renderLanes, ); }}Copy the code

MountChildFibers or reconcileChildFibers are determined based on the existence of the current reconcileChildren, and the two methods are actually similar, It’s just that shouldTrackSideEffects is true when reconcileChildFibers is reconcileChildFibers, which does a little more:

function ChildReconciler(shouldTrackSideEffects) {...return reconcileChildFibers;
}
export const reconcileChildFibers = ChildReconciler(true);
export const mountChildFibers = ChildReconciler(false);
Copy the code

For the moment, we just look at reconcileChildFibers:

function reconcileChildFibers(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChild: any,
  lanes: Lanes,
) :Fiber | null {...// Handle object types
  const isObject = typeof newChild === 'object'&& newChild ! = =null;

  if (isObject) {
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE:
        returnplaceSingleChild( reconcileSingleElement( returnFiber, currentFirstChild, newChild, lanes, ), ); . }}...if (isArray(newChild)) {
    returnreconcileChildrenArray( returnFiber, currentFirstChild, newChild, lanes, ); }...// Remaining cases are all treated as empty.
  return deleteRemainingChildren(returnFiber, currentFirstChild);
}
Copy the code

The reconcileChildFibers deal with each reconcileChildFibers differently according to the type of newChild in the reconcileChildFibers, removing the parts we don’t care about at the moment, and analyzing only cases where newChild is an object and is either REACT_ELEMENT_TYPE or an array. In fact, it involves the Diff algorithm for reconcileChildFibers in The React reconcileChildFibers, which we examine in more detail.

The Diff algorithm

What is Diff’s?

First of all, the first question you need to know is: What two things are Diff algorithms? Is it old FiberNode and new FiberNode? The answer is No.

From the code above, it is current. Child and nextChildren that are passed into reconcileChildFibers, So the Diff algorithm is actually a process of generating new FiberNode by comparing old FiberNode with new ReactElement:

Classification of Diff

According to the type of ReactElement in Diff, Diff algorithms can be divided into:

Single-node Diff (reconcileSingleElement) :ReactElementIs an object.
Multi-node Diff (reconcileChildrenArray) :ReactElementIs an array.

Single node Diff

function reconcileSingleElement(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    element: ReactElement,
    lanes: Lanes,
  ) :Fiber {
    const key = element.key;
    let child = currentFirstChild;
    while(child ! = =null) {
      if (child.key === key) {
        const elementType = element.type;
        if (elementType === REACT_FRAGMENT_TYPE) {
          ...
        } else {
          if (
            child.elementType === elementType ||
            // Keep this check inline so it only runs on the false path:
            (__DEV__
              ? isCompatibleFamilyForHotReloading(child, element)
              : false) ||
            (enableLazyElements &&
              typeof elementType === 'object'&& elementType ! = =null &&
              elementType.$$typeof === REACT_LAZY_TYPE &&
              resolveLazy(elementType) === child.type)
          ) {
            deleteRemainingChildren(returnFiber, child.sibling);
            const existing = useFiber(child, element.props);
            existing.ref = coerceRef(returnFiber, child, element);
            existing.return = returnFiber;
            returnexisting; }}// Didn't match.
        deleteRemainingChildren(returnFiber, child);
        break;
      } else {
        deleteChild(returnFiber, child);
      }
      child = child.sibling;
    }

    if (element.type === REACT_FRAGMENT_TYPE) {
      ...
    } else {
      const created = createFiberFromElement(element, returnFiber.mode, lanes);
      created.ref = coerceRef(returnFiber, currentFirstChild, element);
      created.return = returnFiber;
      returncreated; }}Copy the code

After removing some debug codes and codes with Fragment type, analyze the remaining codes and find that they can be divided into four scenarios:

The originalFiberNodeDoes not exist. You just create new onesFiberNodeAnd marked asPlacementCan.
The newReactElementAnd the oldFiberNode 的 type 和 keyAre the same. You can reuse the old onesFiberNodeAnd will the oldFiberNodeAll sibling nodes of.
The newReactElementAnd the oldFiberNode 的 keyThe same,typeDifferent. Need to put the oldFiberNodeAnd its siblings are marked for deletion, and new ones are createdFiberNodeAnd marked asPlacement.
The newReactElementAnd the oldFiberNode 的 keyDifferent. The currentFiberNodeMark it as delete and continue to compare its sibling nodes and according to policy 2, 3, and 4ReactElementUntil the traversal is complete.

Multi-node Diff

  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;
    // In the first loop, compare the old and new nodes, and exit when the key is different
    for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
      if (oldFiber.index > newIdx) {
        nextOldFiber = oldFiber;
        oldFiber = null;
      } else {
        nextOldFiber = oldFiber.sibling;
      }
      const newFiber = updateSlot(
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        lanes,
      );
      if (newFiber === null) {
        if (oldFiber === null) {
          oldFiber = nextOldFiber;
        }
        break;
      }
      if (shouldTrackSideEffects) {
        // The new and old nodes have the same key but different type
        if (oldFiber && newFiber.alternate === null) {
          deleteChild(returnFiber, oldFiber);
        }
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
      oldFiber = nextOldFiber;
    }

    // The second loop

    // The ReactElement array is iterated over and the remaining old nodes need to be marked as deleted
    if (newIdx === newChildren.length) {
      deleteRemainingChildren(returnFiber, oldFiber);
      return resultingFirstChild;
    }

    // When the old FiberNode list is traversed, FiberNode is created from the remaining nodes in the ReactElement array and marked as Placement
    if (oldFiber === null) {
      for (; newIdx < newChildren.length; newIdx++) {
        const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
        if (newFiber === null) {
          continue;
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
        if (previousNewFiber === null) {
          // TODO: Move out of the loop. This only happens for the first run.
          resultingFirstChild = newFiber;
        } else {
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
      return resultingFirstChild;
    }


    // Save the old unprocessed FiberNode nodes to the Map
    const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

    // Iterate over the elements in the new ReactElement array to find nodes with the same key in the map
    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = updateFromMap(
        existingChildren,
        returnFiber,
        newIdx,
        newChildren[newIdx],
        lanes,
      );
      if(newFiber ! = =null) {
        if (shouldTrackSideEffects) {
          if(newFiber.alternate ! = =null) {
            existingChildren.delete(
              newFiber.key === null ? newIdx : newFiber.key,
            );
          }
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
        if (previousNewFiber === null) {
          resultingFirstChild = newFiber;
        } else{ previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; }}if (shouldTrackSideEffects) {
      existingChildren.forEach((child) = > deleteChild(returnFiber, child));
    }

    return resultingFirstChild;
  }
Copy the code

In practical application scenarios, most list updates are appended or nodes themselves are updated, and node positions change is relatively rare. React is divided into two rounds in the process of multi-node Diff:

The first round of front to back comparison, here is divided into three situations:

If the old and new nodeskey 和 typeIf the same, you can reuse the old node and continue to traverse.
keyThe sametypeThe old node is marked as deleted and the new node is marked asPlacement, and keep going.
keyDifferent, exit the loop.

After the end of the first round, the second round is traversed, which is divided into three situations:

The new node, the ReactElement array, is traversed, and all you need to do is mark the old remaining node as deleted and return.
With the old list of nodes traversed, all you need to do is process the remaining elements in the ReactElement array by creating a new FiberNode from them, marking it as Placement, and then returning.
None of them completed traversal, indicating that the first round of traversal was terminated prematurely. This step is discussed in detail:

3.1. Save the old nodes that have not been traversed as Map and use key as index. 3.2. Traverse the new node and search for reusable nodes in Map through the new node. If no node is found, a new node is created through ReactElement. If a node is found, the old node is reused to create a new node. You end up with newFiber. 3.3. Call placeChild to process newFiber. There are three cases: a. It is created by ReactElement and marked as Placement; B. It is obtained by reusing the old node whose position is less than lastPlacedIndex and marked as Placement; C. It is obtained by reusing the old node whose position oldIndex is greater than lastPlacedIndex. Update lastPlacedIndex to oldIndex without marking.

The above steps must be confusing, especially when it comes to updating lastPlace Index. Consider the following two examples:

Example 1:

Old list: abcde New list: ABdecCopy the code

The result of this example is to move c to the back.

Example 2:

Old list: abcde New list: abECDCopy the code

The result of this example is to move c and D to the end.

Both of them move only one element, but the result is different. The cost of example 2 is obviously higher because of the React Diff algorithm.

conclusion

This paper introduces the second half of beginWork function and leads to the Diff algorithm, discusses the role of Diff algorithm, classification and detailed steps, and combined with the case for comparison.

Welcome to pay attention to the public account “front-end tour”, let us travel in the front-end ocean together.

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 source code coordination Process (2)

The introduction

beginWork

The Diff algorithm

What is Diff’s?

Classification of Diff

Single node Diff

Multi-node Diff

conclusion

React source code coordination Process (2)

The introduction

beginWork

The Diff algorithm

What is Diff’s?

Classification of Diff

Single node Diff

Multi-node Diff

conclusion

Related Posts

JS execution mechanism

Encapsulate Vue – based message comment tree components

Using JavaScript Modules in the browser