Solved: Scala 3 quotes: how to solve this StackOverflowError?

hmf · December 13, 2022, 5:38pm

I implemented a recursive power version using macro quotes as a simpler example to show an issue I have. Here is the macro’s code:

  transparent inline def power2(a: Int, b:Int): Any = ${ power2Impl('a,'b) }

  def power2Impl(a: Expr[Int], b: Expr[Int])(using q1: Quotes): Expr[Int] =
    b match 
      case '{0} => '{1}
      case '{ $expr: tpe } => 
        println(s"b : ${b.show} = ${b.value}")
        println(s"b : ${Type.show[tpe]} = ${b.value}")
        '{
          val nb = $b-1
          val next = ${ power2Impl(a, 'nb)}
          $a * next
        }

and I invoke it so:

    val p2 = data.Macros3.power2(2,2)

and get this compile-time error:

    error]     |Exception occurred while executing macro expansion.
    [error]     |java.lang.StackOverflowError
    [error]     |	at scala.quoted.runtime.impl.Scope.root(SpliceScope.scala:23)
    [error]     |	at scala.quoted.runtime.impl.Scope.root$(SpliceScope.scala:13)
    [error]     |	at scala.quoted.runtime.impl.SpliceScope.root(SpliceScope.scala:36)
    [error]     |	at scala.quoted.runtime.impl.Scope.root(SpliceScope.scala:23)
    [error]     |	at scala.quoted.runtime.impl.Scope.root$(SpliceScope.scala:13)
    [error]     |	at scala.quoted.runtime.impl.SpliceScope.root(SpliceScope.scala:36)
    [error]     |	at scala.quoted.runtime.impl.Scope.root(SpliceScope.scala:23)
    [error]     |	at scala.quoted.runtime.impl.Scope.root$(SpliceScope.scala:13)
    [error]     |	at scala.quoted.runtime.impl.SpliceScope.root(SpliceScope.scala:36)
    [error]     |	at scala.quoted.runtime.impl.Scope.root(SpliceScope.scala:23)

So why is it not stopping when it should? The type checker (via IDE) reports that nb and next are both Int. So I added the print lines to see what is happening and get:

    b : 2 = Some(2)
    b : 2 = Some(2)
    b : nb = None
    b : nb.type = None
    b : nb = None
    b : nb.type = None
    b : nb = None
    b : nb.type = None
    b : nb = None

The lines are duplicated just to check the type. Note that at the start I have Some(2), but then after the 1st subtraction, the compiler seems to generate a None. I am expecting a Some(1). I assume the Some(0) would match the first case.

Can anyone tell me what is happening and how to solve this?

TIA

hmf · December 14, 2022, 11:38am

Alternate working version:

  def power2Impl(a: Expr[Int], b: Expr[Int])(using q1: Quotes): Expr[Int] =
    import quotes.reflect.*
    b match 
      case '{0} => '{1}
      case '{1} => a
      case '{ $expr: Int } => 
        println(s"b(a) : ${b.show} = ${b.value}")
        val next_b: Expr[Int] = '{$expr - 1}
        next_b.value match
          case None => 
            report.errorAndAbort("power2Impl: Unexpected value")
          case Some(0) => 
            // a^1 = a * a⁰
            a
          case Some(1) => 
            // a^2 = a * a¹
            '{$a*$a}
          case Some(x) => 
            // a^b = a * a^x
            println(s"Recursing on Some($x)")
            val next = power2Impl(a, next_b)
            println(s"next = ${next.value}")
            '{$a * $next}

The problem is that in the previous version, the line:

val nb = $b-1

is code that will be generated, and the value is therefore not available when we splice :

${ power2Impl(a, 'nb)}

hence the value None.

hmf · December 19, 2022, 9:19am

The problem is explained in detail by @nicolasstucki. He was kind enough to provide a best-practice example. Much appreciated. Here is the link:

github.com/lampepfl/dotty

Expression from a quote inconsistently available to splicing

opened 09:16AM - 15 Dec 22 UTC

closed 08:51AM - 19 Dec 22 UTC

hmf

itype:invalid area:metaprogramming:quotes

## Compiler version Scala version 3.2.1 ## Minimized code While explori…ng macro quotes, an **incorrect** code snippet seems to exhibit inconsistent compilation and may provide a possible opportunity to detect and flag an error. The code is below. Also available in [scastie](https://scastie.scala-lang.org/x3Rn74eqSD2avaFL7L3imw). ```Scala import scala.quoted.* transparent inline def power5(a: Int, b:Int): Any = ${ power5Impl('a,'b) } def power5Impl(a: Expr[Int], b: Expr[Int])(using q1: Quotes): Expr[Int] = import quotes.reflect.* b match case '{0} => println(s"b(0) : ${b.show} = ${b.value}") '{1} case '{1} => println(s"b(1) : ${b.show} = ${b.value}") a case '{ $expr: tpe } => println(s"b(a) : ${b.show} = ${b.value}") println(s"b(b) : ${Type.show[tpe]} = ${expr.value}") val test: Expr[Int] = '{$b - 1} println(s"test : ${test.show} = ${test.value}") // No terminal match on 0 or 1. Stack overflow // val testOut: Expr[Int] = power5Impl(a, test) // println(s"testOut : ${testOut.show} = ${testOut.value}") '{ val nb = $b - 1 // Incorrect exponent value. Always None. No terminal match on 0 or 1. Stack overflow // This is correct. nb has not been calculated val next = ${ power5Impl(a, 'nb)} // No terminal match on 0 or 1 // Matches and stops ok // val next = ${ power5Impl(a, Expr(1))} // Matches and stops ok // val next = ${ power5Impl(a, '{1})} // Correct exponent value. No terminal match on 0 or 1. Stack overflow // val next = ${ power5Impl(a, test)} $a * next } ``` ## Output As is, the code will, as it should, cause stack overflow. The output is: ```scala b(a) : 2 = Some(2) b(b) : 2 = Some(2) test : 2.-(1) = Some(1) b(a) : nb = None b(b) : nb.type = None test : nb.-(1) = None b(a) : nb = None b(b) : nb.type = None test : nb.-(1) = None b(a) : nb = None b(b) : nb.type = None test : nb.-(1) = None ``` The issue is that the value for `nb` is not available when we splice the call to `power5Impl(a, 'nb)`. Hence the value `None`. If we comment this line and remove the comment from the line: ```scala // val next = ${ power5Impl(a, test)} ``` then we also get a stack overflow. This time however, the value is updated correctly. The overflow occurs because matching fails and may be due to another issue (see #16521). ## Expectation In the case of the `nb` variable being used when unavailable, maybe this can be detected and flagged by compiler? If so a compilation may issue an error or at least a warning. On this next issue, I am unsure. In regards to the `next` that uses the `test` value. Intuitively it seems correct to expect this to be available when splicing. However, after seeing what the issue is with `nb`, I would expect it to behave just like the `nb`. After all both `nb` and `test` are the same quote. It seems like the compiler calculates `test` and makes it available, unlike the `nb`. Maybe the `nb` should also be made available?