towards support for composite type classes such as seq[Number] and SquareMatrix[T]

8 files changed, 87 insertions, 26 deletions

diff --git a/compiler/ast.nim b/compiler/ast.nim
index 130f5a5ad..45784bbcb 100644
--- a/compiler/ast.nim
+++ b/compiler/ast.nim
@@ -340,6 +340,7 @@ type
     tyParametricTypeClass # structured similarly to tyGenericInst
                           # lastSon is the body of the type class
     tyBuiltInTypeClass
+    tyCompositeTypeClass
     tyAnd
     tyOr
     tyNot
@@ -350,7 +351,7 @@ const
   tyPureObject* = tyTuple
   GcTypeKinds* = {tyRef, tySequence, tyString}
   tyError* = tyProxy # as an errornous node should match everything
-  tyTypeClasses* = {tyTypeClass, tyBuiltInTypeClass,
+  tyTypeClasses* = {tyTypeClass, tyBuiltInTypeClass, tyCompositeTypeClass,
                     tyParametricTypeClass, tyAnd, tyOr, tyNot, tyAnything}
 
 type
diff --git a/compiler/procfind.nim b/compiler/procfind.nim
index aefccd140..aef1c4edc 100644
--- a/compiler/procfind.nim
+++ b/compiler/procfind.nim
@@ -25,7 +25,7 @@ proc equalGenericParams(procA, procB: PNode): bool =
     let a = procA.sons[i].sym
     let b = procB.sons[i].sym
     if a.name.id != b.name.id or
-        not sameTypeOrNil(a.typ, b.typ, {TypeDescExactMatch}): return
+        not sameTypeOrNil(a.typ, b.typ, {ExactTypeDescValues}): return
     if a.ast != nil and b.ast != nil:
       if not ExprStructuralEquivalent(a.ast, b.ast): return
   result = true
diff --git a/compiler/seminst.nim b/compiler/seminst.nim
index a76c673da..250e53ed6 100644
--- a/compiler/seminst.nim
+++ b/compiler/seminst.nim
@@ -47,7 +47,7 @@ proc sameInstantiation(a, b: TInstantiation): bool =
   if a.concreteTypes.len == b.concreteTypes.len:
     for i in 0..a.concreteTypes.high:
       if not compareTypes(a.concreteTypes[i], b.concreteTypes[i],
-                          flags = {TypeDescExactMatch}): return
+                          flags = {ExactTypeDescValues}): return
     result = true
 
 proc GenericCacheGet(genericSym: Psym, entry: TInstantiation): PSym =
@@ -165,7 +165,8 @@ proc lateInstantiateGeneric(c: PContext, invocation: PType, info: TLineInfo): PT
       result.sons.add instantiated
       cacheTypeInst result
 
-proc instGenericContainer(c: PContext, info: TLineInfo, header: PType): PType =
+proc instGenericContainer(c: PContext, info: TLineInfo, header: PType,
+                          allowMetaTypes = false): PType =
   when oUseLateInstantiation:
     lateInstantiateGeneric(c, header, info)
   else:
@@ -174,6 +175,7 @@ proc instGenericContainer(c: PContext, info: TLineInfo, header: PType): PType =
     InitIdTable(cl.typeMap)
     cl.info = info
     cl.c = c
+    cl.allowMetaTypes = allowMetaTypes
     result = ReplaceTypeVarsT(cl, header)
 
 proc instGenericContainer(c: PContext, n: PNode, header: PType): PType =
diff --git a/compiler/semtypes.nim b/compiler/semtypes.nim
index 201622016..d3a934c21 100644
--- a/compiler/semtypes.nim
+++ b/compiler/semtypes.nim
@@ -666,11 +666,14 @@ proc liftParamType(c: PContext, procKind: TSymKind, genericParams: PNode,
           paramType.sons[i] = lifted
           result = paramType
   of tyGenericBody:
-    # type Foo[T] = object
-    # proc x(a: Foo, b: Foo) 
-    var typ = newTypeS(tyTypeClass, c)
-    typ.addSonSkipIntLit(paramType)
-    result = addImplicitGeneric(typ)
+    result = newTypeS(tyGenericInvokation, c)
+    result.rawAddSon(paramType)
+    for i in 0 .. paramType.sonsLen - 2:
+      result.rawAddSon(copyType(paramType.sons[i], getCurrOwner(), true))
+    result = instGenericContainer(c, paramType.sym.info, result,
+                                  allowMetaTypes = true)
+    result = newTypeWithSons(c, tyCompositeTypeClass, @[paramType, result])
+    result = addImplicitGeneric(result)
   of tyGenericInst:
     for i in 1 .. (paramType.sons.len - 2):
       var lifted = liftingWalk(paramType.sons[i])
diff --git a/compiler/semtypinst.nim b/compiler/semtypinst.nim
index 69d91766b..f7750171d 100644
--- a/compiler/semtypinst.nim
+++ b/compiler/semtypinst.nim
@@ -50,9 +50,10 @@ proc searchInstTypes*(key: PType): PType =
     block MatchType:
       for j in 1 .. high(key.sons):
         # XXX sameType is not really correct for nested generics?
-        if not sameType(inst.sons[j], key.sons[j]):
+        if not compareTypes(inst.sons[j], key.sons[j],
+                            flags = {ExactGenericParams}):
           break MatchType
-      
+       
       return inst
 
 proc cacheTypeInst*(inst: PType) =
@@ -67,6 +68,8 @@ type
     typeMap*: TIdTable        # map PType to PType
     symMap*: TIdTable         # map PSym to PSym
     info*: TLineInfo
+    allowMetaTypes*: bool     # allow types such as seq[Number]
+                              # i.e. the result contains unresolved generics
 
 proc ReplaceTypeVarsT*(cl: var TReplTypeVars, t: PType): PType
 proc ReplaceTypeVarsS(cl: var TReplTypeVars, s: PSym): PSym
@@ -132,9 +135,10 @@ proc ReplaceTypeVarsS(cl: var TReplTypeVars, s: PSym): PSym =
 proc lookupTypeVar(cl: TReplTypeVars, t: PType): PType = 
   result = PType(idTableGet(cl.typeMap, t))
   if result == nil:
+    if cl.allowMetaTypes: return
     LocalError(t.sym.info, errCannotInstantiateX, typeToString(t))
     result = errorType(cl.c)
-  elif result.kind == tyGenericParam: 
+  elif result.kind == tyGenericParam and not cl.allowMetaTypes:
     InternalError(cl.info, "substitution with generic parameter")
   
 proc handleGenericInvokation(cl: var TReplTypeVars, t: PType): PType = 
@@ -150,11 +154,11 @@ proc handleGenericInvokation(cl: var TReplTypeVars, t: PType): PType =
     var x = t.sons[i]
     if x.kind == tyGenericParam:
       x = lookupTypeVar(cl, x)
-      if header == nil: header = copyType(t, t.owner, false)
-      header.sons[i] = x
-      propagateToOwner(header, x)
-      #idTablePut(cl.typeMap, body.sons[i-1], x)  
-
+      if x != nil:
+        if header == nil: header = copyType(t, t.owner, false)
+        header.sons[i] = x
+        propagateToOwner(header, x)
+  
   if header != nil:
     # search again after first pass:
     result = searchInstTypes(header)
@@ -202,6 +206,7 @@ proc ReplaceTypeVarsT*(cl: var TReplTypeVars, t: PType): PType =
   of tyTypeClass: nil
   of tyGenericParam:
     result = lookupTypeVar(cl, t)
+    if result == nil: return t
     if result.kind == tyGenericInvokation:
       result = handleGenericInvokation(cl, result)
   of tyGenericInvokation: 
diff --git a/compiler/sigmatch.nim b/compiler/sigmatch.nim
index 6a6888223..18020b95c 100644
--- a/compiler/sigmatch.nim
+++ b/compiler/sigmatch.nim
@@ -647,6 +647,8 @@ proc typeRel(c: var TCandidate, f, a: PType, doBind = true): TTypeRelation =
     result = typeRel(c, lastSon(f), a)
 
   of tyGenericBody:
+    if a.kind == tyGenericInst and a.sons[0] == f:
+      return isGeneric
     let ff = lastSon(f)
     if ff != nil: result = typeRel(c, ff, a)
 
@@ -718,6 +720,17 @@ proc typeRel(c: var TCandidate, f, a: PType, doBind = true): TTypeRelation =
     else:
       result = typeRel(c, prev, a)
 
+  of tyCompositeTypeClass:
+    var prev = PType(idTableGet(c.bindings, f))
+    if prev == nil:
+      if typeRel(c, f.sons[1], a) != isNone:
+        put(c.bindings, f, a)
+        return isGeneric
+      else:
+        return isNone
+    else:
+      result = typeRel(c, prev, a)
+
   of tyGenericParam, tyTypeClass:
     var x = PType(idTableGet(c.bindings, f))
     if x == nil:
@@ -780,10 +793,13 @@ proc typeRel(c: var TCandidate, f, a: PType, doBind = true): TTypeRelation =
       let toMatch = if tfUnresolved in f.flags: a
                     else: a.sons[0]
       result = typeRel(c, prev.sons[0], toMatch)
+  
   of tyExpr, tyStmt:
     result = isGeneric
+  
   of tyProxy:
     result = isEqual
+  
   else: internalError("typeRel: " & $f.kind)
   
 proc cmpTypes*(c: PContext, f, a: PType): TTypeRelation = 
diff --git a/compiler/types.nim b/compiler/types.nim
index f6e426f39..1b25a396c 100644
--- a/compiler/types.nim
+++ b/compiler/types.nim
@@ -409,7 +409,7 @@ const
     "uint", "uint8", "uint16", "uint32", "uint64",
     "bignum", "const ",
     "!", "varargs[$1]", "iter[$1]", "Error Type", "TypeClass",
-    "ParametricTypeClass", "BuiltInTypeClass",
+    "ParametricTypeClass", "BuiltInTypeClass", "CompositeTypeClass",
     "and", "or", "not", "any", "static"]
 
 proc TypeToString(typ: PType, prefer: TPreferedDesc = preferName): string =
