Implement Collections.sort() on top of List.sort(), not vice-versa
This is an app-observable behavior change relative to Android N.
This updates List.sort() and Collections.sort() to OpenJDK8u60.
Previously, Android had been using the logic from earlier version
of OpenJDK8 (present up to u19 or so). See:
https://bugs.openjdk.java.net/browse/JDK-8030848
The new behavior makes Collections.sort() more efficient for
List implementations that override List.sort() with a specialized,
efficient implementation. It also makes the modCount behavior of
Collections.sort() consistent with that of overridden List.sort()
implementations.
This behavior change carries a risk of app compat issues in future
versions of Android. Specifically:
- List.sort() implementations that delegate to Collections.sort()
will now infinitely recurse. Such implementations should be
fixed to call super.sort() instead.
- List implementations that override sort() with a version that
changes the value of modCount (this affects e.g. ArrayList but
not LinkedList), will now throw ConcurrentModificationException
if Collections.sort(list) is called in the middle of an iteration.
In such cases, the calling code should be fixed. E.g.,
- don't sort the list in the middle of iterating, or
- loop over list indices instead and use List.get(int), or
- convert the List to an array or a LinkedList first
Should serious app compat issues arise, possible ways to address
them in the platform include:
- revert this change, or
- make the change dependent on targetSdkVersion, or
- detect (indirect) recursive calls to Collections.sort()
and deal with them by logging, throwing a more informative
exception, or changing behavior.
Tests were updated to assert the new behavior.
The harmony CollectionsTest uses an ArrayList subclass that
throws UnsupportedOperationException from ArrayList.set()
without also overriding ArrayList.sort(). This makes the
subclass used in the test inconsistent with the List.sort()
documentation that claims that List.sort() will throw such
an exception if List.listIterator().set() does; this
inconsistency now also affects Collections.sort(). Therefore
the test was updated in this particular place to use a
different List implementation instead that, unlike ArrayList,
does not override List.sort().
Bug: 31902309
Bug: 29935305
Test: cts-tradefed run cts -m CtsLibcoreTestCases -a arm64-v8a
Change-Id: I6aad092f77ecee3eac3e633e1d59957e768fbf2b
4 files changed