unification should consider all parents

[scabug]

val rand = new scala.util.Random()

This works fine

val a = rand.shuffle(0 to 5)

But this gives an error:

val a = rand.shuffle(0 until 5)
<console>:9: error: Cannot construct a collection of type scala.collection.AbstractSeq[Int] with elements of type Int based on a collection of type scala.collection.AbstractSeq[Int].
       val a = rand.shuffle(0 until 5)

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-6948?orig=1
Reporter: Pierre Schaus (pschaus)
Affected Versions: 2.10.0

[scabug]

@retronym said (edited on Jan 9, 2013 2:46:22 PM UTC):
Here's a slightly more isolated look at the problem:

import collection.generic._

object Test {
  def shuffle[T, CC[X] <: TraversableOnce[X]]
             (xs: CC[T])
             (implicit bf: CanBuildFrom[CC[T], T, CC[T]]): CC[T] = null.asInstanceOf[CC[T]]

  def foo1(r: R1) = shuffle(r)                  // fail
  def foo2(r: R1) = shuffle(r: IndexedSeq[Int]) // okay
  def foo3(r: R2) = shuffle(r)                  // okay

  abstract class AbstractSeq[+A] extends collection.Seq[A]

  abstract class R1
  extends AbstractSeq[Int]
     with IndexedSeq[Int]

  abstract class R2 extends IndexedSeq[Int]
}

The intermediate class, AbstractSeq, is new in 2.10.0. It seems that the implicit search isn't looking deeper than the first parent of R1. This test file also fails in 2.9.2, which tells me this isn't a regression in type inference, but rather an existing bug/limitation which has been exposed by the change in the collection hierarchy.

[scabug]

@retronym said:
Adriaan: assigning to you to contemplate the fix and fix version.

AFAICT, the only fix we could deliver in 2.10.1 would be an improved type inference, which of course is also not without risk (one man's treasure is another man's trash.)

While I'm happy to live with rand.shuffle((0 until 5).toList) for the reported bug, I'm worried that the inclusion of AbstractXxx will lead to a trickle of these problems being reported.

[scabug]

@retronym said:
I've analysed this, from the commit comment:

https://github.com/retronym/scala/compare/ticket/6948

In a0a045f, a variety of abstract classes were inserted
into the collections hierarchy to centralize the instantiation
of traits, and thereby shed a few pounds from the JAR size.

These appear to have been carefully added into the right
place in the linearization order, and were kept private,
so it was hard to forsee any downside.

Turns out there was a small downside: type constructor
inference doesn't start by walking up the base type sequence,
instead it first tries the direct parents. This is done
in See TypeVar#registerBound.

For most collections this subtlety isn't visible, as
they typically match the kind CC[x] <: TraversableOnce[x],
and the search of the parents doesn't happen.

But for types like BitSet, Range, and WrappedString,
type inference must work up the heirarchy to find
a suitable type constructor. Not, it finds the newly
inserted AbstractSeq or the like, infers this, and
subsequently fails to find a corresponing CanBuildFrom.

    scala> val rand = new util.Random
    rand: scala.util.Random = scala.util.Random@7adc28b

    scala> rand.shuffle(collection.immutable.BitSet(1))
    <console>:9: error: Cannot construct a collection of type scala.collection.AbstractSet[Int] with elements of type Int based on a collection of type scala.collection.AbstractSet[Int].
                  rand.shuffle(collection.immutable.BitSet(1))
                              ^

    scala> rand.shuffle("": collection.immutable.WrappedString)
    <console>:9: error: Cannot construct a collection of type scala.collection.AbstractSeq[Char] with elements of type Char based on a collection of type scala.collection.AbstractSeq[Char].
                  rand.shuffle("": collection.immutable.WrappedString)
                              ^

    scala> rand.shuffle(1 until 2)
    <console>:9: error: Cannot construct a collection of type scala.collection.AbstractSeq[Int] with elements of type Int based on a collection of type scala.collection.AbstractSeq[Int].
                  rand.shuffle(1 until 2)
                              ^

[scabug]

@paulp said:
I wrapped my head around this on the plane today when I ran smack into it. It is a big problem for my plans. We have to fix it one way or the other. And my test case is a regression from 2.9. Clearly it was going to hit us one way or another, but it's still a regression.

import scala.collection.immutable.BitSet
import scala.collection.generic.CanBuildFrom

object Test {
  def builder[A, CC[X] <: TraversableOnce[X], Coll](xs: Coll with CC[A] with AnyRef)(implicit cbf: CanBuildFrom[_, A, CC[A]]) = cbf()

  def main(args: Array[String]) {
    println(builder(null: BitSet) += 1 result)
  }
}

[scabug]

@gkossakowski said:
Unassigning and rescheduling to M7 as previous deadline was missed.

[scabug]

@paulp said:
It's a crime that this is still in play. It would be REALLY EASY to make the stupid AbstractFoo classes public. Especially since it seems type inference will never be fixed. Think of what this does to someone trying to write oh I don't know some collections.

This is completely nuts! Do you really want to ship another major version which a) cannot figure out not to infer types which you can't access and b) does so reliably in common situations?

scala> def f[A, CC[X]](xs: CC[A]) = xs
warning: there were 1 feature warning(s); re-run with -feature for details
f: [A, CC[X]](xs: CC[A])CC[A]

scala> f(BitSet(1))
res0: scala.collection.AbstractSet[Int] = BitSet(1)

scala> var x: scala.collection.AbstractSet[Int] = res0
<console>:21: error: class AbstractSet in package collection cannot be accessed in package collection
       var x: scala.collection.AbstractSet[Int] = res0
                               ^

And again it's a regression from 2.9.

[scabug]

@adriaanm said:
Work-stealing and crime-solving PR welcome. Please also consider whether all this hyperbole is suitable in a technical forum. The fact that I assigned this to myself and set the fix-by version to what it is, should tell you I would also like to fix this. Instead, I spent a lot of time last week reading and thinking about yet another round of bashing (and sifting through all that chaff for some technical wheat).

[scabug]

@paulp said:
What's hyperbole, that it's nuts? It is nuts. It's even more nuts than these years-long periods of inaction have been completely normalized. Let us not act as if it were a matter of limited resources. Obviously resources are limited, but that is not and never has been the problem.

I will gladly send you a PR to make the Abstract* classes public. That is the only thing I can do. I know how to fix the type computation and it requires a fundamental rework of the typer far beyond what I was able to accomplish when I had better access than I do now and was better paid than I am now.

[scabug]

@adriaanm said:
I'd say it's a bit of an exaggeration to clamor that it's a crime that we haven't gotten around to doing the fundamental rework of the typer that's necessary to fix this properly.

[scabug]

@paulp said:
The crime is the failure to publicize those collections classes, or take some other step with the same effect. They are the front line first parent collections classes, which puts them front and center in every single lub among collections without a sub-super relationship.

[scabug]

@adriaanm said:
It's still a trade-off: as you know (and as I hopefully remember correctly), they were considered implementation artifacts to reduce the bytecode bloat due to the trait encoding. It's great that you found a way to use them to improve type inference, and I'm certainly open to exploring that.

[scabug]

@retronym said:
I'll also note that the AbstractXxx base classes have exposed us to the worst of #3452 (reported as #7374). Mixing in the trait forwarders at the leaves, where Repr is concrete, means that the Java generic signatures are closer to coherent. On its own, that's probably not enough to give up the reductions in bytecode size. But in combination with this problem (hk unification doesn't respect the base-type-seq, so a new parent changed type inference), and also the problem that Paul mentions that inference makes no attempt to infer accessible types, maybe there is an argument to remove them altogether?

[scabug]

@paulp said:
Removing them might be a tough sell, given that all three of the reasons to remove them are scala bugs. I think removing them would be a devastating blow to scala on android. And it was something like 1.4 megabytes savings, which people have presumably normalized, so removing them would amount to donating that much to the library in preference to doing something about those bugs.

I don't know, I'm not the guy to weigh those tradeoffs. I think removing them entirely is probably unwise, but I doubt there are any hail marys coming to fix any of the issues before 2.11. I'll send a PR removing the access limitations.

In case anyone is thinking they don't want to make those classes public because it increases the binary compatibility surface area, I have some bad news: thanks to the leaking of those supposed-to-be-internal types, they're already in the footprint.

object Test {
  def f[A, CC[X]](xs: CC[A]) = xs
  def g = f(scala.collection.immutable.BitSet(1))
}
// public <A extends java/lang/Object, CC extends java/lang/Object> CC f(CC);
//   Signature: (Ljava/lang/Object;)Ljava/lang/Object;

// public scala.collection.AbstractSet<java.lang.Object> g();
//   Signature: ()Lscala/collection/AbstractSet;

In other words there is no such thing as a private type.

[scabug]

@paulp said (edited by @adriaanm on Feb 10, 2014 12:47:12 AM UTC):
workaround for the collections:
scala/scala#3480