Covariant HKT implicits fail to resolve

[neko-kai]

Given this setup:

object example extends App {
trait MonoIO[F[_]]
trait BifunctorIO[F[+_, _]]

case class IO[+A]()
object IO {
  implicit val monoInstance: MonoIO[IO] = new MonoIO[IO]{}
}

trait AnyIO[+F[_]]
object AnyIO {
  implicit def fromMono[F[_]: MonoIO]: AnyIO[F] = new AnyIO[F]{}
  implicit def fromBIO[F[+_, _]: BifunctorIO]: AnyIO[({ type l[A] = F[Nothing, A]})#l] = new AnyIO[({ type l[A] = F[Nothing, A]})#l]{}
}

class SomeAlg[+F[_]]
type SomeAlg2[F[_, _]] = SomeAlg[({ type l[A] = F[Nothing, A]})#l]
object SomeAlg {
  def make[F[_]: AnyIO](): SomeAlg[F] = new SomeAlg[F]
}

val alg: SomeAlg[IO] = SomeAlg.make[IO]()
val alg1: SomeAlg[IO] = SomeAlg.make()
}

Constructing SomeAlg fails even when the types are fully annotated:

val alg: SomeAlg[IO] = SomeAlg.make[IO]()
// could not find implicit value for evidence parameter of type AnyIO[IO]

Explicitly providing AnyIO instance works though: SomeAlg.make[IO](AnyIO.fromMono[IO])

Removing covariance from AnyIO allows SomeAlg.make[IO]() to work, however, a non-type annotated version will still fail to resolve:

val alg1: SomeAlg[IO] = SomeAlg.make()

This is only fixed if covariance is removed from SomeAlg too.
The reason for wanting covariance on these classes is to represent errorless effects, e.g. Clock, Random, Logging:

trait Clock[+F[_]]
trait Clock2[F[_, _]] = Clock[F[Nothing, ?]]

def clockExecutionTime[F[_]: Clock, A](f: F[A]): F[(Duration, A)] = ???

def potentiallyErroringAction[F[_, _]]: F[Throwable, Unit] = ???

def clockedAction[F[+_, +_]: Clock2]: F[Throwable, Unit] = {
  clockExecutionTime(potentiallyErroringAction[F])
}

^ The covariance on the example clock algebra is extremely convenient as it allows it to transition seamlessly between bifunctor (arbitrary error type) and monofunctor (fixed error type) contexts. However, with the bug above, these algebras are extremely limited in how they can participate in implicit resolution.

[joroKr21]

I think the problem boils down to:

1. Companion objects are only in implicit scope for their corresponding type, not subtypes or supertypes.
2. Covariance causes the compiler to look for MonoIO[F] for some F[x] <: IO[x] not MonoIO[IO]

Note that F[_] is a type variable and it doesn't have a companion object.
Putting the instance in the companion object of MonoIO works:

trait MonoIO[F[_]]
trait BifunctorIO[F[+_, _]]
case class IO[+A]()
object MonoIO {
  implicit val monoInstance: MonoIO[IO] = new MonoIO[IO]{}
}

trait AnyIO[+F[_]]
object AnyIO {
  implicit def fromMono[F[_]: MonoIO]: AnyIO[F] = new AnyIO[F]{}
  implicit def fromBIO[F[+_, _]: BifunctorIO]: AnyIO[({ type K[A] = F[Nothing, A] })#K] = new AnyIO[({ type K[A] = F[Nothing, A] })#K]{}
}

[neko-kai]

@joroKr21
Point 1 shouldn't be correct since according to this article the rules are:

The implicit scope of a type T consists of all companion modules (§5.4) of classes that are associated with the implicit parameter’s type. Here, we say a class C is associated with a type T , if it is a base class (§5.1.2) of some part of T

Meaning all supertypes of all type parameters, projection/selection prefixes, intersections and of the type itself are ALL searched. And also this example works, showing that the companion of the supertype must have been searched:

object example extends App {
  class C[+A]

  trait TBase
  object TBase {
    implicit def CTBase[T <: TBase]: C[T] = new C[T]{}
  }

  class T extends TBase

