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

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

このコミットは、Go言語のHTMLパーサーにおける「挿入モード (insertion mode)」の管理方法を根本的に変更するものです。これまでのパーサーでは、状態遷移関数が次の挿入モードとトークンの消費有無を返していましたが、この変更により、現在の挿入モードがパーサー構造体自体に直接格納されるようになります。これにより、特定の挿入モードが別の挿入モードのルールを使用する必要がある場合の処理が簡素化され、関数比較の必要性が排除されます。

コミット

commit 631a575fd92b711854930f3b03b40a2bf66bbd29
Author: Andrew Balholm <andybalholm@gmail.com>
Date:   Sun Nov 13 12:39:41 2011 +1100

    html: store the current insertion mode in the parser
    
    Currently, the state transition functions in the HTML parser
    return the next insertion mode and whether the token is consumed.
    This works well except for when one insertion mode needs to use
    the rules for another insertion mode. Then the useTheRulesFor
    function needs to patch things up. This requires comparing functions
    for equality, which is going to stop working.
    
    Adding a field to the parser structure to store the current
    insertion mode eliminates the need for useTheRulesFor;
    one insertion mode function can now just call the other
    directly. The insertion mode will be changed only if it needs to be.
    
    This CL is an alternative to CL 5372078.
    
    R=nigeltao, rsc
    CC=golang-dev
    https://golang.org/cl/5372079

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

https://github.com/golang/go/commit/631a575fd92b711854930f3b03b40a2bf66bbd29

元コミット内容

このコミットの目的は、HTMLパーサーにおける現在の挿入モードの管理方法を変更することです。以前は、HTMLパーサーの状態遷移関数が、次の挿入モードとトークンが消費されたかどうかを返していました。しかし、ある挿入モードが別の挿入モードのルールを使用する必要がある場合、useTheRulesForというヘルパー関数を使って処理を調整する必要がありました。このuseTheRulesFor関数は、関数の等価性を比較するという、将来的に動作しなくなる可能性のあるメカニズムに依存していました。

このコミットでは、パーサー構造体に現在の挿入モードを格納するための新しいフィールドを追加することで、この問題を解決します。これにより、useTheRulesFor関数が不要になり、ある挿入モード関数が別の挿入モード関数を直接呼び出すことが可能になります。挿入モードは、必要に応じてのみ変更されるようになります。これは、以前提案された変更（CL 5372078）の代替案として提出されました。

変更の背景

HTML5の仕様は、ウェブブラウザがHTMLドキュメントをどのように解析し、DOMツリーを構築するかを厳密に定義しています。この解析プロセスは、複雑な状態機械として記述されており、その中心的な概念の一つが「挿入モード (insertion mode)」です。挿入モードは、パーサーが現在どのHTML要素のコンテキストで動作しているかを示し、次にどのトークンをどのように処理するかを決定します。

Go言語のHTMLパーサーは、このHTML5仕様に準拠して実装されています。コミット前の設計では、各挿入モードに対応する関数が、処理後に次の挿入モードを返していました。しかし、HTML5の仕様には、「現在の挿入モードのルールを使用してトークンを再処理する」といった、ある挿入モードが別の挿入モードのロジックを一時的に借用するケースが存在します。これを実装するために、useTheRulesForというヘルパー関数が導入されていました。

このuseTheRulesFor関数は、引数として渡された関数（挿入モード）が、実際に状態遷移を引き起こしたかどうかを判断するために、関数の等価性比較を行っていました。Go言語において、関数はファーストクラスオブジェクトであり、変数に代入したり、引数として渡したりすることができますが、関数の等価性比較（特にクロージャや動的に生成された関数など、アドレスが異なる可能性がある場合）は、常に信頼できるとは限りません。このコミットの作者は、この比較が「動作しなくなる」と認識しており、より堅牢なメカニズムが必要であると判断しました。

この変更の背景には、HTMLパーサーの正確性と堅牢性を向上させ、将来的なGo言語の変更（例えば、関数ポインタの比較に関する挙動の変更）にも対応できるようにするという意図があります。

前提知識の解説

