react source code analysis 9 Diff algorithm
Video Explanation (efficient learning): Enter learning
Previous articles:
1. Introduction and interview questions
3.react source code architecture
4. Source directory structure and debugging
6.legacy and concurrent mode entry functions
20. Summary & answers to interview questions in Chapter 1
When updating the fiber node in the render phase, we will call reconcileChildFibers to compare the current Fiber and jsx objects to build a workInProgress Fiber. Here, current Fiber refers to the fiber tree corresponding to the current dom, and jsx is the return value of the class component render method or function component.
In reconcileChildFibers, single node diff or multi node diff will be entered according to the type of newChild
//ReactChildFiber.old.js
function reconcileChildFibers(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
newChild: any,
): Fiber | null {
const isObject = typeof newChild === 'object' && newChild !== null;
if (isObject) {
switch (newChild.$$typeof) {
case REACT_ELEMENT_TYPE:
//Single node diff
return placeSingleChild(
reconcileSingleElement(
returnFiber,
currentFirstChild,
newChild,
lanes,
),
);
}
}
//...
if (isArray(newChild)) {
//Multi node diff
return reconcileChildrenArray(
returnFiber,
currentFirstChild,
newChild,
lanes,
);
}
// Delete node
return deleteRemainingChildren(returnFiber, currentFirstChild);
}
The main flow chart of diff process is as follows:
We know that the complexity of comparing the two trees is O(n3), which is unbearable for our application. react puts forward three preconditions to reduce the complexity:
-
Only peer comparison, cross level dom will not be reused
-
Different types of nodes generate different dom trees. In this case, the old nodes and descendant nodes will be directly destroyed and new nodes will be created
-
You can provide reusable clues to the process of element diff through key, for example:
const a = ( <> <p key="0">0</p> <p key="1">1</p> </> ); const b = ( <> <p key="1">1</p> <p key="0">0</p> </> );If the elements in a and b do not have keys, because the text nodes before and after the node update are different, they cannot be reused. Therefore, the previous node will be destroyed and a new node will be created. But now there is a key, the node in b will find the node with the same key in the old a and try to reuse it. Finally, it is found that the update can be completed only by changing the location, The specific comparison process will be described later.
Single node diff
Single point diff has the following conditions:
- The same key and type indicates that nodes can be reused
- key: directly mark and delete the node, and then create a new node
- If the key is the same but the type is different, mark to delete the node and the sibling node, and then create a new node
function reconcileSingleElement(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
element: ReactElement
): Fiber {
const key = element.key;
let child = currentFirstChild;
//The child node is not null to perform comparison
while (child !== null) {
// 1. Compare key
if (child.key === key) {
// 2. Comparison type
switch (child.tag) {
//...
default: {
if (child.elementType === element.type) {
// If the type is the same, the reused node can be reused
return existing;
}
// Jump out of different type s
break;
}
}
//If the key is the same and the type is different, delete the fiber and brother fiber tags
deleteRemainingChildren(returnFiber, child);
break;
} else {
//key: delete the node with different marks
deleteChild(returnFiber, child);
}
child = child.sibling;
}
//New Fiber
}
Multi node diff
Multi node diff is complex. We discuss it in three cases, where a represents the node before update and b represents the node after update
-
Attribute change
const a = ( <> <p key="0" name='0'>0</p> <p key="1">1</p> </> ); const b = ( <> <p key="0" name='00'>0</p> <p key="1">1</p> </> ); -
type change
const a = ( <> <p key="0">0</p> <p key="1">1</p> </> ); const b = ( <> <div key="0">0</div> <p key="1">1</p> </> ); -
New node
const a = ( <> <p key="0">0</p> <p key="1">1</p> </> ); const b = ( <> <p key="0">0</p> <p key="1">1</p> <p key="2">2</p> </> ); -
Node deletion
const a = ( <> <p key="0">0</p> <p key="1">1</p> <p key="2">2</p> </> ); const b = ( <> <p key="0">0</p> <p key="1">1</p> </> ); -
Node position change
const a = ( <> <p key="0">0</p> <p key="1">1</p> </> ); const b = ( <> <p key="1">1</p> <p key="0">0</p> </> );
In the source code, multi node diff has three for loop traversals (it does not mean that all updates go through three traversals. Entering the loop body is conditional and jumping out of the loop is conditional). The first traversal handles node updates (including props updates and type updates and deletions), and the second traversal handles other situations The reason is that in most applications, the frequency of node updates is more frequent, and the node setting of the third processing bit changes
-
First traversal
Because the old node exists in current Fiber, it is a linked list structure. Remember the Fiber dual cache structure. Nodes are connected through child, return and sibling, while new children exist in jsx. When traversing the comparison, first compare newChildren[i] with oldFiber, and then let I + +, nextoldfiber = oldFiber sibling. In the first round of traversal, three cases will be processed, of which the first and second cases will end the first cycle- key is different. The first cycle ends
- newChildren or oldFiber traversal is completed, and the first cycle ends
- The key is different from the type, and the oldFiber is marked as DELETION
- If the key is the same and the type is the same, it can be reused
After the newChildren traversal, the oldFiber has not been traversed. After the first traversal, the nodes in the oldFiber that have not been traversed are marked as DELETION, that is, the deleted DELETION Tag
-
Second traversal
The second traversal considers three cases-
Both newChildren and oldFiber are traversed: the multi node diff process ends
-
newChildren are not traversed, but oldFiber is traversed, and the remaining nodes of newChildren are marked as Placement, that is, the inserted Tag
-
If newChildren and oldFiber are not traversed, they enter the node movement logic
-
-
Third traversal
The main logic is in the placeChild function. For example, the node order is ABCD before updating and ACDB after updating-
The A and key of the first position in newChild and oldFiber are the same and reusable, lastPlacedIndex=0
-
The C in the second position of newChild is different from the B and key in the second position of oldFiber. Jump out of the first cycle and save the BCD in oldFiber in the map
-
The index of C at the second position in newChild in oldFiber = 2 > lastplacedindex = 0. No need to move, lastPlacedIndex=2
-
The index of D at the third position in newChild in oldFiber = 3 > lastplacedindex = 2. There is no need to move, lastPlacedIndex=3
-
B at the fourth position in newChild has index = 1 < lastplacedindex = 3 in oldFiber and moves to the last
Look at the picture more intuitively
For example, the node order before updating is ABCD and after updating is DABC
-
The D of the first position in newChild and the A and key of the first position in oldFiber are different and cannot be reused. Save the ABCD in oldFiber in the map with lastPlacedIndex=0
-
The index of D at the first position in newChild in oldFiber = 3 > lastplacedindex = 0 does not need to be moved, lastPlacedIndex=3
- Index = 0 < lastplacedindex = 3 of A in the second position of newChild in oldFiber, moving to the last
- Index = 1 < lastplacedindex = 3 in oldFiber for B at the third position in newChild, moving to the last
- The index of C at the fourth position in newChild in oldFiber = 2 < lastplacedindex = 3, moving to the last
Look at the picture more intuitively
-
The code is as follows:
//ReactChildFiber.old.js
function placeChild(newFiber, lastPlacedIndex, newIndex) {
newFiber.index = newIndex;
if (!shouldTrackSideEffects) {
return lastPlacedIndex;
}
var current = newFiber.alternate;
if (current !== null) {
var oldIndex = current.index;
if (oldIndex < lastPlacedIndex) {
//If oldIndex is less than lastPlacedIndex, the node is inserted to the end
newFiber.flags = Placement;
return lastPlacedIndex;
} else {
return oldIndex;//No need to move lastPlacedIndex = oldIndex;
}
} else {
//New insert
newFiber.flags = Placement;
return lastPlacedIndex;
}
}
//ReactChildFiber.old.js
function reconcileChildrenArray(
returnFiber: Fiber,//Parent fiber node
currentFirstChild: Fiber | null,//First node in children
newChildren: Array<*>,//The new node array is the jsx array
lanes: Lanes,//lane related Chapter 12 introduction
): Fiber | null {
let resultingFirstChild: Fiber | null = null;//The first node returned after diff
let previousNewFiber: Fiber | null = null;//Last compared node in the new node
let oldFiber = currentFirstChild;//oldFiber being compared
let lastPlacedIndex = 0;//Last reusable node location or oldFiber location
let newIdx = 0;//Compared position in new node
let nextOldFiber = null;//oldFiber being compared
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {//First traversal
if (oldFiber.index > newIdx) {//nextOldFiber assignment
nextOldFiber = oldFiber;
oldFiber = null;
} else {
nextOldFiber = oldFiber.sibling;
}
const newFiber = updateSlot(//Update nodes. If the key s are different, newFiber=null
returnFiber,
oldFiber,
newChildren[newIdx],
lanes,
);
if (newFiber === null) {
if (oldFiber === null) {
oldFiber = nextOldFiber;
}
break;//Jump out of the first traversal
}
if (shouldTrackSideEffects) {//Check shouldTrackSideEffects
if (oldFiber && newFiber.alternate === null) {
deleteChild(returnFiber, oldFiber);
}
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);//Tag node insertion
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
oldFiber = nextOldFiber;
}
if (newIdx === newChildren.length) {
deleteRemainingChildren(returnFiber, oldFiber);//Mark the nodes in oldFiber that have not been traversed as DELETION
return resultingFirstChild;
}
if (oldFiber === null) {
for (; newIdx < newChildren.length; newIdx++) {//Second traversal
const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
if (newFiber === null) {
continue;
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);//Insert new node
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
return resultingFirstChild;
}
// Add the remaining oldFiber to the map
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
for (; newIdx < newChildren.length; newIdx++) {//The third cycle deals with node movement
const newFiber = updateFromMap(
existingChildren,
returnFiber,
newIdx,
newChildren[newIdx],
lanes,
);
if (newFiber !== null) {
if (shouldTrackSideEffects) {
if (newFiber.alternate !== null) {
existingChildren.delete(//Delete found nodes
newFiber.key === null ? newIdx : newFiber.key,
);
}
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);//Logic marked for insertion
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
}
if (shouldTrackSideEffects) {
//Delete the remaining nodes in existingChildren
existingChildren.forEach(child => deleteChild(returnFiber, child));
}
return resultingFirstChild;
}