RFR: 8079136: Accessing a nested sublist leads to StackOverflowError

[Louis Wasserman]

Just checking -- IIRC, this will change the semantics of how structural
modifications to a subList of a subList will affect the first subList.  For
example, I believe in the past, removing an element from a subList of a
subList would decrease the size of the first subList by 1, but now the
first subList will represent the same range of indices, and another element
will be moved into that subList.

Is that an accurate representation of current behavior?  Is changing that
behavior acceptable in this context?

On Tue, May 5, 2015 at 11:02 AM Ivan Gerasimov <ivan.gerasimov at oracle.com>
wrote:

> Hi Paul
>
> On 05.05.2015 19:56, Paul Sandoz wrote:
> > 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;
> >      }
> > }
> >
> Thanks for suggestion!
> I should have realized this myself, that there's no need to set parent
> to ArrayList.this.
> It was a left-over from the previous design, when parent was used in
> different ways.
>
> > 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.
> >
> Okay, I'll reorganize it to make SubList classes stand-alone, not inner
> classes.
> Let's see, if it makes the things nicer.
>
> > 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?
>
> I found only a few tests that test some parts of the functionality:
> test/java/util/List/LockStep.java
> test/java/util/Collection/MOAT.java
>
>
> I'll post an update on the code and test soon.
>
> Sincerely yours,
> Ivan
>
>