Mere presence of implicit conversion makes the program compile despite never being applied

Question

Consider method f which is parameterised by a type constructor F[_] and a proper type A

def f[F[_], A](v: F[A]) = v

Lets try to apply it to new Bar

scala> class Bar
class Bar

scala> def f[F[_], A](v: F[A]) = v
def f[F[_], A](v: F[A]): F[A]

scala> f(new Bar)
       ^
       error: no type parameters for method f: (v: F[A]): F[A] exist so that it can be applied to arguments (Bar)
        --- because ---
       argument expression's type is not compatible with formal parameter type;
        found   : Bar
        required: ?F[?A]
         ^
       error: type mismatch;
        found   : Bar
        required: F[A]

This errors as expected as Bar is not of the right shape.

Now lets add an implicit conversion from Bar to List[Int]

scala> implicit def barToList(b: Bar): List[Int] = List(42)
def barToList(b: Bar): List[Int]

scala> f(new Bar)
val res1: Any = Bar@56881196

This compiles, however notice that implicit conversion did not seem to have actually been applied because the runtime class of res1 is Bar and not List. Furthermore, the compile-time type of res1 is Any and not List[Int]. Looking at output of -Xprint:typer we see something like

val res1: Any = f[Any, Nothing](new Bar())

where we see the following inference happened

F[_] = Any
A = Nothing 

as opposed to

F[_] = List
A = Int 

and we see that no conversion actually happened, that is, we do not see something like

f(barToList(new Bar()))

Why did the mere presence of implicit conversion make the program compile whilst no implicit conversion was actually applied? Note that when being explicit about type parameters it works as expected

scala> f[List, Int](new Bar)
val res2: List[Int] = List(42)

Tele

"This errors as expected as Bar is not of the right shape." Actually Bar can be considered as having the right shape since it's Id[Bar] (where type Id[A] = A). It's just too tricky to infer higher-kinded types. With hints everything works: f(new Bar: Id[Bar]) or f(new Bar: List[Int]). – Campo

@DmytroMitin But Id isn't defined already, is it? Wouldn't it be "easier" to infer it to be a List[Int]? – Helgeson

btw in Dotty this works scastie.scala-lang.org/yQ5ibiClSumSrgX1uv2rLQ – Campo

Answer 1

I've noticed this issue before, and I think it can be tracked down to this code in the compiler:

  // Then define remaining type variables from argument types.
  foreach2(argtpes, formals) { (argtpe, formal) =>
    val tp1 = argtpe.deconst.instantiateTypeParams(tparams, tvars)
    val pt1 = formal.instantiateTypeParams(tparams, tvars)

    // Note that isCompatible side-effects: subtype checks involving typevars
    // are recorded in the typevar's bounds (see TypeConstraint)
    if (!isCompatible(tp1, pt1)) {
      throw new DeferredNoInstance(() =>
        "argument expression's type is not compatible with formal parameter type" + foundReqMsg(tp1, pt1))
    }
  }
  val targs = solvedTypes(tvars, tparams, varianceInTypes(formals), upper = false, lubDepth(formals) max lubDepth(argtpes))

As I understand it, the problem is that the isCompatible check looks for implicit conversions, but doesn't keep track of whether one was required or not, while solvedType just looks at bounds.

So if you don't have the implicit conversion, isCompatible(Bar, F[A]) is false and the methTypeArgs call throws the DeferredNoInstance exception—it won't even consider Any as a candidate for F.

If you do have the implicit conversion, isCompatible(Bar, F[A]) is true, but the compiler promptly forgets that it's only true because of the implicit conversion, and solvedTypes picks Any for F, which is allowed because of Scala's weird special-case kind-polymorphism for Any. At that point the Bar value is perfectly fine, since it's an Any, and the compiler doesn't apply the conversion it found in isCompatible (which it forgot that it needed).

(As a side note, if you provide explicit type parameters for f, methTypeArgs isn't called at all, and this discrepancy between isCompatible and solvedTypes is irrelevant.)

I think this must be a bug in the compiler. I don't know whether someone's already reported it (I just spent five minutes looking and didn't see it).

Hobble