implicit resolution of F[A] for introduced F[_] and A #10753

fommil · 2018-03-01T10:05:51Z

I expected the following code to compile

trait Bar[F[_]]

trait Foo[A]
object Foo {
  implicit def string: Foo[String] = ???
  implicit def bar: Bar[Foo] = ???
}

case class Problem[A](a: A)
object Problem {
  implicit def deriv[A, F[_]](implicit F: F[A], B: Bar[F]): F[Problem[A]] = ???

  deriv[String, Foo] // works

  implicitly[Foo[Problem[String]]]
}

but I get

could not find implicit value for parameter e: Foo[Problem[String]]
[error]   implicitly[Foo[Problem[String]]]
[error]             ^

This is minimised, if you remove the B: Bar[F] constraint, it compiles (but then I don't have everything I need)

Is there a workaround?

The text was updated successfully, but these errors were encountered:

fommil · 2018-03-01T10:29:32Z

(I closed this because I had a typo, then I fixed it and reopened...)

soronpo · 2018-03-01T10:33:31Z

FYI, works in dotty
https://scastie.scala-lang.org/znkjYw5gQayTwv6r1r15qQ

soronpo · 2018-03-01T10:35:07Z

The error I'm getting for scalac

Error:(41, 13) diverging implicit expansion for type Foo[Problem[String]]
starting with method deriv in object Problem
  implicitly[Foo[Problem[String]]]

fommil · 2018-03-01T10:37:22Z

@soronpo that's interesting about dotty! Where is the diverging implicit error coming from? Is this some additional debugging you've got?

soronpo · 2018-03-01T10:39:44Z

The full error:

Error:(15, 13) diverging implicit expansion for type Foo[Problem[String]]
starting with method deriv in object Problem
  implicitly[Foo[Problem[String]]]
Error:(15, 13) not enough arguments for method implicitly: (implicit e: Foo[Problem[String]])Foo[Problem[String]].
Unspecified value parameter e.
  implicitly[Foo[Problem[String]]]

I'm using TLS 2.12.4 (literal types) with -Xsource:2.13

Jasper-M · 2018-03-01T10:49:37Z

If implicitly[Foo[Problem[String]]] is inside object Problem I get diverging implicit expansion. If it's outside I get implicit not found.

soronpo · 2018-03-01T10:54:39Z

If implicitly[Foo[Problem[String]]] is inside object Problem I get diverging implicit expansion. If it's outside I get implicit not found.

In dotty it compiles in either case

Jasper-M · 2018-03-01T11:05:16Z

If implicitly[Foo[Problem[String]]] is inside object Problem I get diverging implicit expansion. If it's outside I get implicit not found.

Hmm, looks like that implicit not found error was rather because deriv was not in the implicit scope. (although I think it should be, because Problem is part of the type?)

EDIT: I think this is actually the problem here: implicit scope (or implicit priorities?).

If you import the implicits it starts working:

trait Bar[F[_]]

trait Foo[A]
object Foo {
  implicit def string: Foo[String] = ???
  implicit def bar: Bar[Foo] = ???
}

case class Problem[A](a: A)
object Problem {
  implicit def deriv[A, F[_]](implicit F: F[A], B: Bar[F]): F[Problem[A]] = ???

  import Foo._
  implicitly[Foo[Problem[String]]]
}

Still doesn't definitively explain why adding or removing B: Bar[F] makes a difference.

fommil · 2018-03-01T11:28:53Z

This hack of importing the Foo._ doesn't work in the real (unminimised) version of the problem fthomas/refined#447 it also wouldn't be a feasible workaround. I'd like to take the complexity hit in the deriv definition to avoid the user having to do anything.

To make the minimisation more realistic, let's rename object Problem to object Main.

fommil · 2018-03-01T11:32:25Z

changing to

object Deriver {
  implicit def deriv[A, F[_]](implicit F: F[A], B: Bar[F]): F[Problem[A]] = ???
}
object Main {
  import Deriver._
  deriv[String, Foo] // works

  import Foo._
  implicitly[Foo[Problem[String]]]
}

I still get

could not find implicit value for parameter e: Foo[Problem[String]]
[error]   implicitly[Foo[Problem[String]]]

Jasper-M · 2018-03-01T11:37:58Z

Strange. It works for me.

fommil · 2018-03-01T11:39:11Z

@Jasper-M I'm on scala 2.12.4, what are you using?

Jasper-M · 2018-03-01T11:40:29Z

Same. Using REPL :paste however. That might make some difference in bizarre edge cases...

fommil · 2018-03-01T11:41:26Z

@Jasper-M any special flags? I'm just using

scalaVersion in ThisBuild := "2.12.4"
scalacOptions in ThisBuild ++= Seq(
  "-language:_",
  "-Ypartial-unification",
  "-deprecation"
)

Jasper-M · 2018-03-01T11:43:55Z

@fommil No flags. Enabling -Ypartial-unification brought the error back for me.

fommil · 2018-03-01T11:53:19Z

maybe playing around with the parameter ordering might help in that case.

fommil · 2018-03-01T13:32:15Z

removing partial-unification PLUS adding the explicit import Foo._ allows it to compile. But adding the import should not be necessary at all, it looks like there is a bug in implicit search here.

soronpo · 2018-03-01T13:35:01Z

Indeed. That's why it works in dotty 😄 . I think I also ran into this in my own library, but didn't try to minimize and have such implicits in an import.

fommil · 2018-03-01T13:35:21Z

ok... I can get it to compile with the partial-unification enabled if I swap the implicit parameters

  implicit def deriv[F[_], A](implicit B: Bar[F], F: F[A]): F[Problem[A]] = ???

ordering of the type parameters does not matter.

We're still back to "why is the import needed?"

joroKr21 · 2018-03-01T20:08:10Z

Can you guess why it is diverging? Well we want an implicit F[A] for any F[_] and any A. But F[Problem[A]] is such an implicit! Thus infinite recursion and divergence. Moving Bar[F] in the beginning is the correct solution as it will fix F to Foo.

Edit: For me the order of the type parameters does matter (F[_] should come first) on Scala 2.13.0-M3

fommil · 2018-03-01T20:43:06Z

@joroKr21 ah! Thanks for the explanation. However, we still need the import Foo._ or it does not compile. This appears to be the bug.

joroKr21 · 2018-03-01T21:05:09Z

Ah yes, I convinced myself that it's a bug. It looks like the expected type Foo[Problem[String]] should constrain the type parameters enough so that only the correct implicits apply.

fommil · 2018-03-03T11:02:40Z

ok, so I think I understand the restriction... it seems

 implicit def deriv[F[_], A](implicit B: Bar[F], F: F[A]): F[Problem[A]] = ???

solving for B fixes F, but F's companion is not included in implicit scope so it is not possible to solve for F[A]. In general I think the bug is that solved types do not contribute to the implicit scope, but they should do!

joroKr21 · 2018-03-04T11:16:20Z

Well it looks in the immediate scope first, which doesn't include object Foo yet. The problem is that it's looking for Bar[?] (i.e. F is not instantiated to Foo yet, but it should be). So it doesn't proceed to the implicit scope of Foo because it's not even part of the pattern type.

fommil · 2018-03-04T11:28:16Z

right, so it can't solve for Bar[F] unless it knows to search on F's companion... which probably means it needs to search all companions. sigh

adriaanm · 2018-03-08T13:49:43Z

Excellent investigation, but I disagree that F should be instantiated to Foo before the implicit search starts. Consider the equivalent problem, forgetting about implicits for now:

trait Bar[F[_]]
trait Foo[A]
class Problem[A](a: A)
object Problem {
  def deriv[A, F[_]]: F[Problem[A]] = ???

  deriv: Foo[Problem[String]]
}

When running with additional tracing (patch below), and under -Xprint:typer -Ytyper-debug:

|    |-- (deriv: Foo[Problem[String]]) BYVALmode-EXPRmode (site: value <local Problem> in Problem) 
|    |    |-- Foo[Problem[String]] TYPEmode (site: value <local Problem> in Problem) 
|    |    |    |-- Problem[String] TYPEmode (site: value <local Problem> in Problem) 
|    |    |    |    |-- String TYPEmode (site: value <local Problem> in Problem) 
|    |    |    |    |    [adapt] String is now a TypeTree(String)
|    |    |    |    |    \-> String
|    |    |    |    \-> Problem[String]
|    |    |    \-> Foo[Problem[String]]
|    |    |-- deriv : pt=Foo[Problem[String]] EXPRmode (site: value <local Problem> in Problem) 
[    create] ?A                       ( In Problem#deriv[A,F[_]] )
[    create] ?F                       ( In Problem#deriv[A,F[_]] )
[    create] ?F[Problem[?A]]          ( In Problem#deriv[A,F[_]] )
[ applyArgs] ?F[Problem[?A]]          ( In Problem#deriv[A,F[_]], apply args Problem[?A] to F )
[addHiBound] String                   ( For Problem#deriv[A,F[_]]'s A / sharesConstraints=false )
[addLoBound] String                   ( For Problem#deriv[A,F[_]]'s A / sharesConstraints=false )
[addLoBound] String                   ( For Problem#deriv[A,F[_]]'s A / sharesConstraints=false )
[addHiBound] String                   ( For Problem#deriv[A,F[_]]'s A / sharesConstraints=false )
[addHiBound] Foo                      ( For Problem#deriv[A,F[_]]'s F / sharesConstraints=false )
|    |    |    solving for (A: ?A, F: ?F)
solving List(?A, ?F)/List(type A, type F)/List(, [_])
solveOne0(tv, tp, v, b)=(TVar<A=null>,type A,invariant,Nothing)
solving ?A false List(String)List(String)
[   setInst] String                   ( In Problem#deriv[A,F[_]], A=String )
solving =?String false List(String)List(String) = String
solveOne0(tv, tp, v, b)=(TVar<F=null>,type F,covariant,[_]Nothing)
solving ?F false List()List()
[   setInst] Nothing                  ( In Problem#deriv[A,F[_]], F=Nothing )
solving =?Nothing false List()List() = Nothing
|    |    |    [adapt] [A, F[_]]=> F[Problem[A]] adapted to [A, F[_]]=> F[Problem[A]] based on pt Foo[Problem[String]]
|    |    |    \-> Nothing
|    |    \-> Foo[Problem[String]]
|    \-> [object Problem] Problem.type
[[syntax trees at end of                     typer]] // foobar.scala
package <empty> {
  abstract trait Bar[F[_] >: [_]Nothing <: [_]Any] extends scala.AnyRef;
  abstract trait Foo[A] extends scala.AnyRef;
  class Problem[A] extends scala.AnyRef {
    <paramaccessor> private[this] val a: A = _;
    def <init>(a: A): Problem[A] = {
      Problem.super.<init>();
      ()
    }
  };
  object Problem extends scala.AnyRef {
    def <init>(): Problem.type = {
      Problem.super.<init>();
      ()
    };
    def deriv[A, F[_] >: [_]Nothing <: [_]Any]: F[Problem[A]] = scala.Predef.???;
    (Problem.this.deriv[String, Nothing]: Foo[Problem[String]])
  }
}

Specifically, we only add an upper bound for F ([addHiBound] Foo) -- there is no lower bound, and thus it gets instantiated to our good friend, Nothing.

Patch:

diff --git i/src/reflect/scala/reflect/internal/Types.scala w/src/reflect/scala/reflect/internal/Types.scala
index bec839b..9508b97 100644
--- i/src/reflect/scala/reflect/internal/Types.scala
+++ w/src/reflect/scala/reflect/internal/Types.scala
@@ -2887,11 +2887,11 @@ trait Types
     @inline final def trace[T](action: String, msg: => String)(value: T): T = {
       // Uncomment the following for a compiler that has some diagnostics about type inference
       // I doubt this is ever useful in the wild, so a recompile will be needed
-//    val s = msg match {
-//      case ""   => ""
-//      case str  => "( " + str + " )"
-//    }
-//    Console.err.println("[%10s] %-25s%s".format(action, value, s))
+       val s = msg match {
+         case ""   => ""
+         case str  => "( " + str + " )"
+       }
+       Console.err.println("[%10s] %-25s%s".format(action, value, s))
       value
     }
 
@@ -3088,6 +3088,7 @@ trait Types
     def addLoBound(tp: Type, isNumericBound: Boolean = false) {
       assert(tp != this, tp) // implies there is a cycle somewhere (?)
       //println("addLoBound: "+(safeToString, debugString(tp))) //DEBUG
+      TypeVar.trace("addLoBound", s"For $originLocation's $originName / sharesConstraints=${sharesConstraints(tp)}")(tp)
       if (!sharesConstraints(tp)) {
         undoLog record this
         constr.addLoBound(tp, isNumericBound)
@@ -3097,6 +3098,7 @@ trait Types
     def addHiBound(tp: Type, isNumericBound: Boolean = false) {
       // assert(tp != this)
       //println("addHiBound: "+(safeToString, debugString(tp))) //DEBUG
+      TypeVar.trace("addHiBound", s"For $originLocation's $originName / sharesConstraints=${sharesConstraints(tp)}")(tp)
       if (!sharesConstraints(tp)) {
         undoLog record this
         constr.addHiBound(tp, isNumericBound)
diff --git i/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala w/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala
index 2697824..bccedff 100644
--- i/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala
+++ w/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala
@@ -196,7 +196,7 @@ private[internal] trait TypeConstraints {
         val up = if (variance.isContravariant) !upper else upper
         tvar.constr.inst = null
         val bound: Type = if (up) tparam.info.bounds.hi else tparam.info.bounds.lo
-        //Console.println("solveOne0(tv, tp, v, b)="+(tvar, tparam, variance, bound))
+        Console.println("solveOne0(tv, tp, v, b)="+(tvar, tparam, variance, bound))
         var cyclic = bound contains tparam
         foreach3(tvars, tparams, variances)((tvar2, tparam2, variance2) => {
           val ok = (tparam2 != tparam) && (
@@ -238,7 +238,7 @@ private[internal] trait TypeConstraints {
         }
         tvar.constr.inst = NoType // necessary because hibounds/lobounds may contain tvar
 
-        //println("solving "+tvar+" "+up+" "+(if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds)+((if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds) map (_.widen)))
+        println("solving "+tvar+" "+up+" "+(if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds)+((if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds) map (_.widen)))
         val newInst = (
           if (up) {
             if (depth.isAnyDepth) glb(tvar.constr.hiBounds)
@@ -252,11 +252,11 @@ private[internal] trait TypeConstraints {
 
         debuglog(s"$tvar setInst $newInst")
         tvar setInst newInst
-        //Console.println("solving "+tvar+" "+up+" "+(if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds)+((if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds) map (_.widen))+" = "+tvar.constr.inst)//@MDEBUG
+        Console.println("solving "+tvar+" "+up+" "+(if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds)+((if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds) map (_.widen))+" = "+tvar.constr.inst)//@MDEBUG
       }
     }
 
-    // println("solving "+tvars+"/"+tparams+"/"+(tparams map (_.info)))
+    println("solving "+tvars+"/"+tparams+"/"+(tparams map (_.info)))
     foreach3(tvars, tparams, variances)(solveOne)
 
     def logBounds(tv: TypeVar) = log {

fommil · 2018-03-08T13:58:11Z

@adriaanm thanks for that. What is the consequence, is there a workaround to force the lower bound or are you saying this is just not something scala compiler can do?

adriaanm · 2018-03-08T14:17:04Z

It's not so much "can't" as "won't" -- a return type is in a covariant position, which is fundamental to OO (since a method is allowed to return a value of any subtype of its result type, we can only constrain from above the type variable that represents that unknown type). This applies equally for regular method calls as well as the method that produce implicit values -- there needs to be subtype slack, so that they can provide an instance of a subtype of the expected type.

It could be possible to refactor your application so that there are more constraints in the mix (such as what happens when you import the implicit values, which means their availability determines the result of type inference). I played around a bit with the code, but it really depends on the greater context.

soronpo · 2018-03-08T14:20:46Z

Then why does it compile in Dotty?

fommil · 2018-03-08T14:24:01Z

@adriaanm greater context is exactly this usecase
https://github.com/fthomas/refined/blob/master/modules/scalaz/shared/src/main/scala/eu/timepit/refined/scalaz/package.scala#L47-L73

example use in https://github.com/fthomas/refined/blob/master/modules/scalaz/shared/src/test/scala-2.12/eu/timepit/refined/scalaz/RefTypeSpecScalazMonadError.scala

i.e. we want to get automatic typeclass derivation for Refined types if they have a Contravariant or MonadError on their companion (which is common for many of our typeclasses).

We use a lot of Refined types on our (boke) Play endpoints.

adriaanm · 2018-03-08T15:05:34Z

Then why does it compile in Dotty?

I don't know, does it still work after scala/scala3#4080 was merged?

joroKr21 · 2018-03-08T22:56:38Z

@adriaanm The example compiles on dotty master, but your argument is compelling. Keeping subtyping in mind, we can modify it in in a way to make it compile with scalac and fail with dotty:

trait Bar[F[_]]
trait Foo[A]
trait Qux[A] extends Foo[A]
object Qux {
  implicit def string: Qux[String] = ???
  implicit def bar: Bar[Qux] = ???
}

case class Problem[A](a: A)
object Problem {
  import Qux._
  implicit def deriv[A, F[_]](implicit B: Bar[F], F: F[A]): F[Problem[A]] = ???
  implicitly[Foo[Problem[String]]]
}

Import still necessary ofc.

adriaanm · 2018-03-09T09:24:18Z

I hope the meta-takeaway is also coming across, but, for the casual reader: relying on fancy type inference is bound to cause work at some point (even within the 2.x series, although we are generally very resistant to touching type inference for this very reason).

It would be great to have tooling that can insert the minimal set of annotations / type arguments to ensure type checking on different versions has the same result. Some kind of fancy cross-compiler AST diffing and patch generation.

fommil · 2018-03-09T10:00:37Z

@adriaanm I assume you want to close the ticket then?

It would be good if there was some other workaround that we could use to avoid enforcing downstream users to import their contravariant / monaderror instances.

adriaanm · 2018-03-09T10:26:12Z

Yes, I'm afraid this is a won't-fix for the 2.x series, unless there's a feasible carry-over from Dotty that allows us to improve this. I agree inferring Nothing is such a downer.

Before closing, let me ping the other side of the street in case they have any suggestions /cc @smarter, @OlivierBlanvillain :-)

fommil · 2018-03-29T19:46:53Z

scalaz has a NotNothing evidence. I was wondering if that would be worth trying out (I do not have high hopes).

fommil · 2018-03-29T20:52:16Z

that's a nope on NotNothing. It was always a longshot.

fommil closed this as completed Mar 1, 2018

fommil reopened this Mar 1, 2018

joroKr21 mentioned this issue Mar 4, 2018

Diverging implicit expansion for type for the first implicit parameter search #8773

Open

lrytz added the Lightbend support label Mar 5, 2018

joroKr21 mentioned this issue Mar 20, 2018

Constraint solving of higher-kinded type variables is too coarse scala/scala3#4147

Closed

fommil closed this as completed Jul 5, 2018

implicit resolution of F[A] for introduced F[_] and A #10753

implicit resolution of F[A] for introduced F[_] and A #10753

Comments

fommil commented Mar 1, 2018 • edited Loading

fommil commented Mar 1, 2018

soronpo commented Mar 1, 2018

soronpo commented Mar 1, 2018 • edited Loading

fommil commented Mar 1, 2018

soronpo commented Mar 1, 2018

Jasper-M commented Mar 1, 2018

soronpo commented Mar 1, 2018

Jasper-M commented Mar 1, 2018 • edited Loading

fommil commented Mar 1, 2018

fommil commented Mar 1, 2018

Jasper-M commented Mar 1, 2018

fommil commented Mar 1, 2018

Jasper-M commented Mar 1, 2018

fommil commented Mar 1, 2018

Jasper-M commented Mar 1, 2018

fommil commented Mar 1, 2018

fommil commented Mar 1, 2018

soronpo commented Mar 1, 2018

fommil commented Mar 1, 2018

joroKr21 commented Mar 1, 2018 • edited Loading

fommil commented Mar 1, 2018

joroKr21 commented Mar 1, 2018

fommil commented Mar 3, 2018 • edited Loading

joroKr21 commented Mar 4, 2018 • edited Loading

fommil commented Mar 4, 2018

adriaanm commented Mar 8, 2018 • edited Loading

fommil commented Mar 8, 2018

adriaanm commented Mar 8, 2018

soronpo commented Mar 8, 2018

fommil commented Mar 8, 2018 • edited Loading

adriaanm commented Mar 8, 2018

joroKr21 commented Mar 8, 2018

adriaanm commented Mar 9, 2018

fommil commented Mar 9, 2018

adriaanm commented Mar 9, 2018 • edited Loading

fommil commented Mar 29, 2018

fommil commented Mar 29, 2018

fommil commented Mar 1, 2018 •

edited

Loading

soronpo commented Mar 1, 2018 •

edited

Loading

Jasper-M commented Mar 1, 2018 •

edited

Loading

joroKr21 commented Mar 1, 2018 •

edited

Loading

fommil commented Mar 3, 2018 •

edited

Loading

joroKr21 commented Mar 4, 2018 •

edited

Loading

adriaanm commented Mar 8, 2018 •

edited

Loading

fommil commented Mar 8, 2018 •

edited

Loading

adriaanm commented Mar 9, 2018 •

edited

Loading