ブラウザのレイアウトエンジンを自作してみた
前々から自作ブラウザを作ってみたかったんですよね。作ります。
今回はブラウザのGUI周りの、主にレイアウトの座標計算モジュールを自作しました。CSS のボックスモデル, Flex, Grid の座標計算というのが伝わりやすいでしょうか。
HTMLパーサ/CSSパーサ/CSSクエリエンジン/ペインティングも一部実装しましたが、レイアウト可視化のテスト用と割り切っていて、ちゃんと作ったのは主にレイアウトの座標計算周りになります。
作ったもの
雑なプレイグラウンド
こんな感じです
Terminal で Sixel を描画して Google を表示したもの。今回は主に座標計算周りの実装なので background-color やフォント周りは未実装なんですが、矩形だけでは自分の目視デバッグもしんどかったので、最低限のビットマップフォントをレンダリングできるようにしました。
リポジトリ
npm:@mizchi/crater
wa.dev のWASMモジュール
というわけで、あとは作る過程と感想の話です。
先行事例の紹介
モジュラーなレイアウトエンジンの実装として有名なのは Yoga Layout Engine があります。React Native や Ink TUI の内部で使われており、主に flexbox の計算を担当します。
また、Rust 製の taffy という実装があります。これは Firefox Servo や Zed Editor などでも使われており、 flexbox だけでなく Grid も実装しています。
ただ、taffy はそれ自体でCSSを計算する能力は持ちません。これはCSSパースして、ユーザーの環境も含めて値を計算して、親子のカスケーディングによる影響も考慮して、最終的な固定座標を解決する必要があります。
CSSの計算は CSS Style Engine という層で、 Firefox/Servo で使われる Stylo が有名です。
Taffy + Stylo を組み合わせたものとして、Blitz があります。
自分が色々と試した結果、 Rust でブラウザを作りたいだけなら、Blitz の実装を参考にしつつ taffy や stylo を直接使うのが一番良さそうに思いました。
今回は勉強目的なのと、 Moonbit でスクラッチで全部書きたかったので、実装を参考にしただけです。
ゴールの設定
- yoga の代替として使えること
- TUI で Ink Alternative を作るための基盤にする
- Pure Moonbit で書くこと
- 今後の自分のために、別の実装に組み込むとことを想定してモジュラーに設計する
- js ビルドを npm で、 webassembly を wa.dev で配布する
実装手順
基本的に Web Platform Tests, WPT を通すことを目標にします。これは Chrome/Firefox/Webkit などに一般的なブラウザの互換テストに使われるテストケース集です。
コアの部分は自分で書くとして、標準に向けて実装するのはとにかく数をこなさないといけません。これはAIにとにかく頑張らせます。
AI があっても人間がやることは多く残っていて、優先して通したいテストケースの指定、ベンチマーク対象の指定、アルゴリズムの選択はユーザーの深い理解が必要になります。実装具合を見ながらこちらから指示を与えました。ChatGPT に既存の実装方法や最新の手法を調べさせつつ、コードを確認して修正していきます。
ただ、WPT は重箱の隅をつつくようなエッジケースが多いです。最初から WPT の通過を目指すのではなく、まずは taffy のテストを移植することにしました。
taffy のテストを移植
taffy の text_fixtures やテストケースをそのまま移植しました。
色々あってこんな感じです。
| Module | Passed | Total | Rate |
|---|---|---|---|
| Block | 204 | 224 | 91.1% |
| Flexbox | 547 | 607 | 90.1% |
| Grid | 266 | 331 | 80.3% |
Grid は複雑な仕様が多くてちょっと微妙ですが、まあ頑張れば対応していけるでしょうという感じ。
あと、これを作る過程で taffy 自体の仕様違反を見つけて報告したら、破壊的変更として修正する話になりました。
間接的に Servo に貢献できたことになるので、まあよかったです。
WPT: Web Platform Tests を通していく
ある程度 taffy のテストを通した段階で、WPT からレイアウト関連のテストをターゲットに含めて実装していきます。
- css/contain
- css/flexbox
- css/grid
- css/overflow
- css/position
現状、こんな感じです。
| Module | Passed | Total | Rate |
|---|---|---|---|
| css-flexbox | 148 | 234 | 63.2% |
| css-grid | 17 | 30 | 56.7% |
| css-sizing | 23 | 50 | 46.0% |
| css-overflow | 8 | 20 | 40.0% |
| css-position | 11 | 30 | 36.7% |
こういうテスト通過率で大丈夫か？と思うかもしれませんが、 やってないのは writing-mode の縦書きとか、プロポーショナルフォントのレンダリング結果(baseline)に依存するものが主に対応できてません。今の実装では座標の計算に等幅フォントを強く仮定しています。
趣味の範囲で作るには過剰なので、テストケースを見て取捨して実装しています。display: table なんかも実装を飛ばしています。
学び/苦労した点
WPT 通すのがしんどい！
WPT を通すのは、かなりしんどいです。正直、そんなエッジケースを考慮する必要あるか？みたいなテストケースが多いんですが、ブラウザの互換性を守るにはこれも必要なんでしょう。WPT の通過率は実用的な機能の網羅率とは全く別の話で、正直数件通っていれば一般的なイメージするブラウザの挙動は達成できます。
WPTを網羅するのは、なんというかWeb標準の執念の話になってきます。
ノードの再計算は最初から考慮した方がいい
ある程度パフォーマンスチューニングをしながら実装したんですが、特にパフォーマンス上有効だったのがレンダーツリーの部分的な再計算時の Double Dirty Bit です。
これはツリーに変更を与えた時、レイアウトの再計算が必要なノードにダーティフラグを建てておいて、その部分だけ再計算します。仮想DOMの計算をノードだけではなく、座標まで拡張した感じです。
Double Dirty Bit を導入して、計算済みのものをキャッシュすると、部分的に書き換えた際の再計算が7~20倍速くなりました。どのブラウザも同じような実装をしてるので、この実装は最初から考慮しておくのが良さそうです。
外因サイズ内在サイズ, CSS: Contain の有用性
CSSレイアウト計算の特に難しい点は、親からの指定によって計算される外因サイズと、自身の子要素によって内因サイズの二つを持つ点です。これによって、最終的な座標の確定に、親/子/自身と3回のパスを、それぞれのノードで行わなければいけません。
で、これを実装する過程で色々なプロパティについて調べ直す必要になったんですが、 contain 要素について思い出しました。これは内因サイズについて明示的に指定することで、そもそも再計算自体を抑制することができます。
俺が座標の最適化欲しかったのはこれじゃないか？と思って調べたんですが、なんか速くなるらしい、ぐらいの話しか出てきません。
というわけで自分で実装して、それを元に計算を刈り込みます。で、その時点で用意してた既存のベンチマークが速くなったかというと...変わんないですね。 Double Dirty Bit が既に十分効いてるので、変化なしです。
とはいえ全く意味ないかという、わざとらしい矩形がガタガタしそうなテストケースを用意すると、さすがに3~5倍速くなりました、適当に指定するんじゃなくて、プロパティの意味を理解してないと使う意味がないプロパティです。その意味では will-change なんかと同類です。
今後やりたいこと
JSビルドで gzip 80k, wasm ビルドも gzip 130kぐらいになので、標準の互換性はともかく、自分の求めていたポータブルなモジュールが手に入りました。再利用可能なモジュールになってるはずなので、このままブラウザを作ってもよし、 Ink 代替となるライブラリを作ってもよし、Sixel レンダリング路線で TUI で完結するUI開発環境を作ってもよし、という感じです。
自分が考えてるのは、GUI面を強化することより、AI向けにアクセシビリティを強化して、座標系は本文抽出やその補助に使うようにすることです。
作りながら考えたのは、レイアウトエンジンとCSSスタイルエンジンって実は綺麗に切り離せるので、ブラウザの制御を握ってるならCSSというフォーマット以外からレンダーツリーを生成してもいいんじゃないかと思いました。Cascadingなどの表現系はCSSという表現範囲に制約されてて、例えば2Dゲームエンジンなどに最適化するならもっと強い制約を置けるレイアウト体系を作ることもできます。
最後に、何より一番よかったことは、実装を通してブラウザの最適化やボトルネックについての考え方の解像度が二段階ぐらいあがったことですね。皆さんもブラウザを作りましょう。
Discussion