improve diagnostic error for diverging implicit expansion

[scabug]

WIP: https://github.com/retronym/scala/compare/topic;diverging-explain?expand=1

example:

-starting with method tc in class CompilerHang
+starting with method tc in class CompilerHang.
+ CompilerHang.this.breakage[F]
+   CompilerHang.this.tc[M]
+     CompilerHang.this.tc[M]

[error] /Users/jason/code/shapeless/examples/src/main/scala/shapeless/examples/ordering.scala:58: diverging implicit expansion for type Ordering[shapeless.examples.OrderingExamples.Foo]
[error] starting with method hlistIsoOrdering in object OrderingExamples.
[error]  scala.this.Predef.implicitly[Ordering[shapeless.examples.OrderingExamples.Foo]]
[error]    math.this.Ordering.comparatorToOrdering[shapeless.examples.OrderingExamples.Foo]
[error]      examples.this.OrderingExamples.hlistIsoOrdering[shapeless.examples.OrderingExamples.Foo, H]
[error]        math.this.Ordering.comparatorToOrdering[shapeless.::[Int,shapeless.::[String,shapeless.HNil]]]

We could also display the corresponding complexity scores calculated in dominates.

https://twitter.com/dlwh/status/412474285806993408

diverging implicit expansions are the most infuriating error messages in the scala compiler

http://stackoverflow.com/questions/20566469/log-implicits-only-for-diverging-implicit-expansions

Other answers suggest using "-Xlog-implicits" option for debugging "diverging implicit expansion" errors. However, it also logs a lot of implicits in places unrelated to these errors. Is there some way to limit it to only explain places which produce compilation errors?

https://twitter.com/mapastr/status/449209695149236224

That moment in which _.some compiles and Some(_) in the same place doesn't with diverging implicit expansion error WTF #scala #scalaz

https://twitter.com/mnnakamura/status/434538504282861568

any idea how to get the scala compiler to stop diverging on my implicit chains?  asking for a friend. https://gist.github.com/mosesn/9014381 

https://twitter.com/nlehuen/status/237494434634297345

Gotta love Scala w/ messages like "diverging implicit expansion for type anorm.Column[B] starting with method rowToOption in object Column"

http://stackoverflow.com/questions/7950014/whats-a-diverging-implicit-expansion-scalac-message-mean

What's a “diverging implicit expansion” scalac message mean?

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-8454?orig=1
Reporter: @retronym
Affected Versions: 2.10.4, 2.11.0-RC3

[scabug]

@retronym said:
Compiling scala-breeze against this to help diagnose implicit search failures:

