| // 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 <u.h> |
| #include <libc.h> |
| #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 = temp(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 = temp(sw->ntest->right->type); |
| a = nod(OAS, facename, sw->ntest->right); |
| typecheck(&a, Etop); |
| cas = list(cas, a); |
| |
| casebody(sw, facename); |
| |
| boolname = temp(types[TBOOL]); |
| typecheck(&boolname, Erv); |
| |
| hashname = temp(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; |
| } |