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

このコミットは、Go言語のドキュメンテーションツールである go/doc パッケージにおける、再帰的な埋め込み型（recursive embedded types）の処理に関するバグ修正です。具体的には、型が自身を（直接的または間接的に）埋め込むような構造を持つ場合に、メソッドセットの収集処理が無限ループに陥る問題を解決しています。

コミット

commit e7bd71c83af94143b2a218c362c081c058e84a70
Author: Gary Burd <gary@beagledreams.com>
Date:   Wed Feb 8 16:54:48 2012 -0800

    go/doc: Handle recursive embedded types.
    
    R=golang-dev, gri
    CC=golang-dev
    https://golang.org/cl/5645053

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

https://github.com/golang/go/commit/e7bd71c83af94143b2a218c362c081c058e84a70

元コミット内容

go/doc: Handle recursive embedded types.

このコミットは、go/doc パッケージが再帰的に埋め込まれた型を正しく処理できるようにするためのものです。

Go言語では、構造体（struct）内に他の構造体を匿名フィールドとして埋め込むことができます。これにより、埋め込まれた構造体のメソッドが外側の構造体のメソッドセットに「昇格」され、あたかも外側の構造体のメソッドであるかのように呼び出すことができます。これはGoの強力な機能の一つですが、型が自身を再帰的に埋め込むようなケース（例: type A struct { *A } や type A struct { *B }; type B struct { *A }）が発生した場合、go/doc パッケージがメソッドセットを収集する際に無限ループに陥る可能性がありました。

この無限ループは、ドキュメンテーション生成プロセスがスタックオーバーフローやリソース枯渇を引き起こし、正常に完了しない原因となります。このコミットは、このような再帰的な構造を検出して適切に処理し、無限ループを回避することを目的としています。

前提知識の解説

Go言語の埋め込み型 (Embedded Types)

Go言語の構造体は、他の構造体やインターフェースを匿名フィールドとして埋め込むことができます。これにより、埋め込まれた型のフィールドやメソッドが、外側の構造体のフィールドやメソッドであるかのように直接アクセスできるようになります。これは、継承に似たコードの再利用メカニズムとして機能しますが、Goの設計思想に沿った「コンポジション（合成）」によるものです。

例:

type Base struct {
    Name string
}

func (b *Base) Greet() {
    fmt.Println("Hello, " + b.Name)
}

type Person struct {
    Base // Base型を埋め込み
    Age  int
}

func main() {
    p := Person{Base: Base{Name: "Alice"}, Age: 30}
    p.Greet() // Person型からBase型のGreetメソッドを呼び出し
}

メソッドセット (Method Sets)

Go言語では、各型が持つメソッドの集合を「メソッドセット」と呼びます。メソッドセットは、インターフェースの実装や、特定の型がどのメソッドを呼び出せるかを決定する上で重要です。ポインタ型と非ポインタ型ではメソッドセットのルールが異なります。

非ポインタ型 T のメソッドセット: レシーバが T である全てのメソッド。
ポインタ型 *T のメソッドセット: レシーバが T または *T である全てのメソッド。

埋め込み型の場合、埋め込まれた型のメソッドは、外側の構造体のメソッドセットに昇格されます。この昇格ルールは、埋め込みがポインタ型 (*EmbeddedType) か非ポインタ型 (EmbeddedType) かによっても異なります。

修正は以下の通りです。

visited マップの導入: collectEmbeddedMethods 関数のシグネチャに visited map[*namedType]bool という新しい引数が追加されました。このマップは、現在処理中の再帰呼び出しパスで既に訪問した namedType のポインタを記録するために使用されます。
訪問済みチェック:
- 関数が呼び出された直後に、現在の typ を visited マップに追加します (visited[typ] = true)。
- 再帰呼び出しを行う前に、埋め込まれた型 (embedded) が visited マップに存在しないかを確認します (if !visited[embedded])。存在しない場合のみ、再帰呼び出しを実行します。これにより、循環参照が検出された場合にそれ以上深く探索するのを防ぎます。
訪問済みマークの解除: 関数の処理が終了する直前に、現在の typ を visited マップから削除します (delete(visited, typ))。これは、同じ型が異なるパスを通じて到達される可能性がある場合に、その型が別の探索パスで再び処理されることを許可するためです。これにより、正確なメソッドセットの収集を保証しつつ、無限ループを回避します。
初期呼び出しの変更: computeMethodSets 関数内で collectEmbeddedMethods を最初に呼び出す際に、新しい空の visited マップを渡すように変更されました (make(map[*namedType]bool))。これにより、各トップレベルの型に対するメソッドセット収集が独立して行われ、それぞれの探索パスで新しい訪問履歴が管理されます。

このアプローチは、グラフ探索アルゴリズムにおける深さ優先探索（DFS）でサイクルを検出・回避する一般的な手法である「訪問済みセット」の利用に相当します。

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

src/pkg/go/doc/reader.go ファイルの collectEmbeddedMethods 関数と、その呼び出し元である computeMethodSets 関数が変更されています。

--- a/src/pkg/go/doc/reader.go
+++ b/src/pkg/go/doc/reader.go
@@ -543,7 +543,8 @@ func customizeRecv(f *Func, recvTypeName string, embeddedIsPtr bool, level int)\
 
 // collectEmbeddedMethods collects the embedded methods of typ in mset.
 //
