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

Endless recursion as a result of incorrect specialization #5629

Closed
scabug opened this issue Mar 29, 2012 · 15 comments
Closed

Endless recursion as a result of incorrect specialization #5629

scabug opened this issue Mar 29, 2012 · 15 comments

Comments

@scabug
Copy link

scabug commented Mar 29, 2012

object test extends App {

  trait MyPF[@specialized(Int) -A] extends (A => Unit) {
    def isDefinedAt(x: A): Boolean
    def applyOrElse[A1 <: A](x: A1, default: A1 => Unit): Unit = {
      println("MyPF.applyOrElse entered...")
      if (isDefinedAt(x)) apply(x) else default(x)
    }
  }

  trait MySmartPF[@specialized(Int) -A] extends MyPF[A] {
    def apply(x: A): Unit = {
      println("MySmartPF.apply entered...")
      applyOrElse(x, { _: Any => throw new MatchError })
    }
  }

  type T = Int
  //type T = Any

  def newPF(test: T): MyPF[T] = new MySmartPF[T] {
    def isDefinedAt(x: T): Boolean = x != test
    override def applyOrElse[A1 <: T](x: A1, default: A1 => Unit): Unit = {
      println("newPF.applyOrElse entered...")
      if (x != test) { println("ok"); () } else { println("default"); default(x) } 
    }
  }
  
  val pf = newPF(1)
  println("=== pf(1):")
  try { pf(1) } catch { case x => println(x) }
  println("=== pf(42):")
  pf(42)
  println("=== done")
}

Expected output:

=== pf(1):
MySmartPF.apply entered...
newPF.applyOrElse entered...
default
scala.MatchError: () (of class scala.runtime.BoxedUnit)
=== pf(42):
MySmartPF.apply entered...
newPF.applyOrElse entered...
ok
=== done

Actual output:

=== pf(1):
MySmartPF.apply entered...
MyPF.applyOrElse entered...
scala.MatchError: () (of class scala.runtime.BoxedUnit)
=== pf(42):
MySmartPF.apply entered...
MyPF.applyOrElse entered...
MySmartPF.apply entered...
MyPF.applyOrElse entered...
...
java.lang.StackOverflowError

The bug is no longer reproduced when we replace type T = Int by type T = Any or remove @specialized.

Now this prevents partial functions to be specialized.

@scabug
Copy link
Author

scabug commented Mar 29, 2012

Imported From: https://issues.scala-lang.org/browse/SI-5629?orig=1
Reporter: @pavelpavlov
Affected Versions: 2.10.0-M2, 2.10.0

@scabug
Copy link
Author

scabug commented Mar 29, 2012

@non said:
So my coworker Adam and I have been looking into this and I think we have a minified test case:

import scala.{specialized => spec}

trait GrandParent[@spec(Int) -A] {
  def foo(a:A): Unit
  def bar[B <: A](b:B): Unit = println("grandparent got: %s" format b)
}

trait Parent[@spec(Int) -A] extends GrandParent[A] {
  def foo(a:A) = bar(a)
}

class IntChild extends Parent[Int] {
  override def bar[B <: Int](b:B): Unit = println("int child got: %s" format b)
}

class AnyChild extends Parent[Any] {
  override def bar[B <: Any](b:B): Unit = println("any child got: %s" format b)
}

object Test {
  def main(args:Array[String]) {
    new IntChild().foo(33)
    new AnyChild().foo(33)
  }
}

The expected output is:

int child got: 33
any child got: 33

the actual output is:

grandparent got: 33
any child got: 33

@scabug
Copy link
Author

scabug commented Mar 29, 2012

@non said (edited on Mar 29, 2012 7:42:23 PM UTC):
The basic problem seems to be that Parent's specialized variants have their 'foo' hardwired to Grandparent's bar.

Interestingly, if you remove the type parameters from bar the problem disappears.

EDIT: That is not quite right.

Really it seems that Grandparent contains a specialized method bar$mcI$sp which Parent$mcI$sp calls. Since IntChild extends Parent$mcI$sp but does not override bar$mcI$sp the grandparent's version is used.

@scabug
Copy link
Author

scabug commented Mar 29, 2012

