Unexpected "recursive value needs type" compile error (triggered by local implicits)

Question

I just encountered an unexpected compile error "recursive value xx needs type". Trying to simplify, I came up with the following code that doesn't compile with Scala 2.12.3:

class Wrapped[A](val inner: A)(implicit val ctag: ClassTag[A]){
  type Inner = A
  def classInfo: String = ctag.toString
}
object Implicits {
  val W = new Wrapped(1234)
  implicit val InnerSeq: Seq[W.Inner] = Seq(1,2)
  implicit val InnerSet: Set[W.Inner] = Set(1,2) // Error: recursive value W needs type
}

I would assume that the type of W is well defined. But it seems that due to the type W occurring in the return type of the local implicit values, W is considered recursive even if the implicits are not used in creation of W.

The strange thing is that removing the second value InnerSet makes the code compile. So one implicit val referring W.Inner is OK, while two or more is a no-go.

Removing the implicit ClassTag dependency for the Wrapper also makes the code compile.

It is easy to get around the problem by moving W to a separate trait, but it would be good to know what's going on here. Why does the code compile with only one implicit in scope?

Update:

In the last preview version of Dotty, the compiler behaves more consistently and doesn't allow any implicits referring W.inner in scope at all:

[error] -- [E045] Syntax Error: 
[error] 9 |  implicit val InnerSeq: Seq[W.Inner] = Seq(1,2)
[error]   |                             ^
[error]   |                             cyclic reference involving value W
[error] one error found

Answer 1

This happens due to the scope of the local implicits you've defined, how type inference works and how implicit resolution works. If we look at the output of the typer phase (using Ytyper-debug), we see:

|-- new Wrapped(1234) EXPRmode (site: value W  in Implicits)
|    |-- new Wrapped BYVALmode-EXPRmode-FUNmode-POLYmode (silent: value W  in Implicits)
|    |    |-- new Wrapped EXPRmode-POLYmode-QUALmode (silent: value W  in Implicits)
|    |    |    |-- Wrapped FUNmode-TYPEmode (silent: value W  in Implicits)
|    |    |    |    \-> Wrapped
|    |    |    \-> Wrapped[A]
|    |    \-> (inner: A)(implicit ctag: scala.reflect.ClassTag[A])Wrapped[A]
|    |-- 1234 BYVALmode-EXPRmode-POLYmode (site: value W  in Implicits)
|    |    \-> Int(1234)
|    solving for (A: ?A)
|    [search #1] start `(inner: A)(implicit ctag: scala.reflect.ClassTag[A])Wrapped[A]`, searching for adaptation to pt=scala.reflect.ClassTag[Int] (silent: value W  in Implicits) implicits disabled
|    |-- Seq[W.Inner] TYPEmode (site: value InnerSeq  in Implicits)
|    |    |-- scala.`package` EXPRmode-POLYmode-QUALmode (site: value InnerSeq  in Implicits)
|    |    |    \-> scala.type
|    |    |-- W.Inner TYPEmode (site: value InnerSeq  in Implicits)
|    |    |    |-- W EXPRmode-POLYmode-QUALmode (site: value InnerSeq  in Implicits)
|    |    |    |    |-- new Wrapped(1234) EXPRmode (site: value W  in Implicits)
|    |    |    |    |    |-- new Wrapped BYVALmode-EXPRmode-FUNmode-POLYmode (silent: value W  in Implicits)
|    |    |    |    |    |    |-- new Wrapped EXPRmode-POLYmode-QUALmode (silent: value W  in Implicits)
|    |    |    |    |    |    |    \-> Wrapped[A]
|    |    |    |    |    |    \-> (inner: A)(implicit ctag: scala.reflect.ClassTag[A])Wrapped[A]
|    |    |    |    |    solving for (A: ?A)
|    |    |    |    |    [search #2] start `(inner: A)(implicit ctag: scala.reflect.ClassTag[A])Wrapped[A]`, searching for adaptation to pt=scala.reflect.ClassTag[Int] (silent: value W
isabled
|    |    |    |    |    |-- Set[W.Inner] TYPEmode (site: value InnerSet  in Implicits)
|    |    |    |    |    |    |-- W.Inner TYPEmode (site: value InnerSet  in Implicits)
|    |    |    |    |    |    |    |-- W EXPRmode-POLYmode-QUALmode (site: value InnerSet  in Implicits)
|    |    |    |    |    |    |    |    caught scala.reflect.internal.Symbols$CyclicReference: illegal cyclic reference involving value W: while typing W

The typer first has to figure out the type parameter of A of Wrapper, since we haven't provided an explicit type, the compiler treats it as Wrapper[A]. The compiler sees that you require an implicit ClassTag[A] in scope to create an instance of Wrapper, so implicit resolution kicks in. The Scala compiler will begin with implicits at the local scope, which are InnerSeq and InnerSet, as you've defined. Continuing the implicit search, the compiler look at InnerSeq and tries to see if it a fit for the resolution of type A and it's corresponding ClassTag[A], but InnerSeq is defined in terms of W.Inner, thus the compiler has to look into W and see it's underlying type, which is currently defined to be Wrapper[A] as we saw in the beginning. Since the implicit resolution is recursive, it now starts looking up an implicit in scope which can help it infer Wrapper[A], and the next implicit definition is InnerSet, but it is also defined in terms of `W.Inner! thus we have a cyclic reference and the compiler bails out.

Now, when we define an explicit type for W:

val W: Wrapped[Int] = new Wrapped(1234)

The type checker knows the W.type is Wrapped[Int] and not Wrapped[A], thus it need not do any recursive implicit resolution. We can see this again in the debug output:

|-- Seq[W.Inner] TYPEmode (site: value InnerSeq  in Implicits)                                 
|    |-- scala.`package` EXPRmode-POLYmode-QUALmode (site: value InnerSeq  in Implicits)       
|    |    \-> scala.type                                                                       
|    |-- W.Inner TYPEmode (site: value InnerSeq  in Implicits)                                 
|    |    |-- W EXPRmode-POLYmode-QUALmode (site: value InnerSeq  in Implicits)                
|    |    |    \-> com.testing.SOTesting.Implicits.W.type (with underlying type Wrapped[Int])  <---- This is the difference
|    |    [adapt] A is now a TypeTree(com.testing.SOTesting.Implicits.W.Inner)                 
|    |    \-> com.testing.SOTesting.Implicits.W.Inner                                          
|    \-> Seq[com.testing.SOTesting.Implicits.W.Inner]      

Since we now know the underlying W.type, the typer can bind W.Inner to Int, thus find a match for A.