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

このコミットは、Goコンパイラ（gc）におけるインターフェース型の比較時に発生する再帰ループのバグを修正するものです。特に、再帰的に定義されたインターフェース型（例: 自身の型を参照するメソッドを持つインターフェース）の比較において、無限ループに陥る問題を解決します。この修正は、型比較のロジックに、既に比較中の型ペアを追跡するメカニズムを導入することで実現されています。

コミット

commit 427b5bddcd0b0a565c82fe79edc7a8b563b8ea76
Author: Russ Cox <rsc@golang.org>
Date:   Mon Jan 23 09:19:02 2012 -0500

    gc: fix recursion loop in interface comparison

    iant's idea.

    Fixes #2745.

    R=iant, dsymonds
    CC=golang-dev
    https://golang.org/cl/5536085

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

https://github.com/golang/go/commit/427b5bddcd0b0a565c82fe79edc7a8b563b8ea76

元コミット内容

Goコンパイラ（gc）において、インターフェース型の比較時に発生する再帰ループを修正します。このアイデアはiantによるものです。Issue #2745を修正します。

変更の背景

Go言語の型システムでは、インターフェース型を含む任意の型を定義できます。Goの仕様では、2つの型が同一であるかどうかの厳密なルールが定められています。特に、インターフェース型は、そのメソッドシグネチャの集合によって定義されます。

問題は、インターフェース型が再帰的に定義される場合に発生しました。例えば、あるインターフェースが、そのインターフェース自身を返すメソッドを持つ場合などです。

type MyInterface interface {
    Method() MyInterface
}

このような再帰的な型定義が存在する場合、Goコンパイラが2つのインターフェース型が等しいかどうかを比較する際に、無限再帰に陥る可能性がありました。型比較のロジックが、再帰的に参照される型を比較しようとするたびに、再び同じ型比較の処理を呼び出し、結果としてスタックオーバーフローや無限ループを引き起こしていました。

このコミットは、この無限再帰の問題を解決するために導入されました。コミットメッセージにあるFixes #2745は、Goプロジェクトの内部バグトラッカーにおける特定の課題番号を示しており、このバグが実際に報告され、修正が必要とされていたことを意味します。

前提知識の解説

Go言語の型システムと型等価性

Go言語では、型は静的に定義され、コンパイル時に厳密にチェックされます。2つの型が等しいかどうかは、Go言語の仕様で明確に定義されています。基本的なルールは以下の通りです。

• 同一の型名: プリミティブ型（int, stringなど）や、同じパッケージ内で同じ名前で宣言された型は等しい。
• 構造体型: フィールドの数、名前、型、タグがすべて同じである場合に等しい。
• 配列型: 要素の型と配列の長さが同じである場合に等しい。
• スライス型: 要素の型が同じである場合に等しい（スライスの長さは実行時に決定されるため、型等価性には影響しない）。
• マップ型: キーの型と要素の型が同じである場合に等しい。
• チャネル型: 要素の型とチャネルの方向（送受信、受信のみ、送信のみ）が同じである場合に等しい。
• 関数型: パラメータの数、型、順序、および戻り値の数、型、順序がすべて同じである場合に等しい。可変長引数（...）の有無も考慮される。
• インターフェース型: インターフェースが持つメソッドの集合が、メソッド名、引数の型、戻り値の型、順序を含めてすべて同じである場合に等しい。

循環参照を持つ型

Go言語では、型定義が循環参照を持つことが可能です。特にインターフェース型や構造体型で発生し得ます。

// インターフェースの循環参照の例
type Node interface {
    Next() Node
}

// 構造体の循環参照の例
type LinkedList struct {
    Value int
    Next  *LinkedList
}

このような循環参照を持つ型を比較する際には、無限再帰に陥らないように特別な注意が必要です。コンパイラは、既に比較中の型ペアを追跡し、同じペアが再度比較対象になった場合は、それらが等しいと仮定して再帰を停止させる必要があります。

src/cmd/gc/subr.cの役割

src/cmd/gc/subr.cは、Goコンパイラ（gc）のソースコードの一部であり、主に型システムに関連するサブルーチンやユーティリティ関数が実装されています。eqtype関数は、このファイル内で定義されており、Go言語の型等価性のルールに従って2つの型が等しいかどうかを判断する役割を担っています。コンパイラの型チェックやコード生成の過程で頻繁に呼び出される非常に重要な関数です。

