Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”. This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

React17 React17 React17 React17 React17 React17

React source code parsing (5), this chapter will combine the source code parsing diff algorithm, including the following contents:

  • React Diff algorithm introduction
  • The diff strategy
  • Diff source code analysis

In the Render phase of React in the previous chapter, the reconcileChildren function is called by Begin, and what is done in the reconcileChildren function is the well-known Diff process in React. This chapter explains the Diff algorithm.

Diff algorithm introduction

Each update to React compares the new ReactElement content with the old Fiber tree. After comparing the differences, a new Fiber tree is constructed and the differences are queued to render the real DOM. This is simply how to convert an old Fiber tree to a new fiber tree with minimal cost.

In the classical DIff algorithm, the minimum time complexity of converting a tree to another tree is O(n^3), where N is the number of nodes of tree species. If this diff algorithm is used, an application with 1000 nodes will need to compare a billion times to complete the DOM tree update, which is obviously unacceptable performance.

Therefore, to apply DIFF to virtual DOM, an efficient DIFF algorithm must be implemented. React implements O(n) time complexity updates to the virtual DOM through a set of bold strategies.

The diff strategy

React optimizes the DIff algorithm to O(n) time complexity based on the following three prerequisite strategies:

  • Only sibling elements are compared. In Web UI, DOM node movement across hierarchies is rare and can be ignored. If there is an update of DOM node across hierarchies, it will not be reused.
  • Two different types of components result in two different tree structures.
  • For children of the same level, the developer can passkeyTo determine which child elements can remain stable across different renders.

The three diff policies above correspond to tree Diff, Component Diff, and Element Diff respectively.

tree diff

According to strategy 1, React compares fiber trees hierarchically, comparing only sibling elements. Sibling refers to the children of the same parent node (the ancestors above are all the same), not the same depth of the tree.

As shown in the figure above, the React Tree Diff uses depth-first traversal, so the elements to be compared are all the same as their ancestors. In other words, the elements circled in the box with the same color are compared. For example, child nodes C and D under node A in the left tree are compared with C, D and E under node A in the right tree.

When elements move across hierarchies, as shown in the following figure:The React Diff process does not directly move subtree A to subtree B. Instead, the following operations are performed:

  1. Delete node A from the root node
  2. Create child node A under node B
  3. Create nodes C and D under the newly created child node A

component diff

The comparison between components, as long as they are of different types, is judged to be two different tree structures and replaced directly.

For example, in the following two trees, the B node on the left and the K node on the right are identical except that they have different types (e.g., B is of div type and K is of P type). However, react still directly replaces the whole node. The actual transformation is:

  1. Create K node under root node
  2. Create nodes E and F under node K
  3. Create nodes G and H under node F
  4. Delete child node B from the root node

Although the performance is better if the child element is reused by changing the type in this example, in the case of timing application development, there are very few cases in which the child element is exactly the same when the type is inconsistent, and too much judgment on such cases can increase timing complexity and reduce average performance.

element diff

React compares elements at the same level using keys to identify which elements can be rendered stably. There are three operations for inserting, deleting and moving elements of the same class.

The tree on the left wants to convert to the tree on the right:

The actual transformation is as follows:

  1. Move child node A of the root node to the next child node B
  2. Add E child nodes under the root node
  3. Example Delete child node C from the root node

Combine the source code to see diff

The whole process

The Diff algorithm starts with the reconcileChildren function and, depending on whether or not the current Fiber exists, decides whether to directly render the new ReactElement content or to diff it with the current Fiber.

