Fix #5962

During the instantiation of a generic type A, some other generic
type B may be instantiated multiple times with different parameters.
We can think about each instantiation as a function call that should
temporary bind the parameter names to concrete types. The problem
with the existing implementation in semtypinst was that it was
performing this binding within a shared global table. In this sense,
it was executing the code as a programming language featuring only
global variables. In such a language, re-entrant functions cannot be
defined properly and hence this was leading to problems with similar
types. The solution is simple - just like we need to introduce stack
frames to handle re-entrant functions, we introduce a stack of type
bindings that are pushed and popped during the generic instantiations.

3 files changed, 133 insertions, 16 deletions

diff --git a/compiler/seminst.nim b/compiler/seminst.nim
index 196dcdbb8..a28d322b1 100644
--- a/compiler/seminst.nim
+++ b/compiler/seminst.nim
@@ -174,10 +174,14 @@ proc sideEffectsCheck(c: PContext, s: PSym) =
 
 proc instGenericContainer(c: PContext, info: TLineInfo, header: PType,
                           allowMetaTypes = false): PType =
-  var cl: TReplTypeVars
+  var
+    typeMap: LayeredIdTable
+    cl: TReplTypeVars
+
   initIdTable(cl.symMap)
-  initIdTable(cl.typeMap)
   initIdTable(cl.localCache)
+  initIdTable(typeMap.topLayer)
+  cl.typeMap = addr(typeMap)
   cl.info = info
   cl.c = c
   cl.allowMetaTypes = allowMetaTypes
