@tailrec and nested definitions

[LucySMartin]

Compiler version

3.4.0
(also validated on near latest local build 3.5.0-RC1-bin-SNAPSHOT-nonbootstrapped-git-9a5b9b4

Minimized code

This compiles:

  @tailrec
  def foo(): Unit =
    def bar(): Unit =
      if (???)
        foo()
      else
        bar()
    bar()

This does not:

  @tailrec
  def foo(): Unit =
    def bar(): Unit =
      if (???)
        foo()
    bar()

Output

These should no compile, as there are no tail recursive calls within the outer @tailrec annotated block. It has erroneously detected that this is ok, due to the rewrite of the inner bar method. This should not compile, and if this were not annotated with @tailrec, the outer tailLabel should not be generated.

Looking into the one that does compile, it generates an unutilised label testLabel2[Unit]: , and fails to warn about having no tail
l recursion optimised calls on the to level method:

    @tailrec def foo(): Unit =
      {
        while <empty> do 
          tailLabel2[Unit]: 
            return
              {
                def bar(): Unit =
                  {
                    while <empty> do 
                      tailLabel1[Unit]: 
                        return
                          if ???() then Test.foo() else 
                            (return[tailLabel1] ()):Unit
                  }
                bar()
              }
      }

Expectation

For the behaviour between these two (weather this is an acceptable place to recur or not) to be consistent between these cases - or in the alternative - to support multi tiered tail recursion.

Notes

This compiles (and indeed rewrites to a loop) if the inner method is declared as inline. Potentially a rule that within annotated @tailrec methods, any inner methods that call the top level method are handled as inline for simple uses directly within this method?

I was having a play around, and while complex, it does look feasible that we could have some sort of rewrite that processes this as a single larger rewrite. What would people thing of optimiseing to something like this:

import scala.annotation.tailrec
import scala.util.boundary
import scala.util.boundary.break

object Test extends App {
    
  //println(a(0))
  println(a_tr(0))

  var count = 0

  def f(tNum: Int): Boolean = {
    count = count + 1
    if (count > 100000) {
      throw new Exception("Infinitely looping")
    }
    tNum == 4 || tNum == 1
  }

  @tailrec
  def a(i: Int): Int = {
    @tailrec
    def b(j: Int): Int = {
      if (f(1)) {
        a(j + 1)
      } else if (f(2)) {
        b(j + 1)
      } else {
        j
      }
    }

    if (f(3)) {
      a(i + 1)
    } else if (f(4)) {
      b(i + 1)
    } else {
      i
    }
  }

 //identical to a, but with tail recursion logic applied
  def a_tr(i: Int): Int = {
    class AExit
    class ATail

    var aRes: Int | Null = null

    boundary[AExit] {
      var aIState = i
      while (true) {
        boundary[ATail] {
          while (true) {
            def b(j: Int): Int = {
              var bJState = i
              while (true) {
                if (f(1)) {
                  aIState = bJState + 1
                  break(new ATail)
                } else if (f(2)) {
                  bJState = bJState + 1
                } else {
                  aRes = bJState
                  break(new AExit())
                }
              }
              ???
            }

            if (f(3)) {
              aIState = aIState + 1
            } else if (f(4)) {
              b(aIState + 1)
            } else {
              aRes = aIState
              break(new AExit)
            }
          }
          ???
        }
      }
      ???
    }

    aRes.nn
  }

}

[LucySMartin]

I had a play with nesting re-writes.
Realised that in my big rewrite above, there would be obvious issues should the method b in the longer example above be lifted and then run outside of any call to a - appreciating now that would be a high complexity approach.

Would be keen to here thoughts on automatically inlining calls to sub-methods in the tail position in cases where it calls the parent method.
so something like:

  def a(i: Int): Unit =
    def b(i: Int): Unit =
      ???
      a(i)
    if (???)
      b(i) // not inlined
      ???
    else
      ???
      b(i) // inlined

In the alternative, is anybody clear as to if the following should compile or not - I think defining this one would inform all the others:

  @tailrec 
  def foo(i: Int): Unit =
    def bar(j: Int) =
      ???
      foo(j)
      ???
    if (???) 
      foo(i + 1)
    else
      bar(i)

In this case, there are direct calls from foo to foo which can be tail optimised, but indirect calls (via bar) that are not tail-optimised. If someone with more involvement with intent of this than me can direct on intent of this case, I can attempt to standardise in such a way to have the original two samples have consistent behaviour.

[sjrd]

I don't think we want to automate inlining for the purpose of allowing tail calls. At best we could augment the @tailrec-emitted error message to tell the user to consider marking the inner method as inline, but it definitely should not be automatic.

[LucySMartin]

Am I correct in reading into the suggestion we augment the error message in this case, that the last example I posted should not compile?
I'm realising that if bar was top level as opposed to nested inside of foo this clearly should compile - even though you could easily get a stack overflow. I'm coming around to the idea that a non tail call from inside an inner method is potentially not enough to fail compilation, and the original bug should be erroring due to having no tail calls, not due to having a call in non tail position (although flagging this (when not @inline onto the error or as a warning would seem positive)).

If we agree weather or not my last sample above should compile despite the non tail indirect call - Ill have a bash at that at some point.

[sjrd]

If we agree weather or not my last sample above should compile despite the non tail indirect call - Ill have a bash at that at some point.

Yes the last example should indeed compile.

(When evaluating @tailrec behavior, it helps to remember that Scala implements self tail-recursive calls, not arbitrary tail calls.)

[LucySMartin]

I'm generally aware of the level of recursion, I was just a tad confused as to how the concept of self would refer to arbitrary children. Ill rephrase the issue description to more accurately point at the real issue, then have a bit of a poke when I get free time.

[som-snytt]

The Scala 2 ticket I take as asking for either rewrite of local methods or error (but not silence) is scala/bug#8767

I assumed it would just error, but I'll take a lead from whatever solution is devised here.

[LucySMartin]

Either erroring or ignoring (potentially with a warn) are fairly simple. A rewrite is not always possible, for example if b is defined, then passed into a pre compiled method, rather than being called directly.

The example in the scala 2 ticket is very different - its two separate methods that call each other - that example looks like either implementing non self tail recursion, or solving the halting problem, neither of which I belive we wish to attempt here.

Our example here is where the second method is a sub method of the first, and we currently have an example which clearly incorrectly compiles (as it has no recursive calls at all). Main focus is on preventing that, but this does open up the question about nested methods.

[LucySMartin]

Above we disscussed the following:

  @tailrec 
  def foo(i: Int): Unit =
    def bar(j: Int) =
      ???
      foo(j)
      ???
    if (???) 
      foo(i + 1)
    else
      bar(i)

The immediate feedback was that this should compile, due to the difference between self-tail recursion and full tail recursion.
If we consider the following case where the inner method is implicit rather than explicit, I assume that in this case we should not compile?

  def bar(x: => Int) = 1
  @tailrec 
  def foo(i: Int): Unit =
    if (???) 
      foo(i + 1)
    else
      bar{
        ???
        foo(i + 1)
        ???
      }

In this case the recursive call is in implicit rather than explicit inner method - but this is obviously a very subtle difference from a technical perspective.
Honestly, I think that the principle of least surprise would be that we stick to a strict rule that any calls from within the physical text of the method that are not rewritten lead to this failure.
Potentially we could then talk about something like @allowNonTailrec for cases like where an inner method is OK to call its outer method (which would not be tail recursive) - in a separate task.

[LucySMartin]

Updated the PR - but I am not sure on having such a difference between explicit and implicit inner methods - it just feels unclean to me.