[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/Vector.scala:215: diverging implicit expansion for type breeze.linalg.norm.Impl2[breeze.linalg.Vector[Double],Double,Double]
[error] starting with method implicitDoubleUTag in object UFunc.
[error]  breeze.math.TensorSpace.make[breeze.linalg.Vector[Double], Int, Double]
[error]    linalg.this.Vector.canNorm[Double]
[error]      generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]        generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]   implicit val space_d = TensorSpace.make[Vector[Double], Int, Double]
[error]                                          ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/Vector.scala:216: diverging implicit expansion for type breeze.linalg.norm.Impl2[breeze.linalg.Vector[Float],Double,Double]
[error] starting with method implicitDoubleUTag in object UFunc.
[error]  breeze.math.TensorSpace.make[breeze.linalg.Vector[Float], Int, Float]
[error]    linalg.this.Vector.canNorm[Float]
[error]      generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Float, Double]
[error]        generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]   implicit val space_f = TensorSpace.make[Vector[Float], Int, Float]
[error]                                          ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/Vector.scala:217: diverging implicit expansion for type breeze.linalg.norm.Impl2[breeze.linalg.Vector[Int],Double,Double]
[error] starting with method implicitDoubleUTag in object UFunc.
[error]  breeze.math.TensorSpace.make[breeze.linalg.Vector[Int], Int, Int]
[error]    linalg.this.Vector.canNorm[Int]
[error]      generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Int, Double]
[error]        generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]   implicit val space_i = TensorSpace.make[Vector[Int], Int, Int]
[error]                                          ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/DenseVector.scala:618: diverging implicit expansion for type breeze.linalg.norm.Impl[Double,Double]
[error] starting with method implicitDoubleUTag in object UFunc.
[error]  breeze.math.TensorSpace.make[breeze.linalg.DenseVector[Double], Int, Double]
[error]    generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]      generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]   implicit val space_d = TensorSpace.make[DenseVector[Double], Int, Double]
[error]                                          ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/DenseVector.scala:619: diverging implicit expansion for type breeze.linalg.norm.Impl[Float,Double]
[error] starting with method implicitDoubleUTag in object UFunc.
[error]  breeze.math.TensorSpace.make[breeze.linalg.DenseVector[Float], Int, Float]
[error]    generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Float, Double]
[error]      generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]   implicit val space_f = TensorSpace.make[DenseVector[Float], Int, Float]
[error]                                          ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/DenseVector.scala:620: diverging implicit expansion for type breeze.linalg.norm.Impl[Int,Double]
[error] starting with method implicitDoubleUTag in object UFunc.
[error]  breeze.math.TensorSpace.make[breeze.linalg.DenseVector[Int], Int, Int]
[error]    generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Int, Double]
[error]      generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]   implicit val space_i = TensorSpace.make[DenseVector[Int], Int, Int]
[error]                                          ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/HashVector.scala:212: diverging implicit expansion for type breeze.linalg.norm.Impl[Double,Double]
[error] starting with method implicitDoubleUTag in object UFunc.
[error]  breeze.math.TensorSpace.make[breeze.linalg.HashVector[Double], Int, Double]
[error]    generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]      generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]     TensorSpace.make[HashVector[Double], Int, Double]
[error]                     ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/HashVector.scala:216: diverging implicit expansion for type breeze.linalg.norm.Impl[Float,Double]
[error] starting with method implicitDoubleUTag in object UFunc.
[error]  breeze.math.TensorSpace.make[breeze.linalg.HashVector[Float], Int, Float]
[error]    generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Float, Double]
[error]      generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]     TensorSpace.make[HashVector[Float], Int, Float]
[error]                     ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/HashVector.scala:220: diverging implicit expansion for type breeze.linalg.norm.Impl[Int,Double]
[error] starting with method implicitDoubleUTag in object UFunc.
[error]  breeze.math.TensorSpace.make[breeze.linalg.HashVector[Int], Int, Int]
[error]    generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Int, Double]
[error]      generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]     TensorSpace.make[HashVector[Int], Int, Int]
[error]                     ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/LU.scala:50: could not find implicit value for parameter bf: breeze.linalg.support.CanMapValues[breeze.linalg.DenseMatrix[T],T,Double,That]
[error]         LU_DM_Impl(v.mapValues(cast))
[error]                               ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/MutableInnerProductSpaceDenseMatrix.scala:27: diverging implicit expansion for type breeze.linalg.norm.Impl[Double,Double]
[error] starting with method implicitDoubleUTag in object UFunc.
[error]  breeze.math.MutableInnerProductSpace.make[breeze.linalg.DenseMatrix[Double], Double]
[error]    generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]      generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]     MutableInnerProductSpace.make[DenseMatrix[Double], Double]
[error]                                  ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/SparseVector.scala:315: diverging implicit expansion for type breeze.linalg.norm.Impl[Double,Double]
[error] starting with method implicitDoubleUTag in object UFunc.
[error]  breeze.math.TensorSpace.make[breeze.linalg.SparseVector[Double], Int, Double]
[error]    generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]      generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]   implicit val space_d: TensorSpace[SparseVector[Double], Int, Double] = TensorSpace.make[SparseVector[Double], Int, Double]
[error]                                                                                          ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/SparseVector.scala:318: diverging implicit expansion for type breeze.linalg.norm.Impl[Float,Double]
[error] starting with method implicitDoubleUTag in object UFunc.
[error]  breeze.math.TensorSpace.make[breeze.linalg.SparseVector[Float], Int, Float]
[error]    generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Float, Double]
[error]      generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]     TensorSpace.make[SparseVector[Float], Int, Float]
[error]                     ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/SparseVector.scala:320: diverging implicit expansion for type breeze.linalg.norm.Impl[Int,Double]
[error] starting with method implicitDoubleUTag in object UFunc.
[error]  breeze.math.TensorSpace.make[breeze.linalg.SparseVector[Int], Int, Int]
[error]    generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Int, Double]
[error]      generic.this.UFunc.implicitDoubleUTag[breeze.linalg.norm.type, Double, Double]
[error]   implicit val space_i: TensorSpace[SparseVector[Int], Int, Int] = TensorSpace.make[SparseVector[Int], Int, Int]
[error]                                                                                    ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/Vector.scala:562: can't expand macros compiled by previous versions of Scala
[error]       data(i) = (start+i*step)
[error]                         ^
[error] /Users/jason/code/breeze/src/main/scala/breeze/linalg/Vector.scala:574: can't expand macros compiled by previous versions of Scala
[error]       data(i) = (start+i*step)
[error]                         ^

[scabug]

@dlwh said:
FWIW, a large portion of my fury derived from not understanding the constraints on implicit search. Maybe document exactly why the scala compiler has decided this diverges? (constraints on the search problem, etc etc.) There's basically nothing in any document I could find that explains the greediness of how implicits are selected.

[scabug]

@retronym said (edited on Apr 4, 2014 1:22:05 PM UTC):
Here's another WIP branch for the improved diagnostic: https://github.com/retronym/scala/tree/ticket/8460-3

@dlwh The compiler is supposed to tolerate one divergent path in the implicit search. If a second path is found, it can abort the search. The implementation of this is a touch buggy and can sometimes explore a bit further, but that's the intent.

The implicit search space is explored in an order driven by the specificity of the candidates. The rules are analagous to those of static overload resolution. The levers are pretty crude, but you can deprioritize an implicit by putting it in a superclass of a the one that defined a competing implicit.

This criteria is used to determine a winner if we have multiple eligible results. With this in mind, the compiler can pre-sort candidates based on the specificity, and avoid exploring less specific candidates if a more-specific result has already been found.

See the neg and pos examples from this commit [1] for an example of how to use this to avoid divergence.

Here's an example of how to use this to speedup implicit search [2].

[1] https://github.com/retronym/scala/tree/ticket/8460-3
[2] NICTA/scoobi#324

[scabug]

@dlwh said:
Thanks so much!

[scabug]

@retronym said:
I forgot one point: type inference constraints gathered in the implicit search for the first implicit parameter are substituted into the type of the second parameter before we search for it, and so on. So the order of implicit parameters matters.

[scabug]

@dlwh said:
Right, I figured that one out eventually. That's definitely the source of most of the diverging implicit expansions I've encountered.

[scabug]

@dlwh said:
Hey Jason,

I hit another one of these that I couldn't figure out and thought I might try out your branch for tracking it down. Is it in a state where it might be usable?

Thanks!

[tribbloid]

Any recommendation on this?

I've asked the same question for splain plugin (merged in scala 2.13.6), still no one has figured out how to do it with the latest compiler