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

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

このコミットは、Go言語にrangeステートメントを導入するものです。rangeステートメントは、配列、スライス、マップなどのコレクション型を反復処理するための強力な構文を提供します。この変更により、Go言語の表現力が向上し、より簡潔でイディオマティックなコード記述が可能になります。特に、コンパイラ（gc）とランタイム（src/runtime/hashmap.c）の両方にわたる広範な変更が含まれており、rangeのセマンティクスをサポートするための基盤が構築されています。

コミット

commit 26b357ca5b4555225803668a88c6d7145eeab59b
Author: Ken Thompson <ken@golang.org>
Date:   Fri Dec 5 18:24:05 2008 -0800

    range statement
    
    R=r
    OCL=20667
    CL=20667
---
 src/cmd/gc/dcl.c       |   2 +-\
 src/cmd/gc/go.h        |  28 ++++++++++++\
 src/cmd/gc/go.y        |  48 +++++----------------
 src/cmd/gc/sys.go      |   8 +++-\
 src/cmd/gc/sysimport.c |   6 ++-\
 src/cmd/gc/walk.c      | 104 +++++++++++++++++++++++++++++++++++++++++++++
 src/runtime/hashmap.c  |  85 ++++++++++++++++++++++++++++++++++++-\
 src/runtime/hashmap.h  |  25 +++++------
 test/ken/range.go      | 113 +++++++++++++++++++++++++++++++++++++++++++++++++
 9 files changed, 364 insertions(+), 55 deletions(-)

diff --git a/src/cmd/gc/dcl.c b/src/cmd/gc/dcl.c
index 13503c5681..a7882e9add 100644
--- a/src/cmd/gc/dcl.c
+++ b/src/cmd/gc/dcl.c
@@ -1263,7 +1263,7 @@ void
 constiter(Node *vv, Type *t, Node *cc)
 {
 	Iter viter, citer;
-	Node *v, *c, *a;
+	Node *v, *c;
 
 	if(cc == N)
 		cc = lastconst;
diff --git a/src/cmd/gc/go.h b/src/cmd/gc/go.h
index 694b368446..b8429c3bd0 100644
--- a/src/cmd/gc/go.h
+++ b/src/cmd/gc/go.h
@@ -74,6 +74,33 @@ struct	Array
 	uchar	b;		// actual array - may not be contig
 };
 
+/*
+ * note this is the runtime representation
+ * of hashmap iterator. it is probably
+ * insafe to use it this way, but it puts
+ * all the changes in one place.
+ * only flag is referenced from go.
+ * actual placement does not matter as long
+ * as the size is >= actual size.
+ */
+typedef	struct	Hiter	Hiter;
+struct	Hiter
+{
+	uchar	data[8];		// return val from next
+	int32	elemsize;		// size of elements in table */
+	int32	changes;		// number of changes observed last time */
+	int32	i;			// stack pointer in subtable_state */
+	uchar	last[8];		// last hash value returned */
+	uchar	h[8];			// the hash table */
+	struct
+	{
+		uchar	sub[8];		// pointer into subtable */
+		uchar	start[8];	// pointer into start of subtable */
+		uchar	end[8];		// pointer into end of subtable */
+		uchar	pad[8];
+	} sub[4];
+};
+
 enum
 {
 	Mpscale	= 29,		// safely smaller than bits in a long
@@ -779,6 +806,7 @@ int
 isandss(Type*, Node*);
 Node*	convas(Node*);
 void	arrayconv(Type*, Node*);
 Node*	colas(Node*, Node*);
+Node*	dorange(Node*, Node*, Node*, int);
 Node*	reorder1(Node*);
 Node*	reorder2(Node*);
 Node*	reorder3(Node*);
diff --git a/src/cmd/gc/go.y b/src/cmd/gc/go.y
index 409838901e..2944d55101 100644
--- a/src/cmd/gc/go.y
+++ b/src/cmd/gc/go.y
@@ -51,8 +51,7 @@
 %type	<node>		stmt_list_r Astmt_list_r Bstmt_list_r
 %type	<node>		Astmt Bstmt
 %type	<node>		for_stmt for_body for_header
-%type	<node>		if_stmt if_body if_header
-%type	<node>		range_header range_body range_stmt select_stmt
+%type	<node>		if_stmt if_body if_header select_stmt
 %type	<node>		simple_stmt osimple_stmt semi_stmt
 %type	<node>		expr uexpr pexpr expr_list oexpr oexpr_list expr_list_r
 %type	<node>		exprsym3_list_r exprsym3
@@ -478,11 +477,6 @@ complex_stmt:
 		popdcl();
 		$$ = $2;
 	}
-|\tLRANGE range_stmt
-	{
-		popdcl();
-		$$ = $2;
-	}
 |\tLCASE expr_list ':'
 	{
 		// will be converted to OCASE
@@ -578,12 +572,20 @@ for_header:
 		$$->ntest = $1;
 		$$->nincr = N;
 	}
