乐趣区

关于前端:让我们来构建一个浏览器引擎吧建议收藏

作者：

jiezi

在

DevUI是一支兼具设计视角和工程视角的团队，服务于华为云DevCloud平台和华为外部数个中后盾零碎，服务于设计师和前端工程师。

官方网站：devui.design

Ng组件库：ng-devui（欢送Star）

官网交换：增加DevUI小助手（devui-official）

DevUIHelper插件：DevUIHelper-LSP（欢送Star）

引言

前端有一个经典的面试题：在浏览器地址栏输出URL到最终呈现出页面，两头产生了什么？

两头有一个过程是获取后盾返回的HTML文本，浏览器渲染引擎将其解析成DOM树，并将HTML中的CSS解析成款式树，而后将DOM树和款式树合并成布局树，并最终由绘图程序绘制到浏览器画板上。

本文通过亲自动手实际，教你一步一步实现一个迷你版浏览器引擎，进而深刻了解渲染引擎的工作原理，干货满满。

次要分成七个局部：

  • 第一局部：开始
  • 第二局部：HTML
  • 第三局部：CSS
  • 第四局部：款式
  • 第五局部：盒子
  • 第六局部：块布局
  • 第七局部：绘制 101

原文写于2014.8.8。

原文地址：https://limpet.net/mbrubeck/2014/08/08/toy-layout-engine-1.html

以下是注释：

第一局部：开始

我正在构建一个“玩具”渲染引擎，我认为你也应该这样做。这是一系列文章中的第一篇。

残缺的系列文章将形容我编写的代码，并向你展现如何编写本人的代码。但首先，让我解释一下起因。

你在造什么？

让咱们谈谈术语。浏览器引擎是web浏览器的一部分，它在“底层”工作，从Internet上获取网页，并将其内容转换成能够浏览、观看、听等模式。Blink、Gecko、WebKit和Trident都是浏览器引擎。相比之下，浏览器自身的用户界面（标签、工具栏、菜单等）被称为chrome。Firefox和SeaMonkey是两个浏览器，应用不同的chrome，但应用雷同的Gecko引擎。

浏览器引擎包含许多子组件：HTTP客户端、HTML解析器、CSS解析器、JavaScript引擎（自身由解析器、解释器和编译器组成）等等。那些波及解析HTML和CSS等web格局，并将其转换成你在屏幕上看到的内容的组件，有时被称为布局引擎或渲染引擎。

为什么是一个“玩具”渲染引擎？

一个功能齐全的浏览器引擎非常复杂。Blink，Gecko，WebKit，它们每一个都有数百万行代码。更年老、更简略的渲染引擎，如Servo和WeasyPrint，也有成千上万行。这对一个老手来说是不容易了解的！

说到非常复杂的软件：如果你加入了编译器或操作系统的课程，在某些时候你可能会创立或批改一个“玩具”编译器或内核。这是一个为学习而设计的简略模型；它可能永远不会由作者以外的任何人治理。然而

制作一个玩具零碎对于理解实在的货色是如何工作的是一个有用的工具。

即便你从未构建过实在的编译器或内核，

理解它们的工作形式也能够帮忙你在编写本人的程序时更好地应用它们。

因而，如果你想成为一名浏览器开发人员，或者只是想理解浏览器引擎外部产生了什么，为什么不构建一个玩具呢？就像实现“真正的”编程语言子集的玩具编译器一样，玩具渲染引擎也能够实现HTML和CSS的一小部分。它不会取代日常浏览器中的引擎，但应该可能阐明出现一个简略HTML文档所需的根本步骤。

在家试试吧。

我心愿我曾经压服你去试一试了。如果你曾经有一些扎实的编程教训并理解一些高级HTML和CSS概念，那么学习本系列将会非常容易。然而，如果你刚刚开始学习这些货色，或者遇到你不了解的货色，请随便问问题，我会尽量让它更分明。

在你开始之前，我想通知你一些你能够做的抉择：

对于编程语言

你能够用任何编程语言构建一个玩具式的布局引擎，真的！用一门你理解和青睐的语言吧。如果这听起来很乏味，你也能够

以此为借口学习一门新语言。

如果你想开始为次要的浏览器引擎（如Gecko或WebKit）做奉献，你可能心愿应用C++，因为C++是这些引擎中应用的次要语言，应用C++能够更容易地将你的代码与它们的代码进行比拟。

我本人的玩具我的项目，robinson，是用Rust写的。我是Mozilla的Servo团队的一员，所以我十分喜爱Rust编程。此外，我创立这个我的项目的指标之一是理解更多的Servo的实现。Robinson有时会应用Servo的简化版本的数据结构和代码。

对于库和捷径

在这样的学习练习中，你必须决定是应用他人的代码，还是从头编写本人的代码。我的倡议是

为你真正想要了解的局部编写你本人的代码，然而不要羞于为其余的局部应用库。

学习如何应用特定的库自身就是一项有价值的练习。

我写robinson不仅仅是为了我本人，也是为了作为这些文章和练习的示例代码。出于这样或那样的起因，我心愿它尽可能地玲珑和独立。到目前为止，除了Rust规范库之外，我没有应用任何内部代码。(这也防止了应用同一版本的Rust来构建多个依赖的小麻烦，而该语言仍在开发中。)不过，这个规定并不是变化无穷的。例如，我当前可能会决定应用图形库，而不是编写本人的低级绘图代码。

另一种防止编写代码的办法是省略一些内容。例如，robinson还没有网络代码；它只能读取本地文件。在一个玩具程序中，如果你想跳过一些货色，你能够跳过。我将在探讨过程中指出相似的潜在捷径，这样你就能够绕过不感兴趣的步骤，间接跳到好的内容。如果你扭转了主见，你能够在当前再补上空白。

第一步：DOM

筹备好写代码了吗？咱们将从一些小的货色开始：DOM的数据结构。让咱们看看robinson的dom模块。

DOM是一个节点树。一个节点有零个或多个子节点。（它还有其余各种属性和办法，但咱们当初能够疏忽其中的大部分。）

struct Node {
  // data common to all nodes:
  children: Vec<Node>,

  // data specific to each node type:
  node_type: NodeType,
}

有多种节点类型，但当初咱们将疏忽其中的大多数，并将节点定义为元素节点或文本节点。在具备继承的语言中，这些是Node的子类型。在Rust中，它们能够是枚举enum（Rust的关键字用于“tagged union”或“sum type”）：

enum NodeType {
  Text(String),
  Element(ElementData),
}

元素包含一个标记名称和任意数量的属性，它们能够存储为从名称到值的映射。Robinson不反对名称空间，所以它只将标记和属性名称存储为简略的字符串。

struct ElementData {
    tag_name: String,
    attributes: AttrMap,
}

type AttrMap = HashMap<String, String>;

最初，一些构造函数使创立新节点变得容易：

fn text(data: String) -> Node {
    Node { children: Vec::new(), node_type: NodeType::Text(data) }
}

fn elem(name: String, attrs: AttrMap, children: Vec<Node>) -> Node {
    Node {
        children: children,
        node_type: NodeType::Element(ElementData {
            tag_name: name,
            attributes: attrs,
        })
    }
}

这是它！一个成熟的DOM实现将蕴含更多的数据和几十个办法，但这就是咱们开始所须要的。

练习

这些只是一些在家能够遵循的倡议。做你感兴趣的练习，跳过不感兴趣的。

  1. 用你抉择的语言启动一个新程序，并编写代码来示意DOM文本节点和元素树。
  2. 装置最新版本的Rust，而后下载并构建robinson。关上dom.rs和扩大NodeType以蕴含其余类型，如正文节点。
  3. 编写代码来丑化DOM节点树。

在下一篇文章中，咱们将增加一个将HTML源代码转换为这些DOM节点树的解析器。

参考文献

