Stack overflow in TypeComparer

[abeln]

Attempting to compile the following program causes a stack overflow in TypeComparer:

class T

class N[Z]

class C[X] extends N[N[_ >: C[C[X]]]] {
  def cast(c: C[T]): N[_ >: C[T]] = c
}

Stack trace

scalac rejects the program:

anietoro@scslt148:~/src/test$ scalac kk2.scala 
kk2.scala:5: error: illegal cyclic reference involving class C
class C[X] extends N[N[_ >: C[C[X]]]] {
                       ^
kk2.scala:6: error: type mismatch;
 found   : C[T]
 required: N[_ >: C[T]]
Note: T <: Any, but class N is invariant in type Z.
You may wish to define Z as +Z instead. (SLS 4.5)
  def cast(c: C[T]): N[_ >: C[T]] = c
                                    ^
two errors found

How I got to this program: this is Example 2 at the bottom of this paper. Both C# and (I guess) Scala implement a check for "expansive cycles" (see Section 9.2 of the CLR spec) that rejects this kind of program.

Does Dotty implement such a check?

[odersky]

Not yet. It would be important to add it, though. If someone volunteers to do it, would be mucg appreciated.

[abeln]

For reference, here's the check in scalac:
https://github.com/scala/scala/blob/2.12.x/src/compiler/scala/tools/nsc/typechecker/Typers.scala#L1777
https://github.com/scala/scala/blob/2.12.x/src/reflect/scala/reflect/internal/Types.scala#L1698

[abeln]

@odersky do you have any comments/suggestions regarding porting the above code to Dotty? Why is the implementation of the cycle detection under scala/reflect, as opposed to tools/nsc? (I'm not familiar with the scalac code)

[odersky]

@abeln The logic of scalac is split between the nscandreflect.internalpackages. Large parts ofTypesandSymbols` is also needed for implementing reflection that's why they are there. The particular part you look at could probably just as well go into Typer.

In Dotty, the obvious place for putting these checks is in Checking, with a call from Typer.

[abeln]

Ok, taking a look at this.

Here's a simpler example (also from the paper) that doesn't use type refinements:

class N[-Y]
class C[X] extends N[N[C[C[X]]]]

class Foo {
  def foo[T](x: C[T]): N[C[T]] = x
}

The sequence of subtype tests is as follows:

C[T] <:? N[C[T]]
N[N[C[C[T]]]] <:? N[C[T]]
C[T] <:? N[C[C[T]]]
N[N[C[C[T]]]] <:? N[C[C[T]]]
C[C[T]] <:? N[C[C[T]]]
... (a cycle: notice the number of Cs has increased by one w.r.t the original test)

[abeln]

Closing, since this is the same as #4805