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

Unsound tail recursion optimization on trait lazy val

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: Scala 2.9.1
    • Fix Version/s: Scala 2.10.0
    • Component/s: Misc Compiler
    • Labels:
      None
    • Environment:

      Scala 2.9.1.final

      Description

      Consider the `bar` lazy val in the following snippet:

      trait Test {
        def root: Test
        
        private final lazy val bar: Thing[Double] = {
          if (this eq root) {
            Thing { () =>
              System.identityHashCode(bar)
            }
          } else {
            root.bar
          }
        }
      }
      
      case class Thing[A](f: () => A)
      

      If we look at the bytecode generated for that lazy val, we get the following:

             0: aload_0       
             1: aload_0       
             2: invokeinterface #12,  1           // InterfaceMethod Test.root:()LTest;
             7: if_acmpne     26
            10: new           #14                 // class Thing
            13: dup           
            14: new           #16                 // class Test$$anonfun$Test$$bar$1
            17: dup           
            18: aload_0       
            19: invokespecial #20                 // Method Test$$anonfun$Test$$bar$1."<init>":(LTest;)V
            22: invokespecial #23                 // Method Thing."<init>":(Lscala/Function0;)V
            25: areturn       
            26: aload_0       
            27: invokeinterface #12,  1           // InterfaceMethod Test.root:()LTest;
            32: astore_0      
            33: goto          0
      

      Specifically, here:

            32: astore_0      
            33: goto          0
      

      Ah, lovely tail recursion! Unfortunately, this is not a function, and it cannot be optimized in this way! Specifically, the bad case is if the value of `root` has already realized `bar`. In this case, the return result from `this.bar` will be a `Thing` which in turn returns a different value of `identityHashCode` than `root.bar` would have returned. Additionally, this tail recursion means that `root.bar` will not be realized if it hasn't already been, thus a fundamental lazy val semantic is violated.

      This seems to be an extremely tricky bug to actually reproduce. Simply changing the body of the function passed to `Thing` is sufficient to avoid the issue. Specifically:

            Thing { () =>
              bar
              42
            }
      

      With things in this position, the compiler sees bar as a recursive call not in tail position and refuses to perform the optimization (based on the error message I get if I turn bar into a def and use @tailrec). Technically, that assessment of the compiler's is overly-strict, but it happens to be sufficient to avoid the issue in this case.

      Anyway, the solution here is to just not ever do tail recursion on lazy vals unless you can prove that the 0 slot is remaining stable. That criterion would fail this lazy val (rightfully).

        Issue Links

          Activity

          Hide
          Adriaan Moors added a comment -

          exclude lazy val accessor defdef

          Show
          Adriaan Moors added a comment - exclude lazy val accessor defdef
          Hide
          Paul Phillips added a comment -

          79e937bea2

          Show
          Paul Phillips added a comment - 79e937bea2

            People

            • Assignee:
              Paul Phillips
              Reporter:
              Daniel Spiewak
            • Votes:
              0 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development