无关浏览器引擎内部结构的更多详细信息，请参阅Tali Garsiel十分精彩的浏览器的工作原理及其到更多资源的链接。

例如代码，这里有一个“小型”开源web出现引擎的简短列表。它们大多比robinson大很多倍，但依然比Gecko或WebKit小得多。只有2000行代码的WebWhirr是惟一一个我称之为“玩具”引擎的引擎。

  • CSSBox (Java)
  • Cocktail (Haxe)
  • gngr (Java)
  • litehtml (c++)
  • LURE (Lua)
  • NetSurf (C)
  • Servo (Rust)
  • Simple San Simon (Haskell)
  • WeasyPrint (Python)
  • WebWhirr (C++)

你可能会发现这些有用的灵感或参考。如果你晓得任何其余相似的我的项目，或者如果你开始本人的我的项目，请让我晓得！

第二局部：HTML

这是构建一个玩具浏览器渲染引擎系列文章的第二篇。

本文是对于解析HTML源代码以生成DOM节点树的。解析是一个很吸引人的话题，然而我没有足够的工夫或专业知识来介绍它。你能够从任何对于编译器的优良课程或书籍中取得对于解析的具体介绍。或者通过浏览与你抉择的编程语言一起工作的解析器生成器的文档来取得入手操作的开始。

HTML有本人独特的解析算法。与大多数编程语言和文件格式的解析器不同，HTML解析算法不会回绝有效的输出。相同，它蕴含了特定的错误处理指令，因而web浏览器能够就如何显示每个web页面达成统一，即便是那些不合乎语法规定的页面。Web浏览器必须做到这一点能力应用：因为不符合标准的HTML在Web晚期就失去了反对，所以当初大部分现有Web页面都在应用它。

简略的HTML方言

我甚至没有尝试实现规范的HTML解析算法。相同，我为HTML语法的一小部分编写了一个根本解析器。我的解析器能够解决这样的简略页面：

<html>
    <body>
        <h1>Title</h1>
        <div id="main" class="test">
            <p>Hello <em>world</em>!</p>
        </div>
    </body>
</html>

容许应用以下语法:

  • 闭合的标签：<p>…</p>
  • 带引号的属性：id="main"
  • 文本节点：<em>world</em>

其余所有内容都不反对，包含：

  • 评论
  • Doctype申明
  • 转义字符（如&amp;）和CDATA节
  • 自完结标签：<br/>或<br>没有完结标签
  • 错误处理（例如未闭合或不正确嵌套的标签）
  • 名称空间和其余XHTML语法：<html:body>
  • 字符编码检测

在这个我的项目的每个阶段，我都或多或少地编写了反对前面阶段所需的最小代码。然而如果你想学习更多的解析实践和工具，你能够在你本人的我的项目中更加雄心勃勃！

示例代码

接下来，让咱们回顾一下我的HTML解析器，记住这只是一种办法（而且可能不是最好的办法）。它的构造松散地基于Servo的cssparser库中的tokenizer模块。它没有真正的错误处理；在大多数状况下，它只是在遇到意外的语法时停止。代码是用Rust语言写的，但我心愿它对于应用相似语言（如Java、C++或C#）的人来说具备相当的可读性。它应用了第一局部中的DOM数据结构。

解析器将其输出字符串和以后地位存储在字符串中。地位是咱们还没有解决的下一个字符的索引。

struct Parser {
    pos: usize, // "usize" is an unsigned integer, similar to "size_t" in C
    input: String,
}

咱们能够用它来实现一些简略的办法来窥视输出中的下一个字符：

impl Parser {
    // Read the current character without consuming it.
    fn next_char(&self) -> char {
        self.input[self.pos..].chars().next().unwrap()
    }

    // Do the next characters start with the given string?
    fn starts_with(&self, s: &str) -> bool {
        self.input[self.pos ..].starts_with(s)
    }

    // Return true if all input is consumed.
    fn eof(&self) -> bool {
        self.pos >= self.input.len()
    }

    // ...
}

Rust字符串存储为UTF-8字节数组。要进入下一个字符，咱们不能只后退一个字节。相同，咱们应用char_indices来正确处理多字节字符。（如果咱们的字符串应用固定宽度的字符，咱们能够只将pos加1。）

// Return the current character, and advance self.pos to the next character.
fn consume_char(&mut self) -> char {
    let mut iter = self.input[self.pos..].char_indices();
    let (_, cur_char) = iter.next().unwrap();
    let (next_pos, _) = iter.next().unwrap_or((1, ' '));
    self.pos += next_pos;
    return cur_char;
}

通常咱们想要应用一个间断的字符串。consume_while办法应用满足给定条件的字符，并将它们作为字符串返回。这个办法的参数是一个函数，它承受一个char并返回一个bool值。

// Consume characters until `test` returns false.
fn consume_while<F>(&mut self, test: F) -> String
        where F: Fn(char) -> bool {
    let mut result = String::new();
    while !self.eof() && test(self.next_char()) {
        result.push(self.consume_char());
    }
    return result;
}

咱们能够应用它来疏忽空格字符序列，或者应用字母数字字符串：

// Consume and discard zero or more whitespace characters.
fn consume_whitespace(&mut self) {
    self.consume_while(CharExt::is_whitespace);
}

// Parse a tag or attribute name.
fn parse_tag_name(&mut self) -> String {
    self.consume_while(|c| match c {
        'a'...'z' | 'A'...'Z' | '0'...'9' => true,
        _ => false
    })
}

当初咱们曾经筹备好开始解析HTML了。要解析单个节点，咱们查看它的第一个字符，看它是元素节点还是文本节点。在咱们简化的HTML版本中，文本节点能够蕴含除<之外的任何字符。

// Parse a single node.
fn parse_node(&mut self) -> dom::Node {
    match self.next_char() {
        '<' => self.parse_element(),
        _   => self.parse_text()
    }
}

// Parse a text node.
fn parse_text(&mut self) -> dom::Node {
    dom::text(self.consume_while(|c| c != '<'))
}

一个元素更为简单。它包含开始和完结标签，以及在它们之间任意数量的子节点:

// Parse a single element, including its open tag, contents, and closing tag.
fn parse_element(&mut self) -> dom::Node {
    // Opening tag.
    assert!(self.consume_char() == '<');
    let tag_name = self.parse_tag_name();
    let attrs = self.parse_attributes();
    assert!(self.consume_char() == '>');

    // Contents.
    let children = self.parse_nodes();

    // Closing tag.
    assert!(self.consume_char() == '<');
    assert!(self.consume_char() == '/');
    assert!(self.parse_tag_name() == tag_name);
    assert!(self.consume_char() == '>');

    return dom::elem(tag_name, attrs, children);
}

在咱们简化的语法中，解析属性非常容易。在达到开始标记(>)的开端之前，咱们反复地查找前面跟着=的名称，而后是用引号括起来的字符串。

// Parse a single name="value" pair.
fn parse_attr(&mut self) -> (String, String) {
    let name = self.parse_tag_name();
    assert!(self.consume_char() == '=');
    let value = self.parse_attr_value();
    return (name, value);
}

// Parse a quoted value.
fn parse_attr_value(&mut self) -> String {
    let open_quote = self.consume_char();
    assert!(open_quote == '"' || open_quote == '\'');
    let value = self.consume_while(|c| c != open_quote);
    assert!(self.consume_char() == open_quote);
    return value;
}

// Parse a list of name="value" pairs, separated by whitespace.
fn parse_attributes(&mut self) -> dom::AttrMap {
    let mut attributes = HashMap::new();
    loop {
        self.consume_whitespace();
        if self.next_char() == '>' {
            break;
        }
        let (name, value) = self.parse_attr();
        attributes.insert(name, value);
    }
    return attributes;
}

为了解析子节点，咱们在循环中递归地调用parse_node，直到达到完结标记。这个函数返回一个Vec，这是Rust对可增长数组的名称。

// Parse a sequence of sibling nodes.
fn parse_nodes(&mut self) -> Vec<dom::Node> {
    let mut nodes = Vec::new();
    loop {
        self.consume_whitespace();
        if self.eof() || self.starts_with("</") {
            break;
        }
        nodes.push(self.parse_node());
    }
    return nodes;
}

最初，咱们能够把所有这些放在一起，将整个HTML文档解析成DOM树。如果文档没有显式蕴含根节点，则该函数将为文档创立根节点；这与真正的HTML解析器的性能相似。

// Parse an HTML document and return the root element.
pub fn parse(source: String) -> dom::Node {
    let mut nodes = Parser { pos: 0, input: source }.parse_nodes();

    // If the document contains a root element, just return it. Otherwise, create one.
    if nodes.len() == 1 {
        nodes.swap_remove(0)
    } else {
        dom::elem("html".to_string(), HashMap::new(), nodes)
    }
}

就是这样！robinson HTML解析器的全副代码。整个程序总共只有100多行代码(不包含空白行和正文)。如果你应用一个好的库或解析器生成器，你可能能够在更少的空间中构建一个相似的玩具解析器。

练习

这里有一些你能够本人尝试的代替办法。与后面一样，你能够抉择其中的一个或多个，并疏忽其余。

  1. 构建一个以HTML子集作为输出并生成DOM节点树的解析器(“手动”或应用库或解析器生成器)。
  2. 批改robinson的HTML解析器，增加一些缺失的个性，比方正文。或者用更好的解析器替换它，可能应用库或生成器构建。
  3. 创立一个有效的HTML文件，导致你的(或我的)解析器失败。批改解析器以从谬误中复原，并为测试文件生成DOM树。

捷径

如果想齐全跳过解析，能够通过编程形式构建DOM树，向程序中增加相似这样的代码(伪代码，调整它以匹配第1局部中编写的DOM代码)：

// <html><body>Hello, world!</body></html>
let root = element("html");
let body = element("body");
root.children.push(body);
body.children.push(text("Hello, world!"));

或者你能够找到一个现有的HTML解析器并将其合并到你的程序中。

本系列的下一篇文章将探讨CSS数据结构和解析。

第三局部：CSS

本文是构建玩具浏览器出现引擎系列文章中的第三篇。

本文介绍了用于读取层叠样式表(CSS)的代码。像平常一样，我不会试图涵盖该标准中的所有内容。相同，我尝试实现足以阐明一些概念并为前期渲染管道生成输出的内容。

分析样式表

上面是一个CSS源代码示例：

h1, h2, h3 { margin: auto; color: #cc0000; }
div.note { margin-bottom: 20px; padding: 10px; }
#answer { display: none; }

接下来，我将从我的玩具浏览器引擎robinson中浏览css模块。尽管这些概念能够很容易地转换成其余编程语言，但代码还是用Rust写的。先浏览后面的文章可能会帮忙您了解上面的一些代码。

CSS样式表是一系列规定。(在下面的示例样式表中，每行蕴含一条规定。)

struct Stylesheet {
    rules: Vec<Rule>,
}

一条规定包含一个或多个用逗号分隔的选择器，后跟一系列用大括号括起来的申明。

struct Rule {
    selectors: Vec<Selector>,
    declarations: Vec<Declaration>,
}

一个选择器能够是一个简略的选择器，也能够是一个由组合符连贯的选择器链。Robinson目前只反对简略的选择器。

留神：令人困惑的是，新的Selectors Level 3规范应用雷同的术语来示意略有不同的货色。在本文中，我次要援用CSS2.1。只管过期了，但它是一个有用的终点，因为它更小，更独立(与CSS3相比，CSS3被分成有数相互依赖和CSS2.1的标准)。

在robinson中，一个简略选择器能够包含一个标记名，一个以’#’为前缀的ID，任意数量的以’.’为前缀的类名，或以上几种状况的组合。如果标签名为空或’*’，那么它是一个“通用选择器”，能够匹配任何标签。

还有许多其余类型的选择器(特地是在CSS3中)，但当初这样就能够了。

enum Selector {
    Simple(SimpleSelector),
}

struct SimpleSelector {
    tag_name: Option<String>,
    id: Option<String>,
    class: Vec<String>,
}

申明只是一个名称/值对，由冒号分隔并以分号完结。例如，“margin: auto;”是一个申明。

struct Declaration {
    name: String,
    value: Value,
}

我的玩具引擎只反对CSS泛滥值类型中的一小部分。

enum Value {
    Keyword(String),
    Length(f32, Unit),
    ColorValue(Color),
    // insert more values here
}

enum Unit {
    Px,
    // insert more units here
}

struct Color {
    r: u8,
    g: u8,
    b: u8,
    a: u8,
}

留神：u8是一个8位无符号整数，f32是一个32位浮点数。

不反对所有其余CSS语法，包含@-rules、正文和下面没有提到的任何选择器/值/单元。

解析

CSS有一个规定的语法，这使得它比它乖僻的表亲HTML更容易正确解析。当符合标准的CSS解析器遇到解析谬误时，它会抛弃样式表中无奈辨认的局部，但依然解决其余部分。这是很有用的，因为它容许样式表蕴含新的语法，但在旧的浏览器中依然产生定义良好的输入。

Robinson应用了一个非常简单(齐全不符合标准)的解析器，构建的形式与第2局部中的HTML解析器雷同。我将粘贴一些代码片段，而不是一行一行地反复整个过程。例如，上面是解析单个选择器的代码:

// Parse one simple selector, e.g.: `type#id.class1.class2.class3`
fn parse_simple_selector(&mut self) -> SimpleSelector {
    let mut selector = SimpleSelector { tag_name: None, id: None, class: Vec::new() };
    while !self.eof() {
        match self.next_char() {
            '#' => {
                self.consume_char();
                selector.id = Some(self.parse_identifier());
            }
            '.' => {
                self.consume_char();
                selector.class.push(self.parse_identifier());
            }
            '*' => {
                // universal selector
                self.consume_char();
            }
            c if valid_identifier_char(c) => {
                selector.tag_name = Some(self.parse_identifier());
            }
            _ => break
        }
    }
    return selector;
}

留神没有谬误查看。一些格局不正确的输出，如###或*foo*将胜利解析并产生奇怪的后果。真正的CSS解析器会抛弃这些有效的选择器。

优先级

优先级是渲染引擎在抵触中决定哪一种款式笼罩另一种款式的办法之一。如果一个样式表蕴含两个匹配元素的规定，具备较高优先级的匹配选择器的规定能够笼罩较低优先级的选择器中的值。

选择器的优先级基于它的组件。ID选择器比类选择器优先级更高，类选择器比标签选择器优先级更高。在每个“层级”中，选择器越多优先级越高。

pub type Specificity = (usize, usize, usize);

impl Selector {
    pub fn specificity(&self) -> Specificity {
        // http://www.w3.org/TR/selectors/#specificity
        let Selector::Simple(ref simple) = *self;
        let a = simple.id.iter().count();
        let b = simple.class.len();
        let c = simple.tag_name.iter().count();
        (a, b, c)
    }
}

(如果咱们反对链选择器，咱们能够通过将链各局部的优先级相加来计算链的优先级。)

每个规定的选择器都存储在排序的向量中，优先级最高的优先。这对于匹配十分重要，我将在下一篇文章中介绍。

// Parse a rule set: `<selectors> { <declarations> }`.
fn parse_rule(&mut self) -> Rule {
    Rule {
        selectors: self.parse_selectors(),
        declarations: self.parse_declarations()
    }
}

// Parse a comma-separated list of selectors.
fn parse_selectors(&mut self) -> Vec<Selector> {
    let mut selectors = Vec::new();
    loop {
        selectors.push(Selector::Simple(self.parse_simple_selector()));
        self.consume_whitespace();
        match self.next_char() {
            ',' => { self.consume_char(); self.consume_whitespace(); }
            '{' => break, // start of declarations
            c   => panic!("Unexpected character {} in selector list", c)
        }
    }
    // Return selectors with highest specificity first, for use in matching.
    selectors.sort_by(|a,b| b.specificity().cmp(&a.specificity()));
    return selectors;
}

CSS解析器的其余部分相当简略。你能够在GitHub上浏览全文。如果您在第2局部中还没有这样做，那么当初是尝试解析器生成器的绝佳机会。我的手卷解析器实现了简略示例文件的工作，但它有很多破绽，如果您违反了它的假如，它将重大失败。有一天，我可能会用rust-peg或相似的货色来取代它。

练习

和以前一样，你应该决定你想做哪些练习，并跳过其余的:

  1. 实现您本人的简化CSS解析器和优先级计算。
  2. 扩大robinson的CSS解析器，以反对更多的值，或一个或多个选择器组合符。
  3. 扩大CSS解析器，抛弃任何蕴含解析谬误的申明，并遵循错误处理规定，在申明完结后持续解析。
  4. 让HTML解析器将任何<style>节点的内容传递给CSS解析器，并返回一个文档对象，该对象除了DOM树之外还蕴含一个样式表列表。

捷径

就像在第2局部中一样，您能够通过间接将CSS数据结构硬编码到您的程序中来跳过解析，或者通过应用曾经有解析器的JSON等代替格局来编写它们。

未完待续

下一篇文章将介绍style模块。在这里，所有的所有都开始联合在一起，选择器匹配以将CSS款式利用到DOM节点。

这个系列的进度可能很快就会慢下来，因为这个月晚些时候我会很忙，我甚至还没有为行将发表的一些文章编写代码。我会让他们尽快赶到的！

第四局部：款式

欢送回到我对于构建本人的玩具浏览器引擎的系列文章。

本文将介绍CSS规范所称的为属性值赋值，也就是我所说的款式模块。此模块将DOM节点和CSS规定作为输出，并将它们匹配起来，以确定任何给定节点的每个CSS属性的值。

这部分不蕴含很多代码，因为我没有实现真正简单的局部。然而，我认为剩下的局部依然很乏味，我还将解释一些缺失的局部如何实现。

款式树

robinson的款式模块的输入是我称之为款式树的货色。这棵树中的每个节点都蕴含一个指向DOM节点的指针，以及它的CSS属性值：

// Map from CSS property names to values.
type PropertyMap = HashMap<String, Value>;

// A node with associated style data.
struct StyledNode<'a> {
    node: &'a Node, // pointer to a DOM node
    specified_values: PropertyMap,
    children: Vec<StyledNode<'a>>,
}

