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

このコミットは、Goコンパイラ（cmd/gc）における関数型（function types）のパラメータ名と結果名の重複チェックに関するバグを修正し、そのチェックのパフォーマンスを改善するものです。具体的には、重複チェックのアルゴリズムを二次時間計算量（quadratic）から線形時間計算量（linear）に最適化しています。

コミット

commit 615f289209d08316da2c609f843bd20201ce2275
Author: Russ Cox <rsc@golang.org>
Date:   Fri Mar 15 15:24:13 2013 -0400

    cmd/gc: ensure unique parameter and result names in function types
    
    In addition to fixing the bug, the check is now linear instead of quadratic.
    
    Fixes #4469.
    
    R=ken2
    CC=golang-dev
    https://golang.org/cl/7773047

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

https://github.com/golang/go/commit/615f289209d08316da2c609f843bd20201ce2275

元コミット内容

cmd/gc: ensure unique parameter and result names in function types

In addition to fixing the bug, the check is now linear instead of quadratic.

Fixes #4469.

R=ken2
CC=golang-dev
https://golang.org/cl/7773047

変更の背景

このコミットは、Goコンパイラ（cmd/gc）が関数型定義におけるパラメータ名や結果名が重複している場合に、正しくエラーを報告しないというバグ（Issue #4469）を修正するために行われました。

元の実装では、関数型内のパラメータ名や結果名の重複をチェックする際に、ネストされたループを使用しており、これが二次時間計算量（O(n^2)）のパフォーマンス特性を持っていました。これは、パラメータや結果の数が増えるにつれてチェックにかかる時間が急激に増加することを意味します。特に、多数のパラメータを持つ関数型の場合、コンパイル時間が不必要に長くなる可能性がありました。

このコミットの目的は、以下の2点です。

バグ修正: 関数型における重複するパラメータ名や結果名を正しく検出してエラーを報告する。
パフォーマンス改善: 重複チェックのアルゴリズムを二次時間計算量から線形時間計算量（O(n)）に改善し、コンパイル効率を向上させる。

Go言語では、関数も型を持ちます。例えば、func(int, string) (bool, error) のような形式で、引数の型と戻り値の型を定義します。この関数型には、引数や戻り値に名前を付けることができます（例: func(x int, y string) (ok bool, err error)）。これらの名前は、関数のシグネチャの一部ではありませんが、コードの可読性を高めるために使用されます。

Goコンパイラ (`cmd/gc`)

cmd/gc は、Go言語の公式コンパイラです。Goのソースコードを機械語に変換する役割を担っています。コンパイルプロセスには、字句解析、構文解析、意味解析、最適化、コード生成などが含まれます。このコミットが関連するのは、主に意味解析の段階で、型チェックや名前解決が行われる部分です。

シンボルテーブルと `Sym` 構造体

コンパイラは、プログラム内で定義される変数、関数、型などの名前（シンボル）を管理するためにシンボルテーブルを使用します。Goコンパイラでは、これらのシンボルは Sym 構造体で表現されます。Sym 構造体には、シンボルの名前、スコープ、型などの情報が含まれます。

二次時間計算量（Quadratic Time Complexity: O(n^2)）と線形時間計算量（Linear Time Complexity: O(n)）

二次時間計算量 (O(n^2)): アルゴリズムの実行時間が入力サイズ n の二乗に比例する場合を指します。例えば、ネストされた2つのループで配列のすべてのペアを比較するような処理がこれに該当します。入力サイズが大きくなると、実行時間が急激に増加するため、大規模なデータには不向きです。
線形時間計算量 (O(n)): アルゴリズムの実行時間が入力サイズ n に比例する場合を指します。例えば、配列の要素を一度だけ走査するような処理がこれに該当します。入力サイズが大きくなっても、実行時間の増加は緩やかであり、効率的なアルゴリズムとされます。

このコミットでは、重複チェックのアルゴリズムを O(n^2) から O(n) に改善することで、コンパイルの効率を大幅に向上させています。

技術的詳細

このコミットの主要な技術的変更点は、関数型、構造体フィールド、インターフェースメソッドのパラメータ/フィールド名の重複チェックを、より効率的な線形時間アルゴリズムに置き換えたことです。

