Comment implémenter le DOM virtuel ? (exemple de code)

Le contenu de cet article porte sur la façon d'implémenter le DOM virtuel ? (Exemple de code) a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. J'espère que cela vous sera utile.

Cet article explique la structure du Virtual DOM et les algorithmes Diff associés en lisant et en analysant le code source du virtual-dom, afin que les lecteurs puissent avoir une certaine compréhension de l'ensemble de la structure des données et des algorithmes Diff associés.

Comment les résultats de l'algorithme Diff dans Virtual DOM sont mappés au DOM réel, nous le révélerons dans le prochain blog.

Le contenu principal de cet article est :

La structure du Virtual DOM et l'algorithme Diff du Virtual DOM

Remarque : L'implémentation de ce Virtual DOM n'est pas la source code de React Virtual DOM, mais basé sur virtual-dom) cette bibliothèque. Les deux sont similaires en principe et cette bibliothèque est plus simple et plus facile à comprendre. Par rapport à cette bibliothèque, React a encore optimisé et ajusté Virtual DOM, que j'analyserai dans les blogs suivants.

Structure du DOM virtuel

VirtualNode

En tant que structure de métadonnées du DOM virtuel, VirtualNode se trouve dans le fichier vnode/vnode.js. Interceptons une partie du code de déclaration pour jeter un œil à la structure interne :

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()检测标志

Ce qui précède est la structure complète d'un VirtualNode, y compris les noms de balises spécifiques, les attributs, les sous-nœuds, etc.

VText

VText est un nœud de texte brut, correspondant au texte brut en HTML. Cet attribut ne possède donc qu’un seul champ : texte.

function VirtualText(text) {
    this.text = String(text)
}

VirtualText.prototype.version = version
VirtualText.prototype.type = "VirtualText"

VPatch

VPatch est une structure de données qui représente l'enregistrement de l'opération qui doit être effectuée sur le DOM virtuel. Il se trouve dans le fichier vnode/vpatch.js. Jetons un coup d'œil au code spécifique à l'intérieur :

// 定义了操作的常量，如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"

Les constantes définissent les opérations sur le nœud VNode. Par exemple : VTEXT consiste à ajouter un nœud VText et PROPS consiste à modifier l'attribut Props du nœud actuel.

Algorithme Diff du DOM virtuel

Maintenant que nous comprenons les trois structures du DOM virtuel, jetons un coup d'œil à l'algorithme Diff du DOM virtuel.

Cet algorithme Diff est l'algorithme de base de Virtual DOM. En saisissant l'état initial A (VNode) et l'état final B (VNode), cet algorithme peut obtenir les étapes de changement (VPatch) de A à B. Sur la base de la série d'étapes obtenue, nous pouvons savoir quels nœuds doivent être ajoutés. et quels nœuds Quels nœuds doivent être supprimés et dont les attributs ont changé. Dans cet algorithme Diff, il est divisé en trois parties :

Algorithme Diff de VNode Algorithme Diff de Props Algorithme Diff pour enfants de Vnode

Ci-dessous, nous présenterons ces algorithmes Diff un par un.

Algorithme Diff de VNode

Cet algorithme est un algorithme de comparaison pour un seul VNode. Il est utilisé dans le scénario de comparaison d’un seul nœud dans deux arbres. L'algorithme spécifique est le suivant. Si vous ne souhaitez pas lire le code source directement, vous pouvez également vous tourner vers ce qui suit. Il y aura des instructions de flux de code pertinentes pour votre référence :

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

Le spécifique. La logique du code est la suivante :

Si a et Si ces deux VNodes sont congrus, on considère qu'il n'y a pas de modification et renvoie directement.

Si l'un d'eux est un thunk, utilisez la méthode de comparaison des thunks.

Si a est un widget et b est vide, alors l'opération de suppression de a et de ses nœuds enfants est ajoutée au patch de manière récursive.

Si b est un VNode,

Si a est également un VNode, alors comparez tagName, namespace, key, et s'ils sont identiques, comparez les Props des deux VNodes (en utilisant le diffProps mentionné ci-dessous), comparez les enfants de deux VNodes en même temps (en utilisant l'algorithme diffChildren mentionné ci-dessous) ; s'ils sont différents, ajoutez directement l'opération d'insertion du nœud b au patch et définissez la position de la marque sur true.

Si a n'est pas un VNode, ajoutez directement l'opération d'insertion du nœud b au patch et définissez la position de la marque sur true.

Si b est VText, vérifiez si le type de a est VText. Sinon, ajoutez l'opération VText au patch et définissez l'indicateur sur true si c'est le cas et que le contenu du texte est différent, puis modifiez le ; Opération VText sur true. L'opération est ajoutée au patch.

Si b est un widget, vérifiez si le type de a est un widget. Si c'est le cas, définissez l'indicateur sur true. Quel que soit le type de a, ajoutez l’opération Widget au correctif.

Vérifiez le bit d'indicateur. Si l'indicateur est vrai, ajoutez l'opération de suppression de a et de ses nœuds enfants au patch par récursivité.

Il s'agit de l'ensemble du processus de l'algorithme de comparaison d'un seul nœud VNode. Cet algorithme est l'entrée de l'ensemble de l'algorithme diff, et la comparaison de deux arbres commence à partir de cet algorithme.

Algorithme Diff de Prpps

Après avoir lu l'algorithme diff d'un seul nœud VNode, jetons un coup d'œil à l'algorithme diffProps mentionné ci-dessus.

Cet algorithme est un algorithme de comparaison Props pour deux nœuds VNode comparés. Il est utilisé lorsque la valeur de la clé et le nom de la balise sont identiques dans les deux scénarios. L'algorithme spécifique est le suivant. Si vous ne souhaitez pas lire le code source directement, vous pouvez également vous tourner vers le bas. Il y aura des instructions de flux de code pertinentes pour votre référence :

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
}

Le spécifique. La logique du code est la suivante :

1. Parcourt l'objet 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进行记录。
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数做了一次（伪）深度优先的递归比较。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!