這篇文章帶給大家的內容是關於虛擬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中的純文字。因此,這個屬性也只有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) } }
程式碼具體邏輯如下:
如果a和b這兩個VNode全等,則認為沒有修改,直接回傳。
如果其中有一個是thunk,則使用thunk的比較方法thunks。
如果a是widget且b為空,那麼透過遞歸將a和它的子節點的remove操作加入到patch中。
如果b是VNode的話,
如果a也是VNode,那麼比較tagName、namespace、key,如果相同則比較兩個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演算法的入口,兩棵樹的比較就是從這個演算法開始的。
看完了單一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
物件。
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数做了一次(伪)深度优先的递归比较。
以上是虛擬DOM怎麼實現? (程式碼範例)的詳細內容。更多資訊請關注PHP中文網其他相關文章!