java.util.Sublist rzucając StackOverFlowError

Question

Otrzymujemy sporadyczne błędy StackOverFlowError w produkcji związane z wykonywaniem operacji SubList. Czy ktoś wcześniej widział coś takiego i wie, co może spowodować?

Jest to kod, który zostanie wywołany, która wyzwala błąd:

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

Rezultat:

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

Problem został spowodowany przez to, że breadCrumbs jest listą typu LinkedList - dodawaliśmy zbyt wiele elementów do listy danych połączonych i wywoływanie sublisty ujawniło ten problem.

Answer 2

Sposób podmenu() zwraca widok poparte oryginalnej listy.

Według 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.)

możliwość wprowadzania zmian konstrukcyjnych do listy, więc wszystkie zakłady są wyłączone - coś może się zdarzyć, w tym nieskończonej rekurencji, co jest, co wydaje się być dzieje.

Answer 3

Oto wyciąg z odpowiedniego źródła:

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

Ten StackOverflowError wskazuje l jest w jakiś sposób odnosi się do prąd podmenu a zatem wywołanie własny listIterator() w nieskończonej pętli.

Skąd pochodzi breadCrumbs? Co mówi jego getClass()?

Answer 4

Nie sądzę, że jest tak z powodu LinkedList. Mam ten sam błąd podczas wywoływania sublisty na tej samej liście rekursywnie. Myślę, że za każdym razem, gdy wywoływana jest nazwa podelistyczna metody, jej indeksy początkowy/końcowy są wciskane w stos. Jeśli ta lista jest ogromna i dlatego zbyt wiele razy ta metoda jest wywoływana, pojawia się StackOverFlowError.

Answer 5

Problem leży w sposobie, w jaki metoda AbstractList.java (klasa podstawowa ArrayList) implementuje metodę subList. Tworzy podlistę (aka view) za pomocą wskaźnika rodzica, przesunięcia i rozmiaru. Jeśli wywołasz podelistę na takiej podsieci, otrzymasz wskaźnik nadrzędny wskazujący na listę, która sama ma wskaźnik rodzica (itp.)

Niektóre operacje (na przykład dodawanie) na podlistach działają rekurencyjnie. Jeśli masz bardzo głęboką hierarchię wskaźników rodzicielskich, otrzymasz komunikat StackOverflowError.

Poniższy fragment pokazuje problem izolacji:

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

Wniosek: Nie używaj podmenu rekurencyjnie tak:

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

Zamiast ustawić długość poprzez usunięcie elementów od końca.

Więcej Drobiazgowy analiza na moim blogu: http://programmingtipsandtraps.blogspot.com/2013/05/javautillistsublist-stackoverflowerror.html

Answer 6

miałem dokładnie ten sam problem przy użyciu zarówno LinkedList biblioteki standardowej i fastutil objectarraylist (fastutil są szybkie i efektywne wdrożenie pamięć ram gromadzenia Java).

Korzystanie

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

stackoverflow spowodował błąd. Wymieniłem na

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

i wszystko działało bez zarzutu.

Nadzieja, że ​​może pomóc