Infinite recursion when printing cyclic types

[samuelgruetter]

In this example

object infpaths {

  object a {
    trait T { t =>
      type M <: t.b.M
      type T <: a.T
      val b: t.T
    }
    val x: a.T = ???
  }

  val m1: a.x.M = ???
  val m2: a.x.b.M = m1
  val m3: a.x.b.b.M = m2

}

we run into an infinite recursion:

[info] error occurred during: TypeBounds(TypeRef(ThisType(module class scala),Nothing), TypeRef(TermRef(ThisType(module class infpaths$),a),T)): TypeBounds(TypeRef(ThisType(module class scala),Nothing), TypeRef(TermRef(ThisType(module class infpaths$),a),T)) member M
[info] exception occured while typechecking tests/pos/infpaths.scala
[error] Exception in thread "main" java.lang.StackOverflowError
[error]     at java.lang.String.getChars(String.java:826)
[error]     at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:416)
[error]     at java.lang.StringBuilder.append(StringBuilder.java:132)
[error]     at scala.collection.mutable.StringBuilder.<init>(StringBuilder.scala:47)
[error]     at scala.collection.mutable.StringBuilder.<init>(StringBuilder.scala:52)
[error]     at scala.runtime.ScalaRunTime$._toString(ScalaRunTime.scala:166)
[error]     at dotty.tools.dotc.core.Types$TermRef.toString(Types.scala:1124)
[error]     at java.lang.String.valueOf(String.java:2854)
[error]     at scala.collection.mutable.StringBuilder.append(StringBuilder.scala:198) 
[error]     at scala.collection.TraversableOnce$$anonfun$addString$1.apply(TraversableOnce.scala:345)
[error]     at scala.collection.Iterator$class.foreach(Iterator.scala:743)
[error]     at scala.collection.AbstractIterator.foreach(Iterator.scala:1174)
[error]     at scala.collection.TraversableOnce$class.addString(TraversableOnce.scala:343)
[error]     at scala.collection.AbstractIterator.addString(Iterator.scala:1174)
[error]     at scala.collection.TraversableOnce$class.mkString(TraversableOnce.scala:309)
...

Note that scalac correctly rejects this example:

<console>:12: error: cyclic aliasing or subtyping involving type M
             type M <: t.b.M
                  ^

I suspect that there might not only be a problem with printing, but also with cycle detection...

[odersky]

@samuelgruetter It looks like a type is printed with toString, where it should be printed with show. Unlike toString, show contains a cycle detection. Can you look into it, and diagnose or fix please?

[samuelgruetter]

That was indeed the case: TermRef was printed with toString instead of show. I fixed this by replacing some s"..." by i"...". But after that, there still was a stack overflow exception in TermRefWithSignature.equals, because a TermRefWithSignature was created whose prefix was a.x.b.b.b.b..., with so many b's that the recursively implemented equals caused a stack overflow.
However, if enough debug output was enabled, the bad trait T was printed before this happened, and printing it caused the SymDenotation of its self reference t to be completed, and SymDenotation.completeFrom detected a "cyclic reference involving val t".

I added some code which makes dotty crash not only in TermRefWithSignature.equals, but already when the ever growing path types a.b.b.....M are created and getting too long. It shows that val m1: a.x.M = ??? is typed before a SymDenotation of trait T is calculated (which would detect the cycle), and this results in such an "infinite" path type being created. You can see the code with all my debug output in this branch, and the output here.

Scala 2 solves this problem with the method checkNonCyclic in nsc/typechecker/Typers.scala, which it calls directly after typechecking the TypeDef M.

I noticed that dotty also has several cycle detection mechanisms, two of which I thought (at first sight) might be suitable for this issue:

• `SymDenotation.completeFrom`, containing `if (myFlags is Touched)`. Kicks in when printing the self reference t. But only works on the whole type containing the bad type member M, not when checking type member M individually, because we would complete different SymDenotations (one for each path length), so we would never revisit an already touched SymDenotation.
  

•  `NamedType.controlled`, which says it can guard against cases like "type T <: T". It keeps a map of visited NamedTypes (ie types tp on which `tp.controlled{op}` was called). But I think there is no NamedType which could serve as tp (to call controlled on) here, because we have different (ever growing) types every time.
  

So I think the existing cycle detection mechanisms in dotty are not sufficient and we need to introduce an additional mechanism, similar to checkNonCyclic in Scala 2, which would be invoked at the end of Typer.typedTypeDef.

@odersky do you agree?

[odersky]

I verified that this works now.