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.
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 :
Parcourt l'objet a.
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数做了一次（伪）深度优先的递归比较。
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!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