以前の checkdupfields 関数は、ネストされたループを使用していました。これは、リスト内の各要素について、その後のすべての要素と比較するという方法で、重複を検出していました。このアプローチは、要素の数が n の場合、約 n * (n-1) / 2 回の比較が必要となり、O(n^2) の計算量になります。

新しいアプローチでは、Sym 構造体に uniqgen という新しいフィールドを追加し、グローバルなユニークなジェネレーション番号 uniqgen を導入しています。

uniqgen の導入:
- src/cmd/gc/go.h の Sym 構造体に uint32 uniqgen; フィールドが追加されました。これは、シンボルが現在のチェックパスで既に訪問されたかどうかをマークするために使用されます。
- src/cmd/gc/dcl.c に static uint32 uniqgen; というグローバル変数が追加されました。これは、重複チェックの各パスの開始時にインクリメントされるカウンターとして機能します。
checkdupfields の変更:
- checkdupfields 関数は、ネストされたループを削除し、単一のループでリストを走査するように変更されました。
- 各シンボル t->sym について、その t->sym->uniqgen が現在のグローバルな uniqgen と等しいかどうかをチェックします。
  - もし等しければ、そのシンボルは現在のチェックパスで既に遭遇しており、重複していることを意味します。この場合、エラーが報告されます。
  - 等しくなければ、そのシンボルは初めて遭遇したものであり、t->sym->uniqgen を現在のグローバルな uniqgen に設定します。これにより、同じチェックパス内で再度遭遇した際に重複として検出されます。
uniqgen のインクリメント:
- tostruct (構造体フィールドの処理), tointerface (インターフェースメソッドの処理), functype (関数型の処理) の各関数で、checkdupfields を呼び出す直前にグローバルな uniqgen がインクリメントされます。これにより、各チェックパスが独立したジェネレーション番号を持つことが保証され、以前のチェックパスでのマークが現在のチェックに影響を与えないようになります。

この変更により、各シンボルは checkdupfields 関数内で最大1回だけアクセスされ、比較されるため、チェックの計算量が線形時間（O(n)）に削減されます。

また、declare 関数内の重複宣言チェックも微調整されています。functype が関数引数の重複エラーを報告するため、PPARAM および PPARAMOUT コンテキストでの重複宣言エラーは declare 関数では抑制されるようになりました。これにより、同じエラーが複数回報告されるのを防ぎます。

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

`src/cmd/gc/dcl.c`

declare 関数内の重複宣言チェックロジックが変更され、PPARAM および PPARAMOUT コンテキストでは重複エラーを抑制するようになりました。
static uint32 uniqgen; が追加されました。
checkdupfields 関数が大幅に書き換えられ、uniqgen を使用した線形時間チェックに変わりました。
tostruct, tointerface, functype 関数内で uniqgen++ が追加され、checkdupfields の呼び出しが調整されました。特に functype では、入力、出力、レシーバの各引数リストに対して checkdupfields が呼び出されるようになりました。
tofunargs から checkdupfields の呼び出しが削除されました。これは functype でまとめてチェックされるためです。

`src/cmd/gc/go.h`

Sym 構造体に uint32 uniqgen; フィールドが追加されました。

テストファイル

test/fixedbugs/bug040.go, test/fixedbugs/bug342.go, test/fixedbugs/bug412.go, test/func1.go の期待されるエラーメッセージが、新しいエラーメッセージ（"duplicate argument" など）に合わせて更新されました。
test/fixedbugs/bug469.go が削除されました。これは、このコミットで修正された問題に関連するテストであり、もはや必要ないためです。
test/funcdup.go と test/funcdup2.go という新しいテストファイルが追加されました。これらは、関数型、インターフェース、構造体、通常の関数定義における重複するパラメータ名や結果名が正しく検出されることを検証するためのものです。

コアとなるコードの解説

`src/cmd/gc/go.h` の `Sym` 構造体への `uniqgen` 追加

struct	Sym
{
	uchar	sym;		// huffman encoding in object file
	Sym*	link;
	int32	tnpkg;	// number of imported packages with this name
	uint32	uniqgen; // <-- 追加
	// saved and restored by dcopy
	Pkg*	pkg;
};

Sym 構造体に uniqgen フィールドが追加されました。これは、シンボルが現在の重複チェックのパスで既に処理されたかどうかを効率的にマークするために使用されます。uint32 型であるため、非常に多くのチェックパスが連続して行われない限り、オーバーフローの心配はほとんどありません。

