RFR: 8079136: Accessing a nested sublist leads to StackOverflowError

[Ivan Gerasimov]

Hi Martin!

>
> I'm afraid of these changes - they are hard to review.
>
> Can't we fix the SOE with a relatively small change to 
> ArrayList.SubList methods that recursively invoke parent methods to 
> use iteration instead, i.e. can't you implement updateSizeAndModCount 
> in the existing SubList class?
>
Well.  Another minor goal I had was to possibly unify two 
implementations of sublists in AbstractList.java and ArrayList.java.
Let me do another try in that direction.
What if sublist classes are made static inner classes, will it look better?

Please see the updated webrev:
WEBREV: http://cr.openjdk.java.net/~igerasim/8079136/03/webrev/

> ---
>
> I would make modCount an argument to updateSizeAndModCount.
>
I did that initially, but later realized that this argument should never 
be different from root.modCount.

> ---
>
> Separate out hot and cold code in subListRangeCheck (although 
> pre-existing code had the same problem)
>
> +    static void subListRangeCheck(int fromIndex, int toIndex, int size) {
> +        if (fromIndex < 0)
> +            throw new IndexOutOfBoundsException("fromIndex = " + 
> fromIndex);
> +        if (toIndex > size)
> +            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
> +        if (fromIndex > toIndex)
> +            throw new IllegalArgumentException("fromIndex(" + fromIndex +
> +                                               ") > toIndex(" + 
> toIndex + ")");
> +    }
> +
>
> if ((fromIndex < 0) | (toIndex > size) | (fromIndex > toIndex)) 
> slowpath();
>
Recently, I investigated this possible way of optimization, and I was 
surprised to discover that javac generates more compact code for logical 
operators, comparing to bitwise operators for booleans.

I've just tried it again to refresh my memory and here are results for a 
simple function:

This >>> void f(int index) { if (index < 0 || index >= size) throw new 
Error(); } <<< compiles into 20 bytecode commads.
This >>> void f(int index) { if (index < 0 | index >= size) throw new 
Error(); } <<< produces 34 commads.

This is because the bitwise or operator really operates on integers.
So, javac first conditionally initializes an auxiliary integer variables 
to either 0 or 1, then ORs them, and then checks the result.
As the result, we have 3 branches in the code above.

Another approach would be to do something like this:
     void f(int index) {
         int x = index | (size - 1 - index);
         if (x < 0)
             throw new Error();
     }
The code length (23) is still a bit greater, comparing to the first 
version, but on the other hand it's got only one branch.
It's still not clear though, if this going to be more efficient or not.

I recommend to leave this code as is for now, and investigate the ways 
to optimize it in a different CR.

> ---
> java style consensus has been converging on: java source files should 
> have exactly one top-level class.  It seems like you changed inner 
> class SubList to be a top-level class - why?
>
Until now, SubList and RandomAccessSubList were top-level classes in 
AbstractList.java.
ArrayList.SubList was an inner class.

Wanting to make their implementations similar, I either had to make all 
of them inner classes (webrev #1), or top-level classes (like in webrev #2).

In my last attempt I made them inner static classes.  Number of changes 
is relatively small, so it might be easier to review.
Would you please take a look?
http://cr.openjdk.java.net/~igerasim/8079136/03/webrev/

Sincerely yours,
Ivan