An overview of

Starting from this chapter, we will enter the React Diff algorithm stage. Before entering this stage formally, let’s first understand the design motivation of react Diff algorithm.

The motivation

Any time a node calls React’s render() method, a tree of React elements is created. On the next state or props update, the same render() method returns a different tree. React needs to determine how efficiently to update the UI based on the differences between the two trees to keep the current UI in sync with the latest tree.

There are some general solutions to this algorithm, namely generating the minimum number of operations to convert one tree into another. However, even with the optimal algorithm, the complexity of the algorithm is O(n 3), where n is the number of elements in the tree.

If used in React, it would require a billion comparisons to show 1000 elements. The cost is simply too high. Therefore, React proposed a set of O(n) heuristic algorithm based on the following two assumptions:

1. Two different types of elements produce different trees;
2. Developers can setkeyProperty to tell the render which child elements can be saved under different renderings.
3. React does not compare across layers, only on the same layer

In practice, we find that the above assumptions hold true in almost all practical scenarios.

The above explanation can be found on the React website, and the third point is my personal opinion

Now we enter the source code phase.

The entry function

The entry function for diff is reconcileChildFibers(), which is called in reconcileChildren ().

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

MountChildFibers () and reconcileChildFibers() are both returned values from the closure ChildReconciler().

ReconcileChildFibers:

 function reconcileChildFibers(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChild: any,
    lanes: Lanes,
  ) :Fiber | null {
    const isUnkeyedTopLevelFragment =
      typeof newChild === 'object'&& newChild ! = =null &&
      newChild.type === REACT_FRAGMENT_TYPE &&
      newChild.key === null;
    if (isUnkeyedTopLevelFragment) {
      newChild = newChild.props.children;
    }

    // Handle object types
    const isObject = typeof newChild === 'object'&& newChild ! = =null;

    if (isObject) {
      switch (newChild.$$typeof) {
        case REACT_ELEMENT_TYPE:
          / / reconcileSingleElement processing
          return placeSingleChild(
            reconcileSingleElement(
              returnFiber,
              currentFirstChild,
              newChild,
              lanes,
            ),
          );
        case REACT_PORTAL_TYPE:
          // reconcileSinglePortal
          return placeSingleChild(
            reconcileSinglePortal(
              returnFiber,
              currentFirstChild,
              newChild,
              lanes,
            ),
          );
        case REACT_LAZY_TYPE:
          if (enableLazyElements) {
            const payload = newChild._payload;
            const init = newChild._init;
            // TODO: This function is supposed to be non-recursive.
            returnreconcileChildFibers( returnFiber, currentFirstChild, init(payload), lanes, ); }}}if (typeof newChild === 'string' || typeof newChild === 'number') {
      / / reconcileSingleTextNode processing
      / /... Omit the implementation
    }

    if (isArray(newChild)) {
      // Handle the array case
      / /... omit
    }

    

    // Remaining cases are all treated as empty.
    // If both fail, delete the node
    return deleteRemainingChildren(returnFiber, currentFirstChild);
  }

Copy the code

Note: reconcileChildFibers() set the flags of the Fiber node to Placement: newFiber. Flags = Placement;

As you can see from the above code, there are three main types of Newchildren dealt with in reconcileChildFibers() :

• Object: indicates a single node that is not text
• String | number: it means the current fiber for TextDom corresponding DOM type
• Array: Indicates that there are multiple nodes at the same level

<ul>
  <li>1</li>
  <li>2</li>
</ul>
Copy the code

In this chapter, we mainly discuss two cases: Object and Array, that is, single-node comparison and multi-node comparison.

Single-node comparison

Contrast we mainly look at single node newChild. $$typeof = = = REACT_ELEMENT_TYPE situation (namely by the react. CreateElenet creates the node). The entry function for a single node is reconcileSingleElement().

