Array covariance

[Brian Goetz]

Since the Burlington meeting, Simms has been prodding me to offer an 
alternative to supporting array covariance for value arrays. John and I 
kicked around the following idea yesterday. At this point, I’d call it a 
half-baked sketch, but so far it seems promising.


        Why covariance at all?

First, let’s talk about why arrays in Java are covariant in the first 
place. And the reason is, unless you have either generics or covariant 
arrays, you can’t write methods that operate on all (or almost all) 
array types, like Arrays.sort(). With covariance, we can write

|void sort(Object[], Comparator) { … } |

and we can sort any (reference) array. I wasn’t in the room, but I 
suspect that array covariance was something that was grudgingly accepted 
because it was the only way to write code that worked on arbitrary arrays.

Now, imagine if we had (invariant) generics in Java 1.0. Then we would 
have written

|<T> void sort(T[], Comparator<T>) { … } |

This makes more sense from a user-model perspective, but what do we 
erase |T[]| to? Unless we also had covariant arrays, we’d not be able to 
erase |T[]| to |Object[]|, but there may be a smaller hammer we can use 
than covariant arrays for this.

Covariance isn’t bad in itself, but the limitations of Java 1.0 arrays 
belie the problem — layout polymorphism. Covariance among arrays of 
Object subtypes is fine because they all have the same layout, but 
primitive arrays were left out from the beginning. We could extend 
covariance to value/primitive arrays — we’ve prove its possible — but 
there’s a cost, which is largely: we take what is a clean and 
predictable performance model for array access, and pollute it with the 
possibility of megamorphic access sites.


        What else is missing about arrays?

Just as primitives are outside of the generic type system (we can’t say 
|ArrayList<int>|, yet), so are arrays. There’s no way to express “any 
array” in the type system; methods like |System.arraycopy| are forced to 
use |Object| as a proxy, and then dynamically ensure that what’s passed 
is actually an array:

|void arraycopy(Object sourceArray, int sourceStart, Object destArray, 
int destStart, int length) |

It would be much nicer if we could say |AnyArray| instead of |Object| 
here; it would be saying what we mean, and would allow us to move some 
type checking from runtime to compilation time. (It also might give us a 
path to not having to write nine versions of |Arrays.fill()|.)

Similarly, there are lots of operations on arrays that are painful, 
ad-hoc, and require VM intrinsification to perform well, like 
|Arrays.copyOf()|.

(Plus, there’s the usual litany of array problems — no final elements, 
no volatile elements, fixed layout, etc.)


        Arrays are primitive

The reason for having arrays in the language and VM is the same reason 
we have primitives — they are a compromise of OO principles to gain a 
practical performance model. There’s few good things about arrays, but 
one of them is they have simple, transparent cost models in time and 
space. Polluting |Object[]| with layout-polymorphism compromises the 
cost model.

The analogy we should be thinking of is:

    array is-to collection as primitive is-to object

That is, arrays are the ground types that our higher-typed programs 
bottom out in (or specialize to), not necessarily the types we want in 
people’s faces.


        What would arrays look like in Valhalla?

Obviously, we’d like for value arrays to be supported at least as well 
as other arrays. Right now, without array covariance, we’re back in the 
same situation the Java 1.0 designers were — that if you want to write 
|Arrays.sort()|, you need covariance. Currently we have no way to extend 
the various nine-way method sets, even if we were willing to write a 
tenth method.

But, in Valhalla, we don’t want 9- or 10-way method sets — we want a 
single method. We want for |Arrays.fill()|, for example, to be something 
like:

|<any T> void fill(T[] array, T element) |

and not have to have eight siblings to clean up the primitive cases.

But, even this syntax is paying homage to the irregularity of 
array-as-primitive. I think what we’d really want is something like

|interface NativeArray<any T> { int length(); T get(int index); void 
set(int index, T val); Class<T> componentType(); } |

and then we’d retrofit |Foo[]| to implement |NativeArray<Foo>|. (We’d 
likely make NA a restricted interface, that is only implemented by 
native arrays, for now.) Then, our single fill method could be (in LW100):

|<any T> void fill(NativeArray<T> array, T element) |

(Impatient readers will want to point out that we could generify over 
the index parameter as well. One impossible problem at a time.)

And similarly, arraycopy can be:

|void arraycopy(NativeArray src, int srcStart, NativeArray dest, int 
destStart, len) |

Bold claim: In such a world, /there is no need for arrays to be 
covariant/. If you want to operate on more than one kind of array, use 
generics. If you want covariance, say |NativeArray<? extends T>|.


        Getting there in steps

Suppose we start in steps; let’s start with an erased interface, 
suitable for later generification:

|interface NativeArray { int length(); Object get(int index); void 
set(int index, Object val); Class<?> componentType(); } |

We make NA a restricted interface (reject any classes that explicitly 
try to implement it at class load time, as if it were sealed), and 
inject it as a super type into all existing array types (including 
primitives and values.) The language overloads the |[]| operators to 
bind to the |get| and |set| methods and continues to simulate the 
synthetic |length| field. Now, someone who wants to write just one 
version of |Arrays.fill| can do so:

|void fill(NativeArray a, Object element) { for (int i=0; i<a.length; 
i++) a[i] = element; } |

