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

このコミットは、Go言語の実験的なHTMLパーサー (exp/html) において、HTML5仕様で定義されている「Noah's Ark clause（ノアの箱舟条項）」の実装と、テスト時の属性ソート機能の追加を行っています。これにより、HTMLパースの正確性が向上し、特にアクティブなフォーマット要素のリストの管理が仕様に準拠するようになります。また、テストの安定性を高めるために、要素の属性を名前でソートしてからダンプする変更も含まれています。

コミット

commit 9c14184e25ea92354b0e6f4962ad0411b1356b67
Author: Andrew Balholm <andybalholm@gmail.com>
Date:   Tue May 29 13:39:54 2012 +1000

    exp/html: implement Noah's Ark clause
    
    Implement the (3-per-family) Noah's Ark clause (i.e. don't put
    more than three identical elements on the list of active formatting
    elements.
    
    Also, when running tests, sort attributes by name before dumping
    them.
    
    Pass 4 additional tests with Noah's Ark clause (including one
    that needs attributes to be sorted).
    
    Pass 5 additional, unrelated tests because of sorting attributes.
    
    R=nigeltao, rsc
    CC=golang-dev
    https://golang.org/cl/6247056

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

https://github.com/golang/go/commit/9c14184e25ea92354b0e6f4962ad0411b1356b67

元コミット内容

このコミットは、主に以下の2つの変更を含んでいます。

Noah's Ark clauseの実装: HTML5のパースアルゴリズムにおける「アクティブなフォーマット要素のリスト」に関する「Noah's Ark clause」を実装します。具体的には、同じ要素が3つ以上リストに存在しないように制御します。
テスト時の属性ソート: テスト実行時に、要素の属性を名前順にソートしてからダンプするように変更します。これにより、テスト結果の安定性が向上します。

これらの変更により、Noah's Ark clauseに関連する4つのテストと、属性ソートによって影響を受ける5つの無関係なテストが追加でパスするようになりました。

変更の背景

HTMLパーサーは、ウェブブラウザがHTMLドキュメントを解析し、DOMツリーを構築するための重要なコンポーネントです。HTML5仕様は、ブラウザ間の互換性を保証するために、非常に詳細なパースアルゴリズムを定義しています。このアルゴリズムには、特定の状況下での要素の処理方法に関する複雑なルールが含まれています。

Noah's Ark clauseの背景

「Noah's Ark clause（ノアの箱舟条項）」は、HTML5のパースアルゴリズムにおける「アクティブなフォーマット要素のリスト (list of active formatting elements)」の管理に関するルールの一部です。このリストは、, , ,  などのフォーマット要素がネストされた場合に、それらの要素が正しく閉じられていない状況（例えば、 のようにタグが交差している場合）でも、DOMツリーの構築を適切に行うために使用されます。

このリストに同じ属性を持つ同じタグ名の要素が無限に追加されることを防ぐため、HTML5仕様では「Noah's Ark clause」が導入されました。この条項は、特定の条件を満たす同一の要素がリスト内に一定数（通常は3つ）以上存在する場合、最も古い要素をリストから削除するというものです。これにより、パーサーが無限ループに陥ったり、メモリを過剰に消費したりするのを防ぎ、堅牢性を高めます。

属性ソートの背景

HTMLの属性の順序は、通常、意味論的には重要ではありません。例えば、<div id="foo" class="bar"> と <div class="bar" id="foo"> は同じ要素として扱われます。しかし、テストにおいてDOMツリーを文字列としてダンプする場合、属性の順序が異なると、意味的に同じであっても文字列比較では異なる結果となり、テストが不安定になる可能性があります。

このコミットでは、テストの信頼性を向上させるために、属性を名前順にソートしてからダンプするように変更されました。これにより、属性の順序に依存しない一貫したテスト結果が得られるようになります。

前提知識の解説

HTML5パースアルゴリズム

HTML5のパースアルゴリズムは、非常に複雑で状態ベースのプロセスです。これは、HTMLの構文が非常に寛容であり、エラーを含むドキュメントでも可能な限りDOMツリーを構築できるように設計されているためです。主要な概念には以下が含まれます。

トークナイゼーション (Tokenization): 入力ストリームをタグ、属性、テキストなどのトークンに分解するプロセス。
ツリー構築 (Tree Construction): トークンストリームをDOMツリーに変換するプロセス。この段階で、様々な状態（インサーションモード）とスタック（要素スタック、アクティブなフォーマット要素のリストなど）が管理されます。
インサーションモード (Insertion Modes): 現在のパース状態に応じて、新しいトークンがDOMツリーにどのように挿入されるかを決定するルールセット。
要素スタック (Stack of Open Elements): 現在開いている要素（まだ閉じタグが来ていない要素）を追跡するためのスタック。
アクティブなフォーマット要素のリスト (List of Active Formatting Elements): , ,  などのフォーマット要素がネストされた場合に、それらの要素が正しく閉じられていない状況（タグの交差など）でも、DOMツリーの構築を適切に行うために使用されるリスト。このリストは、特定のフォーマットが適用されるべき範囲を追跡します。

同一要素のカウント: リストの末尾から逆順に走査し、現在追加しようとしている要素と「同一」と見なされる要素の数をカウントします。
- scopeMarkerNode に遭遇した場合、それ以上遡る必要はないためループを中断します。
- 要素のタイプが ElementNode でない場合、スキップします。
- 名前空間が空でない場合、スキップします（HTML要素は通常名前空間を持たない）。
- タグ名が一致しない場合、スキップします。
- 属性の数が異なる場合、スキップします。
- 属性の比較: 属性のキー、名前空間、値がすべて一致するかどうかを比較します。一つでも一致しない属性があれば、その要素は同一ではないと判断されます。
削除ロジック: 同一と見なされる要素の数が3つ以上になった場合、その要素をリストから削除します。これは、最も古い（リストの先頭に近い）同一の要素が削除されることを意味します。

この実装により、アクティブなフォーマット要素のリストが過剰に肥大化するのを防ぎ、HTML5仕様に準拠したパース動作を実現します。

テスト時の属性ソート (`parse_test.go`)

parse_test.go では、テスト結果をダンプする際に属性をソートするための変更が加えられています。

sortedAttributes 型の定義: Attribute スライスを sort.Interface インターフェースを満たす sortedAttributes 型として定義します。これにより、Goの標準ライブラリの sort.Sort 関数を使用して属性をソートできるようになります。
- Len(): スライスの長さを返します。
- Less(i, j int) bool: i 番目の属性が j 番目の属性よりも小さい場合に true を返します。比較はまず名前空間で行われ、次にキー（属性名）で行われます。
- Swap(i, j int): i 番目と j 番目の属性を入れ替えます。
dumpLevel 関数でのソート適用: dumpLevel 関数内で、要素の属性 (n.Attr) を sortedAttributes 型にキャストし、sort.Sort 関数を呼び出してソートします。
既存の属性順序変更ロジックの削除: 以前存在した、特定の属性の順序を強制的に変更するコメントアウトされたロジックが削除されています。これは、新しい属性ソートロジックによって不要になったためです。

この変更により、テストの出力が属性の順序に依存しなくなり、より安定したテスト結果が得られるようになります。

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

`src/pkg/exp/html/parse.go`

addFormattingElement 関数にNoah's Ark clauseの実装が追加されました。

 func (p *parser) addFormattingElement(tag string, attr []Attribute) {
 	p.addElement(tag, attr)

 	// Implement the Noah's Ark clause, but with three per family instead of two.
 	identicalElements := 0
 findIdenticalElements:
 	for i := len(p.afe) - 1; i >= 0; i-- {
 		n := p.afe[i]
 		if n.Type == scopeMarkerNode {
 			break
 		}
 		if n.Type != ElementNode {
 			continue
 		}
 		if n.Namespace != "" {
 			continue
 		}
 		if n.Data != tag {
 			continue
 		}
 		if len(n.Attr) != len(attr) {
 			continue
 		}
 	compareAttributes:
 		for _, a := range n.Attr {
 			for _, b := range attr {
 				if a.Key == b.Key && a.Namespace == b.Namespace && a.Val == b.Val {
 					// Found a match for this attribute, continue with the next attribute.
 					continue compareAttributes
 				}
 			}
 			// If we get here, there is no attribute that matches a.
 			// Therefore the element is not identical to the new one.
 			continue findIdenticalElements
 		}

 		identicalElements++
 		if identicalElements >= 3 {
 			p.afe.remove(n)
 		}
 	}

 	p.afe = append(p.afe, p.top())
 	// TODO.
 }

