The React Diff algorithm

Image source unsplash.com/photos/BHSs…

preface

We know that the complexity of comparing two DOM trees is O(n³) even if the optimal algorithm is used, where N is the number of elements in the tree. If you use this algorithm in React, showing 1000 elements would require a billion comparisons. The overhead was too high, so React had to reduce the complexity of the diff algorithm.

Optimal DOM Diff algorithm

Here’s a concept called Tree Edit Distance. Let’s look at edit distance first.

Edit distance

Edit distance quantifies the degree of difference between two strings by calculating the minimum operand required to convert a character into an example string.

For example, calculate the editing distance between Kitten and Sitting:

Kitten → sitten (change k to s)
Sitten → sittin (change e to I)
Sittin → sitting (last added g)

Therefore, the editing distance is 3, and the algorithm refers to Levenshtein’s algorithm.

Tree Edit Distance

The edit distance of a Tree is the minimum operand required to map a Tree to an exceptional Tree.

The optimal DOM Diff algorithm complexity O(n³) origin

The traditional Diff algorithm needs to find the minimum update method of two trees, so it needs to compare whether each leaf node of the two trees is the same in pairs, which requires the time complexity of O(n^2). After finding the difference between two trees, it needs to update (move, create, delete) and traverse again, so it is O(n^3).

React For an update component, it compares the current component to the Fiber node that it used when it was last updated (i.e., the Diff algorithm), and generates a new Fiber node.

Related concepts:

The current Fiber. If the DOM node is already on the page, current Fiber represents the corresponding Fiber node of the DOM node.
WorkInProgress Fiber. If the DOM node will be rendered to the page in this update, workInProgress Fiber represents the corresponding Fiber node of the DOM node.
JSX object. That is, the result returned by the Render method of the ClassComponent, or the result of the FunctionComponent call. JSX objects contain information that describes DOM nodes.

The essence of the Rect Diff algorithm is to compare 1 (Current Fiber) and 3 (JSX object) to generate 2 (workInProgress Fiber).

React presets three restrictions to reduce the DOM Diff algorithm’s complexity:

Diff is performed only on sibling elements. React does not attempt to reuse a DOM node if it crosses the hierarchy in two updates.
Two different types of elements produce different trees. If the element changes from div to P, React destroys the div and its descendants and creates a new p and its descendants.
The developer can set the key attribute to tell the render which child elements can be saved in different renders.

React Diff reduces the time complexity to O(n) just by comparing the same level.

The React Diff algorithm starts with the reconcileChildFibers’ entry function, which calls different handlers based on the newChild, or JSX object, type.

ReconcileChildFibers source

// Select different diff functions according to the newChild type
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;
    }

    
    if (typeof newChild === 'object'&& newChild ! = =null) {
      / / the object type
      switch (newChild.$$typeof) {
        case REACT_ELEMENT_TYPE:
          return placeSingleChild(
            reconcileSingleElement(
              returnFiber,
              currentFirstChild,
              newChild,
              lanes,
            ),
          );
        case REACT_PORTAL_TYPE:
          return placeSingleChild(
            reconcileSinglePortal(
              returnFiber,
              currentFirstChild,
              newChild,
              lanes,
            ),
          );
        case REACT_LAZY_TYPE:
          if (enableLazyElements) {
            const payload = newChild._payload;
            const init = newChild._init;
            returnreconcileChildFibers( returnFiber, currentFirstChild, init(payload), lanes, ); }}if (isArray(newChild)) {
        return reconcileChildrenArray(
          returnFiber,
          currentFirstChild,
          newChild,
          lanes,
        );
      }

      if (getIteratorFn(newChild)) {
        return reconcileChildrenIterator(
          returnFiber,
          currentFirstChild,
          newChild,
          lanes,
        );
      }

      throwOnInvalidObjectType(returnFiber, newChild);
    }

    if (typeof newChild === 'string' || typeof newChild === 'number') {
      return placeSingleChild(
        reconcileSingleTextNode(
          returnFiber,
          currentFirstChild,
          ' '+ newChild, lanes, ), ); }...// If none of the above matches, delete the node
    return deleteRemainingChildren(returnFiber, currentFirstChild);
  }
Copy the code

ReturnFiber is the parent of currentFiber, currentFirstChild is currentFiber, newChild is JSX object, and Lanes are priority dependent.

Diff can be divided into two types according to the number of nodes at the same level:

If the newChild type is Object, number, or String, there is only one node at the same level.
When newChild is Array, there are multiple nodes at the same level.

Diff of a single node

For a single node, we take the case of the type Object, which goes into the reconcileSingleElement.

