The cause of
React key I believe you are familiar with it, and I don’t need to say more. However, the use of key may not be so strict, and key may not be given, or index may be given. In fact, there will be no problem in general, at most there will be some loss of performance. However, improper use of key in some specific cases may also lead to bugs, such as the following situation.
Bug caused by key
In a background management system, there is a menu to choose different options on the left, and different videos on the right. However, when the left menu is switched, although the cover image of the video on the right is reloaded, the content of the video after clicking play is not new, it is still the video of the previous TAB, which looks like it has not been re-rendered. And after checking the code, I found that I did not add the key value to the table, and after adding the key value is indeed good. Let’s look at the video code.
<video controls={true} poster={poster}>
<source src={videoUrl} />
</video>
Copy the codeSo here’s the question:
- If I don’t add a key, shouldn’t React interpret the lists as completely different and re-render them?
- The SRC in the video has indeed changed, but the video is still the same
After a search, I first found the answer to the second question: when the source is written in this way, if only SRC is changed, the video will not reload the video. The correct way is to unload the DOM and reload it again, so that the corresponding video can be pulled correctly. Although I feel that this is not common sense, the result is that, without the key, the source is removed and SRC is used in the video to solve the bug. So it looks like this
<video controls={true} poster={poster} src={videoUrl} />
Copy the codeSo let’s go back to the first question. I didn’t give the key. React won’t re-render the DOM that they all think is different?
The diff algorithm
What’s the key value for? In the React diff process, if two nodes with the same key are encountered, React will consider them as the same nodes and reuse this node in the next rendering to reduce the rendering content and improve performance. So what’s the Diff algorithm for React?
Traditional diff algorithm
I haven’t studied carefully to find out exactly what the minimum time complexity is for the changes of the two trees. According to online information, the current minimum time complexity is also O(N3)O(n^3)O(N3), while the current time complexity of the React diff algorithm is O(n)O(n)O(n). Neither of them is on the same order of magnitude, so React’s Diff must have lost something.
React diff algorithm
To reduce algorithm complexity, React imposes some restrictions on front-end development habits:
- React diff only peer elements. If a DOM node crosses a hierarchy, it will never be reused.
- If the TYPE of a DOM node changes, the node and its descendants are destroyed and re-rendered
- React uses the key to determine which nodes belong to the same node
So from these three we can conclude that in order to make our page less unnecessary rendering, we can:
- Don’t change the DOM hierarchy lightly
- Don’t change DOM types easily
- Make good use of the key
The diff implementation
React implements diff. How does react implement diff
The entry function
The entrance to the diff function call reconcileChildFibersreconcileChildFibersreconcileChildFibers, before going through a series of operation, finally came to a diff link, B: what did the react in reconcileChildFibersreconcileChildFibersreconcileChildFibers what
// returnFiber is the last Fiber tree we will render
// currentFirstChild is the currentFirstChild
// newChild is all the child elements to be mounted
// lanes Specifies the priority
function reconcileChildFibers(returnFiber, currentFirstChild, newChild, lanes) {
// Check whether newChild is Fragment
var isUnkeyedTopLevelFragment = typeof newChild === 'object'&& newChild ! = =null && newChild.type === REACT_FRAGMENT_TYPE && newChild.key === null;
// If it is a Fragment, remove the contents of the Fragment
if (isUnkeyedTopLevelFragment) {
newChild = newChild.props.children;
}
// Determine if newChild is an object
var isObject = typeof newChild === 'object'&& newChild ! = =null;
// If it is an object, it is processed according to the different type
if (isObject) {
switch (newChild.$$typeof) {
case REACT_ELEMENT_TYPE:
return placeSingleChild(reconcileSingleElement(returnFiber, currentFirstChild, newChild, lanes));
case REACT_PORTAL_TYPE:
returnplaceSingleChild(reconcileSinglePortal(returnFiber, currentFirstChild, newChild, lanes)); }}// Check whether it is a text type
if (typeof newChild === 'string' || typeof newChild === 'number') {
return placeSingleChild(reconcileSingleTextNode(returnFiber, currentFirstChild, ' ' + newChild, lanes));
}
// Check if it is an array
if (isArray$1(newChild)) {
return reconcileChildrenArray(returnFiber, currentFirstChild, newChild, lanes);
}
// Determine whether it is iterable
if (getIteratorFn(newChild)) {
return reconcileChildrenIterator(returnFiber, currentFirstChild, newChild, lanes);
}
// This is all error handling
if (isObject) {
throwOnInvalidObjectType(returnFiber, newChild);
}
{
if (typeof newChild === 'function') { warnOnFunctionType(returnFiber); }}if (typeof newChild === 'undefined' && !isUnkeyedTopLevelFragment) {
// If the new child is undefined, and the return fiber is a composite
// component, throw an error. If Fiber return types are disabled,
// we already threw above.
switch (returnFiber.tag) {
case ClassComponent:
{
{
var instance = returnFiber.stateNode;
if (instance.render._isMockFunction) {
// We allow auto-mocks to proceed as if they're returning null.
break; }}}// Intentionally fall through to the next case, which handles both
// functions and classes
// eslint-disable-next-lined no-fallthrough
case Block:
case FunctionComponent:
case ForwardRef:
case SimpleMemoComponent:
{
{
{
throw Error((getComponentName(returnFiber.type) || 'Component') + "(...). : Nothing was returned from render. This usually means a return statement is missing. Or, to render nothing, return null.");
}
}
}
}
} // Remaining cases are all treated as empty.
return deleteRemainingChildren(returnFiber, currentFirstChild);
}
Copy the codeAs you can see, this entry function dispatches different types to different subfunctions for processing, relative to a routing file. So how React handles different types of nodes, let’s see.
Peer single node diff
If there is only one node at the same level, will enter reconcileSingleElementreconcileSingleElementreconcileSingleElement to deal with, let’s take a look at what did in this operation.
function reconcileSingleElement(returnFiber, currentFirstChild, element, lanes) {
var key = element.key;
var child = currentFirstChild;
// First check whether this node exists before
while(child ! = =null) {
// Determine the key if there are old nodes
if (child.key === key) {
// Handle according to the tag type
switch (child.tag) {
case Fragment:
{
if (element.type === REACT_FRAGMENT_TYPE) {
deleteRemainingChildren(returnFiber, child.sibling);
var existing = useFiber(child, element.props.children);
existing.return = returnFiber;
{
existing._debugSource = element._source;
existing._debugOwner = element._owner;
}
return existing;
}
break;
}
case Block:
// We intentionally fallthrough here if enableBlocksAPI is not on.
// eslint-disable-next-lined no-fallthrough
default:
{
if (child.elementType === element.type || ( // Keep this check inline so it only runs on the false path:
isCompatibleFamilyForHotReloading(child, element))) {
deleteRemainingChildren(returnFiber, child.sibling);
// reuse the current node
var _existing3 = useFiber(child, element.props);
_existing3.ref = coerceRef(returnFiber, child, element);
_existing3.return = returnFiber;
{
_existing3._debugSource = element._source;
_existing3._debugOwner = element._owner;
}
return _existing3;
}
break; }}// Didn't match.
deleteRemainingChildren(returnFiber, child);
break;
} else {
deleteChild(returnFiber, child);
}
child = child.sibling;
}
// No old node can be created
if (element.type === REACT_FRAGMENT_TYPE) {
var created = createFiberFromFragment(element.props.children, returnFiber.mode, lanes, element.key);
created.return = returnFiber;
return created;
} else {
var _created4 = createFiberFromElement(element, returnFiber.mode, lanes);
_created4.ref = coerceRef(returnFiber, currentFirstChild, element);
_created4.return = returnFiber;
return_created4; }}Copy the codeAs you can see, the first thing it does is determine if this node exists before, and if it doesn’t exist before, it doesn’t reuse, so it just creates a new insert. If there are old nodes, the key and typ e are the same. Note that react will reuse this node only if the key is the same type. React will delete the node if the key or type is different, create a new node and return.
Multiple nodes of the same level diff
Multiple nodes at the same level of the diff is much more complicated than a single node, it will enter reconcileChildrenArrayreconcileChildrenArrayreconcileChildrenArray to deal with, we slowly to see.
function reconcileChildrenArray(returnFiber, currentFirstChild, newChildren, lanes) {{// Check the key, if the same key appears here will give a warning
var knownKeys = null;
for (var i = 0; i < newChildren.length; i++) {
varchild = newChildren[i]; knownKeys = warnOnInvalidKey(child, knownKeys, returnFiber); }}// the result after diff
var resultingFirstChild = null;
// The next fiberNode to the new Fiber tree
var previousNewFiber = null;
// fiberNode of the old Fiber tree, i.e. before the update
var oldFiber = currentFirstChild;
// Index of currently reusable nodes
var lastPlacedIndex = 0;
// Index of the new child
var newIdx = 0;
// Next old fiberNode
var nextOldFiber = null;
// Use newIndex to iterate
for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
// What can I do to enter the first branch
if (oldFiber.index > newIdx) {
nextOldFiber = oldFiber;
oldFiber = null;
} else {
// Sibling is a fiberNode sibling, so use nextOldFiber to store the next fiberNode to be compared
nextOldFiber = oldFiber.sibling;
}
// Get a new fiberNode object by comparing oldFiber with newFiber
// This object can be reused, new, or null
var newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx], lanes);
// Break the loop if null
if (newFiber === null) {
if (oldFiber === null) {
oldFiber = nextOldFiber;
}
break;
}
// optimize the item
if (shouldTrackSideEffects) {
if (oldFiber && newFiber.alternate === null) {
// We matched the slot, but we didn't reuse the existing fiber, so we
// need to delete the existing child.deleteChild(returnFiber, oldFiber); }}// Record the index of the current reusable node
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
// is the initial node
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
// Set the sibling to newFiber
previousNewFiber.sibling = newFiber;
}
// List moves, pre assigns the current node
previousNewFiber = newFiber;
// Assign old to the next object to compare
oldFiber = nextOldFiber;
}
// If newIdx is length, newChild is already iterated
// Then the remaining oldFiber nodes must be deleted
if (newIdx === newChildren.length) {
deleteRemainingChildren(returnFiber, oldFiber);
return resultingFirstChild;
}
// if oldFiber is null, then the oldFiber is already traversed
// The rest of the newChild node is the new node, directly inserted
if (oldFiber === null) {
for (; newIdx < newChildren.length; newIdx++) {
var _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;
}
// If the node breaks, the node changes
// Collect oldFiber that is not traversed at this time, use key as the key value, and store it in map structure
var existingChildren = mapRemainingChildren(returnFiber, oldFiber); // Keep scanning and use the map to restore deleted items as moves.
// Iterate over newChild, using key to find the node in existingChildren
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); }}// Assign an effectTag when it is found
lastPlacedIndex = placeChild(_newFiber2, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
resultingFirstChild = _newFiber2;
} else{ previousNewFiber.sibling = _newFiber2; } previousNewFiber = _newFiber2; }}if (shouldTrackSideEffects) {
// Any existing children that weren't consumed above were deleted. We need
// to add them to the deletion list.
existingChildren.forEach(function (child) {
return deleteChild(returnFiber, child);
});
}
// Return the final result
return resultingFirstChild;
}
Copy the codeFirst, react checks each child’s key as soon as it comes in. In warnOnInvalidKeywarnOnInvalidKeywarnOnInvalidKey, use the Set to store the key value, as value, if it is found that the two will be thrown we usually see a lot of an error:
error('Encountered two children with the same key, `%s`. ' + 'Keys should be unique so that components maintain their identity ' + 'across updates. Non-unique keys may cause children to be ' + 'duplicated and/or omitted — the behavior is unsupported and ' + 'could change in a future version.', key);
Copy the codeReact diff logic. React diff logic
- Iterate over the old and new children and compare them. If the key and type all match, that’s great. Those nodes can be fully reused, and diff ends
- React will use Map with key as the key to collect nodes that are not traversed in oldChildren (old nodes), and then traverse the remaining new nodes. If you can find a key in the map, you reuse it. If you can’t find a key in the map, you reuse it. If you can’t find a key, you create a new one.
- OldChild is traversed, newChild has nodes, so prove that these nodes are inserted, just insert.
- NewChild is traversed, oldChild has nodes, so prove that these nodes are deleted, delete.
Let’s look at the code below:
// Use newIndex to iterate
for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
// What can I do to enter the first branch
if (oldFiber.index > newIdx) {
nextOldFiber = oldFiber;
oldFiber = null;
} else {
// Sibling is a fiberNode sibling, so use nextOldFiber to store the next fiberNode to be compared
nextOldFiber = oldFiber.sibling;
}
// Get a new fiberNode object by comparing oldFiber with newFiber
// This object can be reused, new, or null
var newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx], lanes);
// Break the loop if null
if (newFiber === null) {
if (oldFiber === null) {
oldFiber = nextOldFiber;
}
break;
}
// optimize the item
if (shouldTrackSideEffects) {
if (oldFiber && newFiber.alternate === null) {
// We matched the slot, but we didn't reuse the existing fiber, so we
// need to delete the existing child.deleteChild(returnFiber, oldFiber); }}// Record the index of the current reusable node
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
// is the initial node
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
// Set the sibling to newFiber
previousNewFiber.sibling = newFiber;
}
// List moves, pre assigns the current node
previousNewFiber = newFiber;
// Assign old to the next object to compare
oldFiber = nextOldFiber;
}
Copy the codeHere is newIndex++, so it’s iterating over newChild in the for loop. First it will compare oldFiber’s index to newIndex, because they’re both iterating from scratch, so normally they must be equal, So it’s going to go to the else branch, so nextOldFiber is equal to the sibling of oldFiber, which is the neighbor of the current node. And then newFiber is just updateSlot, so let’s go inside this function
function updateSlot(returnFiber, oldFiber, newChild, lanes) {
// Get the key value, null if no
varkey = oldFiber ! = =null ? oldFiber.key : null;
if (typeof newChild === 'string' || typeof newChild === 'number') {
if(key ! = =null) {
return null;
}
return updateTextNode(returnFiber, oldFiber, ' ' + newChild, lanes);
}
if (typeof newChild === 'object'&& newChild ! = =null) {
switch (newChild.$$typeof) {
case REACT_ELEMENT_TYPE:
{
// If both keys are null, they are equal and can be reused
if (newChild.key === key) {
if (newChild.type === REACT_FRAGMENT_TYPE) {
return updateFragment(returnFiber, oldFiber, newChild.props.children, lanes, key);
}
// Get the updated Element
return updateElement(returnFiber, oldFiber, newChild, lanes);
} else {
return null; }}case REACT_PORTAL_TYPE:
{
if (newChild.key === key) {
return updatePortal(returnFiber, oldFiber, newChild, lanes);
} else {
return null; }}}if (isArray$1(newChild) || getIteratorFn(newChild)) {
if(key ! = =null) {
return null;
}
return updateFragment(returnFiber, oldFiber, newChild, lanes, null);
}
throwOnInvalidObjectType(returnFiber, newChild);
}
{
if (typeof newChild === 'function') { warnOnFunctionType(returnFiber); }}return null; } fiber is returned only if the key is the same, otherwise it is returnednull. Let's look at what $$updateElement does with the same keyfunction updateElement(returnFiber, current, element, lanes) {
// Check whether there are any old nodes
if(current ! = =null) {
// Only the same type can be reused
if (current.elementType === element.type || (
isCompatibleFamilyForHotReloading(current, element))) {x
var existing = useFiber(current, element.props);
existing.ref = coerceRef(returnFiber, current, element);
existing.return = returnFiber;
{
existing._debugSource = element._source;
existing._debugOwner = element._owner;
}
returnexisting; }}// Create a new node if there is no old node or the type is different
var created = createFiberFromElement(element, returnFiber.mode, lanes);
created.ref = coerceRef(returnFiber, current, element);
created.return = returnFiber;
return created;
}
Copy the codeAs you can see, if there is an old node and they have the same type, it will be reused, otherwise a new node will be created and returned.
Returning to our previous loop, a fiber node is returned only if the new and old nodes have the same key. And what if we don’t give key? If neither key is given, it will be null === null, and the result will still be true, so it will be reused. If the key is different, then null is returned, and our for loop breaks, going to the next logic, which we’ll talk about later.
After get new fiberNode, will enter a placeChildplaceChildplaceChild function at this time. Its main function is to determine the update type of each node and return the location of the last reusable node.
function placeChild(newFiber, lastPlacedIndex, newIndex) {
//lastPlacedIndex starts with 0
newFiber.index = newIndex;
if(! shouldTrackSideEffects) {.return lastPlacedIndex;
}
var current = newFiber.alternate;
// Check whether there are any nodes
if(current ! = =null) {
var oldIndex = current.index;
// If oldIndex is less than the index of the nearest reusable node, then it needs to be shifted right
if (oldIndex < lastPlacedIndex) {
// Placement is a constant and react is used to determine the type of change
newFiber.flags = Placement;
return lastPlacedIndex;
} else {
// If it is larger than the nearest reusable node, leave it unchanged and set lastPlacedIndex to that value
returnoldIndex; }}else {
// This fiber is new
newFiber.flags = Placement;
returnlastPlacedIndex; }}Copy the codeThis is a little bit convoluted, but let’s use a simple example to understand, we have four numbers abCD, and we’re going to change it to Dabc. And if you look at it visually, it’s pretty obvious that you’re moving d to the front, but react doesn’t do that, react does that.
- Go through dabc, get the first d, d is the fourth number in abcd, so index=3, greater than lastPlacedIndex=0, stay the same, and change lastPlacedIndex to 3
- Go through dabc, get the second A, a is the first number in ABcd, so index=0, less than lastPlacedIndex=3, and just to keep the order, we need to move a right after D
- Go through dabc, get the third b, b is the second number in ABcd, so index is equal to 1, less than lastPlacedIndex is equal to 3, and just to keep the order, we need to move b right after D
- Go through dabc, get the third c, c is the first number in ABcd, so index is equal to 2, less than lastplace index is equal to 3, and just to keep the order, we need to move c right after D
Therefore, React actually moves ABC after D. Of course, another method is also possible. However, as for React, it is impossible to determine how to move according to the actual situation, so it only adopts a fixed method for modification.
If newIndex is equal to the length of newChild, then we’re done iterating through newChild. If the oldChild is still available, we can delete some nodes, so delete the remaining nodes.
If oldChild is already traversed, but newChild still is, then we can prove that we added nodes, and we can simply add the remaining nodes.
But if we dropped out of the loop, the proof, we have modified the midway of nodes through a mapRemainingChildrenmapRemainingChildrenmapRemainingChildren function to gather at this time no traverse the old node, Map is used to store a key. If there is no key, index is used as the key.
function mapRemainingChildren(returnFiber, currentFirstChild) {
// Create a map
var existingChildren = new Map(a);// Get the first fiber
var existingChild = currentFirstChild;
/ / traverse
while(existingChild ! = =null) {
if(existingChild.key ! = =null) {
// if there is a key, use key
existingChildren.set(existingChild.key, existingChild);
} else {
// If not, use index
existingChildren.set(existingChild.index, existingChild);
}
// Get the sibling fiber
existingChild = existingChild.sibling;
}
return existingChildren;
}
Copy the codeThen again the rest of the newChild, to find the corresponding node, and through placeChildplaceChildplaceChild function marks we need to do the operation.
for (; newIdx < newChildren.length; newIdx++) {
// This is the node found according to the previous map
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); }}// mark the node modification type
lastPlacedIndex = placeChild(_newFiber2, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
resultingFirstChild = _newFiber2;
} else {
previousNewFiber.sibling = _newFiber2;
}
// List movepreviousNewFiber = _newFiber2; }}Copy the codeHere’s a updateFromMapupdateFromMapupdateFromMap, here is mainly from the map before the use of the key to match the corresponding node, if the match can reuse, create a new node can’t match.
conclusion
In fact, the most important points are:
- React uses index instead of discarding the DOM if the key is not given
- React demultiplexes nodes only if the key and type are the same
- When changing the order of a list, React is changed by moving it from top to bottom, so we try to move as few nodes as possible to the front, because this would actually cause all nodes in front of the node to move to the back, not just one node to the front.
Finally, our whole diff process is over. Let’s go back to the original question, if I don’t give the key, won’t React throw them away completely and construct them again? The answer is no. React uses index as the key, and the node type does not change, so React will reuse the node, but it only changes its props, which results in the video not getting the correct video source. Finally, we summarize the general process:
- After entering the entry function, it is processed according to different types
- If it is an element, then it can be updated directly. In this case, it will determine whether it can be reused based on the key and type.
- If it is an array, special processing is done
- First of all, the one-to-one comparison between oldFiber and newChild is cycled. If they are exactly the same, both can be reused, which ends smoothly
- If oldFiber is done iterating through newChild, then new nodes are added. Insert the remaining nodes directly
- If newChild traverses oldFiber, then the node is deleted
- If you exit the loop midway, then prove that some nodes have been changed, then collect the rest of oldFiber, store it in Map, use key as the key value, if there is no key, use index
- Iterate over the remaining newChild, find the corresponding reusable node in map, compare type after finding it, if the same can be reused. If it cannot be found or the type is different, a new node is created
- Finally, return to fiber after diff
We’ve only gone through the core flow here, but notice that there are some other types of comparisons and optimizations in the source code, which are left up to you to explore.