Floating implicit scope in Dotty and the crisis of ambiguous specification

There’s a new feature in Scala 3, it’s called “floating implicit scopes”.
This feature allows you to extend the implicit scope of any type by creating an object with a value that refers to the enclosing object of that type.
You can use it like this[1]:

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

// an ordinary case class with no implicits

object OriginalPrefix {
  case class X()
}

// we make a new object and add an implicit there

object NewPrefix {
  implicit val showX: Show[X] = _ => "This is an implicitly patched `X`"

  // this innocuous line does the magic:
  final val original = OriginalPrefix
}

object App extends App {
  
  // let's check our implicits:

  def defaultShow[A]: Show[A] = _ => "I don't know what that is"

  def printShow[A](a: A)(implicit showOrDefault: Show[A] = defaultShow[A]) = {
    println(showOrDefault.show(a))
  }

  // ordinary X does not have a Show instance:

  printShow[OriginalPrefix.X](new OriginalPrefix.X)
  // I don't know what that is

  // But if we refer to it by a special name it now has a shiny new Show instance:

  printShow[NewPrefix.original.X](new OriginalPrefix.X)
  // This is an implicitly patched `X`

  // Note: `val original = OriginalPrefix` assignment did not change the type, it's still the same

  implicitly[OriginalPrefix.X =:= NewPrefix.original.X]
  val x1: OriginalPrefix.X = new NewPrefix.original.X
  val x2: NewPrefix.original.X = x1
}

Scalac uses defaultShow both times[2] so this is a new feature.

This feature seems very useful, now every time you re-export an object using an alias val, you might potentially add more implicits to the new re-exported name, even if you don’t know you’re doing that. Very powerful.

How does it work? We know that the prefix of a type is a part of the implicit scope of a type. So for any type Obj.Member all the implicits in Obj are part of Member's implicit scope, the rule applies recursively, so for SuperObj.Obj.Member, the SuperObj’s implicits are also in scope.

There’s something very wrong with Scalac - it doesn’t recognize that NewPrefix.original is the prefix of X and so a reference to NewPrefix.original.X does not get the implicits in NewPrefix.

Turns out, Scalac is following the dreaded Scala Language Specification! The infamous SLS has this to say on the matter:

There is a notable absence of a clause for selections Obj.Member, instead they are implciitly folded under projections of form (Obj.type)#Member.

Note the absence of as well as 𝑇 itself in the singleton type clause. That’s right, a singleton type itself and its parts are NOT a part of implicit scope. Instead only the parts of the type of p, i.e. the non-singleton type underlying the singleton type are parts of implicit scope - the singleton type itself is completely ignored.

Scalac faithfully executes this spec, throwing away the singleton type and considering only the underlying type - as evidenced by its source code[3]:

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

The tp itself is not added to the mutable infoMap, it’s decomposed into non-singletons and thrown away. (You may think, if objects are singletons of type AnyRef, how come they’re in implicit scope at all? That’s why the title says “ambiguous spec” – it’s clear from the wording that for implicit scope only the non-singleton type must be considered, but it’s not clear why the non-singleton type of an object is still its singleton type in scalac[4])

Following this algorithm (and keeping in mind that for object definitions the ‘type of p’ is somehow still the object[4]) causes the following transformation:

NewPrefix.original.X ->
(NewPrefix.original.type)#X ->
widen((NewPrefix.original.type))#X ->
widen((NewPrefix.original.type where { val original: OriginalPrefix.type }))#X ->
OriginalPrefix.type#X

By contrast, in Dotty, where the specification compliant widening should occur, where there’s even a comment saying that it SHOULD occur[5], it doesn’t seem to occur[6]:

            if (isAnchor(sym)) {
              val pre = tp.prefix
              addPath(pre)

Prefixes are just accumulated recursively without being widened beforehand, which leads to the observed behavior.

If you’re still not convinced that this behavior is a bug, let me demonstrate clearly:

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

object OriginalPrefix {
  case class X()
  given showX as Show[X] { def (a: X).show = a.toString }
}

final val AliasPrefix = OriginalPrefix

def ok = implicitly[Show[OriginalPrefix.X]]

def ambiguous = implicitly[Show[AliasPrefix.X]]

// ambiguous implicit arguments: both object showX in object OriginalPrefix and object showX in object OriginalPrefix match type Show[AliasPrefix.X] of parameter ev of method implicitly in object DottyPredef

This causes an error because the implicit showX in AliasPrefix is counted twice, both as a member OriginalPrefix and as a member AliasPrefix - they’re both counted separately as two different implicit definitions even though they are the same definition.

If a decision was made at some point to extend implciit scopes with “floating”, this case - which invalidates ALL the implicits in the original prefix object by making them ambiguous when the prefix is “floated” to another path - would’ve been handled as it would surface quickly.

Because this case was not handled - demonstrating that there was no conscious decision to enable this behavior,
and because this behavior is against the spec,
and because this behavior is against the other existing implementation of that spec,
and because this behavior is even against the comments inside Dotty’s own source code,
it’s probably safe to assume that this behavior is a bug.

I’m opening this discussion here because the corresponding bug report in the dotty tracker went nowhere fast[7]. Even if I didn’t convince you that it’s a bug after all, maybe it could really become an official documented feature as a result of discussing it here, or maybe not.

1 Like

That sounds like a bug to me, the compiler should be able to figure out that these are equivalent and therefore not ambiguous.

By contrast, in Dotty, where the specification compliant widening should occur, where there’s even a comment saying that it SHOULD occur (https://github.com/lampepfl/dotty/blob/master/compiler/src/dotty/tools/dotc/typer/Implicits.scala#L496)

Ah that’s interesting, I hadn’t seen that comment, that’s indeed clearer than the spec which just says “the type of p” which for me is “p.type”, so I agree something needs to be done to bring the spec and implementation in alignment.

I think the important clause comes just before that one in the Dotty comments:

   *  - If `tp` is a reference `p.T` to a class or opaque type alias, S also contains all object references
   *    on the prefix path `p`. Under Scala-2 mode, package objects of package references on `p` also
   *    count towards the implicit scope.

And also: I think shapeless 3 might make use of that clause. At least we should check that before trying to change anything.

tasty-reflect QuoteContext API is using “floating implicit scopes”, that’s how I noticed it - because the way it used implicit scope is extremely counter-intuitive and unobvious coming from Scala 2 - i could not figure out how it worked without experimentation, however, it’s fairly easy to change it to use implicit scope by spec.

I checked all occurences of val in shapeless-3 just now and I did not notice anything that could be using this “trick”, notably no implicit definitions inside classes/traits with vals and no uses of val, final val or lazy val for aliasing.

That may need addressing in some other part of the compiler, but in Implicits.scala it will occur naturally once path normalization is restored.