この記事は Chromium Browser アドベントカレンダー 24 日目の記事です。

内容の一部は Chromium の Git レポジトリの Source/core/dom フォルダの README ファイル (英語)が元になっています。README の想定読者は Chrome の開発者でしたが、この記事の想定読者は一般の Web 開発者です。 この記事の一部は README ファイルに還元(バックポート)する予定です。

この記事は詳細な API の使用方法などには深入りしません。雰囲気で理解するのを目的としています。 記事には読者への課題がいくつか含まれていますが雰囲気で理解するにあたって必須ではありません。

課題への解答・記事へのフィードバック・Typo などを発見しましたら GitHub Issue の方へお願いします。

DOM

DOM は Web の基本です。いってみれば Web を構成する原子のようなものです。

dom

個々の DOM オブジェクトは一般にノード (Node) と呼ばれます。 たとえばみなさんが今現在見ているこの記事に対して、ブラウザは約 700 個の DOM ノードを生成します。大規模な Web サイトはより多くのノードから構成されています。例えば YouTube のトップページは現在 約 3,000 個のノードから構成されています。

many dom

各 Web サイトが何個のノードからできているのかを確認するには querySelectorAll などの API が使用できます。 ブラウザの DevTools Console 上で以下のコードを貼り付けて実行してみましょう。ノードが何個あるかわかります。

console.log(document.querySelectorAll('*').length);

DOM はばらばらに存在していません。ブラウザ内部ではノードは木構造 (ツリー: Tree) を構成します。DOM ノードから構成される木のことをノードツリー (Node Tree) と呼びます。

node tree

例: HTML とノードツリー

たとえば以下のような HTML

<html>
  <head>
    <link style='hello.css'>
  </head>
  <body>
    <div>hello</div>
    <p>world</p>
  </body>
</html>

を読み込んだ結果、ブラウザは以下のようなノードツリーを内部に構築します。

node tree example

Chrome におけるノードツリーの実装

ツリー (Tree) はコンピュータサイエンスにおいて頻出するデータ構造です。ツリーをどのように実装するかは状況によって異なります。例えば:

  • 子ノードから親ノードへは辿る必要がないため、親ノードへのポインタはもたない
  • 親ノードにはすべての子ノードへのポインタを持たせる

などの選択肢があるでしょう。

Chrome のノードツリーの実装は以下のようになっています。

1. 各ノードは親ノードへのポインタ parent をもっています。

parent

2. 各ノードはすべての子ノードへのポインタはもっていません。もっているのは 2 つだけ、firstChild (最初の子供)・ lastChild (最後の子供)へのポインタをもっています。

firstChild and lastChild

3. その代わり各ノードは兄弟 (Sibling) ノードへのポインタ previousnext をもっています。つまり兄弟ノードは Linked List (連結リスト)として実装されています。

next sibling and previous sibling

合計すると各ノードには 5 つ (parent, firstChild, lastChild, previous, next) のポインタがあります。

このツリーの表現により Web で標準で利用できる多くの DOM API は定数時間 O(1) で実装が可能です。

課題 1: あなたが Chrome の開発者になったとしましょう。以下の DOM を操作する API:

をそれぞれどのように実装しますか? どのノードのどのポインタの更新が必要になるでしょうか? それぞれの API の動作はリンク先の MDN のドキュメントを参照してください。

ここでは実際に実装する必要はありません。擬似コードで十分です。

課題 2: 以下の JavaScript の関数 countNodes は「手作業」でノードツリーをトラバースしてツリーに含まれるノードの個数を数えます。 ツリーに含まれるノード数を N とした場合、countNodes(document) は実行時間が O(N)ではなく O(N^2) 時間がかかる可能性があります。それはなぜでしょうか? Node.childNodes の動作についてはリンク先の MDN のドキュメントを参照してください。
function countNodes(node) {
  let count = 0;
  for (let i = 0; i < node.childNodes.length; ++i) {
    ++count;
    const child = node.childNodes[i];
    count += countNodes(child);
  }
  return count;
}

