basic templates (generics)

1 files changed, 172 insertions, 36 deletions

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'");