[インデックス 1838] ファイルの概要
このコミットは、Goコンパイラとランタイムにおける型スイッチ（type switch）の挙動を大幅に改善し、新たな機能を追加するものです。具体的には、型スイッチの内部処理に二分探索を導入することで、コンパイルされたコードの効率を向上させています。また、型スイッチにおいて case nil: という新しい構文を導入し、インターフェースが nil である場合にそのケースにマッチするようにしました。
コミット
commit 0f469a99a3d50c2711fe8159af5f2ee125aa2837
Author: Ken Thompson <ken@golang.org>
Date: Tue Mar 17 13:58:38 2009 -0700
binary search on type switches.
new feature 'case nil:' in type switch
will match iff the interface is nil.
R=r
OCL=26404
CL=26404
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/0f469a99a3d50c2711fe8159af5f2ee125aa2837
元コミット内容
binary search on type switches.
new feature 'case nil:' in type switch
will match iff the interface is nil.
R=r
OCL=26404
CL=26404
変更の背景
Go言語の初期段階において、型スイッチは一連の if-else if 文に変換されていました。これは、ケースの数が増えるにつれて線形的な探索となり、コンパイルされたコードの実行効率が低下する可能性がありました。特に、多数の型ケースを持つ型スイッチでは、パフォーマンスのボトルネックとなることが懸念されます。
このコミットの主な目的は、この非効率性を解消し、型スイッチのパフォーマンスを向上させることにあります。具体的には、型スイッチのケースを効率的に探索するために、二分探索アルゴリズムを導入しました。これにより、ケースの数が増えても探索時間が対数的に増加するようになり、大規模な型スイッチでも高速な実行が期待できるようになります。
また、インターフェースの nil 値を直接型スイッチで扱えるようにすることも重要な改善点でした。Goのインターフェースは、型と値のペアで構成されており、両方が nil の場合にのみインターフェース自体が nil となります。しかし、型スイッチで nil を直接ケースとして指定する構文は存在しませんでした。この変更により、インターフェースが nil である状態を明示的に捕捉し、それに応じた処理を記述できるようになり、コードの可読性と堅牢性が向上しました。
前提知識の解説
このコミットを理解するためには、以下のGo言語およびコンパイラの概念に関する知識が必要です。
-
Goのインターフェース: Goのインターフェースは、メソッドのシグネチャの集合を定義します。インターフェース型の変数は、そのインターフェースが要求するすべてのメソッドを実装する任意の具象型の値を保持できます。インターフェースは内部的に「型情報」と「値」の2つのポインタ（またはワード）で構成されます。
- 型情報 (Type): 保持されている具象型の情報（
_type構造体へのポインタ）。 - 値 (Value): 保持されている具象値へのポインタ。
インターフェース変数が
nilであるとは、この両方のポインタがnilである状態を指します。
- 型情報 (Type): 保持されている具象型の情報（
-
型スイッチ (Type Switch): Goの型スイッチは、インターフェース変数が保持している具象型に基づいて異なるコードブロックを実行するための制御構造です。
switch v := i.(type) { case int: // i は int 型 case string: // i は string 型 default: // その他の型 }これまでの実装では、各
caseはi.(type)の結果と線形に比較されていました。 -
ハッシュ関数と型ハッシュ: コンパイラやランタイムでは、型の比較や識別を高速化するためにハッシュ値が利用されることがあります。
typehash関数は、Goの型構造から一意のハッシュ値を生成するために使用されます。このハッシュ値は、型の等価性チェックや、今回の型スイッチのように効率的な探索メカニズムを構築する際に役立ちます。 -
二分探索 (Binary Search): ソートされたデータ構造から特定の要素を効率的に探索するためのアルゴリズムです。探索範囲を半分に絞り込むことを繰り返すため、要素数が
Nの場合、探索時間はO(log N)となります。型スイッチのケースをハッシュ値でソートし、二分探索を適用することで、探索効率を大幅に向上させることができます。 -
Goコンパイラの構造 (gc): Goの公式コンパイラは
gcと呼ばれ、src/cmd/gcディレクトリにそのソースコードがあります。go.y: Go言語の文法定義（Yacc/Bison形式）。構文解析器が生成されます。swt.c:switch文のコンパイルロジックを扱うファイル。subr.c: サブルーチンやユーティリティ関数（typehashなど）を含むファイル。obj.c: オブジェクトコード生成に関連するファイル。sys.go: ランタイムとコンパイラ間のインターフェースとなる組み込み関数を定義するファイル。runtime/iface.c: インターフェースの内部処理（型アサーション、比較など）を実装するランタイムファイル。
技術的詳細
このコミットは、主に以下の技術的変更によって型スイッチの改善を実現しています。
-
typehash関数の拡張:src/cmd/gc/subr.cにあるtypehash関数がtypehash(Type *at, int addsym, int d)に変更されました。新しいaddsymパラメータは、型のハッシュ計算にシンボル名（at->sym->name）を含めるかどうかを制御します。これにより、型のハッシュがより一意になり、特にインターフェースのメソッドシグネチャのハッシュ計算において、名前による区別が可能になります。src/cmd/6g/obj.cのdumpsigt関数など、既存のtypehashの呼び出し箇所もこの新しいシグネチャに合わせて更新されています。 -
sys.ifacethashランタイム関数の導入:src/cmd/gc/builtin.c.bootとsrc/cmd/gc/sys.goで宣言され、src/runtime/iface.cで実装されたsys.ifacethashという新しいランタイム関数が追加されました。この関数は、与えられたインターフェース値の型情報からハッシュ値（Itype->sigt->thash）を取得します。このハッシュ値は、型スイッチの二分探索において、インターフェースが保持する具象型を効率的に識別するために使用されます。インターフェースがnilの場合、または型情報がnilの場合は0を返します。 -
型スイッチの二分探索への変換 (
src/cmd/gc/swt.c):src/cmd/gc/swt.cのtypeswitch関数が大幅に書き直されました。Case構造体: 型スイッチの各caseを表現するための新しいCase構造体が導入されました。これには、元のノード (node)、型のハッシュ値 (hash)、ユニーク性フラグ (uniq)、診断フラグ (diag)、および次のケースへのリンク (link) が含まれます。- ケースの収集とハッシュ計算:
typeswitch関数は、まずすべてのcase文を走査し、それぞれの具象型に対応するCase構造体を作成します。この際、typehash関数を使用して各型のハッシュ値を計算し、Case構造体のhashフィールドに格納します。 case nil:のサポート:src/cmd/gc/go.yでcase nil:構文が追加され、typeswitch関数内でインターフェース値がnilであるかをチェックする特殊なケースとして扱われます。これは、インターフェース変数がnilであるかどうかを直接比較することで実現されます。- ケースのソート: 収集された
Case構造体のリストは、hashcmp関数（ハッシュ値に基づいて比較）を使用してソートされます。これにより、二分探索の前提条件が満たされます。 - 重複ケースの検出:
counthash関数は、ソートされたリストを走査し、同じハッシュ値を持つ重複する型ケースを検出します。これはコンパイル時のエラーとして報告されます。 - 二分探索ツリーの構築 (
typebsw):typebsw関数は、ソートされたケースのリストとハッシュ値に基づいて、二分探索ツリーに相当するOIF(if文) のネストされた構造を生成します。- まず、
sys.ifacethashを呼び出してインターフェースのハッシュ値を取得し、一時変数hashnameに格納します。 - 次に、この
hashnameを使用して、二分探索ツリーをトラバースし、適切なcaseにジャンプします。 Ncase(デフォルトは4) 以下の少数のケースでは、線形探索（一連のif文）にフォールバックします。これは、二分探索のオーバーヘッドが線形探索のメリットを上回る可能性があるためです。- 各
caseブロック内では、インターフェースから具象型への型アサーション（interface.(type)）が行われ、その結果が成功したかどうかを示すブール値がboolnameに格納されます。このboolnameを使用して、最終的なif文が生成され、対応するcaseのコードブロックにジャンプします。
- まず、
これらの変更により、Goコンパイラは型スイッチをより効率的な二分探索ベースのコードに変換できるようになり、実行時のパフォーマンスが向上します。
コアとなるコードの変更箇所
このコミットにおける主要なコード変更箇所は以下の通りです。
src/cmd/gc/go.y:complex_stmtルールにcase nil:の構文解析ロジックが追加されました。pexprルールから不要な空行が削除されました。
src/cmd/gc/go.h:typehash関数のプロトタイプがuint32 typehash(Type*, int, int);に変更されました。
src/cmd/gc/subr.c:typehash関数のシグネチャがtypehash(Type *at, int addsym, int d)に変更され、addsymパラメータが追加されました。typehashの実装に、addsymが真の場合にシンボル名をハッシュに含めるロジックが追加されました。ifaceokT2IおよびifaceokI2I内のtypehashの呼び出しが更新されました。
src/cmd/gc/swt.c:typeswitch関数が完全に書き直され、二分探索ロジックが導入されました。Case構造体、hashcmp、counthash、nextuniq、typebswといった新しいヘルパー関数が追加されました。binarysw関数がexprbswにリネームされ、exprswitchから呼び出されるようになりました。
src/cmd/gc/sys.go:func ifacethash(i1 any) (ret uint32);が宣言されました。
src/runtime/iface.c:sys·ifacethash関数が実装されました。この関数はインターフェースの型情報からthashを取得します。
src/cmd/6g/obj.c:dumpsigtおよびdumpsigi関数内のtypehashの呼び出しが、新しいシグネチャに合わせて更新されました。
コアとなるコードの解説
src/cmd/gc/go.y (抜粋)
--- a/src/cmd/gc/go.y
+++ b/src/cmd/gc/go.y
@@ -484,6 +484,13 @@ complex_stmt:
// right will point to next case
// done in casebody()
poptodcl();
+ if(typeswvar != N && typeswvar->right != N)
+ if($2->op == OLITERAL && $2->val.ctype == CTNIL) {
+ // this version in type switch case nil
+ $$ = nod(OTYPESW, N, N);
+ $$ = nod(OXCASE, $$, N);
+ break;
+ }
$$ = nod(OXCASE, $2, N);
}
| LCASE name '=' expr ':'
この変更は、Goの文法定義ファイル go.y において、型スイッチの case 節で nil リテラルを許可するためのものです。$2 は case の式を表し、それが OLITERAL (リテラル) かつ CTNIL (nil定数) である場合に、特別な OTYPESW ノードと OXCASE ノードを生成します。これにより、コンパイラが case nil: を正しく認識し、後続の処理でインターフェースが nil であるかをチェックするロジックに繋がります。
src/cmd/gc/subr.c の typehash 関数 (抜粋)
--- a/src/cmd/gc/subr.c
+++ b/src/cmd/gc/subr.c
@@ -1919,7 +1919,7 @@ eqargs(Type *t1, Type *t2)
}
uint32
-typehash(Type *at, int d)
+typehash(Type *at, int addsym, int d)
{
uint32 h;
Type *t;
@@ -1931,20 +1931,23 @@ typehash(Type *at, int d)
h = at->etype*PRIME4;
+ if(addsym && at->sym != S)
+ h += stringhash(at->sym->name);
+
switch(at->etype) {
default:
- h += PRIME5 * typehash(at->type, d+1);
+ h += PRIME5 * typehash(at->type, addsym, d+1);
break;
case TINTER:
// botch -- should be sorted?
for(t=at->type; t!=T; t=t->down)
- h += PRIME6 * typehash(t, d+1);
+ h += PRIME6 * typehash(t, addsym, d+1);
break;
case TSTRUCT:
for(t=at->type; t!=T; t=t->down)
- h += PRIME7 * typehash(t, d+1);
+ h += PRIME7 * typehash(t, addsym, d+1);
break;
case TFUNC:
@@ -1953,7 +1956,7 @@ typehash(Type *at, int d)
if(t != T)
t = t->down;
for(; t!=T; t=t->down)
- h += PRIME7 * typehash(t, d+1);
+ h += PRIME7 * typehash(t, addsym, d+1);
break;
}
typehash 関数は、Goの型構造からハッシュ値を計算します。この変更では、addsym という新しいパラメータが追加されました。addsym が真（1）の場合、型のシンボル名（at->sym->name）のハッシュ値が全体のハッシュに加算されます。これは、特にインターフェースのメソッドのハッシュを計算する際に、メソッド名もハッシュに含めることで、より正確なハッシュ値を生成するために使用されます。再帰的な呼び出しも addsym パラメータを伝播させます。
src/cmd/gc/swt.c の typeswitch 関数 (抜粋)
--- a/src/cmd/gc/swt.c
+++ b/src/cmd/gc/swt.c
@@ -10,8 +10,22 @@ enum
Strue,
Sfalse,
Stype,
+
+ Ncase = 4, // needed to binary search
+};
+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 diag; // suppress multiple diagnostics
+ Case* link; // linked list to link
+};
+#define C ((Case*)nil)
/*
* walktype
@@ -351,96 +361,12 @@ loop:
}
void
-typeswitch(Node *sw)
-{
- Iter save;
- Node *face, *bool, *cas;
- Node *t, *a, *b;
-
-//dump("typeswitch", sw);
-
- walktype(sw->ntest->right, Erv);
- if(!istype(sw->ntest->right->type, TINTER)) {
- yyerror("type switch must be on an interface");
- return;
- }
- walkcases(sw, sw0, Stype);
-
- /*
- * predeclare variables for the interface var
- * and the boolean var
- */
- face = nod(OXXX, N, N);
- tempname(face, sw->ntest->right->type);
- cas = nod(OAS, face, sw->ntest->right);
-
- bool = nod(OXXX, N, N);
- tempname(bool, types[TBOOL]);
-
- t = listfirst(&save, &sw->nbody->left);
-
-loop:
- if(t == N) {
- sw->nbody->left = rev(cas);
- walkstate(sw->nbody);
-//dump("done", sw->nbody->left);
- return;
- }
-
- if(t->left == N) {
- cas = list(cas, t->right); // goto default
- t = listnext(&save);
- goto loop;
- }
- if(t->left->op != OTYPESW) {
- 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.
- // not worth doing now -- make a binary search
- // on contents of signature instead.
- if(t->ninit != N && t->ninit->op == ODCL) {
-//dump("typeswitch case init", t->ninit);
- cas = list(cas, t->ninit);
- t->ninit = N;
- }
-
- a = t->left->left; // var
- a = nod(OLIST, a, bool); // var,bool
-
- b = nod(ODOTTYPE, face, N);
- b->type = t->left->left->type; // interface.(type)
-
- a = nod(OAS, a, b); // var,bool = interface.(type)
- cas = list(cas, a);
-
- a = nod(OIF, N, N);
- a->ntest = bool;
- a->nbody = t->right; // if bool { goto l }
- cas = list(cas, a);
-
- t = listnext(&save);
- goto loop;
-}
-
-void
walkswitch(Node *sw)
{
Type *t;
int arg;
-//dump("walkswitch", sw);
-
/*
* reorder the body into (OLIST, cases, statements)
* cases have OGOTO into statements.
@@ -492,32 +417,14 @@ walkswitch(Node *sw)
* convert the switch into OIF statements
*/
exprswitch(sw, arg);
- walkstate(sw->nbody);
-//print("normal done\\n");
+ walkstate(sw->nbody);
}
-/*
- * binary search on cases
- */
-enum
-{
- Ncase = 4, // needed to binary search
-};
-
-typedef struct Case Case;\nstruct Case\n{\n\tNode*\tnode;\t\t// points at case statement\n\tCase*\tlink;\t\t// linked list to link\n};\n-#define\tC\t((Case*)nil)\n-\n int
iscaseconst(Node *t)
{
@@ -662,18 +569,18 @@ constsw(Case *c0, int ncase, Node *name)
// find center and recur
c = c0;
n = ncase>>1;
- for(i=0; i<n; i++)
+ 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+1, name); // include center
- a->nelse = constsw(c->link, ncase-n-1, name); // exclude center
+ a->nbody = constsw(c0, n, name); // include center
+ a->nelse = constsw(c->link, ncase-n, name); // exclude center
return a;
}
Node*
-binarysw(Node *t, Iter *save, Node *name)
+exprbsw(Node *t, Iter *save, Node *name)
{
Case *c, *c1;
int i, ncase;
@@ -701,6 +608,216 @@ binarysw(Node *t, Iter *save, Node *name)
c = csort(c, casecmp);
a = constsw(c, ncase, name);
-//dump("bin", a);\n return a;\n }\n+\n+int\n+hashcmp(Case *c1, Case *c2)\n+{\n+\n+\tif(c1->hash > c2->hash)\n+\t\treturn +1;\n+\tif(c1->hash < c2->hash)\n+\t\treturn -1;\n+\treturn 0;\n+}\n+\n+int\n+counthash(Case *c)\n+{\n+\tCase *c1, *c2;\n+\tType *t1, *t2;\n+\tchar buf1[NSYMB], buf2[NSYMB];\n+\tint ncase;\n+\n+\tncase = 0;\n+\twhile(c != C) {\n+\t\tc->uniq = 1;\n+\t\tncase++;\n+\n+\t\tfor(c1=c->link; c1!=C; c1=c1->link) {\n+\t\t\tif(c->hash != c1->hash)\n+\t\t\t\tbreak;\n+\n+\t\t\t// c1 is a non-unique hash\n+\t\t\t// compare its type to all types c upto c1\n+\t\t\tfor(c2=c; c2!=c1; c2=c2->link) {\n+\t\t\t\tif(c->diag)\n+\t\t\t\t\tcontinue;\n+\t\t\t\tt1 = c1->node->left->left->type;\n+\t\t\t\tt2 = c2->node->left->left->type;\n+\t\t\t\tif(!eqtype(t1, t2, 0))\n+\t\t\t\t\tcontinue;\n+\t\t\t\tsnprint(buf1, sizeof(buf1), "%#T", t1);\n+\t\t\t\tsnprint(buf2, sizeof(buf2), "%#T", t2);\n+\t\t\t\tif(strcmp(buf1, buf2) != 0)\n+\t\t\t\t\tcontinue;\n+\t\t\t\tsetlineno(c1->node);\n+\t\t\t\tyyerror("duplicate type case: %T\\n", t1);\n+\t\t\t\tc->diag = 1;\n+\t\t\t}\n+\t\t}\n+\t\tc = c1;\n+\t}\n+\treturn ncase;\n+}\n+\n+Case*\n+nextuniq(Case *c)\n+{\n+\tfor(c=c->link; c!=C; c=c->link)\n+\t\tif(c->uniq)\n+\t\t\treturn c;\n+\treturn C;\n+}\n+\n+static Node* hashname;\n+static Node* facename;\n+static Node* boolname;\n+static Node* gotodefault;\n+\n+Node*\n+typebsw(Case *c0, int ncase)\n+{\n+\tNode *cas, *cmp;\n+\tNode *a, *b, *t;\n+\tCase *c, *c1;\n+\tint i, n;\n+\n+\tcas = N;\n+\n+\tif(ncase < Ncase) {\n+\t\tfor(i=0; i<ncase; i++) {\n+\t\t\tc1 = nextuniq(c0);\n+\t\t\tcmp = N;\n+\t\t\tfor(c=c0; c!=c1; c=c->link) {\n+\t\t\t\tt = c->node;\n+\n+\t\t\t\tif(t->left->left == N) {\n+\t\t\t\t\t// case nil\n+\t\t\t\t\tVal v;\n+\t\t\t\t\tv.ctype = CTNIL;\n+\t\t\t\t\ta = nod(OIF, N, N);\n+\t\t\t\t\ta->ntest = nod(OEQ, facename, nodlit(v));\n+\t\t\t\t\ta->nbody = t->right; // if i==nil { goto l }\n+\t\t\t\t\tcmp = list(cmp, a);\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\n+\t\t\t\ta = t->left->left; // var\n+\t\t\t\ta = nod(OLIST, a, boolname); // var,bool\n+\n+\t\t\t\tb = nod(ODOTTYPE, facename, N);\n+\t\t\t\tb->type = t->left->left->type; // interface.(type)\n+\n+\t\t\t\ta = nod(OAS, a, b); // var,bool = interface.(type)\n+\t\t\t\tcmp = list(cmp, a);\n+\n+\t\t\t\ta = nod(OIF, N, N);\n+\t\t\t\ta->ntest = boolname;\n+\t\t\t\ta->nbody = t->right; // if bool { goto l }\n+\t\t\t\tcmp = list(cmp, a);\n+\t\t\t}\n+\t\t\tcmp = list(cmp, gotodefault);\n+\t\t\ta = nod(OIF, N, N);\n+\t\t\ta->ntest = nod(OEQ, hashname, nodintconst(c0->hash));\n+\t\t\ta->nbody = rev(cmp);\n+\t\t\tcas = list(cas, a);\n+\t\t\tc0 = c1;\n+\t\t}\n+\t\tcas = list(cas, gotodefault);\n+\t\treturn rev(cas);\n+\t}\n+\n+\t// find the middle and recur\n+\tc = c0;\n+\tn = ncase>>1;\n+\tfor(i=1; i<n; i++)\n+\t\tc = nextuniq(c);\n+\ta = nod(OIF, N, N);\n+\ta->ntest = nod(OLE, hashname, nodintconst(c->hash));\n+\ta->nbody = typebsw(c0, n);\n+\ta->nelse = typebsw(nextuniq(c), ncase-n);\n+\treturn a;\n+}\n+\n+/*\n+ * convert switch of the form\n+ *\tswitch v := i.(type) { case t1: ..; case t2: ..; }\n+ * into if statements\n+ */\n+void\n+typeswitch(Node *sw)\n+{\n+\tIter save;\n+\tNode *cas;\n+\tNode *t, *a;\n+\tCase *c, *c1;\n+\tint ncase;\n+\n+\twalktype(sw->ntest->right, Erv);\n+\tif(!istype(sw->ntest->right->type, TINTER)) {\n+\t\tyyerror("type switch must be on an interface");\n+\t\treturn;\n+\t}\n+\twalkcases(sw, sw0, Stype);\n+\tcas = N;\n+\n+\t/*\n+\t * predeclare temporary variables\n+\t * and the boolean var\n+\t */\n+\tfacename = nod(OXXX, N, N);\n+\ttempname(facename, sw->ntest->right->type);\n+\ta = nod(OAS, facename, sw->ntest->right);\n+\tcas = list(cas, a);\n+\n+\tboolname = nod(OXXX, N, N);\n+\ttempname(boolname, types[TBOOL]);\n+\n+\thashname = nod(OXXX, N, N);\n+\ttempname(hashname, types[TUINT32]);\n+\n+\ta = syslook("ifacethash", 1);\n+\targtype(a, sw->ntest->right->type);\n+\ta = nod(OCALL, a, sw->ntest->right);\n+\ta = nod(OAS, hashname, a);\n+\tcas = list(cas, a);\n+\n+\tgotodefault = N;\n+\n+\tc = C;\n+\tt = listfirst(&save, &sw->nbody->left);\n+\n+loop:\n+\tif(t == N) {\n+\t\tif(gotodefault == N)\n+\t\t\tgotodefault = nod(OBREAK, N, N);\n+\t\tc = csort(c, hashcmp);\n+\t\tncase = counthash(c);\n+\t\ta = typebsw(c, ncase);\n+\t\tsw->nbody->left = list(rev(cas), rev(a));\n+\t\twalkstate(sw->nbody);\n+\t\treturn;\n+\t}\n+\tif(t->left == N) {\n+\t\tgotodefault = t->right;\n+\t\tt = listnext(&save);\n+\t\tgoto loop;\n+\t}\n+\tif(t->left->op != OTYPESW) {\n+\t\tt = listnext(&save);\n+\t\tgoto loop;\n+\t}\n+\n+\tc1 = mal(sizeof(*c));\n+\tc1->link = c;\n+\tc1->node = t;\n+\tc1->hash = 0;\n+\tif(t->left->left != N)\n+\t\tc1->hash = typehash(t->left->left->type, 1, 0);\n+\tc = c1;\n+\n+\tt = listnext(&save);\n+\tgoto loop;\n+}\n```
このコードは、型スイッチのコンパイル方法を根本的に変更します。
* **`Case` 構造体**: 各 `case` 節の情報を保持するための構造体です。`hash` フィールドは、その `case` がマッチする型のハッシュ値を格納します。
* **`typeswitch` 関数**:
1. まず、型スイッチの対象となるインターフェース変数を一時変数 `facename` に格納します。
2. 次に、新しく導入されたランタイム関数 `sys.ifacethash` を呼び出し、インターフェースの型ハッシュを取得して一時変数 `hashname` に格納します。
3. すべての `case` 節を走査し、それぞれの `case` に対応する `Case` 構造体を作成します。`case nil:` の場合は特別な処理を行い、それ以外の型ケースでは `typehash` を呼び出してハッシュ値を計算します。
4. 作成された `Case` リストを `hashcmp` 関数（ハッシュ値で比較）を使ってソートします。
5. `counthash` 関数を呼び出して、重複する型ケースがないかチェックし、ユニークなケースの数を数えます。
6. `typebsw` 関数を呼び出し、ソートされたケースリストとハッシュ値に基づいて、二分探索ツリーに相当する `if` 文のネスト構造を生成します。
7. 最終的に、生成された `if` 文の構造と初期化コードを結合し、型スイッチの本体として設定します。
* **`typebsw` 関数**:
この関数が二分探索の核心部分です。
* `ncase < Ncase` (4) の場合、少数のケースでは線形探索（一連の `if` 文）を生成します。
* それ以外の場合、ケースリストの中央のハッシュ値に基づいて `OLE` (less than or equal) 比較を行う `if` 文を生成し、再帰的に左右のサブツリーを構築します。
* 各リーフノード（または線形探索の各ステップ）では、`case nil:` のチェック（`facename == nil`）や、インターフェースから具象型への型アサーション（`ODOTTYPE`）を行い、その結果（成功したかどうか）を `boolname` に格納します。そして、`boolname` が真であれば対応する `case` のコードブロックにジャンプする `if` 文を生成します。
### `src/runtime/iface.c` の `sys·ifacethash` 関数 (抜粋)
```diff
--- a/src/runtime/iface.c
+++ b/src/runtime/iface.c
@@ -532,6 +532,23 @@ sys·ifaceeq(Iface i1, Iface i2, bool ret)
FLUSH(&ret);\n }\n \n+// ifacethash(i1 any) (ret uint32);\n+void\n+sys·ifacethash(Iface i1, uint32 ret)\n+{\n+\tItype *im;\n+\tSigt *st;\n+\n+\tret = 0;\n+\tim = i1.type;\n+\tif(im != nil) {\n+\t\tst = im->sigt;\n+\t\tif(st != nil)\n+\t\t\tret = st->thash;\n+\t}\n+\tFLUSH(&ret);\n+}\n+\n void\n sys·printinter(Iface i)\n {\n```
この関数は、Goランタイムに新しく追加されたもので、インターフェース `i1` が保持する具象型のハッシュ値を取得します。
* `i1.type` はインターフェースが保持する具象型の情報（`Itype` 構造体へのポインタ）です。
* `Itype` 構造体には、その型に関する様々な情報が含まれており、その中に `sigt` (type signature) へのポインタがあります。
* `Sigt` 構造体には、型のハッシュ値 `thash` が格納されています。
この関数は、インターフェースが `nil` でない場合、またはその型情報が `nil` でない場合に、`thash` の値を返します。これにより、コンパイラが生成したコードは、ランタイムでインターフェースの型ハッシュを効率的に取得できるようになります。
## 関連リンク
* Go言語のインターフェースに関する公式ドキュメント: [https://go.dev/tour/methods/10](https://go.dev/tour/methods/10)
* Go言語の型スイッチに関する公式ドキュメント: [https://go.dev/tour/methods/16](https://go.dev/tour/methods/16)
* Goコンパイラのソースコード: [https://github.com/golang/go/tree/master/src/cmd/compile](https://github.com/golang/go/tree/master/src/cmd/compile)
* Goランタイムのソースコード: [https://github.com/golang/go/tree/master/src/runtime](https://github.com/golang/go/tree/master/src/runtime)
## 参考にした情報源リンク
* Goのインターフェースの内部構造に関する記事 (例: "The Laws of Reflection" by Rob Pike): [https://go.dev/blog/laws-of-reflection](https://go.dev/blog/laws-of-reflection)
* Goコンパイラの内部に関する議論やドキュメント（Goのメーリングリストやデザインドキュメントなど）
* 二分探索アルゴリズムに関する一般的な情報源。
* Goの初期のコミット履歴と関連するデザインドキュメント。
* Goのソースコード内のコメント。