Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

コミット

commit 4b6ca212715b7aa66930bc9c3f1e46b096f5f383
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Wed Apr 3 08:18:30 2013 +0200

    cmd/gc: be more tolerant with recursive types when checking map types.
    
    A nested TFORW type would push algtype1 into an impossible case.
    
    Fixes #5125.
    
    R=golang-dev, daniel.morsing
    CC=golang-dev
    https://golang.org/cl/8213043

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

https://github.com/golang/go/commit/4b6ca212715b7aa66930bc9c3f1e46b096f5f383

元コミット内容

cmd/gc: be more tolerant with recursive types when checking map types.

A nested TFORW type would push algtype1 into an impossible case.

Fixes #5125.

R=golang-dev, daniel.morsing
CC=golang-dev
https://golang.org/cl/8213043

変更の背景

このコミットは、Goコンパイラ（cmd/gc）におけるマップ型のチェック時に発生する、再帰型（recursive types）に関するバグを修正するものです。具体的には、Issue 5125で報告された問題に対応しています。

Go言語では、mapのキーとして使用できる型には制約があります。マップのキーは「比較可能（comparable）」でなければなりません。これは、マップがキーのハッシュ値を計算し、キーの等価性を比較することで動作するためです。スライス、マップ、関数などの型は比較可能ではないため、直接マップのキーとして使用することはできません。

問題は、再帰的に定義された型がマップのキーとして使用される場合に発生しました。特に、型がまだ完全に定義されていない「前方参照型（TFORW）」がネストされている場合、コンパイラの型チェックロジック（algtype1関数）が予期せぬ状態に陥り、マップキーの比較可能性チェックが正しく行われないことがありました。これにより、コンパイルエラーや、場合によっては不正な動作を引き起こす可能性がありました。

このコミットは、algtype1関数がTFORW型やTANY型（任意の型を表すプレースホルダー）をより適切に処理できるようにすることで、この問題を解決し、再帰型を含むマップキーの型チェックの堅牢性を向上させています。

前提知識の解説

Goのマップキーの制約（Comparable Types）

Go言語のmap型は、キーと値のペアを格納するデータ構造です。マップのキーには、その値が「比較可能（comparable）」である型のみを使用できます。比較可能とは、==演算子と!=演算子を使って等価性を比較できることを意味します。

具体的には、以下の型が比較可能です。

  • ブール型
  • 数値型（整数型、浮動小数点型、複素数型）
  • 文字列型
  • ポインタ型
  • チャネル型
  • インターフェース型（動的な値が比較可能な場合）
  • 構造体型（すべてのフィールドが比較可能な場合）
  • 配列型（すべての要素が比較可能な場合）

一方、スライス、マップ、関数は比較可能ではないため、直接マップのキーとして使用することはできません。

再帰型 (Recursive Types)

再帰型とは、その定義の中に自分自身を参照する型が含まれる型のことです。例えば、リンクリストのノードやツリー構造のノードなどが典型的な再帰型です。

type Node struct {
    Value int
    Next  *Node // Node型自身へのポインタ
}

Goコンパイラは再帰型を扱うことができますが、型チェックの過程で、まだ完全に定義されていない型（前方参照型）に遭遇することがあります。

algtype1 関数と型チェックの役割

algtype1はGoコンパイラ（cmd/gc）内部で使用される関数で、型の「アラインメント（alignment）」と「サイズ（size）」を計算し、その型が特定の操作（例えば、マップのキーとしての使用）に適しているかどうかを判断するために使用されます。特に、型の比較可能性（comparability）をチェックする上で重要な役割を担っています。

この関数は、与えられた型tを解析し、その型が比較可能であるか、ハッシュ可能であるか、あるいは比較不可能であるかといった情報を返します。ANOEQ（"not equal"、比較不可能）は、その型がマップのキーとして使用できないことを示します。

TFORW 型（前方参照型）

Goコンパイラがソースコードを解析する際、型が定義される前にその型が参照されることがあります。例えば、相互に参照し合う構造体や、再帰型の場合に発生します。このような場合、コンパイラは一時的にその型を「前方参照型（TFORW）」としてマークします。これは、後でその型の完全な定義が見つかったときに解決されるプレースホルダーのようなものです。

TFORW型は、コンパイラが型の依存関係を解決し、最終的な型情報を構築する上で不可欠な概念です。しかし、型チェックの途中でTFORW型に遭遇した場合、その時点では型の完全な情報がないため、algtype1のような関数が適切な判断を下すのが難しい場合があります。

技術的詳細

このコミットの技術的な核心は、src/cmd/gc/subr.cファイル内のalgtype1関数とmaptype関数の変更にあります。

algtype1関数の変更

