作者：秦策
接《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