国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

如何實現一個虛擬 DOM——virtual-dom 源碼分析

qieangel2013 / 995人閱讀

摘要:具體代碼如下,,下面,我們來簡單介紹下這個排序算法檢查和中的是否擁有字段,如果沒有,直接返回的數組。通過上面這個排序算法,我們可以得到一個新的的數組。

概述

本文通過對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中的純文本。因此,這個屬性也只有text這一個字段。

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算法

了解了虛擬DOM中的三個結構,那我們下面來看下Virtual DOM的Diff算法。

這個Diff算法是Virtual DOM中最核心的一個算法。通過輸入初始狀態A(VNode)和最終狀態B(VNode),這個算法可以得到從A到B的變化步驟(VPatch),根據得到的這一連串步驟,我們就可以知道哪些節點需要新增,哪些節點需要刪除,哪些節點的屬性有了變化。在這個Diff算法中,又分成了三部分:

VNode的Diff算法

Props的Diff算法

Vnode children的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)
    }
}

代碼具體邏輯如下:

如果ab這兩個VNode全等,則認為沒有修改,直接返回。

如果其中有一個是thunk,則使用thunk的比較方法thunks

如果a是widget且b為空,那么通過遞歸將a和它的子節點的remove操作添加到patch中。

如果b是VNode的話,

如果a也是VNode,那么比較tagNamenamespacekey,如果相同則比較兩個VNode的Props(用下面提到的diffProps算法),同時比較兩個VNode的children(用下面提到的diffChildren算法);如果不同則直接將b節點的insert操作添加到patch中,同時將標記位置為true。

如果a不是VNode,那么直接將b節點的insert操作添加到patch中,同時將標記位置為true。

如果b是VText的話,看a的類型是否為VText,如果不是,則將VText操作添加到patch中,并且將標志位設置為true;如果是且文本內容不同,則將VText操作添加到patch中。

如果b是Widget的話,看a的類型是否為widget,如果是,將標志位設置為true。不論a類型為什么,都將Widget操作添加到patch中。

檢查標志位,如果標識為為true,那么通過遞歸將a和它的子節點的remove操作添加到patch中。

這就是單個VNode節點的diff算法全過程。這個算法是整個diff算法的入口,兩棵樹的比較就是從這個算法開始的。

Prpps的Diff算法

看完了單個VNode節點的diff算法,我們來看下上面提到的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對象。

當key值不存在于b,則將此值存儲下來,value賦值為undefined

當此key對應的兩個屬性都相同時,繼續終止此次循環,進行下次循環。

當key值對應的value不同且key值對應的兩個value都是對象時,判斷Prototype值,如果不同則記錄key對應的b對象的值;如果b對應的value是hook的話,記錄b的值。

上面條件判斷都不同且都是對象時,則繼續比較key值對應的兩個對象(遞歸)。

當有一個不是對象時,直接將b對應的value進行記錄。

遍歷b對象,將所有a對象中不存在的key值對應的對象都記錄下來。

整個算法的大致流程如下,因為比較簡單,就不畫相關流程圖了。如果邏輯有些繞的話,可以配合代碼食用,效果更佳。

Vnode children的Diff算法

下面讓我們來看下最后一個算法,就是關于兩個VNode節點的children屬性的diffChildren算法。這個個diff算法分為兩個部分,第一部分是將變化后的結果b的children進行順序調整的算法,保證能夠快速的和a的children進行比較;第二部分就是將a的children與重新排序調整后的b的children進行比較,得到相關的patch。下面,讓我們一個一個算法來看。

reorder算法

該算法的作用是將b節點的children數組進行調整重新排序,讓ab兩個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
        }
    }
}

下面,我們來簡單介紹下這個排序算法:

檢查ab中的children是否擁有key字段,如果沒有,直接返回b的children數組。

如果存在,初始化一個數組newChildren,遍歷a的children元素。

如果aChildren存在key值,則去bChildren中找對應key值,如果bChildren存在則放入新數組中,不存在則放入一個null值。

如果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數做了一次(偽)深度優先的遞歸比較。

下面一片博客,我會介紹如何將得到的VPatch操作應用到真實的DOM中,從而導致HTML樹的變化。

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/109180.html

相關文章

  • 構建一個使用 Virtual-DOM 的前端模版引擎

    摘要:目錄前言問題的提出模板引擎和結合的實現編譯原理相關模版引擎的詞法分析語法分析與抽象語法樹代碼生成完整的結語前言本文嘗試構建一個前端模板引擎,并且把這個引擎和進行結合。于是就構思了一個方案,在前端模板引擎上做手腳。 作者:戴嘉華 轉載請注明出處并保留原文鏈接( https://github.com/livoras/blog/issues/14 )和作者信息。 目錄 前言 問題的提出...

    imccl 評論0 收藏0
  • 如何實現 virtual-dom

    摘要:但是實際開發中,整個文檔樹中和標簽基本不會有太大的改動。在測試中,不難發現其實已經很快了,但是速度會比較慢,所以這里留下了一個待優化的點就是。 如何實現 virtual-dom 0. 什么是 vnode 相信大部分前端同學之前早已無數次聽過或了解過 vnode(虛擬節點),那么什么是 vnode? vnode 應該是什么樣的?如果不使用前端框架,我們可能會寫出這樣的頁面: ...

    rickchen 評論0 收藏0
  • React系列 --- virtualdom diff算法實現分析(三)

    摘要:所以只針對同層級節點做比較,將復雜度的問題轉換成復雜度的問題。 React系列 React系列 --- 簡單模擬語法(一)React系列 --- Jsx, 合成事件與Refs(二)React系列 --- virtualdom diff算法實現分析(三)React系列 --- 從Mixin到HOC再到HOOKS(四)React系列 --- createElement, ReactElem...

    sunsmell 評論0 收藏0
  • 去哪兒網迷你React的研發心得

    摘要:市面上竟然擁有多個虛擬庫。虛擬庫,就是出來后的一種新式庫,以虛擬與算法為核心,屏蔽操作,操作數據即操作視圖。及其他虛擬庫已經將虛擬的生成交由與處理了,因此不同點是,虛擬的結構與算法。因此虛擬庫是分為兩大派系算法派與擬態派。 去哪兒網迷你React是年初立項的新作品,在這前,去哪兒網已經深耕多年,擁有QRN(react-native的公司制定版),HY(基于React的hybird方案)...

    pekonchan 評論0 收藏0
  • React前端學習小結

    摘要:正式開始系統地學習前端已經三個多月了,感覺前端知識體系龐雜但是又非常有趣。更新一個節點需要做的事情有兩件,更新頂層標簽的屬性,更新這個標簽包裹的子節點。 正式開始系統地學習前端已經三個多月了,感覺前端知識體系龐雜但是又非常有趣。前端演進到現在對開發人員的代碼功底要求已經越來越高,幾年前的前端開發還是大量操作DOM,直接與用戶交互,而React、Vue等MVVM框架的出現,則幫助開發者從...

    iOS122 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<