basic templates (generics)

6 files changed, 253 insertions, 52 deletions

diff --git a/bootstrap/all.h b/bootstrap/all.h
index 8c80fe4..aba2bc3 100644
--- a/bootstrap/all.h
+++ b/bootstrap/all.h
@@ -70,6 +70,8 @@ enum toktype {
    TKident,
    TKmacident,
    TKgensym,
+   TKtype,
+   TKexpr,
    TKeof,
 };
 #define NUM_KEYWORDS TKintlit
@@ -91,6 +93,8 @@ struct tok {
          const char *str;
          int strlen;
       };
+      const struct type *ty;
+      struct expr *ex;
    };
 };
 
@@ -121,8 +125,9 @@ struct parser {
       slice_t(struct expanarg) args;
       struct toktree toks;
       const char *name;
-      struct span spp,span;
+      struct span span;
       int idx;
+      bool tepl;
    } *curexpan; // macro expansions
    int expanno;
    const struct type *targty;
@@ -178,6 +183,13 @@ struct type {
             const struct type *ty;
          }) flds;
          slice_t(struct decl *) decls;
+         slice_t(struct teplarg {
+            bool typ;
+            union {
+               const struct type *ty;
+               struct tok tok;
+            };
+         }) tpargs;
          bool fwd;
          int id;
       } agg;
@@ -218,6 +230,7 @@ enum decltype {
    Dlet,
    Dstatic,
    Dmacro,
+   Dtepl,
 };
 
 struct decl {
@@ -235,9 +248,27 @@ struct decl {
          int id, fnid;
       } var;
       struct macro macro;
+      struct tepl {
+         enum decltype t;
+         enum typetype tkind;
+         const char *name;
+         struct env *env;
+         slice_t(struct teplparam) params;
+         struct teplcache {
+            struct teplcache *next;
+            slice_t(struct teplarg) args;
+            const struct type *ty;
+         } *cache;
+         struct toktree toks;
+      } tepl;
    };
 };
 
+struct teplparam {
+   const char *name;
+   bool typ;
+};
+
 struct env {
    struct env *parent;
    struct decls {
@@ -444,7 +475,7 @@ bswap64(u64 x) {
     (slice)->n = (v)->length)
 
 #define container_of(x, T, fld) \
-   (T *)((char *)(x) - offsetof(T, fld))
+   ((T *)((char *)(x) - offsetof(T, fld)))
 
 ///
 /////////////////////////////////
diff --git a/bootstrap/cgen.c b/bootstrap/cgen.c
index 91429ee..587f546 100644
--- a/bootstrap/cgen.c
+++ b/bootstrap/cgen.c
@@ -303,7 +303,7 @@ genstmt(struct stmt *stmt) {
          if (decl.externp)
             genstatic(1, decl.name, &decl.var);
          break;
-      case Dtype: case Dmacro:
+      case Dtype: case Dmacro: case Dtepl:
          break;
       }
       break;
@@ -550,8 +550,7 @@ gendecl(struct decl *decl, bool toplevel) {
    case Dlet:
       assert(!toplevel);
       break;
-   case Dtype:
-   case Dmacro:
+   case Dtype: case Dtepl: case Dmacro:
       break;
    }
 }
diff --git a/bootstrap/dump.c b/bootstrap/dump.c
index 84c4bbe..dae457a 100644
--- a/bootstrap/dump.c
+++ b/bootstrap/dump.c
@@ -3,6 +3,8 @@
 
 static void
 pritype(const struct type *ty) {
+   const char *kind;
+
    assert(ty);
    if (ty->konst)
       epri("const ");
@@ -44,13 +46,25 @@ pritype(const struct type *ty) {
       epri("%s", ty->enu.name ? ty->enu.name : "(anonymous enum)");
       break;
    case TYstruct:
-      epri("%s", ty->agg.name ? ty->agg.name : "(anonymous struct)");
-      break;
+      kind = "struct";
+      goto agg;
    case TYunion:
-      epri("%s", ty->agg.name ? ty->agg.name : "(anonymous union)");
-      break;
+      kind = "union";
+      goto agg;
    case TYeunion:
-      epri("%s", ty->agg.name ? ty->agg.name : "(anonymous tagged union)");
+      kind = "tagged union";
+   agg:
+      epri("%s", ty->agg.name ? ty->agg.name : "(anonymous %s)", kind);
+      if (ty->agg.tpargs.n) {
+         epri("<");
+         int n = ty->agg.tpargs.n;
+         for (int i = 0; i < n; ++i) {
+            epri("%t", ty->agg.tpargs.d[i].ty);
+            if (i < n - 1)
+               epri(", ");
+         }
+         epri("%bc", '>');
+      }
       break;
    }
 }
@@ -141,6 +155,10 @@ tok2str(struct tok tok) {
       }
       buf[i] = '\0';
       strcat(buf, "'");
+   } else if (tok.t == TKtype) {
+      return "<type parameter>";
+   } else if (tok.t == TKexpr) {
+      return "<const parameter>";
    } else {
       snprintf(buf, sizeof buf - 1, "`%c'", tok.t);
    }
@@ -417,6 +435,8 @@ dumpdecl(const struct decl *decl, int ws) {
       }
       epri("}\n");
       break;
+   case Dtepl:
+      assert(0);
    }
 }
 
diff --git a/bootstrap/parse.c b/bootstrap/parse.c
index 7ec725d..4094edb 100644
--- a/bootstrap/parse.c
+++ b/bootstrap/parse.c
@@ -256,22 +256,6 @@ readstrlit(struct parser *P, u8 delim, char *s, size_t n) {
 
 #define MAX_MACROEXPAND_ITER 100
 
-/*
-// guard used at macro arg expansion to avoid it expanding into itself, e.g.:
-//    defmacro foo(x,y) [(x+y)]
-//    let x, y ...;
-//    foo(x,y)
-// would cause infinite recursion otherwise
-static bool
-ismacrodupe(struct parser *P, struct toktree toks) {
-   for (struct expan *ep = P->curexpan; ep; ep = ep->prev) {
-      if (ep->toks.d == toks.d)
-         return 1;
-   }
-   return 0;
-}
-*/
-
 static struct tok
 lex(struct parser *P) {
    u8 c;
@@ -584,6 +568,103 @@ mkslicetype(const struct type *child) {
    });
 }
 
+static struct expr *
+exprdup(struct expr ex) {
+   return memcpy(xmalloc(sizeof ex), &ex, sizeof ex);
+}
+
+static const struct type *parseagg(struct parser *P, const char *name, int kind, struct decl **retdecl);
+
+static const struct type *
+parseexpandtepl(struct parser *P, struct tepl *tepl) {
+   struct expanarg *args = xcalloc(tepl->params.n, sizeof *args);
+   struct expan expan = { P->curexpan, .name = tepl->name };
+   struct tok tok;
+   const struct type *ty = NULL; 
+   int i = 0;
+
+   expan.span = container_of(tepl, struct decl, tepl)->span;
+   expan.tepl = 1;
+   while (!lexmatch(P, &tok, '>')) {
+      struct teplparam *par = tepl->params.d + i;
+      struct toktree toks = {{ xmalloc(sizeof (struct tok)), 1 }};
+   
+      if (par->typ) {
+         toks.d->span = P->curspan;
+         const struct type *ty = parsetype(P);
+         toks.d->t = TKtype;
+         toks.d->ty = ty;
+      } else {
+         struct expr ex = parseexpr(P);
+         if (!fold(&ex))
+            fatal(P, ex.span, "template parameter is not constant expression");
+         toks.d->span = P->tokspan;
+         toks.d->t = TKexpr;
+         toks.d->ex = exprdup(ex);
+      }
+
+      args[i].name = par->name;
+      args[i].toks = toks;
+
+      ++i;
+      if (!lexmatch(P, &tok, ',')) {
+         lexexpect(P, '>');
+         break;
+      }
+   }
+   if (i != tepl->params.n)
+      fatal(P, tok.span, "invalid argument count for template `%s'", tepl->name);
+
+   slice_t(struct teplarg) tpargs = {
+      xmalloc(tepl->params.n * sizeof(struct teplarg)),
+      tepl->params.n
+   };
+   struct teplcache *cache;
+ 
+   for (int i = 0; i < tepl->params.n; ++i) {
+      if (tepl->params.d[i].typ) {
+         tpargs.d[i].typ = 1;
+         tpargs.d[i].ty = args[i].toks.d[0].ty;
+      } else {
+         assert(0);
+      }
+   }
+
+   // TODO hashmap ?
+   for (cache = tepl->cache; cache; cache = cache->next) {
+      for (int i = 0; i < tepl->params.n; ++i) {
+         if (tepl->params.d[i].typ) {
+            if (cache->args.d[i].ty != tpargs.d[i].ty)
+               goto next;
+         } else {
+            assert(0);
+         }
+      }
+      free(tpargs.d);
+      return cache->ty;
+   next:;
+   }
+
+   struct env env = { tepl->env };
+   WITH_TMPCHANGE(struct env *, P->curenv, &env) {
+      struct decl *decl;
+      expan.args.d = args;
+      expan.args.n = i;
+      expan.toks = tepl->toks;
+      ++P->expanno;
+      P->curexpan = memcpy(xmalloc(sizeof expan), &expan, sizeof expan);
+      ty = parseagg(P, tepl->name, tepl->tkind, &decl);
+   }
+   memcpy(&((struct type *)ty)->agg.tpargs, &tpargs, sizeof tpargs);
+   cache = xcalloc(sizeof *cache, 1);
+   cache->next = tepl->cache;
+   memcpy(&cache->args, &tpargs, sizeof tpargs);
+   cache->ty = ty;
+   tepl->cache = cache;
+
+   return ty;
+}
+
 static const struct type *
 parsetype(struct parser *P) {
    struct tok tok;
@@ -642,11 +723,17 @@ parsetype(struct parser *P) {
       const struct decl *decl = finddecl(P, tok.str);
       if (!decl)
          fatal(P, P->tokspan, "%T is not defined", tok);
-      if (decl->t != Dtype)
+      if (decl->t == Dtype) {
+         return decl->ty;
+      } else if (decl->t == Dtepl && decl->tepl.t == Dtype) {
+         lexexpect(P, '<');
+         return parseexpandtepl(P, (struct tepl *)&decl->tepl);         
+      } else
          fatal(P, P->tokspan, "%T is not a type", tok);
-      return decl->ty;
    } else if (lexmatch(P, &tok, TKkw_fn)) {
       return parsefntype(P);
+   } else if (lexmatch(P, &tok, TKtype)) {
+      return tok.ty;
    }
    fatal(P, P->tokspan, "expected type (near %T)", tok);
 }
