290CopyOnWriteArrayList and Collection#toArray()

Author: Dr Heinz M. KabutzDate: 2021-06-10Java Version: 1.5 to 17Category: Concurrency

Abstract: When is it safe for a CopyOnWriteArrayList to accept the result from a toArray() method? In the past, the only thing that mattered was that the type was Object[]. But this was changed in 2020 to only accept the array if the source was a java.util.ArrayList.

Welcome to the 290th edition of The Java(tm) Specialists' Newsletter, sent from a summery Island of Crete. We have seen some brave tourists, but few. Greece is trying to woo digital nomads to come settle here for a while (Euronews.travel). Buyers beware. Greece is a bit more laid back than what you might be used to from home. Four months ago, we needed a confirmation document that we have social insurance here in Greece. We have been faithfully contributing since 2008 and are up to date with our payments. There is one person in Chania who is responsible for the paperwork, and the job is just not getting done. No idea when / if it will ever be done. I have lived in cyberspace for 20 years. Greece has a lot of positive points. The Greeks are hospitable and friendly. The weather is lovely and the food is delicious. However, when you live here, and have to navigate the bureaucracy, you need a lot of patience. Even buying things here is tricky. We are trying to purchase our neighbour's vegetable patch. It's a simple transaction, with clear borders and title deeds. Buyer and seller agree on the price. But we have been waiting for over six months for the transfer to go through. That said, if you do want to come live in Chania as a digital nomad, do let me know how I can help :-)

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

CopyOnWriteArrayList and Collection#toArray()

The only list in Java 1.0 was the java.util.Vector. It was "threadsafe", in that it could not get corrupted by multiple threads modifying it at the same time. However, the behaviour was surprising at best. For example, the lock was not held during iteration, which meant that the Vector could change, leading to skipped or duplicate elements. In Java 1.2, we changed from the confusing Enumeration to the fast-fail Iterator. We would now get a ConcurrentModificationException during iteration. The only way to avoid that was to make a copy of the list prior to iteration, the way that java.util.Observable did.

The CopyOnWriteArrayList makes a copy of the underlying array whenever we modify it in some way. The iterator simply points to the current array. Changes to the list do not get reflected in the iteration. We call this a snapshot iterator.

As part of my ongoing effort to create a huge learning resource about Java, I recorded a 4 hour course on the CopyOnWriteArrayList and the CopyOnWriteArraySet. This is a "teardown" of the classes, with a detailed analysis of every line of code, including how the class has changed over the years. Oh and there is something quite different about this recording compared to all my other courses, but you'll have to watch it carefully to notice it. The first person to guess correctly will get the $50 (excl taxes) course fees refunded. (You only get one guess though).

CopyOnWriteArrayList is derived from java.util.ArrayList, and thus is the only class in java.util.concurrent that is not in the public domain. It differs quite a lot from the original ArrayList and a professor marking assignments would have a hard time proving that they had copied the code. However, the earlier versions of CopyOnWriteArrayList was a lot more similar to ArrayList.

