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

このコミットは、Go言語のランタイムとコンパイラにおける重要な改善を導入し、chan (チャネル) と map (マップ) がスライス ([]) および構造体 (struct) を要素型またはキー/値型として扱えるように拡張しました。これにより、Goの型システムと並行処理の柔軟性が大幅に向上しています。

コミット

commit eee50ae1ac25dec3047e111fd62ee1f83e874e26
Author: Russ Cox <rsc@golang.org>
Date:   Fri Dec 19 12:05:22 2008 -0800

    chan and map of [] and struct
    
    R=r
    DELTA=192  (145 added, 8 deleted, 39 changed)
    OCL=21609
    CL=21614

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

https://github.com/golang/go/commit/eee50ae1ac25dec3047e111fd62ee1f83e874e26

元コミット内容

このコミットは、Go言語のチャネルとマップが、これまでサポートされていなかったスライス型と構造体型を要素またはキー/値として扱えるようにするための変更です。具体的には、コンパイラがこれらの新しい型を認識し、ランタイムがそれらの型に対するハッシュ、比較、コピーといった操作を適切に処理できるように、内部の型アルゴリズムの定義と利用箇所が更新されています。

変更の背景

Go言語の初期段階では、チャネルやマップが扱える型には制限がありました。特に、スライスや構造体のような複合型を直接チャネルで送受信したり、マップのキーや値として使用することはできませんでした。これは、これらの型が内部的に複雑な構造を持つため、ランタイムがそれらを効率的かつ正確にハッシュしたり、比較したり、コピーしたりするための汎用的なメカニズムがまだ整備されていなかったためです。

このコミットは、Go言語の表現力と実用性を高めるために、これらの複合型に対するサポートを追加することを目的としています。これにより、開発者はより自然な形でデータ構造をチャネルやマップで扱うことができ、コードの記述が容易になり、より複雑な並行処理パターンやデータ管理が可能になります。

前提知識の解説

このコミットを理解するためには、以下のGo言語の基本的な概念と内部実装に関する知識が必要です。

1. Goの型システム:
   • プリミティブ型: int, string, bool など。これらは単純な値として扱われます。
   • 複合型:
     • 配列 (Arrays): 固定長で、要素は同じ型を持ちます。Goでは配列は値型です。
     • スライス (Slices): 配列の上に構築された動的なビューです。スライスは内部的にポインタ、長さ、容量を持ち、参照型のように振る舞います。このコミットの文脈では、[] は通常スライスを指します。
     • 構造体 (Structs): 異なる型のフィールドをまとめたユーザー定義の複合型です。構造体は値型です。
     • インターフェース (Interfaces): 型が満たすべきメソッドのセットを定義します。
     • ポインタ (Pointers): メモリアドレスを指します。
2. チャネル (Channels): Goの並行処理の根幹をなす要素で、ゴルーチン間で値を安全に送受信するためのパイプです。チャネルは特定の型の値を送受信するように型付けされます。
3. マップ (Maps): キーと値のペアを格納するハッシュテーブルです。キーは比較可能でなければならず、値は任意の型を持つことができます。
4. Goランタイム (Go Runtime): Goプログラムの実行を管理する低レベルのシステムです。ガベージコレクション、スケジューリング、チャネルやマップの操作など、多くの内部処理を担当します。
5. Goコンパイラ (Go Compiler - gc): Goのソースコードを機械語に変換するツールです。型チェック、コード生成、最適化などを行います。
6. 型アルゴリズム (Type Algorithms): Goのランタイム内部では、各型に対して特定の操作（ハッシュ計算、等価性比較、メモリコピー、値の出力など）を行うための「アルゴリズム」が定義されています。これらは通常、関数ポインタのテーブルとして管理され、algarray のような構造で表現されます。例えば、文字列のハッシュと整数のハッシュは異なるアルゴリズムを使用します。

このコミットは、特にスライスと構造体という複合型が、チャネルやマップの要素/キー/値として適切に扱われるように、コンパイラとランタイムの両方でこれらの型アルゴリズムを拡張・統合するものです。

技術的詳細

このコミットの技術的詳細は、Goコンパイラ (src/cmd/gc) とGoランタイム (src/runtime) の連携にあります。

