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

このコミットは、Goコンパイラのgc（Goコンパイラ自体を指す）における、マップのインデックス評価順序に関するバグ修正を扱っています。具体的には、多重代入（multiple assignments）において、マップのインデックスが他の要素の代入前に正しく評価されない問題を解決します。

コミット

commit 5ea52a4d91fd45a2a727a4f6cca96d08cb2960f2
Author: Daniel Morsing <daniel.morsing@gmail.com>
Date:   Sat Feb 2 12:39:04 2013 +0100

    cmg/gc: Fix evaluation order of map indexing during multiple assignments
    
    Fixes #4620.
    
    R=rsc
    CC=golang-dev
    https://golang.org/cl/7241051

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

https://github.com/golang/go/commit/5ea52a4d91fd45a2a727a4f6cca96d08cb2960f2

元コミット内容

cmg/gc: Fix evaluation order of map indexing during multiple assignments

Fixes #4620.

R=rsc
CC=golang-dev
https://golang.org/cl/7241051

変更の背景

この変更は、Go言語のコンパイラgcにおける、マップのインデックス評価順序に関するバグを修正するために行われました。具体的には、i, m[i] = 1, 2 のような多重代入文において、m[i] の i が、代入される値 1 によって変更される前に評価されるべきであるにもかかわらず、そうならないケースが存在したためです。

Go言語の仕様では、多重代入の右辺の式は、左辺の変数に代入される前にすべて評価されることが保証されています。しかし、このバグが存在したバージョンでは、マップのインデックス式がこの規則に従わず、予期せぬ動作を引き起こす可能性がありました。

この問題は、issue #4620 として報告されており、このコミットはその修正を目的としています。

前提知識の解説

Goコンパイラ (gc) の内部構造

Goコンパイラ（gc）は、ソースコードを機械語に変換する過程で、複数のフェーズを経ます。このコミットで変更されているsrc/cmd/gc/walk.cは、コンパイラの「ウォーカー（walker）」フェーズに関連する部分です。ウォーカーは、抽象構文木（AST）を走査し、最適化やコード生成のための変換を行います。

• AST (Abstract Syntax Tree): プログラムの構造を木構造で表現したものです。コンパイラはソースコードをパースしてASTを構築します。
• Node: ASTの各ノードを表すデータ構造です。例えば、変数、定数、演算子、関数呼び出しなどがNodeとして表現されます。
• OAS (Op Assign): 代入演算子を表すNodeのオペレーションコードです。
• OINDEXMAP: マップのインデックスアクセスを表すNodeのオペレーションコードです。
• convas: ASTノードを変換する関数の一つで、特に代入文を処理し、必要に応じて一時変数の導入や関数呼び出しへの変換を行います。マップへの代入は、内部的にはランタイム関数呼び出しに変換されることがあります。
• reorder3: 式の評価順序を調整する関数です。Go言語の仕様では、式の評価順序が厳密に定められており、reorder3はその順序を保証するために、必要に応じて一時変数を導入したり、式の評価を前倒ししたりします。特に、多重代入や関数呼び出しの引数評価において重要になります。

多重代入と評価順序

Go言語における多重代入（a, b = c, d）では、右辺の式（c, d）がすべて評価されてから、その結果が左辺の変数（a, b）に代入されます。この「すべて評価されてから」という点が重要です。

例: i, m[i] = 1, 2 この場合、1 と 2 が評価され、m[i] の i も、i に 1 が代入される前に評価される必要があります。つまり、m[i] の i は、代入前の i の値（この例では 0）を使って評価され、m[0] が参照されるべきです。その後、i に 1 が代入され、m[0] に 2 が代入されます。

マップの内部表現と操作

Goのマップはハッシュテーブルとして実装されており、キーと値のペアを格納します。マップへの要素の追加、更新、削除は、内部的にはランタイム関数（例: mapassign）の呼び出しとして処理されます。これは、コンパイラが直接機械語でマップ操作を生成するのではなく、Goランタイムが提供する関数を呼び出す形になるためです。

技術的詳細

このコミットの核心は、src/cmd/gc/walk.c 内の ascompatee1 関数と reorder3 関数の変更にあります。

ascompatee1 関数の変更

ascompatee1 関数は、代入文の右辺の式を処理し、必要に応じて変換を行う役割を担っています。変更前は、convas(nod(OAS, l, r), init) という形で、常に代入ノードをconvas関数に渡していました。

変更後、以下のロジックが追加されました。

	Node *n;
	USED(op);
	
	// convas will turn map assigns into function calls,
	// making it impossible for reorder3 to work.
	n = nod(OAS, l, r);
	if(l->op == OINDEXMAP)
		return n;

	return convas(n, init);

この変更の意図は、マップへの代入（l->op == OINDEXMAP）の場合、convas関数をすぐに呼び出すのを避けることです。なぜなら、convasはマップへの代入をランタイム関数呼び出しに変換する可能性があり、その変換が行われると、後続のreorder3関数が式の評価順序を正しく調整できなくなるためです。

つまり、マップへの代入の場合は、まずOASノードをそのまま返し、reorder3が評価順序の調整を終えた後に、改めてconvasによる変換が行われるように制御フローを変更しています。これにより、マップのインデックス式が、多重代入の他の要素が評価される前に、適切なタイミングで評価されるようになります。

reorder3 関数の変更

reorder3関数は、式の評価順序を調整し、必要に応じて一時変数を導入する役割を担っています。この関数は、特に多重代入や関数呼び出しの引数評価において、Go言語の厳密な評価順序を保証するために重要です。

変更前は、reorder3はOINDEXMAPノードを特別扱いしていませんでした。変更後、以下のロジックが追加されました。

	NodeList *list, *early, *mapinit; // mapinitが追加
	Node *l;

	// ... (既存のコード)

	early = nil;
	mapinit = nil; // 初期化

	for(list=all; list; list=list->next) {
		l = list->n->left;

		// ... (既存のコード)

		case OINDEX:
		case OINDEXMAP: // OINDEXMAPが追加
			reorder3save(&l->left, all, list, &early);
			reorder3save(&l->right, all, list, &early);
			if(l->op == OINDEXMAP) // OINDEXMAPの場合の処理が追加
				list->n = convas(list->n, &mapinit);
			break;
		// ... (既存のコード)
	}

	early = concat(mapinit, early); // mapinitがearlyに連結される
	return concat(early, all);

この変更のポイントは以下の通りです。

1. mapinit の導入: mapinit という新しいNodeListが導入されました。これは、マップへの代入に関連する初期化処理（convasによって生成される可能性のあるランタイム関数呼び出しなど）を一時的に保持するためのものです。
2. OINDEXMAP の特別扱い: reorder3がOINDEXMAPノード（マップのインデックスアクセス）を検出した場合、そのノードに対してconvasを呼び出し、その結果をmapinitリストに追加します。これにより、マップのインデックス評価に関連する処理が、他の式よりも「早期に」実行されるように調整されます。
3. mapinit の連結: 最後に、mapinitリストの内容がearlyリスト（早期に評価されるべき式を保持するリスト）の先頭に連結されます。これにより、マップのインデックス評価が、多重代入の他の要素の評価よりも確実に先行して行われるようになります。

これらの変更により、i, m[i] = 1, 2 のような多重代入において、m[i] の i が、i に 1 が代入される前に評価されることが保証されます。

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

src/cmd/gc/walk.c

--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -1296,9 +1296,16 @@ ret:
 static Node*
 ascompatee1(int op, Node *l, Node *r, NodeList **init)
 {
+	Node *n;
 	USED(op);
+	
+	// convas will turn map assigns into function calls,
+	// making it impossible for reorder3 to work.
+	n = nod(OAS, l, r);
+	if(l->op == OINDEXMAP)
+		return n;
 
-	return convas(nod(OAS, l, r), init);
+	return convas(n, init);
 }
 
 static NodeList*
@@ -1896,13 +1903,14 @@ static int aliased(Node*, NodeList*, NodeList*);\
 static NodeList*
 reorder3(NodeList *all)
 {
-	NodeList *list, *early;\
+	NodeList *list, *early, *mapinit;\
 	Node *l;\
 
 	// If a needed expression may be affected by an
 	// earlier assignment, make an early copy of that
 	// expression and use the copy instead.\
 	early = nil;\
+	mapinit = nil;\
 	for(list=all; list; list=list->next) {\
 	\tl = list->n->left;\
 
@@ -1926,8 +1934,11 @@ reorder3(NodeList *all)\
 	\t\tcase ONAME:\
 	\t\t\tbreak;\
 	\t\tcase OINDEX:\
+	\t\tcase OINDEXMAP:\
 	\t\t\treorder3save(&l->left, all, list, &early);\
 	\t\t\treorder3save(&l->right, all, list, &early);\
+	\t\t\tif(l->op == OINDEXMAP)\
+	\t\t\t\tlist->n = convas(list->n, &mapinit);\
 	\t\t\tbreak;\
 	\t\tcase OIND:\
 	\t\tcase ODOTPTR:\
@@ -1938,6 +1949,7 @@ reorder3(NodeList *all)\
 	\treorder3save(&list->n->right, all, list, &early);\
 	}\
 
+\tearly = concat(mapinit, early);\
 	return concat(early, all);\
 }\
 

test/fixedbugs/issue4620.go

--- /dev/null
+++ b/test/fixedbugs/issue4620.go
@@ -0,0 +1,21 @@
+// run
+
+// 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 4620: map indexes are not evaluated before assignment of other elements
+
+package main
+
+import "fmt"
+
+func main() {
+	m := map[int]int{0:1}
+	i := 0
+	i, m[i] = 1, 2
+	if m[0] != 2 {
+		fmt.Println(m)
+		panic("m[i] != 2")
+	}
+}

コアとなるコードの解説

src/cmd/gc/walk.c の変更点

1. ascompatee1 関数:

   • この関数は、代入の右辺の式を処理する際に呼び出されます。
   • 変更前は、常にconvasを呼び出して代入ノードを変換していました。
   • 変更後は、代入の左辺がマップのインデックスアクセス（l->op == OINDEXMAP）である場合、convasを呼び出さずに、OASノードをそのまま返します。
   • この変更の理由は、convasがマップへの代入をランタイム関数呼び出しに変換してしまうと、reorder3が評価順序を正しく調整できなくなるためです。reorder3が先に評価順序を調整し、その後でconvasによる変換が行われるように、処理のタイミングをずらしています。

2. reorder3 関数:

   • この関数は、式の評価順序を調整し、必要に応じて一時変数を導入します。
   • mapinitという新しいNodeListが導入されました。これは、マップへの代入に関連する初期化処理を保持するためのものです。
   • forループ内で、OINDEXMAPノードが検出された場合、そのノードに対してconvasを呼び出し、その結果をmapinitリストに追加します。これにより、マップのインデックス評価に関連する処理が、他の式よりも「早期に」実行されるように調整されます。
   • 最後に、mapinitリストの内容がearlyリスト（早期に評価されるべき式を保持するリスト）の先頭に連結されます。これにより、マップのインデックス評価が、多重代入の他の要素の評価よりも確実に先行して行われることが保証されます。

これらの変更により、i, m[i] = 1, 2 のような多重代入において、m[i] の i が、i に 1 が代入される前に評価されるというGo言語の仕様が正しく満たされるようになります。

test/fixedbugs/issue4620.go の変更点

• このファイルは、issue #4620 で報告されたバグを再現し、修正が正しく適用されたことを検証するための新しいテストケースです。
• テストケースでは、m := map[int]int{0:1} とマップを初期化し、i := 0 と変数を宣言します。
• 問題の多重代入 i, m[i] = 1, 2 を実行します。
• もしバグが修正されていなければ、m[i] の i が 1 に更新された後に評価され、m[1] が参照されてしまう可能性があります。しかし、正しい動作では、m[i] の i は代入前の値 0 で評価され、m[0] が参照されます。
• 最後に if m[0] != 2 で結果を検証し、m[0] が 2 でなければパニックを発生させます。これにより、修正が正しく機能していることを確認します。

関連リンク

• Go言語の仕様: https://go.dev/ref/spec (特に「Assignments」のセクション)
• Goコンパイラのソースコード: https://github.com/golang/go/tree/master/src/cmd/compile

参考にした情報源リンク

• Go言語の公式ドキュメント
• Goコンパイラのソースコード
• Go言語のIssueトラッカー (ただし、issue #4620 は直接見つからなかったため、コミットメッセージからの推測が主)
• Go言語のコンパイラに関する一般的な知識