Virtual DOMのアルゴリズムが知りたくてvirtual-domのコードを読んだ話

DOM javascript

Reactの登場以来気になっていた、Virtual DOMアプローチの具体的な差分抽出手法について、virtual-domを読んで確認してみた。

Reactをいきなり読むのは面倒くさかった・ミニマムな実装から読みたかったというのが、こっちを選択した理由。Reactのアルゴリズムが参考にされているものの、Reactには存在する特定の最適化が入ってないかもしれないので、あくまでもReact系のVirtual DOMを実装するには最低限何が必要かを知る程度のものと判断してほしい。

virtual-domについて

ReactのVirtual DOM部分だけを切り出して再利用可能な形で再実装したライブラリ。elm-htmlとかMercuryといった箇所でvDOMインフラとして既に使われているので、まったくの趣味プロダクトという訳でもなくなっている。

README.md中での触れられている通り、Virtual DOM and diffing algorithmというコンセプトドキュメントをそのまま実装に落としたという感じで、実装自体はきわめて素朴。

実態としてはvtreeとvdomという依存パッケージのフロントエンドのような形式になっており、

  • virtual-dom: Virtual DOMの生成に使うh()という関数の提供と、関連パッケージのre-exportを行う
  • vdom: 出力されたパッチの適用と、Real DOMの出力を行う.
  • vtree: Virtual DOMの構造体とdiffの実装、パッチの出力を行う

のように、virtual-dom -> vdom -> vtreeのような依存関係になっている。

読んだリビジョン

全体的なコード感として、コード量自体は大したこと無いんだけど、コメントが少ないので読みにくい。最適化のためにこういうアプローチにしているのか、突貫作業の結果、こういうアプローチにしているのかよくわからん箇所も多い（Arrayではなく, Objectを数値をkeyとしたハッシュマップにしてリストとして取り扱っている箇所がある）。shapeを意識したコードにすることで高速化の余地もありそうだけど、そもそもコメントが無いのでその辺りの判断基準がわからない。ともすれば、実は何も最適化していないのかもしれない。whyの書かれたコメント重要な例ですね。この辺りはReactとはまったく対照的と言える。

可読性を考えると、TypeScriptとかRustとかgolangで再実装したくなってくる。

それと、テスト結果からは、どうもIE6もサポートしているらしい。たしかに、ES5相当の機能を使っている箇所は見当たらないので信頼しても良いとは思う（が、"use strict"も使わないとか、もう少しやりようはあるんでないの感もある）。

Virtual DOM 概観

構成要素

vDOMのtreeを構成する要素は基本的に2種類。VNodeかVTextの二種類しかない。他にもVWidgetとVThunkというtreeの構成要素があるんだけど、無くてもtreeもpatchも作れるし、具体的な生成方法とユースケースが見つからないので今回は取り扱わない。

VNodeは、ユニークidとして取り扱われるkeyプロパティを持つことが可能で、これを適切に設定してやることで後述する比較がより効率的になる実装となっている。が、必須ではない。 また、VNodeはcountプロパティを持っており、子孫ノードの数をこれ経由で取得できる。

ちなみにVTextはVNodeとは別物で、W3C DOMのように、TextがNodeインターフェースを持つということはない。要はいらんということなのでしょうな。なので、VTextの場合、単純な中身のテキスト比較で同一性の判定を行っている。

VPatchは、検出された差分をもとに生成されるパッチ情報。ここにあるように、要素単位でのノードの追加・削除・並び替えなどを表す。直和型でパターンマッチしたくなる感じの構造体ですね。

差分検出

参考元がVirtual DOM and diffing algorithmであり、それ自体がPerformance Calendar » React’s diff algorithmを元に記述されているので、当然と言えば当然であるが、アルゴリズムとしては、Event Delegationが無くツリー操作に限定している点をのぞけば、ほぼ同一。

ノードの変更

あるノードが変更された場合、原則として、そのノード以下すべてが新規ノードで置き換えられるようになっている（これはvtreeのパッチ生成だけでなくvdomの実装上の問題）。

だが、ノードのキーが同じかつ、localNameやnamespaceも同じ場合には、ノードの入れ替えではなくプロパティの更新のみで済ませることが可能.

ノードを階層ごとに比較

原則として、「rootからの階層が同じ」かつ「sibling内でのindexが同じ」ノード群を一塊と見なし比較を行うことで計算量O(n)で処理を済ませている。これは、比較するAB間でのすべてのノードを先頭から順に比較しようとすると、計算量がO(n3)となってしまうため。あくまでもツリーが極端に変更される（rootの子の構造がガラリと入れ替わる）ようなことが無いという前提で計算量を稼ぐ戦略。ツリー内のすべてのノードの変更履歴を追跡しているわけではなく、subtreeを別の位置（階層）に移動させるようなケースでは、移動されたsubtreeがすべて新規に生成されることになってしまい、差分描画する対象が増える。

各階層のsiblingの比較

各ノードのキーを元に、比較対象となるAとBの間でのノードの位置を検出し、Aでn番目のノードはbのk番目、のようなテーブルを作る。そして、並び替えの情報をパッチに持たせて、適用フェーズで並び替え。

キーが無くても並び替えできるけど新しい順序の構築の効率悪そう、というかキーを付けないケースがあるのでロジックややこしくなってる。

ちなみに消えた（消えるべき）ノードは別途削除用のパッチで消す。

ツリーをpreorderのリストとして取り扱う

パッチの適用箇所を高速かつ簡単に発見するために、ツリーは、preorderでの順番がindexとなる1次元リストとして見なされる。先述したように、各VNodeは保持している子孫ノードをcountプロパティ経由で取得できるため、リストをpreorderでトラバースする際、ノードAの隣のノードBのindexは、「Aのindex + A.count」で表現することができる。

生成したパッチを、このindexを添字にパッチのリストに対して追加することで、差分の適用先を的確かつ高速に発見できるというわけ（再帰も減らせる）。

パッチの適用

vdomのパッチの適用はReal DOMに対して直接行われる. 前述のパッチのリストに合わせて、DOMツリーをいったんpreorderのリストにし、それに対してパッチの適用処理を行う。

まとめ

  • 賢く変更結果を追跡し、変更箇所を最小限に留めるようなアルゴリズムではない
    • その分、探索時間を稼ぐ方向性
  • 断続的にDOMを変更していくのではなく、Window.requestAnimationFrame()などのタイミングで一気にバッチ処理的にDOMを変更することで描画への影響を減らすのが前提となっている
    • たしかVue.jsも似たようなアプローチだった気がする

だいたいこんな感じ。 そのうちReactも読んで固有の最適化パスとか持ってないか探してみたいけど、あれはあれで面倒くさそうな匂いがしてるので、どうしたものか……

追記: VWidgetについて

ツッコミを受けた。

diffアルゴリズムだけ気にしてて、それ以外興味なかったんで完全に失念していた……

VWidget

実装を見るに、Widgetとして独自のコンポーネントを定義できるものと思われる。

コードとして読む上で厄介なのは、VWidgetに関する定義は殆ど無く、vdomの実装からインターフェース（らしきもの）を読み取るしか無いということ（下のような感じ）：

逆に言えば、By designなインターフェース通りに値を返せば、内部的に何をしようが（Virtual-DOMを全く使わなくても）特に問題はない模様。

Servoの現状（2014年Q2）

Servo

Servoの現況概説的なおはなし - snyk_s logの方を未だに参照されてる人がなんか多いみたいなので。

スライド自体は先日のブラウザエンジン先端観測会で使ったものそのものなんだけど、2014年Q2現在の現状としてはこっちの方が正確です。

LL Diver 夜の部『帰ってきただめ自慢』に #Rustlang 枠として参戦します

Rust

今年2014年のLL Eventである、LL Diverの夜の部、『帰ってきただめ自慢』にRust枠として出演する事となりました。

僭越ながら、日本Rust界の大家であるMasanori Ogino氏を差し置いての参戦となりますが、他の日本○○界を代表する歴々に負けずに、ぜひともRust党の存在感をアッピールし、時代をRust色に染め上げられればと思う次第です。

こういう場はプロレスでございますので、「Rust will replace C++, YEEEEAAAAAAAAHH!!!!!」と叫んだところでD言語にドロップキックを食らい、C++闇の軍団に一斗缶で殴られるというお約束が果たせるかと思いきや、どちらも参戦されてないので期待してくださっている皆様には申し訳有りません。文句は@smellman氏までお届けくださいませ。とりあえず俺のせいじゃない。

それでは皆様、他の各種イベントと日程的に被ってはおりますが、ぜひとも観戦いただければ幸いです。

会場であなたとRust! 今すぐダウンロード！

Windowsを使うWebフロントエンドエンジニアだった頃の道具一揃え

Windows Web

前職ではWindowsを使ってWebフロントエンドエンジニアをやっていたんだけど、そのときに自分の開発機に入れていたツール群とかを徐々に忘れてしまいそうだったのでメモを兼ねて書いてみる。Web系=OSXということでノウハウがどれもWin向きではないということで困っている人がいると思いますし、そういう人のお役に万が一でも立てれば幸いです。

背景

自分の当時の背景はこんな感じ。こういう基準・背景でコードを書いてた。

  • 自分は、もっぱらクライアントサイドでJSを書いてた
    • モバイルよりもレスポンシブデザイン向けにコードを書く方が多かった
  • 全てをコマンドラインとかエディタで済ますのが好きではない
  • ツールは概ね好き勝手に入れて問題なかった

入れてたもの

（OfficeとかAdobe CSは除く）

エディタ：Vim

Vimで問題ない人間なので。IDE性とかも特に求めてないので、プラグインとかも自動補完とsyntax highlightだけ入れてた。

日本語はもっぱらメモ帳にMarkdown形式で書いてたなー。Adobe Bracketsとかも入れてたけど、Markdownのプレビュー以外には使わなかったし、大抵はメモ帳かVimで書いた物をpandocで整形してHTMLとかにしてた。

ローカルプロキシ：Fiddler

WindowsでWebフロントエンドやるなら入れておいて損は無い。というか、自分はこれがあるので、Webフロントエンドの開発は間違いなくWindowsの方がやり易いと思ってる。

AutoResponderで稼働中のサイトをデバッグしたり、VMをつないでHTTPキャプチャ機能付きのリバースプロキシ代わりにも出来るので本当に重宝する。

msysGit

WinでGitと言えばこれでしょう。職場のVCSはSVNだったんだけど、git-svnを使えば、「リモートリポジトリが（SVNで）中央集権的に運用されている」スタイルになるだけで、gitのワークフローに載せられたので問題なかったかな。

Git Extensions

Gitの殆どの機能が使えるGUIクライアント。ログビューアと、git-svnに伴うブランチの複雑なリベース・チェリーピックのために使ってた。これのおかげで、Winでtigは使った事が無い。

WindowsでGit使う人間であれば、とりあえず入れておいていいアプリケーションだと思います。Gitに関してなら、SourceTreeやGithub for Windowsよりもこっちを使った方が便利だと思ってます。

mozilla-build

Mozillaのソースツリーのビルドツールなんだけど、*nixなツールが一通り入ってるんで、これを入れて、中のバイナリを色々交換して使ってた。MsysGitに入ってくるものと組み合わせると色々できる。

nkf

Windowsと言ったら、文字コード・改行コードで手間取るよね。

ファイラとかランチャとか

Windowsのタスクバーとスタートメニューで十分でしたね。

Node.js

これが無いと今日のWebフロントエンドは開発にならない。 esprimaを-gで入れて一緒に入ってくるesvalidateコマンド使ったり、escodegenを同じく-gで入れて、変態記法なコードの整形に使ったりした（ただし頻度は少ないし、そもそもgulpとかでLint回せばどっちも要らないよね）。

具体的にどういうモジュール使ってたかはWindows固有の問題じゃないので置いておく。

jq

だいたいFiddlerで解決するんだけど、たまに生のJSONファイルを読まないと行けない時があった。

modern.ieで配布されてるVM一通り

だいたい全部ローカルに保持して、全部に一通りFiddlerをインストールして使ってた。

用途はもちろん検証で、ゲストPCをホスト側にブリッジ接続して、Fiddlerをリバースプロキシの代わりに使ってホスト側で動いてるtestemにつないで、HTTPをキャプチャしつつユニットテストを走らせたりしてた。

Win8以降のProfessional/Enterpriseなら、Hyper-Vが使えるので、それ使えば良いと思う。なければVirtualBoxやVMwareないしは、Virtual PCになると思う。VMWareの方が動作は速いんだけど、所詮検証用なので速度はそんなに欲しくなかったのと、有料ライセンスなソフトをインストール時に申請出さないといけなくて、それが面倒くさくて自分はVirtual PCで済ませてた。

各ブラウザの開発版

開発版じゃないとDeveloper Toolsの最新機能使えないし。

検証用にstable channelも入れてたけど、だいたいNightlyとかCanaryって名前のついてる物で開発も全部やってた。 IEも例外無く、Developer Tools目当てで開発機の上ではバージョンを上げられるまで上げてた。

検証の方は、だいたいVMと検証用のマシンで済ませる感じ。 JSのユニットテストだとロジカルなんでVMで済むケースが多いんだけど、レイアウトの検証になると最近のブラウザはハードウェアアクセラレーションが絡む（=ドライバの問題があるVMでは不確実）ので、品質管理部門と同じ検証用の実マシンで最終確認したりしてた。

だいたいこんな感じでした。 もう少し一般的な路線で言うと開発者がSurfacePro3を買ったらまずやること - Qiitaあたりも参照すれば良いのではないかと思います。

JS界隈にIDLもしくはd.tsを併記・同梱する文化が根付いてほしい

Web javascript

前置き

最近、ウェッブフロントエンドエンジニアらしく各種JavaScriptのライブラリを眺めて、調査・選定しているのだけれども、その過程を通じたこととして、多くのライブラリが、ドキュメントのAPIの説明が貧弱すぎる。

jQueryのドキュメントが腐っているというのは既に広く知られた事実であると思うし、そうでないならば積極的に既知の事実として腐っている事を広めて行くべきであると強く思うが、jQueryに限らずとも、ドキュメントが満足な形で整理されていないのをひしひしと感じる。

この手のものでよくドキュメント化されている部類だと感じるBackbone.jsですら、仮引数の名称と定義のみしか書かれておらず、肝心の引数が備えるべきメンバや、引数の型情報が明示的に記述されていない。そのため、APIを俯瞰し、自分の欲しい情報がどこに詰まっているのか・どのように取得できるのか・DOM標準もしくはECMA262標準との対応がどのようになっているのかを眺めて確認するのが困難だと痛感している。

MarionetteやChaplinなども割とマシな部類ではあるし、プリミティブな値についてはbooleanなどのように表記がなされているが、eventなどのような引数に成ると、DOM Eventなのか、Backbone.Eventsが飛んでくるのかを、文書のコンテクストを咀嚼した上で解釈しなければならなかったり、使い方・思想と混在してAPIが語られているので本当に読みにくい。

この点、Vue.jsなどは、APIのドキュメントが引数の型を明示している、かつドキュメント事態の記述が明瞭簡潔なので、かなりマシな方。個人的には、Objectなどのようにざっくりと書くよりは「最低限このメンバを持って居てほしい」ということでinterfaceを定義するなりしてほしいのだけれども、他が酷すぎるのと、JavaScriptの動的な性質を鑑みると、この水準があれば足る、一種の均衡点だと思う。

主張

私が主張したいのは、ライブラリを公開するにあたっては、APIのシグニチャだけでいいので公開しておいてほしいということ。大層なHow to UseやBoilerplateなどは無くてもいい。ただ、ライブラリの設計哲学とAPIの一式をIDLまたはTypeScriptのd.ts、最悪はコード中のJSDocの形式で表現しておくようにしておいて欲しいということ。どうせGithubもしくはBitbucketにホスティングするのだからmarkdownで簡単に書けるはず。

それを言い出すとECMA262仕様はどうなんだというツッコミが入りそうだけれども、あれに動的型付け言語でFunction.prototype.callで任意のコンテクストを伴って呼ばれうる関数が大量にあることを考えると仕方ないのではないか。むしろ、Function.prototype.callで任意に呼びされる可能性も無く、そんなことをすると確実に挙動が壊れるAPI設計をしていて、おまけにJavaっぽくクラスだのなんだのと名乗るお前のライブラリにIDLが無い事の方が問題。

JavaScriptで記述されるアプリケーションが複雑化するに伴って、単にJITコンパイラに対して情報を提供するという以上に、静的検査などを用いて複雑性の軽減を図るために、JSの世界でも「型」という情報は重視・一般化されつつあるのが現状である。Closure Compiler, TypeScriptなどはその急先鋒であるわけで、ES7には、ES6からpostponeされたTypedObject（構造体定義の導入）がproposalとして上がっていることを考えると、JSにおける型情報の提供というのは希求されているものであることが伺える。

こうした現状を踏まえた上で、理想であれば(Web)IDL, せめてTypeScriptのd.tsによるインターフェースの情報を提供するのが一般化してほしいと強く願う。

結論

とどのつまり、オサレな配布ページをgithub pageで作成するような暇があるのならば、README.mdの一部にAPIってセクションを貼って、IDLを書いて載せろということです。

ServoのDOMバインディングの話

Servo browser

Servoのリポジトリ内にDOMバインディングのデザイン覚え書きを投入したので、現時点での設計について、そろそろ日本語で説明しておく（英語版は結構前からServoのWikiに書いています）。

この記事の中で使うSpiderMonkey API用語は、結構古いものだったりするので、そこに注意（ServoはFirefox 17とかその辺りのSpiderMonkeyを使ってる）。

ブラウザにおけるDOMバインディングとは

この分野については、エデンの園でおきたこと - steps to phantasienという名記事があるので参照されたし。WebKit Chromium port時代のBlinkの話だけど、だいたいどのブラウザでも似たような問題を抱えていて、それぞれ微妙に異なるアプローチで解決している。

改めて私の言葉で要約してみると、「現代の実用的なブラウザエンジンというものは、自身の保有するDOM構造をJavaScriptなどの言語から操作可能にしている。使う側からすれば便利極まりない仕組みだけれど、ブラウザエンジン側にしてみると結構悩みの種。なぜなら、ブラウザエンジンは一般的にC/C++のような自前で参照関係を解決する種類のメモリ管理を必要とする世界であるのに対して、その構造を操作することになるスクリプト言語はだいたいエンジンが専用GC機構を持ち、その機構によってメモリの生存期間が決まるような言語仕様になっているから、これを巧くつなぐ仕組みが必要になる」ということ。

（関係ないけど、モダンなブラウザエンジンのDOMバインディングについて日本語で情報を求めると、だいたいomoさんが、その昔に書いた物にぶち当たる。本当にお世話になっています）

さて、こうした面倒くさい問題に対して、各ブラウザエンジンは幾つかのアプローチで対処している。OSSな実装で言うと：

といった感じ。

IEは、Exploring IE9's Enhanced DOM Capabilities - IEBlog - Site Home - MSDN Blogsによると、IE8まではCOMベースのバインディングを使用していたものの、IE9でChakraと密にバインディングするようにしたらしい。とにかくアーキテクチャ的にもIE9以降は違う感じはわかる。

Servo のアプローチ

上に挙げたアプローチはどれも巧いこと回っているものの、どうせならJSエンジン側のGCで全部を管理するようにしてしまいたい。Cycle Collectorを再実装したくはないし、余計な謎マクロとか色々実装したくはない。

というわけで、本題。「ServoのDOMバインディングは、どのようにオブジェクトの生存に関わる問題を解決しているのか」。答えは単純で「SpiderMonkey GCに全てを任せている」。もちろん世代別GCにも対応済。やったね！

Servoのアプローチその昔: dom.js

先述のエデンの園でおきたことでは、ServoはSpiderMonkey GCにDOMの生存管理を任せる為に、dom.jsを使うらしいと2012年末当時の観測結果として書いてある。が、現在はこの方法を使っている訳ではありません。

とりあえずdom.js路線について自分の知っている範囲の説明をする。実は、この時代は自分も知らない。今よりも、もっと実験実験してたプロジェクトの頃だし、自分もコミットチャンスを見つけてやり始める前。具体的に実装が動いていたのかもわからない。が、どちらにせよ、2012年末頃の時点では、dom.jsでDOMのデータ構造そのものをJavaScriptでself-hostしようとしていた、らしい。

