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

Unsound tail recursion optimization on trait lazy val #5455

Closed
scabug opened this Issue Feb 10, 2012 · 3 comments

Comments

Projects
None yet
2 participants
@scabug
Copy link

scabug commented Feb 10, 2012

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

@scabug

This comment has been minimized.

Copy link

scabug commented Feb 10, 2012

Imported From: https://issues.scala-lang.org/browse/SI-5455?orig=1
Reporter: @djspiewak
Affected Versions: 2.9.1
See #5517

@scabug

This comment has been minimized.

Copy link

scabug commented Feb 21, 2012

@adriaanm said:
exclude lazy val accessor defdef

@scabug

This comment has been minimized.

Copy link

scabug commented Mar 11, 2012

@paulp said:
79e937bea2

@scabug scabug closed this Mar 11, 2012

@scabug scabug added this to the 2.10.0 milestone Apr 7, 2017

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