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

このコミットは、Goコンパイラ（cmd/gc）における型チェックのループに関するバグ修正を目的としています。特に、再帰的な型定義や型エイリアスが絡む場合に、型が完全に評価される前にその定義がコピーされてしまう問題に対処しています。以前の修正（CL 4313064）が不十分であったため、その変更をロールバックし、より堅牢なメカニズムを導入しています。

コミット

• コミットハッシュ: 6363fc5aa6b3aa1ee8826582c6f7a356aa8e4201
• Author: Russ Cox rsc@golang.org
• Date: Thu Jun 7 03:06:40 2012 -0400

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

https://github.com/golang/go/commit/6363fc5aa6b3aa1ee8826582c6f7a356aa8e4201

元コミット内容

cmd/gc: fix type checking loop

CL 4313064 fixed its test case but did not address a
general enough problem:

type T1 struct { F *T2 }
type T2 T1
type T3 T2

could still end up copying the definition of T1 for T2
before T1 was done being evaluated, or T3 before T2
was done.

In order to propagate the updates correctly,
record a copy of an incomplete type for re-execution
once the type is completed. Roll back CL 4313064.

Fixes #3709.

R=ken2
CC=golang-dev, lstoakes
https://golang.org/cl/6301059

変更の背景

このコミットの背景には、Goコンパイラの型チェックにおける複雑な型定義、特に再帰的な型や型エイリアスが絡む場合の不正確な挙動がありました。具体的には、以下のような型定義の連鎖がある場合です。

type T1 struct { F *T2 }
type T2 T1
type T3 T2

このような定義において、コンパイラがT1の評価を完了する前にT2の定義をコピーしてしまったり、T2の評価が完了する前にT3の定義をコピーしてしまったりする問題が発生していました。これにより、型情報が不完全な状態で伝播され、コンパイルエラーや不正なコード生成につながる可能性がありました。

以前の変更リスト（CL 4313064）は、特定のテストケースを修正しましたが、この問題の根本的な原因である「不完全な型定義の早期コピー」という一般的な問題には対処できていませんでした。そのため、このコミットではCL 4313064の変更をロールバックし、より包括的な解決策を導入することで、この型チェックのループ問題を修正しています。この問題はGoのIssue 3709として報告されていました。

前提知識の解説

Goの型システムと型定義

Go言語は静的型付け言語であり、変数は使用前に型を宣言する必要があります。型は、その変数が保持できる値の種類と、その値に対して実行できる操作を決定します。

• 構造体 (Struct): 複数のフィールド（異なる型のデータ）をまとめた複合型です。

  type MyStruct struct {
      Field1 int
      Field2 string
  }
  

• 型エイリアス (Type Alias): 既存の型に新しい名前を付けることができます。新しい名前は元の型と完全に同じ型として扱われます。

  type MyInt int // MyIntはintのエイリアス
  

  このコミットで問題となっているのは、構造体やポインタを含む複雑な型エイリアスの連鎖です。

コンパイラの型チェッカー

コンパイラの型チェッカーは、プログラムが型規則に準拠していることを検証するコンパイラのフェーズです。主な役割は以下の通りです。

• 型の整合性チェック: 変数への代入、関数呼び出しの引数、演算子のオペランドなどが期待される型と一致するかを確認します。
• 型推論: 明示的な型宣言がない場合に、文脈から型を推測します。
• 不完全な型 (Incomplete Types): 型定義がまだ完全に解決されていない状態の型を指します。例えば、相互参照する構造体や、前方参照される型などがこれに該当します。コンパイラは、これらの不完全な型を適切に処理し、最終的に完全な型情報に解決する必要があります。

前方参照と再帰的な型定義

Goでは、型が定義される前にその型を参照することができます（前方参照）。これは特に、相互に参照し合う構造体や、型エイリアスを介した再帰的な定義で重要になります。

type Node struct {
    Value int
    Next *Node // Node自身を参照
}

type A struct {
    BField *B
}

type B struct {
    AField *A
}

このような場合、コンパイラは型の定義を一度にすべて解決することはできません。部分的に定義された型を一時的に保持し、関連するすべての情報が利用可能になった時点で最終的な型を確定させる必要があります。このプロセスが不完全な場合、型チェックのループや不正確な型情報の伝播が発生します。

技術的詳細

このコミットが解決しようとしている技術的な問題は、Goコンパイラの型チェックフェーズにおける「不完全な型定義の伝播」です。特に、構造体や型エイリアスが複雑に絡み合い、相互に参照し合うような場合に顕著になります。

元の問題は、以下のような型定義の連鎖で発生しました。

type T1 struct { F *T2 }
type T2 T1
type T3 T2

