StackOverflowError in stripTypeVar

[TomasMikula]

Compiler version

3.3.1 3.3.2-RC3 3.4.0-RC4 3.4.1-RC1-bin-20240202-5850d2d-NIGHTLY

Self-contained code to reproduce

object StackOverflowTest {

  sealed trait Ev[T]

  enum PartialArgs[TC[_, _], A, B](using val inKind: Ev[A]):
    case Id[TC[_, _], A]()(using Ev[A]) extends PartialArgs[TC, A, A]
    case Fst[TC[_, _], A1, B1, Y]()(using Ev[(A1, Y)]) extends PartialArgs[TC, (A1, Y), (B1, Y)]

  enum TransferOpt[A1, A2, B1, B2]:
    case None[A1, A2]() extends TransferOpt[A1, A2, A1, A2]

  sealed trait Result[TC[_, _], J1, J2, L]
  object Result {
    case class Translucent[TC[_, _], J1, J2, K1, L](
      translucentBase: SemiTransparent[TC, K1, J2, L],
    ) extends Result[TC, J1, J2, L]
  }

  sealed trait SemiTransparent[TC[_, _], K1, K2, L]
  object SemiTransparent {
    case class RTotal[TC[_, _], K1, K2, L2, M1, M2](
      r: PartialArgs[TC, K2, L2],
      tr: TransferOpt[K1, L2, M1, M2],
    ) extends SemiTransparent[TC, K1, K2, (M1, M2)]
  }

  private def test[TC[_, _], J1, J2, K1, K2, L](
    args: PartialArgs[TC, (K1, K2), L],
    j2: Ev[J2],
    k2: Ev[K2],
  ): Result[TC, K1, K2, L] = {
    import PartialArgs.{Id, Fst}
    import Result.Translucent
    import SemiTransparent.RTotal

    given Ev[J2] = j2
    given Ev[K2] = k2

    args match
      case f: Fst[f, k1, l1, k2] =>
        summon[L =:= (l1, K2)]
        Translucent[TC, K1, K2, l1, L](
          RTotal/*[TC, l1, K2, K2, l1, K2]*/( // uncomment type args to make the code compile
            Id(), 
            TransferOpt.None()
          )
        )
  }
}

Original reproduction steps

(Apologies for not having a minimized example. Hoping someone would spot the bug just given the stack trace and code change that avoids/triggers the error.)

git clone https://github.com/TomasMikula/libretto.git
cd libretto
git checkout 7d673fe92de2faf64809bee8b25b906f907054cb
sbt typology/compile

You can further edit build.sbt to use any of the above Scala versions.

A workaround is to supply explicit type arguments in OpenTypeExpr.scala, line 147 (just uncomment them; see the diff triggering the error).

Output (click arrow to expand)

The output for Scala 3.3.1. The exact line numbers in the stack trace will differ for other versions. (The output is trimmed, as the full output does not fit the 65536 char limit of GitHub.) ```scala [info] compiling 29 Scala sources to /Users/tomas/tmp/libretto/typology/target/scala-3.3.1/classes ... java.lang.StackOverflowError while typechecking /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/OpenTypeExpr.scala Exception while compiling /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/inference/Labels.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/inference/Propagator.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/inference/TypeOps.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/kinds/Kind.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/kinds/KindN.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/kinds/Kinds.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/kinds/package.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/terms/Fun.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/terms/TypedFun.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/typeinfer/NonAbstractType.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/typeinfer/TypeInference.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/typeinfer/VarGen.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/AbstractTypeLabel.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/Label.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/Multiplier.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/Multipliers.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/OpenTypeExpr.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/PartialArgs.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/Routing.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/Type.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/TypeConstructor.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/TypeExpr.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/TypeFun.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/TypeTag.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/Types.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/toylang/types/package.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/types/package.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/util/Either3.scala, /Users/tomas/tmp/libretto/typology/src/main/scala/libretto/typology/util/State.scala [error] ## Exception when compiling 29 sources to /Users/tomas/tmp/libretto/typology/target/scala-3.3.1/classes [error] java.lang.StackOverflowError [error] dotty.tools.dotc.core.OrderingConstraint.typeVarOfParam(OrderingConstraint.scala:247) [error] dotty.tools.dotc.core.OrderingConstraint.instType(OrderingConstraint.scala:808) [error] dotty.tools.dotc.core.Types$TypeVar.instanceOpt(Types.scala:4780) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4833) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] dotty.tools.dotc.core.Types$TypeVar.stripTypeVar(Types.scala:4834) [error] (typology / Compile / compileIncremental) java.lang.StackOverflowError [error] Total time: 23 s, completed Feb 3, 2024, 11:08:30 AM ```

[odersky]

The stack trace seems to indicate that a type variable is (directly or indirectly) instantiated to itself.

Unfortunately the stacktrace does not tell us why and where that happens.

[Gedochao]

@TomasMikula do I understend correctly that it's a regression? Does it occur for versions earlier than 3.3.1? and yes, seems like we need a minimization for this.

[TomasMikula]

Hi @Gedochao, no, I'm not saying that this is a regression. It is new code that I have written with 3.3.1, and then tested with newer pre-release versions to check if by any chance it was already resolved.

[TomasMikula]

@odersky I have isolated a self-contained example (see the updated description). Surely it can be minimized further, but this is how far I got so far.

[odersky]

Thank you for producing the example! That should help.