fix #1858; Add support for generic templates and macros

Implementation notes:
Just after overload resolution, the resolved generic params will be added to the
call expression to be later processed in evalTemplate and evalMacroCall. These
procs have been modified to handle the increased number of parameters, but one
remaining issue is that immediate templates and macros don't go through the same
process. The next commit will outlaw the use of generic parameters with such macros.

6 files changed, 108 insertions, 43 deletions

diff --git a/compiler/ast.nim b/compiler/ast.nim
index 883b68d71..a071060d4 100644
--- a/compiler/ast.nim
+++ b/compiler/ast.nim
@@ -1341,6 +1341,10 @@ proc skipTypes*(t: PType, kinds: TTypeKinds): PType =
   result = t
   while result.kind in kinds: result = lastSon(result)
 
+proc safeSkipTypes*(t: PType, kinds: TTypeKinds): PType =
+  result = if t != nil: t.skipTypes(kinds)
+           else: nil
+
 proc isGCedMem*(t: PType): bool {.inline.} =
   result = t.kind in {tyString, tyRef, tySequence} or
            t.kind == tyProc and t.callConv == ccClosure
diff --git a/compiler/evaltempl.nim b/compiler/evaltempl.nim
index 78cc691c0..ecb898d8a 100644
--- a/compiler/evaltempl.nim
+++ b/compiler/evaltempl.nim
@@ -25,16 +25,22 @@ proc copyNode(ctx: TemplCtx, a, b: PNode): PNode =
   if ctx.instLines: result.info = b.info
 
 proc evalTemplateAux(templ, actual: PNode, c: var TemplCtx, result: PNode) =
+  template handleParam(param) =
+    let x = param
+    if x.kind == nkArgList:
+      for y in items(x): result.add(y)
+    else:
+      result.add copyTree(x)
+
   case templ.kind
   of nkSym:
     var s = templ.sym
     if s.owner.id == c.owner.id:
-      if s.kind == skParam:
-        let x = actual.sons[s.position]
-        if x.kind == nkArgList:
-          for y in items(x): result.add(y)
-        else:
-          result.add copyTree(x)
+      case s.kind
+      of skParam:
+        handleParam actual.sons[s.position]
+      of skGenericParam:
+        handleParam actual.sons[s.owner.typ.len + s.position - 1]
       else:
         internalAssert sfGenSym in s.flags
         var x = PSym(idTableGet(c.mapping, s))
@@ -56,21 +62,31 @@ proc evalTemplateAux(templ, actual: PNode, c: var TemplCtx, result: PNode) =
 proc evalTemplateArgs(n: PNode, s: PSym): PNode =
   # if the template has zero arguments, it can be called without ``()``
   # `n` is then a nkSym or something similar
-  var a: int
-  case n.kind
-  of nkCall, nkInfix, nkPrefix, nkPostfix, nkCommand, nkCallStrLit:
-    a = sonsLen(n)
-  else: a = 0
-  var f = s.typ.sonsLen
-  if a > f: globalError(n.info, errWrongNumberOfArguments)
+  var totalParams = case n.kind
+    of nkCall, nkInfix, nkPrefix, nkPostfix, nkCommand, nkCallStrLit: <n.len
+    else: 0
+
+  var
+    genericParams = s.ast[genericParamsPos].len
+    expectedRegularParams = <s.typ.len
+    givenRegularParams = totalParams - genericParams
+
+  if totalParams > expectedRegularParams + genericParams:
+    globalError(n.info, errWrongNumberOfArguments)
 
   result = newNodeI(nkArgList, n.info)
-  for i in countup(1, f - 1):
-    var arg = if i < a: n.sons[i] else: copyTree(s.typ.n.sons[i].sym.ast)
-    if arg == nil or arg.kind == nkEmpty:
+  for i in 1 .. givenRegularParams:
+    result.addSon n.sons[i]
+
+  for i in givenRegularParams+1 .. expectedRegularParams:
+    let default = s.typ.n.sons[i].sym.ast
+    if default.kind == nkEmpty:
       localError(n.info, errWrongNumberOfArguments)
-    addSon(result, arg)
+    result.addSon default.copyTree
 
+  for i in 1 .. genericParams:
+    result.addSon n.sons[givenRegularParams + i]
+  
 var evalTemplateCounter* = 0
   # to prevent endless recursion in templates instantiation
 
diff --git a/compiler/semcall.nim b/compiler/semcall.nim
index a712cc195..961c61c57 100644
--- a/compiler/semcall.nim
+++ b/compiler/semcall.nim
@@ -283,8 +283,21 @@ proc semResolvedCall(c: PContext, n: PNode, x: TCandidate): PNode =
     if containsGenericType(result.typ) or x.fauxMatch == tyUnknown:
       result.typ = newTypeS(x.fauxMatch, c)
     return