-func (r *reader) collectEmbeddedMethods(mset methodSet, typ *namedType, recvTypeName string, embeddedIsPtr bool, level int) {
+func (r *reader) collectEmbeddedMethods(mset methodSet, typ *namedType, recvTypeName string, embeddedIsPtr bool, level int, visited map[*namedType]bool) {
+\tvisited[typ] = true
 \tfor embedded, isPtr := range typ.embedded {
 \t\t// Once an embedded type is embedded as a pointer type
 \t\t// all embedded types in those types are treated like
@@ -557,8 +558,11 @@ func (r *reader) collectEmbeddedMethods(mset methodSet, typ *namedType, recvType
 \t\t\t\tmset.add(customizeRecv(m, recvTypeName, thisEmbeddedIsPtr, level))\
 \t\t\t}\
 \t\t}\
-\t\tr.collectEmbeddedMethods(mset, embedded, recvTypeName, thisEmbeddedIsPtr, level+1)\
+\t\tif !visited[embedded] {\
+\t\t\tr.collectEmbeddedMethods(mset, embedded, recvTypeName, thisEmbeddedIsPtr, level+1, visited)\
+\t\t}\
 \t}\
+\tdelete(visited, typ)\
 }\
 
 // computeMethodSets determines the actual method sets for each type encountered.\
@@ -568,7 +572,7 @@ func (r *reader) computeMethodSets() {\
 \t\t// collect embedded methods for t\
 \t\tif t.isStruct {\
 \t\t\t// struct\
-\t\t\tr.collectEmbeddedMethods(t.methods, t, t.name, false, 1)\
+\t\t\tr.collectEmbeddedMethods(t.methods, t, t.name, false, 1, make(map[*namedType]bool))\
 \t\t} else {\
 \t\t\t// interface\
 \t\t\t// TODO(gri) fix this

コアとなるコードの解説

`collectEmbeddedMethods` 関数の変更

シグネチャの変更: func (r *reader) collectEmbeddedMethods(mset methodSet, typ *namedType, recvTypeName string, embeddedIsPtr bool, level int, visited map[*namedType]bool) visited map[*namedType]bool が追加されました。これは、*namedType をキーとし、その型が現在の探索パスで訪問済みかどうかを示すブール値を値とするマップです。
visited[typ] = true: 関数が開始されるとすぐに、現在の typ（現在処理している型）を visited マップに追加し、true に設定します。これは、この型が現在の再帰呼び出しスタック上で処理中であることを示します。
if !visited[embedded]: 埋め込まれた型 embedded に対して再帰呼び出しを行う前に、visited マップで embedded が既に訪問済みでないかを確認します。
- もし !visited[embedded] が true であれば（つまり、embedded がまだ訪問されていないか、現在のパスでは訪問済みでない場合）、再帰呼び出し r.collectEmbeddedMethods(...) を実行します。
- もし visited[embedded] が true であれば（つまり、embedded が現在のパスで既に訪問済みである場合）、それは循環参照（再帰的な埋め込み）を示しているため、再帰呼び出しをスキップし、無限ループを防ぎます。
delete(visited, typ): for ループ（埋め込み型をイテレートするループ）の後に、現在の typ を visited マップから削除します。これは非常に重要です。この関数は深さ優先探索のように動作するため、ある型の探索が完了したら、その型は現在の探索パスからは「離脱」したと見なされます。これにより、異なる探索パスを通じて同じ型に到達した場合でも、その型が正しく処理されることを保証します。もしこの delete がなければ、一度訪問された型は二度と処理されなくなり、不正確なメソッドセットが生成される可能性があります。

`computeMethodSets` 関数の変更

初期呼び出しの変更: r.collectEmbeddedMethods(t.methods, t, t.name, false, 1, make(map[*namedType]bool)) computeMethodSets は、各構造体 t のメソッドセットを計算する際に collectEmbeddedMethods を呼び出します。この変更により、collectEmbeddedMethods の最初の呼び出し時に、新しい空の visited マップが作成され、渡されます。これにより、各トップレベルの型に対するメソッドセットの収集は、独立した訪問履歴を持つことになります。

これらの変更により、go/doc パッケージは再帰的な埋め込み型を持つGoコードに対しても、安定して正確なドキュメンテーションを生成できるようになりました。

参考にした情報源リンク

Go言語の公式ドキュメント (Go Programming Language Specification)
Go言語のブログ記事やチュートリアル（埋め込み型、メソッドセットに関するもの）
一般的なグラフ探索アルゴリズム（深さ優先探索、訪問済みセット）に関するコンピュータサイエンスの資料
https://golang.org/cl/5645053 (Gerrit Code Review) - このコミットの元のコードレビューページ。
https://github.com/golang/go/commit/e7bd71c83af94143b2a218c362c081c058e84a70 (GitHub Commit)

comemo

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

コミット

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

元コミット内容

変更の背景

前提知識の解説

Go言語の埋め込み型 (Embedded Types)

メソッドセット (Method Sets)

`go/doc` パッケージ

再帰 (Recursion) と無限ループ (Infinite Loop)

技術的詳細