java.util.Sublist throwing StackOverFlowError

Question

Ci sono errori occasionali di StackOverFlowError nella produzione relativi a un'operazione di Sottolista. Qualcuno ha mai visto qualcosa di simile prima e sa cosa potrebbe causarlo?

Questo è il codice che viene chiamato che innesca l'errore:

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

Il risultato:

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

Il problema è stato causato dal fatto che breadCrumbs era una LinkedList: aggiungevamo troppi elementi a LinkedList e la chiamata a subList ha esposto questo problema.

Answer 2

Il metodo sottolista() restituisce una vista sostenuto dalla lista originale.

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

si apportano modifiche strutturali alla lista, in modo da tutte le scommesse sono spenti - nulla può accadere, tra cui una ricorsione infinita, che è ciò che sembra accadere.

Answer 3

Ecco un estratto della fonte pertinente:

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

Questo StackOverflowError indica che è in qualche modo l riferendo alla corrente sottolista e sta chiamando così la propria listIterator() in un ciclo infinito.

Da dove proviene il breadCrumbs? Cosa dice il suo getClass()?

Answer 4

Non penso sia dovuto a LinkedList. Ho avuto lo stesso errore durante la chiamata di subList contro la stessa lista in modo ricorsivo. Penso che ogni volta che viene chiamata la sottoclasse del metodo, i suoi indici inizio/fine vengano messi in pila. Se quell'elenco è enorme e quindi troppe volte viene chiamato quel metodo, si verifica StackOverFlowError.

Answer 5

Il problema sta nel modo in cui AbstractList.java (classe base di ArrayList) implementa il metodo subList. Crea il sottolista (vista aka) per mezzo di un puntatore padre, un offset e una dimensione. Se si richiama l'elenco secondario su tale sottocartella si ottiene il puntatore padre che punta all'elenco che ha un puntatore padre (ecc.)

Alcune operazioni (ad esempio aggiunta) su sottoliste funzionano in modo ricorsivo. Se hai una gerarchia molto profonda di puntatori genitore ottieni un StackOverflowError.

Il seguente frammento mostra il problema isolato:

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

Conclusione: Non utilizzare sottolista ricorsivo simili:

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

invece impostare la lunghezza rimuovendo elementi dalla fine.

un'analisi più dettagliata sul mio blog: http://programmingtipsandtraps.blogspot.com/2013/05/javautillistsublist-stackoverflowerror.html

Answer 6

Ho avuto lo stesso problema esatto utilizzando sia libreria standard LinkedList e fastutil objectarraylist (fastutil sono un'implementazione rapida ed efficiente la memoria di quadro per la raccolta Java).

Utilizzando

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

causato l'errore StackOverflow. Ho sostituito con

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

e tutto ha funzionato bene.

Si spera che possa essere d'aiuto