这些'a是什么？这些都是生存期，这是Rust如何保障指针是内存平安的，而不须要进行垃圾回收的局部起因。如果你不是在Rust的环境中工作，你能够疏忽它们；它们对代码的意义并不重要。

咱们能够向dom::Node构造增加新的字段，而不是创立一个新的树，但我想让款式代码远离晚期的“教训”。这也让我有机会探讨大多数渲染引擎中的平行树。

浏览器引擎模块通常以一个树作为输出，而后产生一个不同但相干的树作为输入。例如，Gecko的布局代码获取一个DOM树并生成一个框架树，而后应用它来构建一个视图树。Blink和WebKit将DOM树转换为渲染树。所有这些引擎的前期阶段会产生更多的树，包含层树和部件树。

在咱们实现了更多的阶段后，咱们的玩具浏览器引擎的管道将看起来像这样：

在我的实现中，DOM树中的每个节点在款式树中只有一个节点。但在更简单的管道阶段，几个输出节点可能会合成为一个输入节点。或者一个输出节点可能扩大为几个输入节点，或者齐全跳过。例如，款式树能够排除显示属性设置为'none'的元素。(相同，我将在布局阶段删除这些内容，因为这样我的代码会变得更简略一些。)

选择器匹配

构建款式树的第一步是选择器匹配。这将非常容易，因为我的CSS解析器只反对简略的选择器。您能够通过查看元素自身来判断一个简略的选择器是否匹配一个元素。匹配复合选择器须要遍历DOM树以查看元素的兄弟元素、父元素等。

fn matches(elem: &ElementData, selector: &Selector) -> bool {
    match *selector {
        Simple(ref simple_selector) => matches_simple_selector(elem, simple_selector)
    }
}

为了有所帮忙，咱们将向DOM元素类型增加一些不便的ID和类拜访器。class属性能够蕴含多个用空格分隔的类名，咱们在散列表中返回这些类名。

impl ElementData {
    pub fn id(&self) -> Option<&String> {
        self.attributes.get("id")
    }

    pub fn classes(&self) -> HashSet<&str> {
        match self.attributes.get("class") {
            Some(classlist) => classlist.split(' ').collect(),
            None => HashSet::new()
        }
    }
}

要测试一个简略的选择器是否匹配一个元素，只需查看每个选择器组件，如果元素没有匹配的类、ID或标记名，则返回false。

fn matches_simple_selector(elem: &ElementData, selector: &SimpleSelector) -> bool {
    // Check type selector
    if selector.tag_name.iter().any(|name| elem.tag_name != *name) {
        return false;
    }

    // Check ID selector
    if selector.id.iter().any(|id| elem.id() != Some(id)) {
        return false;
    }

    // Check class selectors
    let elem_classes = elem.classes();
    if selector.class.iter().any(|class| !elem_classes.contains(&**class)) {
        return false;
    }

    // We didn't find any non-matching selector components.
    return true;
}

留神：这个函数应用any办法，如果迭代器蕴含一个通过所提供的测试的元素，则该办法返回true。这与Python中的any函数(或Haskell)或JavaScript中的some办法雷同。

构建款式树

接下来，咱们须要遍历DOM树。对于树中的每个元素，咱们将在样式表中搜寻匹配规定。

当比拟两个匹配雷同元素的规定时，咱们须要应用来自每个匹配的最高优先级选择器。因为咱们的CSS解析器存储了从优先级从高下的选择器，所以只有找到了匹配的选择器，咱们就能够进行，并返回它的优先级以及指向规定的指针。

type MatchedRule<'a> = (Specificity, &'a Rule);

// If `rule` matches `elem`, return a `MatchedRule`. Otherwise return `None`.
fn match_rule<'a>(elem: &ElementData, rule: &'a Rule) -> Option<MatchedRule<'a>> {
    // Find the first (highest-specificity) matching selector.
    rule.selectors.iter()
        .find(|selector| matches(elem, *selector))
        .map(|selector| (selector.specificity(), rule))
}

为了找到与一个元素匹配的所有规定，咱们称之为filter_map，它对样式表进行线性扫描，查看每个规定并排除不匹配的规定。真正的浏览器引擎会依据标签名称、id、类等将规定存储在多个散列表中，从而加快速度。

// Find all CSS rules that match the given element.
fn matching_rules<'a>(elem: &ElementData, stylesheet: &'a Stylesheet) -> Vec<MatchedRule<'a>> {
    stylesheet.rules.iter().filter_map(|rule| match_rule(elem, rule)).collect()
}

一旦有了匹配规定，就能够为元素找到指定的值。咱们将每个规定的属性值插入到HashMap中。咱们依据优先级对匹配进行排序，因而在较不特定的规定之后解决更特定的规定，并能够笼罩它们在HashMap中的值。

// Apply styles to a single element, returning the specified values.
fn specified_values(elem: &ElementData, stylesheet: &Stylesheet) -> PropertyMap {
    let mut values = HashMap::new();
    let mut rules = matching_rules(elem, stylesheet);

    // Go through the rules from lowest to highest specificity.
    rules.sort_by(|&(a, _), &(b, _)| a.cmp(&b));
    for (_, rule) in rules {
        for declaration in &rule.declarations {
            values.insert(declaration.name.clone(), declaration.value.clone());
        }
    }
    return values;
}

