preface

The React source reference version is 17.0.3. This is the React source series eighth, suggest that the first to see the source students from the first to see, so more coherent, there are source series links below.

The warm-up to prepare

background

In order to avoid heavy and frequent manipulation of the DOM, React introduced the virtual DOM, which was replaced by the Fiber tree after version 16. But how to efficiently replace the old tree with the new tree when the update occurs is a difficult problem. According to some general algorithm solutions, even if you use the optimal algorithm, the complexity of the algorithm is still O(n 3), where n is the number of elements.

This was not what React wanted, and with that in mind, the React team came up with a bolder idea. Since the cost of replacing a tree was so high, I chose to rebuild a tree.

ReactThe team approach

  1. When comparing two trees, the root node of the two trees is first compared. If the root node is a different type of element, React will not consider replacing the root node and then recursing. Instead, React will abandon the tree and create a new one. The recursion is the same, when the node type is different, React will delete the node and all the children below, and then rebuild the tree.

  2. When comparing two component elements of the same type:

    • classComponent instances remain unchanged (so different when renderingstateIs consistent), only component instances are updatedprops.
    • Function components are re-executed (so you need hooks to record the state).

  3. When comparing two React elements of the same type, React retains the DOM node and only compares and updates the changed attributes.

  4. With the introduction of key, developers manually set the element key value to mark elements. React compares elements based on key.

So those are the results of the React Diff algorithm. Ok, so let’s figure out what the React Diff algorithm does, and let’s see how it does it.

BeginWork phase

Compare different types of elements

The code is my deleted pseudo code, for reference only.

