Imported From: https://issues.scala-lang.org/browse/SI-7374?orig=1
Reporter: Donny Nadolny (dnadolny)
Affected Versions: 2.10.1, 2.10.2-RC1, 2.10.2-RC2, 2.10.2, 2.11.0-M4

@vigdorchik said:
How do you compile?

Donny Nadolny (dnadolny) said:
For most of this I used the Scala IDE (v3.0.0rc3-2_10-2013-03-131031-dac2f1c, which has scala 2.10.1). I had also replicated the problem with list.tail() on the command line, again using 2.10.1 (SomeScala.scala in src/scala, Main.java in src/java):

./scalac -sourcepath src/java/* src/scala/*
javac -classpath /home/dnadolny/tools/scala-2.10.1/lib/scala-library.jar:. -d . src/java/Main.java
./scala Main

I have also reproduced it with 2.10.0, however it works correctly under 2.9.2.

@SethTisue said:
here's a complete transcript of a reproduction:

% cat S.scala   
object CreateCollection {
  def someList = List(1, 2, 3)
}
% cat Main.java
class Main {
    public static void main(String[] args) {
        System.out.println(CreateCollection.someList().tail());
    }
}
% /usr/local/scala-2.10.1/bin/scalac S.scala                                
% javac -classpath .:/usr/local/scala-2.10.1/lib/scala-library.jar Main.java
% java -classpath .:/usr/local/scala-2.10.1/lib/scala-library.jar Main      
Exception in thread "main" java.lang.NoSuchMethodError: scala.collection.immutable.List.tail()Lscala/collection/Traversable;
	at Main.main(Main.java:3)

@retronym said:
Paul's analysis from the mailing list:

The method descriptor is not the erasure of the generic signature. Surely a scala bug. Notice how the third tail's return type is Traversable<A> in the generic signature but Object in the descriptor. javac issues an ill-fated call to the method it expects to find based on generic return type Traversable<A>.

Exception in thread "main" java.lang.NoSuchMethodError: scala.collection.immutable.List.tail()Lscala/collection/Traversable;
	at Main.main(Main.java:3)

scala> val tails = classOf[scala.collection.immutable.List[_]].getMethods filter (_.getName == "tail")
tails: Array[java.lang.reflect.Method] = Array(public scala.collection.LinearSeqOptimized scala.collection.immutable.List.tail(), public scala.collection.immutable.List scala.collection.immutable.List.tail(), public java.lang.Object scala.collection.AbstractTraversable.tail())

scala> tails foreach println
public scala.collection.LinearSeqOptimized scala.collection.immutable.List.tail()
public scala.collection.immutable.List scala.collection.immutable.List.tail()
public java.lang.Object scala.collection.AbstractTraversable.tail()

scala> tails map (_.toGenericString) foreach println
public scala.collection.LinearSeqOptimized scala.collection.immutable.List.tail()
public scala.collection.immutable.List scala.collection.immutable.List.tail()
public scala.collection.Traversable<A> scala.collection.AbstractTraversable.tail()

But as you may have heard, my scala days are numbered so all I can offer is this diagnosis.

I bisected that (the old fashioned way, as the regression pre dates the archive of builds available to scalac-hash), and landed scala/scala@a0a045f5c0. That was just a library change (introduction of Abstract{Seq, Iterable, ...}) so the root problem is a latent bug in the backend (either with erasure or with generic signatures.), most probably #3452.

I've been poking around in this space recently to fix some problems with generic sigs and erasure of value classes, so I'll take a look at this one.

@Blaisorblade said:
If it's #3452, very likely it's workarounded by -Xverify (with a backend respecting it -- currently it's GenASM, it used to be GenJVM): -Xverify detected and discarded invalid generic signatures, avoiding the problem (while reducing precision of type signatures, of course).
I even had a pull request enabling that check by default.

@retronym said:
Seen in isolation:

trait TraversableLike[Repr] {
  def tail: Repr = ???
}
trait MyTraversable[A] extends TraversableLike[Option[A]]
abstract class MyAbstractTraversable extends MyTraversable[String]

scala> classOf[MyAbstractTraversable].getMethod("tail")
res16: java.lang.reflect.Method = public java.lang.Object MyAbstractTraversable.tail()

scala> classOf[MyAbstractTraversable].getMethod("tail").toGenericString
res17: String = public scala.Option<java.lang.String> MyAbstractTraversable.tail()

@retronym said (edited on Sep 22, 2013 10:44:53 AM UTC):
Which is just #3452, and is fixed by the almost-there patch of Paul's paulp/scala@c007b7d

scala> classOf[MyAbstractTraversable].getMethod("tail")
res0: java.lang.reflect.Method = public java.lang.Object MyAbstractTraversable.tail()

scala> classOf[MyAbstractTraversable].getMethod("tail").toGenericString
res1: String = public java.lang.Object MyAbstractTraversable.tail()

I think I finally understand Paul's assertion that "we need more bridges". Rather than making the weakening generic signature to meet the erasure to Object we could (should?) sharpen the erasure of tail to Traversable, in the process installing a bridge for the covariant override. Currently, bridges are only added in the erasure phase, so later phases (importantly: mixin) are restricted to generating signatures that exactly match the overriden signature.

@paulp said:
Jason: yes, exactly. I was also thinking about either running mixin before erasure or bridge creation after mixin. It's not clear to me why bridges should be generated before the last moment - I would not base them on the extremely fallible scala ideas as held halfway through the pipeline, but on the actual bytecode being generated.

@retronym said:
I'm pretty sure that bridges have to be based on the Scala typesystem. Brian's JVMLS talk on the matter was really helpful to me to understand why its non-trivial to just do them in the VM (and I think the same arguments prevent us from making it a back-end only affair).

I actually got part of the way there to installing additional bridges in mixin: https://github.com/retronym/scala/compare/ticket/3452-rebased (please excuse the expasperated messaage-free commits at the end of the sequence!) but was lucky enough that a test (or the library) alerted me to a corner case that resulted from spreading responsibility for bridges across two phases. The root complexity is, as you point out, running mixin after erasure. Martin told me he's going to try it way earlier next time around, all the way back in extension methods.

@retronym said:
Maybe I misintepreted your comment; I guess we could have a bridges phase right at the end, even with mixin where it stands. There are still the more fundamental issues that result from Any (should List[Int] project onto List or List). I revisited those tickets last week to remind myself of history.

@paulp said:
Yes, I don't mean we have to ignore scala's type system, but that the bridge analysis should be performed with exact knowledge of the bytecode we are about to generate. This would eliminate a huge class of bridge bugs - the "obviously wrong" bytecode which is still generated in many cases.

@retronym said:
scala/scala#3493

@retronym said:
Fixed, by selectively emitting weaker signatures trait- and static forwarders:

scala/scala#3493

More details:

https://issues.scala-lang.org/browse/SI-3452?focusedCommentId=68230&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-68230