Compiler crash due to memory exhaustion

[jpallas]

dotty 0.4.0-RC1 dies by running out of memory when asked to compile Nil.min in the REPL or the compiler.

[nicolasstucki]

This does not only happen in the REPL.

[nicolasstucki]

The compiler cant figure out the implicit Ordering[T1].

ambiguous implicits for scala.math.Ordering[T1]: scala.math.Ordering.Long.type @ 0, scala.math.Ordering.Short.type @ 0
>>>> StoredError: ambiguous implicits: both object Long in object Ordering and object Short in object Ordering match type scala.math.Ordering[T1] of parameter ord1 of method Tuple6 in object Ordering
>>>> StoredError: No implicit Ordering defined for T

where:    T is a type variable
.
>>>> StoredError: No implicit Ordering defined for T1

where:    T1 is a type variable
.
>>>> StoredError: no implicit argument of type java.util.Comparator[T1] found for parameter cmp of method comparatorToOrdering in trait LowPriorityOrderingImplicits
>>>> StoredError: No implicit Ordering defined for T1

where:    T1 is a type variable
.
>>>> StoredError: No implicit Ordering defined for T1

where:    T1 is a type variable
.
>>>> StoredError: No implicit Ordering defined for T1

where:    T1 is a type variable
.
>>>> StoredError: No implicit Ordering defined for T1

where:    T1 is a type variable
.
>>>> StoredError: No implicit Ordering defined for T1

where:    T1 is a type variable
.
>>>> StoredError: No implicit Ordering defined for T1

where:    T1 is a type variable
.
>>>> StoredError: No implicit Ordering defined for T

where:    T is a type variable
.
>>>> StoredError: No implicit Ordering defined for T1

where:    T1 is a type variable
.
ambiguous implicits for scala.math.Ordering[T1]: scala.math.Ordering.Long.type @ 0, scala.math.Ordering.Short.type @ 0
>>>> StoredError: ambiguous implicits: both object Long in object Ordering and object Short in object Ordering match type scala.math.Ordering[T1] of parameter ord1 of method Tuple8 in object Ordering
>>>> StoredError: No implicit Ordering defined for T

where:    T is a type variable
.
>>>> StoredError: No implicit Ordering defined for T1

where:    T1 is a type variable
.
>>>> StoredError: no implicit argument of type java.util.Comparator[T1] found for parameter cmp of method comparatorToOrdering in trait LowPriorityOrderingImplicits
>>>> StoredError: No implicit Ordering defined for T1

where:    T1 is a type variable

[nicolasstucki]

The issue that as the type is unbounded it will try all possible types which include tuples and nested tuples. Such as:

// in scala.math.Ordering.scala
implicit def Tuple5[T1, T2, T3, T4, T5](implicit ord1: Ordering[T1], ord2: Ordering[T2], ord3: Ordering[T3], ord4: Ordering[T4], ord5: Ordering[T5]): Ordering[(T1, T2, T3, T4, T5)]

In these cases the implicit search tree is extremely wide.

[nicolasstucki]

Here is a self contained example that produces the same result.

object Foo {
  implicit def boolean: Ordering2[Boolean] = ???
  implicit def char: Ordering2[Char] = ???
  implicit def byte: Ordering2[Byte] = ???
  implicit def short: Ordering2[Short] = ???
  implicit def int: Ordering2[Int] = ???
  implicit def long: Ordering2[Long] = ???
  implicit def float: Ordering2[Float] = ???
  implicit def double: Ordering2[Double] = ???
  implicit def unit: Ordering2[Unit] = ???
  implicit def string: Ordering2[String] = ???
  implicit def bigInt: Ordering2[BigInt] = ???
  implicit def bigDec: Ordering2[BigDecimal] = ???
  implicit def Option[T](implicit ord: Ordering[T]): Ordering[Option[T]] = ???
  implicit def Iterable[T](implicit ord: Ordering[T]): Ordering[Iterable[T]] = ???
  implicit def Tuple2[T1, T2](implicit ord1: Ordering2[T1], ord2: Ordering2[T2]): Ordering2[(T1, T2)] = ???
  implicit def Tuple3[T1, T2, T3](implicit ord1: Ordering2[T1], ord2: Ordering2[T2], ord3: Ordering2[T3]) : Ordering2[(T1, T2, T3)] = ???
  implicit def Tuple4[T1, T2, T3, T4](implicit ord1: Ordering2[T1], ord2: Ordering2[T2], ord3: Ordering2[T3], ord4: Ordering2[T4]) : Ordering2[(T1, T2, T3, T4)] = ???
  implicit def Tuple5[T1, T2, T3, T4, T5](implicit ord1: Ordering2[T1], ord2: Ordering2[T2], ord3: Ordering2[T3], ord4: Ordering2[T4], ord5: Ordering2[T5]): Ordering2[(T1, T2, T3, T4, T5)] = ???
  implicit def Tuple6[T1, T2, T3, T4, T5, T6](implicit ord1: Ordering2[T1], ord2: Ordering2[T2], ord3: Ordering2[T3], ord4: Ordering2[T4], ord5: Ordering2[T5], ord6: Ordering2[T6]): Ordering2[(T1, T2, T3, T4, T5, T6)] = ???
  implicit def Tuple7[T1, T2, T3, T4, T5, T6, T7](implicit ord1: Ordering2[T1], ord2: Ordering2[T2], ord3: Ordering2[T3], ord4: Ordering2[T4], ord5: Ordering2[T5], ord6: Ordering2[T6], ord7: Ordering2[T7]): Ordering2[(T1, T2, T3, T4, T5, T6, T7)] = ???
  implicit def Tuple8[T1, T2, T3, T4, T5, T6, T7, T8](implicit ord1: Ordering2[T1], ord2: Ordering2[T2], ord3: Ordering2[T3], ord4: Ordering2[T4], ord5: Ordering2[T5], ord6: Ordering2[T6], ord7: Ordering2[T7], ord8: Ordering2[T8]): Ordering2[(T1, T2, T3, T4, T5, T6, T7, T8)] = ???
  implicit def Tuple9[T1, T2, T3, T4, T5, T6, T7, T8, T9](implicit ord1: Ordering2[T1], ord2: Ordering2[T2], ord3: Ordering2[T3], ord4: Ordering2[T4], ord5: Ordering2[T5], ord6: Ordering2[T6], ord7: Ordering2[T7], ord8 : Ordering2[T8], ord9: Ordering2[T9]): Ordering2[(T1, T2, T3, T4, T5, T6, T7, T8, T9)] = ???
  def min[B](implicit cmp: Ordering2[B]): Unit = ???
  min
}

trait Ordering2[T]

It takes around one minute to compile on my machine.

[OlivierBlanvillain]

I believe this is because implicit search is currently exhaustive up to depth XminImplicitSearchDepth (default = 5), divergence criterion are only considered passed that threathold (see this comment).

[OlivierBlanvillain]

dotr -Xmin-implicit-search-depth 2                                                                     
scala> Nil.min // Almost instant
1 |Nil.min
  |       ^
  |ambiguous implicits: both object Long in object Ordering and object Short in object Ordering match type scala.math.Ordering[B] of parameter cm
p of method min in trait TraversableOnce                                                                                                         

[odersky]

Fixed by #3421