Dotty style downwards comparisons for implicit search and overloading resolution #6037

milessabin · 2017-08-13T13:36:40Z

This is a backport of scala/scala3@8954026 to scalac. As in the Dotty implementation the specificity comparison is as-if all contravariant positions in type constructors were covariant. The feature is enabled by specifying -Xsource:3.0.

Initially this broke test/files/run/t2030.scala in exactly the same way as in Dotty as reported by @smarter here. Since then the landing of the new collections has fixed this.

This fixes scala/bug#2509. It also aligns with the contravariant behaviour hoped for in scala/bug#7768, although it differs on the covariant behaviour, which is unchanged. I think that's a reasonable outcome and that scala/bug#7768 can be declared as fixed.

smarter · 2017-08-13T14:51:35Z

Nice!

The new specificity behaviour is behind flag -Ydotty-specificity.

I think -Xsource:3.0 was proposed for this sort of things: scala/scala-dev#374

som-snytt · 2017-08-13T17:31:05Z

src/compiler/scala/tools/nsc/settings/ScalaSettings.scala

  val YdisableFlatCpCaching  = BooleanSetting    ("-YdisableFlatCpCaching", "Do not cache flat classpath representation of classpath elements from jars across compiler instances.")
  val YpartialUnification = BooleanSetting ("-Ypartial-unification", "Enable partial unification in type constructor inference")
  val Yvirtpatmat     = BooleanSetting    ("-Yvirtpatmat", "Enable pattern matcher virtualization")
+  val YdottySpecificity = BooleanSetting ("-Ydotty-specificity", "Enable Dotty compatible rules for overload selection by specifity")


selection by specifity")

That's how I usually pronounce it.

Curs mi speling ...

retronym

I'd also like to see how this would be described in the spec, assuming it were to become default behaviour. Sometimes these concepts are easier to describe in comments in the implenentation than they are in the more limited vocabulary of the spec.

retronym · 2017-08-13T23:34:31Z

src/compiler/scala/tools/nsc/typechecker/Infer.scala

+                          val flippedParams = sym.rawInfo.typeParams.map { param =>
+                            val flippedFlags = if(param.isContravariant) (param.flags&(~CONTRAVARIANT))|COVARIANT else param.flags
+                            flippedClassSym.newTypeParameter(param.name.toTypeName, param.pos, flippedFlags) setInfo param.info
+                          }


param.info might refer to the original type parameters, so more substitution is needed. Cloning the class upfront takes care of all the rewiring.

scala> class C[-A <: C[A]] defined class C scala> val CClass = symbolOf[C[_]] CClass: $r.intp.global.TypeSymbol = class C scala> val CClass_clone = CClass.cloneSymbol(CClass.owner) CClass_clone: CClass.TypeOfClonedSymbol = class C scala> CClass_clone.rawInfo.typeParams.foreach(sym => if (sym.isContravariant) sym.resetFlag(Flag.CONTRAVARIANT).setFlag(Flag.COVARIANT)) scala> CClass_clone.defString res3: String = class C[+A <: C[A]] extends AnyRef scala> {settings.uniqid.value = true; println(CClass.defString); println(CClass_clone.defString); settings.uniqid.value = false} class C#132392[-A#132393 <: C#132392[A#132393]] extends AnyRef#1932 class C#145639[+A#145640 <: C#132392[A#145640]] extends AnyRef#1932

Thanks. That simplifies things quite a bit.

retronym · 2017-08-13T23:42:45Z

src/compiler/scala/tools/nsc/typechecker/Infer.scala

