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

このコミットは、Go言語の実験的なHTMLパーサーパッケージ exp/html における内部メソッドの簡素化を目的としています。具体的には、HTML要素を追加する際のロジックを整理し、コードの重複を減らし、可読性と保守性を向上させています。この変更により、ベンチマークでわずかながらパフォーマンスの改善も確認されています。

コミット

commit 66429dcf75f37cdae380081396b86b8f6787a96a
Author: Nigel Tao <nigeltao@golang.org>
Date:   Wed Jun 13 10:13:05 2012 +1000

    exp/html: simplify some of the parser's internal methods.
    
    benchmark          old ns/op    new ns/op    delta
    BenchmarkParser      4006888      3950604   -1.40%
    
    R=r, andybalholm
    CC=golang-dev
    https://golang.org/cl/6301070

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

https://github.com/golang/go/commit/66429dcf75f37cdae380081396b86b8f6787a96a

元コミット内容

exp/html: simplify some of the parser's internal methods.

このコミットは、パーサーの内部メソッドの一部を簡素化します。

ベンチマーク結果: BenchmarkParser: 4006888 ns/op -> 3950604 ns/op (1.40%改善)

レビュー担当者: r, andybalholm CC: golang-dev コードレビューリンク: https://golang.org/cl/6301070

変更の背景

Go言語の exp/html パッケージは、HTML5の仕様に準拠したHTMLパーサーを提供します。HTMLのパースは非常に複雑なプロセスであり、特にエラーハンドリングや、ブラウザがHTMLをどのように解釈するかを模倣する「癒し」のメカニズム（tag soup parsing）が重要になります。

このコミットが行われた当時、exp/html パッケージはまだ実験段階（exp は "experimental" の略）であり、コードベースの改善と最適化が活発に行われていました。HTMLパーサーの内部では、入力ストリームから読み取ったトークン（タグ、テキストなど）に基づいて、DOMツリーにノードを追加する処理が頻繁に行われます。

以前の実装では、要素を追加するメソッド（例: addElement, addFormattingElement）が、常にタグ名、属性などの情報を引数として受け取っていました。しかし、多くの場合、これらの情報はパーサーが現在処理しているトークン（p.tok）から直接取得できるものでした。この重複した情報の受け渡しは、コードの冗長性を生み、可読性を低下させ、潜在的なバグの原因となる可能性がありました。

このコミットの背景には、以下の目的があったと考えられます。

コードの簡素化と可読性の向上: 頻繁に呼び出される内部メソッドのシグネチャを簡素化し、呼び出し側のコードをよりクリーンにする。
保守性の向上: 重複する引数を排除することで、将来的な変更やデバッグを容易にする。
パフォーマンスの最適化: メソッド呼び出しのオーバーヘッド削減や、より効率的なデータアクセスにより、パース処理全体のパフォーマンスを改善する。実際にベンチマークでわずかながら改善が見られています。
HTML5パースアルゴリズムへの準拠: HTML5のパースアルゴリズムは非常に詳細であり、その複雑なルールを正確に実装するためには、内部ロジックの明確さと効率性が求められます。

前提知識の解説

このコミットを理解するためには、以下の概念が前提となります。