  implicitly[C[T]]
  def x[X <: TBase] = implicitly[C[X]]
  implicitly[C[X forSome { type X <: TBase}]]
}

Point 2 is the bug in question indeed, the -Xlog-implicits does mention F. I don't understand why putting it into MonoIO companion works, perhaps the IO companion is not searched because higher kinded types are treated differently here? I think the search should never be narrowed to F[x] <: IO[x] which is a far wider range of types than IO[x], I think for covariance the search should be for F[x] forSome { type F[x] <: IO[x] } (which succeeds) not for F[x] <: IO[x]

[joroKr21]

@Kaishh Ah yes, you are right, I completely missed that part of implicits for some reason.
Your second example works just the same with higher-kinded types.

So I guess the problem is that while in your second example the fact that X <: TBase is determined by the upper bound, in the first one this fact is only known by a type variable constraint (AnyIO[F] <: AnyIO[IO] => F[x] <: IO[x]) and maybe the constraints are not considered base types. I don't have enough knowledge to say whether it's sound and/or feasible algorithmically to consider type variable constraints for implicit scope as well.

Edit: Your original example doesn't work even if the type is not higher-kinded.

[neko-kai]

@joroKr21
Note that my original example works in dotty: https://scastie.scala-lang.org/0cq8ypISSH2jBXNNEqtRlg
So, I think the behavior seen here is unlikely to be a deliberate optimization since Dotty went ahead with supporting this.
Sorry for bothering, but, @smarter, any ideas what could it be that dotty does correctly here that scalac doesn't?

[smarter]

Don't know, but what @joroKr21 is saying seems plausible, Dotty does go through upper bounds of type variables to decide what companions to look for to find implicits, I think Scala 2 does the same, but maybe it doesn't do it recursively or something ?

[smarter]

(Also I don't recommend using Scastie to infer Dotty's behavior because it's stuck on an old version of Dotty because of scalacenter/scastie#281)

[neko-kai]

Works on dotty-0.10.0-RC1 too.

I think Scala 2 does the same, but maybe it doesn't do it recursively or something ?

Ok, would that be hard to fix? And if, hypothetically, there was a fix, would it be accepted into 2.12(.9, .10) series or would that be considered a breaking change?

[smarter]

No idea about how hard it'd be to fix :). Probably unlikely to get into 2.12 since it could break source compatibility in non-obvious ways.

[neko-kai]

This works on 2.12 with -Xsource:2.13 flag and on 2.13.0-pre-f1dec97.
This might have been another bug closed by scala/scala#6069
I guess it can be closed?

[neko-kai]

Unfortunately, that was a false positive. The example DOES NOT work under any of 2.13.0-M5, 2.13.0-pre-dd34f62, 2.12.8 with -Xsource:2.13. I was fooled by copypasting the setup code forgetting the summon itself...
I'm reopening then.

[adriaanm]

We can't tackle this in 2.13.0 anymore, but before assigning this to 2.13.1, I'd like to first understand whether this is actually a regression.

[joroKr21]

This is the method that computes the implicit scope of a type:
https://github.com/scala/scala/blob/5da50e6f819ae114814360390d05106eb2ad0bd3/src/compiler/scala/tools/nsc/typechecker/Implicits.scala#L1274-L1336

There is no special handling of type variables. All abstract types end up here:
https://github.com/scala/scala/blob/5da50e6f819ae114814360390d05106eb2ad0bd3/src/compiler/scala/tools/nsc/typechecker/Implicits.scala#L1303-L1316

As you can see only the upper bound is considered and since Scala 2.13 also the prefix and type arguments, but definitely no type constraints are considered.

Also the doc says this method is performance critical.

[neko-kai]

@adriaanm
It's not a regression, since I guess it didn't work in previous versions either. It's fixed in dotty, however.

@joroKr21

Also the doc says this method is performance critical.

Performance doesn't mean it should work incorrectly...

[joroKr21]

Yeah agreed if the spec interpretation that type variable constraints should count towards the implicit scope is correct, then this should be fixed.

At this point the dilemma for me is would a change in this area be accepted in 2.13 and if not is it feasible to fix this in Scala 2 or just waiting for Scala 3 would be the better choice?

[neko-kai]

@joroKr21
Scala 3 is multiple years down the line in the best case, if waiting for Scala 3 is an option, then Scala 2 development may well cease – I don't think that's a good idea!
I think it's completely feasible for Scala 2.13 given that:

1. there are very few, if any covariant higher-kinded type classes around currently,
2. the change is purely in source behavior, no binary breakage,
3. the change in behavior can theoretically lead to an implicit from a different companion object being prioritized, but it cannot lead to an implicit with an incompatible type being selected, program semantic cannot change unless both are true: type class is covariant and there are two overlapping implicits for the same type T1 in companion of T1 and in companion of its superclass T0 – which is a very unlikely situation

[adriaanm]

I think it would help to simplify the example. Here's an equivalent version that doesn't use type constructors, but fails in the same way. Most likely because Nothing is inferred somewhere and then retracted as a solution by adjustTypeArgs. I didn't dig around in the debugger to confirm.

class MonoIO[F] // it works if you make this covariant

class IO
object IO { implicit val monoInstance: MonoIO[IO] = new MonoIO[IO] }

class AnyIO[+F] // also works if you drop covariance here (and don't add it above)
object AnyIO { implicit def fromMono[F](implicit mono: MonoIO[F]): AnyIO[F] = new AnyIO[F] }

object Test {
  // if we provide this explicitly, it works even for any mix of variance: 
  // implicit val ev = AnyIO.fromMono[IO]

  implicitly[AnyIO[IO]] //(AnyIO.fromMono) even with this hint, type inference still fails 
}

This all points to a pretty fundamental limitation in Scala 2 type inference, which we likely can't fix in Scala 2. There's a lot of tickets on Nothing being inferred erroneously. Generally speaking, source-breaking changes are actually the scariest ones for 2.13.x releases (especially in type inference / implicit search).

[joroKr21]

I don't think we have a Nothing problem here.
The problem is that type variable constraints (upper bounds) are not considered for implicit scope.
When the variances are the same F can be instantiated but when they are different, we get a constrained type variable.

[adriaanm]

I suggest compiling the variants in my example with the following patch, and you can observe what happens:

--- i/src/compiler/scala/tools/nsc/typechecker/Infer.scala
+++ w/src/compiler/scala/tools/nsc/typechecker/Infer.scala
@@ -523,6 +523,7 @@ trait Infer extends Checkable {
         }
       }
 
+      println(s"adjustTypeArgs: $tparams --> ${okParams.zip(okArgs)} ++ $undetParams / $tvars / $targs under $restpe")
       AdjustedTypeArgs(okParams.toList, okArgs.toList, undetParams.toList, allArgs.toList)
     }
 

[adriaanm]

Spoiler alert:

adjustTypeArgs: List(type F) --> ListBuffer() ++ ListBuffer(type F) / List(=?Nothing) / List(Nothing) under ?
adjustTypeArgs: List(type F) --> ListBuffer() ++ ListBuffer(type F) / List(=?Nothing) / List(Nothing) under ?
/Users/adriaan/Library/Preferences/IdeaIC2019.3/scratches/scratch_107.scala:13: error: could not find implicit value for parameter e: AnyIO[IO]
  implicitly[AnyIO[IO]] //(AnyIO.fromMono) even with this hint, type inference still fails
            ^
[[syntax trees at end of                     typer]] 

versus:

adjustTypeArgs: List(type F) --> ListBuffer() ++ ListBuffer(type F) / List(=?Nothing) / List(Nothing) under ?
adjustTypeArgs: List(type F) --> ListBuffer((type F,IO)) ++ ListBuffer() / List(=?IO) / List(IO) under ?
adjustTypeArgs: List() --> ListBuffer() ++ ListBuffer() / List() / List() under ?
adjustTypeArgs: List() --> ListBuffer() ++ ListBuffer() / List() / List() under ?
[[syntax trees at end of                     typer]] // scratch_107.scala
package <empty> {
  class MonoIO[+F] extends scala.AnyRef {

[joroKr21]

But with this patch:

--- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -1444,7 +1444,10 @@ trait Implicits {
         case None =>
           val start = if (StatisticsStatics.areSomeColdStatsEnabled) statistics.startTimer(subtypeETNanos) else null
           //        val implicitInfoss = companionImplicits(pt)
-          val implicitInfoss1 = companionImplicitMap(pt).valuesIterator.toList
+          val infoMap = companionImplicitMap(pt)
+          val typeArgs = pt.typeArgs.map(targ => targ.typeSymbol -> targ.typeSymbol.info)
+          println(s"$pt ($typeArgs) -> $infoMap")
+          val implicitInfoss1 = infoMap.valuesIterator.toList
           //        val is1 = implicitInfoss.flatten.toSet
           //        val is2 = implicitInfoss1.flatten.toSet
           //        for (i <- is1)

I get:

AnyIO[IO] (List((class IO,AnyRef {
  def <init>(): IO
}))) -> LinkedHashMap(class AnyIO -> List(fromMono: ?), class IO -> List(monoInstance: ?))
MonoIO[F] (List((type F,))) -> LinkedHashMap()

But I was wrong about one thing, here F is not a type variable - it's an AbstractTypeSymbol and IO doesn't appear as an upper bound.

And anyway if it's not about implicit scope why would bringing the implicit instance into scope matter?

[adriaanm]

And anyway if it's not about implicit scope why would bringing the implicit instance into scope matter?

because it's a transitive implicit search, I think -- method calls are handled differently than just using the local val that's already fully typed

[joroKr21]

Adding an upper bound also makes it compile:

class MonoIO[F]

class IO
object IO { implicit val monoInstance: MonoIO[IO] = new MonoIO[IO] }

class AnyIO[+F] // upper bound in the definition is considered for implicit scope
object AnyIO { implicit def fromMono[F <: IO](implicit mono: MonoIO[F]): AnyIO[F] = new AnyIO[F] }

object Test {
  implicitly[AnyIO[IO]] //(AnyIO.fromMono) even with this hint, type inference still fails 
}

[joroKr21]

So I have a question - instead of keeping the original undetParams as they are, would it not be possible to enhance their bounds with the bounds of tvars as well? We already do it to substitute determined params in the bounds, but not to add newly discovered bounds (from the implicit pt). Although we have the limitation of only a single upper and lower bound. So I'm not sure what would be a good way to do that?

[joroKr21]

@adriaanm see what I meant here: scala/scala#8582