讓我們來構建一個迷你版瀏覽器引擎吧（建議收藏）

加入我們一起學習，天天進步

來源：https://segmentfault.com/a/1190000038859456

DevUI 是一支兼具設計視角和工程視角的團隊，服務於華爲雲 DevCloud 平臺和華爲內部數箇中後臺系統，服務於設計師和前端工程師。
官方網站：devui.design
Ng 組件庫：ng-devui（歡迎 Star）
官方交流：添加 DevUI 小助手（devui-official）
DevUIHelper 插件：DevUIHelper-LSP（歡迎 Star）

引言

前端有一個經典的面試題：在瀏覽器地址欄輸入 URL 到最終呈現出頁面，中間發生了什麼？

中間有一個過程是獲取後臺返回的 HTML 文本，瀏覽器渲染引擎將其解析成 DOM 樹，並將 HTML 中的 CSS 解析成樣式樹，然後將 DOM 樹和樣式樹合併成佈局樹，並最終由繪圖程序繪製到瀏覽器畫板上。

本文通過親自動手實踐，教你一步一步實現一個迷你版瀏覽器引擎，進而 https://mp.weixin.qq.com/s/6-p0LXlz2r7MiNdDEmWiuQ，乾貨滿滿。

主要分成七個部分：

原文寫於 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 是一個節點樹。一個節點有零個或多個子節點。（它還有其他各種屬性和方法，但我們現在可以忽略其中的大部分。）

1struct Node {
2  // data common to all nodes:
3  children: Vec<Node>,
4
5  // data specific to each node type:
6  node_type: NodeType,
7}
8
9

有多種節點類型，但現在我們將忽略其中的大多數，並將節點定義爲元素節點或文本節點。在具有繼承的語言中，這些是 Node 的子類型。在 Rust 中，它們可以是枚舉 enum（Rust 的關鍵字用於 “tagged union” 或“sum type”）：

1enum NodeType {
2  Text(String),
3  Element(ElementData),
4}
5
6

元素包括一個標記名稱和任意數量的屬性，它們可以存儲爲從名稱到值的映射。Robinson 不支持名稱空間，所以它只將標記和屬性名稱存儲爲簡單的字符串。

1struct ElementData {
2    tag_name: String,
3    attributes: AttrMap,
4}
5
6type AttrMap = HashMap<String, String>;
7
8

最後，一些構造函數使創建新節點變得容易：

 1fn text(data: String) -> Node {
 2    Node { children: Vec::new(), node_type: NodeType::Text(data) }
 3}
 4
 5fn elem(name: String, attrs: AttrMap, children: Vec<Node>) -> Node {
 6    Node {
 7        children: children,
 8        node_type: NodeType::Element(ElementData {
 9            tag_name: name,
10            attributes: attrs,
11        })
12    }
13}
14
15

這是它！一個成熟的 DOM 實現將包含更多的數據和幾十個方法，但這就是我們開始所需要的。

練習

這些只是一些在家可以遵循的建議。做你感興趣的練習，跳過不感興趣的。

  1. 用你選擇的語言啓動一個新程序，並編寫代碼來表示 DOM 文本節點和元素樹。

  2. 安裝最新版本的 Rust，然後下載並構建 robinson。打開dom.rs和擴展 NodeType 以包含其他類型，如註釋節點。

  3. 編寫代碼來美化 DOM 節點樹。

在下一篇文章中，我們將添加一個將 HTML 源代碼轉換爲這些 DOM 節點樹的解析器。

參考文獻

有關瀏覽器引擎內部結構的更多詳細信息，請參閱Tali Garsiel非常精彩的瀏覽器的工作原理及其到更多資源的鏈接。

例如代碼，這裏有一個 “小型” 開源 web 呈現引擎的簡短列表。它們大多比 robinson 大很多倍，但仍然比 Gecko 或 WebKit 小得多。只有 2000 行代碼的WebWhirr是唯一一個我稱之爲 “玩具” 引擎的引擎。

你可能會發現這些有用的靈感或參考。如果你知道任何其他類似的項目，或者如果你開始自己的項目，請讓我知道！

第二部分：HTML

這是構建一個玩具瀏覽器渲染引擎系列文章的第二篇。

本文是關於解析 HTML 源代碼以生成 DOM 節點樹的。解析是一個很吸引人的話題，但是我沒有足夠的時間或專業知識來介紹它。你可以從任何關於編譯器的優秀課程或書籍中獲得關於解析的詳細介紹。或者通過閱讀與你選擇的編程語言一起工作的解析器生成器的文檔來獲得動手操作的開始。

HTML 有自己獨特的解析算法。與大多數編程語言和文件格式的解析器不同，HTML 解析算法不會拒絕無效的輸入。相反，它包含了特定的錯誤處理指令，因此 web 瀏覽器可以就如何顯示每個 web 頁面達成一致，即使是那些不符合語法規則的頁面。Web 瀏覽器必須做到這一點才能使用：因爲不符合標準的 HTML 在 Web 早期就得到了支持，所以現在大部分現有 Web 頁面都在使用它。

簡單的 HTML 方言

我甚至沒有嘗試實現標準的 HTML 解析算法。相反，我爲 HTML 語法的一小部分編寫了一個基本解析器。我的解析器可以處理這樣的簡單頁面：

 1<html>
 2    <body>
 3        <h1>Title</h1>
 4        <div>
 5            <p>Hello <em>world</em>!</p>
 6        </div>
 7    </body>
 8</html>
 9
10

允許使用以下語法:

其他所有內容都不支持，包括：

在這個項目的每個階段，我都或多或少地編寫了支持後面階段所需的最小代碼。但是如果你想學習更多的解析理論和工具，你可以在你自己的項目中更加雄心勃勃！

示例代碼

接下來，讓我們回顧一下我的 HTML 解析器，記住這只是一種方法（而且可能不是最好的方法）。它的結構鬆散地基於 Servo 的 cssparser 庫中的 tokenizer 模塊。它沒有真正的錯誤處理；在大多數情況下，它只是在遇到意外的語法時中止。代碼是用 Rust 語言寫的，但我希望它對於使用類似語言（如 Java、C++ 或 C#）的人來說具有相當的可讀性。它使用了第一部分中的 DOM 數據結構。

解析器將其輸入字符串和當前位置存儲在字符串中。位置是我們還沒有處理的下一個字符的索引。

1struct Parser {
2    pos: usize, // "usize" is an unsigned integer, similar to "size_t" in C
3    input: String,
4}
5
6

我們可以用它來實現一些簡單的方法來窺視輸入中的下一個字符：

 1impl Parser {
 2    // Read the current character without consuming it.
 3    fn next_char(&self) -> char {
 4        self.input[self.pos..].chars().next().unwrap()
 5    }
 6
 7    // Do the next characters start with the given string?
 8    fn starts_with(&self, s: &str) -> bool {
 9        self.input[self.pos ..].starts_with(s)
10    }
11
12    // Return true if all input is consumed.
13    fn eof(&self) -> bool {
14        self.pos >= self.input.len()
15    }
16
17    // ...
18}
19
20

Rust 字符串存儲爲 UTF-8 字節數組。要進入下一個字符，我們不能只前進一個字節。相反，我們使用 char_indices 來正確處理多字節字符。（如果我們的字符串使用固定寬度的字符，我們可以只將 pos 加 1。）

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

通常我們想要使用一個連續的字符串。consume_while方法使用滿足給定條件的字符，並將它們作爲字符串返回。這個方法的參數是一個函數，它接受一個 char 並返回一個 bool 值。

 1// Consume characters until `test` returns false.
 2fn consume_while<F>(&mut self, test: F) -> String
 3        where F: Fn(char) -> bool {
 4    let mut result = String::new();
 5    while !self.eof() && test(self.next_char()) {
 6        result.push(self.consume_char());
 7    }
 8    return result;
 9}
10
11

我們可以使用它來忽略空格字符序列，或者使用字母數字字符串：

 1// Consume and discard zero or more whitespace characters.
 2fn consume_whitespace(&mut self) {
 3    self.consume_while(CharExt::is_whitespace);
 4}
 5
 6// Parse a tag or attribute name.
 7fn parse_tag_name(&mut self) -> String {
 8    self.consume_while(|c| match c {
 9        'a'...'z' | 'A'...'Z' | '0'...'9' => true,
10        _ => false
11    })
12}
13
14

現在我們已經準備好開始解析 HTML 了。要解析單個節點，我們查看它的第一個字符，看它是元素節點還是文本節點。在我們簡化的 HTML 版本中，文本節點可以包含除<之外的任何字符。

 1// Parse a single node.
 2fn parse_node(&mut self) -> dom::Node {
 3    match self.next_char() {
 4        '<' => self.parse_element(),
 5        _   => self.parse_text()
 6    }
 7}
 8
 9// Parse a text node.
10fn parse_text(&mut self) -> dom::Node {
11    dom::text(self.consume_while(|c| c != '<'))
12}
13
14

一個元素更爲複雜。它包括開始和結束標籤，以及在它們之間任意數量的子節點:

 1// Parse a single element, including its open tag, contents, and closing tag.
 2fn parse_element(&mut self) -> dom::Node {
 3    // Opening tag.
 4    assert!(self.consume_char() == '<');
 5    let tag_name = self.parse_tag_name();
 6    let attrs = self.parse_attributes();
 7    assert!(self.consume_char() == '>');
 8
 9    // Contents.
10    let children = self.parse_nodes();
11
12    // Closing tag.
13    assert!(self.consume_char() == '<');
14    assert!(self.consume_char() == '/');
15    assert!(self.parse_tag_name() == tag_name);
16    assert!(self.consume_char() == '>');
17
18    return dom::elem(tag_name, attrs, children);
19}
20
21

在我們簡化的語法中，解析屬性非常容易。在到達開始標記 (>) 的末尾之前，我們重複地查找後面跟着=的名稱，然後是用引號括起來的字符串。

 1// Parse a single  pair.
 2fn parse_attr(&mut self) -> (String, String) {
 3    let name = self.parse_tag_name();
 4    assert!(self.consume_char() == '=');
 5    let value = self.parse_attr_value();
 6    return (name, value);
 7}
 8
 9// Parse a quoted value.
10fn parse_attr_value(&mut self) -> String {
11    let open_quote = self.consume_char();
12    assert!(open_quote == '"' || open_quote == '\'');
13    let value = self.consume_while(|c| c != open_quote);
14    assert!(self.consume_char() == open_quote);
15    return value;
16}
17
18// Parse a list of  pairs, separated by whitespace.
19fn parse_attributes(&mut self) -> dom::AttrMap {
20    let mut attributes = HashMap::new();
21    loop {
22        self.consume_whitespace();
23        if self.next_char() == '>' {
24            break;
25        }
26        let (name, value) = self.parse_attr();
27        attributes.insert(name, value);
28    }
29    return attributes;
30}
31
32

爲了解析子節點，我們在循環中遞歸地調用parse_node，直到到達結束標記。這個函數返回一個Vec，這是 Rust 對可增長數組的名稱。

 1// Parse a sequence of sibling nodes.
 2fn parse_nodes(&mut self) -> Vec<dom::Node> {
 3    let mut nodes = Vec::new();
 4    loop {
 5        self.consume_whitespace();
 6        if self.eof() || self.starts_with("</") {
 7            break;
 8        }
 9        nodes.push(self.parse_node());
10    }
11    return nodes;
12}
13
14

最後，我們可以把所有這些放在一起，將整個 HTML 文檔解析成 DOM 樹。如果文檔沒有顯式包含根節點，則該函數將爲文檔創建根節點；這與真正的 HTML 解析器的功能類似。

 1// Parse an HTML document and return the root element.
 2pub fn parse(source: String) -> dom::Node {
 3    let mut nodes = Parser { pos: 0, input: source }.parse_nodes();
 4
 5    // If the document contains a root element, just return it. Otherwise, create one.
 6    if nodes.len() == 1 {
 7        nodes.swap_remove(0)
 8    } else {
 9        dom::elem("html".to_string(), HashMap::new(), nodes)
10    }
11}
12
13

就是這樣！robinson HTML 解析器的全部代碼。整個程序總共只有 100 多行代碼 (不包括空白行和註釋)。如果你使用一個好的庫或解析器生成器，你可能可以在更少的空間中構建一個類似的玩具解析器。

練習

這裏有一些你可以自己嘗試的替代方法。與前面一樣，你可以選擇其中的一個或多個，並忽略其他。

  1. 構建一個以 HTML 子集作爲輸入並生成 DOM 節點樹的解析器 (“手動” 或使用庫或解析器生成器)。

  2. 修改 robinson 的 HTML 解析器，添加一些缺失的特性，比如註釋。或者用更好的解析器替換它，可能使用庫或生成器構建。

  3. 創建一個無效的 HTML 文件，導致你的 (或我的) 解析器失敗。修改解析器以從錯誤中恢復，併爲測試文件生成 DOM 樹。

捷徑

如果想完全跳過解析，可以通過編程方式構建 DOM 樹，向程序中添加類似這樣的代碼 (僞代碼，調整它以匹配第 1 部分中編寫的 DOM 代碼)：

1// <html><body>Hello, world!</body></html>
2let root = element("html");
3let body = element("body");
4root.children.push(body);
5body.children.push(text("Hello, world!"));
6
7

或者你可以找到一個現有的 HTML 解析器並將其合併到你的程序中。

本系列的下一篇文章將討論 CSS 數據結構和解析。

第三部分：CSS

本文是構建玩具瀏覽器呈現引擎系列文章中的第三篇。

本文介紹了用於讀取層疊樣式表 (CSS) 的代碼。像往常一樣，我不會試圖涵蓋該規範中的所有內容。相反，我嘗試實現足以說明一些概念併爲後期渲染管道生成輸入的內容。

剖析樣式表

下面是一個 CSS 源代碼示例：

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

接下來，我將從我的玩具瀏覽器引擎 robinson 中瀏覽 css 模塊。雖然這些概念可以很容易地轉換成其他編程語言，但代碼還是用 Rust 寫的。先閱讀前面的文章可能會幫助您理解下面的一些代碼。

CSS 樣式表是一系列規則。(在上面的示例樣式表中，每行包含一條規則。)

1struct Stylesheet {
2    rules: Vec<Rule>,
3}
4
5

一條規則包括一個或多個用逗號分隔的選擇器，後跟一系列用大括號括起來的聲明。

1struct Rule {
2    selectors: Vec<Selector>,
3    declarations: Vec<Declaration>,
4}
5
6

一個選擇器可以是一個簡單的選擇器，也可以是一個由_組合符_連接的選擇器鏈。Robinson 目前只支持簡單的選擇器。

注意：令人困惑的是，新的 Selectors Level 3 標準使用相同的術語來表示略有不同的東西。在本文中，我主要引用 CSS2.1。儘管過時了，但它是一個有用的起點，因爲它更小，更獨立 (與 CSS3 相比，CSS3 被分成無數互相依賴和 CSS2.1 的規範)。

在 robinson 中，一個簡單選擇器可以包括一個標記名，一個以'#'爲前綴的 ID，任意數量的以'.'爲前綴的類名，或以上幾種情況的組合。如果標籤名爲空或'*'，那麼它是一個 “通用選擇器”，可以匹配任何標籤。

還有許多其他類型的選擇器 (特別是在 CSS3 中)，但現在這樣就可以了。

 1enum Selector {
 2    Simple(SimpleSelector),
 3}
 4
 5struct SimpleSelector {
 6    tag_name: Option<String>,
 7    id: Option<String>,
 8    class: Vec<String>,
 9}
10
11

聲明只是一個名稱 / 值對，由冒號分隔並以分號結束。例如，“margin: auto;” 是一個聲明。

1struct Declaration {
2    name: String,
3    value: Value,
4}
5
6

我的玩具引擎只支持 CSS 衆多值類型中的一小部分。

 1enum Value {
 2    Keyword(String),
 3    Length(f32, Unit),
 4    ColorValue(Color),
 5    // insert more values here
 6}
 7
 8enum Unit {
 9    Px,
10    // insert more units here
11}
12
13struct Color {
14    r: u8,
15    g: u8,
16    b: u8,
17    a: u8,
18}
19
20

注意：u8 是一個 8 位無符號整數，f32 是一個 32 位浮點數。

不支持所有其他 CSS 語法，包括@-rules、註釋和上面沒有提到的任何選擇器 / 值 / 單元。

解析

CSS 有一個規則的語法，這使得它比它古怪的表親 HTML 更容易正確解析。當符合標準的 CSS 解析器遇到解析錯誤時，它會丟棄樣式表中無法識別的部分，但仍然處理其餘部分。這是很有用的，因爲它允許樣式表包含新的語法，但在舊的瀏覽器中仍然產生定義良好的輸出。

Robinson 使用了一個非常簡單 (完全不符合標準) 的解析器，構建的方式與第 2 部分中的 HTML 解析器相同。我將粘貼一些代碼片段，而不是一行一行地重複整個過程。例如，下面是解析單個選擇器的代碼:

 1// Parse one simple selector, e.g.: `type#id.class1.class2.class3`
 2fn parse_simple_selector(&mut self) -> SimpleSelector {
 3    let mut selector = SimpleSelector { tag_name: None, id: None, class: Vec::new() };
 4    while !self.eof() {
 5        match self.next_char() {
 6            '#' => {
 7                self.consume_char();
 8                selector.id = Some(self.parse_identifier());
 9            }
10            '.' => {
11                self.consume_char();
12                selector.class.push(self.parse_identifier());
13            }
14            '*' => {
15                // universal selector
16                self.consume_char();
17            }
18            c if valid_identifier_char(c) => {
19                selector.tag_name = Some(self.parse_identifier());
20            }
21            _ => break
22        }
23    }
24    return selector;
25}
26
27

注意沒有錯誤檢查。一些格式不正確的輸入，如###或*foo*將成功解析併產生奇怪的結果。真正的 CSS 解析器會丟棄這些無效的選擇器。

優先級

優先級是渲染引擎在衝突中決定哪一種樣式覆蓋另一種樣式的方法之一。如果一個樣式表包含兩個匹配元素的規則，具有較高優先級的匹配選擇器的規則可以覆蓋較低優先級的選擇器中的值。

選擇器的優先級基於它的組件。ID 選擇器比類選擇器優先級更高，類選擇器比標籤選擇器優先級更高。在每個 “層級” 中，選擇器越多優先級越高。

 1pub type Specificity = (usize, usize, usize);
 2
 3impl Selector {
 4    pub fn specificity(&self) -> Specificity {
 5        // http://www.w3.org/TR/selectors/#specificity
 6        let Selector::Simple(ref simple) = *self;
 7        let a = simple.id.iter().count();
 8        let b = simple.class.len();
 9        let c = simple.tag_name.iter().count();
10        (a, b, c)
11    }
12}
13
14

(如果我們支持鏈選擇器，我們可以通過將鏈各部分的優先級相加來計算鏈的優先級。)

每個規則的選擇器都存儲在排序的向量中，優先級最高的優先。這對於匹配非常重要，我將在下一篇文章中介紹。

 1// Parse a rule set: `<selectors> { <declarations> }`.
 2fn parse_rule(&mut self) -> Rule {
 3    Rule {
 4        selectors: self.parse_selectors(),
 5        declarations: self.parse_declarations()
 6    }
 7}
 8
 9// Parse a comma-separated list of selectors.
10fn parse_selectors(&mut self) -> Vec<Selector> {
11    let mut selectors = Vec::new();
12    loop {
13        selectors.push(Selector::Simple(self.parse_simple_selector()));
14        self.consume_whitespace();
15        match self.next_char() {
16            ',' => { self.consume_char(); self.consume_whitespace(); }
17            '{' => break, // start of declarations
18            c   => panic!("Unexpected character {} in selector list", c)
19        }
20    }
21    // Return selectors with highest specificity first, for use in matching.
22    selectors.sort_by(|a,b| b.specificity().cmp(&a.specificity()));
23    return selectors;
24}
25
26

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 屬性值：

 1// Map from CSS property names to values.
 2type PropertyMap = HashMap<String, Value>;
 3
 4// A node with associated style data.
 5struct StyledNode<'a> {
 6    node: &'a Node, // pointer to a DOM node
 7    specified_values: PropertyMap,
 8    children: Vec<StyledNode<'a>>,
 9}
10
11

這些'a是什麼？這些都是生存期，這是 Rust 如何保證指針是內存安全的，而不需要進行垃圾回收的部分原因。如果你不是在 Rust 的環境中工作，你可以忽略它們；它們對代碼的意義並不重要。

我們可以向dom::Node結構添加新的字段，而不是創建一個新的樹，但我想讓樣式代碼遠離早期的 “教訓”。這也讓我有機會討論大多數渲染引擎中的平行樹。

瀏覽器引擎模塊通常以一個樹作爲輸入，然後產生一個不同但相關的樹作爲輸出。例如，Gecko 的佈局代碼獲取一個 DOM 樹並生成一個框架樹，然後使用它來構建一個視圖樹。Blink 和 WebKit 將 DOM 樹轉換爲渲染樹。所有這些引擎的後期階段會產生更多的樹，包括層樹和部件樹。

在我們完成了更多的階段後，我們的玩具瀏覽器引擎的管道將看起來像這樣：

在我的實現中，DOM 樹中的每個節點在樣式樹中只有一個節點。但在更復雜的管道階段，幾個輸入節點可能會分解爲一個輸出節點。或者一個輸入節點可能擴展爲幾個輸出節點，或者完全跳過。例如，樣式樹可以排除顯示屬性設置爲'none'的元素。(相反，我將在佈局階段刪除這些內容，因爲這樣我的代碼會變得更簡單一些。)

選擇器匹配

構建樣式樹的第一步是選擇器匹配。這將非常容易，因爲我的 CSS 解析器只支持簡單的選擇器。您可以通過查看元素本身來判斷一個簡單的選擇器是否匹配一個元素。匹配複合選擇器需要遍歷 DOM 樹以查看元素的兄弟元素、父元素等。

1fn matches(elem: &ElementData, selector: &Selector) -> bool {
2    match *selector {
3        Simple(ref simple_selector) => matches_simple_selector(elem, simple_selector)
4    }
5}
6
7

爲了有所幫助，我們將向 DOM 元素類型添加一些方便的 ID 和類訪問器。class屬性可以包含多個用空格分隔的類名，我們在散列表中返回這些類名。

 1impl ElementData {
 2    pub fn id(&self) -> Option<&String> {
 3        self.attributes.get("id")
 4    }
 5
 6    pub fn classes(&self) -> HashSet<&str> {
 7        match self.attributes.get("class") {
 8            Some(classlist) => classlist.split(' ').collect(),
 9            None => HashSet::new()
10        }
11    }
12}
13
14

要測試一個簡單的選擇器是否匹配一個元素，只需查看每個選擇器組件，如果元素沒有匹配的類、ID 或標記名，則返回 false。

 1fn matches_simple_selector(elem: &ElementData, selector: &SimpleSelector) -> bool {
 2    // Check type selector
 3    if selector.tag_name.iter().any(|name| elem.tag_name != *name) {
 4        return false;
 5    }
 6
 7    // Check ID selector
 8    if selector.id.iter().any(|id| elem.id() != Some(id)) {
 9        return false;
10    }
11
12    // Check class selectors
13    let elem_classes = elem.classes();
14    if selector.class.iter().any(|class| !elem_classes.contains(&**class)) {
15        return false;
16    }
17
18    // We didn't find any non-matching selector components.
19    return true;
20}
21
22

注意：這個函數使用 any 方法，如果迭代器包含一個通過所提供的測試的元素，則該方法返回 true。這與 Python 中的 any 函數 (或 Haskell) 或 JavaScript 中的 some 方法相同。

構建樣式樹

接下來，我們需要遍歷 DOM 樹。對於樹中的每個元素，我們將在樣式表中搜索匹配規則。

當比較兩個匹配相同元素的規則時，我們需要使用來自每個匹配的最高優先級選擇器。因爲我們的 CSS 解析器存儲了從優先級從高低的選擇器，所以只要找到了匹配的選擇器，我們就可以停止，並返回它的優先級以及指向規則的指針。

 1type MatchedRule<'a> = (Specificity, &'a Rule);
 2
 3// If `rule` matches `elem`, return a `MatchedRule`. Otherwise return `None`.
 4fn match_rule<'a>(elem: &ElementData, rule: &'a Rule) -> Option<MatchedRule<'a>> {
 5    // Find the first (highest-specificity) matching selector.
 6    rule.selectors.iter()
 7        .find(|selector| matches(elem, *selector))
 8        .map(|selector| (selector.specificity(), rule))
 9}
10
11

爲了找到與一個元素匹配的所有規則，我們稱之爲filter_map，它對樣式表進行線性掃描，檢查每個規則並排除不匹配的規則。真正的瀏覽器引擎會根據標籤名稱、id、類等將規則存儲在多個散列表中，從而加快速度。

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

一旦有了匹配規則，就可以爲元素找到指定的值。我們將每個規則的屬性值插入到HashMap中。我們根據優先級對匹配進行排序，因此在較不特定的規則之後處理更特定的規則，並可以覆蓋它們在 HashMap 中的值。

 1// Apply styles to a single element, returning the specified values.
 2fn specified_values(elem: &ElementData, stylesheet: &Stylesheet) -> PropertyMap {
 3    let mut values = HashMap::new();
 4    let mut rules = matching_rules(elem, stylesheet);
 5
 6    // Go through the rules from lowest to highest specificity.
 7    rules.sort_by(|&(a, _), &(b, _)| a.cmp(&b));
 8    for (_, rule) in rules {
 9        for declaration in &rule.declarations {
10            values.insert(declaration.name.clone(), declaration.value.clone());
11        }
12    }
13    return values;
14}
15
16

現在，我們已經擁有遍歷 DOM 樹和構建樣式樹所需的一切。注意，選擇器匹配只對元素有效，因此文本節點的指定值只是一個空映射。

 1// Apply a stylesheet to an entire DOM tree, returning a StyledNode tree.
 2pub fn style_tree<'a>(root: &'a Node, stylesheet: &'a Stylesheet) -> StyledNode<'a> {
 3    StyledNode {
 4        node: root,
 5        specified_values: match root.node_type {
 6            Element(ref elem) => specified_values(elem, stylesheet),
 7            Text(_) => HashMap::new()
 8        },
 9        children: root.children.iter().map(|child| style_tree(child, stylesheet)).collect(),
10    }
11}
12
13

這就是 robinson 構建樣式樹的全部代碼。接下來我將討論一些明顯的遺漏。

級聯

由 web 頁面的作者提供的樣式表稱爲_作者樣式表_。除此之外，瀏覽器還通過_用戶代理樣式表_提供默認樣式。它們可能允許用戶通過_用戶樣式表_(如 Gecko 的 userContent.css) 添加自定義樣式。

級聯定義這三個 “起源” 中哪個優先於另一個。級聯有 6 個級別: 一個用於每個起源的 “正常” 聲明，另一個用於每個起源的!important聲明。

Robinson 的風格代碼沒有實現級聯；它只需要一個樣式表。缺少默認樣式表意味着 HTML 元素將不具有任何您可能期望的默認樣式。例如，<head>元素的內容不會被隱藏，除非你顯式地把這個規則添加到你的樣式表中：

1head { display: none; }
2
3

實現級聯應該相當簡單：只需跟蹤每個規則的起源，並根據起源和重要性以及特殊性對聲明進行排序。一個簡化的、兩級的級聯應該足以支持最常見的情況：普通用戶代理樣式和普通作者樣式。

計算的值

除了上面提到的 “指定值” 之外，CSS 還定義了初始值、計算值、使用值和實際值。

_初始值_是沒有在級聯中指定的屬性的默認值。_計算值_基於指定值，但可能應用一些特定於屬性的規範化規則。

根據 CSS 規範中的定義，正確實現這些需要爲每個屬性單獨編寫代碼。對於一個真實的瀏覽器引擎來說，這項工作是必要的，但我希望在這個玩具項目中避免它。在後面的階段，當指定的值缺失時，使用這些值的代碼將 (某種程度上) 通過使用默認值模擬初始值。

_使用值_和_實際值_是在佈局期間和之後計算的，我將在以後的文章中介紹。

繼承

如果文本節點不能匹配選擇器，它們如何獲得顏色、字體和其他樣式？答案是繼承。

當屬性被繼承時，任何沒有級聯值的節點都將接收該屬性的父節點值。有些屬性，如'color'，是默認繼承的；其他僅當級聯指定特殊值“inherit”時使用。

我的代碼不支持繼承。要實現它，可以將父類的樣式數據傳遞到specified_values函數，並使用硬編碼的查找表來決定應該繼承哪些屬性。

樣式屬性

任何 HTML 元素都可以包含一個包含 CSS 聲明列表的樣式屬性。沒有選擇器，因爲這些聲明自動只應用於元素本身。

1<span>
2
3

如果您想要支持 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 位浮點型。]

 1// CSS box model. All sizes are in px.
 2
 3struct Dimensions {
 4    // Position of the content area relative to the document origin:
 5    content: Rect,
 6
 7    // Surrounding edges:
 8    padding: EdgeSizes,
 9    border: EdgeSizes,
10    margin: EdgeSizes,
11}
12
13struct Rect {
14    x: f32,
15    y: f32,
16    width: f32,
17    height: f32,
18}
19
20struct EdgeSizes {
21    left: f32,
22    right: f32,
23    top: f32,
24    bottom: f32,
25}
26
27

塊和內聯佈局

注意: 這部分包含的圖表如果沒有相關的視覺樣式，就沒有意義。如果您是在一個提要閱讀器中閱讀這篇文章，嘗試在一個常規的瀏覽器選項卡中打開原始頁面。我還爲使用屏幕閱讀器或其他輔助技術的讀者提供了文本描述。

CSS display 屬性決定一個元素生成哪種類型的框。CSS 定義了幾種框類型，每種都有自己的佈局規則。我只講其中的兩種: 塊和內聯。

我將使用這一點僞 html 來說明區別:

1<container>
2  <a></a>
3  <b></b>
4  <c></c>
5  <d></d>
6</container>
7
8

塊級框從上到下垂直地放置在容器中。

1a, b, c, d { display: block; }
2
3

行內框從左到右水平地放置在容器中。如果它們到達了容器的右邊緣，它們將環繞並繼續在下面的新行。

1a, b, c, d { display: inline; }
2
3

每個框必須只包含塊級子元素或行內子元素。當 DOM 元素包含塊級子元素和內聯子元素時，佈局引擎會插入匿名框來分隔這兩種類型。(這些框是 “匿名的”，因爲它們與 DOM 樹中的節點沒有關聯。)

在這個例子中，內聯框 b 和 c 被一個匿名塊框包圍，粉紅色顯示:

1a    { display: block; }
2b, c { display: inline; }
3d    { display: block; }
4
5

注意，內容默認垂直增長。也就是說，向容器中添加子元素通常會使容器更高，而不是更寬。另一種說法是，默認情況下，塊或行的寬度取決於其容器的寬度，而容器的高度取決於其子容器的高度。

如果你覆蓋了屬性的默認值，比如寬度和高度，這將變得更加複雜，如果你想要支持像垂直書寫這樣的特性，這將變得更加複雜。

佈局樹

佈局樹是一個框的集合。一個盒子有尺寸，它可能包含子盒子。

1struct LayoutBox<'a> {
2    dimensions: Dimensions,
3    box_type: BoxType<'a>,
4    children: Vec<LayoutBox<'a>>,
5}
6
7

框可以是塊節點、內聯節點或匿名塊框。(當我實現文本佈局時，這需要改變，因爲行換行會導致一個內聯節點被分割成多個框。但現在就可以了。)

1enum BoxType<'a> {
2    BlockNode(&'a StyledNode<'a>),
3    InlineNode(&'a StyledNode<'a>),
4    AnonymousBlock,
5}
6
7

要構建佈局樹，我們需要查看每個 DOM 節點的 display 屬性。我向 style 模塊添加了一些代碼，以獲取節點的顯示值。如果沒有指定值，則返回初始值'inline'。

 1enum Display {
 2    Inline,
 3    Block,
 4    None,
 5}
 6
 7impl StyledNode {
 8    // Return the specified value of a property if it exists, otherwise `None`.
 9    fn value(&self, name: &str) -> Option<Value> {
10        self.specified_values.get(name).map(|v| v.clone())
11    }
12
13    // The value of the `display` property (defaults to inline).
14    fn display(&self) -> Display {
15        match self.value("display") {
16            Some(Keyword(s)) => match &*s {
17                "block" => Display::Block,
18                "none" => Display::None,
19                _ => Display::Inline
20            },
21            _ => Display::Inline
22        }
23    }
24}
25
26

現在我們可以遍歷樣式樹，爲每個節點構建一個 LayoutBox，然後爲節點的子節點插入框。如果一個節點的 display 屬性被設置爲'none'，那麼它就不包含在佈局樹中。

 1// Build the tree of LayoutBoxes, but don't perform any layout calculations yet.
 2fn build_layout_tree<'a>(style_node: &'a StyledNode<'a>) -> LayoutBox<'a> {
 3    // Create the root box.
 4    let mut root = LayoutBox::new(match style_node.display() {
 5        Block => BlockNode(style_node),
 6        Inline => InlineNode(style_node),
 7        DisplayNone => panic!("Root node has display: none.")
 8    });
 9
10    // Create the descendant boxes.
11    for child in &style_node.children {
12        match child.display() {
13            Block => root.children.push(build_layout_tree(child)),
14            Inline => root.get_inline_container().children.push(build_layout_tree(child)),
15            DisplayNone => {} // Skip nodes with `display: none;`
16        }
17    }
18    return root;
19}
20
21impl LayoutBox {
22    // Constructor function
23    fn new(box_type: BoxType) -> LayoutBox {
24        LayoutBox {
25            box_type: box_type,
26            dimensions: Default::default(), // initially set all fields to 0.0
27            children: Vec::new(),
28        }
29    }
30    // ...
31}
32
33

如果塊節點包含內聯子節點，則創建一個匿名塊框來包含它。如果一行中有幾個內聯子元素，則將它們都放在同一個匿名容器中。

 1// Where a new inline child should go.
 2fn get_inline_container(&mut self) -> &mut LayoutBox {
 3    match self.box_type {
 4        InlineNode(_) | AnonymousBlock => self,
 5        BlockNode(_) => {
 6            // If we've just generated an anonymous block box, keep using it.
 7            // Otherwise, create a new one.
 8            match self.children.last() {
 9                Some(&LayoutBox { box_type: AnonymousBlock,..}) => {}
10                _ => self.children.push(LayoutBox::new(AnonymousBlock))
11            }
12            self.children.last_mut().unwrap()
13        }
14    }
15}
16
17

這是有意從標準 CSS 框生成算法的多種方式簡化的。例如，它不處理內聯框包含塊級子框的情況。此外，如果塊級節點只有內聯子節點，則會生成一個不必要的匿名框。

未完待續

哇，比我想象的要長。我想我就講到這裏，但是不要擔心：第 6 部分很快就會到來，它將討論塊級佈局。

一旦塊佈局完成，我們就可以跳轉到管道的下一個階段：繪製！我想我可能會這麼做，因爲這樣我們最終可以看到渲染引擎的輸出是漂亮的圖片而不是數字。

然而，這些圖片將只是一堆彩色的矩形，除非我們通過實現內聯佈局和文本佈局來完成佈局模塊。如果我在開始繪畫之前沒有實現這些，我希望之後再回到它們上來。

第六部分：塊佈局

歡迎回到我關於構建一個玩具 HTML 渲染引擎的系列文章，這是系列文章的第 6 篇。

本文將繼續我們在第 5 部分中開始的佈局模塊。這一次，我們將添加布局塊框的功能。這些框是垂直堆疊的，比如標題和段落。

爲了簡單起見，這段代碼只實現了正常流：沒有浮動，沒有絕對定位，也沒有固定定位。

遍歷佈局樹

該代碼的入口點是 layout 函數，它接受一個 LayoutBox 並計算其尺寸。我們將把這個函數分爲三種情況，目前只實現其中一種：

 1impl LayoutBox {
 2    // Lay out a box and its descendants.
 3    fn layout(&mut self, containing_block: Dimensions) {
 4        match self.box_type {
 5            BlockNode(_) => self.layout_block(containing_block),
 6            InlineNode(_) => {} // TODO
 7            AnonymousBlock => {} // TODO
 8        }
 9    }
10
11    // ...
12}
13
14

一個塊的佈局取決於它所包含塊的尺寸。對於正常流中的塊框，這只是框的父。對於根元素，它是瀏覽器窗口 (或“視口”) 的大小。

您可能還記得在前一篇文章中，一個塊的寬度取決於它的父塊，而它的高度取決於它的子塊。這意味着我們的代碼在計算寬度時需要自頂向下遍歷樹，因此它可以在父類的寬度已知之後佈局子類，並自底向上遍歷以計算高度，因此父類的高度在其子類的高度之後計算。

 1fn layout_block(&mut self, containing_block: Dimensions) {
 2    // Child width can depend on parent width, so we need to calculate
 3    // this box's width before laying out its children.
 4    self.calculate_block_width(containing_block);
 5
 6    // Determine where the box is located within its container.
 7    self.calculate_block_position(containing_block);
 8
 9    // Recursively lay out the children of this box.
10    self.layout_block_children();
11
12    // Parent height can depend on child height, so `calculate_height`
13    // must be called *after* the children are laid out.
14    self.calculate_block_height();
15}
16
17

該函數對佈局樹執行一次遍歷，向下時進行寬度計算，向上時進行高度計算。一個真正的佈局引擎可能會執行幾次樹遍歷，一些是自頂向下，一些是自底向上。

計算寬度

寬度計算是塊佈局函數的第一步，也是最複雜的一步。我要一步一步來。首先，我們需要 CSS 寬度屬性的值和所有左右邊的大小:

 1fn calculate_block_width(&mut self, containing_block: Dimensions) {
 2    let style = self.get_style_node();
 3
 4    // `width` has initial value `auto`.
 5    let auto = Keyword("auto".to_string());
 6    let mut width = style.value("width").unwrap_or(auto.clone());
 7
 8    // margin, border, and padding have initial value 0.
 9    let zero = Length(0.0, Px);
10
11    let mut margin_left = style.lookup("margin-left", "margin", &zero);
12    let mut margin_right = style.lookup("margin-right", "margin", &zero);
13
14    let border_left = style.lookup("border-left-width", "border-width", &zero);
15    let border_right = style.lookup("border-right-width", "border-width", &zero);
16
17    let padding_left = style.lookup("padding-left", "padding", &zero);
18    let padding_right = style.lookup("padding-right", "padding", &zero);
19
20    // ...
21}
22
23

這使用了一個名爲 lookup 的助手函數，它只是按順序嘗試一系列值。如果第一個屬性沒有設置，它將嘗試第二個屬性。如果沒有設置，它將返回給定的默認值。這提供了一個不完整 (但簡單) 的簡寫屬性和初始值實現。

注意: 這類似於 JavaScript 或 Ruby 中的以下代碼:

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

因爲子對象不能改變父對象的寬度，所以它需要確保自己的寬度與父對象的寬度相符。CSS 規範將其表達爲一組約束和解決它們的算法。下面的代碼實現了該算法。

首先，我們將邊距、內邊距、邊框和內容寬度相加。to_px 幫助器方法將長度轉換爲它們的數值。如果一個屬性被設置爲'auto'，它會返回 0，因此它不會影響和。

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

這是盒子所需要的最小水平空間。如果它不等於容器的寬度，我們需要調整一些東西使它相等。

如果寬度或邊距設置爲 “auto”，它們可以擴展或收縮以適應可用的空間。按照說明書，我們首先檢查盒子是否太大。如果是這樣，我們將任何可擴展邊距設置爲零。

 1// If width is not auto and the total is wider than the container, treat auto margins as 0.
 2if width != auto && total > containing_block.content.width {
 3    if margin_left == auto {
 4        margin_left = Length(0.0, Px);
 5    }
 6    if margin_right == auto {
 7        margin_right = Length(0.0, Px);
 8    }
 9}
10
11

如果盒子對容器來說太大，就會溢出容器。如果太小，它就會下泄，留下額外的空間。我們將計算下溢量，即容器內剩餘空間的大小。(如果這個數字是負數，它實際上是一個溢出。)

1let underflow = containing_block.content.width - total;
2
3

我們現在遵循規範的算法，通過調整可擴展的尺寸來消除任何溢出或下溢。如果沒有 “自動” 尺寸，我們調整右邊的邊距。(是的，這意味着在溢出的情況下，邊界可能是負的!)

 1match (width == auto, margin_left == auto, margin_right == auto) {
 2    // If the values are overconstrained, calculate margin_right.
 3    (false, false, false) => {
 4        margin_right = Length(margin_right.to_px() + underflow, Px);
 5    }
 6
 7    // If exactly one size is auto, its used value follows from the equality.
 8    (false, false, true) => { margin_right = Length(underflow, Px); }
 9    (false, true, false) => { margin_left  = Length(underflow, Px); }
10
11    // If width is set to auto, any other auto values become 0.
12    (true, _, _) => {
13        if margin_left == auto { margin_left = Length(0.0, Px); }
14        if margin_right == auto { margin_right = Length(0.0, Px); }
15
16        if underflow >= 0.0 {
17            // Expand width to fill the underflow.
18            width = Length(underflow, Px);
19        } else {
20            // Width can't be negative. Adjust the right margin instead.
21            width = Length(0.0, Px);
22            margin_right = Length(margin_right.to_px() + underflow, Px);
23        }
24    }
25
26    // If margin-left and margin-right are both auto, their used values are equal.
27    (false, true, true) => {
28        margin_left = Length(underflow / 2.0, Px);
29        margin_right = Length(underflow / 2.0, Px);
30    }
31}
32
33

此時，約束已經滿足，任何'auto'值都已經轉換爲長度。結果是水平框尺寸的使用值，我們將把它存儲在佈局樹中。你可以在 layout.rs 中看到最終的代碼。

定位

下一步比較簡單。這個函數查找剩餘的邊距 / 內邊距 / 邊框樣式，並使用這些樣式和包含的塊尺寸來確定這個塊在頁面上的位置。

 1fn calculate_block_position(&mut self, containing_block: Dimensions) {
 2    let style = self.get_style_node();
 3    let d = &mut self.dimensions;
 4
 5    // margin, border, and padding have initial value 0.
 6    let zero = Length(0.0, Px);
 7
 8    // If margin-top or margin-bottom is `auto`, the used value is zero.
 9    d.margin.top = style.lookup("margin-top", "margin", &zero).to_px();
10    d.margin.bottom = style.lookup("margin-bottom", "margin", &zero).to_px();
11
12    d.border.top = style.lookup("border-top-width", "border-width", &zero).to_px();
13    d.border.bottom = style.lookup("border-bottom-width", "border-width", &zero).to_px();
14
15    d.padding.top = style.lookup("padding-top", "padding", &zero).to_px();
16    d.padding.bottom = style.lookup("padding-bottom", "padding", &zero).to_px();
17
18    d.content.x = containing_block.content.x +
19                  d.margin.left + d.border.left + d.padding.left;
20
21    // Position the box below all the previous boxes in the container.
22    d.content.y = containing_block.content.height + containing_block.content.y +
23                  d.margin.top + d.border.top + d.padding.top;
24}
25
26

仔細看看最後一條語句，它設置了 y 的位置。這就是爲什麼塊佈局具有獨特的垂直堆疊行爲。爲了實現這一點，我們需要確保父節點的內容。高度在佈局每個子元素後更新。

子元素

下面是遞歸佈局框內容的代碼。當它循環遍歷子框時，它會跟蹤總內容高度。定位代碼 (上面) 使用這個函數來查找下一個子元素的垂直位置。

 1fn layout_block_children(&mut self) {
 2    let d = &mut self.dimensions;
 3    for child in &mut self.children {
 4        child.layout(*d);
 5        // Track the height so each child is laid out below the previous content.
 6        d.content.height = d.content.height + child.dimensions.margin_box().height;
 7    }
 8}
 9
10

每個子節點佔用的總垂直空間是其邊距框的高度，我們是這樣計算的:

 1impl Dimensions {
 2    // The area covered by the content area plus its padding.
 3    fn padding_box(self) -> Rect {
 4        self.content.expanded_by(self.padding)
 5    }
 6    // The area covered by the content area plus padding and borders.
 7    fn border_box(self) -> Rect {
 8        self.padding_box().expanded_by(self.border)
 9    }
10    // The area covered by the content area plus padding, borders, and margin.
11    fn margin_box(self) -> Rect {
12        self.border_box().expanded_by(self.margin)
13    }
14}
15
16impl Rect {
17    fn expanded_by(self, edge: EdgeSizes) -> Rect {
18        Rect {
19            x: self.x - edge.left,
20            y: self.y - edge.top,
21            width: self.width + edge.left + edge.right,
22            height: self.height + edge.top + edge.bottom,
23        }
24    }
25}
26
27

爲簡單起見，這裏沒有實現邊距摺疊。一個真正的佈局引擎會允許一個框的底部邊緣與下一個框的頂部邊緣重疊，而不是每個框都完全放在前一個框的下面。

“高度” 屬性

默認情況下，框的高度等於其內容的高度。但如果'height'屬性被顯式設置爲長度，我們將使用它來代替:

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

這就是塊佈局算法。現在你可以在一個 HTML 文檔上調用 layout()，它會生成一堆矩形，包括寬度、高度、邊距等。很酷, 對吧?

練習

對於雄心勃勃的實現者，一些額外的想法：

  1. 崩潰的垂直邊緣。

  2. 相對定位。

  3. 並行化佈局過程，並測量對性能的影響。

如果您嘗試並行化項目，您可能想要將寬度計算和高度計算分離爲兩個不同的通道。通過爲每個子任務生成一個單獨的任務，從上至下遍歷寬度很容易並行化。高度的計算要稍微複雜一些，因爲您需要返回並在每個子元素被佈局之後調整它們的 y 位置。

未完待續

感謝所有跟隨我走到這一步的人！

隨着我深入到佈局和渲染的陌生領域，這些文章的編寫時間越來越長。在我試驗字體和圖形代碼的下一部分之前，會有一段較長的時間中斷，但我會盡快恢復這個系列。

更新：第 7 部分現在準備好了。

第七部分：繪製 101

歡迎回到我的關於構建一個簡單 HTML 渲染引擎的系列，這是第 7 篇，也是最後一篇。

在這篇文章中，我將添加非常基本的繪畫代碼。這段代碼從佈局模塊中獲取框樹，並將它們轉換爲像素數組。這個過程也稱爲 “柵格化”。

瀏覽器通常在Skia、Cairo、Direct2D等圖形 api 和庫的幫助下實現光柵化。這些 api 提供了繪製多邊形、直線、曲線、漸變和文本的函數。現在，我將編寫我自己的光柵化程序，它只能繪製一種東西: 矩形。

最後我想實現文本渲染。在這一點上，我可能會拋棄這個玩具繪畫代碼，轉而使用 “真正的”2D 圖形庫。但就目前而言，矩形足以將我的塊佈局算法的輸出轉換爲圖片。

迎頭趕上

從上一篇文章開始，我對以前文章中的代碼做了一些小的修改。這包括一些小的重構，以及一些更新，以保持代碼與最新的 Rust 夜間構建兼容。這些更改對理解代碼都不是至關重要的，但是如果您好奇的話，可以查看提交歷史記錄。

構建顯示列表

在繪製之前，我們將遍歷佈局樹並構建一個顯示列表。這是一個圖形操作列表，如 “繪製圓圈” 或“繪製文本字符串”。或者在我們的例子中，只是“畫一個矩形”。

爲什麼要將命令放入顯示列表中，而不是立即執行它們? 顯示列表之所以有用有幾個原因。你可以通過搜索來找到被後期操作完全掩蓋的物品，並將其移除，以消除浪費的油漆。在只知道某些項發生了更改的情況下，可以修改和重用顯示列表。您可以使用相同的顯示列表生成不同類型的輸出: 例如，用於在屏幕上顯示的像素，或用於發送到打印機的矢量圖形。

Robinson 的顯示列表是顯示命令的向量。目前，只有一種類型的 DisplayCommand，一個純色矩形:

1type DisplayList = Vec<DisplayCommand>;
2
3enum DisplayCommand {
4    SolidColor(Color, Rect),
5    // insert more commands here
6}
7
8

爲了構建顯示列表，我們遍歷佈局樹併爲每個框生成一系列命令。首先，我們繪製框的背景，然後在背景頂部繪製邊框和內容。

 1fn build_display_list(layout_root: &LayoutBox) -> DisplayList {
 2    let mut list = Vec::new();
 3    render_layout_box(&mut list, layout_root);
 4    return list;
 5}
 6
 7fn render_layout_box(list: &mut DisplayList, layout_box: &LayoutBox) {
 8    render_background(list, layout_box);
 9    render_borders(list, layout_box);
10    // TODO: render text
11
12    for child in &layout_box.children {
13        render_layout_box(list, child);
14    }
15}
16
17

默認情況下，HTML 元素是按照它們出現的順序堆疊的: 如果兩個元素重疊，則後面的元素畫在前面的元素之上。這反映在我們的顯示列表中，它將按照它們在 DOM 樹中出現的順序繪製元素。如果這段代碼支持 z-index 屬性，那麼各個元素將能夠覆蓋這個堆疊順序，我們需要相應地對顯示列表進行排序。

背景很簡單。它只是一個實心矩形。如果沒有指定背景顏色，那麼背景是透明的，我們不需要生成顯示命令。

 1fn render_background(list: &mut DisplayList, layout_box: &LayoutBox) {
 2    get_color(layout_box, "background").map(|color|
 3        list.push(DisplayCommand::SolidColor(color, layout_box.dimensions.border_box())));
 4}
 5
 6// Return the specified color for CSS property `name`, or None if no color was specified.
 7fn get_color(layout_box: &LayoutBox, name: &str) -> Option<Color> {
 8    match layout_box.box_type {
 9        BlockNode(style) | InlineNode(style) => match style.value(name) {
10            Some(Value::ColorValue(color)) => Some(color),
11            _ => None
12        },
13        AnonymousBlock => None
14    }
15}
16
17

邊框是相似的，但是我們不是畫一個單獨的矩形，而是每條邊框都畫 4 - 1。

 1fn render_borders(list: &mut DisplayList, layout_box: &LayoutBox) {
 2    let color = match get_color(layout_box, "border-color") {
 3        Some(color) => color,
 4        _ => return // bail out if no border-color is specified
 5    };
 6
 7    let d = &layout_box.dimensions;
 8    let border_box = d.border_box();
 9
10    // Left border
11    list.push(DisplayCommand::SolidColor(color, Rect {
12        x: border_box.x,
13        y: border_box.y,
14        width: d.border.left,
15        height: border_box.height,
16    }));
17
18    // Right border
19    list.push(DisplayCommand::SolidColor(color, Rect {
20        x: border_box.x + border_box.width - d.border.right,
21        y: border_box.y,
22        width: d.border.right,
23        height: border_box.height,
24    }));
25
26    // Top border
27    list.push(DisplayCommand::SolidColor(color, Rect {
28        x: border_box.x,
29        y: border_box.y,
30        width: border_box.width,
31        height: d.border.top,
32    }));
33
34    // Bottom border
35    list.push(DisplayCommand::SolidColor(color, Rect {
36        x: border_box.x,
37        y: border_box.y + border_box.height - d.border.bottom,
38        width: border_box.width,
39        height: d.border.bottom,
40    }));
41}
42
43

接下來，渲染函數將繪製盒子的每個子元素，直到整個佈局樹被轉換成顯示命令爲止。

光柵化

現在我們已經構建了顯示列表，我們需要通過執行每個 DisplayCommand 將其轉換爲像素。我們將把像素存儲在畫布中:

 1struct Canvas {
 2    pixels: Vec<Color>,
 3    width: usize,
 4    height: usize,
 5}
 6
 7impl Canvas {
 8    // Create a blank canvas
 9    fn new(width: usize, height: usize) -> Canvas {
10        let white = Color { r: 255, g: 255, b: 255, a: 255 };
11        return Canvas {
12            pixels: repeat(white).take(width * height).collect(),
13            width: width,
14            height: height,
15        }
16    }
17    // ...
18}
19
20

要在畫布上繪製矩形，只需循環遍歷它的行和列，使用 helper 方法確保不會超出畫布的範圍。

 1fn paint_item(&mut self, item: &DisplayCommand) {
 2    match item {
 3        &DisplayCommand::SolidColor(color, rect) => {
 4            // Clip the rectangle to the canvas boundaries.
 5            let x0 = rect.x.clamp(0.0, self.width as f32) as usize;
 6            let y0 = rect.y.clamp(0.0, self.height as f32) as usize;
 7            let x1 = (rect.x + rect.width).clamp(0.0, self.width as f32) as usize;
 8            let y1 = (rect.y + rect.height).clamp(0.0, self.height as f32) as usize;
 9
10            for y in (y0 .. y1) {
11                for x in (x0 .. x1) {
12                    // TODO: alpha compositing with existing pixel
13                    self.pixels[x + y * self.width] = color;
14                }
15            }
16        }
17    }
18}
19
20

注意，這段代碼只適用於不透明的顏色。如果我們添加了透明度 (通過讀取不透明度屬性，或在 CSS 解析器中添加對 rgba() 值的支持)，那麼它就需要將每個新像素與它所繪製的任何內容混合在一起。

現在我們可以把所有東西都放到 paint 函數中，它會構建一個顯示列表，然後柵格化到畫布上:

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

最後，我們可以編寫幾行代碼，使用 Rust 圖像庫將像素數組保存爲 PNG 文件。漂亮的圖片

最後，我們已經到達渲染管道的末端。在不到 1000 行代碼中，robinson 現在可以解析這個 HTML 文件了:

 1<div>
 2  <div>
 3    <div>
 4      <div>
 5        <div>
 6          <div>
 7            <div>
 8            </div>
 9          </div>
10        </div>
11      </div>
12    </div>
13  </div>
14</div>
15
16

和這個 CSS 文件:

 1* { display: block; padding: 12px; }
 2.a { background: #ff0000; }
 3.b { background: #ffa500; }
 4.c { background: #ffff00; }
 5.d { background: #008000; }
 6.e { background: #0000ff; }
 7.f { background: #4b0082; }
 8.g { background: #800080; }
 9
10

得到以下效果：

耶！

練習

如果你是獨自在家玩，這裏有一些你可能想嘗試的事情:

編寫一個替代的繪圖函數，它接受顯示列表並生成矢量輸出 (例如，SVG 文件)，而不是柵格圖像。

添加對不透明度和 alpha 混合的支持。

編寫一個函數，通過剔除完全超出畫布邊界的項來優化顯示列表。

如果你熟悉 OpenGL，可以編寫一個使用 GL 着色器繪製矩形的硬件加速繪製函數。

尾聲

現在我們已經獲得了渲染管道中每個階段的基本功能，現在是時候回去填補一些缺失的特性了——特別是內聯佈局和文本渲染。以後的文章還可能添加額外的階段，如網絡和腳本。

我將在本月的灣區 Rust 聚會上做一個簡短的演講，“讓我們構建一個瀏覽器引擎吧!”會議將於明天 (11 月 6 日，週四) 晚上 7 點在Mozilla的舊金山辦公室舉行，屆時我的伺服開發夥伴們也將進行有關伺服的演講。會談的視頻將在 Air Mozilla 上進行直播，錄音將在稍後發佈。

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/N3opxoBrzk6_2_y5GjkVcA

猜你喜歡