当初，咱们曾经领有遍历DOM树和构建款式树所需的所有。留神，选择器匹配只对元素无效，因而文本节点的指定值只是一个空映射。

// Apply a stylesheet to an entire DOM tree, returning a StyledNode tree.
pub fn style_tree<'a>(root: &'a Node, stylesheet: &'a Stylesheet) -> StyledNode<'a> {
    StyledNode {
        node: root,
        specified_values: match root.node_type {
            Element(ref elem) => specified_values(elem, stylesheet),
            Text(_) => HashMap::new()
        },
        children: root.children.iter().map(|child| style_tree(child, stylesheet)).collect(),
    }
}

这就是robinson构建款式树的全副代码。接下来我将探讨一些显著的脱漏。

级联

由web页面的作者提供的样式表称为作者样式表。除此之外，浏览器还通过用户代理样式表提供默认款式。它们可能容许用户通过用户样式表(如Gecko的userContent.css)增加自定义款式。

级联定义这三个“起源”中哪个优先于另一个。级联有6个级别:一个用于每个起源的“失常”申明，另一个用于每个起源的!important申明。

Robinson的格调代码没有实现级联；它只须要一个样式表。短少默认样式表意味着HTML元素将不具备任何您可能冀望的默认款式。例如，<head>元素的内容不会被暗藏，除非你显式地把这个规定增加到你的样式表中：

head { display: none; }

实现级联应该相当简略：只需跟踪每个规定的起源，并依据起源和重要性以及特殊性对申明进行排序。一个简化的、两级的级联应该足以反对最常见的状况：普通用户代理款式和一般作者款式。

计算的值

除了下面提到的“指定值”之外，CSS还定义了初始值、计算值、应用值和理论值。

初始值是没有在级联中指定的属性的默认值。计算值基于指定值，但可能利用一些特定于属性的规范化规定。

依据CSS标准中的定义，正确实现这些须要为每个属性独自编写代码。对于一个实在的浏览器引擎来说，这项工作是必要的，但我心愿在这个玩具我的项目中防止它。在前面的阶段，当指定的值缺失时，应用这些值的代码将(某种程度上)通过应用默认值模仿初始值。

应用值和理论值是在布局期间和之后计算的，我将在当前的文章中介绍。

继承

如果文本节点不能匹配选择器，它们如何取得色彩、字体和其余款式？答案是继承。

当属性被继承时，任何没有级联值的节点都将接管该属性的父节点值。有些属性，如'color'，是默认继承的；其余仅当级联指定非凡值“inherit”时应用。

我的代码不反对继承。要实现它，能够将父类的款式数据传递到specified_values函数，并应用硬编码的查找表来决定应该继承哪些属性。

款式属性

任何HTML元素都能够蕴含一个蕴含CSS申明列表的款式属性。没有选择器，因为这些申明主动只利用于元素自身。

<span style="color: red; background: yellow;">

如果您想要反对style属性，请应用specified_values函数查看该属性。如果存在该属性，则将其从CSS解析器传递给parse_declarations。在一般的作者申明之后利用后果申明，因为属性比任何CSS选择器都更特定。

练习

除了编写本人的选择器匹配和值赋值代码之外，你还能够在本人的我的项目或robinson的分支中实现下面探讨的一个或多个缺失的局部:

  1. 级联
  2. 初始值和/或计算值
  3. 继承
  4. 款式属性

另外，如果您从第3局部扩大了CSS解析器以蕴含复合选择器，那么当初能够实现对这些复合选择器的匹配。

未完待续

第5局部将介绍布局模块。我还没有实现代码，所以在我开始写这篇文章之前还会有另一个提早。我打算将布局分成至多两篇文章(一篇是块布局，一篇可能是内联布局)。

与此同时，我心愿看到您依据这些文章或练习创立的任何货色。如果你的代码在某个中央，请在上面增加一个链接！到目前为止，我曾经看到了Martin Tomasi的Java实现和Pohl longsin的Swift版本。

第5局部：盒子

这是对于编写一个简略的HTML渲染引擎的系列文章中的第5篇。

本文将开始布局模块，该模块获取款式树并将其转换为二维空间中的一堆矩形。这是一个很大的模块，所以我将把它分成几篇文章。另外，在我为前面的局部编写代码时，我在本文中分享的一些代码可能须要更改。

布局模块的输出是第4局部中的款式树，它的输入是另一棵树，即布局树。这使咱们的迷你渲染管道更进一步：

我将从根本的HTML/CSS布局模型开始探讨。如果您已经学习过如何开发web页面，那么您可能曾经相熟了这一点，然而从实现者的角度来看，它可能有点不同。

盒模型

布局就是方框。方框是网页的一个矩形局部。它具备页面上的宽度、高度和地位。这个矩形称为内容区域，因为它是框的内容绘制的中央。内容能够是文本、图像、视频或其余框。

框还能够在其内容区域四周有内边距、边框和边距。CSS标准中有一个图表显示所有这些层是如何组合在一起的。

Robinson将盒子的内容区域和四周区域存储在上面的构造中。[Rust注:f32是32位浮点型。]

// CSS box model. All sizes are in px.

struct Dimensions {
    // Position of the content area relative to the document origin:
    content: Rect,

    // Surrounding edges:
    padding: EdgeSizes,
    border: EdgeSizes,
    margin: EdgeSizes,
}

struct Rect {
    x: f32,
    y: f32,
    width: f32,
    height: f32,
}

struct EdgeSizes {
    left: f32,
    right: f32,
    top: f32,
    bottom: f32,
}

块和内联布局

留神:这部分蕴含的图表如果没有相干的视觉款式，就没有意义。如果您是在一个提要阅读器中浏览这篇文章，尝试在一个惯例的浏览器选项卡中关上原始页面。我还为应用屏幕阅读器或其余辅助技术的读者提供了文本形容。

CSS display属性决定一个元素生成哪种类型的框。CSS定义了几种框类型，每种都有本人的布局规定。我只讲其中的两种:块和内联。

我将应用这一点伪html来阐明区别:

<container>
  <a></a>
  <b></b>
  <c></c>
  <d></d>
</container>

块级框从上到下垂直地搁置在容器中。

a, b, c, d { display: block; }

行内框从左到右程度地搁置在容器中。如果它们达到了容器的右边缘，它们将盘绕并持续在上面的新行。

a, b, c, d { display: inline; }

每个框必须只蕴含块级子元素或行内子元素。当DOM元素蕴含块级子元素和内联子元素时，布局引擎会插入匿名框来分隔这两种类型。(这些框是“匿名的”，因为它们与DOM树中的节点没有关联。)

在这个例子中，内联框b和c被一个匿名块框突围，粉红色显示:

a    { display: block; }
b, c { display: inline; }
d    { display: block; }

留神，内容默认垂直增长。也就是说，向容器中增加子元素通常会使容器更高，而不是更宽。另一种说法是，默认状况下，块或行的宽度取决于其容器的宽度，而容器的高度取决于其子容器的高度。

如果你笼罩了属性的默认值，比方宽度和高度，这将变得更加简单，如果你想要反对像垂直书写这样的个性，这将变得更加简单。

布局树

布局树是一个框的汇合。一个盒子有尺寸，它可能蕴含子盒子。

struct LayoutBox<'a> {
    dimensions: Dimensions,
    box_type: BoxType<'a>,
    children: Vec<LayoutBox<'a>>,
}

框能够是块节点、内联节点或匿名块框。(当我实现文本布局时，这须要扭转，因为行换行会导致一个内联节点被宰割成多个框。但当初就能够了。)

enum BoxType<'a> {
    BlockNode(&'a StyledNode<'a>),
    InlineNode(&'a StyledNode<'a>),
    AnonymousBlock,
}

要构建布局树，咱们须要查看每个DOM节点的display属性。我向style模块增加了一些代码，以获取节点的显示值。如果没有指定值，则返回初始值’inline’。

enum Display {
    Inline,
    Block,
    None,
}

impl StyledNode {
    // Return the specified value of a property if it exists, otherwise `None`.
    fn value(&self, name: &str) -> Option<Value> {
        self.specified_values.get(name).map(|v| v.clone())
    }

    // The value of the `display` property (defaults to inline).
    fn display(&self) -> Display {
        match self.value("display") {
            Some(Keyword(s)) => match &*s {
                "block" => Display::Block,
                "none" => Display::None,
                _ => Display::Inline
            },
            _ => Display::Inline
        }
    }
}

当初咱们能够遍历款式树，为每个节点构建一个LayoutBox，而后为节点的子节点插入框。如果一个节点的display属性被设置为’none’，那么它就不蕴含在布局树中。

// Build the tree of LayoutBoxes, but don't perform any layout calculations yet.
fn build_layout_tree<'a>(style_node: &'a StyledNode<'a>) -> LayoutBox<'a> {
    // Create the root box.
    let mut root = LayoutBox::new(match style_node.display() {
        Block => BlockNode(style_node),
        Inline => InlineNode(style_node),
        DisplayNone => panic!("Root node has display: none.")
    });

    // Create the descendant boxes.
    for child in &style_node.children {
        match child.display() {
            Block => root.children.push(build_layout_tree(child)),
            Inline => root.get_inline_container().children.push(build_layout_tree(child)),
            DisplayNone => {} // Skip nodes with `display: none;`
        }
    }
    return root;
}

impl LayoutBox {
    // Constructor function
    fn new(box_type: BoxType) -> LayoutBox {
        LayoutBox {
            box_type: box_type,
            dimensions: Default::default(), // initially set all fields to 0.0
            children: Vec::new(),
        }
    }
    // ...
}

如果块节点蕴含内联子节点，则创立一个匿名块框来蕴含它。如果一行中有几个内联子元素，则将它们都放在同一个匿名容器中。

// Where a new inline child should go.
fn get_inline_container(&mut self) -> &mut LayoutBox {
    match self.box_type {
        InlineNode(_) | AnonymousBlock => self,
        BlockNode(_) => {
            // If we've just generated an anonymous block box, keep using it.
            // Otherwise, create a new one.
            match self.children.last() {
                Some(&LayoutBox { box_type: AnonymousBlock,..}) => {}
                _ => self.children.push(LayoutBox::new(AnonymousBlock))
            }
            self.children.last_mut().unwrap()
        }
    }
}

这是无意从规范CSS框生成算法的多种形式简化的。例如，它不解决内联框蕴含块级子框的状况。此外，如果块级节点只有内联子节点，则会生成一个不必要的匿名框。

未完待续

哇，比我设想的要长。我想我就讲到这里，然而不要放心：第6局部很快就会到来，它将探讨块级布局。

一旦块布局实现，咱们就能够跳转到管道的下一个阶段：绘制！我想我可能会这么做，因为这样咱们最终能够看到渲染引擎的输入是丑陋的图片而不是数字。

然而，这些图片将只是一堆黑白的矩形，除非咱们通过实现内联布局和文本布局来实现布局模块。如果我在开始绘画之前没有实现这些，我心愿之后再回到它们上来。

第六局部：块布局

欢送回到我对于构建一个玩具HTML渲染引擎的系列文章，这是系列文章的第6篇。

本文将持续咱们在第5局部中开始的布局模块。这一次，咱们将增加布局块框的性能。这些框是垂直重叠的，比方题目和段落。

为了简略起见，这段代码只实现了失常流：没有浮动，没有相对定位，也没有固定定位。

遍历布局树

该代码的入口点是layout函数，它承受一个LayoutBox并计算其尺寸。咱们将把这个函数分为三种状况，目前只实现其中一种：

impl LayoutBox {
    // Lay out a box and its descendants.
    fn layout(&mut self, containing_block: Dimensions) {
        match self.box_type {
            BlockNode(_) => self.layout_block(containing_block),
            InlineNode(_) => {} // TODO
            AnonymousBlock => {} // TODO
        }
    }

    // ...
}

一个块的布局取决于它所蕴含块的尺寸。对于失常流中的块框，这只是框的父。对于根元素，它是浏览器窗口(或“视口”)的大小。

您可能还记得在前一篇文章中，一个块的宽度取决于它的父块，而它的高度取决于它的子块。这意味着咱们的代码在计算宽度时须要自顶向下遍历树，因而它能够在父类的宽度已知之后布局子类，并自底向上遍历以计算高度，因而父类的高度在其子类的高度之后计算。

fn layout_block(&mut self, containing_block: Dimensions) {
    // Child width can depend on parent width, so we need to calculate
    // this box's width before laying out its children.
    self.calculate_block_width(containing_block);

    // Determine where the box is located within its container.
    self.calculate_block_position(containing_block);

    // Recursively lay out the children of this box.
    self.layout_block_children();

    // Parent height can depend on child height, so `calculate_height`
    // must be called *after* the children are laid out.
    self.calculate_block_height();
}

该函数对布局树执行一次遍历，向下时进行宽度计算，向上时进行高度计算。一个真正的布局引擎可能会执行几次树遍历，一些是自顶向下，一些是自底向上。

计算宽度

宽度计算是块布局函数的第一步，也是最简单的一步。我要一步一步来。首先，咱们须要CSS宽度属性的值和所有左右边的大小:

fn calculate_block_width(&mut self, containing_block: Dimensions) {
    let style = self.get_style_node();

    // `width` has initial value `auto`.
    let auto = Keyword("auto".to_string());
    let mut width = style.value("width").unwrap_or(auto.clone());

    // margin, border, and padding have initial value 0.
    let zero = Length(0.0, Px);

    let mut margin_left = style.lookup("margin-left", "margin", &zero);
    let mut margin_right = style.lookup("margin-right", "margin", &zero);

    let border_left = style.lookup("border-left-width", "border-width", &zero);
    let border_right = style.lookup("border-right-width", "border-width", &zero);

    let padding_left = style.lookup("padding-left", "padding", &zero);
    let padding_right = style.lookup("padding-right", "padding", &zero);

    // ...
}

这应用了一个名为lookup的助手函数，它只是按程序尝试一系列值。如果第一个属性没有设置，它将尝试第二个属性。如果没有设置，它将返回给定的默认值。这提供了一个不残缺(但简略)的简写属性和初始值实现。

留神:这相似于JavaScript或Ruby中的以下代码:

margin_left = style["margin-left"] || style["margin"] || zero;

因为子对象不能扭转父对象的宽度，所以它须要确保本人的宽度与父对象的宽度相符。CSS标准将其表白为一组束缚和解决它们的算法。上面的代码实现了该算法。

首先，咱们将边距、内边距、边框和内容宽度相加。to_px帮忙器办法将长度转换为它们的数值。如果一个属性被设置为’auto’，它会返回0，因而它不会影响和。

let total = [&margin_left, &margin_right, &border_left, &border_right,
             &padding_left, &padding_right, &width].iter().map(|v| v.to_px()).sum();

这是盒子所须要的最小程度空间。如果它不等于容器的宽度，咱们须要调整一些货色使它相等。

如果宽度或边距设置为“auto”，它们能够扩大或膨胀以适应可用的空间。依照说明书，咱们首先查看盒子是否太大。如果是这样，咱们将任何可扩大边距设置为零。

