Possible regression in 2.9: @tailrec annotated method rejected by scalac

[scabug]

The following compiled with Scala 2.8.1:

@annotation.tailrec
def lazyFilter[E](s: Stream[E], p: E => Boolean): Stream[E] = s match {
  case h #:: t => if (p(h)) h #:: lazyFilter(t, p) else lazyFilter(t, p)
}

In 2.9.0 and 2.9.0.1, I get:

  error: could not optimize @tailrec annotated method lazyFilter: it contains a recursive call not in tail position

To my understanding, the method is tail recursive, as the first occurrence of "lazyFilter" is not a call, but a closure that is passed to cons.

I'm not sure if this only a bug in the evaluation of @tailrec, or if the 2.9 compiler really cannot apply tailrec optimization here anymore. In the latter case, it would affect the Stream class as well.

Could you please clarify about this.

Thanks.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-4649?orig=1
Reporter: Christoph Radig (cradig)
Affected Versions: 2.9.0

[scabug]

@paulp said:
You are correct. It only worked in 2.8.1 by accident, as this case was not considered at all. Tightening the general case scooped this up as well, but the closure should be excluded. You can see looking at the bytecode that it compiles to a jump in both versions.

[scabug]

@adriaanm said (edited on Jun 11, 2012 12:06:00 PM UTC):
Vlad, since you've spent some quality time in tail calls recently, could you please take care of suppressing the error. At least, if I understood correctly, the only actual call to lazyFilter is in tail position. The other occurrence is not a call.

[scabug]

@VladUreche said:
If by "quality time" you mean scratching my head and trying to figure out why the typer doesn't work as I expect, then yeah, I did plenty of that :))

Anyway, bug accepted :)

[SethTisue]

not fixed in Scala 3 (3.4.0-RC2) either

[som-snytt]

And if you wondered why this ticket is open but has a pos test, it's because in 2012, a "bunch" of tests were moved out of "pending" without changing the pending part. I added the option header in 2018 but did not notice that the annotation was commented out.

// scalac: -Xfatal-warnings
//
object Test {
  // @annotation.tailrec

[som-snytt]

It is not discriminating in detecting leftover calls:

object Test {
  var xs = List(42)
  @annotation.tailrec
  def f(i: Int): Int =
    if (i <= 0) i
    else {
      val g: Int => Int = f
      xs = xs.map(g)
      f(i - 1)
    }
}

also complains

not-tailrec.scala:8: error: could not optimize @tailrec annotated method f: it contains a recursive call not in tail position
      val g: Int => Int = f
                          ^

as does dotty.

So it's about user expectation:

    else if (i == 42) {
      val x = f(xs.head)
      x // really, you couldn't optimize that for me?
    }

It's not obvious to me what is expected to be obvious, such as the OP example. That is obviously tricky.

The dotty style guide says only use the annotation if there is a danger that unintended recursion could blow the stack.

The choice is either to warn about any possible recursion (that may introduce stack frames) or only self-recursion (which the optimization could possibly make safe). In other words, only warn about self-recursions because that is what you can do something about. Perhaps an additional lint could tack on other recursive references. (One could imagine a more powerful lint that warns about mutual recursion.)