With the rise of React, Virtual DOM became increasingly popular, with various implementations and UI libraries introduced. Snabbdom is a concise implementation of the Virtual DOM. But before we dive into the SNabbDOM, let’s talk about the Virtual DOM.
What is the Virtual DOM?
Before talking about the Virtual DOM, it’s important to understand: What is the DOM?
DOM, or Document Object Model, is a way to represent structured documents through objects. DOM is cross-platform and language-neutral (for example, IT can be used to represent and manipulate BOTH HTML and XML). The browser handles the implementation details of the DOM, and we can then interact with it through JavaScript and CSS.
The main problem with DOM is that it is not optimized for creating dynamic UIs.
The DOM API used to be cumbersome to use directly, but libraries like jQuery have been developed to simplify DOM manipulation. But this does not solve the performance problem of a large number of DOM operations. Dynamic DOM creation/destruction is very common in large page/single-page applications (especially now that front-end rendering is common), and we could certainly use trick to optimize performance, but it’s just too painful.
And Virtual DOM is a kind of exploration to solve the problem.
The Virtual DOM is built on top of the DOM and is a layer of DOM-based abstraction that can be understood as a more lightweight pure JavaScript object (tree) describing the DOM (tree).
Working with JavaScript objects is certainly faster than working with the DOM because you don’t have to update the screen. We can make changes to the Virtual DOM at will, then find the changes and update them to the DOM. But to be efficient, the following issues need to be addressed:
- Efficient diff algorithm, namely, the comparison of two Virtual DOM;
- Update only DOM nodes that need to be updated;
- Data change detection, Batch DOM read and write operations, and so on.
With these questions in mind, let’s get down to business: using snabbDOM as an example, how to implement a Virtual DOM library.
Snabbdom overview
The ES6 adaptation of SNabbDOM can be viewed in Codes/SnabbDOM, with minor changes such as ID /className handling, but the core flow is exactly the same.
Code structure:
SRC ├─ Domapi.js # DOM API, mainly for various DOM operations wrapper, quick browse. ├─ export.js # export determines which interface to expose to the caller, negligible. ├─ H.JS # 'h()' help function, very simple. ├─ index.js # core code, Virtual DOM diff implementation, build DOM from Virtual DOM and so on. ├─ Modules # For attribute handling. │ ├── ├─ class.js │ ├─ class.js │ ├─ class.js │ ├─ class.js # ├ ─ └─ vnode.js # Vnode definition and some related functions.Copy the codeSnabbdom is a lightweight Virtual DOM implementation with less code, modularity and clear structure. This is the main reason I chose SnabbDOM as my source code reading target.
The main interfaces of snabbDOM are:
h(type, data, children), returns the Virtual DOM tree.patch(oldVnode, newVnode)To compare and update the old and new Virtual DOM trees.
Starting with two interfaces, let’s dive into the implementation of snabbDOM.
The realization of the snabbdom
How to implement Virtual DOM? We first define the Virtual DOM, or more specifically, a Virtual DOM node: vnode.
vnode.js
Vnode is an abstraction of a DOM node, so we can easily define its form:
{type, // String, the type of the DOM node, such as 'div'/'span' data, // Object, such as props, style, etc. Children // Array, child node (child vnode)}Copy the codeCorresponding source code SRC /vnode.js:
const VNODE_TYPE = Symbol('virtual-node')
function vnode(type, key, data, children, text, elm) {
const element = {
__type: VNODE_TYPE,
type, key, data, children, text, elm
}
return element
}
function isVnode(vnode) {
return vnode && vnode.__type === VNODE_TYPE
}
function isSameVnode(oldVnode, vnode) {
return oldVnode.key === vnode.key && oldVnode.type === vnode.type
}Copy the codeThe code can be understood almost at a glance, but there are three things to note:
-
The VNode is constructed with a built-in __type with a value of symbol. Verify vNodes using the uniqueness of symbol.
-
Children /text of vnode either cannot coexist. So why not think of text as a children element? The main reason for this is that text nodes are handled differently from other types of nodes.
- Text indicates that the vnode is actually a VTextNode, but snabbdom does not distinguish between vnodes.
elmIt is used to save DOM nodes corresponding to vnodes.
-
IsSameVnode Checks whether the two VNodes are the same. The same here refers to whether the next vnode is converted from the previous vnode and requires the same type and key:
- Type is different, for example
divChange to thep, then the DOM corresponding to vnode must be replaced completely; - The key is different, that is, it is not the previous vnode changes, is different.
- Type is different, for example
h.js
With the format of vNodes defined, we can combine vNodes to create a Virtual DOM tree. The h function is there to help us generate the virtual DOM tree.
Source code SRC /h.js:
function h(type, config, ... Children) {const props = {} return vnode(type, key, props, flattenArray(children).map(c => { return isPrimitive(c) ? vnode(undefined, undefined, undefined, undefined, c) : c }) ) }Copy the codeNote that the children argument can be an Array, a vnode, or even a string. If it is a string, it is automatically converted to a Vnode (whose text is the string).
In most cases, or for a better development experience, we should support JSX or similar syntax and then convert it into h function calls via the Babel plug-in. Since the topic of this article is how to implement the Virtual DOM, it will not be expanded here.
index.js
Now get to the heart of snabbDOM and talk about two features that Virtual DOM must implement:
- How do I create a DOM tree from a VNode? That is, Virtual DOM to real DOM.
- How to compare oldVnode and newVnode, and implement DOM tree update? The DIff algorithm should be as efficient as possible, and updates should reuse the existing DOM as much as possible (minimal updates).
To start with, we’ll show you how to generate a DOM from a vnode:
function createElm(vnode, InsertedVnodeQueue) {let data = vnode.data let I // omit hook call let children = vnode.children let type = vnode.type // Comment if (type === 'comment') {if (vnode.text == null) {vnode.text = ''} vnode.elm = Api.createcomment (vnode.text)} else if (type) {const elm = vnode.elm = data.ns? Api.createelementns (data.ns, type) : api.createElement(type) // Call create hook for (let I = 0; i < cbs.create.length; ++ I) CBS. Create [I](emptyNode, vnode) // Handle children and text respectively. Vnode children and text do not/should exist at the same time. If (isArray(children)) {// Recursive children ensures that each vnode in the vNode tree has its own dom; // Construct the DOM tree corresponding to the vNode tree. children.forEach(ch => { ch && api.appendChild(elm, createElm(ch, insertedVnodeQueue)) }) } else if (isPrimitive(vnode.text)) { api.appendChild(elm, Api.createtextnode (vnode.text))} // Call create hook; Populate the insertedVnodeQueue for insert hooks. i = vnode.data.hook if (i) { i.create && i.create(emptyNode, Vnode) i.queue &&insertedvNodequeue.push (vnode)}} // process text (text type is empty) else {vnode.elm = api.createTextNode(vnode.text) } return vnode.elm }Copy the codeThe code above is not complicated, nor should it be, because the Virtual DOM is an abstraction of the DOM, a description, and generating the DOM from the Virtual DOM should be straightforward: Generate the corresponding DOM based on type, and set the various properties defined in data to the DOM.
Of course, there is some complexity hidden here, such as style handling, such as edge case handling and so on.
Next, how to diff two Virtual DOM trees and perform minimal updates.
In general, the time complexity of finding the smallest change between two arbitrary trees is O(n^3), which is unacceptable. Fortunately, we can make the following assumptions about the Virtual DOM tree:
If oldVnode and VNode are different (e.g., type changes from div to P, or key changes), meaning that the entire Vnode is replaced (because we don’t normally move vNodes across layers), There is no need to compare vNodes’ children. Based on this assumption, we can decompose the tree by hierarchy, which greatly simplifies the complexity to near O(n) :
In addition, for children (arrays) comparisons, because the same layer is likely to move, sequential comparisons will not maximize reuse of the existing DOM. So we track this order by adding a key to each vNode.
Principle analysis, on the code:
function patchVnode(oldVnode, vnode, insertedVnodeQueue) {
// 因为 vnode 和 oldVnode 是相同的 vnode，所以我们可以复用 oldVnode.elm。
const elm = vnode.elm = oldVnode.elm
let oldCh = oldVnode.children
let ch = vnode.children
// 如果 oldVnode 和 vnode 是完全相同，说明无需更新，直接返回。
if (oldVnode === vnode) return
// 调用 update hook
if (vnode.data) {
for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
}
// 如果 vnode.text 是 undefined
if (vnode.text === undefined) {
// 比较 old children 和 new children，并更新
if (oldCh && ch) {
if (oldCh !== ch) {
// 核心逻辑（最复杂的地方）：怎么比较新旧 children 并更新，对应上面
// 的数组比较
updateChildren(elm, oldCh, ch, insertedVnodeQueue)
}
}
// 添加新 children
else if (ch) {
// 首先删除原来的 text
if (oldVnode.text) api.setTextContent(elm, '')
// 然后添加新 dom（对 ch 中每个 vnode 递归创建 dom 并插入到 elm）
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
}
// 相反地，如果原来有 children 而现在没有，那么我们要删除 children。
else if (oldCh) {
removeVnodes(elm, oldCh, 0, oldCh.length - 1);
}
// 最后，如果 oldVnode 有 text，删除。
else if (oldVnode.text) {
api.setTextContent(elm, '');
}
}
// 否则 （vnode 有 text），只要 text 不等，更新 dom 的 text。
else if (oldVnode.text !== vnode.text) {
api.setTextContent(elm, vnode.text)
}
}
function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue) {
let oldStartIdx = 0, 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
let idxInOld
let elmToMove
let before
// 遍历 oldCh 和 newCh 来比较和更新
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 1⃣️ 首先检查 4 种情况，保证 oldStart/oldEnd/newStart/newEnd
// 这 4 个 vnode 非空，左侧的 vnode 为空就右移下标，右侧的 vnode 为空就左移 下标。
if (oldStartVnode == null) {
oldStartVnode = oldCh[++oldStartIdx]
} else if (oldEndVnode == null) {
oldEndVnode = oldCh[--oldEndIdx]
} else if (newStartVnode == null) {
newStartVnode = newCh[++newStartIdx]
} else if (newEndVnode == null) {
newEndVnode = newCh[--newEndIdx]
}
/**
* 2⃣️ 然后 oldStartVnode/oldEndVnode/newStartVnode/newEndVnode 两两比较，
* 对有相同 vnode 的 4 种情况执行对应的 patch 逻辑。
* - 如果同 start 或同 end 的两个 vnode 是相同的（情况 1 和 2），
* 说明不用移动实际 dom，直接更新 dom 属性／children 即可；
* - 如果 start 和 end 两个 vnode 相同（情况 3 和 4），
* 那说明发生了 vnode 的移动，同理我们也要移动 dom。
*/
// 1. 如果 oldStartVnode 和 newStartVnode 相同（key相同），执行 patch
else if (isSameVnode(oldStartVnode, newStartVnode)) {
// 不需要移动 dom
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
}
// 2. 如果 oldEndVnode 和 newEndVnode 相同，执行 patch
else if (isSameVnode(oldEndVnode, newEndVnode)) {
// 不需要移动 dom
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
}
// 3. 如果 oldStartVnode 和 newEndVnode 相同，执行 patch
else if (isSameVnode(oldStartVnode, newEndVnode)) {
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
// 把获得更新后的 (oldStartVnode/newEndVnode) 的 dom 右移，移动到
// oldEndVnode 对应的 dom 的右边。为什么这么右移？
// （1）oldStartVnode 和 newEndVnode 相同，显然是 vnode 右移了。
// （2）若 while 循环刚开始，那移到 oldEndVnode.elm 右边就是最右边，是合理的；
// （3）若循环不是刚开始，因为比较过程是两头向中间，那么两头的 dom 的位置已经是
// 合理的了，移动到 oldEndVnode.elm 右边是正确的位置；
// （4）记住，oldVnode 和 vnode 是相同的才 patch，且 oldVnode 自己对应的 dom
// 总是已经存在的，vnode 的 dom 是不存在的，直接复用 oldVnode 对应的 dom。
api.insertBefore(parentElm, oldStartVnode.elm, api.nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
}
// 4. 如果 oldEndVnode 和 newStartVnode 相同，执行 patch
else if (isSameVnode(oldEndVnode, newStartVnode)) {
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
// 这里是左移更新后的 dom，原因参考上面的右移。
api.insertBefore(parentElm, oldEndVnode.elm, api.nextSibling(oldStartVnode.elm))
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
}
// 3⃣️ 最后一种情况：4 个 vnode 都不相同，那么我们就要
// 1. 从 oldCh 数组建立 key --> index 的 map。
// 2. 只处理 newStartVnode （简化逻辑，有循环我们最终还是会处理到所有 vnode），
// 以它的 key 从上面的 map 里拿到 index；
// 3. 如果 index 存在，那么说明有对应的 old vnode，patch 就好了；
// 4. 如果 index 不存在，那么说明 newStartVnode 是全新的 vnode，直接
// 创建对应的 dom 并插入。
else {
// 如果 oldKeyToIdx 不存在，创建 old children 中 vnode 的 key 到 index 的
// 映射，方便我们之后通过 key 去拿下标。
if (oldKeyToIdx === undefined) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
}
// 尝试通过 newStartVnode 的 key 去拿下标
idxInOld = oldKeyToIdx[newStartVnode.key]
// 下标不存在，说明 newStartVnode 是全新的 vnode。
if (idxInOld == null) {
// 那么为 newStartVnode 创建 dom 并插入到 oldStartVnode.elm 的前面。
api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm)
newStartVnode = newCh[++newStartIdx]
}
// 下标存在，说明 old children 中有相同 key 的 vnode，
else {
elmToMove = oldCh[idxInOld]
// 如果 type 不同，没办法，只能创建新 dom；
if (elmToMove.type !== newStartVnode.type) {
api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm)
}
// type 相同（且key相同），那么说明是相同的 vnode，执行 patch。
else {
patchVnode(elmToMove, newStartVnode, insertedVnodeQueue)
oldCh[idxInOld] = undefined
api.insertBefore(parentElm, elmToMove.elm, oldStartVnode.elm)
}
newStartVnode = newCh[++newStartIdx]
}
}
}
// 上面的循环结束后（循环条件有两个），处理可能的未处理到的 vnode。
// 如果是 new vnodes 里有未处理的（oldStartIdx > oldEndIdx
// 说明 old vnodes 先处理完毕）
if (oldStartIdx > oldEndIdx) {
before = newCh[newEndIdx+1] == null ? null : newCh[newEndIdx+1].elm
addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
}
// 相反，如果 old vnodes 有未处理的，删除 （为处理 vnodes 对应的） 多余的 dom。
else if (newStartIdx > newEndIdx) {
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
}
}Copy the codeHaving covered the core implementation of the SnabbDOM, we can see that the Virtual DOM is a little simpler than we thought.
This article is limited by space, so the code will not be posted completely. If you want to see the complete code, you can go to the official or the warehouse I rewrote with ES6.
As an aside, this is the second part of a series on Learning Notes about React.