rss

Using Java Generics

Tuesday, February 9, 2010

Many programmers are unsatisfied with the restrictions caused by the way generics are implemented in Java. Generics are implemented using erasure, in which generic type parameters are simply removed at compile time (Thus not available to the JVM at runtime). However, that doesn't render generics useless.

Since Java has two compilation steps, during the first phase (compile-time) the compiler will insert necessary casts in the code (so you don't have to) based on the generic type parameters, and then perform the typechecking. During the second phase the JVM doesn’t make use of type information for type parameters (though it seems like the information is stored in the ".class" file metadata area).

Since the JVM isn’t aware of the type parameters associated with a type, it isn’t able to infer that certain operations are safe.
Map<Integer,String> m = new HashMap<Integer,String>();
m.put(1, "SomeString");
String s = m.get(1);
The new Java language allows the above code, but it gets compiled to:
Map m = new HashMap();
m.put(1, "SomeString");
String s = (String) m.get(1);
The lack of runtime type information causes things to not work as expected.

Generic Arrays

You cannot instantiate arrays of concrete parameterized types.
List<Point3D>[] l = new List<Point3D>[10];
The compiler will reject that because it could lead to a type error.

The problem stems from the fact that every time you store a value into an array, there’s a runtime check involved. While that check might be optimized away in certain situations, the language spec doesn’t identify those situations; as far as the semantics are concerned, arrays are not really type safe.

The main source of all the array-related issues is that Java arrays are covariant even though this is not typesafe. That’s why storing to an array requires runtime checks. If array variance was handled properly, there’d be no problem.

Casts

Runtime type casting relies on runtime type information. When you don’t have that information, casts don’t work correctly.
public void fun(Object o) {
  List<Integer> l = (List<Integer>) o;
}
The compiler will issue a warning on line 2 saying that the cast is unchecked. It’s not fully unchecked, because the JVM will check to see if it’s actually a "List", but it can’t check whether it’s a list of Integers or Point3D because that information has been erased.

Since it’s only a warning, you can execute that code and this particular fragment will run just fine. The problem only surfaces when you try and access one of the list elements with, for example, get(). The Java compiler automatically casts the return value of get() to Integer so if the list you got actually contained Point3D objects, you’ll end up with a ClassCastException.

The root problem here is that casts aren’t really type safe. Many functional programming languages use type-safe tagged unions to achieve the similar functionality.

Can’t Call Constructor
public class Pair<T> {
    T x1, x2;
    public Pair() {}
    public void init() {
        x1 = new T();  // Error
        x2 = new T();  // Error
    }
}
This limitation isn’t solely due to type erasure. This is disallowed because there’s no guarantee that the class "T" has a constructor that takes zero parameters. However, you can get around this by using a factory:
public interface Factory<T> {
    T create();
}

public  class Container<T> {
    Factory<T> factory;
    T x1, x2;

    public Pair(Factory<T> factory) { 
        this.factory = factory 
    }

    public void init() {
        x1 = factory.create ();
        x2 = factory.create ();
    }
}

Hacking Generics

Let’s assume we want to create an array to handle generic operations with generic types (e.g. Array multiplication of numeric and non-numeric types: Integer, Point3D, String, ..)

As you know you can’t create an array of generics with T[] t = new T[1] and we can't use Class clazz = T.getClass(). However inside a static context we can access some information about the generic type using the following code:
Class clazz = (Class) ((java.lang.reflect.ParameterizedType)
    getClass().getGenericSuperclass()
        ).getActualTypeArguments()[0];
Now that we know the type, it is possible to allocate the generic array and optionally instantiate it.
array = (T[]) Array.newInstance(clazz, size); 

/** Call default constructor */
array[0] = (T) clazz.newInstance();

/** Call constructor T(String, Integer) */
array[0] = (T) clazz.getConstructor(String.class, 
                Integer.class).newInstance("SomeString", 1);
In order to be successful with the static modifier, we need to code the generic array class as an inner class (see next code snippet). The inner class GenericArrayImpl will provide the basic implementation of a generic array that also initializes the generic objects. Specific array operations are implemented by specialized generic array implementations (see NonNumericArray and NumericArray).
public interface IGenericArray<T> {
    public T get(int i);
    public void multiply(T obj);
}

public class GenericArray {

   /** Contains the implementation of common methods */
   private static abstract class GenericArrayImpl <T> 
                           implements IGenericArray<T> {
      …
   }

   /** Our non-numeric class */
   private static class NonNumericArray extends 
                  GenericArrayImpl<NonNumericClass> { 

      public NonNumericArray(int initialSize) {
         super(initialSize);
      }
 
      @Override
      public void multiply(NonNumericClass obj) {
         for (int j = 0; j < size; j++)
            array[j].multiply(obj);
      } 
   }

   private static class NumericArray extends 
                        GenericArrayImpl <Integer> {
 
      public NumericArray(int initialSize) {
         super(initialSize);
      }
 
      @Override
      public void multiply(Integer obj) {
         for (int j = 0; j < size; j++)
            array[j] *= obj;
      } 
   }
}
A possible implementation for GenericArrayImpl may be:
private static abstract class GenericArrayImpl<T> 
                             implements IGenericArray<T> {

   protected T[] array;
   protected int size;
 
   public GenericArrayImpl(int initialSize) {
      this.size = initialSize;
      initialize();
   }

   @SuppressWarnings({ "unchecked" })
   private void initialize(){  
      Class clazz = 
      (Class) ((java.lang.reflect.ParameterizedType) 
            getClass().getGenericSuperclass()
            ).getActualTypeArguments()[0];

      /** Allocate the array */
      array = (T[]) Array.newInstance(clazz, size); 
  
      /** Initialize objects in the array */
      for (int j = 0; j < size; j++){
         try {
            /** Call default constructor */
            if(array[j] == null)
               array[j] = (T) clazz.newInstance();
   
            /** 
             * Perform some other operations: 
             * array[j].doSomething();
             */
         }
         catch (InstantiationException e) {
            e.printStackTrace();
         }
         catch (IllegalAccessException e) {
            e.printStackTrace();
         }
         catch (IllegalArgumentException e) {
            e.printStackTrace();
         }
         catch (SecurityException e) {
            e.printStackTrace();
         }
      }
   }
 
   /** Common implementation (to avoid duplicated code) */
   public T get(int p){
      return array[p];
   }
}
Now we implement the non-numeric class, where the multiplication is defined.
class NonNumericClass {

   private String data;
 
   public NonNumericClass (){
      data = "default";
   }
 
   public void multiply(NonNumericClass c){
      this.data += c.data;
   }
 
   @Override
   public String toString(){
      return data;
   }
}
And voilá:
/** Working with arrays of NonNumericClass */
IGenericArray<NonNumericClass> a = new GenericArray.NonNumericArray(1);
a.multiply(new NonNumericClass());

/** Working with arrays of Integer */
IGenericArray<Integer> b = new GenericArray.NumericArray(1);
b.multiply(new Integer(1));
References

[1] Type erasure is not evil. cakoose.com. http://cakoose.com/wiki/type_erasure_is_not_evil. Retrieved on 2010-09-02.