Vnode and Diff algorithms in Snabbdom are the most common algorithms in Snabbdom
First, some necessary conceptual explanations
What is the virtual DOM
The most popular front-end frameworks are VUE and React. In the process of learning these two frameworks, there is always a topic that cannot be avoided: VNode, also known as the virtual DOM. What is the virtual DOM? To quote vUE’s official explanation:
A copy of the Dom called Virtual Dom is generated in JavaScript.
That is, the virtual DOM is just a normal JS object. As we all know, it costs a lot to add, delete, change and check the DOM frequently. Since the virtual DOM is only a JS object, we can use the way of manipulating the object instead of manipulating the DOM, and finally change the DOM once, so that to some extent, we can make our UI update more efficient.
2. What is diff algorithm
Since the ultimate task of the virtual DOM is to modify the DOM with the calculated results, how to update the DOM? This requires the diff algorithm to give the final answer.
Diff algorithm is a calculation algorithm used to calculate the differences between old and new DOM.
3. What is Snabbdom
Snabbdom is a virtual DOM library focused on providing a simple, modular experience with powerful functionality and performance.
Probably many people have not heard of this library, in fact, vUE virtual DOM this part is borrowed from Snabbdom, but, it is more simple and pure than VUE, so learning Snabbdom can also help us understand vUE virtual DOM related knowledge.
Second, Snabbdom diff algorithm source code analysis
1. Use of Snabbdom
Let’s look at a simple use of Snabbdom
import {
init,
classModule,
propsModule,
styleModule,
eventListenersModule,
h,
} from "snabbdom";
const patch = init([
// Init patch function with chosen modules
classModule, // makes it easy to toggle classes
propsModule, // for setting properties on DOM elements
styleModule, // handles styling on elements with support for animations
eventListenersModule, // attaches event listeners
]);
// Create a vnode
var vnode = h('div#container.two.classes', {on: {click: someFn}}, [
h('span', {style: {fontWeight: 'bold'}}, 'This is just plain text.'),
' and this is just normal text',
h('a', {props: {href: '/foo'}}, 'Here's a link! ')]);// Select the container
var container = document.getElementById('container');
// Patch the vnode into the container
patch(container, vnode);
// Create a new vnode
var newVnode = h('div#container.two.classes', {on: {click: anotherEventHandler}}, [
h('span', {style: {fontWeight: 'normal'.fontStyle: 'italic'}}, 'Now italic text'),
' and this is still just normal text',
h('a', {props: {href: '/bar'}}, 'Here's a link! ')]);// Replace the old DOM with the new DOM
patch(vnode, newVnode);
Copy the codeThe above demo shows the process: first create a vnode, patch it into the selected container, then create a new vnode, and replace the new vNode with the old one. It should be noted that the first parameter of patch method can be a vNode type or an Element type. The processing of these two parameter types will be described below.
In fact, the above initialization of the container DOM and the replacement of the old and new DOM in the process of using vUE, we also used a lot, but VUE solved the tedious calculation process for us.
2. Vnode generation process
First, let’s take a look at the vNode generation process, which is the following piece:
var vnode = h('div#container.two.classes', {on: {click: someFn}}, [
h('span', {style: {fontWeight: 'bold'}}, 'This is the bold type'),
' and this is just normal text',
h('a', {props: {href: '/foo'}}, 'Here's a link! ')]);Copy the codeThe core point above is the h function, which takes three arguments: the first is a label, the second is an attribute, and the third is a child node, which can also be the return value of an H function.
H function attached below the source:
export function h(sel: any, b? : any, c? : any) :VNode {
let data: VNodeData = {};
let children: any;
let text: any;
let i: number;
if(c ! = =undefined) {
if(b ! = =null) {
data = b;
}
if (is.array(c)) {
children = c;
} else if (is.primitive(c)) {
text = c.toString();
} else if(c && c.sel) { children = [c]; }}else if(b ! = =undefined&& b ! = =null) {
// c is undefined, and b is of the children type
if (is.array(b)) {
children = b;
} else if (is.primitive(b)) {
text = b.toString();
} else if (b && b.sel) {
children = [b];
} else{ data = b; }}if(children ! = =undefined) {
for (i = 0; i < children.length; ++i) {
// Children may be the return value of an h function or a text text
if (is.primitive(children[i]))
children[i] = vnode(
undefined.undefined.undefined,
children[i],
undefined); }}// Handle SVG tags
if (
sel[0= = ="s" &&
sel[1= = ="v" &&
sel[2= = ="g" &&
(sel.length === 3 || sel[3= = ="." || sel[3= = ="#")
) {
addNS(data, children, sel);
}
return vnode(sel, data, children, text, undefined);
}
Copy the codeThe above code first does some function passing, which allows for more flexibility in passing parameters. Second, call the vNode method to generate the child node vNode and its own VNode, and then take a look at the vnode function implementation logic.
export function vnode(
sel: string | undefined,
data: any | undefined,
children: Array<VNode | string> | undefined,
text: string | undefined,
elm: Element | Text | undefined
) :VNode {
const key = data === undefined ? undefined : data.key;
return { sel, data, children, text, elm, key };
}
Copy the codeThe vNode function implementation function is very simple, is to return a JS object, so essentially a Vnode is a js object of the following structure.
{
sel: string | undefined;
data: any | undefined;
children: Array<VNode | string> | undefined.text: string | undefined.elm: Element | Text | undefined.key: string | undefined
}
Copy the codeEach child can also be a VNode, thus assembling a VNode tree.
3. Patch process
Now that we know about the generation process of vNode, we are going to patch the vnode into the container, which is the following two pieces of code.
patch(container, vnode); // Patch the vnode into the container
Copy the codeand
patch(vnode, newVnode); // Replace the old DOM with the new DOM
Copy the codeThe patch function is actually the return value of the init method, so find the source of init:
export function init(modules: Array<Partial<Module>>, domApi? : DOMAPI) {
// DOM manipulation API
constapi: DOMAPI = domApi ! = =undefined ? domApi : htmlDomApi;
function emptyNodeAt() {}
function createRmCb() {}
// Create a DOM tree based on vNode
function createElm() {}
function addVnodes() {}
function invokeDestroyHook() {}
function removeVnodes() {}
function updateChildren() {}
function patchVnode() {}
return function patch(oldVnode: VNode | Element, vnode: VNode) :VNode {
let elm: Node, parent: Node;
// If it is not vNode (when patch is first called),
// The Element type creates an empty object
// The elm value of the empty object is equal to oldVnode
if(! isVnode(oldVnode)) { oldVnode = emptyNodeAt(oldVnode); }// If sameVnode is used
if (sameVnode(oldVnode, vnode)) {
patchVnode(oldVnode, vnode, insertedVnodeQueue);
} else{ elm = oldVnode.elm! ; parent = api.parentNode(elm)as Node;
createElm(vnode);
if(parent ! = =null) { api.insertBefore(parent, vnode.elm! , api.nextSibling(elm)); removeVnodes(parent, [oldVnode],0.0); }}return vnode;
};
}
Copy the codeHere is some code about the timing of the hooks execution, because this article is about the diff process, so the hooks execution logic is not posted in the code, you can read the official source code. Patch (container, vnode) or patch(vnode, newVnode).
Let’s take a look at the implementation logic of patch function:
1. Vnode, the first parameter type, is checked because vnode can be a VNode instance or an Element instance.
2. To compare whether the root nodes of the new and old nodes are the same, it is logical to judge that the key, sel and data.is of the new and old nodes are the same.
function sameVnode(vnode1: VNode, vnode2: VNode) :boolean {
const isSameKey = vnode1.key === vnode2.key;
constisSameIs = vnode1.data? .is === vnode2.data? .is;const isSameSel = vnode1.sel === vnode2.sel;
return isSameSel && isSameKey && isSameIs;
}
Copy the codeSameVnode (oldVnode, vNode) returns false. Create a DOM tree by calling createElm(vNode, insertedVnodeQueue), and append the DOM tree directly to the container’s parent node, replacing the child node directly.
Finally, in order to help you understand the whole patch process, I use a graph to describe the process:
4. Diff of old and new nodes
In the implementation logic of patch function above, when sameVnode(oldVnode, vnode) returns true, patchVnode method will be executed. PatchVnode is actually used to compare the difference between old and new nodes and calculate a new node. Let’s take a look at the comparative implementation of patchVnode:
function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
constelm = (vnode.elm = oldVnode.elm)! ;const oldCh = oldVnode.children as VNode[];
const ch = vnode.children as VNode[];
// If the new and old nodes are equal, no replacement is required
if (oldVnode === vnode) return;
if (isUndef(vnode.text)) { // If the child of the new node is not of type textNode.
if (isDef(oldCh) && isDef(ch)) { // If the child type of the new node and the child type of the old node are both children
if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue); }else if (isDef(ch)) { // If the child type of the new node is children, the type of the old node is text
if (isDef(oldVnode.text)) api.setTextContent(elm, "");
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
} else if (isDef(oldCh)) { // If the child type of the old node is children, the new node has no children
removeVnodes(elm, oldCh, 0, oldCh.length - 1);
} else if (isDef(oldVnode.text)) { // If the child type of the old node is text, the new node has no children
api.setTextContent(elm, ""); }}else if(oldVnode.text ! == vnode.text) {// If the child of the new node is of type text.
if (isDef(oldCh)) {
removeVnodes(elm, oldCh, 0, oldCh.length - 1);
}
api.setTextContent(elm, vnode.text!);
}
}
Copy the codeHere is the first to determine whether oldVnode and Vnode are equal, if equal, then there is no need to continue the comparison; If not, the update life cycle of the new node is performed first. Since the root nodes are compared using the sameVnode method, Snabbdom assumes that the root nodes of vNode and oldVnode are equal, so there is no need to update the root node. So the next step is to directly deal with the update of the child node. Here, in order to facilitate your understanding, I first put a flow chart of the comparison of the child node.
Above, we calculate the values of text and children according to the node type when generating vNodes. Therefore, the text and children attributes of a VNode cannot have values at the same time. Therefore, according to the flowchart, the comparison process of child nodes is as follows:
1. If the children of the new node is empty, the text of the new node is directly compared with the text of the old node (empty if it does not exist).
2. Children of the new node are not empty, and children of the old node are empty. Replace the old node with the new node directly.
3. The children of the new node and the children of the old node are not empty. Run updateChildren().
5. Depth diff of child nodes
When children of the new node and children of the old node are not empty, execute updateChildren(ELM, oldCh, CH, insertedVnodeQueue) for depth comparison.
function updateChildren(parentElm: Node, oldCh: VNode[], newCh: VNode[], insertedVnodeQueue: VNodeQueue) {
let oldStartIdx = 0;
let newStartIdx = 0;
let oldEndIdx = oldCh.length - 1;
let oldStartVnode = oldCh[0];
let oldEndVnode = oldCh[oldEndIdx];
let newEndIdx = newCh.length - 1;
let newStartVnode = newCh[0];
let newEndVnode = newCh[newEndIdx];
let oldKeyToIdx: KeyToIndexMap | undefined;
let idxInOld: number;
let elmToMove: VNode;
let before: any;
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVnode == null) {
// The start position of the old node is null
oldStartVnode = oldCh[++oldStartIdx];
} else if (oldEndVnode == null) {
// The end position of the old node is null
oldEndVnode = oldCh[--oldEndIdx];
} else if (newStartVnode == null) {
// The start position of the new node is null
newStartVnode = newCh[++newStartIdx];
} else if (newEndVnode == null) {
// The end position of the new node is null
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldStartVnode, newStartVnode)) {
// The old node start position and the new node start position diff
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
} else if (sameVnode(oldEndVnode, newEndVnode)) {
// End position of the old node and end position of the new node diff
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldStartVnode, newEndVnode)) {
// The end of the old node and the start of the new node diffpatchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue); api.insertBefore( parentElm, oldStartVnode.elm! , api.nextSibling(oldEndVnode.elm!) ); oldStartVnode = oldCh[++oldStartIdx]; newEndVnode = newCh[--newEndIdx]; }else if (sameVnode(oldEndVnode, newStartVnode)) {
// Start position of old node and end position of new node diffpatchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue); api.insertBefore(parentElm, oldEndVnode.elm! , oldStartVnode.elm!) ; oldEndVnode = oldCh[--oldEndIdx]; newStartVnode = newCh[++newStartIdx]; }else {
if (oldKeyToIdx === undefined) {
// Convert the old node to a map structure
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
}
// Find the starting location of the new node in the map
idxInOld = oldKeyToIdx[newStartVnode.key as string];
if (isUndef(idxInOld)) {
// If not, the new node starts at the new elementapi.insertBefore( parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm! ) ; }else { // If found, the selectors of the two nodes are compared for equality
elmToMove = oldCh[idxInOld];
if(elmToMove.sel ! == newStartVnode.sel) {// If not, the new node starts at the new elementapi.insertBefore( parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm! ) ; }else { // If it is equal, it is considered the same element
patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
oldCh[idxInOld] = undefined asany; api.insertBefore(parentElm, elmToMove.elm! , oldStartVnode.elm!) ; }}// The new node starts rightnewStartVnode = newCh[++newStartIdx]; }}if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
// If you are done
if (oldStartIdx > oldEndIdx) {
// If there are any residual new nodes that do not participate in the diff, then all appends to the parent element
before = newCh[newEndIdx + 1] = =null ? null : newCh[newEndIdx + 1].elm;
addVnodes(
parentElm,
before,
newCh,
newStartIdx,
newEndIdx,
insertedVnodeQueue
);
} else {
// If there are any residual old nodes that do not participate in diff, remove them allremoveVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx); }}}Copy the codeThe diff of the child node should be the most complex link in the whole diff process, so as usual, first figure:
Combine the code and flow chart to see:
1. Check whether the start and end positions of the old and new nodes are null. If null, the position of the corresponding node is moved left (start position) or right (end position).
2. Then compare the start position of the new node with the start position of the old node, the end position of the new node with the end position of the old node, the end position of the new node with the start position of the old node, and the start position of the new node with the end position of the old node. The comparison logic is still the sameVnode function mentioned above. If matched, the patchVnode will be entered again, and the corresponding positions will be moved left (start position) or right (end position) respectively. If no match is found, the VNode where the new node started is searched among all the old child nodes.
3. When the cyclic condition oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx is not met, check whether any residual child nodes in the new child nodes do not participate in the diff process, if so, insert all residual new child nodes; Check the old child nodes to see if there are any residual child nodes that did not participate in the diff process. If so, delete all residual laozi nodes.
Third, summary
Since this article only discusses the vNode generation and diff process of Snabbdom, there are many other places not deep dig, but I suggest that you can have a look at the source of Snabbdom, there are a lot of very good design ideas worth us to learn.
Four, reference
- Snabbdom official repository
Recommended reading
How to use SCSS to achieve one key skin change
Why is index not recommended as key in Vue
Brief analysis of Web screen recording technology scheme and implementation
Open source works
- Political cloud front-end tabloid
Open source address www.zoo.team/openweekly/ (wechat communication group on the official website of tabloid)
- Item selection SKU plug-in
Open source addressGithub.com/zcy-inc/sku…
, recruiting
ZooTeam, a young passionate and creative front-end team, belongs to the PRODUCT R&D department of ZooTeam, based in picturesque Hangzhou. The team now has more than 60 front-end partners, with an average age of 27, and nearly 40% of them are full-stack engineers, no problem in the youth storm group. The members consist of “old” soldiers from Alibaba and NetEase, as well as fresh graduates from Zhejiang University, University of Science and Technology of China, Hangzhou Electric And other universities. In addition to daily business docking, the team also carried out technical exploration and practice in material system, engineering platform, building platform, performance experience, cloud application, data analysis and visualization, promoted and implemented a series of internal technical products, and continued to explore the new boundary of front-end technology system.
If you want to change what’s been bothering you, you want to start bothering you. If you want to change, you’ve been told you need more ideas, but you don’t have a solution. If you want change, you have the power to make it happen, but you don’t need it. If you want to change what you want to accomplish, you need a team to support you, but you don’t have the position to lead people. If you want to change the pace, it will be “5 years and 3 years of experience”; If you want to change the original savvy is good, but there is always a layer of fuzzy window… If you believe in the power of believing, believing that ordinary people can achieve extraordinary things, believing that you can meet a better version of yourself. If you want to be a part of the process of growing a front end team with deep business understanding, sound technology systems, technology value creation, and impact spillover as your business takes off, I think we should talk. Any time, waiting for you to write something and send it to [email protected]
