summaryrefslogtreecommitdiff
path: root/parse
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2016-01-31 22:18:17 -0800
committerOri Bernstein <ori@eigenstate.org>2016-01-31 22:49:31 -0800
commit128470e404d843b3d71c5837cac05d4d4203bd66 (patch)
tree267d7879867aebd35a7f8203d0ff9f77fb9238f0 /parse
parentfb8753c942a8d06926977d221d5c89c3a867fa29 (diff)
downloadmc-128470e404d843b3d71c5837cac05d4d4203bd66.tar.gz
Add support for generic impls.
You can now implement generic shit like iterators.
Diffstat (limited to 'parse')
-rw-r--r--parse/gram.y2
-rw-r--r--parse/infer.c21
-rw-r--r--parse/parse.h8
-rw-r--r--parse/specialize.c116
-rw-r--r--parse/type.c4
-rw-r--r--parse/use.c12
6 files changed, 141 insertions, 22 deletions
diff --git a/parse/gram.y b/parse/gram.y
index 732ad9b..cc69635 100644
--- a/parse/gram.y
+++ b/parse/gram.y
@@ -399,7 +399,7 @@ traitdef: Ttrait Tident generictype optauxtypes { /* trait prototype */
0);
for (i = 0; i < $6.nn; i++) {
$6.nl[i]->decl.trait = $$;
- $6.nl[i]->decl.impls = mkht(tyhash, tyeq);
+ $6.nl[i]->decl.__impls = mkht(tyhash, tyeq);
$6.nl[i]->decl.isgeneric = 1;
}
}
diff --git a/parse/infer.c b/parse/infer.c
index d531148..c728207 100644
--- a/parse/infer.c
+++ b/parse/infer.c
@@ -809,8 +809,6 @@ static int tyrank(Inferstate *st, Type *t)
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;
@@ -914,6 +912,10 @@ static void checksize(Inferstate *st, Node *ctx, Type *a, Type *b)
tystr(a), tystr(b), ctxstr(st, ctx));
}
+static int hasargs(Type *t)
+{
+ return t->type == Tyname && t->narg > 0;
+}
/* Unifies two types, or errors if the types are not unifiable. */
static Type *unify(Inferstate *st, Node *ctx, Type *u, Type *v)
@@ -972,7 +974,7 @@ static Type *unify(Inferstate *st, Node *ctx, Type *u, Type *v)
/* if the tyrank of a is 0 (ie, a raw tyvar), just unify.
* Otherwise, match up subtypes. */
if (a->type == b->type && a->type != Tyvar) {
- if (hasparam(a) && hasparam(b)) {
+ if (hasargs(a) && hasargs(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))
@@ -1684,9 +1686,6 @@ static void specializeimpl(Inferstate *st, Node *n)
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));
verifytraits(st, n, t->param, n->impl.type);
subst = mksubst();
substput(subst, t->param, n->impl.type);
@@ -1707,7 +1706,13 @@ static void specializeimpl(Inferstate *st, Node *n)
fname(sym->loc), lnum(sym->loc));
dcl->decl.name = name;
putdcl(file->file.globls, dcl);
- htput(proto->decl.impls, n->impl.type, dcl);
+ htput(proto->decl.__impls, n->impl.type, dcl);
+ dcl->decl.isconst = 1;
+ if (n->impl.type->type == Tygeneric || hasparams(n->impl.type)) {
+ dcl->decl.isgeneric = 1;
+ lappend(&proto->decl.gimpl, &proto->decl.ngimpl, dcl);
+ lappend(&proto->decl.gtype, &proto->decl.ngtype, ty);
+ }
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),
@@ -2071,7 +2076,7 @@ static void checkvar(Inferstate *st, Node *n)
ty = NULL;
dcl = NULL;
if (n->expr.param)
- dcl = htget(proto->decl.impls, tf(st, n->expr.param));
+ dcl = htget(proto->decl.__impls, tf(st, n->expr.param));
if (dcl)
ty = dcl->decl.type;
if (!ty)
diff --git a/parse/parse.h b/parse/parse.h
index 8022ca8..c02c040 100644
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -328,9 +328,13 @@ struct Node {
impl.
*/
Trait *trait;
- Htab *impls;
- char vis;
+ Htab *__impls;
+ Node **gimpl; /* generic impls of this trait */
+ size_t ngimpl;
+ Node **gtype; /* generic impls of this trait */
+ size_t ngtype;
+ char vis;
/* flags */
char isglobl;
char isconst;
diff --git a/parse/specialize.c b/parse/specialize.c
index dce9f00..bdaa65f 100644
--- a/parse/specialize.c
+++ b/parse/specialize.c
@@ -317,7 +317,9 @@ static Node *specializenode(Node *n, Tysubst *tsmap)
r = mknode(n->loc, n->type);
switch (n->type) {
case Nfile:
- case Nuse: die("Node %s not allowed here\n", nodestr[n->type]); break;
+ case Nuse:
+ die("Node %s not allowed here\n", nodestr[n->type]);
+ break;
case Nexpr:
r->expr.op = n->expr.op;
r->expr.type = tysubst(n->expr.type, tsmap);
@@ -447,6 +449,107 @@ Node *genericname(Node *n, Type *t)
return name;
}
+/* this doesn't walk through named types, so it can't recurse infinitely. */
+int matchquality(Type *pat, Type *to)
+{
+ int match, q;
+ size_t i;
+ Ucon *puc, *tuc;
+
+ if (pat->type == Typaram)
+ return 0;
+ else if (pat->type != to->type)
+ return -1;
+
+ match = 0;
+ switch (pat->type) {
+ case Tystruct:
+ if (pat->nmemb != to->nmemb)
+ return -1;
+ for (i = 0; i < pat->nmemb; i++) {
+ if (!streq(declname(pat->sdecls[i]),declname( to->sdecls[i])))
+ return -1;
+ q = matchquality(decltype(pat->sdecls[i]), decltype(to->sdecls[i]));
+ if (q < 0)
+ return -1;
+ match += q;
+ }
+ break;
+ case Tyunion:
+ if (pat->nmemb != to->nmemb)
+ return -1;
+ for (i = 0; i < pat->nmemb; i++) {
+ if (!nameeq(pat->udecls[i], to->udecls[i]))
+ return -1;
+ puc = pat->udecls[i];
+ tuc = to->udecls[i];
+ if (puc->etype && tuc->etype) {
+ q = matchquality(puc->etype, tuc->etype);
+ if (q < 0)
+ return -1;
+ match += q;
+ } else if (puc->etype != tuc->etype) {
+ return -1;
+ }
+ }
+ break;
+ case Tyname:
+ if (!nameeq(pat->name, to->name))
+ return -1;
+ if (pat->narg != to->narg)
+ return -1;
+ for (i = 0; i < pat->narg; i++) {
+ q = matchquality(pat->sub[i], to->sub[i]);
+ if (q < 0)
+ return -1;
+ match += q;
+ }
+ break;
+ default:
+ if (pat->nsub != to->nsub)
+ break;
+ if (pat->type == to->type)
+ match = 1;
+ for (i = 0; i < pat->nsub; i++) {
+ q = matchquality(pat->sub[i], to->sub[i]);
+ if (q < 0)
+ return -1;
+ match += q;
+ }
+ break;
+ }
+ return match;
+}
+
+Node *bestimpl(Node *n, Type *to)
+{
+ Node **gimpl, **ambig, *match;
+ size_t ngimpl, nambig, i;
+ int score;
+ int best;
+
+ ambig = NULL;
+ nambig = 0;
+ best = -1;
+ gimpl = n->decl.gimpl;
+ ngimpl = n->decl.ngimpl;
+ for (i = 0; i < ngimpl; i++) {
+ score = matchquality(decltype(gimpl[i]), to);
+ if (score > best) {
+ lfree(&ambig, &nambig);
+ best = score;
+ match = gimpl[i];
+ } else if (score == best) {
+ lappend(&ambig, &nambig, gimpl[i]);
+ }
+ }
+ if (best < 0)
+ return NULL;
+ else if (nambig > 0)
+ fatal(n, "ambiguous implementation for %s", tystr(to));
+ return match;
+}
+
/*
* Takes a generic declaration, and creates a specialized
* duplicate of it with type 'to'. It also generates
@@ -471,15 +574,16 @@ Node *specializedcl(Node *g, Type *to, Node **name)
if (!st)
fatal(n, "Can't find symbol table for %s.%s", n->name.ns, n->name.name);
d = getdcl(st, n);
- if (debugopt['S'])
- printf("depth[%d] specializing [%d]%s => %s\n", stabstkoff, g->loc.line,
- namestr(g->decl.name), namestr(n));
if (d)
return d;
if (g->decl.trait) {
- printf("%s\n", namestr(n));
- fatal(g, "no trait implemented for for %s:%s", namestr(g->decl.name), tystr(to));
+ g = bestimpl(g, to);
+ if (!g)
+ fatal(g, "no trait implemented for for %s:%s", namestr(g->decl.name), tystr(to));
}
+ if (debugopt['S'])
+ printf("depth[%d] specializing [%d]%s => %s\n", stabstkoff, g->loc.line,
+ namestr(g->decl.name), namestr(n));
/* namespaced names need to be looked up in their correct
* context. */
if (n->name.ns)
diff --git a/parse/type.c b/parse/type.c
index d711b6b..f6cd127 100644
--- a/parse/type.c
+++ b/parse/type.c
@@ -856,7 +856,7 @@ void iterableinit(Stab *st, Trait *tr)
func = mkdecl(Zloc, mkname(Zloc, "__iternext__"), ty);
func->decl.trait = tr;
- func->decl.impls = mkht(tyhash, tyeq);
+ func->decl.__impls = mkht(tyhash, tyeq);
func->decl.isgeneric = 1;
func->decl.isconst = 1;
func->decl.isglobl = 1;
@@ -876,7 +876,7 @@ void iterableinit(Stab *st, Trait *tr)
func = mkdecl(Zloc, mkname(Zloc, "__iterfin__"), ty);
func->decl.trait = tr;
- func->decl.impls = mkht(tyhash, tyeq);
+ func->decl.__impls = mkht(tyhash, tyeq);
func->decl.isgeneric = 1;
func->decl.isconst = 1;
func->decl.isglobl = 1;
diff --git a/parse/use.c b/parse/use.c
index acdefab..f1dbb71 100644
--- a/parse/use.c
+++ b/parse/use.c
@@ -813,14 +813,20 @@ static void protomap(Trait *tr, Type *ty, Node *dcl)
{
size_t i, len;
char *protoname, *dclname, *p;
+ Node *proto;
dclname = declname(dcl);
for (i = 0; i < tr->nfuncs; i++) {
- protoname = declname(tr->funcs[i]);
+ proto = tr->funcs[i];
+ protoname = declname(proto);
len = strlen(protoname);
p = strstr(dclname, protoname);
if (p && p[len] == '$')
- htput(tr->funcs[i]->decl.impls, ty, dcl);
+ htput(proto->decl.__impls, ty, dcl);
+ if (ty->type == Tygeneric || hasparams(ty)) {
+ lappend(&proto->decl.gimpl, &proto->decl.ngimpl, dcl);
+ lappend(&proto->decl.gtype, &proto->decl.ngtype, ty);
+ }
}
}
@@ -948,7 +954,7 @@ foundextlib:
puttrait(s, tr->name, tr);
for (i = 0; i < tr->nfuncs; i++) {
putdcl(s, tr->funcs[i]);
- tr->funcs[i]->decl.impls = mkht(tyhash, tyeq);
+ tr->funcs[i]->decl.__impls = mkht(tyhash, tyeq);
}
break;
case 'T':