@@ -201,7 +205,8 @@ proc instantiateProcType(c: PContext, pt: TIdTable,
   #addDecl(c, prc)
 
   pushInfoContext(info)
-  var cl = initTypeVars(c, pt, info, nil)
+  var typeMap = initLayeredTypeMap(pt)
+  var cl = initTypeVars(c, addr(typeMap), info, nil)
   var result = instCopyType(cl, prc.typ)
   let originalParams = result.n
   result.n = originalParams.shallowCopy
diff --git a/compiler/semtypinst.nim b/compiler/semtypinst.nim
index 037b07510..2384934ee 100644
--- a/compiler/semtypinst.nim
+++ b/compiler/semtypinst.nim
@@ -73,9 +73,13 @@ proc cacheTypeInst*(inst: PType) =
 
 
 type
+  LayeredIdTable* = object
+    topLayer*: TIdTable
+    nextLayer*: ptr LayeredIdTable
+
   TReplTypeVars* {.final.} = object
     c*: PContext
-    typeMap*: TIdTable        # map PType to PType
+    typeMap*: ptr LayeredIdTable # map PType to PType
     symMap*: TIdTable         # map PSym to PSym
     localCache*: TIdTable     # local cache for remembering alraedy replaced
                               # types during instantiation of meta types
@@ -91,6 +95,23 @@ proc replaceTypeVarsTAux(cl: var TReplTypeVars, t: PType): PType
 proc replaceTypeVarsS(cl: var TReplTypeVars, s: PSym): PSym
 proc replaceTypeVarsN*(cl: var TReplTypeVars, n: PNode; start=0): PNode
 
+proc initLayeredTypeMap*(pt: TIdTable): LayeredIdTable =
+  copyIdTable(result.topLayer, pt)
+
+proc newTypeMapLayer*(cl: var TReplTypeVars): LayeredIdTable =
+  result.nextLayer = cl.typeMap
+  initIdTable(result.topLayer)
+
+proc lookup(typeMap: ptr LayeredIdTable, key: PType): PType =
+  var tm = typeMap
+  while tm != nil:
+    result = PType(idTableGet(tm.topLayer, key))
+    if result != nil: return
+    tm = tm.nextLayer
+
+template put(typeMap: ptr LayeredIdTable, key, value: PType) =
+  idTablePut(typeMap.topLayer, key, value)
+
 template checkMetaInvariants(cl: TReplTypeVars, t: PType) =
   when false:
     if t != nil and tfHasMeta in t.flags and
@@ -219,7 +240,7 @@ proc replaceTypeVarsS(cl: var TReplTypeVars, s: PSym): PSym =
   result.ast = replaceTypeVarsN(cl, s.ast)
 
 proc lookupTypeVar(cl: var TReplTypeVars, t: PType): PType =
-  result = PType(idTableGet(cl.typeMap, t))
+  result = cl.typeMap.lookup(t)
   if result == nil:
     if cl.allowMetaTypes or tfRetType in t.flags: return
     localError(t.sym.info, errCannotInstantiateX, typeToString(t))
@@ -227,7 +248,7 @@ proc lookupTypeVar(cl: var TReplTypeVars, t: PType): PType =
     # In order to prevent endless recursions, we must remember
     # this bad lookup and replace it with errorType everywhere.
     # These code paths are only active in "nim check"
-    idTablePut(cl.typeMap, t, result)
+    cl.typeMap.put(t, result)
   elif result.kind == tyGenericParam and not cl.allowMetaTypes:
     internalError(cl.info, "substitution with generic parameter")
 
@@ -286,12 +307,16 @@ proc handleGenericInvocation(cl: var TReplTypeVars, t: PType): PType =
 
   let oldSkipTypedesc = cl.skipTypedesc
   cl.skipTypedesc = true
+
+  var typeMapLayer = newTypeMapLayer(cl)
+  cl.typeMap = addr(typeMapLayer)
+
   for i in countup(1, sonsLen(t) - 1):
     var x = replaceTypeVarsT(cl, t.sons[i])
     assert x.kind != tyGenericInvocation
     header.sons[i] = x
     propagateToOwner(header, x)
-    idTablePut(cl.typeMap, body.sons[i-1], x)
+    cl.typeMap.put(body.sons[i-1], x)
 
   for i in countup(1, sonsLen(t) - 1):
     # if one of the params is not concrete, we cannot do anything
@@ -304,6 +329,9 @@ proc handleGenericInvocation(cl: var TReplTypeVars, t: PType): PType =
   cl.skipTypedesc = oldSkipTypedesc
   newbody.flags = newbody.flags + (t.flags + body.flags - tfInstClearedFlags)
   result.flags = result.flags + newbody.flags - tfInstClearedFlags
+
+  cl.typeMap = cl.typeMap.nextLayer
+
   # This is actually wrong: tgeneric_closure fails with this line:
   #newbody.callConv = body.callConv
   # This type may be a generic alias and we want to resolve it here.
@@ -405,7 +433,7 @@ proc replaceTypeVarsTAux(cl: var TReplTypeVars, t: PType): PType =
   if t == nil: return
 
   if t.kind in {tyStatic, tyGenericParam} + tyTypeClasses:
-    let lookup = PType(idTableGet(cl.typeMap, t))
+    let lookup = cl.typeMap.lookup(t)
     if lookup != nil: return lookup
 
   case t.kind
@@ -447,7 +475,7 @@ proc replaceTypeVarsTAux(cl: var TReplTypeVars, t: PType): PType =
     result = skipIntLit(t)
 
   of tyTypeDesc:
-    let lookup = PType(idTableGet(cl.typeMap, t)) # lookupTypeVar(cl, t)
+    let lookup = cl.typeMap.lookup(t)
     if lookup != nil:
       result = lookup
       if tfUnresolved in t.flags or cl.skipTypedesc: result = result.base
@@ -486,7 +514,6 @@ proc replaceTypeVarsTAux(cl: var TReplTypeVars, t: PType): PType =
           propagateToOwner(result, r)
       # bug #4677: Do not instantiate effect lists
       result.n = replaceTypeVarsN(cl, result.n, ord(result.kind==tyProc))
-
       case result.kind
       of tyArray:
         let idx = result.sons[0]
@@ -501,18 +528,19 @@ proc replaceTypeVarsTAux(cl: var TReplTypeVars, t: PType): PType =
 
       else: discard
 
-proc initTypeVars*(p: PContext, pt: TIdTable, info: TLineInfo;
+proc initTypeVars*(p: PContext, typeMap: ptr LayeredIdTable, info: TLineInfo;
                    owner: PSym): TReplTypeVars =
   initIdTable(result.symMap)
-  copyIdTable(result.typeMap, pt)
   initIdTable(result.localCache)
+  result.typeMap = typeMap
   result.info = info
   result.c = p
   result.owner = owner
 
 proc replaceTypesInBody*(p: PContext, pt: TIdTable, n: PNode;
                          owner: PSym, allowMetaTypes = false): PNode =
-  var cl = initTypeVars(p, pt, n.info, owner)
+  var typeMap = initLayeredTypeMap(pt)
+  var cl = initTypeVars(p, addr(typeMap), n.info, owner)
   cl.allowMetaTypes = allowMetaTypes
   pushInfoContext(n.info)
   result = replaceTypeVarsN(cl, n)
@@ -520,7 +548,8 @@ proc replaceTypesInBody*(p: PContext, pt: TIdTable, n: PNode;
 
 proc replaceTypesForLambda*(p: PContext, pt: TIdTable, n: PNode;
                             original, new: PSym): PNode =
-  var cl = initTypeVars(p, pt, n.info, original)
+  var typeMap = initLayeredTypeMap(pt)
+  var cl = initTypeVars(p, addr(typeMap), n.info, original)
   idTablePut(cl.symMap, original, new)
   pushInfoContext(n.info)
   result = replaceTypeVarsN(cl, n)
@@ -528,14 +557,16 @@ proc replaceTypesForLambda*(p: PContext, pt: TIdTable, n: PNode;
 
 proc generateTypeInstance*(p: PContext, pt: TIdTable, info: TLineInfo,
                            t: PType): PType =
-  var cl = initTypeVars(p, pt, info, nil)
+  var typeMap = initLayeredTypeMap(pt)
+  var cl = initTypeVars(p, addr(typeMap), info, nil)
   pushInfoContext(info)
   result = replaceTypeVarsT(cl, t)
   popInfoContext()
 
 proc prepareMetatypeForSigmatch*(p: PContext, pt: TIdTable, info: TLineInfo,
                                  t: PType): PType =
-  var cl = initTypeVars(p, pt, info, nil)
+  var typeMap = initLayeredTypeMap(pt)
+  var cl = initTypeVars(p, addr(typeMap), info, nil)
   cl.allowMetaTypes = true
   pushInfoContext(info)
   result = replaceTypeVarsT(cl, t)
diff --git a/tests/generics/treentranttypes.nim b/tests/generics/treentranttypes.nim
new file mode 100644
index 000000000..e79451314
--- /dev/null
+++ b/tests/generics/treentranttypes.nim
@@ -0,0 +1,81 @@
+discard """
+output: '''
+(Field0: 10, Field1: (Field0: test, Field1: 1.2))
+3x3 Matrix [[0.0, 2.0, 3.0], [2.0, 0.0, 5.0], [2.0, 0.0, 5.0]]
+
+2x3 Matrix [[0.0, 2.0, 3.0], [2.0, 0.0, 5.0]]
+
+2x3 Literal [[0.0, 2.0, 3.0], [2.0, 0.0, 5.0]]
+
+2x3 Matrix [[0.0, 0.0, 0.0], [0.0, 0.0, 0.0]]
+
+2x2 ArrayArray[[0.0, 0.0, 0.0], [0.0, 0.0, 0.0]]
+
+2x3 ArrayVector[[0.0, 0.0, 0.0], [0.0, 0.0, 0.0]]
+
+2x3 VectorVector [[0.0, 0.0, 0.0], [0.0, 0.0, 0.0]]
+
+2x3 VectorArray [[0.0, 0.0, 0.0], [0.0, 0.0, 0.0]]
+'''
+"""
+
+# https://github.com/nim-lang/Nim/issues/5962
+
+type
+  ArrayLike[A, B] = (A, B)
+  VectorLike*[SIZE, T] = ArrayLike[SIZE, T]
+  MatrixLike*[M, N, T] = VectorLike[M, VectorLike[N, T]]
+
+proc tupleTest =
+  let m: MatrixLike[int, string, float] = (10, ("test", 1.2))
+  echo m
+
+tupleTest()
+
+type
+  Vector*[K: static[int], T] =
+    array[K, T]
+
+  Matrix*[M: static[int]; N: static[int]; T] =
+    Vector[M, Vector[N, T]]
+  
+proc arrayTest =
+  # every kind of square matrix works just fine
+  let mat_good: Matrix[3, 3, float] = [[0.0, 2.0, 3.0],
+                                       [2.0, 0.0, 5.0],
+                                       [2.0, 0.0, 5.0]]
+  echo "3x3 Matrix ", repr(mat_good)
+
+  # this does not work with explicit type signature (the matrix seems to always think it is NxN instead)
+  let mat_fail: Matrix[2, 3, float] = [[0.0, 2.0, 3.0],
+                                       [2.0, 0.0, 5.0]]
+  echo "2x3 Matrix ", repr(mat_fail)
+
+  # this literal seems to work just fine
+  let mat_also_good = [[0.0, 2.0, 3.0],
+                       [2.0, 0.0, 5.0]]
+
+  echo "2x3 Literal ", repr(mat_also_good)
+
+  # but making a named type out of this leads to pretty nasty runtime behavior
+  var mat_fail_runtime: Matrix[2, 3, float]
+  echo "2x3 Matrix ", repr(mat_fail_runtime)
+
+  # cutting out the matrix type middle man seems to solve our problem
+  var mat_ok_runtime: array[2, array[3, float]]
+  echo "2x2 ArrayArray", repr(mat_ok_runtime)
+
+  # this is fine too
+  var mat_ok_runtime_2: array[2, Vector[3, float]]
+  echo "2x3 ArrayVector", repr(mat_ok_runtime_2)
+
+  # here we are in trouble again
+  var mat_fail_runtime_2: Vector[2, Vector[3, float]]
+  echo "2x3 VectorVector ", repr(mat_fail_runtime_2)
+
+  # and here we are fine again
+  var mat_ok_runtime_3: Vector[2, array[3, float]]
+  echo "2x3 VectorArray ", repr(mat_ok_runtime_3)
+
+arrayTest()
+