function reconcileSingleElement(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    element: ReactElement,
    lanes: Lanes,
  ) :Fiber {
    const key = element.key;
    let child = currentFirstChild;
    // child ! == null indicates that the current interface has a render node
    while(child ! = =null) {
      // Child === null indicates that the DOM node existed in the last update
      If the key is not equal, the current child node cannot be reused, and the child is directly marked as delete
      if (child.key === key) {
        switch (child.tag) {
         	/ / determine the tag
          case Fragment: {
            if (element.type === REACT_FRAGMENT_TYPE) {
              deleteRemainingChildren(returnFiber, child.sibling);
              const existing = useFiber(child, element.props.children);
              existing.return = returnFiber;
              if (__DEV__) {
                existing._debugSource = element._source;
                existing._debugOwner = element._owner;
              }
              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) {
                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;
                  if (__DEV__) {
                    existing._debugSource = element._source;
                    existing._debugOwner = element._owner;
                  }
                  returnexisting; }}}default: {
            // Check whether the tag of the current node is the same as that of the current node
            // The same representation can be reused
            // Otherwise, delete the current node
            if (
              child.elementType === element.type ||
              (__DEV__
                ? isCompatibleFamilyForHotReloading(child, element)
                : false)) {// Delete child's siblings and their children
              deleteRemainingChildren(returnFiber, child.sibling);
              const existing = useFiber(child, element.props);
              existing.ref = coerceRef(returnFiber, child, element);
              existing.return = returnFiber;
              if (__DEV__) {
                existing._debugSource = element._source;
                existing._debugOwner = element._owner;
              }
              return existing;
            }
            break; }}// If no match is found, delete it directly
        deleteRemainingChildren(returnFiber, child);
        break;
      } else {
        deleteChild(returnFiber, child);
      }
      child = child.sibling;
    }
		// Create a fiber based on element
    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

reconcileSingleElement()The flowchart is as follows:

Child: The last updated render node, which is the node currently displayed on the screen

Now let’s examine the code:

• whenchild ! == nullWhen the key and tag are equal, there’s a couple of things that you do
  1. calldeleteRemainingChildren()Deleting a sibling node
  2. calluseFiber()Realize reuse of fiber nodes
  3. callcoerceRef()Deal with ref
• whenchild ! == nullIf the keys are equal and the tags are not equal, it is called directlydeleteRemainingChildren()Delete the current node and its siblings, breaking out of the loop and entering the process of creating a fiber.
• whenchild === nullWhen: direct callcreateFiberFromElement()The system creates a node.

Here’s an example:

// 例1
<ul>
  <li></li>
  <li></li>
</ul>

<ul>
  <div></div>
</ul>
// In this case, react will delete all li under ul and create div

// 例2
<ul>
  <li key='1'></li>
  <li key='2'></li>
</ul>

<ul>
  <li key='2'></li>
</ul>
// When child is the first, the key is not equal, at this time, the node of key===1 is deleted, at the same time, child === child-. Sibling, the next iteration, when child-. key=== 2, the key is the same, reuse
Copy the code

More nodes’

Multi-node DIFF can be classified into the following three cases:

• Update node attributes, including attribute updates, type updates (li–>div)
• Node increase or decrease
• Node position changes

Multiple nodes are one of the three cases.

The entry function for multi-node reconcileChildrenArray():

function reconcileChildrenArray(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChildren: Array<*>,
    lanes: Lanes,
  ) :Fiber | null {
    // The first child fiber is finally returned
    let resultingFirstChild: Fiber | null = null;
    // Intermediate state
    let previousNewFiber: Fiber | null = null;

    // The current old fiber
    let oldFiber = currentFirstChild;
    let lastPlacedIndex = 0;
    // The index of the current DOM
    let newIdx = 0;
    // Next old fiber
    let nextOldFiber = null;
    // Compare the updated situation
    // The loop is broken in two cases
    // 1, oldFiber. Key! == newFiber.key
    // 2, the old or new loop is complete
    for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
      // The first loop
      / /... Omit code
    }

    // The new loop completes, and the remaining old 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;
    }

    // The old loop completes, and the new remaining node is inserted
    if (oldFiber === null) {
      // If we don't have any more existing children we can choose a fast path
      // since the rest will all be insertions.
      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;
    }

    // Both old and new are not finished
    // Add all children to a key map for quick lookups.
    // Form old into map
    const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

    // Keep scanning and use the map to restore deleted items as moves.
    for (; newIdx < newChildren.length; newIdx++) {
      // Loop the second time
      // Omit the code
    }
    // Delete the remaining cases
    if (shouldTrackSideEffects) {
      // Any existing children that weren't consumed above were deleted. We need
      // to add them to the deletion list.
      existingChildren.forEach(child= > deleteChild(returnFiber, child));
    }

    return resultingFirstChild;
  }
