Pathological (effectively non-terminating) compilation times of quote-matching multiple types

[TomasMikula]

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.