Pathological (effectively non-terminating) compilation times of quote-matching multiple types #23317
Description
Compiler version
3.7.0
Minimized code
Compilation of the following effectively does not terminate:
macros9.scala
import scala.quoted.* def goImpl(using Quotes): Expr[Int] = List.empty[Type[?]] match case Nil => Expr(0) case '[t1] :: Nil => Expr(1) case '[t1] :: '[t2] :: Nil => Expr(2) case '[t1] :: '[t2] :: '[t3] :: Nil => Expr(3) case '[t1] :: '[t2] :: '[t3] :: '[t4] :: Nil => Expr(4) case '[t1] :: '[t2] :: '[t3] :: '[t4] :: '[t5] :: Nil => Expr(5) case '[t1] :: '[t2] :: '[t3] :: '[t4] :: '[t5] :: '[t6] :: Nil => Expr(6) case '[t1] :: '[t2] :: '[t3] :: '[t4] :: '[t5] :: '[t6] :: '[t7] :: Nil => Expr(7) case '[t1] :: '[t2] :: '[t3] :: '[t4] :: '[t5] :: '[t6] :: '[t7] :: '[t8] :: Nil => Expr(8) case '[t1] :: '[t2] :: '[t3] :: '[t4] :: '[t5] :: '[t6] :: '[t7] :: '[t8] :: '[t9] :: Nil => Expr(9) case _ => Expr(999)Additional measurements
I created a series of files macros1.scala, ..., macros9.scala, where the last one is above and the first one is
macros1.scala
import scala.quoted.* def goImpl(using Quotes): Expr[Int] = List.empty[Type[?]] match case Nil => Expr(0) case '[t1] :: Nil => Expr(1) case _ => Expr(999)I then timed the compilation times:
% for i in $(seq 9); do echo $i; time scalac macros$i.scala; done 1 scalac macros$i.scala 7.47s user 0.25s system 301% cpu 2.565 total 2 scalac macros$i.scala 8.19s user 0.27s system 307% cpu 2.754 total 3 scalac macros$i.scala 8.07s user 0.27s system 302% cpu 2.756 total 4 scalac macros$i.scala 8.45s user 0.28s system 301% cpu 2.899 total 5 scalac macros$i.scala 9.31s user 0.29s system 305% cpu 3.141 total 6 scalac macros$i.scala 11.40s user 0.36s system 276% cpu 4.254 total 7 scalac macros$i.scala 113.75s user 1.03s system 109% cpu 1:44.84 total 8 We can see a big jump between macros6.scala and macros7.scala (11.40s vs 113.75s).
Compilation of macros8.scala is still running after 25 minutes.