CODEWITHSUNDEEP
scalascala-macrosscala-3parser-combinators
jared jacobson
jared jacobson

Reputation: 159

Scala 3: why does `inline` fix stack overflow

I have this code that results in a stack overflow.

// Lexer.Token defined elsewhere
object BadParser extends Parsers {
  import Lexer.Token
  type Elem = Token
  private def PUNCT = Token.PUNCT

 

  private def parens[T](p: Parser[T]) = PUNCT("(") ~ p ~ PUNCT(")")

 

  def expr: Parser[Any] = parens(expr) | PUNCT(".")
}
class ParensTest extends AnyFlatSpec {
  def testBad(input: String) =
    val tokens = Lexer.scan(input)
    BadParser.expr(tokens)
  "bad parser" should "not recur forever but it does" in {
    testBad("((.))")
  }
}

that is weird enough as it is but it gets weirder. when I try inspecting the parens(expr) like this:

   def expr: Parser[Any] = log(parens(expr))("parens expr") | PUNCT(".")

there is no longer a stack overflow.

I decided to try inlining the parens function and the argument like this:

inline parens(inline p... and that also fixed it.

the confusion for me is that the docs on inline https://docs.scala-lang.org/scala3/guides/macros/inline.html say that inlining parameters shouldn't change the semantics of the function but it clearly does. What am I missing?

(my understanding of inline is that it forces the compiler to actually inline, not just give its best effort, and when you say the parameter is inline, it will inline the parameter instead of passing by value or reference)

Edit: I'm using the Scala Parser Combinator library

Upvotes: 0

Views: 127

Answers (2)

user-id-14900042
user-id-14900042

Reputation: 1284

By-name (also known as lazy evaluation) prevents infinite-recursion in this case. i.e.

  private def parens[T](p: => Parser[T]) = PUNCT("(") ~ p ~ PUNCT(")")

The argument of operator ~ is defined as by-name, so inlining would help you. However, it would not give nice result if too much call-site has been inlined.

Upvotes: 1

Gaël J
Gaël J

Reputation: 15050

You have an infinite recursion when writing:

def expr = parens(expr) | PUNCT(".")

expr is calling itself before being able to call parens.

Why does it go away when inlining?

The inlined code would be as if you had written the following:

def expr = (PUNCT("(") ~ expr ~ PUNCT(")")) | PUNCT(".")

Now, and this is a supposition as we don't have the full code, expr calls the ~ method first which I guess does not need to evaluate expr in your case.

Upvotes: 1

Related Questions