I read the article “There will be no immutable collections in Java - neither now, nor ever” and thought that the problem of the absence of immutable lists in Java, which makes the author sad, is quite solvable on a limited scale. I offer my thoughts and pieces of code on this subject.
(This is an answer article, read the original article first.)
UnmodifiableList vs ImmutableList
The first question that arose is: why do I need a UnmodifiableList , if there is an ImmutableList ? As a result of the discussion, two ideas regarding the meaning of UnmodifiableList are seen in the comments of the original article:
- the method receives an
UnmodifiableList , it cannot change it itself, but knows that the contents can be changed by another thread (and knows how to handle it correctly) - other threads do not affect,
UnmodifiableList and ImmutableList are equivalent for a method, but UnmodifiableList used as a more “lightweight” one.
The first option seems too rare in practice. Thus, if it is possible to make an “easy” implementation of ImmutableList , then UnmodifiableList becomes not very necessary. Therefore, in the future, we will forget about it and will only implement ImmutableList .
Formulation of the problem
We will implement the ImmutableList option:
- The API should be identical to the regular
List API in the "reading" part. The “writing” part should be absent. ImmutableList and List should not be related by inheritance relations. Why so - understands the original article.- It makes sense to do the implementation by analogy with
ArrayList . This is the easiest option. - The implementation should avoid copying arrays whenever possible.
ImmutableList implementation
First, we deal with the API. We examine the Collection and List interfaces and copy the “reading” part from them into our new interfaces.
public interface ReadOnlyCollection<E> extends Iterable<E> { int size(); boolean isEmpty(); boolean contains(Object o); Object[] toArray(); <T> T[] toArray(T[] a); boolean containsAll(Collection<?> c); } public interface ReadOnlyList<E> extends ReadOnlyCollection<E> { E get(int index); int indexOf(Object o); int lastIndexOf(Object o); ListIterator<E> listIterator(); ListIterator<E> listIterator(int index); ReadOnlyList<E> subList(int fromIndex, int toIndex); }
Next, create the ImmutableList class. The signature is similar to ArrayList (but implements the ReadOnlyList interface instead of List ).
public class ImmutableList<E> implements ReadOnlyList<E>, RandomAccess, Cloneable, Serializable
We copy the implementation of the class from ArrayList and firmly refactor, throwing out everything related to the "writing" part, checking for concurrent modification, etc.
Constructors will be as follows:
public ImmutableList() public ImmutableList(E[] original) public ImmutableList(Collection<? extends E> original)
The first creates an empty list. The second creates a list by copying the array. We can’t do without copying if we want to achieve immutable. The third is more interesting. A similar ArrayList constructor also copies data from the collection. We will do the same, unless orginal is an instance of ArrayList or Arrays$ArrayList (this is what is returned by the Arrays.asList() method). We can safely assume that these cases will cover 90% of the constructor calls.
In these cases, we will "steal" the original array through reflections (there is hope that this is faster than copying gigabyte arrays). The essence of "theft":
- we get to the private field
original , which stores the array ( ArrayList.elementData ) - copy the link to the array to ourselves
- put in the source field null
protected static final Field data_ArrayList; static { try { data_ArrayList = ArrayList.class.getDeclaredField("elementData"); data_ArrayList.setAccessible(true); } catch (NoSuchFieldException | SecurityException e) { throw new IllegalStateException(e); } } public ImmutableList(Collection<? extends E> original) { Object[] arr = null; if (original instanceof ArrayList) { try { arr = (Object[]) data_ArrayList.get(original); data_ArrayList.set(original, null); } catch (@SuppressWarnings("unused") IllegalArgumentException | IllegalAccessException e) { arr = null; } } if (arr == null) {
As a contract, we assume that when the constructor is called, the mutable list is ImmutableList to an ImmutableList . The original list cannot be used after that. When trying to use, a NullPointerException arrives. This ensures that the "stolen" array will not change and our list will be really immutable (except for the option when someone gets to the array through reflections).
Other classes
Suppose we decide to use an ImmutableList in a real project.
The project interacts with libraries: receives from them and sends them various lists. In the vast majority of cases, these lists will be an ArrayList . The described implementation of ImmutableList allows ImmutableList to quickly convert the resulting ArrayList to an ImmutableList . It is also required to implement conversion for lists sent to libraries: ImmutableList to List . For fast conversion, you need an ImmutableList wrapper that implements List , throwing exceptions when trying to write to the list (similar to Collections.unmodifiableList ).
Also, the project itself somehow processes the lists. It makes sense to create a MutableList class that represents a mutable list, with an implementation based on ArrayList . In this case, you can refactor the project by substituting instead of all ArrayList class that explicitly declares the intent: either ImmutableList or MutableList .
Need a quick conversion from ImmutableList to MutableList and vice versa. At the same time, unlike the conversion of ArrayList to ImmutableList , we can no longer spoil the original list.
Converting there will usually be slow, with copying the array. But for cases when the received MutableList does not always change, you can make a wrapper: MutableList , which saves a link to the ImmutableList and uses it for "reading" methods, and if the "writing" method is called, then only forgets about the ImmutableList , after copying the contents of it array to itself, and then it already works with its array (something remotely similar is in CopyOnWriteArrayList ).
Converting "back" means receiving a snapshot of the contents of the MutableList at the time the method is called. Again, in most cases you cannot do without copying an array, but you can make a wrapper to optimize cases of several conversions between which the contents of the MutableList did not change. Another option for converting "back": some data is collected in a MutableList , and when the data collection is completed, a MutableList needs to be converted forever to an ImmutableList . It is also implemented without problems with another wrapper.
Total
The results of the experiment in the form of code are posted here
ImmutableList itself is ImmutableList , described in the "Other classes" section (yet?) Is not implemented.
We can assume that the premise of the original article, "immutable collections in Java will not be" is erroneous.
If there is a desire, then it is quite possible to use a similar approach. Yes, with small crutches. Yes, not within the entire system, but only in their projects (although if many penetrate, then it will gradually be pulled into libraries).
One thing: if there is a desire ... (Tahiti, Tahiti ... We were not in any Tahiti! They feed us well here.)