Copy the code

The main logic of the reconcileChildrenArray() function is divided into two cycles. We know that multi-node updating can be divided into three cases, but the probability of the three cases is completely different. The probability of the first case is very high, so React will give priority to the first case, that is, the first cycle.

Before we look at the two-turn cycle in detail, let’s take a look at the front action:

// The first child fiber is finally returned
let resultingFirstChild: Fiber | null = null;
// Intermediate state
let previousNewFiber: Fiber | null = null;

// The current old fiber
let oldFiber = currentFirstChild;
let lastPlacedIndex = 0;
// The index of the current DOM
let newIdx = 0;
// Next old fiber
let nextOldFiber = null;
Copy the code

There are several variables defined before the loop:

• ResultingFirstChild: The fiber returned after the comparison
• PreviousNewFiber: Intermediate state
• OldFiber: The last rendered fiber
• LastPlacedIndex: This value is used by the pan to determine if the node moved inplaceChild()use
• NewIdx: indicates the new index value
• NextOldFiber: The next fiber

First cycle

for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
  		// This is not very clear
      if (oldFiber.index > newIdx) {
        nextOldFiber = oldFiber;
        oldFiber = null;
      } else {
        nextOldFiber = oldFiber.sibling;
      }
  		// If keys are not equal, null is returned
      const newFiber = updateSlot(
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        lanes,
      );
      // Indicates that the key is not equal, and the current loop is directly broken
      if (newFiber === null) {
        if (oldFiber === null) {
          oldFiber = nextOldFiber;
        }
        break;
      }
      if (shouldTrackSideEffects) {
        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;
    }
Copy the code

The first round of traversal steps are as follows:

• When newIdx === 0, oldFiber and newChildren[0] are compared to determine whether they can be reused
• NewIdx++ when reusable, at the same timeoldFiber = nextOldFiberTo enter the next cycle
• Not reusable:
  1. If the key is not equal, it will jump out directly at this time. There may be two cases at this time: position change or node addition or deletion
  2. If the key is the same but the tag is different, oldFiber is marked as DELETE
• When oldFiber === NULL or newIdx === newchildren. length, the first cycle ends.

PlaceChild () is used to mark whether the current node is an insert node

Second cycle

OldFiber and newChildren are traversed at the same time

Ideally, this is when diff is complete

OldFiber is not finished, newChildren is finished

// The new loop completes, and the remaining old is deleted
if (newIdx === newChildren.length) {
  // Delete the remaining oldFiber
  deleteRemainingChildren(returnFiber, oldFiber);
  return resultingFirstChild;
}
Copy the code

OldFiber finished, newChildren did not finish

 // The old loop is complete. All you need to do is loop newChildren
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;
}
Copy the code

OldFiber and newChildren are not finished

In order to find in O(1) time, oldFiber needs to be converted to Map,

const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
Copy the code

for (; newIdx < newChildren.length; newIdx++) {
  		// Update the node
      const newFiber = updateFromMap(
        existingChildren,
        returnFiber,
        newIdx,
        newChildren[newIdx],
        lanes,
      );
      if(newFiber ! = =null) {
        if (shouldTrackSideEffects) {
					// indicates that the current node is a reuse node, and the reuse old node needs to be deleted from existingChildren
          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; }}Copy the code

After the loop is complete, there is one last action, which is to delete the remaining nodes in existingChildren, so the Diff algorithm is complete.

// Delete the remaining cases
if (shouldTrackSideEffects) {
  // Any existing children that weren't consumed above were deleted. We need
  // to add them to the deletion list.
  existingChildren.forEach(child= > deleteChild(returnFiber, child));
}
Copy the code

placeChild

  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) {
       	// This is to determine whether the current node is moving
        newFiber.flags = Placement;
        return lastPlacedIndex;
      } else {
        // This item can stay in place.
        returnoldIndex; }}else {
      // This is an insertion.
      newFiber.flags = Placement;
      returnlastPlacedIndex; }}Copy the code