For many years, they both shared the feature that if they were constructed with another collection, and if the toArray() returned anything other than an Object[], it would create a new array. If they had not done this, and some class returned, for example, a String[], then attempting to store an Integer in that array would cause an ArrayStoreException. Consider this BadArrayList (please don't use in real code):

import java.lang.reflect.*;
import java.util.*;

/**
 * This is an example of a bad bad ArrayList. Don't use!
 */
public final class BadArrayList<E> extends AbstractList<E> {
  private final Object[] elements;
  private final Class<E> type;

  public BadArrayList(Collection<? extends E> collection,
                      Class<E> type) {
    elements = collection.toArray(); // dangerous
    this.type = type;
  }

  public E get(int index) {
    return type.cast(elements[index]);
  }

  public E set(int index, E element) {
    E result = get(index);
    elements[index] = element;
    return result;
  }

  public int size() {
    return elements.length;
  }

  public E[] toArray() {
    E[] copy = (E[]) Array.newInstance(type, elements.length);
    System.arraycopy(elements, 0, copy, 0,
                     Math.min(elements.length, elements.length));
    return copy;
  }
}

When we run the following demo, we get the ArrayStoreException:

import java.util.*;

public class ArrayStoreExceptionDemo {
  public static void main(String... args) {
    List<Integer> numbers = new BadArrayList<>(
        Arrays.asList(1, 2, 3), Integer.class);
    System.out.println(numbers);
    List<Object> objects = new BadArrayList<>(
        numbers, Object.class);
    System.out.println(objects);
    objects.set(0, "One"); // ArrayStoreException
  }
}

[1, 2, 3]
[1, 2, 3]
Exception in thread "main" java.lang.ArrayStoreException: java.lang.String
	at BadArrayList.set(BadArrayList.java:23)
	at ArrayStoreExceptionDemo.main(ArrayStoreExceptionDemo.java:11)

For many years, the approach in the ArrayList and CopyOnWriteArrayList constructors was to first check whether the array returned from toArray() was indeed an Object[]. If it was, then we used it as-is. The JavaDocs for Collection#toArray() clearly state that "the returned array will be "safe" in that no references to it are maintained by this collection. (In other words, this method must allocate a new array even if this collection is backed by an array). The caller is thus free to modify the returned array." The JavaDocs (since Java 10) also state that the result should be an Object[], but implementors of the Collection interface could violate both parts of the contract. Simply accepting the array in the case that it was an Object[] was not enough. Consider the COWCopyConstructorTest:

import java.util.*;
import java.util.concurrent.*;

public class COWCopyConstructorTest {
  private static class BadVector<E> extends Vector<E> {
    public synchronized Object[] toArray() {
      trimToSize();
      return elementData;
    }
  }

  public static void main(String... args) {
    Collection<String> list = new BadVector<String>();
    Collections.addAll(list, "John", "Anton", "Heinz");
    CopyOnWriteArrayList<String> cowList =
        new CopyOnWriteArrayList<String>(list);
    Object[] values = list.toArray();
    values[0] = "Diane";
    System.out.println("list = " + list);
    System.out.println("cowList = " + cowList);
  }
}

The output should be the following:

list = [Diane, Anton, Heinz]
cowList = [John, Anton, Heinz]

However, if we take an older version of Java, such as Java 9, we see the following output:

list = [Diane, Anton, Heinz]
cowList = [Diane, Anton, Heinz]

In the latest builds of the JDK, instead of only looking at whether the array type is an Object[], they instead check whether the collection is an java.util.ArrayList. This is the only collection that they trust to deliver a value from the toArray() method that fufills the contract. It is a bit like my favourite vegetable shop in Kounoupidiana declaring which prefecture of Crete their tomatoes come from. Who can trust anything that comes from Heraklion? They even charge premium prices when the produce comes from our area :-)

Whilst I run my JavaSpecialists server on the latest version of Java, I still have older JDKs on my laptop for research purposes. For these I use the Azul Zulu OpenJDK distribution, as this is well maintained and is tested against the TCK. In Java 8, for example, the code was fixed from 1.8.0_262-b17 onward. The latest versions of Java 7 also work correctly. The feature releases Java 9, 10 and 12 do not work correctly, but Java 11, and 13+ are correct. Nice that this change was backported to older Java versions.

Lesson learned: If you can, try use the latest feature release of Java, currently Java 16. Otherwise, if that is impractical, try use the latest LTS release, currently Java 11. If you do have to to use Java 7 or 8, make sure that your JDK has the latest security fixes.

There are a lot of other very interesting tidbits about the CopyOnWriteArrayList. For example, they use double-checked locking to reduce contention in places. Since Java 9, they use synchronized rather than ReentrantLock in order to save 32 bytes per instance. You will find all this, and much more, in my online course on CopyOnWriteArrayList and Set.

Kind regards

Heinz

P.S. A great thank-you to Stuart Marks for excellent input regarding some of the changes made to CopyOnWriteArrayList. Thank you for confirming that my speculations were correct!

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive