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

コミット

commit 6b72b070166c94f386cdaeea7bc762cdcf277bd3
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Sat Jan 14 17:00:14 2012 +0100

    gc: do not compile switch on interface values into a binary search.
    
    Fixes #2672.
    
    R=golang-dev, lvd
    CC=golang-dev, remy
    https://golang.org/cl/5543058

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

https://github.com/golang/go/commit/6b72b070166c94f386cdaeea7bc762cdcf277bd3

元コミット内容

commit 6b72b070166c94f386cdaeea7bc762cdcf277bd3
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Sat Jan 14 17:00:14 2012 +0100

    gc: do not compile switch on interface values into a binary search.
    
    Fixes #2672.
    
    R=golang-dev, lvd
    CC=golang-dev, remy
    https://golang.org/cl/5543058
---
 src/cmd/gc/swt.c         |  2 +-\
 test/fixedbugs/bug393.go | 30 ++++++++++++++++++++++++++++++\
 2 files changed, 31 insertions(+), 1 deletion(-)\

diff --git a/src/cmd/gc/swt.c b/src/cmd/gc/swt.c
index 8b1b93c7da..6c0a9ac832 100644
--- a/src/cmd/gc/swt.c
+++ b/src/cmd/gc/swt.c
@@ -540,7 +540,7 @@ loop:
 	}\
 
 	// deal with the variables one-at-a-time
