¿Qué significa un mensaje scalac de "expansión implícita divergente"?

Question

Creé un pequeño programa de ejemplo para intentar averiguar por qué un programa más grande no se estaba compilando.

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

Cuando doy de comer a este Scala me sale:

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 

El uso de "-explaintypes" no ofrece nada más. Sin embargo, "-Xlog-implicits" ofrece lo siguiente:

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 

pero eso no me ayuda. ¿Te preguntas qué significa este mensaje y cómo resolverlo?

[Actualizar] El mismo código actual con Scala 2.11.0 produce un segundo mensaje de error además del primero sobre la "expansión implícita divergente". Este segundo mensaje es bastante útil.

$ 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

Poco: messaage su error, simplemente debe ser de error: No coinciden los tipos encontrado: Orden [Int] requiere: Int.

La razón es simplemente que en Ordered[A], la comparación se hacen con A, no con otros ordenamientos

def <(that: A): Boolean 

eso se debe o1 < 2, no o1 < o2. (Por supuesto 1 < 2 también funciona, pero espero que su código es sólo una versión simplificada de otra cosa)

Sin embargo, antes de que los informes del compilador este simple error, si tiene que buscar si alguna implícita en su alcance podría solucionar el problema. Podría convertir el Ordering[Int]o2 en Int (no puede) o el Ordering[Int]o1 en algo que tiene un método def <(Ordered[Int]), por ejemplo Ordered[Ordered[Int]]. Y sucede que debe detener la búsqueda porque parece que podría continuar indefinidamente en una especie de ciclo. La regla se da en la especificación, p. 107 a 109 (especificación para la versión 2.9). Sin embargo, la regla para detener la búsqueda es pesimista, y es posible que deje caer una línea de búsqueda que podría haber tenido éxito, por lo que el compilador cree que debe informarlo. Si bien, de hecho, la mayoría de las veces como aquí, el ciclo se eliminó adecuadamente y no existía ninguna solución. Esto es lo que lo convierte en un mensaje de error sorprendente. Creo que el error más simple debe ser informado también, y más prominente.

Permítanme dar algunas explicaciones limitadas sobre por qué podría haber un ciclo en la búsqueda implícita. Puede haber

implicit def f(implicit a: A): B 

lo que significa que si tiene una A implícita, también tiene una B implícita. Entonces eso hace un gráfico entre tipos: A proporciona B. Es más complejo que eso, en realidad es un hipergraph: 'implcit def f (implícito a: A, implícito b: B): C': A y B proporciona C.

Con genéricos, tiene un número infinito de tipos y un gráfico (hiper) infinito, hecho aún más complejo por subtipado (si necesita una A, cualquier subtipo de A lo hará. Agregue la regla de subtipificación implícita por covarianza/contravariancia)

El gráfico puede contener un ciclo: para obtener una A, puede proporcionar una B, obtener una B, solo puede proporcionar una C, para obtener una C puede proporcionar una A.Eso resume si usted proporciona una A, obtiene una A, lo cual es inútil, y que las líneas de búsqueda deben ser descartadas. Esto no es un problema, en este caso, es un ciclo real, y no hay riesgo de eludir una posible solución al dejarlo caer.

Pero puede ser más complejo, ya que el gráfico es infinito, la búsqueda puede ser infinita sin un ciclo exacto. Si tiene

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

entonces si nos fijamos para X[Int], es posible que busque X[X[Int]] lugar, pero luego, con la misma regla, buscar X[X[X[Int]]] y así sucesivamente. No es exactamente el ciclo, sin embargo, el compilador no persigue esas líneas y lo llama divergente. Excepto que puede haber un implícito X[X[X...X[Int]]]]] en algún ámbito implícito que lo haga exitoso. Esta es la razón por la cual el compilador informa que esta línea de exploración fue descartada.