JDK-6323374 : (coll) Optimize Collections.unmodifiable* and synchronized*
  • Type: Enhancement
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Affected Version: 6
  • Priority: P4
  • Status: Resolved
  • Resolution: Fixed
  • Submitted: 2005-09-13
  • Updated: 2023-07-25
  • Resolved: 2021-03-05
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 17
17 b13Fixed
Related Reports
CSR :  
Duplicate :  
Duplicate :  
Relates :  
Relates :  
Sub Tasks
JDK-8263397 :  
Description
A DESCRIPTION OF THE REQUEST :
When calling an unmodifiableMap (for example) it is sufficient that the function return an unmodifiable class.  As there is no way to detremine if the class is already unmodifyable (with attempting to modify it) this method can be called just in case.  This can result in an unmodifiable collection needless wrapped again and again.

The same holds for synchronized collections.  Once a class is wrapped in a synchronised class, it does not need to be wrapped again.

JUSTIFICATION :
It is quite simple for the methods to check is a map, list,set collection is already wrapped in an unmodifable or synchronized wrapper, but it is ugly to attempt to do this outside the class as the rwapping classes are all package protected.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Once a collection is wrapped with an unmodifiable wrapper, it should not be wrapped again if the method is called again.

The same holds for synchronized wrappers.
ACTUAL -
A collection can be wrapped any number of times to make it very, very unmodifiable or very, very synchronized.

---------- BEGIN SOURCE ----------
Here is an example diff for the synchronized methods.

*** Collections.java	Thu Sep  8 00:09:56 2005
--- CollectionsNew.java	Mon Sep 12 09:54:59 2005
***************
*** 1529,1534 ****
--- 1529,1540 ----
       * @return a synchronized view of the specified collection.
       */
      public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
+         Class<?> cClass = c.getClass();
+         if (cClass == SynchronizedCollection.class ||
+                 cClass == SynchronizedList.class ||
+                 cClass == SynchronizedSet.class ||
+                 cClass == SynchronizedSortedSet.class )
+             return c;
  	return new SynchronizedCollection<T>(c);
      }
  
***************
*** 1633,1638 ****
--- 1639,1647 ----
       * @return a synchronized view of the specified set.
       */
      public static <T> Set<T> synchronizedSet(Set<T> s) {
+         Class<?> sClass = s.getClass();
+         if (sClass == SynchronizedSet.class || sClass == SynchronizedSortedSet.class)
+             return s;
  	return new SynchronizedSet<T>(s);
      }
  
***************
*** 1701,1706 ****
--- 1710,1717 ----
       * @return a synchronized view of the specified sorted set.
       */
      public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {
+         if (s.getClass() == SynchronizedSortedSet.class)
+             return s;
  	return new SynchronizedSortedSet<T>(s);
      }
  
***************
*** 1779,1784 ****
--- 1790,1799 ----
       * @return a synchronized view of the specified list.
       */
      public static <T> List<T> synchronizedList(List<T> list) {
+         Class<?> listClass = list.getClass();
+         if (listClass == SynchronizedRandomAccessList.class || listClass == SynchronizedList.class)
+             return list;
+ 
  	return (list instanceof RandomAccess ?
                  new SynchronizedRandomAccessList<T>(list) :
                  new SynchronizedList<T>(list));
***************
*** 1937,1942 ****
--- 1952,1960 ----
       * @return a synchronized view of the specified map.
       */
      public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
+         Class<?> mClass = m.getClass();
+         if (mClass == SynchronizedMap.class || mClass == SynchronizedSortedMap.class)
+             return m;
  	return new SynchronizedMap<K,V>(m);
      }
  
***************
*** 2077,2082 ****
--- 2095,2102 ----
       * @return a synchronized view of the specified sorted map.
       */
      public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) {
+         if (m.getClass() == SynchronizedSortedMap.class)
+             return m;
  	return new SynchronizedSortedMap<K,V>(m);
      }
  

---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Create a utility class which determines the classes created by the various methods and then uses these to detremine if the wrappers are required.
This is fairly ugly.

OR Create a copy of the Collections class and correct the methods which can be optimised.

Comments
An interim version of the commit had this code: @SuppressWarnings("unchecked") public static <T> Set<T> unmodifiableSet(Set<? extends T> s) { if (s.getClass() == UnmodifiableSet.class || s.getClass() == UnmodifiableSortedSet.class || s.getClass() == UnmodifiableNavigableSet.class) { return (Set<T>) s; } return new UnmodifiableSet<>(s); } This seems safe, but it isn't. The argument is already unmodifiable, and it's either a SortedSet or a NavigableSet, both of which are Sets, so simply returning the argument looks like it ought to be safe. However, it can lead to heap pollution. The static return type is safe, because the Set class doesn't allow any unsafe operations if the type argument is a supertype. The caller can downcast the return value to SortedSet without any warnings (and it can do so apparently safely, after checking instanceof) in which case the caller now has a SortedSet of the supertype. This can result in ClassCastException for certain operations, such as the subsetting operations headSet(), subSet(), and tailSet(). For example: SortedSet<Integer> set1 = new TreeSet<>(Integer::compare); set1.addAll(Arrays.asList(1, 2, 3)); SortedSet<Integer> set2 = Collections.unmodifiableSortedSet(set1); Set<Number> set3 = Collections.unmodifiableSet(set2); // using the modified version shown above set3 instanceof SortedSet ==> true ((SortedSet<Number>)set3).tailSet(2.0) ==> ClassCastException This is similar to the reason that Collections.unmodifiableSet() takes Set<? extends T> whereas unmodifiableSorted() and unmodifiableNavigableSet() do not; they require SortedSet<T> and NavigableSet<T> respectively.
11-03-2021

Changeset: dbef0ec9 Author: Ian Graves <igraves@openjdk.org> Committer: Stuart Marks <smarks@openjdk.org> Date: 2021-03-05 03:20:44 +0000 URL: https://git.openjdk.java.net/jdk/commit/dbef0ec9
05-03-2021

Noting conversation in: https://github.com/openjdk/jdk/pull/2596 there are some inconsistencies in the behavior between a number of the `java.util.collection.ImmutableCollections` classes and the unmodifiable collections class in `java.util.collection.Collections`. I suggest punting on including those until we can figure out how to make the behaviors between these two the same.
17-02-2021

Also consider having Collections.unmodifiableX avoid wrapping instances returned from List.of etc. methods.
06-02-2021

Summary of recent discussion of this bug: * Optimizing the synchronized wrappers is right out, as that changes the identity of the object returned, and synchronization relies on identity. * Optimizing the checked wrappers is probably not worthwhile. The use case for the checked wrappers is to create a collection and wrap it immediately, and it seems unlikely that nested wrapping will occur. The checked wrappers are probably mostly disused at this point, as generics takes care of most type checking at compile time. * Optimizing the unmodifiable wrappers seems reasonable. If this issue were known at the time they were first implemented, they'd probably have a check to avoid nested wrapping. Thus, adding this nested wrapping check is merely a compatibility issue. From a functional standpoint, the behavior of the returned object is the same: it's still an unmodifiable list, supporting get(), iteration, etc. Two behavioral changes are visible: 1) The instance returned is different from what otherwise would be returned, in particular, the returned instance is not always freshly created. 2) The structure of the returned object (lack of nesting) is visible in the serialized form. The change in identity is certainly visible to == and also if the resulting collection is stored in an IdentityHashMap. While these are certainly possible, it seems unlikely that anybody is relying on the identity of a collection, as collections are used mostly for the values they contain, not the identity of the container itself. As for serialization, certainly the structural change is visible but it doesn't seem to give rise to any cases where there is actual incompatibility. As for the benefits of this change, I had previously never heard of cases, but in fact a couple cases have arisen in the past year. This means that there are probably more out there that I haven't heard of. Either people are getting inexplicable StackOverflowErrors, or they run into them and spend time debugging the issue, or they are paying extra memory and performance costs without realizing it. In any case, moving to an "idempotent wrapping" model seems to be a service that's of some value to clients. Proposed Solution For the following methods in the Collections class: unmodifiableCollection unmodifiableList unmodifiableMap unmodifiableNavigableMap unmodifiableNavigableSet unmodifiableSet unmodifiableSortedMap unmodifiableSortedSet a getClass() check should be done on the argument, and if it's == the class wrapper class that would be created, return the argument instead of creating a new wrapper class. Some adjustment may be necessary with the UnmodifiableList/UnmodifiableRandomAccessList cases, but a getClass() check would seem to be straightforward. A CSR should be filed for this change documented the behavior change and compatibility assessment.
26-10-2019

[~smarks]: Yes, there is a workaround for JDK-8214129: http://hg.openjdk.java.net/jdk/jdk/rev/b0e751c70385.
10-12-2018

For what it's worth, List.copyOf, Set.copyOf, and Map.copyOf are idempotent, i.e., they won't make another copy if it's not necessary, and instead will simply return their argument. The comment from Eamonn McManus above (2005-09-14) regarding the synchronized wrappers is relevant. I'm hard-pressed to think of a well-formed locking protocol that uses multiple synchronized wrappers around the same underlying object. But I can imagine that somebody somewhere might be doing something odd that would be disrupted by the change in behavior. The situation for all the wrappers (synchronized, unmodifiable, and checked) is the same regarding object identity. If the system were changed so that it no longer made nested wrappers, this would likely be fine in most straightforward cases. It's the edge cases I'm concerned about. Certainly the application would be able to tell the difference if is sensitive to object identity, that is, if it uses System.identityHashCode or stores the objects in an IdentityHashMap. These are clearly edge cases, but after 20 years of having stable behavior, it's a distinct possibility that something relies on their exact current behavior. The (probably small) possibility of incompatibility, combined with the small benefit to be gained, has made me hesitate making any changes in this area. Presumably there's an alternative fix or workaround for JDK-8214129?
07-12-2018

I don't really buy the argument about penalizing the common cases. I'd expect that the overhead of an instanceof check is going to be negligible compared to whatever operations are going to be done on the returned object. But this isn't to say that I particularly think we need this optimization. Concerning the synchronized* methods, I think there could be backward-compatibility concerns. Today, two different callers of synchronizedList (say) on the same already-synchronized object will get two different Lists. Synchronizing on one will not affect the other. The spec for synchronizedList etc recomends synchronizing on the object before iterating over it, to get consistent results, so this is something we can expect people will do. The proposed change could modify the behaviour of existing code, in that two threads which today synchronize on different objects suddenly find themselves synchronizing on the same object. It is conceivable that this would lead to deadlock.
07-12-2018

The classes are "package private" in java.util. So an "attacker" would have to place the subclass in java.util. There should be no reason to defend against that kind of misuse.
07-12-2018

Using instanceof would fail to an attack where a user subclassed unmodifyableFoo and overrode the mutator methods, then passed the resulting collection to a method trying to create a secure unmodifyable collection by invoking unmodifyableFoo
07-12-2018

Using instanceof would probably be better.
07-12-2018

This issue is the root cause of JDK-8214129. In extreme cases, a large nested sequence of UnmodifiableList (etc.) objects will be constructed, and a StackOverflowException will be thrown when the client attempts to get any information from the collection.
05-12-2018

EVALUATION It's the old problem of optimizing rare use cases a lot while penalizing all other use cases a little. We'd like to keep the source code a model of elegance, and the proposed change is anything but elegant.
13-09-2005

WORK AROUND The user can easily create methods as suggested to avoid wrapping.
13-09-2005