-\tif(c0->type != Texprconst) {\
+\tif(!okforcmp[t->etype] || c0->type != Texprconst) {\
 	\ta = exprbsw(c0, 1, arg);\
 	\tcas = list(cas, a);\
 	\tc0 = c0->link;\
diff --git a/test/fixedbugs/bug393.go b/test/fixedbugs/bug393.go
new file mode 100644
index 0000000000..e21b9c4a41
--- /dev/null
+++ b/test/fixedbugs/bug393.go
@@ -0,0 +1,30 @@\
+// $G $D/$F.go || echo BUG: bug393\
+\
+// Copyright 2012 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 2672\
+// was trying binary search with an interface type\
+\
+package main\
+\
+func f(x interface{}) int {\
+\tswitch x {\
+\tcase 1:\
+\t\treturn 1\
+\tcase 2:\
+\t\treturn 2\
+\tcase 3:\
+\t\treturn 3\
+\tcase 4:\
+\t\treturn 4\
+\tcase "5":\
+\t\treturn 5\
+\tcase "6":\
+\t\treturn 6\
+\tdefault:\
+\t\treturn 7\
+\t}\
+\tpanic("switch")\
+}\

変更の背景

このコミットは、Goコンパイラ（gc）がインターフェース型の値に対するswitch文を処理する際に発生していたバグを修正します。具体的には、コンパイラが特定の条件下でインターフェース値のswitch文を二分探索（binary search）に最適化しようとすることが問題でした。

インターフェース型は、その内部に具体的な値と型の情報を動的に保持します。switch文がインターフェース値に対して使用される場合、各caseの比較は、単なる値の比較だけでなく、型の比較も伴う複雑な操作になります。このような動的な性質を持つインターフェース値に対して、コンパイラが静的な値の比較に用いられる二分探索のような最適化を適用しようとすると、比較ロジックが破綻し、予期せぬ動作やバグ（この場合はGo issue #2672として報告された問題）を引き起こす可能性がありました。

このコミットは、このような誤った最適化を防ぎ、インターフェース値に対するswitch文が正しくコンパイルされるようにすることを目的としています。

前提知識の解説

Go言語の`switch`文

Go言語のswitch文は、他の多くの言語と同様に、複数の条件分岐を簡潔に記述するための制御構造です。Goのswitch文には主に二つの形式があります。

式スイッチ (Expression Switch): 特定の式の値とcase句の値を比較します。

switch x {
case 1:
    // xが1の場合
case 2, 3:
    // xが2または3の場合
default:
    // どのcaseにも一致しない場合
}

型スイッチ (Type Switch): インターフェース変数の動的な型に基づいて分岐します。

switch v := i.(type) {
case int:
    // iの動的な型がintの場合
case string:
    // iの動的な型がstringの場合
default:
    // その他の型の場合
}

本コミットで問題となっているのは、式スイッチがインターフェース値に対して使用された場合です。

インターフェース型 (`interface{}`)

Go言語のインターフェースは、メソッドの集合を定義する型です。interface{}（空インターフェース）は、メソッドを一切持たないインターフェースであり、Goのあらゆる型の値を保持することができます。これは、他の言語におけるObject型やAny型に似ています。

インターフェース型の変数には、以下の2つの情報が内部的に保持されています。

動的な型 (dynamic type): 変数に格納されている具体的な値の型。
動的な値 (dynamic value): 変数に格納されている具体的な値。

switch文でインターフェース値を比較する場合、これらの動的な型と値の両方が考慮される必要があります。

コンパイラの最適化 (二分探索)

コンパイラは、プログラムの実行速度を向上させるために様々な最適化を行います。switch文のような分岐構造は、コンパイラが最適化の対象とすることが多い部分です。

一般的なコンパイラは、switch文のcase値が整数などの順序付け可能な定数である場合、効率的な分岐を実現するために以下の最適化手法を検討します。

ジャンプテーブル (Jump Table): case値が連続している場合や、ある程度の範囲に収まっている場合に、配列のような構造（ジャンプテーブル）を作成し、case値に対応するコードブロックへのオフセットを直接参照することで、高速な分岐を実現します。
二分探索 (Binary Search): case値が連続していないが、ソート可能な定数である場合に、二分探索アルゴリズムを用いて効率的に一致するcaseを見つけ出す方法です。これにより、線形探索（各caseを順番に比較していく）よりも高速に目的のcaseに到達できます。

しかし、インターフェース値の比較は、単なる数値や文字列の比較とは異なり、動的な型情報も考慮する必要があるため、二分探索のような静的な比較最適化には適していません。

`gc` (Go Compiler)

gcは、Go言語の公式コンパイラであり、Goのソースコードを機械語に変換する役割を担っています。src/cmd/gcディレクトリには、このコンパイラのソースコードが含まれています。swt.cファイルは、このコンパイラ内でswitch文の処理を担当する部分の一つです。

技術的詳細

このコミットの技術的な核心は、Goコンパイラがインターフェース値に対するswitch文を誤って二分探索に最適化しようとしていた問題の修正です。

src/cmd/gc/swt.cは、Goコンパイラがswitch文を処理する際のコード生成ロジックを含んでいます。通常、switch文のcaseが定数（Texprconst）である場合、コンパイラは効率的な比較のために二分探索（exprbsw関数）などの最適化を適用しようとします。

しかし、インターフェース値の場合、caseの比較は単なる値の等価性チェックだけでなく、動的な型の等価性チェックも必要とします。例えば、interface{}型の変数xに対してswitch x { case 1: ... case "hello": ... }のようなコードがあった場合、1と"hello"は異なる型であり、これらを単純な数値として二分探索の対象とすることはできません。インターフェースの比較は、内部的に値と型の両方を比較する複雑なランタイム操作を伴います。

既存のコードでは、if(c0->type != Texprconst)という条件で、caseが定数でない場合にのみ二分探索の適用を避けていました。しかし、インターフェース値はTexprconst（定数式）として扱われることがあり、その結果、インターフェース値のswitch文が誤って二分探索の対象となってしまっていました。

このコミットでは、この条件に!okforcmp[t->etype]というチェックを追加しています。

t->etype: switch文の対象となる式の型（EType）。
okforcmp: コンパイラ内部で定義されている、比較操作が安全に適用できる型を示す真偽値の配列。

!okforcmp[t->etype]という条件は、「switchの対象となる式の型が、比較に適さない型である場合」を意味します。これにより、インターフェース型のように動的な性質を持ち、単純な二分探索の前提を満たさない型に対しては、caseが定数であっても二分探索へのコンパイルを明示的に回避するようになります。

結果として、インターフェース値に対するswitch文は、より汎用的な（しかし、この場合は正しい）比較ロジックで処理されるようになり、バグが修正されます。

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

`src/cmd/gc/swt.c`

--- a/src/cmd/gc/swt.c
+++ b/src/cmd/gc/swt.c
@@ -540,7 +540,7 @@ loop:
 	}\
 
 	// deal with the variables one-at-a-time
-\tif(c0->type != Texprconst) {\
+\tif(!okforcmp[t->etype] || c0->type != Texprconst) {\
 	\ta = exprbsw(c0, 1, arg);\
 	\tcas = list(cas, a);\
 	\tc0 = c0->link;\

`test/fixedbugs/bug393.go` (新規追加)

// $G $D/$F.go || echo BUG: bug393
// Copyright 2012 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 2672
// was trying binary search with an interface type

package main

func f(x interface{}) int {
	switch x {
	case 1:
		return 1
	case 2:
		return 2
	case 3:
		return 3
	case 4:
		return 4
	case "5":
		return 5
	case "6":
		return 6
	default:
		return 7
	}
	panic("switch")
}

コアとなるコードの解説

`src/cmd/gc/swt.c` の変更

変更はif文の条件式に!okforcmp[t->etype]が追加された点です。

変更前: if(c0->type != Texprconst)
- この条件は、「caseの値が定数式でない場合」にexprbsw（二分探索を生成する関数）の呼び出しをスキップしていました。しかし、インターフェース値のcaseは定数式として扱われることがあり、その結果、誤って二分探索の対象となっていました。
変更後: if(!okforcmp[t->etype] || c0->type != Texprconst)
- 新しい条件は、「switchの対象となる式の型（t->etype）が比較に適さない型である場合」または「caseの値が定数式でない場合」にexprbswの呼び出しをスキップするようになりました。
- okforcmp配列は、Goコンパイラが内部的に持つ、特定の型が比較操作（特に効率的な比較）に適しているかどうかを示すフラグです。インターフェース型のような動的な型は、このokforcmpがfalseとなるように設定されているため、この変更により、インターフェース値に対するswitch文が二分探索にコンパイルされることが効果的に防止されます。これにより、インターフェースの動的な比較セマンティクスが正しく尊重されるようになります。

`test/fixedbugs/bug393.go` の新規追加

このファイルは、Go issue #2672で報告されたバグを再現し、修正が正しく適用されたことを検証するためのテストケースです。

func f(x interface{}) int: interface{}型の引数xを受け取る関数を定義しています。
switch x { ... }: この関数内で、interface{}型のxに対してswitch文を使用しています。
case 1: ... case 4: ... case "5": ... case "6":: 注目すべきは、caseの値に整数（1から4）と文字列（"5", "6"）が混在している点です。インターフェース値のswitchでは、このような異なる型の値がcaseとして現れることが許容されます。
バグの再現: 修正前のコンパイラでは、このようなswitch文が二分探索に最適化されようとした際に、異なる型の値が混在していることで比較ロジックが破綻し、コンパイルエラーやランタイムエラーを引き起こしていました。
修正の検証: このテストケースがコンパイルエラーなく正常に実行されることで、コンパイラの修正が正しく機能し、インターフェース値に対するswitch文が意図しない二分探索にコンパイルされなくなったことが確認できます。

このテストは、$G $D/$F.go || echo BUG: bug393という行で始まるGoのテスト慣習に従っており、コンパイルまたは実行が失敗した場合にBUG: bug393というメッセージを出力することで、バグの存在を示唆します。修正が適用された後は、このテストは成功し、何も出力されません。

参考にした情報源リンク

Go言語公式ドキュメント: switch文
Go言語公式ドキュメント: インターフェース
Goコンパイラのソースコード (src/cmd/gc/)
Go issue tracker (GitHub)
Go code review system (Gerrit)

comemo