本文主要向大家介绍了机器人之how browsers work---（标准）浏览器工作机制(下)，通过具体的内容向大家展现，希望对大家学习机器人有所帮助。

The tokenization algorithm---标记化算法

The algorithm's output is an HTML token. 算法输出就是一个HTML符记。

The algorithm is expressed as a state machine（状态机）. Each state consumes one or more characters of the input stream and updates the next state according to those characters. The decision is influenced by the current tokenization state and by the tree construction state. This means the same consumed character will yield different results for the correct next state, depending on the current state. The algorithm is too complex to bring fully, so let's see a simple example that will help us understand the principal.![Tokening the example input][1]

构建树算法

When the parser is created the Document object is created.解析器被构建则文档对象被构建。

解析结束后行为

At this stage the browser will mark the document as interactive and start parsing scripts that are in "deferred" mode - those who should be executed after the document is parsed. The document state will be then set to "complete" and a "load" event will be fired.

此阶段，浏览器将文档标记为交互式并解析出于延迟模式的脚本---解析文档之后执行的脚本。而后，文档状态将设置为完成，并触发加载事件

浏览器容错

你从未获取到‘Invalid Syntax错误在html页面，浏览器修理无效内容并继续。

c. CSS解析

the CSS specification defines CSS lexical and syntax grammar .CSS的特点决定了CSS lexical 和语法

webkit CSS 解析器

Webkit uses [Flex and Bison][2] parser generators to create parsers automatically from the CSS grammar files. ![parsing CSS][3]

d. 脚本解析

见js部分

e.脚本及样式处理规则

脚本

The model of the web is synchronous(异步的). Authors expect scripts to be parsed and executed immediately when the parser reaches a <script> tag. The parsing of the document halts until the script was executed. If the script is external then the resource must be first fetched from the network - this is also done synchronously, the parsing halts until the resource is fetched. This was the model for many years and is also specified in HTML 4 and 5 specifications. Authors could mark the script as "defer" and thus it will not halt the document parsing and will execute after it is parsed. HTML5 adds an option to mark the script as asynchronous so it will be parsed and executed by a different thread.

Speculative parsing---推测解析

Both Webkit and Firefox do this optimization. While executing scripts, another thread parses the rest of the document and finds out what other resources need to be loaded from the network and loads them. These way resources can be loaded on parallel connections and the overall speed is better. Note - the speculative parser doesn't modify the DOM tree and leaves that to the main parser, it only parses references to external resources like external scripts, style sheets and images.

Webkit和Firefox都会进行这种优化。 在执行脚本时，另一个线程解析文档的其余部分，并找出需要从网络加载的其他资源并加载它们。 这些方式资源可以并行连接加载，整体速度更好。 注意 - 推测解析器不修改DOM树并将其留给主解析器，它只解析对外部资源的引用，如外部脚本，样式表和图像。

样式

Style sheets on the other hand have a different model. Conceptually it seems that since style sheets don't change the DOM tree, there is no reason to wait for them and stop the document parsing. There is an issue, though, of scripts asking for style information during the document parsing stage. If the style is not loaded and parsed yet, the script will get wrong answers and apparently this caused lots of problems. It seems to be an edge case but is quite common. Firefox blocks all scripts when there is a style sheet that is still being loaded and parsed. Webkit blocks scripts only when they try to access for certain style properties that may be effected by unloaded style sheets.(当存在仍在加载和解析的样式表时，FF会阻止所有脚本；Webkit只在用户视图访问某些可能被卸载的样式表影响的样式属性时阻止脚本)

Render tree---渲染树 构建

While the DOM tree is being constructed, the browser constructs another tree, the render tree. This tree is of visual elements in the order in which they will be displayed.

Firefox calls the elements in the render tree "frames". Webkit uses the term renderer or render object. 

渲染树相对于DOM树

The renderers correspond to the DOM elements, but the relation is not one to one(渲染器与DOM元素对应，但不是一一对应). Non visual DOM elements will not be inserted in the render tree. An example is the "head" element. Also elements whose display attribute was assigned to "none" will not appear in the tree (elements with "hidden" visibility attribute will appear in the tree).![The render tree and the corresponding DOM tree][4]

渲染树构建流

In Firefox, the presentation is registered as a listener for DOM updates. The presentation delegates frame creation to the "FrameConstructor" and the constructor resolves style(see style computation) and creates a frame.

