Zhixingheyi

Where the truth distortion happens.

2011年终总结加2012年计划

时间那是一个飞逝，光阴那是一个荏苒。一转眼，我写博客已经有一年的时间了。期间我的博客也有很大的变化，从最初的独立空间到现在的VPS，从Wordpress变到了Octopress，应该说折腾的不算少，但也乐在其中。

编程经验

今天在整理移动硬盘时发现的一篇收藏的旧文，再次读完后发现写的太好了，基本上涵盖了程序员会碰到的问题，不过可惜的是原文已经找不到了。我觉得把这篇文章作为编程指导更合适，所以记录在这里。

快速排序复习笔记

最近晚上躺在床上没事就拿着手机看了几节MIT的公开课《Introduction to Algorithms》，看着看着就觉得自己关于排序算法的原理基本上都忘光了。顿感非常失落，所以特意又对算法复习了一遍，特别是快速排序，这篇博客就是复习笔记，毕竟发表是最好的记忆嘛。

这门课是由两位老师来上的的，一位是Charles E.Leiserson教授，光听这个名字可能有点陌生，但是如果提到他参与编写的《算法导论》这本书，对于学计算机的人来说那是无人不知无人不晓的经典著作；另一位是80后的Erik DemaineErik Demaine，据说此人在20岁时就当上了MIT的教授，真是牛人啊，而且大多数的课也都是由他来讲的。还有一点我比较在意的是一节课的时间大约是1个小时20分钟左右，这跟中国大学的45分钟一节课很不一样，个人觉得这样的时间安排可以使一节课更加连贯，学习效率也会更好。

浏览器是如何工作的(十)

6 绘制

在绘制阶段会遍历渲染树和调用renderer的paint方法来把他们的内容显示在屏幕上。绘制使用的是UI基础组件。

6.1 全局和增量

像布局一样，可以全局绘(绘制整个渲染树)，也可以是增量绘制。在增量绘制中，一部分renderer的变化不会影响这棵渲染树。变化过的renderer会使它在屏幕上的矩形区域无效，这就会造成OS把它当作“脏区域”(dirty region)并且生成paint事件。OS会聪明地把多个脏区域合并成一个。在Chrome中则更复杂一点，因为renderer不是在主进程中，而是在其他进程中。Chrome模拟OS行为并且扩展它们，表现层监听这些事件而且把消息代理给渲染树的根元素。遍历渲染树直到遇见相关的renderer，渲染树重新绘制自己(经常连同它的孩子节点)。

6.2 绘制顺序

CSS2的规范中规定了绘制的顺序。这个顺序实际上就是元素在上下文中堆积的顺序。因为是从后往前绘制的，所以这个顺序会影响绘制。renderer的堆积顺序是：

  1. background color
  2. background image
  3. border
  4. children
  5. outline

6.3 Firefox的显示列表

Firefox会再次遍历渲染树，然后构造一个已经绘制的矩形区域的显示列表。其中包含矩形区域相关的renderer，从右往左的绘制顺序(背景，边框等)。这种方式只需要遍历一次渲染树就可以重新绘制(所有背景，再所有图片，再所有边框等)。

Firefox通过不把hidden的元素加入到列表中来优化这个过程。

6.4 Webkit的矩形存储

在重新绘制之前，webkit把旧的矩形保存为一个bitmap，然后只重新绘制新旧矩形的不同之处。

浏览器是如何工作的(九)

5 布局

当renderer被创建和加入到树中时，它是没有位置和大小的，计算这两个值称为布局或回流(reflow)。

HTML使用的是基于布局模型的流，这意味着大多数时间内，单一路径下计算几何值是可能的。后进入流的元素不会影响比它先进入流的元素的几何属性值，所以布局文档可以被从左到右，从上到下处理。但是也有例外：比如，HTML的table元素可能需要多条路径。

坐标系统是和根框架相关的，而且使用的是上坐标和左坐标。

布局是一个迭代的过程，它从根renderer(对应于HTML文档的<html>元素)开始。布局迭代部分或整个框架，计算每个renderer的几何信息。

