RFR: 8079136: Accessing a nested sublist leads to StackOverflowError

[Daniel Fuchs]

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.

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. What
   new SubList(root, this, ...);
does might thus be more obvious.
(+ it would be easier to review as it wouldn't cause code
   reorganization:-) )

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

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
>>
>>
>>
>