作者：秦策
接《IE 浏覽器 DOM 樹結構概覽（上）》
現代浏覽器中，為了更好的使用者體驗，頁面經常需要根據不同情況動态進行變化，DOM 流也需要相應的進行修改。為了提高對于流的通路效率，IE 浏覽器采用 Splay tree 來對這個流進行操作。SplayTree 雖然名義上稱作 Tree，其實并不是一個真正意義上樹結構，其本質是為了高效操作流結構而産生的一套改進算法。
IE 中SpalyTree 的基本資料結構為 <code>CTreePos</code>，用于表示流中各資料在 SplayTree 中的邏輯關系，再看一遍 CTreePos 的資料結構，其<code>_pFirstChild</code>、<code>_pNext</code> 指針便是用于描述目前節點在 SplayTree 中的邏輯關系。
SplayTree 的主要功能既是在保證流結構順序的情況下，使得最後通路的節點處在樹的最頂層，進而提升通路效率。以如下頁面舉例想要在在頁面[p1]、[p2] 位置插入标簽<code><p></code>
<code><html>[p1]<textarea></textarea>[p2]<html></code>
首先通路 [p1] 位置，通過 Splay 操作将 [p1] 所指節點旋轉置樹頂，此時 SplayTree 如下左樹所示；接着通路 [p2] 位置，SplayTree 變為如下右圖，此時針對DOM 的操作隻需要發生在 [p1] 的右子樹上即可
SplayTree 的核心函數 <code>Splay()</code>逆向如下，部分備援代碼沒有給出
在通過 SplayTree 高效的實作了 DOM 流的通路之後，IE 設計了一套專門用于操作 DOM 樹的機制稱為 <code>CSpliceTreeEngine</code>，對于 DOM 流的一系列修改操作均通過它來進行。<code>SpliceTreeInternal()</code> 函數部分功能逆向如下
函數首先調用 <code>RecordSplice</code>函數将源 DOM 流中的節點資訊備份一遍，接着根據操作要求決定是否将源 DOM 流中的節點資訊删除，最後将之前備份的節點資訊插入目标 DOM 流中。
對 DOM 流結構進行操作還需要有一個重要的結構 <code>CTreePosGap</code>，該結構用于訓示兩個 CTreePos 之間的内容，在對流進行插入和删除操作時都需要用到<code>CTreePosGap</code>結構來訓示需要操作的區間。<code>CTreePosGap</code> 資料結構如下所示
當然上述操作均要通過 <code>CMarkupPointer</code>來作為 DOM 流的指針才能完成。
通常情況下，一個頁面内容被修改之後， 頁面中的<code>CMarkupPointer</code>還會保留在之前未修改時的位置。舉例來說
當第一個頁面被修改為第二個頁面之後，雖然頁面的内容發生了改變，但是 <code>CMarkupPointer</code>的相對位置仍然保持不變。但如果頁面的修改發生在 <code>CMarkupPointer</code> 指向的位置，如上例中，向c、d之間插入一個Z，p 的位置就會出現二義性。
<code>abcZ[p1]de or abc[p1]Zde</code>
這時就需要引用另一個重要的概念<code>gravity</code>，每一個 <code>CMarkupPointer</code> 都有一個 <code>gravity</code> 值辨別着其左偏或右偏。仍以上述頁面為例
<code>abc[p1,right]defg[p2,left]hij</code>
分别在p1,p2的位置插入一對 <code><B></code>标簽。這時由于<code>gravity</code>的存在，頁面會變成如下
<code>abc<B>[p1,right]defg[p2,left]</B>hij</code>
預設情況下<code>CMarkupPointer</code> 的<code>gravity</code> 值是 left。下面的函數負責檢視或者修改<code>CMarkupPointer</code> 的 <code>gravity</code> 值
再考慮如下例子
<code>[p2]ab[p1]cdxy</code>
當bc 段被移動到 xy之間時p1的位置也出現了二義性，是應該随着bc移動，還是應該繼續保持在原位呢
<code>[p2]a[p1]dxbcy or [p2]adxb[p1]cy</code>
這就需要 <code>cling</code> 的存在，如果p1指定了<code>cling</code>屬性，那麼頁面操作之後就會成為右邊所示的情況，否則就會出現左邊所示的情況
<code>cling</code>和 <code>gravity</code>可以協同作用，考慮下面的例子
<code>a[p1]bcxy</code>
b移動到x、y之間，如果p1指定了 <code>cling</code>屬性，并且 <code>gravity</code> 值為 right，那麼p1便會跟随b一起到xy之間。這種情況下如果b被删除，那麼p1也會跟着從DOM 流中移除，但并不會銷毀，因為p1還有可能重新被使用。<code>cling</code>相關的函數，函數原型如下
下面通過實際的 js 操作來說明如何對 DOM 流進行修改的
appendChild 意為在目标 Element 的最後添加一個子節點，其内部其實是通過 <code>InsertBefore</code>來實作的，
函數首先通過 <code>CMarkupPointer</code> 指定到 parent 的 <code>BeforeEnd</code>位置，再調用 <code>CDoc::InsertElement() -> CMarkup::InsertElementInternal</code>進行實際的插入操作，一般而言标簽都是成對出現的，是以這裡需要使用兩個 <code>CMarkupPointer</code>分别指定新插入标簽的 Begin 和 End 位置
函數的主要邏輯為，首先通過一系列的 <code>CTreePosGap</code> 操作，指定 Begin 和 End 的位置；接着建立一個 <code>CTreeNode</code>并與 Element 關聯。調用 <code>CTreeNode::InitBeginPos</code>初始化标簽對象的 BeginPos ；接着調用 <code>CMarkup::Insert</code> 将 BeginPos 插入 DOM 流中，同時也插入 SpalyTree 中，并調用 <code>CTreePos::GetCpAndMarkup</code> 擷取cp 資訊，更新 SpalyTree 結構，同時觸發 <code>Notify</code> ，進行響應事件的分發。完成了 BeginPos 的操作之後，對 EndPos 也執行相同的操作，最終完成功能。
replaceNode
replaceNode.aspx) 用于将 DOM 流中一個節點替換為另一個節點，其主要功能函數我這裡顯示不出符号表，其逆向主要功能代碼如下
函數的主要邏輯為，通過兩個 <code>CMarkupPointer</code> 指針指定需要替換的目标節點在 DOM 流中的 Begin 和 End 位置，接着調用 <code>CDoc::Move()</code> 函數完成功能。<code>CDoc::Move()</code> 則直接通過調用 <code>CDoc::CutCopyMove</code> 來實作
<code>CDoc::CutCopyMove</code> 根據傳入的 <code>CMarkupPointer</code> 位置資訊構造三個 <code>CTreePosGap</code> 對象，并根據調用者的要求，選擇是進行 <code>Copy</code>操作還是 進行<code>Move</code>操作，最終将請求傳遞給 <code>CSpliceTreeEngine</code>。
IE 的這種 DOM 流結構是由于曆史原因形成的一種特殊情況，随着浏覽器功能的越來越豐富，這種 DOM 組織方式出現越來越多的問題。在 Edge 中微軟已經抛棄了 DOM 流的設計，轉而建構了一個真正意義上的 DOM 樹。
IE 中與 DOM 相關的内容還有很多，這裡僅僅列出了一點微小的工作，還有很多複雜的結構需要進一步分析。
[1] https://msdn.microsoft.com/en-us/library/bb508514(v=vs.85).aspx