shithub: mc

Download patch

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