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

Compiler silently fails to @tailrec a nested tail-recursive function #6526

Closed
scabug opened this issue Oct 15, 2012 · 11 comments
Closed

Compiler silently fails to @tailrec a nested tail-recursive function #6526

scabug opened this issue Oct 15, 2012 · 11 comments
Assignees
Milestone

Comments

@scabug
Copy link

scabug commented Oct 15, 2012

import scala.annotation.tailrec

class TailRec {
  Some(new AnyRef) map { phooie =>
    @tailrec
    def inner(i: Int): Int =
      inner(i + 1)
    
    inner(0)
  } getOrElse 42
}

The inner function in the above code will be compiled into the following bytecode:

  private final int inner$1(int);
    Code:
       0: aload_0       
       1: iload_1       
       2: iconst_1      
       3: iadd          
       4: invokespecial #23                 // Method inner$1:(I)I
       7: ireturn  

Needless to say, invokevirtual != goto. This was a silent failure of the tailrec optimization. No warnings were emitted by the compiler. This bug was found against 2.9.2 and later reproduced against a fresh build of the 2.10.0-RC1 tag.

Hilariously, removing the getOrElse 42 resolves the issue, and the compiler is able to compile the tail recursive call into a jump.

Given how pervasive this "@tailrec inner function" idiom is within the standard library, akka, and myriads of code bases (including Precog), this seems like a very serious issue. It basically implies that a lot of code that people think is safe will actually explode for sufficiently large datasets.

@scabug
Copy link
Author

scabug commented Oct 15, 2012

Imported From: https://issues.scala-lang.org/browse/SI-6526?orig=1
Reporter: @djspiewak
Affected Versions: 2.9.2, 2.10.0
Other Milestones: 2.10.0

@scabug
Copy link
Author

scabug commented Oct 15, 2012

Kris Nuttycombe (nuttycom) said:
This is a complete showstopper for Precog; we use @tailrec everywhere and this misbehavior has us currently sitting right in the middle of a minefield.

@scabug
Copy link
Author

scabug commented Oct 15, 2012

Viktor Klang (viktorklang) said (edited on Oct 15, 2012 10:29:52 PM UTC):
A showstopper? You mean that there is no work-around?

(Not saying that it shouldn't be fixed, but clearly there's a work-around here, which is not to put @tailrec def in closures until the bug is fixed)

@scabug
Copy link
Author

scabug commented Oct 15, 2012

Kris Nuttycombe (nuttycom) said:
Meaning that the only workaround (for us) involves thousands of lines of refactoring to move these @tailrec'ed defs up to the top level. I wouldn't have minded if the compiler actually told us that it failed to TCO the methods, but we use @tailrec defs instead of while loops basically everywhere.

@scabug
Copy link
Author

scabug commented Oct 15, 2012

Viktor Klang (viktorklang) said:
Well, if the compiler had told you, this ticket wouldn't exist…
The problem here seems to be local to tail recursion inside closures, and as such you don't need to move things to top-level, you just need to move it outside of the closure, as a work-around, if needed, until the bug is fixed.

@scabug
Copy link
Author

scabug commented Oct 15, 2012

@djspiewak said:
Kris is not exaggerating when he says that this would involve thousands of lines of refactoring. You're right that this ticket wouldn't exist if the compiler had told us about this issue, since we would have caught the issue early and never would have written our code in this fashion. However, the fact is that the compiler didn't, we did, and now we're in a very serious mess. I doubt that we're the only ones.

The fact is that this is a silent failure of the worst sort. It is a bug in the compiler that introduces a failure condition in your code that is likely to only exist in production (where you see realistic dataset sizes). Compiler bugs are bad enough. Silent compiler bugs are worse. Silent compiler bugs that are only identifiable by reading the bytecode are worse still. Silent compiler bugs that cause your code to crash only in production are DEATH.

My point is this: even though there is a workaround, it's not one that is practical for many people (including us). Even if it were, this bug needs to be fixed. There is almost certainly a lot of code out there, right now, that is broken without anyone knowing. People can't use a workaround if they don't know they have a problem.

@scabug
Copy link
Author

scabug commented Oct 15, 2012

Viktor Klang (viktorklang) said:
Of course the bug needs to be fixed. No one has argued that it shouldn't. I just reacted to the use of the word "showstopper", which is customarily used to describe a situation where no workaround is available, which I disproved was the case here. No doubt silent compiler bugs are serious matters indeed, and they should be fixed indeed.

@scabug
Copy link
Author

scabug commented Oct 16, 2012

@adriaanm said:
Iulian, could you have a look if it's low risk to emit a warning/error?
If we have an RC2, we could include a low-risk fix.

@scabug
Copy link
Author

scabug commented Oct 16, 2012

Kris Nuttycombe (nuttycom) said:
A warning will definitely help so long as it catches all the cases; my main worry is that right now I don't feel like I can trust @tailrec fully, and was dreading the prospect of having to rewrite everything to while loops. But if the warning can be embedded into the TCO machinery such that anywhere that it bails out we're notified, that will greatly ease my mind.

@scabug
Copy link
Author

scabug commented Oct 18, 2012

@dragos said:
Adriaan, not in the following week, but I can have a look middle next week, if nobody beats me to it.

@scabug
Copy link
Author

scabug commented Oct 23, 2012

@paulp said:
Since there's no reference here yet, scala/scala#1507

@scabug scabug closed this as completed Oct 29, 2012
@scabug scabug added the critical label Apr 7, 2017
@scabug scabug added this to the 2.10.0-RC1 milestone Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants