Section 8.3. Specialize to Create Reifiable Types

8.3. Specialize to Create Reifiable Types

Parameterized types are not reifiable, but some operations, such as instance tests, casting, and array creation apply only to reifiable types. In such cases, one workaround is to create a specialized version of the parameterized type. Specialized versions can be created either by delegation (that is, wrappers) or by inheritance (that is, subclassing), and we discuss each in turn.

Example 8.1 shows how to specialize lists to strings; specializing to other types is similar. We begin by specializing the List interface to the desired type:

Example 8-1. Specialize to create reifiable types

 interface ListString extends List<String> {} class ListStrings {   public static ListString wrap(final List<String> list) {     class Random extends AbstractList<String>       implements ListString, RandomAccess     {       public int size() { return list.size(); }       public String get(int i) { return list.get(i); }       public String set(int i, String s) { return list.set(i,s); }       public String remove(int i) { return list.remove(i); }       public void add(int i, String s) { list.add(i,s); }     }     class Sequential extends AbstractSequentialList<String>       implements ListString     {       public int size() { return list.size(); }       public ListIterator<String> listIterator(int index) {         final ListIterator<String> it = list.listIterator(index);         return new ListIterator<String>() {           public void add(String s) { it.add(s); }           public boolean hasNext() { return it.hasNext(); }           public boolean hasPrevious() { return it.hasPrevious(); }           public String next() { return it.next(); }           public int nextIndex() { return it.nextIndex(); }           public String previous() { return it.previous(); }           public int previousIndex() { return it.previousIndex(); }           public void remove() { it.remove(); }           public void set(String s) { it.set(s); }         };       }     }     return list instanceof RandomAccess ? new Random() : new Sequential();   } } class ArrayListString extends ArrayList<String> implements ListString {   public ArrayListString() { super(); }   public ArrayListString(Collection<? extends String> c) { super(c); }   public ArrayListString(int capacity) { super(capacity); } } 

 interface ListString extends List<String> {} 

This declares ListString (an unparameterized type, hence reifiable) to be a subtype of List<String> (a parameterized type, hence not reifiable). Thus, every value of the first type also belongs to the second, but not conversely. The interface declares no new methods; it simply specializes the existing methods to the parameter type String.

Delegation To specialize by delegation, we define a static method wrap that takes an argument of type List<String> and returns a result of type ListString. The Java library places methods that act on the interface Collection in a class called Collections, so we place the method wrap in a class called ListStrings.

Here is an example of its use:

 List<? extends List<?>> lists =   Arrays.asList(     ListStrings.wrap(Arrays.asList("one","two")),     Arrays.asList(3,4),     Arrays.asList("five","six"),     ListStrings.wrap(Arrays.asList("seven","eight"))   ); ListString[] array = new ListString[2]; int i = 0; for (List<?> list : lists)   if (list instanceof ListString)     array[i++] = (ListString)list; assert Arrays.toString(array).equals("[[one, two], [seven, eight]]"); 

This creates a list of lists, then scans it for those lists that implement ListString and places those into an array. Array creation, instance tests, and casts now pose no problems, as they act on the reifiable type ListString rather than the nonreifiable type List<String>. Observe that a List<String> that has not been wrapped will not be recognized as an instance of ListString; this is why the third list in the list of lists is not copied into the array.

The ListStrings class is straightforward to implement, although some care is required to preserve good performance. The Java Collections Framework specifies that whenever a list supports fast random access it should implement the marker interface RandomAccess, to allow generic algorithms to perform well when applied to either random or sequential access lists. It also provides two abstract classes, AbstractList and AbstractSequentialList, suitable for defining random and sequential access lists. For example, ArrayList implements RandomAccess and extends AbstractList, while LinkedList extends Abstract-SequentialList. Class AbstractList defines the methods of the List interface in terms of five abstract methods that provide random access and must be defined in a subclass (size, get, set, add, remove). Similarly, class AbstractSequentialList defines all methods of the List interface in terms of two abstract methods that provide sequential access and must be defined in a subclass (size, listIterator).

The wrap method checks whether the given list implements the interface RandomAccess. If so, it returns an instance of class Random that extends AbstractList and implements RandomAccess, and otherwise it returns an instance of class Sequential that extends AbstractSequentialList. Class Random implements the five methods that must be provided by a subclass of AbstractList. Similarly, class Sequential implements the two methods that must be provided by a subclass of AbstractSequentialList, where the second of these returns a class that implements the nine methods of the ListIterator interface. Implementing the list iterator by delegation instead of simply returning the original list iterator improves the security properties of the wrapper, as discussed below. All of these methods are implemented straightforwardly by delegation.

The wrap method returns a view of the underlying list that will raise a class cast exception if any attempt is made to insert an element into the list that is not of type String. These checks are similar to those provided by the checkedList wrapper. However, for wrap the relevant casts are inserted by the compiler (one reason for implementing the nine methods of the listIterator interface by delegation is to ensure that these casts are inserted), while for checked lists the casts are performed by reflection. Generics usually render these checks redundant, but they can be helpful in the presence of legacy code or unchecked warnings, or when dealing with security issues such as those discussed in Section 8.2.

