Once Again About ImmutableList in Java

In my previous article, “ Cloaking around the ImmutableList in Java, ” I proposed a solution to the problem of the absence of immutable lists in Java, which is not fixed , neither now nor ever, in the article.

The solution then was worked out only at the level of “there is such an idea”, and the implementation in the code was crooked, therefore everything was perceived somewhat skeptically. In this article, I propose a modified solution. The logic of use and API are brought to an acceptable level. Implementation in code is up to beta level.

Formulation of the problem

We will use the definitions from the original article. In particular, this means that ImmutableList



is an immutable list of references to some objects. If these objects are not immutable, then the list will not be an immutable object either, despite the name. In practice, this is unlikely to hurt anyone, but in order to avoid unjustified expectations it is necessary to mention.

It is also clear that the immutability of the list can be "hacked" by means of reflections, or by creating your own classes in the same package, followed by climbing into the protected fields of the list, or something similar.

Unlike the original article, we will not adhere to the principle of “all or nothing”: the author there seems to believe that if the problem cannot be solved at the JDK level, then nothing should be done. (Actually, there’s another question, “cannot be solved” or “the Java authors didn’t have a desire to solve it.” It seems to me that it would still be possible by adding additional interfaces, classes and methods to bring existing collections closer to desired appearance, although less beautiful than if you had thought about it right away, but now it's not about that.)

We will create a library that can successfully coexist with existing collections in Java.

The main ideas of the library:

• There are ImmutableList
  
  
  
  and MutableList
  
  
  
  . By casting types it is impossible to get one from the other.
• In our project, which we want to improve using the library, we replace all the List
  
  
  
  s with one of these two interfaces. If at some point you cannot do without the List
  
  
  
  , then at the first opportunity we will convert the List
  
  
  
  from / to one of two interfaces. The same applies to the moments of receiving / transmitting data to third-party libraries using List
  
  
  
  .
• Mutual conversions between ImmutableList
  
  
  
  , MutableList
  
  
  
  , List
  
  
  
  should be performed as quickly as possible (that is, without copying lists, if possible). Without "cheap" round-trip conversions, the whole idea begins to look dubious.

It should be noted that only lists are considered, since at the moment only they are implemented in the library. But nothing prevents the library from complementing with Set



and Map



s.

API

ImmutableList

ImmutableList



is the successor of ReadOnlyList



(which, as in the previous article, is a copied List



interface from which all mutating methods are thrown). Methods added:

 List<E> toList(); MutableList<E> mutable(); boolean contentEquals(Iterable<? extends E> iterable);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

The toList



method provides the ability to pass an ImmutableList



to pieces of code waiting for a List



. A wrapper is returned in which all modifying methods return an UnsupportedOperationException



, and the remaining methods are redirected to the original ImmutableList



.

The mutable



method converts an ImmutableList



to a MutableList



. A wrapper is returned in which all methods are redirected to the original ImmutableList



until the first change. Before the change, the wrapper is untied from the original ImmutableList



, copying its contents to the internal ArrayList



, to which all operations are then redirected.

The contentEquals



method contentEquals



intended to compare the contents of a list with the contents of an arbitrary Iterable



passed (of course, this operation is meaningful only for those Iterable



implementations that have some distinct order of elements).

Note that in our implementation of ReadOnlyList



, the iterator



and listIterator



return standard java.util.Iterator



/ java.util.ListIterator



. These iterators contain modifying methods that will have to be suppressed by throwing an UnsupportedOperationException



. It would be preferable to make our ReadOnlyIterator



, but in this case we could not write for (Object item : immutableList)



, which would immediately spoil all the pleasure of using the library.

MutableList

MutableList



is the descendant of the regular List



. Methods added:

 ImmutableList<E> snapshot(); void releaseSnapshot(); boolean contentEquals(Iterable<? extends E> iterable);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

The snapshot



method is intended to get a “snapshot” of the current state of MutableList



in the form of ImmutableList



. The “snapshot” is saved inside the MutableList



, and if the state has not changed at the time of the next method call, the same instance of ImmutableList



. The “snapshot” stored inside is discarded the first time any modifying method is called, or when releaseSnapshot



called. The releaseSnapshot



method can be used to save memory if you are sure that no one will need a “snapshot” anymore, but modifying methods will not be called soon.

Mutabor

The Mutabor



class provides a set of static methods that are the “entry points” to the library.

Yes, the project is now called “mutabor” (it is consonant with “mutable”, and in translation it means “I will transform”, which is in good agreement with the idea of ​​quickly “transforming” some types of collections into others).

 public static <E> ImmutableList<E> copyToImmutableList(E[] original); public static <E> ImmutableList<E> copyToImmutableList(Collection<? extends E> original); public static <E> ImmutableList<E> convertToImmutableList(Collection<? extends E> original); public static <E> MutableList<E> copyToMutableList(Collection<? extends E> original); public static <E> MutableList<E> convertToMutableList(List<E> original);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

copyTo*



methods copyTo*



designed to create appropriate collections by copying the provided data. The convertTo*



methods convertTo*



for quick conversion of the transferred collection to the desired type, and if it was not possible to quickly convert, they perform slow copying. If the quick conversion was successful, then the original collection is cleared, and it is assumed that it will not be used in the future (although it can, but this hardly makes sense).

The calls to the constructors of the ImmutableList



/ MutableList



implementation ImmutableList



MutableList



hidden. It is assumed that the user only deals with interfaces, he does not create such objects, and uses the methods described above to transform collections.

Implementation details

ImmutableListImpl

Encapsulates an array of objects. The implementation roughly corresponds to the ArrayList



implementation, from which all modifying methods and checks for concurrent modification are thrown.

The implementation of the toList



and contentEquals



also quite trivial. The toList



method returns a wrapper that redirects calls to a given ImmutableList



; slow copying of data does not occur.

The mutable



method returns a MutableListImpl



created based on this ImmutableList



. Data copying does not occur until any modifying method is called on the received MutableList



.

MutableListImpl

Encapsulates links to ImmutableList



and List



. When creating an object, only one of these two links is always filled, the other remains null



.

 protected ImmutableList<E> immutable; protected List<E> list;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Immutable methods redirect calls to ImmutableList



if it is not null



, and to List



otherwise.

Modifying methods redirect calls to List



, after initializing:

 protected void beforeChange() { if (list == null) { list = new ArrayList<>(immutable.toList()); } immutable = null; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

The snapshot



method looks like this:

 public ImmutableList<E> snapshot() { if (immutable != null) { return immutable; } immutable = InternalUtils.convertToImmutableList(list); if (immutable != null) { //    //   ,  . //     immutable     . list = null; return immutable; } immutable = InternalUtils.copyToImmutableList(list); return immutable; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

The implementation of the releaseSnapshot



and contentEquals



trivial.

This approach allows you to minimize the number of copies of data during "ordinary" use, replacing copies with fast conversions.

Fast list conversion

Fast conversions are possible for the ArrayList



or Arrays$ArrayList



classes (the result of the Arrays.asList()



method). In practice, in the vast majority of cases, it is precisely these classes that come across.

Inside these classes contain an array of elements. The essence of a quick conversion is to get a reference to this array through reflections (this is a private field) and replace it with a reference to an empty array. This ensures that the only reference to the array remains with our object, and the array remains unchanged.

In the previous version of the library, fast conversions of collection types were performed by calling the constructor. At the same time, the original collection object deteriorated (it became unsuitable for further use), which you do not unconsciously expect from the designer. Now a special static method is used for conversion, and the original collection does not spoil, but is simply cleared. Thus, frightening unusual behavior was eliminated.

Problems with equals / hashCode

Java collections use a very strange approach to implement equals



and hashCode



methods.

The comparison is carried out according to the content, which seems to be logical, but the class of the list itself is not taken into account. Therefore, for example, ArrayList



and LinkedList



with the same content will be equals



.

 public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof List)) return false; ListIterator<E> e1 = listIterator(); ListIterator e2 = ((List) o).listIterator(); while (e1.hasNext() && e2.hasNext()) { E o1 = e1.next(); Object o2 = e2.next(); if (!(o1==null ? o2==null : o1.equals(o2))) return false; } return !(e1.hasNext() || e2.hasNext()); } public int hashCode() { int hashCode = 1; for (E e : this) hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); return hashCode; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Thus, now absolutely all implementations of List



must have a similar implementation of equals



(and, as a result, hashCode



). Otherwise, you can get situations when a.equals(b) && !b.equals(a)



, which is not good. A similar situation is with Set



and Map



.

When applied to the library, this means that the implementation of equals



and hashCode



for MutableList



predefined, and in such an implementation, ImmutableList



and MutableList



with the same contents cannot be equals



(since ImmutableList



not a List



). Therefore, contentEquals



methods have been added to compare content.

The implementation of the equals



and hashCode



methods for ImmutableList



made completely similar to the version from AbstractList



, but with the replacement of List



by ReadOnlyList



.

Total

The library sources and tests are posted by reference in the form of a maven project.

In case someone wants to use the library, he started a group in contact for "feedback".

Using the library is pretty obvious, here is a short example:

 private boolean myBusinessProcess() { List<Entity> tempFromDb = queryEntitiesFromDatabase("SELECT * FROM my_table"); ImmutableList<Entity> fromDb = Mutabor.convertToImmutableList(tempFromDb); if (fromDb.isEmpty() || !someChecksPassed(fromDb)) { return false; } //... MutableList<Entity> list = fromDb.mutable(); //time to change list.remove(1); ImmutableList<Entity> processed = list.snapshot(); //time to change ended //... if (!callSideLibraryExpectsListParameter(processed.toList())) { return false; } for (Entity entity : processed) { outputToUI(entity); } return true; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Good luck to all! Send bug reports!