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

"diverging implicit expansion" error: sensitive to lexicographic file ordering, breaks incremental compilation #10222

Open
scabug opened this issue Mar 9, 2017 · 5 comments

Comments

@scabug
Copy link

scabug commented Mar 9, 2017

tl;dr: if the compiler implicitly constructs an Ordering[T] from a Comparable[T] at some point, then later implicit construction of an Ordering[(T, U)] from an Ordered[T] (in unrelated code) will throw a "divergent implicit expansion" error.

This behavior is sensitive to the order in which (otherwise unrelated) files are compiled, and also reliably puts zinc in an inconsistent state where a clean changes whether compilation succeeds or fails.

A minimal repro can be found at ryan-williams/scalac-bug, and is reproduced below:

B.scala
trait B extends Comparable[B]
object B {
  /**
   * Iff this line is compiled before [[C]] below, then [[C]] will throw a "divergent implicit 
   * expansion" error, though the compiler should not carry any state from here to there.
   */
  implicitly[Ordering[B]]
}
C.scala
case class C(n: Int) extends Ordered[C] {
  override def compare(that: C): Int = n - that.n
}

object C {
  /**
   * Fails to compile when this class is lexicographically greater than [[B]].
   */
  implicitly[Ordering[(C, Boolean)]]
}

Repro steps

Compiling B.scala and C.scala: fails:
$ scalac src/main/scala/org/abc/{B,C}.scala
src/main/scala/org/abc/C.scala:11: error: diverging implicit expansion for type Ordering[(org.abc.C, Boolean)]
starting with method $conforms in object Predef
  implicitly[Ordering[(C, Boolean)]]
            ^
one error found
Compiling C.scala and B.scala: succeeds
$ scalac src/main/scala/org/abc/{C,B}.scala
$ rm -rf org  # clean up generated .class files
sbt compile a working branch causes broken branch to require sbt clean
$ git checkout spoil
$ sbt clean compile    # succeeds, correctly
$ git checkout master
$ sbt compile          # succeeds, (erroneously?)
$ sbt clean compile    # fails, (correctly?)

Discussion

This looks similar to #8541 and #10080, but I've filed it separately as there are two things on display here that I didn't see explicitly discussed in them:

  • the lexicographic ordering of absolute paths to the files in question determines whether compilation will succeed or fail
  • the sbt compiler can be put in an inconsistent state where an sbt clean changes whether compilation succeeds or fails.

I ran in to this in a very large codebase and had a very confusing time narrowing down the interactions that were causing it, since they turned out to involve a specific lexicographic ordering of two seemingly-unrelated parts of the codebase as well as one kind of compilation corrupting the compiler's state and causing another compilation to succeed or fail depending on whether an sbt clean was run.

@scabug
Copy link
Author

scabug commented Mar 9, 2017

Imported From: https://issues.scala-lang.org/browse/SI-10222?orig=1
Reporter: Ryan Williams (rdub)
Affected Versions: 2.11.8, 2.12.1
See #8541, #10080

@retronym
Copy link
Member

Yes, this is basically the same as #8541. This implicit is to blame.

  type AsComparable[A] = A => Comparable[A]

  /** This would conflict with all the nice implicit Orderings
   *  available, but thanks to the magic of prioritized implicits
   *  via subclassing we can make `Ordered[A] => Ordering[A]` only
   *  turn up if nothing else works.  Since `Ordered[A]` extends
   *  `Comparable[A]` anyway, we can throw in some Java interop too.
   */
  implicit def ordered[A: AsComparable]: Ordering[A] = new Ordering[A] {
    def compare(x: A, y: A): Int = x compareTo y
  }

I wasn't able to find a way out of the design errors in that implicit in a backwards compatible way. It is worth a fresh investigation.

The sensitivity to order of compilation units is likely due to an implementation detail of implicit search: implicit candidates are explored based on the frequency that they have been chosen previously. This is a supposed performance optimization, but the cost of non-determinism seems too high to me.

retronym added a commit to retronym/scala that referenced this issue Sep 15, 2017
This performance optimization leads to compilation order dependent variations
in whether an implicit search will diverge or will find a successful result.

Let's try turning off this sorting and measuring the impact on compilation
speed.

Refererences: scala/bug#10222, scala/bug#8541, scala/bug#10080
@ryan-williams
Copy link

thanks for the context @retronym

I just hit this again (I think) with a very basic use of shapeless.Generic:

A.scala:

object A { shapeless.Generic[T] }

B.scala:

sealed trait T
case object O extends T

sbt clean compile errors:

could not find implicit value for parameter gen: shapeless.Generic[cubic.T]
[error]   shapeless.Generic[T]
[error]                    ^

After mv A.scala C.scala, sbt compile succeeds, as does sbt clean compile

After undoing the move (mv C.scala A.scala), sbt compile still succeeds, but sbt clean compile fails and further sbt compiles after the clean will also fail.

So it clean-compiles iff the implicit-summon happens in a lexicographically-greater filename.

It additionally incremental-compiles if it was previously compiled as above, before the files' lex-order was reversed.

copied from shapeless gitter

@milessabin
Copy link

@ryan-williams I think the problem you're seeing there is #7046 rather than the issue being reported here.

@ryan-williams
Copy link

Interesting, yea I see now that my shapeless-based example above compiles fine from 2.11.9, while the original repro (more direct link than in the OP) still fails in 2.11.11 and 2.12.3. Thanks for catching/noting!

retronym added a commit to retronym/scala that referenced this issue May 4, 2018
This performance optimization leads to compilation order dependent variations
in whether an implicit search will diverge or will find a successful result.

Let's try turning off this sorting and measuring the impact on compilation
speed.

Refererences: scala/bug#10222, scala/bug#8541, scala/bug#10080
retronym added a commit to retronym/scala that referenced this issue May 13, 2018
This performance optimization leads to compilation order dependent variations
in whether an implicit search will diverge or will find a successful result.

Let's try turning off this sorting and measuring the impact on compilation
speed.

Refererences: scala/bug#10222, scala/bug#8541, scala/bug#10080
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants