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

このコミットは、Goコンパイラの初期化ループ検出に関するバグ修正です。具体的には、グローバル変数の初期化順序を決定する際に、変数と関数の相互依存関係が複雑に絡み合った場合に、コンパイラが初期化ループを正しく検出できない問題を解決します。

コミット

commit 66c8935f732db28632b75aea456c682487febf15
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Thu Aug 29 10:16:09 2013 +0200

    cmd/gc: fix detection of initialization loop.
    
    The compiler computes initialization order by finding
    a spanning tree between a package's global variables.
    But it does so by walking both variables and functions
    and stops detecting cycles between variables when they
    mix with a cycle of mutually recursive functions.
    
    Fixes #4847.
    
    R=golang-dev, daniel.morsing, rsc
    CC=golang-dev
    https://golang.org/cl/9663047

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

https://github.com/golang/go/commit/66c8935f732db28632b75aea456c682487febf15

元コミット内容

cmd/gc: fix detection of initialization loop.

コンパイラは、パッケージのグローバル変数間のスパニングツリーを見つけることで初期化順序を計算します。しかし、変数と関数の両方をウォークし、相互再帰する関数のサイクルと混ざると、変数間のサイクル検出を停止してしまいます。

Issue #4847 を修正します。

変更の背景

Go言語では、パッケージレベルの変数（グローバル変数）は、その初期化順序が重要になります。特に、ある変数の初期化が別の変数の値に依存する場合、コンパイラはそれらの依存関係を解決し、正しい順序で初期化を実行する必要があります。もし、変数間に循環参照（初期化ループ）が存在する場合、それはプログラムの実行時エラーや未定義の動作を引き起こす可能性があるため、コンパイラはこれを検出し、エラーとして報告する必要があります。

このコミットが修正する問題は、Goコンパイラが初期化ループを検出するロジックに欠陥があったことです。具体的には、グローバル変数の初期化順序を決定する際に、コンパイラは依存関係グラフを構築し、その中にサイクル（ループ）がないかをチェックします。しかし、このグラフには変数だけでなく、関数も含まれていました。問題は、変数間の初期化ループが、相互に再帰呼び出しを行う関数群のサイクルと混ざり合った場合に発生しました。コンパイラは、関数間の相互再帰は許容される（これはGoの設計の一部であり、例えばinit()関数や通常の関数呼び出しで発生しうる）と判断し、その結果、変数を含む初期化ループを見逃してしまうことがありました。

Issue #4847は、この特定のバグを報告したもので、コンパイラが検出できなかった初期化ループの具体的なケースを示していました。このバグは、開発者が意図しない循環依存関係を持つコードを記述してしまった場合に、コンパイラがそれを警告せず、実行時に問題を引き起こす可能性がありました。

前提知識の解説

• Go言語の初期化順序: Go言語では、パッケージレベルの変数は宣言順に初期化されますが、依存関係がある場合はその依存関係が優先されます。init()関数も特別な初期化関数として機能します。コンパイラは、これらの依存関係を解決し、正しい初期化順序を決定します。
• 初期化ループ (Initialization Loop): ある変数の初期化が別の変数に依存し、その別の変数が最初の変数に依存するといった循環参照のことです。例えば、var a = b + 1 と var b = a + 1 のようなケースです。このようなループは、どちらの変数も初期化できないため、コンパイラによってエラーとして検出されるべきです。
• スパニングツリー (Spanning Tree): グラフ理論における概念で、グラフのすべての頂点を含む木のことです。コンパイラが初期化順序を計算する際に、変数間の依存関係をグラフとして表現し、そのスパニングツリーを見つけることで、初期化の順序を決定しようとします。
• 相互再帰関数 (Mutually Recursive Functions): 2つ以上の関数が互いに呼び出し合う関係にあることです。例えば、func f1() { f2() } と func f2() { f1() } のようなケースです。Go言語では、このような関数間の相互再帰は通常許容されます。
• AST (Abstract Syntax Tree): ソースコードの抽象的な構文構造を木構造で表現したものです。コンパイラはソースコードをASTに変換し、そのASTを解析して様々な処理を行います。このコミットでは、init1関数がASTをウォークして初期化順序を決定しています。
• Node構造体: Goコンパイラの内部で、ASTの各ノード（変数、関数、式など）を表すために使用される構造体です。n->classはノードの種類（PFUNCは関数、それ以外は変数など）を示し、n->initorderは初期化の状態（InitDone、InitPendingなど）を示します。
• NodeList構造体: Nodeのリストを表現するための構造体で、依存関係の追跡やループ検出に使用されます。

技術的詳細

このコミットの核心は、src/cmd/gc/sinit.c ファイル内の init1 関数における初期化ループ検出ロジックの変更です。

