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

このコミットは、Goコンパイラ（gc）における埋め込みインターフェースの処理に関する無限再帰バグを修正するものです。このバグは、特定の状況下でインターフェースのメソッドセットを展開する際に、コンパイラが無限ループに陥り、メモリ不足（OOM）を引き起こす可能性がありました。

コミット

• コミットハッシュ: 9523b4d59c9a902abce9c584ded795376d875d1b
• 作者: Luuk van Dijk lvd@golang.org
• コミット日時: 2012年1月17日 火曜日 10:00:57 +0100
• コミットメッセージ:

  gc: fix infinite recursion for embedded interfaces
  
  Fixes #1909
  
  R=rsc, gri
  CC=golang-dev
  https://golang.org/cl/5523047
  

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

https://github.com/golang/go/commit/9523b4d59c9a902abce9c584ded795376d875d1b

元コミット内容

commit 9523b4d59c9a902abce9c584ded795376d875d1b
Author: Luuk van Dijk <lvd@golang.org>
Date:   Tue Jan 17 10:00:57 2012 +0100

    gc: fix infinite recursion for embedded interfaces
    
    Fixes #1909
    
    R=rsc, gri
    CC=golang-dev
    https://golang.org/cl/5523047
---
 src/cmd/gc/dcl.c                | 13 +++++++++++--
 src/cmd/gc/export.c             | 11 +++++++++--
 src/cmd/gc/fmt.c                | 18 ++++++++++++++++--
 src/cmd/gc/go.y                 |  6 +++++-\n src/pkg/exp/types/gcimporter.go | 31 +++++++++++++++++--------------
 test/fixedbugs/bug395.go        | 15 +++++++++++++++
 6 files changed, 73 insertions(+), 21 deletions(-)

