java.util.Sublist throwing StackOverFlowError

Question

Мы получаем случайные ошибки StackOverFlowError в производстве, связанные с выполнением операции SubList. Кто-нибудь видел что-то подобное раньше и знает, что может вызвать это?

Это код, который вызывается, который вызывает ошибку:

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); 
    } 
    } 

Результат:

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) 
... 

Answer 1

Проблема была вызвана тем, что breadCrumbs был LinkedList - мы добавляли слишком много элементов в LinkedList и вызывали subList, чтобы выявить эту проблему.

Answer 2

Метод Подсписок() возвращает представление подкрепленную первоначального списка.

Согласно 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.)

Вы делаете структурные изменения в список, так что все ставки выключены - ничего может произойти, в том числе и бесконечной рекурсии, которая является то, что, как представляется, происходит.

Answer 3

Вот выдержка из соответствующего источника:

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

Это StackOverflowError указывает, что l каким-то образом со ссылкой на ток подсписка и, таким образом, вызывая его собственный listIterator() в бесконечном цикле.

Откуда берутся breadCrumbs? Что говорит его getClass()?

Answer 4

Я не думаю, что это связано с LinkedList. Я получил ту же ошибку при вызове subList в том же списке рекурсивно. Я думаю, что каждый раз, когда вызывается метод subList, его начальные/конечные индексы помещаются в стек. Если этот список огромен, и поэтому слишком много раз этот метод вызывается, возникает StackOverFlowError.

Answer 5

Проблема заключается в том, как AbstractList.java (базовый класс ArrayList) реализует метод subList. Он создает подсписку (aka view) с помощью родительского указателя, смещения и размера. Если вы вызываете subList в таком сублисте, вы получаете родительский указатель, указывающий на список, который сам имеет родительский указатель (и т. Д.).

Некоторые операции (например, добавление) на подсписках работают рекурсивно. Если у вас очень глубокая иерархия родительских указателей, вы получаете StackOverflowError.

Следующий фрагмент кода показывает проблему изоляции:

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");  
} 

Заключение: Не используйте Подсписок рекурсивно следующим образом:

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

Вместо установки длины путем удаления элементов из конца.

Более Детальный анализ на моем блоге: http://programmingtipsandtraps.blogspot.com/2013/05/javautillistsublist-stackoverflowerror.html

Answer 6

У меня был точно такой же проблема с использованием как стандартная библиотеки LinkedList и fastutil objectarraylist (fastutil являются быстрым и эффективным внедрением памяти рамок сбора Java).

Использование

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

вызвало StackOverflow ошибку. Я заменил

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

и все было в порядке.

Надеюсь, что это поможет