去年寫了一篇文章手寫一個虛擬DOM庫,徹底讓你理解diff算法介紹虛擬DOM的patch過程和diff算法過程,當時使用的是雙端diff算法,今年看到了Vue3使用的已經是快速diff算法,所以也想寫一篇來記錄一下,但是肯定已經有人寫過了,所以就在想能不能有點不一樣的,上次的文章主要是通過畫圖來一步步展示diff算法的每一種情況和過程,所以就在想能不能改成動畫的形式,于是就有了這篇文章。當然目前的實現還是基于雙端diff算法的,后續會補充上快速diff算法。
傳送門:雙端Diff算法動畫演示。
界面就是這樣的,左側可以輸入要比較的新舊VNode列表,然后點擊啟動按鈕就會以動畫的形式來展示從頭到尾的過程,右側是水平的三個列表,分別代表的是新舊的VNode列表,以及當前的真實DOM列表,DOM列表初始和舊的VNode列表一致,算法結束后會和新的VNode列表一致。
需要說明的是這個動畫只包含diff算法的過程,不包含patch過程。
先來回顧一下雙端diff算法的函數:
const diff = (el, oldChildren, newChildren) => {// 指針let oldStartIdx = 0let oldEndIdx = oldChildren.length - 1let newStartIdx = 0let newEndIdx = newChildren.length - 1// 節點let oldStartVNode = oldChildren[oldStartIdx]let oldEndVNode = oldChildren[oldEndIdx]let newStartVNode = newChildren[newStartIdx]let newEndVNode = newChildren[newEndIdx]while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if (oldStartVNode === null) {oldStartVNode = oldChildren[++oldStartIdx]} else if (oldEndVNode === null) {oldEndVNode = oldChildren[--oldEndIdx]} else if (newStartVNode === null) {newStartVNode = oldChildren[++newStartIdx]} else if (newEndVNode === null) {newEndVNode = oldChildren[--newEndIdx]} else if (isSameNode(oldStartVNode, newStartVNode)) { // 頭-頭patchVNode(oldStartVNode, newStartVNode)// 更新指針oldStartVNode = oldChildren[++oldStartIdx]newStartVNode = newChildren[++newStartIdx]} else if (isSameNode(oldStartVNode, newEndVNode)) { // 頭-尾patchVNode(oldStartVNode, newEndVNode)// 把oldStartVNode節點移動到最后el.insertBefore(oldStartVNode.el, oldEndVNode.el.nextSibling)// 更新指針oldStartVNode = oldChildren[++oldStartIdx]newEndVNode = newChildren[--newEndIdx]} else if (isSameNode(oldEndVNode, newStartVNode)) { // 尾-頭patchVNode(oldEndVNode, newStartVNode)// 把oldEndVNode節點移動到oldStartVNode前el.insertBefore(oldEndVNode.el, oldStartVNode.el)// 更新指針oldEndVNode = oldChildren[--oldEndIdx]newStartVNode = newChildren[++newStartIdx]} else if (isSameNode(oldEndVNode, newEndVNode)) { // 尾-尾patchVNode(oldEndVNode, newEndVNode)// 更新指針oldEndVNode = oldChildren[--oldEndIdx]newEndVNode = newChildren[--newEndIdx]} else {let findIndex = findSameNode(oldChildren, newStartVNode)// newStartVNode在舊列表里不存在,那么是新節點,創建插入if (findIndex === -1) {el.insertBefore(createEl(newStartVNode), oldStartVNode.el)} else { // 在舊列表里存在,那么進行patch,并且移動到oldStartVNode前let oldVNode = oldChildren[findIndex]patchVNode(oldVNode, newStartVNode)el.insertBefore(oldVNode.el, oldStartVNode.el)// 將該VNode置為空oldChildren[findIndex] = nullnewStartVNode = newChildren[++newStartIdx]// 舊列表里存在新列表里沒有的節點,需要刪除if (oldStartIdx <= oldEndIdx) {for (let i = oldStartIdx; i <= oldEndIdx; i++) {removeEvent(oldChildren[i])oldChildren[i] && el.removeChild(oldChildren[i].el)} else if (newStartIdx <= newEndIdx) {let before = newChildren[newEndIdx + 1] ? newChildren[newEndIdx + 1].el : nullfor (let i = newStartIdx; i <= newEndIdx; i++) {el.insertBefore(createEl(newChildren[i]), before)
該函數具體的實現步驟可以參考之前的文章,本文就不再贅述。
我們想讓這個diff過程動起來,首先要找到動畫的對象都有哪些,從函數的參數開始看,首先oldChildren和 newChildren兩個VNode列表是必不可少的,可以通過兩個水平的列表表示,然后是四個指針,這是雙端diff算法的關鍵,我們通過四個箭頭來表示,指向當前所比較的節點,然后就開啟循環了,循環中新舊VNode列表其實基本上是沒啥變化的,我們實際操作的是VNode對應的真實DOM元素,包括patch打補丁、移動、刪除、新增等等操作,所以我們再來個水平的列表表示當前的真實DOM列表,最開始肯定是和舊的VNode列表是對應的,通過diff算法一步步會變成和新的VNode列表對應。
再來回顧一下創建VNode對象的h函數:
export const h = (tag, data = {}, children) => {let text = ''let ellet key// 文本節點if (typeof children === 'string' || typeof children === 'number') {text = childrenchildren = undefined} else if (!Array.isArray(children)) {children = undefinedif (data && data.key) {key = data.keyreturn {tag, // 元素標簽children, // 子元素text, // 文本節點的文本el, // 真實domkey,data
我們輸入的VNode列表數據會使用h函數來創建成VNode對象,所以可以輸入的最簡單的結構如下:
tag: 'div',children: '文本節點的內容',data: {key: 'a'
輸入的新舊VNode列表數據會保存在store中,可以通過如下方式獲取到:
// 輸入的舊VNode列表store.oldVNode// 輸入的新VNode列表store.newVNode
接下來定義相關的變量:
// 指針列表const oldPointerList = ref([])const newPointerList = ref([])// 真實DOM節點列表const actNodeList = ref([])// 新舊節點列表const oldVNodeList = ref([])const newVNodeList = ref([])// 提示信息const info = ref('')
指針的移動動畫可以使用css的transition屬性來實現,只要修改指針元素的left值即可,真實DOM列表的移動動畫可以使用Vue的列表過渡組件TransitionGroup來輕松實現,模板如下:
{{ item.name }}
{{ item.value }}
舊的VNode列表
{{ item ? item.children : '空' }}
新的VNode列表
{{ item.children }}
{{ info }}
{{ item.value }}
{{ item.name }}
真實DOM列表
{{ item.children }}
雙端diff算法過程中是不會修改新的VNode列表的,但是舊的VNode列表是有可能被修改的,也就是當首尾比較沒有找到可以復用的節點,但是通過直接在舊的VNode列表中搜索找到了,那么會移動該VNode對應的真實DOM,移動后該VNode其實就相當于已經被處理過了,但是該VNode的位置又是在當前指針的中間,不能直接被刪除,所以只好置為空null,所以可以看到模板中有處理這種情況。
另外我們還創建了一個info元素用來展示提示的文字信息,作為動畫的描述。
但是這樣還是不夠的,因為每個舊的VNode是有對應的真實DOM元素的,但是我們輸入的只是一個普通的json數據,所以模板還需要新增一個列表,作為舊的VNode列表的關聯節點,這個列表只要提供節點引用即可,不需要可見,所以把它的display設為none:
// 根據輸入的舊VNode列表創建元素const _oldVNodeList = computed(() => {return JSON.parse(store.oldVNode)// 引用DOM元素const oldNode = ref(null)const oldNodeList = ref([])
{{ item.children }}
然后當我們點擊啟動按鈕,就可以給我們的三個列表變量賦值了,并使用h函數創建新舊VNode對象,然后傳遞給打補丁的patch函數就可以開始進行比較更新實際的DOM元素了:
const start = () => {nextTick(() => {// 表示當前真實的DOM列表actNodeList.value = JSON.parse(store.oldVNode)// 表示舊的VNode列表oldVNodeList.value = JSON.parse(store.oldVNode)// 表示新的VNode列表newVNodeList.value = JSON.parse(store.newVNode)nextTick(() => {let oldVNode = h('div',{ key: 1 },JSON.parse(store.oldVNode).map((item, index) => {// 創建VNode對象let vnode = h(item.tag, item.data, item.children)// 關聯真實的DOM元素vnode.el = oldNodeList.value[index]return vnode// 列表的父節點也需要關聯真實的DOM元素oldVNode.el = oldNode.valuelet newVNode = h('div',{ key: 1 },JSON.parse(store.newVNode).map(item => {return h(item.tag, item.data, item.children)// 調用patch函數進行打補丁patch(oldVNode, newVNode)
可以看到我們輸入的新舊VNode列表是作為一個節點的子節點的,這是因為只有當比較的兩個節點都存在非文本節點的子節點時才需要使用diff算法來高效的更新他們的子節點,當patch函數運行完后你可以打開控制臺查看隱藏的DOM列表,會發現是和新的VNode列表保持一致的,那么你可能要問,為什么不直接用這個列表來作為真實DOM列表呢,還要自己額外創建一個actNodeList列表,其實是可以,但是diff算法過程中是使用insertBefore等方法來移動真實DOM節點的,所以不好加過渡動畫,只會看到節點瞬間換位置,不符合我們的動畫需求。
到這里效果如下:
接下來我們先把指針搞出來,我們創建一個處理函數對象,這個對象上會掛載一些方法,用于在diff算法過程中調用,在函數中更新相應的變量。
const handles = {// 更新指針updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx) {oldPointerList.value = [name: 'oldStartIdx',value: oldStartIdx},name: 'oldEndIdx',value: oldEndIdxnewPointerList.value = [name: 'newStartIdx',value: newStartIdx},name: 'newEndIdx',value: newEndIdx},
然后我們就可以在diff函數中通過handles.updatePointers()更新指針了:
const diff = (el, oldChildren, newChildren) => {// 指針handles.updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx)
這樣指針就出來了:
然后在while循環中會不斷改變這四個指針,所以在循環中也需要更新:
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {handles.updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx)
但是這樣顯然是不行的,為啥呢,因為循環也就一瞬間就結束了,而我們希望每次都能停留一段時間,很簡單,我們寫個等待函數:
const wait = t => {return new Promise(resolve => {setTimeout(resolve()},t || 3000
然后我們使用async/await語法,就可以輕松在循環中實現等待了:
const diff = async (el, oldChildren, newChildren) => {while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {handles.updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx)await wait()
接下來我們新增兩個變量,來突出表示當前正在比較的兩個VNode:
// 當前比較中的節點索引const currentCompareOldNodeIndex = ref(-1)const currentCompareNewNodeIndex = ref(-1)const handles = {// 更新當前比較節點updateCompareNodes(a, b) {currentCompareOldNodeIndex.value = acurrentCompareNewNodeIndex.value = b
{{ item ? item.children : '空' }}
{{ item.children }}
給當前比較中的節點添加一個類名,用來突出顯示,接下來還是一樣,需要在diff函數中調用該函數,但是,該怎么加呢:
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if // ...} else if (isSameNode(oldStartVNode, newStartVNode)) {oldStartVNode = oldChildren[++oldStartIdx]newStartVNode = newChildren[++newStartIdx]} else if (isSameNode(oldStartVNode, newEndVNode)) {oldStartVNode = oldChildren[++oldStartIdx]newEndVNode = newChildren[--newEndIdx]} else if (isSameNode(oldEndVNode, newStartVNode)) {oldEndVNode = oldChildren[--oldEndIdx]newStartVNode = newChildren[++newStartIdx]} else if (isSameNode(oldEndVNode, newEndVNode)) {oldEndVNode = oldChildren[--oldEndIdx]newEndVNode = newChildren[--newEndIdx]} else {newStartVNode = newChildren[++newStartIdx]
我們想表現出頭尾比較的過程,其實就在這些if條件中,也就是要在每個if條件中停留一段時間,那么可以直接這樣嗎:
const isSameNode = async () => {handles.updateCompareNodes()await wait()if (await isSameNode(oldStartVNode, newStartVNode))
很遺憾,我嘗試了不行,那么只能改寫成其他形式了:
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {let stop = falselet _isSameNode = falseif (oldStartVNode === null) {callbacks.updateInfo('')oldStartVNode = oldChildren[++oldStartIdx]stop = trueif (!stop) {callbacks.updateInfo('頭-頭比較')callbacks.updateCompareNodes(oldStartIdx, newStartIdx)_isSameNode = isSameNode(oldStartVNode, newStartVNode)if (_isSameNode) {callbacks.updateInfo('key值相同,可以復用,進行patch打補丁操作。新舊節點位置相同,不需要移動對應的真實DOM節點'await wait()if (!stop && _isSameNode) {oldStartVNode = oldChildren[++oldStartIdx]newStartVNode = newChildren[++newStartIdx]stop = true
我們使用一個變量來表示是否進入到了某個分支,然后把檢查節點是否能復用的結果也保存到一個變量上,這樣就可以通過不斷檢查這兩個變量的值來判斷是否需要進入到后續的比較分支中,這樣比較的邏輯就不在if條件中了,就可以使用await了,同時我們還使用updateInfo增加了提示語:
const handles = {// 更新提示信息updateInfo(tip) {info.value = tip
接下來看一下節點的移動操作,當頭(oldStartIdx對應的oldStartVNode節點)尾(newEndIdx對應的newEndVNode節點)比較發現可以復用時,在打完補丁后需要將oldStartVNode對應的真實DOM元素移動到oldEndVNode對應的真實DOM元素的位置,也就是插入到oldEndVNode對應的真實DOM的后面一個節點的前面:
if (!stop && _isSameNode) {// 頭-尾patchVNode(oldStartVNode, newEndVNode)// 把oldStartVNode節點移動到最后el.insertBefore(oldStartVNode.el, oldEndVNode.el.nextSibling)// 更新指針oldStartVNode = oldChildren[++oldStartIdx]newEndVNode = newChildren[--newEndIdx]stop = true
那么我們可以在insertBefore方法移動完真實的DOM元素后緊接著調用一下我們模擬列表的移動節點的方法:
if (!stop && _isSameNode) {el.insertBefore(oldStartVNode.el, oldEndVNode.el.nextSibling)callbacks.moveNode(oldStartIdx, oldEndIdx + 1)
我們要操作的實際上是代表真實DOM節點的actNodeList列表,那么關鍵是要找到具體是哪個,首先頭尾的四個節點指針它們表示的是在新舊VNode列表中的位置,所以我們可以根據oldStartIdx和oldEndIdx獲取到oldVNodeList中對應位置的VNode,然后通過key值在actNodeList列表中找到對應的節點,進行移動、刪除、插入等操作:
const handles = {// 移動節點moveNode(oldIndex, newIndex) {let oldVNode = oldVNodeList.value[oldIndex]let newVNode = oldVNodeList.value[newIndex]let fromIndex = findIndex(oldVNode)let toIndex = findIndex(newVNode)actNodeList.value[fromIndex] = '#'actNodeList.value.splice(toIndex, 0, oldVNode)actNodeList.value = actNodeList.value.filter(item => {return item !== '#'const findIndex = (vnode) => {return !vnode: actNodeList.value.findIndex(item => {return item && item.data.key === vnode.data.key
其他的插入節點和刪除節點也是類似的:
插入節點:
const handles = {// 插入節點insertNode(newVNode, index, inNewVNode) {let node = {data: newVNode.data,children: newVNode.textlet targetIndex = 0if (index === -1) {actNodeList.value.push(node)} else {if (inNewVNode) {let vNode = newVNodeList.value[index]targetIndex = findIndex(vNode)} else {let vNode = oldVNodeList.value[index]targetIndex = findIndex(vNode)actNodeList.value.splice(targetIndex, 0, node)
刪除節點:
const handles = {// 刪除節點removeChild(index) {let vNode = oldVNodeList.value[index]let targetIndex = findIndex(vNode)actNodeList.value.splice(targetIndex, 1)
這些方法在diff函數中的執行位置其實就是執行insertBefore、removeChild方法的地方,具體可以本文源碼,這里就不在具體介紹了。
另外還可以凸顯一下已經結束比較的元素、即將被添加的元素、即將被刪除的元素等等,最終效果:
時間原因,目前只實現了雙端diff算法的效果,后續會增加上快速diff算法的動畫過程,有興趣的可以點個關注喲~
倉庫:https://github.com/wanglin2/VNode_visualization。