ref: b769b88bbc3e0ddcef7991e73b2582d472f08d89
dir: /parse/infer.c/
#include <stdlib.h> #include <stdio.h> #include <stdarg.h> #include <inttypes.h> #include <inttypes.h> #include <ctype.h> #include <string.h> #include <assert.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <unistd.h> #include <assert.h> #include "parse.h" typedef struct Inferstate Inferstate; struct Inferstate { int ingeneric; int sawret; int indentdepth; int intype; Type *ret; /* bound by patterns turn into decls in the action block */ Node **binds; size_t nbinds; /* nodes that need post-inference checking/unification */ Node **postcheck; size_t npostcheck; Stab **postcheckscope; size_t npostcheckscope; /* the type params bound at the current point */ Htab **tybindings; size_t ntybindings; /* generic declarations to be specialized */ Node **genericdecls; size_t ngenericdecls; /* delayed unification -- we fall back to these types in a post pass if we * haven't unifed to something more specific */ Htab *delayed; /* the nodes that we've specialized them to, and the scopes they * appear in */ Node **specializations; size_t nspecializations; Stab **specializationscope; size_t nspecializationscope; }; static void infernode(Inferstate *st, Node **np, Type *ret, int *sawret); static void inferexpr(Inferstate *st, Node **np, Type *ret, int *sawret); static void inferdecl(Inferstate *st, Node *n); static void typesub(Inferstate *st, Node *n); static void tybind(Inferstate *st, Type *t); static Type *tyfix(Inferstate *st, Node *ctx, Type *orig, int noerr); static void bind(Inferstate *st, Node *n); static void tyunbind(Inferstate *st, Type *t); static void unbind(Inferstate *st, Node *n); static Type *unify(Inferstate *st, Node *ctx, Type *a, Type *b); static Type *tf(Inferstate *st, Type *t); static void ctxstrcall(char *buf, size_t sz, Inferstate *st, Node *n) { char *p, *end, *sep, *t; size_t nargs, i; Node **args; Type *et; args = n->expr.args; nargs = n->expr.nargs; p = buf; end = buf + sz; sep = ""; if (exprop(args[0]) == Ovar) p += snprintf(p, end - p, "%s(", namestr(args[0]->expr.args[0])); else p += snprintf(p, end - p, "<e>("); for (i = 1; i < nargs; i++) { et = tyfix(st, NULL, exprtype(args[i]), 1); if (et != NULL) t = tystr(et); else t = strdup("?"); if (exprop(args[i]) == Ovar) p += snprintf(p, end - p, "%s%s:%s", sep, namestr(args[0]->expr.args[0]), t); else p += snprintf(p, end - p, "%s<e%zd>:%s", sep, i, t); sep = ", "; free(t); } t = tystr(tyfix(st, NULL, exprtype(args[0])->sub[0], 1)); p += snprintf(p, end - p, "): %s", t); free(t); } static char *nodetystr(Inferstate *st, Node *n) { Type *t; t = NULL; if (n->type == Nexpr && exprtype(n) != NULL) t = tyfix(st, NULL, exprtype(n), 1); else if (n->type == Ndecl && decltype(n) != NULL) t = tyfix(st, NULL, decltype(n), 1); if (t && tybase(t)->type != Tyvar) return tystr(t); else return strdup("unknown"); } /* Tries to give a good string describing the context * for the sake of error messages. */ static char *ctxstr(Inferstate *st, Node *n) { char *t, *t1, *t2, *t3; char *s, *d; size_t nargs; Node **args; char buf[512]; switch (n->type) { default: s = strdup(nodestr[n->type]); break; case Ndecl: d = declname(n); t = nodetystr(st, n); snprintf(buf, sizeof buf, "%s:%s", d, t); s = strdup(buf); free(t); break; case Nname: s = strdup(namestr(n)); break; case Nexpr: args = n->expr.args; nargs = n->expr.nargs; t1 = NULL; t2 = NULL; t3 = NULL; if (exprop(n) == Ovar) d = namestr(args[0]); else d = opstr[exprop(n)]; t = nodetystr(st, n); if (nargs >= 1) t1 = nodetystr(st, args[0]); if (nargs >= 2) t2 = nodetystr(st, args[1]); if (nargs >= 3) t3 = nodetystr(st, args[2]); switch (opclass[exprop(n)]) { case OTbin: snprintf(buf, sizeof buf, "<e1:%s> %s <e2:%s>", t1, oppretty[exprop(n)], t2); break; case OTpre: snprintf(buf, sizeof buf, "%s<e%s>", t1, oppretty[exprop(n)]); break; case OTpost: snprintf(buf, sizeof buf, "<e:%s>%s", t1, oppretty[exprop(n)]); break; case OTzarg: snprintf(buf, sizeof buf, "%s", oppretty[exprop(n)]); case OTmisc: switch (exprop(n)) { case Ovar: snprintf(buf, sizeof buf, "%s:%s", namestr(args[0]), t); break; case Ocall: ctxstrcall(buf, sizeof buf, st, n); break; case Oidx: if (exprop(args[0]) == Ovar) snprintf(buf, sizeof buf, "%s[<e1:%s>]", namestr(args[0]->expr.args[0]), t2); else snprintf(buf, sizeof buf, "<sl:%s>[<e1%s>]", t1, t2); break; case Oslice: if (exprop(args[0]) == Ovar) snprintf(buf, sizeof buf, "%s[<e1:%s>:<e2:%s>]", namestr(args[0]->expr.args[0]), t2, t3); else snprintf(buf, sizeof buf, "<sl:%s>[<e1%s>:<e2:%s>]", t1, t2, t3); break; case Omemb: snprintf(buf, sizeof buf, "<%s>.%s", t1, namestr(args[1])); break; default: snprintf(buf, sizeof buf, "%s:%s", d, t); break; } } free(t); free(t1); free(t2); free(t3); s = strdup(buf); break; } return s; } static void addspecialization(Inferstate *st, Node *n, Stab *stab) { Node *dcl; dcl = decls[n->expr.did]; lappend(&st->specializationscope, &st->nspecializationscope, stab); lappend(&st->specializations, &st->nspecializations, n); lappend(&st->genericdecls, &st->ngenericdecls, dcl); } static void delayedcheck(Inferstate *st, Node *n, Stab *s) { lappend(&st->postcheck, &st->npostcheck, n); lappend(&st->postcheckscope, &st->npostcheckscope, s); } static void typeerror(Inferstate *st, Type *a, Type *b, Node *ctx, char *msg) { char *t1, *t2, *c; t1 = tystr(tyfix(st, NULL, a, 1)); t2 = tystr(tyfix(st, NULL, b, 1)); c = ctxstr(st, ctx); if (msg) fatal(ctx, "type \"%s\" incompatible with \"%s\" near %s: %s", t1, t2, c, msg); else fatal(ctx, "type \"%s\" incompatible with \"%s\" near %s", t1, t2, c); free(t1); free(t2); free(c); } /* Set a scope's enclosing scope up correctly. * We don't do this in the parser for some reason. */ static void setsuper(Stab *st, Stab *super) { Stab *s; /* verify that we don't accidentally create loops */ for (s = super; s; s = s->super) assert(s->super != st); st->super = super; } /* If the current environment binds a type, * we return true */ static int isbound(Inferstate *st, Type *t) { ssize_t i; Type *p; for (i = st->ntybindings - 1; i >= 0; i--) { p = htget(st->tybindings[i], t->pname); if (p == t) return 1; } return 0; } /* Checks if a type that directly contains itself. * Recursive types that contain themselves through * pointers or slices are fine, but any other self-inclusion * would lead to a value of infinite size */ static int tyinfinite(Inferstate *st, Type *t, Type *sub) { size_t i; assert(t != NULL); if (t == sub) /* FIXME: is this actually right? */ return 1; /* if we're on the first iteration, the subtype is the type * itself. The assignment must come after the equality check * for obvious reasons. */ if (!sub) sub = t; switch (sub->type) { case Tystruct: for (i = 0; i < sub->nmemb; i++) if (tyinfinite(st, t, decltype(sub->sdecls[i]))) return 1; break; case Tyunion: for (i = 0; i < sub->nmemb; i++) { if (sub->udecls[i]->etype && tyinfinite(st, t, sub->udecls[i]->etype)) return 1; } break; case Typtr: case Tyslice: return 0; default: for (i = 0; i < sub->nsub; i++) if (tyinfinite(st, t, sub->sub[i])) return 1; break; } return 0; } static int needfreshenrec(Inferstate *st, Type *t, Bitset *visited) { size_t i; if (bshas(visited, t->tid)) return 0; bsput(visited, t->tid); switch (t->type) { case Typaram: return 1; case Tygeneric: return 1; case Tyname: for (i = 0; i < t->narg; i++) if (needfreshenrec(st, t->arg[i], visited)) return 1; return needfreshenrec(st, t->sub[0], visited); case Tystruct: for (i = 0; i < t->nmemb; i++) if (needfreshenrec(st, decltype(t->sdecls[i]), visited)) return 1; break; case Tyunion: for (i = 0; i < t->nmemb; i++) if (t->udecls[i]->etype && needfreshenrec(st, t->udecls[i]->etype, visited)) return 1; break; default: for (i = 0; i < t->nsub; i++) if (needfreshenrec(st, t->sub[i], visited)) return 1; break; } return 0; } static int needfreshen(Inferstate *st, Type *t) { Bitset *visited; int ret; visited = mkbs(); ret = needfreshenrec(st, t, visited); bsfree(visited); return ret; } /* Freshens the type of a declaration. */ static Type *_tyfreshen(Inferstate *st, Htab *subst, Type *t) { char *from, *to; if (!needfreshen(st, t)) { if (debugopt['u']) indentf(st->indentdepth, "%s isn't generic: skipping freshen\n", tystr(t)); return t; } from = tystr(t); tybind(st, t); if (!subst) { subst = mkht(tyhash, tyeq); t = tyspecialize(t, subst, st->delayed); htfree(subst); } else { t = tyspecialize(t, subst, st->delayed); } tyunbind(st, t); if (debugopt['u']) { to = tystr(t); indentf(st->indentdepth, "Freshen %s => %s\n", from, to); free(from); free(to); } return t; } /* Resolves a type and all it's subtypes recursively.*/ static void tyresolve(Inferstate *st, Type *t) { size_t i; Type *base; if (t->resolved) return; /* type resolution should never throw errors about non-generics * showing up within a generic type, so we push and pop a generic * around resolution */ st->ingeneric++; t->resolved = 1; /* Walk through aggregate type members */ if (t->type == Tystruct) { st->intype++; for (i = 0; i < t->nmemb; i++) infernode(st, &t->sdecls[i], NULL, NULL); st->intype--; } else if (t->type == Tyunion) { for (i = 0; i < t->nmemb; i++) { t->udecls[i]->utype = t; t->udecls[i]->utype = tf(st, t->udecls[i]->utype); if (t->udecls[i]->etype) { tyresolve(st, t->udecls[i]->etype); t->udecls[i]->etype = tf(st, t->udecls[i]->etype); } } } else if (t->type == Tyarray) { if (!st->intype && !t->asize) lfatal(t->loc, "unsized array type outside of struct"); infernode(st, &t->asize, NULL, NULL); } for (i = 0; i < t->nsub; i++) t->sub[i] = tf(st, t->sub[i]); base = tybase(t); /* no-ops if base == t */ if (t->traits) bsunion(t->traits, base->traits); else t->traits = bsdup(base->traits); if (tyinfinite(st, t, NULL)) lfatal(t->loc, "type %s includes itself", tystr(t)); st->ingeneric--; } /* Look up the best type to date in the unification table, returning it */ Type *tysearch(Type *t) { Type *lu; Stab *ns; assert(t != NULL); lu = NULL; while (1) { if (!tytab[t->tid] && t->type == Tyunres) { ns = curstab(); if (t->name->name.ns) { ns = getns_str(ns, t->name->name.ns); } if (!ns) fatal(t->name, "could not resolve namespace \"%s\"", t->name->name.ns); if (!(lu = gettype(ns, t->name))) fatal(t->name, "could not resolve type %s", tystr(t)); tytab[t->tid] = lu; } if (!tytab[t->tid]) break; /* compress paths: shift the link up one level */ if (tytab[tytab[t->tid]->tid]) tytab[t->tid] = tytab[tytab[t->tid]->tid]; t = tytab[t->tid]; } return t; } static Type *tysubst(Inferstate *st, Type *t, Type *orig) { Htab *subst; size_t i; subst = mkht(tyhash, tyeq); for (i = 0; i < t->ngparam; i++) { htput(subst, t->gparam[i], orig->arg[i]); } t = _tyfreshen(st, subst, t); htfree(subst); return t; } /* fixd the most accurate type mapping we have (ie, * the end of the unification chain */ static Type *tf(Inferstate *st, Type *orig) { int isgeneric; Type *t; assert(orig != NULL); t = tysearch(orig); isgeneric = t->type == Tygeneric; st->ingeneric += isgeneric; tyresolve(st, t); /* If this is an instantiation of a generic type, we want the params to * match the instantiation */ if (orig->type == Tyunres && t->type == Tygeneric) { if (t->ngparam != orig->narg) { lfatal(orig->loc, "%s incompatibly specialized with %s, declared on %s:%d", tystr(orig), tystr(t), file->file.files[t->loc.file], t->loc.line); } t = tysubst(st, t, orig); } st->ingeneric -= isgeneric; return t; } /* set the type of any typable node */ static void settype(Inferstate *st, Node *n, Type *t) { t = tf(st, t); switch (n->type) { case Nexpr: n->expr.type = t; break; case Ndecl: n->decl.type = t; break; case Nlit: n->lit.type = t; break; case Nfunc: n->func.type = t; break; default: die("untypable node %s", nodestr[n->type]); break; } } /* Gets the type of a literal value */ static Type *littype(Node *n) { if (n->lit.type) return n->lit.type; switch (n->lit.littype) { case Lchr: return mktype(n->loc, Tychar); break; case Lbool: return mktype(n->loc, Tybool); break; case Lint: return mktylike(n->loc, Tyint); break; case Lflt: return mktylike(n->loc, Tyflt64); break; case Lstr: return mktyslice(n->loc, mktype(n->loc, Tybyte)); break; case Llbl: return mktyptr(n->loc, mktype(n->loc, Tyvoid)); break; case Lfunc: return n->lit.fnval->func.type; break; }; die("Bad lit type %d", n->lit.littype); return NULL; } static Type *delayeducon(Inferstate *st, Type *fallback) { Type *t; char *from, *to; if (fallback->type != Tyunion) return fallback; t = mktylike(fallback->loc, fallback->type); htput(st->delayed, t, fallback); if (debugopt['u']) { from = tystr(t); to = tystr(fallback); indentf(st->indentdepth, "Delay %s -> %s\n", from, to); free(from); free(to); } return t; } /* Finds the type of any typable node */ static Type *type(Inferstate *st, Node *n) { Type *t; switch (n->type) { case Nlit: t = littype(n); break; case Nexpr: t = n->expr.type; break; case Ndecl: t = decltype(n); break; case Nfunc: t = n->func.type; break; default: t = NULL; die("untypeable node %s", nodestr[n->type]); break; }; return tf(st, t); } static Ucon *uconresolve(Inferstate *st, Node *n) { Ucon *uc; Node **args; Stab *ns; args = n->expr.args; ns = curstab(); if (args[0]->name.ns) ns = getns_str(ns, args[0]->name.ns); if (!ns) fatal(n, "no namespace %s\n", args[0]->name.ns); uc = getucon(ns, args[0]); if (!uc) fatal(n, "no union constructor `%s", ctxstr(st, args[0])); if (!uc->etype && n->expr.nargs > 1) fatal(n, "nullary union constructor `%s passed arg ", ctxstr(st, args[0])); else if (uc->etype && n->expr.nargs != 2) fatal(n, "union constructor `%s needs arg ", ctxstr(st, args[0])); return uc; } /* Binds the type parameters present in the * current type into the type environment */ static void putbindings(Inferstate *st, Htab *bt, Type *t) { size_t i; char *s; if (!t) return; if (t->type != Typaram) return; if (debugopt['u']) { s = tystr(t); indentf(st->indentdepth, "Bind %s\n", s); free(s); } if (hthas(bt, t->pname)) unify(st, NULL, htget(bt, t->pname), t); else if (isbound(st, t)) return; htput(bt, t->pname, t); for (i = 0; i < t->narg; i++) putbindings(st, bt, t->arg[i]); } static void tybind(Inferstate *st, Type *t) { Htab *bt; char *s; if (t->type != Tygeneric) return; if (debugopt['u']) { s = tystr(t); indentf(st->indentdepth, "Binding %s\n", s); free(s); } bt = mkht(strhash, streq); lappend(&st->tybindings, &st->ntybindings, bt); putbindings(st, bt, t); } /* Binds the type parameters in the * declaration into the type environment */ static void bind(Inferstate *st, Node *n) { Htab *bt; assert(n->type == Ndecl); if (!n->decl.isgeneric) return; if (!n->decl.init) fatal(n, "generic %s has no initializer", n->decl); st->ingeneric++; bt = mkht(strhash, streq); lappend(&st->tybindings, &st->ntybindings, bt); putbindings(st, bt, n->decl.type); putbindings(st, bt, n->decl.init->expr.type); } /* Rolls back the binding of type parameters in * the type environment */ static void unbind(Inferstate *st, Node *n) { if (!n->decl.isgeneric) return; htfree(st->tybindings[st->ntybindings - 1]); lpop(&st->tybindings, &st->ntybindings); st->ingeneric--; } static void tyunbind(Inferstate *st, Type *t) { if (t->type != Tygeneric) return; htfree(st->tybindings[st->ntybindings - 1]); lpop(&st->tybindings, &st->ntybindings); } /* Constrains a type to implement the required constraints. On * type variables, the constraint is added to the required * constraint list. Otherwise, the type is checked to see * if it has the required constraint */ static void constrain(Inferstate *st, Node *ctx, Type *a, Trait *c) { if (a->type == Tyvar) { if (!a->traits) a->traits = mkbs(); settrait(a, c); } else if (!a->traits || !bshas(a->traits, c->uid)) { fatal(ctx, "%s needs %s near %s", tystr(a), namestr(c->name), ctxstr(st, ctx)); } } /* does b satisfy all the constraints of a? */ static int checktraits(Type *a, Type *b) { /* a has no traits to satisfy */ if (!a->traits) return 1; /* b satisfies no traits; only valid if a requires none */ if (!b->traits) return bscount(a->traits) == 0; /* if a->traits is a subset of b->traits, all of * a's constraints are satisfied by b. */ return bsissubset(a->traits, b->traits); } /* Merges the constraints on types */ static void mergetraits(Inferstate *st, Node *ctx, Type *a, Type *b) { size_t i, n; char *sep; char traitbuf[1024], abuf[1024], bbuf[1024]; if (b->type == Tyvar) { /* make sure that if a = b, both have same traits */ if (a->traits && b->traits) bsunion(b->traits, a->traits); else if (a->traits) b->traits = bsdup(a->traits); else if (b->traits) a->traits = bsdup(b->traits); } else { if (!checktraits(a, b)) { sep = ""; n = 0; for (i = 0; bsiter(a->traits, &i); i++) { if (!b->traits || !bshas(b->traits, i)) n += snprintf(traitbuf + n, sizeof(traitbuf) - n, "%s%s", sep, namestr(traittab[i]->name)); sep = ","; } tyfmt(abuf, sizeof abuf, a); tyfmt(bbuf, sizeof bbuf, b); fatal(ctx, "%s missing traits %s for %s near %s", bbuf, traitbuf, abuf, ctxstr(st, ctx)); } } } /* Tells us if we have an index hack on the type */ static int idxhacked(Type *a, Type *b) { if (a->type == Tyvar && a->nsub > 0) return 1; if (a->type == Tyarray || a->type == Tyslice) return a->type == b->type; return 0; } /* prevents types that contain themselves in the unification; * eg @a U (@a -> foo) */ static int occurs(Type *a, Type *b) { size_t i; if (a == b) return 1; for (i = 0; i < b->nsub; i++) if (occurs(a, b->sub[i])) return 1; return 0; } /* Computes the 'rank' of the type; ie, in which * direction should we unify. A lower ranked type * should be mapped to the higher ranked (ie, more * specific) type. */ static int tyrank(Type *t) { /* plain tyvar */ if (t->type == Tyvar && t->nsub == 0) return 0; /* parameterized tyvar */ if (t->type == Tyvar && t->nsub > 0) return 1; /* concrete type */ return 2; } static int hasparam(Type *t) { return t->type == Tyname && t->narg > 0; } static void unionunify(Inferstate *st, Node *ctx, Type *u, Type *v) { size_t i, j; int found; if (u->nmemb != v->nmemb) fatal(ctx, "can't unify %s and %s near %s\n", tystr(u), tystr(v), ctxstr(st, ctx)); for (i = 0; i < u->nmemb; i++) { found = 0; for (j = 0; j < v->nmemb; j++) { if (strcmp(namestr(u->udecls[i]->name), namestr(v->udecls[i]->name)) != 0) continue; found = 1; if (u->udecls[i]->etype == NULL && v->udecls[i]->etype == NULL) continue; else if (u->udecls[i]->etype && v->udecls[i]->etype) unify(st, ctx, u->udecls[i]->etype, v->udecls[i]->etype); else fatal(ctx, "can't unify %s and %s near %s\n", tystr(u), tystr(v), ctxstr(st, ctx)); } if (!found) fatal(ctx, "can't unify %s and %s near %s\n", tystr(u), tystr(v), ctxstr(st, ctx)); } } static void structunify(Inferstate *st, Node *ctx, Type *u, Type *v) { size_t i, j; int found; if (u->nmemb != v->nmemb) fatal(ctx, "can't unify %s and %s near %s\n", tystr(u), tystr(v), ctxstr(st, ctx)); for (i = 0; i < u->nmemb; i++) { found = 0; for (j = 0; j < v->nmemb; j++) { if (strcmp(namestr(u->sdecls[i]->decl.name), namestr(v->sdecls[i]->decl.name)) != 0) continue; found = 1; unify(st, u->sdecls[i], type(st, u->sdecls[i]), type(st, v->sdecls[i])); } if (!found) fatal(ctx, "can't unify %s and %s near %s\n", tystr(u), tystr(v), ctxstr(st, ctx)); } } static void membunify(Inferstate *st, Node *ctx, Type *u, Type *v) { if (hthas(st->delayed, u)) u = htget(st->delayed, u); u = tybase(u); if (hthas(st->delayed, v)) v = htget(st->delayed, v); v = tybase(v); if (u->type == Tyunion && v->type == Tyunion && u != v) unionunify(st, ctx, u, v); else if (u->type == Tystruct && v->type == Tystruct && u != v) structunify(st, ctx, u, v); } /* Unifies two types, or errors if the types are not unifiable. */ static Type *unify(Inferstate *st, Node *ctx, Type *u, Type *v) { Type *t, *r; Type *a, *b; char *from, *to; size_t i; /* a ==> b */ a = tf(st, u); b = tf(st, v); if (a == b) return a; /* we unify from lower to higher ranked types */ if (tyrank(b) < tyrank(a)) { t = a; a = b; b = t; } if (debugopt['u']) { from = tystr(a); to = tystr(b); indentf(st->indentdepth, "Unify %s => %s\n", from, to); free(from); free(to); } r = NULL; if (a->type == Tyvar) { tytab[a->tid] = b; r = b; } /* Disallow recursive types */ if (a->type == Tyvar && b->type != Tyvar) { if (occurs(a, b)) typeerror(st, a, b, ctx, "Infinite type\n"); } /* if the tyrank of a is 0 (ie, a raw tyvar), just unify. * Otherwise, match up subtypes. */ if ((a->type == b->type || idxhacked(a, b)) && tyrank(a) != 0) { if (a->type == Tyname && !nameeq(a->name, b->name)) typeerror(st, a, b, ctx, NULL); if (a->nsub != b->nsub) { if (tybase(a)->type == Tyfunc) typeerror(st, a, b, ctx, "function arity mismatch"); else typeerror(st, a, b, ctx, "subtype counts incompatible"); } for (i = 0; i < b->nsub; i++) unify(st, ctx, a->sub[i], b->sub[i]); r = b; } else if (hasparam(a) && hasparam(b)) { /* Only Tygeneric and Tyname should be able to unify. And they * should have the same names for this to be true. */ if (!nameeq(a->name, b->name)) typeerror(st, a, b, ctx, NULL); if (a->narg != b->narg) typeerror(st, a, b, ctx, "Incompatible parameter lists"); for (i = 0; i < a->narg; i++) unify(st, ctx, a->arg[i], b->arg[i]); } else if (a->type != Tyvar) { typeerror(st, a, b, ctx, NULL); } mergetraits(st, ctx, a, b); if (a->isreflect || b->isreflect) r->isreflect = a->isreflect = b->isreflect = 1; membunify(st, ctx, a, b); /* if we have delayed types for a tyvar, transfer it over. */ if (a->type == Tyvar && b->type == Tyvar) { if (hthas(st->delayed, a) && !hthas(st->delayed, b)) htput(st->delayed, b, htget(st->delayed, a)); else if (hthas(st->delayed, b) && !hthas(st->delayed, a)) htput(st->delayed, a, htget(st->delayed, b)); } else if (hthas(st->delayed, a)) { unify(st, ctx, htget(st->delayed, a), tybase(b)); } return r; } static void markvatypes(Type **types, size_t ntypes) { size_t i; for (i = 0; i < ntypes; i++) types[i]->isreflect = 1; } /* Applies unifications to function calls. * Funciton application requires a slightly * different approach to unification. */ static void unifycall(Inferstate *st, Node *n) { size_t i; Type *ft; char *ret, *ctx; ft = type(st, n->expr.args[0]); if (ft->type == Tyvar) { /* the first arg is the function itself, so it shouldn't be counted */ ft = mktyfunc(n->loc, &n->expr.args[1], n->expr.nargs - 1, mktyvar(n->loc)); unify(st, n, ft, type(st, n->expr.args[0])); } else if (tybase(ft)->type != Tyfunc) { fatal(n, "calling uncallable type %s", tystr(ft)); } /* first arg: function itself */ for (i = 1; i < n->expr.nargs; i++) if (exprtype(n->expr.args[i])->type == Tyvoid) fatal(n, "void passed where value expected, near %s", ctxstr(st, n)); for (i = 1; i < n->expr.nargs; i++) { if (i == ft->nsub) fatal(n, "%s arity mismatch (expected %zd args, got %zd)", ctxstr(st, n->expr.args[0]), ft->nsub - 1, n->expr.nargs - 1); if (ft->sub[i]->type == Tyvalist) { markvatypes(&ft->sub[i], ft->nsub - i); break; } inferexpr(st, &n->expr.args[i], NULL, NULL); unify(st, n->expr.args[0], ft->sub[i], type(st, n->expr.args[i])); } if (i < ft->nsub && ft->sub[i]->type != Tyvalist) fatal(n, "%s arity mismatch (expected %zd args, got %zd)", ctxstr(st, n->expr.args[0]), ft->nsub - 1, i - 1); if (debugopt['u']) { ret = tystr(ft->sub[0]); ctx = ctxstr(st, n->expr.args[0]); indentf(st->indentdepth, "Call of %s returns %s\n", ctx, ret); free(ctx); free(ret); } settype(st, n, ft->sub[0]); } static void unifyparams(Inferstate *st, Node *ctx, Type *a, Type *b) { size_t i; /* The only types with unifiable params are Tyunres and Tyname. * Tygeneric should always be freshened, and no other types have * parameters attached. * * FIXME: Is it possible to have parameterized typarams? */ if (a->type != Tyunres && a->type != Tyname) return; if (b->type != Tyunres && b->type != Tyname) return; if (a->narg != b->narg) fatal(ctx, "mismatched arg list sizes: %s with %s near %s", tystr(a), tystr(b), ctxstr(st, ctx)); for (i = 0; i < a->narg; i++) unify(st, ctx, a->arg[i], b->arg[i]); } static void loaduses(Node *n) { size_t i; /* uses only allowed at top level. Do we want to keep it this way? */ for (i = 0; i < n->file.nuses; i++) readuse(n->file.uses[i], n->file.globls, Visintern); } static Type *initvar(Inferstate *st, Node *n, Node *s) { Type *t; if (s->decl.ishidden) fatal(n, "attempting to refer to hidden decl %s", ctxstr(st, n)); if (s->decl.isgeneric) t = tysubst(st, tf(st, s->decl.type), s->decl.type); else t = s->decl.type; n->expr.did = s->decl.did; n->expr.isconst = s->decl.isconst; if (s->decl.isgeneric && !st->ingeneric) { t = _tyfreshen(st, NULL, t); addspecialization(st, n, curstab()); if (t->type == Tyvar) { settype(st, n, mktyvar(n->loc)); delayedcheck(st, n, curstab()); } else { settype(st, n, t); } } else { settype(st, n, t); } return t; } /* Finds out if the member reference is actually * referring to a namespaced name, instead of a struct * member. If it is, it transforms it into the variable * reference we should have, instead of the Omemb expr * that we do have */ static Node *checkns(Inferstate *st, Node *n, Node **ret) { Node *var, *name, *nsname; Node **args; Stab *stab; Node *s; /* check that this is a namespaced declaration */ if (n->type != Nexpr) return n; if (exprop(n) != Omemb) return n; if (!n->expr.nargs) return n; args = n->expr.args; if (args[0]->type != Nexpr || exprop(args[0]) != Ovar) return n; name = args[0]->expr.args[0]; stab = getns(curstab(), name); if (!stab) return n; /* substitute the namespaced name */ nsname = mknsname(n->loc, namestr(name), namestr(args[1])); s = getdcl(stab, args[1]); if (!s) fatal(n, "undeclared var %s.%s", nsname->name.ns, nsname->name.name); var = mkexpr(n->loc, Ovar, nsname, NULL); var->expr.idx = n->expr.idx; initvar(st, var, s); *ret = var; return var; } static void inferstruct(Inferstate *st, Node *n, int *isconst) { size_t i; *isconst = 1; for (i = 0; i < n->expr.nargs; i++) { infernode(st, &n->expr.args[i], NULL, NULL); if (!n->expr.args[i]->expr.isconst) *isconst = 0; } settype(st, n, mktyvar(n->loc)); delayedcheck(st, n, curstab()); } static void inferarray(Inferstate *st, Node *n, int *isconst) { size_t i; Type *t; Node *len; *isconst = 1; len = mkintlit(n->loc, n->expr.nargs); t = mktyarray(n->loc, mktyvar(n->loc), len); for (i = 0; i < n->expr.nargs; i++) { infernode(st, &n->expr.args[i], NULL, NULL); unify(st, n, t->sub[0], type(st, n->expr.args[i])); if (!n->expr.args[i]->expr.isconst) *isconst = 0; } settype(st, n, t); } static void infertuple(Inferstate *st, Node *n, int *isconst) { Type **types; size_t i; *isconst = 1; types = xalloc(sizeof(Type *)*n->expr.nargs); for (i = 0; i < n->expr.nargs; i++) { infernode(st, &n->expr.args[i], NULL, NULL); n->expr.isconst = n->expr.isconst && n->expr.args[i]->expr.isconst; types[i] = type(st, n->expr.args[i]); } *isconst = n->expr.isconst; settype(st, n, mktytuple(n->loc, types, n->expr.nargs)); } static void inferucon(Inferstate *st, Node *n, int *isconst) { Ucon *uc; Type *t; *isconst = 1; uc = uconresolve(st, n); t = tysubst(st, tf(st, uc->utype), uc->utype); uc = tybase(t)->udecls[uc->id]; if (uc->etype) { inferexpr(st, &n->expr.args[1], NULL, NULL); unify(st, n, uc->etype, type(st, n->expr.args[1])); *isconst = n->expr.args[1]->expr.isconst; } settype(st, n, delayeducon(st, t)); } static void inferpat(Inferstate *st, Node **np, Node *val, Node ***bind, size_t *nbind) { size_t i; Node **args; Node *s, *n; Stab *ns; Type *t; n = *np; n = checkns(st, n, np); args = n->expr.args; for (i = 0; i < n->expr.nargs; i++) if (args[i]->type == Nexpr) inferpat(st, &args[i], val, bind, nbind); switch (exprop(n)) { case Otup: case Ostruct: case Oarr: case Olit: case Omemb: infernode(st, np, NULL, NULL); break; /* arithmetic expressions just need to be constant */ case Oneg: case Oadd: case Osub: case Omul: case Odiv: case Obsl: case Obsr: case Oband: case Obor: case Obxor: case Obnot: infernode(st, np, NULL, NULL); if (!n->expr.isconst) fatal(n, "matching against non-constant expression near %s", ctxstr(st, n)); break; case Oucon: inferucon(st, n, &n->expr.isconst); break; case Ovar: ns = curstab(); if (args[0]->name.ns) ns = getns_str(ns, args[0]->name.ns); s = getdcl(ns, args[0]); if (s && !s->decl.ishidden) { if (s->decl.isgeneric) t = tysubst(st, s->decl.type, s->decl.type); else if (s->decl.isconst) t = s->decl.type; else fatal(n, "pattern shadows variable declared on %s:%d near %s", fname(s->loc), lnum(s->loc), ctxstr(st, s)); } else { t = mktyvar(n->loc); s = mkdecl(n->loc, n->expr.args[0], t); s->decl.init = val; settype(st, n, t); lappend(bind, nbind, s); } settype(st, n, t); n->expr.did = s->decl.did; break; default: fatal(n, "invalid pattern"); break; } } void addbindings(Inferstate *st, Node *n, Node **bind, size_t nbind) { size_t i; /* order of binding shouldn't matter, so push them into the block * in reverse order. */ for (i = 0; i < nbind; i++) { putdcl(n->block.scope, bind[i]); linsert(&n->block.stmts, &n->block.nstmts, 0, bind[i]); } } static void infersub(Inferstate *st, Node *n, Type *ret, int *sawret, int *exprconst) { Node **args; size_t i, nargs; int isconst; args = n->expr.args; nargs = n->expr.nargs; isconst = 1; for (i = 0; i < nargs; i++) { /* Nlit, Nvar, etc should not be inferred as exprs */ if (args[i]->type == Nexpr) { /* Omemb can sometimes resolve to a namespace. We have to check * this. Icky. */ checkns(st, args[i], &args[i]); inferexpr(st, &args[i], ret, sawret); isconst = isconst && args[i]->expr.isconst; } } if (exprop(n) == Ovar) n->expr.isconst = decls[n->expr.did]->decl.isconst; else if (opispure[exprop(n)]) n->expr.isconst = isconst; *exprconst = n->expr.isconst; } static void inferexpr(Inferstate *st, Node **np, Type *ret, int *sawret) { Node **args; size_t i, nargs; Node *s, *n; Type *t; int isconst; n = *np; assert(n->type == Nexpr); args = n->expr.args; nargs = n->expr.nargs; infernode(st, &n->expr.idx, NULL, NULL); n = checkns(st, n, np); switch (exprop(n)) { /* all operands are same type */ case Oadd: /* @a + @a -> @a */ case Osub: /* @a - @a -> @a */ case Omul: /* @a * @a -> @a */ case Odiv: /* @a / @a -> @a */ case Oneg: /* -@a -> @a */ infersub(st, n, ret, sawret, &isconst); t = type(st, args[0]); constrain(st, n, type(st, args[0]), traittab[Tcnum]); isconst = args[0]->expr.isconst; for (i = 1; i < nargs; i++) { isconst = isconst && args[i]->expr.isconst; t = unify(st, n, t, type(st, args[i])); } n->expr.isconst = isconst; settype(st, n, t); break; case Omod: /* @a % @a -> @a */ case Obor: /* @a | @a -> @a */ case Oband: /* @a & @a -> @a */ case Obxor: /* @a ^ @a -> @a */ case Obsl: /* @a << @a -> @a */ case Obsr: /* @a >> @a -> @a */ case Obnot: /* ~@a -> @a */ case Opreinc: /* ++@a -> @a */ case Opredec: /* --@a -> @a */ case Opostinc: /* @a++ -> @a */ case Opostdec: /* @a-- -> @a */ case Oaddeq: /* @a += @a -> @a */ case Osubeq: /* @a -= @a -> @a */ case Omuleq: /* @a *= @a -> @a */ case Odiveq: /* @a /= @a -> @a */ case Omodeq: /* @a %= @a -> @a */ case Oboreq: /* @a |= @a -> @a */ case Obandeq: /* @a &= @a -> @a */ case Obxoreq: /* @a ^= @a -> @a */ case Obsleq: /* @a <<= @a -> @a */ case Obsreq: /* @a >>= @a -> @a */ infersub(st, n, ret, sawret, &isconst); t = type(st, args[0]); constrain(st, n, type(st, args[0]), traittab[Tcnum]); constrain(st, n, type(st, args[0]), traittab[Tcint]); isconst = args[0]->expr.isconst; for (i = 1; i < nargs; i++) { isconst = isconst && args[i]->expr.isconst; t = unify(st, n, t, type(st, args[i])); } n->expr.isconst = isconst; settype(st, n, t); break; case Oasn: /* @a = @a -> @a */ infersub(st, n, ret, sawret, &isconst); t = type(st, args[0]); for (i = 1; i < nargs; i++) t = unify(st, n, t, type(st, args[i])); settype(st, n, t); if (args[0]->expr.isconst) fatal(n, "attempting to assign constant \"%s\"", ctxstr(st, args[0])); break; /* operands same type, returning bool */ case Olor: /* @a || @b -> bool */ case Oland: /* @a && @b -> bool */ case Oeq: /* @a == @a -> bool */ case One: /* @a != @a -> bool */ case Ogt: /* @a > @a -> bool */ case Oge: /* @a >= @a -> bool */ case Olt: /* @a < @a -> bool */ case Ole: /* @a <= @b -> bool */ infersub(st, n, ret, sawret, &isconst); t = type(st, args[0]); for (i = 1; i < nargs; i++) unify(st, n, t, type(st, args[i])); settype(st, n, mktype(Zloc, Tybool)); break; case Olnot: /* !bool -> bool */ infersub(st, n, ret, sawret, &isconst); t = unify(st, n, type(st, args[0]), mktype(Zloc, Tybool)); settype(st, n, t); break; /* reach into a type and pull out subtypes */ case Oaddr: /* &@a -> @a* */ infersub(st, n, ret, sawret, &isconst); settype(st, n, mktyptr(n->loc, type(st, args[0]))); break; case Oderef: /* *@a* -> @a */ infersub(st, n, ret, sawret, &isconst); t = unify(st, n, type(st, args[0]), mktyptr(n->loc, mktyvar(n->loc))); settype(st, n, t->sub[0]); break; case Oidx: /* @a[@b::tcint] -> @a */ infersub(st, n, ret, sawret, &isconst); t = mktyidxhack(n->loc, mktyvar(n->loc)); unify(st, n, type(st, args[0]), t); constrain(st, n, type(st, args[0]), traittab[Tcidx]); constrain(st, n, type(st, args[1]), traittab[Tcint]); settype(st, n, t->sub[0]); break; case Oslice: /* @a[@b::tcint,@b::tcint] -> @a[,] */ infersub(st, n, ret, sawret, &isconst); t = mktyidxhack(n->loc, mktyvar(n->loc)); unify(st, n, type(st, args[0]), t); constrain(st, n, type(st, args[1]), traittab[Tcint]); constrain(st, n, type(st, args[2]), traittab[Tcint]); settype(st, n, mktyslice(n->loc, t->sub[0])); break; /* special cases */ case Omemb: /* @a.Ident -> @b, verify type(@a.Ident)==@b later */ infersub(st, n, ret, sawret, &isconst); settype(st, n, mktyvar(n->loc)); delayedcheck(st, n, curstab()); break; case Osize: /* sizeof @a -> size */ infersub(st, n, ret, sawret, &isconst); settype(st, n, mktylike(n->loc, Tyuint)); break; case Ocall: /* (@a, @b, @c, ... -> @r)(@a,@b,@c, ... -> @r) -> @r */ infersub(st, n, ret, sawret, &isconst); unifycall(st, n); break; case Ocast: /* cast(@a, @b) -> @b */ infersub(st, n, ret, sawret, &isconst); delayedcheck(st, n, curstab()); break; case Oret: /* -> @a -> void */ infersub(st, n, ret, sawret, &isconst); if (sawret) *sawret = 1; if (!ret) fatal(n, "returns are not valid near %s", ctxstr(st, n)); if (nargs) t = unify(st, n, ret, type(st, args[0])); else t = unify(st, n, mktype(Zloc, Tyvoid), ret); settype(st, n, t); break; case Obreak: case Ocontinue: /* nullary: nothing to infer. */ settype(st, n, mktype(Zloc, Tyvoid)); break; case Ojmp: /* goto void* -> void */ infersub(st, n, ret, sawret, &isconst); settype(st, n, mktype(Zloc, Tyvoid)); break; case Ovar: /* a:@a -> @a */ infersub(st, n, ret, sawret, &isconst); /* if we created this from a namespaced var, the type should be * set, and the normal lookup is expected to fail. Since we're * already done with this node, we can just return. */ if (n->expr.type) return; s = getdcl(curstab(), args[0]); if (!s) fatal(n, "undeclared var %s", ctxstr(st, args[0])); initvar(st, n, s); break; case Oucon: inferucon(st, n, &n->expr.isconst); break; case Otup: infertuple(st, n, &n->expr.isconst); break; case Ostruct: inferstruct(st, n, &n->expr.isconst); break; case Oarr: inferarray(st, n, &n->expr.isconst); break; case Olit: /* <lit>:@a::tyclass -> @a */ infersub(st, n, ret, sawret, &isconst); switch (args[0]->lit.littype) { case Lfunc: infernode(st, &args[0]->lit.fnval, NULL, NULL); break; /* FIXME: env capture means this is non-const */ n->expr.isconst = 1; default: n->expr.isconst = 1; break; } settype(st, n, type(st, args[0])); break; case Obad: case Ocjmp: case Ojtab: case Oset: case Oslbase: case Osllen: case Outag: case Oblit: case Oclear: case Oudata: case Otrunc: case Oswiden: case Ozwiden: case Oint2flt: case Oflt2int: case Oflt2flt: case Ofadd: case Ofsub: case Ofmul: case Ofdiv: case Ofneg: case Ofeq: case Ofne: case Ofgt: case Ofge: case Oflt: case Ofle: case Oueq: case Oune: case Ougt: case Ouge: case Oult: case Oule: case Numops: die("Should not see %s in fe", opstr[exprop(n)]); break; } } static void inferfunc(Inferstate *st, Node *n) { size_t i; int sawret; sawret = 0; for (i = 0; i < n->func.nargs; i++) infernode(st, &n->func.args[i], NULL, NULL); infernode(st, &n->func.body, n->func.type->sub[0], &sawret); /* if there's no return stmt in the function, assume void ret */ if (!sawret) unify(st, n, type(st, n)->sub[0], mktype(Zloc, Tyvoid)); } static void specializeimpl(Inferstate *st, Node *n) { Node *dcl, *proto, *name; Htab *ht; Trait *t; Type *ty; size_t i, j; t = gettrait(curstab(), n->impl.traitname); if (!t) fatal(n, "no trait %s\n", namestr(n->impl.traitname)); n->impl.trait = t; dcl = NULL; proto = NULL; for (i = 0; i < n->impl.ndecls; i++) { /* look up the prototype */ proto = NULL; dcl = n->impl.decls[i]; /* since the decls in an impl are not installed in a namespace, their names are not updated when we call updatens() on the symbol table. Because we need to do namespace dependent comparisons for specializing, we need to set the namespace here. */ if (file->file.globls->name) setns(dcl->decl.name, file->file.globls->name); for (j = 0; j < t->nfuncs; j++) { if (nameeq(dcl->decl.name, t->funcs[j]->decl.name)) { proto = t->funcs[j]; break; } } if (!proto) fatal(n, "declaration %s missing in %s, near %s", namestr(dcl->decl.name), namestr(t->name), ctxstr(st, n)); /* infer and unify types */ if (n->impl.type->type == Tygeneric || n->impl.type->type == Typaram) fatal(n, "trait specialization requires concrete type, got %s", tystr(n->impl.type)); checktraits(t->param, n->impl.type); ht = mkht(tyhash, tyeq); htput(ht, t->param, n->impl.type); ty = tyspecialize(type(st, proto), ht, st->delayed); htfree(ht); inferdecl(st, dcl); unify(st, n, type(st, dcl), ty); /* and put the specialization into the global stab */ name = genericname(proto, ty); dcl->decl.name = name; putdcl(file->file.globls, dcl); if (debugopt['S']) printf("specializing trait [%d]%s:%s => %s:%s\n", n->loc.line, namestr(proto->decl.name), tystr(type(st, proto)), namestr(name), tystr(ty)); dcl->decl.vis = t->vis; lappend(&file->file.stmts, &file->file.nstmts, dcl); } } static void inferdecl(Inferstate *st, Node *n) { Type *t; t = tf(st, decltype(n)); if (t->type == Tygeneric && !n->decl.isgeneric) { t = _tyfreshen(st, NULL, t); unifyparams(st, n, t, decltype(n)); } settype(st, n, t); if (n->decl.init) { inferexpr(st, &n->decl.init, NULL, NULL); unify(st, n, type(st, n), type(st, n->decl.init)); if (n->decl.isconst && !n->decl.init->expr.isconst) fatal(n, "non-const initializer for \"%s\"", ctxstr(st, n)); } else { if ((n->decl.isconst || n->decl.isgeneric) && !n->decl.isextern) fatal(n, "non-extern \"%s\" has no initializer", ctxstr(st, n)); } } static void inferstab(Inferstate *st, Stab *s) { void **k; size_t n, i; Type *t; k = htkeys(s->ty, &n); for (i = 0; i < n; i++) { t = gettype(s, k[i]); if (!t) fatal(k[i], "undefined type %s", namestr(k[i])); t = tysearch(t); updatetype(s, k[i], t); } free(k); } static void infernode(Inferstate *st, Node **np, Type *ret, int *sawret) { size_t i, nbound; Node **bound, *n; Type *t; n = *np; if (!n) return; switch (n->type) { case Nfile: pushstab(n->file.globls); inferstab(st, n->file.globls); for (i = 0; i < n->file.nstmts; i++) infernode(st, &n->file.stmts[i], NULL, sawret); popstab(); break; case Ndecl: if (debugopt['u']) indentf(st->indentdepth, "--- infer %s ---\n", declname(n)); st->indentdepth++; bind(st, n); inferdecl(st, n); if (type(st, n)->type == Typaram && !st->ingeneric) fatal(n, "generic type %s in non-generic near %s", tystr(type(st, n)), ctxstr(st, n)); unbind(st, n); st->indentdepth--; if (debugopt['u']) indentf(st->indentdepth, "--- done ---\n"); break; case Nblock: setsuper(n->block.scope, curstab()); pushstab(n->block.scope); inferstab(st, n->block.scope); for (i = 0; i < n->block.nstmts; i++) { infernode(st, &n->block.stmts[i], ret, sawret); } popstab(); break; case Nifstmt: infernode(st, &n->ifstmt.cond, NULL, sawret); infernode(st, &n->ifstmt.iftrue, ret, sawret); infernode(st, &n->ifstmt.iffalse, ret, sawret); unify(st, n, type(st, n->ifstmt.cond), mktype(n->loc, Tybool)); break; case Nloopstmt: infernode(st, &n->loopstmt.init, ret, sawret); infernode(st, &n->loopstmt.cond, NULL, sawret); infernode(st, &n->loopstmt.step, ret, sawret); infernode(st, &n->loopstmt.body, ret, sawret); unify(st, n, type(st, n->loopstmt.cond), mktype(n->loc, Tybool)); break; case Niterstmt: bound = NULL; nbound = 0; inferpat(st, &n->iterstmt.elt, NULL, &bound, &nbound); addbindings(st, n->iterstmt.body, bound, nbound); infernode(st, &n->iterstmt.seq, NULL, sawret); infernode(st, &n->iterstmt.body, ret, sawret); t = mktyidxhack(n->loc, mktyvar(n->loc)); constrain(st, n, type(st, n->iterstmt.seq), traittab[Tcidx]); unify(st, n, type(st, n->iterstmt.seq), t); unify(st, n, type(st, n->iterstmt.elt), t->sub[0]); break; case Nmatchstmt: infernode(st, &n->matchstmt.val, NULL, sawret); if (tybase(type(st, n->matchstmt.val))->type == Tyvoid) fatal(n, "can't match against a void type near %s", ctxstr(st, n->matchstmt.val)); for (i = 0; i < n->matchstmt.nmatches; i++) { infernode(st, &n->matchstmt.matches[i], ret, sawret); unify(st, n->matchstmt.matches[i]->match.pat, type(st, n->matchstmt.val), type(st, n->matchstmt.matches[i]->match.pat)); } break; case Nmatch: bound = NULL; nbound = 0; inferpat(st, &n->match.pat, NULL, &bound, &nbound); addbindings(st, n->match.block, bound, nbound); infernode(st, &n->match.block, ret, sawret); break; case Nexpr: inferexpr(st, np, ret, sawret); break; case Nfunc: setsuper(n->func.scope, curstab()); if (st->ntybindings > 0) for (i = 0; i < n->func.nargs; i++) putbindings(st, st->tybindings[st->ntybindings - 1], n->func.args[i]->decl.type); pushstab(n->func.scope); inferstab(st, n->func.scope); inferfunc(st, n); popstab(); break; case Nimpl: specializeimpl(st, n); break; case Nname: case Nlit: case Nuse: break; case Nnone: die("Nnone should not be seen as node type!"); break; } } /* returns the final type for t, after all unifications * and default constraint selections */ static Type *tyfix(Inferstate *st, Node *ctx, Type *orig, int noerr) { static Type *tyint, *tyflt; Type *t, *delayed; char *from, *to; size_t i; char buf[1024]; if (!tyint) tyint = mktype(Zloc, Tyint); if (!tyflt) tyflt = mktype(Zloc, Tyflt64); t = tysearch(orig); if (orig->type == Tyvar && hthas(st->delayed, orig)) { delayed = htget(st->delayed, orig); if (t->type == Tyvar) t = delayed; else if (tybase(t)->type != delayed->type && !noerr) fatal(ctx, "type %s not compatible with %s near %s\n", tystr(t), tystr(delayed), ctxstr(st, ctx)); } if (t->type == Tyvar) { if (hastrait(t, traittab[Tcint]) && checktraits(t, tyint)) t = tyint; if (hastrait(t, traittab[Tcfloat]) && checktraits(t, tyflt)) t = tyflt; } else if (!t->fixed) { t->fixed = 1; if (t->type == Tyarray) { typesub(st, t->asize); } else if (t->type == Tystruct) { st->intype++; for (i = 0; i < t->nmemb; i++) typesub(st, t->sdecls[i]); st->intype--; } else if (t->type == Tyunion) { for (i = 0; i < t->nmemb; i++) { if (t->udecls[i]->etype) { tyresolve(st, t->udecls[i]->etype); t->udecls[i]->etype = tyfix(st, ctx, t->udecls[i]->etype, noerr); } } } else if (t->type == Tyname) { for (i = 0; i < t->narg; i++) t->arg[i] = tyfix(st, ctx, t->arg[i], noerr); } for (i = 0; i < t->nsub; i++) t->sub[i] = tyfix(st, ctx, t->sub[i], noerr); } if (t->type == Tyvar && !noerr) { if (debugopt['T']) dump(file, stdout); fatal(ctx, "underconstrained type %s near %s", tyfmt(buf, 1024, t), ctxstr(st, ctx)); } if (debugopt['u'] && !tyeq(orig, t)) { from = tystr(orig); to = tystr(t); indentf(st->indentdepth, "subst %s => %s\n", from, to); free(from); free(to); } return t; } static void checkcast(Inferstate *st, Node *n) { /* FIXME: actually verify the casts. Right now, it's ok to leave this * unimplemented because bad casts get caught by the backend. */ } static void infercompn(Inferstate *st, Node *n) { Node *aggr; Node *memb; Node **nl; Type *t; size_t i; int found; aggr = n->expr.args[0]; memb = n->expr.args[1]; found = 0; t = tybase(tf(st, type(st, aggr))); /* all array-like types have a fake "len" member that we emulate */ if (t->type == Tyslice || t->type == Tyarray) { if (!strcmp(namestr(memb), "len")) { constrain(st, n, type(st, n), traittab[Tcnum]); constrain(st, n, type(st, n), traittab[Tcint]); found = 1; } /* otherwise, we search aggregate types for the member, and unify * the expression with the member type; ie: * * x: aggrtype y : memb in aggrtype * --------------------------------------- * x.y : membtype */ } else { if (tybase(t)->type == Typtr) t = tybase(tf(st, t->sub[0])); if (tybase(t)->type != Tystruct) { if (tybase(t)->type == Tyvar) fatal(n, "underspecified type defined on %s:%d used near %s", fname(t->loc), lnum(t->loc), ctxstr(st, n)); else fatal(n, "type %s does not support member operators near %s", tystr(t), ctxstr(st, n)); } nl = t->sdecls; for (i = 0; i < t->nmemb; i++) { if (!strcmp(namestr(memb), declname(nl[i]))) { unify(st, n, type(st, n), decltype(nl[i])); found = 1; break; } } } if (!found) fatal(aggr, "type %s has no member \"%s\" near %s", tystr(type(st, aggr)), ctxstr(st, memb), ctxstr(st, aggr)); } static void checkstruct(Inferstate *st, Node *n) { Type *t, *et; Node *val, *name; size_t i, j; t = tybase(tf(st, n->lit.type)); if (t->type != Tystruct) { /* * If we haven't inferred the type, and it's inside another struct, * we'll eventually get to it. * * If, on the other hand, it is genuinely underspecified, we'll give * a better error on it later. */ return; } for (i = 0; i < n->expr.nargs; i++) { val = n->expr.args[i]; name = val->expr.idx; et = NULL; for (j = 0; j < t->nmemb; j++) { if (!strcmp(namestr(t->sdecls[j]->decl.name), namestr(name))) { et = type(st, t->sdecls[j]); break; } } if (!et) fatal(n, "could not find member %s in struct %s, near %s", namestr(name), tystr(t), ctxstr(st, n)); unify(st, val, et, type(st, val)); } } static void checkvar(Inferstate *st, Node *n) { Node *dcl; dcl = decls[n->expr.did]; unify(st, n, type(st, n), _tyfreshen(st, NULL, type(st, dcl))); } static void postcheck(Inferstate *st, Node *file) { size_t i; Node *n; for (i = 0; i < st->npostcheck; i++) { n = st->postcheck[i]; pushstab(st->postcheckscope[i]); if (n->type == Nexpr && exprop(n) == Omemb) infercompn(st, n); else if (n->type == Nexpr && exprop(n) == Ocast) checkcast(st, n); else if (n->type == Nexpr && exprop(n) == Ostruct) checkstruct(st, n); else if (n->type == Nexpr && exprop(n) == Ovar) checkvar(st, n); else die("Thing we shouldn't be checking in postcheck\n"); popstab(); } } /* After inference, replace all * types in symbol tables with * the final computed types */ static void stabsub(Inferstate *st, Stab *s) { void **k; size_t n, i; Type *t; Node *d; k = htkeys(s->ty, &n); for (i = 0; i < n; i++) { t = tysearch(gettype(s, k[i])); updatetype(s, k[i], t); tyfix(st, k[i], t, 0); } free(k); k = htkeys(s->dcl, &n); for (i = 0; i < n; i++) { d = getdcl(s, k[i]); if (d) d->decl.type = tyfix(st, d, d->decl.type, 0); } free(k); } static void checkrange(Inferstate *st, Node *n) { Type *t; int64_t sval; uint64_t uval; static const int64_t svranges[][2] = { /* signed ints */ [Tyint8] = {-128LL, 127LL}, [Tyint16] = {-32768LL, 32767LL}, [Tyint32] = {-2147483648LL, 2*2147483647LL}, /* FIXME: this has been doubled allow for uints... */ [Tyint] = {-2147483648LL, 2*2147483647LL}, [Tyint64] = {-9223372036854775808ULL, 9223372036854775807LL}, [Tylong] = {-9223372036854775808ULL, 9223372036854775807LL}, }; static const uint64_t uvranges[][2] = { [Tybyte] = {0, 255ULL}, [Tyuint8] = {0, 255ULL}, [Tyuint16] = {0, 65535ULL}, [Tyuint32] = {0, 4294967295ULL}, [Tyuint64] = {0, 18446744073709551615ULL}, [Tyulong] = {0, 18446744073709551615ULL}, [Tychar] = {0, 4294967295ULL}, }; /* signed types */ t = type(st, n); if (t->type >= Tyint8 && t->type <= Tylong) { sval = n->lit.intval; if (sval < svranges[t->type][0] || sval > svranges[t->type][1]) fatal(n, "literal value %lld out of range for type \"%s\"", sval, tystr(t)); } else if ((t->type >= Tybyte && t->type <= Tyulong) || t->type == Tychar) { uval = n->lit.intval; if (uval < uvranges[t->type][0] || uval > uvranges[t->type][1]) fatal(n, "literal value %llu out of range for type \"%s\"", uval, tystr(t)); } } /* After type inference, replace all types * with the final computed type */ static void typesub(Inferstate *st, Node *n) { size_t i; if (!n) return; switch (n->type) { case Nfile: pushstab(n->file.globls); stabsub(st, n->file.globls); for (i = 0; i < n->file.nstmts; i++) typesub(st, n->file.stmts[i]); popstab(); break; case Ndecl: settype(st, n, tyfix(st, n, type(st, n), 0)); if (n->decl.init) typesub(st, n->decl.init); break; case Nblock: pushstab(n->block.scope); for (i = 0; i < n->block.nstmts; i++) typesub(st, n->block.stmts[i]); popstab(); break; case Nifstmt: typesub(st, n->ifstmt.cond); typesub(st, n->ifstmt.iftrue); typesub(st, n->ifstmt.iffalse); break; case Nloopstmt: typesub(st, n->loopstmt.cond); typesub(st, n->loopstmt.init); typesub(st, n->loopstmt.step); typesub(st, n->loopstmt.body); break; case Niterstmt: typesub(st, n->iterstmt.elt); typesub(st, n->iterstmt.seq); typesub(st, n->iterstmt.body); break; case Nmatchstmt: typesub(st, n->matchstmt.val); for (i = 0; i < n->matchstmt.nmatches; i++) { typesub(st, n->matchstmt.matches[i]); } break; case Nmatch: typesub(st, n->match.pat); typesub(st, n->match.block); break; case Nexpr: settype(st, n, tyfix(st, n, type(st, n), 0)); typesub(st, n->expr.idx); if (exprop(n) == Ocast && exprop(n->expr.args[0]) == Olit && n->expr.args[0]->expr.args[0]->lit.littype == Lint) { settype(st, n->expr.args[0], exprtype(n)); settype(st, n->expr.args[0]->expr.args[0], exprtype(n)); } for (i = 0; i < n->expr.nargs; i++) typesub(st, n->expr.args[i]); break; case Nfunc: pushstab(n->func.scope); settype(st, n, tyfix(st, n, n->func.type, 0)); for (i = 0; i < n->func.nargs; i++) typesub(st, n->func.args[i]); typesub(st, n->func.body); popstab(); break; case Nlit: settype(st, n, tyfix(st, n, type(st, n), 0)); switch (n->lit.littype) { case Lfunc: typesub(st, n->lit.fnval); break; case Lint: checkrange(st, n); default: break; } break; case Nimpl: case Nname: case Nuse: break; case Nnone: die("Nnone should not be seen as node type!"); break; } } static void taghidden(Type *t) { size_t i; if (t->vis != Visintern) return; t->vis = Vishidden; for (i = 0; i < t->nsub; i++) taghidden(t->sub[i]); switch (t->type) { case Tystruct: for (i = 0; i < t->nmemb; i++) taghidden(decltype(t->sdecls[i])); break; case Tyunion: for (i = 0; i < t->nmemb; i++) if (t->udecls[i]->etype) taghidden(t->udecls[i]->etype); break; case Tyname: t->isreflect = 1; for (i = 0; i < t->narg; i++) taghidden(t->arg[i]); case Tygeneric: for (i = 0; i < t->ngparam; i++) taghidden(t->gparam[i]); break; default: break; } } int isexportinit(Node *n) { if (n->decl.isgeneric && !n->decl.trait) return 1; /* we want to inline small values, which means we need to export them */ if (istyprimitive(n->decl.type)) return 1; return 0; } static void nodetag(Stab *st, Node *n, int ingeneric, int hidelocal) { size_t i; Node *d; if (!n) return; switch (n->type) { case Nblock: for (i = 0; i < n->block.nstmts; i++) nodetag(st, n->block.stmts[i], ingeneric, hidelocal); break; case Nifstmt: nodetag(st, n->ifstmt.cond, ingeneric, hidelocal); nodetag(st, n->ifstmt.iftrue, ingeneric, hidelocal); nodetag(st, n->ifstmt.iffalse, ingeneric, hidelocal); break; case Nloopstmt: nodetag(st, n->loopstmt.init, ingeneric, hidelocal); nodetag(st, n->loopstmt.cond, ingeneric, hidelocal); nodetag(st, n->loopstmt.step, ingeneric, hidelocal); nodetag(st, n->loopstmt.body, ingeneric, hidelocal); break; case Niterstmt: nodetag(st, n->iterstmt.elt, ingeneric, hidelocal); nodetag(st, n->iterstmt.seq, ingeneric, hidelocal); nodetag(st, n->iterstmt.body, ingeneric, hidelocal); break; case Nmatchstmt: nodetag(st, n->matchstmt.val, ingeneric, hidelocal); for (i = 0; i < n->matchstmt.nmatches; i++) nodetag(st, n->matchstmt.matches[i], ingeneric, hidelocal); break; case Nmatch: nodetag(st, n->match.pat, ingeneric, hidelocal); nodetag(st, n->match.block, ingeneric, hidelocal); break; case Nexpr: nodetag(st, n->expr.idx, ingeneric, hidelocal); taghidden(n->expr.type); for (i = 0; i < n->expr.nargs; i++) nodetag(st, n->expr.args[i], ingeneric, hidelocal); /* generics need to have the decls they refer to exported. */ if (ingeneric && exprop(n) == Ovar) { d = decls[n->expr.did]; if (d->decl.isglobl && d->decl.vis == Visintern) { d->decl.vis = Vishidden; nodetag(st, d, ingeneric, hidelocal); } } break; case Nlit: taghidden(n->lit.type); if (n->lit.littype == Lfunc) nodetag(st, n->lit.fnval, ingeneric, hidelocal); break; case Ndecl: taghidden(n->decl.type); if (hidelocal && n->decl.ispkglocal) n->decl.vis = Vishidden; n->decl.isexportinit = isexportinit(n); if (n->decl.isexportinit) nodetag(st, n->decl.init, n->decl.isgeneric, hidelocal); break; case Nfunc: taghidden(n->func.type); for (i = 0; i < n->func.nargs; i++) nodetag(st, n->func.args[i], ingeneric, hidelocal); nodetag(st, n->func.body, ingeneric, hidelocal); break; case Nimpl: for (i = 0; i < n->impl.ndecls; i++) { n->impl.decls[i]->decl.vis = Vishidden; nodetag(st, n->impl.decls[i], 0, hidelocal); } break; case Nuse: case Nname: break; case Nfile: case Nnone: die("Invalid node for type export\n"); break; } } void tagexports(Stab *st, int hidelocal) { void **k; Node *s; Type *t; Trait *tr; size_t i, j, n; k = htkeys(st->dcl, &n); for (i = 0; i < n; i++) { s = getdcl(st, k[i]); if (s->decl.vis == Visexport) nodetag(st, s, 0, hidelocal); } free(k); k = htkeys(st->impl, &n); for (i = 0; i < n; i++) { s = getimpl(st, k[i]); if (s->impl.vis == Visexport) nodetag(st, s, 0, hidelocal); } free(k); k = htkeys(st->tr, &n); for (i = 0; i < n; i++) { tr = gettrait(st, k[i]); if (tr->vis == Visexport) { tr->param->vis = Visexport; for (i = 0; i < tr->nmemb; i++) { tr->memb[i]->decl.vis = Visexport; nodetag(st, tr->memb[i], 0, hidelocal); } for (i = 0; i < tr->nfuncs; i++) { tr->funcs[i]->decl.vis = Visexport; nodetag(st, tr->funcs[i], 0, hidelocal); } } } free(k); /* get the explicitly exported symbols */ k = htkeys(st->ty, &n); for (i = 0; i < n; i++) { t = gettype(st, k[i]); if (!t->isreflect && t->vis != Visexport) continue; if (hidelocal && t->ispkglocal) t->vis = Vishidden; taghidden(t); for (j = 0; j < t->nsub; j++) taghidden(t->sub[j]); if (t->type == Tyname) { t->isreflect = 1; for (j = 0; j < t->narg; j++) taghidden(t->arg[j]); } else if (t->type == Tygeneric) { for (j = 0; j < t->ngparam; j++) taghidden(t->gparam[j]); } } free(k); } /* Take generics and build new versions of them * with the type parameters replaced with the * specialized types */ static void specialize(Inferstate *st, Node *f) { Node *d, *name; size_t i; for (i = 0; i < st->nspecializations; i++) { pushstab(st->specializationscope[i]); d = specializedcl(st->genericdecls[i], st->specializations[i]->expr.type, &name); st->specializations[i]->expr.args[0] = name; st->specializations[i]->expr.did = d->decl.did; /* we need to sub in default types in the specialization, so call * typesub on the specialized function */ typesub(st, d); popstab(); } } void applytraits(Inferstate *st, Node *f) { size_t i; Node *n; Trait *trait; Type *ty; pushstab(f->file.globls); /* for now, traits can only be declared globally */ for (i = 0; i < f->file.nstmts; i++) { if (f->file.stmts[i]->type == Nimpl) { n = f->file.stmts[i]; trait = gettrait(f->file.globls, n->impl.traitname); if (!trait) fatal(n, "trait %s does not exist near %s", namestr(n->impl.traitname), ctxstr(st, n)); ty = tf(st, n->impl.type); settrait(ty, trait); } } popstab(); } void infer(Node *file) { Inferstate st = {0,}; assert(file->type == Nfile); st.delayed = mkht(tyhash, tyeq); /* set up the symtabs */ loaduses(file); //mergeexports(&st, file); /* do the inference */ applytraits(&st, file); infernode(&st, &file, NULL, NULL); postcheck(&st, file); /* and replace type vars with actual types */ typesub(&st, file); specialize(&st, file); }