体系ガイド · 発展

RustでDOMの親子関係を保つ

アリーナの添字と開いている要素のスタックを使い、トークン列から一貫したDOMを構築し、回復方針と境界を試験します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 到達目標:配列の上に木を作る
  2. ノードを参照でなく添字でつなぐ理由
  3. 手計算:開いている要素のスタック
  4. 不一致、空要素、重複属性の方針
  5. 構造を検査する小さなRustプログラム
  6. 正常・境界・失敗を分けて比較する
  7. 演習:木とソースを一緒に説明する
  8. この記事をロゲイアに質問する理解を確かめる

到達目標:配列の上に木を作る

字句解析器が返したトークンを、今度は親子関係を持つDOMへ組み立てます。配布プロジェクトのparse_htmlは、一つの配列へノードを追加し、親と子を配列の添字で表すアリーナ方式を使います。この章では、Rustのポインタを直接つなぐことより先に、親が一つであること、親の子一覧と子の親が一致すること、開いている要素のスタックが構築位置を表すことを確認します。

WASMデモへ同じHTMLを与えて、トークン列とDOMを順に見てください。トークンを正しく認識できても、付ける親を誤れば木は違う意味になります。既存の概念デモで理解した「子を追加する」を、Vecへの追加、添字の取得、二つの関係の更新という具体的な操作へ分けるのが目的です。画面のノード番号は一回の解析内の位置であり、利用者アカウントや学習記録のIDとして使うものではありません。

ノードを参照でなく添字でつなぐ理由

Vecが伸びると内部の配置が変わる可能性があります。配列内の要素への参照を長く保持したまま追加を続ける設計は、Rustの借用規則とも衝突します。添字を保存すれば、追加後に配列から必要な要素を取り直せます。ただし添字なら何でも安全という意味ではありません。範囲内であること、その添字が今の文書に属すること、削除後に別のノードへ使い回されないことは、実装側の契約として残ります。

このプロジェクトは解析中にノードを順番に追加するため、生成済みの親へ新しい子を付けるという単純な規則を使えます。親を更新する可変借用を長く残さず、必要な値を先に取り出してからVecへ追加し、最後に親側を更新します。木の形を作る処理と文字列を画面へ出力する処理を分けておくと、出力形式をJSONから別の形式へ替えても構築規則の試験は保てます。

手計算:開いている要素のスタック

<div><p>A</p><p>B</p></div>では、文書ノード0から始め、divを1、最初のpを2、Aを3、次のpを4、Bを5とします。開始タグは現在のスタック最上段へ要素を付け、その要素を新しい最上段にします。文字列は最上段の要素の子です。対応する終了タグは要素をスタックから外すだけで、DOMから削除する操作ではありません。次のpを作るとき、現在位置がdivへ戻っていることが兄弟関係の根拠になります。

ここで最初の</p>でスタックを戻さない誤りを入れると、二つ目のpが一つ目のpの子になります。トークン数や最終的な文字列ABは同じでも、親子関係は変わります。したがって試験では文字列出力だけを比べず、ノード4の親が1であることと、ノード1の子が2と4であることを確かめます。教材が自動挿入や省略タグをどこまで扱うかは別の契約なので、この例では明示的に対応したタグを使います。

入力の後スタック新しく確定した関係
<div>[0,1]1の親は0
<p>A[0,1,2]3の親は2
</p>[0,1]ノード2は残る
<p>B[0,1,4]4の親は1

不一致、空要素、重複属性の方針

実装のparse_htmlは、閉じる名前が現在の要素と一致しない場合に診断を残し、その不一致だけでスタックを変更しません。<div></p></div>なら、</p>の診断と、その後の</div>で正常に戻る動きを別々に追えます。末尾に開いた要素が残る場合にも診断します。黙って全部閉じたことにすると、入力を直すべき場所が見えなくなるためです。この方針は教材の限定構文に対する規則であり、実ブラウザのHTML回復規則の再現ではありません。

br、hr、img、input、meta、linkはこのプロジェクトの空要素として扱い、子を挿入する位置へ積みません。重複属性では最初の値を残すため、同じidを後から見つけたときに上書きする実装とは結果が違います。境界を理解するには、<div>A<br>B</div>でBの親を確認し、idを二回書いた入力で残る属性を確かめます。受理できる入力を増やす際には、既存の診断の位置や子の順序が変わらないかも調べます。

構造を検査する小さなRustプログラム

次の例は、添字を使った木で親子の対称性を検査する独立したプログラムです。ドキュメントの子が1、要素1の親が0であることを双方向から確かめます。配布コードのテストを読む際も、「出力が期待文字列と一致した」だけでなく、どの不変条件を試しているかに名前を付けてください。親一覧と子一覧の片方だけを更新した不具合を、この検査なら直接指摘できます。

さらに文書ノード以外の各ノードがただ一つの親の子一覧に現れること、子の順序が入力の順序であることを調べます。循環を許す変更を加える場合は、訪問済み集合などを使った検査が必要です。今の追加専用の構築では親が先に作られる規則も確認できますが、将来ノード移動を実装したときにはその規則だけで正当性を説明できません。操作を増やすたび、どの証拠が引き続き有効かを見直します。

rust
// Standalone arena invariant; related to parse_html parent/children links.
struct Node { parent: Option<usize>, children: Vec<usize> }
fn main() {
    let nodes = vec![
        Node { parent: None, children: vec![1] },
        Node { parent: Some(0), children: vec![] },
    ];
    for (parent, node) in nodes.iter().enumerate() {
        for &child in &node.children {
            assert_eq!(nodes[child].parent, Some(parent));
        }
    }
}

正常・境界・失敗を分けて比較する

正常例には兄弟と入れ子の両方を含めます。一つのpだけでは、終了タグで親を戻す処理をほとんど試せません。境界例には空文書、空要素、空白のみのテキスト、日本語、上限直前の深さを選びます。失敗例には閉じる名前の不一致、閉じ忘れ、属性の途切れ、ノード数や深さの上限超過を含めます。現在のプロジェクトでは入力8192バイト、512トークン、256ノード、要素の入れ子31段を上限として契約を確かめます。

失敗例でも観察する値は一つではありません。診断があること、入力中の範囲が有効であること、残ったDOMの親子関係が壊れていないこと、再実行で前回のノードが混じらないことを調べます。大きな値を入力して画面が停止しなかったというだけでは、上限で正しく止まった証拠にはなりません。数の境界を一つずつ変えると、字句段階の上限と木構築の上限がどこで働いたかを説明できます。

演習:木とソースを一緒に説明する

完成版を動かした後、演習版で子を追加する箇所を実装し、手計算の木と一致させてください。まずノードを三つに抑えた入力で両方向の関係を調べ、その後に兄弟と空要素を足します。正しく見える出力を得るためにJSONを後から並べ替えるのではなく、parse_htmlが返した時点の木に対して試験を行います。以降のスタイルとレイアウトは、この同じ木を受け取るためです。

最後に、一つの診断について入力のバイト範囲、Rustの分岐、スタックの変化、DOMに残った関係を短く記録します。リンク先の記事とソースの位置を往復しながら、なぜその子がその親へ付いたかを説明できることを完了の目安にします。確認問題への回答、Webデモの実行、ローカル実装の自己申告は別の記録です。ローカルの試験ログを保存すれば、次の章で描画が崩れた場合に木の段階まで正しかったかを再確認できます。

RustでHTMLを解析してDOMを作る

実験の途中状態を読み込み中…

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 20

学習コースから次を選ぶ