元の実装では、init1 関数がASTを深さ優先探索（DFS）のようにウォークし、各ノード（変数または関数）の初期化状態を追跡していました。n->initorder == InitPending の状態は、現在処理中のノードが既に訪問済みであり、かつまだ初期化が完了していないことを示します。これは、依存関係グラフにおいてサイクルが存在する可能性を示唆します。

元のコードでは、InitPending のノードに遭遇した際に、そのノードが PFUNC (関数) であれば、すぐに return していました。これは、「関数間の相互再帰は許容されるため、関数がループに含まれていてもエラーではない」という前提に基づいています。しかし、このロジックには問題がありました。変数と関数が混在するサイクル、特に変数を含むサイクルが関数間の相互再帰の中に隠れてしまう場合、コンパイラはそれを初期化ループとして検出できませんでした。

修正後のコードでは、InitPending のノードに遭遇した場合でも、すぐに return せずに、より詳細なチェックを行うようになりました。

1. n->class != PFUNC のチェック: まず、現在のノード n が関数 (PFUNC) でない場合（つまり変数である場合）、それは変数を含む初期化ループの可能性が高いと判断し、foundinitloop ラベルにジャンプします。
2. initlist の走査: もし n が関数 (PFUNC) であったとしても、initlist (現在処理中の依存関係パスを記録しているリスト) を走査し、その中に PFUNC でないノード（つまり変数）が含まれていないかをチェックします。もし変数が見つかった場合、その変数 l->n が初期化ループの一部であると判断し、foundinitloop ラベルにジャンプします。
3. 関数のみのループ: 上記のチェックを通過し、initlist 内のすべてのノードが関数 (PFUNC) であった場合、それは関数のみの相互再帰ループであると判断し、エラーではないため return します。
4. foundinitloop 処理: foundinitloop に到達した場合、変数を含む初期化ループが検出されたと判断されます。このセクションでは、ループに関与しているノード（変数）を特定し、そのループパスを詳細に表示して、コンパイルエラーとして報告します。特に、nv という新しい変数を導入し、ループの起点となる変数を正確に特定できるようにしています。また、ループパスの表示方法も改善され、より分かりやすく依存関係が示されるようになりました。

この変更により、コンパイラは変数と関数が混在する複雑な依存関係グラフにおいても、変数を含む初期化ループを正確に識別し、適切なエラーメッセージを出力できるようになりました。

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

src/cmd/gc/sinit.c ファイルの init1 関数が主な変更箇所です。

--- a/src/cmd/gc/sinit.c
+++ b/src/cmd/gc/sinit.c
@@ -61,9 +64,29 @@ init1(Node *n, NodeList **out)
  	if(n->initorder == InitDone)
  		return;
  	if(n->initorder == InitPending) {
- 		if(n->class == PFUNC)
- 			return;
+ 		// Since mutually recursive sets of functions are allowed,
+ 		// we don't necessarily raise an error if n depends on a node
+ 		// which is already waiting for its dependencies to be visited.
+ 		//
+ 		// initlist contains a cycle of identifiers referring to each other.
+ 		// If this cycle contains a variable, then this variable refers to itself.
+ 		// Conversely, if there exists an initialization cycle involving
+ 		// a variable in the program, the tree walk will reach a cycle
+ 		// involving that variable.
+ 		if(n->class != PFUNC) {
+ 			nv = n;
+ 			goto foundinitloop;
+ 		}
+ 		for(l=initlist; l->n!=n; l=l->next) {
+ 			if(l->n->class != PFUNC) {
+ 				nv = l->n;
+ 				goto foundinitloop;
+ 			}
+ 		}
+ 		// The loop involves only functions, ok.
+ 		return;
+
+ 	foundinitloop:
  		// if there have already been errors printed,
  		// those errors probably confused us and
  		// there might not be a loop.  let the user
@@ -72,17 +95,26 @@ init1(Node *n, NodeList **out)
  		if(nerrors > 0)
  			errorexit();
 
- 		print("%L: initialization loop:\n", n->lineno);
- 		for(l=initlist;; l=l->next) {
- 			if(l->next == nil)
- 				break;
- 			l->next->end = l;
- 		}
+ 		// There is a loop involving nv. We know about
+ 		// n and initlist = n1 <- ... <- nv <- ... <- n <- ...
+ 		print("%L: initialization loop:\n", nv->lineno);
+ 		// Build back pointers in initlist.
+ 		for(l=initlist; l; l=l->next)
+ 			if(l->next != nil)
+ 				l->next->end = l;
+ 		// Print nv -> ... -> n1 -> n.
+ 		for(l=initlist; l->n!=nv; l=l->next);
  		for(; l; l=l->end)
  			print("\t%L %S refers to\n", l->n->lineno, l->n->sym);
- 		print("\t%L %S\n", n->lineno, n->sym);
+ 		// Print n -> ... -> nv.
+ 		for(l=initlist; l->n!=n; l=l->next);
+ 		for(; l->n != nv; l=l->end)
+ 			print("\t%L %S refers to\n", l->n->lineno, l->n->sym);
+ 		print("\t%L %S\n", nv->lineno, nv->sym);
  		errorexit();
  	}
