RFR: 8079136: Accessing a nested sublist leads to StackOverflowError (original) (raw)

Ivan Gerasimov ivan.gerasimov at oracle.com
Tue May 5 12:55:48 UTC 2015

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

More information about the core-libs-dev mailing list