O'Reilly    
 Published on O'Reilly (http://oreilly.com/)
 See this if you're having trouble printing code examples


O'Reilly Book Excerpts: Java Generics and Collections

Java Generics and Collections: Evolution, Not Revolution, Part 2

by Philip Wadler, Maurice Naftalin

Editor's Note: In last week's excerpt from Chapter 5 of Java Generics and Collections, authors Maurice Naftalin and Philip Wadler considered the situation of having a code-base that doesn't use generics, and how you can migrate to generics without having to cut completely over in one release. They portray the situation with simple examples of "library" and "client" code, and then consider the migration of the library to generics while leaving the client non-genericized. In this second part of the excerpt, they move on to the trickier case: genericizing the client, while leaving the library alone.

Legacy Library with Generic Client

It usually makes sense to update the library before the client, but there may be cases when you wish to do it the other way around. For instance, you may be responsible for maintaining the client but not the library; or the library may be large, so you may want to update it gradually rather than all at once; or you may have class files for the library, but no source.

In such cases, it makes sense to update the library to use parameterized types in its method signatures, but not to change the method bodies. There are three ways to do this: by making minimal changes to the source, by creating stub files, or by use of wrappers. We recommend use of minimal changes when you have access to source and use of stubs when you have access only to class files, and we recommend against use of wrappers.

Evolving a Library using Minimal Changes

The minimal changes technique is shown in Example 5.3. Here the source of the library has been edited, but only to change method signatures, not method bodies. The exact changes required are highlighed in boldface. This is the recommended technique for evolving a library to be generic when you have access to the source.

Example 5-3. Evolving a library using minimal changes

m/Stack.java:
  interface 
 
 Stack<E> {
    public boolean empty();
    public void push(E elt);
    public E pop();
  }

m/ArrayStack.java:
  @SuppressWarnings("unchecked")
  class ArrayStack<E> implements Stack<E> {
    private List list;
    public ArrayStack() { list = new ArrayList(); }
    public boolean empty() { return list.size() == 0; }
    public void push(E elt) { list.add(elt); }  // unchecked call
    public E pop() {
      Object elt = list.remove(list.size()-1);
      return (E)elt;  // unchecked cast
    }
    public String toString() { return "stack"+list.toString(); }
  }

m/Stacks.java:
  @SuppressWarnings("unchecked")
  class Stacks {
    public static <T> Stack<T> reverse(Stack<T> in) {
      Stack out = new ArrayStack();
      while (!in.empty()) {
        Object elt = in.pop();
        out.push(elt);  // unchecked call
      }
      return out;  // unchecked conversion
    }
  }

To be precise, the changes required are:

It is worth noting a few changes that we do not need to make. In method bodies, we can leave occurrences of Object as they stand (see the first line of pop in ArrayStack), and we do not need to add type parameters to any occurrences of raw types (see the first line of reverse in Stacks). Also, we need to add a cast to a return clause only when the return type is a type parameter (as in pop) but not when the return type is a parameterized type (as in reverse).

With these changes, the library will compile successfully, although it will issue a number of unchecked warnings. Following best practice, we have commented the code to indicate which lines trigger such warnings:

% javac -Xlint:unchecked m/Stack.java m/ArrayStack.java m/Stacks.java
m/ArrayStack.java:7: warning: [unchecked] unchecked call to add(E)
as a member of the raw type java.util.List
    public void push(E elt)  list.add(elt);   // unchecked call
                                      ^
m/ArrayStack.java:10: warning: [unchecked] unchecked cast
found   : java.lang.Object
required: E
      return (E)elt;  // unchecked cast
                ^
m/Stacks.java:7: warning: [unchecked] unchecked call to push(T)
as a member of the raw type Stack
        out.push(elt);  // unchecked call
                ^
m/Stacks.java:9: warning: [unchecked] unchecked conversion
found   : Stack
required: Stack<T>
      return out;  // unchecked conversion
             ^
4 warnings

To indicate that we expect unchecked warnings when compiling the library classes, the source has been annotated to suppress such warnings.

@SuppressWarnings("unchecked");

