Skip to content

Conversation

@milessabin
Copy link
Contributor

@milessabin milessabin commented Oct 17, 2017

…implicit selection more consistent with normal overload resolution.

This is an attempt to make implicit selection rules align more closely with people's intuitions and the spec's aspirations that it be consistent with normal overload resolution rules. It also fixes scala/bug#10526.

Candidate implicits are ordered via Infer#isStrictlyMoreSpecific which delegates to Infer#isAsSpecific. Prior to this PR the latter treats all methods with an implicit argument list as if they were nullary methods, leading to scala/bug#10526 ... I believe that the motivation for this behaviour was to allow methods which are intended to appear to users to be nullary to have implicit arguments without affecting their overload resolution behaviour wrt same-named methods which are actually nullary. Whilst this does the right thing in some circumstances, it leads to oddities such as scala/bug#10526 and also means that the specificity test used to order and select implicits is very crude, in effect only considering the result type of an implicit method, not its implicit arguments.

This PR addresses these issues by making the "treat implicit methods as nullary" logic explicitly flagged and enabling it only at the relevant call site in Inferencer#inferExprAlternative. Normal overloading rules are unchanged, and the implicit selection logic is extracted out to ImplicitSearch#Improves. There the relative ordering of a pair of candidate implicits is computed as follows,

  1. The candidates are compared by their result type, the most specific by normal overload rules being selected (this is consistent with the behaviour prior to this PR).
  2. If (1) is a tie then we compare the lengths of the implicit argument lists of the candidates (if any). The candidate with the longest argument list wins (this matches users intuitions that methods with more implicit arguments are "more demanding" hence more specific).
  3. If (2) is a tie then we have a pair of candidates with implicit argument lists of equal length and which are both equally specific wrt their result type/the expected type. We now apply the full normal overloading resolution rules and choose the most specific.

This change makes combining implicits from multiple implicit scopes a great deal more straightforward, since we can now rely on more than just the result type of the implicit definition to guide implicit selection. After this PR the following works as expected,

class Show[T](val i: Int)
object Show {
  def apply[T](implicit st: Show[T]): Int = st.i

  implicit val showInt: Show[Int] = new Show[Int](0)
  implicit def fallback[T]: Show[T] = new Show[T](1)
}

class Generic
object Generic {
  implicit val gen: Generic = new Generic
  implicit def showGen[T](implicit gen: Generic): Show[T] = new Show[T](2)
}

object Test extends App {
  assert(Show[Int] == 0)
  assert(Show[String] == 1)
  assert(Show[Generic] == 2) // showGen beats fallback due to longer argument list
}

Thanks to the use of normal overload resolution rules we also have the ability to use a "phantom" implicit parameter with arguments ordered by subtyping to explicitly prioritize implicit definitions, something for which language extensions of one form or another have occasionally been proposed,

class Low
object Low {
  implicit val low: Low = new Low
}
class Medium extends Low
object Medium {
  implicit val medium: Medium = new Medium
}
class High extends Medium
object High {
  implicit val high: High = new High
}

class Foo[T](val i: Int)
object Foo {
  def apply[T](implicit fooT: Foo[T]): Int = fooT.i

  implicit def foo[T](implicit priority: Low): Foo[T] = new Foo[T](0)
  implicit def foobar[T](implicit priority: Low): Foo[Bar[T]] = new Foo[Bar[T]](1)
  implicit def foobarbaz(implicit priority: Low): Foo[Bar[Baz]] = new Foo[Bar[Baz]](2)
}
class Bar[T]
object Bar {
  implicit def foobar[T](implicit priority: Medium): Foo[Bar[T]] = new Foo[Bar[T]](3)
  implicit def foobarbaz(implicit priority: Medium): Foo[Bar[Baz]] = new Foo[Bar[Baz]](4)
}
class Baz
object Baz {
  implicit def baz(implicit priority: High): Foo[Bar[Baz]] = new Foo[Bar[Baz]](5)
}

object Test extends App {
  assert(Foo[Int] == 0)
  assert(Foo[Bar[Int]] == 3)
  assert(Foo[Bar[Baz]] == 5)
}

This PR changes the outcome of only one partest (test/files/neg/t7289_status_quo.scala) which is intended to exactly capture the current failure behaviour in a specific implicit resolution scenario ... I believe the new (successful) behaviour is an improvement on the old.

With that exception all (par)tests pass. One shapeless test fails to compile after this change but is trivially fixable. I'll schedule a community build when this goes green ...

@scala-jenkins scala-jenkins added this to the 2.13.0-M3 milestone Oct 17, 2017
@milessabin
Copy link
Contributor Author

As expected the community build fails due to a single shapeless test failure. Everything not downstream of shapeless builds successfully however, which is very promising.

Copy link
Member

@lrytz lrytz left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The fix for scala/bug#10526 looks good to me. About the new ranking rules, should that come with a spec update? I see that the current spec is already vague, but there are new rules now that are quite different from what we have in overloading resolution. It looks like we should bring that proposal to people's attention first - what is dotty doing?

implicitly[Ext[_ <: List[List[Int]]]] // fails - ambiguous
implicitly[Ext[_ <: List[List[Int]]]] // compiles due to f and m having equally specific result types due
// to scala/bug#10545 but f now being selected over m because it has
// the longer implicit argument list. When the fix for 10545 is
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

shouldn't the bug reference be 10526 here?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

No, that's the right bug reference ... scala/bug#10526 and scala/bug#10545 intersect here.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

See #6122.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ah got it, sorry for the noise.


