RFR: 8079136: Accessing a nested sublist leads to StackOverflowError

[Paul Sandoz]

Hi Ivan,

ArrayList
--

You can simplify SubList with:

private final class SubList extends AbstractList<E> implements RandomAccess {
    private final SubList parent;
    private final int offset;
    int size;

    // Top level sub-list
    SubList(int offset, int fromIndex, int toIndex) {
        this.parent = null;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }

    // Sub sub-lst
    SubList(SubList parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }

ArrayList.subList becomes:

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(0, fromIndex, toIndex);
}

And SubList.subList:

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, offset, fromIndex, toIndex);
}

And SubList. updateSizeAndModCount:

private void updateSizeAndModCount(int sizeChange) {
    int modCount = ArrayList.this.modCount;
    for (SubList slist = this; slist != null; slist = slist.parent) {
        slist.size += sizeChange;
        slist.modCount = modCount;
    }
}


AbstractList
--

Similar changes can be made as above to ArrayList.SubList etc.

The construction of sub-lists does indeed require a second take. A comment is worthwhile. IMO such scoping is not necessary for ArrayList, i have actually found it rare to require such scoping so using it when not necessary is rather jarring.


NestedSubList
--

My preference is you use a testng data provider so you don't have to roll your own failure checking and reporting.

Are there any other tests for testing the integrity of sublists?

Paul.


On May 5, 2015, at 9:17 AM, Ivan Gerasimov <ivan.gerasimov at oracle.com> 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