Allow recursive type projections

[scabug]

Currently the Scala compiler outputs an "illegal cyclic reference" error when a type projection references itself, even though the containing type is instantiated with different type parameters, see the code example below. This severely limits the possibilities for meta programming (as done in C++) in Scala, which is a shame because the language has the expressive power to make it work.

I see two solutions to this limitation:

• Remove the cyclic reference check and add a maximum type alias/projection depth similar to the template instantiation depth limit found in many C++ compilers (including GCC, -ftemplate-depth-n).

• Enhance the cyclic reference checker, for example if the path contains A[Int]#Type and A[Float]#Type it shouldn't be considered a cyclic reference.

object ProjTest {
  trait MInt { type Type[T <: MInt] }
  trait _0 extends MInt { type Type[T <: MInt] = Boolean }
  trait Succ[Pre <: MInt] extends MInt { type Type[T <: MInt] = T#Type[T] }
  
  type _1 = Succ[_0]
  type _2 = Succ[_1]
  
  type X1 = _0#Type[_0]  // Ok
  type X2 = _1#Type[_0]  // Ok
  type X3 = _2#Type[_2]  // Compiler error, illegal cyclic reference involving type Type
}

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-1291?orig=1
Reporter: @jesnor

[scabug]

Geoffrey Alan Washburn (washburn) said:
It might be reasonable to add experimental support for this. If nothing else it could be useful to test out how things would behave if we could come up with a less restrictive type checking algorithm. On the downside, it would probably require adding at least an additional byte of memory to every symbol in memory. However, if we stored the counters in a separate map rather than with the symbol itself, we could avoid the penalty when users do not provide a depth on the command-line.

[scabug]

@odersky said:
It would be valuable, see also mail by Klaus Ostermann who ran into a similar problem. It would demand major re-engineering of the compiler and spec, though.

[scabug]

Geoffrey Alan Washburn (washburn) said:
I just hacked in experimental support for bounding recursion by depth, and it does help with Ostermann's example, but the example in this ticket will loop no matter what depth you give it. So this example will definitely require a more elaborate typechecking algorithm. I am going to close this ticket because fixing this particular example will most likely require a change significant to warrant a SIP.

[scabug]

@jesnor said:
Sorry, the code is buggy. A correct example:

object ProjTest {
  trait MInt { type Type }
  trait _0 extends MInt { type Type = Boolean }
  trait Succ[Pre <: MInt] extends MInt { type Type = Pre#Type }
  
  type _1 = Succ[_0]
  type _2 = Succ[_1]
  
  type X1 = _0#Type   // Ok
  type X2 = _1#Type   // Ok
  type X3 = _2#Type   // Compiler error, illegal cyclic reference involving type Type
}

Which doesn't contain a loop and should be expanded to:

_2#Type = Succ[_1]#Type = _1#Type = Succ[_0]#Type = _0#Type = Boolean

Can you verify if this works with your experimental branch?

If it does, it could be hopefully be used to implement more advanced things like HList (see http://jnordenberg.blogspot.com).

[scabug]

@odersky said:
Milestone postponed deleted

[scabug]

@paulp said:
The supplied code now compiles with the experimental -Yrecursion option.