javaarraysgenericsstandard-library

Can Arrays.sort(T[] a, Comparator<? super T> c) ever throw ClassCastException if c is not null?

The javadoc for Arrays.sort(T[] a, Comparator<? super T> c) from the package java.util in the standard library for Java 20 API docs reads as follows:

public static void sort(T[] a, Comparator<? super T> c) Sorts the specified array of objects according to the order induced by the specified comparator. All elements in the array must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the array).

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

Implementation note: This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

The implementation takes equal advantage of ascending and descending order in its input array, and can take advantage of ascending and descending order in different parts of the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array.

The implementation was adapted from Tim Peters's list sort for Python ( TimSort). It uses techniques from Peter McIlroy's "Optimistic Sorting and Information Theoretic Complexity", in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.

Type Parameters: T - the class of the objects to be sorted Parameters: a - the array to be sorted c - the comparator to determine the order of the array. A null value indicates that the elements' natural ordering should be used. Throws: ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator IllegalArgumentException - (optional) if the comparator is found to violate the Comparator contract

Emphasis mine.

Doesn't the compiler guarantee (through the use of the type system and the generic signature of the method) that all elements of a are in fact mutually comparable using c and that c.compare(e1, e2) will never throw ClassCastException, provided c is not null?

Presumably, the "actual" signature of toArray, with the type parameters erased, would look like so: static void sort(Object[] a, Comparator c) and the signature of c.compare (let's assume c has the static type Number in our program) would look like so: int compare(Object o1, Object o2) and would contain two casts to Number in its implementation:

Number e1 = (Number) o1;
Number e2 = (Number) o2;
//...

These casts succeed if and only if the runtime type of o1 and o2 is either Number or a sub-type of Number.

The runtime type of o1 and o2 is either Number or a sub-type of Number if and only if the runtime type of a is either Number[] or a sub-type of Number[], e.g. Integer[].

The runtime type of a is either Number[] or a sub-type of Number[] if and only if the static type of a is either Number[] or a sub-type of Number[]. (if the runtime type of a is not Number[] or a sub-type of Number[] but the static type of a is, a ClassCastException will be thrown before the body of Arrays.sort is entered)

That the static type of a is either Number[] or a sub-type of Number[] follows from the method signature static <T> void sort(T[] a, Comparator<? super T> c) because the static type of c is Number (? super T is Number so T is either Number or a sub-type of Number).

I've written some tests to try and get Arrays.sort to throw a ClassCastException, and only really got it when passing null for c instead of an actual comparator.

package org.example.basics.generics.arrays;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Comparator;

class ArraysTest {

    private static final Comparator<Number> compareAsWholeNumber = new Comparator<Number>() {
        @Override
        public int compare(java.lang.Number o1, java.lang.Number o2) {
            return Long.compare(o1.longValue(), o2.longValue());
        }
    };

    @Test
    public void sortingIntsThrowsNoException() {
        Integer[] ints = new Integer[]{4, 2, 3};
        Assertions.assertDoesNotThrow(() -> {
            Arrays.sort(ints, compareAsWholeNumber);
        });

    }

    @Test
    public void sortingDoublesThrowsNoException() {
        Double[] doubles = new Double[]{4.0, 2.0, 3.0};
        Assertions.assertDoesNotThrow(() -> {
            Arrays.sort(doubles, compareAsWholeNumber);
        });
    }

    @Test
    public void sortingNumbersThrowsNoException() {
        Number[] numbers = new Number[]{4.0, 2, 3.0f};
        Assertions.assertDoesNotThrow(() -> {
            Arrays.sort(numbers, compareAsWholeNumber);
        });
    }

//    @Test
//    public void sortingObjectsIsCompileError() {
//        Object[] numbers = new Number[]{4.0, 2, 3.0f};
//        Arrays.sort(numbers, compareAsWholeNumber);
//    }

    @Test
    public void sortingDisguisedStringsThrowsClassCastException() {
        Throwable e = Assertions.assertThrows(ClassCastException.class, () -> {
            Arrays.sort((Number[]) new Object[]{"4.0", "2", "3.0f"}, compareAsWholeNumber);
        });
        e.printStackTrace();
    }

    @Test
    public void sortingDisguisedStringsThrowsClassCastExceptionAtArrayAssignment() {
        Assertions.assertThrows(ClassCastException.class, () -> {
            Number[] numbers = (Number[]) new Object[]{"4.0", "2", "3.0f"};
        });
    }
    @Test
    public void sortingNonComparableWithNullComparatorThrowsClassCastException() {
        Number[] numbers = new Number[]{4.0, 2, 3.0f};
        Throwable e = Assertions.assertThrows(ClassCastException.class, () -> {
            Arrays.sort(numbers, null);
        });
        e.printStackTrace();
    }
}

The above test suite runs successfully on my machine using Eclipse Temurin 20.0.2.

Note especially the last 4 tests.

sortingObjectsIsCompileError: Passing an array with a static type that is neither Number[] nor a sub-type of Number[] to sort is a compile error. Uncommenting that test and trying to compile produces the following for me:

TestToArray.java:46: error: no suitable method found for sort(Object[],Comparator) Arrays.sort(numbers, compareAsWholeNumber); ^ method Arrays.<T#1>sort(T#1[],Comparator<? super T#1>) is not applicable (inference variable T#1 has incompatible bounds upper bounds: Number,Object lower bounds: Object) method Arrays.<T#2>sort(T#2[],int,int,Comparator<? super T#2>) is not applicable (cannot infer type-variable(s) T#2 (actual and formal argument lists differ in length)) where T#1,T#2 are type-variables: T#1 extends Object declared in method <T#1>sort(T#1[],Comparator<? super T#1>) T#2 extends Object declared in method <T#2>sort(T#2[],int,int,Comparator<? super T#2>)

sortingDisguisedStringsThrowsClassCastException: As the name suggests, a ClassCastException is indeed thrown here, but this is misleading: Printing the stacktrace to std_out yields the following (reduced for brevity):

java.lang.ClassCastException: class [Ljava.lang.Object; cannot be cast to class [Ljava.lang.Number; ([Ljava.lang.Object; and [Ljava.lang.Number; are in module java.base of loader 'bootstrap') at org.example.basics.generics.arrays.TestToArray.lambda$sortingDisguisedStringsThrowsClassCastException$3(TestToArray.java:52) <3 internal lines> at org.example.basics.generics.arrays.TestToArray.sortingDisguisedStringsThrowsClassCastException(TestToArray.java:51) at java.base/java.util.ArrayList.forEach(ArrayList.java:1511) <9 internal lines> at java.base/java.util.ArrayList.forEach(ArrayList.java:1511) <30 internal lines> at jdk.proxy1/jdk.proxy1.$Proxy2.stop(Unknown Source) <7 internal lines> at worker.org.gradle.process.internal.worker.GradleWorkerMain.run(GradleWorkerMain.java:69) at worker.org.gradle.process.internal.worker.GradleWorkerMain.main(GradleWorkerMain.java:74)

Note that: 1. the failed cast is from [Ljava.lang.Object to [Ljava.lang.Number rather than from java.lang.Object to java.lang.Number as we would expect it to be for a failed cast inside the compare method and 2. the ClassCastException is thrown from inside the TestToArray class and not from the Arrays class.

The test sortingDisguisedStringsThrowsClassCastExceptionAtArrayAssignment shows that simply assigning the array of String[] to an array of Number[] throws that same ClassCastException.

The last test, sortingNonComparableWithNullComparatorThrowsClassCastException does in fact throw the expected ClassCastException and this is the only case where I was able to get the sort method itself to throw this exception. Printing the stacktrace to std_out yields the following (reduced for brevity):

java.lang.ClassCastException: class java.lang.Double cannot be cast to class java.lang.Integer (java.lang.Double and java.lang.Integer are in module java.base of loader 'bootstrap') at java.base/java.lang.Integer.compareTo(Integer.java:72) at java.base/java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:320) at java.base/java.util.ComparableTimSort.sort(ComparableTimSort.java:188) at java.base/java.util.Arrays.sort(Arrays.java:1041) at java.base/java.util.Arrays.sort(Arrays.java:1228) at org.example.basics.generics.arrays.TestToArray.lambda$sortingNonComparableWithNullComparatorThrowsClassCastException$5(TestToArray.java:67) <30 internal lines> at jdk.proxy1/jdk.proxy1.$Proxy2.stop(Unknown Source) <7 internal lines> at worker.org.gradle.process.internal.worker.GradleWorkerMain.run(GradleWorkerMain.java:69) at worker.org.gradle.process.internal.worker.GradleWorkerMain.main(GradleWorkerMain.java:74)

Note that in this case the failed cast is from java.lang.Double to java.lang.Integer and the exception is actually thrown from the Arrays class.

Is the only case where Arrays.sort(T[] a, Comparator<? super T> c) can throw ClassCastException the case where the value null is passed for the comparator c?

Context: I'm hoping to find out what kind of mistakes I need to make in order for the type system to no longer be able to function as a safeguard against ClassCastException for sort. So far it seems that the compiler will at the very least issue an "unchecked" warning which is reassuring. Is there any way to get a ClassCastException from sort without the compiler issuing "unchecked" warnings (and without passing null in place of c)?

Solution

  • The exception is super simple to trigger if you have raw types (whether accidental or not):

    class FawltyComparators {
    @Test
    void test() {
        final Comparator numberComparer = new NumberComparator();
        final Object[] array = { 1, 2, "3", "4" };
        Arrays.sort(array, numberComparer);
    }

    private static final class NumberComparator implements Comparator<Number> {
        @Override
        public int compare(final Number o1, final Number o2) {
            return 0; // doesn't matter
        }
    }
}

    But this will still give you compiler warnings:

    FawltyCompators.java:17: warning: [unchecked] unchecked method invocation: method sort in class Arrays is applied to given types
        Arrays.sort(array, numberComparer);
                   ^
  required: T[],Comparator<? super T>
  found:    Object[],Comparator
  where T is a type-variable:
    T extends Object declared in method <T>sort(T[],Comparator<? super T>)
FawltyCompators.java:17: warning: [unchecked] unchecked conversion
        Arrays.sort(array, numberComparer);
                           ^
  required: Comparator<? super T>
  found:    Comparator
  where T is a type-variable:
    T extends Object declared in method <T>sort(T[],Comparator<? super T>)