shithub: mc

--- a/parse/infer.c

+++ b/parse/infer.c

@@ -344,7 +344,7 @@

 /* Freshens the type of a declaration. */

-static Type *tyfreshen(Inferstate *st, Htab *subst, Type *t)

+static Type *tyfreshen(Inferstate *st, Tysubst *subst, Type *t)

 	char *from, *to;

@@ -357,9 +357,9 @@

 	from = tystr(t);

 	tybind(st, t);

 	if (!subst) {

-		subst = mkht(tyhash, tyeq);

+		subst = mksubst();

 		t = tyspecialize(t, subst, st->delayed);

-		htfree(subst);

+		substfree(subst);

 	} else {

 		t = tyspecialize(t, subst, st->delayed);

@@ -467,12 +467,12 @@

 	return t;

-static Type *tysubstmap(Inferstate *st, Htab *subst, Type *t, Type *orig)

+static Type *tysubstmap(Inferstate *st, Tysubst *subst, Type *t, Type *orig)

 	size_t i;

 	for (i = 0; i < t->ngparam; i++) {

-		htput(subst, t->gparam[i], tf(st, orig->arg[i]));

+		substput(subst, t->gparam[i], tf(st, orig->arg[i]));

 	t = tyfreshen(st, subst, t);

 	return t;

@@ -480,11 +480,11 @@

 static Type *tysubst(Inferstate *st, Type *t, Type *orig)

-	Htab *subst;

+	Tysubst *subst;

-	subst = mkht(tyhash, tyeq);

+	subst = mksubst();

 	t = tysubstmap(st, subst, t, orig);

-	htfree(subst);

+	substfree(subst);

 	return t;

@@ -1096,7 +1096,7 @@

 static Type *initvar(Inferstate *st, Node *n, Node *s)

 	Type *t, *param;

-	Htab *subst;

+	Tysubst *subst;

 	if (s->decl.ishidden)

 		fatal(n, "attempting to refer to hidden decl %s", ctxstr(st, n));

@@ -1103,13 +1103,13 @@

 	param = NULL;

 	if (s->decl.isgeneric) {

-		subst = mkht(tyhash, tyeq);

+		subst = mksubst();

 		t = tysubstmap(st, subst, tf(st, s->decl.type), s->decl.type);

 		if (s->decl.trait) {

-			param = htget(subst, s->decl.trait->param);

+			param = substget(subst, s->decl.trait->param);

 			delayedcheck(st, n, curstab());

-		htfree(subst);

+		substfree(subst);

 	} else {

 		t = s->decl.type;

@@ -1647,8 +1647,8 @@

 static void specializeimpl(Inferstate *st, Node *n)

 	Node *dcl, *proto, *name, *sym;

+	Tysubst *subst;

 	Type *ty;

-	Htab *ht;

 	Trait *t;

 	size_t i, j;

@@ -1693,12 +1693,12 @@

 			fatal(n, "trait specialization requires concrete type, got %s",

 					tystr(n->impl.type));

 		verifytraits(st, n, t->param, n->impl.type);

-		ht = mkht(tyhash, tyeq);

-		htput(ht, t->param, n->impl.type);

+		subst = mksubst();

+		substput(subst, t->param, n->impl.type);

 		for (j = 0; j < t->naux; j++)

-			htput(ht, t->aux[j], n->impl.aux[j]);

-		ty = tyspecialize(type(st, proto), ht, st->delayed);

-		htfree(ht);

+			substput(subst, t->aux[j], n->impl.aux[j]);

+		ty = tyspecialize(type(st, proto), subst, st->delayed);

+		substfree(subst);

 		inferdecl(st, dcl);

 		unify(st, n, type(st, dcl), ty);

--- a/parse/parse.h

+++ b/parse/parse.h

@@ -18,6 +18,7 @@

 typedef struct Strbuf Strbuf;

 typedef struct Htab Htab;

 typedef struct Str Str;

+typedef struct Tysubst Tysubst;

 typedef struct Tok Tok;

 typedef struct Node Node;

@@ -128,6 +129,11 @@

 	Str strval;

};

+struct Tysubst {

+	Htab **subst;

+	size_t nsubst;

+};

 struct Stab {

 	Stab *super;

 	char *name;

@@ -611,8 +617,14 @@

 Op exprop(Node *n);

 /* specialize generics */

+Tysubst *mksubst();

+void substfree();

+void substput(Tysubst *subst, Type *from, Type *to);

+Type *substget(Tysubst *subst, Type *from);

+void substpush(Tysubst *subst);

+void substpop(Tysubst *subst);

 Node *specializedcl(Node *n, Type *to, Node **name);

-Type *tyspecialize(Type *t, Htab *tymap, Htab *delayed);

+Type *tyspecialize(Type *t, Tysubst *tymap, Htab *delayed);

 Node *genericname(Node *n, Type *t);

 void geninit(Node *file);

--- a/parse/specialize.c

+++ b/parse/specialize.c

@@ -12,8 +12,58 @@

 #include "parse.h"

-static Node *specializenode(Node *g, Htab *tsmap);

+static Node *specializenode(Node *g, Tysubst *tsmap);

+Tysubst *mksubst()

+{

+	Tysubst *subst;

+	subst = zalloc(sizeof(Tysubst));

+	substpush(subst);

+	return subst;

+}

+void substfree(Tysubst *subst)

+{

+	size_t i;

+	for (i = 0; i < subst->nsubst; i++)

+		htfree(subst->subst[i]);

+	lfree(&subst->subst, &subst->nsubst);

+}

+void substpush(Tysubst *subst)

+{

+	lappend(&subst->subst, &subst->nsubst, mkht(tyhash, tyeq));

+}

+void substpop(Tysubst *subst)

+{

+	Htab *ht;

+	ht = lpop(&subst->subst, &subst->nsubst);

+	htfree(ht);

+}

+void substput(Tysubst *subst, Type *from, Type *to)

+{

+	htput(subst->subst[subst->nsubst - 1], from, to);

+}

+Type *substget(Tysubst *subst, Type *from)

+{

+	Type *t;

+	size_t i;

+	t = NULL;

+	for (i = subst->nsubst; i > 0; i--) {

+		t = htget(subst->subst[i-1], from);

+		if (t)

+			break;

+	}

+	return t;

+}

 void addtraits(Type *t, Bitset *traits)

 	size_t b;

@@ -32,14 +82,15 @@

  * parameters (type schemes in most literature)

  * replaced with type variables that we can unify

  * against */

-Type *tyspecialize(Type *orig, Htab *tsmap, Htab *delayed)

+Type *tyspecialize(Type *orig, Tysubst *tsmap, Htab *delayed)

 	Type *t, *ret, *tmp, **arg, *var;

 	size_t i, narg;

 	t = tysearch(orig);

-	if (hthas(tsmap, t))

-		return htget(tsmap, t);

+	tmp = substget(tsmap, t);

+	if (tmp)

+		return tmp;

 	arg = NULL;

 	narg = 0;

 	switch (t->type) {

@@ -46,14 +97,21 @@

 	case Typaram:

 		ret = mktyvar(t->loc);

 		addtraits(ret, t->traits);

-		htput(tsmap, t, ret);

+		substput(tsmap, t, ret);

 		break;

 	case Tygeneric:

 		var = mktyvar(t->loc);

-		htput(tsmap, t, var);

+		substput(tsmap, t, var);

+		if (orig->type == Tyunres) {

+			substpush(tsmap);

+			for (i = 0; i < orig->narg; i++)

+				substput(tsmap, t->gparam[i], orig->arg[i]);

+		}

 		for (i = 0; i < t->ngparam; i++)

 			lappend(&arg, &narg, tyspecialize(t->gparam[i], tsmap, delayed));

 		ret = mktyname(t->loc, t->name, tyspecialize(t->sub[0], tsmap, delayed));

+		if (orig->type == Tyunres)

+			substpop(tsmap);

 		ret->issynth = 1;

 		ret->arg = arg;

 		ret->narg = narg;

@@ -63,7 +121,7 @@

 		if (!hasparams(t))

 			return t;

 		var = mktyvar(t->loc);

-		htput(tsmap, t, var);

+		substput(tsmap, t, var);

 		for (i = 0; i < t->narg; i++)

 			lappend(&arg, &narg, tyspecialize(t->arg[i], tsmap, delayed));

 		ret = mktyname(t->loc, t->name, tyspecialize(t->sub[0], tsmap, delayed));

@@ -73,7 +131,7 @@

 		break;

 	case Tystruct:

 		ret = tydup(t);

-		htput(tsmap, t, ret);

+		substput(tsmap, t, ret);

 		pushstab(NULL);

 		for (i = 0; i < t->nmemb; i++)

 			ret->sdecls[i] = specializenode(t->sdecls[i], tsmap);

@@ -81,7 +139,7 @@

 		break;

 	case Tyunion:

 		ret = tydup(t);

-		htput(tsmap, t, ret);

+		substput(tsmap, t, ret);

 		for (i = 0; i < t->nmemb; i++) {

 			tmp = NULL;

 			if (ret->udecls[i]->etype)

@@ -104,7 +162,7 @@

 	default:

 		if (t->nsub > 0) {

 			ret = tydup(t);

-			htput(tsmap, t, ret);

+			substput(tsmap, t, ret);

 			for (i = 0; i < t->nsub; i++)

 				ret->sub[i] = tyspecialize(t->sub[i], tsmap, delayed);

 		} else {

@@ -118,7 +176,7 @@

 /* Checks if the type 't' is generic, and if it is

  * substitutes the types. This is here for efficiency,

  * so we don't gratuitously duplicate types */

-static Type *tysubst(Type *t, Htab *tsmap)

+static Type *tysubst(Type *t, Tysubst *tsmap)

 	if (hasparams(t))

 		return tyspecialize(t, tsmap, NULL);

@@ -130,7 +188,7 @@

  * Fills the substitution map with a mapping from

  * the type parameter 'from' to it's substititon 'to'

*/

-static void fillsubst(Htab *tsmap, Type *to, Type *from)

+static void fillsubst(Tysubst *tsmap, Type *to, Type *from)

 	size_t i;

@@ -137,7 +195,7 @@

 	if (from->type == Typaram) {

 		if (debugopt['S'])

 			printf("mapping %s => %s\n", tystr(from), tystr(to));

-		htput(tsmap, from, to);

+		substput(tsmap, from, to);

 		return;

 	assert(to->nsub == from->nsub);

@@ -249,7 +307,7 @@

  * need to be specialized to make it concrete

  * instead of generic, and returns it.

*/

-static Node *specializenode(Node *n, Htab *tsmap)

+static Node *specializenode(Node *n, Tysubst *tsmap)

 	Node *r;

 	size_t i;

@@ -397,8 +455,8 @@

 Node *specializedcl(Node *g, Type *to, Node **name)

 	extern int stabstkoff;

+	Tysubst *tsmap;

 	Node *d, *n;

-	Htab *tsmap;

 	Stab *st;

 	assert(g->type == Ndecl);

@@ -428,7 +486,7 @@

 		pushstab(st);

 	/* specialize */

-	tsmap = mkht(tyhash, tyeq);

+	tsmap = mksubst();

 	fillsubst(tsmap, to, g->decl.type);

 	d = mkdecl(g->loc, n, tysubst(g->decl.type, tsmap));

@@ -443,6 +501,7 @@

 	lappend(&file->file.stmts, &file->file.nstmts, d);

 	if (d->decl.name->name.ns)

 		popstab();

+	substfree(tsmap);

 	return d;