console.log(countNodes(document));
課題 3: countNodes(document) の結果、得られるノード数は querySelectorAll('*').length で得られる結果と同じでしょうか? もし大きな違いがあるならそれはなぜでしょうか? (注: これは少し意地悪な問題です。思いつかないときは飛ばしてかまいません)
課題 4: あなたが Chrome の開発者になったとしましょう。Node.childNodes をどのように実装しますか?思いついた実装のメリットとデメリットをそれぞれあげてください。特にメモリ消費量への影響について考えてみましょう。
課題 5: countNodes() を改良しましょう。node.childNodes を使用することなく「確実に」実行時間 O(N) でツリーをトラバースする関数に修正してください。 必要に応じて Node の Web API を参照してください。
課題 6: 再帰を使用しないでノード数を手作業でカウントする関数を JavaScript で書いてください。

Hash Map (ハッシュマップ: 連想配列)

ブラウザはユーザーからのクエリに素早く答えるためツリーに関するさまざまな「情報」を別途もっています。

たとえば getElementById() は指定された id を持つノード(正確にはエレメント)を返す DOM API です。

例: 属性 id=foo をもつエレメントを返す

> document.getElementById('foo')
=> <div id=foo></div>...

ブラウザはこの DOM API が呼ばれるたびに該当 id をもつエレメントを見つけるために毎回ツリーをトラバースしているわけではありません。 ブラウザは id とノードの対応表を別途持っています。そのため document.getElementById() は定数時間 O(1) で応答可能です。

id to element mapping

これはほんの一例です。その他にもたくさんのツリーに関する情報を「キャッシュ」として持っています。 ただしいたずらになんでもデータ構造を用意すればよいというものではありません。時間と空間のトレードオフについては常に慎重に検討しなければいけません。

課題 7: このページに含まれる全ノードのうち id 属性がついているものはいくつありますか? 必要であれば Element.getAttribute() を参照してください。
課題 8: document.getElementById(id) に相当する JavaScript の関数 myGetElementById(root, id) を自分で作成してください。 その際、普通に JavaScript の Object をハッシュマップとして使用してもよいですが、比較的新しい API である Map を使用してもよいでしょう。
function myGetElementById(root, id) {
  // ...
}

myGetElementById(document, id);

tree order

課題 9: このページには id が重複しているノードがあるでしょうか?

この記事はほぼ静的ページです。最初に記事が読み込まれた後はツリーの構造は一部を除いて変化しません。 それに対して多くの Web ページの内容は動的に更新されます。つまりブラウザ内部で保持しているノードツリーの構造は常にアップデートされています。 そのためツリーに関する情報もなんらかのタイミングでアップデートする必要があります。ユーザーに古い情報にもとづいた間違った結果を返すことは許されません。

課題 10 (やや難): ノードツリーが更新されると、先ほどの課題8 で自分で作成した id と エレメントの対応表は古くなるでしょう。なんらかの方法で最新の状態を反映する必要があります。 どのタイミングでどのように更新するのがよいでしょうか?考えてみましょう。どうすれば更新のコストを抑えることができますか?そのためには何が必要になるでしょうか?

Super Tree (スーパーツリー)

ここまでは従来の Web でした。この状況は Shadow DOM の出現とともに様子を変えることになります。

Shadow DOM の詳細はこの記事ではカバーしません。ここではできるだけ簡潔に述べます。

(一定の条件を満たす)すべてのエレメントはエレメント「内部」に別のノードツリーを「ホスト」できるようになりました。 いままで Web の世界を構成する最小構成単位であった エレメント(原子)はその内部にもうひとつの世界をもつことができます。

shadow tree

ホスト側(外側)のツリーは Light Tree (光のツリー)、ホストされる側のツリーは Shadow Tree (影のツリー)と呼ばれます。

