Der Inhalt dieses Artikels befasst sich mit der Implementierung von virtuellem DOM. (Codebeispiel) hat einen gewissen Referenzwert. Freunde in Not können darauf verweisen.
In diesem Artikel wird die Struktur von Virtual DOM und verwandten Diff-Algorithmen durch Lesen und Analysieren des Quellcodes von Virtual-Dom erläutert, sodass die Leser ein gewisses Verständnis der gesamten Datenstruktur und verwandter Diff-Algorithmen erlangen können.
Wie die Ergebnisse des Diff-Algorithmus im virtuellen DOM auf das reale DOM abgebildet werden, verraten wir im nächsten Blog.
Der Hauptinhalt dieses Artikels ist:
Die Struktur von Virtual DOM und der Diff-Algorithmus von Virtual DOM
Hinweis: Die Implementierung dieses Virtual DOM ist nicht die Quelle Code von React Virtual DOM, aber basierend auf Virtual-Dom) dieser Bibliothek. Die beiden sind im Prinzip ähnlich und diese Bibliothek ist einfacher und leichter zu verstehen. Im Vergleich zu dieser Bibliothek hat React Virtual DOM weiter optimiert und angepasst, was ich in nachfolgenden Blogs analysieren werde.
Struktur des virtuellen DOM
VirtualNode
Als Metadatenstruktur des virtuellen DOM befindet sich VirtualNode in der Datei vnode/vnode.js. Lassen Sie uns einen Teil des Deklarationscodes abfangen, um einen Blick auf die interne Struktur zu werfen:
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()检测标志Das Obige ist die vollständige Struktur eines VirtualNode, einschließlich spezifischer Tag-Namen, Attribute, untergeordneter Knoten usw.
VText
VText ist ein Nur-Text-Knoten, der dem Nur-Text in HTML entspricht. Daher verfügt dieses Attribut nur über ein Feld: Text.
function VirtualText(text) {
this.text = String(text)
}
VirtualText.prototype.version = version
VirtualText.prototype.type = "VirtualText"VPatch
VPatch ist eine Datenstruktur, die den Vorgangsdatensatz darstellt, der im virtuellen DOM ausgeführt werden muss. Es befindet sich in der Datei vnode/vpatch.js. Werfen wir einen Blick auf den spezifischen Code darin:
// 定义了操作的常量，如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"Die Konstanten definieren die Operationen auf dem VNode-Knoten. Beispiel: VTEXT dient zum Hinzufügen eines VText-Knotens und PROPS zum Ändern des Props-Attributs des aktuellen Knotens.
Diff-Algorithmus des virtuellen DOM
Da wir nun die drei Strukturen im virtuellen DOM verstanden haben, werfen wir einen Blick auf den Diff-Algorithmus des virtuellen DOM.
Dieser Diff-Algorithmus ist der Kernalgorithmus in Virtual DOM. Durch Eingabe des Anfangszustands A (VNode) und des Endzustands B (VNode) kann dieser Algorithmus die Änderungsschritte (VPatch) von A nach B ermitteln. Anhand der erhaltenen Schrittfolge können wir erkennen, welche Knoten hinzugefügt werden müssen und welche Knoten Welche Knoten gelöscht werden müssen und deren Attribute sich geändert haben. Dieser Diff-Algorithmus ist in drei Teile unterteilt:
Diff-Algorithmus von VNode, Diff-Algorithmus von Props, Diff-Algorithmus von Vnode für Kinder
Im Folgenden stellen wir diese Diff-Algorithmen einzeln vor.
VNode-Diff-Algorithmus
Dieser Algorithmus ist ein Vergleichsalgorithmus für einen einzelnen VNode. Es wird in dem Szenario verwendet, in dem ein einzelner Knoten in zwei Bäumen verglichen wird. Der spezifische Algorithmus lautet wie folgt. Wenn Sie den Quellcode nicht direkt lesen möchten, können Sie sich auch an die folgenden relevanten Codeflussanweisungen wenden:
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)
}
}Die spezifische Logik von Der Code lautet wie folgt:
Wenn a und b dies sind Wenn die beiden VNodes übereinstimmen, wird davon ausgegangen, dass keine Änderung vorliegt, und es wird direkt zurückgegeben.
Wenn einer von ihnen ein Thunk ist, verwenden Sie die Thunk-Vergleichsmethode Thunks.
Wenn a ein Widget und b leer ist, wird die Entfernungsoperation von a und seinen untergeordneten Knoten rekursiv zum Patch hinzugefügt.
Wenn b ein VNode ist,
Wenn a auch ein VNode ist, dann vergleichen Sie tagName, Namespace, Schlüssel, und wenn sie gleich sind, vergleichen Sie die Props der beiden VNodes (unter Verwendung von Der unten erwähnte diffProps-Algorithmus. Vergleichen Sie die untergeordneten Elemente zweier VNodes gleichzeitig (mit dem unten erwähnten diffChildren-Algorithmus). Wenn sie unterschiedlich sind, fügen Sie die Einfügeoperation von Knoten b direkt zum Patch hinzu und setzen Sie die Markierungsposition auf true.
Wenn a kein VNode ist, fügen Sie den Einfügevorgang von Knoten b direkt zum Patch hinzu und setzen Sie die Markierungsposition auf true.
Wenn b VText ist, prüfen Sie, ob der Typ von a VText ist. Wenn nicht, fügen Sie die VText-Operation zum Patch hinzu und setzen Sie das Flag auf true, wenn dies der Fall ist und der Textinhalt anders ist VText-Operation auf true Die Operation wird dem Patch hinzugefügt.
Wenn b ein Widget ist, prüfen Sie, ob der Typ von a ein Widget ist. Wenn ja, setzen Sie das Flag auf true. Fügen Sie unabhängig von der Art eines Patches die Widget-Operation zum Patch hinzu.
Überprüfen Sie das Flag-Bit. Wenn das Flag wahr ist, fügen Sie den Entfernungsvorgang von a und seinen untergeordneten Knoten durch Rekursion hinzu.
Dies ist der gesamte Prozess des Diff-Algorithmus eines einzelnen VNode-Knotens. Dieser Algorithmus ist der Eingang zum gesamten Diff-Algorithmus, und der Vergleich zweier Bäume beginnt mit diesem Algorithmus.
Nachdem wir den Diff-Algorithmus eines einzelnen VNode-Knotens gelesen haben, werfen wir einen Blick auf den oben erwähnten diffProps-Algorithmus.
Dieser Algorithmus ist ein Props-Vergleichsalgorithmus für zwei verglichene VNode-Knoten. Es wird verwendet, wenn der Schlüsselwert und der Tag-Name in beiden Szenarios gleich sind. Der spezifische Algorithmus lautet wie folgt. Wenn Sie den Quellcode nicht direkt lesen möchten, finden Sie dort relevante Codeflussanweisungen als Referenz:
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
}Die spezifische Logik von Der Code lautet wie folgt:
Traverse das a-Objekt.
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数做了一次（伪）深度优先的递归比较。
Das obige ist der detaillierte Inhalt vonWie implementiert man virtuelles DOM? (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
