4.2.4 DOM
输出的树，也就是解析树，是由DOM元素及属性节点组成的。DOM是文档对象模型的缩写，它是html文档的对象表示，作为html元素的外部接口供js等调用。
树的根是“document”对象。
DOM和标签基本是一一对应的关系，例如，如下的标签：
<html>
<body>
<p<Hello DOM</p>
<div><img src=”example.png” /></div>
</body>
</html>
将会被转换为下面的DOM树：
上图：示例标签对应的DOM树
和html一样，DOM的规范也是由W3C组织制定的。访问http://www.w3.org/DOM/DOMTR，这是使用文档的一般规范。一个模型描述一种特定的html元素，可以在http://www.w3.org/TR/2003/REC-DOM-Level-2-HTML-20030109/idl-definitions.htm 查看html定义。
这里所谓的树包含了DOM节点是说树是由实现了DOM接口的元素构建而成的，浏览器使用已被浏览器内部使用的其他属性的具体实现。
4.2.5 解析算法(The parsing algorithm)
正如前面章节中讨论的，hmtl不能被一般的自顶向下或自底向上的解析器所解析。
原因是：
1. 这门语言本身的宽容特性
2. 浏览器对一些常见的非法html有容错机制
3. 解析过程是往复的，通常源码不会在解析过程中发生改变，但在html中，脚本标签包含的“document.write ”可能添加标签，这说明在解析过程中实际上修改了输入
不能使用正则解析技术，浏览器为html定制了专属的解析器。
Html5规范中描述了这个解析算法，算法包括两个阶段——符号化及构建树。
符号化是词法分析的过程，将输入解析为符号，html的符号包括开始标签、结束标签、属性名及属性值。
符号识别器识别出符号后，将其传递给树构建器，并读取下一个字符，以识别下一个符号，这样直到处理完所有输入。
上图：HTML解析流程
4.2.6 符号识别算法(The tokenization algorithm)
浏览器如何解析html标签，略……
4.2.7 树的构建算法(Tree construction algorithm)
在树的构建阶段，将修改以Document为根的DOM树，将元素附加到树上。每个由符号识别器识别生成的节点将会被树构造器进行处理，规范中定义了每个符号相对应的Dom元素，对应的Dom元素将会被创建。这些元素除了会被添加到Dom树上，还将被添加到开放元素堆栈中。这个堆栈用来纠正嵌套的未匹配和未闭合标签，这个算法也是用状态机来描述，所有的状态采用插入模式。
来看一下示例中树的创建过程：
<html>
<body>
Hello world
</body>
</html>
构建树这一阶段的输入是符号识别阶段生成的符号序列。
首先是“initial mode”，接收到html符号后将转换为“before html”模式，在这个模式中对这个符号进行再处理。此时，创建了一个HTMLHtmlElement元素，并将其附加到根Document对象上。
状态此时变为“before head”，接收到body符号时，即使这里没有head符号，也将自动创建一个HTMLHeadElement元素并附加到树上。
现在，转到“in head”模式，然后是“after head”。到这里，body符号会被再次处理，将创建一个HTMLBodyElement并插入到树中，同时，转移到“in body”模式。
然后，接收到字符串“Hello world”的字符符号，第一个字符将导致创建并插入一个text节点，其他字符将附加到该节点。
接收到body结束符号时，转移到“after body”模式，接着接收到html结束符号，这个符号意味着转移到了“after after body”模式，当接收到文件结束符时，整个解析过程结束。
上图：示例html树的构建过程
4.2.8 解析结束时的处理(Action when the parsing is finished)
在这个阶段，浏览器将文档标记为可交互的，并开始解析处于延时模式中的脚本——这些脚本在文档解析后执行。
文档状态将被设置为完成，同时触发一个load事件。
Html5规范中有符号化及构建树的完整算法(http://www.w3.org/TR/html5/syntax.html#html-parser)。
4.2.9 浏览器容错(Browsers error tolerance)
浏览器如何修复无效内容并继续工作，略……
4.3 CSS解析(CSS parsing)
略……
4.3.1 Webkit CSS 解析器(Webkit CSS parser)
略……
4.4 脚本解析(Parsing scripts)
本章将介绍Javascript。(原作者没写…)
4.5 脚本及样式表的处理顺序(The order of processing scripts and style sheets)
4.5.1 脚本(Scripts)
web的模式是同步的，开发者希望解析到一个script标签时立即解析执行脚本，并阻塞文档的解析直到脚本执行完。如果脚本是外引的，则网络必须先请求到这个资源——这个过程也是同步的，会阻塞文档的解析直到资源被请求到。这个模式保持了很多年，并且在html4及html5中都特别指定了。开发者可以将脚本标识为defer，以使其不阻塞文档解析，并在文档解析结束后执行。Html5增加了标记脚本为异步的选项，以使脚本的解析执行使用另一个线程。
4.5.2 预解析(Speculative parsing)
Webkit和Firefox都做了这个优化，当执行脚本时，另一个线程解析剩下的文档，并加载后面需要通过网络加载的资源。这种方式可以使资源并行加载从而使整体速度更快。需要注意的是，预解析并不改变Dom树，它将这个工作留给主解析过程，自己只解析外部资源的引用，比如外部脚本、样式表及图片。
4.5.3 样式表(Style sheets)
样式表采用另一种不同的模式。理论上，既然样式表不改变Dom树，也就没有必要停下文档的解析等待它们，然而，存在一个问题，脚本可能在文档的解析过程中请求样式信息，如果样式还没有加载和解析，脚本将得到错误的值，显然这将会导致很多问题，这看起来是个边缘情况，但确实很常见。Firefox在存在样式表还在加载和解析时阻塞所有的脚本，而chrome只在当脚本试图访问某些可能被未加载的样式表所影响的特定的样式属性时才阻塞这些脚本。
5.渲染树的构造(Render tree construction)
当Dom树构建完成时，浏览器开始构建另一棵树——渲染树。渲染树由元素显示序列中的可见元素组成，它是文档的可视化表示，构建这棵树是为了以正确的顺序绘制文档内容。
Firefox将渲染树中的元素称为frames，webkit则用renderer或渲染对象来描述这些元素。
一个渲染对象知道如何布局以及绘制自己和它的children。
RenderObject是Webkit的渲染对象基类，它的定义如下：
class RenderObject{
virtual void layout();
virtual void paint(PaintInfo);
virtual void rect repaintRect();
Node* node; //the DOM node
RenderStyle* style; // the computed style
RenderLayer* containgLayer; //the containing z-index layer
}
每个渲染对象用一个和该节点的css盒模型相对应的矩形区域来表示，正如css2所描述的那样，它包含诸如宽、高和位置之类的几何信息。盒模型的类型受该节点相关的display样式属性的影响（参考样式计算章节）。下面的webkit代码说明了如何根据display属性决定某个节点创建何种类型的渲染对象。
RenderObject* RenderObject::createObject(Node* node, RenderStyle* style)
{
Document* doc = node->document();
RenderArena* arena = doc->renderArena();
...
RenderObject* o = 0;
switch (style->display()) {
case NONE:
break;
case INLINE:
o = new (arena) RenderInline(node);
break;
case BLOCK:
o = new (arena) RenderBlock(node);
break;
case INLINE_BLOCK:
o = new (arena) RenderBlock(node);
break;
case LIST_ITEM:
o = new (arena) RenderListItem(node);
break;
...
}
return o;
}
元素的类型也需要考虑，例如，表单控件和表格带有特殊的框架。
在webkit中，如果一个元素想创建一个特殊的渲染对象，它需要复写“createRenderer”方法，使渲染对象指向不包含几何信息的样式对象。
5.1 渲染树和Dom树的关系(The render tree relation to the DOM tree)
渲染对象和Dom元素相对应，但这种对应关系不是一对一的，不可见的Dom元素不会被插入渲染树，例如head元素。另外，display属性为none的元素也不会在渲染树中出现(visibility属性为hidden的元素将出现在渲染树中)。
还有一些Dom元素对应几个可见对象，它们一般是一些具有复杂结构的元素，无法用一个矩形来描述。例如，select元素有三个渲染对象——一个显示区域、一个下拉列表及一个按钮。同样，当文本因为宽度不够而折行时，新行将作为额外的渲染元素被添加。另一个多个渲染对象的例子是不规范的html，根据css规范，一个行内元素只能仅包含行内元素或仅包含块状元素，在存在混合内容时，将会创建匿名的块状渲染对象包裹住行内元素。
一些渲染对象和所对应的Dom节点不在树上相同的位置，例如，浮动和绝对定位的元素在文本流之外，在两棵树上的位置不同，渲染树上标识出真实的结构，并用一个占位结构标识出它们原来的位置。
上图：渲染树及对应的Dom树，”Viewport”是初始内容块. 在Webkit中它是”RenderView”对象.
5.2 创建树的流程(The flow of constructing the tree)
Firefox中，表述为一个监听Dom更新的监听器，将frame的创建委派给Frame Constructor，这个构建器计算样式(参看样式计算)并创建一个frame。
Webkit中，计算样式并生成渲染对象的过程称为attachment，每个Dom节点有一个attach方法，attachment的过程是同步的，调用新节点的attach方法将节点插入到Dom树中。
处理html和body标签将构建渲染树的根，这个根渲染对象对应被css规范称为containing block的元素——包含了其他所有块元素的顶级块元素。它的大小就是viewport——浏览器窗口的显示区域，Firefox称它为viewPortFrame，webkit称为RenderView，这个就是文档所指向的渲染对象，树中其他的部分都将作为一个插入的Dom节点被创建。
5.3 样式计算(Style Computation)
创建渲染树需要计算出每个渲染对象的可视属性，这可以通过计算每个元素的样式属性得到。
样式包括各种来源的样式表，行内样式元素及html中的可视化属性（例如bgcolor），可视化属性转化为css样式属性。
样式表来源于浏览器默认样式表，及页面作者和用户提供的样式表——有些样式是浏览器用户提供的（浏览器允许用户定义喜欢的样式，例如，在Firefox中，可以通过在Firefox Profile目录下放置样式表实现）。
计算样式的一些困难：
- 样式数据是非常大的结构，保存大量的样式属性会带来内存问题。
- 如果不进行优化，找到每个元素匹配的规则会导致性能问题，为每个元素查找匹配的规则都需要遍历整个规则表，这个过程有很大的工作量。选择符可能有复杂的结构，匹配过程如果沿着一条开始看似正确，后来却被证明是无用的路径，则必须去尝试另一条路径。
例如，下面这个复杂选择符div div div div｛…｝
这意味着规则应用到三个div的后代div元素，选择树上一条特定的路径去检查，这可能需要遍历节点树，最后却发现它只是两个div的后代，并不使用该规则，然后则需要沿着另一条路径去尝试
- 应用规则涉及非常复杂的级联，它们定义了规则的层次。
我们来看一下浏览器如何处理这些问题：
5.3.1 共享样式数据(Sharing style data)
webkit节点引用样式对象（渲染样式），某些情况下，这些对象可以被节点间共享，这些节点需要是兄弟或是表兄弟节点，并且：
- 这些元素必须处于相同的鼠标状态(比如不能一个处于hover，而另一个不是)
- 不能有元素具有id
- 标签名必须匹配
- class属性必须匹配
- 对应的属性必须相同
- 链接状态必须匹配
- 焦点状态必须匹配
- 不能有元素被属性选择器影响
- 元素不能有行内样式属性
- 不能有生效的兄弟选择器，webcore在任何兄弟选择器相遇时只是简单的抛出一个全局转换，并且在它们显示时使整个文档的样式共享失效，这些包括＋选择器和类似:first-child和:last-child这样的选择器。
5.3.2 Firefox规则树(Firefox rule tree)
Firefox用两个树用来简化样式计算－规则树和样式上下文树，webkit也有样式对象，但它们并没有存储在类似样式上下文树这样的树中，只是由Dom节点指向其相关的样式。
上图：Firefox样式上下文树
样式上下文包含最终值，这些值是通过以正确顺序应用所有匹配的规则，并将它们由逻辑值转换为具体的值，例如，如果逻辑值为屏幕的百分比，则通过计算将其转化为绝对单位。样式树的使用确实很巧妙，它使得在节点中共享的这些值不需要被多次计算，同时也节省了存储空间。
所有匹配的规则都存储在规则树中，一条路径中的底层节点拥有最高的优先级，这棵树包含了所找到的所有规则匹配的路径（译注：可以取巧理解为每条路径对应一个节点，路径上包含了该节点所匹配的所有规则）。规则树并不是一开始就为所有节点进行计算，而是在某个节点需要计算样式时，才进行相应的计算并将计算后的路径添加到树中。
我们将树上的路径看成辞典中的单词，假如已经计算出了如下的规则树：
假如需要为内容树中的另一个节点匹配规则，现在知道匹配的规则（以正确的顺序）为B-E-I，因为我们已经计算出了路径A-B-E-I-L，所以树上已经存在了这条路径，剩下的工作就很少了。
现在来看一下树如何保存。
5.3.2.1 结构化
样式上下文按结构划分，这些结构包括类似border或color这样的特定分类的样式信息。一个结构中的所有特性不是继承的就是非继承的，对继承的特性，除非元素自身有定义，否则就从它的parent继承。非继承的特性(称为reset特性)如果没有定义，则使用默认的值。
样式上下文树缓存完整的结构（包括计算后的值），这样，如果底层节点没有为一个结构提供定义，则使用上层节点缓存的结构。
5.3.2.2 使用规则树计算样式上下文
当为一个特定的元素计算样式时，首先计算出规则树中的一条路径，或是使用已经存在的一条，然后使用路径中的规则去填充新的样式上下文，从样式的底层节点开始，它具有最高优先级（通常是最特定的选择器），遍历规则树，直到填满结构。如果在那个规则节点没有定义所需的结构规则，则沿着路径向上，直到找到该结构规则。
如果最终没有找到该结构的任何规则定义，那么如果这个结构是继承型的，则找到其在内容树中的parent的结构，这种情况下，我们也成功的共享了结构；如果这个结构是reset型的，则使用默认的值。
如果特定的节点添加了值，那么需要做一些额外的计算以将其转换为实际值，然后在树上的节点缓存该值，使它的children可以使用。
当一个元素和它的一个兄弟元素指向同一个树节点时，完整的样式上下文可以被它们共享。
来看一个例子：假设有下面这段html
<html>
<body>
<div class="err" id="div1">
<p>
this is a <span class="big"> big error </span>
this is also a
<span class="big"> very big error</span> error
</p>
</div>
<div class="err" id="div2">another error</div>
</body>
</html>
以及下面这些规则：
- div {margin:5px;color:black}
- .err {color:red}
- .big {margin-top:3px}
- div span {margin-bottom:4px}
- #div1 {color:blue}
- #div 2 {color:green}
简化下问题，我们只填充两个结构——color和margin，color结构只包含一个成员－颜色，margin结构包含四边。
生成的规则树如下(节点名：指向的规则)
上下文树如下(节点名：指向的规则节点)
假设我们解析html，遇到第二个div标签，我们需要为这个节点创建样式上下文，并填充它的样式结构。
我们进行规则匹配，找到这个div匹配的规则为1、2、6，我们发现规则树上已经存在了一条我们可以使用的路径1、2，我们只需为规则6新增一个节点添加到下面(就是规则树中的F)。
然后创建一个样式上下文并将其放到上下文树中，新的样式上下文将指向规则树中的节点F。
现在我们需要填充这个样式上下文，先从填充margin结构开始，既然最后一个规则节点没有添加margin结构，沿着路径向上，直到找到缓存的前面插入节点计算出的结构，我们发现B是最近的指定margin值的节点。因为已经有了color结构的定义，所以不能使用缓存的结构，既然color只有一个属性，也就不需要沿着路径向上填充其他属性。计算出最终值（将字符串转换为RGB等），并缓存计算后的结构。
第二个span元素更简单，进行规则匹配后发现它指向规则G，和前一个span一样，既然有兄弟节点指向同一个节点，就可以共享完整的样式上下文，只需指向前一个span的上下文。
因为结构中包含继承自parent的规则，上下文树做了缓存(color特性是继承来的，但Firefox将其视为reset并在规则树中缓存)。
例如，如果我们为一个paragraph的文字添加规则：
p {font-family:Verdana;font size:10px;font-weight:bold}
那么这个p在内容树中的子节点div，会共享和它parent一样的font结构，这种情况发生在没有为这个div指定font规则时。
Webkit中，并没有规则树，匹配的声明会被遍历四次，先是应用非important的高优先级属性（之所以先应用这些属性，是因为其他的依赖于它们－比如display），其次是高优先级important的，接着是一般优先级非important的，最后是一般优先级important的规则。这样，出现多次的属性将被按照正确的级联顺序进行处理，最后一个生效。
总结一下，共享样式对象（结构中完整或部分内容）解决了问题1和3，Firefox的规则树帮助以正确的顺序应用规则。