if (typeof newChild === 'object'&& newChild ! = =null) {
     switch (newChild.$$typeof) {
        case REACT_ELEMENT_TYPE:
          returnplaceSingleChild( reconcileSingleElement( returnFiber, currentFirstChild, newChild, lanes, ), ); . }}Copy the code

ReconcileSingleElement source

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) {
          if (child.tag === Fragment) {
            deleteRemainingChildren(returnFiber, child.sibling);
            const existing = useFiber(child, element.props.children);
            existing.return = returnFiber;
            returnexisting; }}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) {
      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

The reconcileSingleElement method does the following:

Fiber node from last update`There is no`Corresponding DOM node

function App() {
	const [num, setNum] = useState(0);

	return (
		<div className="App" 
                onClick={()= >{ setNum(num + 1); }} ><h1>{num}</h1>
		</div>
	);
}

export default App;
Copy the code

For example, the code div above is first rendered with currentFirstChild null. CreateFiberFromElement is called to generate a new Fiber node and return.

if (element.type === REACT_FRAGMENT_TYPE) {

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

CreateFiberFromElement source

Fiber node from last update`There are`Corresponding DOM node

DOM nodes are reusable

 function reconcileSingleElement(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    element: ReactElement,
    lanes: Lanes,
  ) :Fiber {
    const key = element.key;
    let child = currentFirstChild;
    while(child ! = =null) {  // The Fiber node from the last update has a corresponding DOM node
      if (child.key === key) { // Compare keys to see if they are the same
        const elementType = element.type;
        if (elementType === REACT_FRAGMENT_TYPE) {
          if (child.tag === Fragment) {
            deleteRemainingChildren(returnFiber, child.sibling);
            const existing = useFiber(child, element.props.children);
            existing.return = returnFiber;
            returnexisting; }}else {
          if (
            child.elementType === elementType ||
            isCompatibleFamilyForHotReloading(child, element) ||
            (enableLazyElements &&
              typeof elementType === 'object'&& elementType ! = =null &&
              elementType.$$typeof === REACT_LAZY_TYPE &&
              resolveLazy(elementType) === child.type)
          ) {// Same key, same type
          
            // Mark the sibling fiber as deleted
            deleteRemainingChildren(returnFiber, child.sibling);
            
            // Copy the Fiber node from the last update as the Fiber node for this update and return it
            const existing = useFiber(child, element.props);
            
            existing.ref = coerceRef(returnFiber, child, element);
            existing.return = returnFiber;
            
            returnexisting; }}// Same key but different type
        // Mark this fiber and its sibling fiber as deleted
        deleteRemainingChildren(returnFiber, child);
        break;
      } else { // If the key is different, mark the fiber as deleted
        deleteChild(returnFiber, child);
      }
      child = child.sibling;
    }

    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

Multi-node DIff

The children of a JSX object returned by a multi-node is an array, as in the following example.

return (
		<div className="App">
			<ul>
				<li key="0">0</li>
				<li key="1">1</li>
				<li key="2">2</li>
			</ul>
		</div>
	);
Copy the code

The newChild parameter for the reconcileChildFibers is of the type Array.

.if (isArray(newChild)) {
        returnreconcileChildrenArray( returnFiber, currentFirstChild, newChild, lanes, ); }...Copy the code

ReconcileChildrenArray source

  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;
    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) {
        if (oldFiber && newFiber.alternate === null) {
          deleteChild(returnFiber, oldFiber);
        }
      }
      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;
      oldFiber = nextOldFiber;
    }

    if (newIdx === newChildren.length) {
      deleteRemainingChildren(returnFiber, oldFiber);
      return resultingFirstChild;
    }

    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) {
          resultingFirstChild = newFiber;
        } else {
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
      return resultingFirstChild;
    }

    const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

    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

Implications for several important variables:

resultingFirstChild: represents workInProgress Fiber, and connects sibling segments via sibling pointer

Points.

PreviousNewFiber: Intermediate variable, connect the last generated Fiber node to the current generated Fiber node (previousnewFiber.Sibling = newFiber).
OldFiber: indicates the current Fiber node traversed.
NextOldFiber: indicates the next Fiber node of the current Fiber node traversed.
NewIdx: represents the index of the JSX object currently traversed in the array.
LastPlacedIndex: represents the position of the newly created Fiber node relative to the DOM node on the page.

The reconcileChildrenArray method eventually returns resultingFirstChild;

The resources

React Technology revealed

The React Diff algorithm

preface

Optimal DOM Diff algorithm

The optimal DOM Diff algorithm complexity O(n³) origin