DOMツリー構築の裏側：ブラウザの腹の内を覗く
フロントエンドエンジニアの日常は、しばしば「仮想DOM」や「フレームワークのリアクティビティ」という抽象化された高層ビルの中で営まれている。しかし、ひとたびパフォーマンスのボトルネックに直面し、メモリプロファイラやPerformanceパネルのタイムラインを睨みつける時、私たちが向き合わなければならないのは、ブラウザのC++（BlinkやWebKit）の地べたを這うような実世界だ。
今回は、その中でもHTMLパーサーが吐き出した「トークン」を、いかにしてメモリ上で生きた「DOMツリー」へと昇華させるか、その泥臭くも洗練されたツリー構築アルゴリズムの深淵に迫る。
W3CやWHATWGの仕様書を開けば、そこには「Tree Construction（ツリー構築）」という果てしなく複雑なステートマシーンの迷宮が広がっている。なぜブラウザは、あんなにも巨大でいびつなHTMLを前にしても、クラッシュせずにページを描画できるのか？ その秘密は、HTML5仕様が定めた「フォールトトレランス（障害耐性）」の狂気的なまでの作り込みにある。
—
トークナイゼーションからDOMノードへの昇華
ネットワーク層からTCPセグメントとして流れてきたバイト列は、Decoderによって文字エンコーディング（通常はUTF-8）に変換され、Tokenizer（字句解析器）へと送られる。Tokenizerの仕事は単純明快だ。文字のストリームを監視し、``, `
しかし、ここからが本番だ。Tokenizerが生成した `StartTagToken` や `EndTagToken` を受け取り、メモリ上に `Node` オブジェクトのインスタンスを生成し、ポインタを張り巡らせて親子関係（DOM Tree）を構築するのが Tree Builder の役割である。
オープンエレメントスタック（The Stack of Open Elements）
DOMツリー構築のアルゴリズムを語る上で欠かせないのが、「オープンエレメントスタック」という概念だ。これは単なるLIFO（後入れ先出し）のデータ構造ではない。現在パース中のコンテキストにおいて、どの要素の内部にいるのかを追跡するための、ブラウザの「現在地を示す羅針盤」である。
HTMLのパース中、パーサーはこのスタックを常に操作している。
1. 開始タグ（Start Tag）に出会うと、対応するDOMノードが生成され、現在の親ノードの子としてアタッチされると同時に、このオープンエレメントスタックのトップにプッシュされる。
2. 終了タグ（End Tag）に出会うと、スタックを上から走査し、一致する要素が見つかるまでポップしていく。
このスタックの存在により、例えば開発者が `
—
HTML5仕様が定める「狂気のエラーハンドリング」
プログラミング言語のパーサー、例えばC++やTypeScriptのコンパイラであれば、構文エラー（Syntax Error）の瞬間にビルドを中断し、赤いエラーメッセージを吐き出して停止する。
しかし、Webの歴史とHTMLパーサーは違う。「Broken HTML（壊れたHTML）」の救済こそが、初期のWebを爆発的に普及させた原動力であり、その代償としてHTML5のツリー構築アルゴリズムは、世界で最も複雑なエラーリカバリの仕様を持つことになった。
不正なネストの自動修正（Adoption Agency Algorithm等）
例えば、次のような「ありえない」マークアップを考えてみてほしい。
ここは段落です。
常識的に考えれば、`
` タグの中に `
` の前に `
` を閉じるべきところを、逆に閉じている）。
もし、これを素朴なアルゴリズムでパースすると、DOMツリーがグチャグチャに破壊され、メモリリークや予期せぬスタイルの崩壊を引き起こす。ここで発動するのが、仕様の最難関の一つである Adoption Agency Algorithm（養子縁組エージェンシー・アルゴリズム） や各種の暗黙的な終了・挿入ルールだ。
ブラウザは以下のように振る舞う。
1. `
` の中に `
` はブロック要素を含めないルールだ」と検知する。
2. 自動的に暗黙の `
` を挿入し、オープンエレメントスタックから `
` をポップする。
3. その後、`
この裏側では、C++のコードベース（Blinkの `HTMLConstructionSite` など）で、ノードの切り離しと再アタッチ（`appendChild` や `insertBefore` に相当する内部操作）がミリ秒単位で高速に実行されている。
—
メモリ効率とパフォーマンスの最適化：上級エンジニアが知るべき現実
このDOM構築フェーズは、Webアプリケーションの初期表示パフォーマンス（TBTやLCP）に直結する。特に、数千〜数万個のノードを持つ巨大なDOMを構築する場合、ブラウザのメモリ管理とメインスレッドのブロックが深刻な問題になる。
1. メモリフットプリントの削減と隠しクラス（Hidden Classes / Shapes）
V8などのJavaScriptエンジンにおいて、オブジェクトのプロパティアクセスを高速化するために「隠しクラス」が使われるのと同様に、ブラウザのC++レイヤーでもDOMノード（`Element` や `HTMLElement` のサブクラス）のメモリレイアウトは高度に最適化されている。
しかし、無駄に深い階層（Deeply nested DOM trees）や、数万の空の `` 要素を生成するようなマークアップは、V8のヒープ外（C++側）でのメモリ消費を急増させる。DOMノード一つひとつが持つポインタ（親、子、兄弟、属性マップ、イベントリスナーのリストなど）のオーバーヘッドは馬鹿にならない。
- 教訓: リストの仮想化（Virtualization）や、必要最低限のDOM構造（Flat DOM）の維持は、CSSのパフォーマンスだけでなく、メモリ帯域とGC（ガベージコレクション）のプレッシャー軽減の観点からも極めて重要である。
2. インクリメンタル・パースとプリロードスキャナー（Preload Scanner）
DOMツリー構築は、ネットワークからバイトが届くたびに非同期かつインクリメンタル（段階的）に行われる。チャンク単位でデータがTokenizerに流れ込み、トークンが生成される端からTree BuilderがDOMノードを組み立てていく。
ここでボトルネックになるのがJavaScriptの実行ブロックだ。パーサーが `
コメント