enforce the covariance rules for user-defined generic types

5 files changed, 105 insertions, 17 deletions

diff --git a/compiler/ast.nim b/compiler/ast.nim
index 4bd76e41e..ee6391919 100644
--- a/compiler/ast.nim
+++ b/compiler/ast.nim
@@ -270,8 +270,8 @@ type
     sfDiscardable,    # returned value may be discarded implicitly
     sfOverriden,      # proc is overriden
     sfGenSym          # symbol is 'gensym'ed; do not add to symbol table
-    sfCovariant       # covariant generic param mimicing seq/array type
-    sfStrongCovariant # covariant generic param mimicing ptr type
+    sfCovariant       # covariant generic param mimicing a ptr type
+    sfWeakCovariant   # covariant generic param mimicing a seq/array type
     sfContravariant   # contravariant generic param
 
   TSymFlags* = set[TSymFlag]
@@ -1009,15 +1009,17 @@ proc add*(father, son: PNode) =
   if isNil(father.sons): father.sons = @[]
   add(father.sons, son)
 
-proc `[]`*(n: PNode, i: int): PNode {.inline.} =
-  result = n.sons[i]
+type Indexable = PNode | PType
+
+template `[]`*(n: Indexable, i: int): Indexable =
+  n.sons[i]
 
 template `-|`*(b, s: untyped): untyped =
   (if b >= 0: b else: s.len + b)
 
 # son access operators with support for negative indices
-template `{}`*(n: PNode, i: int): untyped = n[i -| n]
-template `{}=`*(n: PNode, i: int, s: PNode) =
+template `{}`*(n: Indexable, i: int): untyped = n[i -| n]
+template `{}=`*(n: Indexable, i: int, s: Indexable) =
   n.sons[i -| n] = s
 
 when defined(useNodeIds):
diff --git a/compiler/msgs.nim b/compiler/msgs.nim
index 1842ce1de..e416a3826 100644
--- a/compiler/msgs.nim
+++ b/compiler/msgs.nim
@@ -381,7 +381,7 @@ const
                                 "of the generic paramers can be inferred from the expected signature.",
     errProcHasNoConcreteType: "'$1' doesn't have a concrete type, due to unspecified generic parameters.",
     errCompilerDoesntSupportTarget: "The current compiler \'$1\' doesn't support the requested compilation target",
-    errInOutFlagNotExtern: "`in` and `out` flags can be used only with imported types",
+    errInOutFlagNotExtern: "The `$1` modifier can be used only with imported types",
     errUser: "$1",
     warnCannotOpenFile: "cannot open \'$1\'",
     warnOctalEscape: "octal escape sequences do not exist; leading zero is ignored",
diff --git a/compiler/semstmts.nim b/compiler/semstmts.nim
index e52a1b5cc..4c1fbede3 100644
--- a/compiler/semstmts.nim
+++ b/compiler/semstmts.nim
@@ -730,7 +730,9 @@ proc typeSectionLeftSidePass(c: PContext, n: PNode) =
     var s: PSym
     if name.kind == nkDotExpr:
       s = qualifiedLookUp(c, name, {checkUndeclared, checkModule})
-      if s.kind != skType or s.typ.skipTypes(abstractPtrs).kind != tyObject or tfPartial notin s.typ.skipTypes(abstractPtrs).flags:
+      if s.kind != skType or
+         s.typ.skipTypes(abstractPtrs).kind != tyObject or
+         tfPartial notin s.typ.skipTypes(abstractPtrs).flags:
         localError(name.info, "only .partial objects can be extended")
     else:
       s = semIdentDef(c, name, skType)
@@ -742,6 +744,87 @@ proc typeSectionLeftSidePass(c: PContext, n: PNode) =
       if sfGenSym notin s.flags: addInterfaceDecl(c, s)
     a.sons[0] = newSymNode(s)
 