原理的には一番オーソドックスにSpiderMonkey GCの恩恵を受けられる訳だし、self-hostでおなじみの効果として、DOMデータ構造そのものに対してJITが立ち入れるので、理論上はJITコンパイラによる更なる最適化のチャンスが増える。現代のフロントエンドWebプログラミングの最大の速度障壁はDOMの遅さであるので、そこの速度向上がワンチャンなので、一見すると、筋のよいアプローチに見える。

が、実際には、この試みは断念される。過去のmeeting noteを色々参照したところ、理由は単純にパフォーマンス + 複雑性の問題の様子。JS側と（文脈的にレイアウト用の）DOMの2つのレイヤーツリーを持って、常に同期し続けなければならない。ましてや並列性を狙ったエンジンなので、コードが本当に複雑になるのは想像に難くない。

具体的に何のパフォーマンスが悪かったのかは追跡できなかったのだけど、私の推論としては、おそらくは2つのDOMツリーを作る過程で発生するメモリコピーが要因ではないかと感じる。Webページを1つパースすると、だいたい数百〜数千の単位でDOMの領域のデータ構造がつくられる。これがJSオブジェクトで作成され、しかも同様のツリー構造をもう一回作るとなると、かかるコストは結構なものになるのではないかと。

何はともあれ、この路線は挫折することになる。

SpiderMonkey APIを通してDOMを管理する

というわけで、現在の路線はSpiderMonkeyのAPIに従って、ラッパーオブジェクトの生死に合わせて、RustなDOMオブジェクトの生存を管理する方法を取っている。

全体のデザインはjdmによるもので、ここに書くものはコードから読み解いて、本人に直接確認した内容の覚え書きみたいなもんです。

基本的なライフサイクルについて日本語で書くと以下の通り（英語で書いたのを殆どそのままです）：

前提: RustのDOMの構造

Rustには、別の構造体のデータ構造を継承した構造体をビルトインで定義する方法が無いので、Cでクラスなデータ構造をやるような手法が用いられている。また、後述するGCからのトレースの為、GC管理対象のDOMオブジェクトをJS<T>という型のメンバとして保持している：

// BarがFooを継承している場合の構造体の図
struct Bar {
    foo: Foo, // 先頭に基底クラスを格納する
    field1: JS<Hoge>, // SpiderMonkey GCの管理対象
    field2: int, // SpidrMonkey GCの管理対象でないもの
}

こうした構造体全てに対して、WebIDLから継承関係に応じたTraitを実装することで、どの型からどの型に対してのキャストが可能なのかを属性として付与している。詳しくは dom::bindings::codegen::InheritTypes.rsを見てください。

DOMの生成時

ServoがRustのオブジェクトを生成するとき、bindingコード（CodegenRust.pyによってWebIDLから生成されたglueコード）は、ラッパーオブジェクトとなるJSObjectを生成し、これに対するポインタを自身のReflectorフィールドに格納する。このラッパーオブジェクトはもちろんDOMと完全に一対一になるように生成され（でないとJSの比較演算子が変なことになる）、生成と同時に、対応するDOMオブジェクトへのポインタを自分の中に格納する。これで対応関係の出来上がり。

SpiderMonkey GCの管理下に入るDOMオブジェクトは全てが最基底な位置にReflectorというフィールドを保持しており、ここがラッパーオブジェクトとの対応関係を作っているわけですね。

ちなみに、このようなライフサイクルを作る都合上、Servoでは全てのDOMオブジェクトの生成時に、対応するラッパーオブジェクトの全てを同時に生成している。GeckoやBlinkの場合は、JS側からDOMにアクセスしたタイミングでラッパーオブジェクトを作っているが、それらのアプローチと比べるとServoの方が初期段階ではメモリを使っているはず。と、同時に、Servoのアプローチの方が世代別GCの影響が色濃く出るだろう。ページロードの瞬間からすべてのDOMに対応するJSオブジェクトが生成されているのだから。

DOMのオブジェクトグラフのトレース

