SI-8237 Avoid cyclic constraints when inferring hk type args

An `AppliedTypeVars` spawned from `HKTypeVar#applyArgs`
(necessarily) shares the same `TypeConstraints`.

But, we can have multiple ATVs based on a single HKTV floating
around during inference, and they can appear on both sides
of type relations. An example of this is traced out in
the enclosed test.

This commit avoids registering upper/lower bound constraints
when this is detected.

In the enclosed test, we end up with an empty set of constraints
for `?E`, which results in inference of Nothing, which is what
we expect.

I have also improved the printing of ATVs (to include the args)
and sharpened the log message when `solve` leaves type variables
instantiated to `NoType`, rather than some other type that doesn't
conform to the bounds. Both of these changes helped me to get
to the bottom of this ticket. The improved `ATV#toString` shows
up in some updated checkfiles.

The reported test has quite a checkered history:

  - in 2.10.0 it worked, but more by good luck than good planning
  - after the fix for SI-7226 / 221f52757aa6, it started crashing
  - from 3bd897ba0054f (a merge from 2.10.x just before 2.11.0-M1)
    we started getting a type inference failure, rather than a crash.
    "no type parameters for method exists [...] because cyclic
    instantiation".
  - It still crashes in `isGround` in 2.10.3.

8 files changed, 110 insertions, 7 deletions

diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index 53c528a2bb..ba7efc94a6 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -2905,6 +2905,8 @@ trait Types
 
     override def params: List[Symbol] = zippedArgs map (_._1)
     override def typeArgs: List[Type] = zippedArgs map (_._2)
+
+    override def safeToString: String = super.safeToString + typeArgs.map(_.safeToString).mkString("[", ", ", "]")
   }
 
   trait UntouchableTypeVar extends TypeVar {
@@ -3025,15 +3027,19 @@ trait Types
     def addLoBound(tp: Type, isNumericBound: Boolean = false) {
       assert(tp != this, tp) // implies there is a cycle somewhere (?)
       //println("addLoBound: "+(safeToString, debugString(tp))) //DEBUG
-      undoLog record this
-      constr.addLoBound(tp, isNumericBound)
+      if (!sharesConstraints(tp)) {
+        undoLog record this
+        constr.addLoBound(tp, isNumericBound)
+      }
     }
 
     def addHiBound(tp: Type, isNumericBound: Boolean = false) {
       // assert(tp != this)
       //println("addHiBound: "+(safeToString, debugString(tp))) //DEBUG
-      undoLog record this
-      constr.addHiBound(tp, isNumericBound)
+      if (!sharesConstraints(tp)) {
+        undoLog record this
+        constr.addHiBound(tp, isNumericBound)
+      }
     }
     // </region>
 
@@ -3045,6 +3051,16 @@ trait Types
       case ConstantTrue  => true
       case tv: TypeVar   => tv.suspended
     }
+
+    /** `AppliedTypeVar`s share the same `TypeConstraint` with the `HKTypeVar` that it was spawned from.
+     *   A type inference session can also have more than one ATV.
+     *   If we don't detect that, we end up with "cyclic constraint" when we try to instantiate type parameters
+     *   after solving in, pos/t8237
+     */
+    protected final def sharesConstraints(other: Type): Boolean = other match {
+      case other: TypeVar => constr == other.constr // SI-8237 avoid cycles. Details in pos/t8237.scala
+      case _ => false
+    }
     private[Types] def suspended_=(b: Boolean): Unit = _suspended = if (b) ConstantTrue else ConstantFalse
     // SI-7785 Link the suspended attribute of a TypeVar created in, say, a TypeMap (e.g. AsSeenFrom) to its originator
     private[Types] def linkSuspended(origin: TypeVar): Unit = _suspended = origin
diff --git a/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala b/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala
index e2159d30f5..564cbb1ce3 100644
--- a/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala
+++ b/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala
@@ -257,6 +257,12 @@ private[internal] trait TypeConstraints {
 
     // println("solving "+tvars+"/"+tparams+"/"+(tparams map (_.info)))
     foreach3(tvars, tparams, variances)(solveOne)
-    tvars forall (tv => tv.instWithinBounds || util.andFalse(log(s"Inferred type for ${tv.originString} does not conform to bounds: ${tv.constr}")))
+
+    def logBounds(tv: TypeVar) = log {
+      val what = if (!tv.instValid) "is invalid" else s"does not conform to bounds: ${tv.constr}"
+      s"Inferred type for ${tv.originString} (${tv.inst}) $what"
+    }
+
+    tvars forall (tv => tv.instWithinBounds || util.andFalse(logBounds(tv)))
   }
 }
diff --git a/test/files/neg/names-defaults-neg.check b/test/files/neg/names-defaults-neg.check
index 880ddc4327..20ddd55f1f 100644
--- a/test/files/neg/names-defaults-neg.check
+++ b/test/files/neg/names-defaults-neg.check
@@ -88,7 +88,7 @@ names-defaults-neg.scala:76: error: no type parameters for method test4: (x: T[T
  --- because ---
 argument expression's type is not compatible with formal parameter type;
  found   : List[Int]
- required: ?T
+ required: ?T[?T[List[?T[X forSome { type X }]]]]
 Error occurred in an application involving default arguments.
   test4()
   ^
diff --git a/test/files/neg/t8237-default.check b/test/files/neg/t8237-default.check
new file mode 100644
index 0000000000..59fe21ed03
--- /dev/null
+++ b/test/files/neg/t8237-default.check
@@ -0,0 +1,13 @@
+t8237-default.scala:5: error: no type parameters for method test4: (x: T[T[List[T[X forSome { type X }]]]])Nothing exist so that it can be applied to arguments (List[Int])
+ --- because ---
+argument expression's type is not compatible with formal parameter type;
+ found   : List[Int]
+ required: ?T[?T[List[?T[X forSome { type X }]]]]
+  test4(test4$default$1)
+  ^
+t8237-default.scala:5: error: type mismatch;
+ found   : List[Int]
+ required: T[T[List[T[X forSome { type X }]]]]
+  test4(test4$default$1)
+        ^
+two errors found
diff --git a/test/files/neg/t8237-default.scala b/test/files/neg/t8237-default.scala
new file mode 100644
index 0000000000..f695aa523f
--- /dev/null
+++ b/test/files/neg/t8237-default.scala
@@ -0,0 +1,29 @@
+// This test case was extracte from `names-defaults-neg.scala`
+// It pinpoints an improvement an error message that results from
+// a type inference failure
+object Test extends App {
+  test4(test4$default$1)
+
+  def test4[T[P]](x: T[T[List[T[X forSome { type X }]]]]) = ???
+  def test4$default$1[T[P]]: List[Int] = ???
+}
+
+/*
+OLD:
+ no type parameters for method test4: (x: T[T[List[T[X forSome { type X }]]]])Nothing exist so that it can be applied to arguments (List[Int])
+ --- because ---
+argument expression's type is not compatible with formal parameter type;
+ found   : List[Int]
+ required: ?T
+  test4(test4$default$1)
+  ^
+
+NEW:
+
+no type parameters for method test4: (x: T[T[List[T[X forSome { type X }]]]])Nothing exist so that it can be applied to arguments (List[Int])
+ --- because ---
+argument expression's type is not compatible with formal parameter type;
+ found   : List[Int]
+ required: ?T[?T[List[?T[X forSome { type X }]]]
+  test4(test4$default$1)
+*/
diff --git a/test/files/pos/t8237.scala b/test/files/pos/t8237.scala
new file mode 100644
index 0000000000..005089079e
--- /dev/null
+++ b/test/files/pos/t8237.scala
@@ -0,0 +1,29 @@
+import scala.language.higherKinds
+
+object TestExplicit {
+  trait TC[A]
+  def fTt[A,E[X] <: List[X]](a: A)(implicit tt: TC[E[A]]) = a
+  implicit def tc[T]: TC[T] = ???
+
+  // Typechecking results in SOE in TypeVar.isGround
+  fTt(1)(tc)
+  // fun = TestExplicit.this.fTt[Int, E](1)
+  // args = TestExplicit.this.tc[E[Int]]
+  // argTpes.head.instantiateTypeParams = TC[?E#1[Int]]
+  // formals.head.instantiateTypeParams = TC[?E#2[Int]]
+  //   (where ?E#1 and ?E#2 as distinct AppliedTypeVars that resulted
+  //    from separate applications of type args to the same HKTypeVar, ?E)
+  //
+  // As we check if the argument conforms to the formal, we would have
+  // AppliedTypeVars sharing the same TypeConstraints on the LHS and RHS,
+  // which leads to a cyclic constraint.
+}
+
+object TestImplicit    {
+  trait TC[A]
+  def fTt[A,E[X] <: List[X]](a: A)(implicit tt: TC[E[A]]) = a
+  implicit def tc[T]: TC[T] = ???
+
+  // Oddly enough, this one works.
+  fTt(1)
+}
diff --git a/test/files/pos/t8237b.scala b/test/files/pos/t8237b.scala
new file mode 100644
index 0000000000..52bb310e8b
--- /dev/null
+++ b/test/files/pos/t8237b.scala
@@ -0,0 +1,10 @@
+import scala.language.higherKinds
+import scala.reflect.runtime.universe._
+object Test {
+
+  def fTt[A,E[X]<:List[X]](a: A)(implicit tt: TypeTag[E[A]]) = a
+
+  trait TC[A]
+  implicit def TCListInt[A]: TC[A] = ???
+  fTt(1)
+}
diff --git a/test/files/run/t7319.check b/test/files/run/t7319.check
index d03ee3a6cf..b7443aa0c4 100644
--- a/test/files/run/t7319.check
+++ b/test/files/run/t7319.check
@@ -21,7 +21,7 @@ scala> convert(Some[Int](0))
  --- because ---
 argument expression's type is not compatible with formal parameter type;
  found   : Some[Int]
- required: ?F forSome { type _$1 <: ?F forSome { type _$2 } }
+ required: ?F[_$1] forSome { type _$1 <: ?F[_$2] forSome { type _$2 } }
               convert(Some[Int](0))
               ^
 <console>:12: error: type mismatch;