The content of this article is about how to implement virtual DOM? (Code sample) has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.
This article reads and analyzes the source code of virtual-dom, and explains the structure of Virtual DOM and related Diff algorithms, so that readers can have a certain understanding of the entire data structure and related Diff algorithms.
We will reveal how the results of the Diff algorithm in Virtual DOM are mapped to the real DOM in the next blog.
The main content of this article is:
The structure of Virtual DOM and the Diff algorithm of Virtual DOM
Note: The implementation of this Virtual DOM is not the source code of React Virtual DOM, but Based on virtual-dom) this library. The two are similar in principle, and this library is simpler and easier to understand. Compared with this library, React has further optimized and adjusted Virtual DOM, which I will analyze in subsequent blogs.
Structure of Virtual DOM
VirtualNode
As the metadata structure of Virtual DOM, VirtualNode is located in the vnode/vnode.js file. Let's intercept a part of the declaration code to take a look at the internal structure:
function VirtualNode(tagName, properties, children, key, namespace) {
this.tagName = tagName
this.properties = properties || noProperties //props对象，Object类型
this.children = children || noChildren //子节点，Array类型
this.key = key != null ? String(key) : undefined
this.namespace = (typeof namespace === "string") ? namespace : null
...
this.count = count + descendants
this.hasWidgets = hasWidgets
this.hasThunks = hasThunks
this.hooks = hooks
this.descendantHooks = descendantHooks
}
VirtualNode.prototype.version = version //VirtualNode版本号，isVnode()检测标志
VirtualNode.prototype.type = "VirtualNode" // VirtualNode类型，isVnode()检测标志The above is the complete structure of a VirtualNode, including specific tag names, attributes, child nodes, etc.
VText
VText is a plain text node, corresponding to the plain text in HTML. Therefore, this attribute only has one field: text.
function VirtualText(text) {
this.text = String(text)
}
VirtualText.prototype.version = version
VirtualText.prototype.type = "VirtualText"VPatch
VPatch is a data structure that represents the operation records that need to be performed on Virtual DOM. It is located in the vnode/vpatch.js file. Let's take a look at the specific code inside:
// 定义了操作的常量，如Props变化，增加节点等
VirtualPatch.NONE = 0
VirtualPatch.VTEXT = 1
VirtualPatch.VNODE = 2
VirtualPatch.WIDGET = 3
VirtualPatch.PROPS = 4
VirtualPatch.ORDER = 5
VirtualPatch.INSERT = 6
VirtualPatch.REMOVE = 7
VirtualPatch.THUNK = 8
module.exports = VirtualPatch
function VirtualPatch(type, vNode, patch) {
this.type = Number(type) //操作类型
this.vNode = vNode //需要操作的节点
this.patch = patch //需要操作的内容
}
VirtualPatch.prototype.version = version
VirtualPatch.prototype.type = "VirtualPatch"The constants define the operations on the VNode node. For example: VTEXT is to add a VText node, and PROPS is to change the Props attribute of the current node.
Virtual DOM’s Diff algorithm
Now that we understand the three structures in virtual DOM, let’s take a look at the Virtual DOM’s Diff algorithm.
This Diff algorithm is the core algorithm in Virtual DOM. By inputting the initial state A (VNode) and the final state B (VNode), this algorithm can get the change steps (VPatch) from A to B. Based on the obtained series of steps, we can know which nodes need to be added and which nodes Which nodes need to be deleted and whose attributes have changed. In this Diff algorithm, it is divided into three parts:
VNode’s Diff algorithm Props’ Diff algorithm Vnode children’s Diff algorithm
Below, we will introduce these Diff algorithms one by one.
VNode’s Diff algorithm
This algorithm is a comparison algorithm for a single VNode. It is used in the scenario of comparing a single node in two trees. The specific algorithm is as follows. If you don’t want to read the source code directly, you can also turn to the following. There will be relevant code flow instructions for your reference:
function walk(a, b, patch, index) {
if (a === b) {
return
}
var apply = patch[index]
var applyClear = false
if (isThunk(a) || isThunk(b)) {
thunks(a, b, patch, index)
} else if (b == null) {
// If a is a widget we will add a remove patch for it
// Otherwise any child widgets/hooks must be destroyed.
// This prevents adding two remove patches for a widget.
if (!isWidget(a)) {
clearState(a, patch, index)
apply = patch[index]
}
apply = appendPatch(apply, new VPatch(VPatch.REMOVE, a, b))
} else if (isVNode(b)) {
if (isVNode(a)) {
if (a.tagName === b.tagName &&
a.namespace === b.namespace &&
a.key === b.key) {
var propsPatch = diffProps(a.properties, b.properties)
if (propsPatch) {
apply = appendPatch(apply,
new VPatch(VPatch.PROPS, a, propsPatch))
}
apply = diffChildren(a, b, patch, apply, index)
} else {
apply = appendPatch(apply, new VPatch(VPatch.VNODE, a, b))
applyClear = true
}
} else {
apply = appendPatch(apply, new VPatch(VPatch.VNODE, a, b))
applyClear = true
}
} else if (isVText(b)) {
if (!isVText(a)) {
apply = appendPatch(apply, new VPatch(VPatch.VTEXT, a, b))
applyClear = true
} else if (a.text !== b.text) {
apply = appendPatch(apply, new VPatch(VPatch.VTEXT, a, b))
}
} else if (isWidget(b)) {
if (!isWidget(a)) {
applyClear = true
}
apply = appendPatch(apply, new VPatch(VPatch.WIDGET, a, b))
}
if (apply) {
patch[index] = apply
}
if (applyClear) {
clearState(a, patch, index)
}
}The specific logic of the code is as follows:
If a and b are this If the two VNodes are congruent, it is considered that there is no modification and returns directly.
If one of them is a thunk, use the thunk comparison method thunks.
If a is a widget and b is empty, then the remove operation of a and its child nodes is added to the patch recursively.
If b is a VNode,
If a is also a VNode, then compare tagName, namespace, key, and if they are the same, compare the Props of the two VNodes (using the diffProps algorithm mentioned below), Compare the children of two VNodes at the same time (using the diffChildren algorithm mentioned below); if they are different, directly add the insert operation of node b to the patch, and set the mark position to true.
If a is not a VNode, directly add the insert operation of node b to the patch, and set the mark position to true.
If b is VText, check whether the type of a is VText. If not, add the VText operation to the patch and set the flag bit to true; if it is and the text content is different, add the VText operation to the patch. The operation is added to the patch.
If b is a Widget, check whether the type of a is a widget. If so, set the flag to true. Regardless of the type of a, add the Widget operation to the patch.
Check the flag bit. If the flag is true, then add the remove operation of a and its child nodes to the patch through recursion.
This is the whole process of the diff algorithm of a single VNode node. This algorithm is the entrance to the entire diff algorithm, and the comparison of two trees starts from this algorithm.
After reading the diff algorithm of a single VNode node, let’s take a look at the diffProps algorithm mentioned above.
This algorithm is a Props comparison algorithm for two compared VNode nodes. It is used when the key value and tag name are the same in both scenarios. The specific algorithm is as follows. If you don’t want to read the source code directly, you can also turn to the following. There will be relevant code flow instructions for your reference:
function diffProps(a, b) {
var diff
for (var aKey in a) {
if (!(aKey in b)) {
diff = diff || {}
diff[aKey] = undefined
}
var aValue = a[aKey]
var bValue = b[aKey]
if (aValue === bValue) {
continue
} else if (isObject(aValue) && isObject(bValue)) {
if (getPrototype(bValue) !== getPrototype(aValue)) {
diff = diff || {}
diff[aKey] = bValue
} else if (isHook(bValue)) {
diff = diff || {}
diff[aKey] = bValue
} else {
var objectDiff = diffProps(aValue, bValue)
if (objectDiff) {
diff = diff || {}
diff[aKey] = objectDiff
}
}
} else {
diff = diff || {}
diff[aKey] = bValue
}
}
for (var bKey in b) {
if (!(bKey in a)) {
diff = diff || {}
diff[bKey] = b[bKey]
}
}
return diff
}The specific logic of the code is as follows:
Traverse a objects.
b，则将此值存储下来，value赋值为undefined。b对象的值；如果b对应的value是hook的话，记录b的值。b对应的value进行记录。b对象，将所有a对象中不存在的key值对应的对象都记录下来。整个算法的大致流程如下，因为比较简单，就不画相关流程图了。如果逻辑有些绕的话，可以配合代码食用，效果更佳。
下面让我们来看下最后一个算法，就是关于两个VNode节点的children属性的diffChildren算法。这个个diff算法分为两个部分，第一部分是将变化后的结果b的children进行顺序调整的算法，保证能够快速的和a的children进行比较；第二部分就是将a的children与重新排序调整后的b的children进行比较，得到相关的patch。下面，让我们一个一个算法来看。
该算法的作用是将b节点的children数组进行调整重新排序，让a和b两个children之间的diff算法更加节约时间。具体代码如下：
function reorder(aChildren, bChildren) {
// O(M) time, O(M) memory
var bChildIndex = keyIndex(bChildren)
var bKeys = bChildIndex.keys // have "key" prop，object
var bFree = bChildIndex.free //don't have "key" prop，array
// all children of b don't have "key"
if (bFree.length === bChildren.length) {
return {
children: bChildren,
moves: null
}
}
// O(N) time, O(N) memory
var aChildIndex = keyIndex(aChildren)
var aKeys = aChildIndex.keys
var aFree = aChildIndex.free
// all children of a don't have "key"
if (aFree.length === aChildren.length) {
return {
children: bChildren,
moves: null
}
}
// O(MAX(N, M)) memory
var newChildren = []
var freeIndex = 0
var freeCount = bFree.length
var deletedItems = 0
// Iterate through a and match a node in b
// O(N) time,
for (var i = 0 ; i < aChildren.length; i++) {
var aItem = aChildren[i]
var itemIndex
if (aItem.key) {
if (bKeys.hasOwnProperty(aItem.key)) {
// Match up the old keys
itemIndex = bKeys[aItem.key]
newChildren.push(bChildren[itemIndex])
} else {
// Remove old keyed items
itemIndex = i - deletedItems++
newChildren.push(null)
}
} else {
// Match the item in a with the next free item in b
if (freeIndex < freeCount) {
itemIndex = bFree[freeIndex++]
newChildren.push(bChildren[itemIndex])
} else {
// There are no free items in b to match with
// the free items in a, so the extra free nodes
// are deleted.
itemIndex = i - deletedItems++
newChildren.push(null)
}
}
}
var lastFreeIndex = freeIndex >= bFree.length ?
bChildren.length :
bFree[freeIndex]
// Iterate through b and append any new keys
// O(M) time
for (var j = 0; j < bChildren.length; j++) {
var newItem = bChildren[j]
if (newItem.key) {
if (!aKeys.hasOwnProperty(newItem.key)) {
// Add any new keyed items
// We are adding new items to the end and then sorting them
// in place. In future we should insert new items in place.
newChildren.push(newItem)
}
} else if (j >= lastFreeIndex) {
// Add any leftover non-keyed items
newChildren.push(newItem)
}
}
var simulate = newChildren.slice()
var simulateIndex = 0
var removes = []
var inserts = []
var simulateItem
for (var k = 0; k < bChildren.length;) {
var wantedItem = bChildren[k]
simulateItem = simulate[simulateIndex]
// remove items
while (simulateItem === null && simulate.length) {
removes.push(remove(simulate, simulateIndex, null))
simulateItem = simulate[simulateIndex]
}
if (!simulateItem || simulateItem.key !== wantedItem.key) {
// if we need a key in this position...
if (wantedItem.key) {
if (simulateItem && simulateItem.key) {
// if an insert doesn't put this key in place, it needs to move
if (bKeys[simulateItem.key] !== k + 1) {
removes.push(remove(simulate, simulateIndex, simulateItem.key))
simulateItem = simulate[simulateIndex]
// if the remove didn't put the wanted item in place, we need to insert it
if (!simulateItem || simulateItem.key !== wantedItem.key) {
inserts.push({key: wantedItem.key, to: k})
}
// items are matching, so skip ahead
else {
simulateIndex++
}
}
else {
inserts.push({key: wantedItem.key, to: k})
}
}
else {
inserts.push({key: wantedItem.key, to: k})
}
k++
}
// a key in simulate has no matching wanted key, remove it
else if (simulateItem && simulateItem.key) {
removes.push(remove(simulate, simulateIndex, simulateItem.key))
}
}
else {
simulateIndex++
k++
}
}
// remove all the remaining nodes from simulate
while(simulateIndex < simulate.length) {
simulateItem = simulate[simulateIndex]
removes.push(remove(simulate, simulateIndex, simulateItem && simulateItem.key))
}
// If the only moves we have are deletes then we can just
// let the delete patch remove these items.
if (removes.length === deletedItems && !inserts.length) {
return {
children: newChildren,
moves: null
}
}
return {
children: newChildren,
moves: {
removes: removes,
inserts: inserts
}
}
}下面，我们来简单介绍下这个排序算法：
a和b中的children是否拥有key字段，如果没有，直接返回b的children数组。如果存在，初始化一个数组newChildren，遍历a的children元素。
move操作patch（即remove+insert）。move操作列表。通过上面这个排序算法，我们可以得到一个新的b的children数组。在使用这个数组来进行比较厚，我们可以将两个children数组之间比较的时间复杂度从o(n^2)转换成o(n)。具体的方法和效果我们可以看下面的DiffChildren算法。
function diffChildren(a, b, patch, apply, index) {
var aChildren = a.children
var orderedSet = reorder(aChildren, b.children)
var bChildren = orderedSet.children
var aLen = aChildren.length
var bLen = bChildren.length
var len = aLen > bLen ? aLen : bLen
for (var i = 0; i < len; i++) {
var leftNode = aChildren[i]
var rightNode = bChildren[i]
index += 1
if (!leftNode) {
if (rightNode) {
// Excess nodes in b need to be added
apply = appendPatch(apply,
new VPatch(VPatch.INSERT, null, rightNode))
}
} else {
walk(leftNode, rightNode, patch, index)
}
if (isVNode(leftNode) && leftNode.count) {
index += leftNode.count
}
}
if (orderedSet.moves) {
// Reorder nodes last
apply = appendPatch(apply, new VPatch(
VPatch.ORDER,
a,
orderedSet.moves
))
}
return apply
}通过上面的重新排序算法整理了以后，两个children比较就只需在相同下标的情况下比较了，即aChildren的第N个元素和bChildren的第N个元素进行比较。然后较长的那个元素做insert操作（bChildren）或者remove操作（aChildren）即可。最后，我们将move操作再增加到patch中，就能够抵消我们在reorder时对整个数组的操作。这样只需要一次便利就得到了最终的patch值。
总结
整个Virtual DOM的diff算法设计的非常精巧，通过三个不同的分部算法来实现了VNode、Props和Children的diff算法，将整个Virtual DOM的的diff操作分成了三类。同时三个算法又互相递归调用，对两个Virtual DOM数做了一次（伪）深度优先的递归比较。
The above is the detailed content of How to implement virtual DOM? (code example). For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