外側の世界と内側の世界は本質的な違いは存在しません。つまり Shadow Tree は同時に Light Tree にもなります。光と影はあくまで相対的な概念です。 外側の世界と同様に、内側の世界の各エレメントもそれぞれ内部にもうひとつの世界をもつことができます。この世界は何段にもネストできます。

super tree

モダン Web においては世界はノードのツリーから構成されるのではなく「ノードツリーのツリー」(= Super Tree) から構成されます。 あなたが見ている世界・つくっている世界は実は上の世界を構成するほんの一部分にしかすぎないかもしれませんし、あなたが利用しているエレメントの内部には膨大な世界が広がっているかもしれません。

例: Chrome での利用例

動画の再生に使用する <video> エレメントは Chrome は Shadow DOM を使用して実装しています。Web 開発者は <video> エレメントの中にもうひとつの世界が広がっていることを知る必要はありません。むしろ「知らなかった」という事実はうまくカプセル化が成功している証拠です。

他にも <input> エレメントなど多くのエレメントは Chrome 内部では Shadow Tree を使って実装されています。

video element

Divide and Conquer (分割統治)

さきほど出てきた id とエレメントの対応表はそれぞれのノードツリーごとに存在します。 そのほか、たとえば各ノードツリー内に定義された CSS のルールなどもそれぞれのノードツリー単位で独立に管理されます。 これらのルールの適用範囲はそれぞれのノードツリーのみであるため、サーチやマッチングの対象を大幅に限定できます。

tree scope

CSS の話がでてきたので次は CSS セレクタのデータ構造とマッチングアルゴリズムについて簡単に説明します。

CSS

少しの間 CSS に話を脱線しましょう。CSS の 各セレクタは Chrome では Linked List として表現しています。たとえば以下の CSS のルール:

a b .foo {
  color: red;
}

内に含まれる CSS セレクタ "a b .foo" は以下のように表現されます。

css selector

CSS ルール上では一番右に表記される .foo がリストの先頭であることに注意してください。Chrome 内部では CSS セレクタは Right-to-Left (右から左)の順番で Linked List として表現されます。 双方向リストではなく片方向リストです。

CSS セレクタマッチング

一部の特別な CSS ルールを除いてマッチングの処理はそれぞれのノードツリーで独立に行えます。

それぞれのノードツリーにおいて CSS セレクタとエレメントのマッチングは:

  • CSS セレクタは Right-to-Left
  • ツリー内のエレメントは (基本的には) Bottom-to-Top

の順序で行います。

例:

css selector matching

このように愚直にマッチングしていると Backtracking (バックトラッキング) が何度も発生してマッチングにかかる時間が O(2^N) (指数関数時間) になると思われるかもしれませんが、 実際は数々の最適化・ヒューリスティクルールにより現実時間で終わるようになっています。

そのうちのひとつ Bloom Filter をここでは紹介します。

例: Bloom Filter (ブルームフィルタ)

ブルームフィルタは確率的データ構造です。ある程度の False Positive (偽陽性)を受け入れることで極めて省スペースで「存在するかしないか」をチェックすることが可能です。 詳しい説明はここでは省きます。Wikipedia を参照してください。

Chrome では CSS セレクタフィルタ core/css/SelectorFilter 内でブルームフィルタを使用しています。

例えば id 属性を使用してフィルタを行う場合は、セレクタ内に登場する id をもつエレメントがツリーの先祖に「存在するかしないか」のチェックにブルームフィルタが使用できます。 多くのケースでは「存在しない」ことが確実にわかるため早期にセレクタマッチングを終了することが可能です。False Positive (偽陽性)レートは、仮にユニークな id が 100 あるとして 12 bits のスロットを使用することで、0.2% まで落とすことができます。

ブルームフィルタは Chrome では CSS セレクタマッチング以外にもマルウェアサイトの検出などでも使用しています。

課題 11: 以下のような CSS セレクタマッチングを実現する関数を JavaScript で擬似的に実装してください。selector としてどのようなものが指定可能かはおまかせします。 まずは例のように タグネームの配列のみでやってみましょう。
function selectorMatch(selector, node) {
  // ...
}

console.log(selectorMatch(['div', 'p', 'p'], getElementById('foo')));
課題 12: 先ほど作成した自作セレクタマッチングはどのような入力のときに時間がかかりますか?悪意のある入力を考えてみましょう。
課題 13 (やや難): Bloom Filter を課題 11 に組み込んでください。マッチングの実行時間は改善されますか?
課題 14: ブラウザの CSS エンジンの裏を書いてみましょう。Chrome が固まるような悪意のあるノードツリーと CSS ルールの組み合わせをつくることは可能でしょうか?ノード数 100、スタイルシートのサイズ 1KB という条件で可能でしょうか?

Event (イベント)

Super Tree に戻りましょう。一部の DOM Event (イベント) は Super Tree を駆け抜けてディスパッチされます。 たとえば下図のノード 1 がクリックされたとしましょう。

event dispatch

このとき、イベントの Bubbling フェーズでは:

  1. 緑のノードツリー: 1 -> 2 -> 3 の順
  2. (その後)水色のノードツリー: 4 -> 5 -> 6 の順
  3. (その後)一番上のノードツリー: 7 -> 8 -> 9 の順

イベントがディスパッチされます。 この際、カプセル化を壊さないようにイベントが下の世界(Shadow Tree)で起きたとしても、あたかも自分の世界 (Light Tree) で起きたかのようにブラウザはイベントを「書き換えます」。 たとえば、水色のノードツリーではあたかもノード 4 がクリックされたかのようにユーザーからは見えます( event.target の値が ノード 4 にアジャストされます)。

例: Tweet 埋め込み

Twitter が提供するツイートを埋め込みためのコードは、内部で Shadow DOM を使用しています。ツイート埋め込みコードは<twitterwidget> エレメントを生成しますが、実際の表示はすべて shadow tree 上で行われます。

tweett

<twitterwidget> がホストする shadow tree 内のどこかのノードがクリックされたとしましょう。このとき:

  • <twitterwidget> エレメントの実装者(つまりここでは Twitterのエンジニアのことです)はクリックされたのが「RTボタン」かあるいは「Like」ボタンかどうかを知りたいでしょう。
  • <twitterwidget>エレメントのユーザー(つまりツイートを埋め込みたいページの作者)から見た場合はそこまでの詳細は興味がないです。他の普通のエレメントと同様に <twitterwidget> エレメントそのものがクリックされたことだけ知ることができれば十分でしょう。

もし詳細が知りたいのであればクリックイベントといったローレベルなものを通じて知るのは極めてよくない API デザインです。必要に応じて抽象的できちんと定義されたインターフェース(たとえばカスタムイベント)を通じて伝えるべきです。

一部のイベントはそもそも上の世界に伝える必要がありません。たとえばページを訪れているユーザーがマウスを shadow tree 内のあるノード A からあるノード B に動かしたとします。 このとき <twitterwidget> エレメントの実装者はこの mousemove イベントを拾いたいと思うかもしれません。 一方 <twitterwidget> エレメントのユーザーから見た場合マウスはエレメントの内部を移動しているだけです。イベントは上の世界に伝える必要はありません。

例: 関連ターゲット (relatedTarget) をもつイベント

下の図でマウスポインタがノード A から ノード B に移動したとしましょう。

event related

このときは以下のように mousemove 関連のイベント はディスパッチされます。

  1. 緑のノードツリー: B -> 2 -> 3 の順。このときイベントのプロパティ:

    • event.relatedTargetA ではなく C
    • event.targetB

    すわわちこのノードツリーではマウスが C から B に移動したとみなされます。

  2. (その後)水色のノードツリー: 4 -> 5 -> 6 の順。このときイベントのプロパティ:

    • event.relatedTargetA ではなく C
    • event.target4

    すなわちこのノードツリーではマウスが C から 4 に移動したとみなされます。

  3. (その後)一番上のノードツリー: イベントはティスパッチされません。

