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

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

このコミットは、Go言語のhtmlパッケージにおけるHTMLテーブルのパース処理の改善を目的としています。特に、"foster parenting"（要素の養子縁組）時の隣接するテキストノードのマージと、</tr>タグでのテーブル行の適切なクローズ処理に焦点を当てています。これにより、HTMLの仕様に準拠したより堅牢なテーブルパースが実現され、特定のテストケース（tests1.dat, test 32）が正しく処理されるようになります。

コミット

  • コミットハッシュ: 6e318bda6c4236caf5a7f02d5ce545f5365094e0
  • Author: Andrew Balholm andybalholm@gmail.com
  • Date: Wed Oct 26 11:36:46 2011 +1100
  • Subject: html: improve parsing of tables

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

https://github.com/golang/go/commit/6e318bda6c4236caf5a7f02d5ce545f5365094e0

元コミット内容

html: improve parsing of tables

When foster parenting, merge adjacent text nodes.
Properly close table row at </tr> tag.

Pass tests1.dat, test 32:
<!-----><font><div>hello<table>excite!<b>me!<th><i>please!</tr><!--X-->

| <!-- - -->
| <html>
|   <head>
|   <body>
|     <font>
|       <div>
|         "helloexcite!"
|         <b>
|           "me!"
|         <table>
|           <tbody>
|             <tr>
|               <th>
|                 <i>
|                   "please!"
|             <!-- X -->

R=nigeltao
CC=golang-dev
https://golang.org/cl/5323048

変更の背景

HTMLのパースは、その柔軟性と寛容性から非常に複雑なタスクです。特にテーブル要素は、その構造が厳密に定義されている一方で、ブラウザは不正なマークアップに対しても可能な限りレンダリングを試みるため、パースロジックは多くのエッジケースを考慮する必要があります。

このコミットの背景には、主に以下の2つの問題がありました。

  1. "Foster Parenting"時のテキストノードのマージ不足: HTMLのパースにおいて、特定の状況下で要素が本来の親ではなく、別の要素の子として「養子縁組（foster parenting）」されることがあります。例えば、テーブル内で不正なマークアップがあった場合、その要素がテーブルの外に「養子縁組」されることがあります。この際、隣接するテキストノードが適切にマージされず、DOMツリーが意図しない形で分割されてしまう問題がありました。元のコミットメッセージにあるテストケース <!-----><font><div>hello<table>excite!<b>me!<th><i>please!</tr><!--X--> では、"hello" と "excite!" が別々のテキストノードとして扱われていた可能性があります。
  2. </tr>タグでのテーブル行の不適切なクローズ: HTMLのテーブル構造では、<tr>タグでテーブルの行が始まり、</tr>タグで閉じられます。しかし、パースのロジックが不完全な場合、</tr>タグが検出されても、現在のテーブル行が適切に閉じられず、DOMツリーの構造が崩れる可能性がありました。これは、特にネストされたテーブルや複雑なテーブルレイアウトにおいて問題を引き起こす可能性があります。

これらの問題は、HTML5のパース仕様に完全に準拠し、ブラウザの挙動を模倣するために修正が必要でした。

前提知識の解説

HTMLパースの基本

HTMLパースとは、HTMLドキュメントを読み込み、その構造を解析して、ブラウザがレンダリングできるような内部表現（通常はDOMツリー）を構築するプロセスです。このプロセスは大きく以下の2つの段階に分けられます。

  1. トークン化 (Tokenization): HTMLの生データを、意味のある単位である「トークン」に分解します。例えば、<p>は開始タグトークン、</p>は終了タグトークン、Helloはテキストトークンなどです。
  2. ツリー構築 (Tree Construction): トークン化されたストリームを基に、DOM（Document Object Model）ツリーを構築します。DOMツリーは、HTMLドキュメントの論理的な構造を表すツリー構造であり、各ノードはHTML要素、テキスト、コメントなどを表します。

HTMLテーブルのパースルール

HTMLのテーブルは、その構造が厳密に定義されています。<table>要素は、<caption>、<colgroup>、<thead>、<tbody>、<tfoot>、<tr>、<th>、<td>などの子要素を持つことができます。ブラウザは、これらの要素が正しい順序で出現することを期待しますが、不正なマークアップに対してもエラー回復メカニズムを持っています。

例えば、<td>や<th>が<tr>の外に出現した場合、ブラウザは自動的に<tr>要素を挿入して正しい構造にしようとします。また、<tbody>が明示的に記述されていなくても、<tr>要素が出現すれば自動的に<tbody>が生成されることがあります。

Foster Parenting (要素の養子縁組)

"Foster Parenting"は、HTML5のパースアルゴリズムにおける重要な概念の一つです。これは、特定の要素（特にテーブル関連の要素）が、本来あるべき親要素のスコープ外で出現した場合に、パースエラーを回避するために、別の適切な親要素の「養子」として扱われるメカニズムを指します。