@non said:
One other note to Pavel: the current specialization happening is already doing some boxing between apply and applyOrElse. Thus, in the short term specializing may not offer as much performance as you'd like, and it would be worth leaving it out.

@scabug
Copy link
Author

scabug commented Mar 29, 2012

@pavelpavlov said:
Erik,
What do you mean by 'current' specialization?
One in adriaanm/partialfun branch definitely don't specialize partial functions well, as it goes only half-way (Abstract PF is specialized, but not PF itself). When I've tried to fix it, I've encountered this bug. So if the bug won't be fixed soon, I've plan to turn off PF specialization completely, as such half-specialization can be in fact even slower than no specialize at all. If this issue will be fixed in the near time, I'll try to enable PF specialization again, and maybe create a few other bugs :)

@scabug
Copy link
Author

scabug commented Mar 29, 2012

@non said:
I meant "the specialization that occurred in your test case". Basically, even if the bug was fixed, there would still be some boxing.

I know that after 2.10 there will be some work put into trying to redesign specialization a little bit. So it may be best to just wait and see how that goes.

@scabug
Copy link
Author

scabug commented Mar 29, 2012

@pavelpavlov said:
Note that Int (which is class' specialized type argument) is upper bound for B in IntChild#bar, so the bar's argument b can be specialized as Int and the's no need to box it everywhere in the bar's body. I don't know how hard for current specialization logic is to discover this fact, but without it specialization can do almost nothing for applyOrElse-style partial functions.

@scabug
Copy link
Author

scabug commented Mar 29, 2012

@non said:
One work-around that seems to work is specializing the type parameter to foo also, e.g.:

import scala.{specialized => spec}                                                                                          
                                                                                                                            
trait GrandParent[@spec(Int) -A] {                                                                                          
  def foo(a:A): Unit                                                                                                        
  def bar[@spec(Int) B <: A](b:B): Unit = println("grandparent got: %s" format b)                                           
}                                                                                                                           
                                                                                                                            
trait Parent[@spec(Int) -A] extends GrandParent[A] {                                                                        
  def foo(a:A) = bar(a)                                                                                                     
}                                                                                                                           
                                                                                                                            
class IntChild extends Parent[Int] {                                                                                        
  override def bar[@spec(Int) B <: Int](b:B): Unit = println("int child got: %s" format b)                                  
}                                                                                                                           
                                                                                                                            
class AnyChild extends Parent[Any] {                                                                                        
  override def bar[@spec(Int) B <: Any](b:B): Unit = println("any child got: %s" format b)                                  
}                                                                                                                           
                                                                                                                            
object Test {                                                                                                               
  def main(args:Array[String]) {                                                                                            
    new IntChild().foo(33)                                                                                                  
    new AnyChild().foo(33)                                                                                                  
  }                                                                                                                         
}

Pavel, you may want to consider trying this with your code as well.

@scabug
Copy link
Author

scabug commented Mar 29, 2012

@pavelpavlov said:
Thank you, Erik, I'll try this and let you know about the results.

@scabug
Copy link
Author

scabug commented Mar 30, 2012

@non said:
I just tried this with your code and it produces the correct result.

So while the bug is still open, hopefully it won't impede your PF work.

@scabug
Copy link
Author

scabug commented Mar 30, 2012

@non said:
Given this solution, and thinking about it some more, maybe the correct resolution would be to warn (or error) when a superclass' method (with a specialized type parameter) is overridden with a method that is not specialized?

It seems clear that you either need to override bar and bar$mcI$sp or neither. The other option would be for the subclass' bar to be automatically specialized, but that seems a bit risky. On the other hand it would certainly be more convenient.

Anyone else have any thoughts on this?

@scabug
Copy link
Author

scabug commented May 7, 2012

@axel22 said:
I think the problem here is that IntChild overrides bar, but does not actually override bar$mcI$sp.

@scabug
Copy link
Author

scabug commented May 7, 2012

@axel22 said:
In fact, bar in IntChild should forward to bar$mcI$sp, instead of containing the implementation.

@scabug
Copy link
Author

scabug commented May 7, 2012

@axel22 said:
The problem was that detecting if a method needs a special override used unification to determine this, and unification didn't used to unify over method type parameters and their type bounds - it simply ignored them.

@scabug scabug closed this as completed May 7, 2012
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants