shithub: mc

Info  •  Files  •  Log  •  Branches

Type binding refactoring now compiles.

	Still a bit sloppy on a few things, needs some dedup work,
	but it's working.

--- a/lib/std/endian.myr

+++ b/lib/std/endian.myr

@@ -10,7 +10,7 @@

 	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 @@

 	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

--- a/lib/std/fmt.myr

+++ b/lib/std/fmt.myr

@@ -594,7 +594,7 @@

 		;;

 	else

 		val = (bits : uint64)

-		val &= ~0 >> (8*(sizeof(uint64)-sizeof(@a)))

+		val &= ~0 >> (8*(sizeof(uint64)-sizeof(@a::(integral,numeric))))

 		isneg = false

 	;;

--- a/lib/std/intparse.myr

+++ b/lib/std/intparse.myr

@@ -47,7 +47,7 @@

 	-> doparse(s, isneg, base)

 }

-generic doparse = {s, isneg, base

+generic doparse = {s, isneg, base ->  option(@a::(integral,numeric))

 	var v

 	var cv : int32

--- 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#)

 ;;

--- a/parse/dump.c

+++ b/parse/dump.c

@@ -103,10 +103,36 @@

 	}

 }

+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)

 {

 	outstab(st, fd, 0);

+}

+

+void

+dumpenv(Tyenv *e, FILE *fd)

+{

+	outenv(e, fd, 0);

 }

 void

--- a/parse/gram.y

+++ b/parse/gram.y

@@ -477,7 +477,9 @@

 		$$.types = NULL; $$.ntypes = 0;

 		lappend(&$$.types, &$$.ntypes, $1);

 	}

-	| typarams Tcomma generictype {lappend(&$$.types, &$$.ntypes, $3);}

+	| typarams Tcomma generictype {

+		lappend(&$$.types, &$$.ntypes, $3);

+	}

 	;

 type    : structdef

--- a/parse/infer.c

+++ b/parse/infer.c

@@ -20,10 +20,6 @@

 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 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,9 +282,22 @@

 	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)

 {

 	Stab *s;

@@ -303,20 +308,7 @@

 	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

  * pointers or slices are fine, but any other self-inclusion

@@ -430,23 +422,21 @@

 /* 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 @@

 	ingeneric++;

 	t->resolved = 1;

 	/* Walk through aggregate type members */

+	pushenv(t->env);

 	switch (t->type) {

 	case Tystruct:

 		inaggr++;

@@ -494,11 +485,6 @@

 		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 @@

 		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 @@

 {

 	Stab *ns;

 	Type *lu;

-	int i;

+	Tyenv *e;

 	switch (t->type) {

 	case Tyunres:

@@ -548,8 +533,8 @@

 			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 @@

 			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,129 +722,20 @@

 	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);

+		bindtype(e, 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);

-}

-

 /* 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

@@ -1272,16 +1148,16 @@

 	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 @@

 	 *

 	 * 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 @@

 		*isconst = n->expr.args[1]->expr.isconst;

 	}

 	settype(n, delayeducon(t));

-	tyunbind();

+	//tyunbind();

 }

 static void

@@ -1770,9 +1646,9 @@

 		   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 @@

 		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 @@

 		dcl->decl.vis = t->vis;

 		lappend(&impldecl, &nimpldecl, dcl);

 	}

+	popenv(n->impl.type->env);

 }

 static void

@@ -1962,13 +1840,16 @@

 	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 @@

 		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 @@

 	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 @@

 		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 @@

 	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 @@

 		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 @@

 		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 @@

 static void

 applytraits(Node *f)

 {

-	size_t i, j;

+	size_t i;

 	Node *impl, *n;

 	Trait *tr;

 	Type *ty;

@@ -2676,17 +2563,13 @@

 				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 @@

 	postinfer();

 	/* and replace type vars with actual types */

-	assert(ntybindings == 0);

 	typesub(file, 0);

 	specialize(file);

 	verify(file);

--- a/parse/node.c

+++ b/parse/node.c

@@ -216,11 +216,17 @@

 	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 @@

 	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 @@

 	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;

 }

--- a/parse/parse.h

+++ b/parse/parse.h

@@ -101,6 +101,11 @@

 	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 @@

 	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 @@

 			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 @@

 		} decl;

 		struct {

+			Tyenv *env;

 			Stab *scope;

 			Type *type;

 			size_t nargs;

@@ -313,6 +321,7 @@

 			Trait *trait;

 			Type *type;

 			Type **aux;

+			Tyenv *env;

 			size_t naux;

 			Node **decls;

 			size_t ndecls;

@@ -401,6 +410,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 */

--- a/parse/specialize.c

+++ b/parse/specialize.c

@@ -625,7 +625,7 @@

 		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. */

--- a/parse/stab.c

+++ b/parse/stab.c

@@ -30,30 +30,12 @@

 #define Maxstabdepth 128

 static Stab *stabstk[Maxstabdepth];

-int stabstkoff;

+static size_t stabstkoff;

-/* scope management */

-Stab *

-curstab()

-{

-	assert(stabstkoff > 0);

-	return stabstk[stabstkoff - 1];

-}

+static Tyenv *envstk[Maxstabdepth];

+static size_t envstkoff;

-void

-pushstab(Stab *st)

-{

-	assert(stabstkoff < Maxstabdepth);

-	stabstk[stabstkoff++] = st;

-}

-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

  * we can update it after the fact. */

@@ -81,22 +63,6 @@

 	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 @@

 	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 @@

 		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;

@@ -575,4 +624,77 @@

 	for (i = 0; i < nk; i++)

 		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;

 }

--- a/parse/type.c

+++ b/parse/type.c

@@ -194,6 +194,7 @@

 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 @@

 	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 @@

 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 @@

 	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 @@

 	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 @@

 	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;

 	}

--- a/parse/use.c

+++ b/parse/use.c

@@ -682,7 +682,7 @@

 		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 @@

 	/*

 	* 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 @@

 			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 @@

 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 @@

 					/* 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 @@

 					/* 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 @@

 	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;

 }

--- a/util/bitset.c

+++ b/util/bitset.c

@@ -225,6 +225,15 @@

 		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)

 {

--- 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 @@

 	return a == b;

 }

-static ulong

+ulong

 murmurhash2 (void *ptr, size_t len)

 {

 	uint32_t m = 0x5bd1e995;

--- a/util/util.h

+++ b/util/util.h

@@ -67,6 +67,7 @@

 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 @@

 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);