(The suppress warnings annotation does not work in early versions of Sun's compiler for Java 5.) This prevents the compiler from crying wolf—we've told it not to issue unchecked warnings that we expect, so it will be easy to spot any that we don't expect. In particular, once we've updated the library, we should not see any unchecked warnings from the client. Note as well that we've suppressed warnings on the library classes, but not on the client.

The only way to eliminate (as opposed to suppress) the unchecked warnings generated by compiling the library is to update the entire library source to use generics. This is entirely reasonable, as unless the entire source is updated there is no way the compiler can check that the declared generic types are correct. Indeed, unchecked warnings are warnings—rather than errors—largely because they support the use of this technique. Use this technique only if you are sure that the generic signatures are in fact correct. The best practice is to use this technique only as an intermediate step in evolving code to use generics throughout.

Evolving a Library using Stubs

The stubs technique is shown in Example 5.4. Here we write stubs with generic signatures but no bodies. We compile the generic client against the generic signatures, but run the code against the legacy class files. This technique is appropriate when the source is not released, or when others are responsible for maintaining the source.

Example 5-4. Evolving a library using stubs

s/Stack.java:
  interface Stack<E> {
    public boolean empty();
    public void push(E elt);
    public E pop();
  }

s/StubException.java:
  class StubException extends UnsupportedOperationException {}

s/ArrayStack.java:
  class ArrayStack<E> implements Stack<E> {
    public boolean empty() { throw new StubException(); }
    public void push(E elt) { throw new StubException(); }
    public E pop() { throw new StubException(); }
    public String toString() { throw new StubException(); }
  }

s/Stacks.java:
  class Stacks {
    public static <T> Stack<T> reverse(Stack<T> in) {
      throw new StubException();
    }
  }

To be precise, we introduce the same modifications to interface and class declarations and method signatures as with the minimal changes technique, except we completely delete all executable code, replacing each method body with code that throws a StubException (a new exception that extends UnsupportedOperationException).

When we compile the generic client, we do so against the class files generated from the stub code, which contain appropriate generic signatures (say, in directory s). When we run the client, we do so against the original legacy class files (say, in directory l).

% javac -classpath s g/Client.java
% java -ea -classpath l g/Client

Again, this works because the class files generated for legacy and generic files are essentially identical, save for auxiliary information about the types. In particular, the generic signatures that the client is compiled against match the legacy signatures (apart from auxiliary information about type parameters), so the code runs successfully and gives the same answer as previously.

Evolving a Library using Wrappers

The wrappers technique is shown in Example 5.5. Here we leave the legacy source and class files unchanged, and provide a generic wrapper class that accesses the legacy class via delegation. We present this technique mainly in order to warn you against its use—it is usually better to use minimal changes or stubs.

Example 5-5. Evolving a library using wrappers

// Don't do this—use of wrappers is not recommended!

l/Stack.java, l/Stacks.java, l/ArrayStack.java:
  // As in Example 5.1

w/GenericStack.java:
  interface GenericStack<E> {
    public Stack unwrap();
    public boolean empty();
    public void push(E elt);
    public E pop();
  }

w/GenericStackWrapper.java:
  @SuppressWarnings("unchecked")
  class GenericStackWrapper<E> implements GenericStack<E> {
    private Stack stack;
    public GenericStackWrapper(Stack stack) { this.stack = stack; }
    public Stack unwrap() { return stack; }
    public boolean empty() { return stack.empty(); }
    public void push(E elt) { stack.push(elt); }
    public E pop() { return (E)stack.pop(); }  // unchecked cast
    public String toString() { return stack.toString(); }
  }

w/GenericStacks.java:
  class GenericStacks {
    public static <T> GenericStack<T> reverse(GenericStack<T> in) {
      Stack rawIn = in.unwrap();
      Stack rawOut = Stacks.reverse(rawIn);
      return new GenericStackWrapper<T>(rawOut);
    }
  }

w/Client.java:
  class Client {
    public static void main(String[] args) {
      GenericStack<Integer> stack
        = new GenericStackWrapper<Integer>(new ArrayStack());
      for (int i = 0; i<4; i++) stack.push(i);
      assert stack.toString().equals("stack[0, 1, 2, 3]");
      int top = stack.pop();
      assert top == 3 && stack.toString().equals("stack[0, 1, 2]");
      GenericStack<Integer> reverse = GenericStacks.reverse(stack);
      assert stack.empty();
      assert reverse.toString().equals("stack[2, 1, 0]");
    }
  }

This techique creates a parallel hierarchy of generic interfaces and wrapper classes. To be precise, we create a new interface GenericStack corresponding to the legacy interface Stack, we create a new class GenericWrapperClass to access the legacy implementation ArrayStack, and we create a new class GenericStacks corresponding to the legacy convenience class Stacks.

The generic interface GenericStack is derived from the legacy interface Stack by the same method used in the previous sections to update the signatures to use generics. In addition, a new method unwrap is added, that extracts the legacy implementation from a wrapper.

The wrapper class GenericStackWrapper<E> implements GenericStack<E> by delegation to a Stack. The constructor takes an instance that implements the legacy interface Stack, which is stored in a private field, and the unwrap method returns this instance. Because delegation is used, any updates made to the underlying legacy stack will be seen through the generic stack view offered by the wrapper.

The wrapper implements each method in the interface (empty, push, pop) by a call to the corresponding legacy method; and it implements each method in Object that is overridden in the legacy class (toString) similarly. As with minimal changes, we add an unchecked cast to the return statement when the return type contains a type parameter (as in pop); without this cast you will get an error rather than an unchecked warning.

A single wrapper will suffice for multiple implementations of the same interface. For instance, if we had both ArrayStack and LinkedStack implementations of Stack, we could use GenericStackWrapper<E> for both.

The new convenience class GenericStacks is implemented by delegation to the legacy class Stacks. The generic reverse method unwraps its argument, calls the legacy reverse method, and wraps its result.

Required changes to the client in Example 5.5 are shown in boldface.

Wrappers have a number of disadvantages compared to minimal changes or stubs. Wrappers require maintaining two parallel hierarchies, one of legacy interfaces and classes and one of generic interfaces and classes. Conversion by wrapping and unwrapping between these can become tedious. If and when the legacy classes are generified properly, further work will be required to remove the redundant wrappers.

Wrappers also present deeper and subtler problems. If the code uses object identity, problems may appear because the legacy object and the wrapped object are distinct. Further, complex structures will require multiple layers of wrappers. Imagine applying this technique to a stack of stacks! You would need to define a two-level wrapper, that wraps or unwraps each second-level stack as it is pushed onto or popped from the top-level stack. Because wrapped and legacy objects are distinct, it may be hard or even impossible to always ensure that the wrapped objects view all changes to the legacy objects.

The design of Java generics, by ensuring that legacy objects and generic objects are the same, avoids all of these problems with wrappers. The design of generics for C# is very different: legacy classes and generic classes are completely distinct, and any attempt to combine legacy collections and generic collections will bump into the difficulties with wrappers discussed here.

Conclusions

To review, we have seen both generic and legacy versions of a library and client. These generate equivalent class files, which greatly eases evolution. You can use a generic library with a legacy client, or a legacy library with a generic client. In the latter case, you can update the legacy library with generic method signatures, either by minimal changes to the source or by use of stub files.

The foundation stone that supports all this is the decision to implement generics by erasure, so that generic code generates essentially the same class files as legacy code—a property referred to as binary compatibility. Usually, adding generics in a natural way causes the legacy and generic versions to be binary compatible. However, there are some corner cases where caution is required; these are discussed in Section 8.4.

It is interesting to compare the design of generics in Java and in C#. In Java, generic types do not carry information about type parameters at run time, whereas arrays do contain information about the array element type at run time. In C#, both generic types and arrays contain information about parameter and element types at run time. Each approach has advantages and disadvantages. In the next chapter, we will discuss problems with casting and arrays that arise because Java does not reify information about type parameters, and these problems do not arise in C#. On the other hand, evolution in C# is much more difficult. Legacy and generic collection classes are completely distinct, and any attempt to combine legacy collections and generic collections will encounter the difficulties with wrappers discussed earlier. In contrast, as we've seen, evolution in Java is straightforward.

Maurice Naftalin is Director of Software Development at Morningside Light Ltd., a software consultancy in the United Kingdom.

Philip Wadler is a professor of theoretical computer science at the University of Edinburgh, Scotland, where his research focuses on functional and logic programming.


View catalog information for Java Generics and Collections

Return to ONJava.com.

Copyright © 2009 O'Reilly Media, Inc.