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

[Stuart Marks]

On 5/5/16 4:34 AM, forax at univ-mlv.fr wrote:
> The problem is that AbstractList is a public class, removing it from the hierarchy is not a backward compatible change,
> so it's not something that can be changed as an after through.

(and AbstractSet and AbstractMap)

I disagree that removing those as superclasses would be backward incompatible, 
because it's not specified anywhere that they're superclasses. The usual problem 
comes from serialization, which exposes the superclass chain as well as 
apparently private classes; the serialization proxy stuff should avoid these 
problems.

If somebody were to write

     if (Set.of(...) instanceof AbstractSet)

the behavior of their code would change, but I'm not worried about that.


>>>   - in the constructor, you should use a local variable here,
>>>         @SafeVarargs
>>>         ListN(E... input) {
>>>             // copy and check manually to avoid TOCTOU
>>>             @SuppressWarnings("unchecked")
>>>             E[] elements = (E[])new Object[input.length]; // implicit
>>>             nullcheck of input
>>>             for (int i = 0; i < input.length; i++) {
>>>                 elements[i] = Objects.requireNonNull(input[i]);
>>>             }
>>>             this.elements = elements;
>>>         }
>>
>> Nice. Will fix.

It turns out that this works well for ListN, but not SetN or MapN.

  307         SetN(E... input) {
  308             Objects.requireNonNull(input);
  309
  310             size = input.length;
  311             elements = (E[])new Object[(int)Math.ceil(EXPAND_FACTOR * 
input.length)];
  312             for (int i = 0; i < input.length; i++) {
  313                 E e = Objects.requireNonNull(input[i]);
  314                 int idx = probe(e);
  315                 if (idx >= 0) {
  316                     throw new IllegalArgumentException("duplicate element: 
" + e);
  317                 } else {
  318                     elements[-(idx + 1)] = e;
  319                 }
  320             }
  321         }

The problem is that, during construction, probe() needs to see the elements 
array and the actual elements as they're inserted. Hoisting the array into a 
local variable and assigning elements only at the end causes probe() to NPE.

I've set aside this change for SetN and MapN.

>>>   - the iterator should not be defined as inner class (with a reference to
>>>   Set2) but
>>>     be defined as a static class that contains a copy of e1 and e2,
>>>     this will save an indirection and avoid to keep a link on the Set if it
>>>     is transient.

I started down this path. It was kind-of OK for Set2 and SetN. For MapN, it 
started to get hairy. Some of the Map's state needs to be passed to its entry 
set, and then it needs to be passed along to the entry set iterator. I started 
to hoist these into static nested classes, but the required new fields and 
constructors to initialize them started to clutter things up.

We can revisit this if you really think this is an optimization, but for now 
I've set this aside.

We can also revisit the restructuring of the iterator to advance the index in 
the constructor and in next().

s'marks