StackOverflow in dotc when returning/manipulating big Term/Expr

[Iltotore]

Compiler version

3.2.0 and 3.3.0-RC3

Minimized code

test.sc

//> using scala "3.2.2"
//> using file "ScalaQuotes.scala"

def nonWhitespace(char: Char): Boolean = !char.isWhitespace

println(forallChars(
    value = "1SUT8Dv40Ay78zl26xJJrpkP1cDPsLk1V4eVoRQuGceS7hIo8gmKxbAVWdn15lPYQ1fcifRaTINXg6tDH4WNhxBLbgF+Yqd3ouP7kS978LlFUZq3cAC8UAekvIcnJwzxaqsHBG7+mC1Adk3TqlJt+5JELo5r8apwChkxRzeFaybcRD6xUmb8GGJj/FTpatATVAMh1SrkQsaJhucByHxxt9EVUT2GaITsebwdyTRxtGnam5m+ZrspaAkvXCwXgvfVwZEN5wbvwU5dcZ5279KCPZY/HnW9s8SlS8qbTst5z248l0cALe+hyNkNC1Y05u3uEUlhsJ1AD0MLCjBlroHNjvWrWRDoz93qEbakuPb9/Rr0Z6l09V6exmJ2PXGnSUtV1hYo2DAQbOklQZdEZBkhsY4wirsCTKhOainF5UvtLljHDtap9UaMXtoT6g/gazq1SUT8Dv40Ay78zl26xJJrpkP1cDPsLk1V4eVoRQuGceS7hIo8gmKxbAVWdn15lPYQ1fcifRaTINXg6tDH4WNhxBLbgF+Yqd3ouP7kS978LlFUZq3cAC8UAekvIcnJwzxaqsHBG7+mC1Adk3TqlJt+5JELo5r8apwChkxRzeFaybcRD6xUmb8GGJj/FTpatATVAMh1SrkQsaJhucByHxxt9EVUT2GaITsebwdyTRxtGnam5m+ZrspaAkvXCwXgvfVwZEN5wbvwU5dcZ5279KCPZY/HnW9s8SlS8qbTst5z248l0cALe+hyNkNC1Y05u3uEUlhsJ1AD0MLCjBlroHNjvWrWRDoz93qEbakuPb9/Rr0Z6l09V6exmJ2PXGnS",
    predicate = nonWhitespace
))

ScalaQuoted.scala

//> using scala "3.2.2"

import scala.quoted.*

inline def forallChars(value: String, predicate: Char => Boolean): Boolean = ${forallCharsImpl('value, 'predicate)}

def forallCharsImpl(expr: Expr[String], exprPredicate: Expr[Char => Boolean])(using Quotes): Expr[Boolean] =
  import quotes.reflect.*
  
  expr.value match
    case Some(value) =>
      value
        .map(c => Literal(CharConstant(c)))
        .map(c => Apply(Select.unique(exprPredicate.asTerm, "apply"), List(c)))
        .foldLeft[Term](Literal(BooleanConstant(true)))((t, c) => Apply(Select.unique(t, "&&"), List(c)))
        .asExprOf[Boolean]

      Expr(true)

    case None => ???

Output (click arrow to expand)

This code compiles but when I return the first expression (aka removing the Expr(true) as line 18):

//> using scala "3.2.2"

import scala.quoted.*

inline def forallChars(value: String, predicate: Char => Boolean): Boolean = ${forallCharsImpl('value, 'predicate)}

def forallCharsImpl(expr: Expr[String], exprPredicate: Expr[Char => Boolean])(using Quotes): Expr[Boolean] =
  import quotes.reflect.*
  
  expr.value match
    case Some(value) =>
      value
        .map(c => Literal(CharConstant(c)))
        .map(c => Apply(Select.unique(exprPredicate.asTerm, "apply"), List(c)))
        .foldLeft[Term](Literal(BooleanConstant(true)))((t, c) => Apply(Select.unique(t, "&&"), List(c)))
        .asExprOf[Boolean]

    case None => ???

The compiler crashes with the following StackOverflowError:

Stacktrace

