Type parameters should be instantiated before doing an implicit search

[smarter]

This is a separate issue from #738 but I think that they will need to be fixed together to get something that makes sense.
Consider the following code:

class Foo

object Test {
  def foo[T](x: T)(implicit ev: T): T = ???

  def test: Unit = {
    implicit val evidence: Foo = new Foo
    foo(new Foo)
  }
}

It currently fails with:

try/constrimpl.scala:9: error: ambiguous implicits: both getter StringCanBuildFrom in object Predef$ and getter NothingClassTag in object DottyPredef$ match type (T? >: Foo) of parameter ev of method foo in object Test$
    foo(new Foo)
                ^
try/constrimpl.scala:10: error: ambiguous implicits: both getter StringCanBuildFrom in object Predef$ and getter NothingClassTag in object DottyPredef$ match type (T? >: Foo) of parameter ev of method foo in object Test$
  }
   ^
two errors found

When we do the implicit search, T is not instantiated yet, the only thing we know is that its lower bound is Foo as the error message says: ... match type (T? >: Foo) of parameter ev of method foo .... I don't know how scalac deals with this exactly but it seems like it simply instantiate the type parameter before doing the implicit search, we should consider doing the same thing.

Note that this is also needed to properly fix #553, if we don't instantiate CC to List, then CC is only lower-bounded by List, and lower bounds of abstract types are not part of the implicit scope, this means that the implicit List.canBuildFrom will not be in the scope.

[odersky]

scalac does not generally instantiate parameters before an implicit search. If it did, the whole concept of CanBuildFrom would not work, to give an example. But parameter instantiation is different between the two systems, and it seems this example shows where dotty's way is problematic. Maybe instantiate when there are ambiguity errors otherwise?

[retronym]

FYI, here's how to get a bit of logging from scalac about type param inference.

% cat sandbox/test.scala
class Foo[A, B]

object Test {
  def foo[T, U](x: T)(implicit ev: Foo[T, U]): U = ???

  def test: Unit = {
    implicit val evidence1: Foo[Int, String] = ???
    implicit val evidence2: Foo[String, Int] = ???
    foo(1)
  }
}

% scalac -Dscalac.debug.tvar -Xprint:typer -Ytyper-debug sandbox/test.scala