+|\tnew_name ':' new_name LRANGE expr
+	{
+		$$ = dorange($1, $3, $5, 1);
+	}
+|\tnew_name LRANGE expr
+	{
+		$$ = dorange($1, N, $3, 1);
+	}
 
 for_body:
 	for_header compound_stmt
 	{
 		$$ = $1;
-\t\t$$->nbody = $2;\n+\t\t$$->nbody = list($$->nbody, $2);\
 	}
 
 for_stmt:
@@ -625,36 +627,6 @@ if_stmt:
 		$$ = $2;
 	}
 
-range_header:
-	new_name LCOLAS expr
-	{
-		$$ = N;
-	}
-|\tnew_name ',' new_name LCOLAS expr
-	{
-		$$ = N;
-	}
-|\tnew_name ',' new_name '=' expr
-	{
-		yyerror("range statement only allows := assignment");
-		$$ = N;
-	}
-
-range_body:
-	range_header compound_stmt
-	{
-		$$ = $1;
-		$$->nbody = $2;
-	}
-
-range_stmt:
-	{
-		markdcl();
-	} range_body
-	{
-		$$ = $2;
-	}
-
 select_stmt:
 	{
 		markdcl();
diff --git a/src/cmd/gc/sys.go b/src/cmd/gc/sys.go
index 775b83e51e..bc91beb043 100644
--- a/src/cmd/gc/sys.go
+++ b/src/cmd/gc/sys.go
@@ -51,8 +51,8 @@ export func	Inf(int) float64;			// return signed Inf
 export func	NaN() float64;				// return a NaN
 export func	float32bits(float32) uint32;		// raw bits
 export func	float64bits(float64) uint64;		// raw bits
-export func	float32frombits(uint32) float32;		// raw bits
-export func	float64frombits(uint64) float64;		// raw bits
+export func	float32frombits(uint32) float32;	// raw bits
+export func	float64frombits(uint64) float64;	// raw bits
 
 export func	newmap(keysize int, valsize int,
 			keyalg int, valalg int,
@@ -61,6 +61,10 @@ export func	mapaccess1(hmap *map[any]any, key any) (val any);
 export func	mapaccess2(hmap *map[any]any, key any) (val any, pres bool);
 export func	mapassign1(hmap *map[any]any, key any, val any);
 export func	mapassign2(hmap *map[any]any, key any, val any, pres bool);
+export func	mapiterinit(hmap *map[any]any, hiter *any);
+export func	mapiternext(hiter *any);
+export func	mapiter1(hiter *any) (key any);
+export func	mapiter2(hiter *any) (key any, val any);
 
 export func	newchan(elemsize int, elemalg int, hint int) (hchan *chan any);
 export func	chanrecv1(hchan *chan any) (elem any);
diff --git a/src/cmd/gc/sysimport.c b/src/cmd/gc/sysimport.c
index 3a3dbcedc0..56b6b8aca6 100644
--- a/src/cmd/gc/sysimport.c
+++ b/src/cmd/gc/sysimport.c
@@ -1,4 +1,4 @@
-char *sysimport =\n+char *sysimport = \
 \t\"package sys\\n\"\
 \t\"export func sys.mal (? int32) (? *any)\\n\"\
 \t\"export func sys.breakpoint ()\\n\"\
@@ -48,6 +48,10 @@ char *sysimport =\
 \t\"export func sys.mapaccess2 (hmap *map[any] any, key any) (val any, pres bool)\\n\"\
 \t\"export func sys.mapassign1 (hmap *map[any] any, key any, val any)\\n\"\
 \t\"export func sys.mapassign2 (hmap *map[any] any, key any, val any, pres bool)\\n\"\
+\t\"export func sys.mapiterinit (hmap *map[any] any, hiter *any)\\n\"\
+\t\"export func sys.mapiternext (hiter *any)\\n\"\
+\t\"export func sys.mapiter1 (hiter *any) (key any)\\n\"\
+\t\"export func sys.mapiter2 (hiter *any) (key any, val any)\\n\"\
 \t\"export func sys.newchan (elemsize int, elemalg int, hint int) (hchan *chan any)\\n\"\
 \t\"export func sys.chanrecv1 (hchan *chan any) (elem any)\\n\"\
 \t\"export func sys.chanrecv2 (hchan *chan any) (elem any, pres bool)\\n\"\
diff --git a/src/cmd/gc/walk.c b/src/cmd/gc/walk.c
index da5917aa7f..68cf9123de 100644
--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -3033,6 +3033,110 @@ badt:
 	return nl;
 }
 
+Node*
+dorange(Node *k, Node *v, Node *m, int local)
+{
+	Node *n, *hk, *on, *r, *a;
+	Type *t, *th;
+
+	if(!local)
+		fatal("only local varables now");
+
+	n = nod(OFOR, N, N);
+
+	walktype(m, Erv);
+	t = m->type;
+	if(t == T)
+		goto out;
+	if(t->etype == TARRAY)
+		goto ary;
+	if(isptrto(t, TARRAY)) {
+		t = t->type;
+		goto ary;
+	}
+	if(t->etype == TMAP)
+		goto map;
+	if(isptrto(t, TMAP)) {
+		t = t->type;
+		goto map;
+	}
+
+	yyerror("range must be over map/array");
+	goto out;
+
+ary:
+	hk = nod(OXXX, N, N);		// hidden key
+	tempname(hk, types[TINT]);	// maybe TINT32
+
+	n->ninit = nod(OAS, hk, literal(0));
+	n->ntest = nod(OLT, hk, nod(OLEN, m, N));
+	n->nincr = nod(OASOP, hk, literal(1));
+	n->nincr->etype = OADD;
+
+	k = old2new(k, hk->type);
+	n->nbody = nod(OAS, k, hk);
+
+	if(v != N) {
+		v = old2new(v, t->type);
+		n->nbody = list(n->nbody,
+			nod(OAS, v, nod(OINDEX, m, hk)) );
+	}
+	goto out;
+
+map:
+	th = typ(TARRAY);
+	th->type = ptrto(types[TUINT8]);
+	th->bound = (sizeof(struct Hiter) + types[tptr]->width - 1) /
+			types[tptr]->width;
+	hk = nod(OXXX, N, N);		// hidden iterator
+	tempname(hk, th);		// hashmap hash_iter
+
+	on = syslook("mapiterinit", 1);
+	argtype(on, t->down);
+	argtype(on, t->type);
+	argtype(on, th);
+	r = nod(OADDR, hk, N);
+	r = list(m, r);
+	r = nod(OCALL, on, r);
+	n->ninit = r;
+
+	r = nod(OINDEX, hk, literal(0));
+	a = nod(OLITERAL, N, N);
+	a->val.ctype = CTNIL;
+	r = nod(ONE, r, a);
+	n->ntest = r;
+
+	on = syslook("mapiternext", 1);
+	argtype(on, th);
+	r = nod(OADDR, hk, N);
+	r = nod(OCALL, on, r);
+	n->nincr = r;
+
+	k = old2new(k, t->down);
+	if(v == N) {
+		on = syslook("mapiter1", 1);
+		argtype(on, th);
+		argtype(on, t->down);
+		r = nod(OADDR, hk, N);
+		r = nod(OCALL, on, r);
+		n->nbody = nod(OAS, k, r);
+		goto out;
+	}
+	v = old2new(v, t->type);
+	on = syslook("mapiter2", 1);
+	argtype(on, th);
+	argtype(on, t->down);
+	argtype(on, t->type);
+	r = nod(OADDR, hk, N);
+	r = nod(OCALL, on, r);
+	n->nbody = nod(OAS, nod(OLIST, k, v), r);
+
+	goto out;
+
+out:
+	return n;
+}
+
 /*
  * from ascompat[te]
  * evaluating actual function arguments.
diff --git a/src/runtime/hashmap.c b/src/runtime/hashmap.c
index b70f9e952b..83fe06c665 100644
--- a/src/runtime/hashmap.c
+++ b/src/runtime/hashmap.c
@@ -649,7 +649,7 @@ donothing(uint32 s, void *a, void *b)
 	USED(b);
 }\n 
-typedef	struct hash	Hmap;\n+typedef	struct	hash	Hmap;\
 static	int32	debug	= 0;
 
 // newmap(keysize uint32, valsize uint32,
@@ -860,3 +860,86 @@ sys·mapassign2(Hmap *h, ...)
 		prints("\\n");
 	}
 }\n+\n+// mapiterinit(hmap *map[any]any, hiter *any);\n+void\n+sys·mapiterinit(Hmap *h, struct hash_iter *it)\n+{\n+\thash_iter_init(h, it);\n+\tit->data = hash_next(it);\n+\tif(debug) {\n+\t\tprints(\"sys·mapiterinit: map=\");\n+\t\tsys·printpointer(h);\n+\t\tprints(\"; iter=\");\n+\t\tsys·printpointer(it);\n+\t\tprints(\"; data=\");\n+\t\tsys·printpointer(it->data);\n+\t\tprints(\"\\n\");\n+\t}\n+}\n+\n+// mapiternext(hiter *any);\n+void\n+sys·mapiternext(struct hash_iter *it)\n+{\n+\tit->data = hash_next(it);\n+\tif(debug) {\n+\t\tprints(\"sys·mapiternext: iter=\");\n+\t\tsys·printpointer(it);\n+\t\tprints(\"; data=\");\n+\t\tsys·printpointer(it->data);\n+\t\tprints(\"\\n\");\t}\n+}\n+\n+// mapiter1(hiter *any) (key any);\n+void\n+sys·mapiter1(struct hash_iter *it, ...)\n+{\n+\tHmap *h;\n+\tbyte *ak, *res;\n+\n+\th = it->h;\n+\tak = (byte*)&it + h->ko;\n+\n+\tres = it->data;\n+\tif(res == nil)\n+\t\tthrow(\"sys·mapiter2: key:val nil pointer\");\n+\n+\th->keyalg->copy(h->keysize, ak, res);\n+\n+\tif(debug) {\n+\t\tprints(\"mapiter2: iter=\");\n+\t\tsys·printpointer(it);\n+\t\tprints(\"; map=\");\n+\t\tsys·printpointer(h);\n+\t\tprints(\"\\n\");\n+\t}\n+}\n+\n+// mapiter2(hiter *any) (key any, val any);\n+void\n+sys·mapiter2(struct hash_iter *it, ...)\n+{\n+\tHmap *h;\n+\tbyte *ak, *av, *res;\n+\n+\th = it->h;\n+\tak = (byte*)&it + h->ko;\n+\tav = (byte*)&it + h->vo;\n+\n+\tres = it->data;\n+\tif(res == nil)\n+\t\tthrow(\"sys·mapiter2: key:val nil pointer\");\n+\n+\th->keyalg->copy(h->keysize, ak, res);\n+\th->valalg->copy(h->valsize, av, res+h->keysize);\n+\n+\tif(debug) {\n+\t\tprints(\"mapiter2: iter=\");\n+\t\tsys·printpointer(it);\n+\t\tprints(\"; map=\");\n+\t\tsys·printpointer(h);\n+\t\tprints(\"\\n\");\n+\t}\n+}\ndiff --git a/src/runtime/hashmap.h b/src/runtime/hashmap.h
index 04bb732699..970e9e12e6 100644
--- a/src/runtime/hashmap.h
+++ b/src/runtime/hashmap.h
@@ -72,24 +72,25 @@
 #define	memcpy(a,b,c)\tmcpy((byte*)(a),(byte*)(b),(uint32)(c))\
 #define	assert(a)\tif(!(a)) throw("assert")
 
-struct hash;	    /* opaque */\
-struct hash_subtable;   /* opaque */\
-struct hash_entry;      /* opaque */\
+struct hash;		/* opaque */\
+struct hash_subtable;	/* opaque */\
+struct hash_entry;	/* opaque */
 
 typedef	uint64 uintptr_t;
 typedef uintptr_t hash_hash_t;
 
 struct hash_iter {\
-\tint32 elemsize;	 /* size of elements in table */\
-\tint32 changes;	  /* number of changes observed last time */\
-\tint32 i;		/* stack pointer in subtable_state */\
-\thash_hash_t last_hash; /* last hash value returned */\
-\tstruct hash *h;       /* the hash table */\
+\tuint8*\tdata;		/* returned from next */\
+\tint32\telemsize;	/* size of elements in table */\
+\tint32\tchanges;	/* number of changes observed last time */\
+\tint32\ti;		/* stack pointer in subtable_state */\
+\thash_hash_t last_hash;	/* last hash value returned */\
+\tstruct hash *h;		/* the hash table */
 \tstruct hash_iter_sub {\
-\t\tstruct hash_entry *e;    /* pointer into subtable */\
-\t\tstruct hash_entry *start;  /* start of subtable */\
-\t\tstruct hash_entry *end;  /* end of subtable */\
-\t} subtable_state[16];   /* Should be large enough unless the hashing is\
+\t\tstruct hash_entry *e;		/* pointer into subtable */\
+\t\tstruct hash_entry *start;	/* start of subtable */
+\t\tstruct hash_entry *end;		/* end of subtable */
+\t} subtable_state[4];	/* Should be large enough unless the hashing is
  \t\t\t\t   so bad that many distinct data values hash\
  \t\t\t\t   to the same hash value.  */
 };
