Failure to find implicit parameterized with F-bound

[scabug]

The type-checker fails to find an implicit definition that has an F-bounded type parameter.
Here's a minimized example:

object Test {
  trait A[-T]
  trait B[-T]
  class C extends B[C]
  implicit def AfromB[T <: B[T]]: A[T] = null

  implicitly[A[C]]  // fails
  implicitly[A[C]](AfromB[C]) // ok if argument is given explicitly
}

Dotty compiles this OK. The example came up in an attempt to provide multiversal equality for Scala.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-9764?orig=1
Reporter: @odersky
See #5070

[scabug]

@retronym said (edited on Apr 21, 2016 11:18:26 PM UTC):
Might be the same underlying issue as #5070

[scabug]

@retronym said:
Nope, it is seems unrelated. My patch for #5070 doesn't help. (That said, you might want to look at the comments of that ticket again, Martin, as I showed an example where dotty's implicit search fails with dependent method types.)

The error in this ticket is:

⚡ qscalac -Xlog-implicits test/files/pos/t9764.scala
test/files/pos/t9764.scala:7: AfromB is not a valid implicit value for Test.A[Test.C] because:
typing TypeApply reported errors for the implicit tree: type arguments [Any] do not conform to method AfromB's type parameter bounds [T <: Test.B[T]]
  implicitly[A[C]]  // fails
            ^
test/files/pos/t9764.scala:7: Test.AfromB is not a valid implicit value for Test.A[Test.C] because:
typing TypeApply reported errors for the implicit tree: type arguments [Any] do not conform to method AfromB's type parameter bounds [T <: Test.B[T]]
  implicitly[A[C]]  // fails
            ^
test/files/pos/t9764.scala:7: error: could not find implicit value for parameter e: Test.A[Test.C]
  implicitly[A[C]]  // fails
            ^

Which miminizes the problem to:

object Test {
  trait A[-T]
  trait B[-T]
  class C extends B[C]
  def AfromB[T <: B[T]]: A[T] = null
  AfromB : A[C]
}

[scabug]

@retronym said:
Okay, the bounds of T don't contribute constraints because they are cyclic:

https://github.com/scala/scala/blob/d24e298cbd955101a6b4342602b32ed37643dfb0/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala#L212

I guess this is to avoid having type vars on LHS and RHS of a subtyping check.

Dotty typechecks this as:

Test.AfromB[Test.C']: Test.A[Test.C]

How does it come to this solution? Is C really the maximal type in the range C <: T <: B[T]. Why not B[C]? This would make a great blog post, hint, hint!

[scabug]

@retronym said:
Oh wait, I see that because T is contravariant in the result type A[T], we actually are looking for a lower bound, so C makes sense. Maybe we should only check whether tparam.bounds.lo refers is cyclic in this case when excluding cyclic type params.

[scabug]

@retronym said:
I've got my ups and downs upside down, that last comment wasn't quite right.

I see now that the key difference in inference is that scalac solves for T in adapt(Test.this.AfromB[T], pt = Test.A[Test.C]), whereas dotc does this a little later at adapt((Test.AfromB[T]: Test.A[Test.C], pt = Test.A[Test.C])

By that time, T has the constraints:

Constraint(
 uninstVars = T;
 constrained types = [T <: Test.B[LazyRef(T)]]Test.A[T]
 bounds = 
     T >: Test.C <: Test.B[LazyRef(T)] & Test.C
 ordering = 
)

Given that the T does not appear in the type of this expression, dotc instantiates it to its lower bound, C.

This differs from scalac, which would have picked the upper bound (had it not been cyclic), given that T was in a contravariant position.

[scabug]

@retronym said:
Removing the f-bound lets us see this difference in action:

object Test {
  trait A[-T]
  trait B[-T]
  class C extends B[C]
  def AfromB[T <: B[_]]: A[T] = null
  AfromB : A[C]
}

scalac:

(Test.this.AfromB[Test.B[_]]: Test.A[Test.C])

dotc:

Test.AfromB[Test.C']: Test.A[Test.C]

[newca12]

Someone should add the "fixed in dotty" label for this issue