RFR(m): 8139233 add initial compact immutable collection implementations

[Stuart Marks]

Hi Peter,

Great comments and questions. Responses below....

On 5/4/16 12:20 AM, Peter Levart wrote:
> - What's the point of 11 overloaded List.of() methods for 0 ... 10-arity if you
> then invoke the var-args ListN(E...input) constructor that does the array
> cloning with 8 of them? The same for Set.of()... I suggest that you don't clone
> the array in ListN(E... input) constructor but only in List.of(E ... input) method.

Yes, it is silly to have fixed-arg overloads to provide a fast path, and then to 
turn around and use them in a varargs context that creates an array and then 
copies them, after which the constructor clones the array. The main point, 
though, is that the API allows for a fast path. Even if the current 
implementation doesn't take advantage of it, it can be updated later without 
changing the API.

There's tension here between avoiding copying and central enforcement of all the 
invariants. I'll probably need to do something like adding non-cloning 
constructors and possibly fixed-arg constructor overloads to avoid varargs array 
creation. This is a bit more than I want to do at the moment, but I agree it's 
important.

I've filed JDK-8156071 to track this.

> - {Set0, Set1, Set2}.contains(null) return false, but SetN.contains(null) throws
> NPE. All List{0,1,2,N}.contains(null) return false. What should be the correct
> behavior? ConcurrentHashMap.keySet().contains(null) throws NPE for example.

Good catch. I did some investigation, and the results are interesting. All of 
the List implementations allow nulls. But the all the Queue and Deque 
implementations all disallow nulls, and they all return false from contains(null):

  - ArrayBlockingQueue
  - ArrayDeque
  - ConcurrentLinkedDeque
  - ConcurrentLinkedQueue
  - LinkedBlockingDeque
  - LinkedBlockingQueue
  - LinkedTransferQueue
  - PriorityBlockingQueue
  - PriorityQueue

The following Set implementations disallow nulls, and they throw NPE from 
contains(null):

  - ConcurrentHashMap$KeySetView
  - ConcurrentSkipListSet

The following Map implementations disallow null keys, and they throw NPE from 
containsKey(null) and containsValue(null):

  - ConcurrentHashMap
  - ConcurrentSkipListMap
  - Hashtable

Things seem pretty consistent across the null-unfriendly collections: on Deques 
and Queues, contains(null) is allowed, but on Sets and Maps, contains(null) 
throws NPE. (I have no idea why things are this way.)

Although there are no existing Lists that disallow nulls, based on the Queue and 
Deque behavior, the current behavior of contains(null) on the new List 
implementations seems reasonable.

I will update/override the various contains() methods on the new Set and Map 
implementations to adjust them to throw NPE.

This area could use more tests, too. I've filed JDK-8156074 to track this.

> - SetN.probe(E pe) and MapN.probe(K pk) invoke ee.equals(pe) and ek.equals(pk)
> respectively. Although it should be logically equivalent, it has been a practice
> in collections to invoke the .equals() method on the passed-in argument rather
> than on individual elements of the collection.

Huh, I didn't know that. Good catch. Will fix.

> - Should unchecked exceptions from constructors be wrapped with
> InvalidObjectException in SerialProxy.readResolve() or does the Serialization
> infrastructure already perform the equivalent?

Another good question! The serialization mechanism does deal with any exception 
that's thrown here, since readResolve is invoked reflectively. But basically it 
just rethrows runtime exceptions. Callers are presumably prepared to catch 
ObjectStreamExceptions, so wrapping exceptions thrown from the constructors in a 
suitable exception instance (probably InvalidObjectException) seems like a 
sensible thing to do.

Thanks,

s'marks