-  if finalCallee.ast.sons[genericParamsPos].kind != nkEmpty:
-    finalCallee = generateInstance(c, x.calleeSym, x.bindings, n.info)
+  let gp = finalCallee.ast.sons[genericParamsPos]
+  if gp.kind != nkEmpty:
+    if x.calleeSym.kind notin {skMacro, skTemplate}:
+      finalCallee = generateInstance(c, x.calleeSym, x.bindings, n.info)
+    else:
+      # For macros and templates, the resolved generic params
+      # are added as normal params.
+      for s in instantiateGenericParamList(c, gp, x.bindings):
+        case s.kind
+          of skConst:
+            x.call.add s.ast
+          of skType:
+            x.call.add newSymNode(s, n.info)
+          else:
+            internalAssert false
   result = x.call
   instGenericConvertersSons(c, result, x)
   result.sons[0] = newSymNode(finalCallee, result.sons[0].info)
diff --git a/compiler/seminst.nim b/compiler/seminst.nim
index 81a4465c5..dd60e0881 100644
--- a/compiler/seminst.nim
+++ b/compiler/seminst.nim
@@ -10,14 +10,10 @@
 # This module implements the instantiation of generic procs.
 # included from sem.nim
 
-proc instantiateGenericParamList(c: PContext, n: PNode, pt: TIdTable,
-                                 entry: var TInstantiation) = 
-  if n.kind != nkGenericParams: 
-    internalError(n.info, "instantiateGenericParamList; no generic params")
-  newSeq(entry.concreteTypes, n.len)
+iterator instantiateGenericParamList(c: PContext, n: PNode, pt: TIdTable): PSym =
+  internalAssert n.kind == nkGenericParams
   for i, a in n.pairs:
-    if a.kind != nkSym: 
-      internalError(a.info, "instantiateGenericParamList; no symbol")
+    internalAssert a.kind == nkSym
     var q = a.sym
     if q.typ.kind notin {tyTypeDesc, tyGenericParam, tyStatic, tyIter}+tyTypeClasses:
       continue
