Kengo's blog

Technical articles about original projects, JVM, Static Analysis and TypeScript.

Listを直接変更してもIteratorがConcurrentModificationExceptionをスローしない件

容量拡張コストの低いArrayListの実装中に見つけた、AbstractListが持つ既知の不具合についてまとめておきます。

不具合概要

ArrayListなどの同期化されないListの実装に対してIterator利用中に要素を変更すると、ConcurrentModificationExceptionをスローするというのがJava6の仕様です。

このクラスの iterator および listIterator メソッドによって返される反復子は、「フェイルファスト」です。反復子の作成後に、反復子自体の remove または add メソッド以外の方法でリストが構造的に変更されると、反復子は ConcurrentModificationException をスローします。このように、並行して変更が行われると、反復子は、将来の予測できない時点において予測できない動作が発生する危険を回避するために、ただちにかつ手際よく例外をスローします。

ArrayList (Java Platform SE 6)

しかしSunから入手できるJDKJREの実装には、要素を変更しても例外がスローされないことがあるという既知の不具合が指摘されているそうです。

再現条件

IteratorがListの最後から2番目の要素を処理している間に、Listからその要素を削除する」ことで再現できます。
本来ならばまだ処理できる要素が残っているのですから、Iterator#next()メソッドが実行されて例外が投げられることが期待されます。しかし実際には(要素が残っているのに)Iterator#hasNext()がfalseを返してしまい、例外をスローすることなく不正な状態で反復処理を終えてしまうのです。
この不具合はhasNext()メソッドがAbstractListの変更チェック機構(modCountフィールド)を利用しないことに起因すると言えます。

// 再現用コード

public static void main(String[] args) {
	final List<Integer> list = new ArrayList<Integer>();
	for (int i = 0; i < 5; ++i) list.add(Integer.valueOf(i));
	try {
		for (final Iterator<Integer> iter = list.iterator(); iter.hasNext();) {
			// 3 を 2や4 に変更すると正しく動作する
			if (iter.next().equals(Integer.valueOf(3))) list.remove(3);
		}
	} catch (final ConcurrentModificationException expected) {
		// 期待した通りの動作
		return;
	}
	throw new RuntimeException("Listを変更したのにIteratorが例外を投げませんでした");
}

仕様を守って正しくお使いください

この不具合の影響を受けるのはIteratorに対して並行した要素変更を行うコードであり、仕様を満たさないコードです。ですからAPI仕様書にもこのバグに対する言及はありません。例外に頼った実装をしないように警告する内容が記載されていることからも、List利用者が仕様を正しく守ってコーディングすることが期待されていると考えられます。

通常、非同期の並行変更がある場合、確かな保証を行うことは不可能なので、反復子のフェイルファストの動作を保証することはできません。フェイルファスト反復子は最善努力原則に基づき、ConcurrentModificationException をスローします。したがって、正確を期すためにこの例外に依存するプログラムを書くことは誤りです。「反復子のフェイルファストの動作はバグを検出するためにのみ使用すべきです」。

ArrayList (Java Platform SE 6)

仕様の持つ大切さとAPI提供者の期待することについて学ぶ良い事例であると思いました。