Java PriorityQueue initElementsFromCollection method

Question

I'm having hard time digesting this particular code block from java.util.PriorityQueue#initElementsFromCollection method.

/**
 * Initializes queue array with elements from the given Collection.
 *
 * @param c the collection
 */
private void initFromCollection(Collection<? extends E> c) {
    initElementsFromCollection(c);
    heapify();
}

private void initElementsFromCollection(Collection<? extends E> c) {
    Object[] es = c.toArray();
    int len = es.length;
    if (c.getClass() != ArrayList.class)
        es = Arrays.copyOf(es, len, Object[].class);
    if (len == 1 || this.comparator != null)
        for (Object e : es)
            if (e == null)
                throw new NullPointerException();
    this.queue = ensureNonEmpty(es);
    this.size = len;
}

I can understand that the code here tries to build the Heap from the collection elements supplied via constructor but why are they checking the class type of Collection argument against ArrayList and again copying the elements, it has already been copied into Object[] es using toArray?

    if (c.getClass() != ArrayList.class)
        es = Arrays.copyOf(es, len, Object[].class);

Is anything magical happening in java.util.Arrays#copyOf(U[], int, java.lang.Class<? extends T[]>) ?

java-11

Answer 1

The constructor (or rather its author) does not trust the incoming collection. The collection’s toArray method could violate the contract and return a shared array rather than creating a new one. This way, the caller could get hands on the internally used array of the constructed PriorityQueue instance.

So, the constructor makes another defensive copy, except when the incoming collection is an ArrayList exactly, i.e. not even a subclass of it. In other words, it trusts the ArrayList’s toArray implementation to adhere to the contract, to skip the additional copying step in this specific case. That’s why not even a subclass of ArrayList will be accepted, as a subclass could have overridden the toArray method.

A similar mistrust has been displayed in the default implementation of Stream.toList() as discussed in this question and the comment section beneath that question.

The default implementation has been specified as

default List<T> toList() {
    return (List<T>) Collections.unmodifiableList(new ArrayList<>(Arrays.asList(this.toArray())));
}

because it distrust the toArray() implementation of 3rd party Stream implementations (the JDK implementation overrides the toList() method anyway).

The penalty of this paranoia is even paid twice. In the past, ArrayList’s constructor did trust any incoming collection’s toArray() implementation, but today, it looks like

public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

doing exactly the same as you’ve seen in PriorityQueue’s constructor, only trust toArray() when the collection is exactly an ArrayList.

Since in the case of the toList(), the incoming collection is the result of Arrays.asList(…), i.e. not an ArrayList, the toArray() method will make a copy, followed by ArrayList’s constructor making another copy. All that, while the original array is a new array anyway, for well behaving Stream implementations…

---

We can generalize the problem. The idiomatic initialization of collections, like new ArrayList<>(Arrays.asList(…)) or new ArrayList<>(List.of(…)) or likewise for PriorityQueue, get the penalty of a defensive copy despite only using JDK collections which should have a correct toArray implementation.

I’d probably use c.getClass().getClassLoader() != null instead of c.getClass() != ArrayList.class, to trust all built-in collections, whose implementation has been loaded by the bootstrap loader. But perhaps, that test would turn out to be more expensive than the ArrayList test¹ or there are too many untrustworthy built-in collections…

¹ The key point is whether the optimizer understands the construct well enough to predict its outcome.