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

compile error "diverging implicit expansion for type scala.math.Ordering ..." #8541

Open
scabug opened this issue Apr 26, 2014 · 9 comments
Open

Comments

@scabug
Copy link

scabug commented Apr 26, 2014

object Test2 {
   class TimeStamp(val toLong: Long) extends AnyVal with Ordered[TimeStamp] {
     def compare(that: TimeStamp) = java.lang.Long.compare(toLong, that.toLong)
   }

   // while looking irrelevant, these two code lines are needed to reproduce the bug
   case class L(time: TimeStamp)
   List.empty[L].sortBy(_.time)

   // this line triggers compiler error "diverging implicit expansion for type scala.math.Ordering[(Int, Test2.TimeStamp)] starting with method $conforms in object Predef"
   List.empty[(Int,TimeStamp)].sorted  
}                                      
@scabug
Copy link
Author

scabug commented Apr 26, 2014

Imported From: https://issues.scala-lang.org/browse/SI-8541?orig=1
Reporter: Denis Petrov (denis)
Affected Versions: 2.11.0
See #7291

@scabug
Copy link
Author

scabug commented Apr 27, 2014

@retronym said:
Also fails under 2.10 with -Xdivergence211 (#7291)

% scalac-hash v2.10.4 -Xdivergence211 test/files/pos/t8541.scala
test/files/pos/t8541.scala:11: error: diverging implicit expansion for type scala.math.Ordering[(Int, Test2.TimeStamp)]
starting with method orderingToOrdered in object Ordered
   List.empty[(Int,TimeStamp)].sorted
                               ^

@scabug
Copy link
Author

scabug commented Apr 27, 2014

@retronym said (edited on Apr 27, 2014 8:33:47 AM UTC):
This is such a fragile area. The root problem is that we have implicits defined in the companion scope of both Ordering and of Ordered, and there is no means to prioritize one over the other, which is the usual means to shephard implicit search away from divergence errors.

Here's a aimilar example, teased apart from the standard library:

% scalac-hash v2.10.4 test/files/pos/t8541.scala

% scalac-hash v2.10.4 -Xdivergence211 test/files/pos/t8541.scala
test/files/pos/t8541.scala:6: error: diverging implicit expansion for type Test.Ordering[Test2.TimeStamp]
starting with method orderingToOrdered in object Implicits2
  implicitly[Ordering[TimeStamp]]
            ^
test/files/pos/t8541.scala:7: error: diverging implicit expansion for type Test.Ordering[(Int, Test2.TimeStamp)]
starting with method orderingToOrdered in object Implicits2
  implicitly[Ordering[(Int,TimeStamp)]]
            ^
two errors found

% cat test/files/pos/t8541.scala
object Test2 {
  import Test._, Implicits1._, Implicits2._

  abstract class TimeStamp(val toLong: Long) extends Ordered[TimeStamp]

  implicitly[Ordering[TimeStamp]]
  implicitly[Ordering[(Int,TimeStamp)]]
}

object Test {
  class Ordering[T]
  abstract class Ordered[T] extends java.lang.Comparable[T]
  trait Low {
     implicit def ordered[A <% java.lang.Comparable[A]]: Ordering[A] = ???
     implicit def comparatorToOrdering[A](implicit cmp: java.util.Comparator[A]): Ordering[A] = ???
  }
  object Implicits1 extends Low {
    implicit def OrderingInt: Ordering[Int] = ???
    implicit def OrderingTuple2[A: Ordering, B: Ordering]: Ordering[(A, B)] = ???

  }
  object Implicits2 {
    implicit def orderingToOrdered[T](x: T)(implicit ord: Ordering[T]): Ordered[T] = ???
  }
}

The troublesome implicit is:

implicit def ordered[A <% java.lang.Comparable[A]]: Ordering[A] = ???

This should have instead been declared as:

implicit def ordered[A <: java.lang.Comparable[A]]: Ordering[A] = ???

But it is pretty hard to fix this sort of design error with our backwards compat. constraints.

My example above actually works again in 2.11.0, after a last minute tweak we made to divergence checking to try to make it more lenient and more compatible with 2.11.0. But your example is not rescued. I haven't dug in to the exact reason for that.

My recommendation to work around this issue is to explicitly publish an Orderinging[Timestamp] instance, rather than relying on the implicit from Comparable[T] => Ordering[T]

object Test2 {
   class TimeStamp(val toLong: Long) extends AnyVal
   object TimeStamp {
     implicit def TimeStampOrdering: Ordering[TimeStamp] = Ordering.by(_.toLong)
   }
 
   // while looking irrelevant, these two code lines are needed to reproduce the bug
   case class L(time: TimeStamp)
   List.empty[L].sortBy(_.time)
 
   // this line triggers compiler error "diverging implicit expansion for type scala.math.Ordering[(Int, Test2.TimeStamp)] starting with method $conforms in object Predef"
   List.empty[(Int,TimeStamp)].sorted  
}

@scabug
Copy link
Author

scabug commented May 14, 2014

Denis Petrov (denis) said:
It is easy to work around just by rearrange lines of code.

What is weird is the error appears in so simple code, without any esoteric features of scala, in the code that any beginner could write.

@scabug
Copy link
Author

scabug commented Jun 11, 2014

@retronym said:
Another reproduction for the same underlying problem was provided in #8541.

@scabug
Copy link
Author

scabug commented Oct 22, 2014

@adriaanm said:
We should look into cleaning this up through deprecation in 2.12, if there's no better solution.

@scabug
Copy link
Author

scabug commented Aug 9, 2016

James Koch (james.koch) said:
FWIW, the really spooky thing to me is what Denis flagged w/ his comment these two code lines are needed to reproduce the bug. The two different calls which accept an implicit argument would seem to a layperson to be entirely independent, and yet you need both to reproduce the issue.

I hit this in a more complex file, with about ten calls to methods like these, and worked around it by adding import Ordering.Tuple2 at the top of the file.

@amanjpro
Copy link

amanjpro commented Jun 14, 2017

I also hit this bug in a different setting:

import org.apache.spark.rdd.RDD


class Bar(v: Int) extends Ordered[Bar] {
  def compare(that: Bar): Int = ???
}

object App {

  def main(args: Array[String]): Unit = {

    val dataSet: RDD[Baz] = ???

    // This works - Case 1
    val pairs = RDD.rddToPairRDDFunctions(dataSet)

    pairs.reduceByKey(merge _)

    // This does not work!! - Case 2
    RDD.rddToPairRDDFunctions(dataSet).reduceByKey(merge _)

    // This does not work!! - Case 3
    dataSet.reduceByKey(merge _)
  }

  type Baz = ((Bar, Option[Bar]), Int)

  def merge(b1: Int, b2: Int): Int = ???
}

The first two cases should be identical, not sure why Scala fails to accept the second.

I can make the compiler happy if I provide an implicit ordering instance for Bar.

The above code works fine with 2.10 but doesn't with 2.11

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

savulchik commented Oct 4, 2017

Maybe one more reproducer of the problem using scala 2.12.3:

Welcome to Scala 2.12.3 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_144).
Type in expressions for evaluation. Or try :help.

scala> :paste
// Entering paste mode (ctrl-D to finish)

import java.time.OffsetDateTime
import scala.concurrent.duration.FiniteDuration

implicitly[Ordering[OffsetDateTime]]
implicitly[Ordering[FiniteDuration]]

// Exiting paste mode, now interpreting.

<console>:17: error: diverging implicit expansion for type Ordering[scala.concurrent.duration.FiniteDuration]
starting with method $conforms in object Predef
       implicitly[Ordering[FiniteDuration]]
                 ^

To my surprise if I rearrange the implicitly calls the problem disappears:

scala> :paste
// Entering paste mode (ctrl-D to finish)

import java.time.OffsetDateTime
import scala.concurrent.duration.FiniteDuration

implicitly[Ordering[FiniteDuration]]
implicitly[Ordering[OffsetDateTime]]

// Exiting paste mode, now interpreting.

import java.time.OffsetDateTime
import scala.concurrent.duration.FiniteDuration
res0: Ordering[java.time.OffsetDateTime] = scala.math.LowPriorityOrderingImplicits$$anon$6@60c73e58

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

5 participants