False implicit not found error when searching for an implicit value defined in another module that directly references a higher-kinded type defined in a 3rd module that is a subtype of the sought type

[neko-kai]

Compiler version

3.1.3 and 3.2.1-RC1

Minimized code

This bug seems to definitely require both an external library (cats) and a multi-module project. Attempts to minimize without these two failed for me. It could plausibly be an issue with the org.typelevel cats-core_3 2.6.0 artifact, since I cannot reproduce it with locally defined similar types.

To reproduce execute:

git clone https://github.com/7mind/no-more-orphans.git --branch bug/hkt-cats-type-failure
cd no-more-orphans/
sbt test

With the following setup:

package mylib

import scala.math.Ordering

final case class MyIntSet(i: Set[Int])

object MyIntSet {

  implicit def optionalCatsBoundedSemilatticeForMyIntSet[F[_]: CatsBoundedSemilattice]: F[MyIntSet] = {
    new cats.kernel.BoundedSemilattice[MyIntSet] {
      override def empty: MyIntSet = MyIntSet(Set.empty)
      override def combine(x: MyIntSet, y: MyIntSet): MyIntSet = MyIntSet(x.i ++ y.i)
    }.asInstanceOf[F[MyIntSet]]
  }

  implicit val orderingMyIntSet: Ordering[MyIntSet] = null.asInstanceOf[Ordering[MyIntSet]]

}

private sealed trait CatsBoundedSemilattice[F[_]]
private object CatsBoundedSemilattice {
  // FIXME this misbehaves on Scala 3: generates false implicit-not-found errors when implicit search is in another module
  implicit val get: CatsBoundedSemilattice[cats.kernel.BoundedSemilattice] = null

  // these workarounds all work to pacify Scala 3
//  implicit val get: CatsBoundedSemilattice[[a] =>> cats.kernel.BoundedSemilattice[a]] = null
//  implicit def get[T[x] >: cats.kernel.BoundedSemilattice[x]]: CatsBoundedSemilattice[T] = null
}

Following implicit searches fail - only when done in another module - the same search succeeds inside the module that defines MyIntSet:

    implicitly[BoundedSemilattice[MyIntSet]] // ok, searching for the same type
    implicitly[CommutativeMonoid[MyIntSet]] // fails, when searching for a supertype
    implicitly[Monoid[MyIntSet]] // fails, when searching for a supertype

[error] -- Error: /private/tmp/no-more-orphans/test-cats/src/test/scala/CatsMyIntSetTest.scala:12:32
[error] 12 |    implicitly[Monoid[MyIntSet]]
[error]    |                                ^
[error]    |No given instance of type cats.kernel.Monoid[mylib.MyIntSet] was found for parameter e of method implicitly in object Predef.
[error]    |I found:
[error]    |
[error]    |    mylib.MyIntSet.optionalCatsBoundedSemilatticeForMyIntSet[F](
[error]    |      /* missing */summon[mylib.CatsBoundedSemilattice[F]]
[error]    |    )
[error]    |
[error]    |But no implicit values were found that match type mylib.CatsBoundedSemilattice[F].

Workaround

Replacing CatsBoundedSemilattice.get's type argument with a substantially identical type lambda fixes the issue.

-  implicit val get: CatsBoundedSemilattice[cats.kernel.BoundedSemilattice] = null
+  implicit val get: CatsBoundedSemilattice[[a] =>> cats.kernel.BoundedSemilattice[a]] = null

Expectation

Expected to work as in Scala 2.

NOTE: this bug only happens with an F[_] kinded type, examples in the same project with F[_[_]] kind work correctly.

[prolativ]

Vulpix-style minimization without references to cats:

Lib_1.scala

package pkg

trait Foo1[A]
trait Foo2[A] extends Foo1[A]

trait Bar[F[_]]
object Bar {
  implicit val bar: Bar[pkg.Foo2] = ???
}

trait Qux
object Qux {
  implicit def qux[F[_]](implicit bar: Bar[F]): F[Qux] = ???
}

Test_2.scala

import pkg._

object Test {
  implicitly[Foo2[Qux]]
  implicitly[Foo1[Qux]]
}

Interestingly, now this starts to compile if we remove the theoretically redundant package prefix in

implicit val bar: Bar[pkg.Foo2]

changing it into

implicit val bar: Bar[Foo2]