dackdive's blog

新米webエンジニアによる技術ブログ。JavaScript(React), Salesforce, Python など

「Let's build a browser engine!」を読んでRustで簡易レンダリングエンジンを作った

Rust Frontend

Rust を勉強したらやってみたいなと思ってた記事。

記事について

タイトルの通り、簡単なブラウザのレンダリングエンジンを Rust で作る、という趣旨の記事。
著者は Servo という Mozilla が開発しているレンダリングエンジンのチームに所属（していたらしい。現在は不明）。

最終的にできるもの

たとえば、以下のような HTML と CSS

<html>
  <head>
    <title>Test</title>
  </head>
  <p class="inner">
    Hello, <span id="name">world!</span>
  </p>
  <p class="inner" id="bye">
    Goodbye!
  </p>
</html>

* {
  display: block;
}

span {
  display: inline;
}

html {
  width: 600px;
  padding: 10px;
  border-width: 1px;
  margin: auto;
  background: #ffffff;
}

head {
  display: none;
}

.outer {
  background: #00ccff;
  border-color: #666666;
  border-width: 2px;
  margin: 50px;
  padding: 50px;
}

.inner {
  border-color: #cc0000;
  border-width: 4px;
  height: 100px;
  margin-bottom: 20px;
  width: 500px;
}

.inner#bye {
  background: #ffff00;
}

span#name {
  background: red;
  color: white;
}

をパースし、↓ のような画像を出力できるようになる。

見てわかるように、テキストの描画には対応していない。

また最終的に画像を出力する部分はライブラリ(image クレート)を使用しておりスコープ外。それと、実際のブラウザウィンドウができるわけではない。

やってみた感想

レンダリングエンジンのしくみについては以前 Google の

を読んでいたので、全体的な流れについては理解していたが、このときの記憶をおさらいする感じで読めたのでよかった。
また、特に後半の Style tree から Layout tree を構築して最終的にピクセル単位の情報（どこの座標は何色で描画するか）にするまでの処理はこちらの方が詳しく書かれており、勉強になった。

あと、この記事は昨年の秋頃に読もうとして Rust 全然わからなくてすぐに挫折したんだけど、今だと書いてあることは読めるぐらいにはなっていて数ヶ月前よりは成長を実感できた。
相変わらず所有権まわりというか、どういうときに参照のままで計算してよくてどういうときにムーブしたらいいのか、とか、ここで参照外しする必要あるの？とかはよくわかってない。

ソースコードはここに置いてある。

github.com

元のコードと比べて、2018 edition で一部変更が必要だったところ、image クレートの最新バージョンでうまく動かないところなどは修正してある。
またテストが全くなかったので Part 4 ぐらいまではテストを追加しており、参考になるかもしれない。

学び

レンダリングの流れ

記事中の画像を引用する。

大きな流れは

  • 最初に HTML と CSS をそれぞれパースし DOM と CSS の Rule 群を構築する
  • DOM と Rules から Style tree（DOM にスタイル情報が付与されたような木構造）を構築する
  • Style tree から Layout tree（要素がブロック要素かインライン要素か...という情報と、コンテンツの矩形領域の大きさ）を構築する
  • Layout tree から描画コマンドのリストを作成し、描画

となっている。

Part2: HTML のパース

特に言うことなし。HTML 文字列をパースして DOM を構築する。
記事中のパーサーは文字列をいきなり最終的な DOM に変換しており Lexer（文字列を Token に変換するやつ）は登場しなかった。

Part3: CSS のパース

DOM と異なり、こちらは木構造ではなくただのリストになっている（型で書くと Vec<Rule>）。
記事中のパーサーは simple selector のみサポートしており、複数のセレクターを や > や + などの結合子でつなげたものはサポートしていない。
ref. 結合子 - ウェブ開発を学ぶ | MDN

Part4: Style tree

Style tree は DOM の各要素にスタイル情報を付与したようなもの。
コードではスタイル情報は

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

/// A node with associated style data.
#[derive(Debug, PartialEq)]
pub struct StyledNode<'a> {
    pub node: &'a Node, // pointer to a DOM node
    pub specified_values: PropertyMap,
    pub children: Vec<StyledNode<'a>>,
}

というようにハッシュマップで持たせていた。

また、この specified_values を構築する処理は

/// 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());
        }
    }
    values
}

という関数でやってるんだけど、複数のルールが該当したときに詳細度が高いものが勝つように一度詳細度の低い順に並び替えてから順次ハッシュマップに insert、ということをやっていた（declaration.name が重複してるものは後の方で上書きされる）。

Part5, 6: Layout tree

Style tree から Layout tree を計算する。Layout tree は

struct LayoutBox<'a> {
    dimensions: Dimensions,
    box_type: BoxType<'a>,
    children: Vec<LayoutBox<'a>>,
}
  • box_type: 要素がブロック要素かインライン要素か（または none）
  • dimensions.content: コンテンツの x, y 座標と、縦横の大きさ
  • dimensions.padding, border, margin: padding, border, margin のそれぞれの上下左右幅

といった情報を持った木構造。

DevTools でよく見るこのボックスをイメージするとわかりやすい。

ここに、矩形左上の点の x, y 座標が追加されているイメージ。

ここの座標計算が一番複雑で、かつ元々このあたりの知識がなく理解が難しかったポイント。

  • ブロック要素は縦方向に並び、幅は親 (container) の幅いっぱいになる
  • インライン要素は横方向に並び、親の幅を超えそうになったら折り返す

という基本的なことに加え、ブロック要素とインライン要素が混在していた場合、インライン要素群のまわりに Anonymous Box と呼ばれるブロック要素が形成されるらしい。

（画像は記事より引用）

また、要素の幅に関しては親に依存するが、高さはその要素が包含する子要素の高さに依存する。
そのため、子要素の幅・高さを計算する際に親要素の高さに子の分を足し合わせるといった処理が必要になる。
それは layout_block_children() でやっている。

Part 7: Painting

"Rasterization"（日本語だと "ラスタライズ"？）と呼ばれる描画処理。
Layout tree から直接描画するのではなく、一旦 "円を描け" "テキスト文字を描け" のような描画に関するコマンド（ DisplayCommand ）のリストを作り、最後にそのリストの通りに順番に描画する。

なぜ一旦コマンドに変換するかというと、いくつかの理由がある。

  • 後続のコマンドで完全にカバーされるコマンドを検索し、取り除いて無駄な描画を排除できる
  • 一部の要素しか変更されていないことを知っている場合、コマンドのリストを変更したり再利用できる
  • 同じコマンドリストから異なるアウトプット(たとえばスクリーン用にピクセル、プリンタ用にベクタ)を生成できる

（"Building the Display List" の項を参照）