Spurious implicit argument ambiguity

[travisbrown]

minimized code

trait TC[F[_]]

object TC {
  implicit def instance1: TC[[x] =>> Int => x] = new TC[[x] =>> Int => x] {}
  implicit def instance2: TC[List] = new TC[List] {}
}

case class Foo[F[_], A](value: F[A]) {
  def bar(other: Foo[F, A])(implicit F: TC[F]): Foo[F, A] = other
}

val xs = List(1, 2, 3)
def foo1 = Foo(xs).bar(Foo(xs))
def foo2 = Foo(xs).bar(foo1)
def foo3 = Foo(xs).bar(Foo(xs)).bar(Foo(xs))
def foo4 = Foo(xs).bar(Foo(xs).bar(Foo[List, Int](xs)))
def foo5 = Foo(xs).bar(Foo(xs).bar(Foo(xs)))

Compilation output

-- Error: Foo.scala:17:43 ------------------------------------------------------
17 |def foo5 = Foo(xs).bar(Foo(xs).bar(Foo(xs)))
   |                                           ^
   |ambiguous implicit arguments: both method instance1 in object TC and method instance2 in object TC match type TC[F] of parameter F of method bar in class Foo
1 error found

expectation

This is another attempt to minimize something I'm running into in the Cats tests. As in #7993 the Scala 2 equivalent compiles as expected.

It might be worth noting that if instance1 is TC[Option] or even TC[[x] =>> x => Int], Dotty has no problem with this. I tried minimizing with my own trait Func[-A, +B] but couldn't get it to error.

[julienrf]

Isn’t it because List[A] <: Int => A?

[travisbrown]

@julienrf I guess that explains why I can't reproduce it with a custom Func, but I still don't understand why foo1 through foo4 compile or why it's different from Scala 2.

[travisbrown]

Might also be worth noting that in the original context the error message actually says that the supposed ambiguous instances both match Functor[List]:

[error] -- Error: /home/travis/code/projects/cats/tests/src/test/scala/cats/tests/KleisliSuite.scala:310:24 
[error] 310 |    } yield (k1, k2, k3)
[error]     |                        ^
[error]     |ambiguous implicit arguments: both method catsStdMonadForFunction1 in trait Function1Instances and value catsStdInstancesForList in trait ListInstances match type cats.Functor[List] of parameter F of method map in class Kleisli

[julienrf]

Right, instance2 should have a higher priority since it’s more specific than instance1.

[travisbrown]

If the TC[List] is explicitly prioritized by putting the other in a LowPriority trait it does compile, but prioritizing all of our list instances with respect to our function instances isn't really an option.

[smarter]

Right, instance2 should have a higher priority since it’s more specific than instance1.

It's not more specific since TC is invariant in its type parameter. But I'd expect List to be picked anyway because before doing the implicit search we should have instantiated the type variable F >: [X] => List[X] to F := [X] => List[X]

[smarter]

Here's a minimization:

class Inv[A]
class X
class Y extends X

object Test {
  implicit def impX: Inv[X] = ???
  implicit def impY: Inv[Y] = ???

  def foo[T](x: T)(implicit inv: Inv[T]): Inv[T] = ???
  def wrap[S](y: Inv[S]): Any = ???

  val y: Y = ???

  foo(y) // OK
  wrap(foo(y)) // ambiguous
}

Before doing an implicit search, we need to instantiate some of the type variables involved (because otherwise we're likely to run into ambiguity) but we can't instantiate all of them (some of the type variables might be resolved by the implicit search itself, cf https://milessabin.com/blog/2011/07/16/fundeps-in-scala/). The heuristic we use currently instantiate all type variables which appear in a prefix of the current expression (https://github.com/lampepfl/dotty/blob/9322e8c3dad176c948583c5da262f77b11ec75c6/compiler/src/dotty/tools/dotc/typer/Inferencing.scala#L200-L208), but this doesn't work with wrap(foo(y)) because constraint solving ends up with:

wrap[?S](foo[?T](y))
where
?T := ?S
?S >: Y

at this point we search for uninstantiated type variables in the expression foo[?T](y) but there is none since ?T has been instantiated to ?S already ! For the implicit search to be unambiguous we would need to go deeper and look for uninstantiated type variables in the instantiation of ?T itself, thus realizing that we need to instantiate ?S to Y.

(On a side note, I think the current logic where we traverse an expression to find type variables to instantiate is perhaps too complicated, see #4742 (comment) for an alternative approach I have yet to properly explore)

[travisbrown]

For what it's worth I'm seeing something similar in another place in the Cats tests, where this code:

List(1, 2, 3).traverse(i => Const.of[List[Int]](List(i)))

Has the inferred type Const[Int => Int, List[List[Int]]] instead of Const[List[Int], List[List[Int]]].