Java8의 ArrayList.subList()한후 Iterate시 ConcurrentModificationException 발생

ArrayList의 구현이 Java8에서 바뀌면서 Collections.sort()  사용시 ConcurrentModificationException 발생하는 케이스가 있다고 소개한 적 있다.

http://knight76.tistory.com/entry/Java-8-AtomicReference%EC%97%90%EC%84%9C-%EB%A7%8C%EB%82%98%EB%8A%94-ConcurrentModificationException

최근에 Java8 25 이상 java8구현체에서 ArrayList의 subList()를 사용할 때에도 ConcurrentModificationException이 발생할 수 있다. (실제로 발생했다.)

관련 내용이 아래 Qiita 블로그에도 소개되어 있어서 해당 내용을 공유한다. 

http://qiita.com/kamatama_41/items/0b19564e2e72951edb8b

java8 25 이상 에서 subList로 뽑아낸 ArrayList를 소팅(Collections.sort)를 호출하면, Exception이 발생한다. 

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ArrayListSortTest {
 public static void main(String[] args) {
  List<String> list = new ArrayList<String>();
  list.add("bbb");
  list.add("ccc");
  list.add("aaa");

  List<String> subList = list.subList(0, 2);
  // [bbb, ccc]
  System.out.println(subList);

  Collections.sort(list);

  // jdk1.8.0_11 -> [aaa, bbb]
  // jdk1.8.0_25 -> ConcurrentModificationException
  System.out.println(subList);

 }
}

cme 예외가 발생하는 시점은 System.out.println(subList); 이다.

Exception in thread "main" java.util.ConcurrentModificationException

at java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1231)

at java.util.ArrayList$SubList.listIterator(ArrayList.java:1091)

at java.util.AbstractList.listIterator(AbstractList.java:299)

at java.util.ArrayList$SubList.iterator(ArrayList.java:1087)

at java.util.AbstractCollection.toString(AbstractCollection.java:454)

at java.lang.String.valueOf(String.java:2982)

at java.io.PrintStream.println(PrintStream.java:821)

at com.google.location.java8test.ArrayListSortTest.main(ArrayListSortTest.java:22)

at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)

at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)

at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)

at java.lang.reflect.Method.invoke(Method.java:497)

at com.intellij.rt.execution.application.AppMain.main(AppMain.java:140)

Process finished with exit code 1

Collections.sort()의 구현은 List.sort()로 호출하게 되어 있다.

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}

저자가 사용하는 java8 40에서는 ArrayList.sort()는 다음과 같이 구현되어 있다. (참고로, modCount와 ExpectedModCount가 다르면 throw new ConcurrentModificationException이 발생하도록 되어 있다.)

@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

코드상으로는 Collections.sort() 호출 이후 System.out.println()에서 발생한다.

즉, subList 된 ArrayList를 Iterate 하면서 CME 예외가 발생했다.

ArrayList$SubList$ListIterator 구현에서 next() 메소드 호출시 checkForComodification() 메소드로 modCount를 비교하게 되어 있다. 이 때 개수가 안 맞으면 CME 예외가 발생한다. 참고로 remove(), before() 메소드가 호출될 때에도 동일하게 문제가 발생한다.

public Iterator<E> iterator() {
    return listIterator();
}

public ListIterator<E> listIterator(final int index) {
    checkForComodification();
    rangeCheckForAdd(index);
    final int offset = this.offset;

    return new ListIterator<E>() {
        int cursor = index;
        int lastRet = -1;
        int expectedModCount = ArrayList.this.modCount;

        public boolean hasNext() {
            return cursor != SubList.this.size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= SubList.this.size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (offset + i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[offset + (lastRet = i)];
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (offset + i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[offset + (lastRet = i)];
        }

        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = SubList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (offset + i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[offset + (i++)]);
            }
            // update once at end of iteration to reduce heap write traffic
            lastRet = cursor = i;
            checkForComodification();
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                SubList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = ArrayList.this.modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(offset + lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                SubList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = ArrayList.this.modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            if (expectedModCount != ArrayList.this.modCount)
                throw new ConcurrentModificationException();
        }
    };
}

참고로 CopyOnWriteArrayList에서도 동일한 CME 예외가 발생한다. 

이 문제를 해결하기 위해서는 subList() 가 아닌 새로운 ArrayList()로 만들어야 한다.

( 처음에는 subList() 구현 정책에 대해서는 조금 특이하다라는 느낌이 있었다....)

Lists.newArrayList(Iterables.limit(list, fetchsize))와 같이 사용해야 한다.

하지만, 뒤에 설명하겠지만, subList()로 만든 ArrayList는 임시로 써야지 계속 쓰면 안된다!!!! 즉 자바의 철학에 맞지 않다.

참고로, 위의 예제에서 ArrayList 대신 LinkedList를 사용하면 잘 동작하며 전혀 문제가 발생하지 않는다.

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class LinkedListSortTest {
 public static void main(String[] args) {
  List<String> list = new LinkedList<>();
  list.add("bbb");
  list.add("ccc");
  list.add("aaa");

  List<String> subList = list.subList(0, 2);
  // [bbb, ccc]
  System.out.println(subList);

  Collections.sort(list);

  // jdk1.8.0_11 -> [aaa, bbb]
  // jdk1.8.0_25 -> ConcurrentModificationException
  System.out.println(subList);

 }
}

LinkedList에는 sort() 구현이 없어서 상..상위 클래스인 List 인터페이스의 default 메소드인 sort()를 사용한다. 아래 코드가 List.sort() 메소드인데, 아주 간단한 모델로 쓰고 있다. 따라서 CME 예외가 발생하지 않는다.

public interface List<E> extends Collection<E> {
...

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

openjdk에 관련 글을 살펴보면 좋은 내용이 있다.  subList()는 단순히 임시적인 용도 써야지 그 이상으로 쓰면 쓰지 않도록 추천(??!!) 하고 있다. 

https://bugs.openjdk.java.net/browse/JDK-8079444

https://docs.oracle.com/javase/tutorial/collections/interfaces/list.html

Although the subList operation is extremely powerful, some care must be exercised when using it. The semantics of the List returned by subList become undefined if elements are added to or removed from the backing List in any way other than via the returned List. Thus, it's highly recommended that you use the List returned by subList only as a transient object — to perform one or a sequence of range operations on the backing List. The longer you use the subList instance, the greater the probability that you'll compromise it by modifying the backing List directly or through another subList object. Note that it is legal to modify a sublist of a sublist and to continue using the original sublist (though not concurrently).

http://docs.oracle.com/javase/8/docs/technotes/guides/collections/designfaq.html#a26

 The existence of [the List.subList] method means that people who write methods taking List on input do not have to write secondary forms taking an offset and a length (as they do for arrays). 

http://docs.oracle.com/javase/8/docs/api/java/util/List.html#subList-int-int-

The existence of [the List.subList] method means that people who write methods taking List on input do not have to write secondary forms taking an offset and a length (as they do for arrays).