CODEWITHSUNDEEP
javaerror-handlingstack-overflow
BestPractices
BestPractices

Reputation: 12876

java.util.Sublist throwing StackOverFlowError

We are getting occasional StackOverFlowError errors in production related to doing a SubList operation. Has anyone seen something like this before and know what could cause it?

This is the code that gets called that triggers the error:

  FacesContext context = FacesContext.getCurrentInstance();
    String newViewID = context.getViewRoot().getViewId();

    if (newViewID != null) {
     if (breadCrumbs.contains(newViewID)) {
      // Trims the list upon going back to allow for multiple back button requests.  
      // This is lightweight and not intended for a complex circular navigation.
      breadCrumbs = breadCrumbs.subList(0, breadCrumbs.indexOf(newViewID) + 1);
     } else {
      breadCrumbs.add(newViewID);
     }
    }

The result :

Caused By: java.lang.StackOverflowError
 at java.util.SubList$1.<init>(AbstractList.java:688)
 at java.util.SubList.listIterator(AbstractList.java:687)
 at java.util.SubList$1.<init>(AbstractList.java:688)
 at java.util.SubList.listIterator(AbstractList.java:687)
 ...

Upvotes: 6

Views: 2645

Answers (6)

besil
besil

Reputation: 1379

I had the exact same problem using both LinkedList standard library and fastutil objectarraylist (fastutil are a fast and efficient memory implementation of Java collection framework).

Using 

window = window.subList(index+1, window.size());

caused stackoverflow error. I replaced with 

window = new LinkedList<>( window.subList(index+1, window.size()) );

and everything worked fine.

Hopes it can help

Upvotes: 3

rli
rli

Reputation: 1885

The problem lies in the way AbstractList.java (base class of ArrayList) implements the subList method. It creates the sublist (aka view) by means of a parent pointer, an offset and a size. If you call subList on such a subList you get parent pointer pointing to the list which itself has a parent pointer (etc.)

Some operations (e.g. add) on sublists work recursivly. If you have a very deep hierarchy of parent pointers you get a StackOverflowError.

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.set(0, "test");
        lst = lst.subList(0, 1);
    }

    lst.add("test2");       
}

Conclusion: Do not use subList recursively like this:

breadCrumbs = breadCrumbs.subList(0, breadCrumbs.indexOf(newViewID) + 1);

Instead set the length by removing elements from the end.

More detailled analysis on my blog: http://programmingtipsandtraps.blogspot.com/2013/05/javautillistsublist-stackoverflowerror.html

Upvotes: 0

chance
chance

Reputation: 6487

I don't think it is because of LinkedList. I have got the same error while calling subList against the same list recursively. I think that each time the method subList is called, its begin/end indices are pushed in stack. If that list is huge and therefore too many times that method is called, StackOverFlowError occurs.

Upvotes: 0

BestPractices
BestPractices

Reputation: 12876

The problem was caused by breadCrumbs being a LinkedList-- we were adding too many items to the LinkedList and calling subList exposed this problem.

Upvotes: 0

BalusC
BalusC

Reputation: 1108692

Here's an extract of the relevant source:

681    public ListIterator<E> listIterator(final int index) {
...
687        return new ListIterator<E>() {
688            private ListIterator<E> i = l.listIterator(index+offset);

This StackOverflowError indicates that l is somehow referring to the current sublist and is thus calling its own listIterator() in an infinite loop.

Where does the breadCrumbs come from? What does its getClass() say?

Upvotes: 0

Jim Garrison
Jim Garrison

Reputation: 86764

The subList() method returns a view backed by the original list.

According to the javadoc:

The semantics of the list returned by this method become undefined if the backing list (i.e., this list) is structurally modified in any way other than via the returned list. (Structural modifications are those that change the size of this list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.)

You are making structural changes to the list, so all bets are off -- anything can happen, including infinite recursion, which is what appears to be happening.

Upvotes: 6

Related Questions