Extension method call fails with ambiguous implicit search even though method receiver type should be enough to disambiguate

[mpilquist]

Compiler version

3.0.0-RC2

Minimized code

object Structures:

  trait Functor[F[_]]:
    extension [A](fa: F[A])
      def map[B](f: A => B): F[B]
      def as[B](b: B): F[B] = map(_ => b)
      def void: F[Unit] = as(())

  trait Applicative[F[_]] extends Functor[F]:
    def pure[A](a: A): F[A]
    def unit: F[Unit] = pure(())
    extension[A](fa: F[A])
      def map2[B, C](fb: F[B], f: (A, B) => C): F[C]
      def map[B](f: A => B): F[B] =
        fa.map2(unit, (a, _) => f(a))

  trait Monad[F[_]] extends Applicative[F]:
    extension[A](fa: F[A])
      def flatMap[B](f: A => F[B]): F[B]
      override def map[B](f: A => B): F[B] =
        flatMap(a => pure(f(a)))
      def map2[B, C](fb: F[B], f: (A, B) => C): F[C] =
        flatMap(a => fb.map(b => f(a, b)))

  given Monad[List] with
    def pure[A](a: A) = List(a)
    extension[A](fa: List[A])
      def flatMap[B](f: A => List[B]) = fa.flatMap(f)

  given Monad[Option] with
    def pure[A](a: A) = Some(a)
    extension[A](fa: Option[A])
      def flatMap[B](f: A => Option[B]) = fa.flatMap(f)


  opaque type Kleisli[F[_], A, B] = A => F[B]

  extension [F[_], A, B](k: Kleisli[F, A, B])
    def apply(a: A): F[B] = k(a)

  object Kleisli:
    def apply[F[_], A, B](f: A => F[B]): Kleisli[F, A, B] = f

  given [F[_], A](using F: Monad[F]): Monad[[B] =>> Kleisli[F, A, B]] with
    def pure[B](b: B) = Kleisli(_ => F.pure(b))
    extension[B](k: Kleisli[F, A, B])
      def flatMap[C](f: B => Kleisli[F, A, C]) =
        a => k(a).flatMap(b => f(b)(a))

end Structures

@main def run =
  import Structures.{*, given}
  println(List(1, 2, 3).map2(List(4, 5, 6), (_, _)))

  val p: Kleisli[Option, Int, Int] = Kleisli((x: Int) => if x % 2 == 0 then Some(x) else None)
  val q: Kleisli[Option, Int, Int] = summon[Applicative[[B] =>> Kleisli[Option, Int, B]]].pure(20)
  println(p.map2(q, _ + _)(42))

Output

value map2 is not a member of Structures.Kleisli[Option, Int, Int].
An extension method was tried, but could not be fully constructed:

    Structures.given_Monad_Kleisli[F, A](
      /* ambiguous: both object given_Monad_List in object Structures and object given_Monad_Option in object Structures match type Structures.Monad[F] */
        summon[Structures.Monad[F]]
    ).map2()

Expectation

Because p had type Kleisli[Option, Int, Int], scalac should infer F = Option in given_Monad_Kleisli and unambiguously select given_Monad_Option.

