Assigning to multilevel wildcards

Question

Simple class:

class Pair<K,V> {

}

And a few assignments:

Collection<Pair<String,Long>> c1 = new ArrayList<Pair<String,Long>>();
Collection<Pair<String,Long>> c2 = c1; // ok
Collection<Pair<String,?>> c3 = c1; // this does not compile
Collection<? extends Pair<String,?>> c4 = c1; // ok

why does bullet number three not compile while the fourth one is perfectly legal?

Compiler error:

Type mismatch: cannot convert from Collection<Pair<String,Long>> to Collection<Pair<String,?>>

Answer 1

I will try to explain the Java generics using two simple rules. These rules suffice to answer your question and are basically enough to remember for almost any case:

1. Two generic types X<A> and X<B> are never assignable unless A = B. I.e., generics are invariant by default.
2. Wildcards allow the assignment of X<A>:
   • to X<?>
   • to X<? extends T> iff A is assignable to T (apply rules recursively to A and T)
   • to X<? super T> iff T is assignable to A (apply rules recursively to T and A)

Case c3 = c1

In your example, you try to assign Collection<Pair<String,Long>> to Collection<Pair<String,?>>. That is, in your case A = Pair<String,Long> and B = Pair<String,?>. Since these types are not equal, they are not assignable; they violate Rule 1.

The question is, why doesn't the wildcard help? The answer is simple:
Rule 2 is NOT transitive. I.e., X<X<A>> cannot be assinged to X<X<?>>, there has to be a wildcard in the outermost level; otherwise Rule 2 does not apply to the outermost level.

Case c4 = c1

Here, you got a wildcard in the outer type. Because it is in the outer type, Rule 2 kicks in: A = Pair<String,?> is assignable to B = ? extends Pair<String,Long> (again, because of Rule 2). Therefore, this is legal.

General approach

Here is how you can check any complex generic type: Simply check each generic level by level using the two rules. Start with the outermost level. Once a level violates a rules, you know the assignment is illegal; if all levels adhere to the rules, then the assignment is legal. Lets consider your types again:

X = Collection<Pair<String,Long>>
Y = Collection<Pair<String,?>>
Z = Collection<? extends Pair<String,?>> 

Is X assignable to Y ?

// Outermost level:
A = Pair<String,Long>, B = Pair<String,?>
  => B is no wildcard and A != B (Rule 1), so this is illegal!

Is X assignable to Z ?

// Outermost level:
A = Pair<String,Long>, B = ? extends Pair<String,?>
  => We got a wildcard, so Rule 2 states this is legal if the inner level is legal
// Inner level: (we have to check both parameters)
A = String, B = String => Equal, Rule 1 applies, fine!
A = Long, B = ? => B is wildcard, Rule 2 applies, fine!

Simple Rule to Remember

Each level of generic nesting either needs to be completely identical (A=B) or B needs to contain a wildcard in this level.

Answer 2

First of all, let's simplify the code by removing extra type parameter:

Collection<List<Long>> c1 = new ArrayList<List<Long>>();
Collection<List<Long>> c2 = c1; // ok
Collection<List<?>> c3 = c1; // this does not compile
Collection<? extends List<?>> c4 = c1; // ok

We know that List<? extends T> essentially means "a List you can get T from", and List<?> is the same thing as List<? extends Object>.

So, types of the variables above can be explained as follows:

• c3: "a collection of Lists that allow you to get Objects from them
• c4: "a collection that allows you to get Lists that allow you to get Object from them

In particular, this explanation incurs the following:

// The following line compiles, 
// because `ArrayList<String>` is a `List` you can get `Object`s from
c3.add(new ArrayList<String>()); 

// The following line does not compile, 
// because type of c4 doesn't allow you to put anything into it
c4.add(new ArrayList<String>());

Now, it c3 = c1 were allowed, you can see that c3.add(new ArrayList<String>()) would break type safety of c1:

Collection<List<Long>> c1 = new ArrayList<List<Long>>();
Collection<List<?>> c3 = c1;

c3.add(Arrays.asList("foo")); 

for (List<Long> l: c1) {
    for (Long value: l) {
        // Oops, value is not a Long!
    }
}

Answer 3

The key thing to remember here is that nested wildcards don't capture.

What this means is that the "normal" behavior you expect from top-level wildcards (i.e. wildcards stand for one specific something) doesn't apply to nested wildcards. Instead, nested wildcards stand for any type.

For example, take this declaration:

List<?> l;

This means l is a List of one specific type. Easy.

But what about this?

Collection<List<?>> c;

This is not a Collection of Lists of one specific type. This is a Collection of Lists, each of which is one specific type.

For example, you were expecting something like this to happen:

Collection<List<?>> c = new ArrayList<List<Long>>(); // Not valid, but pretend it is
c.add(new ArrayList<Long>()); // Valid
c.add(new ArrayList<Integer>()); // Invalid, because c is a Collection of Lists of Long

But consider this:

List<?> l = new ArrayList<String>();
c.add(l); // Should this compile?

The type of l exactly matches the type parameter for c, right? So shouldn't you be able to add l to c, even though l isn't a List<Long>?

Also consider this:

c.iterator().next(); // Assume there is an element to return

What type should this return? iterator() returns an Iterator<E>, and next() returns E, which means... c.iterator().next() returns a List<?>. Which is not the List<Long> you were expecting. Why is that?

Because nested wildcards don't capture. And that is the key distinction here. The wildcard in List<?> doesn't capture a single type "overall". It captures a single type for each of the elements in the Collection.

Thus, this is perfectly valid code:

Collection<List<?>> odd = new ArrayList<List<?>>();
odd.add(new ArrayList<String>());
odd.add(new ArrayList<Long>());
List<?> l = odd.iterator().next();
        // returns the ArrayList<String>, but because odd is parameterized with
        // List<?> we can technically end up with a list of anything