1. コンパイラ側の変更 (src/cmd/gc/go.h, src/cmd/gc/subr.c):

   • go.h に、新しい型アルゴリズムの識別子として AARRAY (配列/スライス用) と ASTRUCT (構造体用) が enum に追加されました。これらは、ランタイムが特定の型に対してどの操作（ハッシュ、比較など）を使用すべきかを識別するための定数です。
   • subr.c の algtype 関数が更新されました。この関数は、Goの型 (Type *t) を受け取り、対応する型アルゴリズムの識別子（ASIMP, ASTRING, APTR, AINTER など）を返します。今回の変更で、TARRAY (配列型) に対して AARRAY を、TSTRUCT (構造体型) に対して ASTRUCT を返すロジックが追加されました。これにより、コンパイラはスライスや構造体の型情報をランタイムに正しく伝達できるようになります。

2. ランタイム側の変更 (src/runtime/chan.c, src/runtime/hashmap.c, src/runtime/runtime.c, src/runtime/runtime.h, src/runtime/iface.c):

   • 型アルゴリズムの定義と利用の拡張:
     • runtime.h に AARRAY と ASTRUCT が enum に追加され、コンパイラとランタイム間で型アルゴリズムの識別子が共有されるようになりました。また、algarray の宣言が固定長から可変長 ([]) に変更され、新しい型アルゴリズムの追加に対応できるようになりました。
     • runtime.c の algarray の初期化が更新されました。algarray は、Goの各型アルゴリズム（ASIMP, ASTRING, APTR, AINTER など）に対応する関数ポインタのテーブルです。このテーブルに AARRAY と ASTRUCT のエントリが追加され、それぞれ memhash, memequal, memprint, memcopy といった汎用的なメモリ操作関数が割り当てられました。これは、スライスや構造体のハッシュ、比較、コピーが、そのメモリ内容に基づいて行われることを意味します。
     • runtime.c では、文字列 (string) とポインタ (void*) の操作関数名が、より簡潔なプレフィックス (str と ptr) に変更されました (stringhash -> strhash など)。これはコードの一貫性を高めるためのリファクタリングです。
   • チャネルの要素型サポート (src/runtime/chan.c):
     • sys·newchan 関数は、新しいチャネルを作成する際に要素の型アルゴリズム (elemalg) を受け取ります。この関数内のチェックが拡張され、AARRAY と ASTRUCT が有効な elemalg として許可されるようになりました。これにより、チャネルがスライスや構造体を要素として扱えるようになります。
   • マップのキー/値型サポート (src/runtime/hashmap.c):
     • sys·newmap 関数は、新しいマップを作成する際にキーの型アルゴリズム (keyalg) と値の型アルゴリズム (valalg) を受け取ります。この関数内のチェックが拡張され、AARRAY と ASTRUCT が有効な keyalg および valalg として許可されるようになりました。これにより、マップがスライスや構造体をキーまたは値として扱えるようになります。
     • Goのマップのキーは比較可能でなければなりません。スライスや構造体がキーとして使用できるようになったのは、ランタイムがこれらの型に対してバイト単位の比較 (memequal) とハッシュ計算 (memhash) を実行できるようになったためです。
   • iface.c の変更: iface.c から ASIMP などの enum 定義が削除されました。これは、これらの定義が runtime.h に一元化されたためです。

3. テストの追加 (test/bigalg.go):

   • 新しいテストファイル bigalg.go が追加され、チャネルとマップがスライスと構造体を正しく扱えることを検証しています。
   • arraycmptest: スライスの比較に関する基本的なテスト。
   • maptest: 構造体を値とするマップ、スライスを値とするマップのテスト。
   • maptest2: 構造体をキーとするマップ、スライスをキーとするマップのテスト。
   • chantest: 構造体を要素とするチャネル、スライスを要素とするチャネルのテスト。

これらの変更により、Goのコンパイラはスライスや構造体の型情報をランタイムに渡し、ランタイムはそれらの型に対して適切な内部操作（ハッシュ、比較、コピー）を実行できるようになりました。

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

このコミットのコアとなる変更は、Goの型システムがスライスと構造体をチャネルとマップで扱えるように拡張された点です。

1. 型アルゴリズムの定義拡張:

   • src/cmd/gc/go.h および src/runtime/runtime.h で AARRAY と ASTRUCT が新しい型アルゴリズムとして追加されました。
   • src/cmd/gc/subr.c の algtype 関数で、TARRAY と TSTRUCT に対してこれらの新しいアルゴリズムが返されるようになりました。

2. ランタイムの型アルゴリズムテーブルの更新:

   • src/runtime/runtime.c の algarray が拡張され、AARRAY と ASTRUCT のエントリが追加されました。これにより、これらの型に対するハッシュ、比較、コピーなどの操作が定義されました。

3. チャネルとマップの型チェックの緩和:

   • src/runtime/chan.c の sys·newchan と src/runtime/hashmap.c の sys·newmap で、elemalg, keyalg, valalg のチェックが緩和され、AARRAY と ASTRUCT が許可されるようになりました。