@@ -42,8 +38,7 @@ proc instantiateGenericParamList(c: PContext, n: PNode, pt: TIdTable,
       #t = ReplaceTypeVarsT(cl, t)
     s.typ = t
     if t.kind == tyStatic: s.ast = t.n
-    addDecl(c, s)
-    entry.concreteTypes[i] = t
+    yield s
 
 proc sameInstantiation(a, b: TInstantiation): bool =
   if a.concreteTypes.len == b.concreteTypes.len:
@@ -196,7 +191,7 @@ proc generateInstance(c: PContext, fn: PSym, pt: TIdTable,
   ## The `pt` parameter is a type-unsafe mapping table used to link generic
   ## parameters to their concrete types within the generic instance.
   # no need to instantiate generic templates/macros:
-  if fn.kind in {skTemplate, skMacro}: return fn
+  internalAssert fn.kind notin {skMacro, skTemplate}
   # generates an instantiated proc
   if c.instCounter > 1000: internalError(fn.ast.info, "nesting too deep")
   inc(c.instCounter)
@@ -213,12 +208,18 @@ proc generateInstance(c: PContext, fn: PSym, pt: TIdTable,
   result.ast = n
   pushOwner(result)
   openScope(c)
-  internalAssert n.sons[genericParamsPos].kind != nkEmpty
+  let gp = n.sons[genericParamsPos]
+  internalAssert gp.kind != nkEmpty
   n.sons[namePos] = newSymNode(result)
   pushInfoContext(info)
   var entry = TInstantiation.new
   entry.sym = result
-  instantiateGenericParamList(c, n.sons[genericParamsPos], pt, entry[])
+  newSeq(entry.concreteTypes, gp.len)
+  var i = 0
+  for s in instantiateGenericParamList(c, gp, pt):
+    addDecl(c, s)
+    entry.concreteTypes[i] = s.typ
+    inc i
   pushProcCon(c, result)
   instantiateProcType(c, pt, result, info)
   n.sons[genericParamsPos] = ast.emptyNode
diff --git a/compiler/vm.nim b/compiler/vm.nim
index ad0d3b0a1..4072ed765 100644
--- a/compiler/vm.nim
+++ b/compiler/vm.nim
@@ -1417,12 +1417,20 @@ proc evalStaticStmt*(module: PSym, e: PNode, prc: PSym) =
 proc setupCompileTimeVar*(module: PSym, n: PNode) =
   discard evalConstExprAux(module, nil, n, emStaticStmt)
 
-proc setupMacroParam(x: PNode): PNode =
-  result = x
-  if result.kind in {nkHiddenSubConv, nkHiddenStdConv}: result = result.sons[1]
-  result = canonValue(result)
-  result.flags.incl nfIsRef
-  result.typ = x.typ
+proc setupMacroParam(x: PNode, typ: PType): TFullReg =
+  case typ.kind
+  of tyStatic:
+    putIntoReg(result, x)
+  of tyTypeDesc:
+    putIntoReg(result, x)
+  else:
+    result.kind = rkNode
+    var n = x
+    if n.kind in {nkHiddenSubConv, nkHiddenStdConv}: n = n.sons[1]
+    n = n.canonValue
+    n.flags.incl nfIsRef
+    n.typ = x.typ
+    result.node = n
 
 var evalMacroCounter: int
 
@@ -1442,6 +1450,7 @@ proc evalMacroCall*(module: PSym, n, nOrig: PNode, sym: PSym): PNode =
 
   c.callsite = nOrig
   let start = genProc(c, sym)
+  # c.echoCode start
 
   var tos = PStackFrame(prc: sym, comesFrom: 0, next: nil)
   let maxSlots = sym.offset
@@ -1457,9 +1466,14 @@ proc evalMacroCall*(module: PSym, n, nOrig: PNode, sym: PSym): PNode =
   tos.slots[0].kind = rkNode
   tos.slots[0].node = newNodeIT(nkEmpty, n.info, sym.typ.sons[0])
   # setup parameters:
-  for i in 1 .. < min(tos.slots.len, L):
-    tos.slots[i].kind = rkNode
-    tos.slots[i].node = setupMacroParam(n.sons[i])
+  for i in 1.. <sym.typ.len:
+    tos.slots[i] = setupMacroParam(n.sons[i], sym.typ.sons[i])
+
+  let gp = sym.ast[genericParamsPos]
+  for i in 0 .. <gp.len:
+    let idx = sym.typ.len + i
+    tos.slots[idx] = setupMacroParam(n.sons[idx], gp[i].sym.typ)
+
   # temporary storage:
   #for i in L .. <maxSlots: tos.slots[i] = newNode(nkEmpty)
   result = rawExecute(c, start, tos).regToNode
diff --git a/compiler/vmgen.nim b/compiler/vmgen.nim
index 9a3fc260a..7b574bccc 100644
--- a/compiler/vmgen.nim
+++ b/compiler/vmgen.nim
@@ -164,7 +164,8 @@ proc getSlotKind(t: PType): TSlotKind =
 const
   HighRegisterPressure = 40
 
-proc getTemp(c: PCtx; typ: PType): TRegister =
+proc getTemp(c: PCtx; tt: PType): TRegister =
+  let typ = tt.skipTypes({tyStatic})
   let c = c.prc
   # we prefer the same slot kind here for efficiency. Unfortunately for
   # discardable return types we may not know the desired type. This can happen
@@ -685,7 +686,7 @@ proc genConv(c: PCtx; n, arg: PNode; dest: var TDest; opc=opcConv) =
   if dest < 0: dest = c.getTemp(n.typ)
   c.gABC(n, opc, dest, tmp)
   c.gABx(n, opc, 0, genType(c, n.typ))
-  c.gABx(n, opc, 0, genType(c, arg.typ))
+  c.gABx(n, opc, 0, genType(c, arg.typ.skipTypes({tyStatic})))
   c.freeTemp(tmp)
 
 proc genCard(c: PCtx; n: PNode; dest: var TDest) =
@@ -1085,7 +1086,8 @@ proc genAddrDeref(c: PCtx; n: PNode; dest: var TDest; opc: TOpcode;
     c.freeTemp(tmp)
 
 proc whichAsgnOpc(n: PNode): TOpcode =
-  case n.typ.skipTypes(abstractRange-{tyTypeDesc}).kind
+  let toSkip = abstractRange-{tyTypeDesc}
+  case n.typ.skipTypes(toSkip).kind
   of tyBool, tyChar, tyEnum, tyOrdinal, tyInt..tyInt64, tyUInt..tyUInt64:
     opcAsgnInt
   of tyString, tyCString:
@@ -1559,6 +1561,11 @@ proc gen(c: PCtx; n: PNode; dest: var TDest; flags: TGenFlags = {}) =
         c.gABx(n, opcLdConst, dest, lit)
     of skType:
       genTypeLit(c, s.typ, dest)
+    of skGenericParam:
+      if c.prc.sym.kind == skMacro:
+        genRdVar(c, n, dest, flags)
+      else:
+        internalError(n.info, "cannot generate code for: " & s.name.s)
     else:
       internalError(n.info, "cannot generate code for: " & s.name.s)
   of nkCallKinds:
@@ -1690,6 +1697,14 @@ proc genParams(c: PCtx; params: PNode) =
     c.prc.slots[i] = (inUse: true, kind: slotFixedLet)
   c.prc.maxSlots = max(params.len, 1)
 
+proc genGenericParams(c: PCtx; gp: PNode) =
+  var base = c.prc.maxSlots
+  for i in 0.. <gp.len:
+    var param = gp.sons[i].sym
+    param.position = base + i # XXX: fix this earlier; make it consistent with templates
+    c.prc.slots[base + i] = (inUse: true, kind: slotFixedLet)
+  c.prc.maxSlots = base + gp.len
+
 proc finalJumpTarget(c: PCtx; pc, diff: int) =
   internalAssert(-0x7fff < diff and diff < 0x7fff)
   let oldInstr = c.code[pc]
@@ -1761,6 +1776,8 @@ proc genProc(c: PCtx; s: PSym): int =
     c.prc = p
     # iterate over the parameters and allocate space for them:
     genParams(c, s.typ.n)
+    if s.kind == skMacro and s.ast[genericParamsPos].kind != nkEmpty:
+      genGenericParams(c, s.ast[genericParamsPos])
     if tfCapturesEnv in s.typ.flags:
       #let env = s.ast.sons[paramsPos].lastSon.sym
       #assert env.position == 2