Stack overflow on subtype of large union for IArray[String] literal

[ryanberckmans]

minimized code

With dotty 0.17.0-RC1

// This code produces the compiler error below
val Names = IArray(
  "Aaliyah",
  "Aaron",
  // ... 5000 more names as string literals
)

// This code triggers the same compile error
val Names: IArray[String] = IArray(/* 5000 names */)

// This code compiles successfully
val Names = IArray[String](/* 5000 names */)


[error] 2 |val Names = IArray(
[error]   |                                      ^
[error]   |Recursion limit exceeded.
[error]   |Maybe there is an illegal cyclic reference?
[error]   |If that's not the case, you could also try to increase the stacksize using the -Xss JVM option.
[error]   |A recurring operation is (inner to outer):
[error]   |
[error]   |  subtype ... | ... | ... | ...(...) | ...(...) | String("Winnie") | String("Winnifred") |
[error]   |
[error]   |String("Winona") | String("Winston") | String("Winter") | String("Wm") |
[error]   |  String("Wonda")

expectation

Expected this code to compile:

IArray("Aaliyah", "Aaron", /* 5000 more names */)```

[ashwinbhaskar]

@ryanberckmans What is IArray? Is it your own custom class?

[ryanberckmans]

@ashwinbhaskar IArray is a new immutable array type in dotty.

[ashwinbhaskar]

@ryanberckmans ah okay.

[ashwinbhaskar]

I would love to give this a try if someone could just point me the way.

[ashwinbhaskar]

@ryanberckmans Looking at the implementation of IArray it looks like it is a type alias for Array
type IArray[+T] = Array[_ <: T] .

Is it possible to verify if this problem also happens with Array?

[bishabosha]

Which version are you running on, I have tried this with the code

val arr = IArray("qwertyuiop",
"qwertyuiop",
"qwertyuiop",
"qwertyuiop",
"qwertyuiop",
"qwertyuiop",
"qwertyuiop",
"qwertyuiop",
"qwertyuiop",
"qwertyuiop",
"qwertyuiop",
//...7800 more times
)

which compiles fine, including in the repl

[ryanberckmans]

@bishabosha I'm on dotty 0.17.0-RC1. The "qwertyuiop" example compiles fine I think because its subtype is IArray["qwertyuiop"], which is of fixed size because the same string is repeated 7800 times . The stack overflow comes from 5000 different strings, causing a subtype that's a large union, like IArray["Aaliyah" | "Aaron" ...].

[ryanberckmans]

@ashwinbhaskar looks like the stack overflow comes from subtype generation. The error is not specific to IArray. A fix might generate this subtype non-recursively or tail-recursively, or perhaps abort subtype generation when a stack depth is hit (which would be a feasible solution in this case because the specific subtype is unused.)

[ashwinbhaskar]

@ryanberckmans hmm..okay. Where is this subtype generation happening?

[ryanberckmans]

@ashwinbhaskar I'm just a user and have no knowledge of dotty internals. Not sure I can help any further. Cheers

[nicolasstucki]

This looks like an issue with opaque types and subtyping. It might be tricky to fix.

[odersky]

My guess is the issue is with union types, not opaque types. Handling 5000+ element unions of singleton types is super hard. That's precisely the kind of scenario that motivated our initial design where unions could not contain singletons.

I am unsure what to do here. In practice it seems that any union type larger than a couple of hundred operands is a waste of compiler resources and should be widened. But how to do that in a principled way?

[bishabosha]

Progress has been made to fix this issue in #12928 however there is now a stack overflow in mapWithIndexConserve which is not stack safe
https://github.com/lampepfl/dotty/blob/dd4a23514b765b9d2e35eae798a6fd37395e4fb5/compiler/src/dotty/tools/dotc/core/Decorators.scala#L164