java.util.List.subList StackOverflowError

The other day I came across an interesting problem in one of our products with the program throwing:

Exception in thread "main" java.lang.StackOverflowError
    at java.util.ArrayList$SubList.rangeCheckForAdd(ArrayList.java:1119)
    at java.util.ArrayList$SubList.add(ArrayList.java:963)
    at java.util.ArrayList$SubList.add(ArrayList.java:965)

The code responsible for this looks roughly like this:

    String documentSubType = new String();
    List<String> uids = new ArrayList<String>();

    public void setUid(int index, String value, String documentSubType) {
        while (uids.size() < index + 1) {
            uids.add("");
        }
        uids.set(index, value);
       
        if (documentSubType != null && !documentSubType.isEmpty()) {
            this.documentSubType = documentSubType;
            uids = uids.subList(0, index + 1);
        }
    }

On the whole it looks innocent enough so how comes it still seems to make the stack explode?

The answer lies in the (careless) usage of the subList method. The intention was to set the length of the uids list exactly to the index+1 if certain criteria are met.

Unfortunately subList returns a view on the original list (this is documented) which is implemented in AbstractList by use of a pointer to the parent list (this is not documented). When calling certain operations on such a view, the operations are called recursively on the parent list (this is absolutely not documented).
If you call subList on a view you get a view on a view, meaning you now have a parent hierarchy two levels deep.

If you call the setUid method above a few thousand times you get a parent hierarchy a few thousand levels deep which is then used within a recursive method call and - hey presto - there is your stack overflow.

The following snippet shows the problem isolated:

    public static void main(String[] args) {
        List<String> lst = new ArrayList<String>();
        lst.add(""); 
        for (int i = 0; i < 50000; i++) {

            lst = lst.subList(0, 1);
        }
        lst.add("test2");       
    }

Lessons learned: Do NOT use subList recursively (i.e. on a list that was itself created by a call to subList) because doing so will slow down (many parent pointers to walk through) or crash (StackOverflowError) your program.