SI-8146 Fix non-deterministic <:< for deeply nested types

In the interests of keeping subtyping decidable [1], 152563b
added some bookkeeping to `isSubType` to detect cycles.

However, this was based on a hash set containing instances of
`SubTypePair`, and that class had inconsistencies between its
`hashCode` (in terms of `Type#hashCode`) and `equals`
(in terms of `=:=`).

This inconsistency can be seen in:

    scala> trait C { def apply: (Int @unchecked) }
    defined trait C

    scala> val intUnchecked = typeOf[C].decls.head.info.finalResultType
    intUnchecked: $r.intp.global.Type = Int @unchecked

    scala> val p1 = new SubTypePair(intUnchecked, intUnchecked)
    p1: $r.intp.global.SubTypePair = Int @unchecked <:<? Int @unchecked

    scala> val p2 = new SubTypePair(intUnchecked.withoutAnnotations, intUnchecked.withoutAnnotations)
    p2: $r.intp.global.SubTypePair = Int <:<? Int

    scala> p1 == p2
    res0: Boolean = true

    scala> p1.hashCode == p2.hashCode
    res1: Boolean = false

This commit switches to using `Type#==`, by way of the standard
case class equality.

The risk here is that you could find a subtyping computation that
progresses in such a manner that we don't detect the cycle. It would
need to produce an infinite stream of representations for types that
were `=:=` but not `==`. If that happened, we'd fail to terminate,
rather than judging the relationship as `false`.

[1] http://research.microsoft.com/pubs/64041/fool2007.pdf

2 files changed, 11 insertions, 15 deletions

diff --git a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala
index b60fecd66e..027da6ed50 100644
--- a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala
+++ b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala
@@ -17,20 +17,15 @@ trait TypeComparers {
   private val _pendingSubTypes = new mutable.HashSet[SubTypePair]
   def pendingSubTypes = _pendingSubTypes
 
-  class SubTypePair(val tp1: Type, val tp2: Type) {
-    override def hashCode = tp1.hashCode * 41 + tp2.hashCode
-    override def equals(other: Any) = (this eq other.asInstanceOf[AnyRef]) || (other match {
-      // suspend TypeVars in types compared by =:=,
-      // since we don't want to mutate them simply to check whether a subtype test is pending
-      // in addition to making subtyping "more correct" for type vars,
-      // it should avoid the stackoverflow that's been plaguing us (https://groups.google.com/d/topic/scala-internals/2gHzNjtB4xA/discussion)
-      // this method is only called when subtyping hits a recursion threshold (subsametypeRecursions >= LogPendingSubTypesThreshold)
-      case stp: SubTypePair =>
-        val tvars = List(tp1, stp.tp1, tp2, stp.tp2) flatMap (t => if (t.isGround) Nil else typeVarsInType(t))
-        suspendingTypeVars(tvars)(tp1 =:= stp.tp1 && tp2 =:= stp.tp2)
-      case _ =>
-        false
-    })
+  final case class SubTypePair(tp1: Type, tp2: Type) {
+    // SI-8146 we used to implement equality here in terms of pairwise =:=.
+    //         But, this was inconsistent with hashCode, which was based on the
+    //         Type#hashCode, based on the structure of types, not the meaning.
+    //         Now, we use `Type#{equals,hashCode}` as the (consistent) basis for
+    //         detecting cycles (aka keeping subtyping decidable.)
+    //
+    //         I added a tests to show that we detect the cycle: neg/t8146-no-finitary*
+
     override def toString = tp1+" <:<? "+tp2
   }
 
@@ -262,7 +257,7 @@ trait TypeComparers {
       if (subsametypeRecursions >= LogPendingSubTypesThreshold) {
         val p = new SubTypePair(tp1, tp2)
         if (pendingSubTypes(p))
-          false
+          false // see neg/t8146-no-finitary*
         else
           try {
             pendingSubTypes += p
diff --git a/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala b/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala
index c87995275f..a2d3206156 100644
--- a/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala
+++ b/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala
@@ -198,6 +198,7 @@ trait JavaUniverseForce { self: runtime.JavaUniverse  =>
     this.ErroneousCollector
     this.adaptToNewRunMap
     // inaccessible: this.commonOwnerMapObj
+    this.SubTypePair
     this.SymbolKind
     this.NoSymbol
     this.CyclicReference