export function reconcileChildren(
  current: Fiber | null.// The current fiber node
  workInProgress: Fiber, Fiber / / parent
  nextChildren: any.// The newly generated ReactElement content
  renderLanes: Lanes, // Render priority
) {
  if (current === null) {
    // If the current fiber node is empty, the new ReactElement content directly generates a new fiber
    workInProgress.child = mountChildFibers(
      workInProgress,
      null,
      nextChildren,
      renderLanes,
    );
  } else {
    // If the current fiber node is not empty, diff with the newly generated ReactElement contentworkInProgress.child = reconcileChildFibers( workInProgress, current.child, nextChildren, renderLanes, ); }}Copy the code

Since we are mainly learning the Diff algorithm, we are not concerned with the mountChildFibers function for the moment, focusing on reconcileChildFibers.

function reconcileChildFibers(
  returnFiber: Fiber, Fiber / / parent
  currentFirstChild: Fiber | null.// The parent fiber is the first subfiber to compare
  newChild: any.// Updated react. Element content
  lanes: Lanes, // Update priority
) :Fiber | null {
  
  // ReactElement is created with the fragment type
  const isUnkeyedTopLevelFragment =
    typeof newChild === 'object'&& newChild ! = =null &&
    newChild.type === REACT_FRAGMENT_TYPE &&
    newChild.key === null;
  if (isUnkeyedTopLevelFragment) {
    newChild = newChild.props.children;
  }

  // The updated React.Element is single-node processing
  if (typeof newChild === 'object'&& newChild ! = =null) {
    switch (newChild.$$typeof) {
      // Regular react elements
      case REACT_ELEMENT_TYPE:
        return placeSingleChild(
          reconcileSingleElement(
            returnFiber,
            currentFirstChild,
            newChild,
            lanes,
          ),
        );
      / / the react. Portal type
      case REACT_PORTAL_TYPE:
        return placeSingleChild(
          reconcileSinglePortal(
            returnFiber,
            currentFirstChild,
            newChild,
            lanes,
          ),
        );
      / / the react. Lazy type
      case REACT_LAZY_TYPE:
        if (enableLazyElements) {
          const payload = newChild._payload;
          const init = newChild._init;
          returnreconcileChildFibers( returnFiber, currentFirstChild, init(payload), lanes, ); }}// The updated react. Element is multi-node processing
    if (isArray(newChild)) {
      return reconcileChildrenArray(
        returnFiber,
        currentFirstChild,
        newChild,
        lanes,
      );
    }

    // Separate processing of iterator functions
    if (getIteratorFn(newChild)) {
      return reconcileChildrenIterator(
        returnFiber,
        currentFirstChild,
        newChild,
        lanes,
      );
    }

    throwOnInvalidObjectType(returnFiber, newChild);
  }

  // Type handling of plain text nodes
  if (typeof newChild === 'string' || typeof newChild === 'number') {
    return placeSingleChild(
      reconcileSingleTextNode(
        returnFiber,
        currentFirstChild,
        ' ' + newChild,
        lanes,
      ),
    );
  }

  if (__DEV__) {
    if (typeof newChild === 'function') { warnOnFunctionType(returnFiber); }}// Remove all old subfibers from the parent node
  return deleteRemainingChildren(returnFiber, currentFirstChild);
}
Copy the code

The entry function accepts four parameters: returnFiber, currentFirstChild, newChild, and lanes. According to the type of newChid, we focus on several common diff types. Diff for single React elements, plain text types, and array types.

Therefore, different ReactElement flows are as follows:

The new content is REACT_ELEMENT_TYPE

When the newly created nodes are of type Object, we look at the DIff of type REACT_ELEMENT_TYPE, which is placeSingleChild(reconcileSingleElement(…). ) function.

For the reconcileSingleElement function, look at the source code:

function reconcileSingleElement(
  returnFiber: Fiber, Fiber / / parent
  currentFirstChild: Fiber | null.// Parent fiber The first subfiber to compare
  element: ReactElement, // Current ReactElement content
  lanes: Lanes, // Update priority
) :Fiber {
  const key = element.key;
  let child = currentFirstChild;
  // Handle the case where the old fiber has multiple nodes and the new fiber has one node
  // Loop through the old child fiber under the parent fiber until the loop is complete or the key and type are the same as the new node
  while(child ! = =null) {
    if (child.key === key) {
      const elementType = element.type;
      if (elementType === REACT_FRAGMENT_TYPE) {
        if (child.tag === Fragment) {
        
          // If the new ReactElement and the old Fiber are both fragments with the same key
          // Add Deletion side effects to all sibling nodes behind the old fiber, for dom update Deletion
          deleteRemainingChildren(returnFiber, child.sibling);
          
          // Clone a new fiber using useFiber based on the old fiber and the new props. Children with index 0 and sibling null
          // This is called fiber multiplexing
          const existing = useFiber(child, element.props.children);
          existing.return = returnFiber;
          if (__DEV__) {
            existing._debugSource = element._source;
            existing._debugOwner = element._owner;
          }
          returnexisting; }}else {
        if (
          // If the key and type of the new ReactElement and the old Fiber are the same
          child.elementType === elementType ||
          (__DEV__
            ? isCompatibleFamilyForHotReloading(child, element)
            : false) ||
          (enableLazyElements &&
            typeof elementType === 'object'&& elementType ! = =null &&
            elementType.$$typeof === REACT_LAZY_TYPE &&
            resolveLazy(elementType) === child.type)
        ) {
          // Add Deletion side effects to all sibling nodes behind the old fiber, for dom update Deletion
          deleteRemainingChildren(returnFiber, child.sibling);
          // Reuse the new node via useFiber and return
          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;
          }
          returnexisting; }}// If the key is the same but the type is different, it does not match. Remove the old fiber and its successor fiber
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      // If the key is different, add a side effect flag on the current old fiber and continue traversing its sibling nodes
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }

  Fiber with the same key and type is not matched
  if (element.type === REACT_FRAGMENT_TYPE) {
    // If the new node is a fragment, createFiberFromFragment creates a new fragment type fiber and returns it
    const created = createFiberFromFragment(
      element.props.children,
      returnFiber.mode,
      lanes,
      element.key,
    );
    created.return = returnFiber;
    return created;
  } else {
    // createFiberFromElement Creates fiber and returns
    const created = createFiberFromElement(element, returnFiber.mode, lanes);
    created.ref = coerceRef(returnFiber, currentFirstChild, element);
    created.return = returnFiber;
    returncreated; }}Copy the code

The reconcileSingleElement function iterates through all the old subfibers under the parent fiber, looking for subfibers with the same key and type as the newly generated ReactElement. During each iteration of the comparison:

  • If the current old subfiber is inconsistent with the new content key or type, add the current old subfiberDeletionSide effects flags (for dom updates to remove) continue to compare the next old sub-fiber
  • If the current old subfiber is consistent with the key or type of the new content, it is judged as reusable and passesdeleteRemainingChildrenAdd all sibling fibers after this subfiberDeletionSide effects are marked and then passeduseFiberBased on this sub-fiber and the props of the new content, a new fiber is generated for reuse to end the traversal.

If no subfiber related to the new content key or Type is found after traversal, all the old subfibers under the parent fiber have been marked with Deletion side effect. Create a new fiber based on the new content with createFiberFromElement and return it to the parent fiber.

PlaceSingleChild placeSingleChild

function placeSingleChild(newFiber: Fiber) :Fiber {
  if (shouldTrackSideEffects && newFiber.alternate === null) {
    newFiber.flags |= Placement;
  }
  return newFiber;
}
Copy the code

Something even simpler is done in placeSingleChild, which marks the new fibers generated in reconcileSingleElement with Placement marks to indicate that they are inserted when dom updates are rendered.

So the diff for the REACT_ELEMENT_TYPE type is summarized as follows:

The new content is plain text

When the Typeof newly created nodes is a String or number, they are plain text nodes, using placeSingleChild(reconcileSingleTextNode(…). ) function diff.

As placeSingleChild said earlier, we mainly look at the reconcileSingleTextNode source:

function reconcileSingleTextNode(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  textContent: string,
  lanes: Lanes,
) :Fiber {
  if(currentFirstChild ! = =null && currentFirstChild.tag === HostText) {
    // deleteRemainingChildren add Deletion side effects to all sibling nodes behind the old fiber, for Deletion when DOM updates
    // useFiber is passed into textContext to reuse the current fiber
    deleteRemainingChildren(returnFiber, currentFirstChild.sibling);
    const existing = useFiber(currentFirstChild, textContent);
    existing.return = returnFiber;
    return existing;
  }
  // If not matched, createFiberFromText creates a new fiber
  deleteRemainingChildren(returnFiber, currentFirstChild);
  const created = createFiberFromText(textContent, returnFiber.mode, lanes);
  created.return = returnFiber;
  return created;
}
Copy the code

Diff is easier when the new content is plain text, and you just need to determine the first old subtype of the current parent fiber:

  • When fiber is a text node,deleteRemainingChildrenAdd all siblings of the first old subfiberDeletionSide effects are marked and then passeduseFiberCreate a new fiber reuse based on the current fiber and textContent, and return it to the parent fiber
  • Otherwise, bydeleteRemainingChildrenAdd all old subfibersDeletionSide effects are marked and thencreateFiberFromTextCreate a new text type fiber node and return it to the parent fiber

So the flow for diff is as follows:

The new content is an array type

In both cases, one or more sub-FieBrs become a single fiber. When the new reconcileChildrenArray is an array, it means replacing one or more subfibers with multiple fibers, which is relatively complex. Let’s take a look at the reconcileChildrenArray source code:

function reconcileChildrenArray(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChildren: Array<*>,
  lanes: Lanes,
) :Fiber | null {
  // In the development environment, the system checks whether the key exists and is valid. Otherwise, a warning message is reported
  if (__DEV__) {
    let knownKeys = null;
    for (let i = 0; i < newChildren.length; i++) {
      constchild = newChildren[i]; knownKeys = warnOnInvalidKey(child, knownKeys, returnFiber); }}let resultingFirstChild: Fiber | null = null; // Finally return the first subfiber
  let previousNewFiber: Fiber | null = null;

  let oldFiber = currentFirstChild;
  let lastPlacedIndex = 0;
  let newIdx = 0;
  let nextOldFiber = null;
  // In actual application development, React finds that updates are much more common than additions and deletions, so updates are handled first
  // Find oldFiber to compare according to index of oldFiber and newChildren
  for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
    if (oldFiber.index > newIdx) {
      nextOldFiber = oldFiber;
      oldFiber = null;
    } else {
      nextOldFiber = oldFiber.sibling;
    }
    // Diff oldFiber and the new child with updateSlot to generate a new Fiber
    // updateSlot is similar to the above two types of diff. If oldFiber is reusable, a new fiber is generated based on the props of oldFiber and child. Otherwise return NULL
    const newFiber = updateSlot(
      returnFiber,
      oldFiber,
      newChildren[newIdx],
      lanes,
    );
    // If newFiber is null, it is not reusable and exits the first loop
    if (newFiber === null) {
      if (oldFiber === null) {
        oldFiber = nextOldFiber;
      }
      break;
    }
    if (shouldTrackSideEffects) {
      if (oldFiber && newFiber.alternate === null) { deleteChild(returnFiber, oldFiber); }}// Record the index of the reused oldFiber, and label the new fiber with Placement side effects
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    
    if (previousNewFiber === null) {
      // If the previous newFiber is null, this is the first generated newFiber, set to resultingFirstChild
      resultingFirstChild = newFiber;
    } else {
      // Otherwise build the chain relationship
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
    oldFiber = nextOldFiber;
  }

  if (newIdx === newChildren.length) {
    // newChildren: oldFiber (); // newChildren: oldFiber ()
    // Delete the oldFiber flag
    deleteRemainingChildren(returnFiber, oldFiber);
    return resultingFirstChild;
  }

  if (oldFiber === null) {
    // olderFiber is done
    // newChildren the remaining nodes are nodes that need to be added
    for (; newIdx < newChildren.length; newIdx++) {
      // Iterate over the remaining child and create a new fiber using createChild
      const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
      if (newFiber === null) {
        continue;
      }
      // Handle DOM movement, // record index, and label the new Fiber with Placement side effects
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      // Add the newly created fiber to the Fiber list tree
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
    return resultingFirstChild;
  }

  // oldFiber and newChildren are not iterated
  // mapRemainingChildren generates a map with oldFiber's key as key and oldFiber as value
  const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

  // Iterate over the remaining newChildren
  for (; newIdx < newChildren.length; newIdx++) {
    // Find fiber with key equal in mapRemainingChildren, create new fiber reuse
    const newFiber = updateFromMap(
      existingChildren,
      returnFiber,
      newIdx,
      newChildren[newIdx],
      lanes,
    );
    if(newFiber ! = =null) {
      if (shouldTrackSideEffects) {
        if(newFiber.alternate ! = =null) {
          // Delete the currently found fiber
          existingChildren.delete(
            newFiber.key === null? newIdx : newFiber.key, ); }}// Handle DOM movement, record index, and label the new Fiber with Placement side effects
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      // Add the newly created fiber to the Fiber list tree
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else{ previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; }}if (shouldTrackSideEffects) {
    // Add the Deletion side effect label on the rest of the old fiber
    existingChildren.forEach(child= > deleteChild(returnFiber, child));
  }

  return resultingFirstChild;
}
Copy the code

As you can see from the code above, React will iterate over old Fiber and newChildren when the new content is an array.

  1. First, newChildren is traversed in the first round, passing the current oldFiber with the current newChild subscript of newIdxupdateSlotThe diff process is similar to that of the single-node diff, and the result of the diff is returned:
    • If the key and type of oldFiber and newIdx are the same after diff, it is reusable. Generate a new fiber based on oldFiber and newChild props, passplaceChildType in the newly generated fiberPlacementSide effects are marked, and the new fiber builds a linked list tree relationship with the new fiber generated by previous traversal. Then continue traversal, diff the next oldFiber and newFiber subscript newIdx
    • If the key or type of oldFiber and newIdx are inconsistent after diff, it indicates that the oldFiber and newIdx cannot be reused. The result returned is NULL, and the first round of traversal is complete
  2. After the first iteration, the following scenarios may be performed:
    • If the newChildren traversal is completed, the remaining oldFiber is to be deleteddeleteRemainingChildrenType the rest of the oldFiberDeletionSide effect marker
    • If oldFiber traverses, the remaining newChildren need to be added. Traverses the remaining newChildren and passescreateChildCreate a new Fiber,placeChildType in the newly generated fiberPlacementSide effects are marked and added to the Fiber list tree.
    • If oldFiber and newChildren are not traversed, passmapRemainingChildrenCreate a map with the remaining oldFiber’s key as key and oldFiber as value. It then iterates through the rest of the newChildren, passingupdateFromMapCreate a new fiber with the same key in the map (if found, create it based on oldFiber and newChild props, otherwise create it based on newChild), delete the current key from the map, and thenplaceChildType in the newly generated fiberPlacementSide effects are marked and added to the Fiber list tree. After traversing, existingChildren still have oldFiber, which is the fiber to be deleted,deleteChildThe playDeletionSide effect markers.

So the overall process is as follows:

Render after diff

After the end of the diFF process, a new fiber list tree will be formed, and fiber in the list tree will be marked with side effects through flags field, mainly including the following:

  1. Deletion: The corresponding DOM will be deleted during rendering
  2. Update: The properties to be updated are stored in fiber.updateQueue, and the DOM is updated during rendering
  3. Placement: A Placement can be an insert or a move, but in fact both are insert actions. React updates will first look for the sibling of the fiber to insert, if it finds one that executes the DOMinsertBeforeMethod, which executes the DOM if not foundappendChildMethod, so as to achieve the accuracy of new node insertion position

After the completeUnitWork phase is complete, React creates an effectList of which fibers need to be inserted, deleted, or updated based on flags in the Fiber list tree. The actual DOM nodes are updated later in the Commit phase, which is covered in detail in the next chapter.