2.12 compiler fails to infer type for complex nested Map involving F-bounded type

[wboult]

reproduction steps

using Scala 2.12.13,

The following code seems to never compile, presumably the compiler gets into some kind of trouble while inferring the type of the map being constructed:

case class DocumentId(tpe: String, value: String)

sealed trait KeyType extends Product with Serializable
case class StringKey(k: String) extends KeyType
case class DateKey(k: String) extends KeyType

object Example {
  // ---- No explicit type provided ----
  val expected = Map(
    DocumentId("doc1", "1") -> Set(
      Map(
        StringKey("businessname") -> "eagle invest",
        DateKey("start_date") -> java.sql.Date.valueOf("2017-01-01")
      )
    ),
    DocumentId("doc2", "1") -> Set(
      Map(StringKey("address") -> "London, UK"),
      Map(StringKey("address") -> "London")
    )
  )
}

// compiler falls over trying to infer Map[DocumentId, Set[Map[Any, Any]]]

When I add an explicit type, the code compiles fine:

case class DocumentId(tpe: String, value: String)

sealed trait KeyType extends Product with Serializable
case class StringKey(k: String) extends KeyType
case class DateKey(k: String) extends KeyType

object Example {
  // ---- Explicit type provided ----
  val expected: Map[DocumentId, Set[Map[Any, Any]]] = Map(
    DocumentId("doc1", "1") -> Set(
      Map(
        StringKey("businessname") -> "eagle invest",
        DateKey("start_date") -> java.sql.Date.valueOf("2017-01-01")
      )
    ),
    DocumentId("doc2", "1") -> Set(
      Map(StringKey("address") -> "London, UK"),
      Map(StringKey("address") -> "London")
    )
  )
}

The same code compiles fine without any explicit type in both 2.11 and 2.13 interestingly.
Examples on Scastie:

• Without explicit type: https://scastie.scala-lang.org/ZvGH9eW6QAKyjZpenqr2AA
• With explicit type: https://scastie.scala-lang.org/Q49YYU8ZTmOmaPV9Ao4A6g
• 2.11 without explicit type: https://scastie.scala-lang.org/8fu5mPimQziUXUwkpExO3w
• 2.13 without explicit type: https://scastie.scala-lang.org/dHQQpGuLR2OmnP1BuCj9Eg

problem

compiler gets stuck and eventually dies

[lrytz]

Nice minimization!

cc @retronym, this could lead to useful insights

[wboult]

It actually came from some test code I was porting from 2.11! It appears it can be simplified a bit further:

object Example {
  val expected = Map(
    1 -> Set(
      Map(
        "a" -> "b",
        1 -> new java.util.Date()
      )
    ),
    2 -> Set(
      Map("c" -> "d")
    )
  )
}

I've also tried switching the Date value to try other classes and of the ones that I tried, java.sql.Date and java.util.Date were the only ones that worked.

[Jasper-M]

When you change it to this, compilation does finish in finite time but it goes very slowly.

object Example {
  val expected = Map(
    1 -> Set(
      Map(
        "a" -> (??? : Comparable[String]),
        1 -> (??? : Comparable[Int])
      )
    ),
    2 -> Set(
      Map("c" -> (??? : Comparable[String]))
    )
  )
}

And if I change Int to Option[_] it goes a lot slower still.

@wboult's last example also finishes after a couple of minutes, but seems to require a heap of 3GB.

[SethTisue]

2.13 compiles the code just fine, but that doesn't prove that the underlying compiler issue is fixed; it could be simply that the 2.13 collections are different. (though, are they, in a way that actually comes into play here? it appears that CanBuildFrom is not in play here)

as you would expect, the problem isn't reproducible in Scala 3

[dwijnand]

The mentions of java.util.Date, java.sql.Date and Comparable remind me of #12404, where I discovered the scala compiler doesn't like types like T <: java.lang.Object with java.lang.Comparable[_ >: T], while the java compiler is perfectly happy with a type like T extends Object & Comparable<? super T>. So perhaps there's an issue with lubbing F-bounded types in 2.12?