java.util.Sublist throwing StackOverFlowError

Question

Estamos obteniendo ocasionalmente errores StackOverFlowError en la producción relacionados con la realización de una operación SubList. ¿Alguien ha visto algo así antes y sabe lo que podría causarlo?

Este es el código que se llama que provoca el 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); 
    } 
    } 

El resultado:

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

El problema fue causado por el hecho de que breadCrumbs es una LinkedList-- estábamos agregando demasiados elementos a LinkedList y la sublista de llamada expuso este problema.

Answer 2

El método subLista() devuelve una vista el respaldo de la lista original.

Según el 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.)

Usted está haciendo cambios estructurales en la lista, por lo que todas las apuestas están apagadas - nada puede suceder, incluyendo recursión infinita, que es lo que parece estar sucediendo.

Answer 3

He aquí un extracto de la fuente pertinente:

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

Esto indica que StackOverflowErrorl es de alguna manera en referencia a la lista secundaria actual y está llamando así su propia listIterator() en un bucle infinito.

¿De dónde viene el breadCrumbs? ¿Qué dice su getClass()?

Answer 4

No creo que sea por LinkedList. Tengo el mismo error al llamar subList contra la misma lista recursivamente. Creo que cada vez que se llama a la sublista de método, sus índices de inicio/final se insertan en la pila. Si esa lista es enorme y, por lo tanto, demasiadas veces se llama a ese método, se produce StackOverFlowError.

Answer 5

El problema radica en la forma en que AbstractList.java (clase base de ArrayList) implementa el método subList. Crea la sublista (vista aka) por medio de un puntero principal, un desplazamiento y un tamaño. Si llama a subList en dicha sublista, obtiene el puntero principal apuntando a la lista que tiene un puntero principal (etc.)

Algunas operaciones (por ejemplo, agregar) en sublistas funcionan recursivamente. Si tiene una jerarquía muy profunda de punteros padres, obtiene un StackOverflowError.

El siguiente fragmento muestra el problema aislado:

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

Conclusión: No utilice subLista de forma recursiva como esto:

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

conjunto en lugar de la longitud mediante la eliminación de elementos del final.

Un análisis más detallado en mi blog: http://programmingtipsandtraps.blogspot.com/2013/05/javautillistsublist-stackoverflowerror.html

Answer 6

que tenían el mismo problema exacto utilizando tanto ListaEnlazada biblioteca estándar y fastutil objectarraylist (fastutil son una aplicación de memoria rápida y eficiente de la infraestructura de recogida de Java).

Usando

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

provocó el error de stackoverflow. He sustituido con

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

y todo funcionaba bien.

espera que pueda ayudar a