We have experienced a problem with a StackOverflowException when calling ArrayList.add(). The application added data to the end of a list to find different possible solutions. Attempts that lead to a dead end are then truncated from the list with a call to List.subList(). This might appear like a good way of reusing the data which is still valid.

The problem arises when we do something similar to:

List list = new ArrayList();
// try solution x
list.addAll(someRangeX);
list = list.subList(0, x);
// try solution y
list.addAll(someRangeY);
list = list.subList(0, y);
// try solution z
list.addAll(someRangeZ);
list = list.subList(0, z);
// repeat for thousands of solutions
//…
list.addAll(someRangeXYZ);
// -> StackOverflowException is thrown

The answer to why this is a problem is in the first words of the JavaDoc for List.subList(). “Returns a view of a potion of the list”. The method subList() will return a new object, which has a reference back to the original list. So every time we modify the list, we have to update the parent, parents parent, parents parents parent, and so on. Enough calls to subList() will give us such a deep recursion within ArrayList that we get a StackOverflowException (at java.util.ArrayList$Sublist.add(ArrayList:1005))

This is what the code looks like in ArrayList:


public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}


Out solution is to instantiate a new List containing the sub-list elements, but no reference back to the original list.