Contravariance mucks with implicit resolution

[scabug]

A condition under which the most-specific implicit is not being selected:

// Test.scala
class A
class B extends A

trait Y {
  def value: String
} 

trait X[-T] { // if I make X invariant, this works
  def y(t: T): Y
}

object XA extends X[A] {
  def y(a: A) = new Y { def value = a.getClass + ": AValue" }
}

object XB extends X[B] {
  def y(b: B) = new Y { def value = b.getClass + ": BValue" }
}

object Test {
  implicit def f[T](t: T)(implicit x: X[T]): Y = x.y(t)
  implicit val xa: X[A] = XA
  implicit val xb: X[B] = XB

  def main(argv: Array[String]) {
    val a = new A
    val b = new B
    println("A: " + a.value)
    println("B: " + b.value)
  }
}

gives:

$$ scala Test
A: class A: AValue
B: class B: AValue

Making X invariant in T gives a correct result, but of course is much less flexible.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-2509?orig=1
Reporter: Kris Nuttycombe (nuttycom)

[scabug]

@adriaanm said:
this is due to a known limitation of our type inference algorithm (contravariant type params are problematic wrt inference)

[scabug]

@adriaanm said:
Actually, what I said is a little imprecise:

type inference&implicit search yields:

    println("A: " + f[A](a)(xa).value)
    println("B: " + f[B](b)(xa).value)

but that's what's expected because xa is the value with the most specific type: X[A], as X[A] <: X[B] (since B <: A and X is contravariant in its first type argument)

[scabug]

Kris Nuttycombe (nuttycom) said:
What I find surprising about this is that specificity is conflated with the direction of the variance. At least to my mind, variance is associated with substitutability, whereas specificity is a unidirectional relation in the direction of covariance.

The concepts aren't totally orthogonal; it's more like there should be a distinction between subclassing (where subclasses are always more specific) and subtyping, where an instance of a subtype is always substitutable for an instance of the supertype.

[scabug]

@paulp said:
Noting for any future database searchers that as far as I'm concerned I fixed this.

Discussion: https://groups.google.com/forum/#!topic/scala-language/ZE83TvSWpT4

Implementation: https://github.com/paulp/scala/tree/topic/contrarivariance

[scabug]

@milessabin said (edited on May 29, 2016 7:56:40 AM UTC):
In the light of this Dotty commit I think we should un-Won't Fix this ticket and deal with it here too.

[scabug]

@dwijnand said:
(here's the commit SHA that eventually made it into lampepfl/dotty: scala/scala3@8954026)

[scabug]

@soc said:
Agree. Would be nice to get this into 2.12 as a flag to allow all the "base" libraries to play with it. Without it this would delay even thinking about integrating some fundamental typeclasses into the std lib for years.

[scabug]

Tongfei Chen (ctongfei) said:
I'd very much like to see this fixed in 2.12. Spire/Cats/Scalaz/... are in desperate need of this :-)

[scabug]

Guillaume Martres (Smarter) said (edited on May 30, 2016 4:03:19 PM UTC):
For reference, scala/scala3#1246 (comment) documents the sort of issues with existing implicits that might pop up if you change that rule, and how to fix them.

[lrytz]

scala/scala#6037