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
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With