Saturday, September 6, 2014

Type Erasure and Bridge Methods in Generics

"Generics programming is about abstracting and classifying algorithms and data structures. It's goal is the incremental construction of systematic catalogs of useful, efficient and abstract algorithms and data structures"

-Alexander Stepanov

Generics programming concepts are nothing new. And it is not something Java introduced to the world (Ada, Eiffel and C++ supported generics even before Java did). In 1988 David Musser and Alexander Stepanov introduced and defined this concept.

Java introduced Generics in 2004 (Java 5) and implement it as type erasure. Type erasure consist of following steps:

  • Replace all type parameters in generic types with their bounds or Object if the type parameters are unbounded. The produced bytecode, therefore, contains only ordinary classes, interfaces, and methods.
  • Insert type casts if necessary to preserve type safety.
  • Generate bridge methods to preserve polymorphism in extended generic types.
You can conclude from this, that generics in java are purely compile time feature. Because of this, generics in Java incur no run-time overhead and it is important to point this out. I suspect they implement Generics as compile time correctness because they were focused on backward compatibility.

Here is simple demonstration of replacing generics type with their bounds. In this case bound is Object. I know there are better ways of copy array to collection (like Collections.addAll method), but this is only for demonstration purpose, so I will stick with it. ;)
public static <T> void array2Coll(T[] a, Collection<T> c) {
  for (T o : a) {
    c.add(o);
  }
}
After type erasure code will look like this:
public static void array2Coll(Object[] a, Collection c) {
  for (Object o : a) {
    c.add(o);
  }
}
As you can see, generics type has been replaced with Object type (it's upper bound). If their bound would be something else (for example <T> extends Comparable), then generics would be replaced by Comparable.

Sometimes compiler create a synthetic method, called a bridge method, as part of the type erasure process. Next examples will explain why and when compiler create this methods.
public class Node<T> {
  private T data;

  public Node(T data) { this.data = data; }
    public void setData(T data) {
      System.out.println("Node.setData");
      this.data = data;
    }
  }

public class MyNode extends Node<Integer> {
  public MyNode(Integer data) { 
    super(data); 
  }

  public void setData(Integer data) {
    System.out.println("MyNode.setData");
    super.setData(data);
  }
}
After type erasure compiler will create one synthetic bridge method for second class:
public class Node {

  private Object data;

  public void setData(Object data) {
    System.out.println("Node.setData");
    this.data = data;
  }
}

public class MyNode extends Node {

  public MyNode(Integer data) { 
    super(data); 
  }

  // synthetic bridge method
  public void setData(Object data) {
    setData((Integer) data);
  }

  public void setData(Integer data) {
    System.out.println(Integer data);
    super.setData(data);
  }
}
In this example bridge method was created because MyNode class was missing setData method for Object parameter. Without this method we wouldn't have proper polymorphic behavior and next example would throw ClassCastException.
  MyNode mn = new MyNode(5);
  Node n = mn;  
  n.setData("Hello"); //throws ClassCastException

No comments:

Post a Comment