【Java】ConcurrentModificationExceptionから学ぶListと拡張for文の仕組み

## 始めに
業務中にConcurrentModificationExceptionが発生するケースに出会い、エラーについて調べていく中で勉強になったことがあったのでまとめてみました。

### この記事の対象者
・Javaの勉強をしている方
・ConcurrentModificationExceptionって何？と思っている方

## ConcurrentModificationExceptionとは
Java SE 11 & JDK11 Documentには以下のように定義されています。
>この例外は、オブジェクトの並行変更を検出したメソッドによって、そのような変更が許可されていない場合にスローされます。
たとえば、あるスレッドがCollectionで反復処理を行っている間に、別のスレッドがそのCollectionを変更することは一般に許可されません。 通常、そのような環境では、反復処理の結果は保証されません。
この例外は、オブジェクトが別のスレッドによって並行して更新されていないことを必ずしも示しているわけではありません。 単一のスレッドが、オブジェクトの規約に違反する一連のメソッドを発行した場合、オブジェクトはこの例外をスローします。 たとえば、フェイルファスト・イテレータを持つコレクションの反復処理を行いながら、スレッドがコレクションを直接修正する場合、イテレータはこの例外をスローします。

少し難しく書かれていますが、一つのコレクションに対してループ（=反復処理）を行っている際に、 __別の場所からそのコレクションに対して変更が発生する__ とエラーが発生するようです。

## ConcurrentModificationExceptionが発生するケース
上記引用にもあるように、ConcurrentModificationExceptionは複数スレッドだけでなく単一スレッドでも発生します。
発生するケースとして、今回は単一スレッドの場合・複数スレッドの場合のケースをご紹介します。
### 1. 拡張for文内でリスト内の要素を操作した時
拡張for文内でループ対象に指定したリストから要素を取り除こうとすると発生します。

```java:エラーが発生するソースコード
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(10);

    for (Integer num : list) {
        // numが10以上の場合要素を削除する
        if (num >= 10) {
            list.remove(num);
        }
    }
    System.out.println(list);
```

```:結果
Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1013)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:967)
	at Main.main(Main.java:12)

```

ただし、 __リストの最後から2番目の要素を削除した場合は発生しません__ 。

```java:エラーが発生しないソースコード
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(10);

    for (Integer num : list) {
        // numが3の場合要素を削除する
        if (num == 3) {
            list.remove(num);
        }
    }
    System.out.println(list);
```
```:結果
[1, 2, 10]
```

### 2. 並列処理において同一リスト内の要素を操作した時
あるスレッドが拡張for文を回している最中に別スレッドから同一のリストの要素を操作した場合に発生します。
```java:エラーが発生するソースコード
    List<Integer> list = new ArrayList<>();
	list.add(1);
	list.add(2);
	list.add(3);
	list.add(10);

	new Thread(() -> {
		for (Integer num : list) {
    		try {
				Thread.sleep(3000);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			System.out.println("現在のnum:" + num);
		}
	}).start();

	try {
		Thread.sleep(1000);
	} catch (InterruptedException e) {
		e.printStackTrace();
	}
	list.add(100);
	System.out.println(list);
```
```:結果
java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1013)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:967)
	at com.sample.SampleApplication.lambda$0(SampleApplication.java:22)
	at java.base/java.lang.Thread.run(Thread.java:833)
```
## ConcurrentModificationExceptionが発生する仕組み
エラー発生時のコンソールを見ると、ArrayList.javaのnextメソッド内で呼ばれているcheckForComodificationメソッドでエラーが発生しているようです。

早速ArrayList.javaの処理を見ていきたいのですが、
前提として、 __拡張for文は内部ではイテレータ(コレクションの要素を順にアクセスする)を使用して__ 処理をしています。

Java言語仕様における拡張for文の記述箇所を見ると、拡張for文はコンパイル時下記のように __イテレータを使った処理に読み替えられる__ ようです。

>If the type of Expression is a subtype of Iterable, then the translation is as follows.
```java:
    for (I #i = Expression.iterator(); #i.hasNext(); ) {
        {VariableModifier} TargetType Identifier =
            (TargetType) #i.next();
        Statement
    }
```

では実際の処理を見てみましょう。

まずnext()メソッドを見ると、処理の始めに毎回checkForComodification()メソッドが実行されていることがわかります。

```java:ArrayList.java
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
```

次にcheckForComodification()メソッド見てみると、
modCountとexpectedModCountに差異がある場合ConcurrentModificationExceptionをスローしているようです。

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

modCountとexpectedModCountはそれぞれ下記のようにカウントされている変数です。
- __modCount__ 
実際にリストが変更された回数。
remove()メソッド内（他にもclear()やadd()など）でインクリメントされている。

```java:remove()で呼び出しているfastRemove()メソッド
    private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
    }
```

- __expectedModCount__
teratorによりリストが変更された回数。
Iterator作成時点でのmodCountが記録されている。
```java:Iterator初期化時に作成される変数
    private class Itr implements Iterator<E> {
        int cursor;
        int lastRet = -1;
        int expectedModCount = modCount;
    }
```
実際にどのような値が入っているのか下記画像を見てみましょう。

![modCOunt.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710642/f8bcf1b8-b9b9-e847-2730-beaed99a5dec.png)


このように、リストは __更新回数__ を保持しています。
拡張for文では __ループを始める時点での「これまで更新された回数」__ を保持しておき、次の要素を調べる際に __その回数と「現時点での更新された回数」を比較し__ 回数が異なればエラーをスローしているのです。

### リストの最後から2番目の要素を削除した場合はなぜ発生しないのか？
先ほどConcurrentModificationExceptionが発生するケース1にて、
リストの最後から2番目の要素を削除した場合はこのエラーは発生しないと書きましたが、これはなぜでしょうか？

拡張for文ではhasNext()メソッドを呼び、 __現在位置とリストのサイズが一致していない場合次の要素にアクセスする__ ように制御しています。

最後から2番目の要素を削除する場合、現在位置とリストのサイズは下記のようになります。

![起きない仕組み.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710642/18283967-a08e-3fd6-483e-7f8a89d8edf8.png)


このように、リストの最後の要素の位置が移動することでループが終了し、
modCountとexpectedModCountに差異があっても更新回数の比較が行われないため、正常終了します。

しかし、ここで気をつけたいのが最後の要素に対してはプログラムで用意した判定が実行されていないということです。

下記のように[1, 2 ,3 ,10]から3以上の要素を削除しようとした場合、
結果は[1, 2]ではなく[1, 2, 10]となっており、最後の要素である「10」は判定されていないことがわかります。
```java:エラーが発生しないケース
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(10);

    for (Integer num : list) {
        // numが3以上の場合要素を削除する
        if (num >= 3){
            list.remove(num);
        }
    }
    System.out.println(list);
```
```:結果
[1, 2, 10]
```

## ConcurrentModificationExceptionを解決する方法
ここからは、ConcurrentModificationExceptionを解決する方法を3つ紹介していきます。

### 1. Iteratorを使用する
ArrayListではなくIteratorのremove()を使うことでエラー発生を防ぐことができます。
```java:Iteratorのremove()を使用する
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(10);

    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()) {
        Integer num = iterator.next();
        // numが10以上の場合要素を削除する
        if(num >= 10) {
            iterator.remove();
        } 
    }
    System.out.println(list);
```
```:結果
[1, 2, 3]
```
### 2. removeIf()メソッドを使用する
拡張for文ではなくremoveIf()を使用してフィルタリングすることでリスト内の要素削除が可能になります。
```java:removeIf()メソッドを使用する
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(10);
        
    // numが10以上の場合要素を削除する
    list.removeIf(num -> (num >= 10));

    System.out.println(list);
```
```:結果
[1, 2, 3]
```
### 3. CopyOnWriteArrayListを使用する
CopyOnWriteArrayListでリストを生成することで拡張for文内でリストの要素の削除が可能になります。

CopyOnWriteArrayListを使うことで、リストに対する変更は全てリストのコピーに対して行われるようになります。

Java SE 11 & JDK11 Documentには以下のように定義されています。
>基になる配列の新しいコピーを作成することにより、すべての推移的操作 (add、set など) が実装される ArrayList のスレッドセーフな変数です。

```java:CopyOnWriteArrayListを使用する
    List<Integer> list = new CopyOnWriteArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(10);
        
    for (Integer num : list) {
        // numが10以上の場合要素を削除する
        if (num >= 10) {
            list.remove(num);
        }
    }

    System.out.println(list);
```
```:結果
[1, 2, 3]
```

## 最後に
今回はConcurrentModificationExceptionが発生するケースと原因・対策についてまとめてみました。
原因を理解する中でArrayList内部の処理を見たことで、拡張for文やListについての理解も深めることができました。
## 参考文献
- [Java言語仕様](https://docs.oracle.com/javase/specs/jls/se8/html/jls-14.html#jls-14.14.2)
- [Java Platform, Standard Edition & Java Development Kit　バージョン11 API仕様
](https://docs.oracle.com/javase/jp/11/docs/api/java.base/java/util/ConcurrentModificationException.html)
- [【Java】拡張for文で発生するエラーについて](https://nuxtblog.work/blog/rjga-emxt0/#google_vignette)