`src/pkg/exp/html/parse_test.go`

属性ソートのための sortedAttributes 型が追加され、dumpLevel 関数で属性がソートされるようになりました。

 import (
 	"io"
 	"os"
 	"path/filepath"
+	"sort"
 	"strings"
 	"testing"
 )

// ... (dumpIndent function)

+type sortedAttributes []Attribute
+
+func (a sortedAttributes) Len() int {
+	return len(a)
+}
+
+func (a sortedAttributes) Less(i, j int) bool {
+	if a[i].Namespace != a[j].Namespace {
+		return a[i].Namespace < a[j].Namespace
+	}
+	return a[i].Key < a[j].Key
+}
+
+func (a sortedAttributes) Swap(i, j int) {
+	a[i], a[j] = a[j], a[i]
+}
+
 func dumpLevel(w io.Writer, n *Node, level int) error {
 	dumpIndent(w, level)
 	switch n.Type {
 	case ElementNode:
 		if n.Namespace != "" {
 			fmt.Fprintf(w, "<%s %s>", n.Namespace, n.Data)
 		} else {
 			fmt.Fprintf(w, "<%s>", n.Data)
 		}
-		attr := n.Attr
-		if len(attr) == 2 && attr[0].Namespace == "xml" && attr[1].Namespace == "xlink" {
-			// Some of the test cases in tests10.dat change the order of adjusted
-			// foreign attributes, but that behavior is not in the spec, and could
-			// simply be an implementation detail of html5lib's python map ordering.
-			attr[0], attr[1] = attr[1], attr[0]
-		}
+		attr := sortedAttributes(n.Attr)
+		sort.Sort(attr)
 		for _, a := range attr {
 			io.WriteString(w, "\n")
 			dumpIndent(w, level+1)

コアとなるコードの解説

`parse.go` の `addFormattingElement` 関数内の変更

このコードブロックは、HTML5パースアルゴリズムの「アクティブなフォーマット要素のリスト」に新しいフォーマット要素を追加する際の「Noah's Ark clause」を実装しています。

identicalElements := 0: 同じ要素の数をカウントするための変数です。
for i := len(p.afe) - 1; i >= 0; i--: アクティブなフォーマット要素のリスト p.afe を末尾から逆順に走査します。これは、新しい要素に近い方から古い要素を探すためです。
n := p.afe[i]: 現在処理しているリスト内の要素を取得します。
if n.Type == scopeMarkerNode { break }: scopeMarkerNode は、特定のスコープの開始を示すマーカー要素です。これに遭遇した場合、それ以上古い要素を検索する必要がないため、ループを中断します。
if n.Type != ElementNode || n.Namespace != "" || n.Data != tag || len(n.Attr) != len(attr) { continue }: これは、要素が「同一」であるかどうかの初期チェックです。
- 要素のタイプが ElementNode でない場合（例えば、テキストノードやコメントノード）、スキップします。
- 名前空間が空でない場合（HTML要素は通常名前空間を持たないため）、スキップします。
- タグ名 (n.Data) が現在追加しようとしている要素のタグ名 (tag) と一致しない場合、スキップします。
- 属性の数 (len(n.Attr)) が一致しない場合、スキップします。
compareAttributes: ラベルと内部ループ: ここでは、要素の属性が完全に一致するかどうかを詳細に比較します。
- for _, a := range n.Attr: リスト内の要素 n の各属性 a についてループします。
- for _, b := range attr: 新しい要素の各属性 b についてループします。
- if a.Key == b.Key && a.Namespace == b.Namespace && a.Val == b.Val: 属性のキー（名前）、名前空間、値がすべて一致するかどうかをチェックします。
- continue compareAttributes: 現在の属性 a に一致する属性 b が見つかった場合、次の属性 a の比較に進みます。
- continue findIdenticalElements: 属性 a に一致する属性 b が見つからなかった場合、その要素 n は新しい要素と同一ではないと判断し、findIdenticalElements ラベルにジャンプして次のリスト要素のチェックに進みます。
identicalElements++: 上記のすべてのチェックを通過した場合、その要素 n は新しい要素と同一であると見なし、identicalElements をインクリメントします。
if identicalElements >= 3 { p.afe.remove(n) }: 同一の要素が3つ以上見つかった場合、現在処理している要素 n をリストから削除します。これにより、最も古い同一の要素がリストから取り除かれます。

このロジックにより、アクティブなフォーマット要素のリストがHTML5仕様に準拠して管理され、パーサーの安定性が向上します。

`parse_test.go` の `sortedAttributes` 型と `dumpLevel` 関数内の変更

このコードブロックは、テストの出力においてHTML要素の属性をソートすることで、テスト結果の一貫性を保証するためのものです。

type sortedAttributes []Attribute: Attribute 型のスライスを基にした新しい型 sortedAttributes を定義しています。これは、Goの sort パッケージが提供する sort.Interface インターフェースを実装するための準備です。
func (a sortedAttributes) Len() int { return len(a) }: sort.Interface の Len メソッドを実装しています。ソート対象のスライスの要素数を返します。
func (a sortedAttributes) Less(i, j int) bool { ... }: sort.Interface の Less メソッドを実装しています。これは、i 番目の要素が j 番目の要素よりも「小さい」（ソート順で前に来る）場合に true を返します。
- if a[i].Namespace != a[j].Namespace { return a[i].Namespace < a[j].Namespace }: まず、属性の名前空間で比較します。名前空間が異なる場合、辞書順で小さい方が前に来ます。
- return a[i].Key < a[j].Key: 名前空間が同じ場合、属性のキー（名前）で比較します。辞書順で小さい方が前に来ます。
func (a sortedAttributes) Swap(i, j int) { a[i], a[j] = a[j], a[i] }: sort.Interface の Swap メソッドを実装しています。i 番目と j 番目の要素を入れ替えます。
attr := sortedAttributes(n.Attr): dumpLevel 関数内で、ノード n の属性スライス n.Attr を新しく定義した sortedAttributes 型にキャストしています。これにより、sort.Sort 関数に渡せるようになります。
sort.Sort(attr): Goの標準ライブラリの sort.Sort 関数を呼び出し、sortedAttributes 型の attr スライスをソートします。この関数は、Len, Less, Swap メソッドを使用してソートを実行します。
削除されたコードブロック: 以前は、特定の xml および xlink 名前空間を持つ属性の順序を強制的に変更するロジックが存在しましたが、属性の一般的なソートが導入されたため、この特殊なケースの処理は不要となり削除されました。

これらの変更により、テスト出力における属性の順序が常に一貫するようになり、テストの信頼性と再現性が向上します。

参考にした情報源リンク

HTML Standard - 13.2.6.2 The list of active formatting elements
HTML Standard - 13.2.6.2 The list of active formatting elements - Noah's Ark clause
Go言語のsortパッケージ
HTML属性の順序に関する情報
HTML5 Parsing: The List of Active Formatting Elements (これは一般的な解説であり、直接的な仕様ではありませんが、概念理解に役立ちます)
HTML5 Parsing: The Insertion Mode (これも一般的な解説であり、概念理解に役立ちます)
HTML5 Parsing: Tokenization (これも一般的な解説であり、概念理解に役立ちます)
HTML5 Parsing: Tree Construction (これも一般的な解説であり、概念理解に役立ちます)

comemo