The DIFF algorithm adopted by Vue 3.0 is slightly different from the double-ended comparison of 2.0. The general principle is as follows
// c1: a b [ c d e ] f g
// c2: a b [ d e c h ] f g
Copy the codeIf c1 and C2 are old and new children, there will be a pre-processing process during diff.
Comparisons are made from the front to the back, and when the nodes are different, no further comparisons are made. Then it compares from the back to the front, and when the nodes are different, it does not compare from the front.
After pretreatment, the parts that really need to be diff for C1 and C2 are as follows:
// c1: c d e
// c2: d e c h
Copy the codeFinally, the “longest increasing subsequence” is used to complete the comparison of the above differences and improve the efficiency of DIFF.
Process the same front and back nodes
The preprocessing code is as follows:
const patchKeyedChildren = (
c1,
c2,
container,
parentAnchor,
parentComponent,
parentSuspense,
isSVG,
optimized
) => {
let i = 0;
const l2 = c2.length
let e1 = c1.length - 1
let e2 = c2.length - 1
// 1. sync from start
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = c2[i]
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
parentAnchor,
parentComponent,
parentSuspense,
isSVG,
optimized
)
} else {
break
}
i++
}
// 2. sync from end
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = c2[e2]
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
parentAnchor,
parentComponent,
parentSuspense,
isSVG,
optimized
)
} else {
break
}
e1--
e2--
}
}
Copy the codeOnly nodes are added or removed
Another benefit of preprocessing is that in some cases, we can know exactly when a node is being added or removed.
- New nodes
If I, E1, and E2 satisfy the following relationship, nodes are added
// 3. common sequence + mount
// (a b)
// (a b) c
// i = 2, e1 = 1, e2 = 2
// (a b)
// c (a b)
// i = 0, e1 = -1, e2 = 0
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1;
const anchor = nextPos < l2 ? c2[nextPos] : parentAnchor
while (i <= e2) {
patch(
null,
c2[i],
container,
anchor,
parentComponent,
parentSuspense,
isSVG
)
i++
}
}
} else if {
//
} else {
//
}
Copy the code- Node to remove
If I, E1, and E2 satisfy the following relationships, nodes are removed
// 4. common sequence + unmount
// (a b) c
// (a b)
// i = 2, e1 = 2, e2 = 1
// a (b c)
// (b c)
// i = 0, e1 = 0, e2 = -1
if (i > e1) {
//
} else if (i > e2) {
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
} else {
//
}
Copy the codeA node has been moved, added, or deleted
Sometimes the situation may not be as simple as the above, that is, I, E1, E2 do not satisfy the above two cases, we need to find the nodes to be removed, new nodes, or determine which nodes need to be moved.
To do this, we need to go through the unprocessed nodes in C1 and see if there are corresponding nodes (with the same key) in C2. If no, the node is removed. In this case, unmount the node.
First, in order to quickly confirm whether the node of C1 has a corresponding node in C2 and its location, a mapping (key: index) is established for the nodes in C2.
// 5. unknown sequence
// [i ... e1 + 1]: a b [c d e] f g
// [i ... e2 + 1]: a b [d e c h] f g
// i = 2, e1 = 4, e2 = 5
if (i > e1) {
//
} else if (i > e2) {
//
} else {
const s1 = i
const s2 = i
const keyToNewIndexMap = new Map(a)// 5.1 build key:index map for newChildren
for (i = s2; i <= e2; i++) {
const nextChild = c2[i]
if(nextChild.key ! = =null) {
keyToNewIndexMap.set(nextChild.key, i)
}
}
}
Copy the codeNext, define the following variables
let j
let patched = 0
const toBePatched = e2 - s2 + 1 // Number of nodes to be processed in c2
let moved = false
// used to track whether any node has moved
let maxNewIndexSoFar = 0 // The maximum index in C2 for the traversed c1 node to be processed
// works as Map<newIndex, oldIndex>
// Note that oldIndex is offset by +1
// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// used for determining longest stable subsequence
const newIndexToOldIndexMap = new Array(toBePatched) // For the longest increasing subsequence
for (i = 0; i < toBePatched; i++) {
newIndexToOldIndexMap[i] = 0
}
Copy the codeThen, the nodes to be processed in C1 are traversed to determine whether a node with the same key exists in C2.
- If no, the node is removed. Unmount the node.
- If yes, call patch. And records the index of the node in C1. At the same time, the maximum index of the node in C2 is recorded. If the index position of the node in C2 is less than the maximum index, it indicates that some elements need to be moved.
// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
for (i = s1; i <= e1; i++) {
const prevChild = c1[i]
// (A)
let newIndex
if(prevChild.key ! = =null) {
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
for (j = s2; i <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j])
) {
newIndex = j
break}}}if (newIndex === void 0) {
unmount(prevChild, parentComponent, parentSuspense, true)}else {
newIndexToOldIndexMap[newIndex - s2] = i + 1 // (B)
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
patch(
prevChild,
c2[i],
container,
null,
parentComponent,
parentSuspense,
isSVG,
optimized
)
patched++ // (C)}}Copy the codeDo all nodes in C1 need to search for corresponding nodes in C2 and then call patch?
Note in code (C) above that we update the number of nodes we have patched, so when patched > toBePatched, consider the nodes in c1 to be redundant and remove them.
So we need to add some code at (A) above
if (patched >= toBePatched) {
// all new children have been patched so this can only be a removal
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
Copy the codeThis is where it gets harder to understand.
At the beginning, we said that after preprocessing, the remaining nodes will use the longest increasing subsequence to improve diff efficiency.
The main purpose of solving the longest increasing subsequence is to reduce the movement of DOM elements, which can also be understood as the least DOM operation.
First, we need to solve for the longest increasing subsequence
// generate longest stable subsequence only when nodes have moved
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
Copy the codeLet’s see what the value of newIndexToOldIndexMap is here.
For a specific example, let’s say C1 and C2 are shown below
Defines and initializes the newIndexToOldIndexMap
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) {
newIndexToOldIndexMap[i] = 0
}
Copy the codeToBePatched indicates the number of nodes to be processed in C2 after preprocessing. So in this case, there’s going to be
toBePatched = 4
newIndexToOldIndexMap = [0.0.0.0]
Copy the codeNote that at (B) of the code in 5.2 traversing the nodes in C1 above, there is
// This is I + 1, not I
// Because 0 is a special value, it means this is a new node
newIndexToOldIndexMap[newIndex - s2] = i + 1 // (B)
Copy the codeSo after processing the nodes in C1, we’re going to have
moved = true
newIndexToOldIndexMap = [4.5.3.0]
Copy the codeSo, increasingNewIndexSequence value is getSequence (newIndexToOldIndexMap) return values
// [4, 5, 3, 0] --> the longest increasing subsequence is [4, 5]
// The corresponding index is [0, 1]
increasingNewIndexSequence = [0.1]
Copy the codeAfter the longest increasing subsequence is solved, what is left is to traverse the nodes to be processed in C2 to determine whether the nodes are added or not and whether they need to be moved.
j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
// Note: this is traversing from back to front
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i
const nextChild = c2[nextIndex]
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1]).el : parentAnchor
The value in newIndexToOldIndexMap is initialized to 0 by default
// Where === 0 indicates that the node in c2 has no corresponding node in C1 and is added
if (newIndexToOldIndexMap[i] === 0) {
// mount new
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG
)
} else if (moved) {
// move if:
// There is no stable subsequence (e.g. a reverse)
// OR current node is not among the stable sequence
// j < 0 --> []
if (j < 0|| i ! == increasingNewIndexSequence[j]) { move(nextChild, container, anchor, MoveType.REORDER) }else {
j--
}
}
}
Copy the codeLongest increasing subsequence
In computer science, the longest increasing subsequence problem refers to finding a subsequence in a given numerical sequence, making the number of elements in the subsequence increase successively, and the length of the subsequence as large as possible. The elements in the longest increasing subsequence are not necessarily continuous in the original sequence. “– Wikipedia
For the following original sequence 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, the longest increasing subsequence is 0, 2, 6, 9, 11, 15. It is worth noting that the longest increasing subsequence of the original sequence is not necessarily unique. For the original sequence, there are actually two longest increasing subsequences 0, 4, 6, 9, 11, 15 0, 4, 6, 9, 13, 15Copy the codeThe last
At this point, Vue 3.0 diFF code is analyzed, welcome to discuss.
The specific code: renderer.ts
Vue 3.0 DIFF algorithm and its principle