@@ -604,8 +604,9 @@ type
     dcEqOrDistinctOf       ## a equals b or a is distinct of b
 
   TTypeCmpFlag* = enum
-    IgnoreTupleFields,
-    TypeDescExactMatch,
+    IgnoreTupleFields
+    ExactTypeDescValues
+    ExactGenericParams
     AllowCommonBase
 
   TTypeCmpFlags* = set[TTypeCmpFlag]
@@ -646,7 +647,7 @@ proc SameTypeOrNil*(a, b: PType, flags: TTypeCmpFlags = {}): bool =
       result = SameTypeAux(a, b, c)
 
 proc equalParam(a, b: PSym): TParamsEquality = 
-  if SameTypeOrNil(a.typ, b.typ, {TypeDescExactMatch}) and
+  if SameTypeOrNil(a.typ, b.typ, {ExactTypeDescValues}) and
       ExprStructuralEquivalent(a.constraint, b.constraint):
     if a.ast == b.ast: 
       result = paramsEqual
@@ -682,7 +683,7 @@ proc equalParams(a, b: PNode): TParamsEquality =
         return paramsNotEqual # paramsIncompatible;
       # continue traversal! If not equal, we can return immediately; else
       # it stays incompatible
-    if not SameTypeOrNil(a.sons[0].typ, b.sons[0].typ, {TypeDescExactMatch}):
+    if not SameTypeOrNil(a.sons[0].typ, b.sons[0].typ, {ExactTypeDescValues}):
       if (a.sons[0].typ == nil) or (b.sons[0].typ == nil): 
         result = paramsNotEqual # one proc has a result, the other not is OK
       else: 
@@ -749,9 +750,9 @@ template IfFastObjectTypeCheckFailed(a, b: PType, body: stmt) {.immediate.} =
 
 proc sameObjectTypes*(a, b: PType): bool =
   # specialized for efficiency (sigmatch uses it)
-  IfFastObjectTypeCheckFailed(a, b):     
+  IfFastObjectTypeCheckFailed(a, b):
     var c = initSameTypeClosure()
-    result = sameTypeAux(a, b, c)    
+    result = sameTypeAux(a, b, c)
 
 proc sameDistinctTypes*(a, b: PType): bool {.inline.} =
   result = sameObjectTypes(a, b)
@@ -852,12 +853,15 @@ proc SameTypeAux(x, y: PType, c: var TSameTypeClosure): bool =
     result = sameTypeAux(lastSon(a), lastSon(b), c)
   of tyTypeDesc:
     if c.cmp == dcEqIgnoreDistinct: result = false
-    elif TypeDescExactMatch in c.flags:
+    elif ExactTypeDescValues in c.flags:
       CycleCheck()
       result = sameChildrenAux(x, y, c) and sameFlags(a, b)
     else:
       result = sameFlags(a, b)
-  of tyGenericParam, tyGenericInvokation, tyGenericBody, tySequence,
+  of tyGenericParam:
+    result = if ExactGenericParams in c.flags: a.id == b.id
+             else: sameChildrenAux(a, b, c) and sameFlags(a, b)
+  of tyGenericInvokation, tyGenericBody, tySequence,
      tyOpenArray, tySet, tyRef, tyPtr, tyVar, tyArrayConstr,
      tyArray, tyProc, tyConst, tyMutable, tyVarargs, tyIter,
      tyOrdinal, tyTypeClasses:
diff --git a/tests/compile/tcompositetypeclasses.nim b/tests/compile/tcompositetypeclasses.nim
new file mode 100644
index 000000000..ea966f1a9
--- /dev/null
+++ b/tests/compile/tcompositetypeclasses.nim
@@ -0,0 +1,30 @@
+template accept(e) =
+  static: assert(compiles(e))
+
+template reject(e) =
+  static: assert(not compiles(e))
+
+type
+  TFoo[T, U] = tuple
+    x: T
+    y: U
+
+  TBar[K] = TFoo[K, K]
+
+  TUserClass = int|string
+
+  # TBaz = TBar[TUserClass]
+
+var
+  vfoo: TFoo[int, string]
+  vbar: TFoo[string, string]
+
+proc foo(x: TFoo) = echo "foo"
+proc bar(x: TBar) = echo "bar"
+# proc baz(x: TBaz) = echo "baz"
+
+accept(foo(vfoo))
+accept(bar(vbar))
+# baz vbar
+reject(bar(vfoo))
+