summaryrefslogtreecommitdiff
path: root/parse
diff options
context:
space:
mode:
Diffstat (limited to 'parse')
-rw-r--r--parse/export.c6
-rw-r--r--parse/gram.y4
-rw-r--r--parse/infer.c378
-rw-r--r--parse/parse.h9
-rw-r--r--parse/specialize.c135
-rw-r--r--parse/trait.def2
-rw-r--r--parse/type.c171
-rw-r--r--parse/use.c36
8 files changed, 397 insertions, 344 deletions
diff --git a/parse/export.c b/parse/export.c
index 0963361..1f37e71 100644
--- a/parse/export.c
+++ b/parse/export.c
@@ -75,9 +75,9 @@ tagtype(Stab *st, Type *t, int ingeneric, int hidelocal)
return;
t->vis = Vishidden;
/* export the user defined traits */
- if (t->traits)
- for (i = Ntraits; bsiter(t->traits, &i); i++)
- tagtrait(st, traittab[i], ingeneric, hidelocal);
+ //if (t->traits)
+ // for (i = Ntraits; bsiter(t->traits, &i); i++)
+ // tagtrait(st, traittab[i], ingeneric, hidelocal);
for (i = 0; i < t->nsub; i++)
tagtype(st, t->sub[i], ingeneric, hidelocal);
switch (t->type) {
diff --git a/parse/gram.y b/parse/gram.y
index 6198b49..424538e 100644
--- a/parse/gram.y
+++ b/parse/gram.y
@@ -1081,7 +1081,9 @@ static void addtrait(Type *t, char *str)
for (i = 0; i < ntraittab; i++) {
if (!strcmp(namestr(traittab[i]->name), str)) {
- settrait(t, traittab[i]);
+ if (!t->trneed)
+ t->trneed = mkbs();
+ bsput(t->trneed, i);
return;
}
}
diff --git a/parse/infer.c b/parse/infer.c
index 29b3006..6d15240 100644
--- a/parse/infer.c
+++ b/parse/infer.c
@@ -15,6 +15,21 @@
#include "util.h"
#include "parse.h"
+typedef struct Traitmap Traitmap;
+typedef struct Enttype Enttype;
+
+struct Traitmap {
+ Bitset *traits;
+ Traitmap *sub[Ntypes];
+
+ Htab *name; /* name => bitset(traits) */
+ Type **filter;
+ size_t nfilter;
+ Trait **filtertr;
+ size_t nfiltertr;
+};
+
+
static void infernode(Node **np, Type *ret, int *sawret);
static void inferexpr(Node **np, Type *ret, int *sawret);
static void inferdecl(Node *n);
@@ -51,6 +66,7 @@ static size_t nspecializations;
static Stab **specializationscope;
static size_t nspecializationscope;
static Htab *seqbase;
+static Traitmap *traitmap;
static void
ctxstrcall(char *buf, size_t sz, Node *n)
@@ -239,8 +255,8 @@ adddispspecialization(Node *n, Stab *stab)
tr = traittab[Tcdisp];
ty = decltype(n);
- if (!ty->traits || !bshas(ty->traits, Tcdisp))
- return;
+ //if (!ty->traits || !bshas(ty->traits, Tcdisp))
+ // return;
assert(tr->nproto == 1);
if (hthas(tr->proto[0]->decl.impls, ty))
return;
@@ -250,7 +266,7 @@ adddispspecialization(Node *n, Stab *stab)
}
static void
-additerspecializations(Node *n, Stab *stab)
+additerspecialization(Node *n, Stab *stab)
{
Trait *tr;
Type *ty;
@@ -258,8 +274,8 @@ additerspecializations(Node *n, Stab *stab)
tr = traittab[Tciter];
ty = exprtype(n->iterstmt.seq);
- if (!ty->traits || !bshas(ty->traits, Tciter))
- return;
+ //if (!ty->traits || !bshas(ty->traits, Tciter))
+ // return;
if (ty->type == Tyslice || ty->type == Tyarray || ty->type == Typtr)
return;
for (i = 0; i < tr->nproto; i++) {
@@ -516,11 +532,6 @@ tyresolve(Type *t)
}
}
base = tybase(t);
- /* no-ops if base == t */
- if (t->traits && base->traits)
- bsunion(t->traits, base->traits);
- else if (base->traits)
- t->traits = bsdup(base->traits);
if (occurs(t))
lfatal(t->loc, "type %s includes itself", tystr(t));
popenv(t->env);
@@ -642,6 +653,17 @@ settype(Node *n, Type *t)
marksrc(t, n->loc);
}
+static Type*
+mktylike(Srcloc l, Ty other)
+{
+ Type *t;
+
+ t = mktyvar(l);
+ /* not perfect in general, but good enough for all places mktylike is used. */
+ t->trneed = bsdup(traitmap->sub[other]->traits);
+ return t;
+}
+
/* Gets the type of a literal value */
static Type *
littype(Node *n)
@@ -669,19 +691,11 @@ static Type *
delayeducon(Type *fallback)
{
Type *t;
- char *from, *to;
if (fallback->type != Tyunion)
return fallback;
t = mktylike(fallback->loc, fallback->type);
htput(delayed, t, fallback);
- if (debugopt['u']) {
- from = tystr(t);
- to = tystr(fallback);
- indentf(indentdepth, "Delay %s -> %s\n", from, to);
- free(from);
- free(to);
- }
return t;
}
@@ -746,43 +760,108 @@ _bind(Tyenv *e, Node *n)
* constraint list. Otherwise, the type is checked to see
* if it has the required constraint */
static void
-constrain(Node *ctx, Type *a, Trait *c)
+constrain(Node *ctx, Type *base, Trait *tr)
{
- 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(ctx));
+ Traitmap *tm;
+ Bitset *bs;
+ Type *ty;
+ size_t i;
+
+ while(1) {
+ ty = base;
+ tm = traitmap->sub[ty->type];
+ while (1) {
+ if (ty->type == Typaram && bshas(ty->trneed, tr->uid))
+ return;
+ if (ty->type == Tyvar) {
+ if (!ty->trneed)
+ ty->trneed = mkbs();
+ bsput(ty->trneed, tr->uid);
+ return;
+ }
+ if (bshas(tm->traits, tr->uid))
+ return;
+ if (tm->name && ty->type == Tyname) {
+ bs = htget(tm->name, ty->name);
+ if (bs && bshas(bs, tr->uid))
+ return;
+ }
+ for (i = 0; i < tm->nfilter; i++) {
+ if (tm->filtertr[i]->uid != tr->uid)
+ continue;
+ if (tymatchrank(tm->filter[i], ty) >= 0)
+ return;
+ }
+ if (!tm->sub[ty->type])
+ break;
+ assert(ty->nsub == 1);
+ tm = tm->sub[ty->type];
+ ty = ty->sub[0];
+ }
+ if (base->type != Tyname)
+ break;
+ base = base->sub[0];
}
+ fatal(ctx, "%s needs trait %s near %s", tystr(ty), namestr(tr->name), ctxstr(ctx));
}
-static int
-satisfiestraits(Type *a, Type *b)
+static void
+traitsfor(Type *base, Bitset *dst)
{
- if (!a->traits || bscount(a->traits) == 0)
- return 1;
- if (b->traits)
- return bsissubset(a->traits, b->traits);
- return 0;
+ Traitmap *tm;
+ Type *ty;
+ size_t i;
+
+ while(1) {
+ ty = base;
+ tm = traitmap->sub[ty->type];
+ while (1) {
+ if (ty->type == Tyvar)
+ break;
+ bsunion(dst, tm->traits);
+ for (i = 0; i < tm->nfilter; i++) {
+ if (tymatchrank(tm->filter[i], ty) >= 0)
+ bsput(dst, tm->filtertr[i]->uid);
+ }
+ if (!tm->sub[ty->type] || ty->nsub != 1)
+ break;
+ tm = tm->sub[ty->type];
+ ty = ty->sub[0];
+ }
+ if (base->type != Tyname)
+ break;
+ base = base->sub[0];
+ }
}
static void
verifytraits(Node *ctx, Type *a, Type *b)
{
+ char traitbuf[64], abuf[64], bbuf[64];
+ char asrc[64], bsrc[64];
+ Bitset *abs, *bbs;
size_t i, n;
Srcloc l;
char *sep;
- char traitbuf[64], abuf[64], bbuf[64];
- char asrc[64], bsrc[64];
- if (!satisfiestraits(a, b)) {
+ abs = a->trneed;
+ if (!abs) {
+ abs = mkbs();
+ traitsfor(a, abs);
+ }
+ bbs = b->trneed;
+ if (!bbs) {
+ bbs = mkbs();
+ traitsfor(b, bbs);
+ }
+ if (!bsissubset(abs, bbs)) {
sep = "";
n = 0;
- for (i = 0; bsiter(a->traits, &i); i++) {
- if (!b->traits || !bshas(b->traits, i))
+ *traitbuf = 0;
+ for (i = 0; bsiter(abs, &i); i++) {
+ if (!bshas(bbs, i))
n += bprintf(traitbuf + n, sizeof(traitbuf) - n, "%s%s", sep,
- namestr(traittab[i]->name));
+ namestr(traittab[i]->name));
sep = ",";
}
tyfmt(abuf, sizeof abuf, a);
@@ -792,24 +871,28 @@ verifytraits(Node *ctx, Type *a, Type *b)
l = unifysrc[b->tid];
snprintf(bsrc, sizeof asrc, "\n\t%s from %s:%d", bbuf, fname(l), lnum(l));
}
- fatal(ctx, "%s missing traits %s for %s near %s%s%s",
- bbuf, traitbuf, abuf, ctxstr(ctx),
- srcstr(a), srcstr(b));
+ fatal(ctx, "%s needs trait %s near %s%s%s",
+ bbuf, traitbuf, ctxstr(ctx), srcstr(a), srcstr(b));
}
+ if (!a->trneed)
+ bsfree(abs);
+ if (!b->trneed)
+ bsfree(bbs);
}
/* Merges the constraints on types */
static void
mergetraits(Node *ctx, Type *a, Type *b)
{
+// TRFIX
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);
+ if (a->trneed && b->trneed)
+ bsunion(b->trneed, a->trneed);
+ else if (a->trneed)
+ b->trneed = bsdup(a->trneed);
+ else if (b->trneed)
+ a->trneed = bsdup(b->trneed);
} else {
verifytraits(ctx, a, b);
}
@@ -963,7 +1046,6 @@ unify(Node *ctx, Type *u, Type *v)
Type *t, *r;
Type *a, *b;
Type *ea, *eb;
- char *from, *to;
size_t i;
/* a ==> b */
@@ -979,16 +1061,6 @@ unify(Node *ctx, Type *u, Type *v)
b = t;
}
- if (debugopt['u']) {
- from = tystr(a);
- to = tystr(b);
- indentf(indentdepth, "Unify %s => %s\n", from, to);
- indentf(indentdepth + 1, "indexes: %s => %s\n",
- tystr(htget(seqbase, a)), tystr(htget(seqbase, b)));
- free(from);
- free(to);
- }
-
/* Disallow recursive types */
if (a->type == Tyvar && b->type != Tyvar) {
if (occursin(a, b))
@@ -1075,7 +1147,6 @@ unifycall(Node *n)
{
size_t i;
Type *ft;
- char *ret, *ctx;
ft = type(n->expr.args[0]);
@@ -1100,14 +1171,6 @@ unifycall(Node *n)
if (i < ft->nsub && ft->sub[i]->type != Tyvalist)
fatal(n, "%s arity mismatch (expected %zd args, got %zd)",
ctxstr(n->expr.args[0]), ft->nsub - 1, i - 1);
- if (debugopt['u']) {
- ret = tystr(ft->sub[0]);
- ctx = ctxstr(n->expr.args[0]);
- indentf(indentdepth, "Call of %s returns %s\n", ctx, ret);
- free(ctx);
- free(ret);
- }
-
settype(n, ft->sub[0]);
}
@@ -1811,10 +1874,6 @@ specializeimpl(Node *n)
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(proto)), namestr(name),
- tystr(ty));
dcl->decl.vis = t->vis;
lappend(&impldecl, &nimpldecl, dcl);
@@ -1901,8 +1960,6 @@ infernode(Node **np, Type *ret, int *sawret)
popstab();
break;
case Ndecl:
- if (debugopt['u'])
- indentf(indentdepth, "--- infer %s ---\n", declname(n));
if (n->decl.isgeneric)
ingeneric++;
indentdepth++;
@@ -1915,8 +1972,6 @@ infernode(Node **np, Type *ret, int *sawret)
constrain(n, type(n), traittab[Tcdisp]);
popenv(n->decl.env);
indentdepth--;
- if (debugopt['u'])
- indentf(indentdepth, "--- done ---\n");
if (n->decl.isgeneric)
ingeneric--;
break;
@@ -2011,7 +2066,6 @@ tyfix(Node *ctx, Type *orig, int noerr)
static Type *tyint, *tyflt;
Type *t, *d, *base;
Tyenv *env;
- char *from, *to;
size_t i;
char buf[1024];
@@ -2036,10 +2090,10 @@ tyfix(Node *ctx, Type *orig, int noerr)
tystr(d), ctxstr(ctx));
}
}
- if (t->type == Tyvar) {
- if (hastrait(t, traittab[Tcint]) && satisfiestraits(t, tyint))
+ if (t->type == Tyvar && t->trneed) {
+ if (bshas(t->trneed, Tcint) && bshas(t->trneed, Tcnum))
t = tyint;
- if (hastrait(t, traittab[Tcfloat]) && satisfiestraits(t, tyflt))
+ else if (bshas(t->trneed, Tcflt) && bshas(t->trneed, Tcnum))
t = tyflt;
} else if (!t->fixed) {
t->fixed = 1;
@@ -2066,19 +2120,8 @@ tyfix(Node *ctx, Type *orig, int noerr)
t->sub[i] = tyfix(ctx, t->sub[i], noerr);
}
- if (t->type == Tyvar && !noerr) {
- if (debugopt['T'])
- dump(file, stdout);
+ if (t->type == Tyvar && !noerr)
fatal(ctx, "underconstrained type %s near %s", tyfmt(buf, 1024, t), ctxstr(ctx));
- }
-
- if (debugopt['u'] && !tyeq(orig, t)) {
- from = tystr(orig);
- to = tystr(t);
- indentf(indentdepth, "subst %s => %s\n", from, to);
- free(from);
- free(to);
- }
if (base)
htput(seqbase, t, base);
if (env)
@@ -2439,7 +2482,7 @@ typesub(Node *n, int noerr)
typesub(n->iterstmt.elt, noerr);
typesub(n->iterstmt.seq, noerr);
typesub(n->iterstmt.body, noerr);
- additerspecializations(n, curstab());
+ additerspecialization(n, curstab());
break;
case Nmatchstmt:
typesub(n->matchstmt.val, noerr);
@@ -2560,39 +2603,141 @@ specialize(void)
popstab();
}
}
+static void
+builtintraits(void)
+{
+ size_t i;
+
+ /* char::(numeric,integral) */
+ for (i = 0; i < Ntypes; i++) {
+ traitmap->sub[i] = zalloc(sizeof(Traitmap));
+ traitmap->sub[i]->traits = mkbs();
+ traitmap->sub[i]->name = mkht(namehash, nameeq);
+ }
+
+ bsput(traitmap->sub[Tychar]->traits, Tcnum);
+ bsput(traitmap->sub[Tychar]->traits, Tcint);
+
+ bsput(traitmap->sub[Tybyte]->traits, Tcnum);
+ bsput(traitmap->sub[Tybyte]->traits, Tcint);
+
+ /* <integer types>::(numeric,integral) */
+ for (i = Tyint8; i < Tyflt32; i++) {
+ bsput(traitmap->sub[i]->traits, Tcnum);
+ bsput(traitmap->sub[i]->traits, Tcint);
+ }
+
+ /* <floats>::(numeric,floating) */
+ bsput(traitmap->sub[Tyflt32]->traits, Tcnum);
+ bsput(traitmap->sub[Tyflt32]->traits, Tcflt);
+ bsput(traitmap->sub[Tyflt64]->traits, Tcnum);
+ bsput(traitmap->sub[Tyflt64]->traits, Tcflt);
+
+ /* @a*::(sliceable) */
+ bsput(traitmap->sub[Typtr]->traits, Tcslice);
+
+ /* @a[:]::(indexable,sliceable) */
+ bsput(traitmap->sub[Tyslice]->traits, Tcidx);
+ bsput(traitmap->sub[Tyslice]->traits, Tcslice);
+ bsput(traitmap->sub[Tyslice]->traits, Tciter);
+
+ /* @a[SZ]::(indexable,sliceable) */
+ bsput(traitmap->sub[Tyarray]->traits, Tcidx);
+ bsput(traitmap->sub[Tyarray]->traits, Tcslice);
+ bsput(traitmap->sub[Tyarray]->traits, Tciter);
+
+ /* @a::function */
+ bsput(traitmap->sub[Tyfunc]->traits, Tcfunc);
+}
+
+static Trait*
+findtrait(Node *impl)
+{
+ Trait *tr;
+ Node *n;
+ Stab *ns;
+
+ tr = impl->impl.trait;
+ if (!tr) {
+ n = impl->impl.traitname;
+ ns = file->file.globls;
+ if (n->name.ns)
+ ns = getns(file, n->name.ns);
+ if (ns)
+ tr = gettrait(ns, n);
+ if (!tr)
+ fatal(impl, "trait %s does not exist near %s",
+ namestr(impl->impl.traitname), ctxstr(impl));
+ if (tr->naux != impl->impl.naux)
+ fatal(impl, "incompatible implementation of %s: mismatched aux types",
+ namestr(impl->impl.traitname), ctxstr(impl));
+ }
+ return tr;
+}
static void
-applytraits(void)
+addtraittab(Traitmap *m, Trait *tr, Type *ty)
+{
+ Bitset *bs;
+ Traitmap *mm;
+
+ if (!m->sub[ty->type]) {
+ m->sub[ty->type] = zalloc(sizeof(Traitmap));
+ m->sub[ty->type]->traits = mkbs();
+ m->sub[ty->type]->name = mkht(namehash, nameeq);
+ }
+ mm = m->sub[ty->type];
+ switch (ty->type) {
+ case Tygeneric:
+ case Typaram:
+ lappend(&mm->filter, &m->nfilter, ty);
+ lappend(&mm->filtertr, &m->nfiltertr, tr);
+ break;
+ case Tyname:
+ if (ty->ngparam == 0) {
+ bs = htget(mm->name, ty->name);
+ if (!bs) {
+ bs = mkbs();
+ htput(mm->name, ty->name, bs);
+ }
+ bsput(bs, tr->uid);
+ } else {
+ lappend(&mm->filter, &m->nfilter, ty);
+ lappend(&mm->filtertr, &m->nfiltertr, tr);
+ }
+ break;
+ case Typtr:
+ case Tyarray:
+ addtraittab(mm, tr, ty->sub[0]);
+ break;
+ default:
+ if (istyprimitive(ty)) {
+ bsput(mm->traits, tr->uid);
+ } else {
+ lappend(&mm->filter, &m->nfilter, ty);
+ lappend(&mm->filtertr, &m->nfiltertr, tr);
+ }
+ }
+}
+
+static void
+initimpl(void)
{
size_t i;
- Node *impl, *n;
+ Node *impl;
Trait *tr;
Type *ty;
- Stab *ns;
- tr = NULL;
pushstab(file->file.globls);
- /* for now, traits can only be declared globally */
+ traitmap = zalloc(sizeof(Traitmap));
+ builtintraits();
for (i = 0; i < nimpltab; i++) {
impl = impltab[i];
- tr = impl->impl.trait;
- if (!tr) {
- n = impl->impl.traitname;
- ns = file->file.globls;
- if (n->name.ns)
- ns = getns(file, n->name.ns);
- if (ns)
- tr = gettrait(ns, n);
- if (!tr)
- fatal(impl, "trait %s does not exist near %s",
- namestr(impl->impl.traitname), ctxstr(impl));
- if (tr->naux != impl->impl.naux)
- fatal(impl, "incompatible implementation of %s: mismatched aux types",
- namestr(impl->impl.traitname), ctxstr(impl));
- }
+ tr = findtrait(impl);
+
pushenv(impl->impl.env);
ty = tf(impl->impl.type);
- settrait(ty, tr);
+ addtraittab(traitmap, tr, ty);
if (tr->uid == Tciter) {
htput(seqbase, tf(impl->impl.type), tf(impl->impl.aux[0]));
}
@@ -2601,7 +2746,7 @@ applytraits(void)
popstab();
}
-void
+static void
verify(void)
{
Type *t;
@@ -2630,15 +2775,14 @@ verify(void)
}
void
-infer()
+infer(void)
{
delayed = mkht(tyhash, tyeq);
seqbase = mkht(tyhash, tyeq);
- /* set up the symtabs */
loaduses();
+ initimpl();
/* do the inference */
- applytraits();
infernode(&file, NULL, NULL);
postinfer();
diff --git a/parse/parse.h b/parse/parse.h
index b142c33..443407b 100644
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -124,7 +124,6 @@ struct Type {
Srcloc loc;
Vis vis;
- Bitset *traits; /* the type constraints matched on this type */
Type **gparam; /* Tygeneric: type parameters that match the type args */
size_t ngparam; /* Tygeneric: count of type parameters */
@@ -137,6 +136,7 @@ struct Type {
Type **sub; /* sub-types; shared by all composite types */
size_t nsub; /* For compound types */
size_t nmemb; /* for aggregate types (struct, union) */
+ Bitset *trneed; /* traits needed by this Tyvar/Typaram */
union {
Node *name; /* Tyname: unresolved name. Tyalias: alias name */
Node *asize; /* array size */
@@ -146,7 +146,6 @@ struct Type {
};
char hasparams; /* cache for whether this type has params */
- char issynth; /* Tyname: whether this is synthesized or not */
char ishidden; /* Tyname: whether this is hidden or not */
char ispkglocal; /* Tyname: whether this is package local or not */
char isimport; /* Tyname: whether tyis type was imported. */
@@ -379,6 +378,7 @@ int litvaleq(Node *a, Node *b);
ulong tyhash(void *t);
int tyeq(void *a, void *b);
int tystricteq(void *a, void *b);
+int tymatchrank(Type *pat, Type *to);
ulong namehash(void *t);
int nameeq(void *a, void *b);
ulong nsnamehash(void *t);
@@ -454,7 +454,6 @@ Trait *mktrait(Srcloc l, Node *name,
Type **aux, size_t naux,
Node **proto, size_t nproto,
int isproto);
-Type *mktylike(Srcloc l, Ty ty); /* constrains tyvar t like it was builtin ty */
Ucon *finducon(Type *t, Node *name);
int isstacktype(Type *t);
int istysigned(Type *t);
@@ -469,8 +468,6 @@ char *tyfmt(char *buf, size_t len, Type *t);
char *tystr(Type *t);
size_t tyidfmt(char *buf, size_t len, Type *t);
-int hastrait(Type *t, Trait *c);
-int settrait(Type *t, Trait *c);
int traiteq(Type *t, Trait **traits, size_t len);
int traitfmt(char *buf, size_t len, Type *t);
char *traitstr(Type *t);
@@ -531,8 +528,6 @@ Tysubst *mksubst(void);
void substfree(Tysubst *subst);
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 *param, Type *to, Node **name);
Type *tyspecialize(Type *t, Tysubst *tymap, Htab *delayed, Htab *tybase);
Node *genericname(Node *n, Type *param, Type *t);
diff --git a/parse/specialize.c b/parse/specialize.c
index 86a84cb..c5d4a59 100644
--- a/parse/specialize.c
+++ b/parse/specialize.c
@@ -15,33 +15,13 @@
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
+static void
substpush(Tysubst *subst)
{
lappend(&subst->subst, &subst->nsubst, mkht(tyhash, tyeq));
}
-void
+static void
substpop(Tysubst *subst)
{
Htab *ht;
@@ -71,14 +51,24 @@ substget(Tysubst *subst, Type *from)
return t;
}
+Tysubst *
+mksubst(void)
+{
+ Tysubst *subst;
+
+ subst = zalloc(sizeof(Tysubst));
+ substpush(subst);
+ return subst;
+}
+
void
-addtraits(Type *t, Bitset *traits)
+substfree(Tysubst *subst)
{
- size_t b;
+ size_t i;
- if (traits)
- for (b = 0; bsiter(traits, &b); b++)
- settrait(t, traittab[b]);
+ for (i = 0; i < subst->nsubst; i++)
+ htfree(subst->subst[i]);
+ lfree(&subst->subst, &subst->nsubst);
}
/*
@@ -106,7 +96,7 @@ tyspecialize(Type *orig, Tysubst *tsmap, Htab *delayed, Htab *trbase)
switch (t->type) {
case Typaram:
ret = mktyvar(t->loc);
- addtraits(ret, t->traits);
+ ret->trneed = bsdup(t->trneed);
substput(tsmap, t, ret);
break;
case Tygeneric:
@@ -124,7 +114,6 @@ tyspecialize(Type *orig, Tysubst *tsmap, Htab *delayed, Htab *trbase)
substpop(tsmap);
ret->arg = arg;
ret->narg = narg;
- ret->traits = bsdup(t->traits);
tytab[var->tid] = ret;
break;
case Tyname:
@@ -135,7 +124,6 @@ tyspecialize(Type *orig, Tysubst *tsmap, Htab *delayed, Htab *trbase)
for (i = 0; i < t->narg; i++)
lappend(&arg, &narg, tyspecialize(t->arg[i], tsmap, delayed, trbase));
ret = mktyname(t->loc, t->name, tyspecialize(t->sub[0], tsmap, delayed, trbase));
- ret->traits = bsdup(t->traits);
ret->arg = arg;
ret->narg = narg;
if (trbase && hthas(trbase, orig) && !hthas(trbase, ret)) {
@@ -474,90 +462,7 @@ genericname(Node *n, Type *param, 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->arg[i], to->arg[i]);
- if (q < 0)
- return -1;
- match += q;
- }
- break;
- case Tyarray:
- /* unsized arrays are ok */
- if (pat->asize && to->asize) {
- if (!!litvaleq(pat->asize->expr.args[0], to->asize->expr.args[0]))
- return -1;
- } else if (pat->asize != to->asize) {
- return -1;
- }
- else return matchquality(pat->sub[0], to->sub[0]);
- 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 *
+static Node *
bestimpl(Node *n, Type *to)
{
Node **gimpl, **ambig, *match;
@@ -574,7 +479,7 @@ bestimpl(Node *n, Type *to)
gimpl = n->decl.gimpl;
ngimpl = n->decl.ngimpl;
for (i = 0; i < ngimpl; i++) {
- score = matchquality(decltype(gimpl[i]), to);
+ score = tymatchrank(decltype(gimpl[i]), to);
if (score > best) {
lfree(&ambig, &nambig);
best = score;
diff --git a/parse/trait.def b/parse/trait.def
index 11a3438..81dc62d 100644
--- a/parse/trait.def
+++ b/parse/trait.def
@@ -1,7 +1,7 @@
/* Definitions of built in constraints */
Tc(Tcnum, "numeric") /* arith ops */
Tc(Tcint, "integral") /* behaves like an int, defaults to int as fallback */
-Tc(Tcfloat, "floating") /* behaves like a float, defaults to float as fallback */
+Tc(Tcflt, "floating") /* behaves like a float, defaults to float as fallback */
Tc(Tcidx, "indexable") /* indexable */
Tc(Tcslice, "sliceable") /* sliceable */
Tc(Tcfunc, "function") /* behaves like a function */
diff --git a/parse/type.c b/parse/type.c
index bb8f7b8..6d26670 100644
--- a/parse/type.c
+++ b/parse/type.c
@@ -15,11 +15,6 @@
#include "parse.h"
typedef struct Typename Typename;
-struct Typename {
- Ty ty;
- char *name;
-};
-
Type **tytab = NULL;
Type **types = NULL;
size_t ntypes;
@@ -30,7 +25,6 @@ size_t nimpltab;
static Htab *tydeduptab;
/* Built in type constraints */
-static Trait *traits[Ntypes + 1][4];
static int tybfmt(char *buf, size_t len, Bitset *visted, Type *t);
char stackness[] = {
@@ -64,7 +58,6 @@ Type *
mktype(Srcloc loc, Ty ty)
{
Type *t;
- int i;
/* the first 'n' types will be identity mapped: tytab[Tyint], eg,
* will map to an instantitaion of Tyint.
@@ -87,9 +80,6 @@ mktype(Srcloc loc, Ty ty)
if (ty <= Tyvalist) /* the last builtin atomic type */
t->vis = Visbuiltin;
- for (i = 0; traits[ty][i]; i++)
- settrait(t, traits[ty][i]);
-
return t;
}
@@ -106,8 +96,6 @@ tydup(Type *t)
r->resolved = 0; /* re-resolving doesn't hurt */
r->fixed = 0; /* re-resolving doesn't hurt */
- r->traits = bsdup(t->traits);
-
r->arg = memdup(t->arg, t->narg * sizeof(Type *));
r->narg = t->narg;
r->inst = memdup(t->arg, t->narg * sizeof(Type *));
@@ -128,22 +116,6 @@ tydup(Type *t)
return r;
}
-/*
- * Creates a Tyvar with the same
- * constrants as the 'like' type
- */
-Type *
-mktylike(Srcloc loc, Ty like)
-{
- Type *t;
- int i;
-
- t = mktyvar(loc);
- for (i = 0; traits[like][i]; i++)
- settrait(t, traits[like][i]);
- return t;
-}
-
/* steals memb, funcs */
Trait *
mktrait(Srcloc loc, Node *name, Type *param,
@@ -217,7 +189,6 @@ mktygeneric(Srcloc loc, Node *name, Type **param, size_t nparam, Type *base)
t = mktype(loc, Tygeneric);
t->name = name;
t->nsub = 1;
- t->traits = bsdup(base->traits);
t->sub = xalloc(sizeof(Type *));
t->sub[0] = base;
t->gparam = param;
@@ -240,7 +211,6 @@ mktyname(Srcloc loc, Node *name, Type *base)
t = mktype(loc, Tyname);
t->name = name;
t->nsub = 1;
- t->traits = bsdup(base->traits);
t->sub = xalloc(sizeof(Type *));
t->sub[0] = base;
return t;
@@ -485,18 +455,6 @@ namefmt(char *buf, size_t len, Node *n)
}
int
-settrait(Type *t, Trait *c)
-{
- if (!t->traits)
- t->traits = mkbs();
- bsput(t->traits, c->uid);
- return 1;
-}
-
-int
-hastrait(Type *t, Trait *c) { return t->traits && bshas(t->traits, c->uid); }
-
-int
traitfmt(char *buf, size_t len, Type *t)
{
size_t i;
@@ -504,7 +462,7 @@ traitfmt(char *buf, size_t len, Type *t)
char *end;
char *sep;
- if (!t->traits || !bscount(t->traits))
+ if (!t->trneed || !bscount(t->trneed))
return 0;
p = buf;
@@ -512,11 +470,9 @@ traitfmt(char *buf, size_t len, Type *t)
p += bprintf(p, end - p, " :: ");
sep = "";
- for (i = 0; i < ntraittab; i++) {
- if (bshas(t->traits, i)) {
- p += bprintf(p, end - p, "%s%s", sep, namestr(traittab[i]->name));
- sep = ",";
- }
+ for (i = 0; bsiter(t->trneed, &i); i++) {
+ p += bprintf(p, end - p, "%s%s", sep, namestr(traittab[i]->name));
+ sep = ",";
}
return p - buf;
}
@@ -895,6 +851,89 @@ tyeq(void *a, void *b)
return eq;
}
+/* this doesn't walk through named types, so it can't recurse infinitely. */
+int
+tymatchrank(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 = tymatchrank(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 = tymatchrank(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 = tymatchrank(pat->arg[i], to->arg[i]);
+ if (q < 0)
+ return -1;
+ match += q;
+ }
+ break;
+ case Tyarray:
+ /* unsized arrays are ok */
+ if (pat->asize && to->asize) {
+ if (!!litvaleq(pat->asize->expr.args[0], to->asize->expr.args[0]))
+ return -1;
+ } else if (pat->asize != to->asize) {
+ return -1;
+ }
+ else return tymatchrank(pat->sub[0], to->sub[0]);
+ break;
+ default:
+ if (pat->nsub != to->nsub)
+ break;
+ if (pat->type == to->type)
+ match = 1;
+ for (i = 0; i < pat->nsub; i++) {
+ q = tymatchrank(pat->sub[i], to->sub[i]);
+ if (q < 0)
+ return -1;
+ match += q;
+ }
+ break;
+ }
+ return match;
+}
+
size_t
tyidfmt(char *buf, size_t sz, Type *ty)
{
@@ -1067,7 +1106,6 @@ disposableinit(Stab *st, Trait *tr)
void
tyinit(Stab *st)
{
- int i;
Type *ty;
Trait *tr;
@@ -1084,41 +1122,6 @@ tyinit(Stab *st)
#include "trait.def"
#undef Tc
- /* char::(numeric,integral) */
- traits[Tychar][0] = traittab[Tcnum];
- traits[Tychar][1] = traittab[Tcint];
-
- traits[Tybyte][0] = traittab[Tcnum];
- traits[Tybyte][1] = traittab[Tcint];
-
- /* <integer types>::(numeric,integral) */
- for (i = Tyint8; i < Tyflt32; i++) {
- traits[i][0] = traittab[Tcnum];
- traits[i][1] = traittab[Tcint];
- }
-
- /* <floats>::(numeric,floating) */
- traits[Tyflt32][0] = traittab[Tcnum];
- traits[Tyflt32][1] = traittab[Tcfloat];
- traits[Tyflt64][0] = traittab[Tcnum];
- traits[Tyflt64][1] = traittab[Tcfloat];
-
- /* @a*::(sliceable) */
- traits[Typtr][0] = traittab[Tcslice];
-
- /* @a[:]::(indexable,sliceable) */
- traits[Tyslice][0] = traittab[Tcidx];
- traits[Tyslice][1] = traittab[Tcslice];
- traits[Tyslice][2] = traittab[Tciter];
-
- /* @a[SZ]::(indexable,sliceable) */
- traits[Tyarray][0] = traittab[Tcidx];
- traits[Tyarray][1] = traittab[Tcslice];
- traits[Tyarray][2] = traittab[Tciter];
-
- /* @a::function */
- traits[Tyfunc][0] = traittab[Tcfunc];
-
/* Definining and registering the types has to go after we define the
* constraints, otherwise they will have no constraints set on them. */
#define Ty(t, n, stk) \
diff --git a/parse/use.c b/parse/use.c
index f694cb7..bb5d76a 100644
--- a/parse/use.c
+++ b/parse/use.c
@@ -230,11 +230,11 @@ typickle(FILE *fd, Type *ty)
/* FIXME: since we only support hardcoded traits, we just write
* out the set of them. we should write out the trait list a
* well */
- if (!ty->traits) {
+ if (!ty->trneed) {
wrint(fd, 0);
} else {
- wrint(fd, bscount(ty->traits));
- for (i = 0; bsiter(ty->traits, &i); i++) {
+ wrint(fd, bscount(ty->trneed));
+ for (i = 0; bsiter(ty->trneed, &i); i++) {
if (i < Ntraits)
wrint(fd, i | Builtinmask);
else
@@ -263,7 +263,7 @@ typickle(FILE *fd, Type *ty)
case Tyvar: die("Attempting to pickle %s. This will not work.\n", tystr(ty)); break;
case Tyname:
pickle(fd, ty->name);
- wrbool(fd, ty->issynth);
+ wrbool(fd, 0); /* TRFIX: fixme, compat */
wrint(fd, ty->narg);
for (i = 0; i < ty->narg; i++)
wrtype(fd, ty->arg[i]);
@@ -271,7 +271,7 @@ typickle(FILE *fd, Type *ty)
break;
case Tygeneric:
pickle(fd, ty->name);
- wrbool(fd, ty->issynth);
+ wrbool(fd, 0); /* TRFIX: fixme, compat */
wrint(fd, ty->ngparam);
for (i = 0; i < ty->ngparam; i++)
wrtype(fd, ty->gparam[i]);
@@ -335,8 +335,11 @@ rdtrait(FILE *fd, Trait **dest, Type *ty)
if (tid & Builtinmask) {
if (dest)
*dest = traittab[tid & ~Builtinmask];
- if (ty)
- settrait(ty, traittab[tid & ~Builtinmask]);
+ if (ty) {
+ if (!ty->trneed)
+ ty->trneed = mkbs();
+ bsput(ty->trneed, traittab[tid & ~Builtinmask]->uid);
+ }
} else {
traitfix = xrealloc(traitfix, (ntraitfix + 1) * sizeof(traitfix[0]));
traitfix[ntraitfix++] = (Traitfix){dest, ty, tid};
@@ -366,8 +369,12 @@ tyunpickle(FILE *fd)
if (ty->nsub > 0)
ty->sub = zalloc(ty->nsub * sizeof(Type *));
switch (ty->type) {
- case Tyunres: ty->name = unpickle(fd); break;
- case Typaram: ty->pname = rdstr(fd); break;
+ case Tyunres:
+ ty->name = unpickle(fd);
+ break;
+ case Typaram:
+ ty->pname = rdstr(fd);
+ break;
case Tystruct:
ty->nmemb = rdint(fd);
ty->sdecls = zalloc(ty->nmemb * sizeof(Node *));
@@ -389,7 +396,7 @@ tyunpickle(FILE *fd)
break;
case Tyname:
ty->name = unpickle(fd);
- ty->issynth = rdbool(fd);
+ /*TRFIX: ty->issynth = */ rdbool(fd);
ty->narg = rdint(fd);
ty->arg = zalloc(ty->narg * sizeof(Type *));
for (i = 0; i < ty->narg; i++)
@@ -398,7 +405,7 @@ tyunpickle(FILE *fd)
break;
case Tygeneric:
ty->name = unpickle(fd);
- ty->issynth = rdbool(fd);
+ /* TRFIX: ty->issynth = */ rdbool(fd);
ty->ngparam = rdint(fd);
ty->gparam = zalloc(ty->ngparam * sizeof(Type *));
for (i = 0; i < ty->ngparam; i++)
@@ -799,7 +806,7 @@ fixtypemappings(Stab *st)
/* check for duplicate type definitions */
for (i = 0; i < ntypefix; i++) {
t = htget(tidmap, itop(typefix[i].id));
- if ((t->type != Tyname && t->type != Tygeneric) || t->issynth)
+ if ((t->type != Tyname && t->type != Tygeneric))
continue;
old = tydedup(t);
if (!tyeq(t, old) && !isspecialization(t, old))
@@ -834,7 +841,7 @@ fixtraitmappings(Stab *st)
if (traitfix[i].dest)
*traitfix[i].dest = tr;
if (traitfix[i].type)
- settrait(traitfix[i].type, tr);
+ bsput(traitfix[i].type->trneed, tr->uid);
}
free(traitfix);
@@ -882,7 +889,6 @@ fiximplmappings(Stab *st)
if (getimpl(st, impl))
continue;
putimpl(st, impl);
- settrait(impl->impl.type, tr);
for (j = 0; j < impl->impl.ndecls; j++) {
putdcl(file->file.globls, impl->impl.decls[j]);
protomap(tr, impl->impl.type, impl->impl.decls[j]);
@@ -1008,8 +1014,6 @@ foundextlib:
htput(tidmap, itop(tid), ty);
/* fix up types */
if (ty->type == Tyname || ty->type == Tygeneric) {
- if (ty->issynth)
- break;
if (!streq(s->name, ty->name->name.ns))
ty->ishidden = 1;
if (!gettype(s, ty->name) && !ty->ishidden)
generated by cgit v1.1 at 2022-06-25 23:17:12 +0000