Scala Programming Language
  1. Scala Programming Language
  2. SI-6526

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

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Critical Critical
    • Resolution: Fixed
    • Affects Version/s: Scala 2.9.2, Scala 2.10.0
    • Fix Version/s: Scala 2.10.0-RC1, Scala 2.10.0
    • Component/s: Misc Compiler
    • Labels:
      None
    • Environment:

      Mac OS X
      java version "1.7.0_07"
      Scala code runner version 2.9.2
      Scala code runner version 2.10.0-20121011-125927-25ad7876a9

      Description

      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.

        Activity

        Hide
        Viktor Klang added a comment -

        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.

        Show
        Viktor Klang added a comment - 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.
        Hide
        Adriaan Moors added a comment -

        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.

        Show
        Adriaan Moors added a comment - 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.
        Hide
        Kris Nuttycombe added a comment -

        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.

        Show
        Kris Nuttycombe added a comment - 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.
        Hide
        Iulian Dragos added a comment -

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

        Show
        Iulian Dragos added a comment - Adriaan, not in the following week, but I can have a look middle next week, if nobody beats me to it.
        Hide
        Paul Phillips added a comment -

        Since there's no reference here yet, https://github.com/scala/scala/pull/1507

        Show
        Paul Phillips added a comment - Since there's no reference here yet, https://github.com/scala/scala/pull/1507

          People

          • Assignee:
            Jason Zaugg
            Reporter:
            Daniel Spiewak
          • Votes:
            3 Vote for this issue
            Watchers:
            11 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development