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

Specialized trait with final recursive method explodes during lambdalift #5788

Closed
scabug opened this issue May 10, 2012 · 30 comments
Closed

Specialized trait with final recursive method explodes during lambdalift #5788

scabug opened this issue May 10, 2012 · 30 comments
Assignees
Milestone

Comments

@scabug
Copy link

@scabug scabug commented May 10, 2012

This relatively small test case blows up during "lambdalift":

trait Foo[@specialized(Int) A] {
  final def bar(a:A):A = bar(a)
}

There are a lot of variants that do compile properly. By removing specialized, or final, you can get code that compiles. Of course, this code will just overflow the stack, but the bug seems to affect any recursive final method, not just pointless ones.

I ran into this issue when trying to update https://github.com/non/spire to work with 2.10.0.

I've attached a test source file and the error log.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 10, 2012

Imported From: https://issues.scala-lang.org/browse/SI-5788?orig=1
Reporter: @non
Affected Versions: 2.10.0-M3, 2.10.0
Other Milestones: 2.10.0
Attachments:

  • error_20120814.log (created on Aug 14, 2012 4:00:31 PM UTC, 16734 bytes)
  • error.log (created on May 10, 2012 11:58:11 PM UTC, 21779 bytes)
  • test.scala (created on May 10, 2012 11:58:11 PM UTC, 67 bytes)
@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 11, 2012

@non said:
I should add that it also crashes if Foo is a class instead of a trait.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 15, 2012

@VladUreche said:
Okay, fixed half of it. The problem is LabelDef parameter symbols are recreated instead of picking up the existing symbols from above. I fixed it for symbols defined in the function, now I need to somehow carry the symbol mapping from the method duplication in TypingTransformer.makeSpecializedMembers into Duplicators. (or just use it in case it's already there...)

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 15, 2012

@non said:
Awesome! Let me know if you need any help, or extra testing.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 15, 2012

@VladUreche said:
The typer was nice enough to lend a hand with symbol mapping -- as long as the name stays the same, the typer will find it. :)
Let's see if it passes the test suite now.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 15, 2012

@som-snytt said:
I was about to ask you about that; I only noticed it after discovering -uniqid... I thought Adriaan's comment had special significance, like LabelDefs are used differently now; but it was clear how this used to work in 2.9. Obviously, after learning what Typer is doing for Duplicator, I could answer my questions from yesterday; but I had to stick treeBrowser.browse in a few places to get the picture. For future newbies, one might think of Duplicator.retyped as .reduplicate as opposed to tree.duplicate.

I'll be curious to see the rest of the fix if there's more; you don't just get the enclosing context? Sorry I didn't get it done. :)

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 15, 2012

@VladUreche said:
@andrew:
Thanks for looking into this! I asked Adriaan about it today: LabelDefs have to get existing (previously defined) symbols as parameters.

The problem in our case was that new symbols were passed as parameters to the LabelDef. Later, the erasure phase would update the symbol owners and types, but would skip LabelDef parameters, because they should have been updated at their definition site (which, normally, is before the LabelDef). Finally, this owner mismatch was crashing Lambdalift, because the LabelDef parameters had the pre-erasure owner chains (Foo instead of Foo$class).

It's the first time I use -Ybrowse:, thanks for pointing it out. I used -uniqid, -Xprint: and -Xshow-syms for debugging. And the plain old assert(id != <...>) in Symbols.scala :p