Event Re-Targeting (イベントリターゲティング) / ノード間の関係の判断

このようにブラウザはイベントをあたかも自分のノードツリー内だけで起きたかのようにユーザーに見せるためさまざまなアジャストをおこないます。 これをリターゲティングと呼びます。イベントディスパッチの際にリターゲティングを素早く行うためにはツリー上でのノードの先祖・子孫関係 (Ancestor-Descendant relationships) を何度も判断する必要がでてきます。

例として次のようなノードツリーに対しては:

ancestor

  • A は B の先祖 ? -> Yes
  • B は A の先祖 ? -> No
  • A は D の先祖 ? -> Yes
  • B は F の先祖 ? -> No

等が成り立ちます。

課題 15: ノード間の先祖・子孫関係を判断する以下の JavaScript 関数を実装してください。
function isAncestorOf(ancestor, descendant) {
  // ...
}

console.log(isAncestorOf(a, b)) // -> true
console.log(isAncestorOf(b, a)) // -> false
console.log(isAncestorOf(a, d)) // -> true
console.log(isAncestorOf(b, f)) // -> false

isAncestorOf は素直に実装すると O(N) かかることでしょう。

ノード間の関係の判断 / O(1)

isAncestorOf は少しの工夫で定数時間 O(1) で答えることができるようになります。ただし以下の条件が必要です。

  • イベントの開始前に事前にツリーを 1 回だけトラバースしてもよい
  • 一時的に O(N) のメモリを消費してもよい

イベントディスパッチの開始前にツリーをトラバースして各ノードに以下のように2つの番号をつけることにしましょう。

pre post order

これらの 2 つの番号 (prepost) を利用すれば「A は B の先祖でしょうか?」 という問いには、

A.pre < B.pre && B.post < A.post

の条件をチェックするだけで済みます。これは定数時間 O(1) で判断できます。

課題 16: 先ほど実装した isAncestorOf を 実行時間が O(1) になるように改良してください。メモリはいくら使用してかまいません。どれくらい速度が改善したか計測してください?もし速度が改善しないようならなにが原因が考えてみましょう。

レンダリング

Super Tree はそのままではレンダリングできません。 「ツリーのツリー」 をひとつの「ツリー」に合成する必要があります。そのことを 「Flattening (平らにすること)」と呼んでいます。レイアウトのために平らになったツリーは Flat Tree (フラットツリー)と呼ばれます。

pre post order

Flattening のための詳細なデータ構造とアルゴリズムについては・・・もう十分でしょう。魔法すぎるので省きましょう。

ひとついえることは現在 Chrome は Flat Tree はメモリ上には物理的に保持していません。Flat Tree はあくまでコンセプト上に存在する仮想的なツリーであり、レイアウト時に仮想的に作成されます。

まとめ

この記事は主にデータ構造とアルゴリズムを通じて DOM と Shadow DOM を雰囲気で理解することを目的にしました。 課題に実際に挑戦してみた人は「エンジンの外側」の環境である JavaScript で問題を解く際に何かと不便に感じることが多かったと思います。 「エンジン内部の情報やエンジンがもっているデータ構造を利用できればはるかにいろいろなことができるのでは?」と感じたかもしれません。それはとても正しいことです。それこそがエンジン内部をハックする動機です。

明日の Chromium Browser アドベントカレンダー 最終日は実際のソフトウェアエンジニアリングにフォーカスした「Web のつくりかた: ソフトウェアエンジニアリングと雰囲気で理解する Web 標準とブラウザのつくりかた」です。お楽しみに。

Home | © 2005-2018 hayato.io