Second parameter in implicit parameter list has uninstantiated type variables preventing implicit search from succeeding

[japgolly]

Compiler version

3.0.0-RC1

Minimized code

import scala.collection.Factory

final case class Gen[+A]() {
  def take[C[X] <: Iterable[X], B](n: Int)(implicit w: A <:< C[B], f: Factory[B, C[B]]): Gen[C[B]] =
    Gen()
}

object Usage {
  def expected: Gen[List[Int]] =
    Gen[List[Int]]().take(3)
}

Output

[error] 10 |    Gen[List[Int]]().take(3)
[error]    |                            ^
[error]    |no implicit argument of type collection.Factory[Int, C[Int]] was found for parameter f of method take in class Gen.
[error]    |I found:
[error]    |
[error]    |    collection.Factory.arrayFactory[A]
[error]    |
[error]    |But method arrayFactory in object Factory does not match type collection.Factory[Int, C[Int]].
[error]    |
[error]    |The following import might fix the problem:
[error]    |
[error]    |  import collection.immutable.List.iterableFactory

Expectation

It should compile successfully (it does in Scala 2.13).

[Kordyjan]

Adding mentioned import (collection.immutable.List.iterableFactory) fixes the problem, so the compiler message is completely fine.
It looks like a known incompatibility between scala 2 and 3. However, I cannot find the intended change that is causing that incompatibility. @smarter: can you confirm this is an intended change and not a bug?

[smarter]

It works with two using parameter lists:

import scala.collection.Factory

final case class Gen[+A]() {
  def take[C[X] <: Iterable[X], B](n: Int)(using w: A <:< C[B])(using f: Factory[B, C[B]]): Gen[C[B]] =
    Gen()
  }

object Usage {
  def expected: Gen[List[Int]] =
    Gen[List[Int]]().take(3)
}

So it's possible we can tweak the rules around inference of type variables in implicit parameters to make the first example pass too.

[smarter]

As an aside, the more idiomatic way to write this in Scala 3 would be to use an extension method to avoid the need for <:< evidence by directly defining the method on the type you want:

import scala.collection.Factory

final case class Gen[+A]()

object Gen {
  extension [C[X] <: Iterable[X], B] (g: Gen[C[B]])
    def take(n: Int)(using Factory[B, C[B]]): Gen[C[B]] =
      Gen()
}

object Usage {
  def expected: Gen[List[Int]] =
    Gen[List[Int]]().take(3)
}

[japgolly]

the more idiomatic way to write this in Scala 3 would be to use an extension method

Yeah thanks @smarter , that would be cool but at the moment I'm just trying to cross-compile a Scala 2.x library.

[anatoliykmetyuk]

Minimised to:

type G[A]
given G[H[Int]] = ???

trait H[X]
object H {
  given H[Int] = ???
}


def take[C[_]](using w: G[C[Int]], f: C[Int]) = ???

def test = take

These two examples compile

One:

type G[A]
given G[H[Int]] = ???

trait H[X]
given H[Int] = ???


def take[C[_]](using w: G[C[Int]], f: C[Int]) = ???

def test = take

Two:

type G[A]
given G[H[Int]] = ???

trait H[X]
object H {
  given H[Int] = ???
}


def take[C[_]](using w: G[C[Int]])(using f: C[Int]) = ???

def test = take

Reason:

https://github.com/lampepfl/dotty/blob/88389fc449ada138575c554729d5f3c050b6780b/compiler/src/dotty/tools/dotc/typer/Implicits.scala#L1301-L1304

implicitScope(wildProto).eligible in searchImplicit of Implicits.scala computes the implicit candidates for a given wildProto by looking at the companion objects. In the failing example, when inferring f: C[Int], wildProto is <?> for which the compiler fails to resolve the companion object, hence failing to find the implicit.

In the first working example, the wildProto is still <?> however we never need to look into any companions since the required implicit resides as a top-level definition.

In the second working example, the wildProto is H[Int].

It seems that if we use two parameter lists, wildcards of the second group get populated based on the inference done in the first group. In the case of one parameter list, wildcards do not get populated.

[odersky]

@anatoliykmetyuk That's a great analysis! It also means we might not be able to do anything about this. Can you check whether the wildProto is really <?> or whether there is something that is hidden in an IgnoredProto?

[anatoliykmetyuk]

wildProto seems to be WildcardType when output with println(wildProto).