HTML5パースアルゴリズム:
- HTML5の仕様には、ブラウザがHTMLドキュメントをどのようにパースし、DOMツリーを構築するかを厳密に定義したアルゴリズムが含まれています。これは、エラーのあるHTML（「タグスープ」）でも一貫した結果を生成するために非常に重要です。
- パーサーは、入力ストリームをトークン化し（字句解析）、そのトークンに基づいてDOMツリーを構築します（構文解析）。
- パースプロセスは、様々な「挿入モード (insertion mode)」と呼ばれる状態を持ち、現在のモードと入力トークンに応じて、次のアクションが決定されます。
- 要素スタック (Stack of open elements): 現在開いているHTML要素のスタックです。新しい要素が追加されるとプッシュされ、閉じられるとポップされます。
- アクティブフォーマット要素リスト (List of active formatting elements): <b>, <i> などのフォーマット要素のスコープを管理するためのリストです。ネストされたフォーマット要素や、暗黙的に閉じられるべき要素の処理に用いられます。
- 暗黙的なトークン (Implied tokens): HTML5のパースアルゴリズムでは、特定の状況下で、実際には入力ストリームに存在しないが、パーサーが「存在するものとして扱う」トークン（要素）が生成されることがあります。例えば、<html> タグが省略されていても、パーサーは自動的にそれを挿入します。
Go言語の exp/html パッケージ:
- Go言語の標準ライブラリの一部として提供されるHTMLパーサーです。golang.org/x/net/html パッケージとして利用可能です。
- このパッケージは、HTML5のパースアルゴリズムをGoで実装しており、HTMLドキュメントをDOMツリー（*html.Node）として表現します。
- parser 構造体は、パースの状態（現在のトークン、要素スタック、挿入モードなど）を管理します。
- Token 構造体は、パーサーが読み取った個々のHTMLトークン（StartTag, EndTag, Textなど）を表します。DataAtom はタグの正規化されたアトム（例: a.Html）、Data は元のタグ名文字列（例: "html"）、Attr は属性のリストです。
a.Atom 型:
- golang.org/x/net/html/atom パッケージで定義されている型で、HTMLのタグ名や属性名を効率的に扱うためのアトム化された（整数値にマッピングされた）表現です。文字列比較よりも高速な比較が可能です。

技術的詳細

このコミットの主要な技術的変更点は、HTMLパーサーの内部メソッドのシグネチャ変更と、それに伴う呼び出し箇所の修正です。

addElement メソッドの変更:
- 変更前: func (p *parser) addElement(tagAtom a.Atom, tag string, attr []Attribute)
  - このメソッドは、新しいHTML要素ノードをDOMツリーに追加するために使用されていました。引数として、タグのアトム、タグ名文字列、属性のリストを明示的に受け取っていました。
- 変更後: func (p *parser) addElement()
  - 引数がすべて削除されました。代わりに、このメソッドはパーサーの現在のトークン p.tok から、DataAtom、Data、Attr の情報を直接取得してノードを生成するようになりました。
  - これにより、p.addElement(p.tok.DataAtom, p.tok.Data, p.tok.Attr) のような冗長な呼び出しが、単に p.addElement() と書けるようになり、コードが大幅に簡素化されました。
addSyntheticElement メソッドの導入:
- func (p *parser) addSyntheticElement(tagAtom a.Atom, attr []Attribute)
  - addElement が現在のトークンに依存するようになったため、パーサーが明示的に（現在の入力トークンとは関係なく）新しい要素を生成する必要があるケース（例: 暗黙的に挿入される <html> や <p> タグなど）に対応するために、この新しいメソッドが導入されました。
  - このメソッドは、タグのアトムと属性のリストを引数として受け取り、それらを使用してノードを生成します。
addFormattingElement メソッドの変更:
- 変更前: func (p *parser) addFormattingElement(tagAtom a.Atom, tag string, attr []Attribute)
- 変更後: func (p *parser) addFormattingElement()
  - addElement と同様に、引数が削除され、現在のトークン p.tok から情報を取得するようになりました。
  - 内部では、新しい p.addElement() を呼び出す形に変更されています。
  - また、フォーマット要素の重複チェックロジックにおいて、n.Data != tag という文字列比較が n.DataAtom != tagAtom というアトム比較に変更されました。アトム比較は通常、文字列比較よりも高速であり、正規化された値を使用するため、より堅牢です。
parseImpliedToken メソッドの変更:
- 変更前: func (p *parser) parseImpliedToken(t TokenType, dataAtom a.Atom, data string, attr []Attribute)
- 変更後: func (p *parser) parseImpliedToken(t TokenType, dataAtom a.Atom, data string)
  - 暗黙的なトークンをパースする際に、attr（属性）の引数が削除されました。暗黙的に生成されるトークンは、通常、特定の属性を持たないか、その属性が文脈から導出されるため、この引数は不要と判断されたと考えられます。