このコミットを理解するためには、以下の概念についての基本的な知識が必要です。

  1. HTML5パーシングアルゴリズム:

    • HTML5の仕様は、ブラウザがHTMLドキュメントを解析するための詳細なアルゴリズムを定義しています。これは、トークン化フェーズとツリー構築フェーズの2つの主要なフェーズに分かれます。
    • トークン化 (Tokenization): 入力ストリーム（HTML文字列）を、タグ、属性、テキストなどの意味のある単位（トークン）に分解するプロセスです。
    • ツリー構築 (Tree Construction): トークナイザーから受け取ったトークンに基づいて、DOMツリーを構築するプロセスです。このフェーズが、本コミットの主題である「挿入モード」に深く関連しています。

  2. 挿入モード (Insertion Mode):

    • HTML5のツリー構築アルゴリズムの中心的な概念です。パーサーが現在どのHTML要素のコンテキストで動作しているかを示す状態です。
    • 例えば、<head>タグの中では「in head」モード、<body>タグの中では「in body」モードなど、様々な挿入モードが存在します。
    • 各挿入モードは、特定のトークン（開始タグ、終了タグ、テキストなど）が与えられたときに、DOMツリーにどのように影響を与えるか（要素の追加、削除、属性の変更など）を決定する一連のルールを持っています。
    • パーサーは、これらのルールに基づいて、次の挿入モードに遷移することもあります。

  3. Go言語の関数とメソッド:

    • Go言語では、関数はファーストクラスオブジェクトであり、変数に代入したり、関数の引数として渡したり、関数の戻り値として返したりすることができます。
    • メソッドは、特定の型に関連付けられた関数です。レシーバー（p *parserなど）を通じて、その型のデータにアクセスできます。
    • このコミットでは、insertionModeが関数型として定義されており、パーサーの状態遷移ロジックをカプセル化しています。

  4. Go言語の構造体 (Struct):

    • 関連するフィールドをまとめるためのユーザー定義型です。このコミットでは、parser構造体に新しいフィールドが追加され、パーサーの状態を保持する役割を強化しています。

  5. panicとrecover:

    • Go言語のエラーハンドリングメカニズムの一つです。panicはプログラムの異常終了を引き起こしますが、recoverを使ってパニックから回復し、プログラムのクラッシュを防ぐことができます。このコミットのコードには、不正なパーサー状態を検出した場合にpanicを発生させる箇所があります。

技術的詳細

このコミットの技術的な核心は、HTMLパーサーの状態管理モデルの変更にあります。

変更前のモデル

変更前は、insertionMode型は以下のように定義されていました。

type insertionMode func(*parser) (insertionMode, bool)

これは、*parser型のポインタを引数に取り、次のinsertionMode関数と、トークンが消費されたかどうかを示すbool値を返す関数型でした。

このモデルでは、ある挿入モードが別の挿入モードのルールを一時的に借用したい場合（HTML5仕様の「using the rules for」セクションに対応）、useTheRulesForというヘルパー関数が使用されていました。

func useTheRulesFor(p *parser, actual, delegate insertionMode) (insertionMode, bool) {
    im, consumed := delegate(p)
    if p.originalIM == delegate { // ここで関数の等価性比較が行われる
        p.originalIM = actual
    }
    if im != delegate { // ここでも関数の等価性比較が行われる
        return im, consumed
    }
    return actual, consumed
}

この関数は、delegate関数（借用したい挿入モードのルール）を実行し、その結果に基づいて次の挿入モードを決定していました。問題は、delegate関数が実際に状態遷移を引き起こしたかどうかを判断するために、im != delegateのような関数の等価性比較に依存していた点です。Go言語の関数ポインタの比較は、コンパイル時定数である関数リテラルに対しては機能しますが、動的に生成されたクロージャや、異なるパッケージからインポートされた関数など、アドレスが異なる可能性がある場合には、意図しない結果を招く可能性があります。コミットメッセージにある「which is going to stop working」という記述は、Go言語の将来のバージョンでこの挙動が変更される可能性、あるいは現在の実装でも特定の条件下で問題が発生する可能性を示唆しています。

変更後のモデル

このコミットでは、この問題を解決するために、以下の変更が行われました。

  1. parser構造体へのimフィールドの追加: parser構造体にim insertionModeという新しいフィールドが追加されました。このフィールドが、パーサーの現在の挿入モードを直接保持します。

    type parser struct {
    // ... 既存のフィールド ...
    // im is the current insertion mode.
    im insertionMode
    // originalIM is the insertion mode to go back to after completing a text
    // or inTableText insertion mode.
    originalIM insertionMode
}

  2. insertionMode関数のシグネチャ変更: insertionMode型は以下のように変更されました。

    type insertionMode func(*parser) bool

    これにより、挿入モード関数は、トークンが消費されたかどうかを示すbool値のみを返すようになります。次の挿入モードへの遷移は、関数内でp.im = nextIMのように、parser構造体のimフィールドを直接更新することで行われます。

  3. useTheRulesFor関数の削除: 関数の等価性比較に依存していたuseTheRulesFor関数は完全に削除されました。

  4. 挿入モード間の直接呼び出し: useTheRulesForの代わりに、ある挿入モードが別の挿入モードのルールを借用したい場合、その挿入モード関数を直接呼び出すようになります。例えば、return useTheRulesFor(p, beforeHeadIM, inBodyIM)のような呼び出しは、return inBodyIM(p)のように変更されます。これにより、関数の等価性比較が不要になり、コードがより直接的で理解しやすくなります。

  5. setOriginalIMとresetInsertionModeの変更: これらの関数も、insertionModeを引数として受け取ったり、戻り値として返したりする代わりに、p.imフィールドを直接操作するように変更されました。

    • setOriginalIM(im insertionMode) -> setOriginalIM(): p.originalIM = p.imのように、現在のp.imをoriginalIMに保存します。
    • resetInsertionMode() insertionMode -> resetInsertionMode(): 適切な挿入モードを計算した後、return inSelectIMの代わりにp.im = inSelectIM; returnのようにp.imを直接設定します。

利点

  • 堅牢性の向上: 関数の等価性比較という潜在的に不安定なメカニズムが排除されました。
  • コードの簡素化: useTheRulesForヘルパー関数が不要になり、挿入モード間のロジックの共有がより直接的な関数呼び出しによって行われるようになりました。
  • 状態管理の一元化: 現在の挿入モードがparser構造体内に明示的に保持されることで、パーサーの状態がより明確に管理されるようになりました。

この変更は、HTML5パーシングアルゴリズムの複雑さをGo言語の型システムと構造体の機能を使って、より効率的かつ堅牢に表現するための重要なリファクタリングと言えます。

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

変更は主にsrc/pkg/html/parse.goファイルに集中しています。

  1. parser構造体へのフィールド追加:

    --- a/src/pkg/html/parse.go
