Regression in implicit resolution

[scabug]

object MyApp extends App {
  trait Ring[T] {
    def plus(x: T, y: T): T
    def equiv(x: T, y: T): Boolean
  }

  object Ring {
    trait Element[T <: Element[T]] { this: T =>
      def factory: Ring[T]
      def +(that: T) = factory.plus(this, that)
      def ><(that: T) = factory.equiv(this, that)
    }
  }

  object BigInteger extends Ring[java.math.BigInteger] {
    def apply(value: Int) = java.math.BigInteger.valueOf(value)
    def plus(x: java.math.BigInteger, y: java.math.BigInteger) = x.add(y)
    def equiv(x: java.math.BigInteger, y: java.math.BigInteger) = x.equals(y)
  }

  implicit def int2bigInt(value: Int) = BigInteger(value)

  trait AbstractPoly[T <: AbstractPoly.Element[T, C], C] extends Ring[T] {
    implicit def ring: Ring[C]
    def plus(x: Poly.Element[C], y: Poly.Element[C]) = apply(ring.plus(x.value, y.value))
    def equiv(x: Poly.Element[C], y: Poly.Element[C]) = ring.equiv(x.value, y.value)
    def apply(value: C): T
  }

  object AbstractPoly {
    trait Element[T <: Element[T, C], C] extends Ring.Element[T] { this: T =>
      def factory: AbstractPoly[T, C]
      def value: C
      override def toString = value.toString
    }
  }

  class Poly[C](val ring: Ring[C]) extends AbstractPoly[Poly.Element[C], C] {
    def apply(value: C) = new Poly.Element(this)(value)
  }

  object Poly {
    class Element[C](val factory: Poly[C])(val value: C) extends AbstractPoly.Element[Element[C], C]
    object Element {
      implicit def coef2poly[D <% C, C](value: D)(implicit factory: Poly[C]) = factory(value)
    }
  }

  class RF[R <: AbstractPoly.Element[R, C], C](val ring: AbstractPoly[R, C]) extends Ring[RF.Element[R, C]] {
    def plus(x: RF.Element[R, C], y: RF.Element[R, C]) = apply(ring.plus(x.value, y.value))
    def equiv(x: RF.Element[R, C], y: RF.Element[R, C]) = ring.equiv(x.value, y.value)
    def apply(value: R) = new RF.Element(this)(value)
    def apply(value: C): RF.Element[R, C] = apply(ring(value))
  }

  object RF {
    class Element[R <: AbstractPoly.Element[R, C], C](val factory: RF[R, C])(val value: R) extends Ring.Element[Element[R, C]] {
      override def toString = value.toString
    }
    object Element {
      implicit def coef2rf[D <% C, R <: AbstractPoly.Element[R, C], C](value: D)(implicit factory: RF[R, C]) = factory(value)
    }
  }

  val c = BigInteger(1)

  import Poly.Element.coef2poly
  implicit val p = new Poly(BigInteger)
  val x = p(c)

  import RF.Element.coef2rf
  implicit val q = new RF(p)
  val y = q(x)
  println(1><y)
  println(1><y) // chokes on the second occurence only (!)
}

scalac -language:implicitConversions MyApp.scala
MyApp.scala:76: error: value >< is not a member of Int
  println(1><y)
           ^

It was working in 2.11.0-M6 and previous.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-8065?orig=1
Reporter: @rjolly
Affected Versions: 2.11.0-M7
See #3346

[scabug]

@retronym said:
Behaviour changed in 210dbc7 / #3346

[scabug]

@retronym said (edited on Dec 10, 2013 4:38:39 PM UTC):
Here's a smaller, closely related case:

trait E1[T] {
  def f(that: T) = ()
}

class E2[R, C] extends E1[E2[R, C]]

object MyApp {
  implicit def int2string(value: Int): String = ???
  implicit def coef2rf[D, R, C](value: D)(implicit ev: D => C): E1[E2[R, C]] = ???

  def test: Unit = {

    val y: E2[E1[String], String] = ???
    val i: Int = 0
    i.f(y)
    i.f(y) // chokes on the second occurence only (!)
    ()
  }
}

[scabug]

@xeno-by said:
Further discussion: scala/scala#3408

[scabug]

@retronym said:
Changing the order of int2string and coef2rf the the code in the comment just above leads to the failure in the first instance.

The order that implicit candidates are tried is dynamic based on frequency of applicability. See:

// Implicits.scala
        // most frequent one first
        val sorted = matches sortBy (x => if (isView) -x.useCountView else -x.useCountArg)

[scabug]

@adriaanm said:
As Jason suggested, I think you'll have to work around this in your code by defining an ordering.
The example below works for me. I think #3346 is pretty nice to have fixed, so I'd rather not give it up for this.

I'm sorry, but we're out of time for 2.11. I'll leave it open for a couple more days, but, unless I'm missing something, I think we should anticipate closing this as won't fix.

trait E1[T] {
  def f(that: T) = ()
}
 
class E2[R, C] extends E1[E2[R, C]]

trait Lower {
  implicit def int2string(value: Int): String = ???
} 

object MyApp extends Lower{
  implicit def coef2rf[D, R, C](value: D)(implicit ev: D => C): E1[E2[R, C]] = ???
 
  def test: Unit = {
 
    val y: E2[E1[String], String] = ???
    val i: Int = 0
    i.f(y)
    i.f(y) // chokes on the second occurence only (!)
    ()
  }
}

[scabug]

@rjolly said (edited on Feb 17, 2014 8:19:46 AM UTC):
I think there is a double mistake here.

1. the fact that reordering imports can change compilation success is a different issue than the original one.
2. Jason showed that the effect of the implicit arguments of implicit conversions do not guide type inference #3346 on my code can be countered by removing sortBy in Implicits.scala, hence there is no need to revert that change.

In support of 1), removing sortBy does not fix compilation failure on the first occurrence (i.e. when int2string is moved after coef2rf). It does fix failure on the second occurence.

Regarding my code, I have found a workaround of my own, but yours may be good too, I have to check it.

Still, I think this bug (the original one, causing failure on the second identical line) is worth fixing (and simple to fix, see scala/scala#3408 about how removing sortBy has no effect on performance). Hence I have created a new pull request scala/scala#3540

[scabug]

@adriaanm said:
I thought the sortBy was crucial for performance.

[scabug]

@rjolly said:
I compiled Scalacheck with/out it, and to be honest, it might bring a ~1% improvement. The question is whether it is worth the indeterminism it introduces. I mean, having the exact same line compile or not depending on where it is placed, is unworthy of an end product.

[scabug]

@adriaanm said (edited on Feb 18, 2014 7:52:43 PM UTC):
If there's an error due to a certain sort order, I suspect the bug is that the error isn't reported for all sort orders, not the other way around.
Could you comment on why the proposed workaround isn't viable for you? I would recommend against walking this fine line of exploiting implicit search implementation details.

[scabug]

@rjolly said:
The problem is not how reordering imports causes the failure or not. The problem is that sometimes the second of two identical lines fails, due to a different compiler state.
Your proposed workaround can certainly solve my issue. I have another one that also solve my issue. My project is not the one involved here.

[SethTisue]

seems to have been resolved by 2.11.0:

% /usr/local/scala/scala-2.11.0/bin/scalac S.scala
S.scala:74: error: value >< is not a member of Int
  println(1><y)
           ^
S.scala:75: error: value >< is not a member of Int
  println(1><y) // chokes on the second occurence only (!)
           ^
two errors found

and remains resolved in 2.13.16

[rjolly]

Indeed, I think we can close the ticket then. Thanks for checking!