Sunday, January 1, 2012

Type Wildcard in Java Generics - A Tutorial

Overview

Type wildcard is the most tricky part of Java Generics. The readers are assumed having the basic knowledge of Java Generics. For a quick review of the basics of Java Generics, see my other post, The Basics of Java Generics. Type wildcard is only used in parameterized types, as the type arguments. A type wildcard is never used in a definition of generic type or generic method . In practice, such parameterized types are commonly used in method definitions, serving as the type of the formal parameters of the methods.

A parameterized type may take one of four forms:
  1. List<String>, here String is a concrete type, serving as the type argument for the parameterized type List<String>
  2. List<?>, where ? is a type wildcard without a bound, serving as the type argument for the parameterized type List<?> 
  3. List<? extends Number>, where ? is a type wildcard with a upper bound, serving as the type argument for the parameterized type List<? extends Number>, and Number is the upper bound of the wildcard.
  4. List<? supper Number>, where ? is a type wildcard with a lower bound, serving as the type argument for the parameterized type List<? super Number>, and Number is the lower bound of the wildcard.
For a parameterized type with a type wildcard as a type argument, the wildcard may have either a single upper or lower bound, but not both.

In a World without Type Wildcard

To understand why Java introduces the type wildcard for parameterized type, let’s look at an example. This example is about a circus. In the circus, there are two kinds of animals, birds and dogs. Brids can fly. Dogs can bark. A special kind of birds, nightingares, can also sing. Class hierarchy of animals used in this example are shown in Figure 1. Code for all kinds of animals are shown in Listing 1-1 to 1-4.

Figure 1 - Animal Hierarchy


Listing 1-1 - Animal
package animals;

public class Animal {
    private String name;
    
    public Animal(String name) {
        this.name = name;
    }
    
    public void jump() {
        System.out.println(getName() + " is jumping.");
    }
    
    public String getName() {
        return name;
    }
}

Listing 1-2 -Brid
package animals;

public class Bird extends Animal {    
    public Bird(String name) {
        super(name);
    }
    
    public void fly() {
        System.out.println(getName() + " is flying.");
    }
}

Listing 1-3 -  Nightingale
package animals;

public class Nightingale extends Bird {
    public Nightingale(String name) {
        super(name);
    }
    
    public void sing() {
        System.out.println(getName() + " is singing.");
    }
}

Listing 1-4 - Dog
package animals;

public class Dog extends Animal {   
    public Dog(String name) {
        super(name);
    }
    
    public void bark() {
        System.out.println(getName() + " is barking.");
    }
}

There is a kind of actors in the circus called AnimalTrainer. When given a collection of animals, the AnimalTrainer commands them to jump. The first version of AnimalTrainer is shown in Listing 2-1.

Listing 2-1 - AnimalTrainer Version 1 - Without Type Wildcard
package nowildcard;
import java.util.List;
import animals.Animal;

public class AnimalTrainer {
    public void act(List<Animal> animalList) {
        for (Animal animal : animalList) {
            animal.jump();
        }
    }
}

The first version of the main class, Circus, is shown in Listing 2-2. When the Circus program is launched, it will at first create an AnimalTrainer. Then a list of Animals is created, and two animals are added into the list. It finally invokes the act method, passing the animal list, on the AnimalTrainer. The AnimalTrainer acts by command every animal to jump. So far so good.

Listing 2-2 - Circus Version 1
package nowildcard;
import java.util.ArrayList;
import java.util.List;
import animals.Animal;
import animals.Bird;
import animals.Dog;

public class Circus {
    public static void main(String[] args) {
        AnimalTrainer animalTrainer = new AnimalTrainer();
        
        List<Animal> animalList = new ArrayList<Animal>();
        animalList.add(new Dog("Bob"));
        animalList.add(new Dog("Amy"));
                
        animalTrainer.act(animalList);
    }
}

The second version of the main class, Circus, is shown in Listing 2-3. The AnimalTrainer commands a list of birds to jump. We reason that it will be fine since a bird is actually an animal and can jump. This version of the Circus class, however, does not compile. The line with trouble is  animalTrainer.act(birdList); (Line 15) The error message is:
The method act(List<Animal>) in the type AnimalTrainer is not applicable for the arguments (List<Bird>)


Listing 2-3 - Circus Version 2
package nowildcard;
import java.util.ArrayList;
import java.util.List;

import animals.Bird;

public class Circus {
    public static void main(String[] args) {
        AnimalTrainer animalTrainer = new AnimalTrainer();
        
        List<Bird> birdList = new ArrayList<Bird>();
        birdList.add(new Bird("Tim"));
        birdList.add(new Bird("Nancy"));

        animalTrainer.act(birdList);
    }
}

In fact, Java does not regard List<Bird> as a subtype of List<Animal>. So the act method only accepts List<Animal> as argument, rejecting List<Bird>. You might wonder why Java has such an “unreasonable” rule. Actually, this rule exists for a very good reason. Let’s see why.


What if List<Bird> Were Regarded as a Subtype of List<Animal>?

If Java regarded List<Bird> as a subtype of List<Animal>, we were going to have trouble. To show the trouble, let’s update the Circus class as in Listing 3-3. At first lets look at the two new classes newly added, Magician as in Listing 3-1, and BirdTrainer as in Listing 3-2. The act method of Magician takes a list of Animals, and replaces all Animals in the list by two Dogs. The Magician class compiles perfectly. The act method of BirdTrainer takes a list of Birds and commands each of them to fly. The BirdTrainer class as well compiles perfectly. The Circus class (Version 3, Listing 3-3) does not compile for the same reason as in the Version 2 (Listing 2-3). Line 16 fails. The error message is:
The method act(List<Animal>) in the type Magician is not applicable for the arguments (List<Bird>)  

The Java compiler rejects Line 16 for a good reason. If Java regarded List<Bird> as a subtype of List<Animal> and allowed Line 16 compile, we were going to have run time exception because at run time, when the BirdTrainer got a list, the list actually would contain two Dogs. The Dogs would be commanded to fly but they cannot (a Dog object does not have a fly method). In other words, the Java type integrity would be broken.

To prevent trouble of this nature, Java does not regard List<Bird> as a subtype of List<Animal>. In a generic term of generics, it is said that the type parameter T in List<T> is non-variant.

Listing 3-1 - Magician Version 1

package whatif;
import java.util.List;

import animals.Animal;
import animals.Dog;

public class Magician {
    public void act(List<Animal> animalList) {
        for (int i = 0; i < animalList.size(); i++) {
            animalList.remove(i);
        }
        
        animalList.add(new Dog("Green"));
        animalList.add(new Dog("Red"));        
    }
}

Listing 3-2 - BirdTrainer Version 1

package whatif;
import java.util.List;

import animals.Bird;

public class BirdTrainer {
    public void act(List<Bird> birdList) {
        for (Bird bird : birdList) {
            bird.fly();
        }
    }
}

Listing 3-3 - Circus Version 3

package whatif;
import java.util.ArrayList;
import java.util.List;

import animals.Bird;

public class Circus {
    public static void main(String[] args) {
        BirdTrainer birdTrainer = new BirdTrainer();
        Magician magician = new Magician();
        
        List<Bird> birdList = new ArrayList<Bird>();
        birdList.add(new Bird("Tim"));
        birdList.add(new Bird("Nancy"));
        
        magician.act(birdList);    // this line won't compile.
        
        birdTrainer.act(birdList);
    }
}
 
Type Wildcard with a Upper Bound

Now since we understand why List<Bird> is not regarded as a subtype of List<Animal>, we can come back to seek a solution for our situation: How to enable an AnimalTrainer to accept a List<Bird> as well as a List<Animal>. Java’s solution is type wildcard. Specifically, we can change the AnimalTrainer class to be like in Listing 4-1 (Line 7: act(List<? extends Animal> animalList)). The ? in Line 7 is called a type wildcard, and ? extends Animal says Animal is the upper bound of the type wildcard.
With this version of AnimalTrainer, the main class, Circus, as in Listing 4-2 (it is essentially the same as in Listing 2-3) compiles and runs successfully.