変更前、algtype1関数はTANY（任意の型）やTFORW（前方参照型）のような、まだ完全には解決されていない型に遭遇した場合、適切な処理を行えず、impossible case（ありえないケース）に陥る可能性がありました。これは、これらの型が一時的なプレースホルダーであるため、その時点では比較可能性などの詳細な情報を判断できないためです。

コミットでは、algtype1関数に以下のcaseが追加されました。

	case TANY:
	case TFORW:
		// will be defined later.
		*bad = t;
		return -1;

この変更により、algtype1がTANYまたはTFORW型の引数を受け取った場合、その型が「後で定義される」ことを認識し、エラーを発生させることなく、*badポインタに現在の型tを設定して-1を返します。これは、この型に関する比較可能性の判断を一時的に保留し、より上位の呼び出し元（この場合はmaptype関数）にその判断を委ねることを意味します。これにより、コンパイラは未解決の型に遭遇してもパニックに陥ることなく、処理を継続できるようになります。

maptype関数の変更

maptype関数は、マップ型を構築する際にキーの型が有効であるか（つまり比較可能であるか）をチェックする役割を担っています。変更前は、maptype関数内でalgtype1(key, nil)を直接呼び出し、その結果に基づいてキーの比較可能性を判断していました。しかし、algtype1がTFORW型で失敗する可能性があったため、問題が発生していました。

