Compiler crash with Dotty 0.22.0-RC1

[rachitnigam]

reproduction steps

Running the following program crashes the compiler with java.lang.OutOfMemoryError.

  enum Kind {
    case Type
  }

  enum Term[T <: Term[T, K], K] {
    case Wrap(t: T)
    case Fun(id: Id, tag: K, ret: Term[T, K])
  }

  enum Type {
    case Var(id: Id)
  }

  val tExp: Term[Type, Kind] =
    Term.Fun("x", Kind.Type, Term.Wrap(Type.Var("x")))

  def main(args: Array[String]): Unit = { }

problem

I was trying to implement an parametric AST where the Term enum can be parameterized with a type T used to recursively build well-typed terms (so a Term[Type] can only contain other Term[Type]) and a "Tag" K.

On changing the program to not have K (note the mistake where the Fun node still has an unbound type variable K), I get a different error:

  enum Term[T <: Term[T]] {
    case Wrap(t: T)
    case Fun(id: Id, tag: K, ret: Term[T])
  }

  enum Type {
    case Var(id: Id)
  }

  val tExp: Term[Type, Kind] =
    Term.Fun("x", Term.Wrap(Type.Var("x")))

[error] -- [E007] Type Mismatch Error:
[error] 41 |    Term.Fun("x", Term.Wrap(Type.Var("x")))
[error]    |                            ^^^^^^^^^^^^^
[error]    |Found:    Main.Type
[error]    |Required: Main.Term[
[error]    |  LazyRef(
[error]    |    Main.Term[
[error]    |      LazyRef(
[error]    |        Main.Term[
[error]    |          LazyRef(
[error]    |            Main.Term[
[error]    |              LazyRef(
[error]    |                Main.Term[
[error]    |                  LazyRef( ... // repeats for a while    

expectation

In the program above, I expected the compiler to infer the type for tExp to be Term[Type, Kind]. Instead, it infinite loops. If this is expected behavior, can someone explain what's happening?

[odersky]

The same effects happen if the enum is expanded to explicit classes and objects.

The root cause is that the error messages get too big since there is an implicit unrolling of the Term recursion. We do have a break in that we stop with ... after 100 recursions. This explains the behavior in the second case, where the recursion is linear. But in the first case, we have a fan out of 2 in the type, so a recursion depth of 100 gives an output of size 2^100.

This is an inherent problem of the functional approach to formatting. If we printed imperatively, the output would just go on and on until the user presses ^C. But since we format the text as a purely functional value, we see nothing before we run out of memory.