ここで、T1はT2へのポインタを持つ構造体、T2はT1のエイリアス、T3はT2のエイリアスです。コンパイラがこれらの型を処理する際、T1の定義がまだ完了していないにもかかわらず、T2やT3がT1の不完全な定義をコピーしてしまう可能性がありました。これにより、T2やT3が持つべき正しい型情報が欠落したり、誤った情報になったりする問題が発生していました。

以前の修正（CL 4313064）は、この問題の一部を解決しましたが、一般的なケースには対応できていませんでした。このコミットでは、そのCLをロールバックし、より堅牢なアプローチを採用しています。

新しいアプローチの核心は、不完全な型がコピーされる際に、その型が最終的に完成したときに更新されるべきノード（Node）のリストを記録することです。具体的には、Type構造体にcopytoというNodeList型のフィールドを追加し、TFORW（前方参照型）のような不完全な型が解決されるのを待っているノードをこのリストに格納します。

copytype関数が型をコピーする際、もしコピー元の型がまだTFORWである場合、コピー先のノードをそのTFORW型のcopytoリストに追加します。そして、そのTFORW型が最終的に完全な型に解決されたとき、copytoリストに登録されていたすべてのノードに対して再度copytypeを呼び出し、最新の完全な型情報を伝播させます。

これにより、型定義の評価が完了するまで、その型を参照するすべての場所が「待機」し、型が確定した時点で一斉に正しい情報に更新されるようになります。これは、依存関係グラフにおける遅延評価や、イベント駆動型の更新メカニズムに似ています。

また、maplinenoとembedlinenoというフィールドも、型が完全に解決された後にマップキーとしての使用や埋め込み型としての使用に関するチェックを遅延させるために利用されています。これにより、型チェックの順序依存性が適切に管理され、不完全な型情報による誤ったエラーや不正確なコンパイルが防止されます。

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

このコミットでは、主に以下のファイルが変更されています。

1. src/cmd/gc/go.h:
   • Type構造体に新しいフィールドNodeList *copyto;が追加されました。これは、TFORW（前方参照型）が最終的に解決されたときに、その型をコピーする必要があるノードのリストを保持するために使用されます。
   • resumetypecopy関数とdefertypecopy関数の宣言が削除されました。
2. src/cmd/gc/lex.c:
   • main関数からresumetypecopy();の呼び出しが削除されました。
3. src/cmd/gc/typecheck.c:
   • getforwtype関数の定義が削除されました。
   • typecheck1関数内でdefertypecopyの呼び出しが削除されました。
   • defertypecopy関数とresumetypecopy関数の定義が削除されました。
   • copytype関数のロジックが大幅に変更されました。
     • 引数Node *n, Type *tを受け取ります。
     • もしt->etype == TFORW（不完全な型）であれば、nをt->copytoリストに追加し、処理を終了します。これにより、不完全な型が解決されるまでnへのコピーは延期されます。
     • *n->type = *t;で型情報をコピーします。
     • t->copyto = nil;でcopytoリストをクリアします。
     • for(; l; l=l->next) copytype(l->n, t);というループが追加され、この型が解決されるのを待っていたすべてのノード（copytoリストに登録されていたノード）に対して再帰的にcopytypeを呼び出し、最新の完全な型情報を伝播させます。
     • embedlinenoとmaplinenoを利用して、埋め込み型やマップキーとしての使用に関するチェックを遅延実行するロジックが追加されました。
   • typecheckdeftype関数内で、maplinenoとembedlinenoに関する古いチェックロジックが削除され、copytype関数にその責任が移譲されました。
   • typecheckdeftype関数の最後に、mapqueueに登録されたノードに対してマップキーのチェックを行うロジックが追加されました。
4. test/fixedbugs/bug443.go:
   • 新しいテストファイルが追加されました。これは、このコミットが修正する問題（Issue 3709）の具体的なテストケースです。T1, T2, T3という再帰的な型エイリアス定義と、T3に対するメソッド定義が含まれており、以前は「invalid receiver」エラーでコンパイルに失敗していました。
5. test/map1.go:
   • マップキーの型に関するテストケースが追加されました。T1からT8までの様々な型定義（配列、構造体、ポインタ、再帰的な型など）がマップキーとして使用された場合の挙動をテストしています。これにより、型チェックの修正がマップキーの検証にも正しく適用されることを確認しています。

コアとなるコードの解説

このコミットの核心は、src/cmd/gc/go.hにおけるType構造体へのcopytoフィールドの追加と、src/cmd/gc/typecheck.cにおけるcopytype関数の大幅な変更です。

src/cmd/gc/go.h

struct	Type
{
	// ... 既存のフィールド ...

