378 parse/infer.c
View file

Large diffs are not rendered by default.

9 parse/parse.h
View file
@@ -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);
135 parse/specialize.c
View file
@@ -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;
2 parse/trait.def
View file
@@ -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 */
171 parse/type.c
View file
@@ -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;
@@ -484,18 +454,6 @@ namefmt(char *buf, size_t len, Node *n)
return len - (end - p);
}

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)
{
@@ -504,19 +462,17 @@ 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;
end = p + len;

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) \
36 parse/use.c
View file
@@ -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,15 +263,15 @@ 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]);
wrtype(fd, ty->sub[0]);
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 @@ loaduse(char *path, FILE *f, Stab *st, Vis vis)
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)