Keeping this in mind, let's look at your examples.

---

Collection<Pair<String,Long>> c1 = new ArrayList<Pair<String,Long>>();
Collection<Pair<String,Long>> c2 = c1;

That's intuitively OK. The types exactly match, so c1 is assignable to c2.

---

Collection<Pair<String,Long>> c1 = new ArrayList<Pair<String,Long>>();
Collection<Pair<String,?>> c3 = c1;

Now, let's look back. A Collection<Pair<String,?>> isn't a Collection of Pairs of Strings and a single unknown type. It's a Collection of Pairs, each of which is a pair of a String and some unknown type, which may or may not be the same type as another pair in the collection. So this is valid:

// Assume an appropriate object was assigned to c3
Pair<String, ?> p1 = new Pair<String, String>("Hello", "World");
Pair<String, ?> p2 = new Pair<String, List<String>>("Lorem", new ArrayList<>());
Pair<String, ?> p3 = new Pair<String, Map<String, Integer>>("Ispum", new HashMap<>());
c3.add(p1);
c3.add(p2);
c3.add(p3);

And because this is valid for c3, but shouldn't be valid for c1, assigning c1 to c3 isn't allowed, because it would allow you to put stuff into an ArrayList<Pair<String, Long>> that isn't a Pair<String, Long>.

---

Collection<Pair<String,Long>> c1 = new ArrayList<Pair<String,Long>>();
Collection<? extends Pair<String,?>> c4 = c1;

Now, this is a bit more tricky. The top-level captures one specific type that extends Pair<String, ?>. Because wildcards are supertypes of specific types (e.g. List<?> is a supertype of List<Integer>), Pair<String, Long> can be captured by ? extends Pair<String, ?>, because the former extends the latter. Thus, because Pair<String, Long> is assignment-compatible with ? extends Pair<String, ?>, the assignment is valid.

---

As you can tell from the variety of answers here, there are multiple ways of explaining the behavior of nested wildcards. I was going for a bit more of an intuitive explanation, which I hope I achieved.

Answer 4

One of the advantages of Java generics is stronger type checks at compile time. So anything declared in generics should exactly match. To make it a simple answer I would use some examples.

To initialize a list of numbers you could do like.

List<Number> numbers = new ArrayList<Number>();

This technically means the List "numbers" can store any object that is either a number or sub-class of number. But we cannot initilaize this list with sub types. Anything given in generic tags <> should literally match the assignment. (Java 7 provides a type inference though)

List<Number> intNumbers = new ArrayList<Interger>(); // Compile Error
List<Number> doubleNumbers = new ArrayList<Double>(); // Compile Error
List<List<String>> list = new ArrayList<ArrayList<String>>(); // Compile Error

Even though Integer and Double are subclasses of Number the generics prevents from these initialization. The generic argument specified inside <> should exactly match.

Now if assignment is tightly bound how can the numbers list store sub-class objects? The answer is the add(), addlAll().. etc methods accepts E or anything that extends E, where E is the generic type we gave. So in case of the list "numbers" E is Number so the following statements are perfectly valid.

List<Integer> intNumbers = new ArrayList<Integer>();
List<Number> numbers = new ArrayList<Number>();
numbers.add(new Integer(1));
numbers.add(new Double(1.0));
numbers.addAll(intNumbers);

Again one exception to this is the wildcards. The wildcard is used to accept any arguments. So the following statments are valid.

List<?> numbers = new ArrayList<Number>();
Map<?, ?> unKnownMap = new HashMap<String, String>();

// OR

List<Integer> intNumbers = new ArrayList<Integer>();
List<?> numbers = intNumbers;

Similarly

Pair<String,?> p = new Pair<String, Long>(); // Is valid.

But now we cannot add anything to this list as the element should extend ? and that is an unknown type and the only allowable element is null, which is a member of every type. Java does not infer this from the assignment. So the following result in error

List<?> numbers = new ArrayList<Number>(); // Works fine.
numbers.add(new Integer(1)); // Compile Error
numbers.add(new Double(1.0)); // Compile Error

Also the wildcard inference happens only on one level. Any nesting should again match exactly like usual generics. So

List<List<?>> list = new ArrayList<List<String>>(); // Compile error because nested List<String> doesn not exactly match List<?>
List<List<?>> list = new ArrayList<List<?>>(); // OK - Valid 
List<List<Integer>> intList = new ArrayList<List<Integer>>();
List<List<?>> numbers = intList; // Compile error because nested List<Integer> doesn not exactly match List<?>

So this is your case

Collection<Pair<String,Long>> c1 = new ArrayList<Pair<String,Long>>();
Collection<Pair<String,Long>> c2 = c1; // ok
Collection<Pair<String,?>> c3 = c1; // Compile error because nested Pair<String,?> doesn not exactly match Pair<String,Long>

So you could do something like

Collection<Pair<String,?>> c3 = new ArrayList<Pair<String,?>>(c2);
//OR
Collection<Pair<String,?>> c3 = new ArrayList<Pair<String,?>>();
c3.addAll(c2);

Case 4: When you say List<? extends List<?>> its again first level. That means it checks whether the element under question extends List<?>.

List<? extends List<?>> list = new ArrayList<List<String>>(); // Works similar to List<?> l = new ArrayList<String>();
List<? extends List<List<?>>> numbers = new ArrayList<List<List<String>>>(); // Compile error - Nested level similar to List<List<String>> lst = new ArrayList<List<String>>();

So Collection<Pair<String,?>> c3 = new ArrayList<Pair<String, Long>>(); is similar to Pair<String,?> p = new Pair<String, Long>();