ArrayList#subListを生成後に元のlistをsortしてはいけない

概要

Jdkのバージョンを新しいの(1.8.0_11 -> 1.8.0_25)に上げたらArrayList#subList絡みの処理でConcurrentModificationExceptionが発生するようになってしまいました。
以下エラーが出るようなサンプルコード

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

原因

1. Collections#sortの実装内容が変わっていた

Collections#sortでやっていた実装がList#sortのデフォルト実装に移行され、Collections#sortはList#sortに処理を委譲するようになった。

1.8.0_11

// Collections#sort
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void sort(List<T> list) {
	Object[] a = list.toArray();
	Arrays.sort(a);
	ListIterator<T> i = list.listIterator();
	for (int j=0; j<a.length; j++) {
		i.next();
		i.set((T)a[j]);
	}
}

// List#sort
default void sort(Comparator<? super E> c) {
    Collections.sort(this, c);
}

1.8.0_25

// Collections#sort
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void sort(List<T> list) {
	list.sort(null);
}

// List#sort
@SuppressWarnings({"unchecked", "rawtypes"})
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);
	}
}

2. 1の結果Collections#sortがArrayList#sortを呼ぶようになり、ArrayList#sortが呼ばれるようになった

ここで、ArrayList#modcount(正確に言うとAbstractListのメンバ)がインクリメントされるという副作用が新たに発生する事になる。

ArrayList#sort

@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++;
}

3. 2の結果sort後にsubListをiteratorでイテレーションする場合、ConcurrentModificationExceptionが発生するようになった

ArrayList$SubList$ListIterator

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

final void checkForComodification() {
    if (expectedModCount != ArrayList.this.modCount)  // ここのチェックに引っかかる
        throw new ConcurrentModificationException();
}

その他

• LinkedListはsortメソッドの独自実装は無く、List#sort(デフォルトメソッド)を使うようになっているので、例外は発生しない
• CopyOnWriteArrayListの場合は例外が発生した
• この辺の挙動はListの実装者に委ねられている…？？

結論

subListをsortするためにもとのlistをsortするのは危険なのでやめよう！