技術的詳細

このコミットの技術的な核心は、型比較関数eqtypeが再帰的に呼び出される際に、既に比較中の型ペアを検出して無限ループを防ぐメカニズムを導入した点にあります。

修正前は、eqtype関数が直接再帰的に呼び出されていました。循環参照を持つ型（特にインターフェース型）を比較する際、eqtypeは無限に自身を呼び出し続け、最終的にスタックオーバーフローを引き起こしていました。

修正では、以下の要素が導入されました。

1. TypePairList構造体:

   typedef struct TypePairList TypePairList;
   struct TypePairList
   {
       Type *t1;
       Type *t2;
       TypePairList *next;
   };
   

   これは、現在比較中の型ペア（t1, t2）を記録するための連結リストのノードです。nextポインタは、リストの次の要素を指します。

2. onlist関数:

   static int
   onlist(TypePairList *l, Type *t1, Type *t2)
   {
       for(; l; l=l->next)
           if((l->t1 == t1 && l->t2 == t2) || (l->t1 == t2 && l->t2 == t1))
               return 1;
       return 0;
   }
   

   この関数は、与えられた型ペア（t1, t2）が、現在比較中の型ペアのリストlの中に存在するかどうかをチェックします。型ペアの順序は関係なく（(l->t1 == t1 && l->t2 == t2)または(l->t1 == t2 && l->t2 == t1)）、いずれかの組み合わせで一致すれば1（真）を返します。

3. eqtype1関数: eqtype関数の実質的なロジックを担う新しいヘルパー関数です。eqtype1は、比較対象の型ペアに加えて、現在比較中の型ペアのリスト（assumed_equal）を引数として受け取ります。

   static int eqtype1(Type*, Type*, TypePairList*);
   

4. eqtype関数の変更: 元のeqtype関数は、eqtype1を初期の空のリスト（nil）で呼び出すだけのラッパーになりました。

   int
   eqtype(Type *t1, Type *t2)
   {
       return eqtype1(t1, t2, nil);
   }
   

5. eqtype1内部での再帰検出とリスト操作: eqtype1の冒頭で、現在の型ペアが既にassumed_equalリストに存在するかどうかをonlistでチェックします。

   if(onlist(assumed_equal, t1, t2))
       return 1; // 既に比較中であれば、等しいとみなして再帰を停止
   

   もしリストに存在すれば、それは循環参照を検出したことを意味し、その型ペアは等しいと仮定して1を返します。これにより無限再帰が防止されます。

   次に、現在の型ペアをTypePairListの新しいノードlに格納し、それをassumed_equalリストの先頭に追加します（スタックのようにプッシュ）。

   l.next = assumed_equal;
   l.t1 = t1;
   l.t2 = t2;
   

   そして、eqtype1は再帰的に自身を呼び出す際に、この更新されたリスト&lを渡します。

   比較が完了し、eqtype1が結果を返す直前には、リストから現在の型ペアを削除します（スタックのようにポップ）。これはgoto yes;とgoto no;のラベルの直前で行われます。

   yes:
       assumed_equal = l.next; // リストからポップ
       return 1;
   
   no:
       assumed_equal = l.next; // リストからポップ
       return 0;
   

   このプッシュ/ポップのメカニズムにより、再帰の深さに応じて比較中の型ペアのリストが適切に管理され、正確な型等価性チェックが可能になります。

この修正により、Goコンパイラは循環参照を持つインターフェース型を正しく比較できるようになり、コンパイラの堅牢性が向上しました。

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

主要な変更は src/cmd/gc/subr.c ファイルに集中しています。

1. TypePairList構造体の追加:

   typedef struct TypePairList TypePairList;
   struct TypePairList
   {
       Type *t1;
       Type *t2;
       TypePairList *next;
   };
   

2. onlist関数の追加:

   static int
   onlist(TypePairList *l, Type *t1, Type *t2)
   {
       for(; l; l=l->next)
           if((l->t1 == t1 && l->t2 == t2) || (l->t1 == t2 && l->t2 == t1))
               return 1;
       return 0;
   }
   

3. eqtype1関数のプロトタイプ宣言の追加:

   static int eqtype1(Type*, Type*, TypePairList*);
   

