RFR: 8079136: Accessing a nested sublist leads to StackOverflowError

[Ivan Gerasimov]

On 05.05.2015 13:23, Daniel Fuchs wrote:
> On 05/05/15 10:58, Ivan Gerasimov wrote:
>> Thank you Daniel for taking look at it!
>>
>> On 05.05.2015 11:14, Daniel Fuchs wrote:
>>> Hi Ivan,
>>>
>>> Have you considered to simply override/change subList(int fromIndex,
>>> int toIndex)
>>> in SubList and RandomAccessSubList - so that 'l'/'parent' points
>>> always to the original
>>> root list (instead of being a sublist of sublist of sublist)?
>>>
>> With this fix, both SubList and RandomAccessSubList are made private
>> inner classes of AbstractList.
>> So now we have a pointer to the original root list, which is
>> AbstractList.this in addition to the parent field.
>> All the access methods are implemented to call the corresponding methods
>> of this root list.
>>
>> However, we still need to keep a reference to the immediate parent
>> (which might also be a sublist).
>> When the leaf sublist is modified, its modCount and size fields are
>> adjusted.
>> The same adjustment has to be done to all the members of the sublist 
>> chain.
>
> Ah, I see. That's what I missed. Thanks for the explanation!
> It's fortunate that sublists are not Serializable.
>
> Keeping the implementation package (not inner), renaming 'l' to parent,
> and adding a 'root' parameter could however make the changes less
> obscure.
>
I converted the SubList into an inner class to make the implementations 
for AbstractList.SubList and ArrayList.SubList similar.
It might be not worth doing so, but I thought it would be easier to 
maintain those classes, if they have similar structure.

> Given that SubList is itself an AbstractList, then syntaxes like
>   AbstractList.this.new SubList(this, ...);
> can become a bit intricate - since SubList inherit the ability
> of having an inner SubList of its own.

AbstractList.this.new SubList() was used just for that -- to avoid 
SubList become an inner class of itself.
I learned it hard way that 'new SubList()' could not be used used here :)

> What
>   new SubList(root, this, ...);
> does might thus be more obvious.
> (+ it would be easier to review as it wouldn't cause code
>   reorganization:-) )
>
If ArrayList.SubList and AbstractList.SubList are unified, the code 
reorganization would be made somewhere anyway :)

> Note: I'm not an expert of collections, so you might want to wait for
> further feedback from the experts of the field.
>
Thank you anyway!

Sincerely yours,
Ivan


> best regards,
>
> -- daniel
>
>
>>> It seems to me that overriding sublist to create a sublist based on
>>> 'l'/'parent' instead of basing it on 'this' would solve the same 
>>> problem
>>>  with much less modifications... Or am I maybe missing something?
>>>
>> We have to keep both references: one to the root list, and the other to
>> the immediate parent list.
>> The first reference is used to pass the access requests.
>> The second is used to maintain modCount and size fields of all the
>> sublists in the chain.
>>
>> Sincerely yours,
>> Ivan
>>
>>> best regards,
>>>
>>> -- daniel
>>>
>>> On 5/5/15 9:17 AM, Ivan Gerasimov wrote:
>>>> Hello!
>>>>
>>>> When creating a sublist with List.subList(), it keeps a reference to
>>>> its parent.
>>>> Then, when accessing (get(), set(), add(), remove(), etc.) the
>>>> sublist, it recursively calls the corresponding methods of its parent.
>>>> This recursion, when deep enough, can cause StackOverflowError.
>>>>
>>>> The only reason to do things recursively here, is the need to update
>>>> modCount and size of all the parents.
>>>> So, the proposal is to update these fields in a loop.
>>>>
>>>> A few cleanups were done along the way.
>>>>
>>>> Would you please help review the fix?
>>>>
>>>> BUGURL: https://bugs.openjdk.java.net/browse/JDK-8079136
>>>> WEBREV: http://cr.openjdk.java.net/~igerasim/8079136/0/webrev/
>>>>
>>>> Sincerely yours,
>>>> Ivan
>>>
>>>
>>>
>>
>
>
>