このように生成したDOMのオブジェクトグラフ上をSpiderMonkey GCが歩けるようにするために、Rustの言語機能をかなりトリッキーに使ってる。

  1. SpiderMonky GCはマーキングフェーズ時に、それぞれのbindingコード内に定義された各ラッパーオブジェクトの定義元のJSClass.trace()を呼び出す。
  2. JSClass.trace()は、InhertTypes.rsの定義に従って、Foo::trace()を呼び出す。
  3. Foo::trace()は今度はFoo::encode()を呼び出す。このFoo::encode()は#[deriving(Encodable)]によって、コンパイラに自動生成されたもの。現在の設計ではDOMをEncodableとして扱う目的が無い + 下手なマクロよりも確実に展開されるという前提に立っているのでこのアプローチを採用している。
  4. Foo::encode()は、メンバとして格納しているJS<T>のJS<T>::encode()を呼び出す。
  5. JS<T>::encode()からdom::bindings::trace::trace_reflector()を呼び出す。
  6. trace_reflector()は、対応するラッパーオブジェクトをJSTracerに伝える = GCに伝える。
  7. 1~6までの操作を、オブジェクトグラフの終点まで延々と繰り返す
  8. 最後に、Rustのオブジェクトグラフを全部通り抜けた結果、どのオブジェクトが死ぬべきかがわかるというわけ

DOMの破棄

こうしてトレースした結果から、ライフサイクルを終えたと判別されたDOMは破棄される必要が有る。

この破棄ロジックは非常に簡単でラッパーオブジェクトの破棄タイミングに、JSClass.finalize()が呼び出され、そこからbindingコード内のFooBinding::_finalize()が呼びだされる。このメソッド内では、ラッパーオブジェクト側に格納しているRustオブジェクトのポインタが、Rustのowning pointerにキャストされ、空の変数に代入される。Rustの流儀に則り、ここでライフタイムが終わる = ポインタが指し示すオブジェクトも安全にデストラクトされるというわけ。

SpiderMonkey GCのExact GC Rootingへの対応

ここまでは基本的な動きについて話してきた。この他に、SpiderMonkeyは世代別GCを実装するにあたり、Exact (precise) GC方式に移行しているので、それへの対応が必要になっている。これに辺り、Servoでは、4種類のJS Managedな型を導入している

  • JS<T>は、前段でも述べた通り、RustなDOMオブジェクト内に保持されるDOM型のメンバを表す型。内部的には、格納対象のRustオブジェクトへの生ポインタを保持しているだけだったりする。GCによって再帰的にトレースされる対象。
  • Temporary<T>は、DOM型を返す必要があるメソッドの返り値として用いられる（典型的なのはDocument::getElementById()とか）。これは内部に対応するラッパーオブジェクトへのポインタを含んでいるので、SpiderMonkey GCのConservative Stack Scannerによってスキャンされる対象になり、結果、この型の値が生きている間、GCのrootとなる。ただし、SpiderMonkey GCはRootの選定にあたりLIFOの順番を保証する必要が有るのだけれど、メソッド間で値が移動するため、その順序が崩れてしまう場合がある。そのため、Root<T>という後述の型を導入することで、うまくそこを回避（保証）することにしている
  • Root<T>は、Temporary<T>同様にラッパーオブジェクトへのポインタを保持している。これも同様にConservative Stack ScannerによってスキャンされることでGC Rootとなるのだけれども、先述のLIFOの順番を守るようになっている。トリックとしては、RootCollectionというリストを用意して、Root<T>の生成時にこれに登録していく。スコープを抜ける際に、生成されたRoot<T>はLIFOで破棄されるはずなので、破棄タイミングでアサーションを仕込んでRootCollectionからも取り出すようにして、LIFOな順番を保証するようにしている（ただ、Rustの言語挙動にかなり依存している面は否めない……）
  • JSRef<T>は、Root<T>に対する単純な参照。なんども無駄にRoot<T>を生成したくはないしね！

とまあ、ざっとこんな感じになる。 こうやって、ServoはSpiderMonkey GCにDOMの生存管理を丸っと任せているというわけ。

Servo DOM bindingの今後

第1に、SpiderMonkeyを現在使用しているGecko 17相当から、Gecko 3x相当までアップグレードする必要が有る。性能試験という意味でも、先述した世代別GCの効果測定の意味でも、流石に古いままではテスト対象として微妙だからだ。

第2に、SpiderMonkeyに対してGC Rootを伝える方法の改善。今のようにStack Scannerが辿るよりも、明確にどれがRootであるのかを示すようにした方が良いのは言うまでもない。