+                    val flippedSym =
+                      subst.get(sym) match {
+                        case None =>
+                          val flippedClassSym = sym.owner.newClassSymbol(sym.name.toTypeName, sym.pos, sym.flags)


Surely the new class symbols created by flip will always be treated as unrelated by the subsequent <:<? Maybe that gives the expected result for the test cases.

Dotty's implementation appears to make a type alias instead.

class C[-A] ... type C'[+A] = C[A] // synthetic (ill-varying) type alias

I don't think that's quite what's going on in Dotty's implementation. In the flip in Dotty the TypeMap traversal appears to traverse through to the type members which correspond to the type params of the TypeRef in the scala implementation. These type members then have their variance individually flipped, via a type alias, as you say. But I think the mechanism in scalac has to be different ... we have to work at the TypeRef/type params level.

On your first point, yes you're right that new symbols will be unrelated by <:< except in the trivial case where the outer type constructor is the same in both cases (here the subst map ensures that the same flipped symbol is used). I'm fairly confident that my implementation here matches the one in Dotty, but it's possible that the Dotty implementation gets this wrong as well.

I think however, that in cases where the outer type constructor differs, we will always want to say that neither is specific as the other. The following is the main problem case (included in the latest commit, Dotty agrees with the implementation here),

trait Z[-T] trait Quux[-T] extends Z[T] class A class B extends A

Given the above, what is the relative specificity of Quux[B] and Z[A]? Both Dotty and this implementation say that neither is as specific as the other even though Z[B] is as specific as Z[A] and Quux[B] is a subtype of Z[B]. @smarter what are your thoughts on this?

Intuitively I would expect Quux[B] to be more specific than Z[A] for the reasons you gave. The fact that it doesn't in dotty seems like an oversight to me /cc @odersky .

@retronym is there any way of preserving the subtype relationships of the cloned outer ClassSymbols?

I've opened scala/scala3#2974, you might want to weight in on whether you find the top-level-only-flipping semantics sensible or not.

retronym · 2017-08-13T23:48:54Z

src/compiler/scala/tools/nsc/typechecker/Infer.scala

-          case _                         => existentialAbstraction(undef1, tpe1) <:< existentialAbstraction(undef2, tpe2)
+          case _                         =>
+
+            if (settings.YdottySpecificity) {


This approach looks somewhat expensive, but we could cache the flipped version of each contravariant class symbol by spending a few fields in ClassSymbol.

Yes, this also helps.

retronym · 2017-08-13T23:49:34Z

test/junit/scala/tools/nsc/typechecker/Infer.scala

+trait Z[-T]
+
+@RunWith(classOf[JUnit4])
+class InferencerTests extends BytecodeTesting {


👍 for unit tests!

smarter · 2017-08-15T16:07:40Z

Could you try making Ordering contravariant on top of this PR ? (cf http://github.com/scala/bug/issues/7179, this might require using @unsafeVariance to deal with Java superclasses)

milessabin · 2017-08-22T18:08:46Z

@smarter aside from the inevitable issues with max and min it looks fine.

milessabin · 2017-08-22T20:56:45Z

Quick and dirty PoC of a contravariant (Partial)Ordering and Equiv here: milessabin@9ca6be8.

I made max and min extension methods of Ordering[T] to avoid the variance issue and didn't bother to handle the Float and Double specializations.

It compiles and partests successfully.

smarter · 2017-08-22T21:05:19Z

I made max and min extension methods of Ordering[T] to avoid the variance issue

Would this work?

def max[U <: T](x: U, y: U): U = if (gteq(x, y)) x else y

milessabin · 2017-08-23T07:25:18Z

Would this work?

Yes, but it'd be a bit more work. The nested Ops class interferes.

milessabin · 2017-08-25T10:13:02Z

Latest commit fixes the problem that @retronym pointed out by normalizing the LHS to the type constructor of the RHS via baseType. My reading of the discussion motivating this change is that people's expectations are that specificity runs in the same direction as extension rather than subtyping, so the use of base types at the outer level seems appropriate.

adriaanm · 2017-09-27T16:06:37Z

I'd prefer to have this target 2.13, as it's about exploring dotty compatibility.

milessabin · 2017-09-28T06:18:45Z

I'm fine with this going into 2.13.x. Would you like me to change -Ydotty-specificity to -Xsource:2.13?

The Dotty bug corresponding to the issue that @retronym raised has been fixed with same test case as included in this PR so we can be reasonably confident that the semantics match: scala/scala3#2974.

adriaanm · 2017-09-28T16:37:42Z

Thanks, yes, let's standardize on -Xsource. Regarding the target of 2.13 v 3.0, we can tweak once it's clear what the impact on user code is.

ctongfei · 2017-10-08T15:29:13Z

This is great :-) Cats can make all these typeclasses contravariant now!

milessabin · 2017-10-17T14:56:41Z

Rebased against 2.13.x ...

@adriaanm where does this leave -Xsource:2.13 ... should I just make this unconditional? Or do we need a -Xsource:dotty? Or something else?

smarter · 2017-10-17T15:02:42Z

I would vote for making this unconditional so that it can influence the design of the collection-strawman

milessabin · 2017-10-18T14:31:24Z

I would be very happy to make this unconditional ... @adriaanm?

adriaanm · 2017-10-23T23:30:37Z

More work is needed before we can get to deciding whether this can go in and which flag (if any) it should be gated by. In short, 1) a correct implementation and 2) a detailed explanation of its pros & cons, including how it affects existing code bases and future ones (the new collections).

First, the code has evolved in dotty since the commit you've ported: https://github.com/lampepfl/dotty/blob/master/compiler/src/dotty/tools/dotc/typer/Applications.scala#L1138. Also, your port of the original commit is not obviously correct to me, and it didn't carry over the nice comment that accompanies the dotty implementation. Can you explain your implementation strategy and why it's different from dotty's?

The higher-level concern is that this illustrates this is evolving in dotty. Are we ready to call the latest approach ready for production? We also need to evaluate how it affects existing code bases. If this helps the new collections design -- great! That's a good motivator and test bed, but it's not a sufficient condition.

smarter · 2017-10-24T21:55:59Z

The higher-level concern is that this illustrates this is evolving in dotty.

The only change to the behavior of dotty here was a fix for scala/scala3#2974 and Miles updated his PR to match the agreed-upon behavior. No other changes in this area are planned, though of course we need to see how well this works in practice. I think getting this PR in scalac and seeing what happens on the community build would be very helpful for that.

adriaanm · 2017-10-25T19:59:11Z

Ok, thanks for the background. I'm all for experimentation here, and alignment with dotty, but this is a tricky part of the language and I would like to see a deep dive in how this is implemented and how it will impact existing code.

I still don't understand how the code I linked to and the code in this PR relate. What does FunctionOf do in dotty, and why doesn't it appear here -- is it a cheaper way to flip variance? It would be nice to avoid the symbol cloning (cloning without substitution makes me suspicious, without looking too deeply). Should we do the comparison before or after existential abstraction?

smarter · 2017-10-25T22:42:41Z

I still don't understand how the code I linked to and the code in this PR relate. What does FunctionOf do in dotty, and why doesn't it appear here -- is it a cheaper way to flip variance?

Yeah basically you replace all type arguments Foo that appear in contravariant positions by a function type Foo => () to flip their variance, it's kind of a hack :).

milessabin · 2017-10-26T08:11:13Z

The impact will be similar, though not quite as significant, as partial unification ... people have been working around the old specificity behaviour wrt to contravariant type classes in a variety of ad hoc and more or less unsatisfactory ways for years. This change in Dotty and Scala gives people the behaviour they expected all along and makes the workarounds unnecessary.

Existing code will break, as was the case with partial unification, but I think that's a price worth paying, and I'm fairly confident that most people working with contravariant type classes would agree.

xeno-by · 2018-07-01T19:24:18Z

Since we now have a process to discuss changes that narrow the gap between Scala 2 and Scala 3, I suggest we follow this process with this pull request as well. Let's have this change on the agenda of one of the next SIP meetings?

milessabin · 2018-07-26T15:36:58Z

Rebased, fixed tests broken by 2.13.x deprecations.

More importantly, changed to match the current Dotty semantics which are now to flip variances throughout the type, not just at the top level.

@smarter, I'd welcome your feedback on this.

@adriaanm do you want this behind an -Xsource flag? In which case, what version?

milessabin · 2018-07-26T16:56:57Z

Hey ho ... this should be OK after squashing ...

milessabin · 2018-07-26T17:03:33Z

Squashed.

adriaanm · 2018-08-03T09:16:56Z

My current position is that this should go under -Xsource:3.0. It can then be discussed in a SIP meeting on whether we want this on by default in 2.14. I still think this is a bit of a hack, and the interaction with type inference needs to be fleshed out. See e.g. scala/scala3#4465.

It's too late for this to influence the collections, so I don't think it's urgent from a 2.13 release planning perspective.

milessabin · 2018-08-03T19:07:00Z

If you're happy to merge it with the -Xsource:3.0 logic then I should be able to find time for it next week.

adriaanm · 2018-08-03T20:38:05Z

👌

…

On Fri, Aug 3, 2018 at 21:07 Miles Sabin ***@***.***> wrote: If you're happy to merge it with the -Xsource:3.0 logic then I should be able to find time for it next week. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#6037 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAFjyxPb1Rmu6LEd6Kheov5q-Nnq4vUuks5uNJ9VgaJpZM4O1sJH> .

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. Fixes scala/bug#2509. Fixes scala/bug#7768.

milessabin · 2018-08-06T11:37:51Z

@adriaanm done. Merge when you're happy :-)

I've taken out the spec change for now because having the language conditionalized on the language version was a bit awkward. We should deal with that as part of the SIP for the feature.

SethTisue · 2018-08-08T20:11:32Z

test/files/run/t7768.scala is failing on Windows. at e.g. https://scala-ci.typesafe.com/view/scala-2.13.x/job/scala-2.13.x-integrate-windows/658/consoleFull we see:

 Inv[A] Inv[B] Inv[C] Inv[D] Inv[E]
-Con[A] Con[A] Con[C] Con[C] Con[E]
-Cov[E] Cov[E] Cov[E] Cov[E] Cov[E]
+java.lang.NoClassDefFoundError: Con
...
+Caused by: java.lang.ClassNotFoundException: Con
...

@milessabin any idea why that might be...?

adriaanm · 2018-08-08T20:13:12Z

🤣 Con is a reserved file name on windows 😱

SethTisue · 2018-08-08T20:13:18Z

oh LOL, it must be because con is a reserved name on Windows filesystems?

SethTisue · 2018-08-08T20:13:22Z

jinx

CON you call something CON on Windows? No, you CONnot. references scala#6037

SethTisue · 2018-08-08T20:28:20Z

this leaves me puzzled how Shapeless is able to call something Aux, which is also a dirty word in Redmond.

but, a glance at the source shows that Shapeless's Aux is a type alias, and therefore doesn't produce a .class file. This seems in keeping with our suspicions that @milessabin doesn't even exist at runtime.

PR with fix: #7024

milessabin · 2018-08-08T21:10:46Z

Oh. My. Goodness.

djspiewak · 2018-08-08T21:30:30Z

Narrator: There comes a moment in everyone's life when they must choose what kind of a person they're going to be. A moment where steel is tempered in the unyielding fires of decision. A moment where all the churning demons of ten thousand unanswered slights rage as one and demand retribution.

In that moment, our hero knew: he wasn't a Windows user.

scala-jenkins added this to the 2.12.4 milestone Aug 13, 2017

som-snytt reviewed Aug 13, 2017

View reviewed changes

retronym previously requested changes Aug 13, 2017

View reviewed changes

retronym reviewed Aug 13, 2017

View reviewed changes

smarter mentioned this pull request Aug 14, 2017

Specificity in contravariant implicit resolution scala/scala3#2974

Closed

adriaanm modified the milestones: 2.12.4, 2.13.0-M3 Sep 27, 2017

milessabin changed the base branch from 2.12.x to 2.13.x October 17, 2017 14:55

milessabin force-pushed the topic/si-2509 branch from a93b22a to f1230da Compare October 17, 2017 15:25

milessabin mentioned this pull request Oct 18, 2017

Remove language fragmentation -Y flags. Only -Xsource allowed henceforth. scala/scala-dev#430

Closed

milessabin force-pushed the topic/si-2509 branch from bb98a06 to 3474809 Compare July 26, 2018 15:32

milessabin force-pushed the topic/si-2509 branch from 3474809 to 856f30d Compare July 26, 2018 17:03

milessabin force-pushed the topic/si-2509 branch from 856f30d to f4a8bf8 Compare August 6, 2018 11:33

adriaanm approved these changes Aug 6, 2018

View reviewed changes

adriaanm merged commit cdd6f80 into scala:2.13.x Aug 6, 2018

ctongfei mentioned this pull request Aug 8, 2018

Making Eq/Order/Hash contravariant? typelevel/cats#2370

Closed

SethTisue added a commit to SethTisue/scala that referenced this pull request Aug 8, 2018

fix t7668 test case on Windows

fe20d00

CON you call something CON on Windows? No, you CONnot. references scala#6037

SethTisue mentioned this pull request Aug 8, 2018

fix t7668 test case on Windows #7024

Merged

SethTisue mentioned this pull request Jun 16, 2019

Contravariance prevents proper type derivation in Scala 2.13.0 scala/bug#11570

Open

smarter mentioned this pull request Sep 11, 2019

Resource should be covariant typelevel/cats-effect#617

Closed

smarter mentioned this pull request Aug 1, 2020

Issues with Nothing Instances zio/zio-prelude#113

Open

som-snytt mentioned this pull request Mar 18, 2021

"Ambiguous implicit values" error caused by a mix of -Xsource:3, an explicit (not wildcard) import and a evicted/transitive(?) dependency scala/bug#12350

Closed

milessabin mentioned this pull request Apr 16, 2021

Invariant implicit definition is not picked up for its covariant supertype implicit parameter scala/bug#12231

Open

lrytz mentioned this pull request Aug 2, 2021

-Xsource:3 on scala 2.13.6 breaks type inference for e.g. scala.js union scala/bug#12437

Closed

Dotty style downwards comparisons for implicit search and overloading resolution #6037

Dotty style downwards comparisons for implicit search and overloading resolution #6037

Uh oh!

Conversation

milessabin commented Aug 13, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

smarter commented Aug 13, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

retronym left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

smarter commented Aug 15, 2017

Uh oh!

milessabin commented Aug 22, 2017

Uh oh!

milessabin commented Aug 22, 2017

Uh oh!

smarter commented Aug 22, 2017

Uh oh!

milessabin commented Aug 23, 2017

Uh oh!

milessabin commented Aug 25, 2017

Uh oh!

adriaanm commented Sep 27, 2017

Uh oh!

milessabin commented Sep 28, 2017

Uh oh!

adriaanm commented Sep 28, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ctongfei commented Oct 8, 2017

Uh oh!

milessabin commented Oct 17, 2017

Uh oh!

smarter commented Oct 17, 2017

Uh oh!

milessabin commented Oct 18, 2017

Uh oh!

adriaanm commented Oct 23, 2017

Uh oh!

smarter commented Oct 24, 2017

Uh oh!

adriaanm commented Oct 25, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

smarter commented Oct 25, 2017

Uh oh!

milessabin commented Oct 26, 2017

Uh oh!

xeno-by commented Jul 1, 2018

Uh oh!

milessabin commented Jul 26, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

milessabin commented Jul 26, 2018

milessabin commented Aug 13, 2017 •

edited

Loading

adriaanm commented Sep 28, 2017 •

edited

Loading

adriaanm commented Oct 25, 2017 •

edited

Loading

milessabin commented Jul 26, 2018 •

edited

Loading