preface
This article does not cover the vDom implementation, the mount, or the render function. Only three diff algorithms are discussed. Component, functional-Component, Fragment, and Teleport are not considered as VNode types. Consider only Element and Text. The full code for this article is available in this project.
The following diff algorithm will appear in several methods, listed here, and explain their functions
-
Mount (vnode, parent, [refNode]): Generates a real DOM node from a Vnode. Parent is the real DOM node of its parent, refNode is the real DOM node, and its parent is the parent. If the refNode is not empty, the DOM node generated by the Vnode is inserted before the refNode; If the refNode is empty, the DOM node generated by the Vnode is inserted into the parent as the last child node
-
Patch (prevNode, nextNode, parent): can be simply understood as updating the current DOM node and calling diff algorithm to compare its own child nodes;
A, the React – the Diff
React’s approach is incremental. Determine whether the current node needs to be moved by comparing the node in the new list with the node in the original list.
1. Implementation principle
Let’s take an example like this.
NextList is the new list, prevList is the old list. In this example, we can immediately see that the new list does not need to be moved. Now I’m going to use react’s incremental idea to explain why the nodes in the new list don’t need to move.
We first iterate through the nextList and find out where each node is in the prevList.
function foo(prevList, nextList) {
for (let i = 0; i < nextList.length; i++) {
let nextItem = nextList[i];
for (let j = 0; j < prevList.length; j++) {
let prevItem = prevList[j]
if (nextItem === prevItem) {
}
}
}
}
Copy the codeIf the current position is larger than the previous position, the current node does not need to be moved. So we’ll define a lastIndex to record the location of the last node.
function foo(prevList, nextList) {
let lastIndex = 0
for (let i = 0; i < nextList.length; i++) {
let nextItem = nextList[i];
for (let j = 0; j < prevList.length; j++) {
let prevItem = prevList[j]
if (nextItem === prevItem) {
if (j < lastIndex) {
// Need to move the node
} else {
// No need to move the node. Record the current position and compare it with the next node
lastIndex = j
}
}
}
}
}
Copy the codeIn the example above, the nextList is 0, 1, 2, 3 for each node in the prevList. Each term has to be larger than the previous term, so you don’t have to move it, and that’s how React’s Diff algorithm works.
2. Find the node that you want to move
In the last section, we looked for the corresponding position by checking whether the ratios are equal. But in VDOM, every node is a vNode, so how do we know?
The answer is key. We determine the uniqueness of each node by assigning a value to the key of each node and making the key of vnodes in the same children array different, and then compare the new and old lists.
function reactDiff(prevChildren, nextChildren, parent) {
let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
let nextChild = nextChildren[i];
for (let j = 0; j < prevChildren.length; j++) {
let prevChild = prevChildren[j]
if (nextChild.key === prevChild.key) {
patch(prevChild, nextChild, parent)
if (j < lastIndex) {
// Need to move the node
} else {
// No need to move the node. Record the current position and compare it with the next node
lastIndex = j
}
}
}
}
}
Copy the code3. Move a node
First of all, let’s make it clear that mobile nodes refer to DOM nodes. Vnode. el points to the real DOM node corresponding to this node. The patch method assigns the updated DOM node to the EL attribute of the new VNode.
For the convenience of drawing, we use the value of key to represent vNode nodes. For the convenience of writing, we abbreviate vnode with key value a as vnode-a, and the real DOM node corresponding to vnode-a is dom-a
Let’s substitute the example above into reactDiff for execution. We walk through the new list and find where the vNode is in the old list. When traversing vnode-d, the previous traversal position in the old list is 0 < 2 < 3, indicating that nodes A, C, and d do not need to be moved. LastIndex = 3, vnode-b = 1,1 < 3, DOM -b = 1, DOM -b = 1, DOM -b = 1, DOM -b = 1, DOM -b = 1, DOM -b = 1, DOM -b = 1, DOM -b = 1, DOM -b = 1, DOM -b = 1
And what we can see by looking at it, is that all you need to do is move the dom-B to the dom-d. In other words, we find the VNode to be moved, we call the VNode α, and move the real DOM node corresponding to α to the real DOM corresponding to the previous VNode in the new list.
In this example, the real DOM node DOM -b of vnode-b is moved to the end of the vnode-b in the new list — the real DOM node DOM -d of vnode-d.
function reactDiff(prevChildren, nextChildren, parent) {
let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
let nextChild = nextChildren[i];
for (let j = 0; j < prevChildren.length; j++) {
let prevChild = prevChildren[j]
if (nextChild.key === prevChild.key) {
patch(prevChild, nextChild, parent)
if (j < lastIndex) {
// Move to the back of the previous node
let refNode = nextChildren[i - 1].el.nextSibling;
parent.insertBefore(nextChild.el, refNode)
} else {
// No need to move the node. Record the current position and compare it with the next node
lastIndex = j
}
}
}
}
}
Copy the codeWhy does it move like this? First, our list is traversed from beginning to end. This means that for the current VNode node, all nodes before that node are sorted, and if that node needs to be moved, then just move the DOM node after the previous VNode node, because that’s the order of the Vnodes in the new list.
4. Add a node
In the last section we only covered how to move nodes, but we ignored the case where there is a brand new VNode node in the new list that is not found in the old list. In this case, we need to generate a DOM node based on the new VNode node and insert it into the DOM tree.
At this point, we are faced with two questions: 1. How to discover the brand new node, and 2. Where to insert the generated DOM node
To solve the first problem, it is easy to find nodes. Let’s define a find variable with a value of false. If a VNode with the same key is found in the old list, change the find value to true. If the find value is false, the current node is the new node.
function reactDiff(prevChildren, nextChildren, parent) {
let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
let nextChild = nextChildren[i],
find = false;
for (let j = 0; j < prevChildren.length; j++) {
let prevChild = prevChildren[j]
if (nextChild.key === prevChild.key) {
find = true
patch(prevChild, nextChild, parent)
if (j < lastIndex) {
// Move to the back of the previous node
let refNode = nextChildren[i - 1].el.nextSibling;
parent.insertBefore(nextChild.el, refNode)
} else {
// No need to move the node. Record the current position and compare it with the next node
lastIndex = j
}
break}}if(! find) {// Insert a new node}}}Copy the codeOnce the new node is found, the next step is where to insert it, and the logic here is actually the same as the logic of the mobile node. We can see from the figure above that the new vnode-c follows vnode-b, and the DOM node of vnode-b — DOM -b has been sorted, so we only need to insert the DOM node generated by vnode-c into DOM -b.
But there is a special case where the new node is first in the new list, and we need to find the first node in the old list and insert the new node before the original first node.
function reactDiff(prevChildren, nextChildren, parent) {
let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
let nextChild = nextChildren[i],
find = false;
for (let j = 0; j < prevChildren.length; j++) {
let prevChild = prevChildren[j]
if (nextChild.key === prevChild.key) {
find = true
patch(prevChild, nextChild, parent)
if (j < lastIndex) {
// Move to the back of the previous node
let refNode = nextChildren[i - 1].el.nextSibling;
parent.insertBefore(nextChild.el, refNode)
} else {
// No need to move the node. Record the current position and compare it with the next node
lastIndex = j
}
break}}if(! find) {// Insert a new node
let refNode = i <= 0
? prevChildren[0].el
: nextChildren[i - 1].el.nextSibling mount(nextChild, parent, refNode); }}}Copy the code5. Remove the node
When the old node is not in the new list, we remove its CORRESPONDING DOM node.
function reactDiff(prevChildren, nextChildren, parent) {
let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
let nextChild = nextChildren[i],
find = false;
for (let j = 0; j < prevChildren.length; j++) {
let prevChild = prevChildren[j]
if (nextChild.key === prevChild.key) {
find = true
patch(prevChild, nextChild, parent)
if (j < lastIndex) {
// Move to the back of the previous node
let refNode = nextChildren[i - 1].el.nextSibling;
parent.insertBefore(nextChild.el, refNode)
} else {
// No need to move the node. Record the current position and compare it with the next node
lastIndex = j
}
break}}if(! find) {// Insert a new node
let refNode = i <= 0
? prevChildren[0].el
: nextChildren[i - 1].el.nextSibling mount(nextChild, parent, refNode); }}for (let i = 0; i < prevChildren.length; i++) {
let prevChild = prevChildren[i],
key = prevChild.key,
has = nextChildren.find(item= > item.key === key);
if(! has) parent.removeChild(prevChild.el) } }Copy the code6. Optimizations and deficiencies
So that’s the React Diff algorithm.
The current time complexity of reactDiff is O(m*n). We can exchange space for time and maintain the relationship between key and index as a Map, thus reducing the time complexity to O(n). The specific code can be viewed in this project.
Let’s look at an example like this
According to reactDiff’s thinking, we need to move dom-A after dom-C, and then dom-B after dom-A to complete Diff. But we can see from our observation that Diff can be done simply by moving dom-c to dom-A before it is done.
There is room for optimization. Next, we introduce the diff algorithm in Vue 2.x, the double-ended comparison algorithm, which solves the above problems
Vue 2.x Diff — Double end comparison
The so-called double-ended comparison is the new list and the old list of the two list of the head and tail comparison, in the process of comparison, the pointer will gradually move inward, until a list of nodes all traversal, the comparison stopped.
1. Implementation principle
Let’s start with four Pointers to the heads and tails of the two lists
function vue2Diff(prevChildren, nextChildren, parent) {
let oldStartIndex = 0,
oldEndIndex = prevChildren.length - 1
newStartIndex = 0,
newEndIndex = nextChildren.length - 1;
let oldStartNode = prevChildren[oldStartIndex],
oldEndNode = prevChildren[oldEndIndex],
newStartNode = nextChildren[nextStartIndex],
newEndNode = nextChildren[nextEndIndex];
}
Copy the codeWe find four nodes based on four Pointers, and we compare them, so how do we compare them? Here’s a four-step comparison
- useThe old listThe first node of
oldStartNodewithA new listThe first node ofnewStartNodecontrast - useThe old listThe last node of
oldEndNodewithA new listThe last node ofnewEndNodecontrast - useThe old listThe first node of
oldStartNodewithA new listThe last node ofnewEndNodecontrast - useThe old listThe last node of
oldEndNodewithA new listThe first node ofnewStartNodecontrast
Compare the above four steps to find reusable nodes with the same key, and stop the search when found in one step. The specific comparison sequence is as follows
Compare the sequence code structure as follows:
function vue2Diff(prevChildren, nextChildren, parent) {
let oldStartIndex = 0,
oldEndIndex = prevChildren.length - 1
newStartIndex = 0,
newEndIndex = nextChildren.length - 1;
let oldStartNode = prevChildren[oldStartIndex],
oldEndNode = prevChildren[oldEndIndex],
newStartNode = nextChildren[newStartIndex],
newEndNode = nextChildren[newEndIndex];
if (oldStartNode.key === newStartNode.key) {
} else if (oldEndNode.key === newEndNode.key) {
} else if (oldStartNode.key === newEndNode.key) {
} else if (oldEndNode.key === newStartNode.key) {
}
}
Copy the codeWhen a reusable node is found during comparison, we patch the element first, and then move the pointer forward/backward by one bit. Depending on the comparison node, we move the pointer and direction differently. The specific rules are as follows:
- whenThe old listThe first node of
oldStartNodewithA new listThe first node ofnewStartNodeWhen comparingkeyThe same. thenThe old listThe head of the pointeroldStartIndexwithA new listThe head of the pointernewStartIndexAt the same timeafterMove one bit. - whenThe old listThe last node of
oldEndNodewithA new listThe last node ofnewEndNodeWhen comparingkeyThe same. thenThe old listThe tail pointeroldEndIndexwithA new listThe tail pointernewEndIndexAt the same timebeforeMove one bit. - whenThe old listThe first node of
oldStartNodewithA new listThe last node ofnewEndNodeWhen comparingkeyThe same. thenThe old listThe head of the pointeroldStartIndextoafterMove a bit;A new listThe tail pointernewEndIndextobeforeMove one bit. - whenThe old listThe last node of
oldEndNodewithA new listThe first node ofnewStartNodeWhen comparingkeyThe same. thenThe old listThe tail pointeroldEndIndextobeforeMove a bit;A new listThe head of the pointernewStartIndextoafterMove one bit.
function vue2Diff(prevChildren, nextChildren, parent) {
let oldStartIndex = 0,
oldEndIndex = prevChildren.length - 1,
newStartIndex = 0,
newEndIndex = nextChildren.length - 1;
let oldStartNode = prevChildren[oldStartIndex],
oldEndNode = prevChildren[oldEndIndex],
newStartNode = nextChildren[newStartIndex],
newEndNode = nextChildren[newEndIndex];
if (oldStartNode.key === newStartNode.key) {
patch(oldvStartNode, newStartNode, parent)
oldStartIndex++
newStartIndex++
oldStartNode = prevChildren[oldStartIndex]
newStartNode = nextChildren[newStartIndex]
} else if (oldEndNode.key === newEndNode.key) {
patch(oldEndNode, newEndNode, parent)
oldEndIndex--
newEndIndex--
oldEndNode = prevChildren[oldEndIndex]
newEndNode = nextChildren[newEndIndex]
} else if (oldStartNode.key === newEndNode.key) {
patch(oldStartNode, newEndNode, parent)
oldStartIndex++
newEndIndex--
oldStartNode = prevChildren[oldStartIndex]
newEndNode = nextChildren[newEndIndex]
} else if(oldEndNode.key === newStartNode.key) { patch(oldEndNode, newStartNode, parent) oldEndIndex-- nextStartIndex++ oldEndNode = prevChildren[oldEndIndex] newStartNode = nextChildren[newStartIndex] }}Copy the codeAt the beginning of the section, we mentioned that we want to make the pointer inward, so we need to loop. The loop stops when all nodes in one of the lists have been traversed, as shown below
function vue2Diff(prevChildren, nextChildren, parent) {
let oldStartIndex = 0,
oldEndIndex = prevChildren.length - 1,
newStartIndex = 0,
newEndIndex = nextChildren.length - 1;
let oldStartNode = prevChildren[oldStartIndex],
oldEndNode = prevChildren[oldEndIndex],
newStartNode = nextChildren[newStartIndex],
newEndNode = nextChildren[newEndIndex];
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (oldStartNode.key === newStartNode.key) {
patch(oldStartNode, newStartNode, parent)
oldStartIndex++
newStartIndex++
oldStartNode = prevChildren[oldStartIndex]
newStartNode = nextChildren[newStartIndex]
} else if (oldEndNode.key === newEndNode.key) {
patch(oldEndNode, newEndNode, parent)
oldEndIndex--
newndIndex--
oldEndNode = prevChildren[oldEndIndex]
newEndNode = nextChildren[newEndIndex]
} else if (oldStartNode.key === newEndNode.key) {
patch(oldvStartNode, newEndNode, parent)
oldStartIndex++
newEndIndex--
oldStartNode = prevChildren[oldStartIndex]
newEndNode = nextChildren[newEndIndex]
} else if(oldEndNode.key === newStartNode.key) { patch(oldEndNode, newStartNode, parent) oldEndIndex-- newStartIndex++ oldEndNode = prevChildren[oldEndIndex] newStartNode = nextChildren[newStartIndex] }}}Copy the codeAt this point, the whole cycle is complete, and we need to consider the following two questions:
- Under what circumstances
DOMNodes need to be moved DOMHow nodes move
Let’s solve the first question: when do you need to move?
In the first loop, we discover in the fourth step that oldEndNode, the end node of the old list, has the same key as newStartNode, the head node of the new list, and is a reusable DOM node. By looking at it, we can see that the node that was at the end of the old list is at the beginning of the new list. No one is ahead of him because he is first, so we just need to move the current node ahead of the first node in the old list and make it the first node.
function vue2Diff(prevChildren, nextChildren, parent) {
// ...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (oldStartNode.key === newStartNode.key) {
// ...
} else if (oldEndNode.key === newEndNode.key) {
// ...
} else if (oldStartNode.key === newEndNode.key) {
// ...
} else if (oldEndNode.key === newStartNode.key) {
patch(oldEndNode, newStartNode, parent)
// Move before the old list head node
parent.insertBefore(oldEndNode.el, oldStartNode.el)
oldEndIndex--
newStartIndex++
oldEndNode = prevChildren[oldEndIndex]
newStartNode = nextChildren[newStartIndex]
}
}
}
Copy the code
Then we enter the second loop, where we discover that oldEndNode, the end node of the old list, and newEndNode, the end node of the new list, are reuse nodes. It was the tail node in the old list, and it’s the tail node in the new list, which means it doesn’t have to move, so we don’t have to do anything.
Similarly, if oldStartNode, the head of the old list, and newStartNode, the head of the new list, are reuse nodes, we don’t need to do anything.
In the third part of the loop, we find that oldStartNode, the head node of the old list, and newEndNode, the tail node of the new list, are reuse nodes. And at this point, as you can certainly see at A glance, we’re just going to move the dom-A behind the dom-B.
So the convention, just to explain, is that you have the head node in the old list, and then you have the tail node in the new list. Just move the current node in the old list to the end of the original node.
function vue2Diff(prevChildren, nextChildren, parent) {
// ...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (oldStartNode.key === newStartNode.key) {
// ...
} else if (oldEndNode.key === newEndNode.key) {
// ...
} else if (oldStartNode.key === newEndNode.key) {
patch(oldStartNode, newEndNode, parent)
parent.insertBefore(oldStartNode.el, oldEndNode.el.nextSibling)
oldStartIndex++
newEndIndex--
oldStartNode = prevChildren[oldStartIndex]
newEndNode = nextChildren[newEndIndex]
} else if (oldEndNode.key === newStartNode.key) {
/ /...}}}Copy the code
OK, enter the last loop. In the first step, the old list head node oldStartNode is in the same position as the new list head node newStartNode, so nothing needs to be done. Then the loop is closed, and this is how the Vue2 double-ended comparison works.
2. Non-ideal
In the last section, we discussed the principle of double-ended comparison, but there is a special case, when the four times of comparison did not find the reuse node, we can only take the first node of the new list to the old list to find the node with the same key.
function vue2Diff(prevChildren, nextChildren, parent) {
/ /...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (oldStartNode.key === newStartNode.key) {
/ /...
} else if (oldEndNode.key === newEndNode.key) {
/ /...
} else if (oldStartNode.key === newEndNode.key) {
/ /...
} else if (oldEndNode.key === newStartNode.key) {
/ /...
} else {
// Find a node in the old list with the same key as the head node in the new list
let newKey = newStartNode.key,
oldIndex = prevChildren.findIndex(child= >child.key === newKey); }}}Copy the codeThere are two ways to find a node: one is found in the old list, and the other is not found. Let’s talk about what we found in the picture above.
When we find the corresponding VNode in the old list, we just need to move the DOM element of the found node to the beginning. The logic here is exactly the same as the logic in step 4, except the fourth step is the moved tail node, and here is the moved found node. After the DOM move, instead of changing the node in the old list to undefined, this is a crucial step, because we’ve already moved the node so we don’t need to do the comparison again. Finally we move the header pointer newStartIndex back one bit.
function vue2Diff(prevChildren, nextChildren, parent) {
/ /...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (oldStartNode.key === newStartNode.key) {
/ /...
} else if (oldEndNode.key === newEndNode.key) {
/ /...
} else if (oldStartNode.key === newEndNode.key) {
/ /...
} else if (oldEndNode.key === newStartNode.key) {
/ /...
} else {
// Find a node in the old list with the same key as the head node in the new list
let newtKey = newStartNode.key,
oldIndex = prevChildren.findIndex(child= > child.key === newKey);
if (oldIndex > -1) {
let oldNode = prevChildren[oldIndex];
patch(oldNode, newStartNode, parent)
parent.insertBefore(oldNode.el, oldStartNode.el)
prevChildren[oldIndex] = undefined
}
newStartNode = nextChildren[++newStartIndex]
}
}
}
Copy the codeWhat if the reuse node is not found in the old list? Simply create a new node and place it at the front, then move the head pointer back to newStartIndex.
function vue2Diff(prevChildren, nextChildren, parent) {
/ /...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (oldStartNode.key === newStartNode.key) {
/ /...
} else if (oldEndNode.key === newEndNode.key) {
/ /...
} else if (oldStartNode.key === newEndNode.key) {
/ /...
} else if (oldEndNode.key === newStartNode.key) {
/ /...
} else {
// Find a node in the old list with the same key as the head node in the new list
let newtKey = newStartNode.key,
oldIndex = prevChildren.findIndex(child= > child.key === newKey);
if (oldIndex > -1) {
let oldNode = prevChildren[oldIndex];
patch(oldNode, newStartNode, parent)
parent.insertBefore(oldNode.el, oldStartNode.el)
prevChildren[oldIndex] = undefined
} else {
mount(newStartNode, parent, oldStartNode.el)
}
newStartNode = nextChildren[++newStartIndex]
}
}
}
Copy the codeFinally, the current node is skipped when the old list iterates through undefind.
function vue2Diff(prevChildren, nextChildren, parent) {
/ /...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (oldStartNode === undefind) {
oldStartNode = prevChildren[++oldStartIndex]
} else if (oldEndNode === undefind) {
oldEndNode = prevChildren[--oldEndIndex]
} else if (oldStartNode.key === newStartNode.key) {
/ /...
} else if (oldEndNode.key === newEndNode.key) {
/ /...
} else if (oldStartNode.key === newEndNode.key) {
/ /...
} else if (oldEndNode.key === newStartNode.key) {
/ /...
} else {
// ...}}}Copy the code3. Add a node
Let’s start with an example
This example is very simple. The tail node is the same several times, and the tail pointer is moved forward until the end of the loop, as shown below
OldEndIndex is smaller than oldStartIndex, but there are still nodes in the new list. We just need to insert the remaining nodes into oldStartNode’s DOM one by one. Why before you insert oldStartNode? The reason is that the remaining nodes in the new list are located before oldStartNode. If the remaining nodes are located after oldStartNode, oldStartNode will be compared first. This is something to think about.
function vue2Diff(prevChildren, nextChildren, parent) {
/ /...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
// ...
}
if (oldEndIndex < oldStartIndex) {
for (let i = newStartIndex; i <= newEndIndex; i++) {
mount(nextChildren[i], parent, prevStartNode.el)
}
}
}
Copy the code4. Remove the node
In contrast to the previous section, when newEndIndex of the new list is less than newStartIndex, we simply remove the remaining nodes from the old list. Here we need to note the undefind of the old list. As mentioned in section 2, when the first and last nodes are different, we look for the first node in the new list from the old list. After moving the DOM nodes, we change the node from the old list to undefind. So we need to be aware of these undefinds during the last delete and just skip the current loop if we encounter them.
function vue2Diff(prevChildren, nextChildren, parent) {
/ /...
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
// ...
}
if (oldEndIndex < oldStartIndex) {
for (let i = newStartIndex; i <= newEndIndex; i++) {
mount(nextChildren[i], parent, prevStartNode.el)
}
} else if (newEndIndex < newStartIndex) {
for (let i = oldStartIndex; i <= oldEndIndex; i++) {
if (prevChildren[i]) {
partent.removeChild(prevChildren[i].el)
}
}
}
}
Copy the code5. Summary
At this point, the double-ended comparison is complete. Here is the complete code.
function vue2diff(prevChildren, nextChildren, parent) {
let oldStartIndex = 0,
newStartIndex = 0,
oldStartIndex = prevChildren.length - 1,
newStartIndex = nextChildren.length - 1,
oldStartNode = prevChildren[oldStartIndex],
oldEndNode = prevChildren[oldStartIndex],
newStartNode = nextChildren[newStartIndex],
newEndNode = nextChildren[newStartIndex];
while (oldStartIndex <= oldStartIndex && newStartIndex <= newStartIndex) {
if (oldStartNode === undefined) {
oldStartNode = prevChildren[++oldStartIndex]
} else if (oldEndNode === undefined) {
oldEndNode = prevChildren[--oldStartIndex]
} else if (oldStartNode.key === newStartNode.key) {
patch(oldStartNode, newStartNode, parent)
oldStartIndex++
newStartIndex++
oldStartNode = prevChildren[oldStartIndex]
newStartNode = nextChildren[newStartIndex]
} else if (oldEndNode.key === newEndNode.key) {
patch(oldEndNode, newEndNode, parent)
oldStartIndex--
newStartIndex--
oldEndNode = prevChildren[oldStartIndex]
newEndNode = nextChildren[newStartIndex]
} else if (oldStartNode.key === newEndNode.key) {
patch(oldStartNode, newEndNode, parent)
parent.insertBefore(oldStartNode.el, oldEndNode.el.nextSibling)
oldStartIndex++
newStartIndex--
oldStartNode = prevChildren[oldStartIndex]
newEndNode = nextChildren[newStartIndex]
} else if (oldEndNode.key === newStartNode.key) {
patch(oldEndNode, newStartNode, parent)
parent.insertBefore(oldEndNode.el, oldStartNode.el)
oldStartIndex--
newStartIndex++
oldEndNode = prevChildren[oldStartIndex]
newStartNode = nextChildren[newStartIndex]
} else {
let newKey = newStartNode.key,
oldIndex = prevChildren.findIndex(child= > child && (child.key === newKey));
if (oldIndex === -1) {
mount(newStartNode, parent, oldStartNode.el)
} else {
let prevNode = prevChildren[oldIndex]
patch(prevNode, newStartNode, parent)
parent.insertBefore(prevNode.el, oldStartNode.el)
prevChildren[oldIndex] = undefined
}
newStartIndex++
newStartNode = nextChildren[newStartIndex]
}
}
if (newStartIndex > newStartIndex) {
while (oldStartIndex <= oldStartIndex) {
if(! prevChildren[oldStartIndex]) { oldStartIndex++continue
}
parent.removeChild(prevChildren[oldStartIndex++].el)
}
} else if (oldStartIndex > oldStartIndex) {
while (newStartIndex <= newStartIndex) {
mount(nextChildren[newStartIndex++], parent, oldStartNode.el)
}
}
}
Copy the codeVue3 Diff — the longest increasing subsequence
Vue3’s Diff was borrowed from Inferno, and there are two ideas in the algorithm. The first is the preprocessing of the same pre and post elements; The second is the longest increasing subsequence, which is similar to but different from React’s Diff. Let’s introduce one by one.
1. Pre – and post-processing
Let’s look at these two paragraphs
Hello World
Hey World
In fact, at a simple glance, we can find that part of the two paragraphs of text is the same. These words do not need to be modified or moved. The middle letters really need to be modified, so diff becomes the following part
text1: 'llo'
text2: 'y'
Copy the codeLet’s switch to vNode, as shown below.
The nodes in green boxes in the figure do not need to be moved, they only need to patch. Let’s write this logic in code.
function vue3Diff(prevChildren, nextChildren, parent) {
let j = 0,
prevEnd = prevChildren.length - 1,
nextEnd = nextChildren.length - 1,
prevNode = prevChildren[j],
nextNode = nextChildren[j];
while (prevNode.key === nextNode.key) {
patch(prevNode, nextNode, parent)
j++
prevNode = prevChildren[j]
nextNode = nextChildren[j]
}
prevNode = prevChildren[prevEnd]
nextNode = prevChildren[nextEnd]
while (prevNode.key === nextNode.key) {
patch(prevNode, nextNode, parent)
prevEnd--
nextEnd--
prevNode = prevChildren[prevEnd]
nextNode = prevChildren[nextEnd]
}
}
Copy the codeNow, this is where we need to think about the boundary case, and there are two cases. One is j > prevEnd; The other is j > nextEnd.
For example, if j > prevEnd and j <= nextEnd, we only need to insert the remaining nodes in the new list between j and nextEnd. On the other hand, if j > nextEnd, we delete all nodes from the old list between j and prevEnd.
function vue3Diff(prevChildren, nextChildren, parent) {
// ...
if (j > prevEnd && j <= nextEnd) {
let nextpos = nextEnd + 1,
refNode = nextpos >= nextChildren.length
? null
: nextChildren[nextpos].el;
while(j <= nextEnd) mount(nextChildren[j++], parent, refNode)
} else if (j > nextEnd && j <= prevEnd) {
while(j <= prevEnd) parent.removeChild(prevChildren[j++].el)
}
}
Copy the codeLet’s think about it a little bit more, in our while loop, the Pointers are coming in from both ends, so we should be doing the boundary case inside the loop, so we use the label syntax, and when we fire the boundary case, we exit the whole loop, we go straight into the judgment. The code is as follows:
function vue3Diff(prevChildren, nextChildren, parent) {
let j = 0,
prevEnd = prevChildren.length - 1,
nextEnd = nextChildren.length - 1,
prevNode = prevChildren[j],
nextNode = nextChildren[j];
/ / label syntax
outer: {
while (prevNode.key === nextNode.key) {
patch(prevNode, nextNode, parent)
j++
// If the outer case is triggered in the loop, break it and execute the judgment after the outer case
if (j > prevEnd || j > nextEnd) break outer
prevNode = prevChildren[j]
nextNode = nextChildren[j]
}
prevNode = prevChildren[prevEnd]
nextNode = prevChildren[nextEnd]
while (prevNode.key === nextNode.key) {
patch(prevNode, nextNode, parent)
prevEnd--
nextEnd--
// If the outer case is triggered in the loop, break it and execute the judgment after the outer case
if (j > prevEnd || j > nextEnd) break outer
prevNode = prevChildren[prevEnd]
nextNode = prevChildren[nextEnd]
}
}
// To determine the boundary case
if (j > prevEnd && j <= nextEnd) {
let nextpos = nextEnd + 1,
refNode = nextpos >= nextChildren.length
? null
: nextChildren[nextpos].el;
while(j <= nextEnd) mount(nextChildren[j++], parent, refNode)
} else if (j > nextEnd && j <= prevEnd) {
while(j <= prevEnd) parent.removeChild(prevChildren[j++].el)
}
}
Copy the code2. Determine whether to move the device
In fact, several algorithms look down, the routine is very obvious, is to find the moving node, and then give him to move to the correct position. Add the new nodes that should be added, delete the old nodes that should be deleted, and the algorithm is over. This algorithm is no exception, and we’re going to see how it works.
After the current/post preprocessing is done, we move on to the real diff. First, we create a source array based on the number of nodes remaining in the new list and fill the array with -1.
Let’s write this logic first.
function vue3Diff(prevChildren, nextChildren, parent) {
/ /...
outer: {
// ...
}
// To determine the boundary case
if (j > prevEnd && j <= nextEnd) {
// ...
} else if (j > nextEnd && j <= prevEnd) {
// ...
} else {
let prevStart = j,
nextStart = j,
nextLeft = nextEnd - nextStart + 1.// The number of remaining nodes in the new list
source = new Array(nextLeft).fill(-1); // Create an array filled with -1}}Copy the codeSo what does this source array do? We store the position of the new node in the old list in this array, and we calculate the longest incrementing subsequence of the new node based on the source to move the DOM node. To do this, we first create an object to store the relationship between the nodes in the current list and the index, and then go to the old list to find the location.
When looking for a node, if the old node is not in the new list, just delete it. In addition, we also need a number to record the nodes we have patched. If the number is the same as the number of remaining nodes in the new list, we can directly delete the remaining old nodes
function vue3Diff(prevChildren, nextChildren, parent) {
/ /...
outer: {
// ...
}
// To determine the boundary case
if (j > prevEnd && j <= nextEnd) {
// ...
} else if (j > nextEnd && j <= prevEnd) {
// ...
} else {
let prevStart = j,
nextStart = j,
nextLeft = nextEnd - nextStart + 1.// The number of remaining nodes in the new list
source = new Array(nextLeft).fill(-1), // Create an array filled with -1
nextIndexMap = {}, // Map the new list node to index
patched = 0; // The number of updated nodes
// Save the mapping
for (let i = nextStart; i <= nextEnd; i++) {
let key = nextChildren[i].key
nextIndexMap[key] = i
}
// Go to the old list to find the location
for (let i = prevStart; i <= prevEnd; i++) {
let prevNode = prevChildren[i],
prevKey = prevNode.key,
nextIndex = nextIndexMap[prevKey];
// Delete the old node from the new list if there is no new node or all new nodes have been updated
if (nextIndex === undefind || patched >= nextLeft) {
parent.removeChild(prevNode.el)
continue
}
// Find the corresponding node
let nextNode = nextChildren[nextIndex];
patch(prevNode, nextNode, parent);
// Assign a value to source
source[nextIndex - nextStart] = i
patched++
}
}
}
Copy the code
After finding the position, we observe the re-assigned source, and we can see that if it is a brand new node, its corresponding value in the source array is the initial -1. Through this step, we can distinguish which is the brand new node and which is reusable.
Second, we need to determine whether we need to move. So how do you judge movement? Very simple, just like React we’re incrementing, so if we find an index that’s incrementing all the time, that means we don’t have to move any nodes. We set a variable to hold whether the state needs to be moved or not.
function vue3Diff(prevChildren, nextChildren, parent) {
/ /...
outer: {
// ...
}
// To determine the boundary case
if (j > prevEnd && j <= nextEnd) {
// ...
} else if (j > nextEnd && j <= prevEnd) {
// ...
} else {
let prevStart = j,
nextStart = j,
nextLeft = nextEnd - nextStart + 1.// The number of remaining nodes in the new list
source = new Array(nextLeft).fill(-1), // Create an array filled with -1
nextIndexMap = {}, // Map the new list node to index
patched = 0,
move = false.// Whether to move
lastIndex = 0; // Record the last position
// Save the mapping
for (let i = nextStart; i <= nextEnd; i++) {
let key = nextChildren[i].key
nextIndexMap[key] = i
}
// Go to the old list to find the location
for (let i = prevStart; i <= prevEnd; i++) {
let prevNode = prevChildren[i],
prevKey = prevNode.key,
nextIndex = nextIndexMap[prevKey];
// Delete the old node from the new list if there is no new node or all new nodes have been updated
if (nextIndex === undefind || patched >= nextLeft) {
parent.removeChild(prevNode.el)
continue
}
// Find the corresponding node
let nextNode = nextChildren[nextIndex];
patch(prevNode, nextNode, parent);
// Assign a value to source
source[nextIndex - nextStart] = i
patched++
// The increment method determines whether the move is needed
if (nextIndex < lastIndex) {
move = false
} else {
lastIndex = nextIndex
}
}
if (move) {
// Need to move
} else {
// No need to move}}}Copy the code3. How does DOM move
Having decided if we need to move, we need to think about how. Once a DOM move is required, the first thing we need to do is find the longest increasing subsequence of source.
function vue3Diff(prevChildren, nextChildren, parent) {
/ /...
if (move) {
const seq = lis(source); / / [0, 1]
// Need to move
} else {
// No need to move}}Copy the codeWhat is the longest increasing subsequence: Given a sequence of values, find a subsequence of it in which the values are increasing and the elements in the subsequence are not necessarily continuous in the original sequence. For example, given a numeric sequence: [0, 8, 4, 12]. Then its longest increasing subsequence is: [0, 8, 12]. Of course, there are many possible answers, for example: [0, 4, 12] is also ok.
We cover longest increasing subsequences separately in the next section
In the above code, we call the lis function to find that the longest increasing subsequence of array source is [0, 1]. We know that the value of the source array is [2, 3, 1, -1], and it is obvious that the longest increment subsequence should be [2, 3], but why is the result calculated as [0, 1]? In fact, [0, 1] represents the position index of each element in the longest increasing subsequence in the source array, as shown in the figure below:
We renumber the new list according to source and find the longest increasing subsequence.
We iterate through each item in the source from the back to the front. Three things happen:
- The current value is
- 1, which indicates that this node is a brand new node, and because we areFrom the back forwardIterating, we just create the DOM node and insert it at the end of the queue. - The current index is
Longest increasing subsequenceThe value of PI, which is PIi === seq[j]This means that the node does not need to be moved - The current index is not
Longest increasing subsequence, which means that the DOM node needs to be moved. It makes sense to insert the DOM node directly at the end of the queue, because the end of the queue is sorted.
function vue3Diff(prevChildren, nextChildren, parent) {
/ /...
if (move) {
// Need to move
const seq = lis(source); / / [0, 1]
let j = seq.length - 1; // The pointer to the oldest sequence
// Iterates from back to front
for (let i = nextLeft - 1; i >=0; i--) {
let pos = nextStart + i, // The index of the new list
nextNode = nextChildren[pos], / / find the vnode
nextPos = pos + 1.// The position of the next node to move the DOM
refNode = nextPos >= nextChildren.length ? null : nextChildren[nextPos].el, / / the DOM node
cur = source[i]; // The value of the current source is used to determine whether the node needs to be moved
if (cur === -1) {
// In case 1, the node is brand new
mount(nextNode, parent, refNode)
} else if (cur === seq[j]) {
// Case 2, which is an increasing subsequence, does not need to move the node
// Let j point to the next
j--
} else {
// In case 3, not an increasing subsequence, the node needs to be moved
parent.insetBefore(nextNode.el, refNode)
}
}
} else {
// No need to move}}Copy the codeHaving said the case where you need to move, let’s say the case where you don’t need to move. If there is no need to move, we just need to determine if there is a new node to add to it. The specific code is as follows:
function vue3Diff(prevChildren, nextChildren, parent) {
/ /...
if (move) {
const seq = lis(source); / / [0, 1]
let j = seq.length - 1; // The pointer to the oldest sequence
// Iterates from back to front
for (let i = nextLeft - 1; i >=0; i--) {
let pos = nextStart + i, // The index of the new list
nextNode = nextChildren[pos], / / find the vnode
nextPos = pos + 1.// The position of the next node to move the DOM
refNode = nextPos >= nextChildren.length ? null : nextChildren[nextPos].el, / / the DOM node
cur = source[i]; // The value of the current source is used to determine whether the node needs to be moved
if (cur === -1) {
// In case 1, the node is brand new
mount(nextNode, parent, refNode)
} else if (cur === seq[j]) {
// Case 2, which is an increasing subsequence, does not need to move the node
// Let j point to the next
j--
} else {
// In case 3, not an increasing subsequence, the node needs to be moved
parent.insetBefore(nextNode.el, refNode)
}
}
} else {
// No need to move
for (let i = nextLeft - 1; i >=0; i--) {
let cur = source[i]; // The value of the current source is used to determine whether the node needs to be moved
if (cur === -1) {
let pos = nextStart + i, // The index of the new list
nextNode = nextChildren[pos], / / find the vnode
nextPos = pos + 1.// The position of the next node to move the DOM
refNode = nextPos >= nextChildren.length ? null : nextChildren[nextPos].el, / / the DOM node
mount(nextNode, parent, refNode)
}
}
}
}
Copy the codeAt this point, vue3.0 diff is complete.
4. Longest increasing subsequence
Leetcode has the original problem, the official analysis is very clear, do not understand what I say can go to see the official analysis.
Let’s take this array as an example
[10.9.2.5.3.8.7.13]
Copy the codeWe can think about this using the idea of dynamic programming. The idea of dynamic programming is to decompose a large problem into several small sub-problems and try to get the optimal solution of these sub-problems. The optimal solution of the sub-problems may be used in the larger problems, so that the optimal solution of the small problems can be finally obtained.
If we assume an array [13] with only one value, then the longest incrementing subsequence of that array is [13] itself, of length 1. So we assume that the increment sequence of each term has a length of 1
So we add a value [7, 13] to the array this time. Since 7 < 13, the longest incrementing subsequence of the array is [7, 13], so the length is 2. Then, can we consider that when [7] is less than [13], the length of the increasing sequence headed by [7] is the sum of the length of [7] and the length of [13], that is, 1 + 1 = 2.
Ok, let’s calculate the array based on this idea. Let’s start by assigning each value to an initial value of 1
First of all, 7 is less than 13 so the length of 7 is the length of 13 plus 1. 1 plus 1 is 2
Let’s go ahead and compare eight. We first compare it to 7, it doesn’t increase, but it doesn’t matter we can continue to compare it to 13, 8 less than 13 does increase, so the length of 8 is also going to increase by 1 and the length of 13 is going to increase by 2
Let’s compare 3, let’s compare it to 8 first, 3 is less than 8, so the length of 3 is the length of 8 plus 1, so the length of 3 is 3. But it’s not over yet. We need to compare 3 to 7. Similarly, 3 < 7, at this time, we need to calculate a length of 7 plus one is also 3, we compare the two lengths, if the original length is not as large as the length calculated this time, we replace it, otherwise we keep the original value. Since 3 === 3, we choose not to replace. Finally, we compare 3 with 13. The same 3 is less than 13, and the calculated length is 2, which is smaller than the original length 3. We choose to keep the original value.
And so on, and so on, and so on, and so on, and so on
We take the largest value, 4, which represents the number of the longest increasing subsequence of. The code is as follows:
function lis(arr) {
let len = arr.length,
dp = new Array(len).fill(1); // To save the length
for (let i = len - 1; i >= 0; i--) {
let cur = arr[i]
for(let j = i + 1; j < len; j++) {
let next = arr[j]
// If incrementing, take a larger length
if (cur < next) dp[i] = Math.max(dp[j]+1, dp[i])
}
}
return Math.max(... dp) }Copy the codeSo far, we’ve talked about the basic longest increasing subsequence. In vue3.0, however, what we need is the index of the longest increasing subsequence in the original array. So we also need to create an array to hold the index in the array that corresponds to the oldest sequence of each value. The specific code is as follows:
function lis(arr) {
let len = arr.length,
res = [],
dp = new Array(len).fill(1);
// Save the default index
for (let i = 0; i < len; i++) {
res.push([i])
}
for (let i = len - 1; i >= 0; i--) {
let cur = arr[i],
nextIndex = undefined;
// If the value is -1, skip it directly, because -1 represents a new node and does not need to be sorted
if (cur === -1) continue
for (let j = i + 1; j < len; j++) {
let next = arr[j]
// The increment condition is satisfied
if (cur < next) {
let max = dp[j] + 1
// Whether the current length is larger than the original length
if (max > dp[i]) {
dp[i] = max
nextIndex = j
}
}
}
// Record the value that satisfies the condition, corresponding to the index in the array
if(nextIndex ! = =undefined) res[i].push(... res[nextIndex]) }let index = dp.reduce((prev, cur, i, arr) = > cur > arr[prev] ? i : prev, dp.length - 1)
Return the index of the longest incrementing subsequence
return result[index]
}
Copy the code