Cloak Around ImmutableList in Java

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) { //   ArrayList,      -  arr = original.toArray(); } this.data = arr; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

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.)