RFR: 8079136: Accessing a nested sublist leads to StackOverflowError

[Ivan Gerasimov]

Thanks Louis for looking at this!

Removing an element from a sub-sublist is done as:
  549         public E remove(int index) {
  550             rangeCheck(index);
  551             checkForComodification();
  552             E result = AbstractList.this.remove(index + offset);
  553             updateSizeAndModCount(-1, AbstractList.this.modCount);
  554             return result;
  555         }

It first removes the element from the root list at the line 552.
Then, it updates sizes of all sublist in the chain at 553, so that sizes 
of sublist and sub-sublist are decreased by one.

Sincerely yours,
Ivan

On 06.05.2015 1:02, Louis Wasserman wrote:
> 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 <mailto: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
>