The code shown here was designed to balance power against brevity (it's only thiry-three lines), but other variations are possible. A less complete version might implement only random access if one could guarantee it was never applied to a sequential access list, or vice versa. A more efficient version might skip the use of AbstractList and Abstract-SequentialList, and instead directly delegate all 25 methods of the List interface together with the toString method (see the source code for Collections.checkedList for a model). You also might want to provide additional methods in the ListString interface, such as an unwrap method that returns the underlying List<String>, or a version of subList that returns a ListString rather than a List<String> by recursively applying wrap to the delegated call.

Inheritance To specialize by inheritance, we declare a specialized class that implements the specialized interface and inherits from a suitable implementation of lists. Example 8.1 shows an implementation that specializes ArrayList, which we repeat here:

 class ArrayListString extends ArrayList<String> implements ListString {   public ArrayListString() { super(); }   public ArrayListString(Collection<? extends String> c) { super(c); }   public ArrayListString(int capacity) { super(capacity); } } 

The code is quite compact. All methods are inherited from the superclass, so we only need to define specialized constructors. If the only constructor required was the default constructor, then the class body could be completely empty!

The previous example still works if we create the initial list using inheritance rather than delegation:

 List<? extends List<?>> lists =   Arrays.asList(     new ArrayListString(Arrays.asList("one","two")),     Arrays.asList(3,4),     Arrays.asList("five","six"),     new ArrayListString(Arrays.asList("seven","eight"))   ); ListString[] array = new ListString[2]; int i = 0; for (List<?> list : lists)   if (list instanceof ListString)     array[i++] = (ListString)list; assert Arrays.toString(array).equals("[[one, two], [seven, eight]]"); 

As before, array creation, instance tests, and casts now pose no problem.

However, delegation and inheritance are not interchangeable. Specialization by delegation creates a view of an underlying list, while specialization by inheritance constructs a new list. Further, specialization by delegation has better security properties than specialization by inheritance. Here is an example:

 List<String> original = new ArrayList<String>(); ListString delegated = ListStrings.wrap(original); ListString inherited = new ArrayListString(original); delegated.add("one"); inherited.add("two"); try {   ((List)delegated).add(3);  // unchecked, class cast error } catch (ClassCastException e) {} ((List)inherited).add(4);  // unchecked, no class cast error! assert original.toString().equals("[one]"); assert delegated.toString().equals("[one]"); assert inherited.toString().equals("[two, 4]"); 

Here an original list serves as the basis for two specialized lists, one created by delegation and one by inheritance. Elements added to the delegated list appear in the original, but elements added to the inherited list do not. Type checking normally would prevent any attempt to add an element that is not a string to any object of type List<String>, specialized or not, but such attempts may occur in the presence of legacy code or unchecked warnings. Here we cast to a raw type and use an unchecked call to attempt to add an integer to the delegated and inherited lists. The attempt on the delegated list raises a class cast exception, while the attempt on the inherited list succeeds. To force the second attempt to fail, we should wrap the inherited list using checkedList, as described in Section 8.1.

Another difference is that inheritance can only be applied to a public implementation that can be subclassed (such as ArrayList or LinkedList), whereas delegation can create a view of any list (including lists returned by methods such as Arrays.asList or Collections.immutableList, or by the sublist method on lists).

The security properties of specialization by inheritance can be improved by declaring a specialized signature for any method that adds an element to the list or sets an element:

 class ArrayListString extends ArrayList<String> implements ListString {   public ArrayListString() { super(); }   public ArrayListString(Collection<? extends String> c) { this.addAll(c); }   public ArrayListString(int capacity) { super(capacity); }   public boolean addAll(Collection<? extends String> c) {     for (String s : c) {}  // check that c contains only strings     return super.addAll(c);   }   public boolean add(String element) { return super.add(element); }   public void add(int index, String element) { super.add(index, element); }   public String set(int index, String element) {     return super.set(index, element);   } } 

Now, any attempt to add or set an element that is not a string will raise a class cast exception. However, this property depends on a subtle implementation detail, namely that any other methods that add or set an element (for instance, the add method in listIterator) are implemented in terms of the methods specialized above. In general, if security is desired, delegation is more robust.

Other Types Specialization at other types works similarly. For example, replacing String by Integer in Example 8.1 gives an interface ListInteger and classes List-Integers and ArrayListInteger. This even works for lists of lists. For example, replacing String by ListString in Example 8.1 gives an interface ListListString and classes ListListStrings and ArrayListListString.

However, specialization at wildcard types can be problematic. Say we wanted to specialize both of the types List<Number> and List<? extends Number>. We might expect to use the following declarations:

 // illegal interface ListNumber extends List<Number>, ListExtendsNumber {} interface ListExtendsNumber extends List<? extends Number> {} 

This falls foul of two problems: the first interface extends two different interfaces with the same erasure, which is not allowed (see Section 4.4), and the second interface has a supertype with a wildcard at the top level, which is also not allowed (see Section 2.8). The only workaround is to avoid specialization of types containing wildcards; fortunately, this should rarely be a problem.