Error: Encountered a StackOverflowError coming from the compiler. You might need to restart your Bloop build server:
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:94)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1406)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1412)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1406)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1412)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1406)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1412)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1406)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1412)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1406)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1412)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1406)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1412)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1406)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1412)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1406)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1412)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
dotty.tools.dotc.ast.Trees$Instance$TreeMap.transform(Trees.scala:1406)
dotty.tools.dotc.ast.TreeTypeMap.transform(TreeTypeMap.scala:145)
etc...

If I try to do something with the generated Term/Expr (like calling show), it crashes with the same error.

[sjrd]

I would say this one is on you. You're creating a huge code tree for apparently no good reason. IIUC, you are basically unrolling a loop. Unrolling a loop iteration more than a small power of two times (perhaps 8) is usually going to be detrimental to performance due to code cache misses and things like that.

I suggest you only perform that kind of unrolling of the input string is small.

[Iltotore]

I would say this one is on you. You're creating a huge code tree for apparently no good reason.

This is an example. The "useful" code throwing this error is here. It's a type refinement system which checks whenever possible (and allowed) inputs/constraints at compile-time. The goal is to generate something like f(firstChar) && f(second) && ... f(lastChar) which will get inlined (if f is inline) to true or false at compile-time. Note that I cannot apply f directly in my macro because I cannot get the value of such thing as Expr[A => Boolean].

The weird thing is the fold/maps do not cause the error but returning the generated value does. Is there a workaround I can use? Note that quoting does not work too and throw the SO earlier in the fold.

[nicolasstucki]

The issue is that f(firstChar) && f(second) && ... f(lastChar) is constructing a tree that is O(n) deep where n is the length of the value. You could try a divide an conquer approach to make the depth O(log n).

For example:

def forallCharsImpl(expr: Expr[String], exprPredicate: Expr[Char => Boolean])(using Quotes): Expr[Boolean] =
  import quotes.reflect.*

  expr.value match
    case Some(value) =>
      val predicates: List[Expr[Boolean]] = value
        .map(c => Literal(CharConstant(c)))
        .map(c => Apply(Select.unique(exprPredicate.asTerm, "apply"), List(c)).asExprOf[Boolean])
        .toList
      all(predicates)
    case None => ???

def all(predicates: List[Expr[Boolean]])(using Quotes): Expr[Boolean] =
  predicates match
    case Nil => Expr(true)
    case x :: Nil => x
    case x :: y :: Nil => '{ $x && $y }
    case _ =>
      val (left, right) = predicates.splitAt(predicates.length / 2)
      all(List(all(left), all(right)))

This does change the evaluation order of the &&. But if we assume that they will all be constant-folded it will not matter.

[nicolasstucki]

If you want to make f beta-reduce you will need need to inline it.

inline def forallChars(inline value: String, inline predicate: Char => Boolean): Boolean = ${forallCharsImpl('value, 'predicate)}

You could also beta-reduce during macro expansion to allow further optimization

        .map(c => Expr.betaReduce(Apply(Select.unique(exprPredicate.asTerm, "apply"), List(c)).asExprOf[Boolean]))

After this you may have Expr(true) or Expr(false) for which you can recover the value and then compute the && in the macro itself. The the macro can just generate Expr(true) or Expr(false).

[nicolasstucki]

Also seems that you do not need to use quotes.reflect.

- c => Apply(Select.unique(exprPredicate.asTerm, "apply"), List(Literal(CharConstant(c)))).asExprOf[Boolean]
+ c => '{ $exprPredicate.appy(${Expr(c)}) }

or just '{ $exprPredicate(${Expr(c)}) }

[nicolasstucki]

I discovered a bug that blocks beta-reduction of this example in some cases. See #17227.

[Iltotore]

For my use case I cannot use quoting/splicing directly due to a wrong interaction with inline (I think I should minimize the example and maybe report it a day) but using beta reduction maybe I would no longer need to manipulate the Term AST.

Also, does beta reduction works for custom traits/typeclasses?

Anyway, thank for the explanations !

[Iltotore]

It works like a charm. I guess I can now close this issue.