4. eqtype関数の変更: eqtype1を呼び出すラッパーに変更。

   int
   eqtype(Type *t1, Type *t2)
   {
       return eqtype1(t1, t2, nil);
   }
   

5. eqtype1関数の実装（旧eqtypeのロジックを移動・修正）:
   • 関数シグネチャがstatic int eqtype1(Type *t1, Type *t2, TypePairList *assumed_equal)に変更。
   • 関数冒頭でonlistによる循環参照チェックと、現在の型ペアのリストへの追加。
   • 再帰的な型比較の呼び出しがeqtypeからeqtype1に変更され、assumed_equalリストが渡されるように修正。
     • 例: !eqtype(t1->type, t2->type) -> !eqtype1(t1->type, t2->type, &l)
   • goto yes;とgoto no;ラベルの導入と、リストからのポップ処理の追加。

また、この修正を検証するための新しいテストファイル test/fixedbugs/bug398.go が追加されています。

// test/fixedbugs/bug398.go
package p

type I1 interface {
      F() interface{I1}
}

type I2 interface {
      F() interface{I2}
}       

var v1 I1
var v2 I2

func f() bool {
       return v1 == v2
}

このテストは、再帰的なインターフェース型I1とI2を定義し、それらの変数を比較することで、修正前のコンパイラがクラッシュする（または無限ループに陥る）状況を再現し、修正後の動作を検証します。

コアとなるコードの解説

このコミットの核心は、eqtype1関数と、それに付随するTypePairListおよびonlist関数の連携にあります。

1. TypePairList: これは、型比較の再帰呼び出し中に、現在比較中の型ペアを記録するためのデータ構造です。t1とt2は比較対象の型へのポインタ、nextは連結リストの次の要素へのポインタです。これにより、比較の「スタック」を明示的に管理します。

2. onlist(TypePairList *l, Type *t1, Type *t2): この関数は、現在の再帰呼び出しのパスにおいて、既にt1とt2のペアが比較対象としてリストlに追加されているかどうかをチェックします。もし存在すれば、それは循環参照を意味します。この場合、無限再帰を防ぐために、その型ペアは等しいとみなして1を返します。これにより、コンパイラは無限ループに陥ることなく、循環参照を持つ型を正しく処理できます。

3. eqtype1(Type *t1, Type *t2, TypePairList *assumed_equal):

   • 再帰検出: 関数が呼び出されると、まずonlist(assumed_equal, t1, t2)を呼び出して、現在の型ペアが既に比較中であるかをチェックします。もしそうであれば、1を返して再帰を停止します。
   • リストへの追加: onlistが0を返した場合（つまり、この型ペアがまだ比較中でない場合）、現在の型ペア（t1, t2）を新しいTypePairListノードlに格納し、assumed_equalリストの先頭に「プッシュ」します（l.next = assumed_equal;）。これにより、この型ペアが比較中であることを記録します。
   • 再帰呼び出し: eqtype1は、型構造の内部要素（例: 構造体のフィールドの型、関数の引数/戻り値の型、配列の要素の型など）を比較するために再帰的に自身を呼び出します。この際、更新されたassumed_equalリスト（&l）を引数として渡します。
   • リストからの削除: eqtype1が結果を返す直前（goto yes;またはgoto no;の直前）で、assumed_equal = l.next;を実行し、現在の型ペアをリストから「ポップ」します。これにより、再帰が戻る際にリストの状態が適切に復元されます。

このメカニズムにより、Goコンパイラは、循環参照を持つ複雑な型構造であっても、型等価性を正確かつ効率的に判断できるようになりました。これは、コンパイラの安定性と正確性を向上させる上で重要な修正です。

関連リンク

• GitHubコミットページ: https://github.com/golang/go/commit/427b5bddcd0b0a565c82fe79edc7a8b563b8ea76
• Go言語の公式リポジトリ: https://github.com/golang/go

参考にした情報源リンク

• 上記のGitHubコミット情報
• Go言語の仕様 (特に型等価性に関するセクション): https://go.dev/ref/spec#Type_identity
• Goコンパイラのソースコード (src/cmd/gc/subr.c)
• Go言語のIssueトラッカー (Issue #2745は古い内部トラッカーの可能性があり、直接的な公開リンクは見つかりませんでした)