What's a "diverging implicit expansion" scalac message mean?

Question

I created a small example program to try to work out why a larger program wasn't compiling.

val o1: Ordered[Int] = 1
val o2: Ordered[Int] = 2
println(o1 < o2)

When I feed this to scala I get:

Ordered.scala:3: error: diverging implicit expansion for type scala.math.Ordering[Ordered[Int]]
starting with method ordered in trait LowPriorityOrderingImplicits
println(o1 < o2)
        ^
one error found

Using "-explaintypes" offers nothing further. However, "-Xlog-implicits" gives the following:

math.this.Ordering.comparatorToOrdering is not a valid implicit value for scala.math.Ordering[Ordered[Int]] because:
could not find implicit value for parameter cmp: java.util.Comparator[Ordered[Int]]
scala.this.Predef.conforms is not a valid implicit value for Ordered[Int] => java.lang.Comparable[Ordered[Int]] because:
type mismatch;
 found   : <:<[Ordered[Int],Ordered[Int]]
 required: Ordered[Int] => java.lang.Comparable[Ordered[Int]]
/Users/steshaw/Projects/playground/scala/programming-in-scala/Ordered.scala:3: error: diverging implicit expansion for type scala.math.Ordering[Ordered[Int]]
starting with method ordered in trait LowPriorityOrderingImplicits
println(o1 < o2)
        ^
math.this.Ordering.comparatorToOrdering is not a valid implicit value for scala.math.Ordering[Ordered[Int]] because:
could not find implicit value for parameter cmp: java.util.Comparator[Ordered[Int]]
scala.this.Predef.conforms is not a valid implicit value for Ordered[Int] => java.lang.Comparable[Ordered[Int]] because:
type mismatch;
 found   : <:<[Ordered[Int],Ordered[Int]]
 required: Ordered[Int] => java.lang.Comparable[Ordered[Int]]
one error found

but that's not helping me. Wondering what this message means and how to resolve it?

[Update] The same code today with Scala 2.11.0 produces a second error message in addition to the first about the "diverging implicit expansion". This second message is quite helpful.

$ scala Ordered.scala
Ordered.scala:3: error: diverging implicit expansion for type scala.math.Ordering[Ordered[Int]]
starting with method comparatorToOrdering in trait LowPriorityOrderingImplicits
println(o1 < o2)
        ^
/Users/steshaw/Projects/playground/scala/scalac-errors/Ordered.scala:3: error: type mismatch;
 found   : Ordered[Int]
 required: Int
println(o1 < o2)
             ^
two errors found

Answer 1

Shortly: your error message should simply be

error: type mismatch 
found: Ordering[Int]
required: Int.

The reason is simply that in Ordered[A], comparison are done with A, not with other orderings

def <(that: A): Boolean

That should be o1 < 2, not o1 < o2. (of course 1 < 2 works too, but I expect your code is just a simplified version of something else)

However, before the compiler reports this simple error, if has to search whether some implicit in scope could fix the problem. It might convert the Ordering[Int] o2 to Int (cannot), or the Ordering[Int] o1 to something that has a def <(Ordered[Int]) method, for instance Ordered[Ordered[Int]]. And it happens that it must stop the search because it seems it could goes on indefinitely in kind of a cycle. The rule is given in the spec, p. 107 to 109 (spec for version 2.9). However, the rule for stopping the search is pessimistic, and it is possible that it drops a line of search that might have been successful, so the compiler feels it must report that. While in fact, most of the time as in here, the cycle was properly dropped, and no solution existed. This is what makes for a surprising error message. I think the simpler error should be reported too, and more prominently.

Let me give some limited explanations on why there might be cycle in implicit search. There may be

implicit def f(implicit a: A): B

which means that if you have an implicit A, you have an implicit B too. So that makes a graph between types: A provides B. It is more complex than that, it is actually an hypergraph: implcit def f(implicit a: A, implicit b: B): C: A and B provides C.

With generics, you have an infinite number of type and an infinite (hyper)graph, made still more complex by subtyping (if you need an A, any subtype of A will do. Add the subtyping rule implied by covariance/contravariance)

The graph may contain cycle: to get an A, you may just provide a B; to get a B, you may just provide a C; to get a C, you may just provide an A. That sums up to if you provide an A, you get an A, which is useless, and that line of search has to be dropped. This is not a problem in this case: it is an actual cycle, and there is no risk of bypassing a possible solution by dropping it.

But it may be more complex. As the graph is infinite, the search might be infinite without exactly cycling. If you have

implicit def[A](x: X[X[A]]): X[A] 

then if you look for X[Int], you may look for X[X[Int]] instead, but then, with the same rule, you look for X[X[X[Int]]] and so on. It does not exactly cycle, yet the compiler does not pursue those lines and calls it diverging. Except that there may be an implicit X[X[X...X[Int]]]]] in implicit scope somewhere that would make it success. This is why the compiler reports that this line of exploration was dropped.