例えば、<table>要素の直下に<div>のようなブロック要素が出現した場合、HTMLの仕様ではこれは不正なマークアップです。しかし、ブラウザはエラーでパースを停止するのではなく、この<div>要素をテーブルの外に「養子縁組」させ、DOMツリーの別の場所に配置しようとします。このプロセスは、ウェブページのレンダリングを中断させないためのブラウザの寛容なエラー回復戦略の一部です。

このコミットでは、この「養子縁組」が行われた際に、隣接するテキストノードが適切に結合されるように修正されています。

スタックと挿入モード

HTML5のパースアルゴリズムは、状態機械と要素のスタック（"stack of open elements"）を使用して動作します。

  • スタック (Stack of Open Elements): 現在開いているHTML要素の階層構造を追跡するために使用されます。新しい要素が開始タグで開かれるとスタックにプッシュされ、終了タグで閉じられるとポップされます。
  • 挿入モード (Insertion Mode): 現在パースしているHTMLのコンテキストに基づいて、新しいトークンをどのように処理するかを決定する状態です。例えば、inBodyIM（body要素内）、inTableIM（table要素内）、inRowIM（tr要素内）など、様々な挿入モードが存在します。各挿入モードには、特定のトークンが検出された場合の処理ルールが定義されています。

技術的詳細

Go言語のhtmlパッケージ（golang.org/x/net/html）は、HTML5のパース仕様に準拠したHTMLパーサーを提供します。このパッケージは、ウェブスクレイピングやHTMLドキュメントの操作に広く利用されています。

このパッケージのパース処理は、内部的にHTML5の仕様に記述されている複雑なアルゴリズムを実装しています。これには、トークン化、ツリー構築、そして様々な挿入モードと要素のスタック管理が含まれます。

fosterParent関数

fosterParent関数は、HTML5のパースアルゴリズムにおける「foster parenting」のロジックを実装しています。これは、特定の状況下で要素が通常の親ではなく、別の適切な親に挿入されるべき場合に呼び出されます。このコミットでは、この関数に隣接するテキストノードをマージするロジックが追加されました。

clearStackToContext関数

clearStackToContext関数は、要素のスタックをクリアする（特定の要素が見つかるまでスタックから要素をポップする）ための汎用的な関数です。以前はclearStackToTableContextというテーブル専用の関数がありましたが、このコミットでより汎用的なclearStackToContextに置き換えられ、stopTagsという引数で停止タグのリストを受け取るようになりました。これにより、異なるコンテキストでスタックをクリアする際に、コードの再利用性が向上しました。

inTableIMとinRowIM挿入モード

inTableIMはテーブル要素内でのパースを、inRowIMはテーブル行（<tr>）要素内でのパースをそれぞれ担当する挿入モードです。これらのモードでは、テーブルの構造を正しく構築するために、特定のタグが検出された際の特別な処理が定義されています。

このコミットでは、inTableIM内でtbody, tfoot, thead, td, th, trタグが検出された際に、clearStackToTableContextの代わりにclearStackToContext(tableScopeStopTags)が呼び出されるように変更されました。

また、inRowIMにおいて</tr>終了タグが検出された際の処理が改善されました。以前はTODOコメントで示されていた部分が、elementInScopeとclearStackToContextを使用して、<tr>要素がスコープ内に存在するかを確認し、存在する場合はtableRowContextStopTags（trまたはhtml）までスタックをクリアし、現在の<tr>要素をポップするように修正されました。これにより、</tr>タグが検出された際にテーブル行が適切に閉じられるようになりました。

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

このコミットでは、以下の2つのファイルが変更されています。

  • src/pkg/html/parse.go: HTMLパースの主要なロジックが含まれるファイル。
    • tableRowContextStopTagsという新しいグローバル変数が追加されました。
    • fosterParent関数に、隣接するテキストノードをマージするロジックが追加されました。
    • clearStackToTableContext関数が削除され、より汎用的なclearStackToContext関数が追加されました。
    • inTableIM関数内で、clearStackToTableContextの呼び出しがclearStackToContext(tableScopeStopTags)に置き換えられました。
    • inRowIM関数内で、</tr>終了タグの処理ロジックが大幅に改善されました。
  • src/pkg/html/parse_test.go: HTMLパースのテストが含まれるファイル。
    • TestParser関数内のテストケースのループ回数が32から33に増加しました。これは、新しいテストケース（tests1.dat, test 32）をカバーするためです。

コアとなるコードの解説

src/pkg/html/parse.go

tableRowContextStopTagsの追加

// stopTags for use in clearStackToContext.
var (
	tableRowContextStopTags = []string{"tr", "html"}
)

clearStackToContext関数で使用される新しい停止タグのリストが定義されました。これは、テーブル行のコンテキストでスタックをクリアする際に、trまたはhtml要素が見つかるまでスタックをポップすることを示します。

fosterParent関数の変更

func (p *parser) fosterParent(n *Node) {
	// ... 既存のコード ...

	if i > 0 && parent.Child[i-1].Type == TextNode && n.Type == TextNode {
		parent.Child[i-1].Data += n.Data
		return
	}

	// ... 既存のコード ...
}

fosterParent関数に、隣接するテキストノードをマージするロジックが追加されました。

  • if i > 0 && parent.Child[i-1].Type == TextNode && n.Type == TextNode: これは、現在のノードnがテキストノードであり、かつその親要素parentの直前の兄弟ノード（parent.Child[i-1]）もテキストノードである場合に真となります。
  • parent.Child[i-1].Data += n.Data: この条件が満たされた場合、直前のテキストノードのデータに現在のテキストノードのデータを結合（マージ）します。
  • return: マージが成功した場合、現在のノードnはDOMツリーに追加する必要がないため、関数を終了します。

これにより、例えば"hello"と"excite!"が別々のテキストノードとして生成された場合でも、これらが"helloexcite!"として一つのテキストノードに結合されるようになります。

clearStackToTableContextからclearStackToContextへの変更

// 変更前
// func (p *parser) clearStackToTableContext() { ... }

// 変更後
// clearStackToContext pops elements off the stack of open elements
// until an element listed in stopTags is found.
func (p *parser) clearStackToContext(stopTags []string) {
	for i := len(p.oe) - 1; i >= 0; i-- {
		for _, tag := range stopTags {
			if p.oe[i].Data == tag {
				p.oe = p.oe[:i+1]
				return
			}
		}
	}
}

clearStackToTableContext関数が削除され、より汎用的なclearStackToContext関数が導入されました。この新しい関数はstopTagsという文字列スライスを受け取り、スタックをクリアする際に、このリスト内のいずれかのタグが見つかるまで要素をポップします。これにより、テーブルコンテキストだけでなく、他のコンテキストでも同様のスタッククリアロジックを再利用できるようになりました。

inTableIM関数の変更

func inTableIM(p *parser) (insertionMode, bool) {
	case StartTagToken:
		switch p.tok.Data {
		case "tbody", "tfoot", "thead":
			// 変更前: p.clearStackToTableContext()
			p.clearStackToContext(tableScopeStopTags)
			p.addElement(p.tok.Data, p.tok.Attr)
			return inTableBodyIM, true
		case "td", "th", "tr":
			// 変更前: p.clearStackToTableContext()
			p.clearStackToContext(tableScopeStopTags)
			p.addElement("tbody", nil)
			return inTableBodyIM, false
		// ... 既存のコード ...
	}
	// ... 既存のコード ...
}

inTableIM関数内で、tbody, tfoot, thead, td, th, trなどの開始タグが検出された際のスタッククリア処理が、clearStackToTableContext()からclearStackToContext(tableScopeStopTags)に置き換えられました。tableScopeStopTagsは"html", "table"を含むため、テーブルのスコープ内でスタックをクリアする挙動は維持されますが、より汎用的な関数が使用されるようになりました。

inRowIM関数の変更

func inRowIM(p *parser) (insertionMode, bool) {
	case EndTagToken:
		switch p.tok.Data {
		case "tr":
			// 変更前: // TODO.
			if !p.elementInScope(tableScopeStopTags, "tr") {
				return inRowIM, true
			}
			p.clearStackToContext(tableRowContextStopTags)
			p.oe.pop()
			return inTableBodyIM, true
		// ... 既存のコード ...
	}
	// ... 既存のコード ...
}

inRowIM関数内で、</tr>終了タグが検出された際の処理が大幅に改善されました。

  • if !p.elementInScope(tableScopeStopTags, "tr"): まず、tr要素がtableScopeStopTags（htmlまたはtable）のスコープ内に存在するかどうかを確認します。存在しない場合、これは不正な</tr>タグであり、現在の挿入モードを維持して処理を続行します。
  • p.clearStackToContext(tableRowContextStopTags): tr要素がスコープ内に存在する場合、tableRowContextStopTags（trまたはhtml）が見つかるまでスタックをクリアします。これにより、現在のtr要素とその子孫要素がスタックから適切にポップされます。
  • p.oe.pop(): その後、スタックの最上位にあるtr要素自体をポップします。
  • return inTableBodyIM, true: 処理が成功した場合、挿入モードをinTableBodyIM（テーブルボディ内）に遷移させ、トークンを再処理しないことを示します。

この変更により、</tr>タグが検出された際に、HTML5の仕様に従ってテーブル行が正しく閉じられるようになりました。

src/pkg/html/parse_test.go

func TestParser(t *testing.T) {
	// ... 既存のコード ...
	// TODO(nigeltao): Process all test cases, not just a subset.
	// 変更前: for i := 0; i < 32; i++ {
	for i := 0; i < 33; i++ {
	// ... 既存のコード ...
	}
	// ... 既存のコード ...
}

TestParser関数内のループ回数が32から33に増加しました。これは、tests1.datファイルのテストケース32（インデックス31）をカバーするために行われました。このテストケースは、コミットメッセージに記載されている複雑なテーブルパースのシナリオを検証するためのものです。

関連リンク

参考にした情報源リンク