diff --git a/src/cmd/gc/dcl.c b/src/cmd/gc/dcl.c
index 87dab3eeca..94258a0c59 100644
--- a/src/cmd/gc/dcl.c
+++ b/src/cmd/gc/dcl.c
@@ -940,12 +940,20 @@ interfacefield(Node *n)
 Type*
 tointerface(NodeList *l)
 {
-	Type *t, *f, **tp, *t1;
+	Type *t, *f, **tp, **otp, *t1;
 
 	t = typ(TINTER);
+	t->orig = typ(TINTER);
 
-	for(tp = &t->type; l; l=l->next) {
+	tp = &t->type;
+	otp = &t->orig->type;
+
+	for(; l; l=l->next) {
 		f = interfacefield(l->n);
+		*otp = typ(TFIELD);
+		**otp = *f;
+		otp = &(*otp)->down;
+
 		if (l->n->left == N && f->type->etype == TINTER) {
 			// embedded interface, inline methods
 			for(t1=f->type->type; t1; t1=t1->down) {
@@ -953,6 +961,7 @@ tointerface(NodeList *l)
 				f->type = t1->type;
 				f->broke = t1->broke;
 				f->sym = t1->sym;
+				f->embedded = 1;
 				if(f->sym)
 					f->nname = newname(f->sym);
 				*tp = f;
diff --git a/src/cmd/gc/export.c b/src/cmd/gc/export.c
index e1f289200c..965b745a80 100644
--- a/src/cmd/gc/export.c
+++ b/src/cmd/gc/export.c
@@ -241,6 +241,13 @@ dumpexporttype(Type *t)
 	if(t->sym != S && t->etype != TFIELD)
 		dumppkg(t->sym->pkg);
 
+	// fmt will print the ->orig of an interface, which has the original embedded interfaces.
+	// be sure to dump them here
+	if(t->etype == TINTER)
+		for(f=t->orig->type; f; f=f->down)
+			if(f->sym == S)
+				dumpexporttype(f->type);
+
 	dumpexporttype(t->type);
 	dumpexporttype(t->down);
 
@@ -470,8 +477,8 @@ importtype(Type *pt, Type *t)
 		pt->sym->lastlineno = parserline();
 		declare(n, PEXTERN);
 		checkwidth(pt);
-	} else if(!eqtype(pt->orig, t))
-		yyerror("inconsistent definition for type %S during import\n\t%lT\n\t%lT", pt->sym, pt->orig, t);
+	} else if(!eqtype(pt->orig, t->orig))
+		yyerror("inconsistent definition for type %S during import\n\t%lT\n\t%lT", pt->sym, pt, t);
 
 	if(debug['E'])
 		print("import type %T %lT\n", pt, t);
diff --git a/src/cmd/gc/fmt.c b/src/cmd/gc/fmt.c
index 4afd6c42bf..09e73c7b92 100644
--- a/src/cmd/gc/fmt.c
+++ b/src/cmd/gc/fmt.c
@@ -195,6 +195,7 @@ goopnames[] =
 	[OCONTINUE]	= "continue",
 	[OCOPY]		= "copy",
 	[ODEC]		= "--",
+	[ODELETE]	= "delete",
 	[ODEFER]	= "defer",
 	[ODIV]		= "/",
 	[OEQ]		= "==",
@@ -639,9 +640,15 @@ typefmt(Fmt *fp, Type *t)
 		return fmtprint(fp, "map[%T]%T", t->down, t->type);
 
 	case TINTER:
+		t = t->orig;
 		fmtstrcpy(fp, "interface {");
 		for(t1=t->type; t1!=T; t1=t1->down)
-			if(exportname(t1->sym->name)) {
+			if(!t1->sym) {
+				if(t1->down)
+					fmtprint(fp, " %T;", t1->type);
+				else
+					fmtprint(fp, " %T ", t1->type);
+			} else if(exportname(t1->sym->name)) {
 				if(t1->down)
 					fmtprint(fp, " %hS%hT;", t1->sym, t1->type);
 				else
@@ -946,6 +953,7 @@ static int opprec[] = {
 	[OCONVNOP] = 8,
 	[OCONV] = 8,
 	[OCOPY] = 8,
+	[ODELETE] = 8,
 	[OLEN] = 8,
 	[OLITERAL] = 8,
 	[OMAKESLICE] = 8,
@@ -1010,6 +1018,7 @@ static int opprec[] = {
 	[OGT] = 4,
 	[ONE] = 4,
 	[OCMPSTR] = 4,
+	[OCMPIFACE] = 4,
 
 	[OSEND] = 3,
 	[OANDAND] = 2,
@@ -1218,6 +1227,7 @@ exprfmt(Fmt *f, Node *n, int prec)
 	case OAPPEND:
 	case OCAP:
 	case OCLOSE:
+	case ODELETE:
 	case OLEN:
 	case OMAKE:
 	case ONEW:
@@ -1288,6 +1298,7 @@ exprfmt(Fmt *f, Node *n, int prec)
 		return 0;
 
 	case OCMPSTR:
+	case OCMPIFACE:
 		exprfmt(f, n->left, nprec);
 		fmtprint(f, " %#O ", n->etype);
 		exprfmt(f, n->right, nprec+1);
@@ -1303,8 +1314,10 @@ nodefmt(Fmt *f, Node *n)
 	Type *t;
 
 	t = n->type;
-	if(n->orig == N)
+	if(n->orig == N) {
+		n->orig = n;
 		fatal("node with no orig %N", n);
+	}
 
 	// we almost always want the original, except in export mode for literals
 	// this saves the importer some work, and avoids us having to redo some
@@ -1359,6 +1372,7 @@ nodedump(Fmt *fp, Node *n)
 			indent(fp);
 		}
 	}\n+\t\tfmtprint(fp, "[%p]", n);\n \n 	switch(n->op) {
 	default:
diff --git a/src/cmd/gc/go.y b/src/cmd/gc/go.y
index 6a99a275ca..de07354250 100644
--- a/src/cmd/gc/go.y
+++ b/src/cmd/gc/go.y
@@ -1620,7 +1620,7 @@ non_dcl_stmt:
 		$$->list = $2;
 		if($$->list == nil && curfn != N) {
 			NodeList *l;
-			
+
 			for(l=curfn->dcl; l; l=l->next) {
 				if(l->n->class == PPARAM)
 					continue;
@@ -1953,6 +1953,10 @@ hidden_interfacedcl:
 	{
 		$$ = nod(ODCLFIELD, newname($1), typenod(functype(fakethis(), $3, $5)));
 	}\n+|\thidden_type
+\t{\n+\t\t$$ = nod(ODCLFIELD, N, typenod($1));
+\t}\n 
 ohidden_funres:
 	{
 diff --git a/src/pkg/exp/types/gcimporter.go b/src/pkg/exp/types/gcimporter.go
index 10c56db21f..a573fbb246 100644
--- a/src/pkg/exp/types/gcimporter.go
+++ b/src/pkg/exp/types/gcimporter.go
@@ -460,29 +460,32 @@ func (p *gcParser) parseSignature() *Func {
 	return &Func{Params: params, Results: results, IsVariadic: isVariadic}
 }
 
-// MethodSpec = ( identifier | ExportedName )  Signature .\n+// MethodOrEmbedSpec = Name [ Signature ] .\n //
-func (p *gcParser) parseMethodSpec() *ast.Object {
-	if p.tok == scanner.Ident {
-		p.expect(scanner.Ident)
-	} else {
-		p.parseExportedName()
+// MethodOrEmbedSpec = Name [ Signature ] .
+//
+func (p *gcParser) parseMethodOrEmbedSpec() *ast.Object {
+	p.parseName()
+	if p.tok == '(' {
+		p.parseSignature()
+		// TODO(gri) compute method object
+		return ast.NewObj(ast.Fun, "_")
 	}
-	p.parseSignature()
-
-	// TODO(gri) compute method object
-	return ast.NewObj(ast.Fun, "_")
+	// TODO lookup name and return that type
+	return ast.NewObj(ast.Typ, "_")
 }
 
-// InterfaceType = "interface" "{" [ MethodList ] "}" .\n-// MethodList    = MethodSpec { ";" MethodSpec } .\n+// InterfaceType = "interface" "{" [ MethodOrEmbedList ] "}" .\n+// MethodOrEmbedList = MethodOrEmbedSpec { ";" MethodOrEmbedSpec } .\n //
 func (p *gcParser) parseInterfaceType() Type {
 	var methods ObjList
 
 	parseMethod := func() {
-		meth := p.parseMethodSpec()
-		methods = append(methods, meth)
+		switch m := p.parseMethodOrEmbedSpec(); m.Kind {
+		case ast.Typ:
+			// TODO expand embedded methods
+		case ast.Fun:
+			methods = append(methods, m)
+		}
 	}
 
 	p.expectKeyword("interface")
diff --git a/test/fixedbugs/bug395.go b/test/fixedbugs/bug395.go
new file mode 100644
index 0000000000..d0af3f9fce
--- /dev/null
+++ b/test/fixedbugs/bug395.go
@@ -0,0 +1,15 @@
+// $G $D/$F.go || echo "Bug395"
+
+// Copyright 2011 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 1909
+// Would OOM due to exponential recursion on Foo's expanded methodset in nodefmt
+package test
+
+type Foo interface {
+       Bar() interface{Foo}
+       Baz() interface{Foo}
+       Bug() interface{Foo}
+}

変更の背景

このコミットは、Goコンパイラ（gc）が埋め込みインターフェースを処理する際に発生していた無限再帰バグ（Issue 1909）を修正するために行われました。具体的には、インターフェースが自身を埋め込むような再帰的な定義を持つ場合、コンパイラがそのメソッドセットを展開する際に無限ループに陥り、最終的にメモリを使い果たして（Out-Of-Memory, OOM）クラッシュするという問題がありました。

特に、コンパイラの内部で型情報をフォーマットするnodefmt関数が、この再帰的なインターフェース定義によって指数関数的な再帰呼び出しを引き起こし、メモリ消費が急増していました。この問題は、Go言語の型システムにおけるインターフェースの柔軟性と、コンパイラの内部表現の間のミスマッチに起因していました。

前提知識の解説

Goのインターフェース

Go言語のインターフェースは、メソッドのシグネチャの集合を定義する型です。Goのインターフェースは、JavaやC++のような明示的なimplementsキーワードを必要とせず、型がインターフェースで定義されたすべてのメソッドを実装していれば、そのインターフェースを満たすと見なされます（ダックタイピング）。

埋め込みインターフェース

Goでは、構造体と同様に、インターフェースも他のインターフェースを「埋め込む」ことができます。これにより、埋め込まれたインターフェースのすべてのメソッドが、埋め込み元のインターフェースのメソッドセットに含まれるようになります。これは、既存のインターフェースを再利用し、より大きなインターフェースを構築する際に非常に便利です。

例:

type Reader interface {
    Read(p []byte) (n int, err error)
}

type Writer interface {
    Write(p []byte) (n int, err error)
}

type ReadWriter interface {
    Reader // Readerインターフェースを埋め込む
    Writer // Writerインターフェースを埋め込む
}

このReadWriterインターフェースは、ReadメソッドとWriteメソッドの両方を持つことになります。

Goコンパイラ（gc）

gcはGo言語の公式コンパイラです。ソースコードを解析し、抽象構文木（AST）を構築し、型チェック、最適化、最終的なバイナリコード生成を行います。コンパイラの内部では、Goの型はType構造体などの内部データ構造で表現されます。インターフェースのメソッドセットの展開や、型の比較、エクスポート/インポートなどの処理は、これらの内部データ構造を操作することで行われます。

Type構造体とorigフィールド

Goコンパイラの内部では、Type構造体がGoの型を表します。このType構造体には、型の種類（etype）、関連するシンボル（sym）、そして他の型へのポインタ（type, downなど）が含まれます。このコミットで特に重要となるのがorigフィールドです。origフィールドは、型の「元の」または「非正規化された」形式を保持するために使用されます。これは、コンパイラが型を処理する際に、正規化された形式と元の形式を区別する必要がある場合に役立ちます。

技術的詳細

このバグは、Goコンパイラがインターフェースのメソッドセットを構築・展開する際の内部ロジックに潜んでいました。特に、インターフェースが自身を再帰的に埋め込むような定義（例: interface{ Foo() interface{Foo} }）を持つ場合、コンパイラはメソッドセットを「インライン化」して展開しようとします。

問題は、コンパイラがこの展開処理を行う際に、既に処理済みの型を適切に追跡せず、無限に再帰的な展開を試みていた点にあります。具体的には、src/cmd/gc/dcl.cのtointerface関数や、src/cmd/gc/fmt.cのtypefmt関数、そしてnodefmt関数が、再帰的なインターフェース定義に遭遇すると、同じ型を繰り返し展開しようとし、結果としてコールスタックがオーバーフローしたり、メモリが指数関数的に消費されたりして、最終的にOOMエラーでクラッシュしていました。

この修正の核心は、インターフェース型にorig（original）フィールドを導入し、インターフェースの「元の」定義を保持することです。これにより、コンパイラはメソッドセットを展開する際に、無限再帰に陥ることなく、元の定義を参照して処理を進めることができるようになります。

具体的には、以下の点が改善されました。

1. Type構造体におけるorigフィールドの利用: インターフェース型（TINTER）が作成される際に、そのorigフィールドにもインターフェースの元の型情報がコピーされるようになりました。これにより、メソッドセットの展開や型のエクスポート/インポートの際に、正規化された型と元の型を区別して参照できるようになります。
2. 埋め込みインターフェースの追跡: tointerface関数内で、埋め込みインターフェースが処理される際にf->embedded = 1;というフラグが設定されるようになりました。これにより、埋め込みインターフェースであることを明示的に識別し、適切な処理を行うことができます。
3. エクスポート/インポート時のorigの利用: 型のエクスポート（dumpexporttype）およびインポート（importtype）の際にも、インターフェースのorigフィールドが参照されるようになりました。これにより、異なるパッケージ間でインターフェース型をやり取りする際にも、一貫した正しい型情報が保持され、再帰的な問題が回避されます。
4. 型フォーマット時のorigの利用: typefmt関数がインターフェース型をフォーマットする際に、t->origを参照するようになりました。これにより、無限再帰を引き起こすことなく、インターフェースのメソッドセットを正しく表示できるようになります。
5. nodefmtの堅牢化: nodefmt関数がn->origがN（nil）である場合にfatalエラーを出す前に、n->orig = n;として自身を代入するようになりました。これは、origフィールドが未設定の場合のフォールバックとして機能し、コンパイラの堅牢性を高めます。

これらの変更により、コンパイラは再帰的なインターフェース定義に遭遇しても、無限ループに陥ることなく、正しく型を処理し、メソッドセットを構築できるようになりました。

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

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

• src/cmd/gc/dcl.c: インターフェースの宣言と型構築に関するロジック。
• src/cmd/gc/export.c: 型のエクスポートとインポートに関するロジック。
• src/cmd/gc/fmt.c: コンパイラ内部の型やノードのフォーマット（文字列化）に関するロジック。
• src/cmd/gc/go.y: Go言語の文法定義（Yaccファイル）。
• src/pkg/exp/types/gcimporter.go: gc形式の型情報をインポートするためのパッケージ。
• test/fixedbugs/bug395.go: このバグを再現し、修正を検証するための新しいテストケース。

コアとなるコードの解説

src/cmd/gc/dcl.c

• tointerface関数:
  • インターフェース型tを作成する際に、t->orig = typ(TINTER);として、そのorigフィールドにも新しいインターフェース型を割り当てています。これにより、tとt->origが独立した型構造を持つようになります。
  • tp = &t->type;に加えて、otp = &t->orig->type;というポインタが導入され、tの型リストとt->origの型リストを並行して構築しています。
  • 埋め込みインターフェース（f->type->etype == TINTER）の場合、展開されたメソッドフィールドfに対してf->embedded = 1;というフラグを設定しています。これは、このフィールドが埋め込みインターフェースから来たものであることを示します。

これらの変更により、インターフェースのメソッドセットを構築する際に、元のインターフェースの構造をorigフィールドに保持しつつ、展開されたメソッドセットをtypeフィールドに構築できるようになり、再帰的な参照が適切に管理されます。

src/cmd/gc/export.c

• dumpexporttype関数:
  • インターフェース型（t->etype == TINTER）の場合、t->orig->typeを走査し、埋め込みインターフェースの型もエクスポートするように変更されています。これにより、エクスポートされる型情報にorigフィールドの内容が反映され、インポート側で正しく再構築できるようになります。
• importtype関数:
  • 型の定義が矛盾していないかをチェックする際に、eqtype(pt->orig, t)からeqtype(pt->orig, t->orig)に変更されました。これは、インポートされた型のorigフィールドと、既存の型のorigフィールドを比較することで、より厳密かつ正確な型の一貫性チェックを行うためです。

これらの変更は、コンパイラが型情報をエクスポート/インポートする際に、インターフェースのorigフィールドを考慮に入れることで、型の一貫性を保ち、再帰的な問題を防ぐことを目的としています。

src/cmd/gc/fmt.c

• goopnamesとopprec配列:
  • ODELETEとOCMPIFACEという新しいオペレーションコードが追加されています。これらはGo言語の内部的な操作を表すもので、このコミットの直接的な再帰修正とは関係ありませんが、コンパイラの他の部分での変更に伴うものです。
• typefmt関数:
  • インターフェース型（case TINTER）をフォーマットする際に、t = t->orig;という行が追加されました。これにより、フォーマット時には常にインターフェースの「元の」定義が使用されるようになり、無限再帰が回避されます。
  • 埋め込みインターフェースのシンボルがない場合（!t1->sym）のフォーマットロジックが追加され、埋め込みインターフェースが正しく表示されるようになりました。
• nodefmt関数:
  • if(n->orig == N)のチェックで、fatalエラーを出す前にn->orig = n;という行が追加されました。これは、ノードのorigフィールドが未設定の場合に、そのノード自身をorigとして設定することで、クラッシュを防ぎ、より堅牢な動作を保証します。

これらの変更は、コンパイラが型情報を文字列として表現する際に、無限再帰に陥ることなく、インターフェースの構造を正しく表示できるようにするためのものです。

src/cmd/gc/go.y

• hidden_interfacedclルール:
  • | hidden_type { $$ = nod(ODCLFIELD, N, typenod($1)); }という新しいプロダクションが追加されました。これは、Goの文法解析において、匿名で埋め込まれた型（インターフェースを含む）を正しく処理するためのものです。

src/pkg/exp/types/gcimporter.go

• parseMethodOrEmbedSpec関数:
  • parseMethodSpecがparseMethodOrEmbedSpecにリネームされ、メソッドだけでなく埋め込み型も解析できるように変更されました。
  • p.parseName()の後に、トークンが(であればメソッドシグネチャを解析し、そうでなければ型として扱うロジックが追加されました。
• parseInterfaceType関数:
  • parseMethodクロージャ内で、p.parseMethodOrEmbedSpec()の結果をswitch文で処理し、ast.Typ（型）の場合は「埋め込みメソッドを展開する」（TODO expand embedded methods）というコメントが追加されています。これは、インポート時に埋め込みインターフェースのメソッドセットを正しく展開するための将来的な作業を示唆しています。

これらの変更は、Goの型チェッカー/インポーターが、コンパイラの内部表現と連携して、埋め込みインターフェースを正しく解析し、型システムに統合できるようにするためのものです。

test/fixedbugs/bug395.go

この新しいテストファイルは、Issue 1909で報告されたバグを再現するためのものです。

type Foo interface {
       Bar() interface{Foo}
       Baz() interface{Foo}
       Bug() interface{Foo}
}

このFooインターフェースは、Bar, Baz, Bugというメソッドを持ち、それぞれのメソッドがinterface{Foo}という、自身を埋め込むようなインターフェースを返します。このような再帰的な定義が、修正前のコンパイラで無限再帰を引き起こしていました。このテストの追加により、修正が正しく適用され、バグが解消されたことが検証されます。

関連リンク

• GitHubコミットページ: https://github.com/golang/go/commit/9523b4d59c9a902abce9c584ded795376d875d1b
• Gerrit Change-ID: https://golang.org/cl/5523047

参考にした情報源リンク

• Go issue #56103: spec: disallow anonymous interface cycles (このコミットのIssue #1909とは直接関連しないものの、Goのインターフェースにおける再帰的な問題や匿名インターフェースのサイクルに関する議論の文脈で参考になります)
  • https://github.com/golang/go/issues/56103
• Go言語のインターフェースに関する公式ドキュメントやチュートリアル (Goのインターフェースと埋め込みインターフェースの基本的な理解のため)
  • https://go.dev/doc/effective_go#interfaces
  • https://go.dev/tour/methods/10 (埋め込みインターフェースの例)
• Goコンパイラのソースコード (特にsrc/cmd/gcディレクトリ内のファイル構造と役割の理解のため)
  • https://github.com/golang/go/tree/master/src/cmd/compile/internal/gc (現在のGoコンパイラのgc部分のパス)