madbean

Talking Tiger, generically speaking

16 Feb 2004

Maybe Java Generics (JSR 14) adds too complexity to programming in Java, maybe it doesn't. Maybe there was too much partaking of the generics Kool-aid.

Whatever.

You are going to have to learn to read Generics code, and maybe even how to write your own Generic classes. Hopefully this article will push those code-grokking neurons in the right direction.

(Dang namit: "generic" is just too generic a term. I will use a capitalised "Generic" to refer to the Java language features described by JSR 14; and "generic" just means "generic". Generics could be called "parametric polymorphism", but I don't think calling it that adds any clarity.)

(The code in this article successfully compiles with JDK 1.5.0-beta-b32c, your future mileage may vary.)

What Java Generics does for us

An important programming concept is knowing when you need to be specific, and when you should be abstract, or generic. Java already gives us one way of doing this, in the form of interface inheritance.

  • Interface inheritance allows us to be specific (about implementation) when implementing a class, but generic (about implementation) when using it.
  • For example, the implementation of ArrayList is all about growing and shrinking arrays (as it needs to be). But code that wants to keep track of a list of widgets needs to know nothing about those implementation details, it can just use the more generic List interface.

Whether you need to be specific or generic depends on the context, and there is more than one type of context. Interface inheritance fits one context, and Generics (JSR 14) fits another, orthogonal, context.

  • Generics (JSR 14) allows us to be generic (about types) when implementing a class, but specific (about types) when using it.
  • For example, List only needs to be defined as a list of some type <T>. But when using it, you care very-much what it is a list of.

Generics (JSR 14) provides us with another (orthogonal) tool for abstraction in our Java programs.

But in addition to a design-level facility, Generics provides a practical, code-level facility: Generics helps you avoid casting by transporting type information via type arguments and parameters.

Parameters vs arguments

In Java code, Generics will manifest itself in two forms, as type parameters and as type arguments. You will be familiar with the distinction between parameters and arguments in methods:

void foo(int a, int b) {
    ...
}

void bar(int c) {
    foo(c, 42);
}

Above, a and b are the parameters to foo(). When foo() is called, c and 42 are passed as arguments. Parameters are the "generic" part, and arguments are the "specific" part.

Also note that c is both a parameter of bar() and an argument to foo() (this will also happen in Generics with type parameters and arguments).

So, reading Generics is a matter of working out where a type parameter is being declared, and where a type argument is being passed.

Type parameters

Type parameters can appear in two locations, class (or interface) declarations, and method declarations. When type parameters are used, we are saying that this class/interface/method body is parameterized over those types. We can use those type parameters in the body as if they were a real classname we had imported, but we don't care what actual class it is.

Generic classes and interfaces

A Generic class/interface is declared by putting type parameters after the name of the class/interface. Type parameters begin and end with angle brackets1 and are separated by commas. You can specify more than one type parameter, and each type parameter can have a bound (constraint).

public class Foo <type param 1, type param 2> {
    ...
    type parameters used here.
    ...
}

Type bounds

A type bound places a constraint on the type arguments that can be passed to the type parameter.

<T>
No bound, any type argument can be used.
<SomeType>
Same as above (you are allowed to use parameter names with more than one letter, though no one ever seems to).
<T extends InputStream>
T can be any subclass of InputStream
<T extends Serializable>
T must implement the Serializable interface (note that extends is used here, even when talking about implementing interfaces).
<T extends InputStream & Serializable>
T must be a subclass of InputStream and implement Serializable.
<T extends Serializable & Runnable & Cloneable>
T must implement three interfaces.
<K, V>
Two type parameters (such as the type of the keys, and type of the values, in a Map).
<T, C extends Comparator<T>>
Two type parameters; the second bound is defined in terms of the first. (Type bounds can be mutually- or even self-recursive.)

An example Generic class

Lets define our own immutable "pair" class. Notice how we have declared fields and methods in terms of the type parameters. getFirst() is a method in a Generic class and uses one of the Generic type parameters, but that is different to a Generic method.

public class Pair<X, Y> {
    private final X a;
    private final Y b;
    
    public Pair(X a, Y b) {
        this.a = a;
        this.b = b;
    }

    public X getFirst() {
        return a;
    }
    public Y getSecond() {
        return b;
    }
}

Generic methods

Methods can have their own type parameters, independent of the type parameters of the enclosing class (or even if the enclosing class is not Generic). The type parameters go just before the return type of the method declaration.

class PairUtil 
{
    public static <A extends Number, B extends Number> double add(Pair<A, B> p) {
        return p.getFirst().doubleValue() + p.getSecond().doubleValue();
    }
    
    public static <A, B> Pair<B, A> swap(Pair<A, B> p) {
        A first = p.getFirst();
        B second = p.getSecond();
        return new Pair<B, A>(second, first);
    }
}

We have done a few things in the add() method:

  • The method is Generic over two type parameters A and B.
  • We don't care what A and B are, so long as they are subclasses of Number.
  • The argument to the method is a Pair; the type arguments to that Pair happen to include the type parameters to add(). (More about type arguments below.)

The second method, swap(), is even more funky:

  • The type parameters are used to define the return type, as well as the argument.
  • Local variables in the method are declared in terms of the type parameters.
  • The type parameters A and B are used as type arguments in the constructor call (more on that below).

Type Arguments

Type parameters are for defining Generic classes; type arguments are for using Generic classes. And you will be using Generic classes far more often than you write them.

Wherever you use a Generic classname, you need to supply the appropriate type arguments. These arguments go straight after the classname, surrounded by angle brackets. The arguments you supply must satisfy any type bounds on the type parameters. There are 6 main contexts where you can use type arguments, shown here (and explained below).

String s = "foo";
Integer i = new Integer(3);
Pair<String, Integer> p1;               // (A)
Pair<Integer, String> p2;
Pair<String, Integer> p3;

p1 = new Pair<String, Integer>(s, i);   // (B)

String s1 = p1.getFirst();
Integer i1 = p1.getSecond();

p2 = PairUtil.swap(p1);                 // (C)
p2 = PairUtil.<String,Integer>swap(p1); // (D)

Object o = p1;
if (o instanceof Pair<String, Integer>) { // (E)
    p3 = (Pair<String, Integer>) o;       // (F)
}

Variable declaration (A)

When using a Generic class for a variable (local, field or method parameter), you need to supply the type arguments.

Constructor call (B)

When calling the constructor of a Generic class, the type arguments must also follow the classname (that is, the constructor name).

Inferred Generic-method call (C)

When calling a Generic method, the method's arguments may contain enough information for the compiler to infer the type arguments to the method call. This has happened at line (C) above.

Explicit Generic-method call (D)

When calling a Generic method where you do need to supply the type arguments, the arguments go after the dot of the method call. This applies to static or non-static method calls.

instanceof operator (E)

The right-hand side of the instanceof operator can be a Generic class. In this case, you are permitted to supply type arguments to the Generic class; but those arguments will not be fully used to do the instanceof check. Instead, you get the following warning:

warning: [unchecked] unchecked cast to type Pair<java.lang.String,java.lang.Integer>
        if (o instanceof Pair<String, Integer>) { // (E)
            ^

The reason for this is because Generic types in Java are implemented via type erasure. I'm not going to go into that here; suffice it to stay that type arguments are forgotten somewhere between compile-time and run-time. (More on that below.)

Casting (F)

You can cast to a Generic class, and you can supply the type arguments. But you get a compiler warning for that, too.

warning: [unchecked] unchecked cast to type Pair<java.lang.String,java.lang.Integer>
            p3 = (Pair<String, Integer>) o;       // (F)
                                         ^

Wild-cards in type arguments

Java allows the use of a wild-card in a type argument, in order to simplify the use of Generics (easier to type, and to read).

For example, you may want to use a Generic class, but you don't particularly care what the type argument is. What you could do is specify a "dummy" type parameter T, as in the Generic method count_0() below. Alternatively, you can avoid creating a Generic method, and just use a ? wild-card as in count_1(). You should read List<?> as "a list of whatever".

public static <T> int count_0(List<T> list) {
    int count = 0;
    for (T n : list) {
        count++;
    }
    return count;
}

public static int count_1(List<?> list) {
    int count = 0;
    for (Object n : list) {
        count++;
    }
    return count;
}

Wild-cards with upper and lower bounds

Wild-cards become a bit more funky, because you can specify bounds on them. Firstly, consider this old-school, pre-Generics static method which appends one list to another.

public static void addAll_nonGeneric(List src, List dest) {
    for (Object o : src) {
        dest.add(o);
    }
}

List listOfNumbers = new ArrayList();
List listOfIntegers = new ArrayList();
...
addAll_nonGeneric(listOfIntegers, listOfNumbers);

Now, lets have a first-attempt at making that method Generic.

public static <T> void addAll_0(List<T> src, List<T> dest) {
    for (T o : src) {
        dest.add(o);
    }
}

List<Number> listOfNumbers = new ArrayList<Number>();
listOfNumbers.add(new Integer(3));
listOfNumbers.add(new Double(4.0));

List<Integer> listOfIntegers = new ArrayList<Integer>();
listOfIntegers.add(new Integer(3));
listOfIntegers.add(new Integer(4));

addAll_0(listOfIntegers, listOfNumbers); // syntax error:
// <T>addAll_0(java.util.List<T>,java.util.List<T>) cannot be applied to
// (java.util.List<java.lang.Integer>,java.util.List<java.lang.Number>); no instance(s)
// of type variable(s) T exist so that argument type java.util.List<java.lang.Number>
// conforms to formal parameter type java.util.List<T>

Remember that Integer is a subclass of Number; the compiler is compaining that you have not passed in two Lists with the same type argument. Just because one type argument is a subclass of another is not sufficient to allow a List<Number> to be considered the same as a List<Integer>.

But, logically, we want to allow a list of Integers to be appended to a list of Numbers (since Integers are Numbers). These next three methods all allow this. The first method explicitly uses two type parameters, with a bound that says one must be a subclass of another.

The next two methods do away with the need for a second type parameter. Instead, they use a bounded wild-card to express the required subclass/superclass relationship. You should read List<? extends T> as "A list of T, or any subclass of T". You can read List<? super T> as "A list of T, or any T's super-classes".

/**
 * Append src to dest, so long as "the types of things in src"
 * extend "the types of things in dest". (ie; append Integers to a list
 * of Numbers.)
 */
public static <T, S extends T> void addAll_1(List<S> src, List<T> dest) {
    for (S o : src) {
        dest.add(o);
    }
}

/**
 * Append src to dest, so long as "whatever the types of things in src are",
 * they extend "the types of things in dest".
 */
public static <T> void addAll_2(List<? extends T> src, List<T> dest) {
    for (T o : src) {
        dest.add(o);
    }
}

/**
 * Append src to dest, so long as "whatever the types of things dest can hold",
 * they are a superclass of "the types of things in src".
 */
public static <T> void addAll_3(List<T> src, List<? super T> dest) {
    for (T o : src) {
        dest.add(o);
    }
}

List<Number> listOfNumbers = new ArrayList<Number>();
listOfNumbers.add(new Integer(3));
listOfNumbers.add(new Double(4.0));

List<Integer> listOfIntegers = new ArrayList<Integer>();
listOfIntegers.add(new Integer(3));
listOfIntegers.add(new Integer(4));

addAll_1(listOfIntegers, listOfNumbers);
addAll_2(listOfIntegers, listOfNumbers);
addAll_3(listOfIntegers, listOfNumbers);

Using a Generic parameter in a throws clause

If you have a Generic class Foo<T>, you can use T in the body of Foo; as the type of variables, arguments, return types, and ... in the throws clause of methods (so long as T extends Exception). You may see this often, as it is a great trick for visitor patterns:

public interface Visitor<T, E extends Exception> {
    void visit(T o) throws E;
}

    
public <T, E extends Exception> void throwingVisit(List<T> list, Visitor<T,E> visitor)
    throws E
{
    for (T o : list) {
        visitor.visit(o);
    }
}

public void closeStreams(List<InputStream> streams) throws IOException {
    throwingVisit(streams, new Visitor<InputStream, IOException>() {
        public void visit(InputStream stream) throws IOException {
            stream.close();
        }
    });
}

Gotchas with type erasure

Generic types in Java are implemented via a process known as type erasure. You don't really need to know the details of type-erasure to be able to read Generic code; except there are two gotchas.

Breaking type-safety with casts

Consider the following code. Would you assume that line (A) is safe?

final List<String> stringList = new ArrayList<String>();
stringList.add("foo");
stringList.add("bar");

// some more code here
// ...

String s = stringList.get(0); // (A)

How can our list of strings go wrong? Because we can cast the type arguments away, then re-cast them back incorrectly. Let's insert some tricky code:

final List<String> stringList = new ArrayList<String>();
stringList.add("foo");
stringList.add("bar");

List whatAmI = stringList;
List<Integer> tricky = whatAmI; // (B)
tricky.add(0, new Integer(3)); // this succeeds at compile-time and at runtime

String s = stringList.get(0);  // ClassCastException at runtime

You get a compiler warning at (B) saying unchecked assignment, but you do not get a class-cast exception at runtime. The JVM knows if a class has type parameters, but the concrete type arguments are erased at compile time.

You can cast a List<String> to a List<Integer>; and then you can insert an Integer into that list. Gotcha!

No info about type arguments at runtime

The java.lang.Class class has a method getTypeParameters(), but no method to get any type arguments. The following code prints typeParam=E, not typeParam=java.lang.String.

final List<String> stringList = new ArrayList<String>();

String typeParam = stringList.getClass().getTypeParameters()[0].getName();
System.out.println("typeParam="+ typeParam);

In closing...

Reading Generic Java is not too hard; just work out what are type arguments and what are type parameters, and where they can be used. Then read the Javadoc to see what the type parameters mean; look to see how the parameters have been used in the signatures of the methods.


1 Which, incidentally, makes Generic classes hard to type when writing HTML pages... *sigh*.

  • Home
  • Blog