コミットでは、maptype関数がalgtype1の戻り値と、algtype1が設定するbadポインタをより慎重に扱うように変更されました。

 	if(key != nil) {
-		switch(key->etype) {
+		atype = algtype1(key, &bad);
+		switch(bad == T ? key->etype : bad->etype) {
 		default:
-			if(algtype1(key, nil) == ANOEQ)
+			if(atype == ANOEQ)
 				yyerror("invalid map key type %T", key);
 			break;
 		case TANY:

変更点：

  1. algtype1(key, &bad)を呼び出し、atypeとbad変数を導入しました。これにより、algtype1が返す比較可能性情報（atype）と、問題があった場合にalgtype1が設定する具体的な問題の型（bad）の両方を取得できるようになりました。
  2. switch文の条件がkey->etypeからbad == T ? key->etype : bad->etypeに変更されました。これは、algtype1がbadポインタをT（グローバルなnil型のようなもの）に設定した場合（つまり、特に問題がなかった場合）は元のkey->etypeを使用し、そうでない場合はbadが指す型（TFORWなど）を使用するという意味です。これにより、algtype1がTFORW型を処理した際にbadにその型が設定されることで、maptypeがその情報を利用して適切な判断を下せるようになります。
  3. if(algtype1(key, nil) == ANOEQ)がif(atype == ANOEQ)に変更されました。これは、algtype1を再度呼び出すのではなく、既に取得したatypeの値を利用して比較可能性をチェックすることを意味します。

これらの変更により、maptypeはalgtype1がTFORW型を処理した結果を正しく解釈し、マップキーの型チェックをより堅牢に行えるようになりました。具体的には、再帰型が前方参照を含んでいても、最終的に比較可能であれば正しく処理され、比較不可能であれば適切なエラーが報告されるようになります。

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

このコミットによる主要なコード変更は、以下のファイルに集中しています。

  • src/cmd/gc/subr.c: Goコンパイラの型チェックおよび型関連のユーティリティ関数が含まれるファイルです。algtype1関数とmaptype関数が変更されました。
    • algtype1関数にTANYとTFORWのケースが追加され、これらの型に対する処理がより寛容になりました。
    • maptype関数がalgtype1の戻り値とbadポインタをより適切に利用するように変更されました。
  • test/fixedbugs/issue5125.dir/bug.go: Issue 5125を再現するための新しいテストケースの一部です。再帰的なインターフェースと構造体の定義が含まれています。
  • test/fixedbugs/issue5125.dir/main.go: 上記bug.goをインポートしてコンパイルを試みるためのメインファイルです。
  • test/fixedbugs/issue5125.go: テストスクリプト本体で、compiledirディレクティブを使用してissue5125.dirディレクトリ内のコードがコンパイルされることを確認します。

コアとなるコードの解説

src/cmd/gc/subr.c の変更

algtype1 関数

@@ -548,6 +548,12 @@ algtype1(Type *t, Type **bad)
 		*bad = T;
 
 	switch(t->etype) {
+	case TANY:
+	case TFORW:
+		// will be defined later.
+		*bad = t;
+		return -1;
+
 	case TINT8:
 	case TUINT8:
 	case TINT16:

この変更は、algtype1関数がTANY（任意の型）またはTFORW（前方参照型）に遭遇した場合の挙動を定義しています。以前はこれらのケースが明示的に処理されていなかったため、コンパイラが未定義の動作に陥る可能性がありました。

  • case TANY: と case TFORW:: これらの型は、コンパイル時にまだ完全な情報が利用できないプレースホルダー型です。
  • // will be defined later.: コメントが示すように、これらの型は後続のコンパイルフェーズで解決されることが期待されます。
  • *bad = t;: badポインタは、algtype1が型チェックで問題を発見した場合に、その問題の型を指すために使用されます。ここでは、TANYやTFORW自体が問題というよりは、その型がまだ解決されていないことを上位の呼び出し元に伝えるために、t（現在の型）をbadに設定しています。
  • return -1;: -1を返すことで、この型に関する比較可能性の判断を一時的に保留し、呼び出し元（maptypeなど）にその処理を委ねることを示します。これにより、コンパイラは未解決の型に遭遇してもクラッシュすることなく、柔軟に処理を継続できます。

maptype 関数

@@ -665,11 +671,14 @@ Type*
 maptype(Type *key, Type *val)
 {
 	Type *t;
+	Type *bad;
+	int atype;
 
 	if(key != nil) {
-\t\tswitch(key->etype) {
+\t\tatype = algtype1(key, &bad);
+\t\tswitch(bad == T ? key->etype : bad->etype) {
 		default:
-\t\t\tif(algtype1(key, nil) == ANOEQ)\
+\t\t\tif(atype == ANOEQ)\
 \t\t\t\tyyerror("invalid map key type %T", key);\
 \t\t\tbreak;\
 \t\tcase TANY:

この変更は、マップのキー型（key）の比較可能性をチェックするmaptype関数のロジックを改善しています。

  • Type *bad; int atype;: algtype1からの戻り値と、問題のある型を受け取るための変数を導入しています。
  • atype = algtype1(key, &bad);: algtype1を呼び出し、キー型keyの比較可能性をチェックします。atypeには比較可能性の結果（例: ANOEQ）、badには問題があった場合の型が格納されます。
  • switch(bad == T ? key->etype : bad->etype): ここが重要な変更点です。
    • bad == T: algtype1がbadポインタをT（nil型のようなもの）に設定した場合、それはalgtype1が特に問題なく処理を完了したことを意味します。この場合、元のキー型key->etypeを使用してswitch文を評価します。
    • bad != T: algtype1がbadポインタにTFORWなどの特定の型を設定した場合、それはその型がまだ解決されていないことを意味します。この場合、bad->etypeを使用してswitch文を評価します。これにより、maptypeはalgtype1がTFORWを処理した結果を正しく解釈し、その後のロジックで適切な判断を下せるようになります。
  • if(atype == ANOEQ): 以前はここでalgtype1を再度呼び出していましたが、新しいコードでは既に取得済みのatype変数を利用しています。ANOEQは「比較不可能」を意味し、この場合、yyerror関数で「無効なマップキー型」というエラーが報告されます。

これらの変更により、Goコンパイラは再帰型や前方参照型がマップのキーとして使用される場合でも、より正確かつ堅牢に型チェックを実行できるようになりました。

テストファイルの追加

  • test/fixedbugs/issue5125.dir/bug.go:

    package bug

type Node interface {
	Eval(s *Scene)
}

type plug struct {
	node Node
}

type Scene struct {
	changed map[plug]bool
}

    このファイルは、Issue 5125を再現するための具体的なコードを提供します。Scene構造体内のchangedマップのキーとしてplug構造体が使用されています。plug構造体はNodeインターフェースを含み、NodeインターフェースはScene型を参照するEvalメソッドを持っています。これにより、SceneとNode（そしてplug）の間に再帰的な依存関係が生まれます。この複雑な再帰型がマップキーとして使用される際に、以前のコンパイラでは問題が発生していました。

  • test/fixedbugs/issue5125.dir/main.go:

    package main

import _ "./bug"

func main() {
}

    bug.goをインポートするだけのシンプルなファイルです。これにより、bug.goで定義された型がコンパイラによって処理され、問題が再現されることを確認します。

  • test/fixedbugs/issue5125.go:

    // compiledir

// 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 5125: cyclic dependencies between types confuse
// the hashability test during import.

package ignored

    このファイルは、Goのテストフレームワークが使用するテストスクリプトです。// compiledirディレクティブは、このテストが指定されたディレクトリ（この場合はissue5125.dir）内のGoファイルをコンパイルすることを意味します。コメントには「Issue 5125: 型間の循環依存がインポート時のハッシュ可能性テストを混乱させる」と明記されており、このコミットが解決しようとしている問題の性質を明確に示しています。

これらのテストファイルの追加により、修正が正しく機能し、将来的に同様の回帰が発生しないことが保証されます。

関連リンク

参考にした情報源リンク