Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

improve diagnostic error for diverging implicit expansion #8454

Open
scabug opened this issue Mar 28, 2014 · 9 comments
Open

improve diagnostic error for diverging implicit expansion #8454

scabug opened this issue Mar 28, 2014 · 9 comments
Labels
enhancement infer usability
Milestone
Backlog

Comments

@scabug
Copy link

scabug commented Mar 28, 2014

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
Copy link
Author

scabug commented Mar 28, 2014

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

@scabug
Copy link
Author

scabug commented Mar 28, 2014

@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
Copy link
Author

scabug commented Mar 28, 2014

@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
Copy link
Author

scabug commented Apr 4, 2014

@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
Copy link
Author

scabug commented Apr 4, 2014

@dlwh said:
Thanks so much!

@scabug
Copy link
Author

scabug commented Apr 4, 2014

@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
Copy link
Author

scabug commented Apr 4, 2014

@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
Copy link
Author

scabug commented Nov 17, 2015

@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!

@scabug scabug mentioned this issue Apr 7, 2017
Open
@retronym retronym mentioned this issue Jun 26, 2017
Closed
@tribbloid
Copy link

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

@scala scala deleted a comment from scabug Oct 6, 2021
@scala scala deleted a comment from scabug Oct 6, 2021
@SethTisue SethTisue added this to the Backlog milestone Aug 25, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement infer usability
Projects
None yet
Milestone
Backlog
Development

No branches or pull requests
4 participants
@retronym @SethTisue @tribbloid @scabug