[インデックス 1864] ファイルの概要
このコミットは、Goコンパイラのgc（Go Compiler）部分におけるswitch文の処理ロジックを大幅に書き換えるものです。具体的には、src/cmd/gc/go.y（Go言語の文法定義ファイル）とsrc/cmd/gc/swt.c（switch文のコンパイル処理を扱うC言語ソースファイル）が変更されています。
go.yは、Go言語の構文解析器（パーサー）が使用するYacc/Bison形式の文法定義ファイルです。このファイルは、Goのソースコードがどのように構造化されているかを定義し、コンパイラがコードを抽象構文木（AST）に変換する際の基盤となります。
swt.cは、Goコンパイラのバックエンドに近い部分で、switch文のセマンティックチェックと中間表現への変換、さらには最終的なコード生成のための最適化を担当します。このファイルは、switch文の各caseを効率的に処理するためのロジックを含んでいます。
コミット
commit 79fa5b65cb2e89a9585dd0ed681847a03a48b8a6
Author: Ken Thompson <ken@golang.org>
Date: Sun Mar 22 20:54:21 2009 -0700
rewrote switch
fixed bug 141
R=r
OCL=26627
CL=26627
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/79fa5b65cb2e89a9585dd0ed681847a03a48b8a6
元コミット内容
rewrote switch
fixed bug 141
変更の背景
このコミットの主な背景は、Go言語のswitch文の実装におけるバグ修正と、より堅牢で効率的な処理ロジックへの全面的な書き換えです。コミットメッセージに明記されている「fixed bug 141」が重要な手がかりとなります。
Go言語の初期のバグトラッカーにおけるIssue 141は、「switch文のcaseラベルが定数でない場合にコンパイルエラーが発生する」という問題に関するものです。具体的には、switch文のcase式が定数でない変数や式である場合に、コンパイラが正しく処理できず、内部エラーや不正なコード生成を引き起こしていました。
当時のGoコンパイラ（gc）は、switch文の最適化において、caseラベルが定数である場合にのみ効率的なジャンプテーブルや二分探索ツリーを生成するロジックを持っていました。しかし、Go言語の仕様では、switch文のcaseラベルは定数である必要はなく、任意の式（ただし、評価結果が比較可能な型であること）を記述できます。この仕様と実装の乖離が、バグ141の原因となっていました。
このコミットは、この根本的な問題を解決するために、switch文の処理ロジックを根本から見直し、caseラベルが定数であるか否かに関わらず、統一的かつ正確に処理できるように再設計されたものです。これにより、コンパイラの安定性が向上し、Go言語のswitch文の柔軟な利用が可能になりました。
前提知識の解説
このコミットの変更内容を理解するためには、以下の前提知識が役立ちます。
1. Goコンパイラ (gc) の構造
Goコンパイラ（gc）は、Go言語のソースコードを機械語に変換するツールチェーンの中核をなします。その処理は大きく以下のフェーズに分けられます。
- 字句解析 (Lexical Analysis): ソースコードをトークン（予約語、識別子、演算子など）のストリームに変換します。
- 構文解析 (Syntactic Analysis): トークンのストリームを解析し、言語の文法規則に従って抽象構文木（AST: Abstract Syntax Tree）を構築します。
src/cmd/gc/go.yはこのフェーズで使われる文法定義ファイルです。 - 意味解析 (Semantic Analysis): ASTを走査し、型チェック、名前解決、定数評価などの意味的な検証を行います。このフェーズで、
switch文の各caseの型が適切か、重複がないかなどがチェックされます。src/cmd/gc/swt.cはこのフェーズの一部、またはその後の最適化フェーズでswitch文の処理を担当します。 - 中間コード生成 (Intermediate Code Generation): ASTを、より機械語に近い中間表現（IR）に変換します。
- 最適化 (Optimization): 中間表現に対して様々な最適化を適用し、生成される機械語の効率を向上させます。
- コード生成 (Code Generation): 最適化された中間表現から最終的な機械語を生成します。
2. switch文のコンパイル戦略
switch文は、多くのプログラミング言語に存在する制御構造ですが、そのコンパイル戦略は言語やコンパイラによって異なります。
- ジャンプテーブル (Jump Table):
switch式の値が連続した整数である場合、各caseラベルに対応するコードブロックへのジャンプアドレスを格納したテーブルを作成し、switch式の値を使って直接テーブルをインデックスすることで、高速な分岐を実現します。 - 二分探索 (Binary Search):
caseラベルが連続していないが、ソート可能な定数である場合、二分探索ツリーを構築し、switch式の値とcaseラベルを比較しながら探索することで、効率的な分岐を実現します。 - if-else if連鎖 (If-Else If Chain): 上記の最適化が適用できない場合（例:
caseラベルが非定数式、文字列、浮動小数点数など）、一連のif-else if文に変換されます。これは最も汎用的な方法ですが、分岐数が増えるにつれて効率が低下します。
Go言語のswitch文は、式switchと型switchの2種類があります。
- 式
switch:switchキーワードの後に式が続き、その式の値とcaseラベルの値を比較します。caseラベルは定数でも非定数式でも構いません。 - 型
switch:switchキーワードの後に型アサーション（例:v := i.(type)）が続き、インターフェース変数の動的な型とcaseラベルの型を比較します。
3. 抽象構文木 (AST) とノード (Node)
コンパイラはソースコードをASTとして内部的に表現します。ASTは、プログラムの構造を木構造で表したもので、各ノードはプログラムの要素（変数、式、文など）に対応します。Goコンパイラでは、これらの要素がNode構造体で表現されます。Nodeは、その種類（opフィールド）、子ノード（left, right, nbodyなど）、型情報（typeフィールド）、値（valフィールド）などを含みます。
4. リンクドリストとソート
swt.cのコードでは、Case構造体のリンクドリストが頻繁に利用され、csort関数によってソートされています。これは、caseラベルを効率的に検索・比較するために、特定の順序で並べ替える必要があるためです。マージソートのようなアルゴリズムが内部的に使用されていることが示唆されます。
技術的詳細
このコミットにおけるswitch文の書き換えは、主にsrc/cmd/gc/swt.cファイルに集約されており、その核心はswitch文の各caseをより柔軟かつ効率的に処理するための新しいデータ構造とアルゴリズムの導入にあります。
1. Case構造体の拡張と新しいenum型
以前のCase構造体は、Node* node、uint32 hash、uint8 uniqといったフィールドを持っていましたが、今回の変更で以下のように拡張されました。
struct Case
{
Node* node; // points at case statement
uint32 hash; // hash of a type switch
uint8 type; // type of case (NEW)
uint8 diag; // suppress multiple diagnostics
uint16 ordinal; // position in switch (NEW)
Case* link; // linked list to link
};
特に重要なのは、typeとordinalフィールドの追加です。
-
type:caseの種類を識別するための新しいフィールドです。これに対応して、以下の新しいenum値が定義されました。Tdefault:defaultケースTexprconst: 定数式によるcase（例:case 1:）Texprvar: 変数または非定数式によるcase（例:case x + y:）Ttypenil: 型switchにおけるcase nil:Ttypeconst: 型switchにおける具体的な型定数によるcase（例:case int:）Ttypevar: 型switchにおけるインターフェース型変数によるcase（例:case io.Reader:） これらの型を区別することで、コンパイラは各caseに最適な処理戦略を適用できるようになります。
-
ordinal:switch文内でのcaseの元の出現順序を保持するためのフィールドです。これは、caseの並べ替え（ソート）を行った後でも、元の順序を復元したり、エラーメッセージで正確な行番号を示すために使用されます。
2. mkcaselist関数によるCaseリストの構築
新しく導入されたmkcaselist関数は、switch文のASTノードを受け取り、それを解析してCase構造体のリンクドリストを構築します。この関数は、各caseのタイプ（Tdefault, Texprconstなど）を識別し、Case構造体のtypeフィールドに設定します。これにより、後続の処理でcaseの種類に応じた適切なコンパイル戦略を選択できるようになります。
3. 汎用ソート関数csortと新しい比較関数
csort関数は、汎用的なマージソートアルゴリズムを実装しており、比較関数を引数として受け取ることで、様々な基準でCaseリストをソートできるように設計されています。このコミットでは、以下の新しい比較関数が導入されました。
ordlcmp(Case *c1, Case *c2):caseの元の出現順序（ordinal）に基づいてソートします。defaultケースとnilケースを優先的にソートするロジックも含まれています。これは、caseリストを処理順序に戻すために使用されます。exprcmp(Case *c1, Case *c2): 式switchのcaseラベル（定数式）の値を比較してソートします。これにより、定数caseを効率的に二分探索できるようになります。浮動小数点数、整数、文字列の定数に対応しています。typecmp(Case *c1, Case *c2): 型switchのcaseラベル（型定数）のハッシュ値を比較してソートします。これにより、型caseを効率的に二分探索できるようになります。
これらのソートと新しい比較関数により、コンパイラはcaseラベルの特性（定数、非定数、型など）に応じて、最適な探索アルゴリズム（二分探索、線形探索など）を選択できるようになりました。
4. exprswitchとtypeswitchの再設計
exprswitch関数（式switchの処理）とtypeswitch関数（型switchの処理）は、新しいCase構造体とソートロジックを活用するように大幅に再設計されました。
exprswitch:- まず、
mkcaselistを使ってCaseリストを構築します。 caseが定数式である場合は、exprcmpを使ってソートし、exprbsw関数（二分探索ツリーを構築するロジック）を使って効率的なif-else ifのツリー構造に変換します。caseが非定数式である場合は、線形探索（単純なif文の連鎖）にフォールバックします。- これにより、定数
caseは高速に処理され、非定数caseも正しくコンパイルされるようになりました。
- まず、
typeswitch:- 同様に、
mkcaselistを使ってCaseリストを構築します。 - 型
switchのcaseは、その型ハッシュに基づいてtypecmpでソートされ、typebsw関数によって効率的な分岐ロジックに変換されます。 case nilやインターフェース型変数によるcaseも適切に処理されます。- 型
switchの内部では、インターフェース変数の動的な型情報を取得し、そのハッシュ値や型情報に基づいて分岐を行うためのコードが生成されます。
- 同様に、
5. LCONVERTトークンの削除
src/cmd/gc/go.yからLCONVERTトークンが削除されています。これは、Go言語の初期の文法で型変換（例: int(x)) を表すために使用されていたトークンですが、言語の進化に伴い、より一般的な式として扱われるようになったため、明示的なトークンが不要になった可能性があります。この変更は、switch文の書き換えとは直接関係ないかもしれませんが、コンパイラの文法定義のクリーンアップの一環として行われたと考えられます。
6. バグ141の修正
この書き換えにより、switch文のcaseラベルが定数でない場合でも、コンパイラが正しく処理できるようになりました。具体的には、Texprvarという新しいCaseタイプが導入され、非定数式によるcaseが適切に識別・処理されるようになりました。これにより、以前はコンパイルエラーや不正なコード生成を引き起こしていたバグ141が修正されました。
コアとなるコードの変更箇所
このコミットのコアとなる変更は、src/cmd/gc/swt.cファイルに集中しています。特に以下の部分が重要です。
1. Case構造体の定義変更
--- a/src/cmd/gc/swt.c
+++ b/src/cmd/gc/swt.c
@@ -11,16 +11,222 @@ enum
Sfalse,
Stype,
- Ncase = 4, // needed to binary search
+ Tdefault, // default case
+ Texprconst, // normal constant case
+ Texprvar, // normal variable case
+ Ttypenil, // case nil
+ Ttypeconst, // type hashes
+ Ttypevar, // interface type
+
+ Ncase = 4, // count needed to split
};
-Node* exprbsw(Node *t, Iter *save, Node *name);
-void typeswitch(Node *sw);
typedef struct Case Case;
struct Case
{
Node* node; // points at case statement
uint32 hash; // hash of a type switch
- uint8 uniq; // first of multiple identical hashes
+ uint8 type; // type of case
uint8 diag; // suppress multiple diagnostics
+ uint16 ordinal; // position in switch
Case* link; // linked list to link
};
2. mkcaselist関数の追加
--- a/src/cmd/gc/swt.c
+++ b/src/cmd/gc/swt.c
@@ -209,6 +401,70 @@ loop:
}
Case*
+mkcaselist(Node *sw, int arg)
+{
+ Iter save;
+ Node *n;
+ Case *c, *c1;
+ int ord;
+
+ c = C;
+ ord = 0;
+
+ n = listfirst(&save, sw->nbody->left);
+
+loop:
+ if(n == N)
+ goto done;
+
+ c1 = mal(sizeof(*c1));
+ c1->link = c;
+ c = c1;
+
+ ord++;
+ c->ordinal = ord;
+ c->node = n;
+
+ if(n->left == N) {
+ c->type = Tdefault;
+ goto next;
+ }
+
+ switch(arg) {
+ case Stype:
+ c->hash = 0;
+ if(n->left->left == N) {
+ c->type = Ttypenil;
+ goto next;
+ }
+ if(istype(n->left->left->type, TINTER)) {
+ c->type = Ttypevar;
+ goto next;
+ }
+
+ c->hash = typehash(n->left->left->type, 1, 0);
+ c->type = Ttypeconst;
+ goto next;
+
+ case Snorm:
+ case Strue:
+ case Sfalse:
+ c->type = Texprvar;
+ switch(consttype(n->left)) {
+ case CTFLT:
+ case CTINT:
+ case CTSTR:
+ c->type = Texprconst;
+ }
+ goto next;
+ }
+next:
+ n = listnext(&save);
+ goto loop;
+
+done:
+ if(c == C)
+ return C;
+
+ // sort by value and diagnose duplicate cases
+ switch(arg) {
+ case Stype:
+ c = csort(c, typecmp);
+ for(c1=c; c1->link!=C; c1=c1->link) {
+ if(typecmp(c1, c1->link) != 0)
+ continue;
+ setlineno(c1->link->node);
+ yyerror("duplicate case in switch");
+ print(" previous case at %L\n",
+ c1->node->lineno);
+ }
+ break;
+ case Snorm:
+ case Strue:
+ case Sfalse:
+ c = csort(c, exprcmp);
+ for(c1=c; c1->link!=C; c1=c1->link) {
+ if(exprcmp(c1, c1->link) != 0)
+ continue;
+ setlineno(c1->link->node);
+ yyerror("duplicate case in switch");
+ print(" previous case at %L\n",
+ c1->node->lineno);
+ }
+ break;
+ }
+
+ // put list back in processing order
+ c = csort(c, ordlcmp);
+ return c;
+}
3. csort関数と新しい比較関数群 (ordlcmp, exprcmp, typecmp)
csort関数は既存ですが、その利用方法と、新しい比較関数が追加されています。
--- a/src/cmd/gc/swt.c
+++ b/src/cmd/gc/swt.c
@@ -11,6 +11,109 @@ enum
Sfalse,
Stype,
- Ncase = 4,\t// needed to binary search
+ Tdefault, // default case
+ Texprconst, // normal constant case
+ Texprvar, // normal variable case
+ Ttypenil, // case nil
+ Ttypeconst, // type hashes
+ Ttypevar, // interface type
+
+ Ncase = 4,\t// count needed to split
};
-Node*\texprbsw(Node *t, Iter *save, Node *name);
-void\ttypeswitch(Node *sw);
typedef struct\tCase\tCase;
struct\tCase
{
Node*\tnode;\t\t// points at case statement
uint32\thash;\t\t// hash of a type switch
- uint8\tuniq;\t\t// first of multiple identical hashes
+ uint8\ttype;\t\t// type of case
uint8\tdiag;\t\t// suppress multiple diagnostics
+ uint16\tordinal;\t// position in switch
Case*\tlink;\t\t// linked list to link
};
#define\tC\t((Case*)nil)
+void
+dumpcase(Case *c0)
+{
+ Case *c;
+
+ for(c=c0; c!=C; c=c->link) {
+ switch(c->type) {
+ case Tdefault:
+ print("case-default\n");
+ print("\tord=%d\n", c->ordinal);
+ break;
+ case Texprconst:
+ print("case-exprconst\n");
+ print("\tord=%d\n", c->ordinal);
+ break;
+ case Texprvar:
+ print("case-exprvar\n");
+ print("\tord=%d\n", c->ordinal);
+ print("\top=%O\n", c->node->left->op);
+ break;
+ case Ttypenil:
+ print("case-typenil\n");
+ print("\tord=%d\n", c->ordinal);
+ break;
+ case Ttypeconst:
+ print("case-typeconst\n");
+ print("\tord=%d\n", c->ordinal);
+ print("\thash=%ux\n", c->hash);
+ break;
+ case Ttypevar:
+ print("case-typevar\n");
+ print("\tord=%d\n", c->ordinal);
+ break;
+ default:
+ print("case-???\n");
+ print("\tord=%d\n", c->ordinal);
+ print("\top=%O\n", c->node->left->op);
+ print("\thash=%ux\n", c->hash);
+ break;
+ }
+ }
+ print("\n");
+}
+
+static int
+ordlcmp(Case *c1, Case *c2)
+{
+ // sort default first
+ if(c1->type == Tdefault)
+ return -1;
+ if(c2->type == Tdefault)
+ return +1;
+
+ // sort nil second
+ if(c1->type == Ttypenil)
+ return -1;
+ if(c2->type == Ttypenil)
+ return +1;
+
+ // sort by ordinal
+ if(c1->ordinal > c2->ordinal)
+ return +1;
+ if(c1->ordinal < c2->ordinal)
+ return -1;
+ return 0;
+}
+
+static int
+exprcmp(Case *c1, Case *c2)
+{
+ int ct, n;
+ Node *n1, *n2;
+
+ // sort non-constants last
+ if(c1->type != Texprconst)
+ return +1;
+ if(c2->type != Texprconst)
+ return -1;
+
+ n1 = c1->node->left;
+ n2 = c2->node->left;
+
+ ct = n1->val.ctype;
+ if(ct != n2->val.ctype)
+ fatal("exprcmp");
+
+ // sort by constant value
+ n = 0;
+ switch(ct) {
+ case CTFLT:
+ n = mpcmpfltflt(n1->val.u.fval, n2->val.u.fval);
+ break;
+ case CTINT:
+ n = mpcmpfixfix(n1->val.u.xval, n2->val.u.xval);
+ break;
+ case CTSTR:
+ n = cmpslit(n1, n2);
+ break;
+ }
+
+ return n;
+}
+
+static int
+typecmp(Case *c1, Case *c2)
+{
+
+ // sort non-constants last
+ if(c1->type != Ttypeconst)
+ return +1;
+ if(c2->type != Ttypeconst)
+ return -1;
+
+ // sort by hash code
+ if(c1->hash > c2->hash)
+ return +1;
+ if(c1->hash < c2->hash)
+ return -1;
+ return 0;
+}
+
+static Case*
+csort(Case *l, int(*f)(Case*, Case*))
+{
+ Case *l1, *l2, *le;
+
+ if(l == C || l->link == C)
+ return l;
+
+ l1 = l;
+ l2 = l;
+ for(;;) {
+ l2 = l2->link;
+ if(l2 == C)
+ break;
+ l2 = l2->link;
+ if(l2 == C)
+ break;
+ l1 = l1->link;
+ }
+
+ l2 = l1->link;
+ l1->link = C;
+ l1 = csort(l, f);
+ l2 = csort(l2, f);
+
+ /* set up lead element */
+ if((*f)(l1, l2) < 0) {
+ l = l1;
+ l1 = l1->link;
+ } else {
+ l = l2;
+ l2 = l2->link;
+ }
+ le = l;
+
+ for(;;) {
+ if(l1 == C) {
+ while(l2) {
+ le->link = l2;
+ le = l2;
+ l2 = l2->link;
+ }
+ le->link = C;
+ break;
+ }
+ if(l2 == C) {
+ while(l1) {
+ le->link = l1;
+ le = l1;
+ l1 = l1->link;
+ }
+ break;
+ }
+ if((*f)(l1, l2) < 0) {
+ le->link = l1;
+ le = l1;
+ l1 = l1->link;
+ } else {
+ le->link = l2;
+ le = l2;
+ l2 = l2->link;
+ }
+ }
+ le->link = C;
+ return l;
+}
4. exprswitchとtypeswitchのロジック変更
--- a/src/cmd/gc/swt.c
+++ b/src/cmd/gc/swt.c
@@ -341,138 +590,138 @@ void
casebody(Node *sw)
{
Iter save;
- Node *os, *oc, *t, *c;
+ Node *os, *oc, *n, *c;
Node *cas, *stat, *def;
Node *go, *br;
int32 lno;
lno = setlineno(sw);
- t = listfirst(&save, &sw->nbody);
- if(t == N || t->op == OEMPTY) {
+ n = listfirst(&save, &sw->nbody);
+ if(n == N || n->op == OEMPTY) {
sw->nbody = nod(OLIST, N, N);
return;
}
cas = N;
stat = N;
def = N;
os = N;
oc = N;
br = nod(OBREAK, N, N);
loop:
- if(t == N) {
+ if(n == N) {
if(oc == N && os != N)
yyerror("first switch statement must be a case");
if(def == N)
def = nod(OCASE, N, nod(OBREAK, N, N));
cas = list(cas, def);
sw->nbody->left = rev(cas);
sw->nbody->right = rev(stat);
return;
}
- lno = setlineno(t);
-
- switch(t->op) {
- case OXCASE:
- t->op = OCASE;
- if(oc == N && os != N)
- yyerror("first switch statement must be a case");
-
- // botch - shouldnt fall thru declaration
- if(os != N && os->op == OXFALL)
- os->op = OFALL;
- else
- stat = list(stat, br);
-
- go = nod(OGOTO, newlabel(), N);
-
- c = t->left;
- if(c == N) {
- if(def != N)
- yyerror("more than one default case");
-
- // reuse original default case
- t->right = go;
- def = t;
- }
-
- // expand multi-valued cases
- for(; c!=N; c=c->right) {
- if(c->op != OLIST) {
- // reuse original case
- t->left = c;
- t->right = go;
- cas = list(cas, t);
- break;
- }
- cas = list(cas, nod(OCASE, c->left, go));
- }
- stat = list(stat, nod(OLABEL, go->left, N));
- oc = t;
- os = N;
- break;
-
- default:
- stat = list(stat, t);
- os = t;
- break;
- }
- t = listnext(&save);
+ lno = setlineno(n);
+
+ if(n->op != OXCASE) {
+ stat = list(stat, n);
+ os = n;
+ goto next;
+ }
+
+ n->op = OCASE;
+ if(oc == N && os != N)
+ yyerror("first switch statement must be a case");
+
+ // botch - shouldnt fall thru declaration
+ if(os != N && os->op == OXFALL)
+ os->op = OFALL;
+ else
+ stat = list(stat, br);
+
+ go = nod(OGOTO, newlabel(), N);
+
+ c = n->left;
+ if(c == N) {
+ if(def != N)
+ yyerror("more than one default case");
+
+ // reuse original default case
+ n->right = go;
+ def = n;
+ }
+
+ // expand multi-valued cases
+ for(; c!=N; c=c->right) {
+ if(c->op != OLIST) {
+ // reuse original case
+ n->left = c;
+ n->right = go;
+ cas = list(cas, n);
+ break;
+ }
+ cas = list(cas, nod(OCASE, c->left, go));
+ }
+ stat = list(stat, nod(OLABEL, go->left, N));
+ oc = n;
+ os = N;
+ goto next;
+
+next:
+ n = listnext(&save);
goto loop;
}
-/*
- * rebulid case statements into if .. goto
- */
-void
-exprswitch(Node *sw, int arg)
+static Node* exprname;
+
+Node*
+exprbsw(Case *c0, int ncase, int arg)
{
Iter save;
- Node *name, *bool, *cas;
- Node *t, *a;
-
- cas = N;
- name = N;
- bool = N;
-
- if(arg != Strue && arg != Sfalse) {
- name = nod(OXXX, N, N);
- tempname(name, sw->ntest->type);
- cas = nod(OAS, name, sw->ntest);
- }
-
- t = listfirst(&save, sw->nbody->left);
-
-loop:
- if(t == N) {
- sw->nbody->left = rev(cas);
- return;
- }
-
- if(t->left == N) {
- cas = list(cas, t->right); // goto default
- t = listnext(&save);
- goto loop;
- }
-
- // pull out the dcl in case this
- // variable is allocated on the heap.
- // this should be done better to prevent
- // multiple (unused) heap allocations per switch.
- if(t->ninit != N && t->ninit->op == ODCL) {
- cas = list(cas, t->ninit);
- t->ninit = N;
- }
-
- switch(arg) {
- default:
- // not bool const
- a = exprbsw(t, &save, name);
- if(a != N)
- break;
-
- a = nod(OIF, N, N);
- a->ntest = nod(OEQ, name, t->left); // if name == val
- a->nbody = t->right; // then goto l
- break;
-
- case Strue:
- a = nod(OIF, N, N);
- a->ntest = t->left; // if val
- a->nbody = t->right; // then goto l
- break;
-
- case Sfalse:
- a = nod(OIF, N, N);
- a->ntest = nod(ONOT, t->left, N); // if !val
- a->nbody = t->right; // then goto l
- break;
- }
- cas = list(cas, a);
-
- t = listnext(&save);
- goto loop;
-}
-
-int
-iscaseconst(Node *t)
-{
- if(t == N || t->left == N)
- return 0;
- switch(consttype(t->left)) {
- case CTFLT:
- case CTINT:
- case CTSTR:
- return 1;
- }
- return 0;
-}
-
-int
-countcase(Node *t, Iter save)
-{
- int n;
-
- // note that the iter is by value,
- // so cases are not really consumed
- for(n=0;; n++) {
- if(!iscaseconst(t))
- return n;
- t = listnext(&save);
- }
-}
-
-Case*
-csort(Case *l, int(*f)(Case*, Case*))
-{
- Case *l1, *l2, *le;
-
- if(l == C || l->link == C)
- return l;
-
- l1 = l;
- l2 = l;
- for(;;) {
- l2 = l2->link;
- if(l2 == C)
- break;
- l2 = l2->link;
- if(l2 == C)
- break;
- l1 = l1->link;
- }
-
- l2 = l1->link;
- l1->link = C;
- l1 = csort(l, f);
- l2 = csort(l2, f);
-
- /* set up lead element */
- if((*f)(l1, l2) < 0) {
- l = l1;
- l1 = l1->link;
- } else {
- l = l2;
- l2 = l2->link;
- }
- le = l;
-
- for(;;) {
- if(l1 == C) {
- while(l2) {
- le->link = l2;
- le = l2;
- l2 = l2->link;
- }
- le->link = C;
- break;
- }
- if(l2 == C) {
- while(l1) {
- le->link = l1;
- le = l1;
- l1 = l1->link;
- }
- break;
- }
- if((*f)(l1, l2) < 0) {
- le->link = l1;
- le = l1;
- l1 = l1->link;
- } else {
- le->link = l2;
- le = l2;
- l2 = l2->link;
- }
- }
- le->link = C;
- return l;
-}
-
-int
-casecmp(Case *c1, Case *c2)
-{
- int ct;
- Node *n1, *n2;
-
- n1 = c1->node->left;
- n2 = c2->node->left;
-
- ct = n1->val.ctype;
- if(ct != n2->val.ctype)
- fatal("casecmp1");
-
- switch(ct) {
- case CTFLT:
- return mpcmpfltflt(n1->val.u.fval, n2->val.u.fval);
- case CTINT:
- return mpcmpfixfix(n1->val.u.xval, n2->val.u.xval);
- case CTSTR:
- return cmpslit(n1, n2);
- }
-
- fatal("casecmp2");
- return 0;
-}
-
-Node*
-constsw(Case *c0, int ncase, Node *name)
-{
- Node *cas, *a;
- Case *c;
- int i, n;
-
- // small number do sequentially
- if(ncase < Ncase) {
- cas = N;
- for(i=0; i<ncase; i++) {
- a = nod(OIF, N, N);
- a->ntest = nod(OEQ, name, c0->node->left);
- a->nbody = c0->node->right;
- cas = list(cas, a);
- c0 = c0->link;
- }
- return rev(cas);
- }
-
- // find center and recur
- c = c0;
- n = ncase>>1;
- for(i=1; i<n; i++)
- c = c->link;
-
- a = nod(OIF, N, N);
- a->ntest = nod(OLE, name, c->node->left);
- a->nbody = constsw(c0, n, name); // include center
- a->nelse = constsw(c->link, ncase-n, name); // exclude center
- return a;
-}
-
-Node*
-exprbsw(Node *t, Iter *save, Node *name)
-{
- Case *c, *c1;
- int i, ncase;
- Node *a;
-
- ncase = countcase(t, *save);
- if(ncase < Ncase)
- return N;
-
- c = C;
- for(i=1; i<ncase; i++) {
- c1 = mal(sizeof(*c1));
- c1->link = c;
- c1->node = t;
- c = c1;
-
- t = listnext(save);
- }
-
- // last one shouldnt consume the iter
- c1 = mal(sizeof(*c1));
- c1->link = c;
- c1->node = t;
- c = c1;
-
- c = csort(c, casecmp);
- a = constsw(c, ncase, name);
- return a;
-}
-
-int
-hashcmp(Case *c1, Case *c2)
-{
-
- if(c1->hash > c2->hash)
- return +1;
- if(c1->hash < c2->hash)
- return -1;
- return 0;
-}
-
-int
-counthash(Case *c)
-{
- Case *c1, *c2;
- Type *t1, *t2;
- char buf1[NSYMB], buf2[NSYMB];
- int ncase;
-
- ncase = 0;
- while(c != C) {
- c->uniq = 1;
- ncase++;
-
- for(c1=c->link; c1!=C; c1=c1->link) {
- if(c->hash != c1->hash)
- break;
-
- // c1 is a non-uniq hash
- // compare its type to all types c upto c1
- for(c2=c; c2!=c1; c2=c2->link) {
- if(c->diag)
- continue;
- t1 = c1->node->left->left->type;
- t2 = c2->node->left->left->type;
- if(!eqtype(t1, t2, 0))
- continue;
- snprint(buf1, sizeof(buf1), "%#T", t1);
- snprint(buf2, sizeof(buf2), "%#T", t2);
- if(strcmp(buf1, buf2) != 0)
- continue;
- setlineno(c1->node);
- yyerror("duplicate type case: %T\n", t1);
- c->diag = 1;
- }
- }
- c = c1;
- }
- return ncase;
-}
-
-Case*
-nextuniq(Case *c)
-{
- for(c=c->link; c!=C; c=c->link)
- if(c->uniq)
- return c;
- return C;
-}
-
-static Node* hashname;
-static Node* facename;
-static Node* boolname;
-static Node* gotodefault;
-
-Node*
-typebsw(Case *c0, int ncase)
-{
- Node *cas, *cmp;
- Node *a, *b, *t;
- Case *c, *c1;
- int i, n;
-
- cas = N;
-
- if(ncase < Ncase) {
- for(i=0; i<ncase; i++) {
- c1 = nextuniq(c0);
- cmp = N;
- for(c=c0; c!=c1; c=c->link) {
- t = c->node;
-
- if(t->left->left == N) {
- // case nil
- Val v;
- v.ctype = CTNIL;
- a = nod(OIF, N, N);
- a->ntest = nod(OEQ, facename, nodlit(v));
- a->nbody = t->right; // if i==nil { goto l }
- cmp = list(cmp, a);
- continue;
- }
-
- a = t->left->left; // var
- a = nod(OLIST, a, boolname); // var,bool
-
- b = nod(ODOTTYPE, facename, N);
- b->type = t->left->left->type; // interface.(type)
-
- a = nod(OAS, a, b); // var,bool = interface.(type)
- cmp = list(cmp, a);
-
- a = nod(OIF, N, N);
- a->ntest = boolname;
- a->nbody = t->right; // if bool { goto l }
- cmp = list(cmp, a);
- }
- cmp = list(cmp, gotodefault);
- a = nod(OIF, N, N);
- a->ntest = nod(OEQ, hashname, nodintconst(c0->hash));
- a->nbody = rev(cmp);
- cas = list(cas, a);
- c0 = c1;
- }
- cas = list(cas, gotodefault);
- return rev(cas);
- }
-
- // find the middle and recur
- c = c0;
- n = ncase>>1;
- for(i=1; i<n; i++)
- c = nextuniq(c);
- a = nod(OIF, N, N);
- a->ntest = nod(OLE, hashname, nodintconst(c->hash));
- a->nbody = typebsw(c0, n);
- a->nelse = typebsw(nextuniq(c), ncase-n);
- return a;
-}
-
-@@ -695,10 +758,9 @@ typebsw(Case *c0, int ncase)
void
typeswitch(Node *sw)
{
- Iter save;
- Node *cas;
- Node *t, *a;
- Case *c, *c1;
+ Node *cas;
+ Node *a, *n;
+ Case *c;
+ int i, half;
+ Val v;
+
+ cas = N;
+
+ if(ncase < Ncase) {
+ for(i=0; i<ncase; i++) {
+ n = c0->node;
+
+ switch(c0->type) {
+
+ case Ttypenil:
+ v.ctype = CTNIL;
+ a = nod(OIF, N, N);
+ a->ntest = nod(OEQ, facename, nodlit(v));
+ a->nbody = n->right; // if i==nil { goto l }
+ cas = list(cas, a);
+ break;
+
+ case Ttypevar:
+ a = typeone(n);
+ cas = list(cas, a);
+ break;
+
+ case Ttypeconst:
+ a = nod(OIF, N, N);
+ a->ntest = nod(OEQ, hashname, nodintconst(c0->hash));
+ a->nbody = rev(typeone(n));
+ cas = list(cas, a);
+ break;
+ }
+ c0 = c0->link;
+ }
+ return cas;
+ }
+
+ // find the middle and recur
+ c = c0;
+ half = ncase>>1;
+ for(i=1; i<half; i++)
+ c = c->link;
+ a = nod(OIF, N, N);
+ a->ntest = nod(OLE, hashname, nodintconst(c->hash));
+ a->nbody = typebsw(c0, half);
+ a->nelse = typebsw(c->link, ncase-half);
+ return a;
+}
+
+/*
+ * normal (expression) switch.
+ * rebulid case statements into if .. goto
+ */
+void
+exprswitch(Node *sw)
+{
+ Node *def, *cas;
+ Node *a;
+ Case *c0, *c, *c1;
+ Type *t;
+ int arg, ncase;
+
+ arg = Snorm;
+ if(isconst(sw->ntest, CTBOOL)) {
+ arg = Strue;
+ if(sw->ntest->val.u.bval == 0)
+ arg = Sfalse;
+ }
+ walktype(sw->ntest, Erv);
+
+ /*
+ * convert the switch into OIF statements
+ */
+ exprname = N;
+ cas = N;
+ if(arg != Strue && arg != Sfalse) {
+ exprname = nod(OXXX, N, N);
+ tempname(exprname, sw->ntest->type);
+ cas = nod(OAS, exprname, sw->ntest);
+ }
+
+ c0 = mkcaselist(sw, arg);
+ if(c0 != C && c0->type == Tdefault) {
+ def = c0->node->right;
+ c0 = c0->link;
+ } else {
+ def = nod(OBREAK, N, N);
+ }
+
+loop:
+ if(c0 == C) {
+ cas = list(cas, def);
+ sw->nbody->left = rev(cas);
+ walkstate(sw->nbody);
+ return;
+ }
+
+ // deal with the variables one-at-a-time
+ if(c0->type != Texprconst) {
+ a = exprbsw(c0, 1, arg);
+ cas = list(cas, a);
+ c0 = c0->link;
+ goto loop;
+ }
+
+ // do binary search on run of constants
+ ncase = 1;
+ for(c=c0; c->link!=C; c=c->link) {
+ if(c->link->type != Texprconst)
+ break;
+ ncase++;
+ }
+
+ // break the chain at the count
+ c1 = c->link;
+ c->link = C;
+
+ // sort and compile constants
+ c0 = csort(c0, exprcmp);
+ a = exprbsw(c0, ncase, arg);
+ cas = list(cas, a);
+
+ c0 = c1;
+ goto loop;
+}
+
+static Node* hashname;
+static Node* facename;
+static Node* boolname;
+
+Node*
+typeone(Node *t)
+{
+ Node *a, *b;
+
+ a = t->left->left; // var
+ a = nod(OLIST, a, boolname); // var,bool
+
+ b = nod(ODOTTYPE, facename, N);
+ b->type = t->left->left->type; // interface.(type)
+
+ a = nod(OAS, a, b); // var,bool = interface.(type)
+
+ b = nod(OIF, N, N);
+ b->ntest = boolname;
+ b->nbody = t->right; // if bool { goto l }
+ return list(a, b);
+}
+
+void
+typeswitch(Node *sw)
+{
+ Node *cas, *def;
+ Node *a;
+ Case *c, *c0, *c1;
int ncase;
walktype(sw->ntest->right, Erv);
@@ -730,40 +792,68 @@ typeswitch(Node *sw)
a = nod(OAS, hashname, a);
cas = list(cas, a);
- gotodefault = N;
-
- c = C;
- t = listfirst(&save, &sw->nbody->left);
+ c0 = mkcaselist(sw, Stype);
+ if(c0 != C && c0->type == Tdefault) {
+ def = c0->node->right;
+ c0 = c0->link;
+ } else {
+ def = nod(OBREAK, N, N);
+ }
loop:
- if(t == N) {
- if(gotodefault == N)
- gotodefault = nod(OBREAK, N, N);
- c = csort(c, hashcmp);
- ncase = counthash(c);
- a = typebsw(c, ncase);
- sw->nbody->left = list(rev(cas), rev(a));
+ if(c0 == C) {
+ cas = list(cas, def);
+ sw->nbody->left = rev(cas);
walkstate(sw->nbody);
return;
}
- if(t->left == N) {
- gotodefault = t->right;
- t = listnext(&save);
+
+ // deal with the variables one-at-a-time
+ if(c0->type != Ttypeconst) {
+ a = typebsw(c0, 1);
+ cas = list(cas, a);
+ c0 = c0->link;
goto loop;
}
- if(t->left->op != OTYPESW) {
- t = listnext(&save);
+
+ // do binary search on run of constants
+ ncase = 1;
+ for(c=c0; c->link!=C; c=c->link) {
+ if(c->link->type != Ttypeconst)
+ break;
+ ncase++;
}
- c1 = mal(sizeof(*c));
- c1->link = c;
- c1->node = t;
- c1->hash = 0;
- if(t->left->left != N)
- c1->hash = typehash(t->left->left->type, 1, 0);
- c = c1;
-
- t = listnext(&save);
+ // break the chain at the count
+ c1 = c->link;
+ c->link = C;
+
+ // sort and compile constants
+ c0 = csort(c0, typecmp);
+ a = typebsw(c0, ncase);
+ cas = list(cas, a);
+
+ c0 = c1;
goto loop;
}
+
+void
+walkswitch(Node *sw)
+{
+
+ /*
+ * reorder the body into (OLIST, cases, statements)
+ * cases have OGOTO into statements.
+ * both have inserted OBREAK statements
+ */
+ walkstate(sw->ninit);
+ if(sw->ntest == N)
+ sw->ntest = nodbool(1);
+ casebody(sw);
+
+ if(sw->ntest->op == OTYPESW) {
+ typeswitch(sw);
+ return;
+ }
+ exprswitch(sw);
+}
コアとなるコードの解説
1. Case構造体の変更
Case構造体にtypeとordinalフィールドが追加されたことで、switch文の各caseが持つ意味的な情報（定数、変数、型など）と、ソースコード上での元の位置をコンパイラが内部的に追跡できるようになりました。これにより、より複雑なswitch文の最適化や、正確なエラー報告が可能になります。
2. mkcaselist関数
この関数は、switch文のASTを走査し、各case節に対応するCase構造体を生成してリンクドリストに連結します。
特に注目すべきは、switch(arg)ブロックです。
Stypeの場合（型switch）:case nil(Ttypenil)、インターフェース型変数 (Ttypevar)、具体的な型定数 (Ttypeconst) を区別し、それぞれに適切なtypeとhashを設定します。Snorm,Strue,Sfalseの場合（式switch）:caseが定数式 (Texprconst) か、変数または非定数式 (Texprvar) かを判断し、typeを設定します。 この関数は、Caseリストを構築した後、重複するcaseがないかをチェックし、もしあればコンパイルエラーを報告します。最後に、ordlcmpを使ってリストを元の出現順序にソートし直します。これは、後続の処理でcaseの元の順序が重要になるためです。
3. csortと新しい比較関数
csortは、引数として渡された比較関数に基づいてリンクドリストをソートする汎用的なマージソートの実装です。
ordlcmp:Caseのordinal（元の出現順序）に基づいてソートします。defaultケースとnilケースを特別扱いし、リストの先頭に配置します。これは、mkcaselistでソートされたリストを元の処理順序に戻すために使われます。exprcmp: 式switchの定数caseをその値に基づいてソートします。これにより、定数caseに対して二分探索のような効率的な分岐戦略を適用できるようになります。typecmp: 型switchの型定数caseをそのハッシュ値に基づいてソートします。これにより、型caseに対しても効率的な分岐戦略を適用できるようになります。
これらの関数は、switch文のコンパイルにおいて、caseの特性に応じた最適なコード生成を可能にするための基盤となります。
4. exprswitchとtypeswitchの新しいロジック
これらの関数は、mkcaselistで構築されたCaseリストと、csortでソートされたリストを活用して、switch文を最終的なif-else ifの連鎖や二分探索ツリーに変換します。
exprswitch:- まず、
mkcaselistを呼び出してCaseリストを取得します。 caseがTexprconst（定数式）の場合、exprcmpでソートされたリストに対してexprbswを呼び出し、二分探索ツリーを構築します。これにより、多数の定数caseがある場合でも高速な分岐が実現されます。caseがTexprvar（変数または非定数式）の場合、exprbswをncase=1で呼び出し、単純なif文に変換します。これは、非定数式に対する線形探索に相当します。- 最終的に、生成された
if-else if構造がsw->nbody->leftに設定され、コンパイラの次のフェーズで処理されます。
- まず、
typeswitch:- 同様に、
mkcaselistを呼び出してCaseリストを取得します。 caseがTtypeconst（型定数）の場合、typecmpでソートされたリストに対してtypebswを呼び出し、型ハッシュに基づく二分探索ツリーを構築します。Ttypenil（case nil）やTtypevar（インターフェース型変数）のような特殊な型caseは、typeone関数によって個別に処理され、適切な型アサーションとif文に変換されます。- これにより、型
switchも効率的かつ正確にコンパイルされるようになりました。
- 同様に、
これらの変更により、Goコンパイラはswitch文の多様な使用パターンに対応し、定数caseに対しては最適化されたコードを生成し、非定数caseや型caseに対しても正しいセマンティクスを維持できるようになりました。特に、バグ141で指摘されていた非定数caseの問題が、Texprvarの導入とそれに対応する処理ロジックによって解決されています。
関連リンク
- Go Issue 141: switch statement with non-constant case labels
- Go Language Specification - Switch statements (現在の仕様)
参考にした情報源リンク
- Go Issue 141
- Go言語のソースコード (特に
src/cmd/gc/swt.cとsrc/cmd/gc/go.yのコミット前後の差分) - コンパイラの設計と実装に関する一般的な知識 (AST, 中間表現, コード生成, 最適化)
- Yacc/Bisonに関する一般的な知識
- マージソートアルゴリズムに関する一般的な知識