React Fiber Diff algorithm
Algorithm principle
The React Fiber Diff algorithm is divided into two parts. The first part is to find nodes that can be reused in place by synchronous traversal from left to right. The second part is to use subscript increasing method to mark the nodes that need to be moved. The DIff marking phase is in the Render phase and the movement phase is in the Commit phase.
Here are a few examples:
- Constant examples:
From the above example, it is clear that each node can be reused without any movement of the node. In the first part of the React algorithm, all nodes that can be reused in place are processed.
- Examples of sequential changes:
As shown in the figure, in the first part of the React algorithm, the node “A” is reused in place. In the second part, the subscript of the reusable node in the old list is set to the corresponding subscript of the node in the new list. For example, the newIndex of D is 3, and the newIndex of B is 1. Moves back elements that do not comply with the subscript increment rule.
As shown in the figure, in the first part of the React algorithm, the node “A” is reused in place. In the second part, the subscript of the reusable node in the old list is set to the corresponding subscript of the node in the new list. For example, the newIndex of D is 3, and the newIndex of B is 1. Moves back elements that do not comply with the subscript increment rule.
Algorithm process
Before we talk about the algorithm process, let’s talk about the React Fiber Node structure
In React Fiber architecture, fibers in the same layer are organized as a one-way linked list, rather than as an array as in React15 and other frameworks. Organized on a one-way list, this means that it is not easy to query, and does not support traversal from back to front. Therefore, React uses the map structure to store all nodes when nodes are multiplexed using the subscript incrementing method, facilitating subsequent query operations. Here is the React Fiber architecture:
React Fiber architecture is a tree like complex linked list structure. Each node has three Pointers sibling, child and return, respectively pointing to the next sibling node, child node and parent node. The diff algorithm compares the Sibling linked list at the same level of the new and old trees. Another point to note here is that on the Sibling linked list, the Fiber node has an index attribute, which marks the subscript of the linked list on the node. The purpose of setting this attribute is to facilitate the DIff algorithm to determine whether the node needs to be moved.
In addition, React uses a dual-buffering mechanism, whereby each view has two Fiber trees during update. One is current, which describes the currently rendered view, and the other is workInProgress, which represents the working Fiber tree. The corresponding nodes of the two (if it is judged that DOM can be reused) refer to each other through alternate. For the purposes of this article, it is only necessary to know that the alternate property of the Fiber node in workInProgress points to fiber in the current tree that has been judged to be reusable.
The React Fiber Diff algorithm compares the old and new Fiber structures with the React Elements forms
The React Fiber Diff algorithm is divided into two stages:
- In situ multiplexing node
Let’s look at the algorithm implementation:
let resultingFirstChild: Fiber | null = null;
let previousNewFiber: Fiber | null = null;
// points to the first node in the old list that has not been reused
let oldFiber = currentFirstChild;
// This is the maximum subscript of the current new fiber node, which is used to indicate whether the node needs to be moved
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;
}
// React considers each node of the old Fiber as a slot. If the keys are the same, the slot is matched
// Decide whether to reuse this node based on information such as elementType
const newFiber = updateSlot(
returnFiber,
oldFiber,
newChildren[newIdx],
lanes,
);
// No node that can be reused in place is matched, end of the first part
if (newFiber === null) {
if (oldFiber === null) {
oldFiber = nextOldFiber;
}
break;
}
if (shouldTrackSideEffects) {
if (oldFiber && newFiber.alternate === null) {
// The slot is matched, but fiber is not multiplexed, the node should be marked for removaldeleteChild(returnFiber, oldFiber); }}// Each update finds the maximum index of the new node corresponding to the old node
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
oldFiber = nextOldFiber;
}
// When the new list is a sublist of the old list, the remaining nodes are deleted
if (newIdx === newChildren.length) {
deleteRemainingChildren(returnFiber, oldFiber);
return resultingFirstChild;
}
if (oldFiber === null) {
// When the old list has been accessed, but the new list has not been accessed, the node is created.
for (; newIdx < newChildren.length; newIdx++) {
const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
if (newFiber === null) {
continue;
}
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;
}
return resultingFirstChild;
}
Copy the codeIn the code above, the new React Elements array and the old React Fiber list are synchronously traversed from left to right to find nodes that can be reused in place. Let’s use a simpler example to illustrate the implementation of the process:
React Elements: Old Fiber; React Elements: Old Fiber; React Elements: Old Fiber
In the example above, the old and new lists reuse the “A” and “B” nodes in place.
- Reuse nodes that need to be moved
In the first part of the algorithm, the nodes that can be reused in situ are reused from left to right, followed by the maximum reuse of nodes in the chaotic list, the code is as follows:
// Create a map for all nodes except those that can be reused in place. The space-for-time strategy is convenient for later query operations
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
// Keep scanning and use the map to restore deleted items as moves.
for (; newIdx < newChildren.length; newIdx++) {
// Use map to find nodes that can be reused. If not, create new nodes
const newFiber = updateFromMap(
existingChildren,
returnFiber,
newIdx,
newChildren[newIdx],
lanes,
);
if(newFiber ! = =null) {
if (shouldTrackSideEffects) {
if(newFiber.alternate ! = =null) {
// alternate is not null, indicating that the node is matched to the multiplexing node,
// Delete the overused nodes from the map to avoid overusing
existingChildren.delete(
newFiber.key === null? newIdx : newFiber.key, ); }}// Find the new list to reuse the maximum subscript of the old list
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else{ previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; }}if (shouldTrackSideEffects) {
// The remaining nodes in the map are not matched, so it should be deleted
existingChildren.forEach(child= > deleteChild(returnFiber, child));
}
Copy the codeThe algorithm can be roughly divided into three steps:
- React uses map
to store the old nodes, and then obtains nodes that can be reused based on the keys of the new nodes when traversating the new node list.
- Check whether the node can be reused. If the node can be reused, go to step C; otherwise, create the node
- The placeChild method is used to determine whether the node needs to be moved.
function placeChild(newFiber: Fiber, lastPlacedIndex: number, newIndex: number,) :number {
newFiber.index = newIndex;
// If the new fiber matches the old fiber, the alternate property points to the multiplexed node
const current = newFiber.alternate;
if(current ! = =null) {
// Get the index of the old node to be reused
const oldIndex = current.index;
if (oldIndex < lastPlacedIndex) {
// The new list is traversed from left to right. The DOM reused from the previous node is to the right of this node.
// Then you need to move this object to the right to satisfy the sorting order of the new list
// This is a move.
newFiber.flags |= Placement;
// Returns the farthest subscript so far
return lastPlacedIndex;
} else {
// Returns the subscript of the current maximum multiplexing
returnoldIndex; }}else {
// This is an insertion.
newFiber.flags |= Placement;
returnlastPlacedIndex; }}Copy the codeIn the above logic, as long as the subscript of the current multiplexed node is judged to be less than lastPacedIndex, the multiplexed node needs to be marked as needing to be moved. This is because the algorithm iterates from left to right through the new list and finds nodes from the old list that can be reused. If the previous reusable node is to the right and the next reusable node is to the left of the previous reusable node, the DOM node corresponding to the next node needs to be moved back to meet the update order. In this way, nodes whose subscripts are not increasing are marked and then moved, which is also the idea of increasing method.
Here’s an example of the whole process in Part 2:
Diff algorithm processing is carried out in the Render phase, in which DOM nodes are not processed and will be processed in the Commit phase.
React Fiber Diff
insufficient
React Fiber’s Diff algorithm has two drawbacks:
- Because Fiber is a unidirectional linked list, only the first half of the in-place multiplexing phase can be accessed from the place. If Fiber is a bidirectional linked list, the second half can be reused.
- In the second part of the work, when judging which nodes can not be moved, it is very simple to judge from left to right, so that the performance is not the best in some extreme cases. For example, if the original “2” is in the last element, then the nodes to be moved are “5”, “4” and “3”. Vue3.0 Diff algorithm provides an optimization scheme: the longest ascending subsequence is used to obtain the longest node array that can be reused in situ.
Vue2.0 Diff algorithm
Algorithm principle
Vue Diff algorithm used the double side comparison method, defined four cursor, respectively before and after and before and after the new array of the old array, circulating operation, every round is to compare the old and new array of the head, tail, and two lists end cross comparison, if not find can reuse of nodes, then will find the corresponding node query operation.
Here’s an example:
The algorithm will have four subscripts, which are the indices of the first and last elements of the two arrays: oldStartIdx, oldEndIdx, newStartIdx, and newEndIdx. They all start pointing to both ends of two arrays. Once the algorithm starts, it keeps getting closer and closer to the inside, until it ends with a crossover.
let oldStartIdx = 0;
let oldEndIdx = PreList.length - 1;
let newStartIdx = 0;
let newEndIdx = NewList.length - 1;
Copy the codeIn the example above, the first and last elements of PreList and NewList (” 1 “in the figure) are compared. If the two elements are the same, oldStartIdx and newStartIdx will be moved back. That is:
oldStartIdx++;
newStartIdx++;
Copy the codeNext, if the first element of the two lists is different, the last element (” 5 “in the figure) will be compared and the last pointer of the two lists will be moved forward:
oldEndIdx--;
newEndIdx--;
Copy the codePreList[oldStartIdx] = NewList[newEndIdx] = NewList[newEndIdx] = NewList[oldStartIdx] = NewList[newEndIdx]
oldStartIdx++;
newEndIdx--;
Copy the codeAfter that, if it is found that the two-end comparison and the head-to-tail comparison are not successful, then it will enter the search for reusable nodes through the query.
Algorithm process
The principle of double-ended comparison method is explained above. Here, each cycle of double-ended comparison method is divided into two parts. The first part is to conduct simple comparison to find reusable nodes, and the second part is to query reusable nodes:
- A simple comparison shows the implementation code of reusable nodes as follows. Compared with the source code, irrelevant function calls such as patch are missing in the code:
// Insert the real node
function insertBefore(parentElm, movedElm, targetElm) {
// This function moves the movedNode to a location on the targetNode
}
function nextSibling(elem) {
// Returns the node to the right of elem
}
function isSameNode(nodeA, nodeB) {
// Determine whether the node can be reused
}
const isUndef = (tar) = > typeof tar === 'undefined';
function vueDiff(parentElm, oldList, newList) {
let oldStartIdx = 0;
let oldEndIdx = oldCh.length - 1;
let newStartIdx = 0;
let newEndIdx = newCh.length - 1;
let oldStartNode = oldCh[0];
let oldEndNode = oldCh[oldEndIdx];
let newStartNode = newCh[0];
let newEndNode = newCh[newEndIdx];
while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
// If there is a reusable node,
// After a node is moved, it is set to undefined in oldList to avoid repeated use
oldStartVnode = oldCh[++oldStartIdx];
} else if (isUndef(oldEndVnode)) {
// Same as above
oldEndVnode = oldCh[--oldEndIdx];
} else if (sameVnode(oldStartVnode, newStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) {
// Move the node to the right of the first unprocessed node on the right
insertBefore(parentElm, oldStartVnode.elm, nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldEndVnode, newStartVnode)) {
// Move the node to the left of the first unprocessed node
insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else {
// Query the logic of reusable nodes, as described below}}}Copy the codeThe above comparison is the ideal case of the two-ended comparison method. We can find that the idea of the two-ended comparison method is to start from both ends and find the nodes that can be reused and fill them in order. In the process of work, it will be divided into processed areas and unprocessed areas:
The gray part of the figure is the area that has been processed, and the colored part is the area that has not been processed. According to the processing logic, the node “2” is matched, so what should be done? Since the end goal is to process the DOM in the same order as newCh, the “2” in oldCh must be moved back to the left of the already processed node, i.e. :
Here’s a more complicated example to illustrate the simple comparison process:
OldCh and newCh are both organized as arrays, while their DOM counterpart is organized as a linked list
Here is an update example where DOM is the actual DOM node, oldCh is the list of vNodes at the corresponding render time, and newCh is the list of vNodes in the next state:
The following is the simple in-place reuse code in the diff algorithm, and the specific node operation animation is as follows:
In this case, the comparison between the old and new start and end nodes is carried out respectively, in which “1” and “6” are matched successfully. Under this condition, the position of the final rendering will not change, so there is no need to move nodes. When the head and tail cannot be matched, the head and tail cross match is performed. In this case, if the corresponding node is matched, node movement is required (the operation is performed directly on the corresponding DOM node, and node movement is not required on Vnode).
- Query to find reusable nodes
The first stage is the comparison in the ideal case, but many cases are not ideal, so in the not ideal case, you need to find reusable nodes through query operations. When Vue2.0 Diff queries reusable nodes, there are two situations:
- When the user writes a loop render, they give each node of the list a unique key: In this case, the two-end comparison method will be optimized and the strategy of space for time is adopted. The Map structure is used to store the key, and the matching node is searched according to the key value of the new node during the query. In this case, the time complexity of the node query operation is O(m), where M <= n and n is the total length of the list.
- When the user writes a loop rendering, no key is set for each node: For a list without a key value, Vue performs a brute force search comparison, so the time complexity of this operation is O(m ^ 2), (where m <= n, n is the total length of the list. In the worst case, m === n, then the worst time complexity of the two-ended comparison method is O(n ^ 2)).
Then the specific implementation code is as follows:
// Insert the real node
function insertBefore(parentElm, movedElm, targetElm) {
// This function moves the movedNode to a location on the targetNode
}
function nextSibling(elem) {
// Returns the node to the right of elem
}
function isSameNode(nodeA, nodeB) {
// Determine whether the node can be reused
}
function createKeyToOldIdx (children, beginIdx, endIdx) {
let i, key
const map = {}
for (i = beginIdx; i <= endIdx; ++i) {
key = children[i].key
if (isDef(key)) map[key] = i
}
return map
}
function findIdxInOld (node, oldCh, start, end) {
for (let i = start; i < end; i++) {
const c = oldCh[i]
if (isDef(c) && sameVnode(node, c)) return i
}
}
const isUndef = (tar) = > typeof tar === 'undefined';
function vueDiff(parentElm, oldList, newList) {
let oldStartIdx = 0;
let oldEndIdx = oldCh.length - 1;
let newStartIdx = 0;
let newEndIdx = newCh.length - 1;
let oldStartNode = oldCh[0];
let oldEndNode = oldCh[oldEndIdx];
let newStartNode = newCh[0];
let newEndNode = newCh[newEndIdx];
let oldKeyToIdx, idxInOld, vnodeToMove, refElm;
while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
// If there is a reusable node,
// After a node is moved, it is set to undefined in oldList to avoid repeated use
// undefined is skipped automatically
oldStartVnode = oldCh[++oldStartIdx];
} else if (isUndef(oldEndVnode)) {
// Same as above
oldEndVnode = oldCh[--oldEndIdx];
} else if() {
// omit a bunch of if else
} else {
if (isUndef(oldKeyToIdx)) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
}
// Query a node
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
if (isUndef(idxInOld)) {
// Create a new DOM and insert it before the corresponding DOM node of oldStartVnode
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
} else {
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
// Set the subscript to undefined to indicate that the Vnode has been processed to avoid subsequent processing
oldCh[idxInOld] = undefined
insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
} else {
// The key is the same, but the element type is different
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx) } } newStartVnode = newCh[++newStartIdx]; }}}Copy the codeIt should be noted that in the processing logic of querying the reusable node, if the reusable node is found, the value of oldCh subscript on the node should be set to undefined after the operation, indicating that the node has been reused and avoiding the subsequent reuse of the node.
The previous case is run through the first stage and the following results are obtained:
Note that Vnode and DOM are linked by reference, not matched by subscript, so update by reference to get the corresponding DOM node. (It’s easy to misunderstand the subscript).
The above Vue2.0 Diff algorithm is divided into two parts for easy understanding, not two nodes. In fact, these two parts of the job are judged by each loop.
Finally, attach the code link: Vue2.0 Diff algorithm
Vue3.0 Diff algorithm
Algorithm principle
The Diff algorithm of Vue3.0 is similar to the incrementing method of React Fiber, but a little different. The Diff algorithm of Vue3.0 can be divided into two phases:
- The first stage is to traverse nodes that can be reused in place from both sides of the array (this is similar to React Diff algorithm. React only reuses the first half in place, but does not attempt to reuse the second half in place, because Fiber architecture is one-way linked list, traversing from back to front costs too much). If an array is a subarray of another array, mount or unmount is done.
- If the two arrays are not subsequence relations, that is, completely different sequences exist, the second stage will be entered. Under the premise of reusing nodes in this stage, DOM movement operations will be reduced as much as possible (the longest ascending subsequence is adopted here to help the algorithm reduce DOM operations).
Algorithm process
Without further ado, let’s take a look at the process of the algorithm, which is divided into two stages: in-place reuse phase and reuse requires moving nodes phase let’s take a look at the in-place reuse phase how to deal with?
Duplex in situ multiplexing
function Vue3Diff(c1, c2) {
let i = 0
const l2 = c2.length
let e1 = c1.length - 1
let e2 = l2 - 1
while (i <= e1 && i <= e2) {
const n1 = c1[i];
const n2 = c2[i];
if (isSameNode(n1, n2)) {
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else {
// If you can't reuse in place, exit and wait for phase 2
break;
}
i++;
}
while (i <= e1 && i <= e2) {
const n1 = c1[e1];
const n2 = c2[e2];
if (isSameNode(n1, n2)) {
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else {
// If you can't reuse in place, exit and wait for phase 2
break;
}
e1--;
e2--;
}
// The old list is a subarray of the new list, so you need to mount the new list
if (i > e1) {
if (i <= e2) {
const newPos = e2 + 1;
// Get the position where the node is inserted
const anchor = newPos < l2 ? (c2[nextPos]).el : parentAnchor;
while (i <= e2) {
// Create a node and mount it
patch(
null,
(c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i])),
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
i++
}
}
} else if (i > e2) {
// If the new list is a subarray of the old list, unmount the remaining nodes of the old list
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
}
}
Copy the codeAbove is the first stage of processing code, here are a few examples to explain the above logic corresponding to the scenario:
Double-ended ergodic multiplexing:
In the above example, after dual-end in situ multiplexing, the following figure is shown :(gray indicates that the multiplexing has taken place)
After the dual-end multiplexing is complete, the following two situations may occur
- The old list is a subarray of the new list
In this case, the old array is a subsequence of the new array, so “4” and “5” should be mounted to the DOM:
- The new list is a subarray of the old list
In this case, the new array is a subsequence of the old array, so the DOM node needs to be unmounted:
Reuse nodes that need to be moved
If there is no subarray relationship between the two arrays, the new and old reusable nodes will be found by querying, and the longest ascending subsequence will be found to help Vue find the path that manipulates the DOM nodes least. In the stage of reusing mobile nodes, the work can be divided into two parts: marking reusable nodes and mobile nodes.
- Marks nodes that can be reused
This part of the work can be divided into two actions: finding reusable nodes and old and new reusable node tags.
A. Search for nodes that can be reused for work: The processing method is consistent with Vue2.0. If there is a key in the list element, Map is used to query in space for time; otherwise, traversal is performed.
Vue3.0 uses an array as the subscripts of nodes matched by the old and new lists:
const newList = [a, b, c, d, e];
const oldList = [a, c, b, e, f];
// Then the map should look like this:
const newIndexToOldIndexMap = [2.1.4.0];
Copy the code0 in the newIndexToOldIndexMap array means that the current node cannot find the reusable node. The specific matching result is shown in the figure:
To explain this part of the work above, note that matches are made from “unprocessed lists”, which can be understood as finding matching nodes in a subarray.
Now look at the code:
// I is the index of the first node on the left that cannot be reused after the previous step
const s1 = i // prev starting index
const s2 = i // next starting index
// This step is to build the key -> Vnode map
const keyToNewIndexMap: Map<string | number, number> = new Map(a)for (i = s2; i <= e2; i++) {
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
if(nextChild.key ! =null) {
keyToNewIndexMap.set(nextChild.key, i)
}
}
let j
// Number of nodes with patched
let patched = 0
// The length of the node to be patched
const toBePatched = e2 - s2 + 1
let moved = false
let maxNewIndexSoFar = 0
const newIndexToOldIndexMap = new Array(toBePatched)
// Each element is not reused by default
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
// The old list is iterated without reuse
for (i = s1; i <= e1; i++) {
const prevChild = c1[i]
if (patched >= toBePatched) {
// The new list has patched over all nodes, but the old array still has elements, you only need to remove the old array elements
// all new children have been patched so this can only be a removal
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
let newIndex
if(prevChild.key ! =null) {
// If the key is set, the map will fetch the key value
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
// You can only query reusable nodes by traversing them without keys
// key-less node, try to locate a key-less node of the same type
for (j = s2; j <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j] as VNode)
) {
newIndex = j
break}}}if (newIndex === undefined) {
// If no matching Vnode is found in the new list, the original Vnode is removed
unmount(prevChild, parentComponent, parentSuspense, true)}else {
// Mark Vnode (subscript) in the new list to match the subscript in the old list. Note that there is a + 1 operation in this part, because 0 is
newIndexToOldIndexMap[newIndex - s2] = i + 1
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
// Patch moves the DOM pointed to on oldVnode to newVnode
patch(
prevChild,
c2[newIndex] as VNode,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
patched++
}
}
Copy the codeThe logic is clear: find old and new nodes, and use arrays to connect reusable nodes, but there is a bit of confusion in the above code. There will be two variables: maxNewIndexSoFar and Moved. What do they mean?
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
Copy the codeThis is an optimization that uses the Moved variable to indicate whether a node needs to be moved later. Why do you say that? A few examples:
Example here, determine whether need go straight logic if branch of mobile, this is because the match to the nodes have been increasing, reuse DOM node operating mobile node is required when operating, only need to add a node F in front of the node B can (DOM of the organization in the form of a linked list node, so don’t need to move back nodes).
Here’s another example of a node that needs to be moved:
In this example, the DOM node corresponding to B is before C, but after the update, it needs to be behind C, so the DOM node must be moved. Vue compares the subscript of the node with the maximum subscript previously matched to the new list to determine whether it needs to move. This is similar to lastReplaceIndex in the React Fiber Diff algorithm.
- Mobile node
After marking reusable nodes, these nodes need to be moved. There are many paths to move nodes, and even reordering is a way to move nodes. Here, Vue needs to consider how to operate DOM as little as possible. Vue3.0 adopts the longest increasing subsequence algorithm to find out the longest ascending sequence of the reused old node. The CORRESPONDING DOM node on this sequence does not need any movement, and the DOM node is updated by moving other nodes.
LeCode link: longest increasing subsequence
Instead of looking at the LeeCode link, here’s an example:
[1.3.2.4.8.5.7] The longest ascending subsequence of this example: [1.2.4.5.7]
Copy the codeThe longest ascending subsequence is the subarray that finds the longest ascending from left to right. Let’s do a practical example
const oldCh = [a, b, c, d, e];
const newCh = [a, e, b, c, d];
// Then find
newIndexToOldIndexMap = [4.1.2.3];
Copy the codeIn the example above, the easiest way to move is to move E in front of B. What about Vue? Start by finding the longest sequence in relative ascending order. The ascending order is found because the DOM nodes corresponding to these nodes are in the same relative position relationship as newCh wants, so that these nodes do not need to be moved at all, and finding the longest is to find as many nodes as possible that do not need to be moved, which minimizes DOM manipulation. Then, first work out the longest ascending subsequence:
const oldCh = [a, b, c, d, e];
const newCh = [a, e, b, c, d];
// Then find
newIndexToOldIndexMap = [4.1.2.3];
// Find the longest ascending subsequence from newIndexToOldIndexMap
increasingNewIndexSequence = [1.2.3];
Copy the codeIt can be seen from the longest increasing subsequence that the DOM node corresponding to BCD in oldCh does not need to be changed, only other nodes need to be moved, that is, the relative position of BCD remains unchanged at last, but nodes can be inserted between them:
Let’s look at the concrete implementation of the algorithm:
// Get the longest priority subsequence
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
// Notice that I is decreasing
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i
const nextChild = c2[nextIndex] as VNode
const anchor =
NextIndex + 1 === l2 nextIndex + 1 === l2 parentanchol.appendChild
// Otherwise insert in front of anchor
nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
if (newIndexToOldIndexMap[i] === 0) {
// If there is no old node to reuse, create a new node.
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else if (moved) {
// move if:
// There is no stable subsequence (e.g. a reverse)
// OR current node is not among the stable sequence
if (j < 0|| i ! == increasingNewIndexSequence[j]) {// These nodes need to be moved
move(nextChild, container, anchor, MoveType.REORDER)
} else {
/ / increasingNewIndexSequence deposit is the index to rise subsequence,
/ / if I = = = increasingNewIndexSequence [j],
// Then the current node does not need to move, skip this loop
j--
}
}
}
Copy the codeTips: The anchor above is the anchor point. If it is a node of the same rank, the new node will be inserted in front of the anchor point, and if it is a parent node, it will be inserted directly after the entire DOM list
The whole process of moving is traversing the moving node from right to left. If the minimum ascending sub-sequence is encountered, it means that the node does not need to move, and this cycle is skipped.
There is a question above, why the C2 array (newCh array) is selected as the flag bit anchor in the anchor? This is because the patch function is called at the time of marking, and the patch function transfers references to DOM nodes that can be reused by the old Vnode (but the actual location of the DOM node does not change) to the corresponding Vnode of newCh. At this point, the Vue3.0 DIff algorithm ends.
Here’s an example of this process:
There are two arrays of nodes before and after the update:
const oldCh = [a, b, c, d, e];
const newCh = [a, c, b, e, d];
Copy the code
After calculation, the following data are obtained:
const newIndexToOldIndexMap = [2.1.4.3];
const increasingNewIndexSequence = [1.3];
Copy the codeThen it can be concluded that “B” and “D” do not need to be moved. Next, animation shows the movement process. Before watching the demonstration, three points should be noted:
- In the marking stage, the Patch function will point the EL attribute of the corresponding Vnode in newCh to the DOM node that can be reused, so there is no need to use oldCh array in this stage
- The subscript starts from the first element in the token array, which means that in the above case, the subscript starts from the “C” element in newCh.
- The DOM is organized as a linked list.
At this point, the Vue3.0 DIff algorithm ends.
Code: Vue next diff
summary
Both React Diff and Vue Diff algorithms focus on the problem of how to use the relationship between the old and new VirtualDOM lists to generate a minimum path to modify the DOM node when the VirtualDOM changes (the least number of DOM operations). Don’t forget that DOM manipulation is the most expensive, and JS in-memory object manipulation is relatively inexpensive.