Very slow compile time involving path-dependent types

[pweisenburger]

Compiler version

3.1.2

Minimized code

Given the minimized code:

class /[D, T]
class Delegating[D]

type Aux[E] = Container { type Elements = E }

class Container:
  type Elements = Delegating[Delegates]
  type Delegates

class Resolution[E](value: Aux[E]):
  type Type = Aux[E]

The following code compiles almost instantly (which is expected):

def element0: Container { type Delegates = Unit } = ???

def element16(
    transmittable0: Resolution[?], transmittable1: Resolution[?],
    transmittable2: Resolution[?], transmittable3: Resolution[?],
    transmittable4: Resolution[?], transmittable5: Resolution[?],
    transmittable6: Resolution[?], transmittable7: Resolution[?],
    transmittable8: Resolution[?], transmittable9: Resolution[?],
    transmittable10: Resolution[?], transmittable11: Resolution[?],
    transmittable12: Resolution[?], transmittable13: Resolution[?],
    transmittable14: Resolution[?], transmittable15: Resolution[?])
: Container {
    type Delegates =
      transmittable0.Type / transmittable1.Type /
      transmittable2.Type / transmittable3.Type /
      transmittable4.Type / transmittable5.Type /
      transmittable6.Type / transmittable7.Type /
      transmittable8.Type / transmittable9.Type /
      transmittable10.Type / transmittable11.Type /
      transmittable12.Type / transmittable13.Type /
      transmittable14.Type / transmittable15.Type
  } = ???

def test16 =
  Resolution(
    element16(
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0)))

But the following example, which is just a slightly bigger version of the previous example (22 instead of 16 parameters), takes 10+ seconds to compile on my machine:

def element22(
    transmittable0: Resolution[?], transmittable1: Resolution[?],
    transmittable2: Resolution[?], transmittable3: Resolution[?],
    transmittable4: Resolution[?], transmittable5: Resolution[?],
    transmittable6: Resolution[?], transmittable7: Resolution[?],
    transmittable8: Resolution[?], transmittable9: Resolution[?],
    transmittable10: Resolution[?], transmittable11: Resolution[?],
    transmittable12: Resolution[?], transmittable13: Resolution[?],
    transmittable14: Resolution[?], transmittable15: Resolution[?],
    transmittable16: Resolution[?], transmittable17: Resolution[?],
    transmittable18: Resolution[?], transmittable19: Resolution[?],
    transmittable20: Resolution[?], transmittable21: Resolution[?])
: Container {
    type Delegates =
      transmittable0.Type / transmittable1.Type /
      transmittable2.Type / transmittable3.Type /
      transmittable4.Type / transmittable5.Type /
      transmittable6.Type / transmittable7.Type /
      transmittable8.Type / transmittable9.Type /
      transmittable10.Type / transmittable11.Type /
      transmittable12.Type / transmittable13.Type /
      transmittable14.Type / transmittable15.Type /
      transmittable16.Type / transmittable17.Type /
      transmittable18.Type / transmittable19.Type /
      transmittable20.Type / transmittable21.Type
  } = ???

def test22 =
  Resolution(
    element22(
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0),
      Resolution(element0), Resolution(element0)))

My “real” (not minimized code) has a few more parameters and takes ages to compile (did not finish yet after a several minutes), which makes me think that code in this shape maybe triggers some kind of exponential explosion in the type checker.

Expectation

Scala 2.13 compiles the code instantly. The expectation would be the same for Scala 3.

Note

FYI, I found #14224, which may or may not have the same root cause.

[Kordyjan]

I tried to reproduce that and it is hanging for me for a few minutes on the current main. This is something nasty.

[Kordyjan]

Oh, I see now! I lost the definition of element0 in my snippet. Without that value, it compiles much much longer before finally failing with a type error.

The correct case is also taking longer to compile but it is not that dramatic.

[pweisenburger]

I looked into this a bit more. It seems that isSubType is called with the following arguments:

tp1 = Delegating[?1.Type / ?2.Type / ... / ?15.Type / (?16 : Resolution[Delegating[Unit]])#Type]
tp2 = Delegating[?17.Type / ?18.Type / ... / ?31.Type / ?32.Type]

The ? are the skolems for the method arguments. For some reason that I do not fully understand, type-checking is really slow with all these skolems, in particular the isSubType call at https://github.com/lampepfl/dotty/blob/3.1.2/compiler/src/dotty/tools/dotc/core/TypeComparer.scala#L723. The skolems here are only used to select the Type type member. If, at this point, we resolve these type aliases, we end up with an isSubType check:

tp1 = Delegating[(param)1#Type / (param)2#Type / ... / (param)15#Type / (param)16#Type]
tp2 = Delegating[Aux[Delegating[Unit]] / Aux[Delegating[Unit]] / ... / Aux[Delegating[Unit]] / Aux[Delegating[Unit]]]

Type-checking this is as fast as you would expect.

Does it make sense to get rid of <skolem>.SomeAlias early on?

[odersky]

I checked that indeed every increase in element number by one gives twice as many subtype calls. (How?: I turned the inline value Stats.enabled on, compiled with -Ydetailed-stats and looked at the number of "total subtype" entries for various sizes of element.).

The reason, I believe is this: When testing equality A =:= B we test A <:< B and B <:< A. The program here has a deeply nested applied type of an invariant type constructor /. Comparing applied invariant types means testing corresponding type arguments for equality. So at each level we have a branch out factor of 2, for an overall exponential complexity.

[odersky]

Does it make sense to get rid of .SomeAlias early on?

This helps in the particular test case because then the two types that are compared hash-cons after dealiasing to the same type. But the fix in #15556 is more general.