+
+ 	// reached a new unvisited node.
  	n->initorder = InitPending;
  	l = malloc(sizeof *l);
  	if(l == nil) {

また、test/fixedbugs/issue4847.go には、このバグを再現し、修正が正しく機能することを確認するための新しいテストケースが追加されています。

// errorcheck

// Copyright 2013 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.

// Issue 4847: initialization loop is not detected.

package p

type (
	E int
	S int
)

type matcher func(s *S) E

func matchList(s *S) E { return matcher(matchAnyFn)(s) }

var foo = matcher(matchList)

var matchAny = matcher(matchList) // ERROR "initialization loop"

func matchAnyFn(s *S) (err E) { return matchAny(s) }

このテストケースでは、matchAny 変数が matchList 関数を介して matchAnyFn 関数に依存し、matchAnyFn 関数が再び matchAny 変数に依存するという循環参照を作成しています。この循環参照には変数 matchAny が含まれているため、コンパイラはこれを初期化ループとして検出し、エラーを報告する必要があります。

コアとなるコードの解説

init1 関数は、Goコンパイラの初期化順序決定ロジックの中核をなす関数です。この関数は、ASTノードを再帰的にウォークし、依存関係を解決しながら初期化順序を決定します。

変更のポイントは、n->initorder == InitPending のブロックです。

• nv = n; goto foundinitloop;:
  • もし現在処理中のノード n が関数 (PFUNC) ではなく、かつ InitPending 状態であれば、それは変数であり、既に訪問済みのパス上に存在するため、初期化ループの起点である可能性が高いと判断されます。
  • nv に n を代入し、foundinitloop ラベルにジャンプしてループ検出処理に進みます。
• for(l=initlist; l->n!=n; l=l->next) { ... }:
  • もし n が関数 (PFUNC) であった場合でも、initlist (現在の依存関係パス) を逆順に辿り、n に到達するまでの間に変数 (l->n->class != PFUNC) が含まれていないかをチェックします。
  • もし変数が見つかった場合、その変数 l->n が初期化ループの起点であると判断し、nv にその変数を代入して foundinitloop にジャンプします。
  • この部分が、関数間の相互再帰の中に隠れた変数を含む初期化ループを検出するための重要なロジックです。
• // The loop involves only functions, ok. return;:
  • 上記のチェックをすべて通過し、initlist 内のすべてのノードが関数であった場合、それは関数のみの相互再帰ループであり、Go言語では許容されるため、エラーとはせずに return します。
• foundinitloop: ラベル以降の処理:
  • このブロックは、初期化ループが検出された場合に実行されます。
  • print("%L: initialization loop:\n", nv->lineno); で、ループの起点となった変数 nv の行番号と「initialization loop:」というメッセージを出力します。
  • for(l=initlist; l; l=l->next) if(l->next != nil) l->next->end = l; で、initlist の各ノードに逆方向のポインタ (end) を設定します。これは、ループパスを逆順に辿って表示するために使用されます。
  • for(l=initlist; l->n!=nv; l=l->next); で、initlist を nv が含まれる位置まで進めます。
  • for(; l; l=l->end) print("\t%L %S refers to\n", l->n->lineno, l->n->sym); で、nv から n までのループパスを逆順に表示します。
  • for(l=initlist; l->n!=n; l=l=l->next); で、initlist を n が含まれる位置まで進めます。
  • for(; l->n != nv; l=l->end) print("\t%L %S refers to\n", l->n->lineno, l->n->sym); で、n から nv までのループパスを逆順に表示します。
  • print("\t%L %S\n", nv->lineno, nv->sym); で、ループの終点（起点と同じ）である nv を表示します。
  • errorexit(); で、コンパイルを終了し、エラーを報告します。

この修正により、Goコンパイラはより堅牢な初期化ループ検出メカニズムを持つことになり、開発者が意図しない循環依存関係を早期に発見できるようになりました。

関連リンク

• Go言語の初期化順序に関する公式ドキュメントやブログ記事（Goのバージョンによって詳細が異なる場合がありますが、基本的な概念は共通です）
• Goコンパイラのソースコード（特に src/cmd/gc ディレクトリ）

参考にした情報源リンク

• Go言語の公式ドキュメント
• Go言語のソースコードリポジトリ (golang/go on GitHub)
• Go言語のIssueトラッカー (Issue #4847) - 今回の検索では直接見つかりませんでしたが、通常はこのようなIssueが詳細な議論の場となります。