This may be a duplicate (e.g. #7999 or similar) but not clear to me. Also not clear if title is correct or misleading.

[mpilquist]

This type checks:

object Structures:

  trait Monad[F[_]]:
    def pure[A](a: A): F[A]
    extension[A](fa: F[A])
      def flatMap[B](f: A => F[B]): F[B]

  given Monad[List] with
    def pure[A](a: A) = List(a)
    extension[A](fa: List[A])
      def flatMap[B](f: A => List[B]) = fa.flatMap(f)

  given Monad[Option] with
    def pure[A](a: A) = Some(a)
    extension[A](fa: Option[A])
      def flatMap[B](f: A => Option[B]) = fa.flatMap(f)

  opaque type Kleisli[F[_], A, B] = A => F[B]

  extension [F[_], A, B](k: Kleisli[F, A, B])
    def apply(a: A): F[B] = k(a)

  object Kleisli:
    def apply[F[_], A, B](f: A => F[B]): Kleisli[F, A, B] = f

  given [F[_], A](using F: Monad[F]): Monad[[B] =>> Kleisli[F, A, B]] with
    def pure[B](b: B) = Kleisli(_ => F.pure(b))
    extension[B](k: Kleisli[F, A, B])
      def flatMap[C](f: B => Kleisli[F, A, C]) =
        a => k(a).flatMap(b => f(b)(a))

end Structures

@main def run =
  import Structures.{*, given}

  val p: Kleisli[Option, Int, Int] = Kleisli((x: Int) => if x % 2 == 0 then Some(x) else None)
  p.flatMap(_ => p)

This doesn't - just addition of map2:

object Structures:

  trait Monad[F[_]]:
    def pure[A](a: A): F[A]
    extension[A](fa: F[A])
      def flatMap[B](f: A => F[B]): F[B]
      def map2[B, C](fb: F[B], f: (A, B) => C): F[C] =
        flatMap(a => fb.flatMap(b => pure(f(a, b))))

  given Monad[List] with
    def pure[A](a: A) = List(a)
    extension[A](fa: List[A])
      def flatMap[B](f: A => List[B]) = fa.flatMap(f)

  given Monad[Option] with
    def pure[A](a: A) = Some(a)
    extension[A](fa: Option[A])
      def flatMap[B](f: A => Option[B]) = fa.flatMap(f)

  opaque type Kleisli[F[_], A, B] = A => F[B]

  extension [F[_], A, B](k: Kleisli[F, A, B])
    def apply(a: A): F[B] = k(a)

  object Kleisli:
    def apply[F[_], A, B](f: A => F[B]): Kleisli[F, A, B] = f

  given [F[_], A](using F: Monad[F]): Monad[[B] =>> Kleisli[F, A, B]] with
    def pure[B](b: B) = Kleisli(_ => F.pure(b))
    extension[B](k: Kleisli[F, A, B])
      def flatMap[C](f: B => Kleisli[F, A, C]) =
        a => k(a).flatMap(b => f(b)(a))

end Structures

@main def run =
  import Structures.{*, given}
  println(List(1, 2, 3).map2(List(4, 5, 6), (_, _)))

  val p: Kleisli[Option, Int, Int] = Kleisli((x: Int) => if x % 2 == 0 then Some(x) else None)
  println(p.map2(p, _ + _)(42))

[mpilquist]

Smaller reproduction:

trait Foo[F[_]]:
  extension [A](fa: F[A])
    def foo[B](fb: F[B]): F[Unit]
    def b1[B](fb: F[B]): F[B] = ???
    def b2[B](fb: F[B], f: B => B): F[B] = ???
    def b3[B, C](fb: F[B], f: B => C): F[B] = ???

given Foo[List] with
  extension [A](fa: List[A])
    def foo[B](fb: List[B]) = ???

given Foo[Option] with
  extension [A](fa: Option[A])
    def foo[B](fb: Option[B]) = ???

trait Bar[F[_], X, A]
given [F[_], X](using Foo[F]): Foo[[A] =>> Bar[F, X, A]] with
  extension [A](fa: Bar[F, X, A])
    def foo[B](fb: Bar[F, X, B]) = ???

def works[X, A](b: Bar[Option, X, A])(using Foo[Option]): Unit =
  b.b1(b)
  b.b2(b, _ => ???)
  b.b3(b, _ => ???)

val x: Bar[Option, Int, Int] = ???
val y1 = x.b1(x)
val y2 = x.b2(x, _ => ???)
val y3 = x.b3(x, _ => ???)

Everything type checks except for val y3 = x.b3(x, _ => ???), which fails with:

value b3 is not a member of Bar[Option, Int, Int].
An extension method was tried, but could not be fully constructed:

    main$package.given_Foo_Bar[F, X](
      /* ambiguous: both object given_Foo_List and object given_Foo_Option match type Foo[F] */
        summon[Foo[F]]
    ).b3()

[smarter]

It's weird yeah, seemingly small changes in the extension method definition somehow determine whether the implicit search succeeds or not:

trait Foo[F[_]]:
  extension[A](fa: F[A])
    def ok: Unit = {}
    def fail[B]: Unit = {}

given Foo[List] with {}
given Foo[Option] with {}

class Kleisli[F[_], A, B]
given [F[_], A](using F: Foo[F]): Foo[[B] =>> Kleisli[F, A, B]] with {}

@main def run =
  val p: Kleisli[Option, Int, Int] = ???
  val a = p.ok  // ok
  val b = p.fail[Int] // error: ambiguous

[smarter]

aha, I found the culprit: https://github.com/lampepfl/dotty/blob/8086e4b946de0c13f8bec62864f761ea87c82982/compiler/src/dotty/tools/dotc/typer/ProtoTypes.scala#L67-L79
If I remove the last condition in the if, the original example succeeds, but i6682a.scala fails with -Ycheck:all indeed. Since I'm planning to work on type avoidance in constraint solving in the future I'll self-assign this.