+++ b/src/pkg/html/parse.go
@@ -29,6 +29,8 @@ type parser struct {
 	// Other parsing state flags (section 11.2.3.5).
 	scripting, framesetOK bool
+	// im is the current insertion mode.
+	im insertionMode
 	// originalIM is the insertion mode to go back to after completing a text
 	// or inTableText insertion mode.
 	originalIM insertionMode

  2. insertionMode型のシグネチャ変更:

    --- a/src/pkg/html/parse.go
+++ b/src/pkg/html/parse.go
@@ -265,37 +267,22 @@ func (p *parser) acknowledgeSelfClosingTag() {
 
 // An insertion mode (section 11.2.3.1) is the state transition function from
 // a particular state in the HTML5 parser's state machine. It updates the
-// parser's fields depending on parser.token (where ErrorToken means EOF). In
-// addition to returning the next insertionMode state, it also returns whether
-// the token was consumed.
-type insertionMode func(*parser) (insertionMode, bool)
-// useTheRulesFor runs the delegate insertionMode over p, returning the actual
-// insertionMode unless the delegate caused a state transition.
-// Section 11.2.3.1, "using the rules for".
-func useTheRulesFor(p *parser, actual, delegate insertionMode) (insertionMode, bool) {
-	im, consumed := delegate(p)
-	if p.originalIM == delegate {
-		p.originalIM = actual
-	}
-	if im != delegate {
-		return im, consumed
-	}
-	return actual, consumed
-}
+// parser's fields depending on parser.tok (where ErrorToken means EOF).
+// It returns whether the token was consumed.
+type insertionMode func(*parser) bool

    （useTheRulesFor関数は完全に削除されています。）

  3. setOriginalIM関数の変更:

    --- a/src/pkg/html/parse.go
+++ b/src/pkg/html/parse.go
@@ -269,10 +256,10 @@ type insertionMode func(*parser) (insertionMode, bool)
 // setOriginalIM sets the insertion mode to return to after completing a text or
 // inTableText insertion mode.
 // Section 11.2.3.1, "using the rules for".
-func (p *parser) setOriginalIM(im insertionMode) {
+func (p *parser) setOriginalIM() {
 	if p.originalIM != nil {
 		panic("html: bad parser state: originalIM was set twice")
 	}
-	p.originalIM = im
+	p.originalIM = p.im
 }

  4. resetInsertionMode関数の変更:

    --- a/src/pkg/html/parse.go
+++ b/src/pkg/html/parse.go
@@ -281,30 +268,32 @@ func (p *parser) resetInsertionMode() insertionMode {
 	t\t\treturn inSelectIM
+\t\t\tp.im = inSelectIM
 	case "td", "th":
-\t\t\treturn inCellIM
+\t\t\tp.im = inCellIM
 	case "tr":
-\t\t\treturn inRowIM
+\t\t\tp.im = inRowIM
 	case "tbody", "thead", "tfoot":
-\t\t\treturn inTableBodyIM
+\t\t\tp.im = inTableBodyIM
 	case "caption":
-\t\t\t// TODO: return inCaptionIM
+\t\t\t// TODO: p.im = inCaptionIM
 	case "colgroup":
-\t\t\treturn inColumnGroupIM
+\t\t\tp.im = inColumnGroupIM
 	case "table":
-\t\t\treturn inTableIM
+\t\t\tp.im = inTableIM
 	case "head":
-\t\t\treturn inBodyIM
+\t\t\tp.im = inBodyIM
 	case "body":
-\t\t\treturn inBodyIM
+\t\t\tp.im = inBodyIM
 	case "frameset":
-\t\t\treturn inFramesetIM
+\t\t\tp.im = inFramesetIM
 	case "html":
-\t\t\treturn beforeHeadIM
+\t\t\tp.im = beforeHeadIM
+\t\tdefault:\
+\t\t\tcontinue
 	}
+\t\treturn
 	}\
-\treturn inBodyIM
+\tp.im = inBodyIM
 }

  5. 各挿入モード関数のシグネチャとロジックの変更: initialIM, beforeHTMLIM, inHeadIM, inBodyIMなど、すべてのinsertionMode型の関数が、func(*parser) (insertionMode, bool)からfunc(*parser) boolに変更され、次の挿入モードをp.imに直接設定するようになりました。また、useTheRulesForの呼び出しは、対応する挿入モード関数への直接呼び出しに置き換えられました。

    例: initialIM

    --- a/src/pkg/html/parse.go
+++ b/src/pkg/html/parse.go
@@ -303,20 +290,21 @@ func (p *parser) resetInsertionMode() insertionMode {
 }
 
 // Section 11.2.5.4.1.
-func initialIM(p *parser) (insertionMode, bool) {
+func initialIM(p *parser) bool {
 	switch p.tok.Type {
 	case CommentToken:
 		p.doc.Add(&Node{
 			Type: CommentNode,
 			Data: p.tok.Data,
 		})
-\t\treturn initialIM, true
+\t\treturn true
 	case DoctypeToken:
 		p.doc.Add(&Node{
 			Type: DoctypeNode,
 			Data: p.tok.Data,
 		})
-\t\treturn beforeHTMLIM, true
+\t\tp.im = beforeHTMLIM
+\t\treturn true
 	}
 	// TODO: set "quirks mode"? It's defined in the DOM spec instead of HTML5 proper,
 	// and so switching on "quirks mode" might belong in a different package.
-\treturn beforeHTMLIM, false
+\tp.im = beforeHTMLIM
+\treturn false
 }

    例: beforeHeadIMでのuseTheRulesForの置き換え

    --- a/src/pkg/html/parse.go
+++ b/src/pkg/html/parse.go
@@ -397,7 +391,7 @@ func beforeHeadIM(p *parser) (insertionMode, bool) {
 	\t\tadd = true
 	\t\tattr = p.tok.Attr
 	\tcase "html":
-\t\t\treturn useTheRulesFor(p, beforeHeadIM, inBodyIM)
+\t\t\treturn inBodyIM(p)
 	\tdefault:
 	\t\timplied = true
 	\t}

  6. Parse関数の呼び出しロジックの変更: パーサーの初期化とループ処理が、新しいp.imフィールドを使用するように変更されました。

    --- a/src/pkg/html/parse.go
+++ b/src/pkg/html/parse.go
@@ -1323,9 +1347,10 @@ func Parse(r io.Reader) (*Node, error) {
 		},
 		scripting:  true,
 		framesetOK: true,
+		im:         initialIM,
 	}
 	// Iterate until EOF. Any other error will cause an early return.
-\tim, consumed := initialIM, true
+\tconsumed := true
 	for {
 		if consumed {
 			if err := p.read(); err != nil {
@@ -1335,11 +1360,11 @@ func Parse(r io.Reader) (*Node, error) {
 				return nil, err
 			}
 		}
-\t\tim, consumed = im(p)
+\t\tconsumed = p.im(p)
 	}
 	// Loop until the final token (the ErrorToken signifying EOF) is consumed.
 	for {
-\t\tif im, consumed = im(p); consumed {\
+\t\tif consumed = p.im(p); consumed {\
 			break
 		}
 	}

コアとなるコードの解説

このコミットの核心は、HTMLパーサーの「挿入モード」の管理方法を、関数の戻り値からパーサー構造体自身のフィールドへと移行した点にあります。

parser構造体へのimフィールドの追加

type parser struct {
    // ...
    im insertionMode // 現在の挿入モードを保持する新しいフィールド
    originalIM insertionMode
}

このimフィールドが、パーサーが現在どの挿入モードで動作しているかを常に示します。これにより、パーサーの状態がより明確になり、外部から（または他の挿入モード関数から）現在のモードにアクセスしやすくなります。

insertionMode関数のシグネチャ変更とuseTheRulesForの削除

変更前: type insertionMode func(*parser) (insertionMode, bool) 変更後: type insertionMode func(*parser) bool

以前は、各挿入モード関数は次の挿入モードを返していました。しかし、この設計では、ある挿入モードが別の挿入モードのルールを一時的に適用したい場合に、useTheRulesForというヘルパー関数が必要でした。このヘルパー関数は、関数の等価性比較に依存しており、これが問題の原因でした。

新しいシグネチャでは、挿入モード関数はトークンが消費されたかどうか（bool）のみを返します。次の挿入モードへの遷移は、関数内でp.im = nextModeのように、parser構造体のimフィールドを直接更新することで行われます。

例えば、beforeHTMLIM関数では、HTML要素が暗黙的に作成された後、次の挿入モードをbeforeHeadIMに設定するために、以前はreturn beforeHeadIM, falseとしていましたが、変更後は以下のようになります。

func beforeHTMLIM(p *parser) bool {
    // ...
    p.addElement("html", nil)
    p.im = beforeHeadIM // ここで直接次の挿入モードを設定
    return false
}

また、useTheRulesForが削除されたことで、例えばbeforeHeadIM内でinBodyIMのルールを適用したい場合、以前はreturn useTheRulesFor(p, beforeHeadIM, inBodyIM)としていた箇所が、直接return inBodyIM(p)と呼び出す形に変わりました。

func beforeHeadIM(p *parser) bool {
    // ...
    case "html":
        return inBodyIM(p) // inBodyIMのルールを直接適用
    // ...
}

これにより、コードのフローがより直接的になり、関数の等価性比較という潜在的な問題が解消されました。

Parse関数の変更

Parse関数は、パーサーの初期化とメインループを管理します。

func Parse(r io.Reader) (*Node, error) {
    p := &parser{
        // ...
        im: initialIM, // パーサーの初期化時に最初の挿入モードを設定
    }
    consumed := true
    for {
        if consumed {
            // ... トークンを読み込む ...
        }
        consumed = p.im(p) // 現在の挿入モード関数を呼び出し、トークン消費有無を取得
    }
    // ...
}

以前は、im, consumed := initialIM, trueのようにローカル変数で現在の挿入モードを管理し、im, consumed = im(p)のようにループ内で更新していました。しかし、この変更により、p.imフィールドが現在の挿入モードを保持するため、ローカル変数は不要になり、consumed = p.im(p)のように、パーサーのimフィールドを通じて現在の挿入モード関数を呼び出すようになりました。

この一連の変更により、HTMLパーサーの状態管理がより一貫性のある、堅牢なものとなり、HTML5仕様の複雑なルールをより正確に実装できるようになりました。

関連リンク

参考にした情報源リンク

  • HTML5仕様: 上記の関連リンクに記載されているHTML5の公式仕様。
  • Go言語のドキュメント: Go言語の関数、構造体、メソッドに関する一般的な情報。
  • Go言語のhtmlパッケージのソースコード: コミット前後のsrc/pkg/html/parse.goのコード。
  • Go言語のIssueトラッカーやメーリングリスト: 過去の議論や関連する変更提案（CL 5372078など）に関する情報。
  • Web検索: 「HTML5 parsing insertion mode」、「Go html parser」などのキーワードで、HTMLパーシングの概念やGo言語での実装に関する一般的な情報を収集しました。