diff --git a/test/ken/range.go b/test/ken/range.go
new file mode 100644
index 0000000000..c8a646dd30
--- /dev/null
+++ b/test/ken/range.go
@@ -0,0 +1,113 @@
+// $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
+
+const	size	= 16;
+
+var	a	[size]byte;
+var	p	*[]byte;
+var	m	*map[int]byte;
+
+func
+f(k int) byte
+{
+	return byte(k*10007 % size);
+}
+
+func
+init()
+{
+	p = new([]byte, size);
+	m = new(map[int]byte);
+	for k:=0; k<size; k++ {
+		v := f(k);
+		a[k] = v;
+		p[k] = v;
+		m[k] = v;
+	}
+}
+
+func
+main()
+{
+	var i int;
+
+	/*
+	 * key only
+	 */
+	i = 0;
+	for k range a {
+		v := a[k];
+		if v != f(k) {
+			panicln("key array range", k, v, a[k]);
+		}
+		i++;
+	}
+	if i != size {
+		panicln("key array size", i);
+	}
+
+	i = 0;
+	for k range p {
+		v := p[k];
+		if v != f(k) {
+			panicln("key pointer range", k, v, p[k]);
+		}
+		i++;
+	}
+	if i != size {
+		panicln("key pointer size", i);
+	}
+
+	i = 0;
+	for k range m {
+		v := m[k];
+		if v != f(k) {
+			panicln("key map range", k, v, m[k]);
+		}
+		i++;
+	}
+	if i != size {
+		panicln("key map size", i);
+	}
+
+	/*
+	 * key:value
+	 */
+	i = 0;
+	for k:v range a {
+		if v != f(k) {
+			panicln("key:value array range", k, v, a[k]);
+		}
+		i++;
+	}
+	if i != size {
+		panicln("key:value array size", i);
+	}
+
+	i = 0;
+	for k:v range p {
+		if v != f(k) {
+			panicln("key:value pointer range", k, v, p[k]);
+		}
+		i++;
+	}
+	if i != size {
+		panicln("key:value pointer size", i);
+	}
+
+	i = 0;
+	for k:v range m {
+		if v != f(k) {
+			panicln("key:value map range", k, v, m[k]);
+		}
+		i++;
+	}
+	if i != size {
+		panicln("key:value map size", i);
+	}\n}

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

https://github.com/golang/go/commit/26b357ca5b4555225803668a88c6d7145eeab59b

元コミット内容

    range statement
    
    R=r
    OCL=20667
    CL=20667

変更の背景

このコミットは、Go言語の初期開発段階において、コレクション（配列、スライス、マップ）の要素を効率的かつイディオマティックに反復処理するためのメカニズムとしてrangeステートメントを導入したものです。Go言語は設計当初から、シンプルさ、効率性、並行処理のサポートを重視していました。従来のC言語のようなforループだけでは、コレクションの反復処理が冗長になりがちであり、特にマップのような順序が保証されないデータ構造では、イテレータの管理が複雑になる可能性がありました。

rangeステートメントの導入は、以下の目的を達成するために不可欠でした。

  1. コードの簡潔性向上: コレクションの要素にアクセスするためのボイラープレートコードを削減し、より読みやすく、書きやすいコードを可能にする。
  2. イディオマティックな反復処理: Go言語の設計思想に合致した、自然で直感的な反復処理のパターンを提供する。
  3. 安全性と堅牢性: マップの同時変更に対する安全なイテレーションなど、特定のデータ構造における反復処理の複雑さを抽象化し、開発者が安全に利用できるようにする。
  4. パフォーマンスの最適化: コンパイラとランタイムがrangeステートメントを最適化し、効率的なコードを生成できるようにする。

