PostTyper: exponential compile time with chained transparent inline macro operations

[soronpo]

(Minimization and ticket created by AI)

Compiler version

3.7.1 (also reproducible on 3.8.x nightlies)

Minimized code

Three files, compiled in order:

Wrapper.scala:

class Wrapper(val value: Int)

MacroHelper.scala:

import scala.quoted.*

object MacroHelper:
  transparent inline def add[L, R, Out](
      inline lhs: L,
      inline rhs: R
  ): Out = ${ addMacro[L, R, Out]('lhs, 'rhs) }

  private def addMacro[L: Type, R: Type, Out: Type](
      lhs: Expr[L],
      rhs: Expr[R]
  )(using Quotes): Expr[Out] =
    '{
      val l = $lhs.asInstanceOf[Wrapper].value
      val r = $rhs.asInstanceOf[Wrapper].value
      new Wrapper(l + r).asInstanceOf[Out]
    }

Main.scala:

object Ops:
  extension (inline lhs: Wrapper)
    transparent inline def +(inline rhs: Wrapper): Wrapper =
      MacroHelper.add[Wrapper, Wrapper, Wrapper](lhs, rhs)

@main def test(): Unit =
  import Ops.*
  val a = Wrapper(1)
  // Adjust chain length to observe scaling:
  val result = a + a + a + a + a + a + a + a + a + a + a // 10 additions
  println(result.value)

Compile with:

scalac Wrapper.scala
scalac MacroHelper.scala
scalac -Yprofile-enabled Main.scala   # observe posttyper phase time

Output

PostTyper phase time grows exponentially with the number of chained + operations:

Additions	PostTyper time
5	85ms
8	397ms
10	1.0s
12	4.0s
15	~90s (measured)

Each additional + roughly doubles the compile time. 20 additions would take hours.

Expectation

Compile time should scale linearly (or at most quadratically) with the number of chained operations, not exponentially.

Analysis

The root cause is in PostTyper.scala (line 568 on main):

case tree @ Inlined(call, bindings, expansion) if !tree.inlinedFromOuterScope =>
  val pos = call.sourcePos
  CrossVersionChecks.checkRef(call.symbol, pos)
  withMode(Mode.NoInline)(transform(call))                    // ← expensive, result DISCARDED
  val callTrace = Inlines.inlineCallTrace(call.symbol, pos)(using ctx.withSource(pos.source))
  cpy.Inlined(tree)(callTrace, transformSub(bindings), transform(expansion)(using inlineContext(tree)))

transform(call) re-transforms the full call tree (running checkBounds, normalizeTypeArgs, etc. on any TypeApply inside it), but the result is thrown away — the next line computes callTrace (a minimal Ident) and uses that instead.

When transparent inline operations are chained (a + a + a + ...), each Inlined node's call field contains the full expansion of all previous operations (because inline parameters carry the entire previous tree into the macro's call field). The call tree size grows exponentially with chain length. Since transform(call) traverses this entire tree — encountering nested Inlined nodes that each trigger their own transform(call) — the total work grows exponentially.

Suggested fix

The transform(call) on line 568 can be removed entirely, since:

1. Its result is immediately discarded (not used in the output tree)
2. The side-effecting check it covers (CrossVersionChecks.checkRef) is already performed on the line above (line 567)
3. Any checks on the expansion's contents are covered by transform(expansion) on line 570

Alternatively, if there are side effects within transform(call) that are intentionally needed (beyond checkRef), they could be performed on just the top-level call symbol rather than recursively transforming the entire call tree.