summaryrefslogtreecommitdiff
path: root/src/cmd/gc/swt.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/cmd/gc/swt.c')
-rw-r--r--src/cmd/gc/swt.c896
1 files changed, 896 insertions, 0 deletions
diff --git a/src/cmd/gc/swt.c b/src/cmd/gc/swt.c
new file mode 100644
index 000000000..c2968c44b
--- /dev/null
+++ b/src/cmd/gc/swt.c
@@ -0,0 +1,896 @@
+// 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.
+
+#include "go.h"
+
+enum
+{
+ Snorm = 0,
+ Strue,
+ Sfalse,
+ Stype,
+
+ 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
+};
+
+typedef struct Case Case;
+struct Case
+{
+ Node* node; // points at case statement
+ uint32 hash; // hash of a type switch
+ uint8 type; // type of case
+ uint8 diag; // suppress multiple diagnostics
+ uint16 ordinal; // position in switch
+ Case* link; // linked list to link
+};
+#define C ((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(" ord=%d\n", c->ordinal);
+ break;
+ case Texprconst:
+ print("case-exprconst\n");
+ print(" ord=%d\n", c->ordinal);
+ break;
+ case Texprvar:
+ print("case-exprvar\n");
+ print(" ord=%d\n", c->ordinal);
+ print(" op=%O\n", c->node->left->op);
+ break;
+ case Ttypenil:
+ print("case-typenil\n");
+ print(" ord=%d\n", c->ordinal);
+ break;
+ case Ttypeconst:
+ print("case-typeconst\n");
+ print(" ord=%d\n", c->ordinal);
+ print(" hash=%ux\n", c->hash);
+ break;
+ case Ttypevar:
+ print("case-typevar\n");
+ print(" ord=%d\n", c->ordinal);
+ break;
+ default:
+ print("case-???\n");
+ print(" ord=%d\n", c->ordinal);
+ print(" op=%O\n", c->node->left->op);
+ print(" hash=%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) {
+ // invalid program, but return a sort
+ // order so that we can give a better
+ // error later.
+ return ct - n2->val.ctype;
+ }
+
+ // 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;
+
+ // sort by ordinal so duplicate error
+ // happens on later case.
+ if(c1->ordinal > c2->ordinal)
+ return +1;
+ if(c1->ordinal < c2->ordinal)
+ 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;
+}
+
+static Node*
+newlabel(void)
+{
+ static int label;
+
+ label++;
+ snprint(namebuf, sizeof(namebuf), "%.6d", label);
+ return newname(lookup(namebuf));
+}
+
+/*
+ * build separate list of statements and cases
+ * make labels between cases and statements
+ * deal with fallthrough, break, unreachable statements
+ */
+static void
+casebody(Node *sw, Node *typeswvar)
+{
+ Node *n, *c, *last;
+ Node *def;
+ NodeList *cas, *stat, *l, *lc;
+ Node *go, *br;
+ int32 lno, needvar;
+
+ lno = setlineno(sw);
+ if(sw->list == nil)
+ return;
+
+ cas = nil; // cases
+ stat = nil; // statements
+ def = N; // defaults
+ br = nod(OBREAK, N, N);
+
+ for(l=sw->list; l; l=l->next) {
+ n = l->n;
+ lno = setlineno(n);
+ if(n->op != OXCASE)
+ fatal("casebody %O", n->op);
+ n->op = OCASE;
+ needvar = count(n->list) != 1 || n->list->n->op == OLITERAL;
+
+ go = nod(OGOTO, newlabel(), N);
+ if(n->list == nil) {
+ if(def != N)
+ yyerror("more than one default case");
+ // reuse original default case
+ n->right = go;
+ def = n;
+ }
+
+ if(n->list != nil && n->list->next == nil) {
+ // one case - reuse OCASE node.
+ c = n->list->n;
+ n->left = c;
+ n->right = go;
+ n->list = nil;
+ cas = list(cas, n);
+ } else {
+ // expand multi-valued cases
+ for(lc=n->list; lc; lc=lc->next) {
+ c = lc->n;
+ cas = list(cas, nod(OCASE, c, go));
+ }
+ }
+
+ stat = list(stat, nod(OLABEL, go->left, N));
+ if(typeswvar && needvar && n->nname != N) {
+ NodeList *l;
+
+ l = list1(nod(ODCL, n->nname, N));
+ l = list(l, nod(OAS, n->nname, typeswvar));
+ typechecklist(l, Etop);
+ stat = concat(stat, l);
+ }
+ stat = concat(stat, n->nbody);
+
+ // botch - shouldnt fall thru declaration
+ last = stat->end->n;
+ if(last->op == OXFALL) {
+ if(typeswvar) {
+ setlineno(last);
+ yyerror("cannot fallthrough in type switch");
+ }
+ last->op = OFALL;
+ } else
+ stat = list(stat, br);
+ }
+
+ stat = list(stat, br);
+ if(def)
+ cas = list(cas, def);
+
+ sw->list = cas;
+ sw->nbody = stat;
+ lineno = lno;
+}
+
+static Case*
+mkcaselist(Node *sw, int arg)
+{
+ Node *n;
+ Case *c, *c1, *c2;
+ NodeList *l;
+ int ord;
+
+ c = C;
+ ord = 0;
+
+ for(l=sw->list; l; l=l->next) {
+ n = l->n;
+ c1 = mal(sizeof(*c1));
+ c1->link = c;
+ c = c1;
+
+ ord++;
+ c->ordinal = ord;
+ c->node = n;
+
+ if(n->left == N) {
+ c->type = Tdefault;
+ continue;
+ }
+
+ switch(arg) {
+ case Stype:
+ c->hash = 0;
+ if(n->left->op == OLITERAL) {
+ c->type = Ttypenil;
+ continue;
+ }
+ if(istype(n->left->type, TINTER)) {
+ c->type = Ttypevar;
+ continue;
+ }
+
+ c->hash = typehash(n->left->type);
+ c->type = Ttypeconst;
+ continue;
+
+ case Snorm:
+ case Strue:
+ case Sfalse:
+ c->type = Texprvar;
+ switch(consttype(n->left)) {
+ case CTFLT:
+ case CTINT:
+ case CTSTR:
+ c->type = Texprconst;
+ }
+ continue;
+ }
+ }
+
+ if(c == C)
+ return C;
+
+ // sort by value and diagnose duplicate cases
+ switch(arg) {
+ case Stype:
+ c = csort(c, typecmp);
+ for(c1=c; c1!=C; c1=c1->link) {
+ for(c2=c1->link; c2!=C && c2->hash==c1->hash; c2=c2->link) {
+ if(c1->type == Ttypenil || c1->type == Tdefault)
+ break;
+ if(c2->type == Ttypenil || c2->type == Tdefault)
+ break;
+ if(!eqtype(c1->node->left->type, c2->node->left->type))
+ continue;
+ yyerrorl(c2->node->lineno, "duplicate case in switch\n\tprevious case at %L", 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\n\tprevious case at %L", c1->node->lineno);
+ }
+ break;
+ }
+
+ // put list back in processing order
+ c = csort(c, ordlcmp);
+ return c;
+}
+
+static Node* exprname;
+
+static Node*
+exprbsw(Case *c0, int ncase, int arg)
+{
+ NodeList *cas;
+ Node *a, *n;
+ Case *c;
+ int i, half, lno;
+
+ cas = nil;
+ if(ncase < Ncase) {
+ for(i=0; i<ncase; i++) {
+ n = c0->node;
+ lno = setlineno(n);
+
+ switch(arg) {
+ case Strue:
+ a = nod(OIF, N, N);
+ a->ntest = n->left; // if val
+ a->nbody = list1(n->right); // then goto l
+ break;
+
+ case Sfalse:
+ a = nod(OIF, N, N);
+ a->ntest = nod(ONOT, n->left, N); // if !val
+ typecheck(&a->ntest, Erv);
+ a->nbody = list1(n->right); // then goto l
+ break;
+
+ default:
+ a = nod(OIF, N, N);
+ a->ntest = nod(OEQ, exprname, n->left); // if name == val
+ typecheck(&a->ntest, Erv);
+ a->nbody = list1(n->right); // then goto l
+ break;
+ }
+
+ cas = list(cas, a);
+ c0 = c0->link;
+ lineno = lno;
+ }
+ return liststmt(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, exprname, c->node->left);
+ typecheck(&a->ntest, Erv);
+ a->nbody = list1(exprbsw(c0, half, arg));
+ a->nelse = list1(exprbsw(c->link, ncase-half, arg));
+ return a;
+}
+
+/*
+ * normal (expression) switch.
+ * rebulid case statements into if .. goto
+ */
+static void
+exprswitch(Node *sw)
+{
+ Node *def;
+ NodeList *cas;
+ Node *a;
+ Case *c0, *c, *c1;
+ Type *t;
+ int arg, ncase;
+
+ casebody(sw, N);
+
+ arg = Snorm;
+ if(isconst(sw->ntest, CTBOOL)) {
+ arg = Strue;
+ if(sw->ntest->val.u.bval == 0)
+ arg = Sfalse;
+ }
+ walkexpr(&sw->ntest, &sw->ninit);
+ t = sw->type;
+ if(t == T)
+ return;
+
+ /*
+ * convert the switch into OIF statements
+ */
+ exprname = N;
+ cas = nil;
+ if(arg != Strue && arg != Sfalse) {
+ exprname = nod(OXXX, N, N);
+ tempname(exprname, sw->ntest->type);
+ cas = list1(nod(OAS, exprname, sw->ntest));
+ typechecklist(cas, Etop);
+ }
+
+ 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 = concat(cas, sw->nbody);
+ sw->list = nil;
+ walkstmtlist(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;
+
+static Node*
+typeone(Node *t)
+{
+ NodeList *init;
+ Node *a, *b, *var;
+
+ var = t->nname;
+ init = nil;
+ if(var == N) {
+ typecheck(&nblank, Erv | Easgn);
+ var = nblank;
+ } else
+ init = list1(nod(ODCL, var, N));
+
+ a = nod(OAS2, N, N);
+ a->list = list(list1(var), boolname); // var,bool =
+ b = nod(ODOTTYPE, facename, N);
+ b->type = t->left->type; // interface.(type)
+ a->rlist = list1(b);
+ typecheck(&a, Etop);
+ init = list(init, a);
+
+ b = nod(OIF, N, N);
+ b->ntest = boolname;
+ b->nbody = list1(t->right); // if bool { goto l }
+ a = liststmt(list(init, b));
+ return a;
+}
+
+static Node*
+typebsw(Case *c0, int ncase)
+{
+ NodeList *cas;
+ Node *a, *n;
+ Case *c;
+ int i, half;
+
+ cas = nil;
+
+ if(ncase < Ncase) {
+ for(i=0; i<ncase; i++) {
+ n = c0->node;
+ if(c0->type != Ttypeconst)
+ fatal("typebsw");
+ a = nod(OIF, N, N);
+ a->ntest = nod(OEQ, hashname, nodintconst(c0->hash));
+ typecheck(&a->ntest, Erv);
+ a->nbody = list1(n->right);
+ cas = list(cas, a);
+ c0 = c0->link;
+ }
+ return liststmt(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));
+ typecheck(&a->ntest, Erv);
+ a->nbody = list1(typebsw(c0, half));
+ a->nelse = list1(typebsw(c->link, ncase-half));
+ return a;
+}
+
+/*
+ * convert switch of the form
+ * switch v := i.(type) { case t1: ..; case t2: ..; }
+ * into if statements
+ */
+static void
+typeswitch(Node *sw)
+{
+ Node *def;
+ NodeList *cas, *hash;
+ Node *a, *n;
+ Case *c, *c0, *c1;
+ int ncase;
+ Type *t;
+ Val v;
+
+ if(sw->ntest == nil)
+ return;
+ if(sw->ntest->right == nil) {
+ setlineno(sw);
+ yyerror("type switch must have an assignment");
+ return;
+ }
+ walkexpr(&sw->ntest->right, &sw->ninit);
+ if(!istype(sw->ntest->right->type, TINTER)) {
+ yyerror("type switch must be on an interface");
+ return;
+ }
+ cas = nil;
+
+ /*
+ * predeclare temporary variables
+ * and the boolean var
+ */
+ facename = nod(OXXX, N, N);
+ tempname(facename, sw->ntest->right->type);
+ a = nod(OAS, facename, sw->ntest->right);
+ typecheck(&a, Etop);
+ cas = list(cas, a);
+
+ casebody(sw, facename);
+
+ boolname = nod(OXXX, N, N);
+ tempname(boolname, types[TBOOL]);
+ typecheck(&boolname, Erv);
+
+ hashname = nod(OXXX, N, N);
+ tempname(hashname, types[TUINT32]);
+ typecheck(&hashname, Erv);
+
+ t = sw->ntest->right->type;
+ if(isnilinter(t))
+ a = syslook("efacethash", 1);
+ else
+ a = syslook("ifacethash", 1);
+ argtype(a, t);
+ a = nod(OCALL, a, N);
+ a->list = list1(facename);
+ a = nod(OAS, hashname, a);
+ typecheck(&a, Etop);
+ cas = list(cas, a);
+
+ c0 = mkcaselist(sw, Stype);
+ if(c0 != C && c0->type == Tdefault) {
+ def = c0->node->right;
+ c0 = c0->link;
+ } else {
+ def = nod(OBREAK, N, N);
+ }
+
+ /*
+ * insert if statement into each case block
+ */
+ for(c=c0; c!=C; c=c->link) {
+ n = c->node;
+ switch(c->type) {
+
+ case Ttypenil:
+ v.ctype = CTNIL;
+ a = nod(OIF, N, N);
+ a->ntest = nod(OEQ, facename, nodlit(v));
+ typecheck(&a->ntest, Erv);
+ a->nbody = list1(n->right); // if i==nil { goto l }
+ n->right = a;
+ break;
+
+ case Ttypevar:
+ case Ttypeconst:
+ n->right = typeone(n);
+ break;
+ }
+ }
+
+ /*
+ * generate list of if statements, binary search for constant sequences
+ */
+ while(c0 != C) {
+ if(c0->type != Ttypeconst) {
+ n = c0->node;
+ cas = list(cas, n->right);
+ c0=c0->link;
+ continue;
+ }
+
+ // identify run of constants
+ c1 = c = c0;
+ while(c->link!=C && c->link->type==Ttypeconst)
+ c = c->link;
+ c0 = c->link;
+ c->link = nil;
+
+ // sort by hash
+ c1 = csort(c1, typecmp);
+
+ // for debugging: linear search
+ if(0) {
+ for(c=c1; c!=C; c=c->link) {
+ n = c->node;
+ cas = list(cas, n->right);
+ }
+ continue;
+ }
+
+ // combine adjacent cases with the same hash
+ ncase = 0;
+ for(c=c1; c!=C; c=c->link) {
+ ncase++;
+ hash = list1(c->node->right);
+ while(c->link != C && c->link->hash == c->hash) {
+ hash = list(hash, c->link->node->right);
+ c->link = c->link->link;
+ }
+ c->node->right = liststmt(hash);
+ }
+
+ // binary search among cases to narrow by hash
+ cas = list(cas, typebsw(c1, ncase));
+ }
+ if(nerrors == 0) {
+ cas = list(cas, def);
+ sw->nbody = concat(cas, sw->nbody);
+ sw->list = nil;
+ walkstmtlist(sw->nbody);
+ }
+}
+
+void
+walkswitch(Node *sw)
+{
+
+ /*
+ * reorder the body into (OLIST, cases, statements)
+ * cases have OGOTO into statements.
+ * both have inserted OBREAK statements
+ */
+ walkstmtlist(sw->ninit);
+ if(sw->ntest == N) {
+ sw->ntest = nodbool(1);
+ typecheck(&sw->ntest, Erv);
+ }
+
+ if(sw->ntest->op == OTYPESW) {
+ typeswitch(sw);
+//dump("sw", sw);
+ return;
+ }
+ exprswitch(sw);
+}
+
+/*
+ * type check switch statement
+ */
+void
+typecheckswitch(Node *n)
+{
+ int top, lno;
+ Type *t;
+ NodeList *l, *ll;
+ Node *ncase, *nvar;
+ Node *def;
+
+ lno = lineno;
+ typechecklist(n->ninit, Etop);
+
+ if(n->ntest != N && n->ntest->op == OTYPESW) {
+ // type switch
+ top = Etype;
+ typecheck(&n->ntest->right, Erv);
+ t = n->ntest->right->type;
+ if(t != T && t->etype != TINTER)
+ yyerror("cannot type switch on non-interface value %+N", n->ntest->right);
+ } else {
+ // value switch
+ top = Erv;
+ if(n->ntest) {
+ typecheck(&n->ntest, Erv);
+ defaultlit(&n->ntest, T);
+ t = n->ntest->type;
+ } else
+ t = types[TBOOL];
+ }
+ n->type = t;
+
+ def = N;
+ for(l=n->list; l; l=l->next) {
+ ncase = l->n;
+ setlineno(n);
+ if(ncase->list == nil) {
+ // default
+ if(def != N)
+ yyerror("multiple defaults in switch (first at %L)", def->lineno);
+ else
+ def = ncase;
+ } else {
+ for(ll=ncase->list; ll; ll=ll->next) {
+ setlineno(ll->n);
+ typecheck(&ll->n, Erv | Etype);
+ if(ll->n->type == T || t == T)
+ continue;
+ switch(top) {
+ case Erv: // expression switch
+ defaultlit(&ll->n, t);
+ if(ll->n->op == OTYPE)
+ yyerror("type %T is not an expression", ll->n->type);
+ else if(ll->n->type != T && !eqtype(ll->n->type, t))
+ yyerror("case %+N in %T switch", ll->n, t);
+ break;
+ case Etype: // type switch
+ if(ll->n->op == OLITERAL && istype(ll->n->type, TNIL))
+ ;
+ else if(ll->n->op != OTYPE && ll->n->type != T) {
+ yyerror("%#N is not a type", ll->n);
+ // reset to original type
+ ll->n = n->ntest->right;
+ }
+ break;
+ }
+ }
+ }
+ if(top == Etype && n->type != T) {
+ ll = ncase->list;
+ nvar = ncase->nname;
+ if(nvar != N) {
+ if(ll && ll->next == nil && ll->n->type != T && !istype(ll->n->type, TNIL)) {
+ // single entry type switch
+ nvar->ntype = typenod(ll->n->type);
+ } else {
+ // multiple entry type switch or default
+ nvar->ntype = typenod(n->type);
+ }
+ }
+ }
+ typechecklist(ncase->nbody, Etop);
+ }
+
+ lineno = lno;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-21 17:46:22 +0000