このコミットは、Go言語がまだ公開される前の2008年12月に行われており、言語の基本的な構文とセマンティクスが形成されていく過程の一部として、rangeがその重要な要素として位置づけられたことを示しています。

前提知識の解説

このコミットの技術的詳細を理解するためには、以下の前提知識が役立ちます。

  • Go言語の基本的な構文とデータ型:
    • 配列 (Arrays): 固定長で同じ型の要素を格納するデータ構造。
    • スライス (Slices): 配列のセグメントを参照する動的なデータ構造。Go言語で最も一般的に使用されるシーケンス型。
    • マップ (Maps): キーと値のペアを格納するハッシュテーブルベースのデータ構造。キーは一意であり、順序は保証されない。
    • for ループ: Go言語における基本的な繰り返し構文。
  • コンパイラの基本:
    • 字句解析 (Lexical Analysis): ソースコードをトークンに分解するプロセス。
    • 構文解析 (Syntax Analysis): トークンのストリームを解析し、抽象構文木 (AST) を構築するプロセス。Yacc/Bisonのようなパーサジェネレータが使用されることが多い。
    • 抽象構文木 (Abstract Syntax Tree - AST): ソースコードの構造を木構造で表現したもの。コンパイラの各フェーズでこのASTが変換されていく。
    • 中間表現 (Intermediate Representation - IR): ソースコードを機械語に変換する途中で使用される、より抽象的な表現。
    • コード生成 (Code Generation): 中間表現から最終的な機械語コードを生成するプロセス。
  • Goコンパイラ (gc) の構造:
    • Go言語の初期コンパイラはgcと呼ばれ、C言語で書かれていました（後にGo言語自身で書き直されます）。
    • src/cmd/gc/go.y: Go言語の構文を定義するYaccファイル。ここで新しい構文が追加されると、パーサがその構文を認識できるようになります。
    • src/cmd/gc/walk.c: ASTを走査し、高レベルの構文を低レベルの操作に変換する「ウォーカー」の役割を果たすファイル。ここでrangeステートメントがどのように内部的なforループやランタイム関数呼び出しに変換されるかが定義されます。
    • src/cmd/gc/go.h: コンパイラ内部で使用されるデータ構造や関数の宣言を含むヘッダファイル。
  • Goランタイム (Runtime):
    • Goプログラムの実行をサポートする低レベルのコード。ガベージコレクション、スケジューラ、プリミティブなデータ構造（マップ、チャネルなど）の実装が含まれる。
    • src/runtime/hashmap.c, src/runtime/hashmap.h: Goのマップの実装と、そのイテレーションに関連する関数が含まれる。

技術的詳細

このコミットにおけるrangeステートメントの実装は、コンパイラとランタイムの密接な連携によって実現されています。

1. 構文解析 (src/cmd/gc/go.y)

go.yファイルは、Go言語の文法を定義するYacc（Yet Another Compiler Compiler）の入力ファイルです。このコミットでは、for_headerプロダクションにrangeステートメントの新しい構文が追加されています。

  • new_name ':' new_name LRANGE expr: for k:v range collection の形式に対応します。kとvはそれぞれキーと値の変数、collectionは反復対象のコレクションです。
  • new_name LRANGE expr: for k range collection の形式に対応します。キーのみを反復し、値は無視されます。

これらの構文が認識されると、dorangeという新しいコンパイラ関数が呼び出され、rangeステートメントのセマンティクスが処理されます。

2. AST変換とコード生成 (src/cmd/gc/walk.c)

src/cmd/gc/walk.c内のdorange関数が、rangeステートメントの核心的な変換ロジックを担っています。この関数は、高レベルのrange構文を、より低レベルのforループとランタイム関数呼び出しの組み合わせに変換します。

  • コレクションの型チェック: dorange関数は、rangeの対象が配列、スライス、またはマップであることを確認します。それ以外の型の場合、コンパイルエラー (yyerror) を発生させます。
  • 配列/スライスの場合:
    • 隠し変数 (hk) を導入し、これをインデックスとして使用します。
    • 通常のforループに変換されます。
      • 初期化 (ninit): hk = 0
      • 条件 (ntest): hk < len(collection)
      • インクリメント (nincr): hk++
    • ループ本体 (nbody):
      • キー変数 (k) にhk（インデックス）を代入します。
      • 値変数 (v) が存在する場合、collection[hk]（要素）を代入します。
  • マップの場合:
    • マップのイテレーションは、配列/スライスよりも複雑です。Goのマップは順序が保証されないため、ランタイムのサポートが必要です。
    • 隠しイテレータ変数 (hk) を導入します。この変数は、src/cmd/gc/go.hで定義されたHiter構造体（後述）の型を持ちます。
    • ランタイム関数 (mapiterinit, mapiternext, mapiter1, mapiter2) を利用してイテレーションを制御します。
      • 初期化 (ninit): mapiterinit(map, &iterator) を呼び出し、イテレータを初期化し、最初の要素を取得します。
      • 条件 (ntest): イテレータがまだ要素を持っているか (iterator.data != nil) をチェックします。
      • インクリメント (nincr): mapiternext(&iterator) を呼び出し、次の要素に進みます。
      • ループ本体 (nbody):
        • キーのみの場合 (for k range m): mapiter1(&iterator) を呼び出してキーを取得し、kに代入します。
        • キーと値の場合 (for k:v range m): mapiter2(&iterator) を呼び出してキーと値の両方を取得し、それぞれkとvに代入します。

3. ランタイムサポート (src/runtime/hashmap.c, src/runtime/hashmap.h)

マップのrangeステートメントをサポートするために、ランタイムに新しい関数とデータ構造が追加されています。

  • Hiter 構造体 (src/cmd/gc/go.h, src/runtime/hashmap.h):
    • マップのイテレーション状態を保持するための構造体です。
    • data: 現在のキー/値ペアへのポインタ。
    • elemsize, changes, i, last_hash, h: イテレーションの内部状態を管理するためのフィールド。
    • subtable_state: ハッシュマップの内部構造を走査するためのスタックのようなもの。
    • この構造体は、コンパイラとランタイムの間でマップイテレータの状態を共有するために使用されます。
  • 新しいランタイム関数 (src/runtime/hashmap.c, src/cmd/gc/sys.go, src/cmd/gc/sysimport.c):
    • sys·mapiterinit(Hmap *h, struct hash_iter *it): マップイテレータを初期化し、最初の要素をit->dataに設定します。
    • sys·mapiternext(struct hash_iter *it): イテレータを次の要素に進め、it->dataを更新します。
    • sys·mapiter1(struct hash_iter *it) (key any): イテレータから現在のキーを取得します。
    • sys·mapiter2(struct hash_iter *it) (key any, val any): イテレータから現在のキーと値の両方を取得します。

これらのランタイム関数は、Goのマップの内部構造（ハッシュテーブル）を直接操作し、効率的なイテレーションを実現します。特に、マップのイテレーション中にマップが変更された場合の挙動（Goではランタイムパニックを引き起こす）も、Hiter構造体のchangesフィールドなどで追跡される可能性があります。

4. テスト (test/ken/range.go)

新しいrange.goテストファイルは、rangeステートメントの基本的な機能と、配列、ポインタ（スライス）、マップに対する挙動を検証します。キーのみのイテレーション (for k range ...) とキーと値のイテレーション (for k:v range ...) の両方がテストされており、rangeが正しく動作することを確認しています。

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

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

  • src/cmd/gc/go.h:
    • Hiter構造体の定義が追加されました。これは、マップのイテレーション状態を保持するためのランタイム表現です。
    • dorange関数のプロトタイプ宣言が追加されました。
  • src/cmd/gc/go.y:
    • for_headerプロダクションに、rangeステートメントの新しい構文ルールが追加されました。
      • new_name ':' new_name LRANGE expr (キーと値のイテレーション)
      • new_name LRANGE expr (キーのみのイテレーション)
    • これにより、パーサがrangeキーワードを認識し、対応するASTノードを生成できるようになります。
    • 既存のrange_header, range_body, range_stmtといった、おそらく初期のrange実装の名残と思われるプロダクションが削除されています。これは、rangeの構文がforループに統合されたことを示唆しています。
  • src/cmd/gc/sys.go:
    • mapiterinit, mapiternext, mapiter1, mapiter2といった、マップイテレーションのためのランタイム関数がexport funcとして宣言されました。これにより、Goのコードからこれらのランタイム関数を呼び出すことが可能になります。
  • src/cmd/gc/sysimport.c:
    • sysimport文字列に、上記でsys.goに追加されたマップイテレーション関連のランタイム関数の宣言が追加されました。これは、コンパイラがこれらのシステム関数を認識し、適切にリンクするために必要です。
  • src/cmd/gc/walk.c:
    • dorange関数が新規追加されました。この関数は、rangeステートメントのASTノードを受け取り、それを配列/スライスまたはマップのイテレーションに応じた低レベルのforループ構造とランタイム関数呼び出しに変換します。これはコンパイラのセマンティック分析と中間コード生成の重要な部分です。
  • src/runtime/hashmap.c:
    • sys·mapiterinit, sys·mapiternext, sys·mapiter1, sys·mapiter2といった、マップイテレーションの実際のロジックを実装するC関数が追加されました。これらの関数は、Hmap（ハッシュマップ）とhash_iter（イテレータ状態）の内部構造を直接操作します。
  • src/runtime/hashmap.h:
    • hash_iter構造体の定義が更新されました。特に、dataフィールドが追加され、subtable_stateのサイズが16から4に削減されています。これは、イテレータの内部表現が変更され、より効率的になったことを示唆しています。
  • test/ken/range.go:
    • rangeステートメントの動作を検証するための新しいテストファイルが追加されました。配列、ポインタ（スライス）、マップに対するキーのみ、およびキーと値のイテレーションのテストケースが含まれています。

コアとなるコードの解説

src/cmd/gc/walk.c の dorange 関数

dorange関数は、Goコンパイラのwalkフェーズで呼び出され、rangeステートメントのASTノードを処理します。この関数は、rangeの対象となるコレクションの型（配列/スライスまたはマップ）に基づいて、異なるコード生成パスを実行します。