I committed the patch to [https://github.com/VladUreche/scala/tree/issue/5788]. (it passed the testsuite on my machine)

@erik:
Before I do the pull request, can you please check if it compiles spire correctly? If there are any more problems, ping me so I look at them.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 15, 2012

@non said:
Sure thing, I'll let you know.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 15, 2012

@VladUreche said:
Thanks a lot Erik!

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 15, 2012

@non said:
Hey Vlad.

Using your branch, I can compile Spire with specialization and it runs the benchmark at the speed I expect. Looks good to me!

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 15, 2012

@VladUreche said:
Cool, I'll submit the pull request.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 16, 2012

@VladUreche said (edited on May 16, 2012 12:48:05 PM UTC):
Unfortunately the patch failed the testsuite (I wonder what I tested, that it passed, probably the scaladoc repo...)
The problem is summarized at [http://groups.google.com/group/scala-internals/t/c457242593443902], since depending on where they are generated, LabelDef's parameters look differently. I'm looking into changing the behavior of the tailcalls phase to fix this.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 16, 2012

@som-snytt said:
Or -optimise...

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 16, 2012

@VladUreche said:
What do you mean?

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 16, 2012

@som-snytt said:
Pardon: just a note to self that ant nightly runs with -optimise, as opposed to ant test which is not. I have hit that discrepancy before, where only -optimise fails.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jun 11, 2012

@non said:
I guess this will not be fixed for M4, since that's being tagged now.

Is the plan still to try to change the tailcalls behavior?

Is this something that can be fixed for 2.10.0?

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jun 11, 2012

@VladUreche said:
Unfortunately it's not in M4 but it'll be there in 2.10. I fixed the main issue, but there's a widening transformation happening and I haven't been able to prevent it so far. In case you want to take a look, my last progress is at [https://github.com/VladUreche/scala/tree/issue/5788]. The main commit that explains what I do is [https://github.com/VladUreche/scala/commit/101c4385568b3c762306277d8a2bd14171b4451f].

It won't compile the following case, complaining it's expecting Test.this.B[T] and it got <empty>.This#B[T]:

trait Test {
  trait B[T]
  private final def grow[T](): B[T] = grow[T]()
}
@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jul 10, 2012

@non said:
Hey Vlad, can this be upgraded to critical? I think it's really important that it go in 2.10 but according to Adriaan's email only pullreqs fixing critical bugs can go in.

I was on vacation last week but may try to work on this since it's so important to me.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jul 10, 2012

@VladUreche said:
Done. I'll soon have the last pull request on scaladoc and will have time for specialization.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jul 10, 2012

@non said:
Thanks Vlad!

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 6, 2012

@VladUreche said:
I have a quick fix in: scala/scala#1063 (small enough that it may be merged into 2.10.x at this late stage)
and the complete fix in VladUreche/scala@e86afe6.

If all goes well, I'll revert the quick fix and add the complete one in another pull request once 2.10.x is merged into master.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 14, 2012

Adam Klein (aklein-at-novus.com) said:
As of my latest 2.10.x build (1c5526e), I get this blow up with a slightly different error log, which I'll try to attach.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 14, 2012

@VladUreche said:
Adam, please also test the full patch in VladUreche/scala@e86afe6, as it is supposed to be the correct fix rather than the hack to fix the problem. Thx.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 14, 2012

@VladUreche said:
Thanks for the error log! Are you running the test in the bug?

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 14, 2012

Adam Klein (aklein-at-novus.com) said (edited on Aug 14, 2012 4:32:22 PM UTC):
Confirmed that your full patch corrects the issue, thank you!

(yes, I am running the test case from the original parent)

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 14, 2012

@VladUreche said:
Thanks Adam! Then I'll revert the hack and put in the full patch in 2.10.x.

I'm a bit confused as to why it passed the testsuite without this tesecase working. I'll have a look into this too, after I finish debugging the recent inliner crashes.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 16, 2012

@VladUreche said:
Status update: I prepared the pull request but there is a problem in the backend: the closure elimination phase incorrectly eliminates some code and this leads to a failed test:

$ cat test/files/run/tailcalls-base2.scala 
// This test checks correct handling of the this pointer in the tailcalls transformation
trait Base {
  def message: String
  class T(i: Int) { println(message) ; def msg = message }

  @annotation.tailrec final /* make sure it's transformed by tailcalls */
  def tailCall(a:Int, other: Base): T =
    if (a == 0) 
      new T(0)
    else 
      other.tailCall(a-1, this) // tail call-transformed
}

class ReturnsInt extends Base { def message = this.getClass.toString }
class ReturnsStr extends Base { def message = this.getClass.toString }

object Test extends App {
  val rInt = new ReturnsInt
  val rStr = new ReturnsStr

  for (x <- 1 to 10)
    println(rInt.tailCall(x, rStr).msg)
}

$ build/quick/bin/scalac test/files/run/tailcalls-base2.scala -d classes
$ build/quick/bin/scala -cp classes Test
class ReturnsStr
class ReturnsStr
class ReturnsInt
class ReturnsInt
class ReturnsStr
class ReturnsStr
class ReturnsInt
class ReturnsInt
class ReturnsStr
class ReturnsStr
class ReturnsInt
class ReturnsInt
class ReturnsStr
class ReturnsStr
class ReturnsInt
class ReturnsInt
class ReturnsStr
class ReturnsStr
class ReturnsInt
class ReturnsInt

$ build/quick/bin/scalac test/files/run/tailcalls-base2.scala -d classes -optimize
$ build/quick/bin/scala -cp classes Test
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
class ReturnsStr
@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 16, 2012

@VladUreche said:
It's enough to run with -Yclosure-elim, no need for -optimize. I'll be looking at this tonight.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 19, 2012

@VladUreche said:
I made another attempt to fix the problem without changing tailcalls: https://github.com/scala/scala/pull/1161/files
The full patch is still in the works, my fix for the problem above generated incorrect bytecode, so there's no way it's going into 2.10. It will also be better if we keep the current design, as the full patch generates more JVM instructions and I fear previously-JITted methods will now be interpreted because they're now larger.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 19, 2012

@VladUreche said:
The patch is now in trunk. I'll close the bug but feel free to reopen in there are any problems.

@scabug scabug closed this Aug 19, 2012
@scabug scabug added this to the 2.10.0-M6 milestone Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants
You can’t perform that action at this time.