StackOverflow in implicit search (getParts)

[adriaanm]

trait Cmp[T] { def compareTo(o: T): Int }
class K[T] extends Cmp[K[_ >: T]] { def compareTo(that: K[_ >: T]): Int = ??? }

object Tst {
  (new K[String]).compareTo(new K[Int])
}

stack overflows in 2.13.x -- haven't checked older versions

+ marks the spot

--- i/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ w/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -1367,6 +1367,7 @@ trait Implicits {
        */
       def getParts(tp: Type)(implicit infoMap: InfoMap, seen: mutable.HashSet[Type], pending: Set[Symbol]): Unit = {
         if (seen add tp) tp match {
+//          case _ if seen exists (_ =:= tp) => println(s"already had $tp in $seen")
           case TypeRef(pre, sym, args) =>
             if (sym.isClass && !sym.isRoot &&
                 (isScala213 || !sym.isAnonOrRefinementClass)) {

[adriaanm]

uncommenting that quick fix (this is performance critical, so we can't just use =:=), you get the (expected) type error:

 type mismatch;
 found   : K[Int]
 required: K[_ >: String]
Note: Int <: Any, but class K is invariant in type T.
You may wish to define T as +T instead. (SLS 4.5)
  (new K[String]).compareTo(new K[Int])
                            ^
one error found

[joroKr21]

But in that patch you just added tp to the map, of course it exists there 😄

[adriaanm]

Whoops -- I guess I was thinking in immutable maps, or just being confused as usual 😊

[SethTisue]

stack trace as of 2.13.2:

java.lang.StackOverflowError
	at scala.reflect.internal.tpe.TypeMaps$AsSeenFromMap.thisTypeAsSeen(TypeMaps.scala:650)
	at scala.reflect.internal.tpe.TypeMaps$AsSeenFromMap.apply(TypeMaps.scala:442)
	at scala.reflect.internal.Types$TypeRef.mapOver(Types.scala:2358)
	at scala.reflect.internal.tpe.TypeMaps$AsSeenFromMap.apply(TypeMaps.scala:445)
	at scala.reflect.internal.Types$TypeBounds.mapOver(Types.scala:1577)
	at scala.reflect.internal.tpe.TypeMaps$AsSeenFromMap.apply(TypeMaps.scala:445)
	at scala.reflect.internal.tpe.TypeMaps$TypeMap.applyToSymbolInfo(TypeMaps.scala:123)
	at scala.reflect.internal.tpe.TypeMaps$TypeMap.loop$1(TypeMaps.scala:117)
	at scala.reflect.internal.tpe.TypeMaps$TypeMap.firstChangedSymbol(TypeMaps.scala:121)
	at scala.reflect.internal.tpe.TypeMaps$TypeMap.mapOver(TypeMaps.scala:135)
	at scala.reflect.internal.Types$ExistentialType.mapOver(Types.scala:3211)
	at scala.reflect.internal.tpe.TypeMaps$AsSeenFromMap.apply(TypeMaps.scala:445)
	at scala.reflect.internal.tpe.TypeMaps$AsSeenFromMap.apply(TypeMaps.scala:415)
	at scala.reflect.internal.Types$TypeRef.mapOver(Types.scala:2367)
	at scala.reflect.internal.tpe.TypeMaps$AsSeenFromMap.apply(TypeMaps.scala:445)
	at scala.reflect.internal.Types$Type.asSeenFrom(Types.scala:698)
	at scala.reflect.internal.Types$TypeRef.seenFromOwnerInstantiated$1(Types.scala:2486)
	at scala.reflect.internal.Types$TypeRef.relativize(Types.scala:2490)
	at scala.reflect.internal.Types$TypeRef.$anonfun$baseTypeSeqImpl$2(Types.scala:2615)
	at scala.reflect.internal.BaseTypeSeqs$BaseTypeSeq.map(BaseTypeSeqs.scala:157)
	at scala.reflect.internal.Types$TypeRef.baseTypeSeqImpl(Types.scala:2615)
	at scala.reflect.internal.Types.defineBaseTypeSeqOfTypeRef(Types.scala:2789)
	at scala.reflect.internal.Types.defineBaseTypeSeqOfTypeRef$(Types.scala:2780)
	at scala.reflect.internal.SymbolTable.defineBaseTypeSeqOfTypeRef(SymbolTable.scala:28)
	at scala.reflect.internal.Types$TypeRef.baseTypeSeq(Types.scala:2622)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.getClassParts$1(Implicits.scala:1359)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.getParts$1(Implicits.scala:1394)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.$anonfun$companionImplicitMap$10(Implicits.scala:1395)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.getParts$1(Implicits.scala:1395)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.getClassParts$1(Implicits.scala:1362)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.getParts$1(Implicits.scala:1394)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.$anonfun$companionImplicitMap$10(Implicits.scala:1395)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.getParts$1(Implicits.scala:1395)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.getClassParts$1(Implicits.scala:1362)
	at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.getParts$1(Implicits.scala:1394)

[SethTisue]

#12001 is a likely duplicate, so I've closed it. there, the code is

class Event[+T](weight: Int, data: T) extends Ordered[Event[_ <: T]] {
  def compare(that: Event[_ <: T]): Int = weight - that.weight
}

[joroKr21]

diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
index b39ff3b7c4..44c926a6bc 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -1359,6 +1359,7 @@ trait Implicits {
             val bts = (if(infos1.isEmpty) tp else tp.map(_.withoutAnnotations)).baseTypeSeq
             var i = 1
             while (i < bts.length) {
+              println(bts(i))
               getParts(bts(i))
               i += 1
             }
@@ -1390,8 +1391,11 @@ trait Implicits {
                       result
                   }
                 }
-              else
+              else {
+                println(tp)
                 getClassParts(tp)
+              }
+              args foreach println
               args foreach getParts
             } else if (sym.isAliasType) {
               getParts(tp.normalize) // scala/bug#7180 Normalize needed to expand HK type refs

I guess _$1 is a fresh skolem:

Object
Any
Any
K[Int]
K[_ >: String]
K[Int]
Cmp[K[_ >: Int]]
Cmp[K[_ >: Int]]
Object
Any
$iw
Object
java.io.Serializable
Any
Any
Object
java.io.Serializable
Any
K[_ >: Int]
K[_$1]
Cmp[K[_ >: _$1]]
Cmp[K[_ >: _$1]]
Object
Any
K[_ >: _$1]
K[_$1]
Cmp[K[_ >: _$1]]
Cmp[K[_ >: _$1]]
Object
Any
...

[eshu]

#12001 is a likely duplicate, so I've closed it. there, the code is

class Event[+T](weight: Int, data: T) extends Ordered[Event[_ <: T]] {
  def compare(that: Event[_ <: T]): Int = weight - that.weight
}

The iteresting part in this example is that if I replace weight - that.weight with ???, it shows a correct error instead stack overflow exception.

[joroKr21]

So this happens with generic F-bounded types (and unfortunately Comparable / Ordered are such types). When the types don't match the compiler will try to find an implicit conversion to the expected type. But the base type sequence of these types expands endlessly:

K[Int] <: Cmp[K[a] forSome { type a >: Int }]
K[a] <: Cmp[K[b] forSome { type b >: a }]
K[b] <: Cmp[K[c] forSome { type c >: b }]

and so on

[unkarjedy]

Faced same exception in 2.13.7.
Can't create a minimum reproducible example yet.