|    |    |    |-- foo(1) : pt=Unit EXPRmode (site: method test in Test)
|    |    |    |    |-- foo BYVALmode-EXPRmode-FUNmode-POLYmode (silent: method test in Test)
|    |    |    |    |    [adapt] [T, U](x: T)(implicit ev: Foo[T,U])U adapted to [T, U](x: T)(implicit ev: Foo[T,U])U
|    |    |    |    |    \-> (x: T)(implicit ev: Foo[T,U])U
[    create] ?T                       ( In Test#foo[T,U] )
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    |-- 1 BYVALmode-EXPRmode-POLYmode (site: method test in Test)
|    |    |    |    |    \-> Int(1)
[    create] ?T                       ( In Test#foo[T,U] )
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    solving for (T: ?T, U: ?U)
[   setInst] Int                      ( In Test#foo[T,U], T=Int )
[   setInst] Nothing                  ( In Test#foo[T,U], U=Nothing )
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    solving for (U: ?U)
[   setInst] Nothing                  ( In Test#foo[T,U], U=Nothing )
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    solving for (U: ?U)
[   setInst] String                   ( In Test#foo[T,U], U=String )
|    |    |    |    |-- [T, U](x: T)(implicit ev: Foo[T,U])U : pt=Unit EXPRmode (silent: method test in Test)
|    |    |    |    |    |-- { Test.this.foo[Int, String](1)(evidence1); () } : pt=Unit EXPRmode (silent: method test in Test)
|    |    |    |    |    |    \-> Unit
|    |    |    |    |    [adapt] [T, U](x: T)(implicit ev: Foo[T,U])U adapted to { Test.this.foo[Int, String](1)(evidence1); () } based on pt Unit
|    |    |    |    |    \-> Unit
|    |    |    |    [adapt] [T, U](x: T)(implicit ev: Foo[T,U])U adapted to { Test.this.foo[Int, String](1)(evidence1); () } based on pt Unit
|    |    |    |    \-> Unit
|    |    |    \-> Unit
|    |    \-> [def test] => Unit
|    \-> [object Test] Test.type
[[syntax trees at end of                     typer]] // test.scala
package <empty> {
  class Foo[A, B] extends scala.AnyRef {
    def <init>(): Foo[A,B] = {
      Foo.super.<init>();
      ()
    }
  };
  object Test extends scala.AnyRef {
    def <init>(): Test.type = {
      Test.super.<init>();
      ()
    };
    def foo[T, U](x: T)(implicit ev: Foo[T,U]): U = scala.this.Predef.???;
    def test: Unit = {
      implicit val evidence1: Foo[Int,String] = scala.this.Predef.???;
      implicit val evidence2: Foo[String,Int] = scala.this.Predef.???;
      {
        Test.this.foo[Int, String](1)(evidence1);
        ()
      }
    }
  }
}

[smarter]

@odersky : Yes, that description is not exactly right: in Scala 2, type parameters are instantiated after the first parameter list in which they appear, for example:

class Foo
class Bar extends Foo

object Test {
  def one[T](x: T, y: T): T = x
  def two[T](x: T)(y: T): T = x
  def twob[T](x: T)(y: T): Nothing = ???
  def two2[T,S](x: T)(y: S): T = x

  def test = {
    one(new Bar, new Foo) // scala and dotty: T=Foo
    two(new Bar)(new Foo) // scala: T=Bar, type mismatch; dotty: T=Foo
    twob(new Bar)(new Foo) // scala: T=Bar, type mismatch; dotty: T=Any
    two2(new Bar)(new Foo) // scala: T=Bar, S=Foo; dotty: T=Bar, S=Any
  }
}

The behavior of scalac with implicits is just a special case of that: type parameters which appear in a parameter list before an implicit parameter list will be instantiated, others won't so CanBuildFrom works fine. The behavior of dotty is not really consistent.

[retronym]

I think it is more accurate to say that the compiler attempts to instantiate them all, but retracts ones that solve to Nothing.

[retronym]

One more note: -Ytyper-debug is currently a bit crippled, a lot of useful messages are filtered out during implicit search.

Applying this diff:

git diff -- '**/Implicits.scala'
diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
index 7ec9cd7..1b5783f 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -325,7 +325,7 @@ trait Implicits {
   class ImplicitSearch(tree: Tree, pt: Type, isView: Boolean, context0: Context, pos0: Position = NoPosition) extends Typer(context0) with ImplicitsContextErrors {
     val searchId = implicitSearchId()
     private def typingLog(what: String, msg: => String) =
-      typingStack.printTyping(tree, f"[search #$searchId] $what $msg")
+      typingStack.printTyping(f"[search #$searchId] $what $msg")

     import infer._
     if (Statistics.canEnable) Statistics.incCounter(implicitSearchCount)

Shows the interaction between implicit search and inference more explicitly:

|    |    |    |-- foo(1) : pt=Unit EXPRmode (site: method test in Test)
|    |    |    |    |-- foo BYVALmode-EXPRmode-FUNmode-POLYmode (silent: method test in Test)
|    |    |    |    |    [adapt] [T, U](x: T)(implicit ev: Foo[T,U])U adapted to [T, U](x: T)(implicit ev: Foo[T,U])U
|    |    |    |    |    \-> (x: T)(implicit ev: Foo[T,U])U
[    create] ?T                       ( In Test#foo[T,U] )
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    |-- 1 BYVALmode-EXPRmode-POLYmode (site: method test in Test)
|    |    |    |    |    \-> Int(1)
[    create] ?T                       ( In Test#foo[T,U] )
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    solving for (T: ?T, U: ?U)
[   setInst] Int                      ( In Test#foo[T,U], T=Int )
[   setInst] Nothing                  ( In Test#foo[T,U], U=Nothing )
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    solving for (U: ?U)
[   setInst] Nothing                  ( In Test#foo[T,U], U=Nothing )
|    |    |    |    [search #1] start `[T, U](x: T)(implicit ev: Foo[T,U])U` inferring type U, searching for adaptation to pt=Foo[Int,U] (silent: method test in Test) implicits disabled
|    |    |    |    [search #1] considering evidence1
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    [search #1] solve tvars=?U, tvars.constr= >: String <: String
|    |    |    |    solving for (U: ?U)
[   setInst] String                   ( In Test#foo[T,U], U=String )
|    |    |    |    [search #1] success inferred value of type Foo[Int,=?String] is SearchResult(evidence1, TreeTypeSubstituter(List(type U),List(String)))
|    |    |    |    |-- [T, U](x: T)(implicit ev: Foo[T,U])U : pt=Unit EXPRmode (silent: method test in Test)
|    |    |    |    |    |-- { Test.this.foo[Int, String](1)(evidence1); () } : pt=Unit EXPRmode (silent: method test in Test)
|    |    |    |    |    |    \-> Unit
|    |    |    |    |    [adapt] [T, U](x: T)(implicit ev: Foo[T,U])U adapted to { Test.this.foo[Int, String](1)(evidence1); () } based on pt Unit
|    |    |    |    |    \-> Unit
|    |    |    |    [adapt] [T, U](x: T)(implicit ev: Foo[T,U])U adapted to { Test.this.foo[Int, String](1)(evidence1); () } based on pt Unit
|    |    |    |    \-> Unit

[retronym]

Here's an test case that shows the difference between the "try to instantiate but retract nothing" and "instantiate when referred to in a param list" description:

class Foo[A, B]
class Test {
  implicit val f: Foo[Int, String] = ???
  def t[A, B >: A](a: A)(implicit f: Foo[A, B]) = ???
  t(1)
}

This fails with could not find implicit of Foo[Int, Int].

|    |-- t(1) BYVALmode-EXPRmode (site: value <local Test> in Test)
|    |    |-- t BYVALmode-EXPRmode-FUNmode-POLYmode (silent: value <local Test> in Test)
|    |    |    [adapt] [A, B >: A](a: A)(implicit f: Foo[A,B])Nothing adapted to [A, B >: A](a: A)(implicit f: Foo[A,B])Nothing
|    |    |    \-> (a: A)(implicit f: Foo[A,B])Nothing
|    |    |-- 1 BYVALmode-EXPRmode-POLYmode (site: value <local Test> in Test)
|    |    |    \-> Int(1)
|    |    solving for (A: ?A, B: ?B)
|    |    [search #1] start `[A, B >: A](a: A)(implicit f: Foo[A,B])Nothing`, searching for adaptation to pt=Foo[Int,Int] (silent: value <local Test> in Test) implicits disabled
sandbox/instantiate.scala:5: error: could not find implicit value for parameter f: Foo[Int,Int]
  t(1)
   ^
|    |    |-- [A, B >: A](a: A)(implicit f: Foo[A,B])Nothing BYVALmode-EXPRmode (site: value <local Test> in Test)
|    |    |    [search #2] start `()`, searching for adaptation to pt=Unit => Foo[Int,Int] (silent: value <local Test> in Test) implicits disabled
|    |    |    [search #3] start `()`, searching for adaptation to pt=(=> Unit) => Foo[Int,Int] (silent: value <local Test> in Test) implicits disabled
|    |    |    \-> <error>
|    |    [adapt] [A, B >: A](a: A)(implicit f: Foo[A,B])Nothing adapted to [A, B >: A](a: A)(implicit f: Foo[A,B])Nothing
|    |    \-> <error>

[smarter]

I think it is more accurate to say that the compiler attempts to instantiate them all, but retracts ones that solve to Nothing.

@retronym Ah indeed, I didn't know that! I think that for dotty we want to avoid special-casing Nothing in type inference, so the rule "instantiate when referred to in a param list" would be a good way to do that. It would have some other nice intuitive properties, like the fact that adding an empty parameter list cannot change the result of inference, unlike what happens with scalac:

class Foo
class Bar extends Foo

object Test {
  def a[T >: Foo](x: T): T = x
  def b[T >: Foo]()(y: T): T = y

  def test = {
    a(new Bar) // scalac: T=Bar
    b()(new Bar) // scalac: T=Foo
  }
}

[smarter]

(FWIW, I have a hacky implementation of my proposed scheme at https://github.com/smarter/dotty/commits/fix/tp-instantiation-scheme but it uncovered some other issues in dotty I need to fix first before opening a PR for it, it also breaks inference for some scala2 library methods like zip)

[odersky]

On Wed, Aug 5, 2015 at 7:43 PM, Jason Zaugg notifications@github.com
wrote:

I think it is more accurate to say that the compiler attempts to
instantiate them all, but retracts ones that solve to Nothing.

Yes, that's the problem. dotty does not have the "fear of Nothing", but
it does not instantiate type parameters eagerly either. It's a delicate
question. Maybe instantiate type params only if ambiguity errors are
encountered?

• Martin

—

Reply to this email directly or view it on GitHub
#739 (comment).

Martin Odersky
EPFL

[odersky]

On Wed, Aug 5, 2015 at 7:56 PM, Guillaume Martres notifications@github.com
wrote:

I think it is more accurate to say that the compiler attempts to
instantiate them all, but retracts ones that solve to Nothing.

@retronym https://github.com/retronym Ah indeed, I didn't know that! I
think that for dotty we want to avoid special-casing Nothing in type
inference, so the rule "instantiate when referred to in a param list" would
be a good way to do that.

But how do you define that precisely? Does the argument need a type which
contains the typevar? What if it only has another typevar that contains
this typevar as a bound?

• Martin

It would have some other nice intuitive properties, like the fact that
adding an empty parameter list cannot change the result of inference,
unlike what happens with scalac:

class Fooclass Bar extends Foo
object Test {
def a[T >: Foo](x: T): T = x
def bT >: Foo(y: T): T = y

def test = {
a(new Bar) // scalac: T=Bar
b()(new Bar) // scalac: T=Foo
}
}

—
Reply to this email directly or view it on GitHub
#739 (comment).

Martin Odersky
EPFL

[smarter]

But how do you define that precisely? Does the argument need a type which
contains the typevar? What if it only has another typevar that contains
this typevar as a bound?

"A type which contains the typevar" looks like a good rule to me since it's easy to visually identify, this is what I implemented in my prototype: https://github.com/smarter/dotty/commits/fix/tp-instantiation-scheme

Your proposal could work too, but note that some methods like foldLeft work better if we try to infer type parameters eagerly: https://issues.scala-lang.org/browse/SI-9262?focusedCommentId=72280&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-72280 (I'm sure that whatever we choose, we'll end up breaking inference for some methods, but it'd be good to decide which patterns are useful / worth preserving).

[odersky]

@smarter We could say: "Before typing an implicit parameter list of a method m, instantiate all type parameters of m that occur in the type of some preceding value parameter of m." Is that what your prototype does?

foldLeft already works as intended I believe. The general principle in dotty is not to interpolate type vars except in a handful of situations. One such situation is when we need to infer the type of the parameter of a lambda. In that case we instantiate the expected type of the lambda by interpolating all its type variables.

[smarter]

We could say: "Before typing an implicit parameter list of a method m, instantiate all type parameters of m that occur in the type of some preceding value parameter of m." Is that what your prototype does?

No, I don't special case implicit parameter lists, here's an example of how my prototype works:

def foo[T, S](x: Thing[T])(y: OtherThing[S]) = ???
foo(arg1)(arg2)

1. Typer will first type foo which will not instantiate anything
2. Then we type foo(arg1). At this point we notice that T appears in the current formal parameter list ((x: Thing[T])), so we instantiate it, there are two cases:
   • If T only appears contravariantly in the current parameter list, we maximize T, this solves type parameter inference behaves unexpectedly when a type parameter is used in a contravariant position #718
   • Otherwise, we minimize T.
3. Then we type foo(arg1)(arg2). At this point we notice that S appears in the current formal parameter list ((y: OtherThing[S])), so we instantiate it, the details are the same as in 2.

foldLeft already works as intended I believe. The general principle in dotty is not to interpolate type vars except in a handful of situations. One such situation is when we need to infer the type of the parameter of a lambda. In that case we instantiate the expected type of the lambda by interpolating all its type variables.

Interesting, I did not know that. That covers the most common usecase for multiple parameter lists, but there are other cases where people rely on eager instantiation, for example: http://stackoverflow.com/questions/31177695/shapeless-hlist-type-checking/31192042#31192042 So we need to decide if it's worth breaking compatibility here.