compile error "diverging implicit expansion for type scala.math.Ordering ..."

[scabug]

object Test2 {
   class TimeStamp(val toLong: Long) extends AnyVal with Ordered[TimeStamp] {
     def compare(that: TimeStamp) = java.lang.Long.compare(toLong, that.toLong)
   }

   // while looking irrelevant, these two code lines are needed to reproduce the bug
   case class L(time: TimeStamp)
   List.empty[L].sortBy(_.time)

   // this line triggers compiler error "diverging implicit expansion for type scala.math.Ordering[(Int, Test2.TimeStamp)] starting with method $conforms in object Predef"
   List.empty[(Int,TimeStamp)].sorted  
}                                      

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-8541?orig=1
Reporter: Denis Petrov (denis)
Affected Versions: 2.11.0
See #7291

[scabug]

@retronym said:
Also fails under 2.10 with -Xdivergence211 (#7291)

% scalac-hash v2.10.4 -Xdivergence211 test/files/pos/t8541.scala
test/files/pos/t8541.scala:11: error: diverging implicit expansion for type scala.math.Ordering[(Int, Test2.TimeStamp)]
starting with method orderingToOrdered in object Ordered
   List.empty[(Int,TimeStamp)].sorted
                               ^

[scabug]

@retronym said (edited on Apr 27, 2014 8:33:47 AM UTC):
This is such a fragile area. The root problem is that we have implicits defined in the companion scope of both Ordering and of Ordered, and there is no means to prioritize one over the other, which is the usual means to shephard implicit search away from divergence errors.

Here's a aimilar example, teased apart from the standard library:

% scalac-hash v2.10.4 test/files/pos/t8541.scala

% scalac-hash v2.10.4 -Xdivergence211 test/files/pos/t8541.scala
test/files/pos/t8541.scala:6: error: diverging implicit expansion for type Test.Ordering[Test2.TimeStamp]
starting with method orderingToOrdered in object Implicits2
  implicitly[Ordering[TimeStamp]]
            ^
test/files/pos/t8541.scala:7: error: diverging implicit expansion for type Test.Ordering[(Int, Test2.TimeStamp)]
starting with method orderingToOrdered in object Implicits2
  implicitly[Ordering[(Int,TimeStamp)]]
            ^
two errors found

% cat test/files/pos/t8541.scala

object Test2 {
  import Test._, Implicits1._, Implicits2._

  abstract class TimeStamp(val toLong: Long) extends Ordered[TimeStamp]

  implicitly[Ordering[TimeStamp]]
  implicitly[Ordering[(Int,TimeStamp)]]
}

object Test {
  class Ordering[T]
  abstract class Ordered[T] extends java.lang.Comparable[T]
  trait Low {
     implicit def ordered[A <% java.lang.Comparable[A]]: Ordering[A] = ???
     implicit def comparatorToOrdering[A](implicit cmp: java.util.Comparator[A]): Ordering[A] = ???
  }
  object Implicits1 extends Low {
    implicit def OrderingInt: Ordering[Int] = ???
    implicit def OrderingTuple2[A: Ordering, B: Ordering]: Ordering[(A, B)] = ???

  }
  object Implicits2 {
    implicit def orderingToOrdered[T](x: T)(implicit ord: Ordering[T]): Ordered[T] = ???
  }
}

The troublesome implicit is:

implicit def ordered[A <% java.lang.Comparable[A]]: Ordering[A] = ???

This should have instead been declared as:

implicit def ordered[A <: java.lang.Comparable[A]]: Ordering[A] = ???

But it is pretty hard to fix this sort of design error with our backwards compat. constraints.

My example above actually works again in 2.11.0, after a last minute tweak we made to divergence checking to try to make it more lenient and more compatible with 2.11.0. But your example is not rescued. I haven't dug in to the exact reason for that.

My recommendation to work around this issue is to explicitly publish an Orderinging[Timestamp] instance, rather than relying on the implicit from Comparable[T] => Ordering[T]

object Test2 {
   class TimeStamp(val toLong: Long) extends AnyVal
   object TimeStamp {
     implicit def TimeStampOrdering: Ordering[TimeStamp] = Ordering.by(_.toLong)
   }
 
   // while looking irrelevant, these two code lines are needed to reproduce the bug
   case class L(time: TimeStamp)
   List.empty[L].sortBy(_.time)
 
   // this line triggers compiler error "diverging implicit expansion for type scala.math.Ordering[(Int, Test2.TimeStamp)] starting with method $conforms in object Predef"
   List.empty[(Int,TimeStamp)].sorted  
}

[scabug]

Denis Petrov (denis) said:
It is easy to work around just by rearrange lines of code.

What is weird is the error appears in so simple code, without any esoteric features of scala, in the code that any beginner could write.

[scabug]

@retronym said:
Another reproduction for the same underlying problem was provided in #8541.

[scabug]

@adriaanm said:
We should look into cleaning this up through deprecation in 2.12, if there's no better solution.

[scabug]

James Koch (james.koch) said:
FWIW, the really spooky thing to me is what Denis flagged w/ his comment these two code lines are needed to reproduce the bug. The two different calls which accept an implicit argument would seem to a layperson to be entirely independent, and yet you need both to reproduce the issue.

I hit this in a more complex file, with about ten calls to methods like these, and worked around it by adding import Ordering.Tuple2 at the top of the file.