// If width is not auto and the total is wider than the container, treat auto margins as 0.
if width != auto && total > containing_block.content.width {
    if margin_left == auto {
        margin_left = Length(0.0, Px);
    }
    if margin_right == auto {
        margin_right = Length(0.0, Px);
    }
}

如果盒子对容器来说太大，就会溢出容器。如果太小，它就会下泄，留下额定的空间。咱们将计算下溢量，即容器内残余空间的大小。(如果这个数字是正数，它实际上是一个溢出。)

let underflow = containing_block.content.width - total;

咱们当初遵循标准的算法，通过调整可扩大的尺寸来打消任何溢出或下溢。如果没有“主动”尺寸，咱们调整左边的边距。(是的，这意味着在溢出的状况下，边界可能是负的!)

match (width == auto, margin_left == auto, margin_right == auto) {
    // If the values are overconstrained, calculate margin_right.
    (false, false, false) => {
        margin_right = Length(margin_right.to_px() + underflow, Px);
    }

    // If exactly one size is auto, its used value follows from the equality.
    (false, false, true) => { margin_right = Length(underflow, Px); }
    (false, true, false) => { margin_left  = Length(underflow, Px); }

    // If width is set to auto, any other auto values become 0.
    (true, _, _) => {
        if margin_left == auto { margin_left = Length(0.0, Px); }
        if margin_right == auto { margin_right = Length(0.0, Px); }

        if underflow >= 0.0 {
            // Expand width to fill the underflow.
            width = Length(underflow, Px);
        } else {
            // Width can't be negative. Adjust the right margin instead.
            width = Length(0.0, Px);
            margin_right = Length(margin_right.to_px() + underflow, Px);
        }
    }

    // If margin-left and margin-right are both auto, their used values are equal.
    (false, true, true) => {
        margin_left = Length(underflow / 2.0, Px);
        margin_right = Length(underflow / 2.0, Px);
    }
}

此时，束缚曾经满足，任何’auto’值都曾经转换为长度。后果是程度框尺寸的应用值，咱们将把它存储在布局树中。你能够在layout.rs中看到最终的代码。

定位

下一步比较简单。这个函数查找残余的边距/内边距/边框款式，并应用这些款式和蕴含的块尺寸来确定这个块在页面上的地位。

fn calculate_block_position(&mut self, containing_block: Dimensions) {
    let style = self.get_style_node();
    let d = &mut self.dimensions;

    // margin, border, and padding have initial value 0.
    let zero = Length(0.0, Px);

    // If margin-top or margin-bottom is `auto`, the used value is zero.
    d.margin.top = style.lookup("margin-top", "margin", &zero).to_px();
    d.margin.bottom = style.lookup("margin-bottom", "margin", &zero).to_px();

    d.border.top = style.lookup("border-top-width", "border-width", &zero).to_px();
    d.border.bottom = style.lookup("border-bottom-width", "border-width", &zero).to_px();

    d.padding.top = style.lookup("padding-top", "padding", &zero).to_px();
    d.padding.bottom = style.lookup("padding-bottom", "padding", &zero).to_px();

    d.content.x = containing_block.content.x +
                  d.margin.left + d.border.left + d.padding.left;

    // Position the box below all the previous boxes in the container.
    d.content.y = containing_block.content.height + containing_block.content.y +
                  d.margin.top + d.border.top + d.padding.top;
}

认真看看最初一条语句，它设置了y的地位。这就是为什么块布局具备独特的垂直重叠行为。为了实现这一点，咱们须要确保父节点的内容。高度在布局每个子元素后更新。

子元素

上面是递归布局框内容的代码。当它循环遍历子框时，它会跟踪总内容高度。定位代码(下面)应用这个函数来查找下一个子元素的垂直地位。

fn layout_block_children(&mut self) {
    let d = &mut self.dimensions;
    for child in &mut self.children {
        child.layout(*d);
        // Track the height so each child is laid out below the previous content.
        d.content.height = d.content.height + child.dimensions.margin_box().height;
    }
}

每个子节点占用的总垂直空间是其边距框的高度，咱们是这样计算的:

impl Dimensions {
    // The area covered by the content area plus its padding.
    fn padding_box(self) -> Rect {
        self.content.expanded_by(self.padding)
    }
    // The area covered by the content area plus padding and borders.
    fn border_box(self) -> Rect {
        self.padding_box().expanded_by(self.border)
    }
    // The area covered by the content area plus padding, borders, and margin.
    fn margin_box(self) -> Rect {
        self.border_box().expanded_by(self.margin)
    }
}

impl Rect {
    fn expanded_by(self, edge: EdgeSizes) -> Rect {
        Rect {
            x: self.x - edge.left,
            y: self.y - edge.top,
            width: self.width + edge.left + edge.right,
            height: self.height + edge.top + edge.bottom,
        }
    }
}

为简略起见，这里没有实现边距折叠。一个真正的布局引擎会容许一个框的底部边缘与下一个框的顶部边缘重叠，而不是每个框都齐全放在前一个框的上面。

“高度”属性

默认状况下，框的高度等于其内容的高度。但如果’height’属性被显式设置为长度，咱们将应用它来代替:

fn calculate_block_height(&mut self) {
    // If the height is set to an explicit length, use that exact length.
    // Otherwise, just keep the value set by `layout_block_children`.
    if let Some(Length(h, Px)) = self.get_style_node().value("height") {
        self.dimensions.content.height = h;
    }
}

这就是块布局算法。当初你能够在一个HTML文档上调用layout()，它会生成一堆矩形，包含宽度、高度、边距等。很酷,对吧?

练习

对于雄心勃勃的实现者，一些额定的想法：

  1. 解体的垂直边缘。
  2. 绝对定位。
  3. 并行化布局过程，并测量对性能的影响。

如果您尝试并行化我的项目，您可能想要将宽度计算和高度计算拆散为两个不同的通道。通过为每个子工作生成一个独自的工作，从上至下遍历宽度很容易并行化。高度的计算要略微简单一些，因为您须要返回并在每个子元素被布局之后调整它们的y地位。

未完待续

感激所有追随我走到这一步的人！

随着我深刻到布局和渲染的生疏畛域，这些文章的编写工夫越来越长。在我试验字体和图形代码的下一部分之前，会有一段较长的工夫中断，但我会尽快恢复这个系列。

更新：第7局部当初筹备好了。

第七局部：绘制 101

欢送回到我的对于构建一个简略HTML渲染引擎的系列，这是第7篇，也是最初一篇。

在这篇文章中，我将增加十分根本的绘画代码。这段代码从布局模块中获取框树，并将它们转换为像素数组。这个过程也称为“栅格化”。

浏览器通常在Skia、Cairo、Direct2D等图形api和库的帮忙下实现光栅化。这些api提供了绘制多边形、直线、曲线、突变和文本的函数。当初，我将编写我本人的光栅化程序，它只能绘制一种货色:矩形。

最初我想实现文本渲染。在这一点上，我可能会摈弃这个玩具绘画代码，转而应用“真正的”2D图形库。但就目前而言，矩形足以将我的块布局算法的输入转换为图片。

迎头赶上

从上一篇文章开始，我对以前文章中的代码做了一些小的批改。这包含一些小的重构，以及一些更新，以放弃代码与最新的Rust夜间构建兼容。这些更改对了解代码都不是至关重要的，然而如果您好奇的话，能够查看提交历史记录。

构建显示列表

在绘制之前，咱们将遍历布局树并构建一个显示列表。这是一个图形操作列表，如“绘制圆圈”或“绘制文本字符串”。或者在咱们的例子中，只是“画一个矩形”。

为什么要将命令放入显示列表中，而不是立刻执行它们?显示列表之所以有用有几个起因。你能够通过搜寻来找到被前期操作齐全覆盖的物品，并将其移除，以打消节约的油漆。在只晓得某些项产生了更改的状况下，能够批改和重用显示列表。您能够应用雷同的显示列表生成不同类型的输入:例如，用于在屏幕上显示的像素，或用于发送到打印机的矢量图形。

