Intersection type implicit can't be found when obscured by a type parameter

[neko-kai]

Example:

trait Tc1[A]
trait Tc2[A]
trait Tc12[A] extends Tc1[A] with Tc2[A]

trait Proxy[F[x]]
object Proxy {
  implicit val proxy: Proxy[Tc12] = new Proxy[Tc12] {}
}

final case class X()
object X {
  implicit def tc12[F[x] >: Tc12[x]: Proxy]: F[X] = new Tc12[X] {}
}

object app extends App {
  implicitly[Tc1[X]]
  implicitly[Tc2[X]]
  implicitly[Tc12[X]]
  // all good

  implicitly[Tc1[X] with Tc2[X]]
  // Error:(19, 13) could not find implicit value for parameter e: Tc1[X] with Tc2[X]
  //  implicitly[Tc1[X] with Tc2[X]]
}

Note, changing the return type of X's instance to F[X] with F[X] or applying an identity type lambda magically works around the issue, even though both transformations are tautological:

implicit def tc12[F[x] >: Tc12[x]: Proxy]: F[X] with F[X] = new Tc12[X] {}

type Fixup[A] = A
implicit def tc12[F[x] >: Tc12[x]: Proxy]: Fixup[F[X]] = new Tc12[X] {}

[szeiger]

I was going to change the title to say "compound type" but with actual intersection types in Dotty the problem still exists. In fact, it is worse in Dotty. Only Tc12[X] is found, Tc1[X] and Tc2[X] are also errors:

2 |  implicitly[Tc1[X]]
  |                    ^
  |no implicit argument of type Tc1[X] was found for parameter ev of method implicitly in object DottyPredef.
  |I found:
  |
  |    X.tc12[F](/* missing */implicitly[Proxy[Tc1]])
  |
  |But no implicit values were found that match type Proxy[Tc1].
3 |  implicitly[Tc2[X]]
  |                    ^
  |no implicit argument of type Tc2[X] was found for parameter ev of method implicitly in object DottyPredef.
  |I found:
  |
  |    X.tc12[F](/* missing */implicitly[Proxy[Tc2]])
  |
  |But no implicit values were found that match type Proxy[Tc2].
7 |  implicitly[Tc1[X] with Tc2[X]]
  |                                ^
  |no implicit argument of type Tc1[X] & Tc2[X] was found for parameter ev of method implicitly in object DottyPredef

Making Proxy covariant (trait Proxy[+F[x]]) fixes these additional problems that appear to be caused by changes in type inference. The original issue remains.

/cc @smarter

[smarter]

Please open an issue in the Dotty tracker

[neko-kai]

@smarter I opened dotty-related issues for this:
scala/scala3#6384
scala/scala3#6385

[joroKr21]

scala> X.tc12: Tc1[X] with Tc2[X]
         ^
       error: polymorphic expression cannot be instantiated to expected type;
        found   : [F[x] >: Tc12[x]]F[X]
        required: Tc1[X] with Tc2[X]

scala> typeOf[Tc1[X] with Tc2[X]].typeSymbol.typeParams
res20: List[$r.intp.global.Symbol] = List()

[joroKr21]

LoL, this is an artefact of how subtyping checks are ordered:

• type variables on the left (such as ?F[X]) are in secondTry
• refined types on the right (such as Tc1[X] with Tc2[X]) are in thirdTry
• type aliases on the left (such as Id[?F[X]]) are in fourthTry

So when we have ?F[X] <:< Tc1[X] with Tc2[X] we try to unify and naturally fail.
When we have Id[?F[X]] <:< Tc1[X] with Tc2[X] first we decompose the refined type, then we normalize the LHS and finally unify separately with Tc1 and Tc2 which works.