[TOC]
一、DOM 流簡介
DOM （Document Object Model）作為現(xiàn)代瀏覽器的基礎(chǔ)栗菜，其設(shè)計和實(shí)現(xiàn)方式影響著整個瀏覽器的表現(xiàn)。對安全研究者而言夭谤，了解DOM 的結(jié)構(gòu)更是有著特殊的意義傍睹。在對 DOM 結(jié)構(gòu)有了了解之后進(jìn)行相關(guān)漏洞的分析隔盛，分析工作將會有一個清晰的脈絡(luò)和方向，使得分析工作變得更加簡單焰望，對漏洞的理解也會更加深刻和具體骚亿。
IE 作為一度占據(jù)很大市場份額的主流瀏覽器其 DOM 的組織和結(jié)構(gòu)值得我們?nèi)パ芯恳环E 瀏覽器在剛剛推出時還只是實(shí)現(xiàn)簡單的文本解析功能熊赖，隨著頁面功能的豐富和各種新特性的加入来屠，IE 瀏覽器的功能也變得越來越復(fù)雜，但是作為瀏覽器骨架的 DOM 結(jié)構(gòu)卻仍然延續(xù)了最初的設(shè)計，微軟嘗試通過不斷添加新的屬性以優(yōu)化其表現(xiàn)使其適應(yīng)現(xiàn)代瀏覽器的功能需要俱笛。
出于以上的歷史原因捆姜，IE 瀏覽器的 DOM 結(jié)構(gòu)并不是一個真正意義上的樹結(jié)構(gòu)，而是被設(shè)計成為一個流結(jié)構(gòu)迎膜，頁面內(nèi)容解析出的節(jié)點(diǎn)在邏輯上以線性形式排列泥技，對于 DOM 的訪問和修改均以流的方式進(jìn)行。微軟在有關(guān)Markup 的設(shè)計文檔中描述了這一特點(diǎn) 磕仅。
以如下 Html 文檔舉例
My <B>dog</B> has fleas.
按照樹形結(jié)構(gòu)進(jìn)行構(gòu)建珊豹，上述頁面會被解析成如下的一棵樹
ROOT
|
+-----+------+
| | |
"My" B "has fleas."
|
"dog"
但是如果將上述頁面進(jìn)行修改變成
Where do <B>you <I>want to</B> go</I> today?
在這個頁面中 <B> 標(biāo)簽和 <I> 標(biāo)簽相互嵌套，這樣一來頁面便無法被簡單的表示成為樹結(jié)構(gòu)榕订，此時便選擇使用流來表示頁面店茶，并通過范圍操作操作頁面內(nèi)容。
本文將通過對 IE 8 版本瀏覽器進(jìn)行分析和逆向劫恒，闡述 IE 中 DOM 的結(jié)構(gòu)贩幻，以及這種結(jié)構(gòu)如何在瀏覽器中發(fā)揮作用。（為了方便描述下文統(tǒng)一將 Html 文檔中的標(biāo)簽成為 tag两嘴，而將由 tag 解析而的到的對象稱為 Element丛楚。）
二、DOM 流的結(jié)構(gòu)
在 IE 的 DOM 流中憔辫，頁面元素 Element 并不直接相關(guān)聯(lián)趣些，而是間接通過一個叫做 CTreeNode 的類來完成這一功能。CTreeNode 類結(jié)構(gòu)如下(本文中所列出的數(shù)據(jù)結(jié)構(gòu)和函數(shù)均根據(jù) IE 8 逆向而來贰您，IE9喧务、IE10、IE11 中有所不同枉圃， 但是核心思想均是相同的)
class CTreeNode
{
public:
CElement * element;
CTreeNode * parent;
BYTE _etag; // 0-7: element tag
BYTE _fFirstCommonAncestorNode : 1; // 8: for finding common ancestor
BYTE _fInMarkup : 1; // 9: this node is in a markup and shouldn't die
BYTE _fInMarkupDestruction : 1; // 10: Used by CMarkup::DestroySplayTree
BYTE _fHasLookasidePtr : 2; // 11-12 Lookaside flags
BYTE _fBlockNess : 1; // 13: Cached from format -- valid if _iFF != -1
BYTE _fHasLayout : 1; // 14: Cached from format -- valid if _iFF != -1
BYTE _fUnused : 1; // 15: Unused
SHORT _iPF; // 16-31: Paragraph Format
// DWORD 2
SHORT _iCF; // 0-15: Char Format
SHORT _iFF;
CTreePos _tpBegin;
CTreePos _tpEnd;
DWORD unknow1;
DWORD unknow2;
DWORD unknow3;
};
每個 CTreeNode 都與一個 Element 相關(guān)聯(lián)功茴。一個 CTreeNode 中包含了兩個 CTreePos 結(jié)構(gòu)，分別在邏輯上代表著一個 Element 對應(yīng)的 tag 的頭標(biāo)簽和尾標(biāo)簽孽亲，這些 CTreePos 按照 tag 在 html 文檔中的排布順序依次前后相連坎穿，DOM 流即是這些 CTreePos 對象鏈接而成的雙向鏈表。
CTreePos 對象結(jié)構(gòu)如下返劲，其中 _pLeft玲昧、_pRight 用于構(gòu)建 DOM 流；_cchLeft 表示當(dāng)前 CTreePos 代表的 tag 在頁面中左邊有多少個字符篮绿，可以看做 CTreePos 在 DOM 流中的 index(這里需要經(jīng)過計算)孵延。
class CTreePos
{
public:
DWORD _cElemLeftAndFlags;
DWORD _cchLeft; // 左子樹中的字符數(shù)量
CTreePos* _pFirstChild;
CTreePos* _pNext;
CTreePos* _pLeft; // 當(dāng)前 CTreePos 在 DOM 流中的左邊
CTreePos* _pRight; // 當(dāng)前 CTreePos 在 DOM 流中的右邊
}
以具體的例子來說明 IE 中 DOM 流的情況∏着洌考慮如下頁面
<html>
<body>
<textarea>This is a Test</textarea>
</body>
<html>
上述頁面經(jīng)過 IE 解析之后構(gòu)成如下所示的 DOM 流尘应，每個 Element 與一個 CTreeNode 相關(guān)聯(lián)惶凝，CTreeNode 的兩個 CTreePos 分別按照其 tag 在頁面中的排布前后相連，html 的 tpBegin 與 body 的 tpBegin 之間省略的部分為頁面解析時自動補(bǔ)全的 Head Element
<html> <body> <textarea> This is a Test </textarea> </body> <html>
| | | | | | |
tpBegin...tpBegin tpBegin DataTreePos tpEnd tpEnd tpEnd
| | | | | |
| | ------------CTreeNode------------ | |
| | textarea | |
| | | |
| ----------------------------body-------------------------- |
| |
--------------------------------------html -----------------------------------
三犬钢、DOM 流的遍歷
為了將頁面內(nèi)容與解析出 DOM 流關(guān)聯(lián)起來苍鲜，IE 需要使用一個容器類來對 DOM 流進(jìn)行管理，這個容器類稱為 CMarkup 玷犹。在頁面開始解析時混滔，IE 會默認(rèn)創(chuàng)建一個 CMarkup 用于管理解析過程中產(chǎn)生的一系列 DOM 節(jié)點(diǎn)（CTreeNode）和 DOM 操作，此后每一次針對 DOM 的操作均需要為其指定一個 CMarkup 歹颓，該次操作的 DOM 流即為這個 CMarkup 管理的 DOM坯屿。
IE 瀏覽器在訪問頁面 DOM 流時也按照流的規(guī)范進(jìn)行，為此 IE 使用一個名叫 CMarkupPointer 的對象來作為 DOM 流的迭代器巍扛。CMarkupPointer 顧名思義是用于指示 CMarkup 即DOM 流中位置的指針愿伴。CMarkupPointer 并不是DOM 流的一部分，多數(shù)情況下它都是作為臨時變量來使用电湘。CMarkupPointer 可以被放置于頁面的這些位置：element 的開始、element 的結(jié)束或者 text 之中鹅经。由于 CMarkupPointer 本身不包含內(nèi)容寂呛，因此如果兩個 CMarkupPointer 指向了同一個位置便會難以區(qū)分。CMarkupPointer 的放置工作通過 MoveAdjacentToElement 函數(shù)完成瘾晃。函數(shù)原型如下
HRESULT MoveAdjacentToElement(
CElement *elementTarget,
ELEMENT_ADJACENCY
);
enum ELEMENT_ADJACENCY {
ELEMENT_ADJ_BeforeBegin
ELEMENT_ADJ_AfterBegin
ELEMENT_ADJ_BeforeEnd
ELEMENT_ADJ_AfterEnd
};
一旦 CMarkupPointer 被放置在了文檔中贷痪， 瀏覽器便可以通過它來獲取其所指向位置中 DOM 流的相關(guān)信息。這個功能使用 There 函數(shù)實(shí)現(xiàn)蹦误，函數(shù)原型如下
HRESULT There(
BOOL fLeft,
BOOL fMove,
MARKUP_CONTEXT_TYPE pContextType,
CElement **ppElement,
long *plCch,
OLE_CHAR *pch
);
- 第一個參數(shù)指定獲取指針右邊還是左邊的信息
- 第二個參數(shù)指定指針是否可移動劫拢，若不可移動，則函數(shù)僅僅會返回指針周圍內(nèi)容的描述强胰；否則舱沧，函數(shù)- 在返回周圍內(nèi)容描述的同時還會移動過去。
- 第三個參數(shù)為返回值偶洋，返回pointer周圍的內(nèi)容類型熟吏。
| Value | Are | Example |
|---|---|---|
| CONTEXT_TYPE_None | pointer左邊或者右邊沒有東西 | [p1]<HTML></HTML>[p2] |
| CONTEXT_TYPE_Text | pointer左邊或者右邊是一個text | tex[p]t |
| CONTEXT_TYPE_EnterScope | 如果是Left，則point左邊是一個End tag玄窝；如果是Right牵寺，pointer的右邊是一個Begin tag 。 | </B>[p]<B> |
| CONTEXT_TYPE_ExitScope | 如果是Left恩脂，則point左邊是一個Begin tag帽氓；如果是Right，pointer的右邊是一個End tag 俩块。 | <B>[p]</B> |
| CONTEXT_TYPE_NoScope | pointer的左邊或者右邊不是一個可以成對的標(biāo)簽 | <BR>[p]<BR> |
- 第四個參數(shù)返回 pointer 左邊或者右邊的element
- 第五個參數(shù)用來限定讀取的text范圍黎休，同時也用來返回獲取的text 的大小
- 第六個參數(shù)返回pointer 左邊或者右邊的 text
下面以具體的頁面舉例說明
[p1]Where [p2]<I>do </I>[p3]<B>you <BR>[p4]want</B> to go today[p5]?
對于頁面上的五個 CMarkupPointer 分別調(diào)用 There()函數(shù)浓领，調(diào)用的參數(shù)及結(jié)果如下表
| Ptr | Derection | Type | Element | cch in | cch out | Text |
|---|---|---|---|---|---|---|
| p1 | left | None | - | - | - | - |
| p1 | right | Text | - | 2 | 2 | Wh |
| p1 | right | Text | - | -1 | 6 | - |
| p1 | right | Text | - | 345 | 6 | Where |
| p2 | left | Text | - | NULL | - | - |
| p2 | right | EnterScope | I |
- | - | - |
| p3 | left | ExitScope | I |
- | - | - |
| p4 | left | NoScope | BR |
- | - | - |
| p5 | left | Text | I |
100 | 12 | NULL |
下面通過實(shí)際的 js 操作來說明 IE 是如何通過 CMarkupPointer 來對流結(jié)構(gòu)進(jìn)行遍歷的
previousSibling，nextSibling奋渔，firstChild镊逝，lastChild
js 中可以通過 Node 的這四個函數(shù)獲取一個 Element 周圍 DOM 的信息，這里以 previousSibling 作為典型來說明嫉鲸，previousSibling 在 IE 8 中的函數(shù)邏輯如下所示
HRESULT CElement::GetpreviousSiblingHelper(CElement *this, CElement **previousSibling)
{
CMarkupPointer * markupPointer;
CDoc* cDoc;
HRESULT result;
cDoc = CElement::Doc(this);
CMarkupPointer::CMarkupPointer(markupPointer, cDoc); // 創(chuàng)建 CMarkupPointer
result = markupPointer->MoveAdjacentToElement( this, ELEMENT_ADJ_BeforeBegin); // 放置 CMarkupPointer
if ( result == S_OK )
{
cDoc = CElement::Doc(this);
result = sub_74D4A0B3(cDoc , markupPointer, &nextSibling); // 通過 CMarkupPointer 獲取 Element
}
result = CBase::SetErrorInfo(markupPointer, result);
CMarkupPointer::~CMarkupPointer(markupPointer);
return result;
}
函數(shù)首先新建一個 CMarkupPointer 對象撑蒜，接著將該 CMarkupPointer 放置于目標(biāo)節(jié)點(diǎn)的 ELEMENT_ADJ_BeforeBegin 位置，而后通過該 CMarkupPointer 來檢查周圍的內(nèi)容玄渗，這里使用 CMarkupPointer::There 函數(shù)來獲取 CMarkupPointer 所指的位置的對應(yīng)節(jié)點(diǎn)信息座菠。邏輯上來說即 Element->_tpBegin->_pLeft->There(left)
nextSibling 、firstChild 藤树、lastChild 其函數(shù)邏輯也大體相同浴滴，有所區(qū)別的即是在調(diào)用 MoveAdjacentToElement 時的傳入?yún)?shù)，分別為 ELEMENT_ADJ_AfterEnd岁钓、ELEMENT_ADJ_AfterBegin升略、ELEMENT_ADJ_BeforeEnd
這里也非常容易理解，以如下頁面流為例子屡限。調(diào)用 div.nextSibling 品嚣，首先使用一個 CMarkupPointer 對象指向在 div 的 ELEMENT_ADJ_AfterEnd位置，即下面頁面中[ae]的位置钧大，再調(diào)用 There 獲取 [ae] 右邊的內(nèi)容翰撑，即為下面頁面中的 <a> 標(biāo)簽，其他同理啊央。
<p></p>[bb]<div>[ab]<image/><input/>[be]</div>[ae]<a></a>
childNodes
childNodes 節(jié)點(diǎn)屬性則是通過 CMarkupPointer 遍歷對應(yīng) Element 節(jié)點(diǎn)而實(shí)現(xiàn)眶诈，在 IE 8 中其主要的功能函數(shù)為 CElement::DOMEnumerateChildren ，該函數(shù)逆向后主要功能代碼如下
CElement::DOMEnumerateChildren(CPtrAry<CTreeNode__> children)
{
cDoc = CElement::Doc(this);
CMarkupPointer::CMarkupPointer(markupPtrBegin, cDoc);
CMarkupPointer::CMarkupPointer(markupPtrEnd, cDoc);
......
result = markupPtrBegin->MoveAdjacentToElement( this, ELEMENT_ADJ_AfterBegin); // 放置 MarkupPointer
result = markupPtrEnd->MoveAdjacentToElement( this, ELEMENT_ADJ_AfterEnd); // 放置 MarkupPointer
do{
......
child = markupPointer->There()
children.Append(child);
result = markupPtrBegin->MoveAdjacentToElement( child, ELEMENT_ADJ_AfterBegin); // 放置 MarkupPointer
......
}while( !markupPtrBegin->isLeftOf(markupPtrEnd) )
......
}
通過兩個 CMarkupPointer 指針分別指向 Element 的開始位置 [ab] 和結(jié)尾位置 [ae]瓜饥，并從其開始位置開始依次遍歷 逝撬，其間所有的節(jié)點(diǎn)均為 Element 的子節(jié)點(diǎn)。
<div>[ab]<p></p><image/><input/><a></a></div>[ae]
四乓土、DOM 流的修改
現(xiàn)代瀏覽器中球拦，為了更好的用戶體驗(yàn)，頁面經(jīng)常需要根據(jù)不同情況動態(tài)進(jìn)行變化帐我，DOM 流也需要相應(yīng)的進(jìn)行修改坎炼。為了提高對于流的訪問效率，IE 瀏覽器采用 Splay tree 來對這個流進(jìn)行操作拦键。SplayTree 雖然名義上稱作 Tree谣光，其實(shí)并不是一個真正意義上樹結(jié)構(gòu)，其本質(zhì)是為了高效操作流結(jié)構(gòu)而產(chǎn)生的一套改進(jìn)算法芬为。
IE 中SpalyTree 的基本數(shù)據(jù)結(jié)構(gòu)為 CTreePos萄金，用于表示流中各數(shù)據(jù)在 SplayTree 中的邏輯關(guān)系蟀悦，再看一遍 CTreePos 的數(shù)據(jù)結(jié)構(gòu)，其_pFirstChild氧敢、_pNext 指針便是用于描述當(dāng)前節(jié)點(diǎn)在 SplayTree 中的邏輯關(guān)系日戈。
class CTreePos
{
public:
DWORD _cElemLeftAndFlags; // 左子樹中的 Begin Element 數(shù)量以及一些與 tag 有關(guān)的屬性
DWORD _cchLeft; // 左子樹中的字符數(shù)量
CTreePos* _pFirstChild; // 指向第一個子節(jié)點(diǎn)
CTreePos* _pNext; // 若當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的最后一個節(jié)點(diǎn)，則該指針指向父節(jié)點(diǎn)孙乖，否則指向兄弟節(jié)點(diǎn)
CTreePos* _pLeft;
CTreePos* _pRight;
}
SplayTree 的主要功能既是在保證流結(jié)構(gòu)順序的情況下浙炼，使得最后訪問的節(jié)點(diǎn)處在樹的最頂層，從而提升訪問效率唯袄。以如下頁面舉例想要在在頁面[p1]弯屈、[p2] 位置插入標(biāo)簽 <p>
<html>[p1]<textarea></textarea>[p2]<html>
首先訪問 [p1] 位置，通過 Splay 操作將 [p1] 所指節(jié)點(diǎn)旋轉(zhuǎn)置樹頂恋拷，此時 SplayTree 如下左樹所示资厉；接著訪問 [p2] 位置，SplayTree 變?yōu)槿缦掠覉D蔬顾，此時針對DOM 的操作只需要發(fā)生在 [p1] 的右子樹上即可
p1 p2
/ \ / \
hh th p1 he
\ / \
te => hh th
\ \
p2 te
\
he
// hh 表示 html tag 的頭結(jié)點(diǎn)宴偿，he表示html tag 的尾節(jié)點(diǎn)。依次類推
SplayTree 的核心函數(shù) Splay() 逆向如下诀豁，部分冗余代碼沒有給出
void CTreePos::Splay(CTreePos * t_node)
{
DWORD t1;
CTreePos *v1;
CTreePos *v2;
CTreePos *v3;
CTreePos *v5;
CTreePos *v6;
CTreePos *v7;
// v2 = t_node->parent->parent
v1 = t_node->Parent();
v2 = v1->Parent();
while (v2) // while grandparent
{
v3 = v2->Parent();
// 如果 v3 沒有（當(dāng)前節(jié)點(diǎn)已經(jīng)旋轉(zhuǎn)到第三層窄刘，沒有曾祖父節(jié)點(diǎn)了）則只進(jìn)行一次單旋；否則進(jìn)行一次之字旋或者一字旋;
if (v3)
{
t1 = t_node->_cElemLeftAndFlags ^ v1->_cElemLeftAndFlags;
if (t1 & TPF_LEFT_CHILD) // 如果 t_node 與其父節(jié)點(diǎn)形成左右且叁、或者右左的關(guān)系， 則進(jìn)行之字形旋轉(zhuǎn)
{
// v3 v3 v3
// / \ / \ / \
// v2 E v2 E t E
// / \ / \ / \
// D v1 => D t => v2 v1
// / \ / \ / \ / \
// t C A v1 D A B C
// / \ / \
// A B B C
v1->CTreePos::RotateUp(t_node, v2); //RotateUp(t_node<eax>,v1<ecx>,v2);
v5 = v2;
}
else // 如果 t_node 與 其父節(jié)點(diǎn)均為左節(jié)點(diǎn)秩伞、或均為右節(jié)點(diǎn)逞带，則進(jìn)行一字型旋轉(zhuǎn)
{
// v3 v3 v3
// / \ / \ / \
// v2 E v1 E t E
// / \ / \ / \
// v1 D => t v2 => A v1
// / \ / \ / \ / \
// t C A B C D B v2
// / \ / \
// A B C D
v2->CTreePos::RotateUp(v1, v3); //RotateUp(v1<eax>,v2<ecx>,v3);
v5 = v1;
}
v6 = v3;
}
else
{
v5 = v1;
v6 = v2;
}
v5->RotateUp(t_node, v6); //RotateUp(t_node<eax>,v5<ecx>,v6);
// v2 = t_node->parent->parent
v1 = t_node->Parent();
v2 = v1->Parent();
}
return;
}
void CTreePos::RotateUp(CTreePos* childNode, CTreePos* parentNode)
{
CTreePos *v1;
CTreePos *v2;
CTreePos *v3;
CTreePos *v4;
CTreePos *v5;
CTreePos *v6;
DWORD v7;
DWORD v8;
if (childNode->IsLeftChild())
{
// 右旋
// this child
// / \ / \
// child c => a this
// / \ / \
// a b b c
//
// 得到 childNode 的左節(jié)點(diǎn) ，通過 v2 指示出來
v1 = childNode->_pFirstChild;
if (v1 && v1->IsLeftChild())
v2 = v1;
else
v2 = NULL
//得到 childNode 的右節(jié)點(diǎn)纱新，通過 v3 表示
v1 = childNode->_pFirstChild;
v3 = 0;
if (v1)
{
if (v1->IsLeftChild())
{
// 如果其左節(jié)點(diǎn)有兄弟節(jié)點(diǎn),則該兄弟節(jié)點(diǎn)為右節(jié)點(diǎn)
if (!v1->IsLastChild())
v3 = v1->_pNext;
}
else
{
v3 = v1;
}
}
//得到 this 的右節(jié)點(diǎn)展氓，通過 v5 表示
v4 = this->_pFirstChild;
v5 = 0;
if (v4)
{
if (v4->IsLeftChild())
{
// 如果其左節(jié)點(diǎn)有兄弟節(jié)點(diǎn),則該兄弟節(jié)點(diǎn)為右節(jié)點(diǎn)
if (!v4->IsLastChild())
v5 = v4->_pNext;
}
else
{
v5 = v4;
}
}
//替換 this 節(jié)點(diǎn)和 childNode 節(jié)點(diǎn)的上下關(guān)系
this->ReplaceChild(childNode, parentNode);
// 如果 childNode 有左節(jié)點(diǎn)，則該節(jié)點(diǎn)為 childNode 的第一個子節(jié)點(diǎn)脸爱，且該節(jié)點(diǎn)的兄弟節(jié)點(diǎn)應(yīng)為 this
// 如果 childNode 沒有左節(jié)點(diǎn)遇汞，則 childNode 的第一個子節(jié)點(diǎn)為 this
if (v2)
{
v2->MarkFirst();
v2->_pNext = this;
}
else
{
childNode->_pFirstChild = this;
}
// 如果 childNode 有右節(jié)點(diǎn)，則 this 節(jié)點(diǎn)的第一個節(jié)點(diǎn)為該節(jié)點(diǎn)
// 如果 childNode 沒有右節(jié)點(diǎn)簿废，則 this 節(jié)點(diǎn)的第一個節(jié)點(diǎn)為其右節(jié)點(diǎn)
if (v3)
{
this->_pFirstChild = v3;
v3->MarkLeft();
// 如果 this 節(jié)點(diǎn)也有右節(jié)點(diǎn)空入，則此節(jié)點(diǎn)為原 childNode 右節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
// 如果 this 節(jié)點(diǎn)沒有右節(jié)點(diǎn)，則此節(jié)點(diǎn)變?yōu)?this 最后一節(jié)點(diǎn)族檬，需要為其設(shè)置父節(jié)點(diǎn)指針
if (v5)
{
v3->MarkFirst();
v3->_pNext = v5;
}
else
{
v3->MarkLast();
v3->_pNext = this;
}
}
else
{
this->_pFirstChild = v5;
}
//this 節(jié)點(diǎn)變?yōu)?childNode 節(jié)點(diǎn)的右節(jié)點(diǎn)歪赢，也即最后一個節(jié)點(diǎn)，將其父節(jié)點(diǎn)指針設(shè)置為 childNode
this->MarkRight();
this->MarkLast();
this->_pNext = childNode;
// 調(diào)整 this 節(jié)點(diǎn)和 childNode 節(jié)點(diǎn)的 subtree num
v7 = ((childNode->_cElemLeftAndFlags >> TPF_FLAGS_SHIFT) << TPF_FLAGS_SHIFT); //GetElemLeft : 清除flag 位的干擾
this->_cElemLeftAndFlags - v7;
this->SetFlag(_cElemLeftAndFlags);
this->_cchLeft = this->_cchLeft - childNode->_cchLeft;
// childNode 節(jié)點(diǎn)
v8 = this->_cchLeft;
if (childNode->IsNode()) // Begin,End
{
if (childNode->IsData2Pos())
{
this->_cchLeft = v8 - 1;
if (childNode->IsBeginNode()) // NodeBeg
this->SetFlag(_cElemLeftAndFlags - 0x100); // ElemLeft 減一
}
}
else if (childNode->IsText())
{
v8 = v8 - (childNode->GetInterNode()->_tpEnd._cchLeft) & 0x3FFFFFFF;
this->_cchLeft = v8;
}
return;
}
else
{
// 左旋
// child this
// / \ / \
// a this => child c
// / \ / \
// b c a b
//代碼總體和右旋差異不大单料，這里不再逆向
}
}
在通過 SplayTree 高效的實(shí)現(xiàn)了 DOM 流的訪問之后埋凯，IE 設(shè)計了一套專門用于操作 DOM 樹的機(jī)制稱為 CSpliceTreeEngine点楼，對于 DOM 流的一系列修改操作均通過它來進(jìn)行。SpliceTreeInternal() 函數(shù)部分功能逆向如下
CMarkup::SpliceTreeInternal( CTreePosGap *tpg_Begin, CTreePosGap *tpg_End, CMarkup* target, CTreePosGap *tpg_tar, DWORD opt1白对，DWORD *opt2)
{
CDoc *v1;
CSpliceTreeEngine v2;
HRESULT result;
v1 = this->Doc();
v2 = CSpliceTreeEngine::CSpliceTreeEngine(v1);
EnsureTotalOrder(tpg1, tpg2);
result = CSpliceTreeEngine::Init(this, tpg_Begin, tpg_End, target, tpg_tar, opt1, opt2);
// ...
case copy:
{
result = v1->CSpliceTreeEngine::RecordSplice();
result = v1->CSpliceTreeEngine::InsertSplice();
}
case move:
{
result = v1->CSpliceTreeEngine::RecordSplice();
result = v1->CSpliceTreeEngine::RemoveSplice();
result = v1->CSpliceTreeEngine::InsertSplice();
}
// ...
CSpliceTreeEngine::~CSpliceTreeEngine(v1);
return result;
}
函數(shù)首先調(diào)用 RecordSplice 函數(shù)將源 DOM 流中的節(jié)點(diǎn)信息備份一遍掠廓，接著根據(jù)操作要求決定是否將源 DOM 流中的節(jié)點(diǎn)信息刪除，最后將之前備份的節(jié)點(diǎn)信息插入目標(biāo) DOM 流中甩恼。
對 DOM 流結(jié)構(gòu)進(jìn)行操作還需要有一個重要的結(jié)構(gòu) CTreePosGap蟀瞧，該結(jié)構(gòu)用于指示兩個 CTreePos 之間的內(nèi)容，在對流進(jìn)行插入和刪除操作時都需要用到 CTreePosGap 結(jié)構(gòu)來指示需要操作的區(qū)間媳拴。CTreePosGap 數(shù)據(jù)結(jié)構(gòu)如下所示
class CTreePosGap{
CElement *_pElemRestrict; // 指定 CTreePosGap 所在的Element范圍
CTreePos *_ptpAttach; // 指示與 CTreePosGap 相關(guān)聯(lián)的 CTreePos
unsigned _fLeft : 1; // 當(dāng)前 Gap 是否在 CTreePos 的左邊
unsigned _eAttach : 2;
unsigned _fMoveLeft : 1;
}
當(dāng)然上述操作均要通過 CMarkupPointer 來作為 DOM 流的指針才能完成黄橘。
通常情況下，一個頁面內(nèi)容被修改之后屈溉， 頁面中的 CMarkupPointer 還會保留在之前未修改時的位置塞关。舉例來說
abc[p1]defg[p2]hij
abc[p1]deXYZfg[p2]hij
當(dāng)?shù)谝粋€頁面被修改為第二個頁面之后，雖然頁面的內(nèi)容發(fā)生了改變子巾，但是 CMarkupPointer 的相對位置仍然保持不變。但如果頁面的修改發(fā)生在 CMarkupPointer 指向的位置线梗，如上例中椰于，向c、d之間插入一個Z仪搔，p 的位置就會出現(xiàn)二義性瘾婿。
abcZ[p1]de or abc[p1]Zde
這時就需要引用另一個重要的概念gravity，每一個 CMarkupPointer 都有一個 gravity 值標(biāo)識著其左偏或右偏烤咧。仍以上述頁面為例
abc[p1,right]defg[p2,left]hij
分別在p1,p2的位置插入一對 <B> 標(biāo)簽偏陪。這時由于gravity的存在，頁面會變成如下
abc<B>[p1,right]defg[p2,left]</B>hij
默認(rèn)情況下 CMarkupPointer 的gravity 值是 left煮嫌。下面的函數(shù)負(fù)責(zé)查看或者修改CMarkupPointer 的 gravity 值
enum POINTER_GRAVITY {
POINTER_GRAVITY_Left,
POINTER_GRAVITY_Right
};
HRESULT Gravity(
POINTER_GRAVITY *pGravityOut
);
HRESULT SetGravity(
POINTER_GRAVITY newGravity
);
再考慮如下例子
[p2]ab[p1]cdxy
當(dāng)bc 段被移動到 xy之間時p1的位置也出現(xiàn)了二義性笛谦，是應(yīng)該隨著bc移動，還是應(yīng)該繼續(xù)保持在原位呢
[p2]a[p1]dxbcy or [p2]adxb[p1]cy
這就需要 cling 的存在昌阿，如果p1指定了cling 屬性饥脑，那么頁面操作之后就會成為右邊所示的情況，否則就會出現(xiàn)左邊所示的情況
cling 和 gravity 可以協(xié)同作用懦冰，考慮下面的例子
a[p1]bcxy
b移動到x灶轰、y之間，如果p1指定了 cling 屬性刷钢，并且 gravity 值為 right框往，那么p1便會跟隨b一起到xy之間。這種情況下如果b被刪除闯捎，那么p1也會跟著從DOM 流中移除椰弊，但并不會銷毀许溅，因?yàn)閜1還有可能重新被使用。cling相關(guān)的函數(shù)秉版，函數(shù)原型如下
HRESULT Cling(
BOOL *pClingOut
);
HRESULT SetCling(
BOOL NewCling
);
下面通過實(shí)際的 js 操作來說明如何對 DOM 流進(jìn)行修改的
appendChild
appendChild 意為在目標(biāo) Element 的最后添加一個子節(jié)點(diǎn)贤重，其內(nèi)部其實(shí)是通過 InsertBefore 來實(shí)現(xiàn)的，
CElement::InsertBeforeHelper()
{
cDoc = CElement::Doc(this);
CMarkupPointer::CMarkupPointer(markupPtr, cDoc);
markupPointer->MoveAdjacentToElement( this, ELEMENT_ADJ_BeforeEnd);
CDoc::InsertElement();
}
函數(shù)首先通過 CMarkupPointer 指定到 parent 的 BeforeEnd 位置清焕，再調(diào)用 CDoc::InsertElement() -> CMarkup::InsertElementInternal 進(jìn)行實(shí)際的插入操作并蝗，一般而言標(biāo)簽都是成對出現(xiàn)的，因此這里需要使用兩個 CMarkupPointer 分別指定新插入標(biāo)簽的 Begin 和 End 位置
HRESULT CMarkup::InsertElementInternal(CMarkup *this, int a2, struct CElement *a3, struct CTreePosGap *a4, struct CTreePosGap *a5, unsigned __int32 a6)
{
CTreePosGap::PartitionPointers(v10, a5, a3, v7);
CTreePosGap::PartitionPointers(v12, v11, a3, v69);
//......
CTreePosGap::SetAttachPreference(((*((_BYTE *)a5 + 8) & 1) == 0) + 1, (int)&v78);
CTreePosGap::MoveTo((CTreePosGap *)&v78, v62);
CTreePosGap::SetAttachPreference(((*((_BYTE *)v11 + 8) & 1) == 0) + 1, (int)&v78);
CTreePosGap::MoveTo((CTreePosGap *)&v75, v16);
//.....
CTreePosGap::MoveTo((CTreePosGap *)&v71, v63);
v69 = (int)CTreePosGap::Branch(v19);
v21 = CTreePosGap::Branch(v20);
//......
if ( CMarkup::SearchBranchForNodeInStory(v22, v21, v62) )
v70 = 1;
v23 = (CTreeNode *)HeapAlloc(g_hProcessHeap, 8u, 0x4Cu);
//......
v25 = CTreeNode::CTreeNode(v23, v66, 0, (int)v62);
//......
CElement::SetMarkupPtr(v24, v62);
CElement::PrivateEnterTree(v26);
//......
v27 = CTreeNode::InitBeginPos(v24, v67 == 0);
CMarkup::Insert(v28, a3, v27);
//......
v30 = CTreePos::GetCpAndMarkup(v29, 0, 0);
//......
v34 = CTreeNode::InitEndPos(v33, v70);
CMarkup::Insert(v35, a3, v34);
CTreePosGap::MoveImpl(v36, (int)&v71, 0, 0);
}
函數(shù)的主要邏輯為秸妥，首先通過一系列的 CTreePosGap 操作滚停，指定 Begin 和 End 的位置；接著新建一個 CTreeNode 并與 Element 關(guān)聯(lián)粥惧。調(diào)用 CTreeNode::InitBeginPos 初始化標(biāo)簽對象的 BeginPos 键畴；接著調(diào)用 CMarkup::Insert 將 BeginPos 插入 DOM 流中，同時也插入 SpalyTree 中突雪，并調(diào)用 CTreePos::GetCpAndMarkup 獲取cp 信息起惕，更新 SpalyTree 結(jié)構(gòu)，同時觸發(fā) Notify 咏删，進(jìn)行響應(yīng)事件的分發(fā)惹想。完成了 BeginPos 的操作之后，對 EndPos 也執(zhí)行相同的操作督函，最終完成功能嘀粱。
replaceNode
replaceNode 用于將 DOM 流中一個節(jié)點(diǎn)替換為另一個節(jié)點(diǎn)，其主要功能函數(shù)我這里顯示不出符號表辰狡，其逆向主要功能代碼如下
HRESULT sub_74D359BA(CDOMTextNode *a1, int a2, int a3, struct CMarkupPointer *a4)
{
// .....
CMarkupPointer::CMarkupPointer(v6, v7);
CMarkupPointer::CMarkupPointer(v8, v7);
result = CElement::GetMarkupPtrRange(v9, (struct CMarkupPointer *)&v15, (struct CMarkupPointer *)&v16, v13);
if ( result == SUCCESS )
v11 = CDoc::Move(v10, (struct CMarkupPointer *)&v15, (struct CMarkupPointer *)&v16, (struct CMarkupPointer *)1, v14);
CMarkupPointer::~CMarkupPointer((CMarkupPointer *)&v16);
CMarkupPointer::~CMarkupPointer((CMarkupPointer *)&v15);
return v11;
}
函數(shù)的主要邏輯為锋叨，通過兩個 CMarkupPointer 指針指定需要替換的目標(biāo)節(jié)點(diǎn)在 DOM 流中的 Begin 和 End 位置，接著調(diào)用 CDoc::Move() 函數(shù)完成功能搓译。CDoc::Move() 則直接通過調(diào)用 CDoc::CutCopyMove 來實(shí)現(xiàn)
HRESULT CDoc::CutCopyMove(CDoc *this, int a2, struct CMarkupPointer *a3, struct CMarkupPointer *a4, struct CMarkupPointer *a5, int a6, DWORD a7)
{
//......
CTreePosGap::MoveTo(v12, TPG_LEFT);
CTreePosGap::MoveTo(v13, TPG_RIGHT);
CTreePosGap::MoveTo(v14, TPG_LEFT);
// ......
if ( v7 )
result = CMarkup::SpliceTreeInternal((CMarkup *)&v19,v15,(struct CTreePosGap *)&v19,(struct CTreePosGap *)&v22,*(struct CMarkup **)(v7 + 28),(struct CTreePosGap *)&v16,(int)a5,a6);
else
result = CMarkup::SpliceTreeInternal((CMarkup *)&v19,v15,(struct CTreePosGap *)&v19,(struct CTreePosGap *)&v22,0,0,(int)a5,a6);
return result;
}
CDoc::CutCopyMove 根據(jù)傳入的 CMarkupPointer 位置信息構(gòu)造三個 CTreePosGap 對象悲柱，并根據(jù)調(diào)用者的要求锋喜，選擇是進(jìn)行 Copy 操作還是 進(jìn)行 Move 操作些己，最終將請求傳遞給 CSpliceTreeEngine。
五嘿般、總結(jié)
IE 的這種 DOM 流結(jié)構(gòu)是由于歷史原因形成的一種特殊情況段标，隨著瀏覽器功能的越來越豐富，這種 DOM 組織方式出現(xiàn)越來越多的問題炉奴。2016 年 10 月份的補(bǔ)丁之后微軟在 Edge 中已經(jīng)拋棄了 DOM 流的設(shè)計逼庞，轉(zhuǎn)而構(gòu)建了一個真正意義上的 DOM 樹。 關(guān)于 Edge 中 DOM 樹的結(jié)構(gòu)將在以后的文檔中再進(jìn)行討論瞻赶。
IE 中與 DOM 相關(guān)的內(nèi)容還有很多赛糟，這里僅僅列出了一點(diǎn)微小的工作派任，還有很多復(fù)雜的結(jié)構(gòu)需要進(jìn)一步分析。
六璧南、Reference
[1] https://msdn.microsoft.com/en-us/library/bb508514(v=vs.85).aspx
