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

[lrytz]

I was possibly looking at the same issue at some point in 2021, there's a ticket on some private repo.

My minimization:

object c {
  trait MO[CC[_]]
  trait M[V] extends MO[M]
  trait BF[-F]

  // type arguments [Any,Int] do not conform to method bf's
  // type parameter bounds [CC[X] <: c.M[X] with c.MO[CC],V]
  implicit def bf[CC[X] <: M[X] with MO[CC], V]: BF[CC[V]] = null

  // works
  // implicit def bf[CC[Y] <: M[Y]            , V]: BF[CC[V]] = null

  def t: BF[M[Int]] = bf
  // def t = implicitly[BF[M[Int]]]
}

My notes

• 2.12 (and 2.11 fwiw) crashes with an SEO on the example above
• 2.13 infers bf to bf[Any, Int], which then doesn't type check
• it works in Scala 3

Scala 2 fails because of CC is F-bounded. When solving the type variable for CC, containsSymbol(bound, tparam) is true

• tparam = CC
• bound = [X]c.M[X] with c.MO[CC]

therefore the bound is not added to the type variable's constraints, and inference sets CC to Any.

Scala 3 has a new implementation. Enabling some logging by setting val typr = default shows the following trace:

interpolate def t: c.BF[c.M[Int]] = c.bf[CC, Int]: c.BF[c.M[Int]] in TS[1, 0], owned vars = CC, Int, qualifying = CC, Int, previous =  /  uninstantiated variables: CC
 constrained types: [CC[X] <: c.M[X] & c.MO[CC], V] => c.BF[CC[V]]
 bounds:
     CC[X] >: c.M[V] <: c.M[X] & c.MO[CC]
     V := Int
 ordering:
interpolate non-occurring CC in TS[1, 0] in def t: c.BF[c.M[Int]] = c.bf[CC, Int]: c.BF[c.M[Int]], fromBelow = true,  uninstantiated variables: CC
 constrained types: [CC[X] <: c.M[X] & c.MO[CC], V] => c.BF[CC[V]]
 bounds:
     CC[X] >: c.M[V] <: c.M[X] & c.MO[CC]
     V := Int
 ordering:
approx CC, from below = true, inst = c.M
instantiating CC with c.M

---

What got me there was implicitly[scala.collection.BuildFrom[Map[Int, Int], String, Iterable[String]]] failing. The notes from that investigation:

The implicit BuildFrom available are (simplified)

buildFromMapOps[CC[X, Y] <: Map[X, Y], K0, V0, K, V]: BuildFrom[CC[K0, V0], (K, V), CC[K, V]] -> CC is binary

buildFromIterableOps[CC[X] <: Iterable[X], A0, A]: BuildFrom[CC[A0], A, CC[A]] -> CC is unary

they both don't fit what's asked for

I tried adding

  implicit def buildFromMapOpsIterable[CC[X, Y] <: Map[X, Y] with MapOps[X, Y, CC, _], K0, V0, A]: BuildFrom[CC[K0, V0], A, Iterable[A]] = new BuildFrom[CC[K0, V0], A, Iterable[A]] {
    def newBuilder(from: CC[K0, V0]): Builder[A, Iterable[A]] = (from: MapOps[K0, V0, CC, _]).iterableFactory.newBuilder[A]
    def fromSpecific(from: CC[K0, V0])(it: IterableOnce[A]): Iterable[A] = (from: MapOps[K0, V0, CC, _]).iterableFactory.from(it)
  }

since MapOps extends IterableOps[(K, V), Iterable, C], whre the CC of IterableOps is fixed to Iterable, this would seem fine. But inference fails, because we get to

adapt(tree = BuildFrom.buildFromMapOpsIterable, pt: BuildFrom[Map[Int, Int], String, Iterable[String]])

Because the From parameter of BuildFrom is contravariant, adapt instantiates the tree to BuildFrom.buildFromMapOpsIterable[Any, Int, Int, String], which then fails the bounds checks.