これらの変更により、パーサーのコード全体で要素追加ロジックがより一貫性のあるものになり、特に p.tok の情報に依存するケースでは、呼び出し側のコードが大幅に簡潔になりました。

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

変更はすべて src/pkg/exp/html/parse.go ファイル内で行われています。

主な変更点は以下のメソッドのシグネチャと実装、およびそれらの呼び出し箇所です。

addElement メソッドのシグネチャ変更と実装:

--- a/src/pkg/exp/html/parse.go
+++ b/src/pkg/exp/html/parse.go
@@ -279,21 +279,30 @@ func (p *parser) addText(text string) {
 	})\n }\n 
-// addElement calls addChild with an element node.\n-// TODO: tagAtom, tag and attr are almost always p.tok.DataAtom, p.tok.Data, p.tok.Attr.\n-// The common case should be a no-arg addElement method.\n-func (p *parser) addElement(tagAtom a.Atom, tag string, attr []Attribute) {
+// addElement adds a child element based on the current token.
+func (p *parser) addElement() {
+	p.addChild(&Node{
+		Type:     ElementNode,
+		DataAtom: p.tok.DataAtom,
+		Data:     p.tok.Data,
+		Attr:     p.tok.Attr,
+	})
+}
+
+// addSyntheticElement adds a child element with the given tag and attributes.
+func (p *parser) addSyntheticElement(tagAtom a.Atom, attr []Attribute) {
 	p.addChild(&Node{
 		Type:     ElementNode,
 		DataAtom: tagAtom,
-		Data:     tag,
+		Data:     tagAtom.String(),
 		Attr:     attr,
 	})\n }\n 
 // Section 12.2.3.3.
-func (p *parser) addFormattingElement(tagAtom a.Atom, tag string, attr []Attribute) {
-	p.addElement(tagAtom, tag, attr)
+func (p *parser) addFormattingElement() {
+	tagAtom, attr := p.tok.DataAtom, p.tok.Attr
+	p.addElement()
 
 	// Implement the Noah's Ark clause, but with three per family instead of two.
 	identicalElements := 0
@@ -309,7 +318,7 @@ findIdenticalElements:
 		if n.Namespace != "" {
 			continue
 		}
-		if n.Data != tag {
+		if n.DataAtom != tagAtom {
 			continue
 		}
 		if len(n.Attr) != len(attr) {

parseImpliedToken メソッドのシグネチャ変更:

--- a/src/pkg/exp/html/parse.go
+++ b/src/pkg/exp/html/parse.go
@@ -1933,13 +1942,12 @@ func (p *parser) inForeignContent() bool {
 
 // parseImpliedToken parses a token as though it had appeared in the parser's
 // input.
-func (p *parser) parseImpliedToken(t TokenType, dataAtom a.Atom, data string, attr []Attribute) {
+func (p *parser) parseImpliedToken(t TokenType, dataAtom a.Atom, data string) {
  	realToken, selfClosing := p.tok, p.hasSelfClosingToken
  	p.tok = Token{
  		Type:     t,
  		DataAtom: dataAtom,
  		Data:     data,
-		Attr:     attr,
  	}
  	p.hasSelfClosingToken = false
  	p.parseCurrentToken()

addElement、addFormattingElement、parseImpliedToken の呼び出し箇所の変更: ファイル全体で、これらのメソッドの呼び出し方が新しいシグネチャに合わせて変更されています。
- p.addElement(p.tok.DataAtom, p.tok.Data, p.tok.Attr) のようなパターンは p.addElement() に。
- p.addElement(a.Form, a.Form.String(), nil) のような、現在のトークンに依存しない要素追加は p.addSyntheticElement(a.Form, nil) に。
- p.addFormattingElement(p.tok.DataAtom, p.tok.Data, p.tok.Attr) は p.addFormattingElement() に。
- p.parseImpliedToken(EndTagToken, a.Select, a.Select.String(), nil) は p.parseImpliedToken(EndTagToken, a.Select, a.Select.String()) に。

コアとなるコードの解説

このコミットの核心は、HTMLパーサーがDOMツリーにノードを追加する際の内部ロジックを、より効率的かつ簡潔にするためのリファクタリングです。

addElement() の変更と addSyntheticElement() の導入: 変更前の addElement は、タグのアトム、タグ名、属性を引数として受け取っていました。これは汎用的な関数でしたが、HTMLパーサーの多くの箇所では、現在処理中のトークン（p.tok）からこれらの情報を取得して addElement に渡していました。例えば、p.addElement(p.tok.DataAtom, p.tok.Data, p.tok.Attr) のように、p.tok の情報をそのまま渡すパターンが頻繁に見られました。

このコミットでは、この共通パターンを最適化するために、addElement() を引数なしのメソッドに変更しました。新しい addElement() は、呼び出された時点で p.tok に格納されている情報を自動的に使用してノードを作成します。これにより、呼び出し側のコードは p.addElement() と書くだけで済み、冗長な引数の記述が不要になりました。

しかし、HTML5のパースアルゴリズムでは、入力ストリームに明示的に存在しない要素（例えば、省略された <html> タグや、特定の状況で自動的に挿入される <p> タグなど）を「合成的に (synthetically)」生成する必要がある場合があります。これらの要素は p.tok の情報に依存しないため、引数なしの addElement() では対応できません。この問題を解決するために、addSyntheticElement(tagAtom a.Atom, attr []Attribute) という新しいメソッドが導入されました。このメソッドは、合成的に生成される要素のために、必要なタグのアトムと属性を明示的に引数として受け取ります。

この分離により、コードの意図がより明確になりました。

p.addElement(): 現在の入力トークンに基づいて要素を追加する。
p.addSyntheticElement(): 現在の入力トークンとは独立して、パーサーのロジックによって暗黙的に（合成的に）要素を追加する。

addFormattingElement() の変更: addFormattingElement も同様に引数なしに変更され、内部で新しい p.addElement() を呼び出すようになりました。これにより、フォーマット要素の追加も現在のトークンに依存する形に統一されました。また、このメソッド内の n.Data != tag から n.DataAtom != tagAtom への変更は、文字列比較からアトム比較への移行を示しています。アトムは、文字列を整数値にマッピングしたもので、比較が非常に高速です。これにより、パフォーマンスが向上し、また、タグ名の大文字・小文字の区別など、文字列比較で発生しうる問題を回避できます。

parseImpliedToken() の変更: parseImpliedToken から attr 引数が削除されたのは、暗黙的に生成されるトークンが通常、特定の属性を持たないか、その属性が文脈から導出されるため、この引数が不要と判断されたためです。これにより、メソッドのシグネチャが簡潔になり、呼び出し側のコードも簡素化されました。

これらの変更は、HTMLパーサーの内部構造をより整理し、コードの重複を排除し、保守性を高めることに貢献しています。また、ベンチマーク結果が示すように、わずかながらもパフォーマンスの改善にも繋がっています。

参考にした情報源リンク

上記のGitHubコミットページ
Go言語の exp/html パッケージのソースコード
HTML5仕様書 (WHATWG)
Go言語のドキュメント
一般的なHTMLパーサーの動作原理に関する知識
GoのHTMLパーサーの内部構造に関する議論 (golang-devメーリングリストなど) - コミットメッセージに CC=golang-dev とあるため、関連する議論がメーリングリストにある可能性があります。
Goのコードレビューシステム (Gerrit) - コミットメッセージに記載されているCL (Change-list) リンク。より詳細な議論や変更の経緯が確認できます。

comemo