Robinson的显示列表是显示命令的向量。目前，只有一种类型的DisplayCommand，一个纯色矩形:

type DisplayList = Vec<DisplayCommand>;

enum DisplayCommand {
    SolidColor(Color, Rect),
    // insert more commands here
}

为了构建显示列表，咱们遍历布局树并为每个框生成一系列命令。首先，咱们绘制框的背景，而后在背景顶部绘制边框和内容。

fn build_display_list(layout_root: &LayoutBox) -> DisplayList {
    let mut list = Vec::new();
    render_layout_box(&mut list, layout_root);
    return list;
}

fn render_layout_box(list: &mut DisplayList, layout_box: &LayoutBox) {
    render_background(list, layout_box);
    render_borders(list, layout_box);
    // TODO: render text

    for child in &layout_box.children {
        render_layout_box(list, child);
    }
}

默认状况下，HTML元素是依照它们呈现的程序重叠的:如果两个元素重叠，则前面的元素画在后面的元素之上。这反映在咱们的显示列表中，它将依照它们在DOM树中呈现的程序绘制元素。如果这段代码反对z-index属性，那么各个元素将可能笼罩这个重叠程序，咱们须要相应地对显示列表进行排序。

背景很简略。它只是一个实心矩形。如果没有指定背景色彩，那么背景是通明的，咱们不须要生成显示命令。

fn render_background(list: &mut DisplayList, layout_box: &LayoutBox) {
    get_color(layout_box, "background").map(|color|
        list.push(DisplayCommand::SolidColor(color, layout_box.dimensions.border_box())));
}

// Return the specified color for CSS property `name`, or None if no color was specified.
fn get_color(layout_box: &LayoutBox, name: &str) -> Option<Color> {
    match layout_box.box_type {
        BlockNode(style) | InlineNode(style) => match style.value(name) {
            Some(Value::ColorValue(color)) => Some(color),
            _ => None
        },
        AnonymousBlock => None
    }
}

边框是类似的，然而咱们不是画一个独自的矩形，而是每条边框都画4 – 1。

fn render_borders(list: &mut DisplayList, layout_box: &LayoutBox) {
    let color = match get_color(layout_box, "border-color") {
        Some(color) => color,
        _ => return // bail out if no border-color is specified
    };

    let d = &layout_box.dimensions;
    let border_box = d.border_box();

    // Left border
    list.push(DisplayCommand::SolidColor(color, Rect {
        x: border_box.x,
        y: border_box.y,
        width: d.border.left,
        height: border_box.height,
    }));

    // Right border
    list.push(DisplayCommand::SolidColor(color, Rect {
        x: border_box.x + border_box.width - d.border.right,
        y: border_box.y,
        width: d.border.right,
        height: border_box.height,
    }));

    // Top border
    list.push(DisplayCommand::SolidColor(color, Rect {
        x: border_box.x,
        y: border_box.y,
        width: border_box.width,
        height: d.border.top,
    }));

    // Bottom border
    list.push(DisplayCommand::SolidColor(color, Rect {
        x: border_box.x,
        y: border_box.y + border_box.height - d.border.bottom,
        width: border_box.width,
        height: d.border.bottom,
    }));
}

接下来，渲染函数将绘制盒子的每个子元素，直到整个布局树被转换成显示命令为止。

光栅化

当初咱们曾经构建了显示列表，咱们须要通过执行每个DisplayCommand将其转换为像素。咱们将把像素存储在画布中:

struct Canvas {
    pixels: Vec<Color>,
    width: usize,
    height: usize,
}

impl Canvas {
    // Create a blank canvas
    fn new(width: usize, height: usize) -> Canvas {
        let white = Color { r: 255, g: 255, b: 255, a: 255 };
        return Canvas {
            pixels: repeat(white).take(width * height).collect(),
            width: width,
            height: height,
        }
    }
    // ...
}

要在画布上绘制矩形，只需循环遍历它的行和列，应用helper办法确保不会超出画布的范畴。

fn paint_item(&mut self, item: &DisplayCommand) {
    match item {
        &DisplayCommand::SolidColor(color, rect) => {
            // Clip the rectangle to the canvas boundaries.
            let x0 = rect.x.clamp(0.0, self.width as f32) as usize;
            let y0 = rect.y.clamp(0.0, self.height as f32) as usize;
            let x1 = (rect.x + rect.width).clamp(0.0, self.width as f32) as usize;
            let y1 = (rect.y + rect.height).clamp(0.0, self.height as f32) as usize;

            for y in (y0 .. y1) {
                for x in (x0 .. x1) {
                    // TODO: alpha compositing with existing pixel
                    self.pixels[x + y * self.width] = color;
                }
            }
        }
    }
}

留神，这段代码只实用于不通明的色彩。如果咱们增加了透明度(通过读取不透明度属性，或在CSS解析器中增加对rgba()值的反对)，那么它就须要将每个新像素与它所绘制的任何内容混合在一起。

当初咱们能够把所有货色都放到paint函数中，它会构建一个显示列表，而后栅格化到画布上:

// Paint a tree of LayoutBoxes to an array of pixels.
fn paint(layout_root: &LayoutBox, bounds: Rect) -> Canvas {
    let display_list = build_display_list(layout_root);
    let mut canvas = Canvas::new(bounds.width as usize, bounds.height as usize);
    for item in display_list {
        canvas.paint_item(&item);
    }
    return canvas;
}

最初，咱们能够编写几行代码，应用Rust图像库将像素数组保留为PNG文件。
丑陋的图片

最初，咱们曾经达到渲染管道的末端。在不到1000行代码中，robinson当初能够解析这个HTML文件了:

<div class="a">
  <div class="b">
    <div class="c">
      <div class="d">
        <div class="e">
          <div class="f">
            <div class="g">
            </div>
          </div>
        </div>
      </div>
    </div>
  </div>
</div>

和这个CSS文件:

* { display: block; padding: 12px; }
.a { background: #ff0000; }
.b { background: #ffa500; }
.c { background: #ffff00; }
.d { background: #008000; }
.e { background: #0000ff; }
.f { background: #4b0082; }
.g { background: #800080; }

失去以下成果：

耶！

练习

如果你是单独在家玩，这里有一些你可能想尝试的事件:

编写一个代替的绘图函数，它承受显示列表并生成矢量输入(例如，SVG文件)，而不是栅格图像。

增加对不透明度和alpha混合的反对。

编写一个函数，通过剔除齐全超出画布边界的项来优化显示列表。

如果你相熟OpenGL，能够编写一个应用GL着色器绘制矩形的硬件加速绘制函数。

序幕

当初咱们曾经取得了渲染管道中每个阶段的基本功能，当初是时候回去填补一些缺失的个性了——特地是内联布局和文本渲染。当前的文章还可能增加额定的阶段，如网络和脚本。

我将在本月的湾区Rust团聚上做一个简短的演讲，“让咱们构建一个浏览器引擎吧!”会议将于今天(11月6日，周四)早晨7点在Mozilla的旧金山办公室举办，届时我的伺服开发搭档们也将进行无关伺服的演讲。谈判的视频将在Air Mozilla上进行直播，录音将在稍后公布。

原文写于2014.8.8。

原文链接：https://limpet.net/mbrubeck/2014/08/08/toy-layout-engine-1.html

退出咱们

咱们是DevUI团队，欢送来这里和咱们一起打造优雅高效的人机设计/研发体系。招聘邮箱：muyang2@huawei.com。

文/DevUI Kagol

往期文章举荐

《应用Lint工具“武装”你的我的项目 》

《跟着华为DevUI开源组件库学写单元测试用例》

《在瀑布下用火焰烤饼：三步法助你疾速定位网站性能问题（超具体）》

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章