+proc checkCovariantParamsUsages(genericType: PType) =
+  var body = genericType{-1}
+
+  proc traverseSubTypes(t: PType): bool =
+    template error(msg) = localError(genericType.sym.info, msg)
+
+    result = false
+
+    template subresult(r) =
+      let sub = r
+      result = result or sub
+
+    case t.kind
+    of tyGenericParam:
+      t.sym.flags.incl sfWeakCovariant
+      return true
+
+    of tyObject:
+      for field in t.n:
+        subresult traverseSubTypes(field.typ)
+
+    of tyArray:
+      return traverseSubTypes(t[1])
+
+    of tyProc:
+      for subType in t.sons:
+        if subType != nil:
+          subresult traverseSubTypes(subType)
+      if result:
+        error("non-invariant type param used in a proc type: " &  $t)
+
+    of tySequence:
+      return traverseSubTypes(t[0])
+
+    of tyGenericInvocation:
+      let targetBody = t[0]
+      for i in 1 .. <t.len:
+        let param = t[i]
+        if param.kind == tyGenericParam:
+          if sfCovariant in param.sym.flags:
+            let formalFlags = targetBody[i-1].sym.flags
+            if sfCovariant notin formalFlags:
+              error("covariant param '" & param.sym.name.s &
+                    "' used in a non-covariant position")
+            elif sfWeakCovariant in formalFlags:
+              param.sym.flags.incl sfWeakCovariant
+            result = true
+          elif sfContravariant in param.sym.flags:
+            let formalParam = targetBody[i-1].sym
+            if sfContravariant notin formalParam.flags:
+              error("contravariant param '" & param.sym.name.s &
+                    "' used in a non-contravariant position")
+            result = true
+        else:
+          subresult traverseSubTypes(param)
+
+    of tyAnd, tyOr, tyNot, tyStatic, tyBuiltInTypeClass, tyCompositeTypeClass:
+      error("non-invariant type parameters cannot be used with types such '" & $t & "'")
+
+    of tyUserTypeClass, tyUserTypeClassInst:
+      error("non-invariant type parameters are not supported in concepts")
+
+    of tyTuple:
+      for fieldType in t.sons:
+        subresult traverseSubTypes(fieldType)
+
+    of tyPtr, tyRef, tyVar:
+      if t.base.kind == tyGenericParam: return true
+      return traverseSubTypes(t.base)
+
+    of tyDistinct, tyAlias:
+      return traverseSubTypes(t.lastSon)
+
+    of tyGenericInst:
+      internalAssert false
+
+    else:
+      discard
+
+  discard traverseSubTypes(body)
+
 proc typeSectionRightSidePass(c: PContext, n: PNode) =
   for i in countup(0, sonsLen(n) - 1):
     var a = n.sons[i]
@@ -782,6 +865,9 @@ proc typeSectionRightSidePass(c: PContext, n: PNode) =
         body.sym = s
         body.size = -1 # could not be computed properly
         s.typ.sons[sonsLen(s.typ) - 1] = body
+        if sfCovariant in s.flags:
+          checkCovariantParamsUsages(s.typ)
+
       popOwner(c)
       closeScope(c)
     elif a.sons[2].kind != nkEmpty:
diff --git a/compiler/semtypes.nim b/compiler/semtypes.nim
index ad7e53a4d..e0dedf135 100644
--- a/compiler/semtypes.nim
+++ b/compiler/semtypes.nim
@@ -136,9 +136,6 @@ proc semAnyRef(c: PContext; n: PNode; kind: TTypeKind; prev: PType): PType =
     let n = if n[0].kind == nkBracket: n[0] else: n
     checkMinSonsLen(n, 1)
     var t = semTypeNode(c, n.lastSon, nil)
-    if c.inGenericContext > 0:
-      if t.sym != nil and sfCovariant in t.sym.flags:
-        t.sym.flags.incl sfStrongCovariant
     if t.kind == tyTypeDesc and tfUnresolved notin t.flags:
       t = t.base
     result = newOrPrevType(kind, prev, c)
@@ -1591,10 +1588,13 @@ proc semGenericParamList(c: PContext, n: PNode, father: PType = nil): PNode =
       var covarianceFlag = sfPure
 
       if paramName.kind in {nkInTy, nkOutTy}:
-        if father == nil or sfImportc notin father.sym.flags:
-          localError(paramName.info, errInOutFlagNotExtern)
+        if not nimEnableCovariance or paramName.kind == nkInTy:
+          if father == nil or sfImportc notin father.sym.flags:
+            localError(paramName.info, errInOutFlagNotExtern,
+                       if paramName.kind == nkInTy: "in" else: "out")
         covarianceFlag = if paramName.kind == nkInTy: sfContravariant
                          else: sfCovariant
+        if father != nil: father.sym.flags.incl sfCovariant
         paramName = paramName[0]
 
       var s = if finalType.kind == tyStatic or tfWildcard in typ.flags:
diff --git a/compiler/sigmatch.nim b/compiler/sigmatch.nim
index c2a9b78bf..36975c3db 100644
--- a/compiler/sigmatch.nim
+++ b/compiler/sigmatch.nim
@@ -883,7 +883,7 @@ proc isCovariantPtr(c: var TCandidate, f, a: PType): bool =
     let body = f.base
     return body == a.base and
            a.sonsLen == 3 and
-           sfStrongCovariant in body.sons[0].sym.flags and
+           sfWeakCovariant notin body.sons[0].sym.flags and
            baseTypesCheck(f.sons[1], a.sons[1])
   else:
     return false
@@ -1305,10 +1305,10 @@ proc typeRel(c: var TCandidate, f, aOrig: PType,
               let paramFlags = rootf.base.sons[i-1].sym.flags
               hasCovariance =
                 if sfCovariant in paramFlags:
-                  if sfStrongCovariant in paramFlags:
-                    ff.kind notin {tyRef, tyPtr} and result == isSubtype
-                  else:
+                  if sfWeakCovariant in paramFlags:
                     isCovariantPtr(c, ff, aa)
+                  else:
+                    ff.kind notin {tyRef, tyPtr} and result == isSubtype
                 else:
                   sfContravariant in paramFlags and
                     typeRel(c, aa, ff) == isSubtype