仮想 DOM を実装するにはどうすればよいですか? (コード例)-jsチュートリアル-php.cn

この記事の内容は、仮想 DOM の実装方法についてです。 (コードサンプル) は参考値となっておりますので、困っている方は参考にしていただければ幸いです。

この記事では、読者が全体のデータ構造と関連する Diff アルゴリズムをある程度理解できるように、virtual-dom のソースコードを読み解いて Virtual DOM の構造と関連する Diff アルゴリズムを説明します。

次回のブログでは、仮想 DOM の差分アルゴリズムの結果が実際の DOM にどのようにマッピングされるかを明らかにします。

この記事の主な内容は次のとおりです:

Virtual DOM の構造と Virtual DOM の差分アルゴリズム

注: この Virtual DOM の実装はソースではありません。 React Virtual DOM のコードですが、virtual-dom に基づいています) このライブラリ。この 2 つは原理的に似ていますが、このライブラリの方がシンプルで理解しやすいです。このライブラリと比較して、React は Virtual DOM をさらに最適化および調整しています。これについては、今後のブログで分析します。

仮想 DOM の構造

VirtualNode

仮想 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 のプレーンテキストに対応します。したがって、この属性にはテキストというフィールドが 1 つだけあります。

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 属性を変更します。

仮想 DOM の差分アルゴリズム

仮想 DOM の 3 つの構造を理解したところで、仮想 DOM の差分アルゴリズムを見てみましょう。

この Diff アルゴリズムは、Virtual DOM のコアアルゴリズムです。このアルゴリズムは、初期状態 A (VNode) と最終状態 B (VNode) を入力することで、A から B への変更ステップ (VPatch) を取得できます。取得した一連のステップに基づいて、どのノードを追加する必要があるかを知ることができます。どのノードを削除する必要があるか、またその属性が変更されたか。この Diff アルゴリズムは 3 つの部分に分かれています。

VNode の Diff アルゴリズム Props の Diff アルゴリズム Vnode の子の Diff アルゴリズム

以下、これらの Diff アルゴリズムを 1 つずつ紹介します。

VNode の差分アルゴリズム

このアルゴリズムは、単一の VNode の比較アルゴリズムです。これは、2 つのツリー内の単一ノードを比較するシナリオで使用されます。具体的なアルゴリズムは次のとおりです。ソースコードを直接読みたくない場合は、以下を参照することもできます。参考として、関連するコードフローの手順が記載されています:

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)
    }
}

ログイン後にコピー

具体的なロジックコードは次のとおりです。

If a と b がこれである場合 2 つの VNode が一致する場合、変更はないと見なされ、直接戻ります。

そのうちの 1 つがサンクである場合は、サンク比較メソッド thunks を使用します。

a がウィジェットで、b が空の場合、a とその子ノードの削除操作がパッチに再帰的に追加されます。

b が VNode の場合、

a も VNode の場合、tagName、namespace、key を比較し、それらが同じである場合は、2 つの VNode の Props を比較します (後述の diffProps アルゴリズム)、2 つの VNode の子を同時に比較します (後述の diffChildren アルゴリズムを使用)。それらが異なる場合は、ノード b の挿入操作をパッチに直接追加し、マーク位置を true に設定します。

a が VNode でない場合は、ノード b の挿入操作をパッチに直接追加し、マーク位置を true に設定します。

b が VText の場合、a のタイプが VText であるかどうかを確認します。そうでない場合は、パッチに VText 操作を追加し、フラグビットを true に設定します。VText であり、テキストの内容が異なる場合は、パッチへの VText 操作。操作はパッチに追加されます。

b がウィジェットの場合、a のタイプがウィジェットであるかどうかを確認し、ウィジェットである場合はフラグを true に設定します。 aの種類に関係なく、パッチにWidget操作を追加します。

フラグビットを確認します。フラグが true の場合は、再帰によって a とその子ノードの削除操作をパッチに追加します。

これは、単一の VNode ノードの差分アルゴリズムのプロセス全体です。このアルゴリズムは diff アルゴリズム全体への入り口であり、2 つのツリーの比較はこのアルゴリズムから始まります。

Prpps の差分アルゴリズム

単一の VNode ノードの差分アルゴリズムを読んだ後、上記の diffProps アルゴリズムを見てみましょう。

このアルゴリズムは、2 つの比較される VNode ノードの Props 比較アルゴリズムです。これは、キー値とタグ名が両方のシナリオで同じである場合に使用されます。具体的なアルゴリズムは次のとおりです。ソースコードを直接読みたくない場合は、以下を参照することもできます。参考として、関連するコードフローの手順が記載されています:

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
}

ログイン後にコピー

具体的なロジックコードは次のとおりです:

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

ログイン後にコピー

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

检查a和b中的children是否拥有key字段，如果没有，直接返回b的children数组。
如果存在，初始化一个数组newChildren，遍历a的children元素。
1. 如果aChildren存在key值，则去bChildren中找对应key值，如果bChildren存在则放入新数组中，不存在则放入一个null值。
2. 如果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数做了一次（伪）深度优先的递归比较。

以上が仮想 DOM を実装するにはどうすればよいですか? (コード例)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。