Note that this works for all arrays now — values, primitives, object, 
with some boxing. OK, progress.

One obvious wart in the above is that we’ve taken a step back in terms 
of type safety. We’d like for NA to be generic in its element type, but 
we can’t yet use values or primitives as type parameters. Suppose we 
said instead:

|interface NativeArray<T> { int length(); T get(int index); void set(int 
index, T val); Class<T> componentType(); } |

and treated |Foo[]| (for reference Foo) as implementing |NA<Foo>|, and 
for values and primitives, treat |V[]| as implementing |NA<V.box>|. This 
makes our erased generics story work for:

|<T> fill(NativeArray<T> a, T element) |

but lays down some potholes for migration to specialized generics, as 
when we get to Valhalla, we’d like for |V[]| to implement |Array<V>|, 
not |Array<V.box>|. So, this is a hole to fill, but it seems a promising 
direction.

The result is that we have monomorphic type profiles at |aaload| sites, 
and potentially polymorphic profiles at |invokeinterface 
NativeArray.get| sites — which is more justifiable than polluting aaload 
profiles. And when we get to full specialization, many of these 
polymorphic profiles may flatten out (as we can safely speculate on 
|T[]| at specialized |NativeArray<T>| sites.)


        Overloading

The |NA| story works nicely with existing overload rules too. If we 
currently have:

|fill(int[], int) fill(Object[], Object) |

we can add in an overload

|<T> fill(NativeArray<T>, T) |

Existing source and binary code that wants one of the original methods 
will continue to get it, as |Object[]| is more specific than 
|NativeArray<? extends Object>| and so will be selected in preference to 
the NA version. So the new method would only be selected by value 
instantiations, since none of the existing versions are applicable.

(Over time, we might want to remove some of the hand-specialized 
versions, and turn them into bridges for the specialized generic 
version, reducing us from 9 methods to one method with 8 bridges.)


        Translation

The real stumbling block is: what do we do with |T[]| in generic APIs. 
Currently, we erase these to array-of-erasure-of-T, so usually 
|Object[]|. This is one of the things pushing us towards covariance. 
But, can we change this translation? What if we erased |T[]| to 
NativeArray?

Obviously, we’d have a binary compatibility issue, that we’d have to 
fill in with bridges. And these bridges might conflict with actual 
overloads that take |NativeArray|:

|void m(T[] array) { … } void m(NativeArray array) { … } |

but, maybe since there’s no existing code that uses NA, that’s OK.

This triggers all the issues discussed recently regarding migration — 
there’s a 2x2 matrix of { source, binary } x { client, subclass } 
compatibility.

When used in argument position, passing an |Object[]| where a NA is 
expected is fine, since |Object[]| is a subtype of NA. The problem would 
come when |T[]| is used in return position (or as a field.) But, these 
are fairly rare, and implementations (at least in the JDK) are well behaved:

|// Stream<T> T[] toArray(IntFunction<T[]> generator) // Arrays <T> T[] 
copyOf(T[] array) |

So erasing to NA, with bridges, and performing the same generic type 
checks we do (perhaps with some extra casts) may be a viable path for 
managing the source compatibility aspects.

OK, so if we erase |T[]| to NativeArray, what does that buy us? It 
/almost/ means we can write our |Arrays.*| methods with an extra overload:

|<T> void fill(NativeArray<T>, T) |

But, we don’t have generics over values yet, hrm. So this doesn’t quite 
get us to our Arrays.* methods, dang.

OK, let’s put this idea on hold for a bit.


        Zag before you zig

We could write an erased version:

|void fill(NativeArray, Object) |

which will catch all the flat value arrays, but we lose the compile-time 
type checking that the element type is correct.

But, we may be able to pull a move here. What if we were to allow 
any-vars (in L10) /as long as the resulting signature was invariant in 
T/? Then we could say (with erased generics!)

|<any T> void fill(NativeArray<T>, T.box element) |

because this would erase to |(NativeArray, Object)V|.In other words, a 
small down payment on specialized generics (where it supports 
compile-time type checking, but wouldn’t actually affect any bytecode 
generation), might allow us to write the generic-over-arrays code we want.

So, the compiler would type-check that the passed value is an instance 
of (or convertible to) the box type for which the passed array is an 
array, and then erase the array to NativeArray and erase the element to 
its box. This would even work for |int[]| arrays.

Then, in L100, we migrate NativeArray to be a true specializable 
interface, and we migrate the |fill| method to

|<any T> void fill(NativeArray<T>, T element) |


        Summary

There are lots of holes to fill in, but:

  * We need a suitable translation target for |T[]| in specialized
    generics regardless. One path is full covariance (including for
    primitive arrays); another is to migrate the relatively few methods
    that truck in |T[]| to a different translation.
  * We are going to need some tools for signature migration no matter
    what. I’ve outlined two under separate cover; one is minty-bridges
    (where a method/field says “I am willing to respond to this
    alternate descriptor”), and the other is a technique for migrating
    signatures so that if subclasses override the old signature, we have
    a way to restore order. We are going to need these to get to L100
    regardless.
  * We can borrow some bits from the future to provide a programming
    model for value arrays that is not tied to covariance, and that
    heals the rift between separate array types, which currently are
    completely unrelated. It also moves megamorphic call sites to where
    they belong — |invokeinterface|.

​