ArrayListのソースを読んでみた

# JJUGナイト・セミナーで発表しました
2016年11月21日に概要をお話ししました。スライドはこちらです。

<iframe src="//www.slideshare.net/slideshow/embed_code/key/ucGfhdcDC5pv25" width="595" height="485" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> <div style="margin-bottom:5px"> <strong> <a href="//www.slideshare.net/JSUXDesign/arraylist-javasdk" title="ArrayListをじっくり読んでみた - JavaコアSDKを読む会を社内でやって気づいたこと -" target="_blank">ArrayListをじっくり読んでみた - JavaコアSDKを読む会を社内でやって気づいたこと -</a> </strong> from <strong><a target="_blank" href="//www.slideshare.net/JSUXDesign">JustSystems Corporation</a></strong> </div>

以下は詳細版となります。

# なぜいまArrayListのソースを読むのか

## JavaコアSDKのソースを読もうと思った

ソースレビューで幾度となく指摘する`null`チェックや、長すぎるメソッド、複雑だったり重複していたりするコードに業を煮やし、これはいっちょJavaコアSDKのソースを読む会とかを開催すると、「ほ～なるほど」と気づきが得られて、スキルのベースアップに役立つだろう、と思って社内で読コード会をやってみた。

↓社内Qiitaでの参加者募集の記事（抜粋）
![社内Qiitaでの読コード会募集.PNG](https://qiita-image-store.s3.amazonaws.com/0/101293/221cbbb6-08d6-b24a-af20-426aed967de0.png)

## ArrayListを選んだ理由

* 皆が使う
* `java.lang.String`はテクニックがすごすぎてたぶん重い
* ほどよいボリューム

# 実際にやってみたらば

JDK 1.8.0_102 の `java.util.ArrayList` のコードは1460行。これを先頭から1行ずつ読んでいく。1回1時間で、第6回で完走。

## 全然人気がなかった・・・

初回こそまあまあ人が集まったものの2回目からは結構寒い状況に…。Lombokとか便利なものがある今日この頃、コアSDKのソースを読むというのはちょっとマニアックすぎたか…。
終わってから何人かに話を聞いてみたら、読コード会の様子を毎回Qiitaに詳しくレポートしたので、それを見るだけで参加しなくてもOKそうだと思った人もいるとか…むむむ。

## でも気づきはいろいろあった

リソースの節約方法や、パフォーマンスを考慮しての実装など、うなるポイントが発見できたのは収穫。
疑問点については読コード会の様子のQiita投稿に対して識者からコメントがもらえたりしてフォローしてもらえたので、自分の知識レベルの向上にも役に立った。

# 読コード会の様子

どういう風に読み進めていったのか、議論のポイントをメモしました。
おなかいっぱいになること請け合い。

## 第1回 (LL.1-220)

### サマリー
* コメントが超しっかりしている
* 省力化すげー
* 関連クラスのソースまで読むのも大事

### 詳細
* LL.2-3: Copyright のコメントいるよね

```java
 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
```

* LL.4-23: この20行は ` *` とだけ書かれているがこれはなんのため？
    * OpenJDK8 のソースではその場所に GPL2 に従うってことが書いてあるので、OpenJDK8 と行番号を合わせるため？
* L.27 `package`と`import`の間の空行がいいね

```java
package java.util;

import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
```

* LL.28-30 `import`に`*`を使っていないというのも大事。`*`を使っているとソースを追えなくなる。
* L.33 `<tt>`～`</tt>`とすると等幅フォントに。でも今は`{@code `～`}`と書くね。
    * 実際L.88で使っている。統一されていない。
* LL.33-103 クラスのコメントがここまでかというくらい書いてある。利用者がどうすべきかしっかり書かれているのでいい。
* LL.97-98 `@author`はメンテされればいいけど、編集した人がここに追加しなかったり、ひどいと別の人がコピペして作ったクラスで`@author`がそのままになっているとか最悪。
* L.103 `@since`はプロダクトのバージョンを入れればいい
* L.107 なぜ`java.io.Serializable`だけFQCN表記？
    * ここでしか出てこないから？

```java
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
```

* L.108 クラスの開始の`{`だけで1行。これは [コーディング規約](http://www.oracle.com/technetwork/java/codeconvtoc-136057.html) にあってないのでは。
* L.109 `serialVersionUID`は`serialver`コマンドで出力したっぽい数字。
    * `serialver`コマンドの出力結果はマイナスになることもあるが？→そういうものなので無問題。ただの64bitの数字。
    * `serialVersionUID = 1L`とする流儀もあるが…うーむポリシー次第？
* LL.111-113など `private`でもjavadocがちゃんとある。
* LL.114 `private static final`はちゃんと変数名が全部大文字になっている。`serialVersionUID`はこう書くことが決まっているので例外。
* LL.116-126 `EMPTY_ELEMENTDATA`と`DEFAULTCAPACITY_EMPTY_ELEMENTDATA`の違いがよくわからない。読み進んでいけばわかるか。
    * とはいえ後者のjavadocにちゃんと「こういう違いだよ」と書いてくれてはいる。そういうコメントは大事。けど、まだそれが理解しきれていない。
* L.134 `private`じゃない変数`elementData`。ちゃんと、なぜ`private`じゃないかの説明がコメントにある。
    * でもなんで`elementData`が`transient`なんだろう？→未解決

```java
    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access
```

* L.139 javadocコメント`@serial`がここはあるのはなぜ？→未解決

```java
    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;
```

* LL.143-159 このコンストラクタ、ちゃんと`@throws`のjavadocコメントに例外の説明があるのにコンストラクタは`throws`宣言していない。これは`javadoc`コマンドで警告が出るはず。→今は出ない?

```java
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
```

* L.154 `EMPTY_ELEMENTDATA`は`capacity`が0 のときに共有の配列を割り当てることでインスタンスの生成コストを節約しているのかなるほどーー。
* LL.156-157 157行目のインデントが空白4文字ではなく直前の行の`(`の後ろまで取っている
    * それなら156行目で`(`の次に改行すべきでは。

```java
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
```

* L.165 デフォルトコンストラクタが他のコンストラクタを呼ばずに処理完結している。これは`this(DEFAULT_CAPACITY)`としていないのがすごい。省力化が徹底している。

```java
    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
```

* LL.179-181 `Object[]`でない場合のこの特別な処理はなぜ必要か？
    * BugParadeの番号っぽいのがあるからたぶん回避策→[やはりそうだった](http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652)
    * `Object[]`の場合は最初の`toArray()`で完結しているので対処不要
    * 2つめの`if`文では`{`と`}`でくくっていない
        * [Appleのあのバグ](http://qiita.com/tomohisaota/items/e6995e89b843e1295c08)を教訓に、1行であってもくくるべき
    * 最初の`elementData`は`this`がついていないのが気持ち悪い。よく見たらついていたりついていなかったり統一されていない。

```java
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
```

* L.194 この`modCount`は何だ？ いきなり出てきたぞ？
    * スーパークラスで宣言されている。`Iterator`のための変更カウンタ。25行のjavadocコメントで解説されている。→解説があるとわかるのでよい
    * サブクラスを作るときに親クラスのコードをちゃんと読んでいるか？

```java
    public void trimToSize() {
        modCount++;
```

* L.218 `ensureExplicitCapacity()`とは？→時間切れ

## 第2回 (LL.221-413)

### サマリー
* キャパシティの調整周りは謎だらけで未解決。
* 普段使わないメソッドが。なるほど。

### 詳細
* L.97 （前回のところ） これもしかしてEffective Javaの著者のJoshua Blochでは？？

```java
 * @author  Josh Bloch
```
* L.233: `overflow-concsious code`ってあるけど、何が言いたいのか？
    * オーバーフローが考慮されていると言うこと？ わざわざコメントに書くのはなぜ？
        * overflow-consciousは、計算の結果minCapacityが文字通りオーバーフローしても、していないのと大小関係が保たれるということ。intの最大値付近 → 1.5倍してオーバーフローしてかなり小さい負の値となった場合、a>bだと判定ミスるけど、a-b>0だと（オーバーフローの程度に依りますが）大丈夫。hugeCapacityで負の数をチェックしているのも同じ理屈かと。

```java
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
```

* L.234 `minCapacity > elementData.lenth` ではなく、わざわざ引き算しているのは、0との比較だと早い（アセンブラコードを意識）から？
* L.244 なぜ8なのか不明。
    * javadocコメントでこれ以上大きいサイズをアロケートしようとするとOutOfMemoryErrorとあるけど、必ずしもメモリ不足なわけではないだろうのになぜOutOfMemoryErrorなのか？
        * 読む会の後での気づき：「必ずしも」ではないから、`may`なのか。それならまあなるほど。

```java
    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
```

* L.255 これ`oldCapacity`の1.5倍ということだよね？ はー、こうするもんですか。この方が早いということか。

```java
        int newCapacity = oldCapacity + (oldCapacity >> 1);
```

* L.260 このコメントの意図がわからない。これでオッケー、ということ？

```java
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
```

* LL.264-270 このメソッドの意味が分からない。→未解決
   * L.244で`Integer.MAX_VALUE - 8`とか言っておきながらここで`Integer.MAX_VALUE`を返すのはなんで？
   * `minCapcity`が負になるのはここまでの呼び出し方ではありえない。どういう場合を想定しているのか不明。

```java
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
```

* LL.310-321 いきなり`for`でまわるのではなくて引数によってループを変えている。こうすることでループ中の`if`判定を減らすということか。なるほど。

```java
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
```

* L.351 `ArrayList<?>`の`<?>`って何だっけ？→どのクラスでもよいということ。
    * なぜ`<T>`ではなく`<?>`なのか？→そういえば`elementData`も`T`ではなく`Object`で宣言されている。実際に収まる型がなんでもいようにしている工夫か。

```java
    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }
```

* LL.355-358 これは`Object.clone()`が`CloneNotSupportedException`をスローし、かつこの例外がchecked exceptionというのが果たして妥当だったのか疑問。
    * ともあれ、コメントの通り、ここで例外が発生することはない。こんなときに`throw new InternalError(e);`がコアSDKの中ではイディオム化している。プロダクトコードでも絶対に来ないところではこうするようにしている。

* LL.365-367 1文目はわかりづらいけど、カッコ内でちゃんと言い換えてくれているのでそっちで理解。はあなるほど。

```java
     * <p>The returned array will be "safe" in that no references to it are
     * maintained by this list.  (In other words, this method must allocate
     * a new array).  The caller is thus free to modify the returned array.
```

* LL.387-392 `immedeiately following the end of the collection`とあるので、`null`を代入するのは最後の要素の次。番兵ということか。カッコの説明にもあるけど、`null`番兵が使えるシーンは限定的。中途半端な。
    * 「なら残り全部`null`入れろよ」とも思うが代入するのもコストなので必要最小限ということか。

```java
     * <p>If the list fits in the specified array with room to spare
     * (i.e., the array has more elements than the list), the element in
     * the array immediately following the end of the collection is set to
     * <tt>null</tt>.  (This is useful in determining the length of the
     * list <i>only</i> if the caller knows that the list does not contain
     * any null elements.)
```

* L.408 `System.arraycopy()`は初めて見た。→古く(1.0)からある。今は便利なユーティリティがあるので自分で使うことはまずない。ちなみにこのメソッドは`native`メソッド。

## 第3回 (LL.414-743)

### サマリー
* バグらしき挙動を発見！
* `batchRemove()`は読解が難しい（真似してはいけない）

### 詳細
* LL.428-432 `rangeCheck()`でサイズオーバーのチェック、`elementData()`（の中の配列アクセス）で負の値のチェックがされている。言い換えると、`elementData()`で負の値がチェックされるので、`rangeCheck()`で負の値のチェックをする必要がない。（そして実際にチェックしていない）

```java
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }
```
* LL.446-447: 参照はメソッド経由なのに代入は配列に直アクセスしている・・・。

```java
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
```

* L.458 ここで`modCount`をインクリメントしているのでこのメソッドではインクリメントしなくてよいんだよ、と読む人の心理を先読みしたコメント。いいね。

```java
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
```

* L.499-500 `System.arraycopy()`では、srcやdstがちゃんと待避されているのかな。そうじゃないとこのコードだと、後にコピーするインデックスを上書きしてしまうことになる。

```java
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
```

* LL.540-547 `fastRemove()`は、通常の`remove()`に比べて`rangeCheck()`と元の値のコピーをリターンする以外全く一緒。なるほどそこを省略するために別のメソッドを設けるものか。

```java
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
```

* LL.576-583 これはバグっぽい。引数`c`の大きさが0の時、`modCount`はインクリメントされるが、戻り値は`false`（つまり変更なしを意味する）となる。変更なしなのに`modCount`がインクリメントされて、`Iterator`で`ConcurrentModificationException`が発生する。変更されたのかされていないのかが動きとして統一されていない。
    * ただし、実害はまずない。

```java
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
```

* LL.666-667 このコメントで何がいいたいのか？ ベストというならベストの理由を書いて欲しい。

```java
    /**
     * Constructs an IndexOutOfBoundsException detail message.
     * Of the many possible refactorings of the error handling code,
     * this "outlining" performs best with both server and client VMs.
     */
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
```

* L.714-730 ここ(メソッドの先頭～`finally`の前半)はちょっと難しい。変数名も分かりづらいしコメントも不十分。
    * `r`は読んだインデックス、`w`は書いたインデックス、であろう
    * わざわざ`try`-`finally`でかこっているということはここで例外がスローされるということ。被疑箇所は`c.contains()`しかない。
        * たぶんビンゴ。`finally`のコメントに`if c.contains() throws`とある。
        * 裏付け：このコードで`r != size`となるのは、ループの途中でエラーになる場合しかない
        * 呼び出し元のコードの`@throws NullPointerException`の説明に`if this list contains a null element and the specified collection does not permit null elements` というコメントがあるので、ここで起こりうるのは自分のリストのエレメントに`null`があった場合の`NullPointerException`ということだろう。
    * `arraycopy()`で、読んでないインデックスに対して、書き込んだインデックス以降のデータをコピーしているサイズ合わせ？
        * でも中身をロールバックしているわけでもない。互換性を保たなければいけない挙動とはいったい何なのか？

```java
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }
```

* （上記謎への応答）もし ArrayList.removeAll() を実装してオーバーライドしなければ、AbstractCollection.removeAll() が呼び出される。Iterator#remove() を使って各要素を削除しているので、 ArrayList だったら成功しても途中で失敗しても削除分だけリストが詰められる。これを配列で実装したのが finally 節ということでしょう。

```java
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        Iterator<?> it = iterator();
        while (it.hasNext()) {
            if (c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }
```

* L.720 ここで引数にもらったフラグで判定。`removeAll()`と`retainAll()`は、ロジックは似ているけど真逆の操作なのでここでフラグ制御して重複コードをなくしている。なるほど。

## 第4回 (LL.744-1024)

### サマリー
* シリアライズの伏線は回収された・・・か？！
* 新たなる難敵`SubList`の登場

### 詳細
* LL.754-767 `writeObject()`中も変更チェックするのね。へぇ～。

```java
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
```

* LL.760-763 `elementData`をわざわざ`transient`にして`defaultWriteObject()`で書き出さないようにしているのは、`elementData`の`size`以上分のところを無駄に書き出さないようにするためでは？！

* L.758: `size`は直前の`defaultWriteObject()`で書き出されているのにわざわざもう1回書いている。`clone()`の互換性の振る舞いのためってのがよくわからない。モヤッとボール。:thought_balloon:

* L.782 なんで読み込んだ値(`s.readInt()`)を無視しているんだろう。謎。それならなんで`writeObject()`の時にわざわざ`writeInt(size)`したのか？ つまりダミーで値を書き込んでおく必要があった？ 伏線の回収部分と思われるが理由が不明確。

```java
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }
```

* L.788 なぜわざわざ`a`という変数を宣言して使うのかが不明。直接`elementData`のまま使えばいいのに。
    * aに代入しておくと若干速くなる(可能性がある)のかも知れません。elementdata は this.elementdata なので、この先頭のアドレスを取得するには以下のように一度メインメモリーにアクセスする必要があります。これを変数に取っておけばCPUレジスターへのアクセスになりメモリーにアクセスする回数が減りそうです。コピーのような大きなループでは差が出るかも知れません。とは言っても、いまどきのCPUならL1キャッシュにヒットするだろうし、オプティマイザも頑張るでしょうから、差はほとんど出ないんじゃないかと思います。
        * (this のアドレス + elementdataのオフセット) の先に格納されている値
            * C言語だと &(this -> elementdata) でしょうか。

* L.890-896 本来`while`ループの中で`cursor`と`lastRet`を更新しなければいけないはずなのに、ヒープメモリへのアクセスを押さえるために最後の1回だけしか代入しない。いいのこれ？ `ArrayList`はスレッドアンセーフだからユルいということ？

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

* LL.939-949 インナークラス`ListItr`の`set()`は、`expectedModCount`の更新をしていない。何で？（下に記載の`add()`との違いに注目されたい）
    * ArrayListの`set()`でも`modCount`は変わらない。だから、ここで`expectedModCount`を代入し直す必要がないと言うことか。ほうほうなるほど。

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

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

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

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

* LL.1025-1031 ここを読んだところで内容読解の前に時間切れ。次回このメソッドから再度読む。

```java
        public E set(int index, E e) {
            rangeCheck(index);
            checkForComodification();
            E oldValue = ArrayList.this.elementData(offset + index);
            ArrayList.this.elementData[offset + index] = e;
            return oldValue;
        }
```

## 第5回 (LL.1025-1322)

### サマリー
* `SubList#listIterator()`が返す匿名クラスのメソッドで`ArrayList.this`だったり`SubList.this`だったりなんで？
* さらなる強敵`Spliterator`現る

### 詳細

* LL.1044,1069 `add()`は`void`なのに`addAll()が`boolean`なのはなぜ？
    * `add()`は確実に要素を追加するけど、`addAll()`は引数のコレクションのサイズが0だと要素を追加しないので追加したかどうかの判定が必要だから？

```java
        public void add(int index, E e) {
```

```java
        public boolean addAll(Collection<? extends E> c) {
```

* LL.1073-1077 1文字変数名は分かりづらい。`cSize`が`c`のサイズ。で、`c`って何だっけ？ ってなりそう。そうでもない？

```java
        public boolean addAll(int index, Collection<? extends E> c) {
            rangeCheckForAdd(index);
            int cSize = c.size();
            if (cSize==0)
                return false;
```

* L.1097 `lastRet`は何を表しているのか？ index of LAST RETurned element ってこと？

* L.1151 なぜ`forEach()`だけ`checkForComodification()`の呼び出しが最後になるのか？ 他のメソッドでは操作の前にチェックしている。

```java
                @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();
                }
```

* L.1147 これはVisitorパターン

* LL.1171,1183 `ArrayList.this`なのはなぜ？ `SubList.this`なんじゃないの？
    * `SubList.this.remove()`なのに、`modCount`は`ArrayList.this`を参照。そりゃ同じ値なんだろうけど。
    * `ListIterator`が2つ以上作られて、片方で変更があった時にもう一方でそれを検出できるようにするためか？

```java
                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();
                    }
                }
```

* L.1196 `add()`したときに`lastRet`を-1にしているのはなぜ？

```java
                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();
                    }
                }
```

* L.1270 `Spliterator`って何だ？
    * （ググる）
    * おお、ストリームAPIの中で動いているやつなのね、ほ～なるほど。

```java
    @Override
    public Spliterator<E> spliterator() {
        return new ArrayListSpliterator<>(this, 0, -1, 0);
    }

    /** Index-based split-by-two, lazily initialized Spliterator */
    static final class ArrayListSpliterator<E> implements Spliterator<E> {
```

* LL.1277-1307 長いコメント。このクラスの実装方針について事細かに書かれている。なるほど～。

## 第6回 (LL.1323-1460)

### サマリー
* 値の参照と代入を同時にやるのが読みにくい。けど読み出しが1回になるから効率はいいのかな。

### 詳細

* L.1323 そもそもここの`fence`ってなに？
    * 渡されたリストのうちアクセスする上限のインデックスを指しているようだ。

```java
        private int getFence() { // initialize fence to size on first use
            int hi; // (a specialized variant appears in method forEach)
            ArrayList<E> lst;
            if ((hi = fence) < 0) {
                if ((lst = list) == null)
                    hi = fence = 0;
                else {
                    expectedModCount = lst.modCount;
                    hi = fence = lst.size;
                }
            }
            return hi;
        }
```

* L.1326 `hi`を`fence`で初期化。`fence`はコンストラクタに渡されているもので、これは`-1`がきているから初回はこの`if`文に入る。
    * の参照と代入を同時にやるのが読みにくい。けど、これを2行で書くと読み出しが2回。1回ですみそうなこちらの方が速いしメモリの使用効率もいいということか。

* LL.1337-1342 `lo >= mid`でみているので、自分よりも下に分割できるかどうか。そして、自分自身は、`index = mid`としているので、上側に変身。なんというトリック。
    * 下側に分割するインスタンスを作る`new`のところで、上側となる自分自身も同時に設定している。( `index = mid` とすることにより。） こうすることで1行で「分割」をやってのけているのがほえ～～、という感じ。

```java
        public ArrayListSpliterator<E> trySplit() {
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid) ? null : // divide range in half unless too small
                new ArrayListSpliterator<E>(list, lo, index = mid,
                                            expectedModCount);
        }
```

* L.1360 今回も出てきた、インスタンス変数をローカル変数に代入するテクニック。コメントを見る限りやはりループ中からインスタンス変数にアクセスしたくない意図が読み取れる。

```java
            int i, hi, mc; // hoist accesses and checks from loop
```

* LL.1371,1375 `i = index`、つまり自分のインデックスで`i`を初期化して、さらに`index = hi`で、ループ後の状態を先回りして代入してしまっている。
    * 本来ならループ中で`index = i`とすべきだが、毎回値を代入するのを省略して代入を1回にしてマシンリソースと時間を「稼いで」いる。
    * このあたり、前回読んだ、長々と書いてあるコメントの設計方針が、なんで長々と書いているのかが裏付けられているようだ。

```java
                if ((i = index) >= 0 && (index = hi) <= a.length) {
                    for (; i < hi; ++i) {
                        @SuppressWarnings("unchecked") E e = (E) a[i];
                        action.accept(e);
                    }
```

* LL.1387-1389 `characteristics()`というのはインタフェース`Spliterator`に定義されているので実装しなければいけないメソッド。どういうリスト化の特徴を示す。`SIZED`と`SUBSIZED`はどう使い分けるのだろう？ `SIZED`だけど`SUBSIZED`ではないってどういうもの？

```java
        public int characteristics() {
            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
        }
```

* LL.1418-1421 `removeSet`、つまり、削除対象のもの。これの`nextClearBit()`ということはビットが立っていないもの。つまり、削除しない＝生き残るもの。これを左から詰めている。なんか二重否定みたいでわかりにくい。

```java
            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
                i = removeSet.nextClearBit(i);
                elementData[j] = elementData[i];
            }
```

* LL.1450-1459 ソートは`Arrays.sort()`を使っているのね。
    * `Arrays.sort()`をちょっと追っかけたら、ソート対象によってアルゴリズムがいろいろあって面白そう。（かなり深そうなので読むのは見送り）

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