Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 10340] ファイルの概要

このコミットは、Go言語のhtmlパッケージにおけるHTMLパーサーの改善に関するものです。具体的には、HTMLテーブル要素内で使用される<colgroup>要素のパース処理を正確に行うための変更が加えられています。これにより、HTML5の仕様に準拠したテーブル構造の解析が可能になり、特に<colgroup>と<col>要素が正しくDOMツリーに構築されるようになります。

コミット

commit 83f61a27d6f1ef053c00b4cc2fd9668fdf354ad8
Author: Andrew Balholm <andybalholm@gmail.com>
Date:   Fri Nov 11 11:41:46 2011 +1100

    html: parse column groups
    
    Pass tests1.dat, test 108:
    <table><colgroup><col><colgroup><col><col><col><colgroup><col><col><thead><tr><td></table>
    
    | <html>
    |   <head>
    |   <body>
    |     <table>
    |       <colgroup>
    |         <col>
    |       <colgroup>
    |         <col>
    |         <col>
    |         <col>
    |       <colgroup>
    |         <col>
    |         <col>
    |       <thead>
    |         <tr>
    |           <td>
    
    R=nigeltao
    CC=golang-dev
    https://golang.org/cl/5369061

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/83f61a27d6f1ef053c00b4cc2fd9668fdf354ad8

元コミット内容

このコミットは、Go言語のhtmlパッケージに、HTMLのcolgroup要素をパースする機能を追加します。

変更の目的は、tests1.datのテスト108をパスすることです。このテストケースは、以下のような複雑なテーブル構造を含んでいます。

<table><colgroup><col><colgroup><col><col><col><colgroup><col><col><thead><tr><td></table>

このHTMLをパースした結果として、以下のようなDOMツリーが期待されます。

<html>
  <head>
  <body>
    <table>
      <colgroup>
        <col>
      <colgroup>
        <col>
        <col>
        <col>
      <colgroup>
        <col>
        <col>
      <thead>
        <tr>
          <td>

この変更は、nigeltaoによってレビューされ、golang-devにCCされています。関連するGo CL (Change List) は https://golang.org/cl/5369061 です。

変更の背景

HTMLのパースは、ウェブブラウザやサーバーサイドのレンダリング、スクレイピングなど、多岐にわたるアプリケーションで不可欠な処理です。HTMLは非常に柔軟な構文を持つため、そのパース処理は複雑であり、特にエラーハンドリングや不完全なマークアップの処理において、HTML5の仕様に厳密に準拠することが求められます。

このコミットが行われた2011年当時、Go言語のhtmlパッケージはまだ初期段階にあり、HTML5のすべての要素やパースルールに完全に対応しているわけではありませんでした。特にテーブル構造は、その複雑さから正確なパースが難しい要素の一つです。

<colgroup>要素は、テーブルの列をグループ化し、スタイルを適用するために使用されます。この要素は、その子要素として<col>要素を持つことができます。正確なDOMツリーを構築するためには、パーサーがこれらの要素の出現順序、ネストのルール、および特定の挿入モードにおける挙動を正しく理解し、処理する必要があります。

このコミットの背景には、Go言語のhtmlパッケージがHTML5のテストスイート（特にtests1.dat）をパスし、より堅牢で標準準拠のHTMLパーサーを提供することを目指していたという経緯があります。テスト108は、<colgroup>要素が複数回出現し、その中に<col>要素が適切にネストされているという、比較的複雑なケースを扱っており、このテストをパスすることはパーサーの正確性を高める上で重要でした。

前提知識の解説

HTML5のパースアルゴリズム

HTML5の仕様では、HTML文書をパースするための詳細なアルゴリズムが定義されています。これは、ブラウザがどのようにHTMLを読み込み、DOMツリーを構築するかを標準化したものです。このアルゴリズムは、主に以下の概念に基づいています。

  • トークナイゼーション (Tokenization): 入力されたHTML文字列を、タグ、属性、テキストなどの「トークン」に分解するプロセスです。
  • ツリー構築 (Tree Construction): トークナイザーから受け取ったトークンに基づいて、DOMツリーを構築するプロセスです。このプロセスは、特定の「挿入モード (Insertion Mode)」に従って動作します。

挿入モード (Insertion Mode)

