shithub: mc

--- 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];