4. テストケースの追加:

   • test/bigalg.go が追加され、これらの新しい機能が正しく動作することを確認しています。

コアとなるコードの解説

src/cmd/gc/go.h と src/runtime/runtime.h の enum 変更

--- a/src/cmd/gc/go.h
+++ b/src/cmd/gc/go.h
@@ -41,6 +41,8 @@ enum
 	ASTRING,
 	APTR,
 	AINTER,
+	AARRAY,
+	ASTRUCT,
 
 	BADWIDTH	= -1000000000
 };

--- a/src/runtime/runtime.h
+++ b/src/runtime/runtime.h
@@ -214,10 +214,23 @@ struct	Func
 #define	nelem(x)\t(sizeof(x)/sizeof((x)[0]))
 #define	nil\t\t((void*)0)
 
+/*
+ * known to compiler
+ */
+enum
+{
+	ASIMP		= 0,
+	ASTRING,
+	APTR,
+	AINTER,
+	AARRAY,
+	ASTRUCT,
+};
+
 /*
  * external data
  */
-extern	Alg	algarray[4];
+extern	Alg	algarray[];
 extern	string	emptystring;
 G*	allg;
 int32	goidgen;

これらの変更は、コンパイラとランタイムがGoの型を内部的に分類するために使用する列挙型に、AARRAY (配列/スライス) と ASTRUCT (構造体) を追加しています。これにより、これらの複合型がランタイムで特別な処理を必要とすることをシステム全体で認識できるようになります。algarray の宣言が固定長から可変長になったのは、将来的な型アルゴリズムの追加に柔軟に対応するためです。

src/cmd/gc/subr.c の algtype 関数変更

--- a/src/cmd/gc/subr.c
+++ b/src/cmd/gc/subr.c
@@ -301,6 +301,12 @@ algtype(Type *t)
 	if(isptr[t->etype])
 		a = APTR;	// pointer
 	else
+	if(t->etype == TARRAY)
+		a = AARRAY;
+	else
+	if(t->etype == TSTRUCT)
+		a = ASTRUCT;
+	else
 	if(isinter(t))
 		a = AINTER;	// interface
 //	else

algtype 関数は、Goの型 (Type *t) を受け取り、その型がランタイムでどのように扱われるべきかを示す「アルゴリズムタイプ」を返します。この変更により、コンパイラは配列型 (TARRAY) を AARRAY として、構造体型 (TSTRUCT) を ASTRUCT として識別し、ランタイムにその情報を渡すことができるようになりました。これは、コンパイラがランタイムの型処理と連携するための重要なステップです。

src/runtime/runtime.c の algarray 初期化変更

--- a/src/runtime/runtime.c
+++ b/src/runtime/runtime.c
@@ -646,12 +646,13 @@ pointercopy(uint32 s, void **a, void **b)
 }
 
 Alg
