Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
scabug opened this issue May 26, 2011 · 7 comments · May be fixed by scala/scala#10723
Open

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

scabug opened this issue May 26, 2011 · 7 comments · May be fixed by scala/scala#10723
Assignees
Milestone

Comments

@scabug
Copy link

scabug commented May 26, 2011

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
Copy link
Author

scabug commented May 26, 2011

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

@scabug
Copy link
Author

scabug commented Jun 11, 2011

@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
Copy link
Author

scabug commented Jun 11, 2012

@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
Copy link
Author

scabug commented Jun 11, 2012

@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
Copy link
Member

not fixed in Scala 3 (3.4.0-RC2) either

@som-snytt
Copy link

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
Copy link

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.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

5 participants