집 > 기사 > 웹 프론트엔드 > 가상 DOM을 구현하는 방법은 무엇입니까? (코드 예)

가상 DOM을 구현하는 방법은 무엇입니까? (코드 예)

不言앞으로: 2019-03-14 11:44:032867검색

이 글의 내용은 가상 DOM을 구현하는 방법에 관한 것입니다. (코드 샘플)에는 특정 참조 값이 있습니다. 도움이 필요한 친구가 참조할 수 있기를 바랍니다.

이 글에서는 virtual-dom의 소스 코드를 읽고 분석하여 Virtual DOM의 구조와 관련 Diff 알고리즘을 설명하므로, 독자가 전체 데이터 구조와 관련 Diff 알고리즘을 어느 정도 이해할 수 있습니다.

Virtual DOM의 Diff 알고리즘 결과가 실제 DOM에 어떻게 매핑되는지는 다음 블로그에서 공개하겠습니다.

이 글의 주요 내용은 다음과 같습니다:

Virtual DOM의 구조와 Virtual DOM의 Diff 알고리즘

참고: 이 Virtual DOM의 구현은 React Virtual DOM의 소스 코드가 아니라 virtual-DOM을 기반으로 합니다. 돔) 도서관. 둘은 원칙적으로 유사하며 이 라이브러리가 더 간단하고 이해하기 쉽습니다. 이 라이브러리와 비교하여 React는 Virtual DOM을 더욱 최적화하고 조정했으며, 이에 대해서는 후속 블로그에서 분석하겠습니다.

Virtual DOM의 구조

VirtualNode

Virtual 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의 일반 텍스트에 해당하는 일반 텍스트 노드입니다. 따라서 이 속성에는 텍스트라는 하나의 필드만 있습니다.

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 속성을 변경하는 것입니다.

Virtual DOM의 Diff 알고리즘

이제 Virtual DOM의 세 가지 구조를 이해했으니 이제 Virtual DOM의 Diff 알고리즘을 살펴보겠습니다.

이 Diff 알고리즘은 Virtual DOM의 핵심 알고리즘입니다. 이 알고리즘은 초기 상태 A(VNode)와 최종 상태 B(VNode)를 입력함으로써 A에서 B로의 변경 단계(VPatch)를 얻을 수 있습니다. 획득된 일련의 단계를 기반으로 어떤 노드를 추가해야 하는지 알 수 있습니다. 삭제해야 할 노드와 속성이 변경된 노드. 이 Diff 알고리즘은 세 부분으로 나누어집니다:

VNode의 Diff 알고리즘 Props의 Diff 알고리즘 Vnode 어린이 Diff 알고리즘

이제 이러한 Diff 알고리즘을 하나씩 소개하겠습니다.

VNode의 Diff 알고리즘

이 알고리즘은 단일 VNode에 대한 비교 알고리즘입니다. 두 트리의 단일 노드를 비교하는 시나리오에서 사용됩니다. 구체적인 알고리즘은 다음과 같습니다. 소스 코드를 직접 읽고 싶지 않다면 다음을 참조할 수도 있습니다.

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

코드의 구체적인 논리는 다음과 같습니다.

두 개의 VNode a와 b가 합동이면 수정하지 않고 직접 반환하는 것으로 간주됩니다.

그 중 하나가 썽크라면 썽크 비교 방법인 썽크를 사용하세요.

a가 위젯이고 b가 비어 있는 경우 a와 해당 하위 노드의 제거 작업이 패치에 재귀적으로 추가됩니다.

b가 VNode인 경우,

a도 VNode인 경우 tagName, 네임스페이스, 키를 비교하고, 동일한 경우 두 VNode의 Prop을 비교하고(아래에 언급된 diffProps 알고리즘 사용) 동시에 두 VNode의 하위 항목(아래 언급된 diffChildren 알고리즘 사용)이 다른 경우 노드 b의 삽입 작업을 패치에 직접 추가하고 마크 위치를 true로 설정합니다.

a가 VNode가 아닌 경우 노드 b의 삽입 작업을 패치에 직접 추가하고 마크 위치를 true로 설정합니다.

b가 VText인 경우 a의 유형이 VText인지 확인하세요. 그렇지 않은 경우 VText 작업을 패치에 추가하고 플래그가 true이고 텍스트 내용이 다른 경우 패치에 VText 작업을 추가하세요. . 가운데.

b가 위젯인 경우 a의 유형이 위젯인지 확인하세요. 그렇다면 플래그를 true로 설정하세요. 유형에 관계없이 패치에 위젯 작업을 추가합니다.

플래그 비트를 확인하고, 플래그가 true이면 a와 해당 하위 노드의 제거 작업을 패치에 재귀적으로 추가하세요.

이것은 단일 VNode 노드의 diff 알고리즘의 전체 프로세스입니다. 이 알고리즘은 전체 diff 알고리즘의 입구이며 두 트리의 비교는 이 알고리즘에서 시작됩니다.

Prpps의 Diff 알고리즘

단일 VNode 노드의 diff 알고리즘을 읽은 후 위에서 언급한 diffProps 알고리즘을 살펴보겠습니다. diffProps算法。

该算法是针对于两个比较的VNode节点的Props比较算法。它是用于两个场景中key值和标签名都相同的情况。具体算法如下，如果不想直接阅读源码的同学也可以翻到下面，会有相关代码流程说明供大家参考：

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
}

代码具体逻辑如下：

遍历a

이 알고리즘은 비교된 두 VNode 노드에 대한 Props 비교 알고리즘입니다. 두 시나리오 모두에서 키 값과 태그 이름이 동일한 경우에 사용됩니다. 구체적인 알고리즘은 다음과 같습니다. 소스 코드를 직접 읽고 싶지 않다면 하단으로 이동하여 참고할 수 있는 관련 코드 흐름 지침이 있습니다. 🎜

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객체를 트래버스합니다. 🎜
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

html NULL 常量递归循环数据结构 Namespace JS undefined 对象 dom prototype 算法

성명：

이 기사는 segmentfault.com에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제

이전 기사：JSON.parse() 및 JSON.stringify() 성능 테스트(예)다음 기사：JSON.parse() 및 JSON.stringify() 성능 테스트(예)