In Webkit the process of resolving the style and creating a renderer is called "attachment". Every DOM node has an "attach" method. Attachment is synchronous, node insertion to the DOM tree calls the new node "attach" method.

火狐的呈现被设置为DOM更新的监听，此呈现代理了frameConstructorframe对frame的构建且此构建解决了样式并创造了frame；Webkit中的解决样式和构建render的过程被称为粘贴，每个DOM节点都有一个粘贴的方法。

Processing the html and body tags results in the construction of the render tree root. The root render object corresponds to what the CSS spec calls the containing block - the top most block that contains all other blocks. Its dimensions are the viewport - the browser window display area dimensions. Firefox calls it ViewPortFrame and Webkit calls it RenderView. This is the render object that the document point to. The rest of the tree is constructed as a DOM nodes insertion. （处理html和body标签导致渲染树根的构造。根渲染对象对于CSS规范调用包含块--包含所有其他块最顶层的块。其尺寸即viewport--浏览器窗口显示区域的尺寸。FF调用其ViewPortFrame和Webkit调用其RenderVIew。）

See CSS2 on this topic - //www.w3.org/TR/CSS21/intro.html#processing-model

样式计算

Style data is a very large construct, holding the numerous style properties, this can cause memory problems.

Finding the matching rules for each element can cause performance issues if it's not optimized. Traversing the entire rule list for each element to find matches is a heavy task. Selectors can have complex structure that can cause the matching process to start on a seemingly promising path that is proven to be futile and another path has to be tried.

For example - this compound selector:

div div div div{

...

}

Means the rules apply to a "<div>" who is the descendant of 3 divs. Suppose you want to check if the rule applies for a given "<div>" element. You choose a certain path up the tree for checking. You may need to traverse the node tree up just to find out there are only two divs and the rule does not apply. You then need to try other paths in the tree.

Applying the rules involves quite complex cascade rules that define the hierarchy of the rules.

Let's see how the browsers face these issues:

a. 共享样式数据

Webkit nodes references style objects (RenderStyle) These objects can be shared by nodes in some conditions. The nodes are siblings or cousins and（webkit节点指样式对象（renderstyle），某些情况下该对象可以为节点所共享。节点是兄弟表关系和）:

1.The elements must be in the same mouse state (e.g., one can't be in :hover while the other isn't).元素必须在一些鼠标状态

2.Neither element should have an id---也不能共用ID

3.The tag names should match---标签名应匹配

4.The class attributes should match---class属性应匹配

5.The set of mapped attributes must be identical---映射属性应匹配

6.The link states must match---链接状态应匹配

7.The focus states must match---焦点状态应匹配

8.Neither element should be affected by attribute selectors, where affected is defined as having any selector match that uses an attribute selector in any position within the selector at all。元素不应受属性选择器影响。

9.There must be no inline style attribute on the elements.元素不能有内联样式。

10.There must be no sibling selectors in use at all. WebCore simply throws a global switch when any sibling selector is encountered and disables style sharing for the entire document when they are present. This includes the + selector and selectors like :first-child and :last-child.必须没有使用同级选择器。

b. FireFox 树规则（有额外的树---规则树和样式文本树，针对更容易的样式计算）

Firefox has two extra trees for easier style computation - the rule tree and style context tree. Webkit also has style objects but they are not stored in a tree like the style context tree, only the DOM node points to its relevant style.![Firefox style context tree][5]

The style contexts contain end values（样式文本包含终值）. The values are computed by applying all the matching rules in the correct order and performing manipulations that transform them from logical to concrete values. For example - if the logical value is percentage of the screen it will be calculated and transformed to absolute units. The rule tree idea is really clever. It enables sharing these values between nodes to avoid computing them again. This also saves space.

All the matched rules are stored in a tree. The bottom nodes in a path have higher priority. The tree contains all the paths for rule matches that were found. Storing the rules is done lazily. The tree isn't calculated at the beginning for every node, but whenever a node style needs to be computed the computed paths are added to the tree.

The idea is to see the tree paths as words in a lexicon. Lets say we already computed this rule tree:

Suppose we need to match rules for another element in the content tree, and find out the matched rules (in the correct order) are B - E - I. 

Division into structs---分成结构

The style contexts are divided into structs(结构体). Those structs contain style information for a certain category like border or color. All the properties in a struct are either inherited or non inherited（所有属性在结构体中要么继承要么非继承）. Inherited properties are properties that unless defined by the element, are inherited from its parent. Non inherited properties (called "reset" properties) use default values if not defined.

