RFR: 8079136: Accessing a nested sublist leads to StackOverflowError

[Ivan Gerasimov]

Thank you Doug for your comments!

On 08.05.2015 20:10, Doug Lea wrote:
> On 05/08/2015 10:49 AM, Ivan Gerasimov wrote:
>>> I believe that they also break the AbstractList.subList spec.
>>> http://docs.oracle.com/javase/8/docs/api/java/util/AbstractList.html#subList-int-int- 
>>>
>>>
>
>> I think that the proposed fix formally conforms to the spec.
>
> That would surprise me. The spec says "The returned list is backed by 
> this list"
> and "The subclass's set(int, E), get(int), add(int, E), remove(int), 
> addAll(int, Collection) and removeRange(int, int) methods all delegate 
> to the corresponding methods on the backing abstract list".
>
> It is possible that no differences could be detected, but it would take
> some effort to prove.
>

Hm.  Let me try.

We have two options:
1) Sublist of an arbitrary AbstractList, which is not SubList itself.
2) Sublist of another SubList.

For the first option the conformance is almost obvious:
The AbstractList is referenced as root, and all the methods mentioned 
above delegate to the corresponding methods of the root.
Basically, for this case, all the changes can be though as the field 
rename (l -> root) and minor code rearrangements.

For the second option, the proof can be done by induction.
We have a base case (a sublist of the very first level) proven above.
Now, suppose we sublist a, whose parent is another sublist (so that 
a.parent is not null).
We want to see that a call to a.add(index, e) will be delegated to 
a.parent.set().
That's true, because:
- it's easy to see that if the check a.rangeCheckForAdd(index) passed, 
then a.parent.rangeCheckForAdd(index) will pass too, because the allowed 
range of indices for a is enclosed into the allowed range of indices for 
a.parent.
- it's also easy to see that if the check a.checkForComodification() 
passed, then a.parent.checkForComodification() will pass too, because it 
compares a.modCount with the root.modCount, and a.parent.modCount could 
not be updated without also modifying root.modCount.
- calling a.add(index, e) results in a call to root.add(index + 
a.offset, e). We can think of it as a call to a.parent.add(index + 
a.parent.offset, e). Thus, taking into account the difference between 
a.offset and a.parent.offset (which is the index of the sublist a in the 
list a.parent), we have a clear delegation here from a to a.parent.
- updating a.parent.size and a.parent.modCount is done after the call to 
root.add() comples, in the same way it was done in a recursive call.

The same reasoning can be given for all other methods: set(), get(), 
remove() and so on.

As we've done the induction step, we've completed the proof.
Didn't  I miss something?

>
>>
>> However, I'm not really sure why all this details have to be listed 
>> in the javadoc.
>> Can we just remove them? (with the CCC, of course)
>
> You can't remove specs that subclass implementations were allowed to
> depend on unless you can prove (not just test) that there are no
> consequences. (I suppose the CCC might decide otherwise.)
>
What I meant was that it's not clear how the subclasses of AbstractList 
can depend on the fact that the SubList class has some *private* fields.

>>
>>> The reason that flattened forms were not used is that each
>>> layer does not in general know the class of its parent.
>>>
>>
>> I'm inclined to create another regression test which will 
>> systematically check
>> the behavior of sublists.
>
> How would you do so for arbitrary AbstractList subclasses?
>
An arbitrary AbstractList can either use the default 
AbstractList.subList() method, or override it.
In the first case, all the sublists (and sublists of sublists, and so 
on) are going to be of type SubList (or RandomAccessSubList).
Any operation on a sublist ends up as a call to the corresponding method 
of the root AbstractList, no matter how the sublists are organized.
Thus, we can test their behavior and check if the corresponding methods 
of the root are called correctly or not.

If, on the other hand, the AbstractList.subList() was overridden, the 
sublists must be of some type independent from our SubList.
So, we're not interested in this case.

>
>>> It would be possible (and easy) to create a specialization for the
>>> java.util.Arrays.ArrayList class (i.e., the kind returned by
>>> Arrays.asList(a).subList), which would also fix the SOE problem
>>> in this particular case.
>>>
>>
>> Yes.  The same can be done for Collections.SingletonList too.
>> If AbstractList had a base class, that implements sublists without 
>> tracking down
>> any structural modifications, it could be used as the base class for
>> Arrays.ArrayList and Collections.SingletonList.
>>
>> I think it should better be done as a separate enhancement, though.
>>
>
> Conservatively, this solution seems OK as the *only* enhancement;
> it avoids the reported SOE, and has no further unintended consequences.
>

Thanks. I think I'll file an enhancement request for this.
However, I'm still hoping to have the fix for the AbstractList/ArrayList 
approved too.

Sincerely yours,
Ivan