前言
從開始碰 Vue 跟 React 後便常聽到 Virtual DOM 這個詞，我們都知道這兩個非常多人使用的框架 (函式庫) 都是建立於 Virtual DOM 之上，為的是避免直接操作 DOM，因為操作 DOM 這件事會耗費很大的成本。
Virtual DOM 實際上的作法就是用物件來描述 DOM 的結構，在 DOM 的節點需要更動時，不直接修改 DOM，而是透過 diff 演算法比較 Virtual DOM 修改前與修改後的樹狀結構，然後批次更新真實 DOM 中的節點。
雖然之前大概知道 Virtual DOM 是這樣的作法，但其實也都只是道聽塗說，沒實際 trace 過原始碼。所以，這次就來實作一個簡易的 Virtual DOM，讓自己對於 Virtual DOM 有更進一步的認識。
而這次的實作主要是參考 YouTube 上的一部影片 🎥 Building a Simple Virtual DOM from Scratch — Jason Yu，這部影片的講者非常的生動，而且現場 live coding 把簡易的 Virtual DOM 實作出來，真的很令人佩服。如果有興趣的話，不妨也可以看看這場演講。
操作 DOM 的方法
在實作 Virtual DOM 之前，先了解幾個在實作中會用到操作 DOM 的方法。如果已經很熟習的朋友可以直接跳過 😄
以下的內容都是從 MDN 上擷取出來，然後修改一下範例的描述，如果覺得不清楚，也可以直接到 MDN 上看看哦！
Document.createElement()
Document.createElement() 方法可以依指定的標籤名稱（tagName）建立 HTML 元素。
Document.createTextNode()
創建一個新的文字節點。
Node.appendChild()
Node.appendChild() 方法將一個節點附加到指定父節點的子節點列表的末尾處。如果將被插入的節點已經存在於當前文檔的文檔樹中，那麼 appendChild() 只會將它從原先的位置移動到新的位置（不需要事先移除要移動的節點）。
Element.setAttribute()
設置指定 Element 上的某個屬性值。如果屬性已經存在，則更新該值；否則，使用指定的名稱和值添加一個新的屬性。
Element.removeAttribute()
removeAttribute() 會從指定的 Element 中刪除一個屬性。
ChildNode.replaceWith()
ChildNode.replaceWith() 的方法用一套 Node 物件或者 DOMString 物件替換該節點父節點下的子節點 。 DOMString 物件則會被當做 Text 節點插入。
ChildNode.remove()
ChildNode.remove() 方法會把 Element 從它所屬的 DOM 樹中刪除。
Virtual DOM 的原理
描述 DOM 的物件
前面說道 Virtual DOM 是建立一份描述真實 DOM 的物件，所有的改動都是經由改變 Virtual DOM 之後，再利用 diff 演算法跟批次 patch 改變 DOM 的內容。
以下是一個簡易描述 DOM 的物件，透過 tagName 定義標籤的名稱， attrs 決定在標籤上的所有屬性， children 即是定義在標籤裡面的其他元素。實際上的 vNode 會更複雜，這篇文章中使用的只是一個非常簡易的版本。
初始化 Virtual DOM
接著，我們來了解 Virtual DOM 初始化的步驟。這裡跟平常我們在撰寫 Vue 或 React 的程式碼不太一樣，因為框架中都包了一層語法，在 Vue 中會用 template 語法，而 React 則是 JSX，後面都還要再轉譯一次，才是建立描述 DOM 的物件。
在 React 官方文件中「🔗 沒有 JSX 的 React」這個章節就有提到，JSX 的元素都是呼叫 React.createElement(component, props, ...children) 的語法，以下提到的第一個步驟便是像呼叫 React.createElement() 的過程。
第二個步驟，把 vNode 轉換成實際的 Node 這個過程，會像是將 {tagName: "div"} 這樣描述 DOM 的物件轉換成 <div></div> 。
最後一個步驟，則是把產生的 <div></div> 掛到真實的 DOM 上。
Virtual DOM 的運作過程
前面就有提到，在更新真實的 DOM 之前，會先透過 diff 演算法比較新的 Virtual DOM 與舊的 Virtual DOM，然後再改變 DOM 的節點。所以，如果要定期做到更新這件事，就要使用定時器 Timer 或是觀察者模式 (Observer Pattern)。
我不確定實際上框架會怎麼做這件事，實作中為了方便就使用 Timer 囉! 觀察者模式是我猜的，因為覺得很適合拿來做被動觸發更新。
這篇文章中使用 setInterval(..., 1000) 每一秒都執行 diff 演算法一次，然 後把需要修改的節點 patch 到真實的 DOM 上。
原理就講到這邊，我們開始來實作吧！
從零開始建立一個簡易的 Virtual DOM
首先，我們先看到使用 Virtual DOM 的主程式碼，這份程式碼會做以下幾件事情：
- 使用
createApp(count)建立描述 DOM 的物件，其中的count會決定img的元素數量。 - 使用
render(vApp)把描述 DOM 的物件轉換成實際的 Node。 - 使用
mount()把 Node 掛到 DOM 上。 - 最後，用一個
setInterval當作 Timer，每一秒更新count的數值，然後再次呼叫createApp(count)更新虛擬節點，並透過 Diff 與 Patch 改變 DOM 的節點。
我們依序來撰寫每個在主程式中用到的函式。
建立虛擬節點 — createElement(tagName, options)
我們先看到在 createApp() 中的程式碼，其中多次呼叫了createElement()，目的即是建立描述 DOM 的物件，這個函式實作起來也很簡單，只是透過傳入值建立物件。
別忘了要在輸入的參數加上預設值。
將虛擬節點轉換成真實的節點 — render(vNode)
在創建完虛擬節點後便是把物件轉換成真實的節點，我們分成兩個部分來看，一個部分是只有產生字串節點，另一個部分是產生比較複雜的節點。
我們在寫網頁的時候通常會在字串外包一個標籤，但是有時候可能是故意只保留一個字串，所以在產生節點時要處理這個情況，可以對應到主程式碼中的 String(`Current count: ${count}`)。
如果節點不是單純字串的話，則必須呼叫 renderElement() 。我們會在這邊根據 tagName 產生一個新的節點，然後透過 setAttribute 把所有的屬性都設定上去。
如果有 children 的話，則遞迴呼叫 render 拜訪所有的虛擬節點，產生相對應的元素，再用 appenChild 把所有的子節點都掛到 $el 上。
把節點掛到 DOM 上 — mount($node, $target)
在把虛擬節點轉換成真實的節點後，初始化的最後一個步驟就是掛到真實的 DOM 上了。在 mount() 這個函式中做的事情也很簡單，就是把在網頁中原本的 $target 節點替換成 $node 。
在主程式碼中 mount($app, document.getElementById("app")) 即是把產生的 $app 內容掛到 <div id="app"></div> 上。
Diff 演算法
要把一棵樹轉換成另一棵樹，並且要使用最少的步驟，其時間複雜度是 O(n³)。問題在於如果節點有 1000 個，所以計算量就來到 10 億次，計算量將會讓 CPU 造成不小的開銷。
因此為了解決這個問題，React 與 Vue 將時間複雜度降低至 O(n)，總歸來說，就是只處理同一層級的節點，不進行跨節點的比較，如果遇到節點不一樣的情況，就砍掉重新建立節點。
而此篇文章使用的 Diff 算法的時間複雜度也是 O(n)，只處理同一層級的節點。如果要實作傳統的 Diff 演算法，在 leetcode 中有類似的題目，是歸類於 Hard 的題目，以後有機會再說 😅。
Diff 演算法可以分成三個部分來看：
- 第一個部分是比較傳入的節點 (
diff函式本身)。 - 第二個部分是比較傳入節點的屬性 (
diffAttrs函本身)。 - 第三個部分是比較傳入節點的子節點 (
diffChildren函式)。
diff(oldVNode, newVNode)
先觀察一下程式碼的結構，可以看到很多 $node => { ... } 這樣子回傳的函式，便是 patch 的函式。patch($node) 函式傳入的 $node 會根據 Diff 演算法的結果而改變標籤上的屬性、新增子節點、改變子節點、刪除節點等等。
diff 函式需要考慮四種情況：
- 傳入的新節點可能會是
undefined，因為該節點是將被刪除的節點，所以回傳的patch函式中呼叫了Node.remove()。 - 舊節點或是新節點型態可能會是字串，此時可以直接比較兩個新舊節點，如果不一樣，則用新節點取代掉舊節點。反之，節點不變化。
- 舊節點與新節點的標籤不一樣，則用新節點取代掉舊節點。
- 舊節點與新節點的標籤一樣，所以繼續往下比較標籤上的屬性以及子節點。
diffAttrs(oldAttrs, newAttrs)
diffAttrs 比較簡單，主要就是在標籤上設定屬定跟刪除屬性。看到程式碼的第二行先宣告了一個空陣列 patches ，將會用於儲存屬性變動的 patch 函式。比較完所有的屬性後，會在 diff() 函式呼叫 patchAttrs($node)，將節點傳進來批次更新標籤上的屬性。
diffChildren(oldVchildren, newVChildren)
diffChildren 的任務跟 diffAttrs 很類似，可以用於更新變動的子節點、刪除子節點、插入新的子節點等等。
👉 第三行會比較所有舊子節點與新子節點，每個子節點都會呼叫 diff 函式比較是不是需要更新，如果遇到新子節點被刪除的情況， newVChildren[i] 會回傳 undefined ，因此呼叫 diff 函式將會回傳 Node.remove() 的 patch 函式。
👉 第七行則是用於處理插入新節點的情況，用 Array.slice() 將新插入的子節點分離出來，並將所有插入的子節點建立 patch 函式。
👉 最後，在 diffChildren 回傳的 patch 函式中，先用 childPatches 處理更新子節點與刪除子節點，再呼叫 additionalPatches 插入子節點。
在使用 childPatches 時，為了刪除子節點，會呼叫在 diff 函式中產生的 Node.remove() ，因此當節點被刪除十， for-loop 中的 i 可能會超過 $node.childNodes 的長度，會導致程式發生例外。所以，為了解決超出長度的問題，可以從最後一個 childNode 開始處理，在刪除時也不會因為 childNode 被刪除，導致例外發生。
結論
👉 實作的程式碼在這邊：CodesandBox 。
這篇文章實現了一個簡易的 Virtual DOM，透過實現的過程，更瞭解了 Virtual DOM 的思想。但是實現忽略了使用者更新 View 時，觸發事件進而更新 Virtual DOM 的過程 (可能不只忽略這些 😅)。
網路上其實有許多文章提供導讀 Virtual DOM 或實作 Virtual DOM，其複雜度比這篇文章難很多，這篇文章只是要體驗 Virtual DOM，如果對於比較複雜的實作有興趣，再自己去看看吧！
分享就到這邊，如果喜歡我的文章可以幫我拍個幾下手，在閱讀文章時如果有遇到什麼問題，或是有什麼建議，都歡迎留言告訴我，謝謝。 😃
