Change rules for given prioritization

[odersky]

Consider the following program:

class A
class B extends A
class C extends A

given A = A()
given B = B()
given C = C()

def f(using a: A, b: B, c: C) =
  println(a.getClass)
  println(b.getClass)
  println(c.getClass)

@main def Test = f

With the current rules, this would fail with an ambiguity error between B and C when trying to synthesize the A parameter. This is a problem without an easy remedy.

We can fix this problem by flipping the priority for implicit arguments. Instead of requiring an argument to be most specific, we now require it to be most general while still conforming to the formal parameter.

There are three justifications for this change, which at first glance seems quite drastic:

• It gives us a natural way to deal with inheritance triangles like the one in the code above. Such triangles are quite common.
• Intuitively, we want to get the closest possible match between required formal parameter type and synthetisized argument. The "most general" rule provides that.
• We already do a crucial part of this. Namely, with current rules we interpolate all type variables in an implicit argument downwards, no matter what their variance is. This makes no sense in theory, but solves hairy problems with contravariant typeclasses like Comparable. Instead of this hack, we now do something more principled, by flipping the direction everywhere, preferring general over specific, instead of just flipping contravariant type parameters.

[odersky]

This is a test PR, to see what breaks in the CB.

[odersky]

It turns out nothing broke. I only had to change

• some tests that explicitly tested the old behavior
• a typo in a shapeless 3 test which was not caught because of the old behavior

So I think we can go ahead with this. What's currently implemented:

• Change to the new scheme in 3.5
• Diagnose with a warning where the precedence will change in 3.5-migration

In 3.4 we only revert back overloading resolution to be always specializing without flipping contravariant arguments. I believe that was a mistake to do it in the first place. The only use cases for the strange flip came from implicit arguments, there was never a question to extend it to overloading resolutioin.

[smarter]

The implementation looks good to me, but I believe this will need to be experimental until we go through the SIP process since it's a spec change.

• Concerning the change for 3.4:

  In 3.4 we only revert back overloading resolution to be always specializing without flipping contravariant arguments. I believe that was a mistake to do it in the first place. The only use cases for the strange flip came from implicit arguments, there was never a question to extend it to overloading resolutioin.

  The spec says (/cc @sjrd):

  If there are several eligible arguments which match the implicit parameter's type, a most specific one will be chosen using the rules of static overloading resolution.

  This is nice since it's really parsimonious, if implicit specificity and overloading resolution diverge, we'll pay a price in term of spec complexity.

• Concerning the main change:

  It gives us a natural way to deal with inheritance triangles like the one in the code above. Such triangles are quite common.

  This is true, but I'm not sure if the change as-is fixes the kind of issues people encounter in practice with triangles. The typical issue seems to be something like:

  trait Functor[F[_]]:
    extension [A, B](x: F[A]) def map(f: A => B): F[B]
  trait Monad[F[_]] extends Functor[F] { ... }
  trait Traverse[F[_]] extends Functor[F] { ... }
  
  given Monad[List] with Traverse[List] with { ... }
  
  def test[F[_]: Monad: Traverse](x: F[A]) =
    x.map(...) // error: map is ambiguous
  

  I believe the recommended workaround in Scala 3 so far was:

  def test[F[_]: Monad: Traverse](x: F[A]) =
    given Functor[F] = summon[Monad[F]]
    x.map(...)
  

  and it seems that this change enables a slightly different workaround:

  def test[F[_]: Functor: Monad: Traverse](x: F[A]) =
    x.map(...)
  

  But it's not clear to me that this is worth changing the rules over, at least compared to other rule changes (like prioritizing implicit parameters based on their position in the parameter list).

[odersky]

That's the problem: The example we got (and handled) was already very specialized. Who wants a monad and a traversable in the same function? But what's much more common is that I have the three classes as defined and I want a Functor! Seems obvious, but so far I could not do it. This PR solves the problem.

About going through the SIP process. In theory, yes. But I must admit to myself that I simply don't have the bandwidth to do this. So unless we get a jump in resources and other people going ahead with this, we have to conclude that this will likely not get fixed.

I am thinking of creating a separate branch where I do these improvements. Then the SIP committee or anybody else can pick what they think is worthwhile and turn it into a SIP.