	int32	maplineno;	// first use of TFORW as map key
	int32	embedlineno;	// first use of TFORW as embedded type
	
	// for TFORW, where to copy the eventual value to
	NodeList	*copyto;
};

• NodeList *copyto;: この新しいフィールドは、Type構造体がTFORW（前方参照型、つまりまだ完全に定義されていない型）である場合に特に重要です。このリストには、この不完全な型が最終的に解決されたときに、その完全な型情報をコピーする必要があるすべてのNode（ASTノード）が格納されます。これにより、型定義の依存関係を追跡し、型が確定した時点で関連するすべての場所を更新するメカニズムが提供されます。

src/cmd/gc/typecheck.c

copytype関数の変更

void
copytype(Node *n, Type *t)
{
	int maplineno, embedlineno, lno;
	NodeList *l;

	if(t->etype == TFORW) {
		// This type isn't computed yet; when it is, update n.
		t->copyto = list(t->copyto, n);
		return;
	}

	maplineno = n->type->maplineno;
	embedlineno = n->type->embedlineno;
	l = n->type->copyto; // 以前にこの型を待っていたノードのリスト

	*n->type = *t; // 型情報をコピー

	t = n->type; // n->typeが更新されたので、tも更新

	// ... その他のフィールドのクリア ...
	t->copyto = nil; // コピーが完了したので、copytoリストをクリア

	// Update nodes waiting on this type.
	for(; l; l=l->next)
		copytype(l->n, t); // 待機していたノードに再帰的にコピー

	// Double-check use of type as embedded type.
	lno = lineno;
	if(embedlineno) {
		lineno = embedlineno;
		if(isptr[t->etype])
			yyerror("embedded type cannot be a pointer");
	}
	lineno = lno;
	
	// Queue check for map until all the types are done settling.
	if(maplineno) {
		t->maplineno = maplineno;
		mapqueue = list(mapqueue, n);
	}
}

• 不完全な型の遅延コピー: if(t->etype == TFORW)のブロックが追加されました。もしコピーしようとしている型tがまだTFORW（不完全な型）であれば、現在のノードnをそのtのcopytoリストに追加し、すぐにリターンします。これにより、不完全な型が解決されるまで、その型を参照するノードへの実際の型情報のコピーが延期されます。
• 型情報の伝播: *n->type = *t;で、nの型をtの型で上書きします。これが実際の型情報のコピーです。
• 待機ノードの更新: for(; l; l=l->next) copytype(l->n, t);のループが重要です。lは、以前にn->type（コピーされる前の不完全な型）が解決されるのを待っていたノードのリストです。このループでは、n->typeが完全な型tに解決されたので、l内のすべてのノードに対して再帰的にcopytypeを呼び出し、最新の完全な型情報を伝播させます。これにより、型定義の依存関係が解決され、すべての関連ノードが正しい型情報を持つことが保証されます。
• 遅延チェック: embedlinenoとmaplinenoを利用して、埋め込み型やマップキーとしての使用に関する特定のチェックを、型が完全に解決された後に実行するように遅延させています。これは、不完全な型情報に基づいて誤ったエラーを報告するのを防ぐためです。

typecheckdeftype関数の変更

この関数は、型定義をチェックする際に呼び出されます。変更点としては、以前typecheckdeftype内で直接行われていたmaplinenoとembedlinenoに関するチェックが削除され、その責任がcopytype関数に移譲されました。これにより、型チェックのロジックがよりモジュール化され、不完全な型の処理が一元化されました。

また、mapqueueという新しいリストが導入され、型が完全に解決された後にマップキーのチェックを行うためのノードがこのキューに追加されるようになりました。これにより、マップキーの検証も型解決の最終段階で行われるようになり、不完全な型による問題が回避されます。

これらの変更により、Goコンパイラは複雑な型定義、特に再帰的な型や型エイリアスが絡む場合でも、型情報を正確かつ効率的に処理できるようになりました。

関連リンク

• GitHubコミットページ: https://github.com/golang/go/commit/6363fc5aa6b3aa1ee8826582c6f7a356aa8e4201
• Go Change List (CL) 6301059: https://golang.org/cl/6301059
• Go Issue 3709: このコミットメッセージに記載されているIssue番号ですが、Web検索では直接関連する情報が見つかりませんでした。しかし、コミットメッセージの文脈から、型チェックのループに関する問題であることが示唆されています。

参考にした情報源リンク

• 上記のGitHubコミットページ
• 上記のGo Change List (CL) ページ
• Go言語の公式ドキュメント（型システム、コンパイラの仕組みに関する一般的な知識）
• コンパイラ設計に関する一般的な情報源（型チェック、前方参照、依存関係解決の概念）