-algarray[4] =
-{
-	{\tmemhash,\tmemequal,\tmemprint,\tmemcopy\t},  // 0
-	{\tstringhash,\tstringequal,\tstringprint,\tstringcopy\t},  // 1
-//\t{\tpointerhash,\tpointerequal,\tpointerprint,\tpointercopy\t},  // 2
-	{\tmemhash,\tmemequal,\tmemprint,\tmemcopy\t},  // 2 - treat pointers as ints
-	{\tmemhash,\tmemequal,\tmemprint,\tmemcopy\t},  // 3 - treat interfaces as memory
+algarray[] =
+{
+[ASIMP]		{ memhash, memequal, memprint, memcopy },
+[ASTRING]	{ strhash, strequal, strprint, strcopy },
+[APTR]		{ memhash, memequal, memprint, memcopy },	// TODO: ptr routines
+[AINTER]	{ memhash, memequal, memprint, memcopy },	// TODO: interface routines
+[ASTRUCT]	{ memhash, memequal, memprint, memcopy },	// TODO: what goes here?
+[AARRAY]	{ memhash, memequal, memprint, memcopy },	// TODO: what goes here?
 };

algarray は、Goのランタイムが特定の型に対して実行する操作（ハッシュ、等価性比較、出力、コピー）の関数ポインタを格納するテーブルです。この変更では、ASTRUCT と AARRAY のエントリが追加され、それぞれ memhash, memequal, memprint, memcopy といった汎用的なメモリ操作関数が割り当てられています。これは、スライスや構造体のハッシュや比較が、そのメモリ内容を直接操作することで行われることを示唆しています。コメントにある TODO は、将来的にこれらの型に対するより最適化されたルーチンが実装される可能性を示しています。

src/runtime/chan.c の sys·newchan 関数変更

--- a/src/runtime/chan.c
+++ b/src/runtime/chan.c
@@ -86,14 +86,17 @@ sys·newchan(uint32 elemsize, uint32 elemalg, uint32 hint,
 	Hchan *c;
 	int32 i;
 
-\tif(elemalg >= nelem(algarray)) {\n-\t\tprints(\"0<=\");\n-\t\tsys·printint(elemalg);\n-\t\tprints(\"<\");\n-\t\tsys·printint(nelem(algarray));\n-\t\tprints(\"\\n\");\n-\n-\t\tthrow(\"sys·newchan: elem algorithm out of range\");\n+\tswitch(elemalg){\n+\tcase ASIMP:\n+\tcase ASTRING:\n+\tcase APTR:\n+\tcase AINTER:\n+\tcase AARRAY:\n+\tcase ASTRUCT:\n+\t\tbreak;\n+\tdefault:\n+\t\tprintf(\"chan(alg=%d)\\n\", elemalg);\n+\t\tthrow(\"sys·newchan: unsupported channel element type\");
 	}
 
 	c = mal(sizeof(*c));

sys·newchan は新しいチャネルを作成するランタイム関数です。以前は elemalg (要素の型アルゴリズム) の値が algarray の範囲内にあるかどうかの単純な数値チェックが行われていました。この変更により、switch 文が導入され、ASIMP, ASTRING, APTR, AINTER に加えて AARRAY と ASTRUCT が明示的に許可されるようになりました。これにより、チャネルがスライスや構造体を要素として扱えるようになります。

src/runtime/hashmap.c の sys·newmap 関数変更

--- a/src/runtime/hashmap.c
+++ b/src/runtime/hashmap.c
@@ -663,19 +663,30 @@ sys·newmap(uint32 keysize, uint32 valsize,
 {
 	Hmap *h;
 
-\tif(keyalg >= 4 ||\n-\t   valalg >= 4) {\n-\t\tprints(\"0<=\");\n-\t\tsys·printint(keyalg);\n-\t\tprints(\"<\");\n-\t\tsys·printint(nelem(algarray));\n-\t\tprints(\"\\n0<=\");\n-\t\tsys·printint(valalg);\n-\t\tprints(\"<\");\n-\t\tsys·printint(nelem(algarray));\n-\t\tprints(\"\\n\");\n-\n-\t\tthrow(\"sys·newmap: key/val algorithm out of range\");\n+\tswitch(keyalg) {\n+\tcase ASIMP:\n+\tcase ASTRING:\n+\tcase APTR:\n+\tcase AINTER:\n+\tcase AARRAY:\n+\tcase ASTRUCT:\n+\t\tbreak;\n+\tdefault:\n+\t\tprintf(\"map(keyalg=%d)\\n\", keyalg);\n+\t\tthrow(\"sys·newmap: unsupported map key type\");
+\t}\n+\n+\tswitch(valalg) {\n+\tcase ASIMP:\n+\tcase ASTRING:\n+\tcase APTR:\n+\tcase AINTER:\n+\tcase AARRAY:\n+\tcase ASTRUCT:\n+\t\tbreak;\n+\tdefault:\n+\t\tprintf(\"map(valalg=%d)\\n\", valalg);\n+\t\tthrow(\"sys·newmap: unsupported map value type\");
 	}
 
 	h = mal(sizeof(*h));

sys·newmap は新しいマップを作成するランタイム関数です。チャネルの場合と同様に、キーの型アルゴリズム (keyalg) と値の型アルゴリズム (valalg) のチェックが switch 文に置き換えられ、AARRAY と ASTRUCT が有効な型として許可されるようになりました。これにより、マップがスライスや構造体をキーまたは値として扱えるようになります。特に、スライスや構造体をマップのキーとして使用できるようになったことは、これらの型がハッシュ可能かつ比較可能になったことを意味します。

test/bigalg.go の追加

// $G $D/$F.go && $L $F.$A && ./$A.out

// Copyright 2009 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.

package main

import (
	"os";
	"fmt";
)

type T struct {
	a float64;
	b int64;
	c string;
	d byte;
}

var a = []int{ 1, 2, 3 }
var NIL []int;

func arraycmptest() {
	a1 := a;
	if NIL != nil {
		println("fail1:", NIL, "!= nil");
	}
	if nil != NIL {
		println("fail2: nil !=", NIL);
	}
	if a == nil || nil == a {
		println("fail3:", a, "== nil");
	}
	if a == NIL || NIL == a {
		println("fail4:", a, "==", NIL);
	}
	if a != a {
		println("fail5:", a, "!=", a);
	}
	if a1 != a {
		println("fail6:", a1, "!=", a);
	}
}

var t = T{1.5, 123, "hello", 255}
var mt = new(map[int]T)
var ma = new(map[int][]int)

func maptest() {
	mt[0] = t;
	t1 := mt[0];
	if t1.a != t.a || t1.b != t.b || t1.c != t.c || t1.d != t.d {
		println("fail: map val struct", t1.a, t1.b, t1.c, t1.d);
	}

	ma[1] = a;
	a1 := ma[1];
	if a1 != a {
		println("fail: map val array", a, a1);
	}
}

var mt1 = new(map[T]int)
var ma1 = new(map[[]int] int)

func maptest2() {
	mt1[t] = 123;
	t1 := t;
	val, ok := mt1[t1];
	if val != 123 || !ok {
		println("fail: map key struct", val, ok);
	}

	ma1[a] = 345;
	a1 := a;
	val, ok = ma1[a1];
	if val != 345 || !ok {
		panic("map key array", val, ok);
	}
}

var ct = new(chan T)
var ca = new(chan []int)

func send() {
	ct <- t;
	ca <- a;
}

func chantest() {
	go send();

	t1 := <-ct;
	if t1.a != t.a || t1.b != t.b || t1.c != t.c || t1.d != t.d {
		println("fail: chan struct", t1.a, t1.b, t1.c, t1.d);
	}

	a1 := <-ca;
	if a1 != a {
		println("fail: chan array", a, a1);
	}
}

func main() {
	arraycmptest();
	maptest();
	maptest2();
	chantest();
}

このテストファイルは、新しい機能が期待通りに動作することを検証するためのものです。特に、構造体 T とスライス []int を定義し、これらをマップのキー/値、チャネルの要素として使用するシナリオを網羅しています。maptest2 でスライスをマップのキーとして使用している点に注目してください。これは、スライスが比較可能になったことを示しています。

関連リンク

• Go言語の公式ドキュメント: https://go.dev/doc/
• Go言語のチャネルについて: https://go.dev/tour/concurrency/2
• Go言語のマップについて: https://go.dev/tour/moretypes/19
• Go言語のスライスについて: https://go.dev/tour/moretypes/7

参考にした情報源リンク

• Go言語のソースコード (GitHub): https://github.com/golang/go
• Go言語の初期のコミット履歴 (GitHub): https://github.com/golang/go/commits/master?after=2009-01-01+00%3A00%3A00+-0800 (このコミットは2008年のものなので、履歴を遡る必要があります)
• Go言語の内部実装に関する議論やドキュメント (Goのメーリングリストやデザインドキュメントなど、当時の情報源)
  • Goの初期のデザインドキュメントやメーリングリストのアーカイブは、Goの進化を理解する上で貴重な情報源となります。例えば、golang-dev メーリングリストのアーカイブなどを参照すると、当時の議論の背景をより深く理解できます。
  • Goの内部構造に関するブログ記事や解説記事 (例: "Go's Runtime: An Introduction", "Understanding Go's Type System")
    • これらの情報は特定のURLを挙げるのが難しいですが、Goのランタイムやコンパイラの内部動作を解説している記事は多数存在します。
• Goのソースコード内のコメントやREADMEファイル。
• Goのテストスイート (test/ ディレクトリ内のファイル)。
• Goのコンパイラとランタイムの設計に関する論文や発表資料。
• Goのコミットメッセージ自体が、変更の意図を理解するための重要な情報源です。
• GoのIssue Tracker (当時のバグ報告や機能要望)。
• Goの初期のバージョン管理システム (Mercurial) の履歴。
  • Goは当初Mercurialで管理されており、GitHubへの移行は後に行われました。当時のMercurialリポジトリの履歴も参照すると、より詳細な情報が得られる場合があります。
  • https://go.googlesource.com/go (Goの公式Gitリポジトリ)
  • https://go.googlesource.com/go/+log/master/src/runtime (ランタイムのログ)
  • https://go.googlesource.com/go/+log/master/src/cmd/gc (コンパイラのログ)
  • https://go.googlesource.com/go/+log/master/test (テストのログ)
  • これらのリンクから、コミットハッシュ eee50ae1ac25dec3047e111fd62ee1f83e874e26 を検索することで、当時の詳細な変更内容や関連するコミットを見つけることができます。

この解説は、提供されたコミット情報とGo言語の一般的な知識に基づいて作成されました。より深い理解のためには、Goのソースコードを直接読み解き、当時のデザインドキュメントやメーリングリストの議論を参照することが推奨されます。