Listing 4-1 - AnimalTrainer Version 2, With Type Wildcard With Upper Bound

package upperbound;
import java.util.List;

import animals.Animal;

public class AnimalTrainer {
    public void act(List<? extends Animal> animalList) {
        for (Animal animal : animalList) {
            animal.jump();
        }
    }
}

Listing 4-2 - Circus Version 4

package upperbound;
import java.util.ArrayList;
import java.util.List;

import animals.Bird;

public class Circus {
    public static void main(String[] args) {
        AnimalTrainer animalTrainer = new AnimalTrainer();
        
        List<Bird> birdList = new ArrayList<Bird>();
        birdList.add(new Bird("Tim"));
        birdList.add(new Bird("Nancy"));
        
        animalTrainer.act(birdList);
    }
}

In general, there are three rules about type wildcard with a upper bound, given a generic type G (e.g. List<E>), and two concrete types X and Y where Y is a subtype of X (e.g. Bird is a subtype of Animal):
  1. G<? extends Y> is subtype of G<? extends X> (e.g. List<? extends Bird> is a subtype of List<? extends Animal>
  2. G<X> is subtype of G<? extends X> (e.g. List<Bird> is a subtype of List<? extends Bird>)
  3. G<?> is just a shorthand for G<? extends Object> (e.g. List<?> is a shorthand for List<? extends Object>)
(For the formal specification, see 4.5.1.1 Type Argument Containment and Equivalence, The Java Language Specification, Third Edition)



(Those rules have something to do with the idea of covariance in the theory of generics. They however do not align very well with the theory.)


In the context of our example, Bird is a subtype of Animal, so List<? extends Bird> is a subtype of List<? extends Animal>. Meanwhile, List<Bird> is a subtype of List<? extends Bird>. Therefore List<Bird> is a subtype of List<? extends Animal>. That 

is the reason why the act method has a formal parameter of the type List<? extends Animal> and can accept List<Bird> and List<Animal> as argument.

You might wonder whether the Magician class can also be updated with type wildcard and bring back the trouble of messing up birds by dogs. It cannot. The catch is that when the act method of the Magician is updated to take a parameter of the type List<? extends Animal>, as in Listing 4-3 (Line 8), it is no longer allowed to call the add method of the List class. The compile error message is "The method add(capture#3-of ? extends Animal) in the type List<capture#3-of ? extends Animal> is not applicable for the arguments (Dog)". Therefore, it cannot add dogs into the list.  It fails because the add method here expects an argument of the type “? extends Animal” but Dog is not a subtype of it (Note: even though List<Dog> is a subtype of List<? extends Animal>, Dog is not a subtype of "? Extends Animal". More generally, no class is regard as a subtype of “? Extends Animal”.  It is said that “? Extends Animal” is an undefined type (Note: meanwhile, List<? Extends Animal> is a
well defined parameterized type.)

Listing 4-3 Magician Version 2


package upperbound;
import java.util.List;

import animals.Animal;
import animals.Dog;

public class Magician {
    public void act(List<? extends Animal> animalList) {
        for (int i = 0; i < animalList.size(); i++) {
            animalList.remove(i);
        }
        
        animalList.add(new Dog("Green")); // now these two lines do not compile
        animalList.add(new Dog("Red"));    
    }
}

Based on my experience, the general rule is like this: When a method with a parameter of a parameterized type that is one with type wildcard with a upper bound (e.g. act(List<? extends Animal>)), inside the body of the method, it is not allowed to call any method on the parameter object unless the method is parameterless (e.g. add(E element) on List<E>). I tried to find something about it in the Java Language Specification but found nothing. However, it seems that all Java compilers that I saw are implemented in this way. I could not figure out how to derive this rule from other more basic rules in the Java Specification.

Type Wildcard with a Lower Bound

Similar to type wildcard with a upper bound, a type wildcard may have a lower bound. (However, a type wildcard cannot have both upper and lower bound, nor have more than one upper or lower bounds). The syntax is like this: List<? super Bird> where Bird is the lower bound of the type wildcard.

In general, there are also three rules about type wildcard with a lower bound, given a generic type G (e.g. List<E>), and two concrete types X and Y where X is a subtype of Y (e.g. Bird is a subtype of Animal):
  1. G<? super Y> is a subtype of G<? super X> (e.g. List<? super Animal> is a subtype of List<? super Bird>
  2. G<X> is subtype of G<? super X> (e.g. List<Bird> is a subtype of List<? super Bird>)
(Again, for the formal specification, see 4.5.1.1 Type Argument Containment and Equivalence, The Java Language Specification, Third Edition)

(Those rules have something to do with the idea of contra-variance in the theory of generics. They however do not align very well with the theory.)

Let's illustrate the uses of type wildcard with a lower bound with another version of our Circus program as in Listing 5-1. In this version of the Circus class, an animalList (of type List<Animal>) and a birdList (of type List<Bird>) are created in the main method. Instead of adding animals or birds to the lists in the main method, the animalList is passed to the addBirds method of a BirdKeeper object, and the addDogs method of a DogKeeper object, to add birds and dogs into it. Then an AnimalTrainer acts on the animalList by commanding the animals (birds and dogs) in the list to jump. Also, the birdList is passed to the addBirds method of the BirdKeeper object to add birds to it.  And a BirdTrainer acts on the list by commanding the birds in the birdList to fly. The pertinent version of AnimalTrainer and BirdTrainer are shown in Listing 5-2 and 5-3.

Notice the following points in the above example. For the animalList to contain both birds and dogs, it must be defined as of type List<Animal>, instead of List<Bird> or List<Dog>. For the BirdTrainer to command birds in the birdList to fly, the birdList must be defined as of type List<Bird>, instead of List<Animal>.

For the program to work, the addBirds method of the BirdKeeper class must be able to:
  1. accept a List<Animal> as argument (Line 21, the Circus class)
  2. accept a List<Bird> as argument (Line 26, the Circus class)
  3. add birds into the List<Animal> and the List<Bird> (Line 7-8, the BirdKeeper class)
The solution is shown in Listing 5-4. The type of the formal parameter to the addBirds method is List<? super Bird>. The parameterized type that servers as the type of the formal parameter is a type wildcard with a lower bound. Other choices won't work. If we had the method header as public void addBirds(List<Animal> animalList), the method would not accept List<Bird> as argument; if we If we had the method header as public void addBirds(List<Bird> animalList), the method would not accept List<Animal> as argument; If we had the method header as public void addBirds(List<? extends Animal> animalList), the method would not be able to add anything to the list (i.e. animalList). A type wildcard with a lower bound is the necessary solution to this case.  

Notice that it is allowed to call a method with parameters (e.g the add method of List<E>) on an object referenced by a formal parameter of type wildcard with a lower bound (e.g. the parameter named animalList in the addBirds method of the BirdKeeper class), while it is not allowed if the wildcard has a upper bound.

Similarly, the DogKeeper class is shown in Listing 5-5.

Listing 5-1 - Circus Version 5

package lowerbound;
import java.util.ArrayList;
import java.util.List;

import animals.Animal;
import animals.Bird;

public class Circus {
    public static void main(String[] args) {
        AnimalTrainer animalTrainer = new AnimalTrainer();
        BirdTrainer birdTrainer = new BirdTrainer();
        
        List<Animal> animalList = new ArrayList<Animal>();
        
        BirdKeeper birdKeeper = new BirdKeeper();
        birdKeeper.addBirds(animalList);
               
        DogKeeper dogKeeper = new DogKeeper();        
        dogKeeper.addDogs(animalList);
                
        animalTrainer.act(animalList);
        
        List<Bird> birdList = new ArrayList<Bird>();
        birdKeeper.addBirds(birdList);
        
        birdTrainer.act(birdList);
    }
}

Listing 5-2 - AnimalTrainer Version 3

package lowerbound;
import java.util.List;
import animals.Animal;

public class AnimalTrainer {
    public void act(List<Animal> animalList) {
        for (Animal animal : animalList) {
            animal.jump();
        }
    }
}

Listing 5-3 - BirdTrainer Version 2

package lowerbound;
import java.util.List;
import animals.Bird;

public class BirdTrainer {
    public void act(List<Bird> birdList) {
        for (Bird bird : birdList) {
            bird.fly();
        }
    }
}


Listing 5-4 - BirdKeeper
package lowerbound;
import java.util.List;
import animals.Bird;

public class BirdKeeper {
    public void addBirds(List<? super Bird> animalList) {
        animalList.add(new Bird("Tim"));
        animalList.add(new Bird("Nancy"));
    }
}

Listing 5-5 - DogKeeper

package lowerbound;
import java.util.List;
import animals.Dog;

public class DogKeeper {
    public void addDogs(List<? super Dog> animalList) {
        animalList.add(new Dog("Bob"));
        animalList.add(new Dog("Amy"));
    }
}

Finally, notice that the addBirds method of the BirdKeeper class won't accept an argument of the type List<Nightingale> because List<Nightingale> is not regarded as a subtype of List<? super Bird>. The version of the Circus class as shown in Listing 5-5 won't compile. Line 30, birdKeeper.addBirds(nightingaleList);, will fail. The compile error is:
The method addBirds(List<? super Bird>) in the type BirdKeeper is not applicable for the arguments (List<nightingale>)

Listing 5-5 - Circus Version 6

package lowerbound;
import java.util.ArrayList;
import java.util.List;
import animals.Animal;
import animals.Bird;
import animals.Nightingale;

public class Circus {
    public static void main(String[] args) {
        AnimalTrainer animalTrainer = new AnimalTrainer();
        BirdTrainer birdTrainer = new BirdTrainer();
        
        List<Animal> animalList = new ArrayList<Animal>();
        
        BirdKeeper birdKeeper = new BirdKeeper();
        birdKeeper.addBirds(animalList);
        
        
        DogKeeper dogKeeper = new DogKeeper();        
        dogKeeper.addDogs(animalList);
                
        animalTrainer.act(animalList);
        
        List<Bird> birdList = new ArrayList<Bird>();
        birdKeeper.addBirds(birdList);
        
        birdTrainer.act(birdList);
        
        List<Nightingale> nightingaleList = new ArrayList<Nightingale>();
        birdKeeper.addBirds(nightingaleList); // does not compile
    }
}

Conclusion
  1. Type wildcard is used to increase flexibility of methods that take parameters of parameterized types
  2. It is not allowed to call a method on an object referenced by a parameter of a parameterized type with type wildcard with a upper bound unless the method is parameter less.
  3. It is  allowed to call any method on an object referenced by a parameter of a parameterized type with type wildcard with a lower bound.
References 
  • The Java Language Specification, Third Edition, by James Gosling, Bill Joy, Guy Steele, and Gilad Bracha, Addison Wesley Professional, 2005
  • The Java Programming Language, 4th Edition, by Ken Arnold, James Gosling, and David Holmes, Prentice Hall PTR, 2005

6 comments:

Enum Examples in Java said...

Good piece of information on Generics. thanks for sharing. You may also like Generics tutorial in Java

ARM said...

Hi,

The best post on basic genecric concept. It really help me alot.
Keep posting.

Thanks,
ARM

Bhoopendra kaurav said...

This is the best place to learn generic concept

Anonymous said...

I suppose here is something wrong, Isn't it?

G is just a shorthand for G (e.g. List is a shorthand for List)

Anonymous said...

I suppose here is something wrong, Isn't it?

G<?> is just a shorthand for G<? super Object> (e.g. List<?> is a shorthand for List<? super Object>)

Ted Gao said...

It was incorrect to say "G is just a shorthand for G (e.g. List is a shorthand for List)". I have corrected it. Thanks to Anonymous for pointing out it.