Migrating methods in Collections

[Brian Goetz]

> What we want, I think, is for the signature of those methods to be:
>  - x(Object) // for reference instantiations
>  - x(T)      // for value instantiations
>
> That Object is the erasure of T is a powerful connection we can hang 
> our hat on here.  I think there are at least three linguistic 
> approaches to rescuing these methods:
>
>  - contravariant type args (<U super T>)
>  - some sort of peeling that treats x(T) and x(Object) as separate 
> methods, but usually defaults/bridges one of them, so you just have to 
> implement the appropriate one
>  - some way of expressing a signature that means "T when a value, or 
> Object when a reference"
>
> All of these have cons, but we've got a long enough list to suggest 
> that there is *a* solution here, and maybe there's a better one if we 
> pull on that string some more.
>

Let me summarize the options here in slightly more detail.

Super-ivars.  If we could express contravariant method tvars, then we 
could write:

interface Objectible<any T> {
     <U super T> boolean equals(U u);
}

where

class Object implements Objectible<raw> {
     boolean equals(U u);
}

Now, there is a common equals() method which has the signature 
equals(Object) for reference types and equals(V) for value types.  The 
same applies to Collection.contains and friends.

Cons:
  - contravariance is poisonfor type systems
  - performance impact of specialized generic methods on critical methods


Collapsing method pairs.  Here, Objectible has two methods

     boolean equals(Object o)
     boolean equals(V other)

We can give the former a default for value types (an unboxing bridge) 
and for reference types, the two collapse to the same signature, and we 
tell the compiler/VM that this is a feature and that these are actually 
the same method.  This likely will want some way of declaring that these 
methods are related and intended to be collapsed.

For methods like contains(), we have to do the same -- declare a 
collapsible method pair (with an appropriate ref-default bridge). Users 
may have to implement both in some cases.


Partial refinement.  Here, we have a total method

      boolean contains(V v)

and we "refine" it for erased instantiations:

     <where ref V> boolean contains(Object o)

We teach the compiler that it is allowable (perhaps with some additional 
declaration) to widen the signature of a total method to its erasure in 
erased instantiations.


Honesty.  Here, we find a non-scary way of denoting the dependent type 
(erased T ? erasure(T) : T), which I believe is *actually* the type we 
want (and most of the other approaches are an attempt to avoid naming 
that-which-must-not-be-named).  The complexity of this comes from the 
fact that ref instantiations are variant (and we are using Object as a 
stand-in for <U super T>, both for historical compatibility purposes and 
because type inference was so weak in Java 5) and value instantiations 
are invariant.  Something has to bridge the gap -- either providing the 
right variance tools (super-ivars), pretending to split the methods 
(collapsing pairs/partial refinement), or recognizing a weird-but-honest 
"maybe erased, maybe not" type.

As an strawman purely for expository purposes, suppose we call this type 
T.eq (to evoke "the type of things that T could be compared to for 
equality" -- finding a non-sucky syntax is obviously needed).  Then we have:

     boolean equals(T.eq other)
     boolean contains(T.eq other)
     T.eq[] toArray()

etc.  This is the cleanest solution from a type system perspective: it 
captures the actual type we want, and it works well for toArray as well 
as the others (and when we get to the discussion about "how do I code 
the equals() method", it will show up again, and when we get to the part 
about representing a generic class in bytecode, it will show up yet 
again.)  Peter's suggestion is another path for getting to this 
approach.  It is safe to assign a T to a T.eq; it is an unchecked 
conversion to go from T.eq to T.

We've scribbled with ways to denote this type: T.something, ~T, |T|, 
Something<T>, Something[T], ? something T, etc. None seem that great 
(though the first form seems the most promising, if an appropriately 
evocative "something" could be identified.)  But if we can see our way 
clear to admitting that this is actually the type we're looking for, 
many other problems (including several we've not discussed yet) simply 
fold away.


*Approach**
* 	*Pros**
* 	*Cons**
*
Super-ivars
	Straightforward semantics.
Will be viewed as plugging a hole in existing language.
	Much bigger hammer than needed.
Significant potential complexity (including potential undecidability.)
Potential performance challenges.
Method pairs
	Reasonable partial-method modeling of the problem.
	Users may have to implement both methods.
Likely will need a linguistic mechanism to indicate that two methods 
form a pair.
Partial refinement
	Reasonable partial-method modeling of the problem.
	Users may have to implement both methods.
Likely will need a linguistic mechanism to indicate that two methods 
form a pair.
Complicates semantics of partial methods.
Naming it
	Honest modeling of the problem.
There is only one method, so users only have to implement one method, 
and clients only have to reason about one method.
No need to express relationships between two methods.
The need for something like this also shows up in method implementations.
	It's new and weird, and will take users some time to get used to (but 
possibly mitigated if we had a better name.)


Of these, I think the method-pairs approach dominates the partial 
refinement approach, and I'd like to avoid the super-ivars approach 
(because it trades one problem for several others.)

I think the "honest" approach has the best overall characteristics (by a 
wide margin) -- *if* we can identify a syntactic form that doesn't make 
developers run away screaming, which is a big if.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/valhalla-spec-experts/attachments/20151223/8dee75b1/attachment-0001.html>