Skip to content

Performance regression in 16463.scala #16463

Closed
@kubukoz

Description

@kubukoz

Compiler version

3.2.1

Minimized code

//> using scala "3.2.1"

import scala.compiletime.ops.int._

object TupleOps {
  import Tuple._

  type Reduce[T <: NonEmptyTuple, F[_, _]] =
    Fold[Tuple.Tail[T], Tuple.Head[T], F]

  type Maximum[T <: NonEmptyTuple] = Reduce[
    T,
    [A, B] =>> (A, B) match {
      case (Int, Int) => A Max B
    }
  ]

  type IndexOfRec[T <: Tuple, Elem, I <: Int] = Tuple.Elem[T, I] match {
    case Elem => I
    case _    => IndexOfRec[T, Elem, I + 1]
  }

  type IndexOf[T <: Tuple, Elem] = IndexOfRec[T, Elem, 0]

  type DropLargest[T <: NonEmptyTuple] =
    T IndexOf Maximum[T] match {
      case Int =>
        (
          (T Take (T IndexOf Maximum[T])) Concat
          (T Drop ((T IndexOf Maximum[T]) + 1))
        ) *: EmptyTuple
    }

  type BubbleSort[T <: Tuple] = T match {
    case EmptyTuple => EmptyTuple
    case NonEmptyTuple =>
      BubbleSort[DropLargest[T]] Concat (Maximum[T] *: EmptyTuple)
  }
}

object demo extends App {
  println(compiletime.constValue[TupleOps.BubbleSort[(1, 2)]])
}

Output

Compiles forever. I'm able to get it to terminate with a recursion overflow if I specify really low stack, e.g. -Xss256K:

scala-cli compile . --bloop-java-opt -Xss256K
Starting compilation server
Compiling project (Scala 3.2.1, JVM)
dotty.tools.dotc.core.RecursionOverflow:
Error compiling project (Scala 3.2.1, JVM)
dotty.tools.dotc.core.RecursionOverflow:
Error: Unexpected error when compiling project_f0e8bc45bf: ''
Compilation failed

Expectation

Successfully compiles or fails compilation in a couple seconds at most

Metadata

Metadata

Assignees

Labels

Type

No type

Projects

No projects

Milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions