De-virtualizing abstract collections would increase performance and decrease bytecode bloat for common use cases–without tying the hands of implementors. Conceptually, operations on abstract collections become syntactic sugar for inlined code templates. You opt-in to dynamic behavior by choosing subtypes that override extension methods with virtual ones. The root collections then become an encapsulation of their elements, but not an abstraction over operations on those elements; you can still perform such operations on these collections, but the compiler statically binds the implementation rather than indirecting to the run-time type's vtable-provided version. Collection sub-families–parallel, non-strict, and the like–override generic extension methods with virtual ones, and any value statically typed to such a collection works in the usual object-oriented way.
import collection.generic.CanBuildFrom
import language.implicitConversions
trait Traversable[+A] extends Any {
// From identifies a Scope in which to look for CanBuildFroms
type From <: collection.Traversable[A]
def foreach[U](f: A => U): Unit
}
trait Iterable[+A] extends Any with Traversable[A] {
type From <: collection.Iterable[A]
def iterator: Iterator[A]
override def foreach[U](f: A => U): Unit = ???
}
trait IndexedSeq[+A] extends Any with Iterable[A] {
type From <: collection.IndexedSeq[A]
override def iterator: Iterator[A] = ???
def length: Int
def apply(index: Int): A
}
final class IntArray(val array: Array[Int]) extends AnyVal with IndexedSeq[Int] {
type From <: collection.mutable.WrappedArray.ofInt
@inline def length: Int = array.length
@inline def apply(index: Int): Int = array(index)
}
object Traversable {
// this implicit conversion lifts the From type out of the collection
@inline implicit def ForTraversable[A](self: Traversable[A]) =
new ForTraversable[self.From, A](self)
final class ForTraversable[From, A](val self: Traversable[A]) extends AnyVal {
def foldLeft[B](z: B)(op: (B, A) => B): B = ???
def map[B, That](f: A => B)(
implicit bf: CanBuildFrom[From, B, That]): That = ???
}
}
object Iterable {
@inline implicit def ForIterable[A](self: Iterable[A]) =
new ForIterable[self.From, A](self)
final class ForIterable[From, A](val self: Iterable[A]) extends AnyVal {
// statically overrides ForTraversable.foldLeft
@inline def foldLeft[B](z: B)(op: (B, A) => B): B = {
val iter = self.iterator
var result = z
while (iter.hasNext) result = op(result, iter.next())
result
}
// statically overrides ForTraversable.map
@inline def map[B, That](f: A => B)(
implicit bf: CanBuildFrom[From, B, That]): That = {
val b = bf()
val iter = self.iterator
while (iter.hasNext) b += f(iter.next())
b.result
}
}
}
object IndexedSeq {
@inline implicit def ForIndexedSeq[A](self: IndexedSeq[A]) =
new ForIndexedSeq[self.From, A](self)
final class ForIndexedSeq[From, A](val self: IndexedSeq[A]) extends AnyVal {
// statically overrides ForIterable.foldLeft
@inline def foldLeft[B](z: B)(op: (B, A) => B): B = {
var result = z
var i = 0
val until = self.length
while (i < until) {
result = op(result, self(i))
i += 1
}
result
}
// statically overrides ForIterable.map
@inline def map[B, That](f: A => B)(
implicit bf: CanBuildFrom[From, B, That]): That = {
val b = bf()
var i = 0
val until = self.length
b.sizeHint(until)
while (i < until) {
b += f(self(i))
i += 1
}
b.result
}
}
}Because the core collection interfaces define so little, collection sub-families don't have to conform to an overly broad set of requirements. Non-strict views, for example, don't need to pretend to use builders.
trait TraversableView[+A] extends Traversable[A] {
// virtualize map, with an incompatible, but generally source compatible, signature
def map[B](f: A => B): TraversableView[B]
}Abstract collections behave polymorphically according to their static type.
class Test {
def iterableFold(xs: Iterable[String]) = xs.foldLeft(new StringBuilder)(_ ++= _)
def indexedFold(xs: IndexedSeq[String]) = xs.foldLeft(new StringBuilder)(_ ++= _)
def iterableMap(xs: Iterable[String]) = xs map (_.trim)
def indexedMap(xs: IndexedSeq[String]) = xs map (_.trim)
def sumIntArray(xs: IntArray) = xs.foldLeft(0)(_ + _)
def mapIntArray(xs: IntArray) = xs map (_ + 1)
}Generated bytecode for the foldLeft examples:
public scala.collection.mutable.StringBuilder iterableFold(Iterable<java.lang.String>);
Code:
0: getstatic #16 // Field Iterable$ForIterable$.MODULE$:LIterable$ForIterable$;
3: getstatic #21 // Field Iterable$.MODULE$:LIterable$;
6: astore_2
7: new #23 // class scala/collection/mutable/StringBuilder
10: dup
11: invokespecial #27 // Method scala/collection/mutable/StringBuilder."<init>":()V
14: astore 4
16: astore_3
17: aload_1
18: invokeinterface #33, 1 // InterfaceMethod Iterable.iterator:()Lscala/collection/Iterator;
23: astore 5
25: aload 4
27: astore 9
29: aload 5
31: invokeinterface #39, 1 // InterfaceMethod scala/collection/Iterator.hasNext:()Z
36: ifeq 66
39: aload 5
41: invokeinterface #43, 1 // InterfaceMethod scala/collection/Iterator.next:()Ljava/lang/Object;
46: astore 6
48: aload 9
50: checkcast #23 // class scala/collection/mutable/StringBuilder
53: aload 6
55: checkcast #45 // class java/lang/String
58: invokevirtual #49 // Method scala/collection/mutable/StringBuilder.$plus$plus$eq:(Ljava/lang/String;)Lscala/collection/mutable/StringBuilder;
61: astore 9
63: goto 29
66: aload 9
68: checkcast #23 // class scala/collection/mutable/StringBuilder
71: areturn
public scala.collection.mutable.StringBuilder indexedFold(IndexedSeq<java.lang.String>);
Code:
0: getstatic #64 // Field IndexedSeq$ForIndexedSeq$.MODULE$:LIndexedSeq$ForIndexedSeq$;
3: getstatic #69 // Field IndexedSeq$.MODULE$:LIndexedSeq$;
6: astore_2
7: new #23 // class scala/collection/mutable/StringBuilder
10: dup
11: invokespecial #27 // Method scala/collection/mutable/StringBuilder."<init>":()V
14: astore 4
16: astore_3
17: aload 4
19: astore 10
21: iconst_0
22: istore 9
24: aload_1
25: invokeinterface #75, 1 // InterfaceMethod IndexedSeq.length:()I
30: istore 5
32: iload 9
34: iload 5
36: if_icmpge 73
39: aload_1
40: iload 9
42: invokeinterface #79, 2 // InterfaceMethod IndexedSeq.apply:(I)Ljava/lang/Object;
47: astore 6
49: aload 10
51: checkcast #23 // class scala/collection/mutable/StringBuilder
54: aload 6
56: checkcast #45 // class java/lang/String
59: invokevirtual #49 // Method scala/collection/mutable/StringBuilder.$plus$plus$eq:(Ljava/lang/String;)Lscala/collection/mutable/StringBuilder;
62: astore 10
64: iload 9
66: iconst_1
67: iadd
68: istore 9
70: goto 32
73: aload 10
75: checkcast #23 // class scala/collection/mutable/StringBuilder
78: areturn