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

このコミットは、Go言語の実験的なHTMLパーサーパッケージ exp/html 内の atom サブパッケージに対する変更です。具体的には、HTML要素のタグ名や属性キーを効率的に扱うための「アトム（Atom）」のセットを拡張し、exp/html パーサーが扱う全てのタグを網羅するようにしています。これにより、パーサーの網羅性と堅牢性が向上します。

コミット

commit 90fa13d2b7eee8b785428e0015b29aea95b8e75a
Author: Nigel Tao <nigeltao@golang.org>
Date:   Thu Jun 7 09:35:35 2012 +1000

    exp/html/atom: add more atoms.
    
    This completely covers the tags used by exp/html's parser.
    
    Before:
    295 atoms; 1406 string bytes + 2048 tables = 3454 total data
    BenchmarkLookup    50000         59841 ns/op
    
    After:
    322 atoms; 1508 string bytes + 2048 tables = 3556 total data
    BenchmarkLookup    50000         60159 ns/op
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6296045

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

https://github.com/golang/go/commit/90fa13d2b7eee8b785428e0015b29aea95b8e75a

元コミット内容

exp/html/atom: add more atoms.

このコミットの目的は、exp/html パッケージのHTMLパーサーが使用するタグを完全にカバーするために、より多くのアトムを追加することです。変更前と変更後のベンチマーク結果が示されており、アトムの数が増加し、それに伴いデータサイズとルックアップ時間がわずかに増加していることがわかります。

変更の背景

Go言語の exp/html パッケージは、HTML5の仕様に準拠したHTMLパーサーを提供することを目的としていました。このパーサーは、HTMLドキュメントを効率的に解析するために、頻繁に出現するHTMLの文字列（タグ名や属性キーなど）を整数コード（アトム）にマッピングする仕組みを採用しています。

このコミットが行われる前は、exp/html パーサーが内部的に使用する全てのHTMLタグがアトムとして登録されていませんでした。アトムとして登録されていない文字列は、パーサーが処理する際に毎回文字列として比較・格納されるため、パフォーマンスの低下やメモリ使用量の増加につながる可能性があります。

このコミットの背景にあるのは、exp/html パーサーの網羅性を高め、全ての既知のHTMLタグをアトムとして事前に登録することで、パーサーの効率性と堅牢性を向上させるという明確な意図です。特に、HTMLは通常タグ名の大文字・小文字を区別しませんが、SVG（Scalable Vector Graphics）のようにHTML内に埋め込まれるXMLベースのコンテンツでは大文字・小文字が区別される場合があります。このコミットでは、foreignObject のようにHTMLとSVGの両方で使われる可能性のあるタグについて、両方のケース（foreignObject と foreignobject）をアトムとして追加することで、このような複雑なケースにも対応しています。

前提知識の解説

HTMLアトム (HTML Atoms)

HTMLアトムとは、HTMLパーサーにおいて、頻繁に出現する特定の文字列（HTMLタグ名、属性名など）を効率的に扱うために、それらを一意の整数値（ID）にマッピングする仕組みです。

なぜアトムを使うのか？

パフォーマンスの向上: 文字列の比較は、整数値の比較よりも計算コストが高いです。アトムを使用することで、文字列の比較を整数値の比較に置き換え、パーシング速度を向上させることができます。
メモリ使用量の削減: 同じ文字列がHTMLドキュメント内で何度も出現する場合、その都度新しい文字列オブジェクトを生成する代わりに、共通のアトムIDを参照することでメモリ使用量を削減できます。
コードの簡潔性: 複雑な文字列比較ロジックを、シンプルな整数値の比較に置き換えることで、パーサーのコードをより簡潔に保つことができます。

Go言語の exp/html パッケージでは、このアトムの概念が atom サブパッケージとして実装されており、Atom 型が整数コードを表し、Lookup 関数が文字列からアトムへの変換を行います。

Go言語の `exp/html` パッケージ

exp/html は、Go言語でHTML5の仕様に準拠したHTMLパーサーを提供する実験的なパッケージです。このパッケージは、ウェブブラウザがHTMLを解析するのと同じ方法でHTMLドキュメントを解析し、DOM（Document Object Model）ツリーを構築することを目的としています。ウェブスクレイピング、HTMLの変換、HTMLの検証など、様々な用途で利用されます。

HTMLとSVGにおける大文字・小文字の区別

HTML: HTMLのタグ名や属性名は、一般的に大文字・小文字を区別しません（ケースインセンシティブ）。例えば、<p> と <P> は同じ段落要素として扱われます。
SVG (Scalable Vector Graphics): SVGはXMLベースの画像フォーマットであり、XMLのルールに従ってタグ名や属性名は大文字・小文字を区別します（ケースセンシティブ）。
HTMLに埋め込まれたSVG: HTML5では、SVGを直接HTMLドキュメント内に埋め込むことができます。この場合、SVGの要素はSVGのルールに従い、大文字・小文字が区別されます。

このコミットで foreignObject と foreignobject の両方がアトムとして追加されているのは、この大文字・小文字の区別の違いに対応するためです。foreignObject はSVGの要素であり、HTMLパーサーがSVGコンテンツを正しく処理するためには、そのケースセンシティブな名前もアトムとして認識する必要があるためです。

ハッシュテーブルによる文字列ルックアップ

アトムのルックアップ（文字列からアトムIDへの変換）は、通常、ハッシュテーブル（またはハッシュマップ）を使用して効率的に行われます。

ハッシュ関数: 入力文字列（タグ名など）を数値（ハッシュ値）に変換する関数です。
衝突解決: 異なる文字列が同じハッシュ値を生成する「衝突」が発生した場合に、それを解決するメカニズム（例: チェイニング、オープンアドレス法）。
テーブル: ハッシュ値に基づいてアトムIDや関連データを格納する配列です。

このコミットでは、table.go ファイル内でハッシュテーブルのデータが更新されており、新しいアトムが追加されたことで、ハッシュ関数やテーブル構造が再生成されたことが示唆されます。

技術的詳細

このコミットの技術的詳細は、主に exp/html/atom パッケージの内部実装に焦点を当てています。

アトムの定義と生成:
- src/pkg/exp/html/atom/gen.go: このファイルは、アトムとして登録される文字列のリストを定義しています。このコミットでは、extra スライスに多数の新しいHTMLタグ名や属性名が追加されています。これらの文字列は、Goのコード生成ツールによって table.go 内のアトム定数とルックアップテーブルに変換されます。
- 追加されたアトムには、annotation-xml, basefont, bgsound, big, desc, face, foreignObject, foreignobject, image, isindex, listing, malignmark, marquee, math, mglyph, mi, mn, mo, ms, mtext, noembed, noframes, plaintext, strike, svg, tt, xmp などがあります。これらは、HTML5で定義されている要素や、古いHTMLバージョン、あるいはSVGなどの埋め込みコンテンツで使われる可能性のある要素を含んでいます。
ルックアップテーブルの更新:
- src/pkg/exp/html/atom/table.go: このファイルは、gen.go から生成されるアトムの定数と、文字列からアトムIDへの高速ルックアップを可能にするハッシュテーブル (table 変数) を含んでいます。
- 新しいアトムが追加されたため、既存のアトムIDのオフセットが変更され、Atom 定数の値が多数更新されています。
- hash0 という定数（ハッシュ関数のシード値または初期値）も変更されています。これは、新しいアトムセットに対して最適なハッシュ分布を得るために、ハッシュテーブルの再生成プロセスで調整されたことを示唆しています。
- table 配列自体も大幅に変更されており、新しいアトムに対応するエントリが追加され、既存のエントリの位置も再配置されています。
- atomText という全ての文字列を連結した巨大な文字列も更新されています。これは、アトムIDから元の文字列への変換（Atom.String() メソッド）で使われるデータです。
ケースセンシティブなルックアップの明示:
- src/pkg/exp/html/atom/atom.go のコメントが更新され、Lookup 関数が「ケースセンシティブ」であることが明示されました。これは、foreignObject のようなSVG関連のアトムが追加されたことと関連しています。HTMLタグは通常ケースインセンシティブですが、SVG要素はケースセンシティブであるため、パーサーが両方の形式を正しく識別できるように、ルックアップがケースセンシティブであるという注意書きが追加されたと考えられます。
テストの追加と更新:
- src/pkg/exp/html/atom/atom_test.go: TestForeignObject という新しいテストケースが追加されています。このテストは、foreignobject (小文字) と foreignObject (キャメルケース) の両方のアトムが正しくルックアップされ、文字列に変換されることを検証しています。これは、SVG要素のケースセンシティブな性質に対応するための重要なテストです。
- src/pkg/exp/html/atom/table_test.go: testAtomList が更新され、新しく追加された全てのアトムが含まれるようになりました。これにより、全てのアトムがテストスイートによって網羅的に検証されることが保証されます。
パフォーマンスへの影響:
- コミットメッセージに記載されているベンチマーク結果は、アトムの数が増加したことによるデータサイズとルックアップ時間のわずかな増加を示しています。
  - 変更前: 295 atoms; 1406 string bytes + 2048 tables = 3454 total data, BenchmarkLookup 50000 59841 ns/op
  - 変更後: 322 atoms; 1508 string bytes + 2048 tables = 3556 total data, BenchmarkLookup 50000 60159 ns/op
- アトムの数が増えれば、ハッシュテーブルのサイズや文字列データの量が増加し、ルックアップの平均時間もわずかに増加するのは自然なことです。この程度の性能低下は、パーサーの網羅性と正確性の向上というメリットと比較して許容範囲内と判断されたと考えられます。

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

このコミットにおける主要なコード変更は以下のファイルに集中しています。

src/pkg/exp/html/atom/atom.go:
- パッケージコメントの修正: HTML文字列が「lower-case」であるという記述が削除されました。
- Lookup 関数のコメント修正: ルックアップが「case sensitive」であるという記述が追加されました。
src/pkg/exp/html/atom/atom_test.go:
- TestForeignObject 関数が追加され、foreignobject と foreignObject の両方のアトムのルックアップと文字列変換をテストしています。
src/pkg/exp/html/atom/gen.go:
- extra スライスに、annotation-xml, basefont, bgsound, big, desc, face, foreignObject, foreignobject, image, isindex, listing, malignmark, marquee, math, mglyph, mi, mn, mo, ms, mtext, noembed, noframes, plaintext, strike, svg, tt, xmp などの新しい文字列が追加されました。
src/pkg/exp/html/atom/table.go:
- 多数の新しい Atom 定数が追加され、既存の定数の値も変更されました。
- hash0 定数の値が 0x516c42b0 から 0xc17da63e に変更されました。
- table 配列（ハッシュテーブルの実体）の内容が大幅に更新され、新しいアトムのエントリが追加されました。
- atomText 文字列（全てのアトム名を連結したもの）が更新され、新しいアトム名が含まれるようになりました。
src/pkg/exp/html/atom/table_test.go:
- testAtomList スライスに、gen.go で追加された新しいアトム名が全て追加されました。

コアとなるコードの解説

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

// Package atom provides integer codes (also known as atoms) for a fixed set of
// frequently occurring HTML strings: tag names and attribute keys such as "p"
// and "id".
// ...
// Lookup returns the atom whose name is s. It returns zero if there is no
// such atom. The lookup is case sensitive.
func Lookup(s []byte) Atom {
	if len(s) == 0 || len(s) > maxAtomLen {
		return 0
	}
	// ... (ハッシュテーブルによるルックアップロジック)
}

パッケージコメントから「lower-case」という記述が削除されたのは、foreignObject のように大文字を含むアトムが追加されたため、もはや全てのタグ名が小文字であるという前提がなくなったことを反映しています。 Lookup 関数のコメントに「The lookup is case sensitive.」が追加されたのは、SVG要素の foreignObject のようなケースセンシティブな名前を正確に処理するために、この関数の振る舞いが明確にされたことを示しています。これは、HTMLパーサーがHTMLとXML（SVG）の異なるケースセンシティブ規則を適切に扱う必要があるため重要です。

`src/pkg/exp/html/atom/atom_test.go`

func TestForeignObject(t *testing.T) {
	const (
		afo = Foreignobject
		afO = ForeignObject
		sfo = "foreignobject"
		sfO = "foreignObject"
	)
	if got := Lookup([]byte(sfo)); got != afo {
		t.Errorf("Lookup(%q): got %#v, want %#v", sfo, got, afo)
	}
	if got := Lookup([]byte(sfO)); got != afO {
		t.Errorf("Lookup(%q): got %#v, want %#v", sfO, got, afO)
	}
	if got := afo.String(); got != sfo {
		t.Errorf("Atom(%#v).String(): got %q, want %q", afo, got, sfo)
	}
	if got := afO.String(); got != sfO {
		t.Errorf("Atom(%#v).String(): got %q, want %q", afO, got, sfO)
	}
}

この新しいテストケースは、foreignobject (全て小文字) と foreignObject (キャメルケース) の両方が正しくアトムとして認識され、またアトムから元の文字列に変換できることを検証しています。これは、HTMLのケースインセンシティブな性質と、SVGのケースセンシティブな性質の両方に対応する必要があるという、このコミットの重要な側面を強調しています。

`src/pkg/exp/html/atom/gen.go`

var extra = []string{
	"align",
	"annotation",
	"annotation-xml", // 追加
	"applet",
	"basefont",      // 追加
	"bgsound",       // 追加
	"big",           // 追加
	"center",
	"color",
	"desc",          // 追加
	"face",          // 追加
	"font",
	"foreignObject", // HTML is case-insensitive, but SVG-embedded-in-HTML is case-sensitive. // 追加
	"foreignobject", // 追加
	// ... 他の追加されたアトム
}

extra スライスは、アトムとして登録される追加の文字列を定義しています。このリストに新しいタグ名や属性名が追加されることで、go generate コマンド（またはそれに相当するビルドプロセス）が実行された際に、table.go ファイルが再生成され、新しいアトムがシステムに組み込まれます。コメントにある foreignObject の説明は、HTMLとSVGのケースセンシティブ性の違いを明確に示しており、なぜ両方の形式が必要なのかを説明しています。

`src/pkg/exp/html/atom/table.go`

const (
	A                Atom = 0x1
	Abbr             Atom = 0x4
	Accept           Atom = 0x2106 // 値が変更
	// ... 多数のAtom定数が追加・変更
	AnnotationXml    Atom = 0x1870e // 新規追加
	Basefont         Atom = 0x10208 // 新規追加
	// ...
	ForeignObject    Atom = 0x1fb0d // 新規追加
	Foreignobject    Atom = 0x2080d // 新規追加
	// ...
)

const hash0 = 0xc17da63e // 値が変更

var table = [1 << 9]Atom{
	// ... ハッシュテーブルのエントリが大幅に変更・追加
}

const atomText = "abbradiogrouparamalignmarkbdialogaccept-charsetbodyaccesskey" +
	// ... 新しいアトム名を含むように文字列が変更

このファイルは、アトムシステムの「心臓部」です。

Atom 定数の値が変更されたり、新しい定数が追加されたりしているのは、アトムの総数が増えたため、各アトムに割り当てられる一意の整数値（ID）が再計算された結果です。
hash0 の変更は、ハッシュテーブルの再生成時に、新しいアトムセットに対して最適なハッシュ分布を実現するために、ハッシュ関数の初期シード値が調整されたことを意味します。
table 配列の変更は、新しいアトムがハッシュテーブルに組み込まれ、既存のアトムの位置も再計算されたことを示しています。このテーブルは、Lookup 関数が文字列からアトムIDを効率的に検索するために使用します。
atomText の変更は、アトムIDから元の文字列への逆変換（Atom.String()）をサポートするために、全てのアトム名を連結した文字列が更新されたことを示しています。

これらの変更は、新しいアトムをシステムに完全に統合し、効率的なルックアップと逆変換を維持するために不可欠です。

参考にした情報源リンク

HTML Standard - 13.1.2.1 Case-sensitivity of tags: https://html.spec.whatwg.org/multipage/syntax.html#case-sensitivity-of-tags
SVG 2 Specification - Case Sensitivity: https://svgwg.org/svg2-draft/single-page.html#text-CaseSensitivity
Go言語の go generate コマンドについて: https://go.dev/blog/generate
ハッシュテーブル (Wikipedia): https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB

comemo