Migrating methods in Collections

[Brian Goetz]

Teasing apart the differences:

Essential differences:

  - Arguments to contains/remove (Object vs E).  This comes down to 
variance; for value-instantiated generics, V is the only logical choice, 
whereas for reference instantiated generics (erased or not!) we have to 
contend with ? extends/super T as well.  And because we don't have <U 
super T> inference variables, sometimes we use Object instead of <U 
super T>.

  - Type arguments to xxxAll (Collection<?> vs Collection<? extends 
E>.)  Same basic problem, but the treatment is different, because of 
irregularities in generics.

  - Interaction with arrays.  Fundamental mismatch; (reference) arrays 
are covariant, generics are invariant.  Made more fuzzy by the lack of 
<U super T> inference variables. That value arrays are also invariant 
seems an opportunity to make things fit better.

  - Methods that use null to signal absence (Map.get(), Queue.poll()).  
Slightly related: Map.put() returns what was previously there, but for 
value maps, there's no obvious sentinel for "not there" other than the 
default value, which means that the return value is mostly useless.

Opportunistic differences:
  - widening index size (bleeds into size())

  - Possibly replace some methods with more flexible lambda-powered 
counterparts (removeAll, indexOf, toArray(generator))


Implementation possibilities:
  - The T.eq type (today I am calling it T.rasure, tomorrow I'll call it 
something else) cleanly addresses the contains/remove and toArray 
issues, as well as Object.equals.

  - The xxxAll problems are messy, because there is very little room for 
varying a generic type in a signature when overriding. However, I could 
imagine some wiggle room here for interacting with the T.rasure types.  
Alternately we migrate to new names.

  - The null-signaling methods can be migrated to new total methods.

  - Migrating value-consuming methods to Predicate-consuming methods is 
a pure API evolution choice; we can keep the spirit of the old sigs, or 
upgrade them as we see fit.

  - Widening index sizes will require some as-yet-undisclosed firepower, 
but it is essentially the same trick that would allow us to migrate 
reference-Optional to value-Optional.

On 12/24/2015 11:17 AM, Doug Lea wrote:
> On 12/24/2015 11:01 AM, Brian Goetz wrote:
>> Cowardly of you to not put some form of toArray() in AnyCollection :)
>>
>
> My intent was to keep at AnyX level only those things that
> would never get you into null, boxing, or erasure trouble.
> (Which led to some some jdk8 deja vu of jdk5 deja vu!)
> I don't know of best replacement for toArray or
> even whether it should be mandated. But I tried pass two
> also with List and Map sketches. Not meant as a proposal,
> just as a way to help focus on current and upcoming issues.
> Including for example Pair<K,V> vs Map.Entry.
>
> interface AnyCollection<E> {
>     boolean isEmpty();
>     boolean contains(E e); // not Object
>
>     boolean add(E e);
>     boolean remove(E e);   // not Object
>     boolean removeIf(Predicate<? super E> filter);
>     void clear();
>
>     Spliterator<E> spliterator();    // iterator() omitted
>     Stream<E> stream();
>     Stream<E> parallelStream();
>
>     boolean addAll(AnyCollection<? extends E> c);
>     boolean containsAll(AnyCollection<? extends E> c); // not 
> Collection<?>
>     boolean removeAll(AnyCollection<? extends E> c);   // not 
> Collection<?>
>     boolean retainAll(AnyCollection<? extends E> c);   // not 
> Collection<?>
>
>     // to address other issues:
>     long elementCount();   // not size()
>     AnyCollection<E> adding(E e);
>     AnyCollection<E> removing(E e);
> }
>
> interface Collection<E> extends AnyCollection<E> {
>     int size();
>     boolean contains(Object o); // contravariant arg
>     boolean remove(Object o);   // contravariant arg
>
>     Iterator<E> iterator();
>
>     Object[] toArray();
>     <T> T[] toArray(T[] a);
>
>     boolean equals(Object o);   // declare for sake of Collection spec
>     int hashCode();             // declare for sake of Collection spec
>
>     boolean containsAll(AnyCollection<?> c);
>     boolean removeAll(AnyCollection<?> c);
>     boolean retainAll(AnyCollection<?> c);
> }
>
>
> interface AnyList<E> extends AnyCollection<E> {
>     void replaceAll(UnaryOperator<E> operator);
>     void sort(Comparator<? super E> c);
>     E at(long index);
>     E setAt(long index, E element);
>     void addAt(long index, E element);
>     boolean addAllAt(long index, AnyCollection<? extends E> c);
>     E removeAt(long index);
>     long findFirst(E e);
>     long findLast(E e);
>     // subList?
> }
>
> interface List<E> extends AnyList<E> {
>     E get(int index);
>     E set(int index, E element);
>     void add(int index, E element);
>     boolean addAll(int index, AnyCollection<? extends E> c);
>     E remove(int index);
>     int indexOf(Object o);
>     int lastIndexOf(Object o);
>     ListIterator<E> listIterator();
>     ListIterator<E> listIterator(long index);
>     List<E> subList(int fromIndex, int toIndex);
> }
>
>
> interface AnyMap<K,V> { // too bad not: extends AnyCollection<Pair<K,V>>
>     boolean isEmpty();
>     long mappingCount();   // as above; not size()
>
>     boolean containsKey(K key);
>     boolean containsValue(V value);
>
>     Optional<V> at(K key);
>     V at(K key, V defaultValue);
>
>     boolean putAt(K key, V value);
>     V installAt(K key, V value); //  putIfAbsent, but return current val
>     boolean replaceAt(K key, V value);
>     boolean replaceAt(K key, V oldValue, V newValue);
>
>     boolean removeAt(K key);
>     boolean removeAt(K key, V value);
>     void clear();
>
>     Spliterator<K> keySpliterator();
>     Stream<K> keyStream();
>     Spliterator<V> valueSpliterator();
>     Stream<V> valueStream();
>     Spliterator<Pair<K,V>> spliterator(); // Pair?
>     Stream<Pair<K,V>> stream();
>
>     void putAll(AnyMap<? extends K, ? extends V> m);
>     void forEach(BiConsumer<? super K, ? super V> action);
>     void replaceAll(BiFunction<? super K, ? super V, ? extends V> fun);
>
>     // Might need renaming because of null return as sentinel
>
>     V computeIfAbsent(K key, Function<? super K, ? extends V> fun);
>     V computeIfPresent(K key, BiFunction<? super K, ? super V, ? 
> extends V> fun);
>     V compute(K key, BiFunction<? super K, ? super V, ? extends V> fun);
>     V merge(K key, V value, BiFunction<? super V, ? super V, ? extends 
> V> fun);
> }
>
> interface Map<K,V> extends AnyMap<K,V> {
>     int size();
>     boolean containsKey(Object key);
>     boolean containsValue(Object value);
>     V get(Object key);
>     V getOrDefault(Object key, V defaultValue);
>     V put(K key, V value);
>     V putIfAbsent(K key, V value);
>     V remove(Object key);
>     boolean remove(Object key, Object value);
>     V replace(K key, V value);
>
>     Set<K> keySet();
>     Collection<V> values();
>     Set<Map.Entry<K, V>> entrySet();
>
>     boolean equals(Object o);
>     int hashCode();
> }