ref: 5192aa93538b09713e30be3063817b1068d415a6
parent: dd7fbc0240b45fafd4d380b328b196661ea750cf
author: Ori Bernstein <[email protected]>
date: Sat Dec 24 13:48:09 EST 2011
Move towards type constraints working.
--- a/parse/cstr.def
+++ b/parse/cstr.def
@@ -1,6 +1,6 @@
-Tc(Tcnum) /* arith ops */
-Tc(Tcint) /* bitwise ops */
-Tc(Tctest) /* if condition */
-Tc(Tcidx) /* indexable */
-Tc(Tcslice) /* sliceable */
-Tc(Ncstr)
+Tc(Tcnum, "tcnum") /* arith ops */
+Tc(Tcint, "tcint") /* bitwise ops */
+Tc(Tctest, "tctest") /* if condition */
+Tc(Tcidx, "tcidx") /* indexable */
+Tc(Tcslice, "tcslice") /* sliceable */
+Tc(Ncstr, "")
--- a/parse/ds.c
+++ b/parse/ds.c
@@ -3,6 +3,7 @@
#include <stdint.h>
#include <assert.h>
#include <limits.h>
+#include <string.h>
#include "parse.h"
@@ -32,6 +33,29 @@
return bs;
}
+Bitset *dupbs(Bitset *a)
+{
+ Bitset *bs;
+
+ bs = xalloc(sizeof(Bitset));
+ bs->nchunks = a->nchunks;
+ bs->chunks = xalloc(a->nchunks*sizeof(uint));
+ memcpy(bs->chunks, a->chunks, a->nchunks*sizeof(uint));
+ return bs;
+}
+
+int bscount(Bitset *bs)
+{
+ int i, j, n;
+
+ n = 0;
+ for (i = 0; i < bs->nchunks; i++)
+ for (j = 1; j < sizeof(uint)*CHAR_BIT; j++)
+ if (bs->chunks[i] & 1 << j)
+ n++;
+ return n;
+}
+
void delbs(Bitset *bs)
{
free(bs->chunks);
@@ -89,3 +113,4 @@
for (i = 0; i < a->nchunks; i++)
a->chunks[i] &= ~b->chunks[i];
}
+
--- a/parse/infer.c
+++ b/parse/infer.c
@@ -17,10 +17,10 @@
{
assert(t != NULL);
- if (typetab[t->tid]) {
+ if (tytab[t->tid]) {
printf ("%s => ", tystr(t));
- while (typetab[t->tid]) {
- t = typetab[t->tid];
+ while (tytab[t->tid]) {
+ t = tytab[t->tid];
printf("%s => ", tystr(t));
}
printf("nil\n");
@@ -28,7 +28,22 @@
return t;
}
+/* does b satisfy all the constraints of a? */
+static int cstrcheck(Type *a, Type *b)
+{
+ Bitset *s;
+ int n;
+ /* if b->cstrs \ a->cstrs == 0, then all of
+ * a's constraints are satisfied. */
+ s = dupbs(b->cstrs);
+ bsdiff(s, a->cstrs);
+ n = bscount(s);
+ delbs(s);
+
+ return n == 0;
+}
+
static void loaduses(Node *n)
{
int i;
@@ -108,7 +123,7 @@
if (a->type != b->type && a->type != Tyvar)
fatal(ctx->line, "%s incompatible with %s near %s", tystr(a), tystr(b), ctxstr(ctx));
- typetab[a->tid] = b;
+ tytab[a->tid] = b;
for (i = 0; i < b->nsub; i++) {
if (i >= a->nsub)
fatal(ctx->line, "%s incompatible with %s near %s", tystr(a), tystr(b), ctxstr(ctx));
@@ -299,6 +314,18 @@
{
}
+/* returns the final type for t, after all unifications
+ * and default constraint selections */
+static Type *tyfin(Type *t)
+{
+ t = tf(t);
+ if (t->type == Tyvar) {
+ if (hascstr(t, cstrtab[Tcint]) && cstrcheck(t, tytab[Tyint]))
+ return mkty(-1, Tyint);
+ }
+ return t;
+}
+
static void typesub(Node *n)
{
int i;
@@ -309,7 +336,7 @@
typesub(n->file.stmts[i]);
break;
case Ndecl:
- settype(n, tf(type(n)));
+ settype(n, tyfin(type(n)));
if (n->decl.init)
typesub(n->decl.init);
break;
@@ -329,7 +356,7 @@
typesub(n->loopstmt.body);
break;
case Nexpr:
- settype(n, tf(type(n)));
+ settype(n, tyfin(type(n)));
for (i = 0; i < n->expr.nargs; i++)
typesub(n->expr.args[i]);
break;
--- a/parse/main.c
+++ b/parse/main.c
@@ -44,6 +44,7 @@
}
for (i = optind; i < argc; i++) {
+ tyinit();
tokinit(argv[i]);
file = mkfile(argv[i]);
file->file.exports = mkstab(NULL);
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -39,7 +39,7 @@
} Ty;
typedef enum {
-#define Tc(c) c,
+#define Tc(c, n) c,
#include "cstr.def"
#undef Tc
} Tc;
@@ -65,7 +65,7 @@
char *name;
/* Contents of stab.
- * Types and values are in separate namespaces. */
+ * types and values are in separate namespaces. */
size_t ntypes;
Sym **types;
size_t nsyms;
@@ -83,7 +83,7 @@
Ty type;
int tid;
size_t nsub; /* For fnsub, tusub, sdecls, udecls, edecls. */
- Bitset cstrs; /* the type constraints matched on this type */
+ Bitset *cstrs; /* the type constraints matched on this type */
union {
Node *name; /* Tyname: unresolved name */
Type **fnsub; /* Tyfunc: return, args */
@@ -197,13 +197,15 @@
/* globals */
extern int debug;
extern char *filename;
-extern int ignorenl;
-extern Tok *curtok; /* the last token we tokenized */
-extern int line; /* the last line number we tokenized */
-extern Node *file; /* the current file we're compiling */
-extern Stab *curscope; /* the current scope to insert symbols into */
-extern Type **typetab; /* type -> type map used by inference. size maintained by type creation code */
+extern int ignorenl; /* are '\n' chars currently stmt separators? */
+extern Tok *curtok; /* the last token we tokenized */
+extern int line; /* the last line number we tokenized */
+extern Node *file; /* the current file we're compiling */
+extern Stab *curscope; /* the current scope to insert symbols into */
+extern Type **tytab; /* type -> type map used by inference. size maintained by type creation code */
extern int ntypes;
+extern Cstr **cstrtab; /* int -> cstr map */
+extern int ncstrs;
extern Type *littypes[]; /* literal type -> type map */
@@ -217,6 +219,7 @@
void bsunion(Bitset *a, Bitset *b);
void bsintersect(Bitset *a, Bitset *b);
void bsdiff(Bitset *a, Bitset *b);
+int bscount(Bitset *bs);
/* util functions */
void *zalloc(size_t size);
@@ -257,6 +260,8 @@
/* type manipulation */
int hascstr(Type *t, Cstr *c);
+int cstreq(Type *t, Cstr **cstrs, size_t len);
+int constrain(Type *t, Cstr *c);
char *tyfmt(char *buf, size_t len, Type *t);
char *tystr(Type *t);
--- a/parse/type.c
+++ b/parse/type.c
@@ -18,12 +18,11 @@
};
Type *littypes[Nlit] = {NULL,};
-Type **typetab = NULL;
+Type **tytab = NULL;
int ntypes;
-static Cstr **cstrtab;
-static int ncstr;
+Cstr **cstrtab;
+int ncstr;
-
static Typename typenames[] = {
{Tyvoid, "void"},
{Tychar, "char"},
@@ -41,15 +40,21 @@
{Tybad, NULL}
};
+static Cstr *tycstrs[Ntypes][4];
+
Type *mkty(int line, Ty ty)
{
Type *t;
+ int i;
t = zalloc(sizeof(Type));
t->type = ty;
t->tid = ntypes++;
+ tytab = xrealloc(tytab, ntypes*sizeof(Type*));
- typetab = xrealloc(typetab, ntypes*sizeof(Type*));
+ for(i = 0; tycstrs[ty][i]; i++)
+ constrain(t, tycstrs[ty][i]);
+
return t;
}
@@ -65,6 +70,7 @@
c->funcs = funcs;
c->nfuncs = nfuncs;
c->cid = ncstr++;
+
cstrtab = xrealloc(cstrtab, ncstr*sizeof(Cstr*));
return c;
}
@@ -198,6 +204,21 @@
return len - (end - p);
}
+int constrain(Type *t, Cstr *c)
+{
+ if (!t->cstrs)
+ t->cstrs = mkbs();
+ if (t->type != Tyvar && t->type != Typaram)
+ return 0;
+ bsput(t->cstrs, c->cid);
+ return 1;
+}
+
+int hascstr(Type *t, Cstr *c)
+{
+ return t->cstrs && bshas(t->cstrs, c->cid);
+}
+
static int cstrfmt(char *buf, size_t len, Type *t)
{
return 0;
@@ -308,51 +329,57 @@
return strdup(buf);
}
-static Type *tybuiltins[Ntypes];
-#if 0
-static Cstr *cstrbuiltins[Ncstr];
-#endif
void tyinit(void)
{
-#if 0
int i;
-#define Tc(c) \
- cstrbuiltins[c] = mkcstr(-1, c);
+
+#define Tc(c, n) \
+ mkcstr(-1, n, NULL, 0, NULL, 0);
#include "cstr.def"
#undef Tc
-#endif
#define Ty(t) \
- tybuiltins[t] = mkty(-1, t);
+ mkty(-1, t);
#include "types.def"
#undef Ty
-#if 0
/* bool :: tctest */
- constrain(tybuiltins[Tybool], cstrbuiltins[Tctest]);
+ tycstrs[Tybool][0] = cstrtab[Tctest];
/* <integer types> :: tcnum, tcint, tctest */
for (i = Tyint8; i < Tyfloat32; i++) {
- constrain(tybuiltins[i], cstrbuiltins[Tcnum]);
- constrain(tybuiltins[i], cstrbuiltins[Tcint]);
- constrain(tybuiltins[i], cstrbuiltins[Tctest]);
+ tycstrs[i][0] = cstrtab[Tcnum];
+ tycstrs[i][1] = cstrtab[Tcint];
+ tycstrs[i][2] = cstrtab[Tctest];
}
/* <floats> :: tcnum */
- constrain(tybuiltins[Tyfloat32], cstrbuiltins[Tcnum]);
- constrain(tybuiltins[Tyfloat64], cstrbuiltins[Tcnum]);
+ tycstrs[Tyfloat32][0] = cstrtab[Tcnum];
+ tycstrs[Tyfloat64][1] = cstrtab[Tcnum];
- /* @a* :: tctest, tcslice */
- constrain(tybuiltins[Typtr], cstrbuiltins[Tctest]);
- constrain(tybuiltins[Typtr], cstrbuiltins[Tcslice]);
+ /* @a* :: tctest[0] = tcslice */
+ tycstrs[Typtr][0] = cstrtab[Tctest];
+ tycstrs[Typtr][1] = cstrtab[Tcslice];
- /* @a[,] :: tctest, tcslice, tcidx */
- constrain(tybuiltins[Tyslice], cstrbuiltins[Tctest]);
- constrain(tybuiltins[Tyslice], cstrbuiltins[Tcslice]);
- constrain(tybuiltins[Tyslice], cstrbuiltins[Tcidx]);
+ /* @a[,] :: tctest[0] = tcslice[0] = tcidx */
+ tycstrs[Tyslice][0] = cstrtab[Tctest];
+ tycstrs[Tyslice][1] = cstrtab[Tcslice];
+ tycstrs[Tyslice][2] = cstrtab[Tcidx];
- /* enum */
- constrain(tybuiltins[Tyenum], cstrbuiltins[Tcint]);
- constrain(tybuiltins[Tyenum], cstrbuiltins[Tcnum]);
-#endif
+ /* enum :: tcint, tcnum */
+ tycstrs[Tyenum][0] = cstrtab[Tcint];
+ tycstrs[Tyenum][1] = cstrtab[Tcnum];
+
+ /* array :: tcidx, tcslice */
+ tycstrs[Tyarray][0] = cstrtab[Tcidx];
+ tycstrs[Tyarray][1] = cstrtab[Tcslice];
+
+ /* ptr :: tcslice, tctest */
+ tycstrs[Typtr][0] = cstrtab[Tcidx];
+ tycstrs[Typtr][1] = cstrtab[Tctest];
+
+ /* slice :: tcidx, tcslice, tctest */
+ tycstrs[Tyslice][0] = cstrtab[Tcidx];
+ tycstrs[Tyslice][1] = cstrtab[Tcslice];
+ tycstrs[Tyslice][1] = cstrtab[Tctest];
}