@@ -683,12 +770,6 @@ islvalue(const struct expr *ex) {
 
 /** Expression parsing **/
 
-static struct expr *
-exprdup(struct expr ex) {
-   return memcpy(xmalloc(sizeof ex), &ex, sizeof ex);
-}
-
-
 static struct blockstmt parseblock0(struct parser *P);
 static struct stmt parseblock(struct parser *P);
 static void parseexpandmacro(struct parser *P, const struct macro *macro);
@@ -1852,10 +1933,8 @@ parseexpandmacro(struct parser *P, const struct macro *macro) {
      for (;;) { 
          tok = lex(P);
          switch (tok.t) {
-         case '[': ++bkbal; break;
-         case ']': --bkbal; break;
-         case '{': ++bcbal; break;
-         case '}': --bcbal; break;
+         case '[': ++bkbal; break; case ']': --bkbal; break;
+         case '{': ++bcbal; break; case '}': --bcbal; break;
          case '(': ++pabal; break;
          case ')':
             if (--pabal >= 0)
@@ -2150,12 +2229,9 @@ parsemacrocase(struct parser *P) {
    while (bkbal || pabal || bcbal) {
       tok = lex(P);
       switch (tok.t) {
-      case '(': ++pabal; break;
-      case ')': --pabal; break;
-      case '[': ++bkbal; break;
-      case ']': --bkbal; break;
-      case '{': ++bcbal; break;
-      case '}': --bcbal; break;
+      case '(': ++pabal; break; case ')': --pabal; break;
+      case '[': ++bkbal; break; case ']': --bkbal; break;
+      case '{': ++bcbal; break; case '}': --bcbal; break;
       case TKeof:
          fatal(P, espan, "unterminated macro definition");
       }
@@ -2417,6 +2493,58 @@ doimport(struct parser *P, const char *path) {
    return cf;    
 }
 
+static struct tepl
+parseaggtepl(struct parser *P, int kind, const char *name) {
+   struct tepl tepl = {Dtype, kind, name};
+   vec_t(struct teplparam) params = {0};
+   struct tok tok;
+   vec_t(struct tok) toks = {0};
+
+   while (!lexmatch(P, &tok, '>')) {
+      struct teplparam p;
+      const char *name = lexexpects(P, TKident, "parameter name").str;
+
+      p.name = name;
+      if ((tok = lexpeek(P)).t == '>' || tok.t == ',') {
+         p.typ = 1;
+      } else {
+         assert(0);
+      }
+
+      vec_push(&params, p);
+      
+      if (!lexmatch(P, NULL, ',')) {
+         lexexpect(P, '>');
+         break;
+      }
+   }
+   lexexpect(P, '{');
+   vec_push(&toks, (struct tok){'{'});
+
+   int pabal = 0, // ( ) parens balance
+       bkbal = 0, // [ ] brackets ..
+       bcbal = 1; // { } braces ..
+
+  while (pabal || bkbal || bcbal) { 
+      tok = lex(P);
+      switch (tok.t) {
+      case '[': ++bkbal; break; case ']': --bkbal; break;
+      case '{': ++bcbal; break; case '}': --bcbal; break;
+      case '(': ++pabal; break; case ')': --pabal; break;
+      }
+      if (tok.t == TKident)
+         for (int i = 0; i < params.length; ++i)
+            if (!strcmp(params.data[i].name, tok.str))
+               tok.t = TKmacident;
+      vec_push(&toks, tok);
+   }
+
+   tepl.env = P->curenv;
+   vec_slice_cpy(&tepl.params, &params);
+   vec_slice_cpy(&tepl.toks, &toks);
+   return tepl;
+}
+
 struct staticvaryarg {
    struct parser *P;
    bool externp, toplevel;
@@ -2490,14 +2618,22 @@ parsedecl(decl_yielder_t yield, void *yarg, struct parser *P, bool toplevel) {
       decl.macro.name = name;
    } else if (lexmatch(P, &tok, TKkw_enum)) {
       if (externp) fatal(P, tok.span, "enum cannot be `extern'");
+      decl.t = Dtype;
       decl.name = lexexpects(P, TKident, "enum name").str;
       decl.ty = parseenum(P, decl.name);
    } else if (lexmatch(P, &tok, TKkw_struct)) {
       kind = TYstruct;
       if (externp) fatal(P, tok.span, "struct cannot be `extern'");
    agg:
-      decl.name = lexexpects(P, TKident, "struct name").str;
-      decl.ty = parseagg(P, decl.name, kind, &decl2);
+      decl.span = tok.span;
+      decl.name = lexexpects(P, TKident, "type name").str;
+      if (!lexmatch(P, NULL, '<')) {
+         decl.t = Dtype;
+         decl.ty = parseagg(P, decl.name, kind, &decl2);
+      } else {
+         decl.t = Dtepl;
+         decl.tepl = parseaggtepl(P, kind, decl.name);
+      }
       if (decl2) goto noput;
    } else if (lexmatch(P, &tok, TKkw_union)) {
       if (externp) fatal(P, tok.span, "union cannot be `extern'");
diff --git a/bootstrap/test2.cff b/bootstrap/test2.cff
index ee24d45..66603ba 100644
--- a/bootstrap/test2.cff
+++ b/bootstrap/test2.cff
@@ -1,6 +1,21 @@
 import "libc.hff";
 
-struct Node {
-   next *Node,
-   value int,
+struct Node<T> {
+   link *Node,
+   value T,
+
+   fn ok(self Node) void {
+   }
+}
+
+extern fn main() void {
+   let n Node<int> = {#null, 0};
+   let n Node<int> = {&n, 1};
+
+   printf("n %d\n", n.value);
+   printf("n link %d\n", n.link.value);
+
+   let x Node<f32> = {};
+   n->ok();
+   x->ok();
 }
diff --git a/bootstrap/util.c b/bootstrap/util.c
index 43aa1b4..20f1772 100644
--- a/bootstrap/util.c
+++ b/bootstrap/util.c
@@ -118,7 +118,7 @@ eprifileline(struct span span) {
    }
    // line begin
    for (i = span.idx; i > 0 && src[i] != '\n'; --i) ;
-   ++i;
+   if (i > 0) ++i;
 
    // line end
    for (j = span.idx; src[j] && src[j] != '\n'; ++j) ;
@@ -148,8 +148,8 @@ fatal(struct parser *P, struct span span, const char *fmt, ...) {
    for (struct expan *ep = P->curexpan; ep; ep = ep->prev, ++i) {
       if (ep->name && (i < 8 || !ep->prev || !ep->prev->prev)) {
          span = ep->span;
-         epri("* while expanding macro `%s' at %s:%d:%d\n",
-               ep->name,
+         epri("* while expanding %s `%s' at %s:%d:%d\n",
+               ep->tepl ? "template" : "macro", ep->name,
                fileid2path(ep->span.fileid), span.line, span.col);
          eprifileline(span);
       } else if (ep->name && i == 10) {