共计 9987 个字符，预计需要花费 25 分钟才能阅读完成。
概述
本文通过对 virtual-dom 的源码进行阅读和分析，针对 Virtual DOM 的结构和相关的 Diff 算法进行讲解，让读者能够对整个数据结构以及相关的 Diff 算法有一定的了解。
Virtual DOM 中 Diff 算法得到的结果如何映射到真实 DOM 中，我们将在下一篇博客揭晓。
本文的主要内容为：
Virtual DOM 的结构
Virtual DOM 的 Diff 算法
注：这个 Virtual DOM 的实现并不是 React Virtual DOM 的源码，而是基于 virtual-dom) 这个库。两者在原理上类似，并且这个库更加简单容易理解。相较于这个库，React 对 Virtual DOM 做了进一步的优化和调整，我会在后续的博客中进行分析。
Virtual DOM 的结构
VirtualNode
作为 Virtual DOM 的元数据结构，VirtualNode 位于 vnode/vnode.js 文件中。我们截取一部分声明代码来看下内部结构：
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() 检测标志
上面就是一个 VirtualNode 的完整结构，包含了特定的标签名、属性、子节点等。
VText
VText 是一个纯文本的节点，对应的是 HTML 中的纯文本。因此，这个属性也只有 text 这一个字段。
function VirtualText(text) {
this.text = String(text)
}
VirtualText.prototype.version = version
VirtualText.prototype.type = “VirtualText”
VPatch
VPatch 是表示需要对 Virtual DOM 执行的操作记录的数据结构。它位于 vnode/vpatch.js 文件中。我们来看下里面的具体代码：
// 定义了操作的常量，如 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”
其中常量定义了对 VNode 节点的操作。例如：VTEXT 就是增加一个 VText 节点，PROPS 就是当前节点有 Props 属性改变。
Virtual DOM 的 Diff 算法
了解了虚拟 DOM 中的三个结构，那我们下面来看下 Virtual DOM 的 Diff 算法。
这个 Diff 算法是 Virtual DOM 中最核心的一个算法。通过输入初始状态 A（VNode）和最终状态 B（VNode），这个算法可以得到从 A 到 B 的变化步骤（VPatch），根据得到的这一连串步骤，我们就可以知道哪些节点需要新增，哪些节点需要删除，哪些节点的属性有了变化。在这个 Diff 算法中，又分成了三部分：
VNode 的 Diff 算法
Props 的 Diff 算法
Vnode children 的 Diff 算法
下面，我们就来一个一个介绍这些 Diff 算法。
VNode 的 Diff 算法
该算法是针对于单个 VNode 的比较算法。它是用于两个树中单个节点比较的场景。具体算法如下，如果不想直接阅读源码的同学也可以翻到下面，会有相关代码流程说明供大家参考：
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)
}
}
代码具体逻辑如下：
如果 a 和 b 这两个 VNode 全等，则认为没有修改，直接返回。
如果其中有一个是 thunk，则使用 thunk 的比较方法 thunks。
如果 a 是 widget 且 b 为空，那么通过递归将 a 和它的子节点的 remove 操作添加到 patch 中。
如果 b 是 VNode 的话，
如果 a 也是 VNode，那么比较 tagName、namespace、key，如果相同则比较两个 VNode 的 Props（用下面提到的 diffProps 算法），同时比较两个 VNode 的 children（用下面提到的 diffChildren 算法）；如果不同则直接将 b 节点的 insert 操作添加到 patch 中，同时将标记位置为 true。
如果 a 不是 VNode，那么直接将 b 节点的 insert 操作添加到 patch 中，同时将标记位置为 true。
如果 b 是 VText 的话，看 a 的类型是否为 VText，如果不是，则将 VText 操作添加到 patch 中，并且将标志位设置为 true；如果是且文本内容不同，则将 VText 操作添加到 patch 中。
如果 b 是 Widget 的话，看 a 的类型是否为 widget，如果是，将标志位设置为 true。不论 a 类型为什么，都将 Widget 操作添加到 patch 中。
检查标志位，如果标识为为 true，那么通过递归将 a 和它的子节点的 remove 操作添加到 patch 中。
这就是单个 VNode 节点的 diff 算法全过程。这个算法是整个 diff 算法的入口，两棵树的比较就是从这个算法开始的。
Prpps 的 Diff 算法
看完了单个 VNode 节点的 diff 算法，我们来看下上面提到的 diffProps 算法。
该算法是针对于两个比较的 VNode 节点的 Props 比较算法。它是用于两个场景中 key 值和标签名都相同的情况。具体算法如下，如果不想直接阅读源码的同学也可以翻到下面，会有相关代码流程说明供大家参考：
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
}
代码具体逻辑如下：
遍历 a 对象。
当 key 值不存在于 b，则将此值存储下来，value 赋值为 undefined。
当此 key 对应的两个属性都相同时，继续终止此次循环，进行下次循环。
当 key 值对应的 value 不同且 key 值对应的两个 value 都是对象时，判断 Prototype 值，如果不同则记录 key 对应的 b 对象的值；如果 b 对应的 value 是 hook 的话，记录 b 的值。
上面条件判断都不同且都是对象时，则继续比较 key 值对应的两个对象（递归）。
当有一个不是对象时，直接将 b 对应的 value 进行记录。
遍历 b 对象，将所有 a 对象中不存在的 key 值对应的对象都记录下来。
整个算法的大致流程如下，因为比较简单，就不画相关流程图了。如果逻辑有些绕的话，可以配合代码食用，效果更佳。
Vnode children 的 Diff 算法
下面让我们来看下最后一个算法，就是关于两个 VNode 节点的 children 属性的 diffChildren 算法。这个个 diff 算法分为两个部分，第一部分是将变化后的结果 b 的 children 进行顺序调整的算法，保证能够快速的和 a 的 children 进行比较；第二部分就是将 a 的 children 与重新排序调整后的 b 的 children 进行比较，得到相关的 patch。下面，让我们一个一个算法来看。
reorder 算法
该算法的作用是将 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 元素。
如果 aChildren 存在 key 值，则去 bChildren 中找对应 key 值，如果 bChildren 存在则放入新数组中，不存在则放入一个 null 值。
如果 aChildren 不存在 key 值，则从 bChildren 中不存在 key 值的第一个元素开始取，放入新数组中。
遍历 bChildren，将所有 achildren 中没有的 key 值对应的 value 或者没有 key，并且没有放入新数组的子节点放入新数组中。
将 bChildren 和新数组逐个比较，得到从新数组转换到 bChildren 数组的 move 操作 patch（即 remove+insert）。
返回新数组和 move 操作列表。
通过上面这个排序算法，我们可以得到一个新的 b 的 children 数组。在使用这个数组来进行比较厚，我们可以将两个 children 数组之间比较的时间复杂度从 o(n^2) 转换成 o(n)。具体的方法和效果我们可以看下面的 DiffChildren 算法。
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 数做了一次（伪）深度优先的递归比较。
下面一片博客，我会介绍如何将得到的 VPatch 操作应用到真实的 DOM 中，从而导致 HTML 树的变化。