[odersky]

I think this needs to be merged, and I will not have the bandwidth to make a SIP for this.

Are there other opinions how to proceed here?

[odersky]

@smarter It turns out that Dimi's attempted hylolib port had lots of problems with ambiguities, and they all went away with #19395, which includes this PR as the only change to given resolution. So I think the triangle problem is quite common in "natural" code, and this is a simple fix, which so far broke nothing.

I suggest we roll this in for 3.5 and run the open community build to see whether there are any breakages that can't be fixed.

[smarter]

It turns out that Dimi's attempted hylolib port had lots of problems with ambiguities, and they all went away with https://github.com/lampepfl/dotty/pull/19395, which includes this PR as the only change to given resolution.

I assume https://github.com/lampepfl/dotty/pull/19395 will have a SIP? If the change to given resolution passes the open community build then it's probably uncontroversial enough that it could be a line item in the larger SIP of #19395. Alternatively, maybe @kyouko-taiga would be interested in making a SIP just for the given resolution changes motivated by examples from hylolib?

[odersky]

Sorry, I misread. Yes, of course #19395 will be a SIP. I'd be OK with this fix being a line item, except that I think it would be important to roll it in quickly before there is more code that could break. Type inference changes are always tricky, as we know. So I think it's better to treat it as an independent first step.

I believe #19395 would take a lot more time to be properly discussed.

[kyouko-taiga]

I'm happy to work on a SIP draft for https://github.com/lampepfl/dotty/pull/19395 but it should be clear that I am not the designer of the proposed changes. I merely presented Martin with a list of complaints and let him do the hard work.

Maybe something that could make more sense is for me to write a sort of blog post justifying why one would like to write code in the style of hylo-lib.

[bishabosha]

I'm happy to work on a SIP draft for #19395 but it should be clear that I am not the designer of the proposed changes. I merely presented Martin with a list of complaints and let him do the hard work.

You can co-sign with Martin - as you say you have a lot to say in the motivation section

[odersky]

@WojciechMazur We are considering merging this change for 3.5. Can we run an open CB to see what the damage would be? In the small CB it only caused one regression in a Shapeless 3 test, which arguably detected an error in the test.

[WojciechMazur]

I've run the Open CB for this project 2 weeks ago and there were some failures:

Project	Version	Build URL	Notes
7mind/izumi	1.2.7	Open CB logs	No given instance of
apache/pekko-connectors	1.0.2	Open CB logs	No given instance of
typelevel/kittens	3.3.0	Open CB logs	No given instance of
j5ik2o/akka-persistence-s3	1.2.177	Open CB logs	no member new scala.beans.BeanProperty
kalin-rudnicki/harness	4.1.4 -> 4.1.7	Open CB logs	Recursion limit exceeded.
dfianthdl/dfiant	0.3.7	Open CB logs	Recursion limit exceeded
rssh/dotty-cps-async	0.9.19 -> 0.9.21	Open CB logs

I've started a new build using the rebased version of this PR to confirm the results

[odersky]

Ah yes, thanks for reminding me. I think the results will be similar now.

On Wed, Apr 17, 2024 at 2:39 PM Wojciech Mazur @.***> wrote:

I've run the Open CB for this project 2 weeks ago and there were some failures: Project Version Build URL Notes 7mind/izumi 1.2.7 Open CB logs https://github.com/VirtusLab/community-build3/actions/runs/8546672779/job/23422651877 No given instance of apache/pekko-connectors 1.0.2 Open CB logs https://github.com/VirtusLab/community-build3/actions/runs/8546672779/job/23417510904 No given instance of typelevel/kittens 3.3.0 Open CB logs https://github.com/VirtusLab/community-build3/actions/runs/8546672779/job/23418739535 No given instance of j5ik2o/akka-persistence-s3 1.2.177 Open CB logs https://github.com/VirtusLab/community-build3/actions/runs/8546672779/job/23417522349 no member new scala.beans.BeanProperty kalin-rudnicki/harness 4.1.4 -> 4.1.7 Open CB logs https://github.com/VirtusLab/community-build3/actions/runs/8552762608/job/23434682090 Recursion limit exceeded. dfianthdl/dfiant 0.3.7 Open CB logs https://github.com/VirtusLab/community-build3/actions/runs/8546672779/job/23418552357 Recursion limit exceeded rssh/dotty-cps-async 0.9.19 -> 0.9.21 Open CB logs https://github.com/VirtusLab/community-build3/actions/runs/8546672779/job/23417531690