The tree helps us by caching entire structs (containing the computed end values) in the tree（此树帮我等缓存所有结构体）. The idea is that if the bottom node didn't supply a definition for a struct, a cached struct in an upper node can be used.

用树规则计算样式文本

When computing the style context for a certain element, we first compute a path in the rule tree or use an existing one. We then begin to apply the rules in the path to fill the structs in our new style context. We start at the bottom node of the path - the one with the highest precedence (usually the most specific selector) and traverse the tree up until our struct is full. If there is no specification for the struct in that rule node, then we can greatly optimize - we go up the tree until we find a node that specifies it fully and simply point to it - that's the best optimization - the entire struct is shared. This saves computation of end values and memory.

If we find partial definitions we go up the tree until the struct is filled.

If we didn't find any definitions for our struct, then in case the struct is an "inherited" type - we point to the struct of our parent in the context tree, in this case we also succeeded in sharing structs. If its a reset struct then default values will be used.

If the most specific node does add values then we need to do some extra calculations for transforming it to actual values. We then cache the result in the tree node so it can be used by children.

The resulting rule tree will look like this (the nodes are marked with the node name : the # of rule they point at):![The rule tree][6]

![The context tree][7]

Suppose we parse the HTML and get to the second <div> tag. We need to create a style context for this node and fill its style structs.

We will match the rules and discover that the matching rules for the <div> are 1 ,2 and 6. This means there is already an existing path in the tree that our element can use and we just need to add another node to it for rule 6 (node F in the rule tree).

We will create a style context and put it in the context tree. The new style context will point to node F in the rule tree.

c. Manipulating the rules for an easy match---操作规则方便匹配

There are several sources for style rules:

CSS rules, either in external style sheets or in style elements.
p {color:blue}
Inline style attributes like
<p style="color:blue" />
HTML visual attributes (which are mapped to relevant style rules)
<p bgcolor="blue" />

The last two are easily matched to the element since he owns the style attributes and HTML attributes can be mapped using the element as the key.(最后两个很容易地匹配到了元素因其拥有样式属性和html可以利用元素作为key去键映射的属性)

d. 正确的瀑布流顺序运用规则

Style sheet cascade order---CSS规则

A declaration for a style property can appear in several style sheets, and several times inside a style sheet. This means the order of applying the rules is very important. This is called the "cascade" order. According to CSS2 spec, the cascade order is (from low to high)级联顺序（由低到高）:

Browser declarations:浏览器声明
User normal declarations：用户正常声明
Author normal declarations：作者正常声明
Author important declarations：作者重要声明
User important declarations：用户重要声明

The browser declarations are least important and the user overrides the author only if the declaration was marked as important. Declarations with the same order will be sorted by specifity and then the order they are specified. The HTML visual attributes are translated to matching CSS declarations . They are treated as author rules with low priority.

种类

选择器特性由CSS2规范定义如下：

如果声明是from是一个'style'属性，而不是一个带选择器的规则，则计数1，否则为0（= a）

计数选择器中的ID属性的数量（= b）

计数选择器中其他属性和伪类的数量（= c）

计数选择器中元素名称和伪元素的数量（= d）

连接四个数字a-b-c-d（在具有大基数的数字系统中）给出特异性。

您需要使用的数字基数由您在某个类别中拥有的最高计数来定义。

例如，如果a = 14，您可以使用十六进制基。 在不太可能的情况下，如果a = 17，您将需要一个17位数字基数。 后面的情况可能发生在这样的选择器：html body div div p ...（17标签在你的选择器..不是很可能）。

Some examples:

*             {}  /* a=0 b=0 c=0 d=0 -> specificity = 0,0,0,0 */
li            {}  /* a=0 b=0 c=0 d=1 -> specificity = 0,0,0,1 */
li:first-line {}  /* a=0 b=0 c=0 d=2 -> specificity = 0,0,0,2 */
ul li         {}  /* a=0 b=0 c=0 d=2 -> specificity = 0,0,0,2 */
ul ol+li      {}  /* a=0 b=0 c=0 d=3 -> specificity = 0,0,0,3 */
h1 + *[rel=up]{}  /* a=0 b=0 c=1 d=1 -> specificity = 0,0,1,1 */
ul ol li.red  {}  /* a=0 b=0 c=1 d=3 -> specificity = 0,0,1,3 */
li.red.level  {}  /* a=0 b=0 c=2 d=1 -> specificity = 0,0,2,1 */
#x34y         {}  /* a=0 b=1 c=0 d=0 -> specificity = 0,1,0,0 */
style=""          /* a=1 b=0 c=0 d=0 -> specificity = 1,0,0,0 */

规则排序

After the rules are matched, they are sorted according to the cascade rules. Webkit uses bubble sort for small lists and merge sort for big ones. Webkit implements sorting by overriding the ">" operator for the rules:

``` static bool operator >(CSSRuleData& r1, CSSRuleData& r2)

{

int spec1 = r1.selector()->specificity();

int spec2 = r2.selector()->specificity();

return (spec1 == spec2) : r1.position() > r2.position() : spec1 > spec2;

}

- Gradual process---渐进过程
Webkit使用标记是否已加载所有顶级样式表（包括@imports）的标志。 如果在附加时样式未完全加载 - 使用占位符并在文档中标记，并且一旦样式表被加载，它们将被重新计算。
6. Layout
- Dirty bit system脏位系统
In order not to do a full layout for every small change, browser use a "dirty bit" system. A renderer that is changed or added marks itself and its children as "dirty" - needing layout.

There are two flags - "dirty" and "children are dirty". Children are dirty means that although the renderer itself may be ok, it has at least one child that needs a layout.
- Global and incremental layout---全局和增量布局![Incremental layout - only dirty renderers and their children are layed out][8]
- Asynchronous and Synchronous layout---异同布渲染
- Optimizations---选择
- The layout process 布局过程
The layout usually has the following pattern:

Parent renderer determines its own width.
Parent goes over children and:
Place the child renderer (sets its x and y).
Calls child layout if needed(they are dirty or we are in a global layout or some other reason) - this calculates the child's height.
Parent uses children accumulative heights and the heights of the margins and paddings to set it own height - this will be used by the parent renderer's parent.
Sets its dirty bit to false.
Firefox uses a "state" object(nsHTMLReflowState) as a parameter to layout (termed "reflow"). Among others the state includes the parents width. 
The output of Firefox layout is a "metrics" object(nsHTMLReflowMetrics). It will contain the renderer computed height.
- Width calculation 宽度计算
- Line breaking 换行
7. Painting---喷涂
- 全局和增量
Like layout, painting can also be global - the entire tree is painted - or incremental. In incremental painting, some of the renderers change in a way that does not affect the entire tree. The changed renderer invalidates it's rectangle on the screen. This causes the OS to see it as a "dirty region" and generate a "paint" event. The OS does it cleverly and coalesces several regions into one. In Chrome it is more complicated because the renderer is in a different process then the main process. Chrome simulates the OS behavior to some extent. The presentation listens to these events and delegates the message to the render root. The tree is traversed until the relevant renderer is reached. It will repaint itself (and usually its children).
- 喷涂规则
The stacking order of a block renderer is:
1.background color
2.background image
3.border
4.children
5.outline
- FF 布局列表
Firefox goes over the render tree and builds a display list for the painted rectangular. It contains the renderers relevant for the rectangular, in the right painting order (backgrounds of the renderers, then borders etc). 
That way the tree needs to be traversed only once for a repaint instead of several times - painting all backgrounds, then all images , then all borders etc. 
Firefox optimizes the process by not adding elements that will be hidden, like elements completely beneath other opaque elements.
- Webkit rectangle storage矩形存储
Before repainting, webkit saves the old rectangle as a bitmap. It then paints only the delta between the new and old rectangles. 
8. 动态改变
The browsers try to do the minimal possible actions in response to a change. So changes to an elements color will cause only repaint of the element. Changes to the element position will cause layout and repaint of the element, its children and possibly siblings. Adding a DOM node will cause layout and repaint of the node. Major changes, like increasing font size of the "html" element, will cause invalidation of caches, relyout and repaint of the entire tree.
9. 渲染引擎线程
- 事件循环
10. CSS2 视觉模型
- canvas
- CSS Box model
![box model][9]
- Positioning scheme---定位方案
- Box types---盒类型
Block box: forms a block - have their own rectangle on the browser window.
Inline box: does not have its own block, but is inside a containing block.
Blocks are formatted vertically one after the other. Inlines are formatted horizontally.![block-inlineBlock][10]
- 定位
a. relative
b. floats
c. absolute and fixed
- Layered representation---分层表现       

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标人工智能智能机器人频道！