`src/cmd/gc/dcl.c` の `checkdupfields` 関数の変更

// 変更前 (二次時間計算量)
static void
checkdupfields(Type *t, char* what)
{
	Type* t1;
	int lno;

	lno = lineno;

	for( ; t; t=t->down)
		if(t->sym && t->nname && !isblank(t->nname))
			for(t1=t->down; t1; t1=t1->down)
				if(t1->sym == t->sym) {
					lineno = t->nname->lineno;
					yyerror("duplicate %s %s", what, t->sym->name);
					break;
				}

	lineno = lno;
}

// 変更後 (線形時間計算量)
static uint32 uniqgen; // <-- 追加

static void
checkdupfields(Type *t, char* what)
{
	int lno;

	lno = lineno;

	for( ; t; t=t->down) {
		if(t->sym && t->nname && !isblank(t->nname)) {
			if(t->sym->uniqgen == uniqgen) { // <-- uniqgen を使用したチェック
				lineno = t->nname->lineno;
				yyerror("duplicate %s %s", what, t->sym->name);
			} else
				t->sym->uniqgen = uniqgen; // <-- uniqgen を設定
		}
	}

	lineno = lno;
}

checkdupfields 関数は、重複チェックの核心部分です。変更前はネストされたループで各要素を総当たりで比較していましたが、変更後は uniqgen を利用することで、各シンボルを一度だけ走査するだけで重複を検出できるようになりました。

t->sym->uniqgen == uniqgen のチェックは、現在の checkdupfields の呼び出し（つまり、現在の重複チェックパス）において、このシンボルが既に処理済みであるかを確認します。もし処理済みであれば、それは重複していることを意味します。
t->sym->uniqgen = uniqgen は、シンボルが初めて遭遇した場合に、現在の uniqgen 値でシンボルをマークします。

`tostruct`, `tointerface`, `functype` での `uniqgen` のインクリメントと `checkdupfields` の呼び出し

// tostruct (構造体フィールド)
// ...
	uniqgen++; // <-- 追加
	checkdupfields(t->type, "field");
// ...

// tointerface (インターフェースメソッド)
// ...
	uniqgen++; // <-- 追加
	checkdupfields(t->type, "method");
// ...

// functype (関数型)
// ...
	uniqgen++; // <-- 追加
	checkdupfields(t->type->type, "argument"); // レシーバ
	checkdupfields(t->type->down->type, "argument"); // 戻り値
	checkdupfields(t->type->down->down->type, "argument"); // 引数
// ...

これらの関数は、それぞれ構造体、インターフェース、関数型の定義を処理する際に checkdupfields を呼び出します。checkdupfields を呼び出す直前に uniqgen++ を行うことで、各型定義の重複チェックが独立したコンテキストで行われることを保証します。これにより、異なる型定義間で uniqgen の値が混同されることなく、正確な重複検出が可能になります。

特に functype では、レシーバ、戻り値、引数の各リストに対して checkdupfields が呼び出され、それぞれのリスト内で重複する名前がないかを確認します。

`declare` 関数内の変更

// 変更前
	if(s->block == block)
		redeclare(s, "in this block");

// 変更後
	if(s->block == block) {
		// functype will print errors about duplicate function arguments.
		// Don't repeat the error here.
		if(ctxt != PPARAM && ctxt != PPARAMOUT)
			redeclare(s, "in this block");
	}

この変更は、functype が関数引数の重複エラーを報告するようになったため、declare 関数が同じエラーを再度報告するのを防ぐためのものです。PPARAM (パラメータ) および PPARAMOUT (戻り値) のコンテキストでは、declare は重複宣言エラーを抑制します。これにより、コンパイラの出力がよりクリーンになり、ユーザーにとって分かりやすくなります。

これらの変更により、Goコンパイラは関数型におけるパラメータ名と結果名の重複を正確に検出し、かつそのチェックを非常に効率的に行えるようになりました。

参考にした情報源リンク

Go言語の公式ドキュメント
Goコンパイラのソースコード (src/cmd/gc/)
Go言語のIssueトラッカー
Go言語のコードレビューシステム (Gerrit)
計算量に関する一般的な情報源 (O記法など)