summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2017-07-15 00:36:08 -0700
committerOri Bernstein <ori@eigenstate.org>2017-07-15 00:36:42 -0700
commit357f87c1117edfdf77411781ebfae221a406c454 (patch)
tree5e70ba66596b8ee13ceb46e2c9268fe12101f17a
parent15b5fb5c0f9fee25b01a245229efcef21c103bdc (diff)
downloadmc-357f87c1117edfdf77411781ebfae221a406c454.tar.gz
Type binding refactoring now compiles.
Still a bit sloppy on a few things, needs some dedup work, but it's working.
-rw-r--r--lib/std/endian.myr4
-rw-r--r--lib/std/fmt.myr2
-rw-r--r--lib/std/intparse.myr2
-rw-r--r--lib/thread/common.myr2
-rw-r--r--parse/dump.c26
-rw-r--r--parse/gram.y4
-rw-r--r--parse/infer.c254
-rw-r--r--parse/node.c15
-rw-r--r--parse/parse.h18
-rw-r--r--parse/specialize.c2
-rw-r--r--parse/stab.c196
-rw-r--r--parse/type.c17
-rw-r--r--parse/use.c56
-rw-r--r--util/bitset.c9
-rw-r--r--util/htab.c4
-rw-r--r--util/util.h2
16 files changed, 367 insertions, 246 deletions
diff --git a/lib/std/endian.myr b/lib/std/endian.myr
index a705d8c..874ab71 100644
--- a/lib/std/endian.myr
+++ b/lib/std/endian.myr
@@ -10,7 +10,7 @@ generic hosttonet = {v : @a::(integral,numeric)
var ret
ret = 0
- for i = 0; i < sizeof(@a); i++
+ for i = 0; i < sizeof(@a::(integral,numeric)); i++
ret <<= 8
ret |= v & 0xff
v >>= 8
@@ -23,7 +23,7 @@ generic nettohost = {v : @a::(integral,numeric)
var ret
ret = 0
- for i = 0; i < sizeof(@a); i++
+ for i = 0; i < sizeof(@a::(integral,numeric)); i++
ret <<= 8
ret |= v & 0xff
v >>= 8
diff --git a/lib/std/fmt.myr b/lib/std/fmt.myr
index 92782d3..794218a 100644
--- a/lib/std/fmt.myr
+++ b/lib/std/fmt.myr
@@ -594,7 +594,7 @@ generic intfmt = {sb, opts, signed, bits : @a::(integral,numeric)
;;
else
val = (bits : uint64)
- val &= ~0 >> (8*(sizeof(uint64)-sizeof(@a)))
+ val &= ~0 >> (8*(sizeof(uint64)-sizeof(@a::(integral,numeric))))
isneg = false
;;
diff --git a/lib/std/intparse.myr b/lib/std/intparse.myr
index 405e6c3..e9686b3 100644
--- a/lib/std/intparse.myr
+++ b/lib/std/intparse.myr
@@ -47,7 +47,7 @@ generic intparsebase = {s, base
-> doparse(s, isneg, base)
}
-generic doparse = {s, isneg, base
+generic doparse = {s, isneg, base -> option(@a::(integral,numeric))
var v
var cv : int32
diff --git a/lib/thread/common.myr b/lib/thread/common.myr
index 0268af3..66fc9d5 100644
--- a/lib/thread/common.myr
+++ b/lib/thread/common.myr
@@ -1,5 +1,5 @@
use std
pkg thread =
- generic Zptr = (0 : @a#)
+ pkglocal generic Zptr : @a# = (0 : @a#)
;;
diff --git a/parse/dump.c b/parse/dump.c
index 463c732..f84eea1 100644
--- a/parse/dump.c
+++ b/parse/dump.c
@@ -103,6 +103,26 @@ outstab(Stab *st, FILE *fd, int depth)
}
}
+static void
+outenv(Tyenv *e, FILE *fd, int depth)
+{
+ size_t n, i;
+ void **k;
+ Type *t;
+ char *s;
+
+ if (e->tab) {
+ k = htkeys(e->tab, &n);
+ for (i = 0; i < n; i++) {
+ t = htget(e->tab, k[i]);
+ s = tystr(t);
+ findentf(fd, depth + 1, "B %s\n", s);
+ free(s);
+ }
+ free(k);
+ }
+}
+
void
dumpstab(Stab *st, FILE *fd)
{
@@ -110,6 +130,12 @@ dumpstab(Stab *st, FILE *fd)
}
void
+dumpenv(Tyenv *e, FILE *fd)
+{
+ outenv(e, fd, 0);
+}
+
+void
dumpfilestabs(Node *file, int depth, FILE *fd)
{
size_t nk, i;
diff --git a/parse/gram.y b/parse/gram.y
index f889aa1..5ebfebb 100644
--- a/parse/gram.y
+++ b/parse/gram.y
@@ -477,7 +477,9 @@ typarams: generictype {
$$.types = NULL; $$.ntypes = 0;
lappend(&$$.types, &$$.ntypes, $1);
}
- | typarams Tcomma generictype {lappend(&$$.types, &$$.ntypes, $3);}
+ | typarams Tcomma generictype {
+ lappend(&$$.types, &$$.ntypes, $3);
+ }
;
type : structdef
diff --git a/parse/infer.c b/parse/infer.c
index 3f3f181..80a55ec 100644
--- a/parse/infer.c
+++ b/parse/infer.c
@@ -20,10 +20,6 @@ static void inferexpr(Node **np, Type *ret, int *sawret);
static void inferdecl(Node *n);
static Type *tf(Type *t);
-static void tybind(Type *t);
-static void bind(Node *n);
-static void tyunbind();
-static void unbind(Node *n);
static Type *unify(Node *ctx, Type *a, Type *b);
static Type *tyfix(Node *ctx, Type *orig, int noerr);
@@ -56,10 +52,6 @@ static Stab **specializationscope;
static size_t nspecializationscope;
static Htab *seqbase;
-/* type params bound at the current point */
-static Htab **tybindings;
-static size_t ntybindings;
-
static void
ctxstrcall(char *buf, size_t sz, Node *n)
{
@@ -290,8 +282,21 @@ typeerror(Type *a, Type *b, Node *ctx, char *msg)
free(c);
}
-/* Set a scope's enclosing scope up correctly.
- * We don't do this in the parser for some reason. */
+/* Set a scope's enclosing scope up correctly. */
+static void
+setsuperenv(Tyenv *e, Tyenv *super)
+{
+ Tyenv *te;
+
+ /* verify that we don't accidentally create loops */
+ if (!e)
+ return;
+ for (te = super; te; te = te->super)
+ assert(te->super != e);
+ e->super = super;
+}
+
+/* Set a scope's enclosing scope up correctly. */
static void
setsuper(Stab *st, Stab *super)
{
@@ -303,19 +308,6 @@ setsuper(Stab *st, Stab *super)
st->super = super;
}
-/* If the current environment binds a type,
- * we return true */
-static int
-isbound(Type *t)
-{
- ssize_t i;
-
- for (i = ntybindings - 1; i >= 0; i--) {
- if (htget(tybindings[i], t->pname))
- return 1;
- }
- return 0;
-}
/* Checks if a type that directly contains itself.
* Recursive types that contain themselves through
@@ -430,23 +422,21 @@ needfreshen(Type *t)
/* Freshens the type of a declaration. */
static Type *
-tyfreshen(Tysubst *subst, Type *t)
+tyfreshen(Tysubst *subst, Type *orig)
{
- if (!needfreshen(t)) {
- if (debugopt['u'])
- indentf(indentdepth, "%s isn't generic: skipping freshen\n", tystr(t));
- return t;
- }
+ Type *t;
- tybind(t);
+ if (!needfreshen(orig))
+ return orig;
+ pushenv(orig->env);
if (!subst) {
subst = mksubst();
- t = tyspecialize(t, subst, delayed, seqbase);
+ t = tyspecialize(orig, subst, delayed, seqbase);
substfree(subst);
} else {
- t = tyspecialize(t, subst, delayed, seqbase);
+ t = tyspecialize(orig, subst, delayed, seqbase);
}
- tyunbind();
+ popenv(orig->env);
return t;
}
@@ -466,6 +456,7 @@ tyresolve(Type *t)
ingeneric++;
t->resolved = 1;
/* Walk through aggregate type members */
+ pushenv(t->env);
switch (t->type) {
case Tystruct:
inaggr++;
@@ -494,11 +485,6 @@ tyresolve(Type *t)
if (!isbound(t))
lfatal(t->loc, "type parameter %s is undefined in generic context", tystr(t));
break;
- case Tyname:
- case Tygeneric:
- /* FIXME: this should not include the current type scope in the search. */
- tybind(t);
- break;
default:
break;
}
@@ -513,8 +499,7 @@ tyresolve(Type *t)
t->traits = bsdup(base->traits);
if (occurs(t))
lfatal(t->loc, "type %s includes itself", tystr(t));
- if (t->type == Tygeneric || t->type == Tyname)
- tyunbind();
+ popenv(t->env);
ingeneric--;
}
@@ -533,7 +518,7 @@ remapping(Type *t)
{
Stab *ns;
Type *lu;
- int i;
+ Tyenv *e;
switch (t->type) {
case Tyunres:
@@ -548,8 +533,8 @@ remapping(Type *t)
fatal(t->name, "could not resolve type %s", tystr(t));
return lu;
case Typaram:
- for (i = ntybindings - 1; i >= 0; i--) {
- lu = htget(tybindings[i], t->pname);
+ for (e = curenv(); e; e = e->super) {
+ lu = htget(e->tab, t);
if (lu)
return lu;
}
@@ -628,9 +613,9 @@ tf(Type *orig)
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);
}
- tybind(t);
+ pushenv(orig->env);
t = tysubst(t, orig);
- tyunbind();
+ popenv(orig->env);
}
ingeneric -= isgeneric;
return t;
@@ -737,127 +722,18 @@ uconresolve(Node *n)
return uc;
}
-static void
-putbindingsrec(Htab *bt, Type *t, Bitset *visited)
-{
- size_t i;
-
- t = tysearch(t);
- if (bshas(visited, t->tid))
- return;
- bsput(visited, t->tid);
- switch (t->type) {
- case Typaram:
- if (hthas(bt, t->pname))
- unify(NULL, htget(bt, t->pname), t);
- else if (!isbound(t))
- htput(bt, t->pname, t);
- break;
- case Tygeneric:
- for (i = 0; i < t->ngparam; i++)
- putbindingsrec(bt, t->gparam[i], visited);
- break;
- case Tyname:
- for (i = 0; i < t->narg; i++)
- putbindingsrec(bt, t->arg[i], visited);
- break;
- case Tyunres:
- for (i = 0; i < t->narg; i++)
- putbindingsrec(bt, t->arg[i], visited);
- break;
- case Tystruct:
- for (i = 0; i < t->nmemb; i++)
- putbindingsrec(bt, t->sdecls[i]->decl.type, visited);
- break;
- case Tyunion:
- for (i = 0; i < t->nmemb; i++)
- if (t->udecls[i]->etype)
- putbindingsrec(bt, t->udecls[i]->etype, visited);
- break;
- default:
- for (i = 0; i < t->nsub; i++)
- putbindingsrec(bt, t->sub[i], visited);
- break;
- }
-}
-
-/* Binds the type parameters present in the
- * current type into the type environment */
-static void
-putbindings(Htab *bt, Type *t)
-{
- Bitset *visited;
-
- if (!t)
- return;
- visited = mkbs();
- putbindingsrec(bt, t, visited);
- bsfree(visited);
-}
-
-static void
-tybindall(Type *t)
-{
- Htab *bt;
-
- bt = mkht(strhash, streq);
- lappend(&tybindings, &ntybindings, bt);
- putbindings(bt, t);
-}
-
-static void
-tybind(Type *t)
-{
- Htab *bt;
- size_t i;
-
- bt = mkht(strhash, streq);
- lappend(&tybindings, &ntybindings, bt);
- if (t->type == Tygeneric)
- for (i = 0; i < t->ngparam; i++)
- putbindings(bt, t->gparam[i]);
- else if (t->type == Tyname)
- for (i = 0; i < t->narg; i++)
- putbindings(bt, t->arg[i]);
-}
-
/* Binds the type parameters in the
* declaration into the type environment */
-static void
-bind(Node *n)
+void
+_bind(Tyenv *e, Node *n)
{
- Htab *bt;
-
assert(n->type == Ndecl);
-
if(!n->decl.isgeneric)
return;
ingeneric++;
- bt = mkht(strhash, streq);
- lappend(&tybindings, &ntybindings, bt);
-
- putbindings(bt, n->decl.type);
+ bindtype(e, n->decl.type);
if (n->decl.init)
- putbindings(bt, n->decl.init->expr.type);
-}
-
-/* Rolls back the binding of type parameters in
- * the type environment */
-static void
-unbind(Node *n)
-{
- if(!n->decl.isgeneric)
- return;
- htfree(tybindings[ntybindings - 1]);
- lpop(&tybindings, &ntybindings);
- ingeneric--;
-}
-
-static void
-tyunbind()
-{
- htfree(tybindings[ntybindings - 1]);
- lpop(&tybindings, &ntybindings);
+ bindtype(e, n->decl.init->expr.type);
}
/* Constrains a type to implement the required constraints. On
@@ -1272,16 +1148,16 @@ initvar(Node *n, Node *s)
param = n->expr.param;
if (s->decl.isgeneric) {
subst = mksubst();
- tybindall(s->decl.type);
if (param)
substput(subst, s->decl.trait->param, param);
+ pushenv(s->decl.env);
t = tysubstmap(subst, tf(s->decl.type), s->decl.type);
+ popenv(s->decl.env);
if (s->decl.trait && !param) {
param = substget(subst, s->decl.trait->param);
if (!param)
fatal(n, "ambiguous trait decl %s", ctxstr(s));
}
- tyunbind();
substfree(subst);
} else {
t = s->decl.type;
@@ -1444,7 +1320,7 @@ inferucon(Node *n, int *isconst)
*
* To make it compile, for now, we just bind the types in here.
*/
- tybindall(uc->utype);
+ //tybindall(uc->utype);
t = tysubst(tf(uc->utype), uc->utype);
uc = tybase(t)->udecls[uc->id];
if (uc->etype) {
@@ -1453,7 +1329,7 @@ inferucon(Node *n, int *isconst)
*isconst = n->expr.args[1]->expr.isconst;
}
settype(n, delayeducon(t));
- tyunbind();
+ //tyunbind();
}
static void
@@ -1770,9 +1646,9 @@ inferexpr(Node **np, Type *ret, int *sawret)
infersub(n, ret, sawret, &isconst);
switch (args[0]->lit.littype) {
case Lfunc:
- tybindall(args[0]->lit.fnval->func.type);
+ //tybindall(args[0]->lit.fnval->func.type);
infernode(&args[0]->lit.fnval, NULL, NULL);
- tyunbind();
+ //tyunbind();
/* FIXME: env capture means this is non-const */
n->expr.isconst = 1;
@@ -1873,6 +1749,7 @@ specializeimpl(Node *n)
fatal(n, "%s incompatibly specialized with %zd types instead of %zd types",
namestr(n->impl.traitname), n->impl.naux, t->naux);
n->impl.type = tf(n->impl.type);
+ pushenv(n->impl.type->env);
for (i = 0; i < n->impl.naux; i++)
n->impl.aux[i] = tf(n->impl.aux[i]);
for (i = 0; i < n->impl.ndecls; i++) {
@@ -1934,6 +1811,7 @@ specializeimpl(Node *n)
dcl->decl.vis = t->vis;
lappend(&impldecl, &nimpldecl, dcl);
}
+ popenv(n->impl.type->env);
}
static void
@@ -1962,13 +1840,16 @@ inferstab(Stab *s)
size_t n, i;
Node *dcl;
Type *t;
+ void *se;
k = htkeys(s->dcl, &n);
+ se = curenv();
for (i = 0; i < n; i++) {
dcl = htget(s->dcl, k[i]);
- bind(dcl);
+ pushenv(dcl->decl.env);
tf(type(dcl));
- unbind(dcl);
+ popenv(dcl->decl.env);
+ assert(se == curenv());
}
free(k);
@@ -1978,9 +1859,11 @@ inferstab(Stab *s)
if (!t)
fatal(k[i], "undefined type %s", namestr(k[i]));
t = tysearch(t);
- tybind(t);
+ if (t->env)
+ setsuperenv(t->env, curenv());
+ pushenv(t->env);
tyresolve(t);
- tyunbind();
+ popenv(t->env);
updatetype(s, k[i], t);
}
free(k);
@@ -2010,16 +1893,21 @@ infernode(Node **np, Type *ret, int *sawret)
case Ndecl:
if (debugopt['u'])
indentf(indentdepth, "--- infer %s ---\n", declname(n));
+ if (n->decl.isgeneric)
+ ingeneric++;
indentdepth++;
- bind(n);
+ setsuperenv(n->decl.env, curenv());
+ pushenv(n->decl.env);
inferdecl(n);
if (type(n)->type == Typaram && !ingeneric)
fatal(n, "generic type %s in non-generic near %s", tystr(type(n)),
ctxstr(n));
- unbind(n);
+ popenv(n->decl.env);
indentdepth--;
if (debugopt['u'])
indentf(indentdepth, "--- done ---\n");
+ if (n->decl.isgeneric)
+ ingeneric--;
break;
case Nblock:
setsuper(n->block.scope, curstab());
@@ -2083,13 +1971,12 @@ infernode(Node **np, Type *ret, int *sawret)
break;
case Nfunc:
setsuper(n->func.scope, curstab());
- if (ntybindings > 0)
- for (i = 0; i < n->func.nargs; i++)
- putbindings(tybindings[ntybindings - 1],
- n->func.args[i]->decl.type);
pushstab(n->func.scope);
+ setsuperenv(n->func.env, curenv());
+ pushenv(n->func.env);
inferstab(n->func.scope);
inferfunc(n);
+ popenv(n->func.env);
popstab();
break;
case Nimpl:
@@ -2378,9 +2265,9 @@ stabsub(Stab *s)
k = htkeys(s->dcl, &n);
for (i = 0; i < n; i++) {
d = getdcl(s, k[i]);
- bind(d);
+ pushenv(d->decl.env);
d->decl.type = tyfix(d, d->decl.type, 0);
- unbind(d);
+ popenv(d->decl.env);
if (!d->decl.isconst && !d->decl.isgeneric)
continue;
if (d->decl.trait)
@@ -2499,7 +2386,7 @@ typesub(Node *n, int noerr)
popstab();
break;
case Ndecl:
- bind(n);
+ pushenv(n->decl.env);
settype(n, tyfix(n, type(n), noerr));
if (n->decl.init)
typesub(n->decl.init, noerr);
@@ -2510,7 +2397,7 @@ typesub(Node *n, int noerr)
if (streq(declname(n), "__init__"))
if (!initcompatible(tybase(decltype(n))))
fatal(n, "__init__ must be (->void), got %s", tystr(decltype(n)));
- unbind(n);
+ popenv(n->decl.env);
break;
case Nblock:
pushstab(n->block.scope);
@@ -2650,7 +2537,7 @@ specialize(Node *f)
static void
applytraits(Node *f)
{
- size_t i, j;
+ size_t i;
Node *impl, *n;
Trait *tr;
Type *ty;
@@ -2676,17 +2563,13 @@ applytraits(Node *f)
fatal(impl, "incompatible implementation of %s: mismatched aux types",
namestr(impl->impl.traitname), ctxstr(impl));
}
- tybindall(impl->impl.type);
- for (j = 0; j < impl->impl.naux; j++)
- tybindall(impl->impl.aux[j]);
+ pushenv(impl->impl.env);
ty = tf(impl->impl.type);
settrait(ty, tr);
if (tr->uid == Tciter) {
htput(seqbase, tf(impl->impl.type), tf(impl->impl.aux[0]));
}
- tyunbind();
- for (j = 0; j < impl->impl.naux; j++)
- tyunbind();
+ popenv(impl->impl.env);
}
popstab();
}
@@ -2726,7 +2609,6 @@ infer(Node *file)
postinfer();
/* and replace type vars with actual types */
- assert(ntybindings == 0);
typesub(file, 0);
specialize(file);
verify(file);
diff --git a/parse/node.c b/parse/node.c
index d6b2724..34fdd74 100644
--- a/parse/node.c
+++ b/parse/node.c
@@ -216,11 +216,17 @@ mkfunc(Srcloc loc, Node **args, size_t nargs, Type *ret, Node *body)
f->func.body = body;
f->func.scope = mkstab(1);
f->func.type = mktyfunc(loc, args, nargs, ret);
+ f->func.env = mkenv();
st = body->block.scope;
for (i = 0; i < nargs; i++)
putdcl(st, args[i]);
+ bindtype(f->func.env, ret);
+ for (i = 0; i < nargs; i++)
+ bindtype(f->func.env, decltype(args[i]));
+
+
n = mknode(loc, Nlit);
n->lit.littype = Lfunc;
n->lit.fnval = f;
@@ -250,6 +256,10 @@ mkimplstmt(Srcloc loc, Node *name, Type *t, Type **aux, size_t naux, Node **decl
n->impl.decls = decls;
n->impl.ndecls = ndecls;
lappend(&impltab, &nimpltab, n);
+ if (hasparams(t)) {
+ n->impl.env = mkenv();
+ bindtype(n->impl.env, t);
+ }
return n;
}
@@ -382,6 +392,11 @@ mkdecl(Srcloc loc, Node *name, Type *ty)
n->decl.name = name;
n->decl.type = ty;
lappend(&decls, &ndecls, n);
+ if (ty && hasparams(ty)) {
+ n->decl.env = mkenv();
+ bindtype(n->decl.env, ty);
+ }
+
return n;
}
diff --git a/parse/parse.h b/parse/parse.h
index 1b70c18..07ec44a 100644
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -101,6 +101,11 @@ struct Stab {
Htab *impl; /* trait implementations: really a set of implemented traits. */
};
+struct Tyenv {
+ Tyenv *super;
+ Htab *tab;
+};
+
struct Type {
Ty type;
int tid;
@@ -116,6 +121,7 @@ struct Type {
Type **inst; /* Tyname: instances created */
size_t ninst; /* Tyname: count of instances created */
+ Tyenv *env; /* the environment for bound types, may be null */
Type **sub; /* sub-types; shared by all composite types */
size_t nsub; /* For compound types */
size_t nmemb; /* for aggregate types (struct, union) */
@@ -272,6 +278,7 @@ struct Node {
Node *name;
Type *type;
Node *init;
+ Tyenv *env; /* bound types */
/*
If we have a link to a trait, we should only look it up
@@ -301,6 +308,7 @@ struct Node {
} decl;
struct {
+ Tyenv *env;
Stab *scope;
Type *type;
size_t nargs;
@@ -313,6 +321,7 @@ struct Node {
Trait *trait;
Type *type;
Type **aux;
+ Tyenv *env;
size_t naux;
Node **decls;
size_t ndecls;
@@ -402,6 +411,15 @@ Stab *curstab(void);
void pushstab(Stab *st);
void popstab(void);
+void bindtype(Tyenv *env, Type *t);
+int isbound(Type *t);
+Tyenv *mkenv(void);
+Tyenv *curenv(void);
+void pushenv(Tyenv *e);
+void popenv(Tyenv *e);
+void _tybind(Tyenv *e, Type *t);
+void _bind(Tyenv *e, Node *n);
+
/* type creation */
void tyinit(Stab *st); /* sets up built in types */
diff --git a/parse/specialize.c b/parse/specialize.c
index 0fa1a0d..81eeefa 100644
--- a/parse/specialize.c
+++ b/parse/specialize.c
@@ -625,7 +625,7 @@ specializedcl(Node *gnode, Type *param, Type *to, Node **name)
g = gnode;
}
if (debugopt['S'])
- printf("depth[%d] specializing [%d]%s => %s\n", stabstkoff, g->loc.line,
+ printf("specializing [%d]%s => %s\n", g->loc.line,
namestr(g->decl.name), namestr(n));
/* namespaced names need to be looked up in their correct
* context. */
diff --git a/parse/stab.c b/parse/stab.c
index cf622b3..757dceb 100644
--- a/parse/stab.c
+++ b/parse/stab.c
@@ -30,29 +30,11 @@ struct Traitdefn {
#define Maxstabdepth 128
static Stab *stabstk[Maxstabdepth];
-int stabstkoff;
+static size_t stabstkoff;
-/* scope management */
-Stab *
-curstab()
-{
- assert(stabstkoff > 0);
- return stabstk[stabstkoff - 1];
-}
-
-void
-pushstab(Stab *st)
-{
- assert(stabstkoff < Maxstabdepth);
- stabstk[stabstkoff++] = st;
-}
+static Tyenv *envstk[Maxstabdepth];
+static size_t envstkoff;
-void
-popstab(void)
-{
- assert(stabstkoff > 0);
- stabstkoff--;
-}
/* name hashing: we want namespaced lookups to find the
* name even if we haven't set the namespace up, since
@@ -81,22 +63,6 @@ implhash(void *p)
return h;
}
-Stab *
-findstab(Stab *st, Node *n)
-{
- Stab *ns;
-
- if (n->name.ns) {
- ns = getns(file, n->name.ns);
- if (!ns) {
- ns = mkstab(0);
- updatens(ns, n->name.ns);
- }
- st = ns;
- }
- return st;
-}
-
static int
impleq(void *pa, void *pb)
{
@@ -128,6 +94,81 @@ mkstab(int isfunc)
return st;
}
+Stab *
+curstab()
+{
+ assert(stabstkoff > 0);
+ return stabstk[stabstkoff - 1];
+}
+
+void
+pushstab(Stab *st)
+{
+ assert(stabstkoff < Maxstabdepth);
+ stabstk[stabstkoff++] = st;
+}
+
+void
+popstab()
+{
+ assert(stabstkoff > 0);
+ stabstkoff--;
+}
+
+Tyenv*
+mkenv()
+{
+ Tyenv *e;
+
+ e = malloc(sizeof(Tyenv));
+ e->super = NULL;
+ e->tab = mkht(strhash, streq);
+ return e;
+}
+
+Tyenv*
+curenv()
+{
+ if (!envstkoff)
+ return NULL;
+ else
+ return envstk[envstkoff - 1];
+}
+
+void
+pushenv(Tyenv *env)
+{
+ if (!env)
+ return;
+ assert(envstkoff < Maxstabdepth);
+ envstk[envstkoff++] = env;
+}
+
+void
+popenv(Tyenv *env)
+{
+ if (!env)
+ return;
+ assert(envstkoff > 0);
+ envstkoff--;
+}
+
+Stab *
+findstab(Stab *st, Node *n)
+{
+ Stab *ns;
+
+ if (n->name.ns) {
+ ns = getns(file, n->name.ns);
+ if (!ns) {
+ ns = mkstab(0);
+ updatens(ns, n->name.ns);
+ }
+ st = ns;
+ }
+ return st;
+}
+
Node *
getclosed(Stab *st, Node *n)
{
@@ -329,6 +370,14 @@ mergedecl(Node *old, Node *new)
e->decl.init = g->decl.init;
else if (!g->decl.init)
g->decl.init = e->decl.init;
+ if (old->decl.env || e->decl.env) {
+ if (!old->decl.env)
+ old->decl.env = e->decl.env;
+ if (!e->decl.env)
+ e->decl.env = old->decl.env;
+ bindtype(e->decl.env, old->decl.type);
+ bindtype(old->decl.env, e->decl.type);
+ }
/* FIXME: check compatible typing */
old->decl.ishidden = e->decl.ishidden || g->decl.ishidden;
@@ -576,3 +625,76 @@ updatens(Stab *st, char *name)
setns(k[i], name);
free(k);
}
+
+static void
+bindtype_rec(Tyenv *e, Type *t, Bitset *visited)
+{
+ size_t i;
+ Type *tt;
+
+ t = tysearch(t);
+ if (bshas(visited, t->tid))
+ return;
+ bsput(visited, t->tid);
+ switch (t->type) {
+ case Typaram:
+ tt = htget(e->tab, t->pname);
+ if (tt && tt != t)
+ tytab[t->tid] = tt;
+ else if (!isbound(t))
+ htput(e->tab, t->pname, t);
+ break;
+ case Tygeneric:
+ for (i = 0; i < t->ngparam; i++)
+ bindtype_rec(e, t->gparam[i], visited);
+ break;
+ case Tyname:
+ for (i = 0; i < t->narg; i++)
+ bindtype_rec(e, t->arg[i], visited);
+ break;
+ case Tyunres:
+ for (i = 0; i < t->narg; i++)
+ bindtype_rec(e, t->arg[i], visited);
+ break;
+ case Tystruct:
+ for (i = 0; i < t->nmemb; i++)
+ bindtype_rec(e, t->sdecls[i]->decl.type, visited);
+ break;
+ case Tyunion:
+ for (i = 0; i < t->nmemb; i++)
+ if (t->udecls[i]->etype)
+ bindtype_rec(e, t->udecls[i]->etype, visited);
+ break;
+ default:
+ for (i = 0; i < t->nsub; i++)
+ bindtype_rec(e, t->sub[i], visited);
+ break;
+ }
+}
+
+/* Binds the type parameters present in the
+ * current type into the type environment */
+void
+bindtype(Tyenv *env, Type *t)
+{
+ Bitset *visited;
+
+ if (!t)
+ return;
+ visited = mkbs();
+ bindtype_rec(env, t, visited);
+ bsfree(visited);
+}
+
+/* If the current environment binds a type,
+ * we return true */
+int
+isbound(Type *t)
+{
+
+ Tyenv *e;
+ for (e = curenv(); e; e = e->super)
+ if (htget(e->tab, t->pname))
+ return 1;
+ return 0;
+}
diff --git a/parse/type.c b/parse/type.c
index 62fa34f..82b45ba 100644
--- a/parse/type.c
+++ b/parse/type.c
@@ -194,6 +194,7 @@ mktyparam(Srcloc loc, char *name)
Type *
mktyunres(Srcloc loc, Node *name, Type **arg, size_t narg)
{
+ size_t i;
Type *t;
/* resolve it in the type inference stage */
@@ -201,6 +202,9 @@ mktyunres(Srcloc loc, Node *name, Type **arg, size_t narg)
t->name = name;
t->arg = arg;
t->narg = narg;
+ t->env = mkenv();
+ for (i = 0; i < narg; i++)
+ bindtype(t->env, arg[i]);
return t;
}
@@ -208,6 +212,7 @@ Type *
mktygeneric(Srcloc loc, Node *name, Type **param, size_t nparam, Type *base)
{
Type *t;
+ int i;
t = mktype(loc, Tygeneric);
t->name = name;
@@ -217,6 +222,13 @@ mktygeneric(Srcloc loc, Node *name, Type **param, size_t nparam, Type *base)
t->sub[0] = base;
t->gparam = param;
t->ngparam = nparam;
+ t->env = mkenv();
+ for (i = 0; i < nparam; i++)
+ bindtype(t->env, param[i]);
+ if (!base->env)
+ base->env = t->env;
+ else
+ assert(base->env->super == t->env);
return t;
}
@@ -297,8 +309,11 @@ mktyfunc(Srcloc loc, Node **args, size_t nargs, Type *ret)
t->nsub = nargs + 1;
t->sub = xalloc((1 + nargs) * sizeof(Type *));
t->sub[0] = ret;
+ t->env = mkenv();
for (i = 0; i < nargs; i++)
t->sub[i + 1] = nodetype(args[i]);
+ for (i = 0; i < t->nsub; i++)
+ bindtype(t->env, t->sub[i]);
return t;
}
@@ -732,10 +747,10 @@ tyhash(void *ty)
t = (Type *)ty;
switch (t->type) {
case Tyvar: hash = inthash(t->tid); break;
- case Typaram: hash = strhash(t->pname); break;
case Tyunion: hash = inthash(t->type); break;
case Tystruct: hash = inthash(t->type); break;
case Tyname: hash = namehash(t->name); break;
+ case Typaram: hash = strhash(t->pname); break;
default: hash = inthash(t->type); break;
}
diff --git a/parse/use.c b/parse/use.c
index d194576..629b52b 100644
--- a/parse/use.c
+++ b/parse/use.c
@@ -682,7 +682,7 @@ unpickle(FILE *fd)
n->block.nstmts = rdint(fd);
n->block.stmts = zalloc(sizeof(Node *) * n->block.nstmts);
n->block.scope->super = curstab();
- pushstab(n->func.scope->super);
+ pushstab(n->block.scope->super);
for (i = 0; i < n->block.nstmts; i++)
n->block.stmts[i] = unpickle(fd);
popstab();
@@ -779,8 +779,8 @@ fixtypemappings(Stab *st)
/*
* merge duplicate definitions.
* This allows us to compare named types by id, instead
- * of doing a deep walk through the type. This ability i
- * depended on when we do type inference.
+ * of doing a deep walk through the type. This ability I
+ * depend on when we do type inference.
*/
for (i = 0; i < ntypefix; i++) {
t = htget(tidmap, itop(typefix[i].id));
@@ -788,6 +788,7 @@ fixtypemappings(Stab *st)
die("Unable to find type for id %zd\n", typefix[i].id);
*typefix[i].dest = t;
}
+
for (i = 0; i < ntypefix; i++) {
old = *typefix[i].dest;
if (old->type == Tyname || old->type == Tygeneric) {
@@ -907,17 +908,20 @@ fiximplmappings(Stab *st)
int
loaduse(char *path, FILE *f, Stab *st, Vis vis)
{
- intptr_t tid;
- size_t i;
- int v;
- char *pkg;
+ size_t startdecl, starttype, startimpl;
Node *dcl, *impl, *init;
Stab *s, *ns;
+ intptr_t tid;
+ size_t i, j;
+ char *pkg;
Type *ty;
Trait *tr;
char *lib;
- int c;
+ int c, v;
+ startdecl = ndecls;
+ starttype = ntypes;
+ startimpl = nimpltab;
pushstab(file->file.globls);
if (!tydeduptab)
tydeduptab = mkht(tyhash, tyeq);
@@ -969,8 +973,7 @@ loaduse(char *path, FILE *f, Stab *st, Vis vis)
/* break out of both loop and switch */
goto foundlib;
lappend(&file->file.libdeps, &file->file.nlibdeps, lib);
-foundlib
-:
+foundlib:
break;
case 'X':
lib = rdstr(f);
@@ -979,8 +982,7 @@ foundlib
/* break out of both loop and switch */
goto foundextlib;
lappend(&file->file.extlibs, &file->file.nextlibs, lib);
-foundextlib
-:
+foundextlib:
break;
case 'F': lappend(&file->file.files, &file->file.nfiles, rdstr(f)); break;
case 'G':
@@ -1050,6 +1052,36 @@ foundextlib
fixtraitmappings(s);
fiximplmappings(s);
htfree(tidmap);
+ for (i = starttype; i < ntypes; i++) {
+ ty = types[i];
+ if (ty->type == Tygeneric || ty->type == Tyname) {
+ if (hasparams(ty) && !ty->env) {
+ ty->env = mkenv();
+ for (j = 0; j < ty->ngparam; j++)
+ bindtype(ty->env, ty->gparam[j]);
+ for (j = 0; j < ty->narg; j++)
+ bindtype(ty->env, ty->arg[j]);
+ }
+ if (ty->sub[0]->env)
+ ty->sub[0]->env->super = ty->env;
+ else
+ ty->sub[0]->env = ty->env;
+ }
+ }
+ for (i = startdecl; i < ndecls; i++) {
+ dcl = decls[i];
+ if (hasparams(dcl->decl.type)) {
+ dcl->decl.env = mkenv();
+ bindtype(dcl->decl.env, dcl->decl.type);
+ }
+ }
+ for (i = startimpl; i < nimpltab; i++) {
+ impl = impltab[i];
+ if (!impl->impl.env) {
+ impl->impl.env = mkenv();
+ bindtype(impl->impl.env, impl->impl.type);
+ }
+ }
popstab();
return 1;
}
diff --git a/util/bitset.c b/util/bitset.c
index 6aa9344..6109f9e 100644
--- a/util/bitset.c
+++ b/util/bitset.c
@@ -225,6 +225,15 @@ bsintersect(Bitset *a, Bitset *b)
a->chunks[i] &= b->chunks[i];
}
+ulong
+bshash(Bitset *bs)
+{
+ if (!bs)
+ return 14247517;
+ else
+ return murmurhash2(bs->chunks, bs->nchunks * sizeof(size_t));
+}
+
void
bsdiff(Bitset *a, Bitset *b)
{
diff --git a/util/htab.c b/util/htab.c
index 8894579..7ba6291 100644
--- a/util/htab.c
+++ b/util/htab.c
@@ -11,8 +11,6 @@
#define Initsz 16
#define Seed 2928213749
-static ulong murmurhash2(void *key, size_t len);
-
/* Creates a new empty hash table, using 'hash' as the
* hash funciton, and 'cmp' to verify that there are no
* hash collisions. */
@@ -294,7 +292,7 @@ ptreq(void *a, void *b)
return a == b;
}
-static ulong
+ulong
murmurhash2 (void *ptr, size_t len)
{
uint32_t m = 0x5bd1e995;
diff --git a/util/util.h b/util/util.h
index 49f10d6..be09dfc 100644
--- a/util/util.h
+++ b/util/util.h
@@ -67,6 +67,7 @@ void sbputs(Strbuf *sb, char *s);
void sbputb(Strbuf *sb, char b);
/* bit sets */
+ulong bshash(Bitset *bs);
Bitset *mkbs(void);
void bsfree(Bitset *bs);
Bitset *bsdup(Bitset *bs);
@@ -113,6 +114,7 @@ ulong ptrhash(void *key);
int ptreq(void *a, void *b);
ulong inthash(uint64_t key);
int inteq(uint64_t a, uint64_t b);
+ulong murmurhash2(void *buf, size_t sz);
/* util functions */
void *zalloc(size_t size);