SI-5318 Make implicit divergence checking PolyType aware.

Replaces the two active subclasses of `SymCollector` with
direct use of traversal methods of `Type`.

Wildcard free class type parameters, not just method type parameters,
when stripping the core type of candidate implicits. The spec doesn't
make any such distinction, and the enclosed test, t5318c, crashes
without this change.

8 files changed, 70 insertions, 35 deletions

diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
index 8f025336bb..43b96314b0 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -346,7 +346,11 @@ trait Implicits {
         case _ => tp
       }
       def stripped(tp: Type): Type = {
-        deriveTypeWithWildcards(freeTypeParametersNoSkolems.collect(tp))(tp)
+        // `t.typeSymbol` returns the symbol of the normalized type. If that normalized type
+        // is a `PolyType`, the symbol of the result type is collected. This is precisely
+        // what we require for SI-5318.
+        val syms = for (t <- tp; if t.typeSymbol.isTypeParameter) yield t.typeSymbol
+        deriveTypeWithWildcards(syms.distinct)(tp)
       }
       def sum(xs: List[Int]) = (0 /: xs)(_ + _)
       def complexity(tp: Type): Int = tp.normalize match {
diff --git a/src/compiler/scala/tools/nsc/typechecker/Infer.scala b/src/compiler/scala/tools/nsc/typechecker/Infer.scala
index 1c1adee343..e91050987b 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Infer.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Infer.scala
@@ -1076,7 +1076,7 @@ trait Infer {
      */
     def inferConstructorInstance(tree: Tree, undetparams: List[Symbol], pt0: Type) {
       val pt       = widen(pt0)
-      val ptparams = freeTypeParamsOfTerms.collect(pt)
+      val ptparams = freeTypeParamsOfTerms(pt)
       val ctorTp   = tree.tpe
       val resTp    = ctorTp.finalResultType
 
@@ -1310,8 +1310,8 @@ trait Infer {
 
     def inferTypedPattern(tree0: Tree, pattp: Type, pt0: Type): Type = {
       val pt        = widen(pt0)
-      val ptparams  = freeTypeParamsOfTerms.collect(pt)
-      val tpparams  = freeTypeParamsOfTerms.collect(pattp)
+      val ptparams  = freeTypeParamsOfTerms(pt)
+      val tpparams  = freeTypeParamsOfTerms(pattp)
 
       def ptMatchesPattp = pt matchesPattern pattp.widen
       def pattpMatchesPt = pattp matchesPattern pt
@@ -1364,7 +1364,7 @@ trait Infer {
 
     def inferModulePattern(pat: Tree, pt: Type) =
       if (!(pat.tpe <:< pt)) {
-        val ptparams = freeTypeParamsOfTerms.collect(pt)
+        val ptparams = freeTypeParamsOfTerms(pt)
         debuglog("free type params (2) = " + ptparams)
         val ptvars = ptparams map freshVar
         val pt1 = pt.instantiateTypeParams(ptparams, ptvars)
@@ -1381,19 +1381,6 @@ trait Infer {
       }
     }
 
-    abstract class SymCollector extends TypeCollector(List[Symbol]()) {
-      protected def includeCondition(sym: Symbol): Boolean
-
-      def traverse(tp: Type) {
-        tp.normalize match {
-          case TypeRef(_, sym, _) =>
-            if (includeCondition(sym) && !result.contains(sym)) result = sym :: result
-          case _ =>
-        }
-        mapOver(tp)
-      }
-    }
-
     object approximateAbstracts extends TypeMap {
       def apply(tp: Type): Type = tp.normalize match {
         case TypeRef(pre, sym, _) if sym.isAbstractType => WildcardType
@@ -1401,31 +1388,30 @@ trait Infer {
       }
     }
 
-    /** A traverser to collect type parameters referred to in a type
+    /** Collects type parameters referred to in a type.
      */
-    object freeTypeParamsOfTerms extends SymCollector {
+    def freeTypeParamsOfTerms(tp: Type): List[Symbol] = {
       // An inferred type which corresponds to an unknown type
       // constructor creates a file/declaration order-dependent crasher
       // situation, the behavior of which depends on the state at the
       // time the typevar is created. Until we can deal with these
       // properly, we can avoid it by ignoring type parameters which
       // have type constructors amongst their bounds. See SI-4070.
-      protected def includeCondition(sym: Symbol) = (
-           sym.isAbstractType
-        && sym.owner.isTerm
-        && !sym.info.bounds.exists(_.typeParams.nonEmpty)
-      )
-    }
-
-    /** A traverser to collect type parameters referred to in a type
-     */
-    object freeTypeParametersNoSkolems extends SymCollector {
-      protected def includeCondition(sym: Symbol): Boolean =
-        sym.isTypeParameter && sym.owner.isTerm
-    }
+      def isFreeTypeParamOfTerm(sym: Symbol) = (
+        sym.isAbstractType
+          && sym.owner.isTerm
+          && !sym.info.bounds.exists(_.typeParams.nonEmpty)
+        )
 
-    object typeRefs extends SymCollector {
-      protected def includeCondition(sym: Symbol): Boolean = true
+      // Intentionally *not* using `Type#typeSymbol` here, which would normalize `tp`
+      // and collect symbols from the result type of any resulting `PolyType`s, which 
+      // are not free type parameters of `tp`.
+      //
+      // Contrast with `isFreeTypeParamNoSkolem`.
+      val syms = tp collect {
+        case TypeRef(_, sym, _) if isFreeTypeParamOfTerm(sym) => sym
+      }
+      syms.distinct
     }
 
     /* -- Overload Resolution ---------------------------------------------- */
diff --git a/test/files/neg/t5318.check b/test/files/neg/t5318.check
new file mode 100644
index 0000000000..d6a3a57935
--- /dev/null
+++ b/test/files/neg/t5318.check
@@ -0,0 +1,5 @@
+t5318.scala:7: error: diverging implicit expansion for type CompilerHang.this.TC[F]
+starting with method tc in class CompilerHang
+  breakage  // type checker doesn't terminate, should report inference failure
+  ^
+one error found
diff --git a/test/files/neg/t5318.scala b/test/files/neg/t5318.scala
new file mode 100644
index 0000000000..8009c66e6b
--- /dev/null
+++ b/test/files/neg/t5318.scala
@@ -0,0 +1,8 @@
+class CompilerHang {
+  trait TC[M[_]]
+  trait S[A]
+
+  implicit def tc[M[_]](implicit M0: TC[M]): TC[S] = null
+  def breakage[F[_] : TC] = 0
+  breakage  // type checker doesn't terminate, should report inference failure
+}
\ No newline at end of file
diff --git a/test/files/neg/t5318b.check b/test/files/neg/t5318b.check
new file mode 100644
index 0000000000..47a10d6733
--- /dev/null
+++ b/test/files/neg/t5318b.check
@@ -0,0 +1,5 @@
+t5318b.scala:7: error: diverging implicit expansion for type DivergingImplicitReported.this.TC[F]
+starting with method tc in class DivergingImplicitReported
+  breakage // correct: diverging implicit expansion
+  ^
+one error found
\ No newline at end of file
diff --git a/test/files/neg/t5318b.scala b/test/files/neg/t5318b.scala
new file mode 100644
index 0000000000..123f8b4e04
--- /dev/null
+++ b/test/files/neg/t5318b.scala
@@ -0,0 +1,8 @@
+class DivergingImplicitReported {
+  trait TC[M]
+  trait S
+
+  implicit def tc[M](implicit M0: TC[M]): TC[S] = null
+  def breakage[F: TC] = 0
+  breakage // correct: diverging implicit expansion
+}
\ No newline at end of file
diff --git a/test/files/neg/t5318c.check b/test/files/neg/t5318c.check
new file mode 100644
index 0000000000..594539be69
--- /dev/null
+++ b/test/files/neg/t5318c.check
@@ -0,0 +1,5 @@
+t5318c.scala:13: error: diverging implicit expansion for type CompilerHang.this.TC[F]
+starting with method tc in class CompilerHang
+  breakage // type checker doesn't terminate, should report inference failure
+  ^
+one error found
diff --git a/test/files/neg/t5318c.scala b/test/files/neg/t5318c.scala
new file mode 100644
index 0000000000..477a9874ad
--- /dev/null
+++ b/test/files/neg/t5318c.scala
@@ -0,0 +1,14 @@
+class CompilerHang {
+  trait TC[M[_]]
+  trait S[A]
+
+  class C[M[_]] {
+    type TCM = TC[M]
+  }
+
+  // A nefarious implicit, to motivate the removal of `&& sym.owner.isTerm` from
+  // `isFreeTypeParamNoSkolem`.
+  implicit def tc[x[_], CC[x[_]] <: C[x]](implicit M0: CC[x]#TCM): CC[x]#TCM = null
+  def breakage[F[_] : TC] = 0
+  breakage // type checker doesn't terminate, should report inference failure
+}