From 1cf1bae75db5f178026f6602e9a062484fa73a86 Mon Sep 17 00:00:00 2001
From: Jason Zaugg <jzaugg@gmail.com>
Date: Wed, 5 Feb 2014 15:30:35 +0100
Subject: 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.
---
 src/reflect/scala/reflect/internal/Types.scala     | 24 ++++++++++++++++++----
 .../reflect/internal/tpe/TypeConstraints.scala     |  8 +++++++-
 2 files changed, 27 insertions(+), 5 deletions(-)

(limited to 'src/reflect')

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)))
   }
 }
-- 
cgit v1.2.3