Dotty: Non-definition prefix is in implicit scope, unlike Scala 2

[neko-kai]

Minimized code

trait X {
  trait S
}

class Xa(val internal: X) {
  type S = internal.S
  def s: S = new S{}

  implicit class XS(s: S) {
    def printX: Unit = println(s)
  }
}

object Xa extends Xa(new X{})

object App extends App {
  Xa.s.printX
}

Output

    Xa$$anon$1@55924a6a

The above, unexpectedly, compiles and works with Dotty[1], but not with Scala 2.13[2]

Expectation

It seems like Xa is included in the implicit scope of type Xa.internal.S where Xa is not a _direct prefix_ of S, but is instead only a prefix of its prefix, whereas Scala 2 does not include prefixes of prefixes in implicit scope, but only non-prefix parts of the direct prefix.

[smarter]

Seems like a bug in scalac? The spec says:

The implicit scope of a type T consists of all companion modules of classes that are associated with the implicit parameter's type. Here, we say a class C is associated with a type T if it is a base class of some part of T.

And I don't see any notion of "direct prefix" in the definition of "part" below.

[neko-kai]

@smarter
Yes, the spec does not specify a stop to recursion, but I think the behavior in scalac is deliberate - not limiting the prefix allows completely arbitrary remapping of implicit scopes for any non-top-level identifier purely by re-exporting, I imagine this would hurt the ability to cache implicit scopes because any given implicit scope is determined by the syntactic reference, not by the unique type symbol, if any.

Example: Any type in any object can be attached arbitrary implicits to:

object X {
  final class S
}

object Xa {
  val internal = X
  def s: internal.S = new internal.S

  implicit class XS(s: internal.S) {
    def printX: Unit = println(s)
  }
}

object App extends App {
  val a: Xa.internal.S = new X.S
  a.printX

  // same type, aliased differently
  val b: X.S = new X.S
  b.printX // not a member
}

If this is allowed and declared a feature, it would also be inconsistent - re-exporting can remap types in objects, but not types in packages, because you can't assign a package to a val: val internal = java.lang

/cc @SethTisue

[smarter]

not limiting the prefix allows completely arbitrary remapping of implicit scopes for any non-top-level identifier purely by re-exporting

I'm not sure I understand what you mean by "arbitrary remapping", but in your example, withval internal = X, the type of internal is X.type, so when looking up implicits for internal.S we should find all the implicits defined in X too, and when looking up implicits for X.S, if an implicit of type internal.S is in scope, it will be considered applicable.

[neko-kai]

@smarter
I edited the post to show it clearlier - in Dotty currently you can alias the exact same type X.S from multiple prefixes and the implicit scope will be different for differently aliased values, despite the type being exactly the same (but only IFF the prefix of S is an object, not a package):

  // type X.S ascripted as `Xa.internal.S`
  val a: Xa.internal.S = new X.S
  a.printX // has extension method

  // exact same type X.S, aliased differently
  val b: X.S = new X.S
  b.printX // not a member

https://scastie.scala-lang.org/C4YZxjeuQpGi4yqKC4nQHg

[smarter]

yeah sure, because the parts of Xa.internal.S include Xa and internal, it can have more stuff in its implicit scope, but I don't see how that's a problem?

[smarter]

Also, scalac doesn't seem to be limited to the direct prefix either, e.g. it compiles the following:

object A {
  implicit val x: A.B.C.S = new A.B.C.S
  object B { object C { class S } }
}
object Test {
  def foo(implicit x: A.B.C.S) = x
  foo
}

[neko-kai]

@smarter
Right. I guess the difference is that scalac does not consider prefixes that aren't prefixes of the symbol _at the point of definition_. e.g. this doesn't work in scalac, but works in dotty.

object A {
  object B { object C { class S } }
}
object AX {
  final val B = A.B
  implicit val x: AX.B.C.S = new AX.B.C.S
}
object Test {
  def foo(implicit x: AX.B.C.S) = x
  foo
}

Also, note that the spec refers to type projections specifically, not to syntactic paths. If type of B is A.B.type then a projection from it is A.B.type#C.S, not AX.B.type#C.S, unless its type is B.type & A.B.type

[smarter]

And yet the following works with scalac:

object A {
  class B { object C { class S } }
}
object AX {
  object B extends A.B
  implicit val x: AX.B.C.S = new AX.B.C.S
}

object Test {
  def foo(implicit x: AX.B.C.S) = x
  foo
}

To me it just seems like scalac has some weird quirk where it loses some information related to the prefix in some situation, and not like a purposefully made choice.

Also, note that the spec refers to type projections specifically, not to syntactic paths.

I don't follow, we're interested in the parts of AX.B.C.S. That can be written as AX.B.C.type#S and the spec tells us:

if T is a type projection S#U, the parts of S as well as T itself;

So we know that AX.B.C.type is a part of that type, furthermore the spec tells us:

if T is a singleton type p.type, the parts of the type of p;

So AX.B.C is a part of that type too. From that we get all the prefixes of that type.

[neko-kai]

@smarter

object AX { object B extends A.B

This is correct because the prefix of the type AX.B.C.S is now AX.B.C, whereas with a val object AX { val B = A.B it's A.B.C.S

This rule specifically forbids vals from being part of the path, note that it doesn't say "as well as p.type itself".

if T is a singleton type p.type, the parts of the type of p;

Meaning that for object AX { val B: A.B.type = A.B the prefix of AX.B in implicit search is A, not AX.

So we know that AX.B.C.type is a part of that type, furthermore the spec tells us:

AX.B.C can't be part of that type, because the type of AX.B is A.B, the chain of projections is A.type#B.type#C.type#S. I think scalac doesn't do anything quirky here, while you say that any given type has an infinite amount of prefixes with no possible normalized path.

[smarter]

AX.B.C can't be part of that type, because the type of AX.B is A.X

No, the type of AX.B is AX.B.type.

[smarter]

From dotty's point of view, an object just desugars into a val and a class, so there's no reason to treat it differently from any other val.

[neko-kai]

@smarter

No, the type of AX.B is AX.B.type.

What is the relation between AX.B.type and A.B.type that allows this to hold?

object AX {
  val B = A.B
}

val s: AX.B.C.S = new A.B.C.S

How can it simultaneously be exactly the same and have a different path? Scalac allows only one stable path per type, that seems much more reasonable than an infinite amount of paths.

[smarter]

What is the relation between AX.B.type and A.B.type that allows this to hold?

AX.B.type =:= A.B.type, this is true in both scalac and dotty:

object A { object B }
object AX {
  val B = A.B
}
object Test {
  implicitly[A.B.type =:= AX.B.type]

  val a: A.B.type = AX.B
  val b: AX.B.type = A.B
}

[neko-kai]

That was a rhetorical question.

[smarter]

OK, then I guess I'll be closing this since it doesn't seem to be going anywhere.

Scalac allows only one stable path per type, that seems much more reasonable than an infinite amount of paths.

I don't understand what you mean by that, you can have multiple stable paths to the same value in scalac and dotty, they will all be =:= to each other, and there's no requirement that an implicit search on two different types which are =:= to each other produce the same result, since they can contain different parts.

[joroKr21]

The parts of a type 𝑇 are:
...

• if 𝑇 is a type alias, the parts of its expansion;

🤔

[odersky]

Let's discuss a bit more what to do here. Here's an example, which compiles in both Scala 2 and 3:

class A {
  class B
}

object o {
  object a extends A
  implicit def b: a.B = ???
}

object test {
  implicitly[o.a.B]
}

But if I change the definition of o.a to:

  lazy val a: A = new A()

it still compiles in Dotty but stops compiling in Scala 2. Now is looks to me that neither the object a nor the lazy val a is in the direct prefix of A#B. But written as an object it compiles anyway in both versions of Scala. So, I wonder, how is that justified?

It seems clear to me that we need to work on the spec on what exactly is the implicit scope of a type. It would be best if we could formalize this. But on the face of it, it seems the Dotty behavior
is reasonable. We need to be able to define givens for path dependent types like a.B and it looks unreasonable to require that this works only if a is an object.

[neko-kai]

@odersky

Now is looks to me that neither the object a nor the lazy val a is in the direct prefix of A#B.

The a is a direct prefix. Why? Let's forget about magicness of static objects - if object o is another template - a trait o, then object a will receive a prefix reference to this.o as a _runtime_ constructor parameter and it will change its isInstanceOf relation towards any other instance of o#a.
It is very easy therefore to judge which prefix is a "true" prefix and should be in implicit scope, and which is not – the prefix that changes the results of .isInstanceOf.

Consider that object a creates a completely new class - when declared inside the template, this new class is a member of the template and its type is path-dependent.

But

  lazy val a: A = new A()

is not path a dependent in any way. The type of A is completely unrelated to o. No path-dependency = no inclusion in implicit scope, that much is crystal clear to me and is exactly what the spec says.

Now if we mix in a trait that's actually path-dependent on the outer template, we get the addition in implicit scope (and the runtime pointer! that allows us to distinguish between members of different instances of trait o):

sealed trait InScope
lazy val a: A & InScope = new A with InScope

So, I think the implementation & the intent of the spec are correct, val and object do not behave the same way with implicit because, because they are not the same thing - as Gulliame noted above an object is just a class + val, the class is crucial here as it adds the path-dependency, while the type of val remains completely unrelated - as it is indeed unrelated by isInstanceOf

[joroKr21]

So, I wonder, how is that justified?

I guess it's this part of the spec:

if 𝑇 is a singleton type 𝑝.type, the parts of the type of 𝑝;

Which is interpreted as:

case tp: SingletonType =>
  getParts(tp.widen)

For the object a tp.widen is the type of the object's class which is still nested in o.
But for a normal value it's A which is not nested in o.

[odersky]

@joroKr21 Yes, it looks like that's the crucial phrase. But should it be like that? Here's another example where Scala 2 and 3 differ:

class A {
  class B
}

trait T
object T {
  implicit def b: AA.a.B = ???
}

object AA {
  val a = new A with T {}
}

object test {
  implicitly[AA.a.B]
}

Here. Scala 2 accepts it since the singleton type a also pulls in a base trait T and T's companion object defines an instance. By contrast Dotty rejects since there is no given in AA
itself.

So far, it seems to me that Dotty's behavior is more intuitive.

[joroKr21]

But should it be like that?

That is a good question, I think there is a case to be made for including the prefix of singleton types.

Here. Scala 2 accepts it since the singleton type a also pulls in a base trait T and T's companion object defines an instance. By contrast Dotty rejects since there is no given in AA
itself.

That is confusing to me. If anything I would expect including the prefix of singleton types to expand the implicit scope but not contract it in any way. In Scala 2 all base types' companion objects are part of the implicit scope.

[neko-kai]

@odersky

So far, it seems to me that Dotty's behavior is more intuitive.

This is very coutner-intuitive to me, I always expect all base classes of a type to be included in its implicit scope. It doesn't seem reasonable to me a for a narrower type to have less implicits in scope than a base type - it can only accumulate more implicits as it gets more specific (and acquires more parts).

[smarter]

I agree that this is confusing, I would have expected givens to come both from AA (because it's a prefix) and from A & T (because it's the underlying type of a singleton type in the prefix).

[odersky]

@smarter: Note that there's another indirection: It's not the given in T(which would be a member of AA.a so would qualify in any case), it's the given in the companion of T. That looks very roundabout to me.

[odersky]

This is very coutner-intuitive to me, I always expect all base classes of a type to be included in its implicit scope.

That's correct anyway, in all scenarios. The question is about a prefix P in P.T. Dotty says all members of P (defined or inherited) are in the implicit scope. Scala 2 says: No, members are not in the implicit scope, but all members of companion objects of base types of the widened type of P are. This looks really roundabout and counter-intuitive for me. It sort of works for objects in prefixes since the widened type of an object is the module class, and the module class is its own companion. So in this special case it matches our intuitions. But the special case generalizes only in Dotty in a way I would find natural.

It doesn't seem reasonable to me a for a narrower type to have less implicits in scope than a base type - it can only accumulate more implicits as it gets more specific (and acquires more parts).

I agree that's a good principle to uphold. But I think it does hold.

[odersky]

That is confusing to me. If anything I would expect including the prefix of singleton types to expand the implicit scope but not contract it in any way. In Scala 2 all base types' companion objects are part of the implicit scope.

And in Scala 3 as well. That part is unchanged.

[odersky]

I think I see now why the two approaches are different. It has to do with projections. Scala 2 had the philosophy that types are really formed from projections like A#B and that a.B is just an abbreviation of a.type # B. This was in turn influenced by Java, since Java's inner classes correspond to projections and Java has no notion of a path-dependent type.

Dotty in turn is influenced by DOT which is built on path dependent types, and has no concept of projections.

Now, if you take projections as your basis then it's natural to treat as parts of A # B both A and B. Consequently, we take the base classes of both and look in their companion objects. So the treatment is symmetric for the prefix and the type member. If the prefix is a singleton like a.type we widen it to "get it into shape". So that gives a rationale for Scala 2's behavior.

But in Dotty, projections are at just a marginal construct to support legacy code. It is a much cleaner dependently typed language, where projections have no natural place. Therefore, we treat a.B as the primitive form. And that leads to an asymmetric treatment, where we still look in all
companion objects of base classes of B, and in addition we look for all members of p.

If p is a simple object reference, the two meanings coincide. If p refers to an object that extends base classes, we search their companions only in Scala 2. If p refers to some other val, we consider its members only in Scala 3, whereas in Scala we again search companions of base classes of the underlying type.

[neko-kai]

@odersky

It sort of works for objects in prefixes since the widened type of an object is the module class, and the module class is its own companion. So in this special case it matches our intuitions. But the special case generalizes only in Dotty in a way I would find natural.

IMHO, it's not a special case, but follows directly from assuming that implicit scope belongs to a type, it's not about paths of values, but about paths of types - there is only one actual prefix type for a given TypeRef, it doesn't change in any way if its aliased through final val's - they are syntactic and do not change the type - implicit scope belongs to a type and the same type must only have one implicit scope - this is the intent behind the rules for dealiasing type aliases & widening singleton aliases - it's impossible to observe multiple implicit scopes for the same type in Scala 2, deliberately, - and it's an absolutely vital guarantee for practitioners and not having it would make implicits even more inscrutable by making companion scopes unstable and "floating" based on the way the exact same type is aliased. (I'm actually just repeating this post - https://github.com/lampepfl/dotty/issues/9094#issuecomment-638343353 - the arguments about path-dependency and isInstanceOf).

Scala 2 says: No, members are not in the implicit scope, but all members of companion objects of base types of the widened type of P are. This looks really roundabout and counter-intuitive for me

Scala 2 just says that all prefixes that the type is path-dependent on can contribute to implicit scope, but inconsequential prefixes can't, inconsequential prefixes are those that the member is not path-dependent on, that have no effect at all on type equality or value equality and are just syntactic aliases:

trait S {
  case class T()
}

object A extends S
object B extends S

val X = A
val Y = X

def isEq[A, B](implicit ev: A =:= B = null) = println(ev ne null)

@main def main = {

  // distinct type at compile-time
  isEq[A.T, B.T]

  // distinct $outer at runtime
  println(A.T() == B.T())

  // same type at compile-time
  isEq[X.T, Y.T]

  // same $outer at runtime
  println(X.T() == Y.T())
}

[1]

[neko-kai]

@odersky

If p refers to an object that extends base classes, we search their companions only in Scala 2.

Seems like Dotty does search companions of base classes of prefixes, unless the example below is incorrect[1]:

trait Show[T] {def show(a: T): String}

object S extends LowPriorityInstances {
  opaque type Permissions <: String = String
}

sealed trait LowPriorityInstances
object LowPriorityInstances {
  given Show[S.Permissions] = _ => "perms"
}

@main def main = println(implicitly[Show[S.Permissions]])

[joroKr21]

But two dependent types with different paths are different even if the runtime value is the same. Whereas a type alias should indeed be the same type as the right hand side, regardless of the prefix. One runtime value can have many types due to subtyping but also via different paths, even in Scala 2. Are you saying that it's confusing that the same value can have different implicit scopes depending on its type?

Implicit scope is a property of the type, not the value. In Scala 2 you can influence the implicit scope of a value by upcasting it but not by using a different path. Whereas in Dotty both matter. I think that is more consistent. Does it help to think of normal methods and selection as dynamic dispatch and of extension methods and givens as static dispatch?

I'm not sure about existing code and use cases though. I think probably there exist use cases for finding givens in the prefix. For example shapeless' polymorphic functions come to mind.

The opaque type example - is that some special case? 🤔

[neko-kai]

But two dependent types with different paths are different even if the runtime value is the same. Whereas a type alias should indeed be the same type as the right hand side, regardless of the prefix

They are not different, an aliased path is still the exact same type:

object A {
   trait T
   val T = new T{}
}
val B = A

val z = implicitly[A.T =:= B.T]
val a: A.T.type = B.T.type
val b: B.T.type = A.T.type

Are you saying that it's confusing that the same value can have different implicit scopes depending on its type?

No, it's not, when the static type is different the implicit scope should be different. When the static type is exaclty the same - the implicit scope should be exactly the same. It's impossible in Scala 2 to construct a different implicit scope for exactly the same static type - that's counter-confusing and allows solid repeatable reasoning about implicit scopes.

I think probably there exist use cases for finding givens in the prefix.

All usages of opaque types, abstract type aliases, and Scala 2's tagged types and newtypes rely on finding implicits in the prefix, because an abstract type alias does not have a companion of its own, only its prefix contributes to the implicit scope.

[joroKr21]

I meant something like this:

scala> val x = new S {}
val x: S = $anon$1@52d96367

scala> val y = x
val y: S = $anon$1@52d96367

scala> isEq[x.T, y.T]
false

scala> x.T() == y.T()
val res2: Boolean = true

[neko-kai]

@joroKr21
That's just widening in inference though, because y gets widened to y: S

scala> val x = new S{}
val x: S = $anon$1@12ebfb2d

scala> val y: x.type = x
val y: x.type = $anon$1@12ebfb2d

scala> isEq[x.T, y.T]
true

scala> x.T() == y.T()
val res4: Boolean = true

[odersky]

Seems like Dotty does search companions of base classes of prefixes, unless the example below is incorrect[1]:

In fact, that is another manifestation of #9103. It's fixed in #9106, where the example does not compile anymore.

[odersky]

there is only one actual prefix type for a given TypeRef

This is true by definition. The prefix type of a TypeRef p.T is p.type. If q is an alias of p, then the prefix type of q.T is still q.type. You seem to have another definition of prefix type, but I am not quite clear what it is.

[neko-kai]

The prefix type of a TypeRef p.T is p.type. If q is an alias of p, then the prefix type of q.T is still q.type. You seem to have another definition of prefix type, but I am not quite clear what it is.

I assumed, incorrectly, that after dealias it would be p.type in the TypeRef. But aside of that error, I mean that for the purpose of type relations, =:=, <:< it's _always_ p.type – you cannot manufacture different subtype relations by aliasing - exactly because these singleton-typed values are mere aliases, they're inconsequential by themselves. We do not create new implicit scopes for type aliases, why would they appear for value aliases then?

Another interaction: a def alias prefix does not contribute to implicit scope[1]:

object A {
  trait T
}

object outer {
  def a: A.type = { println("prefixed by side-effect def, but side-effect will not be executed"); A }
  given Ordering[a.T] = null
}

val defPath: outer.a.T = new outer.a.T {}

object App extends App {
  defPath
  implicitly[Ordering[outer.a.T]] //error
}

[odersky]

We do not create new implicit scopes for type aliases, why would they appear for value aliases then?

That's a good point. #9119 fixes that by not considering value aliases. Specifically a value alias is a val that has another singleton type or an object reference as type. With #9119 these do not contribute to the implicit scope anymore.

[neko-kai]

@odersky
Thanks! Although reading the new spec it seems either ambiguous or contradicts this. I think:

If _T_ is a singleton reference, the anchors of its underlying type, plus,
    if _T_ is of the form _(P#x).type_, the anchors of _P_.

This seems to specifically include the prefixes of T where T is a singleton reference, i.e. the scope is modified by a value alias by including its prefixes, whether or not the underlying type is another singleton.

[neko-kai]

@odersky @anatoliykmetyuk

Specifically a value alias is a val that has another singleton type or an object reference as type. With #9119 these do not contribute to the implicit scope anymore.

It seems #9119 did not change this, on latest nightly after #9119 a value alias to an object still contributes to the implicit scope:

object A {
  class T
}
object AliasPrefix {
  final val xa = A
  implicit val x: xa.T = new xa.T
}
object Test extends App {
  def foo(implicit x: AliasPrefix.xa.T) = x
  foo // found, but AliasPrefix is from a value alias, unrelated to A
}