Node*
dorange(Node *k, Node *v, Node *m, int local)
{
    Node *n, *hk, *on, *r, *a;
    Type *t, *th;

    // ... (エラーチェックと型判定) ...

    if(t->etype == TARRAY) // 配列/スライスの場合
        goto ary;
    if(isptrto(t, TARRAY)) { // 配列へのポインタ（スライス）の場合
        t = t->type;
        goto ary;
    }
    if(t->etype == TMAP) // マップの場合
        goto map;
    if(isptrto(t, TMAP)) { // マップへのポインタの場合
        t = t->type;
        goto map;
    }

    yyerror("range must be over map/array"); // サポートされていない型
    goto out;

ary: // 配列/スライスの処理
    hk = nod(OXXX, N, N);       // 隠し変数 (インデックス)
    tempname(hk, types[TINT]);  // int型として一時変数を生成

    n->ninit = nod(OAS, hk, literal(0)); // 初期化: hk = 0
    n->ntest = nod(OLT, hk, nod(OLEN, m, N)); // 条件: hk < len(m)
    n->nincr = nod(OASOP, hk, literal(1)); // インクリメント: hk++
    n->nincr->etype = OADD;

    k = old2new(k, hk->type); // キー変数にインデックスの型を適用
    n->nbody = nod(OAS, k, hk); // ループ本体: キー変数 = インデックス

    if(v != N) { // 値変数がある場合
        v = old2new(v, t->type); // 値変数に要素の型を適用
        n->nbody = list(n->nbody,
            nod(OAS, v, nod(OINDEX, m, hk)) ); // ループ本体: 値変数 = m[インデックス]
    }
    goto out;

map: // マップの処理
    th = typ(TARRAY); // Hiter構造体を表現するための型
    th->type = ptrto(types[TUINT8]);
    th->bound = (sizeof(struct Hiter) + types[tptr]->width - 1) /
            types[tptr]->width;
    hk = nod(OXXX, N, N);       // 隠し変数 (イテレータ)
    tempname(hk, th);       // Hiter型として一時変数を生成

    on = syslook("mapiterinit", 1); // ランタイム関数 mapiterinit を参照
    // ... (引数の型設定) ...
    r = nod(OADDR, hk, N); // イテレータのアドレス
    r = list(m, r); // map と イテレータのアドレスを引数リストに
    r = nod(OCALL, on, r); // mapiterinit(map, &iterator) の呼び出し
    n->ninit = r; // 初期化部に設定

    r = nod(OINDEX, hk, literal(0)); // イテレータの data フィールド (最初の8バイト)
    a = nod(OLITERAL, N, N);
    a->val.ctype = CTNIL;
    r = nod(ONE, r, a); // data != nil のチェック
    n->ntest = r; // 条件部に設定

    on = syslook("mapiternext", 1); // ランタイム関数 mapiternext を参照
    // ... (引数の型設定) ...
    r = nod(OADDR, hk, N); // イテレータのアドレス
    r = nod(OCALL, on, r); // mapiternext(&iterator) の呼び出し
    n->nincr = r; // インクリメント部に設定

    k = old2new(k, t->down); // キー変数にマップのキーの型を適用
    if(v == N) { // キーのみの場合
        on = syslook("mapiter1", 1); // ランタイム関数 mapiter1 を参照
        // ... (引数の型設定) ...
        r = nod(OADDR, hk, N); // イテレータのアドレス
        r = nod(OCALL, on, r); // mapiter1(&iterator) の呼び出し
        n->nbody = nod(OAS, k, r); // ループ本体: キー変数 = mapiter1(&iterator)
        goto out;
    }
    v = old2new(v, t->type); // 値変数にマップの値の型を適用
    on = syslook("mapiter2", 1); // ランタイム関数 mapiter2 を参照
    // ... (引数の型設定) ...
    r = nod(OADDR, hk, N); // イテレータのアドレス
    r = nod(OCALL, on, r); // mapiter2(&iterator) の呼び出し
    n->nbody = nod(OAS, nod(OLIST, k, v), r); // ループ本体: キー, 値 = mapiter2(&iterator)

out:
    return n;
}

このdorange関数は、Goのrangeステートメントがコンパイル時にどのように展開されるかを示しています。配列/スライスに対しては単純なインデックスベースのforループに、マップに対してはランタイムのイテレータ関数を呼び出す複雑なforループに変換されます。

src/runtime/hashmap.c のマップイテレーション関数

ランタイム側では、sys·mapiterinit, sys·mapiternext, sys·mapiter1, sys·mapiter2の4つの関数がマップのイテレーションを直接処理します。

  • sys·mapiterinit:
    • hash_iter_init(h, it)を呼び出してイテレータを初期化します。
    • it->data = hash_next(it)を呼び出して、最初のキー/値ペアへのポインタを取得し、イテレータのdataフィールドに格納します。
  • sys·mapiternext:
    • it->data = hash_next(it)を呼び出して、次のキー/値ペアへのポインタを取得し、it->dataを更新します。
  • sys·mapiter1:
    • it->dataがnilでないことを確認します（要素が存在することを確認）。
    • h->keyalg->copy(h->keysize, ak, res)を呼び出して、現在のキーをイテレータの内部バッファ（ak）にコピーします。このakは、コンパイラが生成したコードによってGoのキー変数にコピーされます。
  • sys·mapiter2:
    • it->dataがnilでないことを確認します。
    • h->keyalg->copy(h->keysize, ak, res)でキーをコピーし、h->valalg->copy(h->valsize, av, res+h->keysize)で値をコピーします。avは値の内部バッファです。

これらのランタイム関数は、Goのマップの内部表現に直接アクセスし、ハッシュテーブルの走査、キーと値の抽出、そしてイテレーション状態の管理を行います。これにより、Goのrangeステートメントが、背後で効率的かつ安全なマップの反復処理を実現しています。

関連リンク

  • Go言語のforステートメントに関する公式ドキュメント: https://go.dev/ref/spec#For_statements
  • Go言語のマップに関する公式ドキュメント: https://go.dev/ref/spec#Map_types
  • Go言語の初期の設計に関する議論やメーリングリストのアーカイブには、rangeステートメントの導入に関する詳細な背景情報が含まれている可能性があります。

参考にした情報源リンク

  • Go言語の公式ドキュメント (上記に記載)
  • Go言語のソースコード (このコミットのdiff)
  • Go言語の歴史に関する一般的な情報源 (例: Wikipedia, Goブログの初期の記事など)
  • コンパイラ設計に関する一般的な知識 (Yacc, AST, 中間表現など)