HTML5のツリー構築アルゴリズムの核心は「挿入モード」です。これは、現在のパーサーの状態に応じて、次に受け取るトークンをどのように処理するかを決定するステートマシンです。例えば、inBodyモードでは<body>要素内のコンテンツを処理し、inTableモードでは<table>要素内のコンテンツを処理します。

各挿入モードには、特定のトークンが来た場合の処理ルールが定義されています。これには、要素の追加、スタックからの要素のポップ、別の挿入モードへの切り替えなどが含まれます。

HTMLのテーブル要素 (<table>, <colgroup>, <col>)

  • <table>: HTMLのテーブル構造のルート要素です。
  • <caption>: テーブルのキャプション（タイトル）を定義します。
  • <thead>: テーブルのヘッダー行をグループ化します。
  • <tbody>: テーブルの本体行をグループ化します。
  • <tfoot>: テーブルのフッター行をグループ化します。
  • <colgroup>: テーブルの列をグループ化するために使用されます。この要素は、テーブルの列にスタイルを適用したり、構造的な意味を持たせたりするために使われます。<colgroup>要素は、その子要素として0個以上の<col>要素を持つことができます。
  • <col>: <colgroup>要素の子要素として使用され、テーブルの単一の列または複数の列にスタイルを適用するために使用されます。<col>要素は空要素（内容を持たない）です。

clearStackToContext メソッド

HTMLパーサーにおいて、DOMツリーを構築する際には「要素スタック (stack of open elements)」が重要な役割を果たします。これは、現在開いている要素（まだ終了タグが来ていない要素）を追跡するためのスタックです。

clearStackToContextのようなメソッドは、特定の要素がスタックに現れるまで、スタックから要素をポップ（削除）するために使用されます。これは、特定のコンテキスト（例えば、テーブル内）で予期しない要素が出現した場合に、パーサーの状態をリセットし、正しいDOM構造を維持するために必要です。

技術的詳細

このコミットは、Go言語のhtmlパッケージ内のparse.goファイルに、HTML5のパースアルゴリズムにおけるinColumnGroupIM（In Column Group Insertion Mode）のロジックを追加・修正しています。

HTML5の仕様では、<table>要素の直後に<colgroup>要素が出現した場合、パーサーはinTableモードからinColumnGroupモードに切り替わる必要があります。また、<colgroup>要素の内部では、<col>要素が適切に処理され、それ以外の要素が出現した場合には、inTableモードに戻るなどの適切なエラーハンドリングが行われる必要があります。

このコミットの主な技術的ポイントは以下の通りです。

  1. resetInsertionMode の修正:

    • resetInsertionMode関数は、パーサーが現在の挿入モードを決定する際に使用されます。
    • 以前はcolgroupタグに対して// TODO: return inColumnGroupIMとコメントアウトされていましたが、このコミットでreturn inColumnGroupIMが有効化されました。これにより、パーサーが<colgroup>タグを検出した際に、正しくinColumnGroupIMに遷移するようになります。

  2. inTableIM の修正:

    • inTableIM関数は、inTable挿入モードにおけるトークンの処理を定義します。
    • <colgroup>タグの処理: inTableIM内で<colgroup>タグが検出された場合、パーサーはtableScopeStopTags（table, tbody, tfoot, thead, trなど）までの要素スタックをクリアし、<colgroup>要素をDOMツリーに追加し、inColumnGroupIMに遷移するように変更されました。これは、HTML5の仕様で定義されている<colgroup>のパースルールに準拠しています。
    • <col>タグの処理: inTableIM内で<col>タグが検出された場合、パーサーは同様にtableScopeStopTagsまでの要素スタックをクリアし、暗黙的に<colgroup>要素をDOMツリーに追加し、その子要素として<col>要素を追加するように変更されました。その後、inColumnGroupIMに遷移します。これは、<col>が<colgroup>なしで出現した場合でも、ブラウザが自動的に<colgroup>を挿入して処理する挙動を模倣しています。

  3. inColumnGroupIM の新規追加:

    • このコミットの最も重要な変更は、inColumnGroupIM関数の新規追加です。この関数は、HTML5のセクション11.2.5.4.12（"The "in column group" insertion mode"）に厳密に従って実装されています。
    • CommentToken: コメントノードとして追加されます。
    • DoctypeToken: 無視されます。
    • StartTagToken:
      • htmlタグの場合: inBodyIMに遷移します。
      • colタグの場合: <col>要素をDOMツリーに追加し、自己終了タグとして扱います。その後、inColumnGroupIMに留まります。
    • EndTagToken:
      • colgroupタグの場合: 要素スタックのトップがhtmlでない限り、スタックからポップし、inTableIMに遷移します。これは、<colgroup>の終了タグが来た場合に、親のテーブルコンテキストに戻るための処理です。
      • colタグの場合: 無視されます。<col>は空要素であるため、終了タグは通常無視されます。
    • 上記以外のトークンが来た場合、要素スタックのトップがhtmlでない限り、スタックからポップし、inTableIMに遷移します。これは、<colgroup>内で予期しない要素が出現した場合に、パーサーがテーブルモードに戻るためのフォールバックメカニズムです。

これらの変更により、Go言語のHTMLパーサーは、HTML5の複雑なテーブル構造、特に<colgroup>と<col>要素のパースにおいて、より正確で堅牢な挙動を示すようになりました。

コアとなるコードの変更箇所

src/pkg/html/parse.go

--- a/src/pkg/html/parse.go
+++ b/src/pkg/html/parse.go
@@ -313,7 +313,7 @@ func (p *parser) resetInsertionMode() insertionMode {
 		case "caption":
 			// TODO: return inCaptionIM
 		case "colgroup":
-			// TODO: return inColumnGroupIM
+			return inColumnGroupIM
 		case "table":
 			return inTableIM
 		case "head":
@@ -879,6 +879,14 @@ func inTableIM(p *parser) (insertionMode, bool) {
 			}
 			// Ignore the token.
 			return inTableIM, true
+		case "colgroup":
+			p.clearStackToContext(tableScopeStopTags)
+			p.addElement(p.tok.Data, p.tok.Attr)
+			return inColumnGroupIM, true
+		case "col":
+			p.clearStackToContext(tableScopeStopTags)
+			p.addElement("colgroup", p.tok.Attr)
+			return inColumnGroupIM, false
 		default:
 			// TODO.
 		}
@@ -924,6 +932,46 @@ func (p *parser) clearStackToContext(stopTags []string) {
 	}
 }
 
+// Section 11.2.5.4.12.
+func inColumnGroupIM(p *parser) (insertionMode, bool) {
+	switch p.tok.Type {
+	case CommentToken:
+		p.addChild(&Node{
+			Type: CommentNode,
+			Data: p.tok.Data,
+		})
+		return inColumnGroupIM, true
+	case DoctypeToken:
+		// Ignore the token.
+		return inColumnGroupIM, true
+	case StartTagToken:
+		switch p.tok.Data {
+		case "html":
+			return useTheRulesFor(p, inColumnGroupIM, inBodyIM)
+		case "col":
+			p.addElement(p.tok.Data, p.tok.Attr)
+			p.oe.pop()
+			p.acknowledgeSelfClosingTag()
+			return inColumnGroupIM, true
+		}
+	case EndTagToken:
+		switch p.tok.Data {
+		case "colgroup":
+			if p.oe.top().Data != "html" {
+				p.oe.pop()
+			}
+			return inTableIM, true
+		case "col":
+			// Ignore the token.
+			return inColumnGroupIM, true
+		}
+	}
+	if p.oe.top().Data != "html" {
+		p.oe.pop()
+	}
+	return inTableIM, false
+}
+
 // Section 11.2.5.4.13.
 func inTableBodyIM(p *parser) (insertionMode, bool) {
 	var (

src/pkg/html/parse_test.go

--- a/src/pkg/html/parse_test.go
+++ b/src/pkg/html/parse_test.go
@@ -133,7 +133,7 @@ func TestParser(t *testing.T) {
 		tn int
 	}{
 		// TODO(nigeltao): Process all the test cases from all the .dat files.
-		{"tests1.dat", 108},
+		{"tests1.dat", 109},
 		{"tests2.dat", 0},
 		{"tests3.dat", 0},
 	}

コアとなるコードの解説

src/pkg/html/parse.go の変更

  1. resetInsertionMode 関数の変更:

    • case "colgroup": の行が // TODO: return inColumnGroupIM から return inColumnGroupIM に変更されました。
    • 解説: これは、パーサーが現在の挿入モードをリセットする際に、<colgroup>タグが検出された場合に正しくinColumnGroupIM（カラムグループ挿入モード）に遷移するように修正されたことを意味します。以前は、このモードへの遷移が実装されていなかったため、<colgroup>要素が正しく処理されませんでした。

  2. inTableIM 関数の変更:

    • case "colgroup": ブロックが追加されました。
      • p.clearStackToContext(tableScopeStopTags): これは、要素スタックをクリアし、tableScopeStopTags（table, tbody, tfoot, thead, trなど）のいずれかの要素が見つかるまで、スタックから要素をポップします。これにより、<colgroup>がテーブルの正しいコンテキストに挿入されることが保証されます。
      • p.addElement(p.tok.Data, p.tok.Attr): 現在のトークン（<colgroup>）をDOMツリーに追加します。
      • return inColumnGroupIM, true: 挿入モードをinColumnGroupIMに切り替えます。trueは、トークンが消費されたことを示します。
    • case "col": ブロックが追加されました。
      • p.clearStackToContext(tableScopeStopTags): 同様に要素スタックをクリアします。
      • p.addElement("colgroup", p.tok.Attr): ここが重要です。<col>タグが直接inTableIMで検出された場合、HTML5の仕様では暗黙的に<colgroup>要素が生成され、その中に<col>が挿入されることになっています。この行は、その暗黙的な<colgroup>要素をDOMツリーに追加します。
      • return inColumnGroupIM, false: 挿入モードをinColumnGroupIMに切り替えますが、falseは現在のトークン（<col>）がまだ消費されていないことを示します。これは、inColumnGroupIM内で改めて<col>トークンが処理されることを意図しています。
    • 解説: これらの変更により、inTableIMにおいて<colgroup>や<col>タグが検出された際に、HTML5の仕様に沿った適切なDOMツリーの構築と挿入モードの遷移が行われるようになりました。特に<col>が単独で出現した場合に、自動的に<colgroup>が挿入される挙動が実装されています。

  3. inColumnGroupIM 関数の新規追加:

    • この関数は、HTML5のセクション11.2.5.4.12「The "in column group" insertion mode」に厳密に基づいて実装されています。
    • CommentToken: コメントノードとしてDOMツリーに追加されます。
    • DoctypeToken: 無視されます。
    • StartTagToken:
      • case "html": htmlタグが検出された場合、inBodyIMに遷移します。これは、HTML文書のルート要素が検出された場合の一般的なフォールバックです。
      • case "col": <col>タグが検出された場合、p.addElement(p.tok.Data, p.tok.Attr)でDOMツリーに追加し、p.oe.pop()で要素スタックからポップ（<col>は空要素なので、すぐに閉じられる）し、p.acknowledgeSelfClosingTag()で自己終了タグとして認識させます。その後、inColumnGroupIMに留まります。
    • EndTagToken:
      • case "colgroup": <colgroup>の終了タグが検出された場合、要素スタックのトップがhtmlでない限り、スタックからポップし、inTableIMに遷移します。これにより、<colgroup>要素の処理が完了し、パーサーがテーブルのコンテキストに戻ります。
      • case "col": <col>の終了タグは無視されます。<col>は空要素であるため、終了タグは意味を持ちません。
    • デフォルトの挙動: 上記のいずれのケースにも当てはまらないトークンが来た場合、要素スタックのトップがhtmlでない限り、スタックから要素をポップし、inTableIMに遷移します。これは、<colgroup>内で予期しない要素が出現した場合に、パーサーがテーブルモードに戻るためのエラーハンドリングです。
    • 解説: この新しい挿入モードは、<colgroup>要素の内部で<col>要素を正しく処理し、それ以外の要素や終了タグが来た場合に、HTML5の仕様に沿って適切なモード遷移やエラー処理を行うための中心的なロジックを提供します。

src/pkg/html/parse_test.go の変更

  • {"tests1.dat", 108}, から {"tests1.dat", 109}, に変更されました。
  • 解説: これは、tests1.datファイル内のテストケースのインデックスが108から109に更新されたことを示しています。おそらく、このコミットによって追加された機能が、新しいテストケース109で検証されるようになったか、既存のテストケース108が修正され、その結果としてインデックスが変更されたことを意味します。これにより、colgroupのパース機能が正しく動作するかどうかが自動テストで確認されるようになります。

これらの変更全体として、Go言語のHTMLパーサーがHTML5のテーブル構造、特に<colgroup>と<col>要素のパースにおいて、より正確で堅牢な挙動を示すようになりました。

関連リンク

  • Go CL (Change List): https://golang.org/cl/5369061

参考にした情報源リンク