templates

4 files changed, 284 insertions, 28 deletions

diff --git a/src/cffc.hff b/src/cffc.hff
index 686de57..c8c90ac 100644
--- a/src/cffc.hff
+++ b/src/cffc.hff
@@ -36,9 +36,9 @@ enum TokT : i32 {
    ident,
    macident,
    gensym,
-   type,
    label,
    strify,
+   typearg,
    eof,
 }
 def NUM_KEYWORDS int = TokT:NUM_KEYWORDS;
@@ -68,8 +68,11 @@ struct AggField {
    ty *const Type,
    off usize,
 }
+
 struct EnumVal { name *const u8, i i64 }
 
+enum union TeplArg;
+
 struct Type {
    size  usize,
    align usize,
@@ -101,6 +104,7 @@ struct Type {
          id int,
          fwd bool,
          enumty *const Type,
+         tpargs [#]TeplArg,
          flds [#]AggField,
          decls *Env,
       },
@@ -228,6 +232,33 @@ struct Macro {
    cs [#]MacroCase
 }
 
+struct TeplParam {
+   name *const u8,
+   u enum union {
+      Ty,
+      Val *const Type,
+   }
+}
+
+enum union TeplArg {
+   Ty *const Type,
+   Val Tok,
+}
+
+struct TeplCache {
+   next *TeplCache,
+   args [#]TeplArg,
+   ty *const Type,
+}
+
+struct Tepl {
+   kind AggKind,
+   env *Env,
+   params [#]TeplParam,
+   toks [#]Tok,
+   cache *TeplCache,
+}
+
 struct Decl {
    name *const u8,
    loc Loc,
@@ -235,10 +266,11 @@ struct Decl {
    u enum union {
       Let Var,
       Static Var,
+      Ty *const Type,
       Def Expr,
       Fn Fn,
       Macro Macro,
-      Ty *const Type,
+      Tepl Tepl,
    },
    myenv *Env,
 }
@@ -253,6 +285,7 @@ struct Expan {
    toks [#]Tok,
    name *const u8,
    loc Loc,
+   tepl bool,
    idx int,
    peektok Option<Tok>
 }
diff --git a/src/fmt.cff b/src/fmt.cff
index 111809f..91f13d8 100644
--- a/src/fmt.cff
+++ b/src/fmt.cff
@@ -67,8 +67,8 @@ extern fn vpfmt(proc *fn(u8, *void) void, parg *void, fmt *const u8, ap va_list)
          p('$');
          ps(tok.u.ident);
          if quote { p('\'');  }
-      case :type;
-         pfmt(proc, parg, "%t", tok.ty);
+      case :typearg;
+         pfmt(proc, parg, "type parameter `%s' (%t)", tok.u.ident, tok.ty);
       case :eof;
          ps("<end of file>");
       case else
@@ -110,8 +110,10 @@ extern fn vpfmt(proc *fn(u8, *void) void, parg *void, fmt *const u8, ap va_list)
          ps("label");
       case :gensym;
          ps("gensym");
-      case :type;
-         ps("type argument");
+      case :typearg;
+         ps("type parameter");
+      case :eof;
+         ps("<end of file>");
       case else
          if t >= 0 and t < NUM_KEYWORDS {
             p('`');
@@ -175,6 +177,21 @@ extern fn vpfmt(proc *fn(u8, *void) void, parg *void, fmt *const u8, ap va_list)
          } else {
             ps("(anonymous)");
          }
+         if agg.tpargs.#ptr {
+            p('<');
+            for let i = 0z; i < agg.tpargs.#len; ++i {
+               switch agg.tpargs[i] {
+               case Ty ty;
+                 pfmt(proc, parg, "%t", ty);
+               case Val tok;
+                 pfmt(proc, parg, "%T", tok);
+               }
+               if i < agg.tpargs.#len - 1 {
+                  ps(", ");
+               }
+            }
+            ps("\e[1m>");
+         }
       case Enum e;
          if e.name {
             ps(e.name);
@@ -341,7 +358,7 @@ extern fn vdiag(P *Parser, loc Loc, kind *const u8, fmt *const u8, ap va_list) v
    for let ep = P.curexpan; ep; ep = ep.prev {
       if ep.name != #null and (i++ < 8 or ep.prev == #null or ep.prev.prev == #null) {
          efmt("* while expanding %s `%s' at %l\n",
-               "macro", ep.name, ep.loc);
+               ep.tepl ? "template" : "macro", ep.name, ep.loc);
          eprifileline(ep.loc);
       } else if ep.name != #null and i == 8 {
          efmt("    ... (some expansions omitted)\n");
diff --git a/src/libc.hff b/src/libc.hff
index 2778a79..a6c326c 100644
--- a/src/libc.hff
+++ b/src/libc.hff
@@ -29,6 +29,7 @@ def PATH_MAX = 4096;
 // string.h
 extern fn strlen(s *const u8) usize;
 extern fn strcmp(a *const u8, b *const u8) int;
+extern fn memcmp(*const void, *const void, usize) int;
 extern fn strcasecmp(a *const u8, b *const u8) int;
 extern fn memcpy(*void, *const void, usize) *void;
 extern fn strcpy(*u8, *const u8) *u8;
diff --git a/src/parse.cff b/src/parse.cff
index 0aa9fb9..96106c7 100644
--- a/src/parse.cff
+++ b/src/parse.cff
@@ -310,6 +310,9 @@ fn lex(P *Parser) Tok {
             foreach(arg, i, ep.args) {
                if streq(tok.u.ident, arg.name) {
                   ++P.expanno;
+                  if ep.tepl {
+                     arg.toks[0].loc = tok.loc;
+                  }
                   P.curexpan = memcpy(xmalloc(sizeof Expan), &Expan {
                      P.curexpan, {}, arg.toks,
                   }, sizeof Expan);
@@ -619,6 +622,7 @@ fn putdecl(P *Parser, eloc Loc, decl Decl) *Decl {
 ///////////////////
 
 fn parseexpr(P *Parser) Expr;
+fn pexbitarith(P *Parser) Expr;
 fn parsetype(P *Parser) *const Type;
 typedef DeclYielder *fn(*Decl, *void) void;
 fn parsedecls(P *Parser, yield DeclYielder, yarg *void, toplevel bool) void;
@@ -670,7 +674,10 @@ fn parseagg(P *Parser, kind AggKind, name *const u8, retdecl **Decl) *const Type
    let decl *Decl = name ? finddecl_noparent(P, name) : #null;
    if decl {
       switch decl.u {
-      case Ty ty; if !ty->is(:Agg) or !ty.u.Agg.fwd { decl = #null; }
+      case Ty ty;
+         if !ty->is(:Agg) or !ty.u.Agg.fwd or ty.u.Agg.kind != kind {
+            decl = #null;
+         }
       }
    }
    let ty = decl ? decl.u.Ty : interntype({ .u: :Agg { kind, name, id++ }});
@@ -778,15 +785,153 @@ fn findaggfield(ty *const Type, name *const u8) *AggField {
    return #null;
 }
 
+fn typematchestarg(targ *const Type, ty *const Type) bool {
+   if targ == ty {
+      return #t;
+   }
+   if typeof2(targ, ty) == #null {
+      return #f;
+   }
+   if targ->is(:Ptr) or ty->is(:Ptr) {
+      if !targ.u.Ptr.konst and ty.u.Ptr.konst {
+         return #f;
+      }
+   }
+   return #t;
+}
+
+fn parseexpandtepl(P *Parser, tepl *Tepl) *const Type {
+   let nparam = tepl.params.#len;
+   let tname = container_of(tepl, Decl, u.Tepl).name;
+   let args *ExpanArg = xcalloc(nparam, sizeof ExpanArg);
+   let ty *const Type = #null;
+   let i = 0z;
+   let tok Tok #?;
+   lexexpect(P, '<');
+   let loc = container_of(tepl, Decl, u.Tepl).loc;
+   while !lexmatch(P, &tok, '>') {
+      let par = &tepl.params[i];
+      let toks [#]Tok = (as(*Tok)xcalloc(sizeof Tok, 1))[0::1];
+      switch par.u {
+      case Ty;
+         toks[0] = { :typearg, P.curloc, parsetype(P), .u: { .ident: par.name }};
+      
+      case Val ty;
+         let ex = pexbitarith(P);
+         if !typematchestarg(ty, ex.ty) {
+            fatal(P, ex.loc, "template value argument mismatch (%t, expected %t)",
+                  ex.ty, ty);
+         }
+         fold(&ex);
+         switch ex.u {
+         case IntLit i;
+            toks[0] = { :int, ex.loc, ty, .u: { .int: i.i }};
+
+         case FloLit f;
+            toks[0] = { :flo, ex.loc, ty, .u: { .flo: f }};
+
+         case BoolLit b;
+            toks[0] = { :bool, ex.loc, ty, .u: { .bool: b }};
+
+         case NullLit;
+            toks[0] = { :null, ex.loc, ty};
+
+         case else
+            fatal(P, ex.loc, "expected constant expression");
+         }
+
+      }
+
+      args[i].name = par.name;
+      args[i].toks = toks;
+      ++i;
+      if !lexmatch(P, &tok, ',') {
+         lexexpect(P, '>');
+         break;
+      }
+   }
+   if i != nparam {
+      fatal(P, tok.loc, "invalid argument count for template `%s' (%d, expected %d)",
+            tname, i, nparam);
+   }
+   let tpargs [#]TeplArg = (as(*TeplArg)xcalloc(nparam, sizeof TeplArg))[0::nparam];
+   foreach(par, i, tepl.params) {
+      switch par.u {
+      case Ty;
+         tpargs[i] = :Ty(args[i].toks[0].ty);
+      case Val;
+         tpargs[i] = :Val(args[i].toks[0]);
+      }
+   }
+
+   let cache *TeplCache #?;
+
+   #'search
+   for cache = tepl.cache; cache; cache = cache.next {
+      for let i = 0; i < nparam; ++i {
+         // XXX memcmp reliable?
+         let arg = &tpargs[i];
+         switch cache.args[i] {
+         case Ty ty;
+            if ty != arg.Ty {
+               break #'search;
+            }
+         case Val tok;
+            let tok2 = arg.Val;
+            switch tok.t {
+            case :int;
+               if tok.u.int != tok2.u.int {
+                  break #'search;
+               }
+            case :flo;
+               if tok.u.flo != tok2.u.flo {
+                  break #'search;
+               }
+            case :bool;
+               if tok.u.bool != tok2.u.bool {
+                  break #'search;
+               }
+
+            case else
+               assert(#f, "unreachable");
+            }
+         }
+      }
+      free(tpargs.#ptr);
+      return cache.ty;
+   }
+   let env = mkenv(tepl.env, P.alloc);
+   with_tmpchange(P.curenv, env) {
+      let decl *Decl #?;
+      let expan Expan = { P.curexpan, args[0::nparam], tepl.toks, tname, tok.loc, #{tepl?} #t };
+      ++P.expanno;
+      P.curexpan = memcpy(xmalloc(sizeof Expan), &expan, sizeof Expan);
+      ty = parseagg(P, tepl.kind, tname, &decl);
+
+   }
+   envfree(env);
+   (as(*Type)ty).u.Agg.tpargs = tpargs;
+   cache = xcalloc(sizeof(*cache), 1);
+   cache.next = tepl.cache;
+   cache.args = tpargs;
+   cache.ty = ty;
+   tepl.cache = cache;
+   return ty;
+}
+
 fn xident2type(P *Parser, eloc Loc, name *const u8) *const Type {
    let decl = finddecl(P, name);
    if decl == #null {
       fatal(P, eloc, "`%s' is not defined", name);
    }
-   if decl.u.#tag != :Ty {
+   switch decl.u {
+   case Ty ty;
+      return ty;
+   case Tepl *tepl;
+      return parseexpandtepl(P, tepl);
+   case else
       fatal(P, eloc, "`%s' is not a type", name);
    }
-   return decl.u.Ty;
 }
 
 fn parsefnparams(P *Parser, variadic *bool, paramnames *Vec<*const u8>, paramtys *Vec<*const Type>) void {
@@ -864,6 +1009,9 @@ fn parsetype(P *Parser) *const Type {
    case lexmatch(P, &tok, :ident);
       return xident2type(P, tok.loc, tok.u.ident);
 
+   case lexmatch(P, &tok, :typearg);
+      return tok.ty;
+
    case lexmatch(P, &tok, :kw_typeof);
       lexexpect(P, '(');
       let ex = parseexpr(P);
@@ -883,21 +1031,6 @@ fn parsetype(P *Parser) *const Type {
 // Expressions Parsing //
 /////////////////////////
 
-fn typematchestarg(targ *const Type, ty *const Type) bool {
-   if targ == ty {
-      return #t;
-   }
-   if typeof2(targ, ty) == #null {
-      return #f;
-   }
-   if targ->is(:Ptr) or ty->is(:Ptr) {
-      if !targ.u.Ptr.konst and ty.u.Ptr.konst {
-         return #f;
-      }
-   }
-   return #t;
-}
-
 fn exprdup(alloc *Allocator, ex Expr) *Expr {
    return memcpy(alloc->alloc(sizeof(ex), alignof(ex)), &ex, sizeof(ex));
 }
@@ -1899,6 +2032,10 @@ fn pstiswitch(P *Parser, loc Loc, ex Expr) Stmt {
    return { loc, :ISwitch { ex, cs->move(P.alloc), f }};
 }
 
+fn psteuswitch(P *Parser, loc Loc, ex Expr) Stmt {
+   let ty = ex.ty;
+}
+
 fn pstswitch(P *Parser) Stmt {
    let loc = P.tokloc;
    let tok Tok #?;
@@ -1909,6 +2046,7 @@ fn pstswitch(P *Parser) Stmt {
       if ex.ty->is(:Int) or ex.ty->is(:Enum) {
          return pstiswitch(P, loc, ex);
       } else if ex.ty->is(:Agg) and ex.ty.u.Agg.kind == :EUnion {
+         return psteuswitch(P, loc, ex);
       } else {
          fatal(P, tok.loc, "invalid switch test expression type (%t)", ex.ty);
       }
@@ -2271,6 +2409,53 @@ fn parsemacro(P *Parser, name *const u8) *Decl {
    return putdecl(P, loc, { name, loc, .u: :Macro { cs->move(P.alloc) }});
 }
 
+fn parsetepl(P *Parser, kind AggKind, name *const u8) Tepl {
+   if envparent(P.curenv) {
+      fatal(P, P.tokloc, "templates can only defined be at top-level");   
+   }
+   let params Vec<TeplParam> = {};
+   let toks Vec<Tok> = {};
+   let tok Tok #?;
+   while (!lexmatch(P, &tok, '>')) {
+      let p TeplParam #?;
+      let name = lexexpects(P, :ident, "parameter name").u.ident;
+
+      p.name = name;
+      if (tok = lexpeek(P)).t == '>' or tok.t == ',' {
+         p.u = :Ty;
+      } else {
+         p.u = :Val(parsetype(P));
+      }
+
+      params->push(p);
+      
+      if !lexmatch(P, #null, ',') {
+         lexexpect(P, '>');
+         break;
+      }
+   }
+   tok = lexexpect(P, '{');
+   toks->push({'{'});
+   let bal = 1;
+   while bal != 0 {
+      tok = lex(P);
+      switch tok.t {
+      case '{'; ++bal; case '}'; --bal;
+      case :eof;
+         fatal(P, tok.loc, "unterminated template definiton");
+      case :ident;
+         vec_each(par, _, params) {
+            if streq(par.name, tok.u.ident) {
+               tok.t = :macident;
+            }
+         }
+      }
+      toks->push(tok);
+   }
+   
+   return { kind, P.curenv, params->move(P.alloc), toks->move(P.alloc), #null };
+}
+
 fn parsedecls(P *Parser, yield DeclYielder, yarg *void, toplevel bool) void {
    let tok = Tok { .loc: P.tokloc },
        decl *Decl = {},
@@ -2304,7 +2489,11 @@ fn parsedecls(P *Parser, yield DeclYielder, yarg *void, toplevel bool) void {
    case lexmatch(P, &tok, :kw_enum);
       if lexmatch(P, &tok, :kw_union) {
          let name = lexexpect(P, :ident).u.ident;
-         parseagg(P, :EUnion, name, &decl);
+         if !lexmatch(P, #null, '<') {
+            parseagg(P, :EUnion, name, &decl);
+         } else {
+            decl = putdecl(P, tok.loc, { name, tok.loc, .u: :Tepl(parsetepl(P, :EUnion, name)) });
+         }
       } else {
          let name = lexexpect(P, :ident).u.ident;
          let loc = P.tokloc;
@@ -2314,11 +2503,19 @@ fn parsedecls(P *Parser, yield DeclYielder, yarg *void, toplevel bool) void {
 
    case lexmatch(P, &tok, :kw_struct);
       let name = lexexpect(P, :ident).u.ident;
-      parseagg(P, :Struct, name, &decl);
+      if !lexmatch(P, #null, '<') {
+         parseagg(P, :Struct, name, &decl);
+      } else {
+         decl = putdecl(P, tok.loc, { name, tok.loc, .u: :Tepl(parsetepl(P, :Struct, name)) });
+      }
 
    case lexmatch(P, &tok, :kw_union);
       let name = lexexpect(P, :ident).u.ident;
-      parseagg(P, :Union, name, &decl);
+      if !lexmatch(P, #null, '<') {
+         parseagg(P, :Union, name, &decl);
+      } else {
+         decl = putdecl(P, tok.loc, { name, tok.loc, .u: :Tepl(parsetepl(P, :Union, name)) });
+      }
 
    case lexmatch(P, &tok, :kw_static);
       struct Arg {
@@ -2381,6 +2578,14 @@ fn parsedecls(P *Parser, yield DeclYielder, yarg *void, toplevel bool) void {
       decl = parsemacro(P, name);
 
    case else;
+      if (tok = lexpeek(P)).t == :ident {
+         let decl = finddecl(P, tok.u.ident);
+         if decl != #null and decl.u.#tag == :Macro {
+            lex(P);
+            parseexpandmacro(P, &decl.u.Macro);
+            return parsedecls(P, yield, yarg, toplevel);
+         }
+      }
       fatal(P, tok.loc, "expected declaration (near %qT)", tok);
    }