`StackOverflowError` while compiling code using an equivalent to `shapeless.ops.hlist.LiftAll`

[mrdziuban]

Compiler version

3.3.0-RC3, also happens on 3.2.2

Minimized code

Please excuse the fact that this code is fairly meaningless, it's a very trimmed down version of a pattern (that actually has meaning) in my codebase.

https://scastie.scala-lang.org/mrdziuban/IHV2q8voTuSKVOSw3WP0Ug/1

trait LiftAll[F[_], T] {
  type Out
  def instances: Out
}

object LiftAll {
  type Aux[F[_], T, Out0] = LiftAll[F, T] { type Out = Out0 }

  inline given tupleInst[F[_], T <: Tuple]: Aux[F, T, Tuple.Map[T, F]] =
    new LiftAll[F, T] {
      type Out = Tuple.Map[T, F]
      lazy val instances = compiletime.summonAll[Tuple.Map[T, F]]
    }

  def apply[F[_], T](using l: LiftAll[F, T]): Aux[F, T, l.Out] = l
}

sealed abstract class Rel[T, TS] {
  final type Type = T
  final type Types = TS
}

object Rel {
  case object I extends Rel[Int, String *: Boolean *: EmptyTuple]
  case object S extends Rel[String, Int *: Boolean *: EmptyTuple]
  case object B extends Rel[Boolean, Int *: String *: EmptyTuple]
}

sealed trait Test[A, B]

object Test {
  given inst[A, Types, B]: Test[Rel[A, Types], B] =
    new Test[Rel[A, Types], B] {}

  def test[T, TS](rel: Rel[T, TS]) =
    rel match {
      case r: Rel.I.type => LiftAll[λ[a => Test[Rel[r.Type, r.Types], a]], r.Types]
      case r: Rel.S.type => LiftAll[λ[a => Test[Rel[r.Type, r.Types], a]], r.Types]
      case r: Rel.B.type => LiftAll[λ[a => Test[Rel[r.Type, r.Types], a]], r.Types]
    }
}

Output

Recursion limit exceeded.
Maybe there is an illegal cyclic reference?
If that's not the case, you could also try to increase the stacksize using the -Xss JVM option.
For the unprocessed stack trace, compile with -Yno-decode-stacktraces.
A recurring operation is (inner to outer):

  subtype [X0] >:
  Playground.Test[
    Playground.Rel[Playground.Rel.I.Type, Playground.Rel.I.Types], X0]
 &
  Playground.Test[
    Playground.Rel[Playground.Rel.S.Type, Playground.Rel.S.Types], X0]
 <:
  Playground.Test[
    Playground.Rel[Playground.Rel.I.Type, Playground.Rel.I.Types], X0]

  Playground.Test[
    Playground.Rel[Playground.Rel.S.Type, Playground.Rel.S.Types], X0] <:< [a] =>>
  Playground.Test[
    Playground.Rel[Playground.Rel.B.Type, Playground.Rel.B.Types], a]

I've tried increasing the stack size as suggested, all the way up to -Xss50M.

When I compile with -Yno-decode-stacktraces I get a stack trace. GitHub tells me the full stack trace is too long to include in the description here but you can view it here: https://gist.github.com/mrdziuban/9d60341f5c2173bd768996da4589af12. Here's a condensed version:

java.lang.StackOverflowError
  at dotty.tools.dotc.core.Types$VariantTraversal.stopBecauseStaticOrLocal(Types.scala:5539)
  at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5656)
  at dotty.tools.dotc.core.TypeComparer$$anon$1.apply(TypeComparer.scala:266)
  at dotty.tools.dotc.core.Types$TypeMap.op$proxy18$1(Types.scala:5658)
  at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5658)
  at dotty.tools.dotc.core.TypeComparer$$anon$1.apply(TypeComparer.scala:266)
  at dotty.tools.dotc.core.Types$TypeMap.op$proxy17$1(Types.scala:5625)
  at dotty.tools.dotc.core.Types$TypeMap.mapArgs(Types.scala:5625)
  at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5662)
  at dotty.tools.dotc.core.TypeComparer$$anon$1.apply(TypeComparer.scala:266)
  at dotty.tools.dotc.core.Types$TypeMap.op$proxy17$1(Types.scala:5625)
  at dotty.tools.dotc.core.Types$TypeMap.mapArgs(Types.scala:5625)
  at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5662)
  at dotty.tools.dotc.core.TypeComparer$$anon$1.apply(TypeComparer.scala:266)
  at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5727)
  at dotty.tools.dotc.core.TypeComparer$$anon$1.apply(TypeComparer.scala:266)
  at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda(Types.scala:5638)
  at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5665)
  at dotty.tools.dotc.core.TypeComparer$$anon$1.apply(TypeComparer.scala:266)
  at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5672)
  at dotty.tools.dotc.core.TypeComparer$$anon$1.apply(TypeComparer.scala:266)
  at dotty.tools.dotc.core.TypeComparer.monitoredIsSubType$1(TypeComparer.scala:269)
  at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1455)
  at dotty.tools.dotc.core.TypeComparer.compareTypeLambda$1(TypeComparer.scala:723)
  at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:731)
  at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:539)
  at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:399)
  at dotty.tools.dotc.core.TypeComparer.monitoredIsSubType$1(TypeComparer.scala:273)
  at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1455)
  at dotty.tools.dotc.core.TypeComparer.compareTypeLambda$1(TypeComparer.scala:723)
  at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:731)
  at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:539)
  at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:399)
  at dotty.tools.dotc.core.TypeComparer.monitoredIsSubType$1(TypeComparer.scala:273)
  at dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1455)
  at dotty.tools.dotc.core.TypeComparer.compareTypeLambda$1(TypeComparer.scala:723)
  at dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:731)
  at dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:539)
  at dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:399)
  ...

Expectation

The code would compile successfully as it does in scala 2 -- https://scastie.scala-lang.org/mrdziuban/WlK9X64oSJOFNyzrSP5FBA/3

Strangely, if I comment out just one of the case objects in object Rel and the corresponding case statement in def test then everything compiles just fine. Not sure if this is actually relevant to the underlying issue but wanted to mention it in case it's helpful for debugging.

[mrdziuban]

I was able to minimize this a bit:

https://scastie.scala-lang.org/mrdziuban/IHV2q8voTuSKVOSw3WP0Ug/19

expand code

trait LiftAll[F[_], T] {
  type Out
  def instances: Out
}

object LiftAll {
  inline def apply[F[_], T <: Tuple]: LiftAll[F, T] { type Out = Tuple.Map[T, F] } =
    new LiftAll[F, T] {
      type Out = Tuple.Map[T, F]
      lazy val instances = compiletime.summonAll[Tuple.Map[T, F]]
    }
}

sealed trait Test[A, B]

object Test {
  given inst[A, B]: Test[A, B] = new Test[A, B] {}

  def test =
    ((): Matchable) match {
      case _: Int => LiftAll[Test[Int, *], String *: Boolean *: EmptyTuple]
      case _: String => LiftAll[Test[String, *], Int *: Boolean *: EmptyTuple]
      case _: Boolean => LiftAll[Test[Boolean, *], Int *: String *: EmptyTuple]
    }
}

A few other things that may be helpful for debugging:

1. The error doesn't happen when using compiletime.summonAll directly instead of LiftAll
2. The error doesn't happen when trait Test only has one type parameter and the LiftAll calls look like LiftAll[Test, String *: Boolean *: EmptyTuple]
3. The error doesn't happen if I add a type annotation of : Any to def test

[mrdziuban]

This appears to be fixed in Scala 3.5.2, but still happens in versions <= 3.5.1. Feel free to close if that's considered a good enough fix

[WojciechMazur]

Bisect shows it was fixed in f2829c3

@prolativ Probably it can be closed after backporting or rejecting backport to the LTS