根renderer的位置是0,0，它的范围是viewport(浏览器窗口的可视区域)。所有的renderer都有layout或reflow方法，每个renderer调用需要生成布局的孩子的layout方法。

浏览器是如何工作的(八)

4.3.3 简单规则匹配的例子

样式规则有下面几种：

  • CSS规则，外部表单或style元素

    p {color:blue}

  • 内联style属性

  • HTML的视觉属性(会被映射到相关的样式规则)

浏览器是如何工作的(七)

4.1 渲染树和DOM树的关系

renderer对应于DOM的元素，但并不是一对一的关系。非视觉DOM元素不会被插入渲染树，比如”head”元素。元素的视觉属性是”none”的元素不会出现在树中(视觉属性是”hidden”话会出现在树中)。

DOM元素对应多个视觉对象。一般情况下，复杂结构的元素不能在单个矩形中被描述清楚。比如，select元素有3个renderer：一个是显示区域；一个是下拉框；还有一个是按钮。当文字被分成多行的时候(在一行里显示的宽度不够)，新的行会被作为附加renderer加入到树中。

另一个有许多renderer的例子例子是不完整的HTML。根据CSS规范，内联元素必须包含块元素或着只包含内联元素。为了防止混合的内容，匿名块renderer会被创建来包裹内敛元素。

有些渲染对象对应于DOM节点，但不是在树中的相同位置。浮动元素和绝对固定位置的元素会被放置在树中的不同的位置，而且映射到实际的frame中去，所以它应该是有站位符的frame。

浏览器是如何工作的(六)

3.3 CSS解析

和HTML不同，CSS是内容无关的语法，所以可以被一般解析器解析。CSS规范定义了词法和语法。

让我们来看一些例子：

CSS的文法(词汇)是用正则表达式定义的

1
2
3
4
5
6
7

comment   \/\*[^*]*\*+([^/*][^*]*\*+)*\/
num   [0-9]+|[0-9]*"."[0-9]+
nonascii  [\200-\377]
nmstart   [_a-z]|{nonascii}|{escape}
nmchar    [_a-z0-9-]|{nonascii}|{escape}
name    {nmchar}+
ident   {nmstart}{nmchar}*

ident是identifier的缩写，比如class的名字；name是元素id(#号引用)。

浏览器是如何工作的(五)

3.2.6 标记算法

这个算法的输出是一个HTML标记，它可以用状态机来表示。每个状态消费输入流的一个或多个字符，然后根据这些字符更新下一个状态。状态的更新是由当前标记状态和树构造状态决定的。这意味着根据当前状态，同样的字符会对下一个正确的状态产生不同的结果。这个算法太复杂，所以不能完全描述清楚，所以让我来看一个简单的例子，这个例子会帮助我们理解这个算法。

标记下面的HTML：

1
2
3
4
5

<html>
  <body>
    Hello world
  </body>
</html>

浏览器是如何工作的(四)

3.2 HTML解析器

HTML解析器的工作是把HTML标记语言解析成为解析树。

3.2.1 HTML语法定义

HTML的词汇和语法是由W3C组织制定的。当前的版本是HTML4，HTML5还在制定当中。

3.2.2 不是内容无关语法的HTML

我们在介绍解析的时候知道了，语法可以被定义为正式使用的格式，比如BNF。

不过不幸的是，所有约定的解析器都不适用于HTML。HTML不能简单的定义一个解析器需要的内容无关语法。

有一个定义HTML的正式格式 - DTD，但它也不是内容无关语法。

所以第一眼看上去就很奇怪，HTML更接近于XML。而XML的解析器却有很多，而且有一个HTML的XML版本 - XHTML，那么有什么不同呢？

不同之处在于，HTML的方式更加宽松，它允许你省略特定的标签，然后会隐式的为你加上去。总的来看，相对于XML来说，HTML是“软”语法。

显然，这个细小的差别让两者大不一样。一方面这是HTML流行的主要原因 - 允许你犯错，而且对于开发人员来说非常容易。另一方面，它有使的写一个正式语法变得非常困难。所以总结来看 - HTML不能被简单的解析，不能被约定的解析器解析，因为它不是内容无关语法，也不能被XML解析器解析。