preface
In interpreting the DIff algorithm of Vue, I integrated the diff function into the vue-Mini-Demo project I wrote earlier, which has implemented data hijacking, template compilation and data response, and instruction binding (for example, V-for). If you’re interested, you can download it and debug it.
Virtual DOM (Virtual DOM)
The diff algorithm is designed to work with the virtual DOM, and we need to understand the virtual DOM before we can understand it. So what is the virtual DOM?
In a nutshell: a virtual DOM is a JavaScript object that describes the real DOM. By saying that, maybe it’s just letting the students know that it’s an object. Therefore, we need to give an example so that you can understand it clearly.
- Real DOM
<div>
<span>dom</span>
</div>
Copy the code- Corresponding virtual DOM
const Vnode = {
tag: 'ul'.children: [{tag: 'span'.text: 'dom'}};Copy the codeFrom the simple example above, it is not hard to see that the Virtual DOM is actually abstracted from the real DOM data, and then simulates the tree structure in the form of objects.
The diff algorithm
Rendering the real DOM is notoriously expensive (especially for complex views). For example, when we modify some data and render it directly into the real DOM, the entire DOM tree will be redrawn and rearranged. So is there a way to update only the DOM we modify and not all of it?
The answer is: yes! That’s the Diff algorithm. It allows us to compare two virtual DOM to find out the differences between them, and then update and render the DOM using other methods (for example, the patch function).
Let’s look at an example (snabbdom as an example) :
case
Snabbdom is a virtual DOM library focused on simplicity, modularity, power, and performance. The virtual DOM used internally in Vue 2.x was modified in reference to it.
There are many tutorials on how to use snabbDOM on the web, but I’m using it directly through BootCDN.
<! DOCTYPE html><html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="Width = device - width, initial - scale = 1.0" />
<title>snabbdom</title>
<script src="https://cdn.bootcdn.net/ajax/libs/snabbdom/0.7.4/snabbdom.js"></script>
<script src="https://cdn.bootcdn.net/ajax/libs/snabbdom/0.7.4/snabbdom-attributes.js"></script>
<script src="https://cdn.bootcdn.net/ajax/libs/snabbdom/0.7.4/snabbdom-dataset.js"></script>
<script src="https://cdn.bootcdn.net/ajax/libs/snabbdom/0.7.4/snabbdom-eventlisteners.js"></script>
<script src="https://cdn.bootcdn.net/ajax/libs/snabbdom/0.7.4/snabbdom-props.js"></script>
<script src="https://cdn.bootcdn.net/ajax/libs/snabbdom/0.7.4/snabbdom-style.js"></script>
<script src="https://cdn.bootcdn.net/ajax/libs/snabbdom/0.7.4/snabbdom-class.js"></script>
<script src="https://cdn.bootcdn.net/ajax/libs/snabbdom/0.7.4/h.js"></script>
</head>
<body>
<div id="app"></div>
<button id="btn">new</button>
<script>
const app = document.getElementById('app')
const { h, init } = window.snabbdom;
// Create patch function to update dom
var patch = snabbdom.init([
// Initialize the patch function and the selected module
snabbdom_class,
snabbdom_props,
snabbdom_style,
snabbdom_eventlisteners
]);
// First render
let vnode = h('div#app', [h('p'.'1')]);
patch(app, vnode);
// Click the button: for the second rendering, the dom element created from the new virtual DOM will replace the previous one,
// Only the dom that has changed will be modified
document.getElementById('btn').addEventListener('click'.function () {
let newNode = h('div#app', [h('p'.'1'), h('p'.'2')]);
patch(vnode, newNode);
});
</script>
</body>
</html>
Copy the codeThe results show
Virtual DOM changes to add a node object.
When rendering the real DOM, click the “add” button and only render the new DOM (the difference between the two virtual DOM), nothing else is changed (the nodes with flashing are newly rendered).
By reading the above pictures, we can know that newNode (virtual DOM) during the second patch has an extra line of code H (‘p’, ‘2’) than vnode (virtual DOM) during the first patch, which is reflected in the virtual DOM, that is, an extra node object. And when rendering, only the difference (the new node) is rendered.
Diff algorithm comparison mode
The snabbDOM example is just to get a better sense of the diff algorithm. Next, we’ll start analyzing the implementation of the DIff algorithm in VUE.
When comparing the old and new virtual DOM, the DIff algorithm in VUE only compares the same level, not across levels. It’s hard to say, but here’s an example:
- Let’s say this is our actual DOM structure
// dom node 1 -- before
<div>
<p>
<span>1</span>
<span>2</span>
</p>
<p>
<span>3</span>
<span>4</span>
</p>
</div>
// dom node 2 -- after
<div>
<p>
<span>1</span>
<span>2</span>
</p>
<p>
<span>3</span>
<span>4</span>
</p>
</div>
Copy the code- The virtual DOM as opposed to the real DOM (a little lazy, looking up an image someone else had drawn on the Internet).
Div to div or P to P, not div to P or SPAN. So, let’s talk about how same-level nodes are compared in the code.
The specific implementation
The patch function
This function is called to generate the corresponding HTML (commonly known as patching) of the vNode virtual node. The patch function receives oldVnode and vNode parameters representing the old node and the new node respectively. It mainly deals with the following cases (only the core implementation here) :
- OldVnode creates a new node if the old node does not exist or is a real element (the first rendering accepts basically HTML).
- If it is not a real element and the old and new virtual nodes are the same object, patch and update the existing root node.
// To facilitate reading and understanding, only the core functions of the code are listed here
function patch(oldVnode, vnode) {
/ /... omit
// The old node does not exist
if (isUndef(oldVnode)) {
// empty mount (likely as component), create new root element
isInitialPatch = true;
createElm(vnode, insertedVnodeQueue);
} else {
// Whether it is a real element
const isRealElement = isDef(oldVnode.nodeType);
// If it is not a real element and the old and new virtual nodes are the same object, patch and update the existing root node
if(! isRealElement && sameVnode(oldVnode, vnode)) { patchVnode(oldVnode, vnode);// Patch the existing root node
} else {
if (isRealElement) {
// Create an empty node to replace the oldVnode
oldVnode = emptyNodeAt(oldVnode);
}
// Replace the existing element
const oldElm = oldVnode.elm;
const parentElm = nodeOps.parentNode(oldElm); // Get the oldElm parent element
// Create a node
createElm(
vnode,
insertedVnodeQueue,
parentElm,
// Returns the element immediately after oldElm
nodeOps.nextSibling(oldElm)
);
/ /... omit}}return vnode.elm;
};
Copy the codePatchVnode function
When it is determined that the old and new virtual nodes need to be compared, the patchVnode function is called. It is mainly responsible for:
- Check whether vNode and oldVnode are the same node object. If yes, return without comparing.
- If vnode.text does not exist, perform the following operations:
- If vNode has children and oldVnode does not, add the children of VNode to ELM.
- If VNode has no child node but oldVnode does, delete the child node of ELM.
- If they both have child nodes, the implementation
updateChildrenThe function compares and finds the differences between the two child nodes to update them (which is the heart of diff).
- If vnode.text and oldvNode. text exist and are not equal, assign vnode.text to ELM.
// To facilitate reading and understanding, only the core functions of the code are listed here
function patchVnode(oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly) {
// Stop the comparison if the old and new nodes are the same object
if (oldVnode === vnode) {
return;
}
if (isDef(vnode.elm) && isDef(ownerArray)) {
// Clone the vNode. This is a strategy used in DIFF called in-place reuse.
// It refers to reusing the previous DOM as much as possible so that there is less manipulation of the DOM when rendering the real DOM.
vnode = ownerArray[index] = cloneVNode(vnode);
}
const elm = (vnode.elm = oldVnode.elm);
let i;
const data = vnode.data;
const oldCh = oldVnode.children;
const ch = vnode.children;
// VNode attributes (class, style, etc.) are updated if both the data and tag attributes are true
if (isDef(data) && isPatchable(vnode)) {
for (i = 0; i < cbs.update.length; ++i) { cbs.update[i](oldVnode, vnode); }}// vnode.text is undefined or null
if (isUndef(vnode.text)) {
// If both oldVnode and vnode have child nodes and are not equal, update the child nodes
if (isDef(oldCh) && isDef(ch)) {
if (oldCh !== ch) {
updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly);
}
} else if (isDef(ch)) { // If only VNode has child nodes, add them to ELM
checkDuplicateKeys(ch); // Check whether the key is duplicated
if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ' '); // Empty elm
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
} else if (isDef(oldCh)) { // If only oldVnode has child nodes, delete the child nodes
removeVnodes(oldCh, 0, oldCh.length - 1);
} else if (isDef(oldVnode.text)) {
nodeOps.setTextContent(elm, ' '); // Empty elm}}else if(oldVnode.text ! == vnode.text) {// If both vNode and oldVnode have the property text and are not equal, then assign vnode.text to ELMnodeOps.setTextContent(elm, vnode.text); }}Copy the codeUpdateChildren function
The updateChildren function, the heart of diff, compares and finds child differences between the old and new virtual nodes in order to minimize updates.
The old and new child nodes are summarized
The oldCh and newCh arguments received by the updateChildren function represent the old and new child nodes, respectively, with two head-and-tail nodes and two head-and-tail node indexes:
-
node
- oldStartVnode— The start node of the old child node
- oldEndVnode— End node of the old child node
- newStartVnode— The start node of the new child node
- newEndVnode— End node of the new child node
-
Node index
- OldStartIdx – The start node index of the old child node
- OldEndIdx – End node index of the old child node
- NewStartIdx – The start node index of the new child node
- NewEndIdx – The end node index of the new child node
These variables combine into four ways of comparison. If none of the four methods match, but the node sets a key, then the comparison is performed by key. In the process of comparison, these variables gradually move towards the middle. When oldStartIdx > oldEndIdx or newStartIdx > newEndIdx, it indicates that at least one of oldCh and newCh has completed traversal, and the comparison ends.
Method of comparing old and new child nodes
- OldStartVnode compares with newStartVnode.
- OldEndVnode is compared with newEndVnode.
- OldStartVnode compares with newEndVnode.
- OldEndVnode compares with newStartVnode.
- None of the above 4 comparisons match, if set
key, usekeyCompare.
function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
let oldStartIdx = 0; // Start node index of the old node
let newStartIdx = 0; // The start node index of the new child node
let oldEndIdx = oldCh.length - 1; // The end node index of the old child node
let oldStartVnode = oldCh[0]; // The start node of the old child node
let oldEndVnode = oldCh[oldEndIdx]; // End node of the old child node
let newEndIdx = newCh.length - 1; // The end node index of the new child node
let newStartVnode = newCh[0]; // The start node of the new child node
let newEndVnode = newCh[newEndIdx]; // The end node of the new child node
let oldKeyToIdx, idxInOld, vnodeToMove, refElm;
// removeOnly is a special flag when only
is used.
// To ensure that the elements removed during the exit transformation remain in the correct relative position
constcanMove = ! removeOnly; checkDuplicateKeys(newCh);// Check whether the key value is duplicated
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
// oldStartVnode moves to the right
oldStartVnode = oldCh[++oldStartIdx];
} else if (isUndef(oldEndVnode)) {
OldEndVnode moves to the left
oldEndVnode = oldCh[--oldEndIdx];
} else if (sameVnode(oldStartVnode, newStartVnode)) {
// oldStartVnode and newStartVnode are the same node
patchVnode(
oldStartVnode,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
);
OldStartVnode and newStartVnode move to the right
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
} else if (sameVnode(oldEndVnode, newEndVnode)) {
// oldEndVnode and newEndVnode are the same node
patchVnode(
oldEndVnode,
newEndVnode,
insertedVnodeQueue,
newCh,
newEndIdx
);
OldEndVnode and newEndVnode move to the left
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldStartVnode, newEndVnode)) {
// oldStartVnode and newEndVnode are the same node
patchVnode(
oldStartVnode,
newEndVnode,
insertedVnodeQueue,
newCh,
newEndIdx
);
canMove &&
// Insert elements
nodeOps.insertBefore(
parentElm,
oldStartVnode.elm,
nodeOps.nextSibling(oldEndVnode.elm)
);
OldStartVnode moves to the right and newEndVnode moves to the left
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldEndVnode, newStartVnode)) {
// oldEndVnode and newStartVnode are the same node
patchVnode(
oldEndVnode,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
);
canMove &&
// Insert elements
nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
OldEndVnode moves to the left and newStartVnode moves to the right
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
} else { // Fifth type of comparison: compare by key
if (isUndef(oldKeyToIdx)) {
// Create an object with the old child's key and index as its key and value and return it
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
}
// Get the current old child node index
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
// Find the element of the same node as oldCh and newStartVnode, and return its index
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
// Check whether idxInOld exists
if (isUndef(idxInOld)) {
// Create a node
createElm(
newStartVnode,
insertedVnodeQueue,
parentElm,
oldStartVnode.elm,
false,
newCh,
newStartIdx
);
} else {
// Fetch the old child node that you currently want to compare
vnodeToMove = oldCh[idxInOld];
// Whether the nodes are the same
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(
vnodeToMove,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
);
// After updating the comparison, exclude the current old child node that is set to undefined, do not compare it.
oldCh[idxInOld] = undefined;
canMove &&
// Insert elements
nodeOps.insertBefore(
parentElm,
vnodeToMove.elm,
oldStartVnode.elm
);
} else {
// Same key, but different element. As a new element.
createElm(
newStartVnode,
insertedVnodeQueue,
parentElm,
oldStartVnode.elm,
false, newCh, newStartIdx ); }}// newStartVnode moves to the rightnewStartVnode = newCh[++newStartIdx]; }}// After exiting the judgment loop, either the new or the old node array has been searched, and there are two cases to deal with:
OldStartIdx > oldEndIdx; oldStartIdx > oldEndIdx;
// newStartIdx > newEndIdx indicates that there are remaining nodes in the old node array and need to be deleted.
if (oldStartIdx > oldEndIdx) {
refElm = isUndef(newCh[newEndIdx + 1])?null : newCh[newEndIdx + 1].elm;
addVnodes(
parentElm,
refElm,
newCh,
newStartIdx,
newEndIdx,
insertedVnodeQueue
);
} else if(newStartIdx > newEndIdx) { removeVnodes(oldCh, oldStartIdx, oldEndIdx); }}Copy the codeBy parsing
To better understand the Update Hildren code logic (the diff process), I’ll take a look at it in combination with graphics.
The first way to compare
OldStartVnode and newStartVnode are compared:
-
Run the sameVnode command to check whether the nodes are the same.
-
If the node is the same, execute patchVnode to find out the difference between the two nodes. If there is difference, update the view; if there is no difference, do nothing. In the real DOM of this example, the text content A is updated to A.
-
OldStartVnode and newStartVnode move to the right.
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
Copy the code
The second way of comparison
OldEndVnode and newEndVnode are compared:
-
Run the sameVnode command to check whether the nodes are the same.
-
If the node is the same, execute patchVnode to find out the difference between the two nodes. If there is difference, update the view; if there is no difference, do nothing. In the real DOM of this example, the text content D is updated to D.
-
OldEndVnode and newEndVnode move to the left
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
Copy the code
The third way of comparison
OldStartVnode compares with newEndVnode:
-
Run the sameVnode command to check whether the nodes are the same.
-
If the node is the same, execute patchVnode to find out the difference between the two nodes. If there is difference, update the view; if there is no difference, do nothing. In the real DOM of this example, the text content A is updated to D.
-
The real DOM corresponding to oldStartVnode is moved behind the real DOM corresponding to oldEndVnode.
// Insert elements
nodeOps.insertBefore(
parentElm,
oldStartVnode.elm,
nodeOps.nextSibling(oldEndVnode.elm)
);
Copy the code- OldStartVnode moves to the right and newEndVnode moves to the left.
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
Copy the code
The fourth way of comparison
OldEndVnode compares with newStartVnode:
-
Run the sameVnode command to check whether the nodes are the same.
-
If the node is the same, execute patchVnode to find out the difference between the two nodes. If there is difference, update the view; if there is no difference, do nothing. In the real DOM of this example, the text content D is updated to A.
-
The real DOM corresponding to oldEndVnode is moved before the real DOM corresponding to oldStartVnode.
// Insert elements
nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
Copy the code- OldEndVnode moves to the left and newStartVnode moves to the right.
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
Copy the code
Fifth way of comparison
If none of the four comparisons match, but a key is set, the comparison is performed by key. For an overview of the process, I recommend comparing keys with the code in Update Dren.
General idea:
Start by finding the index of the node in oldCh (old child node array) that is the same as newStartVnode (the start node of the new child node). If not, compare newStartVnode one by one with the nodes in oldCh to find the index of the same node. Finally, determine whether to compare nodes or create new nodes based on whether the index exists.
Processing process:
- The index (idxInOld) does not exist
createElmCreate a new node. - If the index (idxInOld) exists, extract the node (vnodeToMove) from oldCh for comparison.
- perform
sameVnodeCheck whether the nodes are the same. - If yes, run the command
patchVnodeFind the differences between the two. If there are differences, update the view. If there are no differences, do nothing. Then, the real DOM corresponding to this node is moved before the real DOM corresponding to oldStartVnode. - Not the same node (the same key, but a different element, is considered a new element)
createElmCreate a new node.
- perform
- NewStartVnode moves to the right
The above process is generally divided into two cases: identical nodes and no identical nodes (call createElm). Note that the solid tip indicates that the same node was found, and the dotted tip indicates that the same node was not found.
- A diagram with the same nodes
- There are no diagrams of the same nodes
Processing after exiting the loop
Code display:
if (oldStartIdx > oldEndIdx) {
refElm = isUndef(newCh[newEndIdx + 1])?null : newCh[newEndIdx + 1].elm;
addVnodes(
parentElm,
refElm,
newCh,
newStartIdx,
newEndIdx,
insertedVnodeQueue
);
} else if (newStartIdx > newEndIdx) {
removeVnodes(oldCh, oldStartIdx, oldEndIdx);
}
Copy the codeExiting the loop means that at least one of the new and old child arrays has been searched. As you can see from the code, there are two processing cases:
oldStartIdx > oldEndIdxThere are more nodes in newCh than in oldCh, that is, there are more nodes in newCh and these nodes need to be added. It can be summed up in one sentence:If oldCh does not have a child node, newCh does.
The new nodes are added by calling the addVnodes function. Instead, it calls createElm to create the node element, and then inserts the node element into place via insert.
// Some code is omitted for the sake of understanding the code logic
function createElm(
vnode, // Virtual node object
insertedVnodeQueue, // Stores the queue of inserted VNodes
parentElm, // vnode.elm parent element
refElm, // The element immediately after vnode.elm
nested,
ownerArray,
index
) {
if (isDef(vnode.elm) && isDef(ownerArray)) {
// This vnode was used in the previous rendering!
// It is now used as a new node, and when it is used to insert a reference node, the elm overwriting it causes a potential patch error.
// Instead, we clone nodes on demand before creating their associated DOM elements.
vnode = ownerArray[index] = cloneVNode(vnode);
}
const data = vnode.data; // Get element attributes
const children = vnode.children; // Get the child element
const tag = vnode.tag; // Get the label
// Element node
if (isDef(tag)) {
// Create the element
vnode.elm = nodeOps.createElement(tag, vnode);
// Create a child element
createChildren(vnode, children, insertedVnodeQueue);
if (isDef(data)) {
// Handle various attributes on the element
invokeCreateHooks(vnode, insertedVnodeQueue);
}
// Insert elements
insert(parentElm, vnode.elm, refElm);
} else {
// Plain text nodevnode.elm = nodeOps.createTextNode(vnode.text); insert(parentElm, vnode.elm, refElm); }}Copy the code// Some code is omitted for the sake of understanding the code logic
function insert(parent, elm, ref) {
// There is a parent
if (isDef(parent)) {
// Elms exist after elm (have sibling elms)
if (isDef(ref)) {
Elm and ref are siblings of the same element.
if (nodeOps.parentNode(ref) === parent) {
// Insert elm before refnodeOps.insertBefore(parent, elm, ref); }}else {
// if there is no element after elm, insert elm into parent node
// End of the element list (childNodes[] array)nodeOps.appendChild(parent, elm); }}}Copy the codeLocation diagram of the new element node:
- There is no element node after the new element node
- There is an element node after the new element node
newStartIdx > newEndIdxOldCh has more nodes than newCh. OldCh has more nodes than newCh. OldCh has more nodes than newCh. It can be summed up in one sentence:Delete child nodes that are not present in newCh but are present in oldCh.
Nodes are removed by calling the removeVnodes function.
function removeVnodes(vnodes, startIdx, endIdx) {
for (; startIdx <= endIdx; ++startIdx) {
const ch = vnodes[startIdx];
if (isDef(ch)) { // Check whether ch existsremoveNode(ch.elm); }}}function removeNode(el) {
const parent = nodeOps.parentNode(el);
if (isDef(parent)) { // Whether parent exists
nodeOps.removeChild(parent, el); / / delete}}Copy the codeSchematic of removing element nodes:
The end of the
In the process of reading, if students find something wrong, please feel free to comment. Of course, if you feel that there is a harvest, please also for me a thumbs-up 👍, thank you!