I've started a new build using the rebased version of this PR to confirm the results

— Reply to this email directly, view it on GitHub https://github.com/scala/scala3/pull/19300#issuecomment-2061166119, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAGCKVROGJXZ3ZAPQ7GRJC3Y5ZUQNAVCNFSM6AAAAABA33VSW2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDANRRGE3DMMJRHE . You are receiving this because you authored the thread.Message ID: @.***>

--

Martin Odersky Professor, Programming Methods Group (LAMP) Faculty IC, EPFL Station 14, Lausanne, Switzerland

[odersky]

To give more time to the failing projects, we now delay the rollout of the new scheme:

3.5: old scheme but warn if there will be changes in the future 3.6-migration: new scheme, warn if prioritization has changed 3.6: new scheme, no warning

[WojciechMazur]

OpenCB run after the rebase has quite a different set of projects that fail. All of previously failing projects, with exception of rssh/dotty-cps-async, now do pass the compilation, however, there is a set of projects that started to fail, mostly due to ambiguouse implicit resolution

Project	Version	Build URL	Notes
com-lihaoyi/upickle	3.2.0	Open CB logs	Ambiguous given instances:
dapperware/dappermongo	0.0.1	Open CB logs	conversions cannot be applied because they are ambiguous
epfl-lara/lisa	HEAD	Open CB logs	No given instance of type
lichess-org/lila	HEAD	Open CB logs	Ambiguous given instances:
reactivemongo/reactivemongo-bson	1.1.0-RC12	Open CB logs	No implicit found for
scala-tsi/scala-tsi	0.8.3	Open CB logs	Ambiguous given instances
typelevel/shapeless-3	3.4.1	Open CB logs	not a member (...) but could be made available as an extension method
softwaremill/tapir	1.10.0 -> 1.10.4	Open CB logs	Ambiguous given instances

---

[odersky]

Was that after d10019d was added or before?

[WojciechMazur]

Before, it was based on https://github.com/scala/scala3/pull/19300/commits/7d99aeffe1a6161f934e58f5e8888331036417d9

I might try to check how the delay affects it locally later on the failing projects

[odersky]

@WojciechMazur I think I told you to test the wrong PR here. Sorry! Instead of #20277 it should have been this PR to be tested in the open CB. #20277 already delayed the roll-out until after 3.5, so projects that did not have -source future set would have compiled OK anyway. Can we try again, just to be sure before we merge?

[WojciechMazur]

Sure, I've started the build. I should have results tomorrow morning

[WojciechMazur]

We've found only 1 regression in reactivemongo/reactivemongo, but I think we've already fixed it 2 weeks ago - https://github.com/scala/scala3/issues/18555#issuecomment-2045426048. It's exactly the same and I was able to reproduce it locally. Probably this PR is not based on a commit that introduced a fix.

[odersky]

@WojciechMazur Unfortunately I got the wrong PR again (I forgot to force push the local changes). It was still the version that enabled the change only for 3.6. So, can we run this again, please? I rebased on current main, so the reactive mongo regression should no longer be an issue. And I made sure it's enabled for 3.5.

[WojciechMazur]

Sure, I've started the build. We should have results this evening/tomorrows morning

[WojciechMazur]

It seems like currently there are 4 projects failing due to this PR

Project	Version	Build URL	Notes
reactivemongo/reactivemongo-bson	1.1.0-RC12	Open CB logs	No implicit found for
dapperware/dappermongo	0.0.1	Open CB logs	Implicit conversion cannot be applied, ambigious BsonWriter[Map[X, Y]] instances
lichess-org/lila	HEAD	Open CB logs	Ambigious given instances for BsonWriter[Map[String, V]]
typelevel/shapeless-3	3.4.1	Open CB logs	extension not applied

However, these projects only fail to compile under -source:3.5-migration (default mode of compilation used in OpenCB) - if we remove the flag all of them are able to compile. The first 3 projects are related to the same issue in the reactivemongo/reactivemongo-bson I've tried to reproduce the case for lichess-org/lila:

//> using dep "org.reactivemongo::reactivemongo-bson-api:1.1.0-RC12"
//> using options -source:3.5-migration
import reactivemongo.api.bson.*

def stringMapHandler[V](using writer: BSONWriter[Map[String, V]]): BSONHandler[Map[String, V]] = ???
def typedMapHandler[K, V: BSONHandler] = stringMapHandler[V]

yields:

-- [E172] Type Error: /Users/wmazur/projects/sandbox/repro.test.scala:6:60 -----
6 |def typedMapHandler[K, V: BSONHandler] = stringMapHandler[V]
  |                                                            ^
  |Ambiguous given instances: both given instance mapWriter in trait BSONWriterInstances and given instance collectionWriter in trait BSONWriterInstances match type reactivemongo.api.bson.BSONWriter[Map[String, V]] of parameter writer of method stringMapHandler

I've tried to reproduce the bson api

package bson 

trait BSONWriter[T]
trait BSONDocumentWriter[T] extends BSONWriter[T]
object BSONWriter extends BSONWriterInstances

trait BSONHandler[T] extends BSONWriter[T]

private[bson] trait BSONWriterInstances {
  given mapWriter[V](using BSONWriter[V]): BSONDocumentWriter[Map[String, V]] = bson.mapWriter[V]
  export bson.collectionWriter
}

final class ¬[A, B]
object ¬ {
  implicit def defaultEvidence[A, B]: ¬[A, B] = new ¬[A, B]()
  @annotation.implicitAmbiguous("Could not prove type ${A} is not (¬) ${A}")
  implicit def ambiguousEvidence1[A]: ¬[A, A] = null
  implicit def ambiguousEvidence2[A]: ¬[A, A] = null
}

private[bson] trait DefaultBSONHandlers extends LowPriorityHandlers
private[bson] trait LowPriorityHandlers{
  given collectionWriter[T, Repr <: Iterable[T]](using BSONWriter[T], Repr ¬ Option[T]): BSONWriter[Repr] = ???
  private[bson] def mapWriter[V](implicit valueWriter: BSONWriter[V]): BSONDocumentWriter[Map[String, V]] = ???
}

// --- 
package object bson extends DefaultBSONHandlers

but then we get expected warning instead of error:

-- Warning: /Users/wmazur/projects/sandbox/lila.repro.scala:7:60 ---------------
7 |def typedMapHandler[K, V: BSONHandler] = stringMapHandler[V]
  |                                                            ^
  |Change in given search preference for bson.BSONWriter[Map[String, V]] between alternatives (bson.BSONWriter.mapWriter :
  |  [V²](using x$1: bson.BSONWriter[V²]): bson.BSONDocumentWriter[Map[String, V²]]
  |  ) and (bson.BSONWriter.collectionWriter :
  |  [T, Repr <: Iterable[T]]
  |    (using x$1: bson.BSONWriter[T], x$2: Repr ¬ Option[T]):
  |      bson.BSONWriter[Repr]
  |)
  |Previous choice: the first alternative
  |New choice     : none - it's ambiguous
  |
  |where:    V  is a type in method typedMapHandler
  |          V² is a type variable

[odersky]

Thanks for the analysis!

However, these projects only fail to compile under -source:3.5-migration (default mode of compilation used in OpenCB) - if we remove the flag all of them are able to compile.

If we remove the flag, which source version is used?

[WojciechMazur]

If we remove the flag, which source version is used?

None of these projects use explicit -source flag, so I assume that in case of absence of the -source flag, compiler should work as if the flag -source:3.N was used, where N is current binary minor version, so 3.5. However, in case of lila reproducer if we explicitly pass the -source:3.5 it still fails to compile. It can compile with -source:3.4 and lower though.

[lenguyenthanh]

It seems like currently there are 4 projects failing due to this PR Project Version Build URL Notes reactivemongo/reactivemongo-bson 1.1.0-RC12 Open CB logs No implicit found for dapperware/dappermongo 0.0.1 Open CB logs Implicit conversion cannot be applied, ambigious BsonWriter[Map[X, Y]] instances lichess-org/lila HEAD Open CB logs Ambigious given instances for BsonWriter[Map[String, V]] typelevel/shapeless-3 3.4.1 Open CB logs extension not applied

However, these projects only fail to compile under -source:3.5-migration (default mode of compilation used in OpenCB) - if we remove the flag all of them are able to compile. The first 3 projects are related to the same issue in the reactivemongo/reactivemongo-bson I've tried to reproduce the case for lichess-org/lila:

//> using dep "org.reactivemongo::reactivemongo-bson-api:1.1.0-RC12"
//> using options -source:3.5-migration
import reactivemongo.api.bson.*

def stringMapHandler[V](using writer: BSONWriter[Map[String, V]]): BSONHandler[Map[String, V]] = ???
def typedMapHandler[K, V: BSONHandler] = stringMapHandler[V]

yields:

-- [E172] Type Error: /Users/wmazur/projects/sandbox/repro.test.scala:6:60 -----
6 |def typedMapHandler[K, V: BSONHandler] = stringMapHandler[V]
  |                                                            ^
  |Ambiguous given instances: both given instance mapWriter in trait BSONWriterInstances and given instance collectionWriter in trait BSONWriterInstances match type reactivemongo.api.bson.BSONWriter[Map[String, V]] of parameter writer of method stringMapHandler

I've tried to reproduce the bson api

but then we get expected warning instead of error:

-- Warning: /Users/wmazur/projects/sandbox/lila.repro.scala:7:60 ---------------
7 |def typedMapHandler[K, V: BSONHandler] = stringMapHandler[V]
  |                                                            ^
  |Change in given search preference for bson.BSONWriter[Map[String, V]] between alternatives (bson.BSONWriter.mapWriter :
  |  [V²](using x$1: bson.BSONWriter[V²]): bson.BSONDocumentWriter[Map[String, V²]]
  |  ) and (bson.BSONWriter.collectionWriter :
  |  [T, Repr <: Iterable[T]]
  |    (using x$1: bson.BSONWriter[T], x$2: Repr ¬ Option[T]):
  |      bson.BSONWriter[Repr]
  |)
  |Previous choice: the first alternative
  |New choice     : none - it's ambiguous
  |
  |where:    V  is a type in method typedMapHandler
  |          V² is a type variable

Hi @WojciechMazur, I'm again with migrating lila to 3.5.0-RC2 task. Do you have any suggestion of how to resolve those warnings/errors? It seems We can fix it by removing typedMapHandler but it's bit annoying as We use it widely. Also I would love to know what is the best practice to design scala library/application with implicits?

[soronpo]

In my project I'm getting now hundreds of warnings due to this PR in 3.5.0-RC2 (it does compile successfully with -source:3.6). I don't understand why this hasn't gone through a SIP.

[WojciechMazur]

Do you have any suggestion of how to resolve those warnings/errors? It seems We can fix it by removing typedMapHandler but it's bit annoying as We use it widely

So in 3.5.0 you're now only getting warnings about changes to be introduced in 3.6. The project compiles just fine as long as you don't use -source:future or fatal-warnings. (yes, I know it's not idea to ignore warnings). I cannot tell exactly how to migrate yet, without getting into the project and making some reproductions, especially as it's right now involving in some cases at least 2 lichess projects and 1 external dependency (reactive mongo). There's also the possibility of having bugs. We'll need to check it out and we'll try give some tips on the migration.

[lenguyenthanh]

So in 3.5.0 you're now only getting warnings about changes to be introduced in 3.6. The project compiles just fine as long as you don't use -source:future or fatal-warnings. (yes, I know it's not idea to ignore warnings).

I understand that It'll be fine in 3.5 but the warning is hard to ignore. I reduced some warnings by removing implicit ambiguity but still a lot.

I cannot tell exactly how to migrate yet, without getting into the project and making some reproductions, especially as it's right now involving in some cases at least 2 lichess projects and 1 external dependency (reactive mongo). There's also the possibility of having bugs. We'll need to check it out and we'll try give some tips on the migration.

this would be great really appreciated ❤️ . I'll investigate more in the mean time. Happy to collaborate if needed.

[soronpo]

I reduced some warnings by removing implicit ambiguity but still a lot.

I really think there are a lot of false-positives. I haven't got the time to minimize my warnings yet, but it seems weird there are so many.