第3に、JSObjectの中にRustオブジェクトを格納する。たしか、一発でアロケーションできるようにしたいとかそんな感じだったはず。しばらく全然進捗ないし、自分も昔一回見たっきりなので、効用までは詳しく追ってません……

第4に、DOM APIの実装。そもそも実装してるAPIがまだまだ足りないので、全然ベンチマークも取れないという問題が有るので、ゴリゴリ実装して行かなければ。

だいたいこんな感じ。こうやって構築したDOMツリーに対して、レイアウト側からどのようにさわっているかについては、そのうち書ければ書きたい。

Web ComponentsとHTMLのセマンティクスと自分の将来予測

a11y Web
  • Custom Elements W3C Editor's Draft 18 June 2014を元に書いた。
  • 昔、関連仕様のどこかで今回と似た話を見た記憶が有るんだけど、どこにあったか忘れたので、改めて自分の解釈として書いてみる。

Custom Elementで既存の要素を拡張する

Web ComponentsのCustom Elementは独自の要素を定義することができるのだけど、新要素の導入以外にも、実際には既存の要素を拡張するという使い方ができる。

ElementRegistrationOptionsの、extendsプロパティというのがそう。

specの例では以下のようにp要素を拡張している（引用）：

document.registerElement('x-foo', {
    prototype: Object.create(HTMLParagraphElement.prototype, {
        firstMember: {
            get: function() { return "foo"; },
            enumerable: true,
            configurable: true
        },
        // specify more members for your prototype.
        // ...
    }),
    extends: 'p'
});

var foo = document.createElement('p', 'x-foo');

<p is="x-foo">Paragraph of amazement</p>

セマンティクスとの兼ね合い

this element does not introduce a new tag (like the custom tag elements do)とあるように、type extensionsと呼ばれる既存要素の拡張では、新規の要素を導入するのではなく、既存の要素を拡張することになる。よって、要素のセマンティクスも引き継がれることになる（と解釈している）ので、構造化文書としてHTMLを記述する上では、安易に新しい要素を定義しない方が良いように思う。

また、要素が本来持つ機能・ないし支援技術サポートをそのまま引き継げることになるので、ちょっと見た目を弄る（CSSを組み合わせたパーツ）ようなものであっても同様だろう。もっとも、Shadow DOMと組み合わせてDOMイベントなどの制御を考えだすと逆に魔窟かもしれないが。

この辺り、実装がどのようになっているかは把握していないし、現行のWeb Components関連仕様全てを詳細に把握しているわけではないので、間違いがあったら御容赦願いたいです。

Web Components (Custom Element)の個人的な将来予測（雑感）

Web Componentsが流行した先の未来予測として、「コンポーネント化の仕組みが整備されることで、大コンポーネント時代のような時代が訪れるのではないか」という将来予測がある。それは概ね正しく、かつて一世を風靡したjQuery Pluginの百花繚乱時代がより洗練されて帰ってくるようなものなのだろう（コンポーネントのショーケースの到来については、興味も無いし、まだ始まったばかりなので言及しない）。

ただ、その一方で、それはjQuery Pluginが歩んだ負の道筋も同じように繰り返すのではないかとも予測している。今度こそ良貨が悪貨を駆逐するのかもしれないが、自分はその方面にはあまり期待をしていない。jQuery Pluginという歴史と、JavaScriptという文化圏がコンポーネント足りうる小粒のライブラリの決定版を生み出すことができずに、結局はフレームワーク頼みとなっている現状を振り返ると、そびえたつゴミの山は再び作られるのではないか。そうしたゴミの山の悉くは、実装もクソでAPIもクソでアクセシビリティとかも無考慮で、使用法を理解するよりも再発明した方が時間の節約なものの方が多いのではないか、WAI-ARIAもWCAGも全てが捨ておかれ、美しいエコシステムは到来せず、一部の泊のついたフレームワーク一門を使うか、自分で使うか、という何も変わらない世界が来るのではないかと悲観的になる。

Web Componentsの価値は、全てがグローバル空間に剥き出しだった断片が、コンポーネントとして整然と利用可能になるインフラストラクチャが構築されることにこそあり、端的に言えばShadow DOMのイベントのリターゲティングにこそあるという事実がもたらされるのだと考えれば、それだけで十分で、文化圏のエコシステムがまた破滅したとしても、問題ないのかもしれない。