if (child.elementType === element.type) { deleteRemainingChildren(returnFiber, child.sibling); // Clone current fiber and replace pendingProps with the current element.props var _existing3 = useFiber(child, element.props); _existing3.return = returnFiber; return _existing3; } else {// deleteRemainingChildren(returnFiber, child); Var _created4 = createFiberFromElement(element, returnFiber. Mode, lanes); var _created4 = createFiberFromElement(element, returnFiber. _created4.return = returnFiber; return _created4; }Copy the code

If the React element type is not the same as the element type before or after the update, the React element type is not the same as the element type before or after the update. If the React element type is not the same as the element type before or after the update, the React element type is not the same as the element type after the update. Rebuild yourself based on the new fiber.

Compare elements of the same type

When two elements are of the same type, React will consider reusing the existing fiber for performance reasons, keeping the DOM element but replacing fiber.pendingprops. Because the information for our DOM elements is recorded on the props, React simply replaces the old props with the new ones.

if (child.elementType === element.type) { deleteRemainingChildren(returnFiber, child.sibling); // Clone current fiber and replace pendingProps with the current element.props var _existing3 = useFiber(child, element.props); _existing3.return = returnFiber; return _existing3; }Copy the code

The use of the key

Very simple code, but a lot of credit. React will compare the key values of the new and old nodes to determine whether the new and old nodes are related. If so, it will update, and if not, it will return null.

So under what circumstances is it possible to return null?

The answer is:

  • Insert new nodes;
  • The node was deleted.
  • Node order is changed;
{ if (newChild.key === key) { if (newChild.type === REACT_FRAGMENT_TYPE) { return updateFragment(returnFiber, oldFiber, newChild.props.children, lanes, key); } return updateElement(returnFiber, oldFiber, newChild, lanes); } else { return null; }}Copy the code

When newFiber returns null, oldFiber will reset back to the previous value, ensuring that the key is valid, and then jump out of the loop to match the key with oldFiber.

if (oldFiber.index > newIdx) {
    nextOldFiber = oldFiber;
    oldFiber = null;
}
if (newFiber === null) {
    if (oldFiber === null) {
      oldFiber = nextOldFiber;
    }
    break;
}
Copy the code

After the loop is broken, the remaining unmatched oldfibers are stored in the Map structure with key (without key, index is used)

var existingChildren = mapRemainingChildren(returnFiber, oldFiber)
Copy the code

React then iterates over the newFiber array from where there is no successful key match, and matches the remaining newFiber from the oldFiber Map structure to maximize reuse and match as long as it matches (it will be removed from existingChildren after successful matches). If it does not match, it is added and a corresponding node is created.

for (; newIdx < newChildren.length; newIdx++) { var _newFiber2 = updateFromMap(existingChildren, returnFiber, newIdx, newChildren[newIdx], lanes); if (_newFiber2 ! == null) { if (shouldTrackSideEffects) { if (_newFiber2.alternate ! == null) { existingChildren.delete(_newFiber2.key === null ? newIdx : _newFiber2.key); } } lastPlacedIndex = placeChild(_newFiber2, lastPlacedIndex, newIdx); if (previousNewFiber === null) { resultingFirstChild = _newFiber2; } else { previousNewFiber.sibling = _newFiber2; } previousNewFiber = _newFiber2; }}Copy the code

Comparison of child node positions

When a React parent is an element of the same type, replace props and proceed recursion downwards. Each child node updates in the same way as the parent node:

  • Compare whether the element types are the same;
  • replaceproprs;

It is worth noting that when there are more than one child node, there may be some cases of adding or deleting nodes, or changing the order of nodes. In this case, it is necessary to consider whether the positions of these children nodes have changed.

function placeChild(newFiber, lastPlacedIndex, newIndex) { newFiber.index = newIndex; var current = newFiber.alternate; if (current ! == null) { var oldIndex = current.index; If (oldIndex < lastPlacedIndex) {// move newFiber. Flags = Placement; return lastPlacedIndex; } else {// return oldIndex in the same position; }} else {// newFiber. Flags = Placement; return lastPlacedIndex; }}Copy the code

The child node is updated

When the child node has been updated, if there is still an old node, it will be directly deleted, and no further comparison will be considered

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

CompleteWork phase

As mentioned in the previous article, there is an upward lookup process during the completeWork phase. If it is an update, it creates an updateQueue, updateQueue, which is the result of the diff of the old and new props. The diff code here is too long, so I’ll cut it down

function diffProperties(domElement, tag, lastRawProps, nextRawProps, rootContainerElement) { { validatePropertiesInDevelopment(tag, nextRawProps); } var updatePayload = null; var lastProps; var nextProps; switch (tag) { case 'input': lastProps = getHostProps(domElement, lastRawProps); nextProps = getHostProps(domElement, nextRawProps); updatePayload = []; break; case 'option': ... // break; case 'select': ... // break; case 'textarea': ... // break; default: lastProps = lastRawProps; nextProps = nextRawProps; break; } assertValidProps(tag, nextProps); var propKey; var styleName; var styleUpdates = null; for (propKey in lastProps) { ... } for (propKey in nextProps) { ... } if (styleUpdates) { { validateShorthandPropertyCollisionInDev(styleUpdates, nextProps[STYLE]); } (updatePayload = updatePayload || []).push(STYLE, styleUpdates); } return updatePayload; }Copy the code

In the code above, there is a distinction between the form and the normal DOM element. Because the form can hold the user interaction state, React needs to assemble the form state into props. Distinguish prop is style, dangerouslySetInnerHTML, children and some other properties for different treatment, mainly is to compare lastProps and nextProps, nextProps and there is no lastProps reset, NextProps have different versions than lastProps to add to updates.

conclusion

The React Diff algorithm isn’t that complicated.

That’s the way it is. Simple.

To sum up:

Diff algorithm occurs in two stages, beginWork and completeWork respectively.

In the beginWork phase, the element types before and after the update will be compared:

  • If not, delete the updated element and its children, and rebuild based on the new element.
  • If they are the same, the DOM element is reused and replaced onlyprops;

When the parent element type is the same and there are multiple child nodes, there will be scenarios where key is used. React will reuse oldFiber based on key as much as possible to ensure better performance.

React will diff the props of the new and old nodes during the completeWork phase, and then traverse them to find the changes and add them to the update queue. The update is rendered during the COMMIT phase.

He came up with a formula: seek common ground without shelving differences. The same is the key, and the last is the props

After reading this article, we can understand the following questions:

  1. ReactWhy do it?diffAlgorithm?
  2. ReactthediffHow does the algorithm work?
  3. ReactthediffAt what stage does the algorithm take place?
  4. ReactThe elements of thekeyWhat does it do?
  5. ReactHow to get throughkeyImplement efficientdiff?

Article series arrangement:

  1. React Fiber;
  2. React source series 2: React rendering mechanism;
  3. React source series 3: hooks useState, useReducer;
  4. React code series 4: hooks useEffect;
  5. React code Series 5: Hooks useCallback, useMemo;
  6. React source Series 6: Hooks useContext;
  7. React source series 7: React synthesis events;
  8. React source series eight: React diff algorithm;
  9. React source series 9: React update mechanism;
  10. React source series 10: Concurrent Mode;

Reference:

React official documents;

Making;