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

このコミットは、Go言語の実験的なHTMLパーサーパッケージ exp/html (現在の golang.org/x/net/html に相当) におけるドキュメントの更新と、新しい使用例の追加を目的としています。特に、HTMLノードの子要素がスライスではなく連結リストとして表現されているという重要な設計上の特性を明確にし、その適切な走査方法を示すことに焦点を当てています。

コミット

commit 9dc3152668319fce81ec72055051cee47d4c801d
Author: Nigel Tao <nigeltao@golang.org>
Date:   Thu Oct 18 10:25:50 2012 +1100

    exp/html: update package docs and add an example; a node's children is
    a linked list, not a slice.
    
    R=r, minux.ma
    CC=golang-dev
    https://golang.org/cl/6618055

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

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

元コミット内容

exp/html パッケージのドキュメントを更新し、使用例を追加します。ノードの子要素はスライスではなく連結リストです。

変更の背景

Go言語の exp/html パッケージは、HTMLドキュメントをパースし、DOM (Document Object Model) のようなツリー構造を構築するためのものです。このツリー構造において、各HTMLノード（html.Node）は子ノードを持つことができます。当初、この子ノードのコレクションがGoの一般的なデータ構造である「スライス」として扱われると誤解される可能性がありました。

しかし、exp/html パッケージの設計では、ノードの子要素はスライスではなく、FirstChild、NextSibling、PrevSibling といったポインタを持つ「連結リスト」として実装されています。この設計は、DOMのような動的なツリー構造において、ノードの挿入や削除を効率的に行うために有利です。スライスの場合、要素の挿入や削除は、その後の全要素の移動を伴うため、パフォーマンスコストが高くなる可能性があります。一方、連結リストではポインタの付け替えだけで済むため、O(1)の効率で操作が可能です。

このコミットの背景には、この重要な設計上の選択（連結リストの使用）を明確にし、開発者が誤った方法（スライスとして扱う）で子ノードを走査するのを防ぐ目的があります。具体的には、既存のドキュメント内の誤解を招く可能性のあるコードスニペットを修正し、連結リストの走査方法を示す新しいテスト例を追加することで、パッケージの利用者が正しいイディオムでHTMLツリーを操作できるようにしています。

前提知識の解説

連結リスト (Linked List)

連結リストは、データ要素（ノード）が順序付けられたシーケンスで構成される線形データ構造です。各ノードはデータ自体と、次のノードへの参照（ポインタ）を含みます。双方向連結リストの場合、前のノードへの参照も持ちます。

特徴:

• 動的なサイズ: 要素の追加や削除が容易で、メモリを動的に割り当てます。
• 効率的な挿入/削除: リストの途中への要素の挿入や削除は、ポインタの付け替えだけで済むため、O(1)の時間計算量で行えます。
• 非効率なランダムアクセス: 特定のインデックスの要素にアクセスするには、リストの先頭から順に走査する必要があるため、O(N)の時間計算量がかかります。
• メモリオーバーヘッド: 各ノードがポインタを保持するため、スライスに比べてノードあたりのメモリ消費が大きくなることがあります。

スライス (Slice)

Go言語におけるスライスは、配列のセグメントを参照する軽量なデータ構造です。スライスは、長さ、容量、および基になる配列へのポインタで構成されます。

特徴:

• 動的なサイズ（見かけ上）: スライス自体は動的にサイズ変更可能に見えますが、実際には基になる配列のサイズが変更されるか、新しい配列が割り当てられてコピーされます。
• 効率的なランダムアクセス: 基になる配列へのポインタを持つため、インデックスによる要素へのアクセスはO(1)の時間計算量で行えます。
• 非効率な挿入/削除: スライスの途中への要素の挿入や削除は、その後の全要素を移動させる必要があるため、O(N)の時間計算量がかかります。
• 連続したメモリ: 要素はメモリ上で連続して配置されるため、キャッシュ効率が良い場合があります。

HTML DOM (Document Object Model)

HTML DOMは、HTMLドキュメントをオブジェクトのツリーとして表現するプログラミングインターフェースです。各HTML要素、属性、テキストはノードとして表現され、親子関係や兄弟関係を持ちます。DOMは、JavaScriptなどのスクリプト言語からHTMLドキュメントの構造、スタイル、コンテンツにアクセスし、操作するための標準的な方法を提供します。

HTMLドキュメントの構造は本質的にツリーであり、ノードの追加、削除、移動が頻繁に発生する可能性があります。このため、連結リストのようなデータ構造は、DOMの内部表現として適している場合があります。

技術的詳細

exp/html パッケージの html.Node 構造体は、HTMLドキュメントの各要素、テキスト、コメントなどを表現します。この構造体は、ツリー構造を形成するために以下のフィールドを持っています（簡略化された表現）：

type Node struct {
    Parent      *Node
    FirstChild  *Node
    NextSibling *Node
    PrevSibling *Node
    // ... その他のフィールド (Type, Data, Attr など)
}

• Parent: 親ノードへのポインタ。
• FirstChild: 最初の子ノードへのポインタ。
• NextSibling: 同じ親を持つ次の兄弟ノードへのポインタ。
• PrevSibling: 同じ親を持つ前の兄弟ノードへのポインタ。

この設計により、n.Child のようなスライスは存在せず、子ノードを走査するには FirstChild から NextSibling ポインタをたどる必要があります。

変更前は、ドキュメントの例で for _, c := range n.Child のようなスライスを想定したイテレーションが示されており、これは誤りでした。このコミットでは、これを for c := n.FirstChild; c != nil; c = c.NextSibling という連結リストの走査イディオムに修正しています。

また、example_test.go に追加された ExampleParse 関数は、実際のHTML文字列をパースし、その結果生成された html.Node ツリーを再帰的に走査して、<a> タグの href 属性を抽出する具体的な例を示しています。この例も、子ノードの走査に c := n.FirstChild; c != nil; c = c.NextSibling のパターンを使用しており、正しい使い方を開発者に提示しています。

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

diff --git a/src/pkg/exp/html/doc.go b/src/pkg/exp/html/doc.go
index 56b194ffb9..4dd453091c 100644
--- a/src/pkg/exp/html/doc.go
+++ b/src/pkg/exp/html/doc.go
@@ -84,7 +84,7 @@ example, to process each anchor node in depth-first order:
 		if n.Type == html.ElementNode && n.Data == "a" {
 			// Do something with n...
 		}
-		for _, c := range n.Child {
+		for c := n.FirstChild; c != nil; c = c.NextSibling {
 			f(c)
 		}
 	}
diff --git a/src/pkg/exp/html/example_test.go b/src/pkg/exp/html/example_test.go
new file mode 100644
index 0000000000..c15e9a2bd8
--- /dev/null
+++ b/src/pkg/exp/html/example_test.go
@@ -0,0 +1,39 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This example demonstrates parsing HTML data and walking the resulting tree.
+package html_test
+
+import (
+	"exp/html"
+	"fmt"
+	"log"
+	"strings"
+)
+
+func ExampleParse() {
+	s := `<p>Links:</p><ul><li><a href="foo">Foo</a><li><a href="/bar/baz">BarBaz</a></ul>`
+	doc, err := html.Parse(strings.NewReader(s))
+	if err != nil {
+		log.Fatal(err)
+	}
+	var f func(*html.Node)
+	f = func(n *html.Node) {
+		if n.Type == html.ElementNode && n.Data == "a" {
+			for _, a := range n.Attr {
+				if a.Key == "href" {
+					fmt.Println(a.Val)
+					break
+				}
+			}
+		}
+		for c := n.FirstChild; c != nil; c = c.NextSibling {
+			f(c)
+		}
+	}
+	f(doc)
+	// Output:
+	// foo
+	// /bar/baz
+}

コアとなるコードの解説

src/pkg/exp/html/doc.go の変更

このファイルは exp/html パッケージのドキュメントを定義しています。変更点は1行のみですが、非常に重要です。

-		for _, c := range n.Child {
+		for c := n.FirstChild; c != nil; c = c.NextSibling {

• 変更前 (for _, c := range n.Child): この行は、n.Child というスライスが存在し、その要素を range キーワードでイテレートできるかのように記述されていました。しかし、実際には html.Node 構造体には Child というスライスフィールドは存在しません。これは、パッケージの設計と実際のAPIとの間に誤解を生む可能性がありました。
• 変更後 (for c := n.FirstChild; c != nil; c = c.NextSibling): この行は、連結リストを走査するためのGo言語における標準的なイディオムです。
  • c := n.FirstChild: 現在のノード n の最初の子ノードを c に代入し、走査を開始します。
  • c != nil: c が nil (つまり、子ノードがもう存在しない) でない限りループを続けます。
  • c = c.NextSibling: 現在の子ノード c の次の兄弟ノードを c に代入し、次のイテレーションに進みます。

この修正により、パッケージのドキュメントが実際のAPIと一致し、開発者が子ノードを正しく走査する方法を理解できるようになりました。

src/pkg/exp/html/example_test.go の追加

このファイルは新しく追加されたもので、exp/html パッケージの具体的な使用例 (ExampleParse 関数) を含んでいます。Goの Example 関数は、ドキュメントの一部として自動的にテストされ、その出力がコメント (// Output:) と一致するかどうかが検証されます。これにより、ドキュメントの正確性とコードの動作が保証されます。

func ExampleParse() {
	s := `<p>Links:</p><ul><li><a href="foo">Foo</a><li><a href="/bar/baz">BarBaz</a></ul>`
	doc, err := html.Parse(strings.NewReader(s))
	if err != nil {
		log.Fatal(err)
	}
	var f func(*html.Node)
	f = func(n *html.Node) {
		if n.Type == html.ElementNode && n.Data == "a" {
			for _, a := range n.Attr {
				if a.Key == "href" {
					fmt.Println(a.Val)
					break
				}
			}
		}
		for c := n.FirstChild; c != nil; c = c.NextSibling {
			f(c)
		}
	}
	f(doc)
	// Output:
	// foo
	// /bar/baz
}

• HTML文字列のパース: s に定義されたHTML文字列を html.Parse 関数でパースし、doc (ルートノード) を取得します。
• 再帰的な走査関数 f: f は *html.Node を引数にとる関数で、HTMLツリーを深さ優先で走査します。
• <a> タグの検出と属性抽出: n.Type == html.ElementNode && n.Data == "a" で <a> タグを検出し、その属性 (n.Attr) から href 属性の値を抽出して出力します。
• 子ノードの走査: ここでも for c := n.FirstChild; c != nil; c = c.NextSibling という連結リストの走査イディオムが使われています。これにより、現在のノードのすべての子ノードに対して再帰的に f が呼び出され、ツリー全体が走査されます。
• 出力の検証: // Output: コメントは、この例を実行した際の期待される出力を示しており、Goのテストシステムによって自動的に検証されます。

この新しい例は、exp/html パッケージを使ってHTMLツリーをパースし、特定の要素を検索し、その属性を抽出するという一般的なタスクを、連結リストの走査という正しい方法でどのように行うかを示す明確なガイドラインとなります。

関連リンク

• Go言語の html パッケージ (現在の場所): https://pkg.go.dev/golang.org/x/net/html

参考にした情報源リンク

• golang.org/x/net/html パッケージにおけるノードの子要素が連結リストであることに関する情報: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEb_Ixs_VICqxTkvm6E5Elci2mEfHmGl99ZBbaEoBQHC2pfh5X_Qau2fNFYIiWvJIoAU8P41TURTJW03h1Wa-cldLaU5EI3T9eWwGbdWqBowaxsMqZ_edY2_aBcKd2QZ2Xi
• Go言語におけるスライスと連結リストの一般的な特性に関する情報:
  • https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQE85Qe1bD_uTdOKjp471SXDkel2WqpK5y1RmEulbJTYH5wrJJnxt6ayLiK82IaKNAFq3tsUk3Kp3RQCwIxsrHMEuFL4TaolNMyIjh-dfnXU25GVjk_WDrALMAoNpBJ17KducWstETa5fXedyNnhTHmDc7AYC33mI7DC6oHeACkO_mRoJDJV
  • https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFhH7G7PeMYHiwWfkRFYYNx6cStkouf3MU_ezmVAyt1d-jQ30jpxHG5LVo4YgEGPog4QyWuHJdkMtT-tbmJdwR3MpuYDZeji-CZupKtkk5Vl40nD9SF47H5t3IjQ7eh0bmWIBeDICZWPCn_dbM9zAXjjazS9T5hr0DTVsFXtay

（注: コミットメッセージ内の https://golang.org/cl/6618055 は、ウェブ検索の結果、go.net/websocket に関連する別の変更リストを指しているようでした。これは、Goの内部的な変更リスト番号が時間とともに再利用されたか、または公開されているCLと内部的なCLの対応が異なるためと考えられます。本解説では、コミットの実際の変更内容と、exp/html パッケージの設計に関する情報に基づいて記述しています。）