Implicit resolution in scala 2.10.x. what's going on?

Question

I am using scala 2.10.0-snapshot dated (20120522) and have the following Scala files:

this one defines the typeclass and a basic typeclass instance:

package com.netgents.typeclass.hole

case class Rabbit

trait Hole[A] {
  def findHole(x: A): String
}

object Hole {
  def apply[A: Hole] = implicitly[Hole[A]]
  implicit val rabbitHoleInHole = new Hole[Rabbit] {
    def findHole(x: Rabbit) = "Rabbit found the hole in Hole companion object"
  }
}

this is the package object:

package com.netgents.typeclass

package object hole {

  def findHole[A: Hole](x: A) = Hole[A].findHole(x)

  implicit val rabbitHoleInHolePackage = new Hole[Rabbit] {
    def findHole(x: Rabbit) = "Rabbit found the hole in Hole package object"
  }
}

and here is the test:

package com.netgents.typeclass.hole

object Test extends App {

  implicit val rabbitHoleInOuterTest = new Hole[Rabbit] {
    def findHole(x: Rabbit) = "Rabbit found the hole in outer Test object"
  }

  {
    implicit val rabbitHoleInInnerTest = new Hole[Rabbit] {
      def findHole(x: Rabbit) = "Rabbit found the hole in inner Test object"
    }

    println(findHole(Rabbit()))
  }
}

As you can see, Hole is a simple typeclass that defines a method which a Rabbit is trying to find. I am trying to figure out the implicit resolution rules on it.

• with all four typeclass instances uncommented, scalac complains about ambiguities on rabbitHoleInHolePackage and rabbitHoleInHole. (Why?)

• if I comment out rabbitHoleInHole, scalac compiles and I get back "Rabbit found the hole in Hole package object". (Shouldn't implicits in the local scope take precedence?)

• if I then comment out rabbitHoleInHolePackage, scalac complains about ambiguities on rabbitHoleInOuterTest and rabbitHoleInInnerTest. (Why? In the article by eed3si9n, url listed below, he found implicits btw inner and outer scope can take different precedence.)

• if I then comment out rabbitHoleInInnerTest, scalac compiles and I get back "Rabbit found the hole in outer Test object".

As you can see, the above behaviors do not follow the rules I've read on implicit resolution at all. I've only described a fraction of combinations you can do on commenting/uncommenting out instances and most of them are very strange indeed - and I haven't gotten into imports and subclasses yet.

I've read and watched presentation by suereth, stackoverflow answer by sobral, and a very elaborate revisit by eed3si9n, but I am still completely baffled.

Answer 1

Let's start with the implicits in the package object and the type class companion disabled:

package rabbit {
  trait TC

  object Test  extends App {
    implicit object testInstance1 extends TC { override def toString = "test1" }

    {
      implicit object testInstance2 extends TC { override def toString = "test2" }

      println(implicitly[TC])
    }
  }
}

Scalac looks for any in scope implicits, finds testInstance1 and testInstance2. The fact that one is in a tighter scope is only relevant if they have the same name -- the normal rules of shadowing apply. We've chosen distinct names, and there neither implicit is more specific than the other, so an ambiguity is correctly reported.

Let's try another example, this time we'll play off an implicit in the local scope against one in the package object.

package rabbit {
  object `package` {
    implicit object packageInstance extends TC { override def toString = "package" }
  }

  trait TC

  object Test  extends App {
    {
      implicit object testInstance2 extends TC { override def toString = "test2" }

      println(implicitly[TC])
    }
  }
}

What happens here? The first phase of the implicit search, as before, considers all implicits in scope at the call site. In this case, we have testInstance2 and packageInstance. These are ambiguous, but before reporting that error, the second phase kicks in, and searches the implicit scope of TC.

But what is in the implicit scope here? TC doesn't even have a companion object? We need to review the precise definition here, in 7.2 of the Scala Reference.

The implicit scope of a type T consists of all companion modules (§5.4) 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 (§5.1.2) of some part of T.

The parts of a type T are:

• if T is a compound type T1 with ... with Tn, the union of the parts of T1, ..., Tn, as well as T itself,
• if T is a parameterized type S[T1, ..., Tn], the union of the parts of S and T1,...,Tn,
• if T is a singleton type p.type, the parts of the type of p,
• if T is a type projection S#U, the parts of S as well as T itself,
• in all other cases, just T itself.

We're searching for rabbit.TC. From a type system perspective, this is a shorthand for: rabbit.type#TC, where rabbit.type is a type representing the package, as though it were a regular object. Invoking rule 4, gives us the parts TC and p.type.

So, what does that all mean? Simply, implicit members in the package object are part of the implicit scope, too!

In the example above, this gives us an unambiguous choice in the second phase of the implicit search.

The other examples can be explained in the same way.

In summary:

• Implicit search proceeds in two phases. The usual rules of importing and shadowing determine a list of candidates.
• implicit members in an enclosing package object may also be in scope, assuming you are using nested packages.
• If there are more than one candidate, the rules of static overloading are used to see if there is a winner. An addiotnal a tiebreaker, the compiler prefers one implicit over another defined in a superclass of the first.
• If the first phase fails, the implicit scope is consulted in the much same way. (A difference is that implicit members from different companions may have the same name without shadowing each other.)
• Implicits in package objects from enclosing packages are also part of this implicit scope.

UPDATE

In Scala 2.9.2, the behaviour is different and wrong.

package rabbit {
  trait TC

  object Test extends App {
    implicit object testInstance1 extends TC { override def toString = "test1" }

    {
      implicit object testInstance2 extends TC { override def toString = "test2" }

      // wrongly considered non-ambiguous in 2.9.2. The sub-class rule
      // incorrectly considers:
      //
      // isProperSubClassOrObject(value <local Test>, object Test)
      //   isProperSubClassOrObject(value <local Test>, {object Test}.linkedClassOfClass)
      //   isProperSubClassOrObject(value <local Test>, <none>)
      //     (value <local Test>) isSubClass <none>
      //        <notype> baseTypeIndex <none> >= 0
      //        0 >= 0
      //        true
      //     true
      //   true
      // true
      //
      // 2.10.x correctly reports the ambiguity, since the fix for
      //
      // https://issues.scala-lang.org/browse/SI-5354?focusedCommentId=57914#comment-57914
      // https://github.com/scala/scala/commit/6975b4888d
      //
      println(implicitly[TC])
    }
  }
}