Wie implementiert man virtuelles DOM? (Codebeispiel)

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.

Diff-Algorithmus von Prpps

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:

1. Traverse das a-Objekt.

   1. 当key值不存在于b，则将此值存储下来，value赋值为undefined。
   2. 当此key对应的两个属性都相同时，继续终止此次循环，进行下次循环。
   3. 当key值对应的value不同且key值对应的两个value都是对象时，判断Prototype值，如果不同则记录key对应的b对象的值；如果b对应的value是hook的话，记录b的值。
   4. 上面条件判断都不同且都是对象时，则继续比较key值对应的两个对象（递归）。
   5. 当有一个不是对象时，直接将b对应的value进行记录。
2. 遍历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&#39;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&#39;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
        }
    }
}

下面，我们来简单介绍下这个排序算法：

1. 检查a和b中的children是否拥有key字段，如果没有，直接返回b的children数组。

2. 如果存在，初始化一个数组newChildren，遍历a的children元素。

   1. 如果aChildren存在key值，则去bChildren中找对应key值，如果bChildren存在则放入新数组中，不存在则放入一个null值。
   2. 如果aChildren不存在key值，则从bChildren中不存在key值的第一个元素开始取，放入新数组中。
3. 遍历bChildren，将所有achildren中没有的key值对应的value或者没有key，并且没有放入新数组的子节点放入新数组中。
4. 将bChildren和新数组逐个比较，得到从新数组转换到bChildren数组的move操作patch（即remove+insert）。
5. 返回新数组和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数做了一次（伪）深度优先的递归比较。

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!