def compute = {
// 1. Do we win on result type specificity?
val result0 = isStrictlyMoreSpecific(restpe1, restpe2, info1.sym, info2.sym, false)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

style nit: use a named argument when passing a literal for a boolean param (also in the other invocations of isStrictlyMoreSpecific)

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'll fix.

@milessabin
Copy link
Contributor Author

@lrytz I've pointed @smarter and @odersky at this ... some interest, but no very definite response as yet. I think this is consistent with @odersky's intentions to align implicit selection with normal overload resolution.

I'd be happy to add some language to the spec and put together a write up for general consumption.

@milessabin
Copy link
Contributor Author

Nb. shapeless has been updated to compile once this is merged.

@milessabin milessabin force-pushed the topic/implicit-overload branch from b6f0cdf to e7bb0bc Compare January 11, 2018 10:22
@milessabin
Copy link
Contributor Author

@lrytz rebased and issues addressed.

@milessabin
Copy link
Contributor Author

Rebased.

milessabin added a commit to milessabin/scala that referenced this pull request Mar 6, 2018
This is a backport of the following Dotty change to scalac,

scala/scala3@8954026

As in the Dotty implementation the specificity comparison which is used
for overload resolution and implicit selection is now performed as-if
all contravariant positions in top level type constructors were
covariant.

Currently this breaks test/files/run/t2030.scala in exactly the same way
as in Dotty as reported here,

scala/scala3#1246 (comment)

and in this PR it has been changed to a neg test. However,
test/files/run/t2030.scala passes when this PR is combined with,

scala#6139

so if/when that is merged it can be switched back to a pos test.

Fixes scala/bug#2509. Fixes scala/bug#7768.
@milessabin milessabin force-pushed the topic/implicit-overload branch from dce8db6 to 61ef9a3 Compare March 6, 2018 14:52
@milessabin
Copy link
Contributor Author

Rebased, fixed broken JUnit test, squashed, added useful commit message.

@lrytz
Copy link
Member

lrytz commented Mar 7, 2018

To me, this is still in need of a wider discussion - maybe @adriaanm can bring in a new perspective.

@milessabin
Copy link
Contributor Author

Arguably this is just aligning the implementation with the spec's aspirations, but whatever ... I'd be happy to write a short SIP up for this and have it discussed more widely. I guess I could also port to Dotty.

milessabin added a commit to milessabin/scala that referenced this pull request Mar 22, 2018
This is a backport of the following Dotty change to scalac,

scala/scala3@8954026

As in the Dotty implementation the specificity comparison which is used
for overload resolution and implicit selection is now performed as-if
all contravariant positions in top level type constructors were
covariant.

Currently this breaks test/files/run/t2030.scala in exactly the same way
as in Dotty as reported here,

scala/scala3#1246 (comment)

and in this PR it has been changed to a neg test. However,
test/files/run/t2030.scala passes when this PR is combined with,

scala#6139

so if/when that is merged it can be switched back to a pos test.

Fixes scala/bug#2509. Fixes scala/bug#7768.
This is an attempt to make implicit selection rules align more closely
with people's intuitions and the spec's aspirations that it be
consistent with normal overload resolution rules. It also fixes
scala/bug#10526.

Candidate implicits are ordered via Infer#isStrictlyMoreSpecific which
delegates to Infer#isAsSpecific. Prior to this commit the latter treats all
methods with an implicit argument list as if they were nullary methods,
leading to scala/bug#10526 ... I believe that the motivation for this
behaviour was to allow methods which are intended to appear to users to
be nullary to have implicit arguments without affecting their overload
resolution behaviour wrt same-named methods which are actually nullary.
Whilst this does the right thing in some circumstances, it leads to
oddities such as scala/bug#10526 and also means that the specificity
test used to order and select implicits is very crude, in effect only
considering the result type of an implicit method, not its implicit
arguments.

This commit addresses these issues by making the "treat implicit methods
as nullary" logic explicitly flagged and enabling it only at the
relevant call site in Inferencer#inferExprAlternative. Normal
overloading rules are unchanged, and the implicit selection logic is
extracted out to ImplicitSearch#Improves. There the relative ordering of
a pair of candidate implicits is computed as follows,

1. The candidates are compared by their result type, the most specific by
   normal overload rules being selected (this is consistent with the
   behaviour prior to this commit).

2. If (1) is a tie then we compare the lengths of the implicit argument
   lists of the candidates (if any). The candidate with the longest
   argument list wins (this matches users intuitions that methods with more
   implicit arguments are "more demanding" hence more specific).

3. If (2) is a tie then we have a pair of candidates with implicit
   argument lists of equal length and which are both equally specific wrt
   their result type/the expected type. We now apply the full normal
   overloading resolution rules and choose the most specific.  This change
   makes combining implicits from multiple implicit scopes a great deal
   more straightforward, since we can now rely on more than just the result
   type of the implicit definition to guide implicit selection. With this
   commit the following works as expected,

  class Show[T](val i: Int)
  object Show {
    def apply[T](implicit st: Show[T]): Int = st.i

    implicit val showInt: Show[Int] = new Show[Int](0)
    implicit def fallback[T]: Show[T] = new Show[T](1)
  }

  class Generic
  object Generic {
    implicit val gen: Generic = new Generic
    implicit def showGen[T](implicit gen: Generic): Show[T] = new Show[T](2)
  }

  object Test extends App {
    assert(Show[Int] == 0)
    assert(Show[String] == 1)
    assert(Show[Generic] == 2) // showGen beats fallback due to longer argument list
  }

Thanks to the use of normal overload resolution rules we also have the
ability to use a "phantom" implicit parameter with arguments ordered by
subtyping to explicitly prioritize implicit definitions, something for
which language extensions of one form or another have occasionally been
proposed,

  class Low
  object Low {
    implicit val low: Low = new Low
  }
  class Medium extends Low
  object Medium {
    implicit val medium: Medium = new Medium
  }
  class High extends Medium
  object High {
    implicit val high: High = new High
  }

  class Foo[T](val i: Int)
  object Foo {
    def apply[T](implicit fooT: Foo[T]): Int = fooT.i

    implicit def foo[T](implicit priority: Low): Foo[T] = new Foo[T](0)
    implicit def foobar[T](implicit priority: Low): Foo[Bar[T]] = new Foo[Bar[T]](1)
    implicit def foobarbaz(implicit priority: Low): Foo[Bar[Baz]] = new Foo[Bar[Baz]](2)
  }
  class Bar[T]
  object Bar {
    implicit def foobar[T](implicit priority: Medium): Foo[Bar[T]] = new Foo[Bar[T]](3)
    implicit def foobarbaz(implicit priority: Medium): Foo[Bar[Baz]] = new Foo[Bar[Baz]](4)
  }
  class Baz
  object Baz {
    implicit def baz(implicit priority: High): Foo[Bar[Baz]] = new Foo[Bar[Baz]](5)
  }

  object Test extends App {
    assert(Foo[Int] == 0)
    assert(Foo[Bar[Int]] == 3)
    assert(Foo[Bar[Baz]] == 5)
  }

This commit changes the outcome of only one partest
(test/files/neg/t7289_status_quo.scala) which is intended to exactly
capture the current failure behaviour in a specific implicit resolution
scenario ... I believe the new (successful) behaviour is an improvement
on the old.
@milessabin milessabin force-pushed the topic/implicit-overload branch from 61ef9a3 to 5f45da6 Compare March 22, 2018 20:03
@milessabin
Copy link
Contributor Author

Rebased.

milessabin added a commit to milessabin/scala that referenced this pull request Mar 29, 2018
This is a backport of the following Dotty change to scalac,

scala/scala3@8954026

As in the Dotty implementation the specificity comparison which is used
for overload resolution and implicit selection is now performed as-if
all contravariant positions in top level type constructors were
covariant.

Currently this breaks test/files/run/t2030.scala in exactly the same way
as in Dotty as reported here,

scala/scala3#1246 (comment)

and in this PR it has been changed to a neg test. However,
test/files/run/t2030.scala passes when this PR is combined with,

scala#6139

so if/when that is merged it can be switched back to a pos test.

Fixes scala/bug#2509. Fixes scala/bug#7768.
@adriaanm
Copy link
Contributor

We've discussed this in depth in our team meeting, and ran it by Martin. While we agree implicit prioritization can get tedious, we feel this PR introduces too much magic (e.g., longest argument list wins). The overall complexity of implicit resolution is already high enough. (The implicit argument list is skipped on purpose to avoid costly recursive searches.)

Ultimately, we are hopeful that we can replace type-level computation via implicit search prolog with a much more elegant, functional mechanism: type-level meta-programming.

@adriaanm adriaanm closed this Apr 17, 2018
@fommil

This comment has been minimized.

@SethTisue

This comment has been minimized.

@fommil

This comment has been minimized.

@jvican

This comment has been minimized.

@adriaanm

This comment has been minimized.

@milessabin

This comment has been minimized.

@adriaanm

This comment has been minimized.

@dwijnand

This comment has been minimized.

@SethTisue SethTisue removed this from the 2.13.0-M4 milestone May 4, 2018
milessabin added a commit to milessabin/scala that referenced this pull request Jul 26, 2018
This is a backport of the following Dotty change to scalac,

scala/scala3@8954026

As in the Dotty implementation the specificity comparison which is used
for overload resolution and implicit selection is now performed as-if
all contravariant positions in top level type constructors were
covariant.

Currently this breaks test/files/run/t2030.scala in exactly the same way
as in Dotty as reported here,

scala/scala3#1246 (comment)

and in this PR it has been changed to a neg test. However,
test/files/run/t2030.scala passes when this PR is combined with,

scala#6139

so if/when that is merged it can be switched back to a pos test.

Fixes scala/bug#2509. Fixes scala/bug#7768.
milessabin added a commit to milessabin/scala that referenced this pull request Jul 26, 2018
This is a backport of the following Dotty change to scalac,

scala/scala3@8954026

As in the Dotty implementation the specificity comparison which is used
for overload resolution and implicit selection is now performed as-if
all contravariant positions in type constructors were covariant.

Currently this breaks test/files/run/t2030.scala in exactly the same way
as in Dotty as reported here,

scala/scala3#1246 (comment)

and in this PR it has been changed to a neg test. However,
test/files/run/t2030.scala passes when this PR is combined with,

scala#6139

so if/when that is merged it can be switched back to a pos test.

Fixes scala/bug#2509. Fixes scala/bug#7768.
@kailuowang
Copy link

Cats encounter this issue when migrating to 2.13. Without this PR it's yet to see how to fix without breaking our API.
Detail in typelevel/cats#2335 (comment)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

release-notes worth highlighting in next release notes

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Implicit argument list modifier affects overload resolution with explicit arguments

9 participants